摘 要:Web使用模式挖掘是Web数据挖掘的重要研究内容。本文详细介绍了Web使用模式挖掘中的路径分析技术，并将AprioriAll算法引入路径分析过程，对其发展前景做了合理的展望。
关键词:Web数据挖掘Web使用模式挖掘路径分析技术
中图分类号：TP393文献标识码：A 文章编号：1007-9416（2010）10-0028-02
1 引 言
数据挖掘（Data Mining）就是从数据库中发现隐藏在其中的、潜在的有用信息，并把大量的原始数据转换成有价值的知识的一门新兴科学。随着数据库技术的飞速发展，尤其是随着Web应用技术的不断发展和进步，Web资源以指数级模型飞速增长。面临着浩瀚无边的Web数据，人们呼唤在数据的汪洋中去伪存真、去粗存精，因此以网络数据为挖掘对象的Web数据挖掘技术应用而生[1]。
Oren Etioni在1996年首次提出Web数据挖掘这一概念。Web数据挖掘就是运用数据挖掘技术在服务器Web文档中自动发现并提取有用的信息，它是数据库、信息检索、人工智能、机器学习与自然语言处理等几个相关研究领域的聚合[2]。目前比较盛行的分类就是根据其挖掘对象将其大致分为三类：Web内容挖掘、Web结构挖掘、Web使用模式挖掘。
2 Web使用模式挖掘
Web使用模式挖掘是在用户访问Web页面后，对服务器上留下的访问路径进行挖掘，即对用户访问Web站点的存取方式进行挖掘。其挖掘目的是在海量的Web日志数据中自动、快速地发现用户的访问模式，例如频繁访问页组、频繁访问路径、用户行为聚类等。Web使用模式挖掘常用技术有如下几种：
（1）关联规则挖掘技术（Associate Mining Technology）。在Web数据挖掘中，关联规则挖掘就是要挖掘出用户在一个访问期间内在服务器中访问的页面、文档之间的联系。最为著名的关联规则发现方法是R.Agrawal提出的Apriori算法，从事务数据中挖掘出最大频繁访问项集，这个项集就是关联规则挖掘出来的用户访问模式。
（2）序列模式挖掘技术（Sequence Mining Technology）。序列模式挖掘就是要挖掘出交易集之间的有时间序列的模式。在网站服务器日志里，用户的访问是以时间段为单位记录的，经过数据清洗和事务识别以后是一个间断的时间序列，这些序列反映的用户行为有助于网站确认用户访问网站的兴趣所在。
（3）分类与聚类技术（Classification & Clustering）。分类规则可以挖掘Web日志中某些共同的特性，利用该特性对新添到数据库里的数据项进行分类，根据访问模式得出访问某一服务器文件的用户特性。聚类分析用于将有相似特性的用户、数据项集合到一起，聚类的目标是将大量的数据项聚集成类，使得类与类之间的相似度尽量小，而类内的相似度尽量大。
（4）路径分析技术（Route Analysis Technology）。在Web使用模式挖掘过程中，通过路径分析技术可以确定网站的频繁访问路径，可以对频繁访问的路径进行优化，并可以在频繁访问的路径上放置重要的信息，如导航信息等，以方便用户使用[3]。通过路径分析技术得出的网站结构图在模式挖掘中非常有用。
本文阐述的路径模式挖掘实质就是一种路径分析技术，可用来确定Web中一条频繁出现的浏览路径。
3 路径模式挖掘
3.1 概 念
在因特网上用户一次浏览中依次访问的站点形成浏览路径，从浏览路径中发现潜在的知识的过程，成为路径模式挖掘（Path Pattern Mining）。
3.2 步 骤
（1）生成最大向前引用。由浏览过程中的每个站点构成的序列成为原始路径，既包括到达一个新页面的向前引用，也包括由于访问失败或未找到所需信息造成的向后的引用。只有向前引用是有用的信息，因此从原始路径中删除向后引用，得到一组浏览子序列，其中每个子序列是从用户的访问起点开始的最大向前引用。我们结合实例来说明，如图1所示：原始路径为：{A，B，C，D，C，B，E，F，G，F，H，A，I，J，I，K}，那么最大的向前的引用集为{{ABCD}，{ABEFG}，BEFH}，{AIJ}，{AIK}}。
（2）从得到的最大向前引用中获取大引用序列（large reference sequence）。即在全部浏览过程出现次数超过给定阈值的序列。大引用序列的搜索从一维开始，利用迭代找到所有满足阈值的引用序列。
（3）确定最大引用序列，即不包含在其他任何最大引用序列中的大引用序列。一个最大引用序列对应于Web中一条频繁出现的浏览路径。对上面的例子，假设{{AB}，{BE}，{AD}，{CF}，{FG}，{BF}}是二维的大引用序列，{{ABE}，{CFG}}是三维的大引用序列，那么最大引用序列为{{ABE}，{CFG}，{AD}，{BF}}。
得到的最大引用序列后，就可以根据用户已经访问过的站点来预测他将要访问的站点，提高网络相应速度，优化网站结构，为用户提供更加便捷的服务。
4 算法描述
4.1 生成最大先前引用算法
在生成最大先前引用的过程中，考虑到要把原始路径中的那些向后引用删除，我们使用一个堆栈。堆栈的特点就是“先进先出，后进后出”。利用堆栈的这个特性，在删除向后引用时只需要对栈顶元素判断即可[4]。具体过程是：
A．选取第一个顶入栈。第一个项即用户访问的第一个Web站点。
B．对栈顶的项如果有向前引用，则把这个项的一个向前引用的站点入栈，重复B；否则，从栈底到该项构成了一个最大向前引用，且以该项为这个最大向前引用的终点。把该项最大向前引用加入到最大向前引用集。
C．对栈顶的项如果有向后引用，则把这个想的一个向前引用的项出栈；再对栈顶项判断时候有不同于刚出栈的先前引用，有的话把该项入栈，否则重复C。
D．如果栈顶项的向前引用和栈底项相同，则该项也是一个最大向前引用的终点。从栈底到该项构成了一个最大向前引用，把该最大向前引用加入到最大向前引用集，然后把栈中除了栈底项的其他项全部出栈。
E．如果栈顶项的所有向前引用都已遍历过，且没有向后引用，则算法结束。
4.2大引用序列生成算法
寻找大引用序列与关联规则中的大项集有相似之处。它们都是满足在事务库中出现的足够次数(规定的阈值)，但是大引 用序列必须是连续且有顺序的，而大项集仅仅是项的组合，根据这个特点，本文运用序列模式挖掘中的大序列计算机方法AprioriAll算法，从第一步生成的最大向前引用集中找到满足阈值的所有大引用序列，这就满足了有序性。
AprioriAll算法的详细过程描述如下：
L1={frequent items};//1阶大序列
for(k=2;LK-1≠￠;k=k+1)do
CK=Get_candidate(Lk-1);/*利用函数Get_candidate构造侯选序列*/
forall customer sequence c Dt do
Ct=subset(CK,c);/*计算最大向前引用序列C所包含的候选序列*/
forall s∈Ct do s.sup = s.sup+1;
end for/*累计支持数*/
end for
LK={s∈CK|s.sup>=minsup};/*计算K阶大序列*/
endfor
L=YKLK
为了减少侯选序列的个数，侯选序列的构造用Get_candidate函数来实现。这里用到这样一个性质t如果A是大序列，那么A的所有子序列也必定是大序列。反之，如果一个序列的某个子序列不是大序列．那么这个序列也一定不是大序列。根据这个性质，Get_candidate通过自连接和消减两个步骤来构造候选序列，降低算法扫描数据库的次数，提高算法效率[5]。
4.3生成最大引用序列算法
在得到的大引用序列集合中，假设大引用序列的最大维数为n，从n维大引用序列开始检查每个大引用序列。删除它所含的子引用序列，即可得到最大引用序列。这个过程可以描述如下：
for(k=n;k>=1;k=k-1)do
for each K-large reference sequence S do／*检查每个K维大引用序列*／
{if(subsequence is sequential)
delete all sequential subsequences of S}／*删除S中的子引用序列*／
endfor
endfor
5 结 语
本文将AprioriAll算法引入路径分析过程，处理了用户所访问站点之间的先后顺序问题。随着电子政务和电子商务的高速发展，对所得的频繁访问路径进行优化，如添加导航信息，给访问频率较高的页面添加链接，起到提高办公效率作用。通过路径模式挖掘可以确定网站的频繁访问路径，预测用户的浏览行为，知道用户的兴趣及需求所在。网站的管理员可在服务器端动态地调整Web页面，进一步改善网站结构，为用户提供个性化服务以满足客户的需求。
参考文献
[1] 陈安，陈宁，周龙骧等．数据挖掘技术及应用[M]．北京：科学出版杜，2009.
[2] 蒋望东，黄良发．基于Web数据挖掘综述[J]．湖南工程学院学报，2007，17（1）：61～64.
[3] Dunham M H 著．郭崇慧等译．Data Mining[M]．北京：清华大学出版社，2008.
[4] 刘炜，陈俊杰．一种Web使用模式挖掘模型的设计[J]．计算机应用研究，2007，24（3）：184～186.
[5] 谷秀岩．Web使用模式挖掘的研究[J]．计算机工程与应用，2007，16：175～177.
