о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999 36 8 Vol.36 No.8 1999



WWWϵϢھʵ
ޡΡ̳ɡ컪Ÿ
ժҪInternetӦõռWWWѾչΪһ޴ķֲʽϢռ䣬Ϊûṩһ߼ֵϢԴ.InternetеĿԡ̬칹ԣʹû׼ȷݵشWWWϻȡϢ.нھ˼WWWϢϢЧȡ⣬WWWϽϢھõ㷨ͲԣҪһռģͺ͸ĽRobotϢھϵͳʵ.ʵϵͳܹϺõؽWWWϵϢԶȡ.
ؼʡϢھھVSMWWW
ͼšTP391
THE TECHNOLOGY IMPLEMENTATION OF INFORMATION MINING ON WWW
ZOU Tao, WANG Ji-Cheng, ZHU Hua-Yu, JIN Xiang-Yu, and ZHANG Fu-Yan 
(Department of Computer Science and Technology, Nanjing University, Nanjing 210093)
(State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210093)
AbstractWith the development of Internet, World Wide Web has become a huge distributed information space, which provides users a massive and valuable information resources. But with Web's rapid growth, quickly obtaining what users need on WWW is getting more difficult because of Internet's opening and heterogeneity. Information mining on WWW is a new technology that adopts data mining technology to retrieve information on Internet, and can solve the problem of rich data and poor information in WWW. Described in this paper are the method, algorithm and strategy of information mining on WWW. The design and implementation of a prototype system, which adopts vector space model and modified Robot technology, are presented. 
Key wordsinformation mining, data mining, VSM, WWW
1
ԴWWW(world wide web)1991굮ѾչΪӵнûԼ400վ㡢3ҳľ޴ֲʽϢռ䣬Ϣָʽ1.WWWԳıʽָûģ˴ӼϡҵϢűϢȶʽϢΪûṩһ߼ֵϢԴ.Internetһпԡ̬Ժ칹Եȫֲʽ磬ԴֲܷɢûͳһĹͽṹ͵Ϣȡ.ο١׼ȷشӺ嫵ϢԴѰҵϢѾΪûһ⣬ҲνRich Data Poor Information.Ľھ(data mining)˼Ϣ,WWWϽϢھļؼҪһϢھʵϵͳIDGSʵ.
2WWWϵϢھ
ϢھھϢеӦã2.ϢھָڴѵĻϣõݶԴΪݽĿĵϢȡ.ϢھϢõļк֮ܶбʵĲͬ.еһ㶼RobotݿͲѯ3ɣ1ݣRobotWWWϵĿԵģ书ܾǾķݣֵȫݿ⣬ѯֻǸաûĲѯȻݽΪ򵥵ƥԣʹý϶Ǽ򵥲ģͺģģͣнвңַû.ϢϵͳֻܴԹؼʽʾļĿ꣬޷ûʽĸģĿ꣬ϢھϵͳܹȡĿϢȻĿнĿĵѰѰĵύû.ϢھϵͳҪȡϢɼƥ3ֹɣ¶صļ.
2.1Ŀʾƥ
ĿʾָһĿϢϢھʱЩδ֪ĵûĿس̶ȣĿʾĹ̾ھģ͵Ĺ.Ŀʾģж֣õв߼͡ռ͡͵.Ӧý϶ЧϺõĿʾռģͣvector space model VSM3.
VSMУıĵΪһɣÿһTiĵеҪ̶ȸһȨֵWi.ǿԽ俴һnάϵΪӦֵÿһƪĵӳΪһʸųɵռеһ.ûĿδ֪ĵôʸʾӶĵϢƥתΪռеƥ⴦.ûĿΪUδ֪ĵΪVߵƳ̶ȿ֮ļннԽС˵ƶԽߣƶȼ㹫ʽ£

2.2ȡ
ĿʾдTȨֵѡȡΪȡȡھĿ깲ȡ̣òԵӽֱӰ쵽ھ򹤾ߵЧ.
ʡͶĵĻԪأڲͬݵĵУƵһĹԣ˿ɸݴƵԽĿȡ.ͬĴĵеǲͬģôʣ硰ġtheĵжкܸߵĳƵ޷ĿݣƧĵгֵĴ٣ƵͳԺȷʶΪ.һЩĵгֵƵʶͬԲҲΪ.һЧ߱
1ȫԣܹȷʵʾĿݣ
2ԣܽĿͬĵ.
ɵãĵݵĹڴĵƵĵгָôĵƵ.ǿɹȨֵۺ

