大規模數據集聚類中的數據分區及應用研究

摘 要：針對大型數據庫提出了許多聚類方法，但是這些算法往往計算量較大、對主存的要求較高；而且當數據分布不均勻時，算法的聚類質量會受影響。因此為了提高聚類算法的效率和準確性，采用了數據分區技術首先對數據進行預處理，分區后的數據具有更少的數據量和更均勻的數據分布。

關鍵詞：數據挖掘；聚類；數據分區；并行聚類

中圖法分類號：TP391.4文獻標識碼：A

文章編號：1001—3695(2007)02—0203—03

近十幾年來，人們利用信息技術生產和搜集數據的能力大幅度提高，千萬個數據庫被用于商業管理、政府辦公、科學研究和工程開發等。要想使數據真正成為一個公司的資源，只有充分利用它為公司自身的業務決策和戰略發展服務才行，否則大量的數據可能成為包袱，甚至成為垃圾。因此，面對人們被數據淹沒卻饑餓于知識的挑戰，數據挖掘和知識發現技術應運而生，并得以蓬勃發展，越來越顯示出其強大的生命力。聚類是數據挖掘中一種重要的挖掘任務和挖掘方法，它從數據庫中尋找數據間的相似性，并依此對數據進行分類，使不同類中的數據盡可能相異，而同一類中的數據盡可能相似，即物以類聚，從而優化大規模數據庫的查詢并發現數據中隱含的有用信息或知識。聚類分析問題可描述為：給定m維空間Rm中的n個向量，把每個向量歸屬到S聚類中的某一個，使得每個向量與其聚類中心的距離最小。聚類分析問題的實質是一個全局最優問題。在這里，m可認為是樣本參與聚類的屬性個數，n是樣本的個數，S是由用戶預先設定的分類數目。

數據聚類在很多領域中有著廣泛的應用，如模式識別、圖像處理、數據壓縮、空間數據分析、市場研究、WWW（WWW上的文本分類；對Web的日志數據聚類后發現相似的訪問模式）等。迄今為止，人們提出了許多聚類算法，這些算法都試圖從不同的途徑實現對數據集進行高效、可靠的聚類。例如分割的方法、層次的方法、基于密度的方法、基于網格的方法和基于模型的方法。但是由于在對大型數據庫進行聚類時，很多算法都需要計算兩點之間的距離，如系統聚類法、動態聚類法[1]，因此處理大樣本時系統開銷較大；另一方面，有些算法參數的選擇對初始數據分布比較敏感，數據的分布可能會影響聚類質量，如DBSCAN算法[2，3]。所以很有必要對數據作預處理，預處理一方面使數據能夠有規則地縮減；另一方面使數據分布盡可能均勻，本文采用了數據分區作為數據的預處理方法。使用分區技術后，只需對每個數據分布較均勻的區域進行局部聚類而不是對整個數據進行一次聚類，以此來減少聚類對象的規模，降低內存負擔。此外，還可以把各個區域分配到不同的處理機上進行并行聚類，最后進行類的合并，以此來提高聚類效率。

1 數據分區

數據分區是基于數據統計分布特性來對數據進行分區的。根據數據在多維上的分布特性，把數據空間劃分成一個個小區域，使每個區域的數據分布盡可能均勻。然后對每個分區采用聚類算法，最后把各個局部聚類合并。分區過程使用了五種內部聚集函數：count( )，sum( )，avg( )，max( )，min( )。這些函數在數據立方體中也可以進行有效的計算。在數據的分區中，我們就可以利用這些函數來進行數據分布特性的統計。為了更清楚地描述分區過程，首先給出了步長密度的概念：它指在一個度量長度內的點數除以整個樣本數據中的點數。

在分區中我們使用了直方圖來確定數據分布的密度情況。直方圖由一組矩形組成，這些矩形反映了落在給定區間內的點數占總的樣本數據的多少。在畫直方圖之前，首先要確定分組數和數據樣本點中的最大值和最小值，最大值和最小值可以使用內部聚集函數求出，而組數的值不宜過大或過小，如果組數取得過大則有的區間內沒有樣本觀測值；過小則無法看出數據點的分布情況。組數和數據點之間一般應該滿足如下關系：

