韓海

（江漢大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，湖北武漢430056）

基于萬(wàn)有引力的簇間距離表示法

韓海

（江漢大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，湖北武漢430056）

分析了幾種現(xiàn)有聚類(lèi)算法中簇間距離表示法的優(yōu)缺點(diǎn)，并在此基礎(chǔ)上提出了一種基于萬(wàn)有引力模型的簇間距離計(jì)算方法。該方法模仿物理學(xué)中力的合成原理，是對(duì)把各質(zhì)點(diǎn)間引力數(shù)值直接相加的重要改進(jìn)。理論分析及數(shù)據(jù)計(jì)算的結(jié)果都表明，該方法比引力直接相加有更廣的適應(yīng)性。

聚類(lèi)；簇間距離；引力；積分

0 引言

隨著大數(shù)據(jù)時(shí)代的到來(lái)，聚類(lèi)越來(lái)越受到人們的重視，也在越來(lái)越多的領(lǐng)域發(fā)揮作用。實(shí)際應(yīng)用表明，運(yùn)用聚類(lèi)方法對(duì)已有的統(tǒng)計(jì)數(shù)據(jù)進(jìn)行分析，相應(yīng)地采取不同的措施，可以使得工作有針對(duì)性，從而提高工作效率。

聚類(lèi)是重要的數(shù)據(jù)分析方法。針對(duì)大量的數(shù)據(jù)樣本，聚類(lèi)就是根據(jù)樣本之間的聯(lián)系緊密程度對(duì)它們進(jìn)行分組，使得同一組內(nèi)的樣本聯(lián)系緊密而不同組的樣本之間聯(lián)系松散。聚類(lèi)得到的每一個(gè)分組稱為一個(gè)簇。聚類(lèi)的目的在于確定分組的標(biāo)準(zhǔn)，并分析各個(gè)簇的特點(diǎn)，從而對(duì)新的數(shù)據(jù)估計(jì)它可能屬于哪一個(gè)簇，相應(yīng)地制定有針對(duì)性的處理方案。

聚類(lèi)總是需要在若干種分組結(jié)果中選取人們認(rèn)為最優(yōu)的分組方案。為了能對(duì)各種分組方案進(jìn)行比較，通常都需要建立一個(gè)聚類(lèi)有效性函數(shù)。在常用的聚類(lèi)處理方法中，絕大多數(shù)都綜合考慮兩項(xiàng)指標(biāo)，即用于表示分組內(nèi)部聯(lián)系緊密程度的指標(biāo)和用于表示不同分組之間的聯(lián)系緊密程度的指標(biāo)，兩個(gè)指標(biāo)分別稱為“簇內(nèi)距離”和“簇間距離”。

目前，大家對(duì)于描述簇內(nèi)距離的指標(biāo)相對(duì)比較認(rèn)可，但是對(duì)簇間距離的表示仍然存在較大爭(zhēng)議，也因此提出了各種各樣的簇間距離計(jì)算方法。關(guān)于簇間距離的簡(jiǎn)單處理方法是計(jì)算簇外樣本到本簇中心點(diǎn)的距離，比如計(jì)算兩個(gè)簇中樣本的最小距離、最大距離，或者計(jì)算簇的中心到簇外樣本的最小距離等，這類(lèi)方法由于計(jì)算比較簡(jiǎn)單因而被較多地采用。在文獻(xiàn)［1-3］提出的有效性計(jì)算函數(shù)中，簇間距離的計(jì)算都采用了這類(lèi)方法。這類(lèi)方法要求簇中樣本應(yīng)圍繞簇中心點(diǎn)成球狀分布，且離球心越近樣本越多，離球心越遠(yuǎn)樣本越少，即高斯分布，但這個(gè)要求往往與樣本的實(shí)際分布有一定差距。文獻(xiàn)［4-5］提出了類(lèi)似于萬(wàn)有引力的“凝聚力”計(jì)算式，并以此作為簇內(nèi)距離及簇間距離的評(píng)價(jià)指標(biāo)，該方法明顯地考慮了簇中樣本分布對(duì)簇內(nèi)距離及簇間距離的影響，但從力學(xué)角度來(lái)看，不同方向的力不能簡(jiǎn)單地以數(shù)值相加。本文正是在萬(wàn)有引力或者說(shuō)“凝聚力”的基礎(chǔ)上，加進(jìn)了關(guān)于引力方向的考慮，從而確定一種新的簇間距離計(jì)算方案。

1 定義簇間距離

