基于譜聚類的多維數(shù)據(jù)集異常子群挖掘方法

康耀龍,馮麗露,張景安

(1. 山西大同大學(xué)計(jì)算機(jī)與網(wǎng)絡(luò)工程學(xué)院,山西 大同 037009;2. 山西大同大學(xué),山西 大同 037009;3. 山西大同大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)中心,山西 大同 037009)

1 引言

多維數(shù)據(jù)集中的異常數(shù)據(jù)深度挖掘,是實(shí)現(xiàn)數(shù)據(jù)集中數(shù)據(jù)有效利用的基礎(chǔ),多維數(shù)據(jù)集是一種結(jié)構(gòu),包含多種維度和度量值,前者是實(shí)現(xiàn)多維數(shù)據(jù)結(jié)構(gòu)的定義,后者則是將數(shù)值或者數(shù)據(jù)提供給感興趣的用戶。所有的多維數(shù)據(jù)集均有自己的結(jié)構(gòu),該結(jié)構(gòu)是一種多種數(shù)據(jù)表集合,位于傳統(tǒng)數(shù)據(jù)倉(cāng)庫(kù)中[1]。異常子群指的是符合特定條件下的子群,即為在多維數(shù)據(jù)集切片內(nèi)存在的部分頻繁項(xiàng)集,其可能不是整個(gè)結(jié)構(gòu)的頻繁項(xiàng)集[2]。分析多維數(shù)據(jù)集時(shí),以用戶需求為依據(jù),確定上述異常子群,但是在確定過(guò)程中,由于數(shù)據(jù)集的維度存在變化性,處于不斷增加狀態(tài),導(dǎo)致異常子群的獲取難度增加。譜聚類是以譜圖理論為基礎(chǔ)的一種聚類算法,其在解決多形狀樣本空間聚類方面具備顯著優(yōu)勢(shì),可完成全局收斂,獲取最佳聚類結(jié)果[3]。

異常子群挖掘方法在挖掘過(guò)程中,受到多維結(jié)構(gòu)的影響,導(dǎo)致挖掘結(jié)果均存在局限性,甚至無(wú)法完成高維度目標(biāo)的挖掘。肖文[4]等人提出了基于數(shù)據(jù)集稀疏度的挖掘方法,丁建立[5]等人提出了基于時(shí)間序列的挖掘方法,各自通過(guò)對(duì)差異度進(jìn)行度量和異常聚類實(shí)現(xiàn)目標(biāo)挖掘,但是,兩者均在挖掘深度上存在相對(duì)不足,導(dǎo)致挖掘結(jié)果存在一定的差異性。因此,本文研究基于譜聚類的多維數(shù)據(jù)集異常子群挖掘方法,依據(jù)用戶指定的參數(shù),完成多維數(shù)據(jù)集中的異常子群準(zhǔn)確挖掘。

2 基于譜聚類的多維數(shù)據(jù)集異常子群挖掘

基于譜聚類的多維數(shù)據(jù)集異常子群挖掘由兩部分完成,第一部分是預(yù)處理,通過(guò)對(duì)數(shù)據(jù)進(jìn)行脫機(jī)計(jì)算,獲取數(shù)據(jù)集中存在的部分候選子群;第二部分是異常子集挖掘,基于L1范數(shù)的約束譜聚類算法挖掘候選子群,獲取挖掘結(jié)果。

2.1 多維數(shù)據(jù)集預(yù)處理

設(shè)D表示多維數(shù)據(jù)集,其為給定狀態(tài);C和Z均表示閾值,依次分別對(duì)應(yīng)覆蓋率和支持度;A表示屬性集,屬于用戶輸入,以其為依據(jù),將D中的所有子群返回[6]。

在C中的顯著子群即為構(gòu)成異常模式的子群,S表示特定的顯著子群;|tidset|和tidset分別表示編號(hào)的數(shù)量和集合;S的覆蓋率用cou(S)表示,則結(jié)合C的概念得出:|tidset(S)|=cou(S)×|D|;所以,新生成的S是否為顯著子群的判斷,可通過(guò)|tidset(S)|≥mincoou×|D|完成。

