自動分類成效分析.doc

Size: px

Start display at page:

Download "自動分類成效分析.doc"

召陶
5 years ago
Views:

1 Effectveness Issues n Automatc Text Categorzaton, , 68, Abstract: Text categorzaton or document classfcaton s a task to assgn predefned labels to documents based on ther content. Ths artcle dscusses twelve ssues that are related to the effectveness of automatc text categorzaton based on a lterature revew and the author experences n ths task. Parts of the conclusons nclude: (1) Automatc summarzaton, based on our experments, does not mprove classfcaton effectveness, as opposte to some prevous studes. (2) Inconsstency (n assgnng labels) seems nevtable n ths task and thus may adversely affect the effectveness of better classfers, especally when the test documents are hghly nconsstent (3) Performance measure should go beyond tradtonal precson/recall metrcs. Some cost functons should be consdered to better meet users needs. (4) Machne classfers seem to be more consstent than humans n assgnng labels to documents. Thus classfers can ad human experts to do the job n a cost-effectve way, as s manfested n 2 reported real-world cases. keywords: document classfcaton, effectveness analyss, knowledge management 1

2 document classfcaton or text categorzaton class category [1] [2] Infoseek Altavsta Google collecton browsng topc-based retreval SDI, Selected Dssemnaton of Informaton nformaton flter or routng text mnng knowledge dscovery knowledge management 2

3 [3-23] 3

4 => test collecton ReutersOHSUMED20NG Reuters 1987 Davd Lews OHSUMED Wllam Hersh [24] , MeSHMedcal Subject Headlne 14,321 20NG 20 newsgroups 20, UseNet 4.5% 70% 30% 4

5 A B A A B A B A B labelng document classfcaton or text categorzaton document clusterng unsupervsed learnng supervsed learnng Roussnov Chen [25] Duda Hart [26] The dstncton s that wth supervsed learnng we know the state of nature (class label) for each sample, whereas wth unsupervsed learnng we do not. As one would expect, the problem of unsupervsed learnng s the more dffcult one. => symbolc numerc IF condtons, THEN categores 5

6 C4.5RIPPERsleepng experts [27]Swap-1 [28] SVMSupport Vector MachneKNNK-Nearest NeghborsLLSFLnear Least Square FtPerceptronNeural NetworkNaïve Bayse [29] Bekkerman SVM 20NG [30] 12 feature selecton word Al-Kofah [31] 13,779 word par 13,779 word word par 2/ /6 6

7 n-gram N-gram n n-gram n-gram n-gramn n-gram n-gram n-gram n-gram n feature reducton nosy term theof document frequency, DF TF x IDF 60%-70% TF x IDF N mutual nformaton [32], nformaton gan, ch-square test, correlaton [33], odds rato [34] Ng [33] Perceptron Reuters Bekkerman [30] SVM Reuters 20NG mutual nformaton Reuters 50 20NG Yang and Pedersen [32] Reuters OHSUMED Joachms [35] SVM Reuters 7

acq nformaton gan 200 90% 201-500 70% 501-1000 60% 4000 40% 21% Ng [33] Feature Selecton 20 features 50 features 100 features 200

8 acq nformaton gan % % % % 21% Ng [33] Feature Selecton 20 features 50 features 100 features 200 features Correlaton Ch-square Frequency Bekkerman [30] Joachms [35] 8

9 % 80% [36] [37] Reuters 65% 71.9% [38] Reuters 68.9% 30% 71.5% KNN 75.3% 30% 72.8% 70% Reuters 7 9

SVMSupport Vector Machne KNNK-Nearest NeghborsLLSFLnear Least Square Ftmultlayered perceptronsnaïve BayseRoccho Yang Lu [29] Reuters 90 { SVM, KNN} > LLSF > multlayered perceptrons >> multnomal nave

10 SVMSupport Vector Machne KNNK-Nearest NeghborsLLSFLnear Least Square Ftmultlayered perceptronsnaïve BayseRoccho Yang Lu [29] Reuters 90 { SVM, KNN} > LLSF > multlayered perceptrons >> multnomal nave Bayes SVM KNN SVM KNN LLSF LLSF multlayered perceptrons naïve Bayes Yang Reuters Joachms [35] Reuters mcro-average SVM (0.864)>KNN (0.823)>{Roccho(0.799),C4.5(0.794)}>naïve Bayes (0.72) mcro-average Joachms OHSUMED 23 SVM(0.66) > KNN (0.591) > naïve Bayes (0.57) > Roccho (0.566) > C4.5(0.50) 23 SVM KNN SVM 1990 SVM SVM Platt [39] SVM bnary classfer SVM Yes No mult-class problems SVM SVM SVM Yang

