一种基于密度的快速聚类算法

第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 391

A FAST D ENSIT Y -BASED CL USTER ING AL G OR ITH M

ZHOU 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 jects

1　概 述

近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是,

9

82111期周水庚等:一种基于密度的快速聚类算法

图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 IED

C 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

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 s

DBSCAN

噪声点

FDBSCAN

噪声点丢失点

6.72232252

6.127528510

5.640141110

5.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对同一数据库进行聚类所花

1921

11期周水庚等:一种基于密度的快速聚类算法

时间之比.结果显示,加速比随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 )技术和并行技术与本文快速算法结合起来,用于大规模数据库和数据仓库的聚类分析.

参

考文献1

Chen 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～8832

N 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～1553

Zhang 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～844

E 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 ,19965

Guha 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～846

Zhang 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年

各种聚类算法及改进算法的研究

论文关键词：数据挖掘；聚类算法；聚类分析论文摘要：该文详细阐述了数据挖掘领域的常用聚类算法及改进算法，并比较分析了其优缺点，提出了数据挖掘对聚类的典型要求，指出各自的特点，以便于人们更快、更容易地选择一种聚类算法解决特定问题和对聚类算法作进一步的研究。并给出了相应的算法评价标准、改进建议和聚类分析研究的热点、难点。上述工作将为聚类分析和数据挖掘等研究提供有益的参考。 1 引言随着经济社会和科学技术的高速发展，各行各业积累的数据量急剧增长，如何从海量的数据中提取有用的信息成为当务之急。聚类是将数据划分成群组的过程，即把数据对象分成多个类或簇，在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。它对未知数据的划分和分析起着非常有效的作用。通过聚类，能够识别密集和稀疏的区域，发现全局的分布模式，以及数据属性之间的相互关系等。为了找到效率高、通用性强的聚类方法人们从不同角度提出了许多种聚类算法，一般可分为基于层次的，基于划分的，基于密度的，基于网格的和基于模型的五大类。 2 数据挖掘对聚类算法的要求(1)可兼容性：要求聚类算法能够适应并处理属性不同类型的数据。(2)可伸缩性：要求聚类算法对大型数据集和小数据集都适用。(3)对用户专业知识要求最小化。(4)对数据类别簇的包容性：即聚类算法不仅能在用基本几何形式表达的数据上运行得很好，还要在以其他更高维度形式表现的数据上同样也能实现。(5)能有效识别并处理数据库的大量数据中普遍包含的异常值，空缺值或错误的不符合现实的数据。(6)聚类结果既要满足特定约束条件，又要具有良好聚类特性，且不丢失数据的真实信息。(7)可读性和可视性：能利用各种属性如颜色等以直观形式向用户显示数据挖掘的结果。(8)处理噪声数据的能力。(9)算法能否与输入顺序无关。 3 各种聚类算法介绍随着人们对数据挖掘的深入研究和了解，各种聚类算法的改进算法也相继提出，很多新算法在前人提出的算法中做了某些方面的提高和改进，且很多算法是有针对性地为特定的领域而设计。某些算法可能对某类数据在可行性、效率、精度或简单性上具有一定的优越性，但对其它类型的数据或在其他领域应用中则不一定还有优势。所以，我们必须清楚地了解各种算法的优缺点和应用范围，根据实际问题选择合适的算法。 3.1 基于层次的聚类算法基于层次的聚类算法对给定数据对象进行层次上的分解，可分为凝聚算法和分裂算法。 (1)自底向上的凝聚聚类方法。这种策略是以数据对象作为原子类，然后将这些原子类进行聚合。逐步聚合成越来越大的类，直到满足终止条件。凝聚算法的过程为：在初始时，每一个成员都组成一个单独的簇，在以后的迭代过程中，再把那些相互邻近的簇合并成一个簇，直到所有的成员组成一个簇为止。其时间和空间复杂性均为O(n2)。通过凝聚式的方法将两簇合并后，无法再将其分离到之前的状态。在凝聚聚类时，选择合适的类的个数和画出原始数据的图像很重要。 [!--empirenews.page--] (2)自顶向下分裂聚类方法。与凝聚法相反，该法先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇，或者达到了某个终结条件。其主要思想是将那些成员之间不是非常紧密的簇进行分裂。跟凝聚式方法的方向相反，从一个簇出发，一步一步细化。它的优点在于研究者可以把注意力集中在数据的结构上面。一般情况下不使用分裂型方法，因为在较高的层很难进行正确的拆分。 3.2 基于密度的聚类算法很多算法都使用距离来描述数据之间的相似性，但对于非凸数据集，只用距离来描述是不够的。此时可用密度来取代距离描述相似性，即基于密度的聚类算法。它不是基于各种各样的距离，所以能克服基于距离的算法只能发现“类圆形”的聚类的缺点。其指导思想是：只要一个区域中的点的密度（对象或数据点的数目）大过某个阈值，就把它加到与之相近的聚类中去。该法从数据对象的分布密度出发，把密度足够大的区域连接起来，从而可发现任意形状的簇，并可用来过滤“噪声”数据。常见算法有DBSCAN，DENCLUE 等。[1][2][3]下一页 3.3 基于划分的聚类算法给定一个N个对象的元组或数据库，根据给定要创建的划分的数目k，将数据划分为k个组，每个组表示一个簇类（<=N）时满足如下两点：(1)每个组至少包含一个对象；(2)每个对

