物以類聚
經典的無監督學習演算法 ——K-Means聚類演算法

1. K-Means 定義

K-means聚類演算法首先是隨機選取K個物件作為初始的聚類中心，然后計算每個樣本與各個聚類中心之間的距離，把每個樣本分配給距離它最近的聚類中心，

聚類中心以及分配給它們的物件就代表一個聚類，每分配一次樣本，聚類的聚類中心會根據聚類中現有的物件被重新計算，這個程序將不斷重復直到滿足某個終止條件，

終止條件可以是沒有（或最小數目）樣本被重新分配給不同的聚類，沒有（或最小數目）聚類中心再發生變化，誤差平方和區域最小，

2. K-Means 步驟

理論：
1 . 隨機生成K個聚類中心，
2 .計算每個樣本與每一個聚類中心的距離(歐式距離)，離哪個聚類中心近，就劃分到哪個聚類中心所屬的集合當中，
3 .重新計算每個集合的聚類中心，
4 .重復2，3步直到收斂，
5 .回傳所有的聚類標簽，

圖解K-Means：

資料集采用的是make_blobs，

① 設定K=2，第一次隨機劃分了兩個聚類，可以看出是非常不平衡的！還沒有收斂~

② 計算每個樣本與這兩個聚類中心的距離(歐式距離)，離哪個聚類中心近，就劃分到哪個聚類中心所屬的集合當中，

• 如果這個樣本點到兩個聚類中的距離都是相等的話，就會隨機分配到其中一類，
• 那么當這次聚類結束后，兩個聚類會重新進行聚類中心點的計算，聚類中心就會改變，
• 那么下一次進行樣本點和聚類中心點聚類計算的時候，這個樣本點該劃分到哪一類就會是哪一類，
• 也就是說這個隨機是不影響最終的聚類結果的，

可以換個參考系想想，這兩個聚類中心點不斷在找自己的樣本，就算中間程序中找錯了，也不會影響最終的結果，他該有哪些樣本點還是哪些樣本點

③ 當劃分完這一次所有樣本點到各個聚類中心之后（即哪個樣本點離哪個聚類中心近，就分到哪個聚類中心的集合），重新計算聚類中心的位置，即是黑色點的位置，

下圖，紅色點是沒有計算的，就是上一次的聚類中心點，所以紫色的樣本點都是距離右邊的紅點近的，黃色的樣本點都是距離左邊的紅點近的，黑色點是重新計算后的

然后就通過這個重新計算后的黑色點，繼續計算各個樣本點到這個黑色點的距離，離左邊的聚類中心近的就是黃色區域，離右邊聚類中心點近的就是屬于右邊的一類，

可以看一下這一次聚類的程序： 一共迭代了15次才收斂

3. K-Means 和 KNN 對比

下面兩張圖來自B站Up五分鐘機器學習

4. 小練習

4.1 第一題

Sklearn中的make_circles方法生成資料，用K-Means聚類并可視化，

"""
Sklearn中的make_circles方法生成資料，用K-Means聚類并可視化，
"""
from sklearn.cluster import KMeans
from sklearn.datasets import make_circles
import matplotlib.pyplot as plt
from ex1.clustering_performance import clusteringMetrics  # 匯入的老師寫的庫

fig = plt.figure(1, figsize=(10, 5))
X1, y1 = make_circles(n_samples=400, factor=0.5, noise=0.1)
plt.subplot(121)
plt.title('original')
plt.scatter(X1[:, 0], X1[:, 1], c=y1)
plt.subplot(122)
plt.title('K-means')
kms = KMeans(n_clusters=2, max_iter=400)  # n_cluster聚類中心數 max_iter迭代次數
y1_sample = kms.fit_predict(X1, y1)  # 計算并預測樣本類別
centroids = kms.cluster_centers_
plt.scatter(X1[:, 0], X1[:, 1], c=y1_sample)
plt.scatter(centroids[:, 0], centroids[:, 1], s=30, marker='*', c='b')

print(clusteringMetrics(y1, y1_sample))
plt.show()

4.2 第二題

Sklearn中的make_moons方法生成資料，用K-Means聚類并可視化，

"""
Sklearn中的make_moons方法生成資料，用K-Means聚類并可視化，
"""
import numpy as np
import matplotlib.pyplot as plt
import sklearn.datasets as datasets


def create_data():
    X, y = datasets.make_moons(n_samples=400, noise=0.1)
    return X, y

def init_centers(data, k):
    m, n = data.shape
    # m 樣本個數，n特征個數
    center_ids = np.random.choice(m, k)
    centers = data[center_ids]
    return centers

def cal_dist(ptA, ptB):
    return np.linalg.norm(ptA - ptB)

def kmeans_process(data, k):
    centers = init_centers(data, k)
    m, n = data.shape
    keep_changing = True
    pred_y = np.zeros((m,))
    iteration = 0
    while keep_changing:
        keep_changing = False
        # 計算剩余樣本所屬類別
        for i in range(m):
            min_distance = np.inf
            for center in range(k):
                distance = cal_dist(data[i, :], centers[center, :])
                if distance < min_distance:  # 判斷離哪個更近
                    min_distance = distance
                    idx = center  # 類別換下
            if pred_y[i] != idx:  # 判斷是否發生了改變
                keep_changing = True
            pred_y[i] = idx
        # 更新類別中心點坐標
        for center in range(k):
            cluster_data = data[pred_y == center]
            centers[center, :] = np.mean(cluster_data, axis=0)  # 求相同類別資料點的質心點
        print(centers)
        plt.clf()
        plt.title(f'iteration: {iteration}')
        plt.scatter(X[:, 0], X[:, 1], s=30, c=pred_y)
        plt.scatter(centers[:, 0], centers[:, 1], s=100, c='k')
        plt.pause(1)
        iteration += 1
    return centers, pred_y

if __name__ == '__main__':
    X, y = create_data()
    plt.ion()
    centers, pred_y = kmeans_process(data=X, k=2)
    plt.ioff()
    plt.show()

4.3 第三題

給定的影像，對其像素進行聚類并可視化

from scipy.cluster.vq import *
from pylab import *
from PIL import Image


def clusterpixels(infile, k, steps):
    im = array(Image.open(infile))
    dx = im.shape[0] / steps
    dy = im.shape[1] / steps
    features = []

    for x in range(steps):  # RGB三色通道
        for y in range(steps):
            R = mean(im[int(x * dx):int((x + 1) * dx), int(y * dy):int((y + 1) * dy), 0])
            G = mean(im[int(x * dx):int((x + 1) * dx), int(y * dy):int((y + 1) * dy), 1])
            B = mean(im[int(x * dx):int((x + 1) * dx), int(y * dy):int((y + 1) * dy), 2])
            features.append([R, G, B])
    features = array(features, 'f')  # make into array
    # 聚類， k是聚類數目
    centroids, variance = kmeans(features, k)
    code, distance = vq(features, centroids)
    codeim = code.reshape(steps, steps)
    codeim = np.array(Image.fromarray(codeim).resize((im.shape[1], im.shape[0])))
    return codeim


# k = 5
infile_Stones = 'stones.jpg'
im_Stones = array(Image.open(infile_Stones))
steps = (50, 100)  # image is divided in steps*steps region

# 顯示原圖
figure()
subplot(231)
title('original')
axis('off')
imshow(im_Stones)

for k in range(2, 7):
    codeim = clusterpixels(infile_Stones, k, steps[-1])
    subplot(2, 3, k)
    title('K=' + str(k))
    axis('off')
    imshow(codeim)

show()

最后

小生凡一，期待你的關注，