Экспериментальный анализ алгоритмов бикластеризации

В данной главе представлены экспериментальные результаты сравнения трёх алгоритмов бикластеризации — BBox, GreedyBBox и алгоритма спектрального разложения двудольного графа (Spectral).

Мемоизация в BBox

Как было описано в предыдущей главе, для ускорения метода BBox было использовано хеш-множество, хранящее промежуточные и финальные бикластеры. В данном разделе мы представляем анализ достигнутых с помощью техники мемоизации результатов.

Таблица 2. Ускорение алгоритма BBox за счёт техники мемоизации.

Таблица 2 показывает общее внутренних количество итераций по всем входным строкам, которое потребовалось алгоритму BBox (без мемоизации) для нахождения бикластеров. Столбец «сохранённые итерации» — показывает количество внутренних итераций, которое удалось избежать за счёт мемоизации. В качестве входных данных алгоритму подавались квадратные матрицы размером от 50 до 250 строк и столбцов. Каждый элемент матрицы генерировался с помощью генератора псевдослучайных числе из полуинтервала [0, 1) в случае вещественных матриц и из множества {0, 1} в случае бинарных матриц.

Из таблицы видно, что количество сохранённых итераций много меньше общего числа выполненных итераций. Вдобавок, отношение этих величин падает с ростом размера входной матрицы: для входной матрицы размеров 250×250 сохранённые итерации составляют всего 0.3% от общего числа итераций как для вещественной матрицы, так и для бинарной.

Нужно также заметить, что в результате проведённых экспериментов, количество сохранённых итераций оказалось равным порядку входной матрицы минус один. Это связано с тем, что алгоритм для всех входных строк матрицы сходился к одному и тому же оптимальному бикластеру. При этом «сохранённой» итерацией оказывалась всегда последняя, то есть алгоритму не приходилось проверять, является ли полученный бикластер оптимальным, так как он был уже получен для первой начальной строки и содержался в хеш-множестве. Аналогичная ситуация наблюдалась и для «реальных» данных, то есть матриц релевантности и матриц схожести между ключевыми фразами. Несмотря на то, что для ключевых слов алгоритм находил более одного локально-оптимального бикластера, «сохранёнными» всегда оказывались финальные итерации для различных начальных строк.

Таким образом, можно сделать вывод, что запоминание финальных и промежуточных (неоптимальных) бикластеров даёт очень слабый прирост в эффективности, что не оправдывает выделения дополнительной памяти на хеш-множество, объём которого может расти пропорционально общему числу итераций. С другой стороны, можно ограничиться запоминанием лишь финальных бикластеров, что может дать незначительный прирост по скорости работы алгоритма.

В любом случае, алгоритм остаётся экспоненциальным по сложности в худшем случае, поэтому жадный алгоритм, кажется хорошей альтернативой при анализе матриц крупного размера.