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

[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", 有關使用可以參考下面範例: 
  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

[Git 文章收集] Differences between git merge and git rebase

Source From  Here Preface Merging and rebasing are the two most popular way to applying changes from one branch into another one. They bot...