基于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 的计算复杂度较高，尤其在高维数据和大规模数据集上，因此在实际应用中常常需要结合其他技术进行优化。