機器學習-Kmeans

前言

K-means是一種經典的無監督學習演演算法，用於對資料進行聚類。K-means演演算法將資料集視為具有n個特徵的n維空間，並嘗試通過最小化簇內平方誤差的總和來將資料點劃分為簇。本文將介紹K-means演演算法的原理、實現和應用。

定義

• K-means是一種無監督學習演演算法，
• 用於對資料進行聚類。該演演算法將資料集分為K個簇，每個簇包含最接近其質心的資料點。K-means演演算法將資料集視為具有n個特徵的n維空間，並嘗試通過最小化簇內平方誤差的總和來將資料點劃分為簇。
• 它是一種迭代演演算法，通過將每個資料點分配到最近的質心並計算新的質心來迭代地改進簇的質量，直到質心不再變化或達到最大迭代次數為止。

實現流程（k-means演演算法原理）

K-means演演算法是一種迭代演演算法，其基本思想是通過將每個資料點分配到最近的質心，並計算新的質心來迭代地改進簇的質量，直到質心不再變化或達到最大迭代次數為止。具體步驟如下：

1. 隨機選擇K個點作為初始質心；
2. 計算每個資料點與K個質心的距離；
3. 將資料點劃分到距離最近的質心所在的簇；
4. 對於每個簇，重新計算該簇內所有資料點的均值，將該均值作為新的質心；
5. 如果質心沒有變化，則停止迭代。

K-means演演算法的核心是將資料點分配到最近的質心所在的簇，這是通過計算每個資料點與K個質心的距離來實現的。一般而言，距離可以使用歐氏距離、曼哈頓距離等來計算。而每個簇的質心則是該簇內所有資料點的均值，用於表示該簇的中心位置。

K值的選擇

在K-means演演算法中，簇的數量k是需要事先指定的。選擇合適的簇的數量非常重要。

1. 手肘法：在不同的k值下執行K-means演演算法，計算每個簇的誤差平方和（SSE），並將其繪製成折線圖。通常會發現，隨著k值的增加，SSE會逐漸減小。但是，當k值增加到某個值時，SSE的下降速度會變得更加緩慢，形成一個類似手肘的拐點。該拐點所對應的k值就是比較合適的簇的數量。
2. 輪廓係數法：輪廓係數是一種用於評估聚類結果質量的指標，其取值範圍在[-1, 1]之間。對於每個資料點，輪廓係數是其與同簇其他資料點距離的平均值和與最近的不同簇的所有資料點的距離的平均值之差除以兩者中的較大值。聚類結果的整體輪廓係數是所有資料點的輪廓係數的平均值。較高的輪廓係數表示聚類效果較好。可以在不同的k值下執行K-means演演算法，計算聚類結果的整體輪廓係數，選擇輪廓係數最大的k值。
3. 經驗法則：在實際應用中，可以根據資料的特點、應用場景等因素，採用經驗法則來選擇k值。例如，對於影象分割等應用，通常選擇k值為2，對於客戶分類等應用，通常選擇k值為3或4。

需要注意的是，K-means演演算法可能陷入區域性最優解，因此，選擇k值需要多次執行演演算法，比較不同的聚類結果。

建立資料

• 該程式碼生成了一個包含1000個資料點的亂資料集，其中有4個簇，每個簇的中心點分別位於(0,0)、(3,3)、(0,3)和(3,0)。每個簇的資料點服從正態分佈。最後，用散點圖視覺化了資料集。可以根據需要調整資料集的大小、簇的數量、中心點的位置等引數。

import numpy as np
import matplotlib.pyplot as plt

