尧图网站建设 
k-NN 算法讲解一、算法在做什么k-NNk-近邻大概是最不像「机器学习」的机器学习算法没有训练阶段模型就是训练集本身。所谓学习只是把带标签的样本存起来预测时拿新样本和训练集挨个算距离让最近的 k 个邻居投票。物以类聚——离得近的样本大概率高是一类这就是全部依据。不对数据分布做任何假设决策边界可以任意复杂。名字上的坑k-NN 是监督算法别和 k-means无监督聚类搞混两者只是名字像。二、预测一个样本的过程输入待预测样本 x全部训练数据带标签 │ ▼ 1. 计算 x 与训练集中每一个样本的距离通常欧氏距离 │ ▼ 2. 取距离最小的 k 个作为邻居 │ ▼ 3. 统计这 k 个邻居的类别标签 │ ▼ 输出票数最多的类别写的时候注意一个坑第 2 步不需要完整排序维护一个大小为 k 的最大堆扫一遍就够。样本量大时全排序 O(N log N) 和堆选择 O(N log k) 差距不小。回归任务把第 3 步改成取 k 个邻居输出的加权平均其余完全一样。西瓜示例k 3待测西瓜 x 训练集 [西瓜A: 甜度0.8, 重量5kg, 好] [西瓜B: 甜度0.3, 重量3kg, 坏] [西瓜C: 甜度0.9, 重量6kg, 好] [西瓜D: 甜度0.2, 重量2kg, 坏] ... 计算 x 到所有样本的距离 → 最近 3 个邻居2 好 / 1 坏 → 投票 → 预测为好三、要定的三件事k、距离、权重3.1 k 取多大k 太小如 k1决策边界贴着每个训练样本走一个噪声点就能改变边界 → 过拟合k 太大投票越来越「和稀泥」边界被抹平类别交界处糊掉 → 欠拟合极端情况 kN 时永远预测多数类经验法则是 k ≈ √NN 为样本数更可靠的做法是交叉验证扫一遍 k取验证误差最小的。二分类时 k 取奇数避免平票。3.2 距离度量连续数值特征默认欧氏距离d(x, y) √((x₁ - y₁)² (x₂ - y₂)² ... (xₙ - yₙ)²)曼哈顿距离逐维取绝对差再求和d(x, y) |x₁ - y₁| |x₂ - y₂| ... |xₙ - yₙ|两者怎么选没有定论维度上去到几百之后欧氏距离会先失去区分度有实验报告说曼哈顿距离在高维下更稳一点。其他度量按场景挑余弦相似度只看方向不看模长适合文本、稀疏特征马氏距离考虑特征间的相关性和各自尺度代价是要算协方差矩阵的逆3.3 投票权重默认等权k 个邻居一人一票。可以改成按距离加权常用权重是距离的倒数w_i 1 / d_i d_i → 0 时用一个很小的 ε 兜底避免除零近处邻居话语权大远处邻居基本陪跑。k 取得比较大时这个改法收益明显——等权投票会让远处的「外人」稀释近处的意见。sklearn 里对应weightsdistance。四、优点与代价优点缺点原理简单直观无需训练预测慢每个待测样本都要算一遍全训练集的距离非参数化决策边界任意复杂对异常值敏感天然支持多分类依赖特征缩放否则数值大的特征主导距离加新样本不用重新训练存进去就行维度灾难高维下「最近」失去区分度「无需训练」的另一面是预测慢——计算量从训练期挪到了预测期所以 k-NN 也叫惰性学习lazy learning。样本量大了就得靠 kd-tree 这类索引结构提速见第七节。特征缩放为什么必须做某人体检数据 身高(cm)160, 175, 180 ← 范围 ~20 月薪(元)5000, 30000, 15000 ← 范围 ~25000 不做缩放 → 月薪差异完全主导距离身高几乎不起作用解法是标准预处理标准化z-score减均值除标准差或归一化Min-Max 拉到 [0,1]。注意缩放参数要从训练数据上算再把同一套变换套到待测数据上。五、用在图像分割上5.1 逐像素 k-NN能跑但别用对每个像素的[R, G, B]与所有标记样本算距离 → 投票 → 得到该像素的标签。缺点 - 1 张 1080p 图约 200 万像素每个都独立算一遍距离计算量巨大 - 像素之间互不通气完全不考虑空间信息 → 结果满屏胡椒盐噪声 - 光源一变 RGB 整体偏移效果不稳定5.2 超像素 k-NN推荐先用 SLIC 把图像聚成几百个超像素再以超像素为单位做 k-NN。SLIC 本身见 SLIC_超像素算法原图 (1920×1080, 约200万像素) ↓ SLIC (K200) 超像素标签图 200 个区域 ↓ 对每个超像素提取特征向量平均R, G, B, 纹理等 ↓ 手工标记少量超像素作训练样本如 20 个前景 20 个背景 ↓ k-NN 分类每个未标记超像素找最近的 k 个邻居投票 ↓ 分类结果映射回原图所有像素同一超像素内共享标签k-NN 没有训练阶段那批带标签的超像素本身就是模型所以标记量可以很少但每个类别要覆盖几种典型外观。收益对比方式分类器处理量噪声逐像素200 万样本多超像素200 样本少区域内颜色已平均过一遍5.3 特征向量怎么设计应用场景特征向量备注全图分类物体位置可能变[R_avg, G_avg, B_avg, 纹理...]不加坐标避免位置干扰局部精细分割物体位置固定[R_avg, G_avg, B_avg, x, y, 面积]坐标约束空间邻近性带坐标的版本有个前提物体位置固定。位置会变的场景绝对坐标特征在新图上直接失效——SLIC 笔记的「三个常见误区」里讲的同一件事。六、完整流程示例PCB 缺陷检测# 伪代码fromsklearn.neighborsimportKNeighborsClassifier# 1. 超像素预处理labelsslic(image,n_segments200)# 2. 提取特征featuresextract_features(image,labels)# 每个超像素一行# 3. 手工标注少量样本train_idx[0,3,5,...]# 标记为缺陷的超像素train_labels[1,1,0,...]# 1缺陷, 0正常# 4. k-NN 预测惰性学习fit 只是存数据knnKNeighborsClassifier(n_neighbors5,weightsdistance)knn.fit(features[train_idx],train_labels)predknn.predict(features)# 5. 映射回像素resultpred[labels]# 每个像素获得所属超像素的标签最后一行pred[labels]是 numpy 花式索引labels 是与原图同尺寸的超像素编号矩阵拿它当下标去 pred 里取值直接得到逐像素标签图。七、不够用的地方和补救预测慢kd-tree、Ball-tree 把最近邻搜索从暴力 O(N) 降到平均 O(log N)。坑在于 kd-tree 只在低维经验上 20 维左右以内有效维度再高就退化回暴力搜——sklearn 的algorithmauto会自己挑高维数据先降维PCA、t-SNE再 k-NN顺便缓解维度灾难类别不平衡大类样本多票就多小类容易被淹没。按类别反比加权投票或对训练集欠采样工业场景光源相机固定时差影法与模板图做差比 k-NN 更稳定也更高效先想它 kNN_算法讲解
k-NN 算法讲解一、算法在做什么k-NNk-近邻大概是最不像「机器学习」的机器学习算法没有训练阶段模型就是训练集本身。所谓学习只是把带标签的样本存起来预测时拿新样本和训练集挨个算距离让最近的 k 个邻居投票。物以类聚——离得近的样本大概率高是一类这就是全部依据。不对数据分布做任何假设决策边界可以任意复杂。名字上的坑k-NN 是监督算法别和 k-means无监督聚类搞混两者只是名字像。二、预测一个样本的过程输入待预测样本 x全部训练数据带标签 │ ▼ 1. 计算 x 与训练集中每一个样本的距离通常欧氏距离 │ ▼ 2. 取距离最小的 k 个作为邻居 │ ▼ 3. 统计这 k 个邻居的类别标签 │ ▼ 输出票数最多的类别写的时候注意一个坑第 2 步不需要完整排序维护一个大小为 k 的最大堆扫一遍就够。样本量大时全排序 O(N log N) 和堆选择 O(N log k) 差距不小。回归任务把第 3 步改成取 k 个邻居输出的加权平均其余完全一样。西瓜示例k 3待测西瓜 x 训练集 [西瓜A: 甜度0.8, 重量5kg, 好] [西瓜B: 甜度0.3, 重量3kg, 坏] [西瓜C: 甜度0.9, 重量6kg, 好] [西瓜D: 甜度0.2, 重量2kg, 坏] ... 计算 x 到所有样本的距离 → 最近 3 个邻居2 好 / 1 坏 → 投票 → 预测为好三、要定的三件事k、距离、权重3.1 k 取多大k 太小如 k1决策边界贴着每个训练样本走一个噪声点就能改变边界 → 过拟合k 太大投票越来越「和稀泥」边界被抹平类别交界处糊掉 → 欠拟合极端情况 kN 时永远预测多数类经验法则是 k ≈ √NN 为样本数更可靠的做法是交叉验证扫一遍 k取验证误差最小的。二分类时 k 取奇数避免平票。3.2 距离度量连续数值特征默认欧氏距离d(x, y) √((x₁ - y₁)² (x₂ - y₂)² ... (xₙ - yₙ)²)曼哈顿距离逐维取绝对差再求和d(x, y) |x₁ - y₁| |x₂ - y₂| ... |xₙ - yₙ|两者怎么选没有定论维度上去到几百之后欧氏距离会先失去区分度有实验报告说曼哈顿距离在高维下更稳一点。其他度量按场景挑余弦相似度只看方向不看模长适合文本、稀疏特征马氏距离考虑特征间的相关性和各自尺度代价是要算协方差矩阵的逆3.3 投票权重默认等权k 个邻居一人一票。可以改成按距离加权常用权重是距离的倒数w_i 1 / d_i d_i → 0 时用一个很小的 ε 兜底避免除零近处邻居话语权大远处邻居基本陪跑。k 取得比较大时这个改法收益明显——等权投票会让远处的「外人」稀释近处的意见。sklearn 里对应weightsdistance。四、优点与代价优点缺点原理简单直观无需训练预测慢每个待测样本都要算一遍全训练集的距离非参数化决策边界任意复杂对异常值敏感天然支持多分类依赖特征缩放否则数值大的特征主导距离加新样本不用重新训练存进去就行维度灾难高维下「最近」失去区分度「无需训练」的另一面是预测慢——计算量从训练期挪到了预测期所以 k-NN 也叫惰性学习lazy learning。样本量大了就得靠 kd-tree 这类索引结构提速见第七节。特征缩放为什么必须做某人体检数据 身高(cm)160, 175, 180 ← 范围 ~20 月薪(元)5000, 30000, 15000 ← 范围 ~25000 不做缩放 → 月薪差异完全主导距离身高几乎不起作用解法是标准预处理标准化z-score减均值除标准差或归一化Min-Max 拉到 [0,1]。注意缩放参数要从训练数据上算再把同一套变换套到待测数据上。五、用在图像分割上5.1 逐像素 k-NN能跑但别用对每个像素的[R, G, B]与所有标记样本算距离 → 投票 → 得到该像素的标签。缺点 - 1 张 1080p 图约 200 万像素每个都独立算一遍距离计算量巨大 - 像素之间互不通气完全不考虑空间信息 → 结果满屏胡椒盐噪声 - 光源一变 RGB 整体偏移效果不稳定5.2 超像素 k-NN推荐先用 SLIC 把图像聚成几百个超像素再以超像素为单位做 k-NN。SLIC 本身见 SLIC_超像素算法原图 (1920×1080, 约200万像素) ↓ SLIC (K200) 超像素标签图 200 个区域 ↓ 对每个超像素提取特征向量平均R, G, B, 纹理等 ↓ 手工标记少量超像素作训练样本如 20 个前景 20 个背景 ↓ k-NN 分类每个未标记超像素找最近的 k 个邻居投票 ↓ 分类结果映射回原图所有像素同一超像素内共享标签k-NN 没有训练阶段那批带标签的超像素本身就是模型所以标记量可以很少但每个类别要覆盖几种典型外观。收益对比方式分类器处理量噪声逐像素200 万样本多超像素200 样本少区域内颜色已平均过一遍5.3 特征向量怎么设计应用场景特征向量备注全图分类物体位置可能变[R_avg, G_avg, B_avg, 纹理...]不加坐标避免位置干扰局部精细分割物体位置固定[R_avg, G_avg, B_avg, x, y, 面积]坐标约束空间邻近性带坐标的版本有个前提物体位置固定。位置会变的场景绝对坐标特征在新图上直接失效——SLIC 笔记的「三个常见误区」里讲的同一件事。六、完整流程示例PCB 缺陷检测# 伪代码fromsklearn.neighborsimportKNeighborsClassifier# 1. 超像素预处理labelsslic(image,n_segments200)# 2. 提取特征featuresextract_features(image,labels)# 每个超像素一行# 3. 手工标注少量样本train_idx[0,3,5,...]# 标记为缺陷的超像素train_labels[1,1,0,...]# 1缺陷, 0正常# 4. k-NN 预测惰性学习fit 只是存数据knnKNeighborsClassifier(n_neighbors5,weightsdistance)knn.fit(features[train_idx],train_labels)predknn.predict(features)# 5. 映射回像素resultpred[labels]# 每个像素获得所属超像素的标签最后一行pred[labels]是 numpy 花式索引labels 是与原图同尺寸的超像素编号矩阵拿它当下标去 pred 里取值直接得到逐像素标签图。七、不够用的地方和补救预测慢kd-tree、Ball-tree 把最近邻搜索从暴力 O(N) 降到平均 O(log N)。坑在于 kd-tree 只在低维经验上 20 维左右以内有效维度再高就退化回暴力搜——sklearn 的algorithmauto会自己挑高维数据先降维PCA、t-SNE再 k-NN顺便缓解维度灾难类别不平衡大类样本多票就多小类容易被淹没。按类别反比加权投票或对训练集欠采样工业场景光源相机固定时差影法与模板图做差比 k-NN 更稳定也更高效先想它