圖1是一個(gè)二維數(shù)據(jù)樣本分布示例，每個(gè)“○”代表一個(gè)數(shù)據(jù)樣本。一般會(huì)考慮把這個(gè)樣本集合分成3個(gè)簇，即左上、右上和下半部分各一個(gè)簇。但是，按圖1中的虛線把樣本數(shù)據(jù)劃分成4部分之后，可以看出位于左上角的簇與位于左下角的樣本都是由31個(gè)數(shù)據(jù)構(gòu)成，把左上的簇旋轉(zhuǎn)90°后與左下方的樣本結(jié)構(gòu)相同。正是這個(gè)旋轉(zhuǎn)，導(dǎo)致了上方的62個(gè)數(shù)據(jù)被分成兩個(gè)簇，而下方同樣是62個(gè)數(shù)據(jù)卻分在一個(gè)簇內(nèi)。這一現(xiàn)象顯然應(yīng)該通過(guò)簇間距離的不同來(lái)說(shuō)明。本文下面提出的方法能較好地描述這個(gè)旋轉(zhuǎn)導(dǎo)致的簇間距離差異。

圖1 樣本數(shù)據(jù)Fig.1Sample data

根據(jù)萬(wàn)有引力定律，兩個(gè)質(zhì)點(diǎn)P1和P2之間的引力大小相等、方向相反，并且力的方向在同一條直線上，其引力數(shù)值F（P1，P2）的計(jì)算公式為

數(shù)學(xué)上已經(jīng)證明，如圖2所示的兩個(gè)勻質(zhì)球體間的萬(wàn)有引力也符合上述公式。其中m1、m2是兩個(gè)質(zhì)點(diǎn)（或者勻質(zhì)球體）的質(zhì)量，r=d(P1，P2)是兩個(gè)質(zhì)點(diǎn)（或者兩個(gè)勻質(zhì)球體的中心）之間的距離，G為萬(wàn)有引力常量。但是，對(duì)于非勻質(zhì)球形物體，其引力的計(jì)算就需要用到多重積分。如果兩個(gè)物體初始時(shí)處于靜止?fàn)顟B(tài)，在不考慮其他外力的情況下，兩個(gè)物體之間的萬(wàn)有引力將造成兩個(gè)物體相向運(yùn)動(dòng)，并可能存在某種角度的旋轉(zhuǎn)。盡管聚類(lèi)問(wèn)題中的簇并不是自然界中的物體，但可以借用以積分方式求萬(wàn)有引力的思想來(lái)描述兩個(gè)簇之間的聯(lián)系緊密程度，從而能更好地描述簇內(nèi)樣本分布不均勻情況下的簇間距離。

圖2 萬(wàn)有引力模型Fig.2Model of gravitation

設(shè)X、Y是兩個(gè)簇，X={x1，x2，…，xn}，Y={y1，y2，…，ym}，以xˉ表示X的中心，yˉ表示Y的中心，

定義X、Y的簇間距離d(X，Y)為

其中F(xi，yj)是樣本數(shù)據(jù)xi和yj按（1）式計(jì)算得到的引力值，其中的引力常量G取1，θij是通過(guò)xi和yj的直線與通過(guò)xˉ和yˉ的直線所形成的夾角，如圖3所示。

圖3 質(zhì)點(diǎn)間引力的效果Fig.3Effect of gravitation between particles

按照如上方式定義兩個(gè)簇之間的距離，實(shí)際上是把X和Y視作兩個(gè)非勻質(zhì)物體，借用積分思想求引力的合力，準(zhǔn)確地說(shuō)是求萬(wàn)有引力造成兩物體相向運(yùn)動(dòng)的引力分量，并用該分量的數(shù)值作為X和Y的簇間距離。從力的合成的角度考慮，兩物體間的萬(wàn)有引力是其中所有質(zhì)點(diǎn)對(duì)(xi，yj)之間的引力的合力，其造成物體相向運(yùn)動(dòng)的引力分量是這些質(zhì)點(diǎn)對(duì)之間的引力在xˉ和yˉ連線上的投影之和，而F(xi，yj)cosθij正是求質(zhì)點(diǎn)對(duì)(xi，yj)之間的引力在物體中心點(diǎn)連線上的投影。記和分別是xi和yj在與連線（或者其延長(zhǎng)線）上的投影，則

其中d(xi，yj)和是兩點(diǎn)間的歐氏距離。

2不同簇間距離計(jì)算方法的對(duì)比

將圖1中的樣本沿居中的“+”劃分成4個(gè)簇，上方的兩個(gè)簇記作A和B，左下方的簇記作C，右下方的簇記作D。為了更好地說(shuō)明計(jì)算方法上的差異，添加圖4中的樣本數(shù)據(jù)作為對(duì)比。記圖4上方的簇為E，下方的簇為F。可以看到，每個(gè)簇均包含31個(gè)數(shù)據(jù)，A與B的中心點(diǎn)之間距離為7，C與D的中心點(diǎn)之間距離也為7，E與F的中心點(diǎn)之間距離接近于5。設(shè)水平相鄰和垂直相鄰的兩個(gè)“○”之間的距離均為1，表1是不同的簇間距離表示法針對(duì)d（A，B）、d（C，D）及d（E，F(xiàn)）的計(jì)算結(jié)果。

