机器学习---KNN理论部分
目录
3、 计算两个物体之间的距离/相似度（如上面使用欧式公式距离）
1、KNN算法描述
1、k近邻法（k-nearest neighbor, kNN），具体实现是计算某个点（元素）最近相邻的k个点，然后找出这个k个点中点（元素）个数最多的类别，把这个类别作为当前点（元素）的类别。
2、应用：
应用在分类和回归（主要应用是分类）
3、要关注的几个要素：
1）如何计算当前点（元素）和别的点（元素）的距离。
距离度量，有
a.曼哈顿距离、欧氏距离。
如图，p = 1的时候相当于
如图，p=2的时候就是欧式距离，相当于
b.两个物品的相似度（通过向量计算相似度等）
2）k值的选择
k值的选择会对k近邻法的结果产生重大影响。在应用中，k值一般取一个比较小的数值，通常采用交叉验证法来选取最优的k值。
3）分类决策规则
k近邻法中的分类决策规则往往是多数表决，即由输入实例的k个邻近的训练实例中的多数类，决定输入实例的类。
4、使用knn算法时流程
1. 把一个物体表示成向量
2. 标记号每个物体的标签（i.e., offer/no offer）
3. 计算两个物体之间的距离/相似度
4. 选择合适的K
1、一个物体表示成向量量
这也叫做“特征工程”英文叫Feature Engineering，模型的输入一定是数量化的信息，我们需要把现实生活中的物体表示成向量/矩阵/张量形式。
2. 标记号每个物体的标签
如水果的分类
3、 计算两个物体之间的距离/相似度（如上面使用欧式公式距离）
4、选择合适的K
为了选择合理的K, 首先需要去理解K对算法的影响
为了理解K对算法的影响，需要先理解什么叫算法的决策边界
决策边界：
例1：大学里60分以上作为及格，60分以下作为不及格
例2：今年某高校要计划引入35岁以下，具有海外研究经验3年年以上的学者。
决策边界决定“线性分类器”或者“非线性分类器”
a、KNN的决策边界：怎么寻找（i.e., K=1）？
答案是：交叉验证（Cross Validation），也就是我们平时说的“调参”
b、交叉验证
交叉验证即，把训练数据进一步分成训练数据（Training Data）和验证集(Validation Data)。选择在验证数据里最好的超参数组合。（这里说的超参数是指模型之外的参数，不是模型训练出来的参数，比如这里说的k，并不是模型训练出来的参数，而是我们人为改变k值）
c、交叉验证中需要注意的点
1. 千万不能用测试数据来调参
2. 千万不能用测试数据来调参
3. 千万不能用测试数据来调参
4. 数据量越少，可以适当增加折数
5、特征的缩放
1. 线性归一化（Min-max Normalization）
2. 标准差标准化（Z-score Normalization）
5、KNN 的延伸内容(1)
1、如何处理大数据量
1、预测阶段：需要计算被预测样本和每一个训练样本之间的距离
2、时间复杂度： O(N) ， N是样本总数
3、当N很大的时候，这个复杂度显然不能作为实时预测
解决：
1、近似算法：不再寻求完全准确的解，可以适当损失精确率，利用类似哈希算法– Locality Sensitivity Hashing (LSH)。取部分数据
核心思想：把样本分在不同的bucket, 使得距离比较近的样本较大概率在同一个bucket里LSH 函数h对于给定的相似度量函数d, 满足：
d(x1, x2) <=r 时p(h(x1)==h(x2))的概率高
d(x1,x2)>????????时, p(h(x1)==h(x2))的概率低
2、KD-tree，对于样本个数N来说O(logN)，对于数据维度d来说，指数级复杂度。
2 、如何处理理特征之间的相关性
使用马氏距离，马氏距离(Mahalanobis distance)是由印度统计学家马哈拉诺比斯(P. C. Mahalanobis)提出的，表示点与一个分布之间的距离。它是一种有效的计算两个未知样本集的相似度的方法。与欧氏距离不同的是，它考虑到各种特性之间的联系（例如：一条关于身高的信息会带来一条关于体重的信息，因为两者是有关联的），并且是尺度无关的(scale-invariant)，即独立于测量尺度。对于一个均值为μ，协方差矩阵为Σ的多变量向量，其马氏距离为sqrt( (x-μ)'Σ^(-1)(x-μ) )。
3、怎么处理理样本的重要性
加权重
4、能不能利用Kernel Trick
https://blog.****.net/krais_wk/article/details/80992153
6、总结
1. KNN是一个非常简单的算法
2. 比较适合应用在低维空间
3. 预测时候的复杂度高，对于大数据需要一定的处理