k-medoids算法

k-medoid（也称为围绕medoid的划分）算法是由Kaufman和Rousseeuw于1987年提出的。中间点可以定义为簇中的点，其与簇中所有其他点的相似度最小。
k-medoids聚类是一种无监督的聚类算法，它对未标记数据中的对象进行聚类。k-medoids算法步骤:
步骤1：随机选择k个样本作为初始的簇中心；
步骤2：对剩余的每个样本，将其划分入距离它最近的簇中心所在的簇中，从而形成k个簇；
步骤3：重新计算簇中心，即对于每个簇，找到该簇中的一个样本点，称为medoid，使得该簇中所有其他点到该样本点的距离之和最小;

k-medoids聚类中心一定是原始样本点，而k-means聚类中心不一定是原始样本点

步骤4：如果簇中心没有发生任何改变，算法停止，否则回到步骤2。

k-中心聚类算法代码

function k_medoids(x,k)
%%
%生成数据(为了可视化，生成二维数据）
%x=[rand(20,2);rand(30,2)+1;rand(40,2)*2+1.5];
%k=3;
%样本分布可视化
figure(1)
subplot(1,2,1)%子图1
scatter(x(:,1),x(:,2),"filled")
title("样本分布")
[m,n]=size(x);
%产生1-m范围内的随机的k个整数 
%从原数组中提出这k个点对应坐标
s0=randperm(m,k);
c=x(s0,:);
%初始化
c0=zeros(k,n); 
D=zeros(m,k);
%%
while (max(abs(c-c0))>0.0001)
    c0=c;
    %定义行数为k的元胞数组用以存储簇对应样本点  
    cluster=cell(k,1);  
    %将选取的k个点加入到对应的k个存储单元,每个单元的第一行存储相对应的簇中心  
    for i=1:k  
    cluster{i}=c(i,:);  
    end
    %计算其他样本点到这k个点的距离，然后按照距离最近原则划分这些点 
    for i=1:k
    D(:,i)=sum((x-c(i,:)).^2,2).^0.5;
    end
    [~,id]=min(D,[],2);
    for i=1:k
     %将样本点划分到对应的簇中
    cluster{i}=cat(1,cluster{i},x(id==i,:)); 
    len=size(cluster{i},1);
    d=zeros(len,1);
    %计算每一个簇内的样本点到该簇内其他所有样本点的距离之和
    for j=1:len
        d(j)=sum(sum((cluster{i}-cluster{i}(j,:)).^2,2).^0.5);
    end
    %更新簇内中心
    %将距离其余样本点的距离之和最小的样本点作为该簇新的中心
    [~,id1]=min(d);
    c(i,:)=cluster{i}(id1,:);
    end
end
%绘制k-中心算法聚类结果
subplot(1,2,2) %子图2
for i=1:k  
scatter(cluster{i}(:,1),cluster{i}(:,2),'filled');  
hold on
%聚类中心（！k个原始样本点）
plot(c(i,1),c(i,2),"o","MarkerSize",9)
end
title("k-中心聚类结果")
hold off

测试结果可视化：

算法总结

k-medoids与k-means比较

k-means算法是每次选择簇的均值作为新的中心点，迭代直到簇中心不再变化（趋于稳定）。其缺点是对离群点特别敏感，因为一个很大的极端值对象会扭曲数据分布，使簇均值严重偏离；于是我们考虑新的簇中心不用均值表示而是选择簇内的某个对象，只要使总的代价降低就行，即k-medoids聚类算法。
在k-medoids聚类中，我们将medoid作为参考点，而不是像k-means聚类那样将簇中对象的质心作为参考点。medoid是簇中位置最集中的对象，或其与所有对象的平均差异性最小。因此，k-medoids算法比k-means算法对噪声更具鲁棒性。

k-medoids算法的优缺点

(1). k-medoids算法的优点：

• 与其他聚类算法相比，它有效地处理了数据中存在的噪声和异常值；因为它使用medoid将对象划分为集群。
• 易于实现且易于理解。
• 与其他聚类算法相比，k-medoid算法速度相对较快。
• 它以固定的迭代次数输出最终的对象簇。

(2). k-medoids算法的缺点：

• 对于同一数据集上的不同运行，可能会产生不同的聚类，因为最初，我们从所有数据对象中随机选择k个medoid，并将它们逐个分配给每个聚类，使其成为该聚类的初始medoid。
• 它在开始时固定了k（簇/组的数量）的值，因此我们不知道当k的值是多少时，结果是准确和可区分的。
• 它的总体计算时间和对象在簇或组中的最终分布取决于初始划分。