Clara算法

CLARA(Clustering LARge Applications，大型套用中的聚類方法)(Kaufmann and Rousseeuw in 1990):不考慮整個數據集, 而是選擇數據的一小部分作為樣本.

基本介紹

• 中文名：Clara算法
• 外文名：Clustering LARge Applications
• 優點：可以處理的數據集比 PAM大
• 缺點：有效性依賴於樣本集的大小

算法簡介

CLARA(Clustering LARge Applications，大型套用中的聚類方法)(Kaufmann and Rousseeuw in 1990):不考慮整個數據集, 而是選擇數據的一小部分作為樣本.

算法步驟

它從數據集中抽取多個樣本集, 對每個樣本集使用PAM, 並以最好的聚類作為輸出
CLARA 算法的步驟:
(1) for 　i = 1 to v (選樣的次數) ,重複執行下列步驟( (2) ～ (4) ) :
(2) 隨機地從整個資料庫中抽取一個N(例如：(40 + 2 k))個對象的樣本,調用PAM方法從樣本中找出樣本的k個最優的中心點。
(3)將這k箇中心點套用到整個資料庫上， 對於每一個非代表對象Oj ,判斷它與從樣本中選出的哪個代表對象距離最近.
(4) 計算上一步中得到的聚類的總代價. 若該值小於當前的最小值,用該值替換當前的最小值,保留在這次選樣中得到的k個代表對象作為到目前為止得到的最好的代表對象的集合.
(5) 返回到步驟(1) ,開始下一個循環.
算法結束後，輸出最好的聚類結果

算法優缺點

優點: 可以處理的數據集比 PAM大
缺點:

1有效性依賴於樣本集的大小

2基於樣本的好的聚類並不一定是整個數據集的好的聚類, 樣本可能發生傾斜
例如, Oi是整個數據集上最佳的k箇中心點之一, 但它不包含在樣本中, CLARA將找不到最佳聚類