基于PCA—LDA和KNN—SMO的數(shù)據(jù)碎片分類識(shí)別算法

傅德勝++經(jīng)正俊

摘要：在計(jì)算機(jī)取證領(lǐng)域，數(shù)據(jù)碎片的取證分析已成為獲取數(shù)字證據(jù)的一種重要手段。本文針對(duì)取證中數(shù)據(jù)碎片的取證問(wèn)題提出了一種新的基于內(nèi)容特征的數(shù)據(jù)碎片類型識(shí)別算法，該方法首先對(duì)數(shù)據(jù)碎片進(jìn)行分塊主成分分析PCA后，對(duì)PCA特征向量進(jìn)行線性鑒別分析LDA獲取組合特征向量，然后利用K最鄰近KNN算法和序列最小優(yōu)化SMO算法組成融合分類器，運(yùn)用獲取的組合特征向量對(duì)數(shù)據(jù)碎片進(jìn)行分類識(shí)別。實(shí)驗(yàn)表明，該算法與其他相關(guān)算法相比，具有較高的識(shí)別準(zhǔn)確率和識(shí)別速率，取得了良好的識(shí)別效果。

關(guān)鍵詞：數(shù)據(jù)碎片；計(jì)算機(jī)取證；PCA-LDA；KNN-SMO

中圖分類號(hào)：TP393.08

文獻(xiàn)標(biāo)識(shí)碼：A

DOI： 10.3969/j.issn.1003-6970.2015.07.005

0 引言

在計(jì)算機(jī)取證中，取證人員常會(huì)遇到數(shù)據(jù)碎片問(wèn)題，由于數(shù)據(jù)碎片位于存儲(chǔ)介質(zhì)的底層，且其元信息遭到丟失或損壞，一般的基于擴(kuò)展名和魔術(shù)的識(shí)別方法對(duì)其失效，不能夠?qū)?shù)據(jù)碎片類型進(jìn)行正確的識(shí)別，從而對(duì)后續(xù)的數(shù)據(jù)恢復(fù)等工作造成困難。因此，如何對(duì)當(dāng)前已知的數(shù)據(jù)類型的數(shù)據(jù)碎片進(jìn)行自動(dòng)化分析并提取其特征，用于對(duì)未知類型的數(shù)據(jù)塊（可能為整個(gè)文件，也可能為數(shù)據(jù)碎片）的分類及檢測(cè)，已經(jīng)成為目前國(guó)內(nèi)外研究的熱點(diǎn)和難點(diǎn)問(wèn)題之一，亟需在數(shù)據(jù)碎片類型識(shí)別的精度及速度上有所突破。

在現(xiàn)有的數(shù)據(jù)碎片分類識(shí)別算法中，主要方法有基于字節(jié)頻率的分布特征識(shí)別法，基于統(tǒng)計(jì)量特征識(shí)別法等。基于字節(jié)頻率的分布特征識(shí)別法基本思想是通過(guò)統(tǒng)計(jì)數(shù)據(jù)碎片中字節(jié)的頻率分布（Byte Fre-quency Distribution，BFD）直方圖作為特征向量進(jìn)行識(shí)別，Mason等第一個(gè)提出了基于BFD的識(shí)別方法，但該算法的識(shí)別精度很低。Li等利用多圖心即多個(gè)特征向量來(lái)表征一種數(shù)據(jù)碎片類型方法較好的提高了識(shí)別精度，但作者未利用文件中間的數(shù)據(jù)碎片進(jìn)行測(cè)試，而是從固定位置的文件頭開(kāi)始，存在局限性。Martin等在考慮BFD特征的基礎(chǔ)上，添加了部分字節(jié)之間的順序利用字節(jié)間的變化率來(lái)進(jìn)行分類識(shí)別，但識(shí)別效果并不理想。Xu等通過(guò)離散余弦變換（Discrete Cosine Transform，DCT）利用中低頻系數(shù)和BFD作為特征向量進(jìn)行識(shí)別很好地提高了識(shí)別精度。基于統(tǒng)計(jì)量特征的識(shí)別方法的基本思想是利用數(shù)據(jù)碎片的統(tǒng)計(jì)量（如均值、標(biāo)準(zhǔn)差、峰值等）進(jìn)行分析識(shí)別。Robert等首先提出了基于統(tǒng)計(jì)特征的數(shù)據(jù)碎片識(shí)別方法，利用不同文件類型的均值、標(biāo)準(zhǔn)差的圖線不同進(jìn)行區(qū)分，但是后期識(shí)別工作需要人工觀測(cè)。Sarah等將滑動(dòng)窗口思想引入到統(tǒng)計(jì)分析中，以及采用二次分析取得了較好的分類效果。William等利用16種統(tǒng)計(jì)量進(jìn)行分析識(shí)別，但其實(shí)驗(yàn)采用的數(shù)據(jù)集只有四種類型，較為局限。曹鼎等將定長(zhǎng)和變長(zhǎng)元組運(yùn)用于統(tǒng)計(jì)特征中，有效的提高了識(shí)別的準(zhǔn)確率，但是其實(shí)驗(yàn)數(shù)據(jù)集也只有四種類型，實(shí)驗(yàn)數(shù)據(jù)集過(guò)小。

