PQR*TDBSCAN改進算法

摘要:DBSCAN是基于密度的聚類算法的一個典型代表。但是DBSCAN算法在處理大規模數據庫時，存在很大欠缺。PQR*TDBSCAN是針對DBSCAN算法內存使用過大、I/O消耗過多等方面提出的，但是在實際應用中發現存在異常掛死的可能。本文針對PQR*TDBSCAN的缺陷進行了改進。測試表明，本算法在處理海量數據過程中降低了DBSCAN對時間和空間的需求。

關鍵詞:DBSCAN;數據分區;QR*樹;并行計算

中圖分類號:TP311文獻標識碼:A 文章編號:1009-3044(2010)05-1035-03

AN Improve Algorithm based PQR*TDBSCAN

WANG Hong， XU Fan， CUI Hong-jing， XU Hui

(Computer College.，Shandong Xiehe Vocational and Technical College， Jinan 250107， China)

Abstract: DBSCAN algorithm is an outstanding representative of density based on clustering algorithms. However， there are some defects when dealing with large-scale database. Aiming at requiring large volume of memory support and needing a lot of I/O costs， a PQR*TDBSCAN algorithm is presented. But actually there is the possibility of making the algorithm goes to the abnormal status. In this paper， a PQR*TDBSCAN improve algorithm is presented. Experimental results show that the new algorithm is superior to the original DBSCAN in efficiency.

Key words: DBSCAN; data-partitioning; QR*-tree; parallel computing

隨著信息技術的高速發展，數據庫應用的規模、范圍和深度的不斷擴大，導致積累了大量的數據，而這些激增的數據后面隱藏著許多重要的信息，因此人們希望能夠對其進行更高層次的分析，以便更好地利用這些數據。日前的數據庫系統可以高效、方便地實現數據的錄入、查詢、統計等功能，但是在發現數據中存在的各種關系和規則方面還是比較薄弱。聚類(clustering)是數據挖掘領域中的一個重要課題。它將數據庫中的數據劃分成具有一定意義的子類，使得不同子類中的數據盡可能相異而同一子類中的數據盡可能相同。迄今為止，人們提出了許多數據聚類的算法，像CLARANS，BIRCH，DBSCAN，CURE，STING，CLIQUE和Wavecluster等等。所有這些算法都試圖解決大規模數據庫的數據聚類問題。

基于數據分區、QR*-樹的并行DBSCAN算法PQR*TDBSCAN，即根據數據的空間分布特性，將整個數據空間劃分為多個較小的分區，然后對這些局部分區使用QR*-樹建立空間索引，再進行聚類，最后將各局部聚類進行合并。但是該算法在實際應用過程中針對某一類數據庫無法尋找找到分類方法時會進入到異常掛死的狀態，本文針對PQR*TDBSCAN算法的這個問題提出了PQR*TDBSCAN改進算法。經過實際應用在遇到異常掛死的情況下程序在進行了m次比較后就會停止，防止程序掛死，同時在使用不同分區時使用不同的Eps，可以達到更好的聚類效果，但是該程序的效率與PQR*TDBSCAN基本相同。

1 DBSCAN 及 PQR*TDBSCAN算法模型

Ester Martin 等人提出的 DBSCAN 算法是一種基于密度的空間數據聚類方法， DBSCAN算法采用了一種查找密度可達對象的方法進行聚類分析。DBSCAN算法的正確性由下述事實保證:一個簇與由簇中任意核心對象密度可達的所有對象構成的集合O是等價的。DBSCAN算法采用迭代查找的方法。通過迭代查找所有直接密度可達的對象。找到各個簇所包含的所有密度可達的對象。

PQR*TDBSCAN算法思想是:根據數據庫在某一維的分布特性，將整個數據庫劃分為若干個交集為空的局部區域;然后將每個局部數據庫分別送入一個處理單元中，以每個處理單元為基礎建立QR*-樹，用基于QR*-樹的DBSCAN算法進行聚類(種子點的選取過程中把與核心點的距離在0.6Eps到Eps范圍內的點作為種子點);最后將所得到的聚類結果按照合并規則進行合并。PQR*TDBSCAN的算法具體描述是:

對于一個給定數據庫D和MinPts、參數Eps(由k-dist 圖得到)，D中任意元素E有m維(E1，E2，…，Em)，把D分成n個數據量大致相同的分區，步驟如下:

1) 取任意整數i(1≤i≤m)，把數據庫D投影到第i維上，即任意E∈D，E→Ei，則數據庫D映射為一個一維數據集Di，即Di={Ei|E(E1，E2，…Em)∈D};

2) 令A，B分別為數據集Di的下限和上限，則數據集分布在區間[A，B]內;

3) 找到數列a0，a1，…，an，滿足:A=a0

