【机器学习】k-means算法介绍及简单实现

待我称王封你为后i 2024-04-19 13:19 69阅读 0赞

### 文章目录 ###

*  前言
 *  一、什么是k-means算法
 *  二、k-means的算法过程
 *  三、k-means算法的优缺点
 *   *  3.1 优点
     *  3.2 缺点
 *  四、k-means算法简单案例
 *   *  4.1 手写实现k-means算法
 *  五、参考链接

# 前言 #

k-means算法是经典的基于划分的聚类方法，所以我们不得不先了解一下什么是聚类方法？  
1、对于"[监督学习][Link 1]"(supervised learning)，其训练样本是带有标记信息的，并且监督学习的目的是：对带有标记的数据集进行模型学习，从而便于对新的样本进行分类。而在“[无监督学习][Link 2]”(unsupervised learning)中，训练样本的标记信息是未知的，目标是通过对无标记训练样本的学习来揭示数据的内在性质及规律，为进一步的数据分析提供基础。对于无监督学习，应用最广的便是"聚类"(clustering)。  
2、“聚类算法”试图将数据集中的样本划分为若干个通常是不相交的子集，每个子集称为一个“簇”(cluster)，通过这样的划分，每个簇可能对应于一些潜在的概念或类别。

了解了以上两个概念之后，我们现在开始学习K-means算法。

--------------------

# 一、什么是k-means算法 #

【不说废话，直奔主题】k-means算法又被称为k均值算法。它的算法思想是： `先从样本集中随机选取k个样本作为簇中心，并计算所有样本与这个k个“簇中心”的距离，对于每个样本，将其划分到其距离最近的“簇中心”所在的簇中，对于新的簇计算各个簇的型的“簇中心”。`说的有些绕口，k-means聚类算法的思想打个比方的话就是：物以类聚，人以群分。  
小结一下上述的k-means算法的思想：

> 1、k个样本作为簇中心  
> 2、各个样本点到“簇中心”的距离  
> 3、根据新划分的簇，更新“簇中心”(这里其实就是迭代的思想奥)

好吧，大体的思想就是如所述所说，但是，难免您会觉得空乏无味，难以理解，那我们继续更生动的再次理解一下：

> 1、首先输入k个值，即我们指定希望通过聚类得到k个分组  
> 2、从数据集中随机选取k个数据点作为初始大佬(质心)  
> 3、对数据集中的每个小弟，计算每个小弟距离每个大佬的距离，离大佬距离近，就跟那个大佬  
> 4、执行完步骤3后，每个大佬都会有一帮各自的小弟，这时候每一群选出一个新的大佬(即通过算法选出新的质心)  
> 5、如果新大佬和老大佬之间的距离小于某一个设置的阈值(表示重新计算的质心的位置变化不大，趋于稳定，或者说收敛)，可以认为我们进行的聚类已经达到了期望的结果，算法终止。  
> 6、如果新大佬和老大佬之间的距离变化大，需要迭代3-5步。

更多解释可参考：[https://www.cnblogs.com/qingyunzong/p/9760913.html\#\_label1][https_www.cnblogs.com_qingyunzong_p_9760913.html_label1]

关于k-means的算法思想我们就解释到这里啦，接下来我们就说说关于k-means算法的计算过程  
分割线秀一波—

--------------------

# 二、k-means的算法过程 #

**先走一个流程框图大体悄悄：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppYWppa2FuZ19qams_size_16_color_FFFFFF_t_70]

**一、输入**  
A、输入训练集：  
 D = x ( 1 ) , x ( 2 ) , … , x ( m ) D=x^\{(1)\}, x^\{(2)\}, \\ldots, x^\{(m)\} D=x(1),x(2),…,x(m)  
B、输入k个样本作为簇中心

**二、过程：函数kMeans(D,k,maxIter)**

