Clustering

概念

把許多事物按照某種標準歸為數個類別，其中較為相近/類似的聚為一類，反之較不相近的則聚為不同類。目的是企圖從一大堆雜亂無章的原始資料中，找出少數幾個較小的群體，使得群體內的分子在某些變項的測量值均很類似，而群體與群體間的分子在該測量值上差異較大。 （同一組樣本會因不同目的、資料輸入方式、所選擇分群特徵或資料屬性，形成不同的分群結果）

類型

分割式分群 (Partitional Clustering)：

須事先指定分群數目，選擇對應數量的起始群集中心點，每個資料點只會分配到一個群集。所有資料點均計算與每個中心點的距離或相似度，並依據結果劃分至特定群集。經過不斷的迭代，直到群內的變異/平方誤差最小

階層式分群/系譜分群 (Hierarchical Clustering)

不須事先設定群數k，每次反覆運算過程僅將距離最近的兩個樣本/群聚為一類，直到符合設定的群集數條件

以密度為基礎的方法 (Density-based Method)

問題：

  • 階層式或分割式均以資料點到特定中心點/質心(centroid)的距離為分群依據，這樣「以距離為基礎」的衡量尺度只能得到（高維度空間）球狀的分群結果。若以質心來代表群集，容易使過大的群集或非球狀的群集被分為數個小群集。
  • 可以在有雜訊的空間資料中發現任意形狀的群
  • 若資料點分布為任意形狀，則應考量資料間的緊密程度

Densit-based Spatial Clustering of Application with Noise (DBSCAN)演算法

  • 判斷資料點間的密度是否為密集；將群集看作是資料空間中被低密度區域分割開的「稠密區域」，即密度相連樣本點的最大集合。
  • 高密度的定義為在設定的半徑範圍(Eps)內，所涵蓋資料的最小資料數目是否有達到所設定的門檻值(Minpts)；若符合則為「核心點(core)」，若無則稱「邊緣點」
  • 在半徑範圍內的所有點成為一個群，稱核心點「直接密度」可以到達群內的點（「境內點(border)」）。可密度相連的點成為一個群；不與其他點密度相連的點稱為「雜訊點(noise)」。
  • 可密度相連的核心點設定為一群，與這一群核心點相連的邊緣點成為另一群
  • 特性在於可在具有雜訊的空間資料中發現任意形狀的群集(其他方法只能發現「類別圓形/球狀」)
  • 另有OPTICS演算法、DENCLUE演算法

以模式為基礎的方法

將資料依據模型予以配適而產生群集，如類神經網絡中的自我組織網絡映射圖(self-organization map, SOM)，將資料點投射至二維平面來進行群集分析。

期望最大化分群(Expectation Maximization, EM)

  • 將資料集看做一個含有隱性變數的機率模型，並以實現模型最佳化，即取得與資料本身性質最契合的分群方式為目的。透過反覆估計模型參數找出最佳解，同時列出對應的最佳群集數k。
  • 反覆估計包含E-step (expectation)與M-step (Maximization)兩個步驟交替進行

應用：

  1. 根據顧客基本資料和交易紀錄進行分群，定義並分析不同的顧客類型，進而設計客製化的行銷策略
  2. 將性質或特性相似的網頁予以分類，增快網頁搜尋速度，或依據顧客瀏覽行為與群集分析來預測消費行為
  3. 分析信用卡使用紀錄發覺異常情形，避免盜刷所造成的損失
  4. 依據機台特徵與功能的相似程度，區分相互替代與備援的群集，提升作業效率與維持良率
  5. 將分群後的各項特徵作為後續資料分類的參考準則，或決定群集後將作為離散資料的標註代碼（資料精簡概念）

  1. 依據資料「相似度(similarity)」或「相異度(dissimilarity)」來將資料分群歸屬到數個群集(cluster)的方法，藉以找出各子群集資料背後可能隱藏的特徵、樣型或關聯現象。
  2. 相似度的數值越大，代表資料間關聯的程度越高，應歸類為同一群集。
  3. 群集分析事先並不知道群集數目，故為「非監督式學習(unsupervised learning)」而分群結果的特徵與代表的意義僅能事後加以解釋。
  4. 可視為多變量分析(multivariate analysis)中精簡資料(data reduction)的一種技術；將一大筆資料精簡成少數幾個同質性次群體(homogeneous subgroups)，達到分類、分群的目標。

