什么是K-means算法?

在聚類問題中，我們會給定一組未加標簽的數(shù)據(jù)集，同時希望有一個算法，能夠自動的將這些數(shù)據(jù)分成有緊密關系的子集或簇。
K均值（K-means）算法是現(xiàn)在最熱門最為廣泛運用的聚類算法，它是無監(jiān)督學習的聚類算法。

K-means的聚類步驟

K-means偽代碼（吳恩達老師）.png

① 自定義或隨機初始化 K個聚簇中心；

② 對每個樣本進行簇分配。根據(jù)距離哪個聚簇中心最近依次分配到K個不同的聚簇中（使用歐幾里得算法）；

③ 移動聚類中心。對于每個聚類中心，求出各個簇中所有點的均值。

④ 內循環(huán) ②和③，使樣本聚類更均值，通常為50<X<1000次（請自行調節(jié)）。

⑤ 步驟圖如下三幅：

無標簽的數(shù)據(jù)集.png

初始化聚類中心并進行簇分配圖（X為聚簇中心）.png

經(jīng)過多次內循環(huán)后，移動聚類中心和標簽聚類的結果圖.png

Python代碼示例

例如有一道這樣的題：

一道來自松哥的作業(yè)題.png

K-means的py代碼如下：

# -*- coding: utf-8 -*-

import numpy as np

K = 2


def dist(x, y):
    """
    歐幾里得距離計算
    """
    return np.sqrt(np.sum((x - y) ** 2))


if __name__ == '__main__':
    arrList = [[1, 1], [2, 1], [1, 2], [2, 2],
               [4, 3], [5, 3], [4, 4], [5, 4]]

    arrMap = {}  # 用來記錄樣本屬于哪個簇

    # TODO 隨機初始化K個聚類中心，如果提供了初始中心也可以
    centerList = [[1, 1], [1, 2]]  # 初始中心

    for _ in range(10):  # 內循環(huán)

        # TODO 進行樣本的簇分配
        for i in range(len(arrList)):
            ci = None  # 離聚簇中心的最短距離
            cc = None  # 簇中心下標（標識屬于哪個簇）
            for y in range(len(centerList)):
                tmp = dist(np.array(arrList[i]), np.array(centerList[y]))
                if ci is None:
                    ci = tmp
                    cc = y
                else:
                    ci, cc = (tmp, y) if tmp < ci else (ci, cc)

            arrMap[i] = cc

        # TODO 重新計算聚類中心位置（移動聚類中心）
        count = np.zeros(len(centerList))  # 統(tǒng)計樣本數(shù)
        zeros = np.zeros((len(centerList), 2))  # 每個簇的和
        for i in range(len(arrList)):
            y = arrMap[i]
            count[y] += 1
            zeros[y] = zeros[y] + arrList[i]

        for i in range(len(zeros)):
            # 每個簇的均值，也是聚簇中心的新位置
            centerList[i] = zeros[i] / count[i]

        # print(count)
        # print(zeros)
        print(centerList)
        print(arrMap)
        print()

    pass

友情鏈接：松哥的幽默博客