BT

如何利用碎片时间提升技术认知与能力? 点击获取答案

大规模SNS中兴趣圈子的自动挖掘

| 作者 张俊林 关注 1 他的粉丝 发布于 2012年2月21日. 估计阅读时间: 12 分钟 | 如何结合区块链技术,帮助企业降本增效?让我们深度了解几个成功的案例。
 

一.为何要在大规模SNS中挖掘兴趣圈子

随着国外的facebook、twitter以及国内的人人、新浪微博等SNS及内容分享平台的逐步流行,如何从上亿的海量用户中自动挖掘兴趣圈子成为了一个有趣也非常必要的工作。所谓“兴趣圈子”,指的是在同一分享平台下,有着共同的兴趣爱好的用户群体,比如新浪微博里哪些用户是对云计算感兴趣的?他们是否形成了一个密切交互的圈子?对这些信息的挖掘是很有趣也很有实际用处的。

如果能够从海量用户中通过自动手段挖掘出一个个的兴趣圈子,对于很多具体应用来说是非常重要的基础数据,比如可以利用用户所属兴趣圈子进行感兴趣人物推荐,或者根据所属圈子的群体特性分析用户的个人兴趣点等,所以在SNS平台下,如何对海量数据自动进行兴趣圈子挖掘是个非常有用的基础功能。

二.如何挖掘兴趣圈子

现在的问题是:给定海量用户,如何才能挖掘出具有相似兴趣的圈子?我们基于微博用户的互动信息,构建了一整套兴趣圈子挖掘算法,并取得了较好的挖掘效果。如果把每个用户想象成一个巨大的图中一个节点,如果用户A对用户B有互动行为(转发,评论等),我们可以在用户A和用户B之间建立一条有向边,通过这种方式可以构建出有上亿节点,几十亿边的巨大的有向图。挖掘兴趣圈子就是在这样的巨图中进行的。我们把兴趣圈子挖掘转换为一个图切割问题的具体应用。图1是这个思路的简化图示例。

1 兴趣图例子

2.1 图切割问题

图切割问题本质上是一个聚类问题,几乎所有聚类算法的基本思想都是相近的:给定一批数据,自动对数据进行聚类,使得聚合到同一类别的数据之间比较相似,而不同类别之间的数据差异较大。图切割问题也符合这个定义,等于是将图中节点进行聚类,把密集相连的一批节点聚合到一起,而连接比较稀疏的节点尽可能划分到不同的类别中。

如果用相对形式化的语言来描述的话,图切割问题就是:给定n个点(x1, x2…,xn),聚类的目标是将这n个点分成k个簇,使得同一簇中的数据点比较相似,不同簇间的数据点比较相异。如果按照节点之间的兴趣相似度构建关系图G(V, E),问题就转化为了在图G上做划分,将图G分成k个子图A1,A2,…Ak,使得划分后子图内包含边的总权值尽可能高,而子图之间边的权重尽可能小。在图1所示的例子中,标为相同颜色的节点可被视为聚合到相同子图中,边的权值直观表示为边的长度,即边越长,两个节点距离越远,即其相似性越小,也就是说其边的权值小。

图切割算法有很多,比如min-cut,min-max cut,ratio cut等等,我们采用了谱聚类算法来挖掘用户兴趣圈子。

2.2谱聚类算法

谱聚类算法和很多其他距离算法相比有很多优点,下文会详述此点,同样的,谱聚类也适合解决图切割问题。

谱聚类有个比较有趣的特性,即这个算法可以将图切割问题转换为求由图形成的矩阵的特征值和对应的特征向量问题,这样就把图切割问题转换为矩阵特征值求解及在其基础上的聚类问题。

2 谱聚类算法流程

图2是利用谱聚类进行兴趣圈子挖掘的算法流程示意图,首先我们获得用户之间的互动数据,由于谱聚类只能处理无向图,而用户之间的互动数据是有向的,所以首先根据一定规则将有向图转换为无向图,之后就形成了所有用户的兴趣相似性图。根据谱聚类算法要求,将这个相似性图转换为拉普拉斯矩阵,然后对这个矩阵求其前K个特征值及其对应的特征向量,求解前K个特征向量s1,s2,…,sk,组成矩阵S[n][k](n为用户编号),这样就将一个原本是n*n的矩阵转换为小很多的n*k矩阵,对S按行进行Kmeans聚类,每一行对应相似兴趣图中一个节点。其最终聚类结果就是谱聚类最终的输出结果。

