2.4　归类方法设计准则

类表示公理和归类公理总共有5条公理。其中类表示存在公理和归类等价公理是必然成立的公理。原因如下：类表示存在公理是归类算法能够设计的基础，仅仅要求输入输出有对应的类内部表示。如果输入输出没有类的内部表示，就失去了学习内容的内涵，学习自然无从进行了。归类等价公理假设类的外显指称与其对应的内蕴指称一致，即一个归类算法的外显功能与其内部实现的功能应该相同，这也是对归类算法甚至是对一般算法的期望。否则，给予的学习材料是《红楼梦》，希望学到的内涵是代数几何，就没有实现的可能。因此，设计归类算法真正需要考虑的是两条可分性公理和类表示唯一公理。

归类结果满足两条可分性公理是最低要求，是归类结果应该满足的底线。不满足可分性公理的归类结果不能令人满意，但是只满足可分性公理也不可能保证其是理想的归类结果。理由如下：样本可分性公理只要求任意一个对象只有一个类与其最相似，但是可能还存在另外的类与其相似程度也很高。比如，有A，B，C，D四个类，对象x与类A的相似性是0.251，对象x与类B的相似性是0.25，对象x与类C的相似性也是0.25，对象x与类D的相似性是0.249。样本可分性公理要求将对象x指派到与其具有最高相似度的类A中，但仅仅因为最相似性类与次相似类的相似程度有一线之差就决定类别归属，这样的归类显然抗噪性不强。同样的分析对于类可分性公理也成立。因此，仅仅满足可分性公理的归类结果有时很难是期望的归类结果。实际上，定理2.1和定理2.2清楚地表明了类可分性公理和样本可分性公理对于归类结果的要求之松。因此，可分性公理需要增强。类表示唯一公理要求三个等式成立，对于归类结果的要求是很强的。如果类表示唯一公理成立，则其归类错误率为零，其要求太高，需要适当放低。

根据以上的分析，可以给出归类方法设计的三个准则：类紧致性准则、类分离性准则和类一致性准则。但是，在设计归类算法的时候，这三条设计准则彼此地位并不相同。这是由于三条设计准则依据的公理在归类问题中的地位是不等价的。首先，类表示唯一公理是归类问题的最强约束，其成立与否，对于归类算法的设计影响巨大。如果类表示唯一公理不成立，设计归类算法时就需要首先考虑类一致性准则，以便使得类表示唯一公理尽可能成立。如果假设类表示唯一公理成立，就需要考虑类紧致性准则和类分离性准则。

2.4.1　类一致性准则

如果一个归列算法的输入为，其输出满足类表示唯一公理，则归类结果错误率为零。然而，类表示唯一公理一般不能保证为真，即使人类认知系统也难以总是遵循类表示唯一性公理。类表示唯一性公理对归类是一个非常严格的要求。通常，人类认知系统尽可能使归类输入输出满足类表示唯一性公理。因此，合理的归类准则应该在类表示唯一性公理不成立的情况下，使得类表示唯一公理尽可能近似成立，由此可以得到类一致性准则。

类一致性准则（Categorization Consistency Principle）：如果类表示唯一性公理不成立，一个好的归类结果应该使类表示唯一性公理在逼近意义下尽可能成立。

类一致性准则可以用来设计一些归类判据。对于归类问题来说，归类等价公理必须成立，因此，类表示唯一公理中的三个约束可以简化成两个。于是，类一致性判据可以表示成如下形式。

类一致性判据（Categorization Consistency Criterion）：称作类一致性判据，当且仅当的最优值对应着使得和之间具有最小误差的归类结果。

当类表示唯一性公理不成立时，无论类数是几，类一致性判据是归类算法设计的首选。通常情形下，对于一个具体的学习问题，与不能同时已知。设计算法时，通常用逼近或者代替。在很多归类算法中，为简单计，类表示唯一性公理被假设为真但实际上并不为真。在这样的假设下，将使用类紧致性准则或类分离性准则来设计归类算法。下面讨论类紧致性准则和类分离性准则。

2.4.2　类紧致性准则

