作者：赵旭俊
出版社：电子工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
数据挖掘方法及天体光谱挖掘技术试读：
数据挖掘方法及天体光谱挖掘技术赵旭俊 著内容简介数据挖掘是一门面向应用的新兴学科分支，涉及人工智能、机器学习、模式识别、统计学、数据库、可视化等多个学科领域，其主要目的是从大量原始数据中提取人们感兴趣的、隐含的、尚未被发现的信息和知识，目前已广泛应用于科学、工程、商业、医学等领域。
本书适合从事天文学研究、数据挖掘及知识发现和人工智能等领域的技术人员阅读，也可以作为高等院校天文学、计算机科学与技术等学科的高年级本科生及研究生的学习参考书。未经许可，不得以任何方式复制或抄袭本书之部分或全部内容。版权所有，侵权必究。图书在版编目（CIP）数据数据挖掘方法及天体光谱挖掘技术/赵旭俊著. —北京：电子工业出版社，2013.6ISBN 978-7-121-20532-3Ⅰ．①数… Ⅱ．①赵… Ⅲ．①数据采集－研究 Ⅳ．①TP274中国版本图书馆CIP数据核字（2013）第111696号策划编辑：赵 娜责任编辑：谭丽莎印 刷：三河市鑫金马印装有限公司装 订：三河市鑫金马印装有限公司出版发行：电子工业出版社 北京市海淀区万寿路173信箱 邮编 100036开 本：787×980 1/16 印张：11.75 字数：240千字印 次：2013年6月第1次印刷定 价：39.80元
凡所购买电子工业出版社图书有缺损问题，请向购买书店调换。若书店售缺，请与本社发行部联系，联系及邮购电话：（010）88254888。
质量投诉请发邮件至zlts@phei.com.cn，盗版侵权举报请发邮件至dbqq@phei.com.cn。
服务热线：（010）88258888。前 言
随着LAMOST望远镜的正式投入使用，获取的光谱急剧增多。据统计，每晚将有2万～4万条光谱需要进行自动分类识别及参数测量，如何快速、准确地处理海量天体光谱成为瓶颈。数据挖掘是一门面向应用的新兴学科分支，涉及人工智能、机器学习、模式识别、统计学、数据库、可视化等多个学科领域，其主要目的是从大量原始数据中提取人们感兴趣的、隐含的、尚未被发现的信息和知识，目前已广泛应用于科学、工程、商业、医学等领域。因此，采用数据挖掘作为天体光谱数据的分析方法是可行的、有价值的。
本书是作者近年来科研成果的总结。全书共5章，在绪论之后，全书可以分为以下3部分。（1）关联规则挖掘方法及应用，包括第2章。这一部分提出了基于准频繁项目集的关联规则挖掘、基于背景知识的关联规则挖掘、约束FP-tree及其构造方法、基于信息熵的加权频繁模式树构造共4个算法，用来解决关联规则挖掘中效率较低、扫描数据库次数较多、背景知识无法直接给出等问题。同时，将这几个算法用在天体光谱的数据处理中，实现了天体光谱属性之间的相关性分析，为探索新的天体规律提供了技术支持。（2）离群数据挖掘方法及应用，包括第3章。这一部分提出了基于距离支持度的离群数据挖掘、基于分阶段模糊聚类的离群数据挖掘、基于信息熵的离群数据挖掘、基于特征属性子空间的离群数据挖掘共4种算法，从而提高了离群挖掘的效率及准确率，同时实现了天体光谱数据的离群挖掘，为发现未知天体提供了一种新的方法。（3）天体光谱数据的其他挖掘方法及天体光谱数据挖掘原型系统，包括第4章和第5章。这一部分介绍了天体光谱数据的正、负项目集挖掘、基于约束概念格的恒星光谱分类规则提取、恒星光谱的分类规则后处理等方法，之后给出了几个天体光谱数据挖掘原型系统，介绍了系统的功能模块、体系结构，以及系统运行的相关界面。
本书的完成得到了太原科技大学人工智能实验室、计算机科学与技术学院各位同人的大力支持，尤其是张继福教授、蔡江辉博士为本书提出了很多很好的建议，在此一并致以诚挚的谢意。
本书所涉及的部分研究工作得到了山西省青年科学基金项目（项目编号：2012021015-4）和山西省高校高新技术产业化项目（项目编号：20121011）的资助，在此谨向山西省自然科学基金委员会和山西省教育厅表示深深的感谢并致以敬意。
由于作者的水平有限，书中难免有不妥之处，恳请各位专家和广大读者给予批评指正。编 者2013年5月第1章 绪 论
随着数据库和计算机网络的广泛应用，数据处理领域面临两方面的难题。一方面是数据雪崩：现实世界中产生的数据量呈指数级增长，人们所拥有的信息量急剧增大，超大规模的数据集与日俱增，待处理的海量数据层出不穷，信息量远远超过了人脑掌握、消化的能力，这就是数据雪崩。另一方面，先进的观测技术和现代监测仪器的推广和应用使我们的监测范围更加广泛，随着数据维度的增加，许多数据分析变得非常困难，特别是随着维度的增加，数据在它所占据的空间中越来越稀疏。对于分类，这可能意味着没有足够的数据对象来创建模型，将所有可能的对象可靠地指派到一个类；对于聚类，点之间的密度和距离的定义（对聚类而言是至关重要的）失去了意义，这就是“维灾难”。
如此庞大的信息量已经远远超过了人脑可以驾驭的范围，传统的人工处理方法已经无法处理和利用如此大规模的海量、高维数据，更无法快速、准确地从中获取有用知识，传统的数据库技术和数据处理手段也已经不能满足要求。由于人们迫切需要将这些数据转换成有用的信息和知识，所以如何从海量、高维数据中快速提取有用信息已成为亟待解决的问题之一。正是基于这样的需求，数据挖掘技术受到了广泛关注，并得以快速发展。1.1 数据挖掘
数据挖掘（Data Mining）是一个从大量的数据中发现潜在知识的过程，是半自动或自动地从海量数据中发现模式、相关性、变化、反常规律性的过程。根据挖掘任务划分，数据挖掘主要发现五类知识：广义型知识（Generalization）——根据数据的微观特性发现其表征的、带有普遍性的、较高层次概念的、微观或宏观的知识；分类型知识（Classification）——反映同类事物共同性质的特征知识和不同事物之间差异型的特征知识，用于描述数据的汇聚模式或根据对象的属性区分其所属类别；关联型知识（Association）——反映一个事件和其他事件之间依赖或关联的知识，又称为依赖（Dependency）关系，这类知识可用于数据库的归一化、查询优化等；预测型知识（Prediction）——通过时间序列型数据，由历史的和当前的数据去预测未来的情况，它实际上是一种以时间为关键属性的关联知识；偏差型知识（Deviation）——离群数据（孤立点）的挖掘（Outliers Mining），通过分析标准类外的特例、数据聚类外的异常值、实际观测值和系统预测值间的显著差别，来对差异和极端特例进行描述。1.1.1 产生和定义
随着数据库和计算机网络的广泛应用，人们所拥有的数据量急剧增大，海量数据层出不穷。先进的现代科学观测仪器的使用造成每天都要产生巨量的数据，如我国建成的LAMOST望远镜，每晚将有2万～4万条光谱需要进行自动分类识别及参数测量。显然，大量信息在给人们带来方便的同时也带来了一系列问题，如信息量过大，超过了人们掌握、消化的能力；一些信息的真伪难辨，从而给信息的正确运用带来了困难；信息组织形式的不一致性导致难以对信息进行有效统一处理等，这种变化使得传统的数据库技术和数据处理手段已经不能满足要求。如何在海量数据中获取有价值的信息和知识成了信息系统的核心问题之一。数据挖掘正是为了解决这一问题，并针对大规模数据的分析处理而出现的。
数据挖掘就是从大量原始数据中提取人们感兴趣的、隐含的、尚未被发现的、有用的信息和知识，使它们可以有利于为专家进行决策提供技术支持，其提取的知识可以表示为概念、规则、规律、模式等形式。数据挖掘是当今数据库和人工智能相互结合的最前沿和极富应用前景的研究领域，已引起了国内外众多学者和业界的高度重视，他们已对数据挖掘的方法论、理论和工具开展了广泛深入的研究工作。由于数据挖掘获取的信息和知识可以广泛地应用于生物医学和DNA分析、银行与金融机构、零售业、电信业、商务管理、市场分析和企业决策管理等领域，所以数据挖掘技术引起了信息产业界的极大关注。目前，国内外学者已研究和开发出了一些数据挖掘系统，比较有代表性的通用数据挖掘系统有IBM公司的Almaden研究中心开发的Quest、加拿大Simon Fraser大学开发的DBMiner、SGI公司和美国Standford大学联合开发的MineSet、南京大学开发的Knight原型工具等。一个典型的数据挖掘系统可以由以下几个主要成分组成（如图1-1所示）。图1-1 数据挖掘系统的组成图
数据库、数据仓库或其他信息库：这是一个或一组数据库、数据仓库、电子表格或其他类型的信息库。可以在数据库上进行数据的清理和集成。
数据库或数据仓库服务器：根据用户的数据挖掘请求，数据库或数据仓库服务器负责提取相关数据。
知识库：这是领域知识，用于指导搜索或评估结果模式的兴趣度。
数据挖掘引擎：这是数据挖掘系统的基本部分，由一组功能模块组成，用于特征化、关联、分类、聚类分析，以及演变和偏差分析。
模式评价：通常，此成分使用兴趣度度量，并与数据挖掘引擎模块交互，以便将搜索聚焦在有趣的模式上。
图形用户界面：本模块在用户和数据挖掘系统之间进行通信，允许用户与系统交互，制定数据挖掘查询任务，提供信息，帮助搜索聚焦，根据数据挖掘的中间结果进行探索式数据挖掘。1.1.2 挖掘的过程
数据挖掘的一般过程可用图1-2进行描述。图1-2 数据挖掘的一般过程
1．数据抽取
大多数时候，与数据挖掘任务有关的数据是存储在应用数据库中的，这些数据库往往是为应用的目的而建立的，通常不能直接运行数据挖掘算法，而需要进行必要的抽取和格式的整理工作。
2．数据预处理
数据预处理是指处理掉一些噪声数据（冗余的、不一致的）或添补一些丢失的数据，以便使被挖掘的数据保持完整和干净。
3．数据设计
数据设计是指去掉一些无关的属性或对数据量过大的数据库进行抽样等。
4．算法设计
算法设计主要是指针对特定的挖掘任务，设计挖掘方法模型与高效的算法和相应的数据结构。
5．知识表示
知识表示是指从数据库或数据仓库中获取特定的知识类型，如分类、关联规则、聚类和序列模式等。
6．结果分析
结果分析是指由领域专家（Domain Expert）分析结果的可靠性、合理性及可用性，有时还需要对结果进行可视化处理。
从图1-2可以看出，数据挖掘的核心步骤是算法设计，一个好的数据挖掘模型、一个好的算法（速度快、伸缩性好、结果容易使用且符合用户的特定需求）是影响数据挖掘效率的最重要的因素。1.1.3 挖掘的任务
数据挖掘的任务是从大量数据中发现有趣模式。模式是用语言L来表示的一个表达式E，它可用来描述数据集DS中数据的特性。E所描述的数据是DS的一个子集。在实际应用中，数据挖掘模式可分为分类和回归模式、关联规则模式、聚类模式、孤立点模式、时间序列模式等。
分类（Classification）是找出描述并区分数据类或概念的模型（或函数）的过程。数据分类通常可以分为以下两步。
第一步，建立一个模型，描述预定的数据类集或概念集。可以通过分析由属性描述的数据库元组来构造模型，其中数据库元组是指被分析的样本、实例和对象。
第二步，使用模型进行分类。
常用的数据分类方法有判定树（Decision Tree）、贝叶斯分类（Bayesian）、神经网络（Neural Network）、K-最近邻分类、基于案例的推理（Case-based Reasoning，CBR）、概念格方法、粗糙集方法和模糊集方法。对于分类来说，其目的主要是提高分类的准确率与效率。
关联规则模式由Agrawal、Imielinski、Swami于1993年提出，它是描述在一个事务（项目）中物品（交易）同时出现的规律的知识模式，即通过量化的数字描述物品甲的出现对物品乙的出现的影响程度。关联规则模式的提取通常可以分为两步：找出满足用户的最小支持度的频繁项目集；提取出满足用户的最小置信度的关联规则。从大量商务事务记录中发现有趣的关联联系，可以帮助许多商务决策的制定，如市场规划、广告规划、分类设计、交叉购物和贱卖分析等。又如，在现今中国贷款购买住房和汽车的顾客中，调查发现70%的人的年龄在35～45岁之间，这样银行就可以通过分析这些客户的特点来调整一些相应的政策，以便将贷款发放给这类客户群体。自从Agrawal等提出从大型数据库中挖掘关联规则以来，关联规则的挖掘已广泛地应用在电子通信行业、信用卡公司、股票交易所、银行和超级市场等场合。目前，国内外研究者正在从多种角度、多种渠道研究基于各种数据模型的关联规则的提取。
聚类（Clustering）分析是指根据对象属性标识对象集的类（组、簇）的过程。将对象按某种聚类准则聚类后，可以使对象组内的相异性最小、组间的相异性最大。例如，在保险业上，聚类能帮助保险公司分析投保人群的特征，以加大对这些客户群体的投保率。
孤立点（Outlier）分析是指挖掘出与数据的一般行为或模型不一致的数据对象的过程。例如，孤立点分析通过监测一个给定账号与正常的付费的比较，以付款数额特别大来发现信用卡的欺骗使用。
时间序列（Timer Serial）分析是指把数据之间的关联性与时间联系起来，根据数据随时间变化的趋势预测未来的相关数值。1.1.4 挖掘的分类
数据挖掘可以从很多不同的角度进行分类。（1）根据挖掘的数据库类型，数据挖掘可分为关系数据库挖掘、空间数据库挖掘、时间数据库挖掘、文本数据库挖掘和多媒体数据库挖掘。（2）根据发现知识的种类不同，数据挖掘可分为分类规则挖掘、聚类规则挖掘、关联规则挖掘和序列模式挖掘。（3）根据挖掘使用技术的不同，数据挖掘可分为决策树、贝叶斯网络（Bayesian Networks）、模糊集、粗糙集、遗传算法和概念格。1.1.5 面临的主要问题
目前，数据挖掘面临的主要问题有三大类：挖掘方法和用户交互的问题、性能问题和存储数据的数据库类型具有多样性的问题。
1．挖掘方法和用户交互的问题
这一问题反映了所挖掘的知识类型、在多粒度上挖掘知识的能力、领域知识的使用、特定的挖掘和知识显示。由于不同的用户可能对不同类型的知识感兴趣，所以数据挖掘系统应当覆盖范围很广的数据分析和知识发现任务，并且用户可以和数据挖掘系统交互，以不同的粒度和从不同的角度观察数据和发现模式；发现的知识应易于理解，能够直接被人们使用。
2．性能问题
这一问题包括数据挖掘算法的有效性、可伸缩性和并行处理。为了有效地从数据库中提取信息，数据挖掘算法必须是有效的和可伸缩的，即对于大型数据库来说，数据挖掘算法的运行时间必须是可预计的和可接受的，这是促使开发并行和分布式数据挖掘算法的因素。此外，当数据库更新时，不必重新挖掘全部数据，只要进行知识更新，修正和加强已经发现的知识即可。
3．存储数据的数据库类型具有多样性的问题
这一问题包括关系的、复杂的数据库处理和在异种数据库之间挖掘信息。目前，有些数据库可能包含复杂的数据对象、超文本和多媒体数据、空间数据、时间数据或事务数据，由于数据类型的多样性和数据挖掘的目标不同，所以指望一个系统挖掘所有类型的数据是不现实的。从具有不同数据语义的，结构化的、半结构化的和非结构化的数据源来发现知识，对数据挖掘提出了巨大挑战。
以上问题是数据挖掘技术未来发展的主要需求和挑战。在近年来的数据挖掘的研究和开发中，一些挑战业已受到一定程度的关注，并考虑到了各种需求，而另外一些仍处于研究阶段。1.1.6 主要应用
数据挖掘的研究方兴未艾，具有非常广阔的前景。面向对象数据库、分布式数据库、文本数据库等的数据挖掘；贝叶斯网的兴起；面向多策略和合作的发现系统；结合多媒体技术的应用等都是新的研究方向。数据挖掘原型系统和商业软件已开始在多个方面得到应用。（1）客户分析：在银行信用卡和保险业中，确定有良好信誉和无不良倾向的客户是经营成功与否的关键。数据挖掘可以从以往的交易记录中“总结”出客户这些方面的信息。（2）客户关系管理：数据挖掘可以识别产品使用模式或协助了解客户行为，从而可以改进通道管理（Channel Management）。例如，适时销售（Right Time Marketing）就是基于可由数据挖掘发现的顾客生活周期模型来实施的一种商业策略。（3）零售业：数据挖掘对顾客购物篮数据（Basket Data）的分析可以协助货架布置、确定促销活动时间、促销商品组合及了解畅销和滞销商品的状况。（4）产品质量保证：通过对历史数据的分析，数据挖掘可以发现某些不正常的数据分布，暴露制造和装配操作过程中出现的问题。（5）WEB站点的数据挖掘：电子商务网站每天都可能有上百万次的在线交易，生成大量的记录文件和登记表，可以对这些数据进行分析和挖掘，充分了解客户的喜好、购买模式，甚至是客户的一时冲动，以设计出满足不同客户群体需求的个性化网站，甚至从数据中推测客户的背景信息，进而增加其竞争力。
另外，在各个企事业部门，数据挖掘在假伪检测、风险评估、失误回避、资源分配、市场销售预测和广告投资等方面都可以发挥作用。在国外，数据挖掘已应用于银行金融、零售批发、制造、保险、公共设施、行政、教育、通信、运输等多个行业部门，并且已经出现了许多数据挖掘和知识发现系统。例如，Quest是由IBM Almaden研究中心开发的数据挖掘系统，它可以从大型数据库中发现关联规则、分类规则、时间序列模式等；DBMiner是加拿大Jiawei Han教授领导的小组开发的一个数据挖掘系统；SKICAT系统是由U.M.Fayyad等人开发的知识发现系统，它将图像处理、数据分类、数据库管理等功能集成在一起，能够自动地对数字图像进行搜索和分类；KEFIR（Key Finding Reporter）是由GTE实验室开发的一个知识发现系统等。1.2 关联规则挖掘
关联规则挖掘是数据挖掘的一个重要研究方向，它描述了交易数据集DB中两组不同对象（对象指交易中的内容，又称为交易项目）之间存在的某种关联关系。在关联规则挖掘过程中，需要多次对交易数据集进行扫描并与候选频繁项目集进行匹配和计数。由于面对巨量交易数据集，这一匹配和计算过程需要花费大量时间，所以效率是设计挖掘算法的关键。
关联规则是由Agrawal等人首先提出的一个重要KDD研究课题，它反映了大量数据中项目集之间有趣的关联或相关联系。目前，关联规则挖掘算法中较有影响的挖掘算法为R.Agrawal在1993年提出的Apriori算法。
面对巨量数据，效率是数据挖掘的关键问题所在，因此关联规则的研究也以效率为中心展开了多角度、多层面的讨论与研究。目前，针对关联规则的研究主要有以下几个方面。（1）从研究对象上讲，有布尔型数据挖掘、数值型数据挖掘和模糊数据挖掘。（2）从研究技术上讲，有概念格、云模型、粗糙集等技术，或将这些技术相结合以利于提高挖掘效率。（3）从研究内容上讲，有挖掘算法、更新算法、分布式挖掘、抽样挖掘等几个方面。
挖掘算法以支持度、置信度框架为考虑因素，称为支持度-置信度框架，其中以R.Agrawal提出的Apriori算法较有影响。在此基础上又有很多Apriori算法的变种，如AprioriTid算法、AprioriHybrid算法；更新算法基于交易数据、最小支持度等挖掘条件的改变，为了提高挖掘效率，它考虑了在原来挖掘基础上二次挖掘的实现；分布式挖掘基于现实数据本身的存放特点或安全性等因素，挖掘工作由单处理器向多处理器转化；抽样挖掘也基于提高效率这一角度来考虑，较适合于效率比准确性要求更高的场合。1.2.1 关联规则的基本概念
设I={i,i,…,i}是二进制文字的集合，其中的元素称为项（Item）。12m记D为交易（Transaction）T的集合，这里的交易T是项的集合，并且有T⊆I。对应每一个交易有唯一的标识，如交易号，记为TID。设X是I中的一个项集合，如果X⊆T，则称交易T包含X。
一个关联规则是形如X⇒Y的蕴涵式，这里的X⊂I，Y⊂I，并且有X∩Y=ø。规则X⇒Y在交易数据库D中的支持度（Support）是交易集中包含X和Y的交易数与所有交易数之比，记为support（X⇒Y），即support（X⇒Y）=|{T：X∪Y⊆T，T∈D}|/|D|。
规则X⇒Y在交易集中的置信度（Confidence）是指包含X和Y的交易数与包含X的交易数之比，记为confidence（X⇒Y），即confidence（X⇒Y）= |{T:X∪Y⊆T，T∈D}|/|{T:X⊆T，T∈D}|。
项的集合称为项集（Itemset）。包含k个项的项集称为k-项集（k-itemset）。例如，集合{computer，ativirus_software}是一个2-itemset。包含项目集的事务数称为项目集出现的频率（支持计数），简称为项集的频繁程度或支持度。如果项目集满足由领域专家或用户设定支持度最小值的要求，则称它为频繁项目集。这样，对于某数据库D的关联规则挖掘问题就转化为如何准确、快速、高效地提取支持度大于最小支持度、置信度大于最小置信度的规则。1.2.2 关联规则挖掘的基本步骤
挖掘关联规则的步骤大体可以由一个两步过程来进行描述：（1）找出所有的频繁项目集，即找出所有那些支持度大于事先给定的支持度阈值的项目集；（2）在找出的频繁项目集的基础上产生强关联规则，即产生那些支持度和置信度分别大于或等于事先给定的支持度阈值和置信度阈值的关联规则。
在上述两个步骤中，第二个步骤相对要容易一些，因为它只需要在已经找出的频繁项目集的基础上列出所有可能的关联规则，然后用支持度阈值和置信度阈值来衡量这些关联规则，同时满足支持度阈值和置信度阈值要求的关联规则就被认为是有趣的关联规则。事实上，由于所有的关联规则都是在频繁项目集的基础上产生的，它们已经自动地满足了支持度阈值的要求，所以只需要考虑置信度阈值的要求。第一个步骤是挖掘关联规则的关键步骤，挖掘关联规则的总体性能由第一个步骤决定，因此所有挖掘关联规则的算法都着重于研究第一个步骤。
一般的发现频繁项目集的算法，都先产生候选频繁项目集（Candidate Itemsets）。候选频繁项目集是所有频繁项目集的超集，其产生算法需要具有可实现性，并且保证所有潜在的频繁项目集都包含在候选频繁项目集中。在上述条件下，如何能生成尽可能小的候选频繁项目集是所有方法都应遵循的原则。不同的算法，其候选频繁项目集的生成方法也不尽相同，但其产生候选频繁项目集的规模应该保证使它的进一步验证过程可以被计算。对于分层搜索而言，其候选频繁项目集是通过对前面某一长度的频繁项目集进行连接和剪枝两个操作生成的。
在生成候选频繁项目集后，算法需要从中找出频繁项目集。对于分层搜索算法而言，需要扫描数据库来计算每一个候选项目在数据库中的支持度，并将其记录下来为进一步的操作做好准备。显然，为了计算数据项目集的出现次数，算法需要遍历数据库中的每一条记录，并做相应的判断。对于一个大型数据库而言，这是一项非常耗时的操作。不同的算法使用了不同的技巧来减少这一过程的耗时。例如，DHP算法采用一种Direct Hash技术来减少候选项目的规模，并且采用事务剪枝技术大大缩减所需扫描事务的规模；FP-增长算法将数据库中的事务压缩到一棵频繁模式树中，然后用最不频繁的数据项作为后缀递归寻找频繁数据项。1.2.3 关联规则挖掘的基本方法
自从Agrawal提出关联规则之后，各种算法相继产生，不断发展。经典算法为Apriori算法，在此之后出现了增量式更新算法、基于事务压缩的方法、分区方法、取样方法及频繁模式增长算法等。
1．经典频繁项目集挖掘算法——Apriori算法
前面已经说过，算法的效率是关键，如何有效挖掘长频繁项目集是关联规则发现面临的主要挑战。针对此问题，Agrawal在1994年提出了Apriori算法，其基本思想是重复扫描数据库。第k次扫描产生长度为k的长频繁项目集，称为L，第k+1次扫描时，只考虑L中的k-项kk集产生的长度为k+1的候选频繁项目集C。因此，除了第一次扫描k＋1之外，每一次扫描要考虑的并不是所有项目的组合，而只是其中的一部分，即候选频繁项目集C。因此，Apriori扫描交易数据库的次数和k最大项目集的长度是一样的。Apriori基于一个性质，就是“所有长频繁项目集的子集都是频繁的”。利用此性质可以对候选频繁项目集进行剪枝，使候选频繁项目集C更小，从而显著地改进生成频繁项目集k算法的性能。在已经提出的算法中，Apriori是最有影响的，后来提出的许多算法在某种程度上都是它的变体。
2．杂凑算法
Park等在1995年提出了一个高效地产生频繁项目集的基于杂凑（Hash）的算法——Dynamic Hashing and Pruning（DHP）算法。通过实验可以发现，寻找频繁项目集主要的计算是在生成频繁2-项集上。DHP利用一个杂凑表在计算频繁1-项集时先大概计算出2-项集的支持度，从而减少了候选2-项集的数量。
3．划分
Savasere等设计了一个基于划分的算法，这个算法把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频繁项目集，然后把产生的频繁项目集合并，用来生成所有可能的频繁项目集，最后计算这些项集的支持度。基于划分的算法在很大程度上减小了I/O负载，但在处理高项集时存在一些问题，而且它可能导致频繁项目集的错误处理。
4．采样
Sampling算法是由Toivenen提出的。其基本思想是对给定数据的一个子集进行挖掘，其核心是随机从数据集D中采集样本S，然后搜索S中的频繁项集。样本S的大小以能够在内存中完成频繁项目集的挖掘为准。因此，整个算法只需要扫描一遍数据库。由于搜索的是S中的而不是D中的频繁项目集，所以可能漏掉一些全局的频繁项目集。这是一种以效率换取准确性的方法，在对于效率要求较高的应用场合极具意义和重要性。
5．动态项目集计数
Brin等人提出了动态项目集计数算法。该算法在添加一个新的候选集之前，先估计一下是不是它的所有子集都是频繁的。该算法把数据库分成若干个特定大小的区间，首先计算候选1-项集在第一个区间上的支持度，然后根据这些支持度产生候选2-项集，并且2-项集的支持度和1-项集的支持度在剩余的区间上继续计算。该算法的停止条件是没有新的候选集产生和所有候选集都在整个数据库上计算了支持度。该算法通过区间划分减少了遍历数据库的次数，但是它的性能也是和数据分布密切相关的。
6．基于栈变换的算法
惠晓滨等提出了一个基于频繁模式栈变换的高效关联规则算法，该算法采用了一种频繁模式栈的数据结构来存储所有的频繁模式信息，所有的栈单元都具有偏序关系，并分成构造算法和变换算法两个子算法，从而提高了挖掘效率，而且在数据集的记录数较大时有很好的线性性和伸缩性。
综上所述，基于Apriori的频繁项目集方法即使进行了一些优化，但是对于Apriori算法的一些固有的缺陷还是无法克服：Apriori算法可能产生大量的候选集；生成候选项目时由于模式匹配会造成巨大的时空开销。
7．FP-tree频繁项目集算法
J.Han等提出了不产生候选频繁项目集的方法：FP-tree频繁项目集算法。该算法采用分而治之的策略，在经过第一遍扫描之后，把数据库中的频繁项目集压缩进一棵频繁模式树（FP-tree），同时依然保留其中的关联信息，随后再将FP-tree分化成一些条件库，每个库和一个长度为1的频繁项目集相关，然后再对这些条件库分别进行挖掘。
FP-growth算法实现了FP-tree的构造及在FP-tree上进行挖掘，它只需对数据库进行两次扫描，而且避免了产生大量候选集的问题。实验表明：FP-growth对不同长度的规则具有很好的适应性，同时在效率上较之Apriori算法有很大的提高。
8．基于约束的关联规则
在实际应用中，用户通常对关联规则的子集感兴趣，即用户只想看到某些项目间的关联关系。为此，Srikant等提出了基于约束的关联规则（Constrain-Based Association Rules），其中约束用布尔值表示，如（夹克衫∧皮鞋）∨［Descendants（衣服）∧Ancestors（旅游鞋）］就表示对规则的约束，该规则中要么包含夹克衫和皮鞋，要么包含衣服的后代（Descendants），但不包含旅游鞋的前辈（Ancestors）。该算法没有采取先发现所有的规则再修剪不满足约束的规则的方法，而是直接把约束结合到算法中去，大大提高了规则发现的效率。
1）变支持度关联规则
上述关联规则挖掘算法均存在两大前提，即数据库中的各项目有相同的性质和作用；数据库中各项目的分布是均匀的。然而，实际往往并非如此，当数据库中的项目分布不均匀而出现频率相差较大的情况时，会导致最低支持度设高、设低都存在问题：设高了，会漏掉很多有趣的规则；设低了，会产生大量没有意义乃至虚假的关联规则，甚至还会导致组合爆炸。因此，挖掘关联规则时，如果项目之间在出现频率和重要性上存在很大差异，则不能为所有项目设定一个统一的支持度阈值。对此，有两种不同的解决方式：加权支持度和多支持度。
2）加权支持度关联规则挖掘
加权支持度是指必须考虑支持度和权重两个因素，即加权关联规则挖掘算法在计算支持度时，既要考虑规则中所有项目在数据库中同时出现的频率，也要考虑所有项目的加权值。一方面不能忽略低权值项目，另一方面在加权关联规则模型中，频繁项目集不再具有向下封闭性，因此不能采用Apriori算法及其优化算法。
3）多支持度关联规则挖掘
多支持度是指对每个项目都设置一个支持度阈值，即一种多最小支持度策略。一种多支持度关联规则挖掘算法——MSapriori算法，是通过对Apriori算法进行一些修改而得到的。对于一个项目集来说，其支持度阈值为该项目集中的项目支持度阈值的最小值，这样频繁项目集就失去了向下封闭性。因此，当用MSapriori算法得到频繁项目集以后还需要计算频繁项目集的所有子集的支持度，这又将带来很大的时空开销。
9．多层关联规则挖掘
对于很多应用领域而言，由于数据分布的分散性，所以很难在数据最细节的层次上发现一些强关联规则。当引入概念层次后，就可以在较高的层次上进行挖掘。虽然较高层次上得出的规则可能是普通的信息，但是对于一个用户来说是普通的信息对于另一个用户来说却未必如此。因此，数据挖掘应该提供一种在多个层次上进行挖掘的功能。挖掘多层关联规则一般有两种途径：一种是把单层次关联规则挖掘算法直接应用于多层次；另一种是在不同的层次上应用不同的支持度阈值和置信度阈值。现有的多层关联规则挖掘算法主要是Yongjian Fu提出的ML_TL1算法。ML_TL1算法利用自上而下的策略，从最高层次向低层次方向进行挖掘时，对频繁项目集出现的次数进行累计，以便发现每个层次的频繁项目集，直到无法获得新频繁项目集为止。
10．多维关联规则挖掘
包含两个或更多谓词的关联规则称为多维关联规则。对于多维数据库而言，挖掘的是多维关联规则。根据是否允许同一个维重复出现，多维关联规则可以再细分为维间的关联规则（不允许维重复出现）和混合维关联规则（允许维在规则的左右同时出现）。数据库中的属性可以是符号量或数值量，符号量属性的取值为有限个无序的值，而数值量属性的取值为有大小的数值。根据处理数值量的基本方法的不同，可以对多维关联规则采取不同的挖掘算法：利用静态离散挖掘；挖掘定量关联规则；挖掘基于距离的关联规则。
11．分布式关联规则挖掘
目前已有一些基于分布式的关联规则挖掘的研究工作。
Do.Trong针对一些渐进挖掘频繁模式的算法不能扩展到现实世界的数据库的问题，提出了一种挖掘频繁渐进闭模式算法，使得挖掘频繁闭项集的时间逐步线性。
Zhou，Jiayi提出了采用图形处理单元（GPU）来执行FPM以达到提高挖掘效率的目的。在该算法中，根据GPU硬件划界的特点，设计了一个紧凑的数据结构来存储整个数据库的数据。同时，设计了MemPack和CLProgram模板类来提高FPM的性能。
王治等人针对分布式关联规则挖掘可能造成频繁项集丢失的缺点，提出了一种改进的挖掘算法。该算法采用全局局部通信模式，通过对候选项目集建立对应的频繁标记，把频繁标记和频繁项目集的支持计数作为各局部站点和全局站点之间的传输内容。这样基本上保证了数据挖掘结果的完整性和正确性，但是在挖掘效率上有一定的局限，而且不适用于候选项发生变化的情况。
Mesa，Alejandro提出了一个高度并行算法，它利用垂直位向量数据的分布为决策支持计数，采用该算法自定义架构对于密集的数据库来说能提高挖掘效率。
黄勇等人针对分布式挖掘效率问题，提出了一种新的数据预处理方法及一种基于数组形式的频繁项目集生成算法。采用数据预处理方法可以减少候选项目集的数量，采用二进制的数组只需进行逻辑与运算便可生成频繁项目集，该方法从效率上来说是可行的，但不能够保证数据的一致性。
Negrevergne，Benjamin提出了一种基于LCM算法的并行算法PLCM QS，该算法能连续发现频繁闭项集，同时提出了一个基于Tuple Space结点的并行接口，它能够有效地动态分配任务。
Yu，Kun-Ming提出了两种并行挖掘算法TPFP-tree和BTP-tree，分别在PC集和网格集上挖掘频繁模式，通过事务交换、事务识别集合来直接选择事务，代替了数据库扫描，缩短了TPFP-tree的执行时间。
Lin，Kawuu针对传统并行挖掘算法可能遗漏一些数据的问题，提出了一个新的数据挖掘算法FD-Mine，它能够在云计算环境下发现频繁模式结点。此算法在可测量和执行时间方面有很好的性能。
Kumar，Preetham等人针对扫描多次数据库的问题，将扫描事务数据库转换为在挖掘阶段多次扫描数据库的加权树，并将这种数据结构用于并行结点中，同时对于每个分配给并行结点的频繁数据集，建造了项目集树和以权值最小支持度为基础的项目集树提取的频繁项目集。
秘中凯等人提出了一种基于Map/Reduce框架的频繁挖掘算法，该算法将挖掘任务分割成无相互依赖关系的同构子任务，实现有效的并行计算，并且充分利用Map/Reduce框架和集群环境的优势提高自身的鲁棒性和负载均衡能力，以此解决大规模医药数据分析中的频繁集挖掘问题。
王恩彬等人提出了一种基于向量点积的分布式关联规则挖掘算法，此算法在分布式环境下，利用保持隐私数据挖掘的基本方法和安全计算协议，可以在不泄露任何隐私的基础上有效地对垂直型数据分布进行挖掘。
桂琼等人结合RSA公钥加密和同态加密HES的优势，采用密码分级管理机制，提出了一种简单有效保护隐私的分布式关联规则挖掘算法（PPDM-ARBSM）。在该算法中引入了密码管理服务器（CMS）和数据挖掘服务器（DMS），此算法只适用于隐私保护，具有一定的局限性。
贾泂等人把频繁闭项集和最大频繁项集的概念推广到分布式数据库中，提出了在分布式环境下的频繁项目集的精简表示方法，以及一种基于各站点的全局大项目集的全局频繁闭项集和全局最大频繁项集的挖掘算法。
郑世明等人在相关矩阵理论的研究基础上，将网格与Web服务技术融合，以分布式问题求解环境和开源数据挖掘类库weka为底层支撑，构建了网格环境下面向服务的分布式数据挖掘体系，提出了一种基于矩阵的分布式关联规则算法，该算法不需要进行复杂的寻找频繁项目集的过程，但矩阵运算量非常大。
Chen，Xiaoyun等人提出了一个新奇的并行频繁项目集挖掘算法HPFP-Miner。该算法以FP-Growth为基础，引入有效划分频繁元素列表来减少数据传输，提高了挖掘性能。
在上述算法中，一部分通过其改进能够提高效率，但不能保证结果的准确性与完整性，另外一部分虽然可以保证结果准确、完整，但影响挖掘效率。因此，在保证挖掘结果准确、完整的前提下，能够有效提高挖掘效率值得进行进一步研究。1.2.4 关联规则的应用
目前，关联技术的主要应用领域是商业，其主要挖掘对象是事务（交易）数据库。通过对商业数据库中的海量销售记录进行分析，提取出反映顾客购物习惯和偏好的有用规则（或知识），可以决定商品的降价、摆放及设计优惠券等。当然，也可以把得到的信息应用到促销和广告中。
关联技术不但在商业分析中得到了广泛应用，在其他领域也得到了应用，包括工程、医疗保健、金融证券分析、电信和保险业的错误检验等。下面给出几个例子，它们的应用价值显而易见。
在健康保险业中，可以发现如下规则：用了药品A、B和C的病人通常也会用药品D；接受了Y医生的X治疗的病人通常也会接受注射Z。
在金融业中，关联技术的应用也很多，和在医药业中一样，这样的规则（或知识）常常值千金，如Q公司的股票通常在R公司的股票下跌一天后上涨。
另外，作为数据挖掘的基本任务之一，关联规则还可以用来完成其他的挖掘任务，如通信警报相关分析、学生选课分析、网页访问分析、数据建模、未来收入预测、决策支持等。
由于人们越来越认识到关联规则的重要性，所以几乎所有的知识挖掘工具都包含关联规则的模块。对于制造企业来说，关联规则可以被广泛地应用于市场分析、客户资源管理（CRM）、分类和预测分析等诸多领域。
1．市场分析
制造企业拥有大量关于客户的信息，企业对客户了解得越多，所能得到的收益也就越大。最常见的关联规则的应用事例就是购物篮分析，即如果企业决策者知道哪些产品可以同时（搭配）销售，则销售业绩无疑会迅速上升。
2．客户资源管理（CRM）
除了最基本的购物篮分析外，制造企业中的管理人员还需要知道关于客户的一些具体特征。客户资源管理可以被分为四个步骤：客户群落的划分；交叉销售机会的辨识；选用特定的市场模型支持交叉销售活动；应用磨损模型来提高对客户群体的保持力。在上述的第二步中，在对客户完成聚类并且已经确定了需要进行比较的类别之后，就可以采用关联规则来发现是哪些特征造成了客户之间的不同分类。这无疑会对企业提高交叉销售机会做出决策有很大帮助。通过关联规则的运用，就会发现问题潜在的实质。
3．分类
面对制造企业里的复杂数据和信息集合，研究人员通常采用诸如决策树的方法来实现分类过程。然而，在实际应用中，人们通常面临以下问题：由于数据的模糊性，无法做出准确的划分；在对一个新事例进行分类的过程中，通常很难辨识出最有效的规则；由训练数据产生的规则集包含了大量冗余规则。为了解决以上问题，学者们把关联规则算法延伸到了分类规则的领域。这种新的，通常被称为多层的分类关联规则具有以下两个优点：第一，它能够同时考虑多个变量之间的复杂关系；第二，它能够根据一组规则来决定新事例的具体类别。实践证明这种方法是非常有效的。
4．预测分析
在制造企业里，特别是在机械制造状态在线监测的活动中，可能会发现当监测量A和B上升时，监测量C也会上升。然而，人们似乎对下列规则更感兴趣，即当监测量A和B上升时，监测量C在时间t内上升的概率为p%。前者被称为事务内部的关联，后者则被称为事务外部的关联。经过研究可以发现，关联规则不但可以用来发现在同一事务中不同项目之间的关联性，而且可以用来发现不同事务中不同项目之间的关联性。充分地利用事务外部的关联，无疑可以帮助技术人员预测未来。1.3 离群数据挖掘
离群数据（Outlier）就是明显偏离其他数据，不满足数据的一般模式或行为，与存在的其他数据不一致的数据。离群数据与统计学中的异常值稍有不同：统计学中的异常值往往指的是一维的数据，而这里要研究的离群数据是多维的。离群数据通常来源于测量错误、计算机录入错误、人为错误等，要对这些数据进行修改、删除，否则可能影响数据分析结果；另外，它也可能就是数据的真实性质的反映，可能比一般数据所包含的信息更有价值，这部分数据应予以保留。离群数据的发现，往往可以使人们发现一些真实的，但又出乎意料的知识。离群数据挖掘是数据挖掘的一个新兴课题，在实际生活中有广泛的应用，如金融、通信领域的欺诈分析与监测、网络入侵监测、消费极高或极低客户的消费习惯、过程控制中的故障监测与诊断等。目前，异常挖掘正逐渐成为数据库、机器学习、统计学等领域研究人员的研究热点。
从20世纪80年代开始，离群数据挖掘问题就在统计学领域里得到了广泛研究。通常情况下，用户用某个统计分布对数据点进行建模，再用假定的模型根据点的分布来确定离群数据。许许多多针对不同分布的离群数据挖掘方法发展起来，它们分别适用于不同的情形：数据分布情况；数据分布参数是否已知；离群数量的多少。这些方法的最大缺陷是：在许多情况下，用户并不知道这个数据分布，而且现实数据也往往不符合任何一种理想状态的数学分布。
Ruts和Roussccuw提出了基于深度的算法。根据该算法，每一个数据被映射到一个k维数据空间上的点，每个点被赋予一个特定定义的“深度”，并且根据不同深度将数据划分成不同层次。基于统计学的结论，异常往往存在于较“浅”的数据层次中，但由于基于深度的算法要求计算k维数据空间的凸闭包，所以其复杂度较高。实际上，仅仅当k=2或k=3时，该算法的性能才可以忍受。
Argrawal和Ragaran在1996年提出过“序列离群数据”的概念。他们采用这样一个机制：扫描数据集并观测到一系列相似数据，当发现一个数据点明显不同于前面的序列时，这样的点就被认为是离群数据。这个算法的复杂度与数据集规模成线性关系，有优异的计算性能，但是序列异常对异常存在的假设太理想化，对于现实复杂数据的实验效果不太好。
Knorr和Ng在1998年提出了基于距离的异常监测算法，而Rastogi和Ramaswamy改进了他们的异常定义。在聚类算法研究中，许多算法都具有一定的噪声处理能力，这些算法把异常监测当做聚类算法的副产品。但是聚类中的噪声和异常在概念上还是有些偏差的，噪声定义在聚类基础之上，即噪声是不隶属于任何聚类的数据，而异常不依赖于是否存在聚类，而且基于距离的异常监测算法的出发点是优化聚类查找而不是异常监测。
Breunig和Kriegel将基于密度的聚类算法OPTICS与异常监测合并到一起研究，这个算法的主要计算消耗在聚类的查找上，只需要很小的额外代价就可以监测到异常。这些研究也奠定了基于密度的异常概念的产生，在此基础上，Breunig和Kriegel提出了局部异常因子的概念。
到目前为止提出的异常监测算法对高维数据异常的监测效果都不理想。Aggarwal等提出了一个针对高维数据集进行降维的异常监测新思路，它把高维数据映射到低维子空间，根据子空间的映射数据稀疏度来确定离群数据是否存在，该方法取得了良好的效果。1.3.1 离群数据挖掘的方法
由于离群数据是数据集中与其余数据有显著不同的数据点，所以比较直观的方法是建立数据集中绝大部分数据的数据模型，从而把不满足该数据模型的那一部分数据认定为离群数据。这样就出现了不同的离群数据挖掘方法，大致可以分为以下几类：基于统计的方法，基于距离的方法，基于深度的方法，基于偏离的方法，基于聚类的方法及局部离群数据监测算法。
1．基于统计的离群数据发现方法
基于统计的离群数据发现方法是指首先对已知数据集假定某种分布或概率模型，然后根据模型采用不一致性检验（Discordancy Test）以确定离群数据。不一致性检验包含两个假设：零假设（Working Hypothesis）和对立假设（Alternative Hypothesis）。零假设H描述的0是待处理数据集满足同一分布模型F，即H:∈F，i=1,2,…,n。不一致0性检验验证O关于分布F是否有显著不一致（大或小）。检验统计量i的选取，取决于数据的先验知识。假设统计量T已选定，数据对象Oi的统计量值为V，T的分布被建立，计算显著性SP（V）= Prob(T＞iiV)，如果SP(V)足够小，则拒绝零假设；反之，不能拒绝零假设。ii
对立假设H声明O来自另外一种分布模型G。不一致性检验中的1i对立假设是非常重要的，它决定了检验的准确性，它有以下几种形式：混合对立分布（Mixture Alternative Distribution），内在对立分布（Inherent Alternative Distribution），滑动对立分布（Slippage Alternative Distribution）。
应用基于统计的方法要求事先知道数据集合参数（如假定的数据分布）、分布参数（如均值、标准差）和预期的离群数据的个数，而这些信息在实际应用中一般是未知的。这类方法的另外一个主要的缺点是：绝大多数应用是针对数值型数据的，也就是说，它们对单属性数据是有效的，而较难对高维数据、周期性数据、分类数据进行挖掘。
2．基于距离的异常检测算法
基于距离的异常检测算法最早是由Knorr和Ng提出的。基于距离的离群数据（Distance-based）是指一个对象O是一个带参数p和b的离群数据，表示为DB(p，b)。该方法不依赖于统计检验，而是在寻找一些远离其他数据的点，这里的其他数据是基于给定对象的距离来定义的。基于距离的方法避免了基于统计的方法所必需的大量计算，提高了对海量数据的挖掘效率。
当前的效率较高的挖掘算法有以下几种。（1）基于索引的算法（Index-based）：给定一个数据集合，基于索引的算法采用多维索引结构（如R树或k-d树）来查找每一个对象O在半径d范围内的邻居。设M是一个孤立点的d邻域内的最大对象数目。因此，一旦对象O的M+1个邻居被发现，O就不是孤立点。这个算法2在最坏情况下的复杂度为O（k×n），这里的k是维数，n是数据集合中对象的数目。当k增加时，基于索引的算法具有良好的扩展性。但是该算法的复杂度估算只考虑了搜索时间，而没有考虑建立索引的时间，即使建造索引的任务本身就是计算密集的。（2）嵌套-循环算法（Nested-loop）：嵌套-循环算法和基于索引的算法有相同的计算复杂度，但它避免了索引结构的构建，试图最小化I/O的次数，增加了I/O的效率。它把内存的缓冲空间分为两个区域，并且把数据集合分为若干个逻辑块。它通过精心选择逻辑块装入每一个缓冲区域的顺序来改善I/O效率。2（3）基于单元的算法（Cell-based）：为了减小O(n)的计算复杂度，为驻留内存的数据集合开发了基于单元的算法。它的复杂度是O(ck+n)，这里的c是依赖于单元数目的常数，k是维数。在该算法中，数据空间被划分为边长等于的单位。每个单位有两层围绕着它，第一层的厚度是一个单元，而第二层的厚度是。该算法逐个单元地对孤立点计数，而不是逐个对象地进行计数。由于该算法将对数据集的每一个元素进行离群数据搜索改为对每个单元进行搜索，所以提高了算法的效率。
使用基于距离的方法需要用户通过实验确定合适的p、d参数，如果p、d参数选择不当，会产生错误结论。该方法无法处理分类数据和周期性时态数据。
3．基于深度的异常检测算法
基于深度的异常检测算法首先把数据集中的每个记录表示为k维空间里的一个点，然后根据特定的深度定义给每个点赋予一个深度值，再根据深度值按层组织数据，深度值较小的记录是离群数据的可能性较大，因此该算法只需要在深度较小的层上进行异常检测。具有代表性的异常检测算法有Struy 和Rousseeuw提出的DEEPLOC算法。当维数k≤3时，该算法还有可能是高效的，而当k≥4时，该算法的效率就非常低。
4．基于偏离的异常检测算法
基于偏离的异常检测算法通过测试数据集的主要特征来确定离群数据。其代表性算法有：Aming采用序列化技术来发现离群数据，由于该算法的假设太过理想化，所以遗漏了不少真正的离群数据；Sarawagi应用OLAP数据立方体提出了基于偏移的异常检测算法；Jagdish给出了一个高效的，挖掘时间序列中离群数据的基于偏离的异常检测算法。基于偏离的异常检测算法的主要缺陷是由于需要事先知道数据的主要特征，而现实世界中的数据量非常大且数据的属性也非常多，所以数据的主要特征不容易确定，这样该方法在实际中应用得很少。
5．基于聚类的异常检测算法
这类算法的典型特征是首先考虑数据的聚类特征，将异常点监测视为聚类问题的逆问题加以处理。由于它们有效地运用聚类方法将大部分数据标记为聚类成员，所以异常点发现的目标相对集中。具有代表性的算法有采用WaveCluster聚类算法的原理构造FindOut、基于DENCLUE的算法思想和网格层次方法GridOF等。
6．局部离群数据监测算法
局部离群数据是指在数据集中与其邻域表现不一致或大大偏离其邻域的数据。Breunig和Kriegel研究了全局离群数据的不足之处，即采用全局的观点来定义离群数据，在某些条件下是有意义的和充分的，但是在各密度簇都存在的情况下，就不再适合。于是，Breunig和Kriegel首先提出了基于密度的离群数据挖掘方法，并认为异常不应该是一个二进制性质，即某一个数据对象要么是离群数据，要么不是离群数据，而应该是一个度量。其基本思想来自于基于局部离群因子（LOF）的密度聚类方法：在同一个聚类中的任何对象q，可以证明，其LOF值近似等于1。因此，如果一个数据对象的LOF值远远大于1，就把该数据对象视为离群数据。下面给出LOF值的计算方法。
定义1.1 对象p的k-距离
对于任意的自然数k，定义p的k-距离（k-distance（p））为对象p和某个对象o之间的距离，这里的o满足：
至少存在k个对象o′∈D\{p}，使得d(p,o′)≤d(p,o)；
至多存在k-1个对象o′∈D\{p}，使得d(p,o′) 定义1.2 对象p的k-距离邻域 给定p的(k-distance(p))，p的k-距离邻域包含所有与p的距离不超过k-distance(p)的对象，即N={q|d(p,q)≤k-distance(p)}。k-distance（p） 定义1.3 对象p相对于对象o的可达距离 reach-dist(p,o)=max{k-distance(o)，d(p,o)} 定义1.4 对象p的局部可达密度
试读结束[说明：试读内容隐藏了图片]