Clustering - 物以類聚
經過一學期的折磨，筆者終於挨過去了，直到現在才有空寫文。今次的主題是一個非常入門也是很重要的，那就是Clustering！
Clustering (聚集) 一般用作把相似的事物，都把它圈起來，至於多少個群組才是最好，留在之後討論吧。在香港有一句押韻冷笑話：痴痴呆呆；坐埋一枱。愈痴呆愈容易會被圈起來。在介紹當中的算法設計，我們先反思為什麼Clustering的出現是那麼重要呢？
首先，Clustering這個算法是非監督式的(Unsupervised)，這意味著它不會透過已知的答案去訓練自己，反過來是根據數據本身的特質去計算相似度，然後把集群圈出來。舉例來說，對於我們人腦要分辦男女是一件如意反掌的事，但對機器並不是，Clustering在訓練過程不會因為知道男女，只會把相似的特質的人圈起來，當然，我們要教會機器利用適合的特質，例如：身高，頭髮長度等特徵，來進行聚集，否則永遠結果都不似預期的。來到這裡，有讀者可能會反思一下，竟然我們都已經能輕易分辦男女，早已知道答案是什麼，為何不直接不用監督式的算法呢？因此，認請楚自己的想達到的目標和了解算法背後的設計的原意，無論在數據分析或者機器學習均是極為重要的第一步！來總結一下，Clustering可在人們心中沒有答案的前提下，圈出群組來作分類。另外，請記僅用作分類的算法，不一定是監督式的。
在數學上，一般會用距離來量化相似度，這是最直觀和容易解稱的。而距離的計算方法，也有很多不同樣式，而最常用的是Euclidean Distance：$\sqrt{\sum_{i=1}^n (x_i - y_i)^2}$，假設$x$和$y$這兩點都依付在一個笛卡爾坐標平面上，即是$n=2$，用以前中學學習的距離分式就是：$\sqrt{\sum_{i=1}^2 (x_i - y_i)^2}$，你會發現兩點之間的最短離正正是Euclidean Distance。假設痴呆程度是由兩個特徵：行為和心理(5分為滿分 ，代表最痴呆)這兩個因素組成的，現在有一對痴呆和正常的朋友，他們的距離等於$\sqrt{(5-0)^2+(5-0)^2}=5$，如果兩個都是痴呆的話，距離就變短了：$\sqrt{(5-5)^2+(5-5)^2}=0$。所以距離愈少的，暗示了兩者相似度十分的高。
當明白了距離的藝術之後，要理解Clustering這算法的設計便容易得多，終於都來到戲肉了！。其實實行Clustering的方法大體上分為兩種：Partitional Clustering及Hierarchical Clustering。它們各有好處壞處，只要根據自己的目標來選擇利用那個方法就好了。
首先，Clustering這個算法是非監督式的(Unsupervised)，這意味著它不會透過已知的答案去訓練自己，反過來是根據數據本身的特質去計算相似度，然後把集群圈出來。舉例來說，對於我們人腦要分辦男女是一件如意反掌的事，但對機器並不是，Clustering在訓練過程不會因為知道男女，只會把相似的特質的人圈起來，當然，我們要教會機器利用適合的特質，例如：身高，頭髮長度等特徵，來進行聚集，否則永遠結果都不似預期的。來到這裡，有讀者可能會反思一下，竟然我們都已經能輕易分辦男女，早已知道答案是什麼，為何不直接不用監督式的算法呢？因此，認請楚自己的想達到的目標和了解算法背後的設計的原意，無論在數據分析或者機器學習均是極為重要的第一步！來總結一下，Clustering可在人們心中沒有答案的前提下，圈出群組來作分類。另外，請記僅用作分類的算法，不一定是監督式的。
在數學上，一般會用距離來量化相似度，這是最直觀和容易解稱的。而距離的計算方法，也有很多不同樣式，而最常用的是Euclidean Distance：$\sqrt{\sum_{i=1}^n (x_i - y_i)^2}$，假設$x$和$y$這兩點都依付在一個笛卡爾坐標平面上，即是$n=2$，用以前中學學習的距離分式就是：$\sqrt{\sum_{i=1}^2 (x_i - y_i)^2}$，你會發現兩點之間的最短離正正是Euclidean Distance。假設痴呆程度是由兩個特徵：行為和心理(5分為滿分 ，代表最痴呆)這兩個因素組成的，現在有一對痴呆和正常的朋友，他們的距離等於$\sqrt{(5-0)^2+(5-0)^2}=5$，如果兩個都是痴呆的話，距離就變短了：$\sqrt{(5-5)^2+(5-5)^2}=0$。所以距離愈少的，暗示了兩者相似度十分的高。
當明白了距離的藝術之後，要理解Clustering這算法的設計便容易得多，終於都來到戲肉了！。其實實行Clustering的方法大體上分為兩種：Partitional Clustering及Hierarchical Clustering。它們各有好處壞處，只要根據自己的目標來選擇利用那個方法就好了。
Partitional Clustering
用這個聚集的方法，群組和群組之間不會有任何重疊，如果一個人被分類為群組甲，意味著他不會屬於群組乙，丙等等。最具代表的算法非K-means Clustering莫屬了，只要理解其設計，便十分容易理解群組之間都是如何被分割出來。
K-means Algorithm
根據下圖，我們很容易看到這裡有3個明顯的群組，我們先假設$k=3$，k的數量代表seed的數量，而3顆seed最後會形成3個不重疊群組。
Seed的最初位置一般都是隨機的（如圖：Initial Stage），先考慮其中一點，計算3顆seed和這點的距離，你可以用不同方法的距離，最常用就是Euclidean Distance，你會得到3組的距離，把點都分配到最短距離的Seed，即是如果最短的距離是點與Seed A的話，那麼這一點會被分類成群組A。考慮所有的數據點，每一點都已經分配到相應的群組，然後我們要更新seed的位置（如圖：Iteration 1），也就是把每個群組的中心計算出離並成為新的Seed，然後重新考慮所有的數據點，重新計算距離 ，以分配到相應的群組，直到分配的結果已經沒有變化為止，數學上來說，也就是Converged了（如圖：Iteration 5），那麼三個獨立的群組就會顯露出來。
從這個設計，我們能理解到這算法的限制，首先，在現實的情況，群組的數目不一定可以用肉眼看見和判斷，我們必需要選擇集群的數量，才能使用這方法。而且Seed的最初的位置會影響分出來的集群是否明顯師有效的，所以要設定Seed在不同的位置並重覆算法。如何衡量集群是否聚集得有效？要量化的話，其實也是很直覺的。一個理想的集群的時候，我們都希望它是聚合了相似度高的東西 (較低的WithinSS)，而且群組之間是容易分辦的，也就是群組之間的相似度是低的(較高的BetweenSS)。WithinSS是量化把每一個群組和屬於它的點之間的距離二次方總和，再加起來，換句話說，在一個群組裡愈密集的點，會計算愈低的WithinSS值；而考慮一對群組的相似度，也離不開用距離作指標，把兩個集群的中心，算出距離二次方，乘上作為權重(Weight)的數據點數量，再把其餘一對又一對的距離二次方加起來，會得到BetweenSS。
$WithinSS = \sum_{i=1}^k \sum_{j=1}^{n_i} (x_{ij}-\bar{x_i})^2$
$BetweenSS = \sum_{i=1}^k n_i(\bar{x_i}-\bar{x})^2$
既然我們知道如何用數學來反映理想的Cluster，只要我們一直用不同的K來運行k-means，來獲得WithinSS和BetweenSS，從而選擇最優化和對應的k值。所以在判斷K值的時候，也不再依賴肉眼，或者主觀的選擇了。雖然Clustering的訓練的模式是非監督的，但我們依舊可以利用得出的結果來調整模型的參數，也即是K和seed的初始位置。無論是什麼的模型，學懂如何調整模型的參數是非常重要的。
由於算法和方法實在太多，未能一一討論，但理解K-means後，會讓你更了解Partitional Clustering這個家庭是一般是如何運行。
Hierarchical Clustering
利用層遞的方式把數據聚集起來，由n個數據點，聚集成n-k個集群(k是某整數且少於n)，最終成為1個集群。這個設計並不需要事先考慮群組的數量，同樣是用距離來決定聚合或否，這模型的參數主要是計算集群與集群距離的方式，大致有四個常用的方法：
Single Linkage：集群和集群最近的兩點之距離
Complete Linkage：集群和集群最遠的兩點之距離
Average：集群和集群最近的所有點的距離，並取平均值
Ward's Method：假設兩個集群合成一個，把每點和合成集群中心的距離取平方，再加起來
筆者利用Complete Linkage的方法來作Hierarchical Clustering，結果顯示在下左圖，由於想跟K-means的作個比較，於是我選了3個集群數目（見右圖）。可能點的分佈都比較直接，所以兩者結果也不是差很遠的，紅色的集群也是明顯地分割出來，只是藍色點的數目比較少而已。
用這個聚集的方法，群組和群組之間不會有任何重疊，如果一個人被分類為群組甲，意味著他不會屬於群組乙，丙等等。最具代表的算法非K-means Clustering莫屬了，只要理解其設計，便十分容易理解群組之間都是如何被分割出來。
K-means Algorithm
根據下圖，我們很容易看到這裡有3個明顯的群組，我們先假設$k=3$，k的數量代表seed的數量，而3顆seed最後會形成3個不重疊群組。
Seed的最初位置一般都是隨機的（如圖：Initial Stage），先考慮其中一點，計算3顆seed和這點的距離，你可以用不同方法的距離，最常用就是Euclidean Distance，你會得到3組的距離，把點都分配到最短距離的Seed，即是如果最短的距離是點與Seed A的話，那麼這一點會被分類成群組A。考慮所有的數據點，每一點都已經分配到相應的群組，然後我們要更新seed的位置（如圖：Iteration 1），也就是把每個群組的中心計算出離並成為新的Seed，然後重新考慮所有的數據點，重新計算距離 ，以分配到相應的群組，直到分配的結果已經沒有變化為止，數學上來說，也就是Converged了（如圖：Iteration 5），那麼三個獨立的群組就會顯露出來。
從這個設計，我們能理解到這算法的限制，首先，在現實的情況，群組的數目不一定可以用肉眼看見和判斷，我們必需要選擇集群的數量，才能使用這方法。而且Seed的最初的位置會影響分出來的集群是否明顯師有效的，所以要設定Seed在不同的位置並重覆算法。如何衡量集群是否聚集得有效？要量化的話，其實也是很直覺的。一個理想的集群的時候，我們都希望它是聚合了相似度高的東西 (較低的WithinSS)，而且群組之間是容易分辦的，也就是群組之間的相似度是低的(較高的BetweenSS)。WithinSS是量化把每一個群組和屬於它的點之間的距離二次方總和，再加起來，換句話說，在一個群組裡愈密集的點，會計算愈低的WithinSS值；而考慮一對群組的相似度，也離不開用距離作指標，把兩個集群的中心，算出距離二次方，乘上作為權重(Weight)的數據點數量，再把其餘一對又一對的距離二次方加起來，會得到BetweenSS。
$WithinSS = \sum_{i=1}^k \sum_{j=1}^{n_i} (x_{ij}-\bar{x_i})^2$
$BetweenSS = \sum_{i=1}^k n_i(\bar{x_i}-\bar{x})^2$
既然我們知道如何用數學來反映理想的Cluster，只要我們一直用不同的K來運行k-means，來獲得WithinSS和BetweenSS，從而選擇最優化和對應的k值。所以在判斷K值的時候，也不再依賴肉眼，或者主觀的選擇了。雖然Clustering的訓練的模式是非監督的，但我們依舊可以利用得出的結果來調整模型的參數，也即是K和seed的初始位置。無論是什麼的模型，學懂如何調整模型的參數是非常重要的。
由於算法和方法實在太多，未能一一討論，但理解K-means後，會讓你更了解Partitional Clustering這個家庭是一般是如何運行。
Hierarchical Clustering
利用層遞的方式把數據聚集起來，由n個數據點，聚集成n-k個集群(k是某整數且少於n)，最終成為1個集群。這個設計並不需要事先考慮群組的數量，同樣是用距離來決定聚合或否，這模型的參數主要是計算集群與集群距離的方式，大致有四個常用的方法：
Single Linkage：集群和集群最近的兩點之距離
Complete Linkage：集群和集群最遠的兩點之距離
Average：集群和集群最近的所有點的距離，並取平均值
Ward's Method：假設兩個集群合成一個，把每點和合成集群中心的距離取平方，再加起來
筆者利用Complete Linkage的方法來作Hierarchical Clustering，結果顯示在下左圖，由於想跟K-means的作個比較，於是我選了3個集群數目（見右圖）。可能點的分佈都比較直接，所以兩者結果也不是差很遠的，紅色的集群也是明顯地分割出來，只是藍色點的數目比較少而已。
在現實上，常見的應用有Customer Segmentation，在很多時候，企業都傾向找出一些可獲利的客戶群，針對他們並設計對應的市埸策略。公司所擁有的交易數據，客戶資料，甚至利用社交媒體上的Data，要做這個客戶分類，技術不會是一個障礙，如何理解和解釋結果，並作出相應的決定和策略，相信這部分才是最有具意義和價值。最後筆者的忠告是：原諒筆者長氣一點，認請自己的分析背後的目的，才會讓你在選擇合適的模型，調整模型參數，選擇重要的特徵來訓練模型的過程中得心應手。
Comments
Post a Comment