数据挖掘技术概述

大数据分析和内存计算第4讲数据挖掘技术概述李国良清华大学计算机系第一页，共一百四十六页。提纲数据挖掘概览数据预处理分类（Classification）聚类（Cluster）关联规则（Association

Rule）回归（Regression）第二页，共一百四十六页。数据挖掘概览What?数据挖掘的定义Why?数据挖掘的动机How?哪些数据可以用来挖掘？数据挖掘的主要内容第三页，共一百四十六页。数据挖掘定义什么是数据挖掘（Data

Mining）？Extractionofinteresting(non-trivial,implicit,previouslyunknownandpotentiallyuseful)patternsorknowledgefromhugeamountofdata其他称谓：Knowledge

discovery(mining)

in

database(KDD),

data/pattern

analysis,

business

intelligence,

decision-support

system,

knowledge

extraction,

data

archeology,

data

dredging

and

information

harvesting

etc.第四页，共一百四十六页。模式有效性度量SimplicityE.g.,(association)rulelength,(decision)treesizeCertaintyE.g.,confidence,P(A|B)=#(AandB)/#(B),classificationreliabilityoraccuracy,rulestrength,etc.UtilityPotentialusefulness,e.g.,support(association),noisethreshold(description)NoveltyNotpreviouslyknown,surprising(usedtoremoveredundantrules)第五页，共一百四十六页。为何需要数据挖掘？数据量大缺乏理论知识数据挖掘可以帮助产生新的假说或者使数据变得有意义第六页，共一百四十六页。为何需要数据挖掘？Wearedrowningindata,butstarvinginknowledgeDataexplosion:Automateddatacollectiontoolsandmaturedatabasetechnologyleadtotremendousamountsofdataaccumulatedand/ortobeanalyzedindatabases,datawarehouses,andotherinformationrepositories.

苦恼:淹没在数据中;不能制定合适的决策!数据知识决策模式趋势事实关系模型关联规则序列目标市场资金分配贸易选择在哪儿做广告销售的地理位置金融经济政府人口统计生命周期第七页，共一百四十六页。数据挖掘的意义数据挖掘辅助社会管理促进民生改善支持商业决策推动科技进步股票趋势分析智能交通第八页，共一百四十六页。数据挖掘应用银行美国银行家协会(ABA)预测数据仓库和数据挖掘技术在美国商业银行的应用增长率是14.9％。

分析客户使用分销渠道的情况和分销渠道的容量

；建立利润评测模型；客户关系优化；风险控制等电子商务网上商品推荐；个性化网页；自适应网站…生物制药、基因研究DNA序列查询和匹配；识别基因序列的共发生性…电信欺诈甄别；客户流失…保险、零售第九页，共一百四十六页。数据挖掘应用Debt<10%ofIncomeDebt=0%GoodCreditRisksBadCreditRisksGoodCreditRisksYesYesYesNONONOIncome>$40KQQQQII123456factor1factor2factorn神经网络NeuralNetworks聚类分析ClusteringOpenAccn’tAddNewProductDecreaseUsage???Time序列分析SequenceAnalysis决策树DecisionTrees

倾向性分析

客户保留

客户生命周期管理

目标市场

价格弹性分析

客户细分

市场细分

倾向性分析

客户保留

目标市场

欺诈检测关联分析Association

市场组合分析

套装产品分析

目录设计

交叉销售第十页，共一百四十六页。数据挖掘步骤数据预处理数据清理（消除噪音或不一致数据，补缺）数据集成（多种数据源可以组合在一起）数据变换（规范化）数据规约（数据简化）数据挖掘算法（使用智能方法提取数据模式）分类、聚类、关联分析、回归预测、文本挖掘质量评估（识别提供知识的真正有趣模式）知识表示（可视化和知识表示技术）第十一页，共一百四十六页。数据质量：为何需要数据预处理？数据质量衡量：准确度:correct

or

wrong,

accurate

or

not完整度:not

recorded

unavailable一致性:some

modified

but

some

not,

dangling时效性:timely

update?可信度:how

trustable

the

data

are

correct?可解释性:how

easily

the

data

can

be

understood?第十二页，共一百四十六页。数据挖掘预处理的主要任务数据清理填写空缺的值，平滑噪声数据，识别、删除孤立点，解决不一致性数据集成集成多个数据库、数据立方体或文件数据变换规范化和聚集数据归约得到数据集的压缩表示，它小得多，但可以得到相同或相近的结果数据离散化数据归约的一部分，通过概念分层和数据的离散化来规约数据，对数字型数据特别重要第十三页，共一百四十六页。数据清洗脏数据：例如设备错误，人或者机器错误，传输错误等不完整性：属性值缺失或者只有聚集数据例如：phone=“”;噪音：包含噪声、错误或者异常值例如：salary=-10不一致性:例如：age=42，birthday=03-07-2010假值：例如：使用某一值填补缺失属性第十四页，共一百四十六页。缺失值（Incomplete/Missing