基于密度的最佳聚类数确定方法.

基于密度的最佳聚类数确定方法 [关键字]聚类评估，聚类数，聚类有效性指标 0 引言 聚类是数据挖掘研究中重要的分析手段，其目的是将数据集中对象聚集成类，使得同一类中的对象是相似的，而不同类中的对象是不同的。迄今研究者已经提出了为数众多的聚类算法，并已经在商务智能、图形分析、生物信息等领域得到了广泛应用。作为一种非监督学习的方法，对学习得到的聚类结果进行评估是非常有必要的。因为许多聚类算法需要用户给定数据集的聚类数量，而在实际应用中这通常是事先不知道的。确定数据集的聚类数问题目前仍是聚类分析研究中的基础性难题之一 [1][2]。 聚类评估用于评价聚类结果的质量，这被认为是影响聚类分析成功与否的重要因素之一[3]。它在聚类分析过程中的位置如图1所示。聚类评估的一些重要问题包括确定数据集的聚类趋势、确定正确的类个数、将聚类分析结果与已知的客观结果比较等，本文主要研究其中的最佳聚类数的确定。 通常最佳聚类数的确定是通过以下计算过程来确定的。在给定的数据集上，通过使用不同的输入参数（如聚类数）运行特定的聚类算法，对数据集进行不同的划分，计算每种划分的聚类有效性指标，最后比较各个指标值的大小或变化情况，符合预定条件的指标值所对应的算法参数被认为是最佳的聚类数 [4]。 迄今为止，已有各种类型的度量指标从不同角度来评估数据集划分的有效性，这些指标称为聚类有效性指标（Clustering Validation Indices）。一般地，用于评估聚类的各方面的评估度量指标可分成以下两类[5]。 1）外部指标（External index）：指聚类分析的评价函数是针对基准问题的，其簇的个数及每个数据对象的正确分类均为已知。代表性外部指标有熵、纯度、F-measure等。 2）内部指标（Internal index）：指数据集结构未知的情况下，聚类结果的评价只依靠数据集自身的特征和量值。在这种情况下，聚类分析的度量追求两个目标：类内紧密度和类间分离度。这也是本文的主要研究领域，代表性内部指标有DB，CH，XB，SD等。 从其他不同角度，聚类有效性指标又可分为分割指标与层次指标，模糊指标与非模糊指标，统计指标与几何指标。 用内部指标来评估聚类有效性，获取数据集最佳划分或最佳聚类数的过程一般分为以下4步[6]：

各种密度聚类算法

