数据挖掘入门课件

数据挖掘

主要内容

数据挖掘概述数据预处理数据挖掘算法－分类与预测数据挖掘算法－聚类数据挖掘算法－关联分析序列模式挖掘一、数据挖掘概述数据挖掘概念数据挖掘--从大量的数据中，提取隐含在其中的、人们事先不知道的但又可能有用的信息和知识的过程。数据挖掘的主要目的是提高决策能力，检测异常模式，在过去的经验基础上预言未来趋势等。

例如，通过对大量气象资料和销售资料的处理及分析，德国的啤酒商发现，夏天气温每升高1℃，就会增加230万瓶的啤酒销量；而日本人则发现，夏季30℃以上的天气每增加一天，空调的销量便增加4万台。5

沃尔玛超市建立数据仓库，按周期统计产品的销售信息，经过科学建模后提炼决策层数据。发现每逢周末，位于某地区的沃尔玛超市连锁店的啤酒和尿布的销售量很大，而且单张发票中同时购买尿布和啤酒的记录非常普遍。分析人员认为这并非偶然，经过深入分析得知，通常周末购买尿布的是男士，他们在完成了太太交给的任务后，经常会顺便买一些啤酒。得出这样的结果后，沃尔玛超市的工作人员尝试着将啤酒和尿布摆放在一起销售，结果尿布与啤酒的销售额双双增长。

数据挖掘概念6数据挖掘（DataMining）：又称为数据库中的知识发现，是基于AI、机器学习、统计学等技术，高度自动化地分析原有的数据，进行归纳性推理，从数据仓库或数据库中提取可信的、新颖的、有效的、人们感兴趣的、能别人理解的知识的高级处理过程。这些知识是隐含的、事先未知的有用信息，提取的知识表现为概念、规则、模式、规律等形式，以帮助管理者作出正确的决策。模式：它给出了数据特性或数据之间的关系，是对数据所包含的信息更抽象的描述。模式按功能可以分为预测型模式和描述型模式。在实际应用中，可以细分为关联模式、分类模式、聚类模式和序列模式等。数据挖掘概念数据挖掘的任务分类预测（Prediction）

利用一些变量来预测未知的或其他变量将来的值.典型的方法是回归分析，即利用大量的历史数据，以时间为变量建立线性或非线性回归方程。预测时，只要输入任意的时间值，通过回归方程就可求出该时间的状态。近年来，发展起来的神经网络方法，如BP模型，它实现了非线性样本的学习，能进行非线性函数的预测

典型的分类型任务如下：1、给出一个客户的购买或消费特征，判断其是否会流失；2、给出一个信用卡申请者的资料，判断其编造资料骗取信用卡的可能性3、给出一个病人的症状，判断其可能患的疾病4、给出大额资金交易的细节，判断是否有洗钱的嫌疑；5、给出很多文章，判断文章的类别（如科技、体育、经济等）数据挖掘的任务

描述型任务：找到人们可以解释的，描述数据的模式.描述性任务主要包括聚类、摘要、依赖分析等几种任务。聚类任务把没有预定义类别的数据划分成几个合理的类别，摘要任务形成数据高度浓缩的子集及描述，依赖分析任务发现数据项之间的关系。典型的描述型任务如下：1、给出一组客户的行为特征，将客户分成多个行为相似的群体；2、给出一组购买数据，分析购买某些物品和购买其他物品之间的联系3、给出一篇文档，自动形成该文档的摘要数据挖掘的任务数据挖掘的任务分类

[预测性的]聚类

[描述性的]关联规则发现

[描述性的]序列模式发现[描述性的]预测回归

[预测性的]异常发现

[预测型的]分类给定一组纪录(训练集-trainingset

)每一条记录都包含一组属性,其中的一个属性就是类.为类属性找到一个模型，这个模型就是其他属性值的函数.目的：先前未见过的纪录应该被尽可能精确的分配一个类中.

在分类预测任务中，数据集根据其在数据挖掘过程中扮演角色的不同，可划分为训练集、测试集、验证集。

训练集：是在数据挖掘过程中用来训练学习算法，建立模型的数据集.测试集：就是数据挖掘算法在生成模型后，用以测试所得到的模型的有效性的数据集，常被用来决定模型的精确性.验证集：是在数据挖掘过程结束后，模型应用的实际数据集，验证集用于在实践中检验模型.分类例如：一个销售的顾客数据库（训练样本集合），对购买计算机的人员进行分类：字段为（年龄（取值：<30,30~40,>40);收入(高,中,低);学生否(Y,N);信用(一般,很好);购买计算机否(Y,N))记录为14个,具体数据如下:X1=(<30,高,N,一般,N);X2=(<30,高,N,很好,N);X3=(30~40,高,N,一般,Y);X4=(>40,中,N,一般,Y);X5=(>40,低,Y,一般,Y);X6=(>40,低,Y,很好,N);X7=(30~40,低,Y,很好,Y);X8=(<30,中,N,一般,N);X9=(<30,低,Y,一般,Y);X10=(>40,中,Y,一般,Y);X11=(<30,中,Y,很好,Y);X12=(30~40,中,N,很好,Y);X13=(30~40,高,Y,一般,Y);X14=(>40,中,N,很好,N);

利用贝叶斯法则预测，符合下列条件的人员购买计算机的可能性X=（年龄<30,收入=中,学生否=Y,信用=一般)分类聚类

聚类是按照某个特定标准（通常是某种）把一个数据集分割成不同的类，使得类内相似性尽可能地大，同时类间的区别性也尽可能地大。直观地看，最终形成的每个聚类，在空间上应该是一个相对稠密的区域。聚类是对记录分组，把相似的记录在一个聚类里。聚类和分类的区别是聚类不依赖于预先定义好的类，不需要训练集。

例子：

a.一些特定症状的聚类可能预示了一个特定的疾病

b.租VCD类型不相似的客户聚类，可能暗示成员属于不同的亚文化群

IllustratingClusteringEuclideanDistanceBasedClusteringin3-Dspace.IntraclusterdistancesareminimizedInterclusterdistancesaremaximized

聚类方法主要包括划分聚类、层次聚类、基于密度的聚类和kohonen聚类等；进行划分聚类，一般用距离来度量对象之间的相似性，典型的是欧氏距离；距离越大，则相似性越小，反之亦然；聚集通常作为数据挖掘的第一步。例如，“哪一种类的促销对客户响应最好？”，对于这一类问题，首先对整个客户做聚集，将客户分组在各自的聚集里，然后对每个不同的聚集，回答问题，可能效果更好。聚类

预测回归通常，预测是通过分类或估值起作用的，也就是说，通过分类或估值得出模型，该模型用于对未知变量的预言。从这种意义上说，预测其实没有必要分为一个单独的类。

