Методы бикластеризации для анализа интернет-данных

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

Ключевым понятием кластер-анализа является сходство объектов, которое, как правило, выражается математически посредством меры (метрики) близости. На основе значения этой меры делается вывод о близости объектов и принимается решение об их принадлежности одному кластеру. Несмотря на то, что человеку привычнее воспринимать объектно-признаковое описание данных, в ходе кластер-анализа такое представление обычно теряется, его заменяет матрица сходства, например, объектов. Да и в самих кластерах общее признаковое описание составляющих их объектов явно не выражено. А это приводит к появлению абсурдных классов объектов, например, хорошо известна цепочка слов превращающих "муху" в "слона". Оказывается, некоторые методы кластеризации работают таким образом, что "мухи" и "слоны" оказываются в одном кластере. Помимо этого, не ясно, что общего может быть между огурцом и ботинком, окажись они объектами некоторого кластера. Но в терминах признакового описания мы можем выяснить, что огурец такой же шершавый, как и ботинок из крокодиловой кожи, да и цветом не отличается.

Приведенные примеры кажутся забавными, но в реальных задачах, где цена ошибочного разбиения на классы велика, а невозможность интерпретации результатов экспериментов грозит провалом исследований, такие недостатки методов кластеризации могут иметь существенное значение. Например, при решении задачи поиска документов-дубликатов для Web-страниц, с которой вполне успешно справляются поисковые системы, такие как Google или Yandex, в одном кластере могут оказаться совершенно непохожие документы. К этому приводит тот факт, что существует цепочка документов, в которой каждый документ сходен в чем-то с соседним, но сходство это не транзитивно, а потому общее признаковое описание таких документов при вычислении сходства на каждом шаге не учитывается. В результате страдает пользователь поисковой системы, от которого скрыты эти неверно выявленные нечеткие дубликаты, и поэтому поиск рискует оказаться нерелевантным.

Существует широкий спектр задач, в которых требуется выявлять кластеры с сохранением объектно-признакового описания данных. Это задачи выявления групп генов, обладающих общими свойствами, в биоинформатике, поиск групп посетителей со схожими интересами для рекомендательных систем, выявление интернет-сообществ, научных сообществ, задача анализа социальных сетей, построение автоматических каталогов и рубрикаторов в информационных системах, поиск документов-дубликатов.

Методы кластеризации, разработанные для этих целей, лежат в области кластер-анализа и получили свое собственное название — бикластеризация. Приставка би- указывает на двукомпонентность кластеров, выявляемых методами бикластеризации. Например, для генетических данных первым компонентом такого кластера является множество генов, а вторым — множество экспериментов, в которых они проявляли себя сходным образом. Термин "бикластеризация" впервые упомянут в работе [57], и хотя похожие формулировки и методы встречались ранее (см. [37] ), мы, тем не менее, будем использовать это собирательное название для всей группы методов, описываемых в данной работе, которые применяются для построения таких двукомпонентных кластеров.

В связи с вышеизложенным, основная цель обзора состоит в том, чтобы описать состояние дел в разных областях исследований, в которых нашли применение методы бикластеризации, выявить такие методы, выработать единые принципы их оценки, построить их адекватную классификацию. А также определить те из них, которые подходят для решения задач анализа интернет-данных (Web-mining), а именно выявления групп посетителей сайтов со сходными интересами или поведением, построения таксономий аудитории сайтов, а также задач анализа социальных сетей в Интернете и поиска нечетких веб-дубликатов. Отправной точкой такого исследования является прикладная математическая дисциплина Формальный Анализ Понятий (ФАП) [33].

В рамках этой области сформулировано математическое определение формальных понятий, описано построение их иерархий. Исходно формальное понятие является парой вида (объем, содержание), где под объемом понимается некоторое множество объектов, а под содержанием — множество их общих признаков. Как видим, это определение напоминает описание бикластера. Исходные данные в ФАП представляются в виде объектно-признаковой матрицы, состоящей из нулей и единиц, а формальным понятием является максимальный прямоугольник такой матрицы, заполненный единицами. Это означает, что данное подмножество объектов обладает всеми признаками некоторого подмножества признаков.

Далее для такого множества понятий строится их иерархия, представляющая собой полную решетку, называемую решеткой понятий. Существует ряд работ, исследующих возможности "ослабления" требований к определению формального понятия, например, шумоустойчивые понятия (в смысле [19]). Необходимость такого рода ослаблений вызвана жесткой структурой формальных понятий, требующей наличия всех признаков из содержания понятия у объектов его объема, однако в случае наличия шума возможны "выпадения" некоторых признаков из содержания понятия.

В работах [14,15] предложен подход, использующий нечеткие решетки понятий, в котором значения исходных данных лежат в диапазоне [0, 1]. Причина, по которой целесообразно использование нечетких решеток — возможность более точного описания исходных данных, например, частоты посещения пользователем веб-сайта. Еще одним желательным требованием является сокращение числа таких бикластеров, так как при применении подхода ФАП их количество экспоненциально растет от размера входа. Отчасти проблема порождения большого числа формальных понятий решена путем введения индекса устойчивости формального понятия [49]. В этом случае из множества порожденных понятий отбираются те из них, для которых индекс устойчивости превышает некоторый заданный порог. Проблемы отбора релевантных задаче формальных понятий (бикластеров) также обсуждаются в рамках работы.

