2007年4月21日

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)

2007年4月11日

Movie review mining and summarization

這篇論文出自CIKM’06,目的是做movie review mining和summmarization,主要是藉由產生正面與負面的feature-opinion pairs做為此電影資訊的摘要。此篇論文提出的方法是一開始先利用WordNet、IMDB的movie casts和labeled training data去產生feature跟opinion的keyword list,利用此list找出句子中的feature words和opinion words且決定feature words是屬於哪個feature class和opinion words是正面的還負面的;訓練階段會利用pattern mining 找出dependency grammar graph中feature到opinion pair之間的常見pattern,做為測試階段feature-opinion pair找尋的依據。

實驗部分跟Hu and Liu的KDD'04的opinion extraction做法比較,以擷取feature-opinion pair 的precision 和recall做為評估原則。

連結: Proceedings of the 15th ACM international conference on knowledge management CIKM'06

A study on automatically extracted keywords in text categorization

A study on automatically extracted keywords in text categorization

本篇文章出自於ACL’2006, 其主要目的是探討 “Keyword” 對文件分類的影響力.
keyword extraction: 列舉出幾個常用的方法, 例如: n-grams, PoS, and Chunking. 在feature value 指派的方面, 描述出幾個常用的方法, 例如: tf, tf*idf, relative position of the first occurrence, PoS tag, 其中PoS tag是作者在 “Improved Automatic Keyword Extraction Given More Linguistic Knowledge”所提出來的方法, 在得到input feature and feature value之後, 採用supervised machine learning method (rule induction) 來訓練prediction models, 來判斷輸入的term, 是否為keywords, 實驗結果顯示, keyword 擷取的F-measure 可達44%.

文件分類部份所用的文件表達方式可分為keyword only 和full-text來探討, 而feature value的指派, 則採用tf*idf or boolean value, 而機器學習方法則係用linear support vector machine,來對文章做分類. 以往文件分類最基本的方式係用全文(full-text)的方式當作是input feature. 本篇針對不同的input feature 以及 feature value作了一系列的試驗, 來說明以full-text + keywords來當作是input feature, 其所得到的分類結果 (F-measure) 是最佳的, 可達到81.07%.

Link: Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the ACL

2007年4月10日

Pollock: Automatic Generation of Virtual Web Services from Web Sites

這一篇論文是出自ACM SAC 2005,主要目的是設計一個快速產生Web Service的方法。

假設現在我們想要整合不同的網路書店,我們可能會先找100個書店,然後設法抓出網站中的拍賣資訊。此時有些書店有提供Web Service直接查詢,但有些書店則缺乏相關資訊。這篇論文的構想是為沒有Web Service的網站自動產生"Virtual Web Service",如此一來便可以快速整合不同書店間的資訊。

對於沒有Web Service的網站,首先會利用Wrapper技術擷取該網站的回傳網頁,在這裡使用XWRAP。XWRAP是一個以XML為基礎的wrapper,可 以將wrap出來的資訊轉為XML呈現。同時論文設計了一個translator,用來轉換SOAP和Html GET/POST的資訊,讓Wrapper執行時資訊可以順利傳遞。在Wrapper工作完成後,接下來產生Web Service和WSDL的步驟在此方法中也會處理。

Slides




論文連結

Proceedings of the 2005 ACM SAC, pp. 1650 - 1655