4) 如果分區結果滿足步驟(3)，則轉到步驟(6);

5) 如果分區結果不滿足步驟(3)，則轉到步驟(1);

6) 把分區結果進行簡單的冗余處理， 即把步驟(3)的分區區間修改為:[a0，a1+Eps]，[a1-Eps，a2+Eps]，…，[ai-Eps，ai+1+Eps]，…，[an-1-Eps，an]，(i=1，2，…，n-2)。 為了闡述方便，將修改后的分區定名為C1，C2，…，Cn ;

7) 把Ci發送到第i個處理機內存中，(i=1，2，…，n);

8) 每一個處理機節點用基于QR*-樹DBSCAN算法對本地數據進行聚類(以第i個分區為例):

①對于給定的分區Ci構建QR*-樹;

②)初始化每個點為沒有處理過的、初始化種子點隊列(seeds)為空、初始化結果集(results)為空;

③定義第一個簇的類標簽(ID)為1;

④取得分區Ci第一個點進行聚類;

⑤對在步驟I中建立好的QR*-樹，進行點的區域查詢，并且返回區域查詢的結果點數;

⑥根據MinPts判斷這個點是否是核心點，如果不是核心點就先記為噪聲點(Noise);如果是核心點則將所有的點標記上當前的ID，然后從與核心點的距離在0.6Eps到Eps范圍內的點集(Fseeds)中找出下一個點再進行步驟V，將已經處理過的點從Fseeds中刪除，直到Fseeds為空;

⑦取得分區Ci的下一個點進行聚類，并將類標簽(ID)增加1，直到取道Ci分區的所有點;

⑧基于QR*-樹DBSCAN算法結束。

9) 聚類合并，對于處理機i(1≤i≤n-1):把Ci內數據的聚類信息發送到第i+1個處理機，與Ci+1內數據的聚類信息進行比較，如果某點z分別屬于類1和類2，若z至少有一次為核心對象，則類1和類2合并為一個類;如果某點z在類1、2中都是邊界點，則z可以屬于類1或類2，但類1和類2不能合并;如果z有一次屬于類1，而另一次是噪聲點，則z屬于類1;如果z點兩次都為噪聲點，z在全局聚類中就是噪音點;

10) 算法結束。

2 PQR*TDBSCAN改進算法

2.1 算法思想

PQR*TDBSCAN改進算法思想是:根據數據庫在某一維的分布特性，將整個數據庫劃分為若干個交集為空的局部區域，如果在進行m次的尋找劃分方法的過程中仍然沒有找到，程序停止運行;然后將每個局部數據庫分別送入一個處理單元中，以每個處理單元為基礎建立QR*-樹，用基于QR*-樹的DBSCAN算法進行聚類，同時每個聚類使用自己的Eps(種子點的選取過程中把與核心點的距離在0.6Eps到Eps范圍內的點作為種子點);最后將所得到的聚類結果按照合并規則進行合并。

2.2 算法描述

對于一個給定數據庫D和MinPts、參數Eps(由k-dist 圖得到)，D中任意元素E有m維(E1，E2，…，Em)，把D分成n個數據量大致相同的分區，步驟如下:

1) 取任意整數i(1≤i≤m)，把數據庫D投影到第i維上，即任意E∈D，E→Ei，則數據庫D映射為一個一維數據集Di，即Di={Ei|E(E1，E2，…，Em)∈D};在投影過程中應用數據集的分區算法Partition算法進行數據集的劃分;取一變量tmp，賦初始值為m;

2)令A，B分別為數據集Di的下限和上限，則數據集Di分布在區間[A，B]內;

3)找到數列a0，a1，…，an，滿足:

A=a0

4)如果分區結果滿足步驟3)，則轉到步驟6);

5)如果分區結果不滿足步驟3)且tmp>1，則tmp=tmp-1，轉到步驟1);如果分區結果不滿足步驟3)且tmp≤1，則轉到步驟10);

6)把分區結果進行簡單的冗余處理，即把步驟(3)的分區區間修改為:[a0，a1+Eps]，[a1-Eps，a2+Eps]，…，[ai-Eps，ai+1+Eps]，…，[an-1-Eps，an]，(i=2，3，…，n-2)。為了闡述方便，將修改后的分區分別定名為C1，C2，…，C i+1，…，Cn;

7)把Ci發送到第i個處理機內存中，(i=1，2，…，n);

8)每一個處理機結點用基于QR*樹DBSCAN算法對本地數據進行聚類(以第i個分區為例):

①對于給定的分區Ci構建QR*樹;

②對于給定的分區Ci計算k-dist圖，得到Epsi;

③初始化每個點為沒有處理過的、初始化種子點隊列(seeds)為空、初始化結果集(results)為空;