预测其目的是对未来未知变量的估计，这种预测是需要时间来验证的，即必须经过一定时间后，才知道预测准确性是多少。

例如(1)证券市场;(2)由顾客过去之刷卡消费量预测其未来之刷卡消费量。使用的技巧包括回归分析、时间数列分析及类神经网络方法。关联规则从所有对象决定那些相关对象应该放在一起。例如超市中相关之盥洗用品(牙刷、牙膏、牙线)，放在同一间货架上。在客户营销系统上，此种功能系用来确认交叉销售(cross-selling)的机会以设计出吸引人的产品群组。

序列模式发现定义：给定一个项集合，每一个项都和事件的时间有关系.目的：找出规则来预测在不同时间点上很强的序列依赖性.Rulesareformedbyfirstdisoveringpatterns.Eventoccurrencesinthepatternsaregovernedbytimingconstraints.(AB)(C)(DE)<=ms<=xg

>ng<=ws(AB)(C)(DE)异常检测从正常的行为中检测有意义的异常应用:信用卡欺诈检测网络侵扰检测

TypicalnetworktrafficatUniversitylevelmayreachover100millionconnectionsperday

数据挖掘的发展1989IJCAI会议：数据库中的知识发现讨论专题KnowledgeDiscoveryinDatabases(G.Piatetsky-ShapiroandW.Frawley,1991)1991-1994KDD讨论专题AdvancesinKnowledgeDiscoveryandDataMining(U.Fayyad,G.Piatetsky-Shapiro,P.Smyth,andR.Uthurusamy,1996)1995-1998KDD国际会议(KDD’95-98)JournalofDataMiningandKnowledgeDiscovery(1997)1998ACMSIGKDD,SIGKDD’1999-2002会议,以及SIGKDDExplorations数据挖掘方面更多的国际会议PAKDD,PKDD,SIAM-DataMining,(IEEE)ICDM,DaWaK,SPIE-DM,etc.

进化阶段商业问题支持技术产品厂家产品特点数据搜集

(60年代)“过去五年中我的总收入是多少？”计算机、磁带和磁盘IBM,CDC提供历史性的、静态的数据信息数据访问

(80年代)“在新英格兰的分部去年三月的销售额是多少？”关系数据库（RDBMS），结构化查询语言（SQL），ODBCOracle、Sybase、Informix、IBM、MicrosoftOracle、Sybase、Informix、IBM、Microsoft在记录级提供历史性的、动态数据信息数据仓库；

决策支持

(90年代)“在新英格兰的分部去年三月的销售额是多少？波士顿据此可得出什么结论？”联机分析处理（OLAP）、多维数据库、数据仓库Pilot、Comshare、Arbor、Cognos、Microstrategy在各种层次上提供回溯的、动态的数据信息数据挖掘

（正在流行）“下个月波士顿的销售会怎么样？为什么？”高级算法、多处理器计算机、海量数据库Pilot、Lockheed、IBM、SGI、其他初创公司提供预测性的信息数据挖掘系统代特征数据挖掘算法集成分布计算模型数据模型第一代数据挖掘作为一个独立的应用支持一个或者多个算法独立的系统单个机器向量数据第二代和数据库以及数据仓库集成多个算法：能够挖掘一次不能放进内存的数据数据管理系统，包括数据库和数据仓库同质/局部区域的计算机群集有些系统支持对象、文本、和连续的媒体数据第三代和预言模型系统集成多个算法数据管理和预言模型系统intranet/extranet网络计算支持半结构化数据和web数据第四代和移动数据/各种计算数据联合多个算法数据管理、预言模型、移动系统移动和各种计算设备普遍存在的计算模型数据挖掘系统第一代数据挖掘系统

支持一个或少数几个数据挖掘算法，这些算法设计用来挖掘向量数据（vector-valueddata），这些数据模型在挖掘时候，一般一次性调进内存进行处理。许多这样的系统已经商业化。第二代数据挖掘系统

目前的研究，是改善第一代数据挖掘系统，开发第二代数据挖掘系统。第二代数据挖掘系统支持数据库和数据仓库，和它们具有高性能的接口，具有高的可扩展性。例如，第二代系统能够挖掘大数据集、更复杂的数据集、以及高维数据。这一代系统通过支持数据挖掘模式（dataminingschema）和数据挖掘查询语言（DMQL）增加系统的灵活性。

数据挖掘系统第三代数据挖掘系统

第三代的特征是能够挖掘Internet/Extranet的分布式和高度异质的数据，并且能够有效地和操作型系统集成。这一代数据挖掘系统关键的技术之一是提供对建立在异质系统上的多个预言模型以及管理这些预言模型的元数据提供第一级别（firstclass）的支持。

第四代数据挖掘系统

