基于类内和类间距离的主成分分析算法

张素智，陈小妮，杨 芮，李鹏辉，蔡 强

(1.郑州轻工业大学 计算机与通信工程学院，河南 郑州 450002；2.北京工商大学 食品安全大数据技术北京市重点实验室，北京 100048)

0 引 言

近年来，随着信息技术的不断发展，数据信息爆炸式增长，导致数据的复杂度越来越大，数据类型多种多样，进而引发了数据的“维数灾难”。传统的数据挖掘技术在处理这样的高维数据中面临着巨大挑战，无论从资源上还是时效上，都需要更高的要求[1]。大数据降维算法就是要研究一种有效、简单的数据表示，将数据的维数降到适合处理的大小，从而消除数据冗余，使数据分析处理和存储变得高效低耗。通过数据降维得到高维数据的低维表示，是大数据分析的关键问题。

数据降维算法广泛应用于遗传学、医学和生物信息学等领域[2]。目前，国内外研究人员针对数据降维算法已经进行了大量的研究。文献[3]详细介绍了PCA算法的基本思想以及具体算法实现。由于传统的PCA算法存在占内存较大的问题，文献[4]引入了信息熵的思想，提出了基于信息熵的主成分分析(E-PCA)算法。在数据采用PCA算法降维之前，先利用信息熵先对数据进行特征筛选，不仅提高了降维结果，同时降低了内存占用，减少了运行时间。E-PCA算法虽然在某种程度上对PCA算法进行了改进，但其降维后数据的判别性能较低。对此，文献[5]针对超光谱图像高维和计算复杂两个特点，提出了一种基于超光谱图像的带监督提取技术，该方法具有较好的分类精度和Kappa系数；文献[6]提出了一种边界判别MDP算法，通过最大化类间最大距离，最小化类内最小距离，从而提升了数据低维表示的判别能力，但其对于高维数据的降维效果不太理想。因此，如何在保证降维效果的前提下，同时提高数据低维表示的判别能力是值得进一步研究的。针对以上问题，本文将类内和类间距离的思想引入E-PCA算法中，提出了一种基于类内和类间距离的主成分分析算法—IOPCA。

1 相关工作

1.1 主成分分析

主成分分析(PCA)算法是一种常用的数据降维方法[7]。该方法的基本思想是将n维特征映射到k维。这k维特征被称为主成分，是在原有n维特征基础上重新构造出来的特征，而且所包含信息与原n维特征所包含的信息基本一致。

假设样本数据集X∈Rn，其中X={x1，x2，…，xn}，每一个样本数据xi(i=1，2，…，n)包含m个特征属性，即(l1，l2，…，lm)。经过PCA线性变换后，转换到主成分空间的数据Y由k维的主成分组成。其中Y和X的关系可以用式(1)表示

Y=A′X

(1)

PCA算法的基本原理：首先将原始数据转换为矩阵，并实现矩阵的零均值化；之后计算矩阵的协方差矩阵，求出协方差矩阵的特征值和特征向量；然后将特征向量按对应的特征值大小从上到下排列成矩阵，选取矩阵的前k行组成的新矩阵即为算法的投影矩阵；最后利用式(1)求解出的矩阵就是降维后矩阵[8]。

1.2 信息熵

信息熵表示对信源考虑所有可能情况的平均不确定性。例如：一个信源发出n种取值的信号，记为W={w1，w2，…，wn}，n种信号对应的概率分别为P={p1，p2，…，pn}，并且所有概率之和为1。那么，信源的平均不确定性为单个信号的不确定性的统计平均值，称为信息熵，如式(2)所示

(2)

信息熵在不同的领域具有不同的含义，对于一个系统来说，信息熵的大小可以用来衡量该系统的有序或混乱程度，具体来说，一个系统越有序，则该系统的信息熵越低；相反，一个系统越混乱，则信息熵越高[9]。对于数据特征来说，信息熵的大小可以用来表示该属性所提供的信息量的大小。如果一个属性的信息熵越大，则该属性所包含的信息量越大；反之，则包含的信息量越小[10]。基于以上所述，可以将信息熵引入主成分分析(PCA)算法中，通过与信息熵阈值a比较，来判断该属性是否剔除。从而减小算法的计算量以及数据内存空间占用量。