之所以采取谱聚类来解决这个问题,源于这个算法本身具有的一些优点,比如:

  1. 谱聚类具有坚实的理论基础:图谱理论
  2. 谱聚类不含凸球形数据分布的隐性假设,而常见的很多聚类算法比如KMeans, EM算法都存在这一假设。比如对于图3所示的例子中,谱聚类的聚类效果比较好。

3 非凸球形数据

由于谱聚类具备独特的优点,所以近来应用非常广泛(语音识别、文本挖掘等),但是谱聚类的计算复杂度还是较高,所以面对海量数据,如何能够快速计算是个问题。

为了能够处理上亿的海量数据,我们主要采取了两项措施来对原始算法进行改造,首先是利用MPI平台构建分布式计算系统,对于这种计算密集型迭代式应用,通常hadoop平台被认为是不太合适的,所以通过构建MPI分布式平台来加快数据的分布以提升计算速度。

第二项主要改进措施是将谱聚类由平面型聚类(flat)改造为层次聚类(hierarchy),其基本思想也很简单,即通过多次谱聚类迭代,首先将一个巨大的图划分为较少数的密集子图,然后针对每个密集子图再次迭代使用谱聚类来递归地将其划分为较小的密集子图,通过几个层级的切割,也可以有效增加分布式计算效果并大大提快整体运行效率。

当然,除了以上两项主要改进措施,还包含一些相对细小的改进,在此就不赘述细节了。

2.3应用谱聚类在SNS中挖掘兴趣圈子

正像上文所述,大规模SNS用户中挖掘兴趣圈子的问题可以进一步抽象为用户兴趣图的一个图切割问题,我们通过对谱聚类处理大规模数据进行了技术改进后,使得这项技术可以在多机并行环境下较快地处理上亿规模数据的图切割,在兴趣圈子自动挖掘方面既实现了较好的挖掘效果,又能够使得算法处理真实世界的大规模数据,使其在现实中可行而非仅仅停留在小规模数据处理的学术研究阶段。

下面给出三个使用上述技术在新浪微博平台挖掘出的兴趣圈子,因为实际的兴趣圈子很大(大部分包含几十到几百个节点),所以只列出了兴趣圈子的一部分,从这些例子可以看出其效果还是比较理想的。

用户微博ID

微博名

身份说明

1197161814

李开复

创新工场董事长兼首席执行官

1656232852

JackF2

创新工场豌豆实验室 联合创始人

1738208940

宓金华

创新工场魔图精灵项目负责人

1652837301

徐磊Ryan

布丁 创始人 CEO 原创新工场战略发展部总经理

1642333010

张亮

创新工场投资经理;Apple4us 发起人

1926746140

许红梅Grace

创新工场人力资源部副总裁

1650741047

cuijin

创新工场市场总监崔瑾

1676705655

裘伯纯Benjamin

创新工场法务负责人裘伯纯

1751792424

dikanggu

创新工场员工

1419563143

zouyu9631

创新工场员工

......................................

   

1 “李开复所属兴趣圈子

用户微博ID

微博名

身份说明

1656809190

赵薇

著名演员,代表作《画皮》《还珠格格》等

1829847745

一号立井

李亚鹏

1679085395

邓讴歌

太合麦田音乐制作人

1719232542

那英

内地流行乐天后

1629810574

veggieg

王菲

1496813600

老焦爱民

《杜拉拉升职记》制片人

1768955554

张扬张杨

著名导演

1262945510

廖凡

演员廖凡

1919269943

王一涵

北京中艺博文化传播有限公司董事长兼总经理

1497323383

磨刀哎呦霍霍

编剧霍昕

..............................

   

2 "赵薇"所属兴趣圈子

用户微博ID

微博名

身份说明

1922397344

白硕sse

上海证券交易所总工程师,IR与NLP专家

