Я пытаюсь реализовать версию алгоритма Fuzzy C-Means в Java, и я пытаюсь провести некоторую оптимизацию, вычисляя всего один раз все, что можно вычислить только один раз.
Это итерационный алгоритм, а в отношении обновления матрицы, пикселей x кластеров матрица членства U (сумма значений в строке должна быть 1,0), это правило обновления Я хочу оптимизировать:
, где x - элемент матрицы X ( пикселей x, особенности ), а v принадлежит матрице V ( кластеров x, особенности ). И m - это параметр, который варьируется от 1.1 до 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 и exp, для m = 1.1, составляет 10) приводит к очень маленьким значениям, тогда как деление числителя и знаменателя и THEN возведение в степень результата, по-видимому, лучше в численном отношении. Проблема в том, что он включает в себя гораздо больше операций.
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, нарушается.
Я что-то не так делаю? Есть ли возможное решение для оптимизации кода и его числовой стабильности? Будем благодарны за любые предложения или критику.