Описание алгоритма

Алгоритм BiMax следует стратегии "разделяй и властвуй". Первоначально алгоритм определяет области матрицы

, содержащие только 0, и затем исключает их из дальнейшего рассмотрения. Эта стратегия особенно выигрышна при условии разреженных данных, получение которых из исходных наборов зависит от выбора порога отсечения. В экспериментах, представленных в статье[13], для всех наборов данных доля 1-значений не превышает 6%.

Идея, лежащая в основе алгоритма, состоит в следующем: исходная матрица

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

. Рекурсия прекращается, если текущая матрица, представляющая собой бикластер, содержит только единицы.

Для обработки подматрицы

необходимы специальные операции, чтобы гарантировать максимальность по вложению бикластеров. Проблема возникает в том случае, если

содержит части бикластеров, найденных в

; поэтому необходимо проводить проверку того, что алгоритм рассматривает только те бикластеры, которые расширяются в

. С этой целью вводится параметр

, который содержит множества столбцов, ограничивающие число допустимых бикластеров. Бикластер

допустим, если

обладает одним или несколькими столбцами с каждым множеством столбцов

из

, т.е.

Алгоритм 2.2.1. BiMax(E)

Содержание раздела