Автореферат (Модели, алгоритмы и программные средства бикластеризации на основе замкнутых множеств)

На правах рукописиИгнатов Дмитрий ИгоревичМодели, алгоритмы и программные средства бикластеризации на основезамкнутых множествСпециальность 05.13.18Математическое моделирование, численные методы и комплексы программАВТОРЕФЕРАТдиссертации на соискание учёной степеникандидата технических наукМосква — 2010Работа выполнена в Государственном Университете Высшая Школа Экономики (ГУ-ВШЭ).Научный руководитель:доктор физико-математических наукКузнецов Сергей ОлеговичОфициальные оппоненты:доктор физико-математических наук,профессорАншаков Олег Михайловичдоктор технических наук,профессорХорошевский Владимир ФедоровичВедущая организация:Институт Проблем Управленияим. В.А. Трапезникова РАНЗащита состоится “”2010 г.

в “” ч. на заседании диссертационного совета Д 212.048.09 в Государственном Университете Высшая ШколаЭкономики (ГУ-ВШЭ) по адресу: 105679, Москва, ул. Кирпичная, д. 33.С диссертацией можно ознакомиться в библиотеке Государственного Университета – Высшей Школы Экономики.Автореферат разослан “Учёный секретарьдиссертационного советадоктор технических наук”2010 г.Фомичев В. А.3ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫАктуальность работы. Существует широкий спектр задач, в которых требуется выявлять кластеры с сохранением объектно-признакового описанияданных: выявление групп генов, обладающих общими свойствами; поиск групппосетителей со схожими интересами для рекомендательных систем; выявление сообществ; анализ социальных сетей; автоматическое построение каталогов и рубрикаторов в информационных системах; поиск сходства документов.При решении подобных задач классический кластерный анализ не предоставляет удобных средств, позволяющих сохранить объектно-признаковоеописание кластера.

Например, исследователю-биоинформатику требуется выявлять не столько числовое сходство генов, сколько их общие свойства, т.е. то,благодаря чему они были признаны сходными. Подход к разрешению даннойпроблемы получил название “бикластеризации”.Бикластеризация позволяет отыскивать “бикластеры”, включающие, помимо множества объектов, множество их общих признаков (как вещественныхи бинарных, так и качественных). Например, для данных генной экспрессиипервым компонентом такого кластера является множество генов, а вторым множество экспериментов в которых они проявляли себя сходным образом.Термин “бикластеризация” впервые упомянут в работе Миркина Б.Г.

в 1996 г.Хотя похожие формулировки и методы встречались ранее (например, в работах J.A. Hartigan’а), мы будем использовать это оригинальное название длявсей группы методов, которые применяются для построения таких двукомпонентных кластеров.В анализе данных в начале 80-х годов с появлением работ Р. Виллевозникло прикладное алгебраическое направление Анализ Формальных Понятий (АФП), предоставляющий решеточные модели бикластеризации особого вида, позволяющие сохранять объектно-признаковое описание сходствагруппы объектов внутри кластера и, кроме того, строить иерархии таких кластеров по отношению “быть более общим, чем”.

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

Boulicaut). Необходимость такого рода ослабленийвызвана излишне жёсткой структурой ФП, требующей наличия всех признаков из содержания понятия у всех объектов его объема. Однако в случаеналичия шума возможны “выпадения” некоторых признаков из содержанияпонятия.

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

Отчасти проблема порождения большого числа ФПрешена путем введения индекса устойчивости формального понятия в работах Кузнецова С.О. В этом случае среди множества порожденных ФП отбираются такие, для которых индекс устойчивости превышает некоторый порог.Проблемы отбора релевантных задаче ФП (бикластеров) также обсуждаютсяв рамках данной работы. Что касается моделей “бокс-кластеризации”, описанных Миркиным Б.Г., и шумоустойчивых понятий, то для них характерноналичие сходного подхода.

Этот подход допускает наличие перекрытий илипересечений бикластеров, степень которых оказывается существенной при решении ряда задач. В задачах бикластеризации, решаемых в биоинформатике(см. работы S. Barkow’а и др.), используется похожий аппарат, но значениявходной матрицы не всегда являются булевыми (в большинстве случаев ониположительные вещественные, как в методе OPSM (A. Ben-Dor и др.). Это, всвою очередь, приводит к использованию статистических свойств данных припостроении моделей (см. работы A.

Tanay и др.). У большинства из этих методов, применяемых в биоинформатике, имеются схожие недостатки: проблемаопределения числа кластеров, проблема локального оптимума вследствие использования жадной стратегии поиска (см. работы Y. Cheng’а и G.M. Curch’a)др. Особняком стоят методы спектральной кластеризации, которые изначально опираются на спектральные свойства матричного представления графа связей между объектами.

В последнее время эти методы активно применяются вИнтернет-маркетинге, где связи “рекламодатели-ключевые слова” представлены двудольным графом (например, работы Жукова Л.Е.), и помогают отыскивать потенциальных рекламодателей среди тех, кто не использует некоторыеиз слов, которые купили их конкуренты.

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

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

Посколькумаксимальные замкнутые множества признаков составляют только часть замкнутых, постольку их поиск можно рассматривать в качестве альтернативыспособам сокращения числа ФП для модели АФП. Другим способом сокращения является использование решеток-айсбергов, предложенных в работахG. Stumme.Таким образом разработка моделей, методов и эффективных программных средств бикластеризации на основе замкнутых множеств признаков является актуальной и значимой задачей.Объектом исследования являются модели бикластеризации на основезамкнутых множеств для решения различных задач анализа данных, в которых возможен переход к объектно-признаковому описанию данных.Предметом исследования являются методы, эффективные алгоритмы ипрограммные средства бикластеризации на основе замкнутых множеств длярешения различных задач анализа объектно-признаковых данных.Цели исследования.1.

Выявление взаимосвязи существующих моделей и методов бикластеризации, построение их классификации и таксономии.2. Разработка оригинальных моделей, методов и алгоритмов бикластеризации на основе решеток замкнутых множеств.3. Программная реализация эффективных алгоритмов поиска бикластеровдля решения практических задач анализа данных.Задачи работы. В соответствии с целями диссертационной работы решались (исследовались) следующие задачи.1. Анализ существующих подходов кластеризации и бикластеризации.2. Построение классификации различных моделей и методов бикластеризации, родственных решеточным, изучение их взаимосвязи.3. Разработка оригинальной математической модели и метода бикластеризации на основе решеток замкнутых множеств.4.

Разработка алгоритмов и программных модулей бикластеризации на основе предложенной модели и метода.5. Проведение анализа особенностей разработанного подхода на примеререшения задач анализа Интернет-данных (поиск сходства документов,исследование посещаемости сайтов и разработка рекомендательных систем).66. Разработка методики оценки качества полученных решений в терминахполноты и точности информационного поиска, а также на основе подхода к такой оценке в задачах машинного обучения.Методы исследования. В диссертации используются методы теории упорядоченных множеств и решеток, анализа формальных понятий,теории графов, математической статистики, разработки данных (Data Mining), машинного обучения и информационного поиска.Научная новизна работы определяется полученными в ходе решения задач исследования новыми результатами.1.

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