11 KNN KNN K K votng weghted K=4 Smlarty_Dstance(, )= 0.5 Smlarty_Dstance(, )=0.9 Smlarty_Dstance(, )= =0.8 KNN KNN KNN KNN Lam Ho KNN KNN [40] SVM KNN [41][31][42] multple classfers 11

12 classfcaton scheme herarchcal Reuters Topc PlacePeopleOrganzaton Exchange AI machne learnng classfcaton IR document organzaton categorzaton AI IR AI classfcaton IR categorzaton 6 AI IR classfcaton categorzaton 12

13 B->E B->E->G->M B->E->G B->E->H A->D->I B->E->H B->E->G A->D->I B->E->G Ruz [43] Ng [33] sngle labelng multple labelng subject headngs 13

14 bnary classfer Yes No Yes No Yes Yes optmal Reuters Reuters Reuters 1 100% 0% Reuters 90 14

15 Reuters 1 earn acq money-fx gran crude trade nterest wheat shp corn Reuters 71 coconut palladum coconut-ol palmkernel jet rand cpu castor-ol potato cotton-ol propane groundnut-ol copra-cake ln-ol dfl nkr naphtha rye nzdlr sun-meal 1 1 Krenes [44] 2001 TREC flterng Reuters [45] 1,000 10% 20% Kao [46] Kao 15

16 Dumas [47] SVM Reuters 10 92% 10% 89.6%5% 86.2%1% 72.6% 5 20 [48] % % samplng 16

17 [49] 7~12 5, % 67.14% 8~12 5, % 61.98% 9~12 4, % 61.69% 10~12 3, % 59.77% 11~12 2, % 53.82% 12 1, % 52.64% a b c d A, accuracy P, precson R, recall accuracy=(a+d)/(a+b+c+d), precson=a/(a+c), recall=a/(a+b) d d 1 F=2PR/(P+R) mcro-average macro-average a mcropr ecson =, a + c mcrore call = a + a b 1 m a 1 m a macro Pr ecson = m =, macro Re call = 1 a + c m = 1 a + b 17 m F P R mcro-f macro-fmcro-average macro-average

18 mcro-average macro-average a c b d Hersh [50] Ths feld needs to move beyond smulated data sets and recall/precson type metrcs. We have all seen the decent results that good systems can generate, but now we need to fgure out to make these tools truly useful to researchers and analysts who are gong to use them to solve real-world problems. That s, we need to show that we can help a researcher extract knowledge from mnng the lterature that results n scentfc dscovery prevously not possble (or excessvely tme-consumng). / %=(114-51)/114 F / /3 F=2PR/PR P=R F precson-orented 18

19 recall-orented Yang SIGIR 1999 [29] SIGIR 2001 Yang [51] F % F /0.55=87.28% defned by examples defned by descrptons 19

20 [52] [53]

21 [54] ACM [55] 21

22 12 40% => 22

23 [1] 78 [2] Hsnchun Chen, Knowledge Management Systems: A Text Mnng Perspectve, [3] 84 [4] 84 [5] 85 [6] 86 [7] 87 [8] 88 [9] Sue J. Ker and Jen Nan Chen, A Text Categorzaton Based on Summarzaton Technque, Proceedngs of NLPIR Workshop of ACL 2000, pp [10] Davd D. Lews, An Evaluaton of Phrasal and Clustered Representatons on a Text Categorzaton Task, Proceedngs of the Ffteenth Annual Internatonal ACM SIGIR Conference on Research and development n Informaton Retreval, 1992, Pages [11] Elzabeth D. Lddy, Woojn Pak and Edmund S. Yu, Text Categorzaton for Multple Users based on Semantc Features from a Machne-Readable Dctonary, ACM Transactons on Informaton Systems Vol. 12, No. 3 (Jul. 1994), Pages [12] Ymng Yang and Chrstopher G. Chute, An Example-based Mappng Method for Text Categorzaton and Retreval, ACM Transactons on Informaton Systems Vol. 12, No. 3 (Jul. 1994), Pages [13] Ymng Yang, Expert Network: Effectve and Effcent Learnng from Human Decsons n Text Categorzaton and Retreval, Proceedngs of the 17th Annual Internatonal ACM-SIGIR Conference on Research and Development n Informaton Retreval, 1994, Pages [14] Ymng Yang, Nose Reducton n a Statstcal Approach to Text Categorzaton, Proceedngs of the 18th Annual Internatonal ACM-SIGIR Conference on Research and Development n Informaton Retreval, 1995, Pages

