均值算法是一種典型的無監(jiān)督學(xué)習(xí)算法斥赋，用來對數(shù)據(jù)進行分類。
聚類問題 Clustering
針對監(jiān)督式學(xué)習(xí)，輸入數(shù)據(jù)為 (x, y) 惨驶，目標(biāo)是找出分類邊界，即對新的數(shù)據(jù)進行分類敛助。而無監(jiān)督式學(xué)習(xí)只給出一組數(shù)據(jù)集 ${x_1, x_2, ... , x_m}$ 粗卜，目標(biāo)是去找出這組數(shù)據(jù)的模式特征，比如哪些數(shù)據(jù)是一種類型的纳击，哪些數(shù)據(jù)是另外一種類型的续扔。典型的無監(jiān)督式學(xué)習(xí)包括市場細分，通過分析用戶數(shù)據(jù)焕数，來把一個產(chǎn)品的市場進行細分测砂，找出細分人群。另外一個是社交網(wǎng)絡(luò)分析百匆，分析社交網(wǎng)絡(luò)中的參與人員的不同特點砌些，根據(jù)特點區(qū)分出不同群體。這些都是無監(jiān)督式學(xué)習(xí)里的聚類 (Clustering) 問題加匈。
K 均值算法
K 均值算法算法就是一種解決聚類問題的算法存璃，它包含兩個步驟：
- 給聚類中心分配點：計算所有的訓(xùn)練樣例，把他分配到距離某個聚類中心最短的的那聚類里雕拼。
- 移動聚類中心：新的聚類中心移動到這個聚類所有的點的平均值處纵东。
一直重復(fù)做上面的動作，直到聚類中心不再移動為止啥寇。這個時候我們就探索出了數(shù)據(jù)集的結(jié)構(gòu)了偎球。可以通過一個動畫來直觀地看一下 K 均值算法聚類的過程：
用數(shù)學(xué)的方法來描述 K 均值算法如下：
算法有兩個輸入信息辑甜。一是 K 表示選取的聚類個數(shù)衰絮；二是訓(xùn)練數(shù)據(jù)集 ${x^{(1)}, x^{(2)}, ... , x^{(m)}}$。
- 隨機選擇 K 個聚類中心 $u_1, u_2, ... , u_k$磷醋。
- 從 1 - m 遍歷所有的數(shù)據(jù)集猫牡，計算 $x^{(i)}$ 分別到 $u_1, u_2, ... , u_k$ 的距離，記錄距離最短的聚類中心點邓线。然后把 $x^{(i)}$ 這個點分配給這個聚類淌友。令 $c^{(i)} = j$ 其中 $u_j$ 就是與 $x^{(i)}$ 距離最短的聚類中心點。計算距離時骇陈，一般使用 $| x^{(i)} - u_j |^2$ 來計算震庭。
- 從 1 - K 遍歷所有的聚類中心，移動聚類中心的新位置到這個聚類的均值處你雌。即 $u_j = \frac{1}{c} \left( \sum_{d=1}^c \right)$ 器联，其中 c 表示分配給這個聚類的訓(xùn)練樣例點的個數(shù)。如果特殊情況下，沒有點分配給這個聚類中心主籍，那么說明這個聚類中心就不應(yīng)該存在习贫，直接刪除掉這個聚類中心，最后聚類的個數(shù)變成 K - 1 個千元。
- 重復(fù)步驟 2 苫昌，直到聚類中心不再移動為止。
K 均值算法成本函數(shù)
其中幸海， $c^{(i)}$ 是訓(xùn)練樣例 $x^{(i)}$ 分配的聚類序號祟身；$u_{c^{(i)}}$ 是 $x^{(i)}$ 所屬的聚類的中心點。K 均值算法的成本函數(shù)的物理意義物独，就是訓(xùn)練樣例到其所屬的聚類中心點的距離的平均值袜硫。
隨機初始化聚類中心點
假設(shè) K 是聚類的個數(shù)，m 是訓(xùn)練樣本的個數(shù)挡篓，那么必定有 $K < m$婉陷。在隨機初始化時，隨機從 m 個訓(xùn)練數(shù)據(jù)集里選擇 K 個樣本來作為聚類中心點官研。這是正式推薦的隨機初始化聚類中心的做法秽澳。
在實際解決問題時，最終的聚類結(jié)果會和隨機初始化的聚類中心點有關(guān)戏羽。即不同的隨機初始化的聚類中心點可能得到不同的最終聚類結(jié)果担神。因為成本函數(shù)可能會收斂在一個局部最優(yōu)解，而不是全局最優(yōu)解上始花。一個解決方法是多做幾次隨機初始化的動作妄讯，然后訓(xùn)練出不同的取類中心點以及聚類節(jié)點分配方案。然后用這些值算出成本函數(shù)酷宵，最終選擇那個成本最小的亥贸。
比如，假設(shè)我們做 100 次運算忧吟，步驟如下：
- 隨機選擇 K 個聚類中心點
- 運行 K 均值算法砌函，算出 $c^{(1)}, c^{(2)}, ... , c^{(m)}$ 和 $u_1, u_2, ... , u_k$
- 使用 $c^{(1)}, c^{(2)}, ... , c^{(m)}$ 和 $u_1, u_2, ... , u_k$ 算出最終的成本值
- 記錄最小的成本值，然后跳回步驟 1溜族，直到達到最大運算次數(shù)
這樣我們可以適當(dāng)加大運算次數(shù)，從而求出全局最優(yōu)解垦沉。
選擇聚類的個數(shù)
怎么樣選擇合適的聚類個數(shù)呢煌抒？實際上聚類個數(shù)和業(yè)務(wù)有緊密的關(guān)聯(lián)，比如我們要對 T-Shirt 大小進行聚類分析厕倍，我們是分成 3 個尺寸好呢還是分成 5 個尺寸好寡壮？這個更多的是個業(yè)務(wù)問題而非技術(shù)問題。3 個尺寸可以給生產(chǎn)和銷售帶來便利，但客戶體驗可能不好况既。5 個尺寸客戶體驗好了这溅，但可能會給生產(chǎn)和庫存造成不便。
從技術(shù)角度來講棒仍，也是有一些方法可以來做一些判斷的悲靴。我們可以把聚類個數(shù)作為橫坐標(biāo)，成本函數(shù)作為縱坐標(biāo)莫其，這樣把成本和聚類個數(shù)的數(shù)據(jù)畫出來癞尚。如上圖所示。大體的趨勢是隨著 K 值越來越大乱陡，成本越來越低浇揩。我們找出一個拐點，即在這個拐點之前成本下降比較快憨颠，在這個拐點之后胳徽，成本下降比較慢，那么很可能這個拐點所在的 K 值就是我們要尋求的最優(yōu)解爽彤。
當(dāng)然膜廊，這個技術(shù)方法并不總是有效，我們很可能會得到一個沒有拐點的曲線淫茵，這樣的話爪瓜，就必須和業(yè)務(wù)邏輯結(jié)合以便選擇合適的聚類個數(shù)。
