1、第7章 统计技术 之二贝叶斯分析聚类技术数据挖掘中的统计技术与机器学习技术清华大学出版社7.2 贝叶斯分析(Bayesian Analysis)一种参数估计方法。将关于未知参数的先验信息与样本信息相结合,根据贝叶斯公式,得出后验信息,然后根据后验信息去推断未知参数。在决策支持、风险评估、模式识别等方面都得到了很广泛的应用,被用来建立分类模型,就是著名的贝叶斯分类器(式7.13)贝叶斯分类器(Bayes Classifier)一种简单、功能强大的有指导分类技术。假定所有输入属性的重要性相等,且彼此是独立的。2022年12月14日星期三第2页,共41页)()()|()|(EPHPHEPEHP(式7
2、.13)清华大学出版社7.2 贝叶斯分析其中H为要检验的假设,E为与假设相关的数据样本。从分类的角度考察假设H就是因变量,代表着预测类;数据样本E是输入实例属性值的集合;P(E|H)是给定输入实例属性值E时,假设H为真的条件概率;P(H)为先验概率(priori probability),表示在任何输入属性值E出现之前假设的概率。条件概率和先验概率可以通过训练数据计算出来。2022年12月14日星期三第3页,共41页【例7.4】基于信用卡账单促销数据集(表7.4),应用贝叶斯分类器,判断一个新实例的性别Sex。该实例的输入属性值为Magazine Promotion=Yes,Watch Pro
3、motion=Yes,Life Insurance Promotion=No 以及 Credit Card Insurance=No。清华大学出版社表7.4 用于贝叶斯分类器的数据集2022年12月14日星期三第5页,共41页表7.4用于贝叶斯分类器的数据集Magazine Promotion Watch PromotionLife Insurance PromotionCredit Card InsuranceSexYesNoNoNoMaleYesYesYesYesFemaleNoNoNoNoMaleYesYesYesYesMaleYesNoYesNoFemaleNoNoNoNoFemale
4、YesYesYesYesMaleNoNoNoNoMaleYesNoNoNoMaleYesYesYesNoFemale清华大学出版社1、使用贝叶斯定理解决例7.4问题(1)找出先验信息。将Sex作为输出属性。表7.5依据表7.4,计算类实例个数与实例总数之比,得出每个输入属性的输出属性值的分布。(2)确定要检验的假设。要检验的假设H有两个:客户Sex为Male;客户Sex为Female。要判断新客户的性别Sex,比较两个概率值 和 的大小,概率值大的,其假设H成立。(3)计算 和 两个概率值。计算贝叶斯公式(式7.13)中的条件概率P(E|H)、先验概率P(H)和P(E),即计算P(E|Sex=
5、Male)、P(E|Sex=female)、P(sex=male)、P(Sex=Female)和 Sex=Male 及 Sex=Female 的样本数据出现的概率P(E)。可认为样本集中男女出现比例相同,则两个P(E)值相等。2022年12月14日星期三第6页,共41页)|(EMaleSexP)|(EFemaleSexP清华大学出版社1、使用贝叶斯定理解决例7.4问题 MagazinePromotionWatchPromotionLife InsurancePromotionCredit CardInsuranceSexMaleFemaleMaleFemaleMaleFemaleMaleFem
6、aleYes43222321No21424143概率:yes/total4/63/42/62/42/63/42/61/4概率:no/total2/61/44/62/44/61/44/63/42022年12月14日星期三第7页,共41页表7.5属性sex的计数和概率 计算P(E|Sex=Male)和P(Sex=Male)P(E|Sex=Male)=(4/6)(2/6)(4/6)(4/6)=8/81P(Sex=Male)=6/10=3/5 计算P(E|Sex=Female)和P(Sex=Female)P(E|Sex=Female)=(3/4)(2/4)(1/4)(3/4)=9/128P(Sex=F
7、emale)=4/10=2/5清华大学出版社1、使用贝叶斯定理解决例7.4问题(4)根据贝叶斯公式计算两个P(H|E),即P(Sex=Male|E)和P(Sex=Female|E),比较两个概率值,概率值较大的假设H成立。2022年12月14日星期三第8页,共41页)0.0593/P(E)/P(E)(8/81)(3/5)E|MaleP(Sex /P(E)0.0281 5)/P(E)(9/128)(2/)E|FemaleSex P(结论 在P(E)值相同的情况下,因为0.0593 0.0281,则新实例的Sex最可能为Male。清华大学出版社2、使用Weka贝叶斯分类器解决例7.4问题(1)准备
8、数据;(2)加载训练数据,选择bayes分类器下的NaiveBayes(朴素贝叶斯);(3)设置检验集为Supplies test set。(4)执行训练,并预测新实例,输出结果(图7.14)。2022年12月14日星期三第9页,共41页图7.14 NaiveBayes分类器预测未知实例的输出结果清华大学出版社3、贝叶斯分类器存在的问题kdpkn)((1)概率为0问题若某属性值为0个,则会造成计算条件概率为0。如例7.4中,假设 Credit Card Insurance 为No的女性人数为0,则p(Credit Card Insurance=No|Sex=Female)=0/4=0,使得P(
9、E|Sex=Female)=0,则计算p(Sex=Female|E)时会造成计算错误。解决办法为每个要计算的比率的分子和分母添加一个小常数k。其中K0到1之间的值(通常为1)。P属性可能值总数的等分。如果属性有两个可能值,则p为0.5。0176.01)1)(41)(41)(4(40.5)0.5)(30.5)(10.5)(2(3 )female sex|P(E重新计算条件概率P(E|Sex=Female)。k=1,P=0.5,Sex=Female:式7.142022年12月14日星期三第10页,共41页清华大学出版社3、贝叶斯分类器存在的问题(2)缺失数据问题 当要预测的未知实例的某个输入属性值
10、缺失时 如例7.4中的新实例缺失了Watch Promotion属性值,即Magazine Promotion=Yes,Watch Promotion=Unknown,Life Insurance Promotion=No,Credit Card Insurance=No 判断该客户的性别sex值,只需在计算p(E|Sex=Male)和P(E|Sex=Female)两个条件概率时,都简单地忽略此属性出现的条件概率值即可,即将此属性概率值当作1.0 尽管这样做导致两个条件概率的值增大了,但因为是同时受到相同影响,从而不会影响最终判断。2022年12月14日星期三第11页,共41页7.3 聚类技术
11、清华大学出版社7.3 聚类技术 基于划分的聚类方法 第2章 K-means算法 基于分层的聚类方法 凝聚聚类 COBWEB 基于模型的聚类方法 EM算法2022年12月14日星期三第13页,共41页清华大学出版社7.3.1分层聚类(Hierarchical clustering)应用最为广泛是划分聚类(partition clustering)和分层聚类两大类。划分聚类 对一个具有n个实例的数据集,初始构造k 个簇(k n),然后通过反复迭代调整k个簇的成员,最终直到每个簇的成员稳定为止。k-means 算法一种被普遍使用的划分聚类方法分层聚类 按照对数据实例集合进行层次分解,根据分层分解采用
12、的策略不同,分层聚类法又可以分为凝聚聚类(agglomerative clustering)和分裂聚类(divisive clustering)。2022年12月14日星期三第14页,共41页清华大学出版社7.3.1分层聚类(Hierarchical clustering)凝聚分层聚类采用自底向上策略。首先将每个对象作为一个簇,根据某种相似度度量方法对这些簇进行合并,直到所有实例都被分别聚类到某一个簇中,或满足某个终止条件时为止。绝大多数分层聚类算法属于凝聚聚类方法,这些算法的区别一般是在簇之间的相似度度量方法上不同。分裂分层聚类采用自顶向下策略(与凝聚分层聚类相反的策略)。首先将所有的数据实
13、例放在一个簇中,再根据某种相似度度量方法逐步将其细分为较小的簇,直到达到希望个数的簇,或每个数据实例自成一个簇,或两个最接近簇之间的距离大于某个阈值。2022年12月14日星期三第15页,共41页清华大学出版社1、凝聚聚类(Agglomerative Clustering)一种很受欢迎的无指导聚类技术。在开始时假定每个数据实例代表它自己的类。算法步骤(1)开始时,将每个数据实例放在不同的分类中;(2)直到所有实例都成为某个簇的一部分;确定两个最相似簇;将在中选中的簇合并为一个簇。(3)选择一个由步骤(2)迭代形成的簇作为最后结果。2022年12月14日星期三第16页,共41页【例7.5】对于信
14、用卡账单促销数据集(表7.6),使用凝聚聚类技术,将实例聚类在合适的簇中。清华大学出版社步骤表7.6 信用卡账单促销数据集2022年12月14日星期三第18页,共41页(1)第一次迭代,计算两个实例之间的相似度值。通过式7.15计算的相似性值(图7.15)。比较的属性个数个数两个实例值相同的属性和相似性值jiiII),(jII式7.150.1),(,4.0),(,2.0),(,6.0),(,4.0),(0.1),(,2.0),(,8.0),(,4.0),(0.1),(,0.0),(,8.0),(0.1),(,2.0),(0.1),(554535251544342414332313221211I
15、IIIIIIIIIIIIIIIIIIIIIIIIIIIII相似性值相似性值相似性值相似性值相似性值相似性值相似性值相似性值相似性值相似性值相似性值相似性值相似性值相似性值相似性值图7.15 第一次迭代实例间相似性值清华大学出版社步骤0.1)(),(,4.0)(),(,6.0)(),(,47.0),(,(0.1)(),(,8.0)(),(,47.0),(,(0.1)(),(,33.0),(,(8.0),(),(5545253154424314223123131IIIIIIIIIIIIIIIIIIIIIIIII相似性值相似性值相似性值相似性值相似性值相似性值相似性值相似性值相似性值相似性值(2)第
16、一次迭代,合并两个最相似的实例到一个簇中。可以看到 与 、与 两对实例显示出最高的相似值0.8,选择其中一对进行合并。则第一次迭代后,产生了三个单实例簇()、()、()和一个双实例簇(,)(3)第二迭代,计算两个簇之间的相似度值。有多种方法。计算两个簇中所有实例平均相似度得到簇之间的相似度(图7.16)。如,簇(,)与簇()的相似度值为7/15=0.47。图7.16 第二次迭代簇间相似性4I5I2I3I1I1I3I4I4I2I3I1I2022年12月14日星期三第19页,共41页清华大学出版社步骤(4)第二次迭代,合并 与 。产生两个双实例簇(,)、(和 )和一个单实例簇()。继续簇的合并过程
17、直到所有实例合并到一个簇中。(5)确定最后的簇。多种统计方法(1)使用合并簇时使用的相似度度量方法。(2)将每个簇内的平均相似度与每个簇间的相似度进行比较。(3)结合前两种技术,淘汰一些簇后,将每个保留下来的簇提交给规则生成器,检查这些规则集,选择其中定义最明确的簇作为最后的结果。2I4I1I3I5I2I4I2022年12月14日星期三第20页,共41页说明输入属性值为实数时,常用简单欧氏距离进行实例之间、簇之间的相似性度量。凝聚聚类一般不独立使用,经常是作为其它聚类技术的预处理技术。比较著名的应用是在K-means算法开始前,进行凝聚聚类确定初始簇的个数【例7.6】对于CreditCardP
18、romotion 信用卡账单促销数据集,使用Weka进行分层聚类,查看分层结果。清华大学出版社实验结果2022年12月14日星期三第22页,共41页图7.18分层聚类结果图7.19分层聚类树清华大学出版社2、COBWEB分层聚类算法一种增量式分层聚类算法。使用分类树对实例数据进行分类,分类树的构造过程是一种概念分层的过程,这个过程称为概念聚类。概念聚类(conceptual clustering)无指导聚类技术,结合增量学习(incremental learning)构造概念分层概念分层(concept hierarchy)一种树结构形式,根结点是概念最高层次,包含所有域实例的汇总信息。除了叶
19、结点,其他结点都被称为树的基层结点(basic-level nodes),基层结点表达了人类对概念层次的划分;使用评价函数来度量概念层次质量。属性值必须是分类类型的。2022年12月14日星期三第23页,共41页清华大学出版社COBWEB标准概念聚类算法(1)建立一个类(簇),使用第一个实例作为它唯一的成员;(2)对于每个剩余实例,在每个树层次(概念分层)上,用一个评价函数决定选择以下两个动作之一执行:将新实例放到一个已存在的簇中;创建一个只具有这个新实例的新概念簇。评价函数(evaluation function)一种对概念分类质量的测量指标;COBWEB算法使用的是一种启发式评价方法分类效
20、用(Category Utility,CU)来指导分类。CU定义了聚类的好坏,值越小聚类较差,值越大聚类质量越好。2022年12月14日星期三第24页,共41页清华大学出版社CU计算公式mVAPCVAPCPCUmkijijijikijik)()|()(122式 7.16 中包含三个概率(1)表示在类 的全体成员中,属性 为 的条件概率。(2)表示在整个数据集中,属性 取值为 的概率。(3)表示每个类 的概率。式7.16)|(kijiCVAP)(ijiVAP)(kCPkCijViAijVkC2022年12月14日星期三第25页,共41页iA【例7.7】假设已经将表7.7中实例聚类为两个簇,分别为
21、 ,计算CU值。1C2C清华大学出版社步骤2022年12月14日星期三第27页,共41页表7.7 计算CU使用的数据集Instance数值化前数值化前ColorShapeTypeID数值化后数值化后ColorShapeTypeIDRedCircleTrue001RedrectangleFalse020YellowdiamondTrue111BluediamondTrue211BluediamondFalse2101i2i3i4i5i假设聚类结果分为了两个类 ,分别为(,)和(,)计算CU值步骤(1)计算 数据集共有5个实例,而 和 分别由2个实例和3个实例,则1C2C1i2i3i4i5i)(k
22、CP4.05/2)(1CP6.05/3)(2CP1C2C清华大学出版社步骤(2)计算 这个二重求和被称为无条件概率求和项(Unconditional probability Sum)。计算数据集中每个属性的每个取值的概率值,求平方和,结果如表7.8。表7.8 CU方程中的无条件概率值和条件概率值计算结果属性值整个数据集无条件概率值条件概率值Red(2/5)2=0.1600(2/2)2=1.0000(0/3)2=0.0000Yellow(1/5)2=0.0400(0/2)2=0.0000(1/3)2=0.1111Blue(2/5)2=0.1600(0/2)2=0.0000(2/3)2=0.444
23、4Circle(1/5)2=0.0400(1/2)2=0.2500(0/3)2=0.0000diamond(3/5)2=0.3600(0/2)2=0.0000(3/3)2=1.0000rectangle(1/5)2=0.0400(1/2)2=0.2500(0/3)2=0.0000False:(2/5)2=0.1600(1/2)2=0.2500(1/3)2=0.1111True:(3/5)2=0.3600(1/2)2=0.2500(2/3)2=0.4444求和项Unconditional probability Sum=1.3200Unconditional probability sum(k=
24、1)=2.0000Unconditional probability sum(k=2)=2.1111 ijijiVAP2)(2022年12月14日星期三第28页,共41页清华大学出版社步骤37.02)32.11.2(6.0)31.12(*4.0CU(3)计算 这个二重求和项被称为条件概率求和项(conditional probability Sum)。计算每个属性值分别出现在 和 中的的条件概率,求其平方和,结果如表7.8。(4)计算CU。ijkijiCVAP2)|(2022年12月14日星期三第29页,共41页1C2C【例7.8】根据表7.7中的实例集,使用Weka进行COBWEB聚类,建立
25、概念分层树。清华大学出版社实验结果2022年12月14日星期三第31页,共41页图7.21 COBWEB聚类结果图7.22 COBWEB聚类算法创建的概念分层树清华大学出版社COBWEB算法的优势和局限性优势 能够自动调整类(簇)的个数,不会因为随机选择分类个数的不合理性而造成聚类结果的不理想。局限性 对实例顺序敏感,需要引入两种附加操作合并和分解降低敏感性。假设每个属性的概率分布是彼此独立的,而实际这个假设不总是成立;类(簇)的概率分布的表示、更新和存储的复杂程度,取决于每个属性取值个数。当属性取值较多时,算法的时间和空间复杂度会很大。偏斜的实例数据会造成概念分层树的高度不平衡,也会导致时间
26、和空间复杂度的剧烈变化。2022年12月14日星期三第32页,共41页清华大学出版社7.3.2 基于模型的聚类(Model-based Clustering)为每个分类(簇)假设一个模型,再去发现符合模型的数据实例,使得实例数据与某个模型达成最佳拟合。通过建立反映实例数据空间分布的密度函数来定义簇的特征,通过统计数字确定簇的个数、噪声数据和孤立点,使得该聚类方法具有一定的健壮性,所以应用非常广泛。为每个簇假设一个数学上的参数分布模型,如高斯分布(Gaussian distribution)或泊松分布(Poisson distribution),整个数据集则成为一个这些分布的混合分布模型,每个分
27、类的单个分布被称为成分分布(component distribution)。因为每个成分分布都是数据分布的最佳拟合,则混合模型能够很好地表达整个数据的分布。一个混合(mixture)是一组n元概率分布,其每个分布代表一个簇。混合模型为每个数据实例指定一个概率,假定这个实例是某个簇的成员,则它具有一组特定的属性值。混合模型假定所有属性是独立自由变量。2022年12月14日星期三第33页,共41页清华大学出版社7.3.2 基于模型的聚类N(1,2)N(2,2)图7.23 高斯混合模型聚类示意图2022年12月14日星期三第34页,共41页使用最广泛的是高斯混合模型把分类(簇)看成以重心为中心的高斯
28、分布(图7.23),其中圆圈部分表示分布的主体,为属性均值,为属性标准差。清华大学出版社EM(expectation-maximization)EM算法 一种采用有限高斯混合模型的统计技术;统计学中用于在依赖于无法观测的隐性变量(Latent Variable)的概率模型中,对参数进行最大似然估计。EM算法基本思想假设整个数据集服从高斯混合分布,待聚类的数据实例看成是分布的采样点;通过采样点利用极大似然估计方法估计高斯分布的参数;求出参数即得出了实例数据对分类的隶属函数。与K-means算法相似,都是迭代地进行参数估计直到得到一个期望的收敛值。2022年12月14日星期三第35页,共41页清华
29、大学出版社EM算法的一般过程)2/()(22)2/(1)(xexf假设概率分布是正态的;分类(簇)个数为2;数据实例由单个实值属性组成。任务估计5个参数2个簇均值,2个标准差,1个簇样本概率P(另一个为 1-P)。一般过程(1)估计5个参数的初始值;(2)直到满足某个终止条件;使用正态分布的概率密度函数(式7.17)计算每个实例的分类概率,在双分类情况下,有两个概率分布公式,每个都拥有不同的均值和标准差值;使用步骤(2)中每个实例的概率值重新对5个参数进行重新估值。终止条件是度量聚类质量(来自簇的概率,值越高聚类越理想)值不再显著增大。式7.17其中,e为指数,为属性均值,为属性标准差值,x为
30、属性值。2022年12月14日星期三第36页,共41页【例7.9】使用iris数据集,在Weka中使用EM算法进行聚类,并解释聚类结果。2022年12月14日星期三第37页,共41页清华大学出版社实验结果2022年12月14日星期三第38页,共页图7.25 EM聚类结果图7.26 iris数据集EM聚类的可视化结果清华大学出版社7.4 数据挖掘中的统计技术与机器学习技术 数据挖掘中的统计技术与机器学习技术的不同(1)统计技术假设数据的基本分布(正态分布),其应用可靠性依赖于该假设是否有效。机器学习技术对于要处理的数据没有进行假定。(2)机器学习技术用人可理解的风格来决定知识结构,如决策树和产生
31、式规则包含容易解释的知识。许多统计技术的输出是数学方程,含义解释困难。(3)机器学习技术能够较好地处理缺失和噪声数据,如神经网络特别优秀。统计技术通常需要消除有噪声的数据实例。(4)大多数机器学习技术能够解释自己的行为,神经网络是个例外。统计技术则不能。2022年12月14日星期三第39页,共41页清华大学出版社7.4 数据挖掘中的统计技术与机器学习技术(5)统计技术在处理大型数据集上存在问题。(6)统计技术和机器学习方法在建模速度上没有本质区别,计算复杂性仅仅依赖于技术本身,与其是统计技术还是机器学习方法无关。(7)使用统计检验来评估数据挖掘的输出结果,与建模技术本身无关,不管是应用统计技术还是机器学习方法,所建模型都可以利用统计技术加以检验。2022年12月14日星期三第40页,共41页清华大学出版社本章小结数据挖掘中的统计技术有指导学习技术贝叶斯分析无指导聚类技术简单线性回归多元线性回归多元线性回归实验使用Excel的LINEST函数回归分析分层聚类基于模型的聚类使用Weka的LinearRegression算法线性回归非线性回归对数回归树回归凝聚聚类COBWEB算法EM算法2022年12月14日星期三第41页,共41页图7.27 第7章内容导图