基于矩阵关联规则的webweb服务分类方法

基于矩阵关联规则的webweb服务分类方法

随着互联网的快速发展和web应用的普及，电子商务已成为重要的采购平台和消费者与公司沟通的重要渠道。随着产品、服务、咨询等信息的增加，用户往往无能为力。因此，他们希望能够正确理解用户的访问模式，并积极推荐用户。实现这一愿望需要使用挖掘知识。web使用挖掘是指根据用户访问web站点时服务器上留下的访问日志来探索和检测用户访问模式的过程。每个用户都有自己的访问目的，所以它们会形成不同的访问模式。每次访问用户模式时，基于相同访问模式的用户可以在未来访问网站。用户分类是web访问模式挖掘的一个重要方面。目前，基于web用户分类的方法很多，如决策树、简单的分类方法、ripple和其他方法。然而，这些方法通常表现出布局精度低、模型复杂性高的问题。近年来，许多科学家在用户分类中使用了相关规则。根据研究，基于相关规则的分类方法比传统的分类方法具有更高的分类精度，基于相关性规则的分类算法可以应用于web用户分类，如marni算法。dph算法和比特马斯基算法。在这项工作中，我们主要使用矩阵方法来挖掘web日志数据，并使用矩阵算法来改进排序未来访问用户的分类，为不同的用户提供建议。1分类关联规则的提取和步骤1.1访问事务集的生成Web服务器日志文件中每一条日志记录包括用户的IP(sourceip)、访问日期(date)和时间(time)、访问页的相对路径(url)、浏览器的版本等信息,每一条记录对应用户的一个页面访问.由于日志的原格式不适合直接进行挖掘,并且有些无关页面的访问记录没有价值,所以需要对其进行预处理(如路径补充、去掉样式、导航页、与业务无关的页面访问记录等),预处理后的日志文件设为L.首先对站点的所有页面进行筛选(样式、导航页等与业务无关的页面不予考虑),筛选出来的参与挖掘的页面形成一个集合P(p1,p2,…,pn),n代表所筛选出来的参与挖掘的页面的总数.要进行挖掘先要获得用户的访问事务集,访问事务定义如下:t=<sourceipt,{(lt1.url,lt1.time),(lt2.url,lt2.time),…,(ltm.url,ltm.time)}>对任意的正整数r(1<=r<=m),存在ltr∈L,ltr.sourceip=sourceipt,ltr.time-ltr-1.time<=F,m为该事务所对应的访问用户本次访问的页面总数即事务的长度,F为时间阀值(常量).一个用户的访问记录集中,如果相临记录间的时间间隔超过阀值F,就认为是本用户的2次不同访问,应分为2个不同的事务.在经过预处理后的日志L中寻找事务的方法如下:(1)根据每一个用户的源IP来划分日志,即在日志中找到每一个用户的访问记录集;(2)根据时间阀值F来分割每一个用户的访问记录集,找到每一个用户的每一次访问记录集,此时,每一个访问者的每一次访问记录就构成了一个访问事务;(3)最后按照时间顺序来对访问事务排序形成了访问事务集T0.为了便于挖掘,将划分好的事务集T0中每个事务t=<sourceipt,{(lt1.url,lt1.time),(lt2.url,lt2.time),…,(ltm.url,ltm.time)}>裁减为t=<id,{pl,pm,…,pn}>,即舍弃访问时间不考虑,id为该事务的标识号,(如果sourceipt相同但它们是不同的事务,则它们的id是不同的).pl,pm,…,pn均为事务t中记载的url所对应的页面在页面集合P中的标识,但重复的标识只记一次.页面分类:按照一定的标准将Web站点的页面分为w个类,形成一个类集合C={c1,c2,…,cw},w为类的总数;然后根据领域专家与站点管理员的经验知识对访问事务集T0中的每一个事务进行分类标号,标号值为C中的元素.比如,某事务ti中的访问记录记载的多半是关于手机的页面,则将ti标记为C中对应手机的类cj,即{ti,cj}.将裁减后的每个事务进行分类标号后形成T1,T1′就是具备分类关联规则挖掘条件的事务集.1.2采用矩阵算法提取排序关联规则(1)有关矩阵算法的定义，请参阅布尔矩阵:矩阵元素的值为0或者1的矩阵.(2)最小支持数msinum假设T1中的事务数为o.①构建布尔矩阵Ar*s,其中r=o+2,s=n+w+2,n为页面集P中页面的总数,w为C中类别的总数,o为T′中事务的总数.元素A1j∈P∪C={p1,p2,…,pn,c1,c2,…,cw}(2<=j<=n+w+1),∪A1j=P(2<=j<=n+1),∪A1j=C(n+2<=j<=n+w+1),且∪Aj1=T1′(2<=j<=o+1),A1s=SC,Ar1=SR,SC列记录的是其左边的各列中的值的和,SR行记录的是其上面的各行的值的和,P∪C构成了项集I.然后在该矩阵中的每个元素位置填入相应的值,填入规则为:某元素所处的列所代表的项在所在的行的事务中出现,则该元素为1,否则为0,并在最后一行SR中算出各项出现的次数,在最后一列SC中算出每个事务中项的个数.②计算每个项的最小出现次数.根据给定的最小支持度min-sup和最小可信度min-conf计算各项要求出现的最小次数——最小支持数min-supnum,最小支持数min-supnum为不小于min-sup*o的最小正整数.③裁减不符合条件的列.将最小支持数min-supnum与布尔矩阵中最后一行SR中的值作比较,将小于min-supnum的SR值所对应的列减掉,裁减不符合条件的列之后要重新计算各行的最后一列SC的值.④裁减不符合条件的行.一般来说1项集没有什么研究意义,因为形如规则A=>B最少应该有2个项(A、B,A就称为规则的前件,B称为规则的后件),因此去掉SC中值为1的行,并重新计算最后一行SR中各列的值.如果只需要求K项集(包含K个项)或者更高次项集,则可以在此减掉所有SC中小于K的行,并重新计算SR中各列的值,循环执行③、④步骤,直到没有行和列需要裁减为止,这时矩阵中所剩项的支持数都不小于最小支持数min-supnum.⑤生成频繁项集.经过裁减后的矩阵是将明显不满足K项频繁集性质的行与列剪掉后的矩阵,然后在其中寻找K项频繁集会在很大程度上提高效率.求K项频繁集的算法:输入:最小支持数min-supnum,项数K(K>=2),经过裁减后的布尔矩阵以及其列数b和行数d.输出:K项频繁集集合LK.由于分类关联规则中只有后件是类别项,前件都是页面项,所以在K维组合的过程中应只选取有且仅有第K个向量所对应的项是类别项的K维组合.组合的方法是在页面项所对应的列中选取K-1个列,在类别项所对应的列中选取1个列来组成K维组合,生成共有cΚ-1b-2-wc1w个组合的集合S.生成组合的算法:输入:经过裁减后的布尔矩阵以及其列数b,项数K(K>=2),页面类的总数w;输出:组合集S;将第j1,j2,…,jK,列组成的K维组合加入组合集S中;returnS.以上求K项频繁集的算法中求K项集iK的支持数support的方法是将这K列向量进行对位“与”(同一行的元素)运算,运算结果中1的个数就是K列向量所对应的项所组成的K项集iK的支持数.求K项集iK的支持数的算法:输入:裁减后的布尔矩阵的行数d,K(K>=2)个列向量(Aa1,Aa2,…,AaK)组成的矩阵B,项数K(K>=2);输出:支持数support;有了K项频繁集集合Lk就可以挖掘其中的分类关联规则了.分类关联规则生成算法:输入:K项频繁集集合LK,最小置信度min-conf;输出:规则集RM;foreachi∈LKif该频繁项集i={f1,f2,…,fK}中fK不是类别项thencontinue;else{①因为前K-1个属性是页面项,所以将前K-1个项作为规则的前件A,第K个属性(类别项)作为规则的后件B,从而产生规则A=>B;②计算这个规则的置信度:confi(A=>B)=P(B|A)=supcount(A∪B)/supcount(A);//supcount(A∪B)为包含项集A∪B的事务记录数,supcount(A)为包含项集//A的事务记录数;③if(confi(A=>B)>=min-confthen保留该规则,并加入到规则集RM中;else丢弃该规则;}returnRM.2访问用户的分类假设应用上面的算法挖掘得到分类关联规则集为RM,下面探讨用RM作为分类器对新的用户进行分类.首先将RM中的关联规则存储到数据库中,数据库中存放关联规则的数据表结构如表1所示,并且设pages、kinds2个字段的联合键为主键.规则存储在数据表中的形式如表2所示.如果关联规则是求K项频繁集来获得的,则规则表中对应的规则的pages属性包含K-1个页面.现在就可以对新的访问用户进行分类了,分类过程为:当一个用户(一个源IP)在浏览Web站点时,服务器会记载用户的访问记录,此访问记录中记载了该用户所访问的页面.我们可以设置一个队列,当该用户访问了1.1中所提到的站点页面集合P(p1,p2,…,pn)中的页时,则将此页加到队列的队头;如果此页在队列中已经存在,则不加入,一旦队列中的页面数大于等于K-1,就开始在规则表中匹配规则.匹配方式为:从队头开始取K-1个连续页面,并对这K-1个页面按照其在集合P(p1,p2,…,pn)中出现的先后次序进行排序,然后通过这K-1个页面到规则表中去匹配pages列,将所有匹配的规则找出来.如果只有一个规则匹配,该用户就属于该规则kinds属性值所代表的类,此时就认为用户对该类的页面是感兴趣的,用户即将访问该类中的页面.如果有多个规则匹配,则比较所有匹配规则的置信度,根据置信度高的规则来判断用户的类别;在置信度都相同的情况下就比较所有匹配规则的支持度,根据支持度高的规则来判断用户的类别;在置信度与支持度都相同的情况下就比较所有匹配规则产生的先后顺序,根据先产生的规则来判断用户的类别.当访问记录中记载的同一用户访问的相临2个记录之间的时间间隔超过阀值,则将队列清空重新记载,因为一个新的访问事务开始了.运用上述方法这就可以将新用户分类了.3实验结果与分析我们采用的实验数据是深圳某商务网站的一部分日志记录(如表3所示),其中用来挖掘关联规则的日志记录有10371条,用来测试关联规则分类效果的日志有1285条,每一条记录依次记载的是访问时间、源地址、目标地址、端口、URL及浏览器信息.首先,要用前面讨论过的数据预处理方法对该站点的日志记录进行预处理,并划分事务形成一个事务集;然后将生成的事务进行裁减并加上类别标记;再利用上面讨论的分类关联规则挖掘方法找出所有可能的、满足条件的关联规则;而后利用这个些规则组成的分类器类对用户进行分类.在挖掘分类关联规则以前要确定最小的支持度和置信度,经过多次试验之后,发现最小的支持度为0.1%、可信度为70%时,实验的效果较好.下面将用本文提出的方法所实现的系统与前辈用Apriori算法所实现的系统在性能上作一比较,主要从提取规则所用的时间及利用所得到的规则对用户分类的精度来比较,前提是所用的日志完全相同,在同一台机器上实验.我们将用户分类后就认为用户本次访问会访问其所属的类中的页面,所谓精度是指用户确实访问了其所属的类中的页面占其本次访问的页面总数的百分比.所谓本次访问是指用户在访问过程中访问一个页面与访问下一个页面的时间差没超过阀值,本实验中设阀值为15min.实验证明矩阵算法在精度方面比起Aprior算法没有太大的优势,但在寻找规则的时间上就有明显优势了,而且K的取值越大,所需的时间反而越少.Apriori算法是一种逐层搜索的迭代方法,并且把频繁项集的反单调性用于压缩搜索空间,从而达到快速搜索频繁项集的目的.矩阵算法在时间、空间上都有很大的改进:矩阵算法只扫描数据库一次,在不知道K-1项频繁集的情况下可以直接计算K项频繁集,不需要对K-1项频繁集进行剪枝和连接操作;在计算过程中,K值越大,计算次数越少,因此效率越高.在空间上,矩阵算法不会产生庞大的候选集,也不进行连接操作;同时事务矩阵中存储的绝大多数是布尔值0或1,而布尔值0或1所占的空间很小,所以矩阵算法可以节省很多存储空间,也不会因内存不足而导致大量的I/O操作.4改进的k维组合基于关联规则的Web用户分类关键在于挖掘事务集中的分类关联规则,而挖掘分类关联规则的关键是寻找频繁项集.本文在寻找频繁项集时采用的是矩阵算法,并对矩阵算法进行了改进.以往矩阵算法在寻找频繁项集时多半是直接在裁减后的矩阵中来获取频繁项集,也有人提出在寻找频繁项集前先对裁减后的矩阵中不包括SC列的向量中进行K维组合(每个组合有K个列和d个行,即K个列向量),这比直接在裁减后的矩阵中获取频繁项集提高了效率.本文在别人研究的基础上作了进一步的改进.因