摘要：聚類分析是數(shù)據(jù)挖掘中研究和應(yīng)用的一個(gè)重要部分，層次聚類是目前應(yīng)用最為廣泛的一種聚類方法。本文針對(duì)層次聚類不可逆，需要用戶指定所期望得到的聚類個(gè)數(shù)和閾值作為聚類過(guò)程的終止條件等缺陷，提出了一種利用簇間差異度進(jìn)行簇自動(dòng)合并的動(dòng)態(tài)聚類算法（DMCA），進(jìn)而對(duì)江蘇省13個(gè)地市技術(shù)創(chuàng)新能力做出了聚類分析及綜合評(píng)價(jià)，驗(yàn)證了方法的可行性和有效性。數(shù)據(jù)處理結(jié)果表明，該方法可為相關(guān)管理部門(mén)提供科學(xué)量化的決策評(píng)價(jià)模型。

關(guān)鍵詞：層次聚類 動(dòng)態(tài)聚類 差異度 江蘇省 技術(shù)創(chuàng)新

一、引言

科技創(chuàng)新能力是衡量一個(gè)國(guó)家和地區(qū)發(fā)展實(shí)力的標(biāo)志，國(guó)家“十二五”規(guī)劃綱要[1]和江蘇省“十二五”規(guī)劃綱要[2]都把增強(qiáng)科技創(chuàng)新能力作為提升科技綜合實(shí)力的關(guān)鍵?！吨袊?guó)科技發(fā)展研究報(bào)告》提出，科技創(chuàng)新能力評(píng)價(jià)指標(biāo)由以下五個(gè)方面構(gòu)成：技術(shù)創(chuàng)新環(huán)境、技術(shù)創(chuàng)新投入、技術(shù)創(chuàng)新能力、創(chuàng)新經(jīng)濟(jì)績(jī)效、科技綜合能力[3]。本文的評(píng)價(jià)指標(biāo)體系便是基于以上五個(gè)方面，并借鑒了文獻(xiàn)[4]中的指標(biāo)體系進(jìn)行展開(kāi)的[4]。

關(guān)于技術(shù)創(chuàng)新能力方面的文獻(xiàn)比較豐富，但提供科學(xué)量化決策評(píng)價(jià)方法，并對(duì)評(píng)價(jià)方法進(jìn)行比較的文獻(xiàn)卻相對(duì)較少。聚類分析是研究多要素事物分類問(wèn)題的數(shù)量方法，可以解釋對(duì)象之間、特征之間以及對(duì)象和特征之間錯(cuò)綜復(fù)雜的關(guān)系，能為量化綜合評(píng)價(jià)提供科學(xué)的參考模型。

聚類分析方法中，層次聚類方法是應(yīng)用最廣的聚類技術(shù)。盡管層次聚類適用面廣，但選擇適當(dāng)?shù)暮喜⒒蚍至腰c(diǎn)十分困難，如果在某一步?jīng)]有很好地選擇合并或分裂的決定，可能會(huì)直接導(dǎo)致聚類質(zhì)量受到限制。另外，層次聚類過(guò)程中用戶必須決定聚類在什么時(shí)候停止，以得到某個(gè)數(shù)量的分類，否則算法的輸出結(jié)果總是一個(gè)聚類[5]。針對(duì)層次聚類的缺陷，本文以簇間差異度作為簇自動(dòng)合并與分裂的準(zhǔn)則提出了一種動(dòng)態(tài)合并聚類算法，該算法不需要用戶預(yù)先設(shè)定聚類閥值動(dòng)態(tài)的進(jìn)行簇的劃分，自動(dòng)決定簇的合并及分裂過(guò)程，最終找到一個(gè)最佳的聚類。進(jìn)而以江蘇省13個(gè)地市的科技創(chuàng)新能力指標(biāo)值為實(shí)驗(yàn)數(shù)據(jù)，對(duì)江蘇省科技創(chuàng)新能力進(jìn)行了聚類分析及綜合評(píng)價(jià)。

