iT邦幫忙

2018 iT 邦幫忙鐵人賽
DAY 24
0

一、分群演算法概述

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

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

二、分群演算法介紹

(一)、K-means:

簡介

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

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

設定參數

參數 意義
n_cluster 要分成幾個群
random_state 決定初始點的隨機seed

特性

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

(二)、Hierarchical Clustering

簡介

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

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

參數設定

參數 意義
linkage 如何衡量群與群之間的距離。(註解)
n_clusters 分成幾個群

註解:

  • 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() 

https://ithelp.ithome.com.tw/upload/images/20171226/20107576wP9YTiLnLi.png

(三)、 Density Based Clustering (DBSCAN)

簡介

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

參數設定

參數 意義
eps 半徑

特性

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

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


上一篇
機器學習系列概述
下一篇
分群演算法實作-區辨不同演算法的意義
系列文
玩轉資料與機器學習-以自然語言處理為例31

尚未有邦友留言

立即登入留言