圖4 非球形簇樣本數(shù)據(jù)Fig.4Nonspherical cluster sample data

表1 不同簇間距離計(jì)算方法對(duì)比Tab.1Comparison of different methods for calculating distance of clusters

前4種簇間距離表示方法都以數(shù)值越小表示簇間聯(lián)系越緊密，后兩種表示法則相反。后3種方法均能將簇的內(nèi)部結(jié)構(gòu)反映在簇間距離上，并且都認(rèn)為C、D的簇間距離最小。第四種方法和本文所述的方法均認(rèn)為E、F的簇間距離最大，而第五種方法認(rèn)為A、B的簇間距離最大。第四種方法雖然能夠體現(xiàn)簇的內(nèi)部結(jié)構(gòu)，但數(shù)據(jù)計(jì)算結(jié)果的敏感度較差，比如A、B的簇間距離與C、D的簇間距離差別明顯，但該方法的計(jì)算結(jié)果差別不大?？梢钥吹剑疚奶岢龅囊院铣梢Ρ硎敬亻g距離可以較好地表現(xiàn)簇的內(nèi)部結(jié)構(gòu)對(duì)簇間距離的影響。

3 結(jié)語(yǔ)

聚類(lèi)問(wèn)題最終是要研究對(duì)類(lèi)似于圖1的樣本進(jìn)行分組的最優(yōu)解。一個(gè)有趣的現(xiàn)象是，稍稍調(diào)整樣本的分布，答案就可能不同。在此，僅以本文所述簇間距離之和作為聚類(lèi)標(biāo)準(zhǔn)。在本文依據(jù)引力模型提出的距離定義之下，簇間距離表現(xiàn)為簇間的引力，數(shù)值越大則簇間分離度越差。據(jù)此對(duì)圖1的樣本進(jìn)行聚類(lèi)處理，則應(yīng)該分成3個(gè)簇，如圖5（b）所示，其中圓的半徑是簇中樣本到簇中心點(diǎn)的平均距離。如果加大圖1樣本數(shù)據(jù)的上下間隔，把中間的3個(gè)空行加為5行，則此時(shí)應(yīng)分為兩個(gè)簇，見(jiàn)圖5（a）；反之如果將空行縮減為1行，則應(yīng)分為4個(gè)簇，見(jiàn)圖5（c）。當(dāng)然，不同的聚類(lèi)標(biāo)準(zhǔn)將導(dǎo)致不同的結(jié)果?？梢?jiàn)，聚類(lèi)問(wèn)題的解與方法及樣本分布都有關(guān)。

圖5 聚類(lèi)效果Fig.5Result of clustering

綜上所述，本文的方法更符合自然界中的物理學(xué)有關(guān)規(guī)律，對(duì)簇間距離的描述也不依賴于高斯分布或者球形分布，因而具有更廣泛的適用性。

（References）

［1］張大慶，徐再花.一種新的模糊聚類(lèi)有效性指標(biāo)［J］.沈陽(yáng)農(nóng)業(yè)大學(xué)學(xué)報(bào)，2012，43（5）：636-639.

［2］李雙虎，張風(fēng)海.一個(gè)新的聚類(lèi)有效性分析指標(biāo)［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2007，28（8）：1772-1774.

［3］季鐸，王智超，蔡?hào)|風(fēng)，等.基于高斯分布的簇間距離計(jì)算方法［J］.中文信息學(xué)報(bào)，2008，22（3）：50-55.

［4］劉啟亮，鄧敏，彭東亮，等.基于力學(xué)思想的空間聚類(lèi)有效性評(píng)價(jià)［J］.武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2011，36（8）：982-986，990.

［5］于勇前，趙相國(guó)，陳衡岳，等.基于引力概念的聚類(lèi)質(zhì)量評(píng)估算法［J］.東北大學(xué)學(xué)報(bào)：自然科學(xué)版，2007，28（8）：1109-1112.

（責(zé)任編輯：曾婷）

Description of Distance Between Clusters Based on Gravitation

HAN Hai
（School of Mathematics and Computer Science，Jianghan University，Wuhan 430056，Hubei，China）

Analyses the advantages and disadvantages of several existing methods for description of distance between clusters，based on it，presents a calculation method for distance between clusters based on gravitation model.This method is an important improvement for direct addition of gravita?tion value between each particle，which simulates the synthetic principle of force in physics.Theoreti?cal analysis and computing results show the presented method is more applicable than direct addition of gravitation.

clustering；distance between clusters；gravitation；integral

TP301.6

：A

：1673-0143（2014）05-0036-04

2014-08-13

韓海（1968—），男，副教授，研究方向：圖形圖像處理及模式識(shí)別。