作业C：voronoi图在聚类分析中的应用调研

1、SouthChinaUniversityofTechnology研究生课程论文（2015-2016学年第二学期）计算几何研究生：王志强提交日期：12/8/2017研究生签名：学号201510105289学院计算机科学与工程课程编号B0001009课程名称计算几何学位类别博士任课教师李桂清教师评语：成绩评定：分任课教师签名：年月曰1、课程论文要有题目、作者姓名、摘要、关键词、正文及参考文献。论文题目由研究生结合课程所学内容选定；摘要500字以下，博士生课程论文要求有英文摘要；关键词35个；参考文献不少于10篇，并应有一定的外文文献。2、论文要求自己动手撰写，如发现论文是从网上下载的，或者是抄袭剽

2、窃别人文章的，按作弊处理，本门课程考核成绩计0分。3、课程论文用A4纸双面打印。字体全部用宋体简体，题目要求用小二号字加粗，标题行要求用小四号字加粗，正文内容要求用小四号字；经学院同意，课程论文可以用英文撰写，字体全部用TimesNewRoman,题目要求用18号字加粗；标题行要求用14号字加粗，正文内容要求用12号字；行距为2倍行距（方便教师批注）；页边距左为3cm、右为2cm、上为2.5cm、下为2.5cm；其它格式请参照学位论文要求。4、学位类别按博士、硕士、工程硕士、MBA、MPA等填写。5、篇幅、内容等由任课教师提出具体要求。 Voronoi图在聚类分析中的应用进展综述王志强摘要：V

3、oronoi图是本学期计算几何课程着重教研的内容之一，有着诸多形式化特性的Voronoi图经数学演绎可广泛应用于生产实践的各个邻域。基于原型的聚类算法主要依数据点的近邻特性进行相似性度量，应用Voronoi图进行聚类分析的相关文献中也主要是利用了Voronoi图的近邻特性。本文先概述Voronoi图和聚类分析的基本概念和相关特性，再介绍通过Voronoi图聚类的一般方法，最后逐一介绍最新的相关文献中的创新点。关键词：Voronoi图；聚类分析；k-means聚类1.简介本节内容简要介绍回顾了Voronoi图和聚类算法的基本概念和性质。首先，简明地复述了Voronoi图的概念，并给出了具体的Vo

4、ronoi图例加深读者对Voronoi图的直观印象。其次，简要地归纳了Voronoi图的部分性质，着重讨论了对聚类过程起关键作用的近邻特性。随后，介绍了聚类的基本概念和常见的聚类思想方法框架。最后探讨了聚类分析进行相似性（连通性）度量时有赖于“距离”或“最近邻”，而Voronoi图的最近邻特性是其得以在聚类过程中应用的主要原因。1.1Voronoi图简介Voronoi图是计算儿何邻域首先提出并研究的内容：假设有一平面，其中有n个离散点，按最邻近原则将平面分成儿个区域，每个点与它的最近邻区域相关联。图1所示的是一个Voronoi图，便于直观地给出Voronoi图的相关概念。其中黑色的点称为基点，

5、基点所处的区域称为Voronoi单元。我们可以发现，07-3VoronoiH图1：Voronoi图，选自教材第186页1任一单元中的平面点距离其所在的区域的基点的距离最近。一般地，Vonoroi图的特性可规纳如下2：最近邻近特性。在Voronoi图中，若两个Voronoi单元间不存在其它单元，那么它们的Voronoi单元必存在一条公共边。除公共边外,Voronoi图中的不同的Voronoi多边形铺满了整个二维平面。这种空间结构隐含地表达了空间目标之间的全部邻近信息，由这一特性可方便地求解最近目标对和最邻近目标问题。点集凸多边形外壳由三角网的外边界构成了不存在任何点位于三角形的外接圆内部，反之，

