Canopy在劃分聚類算法中對K選取的優化

王海燕, 崔文超, 許佩迪, 李 闖

(1.長春大學 計算機科學技術學院, 長春 130022； 2.吉林師范大學 計算機學院, 吉林 四平 136000)

Canopy算法是一種簡單、快速、準確的對象聚類方法[1], 可應用于Hadoop平臺[2].該算法可將所有對象都表示為多維特征空間中的一個點, 采用快速近似距離度量和兩個距離閾值比較方式, 實現快速粗聚類.聚類算法[3]應用廣泛, 目前對聚類算法的效率與準確度的研究已有許多結果[4-5].但當數據變大時, 聚類難度也加大.數據變大有多種情況： 數據條目多, 則整個數據集包含的樣本數據向量多； 樣本數據向量維度大, 包含多個屬性； 要聚類的中心向量多等.當所應用聚類算法的數據遇到上述情況時, 聚類K值的取值準確性便尤為重要.在劃分聚類算法中, 準確的K值可有效提高聚類工作的效率.Canopy算法將數據劃分成可重疊的子集, 通過快速近似比對處理, 可為K均值聚類提供K值的預判.本文通過對Canopy算法進行優化, 可更好地實現在劃分聚類算法中聚類數K的預判, 減少試探取值的工作量, 從而減少聚類工作時間, 提高工作效率.

1 傳統Canopy算法

圖1 Canopy算法流程Fig.1 Flow chart of Canopy algorithm

Canopy算法的主要思想是把聚類分為兩個過程[6]： 首先通過使用一個簡單、快捷的距離計算方法將數據分為可重疊的子集, 每個子集是一個“Canopy”； 然后通過使用一個精準、嚴密的距離計算方法計算出現階段中同一個Canopy的所有向量的距離.這種聚類方法使用了兩種距離參與計算, 由于只計算了重疊部分的數據向量, 因此可達到減少計算量的目的.

Canopy算法的優勢主要表現在兩方面： 1) 通過粗略距離計算把數據劃入不同可重疊子集中； 2) 只計算在同一重疊子集中的樣本數據向量, 減少了需要距離計算的樣本數量.Canopy算法流程如圖1所示.由圖1可見, 需要從List中隨機取點, 因此存在噪聲點和孤立點.此外, 算法還需要距離閾值T1,T2參與運算, 因此獲取一個適合當前List的閾值是優化的關鍵.

2 Canopy算法優化

2.1 方法描述

針對Canopy算法在聚類數K值預判過程中的缺陷, 將優化重點放在選取特殊的聚類中心點和獲取閾值T1,T2上.下面根據Python語言實現Canopy算法的優化.

1) 將距離數據均值點最近點作為聚類中心點, 可盡量消除噪聲點和孤立點對聚類效果的影響, 并消除隨機取點對聚類數K的影響.

2) 優化閾值獲取方式.由于原始閾值T1,T2是通過任意取值得到的, 因此通過優化閾值選取方式, 可減少閾值選擇的盲目性.閾值獲取方式有多種: 一是通過計算數據點到均值點的最遠距離L1和最近距離L2確定T1和T2； 二是通過Canopy列表、移除列表中的元素個數、移除率(刪除列表元素個數/Canopy列表元素個數)和聚類效果圖調整T2的大小.若前幾次聚類的移除率太小, 則增大T2； 若移除列表和Canopy列表中的數據點個數小于總數據集個數的5%且增大T2值后聚類效果更佳, 則增大T2； 最后, 根據聚類效果圖得出T2的最終值并參與實驗, 得出合適的聚類數K.優化Canopy算法實現了準確預判聚類的個數.

2.2 Canopy+算法

Canopy+算法主要從閾值獲取方式和初始聚類中心的選取兩方面進行優化.閾值T1,T2的獲?。?通過遍歷所有數據, 取所有數據點的均值點, 計算均值點到所有數據點的距離, 最遠距離記作L1, 最近距離記作L2, 并將L1-L2賦值給T1, 將L1/2賦值給T2； 初始聚類中心通過選取與均值點最近的點得到.兩方面的優化使預判出的聚類數K更準確.在閾值T1,T2獲取過程中,T2是不斷修訂的, 本文需將刪除率控制在一定范圍內.刪除率過大說明T2過大, 刪除率過小說明T2較小.

Canopy+算法步驟如下：

1) 計算List原始數據的均值點, 將距離均值點的最遠距離記作L1, 最近距離記作L2, 并將L1-L2賦值給T1， 將L1/2賦值給T2；

2) 取距離均值點最近點作為算法的聚類中心, 計算該中心與其他樣本數據向量之間的距離d；

3) 將距離d

4) 根據聚類效果圖、移除率和Canopy列表、移除列表中的元素個數再次調整閾值T2；

5) 重復步驟2)和3), 直到候選中心向量名單為空, 即List為空, 算法結束.

3 實驗測試

3.1 數據集獲取