1：从D中随机选择k个样本作为初始"簇中心"向量： μ ( 1 ) , μ ( 2 ) , … , μ ( k ) \\mu^\{(1)\}, \\mu^\{(2)\}, \\dots, \\mu^\{(k)\} μ(1),μ(2),…,μ(k)。  
2：repeat  
             令  C i = ∅ ( 1 ≤ i ≤ k ) C\_\{i\}=\\emptyset(1 \\leq i \\leq k) Ci=∅(1≤i≤k)  
             for j=1,2,…,m do  
                       计算样本 x ( j ) x^\{(j)\} x(j)与各“簇中心”向量 μ i ( 1 ≤ i ≤ k ) \\mu^\{i\}(1\\leq i \\leq k) μi(1≤i≤k) 的欧氏距离  
                       根据距离最近的“簇中心”向量确定 x j x^\{j\} xj的簇标记： λ j = argmin ⁡ i ∈ \{ 1 , 2 , … , k \} d j i \\lambda\_\{j\}=\\operatorname\{argmin\}\_\{i \\in\\\{1,2, \\ldots, k\\\}\} d\_\{j i\} λj=argmini∈\{ 1,2,…,k\}dji  
                       将样本 x j x^\{j\} xj划分到相应的“粗标记”： C λ j = C λ j ∪ \{ x ( j ) \} C\_\{\\lambda\_\{j\}\}=C\_\{\\lambda\_\{j\}\} \\cup\\left\\\{x^\{(j)\}\\right\\\} Cλj=Cλj∪\{ x(j)\}  
             end for  
              for i=1,2,…k do  
                       计算新"簇中心"向量： ( μ ( i ) ) ′ = 1 ∣ C i ∣ ∑ x ∈ C i x \\left(\\mu^\{(i)\}\\right)^\{\\prime\}=\\frac\{1\}\{\\left|C\_\{i\}\\right|\} \\sum\_\{x \\in C\_\{i\}\} x (μ(i))′=∣Ci∣1∑x∈Cix  
                       if  ( μ ( i ) ) ′ \\left(\\mu^\{(i)\}\\right)^\{\\prime\} (μ(i))′= μ ( i ) \\mu^\{(i)\} μ(i) then  
                                   将当前“簇中心”向量 μ ( i ) \\mu^\{(i)\} μ(i) 更新为 ( μ ( i ) ) ′ \\left(\\mu^\{(i)\}\\right)^\{\\prime\} (μ(i))′  
                       else  
                                   保持当前均值向量不变  
                                    
                       end if  
              end for  
              else  
    until 当前“簇中心”向量均为更新  
输出： C = C 1 , C 2 , … , C K C=C\_\{1\}, C\_\{2\}, \\ldots, C\_\{K\} C=C1,C2,…,CK

上述也就是程序实现的大体伪代码思想。

既然是算法，应该有它的优缺点，那接下来就说说k-means算法的优缺点

同样分割线来一波

--------------------

# 三、k-means算法的优缺点 #

## 3.1 优点 ##

> 1、容易理解，聚类效果不错  
> 2、处理大数据集的时候，该算法可以保证较好的伸缩性和高效性(这里是参考的伸缩性我也不太懂啥意思)，其实用大白话来说：聚类效果较好。  
> 3、当簇接近高斯分布的时候，效果较好

## 3.2 缺点 ##

> 1、k值是用户给定的，在绝情数据处理前，k值是不知道的，不同的k值得到的结果自然也就不一样  
> 2、对初始“簇中心”是敏感的  
> 3、不合适发现非凸形状的簇或者大小差别较大的簇  
> 4、特殊值(离散值，另外数据集要求是连续的)对模型的影响较大

接下来我们继续看看使用程序来实现k-means算法的一些简单案例  
老规矩，你懂得

--------------------

# 四、k-means算法简单案例 #

## 4.1 手写实现k-means算法 ##

**1、数据集(testSet.txt)**

1.658985	4.285136
    -3.453687	3.424321
    4.838138	-1.151539
    -5.379713	-3.362104
    0.972564	2.924086
    -3.567919	1.531611
    0.450614	-3.302219

说明：每行表示二维空间的一个点，其实就是(x,y)坐标哇  
**2、源码**