第四代数据挖掘系统能够挖掘嵌入式系统、移动系统、和普遍存在（ubiquitous）计算设备产生的各种类型的数据。数据挖掘与KDD二、数据预处理数据预处理为什么要预处理数据？数据清理数据集成数据变换数据归约数据离散化为什么要预处理数据？现实世界的数据是“肮脏的”——数据多了，什么问题都会出现不完整的：有些感兴趣的属性缺少属性值，或仅包含聚集数据含噪声的：包含错误或者“孤立点”不一致的：在编码或者命名上存在差异没有高质量的数据，就没有高质量的挖掘结果高质量的决策必须依赖高质量的数据数据仓库需要对高质量的数据进行一致地集成数据质量的多维度量一个广为认可的多维度量观点：精确度完整度一致性可信度附加价值可访问性……跟数据本身的含义相关的内在的、上下文的、表象的数据预处理的主要任务数据清理填写空缺的值，平滑噪声数据，识别、删除孤立点，解决不一致性数据集成集成多个数据库、数据立方体或文件数据变换规范化和聚集数据归约得到数据集的压缩表示，它小得多，但可以得到相同或相近的结果数据离散化数据归约的一部分，通过概念分层和数据的离散化来规约数据，对数字型数据特别重要数据预处理为什么要预处理数据？数据清理数据集成数据变换数据归约数据离散化空缺值数据并不总是完整的例如：数据库表中，很多条记录的对应字段没有相应值，比如销售表中的顾客收入引起空缺值的原因设备异常与其他已有数据不一致而被删除因为误解而没有被输入的数据在输入时，有些数据应为得不到重视而没有被输入对数据的改变没有进行日志记载空缺值要经过推断而补上如何处理空缺值忽略元组：当类标号缺少时通常这么做（假定挖掘任务设计分类或描述），当每个属性缺少值的百分比变化很大时，它的效果非常差。人工填写空缺值：工作量大，可行性低使用一个全局变量填充空缺值：比如使用unknown或-∞使用属性的平均值填充空缺值使用与给定元组属同一类的所有样本的平均值使用最可能的值填充空缺值：使用像Bayesian公式或判定树这样的基于推断的方法噪声数据噪声：一个测量变量中的随机错误或偏差引起不正确属性值的原因数据收集工具的问题数据输入错误数据传输错误技术限制命名规则的不一致其它需要数据清理的数据问题重复记录不完整的数据不一致的数据如何处理噪声数据分箱(binning):首先排序数据，并将他们分到等深的箱中然后可以按箱的平均值平滑、按箱中值平滑、按箱的边界平滑等等聚类：监测并且去除孤立点计算机和人工检查结合计算机检测可疑数据，然后对它们进行人工判断回归通过让数据适应回归函数来平滑数据数据平滑的分箱方法price的排序后数据（单位：美元）：4，8，15，21，21，24，25，28，34划分为（等深的）箱：箱1：4，8，15箱2：21，21，24箱3：25，28，34用箱平均值平滑：箱1：9，9，9箱2：22，22，22箱3：29，29，29用箱边界平滑：箱1：4，4，15箱2：21，21，24箱3：25，25，34聚类通过聚类分析查找孤立点，消除噪声回归xyy=x+1X1Y1Y1’数据预处理为什么要预处理数据？数据清理数据集成数据变换数据归约数据离散化数据集成数据集成：将多个数据源中的数据整合到一个一致的存储中模式集成：整合不同数据源中的元数据实体识别问题：匹配来自不同数据源的现实世界的实体，比如：A.cust-id=B.customer_no检测并解决数据值的冲突对现实世界中的同一实体，来自不同数据源的属性值可能是不同的可能的原因：不同的数据表示，不同的度量等等处理数据集成中的冗余数据集成多个数据库时，经常会出现冗余数据同一属性在不同的数据库中会有不同的字段名一个属性可以由另外一个表导出，如“年薪”有些冗余可以被相关分析检测到仔细将多个数据源中的数据集成起来，能够减少或避免结果数据中的冗余与不一致性，从而可以提高挖掘的速度和质量。数据预处理为什么要预处理数据？数据清理数据集成数据变换数据归约数据离散化数据变换 平滑：去除数据中的噪声（分箱、聚类、回归）聚集：汇总，数据立方体的构建数据概化：沿概念分层向上汇总规范化：将数据按比例缩放，使之落入一个小的特定区间最小－最大规范化z-score规范化小数定标规范化属性构造通过现有属性构造新的属性，并添加到属性集中；以增加对高维数据的结构的理解和精确度数据变换——规范化最小－最大规范化z-score规范化小数定标规范化其中，j是使Max(||)<1的最小整数数据预处理为什么要预处理数据？数据清理数据集成数据变换数据归约数据离散化数据归约策略数据仓库中往往存有海量数据，在其上进行复杂的数据分析与挖掘需要很长的时间数据归约数据归约可以用来得到数据集的归约表示，它小得多，但可以产生相同的（或几乎相同的）分析结果数据归约策略数据立方体聚集维归约数据压缩数值归约离散化和概念分层产生用于数据归约的时间不应当超过或“抵消”在归约后的数据上挖掘节省的时间。数据立方体聚集最底层的方体对应于基本方体基本方体对应于感兴趣的实体在数据立方体中存在着不同级别的汇总数据立方体可以看成方体的格每个较高层次的抽象将进一步减少结果数据数据立方体提供了对预计算的汇总数据的快速访问使用与给定任务相关的最小方体在可能的情况下，对于汇总数据的查询应当使用数据立方体维归约通过删除不相干的属性或维减少数据量属性子集选择找出最小属性集，使得数据类的概率分布尽可能的接近使用所有属性的原分布减少出现在发现模式上的属性的数目，使得模式更易于理解启发式的（探索性的）方法逐步向前选择逐步向后删除向前选择和向后删除相结合判定归纳树数据压缩有损压缩VS.无损压缩字符串压缩有广泛的理论基础和精妙的算法通常是无损压缩在解压缩前对字符串的操作非常有限音频/视频压缩通常是有损压缩，压缩精度可以递进选择有时可以在不解压整体数据的情况下，重构某个片断两种有损数据压缩的方法：小波变换和主要成分分析数值归约通过选择替代的、较小的数据表示形式来减少数据量有参方法：使用一个参数模型估计数据，最后只要存储参数即可。线性回归方法：Y=α+βX多元回归：线性回归的扩充对数线性模型：近似离散的多维数据概率分布无参方法：直方图聚类选样直方图一种流行的数据归约技术将某属性的数据划分为不相交的子集，或桶，桶中放置该值的出现频率桶和属性值的划分规则等宽等深V-最优MaxDiff聚类将数据集划分为聚类，然后通过聚类来表示数据集如果数据可以组成各种不同的聚类，则该技术非常有效，反之如果数据界线模糊，则方法无效数据可以分层聚类，并被存储在多层索引树中聚类的定义和算法都有很多选择选样允许用数据的较小随机样本（子集）表示大的数据集对数据集D的样本选择：简单随机选择n个样本，不回放：由D的N个元组中抽取n个样本简单随机选择n个样本，回放：过程同上，只是元组被抽取后，将被回放，可能再次被抽取聚类选样：D中元组被分入M个互不相交的聚类中，可在其中的m个聚类上进行简单随机选择（m<M）分层选样：D被划分为互不相交的“层”，则可通过对每一层的简单随机选样得到D的分层选样选样——SRSSRSWOR(简单随机选样，不回放)SRSWR原始数据选样——聚类/分层选样原始数据聚类/分层选样数据预处理为什么要预处理数据？数据清理数据集成数据变换数据归约数据离散化离散化三种类型的属性值：名称型——e.g.无序集合中的值(如颜色,民族..)序数——e.g.有序集合中的值(如职称)连续值——e.g.实数离散化将连续属性的范围划分为区间有效的规约数据基于判定树的分类挖掘离散化的数值用于进一步分析离散化和概念分层离散化通过将属性域划分为区间，减少给定连续属性值的个数。区间的标号可以代替实际的数据值。概念分层通过使用高层的概念（比如：青年、中年、老年）来替代底层的属性值（比如：实际的年龄数据值）来规约数据数据数值的离散化和概念分层生成分箱（binning）分箱技术递归的用于结果划分，可以产生概念分层。直方图分析（histogram）直方图分析方法递归的应用于每一部分，可以自动产生多级概念分层。聚类分析将数据划分成簇，每个簇形成同一个概念层上的一个节点，每个簇可再分成多个子簇，形成子节点。基于熵的离散化通过自然划分分段通过自然划分分段将数值区域划分为相对一致的、易于阅读的、看上去更直观或自然的区间。聚类分析产生概念分层可能会将一个工资区间划分为：[51263.98,60872.34]通常数据分析人员希望看到划分的形式为[50000，60000]自然划分的3-4-5规则常被用来将数值数据划分为相对一致，“更自然”的区间自然划分的3-4-5规则规则的划分步骤：如果一个区间最高有效位上包含3，6，7或9个不同的值，就将该区间划分为3个等宽子区间；(72,3,2)如果一个区间最高有效位上包含2，4，或8个不同的值，就将该区间划分为4个等宽子区间；如果一个区间最高有效位上包含1，5，或10个不同的值，就将该区间划分为5个等宽子区间；将该规则递归的应用于每个子区间，产生给定数值属性的概念分层；对于数据集中出现的最大值和最小值的极端分布，为了避免上述方法出现的结果扭曲，可以在顶层分段时，选用一个大部分的概率空间。e.g.5%-95%3-4-5规则——例子(-$4000-$5,000)(-$400-0)(-$400--$300)(-$300--$200)(-$200--$100)(-$100-0)(0-$1,000)(0-$200)($200-$400)($400-$600)($600-$800)($800-$1,000)($2,000-$5,000)($2,000-$3,000)($3,000-$4,000)($4,000-$5,000)($1,000-$2,000)($1,000-$1,200)($1,200-$1,400)($1,400-$1,600)($1,600-$1,800)($1,800-$2,000)msd=1,000 Low=-$1,000 High=$2,000第二步第四步第一步-$351 -$159 profit $1,838 $4,700 MinLow(i.e,5%-tile) High(i.e,95%-0tile)Maxcount(-$1,000-$2,000)(-$1,000-0)(0-$1,000)第三步($1,000-$2,000)分类数据的概念分层生成分类数据是指无序的离散数据，它有有限个值（可能很多个）。分类数据的概念分层生成方法：由用户或专家在模式级显式的说明属性的部分序。通过显示数据分组说明分层结构的一部分。说明属性集，但不说明它们的偏序，然后系统根据算法自动产生属性的序，构造有意义的概念分层。对只说明部分属性集的情况，则可根据数据库模式中的数据语义定义对属性的捆绑信息，来恢复相关的属性。属性集的规格根据在给定属性集中，每个属性所包含的不同值的个数，可以自动的生成概念分成；不同值个数最多的属性将被放在概念分层的最底层。countryprovincecitystreet5个不同值65个不同值3567个不同值674,339个不同值三、数据挖掘算法

