基于在线百科全书的群体兴趣及其关联性挖掘

第３４卷第ｌ１期　２０１１年１１月　计　算　机　学　报　Ｖｏ１．３４　Ｎｏ．１１　ＮＯＶ．２Ｏ１１　ＣＨＩＮＥＳＥ　ＪＯＵＲＮＡＬ　ＯＦ　ＣＯＭＰＵＴＥＲＳ　基于在线百科全书的群体兴趣及其关联性挖掘　张海粟”　陈桂生　马于涛”“　刘玉超　”（中国人民解放军理工大学指挥自动化学院（中国人民解放军国防信息学院（武汉大学软件工程国家重点实验室武汉武汉南京２１０００７）　４３００１０）　４３００７２）　０　（中国电子系统工程研究所　北京　１００１４１）　摘要针对协同过滤、基于内容过滤等个性化推荐方法所存在的用户隐私数据收集、冷启动等问题，提出一种群　体兴趣及其关联性的挖掘方法，并应用于推荐领域．以维基百科作为数据源，获取用户社团及其编辑的词条，设计　了以词条及其所属类别为基础的泛树结构生长策略，使用泛树结构表征用户社团所对应的兴趣点．结合用户社团　的结构特征和兴趣点的语义特征给出了用户社团对兴趣点的关注度及兴趣点间关联性的定义，用此群体兴趣取代　个性化推荐方法中的个体兴趣，进行了人工直观评价、测试集对比以及视频点播中的新闻推荐等三种实验．结果表　明，测试集上群体兴趣关联性的准确度达到了５Ｏ　，高于基准协同推荐方法的准确度；新闻推荐实验中，本方法比　按热度推荐方法获得了高出近一倍的点击率，验证了群体兴趣及其关联性的合理性．　关键词　群体兴趣；兴趣点泛树结构；协同推荐；维基百科；社会网挖掘　中图法分类号ＴＰ３９１　ＤＯＩ号：１０．３７２４／ＳＰ．Ｊ．１０１６．２０１１．０２２３４　Ｇｒｏｕｐ　Ｉｎｔｅｒｅｓｔｓ　ａｎｄ　Ｔｈｅｉｒ　Ｃｏｒｒｅｌａｔｉｏｎｓ　Ｍｉｎｉｎｇ　Ｂａｓｅｄ　ｏｎ　Ｗｉｋｉｐｅｄｉａ　ＺＨＡＮＧ　Ｈａｉ～Ｓｕ　’　ＣＨＥＮ　Ｇｕｉ—Ｓｈｅｎｇ。　ＭＡ　Ｙｕ—Ｔａｏ。　，　ＬＩＵ　Ｙｕ—Ｃｈａｏ。　’（Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ａｕｔｏｍａｔｉｃ　Ｃｏｍｍａｎｄｉｎｇ，ＰＬＡ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ．Ｎａｎｊｉｎｇ　２１０００７）　（Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｎａｔｉｏｎａｌ　Ｄｅｆｅｎｓｅ　Ｉｎ　ｆｏｒｍａｔｉｏｎ，Ｗｕｈａｎ　４３００１０）　。　（Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｅｌｅｃｔｒｏｎｉｃ　Ｓｙｓｔｅｍ　Ｅｑｕｉｐｍｅｎｔ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｂｅｉｊｉｎｇ　１００１４１）　”（Ｓｔａｔｅ　Ｋｅｙ　Ｌａｂｏｒａｔｏｒｙ　ｏｆ　Ｓｏｆｔｗａｒｅ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｗｕｈａｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｗｕｈａｎ　４３００７２）　Ａｂｓｔｒａｃｔ　Ｐｅｒｓｏｎａｌｉｚｅｄ　ｒｅｃｏｍｍｅｎｄａｔｉｏｎ　ｔｅｃｈｎｏｌｏｇｉｅｓ，ｓｕｃｈ　ａｓ　ｃｏｌｌａｂｏｒａｔｉｖｅ　ｆｉｌｔｅｒｉｎｇ　ａｎｄ　ｃｏｎｔｅｎｔ　ｂａｓｅｄ　ｆｉｌｔｅｒｉｎｇ，ｆａｃｅ　ｓｏｍｅ　ｐｒｏｂｌｅｍｓ．Ｔｈｅ　ｏｂｖｉｏｕｓ　ｏｎｅｓ　ａｒｅ　ｔｈｅ　ｐｒｉｖａｃｙ　ｈｉｓｔｏｒｙ　ｄａｔａ　ｃｏｌｌｅｃｔｉｏｎ　ａｎｄ　ｃｏｌｄ　ｓｔａｒｔ．Ｉｎ　ｔｈｉｓ　ｐａｐｅｒ，ｗｅ　ｓｕｇｇｅｓｔ　ａ　ｇｒｏｕｐ　ｉｎｔｅｒｅｓｔｓ　ｍｉｎｉｎｇ　ｍｅｔｈｏｄ　ｆｒｏｍ　Ｗｉｋｉｐｅｄｉａ．Ｗｅ　ａｌｓｏ　ａｐｐｌｙ　ｔｈｅ　ｇｒｏｕｐ　ｉｎｔｅｒｅｓｔｓ　ｉｎｔｏ　ｔｈｅ　ｒｅｃｏｍｍｅｎｄａｔｉｏｎ　ｓｙｓｔｅｍ，ｗｈｉｃｈ　ａｖｏｉｄ　ｔｈｅ　ｃｏｌｄ　ｓｔａｒｔ，ａｎｄ　ｄｏｎ’ｔ　ｎｅｅｄ　ａｎｙ　ｐｒｉｖａｃｙ　ｄａｔａ．Ｈｅｒｅ，ｔｈｅ　ｇｒｏｕｐ　ｉｎｔｅｒｅｓｔ　ｒｅｐｌａｃｅｓ　ｔｈｅ　ｐｅｒｓｏｎａｌｉｚｅｄ　ｉｎｔｅｒｅｓｔ　ｉｎ　ｔｈｅ　ｔｒａｄｉｔｉｏｎ—　ａｌ　ｐｅｒｓｏｎａｌｉｚｅｄ　ｒｅｃｏｍｍｅｎｄａｔｉｏｎ　ｔｅｃｈｎｏｌｏｇｉｅｓ．Ｉｎ　ｄｅｔａｉｌ，ｗｅ　ｆｉｒｓｔ　ｓｕｇｇｅｓｔ　ａ　ｇｅｎｅｒａｌ　ｔｒｅｅ　ｓｔｒｕｃｔｕｒｅ　ａｎｄ　ａ　ｇｒｏｗｉｎｇ　ｓｔｒａｔｅｇｙ　ｔｏ　ｄｅｎｏｔｅ　ｔｈｅ　ｉｎｔｅｒｅｓｔ　ｏｆ　ａ　ｕｓｅｒｓ　ｇｒｏｕｐ，ｗｈｉｃｈ　ｉｎｃｌｕｄｅｓ　ｔｈｅ　ｓｅｍａｎｔｉｃ　ｒｅｌａ—　ｔｉｏｎｓｈｉｐ　ｏｆ　ｅａｃｈ　ｉｎｔｅｒｅｓｔ．Ｔｈｅｎ　ｗｅ　ｄｅｆｉｎｅ　ｔｈｅ　ｇｒｏｕｐ　ｉｎｔｅｒｅｓｔ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｓｔｒｕｃｔｕｒｅ　ｏｆ　ｕｓｅｒｓ　ｇｒｏｕｐｓ．Ａｔ　ｌａｓｔ，ｗｅ　ｍｅａｓｕｒｅ　ｔｈｅ　ｃｏｒｒｅｌａｔｉｏｎｓ　ｏｆ　ｉｎｔｅｒｅｓｔｓ　ａｃｃｏｒｄｉｎｇ　ｔｏ　ｔｈｅ　ｇｅｎｅｒａ１　ｔｒｅｅ　ｓｔｒｕｃｔｕｒｅ　ｏｆ　ｉｎｔｅｒｅｓｔｓ．Ｗｅ　ｆｕｒｔｈｅｒ　ｄｅｓｉｇｎ　ｔｈｒｅｅ　ｔｙｐｅｓ　ｏｆ　ｅｘｐｅｒｉｍｅｎｔ　ｔｏ　ｅｖａｌｕａｔｅ　ｔｈｅ　ｒｅａｓｏｎａｂｉｌｉｔｙ　ｏｆ　ｇｒｏｕｐ　ｉｎｔｅｒｅｓｔｓ，ｗｈｉｃｈ　ｉｓ　ｍａｎｕａｌ　ｅｖａｌｕａｔｉｏｎ，ｔｅｓｔ　ｓｅｔ　ｅｖａｌｕａｔｉｏｎ　ａｎｄ　ａ　ｎｅｗｓ　ｒｅｃｏｍｍｅｎｄａｔｉｏｎ　ｅｘｐｅｒｉｍｅｎｔ　ｉｎ　ｖｉｄｅｏ　ｓｅｒｖｉｃｅ．Ｔｈｅ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ，ｔｈｅ　ａｃｃｕｒａｃｙ　ｏｆ　ｃｏｒｒｅｌａｔｉｏｎ　ｂｅｔｗｅｅｎ　ｇｒｏｕｐ　ｉｎｔｅｒｅｓｔｓ　ｃａｎ　ｂｅ　ｍｏｒｅ　ｔｈａｎ　５０％，ａｎｄ　ｔｈｅ　ｎｅｗｓ　ｈｉｔｓ　ｒａｔｅ　ｏｎ　ｔｈｅ　ｒｅｃｏｍｍｅｎｄａｔｉｏｎ　ｆｒｏｍ　ｇｒｏｕｐ　ｉｎｔｅｒｅｓｔｓ　ｉＳ　２　ｔｉｍｅｓ　ｌａｒｇｅｒ　ｔｈａｎ　ｔｈａｔ　ｏｎ　ｔｈｅ　ｒｅｃｏｍｍｅｎｄａｔｉｏｎ　ｆｒｏｍ　ｎｅｗｓ　ｐｏｐｕｌａｒｉｔｙ．　Ｋｅｙｗｏｒｄｓ　ｇｒｏｕｐ　ｉｎｔｅｒｅｓｔ；ｇｅｎｅｒａｌ　ｔｒｅｅ　ｏｆ　ｉｎｔｅｒｅｓｔｓ；ｃｏｌｌａｂｏｒａｔｉｖｅ　ｒｅｃｏｍｍｅｎｄａｔｉｏｎ；Ｗｉｋｉｐｅｄｉａ；　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋ　ｍｉｎｉｎｇ　收稿日期：２０１１一Ｏ８—２９；最终修改稿收到日期：２０１１—０９—１５．本课题得到国家自然科学基金（６９１２０９１２，６１０３５００４）、国家“九七三”重点基础研　究发展规划项目基金（２００７ＣＢ３１０８０４）、中国博士后科学基金（２００９０４６０１０７，２０１００３７９４）资助．张海粟，男，１９８２年生，博士研究生，中国计算机　学会（ＣＣＦ）学生会员，主要研究方向为社会网络挖掘．Ｅ－ｍａｉｌ：ｚｈａｎｇｈａｉｓｕ＠１３９．ｃｏｍ．陈桂生，男，１９６６年生，博士，高工，主要研究方向为数据　挖掘．马于涛，男，１９８０年生，博士后，副教授，主要研究方向为复杂网络．刘玉超，男，１９８１年生，博士研究生，主要研究方向为数据挖掘．　张海粟等：基于在线百科全书的群体兴趣及其关联性挖掘　１　引　言　个性化信息服务技术，如个性化推荐等，通过对　用户的互联网行为进行分析以发现其兴趣倾向，广　泛应用于精准营销、社会关系挖掘和舆情分析等领　域．目前实现个性化信息服务的常见方法有协同过　滤、基于内容过滤等，侧重于获取、表征和挖掘针对　特定个体的特征信息，据此预测或引导个人行为．与　现有个性化推荐技术有所不同，本文提出一种新的　从公开的用户合作行为数据中挖掘群体兴趣的方　法，通过群体兴趣及其关联性给出推荐．该方法不仅　针对个体特征，而且更注重社团的共性特征．如，群　体兴趣挖掘可以回答此类问题：对于“泰坦尼克号”　的观众来说，在观影前是播放香水广告还是汽车广　告，会引起他们更大的兴趣？若能给出“泰坦尼克号”　观众群的群体兴趣点表征及关联性，就可有针对性　地推送更有效果的广告或相关信息，提高营销水平．　欲挖掘群体兴趣及其关联性，首先要有能够准　确反映出群体兴趣的基础数据源．近年来，包括博　客、微博、社交网站和维基等形态在内的Ｗｅｂ　２．０　应用迅速普及，为进行此类挖掘提供了数据来源．维　基是一种群体合作模式，在创作需包罗万象的百科　全书上取得了成功应用，如维基百科．相对于其它几　种ｗｅｂ　２．０应用形态，维基百科的数据全部公开，　所包含的词条都是具有明确定义的概念，容易转化　为兴趣点，而且其噪声数据相对更小，处理起来更为　方便．因此，本文选择维基百科作为挖掘群体兴趣的　基础数据源．基于维基百科进行群体兴趣挖掘的基　本前提假设为：用户对词条做出的编辑表示其对该　词条所涉及领域抱有兴趣，而大量用户的合作编辑　过程则体现了用户群体的兴趣特征，且往往会呈现　出用户社团结构．　群体兴趣挖掘首先对用户进行聚类以识别出社　团，然后再通过社团的编辑行为特征来获取群体兴　趣．本文主要围绕群体兴趣挖掘中的两个核心问题　展开研究．其一，群体兴趣的表征．由于用户社团的　兴趣点不会局限在一个领域，往往较为广泛，且兴趣　点之间也存在上下位、同反义等语义关联，因此不能　简单地使用词条来表征兴趣点．本文根据维基百科　中词条的“类别”属性，通过基于类别树的生长策略　构建泛树结构来表征兴趣点．泛树结构能更准确地　体现出兴趣点间的语义关系，得到更易于理解的挖　掘结果．其二，用户社团对兴趣点的关注度及兴趣点　之间相关性的定义．群体兴趣是社团所表现出的固　有的、稳定的偏好特性，为了精确、有效地定义兴趣　点，需要考虑兴趣点泛树结构特征．本文给出一种融　合语义与结构特征的兴趣点关注度及其关联性度量　方法．在测试集上进行的对比实验表明，群体兴趣获　得了比基于物品的协同推荐方法＿１］更高的精度．　群体兴趣可根据用户社团的兴趣点给出推荐结　果，这一点和个性化推荐方法Ｌ１　（包括基于内容过　滤的推荐、协同推荐和基于点击流的预测等）所达成　的效果看似相同，但在实现思路上有很大不同．基于　内容过滤的推荐技术利用资源和用户兴趣的相似性　来过滤信息，协同推荐利用用户动作历史之间的相　似性，基于点击流的预测也是利用用户历史行为进　行建模．基于在线百科全书的群体兴趣挖掘则使用　群体兴趣点来替代推荐对象的个体兴趣的表征，避　免了内容过滤与点击流分析技术中新资源发现能力　较弱、协同推荐技术中冷启动和稀疏数据等问题．更　突出的是，在推荐中，通过可公开获取的维基百科中　的群体兴趣取代个性化推荐方法中用户的购买、观　影记录等个人隐私数据，避免了大量收集用户数据　时所遇到的隐私保护等社会问题．　本文第２节介绍维基百科数据源与合作编辑网　的用户聚类方法；第３节针对兴趣点表征提出兴趣　点泛树结构的构造方法；第４节给出了兴趣关注度　和关联性的定义；第５节使用３种方法对实验结果　进行了详细分析；第６节给出相关工作；最后总结　全文．　２数据源及用户聚类　２．１维基百科数据源　截至２０１１年９月１５日，维基百科已有用２８０余　种语言编写的１９００余万个词条（英文版的词条数量　最多，已超过３７３万），提供包括词条历史版本在内的　几乎所有数据（ｈｔｔｐ：／／ｄｕｍｐｓ．ｗｉｋｉｍｅｄｉａ．ｏｒｇ）．统　计表明ｌ＿３　］，维基百科能在大部分领域保持较高的准　确度和覆盖度．文献［３］通过与美国国会图书馆的　３０００篇随机文章的对比发现，除了在法律和医学领　域稍有逊色之外，其它方面维基百科几乎都有很好　的覆盖；文献［－４１统计了不同领域词条数目的分布情　况，与传统知识库相比，维基百科在专有名词、新词、　俚语、技术术语和新近事件等方面具有很大的覆盖　优势．　本文以维基百科的中文版本作为数据源，收集　数据的具体方法是：以“电影”类别下３９０个词条的　１１６５名用户作为起始输入，再以这些用户所编辑的　计　算　机　学　报　所有其它词条向外扩充用户，然后通过新扩充的用　户来扩充词条．为获得一定规模的数据量，迭代了　５次，共得到８４　０９８个词条、１７９　０２３个用户，其中包　括属于“电影”类别的词条１９９１个．　２．２用户聚类　两个用户间如果有共同编辑的词条，则在两者　问连边，即将用户一词条二部图转换为用户合作编辑　网，据此合作编辑网进行社团划分，得到用户聚类．　对２．１节的数据集进行处理，最终得到的用户合作　编辑网包括１７６　１７５个节点（删除了２８４８个孤立节　点）、５２０　８５６条边．　此处合作编辑网络的节点规模达到了１Ｏ　数量　级，为计算效率考虑，采用Ｍａｈｏｕｔ数据挖掘工具进　行合作编辑网聚类．通过部署在１Ｏ台ＰＣ上的　Ｈａｄｏｏｐ框架，向Ｍａｈｏｕｔ中的是均值算法输入参数　足一１０００．在划分为２３５个社区的时候，Ｍａｈｏｕｔ给　出了衡量聚类效果的Ｓｉｌｈｏｕｅｔｔｅ指数＿５］的最优值：　０．３８９８．因此取用户社团个数为２３５，其中最小社团　包含的节点数为４８２，最大社团包含的节点数为　２８７９．　在进一步进行兴趣点表征工作之前，在这里首　先检查群体兴趣的区分度．区分度是指用户社团所　编辑词条的覆盖程度的差异性，通过区分度可以粗　略地衡量不同用户社团之间的群体兴趣是否确有倾　向性．区分度Ｄｉｓ定义为　ｒ　—　Ｄｉｓ＝１一　，　一＞　Ｉｖ百　＾　Ａ　ｎＡ，Ｉ，　其中，Ｋ为词条总数，Ａ　表示用户社团ｉ所对应的词　条集合；忌为用户社团的总数．在Ｋ一１７６　１７５，是一　２３５，Ｓｉｌｈｏｕｅｔｔｅ指数为０．３８９８的情况下，Ｄｉｓ值达到　了９７．７　，这说明在最优社团划分的情况下，其词条　的重合程度较低．图１显示了区分度随Ｓｉｌｈｏｕｅｔｔｅ指　数的变化趋势，可以看出，随着Ｓｉｌｈｏｕｅｔｔｅ指数增　加，即用户社团划分趋于合理的时候，其所对应词条　图１　区分度随社团划分结果的变化　的区分度也呈现出增加趋势．由于不同社团所编辑　的词条具有良好的区分度，这就说明其兴趣点具有　倾向性．注意到这里的区分度直接以词条作为单位　来计算，而词条往往包含大量非常细节的概念，因此　在表征兴趣点时不能直接使用词条，否则将会由于　高区分度而忽略掉关联性，此关联性往往是词条在　更高层次的概念上所形成的．下一节将引入词条所　属类别来表征兴趣点以解决此问题．　３兴趣点泛树结构　盐铁论　亚昔　麓　亚洲　、　不连通的树合并为一棵整的泛树．节点合并中的问　１１期　张海粟等：基于在线百科全书的群体兴趣及其关联性挖掘　２２３７　节点并合并．此外还要处理噪声数据，包括设立停用　词、删除孤立节点等．　书籍　精　嘏　（ａ）不一致的层次关系　｝７哲学　７｜思想　｜，　德围思想家　，｝　奥地利作曲家　．ｃ思想　．‘哲学　马克思　马克思　（ｂ）矛盾的层次关系　（ｃ）歧义　图３类别树合并　针对图３所示的问题，类似于文献［６］的方法，　设定节点之间的相似度，以节点间的相似度达到一　定阈值作为节点合并的条件．节点Ａ和Ｂ间相似度　Ｓｉｍ（Ａ，Ｂ）的定义由语义相似度和结构相似度两部　分组成：　Ｓｉｅｒ（Ａ，Ｂ）一（１一ｄ）×ｓｅｍａｎｔｉｃＳｉｍ（Ａ，Ｂ）＋　ａ×ｓｔｒｕｃｔｕｒａｌＳｉｍ（Ａ，Ｂ）．　语义相似度ｓｅｍａｎｔｉｃＳｉｍ主要由两部分组成，　一是名字相似性，二是邻居相似性，计算方法为　ｓｅｍａｎｔｉｃＳｉｍ（Ａ，Ｂ）一　×ｎａｍｅＳｉｍ（Ａ，Ｂ）＋　（１－８）×ｎｅｉｇｈｂｏｒＳｉｍ（Ａ，Ｂ）），　其中，ｎａｍｅＳｉｍ（Ａ，Ｂ）是Ａ和Ｂ的名字相似度（可　根据简单的字符串相似程度计算，也可以引入语义　词典计算，本文的实验采用字符串相似程度），　ｎｅｉｇｈｂｏｒＳｉｍ（Ａ，Ｂ）度量邻居相似度，定义为Ａ和Ｂ　所拥有的共同邻居的名字相似度的均值．　结构相似度ｓｔｒｕｃｔｕｒａｌＳｉｍ根据一层类别树上　词条Ａ和Ｂ所处位置的相似性计算：　ｓｔｒｕｃｔｕｒａｌＳｉｍ（Ａ，Ｂ）一ｋ＋（１－－ｋ）ＤｉｆｆＳｉｍ（Ａ，Ｂ），　其中，ｋ—ｎｅｉｇｈｂｏｒ（Ａ，Ｂ）／ｒａｉｎ（ｎｅｉｇｈｂｏｒ（Ａ），　ｎｅｉｇｈｂｏｒ（Ｂ））度量的是结构特征上两个节点共同邻　居的数目比例，其中ｎｅｉｇｈｂｏｒ（Ａ，Ｂ）为Ａ、Ｂ的共同邻　居数，ｎｅｉｇｈｂｏｒ（Ａ）和ｎｅｉｇｈｂｏｒ（Ｂ）分Ｂ表示Ａ和Ｂ　的邻居数；Ｄｉｆｆ￣ｍ（Ａ，Ｂ）一１一ｎｅｉｇｈｂｏｒＳｉｍ（Ａ，　Ｂ），因此（１一是）×ＤｉｆｆＳｉｍ（Ａ，Ｂ）衡量的是共同邻　居节点之外的其它邻居节点的影响．ａ和　作为权　重调整因子，本文采用使得Ｓｉｍ（Ａ，Ｂ）结果序列的　熵最大化的方法来估计其取值．　一个兴趣点泛树结构示例如附录所示（包含了　图２中的词条）．以类别为基础，可对兴趣点分类进　行提升，使其更容易理解，如盐铁论被归类为文集、　汉朝典籍、经济史；杰尔姆・卡尔被归类为物理化学　家、诺贝尔化学奖得主．还可给出层次性的兴趣点表　征，通过不同层次上兴趣点跃升与下降给出合理的　关联性．例如，汉朝典籍上层的中国古典典籍和汉朝　文化是具有相关性的，而汉朝典籍和中国古典典籍　之间的相关性就可以弱化；中国古典典籍上层的中国　文学和各国文学之间的相关性则可以相应地强化．　４群体兴趣关注度及关联性分析　在兴趣点泛树结构基础上，本节结合用户社团　的结构特征给出群体兴趣关注度的定义，然后再根　据用户社团内部与社团之间两个影响因素来计算兴　趣点关联性．　４．１群体兴趣关注度　兴趣点关注度记为Ｆ（Ｉ，Ｇ），下面统一用Ｉ表示　泛树结构的节点，它可能是根节点（原始词条），也可　能是中间节点或叶节点（更高层次的类别标注），泛　树结构上不再区分词条和类别．Ｇ是某一个用户社　团，Ｇ对应的词条集合记为Ｊ。．本文主要从编辑行　为和兴趣点在泛树结构中的位置这两点来定义　Ｆ（工，Ｇ）．　对于编辑行为而言，兴趣点Ｉ被Ｇ中用户编辑　的次数ＮｕｍｌｎＧ（ｊ，Ｇ）与所有社团的作者全体集合　对此兴趣点的编辑次数需要联立考虑．类似于评估单　词重要性的　产ｉｄｆ方法，这里提出基于编辑特征的　ｅｆ－ｉｓｆ（ｅｄｉｔ　ｆｒｅｑｕｅｎｃｙ—ｉｎｖｅｒｓｅ　ｓｅｔ　ｆｒｅｑｕｅｎｃｙ）方法：　ｅｆ—ｉｓｆｉ，Ｇ—　＾，Ｇ×ｉｓｆｉ，　其中，ｅｆ　一ＮｕｍＩｎＧ（　，Ｇ）／Ｎｕｍ（Ｉ：Ｉ∈工Ｇ），分母　Ｎｕｍ（Ｉ：Ｉ∈ｊＧ）表示在Ｉ。中兴趣点出现的次数之　和；ｉｓｆ　一ｌｏｇ（ｆ　Ｇ　ｌ／（１＋１　Ｇ：Ｊ∈ＪＧ　１）），表示在所有　的用户社团中，具有兴趣点ｊ的社团所占比例的大　小．　厂　×　ｓ＾表示的含义为：兴趣点　在社团Ｇ中　得到编辑的概率乘上　在所有社团中得到编辑的　比例．　若兴趣点处在泛树结构的一个回路中，由于可　以认为回路中的兴趣点间具有强烈相关性，因此其　对关注度的正面影响为　Ｚ一１　ｃｉｒｃｌｅ（ｊ）：ｃｉｒｃｌｅ（Ｉ）∈ＩＧ　１／１　ｃｉｒｃｌｅ（Ｄ　ｆ，　其中，ｃｉｒｃｌｅ（Ｄ为　所处于的最短回路，Ｉ　ｃｉｒｃｌｅ（，）『　为其长度，ｌ　ｃｉｒｃｌｅ（　）：ｃｉｒｃｌｅ（　）∈ＩＧ　ｆ的含义为　既属于回路ｃｉｒｃｌｅ（　）又属于Ｊｃ的兴趣点数目，　｛ｃｉｒｃｌｅ（　）Ｉ为兴趣点Ｉ所处最短回路的长度．　Ｉ处于泛树结构的层次特征主要使用其所覆盖　的根节点数目、与根节点的距离来刻画．设Ｃ　为兴　趣点ｊ所覆盖的根节点（词条）数目，Ｃ为所有根节　点（词条）的数目；Ｈ，为距离所覆盖的根节点的平均　计　算　机　学　报　值，Ｈ为根节点到叶子节点的距离之和（泛树的高　兴趣点，和　的关联性Ｃ（，，Ｊ）同时考虑社团　度）．关注度与兴趣点所覆盖根节点的数目、与根节　点的距离成衰减关系，取高斯衰减函数刻画此关系：　ｅｘｐ［～（Ｃ／Ｃ，＋Ｈ／ＨＪ）］．　内部和社团之间两个要素，对前述计算出的社团内　部与社团之间的两个关联性结果联立考虑：　ｃ（工，Ｊ）一ｃ：，×ｃ　．　４．３群体兴趣挖掘算法步骤与复杂度分析　综合考虑编辑行为和位置信息两个因素，用户　社团Ｇ对兴趣点Ｉ的关注度为　Ｆ（Ｉ，Ｇ）一（１－－ａ）×ｅｆ－ｉｓｆＩ．Ｇ＋　ｄ×Ｚ×ｅｘｐ［一（Ｃ／Ｃ　＋Ｈ／Ｈ　）］，　其中ａ为影响因子，用于调节编辑行为与位置信息　两个因素的权重，本文按照使得Ｆ（Ｉ，Ｇ）序列的熵　最小化来确定ａ的取值，Ｚ为归一化因子．　４．２兴趣点关联性　兴趣倾向是用户社团中稳定的偏好特性，而兴　趣倾向之间的关联性通过用户社团联系起来．兴趣　点间的关联性需考虑两个因素：（１）用户社团内部　结构以及兴趣点关注度等所产生的关联；（２）用户　社团之间所体现出的兴趣点关联．对于这两个因素　处理的基本原则有：社团内部兴趣点的关联性要比　社团之间的更强；社团内部具有更强关注度的兴趣　点之间的关联性更强；处于类似位置的兴趣点之间　的关联性强．　对于用户社团Ｇ内部的兴趣点Ｉ和Ｊ的关联性，　转化为对点加权的网络频繁子结构挖掘问题．其中，　点权重即为Ｇ对于相应兴趣点的关注度Ｆ（　，Ｇ），频　繁子图为同时包含　和Ｊ的最小子图．首先暂不考　虑节点权重，采用经典的ＡｐｒｉｏｒｉＧｒａｐｈ算法Ｌ７　来挖　掘频繁子结构．在计算出频繁子结构Ｓ　，之后，再使　用简单的值和约束法则Ｓｕｍ　ｌｏｗ，其中Ｓｕｍ　为　子结构Ｓ　，中所有节点的权重之和，ｌｏｗ为指定的至　少应该满足的阈值．所挖掘出的满足指定支持度的　频繁子图Ｓ　，的数目记为ｍ，频繁子图Ｓ．，所体现的　关联性即可定义为Ｓ　，在整个泛树结构Ｓ中所占的　面积比（其中ｆ　ｓ　，ｆ和ｆ　Ｓｆ分别表示节点数目）：　Ｃ，Ｊ—ｍ・ｆ　Ｓ　，ｌ／（ｆ　Ｓｆ—ｍ・ｆ　Ｓ　，｝）．　对于分别位于两个社团上的兴趣点，和　的关　联性，关键是计算出其在各自所属的泛树结构上的　共同祖先节点Ｐ　一Ｐ　，然后根据，和Ｊ在两个泛树　上分别与此公共祖先节点的距离来确定两者的相关　性．具体方法为，假设存在此公共祖先节点Ｐ　一Ｐ　，　Ｊ和Ｊ到Ｐ　和Ｐ　Ｊ的最短距离分别为ｄ（卜一Ｐ　），　ｄ（Ｊ—Ｐ，），则Ｊ和．，的社团之间关联性为　Ｃ　一ｅｘｐ一［１／ｄ（ｆ—Ｐ　）＋１／ｄ（Ｊ—ＰＪ）］．　其物理含义是，相关性与公共祖先节点的距离　成反比．若公共祖先节点不存在，则定义ｄ（卜一Ｐ　）　和　（卜一Ｐ，）为距离泛树结构叶子节点的最短距离．　总结前述群体兴趣挖掘算法的主要步骤，包括　用户聚类、兴趣点泛树构建、计算关注度与相关性等　四步，如图４所示．其中，矩形框为算法步骤，椭圆形　为数据，实箭头标示了数据的输入输出关系，空箭头　标示了数据间的关系．　图４群体兴趣挖掘的主要算法步骤　其中，原本复杂度较高的大规模复杂网络聚类　通过基于ＭａｐＲｅｄｕｃｅ的分布式计算平台，复杂度被　降至０（Ｎ・ｌｏｇ（Ｎ）），其中Ｎ为网络的节点数目．兴　趣点表征的复杂度主要在泛树结构的构建步骤，泛树　结构的生长策略按照逐步处理一层类别树的方法，且　要计算每一个类别的相似度，故复杂度为Ｏ（Ｎ　・　（１＋ｓｕｍ（Ｏ（ｚ））），其中Ｎ　为所有类别树的总数，ｚ　为一层类别树的平均节点数，记ｚ　为某类别树的节　点数，ｓｕｍ（Ｏ（ｚ））一（ｚｌ　ｚ２＋（ｚｌ＋ｚ２）　＋…＋（ｚｌ＋　Ｚ２＋…＋　一１）Ｚ　），因此Ｏ（Ｎ　・（１＋ｓｕｍ（０（Ｚ）））一　Ｏ（Ｎ　＋Ｎ　／２）一Ｏ（Ｎ　／２）．在兴趣关注度与相关性　步骤，因为均要计算出整个矩阵的元素，故计算复杂　度为０（１Ｇ１　），其中１Ｇｌ为用户社团和兴趣点所构成　的矩阵Ｇ的元素个数．泛树结构、兴趣关注度和相关　性计算均没有很强耦合的步骤，因此可置于ＭａｐＲｅ－　ｄｕｃｅ分布式平台上，进而复杂度可以进一步降低．　５实验结果分析　５．１　实验过程与评价方法　在前期抽取的１７６　１７５个用户节点、５２０　８５６条　边、２３５个用户社团的基础上，按照图４所示的算法　步骤，建立起群体兴趣及其关联的基础数据库，其　中，针对每一个社团Ｇ和兴趣点Ｉ记录了关注度　张海粟等：基于在线百科全书的群体兴趣及其关联性挖掘　２２３９　Ｆ（Ｇ，Ｄ，针对所有的兴趣点二元组（　，　）记录了关　联性程度Ｃ（Ｉ，Ｊ）．此基础数据可以定期根据维基百　科数据源的变动情况重新计算，达到实时更新的效　果．对群体兴趣的合理性和准确度采用３种方法进　行评价：　（１）人工直观观察结果．　实验以维基百科中“电影”类别下的词条为初始　内容开始爬取．因此，可以直接人工地输入一部电影　作为兴趣点，再借助于常识，定性地评估其返回的关　联兴趣点的合理性。　（２）借助于测试数据集．　引言中已提及，根据用户点击流进行个性化行　为预测会遇到新资源发现能力缺乏的问题．但是，已　记录下的点击流数据却是验证群体兴趣点关联性较　为理想的测试数据集．通过对比群体兴趣的关联性　与真实点击流数据所体现出关联性之间的符合程度　来验证挖掘结果的准确性．本文的点击流数据源由　两部分组成，一是抽取了Ａｍａｚｏｎ．ｃｎ中电影书籍和　ＣＤ类商品的点击浏览数据，二是校园网门户上新　闻页的关键词．这两部分的数据必须结合起来，以达　到领域较宽（由新闻页关键词保证）和内容较准确　（购物网站物品浏览）的目的，从而便于测试群体兴　趣的结果．　通过点击流衡量群体兴趣的具体方法是，给定　任意两个兴趣点　、　及其通过群体兴趣挖掘所得　到的关联性Ｃ（Ｉ，Ｊ），计算在点击流中兴趣点　和　之间的距离ｋ（Ｉ，．厂）（若　或　在点击流中没有出现　则定义为点击流序列的最长距离）．对于点击流中的　相关性，采用简单的距离反比，即１／ｋ（　，Ｊ）越小，　则Ｉ和Ｊ之间的关联性越大．因此，如果Ｃ（Ｊ，Ｊ）和　１／ｋ（Ｉ，Ｊ）所构成的矩阵ｃ和Ｋ呈现出很强的正相　关，就可以说明群体兴趣关联性挖掘的有效性．矩阵　ｃ和Ｋ的相关性通过每一行数据的皮尔逊相关系数　相加得到．　作为基准算法进行类比，使用基于物品（兴趣　点）的协同推荐方法进行了计算．在这里，协同推荐　采用文献Ｅ８３中的算法实现：兴趣点拥有的共同用户　越多，推荐的关联性越强．　（３）网站推荐的实际应用．　以在校园网的视频点播服务中添加新闻链接的　方式进行测试，通过新闻链接被点击的次数作为对　比．实验过程为：在为期一个月的时间内，按照Ｗｅｂ　新闻页面点击的热度确定概率的大小、随机地分配　新闻链接到各视频源上；然后在接下来的一个月时　间内，以同样的视频源作为输入，但是将当前的新闻　链接按照兴趣点相近的原则重新分配．　５．２结果分析　（１）直观结果．　输入测试用例：电影“建国大业”，“泰坦尼克号”，　将返回的关联性最高的９个兴趣点及关联性程度绘　制成雷达图，如图５所示．这里返回的兴趣点分布　于泛树结构各层次，主要依据是关联性程度的排序．　表１列举了另外４部知名电影作为兴趣点输入的测　试结果．　表１兴趣点相关性　输入兴趣点　相关性（相关性按由前到后降序排列）　第一滴血；野战排；奠边府战役；梅兰芳（电影）；　阿甘正传　巴顿将军；乱世佳人（电影）；国际象棋；大学；汤　姆・汉克斯；约翰・肯尼迪　詹姆斯・卡梅隆；终结者；真实的谎言；京杭大　阿凡达　运河；世界三大天然良港；戴维斯一蒙森空军基　地｝哈利・波特；比尔与美琳达・盖茨基金会；　泰坦尼克号；泛美航空２１４号班机空难　非诚勿扰（电影）；手机；秦皇岛；天津；ｉＰｈｏｎｅ；　唐山大地震　编辑部的故事；徐帆；国家地震局；我的机器人　女友；泰坦尼克号　永利街；新宝戏院；美国电影学院；上环；拔萃男　岁月神偷　书院；市区重建局；吴君如；资助学校；香港杰出　学生　泰坦尼克号　梅隆　爱情　建国大业　停车场　北京　邵逸夫　家族　史诗　口岸　韩三平　图５群体兴趣关联性示例（与电影“泰坦尼克号”和　“建国大业”强关联的兴趣点）　从定性的角度分析，可以看出，对于图５中这两　部电影来说，其导演和所反映的背景事件都是用户　社团具有强烈兴趣的（如奥斯卡、战争等）．而其它的　兴趣点中，“泰坦尼克号”社团更加关注一些时尚话　题，如香港小姐竞选等；“建国大业”社团则对于摄影　等有兴趣，而“停车场”的意外出现则可能与影院或　计　算　机　学　报　者生活服务相关．　进一步分析表１中所列举的案例，可以看出，每　一部电影相关的背景、演员和导演等所涉及的信息　往往都是关联性较高的兴趣点所在，同时一些“意料　之外”的结果，如“阿甘正传”中的“国际象棋”、“阿凡　达”中的“京杭大运河”等，往往更可能提示一些有趣　的、隐藏的推荐信息．　总之，从直观上看，每一部电影的用户社团都带　有较为强烈的群体兴趣的倾向性，这有助于挖掘互　联网上大量用户的背景和关注点等有用信息．　（２）测试数据集的覆盖度．　在具体实验中，本文抽取的测试集数据规模为：　Ａｍａｚｏｎ．ｃｎ影视分类下的３９８０部电影和１５　８２０个　相关的点击数据；校园网新闻（包括时政新闻和校园　新闻）的５６９２个关键词和相关点击排名前５的２８　４６０个关键词．最终所得测试集中一共包括５３　９５２个　关键词（其中包括重合的９８０２个关键词）．　分５次随机抽取５个用户社团对应的兴趣点二　元组＜ｆ，Ｊ＞集合，所得到的兴趣点在测试集中出现的　比例分别为１Ｏ．７１％，１２．４３％，６．１７％，ＩＩ．５２　和　９．４７　．在此基础上，分别计算群体兴趣关联性程度、　协同推荐的结果与点击流之间的相关系数，其结果对　比如图６所示．需要说明的是，这里将Ａｍａｚｏｎ．ｃｎ的　数据看作点击流的真实数据而不是协同推荐的结　果，因此协同推荐只计算了校园网中用户点击新闻　网页的关键词这一部分．　巅　ｇ　嫣　佰　《　林　图６　与实际点击流的相关系数　总体上看，两者的相关系数均维持在３Ｏ　９／６以　上，说明都体现出了较为明显的推荐效果．但相对于　协同推荐，群体兴趣的相关性还要高出１５　９／６左右．　事实上，校园网用户点击行为所涉及的领域很宽，同　时其数据较为稀疏（每一位用户收集到的点击关键　词平均为８．６个）．因此，在此种情况下，本案例中的　群体兴趣推荐方法取得了更好的推荐准确率．　（３）视频点播中的新闻推荐实验　校园网的视频点播服务提供电影、新闻和教学　视频的在线播放功能．我们在播放器窗口边设置了　类似于广告的新闻链接来测试推荐效果．在为期两　个月的测试周期中，共得到了１２９　０８６次播放和　９０８７次有效点击（停留时间在３０　Ｓ以上）．其中，在　按照新闻热度放置的一个月中，播放次数和有效点　击次数分别为６７　３４０和５３８７次；在使用群体兴趣　推荐的一个月中，播放次数和有效点击次数分别为　６１　７４６次和１０　３４９次，点击数量提高了近一倍．图７　（ａ）给出了进行实验的２个月内点击新闻链接的概　率曲线．可以看出，使用了群体兴趣关联性推荐的效　果，比起按照新闻热度排序放置的效果高出１Ｏ　～　２０　，相对于本来就约等于１０　的点击率水平，高　出接近一倍，而且基于群体兴趣推荐所得到的点击　概率一直维持在相对较高的水平．　Ｓ一　ｚ）《　永　枯翅　Ｏ　Ｏ　Ｏ　Ｏ　Ｏ　Ｏ　Ｏ　（ｂ）　图７新闻推荐实验中的用户点击概率　另一方面，我们将视频播放中用户点击的新闻　链接记录下来，对比其与群体兴趣关联性的相关系　数（采用类似于图６的皮尔逊相关系数），结果如　图７（ｂ）所示．这里将视频分成电影、新闻和教学三　类．其中，播放电影时的用户点击新闻的概率相对较　低，播放新闻和教学类视频时用户点击新闻的概率　基本相当．与按照新闻热度放置的效果相比，在点击　概率较低的电影类视频中，兴趣推荐能够很大地提　高用户点击所推荐信息的概率．　张海粟等：基于在线百科全书的群体兴趣及其关联性挖掘　２２４１　闻推荐上更比依热度放置链接的效果高出１倍．这　６　相关工作　目前，用户兴趣挖掘的重点集中在动作行为日　志分析¨ｇ　．一种常用的方法是直接抽取用户访问　些实验证明了基于群体兴趣进行推荐的有效性．随　着互联网尤其是Ｗｅｂ２．０的快速发展，我们能够更　加方便地获取公开数据，但同时隐私数据也将得到　更为严格的保护．因此，推荐算法如何从收集私人历　史行为数据转向利用庞大的公开数据，包括本文提　及的维基百科合作编辑以及博客、微博等，应该值得　进一步深入关注．　文档集合中的关键词作为用户兴趣的表征项，借助　聚类和学习算法，挖掘出用户的兴趣［１　］．通常，此　方法同样面临着隐私数据的保护问题．同时，由于所　抽取的特征词在语义上的多义性ｌ１　，单纯基于日志　行为分析所发现的用户兴趣精度难以进一步提高，　而且一般没有可用的本体或语义关系库用来实现兴　趣在概念层次上的跃升与下降等．　还有很多其它技术可直接应用到群体兴趣挖掘　中．如，分类树和本体构建方面的研究方法，包括从　文本中学习概念层次的单词聚类技术『】引，从标注和　分众分类中获取层次结构的基于图的聚类技术［６　等，均可用于提高兴趣点泛树结构的精度．针对维基　百科数据源进行概念提取的工作，目前学术界也有　涉及．如ＨｅｉＮＥＲＥ１８和ＹＡＧＯ［１。　等，将词条名字作　为概念的候选，采取了一些语言学方法进行筛选，这　些思路可用于进一步完善兴趣点的表征．　个性化信息服务技术的发展也在不断地深入．　文献［１］针对目前推荐算法仍然存在的特征提取困　难、冷启动、数据稀疏等问题，总结了引人上下文环　境来扩展“物品一用户”二维关系的多维度推荐、利用　相关反馈提高精度、隐私保护以及推荐中的社会学　因素等多个改进方向．正如本文强调的，基于完全公　平的在线百科全书的群体兴趣在数据收集、反馈、推　荐新资源等方面采用了完全不同的思路，因此两者　可以相互结合，在获取用户隐私数据难易程度不同　的场景下发挥各自的作用．　７　总　结　本文以在线百科全书的数据源作为基础，通过　提取合作编辑过程中的用户社团，给出了社团的群　体兴趣及关联性，可针对非特定个体、但是具有共同　属性的群体进行有效推荐．其核心问题为群体兴趣　的表征和用户社团对兴趣点的关注度及兴趣点之间　相关性的定义．本文提出了一种兴趣点泛树结构的　生长策略，开发了结合结构特征和语义特征的群体　兴趣关注度计算方法．在人工评价、点击流真实数据　测试集和校园网视频点播中的新闻推荐实验等三方　面，都获得了较为明显的效果．如，和点击流数据的　相关性比传统的协同推荐算法要高出１５　左右，新　致谢感谢邓智龙对于实验数据处理的帮助！　参　考　文　献　［１］Ｘｕ　Ｈａｌ—Ｌｉｎｇ，Ｗｕ　Ｘｉａｏ，Ｌｉ　Ｘｉａｏ－Ｄｏｎｇ，Ｙａｎ　Ｂａｏ—Ｐｉｎｇ．Ｃｏｍ—　ｐａｒｉｓｏｎ　ｓｔｕｄｙ　ｏｆ　ｉｎｔｅｒｎｅｔ　ｒｅｃｏｍｍｅｎｄａｔｉｏｎ　ｓｙｓｔｅｍ．Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｆｔｗａｒｅ，２００９，２０（２）：３５０—３６２（ｉｎ　Ｃｈｉｎｅｓｅ）　（许海玲，吴潇，李晓东，阎保平．互联网推荐系统比较研　究．软件学报，２００９，２０（２）：３５０—３６２）　Ｅ２３　Ｓｔａｄｎｙｋ　Ｉ，Ｋａｓｓ　Ｒ．Ｍｏｄｅｌｉｎｇ　ｕｓｅｒｓ　ｉｎｔｅｒｅｓｔｓ　ｉｎ　ｉｎｆｏｒｍａｔｉｏｎ　ｆｉｌｔｅｒｓ．Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　ｏｆ　ｔｈｅ　ＡＣＭ，１９９２，３５（１２）：４９—５Ｏ　［３］Ｈａｌａｖａｉｓ　Ａ，Ｌａｅｋａｆｆ　Ｄ．Ａｎ　ａｎａｌｙｓｉｓ　ｏｆ　ｔｏｐｉｃａｌ　ｃｏｖｅｒａｇｅ　ｏｆ　Ｗｉｋｉｐｅｄｉａ．Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ—Ｍｅｄｉａｔｅｄ　Ｃｏｍｍｕｎｉｃａｔｉｏｎ，　２００８，１３（２）：４２９—４４０　［４］Ｋｉｔｔｕｒ　Ａ，Ｃｈｉ　Ｅ　Ｈ，Ｓｕｈ　Ｂ．Ｗｈａｔ’Ｓ　ｉｎ　ｗｉｋｉｐｅｄｉａ：Ｍａｐｐｉｎｇ　ｔｏｐｉｃｓ　ａｎｄ　ｃｏｎｆｌｉｃｔ　ｕｓｉｎｇ　ｓｏｃｉａｌｌｙ　ａｎｎｏｔａｔｅｄ　ｃａｔｅｇｏｒｙ　ｓｔｒｕｃ—　ｔｕｒｅ／／Ｐｒ０ｃｅｅ出ｎｇｓ　ｏｆ　ｔｈｅ　ＡＣＭ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｈｕｍａｎ　Ｆａｃｔｏｒｓ　ｉｎ　Ｃｏｍｐｕｔｉｎｇ　Ｓｙｓｔｅｍｓ．Ｂｏｓｔｏｎ，ＵＳＡ，２００９：１５０９—１５１２　Ｅ５３　Ｌｉｎ　Ｔｓｕｎ—Ｃｈｅｎ，Ｌｉｕ　Ｒｕ—Ｓｈｅｎｇ，Ｃｈｅｎ　Ｓｈｕ—Ｙｕａｎ，Ｌｉｕ　Ｃｈｅｎ—　Ｃｈｕｎｇ，Ｃｈｅｎ　Ｃｈｉｅｈ—Ｙｕ．Ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍｓ　ａｎｄ　ｓｉｌｈｏｕｅｔｔｅ　ｍｅａｓｕｒｅｓ　ａｐｐｌｉｅｄ　ｔｏ　ｍｉｃｒｏａｒｒａｙ　ｄａｔａ　ｃ１ａｓｓｉｆｉｃａｔｉｏｎ／／Ｐｒｏｃｅｅｄ—　ｉｎｇｓ　ｏｆ　ｔｈｅ　３ｒｄ　Ａｓｉａ—Ｐａｃｉｆｉｃ　Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ　Ｃｏｎｆｅｒｅｎｃｅ．　Ｓｉｎｇａｐｏｒｅ，２００５：２２９—２３８　［６］　Ｐｌａｎｇｐｒａｓ０ｐｃｈｏｋ　Ａ，Ｌｅｒｍａｎ　Ｋ，Ｇｅｔｏｏｒ　Ｌ．Ｇｒｏｗｉｎｇ　ａ　ｔｒｅｅ　ｉｎ　ｔｈｅ　ｆｏｒｅｓｔ：Ｃｏｎｓｔｒｕｃｔｉｎｇ　ｆｏｌｋｓｏｎｏｍｉｅｓ　ｂｙ　ｉｎｔｅｇｒａｔｉｎｇ　ｓｔｒｕｃ—　ｔｕｒｅｄ　ｍｅｔａｄａｔａ／／Ｐｒ０ｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｋｎｏｗｌ—　ｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａ　Ｍｉｎｉｎｇ．Ｗａｓｈｉｎｇｔｏｎ，ＵＳＡ，２０１０：　９４９—９５８　［７］Ｈａｎ　Ｊｉａ—Ｗｅｉ，Ｋａｍｂｅｒ　Ｍ，Ｐｅｉ　Ｊｉａｎ．Ｄａｔａ　Ｍｉｎｉｎｇ：Ｃｏｎｃｅｐｔｓ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｉｅｓ．３　ｒｄ　Ｅｄｉｔｉｏｎ．Ｍａｓｓａｃｈｕｓｅｔｔｓ，ＵＳＡ：Ｍｏｒｇａｎ　Ｋａｕｆｍａｎｎ　Ｐｕｂｌｉｓｈｅｒｓ，２０１　１　Ｅ８３　Ｓｅｇａｒａｎ　Ｔ．Ｐｒｏｇｒａｍｍｉｎｇ　Ｃｏｌｌｅｃｔｉｖｅ　Ｉｎｔｅｌｌｉｇｅｎｃｅ：Ｂｕｉｌｄｉｎｇ　Ｓｍａｒｔ　Ｗｅｂ　２．０　Ａｐｐｌｉｃａｔｉｏｎｓ．ＵＳＡ：Ｏ’Ｒｅｉｌｌｙ　Ｍｅｄｉａ，２００７　［９３　Ｇｕｏ　Ｙａｈ，Ｂａｉ　Ｓｈｕｏ，Ｙａｎｇ　Ｚｈｉ—Ｆｅｎｇ，Ｚｈａｎｇ　Ｋａｉ．Ａｎａｌｙｚｉｎｇ　ｓｃａｌｅ　ｏｆ　ｗｅｂ　ｌｏｇｓ　ａｎｄ　ｍｉｎｉｎｇ　ｕｓｅｒｓ’ｉｎｔｅｒｅｓｔｓ．Ｃｈｉｎｅｓｅ　Ｊｏｕｒ～　ｎａｌ　ｏｆ　Ｃｏｍｐｕｔｅｒｓ，２００５，２８（９）：１４８３—１４９６（ｉｎ　Ｃｈｉｎｅｓｅ）　（郭岩，白硕，杨志峰，张凯．网络日志规模分析和用户兴趣　挖掘．计算机学报，２００５，２８（９）：１４８３－１４９６）　［１０］Ｂｒｚｏｚｏｗｓｋｉ　Ｍ　Ｊ，Ｒｏｍｅｒｏ　Ｄ　Ｍ．Ｗｈｏ　ｓｈｏｕｌｄ　Ｉ　ｆｏｌｌｏｗ？Ｒｅｃ—　ｏｍｍｅｎｄｉｎｇ　ｐｅｏｐｌｅ　ｉｎ　ｄｉｒｅｃｔｅｄ　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋｓ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　５ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　ＡＡＡＩ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｗｅｂｌｏｇｓ　ａｎｄ　Ｓｏｃｉａｌ　Ｍｅｄｉａ．Ｂａｒｃｅｌｏｎａ，Ｓｐａｉｎ，２０１１：４５８－４６１　Ｅｌ１］Ｌｉｕ　Ｊｉａ－Ｈｕｉ，Ｄｏｌａｎ　Ｐ，Ｒｏｎｂｙ　Ｅ．Ｐｅｒｓｏｎａｌｉｚｅｄ　ｎｅｗｓ　ｒｅｃｏｍ—　ｍｅｎｄａｔｉｏｎ　ｂａｓｅｄ　ｏｎ　ｃｌｉｃｋ　ｂｅｈａｖｉ０ｒ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ｌ５ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｉｎｔｅｌｌｉｇｅｎｔ　Ｕｓｅｒ　Ｉｎｔｅｒｆａｃｅｓ．Ｎｅｗ　Ｙｏｒｋ，ＵＳＡ，２０１０：３１—４０　２２４２　计　算　机　学　报　２０１１往　Ｂ－Ｑ，Ｌｉ　Ｙ。Ｐａｎ　Ｓ—Ｌ．Ａ　ｎｏｖｅｌ　ｕｓｅｒｓ’ｉｎｔｅｒｅｓｔｓ　［１２］　Ｍａｏ　Ｑ－Ｊ，Ｆｅｎｇ　ｐｒｅｄｉｃｔｉｏｎ　ａｐｐｒｏａｃｈ　ｂａｓｅｄ　ｏｎ　ｃｏｎｃｅｐｔ　ｌａｔｔｉｃｅ．Ｊｏｕｒｎａｌ　ｏｆ　Ｓｈａｎ—　ｄｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ（Ｅｎｇｉｎｅｅｒｉｎｇ　Ｓｃｉｅｎｃｅ），２０１０，４０（５）：１５９—１６３　ｂｕｒｇ，ＵＳＡ，２００６：８０１－８０８　　Ｎ．Ｉｍｐｒｏｖｅｄ　ａｎｎｏｔａｔｉｏｎ　ｏｆ　ｔｈｅ　ｂｌｏｇｏ　［１６］　Ｂｒｏｏｋｓ　Ｃ　Ｈ，Ｍｏｎｔａｎｅｚｓｐｈｅｒｅ　ｖｉａ　ａｕｔｏ～ｔａｇｇｉｎｇ　ａｎｄ　ｈｉｅｒａｒｃｈｉｃａｌ　ｃｌｕｓｔｅｒｉｎｇ／／Ｐｒ０ｃｅｅｄ—　ｉｎｇｓ　ｏｆ　ｔｈｅ　ｌ５ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｅｅ　ｏｎ　Ｗ　ｏｒｌｄ　Ｗｉｄｅ　Ｗｅｂ．Ｅｄｉｎｂｕｒｇｈ，ＵＫ，２００６：６２５－６３２　［】３］　Ｚｅｎｇ　Ｑｉｎｇ—Ｗｅｉ，Ｊｉａｎｇ　Ｊｉｅ．Ｒｅｓｅａｒｃｈ　ａｎｄ　ｉｍｐｌｅｍｅｎｔａｔｉｏｎ　ｏｎ　ｐｅｒｓｏｎａｌｉｚｅｄ　ｓｅａｒｃｈ　ｅｎｇｉｎｅ．　Ｋｅｙ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｍａｔｅｒｉａｌｓ，　２Ｏ１１，４６７（２）：１２９—１３３　［１７３　Ｗｅｎｔｌａｎｄ　Ｗ，Ｋｎｏｐｐ　Ｊ，Ｓｉｌｂｅｒｅｒ　Ｃ，Ｈａｒｔｕｎｇ　Ｍ．Ｂｕｉｌｄｉｎｇ　ａ　ｍｕｌｔｉｌｉｎｇｕａｌ　ｌｅｘｉｃａｌ　ｒｅｓｏｕｒｃｅ　ｆｏｒ　ｎａｍｅｄ　ｅｎｔｉｔｙ　ｄｉｓａｍｂｉｇｕ—　ｍ　Ｈａｋ—Ｌａｅ，Ｂｒｅｓｌｉｎ　Ｊ　Ｇ，Ｄｅｅｋｅｒ　Ｓ，Ｋｉｍ　Ｈｏｎｇ－Ｇｅｅ．Ｍｉｎ—　［１４］　Ｋｉｉｎｇ　ａｎｄ　ｒｅｐｒｅｓｅｎｔｉｎｇ　ｕｓｅｒ　ｉｎｔｅｒｅｓｔｓ：Ｔｈｅ　ｃａｓｅ　ｏｆ　ｔａｇｇｉｎｇ　ｐｒａｃ—　ｔｉｃｅｓ．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｓｙｓｔｅｍｓ，Ｍａｎ．ａｎｄ　Ｃｙｂｅｒｎｅｔ—　ａｔｉｏｎ，ｔｒａｎｓｌａｔｉｏｎ　ａｎｄ　ｔｒａｎｓＩｉｔｅｒａｔｉｏｎ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　６ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｌａｎｇｕａｇｅ　Ｒｅｓｏｕｒｃｅｓ　ａｎｄ　Ｅｖａｌｕａｔｉｏｎ．Ｍａｒｒａ—　ｉｃｓ，Ｐａｒｔ　Ａ：Ｓｙｓｔｅｍｓ　ａｎｄ　Ｈｕｍａｎｓ，２０１１，４１（４）：６８３—６９２　ｋｅｃｈ，Ｍｏｒｏｃｃｏ，２００８：３２３０～３２３７　［１５］　Ｓｎｏｗ　Ｒ，Ｊｕｒａｆｓｋｙ　Ｄ，Ｎｇ　Ａ　Ｙ．Ｓｅｍａｎｔｉｃ　ｔａｘｏｎｏｍｙ　ｉｎｄｕｃｔｉｏｎ　ｆｒｏｍ　ｈｅｔｅｒ０ｇｅｎｅｏｕｓ　ｅｖｉｄｅｎｃｅ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２１ｓｔ　Ｉｎｔｅｒ—　ｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｃｏｍｐｕｔａｔｉｏｎａｌ　Ｌｉｎｇｕｉｓｔｉｃｓ．Ｓｔｒｏｕｄｓ一　［１８］Ｓｕｃｈａｎｅｋ　Ｆ　Ｍ，Ｋａｓｎｅｃｉ　Ｇ，Ｗｅｉｋｕｍ　Ｇ．ＹＡＧＯ：Ａ　ｌａｒｇｅ　ｏｎ—　ｔｏｌｏｇｙ　ｆｒｏｍ　ｗｉｋｉｐｅｄｉａ　ａｎｄ　ＷｏｒｄＮｅｔ．Ｅｌｓｅｖｉｅｒ　Ｊｏｕｒｎａｌ　ｏｆ　Ｗｅｂ　Ｓｅｍａｎｔｉｃｓ，２００８，６（３）：２０３—２１７　附录．　兴趣点泛树结构示例．　ＺＨＡＮＧ　Ｈａｉ－Ｓｕ，ｂｏｒｎ　ｉｎ　１９８２，　ＣＨＥＮ　Ｇｕｉ－Ｓｈｅｎｇ，ｂｏｒｎ　ｉｎ　１９６６，Ｐ　ｈ．Ｄ．，ｓｅｎｉｏｒ　ｅｎｇｉ—　ｎｅｅｒ．Ｈｉｓ　ｍａｉｎ　ｒｅｓｅａｒｃｈ　ｉｎｔｅｒｅｓｔ　ｉＳ　ｄａｔａ　ｍｉｎｉｎｇ．　ＭＡ　Ｙｕ—Ｔａｏ，ｂｏｒｎ　ｉｎ　１　９８０，Ｐｈ．Ｄ．，ａｓｓｏｃｉａｔｅ　ｐｒｏｆｅｓｓｏｒ．　Ｈｉｓ　ｍａｉｎ　ｒｅｓｅａｒｃｈ　ｉｎｔｅｒｅｓｔ　ｉｓ　ｃｏｍｐｌｅｘ　ｎｅｔｗｏｒｋ．　ＬＩＵ　Ｙｕ—Ｃｈａｏ。ｂｏｒｎ　ｉｎ　１９８１，Ｐｈ．Ｄ．ｃａｎｄｉｄａｔｅ．Ｈｉｓ　Ｐｈ．Ｄ．ｃａｎｄｉｄａｔｅ．Ｈｉｓ　ｍａｉｎ　ｒｅｓｅａｒｃｈ　ｉｎ—　ｔｅｒｅｓｔ　ｉｓ　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋ　ｍｉｎｉｎｇ．　ｍａｉｎ　ｒｅｓｅａｒｃｈ　ｉｎｔｅｒｅｓｔ　ｉｓ　ｎｅｔｗｏｒｋ　ｍｉｎｉｎｇ．　Ｂａｃｋｇｒｏｕｎｄ　Ｍｉｎｉｎｇ　ｕｓｅｒｓ’ｉｎｔｅｒｅｓｔｓ　ｆｏｒ　ｔｈｅ　ｒｅｃｏｍｍｅｎｄａｔｉｏｎ　ｓｙｓｔｅｍｓ　ｉｓ　ａｎ　ｉｍｐｏｒｔａｎｔ　ａｐｐｌｉｃａｔｉｏｎ　ｉｎ　ｔｈｅ　ｅ—ｃｏｍｍｅｒｃｅ．ｓｕｃｈ　ａｓ　ｐｒｅ—　ｉｎｔｅｒｅｓｔｓ　ｏｆ　ａ　ｐｅｒｓｏｎ　ｉｎｔｏ　ａ　ｓｉｍｉｌａｒ　ａｎｄ　ｐｕｂｌｉｃ　ｇｒｏｕｐ（ｉｎ　ｔｈｉｓ　ｐａｐｅｒ，ｔｈｉｓ　ｇｒｏｕｐ　ｉｓ　ｔｈｅ　ｃｏ—ｅｄｉｔｏｒｓ　ｉｎ　Ｗｉｋｉｐｅｄｉａ）．　Ｔｈｉｓ　ｒｅｓｅａｒｃｈ　ｉｓ　ｓｕｐｐｏｒｔｅｄ　ｂｙ　ｔｈｅ　Ｎａｔｉｏｎａｌ　Ｎａｔｕｒａ１　Ｓｃｉ—　ｅｎｃｅ　Ｆｏｕｎｄａｔｉｏｎ　ｏｆ　Ｃｈｉｎａ　ｕｎｄｅｒ　Ｇｒａｎｔ　Ｎｏｓ．６９１２０９１２，　６１０３５００４，ｔｈｅ　Ｎａｔｉｏｎａｌ　Ｂａｓｉｃ　Ｒｅｓｅａｒｃｈ　Ｐｒｏｇｒａｍ（９７３　Ｐｒｏ－　ｃｉｓｅ　ｍａｒｋｅｔｉｎｇ　ａｎｄ　ｐｕｂｌｉｃ　ｏｐｉｎｉｏｎ　ａｎａｌｙｓｉｓ．Ｎｏｗ　ｔｈｅ　ｍａｉｎ　ｐｏｐｕｌａｒ　ｍｅｔｈｏｄｓ　ｆｏｒ　ｉｎｔｅｒｅｓｔ　ｍｉｎｉｎｇ　ｃａｎ　ｂｅ　ｓｕｍｍａｒｉｚｅｄ　ａｓ　ｃｏｌｌａｂｏｒａｔｉｖｅ　ｆｉｌｔｅｒｉｎｇ　ａｎｄ　ｃｏｎｔｅｎｔｍｅｎｔ—ｂａｓｅｄ　ｆｉｌｔｅｒｉｎｇ，ｗｈｉｃｈ　ｃａｎ　ｂｅ　ｓｅｅｎ　ａｓ　ａ　ｐｅｒｓｏｎａｌｉｚｅｄ　ｔｅｎｄｅｎｃｙ　ｍｉｎｉｎｇ　ｔｅｃｈｎｏｌｏｇｙ．　Ｈｅｎｃｅ，ｔｈｅｒｅ　ａｒｅ　ｓｏｍｅ　ｄｒａｗｂａｃｋｓ　ｏｆ　ｔｈｅｓｅ　ｍｅｔｈｏｄｓ，ｓｕｃｈ　ａｓ　ｔｈｅｙ　ｍｕｓｔ　ｃｏｌｌｅｃｔ　ｌｏｔｓ　ｏｆ　ｕｓｅｒｓ　ｈｉｓｔｏｒｙ　ｄａｔａ，ｓｏｍｅｔｉｍｅｓ　ｉｔ　ｉｓ　ｄｉｆｆｉｃｕｌｔ　ａｎｄ　ｉｌｌｅｇａｌ　ｆｏｒ　ｔｈｅ　ｐｒｉｖａｃｙ　ｐｒｏｔｅｃｔｉｏｎ　ｐｏｌｉｃｙ．Ｏｔｈｅｒ　ｄｒａｗｂａｃｋｓ，ｓｕｃｈ　ａｓ　ｃｏｌｄ　ｓｔａｒｔ　ａｎｄ　ｓｐａｒｓｅ　ｄａｔａ，ｍｏｒｅ　ｏｒ　ｌｅｓｓ　ａｒｅ　ｒｅｌａｔｅｄ　ｗｉｔｈ　ｔｈｅ　ｄａｔａ　ｃｏｌｌｅｃｔｉｏｎ　ｐｒｏｂｌｅｍｓ．Ｔｈｕｓ，ｍｏｒｅ　ａｎｄ　ｍｏｒｅ　ｒｅｓｅａｒｃｈｅｒｓ　ｔｅｎｄ　ｔｏ　ｆｉｎｄ　ｔｈｅ　ｍｅｔｈｏｄｓ　ｗｉｔｈｏｕｔ　ｔｈｅ　ｐｒｉｖａｃｙ　ｄａｔａ．Ｉｎ　ｔｈｉｓ　ｐａｐｅｒ，ｗｅ　ｓｕｇｇｅｓｔｅｄ　ｔｈｅ　ｇｒｏｕｐ　ｉｎｔｅｒｅｓｔｓ　ｇｒａｍ）ｏｆ　Ｃｈｉｎａ　ｕｎｄｅｒ　Ｇｒａｎｔ　Ｎｏ．２００７ＣＢ３１０８０４，ａｎｄ　ｔｈｅ　Ｃｈｉｎａ　Ｐｏｓｔｄｏｃｔｏｒａｌ　Ｓｃｉｅｎｃｅ　Ｆｏｕｎｄａｔｉｏｎ　ｕｎｄｅｒ　Ｇｒａｎｔ　Ｎｏｓ．２００９０４６０１０７．２０１０００３７９４．Ａｌ１　ｏｆ　ｔｈｅｓｅ　ｐｒｏｊｅｅｔｓ　ａｒｅ　ａｒｏｕｎｄ　ｔｈｅ　ｐｒｏｂｌｅｍ　ｏｆ　ｓｅｒｖｉｃｅｓ　ｏｎ－ｄｅｍａｎｄ，ａｎｄ　ｈｏｗ　ｔｏ　ｃｈａｒ—　ａｃｔｅｒｉｚｅ　ｏｒ　ｍｏｄｅｌ　ｕｓｅｒｓ’ｄｅｍａｎｄｓ　ｆｏｒ　ｔｈｅ　ｗｅｂ　ｓｅｒｖｉｃｅｓ　ｉｎ　Ｉｎ—　ｔｅｒｎｅｔ．　Ｉｎ　ｔｈｅｓｅ　ｐｒｏｊｅｃｔｓ，ａ　ｃｏｒｅ　ｐｒｏｂｌｅｍ　ｉｓ　ｈｏｗ　ｔｏ　ｍｉｎｉｎｇ　ｔｈｅ　ｈｕｇｅ　ｄａｔａ　ｆｒｏｍ　Ｗｉｋｉｐｅｄｉａ，ａｎｄ　ｈｏｗ　ｔｏ　ａｐｐｌｙ　ｔｈｅ　ｒｅｓｕｌｔｓ　ｉｎｔｏ　ｔｈｅ　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋ　ａｎｄ　ｓｅｒｖｉｃｅｓ　ｏｎ　ｄｅｍａｎｄ．Ｉｔ　ｉｓ　ｏｂｖｉｏｕｓ　ｔｈａｔ　ｔｈｅ　ｉｎ—　ｔｅｒｅｓｔｓ　ｏｆ　ｕｓｅｒｓ　ｃａｎ　ｉｍｐｒｏｖｅ　ｔｈｅ　ｑｕａｌｉｔｙ　ｏｆ　ｓｅｒｖｉｃｅｓ　ｏｎ　ｄｅｍａｎｄ．　ｍｉｎｅｄ　ｆｒｏｍ　ｔｈｅ　ｐｕｂｌｉｃ　Ｗｉｋｉｐｅｄｉａ　ｃｏｏｐｅｒａｔｉｏｎ　ｄａｔａ，ｗｈｉｃｈ　ｃａｎ　ｂｅ　ｕｓｅｄ　ｔｏ　ｒｅｐｌａｃｅ　ｔｈｅ　ｐｒｉｖａｃｙ　ｄａｔａ　ｃｏｌｌｅｃｔｉｏｎ．Ｗｅ　ｒｅｄｕｃｅ　ｔｈｅ