防灾科技学院数据挖掘考点总结李忠

防灾科技学院数据挖掘考点总结李忠防灾科技学院数据挖掘考点总结李忠 社交网络新一代数据挖掘的金矿随着 Facebook 的上 市，社交网络再次成为人们关注的焦点。 与传统的论坛、博 客相比，社交网络是虚拟世界与现实 世界的桥梁，在互联网上将现实生活中人与人之间的关系建 立起来。 从社交网络的分类来看， Facebook、 Twitter、LinkedIn 分别代表三种不同的社交网络。 Facebook 是基于朋友之间强关系的社交网络，有助于朋 友之间关系的维系和改 善；Twitter 是基于单向关注的弱关 系的社交网络，这样的网络有利于塑造意见领袖和消息的传 播； LinkedIn 是面向商务人士的职业社交网络，帮助 用户利 用社交关系进行商务交流以及求职招聘。 三种社交网络每天都会产生大量的用户数据（UGC， User Generated Content） ，并且具有空前的规模性和群体性， 吸引着无数研究者从无序的数据中发掘有价值的信息。 这就像概率统计中经常举的投硬币算其正反面概率的例 子，从几次的投掷结果中很难看到规律，但通过几万次的大 量投掷实验，便很容易看出正反面的出现次数几乎相等的规 律。 社交网络上产生了大量的规模化、群体化 的数据，吸引 了包括计算机科学、心理学、社会学、新闻传播学等领域专 家和学者对其进行研究和探索，希望能够借助更强的社交网 络的分析和处理能力发现更多人 类尚未探索出的规律。 对于社交网络的分析和研究范围很广，也存在着许多有 意思的研究课题。 例如， 在社 交 网络 中社 区圈子的 识别 （Community Detection） 、 社交网络中人物影响力的计算、信息在社交网络 上的传播模型、虚假信息和机器人账号的识别、基于社交网 络信息对股市、大选以及传染病 的预测等。 社交网络的分析和研究是一个交叉领域的学科，所以在 研究过程中，我们通常会利用社会学、心理学甚至是医学上 的基本结论和原理作为指导，通过人工智能领域中使用的 机器学习、图论等算法对社交网络中的行为和未来的趋势进 行模拟和预测。 社交圈子的识别 与一般的以内容为导向的论坛等社区 不同，社交网络最核心的就是人与人的关系，以及所形成 的社交圈子（社区） ，然而每个人根据自己的关系不同及兴 趣不同可以属于多个社交圈子。 在社交网络中我们发布的所有信息流，都是通过我们的 关系圈，逐 层向外传播的；我们收到的消息也直接来自我 们所关心的人，更外围的消息也必须逐层传播才能接触到终 端用户。 因此，如何发现社交圈子是社会关系网络分析中一 个很 重要的基础性的研究。 社交圈子示例如图 1 所示。 图 1 基于 OSLOM 算法的社区发现效果图 利用计算机 来处理社交网络往往会将整个社交网络看作是一个图的结 构，每个用户就是 图中的节点，人与人之间的关系就是节 点之间的边，根据不同类型的社交网络，所构成的图可以是 有向图也可以是无向图，关系的强弱也可以利用边上不同的 权重来 体现。 对于社交圈子的发现算法来说，社交圈子的质量依赖于 圈子内成员的关系的紧致度以及不同圈子间的分离度。 但对于数以亿计的节点来说，目前的圈子发现算 法还很 难处理特大规模的数据，因此很多研究者提出了启发式的方 法去减少程序处理的复杂性，对最终结果进行近似的求解。 然而实际的社交圈子是一个更为复杂的网络，因为用户 会具有多种兴趣，可以属于多个社交圈，发现这种圈子的 研究也被称为重叠社区的发现。 一种比较简单的启发式方法是，以网络中度很大的节点 作为初始的圈子，然后把对圈子贡献最大的邻接节点依次 加入到圈子中， 直到全局贡献度达到极值， 并形成一个圈子。 如果存在对多个圈子贡献度都很大的边界节点，则将其 加入到多个圈子中。 近期也有人提出了使用 标签传播（Label Propagation） 算 法以及粒子群算法来解决重叠社区的发现算法。 社交圈子发现算法并不仅局限在用户主动建立起的关 系上，其更重要的价值在于对用户 非显性的潜在关系发现。 从社交圈子发现的结果中，我们能够更加清楚地看出属 于一个圈子的人群。 当然，社交圈子也有多种划分方式，例如关系型社交圈 子、兴趣 型社交圈子等。 在算法中以亲密度为首要指标和以兴趣为首要指标，也 会得到不同的社交圈子划分。 由此引申出的一个问题是，线上的圈子与线下的真实社 交圈子是否是一致的当两个人在社交网络中互动很频繁 时，他们在线下是否也是真实的好友从算法的角度来说，这 是个很难解决的问题，但如果我们换一个角度来思考这个问 题，想想我们的线 下联系方式，如果 A 跟 B 互相拥有对方 的手机号，那他们是线下真实好友的可能性就非常大了。 包括飞信、米聊、微信等产品，如果真的能够做成基于 手机通讯录的 社交网络，我们就可以通过异构的社交网络 对社交圈子进行综合性的判断，其价值不可估量。 影响力的计算 在社交网络中，意见领袖因为其在网络 上强大的影响力会对信息的传播，以及普通用户的行为造 成巨大的影响。 以新浪微博为例，最直观的影响力表现之一就是加 V 认 证的名人， 发一条正在吃饭的微博， 也能得到数百次的转发， 然而对于一般用户，一 条微博的转发次数能上两位数，便 足以为之欢呼雀跃了。 因此，与现实社会一样，社交网络中的人也存在不同的 阶级和不同的影响力。 然而影响 力应该如何来衡量和计算呢我们前面已经提 到，计算机在处理社交网络时，往往使用图的结构，这与搜 索引擎中的结构相一致，如表 1 所示。 因为在搜索引擎中， 图的节点是网页，边是链接，然而 搜索引擎中的 PageRank 算法是对网页进行排序的算法。 如果我们将 PageRank 使用在社交网络上，就可以对人的 影 响力进行迭代的计算了。 除了 PageRank 算法外，还有 W-entropy 等算法也被应用 在社交网络的影响力计算当中。 表 1 社交网络与搜索引擎对图结构的不同定义 然而对 于每个人来说，其在不同领域的影响力也是不一样的。 例如，李开复的影响力主 要在科技领域，黄健翔的影响 力在体育领域，薛蛮子的影响力主要在投资和公益的领域。 因此如何评价一个人在不同领域的影响力也是一个很重 要的问题，有学者提 出了基于主题级别（Topic Level）的影 响力评价模型 TAP（Topic Affinity Propagation）来尝试解决 这个问题，该算法应用在大规模社交网络数据中显现出了较 好的效果。 在国外，Famecount、Klout 等公司设计了算法对社交网 络中每一个人的 影响力进行打分。 有些公司甚至出现了根据个人网络影响力的不同，在现 实生活中提供差异化服务的模式，例如，香港国泰航空对 Klout 打分不低于 40 分的用 户，可以享受机场贵宾休息室。 虽然该行为也遭到不少人质疑，认为这是“势利”的做法， 不过也可以将其看作是对网络影响力应用在商业模式上的 一种新型探索。 在国内， 新浪的微数据和 Miu 也在微博的影响力计算中 做出了一些探索，目前国内在该领域还有较大的发展空间。 信息传播的建模 在社交网络上，每个人都是个自媒体。 与传统媒体依靠内容作为传播主题的形式有所不 同，社 交网络上的信息传播，更加依赖于