""" author:jjk datetime:2019/5/2 coding:utf-8 project name:Pycharm_workstation Program function: """
    from numpy import *
    import numpy as np
    import matplotlib.pyplot as plt
    
    # 1、读取数据
    def loadDateSet(fileName):
    	dataMat = []
    	fr = open(fileName)  # 打开文件
    	for line in fr.readlines():  # 遍历文件的每一行(每行表示一个数据)
    		curLine = line.strip().split('\t')  # 处理每行数据，返回字符串list
    		fltLine = list(map(float, curLine))  # 使用float函数处理list中的字符串，使其为float类型
    		dataMat.append(fltLine)  # 将该数据加入到数组中
    	return dataMat
    
    # 2、向量距离计算
    def distEclud(vecA, vecB):
    	return sqrt(sum(power(vecA-vecB, 2)))  # 欧氏距离
    
    
    # 3、构建一个包含k个随机质心的集合
    def randCent(dataSet, k):
    	n = shape(dataSet)[1]  # 数据特征个数(即数据维度)
    	# 创建一个0矩阵，其中zeros为创建0填充的数组，mat是转换为矩阵，用于存放k个质心
    	centroids = mat(zeros((k, n)))
    	for i in range(n):  # 遍历每个特征
    		minI = min(dataSet[:,i])  # 获取最小值
    		rangeI = float(max(dataSet[:, i]) - minI)  # 范围
    		centroids[:, i] = minI + rangeI * random.rand(k, 1)  # 最小值+范围*随机数
    	return centroids
    
    # 测试
    #datMat = mat(loadDateSet('testSet.txt'))
    #print(min(datMat[:,0]))
    #print(randCent(datMat, 2))
    
    
    # 4.K均值聚类算法
    """ dataSet:数据集 k:簇的个数 distMeas:距离计算 createCent:创建k个随机质心 关于距离计算方式与随机生成k个质心可以选择其他方法 """
    def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent):
    	m = shape(dataSet)[0]  # 数据数目
    	clusterAssment = mat(zeros((m, 2)))
    	# 储存每个点的簇分配结果，第一列记录簇索引，第二列记录误差，
    	# 误差指当前点到簇质心的距离，可用于评估聚类的效果
    	centroids = createCent(dataSet, k)  # 质心生成
    	clusterChanged = True  # 标记变量，为True则继续迭代
    	while clusterChanged:
    		clusterChanged = False
    		# 1.寻找最近的质心
    		for i in range(m):  # 遍历每个数据
    			minDist = inf  # 最小距离
    			minIndex = -1  # 最小距离的索引
    			for j in range(k):  # 遍历每个质心
    				distJI = distMeas(centroids[j, :], dataSet[i, :])  # 计算该点到每个质心的距离
    				if distJI < minDist:  # 与之前的最小距离比较
    					minDist = distJI  # 更新最小距离
    					minIndex = j  # 更新最小距离的索引
    			# 到此，便得到了该点到哪个质心距离最近
    			# =======================================
    			if clusterAssment[i, 0] != minIndex:  # 如果之前记录的簇索引不等于目前最小距离的簇索引
    				clusterChanged = True  # 设置为True，继续遍历，直到簇分配结果不再改变为止
    			clusterAssment[i, :] = minIndex, minDist**2  # 记录新的簇索引和误差
    		# print(centroids)
    		# 2.更新质心的位置
    		for cent in range(k):
    			ptsInclust = dataSet[nonzero(clusterAssment[:, 0].A == cent)[0]]  # 获取给定簇的所有点
    			""" clusterAssment[:, 0].A == cent：表示clusterAssment第一列簇索引是否等于当前的簇 nonzero：返回一个元祖，第一个元素为True所在的行，第二个元素为True所在的列，这里取为行，即取出给定簇的数据 例如： a = mat([[1,1,0],[1,1,0],[1,0,3]]) nonzero(a) # 返回非0元素所在行和列 (array([0, 0, 1, 1, 2, 2], dtype=int64), array([0, 1, 0, 1, 0, 2], dtype=int64)) """
    			centroids[cent, :] = mean(ptsInclust, axis=0)  # 然后计算均值，axis=0沿着列方向
    	return centroids, clusterAssment  # 返回质心与点分配结果
    
    
    datMat = mat(loadDateSet('testSet.txt'))
    myCentroids, clusterAssing = kMeans(datMat, 4)
    
    # 5.画图
    marker = ['s', 'o', '^', '<']  # 散点图点的形状
    color = ['b','m','c','g']  # 颜色
    X = np.array(datMat)  # 数据点
    CentX = np.array(myCentroids)  # 质心点4个
    Cents = np.array(clusterAssing[:,0])  # 每个数据点对应的簇
    for i,Centroid in enumerate(Cents):  # 遍历每个数据对应的簇，返回数据的索引即其对应的簇
    	plt.scatter(X[i][0], X[i][1], marker=marker[int(Centroid[0])],c=color[int(Centroid[0])])  # 按簇画数据点
    plt.scatter(CentX[:,0],CentX[:,1],marker='*',c = 'r')  # 画4个质心
    plt.show()

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppYWppa2FuZ19qams_size_16_color_FFFFFF_t_70 1]  
获取源码：[链接下文件名为：k-means\_01.py文件][k-means_01.py]  
除此之外，还有关于改进k-means算法的二分k均值(二分k-means算法)、k-means++算法、Canopy+k-means算法、Mini Batch k-means。

# 五、参考链接 #

1、[https://www.cnblogs.com/lliuye/p/9144312.html][https_www.cnblogs.com_lliuye_p_9144312.html]  
2、[https://blog.csdn.net/Daycym/article/details/84774164][https_blog.csdn.net_Daycym_article_details_84774164]

[Link 1]: https://blog.csdn.net/Jiajikang_jjk/article/details/99705122#211_clustering_53
[Link 2]: https://blog.csdn.net/Jiajikang_jjk/article/details/99705122#212_unsemisupervised_56
[https_www.cnblogs.com_qingyunzong_p_9760913.html_label1]: https://www.cnblogs.com/qingyunzong/p/9760913.html#_label1
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppYWppa2FuZ19qams_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/2bf1abdc1e2745e4ac4ca154a42d1568.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppYWppa2FuZ19qams_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/baa093442b734a1286fab5a4693a2554.png
[k-means_01.py]: https://github.com/jiajikang-nlp/NLP-related-algorithm-learning/tree/master/Machine%20Learning%28ML%29
[https_www.cnblogs.com_lliuye_p_9144312.html]: https://www.cnblogs.com/lliuye/p/9144312.html
[https_blog.csdn.net_Daycym_article_details_84774164]: https://blog.csdn.net/Daycym/article/details/84774164