《基于Web用户兴趣的聚类模型挖掘与分析.doc》由会员分享，可在线阅读，更多相关《基于Web用户兴趣的聚类模型挖掘与分析.doc（29页珍藏版）》请在三一文库上搜索。
1、基于Web用户兴趣的聚类模型挖掘与分析/.paper.edu -1- 基于Web用户兴趣的聚类模型挖掘与分析1 陈健荣 1，吕雪蕊 2 1 中山大学信息科学与技术学院，广东广州 （510275） 2 广东省潮州市龙湖医院，广东潮州 （521000） 摘 要：用户兴趣的评估因素有多方面，无论单独从哪个方面都无法得到完整的模型。本文综合考虑了三个核心因素，首先对用户浏览过的页面进行内容分析，并根据主题信息对页面进行聚类；在聚类的过程中除了考虑页面内容的相近程度外还辅以页面路径进行归类判断。在最后得到页面的兴趣簇时将用户的浏览行为对其兴趣的作用列入其中，从而得到综合的评估模型。实践表明此种方式能更准
2、确的反映用户的真实兴趣。 关键词：聚类模型，用户兴趣，Web数据挖掘，知识发现 中图分类号：TP311 文献标识码：A 1 引言 随着因特网越发深入人们的生活，准确的挖掘用户兴趣将变得非常有意义，它可以使得人们在浩瀚的网络中迅速的找到志同道合者进行交流，从而促进知识的传递。对用户兴趣特征的刻画有加权矢量、类型层次结构、加权语义网、书签和目录结构等模型1，而根据用户是否参加可分为显示与隐式两种。由于显示挖掘需要用户主动参与，这很大程度上降低了可用性，并同时带来系统噪音，为了保证挖掘结果的准确性以及提高用户接受度，一般采用隐式数据挖掘。 目前对用户兴趣的挖掘方式有多种，其中有基于浏览内容和行为相结
3、合的方式，如文献2，也有单纯从用户行为的历史信息寻找隐藏规律的。用户会话作为用户行为信息的基本单位，对其聚类是从行为历史中发现用户兴趣的基础工作，因而它自然而然成为重要的分析对象。而对用户会话分析主要采用的是相似性测量方法，基于相同浏览权值的相似性测量方法主要包括文献3-6所提出的4种，即Usage-based，Frequency-based，Viewing-Time-based以及Visiting-Order-based。其中VTB用的最广泛，同时这些方法均假设页面是不相关的而只比较不同会话在相同页面的浏览权值，不考虑页面之间的相似性。事实上，文献7中提到，即使不考虑页面的内容，单纯考虑页面
4、的路径也可以发现不同的页面之间存在相似性。 本文并不单纯从一个方面来分析用户的兴趣，而是综合多种方式、从多角度来建立用户的兴趣模型。首先将用户所访问的页面进行内容挖掘从而得到用矢量方法表示的页面兴趣，在此基础上结合页面URL相似性对页面距离的贡献对页面进行聚类；接着，根据聚类结果考虑用户作用在页面上的行为提取出突出特征从而形成用户兴趣。 2 用户兴趣挖掘方式 2.1 兴趣界定 在分析用户兴趣之前，我们首先对用户兴趣进行界定，即用户由什么组成、影响因素有哪些。一般地，用户对Web文档的访问是有目的的行为，这种行为的动机可以分为稳定兴趣和偶然兴趣。稳定兴趣是指一个人具有持久的兴趣倾向，偶然兴趣是指
5、一个人由于临时需要或其他原因对某事物产生的偶然兴趣，每个人的偶然兴趣可以认为是随机变化的。但在日志 陈健荣（1983-），男，硕士研究生，主要研究方向为数据库与知识库，工作流平台。 /.paper.edu -2- 中用户的兴趣具有集中性，这说明用户由稳定兴趣驱动访问Web的频率远远高于偶然兴趣的驱动，因此一定时间段的Web访问日志中一定蕴含了用户的稳定兴趣。可以这么认为，用户的兴趣由其浏览过的大量页面的兴趣综合而成。其中“页面兴趣”定义如下： 设有页面共有N个主题，所有主题都用数字权值来表示其突出程度，越突出的主题其权值越大，其中第i个主题的权值用 iC 来表示。设所有主题的权值之和为m，权值
6、Ci按从大到小排列，即 1 2 iC C C L ，若0( ) / 80%kiiC m= ，那么主题1k为突出主题，我们称这前k个主题为该页面的兴趣。 我们可根据同样的原理来表示用户的兴趣，文献8便是采用此种方式。 2.2 兴趣挖掘流程 Web 挖掘过程一般包括相关网页采集、文本预处理、文本模型表示、信息或文本特征性抽取、文本分类(聚类)或结果集的数据挖掘等步骤以得到结果从而极大程度的方便用户有效地浏览和获取信息9。 本文提出的用户兴趣挖掘中最核心的步骤是对页面兴趣的挖掘，其大致过程如下：首先捕获用户访问的 URL 并对 URL 进行预处理，主要是去除视频、音频以及无效链接，然后根据“干净”的
7、 URL 提取对应的页面文本，接着对文本中的关键主题进行分析得到页面的兴趣。其流程图如图 1 所示： 图 1 页面兴趣挖掘流程 用户的兴趣在页面兴趣挖掘的基础上综合其他信息进行分析，其中主要考虑了页面路径的相似性、用户在页面上的浏览时间以及点击次数，我们用图 2 的流程来表示： 图2 用户兴趣挖掘流程 3 用户兴趣模型分析 3.1 Web内容挖掘 (一) 页面主题表示 研究页面的主题表示方式目的在于能用形式化的方式来表示页面兴趣，进而计算页面间的距离并最终为挖掘用户兴趣服务。但是 Web 页面不像关系数据库那样具有严格的数据结构，同时具有数值的表示和计算能力。Web 页面多半是半结构化甚至是无
8、结构的文本，/.paper.edu -3- 要对它进行计算首先必须将它的特征进行结构化并赋予数字表示的中间形式，目前比较流行的是矢量空间法。 在矢量空间法中，Web 页面被表示成由词组成的矢量，即形如 L<技术，财经， ，人文>的格式，但在做这个转化之前必须将 Web 文本进行分词。分词并非本文讨论的重点，我们暂且不做分析。为了从文本矢量中体现出页面的主题并可进行计算，我们必须根据关键字的重要程度赋予数字的表示形式，因而最终的矢量形式实际是<技术（10），财经（8），人文（1）>，在矢量表示时我们按其权值从大到小进行排列。 在得到了特征向量的特征项之后，一般要运用词频统
9、计方法来计算特征项的权重。在计算权重上被广泛应用的公式是IF-IDF公式10： ( ) ( ) log( / )i i iW d tf d N n= （1） 其中： ( )itf d itf 为词条 it ，在文档d中的出现频率；N为所有文档的数目， in 为含有词条 it 的文档数目。 在计算得每个页面的矢量之后，我们往往并不保留所有的关键字，因为这样一个页面的矢量可能是冗长的，并且很多关键字出现的次数是很小的，他们对页面兴趣的影响可以忽略，因此在实际操作中我们一般保留权值和为80的前N个关键字来表示页面的兴趣，也即在“2.1兴趣界定”所提到的方法。 在获得某用户浏览过的大量页面矢量表示后，
10、我们便可在此基础上通过再进一步的分析来得到此用户的兴趣，这个方法可大致表示如下（其中Wi表示对页面赋予的另一权值，它主要与用户对此页面的浏览行为相关）： 12nWWW> > ? ? ? ? ? ? ? ?LLLML<体育(10)，文学(7)， ，财经(3)<技术(15)，历史(12)， ，人文(5) <技术(18)，财经(12)， ，人文(10)><政治(13)，生活(10)， ，校园(6)> （2） (二) 页面相似度评价 在分析了页面的矢量表示方式之后我们开始研究页面之间的相似度，也称为页面距离。计算页面之间距离的目的在于对页面继续聚类，因为
11、聚类分析是基于相似性的。下面我们介绍常用的两种相似性度量函数，它们分别是夹角余弦法和欧几里德距离： 1) 夹角余弦法 12 21 1( )( , ) cos( , )nxk ykkn nxk ykk kW WSim X Y X YW W= = = （3） 其中X、Y表示两个页面的矢量，Sim（X，Y）表示X向量和Y向量之间的夹角余弦，Wxk表示X页面的第K各分量的权值，Wyk表示Y页面的第K各分量的权值。 2) 欧几里德距离 2 21 1( , ) ( , ) | | | |x y xn ynSim X Y d X Y W W W W? ?= = + +L （4） 其中 d（X，Y）表示 X、
12、Y 向量之间的欧几里德距离，Wxk 以及 Wyk 的意义同公式（3）一致。 以上两个公式的计算都是针对长度相同并且关键字一一对应的向量，但在实际情况中/.paper.edu -4- 页面的主题数往往是不一样的，项与项之间也不对应，例如页面 X 的兴趣是<体育（5）>，而 Y 页面的兴趣是<音乐（6），计算机（4）>,我们不能简单的认为 Wx1 为 5，Wy1 为 6，Wy2 为 4，因为“体育”与“音乐”之间不具可比性，而“计算机”又找不到对应项。这种情况我们必须对矢量进行扩展，其规则是：移项对齐、补全空缺项。例子中 X 页面的矢量扩展后变成<体育（5），补全（0
13、），补全（0）>，Y 页面矢量扩展后变成<补全（0），音乐（6），计算机（4）>，扩展便可以利用公式（3）、（4）进行距离计算了。 (三) 兴趣聚类 聚类就是将一组对象集合按照相似性归成若干类别，其目的是使属于同一类别的对象之间相似度最大，而不同类别的对象间的相似度最小，是一种典型的无监督的机器学习问题。聚类分析的算法主要有11平面划分方法(Partitioning method)、层次聚类方法(hierarchical method)、基于密度的方法(density-based method)、基于网格的方法(grid-based method)和基于模型的方法(model
14、-based method)。 层次聚类方法就是对给定的数据对象集合进行层次分解，他可分为凝聚的和分裂的。凝聚的方法就是一开始将每个对象作为单独的一个组，然后相继合并相近的对象和组，直到所有的组合并为一个，或者达到一个终止条件为止。而与之相反，分裂的方法一开始将所有对象置于一个簇中，在迭代的每一步中，一个簇分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者达到了某个终止条件。 下面给出一个面向 Web 文本的凝聚的层次聚类法的具体描述12，在描述算法之前我们首先对“聚类中心”进行定义，因为它在层次聚类法中是一个核心的概念和步骤。定义一组Web 页面的矢量为 Sp，则聚类中心 Z 表示如下：
15、 1| |p P pSZ PS = （5） 则对于给定的文档集合 D=D1，D2，Dn)，凝聚的具体过程如下： 1) 将D 中的每个文档看作是一个具有单个成员的簇：Ci=Di，这些簇构成了D的一个聚类CD1，D2，Dn)。 2) 计算C中每对簇(Ci，Cj)之间的相似度Sim(Ci，Cj)。 3) 选取具有最大相似度的簇max Sim(Ci，Cj)，并将Ci、Cj合并为一个新的簇 k i jC C C= U ，从而构成了D 的一个新的聚类C=C1，C2，Cn-1。 4) 计算Ck的聚类中心，并重复上述过程，直到C中剩下一个簇，或满足了特定条件为止。 在进行页面聚类的过程可同时考虑用户聚类，因为
16、两者存在着必然的关系。用户兴趣聚类的基础是越相关的页面，访问它们的用户的兴趣越相似，越不相关的页面，访问它们的用户的兴趣越不相似；反之，页面相关聚类的基础是兴趣越相似的用户访问的页面越相关。兴趣越不相似的用户访问的页面越不相关。可见，页面的相关聚类聚的越好，用户兴趣聚类也就越好；反之亦然。也就是说：用户的兴趣聚类和页面的相关聚类是一个基本循环。用户兴趣聚类直接依赖于页面相关聚类。页面相关聚类则直接依赖于用户兴趣聚类。这种循环关系意味着用户的兴趣聚类与页面的相关聚类是一对对偶问题。由对偶定理呵知：若原问题有解，则其对偶问题亦有解，反之亦然。所以把二种聚类结合起来考虑比分开考虑明智。 /.pape
17、r.edu -5- 3.2 浏览行为分析 研究表明，用户的浏览行为在一定程度上反映了用户的兴趣，例如当用户对某个页面比较感兴趣时他会在页面上停留更多时间，或者会多次访问该页面，同时他拉动滚动条次数也明显增加，有些用户还会收藏该页面或进行编辑等13。但在用户的多种行为中，最明显的体现为浏览时间以及对页面滚动条的点击次数，因此文献2采用多元线性回归模型来评估用户行为与对页面的感兴趣程度的关系，其回归方程表示： L aX bY c= + + （6） 其中 L 表示用户对页面的兴趣度；X 表示浏览时间，一般用秒计算；Y 表示对该页面滚动条的点击次数或翻页次数；a、b、c 都是常量，它根据不同的站点相应
18、不同。在分析该校图书馆 Web 日志时，其采用的参数分别是 0.1300、0.1017 以及 64.0492，在对页面首先进行人工分类的情况下与实验数据进行对比，结果表明此种方式是有效的。 3.3 访问路径分析 (一) 分析前提 每个网站都有它的页面文件层次结构，URL 便反映了这个结构。开发者在构建系统时往往根据内容类别将相近或同一主题的网页组织在同一文件夹中，这种上下级结构便体现了网站设计者对内容的归类。因此，一般相同目录下的页面内容具有较强的相似性，而不同目录下页面相关度较弱。有了这个前提，我们在页面聚类时可以把页面路径考虑进去，而不仅仅是基于主题关键字的比较。 (二) 计算方法 假设有
19、两个页面路径分别是 X 和 Y，它们所体现出来的目录级数分别 Nx 和 Ny，其中相同的目录级数为 Nxy，那么这两个页面路径的相似度表示为： ( , )1min( , )xy x y xyx y xyx ySim X YX YN N N NX YN N NN N=?+ + ?， （7） 从上式可以看出，当 X 和 Y 路径完全一致时，它们的相似度为 1；当它们不完全一样，其相似度由相同目录级数（公式的前半部分）以及不同目录级数（公式的后半部分，它必须乘以一个系数）共同来决定。其中系数 用于调节前后两部分的权重，并且 (0,1 。 显然，页面级数越长说明分类越细，越是在底层相同目录下的页面其相
20、似度越大。为了使 能体现这一特性，我们首先对页面路径所体现出来的目录赋予权值，并将第 k 级的权值记为 Wk，各级的权值的基本原则是：越在顶层的目录其权值越小，越在底层的目录其权值越大，权值的大小便标识着页面相似度的大小。这样， 的值便可以进行如下定义（其中 m 表示相同的目录级数，n 表示路径的总级数）： 1 1/m nk kk kW W= = （8） 从 的计算公式可看出，即使页面路径 X、Y 完全不相同，也就是 xyN 0= 时，x y x ySim(X,Y)=min(N ,N )/(N +N ) 0.5 ，换句话说，即使 1，X、Y 的相似度也不会超过0.5。 有了以上的计算公式之后，
21、我们得到计算两个页面路径的步骤如下： 1) 首 先 将 URL 地 址 按 “/” 进 行 截 分 ， 例 如 页 面 地 址 为/.paper.edu -6- /news.1634/07/0120/09/1GU.html 的 URL 将被截分为（news.163，07，0120，09，1GU.html）； 2) 从头到尾逐个比较目录名，直到找到第一不相同； 3) 计算相同目录的级数以及总级数； 4) 利用公式（7）计算两个页面路径的相似度。 4 实例分析 通过编号为 0001 用户浏览过的页面记录挖掘该用户的兴趣来验证本文论述的模型。这个过程涉及两个核心表结构，其中表 2 的主键 URL 是
22、表 1 的外键。每次用户浏览一个页面时，它的 URL 将被同时记录入表 2 和表 1。在服务器对数据进行分析前，只有 UserID 以及URL 字段有数据写入（IsHandle 默认值为 False），其它字段都没有数据。系统固定在每天凌晨 0 点对数据进行分析。下表只显示部分数据。 表 1 用户与 URL 对应表 UserID URL MeanViewTime MeanClickCount IsHandle 0001 /news.sina/c/ 2007-01-26/213312150457.shtml35 8 True 0001 /news.sina/c/ 2007-01-26/23001
23、2150522.shtml26 4 True 0001 /news.sina/c/ 2007-01-26/232112150526.shtml25 6 False 备注：UserID用户编号，URL页面路径，MeanViewTime该用户对该页面的平均浏览时间，MeanClickCount该用户浏览该页面时的评价点击次数，IsHandle表示当前 URL 是否分析过，默认为False，当对当前 URL 进行分析后其值被改为 True，分析结构被写入表 2 对应 URL 的后三字段。 表 2 URL 信息表 URL URLSlices Interests Weights /news.sina/c
24、/ 2007-01-26/213312150457.shtml （news.sina，c，2007-01-26，213312150457.shtml） （失踪，员工，石油，新闻） （0.35，0.27，0.12，0.08） /news.sina/c/ 2007-01-26/230012150522.shtml （news.sina，c，2007-01-26，230012150522.shtml） （人口，规模，形势，新闻） （0.45，0.18，0.15，0.08） /news.sina/c/ 2007-01-26/232112150526.shtml NULL NULL NULL 备注：UR
25、L页面路径，URLSlices根据“/”将 URL 进行截断，Interest页面兴趣，表示为一组词的组合，Weights各个兴趣的权值，与 Interests 字段一一对应。 用户 0001 浏览过的页面数为 458 个，选取页面相似度为 0.6 作为临界条件对页面进行聚类，聚类后得到表示该用户稳定兴趣的页面 389 个，再按照权值前 80的规则提取这些页面的共同主题，最终得到该用户的兴趣为“新闻，形势，中国，政府”，根据人工对页面URL 对应页面的分析，其结果与系统得出的结论较为接近。 /.paper.edu -7- 5 结论与展望 用户的稳定兴趣由其长期的的行为以及操作对象所反映，而在
26、Web 上用户的行为反映为对感兴趣页面的相关操作，其操作的对象反映为其所关注的页面内容。本文综合的考虑了多方面因素，在页面聚类层次采用内容与路径相结合的方法，在用户兴趣挖掘层次采用页面聚类结果与行为相结合的方法，从而建立了一个相对完全的模型。该模型实际是让用户隐式的对页面打分，并反过来折射出用户的兴趣，分析表明该模型能较真实的反映用户的兴趣。但此模型中涉及到一些相关参数仍可以进一步优化，其最好的方式是用智能算法来进行训练，如何选择算法来改进该模型将是重要的后续工作。 参考文献 1. Wu Y H,Chen Y C,Chen A L P. Enabling Personalized Recomm
27、endation on the Web Based on User Interests and BehaviorsJ In:Proceedings of the 11th International Workshop on Research Issues in Data Engineering. Los Alamitos,CA:IEEE CS Press,2001:17-24 2. 赵银春,付关友,朱征宇.基于 Web 浏览内容和行为相结合的用户兴趣挖掘.计算机工程. 2005(31):93-794 3. Xiao Jitian, Zhang Yanehun. Clustering of We
28、b users using session-based similarity measuresC.Proceedings of the 2001 International Conference on Computer Net-works and Mobile Computing(ICCNMCO1)Washington,DC,IEEE Computer Society,2001:223-228 4. Xiao Jitian,Zhang Yanchun,Jia Xiaohua,et alMeasuring similarity of interests for clustering Web us
29、ersC.Proceedings of the 12th Australian Database Conference 2001(ADC2001) Washington,DC:IEEE Computer Society,2001:107-114 5. Claypool M, Le Phong,Waseda Makoto，et al. Implicit interest indicatorsC.Proceedings of the ACM Intelligent User Interfaces Conference(IUI)New York:ACM Press.2001:14-17 6. Cla
30、ypool M,Brown D,Le P，et al.Inferring user interestJIEEE Internet Computing, 2001,5(6):32-39 7. Wang Weinan，Zaiane O RClustering Web sessions by sequence alignmentC. Proceedings of the 13th International Workshop on Database and Expert Systems Applieations (DEXA02)Washington,DC:IEEE Computer Society,
31、2002：3be achieved if only one factor is considered. This paper take the three important factors into consider. First it analyzes the contents of the pages navigated, and according to the topics it clusters those pages. During the period it not only takes the contents into account but also uses the U
32、RL to help the estimation. At last, the users behaviors on pages are included for they reflect something of the interests, such that, a compositive model appears. Experiments showed that this model can reflect the users real interests better. Keywords: Clustering Model, Users Interests, Web Data Mining, Knowledge Discovery