24 [15] Makoto Iwayama and Takenobu Tokunaga, Cluster-based Text Categorzaton: a Comparson of Category Search Strateges, Proceedngs of the 18th Annual Internatonal ACM-SIGIR Conference on Research and Development n Informaton Retreval, 1995, Pages [16] Marc Damashek, "Gaugng Smlarty wth N-grams: Language-Independent Categorzaton of Text," Scence, Vol. 267, 1995, pp [17] Leah S. Larkey, Automatc Essay Gradng Usng Text Categorzaton Technques, Proceedngs of the 21st Annual Internatonal ACM-SIGIR Conference on Research and Development n Informaton Retreval, 1998, Pages [18] Raymond J. Mooney and Lorene Roy, Content-Based Book Recommendng usng Learnng for Text Categorzaton, Proceedngs of the ffth ACM Conference on ACM 2000 Dgtal Lbrares, 2000, Pages [19] Fabrzo Sebastan, Alessandro Sperdut and Ncola Valdambrn, An Improved Boostng Algorthm and ts Applcaton to Text Categorzaton, Proceedngs of the 9th Internatonal Conference on Informaton and Knowledge Management CIKM 2000, Pages [20] Jhy-Jong Tsay and Jng-Doo Wang, Improvng Automatc Chnese Text Categorzaton by Error Correcton, Proceedngs of the 5th Internatonal Workshop on Informaton Retreval wth Asan Languages, 2000, Pages 1 8. [21] C. K. P. Wong, R. W. P. Luk, K. F. Wong and K. L. Kwok; Text Categorzaton usng Hybrd (Mned) Terms, Proceedngs of the 5th Internatonal Workshop on Informaton Retreval wth Asan Languages, 2000, Pages [22] Jason D. M. Renne and Ryan Rfkn, "Improvng Multclass Text Classfcaton wth the Support Vector Machne," Massachusetts Insttute of Technology. AI Memo AIM [23] Thorsten Joachms, A Statstcal Learnng Model of Text Classfcaton for Support Vector Machnes, Proceedngs of the 23rd Annual Internatonal ACM-SIGIR Conference on Research and Development n Informaton Retreval, 2001, pp [24] W. Hersh, C. Buckley, T. J. Leone, and D. Hckam, OHSUMED: An Interactve Retreval Evaluaton and New Large Test Collecton for Research, Proceedngs of the 17th Annual Internatonal ACM SIGIR Conference on Research and development n Informaton Retreval, 1994, Pages [25] Dmtr G. Roussnov and Hsnchun Chen, A Scalable Self-organzng Map Algorthm for Textual Classfcaton: A Neural Network Approach to Thesaurus Generaton, Communcaton and Cognton n Artfcal Intellgence 24

25 Journal (CC-AI), Vol. 15, N. 1-2, Pages , 1998 [26] R. O. Duda and P. E. Hart. Pattern Classfcaton and Scene Analyss. John Wley & Sons, Inc., New York, NY, [27] Wllam W. Cohen and Yoram Snger, Context-Senstve Learnng Methods for Text Categorzaton, Proceedngs of the 19th Annual Internatonal ACM-SIGIR Conference on Research and Development n Informaton Retreval, 1996, Pages [28] Chdanand Apt, Fred Damerau and Sholom M. Wess, Towards Language Independent Automated Learnng of Text Categorzaton Models, Proceedngs of the 17th Annual Internatonal ACM-SIGIR Conference on Research and Development n Informaton Retreval, 1994, Pages [29] Ymng Yang and Xn Lu, A Re-Examnaton of Text Categorzaton Methods, Proceedngs of the 22nd Annual Internatonal ACM-SIGIR Conference on Research and Development n Informaton Retreval, 1999, Pages [30] Ron Bekkerman, Ran El-Yanv, Yoad Wnter, Naftal Tshby, On Feature Dstrbutonal Clusterng for Text Categorzaton, Proceedngs of the 24th Annual Internatonal ACM-SIGIR Conference on Research and Development n Informaton Retreval, 2001, pp [31] Khald Al-Kofah, Alex Tyrrell, Arun Vachher, Tm Travers, and Peter Jackson, "Combnng Multple Classfers for Text Categorzaton," Proceedngs of the Tenth Internatonal Conference on Informaton and Knowledge Management 2001, Atlanta, Georga, USA, pp [32] Ymng Yang and J. Pedersen, A Comparatve Study on Feature Selecton n Text Categorzaton, Proceedngs of the Internatonal Conference on Machne Learnng (ICML 97), 1997, pp [33] Hwee Tou Ng, We Boon Goh and Kok Leong Low, Feature Selecton, Percepton Learnng, and a Usablty Case Study for Text Categorzaton, Proceedngs of the 20th Annual Internatonal ACM-SIGIR Conference on Research and Development n Informaton Retreval, 1997, Pages [34] Dunja Mladenc, etc, "Feature selecton for unbalanced class dstrbuton and Nave Bayes," Proceedngs of the Internatonal Conference on Machne Learnng (ICML 98), 1998, [35] Thorsten Joachms, Text Categorzaton wth Support Vector Machnes: Learnng wth Many Relevant Features, Proceedngs of the European Conference on Machne Learnng, 1998, Berln, pp [36] 88 [37]