k-means (k-平均值)

概念

隨機選取k個樣本作為起始中心點，將其餘樣本歸入相似度最高中心點所在的群；再計算目前群內樣本座標的平均值為新的中心點，依次循環反覆運算，直到所有樣本所屬的群不再變動。

特徵

  1. 分群結果容易受到離群值影響造成偏移，對異常值/極值敏感，穩定性差，比較適合處理分布集中的大樣本資料集。
  2. 需要預先設定分群數k（延伸至最適分群數檢定）

K-means無法直接處理類別型資料，因為無法求得資料的質心；此時可改用k-Mode，以簡單配對相異度(simple matching dissmilarity)作為衡量相似度的指標，並以群集的眾數作為群集的中心，用頻率為基礎frequency-based的方法來更新群集的眾數。 除了以直接給定或反覆分析驗證來取得適當的群集數外，另可利用兩階段方式：先用階層式集群分析演算法決定集群數目，再利用k-means重新將資料分群。

起始群集中心的選擇不同會造成不同的分群結果；如果起始群集中心的資料點不夠分散，可能會得到較差的結果。 無法處理非球狀(non-blobular)的群集、資料大小差異很大的群集、資料密度不同的群集

k-mediods (k-中心點)

概念

類似k-means，差異在於選擇各群中心點時不取樣本平均值，而是選取「到其餘樣本距離之和」最小的樣本為中心點

特徵

  1. 以群集中最接近中心位置的資料點作為群集的中心，故較不容易受雜訊與異常值的影響
  2. 圍繞中心切割法(partition around medoids, PAM) 當資料點與群集數目增加時，k-Mediods將需要大量的計算成本，許多演算法針對PAM演算法進行修改以適用於大型資料

模糊C-means分群法(Fuzzy C-means clustering, FCM)

根據 C-means algorithm 衍生而來的分群法，透過模糊邏輯的概念，希望能進一步提升分群的效果。FCM與C-means最大的差異在於加入了模糊的概念，資料點x將不再絕對地屬於任何群聚，而是以一個介於 0-1 之間的數字來表示x隸屬於某個群聚的程度。

Hierarchical Clustering (階層式分群/系譜分群)

概念

不須事先設定群數k，每次反覆運算過程僅將距離最近的兩個樣本/群聚為一類，直到符合設定的群集數條件

  • 由下往上(聚合/凝聚法agglomerative):從樹狀結構底部開始，將資料或各分群逐次合併，一開始將每個資料都視為一個獨立的分群，然後依據分群間相似度計算公式，不斷合併兩個最相似的資料/分群，直到所有資料/分群都合併成一個大的群集或達到所訂定的停止條件（設定的數量）為止。
  • 由上往下(分割/分裂法 divisive)從樹狀結構的頂端將大的群集逐次分割，一開始將所有資料視為一個大的群集，不斷地依據相似度公式將大群集分割成較小的群集，直到每個資料點各自成為一個獨立的群集或達到所訂定的停止條件（設定的數量）為止。

特徵

  1. 不須指定分群數目，讓資料自動由上往下/由下往上結合起來
  2. 在階層式分群中，主要是以資料之間的「距離」或「相似度」計算公式，來決定兩筆資料是否接近。
  3. 透過階層架構形式，將資料層層反覆地進行「聚合」或「分割」，以產生最後的樹狀結構。以樹狀圖(dendrogram)呈現各群集中所包含的資料點。根節點僅包含單一群集，代表所有資料點均屬於同一群集，葉節點各自為單一群集

操作概念

