利用等边长正交格网进行层次聚合聚类  

Hierarchical Agglomerative Clustering Algorithm with Equilateral Orthogonal Grid

作　　者：林恒 龚威[1,2] 史硕 LIN Heng1, GONG Wei1,2, SHI Shuo1,2,3(1.State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University Wuhan 430079, China; 2. Collaborative Innovation Center of Geospatial Technology,Wuhan 430079, China; 3. School of Resource and Environmental Sciences,Wuhan University, Wuhan 430079, Chin)

机构地区：[1]武汉大学测绘遥感信息工程国家重点实验室,湖北武汉430079 [2]地球空间信息技术协同创新中心,湖北武汉430079 [3]武汉大学资源与环境科学学院,湖北武汉430079

出　　处：《武汉大学学报（信息科学版）》2018年第5期786-791,共6页Geomatics and Information Science of Wuhan University

基　　金：国家自然科学基金(41127901);国家教育部创新团队发展计划(IRT1278);湖北省自然科学基金(2015CFA002)~~

摘　　要：层次聚合聚类的典型算法可以体现研究数据的多尺度特征,但是典型算法的时空复杂度太高。通过将数据所在空间划分成等边长正交格网,结合3点间距离的传递性排除冗余计算,并将其推广到N维空间。设计了一种与典型算法遵循相同的单链规则,可即时计算类间距离且无需计算距离矩阵的算法,在获得与典型算法相同的多尺度聚类序列的同时,所需内存远小于典型算法。实验结果表明,该算法无需人工干预且不使用距离矩阵,能大幅降低层次聚合聚类的运行时间,但是效率优势随空间维数增长逐渐降低。The process of the typical algorithm of hierarchical agglomerative clustering（HAC） reflects the multi-scale property of studying data,which is crucial in the research of Geography,Cartography and Remote Sensing.However,the typical algorithm is inefficient and costs too much memory space.In this paper,considering the transitivity of distances among points,the studying data are divided into equilateral orthogonal grids to avoid redundant computation;moreover,the feasibility of the proposed algorithm is proved in theory and extended to N-dimensional space.The proposed algorithm follows the same single-link clustering rule as the typical algorithm;and therefore,it generates the same multi-scale clustering series as the typical algorithm.Since there is no distance-matrix,the proposed algorithm costs much less memory space.Experimental results show that although without any manual intervention and distance-matrix,the proposed algorithm obviously improves the efficiency of HAC.However,the advantage decreases as the extending of the dimension number.

关 键 词：层次聚合聚类 多尺度特征 效率优化 等边长正交格网 

分 类 号：P208[天文地球—地图制图学与地理信息工程]