•标签传播算法
(LPA)是由 Zhu 等人于 2002 年提出，它是一种基于图的半监督学习方法，其基本思路是用已标记节点的标签信息去预测未标记节点的标签信息。利用样本间的关系建立关系完全图模型，在完全图中，节点包括已标注和未标注数据，其边表示两个节点的相似度，节点的标签按相似度传递给其他节点。标签数据就像是一个源头，可以对无标签数据进行标注，节点的相似度越大，标签越容易传播。由于该算法简单易实现，算法执行时间短，复杂度低且分类效果好，引起了国内外学者的关注，并将其广泛地应用到多媒体信息分类、虚拟社区挖掘等领域中。
标签传播算法基本理论
根据 LPA 算法基本理论，每个节点的标签按相似度传播给相邻节点，在节点传播的每一步，每个节点根据相邻节点的标签来更新自己的标签，与该节点相似度越大，其相邻节点对其标注的影响权值越大，相似节点的标签越趋于一致，其标签就越容易传播。在标签传播过程中，保持已标注数据的标签不变，使其像一个源头把标签传向未标注数据。最终，当迭代过程结束时，相似节点的概率分布也趋于相似，可以划分到同一个类别中，从而完成标签传播过程。
特点:
（1）只需利用少量的训练标签指导，利用未标注数据的内在结构、分布规律和邻近数据的标记，即可预测和传播未标记数据的标签，然后合并到标记的数据集中。
（2）LPA 可以通过相近节点之间的标签的传递来学习分类，它不受数据分布形状的局限，可以克服一些算法只能发现“类圆形”结构的缺点。只要同一类的数据在空间分布上是相近的，那么不管数据分布是什么形状，都能通过标签传播将它们分到同一个类里。
该算法操作简单、运算量小，适合大规模数据信息的挖掘和处理。缺点是每次迭代结果不稳定，准确率不高。 该算法操作简单、运算量小，适合大规模数据信息的挖掘和处理。缺点是每次迭代结果不稳定，准确率不高。
实验结果
参考：标签传播算法理论及其应用研究综述_张俊丽
main：
clear
clc
close all%(关闭图像)%%%%%%%%%%%%%%%%%%%%%%%% 生成数据 %%%%%%%%%%%%%%%%%%%%%%%%%
%定义一个自变量x含有30个元素，取值区间从0到2pi
N=1000;
t=(2*pi)*(1+2*rand(1,N));
s=6+2*rand(1,N);
x = cos(t);
y = sin(t);
s1=1+2*rand(1,N);
%l有标签数
%u无标签数
X=[x.*s,x.*s1,;y.*s,y.*s1];
X1=[X(1,1:10);X(2,1:10)];
NN=N+1;
X2=[X(1,NN:NN+10);X(2,NN:NN+10)];
X=[X1,X2,X(:,11:N),X(:,NN+11:N*2)];%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% load('22moon.mat');
% X=D(:,1:1:2);
% X=X';
% N=1000;
% X1=[X(1,1:10);X(2,1:10)];
% NN=N+1;
% X2=[X(1,NN:NN+10);X(2,NN:NN+10)];
% X=[X1,X2,X(:,11:N),X(:,NN+11:N*2)];%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
[D,N] = size(X);
%X数据横着放的
figure
plot(X(1,:),X(2,:),'.')
hold on
plot(X1(1,:),X1(2,:),'ok')
plot(X2(1,:),X2(2,:),'or')
hold off
%标号向量label,列向量
label=zeros(20,1);
label(1:10,1)=1;
label(11:20,1)=2;%%%%%%%%%%%%%%%%%%%%%%%% LPA算法分类 %%%%%%%%%%%%%%%%%%%%%%
%label数据点所属类
%l有标号的数据点个数
%N=l+u,数据点个数
%C类别个数
%dd迭代次数
C=2;
dd=30;
[ Labelnew ] = LPA( X,label,C,dd);%%%%%%%%%%%%%%% 画出半监督分类后的结果图 %%%%%%%%%%%%%%%%%%%
%画出分类结果
figure
plot(X(1,:),X(2,:),'.')
hold on
for i=1:Nif Labelnew(i)==1
plot(X(1,i),X(2,i),'ok')else
plot(X(1,i),X(2,i),'or')end
end
hold offLPA：
function [ Labelnew ] = LPA( X,label,C,dd)
%label有标号数据点所属类
%l有标号的数据点个数
%N=l+u,数据点个数
%C类别个数
%dd迭代次数
[D,N] = size(X);
l=size(label);
%Step1:计算距离
X2 = sum(X.^2,1);
distance = repmat(X2,N,1)+repmat(X2',1,N)-2*X'*X;%Step2: 构造相似矩阵W
W = zeros(N,N);
t=2;
for i=1:Nfor j=1:NW(i,j)=exp(-distance(i,j)/(t*t));end
end%Step3: 构造概率传递矩阵T（P）
T=zeros(N,N);
% for i=1:N
% for j=1:N
% T(i,j)=W(i,j)/sum(W(i,:));
% end
% end
zz=1./sum(W,2);
for i=1:N
T(i,:)=W(i,:).*zz(i);
end
%Step4：定义一个（l+u）*C的标注矩阵Y
Y=ones(N,C)*0.5;
%随机生成
% Y=rand(N,C);
%归一化
for i=1:Nfor j=1:CY(i,j)=Y(i,j)/sum(Y(i,:));end
end
%%%%%前l个已有标号写上
for i=1:l %Lj=label(i); Y(i,:)=0;Y(i,j)=1;
end%Step5：更新自己的概率分布。
F=Y;
%更新300次
for i=1:dd
%执行传播
F=T*F;
%重置F中已知的标号
for i=1:l %Lj=label(i); F(i,:)=0;F(i,j)=1;
end
end%Step6：找到每个数据所属于的类
%对列进行排序，sorted是拍好的向量,index是sorted 向量中对 A 的索引，排序是安升序进行的。
%[sorted,index] = sort(distance);
% [B,index]=sort(A,)%从小往大排
[B,index]=sort(F','descend');%从大往小排序
%第二行到第1行的没一列数
Labelnew = index(1,:);
end