《dbscan算法实验报告》由会员分享，可在线阅读，更多相关《dbscan算法实验报告（11页珍藏版）》请在金锄头文库上搜索。
1、一 算法概述1. 密度聚类原理DBSCAN 是一种基于密度的聚类算法，这类密度聚类算法一般假 定类别可以通过样本分布的紧密程度决定。同一类别的样本，他们之 间的紧密相连的，也就是说，在该类别任意样本周围不远处一定有同 类别的样本存在。通过将紧密相连的样本划为一类，这样就得到了一个聚类类别。 通过将所有各组紧密相连的样本划为各个不同的类别，则我们就得到 了最终的所有聚类类别结果。2. DBSCAN 密度定义DBSCAN是基于一组邻域来描述样本集的紧密程度的，参数(, MinPts)用来描述邻域的样本分布紧密程度。其中，6描述了某一样本 的邻域距离阈值，MinPts描述了某一样本的距离为6的邻域中
2、样本个 数的阈值。假设我的样本集是D=(x1,x2xm),则DBSCAN具体的密度 描述定义如下：1) 6-邻域：对于xjWD,其6-邻域包含样本集D中与xj的 距离不大于6的子样本集，即N6(xj)=xiD | distance(xifxj)MinPts，将样 本X/加入核心对象样本集合：0=0 U xj3) 如果核心对象集合 0=0，则算法结束，否则转入步骤 4.4) 在核心对象集合0中，随机选择一个核心对象0，初始 化当前簇核心对象队列0cur=o,初始化类别序号k=k+1，初始化当 前簇样本集合Ck=o,更新未访问样本集合二-05) 如果当前簇核心对象队列0cur=0，则当前聚类簇Ck
3、生成完毕，更新簇划分C=C1,C2,.,Ck,更新核心对象集合0=0-Ck， 转入步骤 3。6) 在当前簇核心对象队列0cur中取出一个核心对象0打通 过邻域距离阈值6找出所有的邻域子样本集Ne(o)，令二Ne(o)Q, 更新当前簇样本集合Ck=CkUA,更新未访问样本集合=-,更新 0cur=0curU (Ne(o,)n0)，转入步骤 5.输出结果为：簇划分 C=C1,C2,.,Ck二 实验目标算法：DBScan，基于密度的聚类算法输入：D： 一个包含n个数据的数据集r：半径参数minPts：领域密度阈值 输出：基于密度的聚类集合三 实验步骤标记D中所有的点为unvisted for eac
4、h p in Dif p.visit = unvisted找出与点p距离不大于r的所有点集合NIf N.size() =minPts将集合N加入集合N中去 End ifElseIf p未被聚到某个簇将p聚到当前簇If p被标记为噪声点将p取消标记为噪声点End If End IfEnd IfEnd forEnd ifEnd ifEnd for四 代码实现1. Point.java 定义点，其中距离计算采用欧式距离public class Point private double x;private double y;private boolean isVisit;private int clu
5、ster;private boolean isNoised;public Point(double x,double y) this.x = x;this.y = y; this.isVisit = false; this.cluster = 0; this.isNoised = false;public double getDistance(Point point) return Math.sqrt(x-point.x)*(x-point.x)+(y-point.y)*(y- point.y);public void setX(double x) this.x = x;public doub
6、le getX() return x;public void setY(double y) this.y = y;public double getY() return y;public void setVisit(boolean isVisit) this.isVisit = isVisit;public boolean getVisit() return isVisit;public int getCluster() return cluster;public void setNoised(boolean isNoised) this.isNoised = isNoised;public
7、void setCluster(int cluster) this.cluster = cluster;public boolean getNoised() return this.isNoised;Overridepublic String toString() return x+ +y+ +cluster+ +(isNoised?1:0); 2. DBScan.java算法实现类public class DBScan private double radius;private int minPts;public DBScan(double radius,int minPts) this.r
8、adius = radius; this.minPts = minPts;public void process(ArrayList points) int size = points.size();int idx = 0;int cluster = 1; while (idxsize) Point p = points.get(idx+); /choose an unvisited point if (!p.getVisit() p.setVisit(true);/set visited ArrayList adjacentPoints = getAdjacentPoints(p, poin
9、ts);/set the point which adjacent points less than minPts noisedif (adjacentPoints != null & adjacentPoints.size() minPts) p.setNoised(true); else p.setCluster(cluster);for (int i = 0; i adjacentPoints.size(); i+) Point adjacentPoint = adjacentPoints.get(i); /only check unvisited point, cause only u
10、nvisited have the chance to add new adjacent pointsif (!adjacentPoint.getVisit() adjacentPoint.setVisit(true); ArrayList adjacentAdjacentPoints = getAdjacentPoints(adjacentPoint, points);/add point which adjacent points not less than minPts noisedif (adjacentAdjacentPoints != null & adjacentAdjacent
11、Points.size() = minPts) adjacentPoints.addAll(adjacentAdjacentPoints); /add point which doest not belong to any clusterif (adjacentPoint.getCluster() = 0) adjacentPoint.setCluster(cluster); /set point which marked noised before non-noisedif (adjacentPoint.getNoised() adjacentPoint.setNoised(false); cluster+;private ArrayList getAdjacentPoints(Point centerPoint,ArrayList points) ArrayList adjacentPoints = new ArrayList(); for (Point p:points) /include centerPoint itselfdouble distance = centerPoint.getDistance(p); if (distance=radius) ad
