9

私はJavaでFuzzyC-Meansアルゴリズムのバージョンを実装しようとしています。また、一度だけ計算できるすべてのものを一度だけ計算することによって、いくつかの最適化を実行しようとしています。

これは反復アルゴリズムであり、マトリックスの更新に関して、ピクセルxクラスターメンバーシップマトリックスU（行の値の合計は1.0である必要があります）、これは最適化する更新ルールです。

代替テキスト

ここで、xは行列の要素X（ピクセルx特徴）であり、vは行列V （クラスターx特徴）に属します。Andは、からまでmの範囲のパラメーターであり、クラスターの数です。使用される距離はユークリッドノルムです。1.1infinityc

この式を平凡な方法で実装する必要がある場合は、次のようにします。

    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それらを行列に格納しましたが、 2回Dの要素を循環させて、2つのネストされたループを生成するため、それだけでは不十分です。V式を見ると、分数の分子は合計に依存しないため、分子と分母を個別に計算でき、分母はピクセルごとに1回だけ計算できます。だから私はこのような解決策に到達しました：

    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);
        }
    }

そうすることで、「banal」計算と2番目の計算の間に数値の違いが生じ、U（最初の反復ではなく、すぐに）の数値が異なります。問題は、非常に小さい数を高い値にべき乗することです（の要素はU0.0から1.0の範囲でありexp、の場合m = 1.1、はです10）は非常に小さい値になりますが、分子と分母を除算して結果をべき乗すると、数値的に良くなるために。問題は、それがはるかに多くの操作を伴うことです。

アップデート

私が得るいくつかの値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でなければならないという制約さえ違反していることを示しています。

私は何か間違ったことをしていますか？コードを最適化し、数値的に安定させるための可能な解決策はありますか？任意の提案や批判をいただければ幸いです。

4

1 に答える 1

8

この問題は、浮動小数点の安定性とは何の関係もありません。

合計を累積する前にセルをクリアするのを忘れたため、2回目以降の反復で分母の値が間違っています。

反復1の正しい分母は、、6.697905e-27つまりほぼ2.0796E-26 - 1.4098E-26です。

于 2011-01-09T18:54:28.090 に答える