ѧ
JOURNAL OF SOFTWARE
2000Vol.11No.4P.545-550




BookmarkϢ
¬顡غ곬ܴ
ժҪϢ(information filtering)ǽϢѯѵҪ,ļûϢĻȡϢƥ㷨.ĴInternetϽϢ˵.ûϢȡ,ͨչϵBookmark,ûϢ,ֱûû.Ϣƥ䷽,ranking㷨.ʵ,ȴͳ㷨ȸ.Ϊʵ,Bookmarkϵͳ,ϵͳͼ,Ĺ.
ؼʡϢ,෨,Bookmark,Internet,WWW.
ͼšTP393
Network Information Filtering Using Bookmark Service
LU Zengxiang GUAN Hongchao LI Yanda
Department of Automation Tsinghua University Beijing 100084
AbstractInformation filtering is an important method to alleviate information overload. How to express user's information needs and how to rank them are two main problems in this area. This paper focuses on these two problems. Bookmark service, the solution that is an extension of bookmark function in browser, is used to catch user's information needs. The evaluation of the documents is used to represent user's information needs. Maxine Margin method, a novel ranking algorithm, is designed to increase precision. An experiment proves that it performs better than the traditional methods. A system called Bookmark Service System is designed for implementation. The system construction is given, and its main function is also introduced.
Key wordsInformation filtering, maxine margin method, Bookmark service, Internet, WWW.
 90ڻķٷչ,Information Overload.ͳϢѯϢʽнϺõı֤.,绷µϢѯȴͬϢݬ룬ʽ,û֪ʶβܴ,ϢҲǧٹ.ĿǰõҪϢѯ(Internet search engine,ùؼʲѯϢ,Altavista,Infoseek,Excite)Ŀ¼(Ϣ˹෽,֯һ״Ŀ¼ṹ,Yahoo!,Looksmart).ʹʱ,ûҪϢɹؼɵQuery.ֻҪQueryͬ,Ĳѯͬ,ûϢƫ.ûҪԼβҵʵQuery.,ϢǶ̬,ûʱֱ仯,Ϊ˻ñ仯Ϣ,ûֻвϵϲѯͬ.Ŀ¼,ûݷϢСΧ,ǣĿ¼ṹǹ̶,ûʱûͳһı׼,,ʱҲ.,Ϣ˹ɵ,ԣϢܴܵ,гɱҲܸ.,ҪҵԼҪϢ,ķѴʱ.ͳϢѯûϢ,ˣϢѯоܵ.,1997EI¼±1994һ.ĽϢ˺ͻѧϰĽǶȣʹһЩ.
