# Course 15 -- Clustering Algorithm

## Clustering algorithm

主要目的就是給所有資料找到其屬於之聚集，重點為聚集個數 k 的值。

而在實作此演算法可以拆分為 2 個子問題:
1. 如果每個 class 的中心點已知，就可以把 observation 分類給最接近 class 的中心點
2. 如果所有 cluster 的 observation 為已知，這也代表我們可以找到 cluster 的中心點

上方值為未知時，我們必須透過 distance function 來找尋哪個點當 centroid 時，
每點 sample 與之的距離總和為最小值，若為最小值，當時 centroid 即為 class 之中心點


但要找到最佳解十分耗時，其問題屬於 NP Hard，
所以透過 heuristic algorithm 來解，其中一個就是 k-means

## k-means

我先前會把 k-nn 和 k-means 混淆，以下講述差異，
其實除了本身名字都有 k ，以及透過 k 的數目來對演算法做操作，其餘皆沒共通點。

### [k-nn](https://zh.wikipedia.org/zh-tw/K-%E8%BF%91%E9%82%BB%E7%AE%97%E6%B3%95)
又稱最近鄰居法，主要是透過新增點附近 k 個已標記點來判斷此為標記點之分類，
而 k 點中最多出現類別即為此為標記點之所屬類別，此演算法屬於==監督式學習==。

### [k-menas](https://zh.wikipedia.org/wiki/K-%E5%B9%B3%E5%9D%87%E7%AE%97%E6%B3%95)
此方法是透過已知 sample 當作點，分別給 sample 的每個點當作 centroid，
並計算說每點介於 centroid 的總距離，再從所有計算出距離的總合裡，
找尋最小總和值，此時 centroid 的點為 cluster 中的中點。
而 k-menas 中的 k 代表要劃分為 k 類 cluster，總點數為 n，k 跟 n 的關係為，k <= n。
此演算法由於原先資料為偽標記過，所以為==非監督式學習==。

### Some questions

1. k 值從何而來 ?
使用 ISODATA(Iterative SelfOrganizing Data Analysis Technique)，
此演算法可以動態找尋適合 k 值，不過此演算法需要多一個參數來決定 k 值。
2. 如何有效找尋 centroid ?
應用幾何知識，盡可能避免計算點中心距離。Elkan的演算法利用三角形不等式來避免許多失調計算，並且是當前最快的高維數據演算法。‎
3. 如何處理 empty cluster ?
降低 k 值，然後初始化 k-means algo.，再跑一次。

## Density-based approach

投影片後面介紹了 HDBSCAN 這個 Density-based approach cluster algorithm


而藉由取得 density landscape，觀察山峰最高點進行分類，
每點的分布以及界定類別的 threshold 高度慎關重要。

## Conclusion

總結來說，Clustering algorithm 對於資料維度敏感，
此算法不適用於高維資料集，而再執行算法前初始透過
[feature selection](https://ithelp.ithome.com.tw/articles/10245037) 去降低資料維度
對於 clustering algorithm 來說十分重要