机器学习 -- k近邻算法

场景

我学习Python的初衷是学习人工智能，满足现有的业务场景。所以必须要看看机器学习这一块。今天看了很久，做个总结。
机器学习分为深度学习和传统机器学习

深度学习

深度学习模型通常非常复杂，包含多层神经网络，每一层都包含大量的神经元（节点）。这些模型可以包含数百万甚至数十亿个参数。深度学习模型可以自动学习数据的特征表示，而无需手动设计特征。通过多层神经网络，深度学习模型可以逐层提取和组合特征，从而更好地捕捉数据中的复杂模式。深度学习模型通常需要大量的数据来进行训练，以充分学习复杂的参数。这意味着深度学习在大规模数据集上表现良好，但在小数据集上可能会过拟合。而且深度学习更像是一个黑盒子，你也不知道它为什么会得到这个结果。还有，深度学习通常需要大量的计算资源，例如高性能GPU，以加速模型的训练。这使得深度学习在硬件要求上更为苛刻。深度学习更适合于计算机视觉，自然语言处理，自动驾驶等场景。

传统机器学习

传统机器学习模型通常比深度学习模型简单，包括线性回归、决策树、支持向量机（SVM）、K近邻（K-NN）等。这些模型具有较少的参数。传统机器学习通常需要手动设计和提取特征。特征工程是一个关键的步骤，需要领域专业知识和经验来选择和创建适当的特征。传统机器学习模型在小规模数据集上也可以表现良好，并且通常不容易过拟合。相对于深度学习，传统机器学习算法通常需要较少的计算资源，因此在资源受限的环境中更具可行性。传统学习很适用于有明确输入与输出数据的场景，如图像识别、语音识别和文本分类。在这些任务中，算法通过训练数据集来学习，其中包含输入数据及其对应的正确输出。

在传统机器分类学习中，有一个很经典的算法叫做 “k近邻算法”。

k近邻算法

众所周知，有很多种类电影，爱情电影，动作电影。爱情电影里有kiss片段，但是可能也会有武打片段。动作片里有动作片段，可能也有Kiss片段。但是，经常看电影的肯定知道，爱情片里的动作片段远远小于动作片段，反之亦然。基于某一场景是否可以给电影分类呢？这种场景就很适合k近邻算法。

概述

k近邻算法是一种简单但非常有效的机器学习算法，主要用于分类和回归问题。其核心思想是基于相似性原则进行预测：即相似的数据点具有相似的输出。

距离度量：改算法首先计算测试数据与每个训练数据点之间的距离。常用的距离度量方法包括欧氏距离、曼哈顿距离和闵可夫斯基距离。 例如：测试样例特征是 [0,0]，样本集特征是 [1,2] 那么距离就是
[(1-0) **2 + (2-0) **2] **0.5 （欧氏距离） 如果距离测试样例的三个样本的值分别是 0，1，2 k是2 ，那么样本1类型如果为A，样本2类型为A，那么测试类型为A。
决策规则：
分类：对于分类问题，算法通常采用“多数投票”原则，即测试数据点被分配到邻居中最常见的类别。
回归：对于回归问题，算法通常计算K个邻居的输出值的平均值，作为预测值。

特点
简单有效：k近邻算法是一种理解起来直观且实现简单的算法。
惰性学习：与其他机器学习算法不同，k近邻算法不需要在训练阶段进行显著的学习过程。它在预测阶段才进行计算，因此属于惰性学习算法。
无参数：k近邻算法不假设数据的分布，因此是一种非参数算法。
内存密集型：由于算法需要存储所有训练数据，因此对内存要求较高。

缺点
K值的选择：K的选择对算法的性能有重要影响。较小的K值使模型对噪声数据更敏感，而较大的K值则可能导致分类/回归边界的平滑化。
维度诅咒：在高维数据中，计算距离变得困难，这会影响k近邻算法算法的性能。
标准化：k近邻算法对数据的尺度非常敏感，因此通常需要进行特征标准化。
计算成本：对于大型数据集，计算每个测试实例的邻居可能非常耗时。

