/【雷火UX数据挖掘】k-means聚类算法家族与R语言示例
最新文章2023-05-05

【雷火UX数据挖掘】k-means聚类算法家族与R语言示例


k-means是常见的一种聚类算法，自1967年首次发表后被广泛应用在多个领域。在多年的发展基础上，k-means已经拓展出了许多变形，称为K-means算法家族。这其中就包括k-means++，k-medoids，k-medians，k-modes，k-prototype以及它们的模糊版本。这些成员都在数据分析中的聚类算法里承担着重要的作用。

本文将对以上提到的成员们的常规算法版本做简单的介绍并附上在R语言中的实练操作。

01
k-means

特点

1. 处理大数据效率高，但只适用于数值型数据，即它无法处理属性数据；

2. 当数据呈几个紧凑且互相分离的云状时效果很好，换言之对噪声和离群点非常敏感。

步骤

1. 随机选择初始的k个中心点，和k类一一对应；

2. 依次将每个点分配到距离其最近的中心点所对应的类；

3. 求每个类当前点集的算术均值作为每个类新的中心点；

4. 重复步骤2和3直到满足迭代终止条件，条件可以是以下任何一个：

1）没有对象被重新分配给不同的聚类；

2）没有聚类中心再发生变化；

3）实现组内平方和（Within Cluster Squared Sum，WCSS）最小；

4）达到最大迭代次数（通常大数据集需要限定最大迭代次数）。



02
k-means++
k-means++是对k-means算法的一个改进。由于k-means初始聚类中心的选取是随机的，这种随机性对结果的影响很大，因此k-means++给出了一种优化初始中心点选取的方法：


特点

1. 聚类结果相比k-means更准确更稳定；

2. 依旧对噪声和离群点非常敏感；

3. 只适用于数值型数据。



步骤

1. 在所有点中随机选择一个点作为第一个中心点；

2. 在已有的m(m>=1)个中心点基础上，计算剩余每个点与已有的m个中心点相距最近的那个中心点之间的距离D(x),然后从这些剩余点中随机选择一个新中心点,被选中的概率为D2(x)；

3. 重复2直到选够k个中心点，开始执行k-means 算法。



03
k-medoids
k-medoids与k-means不同之处在于它每个类的中心点定义为当前簇中所有其他点到该中心点的距离之和最小的那个点，即追求绝对差值和（Sum of Absolute Differences，SAD）最小。这是一种围绕中心点划分（Partitioning Around Medoids，PAM）的方法。PAM方法在设定一个最大迭代次数的基础上，会在过程中基于贪心策略来选择使得聚类的结果质量最高的中心点。计算得到的SAD值越小，则代价越小，聚类质量越好。


特点

1. 当数据中存在噪音和离群点时, k-medoids 比 k-means更准确；

2. 计算中心的步骤时间复杂度是O(n^2)，因此大数据集运行速度较慢；

3. 只能用于数值类数据的分类。



步骤

1. 从数据点集中随机选择k个点，作为初始中心点；

2. 将剩下的点，指派到最近的中心点所属的类。在每个类中，随机用一个非中心点替换类中心点，计算交换后的SAD——若SAD增大，则维持原样；若减小，则p为新的中心点；

3. 重复步骤2，直到已达到设定的最大迭代次数或SAD值不再发生变化，迭代终止。

04
k-medians
不同于k-means使用欧式距离计算目标函数，k-medians使用曼哈顿（Manhattan）距离。在迭代过程中，用的是类样本在每个维度上的中位数来当作为中心点在该维度上的值，而k-means用的是算术均值且不按每个维度来计算。


特点

1. 当数据中存在噪音和离群点时, k-medians的效果比k-means好；

2. 只能用于连续型（数值类）数据的分类。



步骤

1. 随机选取初始的k个中心点；

2. 计算数据集中剩余的点到每个初始中心点的距离，将点归入中心点距离最短的类中；

3. 用曼哈顿距离重新计算每个维度中心点的值；

4. 重复步骤2和3，直到中心点不再变化。

