逼近法確定球形簇的球心與半徑

韓 海

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

聚類在現(xiàn)實中有非常廣泛的應(yīng)用。聚類的結(jié)果是將多個對象劃分成若干組，同組的對象具有相同或相近的性質(zhì)。進一步地，聚類的目的之一是建立分類標(biāo)準(zhǔn)，并認(rèn)為符合某個標(biāo)準(zhǔn)的對象應(yīng)屬于相應(yīng)的類，通常會具有對應(yīng)的性質(zhì)。

設(shè)一個數(shù)據(jù)對象W包含n個分量，記作W=(w1，w2，…，wn)，一個對象就是 n 維空間的一個點。若X和Y是n維空間中的兩個點，則X和Y之間的歐氏距離為

聚類是將由多個數(shù)據(jù)對象構(gòu)成的集合劃分成若干個互不相交的子集，使得每個子集內(nèi)的元素“聯(lián)系”緊密，而處于兩個不同子集內(nèi)的元素“聯(lián)系”松散。劃分出的每一個子集稱為一個“簇”，而“聯(lián)系”通常被理解為兩個元素之間的歐氏距離。文獻［1-3］使用這種方式表示“聯(lián)系”，并在此基礎(chǔ)上進行聚類。聚類得到的結(jié)果往往不易直接建立分類標(biāo)準(zhǔn)，因而通常都把結(jié)果近似地認(rèn)為是球形簇，以下主要討論如何確定每個球形簇的范圍。

不妨設(shè)T是對集合S經(jīng)過聚類后得到的一個球形簇，其中包含k個數(shù)據(jù)元素，即包含n維空間的k個點，并且大致均勻分布成球狀。確定T的幾何范圍就是需要確定一個n維球（球心記作點P，半徑記作r，由P和r確定的球記作球B），使得T中的所有元素均在球內(nèi)，并且球的半徑盡可能小。雖然從數(shù)學(xué)上精確地確定P和r非常困難，但可以從一個初始狀態(tài)出發(fā)，通過逐步優(yōu)化，最終得到一個滿足精度要求的n維球。

1 確定初始參數(shù)

初始半徑r取值為P到T中元素的最大距離。顯然，這樣的球包含了T的所有元素。對于球心移動的距離L，初始時可以取一個比較大的值，比如，從而使得球心能夠比較快地向目標(biāo)位置移動。另外，設(shè)精度要求為θ，即最終得到的球心位置及半徑與準(zhǔn)確值相差均不超過θ或者θ的若干倍。

2 逐步優(yōu)化

逐步優(yōu)化的過程是每次把球心移動L的距離，重新計算半徑，并限制半徑只能減小。如果已經(jīng)不能進行這樣的移動，則將移動距離參數(shù)L減半，然后重復(fù)上述移動。當(dāng)L經(jīng)過若干次減半后將會小于，此時的球心位置及半徑即為最終結(jié)果。

2.1 確定球心的移動位置

對于當(dāng)前的球心P，找出T中所有滿足“到P的距離與r的差值小于L”的元素，即：對于元素 T(i)(i=1，2，…，k)，如果 T(i)滿足則認(rèn)為“T(i)在球面上”。由確定r的方式可知，滿足該條件的點一定存在，于是可以對這些點求均值，得到點Q。

如果d(P，Q)＜L，則球心移動距離已經(jīng)小于L，于是將L減半，重新找出滿足（2）式的點并計算均值Q。反之，如果d(P，Q)≥L，則在PQ連線上取一點 P′，使得 d(P，P′)=L。

2.2 重新確定半徑

對于2.1中得到的點 P′和T中所有元素T(i)(i=1，2，…，k)，計算 d(T(i)， P′)，并取最大值，記作 r′。如果 r′≤r，則將球心移動到 P′，并以 r′作為新的半徑，即令P和r分別取值為P′和r′，然后按新的球心和半徑重復(fù)上述方法處理。反之，如果r′＞r，則將球心移動到 P′是不合適的，此時將L減半，然后重復(fù)上述方法處理。