對于數據分布圖，我們可以穿過每個矩形上邊的中點順次連接成一條曲線，從這條曲線可以看出數據點的密度分布情況。為了避免把一個類分裂成多個類，我們在兩個相鄰波峰之間的波谷位置選擇劃分點，即數據分布最稀疏的位置來確定劃分點。在劃分中，我們給定一個閾值λ，用來決定是否需要在相鄰兩個波峰之間確定一個劃分點，用向量（L₁，S₀，L₂）來存儲相鄰的兩個最大值點L₁（波峰）和L₂（波峰）以及相鄰兩個波峰之間的波谷S₀，當| L₁- L₂|>λ時，就在S₀所對應的坐標軸上的點處進行劃分，所有這些坐標軸上的點構成集合S，因此S中存儲了所有的劃分點。從圖1中的曲線可以看出X₁，X₂為相鄰的兩個波峰值，而且這兩個波峰值相差較大，因此可以在波谷位置確定劃分點為xp 。分別對X，Y軸作這個劃分步驟，確定劃分點。從圖中我們可以看出并不是所有的情況都需要進行數據劃分，當發現數據的分布密度相差不大時，就不需要進行劃分（連續分布時）。

當出現下面三種情況時：①數據分布密度是一條直線；②數據分布密度呈現遞增的情況；③數據分布密度呈現遞減的情況。說明相鄰區域內的數據分布密度較一致，不存在數據分布較稀疏的區域（邊界區域除外），這時需要把兩個維上的數據劃分結合起來考慮，并根據處理機數目進行數據劃分。假設處理機數目為N個，在某一維上劃分了Ki(i=X or i=Y)個區域，另一維上平均劃分成N/ Ki個區域。

如果不是這三種情況，就需要用前面介紹的閾值進行確定。需要說明的是，當出現互相包含的環狀類和互相纏繞的螺旋狀類時，使用這種簡單的投影到X，Y軸的方法并不見效。

2 實驗結果

我們對圖4中的數據對象采用DBSCAN算法進行聚類分析。DBSCAN算法使用基于密度的聚類概念，即要求聚類空間中一定區域內所包含對象的數目不小于某一給定的閾值MinPts。DBSCAN算法的顯著優點是聚類速度快，且能夠發現任意形狀的聚類并有效地處理噪聲點，但是它也存在如下一些缺點：

(1)由于其算法是直接對整個數據庫進行聚類，需要把所有數據載入內存，因此當數據量很龐大時對主存要求較高。

(2)由于在DBSCAN算法中定義了一個全局變量Eps，因此當數據分布不均勻時聚類質量較差。若根據較密的那些類來選取較小的Eps值，那么對于客觀上相對較稀的那些類中的對象，其鄰域中數據對象的數目將可能小于MinPts，也就是說這些對象將被認為是噪聲點，從而不被用于所在類的擴展，因此較稀的類被分成多個性質相似的類；與此相反，若根據較稀的那些類來選取較大的Eps值，那么離得較近而且密度較大的那些類將很可能被合并為同一個類，它們之間的差異也就因為選取較大的Eps值而被忽略。很明顯，在上述兩種情況下，其實很難選取一個合適的Eps值來進行聚類且得到比較準確的聚類結果。

在圖2中，Eps值的選取即為畫出的圓的半徑。從圖中可以看出，圖2(a)圓內的數據對象分布較稀疏，而圖2(b)圓內的數據對象分布比圖2(a)要密集。DBSCAN算法使用的是統一的全局變量Eps，如果根據l圖2(a)數據分布較稀疏的類C₃來選取Eps（MinPts=5）值，那么圖2(b)相鄰比較近的兩個類C₁，C₂就會由于選取的Eps值較大而合并成為一個類。

以上出現的兩種情況都是由于Eps值的選取不適當引起的，因為Eps是一個全局變量，很難同時考慮各種數據分布情況。這種情況當數據分布密度不均勻時尤其突出。

分別對這三個區域進行聚類，聚類結果如表1所示。

如果使用統一的Eps，則聚類結果如表2所示。

3 結束語

聚類分析是數據挖掘中的一個重要內容，如何進行有效、可靠、穩定的聚類，一直是聚類研究的主要內容。本文把并行思想結合到聚類算法中，提出了對數據采用分區技術首先進行預處理的思想。這種方法縮小了聚類規模，提高了聚類效率，減小了內存開銷。隨著數據庫規模的日益增加和人們對效率要求的提高，并行聚類將是一種行之有效的方法，而數據分區為我們實現高效的并行聚類奠定了基礎。因此，今后的工作是開發高效的并行聚類。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。