动态合并聚类算法及其在城市科技创新能力评价中的应用

摘要：聚类分析是数据挖掘中研究和应用的一个重要部分，层次聚类是目前应用最为广泛的一种聚类方法。本文针对层次聚类不可逆，需要用户指定所期望得到的聚类个数和阈值作为聚类过程的终止条件等缺陷，提出了一种利用簇间差异度进行簇自动合并的动态聚类算法（DMCA），进而对江苏省13个地市技术创新能力做出了聚类分析及综合评价，验证了方法的可行性和有效性。数据处理结果表明，该方法可为相关管理部门提供科学量化的决策评价模型。

关键词：层次聚类 动态聚类 差异度 江苏省 技术创新

一、引言

科技创新能力是衡量一个国家和地区发展实力的标志，国家“十二五”规划纲要[1]和江苏省“十二五”规划纲要[2]都把增强科技创新能力作为提升科技综合实力的关键。《中国科技发展研究报告》提出，科技创新能力评价指标由以下五个方面构成：技术创新环境、技术创新投入、技术创新能力、创新经济绩效、科技综合能力[3]。本文的评价指标体系便是基于以上五个方面，并借鉴了文献[4]中的指标体系进行展开的[4]。

关于技术创新能力方面的文献比较丰富，但提供科学量化决策评价方法，并对评价方法进行比较的文献却相对较少。聚类分析是研究多要素事物分类问题的数量方法，可以解释对象之间、特征之间以及对象和特征之间错综复杂的关系，能为量化综合评价提供科学的参考模型。

聚类分析方法中，层次聚类方法是应用最广的聚类技术。尽管层次聚类适用面广，但选择适当的合并或分裂点十分困难，如果在某一步没有很好地选择合并或分裂的决定，可能会直接导致聚类质量受到限制。另外，层次聚类过程中用户必须决定聚类在什么时候停止，以得到某个数量的分类，否则算法的输出结果总是一个聚类[5]。针对层次聚类的缺陷，本文以簇间差异度作为簇自动合并与分裂的准则提出了一种动态合并聚类算法，该算法不需要用户预先设定聚类阀值动态的进行簇的划分，自动决定簇的合并及分裂过程，最终找到一个最佳的聚类。进而以江苏省13个地市的科技创新能力指标值为实验数据，对江苏省科技创新能力进行了聚类分析及综合评价。

二、相关原理与定义

（一）层次聚类原理

层次聚类方法[6]是通过将数据组织为若干组并形成一个相应的树来进行聚类的，根据聚类树图形成的方式，层次聚类方法可分为自顶向下的分裂算法和自底向上的合并算法两种。合并的层次聚类方法由于具体实施过程更为简单实用，所以大多数层次聚类方法都是合并式的[7]，该方法的基本思想是：采用自底向上的策略，首先将每个对象作为一个簇，然后按距离准则逐步合并这些原子簇，减少聚类数，直到所有的对象都在一个簇中，或者某个终结条件被满足为止。

（二）相关定义

定义1 欧式距离：设p维空间内的点X=（x1，x2，...，xp）'及Y=（y1，y2，...，yp）'，定义两点之间的欧式距离为：

■（1）

欧式距离是聚类分析中常见的一种相似性度量方法，它可以用来表示样本点之间的相近程度，距离较近的样本点性质较相似，距离较远的样本点差异较大。

定义2 类间最短距离：聚类过程中，涉及到类和类之间的合并，因此要考虑到类间距离的度量。广泛采用的类间距离度量方法有以下四种：最小距离法、最大距离法、类平均距离法、重心法。本文采用最小距离法，即类间最短距离作为类间合并准则。设A、B是两个聚类，则两类间的最短距离定义为：

Dmin（A，B）=min{d（xA ，xB）}xA∈A，xB∈B（2）

其中d（xA ，xB）表示A类中的样本xA和B类中的样本xB之间的欧氏距离；dmin（A，B）表示A类中的所有样本与B类中的所有样本之间的最小距离。如果一个类C，由A和B两类合并而成，即C=A∪B，则C与另外一个类D之间的最短距离为：

Dmin（C，D）=min{dAD，dBD} （3）

定义3 类内平均距离：设类C包含个聚类{C1，C2，...，Cc}，每个聚类Ci中含有ni个样本，i=1，2，...c，则类X的类内平均距离定义为：

■ （4）

三、动态合并聚类算法（DMCA）

（一）算法思想

