| 利用等边长正交格网进行层次聚合聚类 |
| |
| 引用本文： | 林恒,龚威,史硕.利用等边长正交格网进行层次聚合聚类[J].武汉大学学报(信息科学版),2018,43(5):786-791. |
| |
| 作者姓名： | 林恒 龚威 史硕 |
| |
| 作者单位： | 1.武汉大学测绘遥感信息工程国家重点实验室, 湖北 武汉, 430079 |
| |
| 基金项目： | 国家自然科学基金41127901国家教育部创新团队发展计划IRT1278湖北省自然科学基金2015CFA002 |
| |
| 摘 要： | 层次聚合聚类的典型算法可以体现研究数据的多尺度特征，但是典型算法的时空复杂度太高。通过将数据所在空间划分成等边长正交格网，结合3点间距离的传递性排除冗余计算，并将其推广到N维空间。设计了一种与典型算法遵循相同的单链规则，可即时计算类间距离且无需计算距离矩阵的算法，在获得与典型算法相同的多尺度聚类序列的同时，所需内存远小于典型算法。实验结果表明，该算法无需人工干预且不使用距离矩阵，能大幅降低层次聚合聚类的运行时间，但是效率优势随空间维数增长逐渐降低。
|
| 关 键 词： | 层次聚合聚类 多尺度特征 效率优化 等边长正交格网 |
| 收稿时间： | 2016-01-21 |
Hierarchical Agglomerative Clustering Algorithm with Equilateral Orthogonal Grid |
| |
| Institution: | 1.State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan 430079, China2.Collaborative Innovation Center of Geospatial Technology, Wuhan 430079, China3.School of Resource and Environmental Sciences, Wuhan University, Wuhan 430079, China |
| |
| Abstract: | 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. |
| |
| Keywords: | |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《武汉大学学报(信息科学版)》浏览原始摘要信息 |
| 点击此处可从《武汉大学学报(信息科学版)》下载免费的PDF全文 |
|
