内容讲义教案

1、K均值算法（十大经典算法之一）K中心点算法Adaboost算法（十大经典算法之一）7.4划分方法K均值算法K中心点算法划分方法给定n个对象的数据集D,以及要生成的簇的数目k,划分算法将对象组织为k个划分（kn）,每个划分代表一个簇。这些簇的形成旨在优化一个目标划分准则，如基于距离的相异度函数，使得根据数据集的属性，在同一个簇中的对象是“相似的”，而不同的簇中的对象是“相异的”。第一种划分方法k均值（k-means）K均值算法以K（一般是用户指定的）为输入参数，把n个对象的集合分为K个簇，使得结果簇内对象的相似度高，簇间对象的相似度低。算法聚类流程：首先，随机地选择k个对象，每个对象代表一个初始

2、簇中心。对剩余的每个对象，根据其与各个簇中心的距离，将它指派到距离最近的簇。然后计算每个簇的新均值。这个过程不断重复，直到簇中心点不再发生变化。第一次聚类结果K=2将剩余对象指派到离它最近的簇任选两个初始簇中心初始数据集更新聚类中心第二次聚类结果将剩余对象指派到最近的簇更新聚类中心第三次聚类结果更新簇中心，直到所有的簇中心不发生变化重新指派对象到距离最近的簇K均值过程概述输入：k:簇的数目，D:包含n个对象的数目集。输出：k个簇的集合。方法：(1) 从D中任意选择k个对象作为初始簇中心；(2) Repeat(3)根据簇中对象的均值，将每个对象指派到最相似的簇;(4) 更新簇均值，即计算每个簇中

3、对象的均值;(5) Until每个簇的中心不再发生变化举例：将数据对象集合s分为两个簇，即 k=2YS：O5(5，2)O1(0，2)XO2(0，0)O (5,0)O3(1.5,0)4xyO102O200O31.50O450O552(1) 随机选择两个初始簇中心。M1=O1=(0,2) M2=O2=(0,0)，对应的簇为C1，C2(2)对剩余的每个对象，根据其与各个簇中心的距离，将它赋给最近的簇。对O3：d(M1,O3：d(M1,O4：d(M1,O5d(M2,O3 )=1.5 ， 将O3 加入簇C2。)=2.5对O4d(M2,O4 )=5 ， 将O4 加入簇C2。)= 5.38对O5d(M2,O

4、5 )=5.38 ， 将O5 加入簇C1。)= 5更新，得到两个簇C1=O1，O5和C2=O2，O3，O4(3) 计算新的簇的中心。（簇中心不一定是集合中的点）M1=(2.5,2)重复(2) 和(3)M2=(2.17,0)对O1：d(M1,O1：d(M1,O2：d(M1,O3：d(M1,O4：d(M1,O5d(M2,O1 )=4.72 ， 将O1 加入簇C1。)= 2.5对O2d(M2,O2 )=2.17 ， 将O2 加入簇C2。)= 3.2对O3d(M2,O3 )=0.67 ， 将O3 加入簇C2。)=2.24对O4d(M2,O4 )=2.83 ， 将O4 加入簇C2。)= 3.2对O5d(

5、M2,O5 )=3.47 ， 将O5 加入簇C1。)= 2.5由于在两次迭代中，簇中心不变，所以停止迭代过程，算法停止。聚类结果：C1=O1，O5和 C2=O2，O3，O4提醒：当选择O2和O5为初始簇中心点时聚类结果是C1=O1，O2，O3和C2=O4，O5优点：（1）简单易行；（2）时间复杂度接近线性；（3）对大数据集，是可伸缩和高效率的。缺点：最终的结果会随初始中心的变化而变化；算法依赖于用户指定的k值，不合适的 k 可能返回较差的结果；（3）对离群点是敏感的。第二种划分方法k中心点K均值算法对于离群点是敏感的，因为一个具有很大的值的对象可能显著地数据的分布。平方误差的使用更是严重了这一

