六、KNN(K Nearest Neighbor) K近邻（有监督）
KNN算法，即K近邻算法是一种监督学习算法，本质上是要在给定的训练样本中找到与某一个测试样本A最近的K个实例，然后统计k个实例中所属类别计数最多的那个类，就是A的类别。
KNN算法的思想：对于任意n维输入向量，分别对应于特征空间中的一个点，输出为该特征向量所对应的类别标签或预测值。
工作原理是利用训练数据对特征向量空间进行划分，并将划分结果作为最终算法模型。存在一个样本数据集合，也称作训练样本集，并且样本集中的每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。
输入没有标签的数据后，将这个没有标签的数据的每个特征与样本集中的数据对应的特征进行比较，然后提取样本中特征最相近的数据（最近邻）的分类标签。
一般而言，我们只选择样本数据集中前k个最相似的数据，这就是KNN算法中K的由来，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的类别，作为新数据的分类。
KNN分类算法
1.K的选择：
K值是KNN算法中为数不多的超参数之一，K值的选择也直接影响着模型的性能。
如果我们把k值设置的比较小，那么意味着我们期望个到一个更复杂和更精确的模型，同时更加容易过拟合；
相反，如果K值越大，模型机会越简单，一个很极端的例子就是如果将K值设置的与训练样本数量相等，即K=N，那么无论是什么类别的测试样本最后的测试结果都会是测试样本中数量最多的那个类。
2.距离的度量：
距离的度量描述了测试样本与训练样本的临近程度，这个临近程度就是K个样本选择的依据，在KNN算法中，如果特征是连续的，那么距离函数一般用曼哈顿距离（L1距离）或欧氏距离（L2距离），如果特征是离散的，一般选用汉明距离。
曼哈顿距离在KNN中其实就是样本特征每一个维度上的差值的和：
欧氏距离在KNN中其实就是样本特征每一个维度上的差值的平方和开根号：
汉明距离：
3.分类决策规则：
通过上面提到的K与距离两个概念，我们就能选择出K个与测试样例最近的训练样本，如何根据这K个样本决定测试样例的类别就是KNN的分类决策规则，在KNN中最常用的就是多数表决规则。但是该规则严重依赖于训练样本的数目。
为了快速查找到k个近邻，我们可以考虑使用特殊的数据结构存储训练数据，用来减少搜索次数。其中，KDTree就是最著名的一种。
KDTree（K-dimension Tree）是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。KDTree是一种二叉树，表示对k维空间的一种划分构造KDTree相当于不断地利用垂直于坐标轴的超平面将k维空间进行切分，构成一系列的k维超矩形区域。KDTree的每个节点对应于一个k维超矩形区域。利用KDTree可以省去对大部分数据点的搜索，从而减少搜索的计算量。
网友评论