④定義第一個簇的類標簽(ID)為1;

⑤取得分區Ci第一個點進行聚類;

⑥對在步驟I中建立好的QR*樹，進行點的區域查詢，并且返回區域查詢的結果點數;

⑦根據MinPts判斷這個點是否是核心點，如果不是核心點就先記為噪聲點(Noise);如果是核心點則將所有的點標記上當前的ID，然后從與核心點的距離在0.6Epsi到Epsi范圍內的點集(Fseeds)中找出下一個點再進行步驟(5)，將已經處理過的點從Fseeds中刪除，直到Fseeds為空;

⑧取得分區Ci的下一個點進行聚類，并將類標簽(ID)增加1，直到取到Ci分區的所有點;

⑨基于QR*樹DBSCAN算法結束。

9)聚類合并，對于處理機i(1≤i≤n-1):把Ci內數據的聚類信息發送到第i+1個處理機，與Ci+1內數據的聚類信息進行比較，如果某點z分別屬于類Ci和類Ci+1，且在Ci、Ci+1中均為核心點，則類Ci和類Ci+1合并為一個類;某點z分別屬于類Ci和類Ci+1，且一次為核心點，而另一次為邊界點，則類Ci和類Ci+1合并為一個類;如果某點z在類Ci、Ci+1中都是邊界點，則z可以屬于類Ci或類Ci+1，但是類Ci和類Ci+1不能合并;如果z有一次屬于類Ci，而另一次是噪聲點，則z屬于類Ci;如果z點兩次都為噪聲點，z在全局聚類中就是噪聲點;

10)算法結束。

3性能評估

測試系統用JAVA語言開發。實驗的硬件環境是50臺 Pentium4 3.0G CPU，1024M內存、160G硬盤，軟件環境是windows XP Sp2操作系統、Jbuilder8集成開發環境。同時，系統使用SQL Server 2000作為數據庫，使用“SQL Server 2000 Driver for JDBC”作為數據庫驅動程序。

首先要驗證的是PQR*TDBSCAN改進算法在改進聚類質量上的優勢。本文在評估聚類質量方面與周水庚的PDBSCAN相比較，測試例子如圖1，比較結果如表1。從表1中可以看出PQR*TDBSCAN改進算法在聚類質量上要優于DBSCAN算法，聚類的質量與PDBSCAN相同，即在聚類質量上PQR*TDBSCAN改進算法與PDBSCAN等價。

接下來要對PQR*TDBSCAN改進算法的時間性能進行評估。圖2為DBSCAN、PDBSCAN、PQR*TDBSCAN和PQR*TDBSCAN改進算法的一組測試結果。由圖2可以看出PQR*TDBSCAN改進算法的時間效率比較高，并且當數據量增加的時候他的增幅比較小，可以得出PQR*TDBSCAN改進算法要優于PDBSCAN算法和DBSCAN算法。

5 結束語

本算法與前述提到的DBSCAN的改進算法相比較，可以看出本算法的優勢在于以下幾個方面:

1) 緩解了串行DBSCAN算法因數據規模過大內存需求緊張局面;

2) 通過使用多處理器、多個Eps、QR*-樹作為空間索引結構，最大化提高了算法的運算速度并改善了聚類質量;

3) 通過使用環形區域種子點的查找，使要接受查詢的種子點減少，在不改變聚類質量的情況下，提高了算法的運算速度。

但是本算法存在的主要缺點是對于增量式算法的支持力度不夠，對于這方面的改進將是接下來研究的主要方向。

參考文獻:

[1] 張健沛，許慧，楊靜，崔洪晶.基于數據分區、QR~*-樹的并行DBSCAN算法[A].2006北京地區高校研究生學術交流會——通信與信息技術會議論文集(下)，2006.

[2] Ester M， et al. A density-based algorithm for discovering clusters in large spatial databases with noise. In: Proc of 2nd Int'l Conf on Knowledge Discovering in Databases and Data Mining (KDD-96). Portland: AAAI Press， 1996

[3] ZHOU Shui-Geng， ZHOU Ao-Ying， and CAO Jin. A Data-Partitioning-Based DBSCAN Algorithm [J]. Journal of Computer ResearchDevelopment， 2000， (10):1153-1159.

[4] 邱建華，唐學兵，黃華國.一種基于四叉樹和R*-樹的索引結構--QR*-樹[J].計算機應用，2003，Vol.23， No.8: 124-126，152.

[5] LUAN Li-hua， JI Gen-lin. Fast clustering algorithm based on Quad-tree [J]. Computer Applications，2005，Vol.25，No.5:1001-1003.

[6] QIAN WN， ZHOU AY. Analyzing Popular Clustering Algorithms from Different Viewpoints [J].Journal of Software， 2002，13(8):1382-1394.