Data)数据并不总是完整的例如：数据库表中，很多条记录的对应字段没有相应值，比如销售表中的顾客收入引起空缺值的原因设备异常与其他已有数据不一致而被删除因为误解而没有被输入的数据在输入时，有些数据因为得不到重视而没有被输入对数据的改变没有进行日志记载空缺值要经过推断而补上第十五页，共一百四十六页。如何补充缺失值忽略元组：当类标号缺少时通常这么做（假定挖掘任务设计分类或描述），当每个属性缺少值的百分比变化很大时，它的效果非常差。人工填写空缺值：工作量大，可行性低使用一个全局变量填充空缺值：比如使用unknown或-∞使用属性的平均值填充空缺值使用与给定元组属同一类的所有样本的平均值使用最可能的值填充空缺值：使用像Bayesian公式或判定树这样的基于推断的方法第十六页，共一百四十六页。噪声数据噪声：一个测量变量中的随机错误或偏差引起不正确属性值的原因数据收集工具的问题数据输入错误数据传输错误技术限制命名规则的不一致其它需要数据清理的数据问题重复记录不完整的数据不一致的数据第十七页，共一百四十六页。如何处理噪声数据分箱:firstsortdataandpartitioninto(equi-depth)binsthenonecansmoothbybinmeans,smoothbybinmedian,smoothbybinboundaries,etc.聚类detectandremoveoutliers人机融合detectsuspiciousvaluesandcheckbyhuman(e.g.,dealwithpossibleoutliers)回归smoothbyfittingthedataintoregressionfunctions第十八页，共一百四十六页。分箱(Binning)等宽Equal-width(distance)partitioning:DividestherangeintoNintervalsofequalsize:uniformgridifAandBarethelowestandhighestvaluesoftheattribute,thewidthofintervalswillbe:W=(B–A)/N.Themoststraightforward,butoutliersmaydominatepresentationSkeweddataisnothandledwell.等深Equal-depth(frequency)partitioning:DividestherangeintoNintervals,eachcontainingapproximatelysamenumberofsamplesGooddatascalingManagingcategoricalattributescanbetricky.第十九页，共一百四十六页。数据平滑的分箱方法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第二十页，共一百四十六页。聚类：Cluster

Analysis每个簇中的数据用其中心值代替忽略孤立点先通过聚类等方法找出孤立点。这些孤立点可能包含有用的信息。人工再审查这些孤立点第二十一页，共一百四十六页。Regression通过构造函数来符合数据变化的趋势，这样可以用一个变量预测另一个变量。线性回归多线性回归非线性回归xyy=x+1X1Y1Y1’第二十二页，共一百四十六页。数据集成实体识别元数据可帮助避免错误知识图谱属性冗余相关分析数据重复（元组冗余）数据值冲突的检测与处理表示、比例或编码不同第二十三页，共一百四十六页。数据变换（规范化）平滑：去掉数据中的噪声。技术包括分箱、回归、聚类。聚集：对数据进行汇总或聚集。数据泛化（概化）：使用概念分层，用高层概念替换低层或“原始”数据。规范化：将属性数据按比例缩放，使之落入一个小的特定区间。最小-最大、Z-Score、按小数定标规范化。第二十四页，共一百四十六页。数据变换平滑，聚集数据概化，规范化属性构造(特征构造)有限区间的归一化：无限区间的归一化：模糊隶属度：第二十五页，共一百四十六页。数据规约海量数据代表性数据对海量数据进行复杂的数据分析和挖掘将需要很长时间，使得这种分析不现实或不可行。数据归约技术可以用来得到数据集的归约表示，它小得多，但仍接近保持原数据的完整性。对归约后的数据集挖掘将更有效，并产生相同（或几乎相同）的结果。第二十六页，共一百四十六页。数据规约数据归约策略：（1）数据立方体聚集：对数据立方体做聚集操作（2）属性子集选择：检测并删除不相关、弱相关或冗余的属性和维。（3）维度归约：删除不重要的属性（4）数值归约：用规模较小的数据表示、替换或估计原始数据（5）离散化和概念分层产生属性的原始数值用区间值或较高层的概念替换第二十七页，共一百四十六页。数据立方体据立方体存储多维聚集信息，提供对预计算的汇总数据进行快速访问。如：立方体内存储季度销售额，若对年销售额感兴趣，可对数据执行聚集操作，例如sum()等。第二十八页，共一百四十六页。属性子集选择通过删除不相关或冗余的属性（或维）减小数据集。其目标是找出最小属性集，使得数据类的概率分布尽可能地接近使用所有属性得到的原分布。通过穷举搜索找出有属性的最佳子集是不现实的。通常采用压缩搜索空间的启发式算法。如贪心算法：从局部最优到全局最优。逐步向前选择逐步向后删除向前选择和向后删除的结合决策树归纳第二十九页，共一百四十六页。维度规约维度归约使用数据编码或变换，以便得到原数据的归约或“压缩”表示。分为无损和有损两种。主要方法：串压缩：无损，但只允许有限的数据操作。小波变换（DWT）：有损，适合高维数据。主成分分析（PCA）：有损，能更好地处理稀疏数据。第三十页，共一百四十六页。数值规约通过选择替代的、“较小的”数据表示形式来减少数据量。可以分为参数方法和非参数方法。参数方法：回归（regression）和对数线性模型非参数方法：直方图、聚类、抽样第三十一页，共一百四十六页。离散化离散化的用途：（1）适应某些仅接受离散值的算法；（2）减小数据的尺度。离散化的方法包括几下几种。（1）等距分割；（2）聚类分割；（3）直方图分割；（4）基于熵的分割；（5）基于自然属性的分割。第三十二页，共一百四十六页。抽样用数据的小得多的随机样本（子集）不是大型数据集。抽样方法s个样本无放回简单随机抽样s个样本有放回简单随机抽样聚类抽样分层抽样第三十三页，共一百四十六页。分类第三十四页，共一百四十六页。分类分类是指将数据映射到预先定义好的群组或类。在分析测试数据之前，类别就已经被确定了，所以分类统称被称作有指导的学习。分类算法要求基于数据属性来定义类别。分类算法通常通过观察已知所属类别的数据的特征来描述类别。第三十五页，共一百四十六页。分类应用分类具有广泛的应用，例如医疗诊断、信用卡系统的信用分级、图像模式识别等。为了识别乘客是否是潜在的恐怖分子或罪犯，机场安全摄像站需要对乘客的脸部进行扫描并辨识脸部的基本模式（例如双眼间距、嘴的大小及形状、头的形状），然后将得到的模式与数据库中的已知恐怖分子或罪犯的模式进行逐个比较，看看是否与其中的某一模式相匹配。第三十六页，共一百四十六页。分类步骤1．建立一个模型，描述预定的数据类集或概念集数据元组也称作样本、实例或对象。为建立模型而被分析的数据元组形成训练数据集。训练数据集中的单个元组称作训练样本，假定每个元组属于一个预定义的类，由一个称作类标号。通过分析训练数据集来构造分类模型，可用分类规则、决策树或数学公式等形式提供。2.使用模型进行分类首先评估模型（分类法）的预测准确率。将已知的类标号与该样本的学习模型类预测比较准确率等于测试集的样本中被模型正确分类的百分比测试集应该与训练集的内容相互独立，否则会出现过分适应的情况如果认为模型的准确率可以接受，就可以用它对类标号未知的数据元组或对象进行分类。第三十七页，共一百四十六页。（1）模型的构建TrainingDataClassificationAlgorithmsIFrank=‘professor’ORyears>6THENtenured=‘yes’

