当前位置:文档之家› 基于Web用户兴趣的聚类模型挖掘与分析

基于Web用户兴趣的聚类模型挖掘与分析

基于Web用户兴趣的聚类模型挖掘与分析1陈健荣1,吕雪蕊21 中山大学信息科学与技术学院,广东广州(510275)2 广东省潮州市龙湖医院,广东潮州(521000)E-mail:jrcken@摘要:用户兴趣的评估因素有多方面,无论单独从哪个方面都无法得到完整的模型。

本文综合考虑了三个核心因素,首先对用户浏览过的页面进行内容分析,并根据主题信息对页面进行聚类;在聚类的过程中除了考虑页面内容的相近程度外还辅以页面路径进行归类判断。

在最后得到页面的兴趣簇时将用户的浏览行为对其兴趣的作用列入其中,从而得到综合的评估模型。

实践表明此种方式能更准确的反映用户的真实兴趣。

关键词:聚类模型,用户兴趣,Web数据挖掘,知识发现中图分类号:TP311 文献标识码:A1引言随着因特网越发深入人们的生活,准确的挖掘用户兴趣将变得非常有意义,它可以使得人们在浩瀚的网络中迅速的找到志同道合者进行交流,从而促进知识的传递。

对用户兴趣特征的刻画有加权矢量、类型层次结构、加权语义网、书签和目录结构等模型[1],而根据用户是否参加可分为显示与隐式两种。

由于显示挖掘需要用户主动参与,这很大程度上降低了可用性,并同时带来系统噪音,为了保证挖掘结果的准确性以及提高用户接受度,一般采用隐式数据挖掘。

目前对用户兴趣的挖掘方式有多种,其中有基于浏览内容和行为相结合的方式,如文献[2],也有单纯从用户行为的历史信息寻找隐藏规律的。

用户会话作为用户行为信息的基本单位,对其聚类是从行为历史中发现用户兴趣的基础工作,因而它自然而然成为重要的分析对象。

而对用户会话分析主要采用的是相似性测量方法,基于相同浏览权值的相似性测量方法主要包括文献[3-6]所提出的4种,即Usage-based,Frequency-based,Viewing-Time-based以及Visiting-Order-based。

其中VTB用的最广泛,同时这些方法均假设页面是不相关的而只比较不同会话在相同页面的浏览权值,不考虑页面之间的相似性。

事实上,文献[7]中提到,即使不考虑页面的内容,单纯考虑页面的路径也可以发现不同的页面之间存在相似性。

本文并不单纯从一个方面来分析用户的兴趣,而是综合多种方式、从多角度来建立用户的兴趣模型。

首先将用户所访问的页面进行内容挖掘从而得到用矢量方法表示的页面兴趣,在此基础上结合页面URL相似性对页面距离的贡献对页面进行聚类;接着,根据聚类结果考虑用户作用在页面上的行为提取出突出特征从而形成用户兴趣。

2用户兴趣挖掘方式2.1兴趣界定在分析用户兴趣之前,我们首先对用户兴趣进行界定,即用户由什么组成、影响因素有哪些。

一般地,用户对Web文档的访问是有目的的行为,这种行为的动机可以分为稳定兴趣和偶然兴趣。

稳定兴趣是指一个人具有持久的兴趣倾向,偶然兴趣是指一个人由于临时需要或其他原因对某事物产生的偶然兴趣,每个人的偶然兴趣可以认为是随机变化的。

但在日志陈健荣(1983-),男,硕士研究生,主要研究方向为数据库与知识库,工作流平台。

中用户的兴趣具有集中性,这说明用户由稳定兴趣驱动访问Web 的频率远远高于偶然兴趣的驱动,因此一定时间段的Web 访问日志中一定蕴含了用户的稳定兴趣。

可以这么认为,用户的兴趣由其浏览过的大量页面的兴趣综合而成。

其中“页面兴趣”定义如下:设有页面共有N 个主题,所有主题都用数字权值来表示其突出程度,越突出的主题其权值越大,其中第i 个主题的权值用i C 来表示。

设所有主题的权值之和为m ,权值Ci 按从大到小排列,即12i C C C ≥≥L ,若0()/80%k i i C m =≥∑,那么主题1~k 为突出主题,我们称这前k 个主题为该页面的兴趣。

我们可根据同样的原理来表示用户的兴趣,文献[8]便是采用此种方式。

2.2 兴趣挖掘流程Web 挖掘过程一般包括相关网页采集、文本预处理、文本模型表示、信息或文本特征性抽取、文本分类(聚类)或结果集的数据挖掘等步骤以得到结果从而极大程度的方便用户有效地浏览和获取信息[9]。

本文提出的用户兴趣挖掘中最核心的步骤是对页面兴趣的挖掘,其大致过程如下:首先捕获用户访问的URL 并对URL 进行预处理,主要是去除视频、音频以及无效链接,然后根据“干净”的URL 提取对应的页面文本,接着对文本中的关键主题进行分析得到页面的兴趣。

其流程图如图1所示:图1 页面兴趣挖掘流程用户的兴趣在页面兴趣挖掘的基础上综合其他信息进行分析,其中主要考虑了页面路径的相似性、用户在页面上的浏览时间以及点击次数,我们用图2的流程来表示:图2 用户兴趣挖掘流程3 用户兴趣模型分析3.1 Web 内容挖掘(一) 页面主题表示研究页面的主题表示方式目的在于能用形式化的方式来表示页面兴趣,进而计算页面间的距离并最终为挖掘用户兴趣服务。

但是Web 页面不像关系数据库那样具有严格的数据结构,同时具有数值的表示和计算能力。

