Как найти наибольшую биклику, допуская неполное совпадение?

Дан двумерный массив булевых значений. Строки это аккаунты, столбцы – различные свойства каждого аккаунта: «состоит в группе А», «совершал покупки» и т.п.
Надо найти максимальную биклику (полный двудольный граф) – т.е. тот наибольший набор аккаунтов×свойств, где свойства true
Задача NP-полная, и с её реализацией я кое-как в лоб разобрался. Но теперь два усложнения.
хочется сравнивать «нечётко»: допустить вхождение в биклику аккаунтов, у которых недостаёт 1-2 (задаётся параметром нечеткости) свойств. Лучше посчитаем, как будто они у них true, если это позволит включить их в наибольший набор. Неужели для каждой найденной клики нужно зановой перебрать все данные, проверяя гипотезы о каждом свойства, которое можно бы добавить? Подскажите алгоритм. размер исследуемых наборов растёт. Может, вы прошли курс Machine Learning или прочие BigData – посоветуйте методики поиска, альтернативные полному перебору? Я краем уха слышал, есть такие, эффективно работающие на больших объёмах, пусть, дающие приблизительный результат – объясните, пожалуйста, «на пальцах», как их можно применить к задаче?
Иллюстрации проблемы

Синие ячейки true, белые false. Нечёткая максимальная биклика обведена красным – в каждой строке добавили по три «фантомных» ячейки (серые). Порядок строк/столбцов не имеет значения. Максимальная биклика вовсе не обязательно будет сплошным прямоугольником, это только для иллюстрации.

Например, здесь светло-синие ячейки были отброшены на этапе оптимизации, а оставшиеся формируют две би-клики: строки (3,5) × столбцы (1,3,4,6) и (3,4,5)×(1,3). Однако, если включить fuzziness на 2, то можно добавив в 4-й строке столбцы (4,6), а в строках (3,5) столбец 5 – получить ещё большую биклику (3,4,5)×(1,3,4,5,6).

Ответ

В случае нечеткого определения понятия "полнота" возможны серьезные отклонения в определении "максимальной" биклики в зависимости от метрики, по которой оценивается максимум, так как наличие ненулевого числа false в строках и столбцах биклики позволяет выбирать метрику так, что "максимальными" для каждой метрики будут разные биклики.
Например, в случае метрики "превышение true над false на всей биклике" (количество заполненных против количества незаполненных клеток) и нечеткости 3 на примере с прямоугольником максимумом окажется биклика из столбцов 1,2,6,7 прямоугольника и всех его строк, с метрикой +8. При использовании метрики "всего истин" (число заполненных прямоугольников) выделенный прямоугольник является максимальным. Таким образом, для задачи с нечеткостью метрику нужно жестко задать, причем в зависимости от метрики может варьироваться сам алгоритм выбора биклики.
В общм случае (если метрика линейно зависит от количества строк и столбцов, участвующих в биклике) подойдет жадный алгоритм захвата столбцов. Вначале сортируем столбцы по количеству строк с данным атрибутом, установленным в true, потом включаем в множество столбцов по очереди и смотрим изменение метрики. Для параметра нечеткости начальное рассмотрение должно включать минимум (параметр нечеткости)+1 столбцов, иначе биклика с нечеткостью захватит весь массив строк - этого нам явно не надо. После появления набора столбцов добавляем по одному так, чтобы промежуточное значение метрики возрастало. Количество строк в биклике будет убывать, так как не всегда у имеющихся строк будет true в новом столбце, и какие-то из них выпадут по причине превышения false предела нечеткости, в итоге либо добавим все, либо на каком-то этапе ни одной не получится добавить. Проверяем, удастся ли выкинуть хоть один столбец чтобы метрика полезла вверх, если да, выкидываем и продолжаем, пока изменение включения одного столбца не приведет к увеличению метрики. Выдаем её как локальный максимум. Для очистки совести можно рассмотреть наибольшую по метрике стартовую комбинацию из столбцов, не вошедших в найденную биклику и точно так же её обработать. Если сойдется к этому же набору, его выдаем, иначе проверяем, какая из найденных биклик больше, и если новая, проверяем ещё какую-нибудь комбинацию на случай нескольких локальных максимумов, пока либо не придем к уже найденному локальному максимуму, либо к меньшему, тогда возвращаем текущий локальный максимум как ответ.