05
k-modes
之前提到的基于k-means的各个算法并不适用于非数值型的数据，因而产生了k-modes。它可以应用于离散型数据，其两点之间的距离计算采用的是汉明（Hamming）距离(相同=0，不同=1)。而一个类中心点的每个维度是本类成员中相应维度出现频率最大的那个值（众数）。


特点

1. 在不牺牲效率的前提下实现了对离散型数据的快速聚类；

2. 选用众数意味着抛弃了其他低频的属性值，从而忽略了属性间的差异，使得到的中心点很难准确反映该类特征。



步骤

1. 随机选取k个点作为中心点；

2. 计算各个剩下的数据点到中心点的距离（距离为不同属性值，也就是1的个数）；

3. 将每个点分配到距离最短的中心点的簇内，之后重新确定中心点，新的中心点每个维度上的值都是这个簇内数据点在这个维度上的众数；

4. 重复步骤2和3，直到所有中心点不再变化或达到指定迭代次数为止

06
k-prototype
k-means适合于连续型数据，k-modes适用于离散型数据，而当数据集里有的维度是连续属性，有的维度是离散属性的时候，即数据集是混合属性，就可以用k-prototype了。其度量距离的方法为：连续属性采用欧式距离，离散属性采用Hamming距离，然后两种距离的加权就是最后的距离。
数值属性采用K-means的欧式计算方法得到P1，分类属性采用K-modes的取众数方法得到P2，距离公式可以简单表示为D=P1+a*P2，参数a为权重。若分类属性重要，则增加a，若数值属性重要，则减小a。


步骤

1. 随机选取k个点作为中心点，确定权重因子a;

2. 计算数据集中剩余每个样本点与每个中心点的距离（数值型变量计算欧氏距离，分类型变量计算汉明距离），将其划分到离它最近的中心点的类中；

3. 重新确定中心点，数值型变量取算数均值作为新的原型的特征取值，类别型变量样本取值的众数作为新的原型的特征取值；

4. 重复步骤2和3，直到中心点不再发生变化或达到最大迭代次数为止。

07
R中实战操作
此处省略复杂的数据清洗步骤，假定数据集已经清洗完毕且名为df。
1. 载入需要用到的package
library(cluster)  # 聚类算法
library(tidyverse)  # 数据处理
library(factoextra) # 聚类算法&可视化
2. 在正式跑kmeans之前，我们需要先确定一个合理的K值，此时可以用大家比较熟悉的Elbow Method（手肘法）或者Silhouette Coefficient（轮廓系数）
set.seed(123)
fviz_nbclust(df, kmeans, method = "wss")

fviz_nbclust(df, kmeans, method = "silhouette")

如上两张图所示，在k=2和4的时候产生了明显的拐点或轮廓系数值较高。由于两类较少，当k=4时聚类效果更好。因此我们选择k=4
3. 对数据建立模型：
set.seed(123)
result <- kmeans(df, centers = 4, iter.max = 15, nstart = 25)
centers要么是类的个数，要么是一组中心点，如果是个数，中心点将随机选取
iter.max是最大迭代次数
如果centers是数字，nstart决定了需要随机取几组中心点
默认的kmeans执行的数据格式为kmeans(x, centers, iter.max = 10, nstart = 1)
4. 查阅分类结果
str(result)
通过str()，我们可以看到一系列关于分类结果的文字信息（如下图所示）
如果有特定想查看的，也可以直接使用result$...的方式单独显示，例result$cluster

Cluster：显示每个点被分配到了第几个簇中
Centers：中心点的矩阵
Totss：总平方和
Withinss：簇内平方和的矢量
Tot.tiwhinss: 总簇内平方和
Betweenss：总簇间平方和
Size：每个簇内的数据点个数
同样，也可以通过可视化的功能更直观的查阅分类结果
fviz_cluster(result, data = df)



往期推荐

本文来自微信公众号“网易雷火UX用户体验中心”（ID：LeihuoUX）。大作社经授权转载，该文观点仅代表作者本人，大作社平台仅提供信息存储空间服务。

TAGS:

相关文章