Что касается моделей "бокс-кластеризации", описанных в [56], то для них характерно наличие сходного подхода и параметров, которые используются для выявления шумоустойчивых понятий [19]. Для моделей этого типа также характерно наличие перекрытий или пересечений бикластеров, степень которых оказывается существенной при решении ряда задач. В задачах бикластеризации, решаемых генетиками, используется похожий аппарат, но не всегда значения входной матрицы являются булевыми, как в работе [13], в большинстве случаев они положительные вещественные (например, метод OPSM [16] ). Это, в свою очередь, приводит к использованию статистических свойств данных при построении моделей (см. [76]). У большинства из этих методов, применяемых в биоинформатике, имеются похожие недостатки, например, проблема определения числа кластеров, проблема локального оптимума вследствие использования жадной стратегии поиска [25].

Отдельно стоят методы спектральной кластеризации, которые изначально опираются на спектральные свойства матричного представления графа связей между объектами. В последнее время эти методы активно применяются в Интернет-маркетинге, где связи "рекламодатели-слова" представлены двудольным графом [88] и помогают отыскивать потенциальных рекламодателей среди тех, кто не использует некоторые из слов, что купили их конкуренты. Фактически, эти методы искусственно адаптированы для задачи бикластеризации, поскольку для найденных кластеров приходится восстанавливать их объектно-признаковую структуру (т.е. бикластер).

Для большинства методов, происходящих не из сообщества ФАП, характерно отсутствие иерархии порожденных кластеров, что затрудняет их анализ исследователем. В рамках работы будет предпринята попытка установить возможность построения такой иерархии для остальных методов бикластеризации; такая иерархия предположительно будет носить решеточный или полурешеточный характер.

Исследователями вне ФАП также не используется аппарат ассоциативных правил, являющихся ключевыми в Data Mining при поиске признаковых зависимостей. Ассоциативные правила можно порождать на признаковых описаниях бикластеров, предполагается проведение соответствующих экспериментов. Помимо исследователей, использующих аппарат ассоциативных правил, в Data Mining существует сообщество FIMI (Frequent Itemset Mining Implementation), изучающее проблемы поиска частых (замкнутых) множеств признаков в больших базах данных. Отметим, что замкнутые множества признаков являются в точности содержаниями формальных понятий. Поэтому, как модель бикластеризации, методы FIMI будут включены в обзор.

Максимальные замкнутые множества признаков составляют только часть замкнутых, а потому их можно рассматривать в качестве альтернативы способам сокращения числа формальных понятий для модели ФАП. Еще одним из способов такого сокращения является использование решеток-айсбергов, предложенных в [72], этот подход аналогичен отбору ассоциативных правил в Data Mining по порогу величины поддержки.

В соответствии с целью исследования были поставлены следующие задачи:

Выявить и описать методы бикластеризации, использующиеся в различных областях анализа данных, но не вошедшие в современные научные обзоры других исследователей;
Построить таксономию алгоритмов и моделей бикластеризации на основе хорошо структурированных критериев;
Привести обзор областей применения методов бикластеризации;
Составить перечень программных средств бикластеризации по областям применения;
Выбрать и реализовать некоторые из алгоритмов для проведения экспериментов на массивах Интернет-данных;
Показать пригодность методов бикластеризации для анализа Интернет-данных на экспериментальном материале;
В ряде случаев провести сравнительный анализ особенностей методов и установить связь между используемыми вычислительными моделями.

В рамках работы не оставлены без внимания системы поиска бикластеров, приводится их обзор. В частности, это системы

BicAT — область применения биоинформатика,
Concept Explorer, ToscanaJ, Galicia — сообщество ФАП,
Coron — Data Mining (ассоциативные правила и частые множества признаков),
Cluto, Metis — графовая кластеризация,
и Chaco — спектральная кластеризация.

Обзор состоит из введения, пяти разделов, заключения и списка литературы.

В разделе 1 — "Бикластеризация" описана одноименная задача, указано на ее ключевую роль в анализе данных генетической экспрессии. Приводятся основания для классификации методов и моделей бикластеризации. Определяются типы бикластеров, их структура, стратегии поиска алгоритмов и области значений исходных данных. Построена решеточная таксономия методов бикластеризации.

В разделе 2 — "Методы и модели бикластеризации" приводится обзор различных подходов анализа данных, учитывающих их объектно-признаковый характер. Даны основные определения теории решеток и ФАП. Показана связь ассоциативных правил с бикластерами определенного типа.

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

Раздел 4 — "Прикладные задачи" представляет собой краткий обзор основных областей применения алгоритмов бикластеризации с указанием библиографии и пригодных для решения соответсвующих задач методов.

