ѧ
JOURNAL OF SOFTWARE
2000Vol.11No.3P.328-333



ʽϢ˷о
ﷶء
ժҪʽϢ˷ӶǶûϢ,ͨȻѡĹ,ﵽϵͳܵŻ.ͬʱԵ˼л,˼̳Сĸ,˹ϵͳ.ַѵʱ䣬߹,ͬʱС˽ѵ.
ؼʡϢ,Ϣ.
ͼšTP393
Evolving Information Filtering Method
TIAN Fan-jiangLI Cong-rongWANG Ding-xing
(Department of Computer Science and Technology Tsinghua University Beijing100084)
AbstractEvolving information filtering method presented in this paper describes user's information needs from multi-aspects simultaneously,and improves system filtering performance through a process like natural selection.Inspired by object-oriented programming language,this method also introduces concepts such as inherit and classtree,which make filtering systems easy to use.This method can shorten training time,improve filtering precision,and reduce the relevance between filtering results and training sequence.
Key wordsInformation filtering,information processing.
ϢѸ,Ϣ(information filtering)õԽԽ㷺Ĺע.ϢϵͳûϢԶ̬Ϣй,ûĵ͸û,߻ȡϢЧ.ϢҪǶĵûϢԵжҪ׼ȷͬʱѵʱӦܶ.SIFT1ݵȴͳϢϵͳ,ûֹؼϢļ(profile),ṩطŻ.Щϵͳȱ,˽ʼ״̬ѵĵԺܴ.Amalthaeaϵͳ2ȻѡĸڸϢ,ȡ˽ϺõĽ,ѵ̫,ûʵ,޷ʵ߲,Ҳ޷û.廪ѧѧ뼼ϵƵϢռͷϵͳTH-InfoBaseȻѡͻ䡢ӽֲȸ,ڷʵ˽ʽϢ.ϵͳṩԴû߸Ϣ˷,ʵ,ϵͳвõĽʽϢ˷Чѵʱ䣬׼ȷ.
1 ʽϢ
1.1ʽϢ
ͳϢǶprofile,Ȼͨһѧϰѧϰ,ĵĽʽϢȻѡĸ,̳е˼.
˵ǣϵͳԱĿ,ѵϢļ,ûַͨʽϵͳеϢļѸٵõһϸϢļ.ͬʱ,ʽϢļ(E-Profile),ÿE-ProfileаϢ,ǴӲͬǶȷӳûϢ,֮以ྺֻ,ھʧܵĸ彫̭,ĸԷֳ.,ͨľͺ,һȻѡĹ,ʹϵͳܴﵽ.
1.2ʽϢṹͼ
ͼ1,οʾʵ,ʾΪʵ.

Fig.1Evolving information filter architecture
ͼ1ʽϢṹͼ
1.3ʵ˵
1.3.1 ʽûϢļ(E-Profile)(1)
Table 1 E-Profile
1 E-Profile

ParentT-NumB-ProfileNum
B-Profile 1Credit
B-Profile 2Credit
......
B-Profile nCredit

ڴͳϢϵͳУûϢļ(profile)һ(T)Ȩ(Tw),ʽΪ(T1,W1)(T2,W2)...(Tn,Wn).ĽprofileչΪE-Profile(evolving-profile),Ϊ,ͳʽprofileprofile(B-Profile).E-Profileײ,Ҫָ丸ڵParentָ롢ѵT-NumB-Profile.ǶB-ProfileB-ProfileζCredit.
Ϊ˱ڹ,վ(Web master)E-ProfileһνṹϵͳE-Profile(system E-profile lib),ûE-Profile򱣴User E-Profile Lib.
1.3.2 б(inverted lists)ʵ(term dictionary)
бܷӳĵȨؼ,ʽB-Profileͬ.Ϊͼ洢ռ,ɵбʱϵͳǽгֵĴʶΪ,ֻE-ProfileгֵſΪ,ʵSystem E-Profile LibUser E-Profile Lib,Ϊĵʱ.
1.3.3 ĵ(document)˺ĵ(filtered documents)
ĵϢϵͳĻλ,һĵһԶȻƬ.˺ĵĵûϢصĳ̶,س̶ֵضϵĵ,ʽΪ(D1,S1)(D2,S2)...(Dn,Sn).
1.3.4 Ϣ(feedback information)
ûԶԹ˺ĵеĵϢس̶ȴ,Ϊ5,Ϊ0,Ϊ1,ϢʽΪ(D1,S1)(Di,Si)...(Dm,Sm)(mn).
1.4Ϊʵü㷨˵
1.4.1 (classtree builder)
ϵͳʼʱ,WebMasterʹΪϵͳϵͳE-Profile.ϵͳE-Profileνṹ,ǰĵWorld,һƪĵԱһ,ܹκĶ롰(others).
νṹÿE-ProfileʹñעѵĵϽѵ,ÿE-ProfileݱעΪѵĵ.ɷ,Ϊm,𼯺Cset=C1,C2,...,CmѵĵΪn,ѵĵDset=D1,D2,...,Dn,Di=Vi;Si1,Si2,...,Sim,ViĵDiʾ,SijĵDiCjس̶,CjB-Profile(Pj)ʽõ:

ʽĺǣCjĵֵڦεĵ,ֵڦεĵ .ھProfileпܰܶ,ȡȨߵNյB -ProfileNһϵͳ.ȡεĲֵͬ,ԵõͬB-Profile, ͬCjE-Profile.
1.4.2 ûϢļ(user E-profile generator)
ϵͳE-Profile⽨,ûĽṹĵĵ,ѡԼ ,ڴE-ProfileĻԼE-Profile.ɵķ
(1) ֲ(transplant).ΪP1P2,ʵϾȫһE-Profile.
(2) ӽ(crossbreeding).ΪP1P2;P3,P4,еϢ (P1,P2),µϢļ(P3,P4),·ʽʵ֣
ȵõ㣺
n1=rand(1,sizeof(P)-2),n2=rand(n1,sizeof(P)-1).
Ȼ,P3,P4P1,P2̳:

(3) ޽(inoculation).Ϊ;P2,еϢļ(P1) ʾĵ(Ds),µϢļ(P2),·ʽʵ֣

n=sizeof(Ds),ѵĵDs=D1,D2,...,Dn,Di=Vi;Si1 ,Si2,...,Sim,ViĵDiʾ,SijĵDiCj س̶.
ͨ3ֲ,ûעʱԺܷظϵͳеԼṩʾĵ õԼĳʼE-Profile.
1.4.3 ʵ(dictionary manager)
ʵȸһʱʵ,ϵͳE-Profileû E-Profileôʵ.ҲͬʡʸԤ.
1.4.4 ĵ(document parser)
ĵڲ©ؼϢͬʱĵתɱڸЧĽṹ,ĵʹռģͱʾ.ؼTkĵiеȨWik£
Wik=Tiklog((N+0.5)/nk)/log(N+1.0)
TikĵiйؼTkĳִlog(N/nk)ѵĵTkĵĵƵ;Nѵĵĵ;nkѵĵаTkĵ. 
1.4.5 Ƚ(classifier)
ʱ,E-ProfileеÿB-ProfileĵбȽϣõһƶ,ƶȵķƶȣ3.B-ProfileΪP=p1,p2,...,ptt,ĵΪD=d1,d2,...,dtt,tǴʵеĸ,еÿԪȨ,ǵƶȿ¹ʽ.
ĵΪ0ĵȫ롰,ҪƳ̶.

һE-ProfileйnB-Profile,ôĵd,õnƶ ɵƶS=S1,S2,...,SnT,ͬʱE-ProfilenB-Profil eζ(credit)ҲһζC=C1,C2,...,CnT,ĵ ƶS=CTS,һĵDset=D1,D2,...,Dj,ƶȣ SԵõÿB-Profileĵ,ƶȣSԵõE-Prof ileĵ.
1.4.6 û뷴(representation/feedback)
˺ĵƶṩû.ûȼϵͳжûϢ ƶߵǰNĵ,Nֵûָ.ûԶԼĵ,۷ Ϊ5.
1.4.7 (evolving controller)
(1) ʽѧϰ
B-Profileü(reinforcement)㷨4ݽѧϰ

SijǵiB-Profileĵdj,Vjĵdjʾ, ǵ׼ȷȵ,һȷѡĲ.ͨʽ,ÿB-Profileÿη ûʵϢһСƶ,Ӷﵽ߹׼ȷȵĿ.
ͬʱڶB-Profileʱ,пܳһB-ProfileΪضȺܸߵĵȫ ϵͳѡе,Amalthaeaϵͳ,ζŸùԶ޷ֵ.ķ ԳΪʽѧϰ,еB-Profileͬȵѧϰ,.
(2) Ͳ
B-ProfileζȱʼΪ1/n,nE-ProfileB-Profileĸ., ϵͳʼʱ,еB-ProfileͬĻ.ڽй˲õϢ,ǵ ζȱ.µĻԭǣǳ϶ȴûȴû϶,ô ζȽͣ뱻һ»ƻ뱻϶һ»ζ.ʽΪ

B-ProfileºζԺ,ζӳ䵽01䣺

