【k近邻】 K-Nearest Neighbors算法距离度量选择与数据维度归一化

Ne0inhk

— 4 min read
【k近邻】 K-Nearest Neighbors算法距离度量选择与数据维度归一化
【k近邻】 K-Nearest Neighbors算法原理及流程

【k近邻】 K-Nearest Neighbors算法距离度量选择与数据维度归一化

【k近邻】 K-Nearest Neighbors算法k值的选择

【k近邻】 Kd树的构造与最近邻搜索算法

【k近邻】 Kd树构造与最近邻搜索示例
k近邻算法（K-Nearest Neighbors，简称KNN）是一种常用的监督学习算法，可以用于分类和回归问题。在OpenCV中，KNN算法的函数为`cv.ml.KNearest_create()。 

距离度量的选择

k近邻算法中需要按照距离递增次序排序，通常选取以下类型的距离：

x_{i}=\left(x_{i}^{(1)},x_{i}^{(2)},\cdots,x_{i}^{(n)}\right)^{\mathrm{T}}

L

\infty

距离：

L_{\infty}(x_{i},x_{j})=\max_{l}\mid x_{i}^{(l)}-x_{j}^{(l)}\mid

曼哈顿距离：

L_{1}(x_{i},x_{j})=\sum_{l=1}^{n}|x_{i}^{(l)}-x_{j}^{(l)}|

Lp距离：

L_{p}(x_{i},x_{j})=\left(\sum_{l=1}^{n}\mid x_{i}^{(l)}-x_{j}^{(l)}\mid^{p}\right)^{\frac{1}{p}}

欧式距离：

L_{2}(x_{i},x_{j})=\left(\sum_{l=1}^{n}|x_{i}^{(l)}-x_{j}^{(l)}|^{2}\right)^{\frac{1}{2}}

数据维度归一化

假设所使用的样本特征为

\{(x_{i1},x_{i2},\ldots,x_{in})\}_{i=1}^m

，取每一轴上的最大值减最小值

M_j=\max_{i=1,\ldots,m}x_{ij}-\min_{i=1,\ldots,m}x_{ij}

随后在计算距离时将每一个坐标轴除以相应的

M_j

以进行归一化

d((y_1,\ldots,y_n),(z_1,\ldots,z_n))=\sqrt{\sum_{j=1}^n\left(\frac{y_j}{M_j}-\frac{z_j}{M_j}\right)^2}

数据维度归一化的必要性

当使用多维度数据计算距离时，数据维度的归一化是及其必要的。

例如，以身高(cm)与脚码（尺码）大小作为特征值，判断男性或者女性。5个训练样本分布如下：

A [(179,42),男]，B [(178,43),男]，C [(165,36)女]，D [(177,42),男]，E [(160,35),女]

可以发现，第一维身高特征是第二维脚码特征的4倍左右，在计算距离度量的时候，如果不进行数据维度的归一化，算法就会偏向于第一维特征，这会造成俩个特征并不是等价重要的，最终可能会导致距离计算错误，从而导致预测错误。

以测试样本 F[(167,43),男]为例，取k=3，分别算出F离训练样本的欧式距离，然后选取最近的3个，多数类别就是我们最终的结果，计算结果如下：

\begin{gathered} AF=\sqrt{\left(167-179\right)^2+\left(43-42\right)^2}=\sqrt{145} \\ BF=\sqrt{\left(167-178\right)^2+\left(43-43\right)^2}=\sqrt{121} \\ CF=\sqrt{\left(167-165\right)^2+\left(43-36\right)^2}=\sqrt{53} \\ DF=\sqrt{\left(167-177\right)^2+\left(43-42\right)^2}=\sqrt{101} \\ EF=\sqrt{\left(167-160\right)^2+\left(43-35\right)^2}=\sqrt{103} \end{gathered}

可以得到，最近的前三个分别是C,D,E三个样本，那么由C,E为女性，D为男性，得到预测结果为女性。

女性脚43码的可能性远远小于男性脚43码的可能性，算法却错误地预测F为女性，这不是算法的问题，这是各个特征量纲不同的问题，这里量纲直接导致身高的权重远大于脚码的权重，进而导致预测错误。所以在计算前应该让每个特征同等重要，这就是归一化的必要性。

Read more

libmd 实现详解：仓颉语言中的哈希算法库开发实践

libmd 实现详解：仓颉语言中的哈希算法库开发实践

libmd 实现详解：仓颉语言中的哈希算法库开发实践 前言 密码学哈希函数是现代信息安全的基石，广泛应用于数据完整性验证、数字签名、用户认证和数据安全存储等领域。在仓颉语言生态中，libmd库提供了完整的密码哈希算法实现，支持多种主流哈希算法，包括经典的MD2、MD4、MD5，以及SHA系列（SHA-1、SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/256）和RIPEMD-160等算法。同时，该库还提供了HMAC功能，支持消息认证码的生成，为数据提供了额外的安全保障。 本文将从库的设计思路、核心实现、技术挑战、性能优化等多个维度，深入解析libmd库的开发过程，为仓颉语言开发者提供库开发的实践参考。 一、库概述 1.1 项目背景 在软件开发的众多领域，数据完整性验证和安全性保障是至关重要的需求。哈希算法因其单向性、抗碰撞性和雪崩效应等特性，成为解决这些问题的理想工具。从文件校验到用户认证，从区块链技术到数字签名，哈希算法的应用无处不在。 libmd库旨在为仓颉语言提供一套完整、高效、易用的哈希算法解决方案，支持多种主流哈希算法，

By Ne0inhk
【优选算法必刷100题】第011~012题（同向双指针：滑动窗口算法）：最大连续1的个数 III、将 x 减到 0 的最小操作数

【优选算法必刷100题】第011~012题（同向双指针：滑动窗口算法）：最大连续1的个数 III、将 x 减到 0 的最小操作数

🔥艾莉丝努力练剑：个人主页 ❄专栏传送门：《C语言》、《数据结构与算法》、C/C++干货分享&学习过程记录、Linux操作系统编程详解、笔试/面试常见算法：从基础到进阶 ⭐️为天地立心，为生民立命，为往圣继绝学，为万世开太平 🎬艾莉丝的简介： 🎬艾莉丝的算法专栏简介： 目录 011  最大连续1的个数 III 1.1  题目详解 1.2  算法原理以及代码实现 1.2.1  解法思路：滑动窗口 1.2.2  算法流程 1.2.3  代码实现 1.3  博主手记 012  将 x 减到

By Ne0inhk
当AI变成“需求读心术大师“：Python开发者如何用“脑洞算法“破解预测困局？

当AI变成“需求读心术大师“：Python开发者如何用“脑洞算法“破解预测困局？

前言：哈喽，大家好，今天给大家分享一篇文章！并提供具体代码帮助大家深入理解，彻底掌握！创作不易，如果能帮助到大家或者给大家一些灵感和启发，欢迎点赞 + 收藏 + 关注哦 💕 当AI变成"需求读心术大师"：Python开发者如何用"脑洞算法"破解预测困局？ 📚 本文简介 本文探讨了AI需求预测的局限性及其与人类心理洞察的本质差异。通过Python代码示例（GradientBoostingClassifier模型）揭示了AI"读心术"实为基于历史数据的概率猜测，并运用mermaid图对比展示AI在情感理解、文化背景考量等方面的不足。关键发现： AI预测依赖表面行为数据，而人类能理解深层动机 开发者应结合算法与人文洞察，如文中小陈从"更快的马"解读出"便捷交通工具"的真实需求 提出Python开发场景对照表，显示人类在用户体验设计、错误处理等方面的温度优势 结论：AI预测是工具而非真理，开发者需保持批判思维，

By Ne0inhk
【算法详解】理解KMP，真的那么难吗？—— 一篇讲透它的核心思想

【算法详解】理解KMP，真的那么难吗？—— 一篇讲透它的核心思想

🫧 励志不掉头发的内向程序员：个人主页  ✨️ 个人专栏: 《C++语言》《Linux学习》 🌅偶尔悲伤，偶尔被幸福所完善 👓️博主简介: 文章目录 * 前言 * 一、相关概念 * 二、前缀函数 * 三、计算前缀函数 * 四、用前缀函数解决字符串匹配 * 五、kmp 算法模板 * 六、next 数组版本 * 七、周期和循环节 * 总结 前言 本文用尽量详细的语言来讲解说明 kmp 算法内容，学习之前需要知道一点点动态规划的基础，如果不知道最好去了解了解。我们一起来看看算法吧。 一、相关概念 在学习 kmp 算法之前，我们得先提前了解最基本的 “ 动态规划 ” 的知识，否则可能学习的时候会有一些困难，因为它的原理类似于动态规划。 字符串： * 用字符构成的的序列就是字符串。 这个概念很简单，但是我们这里有个小技巧：就和动态规划那样，

By Ne0inhk