基于屬性相關(guān)分析的離群數(shù)據(jù)并行挖掘算法

王 磊,張繼福

(太原科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,太原030024)

離群數(shù)據(jù)(Outlier)就是明顯偏離其他數(shù)據(jù),不滿足數(shù)據(jù)的一般模式或行為,與存在的其他數(shù)據(jù)不一致的數(shù)據(jù)[1]。離群數(shù)據(jù)挖掘問題可以看作兩個(gè)子問題:(1)定義在給定的數(shù)據(jù)集合中什么樣的數(shù)據(jù)認(rèn)為是不一致的;(2)找到一個(gè)有效的方法挖掘這樣的離群數(shù)據(jù)。離群數(shù)據(jù)挖掘作為數(shù)據(jù)挖掘的一種重要技術(shù),在欺詐檢測(cè)、網(wǎng)絡(luò)安全分析、入侵檢測(cè)等領(lǐng)域有廣泛的應(yīng)用[2]。

目前,國(guó)內(nèi)外主要的離群數(shù)據(jù)挖掘算法大致可分為基于統(tǒng)計(jì)的方法[1]、基于距離的方法[3]、基于深度的方法[4]、基于密度的方法[5]和基于偏差的方法[6]等。隨著數(shù)據(jù)規(guī)模的不斷增大,高維海量離群挖掘是當(dāng)前研究熱點(diǎn)之一,其主要研究成果有:Aggarwal和Yu[7]于2005年提出的投影離群數(shù)據(jù)檢測(cè)算法,Cui Zhu[8]等提出的基于用戶實(shí)例的高維數(shù)據(jù)檢測(cè)算法,張繼福[9-10]等通過引入稠密度系數(shù)提出的基于概念格的離群數(shù)據(jù)挖掘算法,葛凌云[11]等提出的利用微粒群算法搜索稀疏子空間算法,Mohamed[12]等提出的基于屬性相關(guān)分析的聚類算法。蔡江輝[13]等提出了一種基于聚類的離群挖掘算法。但是,這些方法都是在單機(jī)環(huán)境下運(yùn)行的,隨著信息技術(shù)的不斷發(fā)展,大量的數(shù)據(jù)被存儲(chǔ)在數(shù)據(jù)庫中,且數(shù)據(jù)普遍具有分布稀疏、維度高、數(shù)據(jù)量呈指數(shù)增長(zhǎng)等特點(diǎn),這些因素都對(duì)計(jì)算機(jī)的單機(jī)計(jì)算能力提出了非常高的要求。與此同時(shí),受限于大型機(jī)、巨型機(jī)的昂貴價(jià)格,使它們?cè)趯?shí)際應(yīng)用中幾乎不可能得到普及,并行離群挖掘算法成為解決這一問題的有效途徑,即將許多運(yùn)算能力相對(duì)低下計(jì)算機(jī)構(gòu)成計(jì)算機(jī)組,通過并行計(jì)算的方式,以相對(duì)低廉的價(jià)格獲得強(qiáng)大的運(yùn)算能力,從而在普通的實(shí)驗(yàn)環(huán)境中實(shí)現(xiàn)高維海量數(shù)據(jù)的離群挖掘工作。目前,并行離群挖掘的研究成果還比較少,王瑋[14]等針對(duì)海量數(shù)據(jù)提出了一種基于網(wǎng)格的概念格分布式構(gòu)造算法,對(duì)本文的并行算法具有一定的借鑒意義。

針對(duì)上述問題,本文提出了一種基于屬性相關(guān)分析的并行局部離群數(shù)據(jù)挖掘算法。該算法在并行計(jì)算環(huán)境中,首先由主節(jié)點(diǎn)分配屬性相關(guān)分析任務(wù),各個(gè)子節(jié)點(diǎn)分別讀取數(shù)據(jù)子集并計(jì)算各數(shù)據(jù)子集的冗余屬性,通過數(shù)據(jù)通信傳送回主節(jié)點(diǎn)后由主節(jié)點(diǎn)將冗余屬性刪除,從而有效的實(shí)現(xiàn)數(shù)據(jù)集的降維目的;其次由主節(jié)點(diǎn)分配搜索任務(wù),各個(gè)子節(jié)點(diǎn)讀取數(shù)據(jù)子集后根據(jù)用戶設(shè)定的稀疏度系數(shù)閾值,采用微粒群算法搜索各數(shù)據(jù)子集的稀疏子空間,由主節(jié)點(diǎn)進(jìn)行合并計(jì)算后,確定最終的局部離群數(shù)據(jù);最后,采用天體光譜數(shù)據(jù)作為數(shù)據(jù)集,實(shí)驗(yàn)結(jié)果驗(yàn)證了該算法的正確性和有效性,從而為海量高維離群數(shù)據(jù)挖掘提供了一種新途徑。

