一、分群演算法概述

分群演算法在機器學習中扮演的角色，前一篇文章有清楚的介紹了。以下稍微說明一下其應用情境:

1. 文件分群: 早期新聞文章在分類時，可能不太清楚應該分成哪一些類別，因此可以透過其出現過那些文字作為特徵值，進行分群，分出來之後，透過人工去判斷，某一個群組比較像社會類，另一個群組比較像娛樂類。
2. 市場區隔: 商學院裡面有一門應用式用來做市場區隔，舉例來說，假設你有一個產品，你希望跟你的競爭對手做出區別，你可能可以先透過產品的各項特徵值進行分群之後。
3. 生物分類: 界、門、綱、目、科、屬、種

二、分群演算法介紹

(一)、K-means:

簡介

K-means演算法其實算是分群中最簡單也最常被使用的演算法之一，他的原理如下圖(取自stack overflow):

1. 設定重心: 決定要分幾個群，下圖決定分成三群，所以初始重心有三個，這三個點是隨機產生的
2. 分群: 找到分別最靠近這三個點的所有資料點，並做第一個迴圈的分群
3. 尋找重心: 分完群之後，計算所有資料點的重心(element-wise的平均)，做為下一個迴圈的分群標準
   ....
4. 停止: 重複上述方法，只到不會有資料點因為重新尋找重心而改變群組
   

設定參數

特性

1. 一開始需要決定要分成幾個群

(二)、Hierarchical Clustering

簡介

hierarchical的分群方法，步驟簡述如下，可參考下圖(取自維基百科):

1. 把每一個點當作一個群組
2. 透過掃描過整個資料及尋找出最近的兩個群組，並把這兩個點榜再一起變成一個群組
3. 尋找下一個最近的的兩個群組，再綁再一起變成一個群組
4. ....
5. 停止: 直到所有資料都被分成一群，或是透過設定參數到分到幾個群時自動停止
   

參數設定

註解:

• ward(single): 兩個群中最近的點。
• complete: 兩個群中最遠的點。
• average:兩個群的重心。

特性

1. 比較耗效能: 因為有100萬筆資料，就要跑100萬次迴圈，每一次迴圈都要掃描過每一筆資料，才能跑完。
2. 很適合用來做生物分類，因為它可以完整畫出分類樹狀圖。

from scipy.cluster.hierarchy import dendrogram, linkage, set_link_color_palette
Z = linkage(X[:20], 'single')  # X: 資料在下面的示範中會有
plt.figure()
dn = dendrogram(Z)
plt.show() 

(三)、 Density Based Clustering (DBSCAN)

簡介

顧名思義，這種分群演算法計算的是密度，透過設定多長的半徑內，有出現幾個點，不斷延伸，延伸到無法延伸，所有出現在前面延伸範圍的點分成一個群組，請見下圖(取自stackexchange)。

參數設定

特性

1. 常常用來偵測Noisy Data。
2. 無法設定要分成幾個群。

明天將與大家分享實作上使用的code。