基于主成分分析和K近邻的文件类型识别算法.docVIP

基于主成分分析和K近邻的文件类型识别算法 　　摘 要：为解决基于文件后缀名和文件特征标识识别文件类型误判率较高的问题，在基于文件内容识别文件类型的算法基础上，提出主成分分析（PCA）和K近邻（KNN）算法相结合的文件类型识别算法。首先，使用PCA方法对样本预处理以降低样本空间的维数；然后，对降维后的训练样本集进行聚类处理，即用聚类质心代表每种类型的文件；最后，针对训练样本分布不均匀可能造成的分类误差，提出基于距离加权的KNN算法。实验结果表明，改进算法在样本数较多的情况下，能降低分类的计算复杂度，并保持了较高的识别正确率；而且该算法不依赖文件类型的特征标识，应用范围更为广泛。 　　关键词：文件类型识别；字节频率分布；主成分分析；K近邻 　　中图分类号：TP391.4 　　文献标志码：A 　　文章编号：1001-9081（2016）11-3161-04 　　0 引言 　　文件类型是指文件存储在计算机中使用的特殊编码方式，计算机根据文件类型来识别内部存储。每一种类型的文件，都对应着一种或多种存储格式和访问方式。文件类型识别即通过某种途径判别文件所属类型的过程。为了保证计算机信息安全，需要设计出能准确且快速地判断出文件的真实类型的方法。 　　在工程应用中，可以分别使用基于文件的后缀名、基于文件的特征标识、基于文件的二进制内容这三种方法来识别文件实体的真实类型[1]。Windows操作系统采用文件后缀名来标识文件类型；另一种方法是利用特征标识，即魔数信息来识别文件类型。基于后缀名和基于魔数的方法都有识别效率高的优点，但是在识别正确率方面却有明显的不足。此外，通过更改文件魔数信息或者文件的后缀名可以隐藏文件的真实类型，某些恶意用户可以借此来骗取用户访问，控制病毒传播，掩盖违法信息。 　　除了以上两种方法，McDaniel等[2]首次统计文件内容的某些特定字节（特征值），以特征值的频率分布生成文件类型的“指纹”，依此识别文件类型。这种算法不依赖于文件名和文件特征标识，不易被篡改误导；但识别正确率不高。Li等[3]以文献[2]中提出的算法为基础，通过建立文件内容的n-gram模型对算法进行了扩展，并使用多个指纹的聚类算法判断文件类型，提高了识别正确率；但是此方法无法有效地识别相同文件类型中统计特征值有很大差异的文件。 　　此外，在文本分类领域，K近邻（K Nearest Neighbors，KNN）算法因其简单、有效、非参数化而得到了广泛应用[4-5]。但传统KNN分类算法效率低下，可从缩减训练集规模、对文本进行降维处理等方面着手降低算法的计算开销[6]。 　　本文提出的文件类型判别方法是一种新的混合算法，基于基本KNN分类算法，利用主成分分析（Principal Component Analysis， PCA）方法对文件的向量空间模型先降维处理，对降维后的文件通过聚类算法得到该类文件的多个质心，用聚类质心代表全部的训练样本，从而减少了KNN分类器的输入。为减小样本分布不均对分类结果可能产生的影响，使用经加权修正后的KNN算法。实验结果表明使用本文算法分类文件具有较高的精度；另外因为使用了聚类和降维算法，显著地减少了分类时间。 　　1 文件类型特征模型建立 　　1.1 文件的向量空间模型 　　建立文件的特征值模型V： 　　1.2 文件内容截取算法 　　读取整个文件的字节值并统计每个值的频率分布会花费大量的计算时间，文献[3]中提出一种内容截取算法，即用文件某一部分内容的字节值代替整个文件的，这种方法的引入可以有效减少分类计算时间。文献[3]中实验证明，该算法不会降低分类准确性。 　　本文借鉴上述算法，分别截取文件头部1KB、文件中间任意位置1KB进行对比实验。实验结果表明文件中某段位置的字节分布可以很好地代表整个文件的特性。 　　2 PCA和KNN算法描述 　　2.1 PCA算法描述 　　主成分分析是一种统计方法，通过正交变换将一组可能存在相关性的变量转换为一组线性不相关的变量，转换后的这组变量叫主成分。 　　主成分分析方法是一种对数据进行降维的方法，它的基本思想如下：将具有一定相关性的多个原始变量，通过组合变换，得到一组互相无关的综合变量。从中选取几个较少的能够在很大程度上反映原始变量信息的综合变量，就是主成分。主成分之间是互不相关的，且是原始变量的线性组合[8]。 　　主成分分析方法的计算步骤如下： 　　1）获取训练样本特征矩阵： 　　5）根据需要的维数选择p（pm）个重要的主成分，p的选取根据成分的累积贡献率来决定，一般要求累积贡献率达到85%以上，这样才能保证综合变量能包含原始变量的大多数信息。 　　6）计算主成分得分，以达到降维的目的。 　　2.2 KNN算法描述