基于Web日志文件的关联规则挖掘模块的实现

第2卷 1

第 9期

计算机技术与发展COMP ER CHNOL UT TE OGY AND DEVEL MENT OP

Vo _ N . l21 o9S p. 2 e 011

2 1年 9月 01

基于 We b日志文件的关联规则挖掘模块的实现米娜瓦尔 拉合买提玛依拉 别克强塔依娃张太红 努，,,

曾明2O m rR Z i e , s a. . a n a(. 1新疆农业大学计算机与信息工程学院，新疆乌鲁木齐 805; 302 2西安交通大学软件学院， .陕西西安 704; 109

3阿尔伯塔大学计算机科学系， .埃德蒙顿 T G2 1 6 E )摘要：在对 We应用挖掘的基本步骤作系统性研究的基础上， b设计了一个基于 We b日志文件的关联规则挖掘模块。该

系统应能够对用户访问 We时服务器方留下的访问记录进行挖掘，中得出用户的访问模式和访问兴趣。为了识别用户 b从

浏览模式，现了利用关联规则挖掘算法 A rr对 We应用挖掘过程中预处理阶段所产生的用户会话文件进行挖掘的实 pi i o b模块，模块针对用户选定的若干页面产生满足最小支持度和最小置信度的页面之问的强关联规则，以文本的形式显该并示挖掘的结果。 关键词：用户访问序列文件；联规则；关最小支持度；小置信度最中图分类号 _P 1, 30 T文献标识码： A文章编号： 7— 2X(0 10—0 1o 1 3 69 2 1 )9 05一 4 6

I plm e a in fAs o ito M i n o e m e nt to o s ca in ni g M d l

Ba e n W e g F l s d o b Lo i eN L H MA T Min war, IKE I NG AY WA — i Z A a— o g, U A E I I — a e B E Q A T I Ma yl, H NG T ih n aZENG i g Os r R. in M n - ma . Za a e

( . ol eo o u radIfr t nE gneig X ni gA r u ua U iesy U 1C lg f mp m n omao n i r, i a gi l rl nvr t, mmq 80 5, hn; e C n i e n j n ct i i 30 2 C ia 2 S f r n i e r g S h o, ' i oo g

Un v r i Xia 1 0 9, h n; . o t e E g n e n c o l Xia Ja t n i e st wa i n y。 ' 7 0 4 C i a n

3 D pr n f o u n cec。 br nvri。 d n nT G 2 lC nd ) . eat t mp t gSineAl t U esy E mo t 6 E, a aa me o C i ea i t o

Ab t a t Un e l i h y t ma c su is o h a i tp f W e s g n n 0 i lme ta v s a e s g n n y t m。 s r c: d ryng t e s s e t t d e n te b sc se s o b u a e mi i g t mp e n iu lW b u a e mi i g s se i

whc smanyusd t m n he W e lg a c s il ha c urd fo te W e e v r g tteu e iiigp t r sa d vst g itr ihi il e o i et b o c esf et taq i e rm h b sr e,e h srvst atn n iin ne- n e ie t. n r e O i e t y t e n v g t na patr so e i ii r - r r g rt m s u e n t e mi i g o e u e e so l a ss I o d r t d n i a i a o l t n fW b s t v st s Ap i ia o i f h i e e o o l h i s d o n n ft s rs s i n f e t t h h i h ha e n g n r t d at rt e d t r—p o e sn r c s nt eW e l gfl .Th s o it s b e e e ae f h a a p e r c si g p o e s o h e b o i e e a s c ai onmi i g mo e alb s d t e e a t e nn d lc l e u e o g n r t h e fe u n t ms t a t f em n mum u p r r s o d a d sr n s o ito ue e we n s l ce a e h ts t f e b m n— r q e ti e s t ts i y t i e h a s h i s p o tt e h l t g a s c a i n r l sb t e ee t d p g st a ai y t o mi i h n o s h mu c n i

e c n n mu s p r h e h l s n ip a e a s ca o l smi i g r s l y t x . m o fd n e a d mi i m u p tt r s o d -a d d s ly t s o it n r e n n e u t b e t o h i u s Ke r s: s rv s n e u n e fl a s i t n r l mii m o f d n e; n mu s p o y wo d u ii g sq e c e; s o a i e; n mu c n i e c mi i m u p r e i t i c o u t

O引言 数据挖掘中最基本的方法是关联规则挖掘，目其 标是把数据项之间的关联从数据集中挖掘出来。 可以将关联规则用于从 We b日志文件中通过预处理获得用户会话事务文件，在会话事务 1中出现了收稿日期：0 1 0一 1修回日期：0 1 0— 7 21— l2; 2 1— 4 2