demo

我们根据上述所说，编写k近邻算法的代码：

def classify0(inX, dataSet, labels, k):
    # 获取数据集的行数
    dataSetSize = dataSet.shape[0]
    # 计算输入向量与数据集中每个数据点的差值矩阵
    diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet
    # 计算差值矩阵中每个元素的平方
    sqDiffMat = diffMat ** 2
    # 计算每行的平方差值和，得到平方距离的数组
    sqDistances = sqDiffMat.sum(axis=1)
    # 对平方距离数组开平方，得到距离数组
    distances = sqDistances ** 0.5
    # 对距离数组进行排序，返回排序后的索引
    sortedDistIndices = distances.argsort()
    # 创建一个字典，用于存储最近的 k 个数据点的类别及其出现次数
    classCount = {}
    # 遍历排序后的前 k 个索引
    for i in range(k):
        # 获取当前最近数据点的类别
        voteIlabel = labels[sortedDistIndices[i]]
        # 更新字典中该类别的出现次数
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
    # 对字典中的类别及其出现次数进行排序，按出现次数降序排列
    sortedClassCount = sorted(classCount.items(), key=lambda x: x[1], reverse=True)
    # 返回最频繁出现的类别
    return sortedClassCount[0][0]

作为java老本行，自然得有java版。

/**
 * k近邻算法
 * @Author: Herche Jane
 * @Date: 2024/01/04
 */
public class KNNClassifier {

    public static String classify0(double[] inX, double[][] dataSet, String[] labels, int k) {
        int dataSetSize = dataSet.length;

        // 计算距离
        double[] distances = new double[dataSetSize];
        for (int i = 0; i < dataSetSize; i++) {
            double[] data = dataSet[i];
            double distance = 0;
            for (int j = 0; j < inX.length; j++) {
                distance += Math.pow(inX[j] - data[j], 2);
            }
            distances[i] = Math.sqrt(distance);
        }

        // 获取距离的排序索引
        Integer[] sortedDistIndices = getSortedIndices(distances);

        // 计算前k个最近邻的类别及其出现次数
        Map<String, Integer> classCount = new HashMap<>();
        for (int i = 0; i < k; i++) {
            String label = labels[sortedDistIndices[i]];
            classCount.put(label, classCount.getOrDefault(label, 0) + 1);
        }

        // 对类别出现次数进行排序
        List<Map.Entry<String, Integer>> sortedClassCount = new ArrayList<>(classCount.entrySet());
        sortedClassCount.sort((o1, o2) -> o2.getValue().compareTo(o1.getValue()));

        // 返回最频繁的类别
        return sortedClassCount.get(0).getKey();
    }

    private static Integer[] getSortedIndices(double[] array) {
        Integer[] indices = new Integer[array.length];
        for (int i = 0; i < array.length; i++) {
            indices[i] = i;
        }
        Arrays.sort(indices, Comparator.comparingDouble(i -> array[i]));
        return indices;
    }
}

测试调用

致敬java

    public static void main(String[] args) {
        // 示例：数据集和标签
        double[][] dataSet = {{1.0, 2.0}, {2.0, 3.0}, {3.0, 4.0}};
        String[] labels = {"A", "B", "B"};
        double[] inX = {1.5, 2.5};

        // 使用KNN进行分类
        String result = classify0(inX, dataSet, labels, 3);
        System.out.println("分类结果: " + result);
    }

调用结果：

分类结果: B

结束

k近邻算法是分类最简单最有效的方案，k近邻算法必须保存所有的训练集，这就意味着很吃内存。这个算法我们根本就不知道平均实例样本和典型实例样本是什么。当K值较小，即考虑的邻居数量较少时，如果有噪声和脏数据，那么这个训练算是废了。没有自己纠正自己的能力，这就要求数据必须要有预处理，否则很容易出问题！