基于密度的并行聚類算法

1、 8基于密度的并行聚類算法陳 敏 1,高學(xué)東 1,欒紹峻 1,郗玉平 2(1. 北京科技大學(xué)經(jīng)濟(jì)管理學(xué)院,北京 100083; 2. 北京信息職業(yè)技術(shù)學(xué)院汽車工程系,北京 100015摘 要:為滿足大規(guī)?？臻g數(shù)據(jù)庫(kù)的聚類需求,面向計(jì)算機(jī)集群,提出一種基于密度的并行聚類算法。該算法根據(jù)數(shù)據(jù)庫(kù)分布特征進(jìn)行數(shù) 據(jù)分區(qū), 在每一個(gè)節(jié)點(diǎn)上對(duì)數(shù)據(jù)塊并行聚類, 在主節(jié)點(diǎn)上合并聚類結(jié)果。 實(shí)驗(yàn)結(jié)果表明, 該算法的計(jì)算速度隨著節(jié)點(diǎn)數(shù)的增多呈線性增加, 具有較好的延展性。關(guān)鍵詞:并行聚類;計(jì)算機(jī)集群;數(shù)據(jù)庫(kù);延展性Parallel Clustering Algorithm Based on DensityCHEN

2、 Min1, GAO Xue-dong1, LUAN Shao-jun1, XI Yu-ping2(1. School of Economics and Management, University of Science and Technology Beijing, Beijing 100083; 2. Department of Automotive Engineering, Beijing Information Technology College, Beijing 100015【 Abstract 】 In order to meet the demands for large sc

3、ale databases clustering, this paper proposes a parallel clustering algorithm based on density for computer colony. This algorithm goes on data partition according to database distribution feature, processes data block parallel clustering on every node, merges clustering result on main node. Experim

4、ental result shows that computing speed of this algorithm is linear increment with number of node increasing, and it has better extensibility.【 Key words】 parallel clustering; computer colony; database; extensibility計(jì) 算 機(jī) 工 程 Computer Engineering第 36卷 第 11期Vol.36 No.11 2010年 6月June 2010·博士論文

5、83;文章編號(hào):1000 3428(201011 0008 03文獻(xiàn)標(biāo)識(shí)碼:A中圖分類號(hào):TP301.61 概述聚類分析是數(shù)據(jù)挖掘的主要任務(wù)之一,在很多領(lǐng)域有著廣泛應(yīng)用,如模式識(shí)別、圖像處理和數(shù)據(jù)壓縮等。隨著信息 技術(shù)的高速發(fā)展,出現(xiàn)了越來(lái)越多如地理信息、衛(wèi)星圖像等 大規(guī)?？臻g數(shù)據(jù)庫(kù),對(duì)聚類算法提出更高要求:盡可能減少 先決知識(shí)或輸入?yún)?shù)要求,發(fā)現(xiàn)任意形狀的類,適用于大規(guī) 模數(shù)據(jù)庫(kù)聚類等。文獻(xiàn) 1提出一種面向空間數(shù)據(jù)庫(kù),基于密度的聚類算 法,其主要思想為:如果一個(gè)對(duì)象在半徑為 Eps 的領(lǐng)域內(nèi)包 含至少 MinPts 個(gè)對(duì)象,那么該區(qū)域是密集的。該算法基本滿 足上述對(duì)于聚類算法的要求,理論上能

6、夠處理大規(guī)?？臻g數(shù) 據(jù)庫(kù)的聚類。為進(jìn)一步提高計(jì)算速度及當(dāng)空間數(shù)據(jù)庫(kù)規(guī)模增大時(shí)算法 的延展性,本文提出一種基于密度的并行聚類算法。在計(jì)算 機(jī)集群中實(shí)現(xiàn)該算法,其原因是計(jì)算機(jī)集群理論上具有無(wú)限 擴(kuò)容的能力,當(dāng)面臨巨型數(shù)據(jù)庫(kù)時(shí),可以通過(guò)將集群中的計(jì) 算節(jié)點(diǎn)增加到幾百個(gè)甚至上千個(gè)來(lái)滿足計(jì)算要求。本文算法 能合理劃分?jǐn)?shù)據(jù)庫(kù),由集群中的計(jì)算節(jié)點(diǎn)并行聚類,最后合 并聚類結(jié)果。2 基于密度的聚類算法給出文獻(xiàn) 1算法的幾個(gè)基本概念, 其中, DB 為數(shù)據(jù)庫(kù);Eps 和 MinPts 為給定閾值。定義 1(Eps 鄰域 對(duì)于空間任意一個(gè)點(diǎn) p ,其 Eps 領(lǐng)域 記作 ( , (, Eps N p q DB di

7、st p q Eps = 。定 義 2(核 心 點(diǎn) 如 果 一 個(gè) 點(diǎn) 的 Eps 鄰 域 內(nèi) 至 少 包 含MinPts 個(gè)點(diǎn),則稱其為核心點(diǎn)。定義 3(直接密度可達(dá) 若 q 是核心點(diǎn), 且 p 在 q 的 Eps 鄰 域內(nèi),則 p 從 q 直接密度可達(dá)。定義 4(密度可達(dá) 點(diǎn) p 從點(diǎn) q 密度可達(dá),若存在 12, , , p p "n p ,其中, 1p q =; n p p =,且 1i p +從 i p 直接密度可達(dá)。定義 5(密度相連 若點(diǎn) p 和點(diǎn) q 是密度連接的,則存在 對(duì)象 o ,使 p 和 q 都從 o 密度可達(dá)。定義 6(類 數(shù)據(jù)庫(kù) DB 的非空集合 C 是一

8、個(gè)類,當(dāng)且僅 當(dāng) C 滿足以下條件:(1任意點(diǎn) p , q ,若 p C ,且 q 從 p 密度可達(dá),則 q C (最大性 ;(2任意點(diǎn) p , q C ,則 p , q 密度連接 (連通性 。 定義 7(噪聲 數(shù)據(jù)庫(kù) D 中不屬于任何類的點(diǎn)為噪聲。 文獻(xiàn) 1算法思路如下:對(duì)數(shù)據(jù)庫(kù)中任何一個(gè)點(diǎn) p ,對(duì)其 進(jìn)行區(qū)域查詢, 判斷是否是核心點(diǎn), 如是, 則建立新類 C , p 及其鄰域內(nèi)的點(diǎn)均屬于該類。 考察 C 中尚未被考察過(guò)的點(diǎn) q , 若 q 是核心點(diǎn),則將其領(lǐng)域內(nèi)未屬于任何一類的點(diǎn)追加到類C 。不斷重復(fù)此過(guò)程,直到?jīng)]有新的點(diǎn)可以追加為止。以同樣程序?qū)ふ移渌念?不屬于任何類的點(diǎn)為噪聲。文獻(xiàn)

9、 1算法 的復(fù)雜度為 2( O n ,其中, n 是對(duì)象的總數(shù)。為了提高聚類效 率,該算法采用空間數(shù)據(jù)庫(kù)索引 R*-tree2實(shí)現(xiàn)區(qū)域搜索,使基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目“高維稀疏數(shù)據(jù)聚類研究” (70771007作者簡(jiǎn)介:陳 敏 (1976- , 女, 博士研究生, 主研方向:數(shù)據(jù)挖掘; 高學(xué)東,教授;欒紹峻,博士研究生;郗玉平,碩士 收稿日期:2010-01-10 E-mail :lynn.chenmin 9計(jì)算復(fù)雜度降為 (log O n n 。 3 基于密度的并行聚類算法3.1 算法思路問(wèn)題描述:給定 d 維空間點(diǎn)集 12, , , n DB q q q =" 及計(jì)算機(jī)

10、集群 12, , , M PC P P P =" , 其中, , 1,2, , i P i M =" 為集群中的 計(jì)算節(jié)點(diǎn),計(jì)算節(jié)點(diǎn)之間用網(wǎng)絡(luò)相連。尋找數(shù)據(jù)庫(kù) DB 中基 于合適參數(shù) Eps 和 MinPts 的類。本文算法思路如下:(1讀 入 數(shù) 據(jù) 庫(kù) DB , 根 據(jù) k -dist 圖 確 定 參 數(shù) Eps 和MinPts 。(2將數(shù)據(jù)庫(kù) DB 劃分為 N 塊, 12, , , N s s s " , i j s s =,i j , 1N i i DB s =,將數(shù)據(jù)塊 i s , 1,2, , i N =" 分配到集群中的 M 個(gè)計(jì)算節(jié)點(diǎn),其

11、中, N M ,當(dāng)每個(gè)計(jì)算節(jié)點(diǎn)均有 2個(gè) CPU 時(shí),理想劃分為 2N M =。注意:要根據(jù)數(shù)據(jù)庫(kù)規(guī)模來(lái) 確定合適的集群規(guī)模,當(dāng)數(shù)據(jù)庫(kù)較小時(shí),集群中的節(jié)點(diǎn)不宜 過(guò)多。(3計(jì)算機(jī)集群中的計(jì)算節(jié)點(diǎn) 12, , , M P P P " 對(duì)于自己分到 的數(shù)據(jù)塊,利用文獻(xiàn) 1算法聚類。(4合并各計(jì)算節(jié)點(diǎn) i P 的計(jì)算結(jié)果,得到對(duì)整個(gè)數(shù)據(jù)庫(kù)DB 的聚類結(jié)果,本文采用文獻(xiàn) 3中的合并策略。3.2 參數(shù)確定在讀入數(shù)據(jù)庫(kù)后,需要確定參數(shù) Eps 和 MinPts ,即領(lǐng)域 大小及領(lǐng)域內(nèi)最小點(diǎn)數(shù)閾值。文獻(xiàn) 1算法提到的鄰域概念雖 然是任意形狀的,不過(guò)通常都采用“圓”形鄰域。事實(shí)上, 支持領(lǐng)域搜索的 R

12、*-tree的每個(gè)節(jié)點(diǎn)都對(duì)應(yīng)一個(gè)外接矩形, 搜 索其實(shí)是針對(duì)這些矩形進(jìn)行的。如果采用圓形的鄰域,則需 要先在 R*-tree的矩形鄰域內(nèi)搜索, 再根據(jù)矩形與圓形的包含 關(guān)系來(lái)確定在圓形領(lǐng)域內(nèi)的對(duì)象數(shù)目。這樣的轉(zhuǎn)換影響了搜 索的效率,所以,在本文算法中采用矩形搜索鄰域,導(dǎo)致參 數(shù)的確定發(fā)生變化。在文獻(xiàn) 1算法中, 可以將 MinPts 固定為 4,再確定 Eps 的大小。然而經(jīng)過(guò)反復(fù)試驗(yàn)證明,在采用矩形 搜索鄰域時(shí),如果將 MinPts 固定為 4,在某些噪音干擾的情 況下,無(wú)法得出正確的聚類結(jié)果。如果將 MinPts 設(shè)定為 7, 再根據(jù) k -dist 圖來(lái)確定 Eps ,聚類結(jié)果會(huì)較好。實(shí)

13、驗(yàn)結(jié)果表 明,搜索速度與 MinPts 的值無(wú)關(guān),而是由搜索的鄰域范圍, 即 Eps 確定。所以,將 MinPts 設(shè)定為 7不會(huì)降低搜索效率。 3.3 數(shù)據(jù)庫(kù)劃分在確定了參數(shù)后,需要?jiǎng)澐謹(jǐn)?shù)據(jù)庫(kù),劃分的優(yōu)劣對(duì)于計(jì) 算機(jī)集群環(huán)境中的并行計(jì)算來(lái)說(shuō)是至關(guān)重要的,不僅影響到 并行算法的效率與延展性,而且對(duì)整個(gè)并行系統(tǒng)的負(fù)載平衡 也有著重要意義。 本文根據(jù)數(shù)據(jù)空間分布特征來(lái)劃分?jǐn)?shù)據(jù)庫(kù), 具體方法如下:首先掃描數(shù)據(jù)庫(kù),將數(shù)據(jù)庫(kù)在每一個(gè)坐標(biāo)軸 上進(jìn)行投影,據(jù)此找到數(shù)據(jù)庫(kù)在每一維上的分布特征,從而 對(duì)數(shù)據(jù)庫(kù)進(jìn)行合理劃分,這是人機(jī)交互的過(guò)程。分割原數(shù)據(jù)庫(kù)需要遵循 2個(gè)原則:(1依據(jù)空間分布特征進(jìn)行數(shù)據(jù)塊劃分。尋

14、找能顯示數(shù) 據(jù)分布特征的點(diǎn),本文稱為斷點(diǎn),之后從斷點(diǎn)處進(jìn)行區(qū)域 劃分。(2劃分?jǐn)?shù)據(jù)塊的多少要根據(jù)數(shù)據(jù)庫(kù)大小及計(jì)算環(huán)境來(lái) 共同決定。當(dāng)數(shù)據(jù)庫(kù)較小或計(jì)算節(jié)點(diǎn)數(shù)目較少,均不宜將其 劃分成過(guò)多的數(shù)據(jù)塊,其原因是將消耗過(guò)多的合并成本。該數(shù)據(jù)庫(kù)劃分方法適應(yīng)于任何維數(shù)的數(shù)據(jù)空間,為演示方便,以圖 1所示的帶有噪音的二維原數(shù)據(jù)庫(kù)進(jìn)行說(shuō)明。 圖 1 原數(shù)據(jù)庫(kù)將圖 1所示數(shù)據(jù)庫(kù)投影至 X 軸、 Y 軸,投影結(jié)果見(jiàn)圖 2。 圖 2 數(shù)據(jù)庫(kù)在 X 軸、 Y 軸上的投影結(jié)果假如實(shí)驗(yàn)環(huán)境僅有 2個(gè)計(jì)算節(jié)點(diǎn) (4個(gè) CPU ,那么根據(jù) 對(duì)數(shù)據(jù)庫(kù)劃分的 2個(gè)原則, 可在 X 軸上根據(jù) A 點(diǎn), 在 Y 軸上 根據(jù) B 點(diǎn)將數(shù)

15、據(jù)庫(kù)劃分成 4塊。若實(shí)驗(yàn)環(huán)境存在更多計(jì)算節(jié) 點(diǎn),則可適當(dāng)選取多個(gè)斷點(diǎn)將數(shù)據(jù)庫(kù)劃分成更多塊。 3.4 算法復(fù)雜度在完成數(shù)據(jù)庫(kù)劃分之后,每個(gè)計(jì)算節(jié)點(diǎn)將對(duì)自己分到的 數(shù)據(jù)塊 i s , 1,2, , i N =" 采用文獻(xiàn) 1算法分別聚類,在采用空 間索引 R*-tree的情況下, 如果忽略合并成本, 則對(duì)每一個(gè)數(shù) 據(jù)塊聚類的時(shí)間復(fù)雜度為 (log i i O s s , 其中, i s 為數(shù)據(jù)塊 i s 的點(diǎn)數(shù), 即數(shù)據(jù)量。 本文算法總體的時(shí)間復(fù)雜度為 11(log O s s +22log log N N s s s s +" ,在數(shù)據(jù)庫(kù)規(guī)模很大時(shí),遠(yuǎn)小于文獻(xiàn) 1算法的復(fù)雜度

16、 (log O n n ,而且 n 越大,差距越明顯。4 實(shí)驗(yàn)實(shí)驗(yàn)所用設(shè)備為 3臺(tái)筆記本電腦,其中主節(jié)點(diǎn)為一臺(tái)采 用 Windows 操作系統(tǒng)、 Intel 1.73 GHz(雙核 、 2.87 GB內(nèi)存 的筆記本。另外, 2個(gè)計(jì)算節(jié)點(diǎn)為均為采用 Windows 操作系統(tǒng)、 Intel 2.0 GHz(雙核 、 3 GB內(nèi)存的筆記本;電腦之間由帶寬為 100 Mb/s的局域網(wǎng)絡(luò)連接;編程工具和運(yùn)行環(huán)境為 JDK 1.5。 與建立 k -dist 圖確定參數(shù)這個(gè)過(guò)程類似,數(shù)據(jù)分區(qū)是人機(jī)交 互的過(guò)程,作為預(yù)處理部分,沒(méi)有納入執(zhí)行時(shí)間。4.1 加速性實(shí)驗(yàn)采用圖 1所示數(shù)據(jù)庫(kù)來(lái)進(jìn)行測(cè)試,該數(shù)據(jù)庫(kù)文件包

17、含 45 727個(gè)點(diǎn),參數(shù) Eps 和 MinPts 分別設(shè)定為 4, 7,本文算法 聚類結(jié)果如圖 3所示。 10 圖 3 本文算法聚類結(jié)果實(shí)驗(yàn)結(jié)果證明,本文算法的聚類結(jié)果是正確的,并且隨 著計(jì)算節(jié)點(diǎn)的增多,幾乎可以線性加速,如表 1所示。表 1 本文算法與文獻(xiàn) 1算法計(jì)算效率比較算法 節(jié)點(diǎn)數(shù)執(zhí)行時(shí)間 /s執(zhí)行時(shí)間比 /(%聚類結(jié)果 /類文獻(xiàn) 1算法 1 46.375 100 10 本文算法 2 22.953 49 10 本文算法3 16.93837104.2 關(guān)于數(shù)據(jù)庫(kù)規(guī)模的延展性實(shí)驗(yàn)為測(cè)試本文算法的延展性,采用含有 5×104個(gè)點(diǎn)、 1×105個(gè)點(diǎn)、 1.5×

18、105個(gè)點(diǎn)、 2×105個(gè)點(diǎn)的 4個(gè)數(shù)據(jù)庫(kù)進(jìn)行實(shí)驗(yàn)。這 4個(gè)數(shù)據(jù)庫(kù)點(diǎn)的分布形狀基本相似,差別在于對(duì)象數(shù)目。在針對(duì) 4個(gè)數(shù)據(jù)庫(kù)的實(shí)驗(yàn)中,參數(shù) Eps 和 MinPts 均分別設(shè)定為3, 7,實(shí)驗(yàn)結(jié)果如圖 4所示。 圖 4 本文算法的延展性從圖 4可以看出,隨著數(shù)據(jù)庫(kù)規(guī)模的增加, 3條線之間 的距離越遠(yuǎn),本文算法的優(yōu)勢(shì)越明顯。相對(duì)于文獻(xiàn) 1算法, 本文算法在 3臺(tái)機(jī)器上實(shí)現(xiàn)的計(jì)算時(shí)間增勢(shì)很平緩。實(shí)驗(yàn)結(jié) 果表明,當(dāng)數(shù)據(jù)庫(kù)規(guī)模增大時(shí),本文算法可通過(guò)適當(dāng)增加計(jì) 算節(jié)點(diǎn)來(lái)達(dá)到高效聚類,具有良好的延展性。4.3 文獻(xiàn) 1算法中參數(shù)對(duì)計(jì)算效率的影響文獻(xiàn) 1提到當(dāng) MinPts 的值增加時(shí), 執(zhí)行時(shí)間

19、劇增, 然而 本文實(shí)驗(yàn)發(fā)現(xiàn),在預(yù)先確定的 2個(gè)參數(shù) Eps 和 MinPts 中,對(duì)計(jì)算速度有明顯影響的是 Eps 而非 MinPts 。在圖 1中, Eps 的測(cè)試值為 2, 3, 4; MinPts 的測(cè)試值為 4, 7, 10。當(dāng)參數(shù)不正確時(shí),顯然無(wú)法得到正確的聚類結(jié)果, 這里的執(zhí)行時(shí)間定義為文獻(xiàn) 1算法執(zhí)行完畢的時(shí)間,實(shí)驗(yàn)結(jié) 果如圖 5所示。 圖 5 文獻(xiàn) 1算法的參數(shù)對(duì)計(jì)算效率影響從圖 5可以看出,當(dāng) Eps =2, Eps =3, Eps =4時(shí),雖然MinPts 值會(huì)變化,執(zhí)行時(shí)間近似為 3條平行直線;當(dāng) Eps 固定時(shí),執(zhí)行時(shí)間幾乎沒(méi)有隨 MinPts 值而變化。與此相反,當(dāng)M

20、inPts 值固定時(shí),采用不同的 Eps 值,可以看到計(jì)算時(shí)間分別為 3條平行線,有明顯差距。因此,本文主要影響計(jì)算時(shí)間的參數(shù)為 Eps , MinPts 對(duì)計(jì)算時(shí)間影響很小。5 結(jié)束語(yǔ)本文提出一種面向計(jì)算機(jī)集群系統(tǒng)的基于密度的并行聚 類算法。實(shí)驗(yàn)結(jié)果表明,本文算法通過(guò)適當(dāng)增加計(jì)算節(jié)點(diǎn), 能加速計(jì)算速度,適用于大規(guī)模數(shù)據(jù)庫(kù)的聚類分析;并且得 到影響文獻(xiàn) 1算法效率的參數(shù)為 Eps ,而非 MinPts 。下一步 研究方向?yàn)?擬采用更先進(jìn)方式劃分?jǐn)?shù)據(jù)庫(kù),以規(guī)避人機(jī)交 互的過(guò)程,使算法的可操作性、可使用性更強(qiáng)。參考文獻(xiàn)1 Easter M, Kriegek H P, Sander J, et al. A Density-based Algorithmfor Discovering Clusters in Large DatabasesC/Proc. of the 2nd International Conference on Knowledge Discovery