摘要
聚類是一種無監督的學習（無監督學習不依賴預先定義的類或帶類标記的訓練執行個體），它将相似的對象歸到同一個簇中，它是觀察式學習，而非示例式的學習，有點像全自動分類。說白了，聚類（clustering）是完全可以按字面意思來了解的——将相同、相似、相近、相關的對象執行個體聚成一類的過程。機器學習中常見的聚類算法包括 k-Means算法、期望最大化算法（Expectation Maximization，EM，參考“EM算法原理”）、譜聚類算法（參考機器學習算法複習-譜聚類）以及人工神經網絡算法，本文闡述的是K-均值聚類算法，本文介紹K-均值（K-means）和二分K-均值聚類算法。
（一）何謂聚類
還是那句“物以類聚、人以群分”，如果預先知道人群的标簽（如文藝、普通、2B），那麼根據監督學習的分類算法可将一個人明确的劃分到某一類；如果預先不知道人群的标簽，那就隻有根據人的特征（如愛好、學曆、職業等）劃堆了，這就是聚類算法。
聚類是一種無監督的學習（無監督學習不依賴預先定義的類或帶類标記的訓練執行個體），它将相似的對象歸到同一個簇中，它是觀察式學習，而非示例式的學習，有點像全自動分類。所謂簇就是該集合中的對象有很大的相似性，而不同集合間的對象有很大的相異性。簇識别（cluster identification）給出了聚類結果的含義，告訴我們這些簇到底都是些什麼。通常情況下，簇質心可以代表整個簇的資料來做出決策。聚類方法幾乎可以應用于所有對象，簇内的對象越相似，聚類的效果越好。
從機器學習的角度講，簇相當于隐藏模式，聚類與分類的最大不同在于，分類學習的執行個體或資料對象有類别标記，而聚類則不一樣，需要由聚類學習算法自動确定标記。因為其産生的結果與分類相同，而隻是類别沒有預先定義，是以聚類也被稱為無監督分類（unsupervised classification )。
聚類分析是一種探索性的分析，在分類的過程中，人們不必事先給出一個分類的标準，聚類分析能夠從樣本資料出發，自動進行分類。聚類分析所使用方法的不同，常常會得到不同的結論。不同研究者對于同一組資料進行聚類分析，所得到的聚類數未必一緻。從實際應用的角度看，聚類分析是資料挖掘的主要任務之一。而且聚類能夠作為一個獨立的工具獲得資料的分布狀況，觀察每一簇資料的特征，集中對特定的聚簇集合作進一步地分析。聚類分析還可以作為其他算法（如分類和定性歸納算法）的預處理步驟。
聚類分析試圖将相似對象歸入同一簇，将不相似對象歸到不同簇，那麼是否“相似”就要有所選擇的相似度計算方法。現在，存在多種不同的相似度計算方法，到底使用哪種相似度計算方法取決于具體應用，選擇合适的相似度計算方法才會提高聚類算法的性能。機器學習中常用的相似性度量方法參考博文“機器學習中的相似性度量”。
聚類算法通常按照中心點或者分層的方式對輸入資料進行歸并，是以的聚類算法都試圖找到資料的内在結構，以便按照最大的共同點将資料進行歸類，其目标是使同一類對象的相似度盡可能地大；不同類對象之間的相似度盡可能地小。目前聚類的方法很多，根據基本思想的不同，大緻可以将聚類算法分為五大類：層次聚類算法、分割聚類算法、基于限制的聚類算法、機器學習中的聚類算法和用于高次元的聚類算法，參考“各種聚類算法的比較”。聚類算法的基本過程包含特征選擇、相似性度量、聚類準則、聚類算法和結果驗證等，具體參考“聚類算法學習筆記（一）——基礎”。
說白了，聚類（clustering）是完全可以按字面意思來了解的——将相同、相似、相近、相關的對象執行個體聚成一類的過程。簡單了解，如果一個資料集合包含N個執行個體，根據某種準則可以将這N個執行個體劃分為m個類别，每個類别中的執行個體都是相關的，而不同類别之間是差別的也就是不相關的，這就得到了一個聚類模型了。判别新樣本點的所屬類時，就通過計算該點與這m個類别的相似度，選擇最相似的那個類作為該點的歸類。
既然聚類可以看做是一種無監督分類，那麼其應用場景就是廣泛的，包括使用者群劃分、文本分類、圖像識别等等。當幾乎沒有有關資料的先驗資訊(如統計模型)可用，而使用者又要求盡可能地對資料的可能性少進行假設等限制條件下，聚類方法都适合用來檢視資料點中的内在關系以對它們的結構進行評估、決策。
機器學習中常見的聚類算法包括 k-Means算法、期望最大化算法（Expectation Maximization，EM，參考“EM算法原理”）、譜聚類算法（參考機器學習算法複習-譜聚類）以及人工神經網絡算法，本文介紹K-均值（K-means）聚類算法。
（二）K-均值（K-means）聚類算法
1. 認識K-均值聚類算法
K-均值算法是最簡單的一種聚類算法，屬于分割式聚類算法，目的是使各個簇（共k個）中的資料點與所在簇質心的誤差平方和SSE(Sum of Squared Error）達到最小，這也是評價K-means算法最後聚類效果的評價标準。
k-means算法的基礎是最小誤差平方和準則。其代價函數是：
式中，μc(i)表示第i個簇的質心，我們希望得到的聚類模型代價函數最小，直覺的來說，各簇内的樣本越相似，其與該簇質心的誤差平方越小。計算所有簇的誤差平方之和，即可驗證分為k個簇時時的聚類是否是最優的。SSE值越小表示資料點越接近于它們的質心，聚類效果也越好。因為對誤差取了平方，是以更加重視那些遠離中心的點。一種肯定可以降低SSE值的方法是增加簇的個數，但這違背了聚類的目标，聚類的目标是在保持族數目不變的情況下提高簇的品質。
k-均值（k-means）聚類算法之是以稱之為k-均值是因為它可以發現k個不同的簇，且每個簇的中心采用簇中所含子資料集樣本特征的均值計算而成。k-均值是發現給定資料集的k個簇的算法，簇個數k由使用者給定，每一個簇通過其質心( centroid) -- 即簇中所有點的中心來描述。K-均值聚類算法需要數值型資料來進行相似性度量，也可以将标稱型資料映射為二值型資料再用于度量相似性，其優點是容易實作，缺點是可能收斂到局部最小值，在大規模資料集上收斂較慢。
假設訓練樣本資料集X為(m, n）維矩陣，m表示樣本數、n表示每個樣本點的特征數，那麼k-均值聚類算法的結果就是得到一個kxn維矩陣，k表示使用者指定的簇個數，每一行都是一個長度為n的行向量--第i個元素就是該簇中所有樣本第j（j=0,1,...,n-1）個特征的均值。下圖是K-均值聚類算法聚類的過程：
2. 算法過程
K-均值算法的工作流程是這樣的。首先，随機确定k個初始點作為質心；然後将資料集中的每個點配置設定到一個簇中--就是為每個點找距其最近的質心，并将其配置設定給該質心所對應的簇；該步完成之後更新每個簇的質心（該簇所有資料樣本特征的平均值）；上述過程疊代多次直至所有資料點的簇歸屬不再改變或者達到了最大疊代次數Maxiteration。k-均值算法的性能會受到所選相似性度量方法的影響，常用的相似性度量方法就是計算歐氏距離。上述過程的僞代碼表示如下：
***************************************************************
建立k個點作為起始質心
任意點的簇配置設定結果發生改變時（循環内設定、維護标志位changed，也可同時設定最大疊代次數max）
對資料集中的每個資料點
對每個質心
計算質心與資料點之間的距離
将資料點配置設定到距其最近的簇（若有點的簇發生改變則置标志位為changed = True）
更新簇中心： 對每一個簇，計算簇中所有點的均值并将均值作為質心
***************************************************************
上述循環的終止條件是每個點的簇配置設定結果沒有發生改變或者達到了最大循環次數。
初始化時k個質心的選擇可以是随機的，但為了提高性能常用的方式是
（1）盡量選擇距離比較遠的點（方法：依次計算出與已确定的點（第一個點可以随機選擇）的距離，并選擇距離最大的點）。當k比較大時，這種方法計算量比較複雜，适合二分K-均值聚類算法的k值初始化。
（2）采取層次聚類的方式找出k個簇。 TBD
3. 特征值處理
K-均值聚類算法需要數值型資料來進行相似性度量，也可以将标稱型資料映射為二值型資料再用于度量相似性。
另外，樣本會有多個特征，每一個特征都有自己的定義域和取值範圍，他們對distance計算的影響也就不一樣，如取值較大的影響力會蓋過取值較小的參數。為了公平，樣本特征取值必須做一些scale處理，最簡單的方式就是所有特征的數值都采取歸一化處置，把每一維的資料都轉化到0,1區間内，進而減少疊代次數，提高算法的收斂速度。
4. k值的選取
前面提到，在k-均值聚類中簇的數目k是一個使用者預先定義的參數，那麼使用者如何才能知道k的選擇是否正确？如何才能知道生成的簇比較好呢？與K-近鄰分類算法的k值确定方法一樣,k-均值算法也可采用交叉驗證法确定誤差率最低的k值，參考“機器學習經典算法詳解及Python實作--K近鄰(KNN)算法”的2.3節-k值的确定。
當k的數目低于真實的簇的數目時，SSE（或者平均直徑等其他分散度名額）會快速上升。是以可以采用多次聚類，然後比較的方式确定最佳k值。多次聚類，一般是采用 k=1, 2, 4, 8... 這種二分數列的方式，通過交叉驗證找到一個k在 v/2, v 時擷取較好聚類效果的v值，然後繼續使用二分法，在 [v/2, v] 之間找到最佳的k值。
5. K-均值算法的Python實作
下載下傳位址：TBD
K-均值算法收斂但聚類效果較差的原因是，K-均值算法收斂到了局部最小值，而非全局最小值（局部最小值指結果還可以但并非最好結果，全局最小值是可能的最好結果)。為克服k-均值算法收斂于局部最小值的問題，有人提出了另一個稱為二分k- 均值（bisecting K-means)的算法。
（三）二分K-均值（bisecting k-means)聚類算法
顧名思義，二分K-均值聚類算法就是每次對資料集（子資料集）采取k=2的k-均值聚類劃分，子資料集的選取則有一定的準則。二分K-均值聚類算法首先将所有點作為一個簇，第一步是然後将該簇一分為二，之後的疊代是：在所有簇中根據SSE選擇一個簇繼續進行二分K-均值劃分，直到得到使用者指定的簇數目為止。根據SSE選取繼續劃分簇的準則有如下兩種:
(1)選擇哪一個簇進行劃分取決于對"其劃分是否可以最大程度降低SSE的值。這需要将每個簇都進行二分劃分，然後計算該簇二分後的簇SSE之和并計算其與二分前簇SSE之差（當然SSE必須下降），最後選取內插補點最大的那個簇進行二分。
該方案下的二分k-均值算法的僞代碼形式如下：
***************************************************************
将所有資料點看成一個簇
當簇數目小于k時
對每一個簇
計算總誤差
在給定的簇上面進行k-均值聚類（k=2）
計算将該簇一分為二後的總誤差
選擇使得誤差最小的那個簇進行劃分操作
***************************************************************
(2)另一種做法是所有簇中選擇SSE最大的簇進行劃分，直到簇數目達到使用者指定的數目為止，算法過程與（1）相似，差別僅在于每次選取簇中SSE最大的簇。
二分K-均值聚類算法的Python實作
下載下傳位址：TBD
參考
機器學習中的相似性度量
相似度計算常用方法綜述