基于JavaScript 实现近邻算法以及优化方案

2024-06-10 23:36
文章标签 java 算法 实现 优化 script 方案 近邻

本文主要是介绍基于JavaScript 实现近邻算法以及优化方案，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

近邻算法（K-Nearest Neighbors，简称 KNN）是一种简单的、广泛使用的分类和回归算法。它的基本思想是：给定一个待分类的样本，找到这个样本在特征空间中距离最近的 k 个样本，这 k 个样本的多数类别作为待分类样本的类别。

本教程文章将详细讲解如何使用 JavaScript 实现一个简单的 KNN 算法，我们会从理论出发，逐步从零开始编写代码。

理论基础

距离度量

KNN 算法的核心是计算两个样本之间的距离，常用的距离度量方法有：

  • 欧氏距离（Euclidean Distance）
  • 曼哈顿距离（Manhattan Distance）

在本教程中，我们将使用最常见的欧氏距离来计算样本之间的距离。

欧氏距离公式如下：

[ d(p, q) = \sqrt{\sum_{i=1}^{n} (p_i - q_i)^2} ]

其中 ( p ) 和 ( q ) 是两个 n 维空间中的点， ( p_i ) 和 ( q_i ) 是这两个点在第 ( i ) 维的坐标。

算法步骤

  1. 计算距离：计算待分类样本与训练样本集中所有样本的距离。
  2. 排序：按距离从小到大对所有距离进行排序。
  3. 选择最近的 k 个样本：从排序后的结果中选择距离最近的 k 个样本。
  4. 投票：多数投票决定待分类样本的类别。

实现步骤

初始化数据

首先，我们需要一些样本数据来进行分类。假设我们有以下二维数据集：

const trainingData = [{ x: 1, y: 2, label: 'A' },{ x: 2, y: 3, label: 'A' },{ x: 3, y: 3, label: 'B' },{ x: 6, y: 5, label: 'B' },{ x: 7, y: 8, label: 'B' },{ x: 8, y: 8, label: 'A' },
];

计算距离

编写一个函数来计算两个点之间的欧氏距离：

function euclideanDistance(point1, point2) {return Math.sqrt(Math.pow(point1.x - point2.x, 2) +Math.pow(point1.y - point2.y, 2));
}

排序并选择最近的 k 个样本

编写一个函数，根据距离对样本进行排序，并选择距离最近的 k 个样本：

function getKNearestNeighbors(trainingData, testPoint, k) {const distances = trainingData.map((dataPoint) => ({...dataPoint,distance: euclideanDistance(dataPoint, testPoint)}));distances.sort((a, b) => a.distance - b.distance);return distances.slice(0, k);
}

多数投票

编写一个函数，通过多数投票来决定类别：

function majorityVote(neighbors) {const voteCounts = neighbors.reduce((acc, neighbor) => {acc[neighbor.label] = (acc[neighbor.label] || 0) + 1;return acc;}, {});return Object.keys(voteCounts).reduce((a, b) => voteCounts[a] > voteCounts[b] ? a : b);
}

主函数

最后，编写一个主函数来整合上述步骤，完成 KNN 算法：

function knn(trainingData, testPoint, k) {const neighbors = getKNearestNeighbors(trainingData, testPoint, k);return majorityVote(neighbors);
}

测试

现在我们来测试一下这个 KNN 实现：

const testPoint = { x: 5, y: 5 };
const k = 3;const result = knn(trainingData, testPoint, k);
console.log(`The predicted label for the test point is: ${result}`);

运行这个代码，你会得到预测的类别。

优化方案

虽然我们已经实现了一个基本的 KNN 算法，但在实际应用中，我们还可以进行一些优化和扩展，使其更加高效和实用。

优化距离计算

在大数据集上，计算每个点之间的欧氏距离可能会很耗时。我们可以通过一些高效的数据结构如 KD 树（K-Dimensional Tree）来进行快速邻近搜索。以下是一个简单的 KD 树的实现示例：

