Java代码优化会导致数字不准确和错误

Question

我正在尝试用Java 实现Fuzzy C-Means算法的一个版本,我试图通过计算一次只能计算一次的所有内容来进行一些优化.

这是一个迭代算法,关于矩阵的更新,像素x簇成员矩阵U(行中值的总和必须为1.0),这是我想要优化的更新规则:

其中x是矩阵的元素X(像素x特征),v属于矩阵V (簇x特征).并且m是一个参数,范围从1.1to infinity和c是簇的数量.使用的距离是欧几里德范数.

如果我必须以平庸的方式实施这个公式,我会这样做:

    for(int i = 0; i < X.length; i++)
    {
        int count = 0;
        for(int j = 0; j < V.length; j++)
        {
                double num = D[i][j];
                double sumTerms = 0;
                for(int k = 0; k < V.length; k++)
                {
                     double thisDistance = D[i][k];
                     sumTerms += Math.pow(num / thisDistance, (1.0 / (m - 1.0)));
                }
                U[i][j] = (float) (1f / sumTerms);
         }
     }

通过这种方式,我已经完成了一些优化,我预先计算了它们之间所有可能的平方距离X并将V它们存储在一个矩阵中,D但这还不够,因为我要循环V两次,导致两个嵌套循环.看一下公式,分数的分子与总和无关,所以我可以独立地计算分子和分母,分母只能为每个像素计算一次.所以我找到了这样的解决方案:

    int nClusters = V.length;
    double exp = (1.0 / (m - 1.0));
    for(int i = 0; i < X.length; i++)
    {
        int count = 0;
        for(int j = 0; j < nClusters; j++)
        {
             double distance = D[i][j];
             double denominator = D[i][nClusters];
             double numerator = Math.pow(distance, exp);
             U[i][j] = (float) (1f / (numerator * denominator));
        }
     }

在我计算D距离时,我将分母预先计算到矩阵的附加列中:

    for (int i = 0; i < X.length; i++)
    {
        for (int j = 0; j < V.length; j++)
        {
            double sum = 0;
            for (int k = 0; k < nDims; k++)
            {
                final double d = X[i][k] - V[j][k];
                sum += d * d;
            }

            D[i][j] = sum;
            D[i][B.length] += Math.pow(1 / D[i][j], exp);
        }
    }

通过这样做,我遇到'平庸'计算和第二个计算之间的数值差异,导致不同的数值U(不是在第一次迭代,但很快).我猜这个问题是取幂数非常小到高值(U范围从0.0到1.0 的元素,而expfor m = 1.1,是10)导致非常小的值,而通过除以分子和分母,然后指数结果似乎在数字上更好.问题是它涉及更多的操作.

UPDATE

我得到的一些价值观ITERATION 0:

这是D未优化的矩阵的第一行:

384.6632 44482.727 17379.088 1245.4205

这是D优化方式的矩阵的第一行(注意最后一个值是预先计算的分母):

384.6657 44482.7215 17379.0847 1245.4225 1.4098E-26

这是U未优化的第一行:

0.99999213 2.3382613E-21 2.8218658E-17 7.900302E-6

这是U优化的第一行:

0.9999921 2.338395E-21 2.822035E-17 7.900674E-6

ITERATION 1:

这是D未优化的矩阵的第一行:

414.3861 44469.39 17300.092 1197.7633

这是D优化方式的矩阵的第一行(注意最后一个值是预先计算的分母):

414.3880 44469.38 17300.090 1197.7657 2.0796E-26

这是U未优化的第一行:

0.99997544 4.9366603E-21 6.216704E-17 2.4565863E-5

这是U优化的第一行:

0.3220644 1.5900239E-21 2.0023086E-17 7.912171E-6

最后一组值表明它们由于传播的错误而非常不同(我仍然希望我犯了一些错误),甚至违反了这些值的总和必须为1.0的约束.

难道我做错了什么？有没有可能的解决方案来使代码优化和数值稳定？任何建议或批评将不胜感激.

Answer 1

这个问题与浮点稳定性无关.

您在第二次和后续迭代中得到错误的分母值,因为您在累积总和之前忘记清除其单元格.

迭代1的正确分母是6.697905e-27,差不多2.0796E-26 - 1.4098E-26.