26 [38] 2001 [39] Platt, J. Fast Tranng of SVMs usng Sequental Mnmal Optmzaton, n B. Scholkopf, C. Burges, and A. Smola (Eds.) Advances n Kernel Methods Support Vector Learnng, MIT Press, [40] Wa Lam and Chao Yang Ho, Usng a Generalzed Instance Set for Automatc Text Categorzaton, Proceedngs of the 21st Annual Internatonal ACM-SIGIR Conference on Research and Development n Informaton Retreval, 1998, Pages [41] Wa Lam, Kwok-Yn La, A Meta-Learnng Approach for Text Categorzaton, Proceedngs of the 23rd Annual Internatonal ACM-SIGIR Conference on Research and Development n Informaton Retreval, 2001, pp [42] Leah S. Larkey and W. Bruce Croft, Combnng Classfers n Text Categorzaton, Proceedngs of the 19th Annual Internatonal ACM-SIGIR Conference on Research and Development n Informaton Retreval, 1996, Pages [43] Mguel E. Ruz and Padmn Srnvasan; Herarchcal Neural Networks for Text Categorzaton, Proceedngs of the 22nd Annual Internatonal ACM-SIGIR Conference on Research and Development n Informaton Retreval, 1999, Pages [44] M. Krenes, Reuters Corpus problems, trecflterng@lst.research.mcrosoft. com, Oct. 2, [45] " [46] Anne Kao, Re: Reuters Corpus problems, trecflterng@lst.research.mcrosoft. com, Oct. 2, [47] Susan Dumas, John Platt, Davd Heckerman and Mehran Saham, Inductve Learnng Algorthms and Representatons for Text Categorzaton, Proceedngs of the 1998 ACM 7th nternatonal Conference on Informaton and Knowledge Management, 1998, Pages [48] [49] Davd D. Lews and Wllam A. Gale A Sequental Algorthm for Tranng Text Classfers, Proceedngs of the 17th Annual Internatonal ACM SIGIR Conference on Research and development n Informaton Retreval, 1994, Pages [50] Wllam Hersh, Re: medcal classfcaton tools? ddlbeta@scls.rutgers.edu, Feb. 22, [51] Ymng Yang, A Study on Thresholdng Strateges for Text Categorzaton, 26

27 Proceedngs of the 23rd Annual Internatonal ACM-SIGIR Conference on Research and Development n Informaton Retreval, 2001, pp [52], [53] Ymng Yang, Tom Ault, Thomas Perce and Charles W. Lattmer, Improvng Text Categorzaton Methods for Event Trackng, Proceedngs of the 23rd Annual Internatonal ACM-SIGIR Conference on Research and Development n Informaton Retreval, 2000, Pages [54] Ronen Feldman, Ido Dagan, Haym Hrsh, "Mnng Text Usng Keyword Dstrbutons," Journal of Intellgent Informaton Systems, Vol. 10, No. 3, May 1998, pp [55] Introducton to the ACM Computng Classfcaton System [1998 Verson] 27

基于词语关联度的查询缩略*

基于词语关联度的查询缩略* * 基于词语关联度的查询缩略陈炜鹏 1, 付瑞吉 1, 胡熠 2, 秦兵 1, 刘挺 (1. 哈尔滨工业大学计算机科学与技术学院社会计算与信息检索研究中心, 黑龙江省哈尔滨市,150001; 2. 腾讯公司搜索平台部, 广东省深圳市,518057) 摘要 : 冗