[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", 使用範例如下: 

view plaincopy to clipboardprint?

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 = [2, 1, 2, 1]  
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

[ML in DH] Classification 之 Naive Bayesian Categorization

內容來自課程 這裡 
Preface: 
假設現在有一篇文件，其 representation 為一 n 個維度的特徵向量 X = (x1, x2, ..., xn). 目標是將其分類於 m 個 classes C1, ..., Cm之一。直覺的作法是對於每個 class ，估算 P(Ci|X). 如果P(Ci|X) 比其他 P(Cj|X) 有著更高的機率，the naive Bayesian classifier 會將文件 X 分類於 Ci : 
 

Naive Bayesian Training: 
如何利用 training documents 估算 P(X|Ci) 與 P(Ci)? 將 P(Ci) 以「訓練文件中，屬於 class Ci 的比例」估算. 也就是說，若 T(Ci) 表示被分類於 Ci 的訓練文件，我們用 P(Ci) = si/S（其中 S=|T|, si=|T(Ci)|）來估算 P(Ci) 。為了簡化 P(X|Ci) 的估算，我們天真地 (naively) 假設特徵維度之間滿足條件獨立。也就是說: 
 

令 T(Ci, xj) 為 T(Ci) 中，文件含有特徵 xj 的集合。我們用 T(Ci, xj) 在 T(Ci) 所佔的比例估算 P(xj|Ci)。– 也就是說， P(xj|Ci)=sij/si, 其中 sij=|T(Ci, xj)|. 

Example: Naive Bayesian Categorization 
現有一筆關於某人的資料，欲「推測」其是否會買電腦？ 
 

方法：令 C1 代表「YES:會買電腦」， C2 代表「NO:不會買電腦」。現比較 P(C1|X) 與 P(C2|X)，取最大者之類別: 
 
 

Toolkit Usage: 
根據上面說明, 我實作 Naive Bayesian 在 "NaiveBayes.groovy", 有關使用可以參考下面範例: 

view plaincopy to clipboardprint?

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. NaiveBayes nb = new NaiveBayes()  
17.   
18. // 收集每個 Instance 的 Category  
19. def cateList = datas.collect {it[4]}  
20. def instances = []  
21. datas.each { data->  
22.     //printf "\t[Test] %s\n", data[0..3].join(",")  
23.     instances.add(data[0..3])  
24. }  
25. printf "\t[Info] NaiveBayes training...%s\n", nb.train2(instances, cateList)  
26. def testInst = ["<=30", "中", "Y", "O"]  
27. printf "\t[Info] Instance=[%s] is classified as %s!\n", testInst.join(","), nb.classify2(testInst)  
28. testInst = ["31-40", "高", "N", "O"]  
29. printf "\t[Info] Instance=[%s] is classified as %s!\n", testInst.join(","), nb.classify2(testInst)  

執行結果: 
 

Supplement: 
* [ ML In Action ] Classifying with probability theory : naive Bayes