遵守样本可分性公理只是归类结果的一个最低需求，是归类结果应该满足的归类底线。理论上，对于好的归类结果，仅遵从样本可分性公理不是充分条件。一个好的归类结果应该尽可能远离归类底线，不能以恰好没有突破归类底线为设计标准。换句话说，对任意对象，其最相似类的相似程度要尽可能大于其次相似类的相似程度。一般地，如果任意对象的最相似类的相似程度越大，则归类结果越紧致。因此，当设计一个归类方法时，类紧致性准则可表示为：

类紧致性准则（Category Compactness Principle）：归类方法应该使其归类结果尽可能紧致。更详细地说，就是每个对象的最相似类与其次相似类的相似度差别要大。这等价于确保一个对象和它所属类具有最小相异度。

根据类紧致性准则，紧致性具有最大化类内相似度或最小化类内方差两种表现形式。

当然，当类紧致性定义后，类紧致性准则可以直接用来设计一个归类标准。不同的需求产生不同的归类紧致性判据定义，归类紧致性判据的常用定义如下。

类紧致性判据（Category Compactness Criterion）：对于归类输入，JC：称为类紧致性判据，如果的最优值对应的归类输入有最大的类紧致性。

对于归类结果，称为类紧致性判据，如果JC（Y，V，，DsY）的最优值对应的归类结果有最大的类紧致性。

显然，当类数为1时，类紧致性准则依然成立。原因很简单，一个理想的类相似性映射也要求满足类紧致性准则。

一般地，如果知道类相异性映射，可以表示成公式（2.2）：

可以表示成公式（2.3）：

除了公式（2.2）和公式（2.3），当然也可以有其他的表示。理论上，符合类紧致性条件的表示是很多的。

类似地，如果知道类相似性映射且U，V是硬划分，可以表示成公式（2.4）：

可以表示成公式（2.5）

同样地，和也可以有其他表示。

需要指出的是，对于归类问题，经常属于未知部分。通常，SimX和SimY由设计者根据任务需要事先给定，并不需要学习。因此，常常需要学习。当应用类紧致性准则设计归类算法时，一般假设类唯一性公理成立，至少部分成立。当X=Y时，为简单计，除要求之外，甚至假设SimX=SimY或者DsX=DsY。这种假设实际上比类表示唯一公理的要求还高。在这种情况下，可以利用或者来计算。原因很简单，此时或者。

2.4.3　类分离性准则

如果归类结果满足类可分性公理，则仅仅满足不会是一个好的归类结果。一般一个归类结果的类间距离越大越好。

类分离性准则（Category Separation Principle）：一个好的归类结果应该使得不同类表示的差异最大。

如果用类间距离表示不同类表示的差异，显然类分离性准则意味着归类方法要定义类间距离，类间距离越大越好。也就是说，归类方法的输出结果应尽可能远离违反类可分性公理的情形，不能以仅仅满足类可分性公理为满足。类分离性准则有助于设计度量类可分性的归类判据。类可分性判据的常用定义如下：

类分离性判据（Category Separation Criterion）：，是类分离性判据，如果的最优值对应着具有最大类间距离的归类结果。

类分离性判据可以用来判定归类结果远离违反类可分性公理的程度，甚至可以设计归类算法。当类数为1时，类分离性判据不能使用。

2.4.4　奥卡姆剃刀准则

对于一个具体的归类问题，可能存在很多不同的类表示模型性能相近，这些类表示模型有的复杂，有的简单。而类紧致、类分离与类一致性准则都是从具有同一形式的类表示中选取其中具有最佳参数的类表示，并没有考虑类表示自身的复杂度问题，因此，这三条归类设计准则不能用来处理基于复杂度的类表示选择问题。那么，根据什么原则，才能从形式不同复杂度差异极大的类表示中选出最适合人类认知的归类模型？

历史上著名的奥卡姆剃刀（Occam's razor）准则是处理这类问题的基本原则。该准则要求“如无必要，勿增实体”。说得更简单一点，对于性能相同或者相近的模型或理论，人们偏爱简单的那一个。也就是说，对一个归类问题，在同样有效的前提下，人们应该选择简单的归类模型。什么是简单的归类模型呢？这需要定义类表示的复杂度。在定义了类表示的复杂度之后，在同样的性能条件下，奥卡姆剃刀准则要求选择复杂度最小的类表示模型。需要特别指出的是，人们在设计各种机器学习算法时都是遵循奥卡姆剃刀准则的，从来没有例外。只是，类表示复杂度的定义需要根据情景而定。下面，我们使用奥卡姆剃刀准则来研究归类模型的复杂度。

