2012年11月27日 星期二

[ JLRToolkit ] Logistic Regression Toolkit - Usage tutorial

Preface: 
最近因為 PGM 課程 需要使用到 Logistic Regression, 但卻又要求不能使用現有的工具 orz. 只好自己寫一個. 事實上在 [ ML In Action ] Logistic Regression 已經有簡單的說明 Logistic Regression 的原理並帶有 Python 的範例代碼. 所以這邊不對 Logistic Regression 原理多做說明, 而是針對我使用 Java 寫的 Logistic Regression Toolkit "JLRToolkit" 的使用進行講解. (完整的專案代碼可以在 這裡 下載.

Data format: 
這邊對可以餵進去 Toolkit 的 training data format 進行說明, 最簡單的就是假設你每一個 feature 都有值, 則你可以使用格式如下: 

這邊符號 "\s" 指的是空白鍵, 你也可以使用 '\t' =Tab 鍵, 但是要再做設定告訴工具你使用的分隔符是什麼. 而在上面的格式就是每個 feature 的值依序出現在某一行中, 並以空白當作分隔, 而最後一個 item 為 label 或是 class 的值 (必須為整數). 如果 class 只有兩種, 那就是 0 或 1; 如果 class 不只兩種, 則 class 的值從 1 開始累加: 1, 2, 3... etc. 

但有時候你的 feature 的值很 sparse, 就是很多時候 feature 是沒有值 (預設 Toolkit 會使用 0 當作沒有值的值), 則你可以使用下面的格式輸入 Training data: 

也就是你可以使用 feature id 來告訴 toolkit 目前的 feature value 是屬於哪一個 feature, 這樣你就可以不用輸入那些沒有值或是值是零的 feature. 一樣最後一個 item 是 label/class 的值. 

Usage Code Example: 
接著我們如果要用寫代碼來使用這個工具, 可以參考這邊的範例. 首先考慮我們有一個 training data 如下: 
- testSet.txt 
-0.017612 14.053064 0
-1.395634 4.662541 1
-0.752157 6.538620 0
-1.322371 7.152853 0
0.423363 11.054677 0
0.406704 7.067335 1
0.667394 12.741452 0
-2.460150 6.866805 1
...

如果將第一欄的值當作 X (Feature1); 第二欄的值當作 Y (Feature2); 第三欄的值為 label/class 的值 (0 or 1), 並標示於平面座標如下: 
 
(紅點為 label=0 的集合; 藍點為 label=1 的集合

而我們希望 Logistic Regression 幫我們找一條方程式 w0+w1X + w2Y=t 讓我們可以區隔開來某個點是屬於 label=1 或是 label=0 的集合. 由方程式中 X 便是資料中第一欄的值 ; Y 便是是資料中第二欄的值. 也就是我們要找出來 w0, w1 與 w2. 而這邊可以發現 w0 的係數是 1, 故我們在原本 Training data 中補了一欄值都為 1 的欄位, 用來 training 出 w0. 故原先資料改寫如下: 
- testSet2.txt 
1 -0.017612 14.053064 0
1 -1.395634 4.662541 1
1 -0.752157 6.538620 0
1 -1.322371 7.152853 0
1 0.423363 11.054677 0
1 0.406704 7.067335 1
...

接著我們可以使用套件中 john.logisticreg.Train 類別進行 Logistic Regression 的 training, 範例代碼如下: 
  1. Utils.SEP_CHAR="\t"// 設定 separator char = Tab  
  2. Train train = new Train(0.001150); // 設定 ALPHA=0.001; Loop iteration=150  
  3. train.start(new File("testSet2.txt")); // 對 file=testSet2.txt 進行 training.  
  4. train.saveModel(new File("Test.model")); // 將 Training 完得到的 weights 矩陣存到 Test.model 檔案中.  
執行 Log 如下: 
[Info] Total 100 records; Feature size=3; Label size=2...
[Info] Default label=1...
[Info] Label=0:[-1.65, -0.12, 0.35]...
[Info] Label=1:[3.53, 0.81, -0.53]...
[Info] Training done! (0 sec)

現在我們有了 Training model, 並得到對應每個 label 的 weights: w0, w1, w2. 如果拿 label=1 的 weights 來看: 
3.53 + 0.81X + -0.53Y = t

由 Sigmoid 的公式來看, 最佳的區隔效果出現在 t=0 的線上: 
3.53 + 0.81X + -0.53Y = 0
Y = (3.53 + 0.81X) / 0.53

接著如果將得到的線性方程式畫到剛剛的座標平面上(綠色的線), 可以發現它不錯的區隔開來 label=0 (紅點) 與 label=1 (藍點) 的集合: 
 

如果要用剛剛建立的 Training model 進行 prediction, 則可以使用套件中的類別 john.logisticreg.Predict 進行 prediction: 
  1. Predict predict = new Predict(new File("Test.model")); // 載入 Model=Test.model  
  2. System.out.printf("\t[Info] Loading model done...\n");  
  3. Utils.APPEND_ANSWER=true// 設定將 Answer也輸出到 output 的 result.  
  4. predict.start(new File("testSet2.txt"), new File("testPredict.txt")); // 對 "testSet2.txt" 進行 prediction, 並輸出結果到 "testPredict.txt"  
執行 Log 如下: 
[Info] Total 2 labels; Default label=1...
[Info] Loading model done...
[Info] Total predict 100 records...

這邊 Log 秀出來的 Default label=1 指的是我們會建立兩個 classifier for label=0;label=1. 當沒有一個 classifier 可以區隔你的 testing data 時, 仍需要給定一個答案時, 預設是猜 label=1 (因為它在 training data 中出現最多次. orz). 

Console Model Usage: 
這個套件同樣提供 Console mode 的使用方法, 首先來看看它提供的參數: 
 

接著如果要進行 Training, 可以參考用法如下: 
 

同樣要進行 Prediction 可以參考用法如下: 
 

Supplement: 
[ ML In Action ] Predicting numeric values : regression - Linear regression (1) 
[ ML In Action ] Predicting numeric values : regression - Linear regression (2) 
[ ML In Action ] Predicting numeric values : regression - Linear regression (3)

2012年11月26日 星期一

[ Java 文章收集 ] Java 產生不重覆亂數

來源自 這裡 
Preface: 
這邊要產生不重覆亂數的方法,下面是三種方式,只要是暴力法都很慢,速度是O(n^2). Java要產生亂數很簡單,只要呼叫 Random 類別就可以了,不過如果想要不重覆的亂數,有一些小方法可以用,這裡提供三種方法. 

暴力比對法: 
這個 GenerateDuplicateRan 方法會接收一個整數,表示你要取得亂數的範圍,丟進去100表示你要取0~99之間的亂數: 
  1. public static int[] GenerateNonDuplicateRan1(int range)  
  2. {  
  3.     Random rand = new Random();  
  4.     int rdm[] = new int[range];  
  5.     List holeList = new ArrayList();  
  6.     for(int i=0; i
  7.       
  8.     for(int i=0; i
  9.     {  
  10.         int pv=-1;  
  11.         do{  
  12.             pv = (int)(rand.nextDouble()*range);                  
  13.         }while(!holeList.remove(Integer.valueOf(pv)));  
  14.         rdm[i] = pv;  
  15.     }  
  16.     return rdm;  
  17. }  
這個方法接收一個整數,表示你要取得亂數的最大範圍,呼叫 GenerateDuplicateRan(100) 則會回傳一個長度100的整數陣列,裡面就是0~99不重覆的整數。寫的方式很直覺,第一個for loop跑100次,每塞一個值就會去比對之前在陣列中的數字,如果相同就移除。缺點就是要產生大量亂數的時候很慢,因為有兩層for loop,速度是n^2,如果只是要少量亂數的人可以參考. 

Collection移出法: 
第二種方法就快多了,尤其在產生大量亂數的時候更為明顯。分成三個部分來解釋. 
1. 產生一個ArrayList,並且利用for loop塞值進去,你想要產生0~99的亂數,就丟100進去,他就會依序把0~99塞到ArrayList裡面. 
2. 用Collection的remove method,隨機的取index,並且移出,直到 ArrayList 的size = 0。因為本來在ArrayList裡面的數字就沒有重複(用for loop塞的),所以隨機取出的值也不會重複! 
3. 最後一個部份就是去呼叫上面的方法並且宣告一個array來接收上面產生的亂數 
函數 GenerateNonDuplicateRan2 代碼如下: 
  1. public static int[] GenerateNonDuplicateRan2(int range)  
  2. {  
  3.     Random rand = new Random();  
  4.     int rdm[] = new int[range];  
  5.     List holeList = new ArrayList();  
  6.     for(int i=0; i
  7.     int cnt=0;  
  8.     while(holeList.size()>0)  
  9.     {  
  10.         int pv = holeList.remove(rand.nextInt(holeList.size()));  
  11.         rdm[cnt++] = pv;  
  12.     }  
  13.     return rdm;  
  14. }  
HashSet 的暴力比較法: 
另一種方式是使用 HashSet unique element 的特性, 每次產生一個 random 的整數去比對 HashSet 是否已經看過, 否則就從新產生一個 random 的整數; 如果沒看過, 便將該整數加到 HashSet 與 返回的 整數陣列中: 
  1. public static int[] GenerateNonDuplicateRan3(int range)  
  2. {  
  3.     int rdm[] = new int[range];  
  4.     Random rand = new Random();  
  5.     HashSet set = new HashSet();  
  6.     for(int i=0; i
  7.     {  
  8.         int pv = -1;  
  9.         do  
  10.         {  
  11.             pv = rand.nextInt(range);  
  12.         }while(!set.add(pv));  
  13.         rdm[i] = pv;  
  14.     }  
  15.     return rdm;  
  16. }  
測試代碼: 
底下是三種方法的使用代碼: 
  1. public static void main(String args[])  
  2. {  
  3.     int range = 1000;  
  4.     long st = System.currentTimeMillis();  
  5.     int[] rdm = Rdm.GenerateNonDuplicateRan1(range);  
  6.     System.out.printf("\t[Info] GenerateNonDuplicateRan1 with Range=%d:\n", range);  
  7.     long ut = System.currentTimeMillis()-st;  
  8.     for(int i:rdm) System.out.printf("%d ", i);  
  9.     System.out.println();  
  10.     System.out.printf("\t[Info] Spending time=%d ms(%d)!\n\n", ut, rdm.length);  
  11.       
  12.     st = System.currentTimeMillis();  
  13.     rdm = Rdm.GenerateNonDuplicateRan2(range);  
  14.     System.out.printf("\t[Info] GenerateNonDuplicateRan2 with Range=%d:\n", range);  
  15.     ut = System.currentTimeMillis()-st;  
  16.     for(int i:rdm) System.out.printf("%d ", i);  
  17.     System.out.println();  
  18.     System.out.printf("\t[Info] Spending time=%d ms!(%d)\n\n", ut, rdm.length);  
  19.       
  20.     st = System.currentTimeMillis();  
  21.     rdm = Rdm.GenerateNonDuplicateRan3(range);  
  22.     System.out.printf("\t[Info] GenerateNonDuplicateRan3 with Range=%d:\n", range);  
  23.     ut = System.currentTimeMillis()-st;  
  24.     for(int i:rdm) System.out.printf("%d ", i);  
  25.     System.out.println();  
  26.     System.out.printf("\t[Info] Spending time=%d ms!(%d)\n\n", ut, rdm.length);  
  27.       
  28. }  
執行結果如下: 
[Info] GenerateNonDuplicateRan1 with Range=1000:
864 435 238 ...
[Info] Spending time=38 ms(1000)!

[Info] GenerateNonDuplicateRan2 with Range=1000:
406 821 595 ...
[Info] Spending time=
1 ms!(1000)

[Info] GenerateNonDuplicateRan3 with Range=1000:
152 959 751 ...
[Info] Spending time=5 ms!(1000)

可以看的出來第二種方法最快!

[Git 常見問題] error: The following untracked working tree files would be overwritten by merge

  Source From  Here 方案1: // x -----删除忽略文件已经对 git 来说不识别的文件 // d -----删除未被添加到 git 的路径中的文件 // f -----强制运行 #   git clean -d -fx 方案2: 今天在服务器上  gi...