基本選擇器ei生成:ad表示離散屬性,其屬性值則用υd表示;則ei為(ad=υd)。連續(xù)屬性用ac表示,由于無(wú)法對(duì)ac中形成的各個(gè)屬性均生成一個(gè)(ad=υd),所以,需使其形成離散化區(qū)間,其通過(guò)劃分手段完成,且劃分的總數(shù)量用L表示,即{[l0,l1),[l1,l2),…,[lL-2,lL-1),[lL-1,lL)},在此基礎(chǔ)上,完成相應(yīng)的ei生成,同時(shí)構(gòu)建ei對(duì)應(yīng)的tidset;|tidset(ei)|≥mincoou×|D|,使ei完成一階子群的形成,且Si=ei標(biāo)準(zhǔn);基于此可得:|tidset(Si)|=|tidset(ei)|≥mincoou×|D|,此時(shí)D中所有的一階顯著子群即為生成的同階子群。

為保證可靠獲取顯著子群,采用屬性集子組元組概念建立顯著子群索引;該概念存儲(chǔ)于k階子群文件中,其包含兩部分,分別為屬性集相同的子群和該屬性集自身[7],且前者屬于相同k階。k階子群文件中的各個(gè)索引均由k階屬性顯著子集ASk和各屬性集子組構(gòu)成,且后者的屬性集需為ASk;在此基礎(chǔ)上,獲取所有子群?；谏鲜龇治隹芍?各個(gè)屬性即表示各個(gè)維度,其只可具備一個(gè)屬性值[8]。如果ω表示ei的屬性數(shù)量,則0≤k≤ω。

設(shè)Imn表示新形成的項(xiàng)集,|tidset(Imn)|的計(jì)算通過(guò)diffset完成,其公式為

diffset(Imn)=diffset(In)-diffset(Im)

(1)

|tidset(Imn)|=|tidset(Im)|-diffset(Im)-diffset(In)

(2)

式中:In和Im均為項(xiàng)集,兩者前k-1個(gè)項(xiàng)為相同項(xiàng),Imn=Im∪In。

新形成的子群Smn與Imn可完成相同屬性以及屬性值的共享,則tidset(Smn)=tidset(Imn);由于tidset是diffset計(jì)算的依據(jù),可得diffset(Smn)=diffset(Imn)。基于此,Smn是否是顯著子群的判斷,可依據(jù)diffset完成,求解|tidset(Smn)|的公式為

diffset(Smn)=diffset(Sn)-diffset(Sm)

(3)

|tidset(Smn)|=|tidset(Sm)|-diffset(Sm)-diffset(Sn)

(4)

通過(guò)上述方法獲取每個(gè)生成的顯著子群Smn后,以其ad和υd為依據(jù),完成編號(hào)(sid(Smn))的形成,在此基礎(chǔ)上,完成索引diffset(Smn)和|tidset(Smn)|的建立,同時(shí),通過(guò)迭代獲取上一層子群的diffset和|tidset|,由此獲取D中存在的部分候選子群Si。

2.2 異常子群挖掘

2.2.1 算法原理

本文采用屬于半監(jiān)督譜聚類算法的基于L1范數(shù)的約束譜聚類算法完成異常子群挖掘。

(5)

(6)

設(shè)式(6)為劃分準(zhǔn)則,即

(7)

(8)

(9)

為獲取軟約束歸一化劃分函數(shù),結(jié)合式(7)、(8)、(9)完成,得到

(10)

(11)

參數(shù)γ可通過(guò)自身大小的調(diào)整用于權(quán)重的控制,且該權(quán)重屬于歸一化劃分和沖突約束[10]。為保證劃分結(jié)果為最佳結(jié)果,采用連續(xù)放松代替式(10),則約束沖突代價(jià)計(jì)算公式為

(12)

(13)

式中:指示向量用f表示,用于劃分,其最大和最小值分別用max(f)和min(f)表示。最優(yōu)劃分結(jié)果可通過(guò)式(12)(13)獲取。

對(duì)歸一化劃分進(jìn)行約束的代價(jià)函數(shù)計(jì)算公式為

(14)

式中,對(duì)角矩陣用B表示。

(15)

設(shè)

(16)

(17)

