Merge pull request apachecn#362 from DataMonk2017/master

Update 2.k-近邻算法.md
zhaodongzhi · Apr 19, 2018 · 41a4fd7 · 41a4fd7
2 parents b60f9d9 + 64991a6
commit 41a4fd7
Showing 1 changed file with 128 additions and 13 deletions.
diff --git a/docs/2.k-近邻算法.md b/docs/2.k-近邻算法.md
@@ -436,25 +436,140 @@ def handwritingClassTest():
 
 ## KNN 小结
 
-经过上面的介绍我们可以知道， k 近邻算法有 三个基本的要素：
+KNN 是什么？定义： 监督学习？ 非监督学习？
 
-* k 值的选择
+KNN 是一个简单的无显示学习过程，非泛化学习的监督学习模型。在分类和回归中均有应用。
 
-    * k 值的选择会对 k 近邻算法的结果产生重大的影响。
-    * 如果选择较小的 k 值，就相当于用较小的邻域中的训练实例进行预测，“学习”的近似误差（approximation error）会减小，只有与输入实例较近的（相似的）训练实例才会对预测结果起作用。但缺点是“学习”的估计误差（estimation error）会增大，预测结果会对近邻的实例点非常敏感。如果邻近的实例点恰巧是噪声，预测就会出错。换句话说，k 值的减小就意味着整体模型变得复杂，容易发生过拟合。
-    * 如果选择较大的 k 值，就相当于用较大的邻域中的训练实例进行预测。其优点是可以减少学习的估计误差。但缺点是学习的近似误差会增大。这时与输入实例较远的（不相似的）训练实例也会对预测起作用，使预测发生错误。 k 值的增大就意味着整体的模型变得简单。
-    * 近似误差和估计误差，请看这里：https://www.zhihu.com/question/60793482
-     - 近似误差越小，对本数据集的预测效果就越好，但是不保证其他数据集的预测效果
-     - 估计误差越小，对世界上所有相类似的数据集总体预测效果越好，对本数据集的预测效果不一定越好
+### 基本原理
 
-* 距离度量
+简单来说： 通过距离度量来计算查询点（query point）与每个训练数据点的距离，然后选出与查询点（query point）相近的K个最邻点（K nearest neighbors），使用分类决策来选出对应的标签来作为该查询点的标签。
 
