留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

林恒 龚威 史硕

林恒, 龚威, 史硕. 利用等边长正交格网进行层次聚合聚类[J]. 武汉大学学报 ● 信息科学版, 2018, 43(5): 786-791. doi: 10.13203/j.whugis20150668
引用本文: 林恒, 龚威, 史硕. 利用等边长正交格网进行层次聚合聚类[J]. 武汉大学学报 ● 信息科学版, 2018, 43(5): 786-791. doi: 10.13203/j.whugis20150668
LIN Heng, GONG Wei, SHI Shuo. Hierarchical Agglomerative Clustering Algorithm with Equilateral Orthogonal Grid[J]. Geomatics and Information Science of Wuhan University, 2018, 43(5): 786-791. doi: 10.13203/j.whugis20150668
Citation: LIN Heng, GONG Wei, SHI Shuo. Hierarchical Agglomerative Clustering Algorithm with Equilateral Orthogonal Grid[J]. Geomatics and Information Science of Wuhan University, 2018, 43(5): 786-791. doi: 10.13203/j.whugis20150668

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

doi: 10.13203/j.whugis20150668
基金项目: 

国家自然科学基金 41127901

国家教育部创新团队发展计划 IRT1278

湖北省自然科学基金 2015CFA002

详细信息
    作者简介:

    林恒, 博士生, 主要从事多尺度GIS、聚类及三维可视化方面研究。edogawakou@163.com

    通讯作者: 龚威, 博士, 教授。weigong@whu.edu.cn
  • 中图分类号: P208

Hierarchical Agglomerative Clustering Algorithm with Equilateral Orthogonal Grid

Funds: 

The National Natural Science Foundation of China 41127901

the Program for Innovative Research Team in University of Ministry of Education of China IRT1278

the Natural Science Foundation of Hubei Province 2015CFA002

More Information
    Author Bio:

    LIN Heng, PhD candidate, specializes in multi-scale GIS, clustering and 3D visualization. E-mail:edogawakou@163.com

    Corresponding author: GONG Wei, PhD, professor. E-mail:weigong@whu.edu.cn
图(5) / 表(2)
计量
  • 文章访问数:  852
  • HTML全文浏览量:  43
  • PDF下载量:  327
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-01-21
  • 刊出日期:  2018-05-05

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

doi: 10.13203/j.whugis20150668
    基金项目:

    国家自然科学基金 41127901

    国家教育部创新团队发展计划 IRT1278

    湖北省自然科学基金 2015CFA002

    作者简介:

    林恒, 博士生, 主要从事多尺度GIS、聚类及三维可视化方面研究。edogawakou@163.com

    通讯作者: 龚威, 博士, 教授。weigong@whu.edu.cn
  • 中图分类号: P208

摘要: 层次聚合聚类的典型算法可以体现研究数据的多尺度特征,但是典型算法的时空复杂度太高。通过将数据所在空间划分成等边长正交格网,结合3点间距离的传递性排除冗余计算,并将其推广到N维空间。设计了一种与典型算法遵循相同的单链规则,可即时计算类间距离且无需计算距离矩阵的算法,在获得与典型算法相同的多尺度聚类序列的同时,所需内存远小于典型算法。实验结果表明,该算法无需人工干预且不使用距离矩阵,能大幅降低层次聚合聚类的运行时间,但是效率优势随空间维数增长逐渐降低。

English Abstract