1 基本概念

1.1 基于屬性相關(guān)分析的局部離群數(shù)據(jù)挖掘算法

基于屬性相關(guān)分析的高維離群數(shù)據(jù)挖掘的基本思想可歸納為[15]:首先利用屬性相關(guān)分析,刪除冗余屬性;然后使用微粒群算法,根據(jù)用戶確定的稀疏度系數(shù)閾值搜索稀疏子空間;最后根據(jù)稀疏子空間確定局部離群數(shù)據(jù)。其中,屬性相關(guān)分析通過檢測(cè)每個(gè)屬性維的稠密和稀疏區(qū)域分布搜索冗余屬性。有關(guān)定義描述如下:

定義1 對(duì)于任意一個(gè)d維數(shù)據(jù)集,屬性集A={A1,A2,…Ad},數(shù)據(jù)對(duì)象集 X ={X1,X2,…Xn},Xij(i=1,2,…n;j=1,2,…d)表示第i個(gè)數(shù)據(jù)對(duì)象在第j個(gè)屬性上的相關(guān)值,稱Xij是一個(gè)1-d點(diǎn)。

為了檢測(cè)每一屬性上的區(qū)域分布,需要計(jì)算每一個(gè)1-d點(diǎn)Xij的稀疏因子。

定義2 Xij的稀疏因子定義為:對(duì)象在各維中是否處于稠密區(qū)域。

定義4 對(duì)于任意數(shù)據(jù)集,對(duì)象集為N,屬性集為 D,存在屬性Aj,如果(利用定義2和3),即屬性Aj是由稠密區(qū)域構(gòu)成的維,則稱它是冗余屬性。

根據(jù)定義4可以刪除數(shù)據(jù)集中的冗余屬性。在縮減后的數(shù)據(jù)集中,為了度量子空間內(nèi)數(shù)據(jù)的偏離程度,采用文獻(xiàn)[7]定義的稀疏度系數(shù)作為子空間偏移程度的度量因子。

定義5 稀疏度系數(shù)S(D)的表達(dá)式定義為:

其中,n(D)是包含在D中的對(duì)象數(shù),f=1/Φ.對(duì)于局部離群數(shù)據(jù),它所在的子空間內(nèi)包含的數(shù)據(jù)條數(shù)遠(yuǎn)低于平均值,因此稀疏度系數(shù)S(D)小于0.

定義6 根據(jù)定義5計(jì)算子空間S的稀疏度系數(shù),TS為用戶設(shè)定的稀疏度閾值,若稀疏度系數(shù)S(D)＜TS,則稱S為稀疏子空間。

容易發(fā)現(xiàn),λij很大說明1-d點(diǎn) Xij代表的數(shù)據(jù)對(duì)象i在j屬性維上處于稀疏區(qū)域,反之則說明其處于稠密區(qū)域。為了識(shí)別稠密區(qū)域,這里設(shè)置一個(gè)閾值 ε來判斷。

定義3 如果 Xij的稀疏因子 λij＜ε,則令 Zij=1,并稱Xij屬于稠密區(qū)域,反之,則令 Zij=0,并稱 Xij屬于稀疏區(qū)域。

根據(jù)定義3,可以列出一個(gè)稀疏度密度矩陣Z(n*d),通過矩陣Z,可以很清晰的看出每個(gè)數(shù)據(jù)可知,它的維數(shù)均不大于logθ(N/TS2+1)。

