㈠ 8_分类算法-k近邻算法（KNN）
KNN算法是基于距离的分类和回归方法，通过寻找与待预测样本距离最近的K个训练样本，来进行预测。它主要由以下步骤组成：
1. 从训练集合中获取K个离待预测样本距离最近的样本数据；
2. 根据获取得到的K个样本数据来预测当前待预测样本的目标属性值。
在KNN算法中，三个重要因素如下：
1. K的大小：K值选择影响预测结果的准确性。较小的K值可能导致过拟合，较大的K值可能导致过简化。
2. 距离度量：常用的有欧几里得距离、曼哈顿距离等。选择适当的度量方式对预测结果影响较大。
3. 训练数据的质量：数据的完整性和代表性直接影响KNN算法的性能。
在分类预测中，KNN算法通常采用多数表决法或加权多数表决法；在回归预测中，则采用平均值法或加权平均值法。
KNN算法实现的关键在于高效地找出K个最邻近的点，常用方法有邻近搜索算法、KD-Tree、Ball Tree、BBF Tree、MVP Tree等。
KNN算法的优点在于简单、易于理解和实现，无需估计参数或训练过程。然而，其缺点在于计算复杂度高，尤其是在大数据集上。KNN算法适用场景为小数据场景，一般几千至几万样本较为合适。
KD树是一种用于在高维空间中进行数据索引的数据结构。构建KD树的过程如下：
1. 从m个样本的n维特征中，选择方差最大的第k维特征nk作为根节点。对于该特征，选择取值的中位数nkv作为样本的划分点，将样本分为两部分，分别属于左子树和右子树。
2. 对于每个子树，重复上述过程，直到所有样本被正确分类。
KD树可以有效降低KNN算法的计算复杂度，提高查找最近邻的效率。在使用KNN算法时，通常需要合理设置K值、选择合适的距离度量方式，并结合KD树等优化策略，以达到最佳预测效果。