Classifier(Model)NAMERANKYEARSTENUREDMikeAssistantProf3noMaryAssistantProf7yesBillProfessor2yesJimAssociateProf7yesDaveAssistantProf6noAnneAssociateProf3no第三十八页，共一百四十六页。（2）利用模型分类ClassifierTestingDataUnseenData(Jeff,Professor,4)Tenured?第三十九页，共一百四十六页。分类方法评价预测的准确率这涉及模型正确地预测新的或先前未见过的数据的类标号的能力速度构造模型的速度利用模型进行分类的速度强壮性给定噪声数据或具有空缺值的数据，模型正确预测的能力可伸缩性当给定大量数据时，有效地构造模型的能力可解释性

涉及学习模型提供的理解和洞察的层次第四十页，共一百四十六页。分类器性能评价方式准确率和召回率-混淆矩阵等给定一个类Cj和一个数据库元组ti，ti可能被分类器判定为属于Cj或不属于Cj，其实ti本身可能属于Cj或不属于Cj，这样就会产生如下一些情况：真正:判定ti在Cj中，实际上的确在其中。假正:判定ti在Cj中，实际上不在其中。真负:判定ti不在Cj中，实际上不在其中。假负:判定ti不在Cj中，实际上的确在其中。准确率:P=A/(A+B)召回率:R=A/(A+C)第四十一页，共一百四十六页。评估分类方法的准确性保持方法给定数据随机划分为两个集合：训练集(2/3)和测试集(1/3)训练集导出分类法，测试集对其准确性进行评估k-折交叉验证初始数据被划分为k个不相交的，大小大致相同的子集S1,S2…Sk进行k次训练和测试，第i次时，以Si做测试集，其他做训练集准确率为k次迭代正确分类数除以初始数据集样本总数第四十二页，共一百四十六页。分类方法第四十三页，共一百四十六页。基于距离的分类方法与一个类中的成员和另一个类中的成员之间的相似性相比，被映射到同一个类中的成员彼此之间被认为是更加相似的。相似性（距离）度量可以用来识别数据库中不同成员之间的“相似程度”。第四十四页，共一百四十六页。基于距离的分类方法的直观解释（a）类定义（b）待分类样例（c）分类结果第四十五页，共一百四十六页。距离计算方法闵可夫斯基距离:当p=2时，为欧几里得距离当p=1时，为曼哈顿距离当p->∞时，为切比雪夫距离向量内积：夹角余弦：Jaccard：还有信息熵、相关系数等其他的度量方法第四十六页，共一百四十六页。基于距离的分类方法的一般性描述算法

基于距离的分类算法输入：每个类的中心C1，…，Cm；待分类的元组t。

输出：输出类别c。

（1）dist=∞；//距离初始化（2）FORi:=1tomDO（3） IFdis(ci，t)<distTHENBEGIN（4） c←Ci；（5） dist←dist(Ci，t)；（6） END.算法通过对每个元组和各个类的中心来比较，从而可以找出他的最近的类中心，得到确定的类别标记。第四十七页，共一百四十六页。K近邻算法（KNN）K