本文以2DIris數據集和New-thyroid數據集為例進行Canopy算法和Canopy+算法的對比實驗.Iris和New-thyroid數據集都是UCI標準數據庫[7]中的數據集, UCI是一個常用的標準測試數據集庫, 可用于機器學習, 該數據庫目前有335個數據集.3種數據集信息列于表1.

表1 數據集信息

2DIris數據集的可視化界面如圖2所示.由圖2可見, 數據集聚類類別較明顯, 聚類后結果與實際分類結果相符.圖3是New-thyroid數據集進行主成分分析(PCA)降維[8]后的二維效果圖, 通過實驗分析, New-thyroid數據集的二維聚類效果與原數據聚類結果一致.

圖2 2DIris數據集可視化結果Fig.2 Visualization results of 2DIris data set

圖3 New-thyroid數據集可視化結果Fig.3 Visualization results of New-thyroid data set

3.2 2DIris的聚類數預判過程

通過優化方法計算2DIris數據集的初始閾值T1,T2及其他數據.通過Canopy+算法計算得到T1,T2的初始值分別為3.22和1.6, 通過閾值T1,T2得到的聚類移除率分別為0.425,0.97,1, 對應每個移除列表的元素個數分別是63,34,49, 每個Canopy的元素個數分別為148,35,49, 數據集的聚類個數為3.由于移除率不足以改變T2, 因此閾值T1,T2的終止值不變, 實驗結果如圖4所示.由圖4可見, Canopy+算法對2DIris的聚類界限明顯, 可見效果較好, 聚類個數與實際類別個數一致, 聚類效果與其實際分類效果相符.使用優化過程中計算的T1,T2對Canopy算法進行實驗, 結果如圖5所示.與圖4相比, Canopy算法的聚類邊界不清楚, 聚類效果不理想, 且聚類數K易出現誤差.

圖4 Canopy+對2DIris數據集的效果Fig.4 Effect of Canopy+ on 2DIris data set

圖5 Canopy對2DIris數據集的效果Fig.5 Effect of Canopy on 2DIris data set

3.3 New-thyroid數據集的聚類數預判過程

優化方法計算New-thyroid數據集得出的初始閾值T1,T2及其他數據信息列于表2.初始的閾值T2對實驗結果有影響, 且移除率滿足調整T2的條件, 因此需要重新設置.當T2=25時, 存在2個Canopy列表的元素個數小于數據集元素個數的5%, 故增大T2的值； 當T2=30時, 存在其中1個Canopy列表只有2個元素, 繼續增大T2； 當T2=35時, 聚類個數發生了變化, 但仍存在2個Canopy列表的元素個數過少, 繼續增大T2值; 當T2=40時, 聚類個數停止改變, 并根據聚類的效果圖得出這兩個聚類不能因為T2的增大而忽略.因此, 通過效果圖再次調整T2的大小得到最終值, 聚類效果如圖6所示.

表2 New-thyroid數據集的實驗數據

將最終的T1,T2應用于Canopy算法得到的效果如圖7所示.由圖7可見, 圖6中聚類界限分明, 聚類數預判穩定; 而Canopy算法聚類效果與Canopy+算法的聚類效果相比, 聚類界限模糊, 在聚類個數預判上只能取近似值.因此, Canopy+算法的聚類更理想, 聚類個數的預判更準確.

圖6 Canopy+對New-thyroid數據集的效果Fig.6 Effect of Canopy+ on New-thyroid data set

圖7 Canopy對New-thyroid數據集的效果Fig.7 Effect of Canopy on New-thyroid data set

4 Canopy+算法對K值預判的應用

4.1 數據集選擇及處理

應用UCI數據庫中的Seeds數據集, Seeds數據集包含210條數據, 共有7個屬性, 分別是area A,perimeter P,compactness C,length of kernel,width of kernel, asymmetry coefficient,length of kernel groove.為更好實現數據的可視化, 在不影響數據聚類效果的前提下, 通過PCA技術進行多維數據降維操作, 降維后的二維數據點如圖8所示.

4.2 Canopy+算法實現K值預判

圖8 Seeds數據點Fig.8 Data points of Seeds

圖9 最終實驗效果Fig.9 Final experimental effect

選取距離中心點最近點作為初始點, 計算得出閾值T1, 根據T1估算閾值T2的大小, 再根據移除率、移除列表元素個數、Canopy列表元素個數和聚類效果圖, 最終確定閾值T2的值及聚類個數K的值, 其數據信息列于表3.本文根據表3數據進行實驗, 其最終效果如圖9所示.由圖9可見, 聚類數為3時的聚類效果較理想.

表3 Seeds實驗數據信息

綜上所述, 本文在Canopy算法基礎上進行優化, 提出了一種Canopy+算法, 實現了對劃分聚類算法[9]聚類數K的預判.Canopy+算法通過距離、刪除率等參數進行閾值T1,T2的設定, 并不斷調整, 直到確定閾值, 進一步對聚類個數進行預判.實驗結果表明, Canopy+算法預判出了準確的聚類個數, 減少了試探取值的個數, 進而降低了聚類工作量, 減少了聚類工作的時間, 提高了工作效率.