KMeans

典型的$划分聚类$

使用场景

1. KMeans算法属于无监督学习，解决聚类的问题
2. 对于数据集D， 不需提供数据标记，大大减少工作量
3. 数据集D必须是凸集，非凸数据集难以收敛
4. 必须先指定聚类簇数k

k-means优点

1. 原理简单，实现容易，可解释性较强
2. 聚类效果较好
3. 主要的调参只有k

k-means缺点

1. k值的选择不好把握
2. 只适用于凸集，非凸数据集难以收敛
3. 损失函数非凸，易收敛于局部最优解
4. 对于噪声和异常点比较敏感

基本思想

簇内尽量紧凑，簇间尽量分散

算法步骤

1. 随机初始化$k$个聚类中心点：可以从样本集S中随机选择，也可以随机生成
2. 遍历样本集S所有样本点，计算每个样本$x_i$到$k$个中心点的距离，将$x_i$分配给距离最近的中心点所在的簇(给$x_i$一个标记${\hat{y}}_i$)
3. 取各个簇内所有样本的均值样本作为新的聚类中心点
4. 重复2，3过程，直到达到一定的迭代次数或者聚类中心不再改变
   
   

python实现

import numpy as np
from matplotlib import pyplot as plt
import logging
logging.basicConfig(level=logging.INFO,format="%(asctime)s %(message)s")
import os


#计算欧式距离
def l2(x,y):
    """
    x:样本点向量
    y:样本点向量
    return:距离标量
    """
    return np.sqrt(np.sum(np.power(x-y,2)))

#初始化聚类中心 函数
def init_centers(S,k,method="select"):
    """
    S:样本数据集，np数组
    k:初始化聚类中心点的个数
    method:初始化的方式
            defaul,'select',random select k points from S
                    'random',random generation of k points
    
    return np数值
    """
    if method=="select":
        #select k points from S
        points=np.arange(S.shape[0])
        select_points=np.random.choice(points,k)
        return S[select_points]
    
    elif method=="random":
        #random generation
        #样本集S每一列特征的min,max之间随机生成一个数值
        
        #样本集的特征数
        n=S.shape[1]
        #初始化聚类中心点
        centers=np.empty((k,n))
        
        #生成聚类中心点每个特征的值
        for j in range(n):
            min_j,max_j=S[:,j].min(),S[:,j].max()
            range_j=max_j-min_j
            
            #生成第j特征的值,一维赋值
            centers[:,j]=(min_j+range_j*np.random.rand(k,1)).ravel()
                     
        
        return centers
    
    else:
        #待扩展功能
        pass

def nearest_neighbors(x,centers):
    """
    x:单个样本向量
    centers:聚类中心点，np数值
    
    return (min_index,min_dist)
    min_index:最近邻的索引
    min_dist:最近邻的距离
    """
    #初始化最小距离及其索引
    min_index=-1
    min_dist=np.inf #正无穷
    
    #遍历中心点，计算距离
    for idx,center in enumerate(centers):
        x_center_dist=l2(x,center)
        
        if x_center_dist<min_dist:
            min_dist=x_center_dist
            min_index=idx
            
    return min_index,min_dist
        
    
#定义KMeans聚类函数
def kmeans(S,k,dist_measure=l2,max_iter=10,min_threshold=0.05):
    """
    S:样本集，np数组
    k:聚类簇数
    dist_measure:距离度量,默认欧式距离
    max_iter:最大迭代次数,int
    min_threshold:聚类中心点变化的距离阈值，小于这个幅度则停止迭代
        
    return (tag,centers,sse_list)
    tag:样本标签
    centers:聚类中心点
    sse_list:误差平方和 list
    """
    
    #样本总数,特征总数
    m,n=S.shape
    logging.info("current samples shape:%d,%d"%(m,n))
    
    
    #1初始化k个聚类中心点
    cluster_centers=init_centers(X,k,method="random")
    #初始化样本标签 tag
    tag=np.zeros(m)
    #迭代过程中的sse
    sse_list=[]
    
    #控制迭代的轮数，只实现max_iter
    iter_times=0
    while max_iter and iter_times<max_iter:
        #初始化误差平方和
        sse=0
        #2 计算所有样本的  最近邻 聚类中心
        for i in range(m):
            min_index,min_dist=nearest_neighbors(S[i,:],cluster_centers)
            
            #样本i放入最近邻中心点所在簇
            tag[i]=min_index
            sse+=min_dist**2
        sse_list.append(sse)
        #重新计算聚类中心点
        for idx in range(k):
            cluster_centers[idx,:]=np.mean(S[y_hat==idx],axis=0)
        
        iter_times+=1
        
    return tag,cluster_centers,sse_list
        