在不考虑学习任务背景要求的情况下，什么是简单的归类模型呢？这时可以直接考虑归类问题的归类输入和对应的归类输出的复杂性。因此，归类输入输出表示简单的模型，被认为是相对简单的模型。那么怎么定义归类输出输入的复杂度呢？一个简单的方式是用归类输入输出中考虑的元组数来定义归类问题的复杂度。理论上，需要考虑的元组数越多，对应的归类模型越复杂。对于单源数据学习来说，最复杂的归类模型需要考虑的元组数多达8种。归类模型考虑的元组数越少，越简单。

当类别数为1时，由于和恒成立，故归类公理对于单类学习问题自然成立。对于单类学习问题，一般不必考虑对（U，SimX，V，SimY）的约束条件，而只需要考虑四元组。这样归类问题的表示就从八元组降为四元组，因此单类学习问题在机器学习研究中是一个相对简单的问题，在本书中首先论述。对于单类问题来说，最简单的是X=Y，此时只需考虑三元组。而如果X与Y部分相同、部分不同但X与Y的维数相同，则该问题更复杂一些。单类问题中，最复杂的情形是X与Y的维数都不同，这时归类模型需要考虑四元组。本书中将按照这个次序，对单类问题进行分析论述。

如果c>1，则为多类问题。此时归类公理不再当然成立。在最一般的情形下，需要考虑八元组。此时，如果X=Y，则可以将八元组降低，因此X=Y是比X≠Y更为简单的归类问题。因此，在本书中，我们首先讨论X=Y的多类问题，然后讨论X≠Y的多类问题。当X=Y时，如果假设归类公理和类表示唯一公理成立时，显然是最简单的情形。这时如果U已经知道，显然类表示唯一公理不可能成立，否则学习就不会是一个很难的问题了。因此，U未知比已知要简单得多。如果U未知，归类公理和类表示唯一公理都成立，这种情形下，只需要考虑或者）一个四元组就够了，此时对应的是聚类问题。

如果U已知且c>1，对应的是分类问题，则复杂得多。考虑到归类等价公理总是成立，由于Y已经知道而V可由SimY等价代替，对于只需考虑即可。同样的，对于，只需考虑（X，U）即可。在此情形下，我们只需考虑四元组即可，但注意此时依然要输出V，因此，要考虑五元组。此时，要想对分类模型进一步简化，就必须考虑的复杂度。的不同复杂度在一定意义上也反映了分类算法的复杂度。在分类算法论述方面也可以利用奥卡姆剃刀准则，优先介绍简单的分类模型，本书正是遵照这一基本规则进行组织的。

根据上面的分析，单类问题比多类问题简单，多类问题中，输入特征与输出特征相同比不同要简单。这与人类的直觉是一致的。后面，我们将根据奥卡姆剃刀准则意义下的模型复杂度由浅入深地逐步讨论归类模型。即首先讨论单类问题，然后讨论多类问题。

在本章中，假设学习算法是单源数据输入，单源数据输出。在实际应用中，学习算法输入输出都不一定是单源的。一般意义上，机器学习不特别指明，是指单源数据学习。理论上，类表示公理与归类公理对于任意学习算法都应该成立，无论是单源数据学习还是多源数据学习。容易知道，多源数据学习比单源数据学习要复杂得多。因此，在本书中首先讨论单源数据学习，即单源数据输入，单源数据输出；在最后的章节讨论多源数据学习。

最后，需要说明的是，虽然奥卡姆剃刀准则可以在归类的意义下比较机器学习不同模型的复杂度，但是在设计具体的学习算法设计时，奥卡姆剃刀准则并不能独立使用，一般与其他归类设计准则一起使用。这一点与其他归类设计准则非常不同，类一致性准则、类紧致准则和类分离性准则在设计学习算法时都可以独立使用。