,ϢѯϢ(information filtering,IF),Croftף1ָIFϢѯ(information retrieval)Ĳͬ,IFעûĳ(long term)(ָһʱ,ȽϹ̶Ϣ).IF,ûʾprofile,profile൱IRй̶ġquery,IFϵͳprofileԽϵͳ(ranking),ͬʱûֱӻӵصõϢ,profile޸(revising).ڷĴ,ѧϰķϢѵõ㷺,ҪķУBayesѧϰ緽KNN(K nearest neighbor)SVM(support vector machine)ȣ2.
Ϣ˼ڻϢѯǷǳҪо,ڽϢĸԻ̬Լ߱ѯϢûĿöкܴ.Ϣ˵оʵϵͳܶ.,Syskill&Webert3ͨؼʱûϢ,Bayesй;WebWacher4ݸûһṹƵĿ,ûѰϢ;Letizia5ݿԼû·,ȡûϢ;WebHound6ݲ˵ķ,ͬͬ۵ûϵһ,ΪͬϢ,,֮ͿԹϢĹ.
ṩϢ˷ĹؼǻûϢϢ(Ƽ)㷨.ַʱ̼ûϢ,ͬʱûĵϢ仯,ܼϢƥ,ʱ֪ͨû.Ϣ˵ҪûProfileıʾԼRanking.еϢϵͳһùؼʡϢû,ڲͬıʾԲòͬϢƥ㷨.,ùؼʱϵͳ,Booleanģ͡ռģͻģ͵ȣ3ݣ÷Ϣϵͳ,Զķ.ȻҪûԼϢ͸.һInternetû,ɺʵĹؼʡѡص,һѵ.ЩϢϵͳϲϢм,ûϢϢ׼ʷûжĽ.
ڱ,ûµֱӷӳûϢ,ͨBookmarkΪû,ȡûϢ,ͬʱûϢƼ.ΪϢƥľ,ռ䷨,(maximize margin).ĵ1ڽϻûѼϢķ.2Ϣƥ㷨,෨й˵㷨,봫ͳ㷨Ƚϵʵ.3ڽʵʵϵͳBookmark.4ڵóۣһо.
1ûϢ
Internet,ϢϵͳʹõûϢȡкܶ,Ҫֳ֣(1) ûд;(2) ûϢ.
û趨Ϣͨ趨ؼ(informant)趨(my-yahoo),ַʽҪûܽԼϢ.Աͷģ,ûַͨϢ.,ΪҪûд,ϵͳûȤ仯.
ûϢѯ̵ķԶûϢ,䷽ûնһӵϢ(agent),ϢûwebʱϢϴ͸Զ˵ķ,Ϣ֯,зûϢƫ,ûϢƫýµϢƼ(Alexa,Bullseye).ûȤʱ仯,ûΪϢӳûϢǶһ,ʶϢ˺ܴ,һҪûʹ֮ǰԤָһ,ûĸ.
ûϴ洢BookmarkûϢķڡû,һЧķ.Bookmarkд洢ϢûĵģҪ¼ԱԺٶ.BookmarkṹϢ洢ȷеرû.ǿûµûϢ.ԴBookmarkĳһƼĿ¼,Ϊûϲ,Ϊѧϰе;Ŀ¼,ǾƼûбѡе½Ϊѧϰķ.ռ䷨ʾ,Ϳûѧϰķ½Ƽ.
2Ϣ(Ƽ)㷨
ûϢʾĲͬ,õϢƼ㷨Ҳͬ.еķùؼʹûprofile,Բֱƥ䷽Ƽ,Ҳռ䷨,ʹ׼Ƽ.BookmarkϢƼ,µûprofileʹûµϢԱʾ.һؼҲԿһƪ,ַԸùؼʱʾķ.
ʵǸûȤĺͲȤƼ.ⷽо׷ݵIR(information retrieval)еRelevance Feedback.۷,Relevance Feedbackĳɹܶ,Rocchio7ݡBayes.BookmarkϢ,ûķԺܴ,ΪƸ׼ȷRankingṩ.ڼҪеоɹ֮,෽.ʵ,෽иõ.
2.1ͳRelevance Feedback
ͳRelevance Feedbackкܶ8,9,ʵ÷ڶqueryĵ,Ҫ,һøģͽquerytermȨֵterms,һռ䷨query.
Ϊܷ෨,Ҫռ䷨.ռ䷨,Ҫʾ,ҪԤ.,ԤĲΪȥstopword,the,that,stemming,罫played,playingΪplay;ҪдʵĹ.Ԥ֮,±Ϊһʼ(terms).ʼеÿ(term)ҪһȨֵ,ͨǲô(term)TFIDF(term-frequency inverse-document-frequency)Լ.һ¼,ʹTFIDF,iдkȨֵʽ㣺
dwik=tfik*(log2(n)-log2(dfk+1)).(1)
tfikΪkiеƵ,dfkΪk,nΪ.
֮ƶͨ.wjΪj,i,jƶRijʾΪ
(2)
queryʾq,RiqRanking,ڴ˻,ͳķǽµϢתƵquery.Rocchio10,乫ʽΪ
(3)
q1ΪµĲѯ,q0Ϊԭʼѯ,RkΪkƪµ,SkΪkƪµ,n1Ϊ,n2Ϊ,ºͦΪƲ.ʵ=0.75,=0.25ʱ,Ч.
ڸģ,ĸֵ,ԾdjQĸ.ڶ,ʹBayes,±ʾterms,ѡϢnterm(Ai),μף3,ó
(4)
P(Ak=Tkj|Q)(ڷQ,term(Ak)ĸ)P(Q)(¼зQµĸ)Դѵеõ.ʽ(4)Զ½Ranking.
2.2෨
ڴͳRelevance Feedback,ϢͨqueryӰRankingĽ.RankingһӰĹ,¿ռû϶ȽһάӰf(d).IFУf(*)profile.ҵһӰ䷽,ʹ벻ص¾ֿ.ǿӰ
Ri=wxi+b, i=1,,l,(5)
wΪӰ䷽,xΪ,lΪѵ(),bΪ.ͿͨRiʵRanking.
ѵԿɷֵ,Ӱ䵽һάʱ,Աȫֿ,һΨһʹ벻ԶӰw*.Ƕ־Ϊ,ʹw*ranking,γRanking.ڱ֤Ϣ,ȡתΪѰŵ10,㷨£
Ŀ꺯min{w2/2}
yi(wxi+b)1 i=1,l
Lagrangeã
Ŀ꺯
ɿԵó
(6)
(7)
ż⣺,ֵͨⷨi,ʽ(6)ý.ı,ڿռάܸ,󲿷ΪԿɷֵ2.
Բɷֵͨɳڱi,Ϊ
yi(wxi+b)1-i, i=1,,l,(8)
ŻĿΪ
(9)
CΪͷ.C>i>0ӦĵЧ,ĵɾȥ,ʽ(6)ý.ַʹϵһôǲؽвĵ.ͳѧϰۣ11ݵ˼,˾кܺõƹ.
2.3ʵ
ʵʹReuters-21578ݼ .Reuters-21578ݼеʵ,Ҫõзַʽ֮һΪModApteз,е9 603ƪΪԼ,3 299ƪΪۼ.з,ѡ10.ȥstopword;stemming,10 083terms,෨(ԺMaxMargin)Rocchio,ʹȫterms,tfidfȨֵٽйһ,γµ.Bayes,ѡϢ900terms.
Ϣѯ,÷Ҫ׼ǲ׼(precision)Ͳȫ(recall).һ,ָɷ.ڶ㷨ܱȽʱ,precision=recallbreakeven2.Ҳô˷.
ڷ,ѡʱ,֤55;ͬ¶Ա3Ranking.ͼ110011P-Rͼ,ݻ÷Ϊѵȡ100,ظ5,ȡƽٸݸȡ10Ȩƽ.ͼ23ַ淴仯,ȡΪ100,200,500,1 000,2 000,3 299,ÿַ,ۼȡ5,Խȡƽ,ٸݸȡ10ƽ,Ϊbreakevenֵ,Ϊ.ʵSUN Ultra2վϽ,㷨ʱ20.,ͷC=1 000.