2.3 算法流程圖

算法流程如圖1所示。

圖1 算法流程圖

3 算法有效性

對于由k個點構(gòu)成的簇T，顯然，包裹T中所有點的最小n維球是唯一存在的，記作B0=(P0，r0)，球心在點 P0，半徑為r0。記算法終止時以P和r為參數(shù)的球為B，以P為球心、r-θ為半徑的球為B′。當(dāng)T中元素大致均勻分布且r＞＞θ時，上述算法得到的P點相對P0點的偏差不超過2θ，r與r0的偏差不超過θ，即

圖2中灰色環(huán)外層表示以P為球心、r為半徑的球B，由算法中確定r的方式可知T中至少存在一點T(x)，使得d(P，T(x))=r。灰色環(huán)內(nèi)層表示以P為球心、r-θ為半徑的球B′，如果T中的點在灰色區(qū)域內(nèi)則在算法中認(rèn)為“該點在球面上”?；疑h(huán)的“厚度”為θ，虛線表示以P0為球心、以r0為半徑的理論上的最小球B0。顯然，T中所有元素必在球B內(nèi)（含球面上），也必在球B0內(nèi)（含球面上）。

由于r0是理論上包裹T的最小球的半徑，顯然有 r≥r0。

假設(shè)r＞r0+θ，不難看出圖2所示3種位置關(guān)系都將導(dǎo)致矛盾：對于圖2（a），算法決定了灰色環(huán)內(nèi)必有元素，這與“所有元素必在球B0內(nèi)”相矛盾；對于圖2（b）和圖2（c），由于算法中認(rèn)定為“在球面上”的點只能出現(xiàn)在虛線球內(nèi)的灰色區(qū)域，并且分布大致均勻，因而圖2的兩種位置關(guān)系應(yīng)使得算法繼續(xù)執(zhí)行，這與“算法已終止”相矛盾。由此可知≤θ。

圖2 r＞r0+θ時3個球的位置關(guān)系

假設(shè) d(P，P0)＞2θ，由于 | |r-r0≤θ，3個球只可能出現(xiàn)如圖3所示的位置關(guān)系。 A為球B′和球 B0交線上一點，d(P0，A)=r0，d(P，A)=r-θ。在r＞＞θ且數(shù)據(jù)大致均勻分布時，算法應(yīng)繼續(xù)執(zhí)行，對球心P作一次合適的移動，這與算法已終止相矛盾。因此，假設(shè) d(P，P0)＞2θ不成立。

圖3 d(P，P0)＞2θ時的位置關(guān)系

4 結(jié)論

對包括IRIS鳶尾花數(shù)據(jù)在內(nèi)的多組數(shù)據(jù)測試結(jié)果表明，上述算法都能穩(wěn)定運行并產(chǎn)生理想的結(jié)果。在n=2時，該算法還可用于求覆蓋多邊形的最小圓［4］。筆者也對非均勻分布的簇（即非球形簇）進行了測試，算法能夠得到有效輸出，只是元素集中在球內(nèi)某些位置。從多組數(shù)據(jù)的聚類結(jié)果可以看出，形成非球形簇的情況是更普遍現(xiàn)象，因此，盡管可以用本算法求得一個簇的最小球形范圍，但用“如果一個元素在該范圍內(nèi)則屬于相應(yīng)的簇”對元素進行歸類則不太合適。

［1］王德青，朱建平，謝邦昌.主成分聚類分析有效性的思考［J］.統(tǒng)計研究，2012，29（11）：84-87.

［2］Bai T，Kulikowski C A，Gong L G，et al.A Global K-modes algorithm for clustering categorical data［J］.Chinese Journal of Electronics，2012，21（3）：460-465.

［3］邱保志，王波.分類數(shù)據(jù)的聚類邊界檢測技術(shù)［J］.計算機應(yīng)用，2012，32（6）：1654-1657.

［4］戴海鵬，唐厚君.求凸多邊形直徑的改進算法［J］.計算機工程與應(yīng)用，2011，47（3）：44-46.