天天看點

weka算法系列(cluster)——Canopy(1)

本文主要介紹weka的cluster工具集中的Canopy算法,包括算法原理、算法的應用場景以及算法對輸入資料的要求等内容。

文章目錄

      • 算法簡介
      • 算法原理
          • 1.一圖知大意
          • 2.算法流程
          • 3.算法僞代碼
          • 4.Python利用hadoop實作Canopy算法
      • 應用場景
      • 對資料的要求
      • weka使用方法
      • 參考文獻

算法簡介

  Canopy算法是一種比較經典的聚類算法,可稱為

粗聚類

,它的輸出并不是最重要的結果,而是為其他精确算法服務的。它

不需要事先确定如k-means方法所需的聚類中心個數,并可以粗略地估計出聚類中心的個數之後再采用k-means算法

,能有效降低k-means等精确聚類算法的計算複雜度。

  目前Canopy算法在mahout大資料機器學習工具中應用較多,能與hadoop結合産生非常好的計算效果。(其

近似計算以降低算力需求

的思想非常适合大資料分析算法。)

算法原理

1.一圖知大意
weka算法系列(cluster)——Canopy(1)

圖檔來源:http://picksesame.blogspot.com/2011/05/canopy-clustering.html

  如上圖,Canopy算法有兩個門檻值T1和T2,算法的核心就是對大于T1、大于T2且小于T1、小于T2三種門檻值範圍内的instance(執行個體點)采用不同的處理方式。具體算法流程見下一節。

2.算法流程

當執行個體集 D D D非空時:

  從 D D D中選擇元素 d d d作為canopy c c c;

  從 D D D中移除元素 d d d;

  對 D D D中除元素 d d d以外的其它元素進行周遊:

    如果 d i d_i di​與 c c c之間的距離 &lt; T 1 &lt;T_1 <T1​,則将 d i d_i di​加入canopy c c c的集合;(*1)

    如果 d i d_i di​與 c c c之間的距離 &lt; T 2 &lt;T_2 <T2​,則從 D D D中移除目前元素 d i d_i di​;(*2)

  結束周遊。

  将目前的canopy c c c對應的集合存儲到清單 C C C中;

算法結束。

1.關鍵之處在于(*1)和(*2)兩個步驟。參照上一節中的示意圖可知,這種處理方式相當于設定了一個

距離的緩沖區

,即處于 T 1 T_1 T1​和 T 2 T_2 T2​之間的這部分執行個體在每一次聚類中并不是嚴格的屬于該類,還要參與下一次聚類;隻有當小于 T 2 T_2 T2​(嚴格屬于該類)時,才從 D D D中删除,不參與下一次聚類。這樣的處理方式更穩妥。
2. T 1 T_1 T1​和 T 2 T_2 T2​的值通過交叉檢驗确定,如下圖。
from Old_regression import crossValidation
#使用K均值
import kMeans as km
def canopyClustering(datalist):
   state =[];
   #交叉驗證擷取T1和T2;
   T1,T2 = crossValidation(datalist);
   #canopy 預聚類
   canopybins= canopy(datalist, T1 , T2);
   #使用K均值聚類
   k =len(canopybins);
   createCent = [canopy[0] for canopy in canopybins];#擷取canopybins中心
           
代碼參考:Canopy聚類算法分析
3.要注意,最終聚類得到的各個類别中,并不會存在交叉重疊,因為隻要 D D D中存在執行個體元素時,聚類算法就不會停止,算法會循環直至每個元素都嚴格屬于各自的聚類。參考文獻1中關于這一點的分析時不正确的,要注意!
3.算法僞代碼
while D is not empty
      select element d from D to initialize canopy c
      remove d from D
      Loop through remaining elements in D:
           if distance between d_i and c < T1 : add element to the canopy c
           if distance between d_i and c < T2 : remove element from D
      end
      add canopy c to the list of canopies C
end
           
4.Python利用hadoop實作Canopy算法

  參考文獻2中基于Python與hadoop的mapreduce實作了Canopy算法的并行計算,在後續文章中逐一進行解讀。

應用場景

  主要用于正式聚類之前的粗聚類,确定大緻的分類數目。這種思想尤其适用于大資料分析領域。

