聚類

聚類基於“物以類聚”的樸素思想，是將物理或抽象對象集合劃分為由類似的對象組成的多個類或簇（cluster）的過程。聚類使得每個簇中的數據點之間最大程度地相似，而不同簇中的數據點最大程度地不同，從而發現數據集中有效的、有用的信息。

聚類常見數據結構

· 數據矩陣（對象-屬性結構）：

假設有p個屬性（年齡、性別、身高、體重、種族...）來表示n個對象”人“，可看成是一個n×p維的矩陣（矩陣行表示對象，矩陣列表示各個屬性值）

· 相異度矩陣（對象-對象結構）：

存儲n個對象兩兩之間的相異度，可看成是一個n×n維的對稱矩陣（每個數據值表示對應行和列對象之間的度量值），度量值可以用相似度或距離來表示，當用相似度表示時，值越大表示越相似；當用距離表示時，值越小表示越相似，兩者之間可以相互轉化。

相異度矩陣可由數據矩陣通過距離計算公式獲得，在不同的算法需求中，需根據實際情況決定輸入數據結構。

聚類過程

聚類流程

k-means聚類

k-means 算法（k均值算法）是常見的聚類算法之一，將相似的數據歸聚成一個聚類，從而得到 k 個聚類，各個聚類之內的數據相似，各個聚類之間數據相異。

算法思想：

· Step1：隨機選擇數據集中k個點作為初始聚類中心；

· Step2：分別計算數據集中的點到 k 個聚類中心點的距離，將數據點劃入距離最近聚類；

· Step3：計算簇中數據對象平均值確定新的聚類中心；

· Step4：若聚類中心點結果收斂則算法結束，否則重複 Step2- Step3

缺點：

1. K 需要指定

2. 初始點的選擇對最後的聚類結果影響較大（通常以局部最優解結束）

3. 受噪音點影響較大

4. 只能處理一定形狀的簇

canopy

canopy是一種快速粗放的預聚類方法，使用簡單粗放的距離計算測量方法把數據高效地劃分成為多個不完全重疊但可以相交的區域，這個算法獲得的並不是最終結果，它是為其他算法服務的，例如k-means，可以提高大規模數據處理效率。

canopy基本思想

canopy聚類結果

如圖所示，定義了T1，T2，稱為距離閾值（T1>T2），當確定了一箇中心點以後，計算其它點與該中心點的距離，並根據距離閾值T1，T2分別將其它點歸入各自的canopy聚類區域，將該區域分為小於T2的區域（以該點為聚類中心的聚類區域，不可能再產生其它類的聚類中心），大於T2小於T1的區域（已該點為聚類中心的聚類區域，可能會產生其它類的聚類中心），大於T1的區域（不屬於該聚類中心的聚類區域）

算法步驟如下：

1. 將所有數據放在數據對象集合D中；

2. 隨機選擇D中的一個數據對象d作為canopy的中心，並將d從D中移除;

3. 計算數據集合D中所有數據對象到該對象d的距離distance;

4. 若distance

5. 若distance

6.重複步驟2到5，直到D為空，形成多個canopy類（如上圖3所示）。

canopy+kmeans

canopy根據數據對象之間的距離粗略計算出整個區域的類別劃分，產生了n個聚類中心及其聚類區域，可以消除孤立點的影響，這剛好彌補了kmeans初始聚類數目難以選擇及隨機選取聚類中心易陷入局部最優的不足。且在數據量較大時，可以通過僅比較各數據點與最近的聚類中心點的距離來減少距離比較次數，從而減少聚類時間。

算法分為兩步：

step1：在數據集中使用 canopy 算法將數據對象劃分成 k 個 canopy，產生k 個 canopy 的中心點作為 k-means 算法的初始聚類中心；

step2：在 canopy 中使用k-means 算法計算數據對象與聚類中心距離重新劃分聚類及確定新的聚類中心。

另：引入canopy帶來了另一個影響因子：T1和T2的選擇，當T1過大時，可能會產生過多重疊的canopy，使各聚類的中心點距離過近；當T2過大時，會減少簇的個數，反則，則增加簇的個數。

關於選擇閾值的方法，最簡單的是根據經驗設置，或者複雜一點使用交叉驗證法，更多高級算法留給大牛們討論和設計吧。

閱讀更多 AI賦能 的文章

關鍵字: 數據結構 物以類聚 設計