英语原文共 34 页，剩余内容已隐藏，支付完成后下载完整资料
采用位置编码的先序链接WAP-Tree挖掘网络日志顺序模式
CI EZEIFE cezeife@uwindsor.CA;（HTTP：//www.cs.uwindsor.ca / cezeife）伊璐
温莎大学计算机科学学院，加拿大安大略省温莎市，N9B 3P4
编辑：Fayyad
2002年7月收到; 2004年6月修订
摘要. 顺序挖掘是一个为了发现存在于有序事件表中的相关关系，将数据挖掘技术应用于顺序数据库的过程。顺序挖掘技术的一个重要应用是Web使用挖掘，用于挖掘Web日志访问，这些访问是通过一个服务器记录的不同的Web使用者在一段时间内的网页访问序列。WAP-tree挖掘是一个对Web日志访问序列的顺序模式挖掘技术，（WAP-tree挖掘）首先将原始的web访问序列数据库存储在一个前缀树上，类似于存储非顺序数据的频繁模式树。WAP-tree算法通过递归的重构中间树从WAP-tree中挖掘频繁序列，以后缀序列开始，以前缀序列结束。
这篇论文提出了一个使用WAP-tree挖掘频繁序列的更有效的方法，这个方法完全消除了在挖掘过程中大量重构WAP-tree中间树的需要。提出来的算法以先序方式建立原始WAP-tree的频繁头结点链接，使用每个结点的位置码辨认树的结点之间的祖先、后代关系。然后，它通过渐进的前缀序列搜索，从第一个前缀子序列事件开始寻找每个频繁顺序模式。实验展示了在WAP-tree技术之上的巨大的性能收益。
关键词：顺序模式，Web使用挖掘，WAP-tree挖掘，先序链接，位置码，先验技术
1.介绍
关联规则挖掘是一种发现数据之间强烈的关联或者相关关系的数据挖掘技术。给定一个事务集（类似于上下文中的数据库记录），每个事物都包含许多项目（属性），关联规则是这么定义的：X-gt;Y的形式，X,Y都在项目集中且交集为空。这个规则的支持度定义为：包含X,Y并集的事务的百分比，它的置信度是包含在Y中的项目的X事务集的百分比。在关联规则挖掘中，所有支持度比给定最小支持度高的项目被称为大或者频繁项目集。如果项目集X包含i个项目，就称它为i-项目集。Agrawal and Srikant (1994)呈现了关联规则挖掘的概念和一个简单规则的例子：80%购买牛奶和面包的顾客也会购买鸡蛋。
表1.含有项的数据库事务表示例
表1展示了一个可以被挖掘的数据库事务表的例子。这个表格中有一组项目I={a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p}，这些项目可以代表零售店的项目例如面包，黄油，奶酪，鸡蛋，牛奶，糖或者可以代表网页如果感兴趣的领域是web挖掘。使用这个简单起见只有五个事务的数据库，项目集“a,f,c”的支持度是3或者60%，因为这个项目集只在五个事务中的三个（100,200,500）出现。因此，如果用户给定的确定频繁项目集的最小支持度是60%或者更低，那个项目集“a,f,c”就是一个频繁项目集。然而，如果最小支持度是70%，那个“a,f,c”就不是频繁项目集，因为它的支持度比最小支持度阈值低。规则a,f-gt;c（可以从频繁项目集“a,f,c”中产生）的置信度是100%，因为三个事务都包含先行项目“a,f”也包含后继项目“c”。
因为发现所有这样的规则可以帮助市场投资，跨销售分析，做决定和商业管理，所以在这个研究领域的算法被提出（Agrawal and Srikant, 1994; Park et al., 1997; Mannila et al., 1995; Han and Kamber,2000）。这些算法主要关注如何从一组非顺序的项目中有效的产生频繁模式以及如何从产生的频繁模式中发现最有趣的规则。
虽然传统的关联规则挖掘发现了事物内部模式，但是顺序模式挖掘发现了事务间模式，以在按时间排序的事务序列中检测一组项目的存在。在基础的关联规则挖掘中，在一个事务中出现的项目没有顺序，但是在顺序模式挖掘中，项目之间存在顺序，一个项目可能以相同的序列再次出现。一个顺序模式的例子：在出租录像店中，80%的顾客会先租“星球大战”，再租“帝国反击战”，再租“绝地归来”。在关联规则挖掘中使用的计算频繁项目集的支持度和置信度的测量也适用于顺序模式挖掘中确定频繁序列和从频繁序列中产生的强规则。
Web使用挖掘用来自动发现web服务器中的用户访问模式。有趣的用户访问模式可以从web服务器上记录的web访问日志中提取出来。这些访问数据的分析可以为服务器性能的增强，重建网站，电子销售中的直接销售提供有用的信息。(Etzioni, 1996). Madria et al. (1999), Borges and Leven (1999), and Srivastava et al. (2000),都提出将web挖掘基于挖掘web信息的部分分成三个领域：web内容挖掘，web结构挖掘和web使用挖掘。web内容挖掘要求从网页上的真实数据发现有用的信息，例如设计用来传递给使用者的网页上的数据。这通常包含多种类型的数据，例如文本，图片，音频，视频，元数据和超链接。Web内容数据包括自由文本，半结构化数据（例如HTML文件）和更多结构化数据（例如表格中的数据和HTML、XML页面中生成的数据库）。Web结构挖掘发现基于web的链接结构的模型。这个模型基于超链接的拓扑结构，具有或不具有链接的描述。这个模型可以用来对网页分类，产生相似的信息和不同网站之间的关系。Web结构挖掘可以用于发现为特定学科组织的权威站点和基于学科链接到其他相关网站。不仅如此，它还可以用来发现指向许多权威的相关特殊学科的枢纽。Web使用挖掘通过观察web冲浪会话或行为产生有意义的数据。例如，可能发现：90%的访问网址 /products/product.html的客户端也会访问页面/contact/contact.html。这个信息揭示了这两个页面有着紧密的关联并且可以组织在一起给使用者提供一个更简单的浏览路线。在每个web服务器上的使用者的行为都可以从web日志中提取。一个关于在web日志中的一行数据的例子如下格式：
host/ip user [date:time] “request url” status bytes
137.207.76.120–[30/Aug/2001:12:03:24-0500]“GET/jdk1.3/docs/relnotes/deprecatedlist.
html HTTP/1.0” 200 2781
这条被记录的信息从左到右代表：电脑访问网页的host ip地址（137.207.76.120），用户识别号码（-）（这个破折号代表匿名），访问时间（12:03:24 p.m. on Aug 30, 2001 at a location 5 hours behind Greenwich Mean Time (GMT)），请求（GET/jdk1.3/docs/relnotes/
deprecatedlist.html）（其他请求类型是POST和得到http头信息的HEAD）被访问的网页的URL（HTTP/1.0），请求状态（200系列是成功，300系列是重定向，400系列是失败，500系列是服务器错误），被请求的数据的字节数（2781）。尽管大多数项目都从常用日志中提取信息，但是常用日志不能百分百反映每个使用者的浏览行为。缓存的页面视图不会被记录在服务器日志中，通过POST方法传递的信息在服务器日志中也不可用。因此，为了获得恰当的web使用数据源，需要一些额外的技术，例如数据包嗅探器和cookie。在大多数案例中，研究员假设用户web浏览的信息被完全记录在web服务器日志中，该日志被预处理以获得用于挖掘序列的事务数据库。
使用Apriori算法(Agrawal and Srikant, 1994)的基本关联规则发现可以将单个用户会话中经常被访问的页面关联起来。因此，存在或者不存在这样的规则可以帮助web设计者重构他们的网站。用于web使用挖掘中的关联规则方法与用于传统数据库或者数据仓库的关联规则方法大致相同。通过使用顺序模式挖掘，web市场销售员可以预测未来访问模式，这对针对确定使用人群投放广告是有帮助的。例如，从雅虎的主页面开始，使用者可以定位加拿大大学的信息通过下列顺序：Home → Education →Higher Education→
Colleges and Universities → By Region → Countries → Canada or Home → Regional → Countries → Canada → Education → Higher Education。因此，想要吸引学生的大学可以在沿途发任何页面上放置他们的广告。顺序模式技术对发现频繁web访问模式是有用的，且已经被用在了以下最近的工作中(Spiliopoulou,1999; Berendt and Spiliopoulou, 2000; Nanopoulos and Manolopoulos, 2000)。
一个web日志是一组事件（或项目）的序列，每个事件都由两个属性值——用户身份，访问信息。信息可以是以前提供的原始web日志格式的值的组合。例如，这里的访问信息代表访问内容。简单起见，web日志访问内容被表示为项目集{a,b,c,d,e,f}。例如，部分web日志如下所示以lt;User ID，访问内容gt;的格式：
lt;100, agt;lt;100, bgt;lt;200, egt;lt;200, agt;lt;300, bgt;lt;200, egt;lt;100, dgt;lt;200,bgt;lt;400,agt;lt;400, f gt; lt;100, agt;lt;400, bgt;lt;300, agt;lt;100, cgt;lt;200, cgt;lt;400, agt;lt;200, agt;lt;300, bgt;lt;200, cgt; lt;300, f gt;lt;400, cgt;lt;400, f gt;lt;400, cgt;lt;300, agt;lt;300, egt;lt;300, cgt;。
这些web日志时间被预处理，以便将他们分组成不同的用户ID访问序列并且以事务数据库的形式创建web访问序列。事务数据库形式中的web日志序列从经过预处理的web日志中获得。这个序列的每个元组都包含一个事务ID和这个事务的web访问的序列。因此，例如，下面给出的web日志中的用户ID100有访问内容，a,b,d,a,c。从给定的web日志数据中得到的事务web访问序列如表2所示。从web日志中挖掘顺序模式的问题现在基于表2的数据库。给定一个事件集E，访问序列S可以用e1e2hellip;en表示，ei属于E。
表2 简单的web访问序列数据库
这意味着访问序列可以由一系列事件组成，这些事件都是事件集E的成员。在一个访问序列S中，i不等于j时，ei不等于ej不是必须的，这意味着在一个序列中重复的事件是可以的。例如，在表2中，E = {a, b, c, d, e, f }，一个序列S是abdac。一个访问序列的长度|S|是在序列中的事件的数量，一个长度为m的访问序列被称为m-序列。例如，abdac是一个5-序列。Web访问序列数据库（WASD）是S1, S2, . . . , Sm的集合，Si是访问序列。|WASD|也用来描述数据库中访问序列的数量。例如，上面的web数据库是一个在数据库中有4个访问序列：abdac,eaebcac, babfaec and babfaec的WASD。访问序列Srsquo;=e1rsquo;e2rsquo;hellip;elrsquo;被称为序列S=e1e2hellip;en的子序列，S是Srsquo;的超序列，记为S lsquo;sube; S当且仅当对于Srsquo;中的每个事件ejrsquo;，在S中都存在相同的事件ek，在S中发生的事件的顺序也应该遵循在Srsquo;中事件的顺序。例如，S = ab, S = babcd，我们可以说Srsquo;是S的一个子序列。我们也可以说ac是S的一个子序列，虽然S中有b在ac之间。一个频繁模式是一个在挖掘过程中发现的访问序列，并且它应该有一个高于最小支持度的支持度。在访问序列S = e1e2 . . . ekek 1 . . . en中，如果子序列Ssuffix = ek 1 . . . en是模式P = e1lsquo;e2rsquo; . . . elrsquo;的一个超序列，其中ek 1 = e1rsquo;, Sprefix = e1e2 . . . ek被称作S关于模式P的前缀，Ssuffix是Sprefix的后缀序列。例如，在序列eaebcac中，eae是bcac的一个前缀，bcac是eae的后缀。在WASD中模式S的支持度被定义为包含子序列S的序列Si的数目除以数据库WASD中事务的数目。虽然事件在一个访问序列中可以重复，但是一个模式从一个访问序列中最多只能得到一个支持计数的贡献。例如，表2中，fc是一个从用户id300和400中得到50%支持度的模式，分成在用户ID为400的序列中出现了两次，但是只有一个可以贡献fc的支持计数。与关联规则挖掘类似，顺序模式挖掘的最小支持度是有用户设置的确定频繁序列的0-1之间的百分比值。web使用挖掘的问题是找到所有支持度高于lambda;的所有模式，给定web访问序列数据库WASD和最小支持度阈值lambda;。
从web日志中挖掘顺序模式的技术分为Apriori和非Apriori。类Apriori算法连续的产生许多条件模式集合，尤其当顺序模式很长的时候(Agrawal and
全文共30925字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[15384]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
