什麼是CURE演算法？

CURE代表“使用代表點的聚類”。它是一種聚類演算法，使用多種技術來構建一種能夠處理大型資料集、異常值以及具有非球形結構和非均勻大小的聚類的方法。CURE透過使用聚類中的幾個代表點來定義聚類。

這些點將捕捉聚類的幾何形狀和結構。第一個代表點被選擇為距離聚類中心最遠的點，而其餘的點則被選擇為距離所有先前選擇的點最遠的點。透過這種方法，代表點是關聯性地良好分佈的。選擇的多個點是一個引數，但發現10或更多個值執行良好。

由於選擇了代表點，因此它們會向中心收縮一個因子𝛼。這有助於緩和異常值的影響，異常值通常距離中心更遠，因此收縮幅度更大。例如，距離中心10個單位的代表點可以移動3個單位（對於𝛼 = 0.7），而距離中心1個單位的代表點可以移動0.3個單位。

CURE利用層次聚類過程的特定特性，在聚類階段的兩個多個點處去除異常值。首先，如果一個聚類增長緩慢，那麼這可能意味著它主要包含異常值，因為根據定義，異常值遠離其他值，並且不會經常與其他點合併。

在CURE中，這種第一個異常值消除過程通常出現在聚類數量為初始點數的1/3時。第二個異常值消除過程出現在多個聚類數量達到K（所需的多個聚類數量）的級別時。此時，會移除小聚類。

由於CURE的最壞情況複雜度為$\mathrm{O(m^2logm)}$，因此它不能精確地用於大型資料集。CURE使用兩種方法來加速聚類過程。第一種方法是獲取一個隨機樣本，並在樣本資料點上執行層次聚類。接下來進行最後一步，將資料集中每個剩餘點分配到一個聚類中，方法是選擇具有最近代表點的聚類。

在某些情況下，聚類所需的樣本量很大，需要第二種更高階的技術。在這種情況下，CURE將樣本資料進行分割槽，並在每個分割槽中對點進行聚類。此預聚類過程之後是中間聚類的聚類，以及最後一步，將資料集中每個點分配到一個聚類中。

Ginni

更新時間： 2022年2月14日

2K+ 瀏覽量

開啟你的職業生涯

透過完成課程獲得認證

立即開始