二、相關(guān)原理與定義

（一）層次聚類原理

層次聚類方法[6]是通過(guò)將數(shù)據(jù)組織為若干組并形成一個(gè)相應(yīng)的樹(shù)來(lái)進(jìn)行聚類的，根據(jù)聚類樹(shù)圖形成的方式，層次聚類方法可分為自頂向下的分裂算法和自底向上的合并算法兩種。合并的層次聚類方法由于具體實(shí)施過(guò)程更為簡(jiǎn)單實(shí)用，所以大多數(shù)層次聚類方法都是合并式的[7]，該方法的基本思想是：采用自底向上的策略，首先將每個(gè)對(duì)象作為一個(gè)簇，然后按距離準(zhǔn)則逐步合并這些原子簇，減少聚類數(shù)，直到所有的對(duì)象都在一個(gè)簇中，或者某個(gè)終結(jié)條件被滿足為止。

（二）相關(guān)定義

定義1 歐式距離：設(shè)p維空間內(nèi)的點(diǎn)X=（x1，x2，...，xp）'及Y=（y1，y2，...，yp）'，定義兩點(diǎn)之間的歐式距離為：

■（1）

歐式距離是聚類分析中常見(jiàn)的一種相似性度量方法，它可以用來(lái)表示樣本點(diǎn)之間的相近程度，距離較近的樣本點(diǎn)性質(zhì)較相似，距離較遠(yuǎn)的樣本點(diǎn)差異較大。

定義2 類間最短距離：聚類過(guò)程中，涉及到類和類之間的合并，因此要考慮到類間距離的度量。廣泛采用的類間距離度量方法有以下四種：最小距離法、最大距離法、類平均距離法、重心法。本文采用最小距離法，即類間最短距離作為類間合并準(zhǔn)則。設(shè)A、B是兩個(gè)聚類，則兩類間的最短距離定義為：

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

其中d（xA ，xB）表示A類中的樣本xA和B類中的樣本xB之間的歐氏距離；dmin（A，B）表示A類中的所有樣本與B類中的所有樣本之間的最小距離。如果一個(gè)類C，由A和B兩類合并而成，即C=A∪B，則C與另外一個(gè)類D之間的最短距離為：

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

定義3 類內(nèi)平均距離：設(shè)類C包含個(gè)聚類{C1，C2，...，Cc}，每個(gè)聚類Ci中含有ni個(gè)樣本，i=1，2，...c，則類X的類內(nèi)平均距離定義為：

■ （4）

三、動(dòng)態(tài)合并聚類算法（DMCA）

（一）算法思想

層次聚類通過(guò)對(duì)樣本和變量數(shù)據(jù)的不同特征指標(biāo)值進(jìn)行差異程度計(jì)算，根據(jù)變量或樣本間差異程度的大小重新結(jié)合分類，產(chǎn)生一個(gè)更有效的類。但層次聚類方法是不可逆的，兩個(gè)簇合并后，無(wú)法通過(guò)再將其分離到之前的狀態(tài)，而且需要用戶指定所期望得到的聚類個(gè)數(shù)和閾值作為聚類過(guò)程的終止條件，這是很難事先判定的[8]。

基于合并式層次聚類，本文提出了一種動(dòng)態(tài)合并聚類算法（Dynamic-Merge Cluster Algorithm）DMCA。該算法的核心思想是：兩個(gè)子簇是否合并依據(jù)簇間的相對(duì)接近度和相對(duì)互聯(lián)度來(lái)評(píng)定，本文把這種簇間的相對(duì)接近度定義為簇間差異度，將兩個(gè)簇之間的最短距離與它們各自的類內(nèi)平均距離進(jìn)行比較，從而決定是否合并兩個(gè)類。通過(guò)采用簇間差異度作為簇自動(dòng)合并與分裂的準(zhǔn)則，可以克服層次聚類不可逆，且需預(yù)先設(shè)定閥值的缺陷。由于引入一種新的度量依據(jù)，而不是僅僅利用原來(lái)的類間最短距離準(zhǔn)則進(jìn)行簇合并，因此可以實(shí)現(xiàn)不需預(yù)知簇個(gè)數(shù)的聚類和在未知簇劃分信息的情況下對(duì)數(shù)據(jù)集自動(dòng)進(jìn)行聚類分析。

