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

2024-06-10 23:36

本文主要是介绍基于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请求参数接收控制指南分享

《SpringBoot请求参数接收控制指南分享》:本文主要介绍SpringBoot请求参数接收控制指南,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring Boot 请求参数接收控制指南1. 概述2. 有注解时参数接收方式对比3. 无注解时接收参数默认位置

Go语言开发实现查询IP信息的MCP服务器

《Go语言开发实现查询IP信息的MCP服务器》随着MCP的快速普及和广泛应用,MCP服务器也层出不穷,本文将详细介绍如何在Go语言中使用go-mcp库来开发一个查询IP信息的MCP... 目录前言mcp-ip-geo 服务器目录结构说明查询 IP 信息功能实现工具实现工具管理查询单个 IP 信息工具的实现服

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾

SpringBoot项目中报错The field screenShot exceeds its maximum permitted size of 1048576 bytes.的问题及解决

《SpringBoot项目中报错ThefieldscreenShotexceedsitsmaximumpermittedsizeof1048576bytes.的问题及解决》这篇文章... 目录项目场景问题描述原因分析解决方案总结项目场景javascript提示:项目相关背景:项目场景:基于Spring

Spring Boot 整合 SSE的高级实践(Server-Sent Events)

《SpringBoot整合SSE的高级实践(Server-SentEvents)》SSE(Server-SentEvents)是一种基于HTTP协议的单向通信机制,允许服务器向浏览器持续发送实... 目录1、简述2、Spring Boot 中的SSE实现2.1 添加依赖2.2 实现后端接口2.3 配置超时时

Spring Boot读取配置文件的五种方式小结

《SpringBoot读取配置文件的五种方式小结》SpringBoot提供了灵活多样的方式来读取配置文件,这篇文章为大家介绍了5种常见的读取方式,文中的示例代码简洁易懂,大家可以根据自己的需要进... 目录1. 配置文件位置与加载顺序2. 读取配置文件的方式汇总方式一:使用 @Value 注解读取配置方式二

一文详解Java异常处理你都了解哪些知识

《一文详解Java异常处理你都了解哪些知识》:本文主要介绍Java异常处理的相关资料,包括异常的分类、捕获和处理异常的语法、常见的异常类型以及自定义异常的实现,文中通过代码介绍的非常详细,需要的朋... 目录前言一、什么是异常二、异常的分类2.1 受检异常2.2 非受检异常三、异常处理的语法3.1 try-

Java中的@SneakyThrows注解用法详解

《Java中的@SneakyThrows注解用法详解》:本文主要介绍Java中的@SneakyThrows注解用法的相关资料,Lombok的@SneakyThrows注解简化了Java方法中的异常... 目录前言一、@SneakyThrows 简介1.1 什么是 Lombok?二、@SneakyThrows

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间(一)使用预定义格式(二)自定义格式二、时间转字符串(一)使用预定义格式(二)自

Spring 请求之传递 JSON 数据的操作方法

《Spring请求之传递JSON数据的操作方法》JSON就是一种数据格式,有自己的格式和语法,使用文本表示一个对象或数组的信息,因此JSON本质是字符串,主要负责在不同的语言中数据传递和交换,这... 目录jsON 概念JSON 语法JSON 的语法JSON 的两种结构JSON 字符串和 Java 对象互转