о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999Vol.36No.7P.870-875



ûģʽھģ㷨о
ܱȪԴߺ
ժҪӴ˿־ھûģʽصǱڹ˿ȺִҵչսԵҪ֧ż֮һ.лE-OEMģͣоۺϿǷӦ߼ơҳ˽ṹû·ȶԴûģʽǱڹ˿Ⱥھ㷨ʵ֤ģͺ㷨Ч.
ؼʣھ֪ʶ֣ûģʽ
ţTP311.13
ON MODEL AND ALGORITHMS FOR MINING
USER ACCESS PATTERNS
ZHOU Bin
College of Computer Science, National University of Defense Technology, Changsha, 410073
WU Quan-Yuan
College of Computer Science, National University of Defense Technology, Changsha, 410073
GAO Hong-Kui
College of Computer Science, National University of Defense Technology, Changsha, 410073
AbstractIt is important for the modern enterprises to have the ability of discovering useful user access pattern and corresponding potential customers from large volume of user access logs, so that they can benefit from their electronic commerce strategies. This paper presents an algorithm for mining user access patterns and corresponding potential customers, which are based on E-OEM model to integrate application logic, server topology, and user browse path. Experiments show the effectiveness of both the model and the algorithm.
Key wordsdata mining and knowledge discovery, user access pattern, E-business
1
WWWworld wide webս죬ʹһӦԾ˵ٶķ͸ӽлϢĽ빲˾ҵڲֲЭͬĹͳģʽתͣӶʹཻϢɱصӻͺ.Web־ΪĳЩWebȵ־ÿʮ׵ٶ.ЩзõġҪ֪ʶģʽ򡢿ӻṹȣھ֪ʶ֣data mining and knowledge discovery, DMKD1ݵһҪоӦ.
DMKDҪӦ֮һҵжݣbar codeķĿǷֹ˿͹ɣΪ̳ҵṩ֧.ĵӻϢԼҵĹʻʹDMKDںܶõӦòһչѳΪݿ⡢ϢҪо֮һ1.Web־ݵDMKDоҲԽԽܵ.
ԵΪӦñһо⣬ģʽʽ򵥡ԲȣԼЩĽ.
2ع
оĿĽǶȣеĻWeb־ݵо¿ԷΪ3ࣺ1ԷϵͳΪĿꣻ2ԸĽϵͳΪĿꣻ3ûͼΪĿ.ڸĿԵĹܲͬȡҪҲͬ.
ԷϵͳΪĿоҪǴͳѧĽǶȣ־жּ򵥵ͳƣƵҳλʱʱֲͼ.ĿǰеľüѵWeb־ߣweb log analyzer2ݶ.ЩߵʹһWebߣWeb masterWeb뽨Ҫ߼ûı仯ҵ.Perkowitzף3о־ΪݣWeb֯ͱʽԶԶadaptive web siteĸ.һȻǴ˻Agentģڼֶȴ̶ܴDMKDصChenף4·ģʽpath traversal patternķ㷨.㷨Web־ҳƵû·.⣬ݲֿ⼰OLAP־ϵͳĽҲһĹ5.
ܴӴWeb־ҳһģʽ͹򣬵Ŀǰоڲ.УֵģʽĿԲҪ֮һ.һģʽеϢû.˵㷨Էģʽҳ ABCDһƵ·<A, B, C, D>.һϢ·ûӦǱڹ˿ȺȣûĽһһ㷨ݵĹУoverfitµģʽȹС.
3ûģʽھģ㷨
ǵоԵE-businessϹnet marketingΪӦñ.̼WebϽԼƷĿ¼online catalog˿ͣûͨƷĿ¼ʵ϶֧.û̼ҵWeb佻ĹϢûĵ¼Ϣû¼Լûĸ˼ҪϢȣ־ļ˿ݿʽ.ҳԣ̼ҵгҪ.Ŀһض⣺δӴ˿ݼ־УھûģʽصǱڹ˿Ⱥ.֪ʶ̼ƶ.
3.1E-OEMģ
OEMobject exchange modelģһṹݵģͣ6.Ϊܹھ֪ʶۺϿǷӦ߼ơҳ˽ṹû·ȶԴ֪ʶ.ΪˣչOEMģE-OEMextended OEM۵.
1. Oɶʶid(O)Ͷֵval(O).id(O)ڶռΨһʶO.ֵval(O)ʽ
1 ԭʽ.val(O)={l1:d1, , lm:dm}Уliԣdiǻ͵ֵi=0,1,,m
2 ʽ.val(O)={l1:id(O1), , ln: id(On)}УljԣOjǶid(Oj)OjĶãj=01n.
2. OiǶliԣi=01n(li:id(Oi))val(Oi-1)i=01np=<O0, l1, O1, , ln, On>ΪΪn·n0pԴڶO0ֹڶOnOi·pл·pOi.
E-OEMҲôŵͼʾ.ͼеĽǶʶ.val(O)ÿһ(li:id(Oi))ͼжһli(O, Oi)֮Ӧ.ͼлƸE-OEMͼл.WebϵĺܶĵOEMͼл.ͼ1һE-OEMͼ.ͼеĸҶŶ1жǿĳWebҳWebӦ.p=<A, cast, C, actor, D, name, E>һԴAֹEΪ3·ΪACDE.CD·p.


