2013标签传播算法理论及其应用研究综述.docVIP

标签传播算法理论及其应用研究南京大学信息管理南京210093） 摘 要: 标签传播算法是一种基于图的半监督学习算法，已标记节点的标签信息去未标记节点的标签。介绍了标签传播算法理论，了标签传播算法的特点，其在多媒体信息检索、分类、社区发现等方面的应用研究。标签传播半监督学习 TP301　　 文献标志码: A 文章编号：（作者可不填） doi:10.3969/j.issn.1001-3695 (作者可不填) The Overview on Label Propagation Algorithm and Applications Zhang Junli Chang Yanli Shi Wen (Department of Information Management, Nanjing University, Nanjing 210093, China) Abstract: The label propagation algorithm (LPA) is a graph-based semi-supervised learning algorithm, which can predict the information of unlabeled nodes by a few of labeled nodes, has many good natures such as simple, effective, speedy, favorable scalability and reliability. This article introduces the theoretical study of label propagation algorithm, analyses its characteristics and summarizes its applications in multimedia information processing, retrieval, annotation, classification and community discovery, etc. Finally, proposed the future prospects and the trends of developments of the LPA algorithm.? Key words: Label propagation algorithm; Semi-supervised learning; Multimedia; community discovery 0 引言半监督学习(Semi-Supervised Learning, SSL)是一种监督学习和无监督学习相结合的方法，[,]。 标传播算法[]（label propagation algorithm, LPA）Zhu X J于2002年提出，它是一种基于图的半监督学习方法，其基本思路是用已标记节点的标签信息去预测未标记节点的标签信息。利用样本间的关系，建立关系完全图模型，在完全图中，节点包括已标注和未标注数据，其边表示两个节点的相似度，节点的标签按相似度传递给其他节点，标签数据就像是一个源头，可以对无标签数据进行标注，节点的相似度越大，标签越容易传播。由于该算法简单易实现，算法执行时间短，复杂度低且分类效果好，引起了国内外学者的关注，并将其广泛地应用到多媒体信息分类、虚拟社区挖掘等领域中。本文利用关键字“label propagation”、“标签传播”、“标签传递”、“标记传播”、“标记传递”等词作为关键词，对国内外数据库及网络资源进行了检索，结果发现：目前国内外相关文献期刊论文约有90篇，其中国外82篇，国内8篇，国内外硕博论文3篇。国内对该算法的研究尚处于起步阶段，缺乏整体的系统的研究。对论文发表时间进行统计，可知2002-2006前的论文较少约12篇，2007-2009年的论文为36篇，2010-2012.5论文约有57篇。即该算法的研究从02年后，直至07年才引起人们重视，两年前开始成为研究热点。 本文简要介绍了该算法的基本理论和特点，总结了该算法在多媒体信息检索、分类、情感分析、语料标注、图像标注、视频推荐、网络社区发现、图像分割等方面的应用。提出了该算法未来可能的研究方向，探索将LPA应用于图博档，农村信息服务和电子商务等领域。 1 标签传播算法基本理论，节点的标按相似度传播给节点，，每个节点根据邻节点的标来更新自己的标，与该节点相似度越大，其邻节点对其标注的影响权值越大，相似节点的趋于一致，就越容易传播。在标传播过程中，保持已标注数据的标不变，使其像一个源头把标传向未标注数据。最终，当迭代过程