（管理科学与工程专业论文）高维数据集中离群数据挖掘方法的研究.pdf

高维数据集中离群数据挖掘方法的研究 摘要 离群数据的发现，往往可以使人们发现一些真实的、但又出乎意料的 知识。离群数据挖掘是数据挖掘的一个新兴课题，在实际生活中有广泛的 应用。目前，离群挖掘正逐渐成为数据库、机器学习、统计学等领域研究 人员的研究热点。 山于高维空间中数据分布特殊，所以传统的离群数掘挖掘方法不能很 好的适用于高维空间数据集。本文针对这一问题提出了一种利用粗糙集的 属性约简方法对数据集的属性进行约简以减少高维空间的维数，并在约简 生成的子空问中对数据集进行基于超图模型的离群数据挖掘的方法。研究 结果表明，对属性的约简可以节省数据存储空间，提高计算效率，而利用 超图模型可以发现约简后的数据集中的离群数据。实验结果说明了此方法 的高效性并且具有实用价值。 本文共分为六章。第一章“前言”简单介绍了数据挖掘的基本概念、 方法以及分类等。第二章“离群数据挖掘概述”是关于离群数据挖掘以及 常用的离群数据挖掘方法的介绍。第三章“粗糙集理论与数据挖掘”阐述 了羊日糙集的基本理论及其与数据挖掘的关系。在第四章“聚类分析”中。 主要是聚类方法及其与离群数据挖掘的紧密联系。第五章“基于粗糙集与 超图的高维离群数据挖掘研究”是运用粗糙集的属性约简方法和超图模型 在高维数据集中进行离群数据的发现，并描述了实验过程和实验结果。最 后一章是对全文工作的总结以及对今后研究工作的展望。 关键字：离群数据挖掘；粗糙集：聚类；超图 v r e s e a r c ho no u t l i e rd a t am i n i n gi n h i g hd i m e n s i o n a ls p a c e a b s t r a e t o u t l i e rd a t am i n i n gc a nh e l pp e o p l ed i s c o v e rt h et r u ea n du n e x p e c t e d i n f o r m a t i o n o u t l i e rd a t am i n i n gi san e wt a s ko fd a t am i n i n g ，a n di sw i d e l y u s e di n d a i l yl i f e a tp r e s e n t ，o u t l i e r d a t a m i n i n g i sa h o t s p o t f o r t h e r e s e a r c h e r so fd a t a b a s e ，m a c h i n el e a r n i n ga n ds t a t i s t i c s b e c a u s eo ft h ec h a r a c t e r i s t i co ft h ed i s t r i b u t i o nr u l eo ft h ed a t ai nh i g h d i m e n s i o ns p a c e ，t h et r a d i t i o n a lm e t h o d so fo u t l i e rd a t am i n i n gc a n tw o r k v e r yw e l l t or e s o l v et h i sp r o b l e m ，am e t h o do fo u t l i e rd a t am i n i n gi nh i g h d i m e n s i o ns p a c ei sp r e s e n t e di nt h i sp a p e r ，w h i c hu s e sr o u g hs e tt or e d u c et h e a t t r i b u t e so ft h ed a t a s e t sa n dt h e nd e t e c t so u t l i e r si nt h es u b s p a c eu s i n g h y p e r g r a p hm o d e l t h er e s e a r c ht e l l su st h a tt h er e d u c t io no ft h ea t t r i b u t e s c a ns a v et h es t o r a g es p a c ea n du s i n gh y p e r g r a p hm o d e lc a nd e t e c tt h eo u t l i e r d a t a t h er e s u l to ft h ee x p e r i m e n ts h o w st h a tt h i s - a p p r o a c hi se f f e c t i v ea n d p r a c t i c a l t h i st h e s i si sd i v i d e di n t os i xc h a p t e r s t h ef i s tc h a p t e r ，f o r e w o r d ， i n t r o d u c e st h eb a s i cc o n c e p t i o n ，m e t h o d s ，a n dc a t e g o r yo fd a t am i n i n g t h e s e c o n dc h a p t e r ，o u t l i e rd a t am i n i n g ，i sa b o u tt h eb a s i cc o n c e p t i o no fo u t l i e r d a t am i n i n ga n ds o m eo r d i n a r yo u t l i e rd a t am i n i n gm e t h o d s t h et h i r dc h a p t e r ， r o u g hs e tt h e o r ya n dd a t am i n i n g ，i n t r o d u c e st h eb a s i ct h e o r yo fr o u g hs e t a n di t sr e l a t i o n s h i pt od a t am i n i n g t h ef o u r t hc h a p t e r ，c l u s t e r i n g ，i n t r o d u c e s s o m e c l u s t e r i n g m e t h o d sa n dd i s c u s s e st h ec l o s er e l a t i o n s h i pb e t w e e n c l u s t e r i n ga n do u t l i e rd a t am i n i n g t h ef i f t hc h a p t e r ，r e s e a r c ho no u t l i e r d a t am i n i n gi nh i g hd i m e n s i o ns p a c eb a s e do nr o u g hs e ta n dh y p e r g r a p h ， p r e s e n t sa no u t l i e rd a t am i n i n gm e t h o di nh i g hd i m e n s i o nt h a tu s e sr o u g hs e t t h e o r ya n dh y p e r g r a p hm o d e l t h el a s tc h a p t e ri sac o n c l u s i o no fa l lt h ew o r k i nt h i sp a p e ra n da ne x p e c t a t i o no ff u r t h e rr e s e a r c hw o r k k e yw o r d s ：o u t l i e rd a t am i n i n g ；r o u g hs e t ；c l u s t e r i n g ；h y p e r g r a p h v 1 插图目录 幽2 i 离群数据示意剀 幽3 1 上近似、r 近似示意幽 蹦5 1 超边、顶点和聚类关系酗 幽5 2 超图分割过程 幽5 3 实验结果 i x 1 2 1 5 3 7 3 8 3 9 致谢 首先，我要向我的导师倪恋伟教授表示由衷的感激之情。倪老师那渊博 的学 = 5 、富于创新的精神、敏捷的思维能力、实事求是的治学态度以及豁达 的胸怀、执着的人生信念、宽以待人的品质都深深地影响着我，使学生叹服， 且终生受益。正是他那敏捷的思维、宽广的知识和对问题的透彻理解和分析， 使我得以在学术和技术等方面不断成长。本硕士论文是在倪老师的悉心指导 下完成的，从选题、研究方法到实验结果分析论证等各个环节，他都准确地 把握了方向。倪老师不仅在学术上对我精心培养，严格要求，而且在生活上 给予了我热心和无私的关怀。在本文完成之际，谨向尊敬的导师再次致以最 诚挚的谢意! 感谢您三年来对学生的辛勤栽培。 我要衷心感谢李锋刚博士生，黄玲博士生，李建洋博士生，以及我的同 学张威硕士生，许梁海硕士生，赖大荣硕士生，刘玉硕士生，何夏青硕士生。 在学习和撰写论文的过程中，他们或者提供了宝贵的资料，或者一起参与了 探讨，使我受益匪浅。 我还要感谢合肥工业大学管理学院2 0 0 ：3 级研究生2 6 班的全体同学。 他们在近三年的学习和生活中给了我帮助和鼓励。 感谢我的家人，谢谢你们的关心、理解和大力支持! 作者：蔡博文 2 0 0 6 年5 月 1 1 数据挖掘研究背景 第一章前言 随着社会的发展，数据量急剧膨胀，数据的时效性和复杂性远远超过了当 前的信息处理能力。信息化和全球化是二十一世纪的最大特征，在网络技术的 推动下，近十几年柬，人们生产和搜集数据的能力大幅度地提高，而数据获得 和生产能力大大超过数据处理的能力。现今，由于数据生产、传输能力与数据 分析能力的不平衡，人们被数据淹没，寻找隐藏在其中的有用信息无异于大海 捞针。人们希望能够提供高层次的数据分析功能，自动和智能地在待处理的数 据中寻找和发现有用的信息知识。数据挖掘和知识发现( d a t am i n i n ga n d k n o w l e d g ed i s c o v e r y ) 技术也因此应运而生，并蓬勃发展，越来越显示出强大 的生命力。 1 1 1 数据挖掘介绍 什么是数据挖掘? 数据挖掘( d a t a m i n i n g ) 就是从大量的、不完全的、有 噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但 又是潜在有用的信息和知识的过程“ 2 1 。 数据挖掘是揭示存在于数据里的模式及数据间的关系的学科，它强调对大 量观测到的数据库的处理。它是涉及数据库管理，人工智能，机器学习，模式 识别及数据可视化等学科的边缘学科。 数据挖掘是可以从大量数据中挖掘出隐含的、先前未知的、对决策有潜在 价值的知识和规则的高级处理过程【3 l 。通过数据挖掘，有价值的知识、规则或 高层次的信息就能从数据库的相关数据集合中抽取出来，并从不同角度显示， 从而使大型数据库作为个丰富、可靠的资源为知识的提取服务。 1 l2 数据挖掘与知识发现 知识发现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 ) 的定义为：k d d 是 从数掘中辨别有效的、新颖的、潜在有用的、最终可理解的模式的过程i u 。 k d d 一词首次出现在1 9 8 9 年8 月举行的第l l 届国际联合人工智能学 术会议上。到目前为止，由美国人工智能协会( a a a i ) 主办的k d d 国际研讨 会的规模由原来的专题讨论会发展到国际学术大会，研究重点也逐渐从发现方 法转向系统应用，注重多种发现策略和技术的集成，以及多种学科之间的相互 渗透。 知识发现过程主要包括以下步骤【2 】： 数据清理( 消除噪声或不一致数据，以免影响分析结果) ： 数据集成( 将多种数据源组合在一起) ： 数据选择( 在数据集中搜寻与分析任务相关的数据) ； 数据变换( 将数据源统一成适合挖掘的形式，如离散化、汇总或聚集等 操作) ； 数据挖掘( 核心步骤，使用智能方法提取数据模式) ： 模式评估( 根据某种兴趣度度量，识别表示知识的真正有趣的模式) ； 知识表示( 使用可视化和知识表示技术，向用户提供挖掘的知识) 。 数掘库中的知识发现，是从数据中发现有效的、潜在的、有用的、可理解 的结构，数据指的是数据库中的数据，结构指的是模型。数据挖掘是k d d 的核 心步骤，指的是人们可以接受的计算效率的极限，列出数据的模型。挖掘出的 模型可能比记录本身还多，为了获得可用知识，要给出一些模型的选择标准。 “有用的”和“有效的”是指通过更好的预测方法，使人们获得更大效益。对 “确定性”的数量表示，可以通过“准确率”等表示。“可理解的”可以是被 认为是简单化的模式，“兴趣度”是“新奇性”数据量化表示，“兴趣度”可 以在挖掘前进行定义，通过挖掘后对结果进行验证，如果结果不能令人满意， 可以重新定义“兴趣度”。 由此可见，k d d 过程是一个以知识使用者为中心、人机交互的探索过程。 数据挖掘只是数据库中知识发现的一个步骤，但又是最重要的一步。因此，往 往可以不加区别地使用k d d 和数据挖掘。一般在研究领域被称作数据库中知 识发现的，在工程领域则称之为数据挖掘。 1 2 数据挖掘的分类、方法与应用 1 2 1 数据挖掘的分类 从不同角度看，数据挖掘技术有如下几种分类方法：根据挖掘的数据库的 种类进行分类、根据发现知识的种类进行分类和根据采用的技术进行分类。 ( 1 ) 根据挖掘的数据库的种类进行分类，数据库系统本身就有多个划分标 准，这些数据库系统均与各自的数据挖掘技术相对应。因此数据挖掘系统可以 按照数掘库系统的类型来划分，如有关系类型、事务类型、面向对象类型和数 据仓库类型等；若按照所处理的数据类型来划分，就会有空间数据类型、时序 数据类型、异质数据类型、文本类型和多媒体类型等。 ( 2 ) 根据发现知识的种类进行分类，数据挖掘主要发现以下几类知识【l t 3 】： 广义型知识( g e n e r a l i z a t i o n ) ：根据数据的微观特性发现的带有普遍性、 较高层次概念的知识。 分类知识( c l a s s i f i c a t i o n ) ：反映同类数据间共同性的知识和不同类数据 问差异性的知识。 聚类知识( c l u s t e r i n g ) ：指根据事物的属性对未分类的数据进行类别识别 的过程。 关联型知识( a s s o c i a t i o n ) ：反映一个事物和另一个事物问的关联关系的 知识。 序贯模式( s e q u e n t i a lp a t t e r n s ) ：指在多个数据序列中发现数据共同的行 为模式。 预测型知识( p r e d i c t i o n ) ：通过时间序列数据，由历史数据预测未来情况。 偏差型知识( d e v i a t i o n ) ：通过分析数据聚类外的离群点，对差异特例进 行描述。 所有这些知识都可以在不同的概念层次上被发现，随着概念树的提升，从 微观到中观再到宏观，以满足不同用户、不同层次决策的需要。 ( 3 ) 根据采用的技术进行分类，最常采用的数据挖掘技术可分为【2 j ：决策 树，人工神经网络，遗传算法，贝叶斯信任网络，最近邻技术，统计分析，机 器学习方法，粗糙集方法，数据库方法。 1 2 2 数据挖掘的方法 数据挖掘方法可以分为【0 2 】： 1 ) 统计方法：统计学方法可用于对数据的建模。统计方法可细分为：回 归分析、判别分析、聚类分析、探索性分析等。其中回归分析方法是用一组独 立变量和常量来估计一个因变量，主要有线性回归模型、非线性回归模型和非 线性多重回归模型。统计方法可用于分类、聚类和预测等应用。 2 ) 机器学习方法：机器学习法的核心问题是从特殊的训练样本中归纳出 通用函数。机器学习方法可用于分类、聚类和预测等应用。 机器学习可细分为：归纳学习方法、基于范例学习、遗传算法等。 3 ) 神经网络方法：它从结构上模仿生物的神经网络，是一种通过训练数 据集来学习的非线性预测模型。神经网络方法可以用于分类、聚类、特征挖掘 等多种应用。 神经网络方法可细分为：前向神经网络、自组织神经网络等。 4 ) 数据库方法：主要是多维数据分析或联机分析方法，另外还有面向属 性的归纳方法。 5 ) 粗糙集方法：粗糙集理论是一种研究模糊、不完整、不确定知识和数 据的表达、学习、归纳的理论方法，主要用于分类挖掘，数据约简等应用。 6 ) 决策树方法：是一种用树形结构来表示决策集合的方法。其中决策集 合通过对数据集进行分类来产生规则。主要的决策树方法有i d 3 、c 4 5 、c 5 0 和 c a r t 。 7 ) 贝叶斯网络：也称为因果网络、概率网络、影响图和认知图。它将不 确定事件以网络的形式相互连接起来，通过这种关系网络人们可以对某一与其 它事件有关的事件的结果进行预测。 8 ) 最近邻技术：通过k 个与选定记录最相近的历史纪录的组合来辨别新 的记录。最近邻技术主要应用于聚类分析、偏差分析等。 在当前的数据挖掘软件包中被用到的分析过程包括：决策树推断、规则推 断、最近邻方法、聚类方法、联合规则、特征提取、可视化。另外，有些还包 括：神经网络、图形模型、遗传算法、自组织图、神经模糊系统。 l i2 3 数据挖掘的应用 数据挖掘的目的是：提高市场决策能力；检测异常模式；在过去的经验基 础上预言未来趋势等。它不仅能用于控制成本，更重要的是能给企业带来效益。 很多企业都在利用数据挖掘技术帮助管理客户生命周期的各个阶段，包括 争取新的客户、在已有客户的身上赚更多的钱、和保持住好的客户。如果能够 确定好的客户的特点( 如性别、年龄、职业等) ，那么就能为客户提供针对性 的服务。比如，已经发现了购买某一商品的客户的特征，那么就可以向那些具 有这些特征但还没有购买此商品的客户推销这个商品：找到流失的客户的特征 就可以在那些具有相似特征的客户还未流失之前采取针对性的弥补措施，因为 保留一个客户要比争取一个客户便宜的多，也更容易。 数据挖掘技术可以应用在很多不同的领域。电信公司和信用卡公司是用数 据挖掘技术来检测欺诈行为的先行者。保险业也开始用数据挖掘技术来减少欺 诈。在医疗领域中，数据挖掘技术可以用来预测外科手术、医疗试验和药物治 疗的效果。制药公司通过挖掘化学物质和基因对疾病的影响的数据库来判断哪 些物质可能对治疗某种疾病产生效果。零售商更多的使用数据挖掘技术来解决 每种商品在不同地点的库存，了解消费者的消费模式，通过数据挖掘更灵活的 使用促销和优惠券手段。 当前，在电信领域中数据挖掘技术的贡献有：电信数据的多维分析；欺诈 模式分析与非正常模式的确定与辨别；关联规则及序列模式的分析。数据挖掘 在会融领域中的应用有：设计和建立数据仓库，并进行多维数据分析与数据挖 掘；贷款还贷预测以及客户的信用分析；目标市场客户的聚类与分类；金融犯 罪行为的发现。在商业中的应用：基于商业数据的数据仓库的建立：销售、信 息、客户、产品、时间和区域的多维分析；商业促销行为分析；客户忠诚度分 析：相关产品推荐。 由于数据挖掘技术的良好的应用前景，各大软件公司及大学研究机构对此 开展了研究。一批数据挖掘系统被开发出来，其中比较有代表性的有： 1 ) i b m 公司的i n t e l l i g e n tm i n e r ，它提供了较全面的数据挖掘算法，良好的 4 算法伸缩性，并可以和d b 2 集成在一起使用。 2 ) s a s 公司的s a se n t e r p r i s em i n e r ，它包括回归、分类、统计分析，其特 点是有较强的统计分析功能。 3 ) i s ld e c i s i o s y s t e m s 公司的c l e m e n t i n e ，它的挖掘算法包括规则归纳、 神经网络、分类及可视化工县。 其它产品还有t a n d e m 的r e l a t i o n a ld a t am i n e r ，a n g o s ss o f t w a r e 的 k n o w l e d g es e e d e r 等等。除了这些综合软件包外，还有许多专门用途的产品。 另外，许多专业于数据挖掘的咨询公司也成立了。 1 3 离群数据挖掘研究背景 一般来说，数据挖掘可以分成四类：相关、依赖关系的发现：类别的判定； 类别的描述：离群数据挖掘。数据挖掘的大部分研究主要是针对前3 类形式的挖 掘，而对于离群数据挖掘的研究则相对较少。 离群数据挖掘是数据挖掘的一个新的热点。离群数据是指数据集中与其它 数掘很不相似或很不一致的数据，它可能是由于人为错误或机器错误造成的噪 声数据，但也可能是事物本质的体现。对于噪声数据，我们要进行清除，以免 影响数据挖掘的结果。而对于蕴涵有真实知识的离群数据，如果我们找出它们 并进行分析，往往能得到意想不到的知识。 离群数据挖掘已经在会融，网络安全、电信、零售、医疗卫生、天文物理 等行业和领域得到了应用，并且效果较好。离群数据挖掘最早在统计领域得到 研究，随后又发展出基于距离的方法，基于偏离的方法，基于规则的方法，基 于聚类的方法等离群数据挖掘方法。离群数据挖掘是本文的重点研究内容之一， 我们将在后续章节中详细讨论这些方法。 1 4 本文组织及内容安排 本文主要的研究工作是高维空间下离群数据的发现。在实际研究中，我们 发现高维数据的特性与低维数据有很大的不同。主要表现在高维空间中的数据 分布得比较稀疏。这样就使得高维空间中数据之间的距离尺度及区域密度不再 具有直观的意义。从单个数据点来看，其他点到它的距离落在一很小的区间内， 很难给出一个合适的近似阈值来确定哪些点是与它相似的，而哪些不是。因此 传统的离群数据挖掘方法不能很好的适用于高维空间数据集。本文针对这一问 题试图用粗糙集理论和超图的理论来解决高维空间的离群数据挖掘问题。 本文的第一部分先是介绍了数据挖掘的基本概念、方法以及分类等。接着 概述了离群数据挖掘的意义，离群数据挖掘是近来数据挖掘的新热点，也是本 文的只要研究内容之，在本文中我们详细讨论了几种常用的离群数据挖掘方 法。 本文的第二部分是关于粗糙集理论和聚类分析的讨论。这部分首先阐述了 粗糙集的基本理论，粗糙集理论是近期内受到广泛重视的分类理论。它对数据 的分类只依赖于数据集合本身，而不引进其他的数据模型上的假设。粗糙集理 论对数掘的认识是基于数据对象的等价类的，等价类内部的信息原则上被忽 略。粗糙集理论在处理小样本、大空间的分类问题上具有满意效果。本文在后 面将对l 卡r 糙集理论以及它子数据挖掘的关系进行研究。然后介绍了聚类分析以 及若干聚类分析方法，聚类分析是数据挖掘的一个重要手段，由于聚类方法的 特点，使得它与离群数据挖掘有着紧密的联系，本文也使用了一种超图聚类算 法来进行离群数据挖掘。 本文的第三部分提出了一种基于粗糙集与超图的高维离群数据挖掘方法。 超图是对图的一种扩展，其中的每条边可以连接两个或两个以上的顶点。超图 理论已经被较多的用于对高维空间数据集的聚类。本文将使用超图聚类算法中 的超图分割法h m e t i s 来实现高维空间的离群数据挖掘，并描述了实验过程和实 验结果。在论文最后我们对令后研究工作进行了展望。 6 第二章离群数据挖掘概述 数据挖掘是一个从大量的数据中发现潜在知识的过程。一般来说，它可以 分成四类：相关、依赖关系的发现；类别的判定；类别的描述；离群数据的挖 掘( o u t l i e rd a t am i n i n g ) 。通常人们都关注数据库中绝大部分数据所表现的 特征，其中包括关联规则、分类、聚类，而忽视了离群数据的存在和意义，现 有的方法往往研究如何减少离群数据对正常数据的影响，或仅仅把其当作噪声 来处理。 2 1 离群数据的定义 离群数据( 或离群点) 是指明显偏离其他数据，不满足数据的般模式或 行为，与存在的其它数据不一致的数据【4 。 从上述的定义来看，离群数据听起来是令人讨厌的东西，它的存在会影响 数掘分析，应该马上识别出来并剔除掉。然而，这种观点是片面的，离群数据 也可能包含有用的信息。离群数据通常来源于测量错误、计算机录入错误、人 为错误等，这些数据是要被修改或者删除的，否则会影响分析结果。但是，“一 个人的噪声可能是另一个人的信号”，事实上，在一些应用实例中，稀有事件 比普通事件更有研究价值。例如，在门禁系统中，通常进入的都是有权限进入 的些人，而当发现陌生人时，就应该予以阻止或发出警告。这些陌生人就可 以看作是数据库中的离群数据。再如，一个公司的首席执行官的工资收入自然 远远高于其他雇员的工资成为一个离群数据，含油区域的重力加速度p 的值低 于非含油区域，在地震前夕，地下水中的氡等惰性元素含量的异常升高等。因 此，离群数据的发现，往往可以使人们发现一些真实的，但又出乎意料的知识。 在电信计费数据、银行信用卡数据、贷款审批、药物研究、医疗保险等各种数 据中普遍存在着各种欺诈数据。通过对离群数据的研究，发现不正常的行为和 模式，有着非常重要的意义。 2 2 离群数据挖掘的定义 离群点检测可以描述如下：给定一个由个数据点或对象构成的集合，及 预期的离群点的数目，发现与剩余的数据相比是显著相异的、异常的或不一致 的头t 个对象。 在离群数据挖掘中，关键是解决两个核心问题一是如何有效和准确的从大 数据集中发现和搜寻离群数据；二是对发现的离群数据进一步判断是正常数据 ( 异常) 还是错误数据( 噪音) 。 目前，离群数据的挖掘越来越引起数据库、机器学习、统计学等学者的兴 趣，工f 成为数据挖掘和应用领域的研究热点。 2 3 离群数据挖掘的重要方法 离群数据的发现方法主要有以下几种：基于统计学的方法，已知数据集符 合某种概率分布，然后用不一致性检验来确定离群数据，这种检验需要知道数 据的分布，分布的参数等；基于距离的方法【5 6 】，基于距离的离群数据可以表示 为d b ( p ，a 3 ，利用这种方法需要确定合适的参数p ，d ：基于偏离的方法，它通 过数据中某项记录的去除而对整个数据的影响及变化束确定离群数据的存在； 基于规则的方法f7 , 8 , 9 】，利用数据挖掘的方法，如关联规则挖掘，首先确定样本 集的几条规则，然后利用规则来检验出离群数据。另外，还有基于聚类的方法 等一些其它的方法，下面对这些方法做一下简单介绍。 2 3 1 基于统计的离群数据的发现方法 离群点检测的问题最早在统计领域得到研究，用户必须给出数据点的统计 分稚形式。然后按照假定的分布函数采用不一致性检验来确定哪些是离群点。 这种检验需要知道数据集参数( 如数据的分布) 、分布参数( 如均值、标准差 等) 和离群数据个数。 不一致检验一般包含两个假设：零假设h o 和对立假设h 1 。h o 是一个命题， 认为数据有同一分布模型f ，即h o ：o i f ，f = l ，2 ，n 。如果没有统计上的 显著证据来拒绝这个假设，那么就接受h o 。不一致性检验验证o 与分布f 的 数掘相比是否差异显著。依据不同的数据先验知识，不同的统计量可以被提出 来用作不一致性检验。设统计量选定为r ，对象o i 的统计量为v i ，构造分布r ， 计算统计显著性s p ( v 。) = p r o b ( t ，v 。) 。如果某个即( v f ) 足够小，检验结果不是统计 显著的，拒绝零假设h o 。对立假设h l 被采用，它描述总体性质的另外一种想 法，认为o i 来自于另外的分布模型j 。既然0 i 可能在一个模型下是离群数据， 在另一个模型下是非常有效的值，那么结果非常依赖于模型的选择。由此说明 对立假设是非常重要的，它决定了检验的准确性，它有以下几种形式1 9 】： 1 ) 内在对立分布：在内在对立分布中，零假设被拒绝，所有数据对象来自 另一个分布厂的对立假设成立：h 1 ：o j ，户1 ，2 ，h 。f 和j 可能 是不同的分布，或者是参数不同的同一分布。对，分布的形式有所约束 以便它有产生离群数据的可能性。 2 ) 混合对立分布：混合对立分布假设认为不一致的数据对象不是离群数 据但被来自其他分布的数据所污染，这种情况下的对立假设是 h 1 ：0 ( 1 一五) r + 无，f = l ，2 ，刀。 3 ) 滑动对立分布：滑动对立假设认为所有数据对象( 除较少分布外) 独立 来自初始分布f ，剩余数据对象独立来自修改后的分布f ( 参数有所变 化) 。 基于统计学手段检测离群数据的主要缺点是大多数检验是针对单个属性的，而许 多数掘挖掘问题要求在多维空间中发现离群数据。而且，统计学方法要求知道关于数 据集参数的知识，如数据分布。但在实际中，数据分布往往是未知的。统计学方法也 不能确保所有的离群点被发现，或者观察到的分布不能合适的被任何标准的分布来模 拟和表示。并且用统计学方法进行离群点检测需要预先知道离群点个数，而这在实际 应用中往往是难以实现的。 2 3 2 基于距离的离群数据的发现方法 给定数据集t ，t = ( t t ，t 2 ，。 ，o 为数据对象，肛 5 l ，s 2 ，s 口) 且s s t ( 其 中p ”) ，若s 中的对象都远离于o 的距离为d 的领域( 即l i o s ，i i d ) ，则称 o 为基于距离的离群数据，表示为d b ( p ，田。 基于距离的离群数据检测避免了过多的计算。下面介绍几个基于距离的离 群点检测方法 9 】： 1 ) 基于索引的算法：给定一个数据集合，基于索引的算法采用多维索引结 构( 如r 树，k - d 树等) 来查找每个对象d 在半径d 内的邻居。设m 为离群数 据o 的d 领域的最大取值个数。因此，一旦对象o 的第m + 1 个邻居被发现，那 么o 就不是离群数据。此算法在最坏的情况下的计算复杂度为o ( k 2 ) ，k 是维 数，即是数据集中对象的数目。计算复杂度没有考虑建立索引所需要的时间。 2 ) 嵌套一循环算法：此算法和基于索引的算法有相同的计算复杂度，但它 不用建立索引结构，以此来最小化输入输出的次数，提高算法效率。它把内存 的缓冲区域分为两半，把数据集分为若干块。然后以数据块为单位选择装入每 个内存缓冲区，相比于基于索引的算法中对对象逐个进行计算，输入输出效率 有所改善。 3 ) 第k 个最近邻居法：其主要思想是，离群数据总是远离大部分的正常数 据。设数据集7 1 ，| 为数据对象个数，对象0 为离群数据，其以d 为领域包含 数掘对象q ，q t f ( o ，q ) d ，f ( o ，口) 是距离函数，0 的d 领域范围内对象个 数最大为k 个，k = ( 1 - q ) + n ，p = ( 1 一口) 部分数据对象个数远大于k 。 第k 个最近邻居法比基于单元的算法有更好的准确性。但如果离群数据较 多，计算时间增加，而且距离函数的选取非常重要，可以选取欧氏距离，也可 9 以根据挖掘数据的目标，将所感兴趣的属性值加权。 4 1 基于单元的算法：此方法是为了避免o ( n 2 ) 的计算复杂度，它的复杂度 是o ( c + ) ，其中c 是常数，取决于单元的数目，k 是维数。在该方法中，数据 空i n j 被划分为边长等于d 2 i 的单元。每个单元有两个层面围绕着它，第一层 面的厚度是一个单元，而第二层的厚度是【2 x k 一1 】个单元( 进行取整) 。该算法 逐个单元的对离群数据计数，而不是逐个对象的进行计数。对一个给定的单元， 它累计三个计数一一单元中的对象的数目，单元和第一层中对象的数目，单元 和两个层次中的对象的数目。用c ，来标注行为z ，列为y 的单元，单元的第一 层领域记为i ：厶( e ，) = e ，1 “= x + l ，v = y + l ，e ，e ，) ，单元的第二层领域记 为2 ：三2 ( e 。) = q ，| ”= z 3 ，v = y 士3 ，g ，氍厶( e ，a g ，。e ， 。 2 3 3 基于偏离的离群数据的发现方法 基于偏离的离群数据检测没有利用统计方法或基于距离的方法来识别离群 对象，而是通过对一组对象的特征进行检查来识别异常数据。基于偏离的离群 数据的检测是模仿人类的思维方式，在观察一个连续的序列后，即使不清楚数 据的规则，也能快速发现其中一项数据与其他数据明显不同。已知月条记录的 数据集，可以建立数据子集：s - ，& ，品，由此求出子集间的偏离程度。该方 法引入了下列关键概念： 异常数据对象集：它是离群数据或偏离点的集合，所以也称为偏离或者离 群数据集，这些对象的去除可以导致其它数据的相异度的最大减少。 相异函数：对于给定的数据集，如果数据集中两个对象相似，相异函数返 回值较小，反之，则相异函数返回值较大；一个数据子集的计算依赖于前个子 集的计算。 基数函数：一般是给定数据集合中数据对象的个数。 平滑系数：也称平滑因子，它是从原始数据集中去除子集，相异度减小的 量度，该值由集合的势依比例决定。平滑系数最大的子集是异常数据集。 为了减轻输入顺序对结果的可能影响，在实际应用中以上处理过程可以被 重复若干次，每一次采用子集的一个不同的随机顺序。 2 3 4 基于规则的离群数据的发现方法 基于规则的离群数据发现方法1 8 1 是用来在分类数据中进行离群数据挖掘 的。定义条件项c 为数据对象的属性、属性值组成的合取形式。如果对象集合 中有s 的值支持c ，则条件项c 的支持度为s 。如果条件项c 的支持度小于某 一阙值( 最大离群支持度) ，则称c 为离群条件项，所有这些离群条件项的集 合g 。称为离群条件项集，数据对象中与之相对应的数据就是离群数据。 用此种方法发现离群数据可以看作树的搜索问题，根节点为空条件集，第 一层节点由长度为1 的条件项集组成，计算某一条件项的支持度，产生包含此 节点且长度为2 的所有条件项为第二层子节点。其它层叶子节点的产生方法依 次类推。这种算法的计算复杂度与每一层节点的个数，节点的层数有关，设k 为所有最感兴趣节点的个数聆为层数，其计算复杂度为o ( k + r ) 。k 的数量与 数据集的属性个数，每一个属性的值域有关，k 的数量还与数据集本身的特性 ( 如数据的分布) ，以及最大支持度的选取有关。 运用此方法时，应根据数据的特性选取多层最大离群支持度，随层数增加， 最大离群支持度减小；属性的值域范围大，易发现离群数据，属性间有逻辑关 系的数据，更容易发现数据间的逻辑错误。 当数据集中错误过多时，错误数据从规则上并不明显偏离其他数据，不符 合基于规则的离群数据的定义，基于规则的分类数据离群数据挖掘算法无法发 现这一类错误数据。 2 3 5 基于聚类算法的离群数据发现方法 该方法的优点是不需要关于样本数据集的知识。基于聚类算法的离群数据 挖掘的基本思想是首先对样本数据进行聚类操作，然后检测无法归类的孤立 点，这些孤立点就是离群数据。 基于聚类算法的离群数据挖掘可分解成三个问题： 1 ) 用聚类算法( 如基于蚁群的聚类算法) 进行聚类操作，确定类别特征： 2 ) 离群数据的确定：根据离群数据的定义并结合具体的对象，确定离群数 据的度量标准： 3 ) 检测离群数据。 幽2 1 离群数据示意图 例如，在图2 1 中，对数据集( d a t as e t ) 聚类得到三个簇：c ”c 2 、c 3 ， 并检测到两个无法归类的数据点，这两个数据点就是离群数据。 在这旱，我们用蚁群聚类算法，用距离度量法作为离群度量标准。若d i 是 离群数据，当且仅当满足条件： d 2 i i o , 一c 川q ， 其中石，是聚类中心，q 是预先给定的离群数据的度量标准。 在定义了上述的离群数据标准后，就可以进行离群数据挖掘了。下面是离 群数据挖掘的具体步骤： 第一步：利用蚁群聚类算法，确定数据集的分类： 第二步：计算每个点d i 与所有聚类中心的距离d 。 第三步：若满足d = l l o , 一弓忙q ，则可以确定o i 为离群数据a 2 3 6 基于相似系数的离群数据发现方法 该方法将待数据对象以及其属性以矩阵形式表示，计算此矩阵中各元素两 两之间的相似系数，并将得到的相似系数构成相似系数矩阵，将相似系数矩阵 的各行元素求和，所得结果越小则是离群数据的可能越大。设定某一闽值，大 于该阈值的数据可以认为是离群数据【l0 1 。此方法思想易懂，对于多目标决策和 综合评价分析中离群数据的发现比较有效。但缺点也很明显，就是建立相似系 1 2 数矩阵和求和需要进行大量计算，处理大量数据时效率下降明显。 2 4 离群数据分析 离群数掘挖掘主要包括离群数据检测和离群数据分析两部分。离群数据分 析是对检测得到的离群数掘进行进一步的分析，得出有用的结论或规则。所以 说离群数据检测出来还不是最终目的，重要的是分析这些离群数据产生的原因 及其中隐含的知识。 因此，在检测出离群数据后，还要进行以下工作：确认该数据是否确实是 离群数据：分析离群数据产生的原因；对离群数据进行分析，判断其中是否存 在潜在的有用的知识。 通过离群数据挖掘算法发现的离群数据与普通数据相比有几个明显特点。 一是距离上很稀疏。因为无论是基于距离的离群数据发现方法还是基于偏离的 离群数据发现方法，离群数据之间的距离一般都会远远大于正常数据间的距 离，所以不能继续使用基于距离的度量方法：二是数量少。离群数据一般都是 小样本，所以数量较少；三是一般会有属性异常现象。对大多数离群数据来说， 产生离群的主要原因是某些属性值的异常。 在离群数据分析方法中有一种基于频繁属性的子空间法：设 0 = a 。，a ：，4 0 = ( 0 ，啦，o n 是离群数据集，0 j 是具有，个属性 a l ，a ：，4 的数据点。首先在属性集中寻找频繁属性，然后根据对属性频率的统计排序， 确定属性子空间为频繁属性子空间，最后在确定的频繁属性子空间中用关联规 则分析法，或特征化分析法等方法进行常规的知识发现。 2 5 本章小结 离群数据挖掘是一个新兴的研究课题，它是数据挖掘的重要组成部分，它 已经被广泛的应用于科学研究，如金融欺诈、电信计费、医疗保险、网络安全 等。本章先给出了离群数据的定义，然后介绍了几种常用的离群数据挖掘方法。 由于离群数据挖掘包含了离群数据的发现和离群数据分析两个部分，本章随后 对离群数据再挖掘进行了介绍。本文也提出了一种基于粗糙集与超图的离群数 据挖掘方法，将在后面的章节中详细说明。 第三章粗糙集理论与数据挖掘 粗糙集理论是一种研究模糊和不确定性知识的数学工具，由波兰科学家z p a w l a k 在1 9 8 2 年首先提出1 1 ”。其主要思想就是在保持分类能力不变的前提下， 通过知识约简，导出问题的决策或分类规则。知识工程研究中，一直存在着信 息的含糊性等问题。人工智能的基础理论之一一经典逻辑不足以解决这些不确 定性问题。为此，人们提出了一些解决方法，包括统计方法、模糊集理论等， 但这些方法都有一些内在缺陷或限定范围。例如，基于统计的方法在理论上还 令人难以信服，而模糊集方法则存在一个本质问题即如何确定成员隶属度。相 比之下，粗糙集方法则有几个优点【 2 1 ：不需要预先知道的额外信息，如统计中 要求的先验概率和模糊集中要求的隶属度；算法简单、易于操作。 下面给出粗糙集理论的一些重要概念和定义。 3 1 粗糙集的基本理论 半日糙集的研究主要基于分类【13 1 。分类和概念( c o n c e p t ) 同义，一种类别对 应于一个概念( 类别一般表示为外延即集合，而概念常以内涵的形式表示如规 则描述) 。知识由概念组成，如果某知识中含有不精确概念，则该知以不精确 m l 5 1 。 3 1 1 信息系统 粗糙集把客观对象抽象为一个信息系统，也称属性一值系统【16 1 。一个信息 系统s 是一个二元组s = 。其中，u 是对象( 或事例) 的有限集合，泸 x 1 ， x 2 x 。 ；a 是属性的有限集合，a = a j ，a ，口。 。任何属性口4 是一个信息 函数a ：u - + 圪，其中圪是a 的取值集。对于任何属性集b a ，b = 6 l ，巩) 也是一个信息函数b ：u 斗，其中= k ，x k 。 3 1 2 近似空间 近似空间【1 7j 是一个二元组d = ，u 同上，；u r 表示r 中所有等 价类的集合，或称u 的分类，也可称为不可分关系，记为f 挖吠胄) ；m r 表示r 中包含z 的等价类( e q u i v a l e n c ec l a s s ) ：r 中的等价类称为基本集( e l e m e n t a r y s e t s ) ：基本集的有限并集称为可定义集( d e f i n a b l es e t ) ，或称合成集( c o m p o s e d s e t ) 。 上，下近似与边界的概念是粗糙集理论中最重要的概念，设x 是己，的子集 ( 即x 量u ) ，则x 可用可定义集的术语从d 中定义： 1 4 d 中包含在x 中的最大可定义集称为d 中x 的下近似( 1 0 w e r a p p r o x i m a t i o n ) ，记为： _ e 3 c = x e u i x k x ， 也可表示为： _ r x = u l y u 尺f l ，j 。 d 中包含x 的最小可定义集称为d 中x 的上近似( u p p e r a p p r o x i m a t i o n ) ， 记为：取= 缸uj 【工 月n x o ，也可表示为： 麟= u ( y u r f ，n x a ) 。 在图3 1 中，曲线包围的部分是集合，x 的上近似和下近似如图中所示。 塑广 l