当前位置: 代码迷 >> 综合 >> 干货回顾丨机器学习笔记-----AP(affinity propagat)算法讲解及matlab实现
  详细解决方案

干货回顾丨机器学习笔记-----AP(affinity propagat)算法讲解及matlab实现

热度:6   发布时间:2023-12-17 09:33:49.0



在统计和数据挖掘中,亲和传播(AP)是基于数据点之间"消息传递"概念的聚类算法。与诸如k-means或k-medoids的聚类算法不同,亲和传播不需要在运行算法之前确定或估计聚类的数量。 类似于k-medoids,亲和力传播算法发现"样本",输入集合的成员,输出聚类结果。

一 算法描述

2.1基本介绍

我们让(x1,…xn)作为一系列的数据点,然后用矩阵S代表各个数据点之间的相似度,一般相似度的判断有欧氏距离,马氏距离,汉明距离。如果S(i,k)>S(i,j)则表示i到k的距离比i到j的距离近。其中S(k,k)表示节点k作为k的聚类中心的合适程度,可以理解为,节点k成为聚类中心合适度,在最开始时,这个值是初始化的时候使用者给定的值,会影响到最后聚类的数量。

这个算法通过迭代两个消息传递步骤来进行,以更新下面两个矩阵:

代表(Responsibility)矩阵R:r(i,k)表示第k个样本适合作为第i个样本的类代表点的代表程度。说白了K为男人,i为女人,代表矩阵R表示,这个男人成为i这个女人老公的适合程度。

适选(Availabilities)矩阵A=[a(i,k)]N×N:a(i,k)表示第i个样本选择第k个样本作为类代表样本的适合程度,同理表示i选择K作为自己老公的可能性。当然,这个社会是相对于封建社会有点进步的,比如也会征求女方的意见,但是又有一定弊端,这个男人K可以三妻四妾。所以K这个聚类中心,周围可以有许多样本i。所以有的人叫R矩阵为吸引度矩阵,矩阵A为归属度矩阵也是不无道理的。

2.2 算法的迭代公式

对于代表矩阵r: 

假设现在有一个聚类中心K,我们找到另外一个假想的聚类中心k',重新定义K'的代表矩阵和适合矩阵:,找出这两个值相加最大的那一个,在用我们的减去这个最大的,就表示这个K的聚类中心对i这个样本的吸引程度。你想想,最大情敌的吸引力都没有我高,那我岂不是最牛叉???

对于适合矩阵a: 

我们要明白一个道理,如果一个男人对大部分女人的吸引力都很大,那么这个男人对你这个女人的吸引力的可能性是不是比别人大一点?明白了这个道理。同理如果节点k作为其他节点i'的聚类中心的合适度很大,那么节点k作为节点i的聚类中心的合适度也可能会较大,由此就可以先计算节点k对其他节点的吸引度,r(i',k),然后做一个累加和表示节点k对其他节点的吸引度,得到:。等等r(k,k)是什么意思呢,一般帅的人是不是都是特别容易自恋?你懂得,所以这个表示样本选择自己作为聚类中心的自恋程度。为了不让这个值过大,影响整体结果,将这个值控制在0以下。当i=k的时候我们选就可以了。a(k,k)表示K这个作为聚类中心的能力。

注意有时候为了防止参数更新时的震动需要引入一个减震参数damping。Damping计算如下:

二 算法实现

function idx = AP(S)

N = size(s,1);

A=zeros(N,N);

R=zeros(N,N); % Initialize messages

 

lam=0.9; % Set damping factor

 

same_time = -1;

for iter=1:10000

% Compute responsibilities

Rold=R;

AS=A+S;

[Y,I]=max(AS,[],2);

for i=1:N

AS(i,I(i))=-1000;

end

[Y2,I2]=max(AS,[],2);

R=S-repmat(Y,[1,N]);

for i=1:N

R(i,I(i))=S(i,I(i))-Y2(i);

end

R=(1-lam)*R+lam*Rold; % Dampen responsibilities

% Compute availabilities

Aold=A;

Rp=max(R,0);

for k=1:N

Rp(k,k)=R(k,k);

end

A=repmat(sum(Rp,1),[N,1])-Rp;

dA=diag(A);

A=min(A,0);

for k=1:N

A(k,k)=dA(k);

end;

A=(1-lam)*A+lam*Aold; % Dampen availabilities

 

if(same_time == -1)

E=R+A;

[tt idx_old] = max(E,[],2);

same_time = 0;

else

E=R+A;

[tt idx] = max(E,[],2);

 

if(sum(abs(idx_old-idx)) == 0)

same_time = same_time + 1;

if(same_time == 10)

iter

break;

end

end

idx_old = idx;

end

end

 

E=R+A;

[tt idx] = max(E,[],2);

 

% figure;

% for i=unique(idx)'

% ii=find(idx==i);

% h=plot(x(ii),y(ii),'o');

% hold on;

% col=rand(1,3);

% set(h,'Color',col,'MarkerFaceColor',col);

% xi1=x(i)*ones(size(ii)); xi2=y(i)*ones(size(ii));

% line([x(ii)',xi1]',[y(ii)',xi2]','Color',col);

% end;

 

总结:算法讲解部分到这里结束了。谢谢大家,能否走一波关注?哈哈


  相关解决方案