数据挖掘技术在社交关系分析中的应用

郑诗慧+李卓+贾蕊+王杉

摘要：该文对社交关系和数据挖掘的方法进行了介绍和分析，同时也结合具体实例说明了数据挖掘技术在社交关系分析中的应用。

关键词：数据挖掘、社交关系

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）04-0029-03

1 概述

我们生活在一个信息过量的数据时代。每天来自各行各业的数据都会不断地注入到我们的计算机网络或各种存储设备中，而我们要做的就是从这些海量的数据里发现有价值的信息，并把这些信息转换成有用的知识，从而提高信息利用率。

早期的数据收集由于受到种种方面的限制，通常收集范围仅局限在一个很小的范围内，而分析时一般只会采用人工的方式仅借助一些图和概率的知识从中分析一些很简单的信息，在数据量小的同时，信息有效性并不高。而现如今随着科技的发展，数据挖掘技术自然进化而来，它可以帮助我们更加便捷的分析更为庞大的数据。

现如今的社会上存在着这样的一种现象，每个个体之间都存在着相互的联系和依赖，并且这种关系对于个体有着很重要的影响。可以形象一点的说，社交关系中的个体就像互联网中的节点一样互相连接。所以，我们可以通过一种网络模型来描绘当前的社交关系，网络中的节点表示个体，连接则表示两个节点之间的关系。

本文结合具体实例，通过分析社交关系，挖掘出某个时间段内，两个人之间相遇、交友、兴趣、生活规律等相遇的概率，将这些数据记录下来进行研究，从而说明数据挖掘在社交关系分析中的应用。

2 数据挖掘方法

数据挖掘，通常又称为数据库中发现知识（Knowledge Discovery in Databases， KDD），就是从大量的、不完全的、模糊的、随机的实际应用数据中，提取隐含在其中的，人们事先不知道的，但是又潜在有用的信息和知识的过程[1]。

常用的数据挖掘方法有四种：关联规则分析（Associations）、聚类分析（Clustering）、分类分析（Classifiers）、序列模式分析（Sequential Patterns）。这里主要介绍前两种方法。

1） 关联规则分析（Associations）[1]

关联规则是形如X→Y的蕴涵式，其中X和Y分别称为关联规则的先导和后继，关联规则XY存在支持度和置信度。而且，挖掘关联规则的问题也可以归结为挖掘频繁项集。

一般而言，关联规则的挖掘分为两步：一是找出所有的频繁项集，这些项集的每一个频繁出现的次数至少与预定义的最小支持计数一样；二是由频繁项集产生强关联规则，这些规则必须满足最小支持度和最小置信度。

关联规则的主要算法是Apriori算法，通过限制候选产生发现频繁项集。其利用循环渐进的方式，找出数据库中项目的关系，以形成规则。过程大致分为两步，一为连接步（类似于矩阵运算），二为剪枝步（去掉没用的中间结果）。

2） 聚类分析（Clustering）[1]

聚类分析简称聚类，是一个把数据对象（或观测）划分成子集的过程。每个子集是一个簇（cluster），使得簇中的对象彼此相似，但与其他簇中的对象不相似。由聚类分析产生的簇的集合称作一个聚类。此种语境下，相同的数据集上，不同的聚类方法可能产生不同的聚类。

聚类的方法通常有K均值算法、凝聚层次聚类、DBSCAN。K均值算法是基于原型的，划分的聚类技术，它试图发现用户指定个数（K）的簇。凝聚层次聚类，首先将每一个点作为单点簇，然后重复的合并两个最近的簇，直到产生单个的，包含所有点的簇。DBSCAN是一种产生划分聚类的基于密度的聚类算法，簇的个数由算法自动地确定。低密度区域中的点被视为噪音而忽略，因此，DBSCAN不产生完全聚类。

3 社交关系分析

1）用户和用户之间的关系

在社交关系中，可以把每个用户看作一个节点，用户之间在某种条件下只要相遇过就算作有联系，这种联系作为节点之间的连线。用户之间的联系可以是多次的，也可以是零次的，并且一个用户可以与多个用户进行联系。

图1是由5个用户构成的一个简单示意图，由图中可以看出，结点v1到v2有一条单向弧，值为3，说明v1用户与v2用户有3次联系。结点v2到v3是一条双向弧，值为1和2，说明v2用户和v3用户有1次联系，v3用户和v2用户有2次联系，等等。

