基于密度的聚类算法DBSCAN.doc

基于密度的聚类算法DBSCAN的分析与实现 64 / 67摘 要DBSCAN是一个比较有代表性的基于密度的聚类算法。它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分成为簇，并可在有“噪声”的空间数据库中发现任意形状的聚类。同样，DBSCAN算法也存在一些缺点。本文对DBSCAN聚类算法进行程序实现，然后对程序和算法进行定量和定性的验证与分析，通过结果分析总结出DBSCAN的优缺点，同时对DBSCAN的一种改进方法进行程序实现。关键字：数据挖掘；聚类；密度聚类；DBSCAN目 录1聚类分析概述12聚类算法的分类13经典的基于密度的聚类算法DBSCAN24DBSCAN算法的具体实现34.1目标实现功能34.2算法的具体流程图34.3数据的输入44.4程序的初始化44.5 DBSCAN命名空间内的类55DBSCAN算法的测试结果分析55.1定量测试65.2定性验证86算法的优缺点107算法的改进118总结11参考文献12附 录13附录1 DBSCAN实现相关程序及数据131)Form1.cs132)DBSCAN.cs193)DataInput.mdb24附录2 k-dist算法相关程序351)dataMan.h352)draw.h353)drawDoc.h364)drawView.h375)MainFrm.h396)Point.h407)Resource.h418)stdafx.h429)targetver.h4310)dataMan.cpp4411)draw.cpp4612)drawDoc.cpp5013)drawView.cpp5314)MainFrm.cpp6015)Point.cpp6316)stdafx.cpp641 聚类分析概述聚类分析是数据挖掘的重要课题之一。所谓聚类，就是将数据对象分成多个类或簇使得在同一类或簇的对象之间具有较高的相似度而不同类或簇的对象之间具有较大的差异度。聚类与分类的不同是数据中要划分的类是事先未知的，类的形成完全是数据驱动的，属于一种无师指导的学习方法。聚类分析已经广泛地应用到诸多领域中，包括模式识别、数据分析、图像处理、推荐系统以及市场研究通过聚类，人们能够识别密集的和稀疏的区域，因而发现全局的分布模式，以及数据属性之间有趣的相互关系。聚类算法还可以作为数据挖掘中其他算法的一个预处理步骤。2 聚类算法的分类聚类分析的算法可以分为划分法（Partitioning Methods）、层次法（Hierarchical Methods）、基于密度的方法（density-based methods）、基于网格的方法（grid-based methods）、基于模型的方法（Model-Based Methods 1. 划分法(partitioning methods)：给定一个有N个元组或者纪录的数据集，分裂法将构造K个分组，每一个分组就代表一个聚类，KN。而且这K个分组满足下列条件：（1） 每一个分组至少包含一个数据纪录；（2）每一个数据纪录属于且仅属于一个分组（注意：这个要求在某些模糊聚类算法中可以放宽）；对于给定的K，算法首先给出一个初始的分组方法，以后通过反复迭代的方法改变分组，使得每一次改进之后的分组方案都较前一次好，而所谓好的标准就是：同一分组中的记录越近越好，而不同分组中的纪录越远越好。使用这个基本思想的算法有：K-MEANS算法、K-MEDOIDS算法、CLARANS算法； 2. 层次法(hierarchical methods)：这种方法对给定的数据集进行层次似的分解，直到某种条件满足为止。具体又可分为“自底向上”和“自顶向下”两种方案。例如在“自底向上”方案中，初始时每一个数据纪录都组成一个单独的组，在接下来的迭代中，它把那些相互邻近的组合并成一个组，直到所有的记录组成一个分组或者某个条件满足为止。代表算法有：BIRCH算法、CURE算法、CHAMELEON算法等； 3. 基于密度的方法(density-based methods):基于密度的方法与其它方法的一个根本区别是：它不是基于各种各样的距离的，而是基于密度的。这样就能克服基于距离的算法只能发现“类圆形”的聚类的缺点。这个方法的指导思想就是，只要一个区域中的点的密度大过某个阀值，就把它加到与之相近的聚类中去。代表算法有：DBSCAN算法、OPTICS算法、DENCLUE算法等； 4. 基于网格的方法(grid-based methods):这种方法首先将数据空间划分成为有限个单元（cell）的网格结构,所有的处理都是以单个的单元为对象的。这么处理的一个突出的优点就是处理速度很快，通常这是与目标数据库中记录的个数无关的，它只与把数据空间分为多少个单元有关。代表算法有：STING算法、CLIQUE算法、WAVE-CLUSTER算法； 5. 基于模型的方法(model-based methods):基于模型的方法给每一个聚类假定一个模型，然后去寻找能个很好的满足这个模型的数据集。这样一个模型可能是数据点在空间中的密度分布函数或者其它。它的一个潜在的假定就是：目标数据集是由一系列的概率分布所决定的。通常有两种尝试方向：统计的方案和神经网络的方案。3 经典的基于密度的聚类算法DBSCAN密度聚类的指导思想：只要一个区域中的点的密度大于某个值就把它添加到与之相邻的类中。DBSCAN算法是密度聚类法中一个具有代表性的算法。下面先介绍几个相关的基本概念：（1）邻域：对于一个给定的对象，其半径为的邻域称为该对象的邻域。（2）核心点：如果一个点的邻域包含minPts（密度阈值）个点，则此点为核心点。如图1（a）中所示的对象p:（3）边界点：在核心点的邻域内，但不满足核心对象的条件的点。如图1（a）中所示的对象q:（4）直接密度可达：如果点P在点q的邻域内而q是一 个核心点，则称点P是从点q直接密度可达。如图1（b）所示:（5）密度可达：给定一个点集M如果存在一个点链p1，p2pn，pl：q，pn=p，对piM，l in，pi+l是从pi关于和minPts直接密度可达的则点P是从点q关于和 minPts间接密度可达。如图1（c）所示（6）密度相连：在给定的对象集D中，对于参数和minPts，如果对象P和对象q都是从对象o密度可达的，那么称对象p和对象q是密度相连的。如图1（d）所示 (a) (b) (c) (d) 图3-1 边界点、直接密度可达、密度可达、密度相连（7）类与噪声：在给定的对象集D中，对于参数和minPts，一个类C满足下面两个条件之一的非空子集：对于任意点p，qD，若qC，并且p从q密度可达，则pC；对于任意点p，qC，p和q是密度相连的。数据库D中不属于任何类的对象为噪声。DBSCAN (Density-Based Spatial Clustering of Application with Noise) 带有噪声的基于密度的空间聚类算法的描述：从任意点开始，判断每个对象是否未归类，在对象未归类的情况下，判断每个对象是不是核心点，然后对核心点的邻域进行查询，搜索所有的从该对象密度可达的对象，形成一个密度连通集，反复执行此过程得到的所有的密度连通集。这个过程是通过广度优先搜索实现的。4 DBSCAN算法的具体实现4.1 目标实现功能根据DBSCAN的具体算法，列出对算法的实现目标要求如下：a) 可以直接调整半径和最小阈值进行聚类。b) 能在窗体中显示点的相对位置，用黑色标记噪声点，另外用红、粉、绿、金黄、紫、蓝、橘红、紫红八种颜色依次轮流对聚类标色。c) 能统计并显示聚类数以及每个聚类的点数。4.2 算法的具体流程图算法流程描述如下：1) 任意选取一个点 p。2) 得到所有从p 关于eps 和 MinPts密度可达的点.3) 如果p 是一个核心对象, 则找到一个聚类.4) 如果p是一个边界点, 没有从p.5) 密度可达的点, DBSCAN 将访问数据库中的下一个点.6) 继续这一过程, 直到数据库中的所有点都被处理.图4-1 算法流程图4.3 数据的输入DataInput.mdb，以坐标的形式存储点的位置，本文根据实际情况，选择了369个点作为输入,具体数据请见附录。4.4 程序的初始化public ArrayList DataPoints = new ArrayList(400); /创建长度为400的 ArrayList数组列表public SortedList count = new SortedList(); /用count存储每个聚类的点数int m_Core_Num=0 /定义并初始化核心对象的数目int m_MinPts; /定义密度阈值double m_eps; /定义邻域半径dp.class_id = 0; /聚类号，其中0为噪声dp.core_tag = false; /核心点标志dp.used_tag = false; /是否使用过的聚类标志4.5 DBSCAN命名空间内的类命名空间中总共有三个类：1) public sealed class DBSCAN 定义一个公共的抽象类DBSCAN算法实现的主要部分2) public class DataPoint定义一个点的类，内含点的属性描述3) public class DBSCANSort:IComparer比较两个对象5 DBSCAN算法的测试结果分析测试的方法分为定量测试和定性测试两部分，其中定量测试目的是验证程序的准确性，而定性测试则是为观察除噪的效果。定量测试的原理是根据特殊点的选取，来观察临界情况下的聚类结果。本例中的数据有一部分是经过计算严格选取的，就是图示中的双层方框。每个方框中，相邻两点的距离是5，两层方框边的间距为10。如下图左上方的双层正方形：图5-1 特殊点的选取5.1 定量测试分为两部分的验证：1) 聚类单框通过聚类的定义，不难分析，要想将一个方框划分成一个聚类，最小的eps为6，对应的最大的Minpts为2。即当eps6时方框不能被聚成一个类，根据点的选取，当eps为6时Minpts最大只能为2，否则也无法聚成一个类。如下图所示：a)b)图5-2聚类单框结果示意图2) 将距离很近的两框同时聚为一类（合并聚类）DBSCAN具有能聚类任意形状点簇的功能，这是因为在以核心对象为准进行聚类的过程中，如果另一个聚类的核心对象如果在此聚类中，两个聚类则被合并为一个聚类，从而使得聚类后的形状不受限制。此例中，如果要讲两层方框聚为一类，同上例分析可知最小eps为11，对应最大Minpts为5。a)b)图5-3合并聚类结果示意图 可见，实验结果与分析的数据相同，从而定量验证了程序的正确性。5.2 定性验证当eps、Minpts取不同的值时，比较聚类效果。图5-4 eps为5，MinPts为3时的聚类效果图5-5 eps为10，MinPts为3时的聚类效果图5-6 eps为15，MinPts为3时的聚类效果图5-6 eps为20，MinPts为3时的聚类效果图5-7 eps为25，MinPts为3时的聚类效果综上所述，DBSCAN能识别任意形状的聚类，并且可以很好地识别噪声，但是对用户定义的参数较敏感， Eps（邻域半径）、MinPts（密度阈值）设置的细微不同将导致聚类结果的较大差异。当点的密度不均匀的时候，聚类效果不好。6 算法的优缺点DBSCAN聚类算法将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分成为簇，并可在有“噪声”的空间数据库中发现任意形状的聚类。 但DBSCAN算法也存在以下不足 ：1. 采用空间索引时，DBSCAN的计算复杂度是O(nlogn)，其中n是数据库中对象的数目。否则，计算复杂度为O(n2)。本算法需扫描整个数据库，对每个点对象都进行一次查询，所以算法的时间复杂度为O（n2）。2. 在聚类过程中，DBSCAN一旦找到一个核心对象，即以该核心对象为中心向外扩展。此过程中核心对象将不断增多，未处理的对象被保留在内存中。若数据库中存在庞大的聚类，将需要很大的内存来存储核心对象信息，其需求难以预料。 3. 由于在DBSCAN算法中变量Eps，MinPts是全局惟一的，当数据分布不均匀时聚类质量较差。4. 对输入参数敏感。确定参数Eps，MinPts困难，若选取不当，将造成聚类质量下降。 7 算法的改进针对DBSCAN对输入参数敏感的问题，我们查阅了相关文献，找到了一种k-dist法，可以解决此问题。k-dist法的核心思想是，利用数据的空间分布特性，将整个数据空间划分为不同密集程度的小分区，发现不同的密度级别，分别对同一个密度区域中的点利用DBSCAN进行聚类，从而得到更符合现实需求的结果。k-dist基本算法如下：1) 确定参数k(确定要计算所有数据对象与它的第k个最邻近的对象之间的距离，为减少计算量，通常取k=4) 2) 读取数据； 3) 计算 k-dist 距离并按从大到小进行排序，结果保存在order数组中； 4) 设定参数 Mindist( 可根据使用环境先确定，也可根据计算出的 k-dist值确定)； 5) 通过计算前后相邻两个数据对象的k-dist距离之差，也就是 KDIi,i +1与 Mindist 的关系找出所有的关键点，保存在 keypoint数组中； 6) 在 keypoint数组中记录得到的关键点在order数组中的标号、二维空间坐标值和对应k-dist的值；用这些关键点区分出不同密度层次的区域； 7) 对每个子数据集分别利用 DBSCAN过程函数进行局部聚类； 8) 输出聚类结果 k-dist法用C+实现的相关程序请见附录。8 总结本文分析了DBSCAN聚类算法的基本思想，用C#对DBSCAN算法进行可视化实现，并通过定量和定性的角度对算法及程序进行验证，即通过对特殊点的聚类情况分析验证程序的准确性，对比不同eps、MinPts值下的聚类效果及除噪效果，从而分析总结出DBSCAN聚类算法的优缺点，并且用C+实现了DBSCAN的一种优化算法即k-dist法。参考文献1.Jiawei Han, Micheline Kamber.数据挖掘概念与技术.机械工业出版社2.毛国君,段立娟,王实,石云.数据挖掘原理与算法.清华大学出版社3.林姿琼,黄伟婷 改进的 DBS CAN空间聚类算法研究 漳州师范学院学报(自然科学版) 4.冯少荣,肖文俊. DBSCAN聚类算法的研究与改进.中国矿业大学学报附 录附录1 DBSCAN实现相关程序及数据 1) Form1.csusing System;using System.Drawing;using System.Collections;using System.ComponentModel;using System.Windows.Forms;using System.Data;using DBSCAN;using System.Data.OleDb;using System.Drawing.Drawing2D;namespace DBSCAN/ / Form1 的摘要说明。/ public class Form1 : System.Windows.Forms.Form/ / 必需的设计器变量。/ private System.ComponentModel.Container components = null;private System.Windows.Forms.Button button1;private System.Windows.Forms.TextBox textBox2;private System.Windows.Forms.Label label1;private System.Windows.Forms.Label label2;private System.Windows.Forms.TextBox textBox1;private System.Windows.Forms.TrackBar trackBar_EPS;private System.Windows.Forms.TrackBar trackBar1;private TextBox textBox3;private System.Windows.Forms.TextBox textBox4;public DBSCAN ds;public Form1()/ Windows 窗体设计器支持所必需的/InitializeComponent();/ TODO: 在 InitializeComponent 调用后添加任何构造函数代码/ / 清理所有正在使用的资源。/ protected override void Dispose( bool disposing )if( disposing )if (components != null) components.Dispose();base.Dispose( disposing );#region Windows 窗体设计器生成的代码/ / 设计器支持所需的方法 - 不要使用代码编辑器修改/ 此方法的内容。/ private void InitializeComponent()this.button1 = new System.Windows.Forms.Button();this.textBox2 = new System.Windows.Forms.TextBox();this.label1 = new System.Windows.Forms.Label();this.label2 = new System.Windows.Forms.Label();this.textBox1 = new System.Windows.Forms.TextBox();this.trackBar_EPS = new System.Windows.Forms.TrackBar();this.trackBar1 = new System.Windows.Forms.TrackBar();this.textBox3 = new System.Windows.Forms.TextBox();this.textBox4 = new System.Windows.Forms.TextBox();(System.ComponentModel.ISupportInitialize)(this.trackBar_EPS).BeginInit();(System.ComponentModel.ISupportInitialize)(this.trackBar1).BeginInit();this.SuspendLayout();/ / button1/ this.button1.Location = new System.Drawing.Point(648, 144);this.button1.Name = button1;this.button1.Size = new System.Drawing.Size(90, 25);this.button1.TabIndex = 0;this.button1.Text = Run;this.button1.Visible = false;this.button1.Click += new System.EventHandler(this.button1_Click);/ / textBox2/ this.textBox2.Location = new System.Drawing.Point(632, 56);this.textBox2.Name = textBox2;this.textBox2.Size = new System.Drawing.Size(120, 21);this.textBox2.TabIndex = 3;this.textBox2.Text = 3;/ / label1/ this.label1.Location = new System.Drawing.Point(496, 24);this.label1.Name = label1;this.label1.Size = new System.Drawing.Size(29, 18);this.label1.TabIndex = 3;this.label1.Text = eps;/ / label2/ this.label2.Location = new System.Drawing.Point(632, 24);this.label2.Name = label2;this.label2.Size = new System.Drawing.Size(48, 17);this.label2.TabIndex = 4;this.label2.Text = MinPts;/ / textBox1/ this.textBox1.Location = new System.Drawing.Point(496, 56);this.textBox1.Name = textBox1;this.textBox1.Size = new System.Drawing.Size(120, 21);this.textBox1.TabIndex = 1;this.textBox1.Text = 15;this.textBox1.TextChanged += new System.EventHandler(this.textBox1_TextChanged);/ / trackBar_EPS/ this.trackBar_EPS.LargeChange = 10;this.trackBar_EPS.Location = new System.Drawing.Point(496, 88);this.trackBar_EPS.Maximum = 50;this.trackBar_EPS.Name = trackBar_EPS;this.trackBar_EPS.Size = new System.Drawing.Size(120, 45);this.trackBar_EPS.TabIndex = 2;this.trackBar_EPS.TickFrequency = 2;this.trackBar_EPS.Value = 15;this.trackBar_EPS.Scroll += new System.EventHandler(this.trackBar_EPS_Scroll);/ / trackBar1/ this.trackBar1.Location = new System.Drawing.Point(632, 96);this.trackBar1.Maximum = 7;this.trackBar1.Name = trackBar1;this.trackBar1.Size = new System.Drawing.Size(120, 45);this.trackBar1.TabIndex = 4;this.trackBar1.Value = 3;this.trackBar1.Scroll += new System.EventHandler(this.trackBar1_Scroll);/ / textBox3/ this.textBox3.BackColor = System.Drawing.Color.WhiteSmoke;this.textBox3.BorderStyle = System.Windows.Forms.BorderStyle.None;this.textBox3.Location = new System.Drawing.Point(608, 232);this.textBox3.Multiline = true;this.textBox3.Name = textBox3;this.textBox3.Size = new System.Drawing.Size(128, 312);this.textBox3.TabIndex = 5;this.textBox3.Text = ;this.textBox3.TextChanged += new System.EventHandler(this.textBox3_TextChanged);/ / textBox4/ this.textBox4.BackColor = System.Drawing.Color.WhiteSmoke;this.textBox4.BorderStyle = System.Windows.Forms.BorderStyle.None;this.textBox4.Location = new System.Drawing.Point(600, 200);this.textBox4.Name = textBox4;this.textBox4.Size = new System.Drawing.Size(120, 14);this.textBox4.TabIndex = 6;this.textBox4.Text = 聚类结果的点数统计：;/ / Form1/ this.AutoScaleBaseSize = new System.Drawing.Size(6, 14);this.ClientSize = new System.Drawing.Size(759, 580);this.Controls.Add(this.textBox4);this.Controls.Add(this.textBox3);this.Controls.Add(this.trackBar1);this.Controls.Add(this.trackBar_EPS);this.Controls.Add(this.label2);this.Controls.Add(this.label1);this.Controls.Add(this.textBox2);this.Controls.Add(this.textBox1);this.Controls.Add(this.button1);this.Name = Form1;this.Text = DBSCAN Algorithms Demo;this.Load += new System.EventHandler(this.Form1_Load);(System.ComponentModel.ISupportInitialize)(this.trackBar_EPS).EndInit();(System.ComponentModel.ISupportInitialize)(this.trackBar1).EndInit();this.ResumeLayout(false);#endregion/ / 应用程序的主入口点。/ STAThreadstatic void Main() Application.Run(new Form1();private void Form1_Load(object sender, System.EventArgs e)OleDbConnection cn = new OleDbConnection();cn.ConnectionString = Provider=Microsoft.JET.OLEDB.4.0; data source= + Environment.CurrentDirectory + .DataInput.mdb;cn.Open();OleDbCommand cmd = new OleDbCommand(Select * From Table1,cn);OleDbDataReader dr = cmd.ExecuteReader();ds = new DBSCAN();while(dr.Read()ds.AddDataPoint(new DataPoint(Convert.ToDouble(drX), Convert.ToDouble(drY);ds.PrepareDBSCAN_Table();dr.Close();cn.Close();button1_Click(this, null);protected override void OnPaint(PaintEventArgs e)Graphics dc= e.Graphics;Pen pen=new Pen(Color.Black,3);foreach(DataPoint dp in ds.DataPoints)pen.Color=this.GetColor(dp.class_id);dc.DrawEllipse(pen,(float)dp.d1+200,(float)dp.d2+200,2,2);public System.Drawing.Color GetColor(int index)Color xColor=Color.Black, Color.Red , Color.Pink, Color.Green, Color.Gold, Color.Purple, Color.Blue, Color.Orange,Color.Plum ;if(index=0)return xColor0;else return xColorindex % 8+1;private void button1_Click(object sender, System.EventArgs e)int a=Convert.ToInt32(this.textBox1.Text);int b=Convert.ToInt32(this.textBox2.Text);ds.BuildCorePoint(a,b);ds.DBSCAN_Cluster();this.Invalidate();textBox3.Text = ; textBox3.Text += 噪声点共有+ds.count.GetByIndex(0) +个对象+ rn;for (int i = 1; i ds.count.Count; i+)textBox3.Text += 第 + i + 个聚类有 + ds.count.GetByIndex(i) +个对象+ rn;private void trackBar_EPS_Scroll(object sender, System.EventArgs e)this.textBox1.Text = trackBar_EPS.Value.ToString();button1_Click(this, null);private void trackBar1_Scroll(object sender, System.EventArgs e)this.textBox2.Text = trackBar1.Value.ToString();button1_Click(this, null);private void textBox3_TextChanged(object sender, EventArgs e)private void textBox1_TextChanged(object sender, System.EventArgs e)2) DBSCAN.csusing System;using System.Collections;namespace DBSCAN/ / Cluster data using DBSCAN (Density-Based Spatical Clustering of Application with Noise) methed/ See Data Mining for further information/ public sealed class DBSCANpublic ArrayList DataPoints = new ArrayList(400);public SortedList count = new SortedList();private ArrayList DP2DP;private int m_Core_Num;private int m_MinPts;private double m_eps;/ / Add DataPoint to DBSCAN module to cluster/ public void AddDataPoint(DataPoint dp)DataPoints.Add(dp);m_Core_Num = 0;m_MinPts = 0;m_eps = 0;public void RemoveAllDataPoints()DataPoints.Clear();DP2DP.Clear();m_Core_Num = 0;m_MinPts = 0;m_eps = 0;public void ResetAllDataPointsState()foreach(DataPoint dp in DataPoints)dp.class_id = 0;dp.core_tag = false;dp.used_tag = false;public void PrepareDBSCAN_Table()int dp_count = DataPoints.Count;DP2DP = new ArrayList(dp_count);for(int i=0;idp_count;i+)/ SortedList use DBSCANSort so that can support duplicate key/ dp_count also include the point itselfDP2DP.Add(new SortedList(new DBSCANSort(), dp_count);SortedList sl;DataPoint dp;for(int i=0;idp_count;i+)sl=(SortedList)DP2DPi;dp=(DataPoint)DataPointsi;for(int j=0;jdp_count;j+)double distance = dp.Distance(DataPoint)DataPointsj);sl.Add(distance, DataPointsj);public int BuildCorePoint(double eps, int MinPts)ResetAllDataPointsState();int core_num = 0;SortedList sl;DataPoint src_dp, des_dp;for(int i=0;iDataPoints.Count;i+)sl=(SortedList)DP2DPi;des_dp=(DataPoint)sl.GetByIndex(MinPts);src_dp=(DataPoint)DataPointsi;if(src_dp.Distance(des_dp)0)m_Core_Num = core_num;m_MinPts = MinPts;m_eps = eps;return core_num;public void DBSCAN_Cluster()DataPoint dp;int sum=0;int temp;count = new SortedList();int current_class_id = 1;for(int i=0;iDataPoints.Count;i+)dp=(DataPoint)DataPointsi;