Web数据挖掘中频繁访问页组有趣性的研究(2)

    挖掘频繁访问页组的算法类似于关联规则算法中发现最大项目集，我们预先设定支持度的阀值T，在频繁访问页组中都是支持度大于T的页面，在传统的页面聚类算法中，支持度指包含页组中所有页面的用户会话的个数。在MIR算法中，我们除了设定支持度，同时根据网站的拓扑结构计算每个规则的有趣度interest(A|B)。挖掘出来的页组的有趣度还需要满足用户指定的最小兴趣度min-interest。

    在算法中，我们先用FLOYD算法求得A到B的最短有向路径，然后利用上面讨论的公式计算P(A|B)，进行页面间关联概率的计算。MIR算法预先计算任意页面之间的最短路径，存储在邻接矩阵中，提高算法的运行效率。构造最短路径的算法描述如下：

Queue=Enqueue(index)//从第一个页面开始

P=new Node()；//新建一个节点

While not Empty(queue)

   I=Dequeue()；//从队列中取出一个页面

   For each J=I.link  //对于该页面的每个链接

     If not visited[J] then //判断页面J在图G中是否已有结点

              s=s+1；

q=new Node()；

              Enqueue(q)；

              Visited[j]=true；

      Else

         q=GetNode[j]；//获取页J在图G中的结点

Endif

P(J|I)=1/(s+1)；//根据公式计算关联概率

p.addEdge(q，P(J|I))；//从p节点增加有向边到q，概率为P(J|I)

next

end

有趣规则算法：

输入：支持度大于最小支持度T的频繁访问页组{A=>B}，最小有趣度min-interest；

输出：有趣频繁访问页组；

利用上面的算法构造了一个含有任意页面最短路径的邻接矩阵W

For each A=>B

  利用式（1）和W计算interest(B|A)；

  If interest(B|A)>min-interest then

    输出”A=>B”

  End

next

    MIR算法已经在学校网站中的一个星期的日志数据中进行了验证，试验环境是在CPU为PIV1.3G，内存为256M的PC机上，运行平台为Windows2003 server。实验数据长度为6MB的长度，其中包含7万条记录。日志数据中312个不同的页面。经过预处理后转为1703条会话记录。我们用一般的页面聚类算法（支持度大于T）和MIR算法都对实验数据进行挖掘，得到的频繁项目集FGi列表如表1所示。

表1 算法实验比较

    说明：|FGi|－频繁项目集的数目。

    ＋，＋＋，＋＋＋：这三个页组包含了我们感兴趣的页组。

    通过实验可以发现通过MIR算法设定最小兴趣度0.8，对一般算法产生的关联规则进行兴趣度过滤，将兴趣度低的关联规则排除，这样得到规则的兴趣度比较高，在实验中图1的网络拓扑结构产生了如ABD=>F和AE=>C这样的有趣频繁访问页组。我们可以根据这样兴趣度高的规则来调整和改善网络的拓扑结构。网络拓扑修改后如图2所示：

图2 改善的网络拓扑结构

    实验结果表明：MIR算法在规则的有趣度方面有较大的改善，大大提高规则的利用率，可以很好的用于网络拓扑结构的改善。

[ 1 ] R Agrawal，T Imielinski and A Swami. Mining association rulesbetween sets of items in large databases[M ]. Washington，D. C.SIGMODp93，207 - 216

[ 2 ] R Agrawal and R Srikant. Fast algorithms for mining associationrules[ C ]. In J. B. Bocca，M. Jarke，and C. Zaniolo，editors，Proceedings 20 th International Conference on Very Large Databas2es，Morgan Kaufmann，1994. 487 - 499

[ 3 ]G Liu，H Lu，Y Xu，J X. Yu. Ascending Frequency OrderedPrefix - tree：EfficientMining of Frequent Patterns [ C ]. Proc.2003 Int. Conf. on Database Systems for Advanced App lications(DASFAAp03)，Kyoto，Japan，March 2003

[ 4 ]Mohammad El - Hajj and Osmar R Za? ane，COFI - treeMining[ C ]. A New App roach to Pattern Growth with Reduced Candida2cy Generation，in Workshop on Frequent ItemsetMining Imp le2mentations ( FIM Ip03) in conjunction with IEEE - ICDM 2003，Melbourne，Florida，USA，19 November，2003

[ 5 ]Han J，Pei J，Yin Y. M ining frequent pat ternsw ithoutcandidate generat ion [A ]. P roc 2000 A CM 2S IGM ODInt Conf on M anag em ent of D ata (S IGM OD ′00) [C ].Dallas，2000. 1212

[6 ]周欣，沙朝锋，朱杨勇，施伯乐．兴趣度——关联规则的又一个阀值．计算机研究和发展，2000.5