基于R语言的Kmeans聚类算法

vlambda
2020-09-18

基于R语言的Kmeans聚类算法

题记：本文是个人的读书笔记，仅用于学习交流使用。

解决什么问题

本节介绍一下Kmeans聚类，也叫K均值聚类或者是动态聚类法。k-means算法也属于无监督学习的一种聚类算法。采用R语言详细描述Kmeans实现过程。

这种聚类方法的优势在于，对于大样本的聚类，具有计算量小，占用计算机内存较少和方法简单的优点。

算法思想

假设我们要把数据分成k个类，大概可以分为以下几个步骤：

1. 随机选取k个点，作为每个类别的类心；

2.分别计算每个点到这k个中心的距离(点与点的距离计算)，将该点分到最近的聚类中心，这样就形成了k个簇；

3.更新每个簇的类心（均值）；

4.重复以上2~3步，直到类心的位置不再发生变化或者达到设定的迭代次数。

其中第三步是：类心的计算公式如下，其中表示第k类，表示第k类中数据对象的个数：

基于R语言的Kmeans聚类算法

第四步类心的迭代公式：

基于R语言的Kmeans聚类算法

下面我们通过一个具体的例子来理解这个算法，假设我们首先拿到了这样一个数据，要把它分成两类：

1.下图中，人眼可以很快的分辨出来，可以在两个聚类间找到一条合理的分界线。

基于R语言的Kmeans聚类算法

2.首先我们随机选取样本中任意两个点作为聚类中心。根据选取的两点，通过第一次迭代，将图中黑色的点归为一类，蓝色的点归为另一类。

基于R语言的Kmeans聚类算法

3.根据第一次迭代将生成的两类数据，分别求出每个簇的类心。相当于原理第三步。并再次计算每个点与新的类心距离，将点分到最近的类心。

由图可以看到经过第二次迭代，数据正确分成2簇。

基于R语言的Kmeans聚类算法

采用R代码将上述算法原理详细实现一遍，更多采用python写，清楚了原理，用哪种语言写，都是很随意的。当然R里面有封装的好的Kmeans函数，一句代码就做完所有的事，但还是建议大家，自己写一遍算法，有助于理解。

### Kmeans 均值聚类#为给定数据集构建一个包含K个随机质心的集合randcent <- function(dt,k){ centroids <- as.data.frame(matrix(0,nrow = k,ncol=ncol(dt))) colnames(centroids) <- colnames(dt)  for(i in 1:k){ index <- sample(1:nrow(dt),1,replace =T) centroids[i,] <- dt[index,] } return(centroids)}

建立一个对象，存放样本点所属簇和每个样本点与类心的距离。

 #行的数目# 第一列存样本属于哪一簇# 第二列存样本的到簇的中心点的误差(用距离表示)clusterAssment = data.frame(class = rep(0,nrow(dt)),                 error = rep(0,nrow(dt)))

编写Kmeans算法：

