关于聚类:Kmeans算法解析及代码复现

K-means 算法是最罕用的聚类算法之一，本文将对该算法进行解析和 numpy 复现代码。

K-means 解析

定义

K-means 基于的一个假如是同类样本点会在特色空间造成簇。在 K -means 算法中，会给定样本集 X 的 n 个数据点，簇的个数 k。每个簇都有一个类别核心 c。K-means 的优化指标如下式，

式子的意思是让所有数据点离它们所属的类别核心（最近的核心）的欧式间隔之和最小。

求解步骤

求解这个方程个别用上面步骤求解：

1. 随机选取 k 个类别核心 C = {c1, c2,···, ck}。
2. 把每个数据点归到其最近的类别核心的簇，即给每个点打上假标签。失去 k 个簇集。
3. 通过步骤 2 失去的 k 个簇集，从新计算类别核心，计算形式为，
   
4. 反复步骤 2 和步骤 3 直到类别核心不再更新为止。

能够看出 K -means 的求解非常简略，其关键在于类别核心的初始化。最简略的初始化是随机选取 k 个点当作类别核心，但可能会遇到下图状况。下图四个簇对应四个类，当初始点（星）如下图所示时，类别核心无奈收敛到正确的地位上。

k-means++ 算法 [1] 就是为解决这个问题所提出的。
K-means++ 选取初始类别核心步骤为：

1. 随机选取第一个类别核心。
2. 计算所有样本点与其最近的类别核心的间隔 D(x)，以下式概率
   
   从样本集 X 中选取下一个类别核心。
3. 反复步骤 2，直到选取到 k 个类别核心。

关键点在步骤 2，其实质是当一个点属于已选取的类别核心的簇的概率越大，它被选取的概率越小。其目标是使得算法尽可能不在同一簇里不选取两个类别核心。不过算法以概率的模式选取，也无奈保障不呈现上图的状况。因而，个别 K -means 算法会运行屡次，选取指标函数最小的类别核心。

算法代码

初始化形心

应用的是 K -means++ 的形式：

def ini_centers(self,x):
    cs = np.array([x[np.random.randint(0, len(x), size = 1).item()]])
    for j in range(self.class_num - 1):
        for i, c in enumerate(cs):
            d = np.sqrt(np.sum((x - c) ** 2, 1).reshape(-1, 1))
            if i == 0:
                dist = d
            else:
                dist = np.concatenate((dist, d), 1)
                # n, class_num
    dist = dist.min(1)
    dist = dist**2/sum(dist**2)
    index = np.random.choice(np.arange(len(x)), p=dist.ravel())
    new_c = x[index]
    cs = np.concatenate((cs,[new_c]), 0)
    return cs

打标签和从新计算类别核心

cnt = 0
flag = True
while flag and cnt < self.max_iter:
    # predict
    label, score = self.predict(x,cs)
    # update
    new_cs = np.array([x[label==i].mean(0) for i in range(self.class_num)])
        if (cs == new_cs).all(): flag = False
    cs = new_cs
    cnt+=1

预测函数

def predict(self,x,cs):
    for i,c in enumerate(cs):
        d = np.sqrt(np.sum((x - c)**2,1).reshape(-1,1))
        if i == 0:
            dist = d
        else:
            dist = np.concatenate((dist,d),1)
    label = dist.argmin(1)
    score = dist.min(1).sum()
    return label, score

屡次计算

def fit(self,x):
    sc = float("inf")
    for t in range(self.n_init):
    cs = self.ini_centers(x)
        # initial
    cnt = 0
    flag = True
    while flag and cnt < self.max_iter:
        # predict
        label, score = self.predict(x,cs)
        # update
        new_cs = np.array([x[label==i].mean(0) for i in range(self.class_num)])
            if (cs == new_cs).all(): flag = False
        cs = new_cs
        cnt+=1
    if score < sc:
        sc = score
        self.cluster_centers_ = cs
    return self.cluster_centers_

总体函数

class my_Kmeans():
    def __init__(self, class_num, max_iter=300, n_init=10):
        self.class_num = class_num
        self.cluster_centers_ = None
        self.max_iter = max_iter
        self.n_init = n_init
    def ini_centers(self,x):
        cs = np.array([x[np.random.randint(0, len(x), size = 1).item()]])
        for j in range(self.class_num - 1):
            for i, c in enumerate(cs):
                d = np.sqrt(np.sum((x - c) ** 2, 1).reshape(-1, 1))
                if i == 0:
                    dist = d
                else:
                    dist = np.concatenate((dist, d), 1)
                    # n, class_num
        dist = dist.min(1)
        dist = dist**2/sum(dist**2)
        index = np.random.choice(np.arange(len(x)), p=dist.ravel())
        new_c = x[index]
        cs = np.concatenate((cs,[new_c]), 0)
        return cs
 
    def fit(self,x):
        sc = float("inf")
        for t in range(self.n_init):
        cs = self.ini_centers(x)
            # initial
        cnt = 0
        flag = True
        while flag and cnt < self.max_iter:
            # predict
            label, score = self.predict(x,cs)
            # update
            new_cs = np.array([x[label==i].mean(0) for i in range(self.class_num)])
                if (cs == new_cs).all(): flag = False
            cs = new_cs
            cnt+=1
        if score < sc:
            sc = score
            self.cluster_centers_ = cs
        return self.cluster_centers_
 
    def predict(self,x,cs):
        for i,c in enumerate(cs):
            d = np.sqrt(np.sum((x - c)**2,1).reshape(-1,1))
            if i == 0:
                dist = d
            else:
                dist = np.concatenate((dist,d),1)
        label = dist.argmin(1)
        score = dist.min(1).sum()
        return label, score
 
    def fit_predict(self,x):
        self.fit(x)
        label, score = self.predict(x,self.cluster_centers_)
        return label

上述代码经试验基本功能齐备，然而成果跟效率要差于 sklearn 库。有能够改良的中央欢送跟我交换。

[1] Arthur, David and Sergei Vassilvitskii.“k-means++: the advantages of careful seeding.”SODA ’07 (2007).