基于粗糙K—均值用户兴趣的聚类算法

摘要：该文通过对虚拟社区用浏览模式，回复模式的分析和研究，来实现对用户兴趣的聚类，，同时实现对虚拟社区核心用户的挖掘。

关键词：虚拟社区；核心用户；用户兴趣

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2013）15-3537-05

在WEB社区的挖掘中，用户兴趣的获取对于了解用户的需求和用户的特点特别重要。在博客，论坛等这些虚拟的社区中，都是以兴趣作为导向而组织起来的松散的社区结构。在这些论坛和博客中都提供了发帖，回帖，看帖的功能，有不同的主题。每天有大量的新帖，信息更新的速度很快。大部分的用户只浏览或者回复自己感兴趣的主题或者版面。这种以信息为中心，兴趣为导向的模式，在虚拟的社区中具有了小世界特性[1-2]。在虚拟的社区中，用户浏览了哪些主题，对主题是是否有回复，如果没有回复，那么在该主题上停留时间的长短都反映了用户的兴趣模式。文献[3]对用户兴趣模式的挖掘只关注了用户对主题的回复，以及用户之间的相互回复。但是在论坛中，80%的用户只是对主题的浏览而不进行回复。文献[42]根据用户浏览或者回复的主题之间的关系，来寻找用户间的兴趣。

本文通过对虚拟社区用浏览模式，回复模式的分析和研究，来实现对用户兴趣的聚类。通过分析用户浏览的主题网页，在主题网页的浏览的时间，是否有回复来获得用户的兴趣度。将用户的兴趣模式刻画成为一个模糊的语言变量，如“low/middle/high”，这样既可以表征用户兴趣的高低，又忽略了时间，回复次数的细微的差别。通过兴趣度的高低，实现对用户的聚类，同时实现对虚拟社区核心用户的挖掘。然而在WEB社区用户聚类的巨聚类过程中，类和类之间可能不存在明确而清晰的边界，因此在论文中把每个类用粗糙集来表示。提出了基于粗糙K-均值的用户兴趣度的用户聚类方法。

1 用户兴趣模式的预处理

Web服务器的日志文件中包含了大量的用户访问信息，这些信息是用户行为的体现了用户的兴趣和爱好。在论文中只对用户浏览的主题以及在主题上浏览的时间，以及对该主题的回复感兴趣。通过处理后，保留用户的信息形式[{（Ti1，ti1，Ri），（Ti2，ti2，Ri），……}]，[Ti1]表示用户参与的的主题，[ti1]表示用户在该主题下的访问时间，[Ri]表示用户是否在该主题下的回复的数目。假定一个论坛社区中，用户参与的主题的集合可以表示为[{T1，T2……Tm}]，不考虑用户的对主题的访问次序，则第[i]个用户的兴趣度可以表示为如下形式。

显然，每个用户的兴趣模式都被转换成[m]维的向量。将用户的兴趣度聚类成[r]个模糊区间，每个模糊区间对应一个模糊语言的变量。每个模糊语言的变量的隶属度函数可以通过模拟的方法来获得。假如兴趣度隶属度函数如图1所示。

2 用户和用户之间兴趣模式的关联关系

通过扩展后，用户的兴趣度模式向量[EVi]是一个[m+n]维向量，向量中的每个数都是从0到1之间的数。

3 粗糙k-均值聚类扩展模糊用户浏览模式

k-均值聚类算法是聚类算法中比较通用和常用的算法。然而在WEB社区用户聚类过程中，类和类之间可能不存在明确而清晰的边界，因此在论文中把每个类用粗糙集来表示。

设所有的用户的浏览模式要被聚类成[c]个类，第[k]个类的中心的计算公式如下：

具体的算法的步骤如下：

2） 随机选定[c]个模式作为[c]个类的中心

4） 重新计算[k]个类的中心点

5） 重复步骤3和步骤4，直到收敛。

6） 按照粗糙集输出这k个类

算法采用两阶段反复循环的过程，直到没有新的数据元素被分配到类中。算法实现将每一个用户的兴趣度模式分配到某个聚类中，使得它与这个聚类中心的距离比到其它聚类中心的距离要近；然后重新修改聚类中心。

4 实验结果与评价

本文以天涯论坛数据作为验证用户兴趣聚类的源数据来源，为了分析该算法的可行性，从论坛的WEB日志中选取2400条记录，经过数据的预处理，识别出会话的主题有7个。具体的数据如下：

假定根据用户的兴趣度，将用户的兴趣度分成3个模糊的区域，模糊区域的划分根据专家系统给出。如图2所示：

通过每个用户的兴趣度模式矩阵，根据公式3计算出用户之间的相似度[rij]。根据公式（4）（5）（6）（7），最后使用欧氏距离来衡量用户之间的差异性矩阵如下：

5 实验分析

5.1 数据采集

社区数据的采集主要包括两个主要的步骤：

1）通过网络爬虫获得帖子的列表网页，网页中提取出论坛主题的标题。

2）根据第一步获得的论坛主题的URL，分别每个主题的浏览的用户列表，回复列表，每个用户浏览的时间。

作者在2012年8月29号，分别对天涯论坛进行抓取。提取出3782个论坛主题，经过分析后，对其中的2078个主题进行分析，组成了2078个XML文件组成的文集，用户数目为1580个。2012年8月1号，又对天涯论坛的帖子进行抓取，提取出6453个主题，经过分析后，对其中5897个主题进行分析，组成了5897个主题，用户数目4896个。

5.2 数据预处理

本实验中对数据的预处理方法采用第二章提出的数据预处理的方法，得到最终符合实验要求的，无噪声的实验数据。

5.3 实验结果比较

将本文算法和文献[4]做比较，结果如下：

从上表可以看出，当样本数据不大的时候，该文算法和文献[4]的DB值差异不大，但是随着数据样本的增大，该文算法的优越性就体现出来了。

6 结论

WEB在线社区中，用户之间的之间的聚类由于海量的数据以及海量的数据及很多不确定因素的存在，使得用户之间的聚类成为一个极具挑战性的工作，正是由于不确定性因素的存在，使得用户和用户之间不可能清楚的边界，粗糙变量被用来代表一个边界模糊的类。这样类和类之间存在交叉是符合现实的规律的。通过使用粗糙模糊变量来实现基于用户兴趣度的聚类，可以准确的发现用户之间的相似性，这种方法可以实现挖掘用户之间的兴趣的挖掘和聚类，从而根据用户之间的兴趣来做出个性化的推荐。

参考文献：

[1] MIGRAM S.The samll-world problem[J].Psychology Today，1967，1（1）：60-67.

[2] WATTS D J，STROGATZ S H.Collective dynamics of small world networks [J].Nature，1998，393（6684）：440-442.

[3] 孟聪，黄永峰.应励志基于认知度的用户好友社团关系挖掘方法[J].计算机应用研究，2012（8）.

[4] 陈海强，程学旗.基于用户兴趣的寻找虚拟社区核心成员的方法[J].中文信息学报，2009（2）：89-92.