层次聚类通过对样本和变量数据的不同特征指标值进行差异程度计算，根据变量或样本间差异程度的大小重新结合分类，产生一个更有效的类。但层次聚类方法是不可逆的，两个簇合并后，无法通过再将其分离到之前的状态，而且需要用户指定所期望得到的聚类个数和阈值作为聚类过程的终止条件，这是很难事先判定的[8]。

基于合并式层次聚类，本文提出了一种动态合并聚类算法（Dynamic-Merge Cluster Algorithm）DMCA。该算法的核心思想是：两个子簇是否合并依据簇间的相对接近度和相对互联度来评定，本文把这种簇间的相对接近度定义为簇间差异度，将两个簇之间的最短距离与它们各自的类内平均距离进行比较，从而决定是否合并两个类。通过采用簇间差异度作为簇自动合并与分裂的准则，可以克服层次聚类不可逆，且需预先设定阀值的缺陷。由于引入一种新的度量依据，而不是仅仅利用原来的类间最短距离准则进行簇合并，因此可以实现不需预知簇个数的聚类和在未知簇划分信息的情况下对数据集自动进行聚类分析。

（二）合并准则

设两个聚类Ci和Cj，依据公式（1）和（2），它们的类间最短距离为Dmin（Ci，Cj）；依据公式（4），它们的类内平均距离为R（Ci）和R（Cj），则Ci和Cj之间的簇间差异度σij的定义如公式（5）。

σij=min{（Dmin（Ci，Cj）-R（Ci）），（Dmin（Ci，Cj）-R（Cj））} （5）

合并准则：如果σij≤0，说明两个簇离得很近并且互联度较高，那么将类Ci和Cj合并成为一类Cij；如果σij>0，表明两个簇之间的最短距离要大于它们各自的类内平均距离，则把类Ci和Cj分别作为两个不同的类进行划分。

（三）算法描述

算法：动态合并聚类算法（DMCA）

输入：输入包含N个对象的数据集

输出：输出经过自动合并后的聚类结果

步骤1：N个初始数据样本自成一类，按照公式（1）计算各类之间（各样本间）的距离，得到初始化的距离矩阵；

步骤2：对距离矩阵中N（N-1）/2个元素按照距离从小到大的顺序进行快速排序，并将其存储在一维数组D中；

步骤3：对D中的当前元素Dij，首先判断类Ci和Cj是否已经被合并到类中，如果没有，计算类Ci和Cj之间的簇间差异度σij；

步骤4：判断σij，如果σij≤0，将类Ci和Cj合并成为一类Cij，并从簇序列中用Cij替换掉Ci、Cj，否则转向步骤5；

步骤5：取数组D中的下一个元素，重复2—4，直到簇序列中没有能合并的簇为止；

步骤6：输出合并后的聚类结果。

四、DMCA在江苏省城市科技创新能力评价的应用

江苏省共辖13个地级市，按经济发展水平可分成三类不同地区，即苏南、苏中和苏北。苏南为江苏省发达地区，苏中为次发达的过渡地区，苏北为欠发达的地区。

本文根据2011年江苏省统计年鉴[9]和参考文献[4]，选取了江苏省13个地级市的5项科技创新能力指标数据，如表1所示。其中包括：技术创新环境、技术创新投入、技术创新能力、创新经济绩效、科技综合能力。

采用DMCA算法对其进行聚类分析，聚类分析结果如表2所示。从表2中可以看出，本文算法可以在预先不设定阀值的条件下，自动将聚类结果合并成三类，符合江苏省的实际发展情况，而K-means算法和层次聚类算法在聚类个数为4的条件下，虽然聚类结果相同，但与江苏省实际情况不符。在聚类个数为3的条件下，采用三种聚类算法得到的第三类的聚类结果相同，第一、二类有所不同，K-means算法把苏州单独归为一类，出现了孤立点，影响了聚类结果；层次聚类算法和本文算法聚类结果的区别在于把常州归为第一类还是第二类，根据分析比较，常州与苏州、无锡、南京归为一类比较好。从以上分析，可以清晰的看出动态合并聚类算法的优势所在，使用本算法不仅能提高聚类质量，而且聚类结果更加符合实际，更具参考价值。

