下载文档原格式
DBSCAN算法原理DBSCAN（密度聚类算法）是一种基于密度的聚类算法，与传统的基于距离的聚类算法（如K-means）相比具有更好的鲁棒性和可扩展性。
DBSCAN算法的核心思想是根据数据点的密度来进行聚类，而不是根据数据点之间的距离。
本文将详细介绍DBSCAN算法的原理及其实现步骤。
一、算法原理DBSCAN算法根据数据点的密度将数据分为三类：核心点（core point）、边界点（border point）和噪音点（noise point）。
核心点是指在半径为ε内至少包含MinPts个数据点的点，其中MinPts为用户事先指定的一个参数，ε为数据点之间的距离阈值。
边界点是指在半径为ε内没有足够数量的数据点，但它相邻的核心点的总数超过了MinPts的点。
噪音点，即既不是核心点也不是边界点的点。
DBSCAN算法的基本原理如下：1.选择一个未被标记的数据点P作为当前核心点；2.判断当前核心点的ε-邻域（即半径为ε内的所有数据点）中是否包含至少MinPts个数据点，如果是则构成一个簇，所有位于ε-邻域内的点都被标记为该簇的成员；如果否，则将当前核心点标记为噪音点；3.重复步骤2，直到所有的数据点都被标记为一些簇的成员或噪音点。
二、算法步骤1.初始化：设置半径ε和MinPts的值，以及数据集D；2.选择一个未被标记的数据点P作为当前核心点；3.判断当前核心点的ε-邻域是否包含至少MinPts个数据点；-如果是，则创建一个新簇，并将当前核心点P添加到该簇中，并将ε-邻域内的所有点添加到该簇中；-如果否，则标记当前核心点P为噪音点。
4.重复步骤3，直到所有的数据点都被处理过。
5.输出所有的簇。
三、算法特点与优势1.相比于基于距离的聚类算法，DBSCAN具有更好的可扩展性和鲁棒性，可以处理具有不同密度的聚类和噪音点；2.DBSCAN不需要预先指定簇的数量，可以发现任意形状的簇；3. DBSCAN算法的时间复杂度为O(nlogn)，适用于大规模数据集。
r型聚类算法r型聚类算法聚类算法是一种常用的数据挖掘技术，通过对数据进行分组，使得同一组内的数据相似度较高，而不同组之间的数据相似度较低。
其中，r型聚类算法是一种基于密度的聚类算法，能够有效地识别出复杂的聚类结构。
一、引言在数据挖掘和机器学习领域，聚类是一项重要任务。
聚类算法的目标是将数据集划分成不同的组，使得同一组内的数据具有较高的相似度，而不同组之间的数据具有较低的相似度。
r型聚类算法是一种热门的聚类算法，具有高效、准确的特点，被广泛应用于各种领域。
二、r型聚类算法原理r型聚类算法基于密度的概念，通过计算数据点周围的点的密度来确定聚类结构。
其核心思想是找到具有高密度的局部区域，这些区域被认为是聚类的中心。
1. 密度定义r型聚类算法中，密度被定义为某个点周围半径为r的圆内包含的点的个数。
密度越大，表示该点周围的数据点越密集。
2. 核心对象核心对象是指在半径为r的圆内包含的点的个数大于等于某个阈值MinPts的点。
核心对象是聚类算法的关键。
3. 直接密度可达(Directly Density Reachable)在r型聚类算法中，直接密度可达是指对于两个点p和q来说，如果q在p的r-领域内，并且p是一个核心对象，那么就称q是直接密度可达于p的。
这个关系是聚类的基础。
4. 密度可达(Density Reachable)对于两个点p和q来说，如果存在一条点的序列p1,p2,...,pn，使得p1=p，pn=q，并且pi+1是pi的直接密度可达点，那么就称q是密度可达于p的。
5. 密度相连(Density Connected)如果存在一个点o，使得点p和q对于o来说是密度可达的，那么称p和q是密度相连的。
密度相连是一种传递关系，能够将具有相似密度的点连接在一起。
三、算法步骤r型聚类算法的具体步骤如下：1. 初始化：设置半径r和最小密度阈值MinPts。
2. 寻找核心对象：遍历数据集中的每一个点，计算其半径为r的圆内包含的点的个数，如果大于等于MinPts，则将其标记为核心对象。
ticc多元时间序列聚类算法的过程和原理一、引言ticc多元时间序列聚类算法是一种广泛应用于数据挖掘和机器学习领域的聚类算法，旨在将具有相似性的多元时间序列数据分组，以便更好地理解和分析数据。
本文将详细介绍ticc多元时间序列聚类算法的过程和原理。
二、算法概述ticc多元时间序列聚类算法是一种基于密度的聚类算法，通过不断地迭代优化，将具有相似性的多元时间序列数据分组，并形成稳定的聚类结构。
该算法的核心思想是将相似的多元时间序列数据分配给同一聚类，从而揭示数据间的内在关系和模式。
三、过程详解1.预处理：首先对多元时间序列数据进行预处理，包括清洗数据、缺失值填补、时间序列重构等操作，确保数据的准确性和完整性。
2.特征提取：根据多元时间序列数据的特性，提取出相关的特征，如均值、方差、周期性等，以便后续的聚类分析。
3.相似性计算：采用适当的相似性度量方法，如欧几里得距离、余弦相似性等，计算多元时间序列数据之间的相似性。
4.划分聚类：将数据划分为多个聚类，每个聚类包含一组相似性较高的多元时间序列数据。
5.调整聚类：根据划分的聚类结果，调整聚类数目和聚类位置，以获得最佳的聚类效果。
6.输出结果：将最终的聚类结果输出，以便进一步的分析和利用。
四、原理阐述1.密度感知：ticc多元时间序列聚类算法不仅考虑距离，还考虑数据的密度。
通过计算每个数据点周围的邻居数量和密度，可以更好地发现局部聚集的结构。
2.动态规划：ticc多元时间序列聚类算法采用动态规划的思想，通过逐步优化聚类结果，避免全局搜索的复杂性，提高算法的效率和准确性。
3.多样性考虑：ticc多元时间序列聚类算法不仅关注聚类的数量，还关注聚类的多样性。
通过评估聚类的内部相似性和差异性，可以获得更丰富、更真实的聚类结果。
4.适应性调整：ticc多元时间序列聚类算法具有一定的适应性，可以根据不同的数据集和需求，调整算法的参数和策略，以获得最佳的聚类效果。
五、总结ticc多元时间序列聚类算法是一种高效、准确的时间序列聚类算法，适用于大规模、复杂的数据集。
密度聚类（Density-Based Clustering）是一种基于密度的聚类算法，其主要思想是将样本空间划分为密度相连的区域，并将密度较大的区域划分为一个簇。
相比于传统的基于距离的聚类算法，密度聚类对簇形状和大小的假设更为宽松，能够更好地适应各种形状和密度不均匀的簇。
MATLAB作为一种强大的科学计算工具，提供了丰富的聚类算法实现，包括基于密度的聚类算法。
本文将针对MATLAB中基于密度的聚类算法的实现与使用进行介绍，分为以下几个方面：1.密度聚类算法的原理密度聚类算法的核心是基于样本点的密度来划分簇。
需要定义一个邻域的大小（ϵ）和邻域中最小样本点的个数（MinPts），然后通过计算每个样本点的密度来找到核心对象（密度大于MinPts）及其直接密度可达的样本点，最终将这些样本点划分为一个簇。
对于密度相连的簇，会被合并为一个整体。
2.MATLAB中基于密度的聚类算法实现MATLAB中提供了基于密度的聚类算法的实现，主要包括DBSCAN （Density-Based Spatial Clustering of Applications with Noise）和OPTICS（Ordering Points To Identify the Clustering Structure）两种算法。
其中，DBSCAN是一种基于密度的聚类算法，并且对样本点的簇结构进行了良好的定义。
OPTICS算法是对DBSCAN的扩展，通过计算样本点的可达距离将簇进行了有序排列，并能够有效地处理各向异性的数据。
3.基于密度的聚类算法在MATLAB中的使用在MATLAB中，可以借助Statistics and Machine Learning Toolbox提供的函数来实现基于密度的聚类算法。
通过使用fitcknn函数可以构建基于密度的K近邻分类器，利用knnsearch函数可以对新样本进行分类预测。
4.基于密度的聚类算法的优缺点相比于传统的基于距离的聚类算法，基于密度的聚类算法能够更好地适应各种形状和密度不均匀的簇。
dbs算法的原理DBSCAN（Density-Based Spatial Clustering of Applicationswith Noise）是一种基于密度的聚类算法，用于在无监督学习中对数据集进行聚类。
与传统的聚类算法（如K-means）相比，DBSCAN能够发现任意形状的聚类，并且能够自动检测和过滤噪声数据点。
DBSCAN的原理主要包括密度可达、核心对象、直接密度可达和密度可达等概念。
1. 密度可达（Density Reachability）：DBSCAN通过定义数据点之间的密度可达关系来判断数据点是否属于一个聚类。
对于给定的一个数据点p和半径ε，如果存在一个数据点q，q在半径ε内，并且存在一个由p到q的无限长的路径，该路径上的每一个数据点都在半径ε内，则称p密度可达q。
密度可达是一种自动适应密度的测量方式。
2. 核心对象（Core Object）：对于给定的一个数据点p，如果p在半径ε内至少有最小样本数MinPts个数据点，则称p是一个核心对象。
核心对象是聚类形成的关键，它可以直接密度可达它的所有数据点并构成一个聚类。
3. 直接密度可达（Directly Density Reachable）：对于给定的两个数据点p和q，如果p在半径ε内，在半径ε内存在一个核心对象，则称p直接密度可达q。
4. 密度可达（Density Reachable）：对于给定的两个数据点p和q，如果存在一个数据点o1...on，满足p直接密度可达o1，o1直接密度可达o2，...，on直接密度可达q，则称p密度可达q。
基于上述概念，DBSCAN算法使用了两个重要的参数：半径ε和最小样本数MinPts。
算法流程如下：1.选择一个未被访问过的数据点p。
2.检查p是否是一个核心对象：- 如果p的周围半径ε内至少有最小样本数MinPts个数据点，则标记p为核心对象，并以p为中心，找到所有直接密度可达的数据点，构成一个聚类。
DBSCAN算法DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一种基于密度的聚类算法，可以用于发现任意形状的聚类簇，对噪声数据也有较好的容忍度。
DBSCAN算法通过计算数据点的密度来确定聚类簇，并使用可达性和核心点的概念进行聚类。
该算法具有较低的计算复杂度和较好的扩展性，被广泛应用于数据挖掘、图像分析、空间数据分析等领域。
DBSCAN算法的基本思想是：对于给定数据集，首先选择一个随机数据点作为种子点，判断该点的ε-邻域内是否包含足够数量的数据点，若是，则将种子点标记为核心点，根据根据核心点的ε-邻域内的数据点是否包含足够数量的数据点，将这些数据点归为同一个聚类簇。
然后，对于核心点的ε-邻域内的非核心点进行迭代，将其归为对应的聚类簇，直到所有点都被访问并被归类。
DBSCAN算法的关键参数包括半径参数ε和最小密度参数MinPts。
其中，半径参数ε用来决定邻域的大小，最小密度参数MinPts用来决定核心点的最小邻域内数据点数量。
对于任意数据点p，若其ε-邻域内的数据点数量少于MinPts，则将该点标记为噪声点或边界点；若其ε-邻域内的数据点数量大于等于MinPts，则将该点标记为核心点。
DBSCAN算法的优势在于可以发现任意形状的聚类簇，对噪声数据较为容忍，且不需要事先指定聚类的数量。
相比于传统的聚类算法（如K-means算法），DBSCAN算法可以有效处理由于聚类簇形状不规则或聚类簇之间存在不同密度区域造成的效果差异；相比于基于密度的聚类算法（如OPTICS算法），DBSCAN算法具有较低的计算复杂度。
具体实现DBSCAN算法时，可以使用以下步骤：1.随机选择一个未访问的数据点p；2. 判断p的ε-邻域内是否包含至少MinPts个数据点，若是，则将p标记为核心点；否则标记为噪声点或边界点；3.若p被标记为核心点，则创建一个新的聚类簇，并将p加入该聚类簇；4.对p的ε-邻域内的所有未访问数据点进行迭代，若其中一邻域数据点q未被访问，则访问该点；5.对于访问过的数据点q，若其也被标记为核心点，则将其ε-邻域内的所有未访问数据点加入聚类簇，并进行迭代；6.继续选择下一个未访问的数据点，重复上述步骤，直到所有数据点都被访问并被归类。
第37卷第11期2000年11月计算机研究与发展JOU RNAL O F COM PU T ER R ESEA RCH &D EV ELO PM EN T V o l 137,N o 111N ov .2000原稿收到日期:1999209220;修改稿收到日期:1999212209.本课题得到国家自然科学基金项目(项目编号69743001)和国家教委博士点教育基金的资助.周水庚,男,1966年生,博士研究生,高级工程师,主要从事数据库、数据仓库和数据挖掘以及信息检索等的研究.周傲英,男,1965年生,教授,博士生导师,主要从事数据库、数据挖掘和W eb 信息管理等研究.曹晶,女,1976年生,硕士研究生,主要从事数据库、数据挖掘等研究.胡运发,男,1940年生,教授,博士生导师,主要从事知识工程、数字图书馆、信息检索等研究.一种基于密度的快速聚类算法周水庚 周傲英 曹 晶 胡运发(复旦大学计算机科学系 上海 200433)摘 要 聚类是数据挖掘领域中的一个重要研究方向.聚类技术在统计数据分析、模式识别、图像处理等领域有广泛应用.迄今为止人们提出了许多用于大规模数据库的聚类算法.基于密度的聚类算法DBSCAN 就是一个典型代表.以DBSCAN 为基础,提出了一种基于密度的快速聚类算法.新算法以核心对象邻域中所有对象的代表对象为种子对象来扩展类,从而减少区域查询次数,降低I O 开销,实现快速聚类.对二维空间数据测试表明:快速算法能够有效地对大规模数据库进行聚类,速度上数倍于已有DBSCAN 算法.关键词 空间数据库,数据挖掘,聚类,密度,快速算法,代表对象中图法分类号 T P 311.13;T P 391A FAST D ENSIT Y -BASED CL USTER ING AL G OR ITH MZHOU Shu i 2Geng ,ZHOU A o 2Y ing ,CAO J ing ,and HU Yun 2Fa(D ep a rt m en t of Co mp u ter S cience ,F ud an U n iversity ,S hang ha i 200433)Abstract C lu stering is a p rom ising app licati on area fo r m any fields including data m in ing ,statistical data analysis ,p attern recogn iti on ,i m age p rocessing ,etc .In th is paper ,a fast den sity 2based clu stering algo rithm is developed ,w h ich con siderab ly speeds up the o riginal DB SCAN algo rithm .U n like DB SCAN ,the new DB SCAN u ses on ly a s m all num ber of rep resen tative ob jects in a co re ob ject’s neighbo rhood as seeds to exp and the clu ster so that the execu ti on frequency of regi on query can be decreased ,and con sequen tly the I O co st is reduced .Experi m en tal resu lts show that the new algo rithm is effective and efficien t in clu stering large 2scale databases ,and it is faster than the o riginal DB SCAN by several ti m es .Key words spatial database ,data m in ing ,clu stering ,den sity ,fast algo rithm ,rep resen tative ob jects1 概 述近10多年来,数据挖掘逐渐成为数据库研究领域的一个热点[1].其中,聚类分析就是广为研究的问题之一.所谓聚类,就是将数据库中的数据进行分组,使得每一组内的数据尽可能相似而不同组内的数据尽可能不同.聚类技术在统计数据分析、模式识别、图像处理等领域都有广泛的应用前景.迄今为止,人们已经提出了许多聚类算法[2～7].所有这些算法都试图解决大规模数据的聚类问题.以基于密度的聚类算法DB SCAN [4]为基础,本文提出一种基于密度的快速聚类算法.通过选用核心对象附近区域包含的所有对象的代表对象作为种子对象来扩展类,快速算法减少了区域查询的次数,从而减低了聚类时间和I O 开销.本文内容安排如下:首先在第2节中介绍基于密度的聚类算法DB SCAN 的基本思想,并分析它的局限8821计算机研究与发展2000年性;然后第3节描述基于密度的快速聚类算法;接着在第4节中给出对新算法的测试结果;第5节为结束语,同时指出今后的研究方向.2 基于密度的聚类算法D BSCAN基于密度的聚类算法DB SCAN利用类的密度连通特性,可以快速发现任意形状的类.其基本思想是:对于一个类中的每一对象,在其给定半径的邻域中包含的对象不能少于某一给定的最小数目.在DB SCAN 中,发现一个类的过程是基于这样的事实:一个类能够被其中的任意一个核心对象所确定[4].为了发现一个类,DB SCAN先从D中找到任意一对象p,并查找D中关于Ep s和M inP ts的从p密度可达的所有对象.如果p是核心对象,也就是说,半径为Ep s的p的邻域中包含的对象数不少于M inP ts,则根据算法可以找到一个关于参数Ep s和M inP ts的类.如果p是一个边界点,即半径为Ep s的p的邻域包含的对象数小于M inP ts,则没有对象从p密度可达,p被暂时标注为噪声点.然后,DB SCAN处理数据库D中的下一个对象.密度可达对象的获取是通过不断执行区域查询来实现.一个区域查询返回指定区域中的所有对象.为了有效地执行区域查询,DB SCAN算法使用了空间查询中的R32树结构.在进行聚类前,必须建立针对所有数据的R32树.另外,DB SCAN要求用户指定一个全局参量Ep s(为了减少计算量,预先确定参数M inP ts).为了确定Ep s值,DB SCAN计算任意对象与它的第k个最临近的对象之间的距离.然后,根据求得的距离由小到大进行排序,并绘出排序后的图,称做k2d ist图.k2d ist图中的横坐标表示数据对象与它的第k个最近的对象间的距离;纵坐标则为对应于某一k2d ist距离值的数据对象的个数.R32树的建立和k2d ist图的绘制是非常消耗时间的过程.此外,为了得到好的聚类结果,用户必须根据k2d ist图,通过试探选定一个比较合适的k2d ist值,即Ep s值.再就是,DB SCAN不进行任何的预处理而直接对整个数据库进行聚类操作.这样当数据库非常大时,就必须有大内存量支持,I O消耗也非常大.3 一种基于密度的快速聚类算法3.1 算法思想DB SCAN算法的平均执行时间复杂度为O(n log n)(n是数据库中包含的数据对象数目).聚类过程的大部分时间是用在区域查询操作上.实际上,DB SCAN算法进行聚类的过程就是一个不断执行区域查询的过程.因此,如果能够减少区域查询执行的次数,就可以提高聚类的速度.这里,从减少区域查询频度的目的出发,给出一种快速的基于密度的聚类算法.DB SCAN算法选择一个全局k2d ist值来进行聚类.这样,对于那些最稀的类来说,包含在核心对象的半径为Ep s且Ep s等于k2d ist的邻域中的对象数约为k.然而,对于别的类而言,包含在大多数核心对象的具有相同半径值的邻域中的对象数将大于k.DB SCAN算法对核心对象的邻域中包含的所有对象都执行区域查询操作.对类C中的某一给定核心对象p来说,可以想象它的邻域中所包含的所有对象的邻域将会互相覆盖.假定q是p邻域中的一个对象,如果它的邻域被p邻域中的其它对象的邻域所覆盖,则表明对q的区域查询是可以省掉的.这是因为q的邻域中所包含的对象可以通过对覆盖它的其它对象执行区域查询得到.也就是说,q没有必要作为种子对象用于类扩展.实际上,对于密集的类来说,在一个核心对象的邻域中有相当多的对象可以不用作为类扩展用的种子对象.这样,从加速DB SCAN算法来讲,应当选择核心对象邻域中的部分代表对象,而不是像DB SCAN那样选择所有对象,作为种子对象用于类的扩展.这里称这些被选择的对象为对应邻域的代表对象.直观地,p的邻域中靠边沿的对象更适合作为侯选代表对象,因为靠内部的对象的邻域往往被靠边沿的对象的邻域所覆盖.因此,选择代表对象其实就是选择一些对象,这些对象能够近似地表征所在邻域的形状.图1所示为一个二维数据空间实例,这里的数据对象就是点.其中p是类C中的一个核心对象,q i(i=1～4)就是p邻域的代表对象,它们将作为种子对象用于对p的邻域的扩展.这里代表对象数为4.图1 二维空间中的邻域及其代表对象通过选用核心对象附近区域包含的所有对象的代表对象作为种子对象来扩展类,新算法减少了区域查询的次数,从而减低了聚类时间和I O 开销.但是,新算法显然和原有DB SCAN 算法具有相同的复杂度,也为O (n log n ).3.2 代表对象的选择有2个问题需要解决:①代表对象应该选多少;②如何选择代表对象.显然,代表对象不能太多,亦不能太少.若太多,就难以发挥快速算法的效率;反之,如果太少,则代表对象邻域难以比较完全地覆盖其它对象的邻域,从而造成对象“丢失”,影响到聚类质量和效率.对象“丢失”将在下一节讨论.对于二维空间数据,可以选代表对象数为4.直观地,一个核心对象的邻域可以近似地被4个分散较好的代表对象的具有相同半径的邻域所覆盖.实验结果也表明:选择4个代表对象,不仅丢失对象少,且聚类速度提高明显.对于三维空间数据,可以考虑选择6个代表对象.依次类推,在n 维空间中,选择2n 个代表对象.也就是说,在每一维空间上,选择两个对象作为代表对象用于类的扩展.下面给出一种从核心对象的邻域中选择代表种子对象的算法.其基本思想是:首先选出一个与核心对象最远的对象作为第1个代表对象;随后则选出离所有已被选出的代表对象最远的对象作为下一个代表对象,直到选出所需的全部代表对象为止.下面给出该算法的伪码.算法1.代表对象选择算法R ep resentative S eed s S elect (cand id ate seed s ,rep resentative seed s ,R ep resentative M inp ts ,P oint )rep resentative seed s ∶=0;fo r i ∶=1to R ep resentative M inp ts do { m axD ist ∶=0; fo r each p oint p in cand id ate seed s do { if i =1 m inD ist ∶=d ist (p ,P oint ); else m inD ist ∶=m in {d ist (p ,q ) q ∈rep resentative seed s } if (m inD ist ≥m axD ist ){ m axD ist ∶=m inD ist ;m ax P oint ∶=p } } rep resentative seed s ∶=rep resentative seed s ∪{m ax P oint }.}3.3 丢失对象及其处理由于只从核心对象p 的邻域中选择有限个固定数目的代表对象作为种子对象用于类的扩展,p 的邻域中的一些核心对象必然会被忽略掉.在这种情况下,如果某些对象唯一地从那些被忽略的核心对象密度可达,则当p 所在的类C 扩展完成后,这些对象将未被包含在类C 中.这里称这些对象为丢失对象.当然,它们只是暂时地丢失了,可以采取相应的措施把这些丢失的对象找回来.图2所示为二维空间中出现丢失对象时的情况.这里,p 1和p 2分别唯一地从p 3和p 4密度可达.然而,在聚类过程中,p 3和p 4未被选为代表点.这样,C 1聚类完成后,而p 1和p 2被丢失.由于p 1不是核心点,而p 2是,982111期周水庚等:一种基于密度的快速聚类算法图2 二维空间中的丢失对象最后p1被标注为噪声,而p2归到类C2中.丢失对象是类的快速扩展的结果.显然,有两类丢失对象存在.一类丢失对象因为是边界对象,所以被标注为“噪声”;另一类原本为核心对象,它们作为独立的类中的对象而存在.对于第1类丢失对象,可以这样处理:先得到它的邻域中包含的所有对象,然后查找所包含的对象中是不是存在这样的对象,它们已被标注为某一类.如果确实存在这样的对象,则离丢失对象最近的那个对象所在的类即是丢失对象所在的类.若没有这样的对象存在,则表示丢失对象为真正的“噪声”.对于第2类丢失对象,其实就是将它目前所处的类与它原本应该所在的类合并.丢失对象目前所处的类必然紧靠它原本应该所在的类或者处于它原本应该所在的类之中.可以直接对前者的代表对象进行区域查询,得到这些代表对象的邻域对象.如果某一代表对象为核心对象,且其包含有被标注为其它类的对象,则这些对象所在的类和丢失对象所处的类为同一类,也就是说,这两个类合并为一个类.其实丢失对象也可以不作处理,因为丢失对象发生的可能性是比较小的.测试结果也证实了这一点.3.4 算法描述基于密度的快速聚类算法(FDB SCAN)是基于密度的聚类算法DB SCAN的一个快速版本.在新算法中,当新类的第1个核心点找到后,第1批代表点被选为种子点作为类扩展用.在随后的类扩展回合中,新种子不断增加到种子点集合rep resen ta tive seed s中,用于后续类扩展.如此循环执行下去,直到rep resen ta tive seed s 为空.这表明该类扩展完毕.下面给出的是新算法的基本框架.与DB SCAN相比,新主要在两个方面不同:(1)在主程序FDB S CA N()中,增加了丢失点处理过程H and le L ostP oin ts();(2)在过程E xp andC luster()中,加进了过程R ep resen ta tive S eed s S elect(),用于从核心点的邻域中选择代表点.此外,E xp andC luster()中的流程也作了相应的改变.算法2.快速聚类算法框架FDB S CA N(S etof P oints,Ep s,M inP ts,R ep resentative M inP ts)S etof P oints中的所有点被初始化为UN CLA SS IF IEDC lusterId∶=nex tId(NO ISE);fo r i∶=1to S etof P oints.siz e do{ P oint∶=S etof P oints.g et(i) if P oint.C lId=UN CLA SS IF IED then{ if E xp andC luster(S etof P oints,P oint,C lusterId,Ep s,M inP ts,R ep resentative M inP ts) then C lusterId∶=nex tId(C lusterId) } H and le L ostP oints(S etof P oints,Ep s,M inP ts,R ep resentative M inP ts).}E xp andC luster(S etof P oints,P oint,C lusterId,Ep s,M inP ts,R ep resentative M inP ts):BOOL EAN; cand id ate seed s∶=S etof P oints.reg ionquery(P oint,Ep s); if cand id ate seed s.siz e<M inP ts{ P oint为一边界点 S etof P oint.chang eC lId(P oint,NO ISE); return False; } else{ P oint为一核心点 S etof P oints.chang eC lId s(cand id ate seed s,C lId); R ep resentative S eed s S elect(cand id ate seed s,rep resentative seed s,R ep resentative M inP ts,P oint);0921计算机研究与发展2000年 w h ile rep resentative seed s≠Em p ty do{ cu rrentP∶=rep resentative seed s.f irst(); resu lt∶=S etof P oints.reg ionquery(cu rrentP,Ep s); if resu lt.siz e≥M inP ts then{ cu rrentP为核心点 R rep resentative S eed s S elect(resu lt,rep resentative resu ltP,R ep resentative M inP ts,cu rrentP); fo r each po int p in rep resentative resu ltP do if p.C lId=UN CLA SS IF IED then rep resentative seed s.app end(p); fo r each po int p in result do if p.C lId=UN CLA SS IF IED o r NO ISE then S etof P oints.chang eC lId(p,C lId); } rep resentative seed s.d elete(cu rrentP); } return T rue; }4 算法测试这里对快速算法的性能进行测试,并将测试结果与DB SCAN进行了比较.算法在原有DB SCAN软件包基础上用Bo rland C++5.0实现.所有测试在1台PC机(P2CPU,350M H z内存、9.6GB硬盘)上进行.同时使用了模拟数据和真实数据进行测试.真实数据用的是SEQUO I A2000数据库.该数据库也被文献[4]用于对DB SCAN算法的性能测试.典型测试结果分别列于图3至图5中.表1列出的结果表明新算法引起的点丢失是很少的.表1 对丢失点未作处理时F D BSCAN和D BSCAN结果比较Ep sDBSCAN噪声点FDBSCAN噪声点丢失点6.722322526.1275285105.6401411105.072874315 注:总数据量为50000个图3 对SEQU I OA2000数据库的测试结果图3给出的是对SEQUO I A2000数据库的测试结果.从中可以看到,快速算法总是快于DB SCAN算法.一般情况下,FB SCAN算法快于DB SCAN数倍.图4所示为FDB SCAN和DB SCAN算法针对数据量的可扩展性测试结果.由于PC主存的限制,每次只能测试最多50000个左右的数据.图4中的曲线显示FDB SCAN算法关于数据量的可扩展性优于DB SCAN算法.图5为对一个包含10000个数据点的模拟数据库的聚类测试结果.这里测试的是FDB SCAN算法对DB SCAN算法的加速比与Ep s值的关系.定义FDB SCAN对DB SCAN的加速比为t DBSCAN t FDBSCAN,即DB SCAN和FDB SCAN对同一数据库进行聚类所花192111期周水庚等:一种基于密度的快速聚类算法时间之比.结果显示,加速比随Ep s 值的增大而增大.这是因为Ep s 值愈大,则FDB SCAN 算法扩展类愈快,因此加速比愈大.图4 针对数据量的扩展性测试结果图5 加速比(t DBSCAN t FDBSCAN )和Ep s 值的关系5 结束语聚类是数据挖掘中一门非常有用的技术,用于从大量数据中寻找隐含的数据分布和模式.以DB SCAN 算法为基础,本文提出了一种基于密度的快速聚类算法.该算法能够显著提高聚类速度.通过选用核心对象邻域中包含的所有对象的代表对象作为种子对象来扩展类,快速算法减少了区域查询的次数,从而减低了聚类时间和I O 开销.分别用模拟数据和真实数据对快速算法的性能进行测试,结果表明快速算法优于DB SCAN 算法数倍之多.今后工作重点将集中在如下两个方面:首先,在三维和更高维数空间中研究本文算法的效率;其次,将数据取样(sam p ling )技术、数据分区(p artiti on ing )技术和并行技术与本文快速算法结合起来,用于大规模数据库和数据仓库的聚类分析.参考文献1Chen M S et a l .D ata m ining:A n overview from a database perspective .IEEE T rans on KD E,1996,8(6):866～8832N g R T ,H an J.Efficient and effective clustering m ethods fo r spatial data m ining .In:P roc of the 20th VLDB Conf .Santiago:M o rgan Kaufm ann ,1994.144～1553Zhang T et a l .B I RCH :A n efficient data clustering m ethod fo r very large databases .In :P roc of the A CM S IG M OD Int’l Conf on M anagem ent of D ata .M ontreal :A CM P ress ,1996.73～844E ster M et a l .A density 2based algo rithm fo r discovering clusters in large spatial databases w ith no ise .In :P roc of 2nd Int’l Conf on Know ledge D iscovering in D atabases and D ata M ining (KDD 296).Po rtland :AAA I P ress ,19965Guha S et a l .CU R E :A n efficient clustering algo rithm fo r large databases .In :P roc of the A CM S IG M OD Int’l Conf on M anagem ent of D ata .Seattle :A CM P ress ,1998.73～846Zhang W et a l .ST I N G :A statistical info r m ati on grid app roach to spatial data m ining .In :P roc of the 23rd VLDB Conf .A thens :M o rgan Kaufm ann ,1997.186～1957A graw al R et a l .A utom atic subspace clustering of h igh di m ensi onal data fo r data m ining app licati ons.In :P roc of the A CM S IG M OD Int’l Conf on M anagem ent of D ata .Seattle :A CM P ress ,1998.73～842921计算机研究与发展2000年。