Web 页面多半是半结构化甚至是无结构的文本,要对它进行计算首先必须将它的特征进行结构化并赋予数字表示的中间形式,目前比较流行的是矢量空间法。

在矢量空间法中,Web 页面被表示成由词组成的矢量,即形如L <技术,财经,,人文>的格式,但在做这个转化之前必须将Web 文本进行分词。

分词并非本文讨论的重点,我们暂且不做分析。

为了从文本矢量中体现出页面的主题并可进行计算,我们必须根据关键字的重要程度赋予数字的表示形式,因而最终的矢量形式实际是<技术(10),财经(8),…,人文(1)>,在矢量表示时我们按其权值从大到小进行排列。

在得到了特征向量的特征项之后,一般要运用词频统计方法来计算特征项的权重。

在计算权重上被广泛应用的公式是IF-IDF 公式[10]:()()log(/)i i i W d tf d N n =× (1) 其中:()i tf d i tf 为词条i t ,在文档d 中的出现频率;N 为所有文档的数目,i n 为含有词条i t 的文档数目。

在计算得每个页面的矢量之后,我们往往并不保留所有的关键字,因为这样一个页面的矢量可能是冗长的,并且很多关键字出现的次数是很小的,他们对页面兴趣的影响可以忽略,因此在实际操作中我们一般保留权值和为80%的前N 个关键字来表示页面的兴趣,也即在“2.1兴趣界定”所提到的方法。

在获得某用户浏览过的大量页面矢量表示后,我们便可在此基础上通过再进一步的分析来得到此用户的兴趣,这个方法可大致表示如下(其中W i 表示对页面赋予的另一权值,它主要与用户对此页面的浏览行为相关):12n W W W >×>×⇒×⎧⎫⎪⎪⎪⎪⎨⎬⎪⎪⎪⎪⎩⎭L L L M L <体育(10),文学(7),,财经(3)<技术(15),历史(12),,人文(5)<技术(18),财经(12),,人文(10)><政治(13),生活(10),,校园(6)> (2) (二) 页面相似度评价在分析了页面的矢量表示方式之后我们开始研究页面之间的相似度,也称为页面距离。

计算页面之间距离的目的在于对页面继续聚类,因为聚类分析是基于相似性的。

下面我们介绍常用的两种相似性度量函数,它们分别是夹角余弦法和欧几里德距离:1) 夹角余弦法()(,)cos(,)nxk yk W W Sim X Y X Y ×==∑ (3) 其中X 、Y 表示两个页面的矢量,Sim (X ,Y )表示X 向量和Y 向量之间的夹角余弦,Wxk表示X 页面的第K 各分量的权值,Wyk 表示Y 页面的第K 各分量的权值。

2) 欧几里德距离(,)(,)Sim X Y d X Y == (4) 其中d (X ,Y )表示X 、Y 向量之间的欧几里德距离,W xk 以及W yk 的意义同公式(3)一致。

以上两个公式的计算都是针对长度相同并且关键字一一对应的向量,但在实际情况中页面的主题数往往是不一样的,项与项之间也不对应,例如页面X 的兴趣是<体育(5)>,而Y 页面的兴趣是<音乐(6),计算机(4)>,我们不能简单的认为Wx1为5,Wy1为6,Wy2为4,因为“体育”与“音乐”之间不具可比性,而“计算机”又找不到对应项。

这种情况我们必须对矢量进行扩展,其规则是:移项对齐、补全空缺项。

例子中X 页面的矢量扩展后变成<体育(5),补全(0),补全(0)>,Y 页面矢量扩展后变成<补全(0),音乐(6),计算机(4)>,扩展便可以利用公式(3)、(4)进行距离计算了。

(三) 兴趣聚类聚类就是将一组对象集合按照相似性归成若干类别,其目的是使属于同一类别的对象之间相似度最大,而不同类别的对象间的相似度最小,是一种典型的无监督的机器学习问题。

聚类分析的算法主要有[11]平面划分方法(Partitioning method)、层次聚类方法(hierarchical method)、基于密度的方法(density-based method)、基于网格的方法(grid-based method)和基于模型的方法(model-based method)。

层次聚类方法就是对给定的数据对象集合进行层次分解,他可分为凝聚的和分裂的。

凝聚的方法就是一开始将每个对象作为单独的一个组,然后相继合并相近的对象和组,直到所有的组合并为一个,或者达到一个终止条件为止。

而与之相反,分裂的方法一开始将所有对象置于一个簇中,在迭代的每一步中,一个簇分裂为更小的簇,直到最终每个对象在单独的一个簇中,或者达到了某个终止条件。

下面给出一个面向Web 文本的凝聚的层次聚类法的具体描述[12],在描述算法之前我们首先对“聚类中心”进行定义,因为它在层次聚类法中是一个核心的概念和步骤。

定义一组Web 页面的矢量为Sp ,则聚类中心Z 表示如下:1||p P p S Z P S ∈=∑ (5)则对于给定的文档集合D={D1,D2,…,Dn),凝聚的具体过程如下:1) 将D 中的每个文档看作是一个具有单个成员的簇:C i ={D i },这些簇构成了D 的一个聚类C ={D 1,D 2,…,D n )。

2) 计算C 中每对簇(C i ,C j )之间的相似度Sim(C i ,C j )。

3) 选取具有最大相似度的簇max Sim(C i ,C j ),并将C i 、C j 合并为一个新的簇k i j C C C =U ,从而构成了D 的一个新的聚类C={C 1,C 2,…,C n-1}。

4) 计算C k 的聚类中心,并重复上述过程,直到C 中剩下一个簇,或满足了特定条件为止。

在进行页面聚类的过程可同时考虑用户聚类,因为两者存在着必然的关系。

相关主题