U L集 A, R在事务 2中出现了 U L集 B, R在事务 3中同时出现了 U L集 A和 B。能否发现 U L集 A和 B R R 在这三个事务中出现的互相之间的规律呢？答案当然

是肯定的。要解决这个问题可以通过关联规则挖掘来找到 U L集 A和 B在这三个事务之中出现的规律。 R

进一步说，关联规则通过概率来描述出现 U L集 A R对出现 U L集 B的影响，,问 U L集 A的用户 R即访 R访问 U L集 B的可能性有多少。 R

基金项目：新疆维吾尔自治区电子信息发展专项资金项目( J Z X XD ZZ2 19 J00 )

作者简介：米娜瓦尔 努拉合买提( 9 0 )女( 17一，维吾尔族 )工程硕，士，讲师，研究方向为 W b e数据挖掘可视化。

1关联规则简介对于一个关联规则，以从置信度和支持度两个可

基于Web日志文件的关联规则挖掘模块的实现

5 2

计算机技术与发展

第 2卷 1

角度来进行研究，支持度表示项在全部数据库中占的比例，置信度表示了规则的强度，中同时满足最小支其持度和置信度的规则叫做强关联规则]。1 1置信度 .

者访问顺序的文件 v i sq e . t即：问者在一 it enw t,访 s— x个会话中所浏览过的 We页序列。 b 下面就以本系统在挖掘过程中所采用的数据文件说明预处理后文件所包含的数据以及每一行数据所代表的含义：

规则即：

y在事

务集中的置信度是指支持和 Y

的事务数与支持的事务数之比。

( ) itsqe . t 1 Vs—en w t中的每一行数据为某一个访 i x问者访问的页面编号序列：

