【雷火UX数据挖掘】k-means聚类算法家族与R语言示例
k-means是常见的一种聚类算法，自1967年首次发表后被广泛应用在多个领域。在多年的发展基础上，k-means已经拓展出了许多变形，称为K-means算法家族。这其中就包括k-means++，k-medoids，k-medians，k-modes，k-prototype以及它们的模糊版本。这些成员都在数据分析中的聚类算法里承担着重要的作用。
本文将对以上提到的成员们的常规算法版本做简单的介绍并附上在R语言中的实练操作。
特点
1. 处理大数据效率高，但只适用于数值型数据，即它无法处理属性数据；
2. 当数据呈几个紧凑且互相分离的云状时效果很好，换言之对噪声和离群点非常敏感。
步骤
1. 随机选择初始的k个中心点，和k类一一对应；
2. 依次将每个点分配到距离其最近的中心点所对应的类；
3. 求每个类当前点集的算术均值作为每个类新的中心点；
4. 重复步骤2和3直到满足迭代终止条件，条件可以是以下任何一个：
1）没有对象被重新分配给不同的聚类；
2）没有聚类中心再发生变化；
3）实现组内平方和（Within Cluster Squared Sum，WCSS）最小；
4）达到最大迭代次数（通常大数据集需要限定最大迭代次数）。
特点
1. 聚类结果相比k-means更准确更稳定；
2. 依旧对噪声和离群点非常敏感；
3. 只适用于数值型数据。
步骤
1. 在所有点中随机选择一个点作为第一个中心点；
2. 在已有的m(m>=1)个中心点基础上，计算剩余每个点与已有的m个中心点相距最近的那个中心点之间的距离D(x),然后从这些剩余点中随机选择一个新中心点,被选中的概率为D2(x)；
3. 重复2直到选够k个中心点，开始执行k-means 算法。
特点
1. 当数据中存在噪音和离群点时, k-medoids 比 k-means更准确；
2. 计算中心的步骤时间复杂度是O(n^2)，因此大数据集运行速度较慢；
3. 只能用于数值类数据的分类。
步骤
1. 从数据点集中随机选择k个点，作为初始中心点；
2. 将剩下的点，指派到最近的中心点所属的类。在每个类中，随机用一个非中心点替换类中心点，计算交换后的SAD——若SAD增大，则维持原样；若减小，则p为新的中心点；
3. 重复步骤2，直到已达到设定的最大迭代次数或SAD值不再发生变化，迭代终止。
特点
1. 当数据中存在噪音和离群点时, k-medians的效果比k-means好；
2. 只能用于连续型（数值类）数据的分类。
步骤
1. 随机选取初始的k个中心点；
2. 计算数据集中剩余的点到每个初始中心点的距离，将点归入中心点距离最短的类中；
3. 用曼哈顿距离重新计算每个维度中心点的值；
4. 重复步骤2和3，直到中心点不再变化。
特点
1. 在不牺牲效率的前提下实现了对离散型数据的快速聚类；
2. 选用众数意味着抛弃了其他低频的属性值，从而忽略了属性间的差异，使得到的中心点很难准确反映该类特征。
步骤
1. 随机选取k个点作为中心点；
2. 计算各个剩下的数据点到中心点的距离（距离为不同属性值，也就是1的个数）；
3. 将每个点分配到距离最短的中心点的簇内，之后重新确定中心点，新的中心点每个维度上的值都是这个簇内数据点在这个维度上的众数；
4. 重复步骤2和3，直到所有中心点不再变化或达到指定迭代次数为止
步骤
1. 随机选取k个点作为中心点，确定权重因子a;
2. 计算数据集中剩余每个样本点与每个中心点的距离（数值型变量计算欧氏距离，分类型变量计算汉明距离），将其划分到离它最近的中心点的类中；
3. 重新确定中心点，数值型变量取算数均值作为新的原型的特征取值，类别型变量样本取值的众数作为新的原型的特征取值；
4. 重复步骤2和3，直到中心点不再发生变化或达到最大迭代次数为止。
往期推荐