K-Means和EM算法聚类实验分析

《K-Means和EM算法聚类实验分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、南京理工大学计算机系《机器学习》课程作业K-Means与EM算法聚类实验分析章舜仲2040601981．概述　　K-Means是一种常用聚类算法，EM算法是进行极大似然估计的一种有效方法，本文对这两种方法的聚类应用进行了实验比较分析，实验环境为PIV2.8G/1G，Windowsxp+Delphi6.0。　　实验数据为n个数值组成的点集，分配到k个类别中，本文实验中EM聚类算法基于样本数据的混合高斯分布假设，假设概率模型为，其中，实验采用简化处理，取为常数1/K忽略，取值为1，EM与K-Means算法具体步骤略。2

2、．数据集生成　　实验在三个数据集上进行，每个数据集包括6000个随机数值，数值生成方法描述如下。2.1高斯分布随机数　　高斯分布随机数的产生使用Marsaglia-Bray算法，函数RandG输入参数为均值和标准差，返回服从高斯分布的随机数。　　(1)产生两个(0,1)上均匀分布的随机数U1和U2　　(2)令V1=2*U1-1，V2=2*U2-1　　(3)计算S=V1*V1+V2*V2　　(4)若S>=1，返回步骤(1)　　(5)返回值Result=　　实验中分别以N(100,5)和N(150,20)各生成3000

3、个数字，数值频率分布如图1所示。图1　高斯分布数据（数据集a）10南京理工大学计算机系《机器学习》课程作业2.2一维布朗运动轨迹　　令初始数字为d，对d以0.5的概率加1或减1操作，每次得到一个数字，作n次操作即可得到n个数字，相当于一维布朗运动的轨迹。实验中分别以100和200作为起始点作3000次操作，得到数据如图2所示。图2　一维布朗运动数据（数据集b）2.3均匀分布随机数　　使用随机函数产生(100,200)区间上的随机数，如图3所示。图3均匀分布数据（数据集c）据　　观察以上三个数据集，高斯分布数据集a由

4、两个标准的高斯分布类构成，数据类别特征良好，属于比较理想的情况。布朗运动数据集b可分为两个大类，但多处形成局部小类，这和实际情形比较相似，如学科领域交叉形成的边缘学科，大学科中的小学科等，属于比较复杂的情形。数据集c为均匀分布，使用此数据集主要用于观察算法在临界情形下的性能。10南京理工大学计算机系《机器学习》课程作业3．实验分析3.1聚类正确性和稳定性（1）K=2图4K=2的聚类结果据10南京理工大学计算机系《机器学习》课程作业　　图4中，处于同一水平直线上的十字表示属于同一类的数据，在K=2情形下，K-mean

5、s和EM算法均得到稳定的聚类结果，其中在数据集a和b上的聚类符合实际情形，而在均匀分布数据集c上聚类的结果等于平均分割数据集。（2）K=3图5(a)数据集a上的聚类结果据图5(b1)数据集b上聚类结果1据10南京理工大学计算机系《机器学习》课程作业图5(b2)数据集b上聚类结果2据图5(c)数据集c上聚类结果据图5K=3的聚类结果据　　K=3时的聚类结果如图5所示，在数据集a和c中，两个算法均取得较好的稳定性，其中在均匀分布数据集c上的聚类结果依然是等分数据集（增大k后依然有此结论，下面不再给出c的实验结果显示）。

6、而在数据集b出现a1和a2两种聚类结果，通过多次反复实验，a1和a2在k-means和EM算法下均以近似0.5的概率出现，聚类结果出现随机性，在这里K-Means和EM算法具有相同的不稳定性。不稳定的原因在于两个大类交叉处形成的一个局部子类具有不确定的类别特征。解决此种类交叉形成的不确定类可有以下两个方法。①采用分层次聚类的方法，通过实验得到稳定聚类结果的K值后，划分数据集，数据样本归到各类中，然后在每个类的数据集中进行聚类。②10南京理工大学计算机系《机器学习》课程作业所有不确定样本组成不确定数据集，然后在不确定

7、数据集中进行聚类得到确定类，依此类推直至所有样本均归属到确定类别。（3）K=4图6(a1)数据集a上聚类结果1据图6(a2)数据集a上聚类结果2据10南京理工大学计算机系《机器学习》课程作业图6(b1)数据集b上聚类结果1据图6(b2)数据集b上聚类结果2据图6(b3)数据集b上聚类结果3据10南京理工大学计算机系《机器学习》课程作业图6K=4的聚类结果据　　如图6所示，K=4的情形下，数据集a上有a1、a2两种情形，数据集b上有b1、b2、b3三种情形，同时实验发现K-Means算法和EM算法对于这几种情形的产生

8、有了差别。设P(a1｜K-Means)表示K-Means算法时出现a1情形的概率，P(a1｜EM)为EM算法时出现a1的概率，通过反复试验可得到如下结果。在数据集a上，P(a1｜K-Means)≈0.5，P(a2｜K-Means)≈0.5，P(a1｜EM)≈0，P(a2｜EM)≈1，即EM算法得到稳定的结果，而K-Means算法稳定性较差。在数据集b上，P(