3.5　特征值分解

“分而治之”的策略经常被用于机器学习的算法设计中，许多数学对象可以通过分解成多个子成分或者寻找相关特征，来更好地理解整体。例如，整数可以分解为质数。十进制整数12可以用十进制或二进制等不同方式表示，但素数分解是具有唯一性的，通过素数分解可以获得一些有用的信息。例如，12=2×2×3，通过这个表示可以知道12不能被5整除，或者12的倍数可以被2整除等信息。同理，可以通过将矩阵分解成多个子矩阵的方法来发现原矩阵中本来不明显的函数性质。本节将对特征值分解方法进行讲解。

特征值分解（Eigen-Decomposition）是使用最广的矩阵分解方法之一，是一种将矩阵分解成由其特征向量和特征值表示的矩阵之积的方法。

方阵A的特征向量是指与A相乘后相当于对该向量进行放缩的非0向量x：

Ax=λx

标量λ被称为这个特征向量对应的特征值（Eigen value）。非0向量x称为方阵A对应于特征值λ的特征向量。

“特征”在模式识别和图像处理中是非常常见的一个词汇。要认识和描绘一件事物，首先要找出这个事物的特征。因此，要让计算机识别一个事物，首先就要让计算机学会理解或者抽象出事物的特征。不论某一类事物的个体如何变换，都存在于这类事物中的共有特点才能被作为“特征”。例如，计算机视觉中常用的SIFT特征点（Scale-Invariant Feature Transform）就是一种很经典的用于视觉跟踪的特征点，即使被跟踪的物体的尺度、角度发生了变化，这种特征点依然能够找到关联。

在机器学习中，特征向量选取是整个机器学习系统中非常重要的一步。线性代数中的“特征”是抽象的。矩阵乘法对应了一个变换，是把任意一个向量变成另一个方向或长度不同的新向量。在这个变换过程中，原向量会发生旋转、伸缩变化。如果矩阵对某一个向量或某些向量只发生伸缩（尺度）变化，而没有产生旋转变化（也就意味着张成的子空间没有发生改变），这样的向量就是特征向量。可以通过图3.10来理解特征向量的概念。

图3.10　特征向量的概念

可以看出，图3.10中左图通过仿射变换，发生了形变，但是，图像的中心纵轴在变形后并未发生改变。对比上面左右两图中的浅色向量，可以看出其发生了方向的改变，但是深黑色向量的方向依然保持不变，因此深黑色向量可以看作该变换的一个特征向量。深黑色向量在从图3.10左图变换成右图时，既没有被拉伸也没有被压缩，其特征值为1。所有沿着垂直线的向量也都是特征向量，它们的特征值相等。这些沿着垂直线方向的向量构成了特征值为1的特征空间。

如果v是矩阵A的特征向量，那么任何放缩后的向量sv（s∈R，s≠0）也是矩阵A的特征向量。此外，sv和v有相同的特征值。基于特征向量的该特性，通常可以只考虑单位特征向量。假设矩阵A有n个线性无关的特征向量{x1，x2，…，xn}，它们对应的特征值分别为{λ1，λ2，…，λn}。将n个线性无关的特征向量连接一个矩阵，使得每一列是一个特征向量V=[x1，x2，…，xn]，用特征值构成一个新的向量λ=[λ₁，λ₂，…，λ_n]T，此时矩阵A的特征分解如下所示。

A=Vdiag（λ）V-1

值得注意的是，并不是所有矩阵都可以特征值分解，一个大小为Rn×n的矩阵A存在特征向量的充要条件是矩阵A含有n个线性无关的特征向量。