K-Means算法理论及Python实现

叁歲伎倆 2022-03-11 08:35 156阅读 0赞

## 简述 ##

K-means Algorithm(s)

*  Assumes Euclidean space/distance 假设是在欧式空间下的。因为means本身是需要在欧式空间下才可以计算。但K-means有很多的推广版本，将欧式空间中所提到的Centroid转成Clustroid，是一种比较常见的推广方式。
 *  算法先取k个类： Initialization 的时候需要避免ill-initialization 这里考虑到病态的初始化。最为经典的是使用 Rival penalized competitive learning1

**总之**，通过一定的方式，可以实现初始化的K个类中心的选取。

## 算法流程 ##

*  For each point, place it in the cluster whose current centroid it is nearest.对于每个点，将其放在那个类中心离它最近的那个类中。
 *  After all points are assigned, update the locations of centroids of the K clusters. 每个点都被分配完之后，更新每个类的中心位置。
 *  Reassign all points to their closet centroid. 再分配每个点（方法类似）直到整个分配没什么变化。（直到收敛）

## 收敛性证明 ##

> 这里我只给出不是很严谨的证明~ 至于详细的可以看60年前的那篇论文。

我们认为K-means一定会收敛。  
下面使用反证法：  
**假设该算法不收敛。**

那么根据假设就存在有这样的一个点。在添加它之后，即类中心发生移动后，就该删除掉它。  
而这是不合理的。添加上该点之后，该类中心会向该点的发生移动。即距离比之前更近了。而根据算法，我们知道这样的点是不会被抛弃的。所以，这样的点不存在。即该算法会收敛。

**证明不是很严谨，但是却可以拿来做对于算法收敛的直观认知~**  
欢迎大家在评论区补充~

## Python实现 ##

*  注意，这里采用的是完全随机初始化，这样的效果不是很好。因为可能会存在有病态的初始化结果。

def k_means(X, k=3):
        index_list = np.arange(len(X))
        np.random.shuffle(index_list)
        centroids_index = index_list[:k]
        centroids = X[centroids_index]
        y = np.arange(len(X))
        while True:
            y_new = np.arange(len(X))
            for i, xi in enumerate(X):
                y_new[i] = np.argmin([np.linalg.norm(xi - cj) for cj in centroids])
            if sum(y != y_new) == 0:
                break
            for j in range(k):
                centroids[j] = np.mean(X[np.where(y_new == j)], axis=0)
            y = y_new.copy()
        return y

*  直接用PCA截取部分特征，主要是为了画图

from sklearn import datasets
    iris = datasets.load_iris()
    from sklearn.decomposition import PCA
    X_reduced = PCA(n_components=2).fit_transform(iris.data)
    import matplotlib.pyplot as plt
    plt.scatter(X_reduced[:, 0], X_reduced[:, 1], c=y, cmap=plt.cm.Set1)

**原图：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70]

**K-means:**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70 1]

*  直接选用前两个特征

plt.scatter(iris.data[:, 0], iris.data[:, 1], c=y, cmap=plt.cm.Set1)
    y_test_2 = k_means(iris.data)
    plt.scatter(iris.data[:, 0], iris.data[:, 1], c=y_test, cmap=plt.cm.Set1)

**原图：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70 2]

**K-means：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70 3]

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

1.  [https://ieeexplore.ieee.org/abstract/document/238318][https_ieeexplore.ieee.org_abstract_document_238318]) ↩︎

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70]: /images/20220311/a38c79996b3b4225a422d27d815d10fc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70 1]: /images/20220311/f938548e15574345aa9387e7279d8dfc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70 2]: /images/20220311/4d68d213b0b94242bfb13b903641860d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70 3]: /images/20220311/e1a9ff0e29174c93b299abf67bef757d.png
[https_ieeexplore.ieee.org_abstract_document_238318]: https://ieeexplore.ieee.org/abstract/document/238318