－分类与预测分类VS.预测分类：预测分类标号（或离散值）根据训练数据集和类标号属性，构建模型来分类现有数据，并用来分类新数据预测：建立连续函数值模型，比如预测空缺值典型应用信誉证实目标市场医疗诊断性能预测数据分类：两步过程第一步，建立一个模型，描述预定数据类集和概念集假定每个元组属于一个预定义的类，由一个类标号属性确定基本概念训练数据集：由为建立模型而被分析的数据元组形成训练样本：训练数据集中的单个样本（元组）学习模型可以用分类规则、判定树或数学公式的形式提供第二步，使用模型，对将来的或未知的对象进行分类首先评估模型的预测准确率对每个测试样本，将已知的类标号和该样本的学习模型类预测比较模型在给定测试集上的准确率是正确被模型分类的测试样本百分比测试集要独立于训练样本集，否则会出现“过分适应数据”的情况第一步：建立模型训练数据集分类算法IFrank=‘professor’ORyears>6THENtenured=‘yes’分类规则第二步：用模型进行分类分类规则测试集未知数据(Jeff,Professor,4)Tenured?准备分类和预测的数据通过对数据进行预处理，可以提高分类和预测过程的准确性、有效性和可伸缩性数据清理消除或减少噪声，处理空缺值，从而减少学习时的混乱相关性分析数据中的有些属性可能与当前任务不相关；也有些属性可能是冗余的；删除这些属性可以加快学习步骤，使学习结果更精确数据变换可以将数据概化到较高层概念，或将数据进行规范化比较分类方法使用下列标准比较分类和预测方法预测的准确率：模型正确预测新数据的类编号的能力速度：产生和使用模型的计算花销鲁棒性：给定噪声数据或有空缺值的数据，模型正确预测的能力可伸缩性：对大量数据，有效的构建模型的能力可解释性：学习模型提供的理解和洞察的层次决策树分类(DecisionTree)从属性-类别事例推理树状规则的分类方法。应用最为广泛，常用的有：ID3，C4.5。叶节点生成决策树步骤：修剪决策树生成决策树的关键:选择合适的属性作为判断依据，信息增益，信息增益比等生成决策树时未考虑噪声影响，出现过拟合，预测效果差：预先剪枝，后剪枝20世纪七、八十年代，J.RossQuilan开发了决策树算法，称作ID3(IterativeDichotomiser,迭代的二分器)，后又提出了C4.5(ID3的后继)。1984年即位统计学家(L.Breiman,J.Friedman,R.Olshen和C.Stonr)出版了分类与回归树(CART),介绍了二叉决策树的产生。决策树分类二叉树CART算法3.2.决策树的基本思想1.ID3算法和C4.5算法决策树的基本思想每个内部节点（非叶节点）表示一个属性的测试；每个树叶节点代表一个类（输出）归纳学习buys_computer的决策树，表示AllElectronics顾客是否可能购买计算机展示结果规则集决策树AllElectronics顾客数据库类标记的训练样本属性选择度量增益率信息增益指标纯，即划分后各组中所有样本都属于相同的类。属性选择度量又称分裂规则，根据该准则分裂后的输出将样本集细化，理性情况下，每个划分是“纯”的。

信息熵

设数据集为

，类属性具有

个取值，定义

个不同的类设是

中类的样本的集合,和分别是和中的样本个数.数据集D的信息熵:其中,是中任意样本属于类的概率,用估计.使用以2为底的对数函数,是因为信息用二进位编码.应用式子(1),计算AllElectronics顾客数据库分类所需要的信息熵：(1)

假设按属性划分中的样本，且属性根据训练数据的观测具有个不同值。如果是离散值，这些值直接对应于的属性。可依属性将划分为个子集其中，为中的样本，它们在上具有属性值这些划分将对应于从该节点出来的分支。基于按划分对的样本分类所需要的期望信息：其中，充当第个划分的权重。越小，划分的纯度越高。信息增益信息增益定义式：

