康耀龍,馮麗露,張景安

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

1 引言

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

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

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

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

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

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

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

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

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

設Imn表示新形成的項集,|tidset(Imn)|的計算通過diffset完成,其公式為

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

(1)

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

(2)

式中:In和Im均為項集,兩者前k-1個項為相同項,Imn=Im∪In。

新形成的子群Smn與Imn可完成相同屬性以及屬性值的共享,則tidset(Smn)=tidset(Imn);由于tidset是diffset計算的依據(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)

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

2.2 異常子群挖掘

2.2.1 算法原理

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

(5)

(6)

設式(6)為劃分準則,即

(7)

(8)

(9)

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

(10)

(11)

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

(12)

(13)

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

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

(14)

式中,對角矩陣用B表示。

(15)

設

(16)

(17)

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

(18)

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

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

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

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

2)對相似度矩陣進行求解。

3)求解矩陣B。

4)為生成約化圖,對正約束頂點進行合并處理。

5)對步驟2)、3)進行更新處理。

6)采用二分類對全部的簇進行劃分處理。

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

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

9)對形成的簇進行判斷,如果為K個,則直接輸出結果;反之回轉步驟6)。

10)輸出聚類簇。

3 測試分析

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

3.1 最佳閾值確定

候選子群的選擇,需確定支持度最佳閾值,以候選子群選擇過程中所需的計算開銷作為衡量標準,選取開銷最小的閾值為最佳閾值,結果用圖1描述。

圖1 最佳閾值測試結果

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

3.2 挖掘性能和效果測試

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

(19)

(20)

式中:準確率用AC表示;si和ri均表示標簽,分別對應真實結果和計算結果;C和C′均表示標簽集合,分別對應實際結果和計算結果;C和C′的互信息用NMI(C,C′)表示;C和C′的信息熵分別用H(C)和H(C′)表示。

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

圖2 測試結果

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

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

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

表1 三種方法測試結果

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

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

圖3 三種方法的對比結果

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

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

4 結論

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