6、影响。“如何修改这个算法来降低这种敏感性？”可以不采用簇中对象的均值作为参考点，而是在每个簇中选出一个实际的对象来代表该簇。其余的每个对象聚类到与其最相似的代表性对象所在的簇中。这样，划分依然基于最小化所有对象与其对应的参考点之间的相异度之和的原则来执行。算法聚类流程：首先随意选择初始代表对象。只要能提高结果聚类质量，迭代过程就继续用非代表对象替换代表对象。聚类结果的质量用代价函数来评估，该函数度量对象与其簇的代表对象之间的平均相异度。为了确定非代表对象Orandom是否是当前代表对象Oj的好的替代，对于每一个非代表对象p，考虑如下4种情况。第一种情况：p当前隶属于代表对象Oj。如果Oj被Or

7、andom所代替作为代表对象，且p离其他代表对象Oi(ij)最近，则p重新分配给Oi。第二种情况：p当前隶属于代表对象Oj。如果Oj被Orandom代替作为代表对象，且p离Orandom最近，则p被重新分配给Orandom。第三种情况：p当前隶属于中心点Oi，ij。如果Oj被Orandom代替作为代表对象，而p依然离Oi最近，则对象的隶属不发生变化。第四种情况：p当前隶属于中心点Oi，ij。如果Oj被Orandom代替作为代表对象，且p离Orandom最近，那么p被重新分配给Orandom。第四种情况mp 被重新分配给Orandom代价 = d (Orandom, p)-d (Oi, p)Oi

8、OjpOrando第三种情况mp 的隶属不发生变化代价 = 0OiOjpOrando第二种情况mp 被重新分配给Orandom代价 = d (Orandom , p)-d (Oj , p)OiOjpOrando第一种情况mp 被重新分配给Oi代价 = d (Oi, p)-d (Oj, p)OiOjpOrandoK中心点算法随机选择 k个对象作为初始中心点将剩余对象指定到离中心点最近的簇中K=2随机选择一个非中心对象Oramdom如果聚类质量提高，用 Oramdom替换O计算总的替换代价17循环直到代价不再减小为止1098765432100123456789 101098765432100123

9、456789 10109876543210012345678910109876543210012345678910109876543210012345678910每当重新分配发生时，绝对误差 E 的差对代价函数有影响。因此，如果当前的代表对象被非代表对象所取代，代价函数就计算绝对误差值的差。交换的总代价是所有非代表对象所产生的代价之和。如果总代价是负的，实际绝对误差将会减小，Oj可以被Orandom替代。如果总代价是正的，则当前的代表对象Oj是可接受的，在本次迭代中没有变化发生。算法5-2 PAM（k-中心点算法）输入：簇的数目k和包含n个对象的数据库。输出：k个簇，使得所有对象与其最近中心点

10、的相异度总和最小。任意选择k个对象作为初始的簇中心点；REPEAT指派每个剩余的对象给离它最近的中心点所代表的簇；（4）（5）（6）（7）（8）（9）（10）REPEAT选择一个未被选择的代表Oi；REPEAT选择一个未被选择过的代表对象Orandom；计算用Orandom代替Oi的总代价并UNTIL 所有的非代表都被选择过；在S中；UNTIL 所有的代表对象都被选择过；IF 在S中的所有非代表对象代替所有代表对象后计算出的总代（11）价有小于0的存在 THEN 找出S中的用非代表对象替代代表对象后代价最小的一个，并用该非代表对象替代对应的代表对象，形成一个新的k对象的集合；（12）UNTIL

11、 没有再发生簇的重新分配，即所有的S都大于0.假如空间中的五个点A、如图1所示，各点之间的距离关系如表1所示，根据所给的数据对其运行PAM算法实现划分聚类（设k=2）。 样本点间距离如下表所示:起始中心点为CC2AA样本点D2DBB3EE第一步 建立阶段：假如从5个对象中随机抽取的2个中心点为A，B,则样本被划分为A、C、D和B、E，如图5-3所示。第二步交换阶段：假定中心点A、B分别被非中心点C、D、E替换，根据PAM算法需要计算下列代价TCAC、 TCAD、 TCAE、TCBC、TCBD、 TCBE。以TCAC为例说明计算过程：a)当A被C替换以后，A不再是一个中心点，因为A离B比A离C近