什么是聚类？聚类：- 将一个对象的集合分割成几个类，每个类内的对象之间是相似的，但与其他类的对象是不相似的。评判聚类好坏的标准：1 ，能够适用于大数据量。 2 ，能应付不同的数据类型。 3 ，能够发现不同类型的聚类。 4 ，使对专业知识的要求降到最低。 5 ，能应付脏数据。 6 ，对于数据不同的顺序不敏感。 7 ，能应付很多类型的数据。 8 ，模型可解释，可使用。 二，聚类所基于的数据类型。 聚类算法通常基于“数据矩阵”和“ Dissimilarity 矩阵”。 怎么样计算不同对象之间的距离？ 1 ，数值连续的变量(体重，身高等)：度量单位的选取对于聚类的结果的很重要的。例如将身高的单位从米变为尺，将体重的单位从公斤变为磅将对聚类的结果产生很大的影响。为了避免出现这种情况，我们必须将数据标准化：将数据中的单位“去掉”。 A, 计算绝对背离度。B, 计算标准量度。下面我们考虑怎样来计算两个对象之间的差异。 1 ，欧几里得距离。 2 ，曼哈顿距离。这两种算法有共同之处：d(i,j)>=0,d(i,i)=0, d(i,j)=d(j,i),d(i,j)=

(完整word版)各种聚类算法介绍及对比

一、层次聚类 1、层次聚类的原理及分类 1）层次法（Hierarchical methods）先计算样本之间的距离。每次将距离最近的点合并到同一个类。然后，再计算类与类之间的距离，将距离最近的类合并为一个大类。不停的合并，直到合成了一个类。其中类与类的距离的计算方法有：最短距离法，最长距离法，中间距离法，类平均法等。比如最短距离法，将类与类的距离定义为类与类之间样本的最短距离。 层次聚类算法根据层次分解的顺序分为：自下底向上和自上向下，即凝聚的层次聚类算法和分裂的层次聚类算法（agglomerative和divisive），也可以理解为自下而上法（bottom-up）和自上而下法（top-down）。自下而上法就是一开始每个个体（object）都是一个 类，然后根据linkage寻找同类，最后形成一个“类”。自上而下法就是反过来，一开始所有个体都属于一个“类”，然后根据linkage排除异己，最后每个个体都成为一个“类”。这两种路方法没有孰优孰劣之分，只是在实际应用的时候要根据数据特点以及你想要的“类”的个数，来考虑是自上而下更快还是自下而上更快。至于根据Linkage判断“类” 的方法就是最短距离法、最长距离法、中间距离法、类平均法等等（其中类平均法往往被认为是最常用也最好用的方法，一方面因为其良好的单调性，另一方面因为其空间扩张/浓缩的程度适中）。为弥补分解与合并的不足，层次合并经常要与其它聚类方法相结合，如循环定位。 2）Hierarchical methods中比较新的算法有BIRCH（Balanced Iterative Reducing and Clustering Using Hierarchies利用层次方法的平衡迭代规约和聚类）主要是在数据量很大的时候使用，而且数据类型是numerical。首先利用树的结构对对象集进行划分，然后再利用其它聚类方法对这些聚类进行优化；ROCK（A Hierarchical Clustering Algorithm for Categorical Attributes）主要用在categorical的数据类型上；Chameleon（A Hierarchical Clustering Algorithm Using Dynamic Modeling）里用到的linkage是kNN（k-nearest-neighbor）算法，并以此构建一个graph，Chameleon的聚类效果被认为非常强大，比BIRCH好用，但运算复杂度很高，O(n^2)。 2、层次聚类的流程 凝聚型层次聚类的策略是先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有对象都在一个簇中，或者某个终结条件被满足。绝大多数层次聚类属于凝聚型层次聚类，它们只是在簇间相似度的定义上有所不同。这里给出采用最小距离的凝聚层次聚类算法流程： (1) 将每个对象看作一类，计算两两之间的最小距离； (2) 将距离最小的两个类合并成一个新类； (3) 重新计算新类与所有类之间的距离； (4) 重复(2)、(3)，直到所有类最后合并成一类。

各种密度聚类算法

一，什么是聚类？ 聚类： - 将一个对象的集合分割成几个类，每个类内的对象之间是相似的，但与其他类的对象是不相似的。评判聚类好坏的标准： 1 ，能够适用于大数据量。 2 ，能应付不同的数据类型。 3 ，能够发现不同类型的聚类。 4 ，使对专业知识的要求降到最低。 5 ，能应付脏数据。 6 ，对于数据不同的顺序不敏感。 7 ，能应付很多类型的数据。 8 ，模型可解释，可使用。 二，聚类所基于的数据类型。 聚类算法通常基于“数据矩阵”和“ Dissimilarity 矩阵”。 怎么样计算不同对象之间的距离？ 1 ，数值连续的变量（体重，身高等）：度量单位的选取对于聚类的结果的很重要的。例如将身高的单位从米变为尺，将体重的单位从公斤变为磅将对聚类的结果产生很大的影响。为了避免出现这种情况，我们必须将数据标准化：将数据中的单位“去掉”。 A, 计算绝对背离度。 B, 计算标准量度。 下面我们考虑怎样来计算两个对象之间的差异。 1 ，欧几里得距离。 2 ，曼哈顿距离。这两种算法有共同之处： d(i,j)>=0,d(i,i)=0, d(i,j)=d(j,i),d(i,j)=