-    * 特征空间中两个实例点的距离是两个实例点相似程度的反映。
-    * k 近邻模型的特征空间一般是 n 维实数向量空间 ![向量空间](../images/2.KNN/knn_3.png) 。使用的距离是欧氏距离，但也可以是其他距离，如更一般的 ![Lp距离](../images/2.KNN/knn_4.png) 距离，或者 Minkowski 距离。
+## KNN 小结
+
+KNN 是什么？定义： 监督学习？ 非监督学习？
+
+KNN 是一个简单的无显示学习过程，非泛化学习的监督学习模型。在分类和回归中均有应用。
+
+### 基本原理
+
+简单来说： 通过距离度量来计算查询点（query point）与每个训练数据点的距离，然后选出与查询点（query point）相近的K个最邻点（K nearest neighbors），使用分类决策来选出对应的标签来作为该查询点的标签。
+
+### KNN 三要素
+
+>K, K的取值
+
+>>>>对查询点标签影响显著（效果拔群）。k值小的时候 近似误差小，估计误差大。 k值大 近似误差大，估计误差小。
+
+>>>>如果选择较小的 k 值，就相当于用较小的邻域中的训练实例进行预测，“学习”的近似误差（approximation error）会减小，只有与输入实例较近的（相似的）训练实例才会对预测结果起作用。但缺点是“学习”的估计误差（estimation error）会增大，预测结果会对近邻的实例点非常敏感。如果邻近的实例点恰巧是噪声，预测就会出错。换句话说，k 值的减小就意味着整体模型变得复杂，容易发生过拟合。
+        
+>>>>如果选择较大的 k 值，就相当于用较大的邻域中的训练实例进行预测。其优点是可以减少学习的估计误差。但缺点是学习的近似误差会增大。这时与输入实例较远的（不相似的）训练实例也会对预测起作用，使预测发生错误。 k 值的增大就意味着整体的模型变得简单。
+        
+>>>>太大太小都不太好，可以用交叉验证（cross validation）来选取适合的k值。
+    
+>>>>近似误差和估计误差，请看这里：https://www.zhihu.com/question/60793482
+        
+>距离度量 Metric/Distance Measure 
+        
+>>>>距离度量 通常为 欧式距离（Euclidean distance），还可以是 Minkowski 距离 或者 曼哈顿距离。也可以是 地理空间中的一些距离公式。（更多细节可以参看 sklearn 中 valid_metric 部分）
+
+>分类决策 （decision rule）
+
+>>>>分类决策 在 分类问题中 通常为通过少数服从多数 来选取票数最多的标签，在回归问题中通常为 K个最邻点的标签的平均值。
+
+### 算法：（sklearn 上有三种）
+
+>Brute Force 暴力计算/线性扫描 
+    
+>KD Tree 使用二叉树根据数据维度来平分参数空间。
+    
+>Ball Tree 使用一系列的超球体来平分训练数据集。
+
+>树结构的算法都有建树和查询两个过程。Brute Force 没有建树的过程。
+
+>算法特点：   
+        
+>>>>优点： High Accuracy， No Assumption on data， not sensitive to outliers
+        
+>>>>缺点：时间和空间复杂度 高
+        
+>>>>适用范围： continuous values and nominal values
+
+>相似同源产物： 
+        
+>>>>radius neighbors 根据制定的半径来找寻邻点
+
+>影响算法因素：
+
+>>>>N 数据集样本数量(number of samples)， D 数据维度 (number of features)
+
+>总消耗：
+
+>>>>Brute Force:  O[DN^2] 
+            
+>>>>此处考虑的是最蠢的方法：把所有训练的点之间的距离都算一遍。当然有更快的实现方式, 比如 O(ND + kN)  和  O(NDK) , 最快的是 O[DN] 。感兴趣的可以阅读这个链接： [k-NN computational complexity](https://stats.stackexchange.com/questions/219655/k-nn-computational-complexity)
+        
+>>>>KD Tree: O[DN log(N)] 
+
+>>>>Ball Tree: O[DN log(N)] 跟 KD Tree 处于相同的数量级，虽然建树时间会比 KD Tree 久一点，但是在高结构的数据，甚至是高纬度的数据中，查询速度有很大的提升。
+
+>查询所需消耗:
+        
+>>>>Brute Force:  O[DN] 
+
+>>>>KD Tree: 当维度比较小的时候， 比如 D<20,  O[Dlog(N)] 。相反，将会趋向于 O[DN] 
+
+>>>>Ball Tree: O[Dlog(N)] 
+
+>>>>当数据集比较小的时候，比如 N<30的时候，Brute Force 更有优势。
+
+>Intrinsic Dimensionality(本征维数) 和 Sparsity（稀疏度）
+        
+>>>>数据的 intrinsic dimensionality 是指数据所在的流形的维数 d < D , 在参数空间可以是线性或非线性的。稀疏度指的是数据填充参数空间的程度(这与“稀疏”矩阵中使用的概念不同, 数据矩阵可能没有零项, 但是从这个意义上来讲,它的结构 仍然是 "稀疏" 的)。
+        
+>>>>Brute Force 的查询时间不受影响。
+        
+>>>>对于 KD Tree 和 Ball Tree的查询时间, 较小本征维数且更稀疏的数据集的查询时间更快。KD Tree 的改善由于通过坐标轴来平分参数空间的自身特性 没有Ball Tree 显著。
+        
+>k的取值 (k 个邻点)
+
+>>>>Brute Force 的查询时间基本不受影响。
+        
+>>>>但是对于 KD Tree 和 Ball Tree , k越大，查询时间越慢。
+
+>>>>k 在N的占比较大的时候，使用 Brute Force 比较好。
+
+>Number of Query Points （查询点数量， 即测试数据的数量）
+        
+>>>>查询点较少的时候用Brute Force。查询点较多的时候可以使用树结构算法。
+
+>关于 sklearn 中模型的一些额外干货：
+
+>>>>如果KD Tree，Ball Tree 和Brute Force 应用场景傻傻分不清楚，可以直接使用 含有algorithm='auto'的模组。 algorithm='auto' 自动为您选择最优算法。
+>>>>有 regressor 和 classifier 可以来选择。
+        
+>>>>metric/distance measure 可以选择。 另外距离 可以通过weight 来加权。
+
+>leaf size 对KD Tree 和 Ball Tree 的影响
+            
+>>>>建树时间：leaf size 比较大的时候，建树时间也就快点。
+            
+>>>>查询时间： leaf size 太大太小都不太好。如果leaf size 趋向于 N（训练数据的样本数量），算法其实就是 brute force了。如果leaf size 太小了，趋向于1，那查询的时候 遍历树的时间就会大大增加。leaf size 建议的数值是 30，也就是默认值。
+            
+>>>>内存： leaf size 变大，存树结构的内存变小。
+    
+>Nearest Centroid Classifier
+        
+>>>>分类决策是哪个标签的质心与测试点最近，就选哪个标签。
+        
+>>>>该模型假设在所有维度中方差相同。 是一个很好的base line。
+
+>进阶版： Nearest Shrunken Centroid 
+        
+>>>>可以通过shrink_threshold来设置。
+        
+>>>>作用： 可以移除某些影响分类的特征，例如移除噪音特征的影响
 
-* 分类决策规则
 
-    * k 近邻算法中的分类决策规则往往是多数表决，即由输入实例的 k 个邻近的训练实例中的多数类决定输入实例的类。
 
 * * *