KNN算法

KNN概念

1.K近邻算法，即是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例，这K个实例的多数属于某个类，就把该输入实例分类到这个类中。

例如下图展现了两类样本数据，分别由正方形和三角形表示，待分类数据由圆形表示，算法的目的是依据已知的样本数据判断待分类数据的类别，即对圆形数据分类。

距离度量的选择

k近邻算法中需要按照距离递增次序排序，通常选取以下类型的距离：

$x_{i}=\left(x_{i}^{(1)},x_{i}^{(2)},\cdots,x_{i}^{(n)}\right)^{\mathrm{T}}$

欧式距离： $L_{2}(x_{i},x_{j})=\left(\sum_{l=1}^{n}|x_{i}^{(l)}-x_{j}^{(l)}|^{2}\right)^{\frac{1}{2}}$
Lp距离： $L_{p}(x_{i},x_{j})=\left(\sum_{l=1}^{n}\mid x_{i}^{(l)}-x_{j}^{(l)}\mid^{p}\right)^{\frac{1}{p}}$
曼哈顿距离： $L_{1}(x_{i},x_{j})=\sum_{l=1}^{n}|x_{i}^{(l)}-x_{j}^{(l)}|$
L $\infty$ 距离： $L_{\infty}(x_{i},x_{j})=\max_{l}\mid x_{i}^{(l)}-x_{j}^{(l)}\mid$

计算距离一般使用欧氏距离公式，欧几里得公式

K值少数服从多数，由最近的k个邻居决定判别点的归属

流程

1.计算已知数据集的多个点和当前点的距离

2.按照距离递增排序

3.选取当前点距离最近的k个点

4.确定这k个点的类别所出现频率

5.返回k个点出现频率最高的类别作为预测类别

数据集选择

用黑白手写数字识别举例，KNN算法不需要太多数据集，如只需要黑白，可以用ps手写,规定好数据集的范围，如都是28x28,32x32

k值的选择

选择较小的k值
噪声敏感
K值的减小意味着着整体模型会变得复杂，容易发生过拟合情况
学习的近似误差(approximation error)会减小，但学习的估计误差(estimation error)会增大

过拟合：在训练集上准确率非常高，而在测试集上准确率低

选择较大的k值
K值的增大意味着整体的模型会变得简单
学习的估计误差(estimation error)会减小，但学习的近似误差(approximation error)会增大
合理的选择方式：一般先选取一个较小的k值，然后采取交叉验证法来选取最优的k值，即实验调参，类似于神经网络通过调整超参数来得到一个较好的层数。

KNN算法优缺点

优点:

1.精度高

2.对异常值不敏感

3.无数据输入假定

缺点:

1.计算复杂度高

2.空间复杂度高

java方式将图片二值化

