基于 Web 的用户访问模式挖掘研究1.doc

《基于 Web 的用户访问模式挖掘研究1.doc》由会员分享，可在线阅读，更多相关《基于 Web 的用户访问模式挖掘研究1.doc（6页珍藏版）》请在三一办公上搜索。

1、精品论文基于 Web 的用户访问模式挖掘研究1包剑 辽宁工程技术大学计算机系，辽宁阜新 (123000) E-mail: baojian9999摘要：WWW 包含了丰富的信息资源，Web 挖掘可快速有效地获取所需要的信息。Web访问模式挖掘是通过处理 Web 使用数据，以发现用户的访问模式，理解用户的行为。通过 采用优化的矩阵聚类算法对用户群体和页面进行聚类，能够更准确的反映网站的访问情况。关键词Web 挖掘；Web 内容挖掘；矩阵聚类中图分类号: TP.391文献标识码:A0. 引言随着 WWW 的飞速发展，因特网己成为一个巨大的、分布广泛的和全球性的信息服务 中心，其中蕴涵着具有巨大潜在价

2、值的知识，提供各种信息。然而网站的结构越来越复杂， 用户获取信息与提高网络浏览速度却无法得到相应的提高，如何有效得分析用户的需求，帮 助用户从因特网的信息海洋中发现他们感兴趣的信息和资源，己经成为一项迫切而重要的课 题。为此，可将传统的数据挖掘技术与 Web 技术相结合，进行 Web 挖掘。根据用户在浏览 站点时的行为，将挖掘出的用户访问模式应用于网站上，可以改善 Web 站点，提高站点的 服务质量，使网站能够根据用户的行为模式，改良自身的组织结构和表现形式，即所谓自适 应 Web 站点。这将极大的方便用户的使用。1. Web 挖掘Web 挖掘是一门综合性学科，涉及数据挖掘、机器学习、模式识别

3、、人工智能、统计 学、计算机语言学、计算机网络技术、信息学等多个领域。Web 挖掘是指从大量非结构化、 异构的 Web 信息资源中发现有效的、新颖的、潜在可用的及最终可理解的知识（包括概念、 模式、规则、规律、约束及可视化等形式）的过程1。Web 数据形式多样，没有特定的模型来描述，且缺乏机器所能理解的语义，使得有些 数据挖掘技术并不适用于 Web 挖掘，因此 Web 挖掘需要用到更多的有别于传统数据挖掘的 技术，以提高信息检索的精度和效率，改善检索结果的组织。Web 挖掘一般可分为 Web 内 容挖掘、Web 结构挖掘和 Web 访问模式挖掘。Web 挖掘对象分为资源发现和信息获取。资 源发

4、现就是定位文本的位置，并自动生成文档的索引。Web 上的资源一般分为两类：文档 和服务。目前 Web 的资源发现主要集中于 Web 内容挖掘。文本挖掘是指将数据挖掘技术应 用在大量的文本集合上，发现其中隐含的知识的过程。大多数基于数据库的数据挖掘方法均 可作用于文本挖掘，如数据归纳、分类、聚类、关联规则挖掘等。Web 文本挖掘的结果既 可以是对某个文本内容的概括，也可以是对整个文本集合的分类结果或聚类结果等2。Web 访问模式挖掘是通过处理 Web 使用数据，以发现用户的访问模式，理解用户的行为。用户 访问模式的挖掘过程就是通过数据挖掘技术从 Web 使用数据中自动抽取访问模式的过程。1本课题

5、得到辽宁省教育厅高等学校科学研究项目（202182054）的资助。- 6 -2. Web 日志挖掘Web 日志挖掘是通过处理 Web 使用数据，发现用户的访问模式，理解用户的行为。用 户访问模式挖掘的过程就是通过数据挖掘技术从 Web 使用数据中自动抽取访问模式的过 程。Web 日志挖掘过程划分为三个阶段，即数据准备阶段、用户访问模式挖掘算法实施阶 段和模式应用阶段（站点调整阶段）3。2.1 数据准备数据准备阶段可由 Web 数据源和数据预处理两个阶段组成。2.1.1Web 数据源Web 信息异常丰富，但并不能直接作为 Web 数据挖掘的对象，需要对 Web 信息抽象出 合适的数据模型。在 W