ͼ1E-OEMͼ
3. WebվûɷʵġܶĶ󣨰ĵӦö٣ɶռ.
ռжE-OEMģڴ˻Ϲ췴ӳռиĻϢΪ֪ʶָھ.
3.2Ӧ
ڻϽE-OEMģͣ.
3.2.1 Ϣȡ
ĵӦöĶʶΪURLuniversal resource locatorĺֵڶռΨһ.⣬ǻȡ»Ϣ.
(1) ԪϢ.ĵ󣬰URLļС޸ʱȣӦö󣬼¼CGI
(2) Ϣ.ڶռ/ɵĶĶʶ
(3) һϢ.ĵ󣬰ֵӦöǼ¼CGIЧϣΪ书.
3.2.2 ı궨
ûڷϵͳһǼ־Уɴھ֮ǰû̼Ҽtransactionı궨.
4. NΪȻt(Oi)NΪOiķʱ̣c(Oi)NΪOiûʶp=<O0, l1, O1, , ln, On>ΪΪn·.p1 c(Oi)=c(Oj),i,j=01n2 t(Oi)t(Oj),0ijnpΪûcһ·.
5. Tûcķ·ļϣOiOi+1·p1Oj ·p2p1, p2Tp1p21 t(Oi+1)-t(Oi)max_time 2 |t(Oi)-t(Oj)|max_timeTΪûcһmax_timeΪԶʱ.
5ҳʱ궨.ʵУǻ·ԭ򣨹˳ȹС·.ݿ¼˿̼ҵϢй·ֱӴWeb־չõ.ڱĵоУǽݿDֳ֣ݿD+͸ݿD-.D+а̼ҳɽĹ˿D-δɽ.һ£D-ԶD+7.
3.3㡡
˿͵ĹģʽǱڹ˿Ⱥжֱʾʽͷ.У˿͵ĹģʽʾΪģʽԴдĸʾ.һеĶƵ·Сдĸʾɣڴ˻ϣǱڹ˿ȺΪƵģʽûȺ.
6. ڸݿD+ûԶСֶ֧min_supʣ0, 1ݣģʽP=<p1p2pk>D+min_sup|D+|û񼯰ģʽPPΪ˿͵ƵģʽУ|D+|ʾD+еû.
7. ڸݿD-˿Ƶģʽ{P1, P2, , Pk}ģʽƹϵR(D-,Pi)ȼCi(D-/R(D-,Pi)) ΪD-еĵiǱڹ˿Ⱥi=l,l+1,,k.
3.3.1 Ƶģʽ㷨
ƵģʽķƵģʽķ֣8֮ҪĲͬڹ˿Webϵ̴жֲȷԣıCacheûԵ.ЩȷԵ²ͬûķģʽƶϸڲͬ.磬ͼ1еģʽ<ABCDEFG><ABCDFG>ΪƵ.ʹģʽ㷨ʹ㷨ݹУ·ֵģʽԲ.Ϊһ⣬ڷģʽ㷨·ƶ.·p1=<O10,l11,O11,,l1m,O1m>p2=<O20,l21,O21,,l2n,O2n>

Ϊ·p1p2ƶ.sim_path(p1, p2)Զֵmin_simʣ0, 1ݣp1p2·ƹϵ.
ںѡУܶдظǰ׺Hash洢ͼƵУǺܶ򣨻ģʽ㷨Ĺԣ9.ǵ㷨ҲƵķʾͼƵģʽ.ڶݿɨн͵HashɨɺHashģʽֶ֧ȣóƵģʽ.HashĽṹͼ2ʾ.


