一種新的基于網格壓縮的聚類算法ＳＧＲＩＤＳ研究

摘 要:引入了一種新的基于網格的數據壓縮方法，并應用該方法對處理大型空間數據集的聚類算法SGRIDS進行研究。該方法考慮輸入參數對聚類算法質量有較大影響，對密度閾值的確定進行了改進，從而減小輸入參數的影響。實驗證明，該方法能夠獲得較好的聚類效果。

關鍵詞:聚類分析; 聚類算法; 基于網格的數據壓縮; 算法SGRIDS

中圖分類號:TP311文獻標志碼:A

文章編號:1001-3695(2009)09-3274-02

doi:10.3969/j.issn.1001-3695.2009.09.020

Research of new clustering algorithm SGRIDSbased on grid data compression

ZHAO Hui， LIU Xi-yu

(College of Management Economic， Shandong Normal University， Jinan 250014， China)

Abstract:By introducing a new grid-based data compression framework， conducted the study on the clustering algorithm SGRIDS which dealed with a large spatial databases. Considering that the input parameter has a great impact on the quality of clustering algorithms， improved the settlement of the value for density threshold， decreased the impact of input parameter， thus attaining a better clustering effect.

Key words:cluster analysis; clustering algorithms; grid-based data compression; algorithm SGRIDS

隨著計算機硬件和軟件技術的飛速發展，尤其是數據庫技術的普及，人們面臨著日益擴張的數據海洋，原來的數據分析工具已無法有效地為決策者提供決策支持所需要的相關知識，從而形成一種獨特的現象“豐富的數據、貧乏的知識”。數據挖掘[1]又稱為數據庫中知識發現(knowledge discovery from database，KDD)，它是一個從大量資料中抽取挖掘出未知的、有價值的模式或規律等知識的復雜過程。其目的在于大量的資料中發現人們感興趣的知識。

常用的數據挖掘技術包括關聯分析、異類分析、分類與預測、聚類分析以及演化分析等。聚類分析作為一種常用的數據挖掘方法得到了廣泛的應用。

1 聚類演算法分析

1.1 常見聚類算法

聚類[2]分析是直接比較各事物之間的性質，將性質相近的歸為一類，將性質差別較大的歸為不同的類。目前，聚類分析已經被廣泛地應用到許多領域中，包括模式識別、數據分析、圖像處理以及市場研究等[3]。在商務上，聚類能夠幫助市場分析人員從客戶基本庫中發現不同的客戶群;在生物學上，聚類用于推到植物和動物的分類，對基因進行分類;聚類也能對Web上的文檔進行分類等。

大體上，聚類算法[4]劃分為如下幾類:

a)劃分方法。給定一個包含n個對象或數據行，劃分方法將數據集劃分為k個子集(劃分)。其中每個子集均代表一個聚類(k≤n)。代表算法為K-means算法、K-medoids算法等。

b)層次方法。該方法就是通過分解所給定的數據對象集來創建一個層次。它存在的缺陷就是進行(組)分解或合并之后無法回溯。將循環再定位與層次方法結合起來使用常常是有效的，如BIRCH和CURE就是基于這種組合方法設計的。

c)基于密度的方法。只要鄰近區域的密度(對象或數據點的數目)超過某個閾值，就繼續聚類。

d)基于網格的方法。該方法是將對象空間劃分為有限數目的單元以形成網格結構。在大部分基于網格方法的聚類算法中，所有的聚類操作都在網格數據結構上進行，網格中的數據壓縮質量就決定了算法的聚類質量。本文在學習新的基于網格的數據壓縮方法前提下，研究了處理大型空間數據集的聚類算法。

e)基于模型的方法。該方法就是為每個聚類假設一個模型，然后再去發現符合相應模型的數據對象。它根據標準統計方法并考慮到噪聲或異常數據，可以自動確定聚類個數，因而它可以產生很魯棒的聚類方法。

上述方法各有特點，在不同的領域以及數據特點下發揮了不同的作用，實現了數據的有效聚類。但是，面對目前巨大的空間數據庫則明顯顯示出其不足。為此，需要探討空間數據挖掘的新方法，實現空間數據聚類。

