1. 基于样本的学习

对于一个机器学习系统，输入有下面三个方面的内容组成：
样本（instance）
特征（attributes / features)
标签（classes / labels）

什么是样本：
对监督学习来说，每个样本可以看做是一个包含 $n$ 个特征的元组同时拥有一个表明类别的标签。

机器学习的目的：
根据数据提供的 $label$ 标签，试图构建一个模型，这个模型可以代表整个数据集的输入和输出关系。

基于样本的学习（instance-based learning）：
需要将进行标注的 $instance$ 保存在内存中，直接从 $instance$ 中学习（而不建立任何的模型），也称为 $memory-based \: \: learning$ 。

2. 比较样本

如何比较样本（Comparing Instances）呢？

对于每个 $instance$ ，因为它的特征是一个 $n$ 元组，那么我们总是可以把这个 $n$ 元组看成是一个向量 $\vec{f}$ 。

2.1 特征向量

特征的类型：
$nomial / categorial / discrete$ ：例如颜色，性别。
$ordinal$ ：这类特征是有严格顺序的，例如描述温度程度的特征 $cool < mild < hot$ 。
$numeric / continuous$ ：这种是连续的数值特征：例如身高、体重、年龄。

特征向量根据之前的描述，我们可以看做一个 $n$ 元组，那么我们可以将描述这个向量的 $n$ 维空间看做是向量的特征空间。通过这种方式，我们可以衡量任意两个具有相同维度的特征向量的相似度、长度等很多指标来实现对向量定量计算和判断的目的。

2.2 特征向量的度量（Similarity / Distance）

2.2.1 特征向量的度量——向量

相似度 （Similarity）
两个向量的相似度：衡量两个向量之间有多像。
相似度的值越大代表相似度越高。通常相似度的取值范围在 $[0,1]$ 之间

余弦相似度（Cosine Similarity）
给定两个 $instance$ ，他们的特征向量分别是 $\vec{a}, \vec{b}$ ，可以通过计算两个特征向量的角度作为余弦相似度：
$cos(A,B)=\frac{\sum_ia_ib_i}{\sqrt{\sum_ia_i^2}\sqrt{\sum_ib_i^2}}=\frac{\vec{a} \cdot \vec{b}}{|\vec{a}||\vec{b}|}$

2.2.2 特征向量的度量——距离

距离（Distance）
两个向量之间的距离 $distance$ ：
衡量两个向量之间有多不像， $distance$ 越小表明两个向量越像，两个向量的最小距离是 $机器学习基础：基于样本的学习——KNN0$ 。

欧几里得距离 （Euclidean Distance）

曼哈顿距离（Manhattan Distance）

2.2.3 特征向量的度量——非数值型距离

Hamming距离

上面说的两个特征向量距离的度量方式必须要求每一个维度的特征都要是数值类型的，那么如果对于下面这种包含 $nomial$ 类型的 $instance$ 之间，如何衡量 $distance$ 。首先应该将所有的 $nomial$ 特征都使用 $one-hot$ 编码的方式进行转换。

$one-hot$ ：
$one-hot$ 就是一种将非数值特征转换成数值特征的方式。而且能够保证特征在转换之后，不同的取值在距离上都是完全一样的。

例如 $color$ 这列特征，在进行 $one-hot$ 编码之后，所有的特征取值都变成了用 $3$ 个位表示的向量；无论是 $red$ 和 $orange$ 还是 $red$ 和 $yellow$ 或是 $orange$ 和 $yellow$ 之间，都只有一个 $bit$ 位的不同，因此他们相互之间都是公平的。

如果不用 $one-hot$ 可能会造成一种不公平的现象。假设还是对 $color$ ，我们让 $red=1$ ， $orange=2$ ， $yellow=3$ ；看起来他们之间还是彼此距离一样，但其实有一个问题，就是对机器来说，很可能认为 $yellow$ 的优先级高于 $red$ 和 $orange$ ，因为 $yellow$ 的数值较大。而使用 $one-hot$ 就可以完美解决这个问题

$one-hot$ 存在的问题：
但是 $one-hot$ 问题就是会造成特别系数的矩阵。对于 $color$ 来说 $3$ 个颜色还好，如果有一个特征有 $100$ 种不同的取值，那么通过 $one-hot$ 编码出的新特征就会是一个长度为 $100$ 的值，里面除了某一个 $bit$ 位上的值 $=1$ 之外，其他 $99$ 个位置都是 $机器学习基础：基于样本的学习——KNN0$ 。这个矩阵就过于稀疏了。

经过 $one-hot$ 编码之后我们就可以衡量两个样本之间的距离了：

从图中可以看出 $Apple$ 样本和 $Orange$ 之间有 $4$ 个 $bit$ 位是不同的，因此他们的距离就是 $4$ ，而 $Apple$ 和 $Banana$ 的距离是 $6$ 。

$Distance(Apple,Orange)=4$

$Distance(Apple,Banana)=6$

3. Instance-Based 分类器

3.1 最近邻分类器（Nearest Neighbor Classifier）

基于的假设：空间中两个样本的距离越相近，那么他们越可能拥有相同的标签。

算法细节：

对于一个样本 $x$ （测试样本，没有 $label$ ），离他最近的一个训练样本（有 $label$ 的样本）是 $y$ ，它所有的邻居样本是 $z\in Y$ ；在所有邻居样本中通过距离/相似度测算得到距离最小或者相似度最大的邻居样本：

$d(x,y)=min(d(x,z)|z \in Y)$

用这个最近邻居样本的 $label$ 作为当 $x$ 的 $label$ 。

通过最近邻算法得到的决策边界是非线性的：

3.2 K最近邻（K-Nearest Neighbor）算法（KNN）

最近邻是通过找最近的一个带标签的训练样本 $y$ ，把 $y$ 的标签当做自己的预测标签，将一个邻居扩展到 $k$ 个邻居，也就是通过 $k$ 个训练样本的标签来决定当前这个预测样本的标签，这样的算法叫 $K$ 最近邻。

如何选择 $K$ ：不同的 $K$ 会导致算法的表现差异很大。

$K$ 值越小，由于对噪声过拟合，分类器性能越低，泛化能力越差。
当 $K$ 很大的时候 $K$ 值越大，分类器性能越趋向于 $0-R$ 的性能；因为 $0-R$ 其实可以看成将所有的样本数 $N$ 一起考虑的 $N$ -最近邻。
一般来说，对训练数据进行试错是得到合适 $K$ 的唯一方法。
我们需要考虑数据点的密度。

打破平局

一定会出现一种情况，假设是 $1$ -最近邻，但在当前需要预测样本 $x$ 的周围恰好有两个标签不同的样本 $d$ ， $h$ 距离 $x$ 完全相同。

打破平局的方式有 $3$ 种：
随机选一个
选哪个具有更高先验概率的样本：例如 $d$ 的类别标签是 $机器学习基础：基于样本的学习——KNN0$ ， $h$ 的类别标签是 $1$ ，而在整体的训练集的样本分布中，标签为 $机器学习基础：基于样本的学习——KNN0$ 的样本占了 $60\%$ ， $1$ 的样本占了 $40\%$ ，这时候以 $机器学习基础：基于样本的学习——KNN0$ 为标签的样本的先验概率就是 $0.6$ 所以这时候 $x$ 的标签为 $机器学习基础：基于样本的学习——KNN0$ 。
将当前的 $K-NN$ 增加到 $(K+1)-NN$ 。