О формальной постановке задач поиска сгущений в разреженных булевых матрицах

В огромном числе прикладных задач интеллектуального анализа данных, таких как исследование генной экспрессии и тканей, текстовой и веб-информации, рыночных корзин, клиентских сред, входная информация естественным образом представляется в виде двумерной матрицы «субъекты–объекты» («клиенты–сервисы»). Основной целью в рамках указанных областей является так называемая бикластеризация данных, т. е. выделение групп в определенном смысле схожих строк и столбцов. Немалая часть таких задач характеризуется сильной разреженностью соответствующих матриц. Важным аспектом бикластеризации является поиск в некотором смысле плотных подматриц в булевых матрицах, что является основной целью данного исследования. В работе производится формализация предметной области в рамках алгебраического подхода, описаны системы универсальных и локальных ограничений, предложены и доказаны соответствующие критерии разрешимости рассматриваемых задач.