一种基于密度的快速聚类算法

第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 391 A FAST D ENSIT Y -BASED CL USTER ING AL G OR ITH M ZHOU 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 jects 1　概 述 近10多年来,数据挖掘逐渐成为数据库研究领域的一个热点[1].其中,聚类分析就是广为研究的问题之一.所谓聚类,就是将数据库中的数据进行分组,使得每一组内的数据尽可能相似而不同组内的数据尽可能不同.聚类技术在统计数据分析、模式识别、图像处理等领域都有广泛的应用前景.迄今为止,人们已经提出了许多聚类算法[2～7].所有这些算法都试图解决大规模数据的聚类问题.以基于密度的聚类算法DB SCAN [4]为基础,本文提出一种基于密度的快速聚类算法.通过选用核心对象附近区域包含的所有对象的代表对象作为种子对象来扩展类,快速算法减少了区域查询的次数,从而减低了聚类时间和I O 开销 .本文内容安排如下:首先在第2节中介绍基于密度的聚类算法DB SCAN 的基本思想,并分析它的局限

各种聚类算法的比较

各种聚类算法的比较 聚类的目标是使同一类对象的相似度尽可能地小；不同类对象之间的相似度尽可能地大。目前聚类的方法很多，根据基本思想的不同，大致可以将聚类算法分为五大类：层次聚类算法、分割聚类算法、基于约束的聚类算法、机器学习中的聚类算法和用于高维度的聚类算法。摘自数据挖掘中的聚类分析研究综述这篇论文。 1、层次聚类算法 1.1聚合聚类 1.1.1相似度依据距离不同：Single-Link:最近距离、Complete-Link：最远距离、Average-Link：平均距离 1.1.2最具代表性算法 1）CURE算法 特点：固定数目有代表性的点共同代表类 优点：识别形状复杂，大小不一的聚类，过滤孤立点 2）ROCK算法 特点：对CURE算法的改进 优点：同上，并适用于类别属性的数据 3）CHAMELEON算法 特点：利用了动态建模技术 1.2分解聚类 1.3优缺点 优点：适用于任意形状和任意属性的数据集；灵活控制不同层次的聚类粒度，强聚类能力 缺点：大大延长了算法的执行时间，不能回溯处理 2、分割聚类算法 2.1基于密度的聚类 2.1.1特点 将密度足够大的相邻区域连接，能有效处理异常数据，主要用于对空间数据的聚类

1）DBSCAN：不断生长足够高密度的区域 2）DENCLUE：根据数据点在属性空间中的密度进行聚类，密度和网格与处理的结合 3）OPTICS、DBCLASD、CURD：均针对数据在空间中呈现的不同密度分不对DBSCAN作了改进 2.2基于网格的聚类 2.2.1特点 利用属性空间的多维网格数据结构，将空间划分为有限数目的单元以构成网格结构； 1）优点：处理时间与数据对象的数目无关，与数据的输入顺序无关，可以处理任意类型的数据 2）缺点：处理时间与每维空间所划分的单元数相关，一定程度上降低了聚类的质量和准确性 2.2.2典型算法 1）STING：基于网格多分辨率，将空间划分为方形单元，对应不同分辨率2）STING+：改进STING，用于处理动态进化的空间数据 3）ＣＬＩＱＵＥ：结合网格和密度聚类的思想，能处理大规模高维度数据4）WaveCluster：以信号处理思想为基础 2.3基于图论的聚类 2.3.1特点 转换为组合优化问题，并利用图论和相关启发式算法来解决，构造数据集的最小生成数，再逐步删除最长边 1）优点：不需要进行相似度的计算 2.3.2两个主要的应用形式 1）基于超图的划分 2）基于光谱的图划分 2.4基于平方误差的迭代重分配聚类 2.4.1思想 逐步对聚类结果进行优化、不断将目标数据集向各个聚类中心进行重新分配以获最优解

