（12）监督学习-分类问题-K近邻

    KNN模型通过测量不同特征之间的距离进行分类。

    如图：

KNN示意图

    其中距离基于闵可夫斯基距离;当p= 1时，曼哈顿距离，p=2时，欧式距离；p=无穷时，切比雪夫距离。

    K 值一般通过交叉验证的方式选择。或者2分法等方式选择。

    具体步骤为：

K值选取

     （1） 为了判断未知实例的类别，以所有已知类别的实例作为参照

     （2） 选择参数K

     （3） 计算未知实例与所有已知实例的距离（这个距离可以是高斯距离，余弦值，曼哈顿距离以及相关度）

     （4） 选择最近K个已知实例，其多数表决实际时经验风险最小化。

     （5） 根据少数服从多数的投票法则(majority-voting)，让未知实例归类为K个最邻近样本中最多数的类别

    其具体应用有：电影分类——（爱情片，动作片，---打斗次数，接吻次数）；约会网站优化；手写字识别。

    优缺点：

        优点：简单，易于理解，容易实现，通过对K的选择可具备丢噪音数据的健壮性

        缺点：（1）需要大量空间储存所有已知实例（2）算法复杂度高（需要比较所有已知实例与要分类的实例）（3）当其样本分布不平衡时，比如其中一类样本过大（实例数量过多）占主导的时候，新的未知实例容易被归类为这个主导样本，因为这类样本实例的数量过大，但这个新的未知实例实际并木接近目标样本（4）无法给出特征的结构信息，即按什么特征进行分类的。

    改进

           （1）考虑距离加上权重

            （2）需要做数值的归一化，将数据归一化到0-1之间，(num-min)/(max-min),一来可以统一量纲，使得不会因为部分特征决定结果。再者可以加快运算。

            （3）通过KD 树简化搜索。KD树是一棵二叉树，表示对K维空间的划分，其搜索时从某一个结点开始回溯其父节点，寻找离它最近的点。其划分时某坐标的中位数（一组数据的中位数）来划分的。寻找超球面与超矩形的范围。