1.4.2　一个简单的分类示例

与回归对应，给出一个简单的分类例子并通过一个示例样本集和一个简单算法进行说明。图1.4.7所示的是一组训练样本，其中特征向量x是两维的，故可显示于平面图中。该样本集包含3种类型，y_n只取3个不同值，y_n的取值可分别用C₁、C₂、C₃表示，图1.4.7中对应用3种不同的符号表示，分别是“+”“×”和“*”。图1.4.7中实心圆表示一个待分类的新样本。

图1.4.7　分类标注样本的例子

讨论一种最基本的分类算法：K近邻算法（K-nearest neighbors，KNN）。x是二维的情况可直观地描述KNN算法。对于给定的近邻数K，当给出一个新的待分类样本时，以该样本为中心形成一个圆（三维以上情况时对应为超球体），半径逐渐扩大直到圆内包含了K个训练集样本，将圆内包含的K个训练样本表示为D_K，统计D_K内各类型样本数，对本例只需用K₁、K₂、K₃表示各类型的数目，若其中最大的是K_i，则将新样本分类为C_i。例如，图1.4.7的待分类样本，取K=10，计数得到K₁=1，K₂=8，K₃=1，显然，可将该样本分类为C₂，即图中“×”所示的样本类。

KNN算法是一种非参数方法。KNN算法也存在欠拟合、过拟合、超参数确定等问题。近邻数目K是一个超参数，它不能由学习过程确定，需要预先确定。当K取最小值1时（可称为最近邻方法），对样本集自身可完全正确分类（即样本自身的标注）。但对于新输入，由于只由最近的一个训练集样本的类型确定其类型输出，对分类结果的可信度不高，分类误差（即泛化误差）较大，这是一种过拟合。但当K很大时，如极限情况K=N即K为训练集样本数时，对于所有的新输入，输出类型都由训练集中数目最多的类型作为输出，无法反映样本集的局部性质，这显然是一种欠拟合情况。

本节通过两个易于理解的示例，直观地介绍了机器学习中的一些基本术语。包括模型、训练集、测试集、训练误差、测试误差、欠拟合、过拟合、泛化性能、正则化等。可以看到，在一种简单模型下，在给定的数据集下，因模型复杂度不同可能存在欠拟合或过拟合，训练误差和测试误差随模型复杂度有不同表现、泛化性能不同等现象。在完整的机器学习框架内，问题更复杂，尤其不同类型模型之间的各类性能更是相差甚远。解决一个实际问题时，会遇到诸如模型表达能力、训练集规模、泛化误差界等问题，需要更好的理论指导。机器学习中的重要分支——机器学习理论关注从理论上回答这些问题，但遗憾的是，目前学习理论的结果与应用需求之间还有很大的缝隙，实际中更多的还是通过交叉验证等更实用的技术手段来解决这些问题。