В настоящее время методы кластерного
В настоящее время методы кластерного анализа являются востребованными в огромном количестве прикладных задач разных областей науки и техники. Сама область кластеризации, несмотря на непрерывное развитие и появление новых приложений, имеет прочную теоретическую базу и подтвержденные результаты. Изначально постановки задач кластеризации и классификации очень близки, основное отличие состоит в том, что решение проблемы классификации требует отнести некий анализируемый объект к наперед заданному классу, а в случае кластеризации такие классы необходимо породить на основе свойств исследуемых объектов. Не случайно поэтому в машинном обучении кластер-анализ называют обучением без учителя.
Ключевым понятием кластер-анализа является сходство объектов, которое, как правило, выражается математически посредством меры (метрики) близости. На основе значения этой меры делается вывод о близости объектов и принимается решение об их принадлежности одному кластеру. Несмотря на то, что человеку привычнее воспринимать объектно-признаковое описание данных, в ходе кластер-анализа такое представление обычно теряется, его заменяет матрица сходства, например, объектов. Да и в самих кластерах общее признаковое описание составляющих их объектов явно не выражено. А это приводит к появлению абсурдных классов объектов, например, хорошо известна цепочка слов превращающих "муху" в "слона". Оказывается, некоторые методы кластеризации работают таким образом, что "мухи" и "слоны" оказываются в одном кластере. Помимо этого, не ясно, что общего может быть между огурцом и ботинком, окажись они объектами некоторого кластера. Но в терминах признакового описания мы можем выяснить, что огурец такой же шершавый, как и ботинок из крокодиловой кожи, да и цветом не отличается.
Приведенные примеры кажутся забавными, но в реальных задачах, где цена ошибочного разбиения на классы велика, а невозможность интерпретации результатов экспериментов грозит провалом исследований, такие недостатки методов кластеризации могут иметь существенное значение. Например, при решении задачи поиска документов-дубликатов для Web-страниц, с которой вполне успешно справляются поисковые системы, такие как Google или Yandex, в одном кластере могут оказаться совершенно непохожие документы. К этому приводит тот факт, что существует цепочка документов, в которой каждый документ сходен в чем-то с соседним, но сходство это не транзитивно, а потому общее признаковое описание таких документов при вычислении сходства на каждом шаге не учитывается. В результате страдает пользователь поисковой системы, от которого скрыты эти неверно выявленные нечеткие дубликаты, и поэтому поиск рискует оказаться нерелевантным.
Существует широкий спектр задач, в которых требуется выявлять кластеры с сохранением объектно-признакового описания данных. Это задачи выявления групп генов, обладающих общими свойствами, в биоинформатике, поиск групп посетителей со схожими интересами для рекомендательных систем, выявление интернет-сообществ, научных сообществ, задача анализа социальных сетей, построение автоматических каталогов и рубрикаторов в информационных системах, поиск документов-дубликатов.
Методы кластеризации, разработанные для этих целей, лежат в области кластер-анализа и получили свое собственное название — бикластеризация. Приставка би- указывает на двукомпонентность кластеров, выявляемых методами бикластеризации. Например, для генетических данных первым компонентом такого кластера является множество генов, а вторым — множество экспериментов, в которых они проявляли себя сходным образом. Термин "бикластеризация" впервые упомянут в работе[], и хотя похожие формулировки и методы встречались ранее (см. [] ), мы, тем не менее, будем использовать это собирательное название для всей группы методов, описываемых в данной работе, которые применяются для построения таких двукомпонентных кластеров.
В связи с вышеизложенным, основная цель обзора состоит в том, чтобы описать состояние дел в разных областях исследований, в которых нашли применение методы бикластеризации, выявить такие методы, выработать единые принципы их оценки, построить их адекватную классификацию. А также определить те из них, которые подходят для решения задач анализа интернет-данных (Web-mining), а именно выявления групп посетителей сайтов со сходными интересами или поведением, построения таксономий аудитории сайтов, а также задач анализа социальных сетей в Интернете и поиска нечетких веб-дубликатов. Отправной точкой такого исследования является прикладная математическая дисциплина Формальный Анализ Понятий (ФАП) [].
В рамках этой области сформулировано математическое определение формальных понятий, описано построение их иерархий. Исходно формальное понятие является парой вида (объем, содержание), где под объемом понимается некоторое множество объектов, а под содержанием — множество их общих признаков. Как видим, это определение напоминает описание бикластера. Исходные данные в ФАП представляются в виде объектно-признаковой матрицы, состоящей из нулей и единиц, а формальным понятием является максимальный прямоугольник такой матрицы, заполненный единицами. Это означает, что данное подмножество объектов обладает всеми признаками некоторого подмножества признаков.
Далее для такого множества понятий строится их иерархия, представляющая собой полную решетку, называемую решеткой понятий. Существует ряд работ, исследующих возможности "ослабления" требований к определению формального понятия, например, шумоустойчивые понятия (в смысле []). Необходимость такого рода ослаблений вызвана жесткой структурой формальных понятий, требующей наличия всех признаков из содержания понятия у объектов его объема, однако в случае наличия шума возможны "выпадения" некоторых признаков из содержания понятия.
В работах [,] предложен подход, использующий нечеткие решетки понятий, в котором значения исходных данных лежат в диапазоне [0, 1]. Причина, по которой целесообразно использование нечетких решеток — возможность более точного описания исходных данных, например, частоты посещения пользователем веб-сайта. Еще одним желательным требованием является сокращение числа таких бикластеров, так как при применении подхода ФАП их количество экспоненциально растет от размера входа. Отчасти проблема порождения большого числа формальных понятий решена путем введения индекса устойчивости формального понятия []. В этом случае из множества порожденных понятий отбираются те из них, для которых индекс устойчивости превышает некоторый заданный порог. Проблемы отбора релевантных задаче формальных понятий (бикластеров) также обсуждаются в рамках работы.
Что касается моделей "бокс-кластеризации", описанных в [], то для них характерно наличие сходного подхода и параметров, которые используются для выявления шумоустойчивых понятий []. Для моделей этого типа также характерно наличие перекрытий или пересечений бикластеров, степень которых оказывается существенной при решении ряда задач. В задачах бикластеризации, решаемых генетиками, используется похожий аппарат, но не всегда значения входной матрицы являются булевыми, как в работе [], в большинстве случаев они положительные вещественные (например, метод OPSM [] ). Это, в свою очередь, приводит к использованию статистических свойств данных при построении моделей (см. []). У большинства из этих методов, применяемых в биоинформатике, имеются похожие недостатки, например, проблема определения числа кластеров, проблема локального оптимума вследствие использования жадной стратегии поиска [].
Отдельно стоят методы спектральной кластеризации, которые изначально опираются на спектральные свойства матричного представления графа связей между объектами. В последнее время эти методы активно применяются в Интернет-маркетинге, где связи "рекламодатели-слова" представлены двудольным графом [] и помогают отыскивать потенциальных рекламодателей среди тех, кто не использует некоторые из слов, что купили их конкуренты. Фактически, эти методы искусственно адаптированы для задачи бикластеризации, поскольку для найденных кластеров приходится восстанавливать их объектно-признаковую структуру (т.е. бикластер).
Для большинства методов, происходящих не из сообщества ФАП, характерно отсутствие иерархии порожденных кластеров, что затрудняет их анализ исследователем. В рамках работы будет предпринята попытка установить возможность построения такой иерархии для остальных методов бикластеризации; такая иерархия предположительно будет носить решеточный или полурешеточный характер.
Исследователями вне ФАП также не используется аппарат ассоциативных правил, являющихся ключевыми в Data Mining при поиске признаковых зависимостей. Ассоциативные правила можно порождать на признаковых описаниях бикластеров, предполагается проведение соответствующих экспериментов. Помимо исследователей, использующих аппарат ассоциативных правил, в Data Mining существует сообщество FIMI (Frequent Itemset Mining Implementation), изучающее проблемы поиска частых (замкнутых) множеств признаков в больших базах данных. Отметим, что замкнутые множества признаков являются в точности содержаниями формальных понятий. Поэтому, как модель бикластеризации, методы FIMI будут включены в обзор.
Максимальные замкнутые множества признаков составляют только часть замкнутых, а потому их можно рассматривать в качестве альтернативы способам сокращения числа формальных понятий для модели ФАП. Еще одним из способов такого сокращения является использование решеток-айсбергов, предложенных в [], этот подход аналогичен отбору ассоциативных правил в Data Mining по порогу величины поддержки.
В соответствии с целью исследования были поставлены следующие задачи:
В рамках работы не оставлены без внимания системы поиска бикластеров, приводится их обзор. В частности, это системы
Обзор состоит из введения, пяти разделов, заключения и списка литературы.
В разделе — "Бикластеризация" описана одноименная задача, указано на ее ключевую роль в анализе данных генетической экспрессии. Приводятся основания для классификации методов и моделей бикластеризации. Определяются типы бикластеров, их структура, стратегии поиска алгоритмов и области значений исходных данных. Построена решеточная таксономия методов бикластеризации.
В разделе — "Методы и модели бикластеризации" приводится обзор различных подходов анализа данных, учитывающих их объектно-признаковый характер. Даны основные определения теории решеток и ФАП. Показана связь ассоциативных правил с бикластерами определенного типа.
Раздел — "Программные средства бикластеризации" содержит краткий обзор программного обеспечения, которое призвано решать задачи бикластеризации в различных предметных областях.
Раздел — "Прикладные задачи" представляет собой краткий обзор основных областей применения алгоритмов бикластеризации с указанием библиографии и пригодных для решения соответсвующих задач методов.
Раздел — "Эксперименты на массивах Интернет-данных" описывает результаты применения изучаемых подходов к решению задач поиска документов-дубликатов в Интернете, выявления Интернет-сообществ пользователей на основе статистики посещаемости сайтов и рекомендаций в системах контекстной рекламы.