對資料的要求

  下圖是Canopy算法的能力描述,可以看出:資料集的屬性可以是binary二進制屬性(如flag值為0或1)、空标簽屬性、缺失值、标簽屬性、數值屬性以及一進制(unary)屬性。

當不是數值屬性時,可計算執行個體之間的相似性來表示執行個體之間的距離。比如漢明距離、餘弦相似度等
weka算法系列(cluster)——Canopy(1)
  interface欄用于修改源碼時了解其繼承關系。additional欄表示該算法的附加限制是“某類别的最小執行個體數目”必須大于0。

weka使用方法

  1. 參數介紹
    weka算法系列(cluster)——Canopy(1)

比較重要的有如下參數:

t 2 t_2 t2​:對應算法中的門檻值下限 t 2 t_2 t2​,如果<0表示在批訓練時基于屬性值進行啟發式設定(如交叉驗證尋找最佳 t 2 t_2 t2​)。

t 1 t_1 t1​:對應算法中的門檻值下限 t 1 t_1 t1​,如果<0則被視為 t 2 t_2 t2​乘以一個正的常數(即如果 t 1 = − 0.25 t_1=-0.25 t1​=−0.25,則 t 1 = t 2 ∗ 0.25 t_1=t_2*0.25 t1​=t2​∗0.25)。

n u m C l u s t e r s numClusters numClusters:設定類别個數,如果為-1表示根據 t 2 t_2 t2​的距離決定合适的聚類數目。

m i n i m u m C a n o p y D e n s i t y minimumCanopyDensity minimumCanopyDensity:用于算法優化的參數。當某個canopy中 t 2 t_2 t2​距離内的執行個體數目小于該參數時,将該canopy進行剪枝。

p e r i o d P r u n i n g R a t e periodPruningRate periodPruningRate:用于算法優化的參數。表示訓練模型時以多大頻率對低于最低密度的聚類進行剪枝。

其實weka中囊括的Canopy算法已經包括了調優等内容,比較完善了。剪枝參數等與決策樹中的調優類似。
  1. 使用示例
  • 導入資料

      選擇weka中/data目錄下自帶的示例資料集iris.arff資料集,并移除class屬性(聚類屬于無監督學習,不需要标簽)。

    weka算法系列(cluster)——Canopy(1)
  • 設定算法參數

      此處選擇Cluster菜單下的Canopy算法,由下圖可以看出:

    (1)minimumCanopyDensity參數設定為負數、periodPruningRate設定一個較大的值,表示并未采用剪枝等tuning政策;

    (2)maxCandidateCanopiesToHoldInMemory參數設定為100,基本跟沒設定一樣,因為一般的Canopies達不到這個數目,這個參數是為特殊情況下終止算法而設定的。

    weka算法系列(cluster)——Canopy(1)
  • 選擇訓練-測試方法

      這裡采用80%的資料作為訓練集,20%的資料用于測試。

    weka算法系列(cluster)——Canopy(1)
  • 結果分析
    • 标記1、2、3是模型在整個訓練集上的訓練結果:

      (1)标記1的 t 1 t_1 t1​和 t 2 t_2 t2​是訓練集兩個最終門檻值

      (2)标記2表示最終Canopies的數目是3,這和鸢尾花資料集中三類花是相符合的

      (3)标記3分别展示了三種類别對應的執行個體數目,可知cluster0、cluster1和cluster2對應的執行個體數分别為91、46、13。由于原資料集各标簽數目均為50,是以此處結果還是比較粗糙的,不過canopy的數目是正确的,正好可以用于k-means等精确聚類算法。

    • 标記4、5、6是在測試集上的輸出結果:

      (4)由于隻用80%資料訓練模型,導緻Canopies的數目為2,與在全部訓練集上訓練模型的數目(3個)不同。

      (5)标記7表示用80%資料所訓練的模型參數對剩餘20%資料進行分類所得到的分類結果。

      weka算法系列(cluster)——Canopy(1)
總結:從結果輸出來看,采用預設參數而不設定調優參數會導緻最終結果誤差較大。Canopy聚類算法确實可以為精确聚類所需的聚類中心數目提供參考(如在全部訓練集上訓練模型時得出found=3,即可以此作為其他精确聚類算法的初始參數)。

參考文獻

Canopy聚類算法(經典,看圖就明白)

Parallel Machine Learning for Hadoop/Mapreduce – A Python Example

繼續閱讀