基于集成聚類的穩(wěn)定支持向量數(shù)據(jù)描述算法

支持向量數(shù)據(jù)的描述（svdd支持向量數(shù)據(jù)的描述）。常見的單類學(xué)習(xí)存在兩個主要問題:在構(gòu)建模型的過程中通常需要細致的參數(shù)選擇以平衡過擬合和欠擬合的矛盾,但該參數(shù)通常是全局惟一的,因此當(dāng)正類存在多模態(tài)或多密度分布特性時,單一的參數(shù)無法保證整個正類區(qū)域的數(shù)據(jù)描述效果,可能對正類某些區(qū)域刻畫能力較好而對其他區(qū)域刻畫能力較差,嚴重地影響整體性能;在無法得到負類樣本的情況下,由于無法評價單類模型,參數(shù)選擇將遇到較大困難,實際中雖然常用交叉驗證方法確定參數(shù),但單類模型難以評價的問題依然無法得到解決.現(xiàn)有研究提出了一些方法試圖解決以上問題.Wang等為解決以上問題,筆者首次將集成聚類和聚類穩(wěn)定性分析引入單類學(xué)習(xí),并以支持向量數(shù)據(jù)描述為實例提出了新的單類學(xué)習(xí)算法———ECS-SVDD(EnsembleCluster-basedStableSVDD).ECS-SVDD首先進行聚類穩(wěn)定性分析,在不依賴聚類評價指標(biāo)的情況下得到正類中聚類簇的個數(shù),之后通過集成聚類獲取正類中聚類簇的分布情況,并針對這些聚類簇分別構(gòu)建支持向量數(shù)據(jù)描述模型,最后采用最大融合體積方法融合各個支持向量數(shù)據(jù)描述構(gòu)建的邊界,得到最終的單類學(xué)習(xí)模型.相對于傳統(tǒng)單類學(xué)習(xí)方法以及其他解決多模態(tài)單類學(xué)習(xí)的方法,ECS-SVDD具有以下優(yōu)點:將聚類作為單類學(xué)習(xí)的一個步驟時,各聚類簇可以互為正負類樣本進行參數(shù)選擇,同時也避免交叉驗證帶來的大量額外時間消耗;將聚類穩(wěn)定性分析引入單類學(xué)習(xí),在不依賴于聚類評價指標(biāo)的情況下確定聚類簇個數(shù);將集成聚類引入單類學(xué)習(xí),可以有效地提升聚類的性能,同時由于聚類穩(wěn)定性分析步驟已經(jīng)完成了集成聚類所需的主要計算任務(wù),因此集成聚類步驟的實際計算復(fù)雜度幾乎可以忽略不計;以最小體積集優(yōu)化類單類學(xué)習(xí)算法為基礎(chǔ),首次提出通過最大融合體積方法融合各單類學(xué)習(xí)模型的描述邊界,可以避免基于聚類的單類學(xué)習(xí)方法中正類聚類簇間區(qū)域描述不穩(wěn)定的問題.1數(shù)據(jù)區(qū)域的描述研究的目標(biāo)是能夠被歸于最小體積集學(xué)習(xí)框架具體到單類分類問題中,最小體積集學(xué)習(xí)通過學(xué)習(xí)找到包含超過比例α的最小體積樣本空間子集.將μ指定為常用的勒貝格測度,即可自然地導(dǎo)出支持向量數(shù)據(jù)描述算法.不失一般性,筆者首先以支持向量數(shù)據(jù)描述算法為實例展開研究,之后分析筆者提出的方法在其他單類學(xué)習(xí)算法上的可擴展性.支持向量數(shù)據(jù)描述通過在特征空間構(gòu)建一個包裹正類樣本的最小超球完成單類學(xué)習(xí),其優(yōu)化問題可以描述為其中,R是超球的半徑,a是球心的坐標(biāo),ξ為直觀說明以上問題,生成一組二維人工數(shù)據(jù).該數(shù)據(jù)的正類包含一個低密度分布的香蕉型區(qū)域和一個高密度分布的正弦型區(qū)域,如圖1所示,其中“ue5fa”表示正類樣本,“×”表示負類樣本,黑色實線包裹的部分是支持向量數(shù)據(jù)描述算法得到的正類區(qū)域邊界.隨機選取50%的數(shù)據(jù)作為訓(xùn)練數(shù)據(jù),通過變化γ值可得多個不同的支持向量數(shù)據(jù)描述模型.由圖1可見,各個γ值均無法同時有效地刻畫兩個分布區(qū)域.在γ=20時,模型對香蕉型數(shù)據(jù)區(qū)域的描述效果較好,但對正弦分布區(qū)域的擬合較差,正類區(qū)域包含了較多的負類樣本;而當(dāng)γ=1時,模型對正弦分布區(qū)域的描述效果較好,但對香蕉型分布區(qū)域嚴重過擬合.以上兩種情況均不是對正類的有效描述.由式(1)可知,最小體積集學(xué)習(xí)模型在問題定義中僅考慮了全局性而忽略了局部特性,無法對不同分布特性的區(qū)域分別使用不同的參數(shù),故單類學(xué)習(xí)算法在多模態(tài)和多密度等情況下性能不佳.筆者通過向單類學(xué)習(xí)算法引入聚類步驟解決以上問題.首先通過聚類算法找到正類的各個聚類簇,之后對于各聚類簇分別構(gòu)建支持向量數(shù)據(jù)描述模型并集成得到最終的單類學(xué)習(xí)模型,以適應(yīng)多模態(tài)分布和多密度分布正類樣本的特性.然而,在引入聚類算法的同時也引入了聚類簇個數(shù)k這一需要指定的參數(shù).在聚類問題中,k的選擇對聚類算法的結(jié)果具有決定性影響2通過聚類穩(wěn)定分析加強個體學(xué)習(xí)2.1聚類穩(wěn)定性分析為選擇合適的聚類簇個數(shù)k,研究者們提出了多種方法,其中絕大多數(shù)需要預(yù)先指定一種聚類評價指標(biāo),之后通過對比不同k值情況下聚類模型的性能選擇最優(yōu)的k值.但對聚類性能的評價本身非常困難(1)當(dāng)k<k(2)當(dāng)k=k(3)當(dāng)k>k按照以上思路,使用多個k值重復(fù)運行包含隨機性的聚類算法,并利用聚類穩(wěn)定性指標(biāo)計算不同k值下的聚類穩(wěn)定性,選擇聚類穩(wěn)定性最高的k值,即可得到最合適的聚類簇個數(shù).2.2ecs-svdd算法在計算聚類穩(wěn)定性的過程中,最重要的步驟是計算聚類間的相似性,筆者選擇的聚類相似度度量指標(biāo)是歸一化互信息(NormalizedMutualInformation,NMI).源自信息論的歸一化互信息通過度量兩個聚類之間一致信息所占比例計算聚類的相似性.選擇歸一化互信息作為聚類相似性度量有兩個原因:在聚類穩(wěn)定性分析中,采用歸一化互信息作為聚類相似性度量指標(biāo)效果較好為說明使用歸一化互信息度量聚類穩(wěn)定性的效果,在四高斯數(shù)據(jù)(分別以矩形的4個頂點為均值點,單位矩陣為協(xié)方差矩陣生成的高斯分布數(shù)據(jù))和多密度分布二維數(shù)據(jù)(與圖1和圖2中使用的數(shù)據(jù)相同)上多次運行k-means算法,計算k=2到k=12情況下的聚類穩(wěn)定性.如圖3所示,左側(cè)的散點圖顯示了四高斯數(shù)據(jù)和多密度分布數(shù)據(jù)正類的分布情況,右側(cè)的折線圖表示歸一化互信息即聚類穩(wěn)定性指標(biāo),虛線標(biāo)出了聚類穩(wěn)定性最強時聚類簇的個數(shù).從圖3可以看出,當(dāng)k=k經(jīng)聚類穩(wěn)定性分析確定k值后,筆者進一步使用聚類集成得到正類數(shù)據(jù)的聚類簇分布信息.具體而言,在聚類穩(wěn)定性分析步驟保存各次聚類的結(jié)果,同時使用歸一化互信息指標(biāo)計算各聚類結(jié)果的權(quán)值,最后通過加權(quán)投票決定集成后的聚類結(jié)果.該過程中聚類算法本身的運行時間和歸一化互信息的計算是主要的計算復(fù)雜度來源,但聚類穩(wěn)定性分析步驟已將歸一化互信息指標(biāo)計算完畢,因此聚類集成幾乎沒有額外的計算復(fù)雜度.得到聚類結(jié)果之后,對各聚類簇分別使用單類學(xué)習(xí)算法建立模型.在對某一聚類簇建立模型時,其他聚類簇的樣本應(yīng)盡可能少地被包含在描述區(qū)域內(nèi),因此可以作為負類樣本參與參數(shù)選擇,有效解決單類學(xué)習(xí)算法在無負類樣本情況下參數(shù)選擇困難的問題.得到各聚類簇的單類學(xué)習(xí)模型之后,需要融合這些模型的決策邊界.由于各支持向量數(shù)據(jù)描述模型已找到各聚類簇分布集中的最小體積區(qū)域,在融合各支持向量數(shù)據(jù)描述邊界時不應(yīng)損失各支持向量數(shù)據(jù)描述模型的體積,否則不僅違背最小體積集學(xué)習(xí)的定義,而且各聚類簇之間的正類區(qū)域可能無法得到有效描述.因此,通過最大融合體積方法融合各支持向量數(shù)據(jù)描述模型的決策邊界,即樣本在任意支持向量數(shù)據(jù)描述邊界內(nèi)均被判定為目標(biāo)類.將以上算法稱為基于集成聚類的穩(wěn)定支持向量數(shù)據(jù)描述(ECS-SVDD),其算法流程如下,其中在聚類加權(quán)投票前需要對齊聚類標(biāo)簽ECS-SVDD算法流程如下:式中,n表示所有樣本的個數(shù),即D2.3ecs-svdd的計算復(fù)雜度支持向量數(shù)據(jù)描述算法需要解二次規(guī)劃問題.記正類樣本數(shù)為n,則支持向量數(shù)據(jù)描述的典型計算復(fù)雜度是O(n引入聚類和聚類穩(wěn)定性分析后,記聚類穩(wěn)定性分析的重復(fù)次數(shù)為p,最大聚類中心數(shù)為q,最終確定的聚類簇個數(shù)為k.以k-means作為聚類算法,則聚類穩(wěn)定性分析步驟的復(fù)雜度是O(npq).ECS-SVDD中集成聚類步驟的主要計算內(nèi)容在聚類穩(wěn)定性分析步驟已經(jīng)完成,可忽略ECS-SVDD集成聚類步驟的計算復(fù)雜度.因此,ECS-SVDD的計算復(fù)雜度是O(npq)+O(n2.4ecs-svdd的低體積融合ECS-SVDD采用支持向量數(shù)據(jù)描述作為單類學(xué)習(xí)算法對各聚類簇建立模型.這里的支持向量數(shù)據(jù)描述可以替換為其他單類學(xué)習(xí)算法.ECS-SVDD在最終融合各聚類簇邊界時采用了最大體積融合方法,因此替換的單類學(xué)習(xí)算法應(yīng)能夠歸入最小包含體積集合學(xué)習(xí)框架3實驗3.1ecs-svdd與單類分類算法的對比實驗數(shù)據(jù)是從機器學(xué)習(xí)領(lǐng)域常用的UCI標(biāo)準(zhǔn)數(shù)據(jù)集中選擇的7個二分類數(shù)據(jù)集.按照單類學(xué)習(xí)研究中通行的方法實驗主要對比單個支持向量數(shù)據(jù)描述算法與ECS-SVDD算法,同時參與對比的單類學(xué)習(xí)方法包括混合高斯概率密度估計方法(MOG)和K-means單類分類算法單類學(xué)習(xí)算法的評價問題尚未得到充分解決從表2的實驗結(jié)果可以看出,在多數(shù)數(shù)據(jù)集上,ECS-SVDD較其他算法性能更優(yōu),說明與同類單類學(xué)習(xí)算法和單個支持向量數(shù)據(jù)描述算法相比,ECS-SVDD算法能夠更好地完成單類分類任務(wù).3.2在惡意程序檢測問題上的應(yīng)用惡意程序檢測是計算機安全領(lǐng)域的重要問題,傳統(tǒng)方法使用二分類算法建立惡意程序檢測模型.但是,非惡意程序功能各異,數(shù)量巨大,難以充分采樣.此外,對惡意程序檢測問題而言,將非惡意程序判定為惡意是難以容忍的,因此將惡意程序類別作為正類,使用單類學(xué)習(xí)建立惡意程序檢測模型,不僅能夠利用收集到的大量惡意樣本,而且可以有效降低誤檢的風(fēng)險.實驗收集了來自46個具有代表性的惡意程序家族的15478個惡意程序樣本以及2898個非惡意程序樣本,使用基于全系統(tǒng)模擬器的惡意程序動態(tài)分析沙盒Osiris由表3可見,ECS-SVDD在各項評價指標(biāo)上均優(yōu)于其他算法,同時由圖4可見,ECS-SVDD以ROC分析得到的性能評價也優(yōu)于其他算法.這說明相對于其他單類學(xué)習(xí)算法,ECS-SVDD能夠更有效地擬合較復(fù)雜的惡意程序類內(nèi)部分布情況,完成惡意程序檢測任務(wù).4ecs-svdd算法針對單類學(xué)習(xí)對多模態(tài)或多密度分布描述效果較差的問題,筆者提出了一種新的基于集成聚類和聚類穩(wěn)定性分析的單類學(xué)習(xí)算法———ECS-SVDD.該算法首先使用聚類穩(wěn)定性分析挖掘正類中聚類簇的個數(shù),之后使用集成聚類劃分聚類簇并對各聚類簇分別使用支持向量