Nearestneighbor(KNN)通过计算每个训练数据到待分类元组的距离，取和待分类元组距离最近的K个训练数据，K个数据中哪个类别的训练数据占多数，则待分类元组就属于哪个类别。训练样本用n维数值属性描述。每个样本代表n维空间的一个点。所有的训练样本都放在n维模式空间中。给定一个样本，k-最临近分类法搜索模式空间，找出最接近未知样本的k个训练样本。第四十八页，共一百四十六页。K近邻算法（KNN）要求的信息训练集距离计算值要获取的最邻近的邻居的数目k一个未知的记录进行分类计算与其它训练记录之间的距离识别出k个最近的邻居使用最近邻居的类标号来标识未知元组的类（bytakingmajorityvote）第四十九页，共一百四十六页。K近邻算法（KNN）算法K-近邻分类算法输入：

训练数据T；近邻数目K；待分类的元组t。

输出：

输出类别c。

（1）N=∅；（2）FOReachd∈TDOBEGIN（3）IF|N|≤KTHEN（4）

N=N∪{d}；

（5）ELSE（6）

IF

u∈Nsuchthatsim(t，u)<sim(t，d)THENBEGIN（7）

N=N-{u}；（8）

N=N∪{d}；（9） END（10）END（11）c=classtowhichthemostu∈N.第五十页，共一百四十六页。K近邻算法（KNN）K值的选取如果k过于小，那么将会对数据中存在的噪声过于敏感如果k过大，邻居中可能包含其他类的点一个经验的取值法则为k≤，q为训练元组的数目。商业算法通常以10作为默认值。第五十一页，共一百四十六页。决策树第五十二页，共一百四十六页。决策树（Decision

Tree）决策树是以实例为基础的归纳学习算法。它从一组无次序、无规则的元组中推理出决策树表示形式的分类规则。类似于流程图的树结构，其中每个内部节点表示在一个属性上的测试，每个分支代表一个测试输出，而每个树叶节点代表类或类分布。树的最顶层节点是根节点。第五十三页，共一百四十六页。决策树例如，在贷款申请中，要对申请的风险大小做出判断。收入>40000高负债工作时间>5年是否是否“年收入大于￥40000”并且“高负债”的用户被认为是“高风险”；“年收入小于￥40000”但“工作时间大于5年”的申请，是“低风险”；NYYNNY第五十四页，共一百四十六页。决策树buys_computer的决策树示意

Age?

Credit_rating?

student?

yes

no

yesyes

no

<=30?

>40

30~40yes

no

fairexcellent

第五十五页，共一百四十六页。决策树决策树（decisiontree）1986年Quinlan提出了著名的ID3算法。在ID3算法的基础上，1993年Quinlan又提出了C4.5算法。为了适应处理大规模数据集的需要，后来又提出了若干改进的算法，其中SLIQ(super-visedlearninginquest)和SPRINT(scalableparallelizable

inductionofdecisiontrees)是比较有代表性的两个算法。第五十六页，共一百四十六页。决策树的步骤使用决策树进行分类分为两步：第1步：利用训练集建立并精化一棵决策树，建立决策树模型。这个过程实际上是一个从数据中获取知识，进行机器学习的过程。第2步：利用生成完毕的决策树对输入数据进行分类。对输入的记录，从根结点依次测试记录的属性值，直到到达某个叶结点，从而找到该记录所在的类。

第五十七页，共一百四十六页。决策树算法递归执行的终止条件（停止分支的条件）对于给定的节点，所有的例子都属于同一个类虽然对于某一个节点当前的例子不属于同一个类，但是已经没有属性可用来选择继续进行分支处理第五十八页，共一百四十六页。分裂属性选择选择属性的方法选择具有最大信息增益的属性作为当前节点的测试属性该属性使得对结果划分中的样本分类所需的信息量最小，并反映划分的最小随机性。用信息增益这种信息论的理论方法，使得对一个对象分类所需要的期望测试数目达到最小，并确保找到一棵简单的树。第五十九页，共一百四十六页。分裂属性选择怎样计算信息增益（informationgain）信息增益被定义为原始分割的熵与划分以后各分割的熵累加得到的总熵之间的差。信息增益是指划分前后进行正确预测所需的信息量之差。选择具有最高信息增益的属性作为当前节点的测试属性。第六十页，共一百四十六页。信息增益的计算

设S是有s个训练样本数据的集合，类标号属性具有m个不同值，定义m个不同类Ci（i=1,2,…,m），si是类Ci中的样本数，则对一个给定的训练样本分类所需要的期望信息为：

其中pi是任意样本属于Ci的概率，可用si/s来估计第六十一页，共一百四十六页。决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第六十二页，共一百四十六页。决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买决策属性“买计算机？”。该属性分两类：买/不买S1(买)=641S2（不买）=383S=S1+S2=1024P1=641/1024=0.6260P2=383/1024=0.3740I(S1,S2)=I(641,383)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9537第1步计算决策属性的熵第六十三页，共一百四十六页。决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第2步计算条件属性的熵条件属性共有4个。分别是年龄、收入、学生、信誉。分别计算不同属性的信息增益。第六十四页，共一百四十六页。决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第2-1步计算年龄的熵年龄共分三个组：

青年、中年、老年青年买与不买比例为128/256S1(买)=128S2（不买）=256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9183第六十五页，共一百四十六页。决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第2-2步计算年龄的熵年龄共分三个组：