根据聚类结果比较，科技创新能力排在江苏省前四位的城市分别为苏州市、无锡市、南京市、常州市。这些地市一般都具有以下特点：相对于科技创新能力较弱的地区，这些地市都具有相对较好的科技基础，吸引外资相对较多，尤其是苏州，已成为中国吸引外资最多的城市，带动了高新技术产业的发展，也提高了科技创新的综合竞争实力。苏中的南通、扬州、镇江、泰州四地市综合排名大体处于中等水平；苏北的淮安、宿迁、盐城、连云港、徐州五地市的综合排名则为最后五名。可以看出，江苏省各地级市科技创新能力分布不平衡，苏南地区的科技创新能力优势明显，苏中地区的科技创新能力有待提高，苏北地区科技创新能力偏弱，需要大力加强科技创新投入和出台相应的政策措施来推动科技创新能力的发展。

五、结束语

本文基于合并式层次聚类的思想，阐述了一种采用簇间差异度进行簇自动合并划分的动态合并聚类算法，克服了层次划分方法不可逆、需要预先设定聚类阀值等缺陷。通过实践，将其运用到江苏省技术创新能力评价实例中，为江苏省13个地市的科技创新能力提供了科学量化决策评价，验证了算法的可行性与有效性。与其他聚类方法相比，本算法聚类结果更加符合客观实际，从而对各地区科技创新能力分析提供了参考。■

参考文献：

[1]中国网.中华人民共和国国民经济和社会发展第十二个五年规划纲要（全文）[EB/OL].http：//www.china.com.cn/policy/txt/

2011—03/16/content_22156007.htm

[2]江苏省发展规划中心.江苏省“十二五”规划纲要（全文）[EB/OL].http：//jsdp.njnu.edu.cn/Article/news_vi-

ew. asp？newsid=928，2011.7.6

[3]《中国科技发展研究报告》研究组. 中国科技发展研究报（2000）—科技全球化及中国面临的挑战[M].北京：社会科学文献出版社，2000.

[4]王芳. 江苏省科技创新能力的评价及对策[J].科技经济市场，2009（7）：63—64

[5]Xu R，Wunsch D.Clustering[M]. New York：IEEE Pr-

ess，2009：20—40

[6]Sambasivam，Theodosopoulos.Advanced data clus-

tering methods of mining web documents. Issues in Informing Science and Information Technology， 2006，8（3）： 563—579

[7]Ian Davidson， S. S. Ravi，Using instance—level

constraints in agglomerative hierarchical clustering：theoretical and empirical results， Data Mining and Knowledge Discovery，2009，18（2）：257—282

[8]段明秀.层次聚类算法的研究与应用[J].中南大学硕士学位论文，2009

[9]江苏省统计局编：江苏统计年鉴2011[M].北京：中国统计出版社

（董智，1970年生，江苏徐州人，江苏师范大学外国语学院国际交流系讲师。研究方向：市场营销、物流管理、国际商务文化）

（三）算法描述

算法：动态合并聚类算法（DMCA）

输入：输入包含N个对象的数据集

输出：输出经过自动合并后的聚类结果

步骤1：N个初始数据样本自成一类，按照公式（1）计算各类之间（各样本间）的距离，得到初始化的距离矩阵；

步骤2：对距离矩阵中N（N-1）/2个元素按照距离从小到大的顺序进行快速排序，并将其存储在一维数组D中；

步骤3：对D中的当前元素Dij，首先判断类Ci和Cj是否已经被合并到类中，如果没有，计算类Ci和Cj之间的簇间差异度σij；

步骤4：判断σij，如果σij≤0，将类Ci和Cj合并成为一类Cij，并从簇序列中用Cij替换掉Ci、Cj，否则转向步骤5；

步骤5：取数组D中的下一个元素，重复2—4，直到簇序列中没有能合并的簇为止；

步骤6：输出合并后的聚类结果。

四、DMCA在江苏省城市科技创新能力评价的应用

江苏省共辖13个地级市，按经济发展水平可分成三类不同地区，即苏南、苏中和苏北。苏南为江苏省发达地区，苏中为次发达的过渡地区，苏北为欠发达的地区。

本文根据2011年江苏省统计年鉴[9]和参考文献[4]，选取了江苏省13个地级市的5项科技创新能力指标数据，如表1所示。其中包括：技术创新环境、技术创新投入、技术创新能力、创新经济绩效、科技综合能力。