1.3 类内和类间距离

为了增强原始数据低维表示的判别能力，本文在PCA算法的基础上引入了类内和类间距离[11]。通过实现类间距离最大化，类内距离最小化，来提高低维数据对分类的贡献。样本间的类内距离和类间距离一般指的是欧式距离，具体定义如下。

定义1 假设有两个任意给定的样本，记为x1和x2，则该样本之间的距离d(x1，x2)为式(3)所示

(3)

定义2 假设有两个不同类别的样本集合，分别记为cm和cn，分别在两个类别中选取两个样本点xi(∀xi∈cm)和xj(∀xj∈cn)，则d(cm，cn)为两个类别间的距离，又称类间距离，如式(4)所示

(4)

定义3 给定同一个类别ci的任意两个样本点，分别记为xa(∀xa∈ci)和xb(∀xb∈ci)，则d(ci)为类别内的距离，又称类内距离，如式(5)所示

(5)

(6)

(7)

根据式(4)和式(5)可以求得样本数据X的边界，如式(8)所示

(8)

其中，J代表样本数据边界，m表示样本的类别数，ci和cj属于不同的类别。

一般通过最大化不同类样本边界距离和最小化同类样本边界距离，来实现数据低维表示的类间距离最大化和类内距离最小化。具体思想如图1所示。

图1 类内距离最小化和类间距离最大化的基本思想

其中，图1中圆形表示一个类别，方形表示不同于圆形的另一个类别。实线表示类间距离，虚线表示类内距离，虚线和实线连接的样本点统称为边界样本点。从图1中可以看出，变换后实线变长，虚线变短，边界距离增强。因此可以分析出，变换后的样本数据具有较强的可分性。

根据式(8)，可以得出，实现类内距离最小化和类间距离最大化就是实现低维空间的样本数据边界最大，如式(9)

(9)

其中，∂(ci,cj)、∂(ci)分别是低维空间的类间距离和类内距离。

在此引入正交约束，如式(10)，根据定义4和定义5，可以将∂(ci,cj)，∂(ci)分别展开，如式(11)和(12)所示

VTV=I

(10)

(11)

(12)

结合式(10)，将式(11)和式(12)代入到式(9)得到式(13)。通过求解式(13)，找到满足低维空间类内距离最小化、类间距离最大化的投影矩阵V

(13)

边界判别投影(MDP)数据降维算法较好实现了最小化同类样本间的最大距离，最大化不同类样本间的最小距离。借助MDP算法的优化目标函数[12]，如式(14)所示。通过求解目标函数中的投影矩阵V，即可实现投影后矩阵边界最大化

maxtr(VT(S(b)-S(w))V)

(14)

其中，S(b)=XL(b)XT，S(w)=XL(w)XT，L(b)和L(w)是Laplacian矩阵，分别代表样本数据同类样本间的近邻关系和异类样本间的近邻关系。

2 基于类内和类间距离的主成分分析算法

2.1 算法基本思想

数据维数的不断提高，形式也越来越复杂。从而使对高维数据进行分析处理越来越难。为了在尽量保留数据信息的情况下降低数据的维度，同时增强数据低维表示的判别能力，使低维表示的数据更有利于分类。因此，本文引入信息熵、类间距离和类内距离的思想。提出了基于类间和类内距离的数据降维(IOPCA)算法。该算法思想如图2所示，图中左侧是原始数据分布，右侧是降维后的数据分布。图中的不同形状代表不同的类别，实线代表同类间样本点的距离，虚线代表异类间样本点的距离。从图中可以看出，数据经过降维处理后，从高维变为低维，同时类内距离变小，类间距离变大。

图2 IOPCA数据降维算法的基本思想

2.2 算法主要内容

2.2.1 算法流程