聚类算法比较

聚类算法: 1. 划分法：K-MEANS算法、K-M EDOIDS算法、CLARANS算法； 1）K-means 算法： 基本思想是初始随机给定K个簇中心，按照最邻近原则把待分类样本点分到各个簇。然后按平均法重新计算各个簇的质心，从而确定新的簇心。一直迭代，直到簇心的移动距离小于某个给定的值。 K-Means聚类算法主要分为三个步骤： (1)第一步是为待聚类的点寻找聚类中心 (2)第二步是计算每个点到聚类中心的距离，将每个点聚类到离该点最近的聚类中去 (3)第三步是计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心 反复执行(2)、(3)，直到聚类中心不再进行大范围移动或者聚类次数达到要求为止 下图展示了对n个样本点进行K-means聚类的效果，这里k取2： (a)未聚类的初始点集 (b)随机选取两个点作为聚类中心 (c)计算每个点到聚类中心的距离，并聚类到离该点最近的聚类中去 (d)计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心 (e)重复(c),计算每个点到聚类中心的距离，并聚类到离该点最近的聚类中去 (f)重复(d),计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心 优点： 1.算法快速、简单; 2.对大数据集有较高的效率并且是可伸缩性的; 3.时间复杂度近于线性，而且适合挖掘大规模数据集。 缺点： 1. 在 K-means 算法中 K 是事先给定的，这个 K 值的选定是非常难以估计的。 2. 在 K-means 算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响。

密度聚类算法 DENCLUE 2.0

DENCLUE2.0:Fast Clustering based on Kernel Density Estimation Alexander Hinneburg1and Hans-Henning Gabriel2 1Institute of Computer Science Martin-Luther-University Halle-Wittenberg,Germany hinneburg@informatik.uni-halle.de 2Otto-von-Guericke-University Magdeburg,Germany Hans-Henning.Gabriel@web.de Abstract.The Denclue algorithm employs a cluster model based on kernel density estimation.A cluster is de?ned by a local maximum of the estimated density function.Data points are assigned to clusters by hill climbing,i.e.points going to the same local maximum are put into the same cluster.A disadvantage of Denclue1.0is,that the used hill climbing may make unnecessary small steps in the beginning and never converges exactly to the maximum,it just comes close. We introduce a new hill climbing procedure for Gaussian kernels,which adjusts the step size automatically at no extra costs.We prove that the procedure converges exactly towards a local maximum by reducing it to a special case of the expectation maximization algorithm.We show experimentally that the new procedure needs much less iterations and can be accelerated by sampling based methods with sacri?cing only a small amount of accuracy. 1Introduction Clustering can be formulated in many di?erent ways.Non-parametric methods are well suited for exploring clusters,because no generative model of the data is assumed.Instead,the probability density in the data space is directly estimated from data instances.Kernel density estimation[15,14]is a principled way of doing that task.There are several clustering algorithms,which exploit the adaptive nature of a kernel density estimate.Examples are the algorithms by Schnell [13]and Fukunaga[5]which use the gradient of the estimated density function. The algorithms are also described in the books by Bock[3]and Fukunaga[4] respectively.The Denclue framework for clustering[7,8]builds upon Schnells algorithm.There,clusters are de?ned by local maxima of the density estimate. Data points are assigned to local maxima by hill climbing.Those points which are assigned to the same local maximum are put into a single cluster. However,the algorithms use directional information of the gradient only. The step size remains?xed throughout the hill climbing.This implies certain disadvantages,namely the hill climbing does not converges towards the local maximum,it just comes close,and the number of iteration steps may be large

(完整版)聚类算法总结.doc