（二）合并準(zhǔn)則

設(shè)兩個(gè)聚類Ci和Cj，依據(jù)公式（1）和（2），它們的類間最短距離為Dmin（Ci，Cj）；依據(jù)公式（4），它們的類內(nèi)平均距離為R（Ci）和R（Cj），則Ci和Cj之間的簇間差異度σij的定義如公式（5）。

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

合并準(zhǔn)則：如果σij≤0，說(shuō)明兩個(gè)簇離得很近并且互聯(lián)度較高，那么將類Ci和Cj合并成為一類Cij；如果σij>0，表明兩個(gè)簇之間的最短距離要大于它們各自的類內(nèi)平均距離，則把類Ci和Cj分別作為兩個(gè)不同的類進(jìn)行劃分。

（三）算法描述

算法：動(dòng)態(tài)合并聚類算法（DMCA）

輸入：輸入包含N個(gè)對(duì)象的數(shù)據(jù)集

輸出：輸出經(jīng)過(guò)自動(dòng)合并后的聚類結(jié)果

步驟1：N個(gè)初始數(shù)據(jù)樣本自成一類，按照公式（1）計(jì)算各類之間（各樣本間）的距離，得到初始化的距離矩陣；

步驟2：對(duì)距離矩陣中N（N-1）/2個(gè)元素按照距離從小到大的順序進(jìn)行快速排序，并將其存儲(chǔ)在一維數(shù)組D中；

步驟3：對(duì)D中的當(dāng)前元素Dij，首先判斷類Ci和Cj是否已經(jīng)被合并到類中，如果沒(méi)有，計(jì)算類Ci和Cj之間的簇間差異度σij；

步驟4：判斷σij，如果σij≤0，將類Ci和Cj合并成為一類Cij，并從簇序列中用Cij替換掉Ci、Cj，否則轉(zhuǎn)向步驟5；

步驟5：取數(shù)組D中的下一個(gè)元素，重復(fù)2—4，直到簇序列中沒(méi)有能合并的簇為止；

步驟6：輸出合并后的聚類結(jié)果。

四、DMCA在江蘇省城市科技創(chuàng)新能力評(píng)價(jià)的應(yīng)用

江蘇省共轄13個(gè)地級(jí)市，按經(jīng)濟(jì)發(fā)展水平可分成三類不同地區(qū)，即蘇南、蘇中和蘇北。蘇南為江蘇省發(fā)達(dá)地區(qū)，蘇中為次發(fā)達(dá)的過(guò)渡地區(qū)，蘇北為欠發(fā)達(dá)的地區(qū)。

本文根據(jù)2011年江蘇省統(tǒng)計(jì)年鑒[9]和參考文獻(xiàn)[4]，選取了江蘇省13個(gè)地級(jí)市的5項(xiàng)科技創(chuàng)新能力指標(biāo)數(shù)據(jù)，如表1所示。其中包括：技術(shù)創(chuàng)新環(huán)境、技術(shù)創(chuàng)新投入、技術(shù)創(chuàng)新能力、創(chuàng)新經(jīng)濟(jì)績(jī)效、科技綜合能力。

