KNN(K近邻)

KNN（K近邻）通过相似度度量待预测样本。与已知样本的相似度，选取相似度最高的k个样本作为K个最近邻。KNN的优缺点，KNN的分类。

KNN(K近邻)

• 简介
  • 思想：通过相似度度量待预测样本与已知样本的相似度，选取相似度最高的K个样本作为K个最近邻，根据K个最近邻的标签对带待预测样本的标签做预测
• KNN需要考虑的几个问题
  • 相似度如何度量？
    • 距离
      • 欧式距离(最常用)
      • 马氏距离
      • 曼哈顿距离
      • 汉明距离
      • 切比雪夫距离
      • 闵可夫斯基距离
    • 皮尔逊相似度(约束条件较多)
    • 斯皮尔曼相似度(约束条件较少)
    • 余弦相似度(文档数据)
    • 杰卡德相似度(标称属性)
  • 参数K如何确定？
    • 经验法则
    • 网格搜索
• KNN的优缺点
  • 优点
    • 适用于非线性分类
    • 针对类域的交叉或重叠较多的训练样本集来说，KNN更准确度高
    • KNN对异常点不敏感
  • 缺点
    • 可解释性较差
    • 当特征维度较高时，计算量过大（最严重！最常见！）
    • 由于是惰性学习，因此预测速度相比逻辑回归等其他算法较缓慢
    • 样本不平衡严重影响准确度
• KNN的优化
  • 方法一：更换数据集的数据结构
    • KD-tree：通过KD-tree存储训练数据，减少不必要的搜索空间，进而加快搜索速度。
      • KD树的建立
        • 举个例子：数据集有两个特征，共包含6个训练样本
        • 数据集如下：{A(2，3)、D（4,7）、B（5,4）、F（7,2）、E（8,1）、C（9,6）}
        • 数据集可视化：
        • 步骤一：首先沿 x 坐标进行切分，我们选出 x 坐标的中位点F为根节点
        • 步骤一可视化：
        • 步骤二：沿 y坐标进行切分，选出y坐标的中位点B与C为左右节点
        • 步骤二可视化：
        • 步骤三：重复步骤二，先对x轴划分，再对y轴划分
        • 步骤三可视化：
        • 结果可视化：
      • KD树的搜索
        • 假设待测样本X为(8.5,1)，则搜索过程如下
        • 步骤一：从根节点出发，不断判断待测样本的特征值，进而让待测样本向下移动，直至寻找到最近邻点(叶子节点)
        • 步骤一可视化：
        • 步骤二：从最近邻点回退，并依次计算X与回退节点的距离，若小于X与最近邻点的距离，那么更新最近邻点，直至回退到根节点
        • 步骤二可视化：
      • KD树的预测
        • 根据最近邻K的数值，针对同一待测样本X进行K次搜索，并标记每一次搜索到的最近邻节点为已选（保证每次获取的最近邻节点不相同）
        • 分类问题：计算K个最近邻节点的标签的众数
        • 回归问题：计算K个最近邻节点的标签的均值
    • 球-tree
  • 方法二：选择合适的相似度度量方式
• KNN分类
  • 计算K个最近邻节点的标签的众数
  • 损失函数：误分类率(因为无法优化参数，所以没啥用)
• KNN回归
  • 计算K个最近邻节点的标签的均值
  • 损失函数：MSE(因为无法优化参数，所以也没啥用)