假設(shè)D維屬性集中包含N個(gè)數(shù)據(jù)對(duì)象,縮減后的屬性集維數(shù)為A.選取k維作為子空間,且將k維作為A維空間的微粒,稀疏度系數(shù)作為適應(yīng)值函數(shù),利用微粒群算法可以找出稀疏子空間并確定局部離群數(shù)據(jù)。

1.2 并行計(jì)算與MPI

并行計(jì)算或者并行處理,指的是利用多個(gè)具有計(jì)算能力的部件來共同完成一個(gè)計(jì)算工作,獲得比用一個(gè)部件來完成要快的效果,它是計(jì)算數(shù)學(xué)與新一代計(jì)算機(jī)相結(jié)合的產(chǎn)物[16]。并行計(jì)算以其強(qiáng)大的計(jì)算能力、優(yōu)越的性價(jià)比、成熟的技術(shù)和設(shè)備、良好的可移植性和可伸縮性成為大規(guī)模數(shù)據(jù)分析的有效支持工具。目前,最流行的兩個(gè)并行計(jì)算支持環(huán)境是PVM和 MPI。MPI(Message Passing Interface)[17]是一種消息傳遞標(biāo)準(zhǔn)或規(guī)范,它以可移植性強(qiáng)、模塊性高、應(yīng)用領(lǐng)域靈活而受到國(guó)際上的廣泛重視。

并行計(jì)算中的數(shù)據(jù)集劃分方式主要分為兩類:水平劃分和垂直劃分。假設(shè)DB是由D維屬性、N條數(shù)據(jù)構(gòu)成的數(shù)據(jù)集,可以將DB水平或者垂直的劃分成m個(gè)子集。水平劃分即DB=DB1∪DB2…∪DBm,且DBi∩DBj=?(1≤i≤m,1≤j≤m),|DB1|+|DB2|+… +|DBm|=N.垂直劃分即DB=DB1∪DB2…∪DBm,且attr(DBi)∩attr(DBj)=?,|attr(DB1)|+|attr(DB2)|+… +|attr(DBm)|=D,attr(DBi)表示數(shù)據(jù)集DBi的屬性子集(1≤i≤m,1≤j≤m)。

2 基于屬性相關(guān)分析的并行離群挖掘方法

針對(duì)大規(guī)模高維數(shù)據(jù)集,其龐大的數(shù)據(jù)存儲(chǔ)、復(fù)雜的數(shù)據(jù)結(jié)構(gòu)都使單機(jī)環(huán)境下的數(shù)據(jù)挖掘算法變的越來越復(fù)雜。雖然近期國(guó)內(nèi)外學(xué)者提出了一些針對(duì)高維海量數(shù)據(jù)的算法,但面對(duì)數(shù)據(jù)量的指數(shù)級(jí)增長(zhǎng)和硬件環(huán)境的制約,這些算法也面臨各種各樣的使用限制甚至瓶頸。針對(duì)上述問題,采用并行計(jì)算的思想,對(duì)基于屬性相關(guān)分析的高維離群數(shù)據(jù)挖掘算法進(jìn)行改進(jìn),使其在普通的實(shí)驗(yàn)環(huán)境下也能獲得較高的效率。該算法主要由兩部分構(gòu)成:屬性相關(guān)分析刪除冗余屬性和微粒群算法搜索離群子空間。

屬性相關(guān)分析是依據(jù)每維的稀疏稠密性刪除冗余屬性的,而各維的稀疏稠密性可以根據(jù)定義2、3、4按屬性維獨(dú)立運(yùn)算,各維之間互不影響,因此屬性相關(guān)分析可以用垂直劃分的并行計(jì)算來實(shí)現(xiàn)。在屬性相關(guān)分析刪除冗余屬性過程中,主節(jié)點(diǎn)首先根據(jù)子節(jié)點(diǎn)數(shù)M和屬性數(shù)D垂直劃分(D/M)數(shù)據(jù)集P.主節(jié)點(diǎn)分配任務(wù)后,子節(jié)點(diǎn)利用屬性相關(guān)分析求出每個(gè)數(shù)據(jù)子集的冗余屬性。然后子節(jié)點(diǎn)將冗余屬性序號(hào)傳回主節(jié)點(diǎn),由主節(jié)點(diǎn)合并處理后刪除冗余屬性,此時(shí)數(shù)據(jù)集為縮減屬性的數(shù)據(jù)集,記為縮減集Q.

