1. 聚類算法都是無監(jiān)督學習嗎?
什么是聚類算法空幻？聚類是一種機器學習技術，它涉及到數據點的分組容客。給定一組數據點秕铛，我們可以使用聚類算法將每個數據點劃分為一個特定的組。理論上缩挑，同一組中的數據點應該具有相似的屬性和/或特征但两，而不同組中的數據點應該具有高度不同的屬性和/或特征。聚類是一種無監(jiān)督學習的方法供置，是許多領域中常用的統(tǒng)計數據分析技術谨湘。
常用的算法包括K-MEANS、高斯混合模型（Gaussian Mixed Model士袄，GMM）悲关、自組織映射神經網絡（Self-Organizing Map，SOM）
2. k-means(k均值)算法
2.1 算法過程
K-均值是最普及的聚類算法娄柳，算法接受一個未標記的數據集寓辱，然后將數據聚類成不同的組。
K-均值是一個迭代算法赤拒，假設我們想要將數據聚類成 n 個組秫筏，其方法為:
- 首先選擇??個隨機的點，稱為聚類中心（cluster centroids）挎挖；
- 對于數據集中的每一個數據这敬，按照距離??個中心點的距離，將其與距離最近的中心點關聯(lián)起來蕉朵，與同一個中心點關聯(lián)的所有點聚成一類崔涂。
- 計算每一個組的平均值，將該組所關聯(lián)的中心點移動到平均值的位置始衅。
- 重復步驟冷蚂，直至中心點不再變化缭保。
用 來表示聚類中心，用??(1),??(2),...,??(??)來存儲與第??個實例數據最近的聚類中心的索引蝙茶，K-均值算法的偽代碼如下：
Repeat {
for i = 1 to m
c(i) := index (form 1 to K) of cluster centroid closest to x(i)
for k = 1 to K
μk := average (mean) of points assigned to cluster k
}
算法分為兩個步驟艺骂，第一個 for 循環(huán)是賦值步驟，即：對于每一個樣例??隆夯，計算其應該屬于的類钳恕。第二個 for 循環(huán)是聚類中心的移動，即：對于每一個類??蹄衷，重新計算該類的質心忧额。
K-均值算法也可以很便利地用于將數據分為許多不同組，即使在沒有非常明顯區(qū)分的組群的情況下也可以宦芦。下圖所示的數據集包含身高和體重兩項特征構成的宙址，利用 K-均值算法將數據分為三類轴脐，用于幫助確定將要生產的 T-恤衫的三種尺寸调卑。
2.2 損失函數
K-均值最小化問題，是要最小化所有的數據點與其所關聯(lián)的聚類中心點之間的距離之和大咱，因此 K-均值的代價函數（又稱畸變函數 Distortion function）為：
其中 代表與
最近的聚類中心點恬涧。 我們的的優(yōu)化目標便是找出使得代價函數最小的
和
。
2.3 k值的選擇
在運行 K-均值算法的之前碴巾，我們首先要隨機初始化所有的聚類中心點溯捆，下面介紹怎樣做：
- 我們應該選擇?? < ??，即聚類中心點的個數要小于所有訓練集實例的數量厦瓢。
- 隨機選擇??個訓練實例提揍，然后令??個聚類中心分別與這??個訓練實例相等K-均值的一個問題在于，它有可能會停留在一個局部最小值處煮仇，而這取決于初始化的情況劳跃。
為了解決這個問題，我們通常需要多次運行 K-均值算法浙垫，每一次都重新進行隨機初始化刨仑，最后再比較多次運行 K-均值的結果，選擇代價函數最小的結果夹姥。這種方法在??較小的時候（2--10）還是可行的杉武，但是如果??較大，這么做也可能不會有明顯地改善辙售。
沒有所謂最好的選擇聚類數的方法轻抱，通常是需要根據不同的問題，人工進行選擇的旦部。選擇的時候思考我們運用 K-均值算法聚類的動機是什么祈搜。有一個可能會談及的方法叫作“肘部法則”封拧。關 于“肘部法則”，我們所需要做的是改變??值夭问，也就是聚類類別數目的總數泽西。我們用一個聚類來運行 K 均值聚類方法。這就意味著缰趋，所有的數據都會分到一個聚類里捧杉，然后計算成本函數或者計算畸變函數??。??代表聚類數字秘血。
我們可能會得到一條類似于這樣的曲線味抖。像一個人的肘部。這就是“肘部法則”所做的灰粮，讓我們來看這樣一個圖仔涩，看起來就好像有一個很清楚的肘在那兒。你會發(fā)現這種模式粘舟，它的畸變值會迅速下降熔脂，從 1 到 2，從 2 到 3 之后柑肴，你會在 3 的時候達到一個肘點霞揉。在此之后，畸變值就下降的非常慢晰骑，看起來就像使用 3 個聚類來進行聚類是正確的适秩，這是因為那個點是曲線的肘點，畸變值下降得很快硕舆，?? = 3之后就下降得很慢秽荞，那么我們就選?? = 3。當你應用“肘部法則”的時候抚官，如果你得到了一個像上面這樣的圖扬跋，那么這將是一種用來選擇聚類個數的合理方法。
2.4 KNN與K-means區(qū)別耗式？
K最近鄰(k-Nearest Neighbor胁住，KNN)分類算法，是一個理論上比較成熟的方法刊咳，也是最簡單的機器學習算法之一彪见。
| KNN | K-Means |
|---|---|
| 1.KNN是分類算法 2.屬于監(jiān)督學習 3.訓練數據集是帶label的數據 |
1.K-Means是聚類算法 2.屬于非監(jiān)督學習 3.訓練數據集是無label的數據，是雜亂無章的娱挨，經過聚類后變得有序余指，先無序，后有序。 |
| 沒有明顯的前期訓練過程酵镜，屬于memory based learning | 有明顯的前期訓練過程 |
| K的含義：一個樣本x碉碉，對它進行分類，就從訓練數據集中淮韭，在x附近找離它最近的K個數據點垢粮，這K個數據點，類別c占的個數最多靠粪，就把x的label設為c蜡吧。 | K的含義：K是人工固定好的數字，假設數據集合可以分為K個蔟占键，那么就利用訓練數據來訓練出這K個分類昔善。 |
相似點
都包含這樣的過程，給定一個點畔乙，在數據集中找離它最近的點君仆。即二者都用到了NN(Nears Neighbor)算法思想。
2.5 K-Means優(yōu)缺點及改進
k-means：在大數據的條件下牲距，會耗費大量的時間和內存返咱。 優(yōu)化k-means的建議：
減少聚類的數目K。因為嗅虏，每個樣本都要跟類中心計算距離洛姑。
減少樣本的特征維度。比如說皮服，通過PCA等進行降維。
考察其他的聚類算法参咙，通過選取toy數據龄广，去測試不同聚類算法的性能。
hadoop集群蕴侧，K-means算法是很容易進行并行計算的择同。
-
算法可能找到局部最優(yōu)的聚類，而不是全局最優(yōu)的聚類净宵。使用改進的二分k-means算法敲才。
二分k-means算法：首先將整個數據集看成一個簇，然后進行一次k-means（k=2）算法將該簇一分為二择葡，并計算每個簇的誤差平方和紧武，選擇平方和最大的簇迭代上述過程再次一分為二，直至簇數達到用戶指定的k為止敏储，此時可以達到的全局最優(yōu)阻星。
3. 高斯混合模型(GMM)
3.1 GMM的思想
高斯混合模型（Gaussian Mixed Model，GMM）也是一種常見的聚類算法已添，與K均值算法類似妥箕，同樣使用了EM算法進行迭代計算滥酥。高斯混合模型假設每個簇的數據都是符合高斯分布（又叫正態(tài)分布）的，當前數據呈現的分布就是各個簇的高斯分布疊加在一起的結果畦幢。
第一張圖是一個數據分布的樣例坎吻，如果只用一個高斯分布來擬合圖中的數據，圖 中所示的橢圓即為高斯分布的二倍標準差所對應的橢圓宇葱。直觀來說禾怠，圖中的數據 明顯分為兩簇，因此只用一個高斯分布來擬和是不太合理的贝搁，需要推廣到用多個 高斯分布的疊加來對數據進行擬合吗氏。第二張圖是用兩個高斯分布的疊加來擬合得到的結果。這就引出了高斯混合模型雷逆，即用多個高斯分布函數的線形組合來對數據分布進行擬合弦讽。理論上，高斯混合模型可以擬合出任意類型的分布膀哲。
高斯混合模型的核心思想是往产，假設數據可以看作從多個高斯分布中生成出來 的。在該假設下某宪，每個單獨的分模型都是標準高斯模型仿村，其均值 和方差
是待估計的參數。此外兴喂，每個分模型都還有一個參數
蔼囊，可以理解為權重或生成數據的概 率。高斯混合模型的公式為：
通常我們并不能直接得到高斯混合模型的參數衣迷，而是觀察到了一系列 數據點畏鼓，給出一個類別的數量K后，希望求得最佳的K個高斯分模型壶谒。因此云矫，高斯 混合模型的計算，便成了最佳的均值μ汗菜，方差Σ让禀、權重π的尋找，這類問題通常通過 最大似然估計來求解陨界。遺憾的是巡揍，此問題中直接使用最大似然估計，得到的是一 個復雜的非凸函數普碎，目標函數是和的對數吼肥，難以展開和對其求偏導。
**在這種情況下，可以用EM算法缀皱。 **EM算法是在最大化目標函數時斗这，先固定一個變量使整體函數變?yōu)橥箖?yōu)化函數，求導得到最值啤斗，然后利用最優(yōu)參數更新被固定的變量表箭，進入下一個循環(huán)。具體到高 斯混合模型的求解钮莲，EM算法的迭代過程如下免钻。
首先，初始隨機選擇各參數的值崔拥。然后极舔，重復下述兩步，直到收斂链瓦。
- E步驟拆魏。根據當前的參數，計算每個點由某個分模型生成的概率慈俯。
- M步驟渤刃。使用E步驟估計出的概率，來改進每個分模型的均值贴膘，方差和權重卖子。
高斯混合模型是一個生成式模型⌒滔浚可以這樣理解數據的生成過程洋闽，假設一個最簡單的情況，即只有兩個一維標準高斯分布的分模型N(0,1)和N(5,1)氛琢，其權重分別為0.7和0.3喊递。那么，在生成第一個數據點時阳似，先按照權重的比例，隨機選擇一個分布铐伴，比如選擇第一個高斯分布撮奏，接著從N(0,1)中生成一個點，如?0.5当宴，便是第一個數據點畜吊。在生成第二個數據點時，隨機選擇到第二個高斯分布N(5,1)户矢，生成了第二個點4.7玲献。如此循環(huán)執(zhí)行，便生成出了所有的數據點。
也就是說捌年，我們并不知道最佳的K個高斯分布的各自3個參數瓢娜，也不知道每個 數據點究竟是哪個高斯分布生成的。所以每次循環(huán)時礼预，先固定當前的高斯分布不 變眠砾，獲得每個數據點由各個高斯分布生成的概率。然后固定該生成概率不變托酸，根據數據點和生成概率褒颈，獲得一個組更佳的高斯分布。循環(huán)往復励堡，直到參數的不再變化谷丸，或者變化非常小時，便得到了比較合理的一組高斯分布应结。
3.2 GMM與K-Means相比
高斯混合模型與K均值算法的相同點是：
- 它們都是可用于聚類的算法刨疼；
- 都需要 指定K值；
- 都是使用EM算法來求解摊趾；
- 都往往只能收斂于局部最優(yōu)币狠。
而它相比于K 均值算法的優(yōu)點是，可以給出一個樣本屬于某類的概率是多少砾层；不僅僅可以用于聚類漩绵，還可以用于概率密度的估計；并且可以用于生成新的樣本點肛炮。
4. 聚類算法如何評估
由于數據以及需求的多樣性止吐，沒有一種算法能夠適用于所有的數據類型、數 據簇或應用場景侨糟，似乎每種情況都可能需要一種不同的評估方法或度量標準碍扔。例 如，K均值聚類可以用誤差平方和來評估秕重，但是基于密度的數據簇可能不是球形不同， 誤差平方和則會失效。在許多情況下溶耘，判斷聚類算法結果的好壞強烈依賴于主觀 解釋二拐。盡管如此，聚類算法的評估還是必需的凳兵，它是聚類分析中十分重要的部分之一百新。
聚類評估的任務是估計在數據集上進行聚類的可行性，以及聚類方法產生結 果的質量庐扫。這一過程又分為三個子任務饭望。
-
估計聚類趨勢仗哨。
這一步驟是檢測數據分布中是否存在非隨機的簇結構。如果數據是基本隨機 的铅辞，那么聚類的結果也是毫無意義的厌漂。我們可以觀察聚類誤差是否隨聚類類別數 量的增加而單調變化，如果數據是基本隨機的巷挥，即不存在非隨機簇結構桩卵，那么聚 類誤差隨聚類類別數量增加而變化的幅度應該較不顯著，并且也找不到一個合適 的K對應數據的真實簇數倍宾。
-
判定數據簇數雏节。
確定聚類趨勢之后，我們需要找到與真實數據分布最為吻合的簇數高职，據此判定聚類結果的質量钩乍。數據簇數的判定方法有很多，例如手肘法和Gap Statistic方 法怔锌。需要說明的是寥粹，用于評估的最佳數據簇數可能與程序輸出的簇數是不同的。 例如埃元，有些聚類算法可以自動地確定數據的簇數涝涤，但可能與我們通過其他方法確 定的最優(yōu)數據簇數有所差別。
-
測定聚類質量岛杀。
在無監(jiān)督的情況下阔拳，我們可以通過考察簇的分離情況和簇的緊 湊情況來評估聚類的效果。定義評估指標可以展現面試者實際解決和分析問題的 能力类嗤。事實上測量指標可以有很多種糊肠，以下列出了幾種常用的度量指標，更多的 指標可以閱讀相關文獻遗锣。
輪廓系數货裹、均方根標準偏差、R方（R-Square）精偿、改進的HubertΓ統(tǒng)計弧圆。
5. 代碼實現
作者：@mantchs
GitHub：https://github.com/NLP-LOVE/ML-NLP
歡迎大家加入討論！共同完善此項目笔咽！群號：【541954936】點擊加入
