密度聚类算法报告
时间：2021-04-20 10:05:10 来源：勤学考试网 本文已影响 人 
密度聚类算法报告 1. 摘要 聚类分析是数据挖掘的重要方法。该文阐述了基于密度聚类分析的基本概念及其经典的算法思想，并提出了一种基于核心点进行聚类的算法。该算法首先对点进行分类，分出核心点、边界点和噪音点。然后采用自下而上的方式对簇进行合并。对所有数据进行分类并合并标记后，给出最后结果图。算法保证了数据处理的完整性。
2. 密度聚类的相关概念 对于构成簇的每个对象，其Eps邻域包含的对象个数必须不小于一个给定值（MinPts），也就是说其邻域的密度必须不小于某个阈值。下面给出基于密度聚类算法分析中的一些定义。
直接密度可达：设 p是核心点，如果q在p的Eps邻域内，则称从p出发直接可达q。
密度相连：如果样本集合中存在一个对象o ，使得对象p 和q 是从o 关于Eps邻域和MinPts 密度可达的，那么对象p 和q 关于Eps和MinPts 密度相连 。
簇：基于密度可达性的最大的密度相连的点的集合称为簇。
噪音点：不在任何簇中的对象。
3. 原理 考察样本集中的某一点o，若o是核心点，则通过区域查询得到该点的邻域，邻域中的点和o同属于一个簇，这些点将作为下一轮的考察对象（即种子点），并通过不断地对种子点进行区域查询来扩展它们所在的簇，直至找到一个完整的簇。然后，依此程序寻找其它的簇。最后剩下的不属于任何类的点即为噪音点。
4. 算法流程 算法描述：
算法：
dbscan 输入：
Eps—半径。
MinPts—给定点在Eps邻域内成为核心对象的最小邻域点数。
数据集。
输出：
聚成的簇的图形。
1. Repeat 2. 从数据集中抽取一个未处理的点；
3. If 该点为核心点 Then找出该点密度可达的点，构成一个簇；
4. Else goto 2；
5. 簇外的点都标记成噪声；
6. Until 所有的点都被处理过；
5.输入函数和子函数 5.1输入函数：
MinPts=5; %阈值 Eps=1; %半径 [m,n]=size(data);%得到数据的大小 x=[(1:m)＇ data];%将数据存到x中，并加上标号1->m [m,n]=size(x);%载入数据集的大小 type=zeros(m,1);%用于区分核心点1，边界点0和噪音点-1 dealed=zeros(m,1);%用于判断该点是否处理过,0表示未处理过,1表示处理过 dis=calDistance(x(:,2:n-1));%距离矩阵计算 class=zeros(1,m);%颜色分类 number=1;%簇号 5.2子函数：
% 计算矩阵中点与点之间的距离 function [ dis ] = calDistance( x ) [m,n] = size(x); %给m，n赋值 dis = zeros(m,m); %距离矩阵 for i = 1:m %计算点i和点j之间的欧式距离 for j = i:m tmp =0; for k = 1:n %n维循环 tmp = tmp+(x(i,k)-x(j,k)).^2; end dis(i,j) = sqrt(tmp); dis(j,i) = dis(i,j); end end end % 画出Eps和minpots的曲线 data=load(＇C:＼Users＼sinx＼Desktop＼data＼rings.txt＇); [m,n]=size(data);%得到数据的大小 x=[(1:m)＇ data];%将数据存到x中，并加上标号1->m Dis=calDistance(x(:,2:n-1));%距离矩阵计算 Dis_4=sort(Dis,2); e=Dis_4(:,4)＇; e=-sort(-e);%降序排列 plot(e) axis([0,100,0,0.5]) 5.3确定EPS和MinPts 求出所有点的第5近邻记为dis_5，并将dis_5按照降序排列，找出Eps值相对平缓的点作为Eps，并且Minpts取值为5. 如下图5-1. 图5-1（数据集rings.txt） 6.算法分析 本程序采用密度聚类算法（DBSCAN），目的在于过滤低密度区域，发现稠密度样本点。
优点：在执行时不需要知道簇的数目，簇的大小，以及可以对任意维度的样本都可以得出良好的结果。并且对噪声有一定的抗干扰能力。
缺点：当点的距离都比较接近的时候，无法执行出良好的结果；
当数据集的密度是可变的时候，也无法得出良好的结果。
7.结果图 本算法运行的结果如图7-1和7-2所示：
图7-1（数据集rings.txt） 图7-2（数据集ball.txt） 8. 附录代码 for i=1:m if dealed(i)==0 xTemp=x(i,:); D=dis(i,:); ind=find(D<=Eps); if length(ind)>1 && length(ind)<MinPts+1 type(i)=0; class(i)=0; %噪音点 if length(ind)==1 type(i)=-1; class(i)=-1; dealed(i)=1; end %核心点 if length(ind)>=MinPts+1 type(xTemp(1,1))=1; class(ind)=number; %直接密度可达与密度可达 while ~isempty(ind)%邻域内点不为空执行循环 yTemp=x(ind(1),:); %yTemp存第ind（1）个点 dealed(ind(1))=1; ind(1)=[]; D=dis(yTemp(1,1),:); ind_1=find(D<=Eps); if length(ind_1)>1 class(ind_1)=number; if length(ind_1)>=MinPts+1 type(yTemp(1,1))=1; for j=1:length(ind_1) if dealed(ind_1(j))==0 dealed(ind_1(j))=1; ind=[ind ind_1(j)]; class(ind_1(j))=number; end end else %该点不能扩展 type(yTemp(1,1))=0; end end end number=number+1; end end end ind_2=find(class==0); class(ind_2)=-1; type(ind_2)=-1;