1.聚类定义 “聚类是把相似的对象通过静态分类的方法分成不同的组别或者 更多的子集（ subset）,这样让在同一个子集中的成员对象都有一 些相似的属性”—— wikipedia “聚类分析指将物理或抽象对象 的集合分组成为由类似的对象组 成的多个类的分析过程。它是一种重要的人类行为。聚类是将数 据分类到不同的类或者簇这样的一个过程，所以同一个簇中的对 象有很大的相似性，而不同簇间的对象有很大的相异性。”——百度百科 说白了，聚类（ clustering）是完全可以按字面意思来理解的——将相同、相似、相近、相关的对象实例聚成一类的过程。简单理 解，如果一个数据集合包含 N 个实例，根据某种准则可以将这 N 个 实例划分为 m 个类别，每个类别中的实例都是相关的，而不同类别 之间是区别的也就是不相关的，这个过程就叫聚类了。 2.聚类过程 : 1)数据准备 :包括特征标准化和降维 . 2)特征选择 :从最初的特征中选择最有效的特征 ,并将其存储于向量 中 . 3)特征提取 :通过对所选择的特征进行转换形成新的突出特征.

4)聚类 (或分组 ):首先选择合适特征类型的某种距离函数 (或构造新的距离函数 )进行接近程度的度量 ;而后执行聚类或分组 . 5)聚类结果评估 :是指对聚类结果进行评估 .评估主要有 3 种 :外部有效性评估、内部有效性评估和相关性测试评估. 3聚类算法的类别 没有任何一种聚类技术(聚类算法 )可以普遍适用于揭示各种多维数据集所呈现出来的多种多样的结构，根据数据在聚类中的积聚规则以及应用这些规则的方法,有多种聚类算法.聚类算法有多种分类方法将聚类算法大致分成层次化聚类算法、划分式聚类算 法、基于密度和网格的聚类算法和其他聚类算法,如图1 所示的4 个类别.

各种聚类算法介绍及对比教学内容

各种聚类算法介绍及 对比

一、层次聚类 1、层次聚类的原理及分类 1）层次法（Hierarchical methods）先计算样本之间的距离。每次将距离最近的点合并到同一个类。然后，再计算类与类之间的距离，将距离最近的类合并为一个大类。不停的合并，直到合成了一个类。其中类与类的距离的计算方法有：最短距离法，最长距离法，中间距离法，类平均法等。比如最短距离法，将类与类的距离定义为类与类之间样本的最短距离。 层次聚类算法根据层次分解的顺序分为：自下底向上和自上向下，即凝聚的层次聚类算法和分裂的层次聚类算法（agglomerative和divisive），也可以理解为自下而上法（bottom-up）和自上而下法（top-down）。自下而上法就是一开始每个个体（object）都是一个类，然后根据linkage寻找同类，最后形成一个“类”。自上而下法就是反过来，一开始所有个体都属于一个“类”，然后根据linkage排除异己，最后每个个体都成为一个“类”。这两种路方法没有孰优孰劣之分，只是在实际应用的时候要根据数据特点以及你想要的“类”的个数，来考虑是自上而下更快还是自下而上更快。至于根据Linkage判断“类”的方法就是最短距离法、最长距离法、中间距离法、类平均法等等（其中类平均法往往被认为是最常用也最好用的方法，一方面因为其良好的单调性，另一方面因为其空间扩张/浓缩的程度适中）。为弥补分解与合并的不足，层次合并经常要与其它聚类方法相结合，如循环定位。 2）Hierarchical methods中比较新的算法有BIRCH（Balanced Iterative Reducing and Clustering Using Hierarchies利用层次方法的平衡迭代规约和聚类）主要是在数据量很大的时候使用，而且数据类型是numerical。首先利用树的结构对对象集进行划分，然后再利用其它聚类方法对这些聚类进行优化；ROCK（A Hierarchical Clustering Algorithm for Categorical Attributes）主要用在categorical的数据类型上；Chameleon（A Hierarchical Clustering Algorithm Using Dynamic Modeling）里用到的linkage是kNN（k-nearest-neighbor）算法，并以此构建一个graph，Chameleon的聚类效果被认为非常强大，比BIRCH好用，但运算复杂度很高，O(n^2)。 2、层次聚类的流程 凝聚型层次聚类的策略是先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有对象都在一个簇中，或者某个终结条件被满足。绝大多数层次聚类属于凝聚型层次聚类，它们只是在簇间相似度的定义上有所不同。这里给出采用最小距离的凝聚层次聚类算法流程： (1) 将每个对象看作一类，计算两两之间的最小距离； (2) 将距离最小的两个类合并成一个新类； (3) 重新计算新类与所有类之间的距离； (4) 重复(2)、(3)，直到所有类最后合并成一类。