機器學習_學習筆記系列(90)：探索聚類分析(Cluster in Quest)
在前幾回當中，我們介紹有關density-based的clustering演算法，像是DBSCAN、HDBSCAN和OPTICS，而對於空間上的資料處理，學過數值分析FEM和FVM的朋友，相信看到這種演算法都一定會有一個直覺，就是那我們能不能以劃分網格的方法來做clustering？
答案是可以的！而這也是我們今天要來探討的新演算法「CLIQUE」。
Cluster in Quest
CLIQUE這個演算法其是由當時IBM研究團隊的Rakesh Agrawa、Johannes Gehrke、Dimitrios Gunopulos、Prabhakar Raghavan，論文名稱叫做
Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications
對於CLIQUE其為一種grid-based的clustering演算法，其做法非常直觀，假使我們今天拿到的資料有n筆資料、d個維度，我們在這裡會設定兩個參數
1. Interval ζ：代表我們數據點切割的區間數量，其就是對每個維度取最小和最大值，然後中間切割成ζ區間
2. Threshold τ：代表一個區間中能為dense unit的最低數量
我們可以看到這裡有一個詞叫做dense unit，其概念就是如果這個區間資料點的密集度夠大，也就是數量超過τ，代表他有可能為我們的cluster所以把這個區間標記為dense unit。
從上面這個圖，我們可以很明顯看到在不同的dimension我們把他分成好幾個區塊，而有顏色的區塊就是dense unit，而散落在沒有顏色區塊的點就視為noise。
所以我們可以看到原本paper的圖
如A和B兩個區域合併起來就是一個cluster，所以這樣的想法就其實和DBSCAN有點相似。
而對於演算法的步驟，一開始我們會對每個維度產生一維的dense unit，接著在像圖中一樣把兩個一維的dense unit對照，就可以得到二維的dense unit。然後我們又可以用二維的dense unit和另一組一維的dense unit比對，得到三維，所以就這樣依此類推，我們最後就可以得到d維的dense unit。
最後當我們拿到這些dense unit後我們再看他們網格相連的情況，就可以得到cluster，如上面那張圖，我們最後就得到3個clusters。
Example
接下來我們來看其在MNIST的表現。(P.S.因為運算速度非常慢所以我先把資料降到二維再做CLIQUE)
我們可以看到紫色差差的地方其就視為noise，而其他地方就可以看到有些cluster。
小結語：
這篇paper是由很多很厲害的科學家所寫的，可能他們想要把這個演算法寫得很嚴謹，所以利用了很多符號，但就造成讓人很難看得懂這篇文章想表達的意思，而且CLIQUE在我試驗過幾次後，其實效果真的蠻不好的，而且運算速度也很慢，所以非常少人用CLIQUE來做clustering，不過不可否認這篇paper的學術價值，其告訴了我們實際上clustering是可以用grid的方法來做。
Python Sample Code:
Github:
Reference:
[1] Agrawal, R., Gehrke, J., Gunopulos, D., & Raghavan, P. (1998, June). Automatic subspace clustering of high dimensional data for data mining applications. In Proceedings of the 1998 ACM SIGMOD international conference on Management of data (pp. 94–105).