采用DMCA算法對(duì)其進(jìn)行聚類分析，聚類分析結(jié)果如表2所示。從表2中可以看出，本文算法可以在預(yù)先不設(shè)定閥值的條件下，自動(dòng)將聚類結(jié)果合并成三類，符合江蘇省的實(shí)際發(fā)展情況，而K-means算法和層次聚類算法在聚類個(gè)數(shù)為4的條件下，雖然聚類結(jié)果相同，但與江蘇省實(shí)際情況不符。在聚類個(gè)數(shù)為3的條件下，采用三種聚類算法得到的第三類的聚類結(jié)果相同，第一、二類有所不同，K-means算法把蘇州單獨(dú)歸為一類，出現(xiàn)了孤立點(diǎn)，影響了聚類結(jié)果；層次聚類算法和本文算法聚類結(jié)果的區(qū)別在于把常州歸為第一類還是第二類，根據(jù)分析比較，常州與蘇州、無(wú)錫、南京歸為一類比較好。從以上分析，可以清晰的看出動(dòng)態(tài)合并聚類算法的優(yōu)勢(shì)所在，使用本算法不僅能提高聚類質(zhì)量，而且聚類結(jié)果更加符合實(shí)際，更具參考價(jià)值。

根據(jù)聚類結(jié)果比較，科技創(chuàng)新能力排在江蘇省前四位的城市分別為蘇州市、無(wú)錫市、南京市、常州市。這些地市一般都具有以下特點(diǎn)：相對(duì)于科技創(chuàng)新能力較弱的地區(qū)，這些地市都具有相對(duì)較好的科技基礎(chǔ)，吸引外資相對(duì)較多，尤其是蘇州，已成為中國(guó)吸引外資最多的城市，帶動(dòng)了高新技術(shù)產(chǎn)業(yè)的發(fā)展，也提高了科技創(chuàng)新的綜合競(jìng)爭(zhēng)實(shí)力。蘇中的南通、揚(yáng)州、鎮(zhèn)江、泰州四地市綜合排名大體處于中等水平；蘇北的淮安、宿遷、鹽城、連云港、徐州五地市的綜合排名則為最后五名。可以看出，江蘇省各地級(jí)市科技創(chuàng)新能力分布不平衡，蘇南地區(qū)的科技創(chuàng)新能力優(yōu)勢(shì)明顯，蘇中地區(qū)的科技創(chuàng)新能力有待提高，蘇北地區(qū)科技創(chuàng)新能力偏弱，需要大力加強(qiáng)科技創(chuàng)新投入和出臺(tái)相應(yīng)的政策措施來(lái)推動(dòng)科技創(chuàng)新能力的發(fā)展。

五、結(jié)束語(yǔ)

本文基于合并式層次聚類的思想，闡述了一種采用簇間差異度進(jìn)行簇自動(dòng)合并劃分的動(dòng)態(tài)合并聚類算法，克服了層次劃分方法不可逆、需要預(yù)先設(shè)定聚類閥值等缺陷。通過(guò)實(shí)踐，將其運(yùn)用到江蘇省技術(shù)創(chuàng)新能力評(píng)價(jià)實(shí)例中，為江蘇省13個(gè)地市的科技創(chuàng)新能力提供了科學(xué)量化決策評(píng)價(jià)，驗(yàn)證了算法的可行性與有效性。與其他聚類方法相比，本算法聚類結(jié)果更加符合客觀實(shí)際，從而對(duì)各地區(qū)科技創(chuàng)新能力分析提供了參考?！?/p>

參考文獻(xiàn)：

[1]中國(guó)網(wǎng).中華人民共和國(guó)國(guó)民經(jīng)濟(jì)和社會(huì)發(fā)展第十二個(gè)五年規(guī)劃綱要（全文）[EB/OL].http：//www.china.com.cn/policy/txt/

2011—03/16/content_22156007.htm

[2]江蘇省發(fā)展規(guī)劃中心.江蘇省“十二五”規(guī)劃綱要（全文）[EB/OL].http：//jsdp.njnu.edu.cn/Article/news_vi-

ew. asp？newsid=928，2011.7.6

[3]《中國(guó)科技發(fā)展研究報(bào)告》研究組. 中國(guó)科技發(fā)展研究報(bào)（2000）—科技全球化及中國(guó)面臨的挑戰(zhàn)[M].北京：社會(huì)科學(xué)文獻(xiàn)出版社，2000.