告诉我们知道的值而导致的信息需求的期望减少。按照能做“最佳分类”的属性划分，使完成样本分类需要的信息量最小。选择具有最高信息增益的属性作为分裂属性信息增益信息增益信息增益信息增益第一次迭代后形成的决策树ageyouthmiddle_agedseniorP1P2P8P9P11P3P7P12P13P4P5P6P10P14属性age具有最高信息增益，成为分裂属性算法终止条件1一个节点的所有样本均属于同一类2若当前数据集没有属性可用于划分时，则按照少数服从多数的原则将当前节点强制为叶节点。3当分到某类时，某个值的比例达到了给定的阈值。buys_computer的决策树，表示AllElectronics顾客是否可能购买计算机最终形成的决策树递归ageyouthmiddle_agedseniorYesfairnoyescredit_rating?student?YesNoYesNoexcellent算法流程优点：(1)原理简单，生成模式便于理解；(2)对噪声数据有很好的强壮性。缺点：(1)只能处理离散值属性；(2)偏袒选择值较多的属性；(3)易产生过拟合（overfitting）后剪枝ID3算法优缺点C4.5算法1993年由Quinlan提出，采用信息增益比(信息率)来选择属性。克服偏向选择取值较多属性的缺点用阈值对属性划分，即把训练集中该属性的所有值划分到不同的区间中。用最常见值代替未知值规则存于二维数组中如：视为youth;视为middle_aged;

视为senior.Why？信息增益度量偏向于有许多输出的测试，即它倾向于选择具有大量值的属性。举个极端的例子：考虑充当唯一标识的属性PID。对PID的分裂将产生大量划分（与样本个数一样多），每个分类只包含一个样本，且每个划分都是纯的。对属性PID划分得到的信息增益最大，显然，这种划分对分类没有用处。增益率What？

使用分裂信息(splitinformation)将信息增益规范化。该值表示数据集按属性测试的个划分产生的信息。增益率：选择具有最大信息率的属性作为分裂属性。增益率增益率income其他属性的信息率可类似求出。对数据源进行数据预处理，将连续性的属性变量进行离散化处理形成决策树的训练集；计算每个属性的信息增益和信息增益率；对于取值连续的属性，分别计算不同分割点所对应的分类的信息增益率，选择最大信息增益率对应的阈值作为该属性分类的分割点；选择信息增益率最大的属性作为当前的属性节点，得到决策树的根节点。根节点属性每一个可能的取值对应一个子集，对样本自己递归地执行步骤2过程，知道划分的每个子集中的观测数据在分类属性上取值都相同，生成决策树。根据构造的决策树提取分类规则，对新的数据及进行分类。C4.5算法CompanyLogo连续属性的处理设数据集T中，连续属性A的取值{v1,v2,…,vm},则任何在vi和vi+1之间的任意取值都可以把实例集合分为两部分T1={t|A≤vi}和T2={t|A＞vi}；对属性A一共有m-1种分割情况；计算每种分割所对应的信息增益率gain_ratio(vi)在m-1种分割中，Threshold(V)=vkgain_ration(vk)=max{gain_ration(vi)}连续属性A可以分割为：

AA＞Threshold(V)A≤Threshold(V)连续属性的处理根据上面的描述，我们需要对每个候选分割阈值进行增益或熵的计算才能得到最优的阈值，我们需要算N-1次增益或熵（对应温度这个变量而言就是13次计算）。能否有所改进呢？该图中的绿线代表可能的最优分割阈值点，根据信息论知识，像middle[72,75]（红线所示）这个分割点，72,75属于同一个类，这样的分割点是不可能有信息增益的

C4．5算法将分类范围从分类的属性扩展到数字属性。如果数据集中存在连续型的描述性属性(数字属性)，C4．5算法首先将这些连续型属性的值分成不同的区间，即“离散化”。通常将连续型属性值“离散化”的方法为：①寻找该连续型属性的最小值，并将它赋值给min，寻找该连续型属性的最大值，并将它赋值给max；②设置区间[min，max]中的N个等分断点Ai，其中，i=1,2,⋯,N；③分别计算把(min，Ai)和(Ai,max)(i=1,2,3,⋯,N)作为区间值时的信息增益率（Ratio）值，并进行比较；④选取信息增益率最大的A。作为该连续型属性的断点，将属性值设置为[min，A]和(A，max)两个区间值。连续属性的处理

离散化处理过程中，C4.5算法是对节点上的每个属性都要计算其信息增益率,然后从中选择信息增益率最大的属性断点。由于在信息增益率计算过程中涉及到对数函数的计算,在计算程序中就得调用库函数,同时随着数据量的增大，计算量也随之增大。这样就增加了计算量时间。因此，在改进的C4.5算法中采用了“Fayyad边界点判定定理”连续属性的处理定义:

属性A中的一个值T是一边界点,当且仅当在按A的值排序的实例序列中,存在两个实例e1,e2∈S具有不同的类,使得A(e1)<T<A(e2),且不存在任何其他的实例e′∈S,使得A(e1)<A(e′)<A(e2)。A(e)表示实例e的A属性值。S表示实例的集合。定理

:

若T使得E(A,T,S)最小,则T是一个边界点。其中,A为属性,S为实例集合,E表示平均类熵,T为某一阈值点。定理表明,对连续属性A,使得实例集合的平均类熵达到最小值的T,总是处于实例序列中两个相邻异类实例之间。连续属性的处理

由Fayyad边界点判定定理可知,无需检查每一个阈值点,只要检查相邻不同类别的边界点即可。为了保持与C4.5的一致性,这里边界点选为相邻不同类别的属性值中较小的一个。例如,当排序后的实例属性值为{v1,v2,⋯,v10},其中前3个属于类别C1,中间4个属于类别C2,最后3个属于类别C3,因此只需考察两个边界点v3与v7而无需检查其余7个阈值点,然后选择v3与v7中使得平均类熵最小的那个作为最优阈值。连续属性的处理示例—高尔夫我们分类的目的就是根据某一天的天气状态，如天气，温度，湿度，是否刮风，来判断这一天是否适合打高尔夫球。最终生成的决策树CART

指标(index)在CART中使用。CART生成二叉树。

指标用来度量数据划分或者数据集的不纯度。其中，是中样本属于类的概率，并用估计。

指标考虑每个属性上的二元划分。Gini指标CART如果

属性是离散值，考察

的属性值形成的可能子集每个子集可以看作属性的形如的二元测试。给定一个样本，如果该样本的值出现在中，该测试满足。Gini指标AllElectronics顾客数据库类标记的训练样本为了找出数据集的分裂准则，需要计算每个属性的

指标。CART以属性

为例。有三个属性值子集有个分别是和由于集合不代表任何分裂，基于属性的二元和划分，存在种划分数据集的方法。Gini指标CART如果按照的二元分裂，将划分成和，则给定该划分的

指标为：基于该划分计算出的指标值为：数据集中满足

的样本共10个，考虑属性的子集。其余4个样本被划分到中。被分到中，对于连续值属性，必须考虑每个可能的分裂点。取排序好的每对相邻值的中点取做可能的分裂点。被分成和Gini指标Gini指标类似地，对其余子集分裂的指标值是：0.458(子集{}和{})0.450(子集{}和{})同样的办法，评估节点，得到(或)为的最好分裂.

CART