基于类间和类内距离的数据降维(IOPCA)算法的基本处理流程如图3所示。首先，在对高维数据降维前，通过采用信息熵进行属性筛选，降低算法的计算量，减小数据的占内存空间；然后，用基于类间和类内距离思想的数据降维目标函数求解投影矩阵，代替PCA算法利用协方差矩阵求解主成分，从而得到PCA算法的优化算法；最后，将属性筛选后的矩阵用PCA算法的优化算法进行降维。

图3 基于类内和类间距离的主成分分析算法流程

2.2.2 算法介绍

基于类内和类间距离的PCA数据降维(IOPCA)算法与E-PCA算法，相同之处在于对数据进行降维之前都将属性的信息熵与信息熵阈值a对比，进行了一次特征筛选；不同之处在于IOPCA算法在对筛选后数据的降维过程中充分考虑了类间距离和类内距离，从而实现了投影到低维空间数据的类间距离最大化，类内距离最小化。具体算法步骤如下。

输入：数据矩阵Pd×n，n表示样本数目，d代表样本维度，每个样本对应的类别为label(xi)∈C，其中C={c1,c2,…,ck}，信息熵阈值a，贡献率f。

输出：降维结果。

(1)计算每个属性的信息熵值，通过与阈值a比较，进行特征筛选。

(2)进行样本矩阵中心化，计算得矩阵Xd×n

X=A-repmat(mean(A,2),1,n)

(15)

(3)计算Laplacian矩阵L

L=L(b)-L(w)

(16)

(4)采用不完全Cholesky分解技术对数据矩阵X进行QR分解，分解结果如式(17)所示

X=QR

(17)

(5)求解矩阵Z=RLRT，计算Z的特征值(eigenVa-lue)和特征向量(eigenVector)。

(6)对矩阵Z特征分解，求得矩阵U=[u1,u2,…,ur]，其中，ui是矩阵Z的第r个最大特征值λi对应的特征向量。

(7)选定投影矩阵V。投影矩阵如下公式所示

V=QU

(18)

(8)计算降维结果Y

Y=VTX=(QU)TQR=UTR

(19)

(9)算法结束。

IOPCA算法中的r值不作为参数输入，r值的确定与特征值的贡献率f有关，IOPCA算法中贡献率计算与PCA算法中一样，指的是选取属性值与样本中的所有属性值的和的比值。计算公式如下所示

(20)

3 实 验

为了验证IOPCA算法的有效性，本文将IOPCA算法与PCA、E-PCA、LDA算法，从降维结果以及降维后数据经过KNN、SVM算法的分类精确度上进行比较。

3.1 环境和数据集

实验环境：本文在MATLAB R2014a下对PCA、E-PCA、LDA和IOPCA进行模拟仿真，配置环境为Pen-tium4，2.8 GHz CPU，内存1 GB，Windows XP系统。

数据集：为了更全面分析4种降维算法的性能，本文从UCI标准数据库[13]中选取4种数据集进行实验，包括：Iris数据集，150个样本，4个属性，3个类；Soybean(large)数据集，307个样本，35个属性，18个类；Sonar数据集，208个样本，2个类，60个特征；SPECTF incorrect数据集，269个样本，2个类，44个特征。

3.2 结果及分析

(1)降维结果

通过对4种数据集采用PCA、E-PCA、LDA和IOPCA降维方法在MATLAB进行实验，设置PCA、E-PCA、IOPCA的贡献率f=0.95，在实验过程中信息熵阈值根据数据集的属性信息熵来选取。实验得到的降维结果见表1。从表1可以看出，当E-PCA算法中的信息熵阈值为0时，E-PCA等价于PCA。另外，对于Iris数据集，本文方法和PCA、E-PCA方法的降维结果一样，优于LDA方法；然而，对于其它3种数据集，本文方法的降维结果均优于PCA、E-PCA和LDA方法。

表1 4种数据集在不同降维方法下的降维结果

(2)分类精确度

分别将4种数据集通过PCA、E-PCA、LDA和IOPCA进行降维处理，按照表2所示的测试集样本数和训练集样本数来分配，采用KNN和SVM算法进行分类，并与4种原始数据采用KNN和SVM进行分类的分类精确度进行对比。分类实验均重复10次取精确度平均值。实验结果见表3～表6。