c n(:{。dc=)』 nee y 并集， r为所有用户会话事务的集合。

( )

2 3 3, 2 4 6 6 6, 2 3 7 5 6 5 2,2 0 6 5 7 6 53 2 3 2, 2 3 2 3 2, 6 8 2 7, 6 8 6 5 7, 6 8 2 3 3

式中：为事务项集， y为事务项集，是一组 U L t R项， u y为包含和 y的事务， 也就是项集和 y的公式 ( )明， 1说设中支持全部的 U L集的事 R务中，有的事务同时也支持 U L I R集， 称为关联其中第一行中的数据编号对应的 U L地址为： R233“ 7 5,/~jh” s i

6 52“ pol ga/si t l 24,/ epe rd j . m”/ h h6 6 6,/p o l/ r d rfls hml’ 2 0“ e p e g a/p o e . t’ i

规则

y的置信度。简单地来说，置信度是指在 U L R

65 7“ pol ga/i u. tl 2 3。/ eper d j h ihm’/ n’

集 X出现时 U L集 y也同时出现的概率有多大。 R12支持度 .一

该行数据说明第一个用户登录到页面/~ si, j后 h访问了该页面的内容，接着访问了与 j ihm文件处 s . tl h于同一层的页面文件 p fe.t l o s m r l h以及 j h ihm。 i i u. t l n

个关联规则是形如 jy的蕴涵式，这里 n l,

≠。规则 jl,在事务中的支持度是事务集中支持和 y的事务数与所有事务数之比。即：

( )i . t该文件中包含有关网站结构的信息。 2 lk t: n x如：2, 8 6 5 66

S p otX, ) upr= y: (

() 2

2, 8 2 5 85

式中各符号含义同式 ( ) 1。公式()明， 2说设中有 J的事务同时支持 U L I% R集和 Y%称为关联规则 j y的支持度。支持度，

第一行的数据表示在编号为 2的页面中有一个指向编号为 5 6 6页面的一个超链接。其中：主页 86 2为的编号，84 5 24为页面” aoths r.t l的编号。/b u ioy h”/ t m ( ) ae.

t 3 pgst:每一个页面的 U L都用唯一编号 x R

的含义是和 l,这两个 U L的并集 c在所有的事务 R集中出现的概率的大小。若某天共有 10 0 0个浏览者，其中有 30个浏览者同时访问了和 y那么上述的关联 0,规则的支持度就是 3%。 0关联规则 r是下面形式的一个表达式：X￣ Y( 8,,

来表示，因此该文件中包含的信息为从编号到 U L的 R映射。例如：2“”(,/主页的 I D号为 2 ) 3,/ b l k’“ u i o’ t一

O) L,

() 38“一~ e nc/ 4 1 c u4 8。/ u ie c 0/ mp t01一

式中为事务项集， y为事务项集，, 为 u y的 支持度，, r O为的置信度。 L 公式 ( )说明， 3给定一个事务集，挖掘关联规则问题就是产生支持度和置信度分别大于等于给定的最小支持度和最小置信度的关联规则。

hoe/ r et ovrpo c j/

s cin d c me t h m’ e t/ o u n. t’ o

2 2关联规则的实现 .挖掘关联规则主要包含以下两个步骤：

步骤一：发现所有的频繁项集，据定义，根这些项

2基于 We b日志文件的关联规则挖掘模块集的支持计数至少应等于最小支持度 rn sp与用户 a—u i的实现访问序列文件中事务总数的乘积；该模块的主要功能为：过关联规则挖掘算法通 A f f从用户访问序列文件中挖掘出支持度和置信度 po ii大于给定的支持度与置信度的被选择的节点 (面)页 之间的关联规则。2 1数据预处理 .

步骤二：根据所获得的频繁项集，产生相应的强关联规则。根据定义这些规则必须满足最小置信度阈值。 。

该模块主要由 Lt st和 A srl类组成。L im e类 e s ue o i—

t st的对象主要用于存放所产生的频繁项集以及 e e类 m各频繁项的支持计数。A srl类主要由 it o pr s ue o n cm a— e

从 We b服务器中的日志文件中获取的含有访问

基于Web日志文件的关联规则挖掘模块的实现

第 9期

米娜瓦尔 努拉合买提等：于 we基 b日志文件的关联规则挖掘模块的实现 k s .n e O (” k= 1 id x f“, );

3 5

sb( tn t I Sr g i m D ) Sr g u is ig u

Sr g i m D, tn t l 1, tn n etn i e i e i t r

( tn l S n ) it o pr tn ( tn l Sr g Sr gs,t gs, m ae r g Sr gs,tn i i r 2 nc si i i s ) itgt nt ( tn 1以及 p b c V c rC m 2, e eg Sr gs ) n l h i u l et o - i op tso V c rnd i o, obespotd ul mn uA s ( et oe f du l u pr obe i— o nr ,

i k> I s= 1 sbtn ( k ls.eg f k - ){l ig k+,11 t ( r nh

( )m+; );m+} e e{l nl m+;} l s= ul m+} s; rt m;} eu m( m)方法 p b cV c rC m uA s ( et oe f, u l et o p tso V c rndi o i o o nr

cni ne tr sIE cpi等方法组成。 of e c)ho xet n d w O o 其中，法 itcm aeu Sr g i m D, tn 方 n o prsb( tn t I S g i e i r

im D ) t I 1主要用于判断两个项集的包含关系， e若第一个项集的所有项都包含在第二个项集中，方法返回该 1否则返回 0 ,。方法 S n nt tn ( tn l S n 2主要完 t gu i sig S gs,t gs ) i r er i r i r成合并项集的操作，将第二个项集 s 2中不包含在第一

du l sp o du l rn cn dne obe u p￣,obea— of e c )是该模块中的 i i一

个核心方法。该方法主要根据选定的节点，得这获

些节点的所有候选项集以及各候选项集在访问序列文件中出现的次数，支持计数，即：然后根据给定的支持度和置信度删除不符合条件的各候选项集来获得频繁

个项集 s 1中的各项合并到 s 1中。合并项集的流程图如图 1所示。

项集，该方法的输出是满足给定的最小支持度与置信度的关联规则。

3应

用

3 1基本资料 .通常在一个网站挖掘应用数据的原因在于要提高这个网站的可用性。分析的第一步是收集客户的使用途径。每一个客户的会话都是一系列的网页要

求。这些网页请求的联系可以由分析客户浏览行为之间的联系而得到。这些联系暗示这

些网页之间要添加一

些附加链接。如果在一个会话中经常被访问的两个

页面彼此之间没有链接，么加上链接或提供推送服那务，客户会感到更加方便。 本实例使用的是加拿大阿尔伯塔大学计算机科学系一周内产生的 We日志文件进行预处理后得到的 b图 1项集合并流程图 方法 i o prsig Sr gs,tn 2主要用 n cm a tn ( tn l S gs ) t er i i r

用户访问序列文件。 3 2关联规则挖掘结果与分析 .可以通过挖掘被选定节点的关联规则，网站结对构的调整提供理论依据；若实验环境配置较高，系统该可以处理时间跨度更长的 We b预处理数据。在本实例中首先采用 We b图有效地可视化了 We b站点的拓

