《数据挖掘课程论文》由会员分享，可在线阅读，更多相关《数据挖掘课程论文（22页珍藏版）》请在金锄头文库上搜索。
1、面向社会网络分析的数据挖掘方法研究摘要随着信息技术的发展，越来越多的社会关系数据被收集。如果能够有效地对 它们进行分析，必将加深人们对社会学的理解，促进社会学的发展。但是数据量 的增大同时对分析技术提出了巨大的挑战。如今社会网络的规模早已超出了原有 分析手段的处理能力，必须借助更为有效的工具才能完成分析任务。数据挖掘作 为一种帮助人们从海量数据中发现潜在有用的知识的工具，在很多领域发挥了重 要的作用。社会网络分析又称为链接挖掘，是指用数据挖掘的方法处理社会网络 中的关系数据。本文对数据挖掘和社会网络分析中的一些方法进行了介绍并对数 据挖掘算法在社会网络分析的应用进行了概括。关键词：设会网络分析
2、；数据挖掘；链接挖掘RESEARCH ON SOCIAL NETWORK ANALYSIS-ORIENTED DATAMINING METHODABSTRACTWith the development of information technology, more and more social relation data have been collected. Effectively analyzing these data will help the human understand the properties of society, and promote the developme
3、nt of sociology. However, the growth of data presented a huge challenge to the analysis method. Now the scale of social network has already gone beyond the scope of the handling capacity of the original analytical methods. Some more effective tool should be utilized to complete the analysis tasks. D
4、ata Mining helps people find a potentially useful knowledge from Massive Data, and play an important role in many fields. Social network analysis is also called linking mining. It use methods of data mining to deal with relational data in social network. This paper briefly introduces some methods in
5、 the areas of data mining and social network analysis, and generalizes the application of data mining using in social network analysis.KEY WORDS： social network analysis; data mining; link mining目录1. 引言 42. 社会网络和数据挖掘方法介绍 52.1 社会网络分析方法 52.1.1 用户用户网络模型 52.1.2 用户事件网络模型 72.2 数据挖掘方法 82.2.1 关联规则分析 92.2.2
6、聚类分析 103. 数据挖掘在社会网络分析中的应用 123.1 基于相似度度量方法 123.2 基于统计的方法 153.3 基于频繁模式挖掘的方法 184.总结 181.引言传统的机器学习处理的社会学中的对象是单独的数据实例，这些数据实例往 往可以用一个包含多个属性值的向量来表示，同时这些数据实例之间假设是统计 上独立的。例如要训练一个疾病诊断系统，它的任务是诊断一个被试者是否患有 某种传染病。传统的学习算法用一个向量来表示一个被试者，同时假设两个被试 者之间的患病情况是相互独立的，即知道一个确诊病人对于诊断其他被试者是否 患病不能提供任何帮助。直观经验告诉我们这种假设是不合理的。直到二十世纪
7、 30年代，Jacob More no和哈佛大学的一组研究人员分别提出了社会网络模型来 分析社会学中的现象和问题。现代社会学主要研究现代社会的发展和社会中的组 织性或者团体性行为。社会学家发现社会实体之间存在着相互的依赖和联系，并 且这种联系对于每个社会实体有着重要的影响。基于这样的观察，他们通过网络 模型来刻画社会实体之间的关系，并进一步用来分析社会关系之间的模式和隐含 规律。为了更好的研究这个问题，他们试图用图结构来刻画这种社会网络结构。 一个社会网络由很多节点（n ode）和连接这些节点的一种或多种特定的链接（li nk） 所组成。节点往往表示了个人或团体，也即传统数据挖掘中的数据实例，
8、链接则 表示了他们之间存在的各种关系（relation）,如朋友关系、亲属关系、贸易关系、 性关系等。由于数据收集方式的限制，早期的社会网络局限于一个小的团体之内，往往 仅包含几十个结点。借助于图论和概率统计的知识，人工处理可以从中分析出一 些简单的性质和模式。但是，随着现代的通信技术的发展，越来越多的数据被收 集和整合在一起，建立一个大的社会网络成为可能。例如，可以通过电子邮件的 日志来建立使用者之间的联系网络，或者通过网络日志及网络通讯录等方式将用 户提交的联系人信息建立社会网络。所以，现在的社会网络规模比早期网络庞大， 通常包含几千或者几万的结点，甚至有多达百万个结点的网络。面对这样庞大
9、复 杂的网络，简单的数学知识和原始的人工处理已经不可能进行有效的分析。数据 挖掘是从巨量数据中发现有效的、新颖的、潜在有用的并且最终可理解的模式的 非平凡过程。数据挖掘就是为了解决当今拥有大量数据，但缺乏有效分析手段的困境而出现的研究领域。目前，已经在包括生物信息学，自然语言处理等许多方 面发挥了巨大的作用。与传统的数据挖掘只关注数据实例不同，社会网络分析对链接同样关注。从 数据挖掘角度，社会网络分析又称为链接挖掘(link mining)。通过对链接的挖掘 我们可以获得关于实例更丰富(如某个实例在整个网络中的重要性)、更准确(如 预测某个实例所属的类别)的关系数据(relatio nal d
10、ata)。社会网络分析是关系数据挖掘的主要应用。关系数据挖掘的发展为社会网络 分析提供了更有力的工具，促进了社会网络分析的发展。本文分析了社会网络分 析数据的方法以及任务和需求，介绍了几类适于社会网络分析的数据挖掘算法。2.社会网络和数据挖掘方法介绍2.1 社会网络分析方法社会网络分析是一套用来分析多个个体通过相互联系构成的网络的结构，性质以及其他用于描述这个网络的属性的分析方法的集合。如社会网络分析方法提 供了根据网络中节点的联系紧密情况将网络分层的方法，网络中节点相互作用模 式识别，将网络分块，给用户评级，信息扩散，对社会网络提供图形描述，中心 度的分布等。下面我们介绍社会网络分析最重要的
11、两个模型，用户用户网络 模型和用户事件网络模型2.1.1 用户用户网络模型在网络模型中，我们把用户作为节点，用户之间的联系作为节点之间的连线， 构成一个社会网络。用户之间产生联系，一个用户对另一个用户的连接可以是一 次也可以是多次，并且是带有方向的，因此这是一个带有数值的有向网络。如果 用户A指向用户B,则产生弧AB,这条弧由A指向B,连接的次数就是这条 弧的值。整个网络中节点的数量用l表示。每个结点用v.表示。i图2.1用户用户网络示意图图2.1给出了一个由6个用户构成的简单的“用户一一用户网络”示意图。 图2.1中，结点v到v有1条弧，值为3,表示用户v与用户v有3次连接。1 2 1 2结
12、点v与v之间是双向弧，值为1和3,表示用户v与用户v有1次连接,2 323表示用户v与用户v有3次连接，以此类推。3 2威望度计算：在一个有向带值得网络中，一个结点的威望度是指这个结点的 入度与所有节点的入度和的比值6。PdW = Xi-(式 2.1) X.i -1式2.1是威望度的计算公式，其中x表示节点v的入度。入度是指所有指i-i向该结点的弧上的值的和。如图2.1中，节点v的入度为2+3=5，威望度为35/14=0.385；节点v的入度为1,威望度为1/14=0.077；结点v的入度为0， 6 1威望度为0/13=0。一个结点的威望度越高，该结点所代表的用户被其他用户连 接的次数就越多，
13、该用户在网络模型所处的位置就越重要。计算表明在节点数量 巨大的网络中所有的节点符合幂律分布而不是随机网络中的正态分布钟形曲线。 我们将其记作N(k)，根据公式N(k) k-r，其中参数Y就是幕次数。例如，在计算 过的万维网文档上的外指链接后，其链接符合公式N(k) k-r，其中Y =2.57。中心度计算：在一个有向带值的网络中，一个结点的中心度是指这个结点的 出度与所有结点的出度和的比值6。CD（v.） = （式 2.2）1 x.1 +1式2.2是中心度的计算公式，其中x表示节点v的出度。出度是指所有该i+i节点指向其他结点的所有弧上的值的和。如图2.1中结点v的出度为2+3+2=7,1中心度
14、为7/14=0.538，结点v的出度为1+1+1=3,中心度为3/14=0.154。一个3结点的中心度越高，表示该结点连接别人的次数就越多，说明该用户在网络模型 中越活跃。2.1.2用户事件网络模型在网络模型中，用户之间除了连接这种联系以外，用户还因为同时参与一个 事件而联系，而事件也因有相同的用户参与而联系。在模型中，通过用户与事件 之间的联系构建网络拓扑图，假如用户v参与了事件e,则在v和e之间连线， 因为我们这里主要研究事件传播的广度，因此我们不考虑用户对同一事件的多次 参与，又因为这种联系只在两种不同类型的对象（用户和事件）之间存在，所以 方向已经没有意义，因此这是一个不带值的无向图4
15、。图2.2用户事件网络示意图图2.2给出了一个由6个用户和5个事件构成的简单的“用户一一事件网 络”示意图。图中，左边的6个圆球表示6个用户，由v标出，i从1到6；右i边的5个圆球表示5个事件，由e标出，i从1到5。图中的线连接用户与事件,i如v到e有一条连线，表示用户v参与了事件e,以此类推。1 1 1 1事件的中心度计算：事件的中心度是指参与该事件的人数与总人数个数的比值。xCE(e.)(式 2.3)E i n式(2.3 )为事件中心度计算公式，其中x表示参与e事件的用户，n表示该ii图中总的用户个数。如图2.2中e事件的参与人数为3,事件中心度为3/6=0.5。2事件之间的联系。在图2.2中，事件之间没有直接联系，但是却存在间接联 系，我们认为拥有相同的用户参与的两个事件之间存在联系，拥有相同用户的数 量越多则两个事件联系越紧密。如，事件e和e拥有一个相同的用户(v),则1 2 1它们的联系强度为1;事件e和e拥有2个相同的用户(v v ),则它们的联233,4系强度为2。通过这种方式建立只有事件之间的联系而把用户从网络中剥离出来 得到新的“事件事件网络”模型，可以很方便的找出联系最紧密的事件。 2.2 数据挖掘方法数据挖掘(Data Mining)就是从大量的、不完全的、有噪声的、模糊的、随 机
