（计算机应用技术专业论文）基于兴趣度的离群点挖掘技术研究.pdf

基于兴趣度的离群点挖掘技术研究 摘要 现代企业在其信息化的过程中积累了越来越多的数据，对于一些企业应用，异常数据的挖掘比 常规模式的挖掘更有应用价值。对于这类数据挖掘研究的需求日益明显增加，无论在国内还是国外 都形成了广阔的研究领域，该项技术越来越多的投入到现今社会的诸多应用中，发挥着其不可被替 代的作用。例如企业管理风险的预测分析，网络入侵检测等。这些技术都需要对于异常情况快速而 敏感的检测，这些都为离群点的挖掘提供了潜在的应用背景。 在目前的数据挖掘研究中，兴趣规则的研究大多基于关联规则和强关联规则的考虑，孤立点的 研究也只是基于单库，适应高维的孤立点检测的有效算法依然在研究中，基于这些因素，本文提出 了不同于以往研究的一种兴趣度新定义新奇度，即把兴趣度和离群点结合起来，注重具有此类 特征的离群点的挖掘。在现有的l o f 算法和g r i d l o f 算法的基础上，把数据库看作数据集，用孤 立点概念代替新奇数据的概念，提出改进后的基于兴趣度的挖掘新奇数据的算法g p o d ( a g r i d b a s e dp r e p r o c e s s i n go u t l i e rd e t e c t i o na l g o r i t h m ) ，使其能更有效、快速的挖掘出离群点，g p o d 算法在高维数据集的挖掘中也具有一定的理论价值。在适当的环境f 可以迸一步引申为兴趣规则， 并推广应用丁多库环境中，挖掘出具有实际意义的有用规则，进而为企业决策者提供有用的信息。 本文在介绍相关的概念及定义的基础上，详细讨论了兴趣规则的具体定义，具体意义及应用。 还重点介绍挖掘算法采用的技术孤立点检测和聚类，阐述了基于兴趣度的离群点挖掘方法以及 如何由席间规则得出多库下的规则；此外，本文还具体介绍了g p o d 算法在多库下实行的步骤，给 山主要的算法代码，并给出算法的实现部分和实验结果，验证算法的先进性，分析算法的性能，给 出其优点和不足，与算法l o f 和g r i d l o f 的一些比较。最后做出总结，指出本课题进一步研究和 有待完善的内容以及下一步研究t 作的主要方向。 关键词：离群点，兴趣度，新奇度，局部偏离因素，单元网格，多库 基于兴趣度的离群点挖掘技术研究 a b s t r a c t t o d a y , m o r ea n dm o r ed a t aw e r ea c c u m u l a t e dl nc o m p a n i e sf o rs o m eo f t h e m ，e x c e p t i o n a ld a t aa r em o r e v a l u a b l et h a nn o r m a lo n e s t h er e q u i r e m e n to f m i n i n gd a t ao fs u c ht y p ei n c r e a s e se v e r yy e a ri nb o t ho u r c o a n t t ya n df o r e i g no n e s w i d er a n g e so fs t u d ya r e aw e r ef o r m e d t e c h n o l o g ya b o u tt h ea r e ah a v eb e e n p u ti n t om a n ya p p l i c a t i o n si no u rm o d e ms o c i e t ya n da c t e da sau s e f u lt 0 0 1 f o re x a m p l e ，t h ea n a l y s i so f p r e d i c t i o no f r i s km a n a g e m e n to fe n t e r p r i s e ，n e t w o r ki n t r u s i o nd e t e c t i o na n ds oo n t h i st e c h n o l o g yn e e d d e t e c te x c e p t i o n a lc a s es e n s i t i v e l ya n ds p e e d i l ya l lt h e s ea r eb a c k g r o u n d so f m i n i n g o u t l i e r s i nr e c e n ts t u d yo fd a t am i n i n g ，m o s ts t u d yo fi n t e r e s t i n gr u l e sb a s e do na s s o c i a t i o n a lr u l e so rs t r o n g a s s o c i a t i o n a lr u l e s t h ew o r ko fo u t l i e rd e t e c t i o nb a s e do ns i n g l ed a t a s e t f o rt h e s er e a s o n s ，t h i sp a p e r b r o u g h to u tan e wd e f i n i t i o na b o u ti n t e r e s t i n g n e s st h a tn a m e dp e c u l i a r i t y c o m b i n i n gt h ec o n c e p t i o no f p e c u l i a r i t ya n do u t l i e r s ，t h ep a p e r f o c u so nm i n i n go u t l i e r si nd a t a b a s e an e wa d v a n c e da l g o r i t h mg p o d w e r eb r o u g h to u tb a s e do ng r i d l o fa n dl o f , w h i c hc o u l dm i n eo u t l i e r so u tm o r ee f f i c i e n t l y i tc a na l s o e x p a n d t ob eu s e di nm u l t i d a t a b a s e ，w h i c hc a np r o v i d em o r eu s e f u li n f o r m a t i o n t ou s e r s i nt h eb e g i n n i n g ，t h ep a p e ri n t r o d u c e dc o n c e p t i o n sa n dd e f i n i t i o n sr e l a t i o nt ot h ec o n t e n to fs t u d y t h e n i t g a v et h ed e f i n i t i o na n da p p l i c a t i o n so fi n t e r e s t i n g n e s si nd e t a i l t h et e c h n o l o g yo f o u t l i e rd e t e c t i o na n d c l u s t e r i n gw e r ei m p o r t a n tp a r to f t h ei s s u e 。a f t e rt h i s ，t h ep r o c e s so fm i n i n go u t l i e r sb yg p o d a n dh o wt o g e tr u l e sa m o n g d a t a b a s e sw e r ed e s c r i b e d as e r i e se x p e r i m e n t sw e r ee x e c u t e dt ot e s tt h em e r i t so fg p o d a n di t s i m p r o v e m e n t s f i n a l l y , t h es u m m a r y o ft h i sp a p e rw a sg i v e ni n c l u d i n gm o r ew o r kw es h o u l dd o a b o u tt h es t u d ya n dt h em a i nd i r e c t i o no f n e x tt a s k k e yw o r d s ：o u t l i e r s ，i n t e r e s t i n g n e s s ，p e c u l i a r i t y , l o c a lo u t l i e r f a c t o r , c e l l ，m u l t i - d a t a b a s e i l 邵44 6 7 6 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材刳。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 研究生签名：! 盆! 盈日期：塑生：g研究生签名：垡! 日期：塑生：g 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 研究生签名：余党 铈签名：生茎笪| = i 期：2 口。孑扩 基于兴趣度的离群点挖掘技术研究 1 1 数据挖掘技术 第一章绪论 计算机技术的迅猛发展以及网络的普及，使人们有了更多的机会和便捷的方法与外界进行信息 交流。可是，数据大量的涌入，增加了我们获取有用信息的难度。如何从大量的数据中获得有价值 的信息，采用传统的数据库技术已显得无能为力。数据的迅速增加与数据韵分析处理方法滞焉的矛 盾越米越火，人们希望能够在对已有的大量数据分析的基础上进行科学研究、商业决策或企业管理， 数据挖掘正是在这一背景下诞生的。实践证明，数据挖掘己在多个领域里取得了成效。 数据挖掘( d m ，d a t am i n i n g ) 是指从数据集中识剐出有效冉勺、新颖的、潜在有塌的以及最终可 理解的模式、并将该信息运用于制定重要管理决策的高级处理过稳。一般而言，数据挖掘技术从理 论和技术上继承了知识发现( k d d ，k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 领域的成果，同时又具有其 独特的内涵。数据挖掘技术更着眼于设计高效的算法以达到从巨量数据中发现规则知识的目的。相 对于其他的数据分析工具( 如查询、o l a p 等) 而言，数据挖掘技术希望在无人工干预下自动获取 令人感兴趣的知识。随着数据最的增大，对模式精细度、准确度要求的增高导致问题复杂性的增大， 而数据挖掘! j i j 可以提供多种技术和方法解决这样的问题1 1 9 ，包括： ( 1 ) 多种模式多种类别模式的结合使用有助于发现有用的模式，降低问题的复杂性。例如，首 先刚聚类的方法把数据分组，然后在各个分组上挖掘预测性的模式，将会比单纯在整个数据集上进 行揉作更有效、准确度更高。 ( 2 ) 多种算法很多模式，特别是与分类有关的模式，可以由不同的算法来实现，各有各的优缺 点，适用于不同的需求和环境。 ( 3 ) 验证方法在评估模式时。有多种可能的验证方法。比较成熟的有n 层交义验证或 b o o t s t r a p p i n g 等，可以控制以达到最大的准确度。 ( 4 ) 数据选择和转换模式通常被大量的数据项隐藏，有些数据是冗余的，有些数据更是与挖掘 模式完全无关的。而这些势据项的存在会影响到有价值的模式的发现。数据挖掘系统的一个重要功 能就是能够处理数据复杂性，提供工具，选择正确的数据项和转换数据值。 ( 5 ) 可视化可视化工：具提供直观、简洁的机制表示大量的信息。这有勘于定位重要的数据，评 价模式的质量，从而减少建模的复杂性。 ( 6 ) 扩展性为了更有效的提高处理大量数据的效率，数据挖掘系统的扩展性十分重要。需要了 解的是：数据挖掘系统能否充分利用硬件资源；能否支持并行计算；当处理器的数量增加时算法 i 基于兴趣度的离群点挖掘技术研究 的计算规模是否相应增长。 因而，数据挖掘技术与统计学、数据库系统、模式识别、人工智能、可视化技术、数据分析等 学科和技术密切相关，只有综合运用这些技术，才能使数据挖掘研究深入的开展。 1 2 问题的提出 1 2 1 数据存储技术的发展 科学技术的迅猛发展，导致信息量的目益增大同时也带动了数据库技术利网络技术的快速发 展，出现了计算机通信网络和分布式、联邦式、异构式的多库系统技术等形形色色的信息存储方式。 现今，各企事业单位都十分重视信息化建设，相继构建本单位的数据库应用系统和i n t r a n e t e x t r a n e t 环境，日积月累，各企事业单位均存储了大量的数据，且大多存放在代表主流的关系数据库中，这 样便构成了更为复杂多样的数据库系统。 由丁二数据挖掘可为决策者提供重要并有价值的信息和知识，产生不可估量的收益。所以其市场 需求日益增长。如何在大龟的分散的多库中挖掘出有用的决策知识或规则具有重要的现实意义。由 此可见，数据量的日益庞大，数据存储结构的复杂和存储方式的更新都要求新的更能适应当前信息 环境的数据挖掘技术的出现。 1 2 2 企业管理应用的需求 在技术迅猛发展的今天，一方面，由于信息量的增| 圭速度越来越快，企业中积累了越来越多的 数据，另一方面，网络技术的发展带动了企业和政府的信息化建设，更多的企业有了自己的i n t r a n e t 和网站，其数据库通常分布在异地下属公司或分支部门中。企业决策者和政府领导面对这些海量数 据库无所适从，他们需要从海量数据中高教地提取并发现隐含的、未知的、有潜在应用价值的模式 或规则，为企事业进行前摄的、基于知识的决策提供科学的依据，这也被称为存在于许多大型公司 中的数据库资源问题。 同时，有效的挖掘技术可以使公司合理运用现有的数据资源，做出增加利润的决策和管理方案。 这些都对技术挖掘的放用性提出了更高的要求。对于一些企业应用，异常数据的挖掘比常规模式的 挖掘更有应用价值。对于这类数据的挖搌研究的需求日赫明显增加，无论在国内还是国外都形成了 广阔的研究领域，该项技术的越来越多的投入到现今社会的诸多应用中，发挥着其不可被替代的作 用。例如犯罪的分析和侦查，网络入侵检测等。它们都需要对于异常情况快速而敏感的检测，这些 都为离群点的挖掘提供了潜在的应用背景。 2 基于兴趣度的离群点挖掘技术研究 1 2 3 兴趣规则研究的不足 1 9 8 9 年8 月在美国底特律召开的第1 1 届国际人工智能会议上首先山现k d d 这个术语，此后数 据挖掘研究领域异常活跃，挖掘技术的研究取得了丰硕的成果，也已研制出了许多数据挖掘的相关 产品，从理论研究走向了市场应用。 关联规则、分类规则和聚类分析是数据挖掘的主要内容。基于兴趣度的关联规则的采掘则是数 据库领域众多学者关注的热点研究问题之一。目前应用最为广泛的兴趣规则挖掘主要是针对单张表 进行的。在多库环境下，我们可以把它简化理解为多表的基本结构( 即一个数据库只含有一张表) 米处理。几年来已有许多致力于分布式数据库挖掘的算法，然而，兴趣规则的挖掘算法都是把兴趣 度作为进一步的筛选阀值的改进的a p r i o r i 算法，是传统的单库技术，也就是说，把所有的相关数据 集成一个大的数据集，然后在其上进行挖掘。其中存在三点不足： 在自底向上的搜索过程中将产生和传送大量的候选项目集，网络通讯代价高，算法效率低： 在逻辑同构的多库环境下挖掘规则，很少考虑数据库的相关性；一些重要的规则被忽略， 因而不能满足具体应用的需求； 在强关联规则的基础上进行筛选，忽略了出现较少的异常情况，而其中可能蕴含有用且用 户感兴趣的信息。比如说，在某些地方的超市，若当它们增加购进的商品x 和商品y 时， 则x ，y 的销售额都得到增长，而由于x ，y 数据量小，当这些数据一起并入成为一个大 的数据集后，这个规则由于所占比例太小而不可能被挖掘出来。 在最近的兴趣规则应用于多库的研究中，s h i c h a o z h a o 提山一个多库挖掘的新过程m d m ，把 大型的公司看作一个二层的结构组织，其每个分支有一个数据库，把数据库看作一个表，先把这些 数据库分类，在局部模式上挖掘具有较高频率和极少频率的规则，其中极少频率的规则则是通过离 群点来发现的兴趣规则，通过子公司对这些规则的支持程度来合成这些局部规则。但是这个方法的 过程中并没有明确的提出用户兴趣度的衡量，库问的规则合成也只是简单的考虑了一下各分布数据 库对丁规则的支持情况。 n i n gz h o n g 在 2 中提到了多库环境下新奇规则的研究，并对新奇度进行了定义，用主关键字 作为库间规则的连接依据来计算规则的关联度。其新奇度的定义公式如下： 定义11 ：设x = x 】，x 2 ，x 4 是一关系表中的某个属性数据集，x i 的新奇度用p e c u l i a r i t yf a c t o r 米表示，记为p f ( x ) ， p f ( x i ) = 扣瓦丽 j = l 其中( 崩，x j ) = lx i 一琦1 ，表示该属性两个值之间的概念距离，如果x 为数值型，其距离为数 3 基于兴趣度的离群点挖掘技术研究 值上的差的绝对值，如果属性为符号型，当背景知识存在时，其距离为概念上的距离，否则为1 。 通过这个定义计算单个属性的每个取值的偏离度，p f 值明显偏大属性值就是新奇数据，并咀此为依 据进一步得到库间的新奇规则。显然，这个测量距离的定义较为简单，是基于一维属性值的，而现 在的数据往往要从多维角度来考虑，对于多维数据集这种新奇度的测量是不够的，与基于距离的孤 立点检测方法类似，其弊端在后面介绍基于距离孤立点检测算法的章节中将有讨论。 1 2 4 未来离群点挖掘技术的挑战 我们所说的离群点即孤立点( o u t l i e r s ) ，离群点的挖掘也就是孤立点的检测技术。随着数据挖掘 技术的发展，孤立点的检测也面l 临着二个问题：首先是挖掘算法的有效性，如何有效的判定一个点 是孤立点仍然是我们的研究重点。要获取用户感兴趣的信息，我们就要先判定怎样的信息才有价值， 能有极大的可能性吸引顾客的注意力，对用户有所帮助，也就是孤立点的判定标准，这仍然是孤立 点检测算法需要得到改进的关键因素之一。 其次，我们要快速的把它找出来，数据的大量涌入，不仅增加了寻找有用数据的难度，也延长 了数据挖掘的时间，人们不可能耗费大量的时间来等待结果，即使是一个有决策价值的结果，用户 也可能因为不愿意以浪费时间的代价而拒绝使用这项技术。在千变万化的现实世界中，高科技的发 展使得社会的每一部分都在发生高速的变化，这就要求新研制出来的技术必须跟上新潮流的快速的 步伐。特别是在某些应用中，用户需要系统快速灵敏的对现实数据做出反应，从而进行更好的决策。 可行度低的算法会影响原本潜在的有用规则的提取。例如，一个股票投资商做一个投资决定时需要 了解投资对象的变化情况，山现的异常等等，如果这些反映不及时或错误，就有可能会导致投资失 败甚至破产。快速高效的离群点挖掘则是已经开展的一场新的技术挑战。 1 3 本文的研究目的及内容 综合前面的讨论，兴趣规则的研究大多基于关联规则和强关联规则的考虑，孤立点的研究也只 是基于单库，目前适应高维的孤立点检测成熟算法依然在研究中，本文考虑不同以往研究的兴趣度 定义新奇度( 也是兴趣度的一种) ，注重具有此类特征的离群点的挖掘。在现有的l o f 算法和 g r i d l o f 算法的基础上，把数据库看作数据集，用孤立点概念代替新奇数据的概念，提出改进后的 基于兴趣度的挖掘新奇数据的方法g p o d ( a g r i d b a s e d p r e p r o c e s s i n g o u t l i e r d e t e c t i o na l g o r i t h m ) ，使 其能更有效、快速的挖掘出离群点，在高维数据集的挖掘中具有较高的理论价值。并在适当的环境 下可以进一步引申为兴趣规则，且可以应用于多库环境中，挖掘出具有实际意义的有用信息，进而 为企业决策者提供有用的信息。 4 基于兴趣度的离群点挖掘技术研究 1 4 本文的基本框架 本文在绪论中讨论文章算法所要用到的具体概念及定义：接下来的第二章详细介绍兴趣规则的 具体定义本文兴趣度的具体意义及应用。第三章重点介绍挖掘算法采用的技术孤立点检测和 聚类，第四章阐述基于兴趣度的离群点挖掘方法以及如何由库间规则得出多库下的规则，第五章具 体介绍g p o d 算法在多库下实行的步骤，给出主要的算法代码，第六章则是算法的实现部分，给出 实验结果，验证算法的先进性，分析算法的性能，给出其优点和不足，与算法l o f 和g r i d l o f 的 一些比较。第七章做出总结，指出本课题的一些不足和有待完善的一些方面以及下一步研究工作的 大致方向。 基于兴趣度的离群点挖掘技术研究 2 1 兴趣规则 第二章数据挖掘中的兴趣度分析 很多d m 算法都是从大量的数据中挖掘关联规则。对于从数据中可挖掘出的大量的关联规则， 用户往往只对其中部分规则感兴趣。由此引出了多种进一步筛选规则的方法和各式各样的筏量标准， 但这些研究工作的目标是一致的，那就是挖掘出真正有用的规则。而衡量规则是否有用最终是取决 于用户的，如果用户愿意使用挖掘出来的规9 1 l ，则规则是有用的。只有用户感兴趣的规则用户才可 能使用它，所以，随着数据挖掘的发展，兴趣规m q 渐渐成为有用规则的代名词。可以说，所有数据 挖掘技术的研究都或多或少与“兴趣”有关，用户越感兴趣的规则越有用，越有挖掘和研究价值， 反之则反。因此，我们在进行数据挖掘方面的研究都必须首要考虑“兴趣”问题，对于兴趣规则的 概念应有清楚而详尽的认识。 此外，兴趣规则主导着兴趣度的研究，本文算法既然是基于兴趣度的研究，就要从兴趣规n t f 始，了解它的内在含义。 一般来说，兴趣规则应满足以下几点【7 1 ： 1 简洁性：规则应该是简单易懂，容易给出表达形式的。规则的总体简洁。用它的= 进位位数， 或属性数，或规则中出现的操作附属来定义。 2 确定性：每个发现的模式都应当有其有效性或“值得信赖性”的因素，通常用置信度来衡量。 3 实用性：一条规则的潜在的有用性是定义其兴趣度的一个重要因素，可以用支持度来评估。 4 。新颖性：用来标示只提供新信息或提高给定规则性能的模式。如一个数据异常。也可用丁删 除冗余模式。如果发现的规则被已在知识库中或导出的规则集中的另一规则所蕴含，则两个 规j i ! j 都要重新审查，以便去掉潜在的冗余。如已有的置信度用来检查冗余的规则。 通常情况下，从数据库中挖掘出来的规则分为三类；不正确的，无用的和用户真正感兴趣的： 不正确的规则是指规则本身存在着这样或那样的逻辑错误，是不能作为正确规则来使用的模式。 无用的规j l l j 指挖掘所得到的规则没有包含有用信息，是我们已经知道的，或普遍存在的规律等 等。 以上两类规则在我们挖掘关联规则基础上的兴趣规则时经常碰到。例如，“数学学得好的学生物 理学得差”就不是一条正确的规则。义比如，我们都知道大多数人喝咖啡需要加方糖，所以形如咖 啡的销售会促进方糖的销售的规则对用户来说没有太大的实用价值。 第三类蹦户真正感兴趣的规则是指崩户对新发现的规则感到惊讶这个规则超出预想。这样的 6 基于兴趣度的离群点挖掘技术研究 兴趣规则又分为两种：一种是频繁出现但用户没有发觉的。另一种是偶然出现的，出乎用户意料之 外的模式，符合这两种情况的规则都是我们挖掘的目标。后一种特征的兴趣度形式就是本文的离群 点挖掘基于的重点。 2 2 兴趣度的引入 兴趣度的研究是从关联规则的挖掘起步的，关联规则是当前数据挖掘研究的主要内容之一，是 指在数据库中采掘出具有这种形式的规则：由于某些事件的发生而引起另外一些事件的发生。它用 于确定数据集中不同领域或属- 胜之间的联系，找出可信的、有价值的多个域之间的依赖关系，在决 策支持系统、专家系统和智能信息系统等各个方面起着重要的作用。例如，在学生成绩数据库中， 可以发现“离散数学成绩为优的学生编译原理成绩也是优的可能性是6 6 ”；在超市销售记 录中，我们可以发现“购买鱼子酱的顾客又购买了伏特加酒的可能性是8 6 ”，这样，我们可以加 强离散数学课的教学，以此来提高编译原理课的教学成果；或者降低鱼子酱的价格来促进 伏特加酒的销售。 然而，关联规则也存在局限性。对于从数据中可挖掘出的大量的关联规j i ! ! j 用户往往只对其中 部分规则感兴趣。而现有的关联规则挖掘算法主要是考虑两个称作置信度和支持度的阀值，例如经 姐的a p r i o r i 算法和d h p 算法。最小支持度和最小置信度并不能确保所有挖掘山的关联规则都是用 户所感兴趣的，其中可能包含许多冗余、无意义的关联规则，而且支持度和置信度较高的关联规则 有可能是常识性的知识，这样数据挖掘就显得没有太大意义。自从a g r a w a l 等人于1 9 9 3 年首先提出 了采棚顾客交易数据库中项集间的关联问题，诸多的研究人员对关联规则的挖掘问题进行了大量的 研究。并且，随着数据库应用的普及，数据采剩的应用范围越来越广，人竹j 越来越关注挖掘山的信 息的有用性。 让我们来看这样一个例子，设若在一个底层交易数据库中有n 条交易记录为方便起见，我们只讨 论这n 条记录购买咖啡和奶粉的隋况如表2 1 所示，行c 和c 分别对应购买了咖啡和没有购买咖啡的 记录数，列m 和删分别对应购买了奶粉和没有购买奶粉的记录数。 袭2 1 购买咖啡和牛奶的统计表f ) 7 基于兴趣度的离群点挖掘技术研究 可以进一步分析关联规则c o f f e e - - m i l k ，它的支持度s = 2 0 1 0 0 = 2 0 ，应该说是很高的；它的置 信度c = i e u m l i c l = 2 0 2 5 = 8 0 ，同样已经非常高了。当我”j 把置信度和支持度阈值定为低于0 8 和0 2 时，很显然该规则将会作为目标规则之一被挖掘出来。由此我们得出结论，刺激顾客对咖啡的购买欲 望将增加奶粉的销售量，或换句话说，将咖啡和奶粉放在一起将提高奶粉的销售量。 然而，事实并非如此。原始交易库告诉我们有9 0 的顾客会购买奶粉。而上述挖掘出的关联规 则显示买咖啡的顾客有8 0 的可能性购买奶粉。也就是说，个已知买了咖啡的颇客购买奶粉的可 能性事实上比一个我们不知道任何信息的顾客购买奶粉的可能性小( 小1 0 ) 。我们并不能肯定地说 购买了咖啡就会购买奶粉这条规则一定不正确，但至少它的价值已经不如人们开始期望的那么商了， 更严重的话，这条规则确实会是误导性的。因为事实上，由原始库可以看出不买咖啡就会买奶粉 ( c o 虢e m i l k ) 的可能性更大( 7 0 7 5 = 9 3 3 ) 。 由此可见，只要人们仍把支持度作为最初项集产生的主要决定因素，那么，要么把支持度设的 足够低以使得不丢失任何有意义的规则，要么冒着丢失一些重要规则的风险定义较高的支持度：对 前一种情形计算效率将成为一个问题，而后一种情形则有可能丢失从用户观点看来是有意义的规则。 为了修剪一些无趣的规则，即避免生戒“错觉”的关联规则，人们定义了兴趣度这个度量值来进一 步约束挖掘出来的关联规则。 2 。3 兴趣度的研究现状 对兴趣度的研究至今已有许多各式各样的定义：在【1 1 】中作者给出了感* 趣的规则的定义 ( r i n t e r e s t i n g ) ，以关联规则的支持度和置信度的差的绝对值为核心构造表达式作为兴趣度的定义， 其后在【1 2 中，作者又对此作了改进。文 1 3 把事件的依赖性的统计定义扩展到了兴趣度的定义上； 文 1 4 定义了否定关联规则的兴趣度。k l e m e t t i n e n 等定义了模版( t e m p l a t e ) 的概念”1 ，用户使用它 来确定哪些规则是令人感兴趣的而哪些则不然。也就是说，如果一条规则匹配一个包含的模版 ( i n c l u s i v et e m p l a t e ) ，则是令人感兴趣的，然而，如果一条规则匹配一个限制的模版( r e s t r i c t i v e t e m p l a t e ) ，则被认为是缺乏兴趣的。在文 9 中将一个基于差异思想的兴趣度定义运用到关联规则中， 设一个数据库d ，给出规则r ：b = h ，关联规则式给出r 的正确度是由它的置信度c = i h u b i 1 8 1 决定的，而所有原始记录支持该规则反映信息的比例可用原始记录中支持该规则右部h 所反映信息 的比例来表示，即s r h = i h i i d t 。于是 9 中定义规则r 的兴趣度为( 其中c r 为规则r 的置信度，s m t 为规则r 的支持度) ： m 坛= 意志 8 基于兴趣度的离群点挖掘技术研究 然后在 1 0 中继续研究了对该挖掘算法的反向挖掘应用，即否定的兴趣关联规则。此外还有蕴 涵性度量：用a ，b 的信任度p ( a ) p ( b ) p ( a ，b ) 来定义：蕴涵规则( i m p l i c a t i o nr u l e ) ，规则的蕴涵强 度在 o ，一】之间变化，其中蕴涵强度为1 表示完全无关的规则，o 。表示完备的规则，如果蕴涵强度大 于1 则表示更大的期望存在性：类似的还有收集强度( c o l l e c t i v es t r e n g t h ) ：使用“大于期望值”来 发现有意义的关联规则。项集的“收集强度”是f o ，m 之间的一个数值，其中0 表示完备的否定相关 性，而值o o 表示完备的正相关性：及改进度等不同形式用来进一步定义筛选关联规则的兴趣度。 必须指出，现有的兴趣度定义止于单表，其算法也大多基于a p r i o r i 算法，多库间的兴趣度定义 尚朱在国内有明确研究。目前的分布式存储技术在关系数据库系统的关联规则挖掘上也有应崩，但 其分布的数据库具有相同的表结构，对于不同构数据库间的分布存储和采掘尚不多见。由于表间连 接时空开销较大，而且多个表可能属于不同的数据库，甚至不同的机构，因安全性等因素不能将其 在物理上迮接起来，因此需要从多个表中直接提取关联规则，考虑这种情况f 的兴趣度则是更深一 步的数据挖掘技术。 2 4 本文兴趣度的具体意义 相对于目前研究得较多的用支持度，置信度及它们构成的表达式所定义的兴趣度来挖掘兴趣规 则，频率较少的项集同样值得关注，而且往往含有用户感兴趣的信息，也是兴趣规则的一种。它的 出现越不同寻常，则越有挖掘价值。不同于2 3 节所述的研究方向，本文考虑此类兴趣规则所决定 的兴趣皮，主要由规则的新奇性决定，故用新奇度米定义兴趣度，其含义指出现概率极少的数据或 表现异常的数据( 一般称作孤立点或离群点) 。着重挖掘此类数据和由其推导出来的规则，从中发现 用户真正感兴趣的信息。 通过新奇度挖掘在现实数据库的挖掘应用中具有极高的应用价值。例如，在企业信用卡销售记 录数据库中检测销售记录，可能发现恶意透支者很少使用的一种特殊用卡方式，总结这些案例的资 料，找出共同特征。比如说，是某个特定地区的，f 次如果有人使用这些方式作案，很可能就与记 载的使用相同方式的人或出现地区有关系，对于发现和缩小作案者的范围有很大帮助。类似的在入 侵检测和网络安全等其他方面都有极高的实际应用意义。 我们的论文研究工作是结合国家科技部中小型企业创新基金项目“企业商务智能决策导航器一 一e b i d n ，( 项目编号：0 2 c 2 6 2 1 3 2 1 0 0 7 0 ) 开展的。在这一课题研究中关联规则挖_ i l 是决策技术的 主要内容，鉴于在关联规则算法研究中基于若趣度的离群点挖掘技术的应用需求，我们对此主题进 行了深入的专门研究。事实上这一专题研究的价值是极其重大的。例如：对于一个企业应用系统而 言，根据网络服务、事务及其他相关数据的分析，对其进行挖掘，可以得到关于入侵的相关信息。 9 基于兴趣度的离群点挖掘技术研究 仔细分析这些挖掘结果，并对现有的危险采取相应的防范措施，就能够有效的加强网络的管理、建 设和维护。这对于一个单位，企业甚至国家都具有重大的现实意义。 1 0 基于兴趣度的离群点挖掘技术研究 第三章离群点的挖掘技术 根据新奇度的含义，又考虑到离群点具有新奇度的特征，为了挖掘异常情况下出现的数据，我 们把离群点的检测技术应用于该类数据的挖掘，以衡量离群点的偏离度来代替规则的新奇度，以此 为依据发现新奇类的兴趣规则。需要说明的是，我们所指的离群点即国内数据挖掘研究的孤立点， 为了保持和参考文献的一致性，本文中保留了“孤立点”这个名词。 3 1 关于孤立点的数据挖掘 在数据仓库和知识发现领域，人们一直十分重视数据集中“孤立点”的检测。著名的孤立点定 义由d h a w k i n s 在【6 中首次提出。所谓孤立点是指在数据集中，常常存在些数据对象，他们不符 合数据的一般模型，即与数据的其他部分( 往往是大部分) 不同或不一致，我们称这样的数据对象 为孤立点( o u t l i e r ) 。孤立点可能是由度量或执行错误导致的。例如，在程序中对未记录年龄的缺省 设置而导致一个人的年龄可能为9 9 9 。另外，孤立点也可能是固有的数据的变异性的结果。例如， 一个公司的总经理的工资自然远远高于公司其他职员的工资，成为一个孤立点。这样的孤立点有助 于我们发现工作中的某种特殊情况。 许多数据挖掘算法试图使孤立点的影响最小化，或者排除它们。但是，由于一种情况下的噪声 可能成为另一种情况下的有用信号，这就有可能导致重要的隐藏信息的丢失。例如，在欺诈探测中， 孤立点可能预示着欺诈行为。此外，在市场分析中可根据孤立点去探究极低或极高收入的客户的消 费行为，或者在医疗分析中用于发现对多种治疗方式的不寻常的反应。总而言之不管孤立点是应 该去掉的噪声，还是隐藏有重要信息的数据单元，都能从正面或反面给我们提供有用的信息，在数 据挖掘中检测出数据集中的孤立点是非常重要的。 孤立点的挖掘可以描述如下；给定一个r 1 个数据点或对象的集合，及预期的孤立点的数目k ， 发现与剩余的数据相比是显著相异的、异常的或不一致的头k 个对象。由此，孤立点挖掘可以看作 是两个子问题： ( 1 )在给定的数据集合中定义什么样的数据可以被认为是不一致的； ( 2 ) 找到一个有效的方法米挖掘这样的孤立点。 随着统计领域和数据库领域对孤立点检测的重要性意识的增加，更多具体的孤立点含义被明确 定义并用来解决特定领域的难题，这些定义虽然貌似不同，但都建立在h a w k i n s 的定义原型基础之 匕。 基于兴趣度的离群点挖掘技术研究 3 2 孤立点检测的分类及研究状况 围绕孤立点的定义，人们开展了检测方法的深入研究，到目前为止，已经有很多较为成熟的孤 立点检测方面的研究，大致分为五类 8 1 ： 第一种是基于分布的孤立点检测( d i s t r i b u t i o n b a s e da p p r o a c h ) ，对给定的数据集合假设了一个 分布或概率模型( 正态分布、柏松分布等) ，然后根据模型采t l j 不一致性检验( d i s c o r d a n c et e s t ) 来确 定孤立点，这种方法通常在统计学中应用很多。它规定偏离一个给定分布的点为孤立点。该检验要 求知道数据集参数( 例如假设的数据分布) 、分布参数( 例如均值和方差) 和预期的孤立点的数目。 基于统计学的方法检测孤立点的一个主要缺点是，绝大多数检验是针对单个属性的，而许多数据挖 掘问题要求在多维空间中发现孤立点。而且，统计学的方法要求关于数据集合参数的知识，例如数 据分布方面的知识等。 由于在许多情况下，大多数的数据分布可能是未知的。当没有特定的检验时，统计学方法不能 确保所有的孤立点被发现，或者观察到的分布不能恰当地被任何标准的分布来模拟。退一步说，如 果采用这种方法，对于不存在任何点分布先验知识的数据集，我们不得不事先举行多次实验来断定 哪种分布城是否存在某种分布最适合表示这些数据集的分布规律或与数据的分布相吻合。这种前提 上作的代价是十分昂贵的；而且，实际系统中的数据是多变的，特别是随着数据的增加，其分布模 式有可能发生重大的或和以前截然不同的变化，在这种情况下，我们不得不重新研究其分布模式， 而前面所作的工作很可能付之东流。所以，随着数据库在现实中应用的逐步扩展，这种检测方法的 局限性和弊端日益增大。 第二种是基于深度的孤立点检测( d e p t h - b a s e da p p r o a c h ) ，这种方法建立在几何计算的基础上， 主要依赖计算k - d 球凸外侧的不同层数，在外层的点被认为是孤立的。然而，这些算法在维数高的 情况下性能很低，无法处理大规模的数据，目前应用较少。 第三种是基于距离的( d i s t a n c e b a s e da p p r o a c h ) ，在k n o r r 和n g 的文章中提到，如果一个数 据集中的点，有至少p c t 的点与之相隔d m i n 以上的距离，则这个点是孤立的。这种孤立点检测方 法主要取决于对p c t 、d m i n 的值的统一规定。如果一个数据集中有稀疏和密集的点集，取值稍不 注意。则较稀疏的点极有可能全部被认为是孤立点，如图3 - l 所示。 图3 - 1基于距离的孤立点检测的缺陷 1 2 基于兴趣度的离群点挖掘技术研究 在图3 - 1 中，按照基于距离的孤立点检测方法，如果距离阀值太大，d r a i n 大于右边点集的平 均间距，则点o 就会无法被检测出来，如果过小，d r a i n 为左边点集的平均间距，则右边较稀疏的点 就会全部被认为是孤立点。因而。两种情况都无法正确检测山我们所需要的孤立点。 第四种是基于聚类的方法( c l u s t e r i n g b a s e da p p r o a c h ) ，孤立点在这些方法中作为一个副产品， 这类方法主要取决于聚类方法的效果。既然主要目标是聚类，故这种方法对孤立点检测来说肯定不 是昂优的。在大多数情况下，孤立点的标准是含蓄的，不能轻而易举的从聚类过程中被发现。因此， 聚类可以用来做孤立点检测的数据准备，但不能算做最终可以使用的最佳的孤立点检测方法。 第五种是基= i 二密度的方法( d e n s i t y b a s e da p p r o a c h ) ，也是我们研究工作所讨论的算法依据之一。 一般而言，一个数据集的不同部分表现出不同的特征，考虑一个点与其相邻点表现山来的特征与别 的点的不同是十分有意义的，在这个方面m b r e u n i g 等提山了一个点的l o f 的概念口】( l o c a l o u t l i e r f a c t o r ) 。即局部偏离因素，是对一个点与其相邻点密度差异的直观测量，相邻距离被定义为第m i n p t s 个最靠近当前点的距离。l o f 值高的点就是孤立点。然而 5 中的工作需要计算所有点的l o f 值， 这项l = 作是非常繁杂的，因为它要求大量的k 临近点的查询操作。由于不是每个点都有可能成为孤 立点，后来有人提出改进的算法【”1 ，只要求取出l o f 值最人的前n 个点，这样就减少了一些计算。 l o f 算法的主要消耗取决于m i n p t s 的值。但有文章指出了l o f 的弱点【8 】。例如m i n p t s 的选择要求 较高，为了检测出比较边缘的聚类，m i n p t s 必须取值和这些聚类的大小一样( 如图3 2 ，如果我们 采明了较近的邻居定义，若邻居很少，就可能忽略边远地区的小规模聚类点集) 。 图3 - 2l o f 方法的缺点不总图 后来有人对l o f 进行改进，提出l o f 、l o f ”和g r i d l o f 等算法，进一步改进它的性能。针 对l o f 的弱点，s p i r o sp a p a d i m i t r i o u 等人介绍了多粒度偏离因素m d e f ( m u l t i - g r a n u l a r i t y d e v i a t i o n f a c t o r ) 的概念，在此基础上提出了l o c i ( l o c a l c o r r e l a t i o ni n t e g r a lm e t h o d ) 和a l o c i ( a p p r o x i m a t e l o c i ) 算法，达到比较理想的挖掘效果。 值得一提的是，在本文算法中我们用到了l o f 方法来判断孤立点，但是不会受到以上缺点的影 响，因为在挖掘孤立点前把这样的聚类点都删除了，这样一来就可以避免此类情形，从而保证l o f 算法的准确实施。 近来叉出现了一些在这五类之外的研究方法，例如基于划分的方法( p a r t i t i o n b a s e da l o g r i t h m ) ， 一一 一 茎王堂垫些塑塑鲎皇堡塑垫查塑塞 先把数据集按一定规律划分为多个子集，再对各个子集进行筛减处理，详细的算法在 2 8 中有讨论。 研究基于连接的孤立点( c o n n e c t i v i t y b a s e do u t l i e r ) 1 2 0 1 ，也是相对