密度聚类算法报告.doc

1、密度聚类算法报告密度聚类算法报告 1.【摘要】：p 聚类分析p 是数据挖掘的重要方法。该文阐述了基于密度聚类分析p 的基本概念及其经典的算法思想，并提出了一种基于核心点进行聚类的算法。该算法首先对点进行分类，分出核心点、边界点和噪音点。然后采用自下而上的方式对簇进行合并。对所有数据进行分类并合并标记后，给出最后结果图。算法保证了数据处理的完整性。2.密度聚类的相关概念 对于构成簇的每个对象，其Eps邻域包含的对象个数必须不小于一个给定值（MinPts），也就是说其邻域的密度必须不小于某个阈值。下面给出基于密度聚类算法分析p 中的一些定义。直接密度可达：设 p是核心点，如果q在p的Eps邻域内，

2、则称从p出发直接可达q。密度相连：如果样本集合中存在一个对象o ，使得对象p 和q 是从o 关于Eps邻域和MinPts 密度可达的，那么对象p 和q 关于Eps和MinPts 密度相连 。簇：基于密度可达性的最大的密度相连的点的集合称为簇。噪音点：不在任何簇中的对象。3.原理 考察样本集中的某一点o，若o是核心点，则通过区域查询得到该点的邻域，邻域中的点和o同属于一个簇，这些点将作为下一轮的考察对象（即种子点），并通过不断地对种子点进行区域查询来扩展它们所在的簇，直至找到一个完整的簇。然后，依此程序寻找其它的簇。最后剩下的不属于任何类的点即为噪音点。4.算法流程 算法描述：算法：dbscan

3、 输入：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);得到数据的大小 _=(1:m) data;将数据存到_中，并加上标号1->m m,n=size(_);载入数据集的大小 type=zeros(m,1);用于区分核

4、心点1，边界点0和噪音点-1 dealed=zeros(m,1);用于判断该点是否处理过,0表示未处理过,1表示处理过 dis=calDistance(_(:,2:n-1);距离矩阵计算 class=zeros(1,m);颜色分类 number=1;簇号 5.2子函数：计算矩阵中点与点之间的距离 function dis = calDistance( _ ) m,n = size(_); 给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+

5、(_(i,k)-_(j,k).2; end dis(i,j) = sqrt(tmp); dis(j,i) = dis(i,j); end end end 画出Eps和minpots的曲线 data=load(C:Userssin_Deskdatarings.t_t); m,n=size(data);得到数据的大小 _=(1:m) data;将数据存到_中，并加上标号1->m Dis=calDistance(_(:,2:n-1);距离矩阵计算 Dis_4=sort(Dis,2); e=Dis_4(:,4); e=-sort(-e);降序排列 plot(e) a_is(0,100,0,0.5

6、) 5.3确定EPS和MinPts 求出所有点的第5近邻记为dis_5，并将dis_5按照降序排列，找出Eps值相对平缓的点作为Eps，并且Minpts取值为5.如下图5-1.图5-1（数据集rings.t_t）6.算法分析p 本程序采用密度聚类算法（DBSCAN），目的在于过滤低密度区域，发现稠密度样本点。优点：在执行时不需要知道簇的数目，簇的大小，以及可以对任意维度的样本都可以得出良好的结果。并且对噪声有一定的抗干扰能力。缺点：当点的距离都比较接近的时候，无法执行出良好的结果；当数据集的密度是可变的时候，也无法得出良好的结果。7.结果图 本算法运行的结果如图7-1和7-2所示：图7-1（数

7、据集rings.t_t）图7-2（数据集ball.t_t）8.附录代码 for i=1:m if dealed(i)=0 _Temp=_(i,:); D=dis(i,:); ind=find(D1 length(ind)=MinPts+1 type(_Temp(1,1)=1; class(ind)=number; 直接密度可达与密度可达 while isempty(ind)邻域内点不为空执行循环 yTemp=_(ind(1),:); yTemp存第ind（1）个点 dealed(ind(1)=1; ind(1)=; D=dis(yTemp(1,1),:); ind_1=find(D1 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(