资源描述：
《dbscan算法实验报告.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、一．算法概述1.密度聚类原理 DBSCAN是一种基于密度的聚类算法，这类密度聚类算法一般假定类别可以通过样本分布的紧密程度决定。同一类别的样本，他们之间的紧密相连的，也就是说，在该类别任意样本周围不远处一定有同类别的样本存在。 通过将紧密相连的样本划为一类，这样就得到了一个聚类类别。通过将所有各组紧密相连的样本划为各个不同的类别，则我们就得到了最终的所有聚类类别结果。2.DBSCAN密度定义 DBSCAN是基于一组邻域来描述样本集的紧密程度的，参数(ϵ,MinPts)用来描述邻域的样本分布紧密程度。其中，ϵ描述了某一样本的邻域距离阈值，Min
2、Pts描述了某一样本的距离为ϵ的邻域中样本个数的阈值。假设我的样本集是D=(x1,x2,...,xm),则DBSCAN具体的密度描述定义如下： 1）ϵ-邻域：对于xj∈D，其ϵ-邻域包含样本集D中与xj的距离不大于ϵ的子样本集，即Nϵ(xj)={xi∈D
3、distance(xi,xj)≤ϵ},这个子样本集的个数记为
4、Nϵ(xj)
5、 2)核心对象：对于任一样本xj∈D，如果其ϵ-邻域对应的Nϵ(xj)至少包含MinPts个样本，即如果
6、Nϵ(xj)
7、≥MinPts，则xj是核心对象。 3）密度直达：如果xi位于xj的ϵ-邻域中，且
8、xj是核心对象，则称xi由xj密度直达。注意反之不一定成立，即此时不能说xj由xi密度直达,除非且xi也是核心对象。 4）密度可达：对于xi和xj,如果存在样本样本序列p1,p2,...,pT,满足p1=xi,pT=xj,且pt+1由pt密度直达，则称xj由xi密度可达。也就是说，密度可达满足传递性。此时序列中的传递样本p1,p2,...,pT−1均为核心对象，因为只有核心对象才能使其他样本密度直达。注意密度可达也不满足对称性，这个可以由密度直达的不对称性得出。 5）密度相连：对于xi和xj,如果存在核心对象样本xk，使xi和xj均由x
9、k密度可达，则称xi和xj密度相连。注意密度相连关系是满足对称性的。3.DBSCAN密度聚类思想 DBSCAN的聚类定义很简单：由密度可达关系导出的最大密度相连的样本集合，即为我们最终聚类的一个类别，或者说一个簇。 这个DBSCAN的簇里面可以有一个或者多个核心对象。如果只有一个核心对象，则簇里其他的非核心对象样本都在这个核心对象的ϵ-邻域里；如果有多个核心对象，则簇里的任意一个核心对象的ϵ-邻域中一定有一个其他的核心对象，否则这两个核心对象无法密度可达。这些核心对象的ϵ-邻域里所有的样本的集合组成的一个DBSCAN聚类簇。 4.
10、DBSCAN聚类算法 下面我们对DBSCAN聚类算法的流程做一个总结。 输入：样本集D=(x1,x2,...,xm)，邻域参数(ϵ,MinPts),样本距离度量方式 输出：簇划分C. 1）初始化核心对象集合Ω=∅,初始化聚类簇数k=0，初始化未访问样本集合Γ=D, 簇划分C=∅ 2)对于j=1,2,...m,按下面的步骤找出所有的核心对象： a)通过距离度量方式，找到样本xj的ϵ-邻域子样本集Nϵ(xj) b)如果子样本集样本个数满足
11、Nϵ(xj)
12、≥MinPts，将样本xj加入核心对象样本集合：
13、Ω=Ω∪{xj} 3）如果核心对象集合Ω=∅，则算法结束，否则转入步骤4. 4）在核心对象集合Ω中，随机选择一个核心对象o，初始化当前簇核心对象队列Ωcur={o},初始化类别序号k=k+1，初始化当前簇样本集合Ck={o},更新未访问样本集合Γ=Γ−{o} 5）如果当前簇核心对象队列Ωcur=∅，则当前聚类簇Ck生成完毕,更新簇划分C={C1,C2,...,Ck},更新核心对象集合Ω=Ω−Ck， 转入步骤3。 6）在当前簇核心对象队列Ωcur中取出一个核心对象o′,通过邻域距离阈值ϵ找出所有的ϵ-邻域子样本集Nϵ(o′)，
14、令Δ=Nϵ(o′)∩Γ,更新当前簇样本集合Ck=Ck∪Δ,更新未访问样本集合Γ=Γ−Δ, 更新Ωcur=Ωcur∪(Nϵ(o′)∩Ω)，转入步骤5. 输出结果为： 簇划分C={C1,C2,...,Ck}一．实验目标算法：DBScan，基于密度的聚类算法输入：D：一个包含n个数据的数据集r：半径参数minPts：领域密度阈值输出：基于密度的聚类集合二．实验步骤标记D中所有的点为unvistedforeachpinDifp.visit=unvisted找出与点p距离不大于r的所有点集合NIfN.size()15、oreachp'inNIfp'.visit==unvisted找出与点p距离不大于r的所有点集合N'IfN'.size()