6、如果一个三角网满足此条件，那么它就是Delaunay三角网若将三角网中的所有三角形的最小角升序排序，那么Delaunay三角网的排列所得的数值最大，可以看出，Delaunay三角网是“最接近于规则化的”的三角网1.2聚类算法简介 聚类分析是模式识别、数据挖掘等领域的重要研究内容之一，也是通过无监督学习发现数据内在结构的主要方法之一。聚类广泛应用于语音识别、字符识别、图像分割与机器视觉、数据压缩与信息检索，对心理学、生物学、考古学、地质学等研究也起着重要作用。然而，聚类至今未形成一个学术界公认的定义，一般认为聚类是在没有类标签帮助下，通过对数据的内在特性的分析，将相似的数据样本点归为一类的过程。

7、数十年來，经典聚类算法层出不穷，2014年Science杂志上也刊载了一篇基于快速寻找密度峰值的聚类算法3,但从聚类的思想和方法上可归为如下儿种类别：划分方法(partitioningmethods)K-MEANS算法K-MEDOIDS算法CLARANS算法层次方法(hierarchicalmethods)BIRCH算法CURE算法CHAMELEON算法基于密度的方法(density-basedmethods)DBSCAN算法OPTICS算法DENCLUE算法基于网格的方法(grid-basedmethods)STING算法CLIQUE算法WAVE-CLUSTER算法基于模型的方法(model

8、-basedmethods)传递闭包法，直接聚类法，布尔矩阵法，基于统计的聚类，相关性分析聚类、神经网络聚类、基于进化算法的聚类等各聚类算法虽形式各异、思想方法各有特色，但都依赖于“距离度量”“近邻信息”等來区分定义样本点间的相似性。基于划分方法中，类内距离最小和类间距离最大通常是划分过程中的优化目标；基于密度的方法中，局部密度的估计和指定半径内样本点个数或最近邻样本点所占区域大小有关；层次聚类和模型聚类过程都会用到样本点的最近邻信息。Voronoi图可以应用于聚类过程正是依赖于最近邻特性。2.Voronoi图聚类的一般方法基于Voronoi图的聚类算法通常是一类基于原型的聚类算法，但在实现上

9、常利用基于密度或基于网格的聚类思想，也就是将Voronoi图代替网格來实现聚类。2.1网格聚类及其缺点网格聚类方法本质上是基于密度聚类方法的优化，相比于基于密度的方法，基于网格进行密度估计有较低的时间开销。网格聚类方法假设位于同一个网格的数据点都属于相同的类，因而网格的大小和网格的位置将显著影响基于空间数据聚类结果。极端的特例是：每个网格都足够小，那么所有不同的样本点都各自归属一类；网格足够大，所有的样本点都属于相同的类。图2所示”的数据】数据取自参考文献3集包含2000个样本点，直观上应分为5个类。图2：某数据集示例图3中左侧网格选取过大，因而所有数据被视为同一类，而右侧中9个网格中只有3个

10、网格中的样本点被视为高密度点，其余6个网格的数据均被视为低密度点，因而只分为3类。图3：左侧所有数据属于同一网格，右侧数据分为3类从上例可直观看出，网格虽然简化了样本点密度的估计，但它的定义却与类的直观概念相距共远，调整网格的大小及位置会得出不同的聚类结果。连同密度阈值共有三个参数，在实际应用中难以找出一个通用的确定各个最优参数值的方法。事实上，同一网格内的数据距离该网格的中心要比它们到其它网格的中心更近，因而也可以将基于网格的聚类算法看作是基于原型的聚类算法的特例：基于网格的聚类算法是由相互平行或垂直的多个原型演化并且原型点位于特定位置的聚类算法。2.2用Voronoi图替代网格小节1.1中

11、我们讨论了Voronoi图的最近邻特性，即：任一单元中的平面点距离其所在的区域的基点的距离最近。如图4所示：B点到所属单元母点A的距离比它到所有其他母点的距离都短，且对于母点A所在的单元中的任一数据点都有这个结论。图4：Voronoi图示例通过直观地比较分析，我们可以发现Voronoi图的定义比网格更符合数据类(簇)的要求：Voronoi单元的形状可以是任意凸多边形，而网格的形状只能是矩形Voronoi单元的大小不是固定的，用Voronoi图代替网格进行聚类不需要设定大小和位置参数，只需确定的母点位置就可以得出确定的Voronoi图，故而每个数据点所属的类也可唯一确定以上分析我们可以得出：用V

