2007年4月14日 星期六
<04/14> 建好了C4.5 decision tree
雖然說build a decision tree的規則很簡單，但是真正在算information gain、entropy等等的時候還是會有些一時無法理解。好不容易把全部搞懂，代入正確的數字，最後比較gain ratio的地方也正確了，建出來的tree跟第五章投影片的順序也一致，接下來就是要搞C4.5 rule的部份了，希望趕快把這個作業寫完囉。
2007年3月28日 星期三
<03/28>這兩三個禮拜
實作了K-means、Sammon's、Fuzzy-C-means演算法，以及SVM未知詞合併的計畫。程式一個接一個寫的過程中，不知不覺熟悉的速度就會愈來愈快，也就愈來愈上手。在寫程式的過程中，因為會碰到問題，因此查API變成了例行公式，漸漸的，有些觀念也應用的比較熟練了，像是 garbage collection，以前總是覺得不需要，但是隨著程式所牽扯的資料量愈來愈大，做gc反而變成了很重要的一回事。
在SVM未知詞合併的計畫裡，目前是用training data訓練SVM，而在training data裡標示為要合併的未知詞組合，像是(婦、唱、夫、隨)這四個"詞"被判定為要合併，但不會將它加進原有辭典中，因為只是讓SVM學會，碰到這種例子的時候，SVM要判定為合併，目的是讓SVM學習；不過現在老師說要將testing data判定為要合併的未知詞組合，要把它加進舊有的辭典裡去。
我有一個疑問，是否要將training data判定要合併的這些未知詞組合也要加到辭典裡，還是只是為了讓SVM學習，不加進去，讓SVM以後再次遇到時，自行判斷合併與否。
這個疑問的兩種解答會造成辭典裡的index不同，畢竟婦唱夫隨這四個字是分開的時候，在辭典裡分屬四個不同的位置，所以餵給SVM的資料也要存四個不同的index；若是在training的過程中將這四個字合併並加入辭典，則這個新詞(四字合起來)只會有一個index，SVM對待它的方式也會大有不同(只會看成一個attribute)。
在SVM未知詞合併的計畫裡，目前是用training data訓練SVM，而在training data裡標示為要合併的未知詞組合，像是(婦、唱、夫、隨)這四個"詞"被判定為要合併，但不會將它加進原有辭典中，因為只是讓SVM學會，碰到這種例子的時候，SVM要判定為合併，目的是讓SVM學習；不過現在老師說要將testing data判定為要合併的未知詞組合，要把它加進舊有的辭典裡去。
我有一個疑問，是否要將training data判定要合併的這些未知詞組合也要加到辭典裡，還是只是為了讓SVM學習，不加進去，讓SVM以後再次遇到時，自行判斷合併與否。
這個疑問的兩種解答會造成辭典裡的index不同，畢竟婦唱夫隨這四個字是分開的時候，在辭典裡分屬四個不同的位置，所以餵給SVM的資料也要存四個不同的index；若是在training的過程中將這四個字合併並加入辭典，則這個新詞(四字合起來)只會有一個index，SVM對待它的方式也會大有不同(只會看成一個attribute)。
2007年3月18日 星期日
Lazy Associative Classification
這篇paper主要是介紹了一個新的associative classification的作法。一般來說，associative classifier會比decision tree classifier的準確率要來得高。因為decision tree classifier 是用greedy(local) search的方法，選出目前擁有最高information gain的attribute，加進tree裡面形成新的split node，對於此node的子樹來說，皆為該attribute與其他所剩下的attribute中，挑選擁有最高information gain的attribute來繼續splitting，直到所有的instance屬於同一個class或是此node已低於某特定的minimum support threshold等等。decision tree classifier的特點是快速且容易明瞭，缺點為local search的情況下容易忽略了important rules。association rule classifier可以解決此問題，透過global search的方式，可以產生large number of rules。但是該優點正也是缺點所在，產生了大規模的rule set，許多的rule在分類的過程中甚至幾乎沒有用到，整體效率不彰。
因此本篇作者提出了lazy associative classification的觀念，相比於一般的 (eager) associative classification，lazy associative classifier並不是對於所有的 training data皆產生了rule set，而是demand-driven basis，也就是只針對testing instance所擁有的feature去產生association rules，如此可以保證所產生的association rules一定至少跟testing data有若干關係，不至於發生在測試的過程中，只用到少數association rules的情形。
對於lazy associative classification，為了一開始就記錄test instance所包含的feature set，會用到比一般associative classification更多的workload，此問題在paper中也提到了可以用caching的方式解決。另一個問題是只針對test instance產生的association rule，代表的就是要犧牲部分的generalization和影響classification若干的accuracy。
最後實驗證實，lazy association classification可以降低10%的error rate，相比於一般的association classification；而若是跟decision tree classification相比，更可以減少近20%的error rate。
Proceedings of the Sixth International Conference on Data Mining 2006 (IEEE)
因此本篇作者提出了lazy associative classification的觀念，相比於一般的 (eager) associative classification，lazy associative classifier並不是對於所有的 training data皆產生了rule set，而是demand-driven basis，也就是只針對testing instance所擁有的feature去產生association rules，如此可以保證所產生的association rules一定至少跟testing data有若干關係，不至於發生在測試的過程中，只用到少數association rules的情形。
對於lazy associative classification，為了一開始就記錄test instance所包含的feature set，會用到比一般associative classification更多的workload，此問題在paper中也提到了可以用caching的方式解決。另一個問題是只針對test instance產生的association rule，代表的就是要犧牲部分的generalization和影響classification若干的accuracy。
最後實驗證實，lazy association classification可以降低10%的error rate，相比於一般的association classification；而若是跟decision tree classification相比，更可以減少近20%的error rate。
Proceedings of the Sixth International Conference on Data Mining 2006 (IEEE)
2007年2月12日 星期一
研究計畫(SVM using in Chinese Unknown Word)
之前學期尚未結束時，計畫停頓了一下子。並不是完全停頓，但是進度很慢。直到寒假開始，才又開始趕工。
因為training data太過龐大，因此我一直是以subset來做測試，測試辭典的index、屬性，測試Phase2_training的資料是否有正確處理到，包括計算其sliding window所組成的未知詞之frequency，以及該sliding window未知詞之prefix、suffix結合的機率，還有該sliding window的條件機率( P(1/2.3.4) or P(4/1.2.3) ，0是prefix，5是suffix。<=此例子是sliding window4)。
這幾天我開始用全部的Phase2_training data來跑，才發現了嚴重的問題。程式碼的效率不彰，使得整個程式的物件宣告不是太集中，一下子吃掉了太多記憶體；就是太分散，以致於不知道什麼已經宣告過了... 這是自己經驗的問題，看來我還有得學了。所以最近把程式碼不斷的修過，加上讓java擁有更多的memory來跑，跑出來應該不是什麼問題了。
在testing的部份，我用學長的程式將testing的數十個document組合成一起。結果當掉了...我再問問看學長好了。等到組合好，就可以拿去讓LIBSVM predict了。
而LIBSVM的使用，基本的train、predict功能都不是問題，重點是它有些參數可以調，讓precision可以更高一點，這些參數要怎麼設定現在還是不太確定。看過有人寫的tutorial，他說最好的方法就是 "try!!!"... 是啦，good answer~
另外就是論文的部份，因為實在是沒什麼經驗，所以我想應該要先把想要寫什麼，給弄清楚。之後還要多看看別人的paper，看看別人是如何表達意見的，格式、用字等等，才可以。
因為training data太過龐大，因此我一直是以subset來做測試，測試辭典的index、屬性，測試Phase2_training的資料是否有正確處理到，包括計算其sliding window所組成的未知詞之frequency，以及該sliding window未知詞之prefix、suffix結合的機率，還有該sliding window的條件機率( P(1/2.3.4) or P(4/1.2.3) ，0是prefix，5是suffix。<=此例子是sliding window4)。
這幾天我開始用全部的Phase2_training data來跑，才發現了嚴重的問題。程式碼的效率不彰，使得整個程式的物件宣告不是太集中，一下子吃掉了太多記憶體；就是太分散，以致於不知道什麼已經宣告過了... 這是自己經驗的問題，看來我還有得學了。所以最近把程式碼不斷的修過，加上讓java擁有更多的memory來跑，跑出來應該不是什麼問題了。
在testing的部份，我用學長的程式將testing的數十個document組合成一起。結果當掉了...我再問問看學長好了。等到組合好，就可以拿去讓LIBSVM predict了。
而LIBSVM的使用，基本的train、predict功能都不是問題，重點是它有些參數可以調，讓precision可以更高一點，這些參數要怎麼設定現在還是不太確定。看過有人寫的tutorial，他說最好的方法就是 "try!!!"... 是啦，good answer~
另外就是論文的部份，因為實在是沒什麼經驗，所以我想應該要先把想要寫什麼，給弄清楚。之後還要多看看別人的paper，看看別人是如何表達意見的，格式、用字等等，才可以。
2007年1月23日 星期二
Knowing a Web Page By the Company It Keeps (1/23)
這篇取自於 CIKM'2006的論文，內容主要是講如何透過neighboring page的資訊將target page 做分類。
Web page classification有許多資訊可以加以應用，包括網頁的內容及鏈結資訊等，這一篇論文則著重在相鄰網頁可以提供的分類效果。作者將相鄰網頁分成Parent，Child，Sibling及Sprouse四種類別，同時依據相鄰網頁是否經過label與否給予權重，再依相鄰網頁與target Page是否係出同門（網站）給予不同權重，最後對所有的參數如何影響分類的表現做了很完整的實驗。整篇的idea不是很困難，不過作者做了深入的研究以及實驗。
結論與直觀想法差距不大：
1. 有label的網頁提供的分類效果總是比沒有label的網頁好(η Eta)。
2. 四種鄰近網頁中屬Sibling的效最佳(β Beta)。
3. 來自同一網站的相鄰網頁提供的資訊比其他網站的相鄰資訊有益於分類(θ Theta)。
4. 鄰近網頁與target page的權重比於0.2與0.8是效果最佳(α Alpha)。
對ODP(Open Directory Project)等品質高的網頁分類效果可達90%，但是對一般網頁效果則降至56%，顯示還有相當的改善空間。
Web page classification有許多資訊可以加以應用，包括網頁的內容及鏈結資訊等，這一篇論文則著重在相鄰網頁可以提供的分類效果。作者將相鄰網頁分成Parent，Child，Sibling及Sprouse四種類別，同時依據相鄰網頁是否經過label與否給予權重，再依相鄰網頁與target Page是否係出同門（網站）給予不同權重，最後對所有的參數如何影響分類的表現做了很完整的實驗。整篇的idea不是很困難，不過作者做了深入的研究以及實驗。
結論與直觀想法差距不大：
1. 有label的網頁提供的分類效果總是比沒有label的網頁好(η Eta)。
2. 四種鄰近網頁中屬Sibling的效最佳(β Beta)。
3. 來自同一網站的相鄰網頁提供的資訊比其他網站的相鄰資訊有益於分類(θ Theta)。
4. 鄰近網頁與target page的權重比於0.2與0.8是效果最佳(α Alpha)。
對ODP(Open Directory Project)等品質高的網頁分類效果可達90%，但是對一般網頁效果則降至56%，顯示還有相當的改善空間。
2007年1月21日 星期日
seminar 1/23 summary
我這次報的paper是Knowing a Web Page by the Company It Keeps。
這篇paper是來自於 CIKM'2006。
內容主要是講如何透過neighboring page的資訊將target page 做分類。Web page classification有許多technique可以加以應用，包括link structure、neighboring page information等等，不過這一篇paper只著重在neighboring page information的幫忙下做網頁的分類。我認為作者對於neighboring page的分類很仔細，不僅根據link structure切割成四種集合，再將整個neighboring page分成是否經過labeling(是否分類成屬於某種category)兩種，並對所有的parameter如何影響分類的表現做了很完整的實驗。整篇的idea不是很困難，不過作者做了深入的研究以及實驗，從這方面真的可以看到作者用心之處。我看完這篇paper後，對於web page classification有了初步的了解，特別是neighboring page information的方面，對於影響分類的一些小因素得到了不少啟示。
這篇paper是來自於 CIKM'2006。
內容主要是講如何透過neighboring page的資訊將target page 做分類。Web page classification有許多technique可以加以應用，包括link structure、neighboring page information等等，不過這一篇paper只著重在neighboring page information的幫忙下做網頁的分類。我認為作者對於neighboring page的分類很仔細，不僅根據link structure切割成四種集合，再將整個neighboring page分成是否經過labeling(是否分類成屬於某種category)兩種，並對所有的parameter如何影響分類的表現做了很完整的實驗。整篇的idea不是很困難，不過作者做了深入的研究以及實驗，從這方面真的可以看到作者用心之處。我看完這篇paper後，對於web page classification有了初步的了解，特別是neighboring page information的方面，對於影響分類的一些小因素得到了不少啟示。
seminar 1/23 note 2
Experiment part
IO-bridge : consider only siblings of the target page within a human labeled dataset
bridge : if two or more pages have the same class, while not committing what that class would be, we call these documents bridges.
IO-bridge : a page B points to both document b1 and b2, and the way from b1 to b2 is to traverse the edge (B,b1) against its direction and then (B,b2). So B is IO-bridge for b1 and b2 because of the inlink to B (b1->B) and followed by an outlink (B->b2). http://delivery.acm.org/10.1145/280000/276332/p307-chakrabarti.pdf?key1=276332&key2=0117839611&coll=GUIDE&dl=GUIDE&CFID=9534706&CFTOKEN=44327035
IO-bridge : consider only siblings of the target page within a human labeled dataset
bridge : if two or more pages have the same class, while not committing what that class would be, we call these documents bridges.
IO-bridge : a page B points to both document b1 and b2, and the way from b1 to b2 is to traverse the edge (B,b1) against its direction and then (B,b2). So B is IO-bridge for b1 and b2 because of the inlink to B (b1->B) and followed by an outlink (B->b2). http://delivery.acm.org/10.1145/280000/276332/p307-chakrabarti.pdf?key1=276332&key2=0117839611&coll=GUIDE&dl=GUIDE&CFID=9534706&CFTOKEN=44327035
seminar 1/23 note 1
Experiment part
K+C from Calado : link-based and content-based combination for web document classification
kNN for content-based , co-citation for link-based.
co-citation : a Web page author will insert links to pages related to his own pages. Apply co-
citation to Web documents by treating links as citations.
http://delivery.acm.org/10.1145/960000/956938/p394-calado.pdf?key1=956938&amp;amp;key2=5009639611&coll=GUIDE&dl=GUIDE&CFID=11980192&CFTOKEN=64981017
K+C from Calado : link-based and content-based combination for web document classification
kNN for content-based , co-citation for link-based.
co-citation : a Web page author will insert links to pages related to his own pages. Apply co-
citation to Web documents by treating links as citations.
http://delivery.acm.org/10.1145/960000/956938/p394-calado.pdf?key1=956938&amp;amp;key2=5009639611&coll=GUIDE&dl=GUIDE&CFID=11980192&CFTOKEN=64981017
訂閱：
文章 (Atom)