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

#алгоритм #графы #big_data

Дан двумерный массив булевых значений. Строки это аккаунты, столбцы – различные свойства
каждого аккаунта: «состоит в группе А», «совершал покупки» и т.п.

Надо найти максимальную биклику (полный двудольный граф) – т.е. тот наибольший набор
аккаунтов×свойств, где свойства 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).
    

Ответы

Ответ 1

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

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

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