6、eb 日志挖掘中，Web 使用数据可以从服务器端、客户端、代理服务 器端或是应用所需的数据库中进行采集。2.1.2 数据预处理在 Web 日志挖掘中，主要分析的数据源是服务器日志，但是由于服务器日志记录的数 据并不完整，直接在其上进行挖掘非常困难。对日志进行预处理的结果直接影响到挖掘算法 产生的规则与模式，因此预处理过程是 Web 日志挖掘质量保证的关键。预处理阶段的输入是原始日志文件，输出是用户会话文件。主要包括以下步骤：（1） 数据转换：将原始日志文件导入数据库中。（2）数据清理：删除与日志分析目的无关的记 录。（3）用户识别：将用户和请求的页面相关联。（4）会话识别：将用户在一段时间内的

7、 请求页面分解成能反映实际浏览习惯的用户会话。（5）路径补充：将本地或者代理服务器 中缓存而没有被日志记录的请求页面增加到会话中。3. Web 用户访问模式挖掘对于 Web 站点来说，其拓扑结构是已知的。尽管不同用户在不同的时期可能会有不同 的浏览模式，但其长期趋势应该是稳定的。因此，通过挖掘一定时期内用户的访问信息，便 可发现该站点的相似用户群体以及相关的页面信息。一个 Web 站点的拓扑结构就是一幅有向图，而用户在一段时间内的访问模式则为其子 图。从原始日志数据中导出最大向前引用序列 MFP4。这个过程实际上就是在构造用户的访 问子图。另外，用户的浏览行为就蕴含在站点的拓扑结构中，即为它的

8、一个子图。具有相似 访问子图的用户显然为需求相似的用户，也就是用户群体聚类。因此，不需要再去重新构造 网站的拓扑结构，从服务器日志文件中就能获知网站的结构，因为浏览数据本身就反映了这 种结构。因此直接对 Web 站点的拓扑结构和用户浏览信息进行处理。3.1 Web 用户访问挖掘算法本文应用矩阵聚类的算法，并对其进行改进，处理起来比较简单，而且具有广泛性5。 它对日志文件的要求不高，不需要对进行会话识别和事务识别，也不需要复杂的数据结构， 因此较为方便。对原始的 Log 数据进行预处理后，以 L=的形式表示 Web 服务器日志。 其中，UserID 表示 Web 用户 ID，IP 表示用户的 I

9、P 地址，url 表示用户请求的 url，time 表示相应的浏览时间。然后，对其做进一步处理，以反映用户在某一段时间内的浏览行为。3.1.1 基本定义定义 1：用户浏览行为 A：记录用户浏览该网站时留下的信息，它是具有如式 3.1 形式的 2 (n+1)元组：A =（3.1）其中，l A L ， l A _ ip = IPA ，l A _ useid = UserIDA ，n1，hits 表示到目前为止用户UserIDA 浏览页面 l A _ useid 的次数。定义 2：Web 站点的模型 G：Web 站点的拓扑结构可以看成是有向图，如式 3.2 所示：G =（3.2）其中，N 为结点集；

10、N P= Node N , (UID, hits )n ，n1，记录用户 UID 及其访问结点 Node 的次数，为结点属性集；E 为有向边集； EP= (e E, Number ofpathp )m ，p，m1，为有向边属性集，记录有向边及其所在路径的编号。定义 3：urlID-UserID 关联矩阵 M m n ：根据有向图 G 的定义，从 G 的结点集 N 中可以 得到该站点的所有 url，从相应的结点属性集 N P 中可以获得访问每一个结点的 UserID 及相应的访问权值，由此以 urlID 为行，以 UserID 为列，以访问次数 hits 为访问权值，可以建立 urlID-Use