[4]王芳. 江蘇省科技創(chuàng)新能力的評(píng)價(jià)及對(duì)策[J].科技經(jīng)濟(jì)市場(chǎng)，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]段明秀.層次聚類算法的研究與應(yīng)用[J].中南大學(xué)碩士學(xué)位論文，2009

[9]江蘇省統(tǒng)計(jì)局編：江蘇統(tǒng)計(jì)年鑒2011[M].北京：中國(guó)統(tǒng)計(jì)出版社

（董智，1970年生，江蘇徐州人，江蘇師范大學(xué)外國(guó)語(yǔ)學(xué)院國(guó)際交流系講師。研究方向：市場(chǎng)營(yíng)銷(xiāo)、物流管理、國(guó)際商務(wù)文化）

（三）算法描述

算法：動(dòng)態(tài)合并聚類算法（DMCA）

輸入：輸入包含N個(gè)對(duì)象的數(shù)據(jù)集

輸出：輸出經(jīng)過(guò)自動(dòng)合并后的聚類結(jié)果

步驟1：N個(gè)初始數(shù)據(jù)樣本自成一類，按照公式（1）計(jì)算各類之間（各樣本間）的距離，得到初始化的距離矩陣；

步驟2：對(duì)距離矩陣中N（N-1）/2個(gè)元素按照距離從小到大的順序進(jìn)行快速排序，并將其存儲(chǔ)在一維數(shù)組D中；

步驟3：對(duì)D中的當(dāng)前元素Dij，首先判斷類Ci和Cj是否已經(jīng)被合并到類中，如果沒(méi)有，計(jì)算類Ci和Cj之間的簇間差異度σij；

步驟4：判斷σij，如果σij≤0，將類Ci和Cj合并成為一類Cij，并從簇序列中用Cij替換掉Ci、Cj，否則轉(zhuǎn)向步驟5；

步驟5：取數(shù)組D中的下一個(gè)元素，重復(fù)2—4，直到簇序列中沒(méi)有能合并的簇為止；

步驟6：輸出合并后的聚類結(jié)果。

四、DMCA在江蘇省城市科技創(chuàng)新能力評(píng)價(jià)的應(yīng)用

江蘇省共轄13個(gè)地級(jí)市，按經(jīng)濟(jì)發(fā)展水平可分成三類不同地區(qū)，即蘇南、蘇中和蘇北。蘇南為江蘇省發(fā)達(dá)地區(qū)，蘇中為次發(fā)達(dá)的過(guò)渡地區(qū)，蘇北為欠發(fā)達(dá)的地區(qū)。

本文根據(jù)2011年江蘇省統(tǒng)計(jì)年鑒[9]和參考文獻(xiàn)[4]，選取了江蘇省13個(gè)地級(jí)市的5項(xiàng)科技創(chuàng)新能力指標(biāo)數(shù)據(jù)，如表1所示。其中包括：技術(shù)創(chuàng)新環(huán)境、技術(shù)創(chuàng)新投入、技術(shù)創(chuàng)新能力、創(chuàng)新經(jīng)濟(jì)績(jī)效、科技綜合能力。

采用DMCA算法對(duì)其進(jìn)行聚類分析，聚類分析結(jié)果如表2所示。從表2中可以看出，本文算法可以在預(yù)先不設(shè)定閥值的條件下，自動(dòng)將聚類結(jié)果合并成三類，符合江蘇省的實(shí)際發(fā)展情況，而K-means算法和層次聚類算法在聚類個(gè)數(shù)為4的條件下，雖然聚類結(jié)果相同，但與江蘇省實(shí)際情況不符。在聚類個(gè)數(shù)為3的條件下，采用三種聚類算法得到的第三類的聚類結(jié)果相同，第一、二類有所不同，K-means算法把蘇州單獨(dú)歸為一類，出現(xiàn)了孤立點(diǎn)，影響了聚類結(jié)果；層次聚類算法和本文算法聚類結(jié)果的區(qū)別在于把常州歸為第一類還是第二類，根據(jù)分析比較，常州與蘇州、無(wú)錫、南京歸為一類比較好。從以上分析，可以清晰的看出動(dòng)態(tài)合并聚類算法的優(yōu)勢(shì)所在，使用本算法不僅能提高聚類質(zhì)量，而且聚類結(jié)果更加符合實(shí)際，更具參考價(jià)值。

