大数据分析链接挖掘课件.ppt

《大数据分析链接挖掘课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、浅谈链接挖掘基本概念用图结构刻画"社交网络"的思路一个社交网络由很多节点（Node），和连接这些节点的一种或多种特定的链接（Link）组成节点表示数据实例，链接则表示实例之间存在的各种关系（Relation）社会网络的结构属性，如节点的度数（Degree）、连通性（Connectivity）子图（Subgraph）有助于我们对社团或群体行为的研究链接挖掘中的数据表示基本表示：行为者(Actor)：社交网络中的实体。联系(Relationtie)：不同的社会实体通过联系连接在一起。复杂的模式包括：二元组(Dyad)：由两个行为者及他们之间的关系组成，这是研究关系模式的基本单位；子图(Sub

2、group)：由网络中的一部分行动者和他们之间的关系组成，可以通过子图来研究社会网络中的一个小团体所具有的特征；图(Graph)：所有行动者及其之间的关系，分析社会网络的总体特征。典型的链接挖掘任务介绍基于链接的节点排序（Link-BasedObjectRanking）基于链接的节点分类（Link-BasedObjectClassification）节点聚类（ObjectClustering）链接预测（LinkPrediction）子图发现（SubgraphDiscovery）图分类（GraphClassification）基于链接的节点排序(Link-BasedObjectRankin

3、g)通过分析图中的链接结构，根据某种衡量节点重要性的度量对图中的节点进行排序，这种可度量的重要性被称为中心度（Centrality）。根据复杂程度不同，可分为局部度量和全局度量(静态图)。局部度量包括“度中心度”(DegreeCentrality)，即某个顶点的度数;全部度量包括“特征向量/能量中心度”（Eigenvector/PowerCentrality）其他的排序方法基于两个节点到他们所链接的相似节点的度数，估计这两个节点间相似程度（通过随机游走来计算），并可以引入了图分块以提高算法的稳定性G.JehandJ.Widom.SimRank:Ameasureofstructural-c

4、ontextsimilarity.InACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining,pages538-543,2002.J.Sun,H.Qu,D.Chakrabarti,andC.Faloutsos.Relevancesearchandanomalydetectioninbipartitegraphs.SIGKDDExplorations,7(2),December2005.扩展阅读(很老，很经典)：L.Freeman.Centralityinsocialnetworks:Conceptualclari

5、fications.SocialNetworks,1:215-239,1979.P.Bonacich.Powerandcentrality:Afamilyofmeasures.AmericanJournalofSociology,92(5):1170-1182,1987.基于链接的节点分类(Link-BasedObjectClassification)传统机器学习中的分类问题是基于数据实例（节点）独立且分布的假设一个数据图G=(O;L)表示节点集合O和他们之间的链接集合L，LBOC将O中的成员赋予某一类标签，与传统ML最大的区别在于节点的类别是彼此相关的条件随机场(Conditional

6、RandomFields)的概念，扩展了传统最大熵模型对于数据的结构必须是链式结构的限制J.Lafferty,A.McCallum,andF.Pereira.Conditionalrandomfields:Probabilisticmodelsforsegmentingandlabelingsequencedata.InProc.ofICML-01,2001.对每个数据实例增加新的属性来扩展简单的机器学习分类器，使其能处理基于链接的节点分类问题Q.LuandL.Getoor.Link-basedclassification.InInternationalConferenceonMachi

7、neLearning,2003.增加的新属性度量了类标签在节点组成的马尔可夫毯（MarkovBlanket）中的分布节点聚类（ObjectClustering）又称为群体检测（GroupDetection），将有着共同的特征的节点聚集。假设图中的节点和链接都属于同一种类，群体检测技术可以分成聚合聚类和分裂聚类块建模（Blockmodeling）是将社会网络分割成个体的集合，称为位置（Position）；定义在链接集合和聚合聚类之间的