11、rID 关联矩阵 M m n ，如式 3.3 所示： h1,1 h2 ,1h1, 2h2 ,2Lh1, jLh2, jLh1,n hL2,n MM m n = MMMMM （3.3） hi ,1hi , 2Lhi , jLhi ,m MMMMMM hm,1hm, 2Lhm, jLhm,n其中，hi , j 是页面 i 在一段时间区域内被用户 j 访问的次数，即用户 j 在一段时间区域内访问 i 页面的次数；每一列向量 M , j表示用户 j 对该网站中所有页面的访问情况；每一行 向量 M i,表示所有用户对页面 i 的访问情况。因此，可以认为，行向量反映了用户类型，描述了用户的个性化访问子图；

12、而列向量即代表了站点的结构，又蕴含有用户共同的访问模式。那么，分别度量行向量和列向量的相似性，就能直接得到相似用户群体和相关 Web 页 面，也实现了对页面及用户的聚类。定义 4：权值关联矩阵 Am n ：由关联矩阵 M m n 演变而来的，如式 3.4 所示的矩阵形式： a1,1 a2 ,1a1,2a2 ,2La1, jLa2, jLa1,n aL2,n MAmn = MMMMM （3.4） ai ,1ai , 2Lai , jLai ,m MMMMMM am,1am, 2Lam, jLam,ni , j i , j10其中 a 为权代表值，a= hi, j = 0hi, j i ，ai ,

13、 j =0，表示用户 j 没有访问页面 i；ai , j =1，2hi, j i表示用户 j 对页面 i 的内容感兴趣； ai , j =2，表示用户 j 对页面 i 的内容非常感兴趣； i 是权值闽值(闽值根据聚类情况的不同而定)。定义 5 ： 相似度 sim( pi , p j ) ：设 pi 和p j 均是 n 维空 间上的 两个向量 ，且 pi = (ai1 ,L, aik ,L, aim ) ， p j = (a j1 ,L, a jk ,L, a jm ) ，lkn，那么向量 pi 和 p j 的相似度sim( pi , p j ) 如式 3.5 所示：Sim( pi , p j)

14、 = cos(pi , p j ) =pi p jn(aik a jk )= k =1 （3.5）pi p jn2(aik )k =1n2(a jk )k =1其中， pi p j 表示两个向量的数量积， pi和 p j分别是向量的 pi 和 p j 的模。3.1.2 算法描述urlID-UserID 关联矩阵 M m n 的行向量 M i,描述了所有用户对各个网页的访问情况。可以认为：对于所有用户访问情况相同或相似的网页，一定具有某些相似性，因此可将它们聚为一类。n聚类时，首先计算 urlID-UserID 关联矩阵 M m n 每行的权值阀值 i = M m n hi , j / nj =

15、1（取整函数），然后对 M m n 进行预处理，根据定义 4，对于任意 hij i ，可令 aij =2，对于任意 i hij 0，可令 aij =1，对于任意 hij = 0，可令 aij = 0，由此生成权值矩阵 Am n 。m ni , jm m然后根据定义 5，计算权值矩阵 A中行向量间的相似度 s，生成相似矩阵 ASim 。在对称矩阵SimSimAm m ，任意的 si , j Amm (1im，ijm)表示第 i 个行向量和第 j 个行向量间的相似度，其对角线元素值是 1。由于相似矩阵的对称性，只需考虑它的倒三角部分（不包括对角m m线）。然后再根据式（3.6）计算相似矩阵 ASi

