- 浏览: 75676 次
最新评论
一 什么是基于密度的聚类算法
由于层次聚类算法和划分式 聚类算往往只能发现凸形的聚类簇。为了弥补这一缺陷,发现各种任意形状的聚类簇,开发出基于密度的聚类算法。这类算法认为,在整个样本空间点中,各目标类 簇是由一群的稠密样本点组成的,而这些稠密样本点被低密度区域(噪声)分割,而算法的目的就是要过滤低密度区域,发现稠密样本点。
二 DBSCAN ( Density-based Spatial Clustering of Applications with Noise )
是一种基于高密度联通区域的聚类算法,它将类簇定义为高密度相连点的最大集合。它本身对噪声不敏感,并且能发现任意形状的类簇。
DBSCAN 中的的几个定义:
Ε 领域:给定对象 半径为 Ε 内的区域称为该对象的 Ε 领域
核心对象:如果给定对象 Ε 领域内的样本点数大于等于 MinPts ,则称该对象为核心对象 。
直接密度可达:对于样本集合 D ,如果样本点 q 在 p 的 Ε 领域内,并且 p 为核心对象,那么对象 q 从对象 p 直接密度可达 。
密度可达:对于样本集合 D ,给定一串样本点 p1 ,p2 ….pn , p= p1 ,q= pn , 假如对象 pi 从 pi-1 直接密度可达,那么对象 q 从对象 p 密度可达 。
密度相连:对于样本集合 D 中的任意一点 O ,如果存在对象 p 到对象 o 密度可达,并且对象 q 到对象 o 密度可达,那么对象 q 到对象 p 密度相连 。
可以发现,密度可达是直接密度可达的传递闭包,并且这种关系是非对称的。密度相连是对称关系。 DBSCAN 目的是找到密度相连对象的最大集合。
Eg: 假设半径 Ε=3 , MinPts=3 ,点 p 的 E 领域中有点 {m,p,p1,p2,o}, 点 m 的 E 领域中有点 {m,q,p,m1,m2}, 点 q 的 E 领域中有点 {q,m}, 点 o 的 E 领域中有点 {o,p,s}, 点 s 的 E 领域中有点 {o,s,s1}.
那么核心对象有 p,m,o,s(q 不是核心对象,因为它对应的 E 领域中点数量等于 2 ,小于 MinPts=3) ;
点 m 从点 p 直接密度可达,因为 m 在 p 的 E 领域内,并且 p 为核心对象;
点 q 从点 p 密度可达,因为点 q 从点 m 直接密度可达,并且点 m 从点 p 直接密度可达;
点 q 到点 s 密度相连,因为点 q 从点 p 密度可达,并且 s 从点 p 密度可达。
三
算法描述
算法: DBSCAN 输入: E — 半径 MinPts — 给定点在 E 领域内成为核心对象的最小领域点数 D — 集合 输出:目标类簇集合 方法: repeat 1) 判断输入点是否为核心对象 2) 找出核心对象的 E 领域中的所有直接密度可达点 util 所有输入点都判断完毕 repeat 针对所有核心对象的 E 领域所有直接密度可达点找到最大密度相连对象集合, 中间涉及到一些密度可达对象的合并。 Util 所有核心对象的 E 领域都遍历完毕 |
四 算法实现
package
com.dbscan;
public class DataPoint
{
private String dataPointName; // 样本点名
private double dimensioin[]; // 样本点的维度
private boolean isKey; //是否是核心对象
public DataPoint(){
}
public DataPoint(double[] dimensioin,String dataPointName,boolean
isKey){
this.dataPointName=dataPointName;
this.dimensioin=dimensioin;
this.isKey=isKey;
}
}
------------
package com.dbscan;
import
java.util.ArrayList;
import
java.util.List;
public class Cluster
{
private List<DataPoint> dataPoints =
new ArrayList<DataPoint>(); //
类簇中的样本点
private String clusterName; //簇名
public List<DataPoint>
getDataPoints() {
return
dataPoints;
}
public void
setDataPoints(List<DataPoint>
dataPoints) {
this.dataPoints = dataPoints;
}
public String getClusterName() {
return
clusterName;
}
public void setClusterName(String clusterName) {
this.clusterName = clusterName;
}
}
------------
package
com.dbscan;
import
java.util.ArrayList;
import
java.util.List;
public class ClusterAnalysis
{
public List<Cluster>
doDbscanAnalysis(List<DataPoint>
dataPoints,
double
radius, int ObjectNum) {
List<Cluster> clusterList=new
ArrayList<Cluster>();
for(int i=0;
i<dataPoints.size();i++){
DataPoint dp=dataPoints.get(i);
List<DataPoint>
arrivableObjects=isKeyAndReturnObjects(dp,dataPoints,radius,ObjectNum);
if(arrivableObjects!=null){
Cluster tempCluster=new Cluster();
tempCluster.setClusterName("Cluster "+i);
tempCluster.setDataPoints(arrivableObjects);
clusterList.add(tempCluster);
}
}
for(int
i=0;i<clusterList.size();i++){
for(int
j=0;j<clusterList.size();j++){
if(i!=j){
Cluster clusterA=clusterList.get(i);
Cluster clusterB=clusterList.get(j);
List<DataPoint>
dpsA=clusterA.getDataPoints();
List<DataPoint>
dpsB=clusterB.getDataPoints();
boolean flag=mergeList(dpsA,dpsB);
if(flag){
clusterList.set(j, new
Cluster());
}
}
}
}
return clusterList;
}
public void
displayCluster(List<Cluster>
clusterList){
if(clusterList!=null){
for(Cluster
tempCluster:clusterList){
if(tempCluster.getDataPoints()!=null&&tempCluster.getDataPoints().size()>0){
System.out.println("----------"+tempCluster.getClusterName()+"----------");
for(DataPoint dp:tempCluster.getDataPoints()){
System.out.println(dp.getDataPointName());
}
}
}
}
}
private double getDistance(DataPoint dp1,DataPoint
dp2){
double
distance=0.0;
double[] dim1=dp1.getDimensioin();
double[] dim2=dp2.getDimensioin();
if(dim1.length==dim2.length){
for(int i=0;i<dim1.length;i++){
double
temp=Math.pow((dim1[i]-dim2[i]), 2);
distance=distance+temp;
}
distance=Math.pow(distance, 0.5);
return distance;
}
return
distance;
}
private
List<DataPoint>
isKeyAndReturnObjects(DataPoint
dataPoint,List<DataPoint>
dataPoints,double radius,int ObjectNum){
List<DataPoint> arrivableObjects=new
ArrayList<DataPoint>();
//用来存储所有直接密度可达对象
for(DataPoint
dp:dataPoints){
double distance=getDistance(dataPoint,dp);
if(distance<=radius){
arrivableObjects.add(dp);
}
}
if(arrivableObjects.size()>=ObjectNum){
dataPoint.setKey(true);
return
arrivableObjects;
}
return null;
}
private
boolean isContain(DataPoint
dp,List<DataPoint>
dps){
boolean flag=false;
String name=dp.getDataPointName().trim();
for(DataPoint tempDp:dps){
String tempName=tempDp.getDataPointName().trim();
if(name.equals(tempName)){
flag=true;
break;
}
}
return flag;
}
private
boolean mergeList(List<DataPoint>
dps1,List<DataPoint>
dps2){
boolean
flag=false;
if(dps1==null||dps2==null||dps1.size()==0||dps2.size()==0){
return flag;
}
for(DataPoint dp:dps2){
if(dp.isKey()&&isContain(dp,dps1)){
flag=true;
break;
}
}
if(flag){
for(DataPoint
dp:dps2){
if(!isContain(dp,dps1)){
DataPoint tempDp=new
DataPoint(dp.getDimensioin(),dp.getDataPointName(),dp.isKey());
dps1.add(tempDp);
}
}
}
return flag;
}
public
static void main(String[] args){
ArrayList<DataPoint> dpoints = new
ArrayList<DataPoint>();
double[] a={2,3};
double[] b={2,4};
double[] c={1,4};
double[] d={1,3};
double[] e={2,2};
double[] f={3,2};
double[] g={8,7};
double[] h={8,6};
double[] i={7,7};
double[] j={7,6};
double[] k={8,5};
double[] l={100,2};//孤立点
double[] m={8,20};
double[] n={8,19};
double[] o={7,18};
double[] p={7,17};
double[] q={8,21};
dpoints.add(new DataPoint(a,"a",false));
dpoints.add(new DataPoint(b,"b",false));
dpoints.add(new DataPoint(c,"c",false));
dpoints.add(new DataPoint(d,"d",false));
dpoints.add(new DataPoint(e,"e",false));
dpoints.add(new DataPoint(f,"f",false));
dpoints.add(new DataPoint(g,"g",false));
dpoints.add(new DataPoint(h,"h",false));
dpoints.add(new DataPoint(i,"i",false));
dpoints.add(new DataPoint(j,"j",false));
dpoints.add(new DataPoint(k,"k",false));
dpoints.add(new DataPoint(l,"l",false));
dpoints.add(new DataPoint(m,"m",false));
dpoints.add(new DataPoint(n,"n",false));
dpoints.add(new DataPoint(o,"o",false));
dpoints.add(new DataPoint(p,"p",false));
dpoints.add(new DataPoint(q,"q",false));
ClusterAnalysis ca=new ClusterAnalysis();
List<Cluster>
clusterList=ca.doDbscanAnalysis(dpoints, 2, 4);
ca.displayCluster(clusterList);
}
}
}
发表评论
-
话题监测与发现之热点新闻发现技术
2013-01-25 09:51 3769最近在帮朋友做一 ... -
【转载】推荐几个数据分析网站
2013-01-04 09:45 1319From http://blog.sina.com.cn/ ... -
数据挖掘只言片语
2013-01-04 09:44 1996写了好几篇关于数据挖掘算法的帖子,都属于技术上的细节贴。这篇文 ... -
【转载】如何预测用户query意图
2013-01-03 17:57 1414From http://www.searchtb.com/20 ... -
关联规则(二)强关联规则一定就是用户感兴趣的规则吗
2012-12-28 08:58 2473关联规则算法 Apriori 表明 , 当蕴含式 A ... -
关联规则(一)Apriori算法
2012-12-28 08:58 78651. 挖掘关联规 ... -
聚类分析(七)离群点分析
2012-12-28 08:57 5107一、 ... -
聚类分析(六)基于密度的聚类算法 — OPTICS
2012-12-28 08:57 16401 什么是 OPTICS 算法 在前面介绍的 ... -
数据分布倾斜性风险浅析
2012-12-28 08:56 995数据分布倾斜性指的是数据分布过度集中于数据空间的某端, ... -
聚类分析(四)层次聚类算法
2012-12-27 15:31 3721层次聚类算法: 前面 ... -
聚类分析(三) K中心点算法(k-mediods)
2012-12-27 15:28 5104K 中心点算法( K-medoids ) ... -
聚类分析(二) K-MEANS
2012-12-27 15:24 2180K-means 算法 一般情况,聚类算法可以划分为 ... -
聚类分析(一) 什么是聚类分析
2012-12-27 15:22 1944将一群物理对 ...
相关推荐
基于密度的聚类算法DBSCAN,matlab官方程序,欢迎下载。
最近在Science上的一篇基于密度的聚类算法《Clustering by fast search and find of density peaks》引起了大家的关注(在我的博文“论文中的机器学习算法——基于密度峰值的聚类算法”中也进行了中文的描述)。...
CSDN海神之光上传的代码均可运行,亲测可用,直接替换数据即可,适合小白;1、代码压缩包内容主函数:main.m;调用函数:其他m文件;无需运行 运行结果效果图;2、代码运行版本Matlab 2019b;若运行有误,根据提示...
**基于密度的聚类算法——DBSCAN** DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一种非监督学习的聚类算法,它以其独特的密度连接概念,在数据挖掘领域有着广泛的应用。DBSCAN能够...
java版的DBSCAN聚类算法实现,是典型的算法思路实现,遍历未访问的所有点,如果是核心点,就新建一个簇,然后遍历其邻域内的所有点集A,不断扩展,如果簇内的点时核心点,就将其邻域所有点纳入点集A,并从点集移除已...
DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一种基于密度的聚类算法,它能够发现任意形状的聚类,并且对噪声具有很好的鲁棒性。这个算法与传统的聚类方法如K-Means不同,它不需要预先...
DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一种基于密度的空间聚类算法,它能够发现任意形状的聚类,并且对噪声不敏感。在C++中实现DBSCAN,需要理解其核心概念和步骤。 首先,...
这几天由于工作需要,对DBSCAN聚类算法进行了C++的实现。时间复杂度O(n^2),主要花在算每个点领域内的点上。算法很简单,现共享大家参考,也希望有更多交流。 数据点类型描述如下: 代码如下:#include using ...
DBSCAN聚类(密度聚类算法)-基于密度的聚类算法-聚类可视化-MATLAB代码 本代码详细图文介绍,请点击博客主页查找对应文章查看。可保证运行,运行失败或报错免费解决。 DBSCAN (Density-Based Spatial Clustering of ...
DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一种基于密度的空间聚类算法,它能够发现任意形状的聚类,并且对噪声具有很好的处理能力。在MATLAB中实现DBSCAN,可以帮助我们更方便地...
DBSCAN 聚类,是一种基于密度的聚类算法,它类似于均值漂移,DBSCAN 与其他聚类算法相比有很多优点,首先,它根本不需要固定数量的簇。它也会异常值识别为噪声,而不像均值漂移,即使数据点非常不同,也会简单地将...
"基于密度的聚类算法 -- DBSCAN" 基于密度的聚类算法是一种常用的聚类算法,它可以发现任意形状的聚类簇,而不仅仅是凸形的聚类簇。DBSCAN(Density-based Spatial Clustering of Applications with Noise)是一种...
DBSCAN是一种基于密度的聚类算法,它的核心思想是通过考察数据点之间的邻域关系来定义聚类。它不依赖于预先设定的类别数量,而是根据数据点的密度分布自动识别簇。DBSCAN的主要参数包括: 1. **ε(epsilon)邻域**...
总之,DBSCAN聚类算法是基于密度的一种强大工具,能够处理复杂的数据分布,而"**dbscan.m**"文件提供了在MATLAB环境中实现这一算法的可能性,使得用户可以对自定义数据集进行聚类分析。通过调整参数,可以适应各种...
基于密度的聚类算法----DBSCAN算法的代码实现python
DBSCAN是一种基于密度的聚类算法,能发现任意形状的簇,并且对噪声和异常值具有很好的鲁棒性。其主要概念是: - 密度可达:如果数据点A可以直接到达数据点B(通过一系列密度可达的点),则A和B属于同一簇。 - ...
基于密度的聚类算法dbscan,是最新的聚类的算法。matlab程序
DBSCAN,全称为Density-Based Spatial Clustering of Applications with Noise(基于密度的空间聚类应用与噪声),是一种在数据挖掘领域广泛应用的无监督学习聚类算法。它与其他聚类算法如K-means不同,不依赖于预先...
最近研究聚类算法,自己写了个DBSCAN算法,数据存在文本文档中,我的数据是二维的空间坐标……