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

相关文章

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N

Java编译生成多个.class文件的原理和作用

《Java编译生成多个.class文件的原理和作用》作为一名经验丰富的开发者,在Java项目中执行编译后,可能会发现一个.java源文件有时会产生多个.class文件,从技术实现层面详细剖析这一现象... 目录一、内部类机制与.class文件生成成员内部类(常规内部类)局部内部类(方法内部类)匿名内部类二、

SpringBoot实现数据库读写分离的3种方法小结

《SpringBoot实现数据库读写分离的3种方法小结》为了提高系统的读写性能和可用性,读写分离是一种经典的数据库架构模式,在SpringBoot应用中,有多种方式可以实现数据库读写分离,本文将介绍三... 目录一、数据库读写分离概述二、方案一:基于AbstractRoutingDataSource实现动态

Python FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

《PythonFastAPI+Celery+RabbitMQ实现分布式图片水印处理系统》这篇文章主要为大家详细介绍了PythonFastAPI如何结合Celery以及RabbitMQ实现简单的分布式... 实现思路FastAPI 服务器Celery 任务队列RabbitMQ 作为消息代理定时任务处理完整

Springboot @Autowired和@Resource的区别解析

《Springboot@Autowired和@Resource的区别解析》@Resource是JDK提供的注解,只是Spring在实现上提供了这个注解的功能支持,本文给大家介绍Springboot@... 目录【一】定义【1】@Autowired【2】@Resource【二】区别【1】包含的属性不同【2】@

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

Elasticsearch 在 Java 中的使用教程

《Elasticsearch在Java中的使用教程》Elasticsearch是一个分布式搜索和分析引擎,基于ApacheLucene构建,能够实现实时数据的存储、搜索、和分析,它广泛应用于全文... 目录1. Elasticsearch 简介2. 环境准备2.1 安装 Elasticsearch2.2 J

Java中的String.valueOf()和toString()方法区别小结

《Java中的String.valueOf()和toString()方法区别小结》字符串操作是开发者日常编程任务中不可或缺的一部分,转换为字符串是一种常见需求,其中最常见的就是String.value... 目录String.valueOf()方法方法定义方法实现使用示例使用场景toString()方法方法