指标值为0.357；属性和都是二元的，分别具有指标值0.367和0.429.比较可知，属性和分裂子集产生最小

指标，因此被选作根节点，产生两个分支。CART生成二叉树CART生成二叉树对分裂后的子集，递归调用上述流程，即可完成建树。yesyesnono是是是否否否决策树剪枝Why？由于数据中存在噪声，许多分支反映的是训练数据中的异常。剪枝来处理这种过分拟合问题。How?先剪枝(prepruning)后剪枝(postpruning)在完全正确分类训练集之前就停止树的生长。由“完全生长”的树剪去子树。决策树剪枝——先剪枝最直接的方法：事先限定树的最大生长高度如果设为3，则如图剪枝yesyesno剪枝处理yesno45311no否否否否是是是是找出“完全”生长的树树叶用被替换的子树最频繁的类标号。yesyesnoyesno41311no2yes/no2NO是是是是是是否否否否否否决策树剪枝——后剪枝贝叶斯分类贝叶斯分类利用统计学中的贝叶斯定理，来预测类成员的概率，即给定一个样本，计算该样本属于一个特定的类的概率。朴素贝叶斯分类：假设每个属性之间都是相互独立的，并且每个属性对分类问题产生的影响都是一样的。后向传播分类后向传播是一种神经网络学习算法；神经网络是一组连接的输入/输出单元，每个连接都与一个权相连。在学习阶段，通过调整神经网络的权，使得能够预测输入样本的正确标号来学习。优点预测精度总的来说较高健壮性好，训练样本中包含错误时也可正常工作输出可能是离散值、连续值或者是离散或量化属性的向量值对目标进行分类较快缺点训练（学习）时间长蕴涵在学习的权中的符号含义很难理解很难根专业领域知识相整合其他分类方法k-最临近分类给定一个未知样本，k-最临近分类法搜索模式空间，找出最接近未知样本的k个训练样本；然后使用k个最临近者中最公共的类来预测当前样本的类标号基于案例的推理样本或案例使用复杂的符号表示，对于新案例，先检测是否存在同样的训练案例；如果找不到，则搜索类似的训练案例遗传算法结合生物进化思想的算法什么是预测？预测是构造和使用模型评估无样本类，或评估给定样本可能具有的属性或值空间。预测和分类的异同相同点两者都需要构建模型都用模型来估计未知值预测当中主要的估计方法是回归分析线性回归和多元回归非线性回归不同点分类法主要是用来预测类标号（分类属性值）预测法主要是用来估计连续值（量化属性值）回归方法线性回归：Y=+X其中

和

是回归系数，可以根据给定的数据点，通过最小二乘法来求得多元回归：Y=+1X1+2X2线性回归的扩展，设计多个预测变量，可以用最小二乘法求得上式中的，1和

2非线性回归：Y=+1X1+2X22+3X33对不呈线性依赖的数据建模使用多项式回归建模方法，然后进行变量变换，将非线性模型转换为线性模型，然后用最小二乘法求解评估分类法的准确性导出分类法后，再使用训练数据评估分类法，可能错误的导致乐观的估计保持方法给定数据随机划分为两个集合：训练集(2/3)和测试集(1/3)训练集导出分类法，测试集对其准确性进行评估随机子选样：保持方法的一个变形，将保持方法重复k次，然后取准确率的平均值k-折交叉确认初始数据被划分为k个不相交的，大小大致相同的子集S1,S2…Sk进行k次训练和测试，第i次时，以Si做测试集，其他做训练集准确率为k次迭代正确分类数除以初始数据集样本总数提高分类法的准确性Bagging技术和boosting技术都通过将T个学习得到的分类法C1,C2…CT组合起来，从而创造一个改进的分类法C*Bagging技术对训练集S进行T次迭代，每次通过放回取样选取样本集St，通过学习St得到分类法Ct对于未知样本X，每个分类法返回其类预测，作为一票C*统计得票，并将得票最高的预测赋予XBoosting技术每个训练样本赋予一个权值Ct的权值取决于其错误率四、数据挖掘算法－聚类什么是聚类分析？聚类（簇）：数据对象的集合在同一个聚类（簇）中的对象彼此相似不同簇中的对象则相异聚类分析将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程聚类是一种无指导的学习：没有预定义的类编号聚类分析的数据挖掘功能作为一个独立的工具来获得数据分布的情况作为其他算法（如：特征和分类）的预处理步骤聚类分析的典型应用模式识别空间数据分析在GIS系统中，对相似区域进行聚类，产生主题地图检测空间聚类，并给出它们在空间数据挖掘中的解释图像处理商务应用中，帮市场分析人员发现不同的顾客群万维网对WEB上的文档进行分类对WEB日志的数据进行聚类，以发现相同的用户访问模式什么是好的聚类分析？一个好的聚类分析方法会产生高质量的聚类高类内相似度低类间相似度作为统计学的一个分支，聚类分析的研究主要是基于距离的聚类；一个高质量的聚类分析结果，将取决于所使用的聚类方法聚类方法的所使用的相似性度量和方法的实施方法发现隐藏模式的能力数据挖掘对聚类分析的要求(1)可扩展性(Scalability)大多数来自于机器学习和统计学领域的聚类算法在处理数百条数据时能表现出高效率处理不同数据类型的能力数字型；二元类型，分类型/标称型，序数型,比例标度型等等发现任意形状的能力基于距离的聚类算法往往发现的是球形的聚类，其实现实的聚类是任意形状的用于决定输入参数的领域知识最小化对于高维数据，参数很难决定，聚类的质量也很难控制处理噪声数据的能力对空缺值、离群点、数据噪声不敏感数据挖掘对聚类分析的要求(2)对于输入数据的顺序不敏感同一个数据集合，以不同的次序提交给同一个算法，应该产生相似的结果高维性高维的数据往往比较稀松，而且高度倾斜基于约束的聚类找到既满足约束条件，又具有良好聚类特性的数据分组可解释性和可用性聚类要和特定的语义解释和应用相联系聚类分析中的数据类型许多聚类算法采用以下两种数据结构数据矩阵：用p个变量来表示n个对象也叫二模矩阵，行与列代表不同实体相异度矩阵：存储n个对象两两之间的临近度也叫单模矩阵，行和列代表相同的实体相异度计算许多聚类算法都是以相异度矩阵为基础，如果数据是用数据矩阵形式表示，则往往要将其先转化为相异度矩阵。相异度d(i,j)的具体计算会因所使用的数据类型不同而不同，常用的数据类型包括：区间标度变量二元变量标称型、序数型和比例标度型变量混合类型的变量区间标度变量区间标度度量是一个粗略线性标度的连续度量，比如重量、高度等选用的度量单位将直接影响聚类分析的结果，因此需要实现度量值的标准化，将原来的值转化为无单位的值，给定一个变量f的度量值，可使用以下方法进行标准化：计算平均的绝对偏差其中计算标准化的度量值(z-score)使用平均的绝对偏差往往比使用标准差更具有健壮性对象间的相似度和相异度(1)对象间的相似度和相异度是基于两个对象间的距离来计算的Euclidean距离i=(xi1,xi2,…,xip)和j=(xj1,xj2,…,xjp)是两个p维数据对象Manhattan距离对象间的相似度和相异度(2)Manhattan距离和Euclidean距离的性质d(i,j)