入度是指所有指向该结点的弧上的值的和。而在一个有向带值的联系图中，一个结点的入度与所有结点的入度和的比值α越高，就说明该用户与其他用户的联系越密切，该用户所处的地位就越重要。如图1中，结点v1的入度为0，则α为0/12=0；结点v4的入度为1，则α为1/12=0.083；结点v2的入度为7，则α为7/12=0.583，等等。

出度是指所有该结点指向其他结点的所有弧上的值的和。同理，在一个有向带值的联系图中，一个结点的出度与所有结点的出度和的比值β越高，就说明该用户在联系中越活跃。如图1中，结点v1的出度为5，则β为5/14=0.357，结点v5的出度为2，则β为2/14=0.143，等等。

2）用户和事件之间的关系

在社交关系中，用户之间除了因为相遇而有联系以外，还会因为做了同样的事情，有着同样的兴趣爱好，生活规律而产生联系。这里主要考虑的是用户之间因为做了同一件事情而产生的联系，所以不考虑一个用户某件事情做了多少次。

图2是由5个用户和3个事情构成的一个简单示意图，图中的线连接用户与事情，由图中可以看出，v1用户分别到e1和e2事情上有连线，说明用户v1参与了事情e1和e2，等等。

通过图2中，每个事情的用户参与人数和总人数个数相比较，我们不难发现，在e3事情上有v2，v3，v4，v5用户参与，且是3个事情当中，参与的人数最多的一个事情，这就说明了这四位用户之间因为做了同样的事情，有着相同的兴趣爱好而产生了联系。

4 实例

1）数据说明

本文在研究时选取的数据集[2]来自美国麻省理工学院的一个实验室。该份数据在进行挖掘时，随机选取了94个人，包括教师和学生，包括男性和女性。然后通过使用手机安装软件来记录并发送一些相关的需要收集的数据内容。整个收集过程持续了大概九个月，所收集的数据包括位置、手机的活动（通话、短信、游戏、充电状态等）以及每个人的自我报告等等。

2）基于相似度度量方法进行数据挖掘

K邻近算法，某些聚类算法都是基于相似度度量的。同一数据集，不同任务，最佳相似度往往也不同，一个合适的相似度度量会因为属性多，目标任务不明确而很难选取[1]。但是，当找到合适的相似度度量之后，这类方法便很好解释了。

如果通过数据分析发现某两个用户在一些事情上有很大的交集，那么他们将来成为朋友的可能性会远远大于两个没有事情交集的用户。同理，有着同样交友圈的两个人也会比其他人有更大的机会成为好朋友。再或者，两个本身没有交集的人，因为共同认识一个好友，或者有着相同的兴趣爱好，而在将来的某一天产生交集也成为好朋友。

图3和图4就是本文所研究的数据集中，关于用户通信次数与相遇次数之间的一个关系。图3中，坐标横轴是通信次数，范围是0到300次，纵轴是相遇次数，范围是0到4000次。从图中不难发现，大部分的点都落到了横轴0到50，纵轴0到500这个区间内，不利于查看。因此，为了更加直观方便地看到通信次数与相遇次数之间的关系，图4是图3中的点的密集范围的一个放大，横轴通信次数的范围是0到150次，纵轴相遇次数的范围是0到1000次。

通过研究数据所得到图3和图4中不难发现一个趋势，当两个用户之间交流沟通的次数越少，两个人的相遇碰见次数也就越低。这样的两个人很难成为好朋友，因为他们在关于某一个事情上并没有多大的交集，导致之间并没有多少沟通。反之，当两个用户交流沟通的次数越多时，两个人的相遇碰见次数也就越高。这样的两个人成为好朋友的可能性非常高，因为他们之间会经常为了共同的一个事情而进行交流沟通以及见面。当然，也会有一些比较例外的时候，比如两个几乎没联系的人，但是相遇次数却非常高，这可能是因为他们每天坐在同一间教室里上课，或者同一辆公交车回家等等。

5 观点及结论

数据挖掘技术是现如今我们在分析大量数据时不可或缺的，也是在分析社交关系这个庞大的数据集时不可或缺的。利用挖掘技术在分析数据时，可以有效地提高信息利用率，也有助于我们今后在做一些社交分享类系统时，提供一些非常有用的信息，提高效率。

参考文献：

[1] 韩家炜，裴健. 数据挖掘概念与技术[M].范明，孟小峰，译.北京：机械工业出版社，2012.

[2] Nathan Eagle，PhD. The Reality Mining Data README[EB/OL].http：//realitycommons.media.mit.edu.