基于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。

相关文章

Vue3 的 shallowRef 和 shallowReactive：优化性能

Vue3 的 shallowRef 和 shallowReactive：优化性能

大家对 Vue3 的 ref 和 reactive 都很熟悉，那么对 shallowRef 和 shallowReactive 是否了解呢？ 在编程和数据结构中，“shallow”（浅层）通常指对数据结构的最外层进行操作，而不递归地处理其内部或嵌套的数据。这种处理方式关注的是数据结构的第一层属性或元素，而忽略更深层次的嵌套内容。 1. 浅层与深层的对比 1.1 浅层（Shallow） 定义
阅读更多...
JVM 的类初始化机制

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时，有没有考虑过 JVM 是如何把静态的字节码（byte code）转化为运行时对象的呢，这个问题看似简单，但清楚的同学相信也不会太多，这篇文章首先介绍 JVM 类初始化的机制，然后给出几个易出错的实例来分析，帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段，分别是：loading 、Linking、initialization
阅读更多...
Spring Security 基于表达式的权限控制

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权，允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true （Spring security默认会带有ROLE_前缀）,去
阅读更多...
浅析Spring Security认证过程

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程，特意画了如下的类图，包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口，接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti
阅读更多...
Spring Security--Architecture Overview

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类，它们之间的依赖，构建起了整个框架。想要理解整个架构，最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文（security context）的信息。当前操作的用户是谁，该用户是否已经被认证，他拥有哪些角色权限…这些都被保
阅读更多...
Spring Security基于数据库验证流程详解

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
Spring Security 从入门到进阶系列教程

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
Java架构师知识体认识

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
无人叉车3d激光slam多房间建图定位异常处理方案-墙体画线地图切分方案

无人叉车3d激光slam多房间建图定位异常处理方案-墙体画线地图切分方案

墙体画线地图切分方案 针对问题：墙体两侧特征混淆误匹配，导致建图和定位偏差，表现为过门跳变、外月台走歪等 ·解决思路：预期的根治方案IGICP需要较长时间完成上线，先使用切分地图的工程化方案，即墙体两侧切分为不同地图，在某一侧只使用该侧地图进行定位 方案思路 切分原理：切分地图基于关键帧位置，而非点云。 理论基础：光照是直线的，一帧点云必定只能照射到墙的一侧，无法同时照到两侧实践考虑：关
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2