基于萬有引力的簇間距離表示法

韓海

（江漢大學數學與計算機科學學院，湖北武漢430056）

基于萬有引力的簇間距離表示法

韓海

（江漢大學數學與計算機科學學院，湖北武漢430056）

分析了幾種現有聚類算法中簇間距離表示法的優(yōu)缺點，并在此基礎上提出了一種基于萬有引力模型的簇間距離計算方法。該方法模仿物理學中力的合成原理，是對把各質點間引力數值直接相加的重要改進。理論分析及數據計算的結果都表明，該方法比引力直接相加有更廣的適應性。

聚類；簇間距離；引力；積分

0 引言

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

聚類是重要的數據分析方法。針對大量的數據樣本，聚類就是根據樣本之間的聯系緊密程度對它們進行分組，使得同一組內的樣本聯系緊密而不同組的樣本之間聯系松散。聚類得到的每一個分組稱為一個簇。聚類的目的在于確定分組的標準，并分析各個簇的特點，從而對新的數據估計它可能屬于哪一個簇，相應地制定有針對性的處理方案。

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

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

1 定義簇間距離

圖1是一個二維數據樣本分布示例，每個“○”代表一個數據樣本。一般會考慮把這個樣本集合分成3個簇，即左上、右上和下半部分各一個簇。但是，按圖1中的虛線把樣本數據劃分成4部分之后，可以看出位于左上角的簇與位于左下角的樣本都是由31個數據構成，把左上的簇旋轉90°后與左下方的樣本結構相同。正是這個旋轉，導致了上方的62個數據被分成兩個簇，而下方同樣是62個數據卻分在一個簇內。這一現象顯然應該通過簇間距離的不同來說明。本文下面提出的方法能較好地描述這個旋轉導致的簇間距離差異。

圖1 樣本數據Fig.1Sample data

根據萬有引力定律，兩個質點P1和P2之間的引力大小相等、方向相反，并且力的方向在同一條直線上，其引力數值F（P1，P2）的計算公式為

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

圖2 萬有引力模型Fig.2Model of gravitation

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

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

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

圖3 質點間引力的效果Fig.3Effect of gravitation between particles

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

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

2不同簇間距離計算方法的對比

將圖1中的樣本沿居中的“+”劃分成4個簇，上方的兩個簇記作A和B，左下方的簇記作C，右下方的簇記作D。為了更好地說明計算方法上的差異，添加圖4中的樣本數據作為對比。記圖4上方的簇為E，下方的簇為F?？梢钥吹?，每個簇均包含31個數據，A與B的中心點之間距離為7，C與D的中心點之間距離也為7，E與F的中心點之間距離接近于5。設水平相鄰和垂直相鄰的兩個“○”之間的距離均為1，表1是不同的簇間距離表示法針對d（A，B）、d（C，D）及d（E，F）的計算結果。

圖4 非球形簇樣本數據Fig.4Nonspherical cluster sample data

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

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

3 結語

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

圖5 聚類效果Fig.5Result of clustering

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

（References）

［1］張大慶，徐再花.一種新的模糊聚類有效性指標［J］.沈陽農業(yè)大學學報，2012，43（5）：636-639.

［2］李雙虎，張風海.一個新的聚類有效性分析指標［J］.計算機工程與設計，2007，28（8）：1772-1774.

［3］季鐸，王智超，蔡東風，等.基于高斯分布的簇間距離計算方法［J］.中文信息學報，2008，22（3）：50-55.

［4］劉啟亮，鄧敏，彭東亮，等.基于力學思想的空間聚類有效性評價［J］.武漢大學學報：信息科學版，2011，36（8）：982-986，990.

［5］于勇前，趙相國，陳衡岳，等.基于引力概念的聚類質量評估算法［J］.東北大學學報：自然科學版，2007，28（8）：1109-1112.

（責任編輯：曾婷）

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—），男，副教授，研究方向：圖形圖像處理及模式識別。