基于高阶奇异值分解的手写数字分类

基于高阶奇异值分解的手写数字分类摘要在这篇文章中，我们提出了两个基于高阶奇异值分解〔HOSVD〕的手写数字分类的算法。第一个算法用HOSVD进行类模型的建立，使得分类结果的错误率小于6%。第二种算法用HOSVD同时在两个模型中进行张量近似。第二种算法在把原始数据减少约98%后，仍然使分类的错误率小于5%。两种算法在进行分类的检验阶段，都是通过一系列最小方差来实现分类的。从计算量的角度考虑，第二种算法是第一种算法效率的两倍。1、简介手写数字的自动分类常被看是一个标准的模式识别问题，它包含了这一领域的很多难点。由于同一类中各个对象之间的变化非常大，同时不同类之间的对象有非常相似，所以把一个未知的数据划分到十个确定类别中的某一个是一个非常困难的过程。解决这一问题有许多不同的方法，例如：主成分分析法〔PCA〕、支持向量法〔SVM〕、最邻近法和k-临近法，回归、统计模型和神经网络等。关于不同模式识别方法的研究可以再参考文献[1,2]中查阅。对于手写数字分类的不同算法的比拟可以在参考文献[3]中找到。其中，表现最好的算法是基于神经网络和在局部仿射变换下测量不变性的正切距离方法来实现的。其他算法可以再参考文献[6,7,8]中查阅。通常，表现好的算法表述比拟复杂或者计算量非常的。在这篇文章中，我们提出了两种结果很好，同时比拟简单、高效的算法。这两种算法都是基于对张量的HOSVD。第一种算法通过HOSVD计算得到每一个类的一个小的基矩阵的集合，这个集合包含了这个类中所有数据的主要的子空间。这些子空间然后用来描述未知的数据。这个算法和SIMCA、PCA比拟类似。第二种算法使用HOSVD对训练集合进行压缩。每个类的模型都是通过压缩的训练集合建立的，分类的过程和第一个算法相同。它的优点有两个：一个是各个类的模型的描述需要的内存更少，另一个是在结果没有变差的情况下算法更加高效。这个算法即使在训练集合压缩98%后仍然能使分类的错误率小于5%。近年来，应用张量方法解决问题在模式识别和其他各个领域引起了越来越多的关注。我们所说的张量是指多维的或多模的数组。通常，数据是一种多维的结构，把它们存储在矩阵或者向量中不是很合理。一个简单的例子就是一组时间序列的图像。每一幅图像都是一个二维的数据数组，把不同时间序列的图像放在一起共同构成了一个张量。通常，这种方法有利于在存储数据的过程中不破坏内在的多维间的结构。张量方法在化学测量和心理测量已经应用了很长时间。最近，HOSVD已经应用到人脸识别。在这篇文章中，我们使用USPS数据库中的手写数字对我们提出的算法进行测试。这些数字是从信封上扫描的到的大小为1616的灰度图像。这个数据库被广泛应用到分类算分的测评中。这篇文章后面的局部是这样安排的：第二局部包含张量概念的介绍以及一些本文提出的算法所涉及的张量理论的结论。第三局部论述了两种算法。第四局部对数据的测试进行了论述，并对数据集合进行了更加详细的介绍。这些算法将使用伪matlab代码进行演示。因此，在代码例子中我们将使用A(I,j,k)这个记号代表aijk。同样，在式子中我们也将用一些matlab类型的符号。例如，我们定义1维-模指三阶张量A按照的列向量展开。其它维的模的定义非常明显。因此，维是通过固定其中出了一个之外的所有参数来定义的。类似的，我们定义一个张量的局部是固定其中的一个参数来确定的子张量。2、张量的概念粗略地说，一个N阶张量就是一个对象包括N个参数。张量的维是指张量的模。向量和矩阵可以分别看作是一阶和二阶的张量。在这篇文章中，我们应用的是三阶张量。因此，为了描述方便，在这节中我们的一些理论的论述仅仅针对三阶张量I,J,K是正整数；的向量空间的维数是IJK。通常的任意维的张量的概念也与此类似。设是普通的欧式空间几何。定义张量的标量乘积为两个张量A,B正交是指它们的标量乘积等于零张量A的模定义为张量和矩阵的标量乘积和模的定义与此相类似。有时常将一个张量重新排列成一个矩阵。我们把这个过程叫做矩阵化一个张量。n-模矩阵化一个张量K是指将K的n维-参数排列成一个矩阵的列向量得到的矩阵，记作。我们可以假设的列向量的排列是一种正向循环的方式。那么，矩阵化一个三阶张量可以定义为A中的一个参数在矩阵中需要指出的是中的列向量是A的n维-参数。没有一个确定的从矩阵的秩的定义角度来概括高阶张量的秩的方法。一个可行的方法是定义张量A的n-秩为A的n-模子空间的维数是指n-模矩阵化的张量A的矩阵，没有特别说明rank是指矩阵的秩。容易证明一个三阶张量的不同的n-秩通常是不同于同样的矩阵。我们现在给出一个通常的张量-矩阵乘法的概念。定义1〔n-模张量-矩阵乘法〕设，。那么n-模张量-矩阵乘法可以定义为例如，张量，矩阵的1-模乘积为给出张量，和矩阵，，张量-矩阵乘法满足下面的性质，由于的列向量是张量A的n维的元素，所以n-模乘法可以被看作是n-模矩阵化张量B得到，先进行普通的矩阵相乘，然后将重新排列成张量B。2.1高阶奇异值分解矩阵的奇异值分解〔SVD〕在很多应用中是一个非常有用的工具。不失普遍性，我们设矩阵，满足mn。结论2〔矩阵的SVD〕任何矩阵可以写成下面的乘积，其中是正交的矩阵，∑是一个非负的对角矩阵，满足以下性质：U和V的列向量分别称作左奇异向量、右奇异向量，是奇异值。奇异值分解的证明可以再参考文献[16]中查阅。如果把矩阵看作是一个二阶的张量，那么可以把SVD看作是n-模的乘积。一个可行的关于张量的奇异值分解的概括可以在参考文献[9]中查阅，这种分解称作HOSVD。我们论述对于三阶张量的HOSVD。结论3〔HOSVD〕三阶张量可以写成下面的乘积，包含以下性质：，都是正交的矩阵。是一个和的维数相同的张量，并且QUOTE满足以下性质〔a〕〔完全正交性〕同一模中的两个不同局部满足正交性，〔b〕〔排列性质〕每个模的不同局部的模长都是按照同样的序列排列的。例如，第一模的各个局部的模长满足式子〔13〕中的模长，实际上就是矩阵化张量的奇异值。在式子〔13〕中的排列的性质，可也粗略的看作是：核张量的“能量〞或者“主要局部〞集中在〔1,1,1〕这个角落附近。这个性质使我们可以用HOSVD进行数据压缩。对张量的HOSVD的计算，可以通过分别计算，n=1,2,3，的左奇异矩阵，满足正交性的U、V、W来实现。计算以下三个SVD：不需要明确地求出。计算核张量需要指出的是，我们可以利用一些常理，例如由于，所以防止计算右奇异值矩阵，从而减少了大量的浮点运算。2.2基于HOSVD的张量近似在矩阵数据的压缩中，经常使用低秩的近似：对于满足正交性的模长不变的情况下，对于一个给定矩阵F最正确的k阶秩近似可以通过SVD来实现[16]，其中，，Uk、Vk分别是U、V的前k列。这种近似可以通过图二明显的演示。由于存在式子〔13〕中的排列性质，张量的近似可以通过HOSVD以类似的方法实现。然而，通常的张量近似在式子〔3〕中的定义的模中并不是最优的方法。对于一个三阶张量的近似，可以写成以下形式这里，QUOTE。一种度量张量近似结果好坏的方法就是测量张量的n模奇异值下降的大小：如果核张量QUOTE的模省略的局部比拟小，那么近似的错误也比拟小。图三中演示了张量的低阶近似。2.3正交基矩阵一个矩阵F可以写成是秩为一的SVD的和三阶张量也可以实现类似的分解，其中，需要指出的是，是矩阵Av和向量wv之间的矢量乘积，相乘的结果是三阶的张量。由于满足完全正交性，所以Av也是正交的：当vu的时候。〔其中，tr是指计算迹〕。这些正交的矩阵可以看做是一组线性独立的基矩阵。图四是它的演示。方块代表Av，它上面的线是指向量wv，它们一起表示三模的向量积。3、算法3.1算法一：基于HOSVD的分类这一节我们将论述如何使用HOSVD建立手写数字分类的算法。训练集合的数据进行了人工的分类。把每个数据看作是空间的点，可以认为训练集合中的数据形成了十个别离的很好的聚类，否那么分类算法的运行结果会非常差。同时，每一个聚类中的主要向量包含了的子空间。我们使用一种变化了的SIMCA算法，给每一个类建立一个正交的基矩阵的小集合。每个类的基矩阵的集合包含了这个类子空间的主要局部。然后，当我们决定哪个基能最好的描述一个未知数据，我们就计算用着十个类分别近似这个数据的误差。我们使用HOSVD来计算不同的基矩阵集合。3.1.1训练阶段正交基矩阵的集合是通过2.3节的方法来进行计算的。每一个类的基是通过对相同的训练数据构成的三阶张量的计算得到的。设是一个包含2的张量，它已经进行了HOSVD。由式子〔16〕可知这里，是正交的基矩阵。同时也说明，中的每一个数据都是的唯一确定的线性组合。线性组合的系数就是向量QUOTE中的元素。我们可以用图五演示式子〔17〕中任意一个中的2都是的一个线性组合。这些系数可以看做是第三模向量上的点。我们截取式子〔17〕中和的一局部得到每个聚类的一个k维的小的子空间。假设我们得到所有类的基，每个基包含k个基矩阵，并指出同时，假设基矩阵都是归一化的。那么这里是Kroneckerdelta。设D是未知数据，且D已经归一化，即QUOTE。哪个基矩阵集合是描述D的最好方式呢？3.1.2测试阶段考虑最下化问题指类别的标号，式中是未知的要确定的标量。这是一个最小方差问题。由于对固定的，都是正交的所以可以很容易求得：求解的方法是有一个非常有意思的地方是是两个矩阵D和的夹角的cosine值，把这个求法带入到式子〔18〕中，应用基矩阵的正交性可以得到以下模的平方的表达式，我们现在把D划分到使得R(u)取得最小值的u这一类中。算法一是分类的算法的总结，算法的结果在4.3节中给出。算法一基于HOSVD的分类训练阶段把相同的训练数据排列到同一个张量中。计算每个张量的HOSVD。计算并存储归一化的基矩阵QUOTEu=0,1,…,9。测试阶段把未知数据归一化。计算，u=0,1,…,9。确定使得R(u)得到最小值的u，并把D划分到u这一类。3.2算法2：基于HOSVD的压缩和分类在计算不同类的基向量前可以用HOSVD进行数据压缩。这是算法二后面的主要思想，也是这篇论文的主要奉献。这与矩阵的低阶秩近似相类似。就计算效率的改良而言，所有类中的数据都投影到了一个共同的子空间。因此，一个未知的数据只需投影一次。如果不同类有不同的子空间，那我们就不得不把这个未知数据投影到每一个子空间。这样，算法的测试阶段将需要大的非常多的计算量和内存。3.2.1训练阶段首先我们建立一个包含训练集中的每一个数据的张量。数据将如图六所示进行组织。所有的数据都被重新排列成中的向量。张量的每一个不同局部包含同一类的数据。我们对张量进行HOSVD其中，，。图七演示了张量近似。通过这个近似，我们把每个数据的表示从降到了，每个类中的数据的量降到了q。降维后的张量可以通过以下式子进行计算QUOTE我们可把图像的降维表示看成是向列空间的投影。假设p、q相对于中的相应的维数非常小，那么我们就实现了对训练集中数据的大的降维。表一中列出了相对于不同的p、q进行数据压缩后，数据近似产生的错误率。为了使近似的结果比拟好，那么像素模和数据模省略的奇异值就必须很小。图八中给出了局部奇异值的示意图。我们可以看到相对于数据模的奇异值，像素模的奇异值减少的非常快。数据模的奇异值减少的速度没有那么快说明了所有类中的不同数据的变化很大。从表一中的p、q我们可以看到，即使数据降维99%后错误率仍然出奇的低。重新把式子〔21〕中的数据张量的的低维近似写成像素模可以对HOSVD进行下面的解释。Dp中的每一列是包含p个元素的某个数据。FVq是每一行包含了不同数据在基向量下的坐标。有意思的是Vq的每一行中的列向量表示u所指的类的基向量。为了得到不同类的正交的、排列的基向量，我们对进行SVD并取k个最主要的左奇异值向量，其中的k列基矩阵是指Bu∈Rp×k3.3.2测试阶段设d∈R400是一个未知的数据。在测试阶段我们计算它的低维表示，然后解决下面的小了许多的最小方差问题。，u是固定的类别。由于Bu的列向量满足正交性，可以得到如下的计算方法把它带入到上式中，可以得到，再一次，我们把使得剩余值最小的u作为未知数据的类。完整的分类算法如下。算法二训练阶段把数据集中的所有数据向量化并排列到张量中。对张量QUOTED进行HOSVD。计算数据集的降维后的张量。计算并存储每个类的基矩阵。测试阶段计算未知数据的低维表示。计算剩余值u=0,1,…,9。确定使R(u)取得最小值的u，并把未知数据d划分到这一类中。4、测试和结果到现在描述的过程都是非常普遍的。为了得到一个算法还需要确定几个参数。例如在分类过程中基向量的个数。还有在第二个算法中的p、q。在这一节我们对提出的算法进行验证。但首先对我们用到的数据库和预处理进行简单的介绍。4.1数据集——USPS数据库我们在实验中用到的数据集在网上可以免费得到。这个数据库常常用来对分类算法进行评估。数据库中的数据是ＵＳ邮政信封上扫描得到的。图像的大小是QUOTE１６×１６的像素，灰度强度的范围是０－２５５。可以得到两个集合，一个是包含７２９１个数据的训练集合，另一个是有２００７个数据的测试集合。数据的分布情况如表二所示。根据Ｈａｓｔｉｅ的观点，这个数据库相对于其他的数据库，从分类的角度来考虑，难度更大。图一所列出的数据是书写非常标准的，但数据库中还有许多书写的很不标准的数据。MNIST数据库是另一个未分类而建的比拟有名的数据库。它里面数据的大小是，灰度强度是和USPS相同的。一些常用的算法在这数据库上的实验，错误率都比拟低。为了在三阶张量中完全用到训练集合中的数据，有一局部数据需要复制。这是因为不同类中的数据的量不相同。4.2预处理——高斯模糊分类数据有几种预处理的方法。模糊和标准化都是常用的预处理技术。根据Simard的观点，模糊对于判别鉴定过程，至少对于手写数字的分类来说是非常重要的。模糊可以认为是使模式变得光滑或者使锋利的边角变得柔和。在模糊过程中使用不同的模糊函数就能得到不同的模糊结果。高斯是一个常用的模糊函数，标准差σ常常用来控制模糊的量。图十给出了两个例子。由于式〔25〕的快速衰变，我们用限制与有关像素直接相连的点的模糊来近似纯粹的高斯模糊，如图11所示。黑色的方块是能够进行高斯模糊的相邻区域。这种高斯模糊的近似节省了大量的计算时间。而且这种近似模糊与完全的高斯模糊没有很大的区别。模糊的因子设为0.9，这和参考文献[5]中是一样的。模糊因子σ的值设的很高的时候，一般认为不会使类别中的信息有所损失。4.3算法一的测试和检验算法的测试依照3.1节中的算法公式进行。在分类的过程中，每个类最多用到16个基矩阵，然后再对每一个未知数据进行10个最小方差问题。在每一次检验中，不同类的基矩阵的数目是相同的。图12是测试的结果。可以清楚地看到，在基矩阵的数目从0增加到12的过程中，识别的结果越来越好。不同类的识别错误率的分布不是完全一样的。2、3、5、7、8的识别就相对难一些。有时一个算法能够在所有的情况下都有一个好的识别结果是很重要的。如果错误分类后将会引起很高的风险，那么最好把这样的对象再进行进一步的分析。这样的性质可以通过替换测试阶段的第三步为下面内容轻松地实现：3如果最小的剩余量明显小与其它的剩余量，我们就把这个未知数据划分到使得剩余量最小的u类中。否那么，拒绝划分类，认为这个数据不确定。4.4算法二的测试和结果算法二的测试使用相同的方式来实现的。我们变化基向量的个数，同时也根据表一中的数据值，变化p、q来确定数据减少的量。图13中给出了测试的结果。第二种算法的分类结果更好。即使数据的量减少了98%-99%，算法二的分类结果仍然和算法一不相上下。算法二中的模型的建立使用了训练集合中的全部数据。通过比拟图12、13，有些情况下算法二的错误率更低。4.5计算的复杂度在分类过程中算法运行的快慢也是非常重要的。训练阶段的计算复杂度也很重要，但是对于一个实时的应用系统来说就不是那么重要了。下面我们给出了这两个算法计算复杂度的简要描述，同时把它们和最近邻算法作比拟。在下面的局部，我们假设数据的大小是I×I的像素，每一个类有N个训练数据，在分类过程中，每个类有k个基向量。4.5.1训练阶段在算法一、二的训练阶段，我们分别计算QUOTEAvu和QUOTEBu。为了得到，我们要在式子中计算，然后再计算这些操作要进行一次SVD和张量