C++ 中的大数问题存在余弦相似性

Question

我正在写这个函数

double long CosineDistance(const vector<unsigned long>& a,const vector<unsigned long>& b){
  double long num = 0.0, den1 = 0.0, den2 = 0.0 ;
    for(int i = 0; i < a.size(); ++i) {
     num+=a[i]*b[i] ;
     den1+=a[i]*a[i] ;
     den2+=b[i]*b[i] ;
     } 
return num/(sqrt(den1)*sqrt(den2));
}

并且它可以像预期的那样用小数字工作：

即通过 {1,3,8} 和 {5,4,9} returns 0.936686（正确）

现在我正在构建的项目使用大数字（它们是散列字符串）并使用像

这样的数字

{3337682107,92015386,2479056,2478761,4153082938}

和

{104667454,92015386,150359366,2225484100,2479056}

它 returns me 1，根据 WolframAlpha，我认为这是 0.968597 的近似值。

已经检查过溢出但没有发生。

有办法解决这个问题吗？

谢谢

Answer 1

有几个地方可能会失去精度。

当两个非常大的无符号长整数相乘时，它可能会溢出。
将unsigned long 转换为long double 时，基本上可以忽略低位。（截断）
当添加两个 long double 时，其中一个比另一个大足够数量级，较小的将基本上被忽略。如果只是大了几个数量级，那么小的低位基本上会被忽略。

在你的例子中，计算并没有损失多少精度，1 vs .95 相对来说已经很接近了。如果您需要计算完全不丢失精度，一种方法是使用像 boost::multiprecision 这样的 bignum 库。您可以不在代码中使用 long double，而是在该库中使用像 cpp::rational 这样的无限精度有理数。然后在求平方根的时候转成long double

如果这些数字像您所说的那样是字符串的哈希值，并且这些值本身并没有那么重要，（大概您只是想对它们进行聚类之类的？）那么您可以做的一件事是选择一个输出较小数字的散列函数，或者 mod 这些数字只有 6 位长。这将大大降低完全失去精度的可能性。

Answer 2

当您计算两个向量 a 和 b 之间的余弦相似度时，以下内容成立：

CosineDistance(a*x,b*x) == CosineDinstance(a,b);

对于任何数字 x（但不是 0）。因此，您可以简单地使用双精度和适当的比例因子 x 来避免溢出。

Answer 3

{3337682107,92015386,2479056,2478761,4153082938}的平方和大于2^64，这似乎是double long尾数的典型最大尺寸。假设是这种情况，您将获得与使用会溢出的无符号长整型相同的精度。

Answer 4

我使用 Matlab 和 C++ (x64 VC2013) 检查了这个，对于你的 "big numbers" 案例，我得到的答案是 0.0314034 而不是 0.968597。我将原始数字用作 double 而不是从 int 转换为 double.

这是我检查的方式。

#include <cmath>
#include <vector>
#include <iostream>
using namespace std;

double CosineDistance(const vector<double> &a, const vector<double> &b);
long double CosineDistance2(const vector<long double> &a, const vector<long double> &b);
long double Cos2(const vector<unsigned long> &a, const vector<unsigned long> &b);
long double Cos3(const vector<unsigned long> &a, const vector<unsigned long> &b);

int main(int argc, char * argv[]){

    vector<double> a = { 1, 3, 8 };
    vector<double> b = { 5, 4, 9 };

    double v1 = CosineDistance(a, b);

    vector<double> a2 = { 3337.682107, 92.015386, 2.479056, 2.478761, 4153.082938 };
    vector<double> b2 = { 104.667454, 92.015386, 150.359366, 2225.484100, 2.479056 };

    double v2 = CosineDistance(a2, b2);

    vector<double> a3 = { 333.7682107, 9.2015386, .2479056, .2478761, 415.3082938 };
    vector<double> b3 = { 10.4667454, 9.2015386, 15.0359366, 222.5484100, .2479056 };

    double v3 = CosineDistance(a3, b3);

    vector<double> a4 = { .1, .3, .8 };
    vector<double> b4 = { .5, .4, .9 };

    double v4 = CosineDistance(a4, b4);

    vector<long double> a5 = { 3337682107, 92015386, 2479056, 2478761, 4153082938 };
    vector<long double> b5 = { 104667454, 92015386, 150359366, 2225484100, 2479056 };

    long double v5 = CosineDistance2(a5, b5);

    vector<unsigned long> a6 = { 3337682107, 92015386, 2479056, 2478761, 4153082938 };
    vector<unsigned long> b6 = { 104667454, 92015386, 150359366, 2225484100, 2479056 };

    long double v6 = Cos2(a6, b6);
    long double v7 = Cos3(a6, b6);

    cout << v1 << endl;
    cout << v2 << endl;
    cout << v3 << endl;
    cout << v4 << endl;
    cout << v5 << endl;
    cout << v6 << endl;
    cout << v7 << endl;

    return 0;
}

double CosineDistance(const vector<double> &a, const vector<double> &b){

    double num(0.0), den1(0.0), den2(0.0);

    for (unsigned int i = 0; i < a.size(); ++i){
        num += a[i] * b[i];
        den1 += a[i] * a[i];
        den2 += b[i] * b[i];
    }

    double res = num / (sqrt(den1) * sqrt(den2));

    return res;
}

long double CosineDistance2(const vector<long double> &a, const vector<long double> &b){

    long double num(0.0), den1(0.0), den2(0.0);

    for (unsigned int i = 0; i < a.size(); ++i){
        num += a[i] * b[i];
        den1 += a[i] * a[i];
        den2 += b[i] * b[i];
    }

    long double res = num / (sqrt(den1) * sqrt(den2));

    return res;
}

long double Cos2(const vector<unsigned long> &a, const vector<unsigned long> &b){

    vector<long double> ad(a.size());
    vector<long double> bd(b.size());
    for (unsigned int i = 0; i < a.size(); ++i){
        ad[i] = static_cast<long double>(a[i]);
        bd[i] = static_cast<long double>(b[i]);
    }

    long double num(0.0), den1(0.0), den2(0.0);

    for (unsigned int i = 0; i < a.size(); ++i){
        num += ad[i] * bd[i];
        den1 += ad[i] * ad[i];
        den2 += bd[i] * bd[i];
    }

    long double res = num / (sqrt(den1) * sqrt(den2));

    return res;
}

long double Cos3(const vector<unsigned long> &a, const vector<unsigned long> &b){

    long double num(0.0), den1(0.0), den2(0.0);

    for (unsigned int i = 0; i < a.size(); ++i){
        num += a[i] * b[i];
        den1 += a[i] * a[i];
        den2 += b[i] * b[i];
    }

    long double res = num / (sqrt(den1) * sqrt(den2));

    return res;
}

输出为：

请注意，当我专门从 unsigned long 转换为 long double 时，我的答案与 Matlab 和我的其他 C++ 数字一致。

C++ 中的大数问题存在余弦相似性

Big numbers in c++ issue in cosine similarity

c++

precision

long-integer