（计算机应用技术专业论文）数据挖掘中孤立点检测算法的研究.pdf

摘要 数据挖掘是从大量的数据集中提取隐含的、未知的、潜在有用的 知识的过程，是数据库研究最活跃的领域之一。而孤立点检测是数据 挖掘中的重要研究分支，其作用就是发现数据集中的“小模式 ，即 显著不同于其它数据的对象。经过近2 0 年的发展，孤立点检测技术 得到了广泛的应用。传统的孤立点检测算法存在一些难以克服的障 碍，例如算法的参数难以选择造成检测结果不稳定，算法难以适应高 维数据的特性等。本论文主要针对以上问题，对孤立点检测算法进行 了研究。 本文对当前的孤立点检测算法进行详细地研究比较，指出各自的 适用范围和存在的不足，并在此基础上完成主要工作如下： 本文在对基于单元的孤立点检测算法的详细研究分析的基础上， 针对该算法中边界处孤立点的误判问题，提出用数据集边界阈值动态 调整函数的方法来解决此问题，针对距离值d 需要手动输入的问题， 提出利用抽样平均距离来代替手动输入距离值d 。 改进后的算法不仅有效地减少了边界处孤立点的误判，还减少了 参数的输入，提高了算法的自动化程度。 针对传统孤立点检测算法对高维数据的适应性较差的情况，提出 基于粗糙集的孤立点挖掘算法，为孤立点的定义和孤立点的挖掘提出 一个新的方法，并用实验充分验证粗糙集理论在孤立点检测算法中的 有效性。 关键词数据挖掘，孤立点检测，边界单元格，粗糙集 a b s t r a c t a so n eo ft h em o s te x c i t i n gf i e l d so fd a t a b a s er e s e a r c h ，d a t am i n i n g ， r e f e r st oap r o c e s si nw h i c ht h ei m p l i e d ，u n k n o w nk n o w l e d g eo f p o t e n t i a l u s ei se x c a v m e df r o mav a s tc o l l e c t i o no fd a t a o u t l i e r sd e t e c t i o ni sa i m p o r t a n tp a r to fd a t am i n i n gr e s e a r c h i t sp u r p o s ei st of i n dt h e “s m a l l p a t t e m s f r o md a t a s e t a no u t l i e ri sa l lo b j e c tt h a ti sc o n s i d e r a b l y d i s s i m i l a ro ri n c o n s i s t e n tw i t ht h er e m a i n d e ro ft h ed a t a w i t ht h e d e v e l o p m e n to fn e a r l yt w e n t yy e a r s ，o u t l i e r sd e t e c t i o nh a sb e e nu s e di n m a n yf i e l d s t 】r a d i t i o n a lo u t l i e rd e t e c t i o na l g o r i t h m sh a v ee n c o u n t e r e d s o m ei n s u r m o u n t a b l eo b s t a c l e s f o ri n s t a n c e ：t os e l e c tt h ea l g o r i t h m s p a r a m e t e r si sd i f f i c u l tw h i c hl e a dt oa nu n s t a b l er e s u l t ；t h ea l g o r i t h mi s d i 伍c u l tt om e e tt h e h i g h d i m e n s i o n a ld a t ac h a r a c t e r i s t i c s ；a n d s o o n t h e s ep a p e rm a i n l yf o r t h ea b o v ep r o b l e m sd os o m er e s e a r c ho n o u t l i e rd e t e c t i o na l g o r i t h m t h ee x i s t i n go u t l i e rd e t e c t i o n a l g o r i t h m s a r ei n t r o d u c e da n d a n a l y z e di nt h i st h e s i s t h ea p p l y i n ge x t e n ta n ds h o r t a g e so ft h ee x i s t i n g o u t l i e rd e t e c t i o na l g o r i t h m sa r ep o i n t e do u t t h em a i nc o n t e n to ft h i s t h e s i si sa sf o l l o w i n g ： b a s e do nt h er e s e a r c ho ft h ea l g o r i t h mo fb a s e d e e l lo u t l i e rd e t e c t i o n 。 an e wo u t l i e r - a n a l y s i sa l g o r i t h mi sp r e s e n t e d ad y n a m i ca d j u s t m e n t f u n c t i o no nd a t a s e tb o u n d a r yt h r e s h o l di su s e dt os o l v et h ep r o b l e mo f m i s - j u d g e m e n ta b o u tt h eo u t l i e ro nt h eb o u n d a r y a sf o rt h ep r o b l e mt h a t i ti sn e e d e dt oi n p u tt h ev a l u eo fd i s t a n c ed m a n u a l l y , t h em e a ni su s e dt o i np l a c eo fm a n u a li n p u t t i n g ，n l en e wa l g o r i t h mn o to n l yr e d u c e st h e m i s - j u d g e m e n tt ot h eo u t l i e ro nt h eb o u n d a r y , b u ta l s od e c r e a s e st h ei n p u t o f p a r a m e t e r sa n dp r o m o t e st h ed e g r e eo fa u t o m a t i z a t i o no fc a l c u l a t i o n a sf o rt h ep r o b l e mt h a tt h ea l g o r i t h mi sd i 衢c u l tt om e e tt h e h i 曲- d i m e n s i o n a ld a t ac h a r a c t e r i s t i c s ，a na l g o r i t h mb a s e do nr o u g hf o r o u t l i e rd e t e c t i o ni sp r o p o s e d an e wm e t h o di so f f e r e df o rt h er e s e a r c ho f o u t l i e rd e t e c t i o na l g o r i t h m s i na d d i t i o n ，i no r d e rt op r o v ei t sf e a s i b i l i t y , r e l e v a n te x p e r i m e n t sh a v eb e e np e r f o r m e d k e y w o r d s d a t am i n i n g ，o u t l i e rd e t e c t i o n ，b e n f o r dl a w , r o u g h l l 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得中南大学或其他单位的学位或者证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：j 弘j l 日期： 抛弋年 f 月 2 f 日 关于论文使用授权的说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有 权保留学位论文，允许该论文被查阅和借阅；学校可以公布该论文的 全部或部分内容，可以采用复印、缩印或其他手段保存学位论文；学 校可以根据国家和湖南省有关部门规定送交学位论文。 日期：弦。气年争月2 户 中南大学硕士学位论文 第一章绪论 1 1 研究背景 第一章绪论 随着计算机技术的应用及互联网的日益普及，“丰富的数据和贫乏的知识 问题日见突出，激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行 更高层次的分析，以便更好地利用这些数据h 1 。据统计，早在2 0 世纪8 0 年代，全 球信息量每隔2 0 个月就要增长一倍，而进入9 0 年代，全世界拥有的数据库及其所 存储的数据规模增长更快。9 0 年代互联网的出现与发展，以及随之而来的企业内 部网和企业外部网、虚拟私有网的产生和应用，使整个世晃连接成一个小小的地 球村。这样，展现在人们面前的已不是局限于本部门、本单位和本行业的庞大数 据库，而是互相交织的信息海洋。据估计，1 9 9 3 年全球数据存储容量约为2 0 0 0 t b ， 至t j 2 0 0 0 年增加到3 0 0 万t b ，面对这极度膨胀的数据量，人们受到“信息爆炸 、 “混沌信息空间 和“数据过剩的巨大压力犯，。 数据挖掘( d a t am in g ，简称d m ) 与数据仓库( d a t aw a r e h o u s e ，简称d w ) 技 术的出现正迎合了在这么极大数据量膨胀中搜寻有价值信息的需要钉。数据仓 库与传统的数据库系统有着本质的区别，它是为了便于分析针对特定主题的、集 成化的、时变的、不可更新的( 稳定的) 数据啼1 。数据仓库中数据可以来源于不同 系统的多个数据库，建立数据仓库的目的是为了更好地支持决策分析，由于以往 的数据库系统记录的是每一项业务处理的流水帐，而且分散在不同的子系统中， 同一笔业务在不同的系统中被所表示的数据类型、名称很难达到完全一致，甚至 出现一些误操作，数据仓库的出现不仅解决了这些问题，而且提供了能进行分析 和产生相应报表的在线分析工具一联机分析处理( o nl i n ea n a l y t i c a l p r o c e s s i n g ，简称o l a p ) 。o l a p 能使用户针对特定问题对数据从多个角度，从不 同层次上进行分析得到信息。但由于数据仓库中的数据来源于多个数据源，因此， 其中必定埋藏着丰富的且不为人所知有价值的信息和知识，要想及时准确得到这 些就必须借助计算机和智能化自动工具，来帮助挖掘隐藏在数据中的各类知识。 为实现这样的目标，多年来，数理统计技术方法以及人工智能和知识工程等领域 的研究成果，给开发满足这类要求的数据深度分析工具提供了坚实而丰富的理论 和技术基础。 “挖掘 一词最早出现于统计学中，是数据库技术与人工智能、机器学习、 神经网络、统计学、模式识别、知识库系统、知识获取、信息提取、高性能计算 和数据可视化等学科相互结合的最前沿和极富应用前景的最新研究领域怕1 。从统 中南大学硕士学位论文第一章绪论 计学的角度，数据挖掘是指分析所观察的数据集，以发现可信的数据间的未知关 系并提供给数据拥有者可理解的、新颖的和有用的归纳数据盯1 。从数据库的观点 来看，数据挖掘是指从存储在数据库、数据仓库或其它信息仓库中的大量数据中 发现有趣的知识的过程陋1 。从机器学习的角度，数据挖掘定义为从数据中抽取隐 含的、明显未知的和潜在有用的信息嘲。目前，人们比较倾向认为数据挖掘，也 叫数据库中的发现知识( 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 ，简称k d d ) ，就是从 大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其 中的、人们事先不知道的、但又潜在有用的信息和知识的过程。它把人们对数据 的应用从低层次的简单查询，提升到从数据中挖掘知识，以提供决策支持。这是 从数据到知识演化过程中的一个重要里程碑。 数据挖掘是在1 9 8 9 年8 月于美国底特律市召开的第十一界国际联合人工智 能学术会议上正式形成的，人们常常与数据库中的知识发现( k n o w l e d g e d i s c o v e r yf r o md a t a b a s e ，简称k d d ) 混淆0 i 。从1 9 9 5 年开始，每年主办一次 k d d 国际学术会议，将k d d 和d m 方面的研究推向了高潮，从此数据挖掘一词开 始流行。迄今为止，由美国人工智能协会主办的k d d 国际讨论会议召开了十二次， 规模由原来的专题讨论会发展到国际学术大会。 除了美国人工智能协会主办的k d d 年会外，还有许多的数据挖掘年会，包 括亚太知识发现和数据挖掘会议( p a c i f i c - a s i ac o n f e r e n c e ；o nk n o w l e d g e d i s c o v e r ya n dd a t am i n i n g 简称p a k d d ) ，欧洲数据挖掘讨论会( e u r o p e a n s y m p o s i u mo np r i n c i p l e so f d a t am i n i n ga n dk n o w l e d g ed i s c o v e r y 简称p k d d ) 现在一般伴随欧洲机器学习讨论会召开( e u r o p e a nc o n f e r e n c eo nm a c h i n e l e a r n i n g 简称e c m l ) 等。此外，数据库、人工智能、信息处理、知识工程等领 域的国际学术刊物也都开辟了k d d 专题或专刊。 孤立点检测，也称为异常点检测。长期以来，人们都十分关注数据集中异常 的数据，这些数据通常被认为污染了数据集，即改变数据集的原有信息或数据产 生机理，因此许多数据挖掘算法试图使孤立点的影响最小化，或者排除它们。然 而，一个人的噪音可能是另一个人需要的重要信号，简单地剔除孤立点的方式可 能导致一些重要信息的丢失。过去的一个多世纪中，孤立点问题的研究经历了几 次盛衰交替。今天，它再次成为数据挖掘的一个新的热点，受到广泛关注。 孤立点检测是数据挖掘中的一项重要技术，其目标是发现数据集中行为异常 的少量的数据对象。在数据挖掘领域，孤立点检测的研究对象是数据集中偏离绝 大多数对象的很小一部分。在很多数据挖掘应用中，发现孤立点比发现普通情况 更有意义，更需要保留与研究m 1 。例如飞机性能统计数据中的一个孤立点，可能 表示飞机发动机的一个设计缺陷；地理图像上的一个孤立点可能标志着一个危险 2 中南大学硕士学位论文 第一章绪论 对象( 如一颗地雷) ：另外，系统中的一个孤立点还可能是对某个恶意入侵的精确 定位n 羽。孤立点挖掘还可应用于金融欺诈、网络监控、数据清洗、电子商务、职 业运动员的成绩分析、故障检测、天气预报、医药研究、信贷信用等领域n 。 孤立点挖掘可以被形势化的描述：给定一个含有n 个数据点或对象的集合， 预期的孤立点数目k ，发现集合中与其余数据相比显著相异的、异常的或者不一 致的前k 个对象，所以，孤立点挖掘问题可以被看作两个子问题n 钔： ( 1 ) 在给定的数据集中定义什么样的数据被认为是不一致的。 ( 2 ) 找到一个有效的方法来挖掘这样的不一致的点。 由于数据集中数据的动态性、多样性和多维性，挖掘数据集中的孤立点问题 通常是比较困难的。 1 2 国内外研究现状 数据挖掘在研究和应用方面发展迅速，尤其是在商业和银行领域，其应用比 研究的发展速度还要快。目前，根据国际上数据挖掘的发展趋势，其研究主要有： 对知识发现方法的研究进一步发展，如近年来注重对b a y e s 方法以及b o o s t i n g 方法的研究和提高n 目；传统的统计学回归法在数据挖掘中的应用；数据挖掘与数 据库、数据仓库的紧密结合。在应用方面包括：数据挖掘商业软件工具不断产生 和完善，注重建立解决问题的整体系统，而不是孤立的过程。用户主要集中在大 型银行、保险公司、电信公司和销售业，制造业的应用也正在逐渐展开。国内从 事数据挖掘研究的人员主要在大学，也有一部分在研究所或者公司。所涉及的领 域很多，一般集中于学习算法的研究、数据挖掘的实际应用以及有关数据挖掘理 论方面的研究。 在以前的很多研究中，往往将孤立点的检测作为聚类算法的副产品，这些算 法更多地认为孤立点是嵌入到类中的背景噪声数据n 们。孤立点检测是数据挖掘中 一个重要的研究方面n 他，与关联规则挖掘、分类、类描述等数据挖掘不同，孤 立点发现用来检测数据集中小部分对象，即数据集中显著不同于其它数据的可疑 对象。 1 9 9 1 年，数据挖掘的出现为欺诈侦测和预防分析研究注入了新的活力，提供 了新的思路。国内外许多学者纷纷采用数据挖掘技术，对原始的应用业务数据进 行处理，挖掘蕴涵在交易数据背后，反映交易规则，以实现对业务中可疑行为进 行侦测和预测，最终达到指导中防范诈骗的目的。 孤立点发现在国外获得了广泛的研究和应用，e m k n o r r 和r t n g 将孤立点 检测用于分析n h l ( n a t i o n a lh o c k e yl e a g u e ) 的运动员统计数据，用来发现表现 例外的运动员：k y a m a n i s h i 和j t a k e u c h i 演示了如何将孤立点检测应用于股 3 中南大学硕士学位论文第一章绪论 票数据的变动检测；j l a u r i k k a l a ，m j u h o l a ，e t a l 研究了孤立点在医学数据中 的应用；l g r o s s i 则将孤立点分析应用于数据质量评价：近来，空间孤立点检 测被大量研究；在数据仓库领域，孤立点检测被用来发现不一致的数据，提高数 据质量。 e d w i nm k n o r r 和r a y m o n dt n g 在基于距离的孤立点的含义分析中提出 了孤立点的孤立程度的概念。孤立点有强弱之分，并提出了u p l a t t i c e 算法来挖 掘这些程度不同的孤立点。在另一篇文章中，他们提出了孤立点挖掘的一种基于 距离的u n i f i e da p p r o a c h ，并提出了相应的算法。 d b m i n e r 是加拿大的d b m i n e rt e c h n o l o g y 公司开发的数据挖掘软件。它的最 新关联规则挖掘模块d b m i n e ra x2 0 0 2 和序列规则挖掘模块d b m i n e rs x2 0 0 2 使用关联挖掘算法或序列挖掘算法来找出那些有疑问( 孤立点) 的业务。 i s l a n d i a ，n y 软件公司开发了c l e v e r p a t h 为金融、银行和保险业的客户提 供自动化的、随行业定制的欺诈侦测工具。通过具体分析公司的业务从而进行侦 测欺诈和其他违法行为。其他的欺诈侦测软件如d e l t am i n e r 把新的搜索技术和 商务智能方法集成在o l a p ( 在线分析处理) 系统的前端从而发现最重要的孤立 点；k e p l e r 是一个包含偏离检测功能的数据挖掘软件包。 相比之下在国内对孤立点数据挖掘研究、应用方面比较晚，大多数是局于理 论，局部范围的应用。重庆工学院的曹长修提出了利用决策树来搜索可疑信息为 进行检测金融欺诈提供有利工具。 1 3 论文的研究内容 本论文的主要研究内容有以下三个方面： ( 1 ) 为了减少参数的输入，提高算法的自动化程度，对基于单元的孤立点 检测算法中的参数d ，提出用抽样平均值来代替参数d 。 ( 2 ) 为了减少边界单元格误判问题，对基于单元的孤立点挖掘算法中的边 界单元格m 值，给出了调整函数，并在以上两点的基础上改进了算法，达到了较 好的效果。 ( 3 ) 提出了基于粗糙集的孤立点挖掘算法，并用实验证明了该算法的正确 性和有效性。 1 4 论文的组织结构 本文采用的研究方法是理论研究与实证研究相结合。在文献阅读的基础上结 合调查访问、实例数据的挖掘分析；同时在定性研究的基础上大量结合定量研究 4 中南大学硕士学位论文第一章绪论 的方法。 本论文共分五章，结构如下： 第一章简单介绍了本课题的研究背景和意义、论文的主要研究内容和思路。 第二章详细的分析了数据挖掘技术的研究现状和孤立点挖掘理论，在分析 孤立点挖掘技术的基础上，介绍了一些典型的孤立点挖掘算法，并分析了这些算 法的时间复杂度以及各自的优点和缺点。 第三章在前人研究的基础上，对距离值d 提出了改进方案，用抽样平均距 离来代替，减少参数的输入。对边界单元格出现误判的问题提出了解决方案，该 方法能均衡待处理边界单元格邻居的数目。同时对对象间距离的计算和数据量标 准化进行了论述。 第四章在对粗糙集理论和孤立点算法进行详细分析的基础上，提出了基于 粗糙集的孤立点挖掘算法，为孤立点的定义和孤立点的挖掘提出了一个新的方 法，并用实验充分验证了粗糙集理论在孤立点检测算法中的可用性。 第五章对论文的研究工作进行总结，对未来的研究工作进行展望，并提出 进一步研究的方向。 5 中南大学硕士学位论文第三章基于粗糙集理论的孤立点算法 第二章数据挖掘技术和孤立点算法分析 2 1 数据挖掘概述 数据挖掘是一种从大型数据库或者数据仓库中提取隐藏的预测性信息的新 兴科学，而其数据挖掘算法更是这种新技术的灵魂所在。随着数据挖掘技术的快 速发展，数据挖掘在各个领域的应用也就越来越广泛，数据挖掘算法的应用更是 这个新技术的核心。简单的讲，数据挖掘就是从大量数据中提取或者挖掘知识， 一般具有如下的特点： ( 1 ) 数据规模十分巨大。 ( 2 ) 不能形成精确查询要求，一般是决策者提出的即时随机查询。 ( 3 ) 数据变化迅速，需要对动态数据做出快速反应提供决策支持。 ( 4 ) 主要基于大样本的统计规律，其发现的规则不一定适用于所有数据。 2 1 1 数据挖掘过程及系统结构 当前，数据挖掘界公认的规范标准是由s p s s 、n c r 、d a i m l e r c h r y s l e r 等多 家世纪知名公司根据世纪经验和理论基础共同设计的c r i s p d m ( c r o s si n d u s t r y s t a n d a r dp r o c e s sf o rd a t am i n i n g ) ，其流程图如图2 1 所示。 图2 - 1c r i s p d 粗方法 6 中南大学硕士学位论文第三章基于粗糙集理论的孤立点算法 由图2 1 可知，一个数据挖掘项目的生命周期由六个阶段组成，各个阶段的 顺序可以有所变化，这取决于每个阶段的结果和接下来将要实施的阶段或者一个 阶段的具体任务。箭头指出了各个阶段间最重要和频繁的关联。最外层的循环表 示数据挖掘本身的循环特征，即数据挖掘并非一旦得到一个解决方案就结束了， 在流程和解决方案中得到的教训可以引发新的、常常是更为集中的商业问题。每 个阶段的要点如下： ( 1 ) 业务理解( b u s i n e s su n d e r s t a n d i n g ) ：这个阶段集中在理解项目目标 和从业务的角度理解需求，同时将这个知识转化为数据挖掘问题的定义和完成目 标的初步计划。 ( 2 ) 数据理解( d a t au n d e r s t a n d i n g ) ：数据理解阶段从初始的数据收集开 始，通过一些活动来熟悉数据并识别数据的质量问题，首次发现数据的内部属性， 或是探测引起兴趣的子集去形成隐含信息的假设。 ( 3 ) 数据准备( d a t ap r e p a r a t i o n ) ：数据准备阶段包括从未处理数据中构 造最终数据集的所有活动，这些数据将是模型工具的输入值。其任务包括表、记 录和属性的选择，以及为模型工具转换和清洗数据。 ( 4 ) 建立模型( m o d e l i n g ) ：在这个阶段，主要是选择各种建模技术，同时 对模型的参数进行调整以达到最佳的数值。一般，有些技术可以解决一类相同的 数据挖掘问题。有些技术在数据形成上有特殊要求，因此需要经常跳回到数据准 备阶段。 ( 5 ) 模型评估( e v a l u a t i o n ) ：到项目的这个阶段，基本已经从数据分析的 角度建立了一个高质量显示的模型。在开始最后模型发布之前，重要的事情是彻 底地评估模型，检查构造模型的步骤，确保模型可以完成业务目标。这个阶段的 关键目的是确定是否有重要业务问题没有被充分的考虑。 ( 6 ) 模型发布( d e p l o y m e n t ) ：根据需求，这个阶段可以产生简单的报告， 或是实现一个比较复杂的、可重复的数据挖掘过程。即组织并以一种客户能够使 用的方式呈现。 在数据挖掘的整个生命周期中，被研究的业务对象是整个过程的基础，它即 是整个挖掘过程的驱动又是检验最后结果和指引分析人员完成数据挖掘的依据 和顾问。其实，数据挖掘的过程并不是自动的，这其中绝大多数的工作需要人工 完成。对挖掘数据的准备将用去4 5 的时间，这说明数据挖掘对数据的严格要 求，而挖掘工作仅占总工作量的1 5 ( 见图2 - 2 ) 。 7 中南大学硕士学位论文 第三章基于粗糙集理论的孤立点算法 0 3 5 、 、 3 0 1 u 无 业务理解数据理解数据准备数据挖掘模型评估结果公布 图2 - 2 数据挖掘每个过程花费时间和重要性比较 _ 花费时间 币噩性 数据挖掘或者知识发现( k d d ) 是c r i s pd m 中屉重要的环节，其整体过程可 描述如图2 3 所示。 田2 - 3 敷据挖掘全过程 如图2 - 3 所示，整个知识发现过程是由若干挖掘步骤组成，而数据挖掘仅是 、 二 j ； 0 中南大学硕士学位论文 第三章基于粗糙集理论的孤立点算法 其中的一个主要步骤。整个知识发现的主要步骤有： 数据清洗：其作用主要用来消除噪声或者不一致数据。 数据集成：将来自多个数据源的数据组合起来。 数据转换：将数据转换为易于进行数据哇的数据存储形式。 数据挖掘：利用智能挖掘方法挖掘模式或规律知识。 模式评估：根据一定评估标准从挖掘结果中筛选出有意义的模式知识。 知识表示：利用可视化和知识表达技术，向用户展示挖掘出的知识。 由上述过程可知，整个挖掘过程是一个不断反馈的过程。比如，用户在挖掘 途中发现选择的数据不好，或使用的挖掘技术产生不了期望的结果，这时，用户 需要重复先前的过程，甚至重新开始。 基于这种观点，文献【1 4 】中提出一种知识发现的全过程得依靠可视化挖掘系 统，图2 4 就是一个典型的数据挖掘系统结构。 图2 - 4 数据挖掘结构系统图 数据挖掘系统主要包括以下几个部分： 数据库、数据仓库或其他信息库，表示数据挖掘对象是由一个( 或组) 数据 库、数据仓库、数据表单或者其他信息数据库组成。通常需要使用数据清洗和数 据集成操作，对这些数据对象进行初步处理。 数据库或数据仓库服务器负责根据用户的数据挖掘请求读取相关的数据。 知识库用于存放数据挖掘需要的领域知识，这些知识将用于知道数据挖掘的 搜索过程，或者用于帮助对挖掘结果的评估。挖掘算法中使用的用户定义的阈值 9 中南大学硕士学位论文 第三章基于粗糙集理论的孤立点算法 就是最简单的领域知识。 数据挖掘引擎是数据挖掘系统的最基本部件，通常包括一组挖掘功能模块， 以便完成定性归纳、关联分析、分类归纳、进化计算和偏差分析等挖掘功能。 模式评估模块可根据趣味标准协助数据挖掘模块聚焦挖掘更有意义的模式 知识。但该模块能否跟数据挖掘模块有机结合，取决于数据挖掘模块中使用的具 体挖掘算法。因此，若数据挖掘算法能够与知识评估方法有机结合将有助于提高 数据挖掘的效率。 可视化用户界面模块主要帮助用户与数据挖掘系统本身进行沟通交流。一方 面用户通过该模块将自己的挖掘要求或任务提交挖掘系统，以及提供挖掘搜索所 需要的相关知识；另一方面系统通过该模块向用户展示或解释数据挖掘的结果或 中间结果；此外该模块也可以帮助用户浏览数据对象内容与数据定义模式、评估 所挖掘出的模式知识，以及以多种形势展示挖掘出的模式知识。 2 1 2 数据挖掘的任务及方法 数据挖掘的任务一般可以分为两类：描述和预测。描述性挖掘任务刻画数据 库中数据的一般特性。预测性挖掘任务通过对现有数据进行分析推测，以对未来 的行为进行预测。具体的说可以分为概念描述、关联分析、聚类分析、分类和预 测、孤立点分析、等。 ( 1 ) 概念描述( c o n c e p td e s c r i p t i o n ) 描述性数据挖掘的最简单类型是概念描述。抽象的并且有意义的描述才是用 户需要的。经过归纳的抽象描述能概括大量的关于类的信息。特征描述和判别描 述是两种典型的描述。特征描述是从与学习任务相关的一组数据中提取出关于这 些数据的特征式，这些特征式可以表达该数据集的总体特征。判别描述则描述了 两个或更多个类之间的差异。 ( 2 ) 关联分析( a s s o c i a t i o na n a l y s i s ) 关联规则是一种简单、实用的分析规则，它描述了一个事物中某些属性同时 出现的规律和模式，是数据挖掘中最成熟的主要技术之一，由r a g r a w a l 等人首 次提出汹3 。其最经典的关联规则的挖掘算法是a p r i o r i 算法啪1 ，该算法先挖出所 有的频繁项集，然后由频繁项集产生关联规则。关联分为简单关联、时序关联和 因果关联。关联规则挖掘的目的是在交易数据库中发现各项之间的关联关系渊。 关联规则挖掘的一个典型例子是购物篮分析。 ( 3 ) 分类和预测( c l a s f i f i c a f i o na n dp r e d i c a t i o n ) 分类是利用训练数据集通过一定的算法而求得分类规则的过程，是数据挖掘 中一项非常重要的任务，其目的是提出一个分类函数或者分类模型。数据分类实 1 0 中南大学硕士学位论文 第三章基于粗糙集理论的孤立点算法 际上就是从数据库对象中发现共性，并将数据对象分成不同几类的一个过程。分 类的目标首先是对训练数据进行分析，使用数据的某些特征属性，给出每个类的 准确描述( 即分类规则) ，然后使用这些描述，对数据库中的其它数据进行分类。 实际上，分类是一个两步过程：第一步，建立一个模型，描述指定的数据类集或 概念集；第二步，使用模型进行分类。完成分类任务的方法有决策树、统计学方 法嘲、机器学习1 、神经网络方法等等嘲，其中决策树方法由于具有速度快、精 度高、生成模式简单等优点备受关注，比较典型的决策树算法有i d 3 和c 4 5 。 ( 4 ) 聚类分析( c l u s t e r i n g ) 聚类分析是一项重要的研究课题，在数据挖掘、模式识别、统计数据分析、 自然语言理解等领域都有广泛的应用前景汹1 。聚类是把数据按照相似性归纳成若 干类别，同一类中的数据彼此相似，不同类中的数据相异。聚类分析所分析处理 的数据都是无事先确定的类别归属，属于无监督学习方法。 聚类算法有很多种，算法的选择主要取决于数据的类型和聚类的应用目的。 总的来说，聚类算法可以分成下列几类：基于划分的方法汹3 ，具有代表性的算 法有如k - m e a n s 、p a m ，c l a r a 、c l a r a n s 等。基于层次的方法，典型代表算法 有a g n e s 、b i r c h 、c u r e 、r o c k 、c h a m e l e o n 等。基于密度的方法，典型算法有 d b s c a n 、o p t i c s 、d e n c l u e 等。基于网格的方法，典型算法有s t i n g 、w a v e c i u s t e r 等。其中，s t i n g 是基于网格方法的一个典型例子。c l i q u e 和w a v e c l u s t e r 这两 种算法既是基于网格的，又是基于密度的。 ( 5 ) 孤立点分析( o u t l i e r a n a l y s i s ) 孤立点数据包括很多有用的知识，数据库中的数据存在很多异常情况，发现 据库中数据存在的异常情况是非常重要的。孤立点检测的基本方法就是寻找观察 结果与参照之间的有很多差别的对象。本文将在后续章节中详细论述有关孤立点 分析的情况。 ( 6 ) 演变分析( e v o l u t i o na n a l y s i s ) 数据演变分析描述行为随时间变化的对象的规律或趋势，并对其建模。尽管 也包括了时态数据的分类、聚类和关联分析等，但时间序列数据分析、序列或周 期模式匹配和基于相似性的数据分析等是进化分析区别于其它方法的特征。 数据挖掘算法的好坏将直接影响到所发现知识的好坏，目前大多数的研究都 集中在数据挖掘算法理论和应用上，现在的多种数据挖掘方法从总体上可以归类 为以下几种。 ( 1 ) 统计学方法是最早应用于数据挖掘领域的方法，该方法是从事物的外 在数量的表现去推断该事物可能的规律。使用这种方法一般要先建立一个数学模 型或统计学模型，然后根据这种模型提取出相关的知识。 中南大学硕士学位论文 第三章基于粗糙集理论的孤立点算法 ( 2 ) 机器学习方法是目前的研究重点，研究成果也比较多。大多数机器学 习方法是利用人类的认知模型模仿人类的学习方法从数据中提取知识。 ( 3 ) 仿生学方法的典型是神经网络方法和遗传算法。神经网络模拟人脑神 经元结构，以m p 和h e b b 学习规则为基础，建立了前馈式网络、反馈式网络和 自组织网络。前馈式网络用于预测及模式识别，反馈式网络擅长联想记忆和优化 计算，而自组织网络非常适合用于聚类算法的研究。遗传算法是按照自然进化原 理提出的一种优化策略。通过最好解的选择和彼此组合，可以期待解的集合将越 来越好。 2 2 孤立点算法分析 孤立点发现是数据挖掘的一个重要研究方面，被用来发现数据集中小的模式 ( 相对于聚类) ，即数据集中明显不同于其它数据的对象。孤立点的研究非常重 要，主要原因如下： ( 1 ) 它对数据分析的结果有很大的影响； ( 2 ) 虽然它通常是测量、记录错误，但有些可能代表应用领域中感兴趣的、 有意义的知识； ( 3 ) 确定孤立点经常导致发现新的知识。 孤立点的产生通常源于如下两个方面： ( 1 ) 测量数据、计算机录入错误、网络数据传输错误、人为错误等原因引 起。对这一类数据要进行删除、修改，否则会影响数据分析结果； ( 2 ) 可能是数据真实性质的反映，通常比一般数据包含的信息更有价值， 应该给予保留1 3 2 1 。例如难得一遇的气温或降雨比正常气候更有意义；不同寻常 的气候变化往往预示着某种地质灾害的发生；高血压病人的血压值高于普通人的 血压值等。 因为孤立点是一个很复杂的概念，不同的研究者给出了不同的定义。k n o r r 等把数据集o 中的孤立点描述为在o 中存在与o 的距离大于d ( d 是个具体距 离) 那一小部分数据【3 3 3 钳。然而，r a m a s w a m y 等认为，孤立点就是与所有别的数 据相比有最大距离的那些数据【3 5 1 。b r e u n i g 等认为孤立点就是在一个给定的邻域 内具有最大局部孤立因子的那些数据t 3 6 - 3 9 1 。局部孤立因子就是在一个具体的点周 围对象的距离或密度的度量。高局部孤立因子意味着与邻居很远，而低局部孤立 因子意味着于邻居更近。因此当前还没有一个被广泛接受的定义。然而h a w k i n s 给出的描述几乎成为被广泛接受的定义：“孤立点是在数据集中偏离大部分数据 的数据，使人怀疑这些数据的偏离并非由随机因数产生，而是产生于完全不同的 1 2 中南大学硕士学位论文第三章基于粗糙集理论的孤立点算法 机制 4 0 1 。后来研究者们根据对孤立点存在的不同假设，发展了很多孤立点检 测算法，大体可以分为基于统计的算法、基于距离的算法、基于密度的算法、基 于偏离的算法以及基于关联的算法等，其中基于距离的孤立点检测算法将在第三 章详细介绍。 2 2 1 基于统计的方法 从2 0 世纪8 0 年代起，孤立点检测的问题就在统计学领域得到广泛研究1 4 l j 。 基于统计的孤立点挖掘方法的思想来自于统计学方法，对给定的数据集预先假定 一个分布或概率模型，然后根据模型采用不一致性检验来确定孤立点【4 2 】。统计 方式发现孤立点主要有两种方法：第一块处理步骤，将所有的有疑问的数据对象 当作孤立点对象或正常数据对象。第二连续步骤，将最不可能是孤立点的数据对 象首先进行检验，若此数据是孤立点，其它数据当然也是孤立点将最可能是孤立 点的数据首先进行检验，若此数据不是孤立点，其它数据当然也不是孤立点。 任何统计检测不可避免地要检测数据集的工作假设和替代假设，如果没有在 统计上的显著证据支持拒绝工作假设，工作假设被保留不一致检测验证一个对 象关于工作假设分布是否显著的大或者显著的小，如果估算显著性概率是足够 的小，那么对象是不一致的，工作假设被拒绝，同时，替代假设被接受，它说明了数 据对象来自于另一个分布模型，所以该数据对象是一个孤立点。基于统计学方法 的替代模型主要有四种：确定性替代分布、固定替代分布、混合替代分布和滑动 替代分布。 由于该方法需要事先知道数据集数据模型( 例如假设的数据分布) 、分布参 数( 例如平均值和方差) 和假设的异常点的数目。因此基于统计学手段检测孤立 点的方法不可避免的含有如下的缺点： ( 1 ) 绝大多数一致性检验是针对单个属性的，而许多数据挖掘问题要求在 多维空间中发现孤立点。 ( 2 ) 统计学方法要求知道数据集参数如数据的分布、分布参数如均值、标 准差等但在实际中，数据分布往往是未知的。 ( 3 ) 统计学方法也不能确保所有的孤立点被发现，或者观察到的分布不能 合适的被任何标准的分布来模拟和表示。并且用统计学方法进行孤立点检测需要 预先知道孤立点个数，而这在实际应用中往往是难以实现的。 2 2 2 基于密度的方法 基于距离的孤立点定义是针对全局孤立点的，而现实数据集中存在一种称之 1 3 中南大学硕士学位论文第三章基于粗糙集理论的孤立点算法 为局部孤立点的概念。如图2 5 所示，o l 是一个全局孤立点，而0 2 利用基于距离 的孤立点检测算法是很难发现的。根据h a w k i n s 对孤立点的定义，0 2 对于聚类2 来说是一个与全类对象不相同的点，满足孤立点的概念。事实上，利用d b ( p ，d ) 的定义，只能发现0 1 是一个孤立点，这是因为对聚类l 中的每一个对象q ，找不到一 个合适的参数p 和d 来满足使q 最近的邻域中的对象间的距离大于0 2 和聚类2 间的 距离，从而保证0 2 是孤立点的同时又能保证聚类1 中的对象不是孤立点。该例说 明，d b ( p ，d ) 在某些特定的情况下是准确和充分的，但聚类密度如果存在不同就 会出现问题。 图2 - 5 二维数据集 b r e u n i n g 等人认为成为孤立点并不是像基于距离的孤立点挖掘概念那样仅 仅是一个二分属性，即数据对象不能仅被分成是孤立点或者不是孤立点，而是每 个对象有某个孤立度。他们认为，在许多情况下，对每个对象赋予孤立点度会更 有意义。因此，他们提出了一个新的度量方法即局部孤立因子( 1 0 c a lo u t l i e rf a c t o r ， 简称l o f ) ，并以此提出了一个新的孤立点挖掘算法。文献 3 3 】给出了一个l o f 算 法的改进算法。l o f 是孤立点挖掘算法中基于密度的方法的一个典型算法，避开 了计算绝大多数对象的l o f 。以l o f 为代表的基于密度的孤立点挖掘算法，其主 要包括下面几个步骤： ( 1 ) 对象p 的k 距离。首先通过寻找对象的k - 距离( k d i s t a n c e ( p ) ) ，来确定 对象的局部范围。这里k 为对象p 对于整个数据集中其他对象的距离最少的k 个邻居，即m i n p t s 。 ( 2 ) 遍历数据库，找到对象p 的k - 距离邻居n k 埘咖c c ( p ) ( p ) 。也就是说，以 对象p 为圆心，k 距离为半径的圆包括的数据对象都是对象p 的k - 距离邻居。所 以l 【- 距离邻居的个数总是大于等于k 的。 ( 3 ) 定义对象p 关于对象o 的可达距离r e a c h d i s t k ( p ，o ) 为： r e a c h - d i s t k ( p ，o 廓a x ( k - - d i s t a n c e ( o ) ，d ( p ，0 ) ) ( 4 ) 计算对象p 的局部可达密度： 1 4 中南大学硕士学位论文第三章基于粗糙集理论的孤立点算法 l r d u 撕2 - 磊磊1 而 堡丝苎! 竺! 出 j m 加栅( p ) i ( 5 ) 计算对象p 的局部孤立因子( l o f ) ： ( 2 2 ) 在得出每个对象的l o f 值后，可以按照l o