C++ LSH 欧氏距离 KNN 代码

以下是C++实现的基于LSH和欧氏距离的KNN算法代码：

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cmath>
#include <algorithm>

using namespace std;

// 定义向量维度
const int DIMENSION = 20;

// 定义哈希函数的个数和每个哈希函数的长度
const int HASH_FUNC_NUM = 5;
const int HASH_FUNC_LEN = 4;

// 定义KNN算法中的K值
const int K = 5;

// 定义数据集中的向量数量
const int DATASET_SIZE = 1000;

// 定义每个哈希函数的系数和偏移量
int a[HASH_FUNC_NUM][DIMENSION], b[HASH_FUNC_NUM];

// 定义哈希表，键为哈希值，值为对应的向量编号列表
unordered_map<int, vector<int>> hash_table[HASH_FUNC_NUM];

// 计算两个向量之间的欧氏距离
double euclidean_distance(const vector<double>& v1, const vector<double>& v2) {
    double distance = 0.0;
    for (int i = 0; i < DIMENSION; i++) {
        distance += pow(v1[i] - v2[i], 2);
    }
    return sqrt(distance);
}

// 初始化哈希函数的系数和偏移量
void init_hash_function() {
    for (int i = 0; i < HASH_FUNC_NUM; i++) {
        for (int j = 0; j < DIMENSION; j++) {
            a[i][j] = rand() % 100 + 1;    // 生成1~100之间的随机数
        }
        b[i] = rand() % 100 + 1;
    }
}

// 计算向量v的哈希值
int calc_hash_value(const vector<double>& v, int hash_func_index) {
    int hash_value = 0;
    for (int i = 0; i < DIMENSION; i++) {
        hash_value += a[hash_func_index][i] * v[i];
    }
    hash_value += b[hash_func_index];
    return hash_value;
}

// 建立LSH索引
void build_lsh_index(const vector<vector<double>>& dataset) {
    for (int i = 0; i < DATASET_SIZE; i++) {
        for (int j = 0; j < HASH_FUNC_NUM; j++) {
            int hash_value = calc_hash_value(dataset[i], j);
            hash_table[j][hash_value].push_back(i);
        }
    }
}

// 在哈希表中查找与查询向量v相似的向量
vector<int> find_similar_vectors(const vector<double>& v) {
    vector<int> similar_vectors;
    unordered_map<int, int> cnt;    // 用于统计每个向量出现的次数
    for (int i = 0; i < HASH_FUNC_NUM; i++) {
        int hash_value = calc_hash_value(v, i);
        for (int j = 0; j < hash_table[i][hash_value].size(); j++) {
            int vector_index = hash_table[i][hash_value][j];
            cnt[vector_index]++;
        }
    }
    for (auto it = cnt.begin(); it != cnt.end(); it++) {
        if (it->second >= HASH_FUNC_NUM) {    // 如果某个向量在所有哈希函数中都出现了，则认为它与查询向量相似
            similar_vectors.push_back(it->first);
        }
    }
    return similar_vectors;
}

// 使用欧氏距离计算KNN
vector<int> knn(const vector<vector<double>>& dataset, const vector<double>& query) {
    vector<int> similar_vectors = find_similar_vectors(query);
    vector<pair<double, int>> distances;
    for (int i = 0; i < similar_vectors.size(); i++) {
        double distance = euclidean_distance(dataset[similar_vectors[i]], query);
        distances.push_back(make_pair(distance, similar_vectors[i]));
    }
    sort(distances.begin(), distances.end());
    vector<int> knn_vectors;
    for (int i = 0; i < K; i++) {
        knn_vectors.push_back(distances[i].second);
    }
    return knn_vectors;
}

int main() {
    // 生成随机数据集
    vector<vector<double>> dataset(DATASET_SIZE, vector<double>(DIMENSION));
    for (int i = 0; i < DATASET_SIZE; i++) {
        for (int j = 0; j < DIMENSION; j++) {
            dataset[i][j] = rand() % 100 + 1;
        }
    }

    // 初始化哈希函数的系数和偏移量
    init_hash_function();

    // 建立LSH索引
    build_lsh_index(dataset);

    // 查询向量
    vector<double> query(DIMENSION);
    for (int i = 0; i < DIMENSION; i++) {
        query[i] = rand() % 100 + 1;
    }

    // 计算KNN
    vector<int> knn_vectors = knn(dataset, query);

    // 输出KNN结果
    cout << "query vector: ";
    for (int i = 0; i < DIMENSION; i++) {
        cout << query[i] << " ";
    }
    cout << endl;
    cout << "KNN vectors: ";
    for (int i = 0; i < knn_vectors.size(); i++) {
        cout << knn_vectors[i] << " ";
    }
    cout << endl;

    return 0;
}

说明：

- 程序中使用了vector和unordered_map等STL容器，需要包含头文件```<vector>```和```<unordered_map>```。
- 程序中用到了随机数生成函数rand()，需要包含头文件```<cstdlib>```。
- 程序中使用的是欧氏距离，计算时需要引入数学函数库cmath，需要包含头文件```<cmath>```。
- 在实际应用中，可以根据具体情况调整哈希函数的个数、长度和系数等参数。