KNN算法：寻找邻居

如何找朋友

KNN是昨天才初次接触到的算法，属于最基本的无监督分类方法。个人认为它的核心概念最能体现为基于邻居的距离计算进行分类：首先通过对数据样本计算距离确定邻居集合，在此基础上根据邻居所属类别进行投票统计以确定待测样本所属类别

想象训练集的数据构建了一个庞大的社会生态，在这个生态系统中包含了众多基于"人以类聚"原则形成的社群（人类本能的自我复制机制）。假使有一个新角色（测试数据角色）决定加入这个群体中来实现快速融入目标社群的目标，则他的第一步行动必然是选择最适合融入的那个子社群。最简单的方法是：首先让新角色与整个群体中的每个人逐一交流并建立联系（计算欧氏距离或其他形式的距离指标），从而筛选出与其兴趣高度契合的前K个好友关系网络。其次通过分析这K个好友分别属于哪些社群分布情况，并统计各社群所包含的好友数量（采用多数决投票机制），最终确定目标定居地为好友数量最多的那个社群区域。当然如果这位新角色不具备多数决思维模式或者有更为理性的决策标准可以选择，则可以选择其他更适合的方式继续执行目标策略。此外如果这位新角色不愿意采取逐一交流的方式扩大社交圈层，则可以通过对整个群体进行结构化分区并建立KD树来进行高效的邻居搜索操作：例如已知这位新角色偏好海边生活方式则无需与蒙古族等非海边居住者的对话空间即可完成特征匹配任务；这种情况下的时间复杂度仅为O(log N)运算级别