Leader聚類算法解釋

Question

我想了解這個算法，但無法獲得適當的文檔和解釋。有人可以幫助我理解這種聚類算法。

Answer 1

發佈答案，以便對他人有幫助。

Leader算法是一種通常用於聚類大型數據集的增量聚類算法。該算法是依賴於順序的，並且可以基於數據集提供給算法的順序形成不同的聚類。該算法由以下步驟組成。

步驟1：將第一個數據項P1分配給C1。該數據集將成爲集羣C1的領導者。

第2步：現在移動到下一個數據項說P2，並計算它與領導P1的距離。如果P2和引導者P1之間的距離小於用戶指定的閾值（t），則將數據點P2分配給該聚類（聚類C1）。如果引導者P1和數據項P2之間的距離大於用戶指定的閾值t，則形成新的聚類C2並將P2分配給該新聚類。 P2將成爲集羣C2的領導者。

第3步：對於所有剩餘的數據項，計算數據點與聚類引導者之間的距離。如果數據項與任何領導者之間的距離小於用戶指定的閾值，則將數據點分配給該羣集。但是，如果數據點與任何羣集領導之間的距離大於用戶指定的閾值，則會創建一個新羣集，並將該特定數據點分配給該羣集，並將其視爲羣集的領導。

步驟4：重複步驟3，直到所有數據項都被分配給簇。

舉例說明理論。

考慮圖案位於

A (1, 1),B(1, 2), C(2, 2), D(6, 2), E(7, 2), F(6, 6), G(7, 6) 

讓數據的順序A, B, C, D, E, F and G進行處理，並且用戶指定的閾值T是3。 A(1, 1)是處理的第一個數據項，它被分配到集羣C1並且也成爲C1的領導者。

對於第二點B，計算其與領導者A的距離。 使用歐氏距離式（Distance(a, b)) = √(x - a)² + (y - b)²），我們得到作爲√(1 - 1)² + (1 - 2)² = 1的距離，這是小於用戶指定的閾值3，所以B被分配給該羣集1.

對於第三點C(2, 2)的前導A(1, 1)之間的距離計算集羣C1和點數C。使用歐幾里得公式，距離爲√(1 - 2)² + (1 - 2)² = 1.41，小於 閾值，所以C也被分配到C1。 A與D之間的距離（√（1-6）2 +（1-2）= 5.099）大於用戶指定的閾值3，因此創建了一個新簇並將D分配給簇C2。 D是這個集羣的領導者。

對於點E，從A（的C1前導）和D（的C2前導）的距離被計算。由於Distance(D,E)是小於用戶指定的閾值3，它被分配到簇2.

的F從A的距離（C1的領導者）是7.07和從D（C2的領導者）是4。 這兩個距離都高於閾值，因此F被放入新羣集C3中，併成爲該羣集的領導者。 對於G，Distance(A,G),Distance(D,G)和Distance(F,G)分別是7.81，6.41和1。由於Distance(F,G)是小於用戶指定3它被分配到簇3.

可以看出，如果數據已經以不同的順序被處理，則簇 領袖會有所不同，甚至簇可以變化。如果C發生在 A和B之前，那麼C將是C1的領導者。如果D之前發生並且和D之間的距離小於閾值，則它將在C1之內。如果A是領導者，則此 可能不會發生。領導者算法因此是依賴於順序的，並且可以基於處理順序給出不同的結果。