7. (k-nearest neighbor) KNN

1. 简介

KNN算法的原理十分简单，即寻找离该点最近的K个点，则该点的值可以由这k个点决定。KNN既可以做分类，也可以做预测，如果做分类，其决策的边界是非线性的。

2. 功能

KNN可以进行分类和预测，

如果是分类，其结果是categorical的，则可以通过k个点进行投票的方式来进行分类，
如果是回归，其结果是numerical的，则可以通过k个点的值进行求平均，或者是根据距离的大小进行权重分配的操作来求出其具体的值(比如距离越大则权重越小，那么权重可以是距离的倒数)

3. 原理

显然第一步是需要定义距离，关于距离的定义可以是欧式距离，曼哈顿距离，或者是统计距离（也称马氏距离），第二步是根据距离来寻找k个点，最终的结果由这k个点决定。

a. 距离的定义
假设 $p_1 (x_1, x_2, ..., x_d)$ 和 $p_2 (u_1, u_2, ..., u_d)$ , 其中x和u都是预测结果的变量(注意定义距离的时候不会用到y)
欧式距离：普遍适用
$d = \sqrt{(x_1-u_1)^2+(x_2-u_2)^2+...+(x_d-u_d)^2}$
曼哈顿距离：适用于网格的距离定义
$d = |x_1 - u_1| + |x_2 - u_2| + ... + |x_d - u_d|$
马氏距离: 用于消除变量之间的相关性
$\vec{v} = (x_1-u_1,x_2-u_2,...x_d-u_d), \Sigma$ 是两个点之间的协方差矩阵
$d = \sqrt{\vec{v}^T\Sigma\vec{v}}$

b. 变量中的categorical variable
当变量之中出现categorical variable的时候，则需要转换成binary dummy variable

例如：假设A是一个categorical variable, A的值有1，2，3，则我们可以创建3个dummy variable A_1, A_2, A_3来表示A，如果A=1，则A_1=1, A_2=0, A_3=0, 如果A=2，则A_1=0, A_2=1, A_3=0，同理得到A=3，可表示为[0,0,1]，一点需要注意的是，当为A创建dummy variable的时候，尽管创建三个dummy variable和创建两个dummy variable所包含的信息一致，但KNN需要所有的三个variable，这是因为第三个variable虽然是redundant，但是避免了multicolinearity的问题，只用2个dummy variable和用3个dummy variable最终拟合出来的结果是不一致的。

KNN对含有m个种类的categorical variable创建的所有m个dummy variable都要被保留下来以保证结果的准确性

c. k对结果的影响及选取
对于分类问题

如果k很低，只寻找很近的点，那么最可能出现的问题是把随机的噪声也放进了我们的model里，因此会在决策边缘产生更多尖锐的部分(more zig-zag)，提高k值会柔化决策边缘。
如果k很高，则会过滤掉训练集之中的local structure，决策边缘会变得十分平滑(less zig-zag)
显然，如果数据的结构越复杂，我们需要的k值就越小用以提升拟合效果
同时由上述的分析，knn的决策边界可以是非线性的，其拟合的效果十分依赖于数据结构，通常而言，k值一般取值为1-20
那么具体k该怎么选择？我们既希望保留本地的结构特征，也希望避免过拟合，那么折中之后，采用的方式是选取在验证集里面的准确率最大的。然而这会有风险，就是结的产生，比如当k从1一直到14，当k=4的时候验证集准确率是0.9，k=3或者5的时候都只有0.7，当k=7-10的时候又都是0.8，那么该怎么选择？这种情况下可以选k=4，但是k=4依旧是一个不稳定的方案，因此理想情况下需要第三份数据集来检验这个结果。
而对于预测问题，评判的标准则是常规的MSE, RMSE等等

4. 模型的优点和缺点

优点
a. KNN的模型简单，而且假设的参数很少
缺点
a. KNN的训练耗时很长，它并不是在训练训练集上花很多的时间，而是花很多的时间寻找每个数据的邻近点
如果要减少KNN消耗的时间，通常有如下两种方法：
$\space$ i. 采用dimension reduction的方法：PCA, SVD, factor analysis等方式
$\space$ ii. 采用复杂的数据结构，比如搜索树，桶排序等方式
b. curse of dimensionality，当使用KNN的时候，显然距离的计算会受到预测模型的参数的数量的影响，而且这个影响随着predictor的增加是指数性的增长
c. lazy learner，对于每一条新的数据，都要计算它和整个训练集的距离，这对于real-time calculation是致命的

5. python伪代码

预处理

# norm转换数据
scaler = preprocessing.StandardScaler()
scaler.fit(X)
# 分离数据集
trainNorm = df.iloc[trainData.index]
validNorm = df.iloc[validData.index]
# 新数据用scalar转换
scalar.transform(new_data)

若分类，采用NearestNeighbors

from sklearn.neighbors import NearestNeighbors
knn = NearestNeighbors(n_neighbors=3) # k=3
knn.fit(trainNorm.iloc[:, 0:-1]) # exclude y

如果要取得distance和最近的数据，可以用如下代码

distances, indices = knn.kneighbors(normed_new_data)
# indices会返回一个列表的列表，每一个列表对应normed_new_data中的每一个数据，如果只有一条数据，则只取第一个数即可
trainNorm.iloc[indices[0], :]

若预测，采用KNeighborsRegressor，语法和上面的类似，只用把 NearestNeighbors替换成KNeighborsRegressor即可