16、m相似阀值 。m mSim = si, ji=1 j=1（矩阵 Amm 中非零的个数）（3.6）1 Ls1, jLs1,m MMMM Sim相似矩阵 Amm = 1 si ,m MM 1 输入：预处理后的日志数据库 Webdatabase输出：聚类结果 Clu由 Webdatabase 生成关联矩阵材 M m n ；计算 M m n 的行关联阀值 i （或列关联阀值）：for（i=0；im；i+=1）for（(j=0；j i ）ai,j =2;if( i hi,j 0)ai,j =1;/生成权值矩阵 Am nfor (i=0;im;i+=1) for(j=0;jn;j+=1) 求各行之间的相似

17、度；（或求各列之间的相似度）/生成相似矩阵 ASim （或 ASim ）求相似阀值 :for (i=0;im;i+=1) for(j=0;j )mmnn将页面 i 与页面 j 聚为一类；（或将用户 i 与用户 j 聚为一类）/完成聚类操作3.2 实验结果在 WindowsNT 平台下，用 Java 语言实现了本算法，并对算法的准确性进行了验证。将 本文算法和最大向前引用算法（MF 算法）进行了准确性实验。在一定的阈值控制下挖掘出 相同数量的浏览偏爱路径和频繁访问路径，与已知的网站经验兴趣路径比较，显示该算法具 有一定的优势。用三元组 Interest(URL.time,URL.size,URL

18、.num)表示页面兴趣度，构造以引用 网页 URL 为行、浏览网页 URL 为列，页面的平均兴趣度为元素值的网站访问矩阵。算法本身对服务器日志的预处理要求低，只需要简单的数据清洗。实验表明能准确地反 映用户浏览兴趣，而且系统可扩展性也较好由于将用户访问页面的次数、页面的平均访问时 间、页面的大小综合考虑，从而得到偏爱路径。因此算法准确度高。还可将用户的浏览偏爱 引入时间参考度量，在通过某种选择进入到下一个页面后，浏览的时间越长，说明用户越有 兴趣，越偏爱于访问，而浏览时间越短则相反。另外还考虑在 Web 日志预处理时加上用户 识别，来发现某类或某个用户的浏览偏爱路径。聚类算法可以准确地反映用户

19、浏览兴趣，在不给用户增加额外负担的前提下，具有简单高效的优点，而且系统可扩展性也较好。还可以在 Web 日志预处理时加上用户识别，来发现某类或某个用户的浏览偏爱路径，进行个性化 网站设计。4. 结语WWW 具有丰富的资源，由于 Web 数据的特点，使得 Web 数据挖掘成为数据挖掘技术 中的难点。Web 数据挖掘应该着重在 Web 挖掘的内在机制的研究及其实现；Web 知识库的 动态维护、更新；半结构、结构的文本数据、图形图像数据、多媒体数据的高效挖掘算法； Web 挖掘算法在海量数据挖掘时的适应性和时效性以及专门用于知识发现的数据挖掘语言 及其标准化和关联规则和序列模式在构造自组织站点的研究

20、等方面6。参考文献1 Chakrabarti S, Dom B E,Kumar S R,et al. Mining the Webs Link Structure. Computer,1999, 32（8）: 60-672 Z. Huang. Extensions to the k-means algorithm for clustering large data sets with categorical values J. DataMining and Knowledge Discovery, vol. 2, 1998: 283-304.3 D. S. W. Ngu and X. Wu.

21、Site Helper: A localized agent that helps incremental exploration of the World WideWeb. In 6th International exploration of the World Wide Web conference, Santa Clara, CA 1997.4 Joachims, T., Freitag, D. &Mitchell, T. Web Watcher: A Tour Guide for the World Wide Web.Proceedings of the15 Internationa

22、l Joint Conference on Artificial Intelligence IJCAI-97.5 邢东山,沈钧毅.一种新的基于协作过滤的用户浏览预测模型J.情报学报,2004,1(23):16-19.6 邹涛,王继成,朱华宇等.WWW 上的信息挖掘技术及实现J.计算机研究与发展,1999, 36（8）: 1019-1024The Study of Mining Technology Based on WebBao JianDepartment of Computer Science & Technology, Liaoning Technical University, Fux

23、in (123000)AbstractWWW contains rich information resources; Web mining can obtain the needed information effectively.According to the XML generated backgrounds and characteristics, make Web mining models and the method of data draw out the based on XML, detailing specific Web mining realize process. And discussed the value of Web mining and importance of Web development.Keywords：Web mining; Web Content Mining; matrix clustering