（山東大學計算機科學與技術學院，濟南，山東，250101）
摘 要:這是一個基于網格的均勻簇劃分算法，通過對網格的二分和與其鄰居節點進行合并，將圖像上的若干個網格聚成一個合適的簇。這樣得到的聚類結果不僅能保證具有相似性的點聚在一個簇內，還能保證每個簇內含有的點的數目相等，即得到的是均勻簇。此算法既有基于網格的聚類方法計算速度快的優點，又克服了傳統的聚類方法不能得到均勻簇的不足。最后通過仿真實驗證明了該算法的有效性。
關鍵詞: 網格；聚類；均勻簇；二分法
A New Method For Partioning Even Clusters Based On Grid
XIE Jing 1, SHI Bing1, FU Lihong 1
(1School of computer science and technology, Shandong University, Jinan, China 250101）
Abstract: A new method for partioning even clusters based on grid is presented in this paper. By bisecting and merging the grids, this algorithm will gather some grids into one cluster. Therefore, the result of this method not only ensures that the points with similarity are divided into one cluster but also ensures the number of points in every cluster is equal. Therefore, this algorithm has two properties: one is that it has fast calculation of Grid computing; the other is it overcomes the obstacle that existing data clustering methods cannot get even clusters. The simulations verify the validity of this method.
Keywords: grid; data clustering; even cluster; bisection
1引言
聚類[1,2]是將物理或抽象的集合分成為由若干個類似的對象組成的多個類的過程，廣泛應用于諸多領域，如模式識別[3]和圖像處理，市場分析和數據分析，生物學和地球科學等。迄今為止，聚類的方法基本上分為四類：基于劃分的方法[4]，基于層次的方法[5]，基于密度的方法[6]和基于網格的方法[7]�；趧澐值木垲惙椒ㄊ且詧D像上的距離為劃分標準，但不適合處理高維的數據；層次聚類方法的一個步驟完成之后，不能再進行撤銷，往往需要結合別的聚類方法；基于密度的方法對于分散的、高維數據效果不好；基于網格的方法則比較適用于高維數據和復雜形狀[8]。近年來，基于網格的聚類方法以其計算速度快的優點得到了廣泛的應用和良好的發展[9,10]。
在基于網格的聚類方法中，比較有代表性的方法是STING和CLIQUE[11]。在這些算法中，每個數據對象被分配到一個固定的網格中，再對每個網格進行處理。在處理的過程中，每個數據對象的歸屬及網格的尺寸都是不變的，因此又稱固定網格算法。在此種情況下，網格的劃分就對聚類分析的質量有著重要的影響。如果網格劃分的比較細，計算量會明顯增加；但若是劃分的比較粗的話，就會大大降低聚類的質量。
目前已有的聚類方法都是把具有“相似性”的數據聚在一個簇內，最后得到若干個簇，每個簇內含有的對象數目各不相同。然而，在有些情況下，我們還需要每個簇內包含的對象數目相等。例如通信基站位置的選取。在通信中，一個基站的容量是有限的，即在同一時刻，一個基站只能為一定數目的用戶提供通信服務。近年來研究表明基站有很強的輻射性，對人體有極大的傷害。因此，我們在建立基站的時候，要盡可能減少基站的數目，并且不影響到用戶的正常通信，這就要求我們把一個地區的人群按照地理位置靠近的原則，分成人口數相等的若干個簇。
本文是在基于以上研究的背景下，提出的基于網格的均勻簇劃分算法。先把數據對象劃分成若干個網格，再對網格進行二分和合并操作，得到含有實體數目相同的若干個均勻簇。該算法既有網格聚類方法處理速度快的優點，又可以在處理的過程中對網格進行靈活的二分處理，提高了聚類結果的正確性。更重要的是，能夠保證最后得到的每個簇內含有的數據對象數目相等。
2基于網格的均勻簇劃分算法
2.1 算法的總體思路
算法的總體思路是先將數據對象分為若干個網格，然后從第一個網格開始進行操作，先與其右邊的未被訪問的鄰居進行合并，若合并后仍小于要求的點數目，再找其下面的鄰居網格進行合并，若還沒有達到要求的點的數目，再與其右下方的鄰居合并…，直到合并到網格Mj時，所有合并起來的網格內的總的點數目大于或等于要求的均勻簇里含有的點數目，則停止合并。若等于要求的點的數目，則將這些網格合并為一個符合要求的簇；若大于要求的點的數目，則對網格Mj在x方向上進行二分，再對分裂后的子網格進行同樣的合并操作，直至得到符合要求的簇。按這樣的方法對所有的網格進行處理，直至圖像上不存在未處理的網格。
2.2 算法的基本步驟和說明
假設給定一個圖像上有若干個點，要求我們將該其分為點數相等的C個區域。算法的基本步驟如下[12]：
①對圖像進行處理，計算要求的均勻簇內的點數目NC=N/C。劃分各個坐標軸形成網格。
②計算圖像上每一個網格的信息，包括每個網格內點的數目S；每個網格左上頂點的信息；網格大小的信息；網格所屬的簇的信息；網格是否被訪問的信息；網格的鄰居信息等。將所有的這些信息存儲在一個矩陣中。
③程序開始時，所有網格都為未訪問狀態。將所有這些未訪問的網格放入隊列q中。取隊列q頭上的網格M1，與其鄰居網格進行合并，合并后有三種情況：
④對以上三種情況進行分別處理，保證每種情況下都能得到一個符合要求的簇。處理的過程包括合并和二分操作，每對一個網格進行了操作，就將其在隊列q中刪去；每分裂出一個新的網格，就將其加入到隊列中。
⑤繼續取隊列q中的下一個網格，回到步驟③，進行同樣的操作，直到隊列q為空，則代表所有的網格都已經被劃分到相應的簇中。
⑥把不同的簇用不同的顏色標出來。
以上每個步驟的詳細說明如下：
Step1. 對圖像進行處理，計算圖像內所有的點數目，設點的總數目為N。假設要把圖像分為C個大小相等的簇，則要求每個簇內包含的點數目都為NC=N/C；再根據圖像的大小，對二維圖像進行合適的劃分，將其分為K*K個網格。
Step2. 計算每個網格的信息，存儲在一個K*K行，15列的矩陣中。矩陣中的每一行代表圖像中的一個網格，每一列代表網格的一個屬性。網格的15個屬性分別為每個網格的編號i、網格左上頂點的x坐標和y坐標、網格在x和y方向上的距離、該網格內含有的點的數目S、該網格被劃分到的簇的編號T以及該網格的鄰居網格的編號。在計算鄰居節點時候，我們采用傳統意義上的八相鄰定義。對于不存在的鄰居，將其鄰居的編號設為0。操作之前的矩陣信息如下表所示。
表1. 所有網格的信息矩陣
|
每
個
網
格
編
號
i |
左上
頂點
x
坐標 |
左上
頂點
y
坐標 |
x
方向
上
的
長度 |
y
方向
上
的
長度 |
網格
內的
點數
S |
分到
簇的
編號
T |
右
邊鄰
居的
編號 |
… |
左
邊
鄰
居
的
編
號 |
|
1 |
1 |
1 |
10 |
10 |
6 |
0 |
2 |
|
0 |
|
2 |
1 |
11 |
10 |
10 |
3 |
0 |
3 |
|
1 |
|
… |
|
|
|
|
|
|
|
|
|
|
K*K |
41 |
41 |
10 |
10 |
7 |
0 |
0 |
|
K*K-1 |
|
|
|
|
|
|
|
|
|
|
|
Step3. 在未進行操作之前，所有網格所屬的簇的編號初始化為0，即都未被訪問。將所有未被訪問的網格的編號放入隊列q中。選取隊列q中的第一個網格M1開始運算,將此網格與其鄰居網格進行合并。先將M1在隊列q中刪去，并將其所屬的簇T的編號設為t的值（t初始劃為1）。再將兩個網格的S值相加，相加后會出現三種情況，即③中（1），（2）和（3）。
Step4. 對Step3中的三種情況分別處理。先來看情況（1），即合并網格Mj后，兩個網格的S值相加等于NC，這時，網格M1和網格Mj合并起來就是一個符合要求的簇。將網格Mj的屬性T改為t的值，執行t=t+1操作，并將網格Mj隊列q中刪去。到步驟⑤進行下一步操作。
若合并后滿足條件（2），則代表這兩個網格合并后二者含有的點數目相加還達不到規定的簇內的點數目，需要繼續進行合并操作。這時，把網格Mj的屬性T值設為t，但不執行t=t+1操作，因為簇t要繼續合并新的網格，將網格Mj從隊列q中刪去，繼續找網格M1的下一個鄰居進行合并，合并后仍然會有③中的三種情況，即到步驟④。在條件（2）下，若網格M1跟它所有的八個鄰居合并之后，仍滿足條件（2），這時我們用遞歸的方式，找網格M1的第一個鄰居網格M2的未訪問的鄰居再進行合并。
若合并后符合條件（3），即這些網格的S值相加大于要求的簇內的點數。此時我們需要對網格Mj進行二分操作。在本算法中，對網格的二分只在x方向進行，如下圖所示。
每進行一次二分，則就會多出一個網格，我們將新分出的網格編號設為K*K+1，更新矩陣內網格Mj的信息：將網格Mj在x方向上的距離減半，重新計算該網格內含有的點的數目，并將其右面鄰居的編號改為新出現的網格MK*K+1；計算新出現的網格MK*K+1的各個屬性，添加在原矩陣的最后一行。將網格MK*K+1插入隊列q中。將改變了屬性S的網格Mj重新進行合并操作，更新
的值，即先減去網格Mj的原S值，再加上該網格現在的S值，更新后仍有三種情況，回到步驟④，分別進行處理。
Step5. 當每個網格被劃分到相應的簇中，我們就將其在隊列q中刪去；每進行一次二分，我們就將新分出的網格加到隊列q中。這樣，隊列q中存放的一直都是未被訪問的網格。每當一個符合要求的簇劃分出來之后，我們就會再在隊列q中再取其頭上的網格，回到步驟③，開始進行下一個簇的劃分。當隊列q為空時，則代表圖像上所有的網格都已經被劃分到了相應的簇中。
Step6. 取出每個網格的屬性T，不同的T值代表該網格屬于不同的簇，將T值相同的網格涂上相同的顏色，則圖像被劃分為不同的簇，并且每個簇內含有的點的數目相等。
3實例仿真
在平面上隨機畫若干個點來驗證此算法[13]，以點的數目120為例，我們要將其分為6個簇，每個簇內要包含20個點。在程序的運行時，有的圖像不需要對網格進行二分，在劃分完網格之后，只需要將網格跟它的鄰居網格合并起來就可以得到6個均勻簇。這是程序復雜度最低的情況，此種情況下，程序的運行結果如下圖所示。
這種復雜度最低的情況在實際中是比較少見的。通常情況下，對圖像進行處理時，都需要對網格進行二分操作，如下圖所示。
由以上兩個運行結果可以看出，該算法不僅按照位置靠近的原則將點聚到相應的簇中，而且保證了劃分成的6個簇內含有數目相同的點，證明了該算法的有效性。
4 結論和展望
本文提出的基于網格的均勻簇劃分算法在效率上和實際應用中有著獨特的優勢。例如，在某市一家通信公司選取基站位置的時候，假設一個基站的通訊容量是15萬人，該市的人口是150萬。我們就可以根據此算法，將該市的人口按照地理位置相近的原則分為10個區，每個區的人口數都是15萬。這樣，通訊公司只需要在每個區的中心建立一個基站，既保證了提供優質的通信服務，又減少了基站給人們的輻射，同時降低了通信成本。不過，此算法在某些方面仍存在不足和改進之處：
· 在實際應用中，若某些網格內含有的對象數目特比多，則在程序的運行中需要對該網格進行多次二分，此時程序的復雜度會較高。
· 可以考慮和別的方法，如基于密度的聚類法結合起來實現均勻簇的劃分。
參考文獻(References)
[1] Han Jianwei, Micheline Kambr. Data Mining: Concepts and Techniques[Z], 2001
[2] A.K.JAIN. Data Clustering: A review[M]: ACM Computering Surveys, 1999, (9)
[3] Anil K.Jain, Robert P.W, Jianchang Mao. Statistical Pattern Recognition: A Review: IEEE transaction on pattern analysis and machine intelligence[J], vol. 22, NO.1, January 2000:P4-37
[4] KAUFMAN L, ROUSSEEUW PJ. Finding groups in data: An introduction to cluster analysis [M]. New York: John Wiley & Sons, 1990
[5] Julio F. Navarro, Carlos S. Frenk, Simon D.M.White, A universal density profile from hierarchical clustering [J]. The astrophysical journal, 1997, 12, P493-508
[6] SUDIPTO G, RASTOGI R, SHIM K Cure: An efficient clustering algorithm for large database [J].Proceedings of the ACM SIGMOD international conference on Management of data [M]. New York: ACM Press, 1998: P73-84
[7] Wei-keng, Ying liu, Alok Choudhary. Agrid-based Clustering Algorithm using Adaptive Mesh refinement[J].Mining Scientific and Engineering Datasets, 2004,7: P1-9
[8] AGRAWAL R, GEHRKE J, GUNOPULOS, et al. Automatic subspace clustering of high dimensional data for mining applications [A]. Proceedings of the ACM SIGMOD international conference on Management of data[C]. New York: ACM Press, 1998.P94-105
[9] Pandeng, Zhengyingping, Xulilong, Chenjun.Grid method of data clustering based on RBF neural networks[J].Computer Application, 2007, (2): P333-336.
潘登, 鄭應平，徐立鴻，陳俊. 基于RBF神經網格的網絡數
據聚類方法[J].計算機應用, 2007, (2): P333-336
[10] Yangfan, mihong.one method of data clustering method applying in subdivision[J].Science of Surveying and mapping,2007
楊帆，米紅.一種基于網格的聚類方法在區域劃分中的應用
[J].測繪科學，2007
[11] Yue Shihong, Wang Zhengyou. Bisecting Grid-Based Clustering Approach and Its Validity[J].Journal of Computer Research and Development, 2005,42(9):P1505-15010
[12] Wangxiaodong. Algorithm design and analysis [M].Beijing:
Tsinghua University Press, 2003
王曉東.算法的設計與分析 [M].北京: 清華大學出版社, 2003
[13] Xuedingyu. Scientific Computation language MATLAB5.3 Program design and application [M].Beijing: Tsinghua press, 2000
薛定宇.科學運算語言MATLAB5.3程序設計與應用 [M].北京：清華大學出版社，2003
作者簡介：
解靜，2004年9月進入山東大學計算機科學與技術專業學院進行本科學習。本科期間成績突出，表現優秀，于2008年9月被保送為本校該專業的研究生。師從石冰教授，主要研究方向為數據庫和數據挖掘等。