以上數(shù)據(jù)碎片類型的識(shí)別方法中，由于在特征選取上對(duì)數(shù)據(jù)碎片的描述不夠，導(dǎo)致不能夠很好識(shí)別碎片類型，此外很多作者實(shí)驗(yàn)是局限在較小的私有數(shù)據(jù)集上進(jìn)行，實(shí)驗(yàn)效果的有效性難以保證。

針對(duì)上述問(wèn)題，本文提出了基于PCA-LDA和KNN-SMO的數(shù)據(jù)碎片分類識(shí)別算法，對(duì)數(shù)據(jù)碎片先后采用PCA和LDA兩種變換方法，獲得組合特征向量，接著利用KNN和SMO組成的融合分類器進(jìn)行分類識(shí)別。通過(guò)PCA-LDA變換能夠充分提取出數(shù)據(jù)碎片的主要特征，且利用KNN和SMO融合的分類器，一方面利用了KNN快速分類的能力，另一方面利用了SMO在克服小樣本問(wèn)題上的優(yōu)勢(shì)，從而提高了數(shù)據(jù)碎片類型的識(shí)別精度與速度。并且實(shí)驗(yàn)中采用數(shù)據(jù)量大的公開(kāi)數(shù)據(jù)集進(jìn)行測(cè)試，保證了實(shí)驗(yàn)結(jié)果的有效性。

1 PCA-LDA組合特征的提取

PCA即主成分分析技術(shù)，其旨在利用降維的思想，把多指標(biāo)轉(zhuǎn)化為少數(shù)幾個(gè)綜合指標(biāo)。

LDA即線性鑒別分析，其基本思想是將高維的模式樣本投影到最佳鑒別矢量空間，以達(dá)到抽取分類信息和壓縮特征空間維數(shù)的效果。由于LDA方法采用了使得樣本能夠正確分類識(shí)別的先驗(yàn)知識(shí)，即尋找最優(yōu)投影方向，使得投影后向量的類間離散度矩陣和類內(nèi)離散度矩陣的比率最大化，能夠提高識(shí)別率。

本文算法中關(guān)于數(shù)據(jù)碎片PCA-LDA組合特征向量的提取方法如下：

（1）將數(shù)據(jù)碎片分塊后，利用主PCA在投影方向上提取特征向量，首先按照公式（1）計(jì)算樣本協(xié)方差矩

其中 ，即為樣本均值。

（2）選取S中前f個(gè)最大特征值組成特征向量U，如式（2）所示：

（3）計(jì)算f維特征空間類間離散度，如式（3）所示：

其中P（i）為先驗(yàn)概率，其中u為所有樣本向量的均值向量，u_i為第i個(gè)樣本類別的均值向量。

（4）計(jì)算t維特征空間類內(nèi)離散度，如式（4）所示：

（5）求解矩陣Swl Sb的特征值，選取，個(gè)最大特征值組成的向量為最終的組合特征向量V，如式（5）所示：

2 KNN-SMO融合分類器的構(gòu)造

KNN分類算法，是一個(gè)理論上比較成熟的方法，也是最簡(jiǎn)單的機(jī)器學(xué)習(xí)算法之一。該方法的原理是如果一個(gè)樣本在特征空間中的k個(gè)最相似（即特征空間中最鄰近）的樣本中的大多數(shù)屬于某一個(gè)類別，則該樣本也屬于這個(gè)類別 ?；久枋鋈缦拢?/p>

對(duì)一個(gè)C類別問(wèn)題，每類有N_i個(gè)樣本，i=1，2，…，C，則第i類 判別函數(shù)為公式（6）-（7）所示：

其中計(jì)算樣本的距離可以使用樣本距離有歐氏距離、曼哈頓距離以及范數(shù)等。

SMO算法由Microsoft Research的John C.Platt在1998年提出，并成為最快的二次規(guī)劃優(yōu)化算法。其基本思想如下：

對(duì)于輸入數(shù)據(jù)集

其主要步驟如下：第一步選取一對(duì)參數(shù) 和 ，選取方法使用啟發(fā)式方法。第二步，固定除被選取的參數(shù)之外的其他參數(shù)，確定W極值條件下的a和 ，其中 由 表示。

基于KNN和SMO的融合分類器構(gòu)造方案如下：

首先利用KNN算法對(duì)訓(xùn)練集進(jìn)行修剪，根據(jù)每個(gè)樣本與其最近鄰的K的樣本的類別的異同決定其取舍.然后再用SVM進(jìn)行訓(xùn)練獲得。實(shí)驗(yàn)表明，與經(jīng)典分類器算法相比，KNN-SMO不單在分類正確率上有了較大提高，而且分類速度更快，并能適用更大規(guī)模的訓(xùn)練樣本集。

3 數(shù)據(jù)碎片類型識(shí)別

利用PCA-LDA獲得的數(shù)據(jù)碎片的組合特征向量后，利用KNN-SMO融合分類器進(jìn)行識(shí)別，即首先用KNN對(duì)樣本進(jìn)行過(guò)濾，在剩下的樣本中再利用SMO算法進(jìn)行分類識(shí)別，最終完成識(shí)別過(guò)程。

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

本文在實(shí)驗(yàn)中選取的數(shù)據(jù)集是文獻(xiàn)和等所采用的公共的數(shù)據(jù)集govdocsl，該數(shù)據(jù)集由Garfinkel等發(fā)布，共有1，000，000個(gè)不同類型的文件。本文在實(shí)驗(yàn)中共選取了30種不同類型的文件進(jìn)行測(cè)試，文件類型如表1所示：在實(shí)驗(yàn)中，每種類型隨機(jī)選取10個(gè)以上的文件進(jìn)行碎片化，碎片的大小以1024字節(jié)為標(biāo)準(zhǔn)，并保證碎片化后每種類型的文件含有5000個(gè)以上的碎片，然后再?gòu)闹羞x取1000個(gè)數(shù)據(jù)碎片進(jìn)行實(shí)驗(yàn)。

此外，大部分的數(shù)據(jù)類型在頭部可能會(huì)含有一些能夠標(biāo)識(shí)數(shù)據(jù)類型的元信息，而尾部的最后一個(gè)數(shù)據(jù)碎片可能不夠特定的碎片大小，因此在實(shí)驗(yàn)忽略了文件頭部的第一個(gè)數(shù)據(jù)碎片和文件尾部的最后一個(gè)數(shù)據(jù)碎片。

本文使用Matlab 2013Rb軟件對(duì)本文的算法進(jìn)行實(shí)現(xiàn)，然后對(duì)數(shù)據(jù)碎片類型進(jìn)行識(shí)別測(cè)試。此外，為了驗(yàn)證本文算法的優(yōu)越性，本文對(duì)文獻(xiàn) 、 和 的算法進(jìn)行了實(shí)現(xiàn)，然后與本文算法一起進(jìn)行對(duì)比實(shí)驗(yàn)。

實(shí)驗(yàn)結(jié)果評(píng)價(jià)上從查重率、查準(zhǔn)率和F值三方面考慮，分別如公式（10）-（12）所示：

其中A、B和C的含義如表2所示。

表3給出了不同算法下有測(cè)試樣本P、R和F值均值對(duì)比結(jié)果，從表中數(shù)據(jù)可以看出本文算法的P值均值、R值均值和F值均值分別為0.9327、0.9284和0.9339明顯優(yōu)于另外三個(gè)算法的識(shí)別結(jié)果，這是由于利用利用數(shù)據(jù)碎片的PCA-LDA特征作為特征向量，能夠更好地描述數(shù)據(jù)碎片的主要特征，并且利用KNN-SMO融合分類器能夠更好地對(duì)碎片類型進(jìn)行識(shí)別，可見(jiàn)本文算法的有效性。

表4給出了運(yùn)用本文分類器和其余經(jīng)典分類器的識(shí)別對(duì)比結(jié)果，從表中數(shù)據(jù)可以看出本文所提出的KNN-SMO融合分類器的P值均值、R值均值和F值均值分別為0.9327、0.9284和0.9339明顯優(yōu)于其他經(jīng)典分類器的識(shí)別結(jié)果，運(yùn)行時(shí)間均值為17.28s除了比NaIve Bayes略低外，冥想由于LIBSVM和LIBLINEAR分類識(shí)別法。這是由于一方面利用KNN分類器提高了識(shí)別效率，另一方面利用SMO再次對(duì)剩余樣本進(jìn)行識(shí)別，增加了識(shí)別的精度。

圖1給出了四種常見(jiàn)典型文件類型DOC、JPEG、PDF和ZIP在三種算法下F值的對(duì)比圖，從圖1可以看出本文算法明顯優(yōu)于其他三種算法，四種文件類型下F值均在0.95及其以上，可見(jiàn)本文算法對(duì)常見(jiàn)文件類型具有很高的識(shí)別精度。

5 總結(jié)

本文針對(duì)數(shù)據(jù)碎片的識(shí)別，提出了一種PCA-LDA和KNN-SMO的數(shù)據(jù)碎片分類識(shí)別算法，該方法通過(guò)對(duì)數(shù)據(jù)碎片進(jìn)行PCA和LDA變換獲得組合特征向量，然后利用KNN和SMO的融合分類器進(jìn)行分類識(shí)別。實(shí)驗(yàn)表明，本文算法與其他相關(guān)算法相比，具有更高的識(shí)別準(zhǔn)確率和更快的識(shí)別速率。