/**
     * 将图片二值化
     *
     * @param file
     */
    public int[][] imageTrainBit(File file) {
        try {

            BufferedImage read = ImageIO.read(file);

            int width = read.getWidth();
            int height = read.getHeight();
            BufferedImage bufferedImage = new BufferedImage(width, height, BufferedImage.TYPE_BYTE_GRAY);
            Graphics2D graphics = bufferedImage.createGraphics();
            graphics.drawImage(read, 0, 0, null);
            graphics.dispose();


            int threshold = 128;
            //用于存储图片的二值化数组
            int data[][] = new int[height][width];
            for (int y = 0; y < height; ++y) {
                for (int x = 0; x < width; ++x) {
                    //获取图片指定点的rgb色彩
                    //int rgb = read.getRGB(x,y);
                    int gray = new Color(bufferedImage.getRGB(x, y)).getRed();
                    int binaryPixel = gray < threshold ? Color.BLACK.getRGB() : Color.WHITE.getRGB();
                    //binaryImage.setRGB(x,y,binaryPixel)
                    data[y][x] = gray != 0 ? 1 : 0;
                }
            }
            return data;
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

将二值化的图片转换为一维特征向量值

/**
     * 将二值化的图片转换为一维特征向量值
     *
     * @return
     */
    public int[] bitImageTrainVector(int imageBit[][]) {
        int data[] = new int[imageBit.length * imageBit[0].length];
        for (int y = 0; y < imageBit.length; ++y) {
            for (int x = 0; x < imageBit[y].length; ++x) {
                data[imageBit[y].length * y + x] = imageBit[y][x];
            }
        }
        return data;
    }

特征数量

特征数量 是指在模型中每个样本所包含的独立变量或属性的数量。在图像识别中，每个图像可以被视为一个特征矩阵。具体来说：

每个像素作为特征：在处理图像时，图像的每个像素值都可以被视为一个特征。当图像被展平成一维数组时，数组的长度即为特征数量。例如，一个28x28的灰度图像有784个像素，因此它的特征数量为784。
其他特征：除了直接使用像素值外，有时候会提取其他特征，如边缘、角点、纹理等，这些都是定义图像特征的方式。总特征数量可能包括所有这些特征。

为什么要转换成0-1矩阵

将图像转换为0-1矩阵：

数据范围一致性：
- 图像的原始像素值通常在0到255之间（对于8位灰度图像）。如果将其直接输入到KNN模型等算法中，各种特征由于数值上存在差异，可能导致模型无法有效地比较不同特征之间的距离。
- 将像素值转换为0-1范围内的浮点数可以保证特征值在同一尺度上，从而使得距离计算更加合理和准确。
提高收敛速度：
- 在某些机器学习算法中，特征的尺度会影响模型的训练效率。通过统一特征的尺度，可以加速收敛过程，减少训练时间。
降低计算复杂度：
- 在一些算法中，尤其是在计算距离的方法中（如欧几里得距离），特征值的大小差异会影响最终结果。统一特征值的范围可以降低计算复杂度，提高模型性能。
避免数值不稳定性：
- 较大的数字可能导致浮点运算中的数值不稳定性，将特征缩放到0-1区间可以减少这种风险。

基于C++的Opencv实现KNN算法识别手写黑白数字

流程(假设你已经安装好了Opencv)

引入库和定义数据结构。
检查文件的存在性。
加载训练图像并提取特征和标签。
训练 KNN 模型。
加载测试图像，转换为特征向量。
进行数字识别，返回预测结果。
输出识别结果。

需要引用的头文件

#include <opencv2/highgui/highgui_c.h>
#include <filesystem>
#include <algorithm>
#include <opencv2/opencv.hpp>
#include <opencv2/ml.hpp>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>


using namespace cv;
using namespace cv::ml;
using namespace std;
namespace fs = std::filesystem;

结构体定义：定义一个名为 xlsj 的结构体，用于存储训练数据每个样本的特征和对应标签

// 定义 训练数据结构体
struct xlsj {
    Mat features;  // 特征向量
    int label;     // 标签
};

定义一个名为 KNNModel 的结构体，用于存储 KNN 模型及其特征数量,使用智能指针Ptr管理KNN对象的内存，”numFeatures”存储特征矩阵列数方便后面的识别预测

struct KNNModel {
    Ptr<KNearest> knn;
    int numFeatures;  // 特征矩阵的列数
};

文件存在性检查

检查指定路径的文件是否存在

使用 ifstream 尝试打开文件，如果成功则返回 true，否则返回 false


// 检查文件是否存在
bool fileExists(const string& filePath) {
    ifstream file(filePath);
    return file.good();
}

图像转换及二值化

将输入图像转换为二值化形式。

cvtColor：将图像转换为灰度图。

threshold：对灰度图像应用阈值，生成二值图像，背景为黑色，前景为白色。

返回二值化后的图像。

// 转换图像为01矩阵并进行二值化处理
Mat To01Matrix(const Mat& image) {
    Mat grayImage;
    cvtColor(image, grayImage, COLOR_BGR2GRAY); //转灰度图像
    Mat binaryImage;
    threshold(grayImage, binaryImage, 128, 255, THRESH_BINARY_INV); // 二值化
    return binaryImage;
}

加载训练数据

遍历指定路径trainPath下所有的文件，避免了文件名乱糟糟不好写的情况，加载图像提取特征和标签.

fs::directory_iterator(trainPath)：遍历指定路径中的文件和目录。

entry.path().string()：获取当前文件/目录的完整路径。

检查文件是否存在且为常规文件，并加载图像。

如果读取成功，则获取图像的特征，提取标签，并将 xlsj 结构体添加到 trainDataSet 向量中。

// 加载训练数据
vector<xlsj> loadTrainData(const string& trainPath) {
    vector<xlsj> trainDataSet;
    for (const auto& entry : fs::directory_iterator(trainPath)) {
        const auto& filePath = entry.path().string();

        // 打印遍历到的文件名
        cout << "尝试加载图像: " << filePath << endl;

        if (fs::is_regular_file(entry) && fileExists(filePath)) {
            Mat image = imread(filePath);
            if (image.empty()) {
                cout << "无法加载图像 " << filePath << "!" << endl;
                continue; // 忽略无法加载的图像
            }

            Mat features = To01Matrix(image).reshape(1, 1); // 展平成一维特征向量
           // features.convertTo(features, CV_32F); // 转换特征矩阵为浮点型

            // 从文件名中提取标签
            int label = stoi(filePath.substr(trainPath.size(), filePath.find_last_of('-') - trainPath.size()));

            xlsj data;
            data.features = features;
            data.label = label;
            trainDataSet.push_back(data);
        }
        else {
            cout << "文件 " << filePath << " 不是常规文件或不存在!" << endl;
        }
    }

    cout << "加载的训练数据数量: " << trainDataSet.size() << endl;
    return trainDataSet;
}

训练 KNN 模型

从训练数据集中提取特征和标签，并使用这些数据训练 KNN 模型。

push_back：将每个特征和标签添加到相应的矩阵中。

1 2	featureMatrix.push_back(data.features); labelMatrix.push_back(data.label);

将当前数据点的特征和标签添加到特征和标签矩阵中

1	Ptr<KNearest> knn = KNearest::create();

创建一个智能指针 knn，指向新的KNN模型实例。使用 Ptr 是为了自动管理内存，避免手动释放。

检查特征和标签矩阵是否为空，若为空则输出错误信息并返回，并将特征矩阵转换为浮点型、标签矩阵转换为整型。创建 KNN 模型并设置 K 值，调用 train 方法训练模型。

最后返回包含 KNN 模型和特征列数的结构体。

1	return { knn, featureMatrix.cols };

// 训练KNN模型
KNNModel trainKNN(const vector<xlsj>& trainDataSet, int k) {
    Mat featureMatrix, labelMatrix; // 特征与标签矩阵
    for (const auto& data : trainDataSet) {
        featureMatrix.push_back(data.features);
        labelMatrix.push_back(data.label);
    }

    // 检查特征和标签矩阵
    if (featureMatrix.empty() || labelMatrix.empty()) {
        cout << "特征矩阵或标签矩阵为空!" << endl;
        return { nullptr, -1 }; // 返回空指针
    }

    featureMatrix.convertTo(featureMatrix, CV_32F); // 转换特征矩阵为浮点型
    labelMatrix.convertTo(labelMatrix, CV_32S); // 转换标签矩阵为整数型

    Ptr<KNearest> knn = KNearest::create();
    knn->setDefaultK(k);
    knn->train(featureMatrix, ROW_SAMPLE, labelMatrix);

    cout << "KNN模型训练完成" << endl;
    return { knn, featureMatrix.cols };  // 返回 KNN 模型以及特征矩阵的列数
}

使用 KNN 进行数字识别

接受测试图像并返回预测的标签。

将测试图像转换为 01 矩阵，并展平为特征向量,并且确保特征矩阵为浮点型。

然后调用 findNearest 方法找到最近的 K 个邻居，并返回结果、标签和距离。

1	knn->findNearest(features, 1, result, resultLabels, resultDistances);

调用 KNN 模型的成员函数 findNearest 来寻找最近的 K 个邻居。

参数说明：

features: 输入的特征向量，用于识别。

1: K值，指定要查找的邻居的数量，这里设置为1，即找到最近的一个邻居。

result: 用于存储识别结果的矩阵。

resultLabels: 用于存储最近邻的标签信息。

resultDistances: 用于存储最近邻的距离信息。

最后从结果标签中转整形提取预测的数字。

// 使用KNN进行识别
int recognizeDigit(const Ptr<KNearest>& knn, const Mat& testImage) {
    Mat features = To01Matrix(testImage).reshape(1, 1);//转01矩阵的特征
    features.convertTo(features, CV_32F); // 转换特征矩阵为浮点型
    Mat result;//结果
    Mat resultLabels;//结果标签
    Mat resultDistances;//结果距离
    knn->findNearest(features, 1, result, resultLabels, resultDistances);
    return (int)resultLabels.at<float>(0, 0);
}

主函数

int main() {
    // k值
    int k = 5;
    string n = "9";

    // 路径
    string testPath = R"(C:\cyuyan\KNNmain\data\test\)" + n + ".jpg";
    string trainPath = R"(C:\cyuyan\KNNmain\data\xl\)";
    // Mat src = imread(testPath);

    // 加载训练数据
    vector<xlsj> trainDataSet = loadTrainData(trainPath);
    if (trainDataSet.empty()) {
        cout << "没有训练数据!" << endl; // 查询训练数据是否存在
        return -1;
    }

    // 训练 KNN 模型
    KNNModel model = trainKNN(trainDataSet, k);

    if (!model.knn) {
        return -1; //判断trainKNN是否正常
    }

    // 加载测试图像
    if (!fileExists(testPath)) {
        cout << "测试文件 " << testPath << " 不存在!" << endl;
        return -1;
    }

    Mat testImage = imread(testPath);
    if (testImage.empty()) {
        cout << "无法加载图像" << testPath << "!" << endl;
        return -1;
    }

    // 进行识别
    Mat features = To01Matrix(testImage).reshape(1, 1); // 转01矩阵的特征
    features.convertTo(features, CV_32F); // 转换特征矩阵为浮点型

    // 判断特征数量与训练特征是否一样
    if (features.cols != model.numFeatures) {
        cout << "测试样本的特征数量与训练样本不匹配" << endl;
        return -1;
    }

    //namedWindow("test opencv setup", CV_WINDOW_AUTOSIZE);
    //imshow("test opencv setup", src);

    int res = recognizeDigit(model.knn, testImage);
    cout << "预测结果: " << res << endl;

    return 0;
}

贴一下完整代码

#include <opencv2/highgui/highgui_c.h>
#include <filesystem>
#include <algorithm>
#include <opencv2/opencv.hpp>
#include <opencv2/ml.hpp>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>


using namespace cv;
using namespace cv::ml;
using namespace std;
namespace fs = std::filesystem;

// 定义 训练数据结构体
struct xlsj {
    Mat features;  // 特征向量
    int label;     // 标签
};
struct KNNModel {
    Ptr<KNearest> knn;
    int numFeatures;  // 特征矩阵的列数
};

// 检查文件是否存在
bool fileExists(const string& filePath) {
    ifstream file(filePath);
    return file.good();
}

// 转换图像为01矩阵并进行二值化处理
Mat To01Matrix(const Mat& image) {
    Mat grayImage;
    cvtColor(image, grayImage, COLOR_BGR2GRAY); //转灰度图像
    Mat binaryImage;
    threshold(grayImage, binaryImage, 128, 255, THRESH_BINARY_INV); // 二值化
    return binaryImage;
}


// 加载训练数据
vector<xlsj> loadTrainData(const string& trainPath) {
    vector<xlsj> trainDataSet;
    for (const auto& entry : fs::directory_iterator(trainPath)) {
        const auto& filePath = entry.path().string();

        // 打印遍历到的文件名
        cout << "尝试加载图像: " << filePath << endl;

        if (fs::is_regular_file(entry) && fileExists(filePath)) {
            Mat image = imread(filePath);
            if (image.empty()) {
                cout << "无法加载图像 " << filePath << "!" << endl;
                continue; // 忽略无法加载的图像
            }

            Mat features = To01Matrix(image).reshape(1, 1); // 展平成一维特征向量
           // features.convertTo(features, CV_32F); // 转换特征矩阵为浮点型

            // 从文件名中提取标签
            int label = stoi(filePath.substr(trainPath.size(), filePath.find_last_of('-') - trainPath.size()));

            xlsj data;
            data.features = features;
            data.label = label;
            trainDataSet.push_back(data);
        }
        else {
            cout << "文件 " << filePath << " 不是常规文件或不存在!" << endl;
        }
    }

    cout << "加载的训练数据数量: " << trainDataSet.size() << endl;
    return trainDataSet;
}


// 训练KNN模型
KNNModel trainKNN(const vector<xlsj>& trainDataSet, int k) {
    Mat featureMatrix, labelMatrix; // 特征与标签矩阵
    for (const auto& data : trainDataSet) {
        featureMatrix.push_back(data.features);
        labelMatrix.push_back(data.label);
    }

    // 检查特征和标签矩阵
    if (featureMatrix.empty() || labelMatrix.empty()) {
        cout << "特征矩阵或标签矩阵为空!" << endl;
        return { nullptr, -1 }; // 返回空指针
    }

    featureMatrix.convertTo(featureMatrix, CV_32F); // 转换特征矩阵为浮点型
    labelMatrix.convertTo(labelMatrix, CV_32S); // 转换标签矩阵为整数型

    Ptr<KNearest> knn = KNearest::create();
    knn->setDefaultK(k);
    knn->train(featureMatrix, ROW_SAMPLE, labelMatrix);

    cout << "KNN模型训练完成" << endl;
    return { knn, featureMatrix.cols };  // 返回 KNN 模型以及特征矩阵的列数
}

// 使用KNN进行识别
int recognizeDigit(const Ptr<KNearest>& knn, const Mat& testImage) {
    Mat features = To01Matrix(testImage).reshape(1, 1);//转01矩阵的特征
    features.convertTo(features, CV_32F); // 转换特征矩阵为浮点型
    Mat result;//结果
    Mat resultLabels;//结果标签
    Mat resultDistances;//结果距离
    knn->findNearest(features, 1, result, resultLabels, resultDistances);
    return (int)resultLabels.at<float>(0, 0);
}

int main() {
    // k值
    int k = 5;
    string n = "9";

    // 路径
    string testPath = R"(C:\cyuyan\KNNmain\data\test\)" + n + ".jpg";
    string trainPath = R"(C:\cyuyan\KNNmain\data\xl\)";
    // Mat src = imread(testPath);

    // 加载训练数据
    vector<xlsj> trainDataSet = loadTrainData(trainPath);
    if (trainDataSet.empty()) {
        cout << "没有训练数据!" << endl; // 查询训练数据是否存在
        return -1;
    }

    // 训练 KNN 模型
    KNNModel model = trainKNN(trainDataSet, k);

    if (!model.knn) {
        return -1; //判断trainKNN是否正常
    }

    // 加载测试图像
    if (!fileExists(testPath)) {
        cout << "测试文件 " << testPath << " 不存在!" << endl;
        return -1;
    }

    Mat testImage = imread(testPath);
    if (testImage.empty()) {
        cout << "无法加载图像" << testPath << "!" << endl;
        return -1;
    }

    // 进行识别
    Mat features = To01Matrix(testImage).reshape(1, 1); // 转01矩阵的特征
    features.convertTo(features, CV_32F); // 转换特征矩阵为浮点型

    // 判断特征数量与训练特征是否一样
    if (features.cols != model.numFeatures) {
        cout << "测试样本的特征数量与训练样本不匹配" << endl;
        return -1;
    }

    //namedWindow("test opencv setup", CV_WINDOW_AUTOSIZE);
    //imshow("test opencv setup", src);

    int res = recognizeDigit(model.knn, testImage);
    cout << "预测结果: " << res << endl;

    return 0;
}