于判断两个项集中的各项是否完全相同，果完全相如同返回 1否则返回 0,。该方法代码片段如下：it o p r tn ( tn l Sr gs ){ n cm ae r g Sr gs,tn s i i i 2i tmm; n itn n n;

扑结构以及各节点访问计数和登录计数信息，有效即，地将 We b站点的拓扑结构图与 We b站点应用数据结合在一起。给定层次数和起始 U L的 We R b图生成后， 需要用户选择挖掘关联规则的节点，并输入最小支持度和最小置信度阈值。考虑到只对一周的访问序列文

m cm aeu (l s ) m= o prsb s,; 2n= o prsb s,1; n cm aeu (2 s)

i ( m:=1& n==1 ){ f m ( )&( n ) ru ( )} e r 1; tn

e ertr( ) l un 0;} s e方法 it e eg ( tn 1主要用于统计项集中 n gtn t S gs ) l h r i项的个数。由于项集中的各项之间由逗号分隔，以所

件进行挖掘，将支持度和置信度的值设置的较小，均为0. 01。 0

表 l中列出了被选节点通过关联规则挖掘后的结

主要是通过统计代表项集的字符串参数中的逗号的个数，并且为了将最后一项统计进去，最后逗号个数还要加一来得出项集中的项的个数。代码片段如下：it e eg ( tn 1 n gtn t Sr gs){ l h iitmm;n k; m=0; n i tk r a

果，支持度与置信度较高一点的节点之间的关联性要强一点。比如

,在表 1中显示有以下两组数据： 第一组：pol f ut. tl一>> pol fc/ epe a l h一 ->/ epe a./c y m/u y rfls hml h/p o e . t i s p o t= 0.0l 2 9 6 l 7 2 48 o fd n e= 0. upr 6 6 8 6 9 6 5 c n e c i5】 9 6 6 8 42 5 6 6 O 7 6 71

w i (l n l h e s != u ){ l 1

基于Web日志文件的关联规则挖掘模块的实现

5 4

计算机技术与发爬

第 2卷 1

表 1关联规则挖掘结果 LL j R/根节点 ) (, ,

UI R/ epe f ut.t l p ol a l hm/ c y/ e p d, t p o k/ h ml/~c i o k hn o

支持度O 0)9 2 .( 5 2O. ol 5 0 7 8 0 o5 6 . o 71

置信度O o 3 1 .0 44O. 0 O 4 0 2 3 O.) 6 1 ( 6l o

,

/ e p e a u y nl ls h ml p o l/fc h/p f e . t i

Oo 5 7 . o1 0

O. o1 4 o 73

/ e pe a ut. t p o l/fc l hml yO. oI 9 0 13 0. ol 8 o 3 0 00 3 2 . 9 8l

/ e p e a u t/p o i s h ml p o l/fc l y r fl . t e/, p e fc h . t p, l/ a u y h ml ' o, 0 0 9 2 . 02 5

/ o l/ a u y h ml pe p e fc h . t/ e pe a ut. t p o l/fc l h ml y

/ e p c a u y r fl s h ml p o l/fc h/p o e . t i/ p o l/fc l/p o ls hml/ e pe a ut y rf e . t i

0 O6 6 . 12 9O. ol 9 0 13

O. 6 6 5l 9 60. 3 9 4 0 7, 2

/ o l/￣d.1 n pe p e g a 1 f l t/~c i o k hn o/p o l/ a￣ y p o i s h rl e p e f c,/ r f e . t h l n/p,p e f c h/p o l s h ml￣ l/a u y rfe . t o i

7

O( 78 .) 5 ol O【) 71 .K5 6

0 O 8 3l .7 4 00 6 7 .6 2 8O (6 8 2 .), 5 6 0 72 4 8 . 14

, /p o l/ a u t . t e p e f c l h ml y

0. H1 0 0 57 0 O O

66 8 . l2 9

/j pef u￡ )o/ . t/ f0l/n l/J fe hm| j c y ri s/ e pe f, l . u l/p o l/ a u t h n￣ y c/p o l/ a u y r f e . t e p e f e h/p o i s h ml l/ e pe fc l . t p o l/ a u t h ml y

/ p01 f u y hm/ ep a h . tl c/p o l/ a u y ' mf e . t e pe fc h/ p￣ s h ml p o l/ a u y h ml e pe fc h . t