12、，A被分配到B中心点代表的簇，CAAC=d(A,B)-d(A,A)=1。B是一个中心点，当A被C替换以后，B不受影响，CBAC=0。C原先属于A中心点所在的簇，当A被C替换以后，C是新中心点，符合PAM算法代价函数的第二种情况CCAC=d(C,C)-d(C,A)=0-2=-2。D原先属于A中心点所在的簇，当A被C替换以后，离D最近的中心点是C，根据PAM算法代价函数的第二种情况CDAC=d(D,C)-d(D,A)=1-2=-1。E原先属于B中心点所在的簇，当A被C替换以后，离E最近的中心仍然是 B，根据PAM算法代价函数的第三种情况CEAC=0。b)c)d)e)因此，TCAC=CAAC+ CB

13、AC+ CBAC+ CDAC+ CEAC=1+0-2-1+0=-2。A,B样本点ABCDEA01223B10243C22015D24103E33530在上述代价计算完毕后，要选取一个最小的代价，显然有多种替换可以选择，选 择第一个最小代价的替换（也就是C替换A），根据图5-4（a）所示，样本点被划分为 B、A、E和C、D两个簇。图5-4（b）和图5-4（c）分别表示了D替换A，E替换A的情况和相应的代价CCCAAA112111DDDBBB333EE(a)C替换A,TCAC=-2(b) D替换A, TCAD=-2(c) E替换A,TCAE=-1图5-4替换中心点A图5-5（a）、（b）、（c）分

14、别表示了用C、D、E替换B的情况和相应的代价。CCCA2AA11111D2DBBB33EEC替换B, TCBC=-2(b) D替换B, TCBD=-2图5-5 替换中心点B(c) E替换B, TCBE=-2通过上述计算，已经完成了PAM算法的第一次迭代。在下一迭代中，将用其他的非中心点A、D、E替换中心点B、C，找出具有最小代价的替换。一直重复上述过程，直到代价不再减小为止。DEEK中心点算法的特点：（1）当存在噪声和离群点时，K中心点方法比K均值更健壮，因为中心点不像均值那样容易受离群点或其他值的影响。（2）K中心点方法的执行代价比K均值算法高。（3）两种方法都要指定簇的个数K.AdaBoo

15、st算法AdaBoostAdaboost是adaptive boost的缩写，它是一种迭代算法。其是针对同一个训练集训练不同的分类器（弱分类器），然后把这些弱分类器集合起来，一个更强的最终分类器 (强分类器)。其算法本身是通过改变数据分布来实现的，它根据每次训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。 将修改过权值的新数据集送给下层分类器进行训练，最后 将每次训练得到的分类器融合起来，作为最后的决策分类 器。使用Adaboost分类器可以排除一些不必要的训练数据特征，并将重点放在关键的训练数据上。该算法其实是一个弱分类算法的过程，这个过程通过不断的训练，

16、可以提高对数据的分类能力。简单的例子来看看adaboost的实现过程：图中，“+”和“-”分别表示两种类别，在这个过程中，使用水平或者垂直的直线作为分类器，来进行分类。第一步：e1=0.3 1=0.37样本权重的更新过程：分错的3个样本权重不变 ：都为 0.1分对的7个样本的权重更新为：0.1*（e1/(1-e1）=0.1*0.3/0.7=0.3/7最后规范化权重：3个分错的样本权重变为 1/67个分对的样本权重变为 1/14根据分类的正确率，得到一个新的样本分布D2，一个子分类器h1其中划圈的样本表示被分错的。在右边的图中，比较大的“+”表示对该样本做了。第二步：e2=0.21 2=0.58

17、根据分类的正确率，得到一个新的样本分布D3，一个子分类器h2第三步：e3=0.14 3=0.79得到一个子分类器h3整合所有子分类器：0.370.580.79因此可以得到整合的结果，从结果中看，即使简单的分类器，组合起来也能获得很好的分类效果。D举例：D是10个元组的训练集将每个元组的权重初始化为0.1根据元组的权重有放回的抽样10次，得到D1.使用训练集导出模型M1.计算M1误差率e(M1)=0.1*1+0.1*1+0+.=0.2分类器M1的表决权重D1(特殊情况，每个元组抽到一次)log 1 e(M1 ) log 0.8 0.6e(M1 )0.2(6) 更新正确分类元组的权重原元组的权重* e(M1) / (1-e(M1)8个正确分类的元组的权重更新为0.1*0.2/0.