KNN（上）：如何根据打斗和接吻次数来划分电影类型？

想对电影的类型进行分类，统计了电影中打斗次数、接吻次数，还有其他的指标可以被统计到

希望当有一部新电影的时候自动分类它的类型，把打斗次数看成X轴，接吻次数看成Y轴，然后在二维的的坐标轴上，对这几部电影进行标记，对于未知电影A，坐标为(x,y)，需要看下离电影A最近的都有哪些电影，大多属于哪个分类，那么电影A就属于哪个分类，实际，还需要确定一个K值，就是我们要观察离电影A最近的电影有多少个

KNN工作原理

简单说就是“近朱者赤近墨者黑”，分三步计算：

1. 计算待分类物体与其他物体之间的距离
2. 统计距离最近的K个邻居
3. 对于K个最近的邻居，属于哪个分类最多，待分类物体就属于哪一类

K值如何选择

如果K值过小，相当于未分类物体与它邻居非常接近才行，但是如果邻居点是个噪声点，那么未分类物体的分类会产生误差，这样KNN分类会产生过拟合

如果K值过大，相当于距离过远的点会对未知物体的分类产生影响，虽然鲁棒性强，但是会产生欠拟合的情况

采用交叉验证的方式选择K值：把样本集中的大部分样本作为训练集，小部分用于预测，把K值选取在一个较小的范围内同时在验证集上准确率最高的那个最终确定为K值

距离如何计算

两个样本点之间的距离代表了两个样本之间的相似度，距离越大差异性越大。距离的计算方式：

1. 欧式距离
2. 曼哈顿距离
3. 闵可夫斯基距离
4. 切比雪夫距离
5. 余弦距离

• 欧式距离，最常用的公式，在二维空间中，两点的欧式距离是$d=\sqrt{(x_1-y_1)^2+(x_2-y_2)^2}$d=(x1​−y1​)2+(x2​−y2​)2​，同理还可以得到两点在n维空间中的距离：

• 曼哈顿距离在几何空间中用的较多，绿色的直线代表两点之间的欧式距离，红色黄色为两点的曼哈顿距离，曼哈顿距离等于两个点在坐标系上绝对轴距总和$d=|x_1-y_1|+|x_2-y_2|$d=∣x1​−y1​∣+∣x2​−y2​∣

• 闵可夫斯基距离是一组距离的定义，对于n维空间中的两个点x(x1,x2…,xn)和y(y1,y2…,yn)，x和y两个点之间的闵可夫斯基距离为：

p代表空间的维数，当p=1的时候就是曼哈顿距离，p=2就是欧式距离；p->∞就是切比雪夫距离

• 切比雪夫距离，两个点之间的切比雪夫距离就是两个点坐标数值差的绝对值的最大值，即max(|x1-y1|,|x2-y2|)

• 余弦距离是两个向量的夹角，在方向上计算两者之间的差异，可以衡量用户对内容兴趣的区分度，比如用搜索引擎搜索某个关键词，还会给你推荐其他相关搜索，这些推荐的关键词就是采用余弦距离计算得出

KD树

KNN就是求大量计算样本点之间的距离，为了减少计算距离次数，提升效率，提出KD树，KD树就是对数据点在K维空间中划分的一种数据结构，在KD树的构造中，每个节点都是K维数值点的二叉树，可以采用二叉树的增删改查操作

KD树是一个二叉树，在sklearn中可以直接调用KD树

用KNN做回归

KNN可以做分类，做回归。回归的意思，想要对未知电影进行类型划分是一个分类问题，先看一下要分类的未知电影离他最近的K部电影大多属于哪个分类这部电影属于哪个分类，一部新电影，已知是爱情片，想要知道它的打斗次数、接吻次数可能是多少，这就是一个回归问题。

对于一个新电影X，要预测它的某个属性值，比如打斗次数，具体特征属性和数值如下，先计算待测点（电影X）到已知点的距离，选择距离最近的K个点，假设K=3，此时最近的3个点分别是《战狼》《红海行动》《碟中谍6》，此时它的打斗次数就是这3个点的该属性值的平均值，即(100+95+105)/3=100

回归一般是预测某个属性值，这个属性值是连续型的，而不是离散型的。如果是离散型的就变成了分类问题。比如对于这个待测点的已知属性值，我们先计算这个待测点与已知点的距离，然后选择最近的K个点。这样也就是知道了这个待测点和哪K个已知点最接近。那么这个待测点的未知属性值就等于这K个点的该属性值的平均值

推荐kaggle项目

信用卡欺诈交易分类预测 https://www.kaggle.com/mlg-ulb/creditcardfraud
比特币趋势分析
https://www.kaggle.com/mczielinski/bitcoin-historical-data
宇宙中的脉冲星预测 https://www.kaggle.com/pavanraj159/predicting-a-pulsar-star
西班牙高铁票价 https://www.kaggle.com/thegurus/spanish-high-speed-rail-system-ticket-pricing

.kaggle.com/thegurus/spanish-high-speed-rail-system-ticket-pricing