密度峰值聚类算法(DPC)

目录

DPC算法

1.1 DPC算法的两个假设

1）类簇中心被类簇中其他密度较低的数据点包围；
2）类簇中心间的距离相对较远。

1.2 DPC算法的两个重要概念

1）局部密度
设有数据集为 ，其中 ，N为样本个数，M为样本维数。
对于样本点i的局部密度，局部密度有两种计算方式，离散值采用截断核的计算方式，连续值则用高斯核的计算方式。

式中dij为数据点 i 与数据点 j 的欧氏距离，dc为数据点i的邻域截断距离。
采用截断核计算的局部密度ρi等于分布在样本点i的邻域截断距离范围内的样本点个数；而利用高斯计算的局部密度ρi等于所有样本点到样本点i的高斯距离之和。
DPC算法的原论文指出，对于较大规模的数据集，截断核的计算方式聚类效果较好；而对于小规模数据集，高斯核的计算方式聚类效果更为明显。

1.3 DPC算法的执行步骤

1.4 DPC算法的优缺点

优点：
1）不需要事先指定类簇数；
2）能够发现非球形类簇；
3）只有一个参数需要预先取值。
缺点：
1）当类簇间的数据密集程度差异较大时，DPC算法并不能获得较好的聚类效果；
2）DPC算法的样本分配策略存在分配连带错误。

matlab代码

密度计算函数

计算密度，利用截断核算法，pdist2是计算欧式距离的，对于每个idata_len进行计算所有的点的欧式距离，利用求和函数进行求取密度

function data_density=cal_density(data,cut_dist)%%利用截断核的方式进行计算data_len=size(data,1);%%size(data,1)是获取data的行数，size(data,2)是获取列数data_density=zeros(1,data_len);%%for idata_len=1:data_lentemp_dist=pdist2(data,data(idata_len,:));%计算第i行的点和data中所有点的欧式距离data_density(idata_len)=sum(temp_dist<=cut_dist);%%temp_dist中所有数据同cut_dist进行比较%%disp(data_density(idata_len))end
end

计算delta

两种情况：
对于密度最高的值，选取距离其最远的距离
对于密度最低的值，选取距离其最近的距离

function data_delta=cal_delta(data,data_density)data_len=size(data,1);data_delta=zeros(1,data_len);for idata_len=1:data_lenindex=data_density>data_density(idata_len);%%index中存的是所有大于idata_len密度值的下标if sum(index)~=0data_delta(idata_len)=min(pdist2(data(idata_len,:),data(index,:)));elsedata_delta(idata_len)=max(pdist2(data(idata_len,:),data));end%{两种情况：对于密度最高的值，选取距离其最远的距离对于密度最低的值，选取距离其最近的距离%}end
end

寻找聚类中心点

首先计算决策值，之后进行排序，选择前后项差值较大的点作为疑似中心点，然后对每个疑似中心点找出小于两倍截断距离的疑似中心点并选取其中具有最大密度的点，最后进行去重

function [center,center_index]=find_center(data,data_delta,data_density,cut_dist)R=data_density.*data_delta;%计算决策值figure;plot(R,'*','Color','red')[sort_R,R_index]=sort(R,"descend");%sort_R是排序好的序列，R_index是sort_R中元素在原来的R中的位置gama=abs(sort_R(1:end-1)-sort_R(2:end));%计算sort_R临近的两项之间的距离%disp(gama)[sort_gama,gama_idnex]=sort(gama,"descend");%对差值进行降序排列gmeans=mean(sort_gama(2:end));%求平均值%gmeans=mean(sort_gama);%寻找疑似聚类中心点，疑似聚类中心：第i项比第i+1项的差值大于平均差值，就认为第i项是疑似聚类中心temp_center=data(R_index(gama>gmeans),:);temp_center_index=R_index(gama>gmeans);%进一步筛选中心点temp_center_dist=pdist2(temp_center,temp_center);    temp_center_len=size(temp_center,1);center=[];center_index=[];%判断中心点之间距离是否小于2倍截断距离并中心点去重for icenter_len=1:temp_center_lentemp_index=find(temp_center_dist(icenter_len,:)<2*cut_dist);%返回比2*截断距离小的下标[~,max_density_index]=max(data_density(temp_center_index(temp_index)));%找出符合条件的最大值的索引if sum(center_index==temp_center_index(temp_index(max_density_index)))==0%如果不在center_index中则加入center=[center;temp_center(temp_index(max_density_index),:)];%每个数据是坐标，因此垂直拼接center_index=[center_index,temp_center_index(temp_index(max_density_index))];%{if icenter_len<=1disp(center)end%}end%center(icenter_len,:)=temp_center(temp_index(max_density_index),:);end
end
%{
[A,B]相当于水平拼接A和B，即horzcat(A,B)
[A;B]相当于垂直拼接A和B，即vertcat(A,B)
%}

聚类算法

对于中心点：归于自身
对于非中心点：首先选择密度比自身大的点，然后不断选择其中密度最小的点，判断是否为中心点，是则归于此点，否则继续迭代

function cluster=Clustering(data,center,center_index,data_density)data_len=size(data,1);data_dist=pdist2(data,data);cluster=zeros(1,data_len);% 标记中心点序号for i=1:size(center_index,2)cluster(center_index(i))=i;end% 对数据密度进行降序排序[sort_density,sort_index]=sort(data_density,"descend");for idata_len=1:data_len%判断当前数据点是否被分类if cluster(sort_index(idata_len))==0near=sort_index(idata_len);while 1near_density=find(data_density>data_density(near));%找出密度比near大的点near_dist=data_dist(near,near_density);%选取其中最小值[~,min_index]=min(near_dist);if cluster(near_density(min_index))%若为中心点则可加入，否则不能，继续迭代查找cluster(sort_index(idata_len))=cluster(near_density(min_index));break;elsenear=near_density(min_index);endendendend
end