青年、中年、老年中年买与不买比例为256/0S1(买)=256S2（不买）=0S=S1+S2=256P1=256/256P2=0/256I(S1,S2)=I(256，0)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0第六十六页，共一百四十六页。决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第2-3步计算年龄的熵年龄共分三个组：

青年、中年、老年老年买与不买比例为125/127S1(买)=125S2（不买）=127S=S1+S2=252P1=125/252P2=127/252I(S1,S2)=I(125，127)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9157第六十七页，共一百四十六页。决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第2-4步计算年龄的熵年龄共分三个组：

青年、中年、老年所占比例青年组384/1025=0.375中年组256/1024=0.25老年组384/1024=0.375计算年龄的平均信息期望E（年龄）=0.375*0.9183+0.25*0+0.375*0.9157=0.6877G（年龄信息增益）=0.9537-0.6877=0.2660（1）第六十八页，共一百四十六页。决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第3步计算收入的熵收入共分三个组：

高、中、低E（收入）=0.9361收入信息增益=0.9537-0.9361=0.0176(2)第六十九页，共一百四十六页。决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第4步计算学生的熵学生共分二个组：

学生、非学生E（学生）=0.7811年龄信息增益=0.9537-0.7811=0.1726（3）第七十页，共一百四十六页。决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第5步计算信誉的熵信誉分二个组：

良好，优秀E（信誉）=0.9048信誉信息增益=0.9537-0.9048=0.0453（4）第七十一页，共一百四十六页。决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第6步计算选择节点

年龄信息增益=0.9537-0.6877=0.2660（1）收入信息增益=0.9537-0.9361=0.0176（2）年龄信息增益=0.9537-0.7811=0.1726（3）信誉信息增益=0.9537-0.9048=0.0453（4）第七十二页，共一百四十六页。决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买年龄青年中年老年买/不买买买/不买叶子第七十三页，共一百四十六页。决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买青年买与不买比例为128/256S1(买)=128S2（不买）=256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9183第七十四页，共一百四十六页。决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128青中否良不买64青低是良买64青中是优买如果选择收入作为节点分高、中、低平均信息期望（加权总和）：

