程式扎記: [ML in DH] Classification 之 Distance-Based Methods

標籤

2014年5月29日 星期四

[ML in DH] Classification 之 Distance-Based Methods

內容來自課程 這裡 
Preface: 
用「向量」來表示文件,然後定義「距離」. 例如,使用歐氏幾何概念下,向量與向量之間的距離,來表示文件之間的相似程度距離越近越相似).令事先定義好的類別為 C = {C1, C2, ..., Cn} . 給定一個已經分好類別的文件集合 (training set): 
- Simple Distance-Based Approach:如果欲分類的文件 d「最接近」類別 Ci 的中心點,就把 d 歸類於 C
- k-Nearest Neighbors (k-NN) Approach:令 N(k) 為最接近 d 的 k 個點的集合。若 N(k) 中的文件被分類於class Ci 的最多,就將 d 分類在 Ci。

Simple Distance-Based Algorithm 
必須先將 distance(Ci, d) 定義出來。例如,若 training set 中, t1, ..., tm 這 m 篇文件被預先分類於 Ci,我們可令 center(Ci) 為 t1, ..., tm 這 m 個向量的中心點,而定義 distance(Ci, d) 為 d 到 center(Ci) 的距離. 演算法的 pseudo code 如下: 
 

k-Nearest Neighbors: 
 

接著來看下面圖形化的範例了解 k-Means 與 Simple Distance-Based 的差別: 
 

Example: 3-NN 
若定義距離函數為 dist(x,y) = |年齡等級差| + |收入等級差| + |是否學生差| + |信用狀況差| 
– 年齡等級: <=30, 介於 31-40, > 40 的等級分別為 1, 2, 3
– 收入等級: 收入為高, 中, 低 的等級分別為 1, 2, 3
– 是否為學生:若「是」則等級為 1, 「否」則為 2
– 信用狀況:「良好」的等級為 1,「普通」的等級為 2

現有一筆關於某人的資料,欲「推測」其是否會買電腦: 
 

令 xi 代表編號 i 的資料。則 dist(d, xi) 的距離為: 
 

Toolkit Usage: 
kNN 的演算法我實作於 "KNN.groovy", 使用範例如下: 
  1. def labels = ["Age""Income""Student?""CC""Class"]  
  2. def datas =  [["<=30""高""N""O""N"],  
  3.               ["<=30""高""N""G""N"],  
  4.               ["31-40""高""N""O""Y"],  
  5.               [">40""中""N""O""Y"],  
  6.               [">40""低""Y""O""Y"],  
  7.               [">40""低""Y""G""N"],  
  8.               ["31-40""低""Y""G""Y"],  
  9.               ["<=30""中""N""O""N"],  
  10.               ["<=30""低""Y""O""Y"],  
  11.               [">40""中""Y""O""Y"],  
  12.               ["<=30""中""Y""G""Y"],  
  13.               ["31-40""中""N""G""Y"],  
  14.               ["31-40""高""Y""O""Y"],  
  15.               [">40""中""N""G""N"]]  
  16. // 收集每個 Instance 的 Category  
  17. def cateList = datas.collect {it[4]}  
  18.   
  19. printf "\t[Info] kNN with k=3:\n"  
  20. KNN knn = new KNN()  
  21. def kNNData = datas.collect{d->  
  22.     def inst = []  
  23.     switch(d[0])  
  24.     {  
  25.         case "<=30":  
  26.             inst.add(1)  
  27.             break  
  28.         case "31-40":  
  29.             inst.add(2)  
  30.             break  
  31.         case ">40":  
  32.             inst.add(3)                   
  33.     }  
  34.     switch(d[1])  
  35.     {  
  36.         case "高":  
  37.             inst.add(1)  
  38.             break  
  39.         case "中":  
  40.             inst.add(2)  
  41.             break  
  42.         case "低":  
  43.             inst.add(3)  
  44.     }  
  45.     switch(d[2])  
  46.     {  
  47.         case "Y":  
  48.             inst.add(1)  
  49.             break  
  50.         case "N":  
  51.             inst.add(2)                   
  52.     }  
  53.     switch(d[3])  
  54.     {  
  55.         case "G":  
  56.             inst.add(1)  
  57.             break  
  58.         case "O":  
  59.             inst.add(2)  
  60.     }  
  61.     return inst  
  62. }  
  63.       
  64. testInst = [2121]  
  65. printf "\t[Info] For KNN, [%s] is classified as %s\n", testInst.join(","), knn.classify1(testInst, kNNData, cateList, 3)  
執行結果如下: 
 

Supplement: 
[ ML In Action ] Classifying with k-Nearest Neighbors

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!