基于PCA—LDA和KNN—SMO的數據碎片分類識別算法

傅德勝++經正俊

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

關鍵詞：數據碎片；計算機取證；PCA-LDA；KNN-SMO

中圖分類號：TP393.08

文獻標識碼：A

DOI： 10.3969/j.issn.1003-6970.2015.07.005

0 引言

在計算機取證中，取證人員常會遇到數據碎片問題，由于數據碎片位于存儲介質的底層，且其元信息遭到丟失或損壞，一般的基于擴展名和魔術的識別方法對其失效，不能夠對數據碎片類型進行正確的識別，從而對后續的數據恢復等工作造成困難。因此，如何對當前已知的數據類型的數據碎片進行自動化分析并提取其特征，用于對未知類型的數據塊（可能為整個文件，也可能為數據碎片）的分類及檢測，已經成為目前國內外研究的熱點和難點問題之一，亟需在數據碎片類型識別的精度及速度上有所突破。

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

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

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

1 PCA-LDA組合特征的提取

PCA即主成分分析技術，其旨在利用降維的思想，把多指標轉化為少數幾個綜合指標。

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

本文算法中關于數據碎片PCA-LDA組合特征向量的提取方法如下：

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

其中 ，即為樣本均值。

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

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

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

（4）計算t維特征空間類內離散度，如式（4）所示：

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

2 KNN-SMO融合分類器的構造

KNN分類算法，是一個理論上比較成熟的方法，也是最簡單的機器學習算法之一。該方法的原理是如果一個樣本在特征空間中的k個最相似（即特征空間中最鄰近）的樣本中的大多數屬于某一個類別，則該樣本也屬于這個類別 。基本描述如下：

對一個C類別問題，每類有N_i個樣本，i=1，2，…，C，則第i類 判別函數為公式（6）-（7）所示：

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

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

對于輸入數據集

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

基于KNN和SMO的融合分類器構造方案如下：

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

3 數據碎片類型識別

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

4 實驗結果與分析

本文在實驗中選取的數據集是文獻和等所采用的公共的數據集govdocsl，該數據集由Garfinkel等發布，共有1，000，000個不同類型的文件。本文在實驗中共選取了30種不同類型的文件進行測試，文件類型如表1所示：在實驗中，每種類型隨機選取10個以上的文件進行碎片化，碎片的大小以1024字節為標準，并保證碎片化后每種類型的文件含有5000個以上的碎片，然后再從中選取1000個數據碎片進行實驗。

此外，大部分的數據類型在頭部可能會含有一些能夠標識數據類型的元信息，而尾部的最后一個數據碎片可能不夠特定的碎片大小，因此在實驗忽略了文件頭部的第一個數據碎片和文件尾部的最后一個數據碎片。

本文使用Matlab 2013Rb軟件對本文的算法進行實現，然后對數據碎片類型進行識別測試。此外，為了驗證本文算法的優越性，本文對文獻 、 和 的算法進行了實現，然后與本文算法一起進行對比實驗。

實驗結果評價上從查重率、查準率和F值三方面考慮，分別如公式（10）-（12）所示：

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

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

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

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

5 總結

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