根據(jù)聚類結(jié)果比較，科技創(chuàng)新能力排在江蘇省前四位的城市分別為蘇州市、無(wú)錫市、南京市、常州市。這些地市一般都具有以下特點(diǎn)：相對(duì)于科技創(chuàng)新能力較弱的地區(qū)，這些地市都具有相對(duì)較好的科技基礎(chǔ)，吸引外資相對(duì)較多，尤其是蘇州，已成為中國(guó)吸引外資最多的城市，帶動(dòng)了高新技術(shù)產(chǎn)業(yè)的發(fā)展，也提高了科技創(chuàng)新的綜合競(jìng)爭(zhēng)實(shí)力。蘇中的南通、揚(yáng)州、鎮(zhèn)江、泰州四地市綜合排名大體處于中等水平；蘇北的淮安、宿遷、鹽城、連云港、徐州五地市的綜合排名則為最后五名?？梢钥闯?，江蘇省各地級(jí)市科技創(chuàng)新能力分布不平衡，蘇南地區(qū)的科技創(chuàng)新能力優(yōu)勢(shì)明顯，蘇中地區(qū)的科技創(chuàng)新能力有待提高，蘇北地區(qū)科技創(chuàng)新能力偏弱，需要大力加強(qiáng)科技創(chuàng)新投入和出臺(tái)相應(yīng)的政策措施來(lái)推動(dòng)科技創(chuàng)新能力的發(fā)展。

五、結(jié)束語(yǔ)

本文基于合并式層次聚類的思想，闡述了一種采用簇間差異度進(jìn)行簇自動(dòng)合并劃分的動(dòng)態(tài)合并聚類算法，克服了層次劃分方法不可逆、需要預(yù)先設(shè)定聚類閥值等缺陷。通過(guò)實(shí)踐，將其運(yùn)用到江蘇省技術(shù)創(chuàng)新能力評(píng)價(jià)實(shí)例中，為江蘇省13個(gè)地市的科技創(chuàng)新能力提供了科學(xué)量化決策評(píng)價(jià)，驗(yàn)證了算法的可行性與有效性。與其他聚類方法相比，本算法聚類結(jié)果更加符合客觀實(shí)際，從而對(duì)各地區(qū)科技創(chuàng)新能力分析提供了參考?！?/p>

參考文獻(xiàn)：

[1]中國(guó)網(wǎng).中華人民共和國(guó)國(guó)民經(jīng)濟(jì)和社會(huì)發(fā)展第十二個(gè)五年規(guī)劃綱要（全文）[EB/OL].http：//www.china.com.cn/policy/txt/

2011—03/16/content_22156007.htm

[2]江蘇省發(fā)展規(guī)劃中心.江蘇省“十二五”規(guī)劃綱要（全文）[EB/OL].http：//jsdp.njnu.edu.cn/Article/news_vi-

ew. asp？newsid=928，2011.7.6

[3]《中國(guó)科技發(fā)展研究報(bào)告》研究組. 中國(guó)科技發(fā)展研究報(bào)（2000）—科技全球化及中國(guó)面臨的挑戰(zhàn)[M].北京：社會(huì)科學(xué)文獻(xiàn)出版社，2000.

[4]王芳. 江蘇省科技創(chuàng)新能力的評(píng)價(jià)及對(duì)策[J].科技經(jīng)濟(jì)市場(chǎng)，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]段明秀.層次聚類算法的研究與應(yīng)用[J].中南大學(xué)碩士學(xué)位論文，2009