0d(i,i)

=0d(i,j)

=d(j,i)d(i,j)

d(i,k)

+d(k,j)Minkowski距离上式中，q为正整数，如果q=1则表示Manhattan距离，如果q=2则表示Euclidean距离二元变量(1)一个二元变量只有两种状态：0或1；e.g.smoker来表示是否吸烟一个对象可以包含多个二元变量。二元变量的可能性表：如何计算两个二元变量之间的相似度？ObjectiObjectj二元变量(2)对称的VS.不对称的二元变量对称的二元变量指变量的两个状态具有同等价值，相同权重；e.g.性别基于对称的二元变量的相似度称为恒定的相似度，可以使用简单匹配系数评估它们的相异度：不对称的二元变量中，变量的两个状态的重要性是不同的；e.g.HIV阳性VSHIV阴性基于不对称的二元变量的相似度称为非恒定的相似度，可以使用Jaccard系数评估它们的相异度二元变量的相异度——示例二元变量之间的相异度（病人记录表）Name是对象标识gender是对称的二元变量其余属性都是非对称的二元变量如过Y和P（positive阳性）为1，N为0，则：标称变量标称变量是二元变量的推广，它可以具有多于两个的状态值。比如：红、绿、蓝、黄。对于标称型变量，值之间的排列顺序是不重要的。计算标称变量所描述的对象（一个对象可以包含多个标称变量）i和j之间的相异度方法一：简单匹配方法m:匹配的数目，即对象i和j取值相同的变量的数目(也可加上权重)方法二：对M个标称状态中的每个状态创建一个新的二元变量，并用非对称的二元变量来编码标称变量红 绿 蓝 黄 取值0 1 0 0 绿0 0 1 0 蓝。。。。。。序数型变量一个序数型变量可以是离散的或者是连续的序数型变量的值之间是有顺序关系的，比如：讲师、副教授、正教授。假设f是描述n个对象的一组序数型变量之一，f的相异度计算如下：1.设第i个对象的f值为xif，则用它在值中的序rif代替2.将每个变量的值域映射到[0,1]的空间3.采用区间标度变量的相异度计算方法计算f的相异度比例标度变量一个比例标度型变量xif是在非线性的标度中所取的正的度量值，例如指数标度，近似的遵循以下公式：

AeBtorAe-Bt

