###### tags: `clusting`
# [分群演算法](https://ithelp.ithome.com.tw/articles/10193760)

- [資料分群簡介](https://www.jamleecute.com/partitional-clustering-kmeans-kmedoid/)
- [R筆記–(9)分群分析(Clustering)](https://rpubs.com/skydome20/R-Note9-Clustering)
- [分群法](https://sites.google.com/site/thesisdata2011/clustering-1)
## 硬切割
### 切割式分群(partitional clustering)
#### 無監督式
==k-means==
- 無監督式
- 最終會將資料分成k群，各個群取中心(mean)
- 隨機產生k個點，分成k群->可組k維空間
- pros
- 計算快
- 低複雜度 -> 可處理大量資料
- cons
- 如果有outliers -> 影響群心精準度
- 無法處理密度、大小不同的點
- 不同群心的初始值可能會有不同的結果
+ 用群心做分類，看哪一個點比較靠近哪個群心就分為同一類，分完後再重複上述步驟，直到群心的變化不大就停止。

==Partitioning around medoids(k-medoids)==
- 改良k-means -> 不取平均值
1. 隨機取k個中心點
2. 計算點與中心的距離哪一個最短，並將所有點分類到各個中心
3. 計算準則函數最小的點作為中心點
>準則函数 : 那一團中所有點到該中心點的最小距離和

***
## 軟切割(fuzzy)
#### 無監督式
==fuzzy clusting==
和k-means的原理很像，但是這裡有重疊M>2
- 透過次方確認軟切割M = ? -> 公式
- 切割式演算法使用次數占最多(因為計算低，低複雜度)，重疊分群占次要
***

### 階層式分群(hierarchical clustering)
==[Hierarchial clustering](https://medium.com/ai-academy-taiwan/clustering-method-4-ed927a5b4377)==

- 樹狀圖(dendragram)由樹結構(tree struct)組成 -> 可表示分層
- 如何判斷距離
- 最小距離，單鏈接Single Linkage
- 最大距離，全連結Complete Linkage
- 平均距離，均連結Average Linkage
- 計算量非常大
- 聚合(由下而上)
- 將相似的放在一起(形狀、特徵...)
- 距離相近的放在一起(圓圈、直線..)
- 分裂(由上而下)
- 切割相似度最低、距離最遠的
- 2種假設
- 如果該點在群內 -> 點跟群的距離 = 群的每個資料點的距離的平均值。
- 如果點在群內 -> 點和群的距離 = 群裡的其他各個資料點的距離的平均值。
- 

- pros
- 可用樹狀圖代表
- 可以分不同種類、大小、密度
- cons
- 高複雜度
- 計算慢
- 如果被分為一群就沒辦法調整內容
+ 每一個點視為合集，兩兩相近的再併起來

==Model-Based 模型導向分群法==
- 基於已知環境或模型找出最佳解 -> 白盒
- 測量不確定性&概率 -> 自動檢測最佳的合集
- 可考量到雜訊或是極值
- 找出資料和數學模型之間的最佳解

***

==[self-organizing Map 自組織映射圖](https://blog.xuite.net/metafun/life/509048033)==
- 無監督式
- 透過**競爭學習**(輸出)，訓練權重係數後，自動得出各分群的中心不須事先指定分群數目->找出最佳答案
- 容錯率高 -> 可用於資料多時
- 用視覺化呈現
- 會將高維度降維，但是又保留原本的資料

+ 將資料集輸入後，選擇一個pattern，將資料投射到到2維空間後，用權重計算差距量，差距量最小為最佳解。以最佳解為中心找鄰近有沒有更好的

***

==Density Based Clustering (DBSCAN)==
- 無法設定要分幾個群
+ 先設定半徑多長畫一個圓，在從範圍內找出有幾個點，範圍內的點再延伸，把範圍內的點變成一個合集

***
## 開發搜尋 search developed
### 粒子群最佳化（Particle Swarm Optimization, PSO）
- 從每一個粒子(群心?)找附近最近的點
- 初始化一群微粒子(位置、速度)，在那個範圍內用權重打分數
### 人工蜂群演算法(Artificial Bee Colony, ABC)
### 蟻群演算法（Ant Colony Optimization, ACO）
### 人工魚群演算法 （Artificial Fish-Swarm Algorithm，AFSA）
- 混合不同的計算
***
## 比較技術 comparative techniques
### 差分進化演算法（Differential Evolution）
### 支撐向量機(support vector machine, SVM)
### 最大期望演算法（Expectation-maximization algorithm,EM)
### 人形模型( Gustafson–Kessel,GK)
### 和聲搜索（Harmony Search, HS）
### K-近鄰演算法(K-Nearest Neighbors,KNN)
- 監督式學習