标签传播算法理论及其应用研究综述
- 格式：pdf
- 大小：261.44 KB
- 文档页数：5
文档推荐
-
一种新的基于标签传播的重叠社区发现算法页数:13
-
基于标签传播能力的改进LPA算法页数:5
-
标签传播算法理论及其应用研究综述页数:5
下载文档原格式
合集下载
复杂网络社区发现算法与应用研究
复杂网络社区发现算法与应用研究社交网络的快速发展给人们的交流和信息传播带来了巨大的便利，同时也使得网络中存在大量复杂的关系和交互行为。
复杂网络中的社区结构被认为是网络中一种重要的组织形式，研究复杂网络社区结构可以帮助我们更好地理解网络的演化和功能。
一、复杂网络社区发现算法介绍社区发现算法是一种用于检测复杂网络中社区结构的方法。
常见的社区发现算法包括GN算法、Louvain算法、标签传播算法、模块度最大化算法等。
GN算法是一种基于边介数的层次聚类算法，通过不断切割网络中边介数最大的边来发现社区。
Louvain算法是一种基于模块度优化的贪心算法，通过迭代地将节点重新分配到模块中以优化模块度，该算法处理速度较快。
标签传播算法是一种无监督的算法，通过节点间标签的传递更新来进行社区发现。
模块度最大化算法是一种基于优化网络模块度的算法，通过迭代地合并节点和模块来达到最大化模块度的目标。
搜索引擎提供的 PageRank 算法也可以被用于社区发现。
PageRank算法是一种用于排名网页重要性的算法，它可以通过将复杂网络建模为一个图，然后计算图中节点的重要性来进行社区划分。
二、复杂网络社区发现算法的应用复杂网络社区发现算法不仅在理论研究中有重要的作用，也在实际应用中发挥了巨大的价值。
首先，社区发现算法在社交网络分析中有广泛的应用。
社交网络中存在着大量的社区结构，通过发现这些社区可以更好地理解社交网络的组织结构和信息传播机制，它对于社交网络上的用户行为预测、信息推荐和舆情分析等方面具有重要意义。
其次，社区发现算法在生物学领域有着广泛的应用。
生物网络中存在着复杂的分子相互作用关系，研究这些关系可以帮助我们理解生物网络的功能和演化规律。
通过社区发现算法可以发现蛋白质相互作用网络中的功能模块，这对于研究蛋白质相互作用网络的功能和疾病的发生有重要的意义。
此外，复杂网络社区发现算法还在推荐系统、网络安全等领域有着广泛的应用。
社交网络分析中的社区发现技巧总结
社交网络分析中的社区发现技巧总结社交网络分析是一种研究社交关系的分析方法，通过对社交网络中的节点和边进行深入研究，可以揭示出社会关系的模式、影响力的传播路径等。
其中，社区发现是社交网络分析中的一个重要方面，它能够帮助我们识别出网络中相互关联紧密、功能相似的节点群体。
社区发现技巧的总结如下：1.节点度中心性节点度中心性是指节点的度数，即其在网络中所连接的边的数量。
在社交网络中，节点度中心性可以反映出节点的重要性和连接的紧密程度。
通过计算节点的度中心性，我们可以发现网络中度数较高的节点，往往代表着社区的核心节点。
2.介数中心性介数中心性用于衡量节点在整个网络中的中介程度，即节点在网络中作为桥梁的能力。
在社交网络中，介数中心性可以帮助我们发现那些在社区之间有着重要桥梁作用的节点，即连接不同社区的节点。
3.聚类系数聚类系数反映了网络中节点之间的紧密程度，它可以衡量节点间连接的密集程度，并从而发现社区。
在社交网络分析中，如果节点的聚类系数较高，即节点与其邻居节点之间的连接较紧密，那么可以认为这些节点可能属于同一个社区。
4.模块化模块化是一种社区发现的度量方法，它通过计算网络中节点与社区的内部联系强度与节点与社区的外部联系强度的差别，来评估社区发现的效果。
模块化值在-1到1之间，当模块化值接近1时，表示社区发现效果好，节点在社区内部联系强，并且社区之间的联系较弱。
5.谱聚类谱聚类是一种常见的社区发现方法，它基于图谱理论，通过计算节点相似性矩阵的特征向量来划分社区。
谱聚类可以将节点分为一组个体相似的社区，并且保持社区内的紧密连接和社区间的松散连接。
6.标签传播标签传播算法是一种基于标签更新的社区发现方法，它通过不断的更新节点的标签信息，将具有相似标签的节点划分为同一个社区。
标签传播算法简单、高效，并且在一些实际应用中取得了较好的效果。
7.模块度最优化模块度最优化是一种基于网络结构的社区发现方法，它通过优化模块度函数，将网络划分成多个具有较高内部联系和较低外部联系的社区。
基于LeaderRank的标签传播社区发现算法
基于LeaderRank的标签传播社区发现算法石梦雨;周勇;邢艳【摘要】针对标签传播算法(LPA)结果的不稳定性,提出一种改进的基于标签传播的社区发现算法.该算法引入LeaderRank的概念来量化网络节点的影响力和重要性;然后按照节点重要程度从高到低选择若干核心节点;最后按照顺序分别以每个核心节点为中心向外逐层进行标签更新,直到不再出现标签变化为止,从而解决了原始算法对节点随机排序造成的结果不稳定性.以LFR基准网络和真实网络为实验数据,与几个现有标签传播算法进行比较,社区划分结果的标准化互信息(NMI)和模块度(Modularity)均高于对比算法.理论分析和实验结果表明所提算法不仅有效地增强了社区发现结果的稳定性,同时提高了准确率.【期刊名称】《计算机应用》【年(卷),期】2015(035)002【总页数】5页(P448-451,455)【关键词】标签传播算法;不稳定性;社区发现;LeaderRank;节点重要性【作者】石梦雨;周勇;邢艳【作者单位】中国矿业大学计算机科学与技术学院,江苏徐州221008;中国矿业大学计算机科学与技术学院,江苏徐州221008;中国矿业大学计算机科学与技术学院,江苏徐州221008【正文语种】中文【中图分类】TP18;TP3110 引言随着科技的飞速发展，复杂网络研究越来越得到广泛重视。
几乎所有的复杂系统都可以用网络建模进行研究［1］，例如，人类社会是由各种社会关系组成的复杂网络;万维网是由网页和超链接构成的网络;铁路运输网络是由城市和城市之间的铁路干线构成的网络等。
复杂网络具有小世界、无标度以及高积聚系数［2］等特性，其中社区结构是复杂网络的最重要性质之一。
所谓社区是指网络中连接紧密的个体组成的集合。
社区发现能帮助研究复杂网络的社区结构，具有重要的理论意义和广泛的应用前景，目前已经被应用于社会网络分析、生物网络、网页文档聚类等各个领域。
近年来学者们提出了很多社区发现算法，包括图分割、层次聚类、分割聚类、谱聚类及模块函数算法等。
标签推荐方法研究综述
标签推荐方法研究综述
徐鹏宇;刘华锋;刘冰;景丽萍;于剑
【期刊名称】《软件学报》
【年(卷),期】2022(33)4
【摘要】随着互联网信息的爆炸式增长,标签(由用户指定用来描述项目的关键词)在互联网信息检索领域中变得越来越重要.为在线内容赋予合适的标签,有利于更高效的内容组织和内容消费.而标签推荐通过辅助用户进行打标签的操作,极大地提升了标签的质量,标签推荐也因此受到了研究者们的广泛关注.总结出标签推荐任务的三大特性,即项目内容的多样性、标签之间的相关性以及用户偏好的差异性.根据这些特性,将标签推荐方法划分为3个类别,分别是基于内容的方法、基于标签相关性的方法以及基于用户偏好的方法.之后,针对这3个类别下的对应方法进行了梳理和剖析.最后,提出了当前标签推荐领域面临的主要挑战,例如标签的长尾问题、用户偏好的动态性以及多模态信息的融合问题等,并对未来研究方向进行了展望.
【总页数】23页(P1244-1266)
【作者】徐鹏宇;刘华锋;刘冰;景丽萍;于剑
【作者单位】交通数据分析与挖掘北京市重点实验室(北京交通大学);北京交通大学计算机与信息技术学院
【正文语种】中文
【中图分类】TP311
【相关文献】
1.基于LDA主题模型的标签推荐方法研究
2.基于灰色关联度聚类与标签重叠因子结合的协同过滤推荐方法研究
3.我国基于Folksonomy的标签推荐方法研究综述
4.基于标签的协同过滤推荐方法研究
5.基于标签的个性化项目推荐系统研究综述
因版权原因，仅展示原文概要，查看原文内容请购买。
社会工作经典理论之标签理论
（二）形成期（20世纪50年代），以莱默 特(Edwin Lement)1951年出版的《社会病 理学》一书为标志。在此书中，莱默特将 越轨划分为“初级越轨（primary deviance）”和“次级越轨(secondary deviance)”。他认为，几乎每一个人都可能 偶尔发生越轨行为，绝大数的这类行为都 是暂时的、试探性的、轻微的和容易隐瞒 的。这类第一次发生的、虽然违背了普遍 地行为规范、但行为者本人与别人却并没 有这样认定的越轨行为是初级越轨行为。 不过，如果这类行为碰巧被某些重要的人 发现并被公布于众，情况就会发生急剧的 变化。
（二）标签理论的局限 标签理论提供越轨行为如何发生与持 续的新观点，尽管对越轨行为的研究有一 定的贡献，但由于此理论的不够精确清楚， 以及缺乏实征的证据，也引起了不少批评。 1、标签理论不能解释越轨行为的真正成因 标签理论认为社会的反应，尤其是公 开地张贴上标签是越轨行为的成因，而批 评者则不以为然，为此批评者提出了两点 理由：
（三）繁荣期，以1963年，贝克尔（Howard Becker）出 版的《圈外人》(《The Outsiders》，又译《局外人》) 为标志，该书系统地阐述了标签理论的主要内容。贝克 尔说：“越轨行为是应用规章、法律等对于一个‘冒犯 者’标定的结果。所谓有越轨行为者，就是被成功地贴 上了这种标签的人。” 依据贝克尔的观点，越轨既不是 与生俱来的人性，也不是后天教化的产物，而是一些人 将一些规则和制裁方式应用于“圈外人”的结果，是一 种社会反应、他人定义的结果。由于某些“圈外人”被 成功的贴上了标签，于是他们便成为了越轨行为者。 贝克尔在《圈外人》一书中又明确提出，要把越轨理论 的分析从越轨行为转移到那些把他人贴上越轨标签的 “道德提倡者身上去，最起码也要将越轨视为被人称为 越轨者和称人为越轨者这两部分人进行互动的结果。
基于优化标签传播算法的社区发现方法研究
基于优化标签传播算法的社区发现方法研究
吴小兰;章成志
【期刊名称】《情报学报》
【年(卷),期】2014(033)005
【摘要】自动发现高质量的网络社区结构是当前社会网络分析研究中的热点方向之一.与现有一些网络社区结构发现算法相比,标签传播社区发现算法具有不需要指定社区数量与时间复杂度低的优点,但该算法随机排列待更新节点和随机选择候选标签的策略严重影响了算法的准确率和稳定性.为了降低标签传播算法中这两种随机性,本文提出了一种优化的标签传播算法.经在真实基准网和计算机生成网的测试表明该算法具有更好的有效性和稳定性后,我们将该算法应用在科学网博客中“图书馆、情报与文献学”领域用户的好友关系网上,有效地发现了该网络中的社区结构.
【总页数】11页(P538-548)
【作者】吴小兰;章成志
【作者单位】南京理工大学经济管理学院信息管理系,南京210094;安徽财经大学管理科学与工程学院,蚌埠233030;南京理工大学经济管理学院信息管理系,南京210094
【正文语种】中文
【相关文献】
1.基于多标签传播的重叠社区发现优化算法 [J], 杜长江;王志晓;邢贞明
2.基于模块度优化的标签传播社区发现算法 [J], 李磊;倪林
3.基于模块密度优化的标签传播社区发现算法 [J], 陈建军;叶东毅
4.一种优化标签传播过程的重叠社区发现算法 [J], 赵雨露;张曦煌
5.基于标签传播的蚁群优化算法求解社区发现问题 [J], 顾军华;江帆;武君艳;许馨匀;张素琪
因版权原因，仅展示原文概要，查看原文内容请购买。
基于标签传播算法在重叠社区发现中的改进
基于标签传播算法在重叠社区发现中的改进王茜;方旭【摘要】随着信息技术的发展,复杂网络越来越被广泛关注.在真实网络中,重叠社区发现也越来越普遍,与算法相比,标签传播算法简单.在原有COPRA算法的基础上,对标签初始化和标签选择进行改进,提出一种新的重叠社区发现算法.实验表明,该算法挖掘的重叠社区具有更高的模块度,能够更加有效地发现重叠社区结构.【期刊名称】《现代计算机（专业版）》【年(卷),期】2017(000)012【总页数】4页(P7-10)【关键词】复杂网络;重叠社区发现;标签传播【作者】王茜;方旭【作者单位】重庆大学计算机学院,重庆 400044;重庆大学计算机学院,重庆400044【正文语种】中文随着信息技术的发展，大多数网络都存在社区结构这一特征。
现有的社区发现主要分为非重叠社区发现和重叠社区发现两大类，其中非重叠社区发现方法发现的社区是彼此不重叠的，一个节点只能属于一个社区，而重叠社区发现允许一个节点同属于多个社区。
重叠社区与非重叠社区比较具有更现实的意义，首先重叠节点是必然是社区中重要的节点，其次重叠社区反映了更加真实的社会网络结构。
那么重叠社区的发现及其算法研究已经成为目前一个热点问题。
2.1 标签传播思想标签传播算法在2002年最早被提出，先为任一节点初始化一个标签，然后根据邻接点更新自己标签，如果标签直接越相似，那么邻接点的标签就更易被传播。
2.2 LPA算法图G=（V，E）表示有n个节点{1，2，…，n}∈V，m条边{1，2，…，m}∈E的无向无权复杂网络，标签传播算法根据标签传播的思想，重复迭代更新到算法结束，最后根据节点标签分类。
标签传播具体流程如下：（1）初始化，为节点分配标签，x节点标签为Cx（0）=x；（2）随机排列网络中的节点，排列为X；（3）对X中每个节点x，根据公式Cx（t）=f（C（x1）（t-1），…，Cxm（t-1），Cxm+1（t-1））对x节点的标签进行更新。
一种新的基于标签传播的重叠社区发现算法
一种新的基于标签传播的重叠社区发现算法摘要摘要：发现高质量的社区是社区网络问题的研究热点。
目前，社区发现算法大多针对非重叠社区，重叠社区发现算法较少。
基于标签传播的算法是现有重叠社区发现算法中的一类，其中COPRA为典型算法。
尽管该算法具有接近线性的时间复杂度，但存在随机因素，结果不稳定，产生的社区结构存在一定差异。
为此，提出一种新的基于标签传播的社区发现算法，实验表明该算法在复杂度相近的情况下能明显提高所发现社区的质量，且具有较好的稳定性。
关键词关键词：社区发现；重叠社区；标签传播；稳定性DOIDOI：10.11907/rjdk.1431038中图分类号：TP312文献标识码：A文章编号文章编号：16727800（2015）0040059041重叠社区及其发现算法近年来，复杂网络研究受到广泛关注，主要涉及系统科学、统计物理学、社会科学、生物学等多个领域[1]。
随着通信和互联网技术的快速发展，人们发现众多网络都存在社区结构[2]这一特征。
所谓社区结构，简单来说，就是网络中的节点存在分组，一般组内的边连接比较稠密，而组间的边连接比较稀疏。
社区结构在一定程度上可以反映出真实网络的拓扑关系。
社区发现可以帮助更好地理解网络拓扑结构及其功能，从而更好地利用和改造网络，例如挖掘网络中的未知功能、控制疾病传播等。
社区发现在某些特定应用环境中也有现实意义，例如发现恐怖分子、寻找犯罪团体等。
然而，真实网络存在一些同时属于多个社区的节点，这些节点叫作“重叠节点”，与其它社区存在重叠节点的社区就叫作“重叠社区”。
例如在社会关系网络中，小王既参加了台球俱乐部，又参加了乒乓球俱乐部，那么小王就是这两个社区的重叠节点，台球俱乐部和乒乓球俱乐部是两个重叠社区。
重叠社区较之非重叠社区具有更好的现实意义：一方面，重叠节点是网络中关键点，重叠社区因此而产生联系；另一方面，重叠社区反映了更加真实的网络结构。
因此，研究重叠社区更符合真实网络的结构。
基于深度学习的弱监督图像分类技术研究
基于深度学习的弱监督图像分类技术研究近年来，深度学习技术在图像分类领域中得到了广泛应用。
但是，传统的深度学习算法需要标注大量的训练数据，这对于训练样本难以获取的应用场景来说是一个严峻的挑战。
弱监督学习技术可以利用少量的有标注数据来训练模型，大大减少了人工标注样本的工作量。
在图像分类领域，弱监督学习技术也被广泛应用，包括基于标签传播、多示例学习和注意力机制等方法。
本文将重点介绍基于深度学习的弱监督图像分类技术研究。
一、标签传播算法标签传播算法利用图形理论中的标签传播算法对训练数据的标签进行传播和推理，从而对未标记数据进行标注，从而弱化对训练数据的要求。
标签传播算法需要利用光滑性假设，即对于相似的图像样本，在特征空间中也应该有相似的位置，从而进行标注推理。
标签传播算法可以将不同的数据分成若干个类别，并对没有标签的数据进行分类，达到了分类目的。
但是，标签传播算法也存在一些问题，如不能很好地避免噪声的干扰、对于复杂模型的支持不够强等问题。
二、多示例学习算法多示例学习算法是一种利用未加标注数据来训练模型的弱监督方法。
多示例学习是一种只需要标记某一组数据属于哪一类的学习方法。
因此，使用多示例学习方法来设计图像分类模型时，只需要标注图像组别的标签，而不需要标注每张图像的标签。
多示例学习算法可以将图像分成多个部分，并将每个部分视为一个示例，从而利用未标记数据中的信息对模型进行训练。
通过多示例学习算法，我们可以快速训练出一个分类模型，并对新的图像进行分类。
但是，多示例学习算法仍然存在着过拟合风险和对未加标注数据的利用效率不足等问题。
三、注意力机制算法注意力机制可以使深度学习模型更关注某些特殊样本，从而达到更好的分类效果。
在图像分类领域，注意力机制可以将图像各个区域的关注度量化，并将其应用到深度学习网络中从而提高分类效果。
不同于固定区域的排列权重，注意力机制可以自适应地为不同的区域计算权重，并且可以利用未加标注数据的信息来指导模型的训练。
lpa算法原理
lpa算法原理LPA算法原理LPA（Label Propagation Algorithm）算法是一种基于标签传播的无监督学习算法，用于社区发现和图分类等问题。
该算法通过标签在图中的传播来实现节点的标签更新，从而得到节点的最终标签。
LPA算法的核心思想是利用节点邻居的标签信息来更新自身的标签，达到标签传播的目的。
LPA算法的步骤如下：1. 初始化：为每个节点赋予一个唯一的初始标签。
2. 标签传播：迭代地更新每个节点的标签，直到收敛为止。
- 对于每个节点，根据其邻居节点的标签来更新自身的标签。
具体而言，节点选择邻居节点中出现最多次数的标签作为自己的新标签。
- 如果有多个标签出现次数相同，则随机选择一个作为新标签。
3. 收敛判断：判断是否达到收敛条件。
若达到，算法结束；否则，返回第2步。
LPA算法的特点：1. 无监督学习：LPA算法不需要事先标注样本，仅利用节点的邻居信息进行标签传播，因此可以应用于无监督学习任务。
2. 高效简单：LPA算法的计算复杂度较低，且实现简单。
它只需要进行标签传播迭代，并且每次迭代只需要考虑节点的邻居信息，因此算法具有较高的效率。
3. 适用性广泛：LPA算法可以应用于社区发现、图分类、推荐系统等多个领域。
在社区发现任务中，节点的标签可以表示节点所属的社区，通过LPA算法可以将相似节点聚集到一起，发现图中的社区结构。
LPA算法的应用举例：在社交网络中，可以利用LPA算法进行社区发现。
社交网络中的节点可以表示用户，边表示用户之间的关系。
通过LPA算法，可以将具有相似兴趣、活动或联系的用户聚集到一起，形成不同的社区。
这对于社交网络的用户推荐、信息传播等任务具有重要意义。
另一方面，LPA算法也可以应用于图分类任务。
对于一个图分类问题，可以将图中的节点作为样本，节点的邻居关系作为特征。
通过LPA算法，可以将相似的节点聚集到一起，并将其标记为同一类别，从而实现图的分类。
总结：LPA算法是一种基于标签传播的无监督学习算法，通过节点标签的传播来实现节点标签的更新。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
收稿日期：2012-06-28；修回日期：2012-08-14基金项目：国家社科基金重大资助项目（10＆ZD134）作者简介：张俊丽（1982-），女，湖北松滋人，博士，主要研究方向为多媒体信息检索与分类、机器学习（elili62@126．com）；常艳丽，博士研究生；师文，博士研究生．
标签传播算法理论及其应用研究综述*张俊丽，常艳丽，师文（南京大学信息管理学院，南京210093）
摘要：介绍了标签传播算法理论，分析了标签传播算法的特点，总结了其在多媒体信息检索、分类、标注、处理和社区发现等方面的应用研究，最后探讨了标签传播算法未来的研究方向。关键词：标签传播算法；半监督学习；多媒体；社区发现中图分类号：TP301文献标志码：A文章编号：1001-3695（2013）01-0021-05doi：10．3969/j．issn．1001-3695．2013．01．004
OverviewonlabelpropagationalgorithmandapplicationsZHANGJun-li，CHANGYan-li，SHIWen（SchoolofInformationManagement，NanjingUniversity，Nanjing210093，China）
Abstract：Thisarticleintroducedthetheoreticalstudyoflabelpropagationalgorithm，analyseditscharacteristicsandsumma-rizeditsapplicationsinmultimediainformationprocessing，retrieval，annotation，classificationandcommunitydiscovery，etc．Finally，thispaperproposedthefutureprospectsandthetrendsofdevelopmentsoftheLPAalgorithm．Keywords：labelpropagationalgorithm（LPA）；semi-supervisedlearning（SSL）；multimedia；communitydiscovery
机器学习算法可以分为有监督学习和无监督学习算法两大类。所谓有监督学习，是指从已经标注好类别的数据样本中学习；而无监督学习，是指根据数据本身的内在特点进行学习，样本事先并没有清晰的分类。半监督学习（SSL）是一种监督学习和无监督学习相结合的方法，其主要思想是：基于数据分布上的模型假设，利用少量的已标注数据进行指导并预测未标记数据的标记，然后合并到标记的数据集中［1，2］。标签传播算法［3］（LPA）是由Zhu等人于2002年提出，它是一种基于图的半监督学习方法，其基本思路是用已标记节点的标签信息去预测未标记节点的标签信息。利用样本间的关系建立关系完全图模型，在完全图中，节点包括已标注和未标注数据，其边表示两个节点的相似度，节点的标签按相似度传递给其他节点。标签数据就像是一个源头，可以对无标签数据进行标注，节点的相似度越大，标签越容易传播。由于该算法简单易实现，算法执行时间短，复杂度低且分类效果好，引起了国内外学者的关注，并将其广泛地应用到多媒体信息分类、虚拟社区挖掘等领域中。本文利用关键字labelpropagation、标签传播、标签传递、标记传播、标记传递等词作为关键词，对国内外数据库及网络资源进行了检索，结果发现，目前国内外相关文献期刊论文约有90篇，其中国外82篇，国内8篇，国内外硕博论文3篇。1标签传播算法基本理论根据LPA算法基本理论，每个节点的标签按相似度传播给相邻节点，在节点传播的每一步，每个节点根据相邻节点的标签来更新自己的标签，与该节点相似度越大，其相邻节点对其标注的影响权值越大，相似节点的标签越趋于一致，其标签就越容易传播。在标签传播过程中，保持已标注数据的标签不变，使其像一个源头把标签传向未标注数据。最终，当迭代过程结束时，相似节点的概率分布也趋于相似，可以划分到同一个类别中，从而完成标签传播过程。具体算法［3］如下：令（x1，y1）…（xl，yl）是已标注数据，YL=
｛y1…yl｝∈｛1…C｝是类别标签，类别数C已知，且均存在于标
签数据中。令（xl+1，yl+1）…（xl+u，yl+u）为未标注数据，YU=
｛yl+1…yl+u｝不可观测，l＜＜u，令数据集X=｛x1…xl+u｝∈RD。
问题转换为：从数据集X中，利用YL的学习，为未标注数据集YU的每个数据找到对应的标签。
将所有数据作为节点（包括已标注和未标注数据），创建一个完全连接图，其边的权重计算式如下：
wij=exp（－d2ijσ2）=exp（－∑Dd=1（xdi－xdj）2σ2）（1）
其中：dij表示任意两个节点的欧氏距离，权重wij受控于参数σ。为衡量一个节点的标注通过边传播到其他节点的概率，在此定义一个（l+u）×（l+u）概率传递矩阵T如下所示：
Tij=P（j→i）=wij
∑l+uk=1wkj
（2）
其中：Tij是节点j到i的传播概率。同时定义一个（l+u）×C的标注矩阵Y，令Yic=δ（yi，c），它的第i行代表着节点yi的标注概率，第c列代表类别，若Yic=
1则表示节点yi是属于c类别，否则为0。通过概率传递，使其
概率分布集中于给定类别，然后通过边的权重值来传递节点标签。矩阵Y的初始值并不重要，但是要保证他的每行都是标准化的。算法描述如下：输入：u个未标注数据，l个标注数据及其类别C。输出：u个未标注数据的标注。a）初始化，利用式（1）计算边权重矩阵wij，得到数据间的相似度。
b）根据步骤a）得到的wij，利用式（2）计算节点j到i的传播概率。
第30卷第1期2013年1月计算机应用研究ApplicationResearchofComputersVol.30No.1Jan．2013c）定义一个（l+u）×C维的标注矩阵Y。d）每个节点按传播概率把它周围节点传播的标注值按权重相加，并更新自己的概率分布：
Fij=∑l+uk=1Tij1≤i≤l+u；1≤j≤C（3）e）限定已标注数据，把已标注数据的概率分布重新赋值
为初始值。重复步骤d），直到收敛。注意保持已标注数据点的标注源不变，把它的值限定为Yl，不断地把标注从高权值传播到低权值。Fij=Yij1≤i≤l；1≤j≤C（4）
2标签传播算法的特点
a）LPA是一种半监督学习算法，具有半监督学习算法的
两个假设前提：（a）邻近的样本点拥有相同的标签，根据该假设，分类时边界两侧尽可能避免选择较为密集的样本数据点，而是尽量选择稀疏数据，便于算法利用少量已标注数据指导大量的未标注数据；（b）相同流形结构上的点能够拥有相同的标签，根据该假设，未标记的样本数据能够让数据空间变得更加密集，便于充分分析局部区域特征。b）LPA只需利用少量的训练标签指导，利用未标注数据
的内在结构、分布规律和邻近数据的标记，即可预测和传播未标记数据的标签，然后合并到标记的数据集中。该算法操作简单、运算量小，适合大规模数据信息的挖掘和处理。c）LPA可以通过相近节点之间的标签的传递来学习分
类，它不受数据分布形状的局限，可以克服一些算法只能发现“类圆形”结构的缺点。只要同一类的数据在空间分布上是相
近的，那么不管数据分布是什么形状，都能通过标签传播将它们分到同一个类里。因此可以处理包括音频、视频、图像及文本的标注、检索及分类，算法简单、执行速度快、可扩展性强、效果好。
3标签传播算法的应用研究
LPA的上述特点决定了它具有较强的实用性，在多媒体信
息检索与分类、网络社区发现、多媒体信息标注与处理等诸多领域都取得了令人鼓舞的成果。本文通过对国内外研究文献的整理，总结出学术界对标签传播算法的应用研究。
3.1文本信息检索与分类
文本分类［4］是指在给定的分类模型下，将用自然语言表示的文本，根据其内容自动地确定该文本所属的一个或多个类别。信息检索主要是对用户需求和信息资源分别标引，对这两个标引结果进行匹配，并将匹配成功的资源文档作为检索结果返回给用户。实质上，文本分类和信息检索技术都是进行标引和匹配的，文本分类是将类别与文本内容进行匹配，而信息检索是将用户需求与信息资源进行匹配。在文本分类与信息检索中，其关键技术是分类算法或检索算法，该算法的性能直接影响到信息分类或者检索效果。LPA能够根据用户的要求，将类别标签或者用户的需求标
签按照相似度将标签传播至未标注文本或网页，该相似度决定了其相邻节点间传播的概率，对类别或者用户需求与信息资源进行匹配，从而实现检索与分类、语义消岐、语料标注、信息推荐、情感分析等。这种算法的最大优点是能够利用有限的标注数据，对大量的未知信息或者网页进行标注，减少人工训练标签数据的工作量。Yang等人［5］创新性地利用LPA算法进行英汉双语信息检索。使用OKAPIBM25作为检索模型，从初始检索结果的排序中提取出伪标注文件，采用LPA对未标注文本进行标注，并利用K-means聚类信息，然后对文档按照相关度重排。Kim和贺松林等人［6，7］提出利用LPA进行网页分类。前者假设未标注文本容易被相同用户查询和点击，搜索引擎的点击日志里包含了相似类别网页的链接信息，利用用户的点击信息发现相似页面，构建相似文本点击图，自动扩大训练数据。其方法是通过构建训练模型———点击数据模型和查询约束模型，计算相似度，然后利用LPA对未标注信息标注，从而解决网页分类问题。而贺松林等人主要是对LPA进行改进，利用K-means和LPA进行网页分类，其主要特点是针对网页特点，使用欧氏距离构建一个带权图，利用标签传播算法将已标记节点的标签沿着边向相邻节点传播，从而将网页分类问题转为标签在图上的传播，并结合K-means聚类在保证精度的情况下降低维度，提升标签传播的效率及性能。Blair-Goldensohn等人［8］创新性地提出将LPA应用于情感分类（也称为极性分类），他利用少量人工标签引导极性词典，基于LPA算法，充分利用上下文和用户提供的标签，对顾客购后评价进行情感分类。Rao等人［9］提出利用基于图的LPA算法进行极性分类，每个节点代表待分类的词，边的权重表示两个词之间的相似度，每个节点有两个标签，即正面的和负面的，利用WordNet和OpenOffice两个词库的英语、法语和北印度语进行实验。Speriosu等人［10］在已有研究基础上，对上述两种方法进行改进，通过增加节点和边构建一个有向的不对称关系图，直观地显示其追随者关系图，并结合词性链接，利用LPA进行极性分类。任晓娟和郝建柏等人［11，12］利用LPA算法进行文本分类。任晓娟指出，LPA算法应用于文本分类存在噪声问题，提出LPA在标签传播的过程中，计算每个点和各个类别的相似度。如果某个节点和每个类别的相似度都比给定的阈值小，那么就把该点设定为噪声点，即不属于任何类别，剔除该噪声点后再进行信息分类。郝建柏等人则先利用模糊近邻算法，使样本与其k个近邻连接，然后利用LPA使类别标签从已标注数据向未标注数据传递，从而实现分类。Niu等人［13］假设类似的样本拥有类似的标签，未标注样本的标签不仅受邻近标注样本的影响，也受到邻近未标注样本的影响。利用数据加权图作为向量，使LPA自动地在邻近向量之间传播标签，从而进行语义消岐。Lansdall-Welfare等人［14］创新性地构建了一个文本稀疏数据图，将文档用顶点图表示，利用LPA沿着图的边缘传播文本数据的标签，使距离近的文本倾向于拥有相同的标签，可对不正确的文档标注及时地重分类和重标注，从而提高标注质量。上述文献的主要作者和主要贡献如表1所示。3.2多媒体信息标注、检索与分类多媒体信息的标注主要是将已标注的多媒体样本（如图像、音/视频等）看做是分类系统中的类标签，利用机器学习算法从已标注的多媒体样本集中，自动学习语义概念空间与多媒体特征空间的关系模型，从而对未标注样本生成类别标签，完成多媒体样本信息的标注。常用的标注算法有贝叶斯（Bayes）、支持向量机（supportvectormachine，SVM）、二维隐马尔可夫模型（2-dimensionalhiddenMarkovmodel，2D-HMM）等［15］。