表2 4种数据集的样本数量

Iris数据集降维前后经过KNN、SVM算法的分类精确度见表3。通过表3可以看出，将Iris数据集经过PCA、E-PCA算法降维后的数据，作为KNN、SVM算法的输入，分类精确度略有降低；而将Iris数据集经过LDA算法降维后的数据，作为KNN、SVM算法的输入，分类精确度分别提高约1.6和0.67个百分点，同样采用IOPCA算法降维，分类精确度分别提高约5.41和1.89个百分点。

表3 Iris数据集降维后经过KNN、SVM算法的分类精确度/%

Soybean(large)数据集降维前后经过KNN、SVM算法的分类精确度见表4。分析表4可以得出，该数据集采用PCA、E-PCA降维后的数据经过KNN、SVM算法的分类精确度均降低约0.5～1.0个百分点，采用LDA降维后的数据经过KNN、SVM算法的分类精确度分别提高约11.43和0.57个百分点，同样的采用IOPCA算法，分类精确度分别提高约13.14和1.86个百分点。

表4 Soybean(large)数据集降维后经过KNN、SVM算法的分类精确度/%

Sonar数据集降维前后经过KNN、SVM算法的分类精确度见表5。从表5中可以看出，Sonar数据集相比于SVM更加适合使用KNN算法进行分类。另外，该数据集采用PCA、E-PCA降维后的数据经过KNN、SVM算法的分类精确度均降低约0.5～1.0个百分点，采用LDA算法降维后的数据经过KNN、SVM算法的分类精确度分别提高约10.25和2.5个百分点，同样的采用IOPCA算法，分类精确度分别提高约14.46和5.44个百分点。

SPECTF incorrect数据集降维前后经过KNN、SVM算法的分类精确度见表6。从表6中可以看出，该数据集采用PCA、E-PCA降维后的数据经过KNN、SVM算法的分类精确度均降低约2个百分点，采用LDA算法降维后的数据经过KNN、SVM算法的分类精确度分别提高约0.8和1.66个百分点，同样采用IOPCA算法，分类精确度分别提高约2.94和3.58个百分点。

表5 Sonar数据集降维后经过KNN、SVM算法的分类精确度/%

表6 SPECTF incorrect数据集降维后经过KNN、SVM算法的分类精确度/%

为了更直观衡量算法的有效性，单独比较数据集降维处理前以及采用4种方法降维处理后分别经过KNN和SVM算法的分类精确度。结果如图4和图5所示。

图4 4种数据集采用KNN算法的分类精确度

图5 4种数据集采用SVM算法的分类精确度

综合分析表3～表6和柱状图4、图5可得，PCA和E-PCA算法虽然实现了数据维度减少的结果，但是同时也降低了数据的分类能力，原因在于将数据从高维空间向低维空间映射时，没有对类间距离做太多的考虑。而LDA和IOPCA算法在有效降低数据维度的同时，提高了数据的分类能力。因此，从降维后数据的分类判别能力上来说，本文所提出的IOPCA算法相对其它3类降维算法较好。

4 结束语

由于传统的主成分分析数据降维方法提取的低维表示的判别性能较低，本文给出了基于类内和类间距离的主成分分析数据降维方法，该方法将类内和类间距离的思想引入到PCA算法中，通过最大化不同类别间的最小距离，同时最小化同类别间的最大距离，来增强数据低维表示的判别性能。在MATLAB环境中，通过与PCA、E-PCA、LDA方法进行对比,结果表明IOPCA算法不仅提高了数据的降维效果，同时提高了降维后低维数据的判别性能。但是在实验过程中，只将该方法与数据降维的其它几种线性方法进行了比较，而且实验所用数据集类型覆盖面不够广。因此，下一步工作，将本文提出的IOPCA方法与几种非线性数据降维方法进行比较，如：Laplacian Eigenmaps(LE)、局部线性嵌入(LLE)等，从而对本文所提算法更加全面地做出评价，并做出进一步改进。