AI 年度盘点与2025发展趋势展望,50+案例解析亮相AICon 了解详情
写点什么

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

  • 2012-02-20
  • 本文字数:3591 字

    阅读完需:约 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 )关注我们,并与我们的编辑和其他读者朋友交流。

2012-02-20 00:0012700

评论

发布
暂无评论
发现更多内容

显示器选购总结-戴尔2705QM-明基PD2700U

李印

总结 经验分享

技术盘点:2022年云原生架构趋势解读

阿里巴巴云原生

阿里云 架构 云原生 趋势

Lyft微服务研发效能提升实践 | 2. 优化快速本地开发

俞凡

研发效能 大厂实践 2月月更 lyft

技术盘点:消息中间件的过去、现在和未来

阿里巴巴云原生

阿里云 云原生 中间件 消息队列 EventBridge

AIGC的“含科量”与“含资量”

脑极体

The Rust Programming Language

Joseph295

Kubernetes集群仪表盘dashboard&Kuboard安装Demo

山河已无恙

Kubernetes 2月月更

也许我们可以用另一种角度与观点看待世界所发生的事情,让你有所解答。

叶小鍵

电子书《大型组织深入推广零代码应用平台的行动指南》正式发布!

明道云

鸿蒙学习笔记之使用 XML 方式创建布局

宇宙之一粟

鸿蒙 java UI 2月月更

gopher成长之路(四):GO开发工程师写QT

非晓为骁

个人成长

基于51单片机室内灯光控制系统

DS小龙哥

2月月更

Go 并发模式:管道和取消(译)

en

Go

Go反射的三大法则

linlh

反射 元编程 Go 语言 2月月更

【C语言】一维数组

謓泽

C语言 2月月更 一维数组

设计消息队列存储消息数据的 MySQL 表格

swallowluo

架构实战营 #架构实战营 「架构实战营」

LabVIEW生成应用程序(exe)和安装程序(installer)

不脱发的程序猿

LabVIEW 生成应用程序(exe) 安装程序(installer)

AI赋能安全技术总结与展望| 社区征文

herosunly

人工智能 新春征文 2月月更

DOM 精通了?请问 Node 和 Element 有何区别?

编程三昧

JavaScript 前端 DOM 2月月更

kube-scheduler源码分析(1)-初始化与启动分析

良凯尔

源码 Kubernetes 容器 源码分析 #Kubernetes#

RPA进阶(一):走近 RPA 世界

No Silver Bullet

RPA 机器人流程自动化 2月月更

工作想法小计2/7 - 2/11

非晓为骁

个人成长 开发 工作方式 Go 语言

技术盘点:2022 年容器、Serverless、可观测、服务网格有哪些值得关注的趋势?

阿里巴巴云原生

阿里云 Serverless 云原生 趋势 可观测

为什么需要单元测试?

蜜糖的代码注释

单元测试 后端开发 2月月更

韵达基于云原生的业务中台建设 | 实战派

阿里巴巴云原生

阿里云 云原生 业务中台 合作案例

技术盘点:云原生中间件的技术演进与未来趋势展望

阿里巴巴云原生

阿里云 云原生 中间件 趋势

战略规划和战略解码BLM+BEM

wood

bem 战略制定 300天创作 BLM

DOM 节点的克隆和导入

编程三昧

JavaScript 前端 DOM 2月月更

消息队列存储消息数据的表结构

皓月

「架构实战营」

LabVIEW跳转访问网页

不脱发的程序猿

LabVIEW 跳转访问网页

架构训练营 毕业设计

ren

大规模SNS中兴趣圈子的自动挖掘_《架构师》月刊_张俊林_InfoQ精选文章