林恒, 龚威, 史硕. 利用等边长正交格网进行层次聚合聚类[J]. 武汉大学学报 ● 信息科学版, 2018, 43(5): 786-791. doi: 10.13203/j.whugis20150668
引用本文: 林恒, 龚威, 史硕. 利用等边长正交格网进行层次聚合聚类[J]. 武汉大学学报 ● 信息科学版, 2018, 43(5): 786-791. doi: 10.13203/j.whugis20150668
LIN Heng, GONG Wei, SHI Shuo. Hierarchical Agglomerative Clustering Algorithm with Equilateral Orthogonal Grid[J]. Geomatics and Information Science of Wuhan University, 2018, 43(5): 786-791. doi: 10.13203/j.whugis20150668
Citation: LIN Heng, GONG Wei, SHI Shuo. Hierarchical Agglomerative Clustering Algorithm with Equilateral Orthogonal Grid[J]. Geomatics and Information Science of Wuhan University, 2018, 43(5): 786-791. doi: 10.13203/j.whugis20150668
  • 层次聚合是一种基本的聚类思想,单纯的层次聚合可以作为一种独立的聚类算法,另外还有很多基于层次聚合的聚类算法[1-3]。层次聚合聚类(hierarchical agglomerative cluster, HAC)[4]的典型算法在计算距离矩阵和最小类间距离的过程中需要耗费大量的运算时间和内存空间,因此常被认为是一种低效的算法[5]。另外,在模式识别领域获得合适的聚类结果是最终的目标,聚类过程往往只是某个目标函数的优化过程(如K-均值[6]、Chameleon[3]), 聚类中间态并不被看作算法的一种成果,因此不受重视。但是,层次聚合的过程体现了研究数据的多尺度特征,该特征在地理学[7-8]、制图学[9-11]和遥感领域[12-14]的研究中具有非常重要的意义。文献[15]在图斑集聚类研究中使用了层次聚类,同时利用图斑的邻接关系排除了大量冗余计算。本文基于层次聚合思想,面向更加一般化的研究数据,提出了一种基于等边长正交格网的层次聚合聚类算法。这种算法得到的多尺度聚类序列与层次聚合聚类的典型算法完全相同,而且不需要人工干预和距离矩阵就可以排除大量冗余计算,有效减少了运算时间和内存占用。

    • 层次聚合聚类的典型算法(简称为典型算法)的基本思路是:将研究数据中每一个点当作一个独立的类,以两个类中最近两点的距离作为两类的类间距离;找到当前所有类中最小的类间距离,若两个类的类间距离等于当前最小的类间距离,则将这两个类合并为一个类。重复上述计算判断过程,直到所有的类合并成为一类(或达到预先设定的条件)为止。

      图 1所示,数据ABCD是一维数轴上4个点(ABCD),按照层次聚合聚类算法原理,计算4个点中任何两点之间的距离来判断当前最小类间距离。由图 1可知,距离|SAB|比|SAC|和|SAD|都小,所以在计算点A的最小类间距离的过程中无需计算|SAC|和|SAD|。因此,在一维空间中计算最小类间距离时,只需计算类(类内点在一个连续的区间中)的边缘点与相邻非同类点的间距。这是由于一维空间中3点间距离存在简单的传递性,即若ABC,则|SAB|<|SAB|+|SBC|= |SAB|+|SBC|=|SAC|。但当一维空间推广到二维空间时,3点之间距离的传递性就变得更加复杂(若3点不共线,则|SAB|+|SBC|≠|SAB|+|SBC|)。如图 2所示,任意在圆A(用⊙A表示)内的点B都存在|SAB|<|SAC|,任意⊙A外的点D都存在|SAD|>|SAC|。但是很难通过对点AC坐标的简单比较判断其他点与⊙A的相对关系,除非比较其他点到圆心A的距离与|SAC|的大小。

      图  1  一维数轴上多点间距离的传递性

      Figure 1.  Transitivity of Distances Among Points in 1-Dimensional Axis

      图  2  二维空间中多点间距离的传递性

      Figure 2.  Transitivity of Distances AmongPoints in 2-Dimensional  

    • 本文所提出的层次聚合聚类算法综合考虑了二维空间中距离的传递性和等边长正交格网空间划分这两个因素。

      正交格网可以通过简单的坐标值对比把数据所在空间分隔为若干个区域单元,通过区域单元的邻接性可以粗略比较数据点间的相对距离。而结合3点之间距离的传递性质,可以使得数据点间相对距离的比较更加精确。假定数据点在二维空间中随机分布,从最近点搜索效率角度看,等边长正交格网的搜索效率高于非等边长正交格网。

      图 3所示,将图 3中0<x<3, 0<y<3范围内等分的9个1×1正方形看作一套九宫格,二维平面空间中有一点A(1.5, 1.7)处于正中心的宫格中,以点A为中心、以0.3为半径r作实线圆。若点A在中心宫格范围内的最近点在实线圆内,则该最近点为点A的全局最近点;若点A在中心宫格范围内不存在最近点或者最近点不在实线圆内,则进一步计算点A与中心宫格外围8个宫格范围内数据点的点间距离,并以点A为中心、以1.3为半径作圆。依此类推,判断相应范围内的最近点是否在圆形区域内以决定是否继续搜索更加外围一层的格网。与典型算法相比,在求解最近类间距离的过程中,若最小类间距离小于圆的半径,可避免当前搜索网格区域外的大量冗余计算。

      图  3  点A最近点的搜索范围

      Figure 3.  Searching Range of Nearest Neighbor of Point A

    • 图 3中若点A在1×1网格中存在最近点但该最近点不在实心圆内,则需比较点A与更外层的8个1×1网格中点的距离。在当前求解得到的最小类间距离大于实心圆的半径0.3时,若最小类间距离小于0.5,则仅有九宫格中顶层中间这一个网格应纳入下一步的搜索范围;若最小类间距离小于$\sqrt {0.34} $且大于0.5,则九宫格中仅有顶层中间和左右两层中间这3个网格被纳入下一步的搜索范围;若最小类间距离小于0.7大于$\sqrt {0.34} $,那么九宫格中底层3个网格都应该被排除在下一步的搜索范围之外;若最小类间距离大于0.7小于1.3,那么这一层8个网格都应当被列入下一步的搜索范围。

    • 研究数据可能具有多个维度,因此维度扩展性也是数据挖掘算法的重要特征。根据2.1节中的分析,在一维空间中根据3点之间距离的传递性,可以直接通过比较数据坐标值排除冗余运算;相比一维空间,二维空间中3点之间距离的传递性更加复杂。在2.1节中,通过等边长正交格网及以当前点为圆心与格网相切的圆形结合,排除了大部分冗余计算(若当前得到的最小类间距离小于圆的半径,则当前网格外部任意位置与当前点的距离必然大于当前得到的最小类间距离)。

      可以证得从二维到三维,再到N维,上述3点之间距离的传递性是相同的。假设N维空间中存在ABC这3点,3点所在某外包区间被划分为等边长正交格网。xi, A为点A在第i个维度上的坐标值,点A在某网格内且该网格在各维度值域相同(即∀xi, A∈(a, b), i=1, 2…Nab是数轴上的点值),点A所在网格有2NN-1维的外表面,表达式为xi=axi=b, i=1, 2…N。将点A沿N个维度正投影到该区域外表的2NN-1维空间上,正投影即为点A到该外表面的最近距离。比较点A到每个正投影点的距离,离点A最近的正投影点记为A′,点A到点A′的距离记作dAA。假设点B与点A的距离小于dAA,即dABdAA,则点B为点A在该网格内的最近点。假设点C在该网格外(即∃xi, C∉(a, b); i=1, 2…N),比较dAA(即min{|xi, A-y|; i=1, 2…N; y=a, b})和dAC(即$\sqrt {{{\sum\limits_{i = 1}^N {\left( {{x_{i, A}}-{x_{i, C}}} \right)} }^2}} $;∃xi, C∉(a, b) i=1, 2…N),由缩放法可知有dAA<$\sqrt {{{\sum\limits_{i = 1}^N {\left( {{x_{i, A}}-{x_{i, C}}} \right)} }^2}} $,形成不等式组:

      $$ \left\{ \begin{array}{l} {d_{AB}} < {d_{AA'}}\\ {d_{AA'}} = \min \left\{ {\left| {{x_{i, A}}-y} \right|;i = 1, 2 \cdots N;y = a, b} \right\}\\ {d_{AA'}} < \sqrt {\sum\limits_{i = 1}^N {{{\left( {{x_{i, A}}-{x_{i, C}}} \right)}^2}} } \\ \sqrt {\sum\limits_{i = 1}^N {{{\left( {{x_{i, A}}-{x_{i, C}}} \right)}^2}} } = {d_{AC}} \end{array} \right. $$ (1)

      由不等式组得dABdAC,即在N维空间中,若点AdAA范围内存在最近非同类点B,则点B为点A的全局最近非同类点,点A所在网格范围之外的任意点C不需要再参与计算和比较。因此,2.1节和2.2节中二维空间中的等边长正交格网与圆(球)形相结合的排除冗余计算的方法可以推广到N维空间中。

    • 根据2.1节及2.2节中例子的描述,结合2.3节中由二维到N维的推广,将例子中所用到的算法推广到N维空间中的一般情况。先确定数据中n个数据点在N维空间中的最小外包区间,将这个区间分别在N个维度上依据特定边长l等距离划分成若干单元。若在某些维度上剩余区间小于l,则延长至l并划分为一个单元,最终形成N维等边长正交格网。任意数据点都处于某个网格中,本文实验中取网格边长l为:

      $$ l = \frac{{\max \left\{ {\left| {{x_{i, j}}- {x_{i, k}}} \right|;i = 1, 2 \cdots N;j, k = 1, 2 \cdots n} \right\}}}{{\sqrt[N]{n}}} $$

      基于等边长正交格网的层次聚合聚类算法的流程为:(1)将研究数据分配到等边长正交格网中,将最短类间距离初值赋为无穷大,第一个数据点设置为当前点。(2)在当前数据点所在网格中寻找距离当前数据点最近的非同类点,若两者之间的距离小于最短类间距离,则将该距离赋值给最短类间距离。(3)若搜索范围没有进行外拓,则搜索范围为当前点所在网格;若搜索范围进行过外拓,则搜索范围为一层网格(或其中的一部分)。当前数据点沿着每个维度向当前搜索范围网格层的2NN-1维外表面正投影,寻找与当前点最近的投影点并将两者之间的距离记为格网距离。(4)比较格网距离与最短类间距离,若最短类间距离小于格网距离则进入步骤(6);否则,进入步骤(5)。(5)利用网格的邻接性将当前搜索过的网格外拓一层,比较当前数据点到这一层所有网格的距离(通过空间的对称性简化计算)。若当前数据点到某个网格的距离大于最短类间距离,则将该网格剔除出搜索范围;否则,该网格纳入到搜索范围,进入步骤(3)。(6)若当前点是最后一个数据点,则将类间距离等于最短类间距离的类合并,进入步骤(7);否则,下一个数据点成为当前数据点,进入步骤(2)。(7)若当前所有数据都合并为一个类(或者达到预先设定的条件),则算法结束;否则,将最短类间距离赋值为无穷大,将研究数据中第一个数据点设为当前点,进入步骤(2)。

    • 图 4所示,本文算法与典型算法一样,可以正确识别任意形状类簇。图 5中85个点的分布具有明显分形特征。从全局来看,除去中间孤立的点以外,其他点可以分为4类(由较粗的虚线框表示);从局部来看,每一个类还可以继续分为一个孤立点和4个类(由较细的虚线框表示)。层次聚合聚类的过程可以逐级识别相应尺度下的类簇,这一过程反映了研究数据的多尺度特征。

      图  4  本文算法识别的任意形状类簇

      Figure 4.  Clusters with any Shape Recognized by the Proposed Algorithm Recognized

      图  5  本文算法反映分形数据的多尺度特征

      Figure 5.  Multi-scale Property of Fractal Data Reflected by the Proposed Algorithm

      本文中用于测试算法运行时间的数据在每一个维度的值域相同,并且其坐标值在每一个维度的值域内随机取值。表 1中列出了无距离矩阵层次聚合聚类算法、典型算法以及本文算法在不同数据数量下的运行时间。由表 1可知,在相同的研究数据实验中,无距离矩阵层次聚合聚类算法所需时间最长,典型算法所需时间其次,本文算法所需时间明显少于上述两种算法。由于无距离矩阵层次聚合聚类算法和典型算法所需时间太长,本文没有进行大规模数据量的实验,仅根据这两个算法的复杂度O(n3)[15]给出理论值作为参考,与本文算法的实验结果进行对比。

      表 1  不同数据量下各算法执行时间对比

      Table 1.  Running Time Comparison of Algorithms with Different Data Sizess

      数据量/个 无距离矩阵层次聚合聚类算法 典型算法(使用距离矩阵) 本文算法
      /min /s /ms /min /s /ms /min /s /ms
      1 000 0 39 172 0 3 370 0 0 483
      2 000 5 12 735 0 26 848 0 1 919
      4 000 40 13 585 3 30 944 0 7 582
      8 000 321 48 68* 25 56 952 0 28 377
      10 000 628 32 266* 50 40 922* 0 43 930
      100 000 628 537 45 625* 50 682 1 875* 11 48 900
      注:标注有*的是根据复杂度[15]计算的理论值,字体加粗的是实验数据

      表 2中列出了典型算法与本文算法在同样数据量不同维数下的运行时间。由表 2可知, 相同数据量的条件下,维度的增加对典型算法没有明显影响,而本文算法的运行时间随实验数据维度的增加几乎成倍增长。当数据规模为3 000(5 000)、维度为6(7)时,本文算法运行时间超过典型算法。

      表 2  不同维度下各算法执行时间对比

      Table 2.  Running Time Comparison of Algorithms with Different Dimensional Data

      数据量/个 维度 典型算法(计算距离矩阵) 本文算法
      /min /s /ms /min /s /ms
      2 1 31 183 0 4 212
      3 1 32 87 0 10 171
      3 000 4 1 31 448 0 22 901
      5 1 30 153 0 49 842
      6 1 31 230 1 41 759
      2 6 45 338 0 12 511
      3 7 6 600 0 29 312
      5 000 4 7 9 549 1 5 302
      5 7 3 793 2 23 52
      6 7 8 67 5 33 858
      7 7 7 380 11 24 221

      典型算法需要先计算距离矩阵,然后在距离矩阵中寻找当前最小的类间距离并合并最近类。随着研究数据数量的增加,储存距离矩阵需要耗费大量的系统内存(空间复杂度为O(n2)),当数据量达到一定程度时所需内存将超过一般计算机内存;若没有事先计算距离矩阵,在寻找最短类间距离的时候即时计算类间距离,所需时间将会更多。本文算法不使用距离矩阵(空间复杂度降为O(n)),能大幅提高算法效率,不存在内存超限的风险。但是由于本文算法基于等边长正交格网,与单个网格相邻的网格数量为3N-1,随着维度N的增加, 格网外拓一层的计算量也快速增加,逐渐抵消掉格网排除冗余计算的优势。而典型算法最初计算好距离矩阵,然后在距离矩阵中搜索当前最小距离,对于维数的扩张并不敏感。

    • 本文通过对一维、二维空间中3点之间距离的传递性进行分析,结合等边长正交格网的划分,实现了对层次聚合聚类算法中大量冗余计算的排除,并将该算法推广到了N维空间。实验结果表明,本文算法依然保持典型层次聚合聚类算法的优势特征,且大幅降低了程序运行时间和所需内存空间。但是,随着数据维度的增加,本文算法的效率优势逐渐降低。因此,从研究数据的多尺度特征的角度看,本文算法适宜于处理维度较低、数据量较大的数据。另外,本文实验中格网的边长直接根据研究数据中的数据总量确定,但是多数情况下数据分布并不均匀,甚至差异巨大。在未来的研究中,将会参考文献[16]中的思路用嵌套的多级格网来划分研究数据,进一步提高算法的效率。

参考文献 (16)

目录

    /

    返回文章
    返回