采用微粒群算法搜索離群子空間是通過判斷隨機(jī)子空間的稀疏程度確定的,根據(jù)微粒群算法的特點(diǎn),子空間的隨機(jī)選擇過程又通過隨機(jī)選定屬性實(shí)現(xiàn),因此微粒群搜索離群子空間可以采用水平劃分的并行計(jì)算來實(shí)現(xiàn)。采用水平劃分的方法可以保證各數(shù)據(jù)子集中屬性的完整性,進(jìn)而也保證了離群子空間搜索結(jié)果的完備性。在微粒群算法搜索離群子空間過程中,主節(jié)點(diǎn)根據(jù)子節(jié)點(diǎn)數(shù)M和數(shù)據(jù)條數(shù)N水平劃分(N/M)縮減數(shù)據(jù)集Q.主節(jié)點(diǎn)分配任務(wù)后,子節(jié)點(diǎn)根據(jù)用戶設(shè)定的稀疏度閾值,使用微粒群算法在各自分配的數(shù)據(jù)子集上搜索局部稀疏子空間。然后將局部稀疏子空間的相關(guān)信息(包括數(shù)據(jù)條數(shù),數(shù)據(jù)記錄號(hào),屬性序號(hào))傳回主節(jié)點(diǎn),主節(jié)點(diǎn)通過對(duì)相同局部稀疏子空間的數(shù)據(jù)條數(shù)進(jìn)行合并,生成全局子空間。最后,主節(jié)點(diǎn)根據(jù)稀疏度閾值對(duì)全局子空間進(jìn)行判斷,識(shí)別出全局稀疏子空間和離群數(shù)據(jù)。

定理1 對(duì)于任意一個(gè)D維屬性、N條數(shù)據(jù)構(gòu)成的數(shù)據(jù)集,任意由冗余屬性構(gòu)成的子空間都不是稀疏子空間。

證明 假設(shè)子空間Q是由冗余屬性構(gòu)成的稀疏子空間。據(jù)定義5?子空間Q的稀疏度系數(shù)S(D)＜TS,再由定義4?冗余屬性即由稠密區(qū)域構(gòu)成的屬性,而冗余屬性的稠密性遠(yuǎn)大于非冗余屬性的稠密性 ?稀疏子空間Q的稠密性遠(yuǎn)大于其他子空間的稠密性,即其他子空間的稀疏度系數(shù)S(D)′＜TS,據(jù)定義6?其他子空間也是稀疏子空間數(shù)據(jù)集中所有的子空間都是稀疏子空間。與假設(shè)矛盾,定理1得證。

定理2 在屬性相關(guān)分析中,并行計(jì)算環(huán)境和單機(jī)環(huán)境刪除冗余屬性的操作結(jié)果一致。

證明 假設(shè)DB是由D維屬性、N條數(shù)據(jù)構(gòu)成的數(shù)據(jù)集。對(duì)數(shù)據(jù)集的垂直劃分即DB =DB1∪DB2…∪DBm,并且attr(DBi)∩attr(DBj)=?(1≤i≤m,1≤j≤m),|attr(DB1)|+|attr(DB2)|+… +|attr(DBm)|=D.屬性相關(guān)分析是以屬性為單位的運(yùn)算,所以單機(jī)環(huán)境下是做屬性(1,D)的分析,而并行環(huán)境是子節(jié)點(diǎn)I對(duì)屬性子集attr(DBi)同時(shí)進(jìn)行((M-1)D/M+1,ID/M)分析,1≤I≤M.由垂直劃分的概念可知,并行和單機(jī)環(huán)境刪除冗余屬性的操作結(jié)果一致。

推論1 在并行實(shí)驗(yàn)環(huán)境下,刪除冗余屬性對(duì)離群數(shù)據(jù)挖掘的精度沒有影響。

