第5章　单类数据降维

类表示公理与归类公理清楚说明了类相似性映射在归类问题中具有极其重要的作用。因此设计合理的类相似性映射，避免产生相似性悖论，是解决归类问题的关键。而设计合理的类相似性映射，需要合理的对象特性输入与输出表示。如果对象特性表示不合理，类相似性映射就失去了合理的基础。比如以人的外貌美丑、胖瘦、高矮、肤色、语言等来表征人的善恶，那么可以想象无论如何设计类相似性映射，都很难得到理想的归类结果。对于这样的问题，模式识别的先驱之一渡边慧（美籍日裔）提出了著名的丑小鸭定理：如果没有合适的表征（对象特性表示），丑小鸭与白天鹅之间的相似性与两只白天鹅之间的相似性一样大。丑小鸭定理的一个形象例子，可见唐朝诗人白居易的两句诗：“草萤有耀终非火，荷露虽团岂是珠。”因此，发现合适的对象特性表示，对于归类问题至关重要。

通常，在信息获取阶段，判定特征与学习任务是否匹配依赖于领域知识，通常属于领域专家的工作。信息采集过程中一旦丢失重要的特征将严重损害学习效果，甚至导致完全不可学习，因此，一般倾向于多采集一些相关特征。然而，相关特征过多又会导致“维数灾难”（curse of dimensionality）问题。维数灾难最早是由理查德·贝尔曼（Richard E. Bellman）在考虑动态优化问题时提出来的术语，用来描述当（数学）空间维度增加时，高维空间（通常有成百上千维）因体积指数增加而遇到的各种计算问题，这样的难题在低维空间中不会遇到。在机器学习中，是指随着特征维数的增加，同样规模的训练样本在输入空间越来越稀疏，学习算法搜索到正确知识表示的计算复杂度呈指数级增长。处理维数灾难的一种经典方法是数据降维。

本章将讨论在给定对象的特性表示后，如何从中得到更合理的数据特征，即数据降维问题。为简单起见，对于对象O=｛o1，o2，…，oN｝，假设对象特性输入表示为｛x1，x2，…，xN｝，其中，∀k，xk是一个p×1实向量，因此对象特性输入表示可简写为X=［xrk］p×N，即对象可表示在一个p维空间中的隐藏结构之中。同样的，这些对象假设具有的对象特性输出表示为｛y1，y2，…，yN｝，其中，∀k，yk是一个d×1实向量，可简写为Y=［yrk］d×N，即对象可以在一个低维空间中表示，这里，p>> d。这样的一个归类问题，称为数据降维问题。

如果U未知且c>1，此时的数据降维问题称为无监督数据降维。否则称为有监督数据降维问题。显然，数据降维问题具有归类输入和归类输出。本章中，我们先研究最简单的情形，即c=1的情形。此时无论U已知还是未知，都不提供任何有用的归类信息，因此单类降维问题属于无监督学习。在这个假设下，与显然成立。类表示唯一公理要想成立，只需要求。但是类表示唯一公理不一定成立。当类表示唯一公理不成立时，作为类表示唯一公理的弱化版本（类一致性准则）必然要成立。即，与尽可能近似。如果类表示唯一公理成立，类紧致性准则要求最佳应使得类尽可能紧致。以上分析告诉我们，此时最重要的是得到输入类认知表示和输出类认知表示。据此，我们可以研究许多典型的数据降维算法。