1.2 空間數據聚類

衛星圖像、攝影、醫學器械、地理信息系統等各種應用獲取的空間數據量十分巨大，由人工來詳細分析這些資料非常昂貴，甚至是不可能的。空間數據聚類的任務是發現數據中自然存在的簇。空間數據指的是二維空間或三維空間中的點、多邊形以及d-維空間中的點[5]。對空間數據進行聚類分析是一個熱點研究問題。

空間數據庫的典型特征是規模大且數據分布不規則。對于無法全部裝入內存的大型空間數據集，基于劃分的CLARANS[6]和基于密度的DBSCAN[7]要求對資料集的隨機存取或多遍掃描的代價非常昂貴，而網格方法的壓縮功能和它能發現任意形狀簇的能力使得基于網格方法的聚類算法特別適用于處理大型空間數據庫，算法STING[8]和算法WaveCluster[9]都是成功的基于網格方法的空間數據聚類算法。

本文學習了一個新的基于網格的數據壓縮方法，對能處理大型空間數據集的聚類算法SGRIDS(a scalable GRID-based clustering algorithm for very large spatial databases)[10]進行了研究改進及實驗分析。

2 基于網格的聚類算法SGRIDS及改進

2.1 基于網格的數據壓縮方法[11]

首先將空間數據均勻劃分為中等粒度的網格，然后計算每個網格單元所包含的數據點數目。網格單元內數據的密度定義為它包含的數據點數目除以網格單元的體積。起初，讀入的數據和網格單元都被保存到內存中。設密度閾值τ是一個位于網格單元數據密度最大值與最小值之間的值。若一個網格單元密度超過τ，它被稱為一個高密度網格單元。相鄰的高密度網格單元被合并，形成大的高密度區域。為方便計算，只有形成矩形區域的合并才被允許。包含在每個高密度區域內的數據點數目及其均值被保存下來，數據點被丟棄。未被合并的網格單元內的數據點都被直接保存在內存中。最后，內存中保存的數據點為高密度區域、未被合并的網格單元以及落入這些網格單元內的數據點。

2.2 算法SGRIDS改進

算法SGRIDS中關于密度閾值τ的確定，采用如下方法:

找到每個網格單元的數據點個數count>0的網格單元的最大密度值dmax和最小密度值dmin。密度閾值τ=dmin+(dmax-dmin)×ε。若一個網格單元的count≥τ，它被稱為一個高密度網格單元。參數ε取經驗值[0，1]，其取值對算法影響較大。因此，本文對算法中τ的取值作改進，并進行了實驗分析。

以下為改進后的算法SGRIDS。

輸入:數據集，網格劃分參數ξ，控制數據壓縮周期的參數p。

輸出:帶簇標志的不均勻劃分的網格。

a)將數據空間的每維均勻劃分為ξ段以構建初始的網格單元。

b)讀入部分數據，將它們投影到網格數據結構中，計算每個網格單元包含的數據點個數count。

c)找到count>0的網格單元密度值di，按從小到大的順序排列，算計xn=di1-di2，找到最大的密度差xmax，取此時的τ=di2。若一個網格單元的count≥τ，它被稱為一個高密度網格單元。

d)將相鄰的高密度網格單元合并，形成較大的矩形區域，計算這些區域內數據點的數目和均值。將區域內的數據點從內存中刪除。

e)讀入一個新的數據點，若它落入某個區域，修改此區域的count與均值，將次數據點丟棄;若它落入區域外的網格單元，修改此網格單元的count，并將次數據點保存在內存。

f)若d)執行后，該步已讀入p個數據點，轉入c)。

g)若數據集中還有數據未讀入，轉入e)。

h)執行c)和d)。

i)將區域標志為簇，相連的區域屬于同一個簇。

j)給內存中的數據分配簇標志。數據點被分配給離它最近的區域所屬的簇。

2.3 實驗分析

