> For the complete documentation index, see [llms.txt](https://aye10032.gitbook.io/prml-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aye10032.gitbook.io/prml-note/di-si-zhang-te-zheng-xuan-ze-he-ti-qu/4.3-li-san-kl-bian-huan.md).
# 4.3 离散K-L变换
* 前面讨论的特征选择是在一定准则下，从n个特征中选出k个来反映原有模式
* 这种简单删掉某n-k个特征的做法并不十分理想，因为一般来说，原来的n个数据各自在不同程度上反映了识别对象的某些特征，简单地删去某些特征可能会丢失较多的有用信息
* 如果将原来的特征做正交变换，获得的每个数据都是原来n个数据的线性组合，然后从新的数据中选出少数几个，使其尽可能多地反映各类模式之间的差异，而这些特征间又尽可能相互独立，则比单纯的选择方法更灵活、更有效
{% hint style="success" %}
K-L变换（Karhunen-Loeve变换）就是一种适用于任意概率密度函数的**正交变换**
{% endhint %}
## 4.3.1 离散的有限K-L展开
### 一、展开式的推导
设有一连续的随机实函数$$x(t)$$，$$T\_1\leq t\leq T\_2$$，则$$x(t)$$可用已知的正交函数集$${\varphi\_j(t),\ j=1,2,\dots}$$的线性组合展开，即：
$$
\begin{align} x(t) &= a\_1\varphi\_1(t) + a\_2\varphi\_2(t) + \cdots+a\_j\varphi\_j(t) + \cdots \nonumber \ &= \sum\_{j=1}^\infty a\_j\varphi\_j(t),\ \ T\_1\leq t\leq T\_2 \nonumber \end{align}
$$
其中$$a\_j$$为展开式的**随即系数**，$$\varphi\_j(t)$$为一**连续的正交函数**，满足：
$$
\int\_{T\_1}^{T\_2}\varphi\_n(t)\tilde{\varphi}\_m(t)dt=\begin{cases} 1 & m=n \ 0 & m\neq n \end{cases}
$$
其中，$$\tilde{\varphi}\_m(t)$$为$$\varphi\_m(t)$$的**共轭复数**形式
将上式写成离散的正交函数形式，使得连续随机函数$$x(t)$$和连续正交函数$$\varphi\_j(t)$$在区间$$T\_1\leq t \leq T\_2$$内被**等间隔采样**为n个离散点，即：
$$
x(t) \to {x(1),x(2),\cdots,x(n)} \ \varphi\_j(t) \to {\varphi\_j(1),\varphi\_j(2),\cdots,\varphi\_j(n)}
$$
写成向量形式，则有：
$$
x = (x(1),x(2), \cdots, x(n))^T \ \varphi\_j=(\varphi\_j(1),\varphi\_j(2),\cdots,\varphi\_j(n))^T
$$
则可以对公式$$(1)$$取n项近似，并写成离散展开形式：
$$
x=\sum\_{j=1}^na\_j\varphi\_j = \varphi a,\ \ T\_1\leq t\leq T\_2
$$
其中，$$a$$为展开式中的随即系数的向量形式，$$\varphi$$为一$$n\times n$$矩阵，即：
$$
a=(a\_1,a\_2,\dots,a\_j,\dots,a\_n)^T \ \ \varphi = \begin{bmatrix} \varphi\_1(1) & \varphi\_2(1) & \cdots & \varphi\_n(1) \ \varphi\_1(2) & \varphi\_2(2) & \cdots & \varphi\_n(2) \ \vdots & \vdots & \ddots & \vdots \ \varphi\_1(n) & \varphi\_2(n) & \cdots & \varphi\_n(n) \end{bmatrix}
$$
可以看出，$$\varphi$$本质上是一个**正交变换矩阵**，它将$$x$$变换成$$a$$。
### 二、K-L展开式的性质
{% hint style="success" %}
如果对c种模式类别$${\omega\_i}\_{i=1,\dots,c}$$做离散正交展开，则对每一模式可分别写成：$$x\_i=\varphi a\_i$$，其中矩阵$$\varphi$$取决于所选用的正交函数
对各个模式类别，正交函数都是**相同的**，但其展开系数向量$$a\_i$$则因类别的不同模式分布而异
{% endhint %}
K-L展开式的根本性质是将随机向量x展开为另一组正交向量$$\varphi\_j$$的线性和，且其展开式系数$$a\_j$$（即系数向量a的各个分量）具有不同的性质。
### 三、变换矩阵和系数的计算
设随机向量x的**总体自相关矩阵**为$$R=E{xx^T}$$，由：
$$
x=\sum\_{j=1}^n a\_j\varphi\_j=\varphi a,\ \ T\_1\leq t\leq T\_2 \tag{2}
$$
将$$X=\varphi a$$带入自相关矩阵，可得：
$$
\begin{align} R &= E{\varphi a a^T\varphi^T} \notag \ &= \varphi (E{aa^T})\varphi^T \notag \end{align}
$$
要求系数向量$$\boldsymbol{a}$$的各个不同分量应**独立**，即应使$$(a\_1, a\_2, …, a\_j, …, a\_n)$$满足如下关系：
$$
E(a\_ja\_k) = \begin{cases} \lambda\_j & j=k \ 0 & j\neq k \end{cases}
$$
写成矩阵形式，应使：$$E{a a^T} = D\_\lambda$$，其中$$D\_\lambda$$为对角形矩阵，其互相关成分均为0，即：
$$
D\_\lambda = \begin{bmatrix} \lambda\_1 & 0 & \cdots & \cdots 0 \ 0 & \ddots & 0 & \cdots & 0 \ 0 & \cdots & \lambda\_j & \cdots & 0 \ 0 & \cdots & 0 & \ddots & 0 \ 0 & \cdots & \cdots & 0 & \lambda\_n \end{bmatrix}
$$
则自相关矩阵可以写成：
$$
R=\varphi D\_\lambda \varphi^T
$$
由于$$\varphi$$中各个向量都相互**归一正交**，因此有：
$$
R\varphi = \varphi D\_\lambda \varphi^T \varphi = \varphi D\_\lambda
$$
其中，$$\varphi\_j$$向量对应为：
$$
R \varphi\_j=\lambda\_j\varphi\_j
$$
可以看出，$$\lambda\_j$$是x的自相关矩阵R的**特征值**，$$\varphi\_j$$是对应的**特征向量**。因为R是实对称矩阵，其不同特征值对应的特征向量应正交，即：
$$
\varphi\_j^T\varphi\_k = \begin{cases} 1 & j=k \ 0 & j\neq k \end{cases}
$$
带入式$$(2)$$，K-L展开式的系数为：
$$
a = \varphi^Tx
$$
{% hint style="success" %}
总结而言，计算l K-L展开式系数可以分为以下三步：
1. 求随机向量x的自相关矩阵：$$R = E{xx^T}$$
2. 求R的特征值和特征向量，得到矩阵$$\varphi=(\varphi\_1,\varphi\_2,\dots,\varphi\_n)$$
3. 求展开式系数：$$a=\varphi^Tx$$
{% endhint %}
## 4.3.2 按照K-L展开式选择特征
* K-L展开式用于特征选择相当于一种线性变换
* 若从n个特征向量中取出m个组成变换矩阵$$\varphi$$，即：
$$
\varphi = (\varphi\_1\ \varphi\_2\ \dots\ \varphi\_m),\ m\**最小均方差条件下**接近原来的向量x
对于$$x=\sum\limits\_{j=1}^n$$，现在仅仅取m项，**对略去的系数项用预先选定的常数b代替**，此时对x的估计值为：
$$
\hat{x} = \sum\_{j=1}^ma\_i\varphi\_i + \sum\_{j=m+1}^nb\varphi\_j
$$
则产生的误差为：
$$
\Delta x = x - \hat{x} = \sum\_{j=m+1}^n(a\_j-b)\varphi\_j
$$
此时$$\Delta x$$的**均方差**为：
$$
\begin{align} \overline{\varepsilon^2} &= E{\Vert\Delta x\Vert}^2 \nonumber \ &= \sum\_{j=m+1}^n{E(a\_j-b)^2} \nonumber \end{align}
$$
要使得$$\overline{\varepsilon^2}$$最小，则对b的选择应满足：
$$
\begin{align} \frac{\partial}{\partial b}\[E(a\_j-b)^2] &= \frac{\partial}{\partial b}\[E(a\_j^2-2a\_jb+b^2)] \nonumber \ &= -2\[E(a\_j)-b] \nonumber \ &=0 \nonumber \end{align}
$$
因此，$$b=E\[a\_j]$$，即**对省略掉的a中的分量，应使用它们的数学期望来代替**，此时的误差为：
$$
\begin{align} \overline{\varepsilon^2} &= \sum\_{j=m+1}^nE\[(a\_j-E{a\_j})^2] \nonumber \ &= \sum\_{j=m+1}^n\varphi^T\_jE\[(x-E{x})(x-E{x})^T]\varphi\_j \nonumber \ &= \sum\_{j=m+1}^n\varphi\_j^TC\_x\varphi\_j \nonumber \end{align}
$$
其中，$$C\_x$$为x的**协方差矩阵**
设$$\lambda\_j$$为$$C\_x$$的第j个特征值，$$\varphi\_j$$是与$$\lambda\_j$$对应的特征向量，则：
$$
C\_x\varphi\_j = \lambda\_j\varphi\_j
$$
由于$$\varphi\_j$$是一个正交阵，因此有：
$$
\varphi\_j^T\varphi\_j=1
$$
从而
$$
\varphi\_j^TC\_x\varphi\_j = \lambda\_j
$$
因此
$$
\begin{align} \overline{\varepsilon^2} &= \sum\_{j=m+1}^n\varphi\_j^TC\_x\varphi\_j \nonumber \ &= \sum\_{j=m+1}^n\lambda\_j \end{align}
$$
由此可以看出，**特征值越小，误差也越小**
### 结论
从K-L展开式的性质和按最小均方差的准则来选择特征，应使$$E\[a\_j]=0$$。由于$$E\[a]=E\[\varphi^Tx]= \varphi^TE\[x]$$，故应使$$E\[x]=0$$。基于这一条件，在将整体模式进行K-L变换之前，应先将其均值作为新坐标轴的原点，采用协方差矩阵C或自相关矩阵R来计算特征值。如果$$E\[x]\neq0$$，则只能得到“次最佳”的结果。
将K-L展开式系数$$a\_j$$（亦即变换后的特征）用$$y\_j$$表示，写成向量形式：$$y= \varphi^Tx$$。此时变换矩阵$$\varphi$$用m个特征向量组成。为使误差最小，不采用的特征向量，其对应的**特征值应尽可能小**。因此，将特征值按大小次序标号，即
$$
\lambda\_1\gt\lambda\_2\gt\dots\gt\lambda\_m\gt\dots\gt\lambda\_n\geq0
$$
若首先采用前面的m个特征向量，便可使变换误差最小。此时的变换矩阵为：
$$
\varphi^T = \begin{pmatrix} \varphi\_1^T\ \varphi\_2^T\ \vdots\ \varphi\_m^T \end{pmatrix}
$$
K-L变换是在均方误差最小的意义下获得数据压缩（降维）的最佳变换，且不受模式分布的限制。对于一种类别的模式特征提取，它不存在特征分类问题，只是实现用低维的m个特征来表示原来高维的n个特征，使其误差最小，亦即使其整个模式分布结构尽可能保持不变。
通过K-L变换能获得互不相关的新特征。若采用较大特征值对应的特征向量组成变换矩阵，则能对应地保留原模式中方差最大的特征成分，所以K-L变换起到了减小相关性、突出差异性的效果。在此情况下， K-L变换也称为**主成分变换**（**PCA变换**）。
{% hint style="warning" %}
需要指出的是，采用K-L变换作为模式分类的特征提取时，要特别注意保留不同类别的模式分类鉴别信息，仅单纯考虑尽可能代表原来模式的主成分，有时并不一定有利于分类的鉴别。
{% endhint %}
#### K-L变换的一般步骤
给定N个样本$$x^1,\dots,x^N$$，利用KL变换将其降至m维的步骤：
1. 计算样本均值：$$\boldsymbol m =E(\boldsymbol x)$$
2. 平移样本：$$\boldsymbol{z=x-m}$$
3. 计算$$\boldsymbol z$$的自相关矩阵：$$R(z)=\sum\limits\_{i=1}^N p(\omega\_i)E(\boldsymbol{z\ z}^T)=C\_x$$
4. 求协方差矩阵$$C\_x$$的特征向量，取最大的m个特征值对应的m个特征向量构成变换矩阵$$\Phi$$
{% hint style="info" %}
给定两类模式，其分布如图所示，试用K-L变换实现一维的特征提取（假定两类模式出现的概率相等）
$$
m = \frac{1}{5}\sum\_{j=1}^{N\_i}x\_{1j}+\frac{1}{5}\sum\_{j=1}^{N\_i}x\_{2j}=0
$$
这符合K-L变换进行特征压缩的最佳条件。
由于$$P(\omega\_1)=P(\omega\_2)=0.5$$，故：
$$
\begin{align} R &= \sum\_{j=1}^2P(\omega\_i)E{xx^T} \nonumber \ &= \frac{1}{2}\left\[\frac{1}{5}\sum\_{j=1}^5x\_{1j}x\_{1j}^T\right] + \frac{1}{2}\left\[\frac{1}{5}\sum\_{j=1}^5x\_{2j}x\_{2j}^T\right] \nonumber \ \ &= \begin{pmatrix} 25.4 & 25.0\ 25.0 & 25.4 \end{pmatrix} \end{align}
$$
解特征值方程$$\vert R-\lambda E\vert$$，求R的特征值：$$\lambda\_1=50.4,\lambda\_2=0.4$$，求解对应的特征向量，得到：
$$
\varphi\_1=\frac{1}{\sqrt{2}} \begin{pmatrix} 1 \ 1 \end{pmatrix} \ \varphi\_2=\frac{1}{\sqrt{2}} \begin{pmatrix} 1 \ -1 \end{pmatrix}
$$
取较大的特征值$$\lambda\_1$$对应的变换向量作为变换矩阵，由$$y=\varphi^Tx$$得到变换后的一维模式特征为：
$$
\omega\_1:\left{-\frac{10}{\sqrt2},-\frac{9}{\sqrt2},-\frac{9}{\sqrt2},-\frac{11}{\sqrt2},-\frac{11}{\sqrt2}\right} \ \omega\_2:\left{\frac{10}{\sqrt2},\frac{11}{\sqrt2},\frac{11}{\sqrt2},\frac{9}{\sqrt2},\frac{9}{\sqrt2}\right}
$$
{% endhint %}
上面的例子中可以看到
## 绘图代码
```python
import matplotlib.pyplot as plt
import numpy as np
x = [4, 5, 5, 5, 6, -4, -5, -5, -5, -6]
y = [5, 4, 5, 6, 5, -5, -4, -5, -6, -5]
plt.plot([5, -5], [5, -5], color='red', linestyle='--')
plt.arrow(0, 0, 2, 2, head_width=0.2, head_length=0.5, fc='black', ec='black', zorder=2)
plt.arrow(0, 0, 2, -2, head_width=0.2, head_length=0.5, fc='black', ec='black')
plt.plot(x[0:5], y[0:5], 'o', color='white', markeredgecolor='blue')
plt.plot(x[5:10], y[5:10], 'o', color='blue')
plt.annotate('$\\phi_1$', xy=(2, 1.2), xytext=(2, 1.2), fontsize=12)
plt.annotate('$\\phi_2$', xy=(2, -3), xytext=(2, -3), fontsize=12)
plt.axhline(0, color='black', linewidth=0.5)
plt.axvline(0, color='black', linewidth=0.5)
plt.gca().set_aspect('equal', adjustable='box')
plt.grid(True)
plt.show()
```