1937618377

林鸿飞

大连理工大学电子信息与电气工程学部 副部长

1684953923

关毅的围脖

哈尔滨工业大学计算机学院教授、博士生导师关毅

1936526225

王斌_ICTIR

中国科学院计算技术研究所副研究员,博士生导师王斌

1808067361

ITNLP

哈尔滨工业大学智能技术与自然语言处理(ITNLP)研究室

1970879995

孙茂松

清华大学计算机科学与技术系教授、中国中文信息学会副理事长孙茂松

1788077877

张颖峰

上海载和网络科技有限公司 研发总监

1340489195

韩先培

中国科学院软件所助理研究员

1497035431

梁斌penny

清华大学计算机科学与技术系在读博士;《走进搜索引擎》《深入搜索引擎》作者,THUIRDB的Coder。

1064649941

张俊林say

《这就是搜索引擎:核心技术详解》作者。本文作者。

.............................

   

3 “自然语言处理与信息检索兴趣圈子

通过大量的聚类数据分析,使用互动数据构建用户兴趣图得出的兴趣圈子大部分属于以下两种类型:一种类型是同事朋友圈子,这是因为线下关系迁移到网络的体现;另外一种比较常见的是兴趣类似的微博用户,比如NLP圈子,NOSQL圈子这种根据讨论技术确定的兴趣圈子等,这是由于共同关注相似话题并经常互动形成的。

三.结束语

大规模SNS与内容分享平台中如何自动挖掘兴趣圈子是个很有趣也非常必要的功能,现有公开文献很少提及超大规模数据如何实现自动挖掘的算法,大多数是在10万以下规模数据进行的研究工作,本文简述了在新浪微博平台通过改造的谱聚类进行的大规模兴趣圈子挖掘,实践表明取得了很好的挖掘效果。当然,现有系统还面临一些问题,比如属于硬聚类,即每个用户只能隶属于一个兴趣圈子,而实际上很可能一个用户属于多个兴趣组中,所以我们面对大规模数据的软聚类,也在进行进一步的研发与改进。

关于作者

张俊林,《这就是搜索引擎:核心技术详解》作者、新浪微博研发人员。


感谢张龙对本文的审校。

给InfoQ中文站投稿或者参与内容翻译工作,请邮件至editors@cn.infoq.com。也欢迎大家通过新浪微博(@InfoQ)或者腾讯微博(@InfoQ)关注我们,并与我们的编辑和其他读者朋友交流。

评价本文

专业度
风格

您好,朋友!

您需要 注册一个InfoQ账号 或者 才能进行评论。在您完成注册后还需要进行一些设置。

获得来自InfoQ的更多体验。

告诉我们您的想法

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

剧本不对啊 by zhou yi

李开复和赵薇所属兴趣圈子反掉了不是么

Re: 剧本不对啊 by 俊林 张

怎样反调了?

Re: 剧本不对啊 by 冯 希顺

好像是反了,赵薇的圈子里都是些学术界的人。

另外,我还是没看明白什么样的两个用户兴趣是相同的,有互动?能举个实际点的例子吗?

Re: 剧本不对啊 by 俊林 张

表的标题在表格下方。
两个节点的边代表兴趣,主要是根据用户互动形成的,比如A转发B或者评论收藏B的内容,则在A建立一条指向B的边并赋予权值。

Re: 剧本不对啊 by 于 彬

要多学习数据结构了,很像往这方面发展

Re: 剧本不对啊 by 于 彬

有向变具体如何建立?权值如何计算?这个可以详细讲讲吗

权值如何确定? by long robin

边的权值是如何确定的,根据算法自动生成,还是手动设置呢?

Re: 剧本不对啊 by Liu Zhen

你把表格和表格说明看错了

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

8 讨论

登陆InfoQ,与你最关心的话题互动。


找回密码....

Follow

关注你最喜爱的话题和作者

快速浏览网站内你所感兴趣话题的精选内容。

Like

内容自由定制

选择想要阅读的主题和喜爱的作者定制自己的新闻源。

Notifications

获取更新

设置通知机制以获取内容更新对您而言是否重要

BT