[9]江蘇省統(tǒng)計(jì)局編：江蘇統(tǒng)計(jì)年鑒2011[M].北京：中國(guó)統(tǒng)計(jì)出版社

（董智，1970年生，江蘇徐州人，江蘇師范大學(xué)外國(guó)語(yǔ)學(xué)院國(guó)際交流系講師。研究方向：市場(chǎng)營(yíng)銷(xiāo)、物流管理、國(guó)際商務(wù)文化）

（三）算法描述

算法：動(dòng)態(tài)合并聚類算法（DMCA）

輸入：輸入包含N個(gè)對(duì)象的數(shù)據(jù)集

輸出：輸出經(jīng)過(guò)自動(dòng)合并后的聚類結(jié)果

步驟1：N個(gè)初始數(shù)據(jù)樣本自成一類，按照公式（1）計(jì)算各類之間（各樣本間）的距離，得到初始化的距離矩陣；

步驟2：對(duì)距離矩陣中N（N-1）/2個(gè)元素按照距離從小到大的順序進(jìn)行快速排序，并將其存儲(chǔ)在一維數(shù)組D中；

步驟3：對(duì)D中的當(dāng)前元素Dij，首先判斷類Ci和Cj是否已經(jīng)被合并到類中，如果沒(méi)有，計(jì)算類Ci和Cj之間的簇間差異度σij；

步驟4：判斷σij，如果σij≤0，將類Ci和Cj合并成為一類Cij，并從簇序列中用Cij替換掉Ci、Cj，否則轉(zhuǎn)向步驟5；

步驟5：取數(shù)組D中的下一個(gè)元素，重復(fù)2—4，直到簇序列中沒(méi)有能合并的簇為止；

步驟6：輸出合并后的聚類結(jié)果。

四、DMCA在江蘇省城市科技創(chuàng)新能力評(píng)價(jià)的應(yīng)用

江蘇省共轄13個(gè)地級(jí)市，按經(jīng)濟(jì)發(fā)展水平可分成三類不同地區(qū)，即蘇南、蘇中和蘇北。蘇南為江蘇省發(fā)達(dá)地區(qū)，蘇中為次發(fā)達(dá)的過(guò)渡地區(qū)，蘇北為欠發(fā)達(dá)的地區(qū)。

本文根據(jù)2011年江蘇省統(tǒng)計(jì)年鑒[9]和參考文獻(xiàn)[4]，選取了江蘇省13個(gè)地級(jí)市的5項(xiàng)科技創(chuàng)新能力指標(biāo)數(shù)據(jù)，如表1所示。其中包括：技術(shù)創(chuàng)新環(huán)境、技術(shù)創(chuàng)新投入、技術(shù)創(chuàng)新能力、創(chuàng)新經(jīng)濟(jì)績(jī)效、科技綜合能力。

采用DMCA算法對(duì)其進(jìn)行聚類分析，聚類分析結(jié)果如表2所示。從表2中可以看出，本文算法可以在預(yù)先不設(shè)定閥值的條件下，自動(dòng)將聚類結(jié)果合并成三類，符合江蘇省的實(shí)際發(fā)展情況，而K-means算法和層次聚類算法在聚類個(gè)數(shù)為4的條件下，雖然聚類結(jié)果相同，但與江蘇省實(shí)際情況不符。在聚類個(gè)數(shù)為3的條件下，采用三種聚類算法得到的第三類的聚類結(jié)果相同，第一、二類有所不同，K-means算法把蘇州單獨(dú)歸為一類，出現(xiàn)了孤立點(diǎn)，影響了聚類結(jié)果；層次聚類算法和本文算法聚類結(jié)果的區(qū)別在于把常州歸為第一類還是第二類，根據(jù)分析比較，常州與蘇州、無(wú)錫、南京歸為一類比較好。從以上分析，可以清晰的看出動(dòng)態(tài)合并聚類算法的優(yōu)勢(shì)所在，使用本算法不僅能提高聚類質(zhì)量，而且聚類結(jié)果更加符合實(shí)際，更具參考價(jià)值。