則可獲取代價(jià)函數(shù)的計(jì)算公式為

(18)

通過(guò)式(18)即可獲取Fγ(f)的結(jié)果,該結(jié)果即為挖掘最優(yōu)解。

2.2.2 多維數(shù)據(jù)集異常子群挖掘流程

結(jié)合候選子群的類別多樣化特征,對(duì)異常子集的挖掘,也可看作是對(duì)多類別的候選子群進(jìn)行聚類。為保證挖掘效果,實(shí)現(xiàn)不同類別候選子群的最佳聚類,將該聚類采用多類別的歸一化圖劃分替代。在該過(guò)程中,采用整合方式對(duì)正約束點(diǎn)進(jìn)行處理,并對(duì)頂點(diǎn)的度和邊進(jìn)行重現(xiàn)定義,以此保證全部的正約束和劃分不會(huì)發(fā)生沖突,實(shí)現(xiàn)約化圖的形成,完成候選子群的挖掘,即完成異常子群挖掘。

1)輸入:候選子群Si(i=1,2,…,n)、其類別數(shù)量k、正負(fù)約束。

2)對(duì)相似度矩陣進(jìn)行求解。

3)求解矩陣B。

4)為生成約化圖,對(duì)正約束頂點(diǎn)進(jìn)行合并處理。

5)對(duì)步驟2)、3)進(jìn)行更新處理。

6)采用二分類對(duì)全部的簇進(jìn)行劃分處理。

7)求解代價(jià)函數(shù),為經(jīng)過(guò)劃分的多類劃分。

8)在多類劃分函數(shù)中,采用劃分手段對(duì)其中最小的函數(shù)進(jìn)行處理。

9)對(duì)形成的簇進(jìn)行判斷,如果為K個(gè),則直接輸出結(jié)果;反之回轉(zhuǎn)步驟6)。

10)輸出聚類簇。

3 測(cè)試分析

為分析本文方法在多維數(shù)據(jù)集異常子群挖掘中的應(yīng)用性能和效果,選取Wine數(shù)據(jù)集為測(cè)試對(duì)象,該對(duì)象內(nèi)共有三類樣本數(shù)據(jù)(采用1、2、3進(jìn)行編號(hào)),數(shù)據(jù)集中共有樣本數(shù)量178個(gè),各類樣本數(shù)量依次分別為59個(gè)、71個(gè)和48個(gè);十三種特征,其中各個(gè)特征均表示相對(duì)應(yīng)的成分含量。測(cè)試采用Matlab2016b仿真軟件完成。

3.1 最佳閾值確定

候選子群的選擇,需確定支持度最佳閾值,以候選子群選擇過(guò)程中所需的計(jì)算開(kāi)銷作為衡量標(biāo)準(zhǔn),選取開(kāi)銷最小的閾值為最佳閾值,結(jié)果用圖1描述。

圖1 最佳閾值測(cè)試結(jié)果

對(duì)圖1測(cè)試進(jìn)行分析后可得:在不同閾值取值情況下,所需開(kāi)銷呈現(xiàn)變化狀態(tài),當(dāng)閾值取值為0.5時(shí),開(kāi)銷最小,僅為0.27s。因此本文最佳支持度閾值設(shè)定為0.5,并用于后續(xù)所有測(cè)試。

3.2 挖掘性能和效果測(cè)試

采用挖掘準(zhǔn)確率、標(biāo)準(zhǔn)化互信息作為衡量本文方法的指標(biāo),前者用于衡量方法的效果,后者則用于衡量方法的性能,其取值范圍為[0,1],越接近1表明性能越好。兩者公式分別為

(19)

(20)

式中:準(zhǔn)確率用AC表示;si和ri均表示標(biāo)簽,分別對(duì)應(yīng)真實(shí)結(jié)果和計(jì)算結(jié)果;C和C′均表示標(biāo)簽集合,分別對(duì)應(yīng)實(shí)際結(jié)果和計(jì)算結(jié)果;C和C′的互信息用NMI(C,C′)表示;C和C′的信息熵分別用H(C)和H(C′)表示。

