用户访问模式挖掘及在电子商务中的应用(2)
2014-06-02 01:14
导读：1．站点结构的分析 每个Web网站并不是平面结构，而是有自己的特定结构。我们可将Web结构看作是一个多层的模型，每个层面包含很多页面，这些页面上有
1．站点结构的分析
每个Web网站并不是平面结构，而是有自己的特定结构。我们可将Web结构看作是一个多层的模型，每个层面包含很多页面，这些页面上有很多文本、图片、
音乐等页面元素组成，它们可以链接本层面或其他层面的页面元素。
Web可以用一个有向图来表示，G=(V，E)，V是页面的集合，E是页面之间的超链接集合。页面抽象为图中的顶点，而页面之间的超链接抽象为图中的有向边。顶点v的进边表示对v的引用，出边表示v引用了其它的页面。 所以Web页面之间的超链接揭示了Web结构。通过对Web结构的分析可对Web数据挖掘有很大的帮助，如图4，某站点拓扑结构示例图。
2．基于图结构的用户访问模式挖掘算法
Web用户访问模式的挖掘过程可描述为：把用户会话序列看成是对图的遍历，结合数据库和Web图结构确定访问的最大向前路径。从中找出支持度大于阈值的所有子路径即频繁遍历路径，最后确定最大频繁遍历路径。基于图结构的用户访问模式的挖掘和现有方法最大的不同是，访问模式也被以为是图遍历，而不是二叉树访问顺序，即用户会话序列是图中的路径。
(1)天生最大向前路径
Web用户访问模式的挖掘过程的第一步是把用户会话序列看成是对图的遍历，结合数据库和Web图结构确定访问的最大向前路径。所谓最大向前路径(MFP)是指从起始页开始到回溯发生前，用户连续访问的最大页面序列。
假设
代表一个用户会话，代表一个含有潜伏MFP的字符串，初值为空，f1ag表明当前的遍历方向是前进还是后退，数据库D存储MFP序列。算法依次对每一个用户会话进行如下操纵： （转载自http://zw.nseac.coM科教作文网）
①依次读取页面xi(1≤i≤m)。
②若Xi不存在于{y1，…，y-1}中，即xi是没有访问过的页面，则将xi作为yj加进当前可能的MFP中，f1ag标记为前进，转(1)。
③否则若xi=yk(1≤k 假如f1ag标明前进遍历，则将{y1，…，y-1}作为一个M F P输出到最大前向路径集合F中，然后从中删除{yk 1，…，yj-1}，并设标志f1ag为向后移动，转(1)。
假如flag标明为回退，删除{yk i，…，yj-1}后转(1)。
④当处理到用户会话中的最后一页时，假如f1ag标志仍-标明向前，则此时的{y1，…，yj 1}是该会话中的最后一个MFP。 此算法的形式化描述如下：
for aU Sn∈S //依次处理绘画文件中的每个会话Sn1
y1=x1；j=2；i=2 f1ag=YES； ////初始化页面序列，将遍历方向设置为前进；
while(i≤m)//循环处理用户会话Sn中每个页面；
{
if(xi==yk)for some 1≤k (2)挖掘频繁遍历路径
频繁遍历路径是指MFP中满足一定支持度的子路径序列(不是连续页面序列)。频繁遍历路径的确定能用像Aprior算法中的逐层搜索算法实现。在算法的每步中，都要扫描数据库，并计算所有的候选集的支持度。每步中的所有候选集都有相同的长度。在每个过程的结束，天生候选集Ck，然后计算Ck中每个候选项的支持度并剪除小于支持度阈值的候选项，以减少下一循环的扫描时间，由此频繁遍历路径集合Lk被确定，并用于在下个步中候选集的计算。算法的一般结构如下。支持度的最小值记为minSupport，Ck表示所有长度为k的候选集，Lk表示所有长度为k的频繁遍历路径的集合，D表示数据库，G表示图。 （科教范文网http://fw.ΝsΕΑc.com编辑）
算法4－逐层搜索确定图G中的频繁遍历路径 尽管逐层搜索算法的基本结构相似于Apriori，但是它的组成部分(i)候选集支持度计算(ii)产生下一阶段的候选集，明显不同于Apriori，由于，该算法中的候选集必须是图中的路径。该算法基于定理4执行Apriori剪除。对于支持度计算(第6，7步)，基于子路径的数目。