證明 由定理1可知,刪除冗余屬性對(duì)搜索稀疏子空間的結(jié)果沒有影響,即對(duì)離群挖掘的精度沒有影響,由定理2可知,并行環(huán)境和單機(jī)環(huán)境下的屬性相關(guān)分析結(jié)果一致,所以,并行實(shí)驗(yàn)環(huán)境下,刪除冗余屬性不影響離群挖掘算法結(jié)果。

定義7 假設(shè)DB是由D維屬性、N條數(shù)據(jù)構(gòu)成的數(shù)據(jù)集。數(shù)據(jù)集水平劃分后,如果各個(gè)子節(jié)點(diǎn)分析的數(shù)據(jù)子集中,存在稀疏度系數(shù)小于用戶設(shè)定的系數(shù)度閾值的子空間(利用定義5和6),即S(D)＜TS,則稱這些子空間為局部稀疏子空間。

定義8 假設(shè)DB是由D維屬性、N條數(shù)據(jù)構(gòu)成的數(shù)據(jù)集。數(shù)據(jù)集水平劃分后,如果各子節(jié)點(diǎn)分析的數(shù)據(jù)子集中,存在屬性序號(hào)相同,數(shù)據(jù)記錄號(hào)不同的子空間,則稱這些子空間為相同局部子空間。如果這些子空間同時(shí)滿足定義7,則稱它們?yōu)橄嗤植肯∈枳涌臻g。

定義9 在相同局部稀疏子空間中,如果數(shù)據(jù)對(duì)象合并后,仍然滿足定義5和6,即S(D)＜TS,則稱合并后的子空間為全局稀疏子空間,全局稀疏子空間中所包含的數(shù)據(jù)對(duì)象稱為局部離群數(shù)據(jù)。

定理3 如果各個(gè)子節(jié)點(diǎn)的相同局部子空間中存在非局部稀疏子空間,那么這些相同局部子空間合并后的全局子空間必定不是全局稀疏子空間。

證明 設(shè)子節(jié)點(diǎn)I上存在一個(gè)非局部稀疏子空間P,P的相同局部子空間都是局部稀疏子空間,由定義6可知,P不滿足S(D)＜TS,由于稀疏度系數(shù)TS不變,易知數(shù)據(jù)條數(shù)合并后的全局子空間必定也不滿足S(D)＜TS,即這個(gè)全局子空間不是全局稀疏子空間。

推論2 并行環(huán)境下搜索的全局稀疏子空間與單機(jī)環(huán)境的稀疏子空間一致。

證明 由于微粒群算法的適應(yīng)值函數(shù)一致,由定義9和定理3可知,數(shù)據(jù)對(duì)象的個(gè)體和全局最優(yōu)位置一樣,即稀疏度系數(shù)也一致。所以,并行環(huán)境下的全局稀疏子空間和單機(jī)環(huán)境的稀疏子空間也一致。

推論3 基于屬性相關(guān)分析的并行局部離群挖掘與單機(jī)環(huán)境的結(jié)果一致。

證明 本文并行算法由兩部分構(gòu)成。由推論1和推論2可知,屬性相關(guān)分析和微粒群搜索算法的并行與單機(jī)結(jié)果都一致,易知基于屬性相關(guān)分析的并行局部離群挖掘算法和單機(jī)環(huán)境下的算法結(jié)果一致。

3 算法描述

根據(jù)上述描述的基本思想,基于屬性相關(guān)分析的并行局部離群數(shù)據(jù)挖掘算法由兩個(gè)子算法構(gòu)成:并行屬性相關(guān)分析算法和并行微粒群搜索算法。

算法1 并行屬性相關(guān)分析算法

輸入:原始數(shù)據(jù)集DB,稀疏因子閾值 ε,子節(jié)點(diǎn)數(shù)目M

輸出:縮減數(shù)據(jù)集RDB

(1)主節(jié)點(diǎn)根據(jù)子節(jié)點(diǎn)數(shù)目M和數(shù)據(jù)集維數(shù)D,由D/M劃分各個(gè)子節(jié)點(diǎn)要計(jì)算的數(shù)據(jù)子集(此次劃分為垂直劃分);