采用DMCA算法对其进行聚类分析，聚类分析结果如表2所示。从表2中可以看出，本文算法可以在预先不设定阀值的条件下，自动将聚类结果合并成三类，符合江苏省的实际发展情况，而K-means算法和层次聚类算法在聚类个数为4的条件下，虽然聚类结果相同，但与江苏省实际情况不符。在聚类个数为3的条件下，采用三种聚类算法得到的第三类的聚类结果相同，第一、二类有所不同，K-means算法把苏州单独归为一类，出现了孤立点，影响了聚类结果；层次聚类算法和本文算法聚类结果的区别在于把常州归为第一类还是第二类，根据分析比较，常州与苏州、无锡、南京归为一类比较好。从以上分析，可以清晰的看出动态合并聚类算法的优势所在，使用本算法不仅能提高聚类质量，而且聚类结果更加符合实际，更具参考价值。

根据聚类结果比较，科技创新能力排在江苏省前四位的城市分别为苏州市、无锡市、南京市、常州市。这些地市一般都具有以下特点：相对于科技创新能力较弱的地区，这些地市都具有相对较好的科技基础，吸引外资相对较多，尤其是苏州，已成为中国吸引外资最多的城市，带动了高新技术产业的发展，也提高了科技创新的综合竞争实力。苏中的南通、扬州、镇江、泰州四地市综合排名大体处于中等水平；苏北的淮安、宿迁、盐城、连云港、徐州五地市的综合排名则为最后五名。可以看出，江苏省各地级市科技创新能力分布不平衡，苏南地区的科技创新能力优势明显，苏中地区的科技创新能力有待提高，苏北地区科技创新能力偏弱，需要大力加强科技创新投入和出台相应的政策措施来推动科技创新能力的发展。

五、结束语

本文基于合并式层次聚类的思想，阐述了一种采用簇间差异度进行簇自动合并划分的动态合并聚类算法，克服了层次划分方法不可逆、需要预先设定聚类阀值等缺陷。通过实践，将其运用到江苏省技术创新能力评价实例中，为江苏省13个地市的科技创新能力提供了科学量化决策评价，验证了算法的可行性与有效性。与其他聚类方法相比，本算法聚类结果更加符合客观实际，从而对各地区科技创新能力分析提供了参考。■

参考文献：

[1]中国网.中华人民共和国国民经济和社会发展第十二个五年规划纲要（全文）[EB/OL].http：//www.china.com.cn/policy/txt/

2011—03/16/content_22156007.htm

[2]江苏省发展规划中心.江苏省“十二五”规划纲要（全文）[EB/OL].http：//jsdp.njnu.edu.cn/Article/news_vi-

ew. asp？newsid=928，2011.7.6

[3]《中国科技发展研究报告》研究组. 中国科技发展研究报（2000）—科技全球化及中国面临的挑战[M].北京：社会科学文献出版社，2000.

[4]王芳. 江苏省科技创新能力的评价及对策[J].科技经济市场，2009（7）：63—64

[5]Xu R，Wunsch D.Clustering[M]. New York：IEEE Pr-

ess，2009：20—40

[6]Sambasivam，Theodosopoulos.Advanced data clus-

tering methods of mining web documents. Issues in Informing Science and Information Technology， 2006，8（3）： 563—579

[7]Ian Davidson， S. S. Ravi，Using instance—level

constraints in agglomerative hierarchical clustering：theoretical and empirical results， Data Mining and Knowledge Discovery，2009，18（2）：257—282

[8]段明秀.层次聚类算法的研究与应用[J].中南大学硕士学位论文，2009

[9]江苏省统计局编：江苏统计年鉴2011[M].北京：中国统计出版社

（董智，1970年生，江苏徐州人，江苏师范大学外国语学院国际交流系讲师。研究方向：市场营销、物流管理、国际商务文化）

（三）算法描述

算法：动态合并聚类算法（DMCA）

输入：输入包含N个对象的数据集

输出：输出经过自动合并后的聚类结果

步骤1：N个初始数据样本自成一类，按照公式（1）计算各类之间（各样本间）的距离，得到初始化的距离矩阵；

步骤2：对距离矩阵中N（N-1）/2个元素按照距离从小到大的顺序进行快速排序，并将其存储在一维数组D中；

步骤3：对D中的当前元素Dij，首先判断类Ci和Cj是否已经被合并到类中，如果没有，计算类Ci和Cj之间的簇间差异度σij；

步骤4：判断σij，如果σij≤0，将类Ci和Cj合并成为一类Cij，并从簇序列中用Cij替换掉Ci、Cj，否则转向步骤5；

步骤5：取数组D中的下一个元素，重复2—4，直到簇序列中没有能合并的簇为止；