бʾTkĵDiеĳƵNʾȫĵnkʾTkĵƵ.
ϢھĶһ㶼HTMLĵHTMLĵдںܶϢЩϢĵкܸߵĸԣ˿ЩϢȡ.ȡʱCofTitleCofLinkTextCofH1CofH2һϵHTMLĵеĵıļȨϵԳڲͬĴԲͬƵʼȨϵ.
2.3ıϢԤ
ڶĵȡǰҪȽıϢԤҪӢĵStemmingĵĴз.
ӢĵʵĶʽȡʸɵḺ́Stemming.Ӣĵھʹʱʱȥʱȶʽ硰walkwalkedwalkerwalkingеĵʡݴʡʵȶʽ硰useusefulusefulnessusefullyȣǵĴʸͬģڽдƵͳʱӦΪͬĴʴ.ʵStemmingһķǽǰ׺׺ʽƥ䷽ʽʵ.
ͬӢĲͬиûйеķָո񣩣ĵĴƵͳǰҪĵзִʴ.ıķִʾıĸָıʽתΪɢĴʽ.ıķִʷкַ֣ܶõҲͬϢھԷִʴҪнϸߵʵʱԣԷִʵ׼ȷȲ̫Уһķִʴʣ˿ԲýΪ򵥵Ļڴʵƥ䡢ʱִʷ.
2.4ԴϢɼ
WWWԳıʽ洢ϢṩϢģWWWϽԴϢɼҪͨRobotʵ֣4.RobotһWebҳеĳӽԶεĳ򣬲ܹͨHTTPȱ׼Эεҳ.WWWһ״ṹϢռ䣬ǿɽΪһͼҳΪͼеĽڵ㣬ҳеĳΪͼе.ǿʹͼ㷨㷨͹㷨б.
ԴϢɼǽϢھҪ.дڵϢǳ޴ΪھЧʣԴĵɼ׶ξӦϢԴһĹ.ڽھǰӦȸھĿ꣬YahooAltaVistaԴϵͳнԴַѯȡվ㷵ؽĽҪɼΧȡΪϵͳɼԴַ.Ϊ߲ɼЧʣɶÿһվһRobotвɼĵ.ڲɼУӦʵheuristicԣָRobot·ѡͲɼΧԼĵɼäĿ.
2.5ıϢ
WWWУкܶͼϢPDFPSȸʽ洢ĵͼOCRķݷȡʹϵͳúʮӴ͵Ч.ǵWWWеķıϢһ㶼ǲá-ļԵʽָûģÿļһıӵıڡA/AǶԼ֣ӦЩıǶӵķıĸ߶ȸԿԲ÷ıļıȡӶıϢתΪıϢд.
2.6ָ
ھϵͳ֤һòԼͽ֤ķòȫʣrecall;ȣprecisionϢھϵͳЧ.ȫΪھ򵽵ĵʵĵ֮ȣΪеĵĵ֮.һϢھϵͳӦͬʱнϸߵĲȫʺ;.
3ʵϵͳʵ
3.1IDGSϵͳ빤
IDGSϵͳ(information discovering and gathering system)ΪWWWԶӢļϵѼƿģIDGSܹûύھĿWWWԶûϢ.IDGSϵͳռģͣVSMͻڴƵͳƵȨֵۼȡԴվѯĵɼģʽƥ4ɣͼ1ʾ.


ͼ1IDGSϵͳṹͼ
IDGSϵͳĹ£
1ȡûύھĿȡھĿʸ
2վѯʸȡȨֵ310Ϊѯؼ֣ԴϵͳͲѯ󣬽صĽURLΪĵɼ㣻
3ϢɼRobotӲѯԴURLʼĵɼ
4ģʽƥ䣺ȡԴĵʸƥ䣬ѷֵĵύû.
3.2ؼĴ
(1) Ƶͳ
IDGSϵͳӦΪļĵĵһ㶼רҵʻ㣬ڽȡʱͨʻзֺʹƵͳ.ΪϵͳʵʱԺЧʣ˴͵ͨзͳƴʱרҵʵĵĴƵͳƺӢĵStemming.רҵʵֻڱпֵܳרҵδ¼ͨʻ㣬ڱ֤ȡ׼ȷԵǰ´ϵͳЧ.
(2) ʵ
ΪVSMģҪ໥ȻԶ֮ìܣǽ3ʵ䣺ʵ䡢ͬʴʵ̺ʴʵڴƵͳƣʵеĴҪںϱ־ܵĶ.дƵͳƺȡʱʵеΪʾддƵͳƹʽΪ