ͼ2ƵģʽHashʾ
ʵУǲHashģʽɢתͬƥ.һƥƥ̣һڽݷֿ鲢д.
ƥĽƶȲⶨϵıŴ·.㷨̴£ģʽʱⶨģʽĵһ·²߱ϵ·ƶ.ƶСmin_sim򴴽һµӽ㼰ӦߣϵıΪģʽĵһ·ӽ1ȡƶӽΪ½㣬ǰ1.ģʽɾһ·½²㣬ⶨģʽǰ·²·ƶȣظùֱģʽΪ.Ӧķģʽɴýĸ߱α궨ģʽֶ֧ǵǰ֮.
3.3.2 Ǳڹ˿Ⱥ㷨
һأǱڹ˿ȺķֶΪݿD-ķࣨclassificationࣨclustering.ĲK-Means10ݾ㷨D-ڸģʽƹϵµĻ.ʼKĿƵģʽ㷨ĽҲҵԱָ.ģʽƹϵǻ·ƹϵ.ģʽP1=<p11p12p1n>P2=<p21 p22p2n>
Sim_pattern(P1, P2)= |{pi|sim_path(pi1, pi2)min_sim}|/n
ΪģʽP1P2ƶȣSim_Pattern(P1, P2)ԶֵMIN_SIMʣ0, 1ݣP1P2ģʽƹϵ.㷨.
룺ݿD-ʼ{P1,P2,,Pk}СģʽƶMIN_SIM.
C1,C2,Cn.
㷨
Ci:={Pi}, i=1,2,,k;
foreach P in D-
s=Sim_pattern(P, Pj):=maxi Sim_pattern(P, Pi), i=1,2,,k;
if sMIN_SIM then
Cj:=CjP;
return Ci,i=1,2,,k.
4ģ
Ϊ˶㷨Pentium 266/64M RAM/Windows 95/MS Visual C++ 5.0½ģʵ飺1Ԥȸ5ģʽΪMarkovģͣ1ʾֱɴСΪ500050000D+D-2ģʽ㷨D+min_sim㷨ʱ俪3Ǳڹ˿Ⱥ㷨D-min_sim㷨ķȷ.ͼ3ͼ4ֱʵ.
1ʵɲ

D+D-
ƽ·ȡ3ƽ·ȡ3
ƽģʽȡ3ƽģʽȡ3
Markov״̬תƸʡ0.95Markov״̬תƸʡ0.90
˿200˿2000


ͼ3㷨ʱ俪


ͼ4㷨ȷ
ͼ3֪1㷨ʱ䳤Ӧģʽھ㷨.Ҫǿ·ĸռ󣻣2㷨ʱ·ƶȽ.ͼ4㷨ķȷɴ66.˵㷨Ч.
5
Ӵ˿ݡ־ھûģʽصǱڹ˿ȺʵеսԵ̼ҵҵҪ.ĻE-OEMģͣۺϿǷӦ߼ơҳ˽ṹû·ȶԴûģʽǱڹ˿Ⱥھ㷨ʵ֤㷨ЧԵ.һо1㷨ʵݲӦŻ2ûģʽ㷨չͬ.
ĿǰֻCGIӦ.
Ŀõҡ߿Ƽ. 
߼飺ܱУ19716ʿоҪоΪھ֪ʶ.
ȪԴУ19422ڣʿʦҪоΪֲ.
ߺУ19426оԱҪоΪݿ⡢.
ߵλܱ󣨹ѧѧѧԺɳ410073
ȪԴѧѧѧԺɳ410073
ߺѧѧѧԺɳ410073
οף
1Fayyad U M, Piatetski-Shapiro G, Smith P. From data mining to knowledge discovery: An overview. In: Fayyad U M, Piatetsky-Shapiro G, Smith P, Uthurusamy R eds, Advances in Knowledge Discovery and Data Mining. Boston: AAAI/MIT Press, 1996, 134
2http://www.uu.se/Software/Analyzers/Access-analyzers.html
3Perkowitz M, Etzioni O. Adaptive web sites: An AI challenge. In: IJCAI'97, Japan, 1997. 233240
4Chen M S, Park J S, Yu P S. Data mining for path traversal patterns in a Web environment. In: Proceedings of the 16th International Conference on Distributed Computing Systems, Hongkong, 1996, 385392
5Zaiane O R, Xin M, Han J W. Discovering Web access patterns and trends by applying OLAP and data mining technology on web logs. Simon-Fraser University, Tech Rep: 1997
6Nestorov W, Ullman J, Wiener J, Chawathe S. Representative objects: concise representations of semistructured hierarchical data. In: ICDE'97. Birmingham, 1997. 220227
7Ling C X, Li C. Data mining for direct marketing: Problems and solutions, In: KDD '98, 1998
8Srikant R, Vu W, Agrawal R. Mining association rules with item constrains. IBM Almaden Research Center, Tech Rep: 97-056, 1997
9Park J S, Chen M, Yu P S. An effective hash based algorithm for mining association rules. In: ACM International Conference on Management of Data, Caliform, 1995
10Hartigan J. Clustering Algorithms. New York: John Wiley & Suns Inc, 1975
ոڣ1998-10-06
޸ڣ1999-03-08
