2014年7月13日

輕鬆聊之KNN演算法

今天來簡單介紹一下KNN演算法,全名叫K-nearest neighbors algorithm。KNN可以說是機器學習(Machine Learning)中最簡單的演算法,簡單到我連Sample Code都不想寫給你看(其實是懶),只要記住下面這五個字,「西瓜偎大邊」就可以完全了解這個演算法的奧義。

讓我們來想想一個情況,有一天晚上俊傑騎著機車正在回家的路上,不小心捲進了一群飆車族的械鬥,他環視了一下發現總共有三群飆車族,身上的衣服分別是黃、灰、紅。他已經在車陣之中,而且處境非常的危險,所以俊傑有兩條路可以選

  1. 不加入任何陣營,來一個打一個,以一擋百。

  2. 選擇加入某個陣營

基本上選了1就沒什麼好討論了,所以我們先假設他選2好了。俊傑本身就是個識時務的人,所以他看了一下離他最近的7個人(k=7),發現有黃色衣服的有4個,灰色有2個,紅色有一個,所以他當下立刻從包包來出一件黃色外套(不要問為什麼他剛好有黃色外套),加入黃色陣營,這就是所謂的「西瓜偎大邊」。從這個故事我們了解,俊傑本身應該是有學過KNN演算法的。

KNN屬於機器學習中的監督式學習(Supervised learning),不過一般來說監督式學習是透過資料訓練(training)出一個model,但是在KNN其實並沒有做training的動作。KNN一般用來做資料的分類,如果你已經有一群分好類別的資料,後來加進去點就可以透過KNN的方式指定新增加資料的分類。K表示一個常數,簡單的來說就是KNN就是看離你最近的K的點,然後看哪個類別的點最多就把自己也當成那個類別。你如果只看3個點,就是3NN囉。

下面這張圖,k=8所以周遭有6綠2紅,那個黑點理所當然就變成綠色的。

KNN圖示

KNN演算法雖然非常的簡單直覺,但是其實準確度還蠻高的,是一個蠻實用的演算法。不過實際使用上還是有一些難題在,例如

  1. 好K讓你上天堂,K要多少最合適,怎麼樣挑一個好K。(其實是有一些常用的方法)

  2. 怎麼算出資料的”距離”,例如座標距離、顏色相近程度、字詞重疊程度…等,這個會跟你的資料還有分類方法有關。 (這個要問施主你了)

  3. 每次都要掃描全部的資料算出距離,才能知道最近的k筆資料是什麼,需要相對高的記憶體跟計算時間。 (有其他加強版的演算法)

關於上面3點,未來有機會再來聊聊吧(很明顯是芭樂票)。

簡單來說,KNN就是讓你透過一群已經標記好類別的資料,來針對未分類的資料做分類的工具。

那如果只有一群尚未分類的資料,我們要怎麼將他分類呢?這邊就是非監督式學習(Unsupervised learning)中的K-Means的故事了,有機會再聊囉…

[更新: 20140708]
輕鬆聊之K-Means演算法

3 則留言: