基于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的融合分类器进行分类识别。实验表明，本文算法与其他相关算法相比，具有更高的识别准确率和更快的识别速率。