D0I:10.13374/1.issnl00I53.2006.09.020 第28卷第9期 北京科技大学学报 Vol.28 No.9 2006年9月 Journal of University of Science and Technology Beijing Sep·2006 一种分布式Wb使用模式挖掘模型及算法 张克君1,2) 杨炳儒)赵耿)曲文龙)李欣) 1)北京电子科技学院计算机科学与技术系，北京1000702)北京科技大学信息工程学院，北京100083 摘要给出了一种分布式Wb日志挖掘模型DWLMS.根据对挖掘过程及算法进行分析，提出 了一种基于DWLMS的局部频繁路径的更新算法LFP和全局频繁路径的更新算法GFP,较好地 解决了Wb访问信息的异地存储、实时增长、，分布式算法通讯量等因素给模式分析过程带来的困 难。在实验室对该方法进行了简单实现和实际日志数据的测试，结果表明了算法的有效性， 关键词分布式数据挖掘：Wh使用模式挖掘：Weh日志挖掘：频繁路径 分类号TP311.13 Weh使用模式挖掘，又称Wb日志挖掘，是 从Wb的访问记录中抽取感兴趣的模式的过 1 DWLMS模型及相关概念 程1②]，其常用的技术有WEB挖掘特有的路径分 1.1 DWLMS基本思想 析技术和数据挖掘领域的传统技术，现有路径分 分布式Wb使用挖掘系统模型DWLMS的 析技术一般基于Chen等在文献[3]中的工作， 基本思想（图1）：采用基于分布式数据库基础上 Alexandros Nanopoulos Yannis ManolopoulosF 的全局局部站点的数据挖掘模式，由全局和局 2001年又提出了MF,FS,SS算法[，这些算法 部站点协同完成分布式全局模式挖掘任务，全局 都是用于集中式数据库系统中的挖掘算法， 用户控制挖掘的过程，发出挖掘指令，局部站点 目前，人们对分布式数据挖掘(DDM)的研究 接受指令，并执行任务一对增量部分的日志 已取得了一些进展，并提出了一些分布式数据挖 Log:进行预处理等，生成局部用户访问事务增量 掘算法和分布式数据挖掘体系，如PADMA[], d:执行局部增量挖掘算法，产生局部模式F:, CDMO,HDM门和DDMINER8]等.所谓分布 并保存于局部模式库中：将局部模式的支持数及 式数据挖掘就是使用分布式算法，从逻辑上或物 局部模式F:传送给全局站点，全局站点整合所 理上分布的数据源中发现知识的过程， 有局部站点的局部模式F,从中找出全局模式知 本文对多镜像站点环境下的分布式日志挖掘 识F,保存在全局模式知识库中，以供局部站点访 系统中频繁访问路径模式挖掘进行了研究，主要 问 讨论了站点访问日志量增加时频繁访问路径如何 对于分布式系统，尽量减少传输量是至关重 高效更新的问题，提出了一种基于多镜像站点的 要的，提出的局部或全局挖掘算法将致力于减少 分布式Web使用挖掘系统模型(distributed Web 传输无效信息的冗余量，另外，如果系统在传输 log mining system,DWLMS),以及基于DWLMS 信息时采用广播的方式，则系统需要O(n)的通 的局部频繁访问路径的更新算法LFP和全局频 信量，其中n为系统中站点的个数，而DWLMS 繁访问路径的更新算法GFP,该算法能够产生较 采用全局一局部站点模式，因此系统在传输相同 少数量的频繁访问路径候选集，减小网络通信量， 信息时只需要O(n)的通信量， 有效解决了Wb访问信息的异地存储、实时增 1.2相关概念与理论 长、分布式算法通讯量等因素给模式分析过程带 定义1用户会话，设V={v1,v2,,0m} 来的问题 是网站上网页的集合，一个会话S是同一用户在 收稿日期：2005-07-20修回日期：2005-09-09 一次浏览过程中连续请求的页面序列，它代表了 基金项目：国家自然基金资助项目(N。·70431002)和北京电子 用户对服务器的一次有效访问，记为S=〈p1, 科技学院重点实验室资助项目 p2,…,P）,p:∈V·每一个会话具有惟一会话标 作者简介：张克君(1972一)，男，博士：杨炳儒(1943一)，男，教 授，博士生导师 识sessionID
一种分布式 Web 使用模式挖掘模型及算法 张克君12） 杨炳儒2） 赵 耿1） 曲文龙2） 李 欣2） 1） 北京电子科技学院计算机科学与技术系北京100070 2） 北京科技大学信息工程学院北京100083 摘 要 给出了一种分布式 Web 日志挖掘模型 DWLMS．根据对挖掘过程及算法进行分析提出 了一种基于 DWLMS 的局部频繁路径的更新算法 LFP 和全局频繁路径的更新算法 GFP较好地 解决了 Web 访问信息的异地存储、实时增长、分布式算法通讯量等因素给模式分析过程带来的困 难．在实验室对该方法进行了简单实现和实际日志数据的测试结果表明了算法的有效性． 关键词 分布式数据挖掘；Web 使用模式挖掘；Web 日志挖掘；频繁路径 分类号 TP311∙13 收稿日期：20050720 修回日期：20050909 基金项目：国家自然基金资助项目（No．70431002）和北京电子 科技学院重点实验室资助项目 作者简介：张克君（1972—）男博士；杨炳儒（1943—）男教 授博士生导师 Web 使用模式挖掘又称 Web 日志挖掘是 从 Web 的访问记录中抽取感兴趣的模式的过 程［12］其常用的技术有 WEB 挖掘特有的路径分 析技术和数据挖掘领域的传统技术．现有路径分 析技术一般基于 Chen 等在文献 ［3］ 中的工作 Alexandros Nanopoulos 和 Yannis Manolopoulos 于 2001年又提出了 MFFSSS 算法［4］．这些算法 都是用于集中式数据库系统中的挖掘算法． 目前人们对分布式数据挖掘（DDM）的研究 已取得了一些进展并提出了一些分布式数据挖 掘算法和分布式数据挖掘体系如 PADMA ［5］ CDM ［6］HDM ［7］ 和 DDMINER ［8］ 等．所谓分布 式数据挖掘就是使用分布式算法从逻辑上或物 理上分布的数据源中发现知识的过程． 本文对多镜像站点环境下的分布式日志挖掘 系统中频繁访问路径模式挖掘进行了研究主要 讨论了站点访问日志量增加时频繁访问路径如何 高效更新的问题提出了一种基于多镜像站点的 分布式 Web 使用挖掘系统模型（distributed Web log mining systemDWLMS）以及基于 DWLMS 的局部频繁访问路径的更新算法 LFP 和全局频 繁访问路径的更新算法 GFP．该算法能够产生较 少数量的频繁访问路径候选集减小网络通信量 有效解决了 Web 访问信息的异地存储、实时增 长、分布式算法通讯量等因素给模式分析过程带 来的问题． 1 DWLMS 模型及相关概念 1∙1 DWLMS 基本思想 分布式 Web 使用挖掘系统模型 DWLMS 的 基本思想（图1）：采用基于分布式数据库基础上 的全局—局部站点的数据挖掘模式由全局和局 部站点协同完成分布式全局模式挖掘任务．全局 用户控制挖掘的过程发出挖掘指令．局部站点 接受指令并执行任务———对增量部分的日志 Log ＋ i 进行预处理等生成局部用户访问事务增量 d ＋ i ；执行局部增量挖掘算法产生局部模式 F′i 并保存于局部模式库中；将局部模式的支持数及 局部模式 F′i 传送给全局站点．全局站点整合所 有局部站点的局部模式 F′i从中找出全局模式知 识 F保存在全局模式知识库中以供局部站点访 问． 对于分布式系统尽量减少传输量是至关重 要的提出的局部或全局挖掘算法将致力于减少 传输无效信息的冗余量．另外如果系统在传输 信息时采用广播的方式则系统需要 O（ n 2）的通 信量其中 n 为系统中站点的个数而 DWLMS 采用全局—局部站点模式因此系统在传输相同 信息时只需要 O（ n）的通信量． 1∙2 相关概念与理论 定义1 用户会话．设 V ＝｛v1v2…v m｝ 是网站上网页的集合一个会话 S 是同一用户在 一次浏览过程中连续请求的页面序列它代表了 用户对服务器的一次有效访问记为 S ＝〈p1 p2…p n〉pi∈ V ．每一个会话具有惟一会话标 识 sessionID． 第28卷 第9期 2006年 9月 北 京 科 技 大 学 学 报 Journal of University of Science and Technology Beijing Vol．28No．9 Sep．2006 DOI:10．13374／j．issn1001－053x．2006．09．020
Vol.28 No.9 张克君等：一种分布式Web使用模式挖掘模型及算法 .897. 表示层 事务层 资源层 框架 全局控制 数据挖掘处理 全局模式库 Struts (全局挖掘) (GFP) Drivers/ 应用服务器 Adapter HTML/JSP ∈今RM 预处理对象 浏览器 分布式预处理 局部事务库 局部控制 数据挖掘处理 (LDB) (局部挖掘) 局部模式库 数据挖掘处理 (LFP) 《高部挖掘) 应用服务器 资源 图1分布式Web日志挖据系统体系结构(DVLS) Fig.1 Architecture of a distributed Web log mining system 定义2访问路径，用户会话中由连续页面 假设X:FP',则每个站点上X的支持数 构成的子页面序列，可以表示为P=〈p1,p2,…, S:(X)<X minsup,从而得到X∈FP, p),P:∈V,一个k路径是长度为k的访问页 面序列. s)空0空 Xminsup, 定义3最大向前访问路径.用户会话中从 这与X∈FP矛盾，证毕 起点开始的一次最大访问路径，简称MFP 定理1表明，所有局部站点提取的局部频繁 定义4频繁访问路径，最大向前路径MFP 访问路径的总和一定包含全局频繁访问路径集， 中满足一定支持度的子路径序列（包含频繁访问 也就是说，若X是全局频繁的，则一定存在某个 路径的MFP的个数占全部MFP数量的比例叫 站点使得X在该站点是局部频繁的，反之，如果 支持度)·局部事务数据库中生成的频繁访问路 X是局部频繁的，那X不一定是全局频繁的 径集称为局部频繁访问路径集；全局事务数据库 定义6重频繁路径，若X既是某站点的局 中生成的频繁访问路径集称为全局频繁访问路径 部频繁访问路径，又是全局频繁路径，则称X为 集，记为FP 该站点的重频繁路径，显然，某站点的重频繁路 定义5事务数据库.设分布式系统中位于 径包含于该站点的局部频繁路径集合中 N个站点的事务数据库分别为{D1,D2,…, 性质1若X是某站点的重频繁路径，则X Dxi,DB=D1UD2UUDw,则D:(1≤i≤N) 的所有子集也是该站点的重频繁路径 称为局部事务数据库，D称为全局事务数据库. 根据定理1和性质1可得性质2. 定理1设分布式挖掘系统中站点i上的局 性质2若X是全局频繁k路径，则存在一 部频繁访问路径集为FP=1,2,…,N,将所有站 个站点P:(=1,2,…,N)使得X以及它的所有 点上的FP:合并得到集合FP,则FP一定是全局 (k一1)路径子集在站点P:为重频繁路径 频繁访问路径集FP的超集 2 频繁路径挖掘过程算法 证明要证FP是全局频繁访问路径集FP 的超集，只要证HX∈FP,则X∈FP, 2.1局部挖掘事务库生成 设最小支持度为minsup,每个站点的事务记 Web使用挖掘的数据预处理过程如图2所 录数为ni,=1,2,…,N,X在第i个站点的支持 示，包括数据净化、用户识别、会话识别、路径补充 数为S:(X),因为X∈FP,所以X的全局支持数 和事务识别等步骤1】.局部日志预处理的主要 s(x)=空s.(x)空n 职责就是对本次该服务器日志增加数据Lg进 Xminsup 行处理，产生对应的新增加的事务集合d.其中
图1 分布式 Web 日志挖掘系统体系结构（DWLMS） Fig．1 Architecture of a distributed Web log mining system 定义2 访问路径．用户会话中由连续页面 构成的子页面序列可以表示为 P＝〈p1p2… pk〉pi∈ V ．一个 k—路径是长度为 k 的访问页 面序列． 定义3 最大向前访问路径．用户会话中从 起点开始的一次最大访问路径简称 MFP． 定义4 频繁访问路径．最大向前路径 MFP 中满足一定支持度的子路径序列（包含频繁访问 路径的 MFP 的个数占全部 MFP 数量的比例叫 支持度）．局部事务数据库中生成的频繁访问路 径集称为局部频繁访问路径集；全局事务数据库 中生成的频繁访问路径集称为全局频繁访问路径 集记为 FP． 定义5 事务数据库．设分布式系统中位于 N 个站点的事务数据库分别为｛D1D2… DN｝DB＝ D1∪ D2∪…∪ DN则 Di（1≤ i≤ N） 称为局部事务数据库DB 称为全局事务数据库． 定理1 设分布式挖掘系统中站点 i 上的局 部频繁访问路径集为 FP′i＝12…N将所有站 点上的 FP′i 合并得到集合 FP′则 FP′一定是全局 频繁访问路径集 FP 的超集． 证明 要证 FP′是全局频繁访问路径集 FP 的超集只要证∀X∈FP则 X∈FP′． 设最小支持度为 minsup每个站点的事务记 录数为 nii＝12…NX 在第 i 个站点的支持 数为 Si（ X）因为 X∈FP所以 X 的全局支持数 S（ X）＝ ∑ N i＝1 Si（ X）≥ ∑ n i＝1 ni ×minsup． 假设 X∈／FP′则每个站点上 X 的支持数 Si（ X）＜ ni × minsup从 而 得 到 X ∈ FP S（ X）＝ ∑ N i＝1 Si（ X）＜ ∑ N i＝1 ni ×minsup 这与 X∈FP 矛盾．证毕 定理1表明所有局部站点提取的局部频繁 访问路径的总和一定包含全局频繁访问路径集． 也就是说若 X 是全局频繁的则一定存在某个 站点使得 X 在该站点是局部频繁的．反之如果 X 是局部频繁的那 X 不一定是全局频繁的． 定义6 重频繁路径．若 X 既是某站点的局 部频繁访问路径又是全局频繁路径则称 X 为 该站点的重频繁路径．显然某站点的重频繁路 径包含于该站点的局部频繁路径集合中． 性质1 若 X 是某站点的重频繁路径则 X 的所有子集也是该站点的重频繁路径． 根据定理1和性质1可得性质2． 性质2 若 X 是全局频繁 k—路径则存在一 个站点 Pi（ i＝12…N）使得 X 以及它的所有 （ k—1）路径子集在站点 Pi 为重频繁路径． 2 频繁路径挖掘过程算法 2∙1 局部挖掘事务库生成 Web 使用挖掘的数据预处理过程如图2所 示包括数据净化、用户识别、会话识别、路径补充 和事务识别等步骤［12］．局部日志预处理的主要 职责就是对本次该服务器日志增加数据 Log ＋ i 进 行处理产生对应的新增加的事务集合 d ＋ i ．其中 Vol．28No．9 张克君等： 一种分布式 Web 使用模式挖掘模型及算法 ·897·
898 北京科技大学学报 2006年第9期 事务识别环节是重要的，事务识别是对用户会话 库d中； 进行语义分组，通常采用Chen等人提出的最大 (14)y1=x::j=2;flag=TRUE: 向前引用路径（简称为MFP)]来定义事务.事 (l5)f(flag=TRUE)then将y,…,yD 务的具体意义是：用户为获得一项有意义的信息 作为MFP输出到事务库d中； 所点击的页面序列，也就是用户会话中的每一次 (16)} 前进浏览的第一页到回退的前一页组成的路径 局部日志数据预处理的结果是局部事务库中 获得有意义的事务，是保证Wb使用挖掘结果可 的增量集d, 靠性的关键，为此，本文提出了一种事务识别算 2.2局部频繁访问路径更新算法 法如下 为便于表述，定义如下符号，如表1所示. 表1频繁访问路径挖掘相关符号的定义 数据净化 、会话识别 佣户会话文件 Table 1 Symbols definition about frequent access paths mining 事务数据库路径X的支持数颜繁路径集重频繁路径集 访问 用户识别 路径补充 、事务识别。 引志增量 d supi (X) D supi(X) Li(i) H(i) (结构化处理 D=D:Ud () () 站点文作 站点结构 事务增量 sup(X) 其中，D:为第i站点更新后的事务数据库， 图2局部Wh日志挖掘预处理的具体过程 Fig.2 Preprocessing of local Web log mining 显然，D=D:Ud,D:=D-d;sup:(X)为D: 中路径X的支持数；L()为D:中的频繁访问路 设x1,,x)表示一个用户会话，设y1, 径集；Lk(i)为L(i)中的频繁k路径集；H(i)为 …,ym)代表一个含有潜在MFP,flag表示当前用 D:中的重频繁路径集；H,(i)为H(i)中的重频 户浏览路径方向(flag=TRUE表示向前，flag= 繁k路径集；sup:(X)为更新后事务数据库D:中 FALSE表示后退)，事务库用d表示，网站的拓 路径X的支持数；L()为D:中的频繁路径集； 扑结构用有向图G表示，则用户会话文件生成 Lk(i)为L'(i)中的频繁k路径集；H'(i)为D: MFP事务库的算法为： 中的重频繁路径集；H()为H()中的重频繁 算法1基于站点图结构的事务识别算法 k路径集；sup(X)为d中路径X的支持数， MFP 输入：用户会话文件 根据支持数的定义可得如下性质3. 输出：MFP事务库d 性质3sup(X)=sup:(X)十sup(X) (I)for each Session∥扫描会话文件 全局频繁路径集的获取，是建立在各局部站 (2)yI=x1:j=2:i=2:flag=TRUE: 点局部频繁路径集更新整合基础上的，在前次获 (3)for(≤m;i++)1 取频繁路径集的挖掘过程中，已经得到L()和 (4)fx:=yg,1≤kj)1 sup:(X),HX∈L(i)·因此，局部频繁路径集更 (5)if (flag=TRUE)then 新任务就是，给定D,D:,d,L(i)和sup(X), (6)将y1,…,y-D作为MFP输出到事务 对于HX∈L'(i),如何高效计算L'(i)和 库d中； sup(X)· (7)j=k+1:flag=FALSE: 为了求解D:中的频繁路径集L(),给出局 (8)else{j=k+1:} 部频繁路径集更新算法LFP,其方法是：用类似 (9)lelsel 于Apriori算法的迭代方法，从频繁k路径候选 (I0)议-1，x)为G的有向边then{∥经 集Ck(i)中求出所有频繁k路径集Lk(i),首先 过链接到达 需要用频繁k一1项集生成长度为k的候选集，记 (11)yj=x::j=j+1:flag=TRUE: 为CAk(i)=candidate-gen(Lk-1(i),但是，在 (12)else∥该页由用户直接输入url访问 分布式环境中，Lk-1()中有些路径集不是全局 的 频繁的，由Lk-1()产生的C()集合必定比较大， (13)将y1,…,y-)作为MFP输出到事务 这是不可取的，这里给出k路径候选集的生成算
事务识别环节是重要的事务识别是对用户会话 进行语义分组．通常采用 Chen 等人提出的最大 向前引用路径（简称为 MFP） ［3］ 来定义事务．事 务的具体意义是：用户为获得一项有意义的信息 所点击的页面序列也就是用户会话中的每一次 前进浏览的第一页到回退的前一页组成的路径． 获得有意义的事务是保证 Web 使用挖掘结果可 靠性的关键．为此本文提出了一种事务识别算 法如下． 图2 局部 Web 日志挖掘预处理的具体过程 Fig．2 Preprocessing of local Web log mining 设〈x1…xm〉表示一个用户会话设〈y1 …ym〉代表一个含有潜在 MFPflag 表示当前用 户浏览路径方向（flag＝TRUE 表示向前flag＝ FALSE 表示后退）事务库用 d ＋ i 表示网站的拓 扑结构用有向图 G 表示．则用户会话文件生成 MFP 事务库的算法为： 算法1 基于站点图结构的事务识别算法 MFP 输入：用户会话文件 输出：MFP 事务库 d ＋ i （1） for each Session｛∥扫描会话文件 （2） y1＝ x1；j＝2；i＝2；flag＝TRUE； （3） for （ i≤ m；i＋＋）｛ （4） if ｛xi＝yk1≤k＜ j）｛ （5） if （flag＝TRUE） then｛ （6） 将〈y1…yj—1〉作为 MFP 输出到事务 库 d ＋ i 中； （7） j＝k＋1；flag＝FALSE；｝ （8） else｛j＝k＋1；｝ （9）｝else｛ （10） if〈yj—1xi〉为 G 的有向边 then｛∥经 过链接到达 （11） yj＝ xi；j＝ j＋1；flag＝TRUE； （12）｝else｛∥该页由用户直接输入 url 访问 的 （13） 将〈y1…yj—1〉作为 MFP 输出到事务 库 d ＋ i 中； （14） y1＝ xi；j＝2；flag＝TRUE；｝｝｝ （15） if （flag＝TRUE） then 将〈y1…yj—1〉 作为 MFP 输出到事务库 d ＋ i 中； （16）｝ 局部日志数据预处理的结果是局部事务库中 的增量集 d ＋ i ． 2∙2 局部频繁访问路径更新算法 为便于表述定义如下符号如表1所示． 表1 频繁访问路径挖掘相关符号的定义 Table1 Symbols definition about frequent access paths mining 事务数据库 路径 X 的支持数 频繁路径集 重频繁路径集 d ＋ i sup ＋ i （ X） Di sup i（ X） L k（ i） Hk（ i） D′i＝ Di∪ d ＋ i sup′i（ X） L′k（ i） H′k（ i） 其中D′i 为第 i 站点更新后的事务数据库 显然D′i＝ Di∪ d ＋ i Di＝ D′i— d ＋ i ；sup i（ X）为 Di 中路径 X 的支持数；L （ i）为 Di 中的频繁访问路 径集；Lk（ i）为 L （ i）中的频繁 k—路径集；H（ i）为 Di 中的重频繁路径集；Hk（ i）为 H（ i）中的重频 繁k—路径集；sup′i（ X）为更新后事务数据库 D′i 中 路径 X 的支持数；L′（ i）为 D′i 中的频繁路径集； L′k（ i）为 L′（ i）中的频繁 k—路径集；H′（ i）为 D′i 中的重频繁路径集；H′k（ i）为 H′（ i）中的重频繁 k—路径集；sup ＋ i （ X）为 d ＋ i 中路径 X 的支持数． 根据支持数的定义可得如下性质3． 性质3 sup′i（ X）＝sup i（ X）＋sup ＋ i （ X）． 全局频繁路径集的获取是建立在各局部站 点局部频繁路径集更新整合基础上的．在前次获 取频繁路径集的挖掘过程中已经得到 L （ i）和 sup i（ X）∀X∈ L （ i）．因此局部频繁路径集更 新任务就是给定 DiD′id ＋ i L （ i）和sup i（ X） 对于 ∀X ∈ L′（ i ）如 何 高 效 计 算 L′（ i ） 和 sup′i（ X）． 为了求解 D′i 中的频繁路径集 L′（ i）给出局 部频繁路径集更新算法 LFP其方法是：用类似 于 Apriori 算法的迭代方法从频繁 k—路径候选 集 Ck（ i）中求出所有频繁 k—路径集 L′k（ i）．首先 需要用频繁 k—1项集生成长度为 k 的候选集记 为 CAk（ i）＝candidate—gen（ L′k—1（ i））．但是在 分布式环境中L′k—1（ i）中有些路径集不是全局 频繁的由 L′k—1（ i）产生的 Ck（ i）集合必定比较大 这是不可取的．这里给出 k—路径候选集的生成算 ·898· 北 京 科 技 大 学 学 报 2006年第9期
Vol.28 No.9 张克君等：一种分布式Web使用模式挖掘模型及算法 .899. 法，令CHk(i)=candidateFP-gen(Lk-1(i),函 supi(X)=supi(X)supi(X)<D:lXminsup+ 数candidateFP-gen的算法如下， Id:lXminsup=(I D:l+ldil)x 算法2局部候选路径生成算法candi- minsup=D:Xminsup, dateFP-gen 从而，由L'()的定义可知X廷L'()证毕 输入：频繁k路径集Lk 为了将Q:()中的某些非频繁路径删去， 输出：频繁(k+1)路径候选集 VX∈Q(i),扫描d,计算sup(X)·根据定理 (1)for each(y1,..,yL 2,若sup(X)≤|d|Xminsup,则将X从Q(i) (2)N={G中全部以y%为起点的有向边的 中删掉.对于Q(i)中的剩余项X,计算 终点的集合； sup(X)=sp:(X)十sup（X)若supi(X)≥ (3)for each v∈N (4)ifu≠y(1≤i≤k)and(y2,…,yg,以∈ |DI×minsup,则将X加入L'(k)中， Let 综上所述，算法LFP在站点i的第k次循环 的操作描述如下， (5)Cy1,…,y%,; 算法3局部频繁路径集更新算法LFP (6)S={路径C所有长度为k的子路径}； 输入：局部事务集合 (7)for each s∈S 输出：局部频繁访问路径集、局部频繁访问路 (8)fs∈Lk把C加入到Ck+1;} 径支持数 (9)} (1)if k=1 then C1(i)=Vielse (10)} (2)C(i)=candidateFP-gen(H-1(i)); 因为H-1(i)三Lk-1(i),所以CHk(i)三 (3)if C(i)=then break: CAk(),根据性质2，事务数据库更新后全局频 (4)将Ck()划分为两部分：P(i)和 繁k路径集 Qx(i); FP CH()= =1 (5)for each X∈P(i)UQu(i),扫描d, candidate-gen() 计算sup(X); (6)for each X∈Pk(i),计算sup:(X)= 显然通过重频繁路径集Hk-1(i)通过candi- dateFP-gen函数产生一个数量较小的频繁项目 sup(X)十sup(X); 候选集Ck(),这也是提出重频繁路径集概念的 (7)for each X∈Qu(i) 原因， (8)if supi (X)dilXminsup then delete 令Ck(i)=candidateFP-gen(H-i(i)).将 X from Q(i); C(i)划分为两个部分：P(i)=C(i)∩Lk(i), (9)for each X∈Qk(i) (1O)扫描D:,计算sup:(X)=sup:(X)十 Q(i)=Ck(i)一Px(i)其中P(i)是D:中的 supi (X) 频繁k项集；Q(i)是D:中的非频繁项目集，即 Q(i)是L(i) (11)for each XEP(i)Q(i) HX∈P(i),利用性质3可知：supi(X)= (l2)if supi(X)≥|D:IX minsup then将X 加入Lk() sup:(X)十sup(X),其中sup(X)通过扫描d 2.3全局频繁路径集产生算法 求得.如果sup:(X)≥|D:|×minsup,则X∈ 全局频繁路径集的更新是建立在局部频繁路 Le(i). 径集更新基础上的，即要找出全局频繁k一路径 HX∈Q(i),sup:(X)未知，但sup:(X)< 集，必须求解每个局部站点的频繁k路径集。前 |D:Xminsup,通过下面的定理2，可将Qs(i)中 面已经论述了局部频繁路径集的更新算法LFP, 的某些非频繁路径删掉， 本部分给出基于DWLMS系统的全局频繁路径 定理2如果XL(i),并且sup(X)≤ 集更新算法GFP,算法GFP采用迭代方法求解 |d|×minsup,则XL'(i) 事务数据库更新后的全局频繁k一路径集，k=1, 证明XL(i),则sup:(X)<|D:|X 2,…,N.各站点第k次循环迭代的步骤描述如 minsup,因此， 下
法令 CHk（ i）＝candidateFP—gen（ L′k—1（ i））函 数 candidateFP—gen 的算法如下． 算法 2 局 部 候 选 路 径 生 成 算 法 candidateFP—gen 输入：频繁 k—路径集 Lk 输出：频繁（ k＋1）—路径候选集 （1） for each〈y1…yk〉∈ Lk｛ （2） N＝｛G 中全部以 yk 为起点的有向边的 终点的集合｝； （3） for each v∈ N （4） if v≠yi（1≤ i≤k） and〈y2…ykv〉∈ Lk｛ （5） C＝〈y1…ykv〉； （6） S＝｛路径 C 所有长度为 k 的子路径｝； （7） for each s∈S （8） if s∈ Lk 把 C 加入到 Ck＋1；｝ （9）｝ （10）｝ 因为 H′k—1（ i）⊆ L′k—1（ i）所以 CHk （ i）⊆ CAk（ i）．根据性质2事务数据库更新后全局频 繁 k—路径集 FP′k⊆ ∪ N i＝1 CHk（ i）＝ ∪ N i＝1 candidate—gen（ H′k—1（ i））． 显然通过重频繁路径集 H′k—1（ i） 通过 candidateFP—gen 函数产生一个数量较小的频繁项目 候选集 Ck（ i）这也是提出重频繁路径集概念的 原因． 令 Ck（ i）＝candidateFP—gen（ H′k—1（ i））．将 Ck（ i）划分为两个部分：Pk（ i）＝ Ck（ i）∩ Lk（ i） Qk（ i）＝Ck（ i）— Pk（ i）．其中 Pk（ i）是 Di 中的 频繁 k 项集；Qk（ i）是 Di 中的非频繁项目集即 Qk（ i）∈／L l（ i）． ∀X∈ Pk （ i）利用性质3可知：sup′i （ X）＝ sup i（ X）＋sup ＋ i （ X）其中sup ＋ i （ X）通过扫描 d ＋ i 求得．如果sup′i （ X）≥｜D′i｜×minsup则 X ∈ L′k（ i）． ∀X∈ Qk （ i）sup i （ X）未知但sup i （ X）＜ ｜Di｜×minsup．通过下面的定理2可将 Qk（ i）中 的某些非频繁路径删掉． 定理2 如果 X ∈／L （ i）并且sup ＋ i （ X）≤ ｜d ＋ i ｜×minsup则 X∈／L′（ i）． 证明 X ∈／L （ i）则 sup i （ X ） ＜｜Di｜× minsup．因此 sup′i（ X）＝sup i（ X）＋sup ＋ i （ X）＜｜Di｜×minsup＋ ｜d ＋ i ｜×minsup＝（｜Di｜＋｜d ＋ i ｜）× minsup＝｜D′i｜×minsup 从而由 L′（ i）的定义可知 X∈／L′（ i）．证毕 为了将 Qk （ i）中的某些非频繁路径删去 ∀X∈ Qk（ i）扫描 d ＋ i 计算sup ＋ i （ X）．根据定理 2若sup ＋ i （ X）≤｜d ＋ i ｜×minsup则将 X 从 Qk（ i） 中删 掉．对 于 Qk （ i ） 中 的 剩 余 项 X计 算 sup′i（ X）＝sup i （ X）＋sup ＋ i （ X ）．若sup′i （ X ） ≥ ｜D′i｜×minsup则将 X 加入 L′（ k）中． 综上所述算法 LFP 在站点 i 的第 k 次循环 的操作描述如下． 算法3 局部频繁路径集更新算法 LFP 输入：局部事务集合 输出：局部频繁访问路径集、局部频繁访问路 径支持数 （1） if k＝1then C1（ i）＝ V i else （2） Ck（ i）＝candidateFP—gen（ H′k—1（ i））； （3） if Ck（ i）＝／○ then break； （4） 将 Ck （ i ） 划 分 为 两 部 分： Pk （ i ） 和 Qk（ i）； （5） for each X∈ Pk（ i）∪ Qk（ i）扫描 d ＋ i 计算sup ＋ i （ X）； （6） for each X ∈ Pk （ i）计算 sup′i （ X ） ＝ sup i（ X）＋sup ＋ i （ X）； （7） for each X∈ Qk（ i） （8） if sup ＋ i （ X）≤｜d ＋ i ｜×minsup then delete X from Qk（ i）； （9） for each X∈ Qk（ i） （10） 扫描 Di计算sup′i （ X ）＝sup i （ X ）＋ sup ＋ i （ X）； （11） for each X∈Pk（ i）∪ Qk（ i） （12） if sup′i（ X）≥｜D′i｜×minsup then 将 X 加入 L′k（ i）． 2∙3 全局频繁路径集产生算法 全局频繁路径集的更新是建立在局部频繁路 径集更新基础上的即要找出全局频繁 k—路径 集必须求解每个局部站点的频繁 k—路径集．前 面已经论述了局部频繁路径集的更新算法 LFP 本部分给出基于 DWLMS 系统的全局频繁路径 集更新算法 GFP．算法 GFP 采用迭代方法求解 事务数据库更新后的全局频繁 k—路径集k＝1 2…N．各站点第 k 次循环迭代的步骤描述如 下． Vol．28No．9 张克君等： 一种分布式 Web 使用模式挖掘模型及算法 ·899·
,900 北京科技大学学报 2006年第9期 算法4全局频繁路径集更新算法GP 机存储分布式事务数据库，并执行局部挖掘任务； (1)各局部站点根据局部频繁路径集更新算 另一台微机执行全局挖掘算法任务，分布式软件 法LFP的第k次循环迭代的过程，计算事务数据 平台及LFP/GFP更新算法采用J2EE技术实现. 库更新后的局部频繁路径候选集C4()及其支持 数据源为北京科技大学网站(www·ustb,edu,cn) 数，并将其发送给全局站点；保存局部频繁路径集 2周的访问日志，日志数据量总共是145MB,将 Lk()及其局部支持数： 其按时间分段并分布于3台微机中，进行分布式 (2)全局站点对所有局部频繁路径候选集 用户频繁访问路径挖掘算法LFP/GFP的运行结 Ck(i)进行合并，计算其全局支持数，扫描计算 果和性能测试，通过多次实验，结果表明频繁路 sup'(X)≥|D'|Xminsup,得到全局频繁k路径 径更新算法LFP/GFP的正确、有效性，例如，当， 集FPk,并将FPk发送到各局部站点； 全局4频繁访问路径及其支持数、局部4频繁路 (③)各局部站点将收到全局发来的FPk与本 径及其支持数的实验结果如表2.分析FP41路径 站点的局部频繁路径候选集Lk()进行比较得出 可以看出，目前访问报考研究生的相关信息的频 本站点的重频繁路径集H()以便利用LFP算 率是较高的，这样的知识是有意义的， 法计算事务数据库更新后的局部频繁(k十1)一路 为了测试算法LFP/GFP的性能，用Java语 径集； 言实现了LFP/GFP算法和现有的分布式挖掘算 (4)k=k+1,转第(1)步 法DMA算法[]，在不同支持度和不同数据库更 3实验结果与分析 新情况下，将GFP算法同DMA算法执行时间进 行比较，结果如图3所示，从中可以看出，在各种 利用4台PC构建采用DWLMS模型的分布 情况下，GFP算法求解频繁路径集所需执行时间 式Wb使用挖掘系统，节点配置为PV1.8G,256 比重新运行DMA算法求解频繁路径集所需执行 MB,运行平台Windows2000 Server,其中3台微 时间少得多，进而说明本文提出的分布式系统中 表2DWLS系统中局部频繁路径和全局频繁路径的实验结果(k=4,Support=0.25) Table 2 Results of local frequent paths and global frequent paths algorithms test 局部站点Site-1 局部站点Site-2 局部站点Site-3 全局站点Site-G 频繁路径 支持数 频繁路径 支持数 频繁路径 支持数 频繁路径 支持数 FPal 2665 FP4l 2108 FP4l 2386 FPal 7159 FP42 2218 FP42 1866 FP43 1905 FP3 2139 注：FPl→/ust ben/index.asp→/yjy/index.htm→/jr/index3.htm→/yjr/zss2005ml-htm; FP2→/ustben/index.asp→/yjr/index-htm→/yjr/index5.htm→/yjy/aj-htm: FP3-/ustben/index-asp/lib-ustb-edu-cn/index.htm/libed/netdb.htm/libcd/testdb.htm. 140000 70000r (a)支持度Support0.15 {b)支持度Support-=0.25 120000 60000 1000U0 DMA 50000 DMA 自 80000 40000 60000- 30000 GFP GFP 40000 20000 20000 10000 0 15 20 10 15 20 串务库更新率% 事务库更新率% 图3GFP算法与DMA算法执行效率比较 Fig-3 Comparison of efficiency between GFP algorithm with DMA algorithm
算法4 全局频繁路径集更新算法 GFP （1） 各局部站点根据局部频繁路径集更新算 法 LFP 的第 k 次循环迭代的过程计算事务数据 库更新后的局部频繁路径候选集 Ck（ i）及其支持 数并将其发送给全局站点；保存局部频繁路径集 L′k（ i）及其局部支持数； （2） 全局站点对所有局部频繁路径候选集 Ck（ i）进行合并计算其全局支持数扫描计算 sup′（ X）≥｜D′｜×minsup得到全局频繁 k—路径 集 FP k并将 FP k 发送到各局部站点； （3） 各局部站点将收到全局发来的 FP k 与本 站点的局部频繁路径候选集 L′k（ i）进行比较得出 本站点的重频繁路径集 H′k（ i）以便利用 LFP 算 法计算事务数据库更新后的局部频繁（ k＋1）—路 径集； （4） k＝k＋1转第（1）步． 3 实验结果与分析 利用4台 PC 构建采用 DWLMS 模型的分布 式 Web 使用挖掘系统节点配置为 PⅣ1∙8G256 MB运行平台 Windows2000Server．其中3台微 机存储分布式事务数据库并执行局部挖掘任务； 另一台微机执行全局挖掘算法任务．分布式软件 平台及 LFP／GFP 更新算法采用 J2EE 技术实现． 数据源为北京科技大学网站（www．ustb．edu．cn） 2周的访问日志日志数据量总共是145MB．将 其按时间分段并分布于3台微机中进行分布式 用户频繁访问路径挖掘算法 LFP／GFP 的运行结 果和性能测试．通过多次实验结果表明频繁路 径更新算法 LFP／GFP 的正确、有效性．例如当 全局4—频繁访问路径及其支持数、局部4—频繁路 径及其支持数的实验结果如表2．分析FP41路径 可以看出目前访问报考研究生的相关信息的频 率是较高的这样的知识是有意义的． 为了测试算法 LFP／GFP 的性能用 Java 语 言实现了 LFP／GFP 算法和现有的分布式挖掘算 法 DMA 算法［9］．在不同支持度和不同数据库更 新情况下将 GFP 算法同 DMA 算法执行时间进 行比较结果如图3所示．从中可以看出在各种 情况下GFP 算法求解频繁路径集所需执行时间 比重新运行 DMA 算法求解频繁路径集所需执行 时间少得多进而说明本文提出的分布式系统中 表2 DWLMS 系统中局部频繁路径和全局频繁路径的实验结果（ k＝4Support＝0∙25） Table2 Results of local frequent paths and global frequent paths algorithms test 局部站点 Site—1 局部站点 Site—2 局部站点 Site—3 全局站点 Site—G 频繁4—路径 支持数 频繁4—路径 支持数 频繁4—路径 支持数 频繁4—路径 支持数 FP41 2665 FP41 2108 FP41 2386 FP41 7159 FP42 2218 FP42 1866 FP43 1905 FP43 2139 注：FP41→／ustbcn／index．asp→／yjsy／index．htm→／yjsy／index3．htm→／yjsy／zsss2005ml．htm； FP42→／ustbcn／index．asp→／yjsy／index．htm→／yjsy／index5．htm→／yjsy／aj．htm； FP43→／ustbcn／index．asp→／lib．ustb．edu．cn／index．htm→／libcd／netdb．htm→／libcd／testdb．htm． 图3 GFP 算法与 DMA 算法执行效率比较 Fig．3 Comparison of efficiency between GFP algorithm with DMA algorithm ·900· 北 京 科 技 大 学 学 报 2006年第9期
Vol.28 No.9 张克君等：一种分布式Web使用模式挖掘模型及算法 .901. 频繁路径集的更新算法LFP/GFP算法具有较高 难 的效率，从理论上讲，局部更新算法LFP在求解 频繁路径集L()时，利用了前次挖掘过程中产 参考文献 生的频繁路径集Lk(i)和支持数sup:(X)及全局 [1]韩家炜，孟小峰，王静，等.Wb挖掘研究.计算机研究与 发展，2001,38(4)：405 第k一1次循环中产生的重频繁路径集H-1() [2]Srivastava J.Cooley R,Deshpande M,et al.Web usage min- 显然，GFP的优点是：(I)减少了数据库扫描的次 ing:discovery and application of usage patterns from Web da- 数：(2)减少了k次叠代产生的频繁路径候选集 ta.SIGKDD Explorations.2000.1(2):12 Ck(i)的大小，也就减少了频繁路径候选集生成的 [3]Chen M S,Park JS.Yu P S.Efficient data mining for path 执行时间；(3)由于频繁路径候选集C()数量的 traversal patterns.IEEE Trans Knowl Data Eng.1998.10 (2):209 减小，从而减少了局部站点向全局站点传输数据 [4]Nanopoulos A.Manolopoulos Y.Mining patterns from graph 量.因此GFP算法有较高的执行效率. traversals.Data Knowl Eng.2001,37:243 4 结论 [5]Kargupta H.Hamzaoglu I,Stafford B.Scalable distributed data mining using an agent based architecture Proc of 本文针对目前Wb频繁访问路径算法的缺 KDD97.Menlo Park:AAAI Press.1997:211 陷，对多镜像站点环境下的Wb分布式使用挖掘 [6]Kargupta H.Park B.Johnson E et al.Collective data mining from distributed vertically partitioned feature space/Work- 系统中频繁访问路径模式挖掘进行了研究，主要 shop on Distributed Data Mining.International Conference on 讨论了当局部站点访问日志量增加时的情况下， Knowledge Discovery and Data Mining.New York,1998 用户频繁访问路径如何高效更新的问题，提出了 [7]Masseglia F.Teisseire M,Poncelet P.Real time Web usage 一种多镜像站点环境下的Wh使用挖掘模型 mining with a distributed navigation analysisProceedings of DWLMS,以及基于DWLMS的局部频繁访问路 the 12th International Workshop on Research Issues in Data Engineering-San Jose.2002:169 径的更新算法LFP和全局频繁访问路径的更新 [8]吉根林，杨明，赵斌，等.基于DDMINER分布式数据库系 算法GFP,实验结果表明这些算法的正确性、高 统的颜繁项目集更新.计算机学报，2003,26(10)：1387 效性，能够有效解决多镜像站点环境引起的Wb [9]Cheung D W.Ng V T.Fu A W.Efficient mining of associa- 访问信息的异地存储、实时增长、分布式算法通讯 tion rules in distributed databases.IEEE Trans Knowl Data 量等因素给频繁访问路径模式发现过程带来的困 Eng1996,8(6):911 Construction and algorithms of distributed web usage pattern mining ZHA NG Kejun2),YANG Bingru2),ZHAO Geng),QU Wenlong2),LI Xin2) 1)Department of Computer Science and Technology Beijing Electronic Science and Technology Institute.Beijing 100070.China 2)Information Engineering School.University of Science and Technology Beijing.Beijing 100083.China ABSTRACT A distributed Web log mining system model(DWLMS)is presented.Based on the analysis on the procedure and algorithm of Web frequent access pattern mining,the more general incremental updat- ing algorithms of local frequent paths(LFP)and global frequent paths(GFP)in a distributed database sys- tem based on DWLMS are proposed for discovering the frequent access paths.Some troubles produced by real time incremental distributed Web access information and more communication data are solved better by the algorithms.The method was realized simply and tested with real world Web log information in labora- tory,and the results show that the algorithms are valid. KEY WORDS distributed data mining:Web access pattern mining:Web log mining;frequent path
频繁路径集的更新算法 LFP／GFP 算法具有较高 的效率．从理论上讲局部更新算法 LFP 在求解 频繁路径集 L′k（ i）时利用了前次挖掘过程中产 生的频繁路径集 Lk（ i）和支持数sup i（ X）及全局 第 k—1次循环中产生的重频繁路径集 H′k—1（ i）． 显然GFP 的优点是：（1）减少了数据库扫描的次 数；（2）减少了 k 次叠代产生的频繁路径候选集 Ck（ i）的大小也就减少了频繁路径候选集生成的 执行时间；（3）由于频繁路径候选集 Ck（ i）数量的 减小从而减少了局部站点向全局站点传输数据 量．因此 GFP 算法有较高的执行效率． 4 结论 本文针对目前 Web 频繁访问路径算法的缺 陷对多镜像站点环境下的 Web 分布式使用挖掘 系统中频繁访问路径模式挖掘进行了研究主要 讨论了当局部站点访问日志量增加时的情况下 用户频繁访问路径如何高效更新的问题．提出了 一种多镜像站点环境下的 Web 使用挖掘模型 DWLMS以及基于 DWLMS 的局部频繁访问路 径的更新算法 LFP 和全局频繁访问路径的更新 算法 GFP．实验结果表明这些算法的正确性、高 效性能够有效解决多镜像站点环境引起的 Web 访问信息的异地存储、实时增长、分布式算法通讯 量等因素给频繁访问路径模式发现过程带来的困 难． 参 考 文 献 ［1］ 韩家炜孟小峰王静等．Web 挖掘研究．计算机研究与 发展200138（4）：405 ［2］ Srivastava JCooley RDeshpande Met al．Web usage mining：discovery and application of usage patterns from Web data．SIGKDD Explorations20001（2）：12 ［3］ Chen M SPark J SYu P S．Efficient data mining for path traversal patterns．IEEE Trans Knowl Data Eng199810 （2）：209 ［4］ Nanopoulos AManolopoulos Y．Mining patterns from graph traversals．Data Knowl Eng200137：243 ［5］ Kargupta HHamzaoglu IStafford B．Scalable distributed data mining using an agent based architecture ∥ Proc of KDD97．Menlo Park：AAAI Press1997：211 ［6］ Kargupta HPark BJohnson E et al．Collective data mining from distributed vertically partitioned feature space ∥ Workshop on Distributed Data MiningInternational Conference on Knowledge Discovery and Data Mining．New York1998 ［7］ Masseglia FTeisseire MPoncelet P．Real time Web usage mining with a distributed navigation analysis ∥ Proceedings of the12th International Workshop on Research Issues in Data Engineering．San Jose2002：169 ［8］ 吉根林杨明赵斌等．基于 DDMINER 分布式数据库系 统的频繁项目集更新．计算机学报200326（10）：1387 ［9］ Cheung D WNg V TFu A W．Efficient mining of association rules in distributed databases．IEEE Trans Knowl Data Eng19968（6）：911 Construction and algorithms of distributed web usage pattern mining ZHA NG Kejun 12）Y A NG Bingru 2）ZHAO Geng 1）QU Wenlong 2）LI Xin 2） 1） Department of Computer Science and TechnologyBeijing Electronic Science and Technology InstituteBeijing100070China 2） Information Engineering SchoolUniversity of Science and Technology BeijingBeijing100083China ABSTRACT A distributed Web log mining system model （DWLMS） is presented．Based on the analysis on the procedure and algorithm of Web frequent access pattern miningthe more general incremental updating algorithms of local frequent paths （LFP） and global frequent paths （GFP） in a distributed database system based on DWLMS are proposed for discovering the frequent access paths．Some troubles produced by real time incremental distributed Web access information and more communication data are solved better by the algorithms．The method was realized simply and tested with real world Web log information in laboratoryand the results show that the algorithms are valid． KEY WORDS distributed data mining；Web access pattern mining；Web log mining；frequent path Vol．28No．9 张克君等： 一种分布式 Web 使用模式挖掘模型及算法 ·901·