ʽУTMfΪʵƵTTfΪͬʴƵTIfΪ̺ʴƵeΪչϵȡֵھΧ;ȷȡֵΪ01.ʾĵеĳƵͬʴ̺ʴ3ֵĴƵȨۼƵõ.ͬʴʵ̺ʴʵȿԽȻԶ⣬ֿͬʱɶӢıStemmingʵʽΪͬʴ.ʵӦлԸҪӦĽʴʵ͹ʴʵ߲ȫ.
(3) ȡƥ
IDGSϵͳôƵͳƺVSMģ͵ķȡģʽƥ.ڶHTMLĵȡʱIDGSCofTitleCofH1CofH2CofH3CofBoldCofStrongCofEMCofLinkTextCofNearTextCofImageAltȶʽȨϵڼȨֵĹУԳڲͬʽĴƵӦļȨϵHTMLĵеĸʽϢ.⻹CofHeadCofTailĵϵʵ̧߳ĵʼֹĴȨֵ.ĵݼƶͨĿʸԴĵʸļнֵȷƶֵһȡֵ0.45.
⣬ʵӦĸҲ˹ֻ࣬Ȩֵϸߵ󽵵ϵͳĴٶ.ʵǰ30Ȩֵɸ򣩵ģֵһռȫģֵ85ϣ80ԺӰСеģֵֻռģֵ4%7%ңڶʵʱҪϸߵ£ȡ3080ɴﵽϺõЧ.
(4) RobotĸĽ
׼ȷԺʱЧϢھؼҪ.WWWϽϢھʱϵͳҪԴĵصغٽдäĿĵɼķѴ紫Դ󽵵ϵͳھЧʺϢھʱЧԣ˱RobotʵĸĽʹԴĵĲɼнǿĿԣԼ紫ھʱЧ.IDGSУһȤģͣĵɼģеRobot˸Ľ.


ͼ2Webҳʾͼ
ȤģģʱȤƵһRobotԣͼ2ʾWebҳӽṹ˵Ȥģͽȵβ裺 Ԥ趨һȤֵITȤ׼IB ʼҳA1ĿضIA1ΪҳA1Ȥֵ趨ǰȤֵI=IA1 IITκҳB1Σ B1ҳ棬ҳB1ضIB1ʱȤֵΪI=I+(IB1-IB) IITκҳC1򷵻A1ȡI=IA1ʼB2֧ 裬ֱA1ȫҳ֧.ʵȤģܹĵɼЧԣͨȤ׼RobotηΧ.
3.3ϵͳ
IDGSϵͳǲVisual BasicLotus DominoWindows NTʵֵģAccessݿʽʵ䡢ƵϢѵıRobotɼ״̬.ڲԽ׶Σǽ10Ŀ꣬Լ1000ƪĵ3000ȡ.㷨ֵĵϵͳﵽ˽ϺõЧ.ԡ硷棨http://www.computerworld.com.cn˲ԣ1Ϊɼ100ƪHTMLĵʶʡѧUMϢʵҵĵ뵼ϵͳINQUERYĽͨĵĵ4ݽ˱Ƚ.ϵͳʱ縺صӰܴ󣬱δгķʱ.ԣȡ40£10M̫а1MıϢվ㣬ֻ515.
1IDGSϵͳINQUERYϵͳȽ

ȫ(%)IDGSϵͳ(%)INQUERYϵͳ(%)
1210071.3
2510060.1
4185.347.6
8378.329.8
1007214.5
ƽ87.141.7


IDGSԼļϽʵֵģĵΪԣԲԽͨĵINQUERYϵͳҲIDGSȡ˽ϺõھЧ. 
4
Ϣھھеһµķ֧漰缼ھý弼ı˹ܼȶ.ûͳƵȡʽRobotWWWϵıϢھʵ˳֣̽ȡ˳ĳɹһ̶ϽInternetеԶȡ⣬༼дڽһо.
Ŀõʡί塱ƼĿ(ĿDE96017)
߼飺ΣУ197011ʿооΪϢ֡Agent.̳ɣУ19735ʿооΪϢ֡ýϢ.컪˶ʿоϵͳľʵ.ŸףڣʿʦҪоΪý弼ͼѧھϢ.
ߵλޡΡ̳ɡ컪ŸסϾѧѧ뼼ϵϾ210093Ͼѧ¼صʵҡϾ210093
ο
1Gudivada V N. Information retrieval on the World Wide Web. IEEE Internet Computing, 1997, 1(5): 5868
2ˮƽ. ݲɾع. С΢ͼϵͳ, 1998, 19(4): 7481
(Li Shuiping, Review of data mining. Mini-Micro Systems (in Chinese), 1998, 19(4):7481)
3Salton G, Wong A, Yang C S. A vector space model for automatic indexing. Communications of ACM, 1975, 18(11): 613620
4. WWWϵϢ漼. С΢ͼϵͳ, 1998, 19(6):6671
(Zhang Xiaohui. Information discovery and search engine for World Wide Web. Mini-Micro Systems (in Chinese), 1998, 19(6): 6671)
5John Broglio, Callan James P. INQUERY system overview. http://www.cs.umass.edu/croft
յڣ1998-10-06
޸ڣ1999-05-17
