HackMD
tags: clusting
分群演算法
硬切割
切割式分群(partitional clustering)
無監督式
k-means
- 無監督式
- 最終會將資料分成k群，各個群取中心(mean)
- 隨機產生k個點，分成k群->可組k維空間
- pros
- 計算快
- 低複雜度 -> 可處理大量資料
- cons
- 如果有outliers -> 影響群心精準度
- 無法處理密度、大小不同的點
- 不同群心的初始值可能會有不同的結果
- 用群心做分類，看哪一個點比較靠近哪個群心就分為同一類，分完後再重複上述步驟，直到群心的變化不大就停止。
Partitioning around medoids(k-medoids)
- 改良k-means -> 不取平均值
- 隨機取k個中心點
- 計算點與中心的距離哪一個最短，並將所有點分類到各個中心
- 計算準則函數最小的點作為中心點
準則函数 : 那一團中所有點到該中心點的最小距離和
軟切割(fuzzy)
無監督式
fuzzy clusting
和k-means的原理很像，但是這裡有重疊M>2
- 透過次方確認軟切割M = ? -> 公式
- 切割式演算法使用次數占最多(因為計算低，低複雜度)，重疊分群占次要
階層式分群(hierarchical clustering)
-
樹狀圖(dendragram)由樹結構(tree struct)組成 -> 可表示分層
-
如何判斷距離
- 最小距離，單鏈接Single Linkage
- 最大距離，全連結Complete Linkage
- 平均距離，均連結Average Linkage
-
計算量非常大
-
聚合(由下而上)
- 將相似的放在一起(形狀、特徵…)
- 距離相近的放在一起(圓圈、直線..)
-
分裂(由上而下)
- 切割相似度最低、距離最遠的
- 2種假設
- 如果該點在群內 -> 點跟群的距離 = 群的每個資料點的距離的平均值。
- 如果點在群內 -> 點和群的距離 = 群裡的其他各個資料點的距離的平均值。
-
pros
- 可用樹狀圖代表
- 可以分不同種類、大小、密度
-
cons
- 高複雜度
- 計算慢
- 如果被分為一群就沒辦法調整內容
- 每一個點視為合集，兩兩相近的再併起來
Model-Based 模型導向分群法
- 基於已知環境或模型找出最佳解 -> 白盒
- 測量不確定性&概率 -> 自動檢測最佳的合集
- 可考量到雜訊或是極值
- 找出資料和數學模型之間的最佳解
- 無監督式
- 透過競爭學習(輸出)，訓練權重係數後，自動得出各分群的中心不須事先指定分群數目->找出最佳答案
- 容錯率高 -> 可用於資料多時
- 用視覺化呈現
- 會將高維度降維，但是又保留原本的資料
- 將資料集輸入後，選擇一個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)
- 監督式學習