(3) ̭
ûṩķﵽһֵ,ϵͳͨӽи.ǣѡζ (credit)ߵB-ProfileΪ,ΪֻбֺõB-Profileзֳ ʸ.ӽõµB-Profile,ѰֲѵB-Profile, .ѡζC䣺
C=C(Fmax-Fn+N)0ӣ1
CζȣFmaxǴӵǰE-ProfileĸB-Profileеõ෴FnǸprofileõķNһύûĵ,һηСλϵͳ.ζǻ¼裺ηͺټ ﵽͬζȵB-Profileǲͬ,ԽᡱԽǰ;.
2ʵ
2.1ݼָ
ʵʹõݼ500HTMLĵ.10ֲͬϢ10û,500ĵ˹ע,ÿĵ10Ϣس̶ȼΪS1,S2,...,S10.׼ȷȵָ滯ľȺͲȫ(normalized precision and recall)3.

Nʾ˼еĵ,RELʾĵ.
ֵԽ߱ѡĵûʵϢԽ,ȫֵԽ߱© ĵԽ,ֵͬʱȡýϸֵ.
ѧϰٶϵͳȶشﵽû̶ʱĵ,ѧϰٶûϸ Ķ,Ľͨݺͼʾֱ۵˵ѧϰٶȷ.
Ϊо˽ѵ֮Ĺϵ,ξָDiffι˽ ֮Ĳ.˼ΪDset=Dm,Dm+1,...,Dm+n,ζԸ ˼ϵضжϷֱΪ(Sm,Sm+1,...,Sm+n)(Sm,Sm+1 ,...,Sm+n),DiffΪ

DiffֵԽ˽Խ,ǵʵ,ЧѵĹϵԽ.,DiffԽСԽ.
2.2ʵ
ʵ3ֹбȽϣ
(1) ʽ.ÿE-Profile4B-Profile,ÿ20ĵķϢһ̭,ÿθB-Profile.
(2) ѧϰĻ.ÿE-Profile1B-Profile,ֻѧϰ,̭.
(3) ѧϰĻ.ÿE-Profileа1B-Profile,ѧϰ,̭.
ΪԹ˽ѵĹϵ,ʹɵĵжʵ.
2.3ʵ
2.3.1 ѧϰٶ
ͼ2ͼ3Կ,ʽϢѧϰ,(ȺͲȫ)ȻĹЧҪ.ʵǷ,ڲĵ͸,ʽϢĹв,̭.,ʽϢǺ,ʹֲ,ҲַҪ,ӰǱڲȶ.Ȼ,оȶ̭ǽһĹ֮һ.

Fig.2Comparison of the precision of there filters
ͼ23ֹ˾ȵıȽ

Fig.3Comparison of the recall of three filters
ͼ33ֹȫʵıȽ
2.3.2 ѵ޹
ͼ4ʾʽѵ޹ԷֽϺ,ֵעǣһʼ־ͱֹҪõö.ΪÿE-ProfileͰB-Profile,Ҳ˵,ÿE-ProfileͼӶֽǶĵж,ԱֱȽϳɫ.

Fig.4Comparison of three filters'diff value(diff is the difference between filtering resultscaused by different training sequences)
ͼ43ֹdiffֵıȽ(diffǲͬѵеµĹ˽֮Ĳ)
3 ᡡ
ĽһֽʽϢ˷,÷ڷ෽ɡϲѵȷ涼µĳ.ʵ,÷й׼ȷѵʱ̡ѵ޹صŵ,ʺڸ׼ȷȵĶƻϢϵͳ.
оõ863߿ƼĿ(No.863-306-zt01-03-1)IBMоĻ.ﷶ,1974,ʿ,ҪоΪWWWӦϵͳ,Ϣɼ,Ϣ.,1975,˶ʿ,ҪҪоΪϢ͹.,1973,,ʿʦ,ҪоΪзֲϵͳ,WWWӦϵͳ.
ͨѶϵͳϵ:ﷶ, 100084,廪ѧѧ뼼ϵ
ߵλﷶ(廪ѧѧ뼼ϵ100084)
(廪ѧѧ뼼ϵ100084)
(廪ѧѧ뼼ϵ100084)
ο
1Yan T Y,Garcia-Molina H.Sifta tool for wide-area information dissemination.In: USENIX Association ed.Proceedings of the 1995 USENIX Technical Conference.Berkeley,CA: USENIX Association,1995.177186
2Moukas A.Amalthaea: information discovery and filtering using a multiagent evolving ecosystem.Applied Artificial Intelligence,1997,11(5):437457
3Salton G,McGill M J.Introduction to Modern Information Retrieval.New York: McGraw-Hill,1983
4Narendra K S,Thathachar M A L.Learning AutomaticAn Introduction.Englewood Cliffs,NJ: Prentice-Hall,1989
1998-12-07յԭ,1999-03-30յ޸ĸ