(2)主節(jié)點(diǎn)通過第一次網(wǎng)絡(luò)通信分配屬性相關(guān)分析任務(wù),子節(jié)點(diǎn)1的任務(wù)為屬性(1,D/M)的數(shù)據(jù)子集,依次類推,子節(jié)點(diǎn)I的任務(wù)為屬性((M-1)D/M+1,ID/M)的數(shù)據(jù)子集;

(3)各個(gè)子節(jié)點(diǎn)通過用戶設(shè)定的稀疏因子閾值ε,使用屬性相關(guān)分析對(duì)各自的數(shù)據(jù)子集進(jìn)行運(yùn)算,找出各數(shù)據(jù)子集的冗余屬性;

(4)各子節(jié)點(diǎn)通過第二次網(wǎng)絡(luò)通信將冗余屬性序號(hào)傳回主節(jié)點(diǎn);

(5)主節(jié)點(diǎn)對(duì)數(shù)據(jù)子集的冗余屬性進(jìn)行匯總,得出原始數(shù)據(jù)集DB的冗余屬性;

(6)主節(jié)點(diǎn)對(duì)原始數(shù)據(jù)集的冗余屬性進(jìn)行刪除,得出縮減數(shù)據(jù)集RDB.

算法2 離群數(shù)據(jù)并行挖掘算法

輸入:縮減數(shù)據(jù)集RDB,稀疏度系數(shù)閾值S,子節(jié)點(diǎn)數(shù)目M

輸出:局部離群數(shù)據(jù)

(1)主節(jié)點(diǎn)根據(jù)子節(jié)點(diǎn)數(shù)目M和縮減數(shù)據(jù)集條數(shù)N,由N/M劃分各個(gè)子節(jié)點(diǎn)要計(jì)算的數(shù)據(jù)子集(此次劃分為水平劃分);

(2)主節(jié)點(diǎn)通過第三次網(wǎng)絡(luò)通信分配微粒群搜索任務(wù),子節(jié)點(diǎn)1的任務(wù)為數(shù)據(jù)編號(hào)(1,N/M)的數(shù)據(jù)子集,依次類推,子節(jié)點(diǎn)I的任務(wù)為數(shù)據(jù)編號(hào)((M-1)N/M+1,IN/M)的數(shù)據(jù)子集;

(3)各個(gè)子節(jié)點(diǎn)通過稀疏度系數(shù)S,使用微粒群算法搜索各數(shù)據(jù)子集,找出局部稀疏子空間;

(4)各子節(jié)點(diǎn)通過第四次網(wǎng)絡(luò)通信將局部稀疏子空間的相關(guān)信息(包括數(shù)據(jù)條數(shù),數(shù)據(jù)記錄號(hào),屬性序號(hào))傳回主節(jié)點(diǎn);

(5)主節(jié)點(diǎn)對(duì)相同局部稀疏子空間的數(shù)據(jù)條數(shù)進(jìn)行合并,得出全局子空間的集合;

(6)主節(jié)點(diǎn)通過稀疏度系數(shù),對(duì)全局子空間進(jìn)行判別,得出全局稀疏子空間;

(7)主節(jié)點(diǎn)根據(jù)數(shù)據(jù)記錄號(hào)得出最后的離群數(shù)據(jù)。

在算法1和2中,共進(jìn)行了4次網(wǎng)絡(luò)通信,兩次任務(wù)分配通信和兩次結(jié)果回傳通信。由于網(wǎng)絡(luò)通信僅傳輸屬性序號(hào)、數(shù)據(jù)標(biāo)號(hào)等信息,并不涉及具體數(shù)據(jù)的通信,其數(shù)據(jù)量傳遞較少,因此,局域網(wǎng)網(wǎng)絡(luò)通信代價(jià)幾乎可以忽略。在算法1中,由于attr(DBi)∩attr(DBj)=?,各子節(jié)點(diǎn)可以獨(dú)立進(jìn)行屬性相關(guān)分析,步驟3的理論運(yùn)行效率接近T/M(T是單機(jī)環(huán)境下運(yùn)行屬性相關(guān)分析的時(shí)間,M是子節(jié)點(diǎn)個(gè)數(shù)),而其他步驟中的通信和數(shù)據(jù)庫讀寫時(shí)間相對(duì)較小,算法1能較好的提高效率。微粒群算法不是線性算法,隨著數(shù)據(jù)量的增大,其運(yùn)行時(shí)間也會(huì)大幅增加,而算法2由各子節(jié)點(diǎn)獨(dú)立的搜索離群子空間,其步驟3的理論運(yùn)行時(shí)間小于T/M(T是單機(jī)環(huán)境下運(yùn)行微粒群搜索的時(shí)間,M是子節(jié)點(diǎn)個(gè)數(shù)),同樣算法2的通信和合并計(jì)算時(shí)間代價(jià)相對(duì)較小,算法2也能大幅縮短運(yùn)行時(shí)間。