class KDTree {constructor(points, depth = 0) {if (points.length === 0) {this.node = null;return;}const k = 2; // 2Dconst axis = depth % k;points.sort((a, b) => a[axis] - b[axis]);const median = Math.floor(points.length / 2);this.node = points[median];this.left = new KDTree(points.slice(0, median), depth + 1);this.right = new KDTree(points.slice(median + 1), depth + 1);}nearest(point, depth = 0, best = null) {if (this.node === null) {return best;}const k = 2;const axis = depth % k;let nextBranch = null;let oppositeBranch = null;if (point[axis] < this.node[axis]) {nextBranch = this.left;oppositeBranch = this.right;} else {nextBranch = this.right;oppositeBranch = this.left;}best = nextBranch.nearest(point, depth + 1, best);const dist = euclideanDistance(point, this.node);if (best === null || dist < euclideanDistance(point, best)) {best = this.node;}if (Math.abs(point[axis] - this.node[axis]) < euclideanDistance(point, best)) {best = oppositeBranch.nearest(point, depth + 1, best);}return best;}
}const points = trainingData.map(point => [point.x, point.y, point.label]);
const kdTree = new KDTree(points);const nearestPoint = kdTree.nearest([testPoint.x, testPoint.y]);
console.log(`The nearest point is: ${nearestPoint[2]}`);

考虑不同距离度量

不同的距离度量方法在不同的场景下可能会有不同的效果。除了欧氏距离外，还可以尝试以下几种距离度量方法：