為分析本文方法的挖掘性能,以式(19)、(20)為依據(jù),測(cè)試本文方法在約束數(shù)量變化情況下準(zhǔn)確率、標(biāo)準(zhǔn)化互信息的變化情況,結(jié)果用圖2描述。

圖2 測(cè)試結(jié)果

對(duì)圖2進(jìn)行分析后可得:監(jiān)督約束數(shù)量的增加,本文方法的準(zhǔn)確率和標(biāo)準(zhǔn)化互信息隨之增加,監(jiān)督約束數(shù)量越多,本文方法的性能越佳,越可保證異常子群挖掘的效果,因此,為保證本文方法的挖掘效果,需保證其監(jiān)督性能較好,約束數(shù)量設(shè)定在320以上。

為直觀衡量本文方法的優(yōu)劣,將基于數(shù)據(jù)集稀疏度的方法(文獻(xiàn)[4]方法)和基于時(shí)間序列的方法(文獻(xiàn)[5]方法)作為本文方法的對(duì)比方法,完成對(duì)此測(cè)試。

為分析本文方法的優(yōu)劣,根據(jù)式(19)、(20)測(cè)試三種方法在不同近鄰點(diǎn)數(shù)量下的準(zhǔn)確率、標(biāo)準(zhǔn)化互信息的測(cè)試結(jié)果,用表1描述。

表1 三種方法測(cè)試結(jié)果

對(duì)表1進(jìn)行分析后可得:在不同最近鄰數(shù)量本文方法的準(zhǔn)確率、標(biāo)準(zhǔn)化互信息值均為最佳,表明本文方法的效果和性能均優(yōu)于兩種對(duì)比方法,可保證在良好的性能下實(shí)現(xiàn)多維數(shù)據(jù)集異常子群的準(zhǔn)確挖掘,這是由于本文方法可直接對(duì)多維數(shù)據(jù)集內(nèi)的顯著子群進(jìn)行計(jì)算并建立候選子群,使挖掘性能顯著提升。

本文以第2類數(shù)據(jù)作指定需求數(shù)據(jù),采用三種方法分別對(duì)目標(biāo)對(duì)象進(jìn)行挖掘,統(tǒng)計(jì)三種方法的挖掘效果,以此定量分析三種方法的挖掘效果,用圖3描述。

圖3 三種方法的對(duì)比結(jié)果

對(duì)圖3進(jìn)行分析可得:三種方法在對(duì)多維數(shù)據(jù)集進(jìn)行挖掘中,挖掘數(shù)據(jù)量增加,表示數(shù)據(jù)集的維度在增加,在此情況下,文本方法的挖掘性能穩(wěn)定,維度的增加對(duì)方法的挖掘效果并沒(méi)造成影響;但是兩種對(duì)比方法則在維度的增加下,挖掘效果逐漸降低,當(dāng)樣本數(shù)量超過(guò)121時(shí),兩種方法則無(wú)法繼續(xù)深度挖掘。

表明本文方法具備更佳的多維數(shù)據(jù)集異常子群的挖掘效果,可實(shí)現(xiàn)數(shù)據(jù)深度挖掘,且穩(wěn)定性較好。

4 結(jié)論

由于多維數(shù)據(jù)集的多維特征,導(dǎo)致用戶想對(duì)其內(nèi)的信息數(shù)據(jù)進(jìn)行調(diào)取或者查看時(shí),無(wú)法實(shí)現(xiàn)數(shù)據(jù)的深度挖掘,影響數(shù)據(jù)調(diào)取或者使用情況,因此,當(dāng)在用戶確定數(shù)據(jù)類別或者指定的情況下,其所需的目標(biāo)數(shù)據(jù)即可用異常子集描述,為了完成該類數(shù)據(jù)子集的挖掘,本文提出基于譜聚類的多維數(shù)據(jù)集異常子群挖掘方法,該方法以候選子群的選取為基礎(chǔ),通過(guò)譜聚類方法完成特定情況下的異常數(shù)據(jù)子群挖掘。并通過(guò)相關(guān)測(cè)試表明:本文方法具備良好的異常子群挖掘性能以及效果,在標(biāo)準(zhǔn)化互信息值較高的情況下,實(shí)現(xiàn)指定的情況的異常數(shù)據(jù)子群挖掘。