全 文 ：第 wu卷 增刊 t
u s s y年 | 月
林 业 科 学
≥≤Œ∞‘׌„ ≥Œ∂ „∞ ≥Œ‘Œ≤„∞
∂²¯1wu o≥³qt
≥ ³¨qou s s y
系统聚类的一种优化算法实现
张 峰 张晓东 朱德海 刘峻明
k中国农业大学信息与电气工程学院 北京 tsss{vl
摘 要 } 从计算机程序设计的角度出发 o针对影响系统聚类算法执行效率的几个主要因素 o分别提出较合理的数
据结构来优化系统聚类的算法实现 o降低算法的时间和空间的复杂度 o增强系统聚类对大数据量的空间数据处理
能力 o并通过实际例子证明该优化算法的可行性 ∀
关键词 } 系统聚类 ~算法优化 ~数据结构
中图分类号 }×°vst1y 文献标识码 }„ 文章编号 }tsst p zw{{kussyl增 t p sttx p sx
收稿日期 }ussx p sy p uw ∀
基金项目 }国家 {yv课题/数字林业平台技术研究与应用0kussv„„us|sysl ∀
Αν Οπτιµιζεδ Αλγοριτηµ Ρεαλιζατιον φορ Σψστεµατιχαλ Χλυστερινγ
«¤±ªƒ ±¨ª «¤±ª÷¬¤²§²±ª «∏⁄¨ «¤¬ ¬∏∏±°¬±ª
kΧολλεγε οφ Ινφορµατιον ανδ Ελεχτριχαλ Ενγινεερινγ o Χηινα Αγριχυλτυραλ Υνιϖερσιτψ Βειϕινγ tsss|wl
Αβστραχτ } ≥¼¶·¨°¤·¬¦¤¯ ¦¯∏¶·¨µ¬±ª¬¶¤®¬±§²©·¼³¬¦¤¯ ¦¯∏¶·¨µ¬±ª °¨ ·«²§²©¶³¤·¬¤¯ ¤±¤¯¼¶¬¶o¤³³¯¬¨§º¬§¨ ¼¯¬± °¤±¼©¬¨ §¯¶q…∏·
¥¨¦¤∏¶¨ ²©·«¨ ¬¯°¬·¤·¬²±²©¬·¶²º± ¤¯ª²µ¬·«°o°¤±¼¶¼¶·¨°¤·¬¦¤¯ ¦¯∏¶·¨µ¬±ª³µ²ªµ¤°¶¦¤±.·³µ²¦¨¶¶·«¨ §¤·¤ ©¨©¬¦¬¨±¦¼q„¬°¬±ª¤·
¶¨√¨ µ¤¯ ©¤¦·²µ¶¯¬°¬·¨§·«¨ µ∏±±¬±ª ©¨©¬¦¬¨±¦¼o·«¬¶³¤³¨µ³∏·¶©²µº¤µ§¤µ¨¤¶²±¤¥¯¨§¤·¤¶·µ∏¦·∏µ¨·²²³·¬°¬½¨ ·«¨ ¦²°³∏·¨µ³µ²ªµ¤°
²©¶¼¶·¨°¤·¬¦¤¯ ¦¯∏¶·¨µ¬±ª¥¤¶¨§²±·«¨ ¦²°³∏·¨µ³µ²ªµ¤°°¬±ªoº«¬¦«µ¨§∏¦¨¶·«¨ ¦²°³¯ ¬¨¬·¼²©·¬°¨ ¤±§¶³¤¦¨ ¤±§ ±¨«¤±¦¨¶·«¨
¦¤³¤¥¬¯¬·¼·² §¨¤¯ º¬·«¤ªµ¨¤·§¨¤¯ ²©¶³¤·¬¤¯ §¤·¤q ׫¨ ¦¤¶¨ ²© ¤³³¯¬¦¤·¬²± «¤¶³µ²√¨ §·«¤··«¨ ²³·¬°¬½¨ § °¨ ·«²§¬¶«¬ª«¯¼
©¨©¨¦·¬√¨ q
Κεψ ωορδσ} ¶¼¶·¨°¤·¬¦¤¯ ¦¯∏¶·¨µ¬±ª~¤¯ª²µ¬·«° ²³·¬°¬½¤·¬²±~§¤·¤¶·µ∏¦·∏µ¨
随着 ŠŒ≥技术的发展 o越来越多的行业开始引入 ŠŒ≥概念 oŠŒ≥的应用逐渐深入到人们的生产和生活中 ∀
计算机数据库技术k⁄…≥l !计算机辅助设计k≤„⁄l !计算机辅助制图k≤„ l !计算机图形学k¦²°³∏·¨µ
ªµ¤³«¬¦¶l的发展对 ŠŒ≥的进步起着强烈的支持作用 ∀
空间分析作为地理信息系统的主要功能特征 o也是评价一个地理信息系统成功与否的主要指标 ∀它基
于地理对象的位置和形态的空间数据分析技术 o目的在于提取和传输空间信息k郭仁忠 ousstl ∀根据空间分
析作用数据性质的不同 o一般把空间分析分为基于空间图形数据的分析运算 !基于非空间属性的数据运算 !
空间和非空间数据的联合运算k汤国安 oussul ∀
空间分析的方法有很多种 o其中空间聚类是最常用的一种 o它是基于空间图形数据进行空间信息提取的
一种空间分析方法 ∀所谓空间聚类 o就是将一组空间对象划分为一定数目的有意义的簇 o使得同一簇中的对
象有较大的相似度 o而属于不同簇的对象差别较大 o即相异度较大k‹¤± ετ αλqousstl ∀聚类技术在许多领域
得到了广泛应用 o如统计数据分析 !模式匹配和图像处理以及商业领域等 ∀大到地球和宇宙观察数据处理 o
小到生物基因结构分析 o聚类技术都有其用武之地k戴晓燕等 oussvl ∀例如 o根据全国各个气象观测点的多
维数据 o利用空间聚类技术分析国家各个地区的气候条件 o制定气象分布图 ~对国土资源的聚类分析 o可以
得到国家的国土资源的分布情况 o对于发展地方经济和加强国家建设都有较强的指导意义 ~对不同城市经
济发展水平的聚类分析 o可以了解我国经济发展的趋势 ~目前 o数字地球 !数字城市 !数字农业 !数字林业等
一系列/数字化0工程的提出 o使得空间聚类分析作为地理信息系统的一项基本功能得到了前所未有的重视
和应用 ∀
然而 o空间聚类一直是空间分析中一个相对比较困难的问题 o大规模 !多维空间数据的聚类尤其突出k邸
凯昌 ousstl ∀许多专家学者从算法本身的角度针对一些应用提出了各种改进或创新的算法k刘夫涛等 o
usss ~王美华 ousswl o这些算法的提出很少考虑到计算机实现的难易程度和执行效率问题k田纪春等 ot||wl o
所以导致一些空间聚类算法虽然在思想上很容易理解 o但实施时却往往碰到了一些难以克服的问题 ∀本文
从计算机数据结构的角度来分析一种典型的空间聚类算法 ) ) ) 系统聚类 o使之不但在算法上容易理解 o而且
在执行时也有较高的效率 ∀
t 系统聚类算法
系统聚类算法是一种被广泛使用的典型空间聚类算法 ∀首先假定每一个空间数据对象自成一类 o然后
根据一定的聚类判别准则对最相似的 u个类进行合并 ∀随着相似类的合并 o类越来越少 o直至达到所要求的
分类数目k李仲来 ot||wl ∀不同的应用所采用的聚类准则也不尽相同 o一般认为点与点之间的空间距离是决
定点群集聚特征的最主要的统计量 o只有聚类靠近的点才可以归为同一子群 o因此空间聚类最常用的准则是
欧式距离准则 ∀但从聚类本身的含义出发 o同一类中的点应尽可能集中 o不同类的点尽可能分离 o也就是类
内的方差尽可能小 o类之间的方差尽可能大 o这就是离差准则k郭仁忠 ousstl ∀为了叙述的方便 o本文采用欧
式最短距离作为聚类的准则 o离差准则的算法设计和欧式距离准则相同 ∀系统聚类的算法可以用下面的步
骤表示 }tl设 Πιkι € s ot o, νl为空间数据对象 o每一个数据对象都构成一类 Γιk¬€ s ot o, νl ~ul计算类两
两之间的距离 ∆ι oϕkι € s ot o, ν ~ϕ€ s ot o, ν ~ι Ξ ϕl o构成上三角或下三角距离矩阵 Μ~vl查找距离矩阵 Μ
中 ∆κoλ € Œ‘k ∆ι oϕl kι € s ot o, ν ~ϕ€ s ot o, ν ~ι Ξ ϕl的 u个类 Γκ !Γλ o合并这 u个类为一新类 Γκoλ ~wl计算新
类 Γκoλ与其他类 Γιkι € s ot o, ν ~ ι Ξ κo ι Ξ λl的距离 o并刷新聚类矩阵 Μ~xl重复步骤 vl o继续合并距离最
近的类 o直到达到所要求的聚类数目 ∀
u 算法实现设计
211 算法分析
系统聚类算法的原理简单易懂 o易用计算机程序实现 o但执行效率低下 ∀设计合理的数据结构来优化算
法成为系统聚类程序实现的关键问题 ∀
分析系统聚类算法的实现步骤可以得到 o有 w个关键点直接影响着程序的执行效率问题 }tl原始数据对
象的存贮 ~ul原始距离矩阵 Μ的计算 ~vl合并新类后距离矩阵 Μ的刷新 ~wl新类的存贮 ∀
u1t1t 原始数据对象的存贮 原始数据对象是空间聚类分析的基础 o原始数据对象的存贮结构直接影响着
后面聚类算法的简洁程度 ∀另外 o有些数据对象不但包含着空间位置的信息 o而且还有非空间的属性信息 o
因此还要使原始数据对象的数据结构有一定的扩展性能 ∀链表结构是程序设计时常用的数据结构形式 o将
原始数据对象的数据结构设计成链表的形式 o可以充分发挥链表的可扩展 !不需要大量连续内存空间的特
点 ∀原始数据链表的节点有代表空间位置信息的 ξ !ψ!ζ数据项 o有代表属性信息的指针变量 o还有指明该
数据对象索引的变量 ∀该数据结构见表 t ∀
表 1 原始数据对象存贮结构
Ταβ .1 Στοραγε στρυχτυρε οφ οριγιναλ δατα οβϕεχτ
索引 Œ±§¨¬ 空间信息k ξ oψoζl ≥³¤·¬¤¯ ¬±©²µ°¤·¬²±k ξ oψoζl 属性信息 „·µ¬¥∏·¨¬±©²µ°¤·¬²±
索引 Œ±§¨¬ 空间信息k ξ oψoζl ≥³¤·¬¤¯ ¬±©²µ°¤·¬²± 属性信息 „·µ¬¥∏·¨¬±©²µ°¤·¬²±
, , ,
u v , ‘
t ∆t ou ∆t ov ∆t oµ ∆t oν
u s ∆u ov ∆u oµ ∆u oν
, s s ∆κoµ ∆κoν
Ν p t s s s ∆ν p t oν
u1t1u 原始距离矩阵 Μ的计算 距离矩阵仅仅用来存储聚
类的统计量 o所以采用最简单的二维矩阵作为其存贮结构 ∀
在分配二维矩阵空间时 o将所有的数据初始化为零 o这样在计
算统计量时 o仅仅考虑矩阵的上三角或下三角的统计量就够
了 ∀该二维矩阵如下 ∀
u1t1v 合并新类后距离矩阵 Μ的刷新 这是算法中的核心步骤 o也是决定算法执行效率 !占用系统资源多
少的关键环节 ∀该算法实现时 o为了节省内存空间 o所有的矩阵统计量刷新在原始距离矩阵 Μ上实现 ∀假
设 u个类 Γκ !Γλ合并成一个新类 Γκoλ o且 λ大于 κo分别比较距离矩阵 Μ中存贮的 ∆κoι与 ∆λoιkι € s ot o, νl的
大小 o用二者中较小的数据刷新距离矩阵 Μ所对应的 λ列和λ行上 o并将新类的 Γκoλ的索引设定为 λo将矩阵
中的 κ行和 κ列数据都刷新为零 ∀充分利用已分配的内存空间来进行数据的频繁变换 o不但在空间上节省
了很多资源 o而且在时间上也避免了频繁分配和回收空间所造成的时间消耗 ∀下面示意了 u个类合并时刷
ytt 林 业 科 学 wu卷
新距离矩阵统计量的过程 ∀
u v w x y
t uux ywt uww t uts u zs{
u s t ws{ yux xvv t {{x
v s s 205 t usu u v|v
w s s s y|z t |ys
x s s s s vvv
¤
u v w x y
t uux 0 uww t uts u zs{
u s 0 yux xvv t {{x
v s s 0 0 0
w s s s y|z t |ys
x s s s s vvv
¥
在矩阵 ¤中 o找到 ∆v ow是最小的统计量k加黑斜体数据l o说明需要将类 v和类 w合并成一个新类 o此时
分别比较 ∆t ov与 ∆t ow !∆u ov与 ∆u ow !∆v ox与 ∆w ox !∆v oy与 ∆w oy的大小 o将最小的距离量刷新到列 w和行 w中k矩阵
¥中加下划线的数据l o然后将列 v和行 v的数据刷新为零k矩阵 ¥中加黑斜体数据l ∀
图 t 新类类节点存贮结构
ƒ¬ªqt ≥·²µ¤ª¨ ¶·µ∏¦·∏µ¨ ²©±¨ º ¦¯¤¶¶±²§¨
u1t1w 新类的存贮 新类的存贮仍采用链表的形式 o与原
始数据对象存贮结构的不同在于新类的链节点采用二维的
存贮方式 o因为每个类链节点不但要含有自身类中所有数
据对象的信息 o而且还要有邻接类的信息 ∀对于类中所包
含的数据对象的信息 o设计了另外的数据节点来存贮 o该数
据节点中仅简单的包含数据对象的索引信息 ∀这样的类数
据结构对聚类结果的遍历输出和后期的微调整都较强的适
应性 ∀其结构示意图可用图 t表示 ∀
212 伪代码算法实现
上文给出了系统聚类算法的详细分析 o并设计了比较
优化的几个关键点的数据结构 o下面给出相关的伪代码并作简要的分析 ∀
tl 原始数据对象的数据结构
¶·µ∏¦··¤ª⁄¤·¤
¾¬±· ¬±§¨¬~ ΠΠ原始数据对象索引
§²∏¥¯¨ ¬o¼o½~ ΠΠ空间位置信息
√²¬§3 ³µ²³~À ΠΠ属性信息
ul原始距离矩阵  的定义及初始化
§²∏¥¯¨3 3 ¤·µ¬¬~ ΠΠ定义浮点型的二维矩阵
¤·µ¬¬€ ±¨ º §²∏¥¯¨3 ≈• ¦¨²µ§≤²∏±·  ~ ΠΠ分配二维矩阵内存空间
©²µk¬±·¬€ s ~¬ • ¦¨²µ§≤²∏±·~¬n n l
¤·µ¬¬≈¬  € ±¨ º §²∏¥¯ ≈¨• ¦¨²µ§≤²∏±·  ~
©²µk¬±·¬€ s ~¬ • ¦¨²µ§≤²∏±·~¬n n l ΠΠ初始化二维矩阵
©²µk¬±·­€ s ~­ • ¦¨²µ§≤²∏±·~­n n l
¤·µ¬¬≈¬ ≈­  € s ~
该段代码的主要运算量在初始化二维矩阵时 o其时间复杂度为 ’k νul ∀
vl新类的存贮结构
¶·µ∏¦··¤ª≥∏¥¯¬¶· ΠΠ数据对象节点
¾¬±· ¬±§¨¬~ ΠΠ数据对象索引
≥∏¥¯¬¶·3 ³±¨ ¬·~À ~ ΠΠ下一节点指针
¶·µ∏¦··¤ª≤¯ ∏¶·¨µ¯¬¶· ΠΠ类节点
¾¬±· ¬±§¨¬~ ΠΠ类索引
¬±· ¦²∏±·~ ΠΠ数据对象数
≥∏¥¯¬¶·3 ¶∏¥¯¬¶·~ ΠΠ数据对象指针
ztt 增刊 t 张 峰等 }系统聚类的一种优化算法实现
≤¯ ∏¶·¨µ¯¬¶·3 ³±¨ ¬·~À ~ ΠΠ下一节点指针
wl距离矩阵  的刷新
变量 ·¨°³≤¯ ∏¶·¨µ¯¬¶·为指向类链表的头结点的指针变量 ∀
º«¬¯¨ k·¨°³≤¯ ∏¶·¨µ¯¬¶·ii·¨°³≤¯ ∏¶·¨µ¯¬¶·p ¬±§¨¬d € ≤²¯l
¾ ¬±·¬€·¨°³≤¯ ∏¶·¨µ¯¬¶·p ¬±§¨¬~
ΠΠ获得 u个要合并的类需要进行比较的距离
¬©k¬ •²ºl
ƒ¬µ¶·∂¤¯∏¨ € ¤·µ¬¬≈¬ ≈•²º  ~
¨¯¶¨
ƒ¬µ¶·∂¤¯∏¨ € ¤·µ¬¬≈•²º ≈¬  ~
¬©k¬ ≤²¯l
≥¨ ¦²±§∂¤¯∏¨ € ¤·µ¬¬≈¬ ≈≤²¯  ~
¨¯¶¨
≥¨ ¦²±§∂¤¯∏¨ € ¤·µ¬¬≈≤²¯ ≈¬  ~
·¨°³∂¤¯∏¨ € °¬±kƒ¬µ¶·∂¤¯∏¨ o≥¨ ¦²±§∂¤¯∏¨ l ~
ΠΠ将二者中较小的数据刷新到新类的行和列中
¬©k¬ ≤²¯l
¤·µ¬¬≈¬ ≈≤²¯  €·¨°³∂¤¯∏¨ ~
¨¯¶¨
¤·µ¬¬≈≤²¯ ≈¬  €·¨°³∂¤¯∏¨ ~
·¨°³≤¯ ∏¶·¨µ¯¬¶·€·¨°³≤¯ ∏¶·¨µ¯¬¶·p  ³±¨ ¬·~
À
ΠΠ将较小的行所有的统计值置为 s
©²µk¬±·®€ s ~® °p • ¦¨²µ§¦²∏±·~®n n l
¾ ¬©k® •²ºl
¤·µ¬¬≈® ≈•²º  € s ~
¨¯¶¨
¤·µ¬¬≈•²º ≈®  € s ~À
这是算法的核心代码部分 o但从代码分析可以看出 o该段代码的时间复杂度也仅仅是 ’k νl o与参加聚类
的数据对象数成正比 ~并且在空间上也仅仅只是利用先前分配的内存空间 ∀
v 与其他软件系统聚类模块的比较
目前许多统计分析软件或具有统计分析软件功能的其他软件都具有聚类功能 o如 ¤·¯¤¥!≥„≥等 o但由
于各个软件所针对的应用领域不尽相同 o所以存在着这样或那样的缺点 o如 ¤·¯¤¥虽然也有系统聚类模块 o
但其在选择聚类准则时 o只能使用固定的欧式距离 o这大大地限制了其应用的灵活性k宋兆基等 oussxl ∀而
≥„≥虽然可以选择多种聚类准则 o但其对数据的输入格式和操作步骤有较严格的要求 o而且运行 ≥„≥所需的
内存资源消耗也较大 ∀而本文所实现的该算法程序 o从最底层的算法设计来优化程序的执行效率 o不但克服
了这些软件的局限性 o而且能够直接对用空间坐标对表达的空间数据k如¶«¤³¨ 格式文件l进行聚类分析 ∀
图 u是利用该算法程序对速生丰产林部分企业的集群特性进行分析研究的结果示意图 o聚类准则采用
欧式距离的最小距离准则 o图中共有 t vss多个数据点 o聚为 y类 o在 °wt1yŠΠuxy  的电脑上仅仅耗时 u ¶左
右 ∀同样的数据 o在用 ¤·¯¤¥或 ≥„≥运算时 o则需要 v ¶以上才能完成 ∀应用实践证明 o该数据结构有效的
提高了系统聚类执行的效率 ∀
w 结论
本文从数据结构 !计算机程序设计的角度对系统聚类算法进行了优化分析 ∀利用了较少的内存空间 o程
{tt 林 业 科 学 wu卷
图 u 聚类效果图
ƒ¬ªqu ∞©©¨¦·§¬¤ªµ¤° ²©¦¯∏¶·¨µ¬±ª
序的时间复杂度与参加聚类数据点的平方成正比 o在文章的最后给出了相应的伪代码实现 o使得这种典型的
聚类算法具有更高的执行效率 o加强了系统聚类算法对大量空间数据的处理能力 ∀
参 考 文 献
戴晓燕 o过仲阳 qussv1 空间聚类的研究现状及其应用 q上海地质 ow }wt p wx
汤国安 qussu1„µ¦∂¬¨º地理信息系统空间分析方法 q北京 }科学出版社 ots }xs
邸凯昌 qusst1 空间数据发掘与知识发现 q武汉 }武汉测绘科技大学出版社 otxz p tyx
郭仁忠 qusst1空间分析 qu版 q北京 }高等教育出版社 o|v p ttu
刘夫涛 o张 雷 qusss1 多重系统聚类挖掘算法及其实现 q计算机工程与应用 ots }wt p wu ~ttv
李仲来 qt||w1系统聚类递推公式的推广 q应用概率统计 otskwl }v{z p v|s
宋兆基 o徐流美 qussx1  „׏„… y1x在科学计算中的应用 q北京 }清华大学出版社 ousx p utt
田纪春 o陈德富 o庞祥梅 qt||w1 系统聚类方法及其计算机程序在农业生产中的应用 q农业系统科学与综合研究 otskul }twu p tww
王美华 qussw1 数据挖掘领域中的聚类方法 q南华大学学报 }理工版 ot{ktl }x{ p yu
‹¤± oŽ¤°¥¨µ qusst1⁄¤·¤ °¬±¬±ª}¦²±¦¨³·¶¤±§·¨¦«±¬´∏¨¶q≥¤± ƒµ¤±¦¬¶¦²}„¦¤§¨ °¬¦°µ¨¶¶
k责任编辑 石红青 于静娴 张君颖l
|tt 增刊 t 张 峰等 }系统聚类的一种优化算法实现