2.5.3 维度归约

2.5.3 维度归约

维度归约使用数据编码或变换，以便得到原数据的归约或“压缩”表示。如果原数据可以由压缩数据重新构造而不丢失任何信息，则该数据归约是无损的。如果我们只能重新构造原数据的近似表示，则该数据归约是有损的。有一些很好的串压缩算法。尽管它们通常是无损的，但是只允许有限的数据操作。本节，我们介绍另外两种流行、有效的有损的维归约方法：小波变换和主成分分析。

1. 小波变换

离散小波变换（DWT）是一种线性信号处理技术，当用于数据向量X时，将它变换成数值上不同的小波系数向量X'。两个向量具有相同的长度。当这种技术用于数据归约时，每个元组看作一个n维数据向量，即X = (x1, x2, ., xn），描述n个数据库属性在元组上的n个测量值。

“如果小波变换的数据与原数据的长度相等，这种技术如何能够用于数据归约？”关键在在我们的记号中，代表向量的变量用粗斜体，描述向量的度量用斜体。

于小波变换后的数据可以截短。仅存放一小部分最强的小波系数，就能保留近似的压缩数据。

例如，保留大于用户设定的某个阈值的所有小波系数，其他系数置为0。这样，结果数据表示非常稀疏，使得如果在小波空间进行计算，利用数据稀疏特点的操作计算得非常快。该技术也能用于消除噪声，而不会光滑掉数据的主要特征，使得它们也能有效地用于数据清理。给定一组系数，使用所用的DWT的逆，可以构造原数据的近似。

DWT与离散傅里叶变换（DFT）有密切关系，DFT是一种涉及正弦和余弦的信号处理技术。然而一般地说，DWT是一种更好的有损压缩。也就是说，对于给定的数据向量，如果DWT和DFT保留相同数目的系数，DWT将提供原数据的更准确的近似。因此，对于等价的近似，DWT比DFT需要的空间小。不像DFT，小波空间局部性相当好，有助于保留局部细节。

只有一种DFT，但有若干族DWT。图2-16显示了一些小波族。流行的小波变换包括Haar-2, Daubechies-4和Daubechies-6变换。应用离散小波变换的一般过程使用一种分层金字塔算法（pyramid algorithm），它在每次迭代将数据减半，导致很快的计算速度。该方法如下： 

图2-16 小波族的例子。小波名后的数是小波的消失瞬间。这是系数必须满足的数学联系集，并且与小波系数的个数有关

（1）输入数据向量的长度L必须是2的整数幂。必要时（L≥n），通过在数据向量后添加0， 这一条件可以满足。

（2）每个变换涉及应用两个函数。第一个使用某种数据光滑，如求和或加权平均。第二个进行加权差分，产生数据的细节特征。

（3）两个函数作用于X中的数据点对，即用于所有的测量对（x2i, x2i+1）。这导致两个长度为L/2的数据集。一般，它们分别代表输入数据的光滑后的版本或低频版本和它的高频内容。

（4）两个函数递归地作用于前面循环得到的数据集，直到得到的数据集长度为2。

（5）由以上迭代得到的数据集中选择值，指定其为数据变换的小波系数。等价地，可以将矩阵乘法用于输入数据，以得到小波系数。所用的矩阵依赖于给定的DWT。矩阵必须是标准正交的，即列是单位向量并相互正交，使得矩阵的逆是它的转置。尽管受篇幅限制，这里我们不再讨论，但这种性质允许由光滑和光滑-差数据集重构数据。通过将矩阵因子分解成几个稀疏矩阵，对于长度为n的输入向量，“快速DWT”算法的复杂度为O (n)。

小波变换可以用于多维数据，如数据立方体。可以按以下方法做：首先将变换用于第一个维，然后第二个，如此下去。计算复杂性关于立方体中单元的个数是线性的。对于稀疏或倾斜数据和具有有序属性的数据，小波变换给出很好的结果。据报道，小波变换的有损压缩比当前的商业标准JPEG压缩好。小波变换有许多实际应用，包括指纹图像压缩、计算机视觉、时间序列数据分析和数据清理。

2. 主成分分析

这里，作为一种维度归约方法，我们直观地介绍主成分分析。详细的理论解释已超出本书范围。

假定待归约的数据由n个属性或维描述的元组或数据向量组成。主成分分析（principal components analysis）或PCA（又称Karhunen-Loeve或K-L方法）搜索k个最能代表数据的n维正交向量，其中k≤n。这样，原来的数据投影到一个小得多的空间，导致维度归约。不像属性子集选择通过保留原属性集的一个子集来减少属性集的大小，PCA通过创建一个替换的、更小的变量集“组合”属性的基本要素。原数据可以投影到该较小的集合中。PCA常常揭示先前未曾察觉的联系，并因此允许解释不寻常的结果。

基本过程如下：

（1）对输入数据规范化，使得每个属性都落入相同的区间。此步有助于确保具有较大定义域的属性不会支配具有较小定义域的属性。

（2）PCA计算k个标准正交向量，作为规范化输入数据的基。这些是单位向量，每一个方向都垂直于另一个。这些向量称为主成分。输入数据是主成分的线性组合。

（3）对主成分按“重要性”或强度降序排列。主成分基本上充当数据的新坐标轴，提供关于方差的重要信息。也就是说，对坐标轴进行排序，使得第一个坐标轴显示数据的最大方差，第二个显示次大方差，如此下去。例如，图2-17显示原来映射到轴X1和X2的给定数据集的前两个主成分Y1和Y2。这一信息帮助识别数据中的分组或模式。

（4）既然主成分根据“重要性”降序排列，就可以通过去掉较弱的成分（即方差较小）来归约数据的规模。使用最强的主成分，应当能够重构原数据的很好的近似。

图2-17 主成分分析。Y1和Y2是给定数据的前两个主成分

PCA计算开销低，可以用于有序和无序的属性，并且可以处理稀疏和倾斜数据。多于2维的多维数据可以通过将问题归约为2维问题来处理。主成分可以用作多元回归和聚类分析的输入。与小波变换相比，PCA能够更好地处理稀疏数据，而小波变换更适合高维数据。