K-Means聚类算法以及扩展算法K-Modes、K-Prototype_kmeans 的扩展

作者：黑客灵魂 | 2024-07-09 17:25:25

踩

kmeans 的扩展

k-means聚类算法是一种简单易行，时间复杂度低的聚类算法，特别是针对大规模的数据集。但其只能处理数值属性限制了他的应用范围，它的具体算法步骤如下：

1.确立最终聚类处理得到簇的个数，如果有先验知识，如知道一个数据集为有3类，则可设k=3。如果不清楚，有一些指导性方法可确定估计值；

2.选取k条初始记录作为质心，k条记录的欧式具体尽量大，说明记录的相关性低，提高聚类效果；

3.从数据集读取一条记录，计算与k个质心的欧式距离，并归并到距离最短的一个簇内，并更新簇的质心；重复第三部直至将数据集读取完；

4.重新调整记录所属的簇，这一步也是比较难理解的。因为每个簇的质心随着加入记录而更新改变，因此导致原先属于这个簇的记录由于与现在改变后的另外一个簇的质心距离更短，所以也应该重新将它分配到更短距离的那个簇上。分配后更新所有簇的质心，不断重复第四步知道没有记录重新分配。

K-means算法2个核心问题：

1.度量记录之间的相关性的计算公式，此处采用欧式距离

2.更新簇内质心的方法，此处采用平均值法，即means；

K-modes算法是按照k-means算法的核心内容进行修改，针对分类属性的的1.度量。2.更新质心的问题而改进。具体如下

1.度量记录之间的相关性D的计算公式是比较两记录之间，属性相同为0，不同为1.并所有相加。因此D越大，即他的不相关程度越强（与欧式距离代表的意义是一样的）；

2.更新modes，使用一个簇的每个属性出现频率最大的那个属性值作为代表簇的属性值(如｛[a,b] [a,c] [c,b] [b,c]｝)代表模式为[a,b]或者[a,c];

K-Prototype算法是结合K-Means与K-modes算法，针对混合属性的，解决2个核心问题如下：

1.度量具有混合属性的方法是，数值属性采用K-means方法得到P1，分类属性采用K-modes方法P2，那么D=P1+a*P2，a是权重，如果觉得分类属性重要，则增加a，否则减少a，a=0时即只有数值属性

2.更新一个簇的中心的方法，方法是结合 K-Means与K-modes的更新方法

总结：这三种方法将只针对数值属性的k-means算法扩展到可以解决分类属性与混合属性，实验结果表明k-modes的算法时间复杂度比其余两者低。三者时间复杂度成线性增长。但存在问题如下：

1.K值的确立

2. k-prototype中权重a的确立

3.k条初始记录的选取

百科解释:
k-modes算法是在数据挖掘中对分类属性型数据的采用的聚类算法。k-modes算法是对k-means算法的扩展。k-means算法是在数据挖掘领域中普遍应用的聚类算法，它只能处理数值型数据，而不能处理分类属性型数据。例如表示人的属性有：姓名、性别、年龄、家庭住址等属性。而k-modes算法就能够处理分类属性型数据。k-modes算法采用差异度来代替k-means算法中的距离。k-modes算法中差异度越小，则表示距离越小。一个样本和一个聚类中心的差异度就是它们各个属性不相同的个数，不相同则记为一，最后计算一的总和。这个和就是某个样本到某个聚类中心的差异度。该样本属于差异度最小的聚类中心。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/黑客灵魂/article/detail/803143