AI - Ch18 機器學習(6), 分群/聚類：K平均演算法 Clustering: K-means Algorithm

非監督式學習
在非監督式學習中，預先準備好的範例數據並不被特別標識，非監督式學習的學習模型是為了推斷出數據的一些內在結構。它是監督式學習和強化學習等策略之外的一種選擇。

所謂監督式學習與非監督式學習的差異，主要在於目標預測變數，監督式學習，有目標變數去訓練模型，因此模型評估講求準度；而非監督式分析的目的在於找出輸入變數間的內部關係與資料的形貌(pattern)，找出資料間大致分布的趨勢，而沒有要預測的對象。

實務上，典型的任務是分類和迴歸分析，常被拿來應用的非監督式演算方法包括

1. 關聯規則的學習 (Frequent itemset, Association rule - Apriori)
2. 群集分析 (Clustering - K-Means)
3. 在人工神經網路中，自我組織映射（SOM）和適應性共振理論（ART）則是最常用的非監督式學習。

分群 (clustering)
分群是一種將資料分類成群的方法，為一種非監督式學習，也就是訓練資料沒有預先定義的標籤。其主要的目的在於找出資料中相似的幾個群聚，讓在同一個子集中的成員對象都有相似的一些屬性，常見的包括在坐標系中更加短的空間距離等。

一般而言，分群法可以大致歸為兩大類：

• 階層式分群法 (hierarchical clustering) : 群的數目可以由大變小(divisive hierarchical clustering)，或是由小變大(agglomerative hierarchical clustering)，來進群聚的合併或分裂，最後再選取最佳的群的數目。
• 分割式分群法 (partitional clustering) : 先指定群的數目後，再用一套疊代的數學運算法，找出最佳的分群方式以及相關的群中心。

不同分群法的概念比較

• For numeric and/or symbolic data
• Conceptual (model-based) vs. partitioning
• Disjoint vs. Overlapping
• Deterministic vs. probabilistic
• Hierarchical vs. flat
• Top-down vs. Bottom-up
• Incremental vs. batch learning

實務上主要常用的分群方法

• Centroid-based clustering (k-means, probability-based clustering (EM)...) : flat, batch learning, exclusive, deterministic or probabilistic.
• Connectivity based clustering (Hierarchical clustering)
• Partitioning: agglomerative (bottom-up) or divisible (top-down).
• Conceptual: Cobweb, category utility function.
• Distribution-based clustering
• Density-based clustering

評估分群品質
Precise definition of clustering quality is difficult.

• subjective approaches : high similarity within a cluster, low across clusters, in other words, Large inter-cluster distance, small intra-cluster distance)
• objective functions : Benchmarking on existing labels, like category utility, entropy).

簡易的分群 - k平均演算法 (K-means algorithm)
把n個點劃分到k個聚類中，使得每個點都屬於離他最近的均值(聚類中心)對應的聚類，以之作為聚類的標準。這個問題將歸結為一個把資料空間劃分為Voronoi cells的問題。

這個問題在計算上是NP困難，不過存在高效的啟發式演算法。一般情況下，都使用效率比較高的啟發式演算法，它們能夠快速收斂於一個局部最優解。這些演算法通常類似於通過疊代最佳化方法處理高斯混合分布的最大期望演算法（EM演算法）。而且，它們都使用聚類中心來為資料建模；然而k-平均聚類傾向於在可比較的空間範圍內尋找聚類，期望-最大化技術卻允許聚類有不同的形狀。

[注意1] k-平均聚類(K-means)與k-近鄰(KNN)之間沒有任何關係（後者是另一流行的機器學習技術）。

[注意2] 聚類數目k是一個輸入參數。選擇不恰當的k值可能會導致糟糕的聚類結果。通常要進行特徵檢查以決定聚類數目。

[注意3] 使用這一演算法無法保證得到全局最優解，例如：

k平均演算法描述
已知觀測集$(x_1,x_2,...,x_n)$，其中每個觀測都是一個d-維實向量，k-平均聚類要把這n個觀測劃分到k個集合中(k≤n),使得組內平方和（WCSS within-cluster sum of squares）最小。換句話說，它的目標是找到使得滿足下式

$\underset{\mathbf{S}} {\operatorname{arg\,min}}  \sum_{i=1}^{k} \sum_{\mathbf x \in S_i} \left\| \mathbf x - \boldsymbol\mu_i \right\|^2$，其中$\mu _i$是$S_i$中所有點的均值。

通常使用了疊代最佳化的技術。稱為k-平均演算法或Lloyd演算法。已知初始的k個均值點$m_1^{(1)},...,m_k^{(1)}$，演算法的按照下面兩個步驟交替進行：


1.   分配(Assignment)：將每個觀測分配到聚類中，使組內平方和(WCSS)達最小。因為這一平方和就是平方後的歐氏距離，所以很直觀地把觀測分配到離它最近得均值點即可（數學上，這意味依照由這些均值點生成的Voronoi圖來劃分上述觀測）。

$S_i^{(t)}=\left \{ x_p:\left \| x_p-m_i^{(t)} \right \|^2\leq \left \| x_p -m_j^{(t)} \right \|^2\forall j,1\leq j\leq k \right \}$

其中每個$x_p$都只被分配到一個確定的聚類$S^{t}$中，儘管在理論上它可能被分配到2個或者更多的聚類。


2.   更新(Update)：計算上步得到聚類中每一聚類觀測值圖心，作為新均值點。

$m_i^{(t+1)}=\frac{1}{\left | S_i^{(t)} \right |}\sum_{x_j\in S_i^{(t)}}x_j$

因為算術平均是最小平方估計，所以這一步同樣減小了目標函式組內平方和（WCSS）的值。


這一演算法將在對於觀測的分配不再變化時收斂。由於交替進行的兩個步驟都會減小目標函式WCSS的值，並且分配方案只有有限種，所以演算法一定會收斂於某一（局部）最優解。

下面的系列圖是一個很好的K-means演算法範例：

The distance function

• Simplest case: one numeric attribute A : Distance(X,Y) = A(X) – A(Y)
• Several numeric attributes:
• Euclidean distance 
• Pearson’s correlation coefficient 
• Nominal attributes: distance is set to 1 if values are different, 0 if they are equal

[!] Weighting the attributes might be necessary


K-means variations
K-medians – instead of mean, use median in each dimension
Advantage: not affected by extreme values

example:
Mean of 1,3,5,7,9 is 5
Mean of 1, 3, 5, 7, 1009 is 205
Median of 1, 3, 5, 7, 1009 is 5

K-medoids – instead of virtual centers, use a real data point as the center
Advantage:  More robust to noise and outliers as compared with k-means




K-means clustering summary

• Advantages 
• Simple, understandable
• items automatically assigned to clusters
• Disadvantages
• NOT global optimal solution
• Must pick number of clusters before hand : need to check characteristics.
• All items forced into a cluster
• Too sensitive to outliers : using K-medians、K-medoids to relieve the problem.

References

交大胡毓志教授人工智慧講義

Sina App Engine Blog - 機器學習常見算法分類匯總
http://blog.sae.sina.com.cn/archives/5547

Wiki - k-平均演算法
https://zh.wikipedia.org/wiki/K-%E5%B9%B3%E5%9D%87%E7%AE%97%E6%B3%95

活學活用分群分析--如何運用SAS EM Cluster node進行客群分析(上)
http://www.sasresource.com/artical206.html