4.8聚类算法评价.ppt

4.1.1 聚类分析研究的主要内容 (1) 模式表示(包括特征提取和/或选择)； (2) 适合于数据领域的模式相似性定义； (3) 聚类或划分算法； (4) 数据摘要； (5) 输出结果的评估。 k-means聚类算法示例-1 例 4.1 对表4-1中二维数据，使用k-means算法将其划分为2个簇，假设初始簇中心选为P7(4，5)，P10(5，5)。 表4-1 k-means聚类过程示例数据集1 解：图4-2 显示了对于给定的数据集k-means聚类算法的执行过程。 (1)根据题目，假设划分的两个簇分别为C1和C2，中心分别为(4，5)和(5，5)，下面计算10个样本到这2个簇中心的距离，并将10个样本指派到与其最近的簇： (2)第一轮迭代结果如下： 属于簇C1的样本有：{P7，P1，P2，P4，P5，P8} 属于簇C2的样本有：{P10，P3，P6，P9} 重新计算新的簇的中心，有：C1的中心为(3.5，5.167)，C2的中心为(6.75，4.25) k-means聚类算法示例-2 (3)继续计算10个样本到新的簇的中心的距离，重新分配到新的簇中，第二轮迭代结果如下： 属于簇C1的样本有：{ P1，P2，P4，P5，P7，P10} 属于簇C2的样本有：{ P3，P6，P8，P9} 重新计算新的簇的中心，有：C1的中心为(3.67，5.83)，C2的中心为(6.5，3.25) (4)继续计算10个样本到新的簇的中心的距离，重新分配到新的簇中，发现簇中心不再发生变化，算法终止。 4.2.2 二分k-means算法 二分K-means算法是基本k-means算法的直接扩充，基于如下想法：为了得到k个簇，将所有点的集合分裂成两个簇，从中选择一个继续分裂，如此重复直到产生k个簇。算法详细描述如下： 初始化簇表，使之包含由所有的点组成的簇。 Repeat 从簇表中选取一个簇。 { 对选定的簇进行多次二分“试验” } For i=1 to 试验次数 do 使用基于基本k-means，二分选定的簇 End for 从二分试验中选择具有最小总SSE的两个簇。 将这两个簇添加到簇表中 Until 簇表中包含k个簇 4.2.3 k-means聚类算法的拓展 -1 对于聚类分析而言，聚类表示和数据对象之间相似度的定义是最基础的问题，直接影响数据聚类的效果。 这里介绍一种简单的聚类表示方法，并对Minkowski距离进行推广以使聚类算法可以有效处理含分类属性的数据。 假设数据集D有m个属性，其中有mC个分类属性和mN个数值属性，m=mC+mN ，用Di表示第i个属性取值的集合。 距离计算示例 例4-2 假设描述学生的信息包含属性：性别，籍贯，年龄。有两条记录p，q及两个簇C1，C2的信息如下，分别求出记录和簇彼此之间的距离： p={男，广州，18} ， q={女，深圳，20} C1={男：25，女：5；广州：20，深圳：6，韶关：4；19} C2={男：3，女：12；汕头：12，深圳：1，湛江：2；24} 按定义4-3，取x=1得到的各距离如下： d(p，q)=1+1+(20-18)=4 d(p，C1)=(1-25/30)+(1-20/30)+(19-18)=1.5 d(p，C2)=(1-3/15)+(1-0/15)+(24-18)=7.8 d(q,C1)=(1-5/30)+(1-6/30)+(20-19)=79/30 d(q,C2)=(1-12/15)+(1-1/15)+(24-20)=77/15 d(C1,C2)=1-(25*3+5*12)/(30*15)+1-6*1/(30*15)+(24-19)=1003/150≈6.69 k-summary算法示例-1 例4-3 对于表4-2所示的数据集，请使用k-summary算法将其划分为3个簇。 表4-2 聚类过程示例数据集2 k-summary算法示例-2 解：(1)假定选择第5条记录{ rainy，68,80，FALSE }，第7条记录{overcast，64，65，TRUE}和第10条记录{ rainy，75，80，FALSE }作为三个簇C1、C2和C3的初始中心（摘要）。 (2) 划分对象到最近的簇，各记录与三个簇之间的距离 (使用欧几里得距离) 如下表： k-summary算法示例-3 第一次划分后三个簇的摘要信息更新为： 簇C1:{ rainy:3 ;69.667; 89.000; FALSE:2,TRUE:1}; 簇C2:{ overcast:1,rainy:1,