機器學習_學習筆記系列(91)：表徵聚類(Clustering Using Representatives)
OK在這個章節我們就繼續延續我們clustering的內容，而我們今天要來介紹的演算法為「CURE」
Clustering Using Representatives
對於CURE演算法，其是由Stanford和Bell Lab的Sudipto Guha、Rajeev Rastogi、Kyuseok Shim提出，論文名稱叫做
CURE: An Efficient Clustering Algorithm for Large Databases
而CURE，其是一個速度非常快的clustering演算法，所以適合用在大數據的處理。而且相較於k-mean演算法，對於outliers有更robust的特性，其演算法概念，是在k-mean和hierarchical clustering之間採用則中的概念，並且在處理大數據量的時候採用了取樣，分區的方法，來提高其效率。
對於CURE的出現最主要就是解決k-mean和hierarchical clustering的問題，回顧一下k-mean演算法，當我們在做clustering的時候，我們會給定圓心和半徑來組成cluster，但是顯然這樣的方法，如果我們數據的分布是不規則形狀，就會造成我們clustering的結果非常差。
在hierarchical clustering中，他最大的問題就是我們是利用計算點與點之間的距離來clustering，所以像是下圖中我們用人為就可以清楚判斷就是3個不同的cluster，但是有2個cluster靠非常近，所以計算上就會把他視為1個cluster。
而對於CURE演算法，其是使用一定數量且分散的點來夠成一個cluster，所以就可以解決k-mean和hierarchical clustering的問題。
Algorithms
對於CURE演算法，其整體演算法如下
我們可以看到對於CURE演算法其在一開始的時候會以KD Tree來儲存資料，而這邊的Heap我們會根據所有資料點互相的距離，由大到小排序。所以在進入while迴圈第一步的時候，我們是希望資料合併到最後，cluster總數量會等於我們所設定的數量。
所以進入迴圈，我們會從Heap裡面抽取距離最小的兩個點u和v合併成w，並把被合併的點，v從KD Tree和Heap裡面刪除。而因為我們現在把兩個點合併成w，所有點到w的質心距離也會跟著改變，所以for迴圈做的事情就是把我們全部的距離作調整。
而接下來我們就根據這樣的邏輯，每次把最小距離的兩個集合抽出、合併、刪除被合併的點，再更新我們所有集合質心互相的距離，直到達到我們所設定的cluster數量。
而對於CURE演算法最重要的就是merge這個function。我們可以看到一開始他會計算兩個集合合併後的質心位置，而接下來這裡for所做的事情就是，我們會從合併的集合w挑選c個點作為代表w集合的點。而在最後我們可以看到當我們得到c個代表點後，多加了一個參數α，其代表的就是對於質心的收縮程度。
而這裡會選擇c個代表點是因為，當我們數據量很龐大的時候，最後可能每個集合的資料數量都很大，所以我們這裡就用c個點，作為我們每個集合的代表點，就可以大大減少我們的運算時間。
Example
接下來我們來看MNIST的表現
P.S.
這裡我的作法是把目標設為48個cluster，因為可能有些cluster的數據點資料量很少，其就是所謂的noise。
我們可以看到其分類的效果也算不錯。
Python Sample Code:
Github:
Reference:
[1] Guha, S., Rastogi, R., & Shim, K. (1998). CURE: An efficient clustering algorithm for large databases. ACM Sigmod record, 27(2), 73–84.
[2] Novikov, A., 2019. PyClustering: Data Mining Library. Journal of Open Source Software, 4(36), p.1230. Available at: http://dx.doi.org/10.21105/joss.01230.