# 建立資料集
np.random.seed(0)
n_samples = 1000
centers = np.array([[0, 0], [3, 3], [0, 3], [3, 0]])
X = np.zeros((n_samples, 2))
for i in range(len(centers)):
    X[i * (n_samples // len(centers)): (i + 1) * (n_samples // len(centers)), :] = \
        centers[i] + np.random.randn(n_samples // len(centers), 2)

# 視覺化資料集
plt.scatter(X[:, 0], X[:, 1], s=10)
plt.show()

實現k-means

• 該程式碼接受一個資料矩陣X、簇的數量k和最大迭代次數max_iter作為輸入，返回每個資料點的簇標籤和最終的質心座標。在每次迭代中，先計算每個資料點與k個質心的距離，然後將資料點劃分到距離最近的質心所在的簇。接著，對於每個簇，重新計算該簇內所有資料點的均值，將該均值作為新的質心。最後，如果質心沒有變化，則停止迭代。

import numpy as np

def k_means(X, k, max_iter=100):
    # 隨機選擇k個點作為初始質心
    centroids = X[np.random.choice(len(X), k, replace=False)]

    for i in range(max_iter):
        # 計算每個資料點與k個質心的距離
        distances = np.linalg.norm(X[:, np.newaxis, :] - centroids, axis=-1)

        # 將資料點劃分到距離最近的質心所在的簇
        labels = np.argmin(distances, axis=1)

        # 對於每個簇，重新計算該簇內所有資料點的均值，將該均值作為新的質心
        new_centroids = np.array([X[labels == j].mean(axis=0) for j in range(k)])

        # 如果質心沒有變化，則停止迭代
        if np.allclose(new_centroids, centroids):
            break

        centroids = new_centroids

    return labels, centroids
if __name__ == '__main__':
    
    labels, centroids = k_means(X=X, k=4)
    
    plt.scatter(X[labels==0, 0], X[labels==0, 1], color='r')
    plt.scatter(X[labels==1, 0], X[labels==1, 1], color='g')
    plt.scatter(X[labels==2, 0], X[labels==2, 1], color='b')
    plt.scatter(X[labels==3, 0], X[labels==3, 1])

    plt.show()

優化後程式碼

• 在此優化後的程式碼中，我們使用了兩個新函數
• plot_data函數用於繪製劃分後的資料集
• plot_centers函數用於繪製中心點
• 在主函數中，我們先呼叫k_means函數得到簇標籤和中心點，然後呼叫plot_data函數繪製劃分後的資料集，最後呼叫plot_centers函數繪製中心點。這樣的程式碼結構使得程式碼更易讀，更易於偵錯和維護。

import numpy as np
import matplotlib.pyplot as plt


# 建立資料集
np.random.seed(0)
n_samples = 1000
centers = np.array([[0, 0], [3, 3], [0, 3], [3, 0]])
X = np.zeros((n_samples, 2))
for i in range(len(centers)):
    X[i * (n_samples // len(centers)): (i + 1) * (n_samples // len(centers)), :] = \
        centers[i] + np.random.randn(n_samples // len(centers), 2)

# 視覺化資料集
def plot_data(X, labels):
    plt.scatter(X[labels==0, 0], X[labels==0, 1], color='r')
    plt.scatter(X[labels==1, 0], X[labels==1, 1], color='g')
    plt.scatter(X[labels==2, 0], X[labels==2, 1], color='b')
    plt.scatter(X[labels==3, 0], X[labels==3, 1], color='m')
    plt.show()

def plot_centers(centroids):
    plt.scatter(centroids[:, 0], centroids[:, 1], s=200, marker='*', color='k')
    plt.show()

def k_means(X, k, max_iter=100):
    # 隨機選擇k個點作為初始質心
    centroids = X[np.random.choice(len(X), k, replace=False)]

    for i in range(max_iter):
        # 計算每個資料點與k個質心的距離
        distances = np.linalg.norm(X[:, np.newaxis, :] - centroids, axis=-1)

        # 將資料點劃分到距離最近的質心所在的簇
        labels = np.argmin(distances, axis=1)

        # 對於每個簇，重新計算該簇內所有資料點的均值，將該均值作為新的質心
        new_centroids = np.array([X[labels == j].mean(axis=0) for j in range(k)])

        # 如果質心沒有變化，則停止迭代
        if np.allclose(new_centroids, centroids):
            break

        centroids = new_centroids

    return labels, centroids

if __name__ == '__main__':
    labels, centroids = k_means(X=X, k=4)
    plot_data(X, labels)
    plot_centers(centroids)