计算比例标度型变量描述的对象之间的相异度采用与区间标度变量同样的方法——标度可能被扭曲，效果往往不好对比例标度型变量进行对数变化之后进行与区间标度变量的相似处理yif=log(xif)将xif看作连续的序数型数据，将其秩作为区间标度的值来对待混合类型的变量在真实的数据库中，数据对象不是被一种类型的度量所描述，而是被多种类型（即混合类型）的度量所描述，包括：区间标度度量、对称二元变量，不对称二元变量，标称变量，序数型变量合比例标度变量计算混合型变量描述的对象之间的相异度将变量按类型分组，对每种类型的变量进行单独的聚类分析在每种聚类分析导出相似结果的情况下可行所有变量一起处理，进行一次聚类分析，可以将不同类型的变量组合在单个相异度矩阵中，把所有有意义的变量转换到共同的值域区间[0,1]之内主要的聚类方法聚类分析算法种类繁多，具体的算法选择取决于数据类型，聚类的应用和目的，常用的聚类算法包括：划分方法层次的方法基于密度的方法基于网格的方法基于模型的方法实际应用中的聚类算法，往往是上述聚类方法中多种方法的整合划分方法给定一个n个对象或元组的数据库，一个划分方法构建数据的k个划分，每个划分表示一个簇，并且k<=n。每个组至少包含一个对象每个对象属于且仅属于一个组划分准则：同一个聚类中的对象尽可能的接近或相关，不同聚类中的对象尽可能的原理或不同簇的表示k-平均算法由簇的平均值来代表整个簇k中心点算法由处于簇的中心区域的某个值代表整个簇层次的方法对给定数据对象集合进行层次分解自底向上方法（凝聚）：开始将每个对象作为单独的一个组，然后相继的合并相近的对象或组，直到所有的组合并为一个，或者达到一个终止条件。自顶向下方法（分裂）：开始将所有的对象置于一个簇中，在迭代的每一步，一个簇被分裂为多个更小的簇，直到最终每个对象在一个单独的簇中，或达到一个终止条件缺点：合并或分裂的步骤不能被撤销基于密度的方法基于距离的聚类方法的缺点：只能发现球状的簇，难以发现任意形状的簇。基于密度的据类：只要临近区域的密度（对象或数据点的数目）超过某个临界值，就继续聚类。优点：可以过滤掉“噪声”和“离群点”，发现任意形状的簇。基于网格的方法把对象空间量化为有限数目的单元，形成一个网格结构。所有的聚类都在这个网格结构上进行。优点：处理数度快（因为处理时间独立于数据对象数目，只与量化空间中每一维的单元数目有关）基于模型的方法为每个簇假定一个模型，寻找数据对给定模型的最佳拟合。一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类这种方法同时也用于自动的决定数据集中聚类的数目通过统计学的方法，考虑噪声和离群点，从而产生健壮的聚类方法划分的方法给定n个对象的数据集，以及要生成的簇的数目k，划分算法将对象组织为k个划分（kn）每个划分代表一个簇通常通过计算对象间距离进行划分典型的划分方法k均值k中心点以上两种方法的变种基于质心的技术：k均值方法簇的相似度是关于簇中对象的均值度量，可以看作簇的质心（centroid）k均值算法流程随机选择k个对象，每个对象代表一个簇的初始均值或中心对剩余的每个对象，根据它与簇均值的距离，将他指派到最相似的簇计算每个簇的新均值回到步骤2，循环，直到准则函数收敛常用准则函数：平方误差准则(p是空间中的点，mi是簇Ci的均值)k均值方法---示例012345678910012345678910012345678910012345678910K=2随机选择2个对象，作为簇的中心将每个对象指派到最相似的簇更新每个簇的均值更新每个簇的均值重新分派重新分派…k均值算法的评论可扩展性较好，算法复杂度为O(nkt)，其中n为对象总数，k是簇的个数，t是迭代次数。经常终止于局部最优解缺点只有当簇均值有定义的情况下，k均值方法才能使用。（某些分类属性的均值可能没有定义）用户必须首先给定簇数目不适合发现非凸形状的簇，或者大小差别很大的簇对噪声和离群点数据敏感基于代表对象的技术：k中心点方法k均值方法对于离群点敏感一个具有很大极端值的对象可能显著的扭曲数据的分布平方误差函数将进一步严重恶化这种影响k中心点方法：采用簇的中心点，即最靠近中心的对象来代表簇降低算法对离群点的敏感度012345678910012345678910012345678910012345678910k中心点方法步骤k中心点方法仍然基于最小化所有对象与其对应的参照点之间的相异度之和原则，使用的是绝对误差标准(p是空间中的点，代表簇Cj中一个给定对象；oj是簇Cj中的代表对象)通常该算法重复迭代，直到每个代表对象都成为它的簇的实际中心点首先随意选择初始代表对象只要能够提高结果聚类质量，迭代过程就使用非代表对象替换代表对象聚类结果的质量用代价函数评估，该函数度量对象与其簇的代表对象之间的平均差异度k中心点方法---代表对象替换重新分配将对代价函数产生影响，如果当前的代表对象被非代表对象所取代，代价函数就是计算绝对误差值的差变换的总代价是所有非代表对象所产生的代价之和总代价为负，实际的绝对误差E将减少，Oj可以被Orandom所取代总代价为正，则本次迭代没有变化k均值方法与k中心点方法比较当存在噪声和离群点时，k中心点方法比k均值方法更加鲁棒中心点较少的受离群点影响k中心点方法的执行代价比k均值方法要高k均值方法：O(nkt)k中心点方法：O(k(n-k)2)n与k较大时，k中心点方法的执行代价很高两种方法都要用户指定簇的数目k离群点分析什么是离群点？一个数据集与其他数据有着显著区别的数据对象的集合例如：运动员：MichaelJordon,舒马赫，布勃卡离群点产生原因度量或执行错误（年龄：-999）数据变异的结果离群点挖掘给定一个n个数据对象的集合，以及预期的离群点数目k，发现与剩余的数据有着显著差异的头k个数据对象应用欺诈检测、医疗中的异常分析等基于统计的离群点检测统计的方法对于给定的数据集合假定了一个分布或概率模型（例如正态分布）使用依赖于以下参数的不一致性检验（discordancytests）数据分布分布参数（e.g.均值或方差）预期的离群点数缺点绝大多数检验是针对单个属性的，而数据挖掘要求在多维空间中发现离群点大部分情况下，数据分布可能是未知的基于距离的离群点检测为了解决统计学方法带来的一些限制，引入了基于距离的离群点检测在不知道数据分布的情况下对数据进行多维分析基于距离的离群点：即DB(p,d)，如果数据集合S中的对象至少有p部分与对象o的距离大于d，则对象o就是DB(p,d)。挖掘基于距离的离群点的高效算法：基于索引的算法嵌套－循环算法基于单元的算法基于偏离的离群点检测通过检查一组对象的主要特征来确立离群点跟主要特征的描述相“偏离”的对象被认为是离群点两种基于偏离的离群点探测技术序列异常技术模仿人类从一系列推测类似的对象中识别异常对象的方式OLAP数据立方体技术在大规模的多维数据中采用数据立方体来确定异常区域。如果一个立方体的单元值显著的不同于根据统计模型得到的期望值，则改单元值被认为是一个异常，并用可视化技术表示。五、数据挖掘算法－关联什么是关联挖掘?关联规则挖掘：在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性、或因果结构。应用：购物篮分析、交叉销售、产品目录设计、loss-leaderanalysis、聚集、分类等。举例：规则形式：“Body®Head[support,confidence]”.buys(x,“diapers”)®buys(x,“beers”)[0.5%,60%]major(x,“CS”)^takes(x,“DB”)®grade(x,“A”)[1%,75%]关联规则：基本概念给定:(1)交易数据库(2)每笔交易是：一个项目列表(消费者一次购买活动中购买的商品)查找:所有描述一个项目集合与其他项目集合相关性的规则E.g.,98%ofpeoplewhopurchasetiresandautoaccessoriesalsogetautomotiveservicesdone应用*护理用品

(商店应该怎样提高护理用品的销售？)家用电器

*

(其他商品的库存有什么影响?)在产品直销中使用附加邮寄Detecting“ping-pong”ingofpatients,faulty“collisions”规则度量：支持度与可信度查找所有的规则X&YZ具有最小支持度和可信度支持度,

s,一次交易中包含{X、Y、Z}的可能性可信度,

c,

包含{X、Y}的交易中也包含Z的条件概率设最小支持度为50%,最小可信度为50%,则可得到AC(50%,66.6%)CA(50%,100%)买尿布的客户二者都买的客户买啤酒的客户关联规则挖掘：路线图布尔vs.定量关联(基于处理数据的类型)buys(x,“SQLServer”)^buys(x,“DMBook”)®buys(x,“DBMiner”)[0.2%,60%]age(x,“30..39”)^income(x,“42..48K”)®buys(x,“PC”)[1%,75%]单维vs.多维关联

(例子同上)单层vs.多层分析那个品种牌子的啤酒与那个牌子的尿布有关系?各种扩展相关性、因果分析关联并不一定意味着相关或因果最大模式和闭合相集添加约束如,哪些“小东西”的销售促发了“大家伙”的买卖？关联规则挖掘—一个例子对于A

C：support=support({A

、C})=50%confidence=support({A

、C})/support({A})=66.6%Apriori的基本思想:频繁项集的任何子集也一定是频繁的最小支持度50%最小可信度50%关键步骤：挖掘频繁集频繁集:是指满足最小支持度的项目集合频繁集的子集也一定是频繁的如,如果{AB}是频繁集，则{A}{B}也一定是频繁集从1到k（k-频繁集）递归查找频繁集用得到的频繁集生成关联规则Apriori算法的基本原理Apriori算法使用称为逐层收索的迭代方法，首先寻找1-项频繁集的集合，集合记做L1，L1用于寻找两项频繁集合L2，L2用于寻找L3，如此下去，直到不能找K项频繁集合

K项频繁集候选集：每个项都有K个元素，用C表示K项频繁集：每一项都满足最小支持度的项，每个项中有K个元素，用L表示

Apriori算法分为两个阶段1.寻找频繁项集2.由频繁项集挖掘关联规则Apriori算法的基本原理如何生成频繁集(连接，剪枝)C1(1-项频繁集候选集):扫描数据库,对每个单独的项进行计数得到C1L1(1-项频繁集):从C1中删除支持度小于sup的项得到L1Ck+1(K+1项频繁集候选集)：CK+1由Lk与自身连接得到，即CK+1=Lk*Lk连接的条件是，参与连接的两个K项集合前k-1项相同，第k项不同Lk+1