根據(jù)聚類結(jié)果比較，科技創(chuàng)新能力排在江蘇省前四位的城市分別為蘇州市、無(wú)錫市、南京市、常州市。這些地市一般都具有以下特點(diǎn)：相對(duì)于科技創(chuàng)新能力較弱的地區(qū)，這些地市都具有相對(duì)較好的科技基礎(chǔ)，吸引外資相對(duì)較多，尤其是蘇州，已成為中國(guó)吸引外資最多的城市，帶動(dòng)了高新技術(shù)產(chǎn)業(yè)的發(fā)展，也提高了科技創(chuàng)新的綜合競(jìng)爭(zhēng)實(shí)力。蘇中的南通、揚(yáng)州、鎮(zhèn)江、泰州四地市綜合排名大體處于中等水平；蘇北的淮安、宿遷、鹽城、連云港、徐州五地市的綜合排名則為最后五名?？梢钥闯觯K省各地級(jí)市科技創(chuàng)新能力分布不平衡，蘇南地區(qū)的科技創(chuàng)新能力優(yōu)勢(shì)明顯，蘇中地區(qū)的科技創(chuàng)新能力有待提高，蘇北地區(qū)科技創(chuàng)新能力偏弱，需要大力加強(qiáng)科技創(chuàng)新投入和出臺(tái)相應(yīng)的政策措施來(lái)推動(dòng)科技創(chuàng)新能力的發(fā)展。

五、結(jié)束語(yǔ)

本文基于合并式層次聚類的思想，闡述了一種采用簇間差異度進(jìn)行簇自動(dòng)合并劃分的動(dòng)態(tài)合并聚類算法，克服了層次劃分方法不可逆、需要預(yù)先設(shè)定聚類閥值等缺陷。通過(guò)實(shí)踐，將其運(yùn)用到江蘇省技術(shù)創(chuàng)新能力評(píng)價(jià)實(shí)例中，為江蘇省13個(gè)地市的科技創(chuàng)新能力提供了科學(xué)量化決策評(píng)價(jià)，驗(yàn)證了算法的可行性與有效性。與其他聚類方法相比，本算法聚類結(jié)果更加符合客觀實(shí)際，從而對(duì)各地區(qū)科技創(chuàng)新能力分析提供了參考?！?/p>

參考文獻(xiàn)：

[1]中國(guó)網(wǎng).中華人民共和國(guó)國(guó)民經(jīng)濟(jì)和社會(huì)發(fā)展第十二個(gè)五年規(guī)劃綱要（全文）[EB/OL].http：//www.china.com.cn/policy/txt/

2011—03/16/content_22156007.htm

[2]江蘇省發(fā)展規(guī)劃中心.江蘇省“十二五”規(guī)劃綱要（全文）[EB/OL].http：//jsdp.njnu.edu.cn/Article/news_vi-

ew. asp？newsid=928，2011.7.6

[3]《中國(guó)科技發(fā)展研究報(bào)告》研究組. 中國(guó)科技發(fā)展研究報(bào)（2000）—科技全球化及中國(guó)面臨的挑戰(zhàn)[M].北京：社會(huì)科學(xué)文獻(xiàn)出版社，2000.

[4]王芳. 江蘇省科技創(chuàng)新能力的評(píng)價(jià)及對(duì)策[J].科技經(jīng)濟(jì)市場(chǎng)，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]段明秀.層次聚類算法的研究與應(yīng)用[J].中南大學(xué)碩士學(xué)位論文，2009

[9]江蘇省統(tǒng)計(jì)局編：江蘇統(tǒng)計(jì)年鑒2011[M].北京：中國(guó)統(tǒng)計(jì)出版社

（董智，1970年生，江蘇徐州人，江蘇師范大學(xué)外國(guó)語(yǔ)學(xué)院國(guó)際交流系講師。研究方向：市場(chǎng)營(yíng)銷(xiāo)、物流管理、國(guó)際商務(wù)文化）