深圳公司网站设计公,程序开发的难点,编写app用什么软件,建设一个小网站需要多少钱前言
近邻算法#xff08;K-Nearest Neighbors#xff0c;简称 KNN#xff09;是一种简单的、广泛使用的分类和回归算法。它的基本思想是#xff1a;给定一个待分类的样本#xff0c;找到这个样本在特征空间中距离最近的 k 个样本#xff0c;这 k 个样本的多数类别作为待…前言
近邻算法K-Nearest Neighbors简称 KNN是一种简单的、广泛使用的分类和回归算法。它的基本思想是给定一个待分类的样本找到这个样本在特征空间中距离最近的 k 个样本这 k 个样本的多数类别作为待分类样本的类别。
本教程文章将详细讲解如何使用 JavaScript 实现一个简单的 KNN 算法我们会从理论出发逐步从零开始编写代码。
理论基础
距离度量
KNN 算法的核心是计算两个样本之间的距离常用的距离度量方法有
欧氏距离Euclidean Distance曼哈顿距离Manhattan Distance
在本教程中我们将使用最常见的欧氏距离来计算样本之间的距离。
欧氏距离公式如下
[ d(p, q) \sqrt{\sum_{i1}^{n} (p_i - q_i)^2} ]
其中 ( p ) 和 ( q ) 是两个 n 维空间中的点 ( p_i ) 和 ( q_i ) 是这两个点在第 ( i ) 维的坐标。
算法步骤
计算距离计算待分类样本与训练样本集中所有样本的距离。排序按距离从小到大对所有距离进行排序。选择最近的 k 个样本从排序后的结果中选择距离最近的 k 个样本。投票多数投票决定待分类样本的类别。
实现步骤
初始化数据
首先我们需要一些样本数据来进行分类。假设我们有以下二维数据集
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 的计算复杂度较高尤其在高维数据和大规模数据集上因此在实际应用中常常需要结合其他技术进行优化。