  • 曼哈顿距离（Manhattan Distance）
  • 闵可夫斯基距离（Minkowski Distance）
  • 切比雪夫距离（Chebyshev Distance）

我们可以编写一些函数来实现这些距离度量方法，并在主函数中进行选择：

function manhattanDistance(point1, point2) {return Math.abs(point1.x - point2.x) + Math.abs(point1.y - point2.y);
}function minkowskiDistance(point1, point2, p) {return Math.pow(Math.pow(Math.abs(point1.x - point2.x), p) +Math.pow(Math.abs(point1.y - point2.y), p),1 / p);
}function chebyshevDistance(point1, point2) {return Math.max(Math.abs(point1.x - point2.x), Math.abs(point1.y - point2.y));
}

调整 k 值

选择合适的 k 值对算法的性能至关重要。过小的 k 值可能导致过拟合，而过大的 k 值可能导致欠拟合。一个常见的做法是通过交叉验证来选择最优的 k 值。

处理多维数据

在实际应用中，数据通常是多维的。我们的算法已经可以处理二维数据，但对于多维数据，只需稍微调整距离计算函数即可：

function euclideanDistanceND(point1, point2) {let sum = 0;for (let i = 0; i < point1.length; i++) {sum += Math.pow(point1[i] - point2[i], 2);}return Math.sqrt(sum);
}

代码重构

为了更好地组织代码，我们可以将不同的功能模块化：

class KNN {constructor(k = 3, distanceMetric = euclideanDistance) {this.k = k;this.distanceMetric = distanceMetric;}fit(trainingData) {this.trainingData = trainingData;}predict(testPoint) {const neighbors = this.getKNearestNeighbors(testPoint);return this.majorityVote(neighbors);}getKNearestNeighbors(testPoint) {const distances = this.trainingData.map((dataPoint) => ({...dataPoint,distance: this.distanceMetric(dataPoint, testPoint)}));distances.sort((a, b) => a.distance - b.distance);return distances.slice(0, this.k);}majorityVote(neighbors) {const voteCounts = neighbors.reduce((acc, neighbor) => {acc[neighbor.label] = (acc[neighbor.label] || 0) + 1;return acc;}, {});return Object.keys(voteCounts).reduce((a, b) => voteCounts[a] > voteCounts[b] ? a : b);}
}// 测试代码
const knnClassifier = new KNN(3, euclideanDistance);
knnClassifier.fit(trainingData);
const predictedLabel = knnClassifier.predict(testPoint);
console.log(`The predicted label for the test point is: ${predictedLabel}`);

通过这种方式，我们不仅提高了代码的可读性和可维护性，还为将来更复杂的扩展和优化打下了基础。

结语

KNN 算法简单易懂，适用于很多分类问题，特别是在数据规模不大时。然而，KNN 的计算复杂度较高，尤其在高维数据和大规模数据集上，因此在实际应用中常常需要结合其他技术进行优化。

这篇关于基于JavaScript 实现近邻算法以及优化方案的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1049591。

相关文章

SpringBoot整合liteflow的详细过程

SpringBoot整合liteflow的详细过程

《SpringBoot整合liteflow的详细过程》：本文主要介绍SpringBoot整合liteflow的详细过程,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋...  liteflow 是什么？ 能做什么？总之一句话：能帮你规范写代码逻辑 ，编排并解耦业务逻辑，代码
阅读更多...
JavaSE正则表达式用法总结大全

JavaSE正则表达式用法总结大全

《JavaSE正则表达式用法总结大全》正则表达式就是由一些特定的字符组成,代表的是一个规则,：本文主要介绍JavaSE正则表达式用法的相关资料,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录常用的正则表达式匹配符正则表China编程达式常用的类Pattern类Matcher类PatternSynta
阅读更多...
Spring Security中用户名和密码的验证完整流程

Spring Security中用户名和密码的验证完整流程

《SpringSecurity中用户名和密码的验证完整流程》本文给大家介绍SpringSecurity中用户名和密码的验证完整流程,本文结合实例代码给大家介绍的非常详细,对大家的学习或工作具有一定... 首先创建了一个UsernamePasswordAuthenticationTChina编程oken对象，这是S
阅读更多...
java实现docker镜像上传到harbor仓库的方式

java实现docker镜像上传到harbor仓库的方式

《java实现docker镜像上传到harbor仓库的方式》：本文主要介绍java实现docker镜像上传到harbor仓库的方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录1. 前 言2. 编写工具类2.1 引入依赖包2.2 使用当前服务器的docker环境推送镜像2.2
阅读更多...
C++20管道运算符的实现示例

C++20管道运算符的实现示例

《C++20管道运算符的实现示例》本文简要介绍C++20管道运算符的使用与实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录标准库的管道运算符使用自己实现类似的管道运算符我们不打算介绍太多，因为它实际属于c++20最为重要的
阅读更多...
Java easyExcel实现导入多sheet的Excel

Java easyExcel实现导入多sheet的Excel

《JavaeasyExcel实现导入多sheet的Excel》这篇文章主要为大家详细介绍了如何使用JavaeasyExcel实现导入多sheet的Excel,文中的示例代码讲解详细,感兴趣的小伙伴可... 目录1.官网2.Excel样式3.代码1.官网easyExcel官网2.Excel样式3.代码
阅读更多...
Java MQTT实战应用

Java MQTT实战应用

《JavaMQTT实战应用》本文详解MQTT协议,涵盖其发布/订阅机制、低功耗高效特性、三种服务质量等级（QoS0/1/2）,以及客户端、代理、主题的核心概念,最后提供Linux部署教程、Sprin... 目录一、MQTT协议二、MQTT优点三、三种服务质量等级四、客户端、代理、主题1. 客户端（Clien
阅读更多...
Java中调用数据库存储过程的示例代码

Java中调用数据库存储过程的示例代码

《Java中调用数据库存储过程的示例代码》本文介绍Java通过JDBC调用数据库存储过程的方法,涵盖参数类型、执行步骤及数据库差异,需注意异常处理与资源管理,以优化性能并实现复杂业务逻辑,感兴趣的朋友... 目录一、存储过程概述二、Java调用存储过程的基本javascript步骤三、Java调用存储过程示
阅读更多...
MyBatisPlus如何优化千万级数据的CRUD

MyBatisPlus如何优化千万级数据的CRUD

《MyBatisPlus如何优化千万级数据的CRUD》最近负责的一个项目,数据库表量级破千万,每次执行CRUD都像走钢丝,稍有不慎就引起数据库报警,本文就结合这个项目的实战经验,聊聊MyBatisPl... 目录背景一、MyBATis Plus 简介二、千万级数据的挑战三、优化 CRUD 的关键策略1. 查
阅读更多...
python实现对数据公钥加密与私钥解密

python实现对数据公钥加密与私钥解密

《python实现对数据公钥加密与私钥解密》这篇文章主要为大家详细介绍了如何使用python实现对数据公钥加密与私钥解密,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录公钥私钥的生成使用公钥加密使用私钥解密公钥私钥的生成这一部分，使用python生成公钥与私钥，然后保存在两个文
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2