目的：使群集內的總變異最小/相似程度最大；使群集間的總變異最大/相似程度最小

  1. 資料準備與分群特徵選取：依據問題特性、資料類型與所選擇的分群演算法，自蒐集資料的變數中選舉具備代表性的變數來做為分群運算的特徵
  2. 相似度計算：選擇衡量相似度的計算方式，如距離、相關係數，但必須考慮資料類型下的可取得性與後續使用的演算法需求。eg: 在類別尺度中，採歐式距離會造成資料尺度的誤用。
  3. 分群演算：透過演算法將資料分組
  4. 分群結果評估與解釋：檢視分群結果是否合理並確認是否適用所選用的演算法；若不合理則重新檢視上述步驟。分群結果可能作為另一個分析的輸入資料，故須對群集進行定義與命名。

相似度

距離

「距離」常用來衡量兩筆資料/個體在多維變數下的相異程度。

  1. 歐式距離 Euclidean distance： 多維空間下兩個資料點的幾何距離 2.曼哈頓距離 Manhattan distance 又稱為城市街道距離city-block distance，定義為各變數差距絕對值之和。 3.乘冪距離 Minkowski distance 可視為歐式距離與曼哈頓距離的通式
  2. 加權距離 weighted distance 當各變數的重要性不同時，可給定對應權重；權重總和為1。權重相同時即為歐式距離。
  3. 標準化距離 normalized distance 不同維度資料的衡量尺度或單位不同時，衡量結果較大的變數可能dominate最後結果；e.g.薪資與年資的數字無法直接比較 解決資料在不同尺度上的差異，可先對變數進行「標準化(standardization)」，轉換至同一比較基準，可避免變數間因尺度不同導致資料的分布範圍差異過大。 傳換後資料可用以偵測異常值。
  4. 馬式距離 (Mahalanobis distance) 若變數間除了尺度差異外，其間也具有相關性 利用共變異數矩陣。當變數間不存在相關性時，所有變數的變異數均為1，馬式距離即為標準化的歐式距離。

    相似程度 (proximity)

    透過距離公式，可以計算不同群間各點間彼此的距離；再依據不同的概念設定，計算不同群間的相似程度
  5. method="single" # 最小距離/最近法/單一連結法，取群與群之間最近點的距離
  6. method="complete" # 最大距離/最遠法/完全連結法，取群與群之間最遠點的距離
  7. method="average" # 平均距離/平均法/平均連結法，群與群之間所有點距離的平均；避免群集間的距離衡量受到雜訊影響
  8. method="centroid" # 中心距離/中心法，取群與群之間中心點的距離；解決距離衡量對異常值過於敏感的問題，並能進一步處理類別型的資料
  9. method="ward.D2" # 華德法，衡量群集內(within-cluster)變異作為群集相似度。依序將所有群集合併，反覆計算與合併每一階段中最小群集的組內變異，直到所有資料均合併為一群為止。概念在使群集內資料的同質性hemogeneity最大化，即群集內變異最小化，以「均方差和 (sum of squared errors, SSE)」計算。
  10. 另一種公式：Similarity = 1/(1+d(.))

相關係數