Раздел 5 — "Эксперименты на массивах Интернет-данных" описывает результаты применения изучаемых подходов к решению задач поиска документов-дубликатов в Интернете, выявления Интернет-сообществ пользователей на основе статистики посещаемости сайтов и рекомендаций в системах контекстной рекламы.

1. Бикластеризация

В этом разделе мы опишем проблематику задачи и дадим основные определения, которыми оперирует бикластеризация как метод анализа данных. Помимо это будут приведены основания для классификации методов и алгоритмов бикластеризации. В качестве таких оснований выступают следующие критерии: типы бикластеров, структура бикластеров, получаемых в ходе анализа, а также стратегии поиска, которые используют рассматриваемые алгоритмы. Отметим, что основания для классификации алгоритмов были даны раннее португальским ученым Сарой Мадейра (см. обзор по методам бикластеризации генетических данных [54]).

Мы используем выявленные критерии для построения таксономии методов и дополняем существующую классификацию. В частности, мы рассматриваем методы бикластеризации, которые возникли вне области биоинформатики и предназначены для решения других задач, а также теми методами, которые появились позже написания обзора [54] или не вошли в него. По этой же причине мы не рассматриваем подробно те модели, которые описаны в обзорах [54], [13] и [77]. В качестве еще одного критерия классификации можно использовать область применения метода, но для этого необходимо строго типизировать задачи.

1.1. Постановка задачи и основные определения

Под термином бикластеризация понимается широкий круг задач и методов, а потому для него в научной литературе существует целый ряд синонимов: совместная кластеризация (simultaneous clustering), кокластеризация (co-clustering), двувходовая кластеризация (two-way clustering), кластеризация подпространства (subspace clustering), двумерная кластеризация (bi-dimensional) и бокс-кластеризация (box-clustering). Повышенный интерес к бикластеризации и выделение ее в самостоятельную область анализа данных возникли в связи задачей анализа массивов генетических данных (microarray data analysis). Поэтому, прежде чем дать основные определения из области бикластеризации, мы опишем задачи анализа генетических данных и то, как бикластеринг оказывается полезен для их решения.

Обычно данные генной экспрессии (gene expression data) представляют собой матрицу, в которой строки соответствуют генам, а столбцы — условиям. Каждый элемент такой матрицы отражает уровень экспрессии некоторого гена при заданном условии и представлен действительным числом, как правило, логарифмом относительного содержания информационной РНК (mRNA) гена при этом условии. Такие матрицы, как правило, изучают в двух размерностях, в размерности генов или столбцов. Этим способам анализа соответствует выявление экспрессии шаблонов генов посредством сравнения строк или столбцов. Общие задачи такого анализа включают в себя:

группировку генов согласно их экспрессии для множества условий;
классификацию нового гена по известной экспрессии его и других генов для установленной классификации;
группировку условий, основанная на экспрессии конкретного множества генов;
классификацию нового образца при известной экспрессии генов и условиях эксперимента.

Методы кластеризации могут быть использованы для группирования либо генов, либо условий, а потому явно решают задачи 1 и 3, указанные выше, и неявно — 2 и 4. Но применение методов кластеризации к анализу данных генной экспрессии ведет к значительным сложностям. Активационные образцы образуют группы генов только при определенных экспериментальных условиях. Таким образом, понимание клеточных процессов указывает на то, что необходимо искать множество генов, ведущих себя слаженно и совместно выраженных только при некоторых экспериментальных условиях, и почти независимо при других условиях. А значит, необходимы специальные методы поиска таких локальных образцов, которые могли бы играть ключевую роль в открытии новых генетических взаимодействий [16].

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

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

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

Кластер генов необходимо определять в соответствии только подмножеству условий.
Кластер условий необходимо определять в соответствии только подмножеству генов.
Кластеры не должны быть исключающими и/или полными (гены или условия могут принадлежать ко многим кластерам или вообще ни к одному, а также могуть быть сгруппированы по подмножеству условий или генов соответственно).

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

Фактически, мы будем работать с матрицей размера n на m, элементы которой в общем случае представляют собой действительные числа. Абстрагируясь от задач анализа генетических данных мы будем считать, что строкам матрицы соответствуют некоторые объекты, а столбцам — признаки. Пусть дана матрица , — строк, — число столбцов, — множество строк, — множество столбцов. Будем использовать для обозначения матрицы . Если и подмножества строк и столбцов соответственно, то определяет подматрицу матрицы .

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

Отметим, что мы дали недостаточно формальное определение бикластера. В рамках моделей, представленных в работе, требования, которые предъявляются к понятию бикластера, различаются, а потому формальные определения даются нами только для конкретных случаев. Задача, которую решает алгоритм бикластеризации, заключается в нахождении такого множества бикластеров , которое удовлетворяет некоторым формально определенным требованиям однородности. Словосочетания "сходное поведение" и требования однородности раскрываются в подразделе 1.3 в определениях типов бикластеров.

Содержание Вперёд