4 實(shí)驗(yàn)結(jié)果分析

采用國(guó)家天文臺(tái)提供的高紅移類星體、晚型星、類星體、恒星四個(gè)SDSS天體光譜數(shù)據(jù),經(jīng)過離散化以后作為實(shí)驗(yàn)數(shù)據(jù)集[18],其中:44條光譜特征線作為屬性,即:維數(shù) =44、光譜數(shù)據(jù)集分別含有5403(7M)、34117(46M)、71601(99M)、74614(104M)條,數(shù)據(jù)庫為E5506CPU,8GB內(nèi)存做服務(wù)器的ORACLE 9i數(shù)據(jù)庫。實(shí)驗(yàn)設(shè)備使用4臺(tái)Pentium D925 CPU,512 MB內(nèi)存計(jì)算機(jī)作為子節(jié)點(diǎn),其中1臺(tái)同時(shí)作為主節(jié)點(diǎn)。實(shí)驗(yàn)平臺(tái)為MPICH2-1.0.3的并行環(huán)境,采用Visual C++6.0實(shí)現(xiàn)了本文所提的單機(jī)算法和并行算法。

在實(shí)驗(yàn)中,稀疏度系數(shù)取-1,稀疏因子取0.1,微粒群的規(guī)模設(shè)為N=30,參數(shù)c1、c2設(shè)為0.5,w為0.8,算法的試驗(yàn)次數(shù)為10次,取平均值作為結(jié)果。加速比S是衡量并行算法的主要指標(biāo),其定義為S=T/P,其中:T表示單機(jī)環(huán)境的串行耗時(shí),P表示并行運(yùn)算的耗時(shí),實(shí)驗(yàn)結(jié)果見圖1和圖2。

由圖1可以看出,在實(shí)驗(yàn)環(huán)境相同的情況下,并行環(huán)境的算法和單機(jī)環(huán)境的算法找出的離群數(shù)據(jù)基本相同。說明并行環(huán)境下算法的精度與單機(jī)環(huán)境下算法的精度一致,在上述兩個(gè)子算法中,并行屬性相關(guān)分析和單機(jī)屬性相關(guān)分析、并行子空間搜索和單機(jī)子空間搜索的結(jié)果大體是一致的,從而進(jìn)一步驗(yàn)證了算法的正確性。

圖1 局部離群數(shù)據(jù)個(gè)數(shù)比較Fig.1 Comparison with the count of local outlier

圖2 并行算法加速比Fig.2 The acceleration of parallel algorithm

由圖2可以看出,隨著數(shù)據(jù)集逐漸增大,并行算法的加速比也逐漸增大,主要是由于算法2的加速比提升引起的。在算法1中,由于屬性相關(guān)分析基本呈線性變化,加速比基本保持不變;但在算法2中,隨著數(shù)據(jù)量的增大,其單機(jī)環(huán)境下的微粒群搜索計(jì)算量劇增,且增幅遠(yuǎn)遠(yuǎn)超過并行子節(jié)點(diǎn)中的微粒群搜索,算法2的加速比呈上升趨勢(shì)。另外,由于并行算法僅進(jìn)行了4次通信,且屬于局域網(wǎng)通信,數(shù)據(jù)量也較小,所以其網(wǎng)絡(luò)通信時(shí)間幾乎可以忽略,這也是算法加速比隨著數(shù)據(jù)集增大而逐漸提高的因素之一。總之,隨著數(shù)據(jù)集的增加,微粒群搜索加速比的提高和網(wǎng)絡(luò)通信時(shí)間的相對(duì)較少是并行算法的加速比提高的關(guān)鍵原因。