步骤6：输出合并后的聚类结果。

四、DMCA在江苏省城市科技创新能力评价的应用

江苏省共辖13个地级市，按经济发展水平可分成三类不同地区，即苏南、苏中和苏北。苏南为江苏省发达地区，苏中为次发达的过渡地区，苏北为欠发达的地区。

本文根据2011年江苏省统计年鉴[9]和参考文献[4]，选取了江苏省13个地级市的5项科技创新能力指标数据，如表1所示。其中包括：技术创新环境、技术创新投入、技术创新能力、创新经济绩效、科技综合能力。

采用DMCA算法对其进行聚类分析，聚类分析结果如表2所示。从表2中可以看出，本文算法可以在预先不设定阀值的条件下，自动将聚类结果合并成三类，符合江苏省的实际发展情况，而K-means算法和层次聚类算法在聚类个数为4的条件下，虽然聚类结果相同，但与江苏省实际情况不符。在聚类个数为3的条件下，采用三种聚类算法得到的第三类的聚类结果相同，第一、二类有所不同，K-means算法把苏州单独归为一类，出现了孤立点，影响了聚类结果；层次聚类算法和本文算法聚类结果的区别在于把常州归为第一类还是第二类，根据分析比较，常州与苏州、无锡、南京归为一类比较好。从以上分析，可以清晰的看出动态合并聚类算法的优势所在，使用本算法不仅能提高聚类质量，而且聚类结果更加符合实际，更具参考价值。

根据聚类结果比较，科技创新能力排在江苏省前四位的城市分别为苏州市、无锡市、南京市、常州市。这些地市一般都具有以下特点：相对于科技创新能力较弱的地区，这些地市都具有相对较好的科技基础，吸引外资相对较多，尤其是苏州，已成为中国吸引外资最多的城市，带动了高新技术产业的发展，也提高了科技创新的综合竞争实力。苏中的南通、扬州、镇江、泰州四地市综合排名大体处于中等水平；苏北的淮安、宿迁、盐城、连云港、徐州五地市的综合排名则为最后五名。可以看出，江苏省各地级市科技创新能力分布不平衡，苏南地区的科技创新能力优势明显，苏中地区的科技创新能力有待提高，苏北地区科技创新能力偏弱，需要大力加强科技创新投入和出台相应的政策措施来推动科技创新能力的发展。

五、结束语

本文基于合并式层次聚类的思想，阐述了一种采用簇间差异度进行簇自动合并划分的动态合并聚类算法，克服了层次划分方法不可逆、需要预先设定聚类阀值等缺陷。通过实践，将其运用到江苏省技术创新能力评价实例中，为江苏省13个地市的科技创新能力提供了科学量化决策评价，验证了算法的可行性与有效性。与其他聚类方法相比，本算法聚类结果更加符合客观实际，从而对各地区科技创新能力分析提供了参考。■

参考文献：

[1]中国网.中华人民共和国国民经济和社会发展第十二个五年规划纲要（全文）[EB/OL].http：//www.china.com.cn/policy/txt/

2011—03/16/content_22156007.htm

[2]江苏省发展规划中心.江苏省“十二五”规划纲要（全文）[EB/OL].http：//jsdp.njnu.edu.cn/Article/news_vi-

ew. asp？newsid=928，2011.7.6

[3]《中国科技发展研究报告》研究组. 中国科技发展研究报（2000）—科技全球化及中国面临的挑战[M].北京：社会科学文献出版社，2000.

[4]王芳. 江苏省科技创新能力的评价及对策[J].科技经济市场，2009（7）：63—64

[5]Xu R，Wunsch D.Clustering[M]. New York：IEEE Pr-

ess，2009：20—40

[6]Sambasivam，Theodosopoulos.Advanced data clus-

tering methods of mining web documents. Issues in Informing Science and Information Technology， 2006，8（3）： 563—579

[7]Ian Davidson， S. S. Ravi，Using instance—level

constraints in agglomerative hierarchical clustering：theoretical and empirical results， Data Mining and Knowledge Discovery，2009，18（2）：257—282

[8]段明秀.层次聚类算法的研究与应用[J].中南大学硕士学位论文，2009

[9]江苏省统计局编：江苏统计年鉴2011[M].北京：中国统计出版社

（董智，1970年生，江苏徐州人，江苏师范大学外国语学院国际交流系讲师。研究方向：市场营销、物流管理、国际商务文化）