非監督學習演算法--K均值聚類

01-28

本文介紹最常見的非監督學習演算法「K均值(K-means)」，思路和模擬主要參考Ng的課程「Machine Learning」以及課程作業的Matlab的實現。

猛戳下載本文Matlab實現，其中ex7.m包含了k-means的代碼，ex7_pca.m包含了PCA的代碼。

以下是正文。

K-means的意義和使用場景：

在無任何先驗分類知識的情況下，自動發現數據集的分類。例如：

??下面簡述演算法步驟、模擬以及演算法中的問題 ??

1.1 演算法步驟

假設希望將訓練數據集 $x^{(i)} (i = 1, 2, 3,..., m)$ 分為K類；
在 $x^{(i)} (i = 1, 2, 3,..., m)$ 中，隨機選擇K個作為初始分類的圖心(centroids) $mu _{1}, mu _{2}, mu _{3},..., mu _{K}$ ；
遍歷 $x^{(i)}$ ，計算出和每個 $x$ 距離最近的圖心 $mu ^{(i)}$ ，記錄當前 $x$ 屬於第 $i$ 類；
遍歷K種分類，分別計算上一步中，劃歸其中的所有 $x$ 點的中心點，將該點設置為本分類中心的圖心；
迭代上兩步，直到圖心位置收斂。

1.2 Matlab模擬：K-means過程

(我做了個gif動圖，可能需要戳一下它才會動起來)

1.3 隨機初始化 Random Initialisation

由於初始的圖心是隨機選擇的，K-means可能陷入局部最優而導致最終的圖心無法收斂到合適的位置。可以使用隨機初始化來解決這個問題：

多次運行K-means演算法，計算 $c^{(1)},..., c^{(m)}, mu _{1},..., mu _{k}$ ；
計算Cost Function $J = (c^{(1)},..., c^{(m)}, mu _{1},..., mu _{k})$ ，函數代表了聚類的失真程度；
選擇J最小的那一組初始化以及最終的計算結果。