第 3 章 k-近邻

k-近邻基本算法

评价分类效果的常见指标

影响算法精确度的若干问题

k-近邻算法示例

从本章开始的三章，我们要处理的主要都是分类问题。分类问题与聚类问题不同，它已经知道了用于训练的数据对象的每个所属的类别标号，我们需要解决的问题是，对于不知道标号的数据对象（一般称为测试对象、目标对象或者新对象），给它们分配标号。一般而言，每个数据对象有且仅有一个标号。因为已知训练集中的类别标号（能够有一个客观的标准来进行判断），所以分类问题在机器学习教材中通常被称为“有监督的学习”。

分类问题的实质是预测，通过已知的信息，包括训练集中数据对象的特征和类别标号，以及测试集中数据对象的特征，来预测未知的信息，即测试集中数据对象的类别标号。这与聚类不一样，聚类是属于描述性的问题，让我们看到隐藏在原始数据中的一些深刻模式。 一般而言，数据挖掘的问题都是分为这两类：一种是描述性的（如聚类），一种是预测性的（如分类）。因为分类在数据挖掘中特别重要，所以我们往往把它视作单独的一类，与预测相区分，后者狭义上指数值的预测，如回归分析就是要解决这类问题。

解决分类问题的模型和算法称为分类器（classifier），解决预测问题的模型和算法称为预测器（predictor）。但是正如我们刚才讲的，分类问题也是一种预测问题，实际上很多分类器稍微变化一下，但也可以用于预测器。例如，本章要介绍的 k-近邻（k-Nearest Neighbor，k-NN）算法，主要是用于分类，也可以看作一种回归预测的工具。在搜索引擎上查询“k-NN regression”，就可以看到很多k-NN用来进行数值预测的方法和应用。后面也会通过电子商务的简单例子来介绍k-近邻回归。

本章将先介绍 k-近邻的基本算法——这部分非常简单，因为 k-近邻算法是所有数据挖掘著名算法中最简单的；然后，讨论影响 k-近邻算法精确度的若干重要因素，这对读者真正用好 k-近邻算法至关重要；最后，给出一个具体的示例，帮助读者理解算法的过程。