本文采用的實驗支持系統是MODE-CES [12]，系統主界面如圖1所示。

實驗系統用C#語言開發。實驗的軟件環境是Windows XP Professional操作系統、Microsoft Visual Studio .NET 2003集成開發環境，使用SQL Server 2000作為數據庫，使用SQL Server 2000 Driver for ODBC作為數據庫驅動程序;硬件環境是Intel Pentium 4的CPU，512 MB內存80 GB硬盤。

數據集DS如圖2所示。在圖2中，顯示的黑色區域為數據集DS，此數據集使用文獻[9]中生成數據集DS4的方法生成。

下面將以本文研究的SGRIDS算法對圖2中的數據集進行聚類分析:

a)讀入要進行聚類分析的數據源;

b)選擇聚類算法，并輸入算法需要的參數;

c)點擊“開始聚類”按鈕進行聚類分析，聚類完成后將彈出一個關于聚類耗時與聚類有效性指數的對話框;

d)查看聚類結果。

圖3顯示的是圖2數據集DS在改進算法下的聚類結果。采用原演算法分析使用不同的ε值處理圖2的數據源DS時得到的簇的數目如表1所示。

表1 使用不同的ε值，得到的簇的數目(ξ=75，p=20 000)

ε0.30.40.50.60.7

簇的數目22222

對于簇內數據為均勻分布的數據集DS，只有ε<0.6，算法才能成功識別出數據集中的兩個簇，而改進后的算法可以很好地識別出數據集中的兩個簇。

3 結束語

本文針對基于網格的方法能較好地處理空間數據聚類問題，引入新的基于網格的數據壓縮方法，提高了壓縮質量。同時，針對處理大型空間數據集的聚類算法SGRIDS進行研究，對密度閾值的確定進行改進。實驗證明，改進后的算法在不利用經驗參數的情況下仍能很好地聚類。

參考文獻:

[1]朱明.數據挖掘[M].合肥:中國科學技術大學出版社，2002:5-6.

[2]邵峰晶，于忠清.數據挖掘的原理與算法[M].北京:中國水利水電出版社，2003.

[3]張敏，于劍.基于劃分的模糊聚類算法[J].軟件學報，2004，15(6):858-859.

[4]HAN Jia-wei， KAMBER M. Data mining concepts and techniques[M].范明，孟小峰，等譯.北京:機械工業出版社，2002.

[5]SHEIKHOLESLAMI G， CHATTERJEE S， ZHANG Ai-dong. Wavecluster: a wavelet-based clustering approach for spatial data in very large databases[J]. The International Journal on Very Large Data Bases， 2000，8(3-4):289-304.

[6]NG R T， HAN Jia-wei. efficient and effective clustering methods for spatial data mining[C]//Proc of the 20th International Conference on Very Large Data Bases. San Francisco， CA:Morgan Kaufmann Publishers，1994:144-155.

[7]ESTER M， KRIEGEL H P， SANDER J， et al. A density-basef algorithm for discovering clusters in large spatial databases with noise[C]//Proc of the 2nd International Conference on Knowledge Disco-very and Data Mining. Portiand， Oregon:AAAI Press， 1996:226-231.

[8]WANG Wei， YANG Jiong， MUNTZ R. STING:a statistical information grid approach to spatial data mining[C]//Proc of the 23rd VLDB Conference. San Francisco， CA:Morgan Kaufmann Publishers， 1997:186-195.

[9]SHEIKHOLESLAMI G， CHATTERJEE S， ZHANG Ai-dong. Wavecluster: a multi-resolution clustering approach for very large spatial databases[C]//Proc of the 24th VLDB Conference. New York:[s.n.]， 1998:428-438.

[10]SUN Yu-fen， LU Yan-sheng. A scalable GRID-based clustering algorithm for very large spatial databases[C]//Proc of International Conference on Computational Intelligence and Security.2006:763-768.

[11]孫玉芬.基于網格方法的聚類算法研究[D].2006:45-48.

[12]曾東海，米紅.基于網格密度和空間劃分樹的聚類算法研究[D].2006:59-60.