《K-Means和EM算法聚类实验分析》由会员分享，可在线阅读，更多相关《K-Means和EM算法聚类实验分析（10页珍藏版）》请在金锄头文库上搜索。
1、南京理工高校计算机系机器学习课程作业K-Means 与 EM 算法聚类试验分析章舜仲 2040601981. 概述K-Means 是一种常用聚类算法，EM 算法是进展极大似然估量的一种有效方法，本文对这两种方法的聚类应用进展了试验比较分析，试验环境为PIV2.8G/1G，Windows xp+Delphi6.0。试验数据为 n 个数值组成的点集，安排到k 个类别中，本文试验中EM 聚类算法基于样本数据10的 混 合 高 斯 分 布 假 设 ， 假 设 概 率 模 型 为 P(xi| m,s ) = K ajj =1 p (xji| m ,sj) ， 其 中jp (x| m ,s ) =1- (
2、x2pse x p (i- m )2j) ，试验承受简化处理，a取为常数 1/K 无视，s 取jijj2s 2jjjj值为 1，EM 与 K-Means 算法具体步骤略。2. 数据集生成试验在三个数据集上进展，每个数据集包括6000 个随机数值，数值生成方法描述如下。2.1 高斯分布随机数高斯分布随机数的产生使用Marsaglia-Bray 算法，函数RandG 输入参数为均值m 和标准差s ， 返回听从高斯分布的随机数。(1) 产生两个(0, 1) 上均匀分布的随机数U 和U12(2) 令V=2*U -1，V =2*U -11122(3) 计算S= V * V + V * V1122(4)
3、假设 S=1，返回步骤(1)(5) 返回值Result= (-2 (LnS / S ) 2 V1s + m试验中分别以N(100,5)和 N(150,20)各生成 3000 个数字，数值频率分布如图 1 所示。图 1高斯分布数据数据集 a2.2 一维布朗运动轨迹令初始数字为d，对d 以 0.5 的概率加 1 或减 1 操作，每次得到一个数字，作n 次操作即可得到n 个数字，相当于一维布朗运动的轨迹。试验中分别以100 和 200 作为起始点作 3000 次操作，得到数据如图 2 所示。图 2一维布朗运动数据数据集b2.3 均匀分布随机数使用随机函数产生(100,200)区间上的随机数，如图 3
4、 所示。图 3均匀分布数据数据集 c观看以上三个数据集，高斯分布数据集 a 由两个标准的高斯分布类构成，数据类别特征良好， 属于比较抱负的状况。布朗运动数据集 b 可分为两个大类，但多处形成局部小类，这和实际情形比较相像，如学科领域穿插形成的边缘学科，高校科中的学校科等，属于比较简单的情形。数据集 c 为均匀分布，使用此数据集主要用于观看算法在临界情形下的性能。3. 试验分析3.1 聚类正确性和稳定性1K=2图 4K=2 的聚类结果图 4 中，处于同一水平直线上的十字表示属于同一类的数据，在K=2 情形下，K-means 和 EM 算法均得到稳定的聚类结果，其中在数据集 a 和 b 上的聚类符
5、合实际情形，而在均匀分布数据集 c 上聚类的结果等于平均分割数据集。2K=3图 5 (a) 数据集 a 上的聚类结果图 5 (b1) 数据集b 上聚类结果 1图 5 (b2) 数据集b 上聚类结果 2图 5 (c) 数据集 c 上聚类结果图 5K=3 的聚类结果K=3 时的聚类结果如图 5 所示，在数据集 a 和 c 中，两个算法均取得较好的稳定性，其中在均匀分布数据集 c 上的聚类结果照旧是等分数据集增大k 后照旧有此结论，下面不再给出c 的试验结果显示。而在数据集 b 消灭 a1 和 a2 两种聚类结果，通过屡次反复试验，a1 和 a2 在 k-means 和EM 算法下均以近似 0.5
6、的概率消灭，聚类结果消灭随机性，在这里K-Means 和 EM 算法具有一样的不稳定性。不稳定的缘由在于两个大类穿插处形成的一个局部子类具有不确定的类别特征。解决 此种类穿插形成的不确定类可有以下两个方法。 承受分层次聚类的方法，通过试验得到稳定聚类结果的 K 值后，划分数据集，数据样本归到各类中，然后在每个类的数据集中进展聚类。 全部不确定样本组成不确定数据集，然后在不确定数据集中进展聚类得到确定类，依此类推直至全部样本均归属到确定类别。3K=4图 6 (a1) 数据集 a 上聚类结果 1图 6 (a2) 数据集 a 上聚类结果 2图 6 (b1) 数据集b 上聚类结果 1图 6 (b2)
7、数据集b 上聚类结果 2据图 6 (b3) 数据集b 上聚类结果 3图 6K=4 的聚类结果如图 6 所示，K=4 的情形下，数据集a 上有 a1、a2 两种情形，数据集b 上有 b1、b2、b3 三种情形，同时试验觉察K-Means 算法和EM 算法对于这几种情形的产生有了差异。设 P(a1K-Means)表示 K-Means 算法时消灭 a1 情形的概率，P(a1EM)为 EM 算法时消灭 a1的概率，通过反复试验可得到如下结果。在数据集a 上，P(a1K-Means)0.5，P(a2K-Means)0.5，P(a1EM)0，P(a2EM)1， 即 EM 算法得到稳定的结果，而K-Mean
8、s 算法稳定性较差。在数据集b 上，P(b1K-Means)1/3，P(b2K-Means)1/3，P(b3K-Means)1/3，P(b1 EM)0，P(b2EM)0.5，P(b3EM)0.5，相对来说EM 算法仍旧比K-Means 算法稳定性好。以上数据显示 EM 算法不会产生a1 和 b1 情形，观看图 6 中 a1 和 b1 可以觉察这两种情形属于最糟糕的情形，其共同点是将图中的数值频率最顶峰一分为二，图中的顶峰表示样本密度最大的区域， 也是类别特征最清楚的样本，应当属于同一类。而b2 和 b3 的不确定形成缘由是由于两个类穿插处有一个子类，和图 5 的 b1、b2 的情形一样，是由于
9、样本类别特征模糊造成的。因此 EM 算法相比K-Means 算法聚类的正确性的和稳定性更好。3.2 时间简单度试验给定了EM 算法和K-Means 算法收敛的一样判定条件，K-Means 算法为连续 5 次迭代类中心不变不变指当前中心值和原来的中心值差小于0.01，EM 算法同样为连续 5 次迭代高斯分布中心不变，以下试验数据比较了K-means 和 EM 算法从开头到收敛的时间消耗。1K=2毫秒试验次数数据集aK-MeansEM数据集bK-MeansEM数据 cK-MeansEM总平均10.932.9时间消耗比值3.0表 1K=2 算法收敛时间消耗1154716323263216321631
10、153231516031163240160310315031153115316032163103171531153115318032163116479031016164610164716311532平均7.731.51129.61437.62K=3毫秒试验次数数据集aK-MeansEM数据集bK-MeansEM数据 cK-MeansEM表 2K=3 算法收敛时间消耗11663166231782163115621647316621662156241562063164751647157815476046078156271547157816628166216791647916631563063101
11、6630621662平均14.254.610.868.715.657.7总平均13.5360.33时间消耗比值4.53K=4毫秒试验次数数据集aK-MeansEM数据集bK-MeansEM数据 cK-MeansEM总平均20.43102.13时间消耗比值5.0表 3K=4 算法收敛时间消耗131125311094614121618715621612531663166332125416188166216141515621662321256166331793262716172157816638161571562161569161721663156310316316781693平均18.9125.2
12、18.771.823.7109.44K=5毫秒试验次数数据集aK-MeansEM数据集bK-MeansEM数据 cK-MeansEM表 4K=5 算法收敛时间消耗1311403110931156216125161253117231614016125152034311873110915156531941615616936161101678329471611016110161888327916941614191612515933115710159416941562平均22120.418.9109.321.8142.2总平均20.9123.97时间消耗比值6.05K=6毫秒试验次数数据集aK-MeansEM数据集bK-MeansEM数据 cK-MeansEM总平均24.03251.37时间消耗比值10.5表 5K=5 算法收敛时间消耗132
