社会网络中的数据挖掘方法.doc

社会网络中的数据挖掘方法摘要：随着Web2.0技术的发展，社交网络在人们生活中所起的作用越来越大，社会网络分析越来越多得受到人们的重视，将数据挖掘的方法应用于社会网络分析成为数据挖掘研究的一个新的方向。如何从庞大冗杂的社会网络数据中挖掘出有用的信息成为广大学者研究的问题，并且当前关于社区挖掘的绝大多数方法都假定社会网络中只存在一种关系,挖掘结果并不完全符合用户的真实需求。因此，本文将从节点依赖性着手分析社会网络中数据之间的联系，从链接挖掘入手，分析得出关联分析和聚类分析这两种数据挖掘方法，并在此基础上简要探讨了多关系社会网络的数据挖掘方法。关键字：社会网络；数据挖掘；关联分析；聚类分析；多关系传统的机器学习和数据挖掘任务处理的对象是单独的数据实例，这些数据实例往往可以用一个包含多个属性值的向量来表示，同时这些数据实例之间假设是统计上独立的。然而在社会里，人与人不是简单的统计上独立的采样点，他们之间必然存在着联系和影响。忽视了这种联系会对数据挖掘效果带来很大的影响。为了解决这个问题，必须将数据实例之间的关系同时考虑进来，从而人们提出了社会网络的概念，试图用图结构来刻画这种社会结构。将数据挖掘的方法应用于社会网络分析是数据挖掘研究的一个新的方向。社会网络分析又称为链接挖掘（link mining），节点代表社会网络中个体或团体，链接表示了个体之间存在的各种关系（relation），如朋友关系、亲属关系、贸易关系、性关系等。通过对链接的挖掘我们可以获得关于实例更丰富（如某个实例在整个网络中的重要性）、更准确（如预测某个实例所属的类别）的信息。近年来，社会网络的个体影响力分析和关键成员挖掘在研究上获得了广泛的关注。通常认为，节点的社会地位可以用一种打分函数进行衡量，而这个打分函数的取值就可以被理解为节点在社会网络上的影响力或权威性。通常权威性函数值大的节点可以被理解为是网络中的重要个体，或关键成员。根据网络的不同，关键成员挖掘技术具有不同的应用背景。例如，Web搜索服务提供者期望通过分析链接结构，计算网页的重要性，从而为用户提供最贴近需求的搜索结果；在学术合作网络中，人们期望通过对合作结构和主题进行层次分析，从而发现合作模式和重要学者；在线社交网站中，通过主题对个体进行重要程度和个人兴趣进行分类，从而发现关键成员和意见领袖。类似的研究在学术研究、舆情分析、商业推广等领域上都有很好的应用。在社会网络中，每个个体都在网络结构中体现出了不同的社会影响力。例如，在微博网络中，同样的话题由不同的成员转载，受到的关注度往往会大不相同。是什么原因造成了这种影响力的差异呢？我们认为，个体的结构上下文，即个体在网络的链接结构中所处的位置，是造成个体在网络中受关注程度差异的重要因素。这种结构带来的差异性体现了网络中个体的社会特征，这也是社会网络中节点重要性排名算法与一般检索系统不同的重要原因。社会网络中的成员间往往在信息交换中体现出一种相互依存的特点。例如，微博中部分ID走红的原因其支持者的关注和评论，而某些ID的受到的关注则来源其自身发表内容的吸引力。相比起来，前者对网络表现出一种强烈依赖的特征，即如果将其支持者与其关系断开，其受关注程度必然会有大幅下降；由于后者依靠其自身内容吸引读者，网络结构对其的影响力则相对较小。这一现象是由社会成员在网络中体现出的社会性造成的。假设网络发生某种特定结构的变化，如果一个个体在结构变化时，其自身影响力也发生改变，则这种改变可以被理解成个体对其网络结构的依赖。分析节点对网络结构的依赖性和支持力在实际中拥有广泛的应用前景。社会网络中的每个成员有着或大或小的关联度，他们相互依存，但由于个体在网络的链接结构中所处的位置的不同，使得个体间关联度大小及影响力不同，通过对关联规则的分析可根据客户需求有效地进行数据挖掘。关联规则分析首先由Govind P. AGRAWAL等人提出，用来发现购物篮数据事务中各项之间的有趣联系。从那以后，进行了广泛的研究，以解决关联分析的概念，实现和应用问题。关联规则是形如X Y的蕴含表达式，其中 X 和 Y 是不相交的项集，即XY=。关联规则的强度可以用它的支持度和置信度度量。支持度确定规则可以用于给定数据集的频繁程度，而置信度确定Y和在包含X的事务中出现的频繁程度。关联规则的挖掘问题就是生成所有满足指定的最小支持度和最小置信度的关联规则。满足最小支持度和最小置信度的关联规则称为强关联规则。关联规则的挖掘是一个两部的过程：找出所有的频繁项集：这些项集出现的频繁性至少和与定义的最小支持计数一样。由频繁项集产生强关联规则：这些规则必须满足最小支持度和最小置信度。在关联规则中有涉及到的数据维度，可以分为单维关联规则和多维关联规则，比如：“啤酒尿布”就是单维关联规则，“性别=女职业=秘书”就是多维关联规则，Apriori 算法是关联规则分析中最经典的算法。社会网络中存在着一定的关键成员，而关键成员吸引其余与其具有相似性的成员聚类形成小组，通过聚类分析的方法也可有效地为客户提供潜在的需要数据，即数据挖掘。聚类分析将数据划分成有意义或有用的组。聚类分析仅根据在数据中发现的描述对象及其关系的信息，将数据对象分组。其目标是，组内的对象相互之间是相似的(相关的)，而不同组中的对象是不同的(不相关的)。组内的相似性越大，组间差别越大，聚类就越好。聚类的方法通常有 K 均值算法，凝聚层次聚类，DBSCAN。K 均值是基于原型的，划分的聚类技术。它试图发现用户指定个数(K)的簇。凝聚层次聚类是首先将每一个点作为单点簇；然后重复的合并两个最近的簇，直到产生单个的，包含所有点的簇。DBSCAN 是一种产生划分聚类的基于密度的聚类算法，簇的个数由算法自动地确定。低密度区域中的点被视为噪音而忽略。但现实的社会网络多为多关系的网络或异质网络，个体间往往存在着多种不同的关系，这些关系在不同任务中扮演者不同角色，因此，我们需要探讨得出一种更高效的数据挖掘方法来有效利用社会网络中的各种链接，从而满足用户的真实需求。我们可以从从降低噪声数据,提高算法效率和利用语义信息三方面对多关系社会网络进行社区挖掘方法的研究,为解决以上三方面内容提供了一种解决方案具体研究内容主要包括以下方面:首先,提出一种基于相关性分析的多关系社会网络社区挖掘算法(MCMABCA),解决了多关系社会网络影响挖掘结果正确性的噪声数据问题该方法将多关系社会网络中的社区挖掘问题转化为关系的选择和抽取问题,针对多关系的社会网络,基于相关性分析去除冗余关系,并结合用户查询抽取组合关系,根据这种组合关系挖掘社会网络中符合用户需求的社区结构。其次,提出一种基于排名的多关系社会网络中的社区挖掘算法(MCMABR),为维数较高的多关系社会网络降低算法复杂度提供了一种解决方案该算法针对社会网络中的关系数目成千上万情况下,对于用户查询来说,每个关系的重要程度是不一样的特点,对社会网络中关系集进行了预处理,选择重要度排名靠前的关系,在此基础上抽取出一组关系组合来发现社区结构,大大降低了时间复杂度,提高了算法效率。另外,针对某些情况下,仅仅从图拓扑结构上进行社区挖掘得不到用户想要的结果,还需要考虑社会网络中的语义信息,提出了一种多关系社会网络中的语义社区发现方法该方法首先定义和构建了社区一实体一语义数据模型(CED模型),采用Gibbs抽样算法对该模型进行了近似求解,通过计算属于社区的语义数据的概率分布发现语义社区。参考文献1张引.社会网络分析中的数据挖掘综述D.南京：南京大学计算机科学与技