基于delaunay三角网的cbdt聚类算法研究

《基于delaunay三角网的cbdt聚类算法研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第19卷第l期计算机技术与发展Vo1．I9NO．12009年1月COMPUTERTECHNOLOGYANDDEVEI0PMENTJan．2009基于Delaunay三角网的CBDT聚类算法研究李静，陈立潮，成洪静，聂跃光(太原科技大学计算机科学与技术学院，山西太原030024)摘要：聚类分析是空间数据挖掘的重要方法之一。Delaunay三角网具有良好的空问邻近特性，应用于空间聚类分析具有独特的优势，提出了一种基于Delaunay三角网的聚类算法——CBDT算法，该算法采用了将Delaunay三角剖分得到的三角形划分为小三角形、狭长三角形和大三

2、角形的聚类模型，通过一定规则分别以小三角形、狭长三角形为基准进行扩展从而实现聚类。CBDT算法相对于AUTOCLUST算法能识别密度渐变的簇，而且计算量要比A1rrDCI．I，ST小得多。经实验验证，证明了该算法的有效性。关键词：空间聚类；聚类算法；I~．．1aunay三角网中图分类号：TP301．6文献标识码：A文章编号：1673—629X(2009)01—0021一O4StudyofSpatialClusteringAlgorithmBasedonDelaunayTriangulationLIJing，CHENLi-chao，CHENGH

3、ong-jing，NIEYue-guang一(Dept．ofComputerScience&Technology，TaiyuanUniversityofScience&Technology，Taiyuan030024，China)Abstract：Clusteringanalysisisoneofmainmethodsofspatialdatamining．Delauanytriangulationhastheparticularpropertyofproximitythatusedforclusteringanalysis．Inthispa

4、per，anearalgorithm—CBDT(clusteringofhas~xlonDehunaytriangulation)hasbeenpro—posed．BydividingtheDelaunaytriangulationintosmaller—triangles，longandnarrow—trianglesandbigger—triangles，obtaintheclus-t~ingmodel，andexpandthesetrianglesrespectivelyaccordingso,fierulestoclustering．

5、CBDThastheadvantagesthatcannotonlyrec—ogtheclusterofdensity—changingandalsoexpendsmallercomputetimethanA~LUST．Thealgorithmthathadbeenexperi·mentediSfeasible．KeyWOlds：spatialclustering；clusteringalgorithm；DelaunaytriangulationO引言不包含面内的其他任何点，称之为Delaunay三角网的从二维空间数据中发现隐含模式或有意义的

6、子群空外接圆性质；最大最小角度性质：在由点集P中所的聚类有很多应用，比如资源规划、市场分析、图像处能形成的三角网中，Delaunay三角网中三角形的最小理、动物群体迁徙分析、疾病扩散分析等。Voronoi图内角尽量最大，即三角形尽量接近等边三角形。由于和其对偶图Delaunay三角网是两个被普遍接受和采这两个性质，决定了Delaunay三角网具有极大的应用用的分析研究区域离散数据的有利工具，在地理信息价值。同时，它也是二维平面三角网中唯一的、最好系统、地学分析、计算机视觉、有限元分析和表面对象的。Delaunay三角网作为一种构建数据集拓扑关

7、系的重建等领域有广泛的应用。在分析研究区域离散数据方法，广泛应用于计算机图形学和实体建模中。De—时，都可以尝试一下采用Delaunay三角网和Vomnoilaunay三角网能很好地表达空间数据之间的邻近关图的分析途径[0．2]。Delauany三角网具有两个非常重系，笔者借鉴了AUTOCLUST算法的思想，提出了根要的性质：保证最邻近的点构成三角形，即三角形的据Delaunay三角剖分后所得三角形的形状、大小聚类边长之和尽量最小，且每个Delaunay三角形的外接圆的思想。据此提出了CBDT(ClusteringofBaSedonDe—la

8、unayTriangulation)算法，该算法与AUTOCLUST算收稿日期：2008—04—26法相比能实现同一簇中密度逐渐变化的簇。基金项目：山两省自然科学基