if __name__=="__main__":
    X=np.loadtxt("kmeansSamples.txt")
    y_hat,centers,sse_list=kmeans(X,3,max_iter=6)
    print("cluster tag:",y_hat)
    print("sse list",sse_list)
    fig=plt.figure()
    plt.scatter(X[:,0],X[:,1],s=50,c=y_hat,label="samples")
    plt.scatter(centers[:,0],centers[:,1],s=300,c=np.unique(y_hat),marker="*",label="centers")
    plt.grid()
    plt.legend(loc="best",frameon=True,framealpha=0.7)
    plt.title("KMeans cluster")
    plt.axis("equal")
    fig.show()

sklearn库的实现

from sklearn.cluster import KMeans
from sklearn.preprocessing import StandardScaler
import numpy as np
from matplotlib import pyplot as plt
#实例化一个kmeans对象
kmeans=KMeans(n_clusters=3,random_state=9)
#加载数据
x=np.loadtxt("kmeansSamples.txt")
#数据归一化
ss=StandardScaler()
x_scale=ss.fit_transform(x)
#聚类拟合
kmeans.fit(x_scale)
#聚类标签
kmeans.labels_
#聚类中心点
kmeans.cluster_centers_
#对未知样本分簇
y_pred=kmeans.predict(x_new)

改进的kmeans

1. 二分k-means：对每个簇进行k=2的kmeans聚类分簇，对SSE减少最多的簇优先二分聚类，促使算法收敛于全局最优解
2. k-means++：初始化距离较远的聚类中心点(避免初始化中心点的扎堆)，促使算法收敛于全局最优解
3. k-mediods：重新选择聚类中心，而不是取每个簇的均值，让本簇所有其他样本点到该点的距离和最小，减少噪声的干扰
4. mini batch kmeans：对大数据集时，采用抽样部分数据集做kmeans聚类，利用找到的聚类中心，对整个数据集分簇，从而降低kmeans的时间复杂度，但是以降低部分优化质量为代价。

基于kmeans项目

KMeans总结

最后一次回顾KMeans聚类算法。

KMeans聚类算法的原理

• 一个数据集如下，我们希望将它分为两个簇（因为通过人的观察，它看起来像是可以分成两个簇，KMeans聚类算法的K是需要操作人员自己选择的，这也是这个算法的弊端之一，可以通过肘部法则（手肘法）来改善）👇。
  
• KMeans聚类算法的第一步，是初始化聚类中心。通常我们使用随机初始化的方法，即，在已经给定的样本点中选取聚类中心。但此处为了说明问题，使用了另一种方法初始化聚类中心，但是无论使用哪种初始化的方法，最终都是有可能得到最佳结果的。
  
  👆生成两个聚类中心，因为我们希望将数据集分为两个簇。
• 显然，KMeans聚类算法是一个需要迭代的方法，它通过不断的迭代，改变聚类中心的位置和样本点与聚类中心的关系划分，当迭代不使结果产生改变时 ，说明分类的工作已经完成，可以退出循环返回结果了。每一步的迭代，KMeans聚类算法要做两件事，第一件事是为样本点寻找合适的聚类中心，即，某个样本点与哪一个聚类中心的欧氏距离最近，那么就将这个样本点划分给哪个聚类中心。
  
• KMeans聚类算法要做的另一件事情，是改变聚类中心，由上图可知，由于该例中只需要将数据集分为两个簇，因此使用红色和蓝色代表两个簇的聚类中心和簇中样本点。改变聚类中心，说的是将某个簇的聚类中心重新放到属于这个簇的样本点的平均中心位置。
  
  👆聚类中心改变前，聚类中心改变后👇
  
  划分完聚类中心之后，便进入到了下一次迭代，此时要先重新为所有样本点选择新的聚类中心，因为上一次迭代的最后一步，聚类中心的位置改变了。之后再改变聚类中心的位置，依次迭代，直到聚类中心的位置和样本点的划分都不再发生改变，结束迭代，分类完成。
  

