（计算机应用技术专业论文）交互式可视化例外数据挖掘方法研究及应用.pdf

论文题目：交互式可视化例外数据挖掘方法研究及应用 专业：计算机应用技术 硕士生：赵彩 ( 签名) 起型j 指导教师：李爱国 ( 签名达娶蠡 摘要 本文针对胜利油田生产数据库高效例外数据挖掘问题，在综合研究各种可视化例外 数据挖掘方法以及胜利油田生产数据库特点的基础上，提出了一种新颖的交互式可视化 例外数据挖掘方法。该方法提高了例外数据挖掘的效率与精度，并将其应用到胜利油田 生产数据库中验证了该方法的有效性，为后续工作提供了技术支撑和理论基础。主要研 究内容和取得的成果如下： ( 1 ) 通过研究数据挖掘中的各种可视化方法，提出了一种新颖的交互式可视化例外 数据挖掘方法。该方法思路为：先将数据库表中的数值属性值转化为相应字符，再给各 字符赋以相应颜色值，每次可视化显示出4 个连续属性的模式分布情况。根据可视化图 形所识别出的频繁模式候选集以及例外模式定义，计算每条数据的例外支持度，由所设 定阈值即可得到例外数据。将该方法与经典例外检测算法l o f 和q r n o f 算法进行了实 验对比，实验数据采用真实的胜利油田生产数据集。实验结果显示所提方法在计算速度 以及精度上都优于l o f 及q r n o f ，与l o f 及q r n o f 相比速度分别提高了1 6 倍和5 倍，精度分别提高了2 7 和4 0 。在着色方面，该方法对p b c 方法进行了改进，更加 适应人的感知，使人们更易于对可视化图形的识别与分析。 c 2 ) 针对胜利油田生产数据库的分布式特点，在研究分布式数据挖掘方法的基础上， 本文给出了适合胜利油田生产数据库的分布式可视化例外数据挖掘任务分配模型和具 体算法。并运用了s o c k e t 通信机制实现了客户端与服务器之闻的交互。 ( 3 ) 在上述两项研究工作的基础上。我们将所提出的交互式可视化例外数据挖掘方 法应用到胜利油田生产数据库中验证其有效性，并设计实现针对胜利油田生产数据库的 交互式可视化例外数据挖掘的原型软件系统。该系统实现了高效检测胜利油田生产数据 库中的例外数据同时还可以实现资源共享，提高了资源利用率，同时也能使数据挖掘过 程透明化，节省了人力。该系统同样适用于大规模数据库的例外数据检测，具有一定的 通用性并为后续工作打下坚实的基础。 关键词：数据库；知识获取；数据挖掘；可视化；例外模式 研究类型：应用研究 s u b j e e t ：i n t e r a c t i v ev i s u a l i z a t i o no u t l i e rd a t am i n i n ga n di t s a p p l i c a t i o n s p e c i a l t y ：c o m p u t e ra p p l i c a t i o nt e c h n o l o g y n a m e：z h a o c a i i n s t r u c t o r ：l ia i g u o a b s t r a c t ( s i g n a t u r e ) ( s i g n a t u r e ) 2j 凶 t 1 1 i s p a p e rm a i n l yf o c u s e so nt h ee f f e c t i v eo u t l i e r d a t am i n i n gp r o b l e mo fs l o f s ( s h e n g l io i lf i e l d ) p r o d u c t i o nd a t a b a s e b a s e do np l e n t yo fr e s e a r c hw o r k so nv i s u a l i z a t i o n o u t l i e rd a t am i n i n gm e t h o da n dt h ec h a r a c t e r so fs l o f sp r o d u c t i o nd a t a b a s e ，w ep r o p o s e d o n en o v e li n t e r a c t i v ev i s u a l i z a t i o no u t l i e rd a t am i n i n gm e t h o d ，w h i c he n h a n c e se f f i c i e n c ya n d t h ep r e c i s i o no no u t l i e rd a t am i n i n g 1 1 1 ee f f e c t i v e l yi sp r o v e db yt h ea c t u a lu s eo ns l o f s p r o d u c t i o nd a t a b a s e i th a sp r o v i d e dt h et e c h n i c a ls u p p o r tf o rt h ef u t u r ew o r ka n dt h e o r e t i c f o u n d a t i o n t h em a i nc o n t e n t sa n da c h i e v e m e n t so f t h er e s e a r c ha r ea sf o l l o w s ： ( 1 ) t h r o u g hr e s e a r c h i n gv a r i o u sv i s u a l i z a t i o nm e t h o d so nd a t am i n i n g ，w ep r o p o s ea n o v e li n t e r a c t i v ev i s u a l i z a t i o no u t l i e rd a t am i n i n gm e t h o d t h ew a yi sa sf o l l o w s ：f i r s tw e t r a n s f o r mt h en u m b e rv a l u eo ff i e l d si nd a t a b a s et a b l et oc o r r e s p o n d i n gc h a r a c t e r ；t h e nw e s e te a c hc h a r a c t e re n d u ew i t hc o r r e s p o n d i n gc o l o rv a l u e e a c ht i m et h ev i s u a l i z a t i o nm o d e l s h o w st h ed i s t r i b u t i o ns i t u a t i o no f4c o n t i n u a l l ya t t r i b u t e s ；b a s e do nt h ef r e q u e n tp a t t e r n s c a n d i d a t e - s e to ft h ev i s u a l i z a t i o nm o d e la n dt h ed e f i n i t i o no fo u t l i e rp a t t e r n , w ec a l c u l a t et h e o u t l i e rs u p p o r td e g r e eo ne a c hd a t at oo b t a i nt h eo u t l i e r sb yp r e - e s t a b l i s h e dt h r e s h o l dv a l u e w ec o n t r a s to u rm e t h o dw i t hc l a s s i c a ll o fa n dq r n o fo u t l i e rd e t e c t i n ga l g o r i t h m s t h e e x p e r i m e n td a t as e te m p l o y st h es l o f sp r o d u c t i o nd a t as d t h ee x p e r i m e n tr e s u l ts h o w so u r m e t h o ds u p e r i o rt ol o fa n dq r n o fi nt h ec o m p u t a t i o ns p e e da n dp r e c i s i o n i nt h e c o m p u t a t i o ns p e e ds i d e ，i te n h a n c e d1 6t i m e sa n d5t i m e ss e p a r a t e l y ；i nt h ep r e c i s i o ns i d e , i t e n h a n c e d2 7 a n d4 0 s e p a r a t e l y i ta l s os u p e r i o rt oa n di m p r o v eo nt h ep b ca l g o r i t h mi n p i g m e n t a t i o nw a y o u rm e t h o de v e nm o r ea d a p t st op e r s o n ss e n s a t i o na n dh e l p sp e o p l et o r e c o g n i z ea n da n a l y z em o r ee a s i l y ( 2 ) i na l l u s i o nt ot h ed i s t r i b u t e dc h a r a c t e r i s t i co fs l o f sp r o d u c t i o nd a t a b a s ea n db a s e d o nt h ed i s t r i b u t e dd a t am i n i n gr e s e a r c h ，w eg i v eo n ea s s i g n m e n ta l l o tm o d e la n do n ec o n c r e t e a l g o r i t h m o ft h ed i s t r i b u t e dv i s u a l i z a t i o no u t l i e rd a t am i n i n g ，w h i c hs u i t e dt os l o f s p r o d u c t i o nd a t a b a s e w er e a l i z et h ei n t e r a c t i v ec o r r e s p o n d e n c eb e t w e e nc l i e n ta n ds e r v e rb y s o c k e tm e c h a n i s m ( 3 ) b a s e do na b o v et w or e s e a r c hw o r k s ，w ea p p l i e dt h ei n t e r a c t i v ev i s u a l i z a t i o no u t l i e r d a t am i n i n gm e t h o dt os l o f sp r o d u c t i o nd a t a b a s et ot e s t i f yi t sv a l i d i t y w ed e s i g na n d r e a l i z ea p r o t o t y p es o f t w a r es y s t e mf o ri n t e r a c t i v ev i s u a l i z a t i o no u t l i e rd a t am i n i n go ns l o f s p r o d u c t i o n d a t a b a s e t h i ss y s t e mr e a l i z e se f f e c t i v e d e t e c t i n g o u t l i e rd a t ai ns l o f s p r o d u c t i o nd a t a b a s ea n d r e s o u r c e sc o m m u n i o n i ta l s oe n h a n c e st h eu s i n go fr e s o u r c e s ，s a v e s m a n p o w e ra n dm a k e sd a t am i n i n gp r o c e s s i n gv i t r i f i c a t i o n t h i ss y s t e mh a sc o m m o n c h a r a c t e r i s t i c sw h i c ha l s oc a nb es u i t a b l ef o ro u t l i e rd a t ad e t e c t i n go nl a r g e - s c a l ed a t a b a s e i t b u i l d st h es o l i df o u n d a t i o nf o rt h ef o l l o w i n gw o r k s k n o w l e d g ea c q u i r e m e n t d a t am i n i n gv i s u a l i z a t i o n o u t l i e rp a t t e r n s t h e s i s ：a p p l i c a t i o nr e s e a r c h 西妻料技太学 学位论文独创性说明 本人郑重声明：所呈交的学位论文是我个人在导师指导下进行的研究工作及 其取得研究成果。尽我所知，除了文中加以标注和致谢的地方外，论文中不包含 其他人或集体已经公开发表或撰写过的研究成果，也不包含为获得西安科技大学 或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中做了明确的说明并表示了谢意。 学位论文作者签名：枢甜)日期：3 0 0 、? , 6 、2 ) 学位论文作者签名：他钟) 日期： b 、2 ) 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期间 论文工作的知识产权单位属于西安科技大学。学校有权保留并向国家有关部门或 机构送交论文的复印件和电子版。本人允许论文被查阅和借阅。学校可以将本学 位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存和汇编本学位论文。同时本人保证，毕业后结合学位论文研究课 题再撰写的文章一律注明作者单位为西安科技大学。 保密论文待解密后适用本声明。 学位论文作者签名：弛 指导教师签名：巷习 矗，司年多月；p 日 1 绪论 1 1 研究背景及意义 1 绪论 胜利油田“九五”以来就着手建立了较为完善的专业管理信息系统，全面覆盖了油 田经营管理各项业务，促使信息把握更加及时，管理效率显著提高。近几年油田主要致 力于系统间的联动，作为国内应用e r p ( e n m p r i s er e s o u r c ep l a n n i n g ) 系统规模最大的一 家企业，2 0 0 5 年胜利油田e r p 系统( 企业资源计划) 正式上线运行，信息系统由过去的“单 线应用”转变为“集成应用”，原有的管理模式发生了重大变革，建立了新的管理程序， 用标准、优化的流程解决了制度落实过程中存在的不足。由于随着计算机技术在胜利油 田的广泛应用，积累了大量的生产信息数据，并且油田开发和生产科研土作中的大量信 息已经实现网上传输。在传输数据的过程中，由于各种原因，不可避免地会出现一些错 误数据，从而影响到最终的结果而掩盖了正确的生产信息。 根据对油田生产情况的具体分析，可以将生产数据的错误类型分为以下三类： ( 1 ) 不符合原始界限( 该界限用户己给出) 时，有以下几种可能的原因： 数据在输入和存储过程中计算机产生的错误： 人工输入数据时，以欺诈为目的对数据的恶意修改。 上述情况，不符合用户所给出的最大范围，表明该数据是完全错误的，需要监控人 员直接对其进行处理。 ( 数据变化过大，原因如下： 数据在输入和存储过程中计算机的错误； 人工输入数据时，以欺诈为目的对数据的恶意修改； 在生产过程中，人为的影响( 例如油井作业、维修时，己停产) 。 ( 3 ) 不符合数据的大体趋势时，原因同( 2 ) 。 所以迫切需要一种能及时检测例外数据的方法来提高数据质量，在数据挖掘领域此 问题归结为例外数据挖掘问题。针对胜利油田数据库所积累的大量数据，更加需要一种 能高效进行例外数据挖掘的方法，并且该方法应具有透明性和可信度高的特点。 为了使发现知识的过程和结果易于理解和在发现知识过程中进行人机交互，要发展 发现知识的可视化方法。为了了解数据之间的相互关系及发展趋势，人们可以求助于可 视化技术。可视化不仅用图像来显示多维的非空间数据，使用户加深对数据含义的理解； 而且用形象直观的图像来指引检索过程，加快检索速度；在检索结果的显示上，也可以使 用可视化的手段或方法。可视化一直是计算机领域的研究热点，随着数据挖掘应用的发 展，人们对数据挖掘的可视化要求越来越高，数据挖掘可视化是目前数据挖掘研究的一 西安科技大学硕士学位论文 个重要方面。数据挖掘可视化方法目的就是要很好利用了人类的这种对于可视化形式下 模型和结构的获取能力，并且对这个结果进行分析解释。数据挖掘可视化己经证明在探 索性数据分析中有很大的价值，同时在处理大型数据库中也有很好的潜力。对于分析人 员来说，将数据挖掘整个过程进行可视化具有非常高的价值和重要性。将抽象的信息以 一种简明的形式呈现出来，从而给用户一个关于分析结果总体情况的概念。这样，也可 以给分析人员更多的自信以指导下一步的工作。通过将数据挖掘过程用可视化方式呈现 出来，从而帮助分析人员以一种形象、简明的方式掌握知识萃取和决策分析的过程，并 让他们充分的融入其中。将可视化技术与数据挖掘技术两者结合起来，进行可视化的数 据挖掘，可以大大地提高数据挖掘的效率，也可以得到更多更有价值的结果。数据挖掘 可视化的目的是使用户能够交互地浏览数据、挖掘过程等，当所要识别的不规则事物是 一系列图形而不是数字表格时，人的识别的速度是最快的。 可视化数据挖掘用数据或知识可视化技术从大的数据集中发现隐含的和有用的知 识。人们的视觉系统是由眼睛和人脑控制的，后者可看作一个强有力且高度并行的处理 和推理引擎，它带有一个大的知识库。可视化数据挖掘把这些强大的组件有效地组合起 来，使它成为一个吸引人的有效的工具，用来对数据的属性，模式，簇，孤立点进行综 合分析。可视化数据挖掘可看作是由数据可视化和数据挖掘两个学科融合而成的。它和 计算机图形，多媒体系统，人机接口，模式识别，高性能处理都紧密相关。总之，数据 可视化和数据挖掘可以从以下方面进行融合： ( 1 ) 数据可视化 数据库和数据仓库中的数据可看作具有不同的粒度或不同的抽象级别，也可以看作 是有不同属性和维组合起来的。数据能用多种可视化方式进行描述，比如：盒状图，三 维立方体，数据分布图表，曲线，平面，连结图等。可视化显示能把数据库中数据特性 的总体印象提供给用户 ( 2 ) 数据挖掘结果可视化 数据挖掘结果可视化指将数据挖掘后得到的知识和结果用可视化的形式描述出来。 这些形式包括分散划分( s c a t t e rp l o t s ) 和盒状图( 通过描述性的数据挖掘) ，以及决策树，关 联规则，簇，孤立点，一般规则等。 ( 3 ) 数据挖掘过程可视化 这种可视化用可视化形式描述各种挖掘过程，从中用户可以看出数据是从哪个数据 库或数据仓库中抽取出来的，怎样抽取的以及怎样清洗，集成，预处理和挖掘的。而且， 可以看出数据挖掘选用的方法，结果存储的地方及显示方式。 ( 4 ) 交互式的可视化数据挖掘 交互式的可视化数据挖掘在数据挖掘过程中使用了可视化工具，它用来帮助用户做 出明智的数据挖掘决策。例如，一系列属性的数据分布可以用彩色扇区或列( 取决于整 2 1 绪论 个空间是使用一个圆形描述还是使用列的集合描述) 来表示，这种表示方式可以帮助用 户决定哪个扇区作为分类首先被选中，哪个地方是最好扇区分割点。 可视化例外数据挖掘在理解数据奇异，数据检测，目前人们还需在可视化手段，可 视化结果和用户间的交互技术方面作进一步研究。在数据挖掘中使用可视化技术可以起 到以下作用：通过提供数据和知识的可视化，可以利用人类的模式识别能力评估和提供 挖掘出的结果模式的有效性：利用可视化技术建立用户与数据挖掘系统交互的良好沟通 通道，使用户能够使用自己丰富的行业知识来规整、约束挖掘过程，改善挖掘结果；提 供对挖掘结果的可视化显示，使用户对结果模式能够有深刻直观的理解。从而打破传统 挖掘算法的黑盒子模式，使用户对挖掘系统的信赖程度大大提高。 可视化数据挖掘可以应用在对于数据挖掘划分的所有三个阶段上：假设产生，挖掘， 结果表示。可视化数据挖掘的目的是提供一个可视化和数据挖掘的融合环境，以提高整 个数据挖掘的有效性，由于这个融合的工作非常新，所以很少有工作涵盖了所有的部分。 从数据挖掘的整个过程来看，可视化技术应用于数据挖掘主要有以下几个方面，如图1 1 所示； ( 1 ) 作为观察“数据山”的第一步，应用于数据预处理阶段。以图形方式提供一个 数据的可视印象，给用户一个大体直观感觉，帮助用户确定从何处着手进行挖掘。如下 图( a ) 所示。 ( 2 ) 作为直接进行数据挖掘的一种方式，应用于数据挖掘实施阶段，允许最终用户 借助人脑的探索分析功能寻找发现模式。当人脑可以对显示的图形实时做出判断时，这 种方式较使用计算机的自动数据挖掘技术要有效得多。如下图( b ) 所示。 ( 3 ) 作为显示挖掘结果和预测模型得一种方式，应用于数据挖掘的最后阶段，使最 终用户能够更好地理解挖掘出的结果模式。如下图( c ) 所示。 西安科技大学硕士学位论文 ( a ) 预先的可视化( b ) 中间的可视化( c ) 最后的可视化 图1 1 可视化技术应用在数据挖掘中的不同阶段 由于不同的需求必须采用不同的数据可视化技术，可视化必须渗透到数据挖掘和知 识发现的每一个步骤：从数据选择，数据预处理、数据挖掘到分析评估阶段，使用户看 到数据处理的全过程、监测并控制数据分析过程。因为在数据选择中对被分析的原始数 据的可视化显示有助于对合适的模型表达的确定：在数据预处理、数据挖掘过程中，展 现处理过程的可视化有助于理解所采用的方法并发现方法的不足之处：在知识的表达、 解释和评价时可视化有助于理解所获得的知识并检验知识的真伪和实用性。用直观图形 将信息模式、数据的关联或趋势呈现给决策者，使用户能交互式地分析数据关系。可视 化技术将人的观察力和智能融合入知识发现系统，可以提高用户对数据的理解，能极大 地改善系统挖掘速度和深度，从而增加提取新的、有用的知识的可能性。 随着胜利油田生产数据库的快速发展，由于数据保密，市场竞争，以及有限的网络 带宽，无法将分布式数据库中的数据统一存放、集中处理。这就使得数据挖掘系统需要 具有分布式挖掘的能力，同时也需要我们根据分布式数据挖掘的特点给出新的任务分配 模型以及分布式例外数据挖掘算法。 所以，在现实数据库中检测例外数据采用具有分布式能力的交互式可视化的数据挖 掘的方法就成为一种的趋势。目前，这样的研究正得到越来越多的重视。 1 2 国内外的研究动态及发展趋势 可视化技术的最早提出源于科学计算可视化( v i s u a l i z a t i o ni ns c i e n t i f i cc o m p u t i n g ， l 绪论 简称v i s c ) 的提出。它是发达国家在二十世纪8 0 年代后期提出并发展起来的一个新的 研究领域。它正式出现于1 9 8 7 年2 月美国国家科学基金会召开的一个研讨会上。将计 算机进行的大规模科学( 工程) 计算结果及其产生的庞大而令人一时难以理解的数据信息 转换成计算机图形、图像信息，加以静态或动态显示，从而得到有关计算结果的直观整 体概念，以便及时和正确地理解、把握科学工程计算中的各种现象和结果。从1 9 9 0 年 起，美国i e e e 计算机学会计算机图形学技术委员会开始一年一度地举办可视化国际学 术会议，这标志着“科学计算可视化”作为一个学科已经成熟，它的应用遍及所有应用 计算机从事计算的科学和工程学科，并获得巨大效益。 所谓“科学计算可视化”，就是应用计算机图形学和图像处理技术，将科学计算过 程中产生的数据及结果，转换为人们容易理解的图形图像格式，在屏幕上显示出来科学 计算可视化把科学计算过程中的数据及结果转变成人的视觉可以感受到的计算机图像， 这些图像可以将大量的抽象信息有机的组织在一起，并形象生动地显示数据所表示的内 容及其之间的关系，从而使许多抽象的、难于理解的原理和规律变得直观简单，许多繁 杂而枯燥的数据变得生动有趣。 实现科学计算可视化具有多方面重要意义。它可以大大加快数据的处理速度，使目 前每日每时都在产生的庞大数据得到有效地利用；它可以在人与数据、人与人之间实现 图像通信，从而使人们能够观察到在传统的科学计算中观察不到的现象；它还可以实现 对计算过程的引导和控制，通过交互手段改变计算所依据的条件，并观察其影响。在医 学上由核磁共振、c t 扫描等设备产生的人体器官数据，可以通过三维重建生成三维真 实图像，使医生对病变部位的大小，位置，不仅有定性的认识，而且有定量的认识；在 天文学中，绘制整个宇宙的三维地图，可以更好地理解星系的起源、演变和内部结构， 帮助人们了解宇宙更深层的奥秘；利用可视化技术对污染的传播和积累、全球臭氧的分 布、建筑物与周围气流、大面积水域污染等问题进行模拟、实验，分析产生的后果，就 可以为人类在环境生态学方面提供切实可行的预防措施：将可视化技术应用在地质勘探 中，利用自然的地震波或人工爆破产生的声波在不同地质构造层中的传播速度和衰减程 度的不同特点，利用反演变换重构表示地质结构的体数据，以帮助寻找新的矿产，并确 保己发现矿产的最佳状态i 取得良好的经济效益。 总之，可视化技术可以极大地提高科学研究的速度和质量，实现科学计算工具和环 境的进一步现代化，从而使科学研究工作的面貌发生根本性变化。我们也可以从中看出， 可视化技术具有以下三个主要特点： ( 1 ) 交互式的环境：用户可以方便的以交互式方式管理和开发数据。 ( 2 ) 多维的属性：用户可以看到表示对象或事件的数据的多个属性和变量，而数据 可以按其每一维的值，将其分类、排序、组合和显示。 ( 3 ) 的可视性：数据可以用图像、曲线、二维图形、三维体和动画来表示，并可以 西安科技大学硕士学位论文 对其模式和相互关系进行可视化分析。 国内对数据挖掘的研究稍晚。1 9 9 3 年国家自然科学基金开始对数据挖掘研究进行支 持，1 9 9 9 年4 月即在北京召开第三届亚太地区k d d 国际会议( p a k d d 9 9 ) 。目前国内许 多高校和科研单位在充实数据挖掘的基础理论和应用研究，如北京系统工程研究所对模 糊方法在数据挖掘中的应用研究、北京大学对数据立方体的研究、华中理工大学、复旦 大学、浙江大学等对关联规则的研究等。西安交通大学已知的有机械学院、电信学院、 工程学院和管理学院在从不同角度对数据挖掘进行研究。 近年来，例外检测作为数据挖掘的一个分支，正受到越来越多国内专家的关注和研 究【l 一5 1 。例外( o u t l i e r ) 在部分中文学术文献中还被称为“离群”、“异常”、“孤立点”等。例 外挖掘可一般性地描述为：采用某种数学方法从给定数据集中发现孤立的或者或与多数 数据不一致的少数数据。例外数据既可能是由于测量噪声或者输入错误而造成的，也可 能是由于系统的内在特性变化而产生的。由于测量噪声或者输入错误而造成的例外数据 可统称为噪声，它会对数据的后续处理和使用带来困扰，例如数据库系统中错误的输入 数据等，因此需要将这些例外数据识别并剔除；由于系统的内在特性变化而产生的例外 数据则反映出系统的结构、参数等发生了变化，例如传感器故障而导致的数据例外，因 此及时检测这些例外数据可以及时发现系统的故障。例外挖掘又称为例外检测、例外发 现等。例外挖掘在电信和金融领域的欺诈检测，信息和网络安全以及几点系统故障诊断 中都有惯犯的潜在应用价值。因此，目前例外挖掘已成为数据挖掘领域的研究热点之一 i l l 。 例外挖掘算法大致可以分为五类：基于分布的方法；基于深度的方法【l , 2 1 ；基于聚类 的方法【3 弓l ；基于距离的方法 6 4 1 和基于密度的方法i 4 1 。基于分布和基于深度的方法主 要发展于统计学领域。基于分布的方法假设数据库的分布己知，根据分布对数据库中的 每个对象进行“不一致”测试，如果该对象与分布不符合，那么就认为是例外。但是实 际上一般数据库的分布是未知的，往往也很难通过估计得到；基于深度的方法只适合于 二维或三维数据，对于四维以上的数据集就显得效率低下1 1 , 2 1 ；基于聚类的方法间接或者 直接利用已有的聚类算法，但是聚类算法显得不是那么高效，因为它一般不对例外处理 作特别优化，而且这类算法通常没有一个形式化的易于被用户接受的例外定义。国内复 旦大学的一些学者在离群点发现技术上做了大量工作0 6 , 1 7 1 ，如提出基于估计的高效子空 间局部离群点发现s l o t ( s u b s p a e el o c a lo u t l i e rt e s t ) ，子空间离群点是指数据集在某些 维上的投影上的特殊的点，是对数据集的纵向分割。这个算法能够在预先去除大量不可 能成为离群点的对象前提下找到在所有子空间中的所有局部离群点，大大减少了计算 量。 我国有关数据挖掘例外检测问题的研究正处于初步发展的阶段。目前，关于例外检 测的国内论文也日益增多，研究的问题也逐渐深入。在对面向高维的方法中，魏藜等提 6 1 绪论 出了一种基于超图模型的例外定义【瑚，这一定义既体现了“局部”的概念，又能很好地解 释例外的含义，同时给出了基于超图的例外检测算法h o t ( h y p e rg r a p h - b a s e do u t l i e r t e s t ) ，通过计算每个点的支持度、隶属度和规模偏差来检测例外。该算法既能处理数值 属性，又能处理分类属性，能有效发现高维空间数据中的例外。由郑斌祥等就是针对基 于时间序列数据的例外数据挖掘【1 9 1 ，在文献 1 9 l 中首先通过对时序数据进行离散傅立叶 变换将其从时域空间变换到频域空间，将时序数据映射为多维空间的点，在此基础上， 提出进行例外数据挖掘算法。李存华等提出面向大规模数据集的高效离群点检测g r i d o f 算法 2 0 1 ，通过对数据集中离群点分布特征的分析，在数据空间网格划分的基础上， 研究数据超方各层次上的密度近似计算与稠密数据主体滤出策略，给出通过简单的修正 近似计算取代繁复的点对点密度函数值计算的方法。姜灵敏提出了基于相似系数和检测 孤立点的聚类算法，向多目标决策和综合评价中的例外点集检测迈进了一步【2 l 】。 但是，纵观这些例外点检测的方法，有的方法只能对单一的数据库，有的精度不高， 有的算法时间复杂度过高，有的不能满足快速有效检测数据库中例外数据的需求。所以， 能够解决现实数据库的例外检测的问题在数据挖掘领域中迫在眉睫。使用分布式例外挖 掘就是一种方法。目前，国内一些专家也在研究分布式数据挖掘的问题，文献 2 2 1 就对 分布式数据挖掘计算过程( d i s t r i b u t i v ed a t a m i n i n gc a l c u l a t i n gp r o t c e 8 8 ，d d c p ) 算法进行 了研究，提出了一种关联规则挖掘大项集生成的并行和分布式处理的计算框架的算法， 该算法以大规模事务数据库为基础，将数据有效的分片后作分布或者并行处理，通过结 点之间的通信降低了节点间传输的数据量。文献 2 3 1 提出了一种基于软构件的分布式计 算环境c o r b a 的新型分布式数据挖掘体系，其突出特点是易于扩充性，良好的复用性 和安全性，并且提出了新的知识评价结构。文献 2 4 1 提出了一个基于a g e n t 的分布式数 据挖掘形式模型，并结合数据挖掘方法和知识集成技术对该模型进行了深入地分析和讨 论。所以，专家们也认识到解决现实数据库的例外挖掘问题采用分布式数据挖掘是必然 的趋势。虽然可视化对数据挖掘交互性有着更好的推进作用，但是国内对数据挖掘的可 视化研究目前还是一个空白，所以需要对其进行更深的研究。 近年来，国外基于数据挖掘思想的例外点检测研究获得了一系列重要的成果，诸多 行之有效的检测算法在广泛的领域里获得了应用。其中较具有代表性的工作有基于深度 的算法d e e p l o c ”，k n o r r 等人提出的基于距离的算法f i n d a l l o u t s d l 2 卯，y u 等人的基 于小波变换方法的算法f i n d o m 【5 】，b r e u n i g 等提出的带离群度的例外点检测算法l o f t l o l 和j o s h i 等的基于机器学习方法的二阶段规则推倒算法n p r u l e 2 6 垮。j i a n gmf 4 1 ，p o r t n o y l 2 7 1 ，h e z y 唧分别提出了几种以聚类为基础的例外检测方法，这些方法有两个共同的 特点：( 1 ) 先采用特殊的聚类算法处理输入数据而得到聚类，再在聚类的基础上来检测 例外。( 2 ) 只需要扫描数据库若干次，效率较高，适用于大规模数据库。但文献 4 】只能 应用于纯数值属性的数据库，也不能很好地处理分类属性，相反t 3 1 h 能直接应用于纯 7 西安科技大学硕士学位论文 分类属性的数据库。另外，对于参数的选择需要人工干预，难以自动处理。基于密度 和基于聚类的方法考虑数据到了数据的局部特性，可以更准确地查找例外，这些方法 大多利用了距离或相似度这个基本概念，并通过对象的特定“例外因子”来度量对象的 例外程度。c h a u d h a r y 等人提出使用k _ d 树的方法田l ，该方法不需要架设任何可能的模 型并且l 树与对象和维数的个数呈线性变化。g h o t i n g 等人提出l o a d e d 算法例，其 是一个可调的算法。能检测连续和无条件的属性。s a r a w a g is 等 3 0 l 提出了一种从数据中 自动发现例外的数据立方探查方法，该方法利用数据立方来识别大面积多维数据库中 的例外区域。这种方法是一种发现驱动的启发式方法，可利用指示数据意外的计算结果 来帮助用户在所有累计层次进行数据分析。如果根据统计模型，立方体中一个单元的值 与所期望值明显不同，那么就认为该单元就是一个例外单元。根据标示出来的例外，数 据分析人员就可以按照数据的层次结构逐层向下钻取，找出数据例外发生的原因。 在空间复杂度上，由于f i n d a l l o u t s d ，n p - r u l e ，f i n d o u t 和l o f 等算法没有充分考 虑例外点检测问题的特点，在内存有限的条件下，缺乏对构成大规模数据库主体的属于 常规聚类模式的数据的预过滤处理而导致频繁的数据交换和难以容忍的空间复杂度。如 基于内外存交换的算法f i n d a l l o u t s d ，尽管k n o r r 等声称其具有相对于数据量的线性时 间复杂度，然而对于大规模数据集却需要3 次整体内外存交换。其次，上述算法一般均 具有o ( n l o g n ) 以上的时间复杂度，在处理包含海量数据样本的数据集时显然无法获得 令人满意的响应速度。另外，数据集的高维性常造成算法失效，如d e e p l o c 和f i n d o u t 仅适用于处理4 位以下的数据集。 因而，从速度、精度、准确度和时间空间复杂度等方面，上述检测算法在处理大规 模数据库时均存在着自身的弱点。 1 9 9 6 年，k a r g u p t a 和m m z a 0 0 u 等人提出了使用软件代理的并行，分布式数据挖掘 系统( p a d m a ) 3 q ，已经开发的软件代理能够远程访问数据和分析数据，以及使用w e b 界 面交互式数据可视化，还可以检测和发现非结构化文本文档中的模式。文献【3 2 】提出了 f d m ( f a s td i s t r i b u t e dm i n i n go fa s s o c i a t i o nr u l e s ) 算法以解决分布式环境中的关联规则挖 掘问题，该方法利用在局部频繁项目集与全局频繁项目集之间存在的性质来减少需要传 输的信息量，并利用散列方法指定局部频繁项目集的轮询站点缩小了所需的通信次数， 从而快速、有效地生成全局频繁项目集。文献【3 3 】提出了c d m ( c o l l e c t i v ed a t am i n i n g ) 框 架以解决分布式环境中的分类学习问题，该文指出对分布式环境中的站点直接应用现有 机器学习和统计算法生成的局部模型可能是不正确的，与全局模型不一致。该方法使用 正交基函数进行局部分析，再将所有局部生成的正交基函数组合，形成全局数据模型。 g r o s s m a n 等人提出了一种称为p d s ( p h o t o n i cd a t as e r v i c c s ) 的集成框架p 硼，在该框架中首 次集成了支持远程数据分析和分布式数据挖掘的数据服务，设计用于在高性能网络上进 行高效数据传输的网络协议以及设计用于光纤网络的链路服务，该框架可用于进行 8 i 绪论 g - i g a b y t e 大数据量的分布式数据挖掘。 国外主要针对时间序列数据集将可视化运用到数据挖掘当中。在文献1 3 5 1 中提出了 一个信息可视化的分类和基于数据类型的可视化挖掘技术。j a r k e 等人在时间序列的研 究中运用了可视化技术，提出运用聚类的方法找到相似的每天的数据模式，然后用日历 对应每一天的图表形式可视化平均的模式，这种方法可快速得到标准和例外模式冈。最 近对于这些数据集的交互式可视化的研究重点放在了支持多尺度和周期性的视图上。作 为一种早期的可视化技术，递归模式对按层次分解成细粒度时间周期( 年、月、星期等) 的数据提供了密度显示吲。螺旋形可视化使用了一种圆形m e 癯a p h o r 来显示一些数据集 的周期性口”，它是通过视觉检查来识别不同模式的。作为主要的可视化实现方法，这些 系统因为只适用于特定涉及时间变化模式的询问而使使用受到限制。我们也迫切需要一 种能够适应现实数据库的可视化方法。 综合国内外现状也可以看到现存数据挖掘例外点检测的方法对单一的数据库算法 的精度和时间复杂度都不尽如人意，也不能满足快速有效检测数据库中例外数据的需 求。所以，能够解决大规模数据库的例外检测的问题在数据挖掘领域中迫在眉睫，进行 分布式例外挖掘是解决此问题的一个途径。国内外在一般数据库的可视化例外数据挖掘 方面的研究还是一个空白，所以将可视化技术运用在数据挖掘当中将更具有广泛的前 景，也是未来发展的一个趋势。 1 3 本文研究内容及取得成果 本文的研究课题在西安科技大学研究基金资助下，主要针对胜利油田生产数据库高 效例外数据挖掘问题，在综合研究各种可视化例外数据挖掘方法以及胜利油田生产数据 库特点的基础上，提出了一种新颖的交互式可视化例外数据挖掘方法，该方法提高了例 外数据挖掘的效率与精度，并将其应用到胜利油田生产数据库中验证了该方法的有效 性，为后续工作提供了技术支撑和理论基础。 主要研究内容和取得的成果如下： ( 1 ) 通过研究数据挖掘中的各种可视化方法，提出了一种新颖的交互式可视化例外 数据挖掘方法，其思路为：先将数据库表中的数值属性值转化为相应字符，再给各字符 赋以相应颜色值，每次可视化显示出4 个连续属性的模式分布情况，根据可视化图形所 识别出的频繁模式候选集以及例外模式定义，计算每条记录的例外支持度，由所设定阈 值即可得到例外数据。将该方法与经典例外检测算法l o f 和q r n o f 算法进行了实验对 比，数据采用真实的胜利油田生产数据集。结果显示交互式可视化例外数据挖掘方法在 计算速度以及命中例外数据的精度上都优于l o f 及q r n o f ，速度分别提高了1 6 倍和5 倍，命中精度分别提高了2 7 和4 0 。该方法在着色方面，对p b c 算法进行了改进， 更加适应人的感知，使人们更易于对可视化图形的识别与分析。在研究数值属性离散化 9 西安科技大学硕士学位论文 及概念分层的基础上，作者针对混沌时间序列就是首先使用了概念分层方法对时间序列 进行分割，然后再预测趋势的，并且这篇文章中在西安交通大学学报( 英文版) 中发表。 ( 2 ) 针对胜利油田生产数据库的分布式特点，在研究分布式数据挖掘方法的基础上， 给出了适合胜利油田生产数据库的分布式可视化例外数据挖掘任务分配模型和具体算 法，运用了s o c k e t 通信机制实现客户端与服务器之间的交互。为胜利油田生产数据库的 分布式可视化例外数据挖掘奠定了基础。 ( 3 ) 在上述两项研究工作的基础上，将所提出的交互式可视化例外数据挖掘方法应 用到胜利油田生产数据库中验证其有效性，并设计实现针对胜利油田生产数据库的交互 式可视化例外数据挖掘的原型软件系统。该系统共有3 个模块构成：交互式可视化模块、 分布式可视化模块和例外检测模块。该系统实现了高效地检测出胜利油田生产数据库数 据中的例外数据同时还可以实现资源共享，提高了资源利用率，也能使数据挖掘过程透 明化，节省了人力。该软件同样也能适用于大规模数据库的例外数据检测，具有一定的 通用性，为后续工作打