5 結(jié)束語

針對(duì)高維海量數(shù)據(jù)集中的局部離群數(shù)據(jù),采用并行計(jì)算的思想,給出了一種基于屬性相關(guān)分析的并行局部離群數(shù)據(jù)挖掘算法。該算法通過兩個(gè)并行子算法完成了離群數(shù)據(jù)的挖掘任務(wù),并在局域網(wǎng)實(shí)驗(yàn)環(huán)境中,大幅地提高挖掘效率。采用恒星光譜數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù),驗(yàn)證了該算法的正確性和有效性。

[1]KNNOR E,NG R.Algorithms for mining distance-based outliers in large datasets[C]//Proc of the 24th VLDB Conference.New York:Morgan Kaufmann,1998:392-403.

[2]HAN J W,KAMBER M.Data Mining Concepts and Techniques[M].San Francisco:Morgan Kaufmann publishers,2001.

[3]BARNETT V,LEWIS T.Outliers in statistical data[M].New York:John Wiley and Sons,1994.

[4]PREPARATA F,SHAMOS M.Computational Geometry:An Introduction[M].USA:Springer-Verlag,1988.

[5]SARAWAGI S,AGRNWAL K,MEGIDDO N.Discovery-driven Exploration of OLAP Data Cubes[C]//Valencia:Proc of Int Conf Extending Database Technology,1998:168-182.

[6]BREUNIG M,KRIGEGL H P,NG R T,SANDER J.LOF:Identifying density-based local outlier[C]//ZytkowJ Med.Rauch Proc of the 3rd European Conference on Principles and Practice of knowledge Discovery in Databases.Prague:Springer,1999:262-270.

[7]AGARARWAL,YU P S.An effective and efficient algorithm for high-dimensional outlier detection[J].The International Journal on Very Large Data Bases,2005,14(2):211-221.

[8]ZHU C,KITAGAWA K,FALOUTSOS C.Example-Based Robust Outlier Detection in High Dimensional Datasets[C]//ICDM'05,2005:829-832.

[9]張繼福,蔣義勇,胡立華,等.基于概念格的天體光譜離群數(shù)據(jù)識(shí)別方法[J].自動(dòng)化學(xué)報(bào),2008,34(9):1060-1066.

[10]ZHANG J F,JIANG Y Y,CHANG KAI H.A Concept Lattice Based Outlier Mining Method in Low Dimensional Subspaces[J].Pattern Recognition Letters,2009,30(15):1434-1439.

[11]葛凌云,張繼福,蔡江輝.基于微粒群和子空間的離群數(shù)據(jù)挖掘算法研究[J].系統(tǒng)仿真學(xué)報(bào),2009,21(7):1897-1900.

[12]MOHAMED BOUGUESSA,SHENGRUI WANG.Mining Projected Clusters in High-Dimensional Spaces[J].IEEE Transactions On Knowledge And Data Engineering,2009,21(4):507-522.

[13]蔡江輝,張繼福.基于聚類的離群數(shù)據(jù)挖掘及應(yīng)用[J].太原重型機(jī)械學(xué)院學(xué)報(bào),2004,25(4):254-258.

[14]王瑋,張繼福.一種基于網(wǎng)格的概念格分布式構(gòu)造方法[J].太原科技大學(xué)學(xué)報(bào),2010,31(3):197-201.

[15]王磊.基于屬性相關(guān)分析的局部離群數(shù)據(jù)并行挖掘算法研究[D].太原:太原科技大學(xué),2011.

[16]CULLER D,KARP R,PATTERSON D.LogP:Towards a Realistic Model of Parallel Computation[C]//Proc 4th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming.ACM,New York,1993:1-12.

[17]DONGARRA J.Introduction to MPI[J].Int J Supercomputer Applications,1994,8(3/4):169-174.

[18]張繼福,趙旭俊.一種基于約束FP樹的天體光譜數(shù)據(jù)相關(guān)性分析方法[J].模式識(shí)別與人工智能,2009,22(4):639-646.