ٲ׼ʣڲȫʣ
Fig.1
ͼ1

ٲ׼ʣڲȫʣ
Fig.2
ͼ2
ʵ,Ranking봫ͳиõ,ͬ,ȿ10%.ķС,෽ܱõ.
3Bookmark
BookmarkϵͳһϢϵͳ.ʹBookmarkûӿ,ûϢ,ûϢƼ;BookmarkϢ,ʹRanking㷨Ϣ;ϢȡϢ,ͨϢƼû;ûBookmarkеַ,Ϣи;ûֱӻõϢ,ͨBookmarkӵϢԴݿ,ҿͨƼû.ϵͳͼͼ3ʾ.

ûûǩ񣬢۹ܸ£ϢԴݿ⣬޴Ϣ
Fig.3
ͼ3
ϵͳhttp://test.au.tsinghua.edu.cn/ʵ.ڽʱ,ϵͳҪ洢Ϣ,ǽµı־д洢,ֻ洢.ϢƼ,Ȼ㸴,ڲʵʱûƼ,ٶȲҪ.Ϊ˹Bookmark,ҲԼϢ(intelligent agent)һЩҪ(Internet search engine)лϢ,ҪרŵϢ(agent)شоȡϢ,ԴΪƼز.
BookmarkϢкܶ.ûԵԼеBookmarkļֱʱͨͻǩ,ҿԶиֱ༭.ûȷضµԼǷһ,ͨϢʹϢƼΪ׼ȷ.ûƼķΧ,ϵͳûϢƼϢֱӲBookmarkṹ,ȫûϰ.,ϵͳʹBookmarkʵ绯,洢ûBookmarkϢ,,ʹûκεطƽ̨,ӵһµBookmarkϢ.
4 
ͨBookmarkϢЧķ.ûµۻȡûϢ,ͨBookmarkûƼϢǷûʹϰߵ.ͬʱṩһµBookmark,û.ûϢй,Rankingкܺõ.Ӧڷʵʱ,رڳߵϢ.
ҪǻݵĹ,ⷽкܶҪһо⣺(1) 봫ͳĹؼʷ,µۿƹ㵽Թؼʵ;(2) ڶʱ,ƪ,ںܶ,ֻһûĵй,Ҫϵͳѡ񲿷½Ƽ(3) ûµǶص,ֻáǡ񡱱׼ʧϢ,Ҫо༶۵Ranking(4) ϢǶֵ,öµ۹profileʱ,۵¼̶,Թ̶¼з֮,Ϳʵֶֹ,⽫һЧĶֹ˷.
ϵͳ¼ûBookmarkϢΪ˵ʵṩ˺ܺõĻ.û֮ԽϢƼķ.޹,ܱ֤Ϣ.⽫ΪһַǳҪϢ˷.
¬飨廪ѧԶϵ100084
غ곬廪ѧԶϵ100084
ܴ廪ѧԶϵ100084
ο
1Belkin N J, Croft W B. Information filtering and information retrieval: two sides of the same coin. Communication of ACM, 1992,35(12):2938
2Joachims T. Text categorization with support vector machine. Technical Report. LS VIII Number 23, German: University of Dortmund, 1997
3Pazzani M, Billsus D. Learning and revising user profiles: the identification of interesting web sites. Machine Learning, 1997,27(3):313331
4Armstrong R, Freitag D, Joachims T et al. WebWatcher: a learning apprentice for the World Wide Web. In: American Association for Artificial Intelligence ed. Working Notes of the AAAI Spring Symposium Series on Information Gathering from Distributed, Heterogeneous Environments. Cambridge, MA: AAAI Press, 1995. 612
5Lieberman H. Letizia: an agent that assists web browsing. In: AT&T Labs ed. Proceedings of the International Joint Conference on Artificial Intelligence. San Mateo, CA: Morgan Kaufman Publishers, 1995. 924929
6Lashkari Y. The WebHound personalized document filtering system. 1997, http://rg.media.mit.edu/projects/webhound/
7Rocchio J. Relevance feedback in information retrieval. In: Salton G ed. The SMART Retrieval System: Experiments in Automatic Document Processing. Englewood Cliffs, NJ: Prentice-Hall Inc., 1997. 313323
8Harman D. Relevance feedback revisited. In: ACM ed. Proceedings of the SIGIR'92. Copenhagen: ACM Press, 1992
9Allan J. Incremental relevance feedback for information filtering. In: ACM ed. Proceedings of the SIGIR'96. Copenhagen: ACM Press, 1996. 270278
10Cortes C, Vapnik V. Support-Vector networks. Machine Learning, 1995,20(3):273297
11Vapnik V. The Nature of Statistical Learning Theory. New York: Springer-Verlag, 1995


