【ML算法】无监督学习——K-means聚类

淡淡的烟草味﹌ 2022-06-05 11:06 249阅读 0赞

### 前言 ###

这一系列文章将介绍各种机器学习算法，部分算法涉及公示推导，我的博客中有另一个板块介绍基于python和R实现各种机器学习算法，详情见置顶的目录。

### K-means算法 ###

聚类算法是一种无监督的机器学习算法，通过距离测度实现样本点的归类，算法的最终目的是使得聚簇内部样本点相似度最大，聚簇间样本点相似度最小，常见的聚类算法有k-means聚类、层次聚类、DBCAN聚类等，本文介绍K-means聚类算法，其他两种算法会陆续编辑。  
K-means算法的主要过程：  
（1）选取K值  
（2）随机确定K个初始样本中心点  
（3）计算其他样本点与聚簇中心的距离，将样本总体分成K个类  
（4）重新计算聚簇中心  
（5）重复(3)(4)两个过程，直到聚簇中心不发生变化，算法收敛  
由上面可以看出K-means聚类结果的主要影响因素如下：  
（1）距离测度选择。K-means聚类是以距离测度作为聚类依据，因此对于同一个样本点，选取不同的距离测度，得到的距离也不同，关于距离测度，在KNN算法中有所介绍，见文末，K-means聚类常用的距离测度为欧式距离，公式如下：

d(xi,xj)=∑k=1n(x(k)i−x(k)j)2‾‾‾‾‾‾‾‾‾‾‾‾‾‾⎷=∑k=1n(x(1)i−x(1)j)2\+(x(2)i−x(2)j)2\+⋯\+(x(n)i−x(n)j)2‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾⎷  d ( x i , x j ) = ∑ k = 1 n ( x i ( k ) − x j ( k ) ) 2 = ∑ k = 1 n ( x i ( 1 ) − x j ( 1 ) ) 2 + ( x i ( 2 ) − x j ( 2 ) ) 2 + ⋯ + ( x i ( n ) − x j ( n ) ) 2

（2）数据特征。由于样本点本身属性具有的数据特征，在做聚类时，会因为数据影响距离，最终影响聚类效果，比如  x  x  的有四个属性，其属性的数据范围为：  x∈((0,1),(1,10),(1,100),(100,200)) x ∈ ( ( 0 , 1 ) , ( 1 , 10 ) , ( 1 , 100 ) , ( 100 , 200 ) ) ，这种情况下，如果采取欧式距离测度，在计算时属性3和属性4的值对于距离的结果影响很大，可能直接影响了聚类结果。  
处理方法：这种情况下可以进行数据预处理，对数据进行标准化，如0/1标准化、最小最大标准化，后续会在“machine learning算法学习”版块中介绍常用的数据预处理方法。  
（3）k值选取。k值的选取在K-means算法中是一个很常见又很重要的问题，选取好的k值，可以直接得到想要的聚类效果，如果k值选不好，可能会意向最终聚类效果。  
处理方法：常见的选取k值的方法有以下两种：一是先把样本点plot出样本散点图观察数据特征，自己确定k值。二是设置一个循环，如  k∈\[2,20\]  k ∈ \[ 2 , 20 \]  ，之后执行循环，找到聚类效果最好的情况对应的k值。  
（4）初始中心点选取。由于样本聚簇初始中心点是随机选取的，具有不稳定性，如果随机选取的初始点距离较近，则很可能增加迭代次数、影响最终的聚类结果。  
处理方法：在选取初始点时，对选取原则加以限制，如随机选取相互间距离较远的k个点作为初始聚簇中心点，这就是K-means++的基本原则，将在下一节介绍。

### K-means++算法 ###

K-means++算法的基本思想为：使得初始选取的k个中心点距离尽可能远。其基本实现过程如下：  
（1）随机选取一个初始聚类中心点作为seed  
（2）对于数据集中的每个点，分别计算它与seed点的距离 d(x)  d ( x )  ，根据距离测度选出下一个中心点  
（3）重复过程（2）直到选出k个中心点  
（4）执行K-means算法  
为了降低离群点对于聚类中心的影响，在（2）中选择中心点的原则是： d(x)  d ( x )  较大的点，被选取作为聚类中心的概率较大。  
选取方法：将（2）中每个点与seed点的距离 d(x)  d ( x )  保存在数组中，然后求和得到 sum(D(x))  s u m ( D ( x ) )  ，取一个能落在sum(D(x))  s u m ( D ( x ) )  中的随机值Random  R a n d o m ，然后Random−=D(x)  R a n d o m − = D ( x )  直到其小于等于0，此时的点就是下一个中心点。  
K-means++算法可以确定初始聚类中心，但其也存在缺点：下一个中心点的选择依赖前一个中心点。

### 应用 ###

聚类算法应用广泛，对于K-means算法来讲，常用作数据降维、探索性数据分析等，同时K-means算法也经常用于进行基础聚类挖掘研究，我在之前写过一篇基于K-means聚类的临终关怀现状分析的文章，链接在文末。

### 参考资源 ###

KNN算法中关于距离测度介绍： [http://blog.csdn.net/roguesir/article/details/78580412][http_blog.csdn.net_roguesir_article_details_78580412]  
常用数据预处理方法：[http://blog.csdn.net/roguesir/article/details/78639809][http_blog.csdn.net_roguesir_article_details_78639809]  
基于K-means算法的我国临终关怀现状分析：[http://blog.csdn.net/roguesir/article/details/74940641][http_blog.csdn.net_roguesir_article_details_74940641]

[http_blog.csdn.net_roguesir_article_details_78580412]: http://blog.csdn.net/roguesir/article/details/78580412
[http_blog.csdn.net_roguesir_article_details_78639809]: http://blog.csdn.net/roguesir/article/details/78639809
[http_blog.csdn.net_roguesir_article_details_74940641]: http://blog.csdn.net/roguesir/article/details/74940641