计算机应用研究
ApplicationResearchofComputersVol.25No.7Jul.2008
改进K2means的空间聚类算法
赵 伟
1,2
3
,张 姝,李文辉
21
(1.吉林大学计算机科学与技术学院,长春130012;2.长春工业大学计算机科学与工程学院,长春130012)
摘 要:提出了基于K2means的四叉树与R2link树的混合结构树,提高了R2link树的查询性能,在K2means中采用均值—标准差确定初始聚类中心,提高了收敛速度,通过距离准则函数来优化K值,避免K值的盲目选取。与R2link相比空间开销代价有时略大,但换取了更高的性能,且数据量越多,此种结构的整体性能越好,适合于海量数据。
关键词:空间数据库;R2link树;四叉树;空间聚类;空间索引
中图分类号:TP30116 文献标志码:A 文章编号:100123695(2008)0721995203ImprovedK2meansclusteringalgorithmonspaceZHAOWei,ZHANGShu,LIWen2huiChangchunUniversityofTechnology,Changchun130012,China)
1,2
21(1.CollegeofComputerScience&Technology,JilinUniversity,Changchun130012,China;2.SchoolofComputerScience&Engineering,
Abstract:ThispaperpresentedaquickspeedspatialindexingstructurewhichwasbasedonR2linktree.AnditusedK2
meansalgorithminthestructure.InK2meansalgorithm,adoptedvalue2standarddeviationtoascertaintheinitialclusteringcen2trestoimproveconvergencespeedandascertainultimateKvaluebydistancecriterionfunctiontomakeKvaluemostsuitable.ThestructuresometimesconsumesmorestoragethanR2linkbutgainsbetterperformance.Furthermore,dataquantitymore,thiskindofstructureoverallperformanceisbetter.
Keywords:spatialdatabase;R2linktree;quad2tree;spatialclustering;spatialindexstructure
随着计算机技术的发展,空间数据库应用范围已经扩展到了机器人、计算机视觉、图像识别、环境保护、地理信息处理等领域
[1]
xl∈ci
6xl表示第i个簇的中心位置,i=1,…,k;ni是簇Ci中数据
K2means聚类算法属于聚类分析方法中一种基本的且应
。为了提高空间数据的处理效率,空间数据库必须利
项的个数;d(xl,mi)表示xl到mi的距离。
用最广的划分方法,是一种在无类标号数据中发现簇和簇中心的方法[4]。该算法的基本思想是:给定一个包含n个数据对象的数据库,以及要生成簇的数目K,随机选取K个对象作为初始的K个聚类中心;然后计算剩余各个样本到每一个聚类中心的距离,把该样本归到离它最近的那个聚类中心所在的类,对调整后的新类使用平均值的方法计算新的聚类中心;如果相邻两次的聚类中心没有任何变化,说明样本调整结束且聚类平均误差准则函数已经收敛。本算法在每次迭代中都要考察每个样本的分类是否正确,若不正确,就要调整,在全部样本调整完后,修改聚类中心,进入下一次迭代。如果在一次迭代算法中,所有的样本被正确分类,则不会有调整,聚类中心不会有变化。在算法迭代中值在不断减小,最终收敛至一个固定的值。该准则也是衡量算法是否正确的依据之一。1 四叉树与
k
用有效的空间索引机制。常见的空间索引一般是采用自顶向下、逐级划分空间的方法,比较有代表性的有BSP树、KDB树、
R树、R+树、CELL树、四叉树和网型空间索引等
[2]
。
聚类分析是提高空间索引性能的一种非常有效的方法。目前已有K均值、CURE、ISODATA等多种算法。这些算法多数依赖于初始解的选择。当初始解选择不好时,会影响聚类质量,降低空间检索效率,且这些算法执行结果与数据输入次序有关
[3]
。
本文采用均值—标准差的方法决定初始聚类中心,使用准则函数优化K值,改进了K2means算法,并用此构造R2link,从而提高了空间检索的效率。
基本原理
111 K2means算法
2树混合的结构
定义1 K2means聚类问题:假设N个数据集合X={X1,…,Xn}是待聚类数据。其中:Xj={Xj1,…,Xjq}∈Rq,j=1,…,n。K均值聚类问题是要找到X的一个划分Pk={C1,…,
Ck},使目标函数f(Pk)=66d(xl,mi)最小。其中:mi=1/ni
i=lxl∈cik
四叉树是2叉树。让四叉树的每个节点均指向一棵与其对应索引空间相关联的R2link树。实质就是将一棵大的R2
link树分解成多棵小的R2link树,将查询尽可能限定在局部空
间区域,从而提高查找性能。
混合结构是由一棵深度为d的2k四叉树Qt和n棵R2link
收稿日期:2007206206;修回日期:2007209228 基金项目:国家自然科学基金资助项目(60573182);教育部博士点基金资助项目
(20060183042);吉林省科技发展计划资助项目(20060527,20040531)
作者简介:赵伟(19672),男,博士研究生,主要研究方向为数据库系统、虚拟现实技术等(prince1205@163.com);张姝(19802),女,硕士研究生,主要研究方向为数据库系统、虚拟现实技术等;李文辉(19612),男,教授,博导,博士,主要研究方向为计算机图形学与虚拟现实技术等.
・1996・
d-1i=0
计算机应用研究
最小值时,K为最优解。1 基于改进的
2
构建的
2
算法
第25卷
树组成。其中设d>0,n=6(2k)i,四叉树Qt共有n个节点,按宽度遍历方法进行编号依次为Qt0,Qt1,…,Qtn-1。Qt将整个索引空间(S)分成n个d级子空间(IS0,IS1,…,ISn-1)。每一级的所有子空间两两不相交,且一起构成整个索引空间S。
n棵R2link树(Rt0,Rt1,…,Rtn-1)分别与四叉树Qt的n个节点及四叉树Qt划分的n个子空间相关联,[(i=0,1,…,n-1),Qti←→Si←→Rti]。Si与Rti相关联,即Rti用于索引属于Si的空间目标。
R2link树采用最小外接矩形来界定空间实体,其不可避免
地导致约束矩形区重叠,而覆盖区域的大小和区域的重叠程度是影响搜索性能的重要因素。受聚类算法启发,引入新的节点分配原则,在建构R2link树时,使用改进的K2means算法来代替传统R2link树的面积增量最小准则,以减少R2link树的空间矩形的空白区域与重叠区域,从而大大提高空间查询的效率。
它的基本思想是采用均值—标准差选取初始聚类中心。算法的基本思想是:
a)算出所有数据的均值假定为μ,标准差为σ。也就是说数据主要分布在(μ-σ,μ+σ)之间,在此区间由公式mi=(μ-σ)+2σi/N(i=1,…,N/M)选取K个点,即为初始聚类中心。其中K=N/M。b)计算各个数据对象到各聚类中心的距离,把数据对象归到离它最近的那个聚类中心所在的类。
c)对调整后的新类计算新的聚类中心,如果相邻两次的聚类中心没有任何变化,说明数据对象调整结束。
d)K值是预先给定的,未必就是最优解。基于类际离散度最大、类内离散度最小的原则,使用准则函数对K值进一步优化。
以确定的聚类中心为初始聚类中心,计算各个数据对象与初始聚类中心距离,并计算距离准则函数,直到K大于或等于
[N/M]。其中使准则函数值最小的K值作为最终划分聚类的
定义2 空间目标r属于Si。
r完全被Si所包围,并且Si是所有包围P的子空间中最
小的。以图1所示的二维空间为例,混合结构由一棵深度为2的四叉树和5棵R2link树组成,整个空间分成2级共5个子空间:IS0,IS1,IS2,IS3,IS4(IS0=IS1∪IS2∪IS3∪IS4),Rt0,Rt1,
Rt2,Rt3和Rt4这5棵R2Link树分别与它们相关联。
2 基于改进的K2means构建的R2link算法211 改进的K2means算法21111 初始点的选取
由K均值算法可知,如果所选取的初始聚类中心在几个分布密集区域的中心,其周围的点容易分到最近的点,聚类收敛越快,需要迭代的次数越少[7]。
要分析所有数据的分布情况,计算其分布密度,可以根据随机函数的分布知识,聚类的数据应主要分布在所有数据的均值附近。标准差是评价数据分布的一个重要指标,假设所有数
据的均值为μ,标准差为σ,则数据应该主要分布在(μ-σ,μ+σ)之间。假设分类数为N,选择初始分类点为(μ-σ,μ+σ)之间的N个等分点。设第i类的初始分类中心为mi,则
σi/N;i=1,…,Nmi=(μ-σ)+2
个数。
e)将空间对象重新根据欧氏距离公式分配到相应的聚类,更新各聚类中心,直到聚类结果不变。
在对空间对象分组时,基于改进的K2means产生的分组要优于基于面积增量最小准则产生的分组,如图2、3所示。
如果参与分类的是多维数据,如d维,则每个聚类初始聚
类中心的各个向量应在(μl-σl,μl+σl)之间,设第i类聚类初σil/N。始中心值为{mi1,mi2,…,mid},则有mil=(μl-σl)+2
21112 优化K值的准则函数
定义3 类际离散度。
令K={X,R}为空间聚类的聚类空间。其中:X={x1,
x2,…,xn},假设n个空间对象被聚类为k个簇,定义类际离散
度为所有聚类中心到全域中心的距离之和,即L=6|mi-m|。
i=1
k
具体算法的实例分析如下:设N为R_Link树某节点当前拥有的子节点个数,m与M分别为R_Link树中每个节点能容纳的实体最小与最大个数。
输入:N个d维待分类数据{X1,X2,…,Xn}。其中Xi=
{Xi1,…,Xid};待分类的簇数为K。
其中:L为类际离散度;m为全部样本的均值;mi为簇Ci所含样本的均值;k为所要聚类的个数。
定义4 类内离散度。
令K={X,R}为空间聚类的聚类空间。其中:X={x1,
x2,…,xn},假设n个空间对象被聚类为k个簇,定义类内距离
为所有聚类簇内部距离的总和,即D=66|p-mi|。其中:D
i=1p∈ci
k
输出:K个簇,使得类际离散度最大,而类内离散度最小。
a)采用均值—标准差选择K个初始聚类中心{c1,c2,…,
ck}。其中:K的取值为[N/M]～[N/m],初值为[N/M];cj={cj1,cj2,…,cjd}。
为类内离散度;p为任一空间对象,即样本。
定义5 距离准则函数。
令K={X,R}为空间聚类的聚类空间。其中:X={x1,x2,
xn},假设n个空间对象被聚类为k个簇,定义距离准则函数为
b)根据欧氏距离公式,计算每个数据到各簇的距离,将各
数据划分到具有最小距离的簇中。其中距离计算公式为
d(xi,mj)=
l=1
类内离散度与类际离散度之商:
F(s,k)=D/L=6|mi-m|/(66|p-mi|)
i=1
i=1p∈ci
k
k
6(Xil-mjl)2;i=1,…,N;j=1,…,k
d
其中:d(xi,mj)为第i个矢量数据到第j个聚类的距离。c)根据分配的结果更新各聚类中心。
d)重复步骤b)和c),直到聚类结果不变。
其中:F(s,k)为距离准则函数。当距离准则函数F(s,k)达到
第7期
k
赵 伟,等:改进K2means的空间聚类算法
k
・19 97・
e)计算类际离散度L=6|mi-m|、类内离散度D=66
i=1
ki=1p∈ci
点越紧凑,聚类性能越高的特点,提出了基于空间聚类的四叉树与R2link树的混合结构,以提高查找、插入、删除的效率。用四叉树将整个索引空间划分成多级子索引空间,用R2link树索引每级的每个子空间。采用K2means算法来构造R2link树,并通过距离准则函数优化K值,使得R2link树各子节点紧凑、聚类性能高,达到了提高R2link树查询效率的目的。
在今后的研究工作中,笔者将仍然以索引结构为重点,可以选择下列问题为研究方向:
a)高维(k>20)数据对象的索引结构。
b)大数据量空间物体的存储研究,怎样在传递数据时减
i=1p∈ci
|p-mi|及计算距离准则函数F(S,K)=L/D=(66|p-mi|)/6|mi-m|。
i=1k
重复上述步骤,直到K值大于或等于[N/m]。
f)选择使距离准则函数值最小的k值作为划分聚类的个数,将空间对象按上述步骤b)～e)分配到相应的聚类。
实验结果与性能分析
为了便于性能评价,在实验时选定三个参考对象,即R树、R2link树和改进的R2link树。其测试环境为WindowsXP操作系统,CPU为赛扬IV1.7GHz,内存256MB,磁盘盘页大小1024Byte,采用随机数据进行性能测试。
本文进行如下两个实验:a)将R树、R2link树与改进后的R2link树在查询时间效率上作比较。
以深度为2的四叉树为例,当用于查询的实验数据增加时,R树、R2link树与改进后的R2link树需要的页面数都在不断增加,如表1所示。本文给出了实验结果的图像描述,如图
4所示。从图4可以看出,在具有相同查询数据的条件下,改
少磁盘访问开销。
c)空间查询方法与传统SQL语言的结合。
d)空间索引的分布化或并行化。表1 不同树型结构的页面占用表算法R2树R2link树
08580205
数据量5000100001500020000250003000018016010565
243218168125
265237189166
281255222182
317263238195
377285257211
改进的R2link树
Level2Level3
表2 不同树型结构的空间占用表
算法R2树R2link树
032323334
进后的R2link树在查询上占用的页面总数要优于R树与
R2link树;当树的深度增加时,Leveli=3,4,5,…,k时,结果也
数据量
5000100001500020000250003000032.533.736.239.5
3334.13741
33.233.73539.2
32.83335.534.5
32.633.235.333.7
33.533.83533.9
是一致的。由于改进后的R2link树在查询相同数量的数据时占用的页面数要少于R树,查询速度要优于R树与R2link树。
b)将R树、R2link树和改进后的R2link树进行空间性能的比较。
本文仍然采用相同的随机数据进行空间性能测试,如表2所示。从图5中可以看出,当测试的随机数数目相同时,无论改进后的R2link树Leveli中i取何值,占用的页面数都要多于
R树与R2link树。改进后的R2link树的存储空间开销与四叉
改进的
R2link树
Level2Level3
树的深度成正比,一般比R树、R2link树要大,但索引目标数越多时,它们的存储开销越接近。因此,这个方法比较适合于海量数据。
就插入、删除、查找效率而言,由于改进后的R2link树采用四叉树对整个索引空间进行了划分,且四叉树节点所对应的
R2link是基于空间聚类所构造的,使R2link各子节点紧凑、其
参考文献:
[1]陈述彭,鲁学军,周成虎.地理信息系统导论[M].北京:科学技术
出版社,2001.
[2]KIMM,EOS.Efficientindexingofmovingobjectsusingtime2based
partitioningwithR2tree[C]//ProcofInternationalConferenceonComputationalScience.2005:5682575.[3]
KANUNGOT,MOUNTDM,NETANYAHUNS,etal.AnefficientK2meansclusteringalgorithm:analysisandimplementation[J].IEEETransonPatternAnalysisandMachineIntelligence,2002,24(7):8812892.
[4]周水庚,周傲英,曹晶,等.一种基于密度的快速聚类算法[J].计
聚类性能更高。其查询、插入、删除操作在一棵矮的具有高聚类性的R2link树上进行,不再针对整个索引空间,而被限定在某些局部区域,因此其插入、删除、查询性能优于R2link树。
结束语
本文针对R2link树允许索引空间重叠、多路查询且各子节
(上接第1994页)[3]
ISLERV,LAURWH,GREENM.Real2timemulti2resolutionmode2lingforcomplexvirtualenvironments[C]//ProcofACMSymposiumonVirtualRealitySoftwareandTechnology.HongKong:ACMPress,1996:11219.
[4]GARLANDM,HECKBERTPS.Surfacesimplificationusingquadric
errormetrics[J].ComputerGraphics,1997,31(3):2092216.[5]周昆,潘志庚,石教英.基于三角形折叠的网格简化算法[J].计算
算机研究与发展,2002,37(11):128721292.
[6]FARKASL.Anthropometricfacialproportionsinmedicine[M].[S.
l.]:ThomasBooks,1987.
[7]HOPPEH,DeROSET,DUCHAMPT,etal.Meshoptimization[C]//
ProcoftheSIGGRAPH’93.1993.
[8]CIGNONIP,MONTANIC,SCOPIGNORA.Comparisonofmeshsim2
plificationalgorithm[J].Computer&Graphics,1998,22(1):37254.
[9]陶志良,潘志庚,石教英.支持快速恢复的可逆递进网格及其生成
机学报,1998,21(6):5062513.方法[J].软件学报,1999,10(5):5032507.
因篇幅问题不能全部显示，请点此查看更多更全内容