衡量兩變數間的變動方向與程度大小的關係

  1. 皮爾森相關係數 Pearson correlation 連續型資料中最常使用，又稱線性相關係數。與單位無關，介於-1至+1間。一般而言，[0, 0.3]低度相關、(0.3, 0.7]中度相關、(0.7, 1]高度相關。
  2. 斯皮爾曼排序相關係數 (Spearman's rank correlation coefficient) 針對序列尺度資料。數值越大代表兩變數樣本資料間的順序一致性越高，並非其樣本資料具有高度相關。若所有成對資料的順序均相同，數值為1，代表兩變數等級資料具有高度一致性。

二元關聯係數

類別變數僅有0或1兩種狀態，稱二元變數或布林變數。 衡量類別資料的相似度可用簡單比對係數 (simple matching coefficient, SMC) 若某二元變數如1/True比0/False更有意義（具備某特徵），可選用Jaccard係數

R操作

可用套件：

  • stats：可使用kmeans、階層式分群（hclust()、cutree()、rect.hclust()）
  • cluster：專用於K-Medoids分群分析，包含相關演算法與資料及（pam()）
  • fpc：含有固定點分群、線性迴歸分群、DBSCAN分群等演算法（dbscan()）
  • mclust：主要用來處理高斯混合模型，透過EM演算法進行分群、分類及密度估計；Mclust()、clustBIC()、mclust2Dplot()、densityMclust()
  • e1071：利用cmeans()來執行模糊C平均算法
  1. stats套件 使用dist()來建立資料之間的「距離矩陣(Distance Matrix)」，判斷資料之間的遠與近：

distance <- dist(data_set, method="euclidean")

## 計算歐式距離矩陣。

method可設定歐式距離"euclidean"、曼哈頓距離"manhattan"、乘冪距離"minkowski"、"maximum"、"canberra"或"binary"、

cluster <- hclust(distance, method="complete") # method可設定"single"、"complete"、"average"、"centroid" "ward"

  • 相近程度(proximity)：
  • method="single" # 最小距離/最近法/單一連結法，取群與群之間最近點的距離
  • method="complete" # 最大距離/最遠法/完全連結法，取群與群之間最遠點的距離
  • method="average" # 平均距離/平均法/平均連結法，群與群之間所有點距離的平均；避免群集間的距離衡量受到雜訊影響
  • method="centroid" # 中心距離/中心法，取群與群之間中心點的距離；解決距離衡量對異常值過於敏感的問題，並能進一步處理類別型的資料
  • method="ward.D2" # 華德法，衡量群集內(within-cluster)變異作為群集相似度。依序將所有群集合併，反覆計算與合併每一階段中最小群集的組內變異，直到所有資料均合併為一群為止。概念在使群集內資料的同質性hemogeneity最大化，即群集內變異最小化，以「均方差和 (sum of squared errors, SSE)」計算。

樹狀結構視覺化 plot(cluster, hang=-1, xlab="Eclidean", labels=iris$Species) #畫出樹狀結構，圖型中縱軸高度h即為群集間距離 hang設定標籤與葉節點之間的距離，若為負數代表標籤對齊 abline(h=9, col="red") #設定一特定值來切割樹狀結構，顯示較佳的分群數量

cutree() #自定分群數量，並將資料與分群結果進行標註 cut.cluster <- cutree(cluster, k=3) #分成三群 cut.cluster #將資料轉成分群結果

table(cluster, iris$Species) #以表列方式呈現並比較分群結果和實際狀態 rect.hclust(cluster, k=4) #將分群結果在圖形中以矩形區分標示；k為自訂分群數量或自訂h高度

  1. Partitional Clustering kmeans() **資料必須為numeric，無法處理類別資料

kmeans_cluster <- kmeans(E_dist, centers=3)

kmeans_cluster$withinss table(kmeans_cluster$cluster, iris$Species) library(factoextra) fviz_cluster(kmeans_cluster, data=data_test, geom=c("point","text"), frame.type = "norm")

  1. 最適分群數目 Optimal number for clusters 分群目的：使群集內的總變異最小；使群集間的總變異最大 找出一個數字n，使得資料被分成n群時，群內的總變異(SSE)會最小，那麼n = 最佳的分群數目 Elbow Method Average Silhouette Method 平均側影法 側影系數(Silhouette Coefficient)會根據每個資料點的內聚力和分散力，衡量分群的效果(quality)。取每一個資料點的側影平均值(故稱Avg. Silhouette Method)，當作衡量最佳分群數目的準則 參數method="silhouette"

  2. NbClust套件 提供分群指標(Clustering Index)來評估分群效果 library(NbClust) NbClust(data_set, distance = "euclidean", min.nc = 2, max.nc = 25, method = "kmeans", index = "all") 引數：distance距離公式、method分群的學習方法、index很多種分群指標，設定all為除了gap, gamma, gplus以外的所有指標

results matching ""

    No results matching ""