本文主要介紹weka的cluster工具集中的Canopy算法,包括算法原理、算法的應用場景以及算法對輸入資料的要求等内容。
文章目錄
-
-
- 算法簡介
- 算法原理
-
-
- 1.一圖知大意
- 2.算法流程
- 3.算法僞代碼
- 4.Python利用hadoop實作Canopy算法
-
- 應用場景
- 對資料的要求
- weka使用方法
- 參考文獻
-
算法簡介
Canopy算法是一種比較經典的聚類算法,可稱為
粗聚類
,它的輸出并不是最重要的結果,而是為其他精确算法服務的。它
不需要事先确定如k-means方法所需的聚類中心個數,并可以粗略地估計出聚類中心的個數之後再采用k-means算法
,能有效降低k-means等精确聚類算法的計算複雜度。
目前Canopy算法在mahout大資料機器學習工具中應用較多,能與hadoop結合産生非常好的計算效果。(其
近似計算以降低算力需求
的思想非常适合大資料分析算法。)
算法原理
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之間的距離 < T 1 <T_1 <T1,則将 d i d_i di加入canopy c c c的集合;(*1)
如果 d i d_i di與 c c c之間的距離 < T 2 <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的值通過交叉檢驗确定,如下圖。代碼參考:Canopy聚類算法分析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中心
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)屬性。
當不是數值屬性時,可計算執行個體之間的相似性來表示執行個體之間的距離。比如漢明距離、餘弦相似度等 interface欄用于修改源碼時了解其繼承關系。additional欄表示該算法的附加限制是“某類别的最小執行個體數目”必須大于0。
weka使用方法
- 參數介紹
比較重要的有如下參數:
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算法已經包括了調優等内容,比較完善了。剪枝參數等與決策樹中的調優類似。
- 使用示例
-
導入資料
選擇weka中/data目錄下自帶的示例資料集iris.arff資料集,并移除class屬性(聚類屬于無監督學習,不需要标簽)。
-
設定算法參數
此處選擇Cluster菜單下的Canopy算法,由下圖可以看出:
(1)minimumCanopyDensity參數設定為負數、periodPruningRate設定一個較大的值,表示并未采用剪枝等tuning政策;
(2)maxCandidateCanopiesToHoldInMemory參數設定為100,基本跟沒設定一樣,因為一般的Canopies達不到這個數目,這個參數是為特殊情況下終止算法而設定的。
-
選擇訓練-測試方法
這裡采用80%的資料作為訓練集,20%的資料用于測試。
- 結果分析
-
标記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%資料進行分類所得到的分類結果。
-
總結:從結果輸出來看,采用預設參數而不設定調優參數會導緻最終結果誤差較大。Canopy聚類算法确實可以為精确聚類所需的聚類中心數目提供參考(如在全部訓練集上訓練模型時得出found=3,即可以此作為其他精确聚類算法的初始參數)。
參考文獻
Canopy聚類算法(經典,看圖就明白)
Parallel Machine Learning for Hadoop/Mapreduce – A Python Example