E(收入）=0.3333*0+0.5*0.9183+0.1667*0=0.4592Gain(收入)=I(128,256)-E(收入)=0.9183

–0.4592=0.4591I(0,128)=0比例:128/384=0.3333I(64,128)=0.9183比例:192/384=0.5I(64,0)=0比例:64/384=0.1667注意第七十五页，共一百四十六页。决策树算法计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买年龄青年中年老年学生买信誉叶子否是优良买不买买/不买买叶子叶子叶子第七十六页，共一百四十六页。决策树分类规则提取决策树所表示的分类知识可以被抽取出来并可用IF-THEN分类规则形式加以表示。从决策树的根结点到任一个叶结点所形成的一条路径就构成了一条分类规则。沿着决策树的一条路径所形成的属性-值对就构成了分类规则条件部分（IF部分）中的一个合取项，叶结点所标记的类别就构成了规则的结论内容（THEN部分）。IF-THEN分类规则表达方式易于被人理解，且当决策树较大时，IF-THEN规则表示形式的优势就更加突出。第七十七页，共一百四十六页。贝叶斯分类第七十八页，共一百四十六页。贝叶斯分类贝叶斯定理

贝叶斯定理给出了如下计算P(C|X)的简单有效的方法:

P(C):是先验概率，或称C的先验概率。

P(X):样本数据被观察的概率。

P(X|C)代表假设C成立的情况下，观察到X的概率。

P(C|X)是后验概率，或称条件X下C的后验概率。

后验概率P(C|X)比先验概率P(C)基于更多的信息。

P(C)是独立于X的。第七十九页，共一百四十六页。朴素贝叶斯分类朴素贝叶斯分类的工作过程如下：(1)每个数据样本用一个n维特征向量X={x1,x2…xn}表示，分别描述n个属性A1，…，An样本的n个度量。(2)假定有m个类C1，C2，…，Cm，给定一个未知的数据样本X（即没有类标号），分类器将预测X属于具有最高后验概率（条件X下）的类。朴素贝叶斯分类将未知的样本分配给类Ci（1≤i≤m）当且仅当P(Ci|X)>P(Cj|X)，j≠i。即最大化P(Ci|X)P(Ci|X)最大的类Ci称为最大后验假定。第八十页，共一百四十六页。朴素贝叶斯分类(3)由于P(X)对于所有类为常数，P(X|Ci)*P(Ci)最大即可。如果Ci类的先验概率未知，则通常假定这些类是等概率的，即P(C1)=P(C2)=…=P(Cm)，因此问题就转换为对P(X|Ci)的最大化（P(X|Ci)常被称为给定Ci时数据X的似然度，而使P(X|Ci)最大的假设Ci称为最大似然假设）。否则，需要最大化P(X|Ci)*P(Ci)。类的先验概率可以用P(Ci)=si/s计算，其中si是类Ci中的训练样本数，而s是训练样本总数。第八十一页，共一百四十六页。朴素贝叶斯分类（4）给定具有许多属性的数据集，计算P(X|Ci)的开销可能非常大。为降低计算P(X|Ci)的开销，可以做类条件独立的朴素假定。给定样本的类标号，假定属性值相互条件独立，即在属性间，不存在依赖关系。这样概率P(x1|Ci)，P(x2|Ci)，……，P(xn|Ci)由训练样本估值。第八十二页，共一百四十六页。如果Ak是离散属性，则P(xk|Ci)=sik/si，其中sik是在属性Ak上具有值xk的类Ci的训练样本数，si是Ci中的训练样本数。

如果Ak是连续值属性，常用的处理方法有两种：一是对其离散化，然后按照离散值处理；另一种假定这一属性服从某一分布，通常假定该属性服从高斯分布。(5)对未知样本X分类，也就是对每个类Ci，计算P(X|Ci)*P(Ci)。样本X被指派到类Ci，当且仅当P(Ci|X)>P(Cj|X)，1≤j≤m，j≠i。即X被指派到其P(X|Ci)*P(Ci)最大的类。第八十三页，共一百四十六页。朴素贝叶斯分类举例希望分类的未知样本为:X=（age=“<=30”，income=“medium”，student=“yes”，credit_rating=“fair”）思路:计算每一个类的P(Ci|X)=P(X|Ci)P(Ci)/P(X),Ci代表任意一个类，X代表需要判断的查询条件第八十四页，共一百四十六页。朴素贝叶斯分类举例设C1对应于类buys_computer=“yes”，C2对应于类buys_computer=“no”。(1)需要最大化P(X|Ci)*P(Ci)，i=1，2。每个类的先验概率P(Ci)可以根据训练样本计算： P(buys_computer=”yes”)=9/14=0.643， P(buys_computer=”no”)=5/14=0.357。

第八十五页，共一百四十六页。朴素贝叶斯分类举例(2)为计算P(X|Ci)，i=1，2，计算下面的条件概率：P(age<=30|buys_computer=“yes”)=2/9=0.222，P(age<=30”|buys_computer=“no”)=3/5=0.600，P(income=“medium”|buys_computer=“yes”)=4/9=0.444，P(income=“medium”|buys_computer=“no”)=2/5=0.400，P(student=“yes”|buys_computer=“yes”)=6/9=0.677，P(student=“yes”|buys_computer=“no”)=1/5=0.200，P(credit_rating=“fair”|buys_computer=“yes”)=6/9=0.667，P(credit_rating=“fair”|buys_computer=“no”)=2/5=0.400。

第八十六页，共一百四十六页。朴素贝叶斯分类举例(3)假设条件独立性，使用以上概率，得到：P(X|buys_computer=“yes”)=0.222*0.444*0.667*0.667=0.044，P(X|buys_computer=“no”)=0.600*0.400*0.200*0.400=0.019，P(X|buys_computer=“yes”)*P(buys_computer=“yes”)=

0.044*0.643=0.028，P(X|buys_computer=“no”)*P(buys_computer=“no”)=

0.019*0.357=0.007。因此，对于样本X，朴素贝叶斯分类预测buys_computer=“yes”X=（age=“<=30”,income=“medium”,student=“yes”,credit_rating=“fair”）第八十七页，共一百四十六页。聚类第八十八页，共一百四十六页。聚类：Cluster聚类就是对大量未知标注的数据集，按数据的内在相似性将数据集划分为多个类别在同一个类中，对象之间具有相似性；不同类的对象之间是相异的。聚类分析把一个给定的数据对象集合分成不同的簇；聚类是一种无监督分类法:没有预先指定的类别；典型的应用作为一个独立的分析工具，用于了解数据的分布；

作为其它算法的一个数据预处理步骤；第八十九页，共一百四十六页。聚类图示聚类中没有任何指导信息，完全按照数据的分布进行类别划分第九十页，共一百四十六页。聚类与分类的区别有类别标记和无类别标记;有监督与无监督;（有训练语料与无训练语料）TrainAndClassification（分类）;NoTrain（聚类）;第九十一页，共一百四十六页。聚类分析为达到全局最优，基于划分的聚类会要求穷举所有可能的划分。聚类技术将数据元组视为对象。它将对象划分为群或聚类，使得在一个聚类中的对象“类似”，但与其它聚类中的对象“不类似”。绝大多数应用采用了以下两个比较流行的基于划分的方法，这些基于划分的聚类方法对在中小规模的数据库中发现球状簇很适用。（1）k-means算法，在该算法中，每个簇用该簇中对象的平均值来表示。（2）k-medoids算法，在该算法中，每个簇用接近聚类中心的一个对象来表示。第九十二页，共一百四十六页。K-means初始参数-类别数&初始类别中心;聚类有效性函数-最小误差;优点：

聚类时间快;缺点：对初始参数敏感;容易陷入局部最优;

第九十三页，共一百四十六页。K-means步骤1设置初始类别中心和类别数;2根据类别中心对数据进行类别划分;3重新计算当前类别划分下每类的中心;4在得到类别中心下继续进行类别划分;5如果连续两次的类别划分结果不变则停止算法;否则循环2～5;O（kndt）第九十四页，共一百四十六页。第九十五页，共一百四十六页。初始值敏感初始化4个类别中心;左侧的全体数据仅与第一个类别中心相似;第九十六页，共一百四十六页。K-mediods步骤1任意选取K个对象作为medoids;2将余下的对象分到各个类中去（根据与medoid最相近的原则）;3对于每个类（Oi）中，顺序选取一个Or，计算用Or代替Oi后的消耗—E（Or）。选择E最小的那个Or来代替Oi。4重复2-3直到medoids不变;O（n2dt）第九十七页，共一百四十六页。聚类方法性能评价一个好的聚类方法要能产生高质量的聚类结果——簇，这些簇要具备以下两个特点：高的簇内相似性低的簇间相似性

聚类结果的好坏取决于该聚类方法采用的相似性评估方法以及该方法的具体实现；聚类方法的好坏还取决于该方法是能发现某些还是所有的隐含模式；第九十八页，共一百四十六页。聚类方法性能评价可伸缩性能够处理不同类型的属性能发现任意形状的簇在决定输入参数的时候，尽量不需要特定的领域知识；能够处理噪声和异常对输入数据对象的顺序不敏感能处理高维数据能产生一个好的、能满足用户指定约束的聚类结果结果是可解释的、可理解的和可用的第九十九页，共一百四十六页。聚类评价准备率：找到正确的结果数/找到结果数召回率：找到正确的结果数/正确结果数最小误差:衡量不同类别的数据与类别中心的误差和;最小方差:衡量同一类别内数据的平均误差和;第一百页，共一百四十六页。常用的相似性度量方法余弦夹角：Dice系数：Jaccard系数：第一百零一页，共一百四十六页。相似性度量方法EuclideanDistance交叉熵Cosine数据表示为向量，向量中某一维对应数据某一特征或属性仅计算了数据向量中属于同一维度特征的权值差距;第一百零二页，共一百四十六页。聚类分析（续）基于层次的方法：层次的方法对给定数据集合进行层次的分解。根据层次的分解如何形成，层次的方法可以被分为凝聚或分裂方法。

（Chameleon，CURE，BIRCH）

基于密度的方法：只要临近区域的密度超过某个阈值，就继续聚类。避免仅生成球状聚类。（DBSCAN，OPTICS，DENCLUE）基于网格的方法：基于网格的方法把对象空间量化为有限数目的单元，所有的聚类操作都在这个量化的空间上进行。这种方法的主要优点是它的处理速度很快。（STING，CLIQUE，WaveCluster）基于模型的方法：为每个簇假设一个模型，发现数据对模型的最好匹配。（COBWEB，CLASSIT，AutoClass）

第一百零三页，共一百四十六页。DBSCAN基于密度的簇是密度相连的点的集合主要思想寻找被低密度区域分离的高密度区域只要临近区域的密度（单位大小上对象或数据点的数目）超过某个阈值，就继续聚类

第一百零四页，共一百四十六页。DBSCAN两个参数：Eps:邻域的最大半径MinPts:一个核心对象以Eps为半径的邻域内的最小顶点数MinPts=5Eps=1cmpq第一百零五页，共一百四十六页。DBSCAN密度=制定半径(Eps)内点的个数如果一个对象的Eps邻域至少包含最小数目MinPts个对象，则称该对象为核心对象（Corepoint）如果一个对象是非核心对象,但它的邻域中有核心对象，则称该对象为边界点（Borderpoint

）除核心对象和边界点之外的点是噪声点（Noisepoint

）第一百零六页，共一百四十六页。DBSCAN第一百零七页，共一百四十六页。DBSCAN密度可达的（Density-reachable）对于对象p和核心对象q(关于E和MinPts),我们称p是从q(关于E和MinPts)直接密度可达，若对象p在对象q的E邻域内。如果存在一个对象链p1,…,pn,p1=q,pn=p

，pi+1是从pi关于Eps和MinPts

直接密度可达的，则对象p是从对象q关于Eps和MinPts

密度可达的。密度可达性是直接密度可达性的传递闭包，这种关系是非对称的。只有核心对象之间是相互可达的。pqp1第一百零八页，共一百四十六页。DBSCAN密度相连的（Density-connected）如果对象集合D中存在一个对象o，使得对象p和q是从o关于Eps

和MinPts密度可达的，那么对象p和q是关于Eps

和MinPts密度相连的。密度相连性是一个对称的关系。pqo第一百零九页，共一百四十六页。DBSCANDBSCAN算法描述：输入：包含n个对象的数据库，半径ε，最少数目MinPts。输出：所有生成的簇，达到密度要求。1.REPEAT2.从数据库中抽取一个未处理过的点；3.IF抽出的点是核心点THEN找出所有从该点密度可达的对象，形成一个簇4.ELSE抽出的点是边缘点(非核心对象)，跳出本次循环，寻找下一点；5.UNTIL所有点都被处理；第一百一十页，共一百四十六页。基于密度方法的聚类-DBSCAN

下面给出一个样本事务数据库（见下表），对它实施DBSCAN算法。根据所给的数据通过对其进行DBSCAN算法，以下为算法的步骤（设n=12，用户输入ε=1，MinPts=4）

序号属性1属性2121251312422532642752862913102311531224样本事务数据库第一百一十一页，共一百四十六页。DBSCAN聚类过程第1步，在数据库中选择一点1，由于在以它为圆心的，以1为半径的圆内包含2个点（小于4），因此它不是核心点，选择下一个点。第2步，在数据库中选择一点2，由于在以它为圆心的，以1为半径的圆内包含2个点，因此它不是核心点，选择下一个点。第3步，在数据库中选择一点3，由于在以它为圆心的，以1为半径的圆内包含3个点，因此它不是核心点，选择下一个点。第一百一十二页，共一百四十六页。DBSCAN聚类过程第4步，在数据库中选择一点4，由于在以它为圆心的，以1为半径的圆内包含5个点，因此它是核心点，寻找从它出发可达的点（直接可达4个，间接可达3个），聚出的新类{1，3，4，5，9，10，12}，选择下一个点。第一百一十三页，共一百四十六页。DBSCAN聚类过程第5步，在数据库中选择一点5，已经在簇1中，选择下一个点。第6步，在数据库中选择一点6，由于在以它为圆心的，以1为半径的圆内包含3个点，因此它不是核心点，选择下一个点。第一百一十四页，共一百四十六页。DBSCAN聚类过程第7步，在数据库中选择一点7，由于在以它为圆心的，以1为半径的圆内包含5个点，因此它是核心点，寻找从它出发可达的点，聚出的新类{2，6，7，8，11}，选择下一个点。第一百一十五页，共一百四十六页。DBSCAN聚类过程第8步，在数据库中选择一点8，已经在簇2中，选择下一个点。第9步，在数据库中选择一点9，已经在簇1中，选择下一个点。第10步，在数据库中选择一点10，已经在簇1中，选择下一个点。第11步，在数据库中选择一点11，已经在簇2中，选择下一个点。第12步，选择12点，已经在簇1中，由于这已经是最后一点所有点都以处理，程序终止。序号属性1属性2121251312422532642752862913102311531224第一百一十六页，共一百四十六页。基于密度方法的聚类-DBSCAN步骤选择的点在ε中点的个数通过计算可达点而找到的新簇112无222无333无445簇C1：{1，3，4，5，9，10，12}553已在一个簇C1中663无775簇C2：{2，6，7，8，11}882已在一个簇C2中993已在一个簇C1中10104已在一个簇C1中，11112已在一个簇C2中12122已在一个簇C1中算法执行过程：第一百一十七页，共一百四十六页。DBSCANOriginalPointsClusters特点：抗噪声能处理任意形状聚类第一百一十八页，共一百四十六页。关联规则第一百一十九页，共一百四十六页。关联规则：Association

Rule关联规则挖掘：在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性、或因果结构。应用：购物篮分析、交叉销售、产品目录设计等。举例：

规则形式:“Body

=>

Head[support,confidence]”buys(x,“diapers”)=>buys(x,“beers”)[0.5%,60%]major(x,“CS”)^takes(x,“DB”)=>grade(x,“A”)[1%,75%]第一百二十页，共一百四十六页。规则度量：支持度与可信度查找所有的规则

X&Y=>Z具有最小支持度和可信度支持度,

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

c,

包含{X、Y}的交易中也包含Z的条件概率设最小支持度为50%,最小可信度为50%,则可得到A=>C(50%,66.6%)C=>A(50%,100%)买尿布的客户二者都买的客户买啤酒的客户第一百二十一页，共一百四十六页。关联规则挖掘问题就是根据用户指定的最小支持度和最小可信度来寻找强关联规则。关联规则挖掘问题可以划分成两个子问题：1.发现频繁项目集:通过用户给定最小支持度，寻找所有频繁项目集或者最大频繁项目集。2.生成关联规则:通过用户给定最小可信度，在频繁项目集中，寻找关联规则。第1个子问题是近年来关联规则挖掘算法研究的重点。关联规则挖掘基本过程第一百二十二页，共一百四十六页。经典的发现频繁项目集算法Apriori算法是通过项目集元素数目不断增长来完成频繁项目集发现的。首先产生1_频繁项目集L1，然后产生2_频繁项目集L2，直到不能再扩展频繁项目集的元素数目为止。TIDItemset1001，3，42002，3，53001，2，3，54002，51994年，Agrawal等人提出了著名的Apriori算法。第一百二十三页，共一百四十六页。Apriori算法例子DatabaseDC1L1L2C2ScanDL3ScanDC3ScanDC4ScanDScanDØL4Minsupport=50%

C1：1-候选集L1：1-频繁项目集C2：2-候选集L2：2-频繁项目集C3：3-候选集L3：3-频繁项目集C4：4-候选集L4：4-频繁项目集L3是最大频繁项目集第一百二十四页，共一百四十六页。

根据上面介绍的关联规则挖掘的两个步骤，在得到了所有频繁项目集后，可以按照下面的步骤生成关联规则：对于每一个频繁项目集l，生成其所有的非空子集；对于l

的每一个非空子集x，计算Conference（x），如果Confidence（x）≥minconfidence，那么“x(l-x)”成立。关联规则生成算法:从给定的频繁项目集中生成强关联规则该算法的核心是genrules递归过程，它实现一个频繁项目集中所有强关联规则的生成。Rule-generate（L，minconf）（1）FOReachfrequentitemsetlkinL（2）genrules（lk

，lk）;关联规则的生成问题第一百二十五页，共一百四十六页。Rule-generate算法例子Minconfidence=80%序号lkxm-1ConfidenceSupport规则（是否是强规则）1235267%50%235（否）2235367%50%325（否）3235567%50%523（否）423523100%50%235（是）52352567%