kmeans_fit <- function(dt,k){clusterAssment = data.frame(class = rep(0,nrow(dt)), error = rep(0,nrow(dt))) clusterChange = T # 第1步 初始化centroids centroids = randcent(dt,k=2) step=1 while(clusterChange){ clusterChange = F # 遍历所有的样本（行数） for(i in 1:nrow(dt)){ minDist = 100000.0      minIndex = -1      # 遍历所有的质心       #第2步 找出最近的质心 for(j in 1:k){ dt_ <- rbind(dt[i,],centroids[j,]) d <- dist(dt_) if(d < minDist){ minDist <- d; minIndex<- j} } # 第 3 步：更新每一行样本所属的簇 if(clusterAssment[i,1]!= minIndex){ clusterChange = T clusterAssment[i,1] <- minIndex clusterAssment[i,2] <- minDist } } #第 4 步：更新质心 for(i in 1:k){ loc <- which(clusterAssment[,1]==i)  pointsIncluster <- dt[loc,] # 获取簇类所有的点 centroids[i,] <- apply(pointsIncluster,2,mean) ##对数据集的列就均值 } step=step+1 ##观察迭代次数 print(step) } print("Congratulations,cluster complete!") re <- list(centroids=centroids,clusterAssment=clusterAssment) return(re)}

运行这个简易的算法模型

dt <- data.frame(x1 = c(5,6,4.5,0.5,2,-3,-2.5,-2,0,-4,3,-1), x2=c(5,2,2,2.1,1,0,-1,-2,-4,-3.5,3,-1.75))re <- kmeans_fit(dt,2)###查看运行完的结果re$centroids;re$clusterAssment  ## 可查看所属簇和类心library(ggplot2)qplot(dt$x1,dt$x2,color=clusterAssment$class) ###画图

案例实战

03部分，我们采用一个小例子拆解了Kmeans的基本算法原理，接下来我们可以拿这个代码跑一遍中的葡萄酒案例，跟层次聚类的结果对比一下，匹配效果达到95%，效果还是不错的。请注意之所以让K=3也是继承了之前的最优聚类个数的选择。

library(HDclassif) #contains the dataset ##葡萄酒数据集data(wine)names(wine) <- c("Class", "Alcohol", "MalicAcid", "Ash", "Alk_ash", "magnesium", "T_phenols", "Flavanoids", "Non_flav",                 "Proantho", "C_Intensity", "Hue", "OD280_315", "Proline")df <- as.data.frame(scale(wine[, -1]))re <- kmeans_fit(df,3)table(re$clusterAssment[,1],wine$Class) ###匹配度达95%

基于R语言的Kmeans聚类算法

Kmeans()函数详解

接下来我们用R自带的Kmeans函数跑一遍这个葡萄酒数据集，首先介绍一下Kmeans()函数：

kmeans(x, centers, iter.max = 10, nstart = 1,algorithm = c("Hartigan-Wong", "Lloyd","Forgy", "MacQueen"))

其中：

1.待聚类样本组织在x指定的矩阵或数据框中。

2.参数centers：若为一个整数，则表示聚类数目K；若为一个矩阵（行数等于聚类数目K，列数等于聚类变量个数），则表示初始类质心，每一行表示一个初始类质心。

3.参数iter.max用于指定最大迭代次数，默认为10次。R中仅以最大迭代次数作为终止迭代条件。

4.当参数为centers为一个整数时，R将采用随机选择法从数据中抽取K个观测值作为初始类质心。我们，不同的初始类质心对最终的聚类结果是存在影响的。所以，R为克服大数据集下终止迭代次数不充分大时，初始类质心抽取的随机性对聚类结果的影响，可指定参数nstar为一个大于1的值（默认为1），表示重复多次抽取质心。

5.参数algorithm，用于指定迭代算法，其中"Lloyd"是经典的算法，就是上面自己编写代码的实现过程，但这种算法针对不平衡数据效果不太好，而"Hartigan-Wong"则是改进的针对不平衡数据的算法，作为默认算法。每一种算法的实现过程，有兴趣的朋友可以参看参考文献3。

返回结果解释：

Kmeans函数的返回结果是一个列表，包括如下成分：

1.cluster：存储各观测所属的类别编号，也称聚类解。

2.centers：存储各个类的最终类质心。

3.totss：所有聚类变量的离差平方和之和，是对类内部观测数据点离散程度的测度。

4.cotwithss：每个类内所有聚类变量的离差平方和之和的总和。

5.betweenss：各类别间的聚类变量离差平方和之和

6.size：各类的样本量。

Kmeans聚类

现在选择3个簇进行Kmeans聚类，现在计算距离矩阵，并建立层次聚类模型。如下所示：

set.seed(1234) ##设定随机数种子km <- kmeans(scale(df), 3, nstart = 25)  #设置随机分配的参数nstart

对比K均值聚类结果和品种等级：

table(km$cluster, wine$Class)

这个表中，聚类结果匹配了96%的品种等级。与层次聚类的ward.D2相比，这两种方法效果相似，因此可以将任意一种作为最优的聚类方法。

总结

以上是针对全部是数值型的数据做的分类，用R语言实现是非常简单的。如果数据里面既有数值型，又有非数值型，用什么聚类方法呢？后面有机会再跟大家介绍另外集中聚类方法。

参考文献

薛毅等.统计建模与R软件.清华大学出版社
Cory Leismester.精通机器学习.基于R.人民邮电出版社
https://blog.csdn.net/joeland209/article/details/72147763

作介绍：医疗大数据统计分析师,擅长R语言。

欢迎各位在后台留言，恳请斧正！

更多阅读

长按二维码

易学统计

vlambda博客
学习文章列表