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

韓 海

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

聚類在現實中有非常廣泛的應用。聚類的結果是將多個對象劃分成若干組，同組的對象具有相同或相近的性質。進一步地，聚類的目的之一是建立分類標準，并認為符合某個標準的對象應屬于相應的類，通常會具有對應的性質。

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

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

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

1 確定初始參數

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

2 逐步優化

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

2.1 確定球心的移動位置

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

如果d(P，Q)＜L，則球心移動距離已經小于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′，然后按新的球心和半徑重復上述方法處理。反之，如果r′＞r，則將球心移動到 P′是不合適的，此時將L減半，然后重復上述方法處理。

2.3 算法流程圖

算法流程如圖1所示。

圖1 算法流程圖

3 算法有效性

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

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

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

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

圖2 r＞r0+θ時3個球的位置關系

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

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

4 結論

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

［1］王德青，朱建平，謝邦昌.主成分聚類分析有效性的思考［J］.統計研究，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］邱保志，王波.分類數據的聚類邊界檢測技術［J］.計算機應用，2012，32（6）：1654-1657.

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