12、oronoi图代替网格进行聚类分析有诸多便利之处，对二维空间数据聚类是可行的。2.3基于Voronoi图聚类的基本思想与基于网格的聚类算法思想类似，基于Voronoi图的聚类算法主要步骤如下：根据数据样本空间分布构造平面上的Voronoi图(初始时随机选取母点)将每一数据样本点划分到其所属的Voronoi单元计算Voronoi单元的密度(一个Voronoi单元可视为一个类簇)低于设定密度阈值的视为低密度点，舍弃低密度单元，只计算非低密度单元的数据点质心作为下轮迭代中的母点一般地，算法初始化时选定较多的Voronoi单元母点数(心2c,編是初始时母点数量，c是最佳类簇个数)。假设c=5,我们选取

13、褊=50,第一轮迭代中必然存在有低密度单元，不妨假设存在20个低密度单元。我们只计算30个非低密度单元中样本点的质心位置，作为第二轮迭代的Voronoi单元母点，总数为心=30,依次迭代，直到某轮所有的Voronoi单元都是非低密度单元时则此时的Voronoi单元数目为最终的类个数。此后还需多个循环迭代使Voronoi单元母点的新位置的变化小于设定的阈值，进而形成稳定的聚类结果。算法1是基于Voronoi图聚类的形式化描述。算法1：基Voronoi图的聚类算法Input:设定密度阈值I、初始Voronoi单元数上；扫描聚类数据样本点，找出各个维度坐标的最大/最小值，构造平面上包含所有的数据点的

14、矩形；随机生成Voronoi图母点，构建Voronoi图；Repeat：计算整个区域内的点平均密度(“)7亥轮循环中待聚类的点数/整个区域面积)；指定待聚类的数据点所属的Voronoi单元，计算每个Voronoi单元中的数据点个数；Foreach/ink计算第i个Voronoi单元格的点密度q;r?将第i个Voronoi单元格标记为非低密度单元并求出质心：Po将第i个Voronoi单元格标记为低密度单元；Endfor以本轮求得的非低密度Voronoi单元的质心为新一轮构造Voronoi图的母点构图；UntiI当前循环中的Voronoi图中低密度单元数为0;此时Voronoi图的单元格数不再发生