KMeans聚类算法的缺点

• 聚类的个数在开始就要设定。
• 聚类的结果取决于初始设定的聚类中心。
• 对异常值很敏感。
• 不适合用于发现非凸聚类问题。
• 不能保证得到全局最优解，它往往会陷入一个局部最优解。 此时重复运行算法是有可能得到全局最优解的。

KMeans聚类算法的Python实现

import numpy as np
import matplotlib.pyplot as plt
import random
from sklearn.datasets import make_blobs
np.random.seed(123)

# 从自带的机器学习库中获取数据，转移到变量中
X,y = make_blobs(centers=4,n_samples=1000) #四个聚类中心，1000个样本点
print(f'Shape of dataset:{X.shape}')# 打印数据集的大小
fig = plt.figure(figsize=(8,6))#准备绘制簇图像
plt.scatter(X[:,0],X[:,1],c = y)#X[:,0]代表取所有行中的第0个数据，即第0列数据
#👆数据集X的维度是(1000,2)的。
plt.title("Dataset with 4 clusters")#手动选择聚类中心，此处选择为4
#👆通过肘部法则可以选择聚类中心
plt.xlabel("First feature")
plt.ylabel("Second feature")
plt.show()
#👆展示初始数据集

#👇KMeans聚类算法：
class KMeans():
    def __init__(self,n_clusters = 4):
        self.k = n_clusters #初始化K为聚类中心个数

    def fit(self,data):#训练KMeans聚类算法模型
        """
        取数据集当中的一小部分用来训练K-Means聚类算法模型
        """
        n_samples,_ = data.shape #样本量为数据集的大小。
        #👇初始化聚类中心
        self.centers = np.array(random.sample(list(data),self.k)) #随机初始化聚类中心，个数为4
        self.initial_centers = np.copy(self.centers) #随机初始化
        #继续追踪样本点到聚类中心的欧氏距离是否改变，如果不再改变，停止迭代，分类完成
        #停止迭代的条件是，每一个样本点被分配到的聚类中心不再改变，重点在于每一个样本点
        old_assigns = None
        n_iters = 0 #记录迭代次数

        while True: #永真循环，因为结束迭代的条件是聚类中心位置和样本点的聚类划分不再改变。
            new_assigns = [self.classify(datapoint) for datapoint in data]
            #👆对于本例，有1000个数据，因为有1000个样本点
            #👆为所有样本点重新划分新的聚类中心。
            if new_assigns == old_assigns: #如果划分没有改变，那么就代表聚类中心的位置没有改变
            #如果这两条都满足，那么就说明划分完成，实际上，只要一条满足，就代表划分完成。
                print(f"Training finished after {n_iters} iterations!")
                return

            old_assigns = new_assigns
            n_iters += 1

            #根据欧氏距离重新计算聚类中心
            for id_ in range(self.k): #重新部署聚类中心的位置。
                points_idx = np.where(np.array(new_assigns) == id_)
                datapoints = data[points_idx]
                self.centers[id_] = datapoints.mean(axis = 0)
    def l2_distance(self,datapoint):#计算欧氏距离
        dists = np.sqrt(np.sum((self.centers - datapoint)**2,axis=1))
        return dists

    def classify(self,datapoint):#为样本点分配它们的聚类中心
        """
        Given a datapoint, compute the cluster closest to the datapoint.
        Return the cluster ID of that cluster.
        """
        dists = self.l2_distance(datapoint)
        return np.argmin(dists)#为许许多多的样本点重新分配聚类中心

    def plot_clusters(self,data):
        plt.figure(figsize=(12,10))
        plt.title("Initial centers in black,final centers in red")
        plt.scatter(data[:,0],data[:,1],marker = '.',c=y)
        plt.scatter(self.centers[:,0],self.centers[:,1],c='r')
        plt.scatter(self.initial_centers[:,0],self.initial_centers[:,1],c='k')
        plt.show()

if __name__ == '__main__':
    kmeans = KMeans(n_clusters = 4)
    kmeans.fit(X)
    kmeans.plot_clusters(X)

总结

总的来说，KMeans聚类算法是一个相当入门的用于分类的无监督学习算法，本文使用Python实现，更是简化了KMeans聚类算法的难度（Python算是描述性语言）。本文使用了Python自带的机器学习库sklearn，使用的样本也是来自sklearn库中的样本。