C++ LSH knn代码

以下是使用 C++ 实现的 LSH knn 代码示例：

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

using namespace std;

// 定义向量类型
typedef vector<double> Vector;

// 计算欧几里得距离
double euclideanDistance(const Vector& v1, const Vector& v2) {
    double sum = 0.0;
    for (int i = 0; i < v1.size(); ++i) {
        sum += pow(v1[i] - v2[i], 2);
    }
    return sqrt(sum);
}

// 计算哈希值
int hashValue(const Vector& v, const Vector& r, double b) {
    int h = 0;
    for (int i = 0; i < v.size(); ++i) {
        h += (v[i] * r[i] + b) >= 0 ? 1 << i : 0;
    }
    return h;
}

// LSH knn 函数
vector<int> lshKnn(const vector<Vector>& data, int k, int L, int m) {
    // 初始化随机向量
    default_random_engine generator;
    normal_distribution<double> distribution(0.0, 1.0);
    vector<vector<Vector>> r(L, vector<Vector>(k, Vector(m)));
    vector<vector<double>> b(L, vector<double>(k));
    for (int i = 0; i < L; ++i) {
        for (int j = 0; j < k; ++j) {
            for (int l = 0; l < m; ++l) {
                r[i][j].push_back(distribution(generator));
            }
            b[i][j] = distribution(generator) * m;
        }
    }

    // 建立哈希表
    unordered_map<int, vector<int>> hashTable;
    for (int i = 0; i < data.size(); ++i) {
        for (int j = 0; j < L; ++j) {
            int h = hashValue(data[i], r[j], b[j][0]);
            hashTable[h].push_back(i);
        }
    }

    // 搜索 k 近邻
    vector<int> knn(data.size(), -1);
    vector<double> knnDist(data.size(), numeric_limits<double>::max());
    for (int i = 0; i < data.size(); ++i) {
        for (int j = 0; j < L; ++j) {
            int h = hashValue(data[i], r[j], b[j][0]);
            for (int idx : hashTable[h]) {
                double dist = euclideanDistance(data[i], data[idx]);
                if (dist < knnDist[i]) {
                    knn[i] = idx;
                    knnDist[i] = dist;
                }
            }
        }
    }

    return knn;
}

int main() {
    // 定义数据集
    vector<Vector> data = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {10, 11, 12}};

    // 设置参数
    int k = 2;  // k 近邻数量
    int L = 2;  // 哈希表数量
    int m = 3;  // 随机向量长度

    // 调用 LSH knn 函数
    vector<int> knn = lshKnn(data, k, L, m);

    // 输出结果
    for (int i = 0; i < data.size(); ++i) {
        cout << "data " << i << " is closest to data " << knn[i] << endl;
    }

    return 0;
}

注：以上代码仅作示例，实际应用中需要根据具体场景选择合适的距离函数、哈希函数等。