O 0)l3 .( 95 l0. o 1 3 1 l9 5 ) 0 0 13 . ol 9

O 02 2 . 59 4O. O4 5 4 25 07 6 6 . 9】 6

,

0. o 1 o l 93

0. 3 5 07 3 9

/p o l/a a y D0i s 1ml e pe fc h/1 fe .l r l t

第二组：pot f u yp ishm一一>/ e—/ epe a i/ mfe.t l一>> po/ct lpe f, h . mn l/ a- t t l u y s p ot= 0.01 2 9 6 1 7 2 48 c n d n e= 0. u pr 6 6 8 69 6 5 of e c i 7 4 4 7 6 53 2l 48 6 9 6 7 8

参考文献：[] H nJ, a br Dt Min: ocps n ehi e 1 a K m e W M. a n g C netadTcn us a i q[ .n dB in: h aM ci rs,07 17 15 M]2 de. eig C i ahn Pes20:— 5 . j n e 4 [ A rwl, menk T S a i . i n s c tnR l 2 g a R I iisi,w m Mn gAs i o u s a l A i oa i e btenSt o Im a eD t ae[ // r edns e e es ft si Lr a bssC w e n g a Po ei c g o t 93A M SG O ofec.Wah o nD: . fh 19 C I M D C n r e e en si . C[S n n J, 9: 7 26 . 1 3 2 - 1. 9 0

这两组数据表示：客户访问完页面 f u y,过 al后通 ct该页中的超链接进入页面 po l rfe i s的概率高于表 1中

的其他组或从页面 po l返回到其父节点 f u y的[]%a C in . nef i tmeh d frn nn so it n r

fe is a l ct 3 yY, h g』 A fc n a i e t f i asc i o o i g ao概率高于表 1中的其他组。利用该 We访问信息挖掘 b rl[] K o l g- ae yt s2 0,8 3: - 0 . u s J . nw e e B sdS s m,0 5 1 ( )9 15 e d e 94袁 We J. 结果，可以建议 We b站点的管理者在这两个页面中添[]候亚丽，方 . b日志挖掘中的数据预处理技术[ j

加进入和返回的超链接；面对广大用户改进 We b服务

河北大学学报，052 ( ) 2 2 25 20, 2: 0— 0 . 5 []李烈彪， 5张海鹏，亚峰 . b日志挖掘中数据预处理力法周 We‘的研究[]汁算机技术发展， 0,7 7:— 2 J. 2 7 1( )4 5 . 0 6

器性能的一个重要手段是使 We务器能够进行推 b服送服务 .所以也可以建议在这些页面中增加推送服务功能，一旦一个规则“aut - r i s被选中，, f l * ol” c y一 p fe即

[]袁万莲， 6郑

诚，明清 .种改进的 A fr算法[]计钾.翟一 po ii J.

当用户访问了 f u y,么 pols被推送。通过[]郭有强 .高效的关联规则维护算法研究与实现[]汁 a l时那 ct rfe将 i 7一种 J.提高用户找到所需信息的速度，以大大改进 We可 b站算机技术与发展， 0,7 1 ) 13 16 2 7 1 (0:— 2 . 0 2 点的访问效率和用户的满意度。 []熊忠阳， 8周亚峰 . b访问挖掘的预处理技术的研究【 . We j j计算机技术与发展，0 7 1 ( ) 1— 8 20, 8: 1 . 7 4

机技术与发展，0 8 1 ( ) 5一 3 20, 5:l 5 . 8

4结束语 该系统的有效性与准确性与预处理结果有关，所以预处理在该项目中占重要地位，预处理过程很繁但

[]赵 9[O 1]张

伟，丕廉，何陈

霞. b日忐挖掘【的数据预处理技 We j 1

术研究]计算机应用， 0 ( )6 -4 J. 2 3 5:2 6 . 0 娥，冯秋红，宣慧玉. b使用模式研究中的数据挖掘 We

[]计算机应用研究，0 13: - 3 J. 20 ( )8 8 . 0

琐，的预处理结果能生成令人满意的挖掘结果。其[ 1玉

珍 . b用模式挖掘中的几个关键问题研究[]电好 1]王 We使 J.次，在该系统中还可以增加其他功能，为了提供个性化脑开发与应用， 0,6 1) 1- 9 2 31(1: 1. 0 81]戴军湘.于 We基 b日志挖掘的自适应网站推荐系统框架研的服务，可以挖掘浏览者与其访问的页面之间的关联[2

规则等。

究[ . D]长沙：南大学，05湖 20 .