15、变化，其数值等于最终的聚类类个数；Repeat计算每个Voronoi单元中的数据点的质心；以计算出的质心为新一轮的母点构建Voronoi图；(1刀Until本轮循环中母点位置的变化值小于设定阀值；(18)Output:当前母点为聚类中心，每个音单元的样本点属于其母点所在的类。以上算法整体时间复杂度为0(71),空间复杂度也是O(n),是一类相对高效的聚类算法。3基于Voronoi图聚类的部分有代表性的研究进展硕士二年级起我开始以聚类算法作为主要研究方向，本次计算几何的课程作业也以调查研究Voronoi图在聚类上的应用为题。前2节分别介绍了Voronoi图和聚类的基本概念和Voronoi图聚类的

16、一般方法，本节分别介绍Ajani4、Xiang5、Reddy6和Edla7-8于2010年以來的发表的研究成果。3.1基于哈希索引和Voronoi图的聚类算法Ajani(2013)提出了一种基于哈希索引和Voronoi图的用于处理不确定数据?的高效聚类算法，该方法整合了哈希技术、Voronoi图和K-means聚类算法，获得了比经典K-means聚类算法更好的效果。图5：基于哈希索引和Voronoi图的聚类算法流程图该文的研究动机基于假设：如果不确定性的信息可以直接应用于聚类过程,那么聚类结果的质量将比未使用这一额外信息的要高910o然而，传统的聚类方法是针对处理确定的数据(即每个点都有确定的

17、值)设计的，因而难以解2不确定数据(uncertaindata)简介4：Uncertaindatahasbeenevolvedinmanyareas.Atraditionalfieldwhereuncertaintyisevident,suchassensordata,isjoinedbymanytopics&omcomputerscienceanddataanalyticsForexample,explaindataminingforcontinuousuncertainty.Continuousuncertaintyisapropertyoftheuncertaintyregionmost

18、lyfoundinsensornetworkwheredevicelocationsareuncertaininpractice.Amobiledevicemaydeduceandreportitslocationbycomparingthestrengthsofradiosignalsfrommobileaccesspoints.Besidescontinuousuncertainty,thefieldofuncertaindataobjectsdiscretevalueshasalsoattractingfurtherresearchinmanyways.Mostrecentresearc

19、hinthefieldofdataminingisperformedwithafocusonclusteringuncertainpoints.决数据的不确定性。解决不确定数据的的可行方法之一是通过选取有代表性的样本点将不确定数据转为定值数据(point-valueddata),该文通过索引技术(Indexing)将不确定数据转为索引表(indextable),然后基于该索引表进行k-means聚类，最后使用Voronoi图对k-means聚类结果精细化(refinement)。3.2Voronoi聚类(Voronoi-clusteringforplanedata)Xiang(2014)提出了

20、针对平面数据的Voronoi聚类方法，与传统基于Voronoi图的聚类方法类似，该论文主要利用Voronoi图的最近邻特性(thenearestneighbor),相比于经典的k-means聚类所提算法可以自行发现类个数。如图6所示，Voronoi单元通常是凸多边形，比之于网格聚类中的矩形直观上更符合类簇的特点。(a)(b)图6：加入新中心点(母点)后Voronoi单元由3个增加为4个如图6所示，Voronoi单元的面积将直接影响Voronoi单元的平均密度，通常Voronoi单元的平均密度定义为Voronoi单元内的样本点总数与Voronoi单元面积之商。假定Voronoi某个单元的顶点序列

21、依次为alfa2,.,am,am+1,且4n+i=s每个顶点的坐标表示为(i=1,2m),则可通过顶点坐标确定此单元的面积：1S=|兀*2一271+273一2+7171一兀1%1有了Voronoi单元的面积计算方法，可以用Voronoi单元的平均密度代替网格的平均密度，从而使用Voronoi图取代网格的概念并借鉴网格聚类的思想进行数据聚类操作，具体流程见图7。II否图7：Voronoi聚类流程图3.3基于Voronoi图初始化中心点的k-means聚类算法Reddy(2012)提出了通过Voronoi图初始化k-meansk-meansalgonthmisoneofthefamousparti

22、tioningclusteringtechniquesthathasbeenstudiedextensivelyHowever,themajorproblemwiththismethodthatitcannotensuretheglobaloptimumresultsduetotherandomselectionofinitialclustercenters.However,themajorproblemwiththismethodthatitcannotensuretheglobaloptimumresultsduetotherandomselectionofinitialclusterce

23、nters.详见6,p396聚类中心点的算法，该文的主要研究动机是“初始点的选取对k-means聚类的最终结果影响较大”,而借助Voronoi图可以有效地选出位于大半径Voronoi环(higherradiusVoronoicircles)边界的点作为聚类初始点。图8：Voronoi图(左)与Voronoi环(只给出了部分环)对一Voronoi顶点12,其最大空环(thelargestemptycircle)是以其为中心穿过多个相邻母点的圆环，且内部不包含其他母点，表示为CirS(v),直观上如图8右侧所示。以最大Voronoi环为迟度初始化fc-means聚类中心点可使迭代收敛速度更快，聚类

24、结果更优。该算法有两个阶段，第1阶段是借助Voronoi初始化聚类中心点，第2阶段是将初始化后的聚类中心点输入k-means得到最终的聚类结果。基本的思想方法如下：由给定71个数据点集S和聚类的类个数k构建Voronoi图；将Voronoi图的所有顶点按他们的最大Voronoi环半径降序排序，存储在sorted_vertex数组中；维护两个初始为空的数组Test和cCenter,Test用于存储Voronoi环周长上的点，cCenter用于存储类中心位置：从最大半径的Voronoi环开始，将环周上的点存储于Test中，找出Test中存储的任两点间距离比半径小的点，将他们从Test数组中移除，满

25、足条件的放入cCenter数组中。然后从第二个大的Voronoi环开始重复移除Test数组中元素的工作，再找出Test中和cCenter中存储的任两点小于当前Voronoi环半径的点并从cCenter中移除。遍历所有Voronoi环后将cCenterU数组中剩下的点将作为聚类中心点。该文借助Voronoi环初始化k-means聚类中心，通过实验验证了所提算法相对于经典k-means聚类算法的优越性。此外，Edla(2012)也提出了和本小节算法类似的借助Voronoi环初始化/c-means聚类中心点的算法，与Reddy(2012)所提算法不同之处在于Edla(2O12)引入了归一化信息增益(

26、normalizedinformationgain)来筛选聚类的类质量,但算法涉及Voronoi图应用的部分与Reddy(2012)所提算法基本相同。4.小结本文概述了Voronoi图在聚类中的应用，先介绍了Voronoi聚类的一般思想方法，乂介绍了相关文献的近期成果。总得來说，人们可以利用Voronoi图的最近邻特性进行聚类，并提出了一系列的Voronoi图聚类方法。14 参考文献11(荷)伯格(Berg,M)计算几何的算法与应用：第3版M世界图书出版公司北京公司，2013.刘金义，刘爽.Voronoi图应用综述J.图学学报，2004,25(2):125-132.RodriguezA,Lai

27、oAMachinelearningClusteringbyfastsearchandfindofdensitypeaks.J.Science,2014,344(6191):14926AjaniS,WanjariMAnEfficientApproachforClusteringUncertainDataMiningBasedonHashIndexingandVoronoiClusteringC/InternationalConferenceonComputationalIntelligenceandCommunicationNetworks2013:486490XiangZ,YuZVoronoi

28、一clusteringforplanedataC/InternationalConferenceonNaturalComputation.IEEE,2014ReddyD,JanaPKInitializetionforKmeansClusteringusingVoronoiDiagramEJProcediaTechnology,2012,4(4):395-400.EdlaDR,JanaPKAnovelclustaringalgorithmusingvoronoidiagramC/SeventhInternationalConferenceonDigitaiInformationManagemen

29、t2012:3540EdlaDR,JanaPKClustaringBiologicalDataUsingVoronoiDiagramtC/InternationalConferenceonAdvancedComputing,NETWORKINGandSecurity.2011:188-197“ClustetingUncertainDataWithPossibleWorldsverBenjaminVolk,FrankRosenthal,MartinHahmann,DirkHabich,WolfgangLehner,IEEEInternationalConferenceonDataEngineer

30、ingAggarwalCC,YuPSASurveyofUncertainDataAlgorithmsandAppliestionsJIEEETransaetionsonKnowledge&DataEngineering,2009,21(5):609623ZhongC,MiaoD,WangRAgraph-theoreticalclustetingmethodbasedontworoundsofminimumspanningtreesJPatternRecognition,2010,43(3):752766KoivistoinenH,RuuskaM,ElomaaTAVoronoiDiagramAp

31、proachtoAutonomousClusteringM/DiscoveryScienceSpringerBerlinHeidelberg,2006:149160LeeI,YangJVoronoibasedTopologicalInformationforCombiningPartitioningandHierarchicalClusteringC/InternationalConferenceonComputationalIntelligenceforModelling,Control&Automation,&InternationalConferenceonIntelligentAgents,WebTechnologies&InternetCommerceIEEEComputerSociety,2005:484一489ChauM,ChengR,KaoB,etal.UncertainDataMining:AnExampleinClustaringLocationDataC/Pacific-AsiaConferen