автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Модели, алгоритмы и программные средства бикластеризации на основе замкнутых множеств

На правах рукописи

Игнатов Дмитрий Игоревич

Модели, алгоритмы и программные средства бикластеризации на основе

замкнутых множеств

Специальность 05.13.18 Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата технических наук

2 5 но Я 2010

Москва — 2010

004614229

Работа выполнена в Государственном университете - Высшей школе экономики (ГУ-ВШЭ).

Научный руководитель: Официальные оппоненты:

Ведущая организация:

доктор физико-математических наук Кузнецов Сергей Олегович

доктор физико-математических наук, профессор

Аншаков Олег Михайлович

доктор технических наук, профессор

Хорошевский Владимир Федорович

Институт проблем управления им. В.А. Трапезникова РАН

Защита состоится "25" ноября 2010 г. в 14.00 ч. на заседании диссертационного совета Д 212.048.09 в Государственном университете - Высшей школе экономики (ГУ-ВШЭ) по адресу: 105679, Москва, ул. Кирпичная, д. 33., ауд. 503

С диссертацией можно ознакомиться в библиотеке Государственного Университета - Высшей школы экономики.

Автореферат разослан октября 2010 г.

-Ю-

Учёный секретарь диссертационного совета доктор технических наук

В.А. Фомичев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

тия (в смысле работ J.-F. Boulicaut). Необходимость такого рода ослаблений вызвана излишне жёсткой структурой ФП, требующей наличия всех признаков из содержания понятия у всех объектов его объема. Однако в случае наличия шума возможны "выпадения" некоторых признаков из содержания понятия. В работах R. Belohlavek'a предложен подход, использующий нечеткие решетки понятий, в котором значения исходных данных лежат в диапазоне [О, 1]. Причина, по которой целесообразно использование нечетких решеток, — возможность передачи вероятностого характера описания исходных данных, например, частоты посещения пользователем веб-сайта. Еще одним желательным требованием является сокращение числа таких бикластеров, т.к. в случае использования АФП их количество растет экспоненциально относительно размера входа. Отчасти проблема порождения большого числа ФП решена путем введения индекса устойчивости формального понятия в работах Кузнецова С.О. В этом случае среди множества порожденных ФП отбираются такие, для которых индекс устойчивости превышает некоторый порог. Проблемы отбора релевантных задаче ФП (бикластеров) также обсуждаются в рамках данной работы. Что касается моделей "бокс-кластеризации", описанных Миркиным Б.Г., и шумоустойчивых понятий, то для них характерно наличие сходного подхода. Этот подход допускает наличие перекрытий или пересечений бикластеров, степень которых оказывается существенной при решении ряда задач. В задачах бикластеризации, решаемых в биоинформатике (см. работы S. Barkow'a и др.), используется похожий аппарат, но значения входной матрицы не всегда являются булевыми (в большинстве случаев они положительные вещественные, как в методе OPSM (A. Ben-Dor и др.). Это, в свою очередь, приводит к использованию статистических свойств данных при построении моделей (см. работы А. Тапау и др.). У большинства из этих методов, применяемых в биоинформатике, имеются схожие недостатки: проблема определения числа кластеров, проблема локального оптимума вследствие использования жадной стратегии поиска (см. работы Y. Cheng'a и G.M. Curch'a) др. Особняком стоят методы спектральной кластеризации, которые изначально опираются на спектральные свойства матричного представления графа связей между объектами. В последнее время эти методы активно применяются в Интернет-маркетинге, где связи "рекламодатели-ключевые слова" представлены двудольным графом (например,1 работы Жукова /КЕ.), и помогают отыскивать потенциальных рекламодателей среди тех, кто не использует некоторые из слов, которые купили их конкуренты. Фактически эти методы искусственно адаптированы для задач бикластеризации, поскольку для найденных кластеров приходится восстанавливать их объектно-признаковую структуру.

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

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

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

Объектом исследования являются модели бикластеризации на основе замкнутых множеств для решения различных задач анализа данных, в которых возможен переход к объектно-признаковому описанию данных.

Предметом исследования являются методы, эффективные алгоритмы и программные средства бикластеризации на основе замкнутых множеств для решения различных задач анализа объектно-признаковых данных. Цели исследования.

1. Выявление взаимосвязи существующих моделей и методов бикластеризации, построение их классификации и таксономии.

2. Разработка оригинальных моделей, методов и алгоритмов бикластеризации на основе решеток замкнутых множеств.

3. Программная реализация эффективных алгоритмов поиска бикластеров для решения практических задач анализа данных.

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

1. Анализ существующих подходов кластеризации и бикластеризации.

2. Построение классификации различных моделей и методов бикластеризации, родственных решеточным, изучение их взаимосвязи.

3. Разработка оригинальной математической модели и метода бикластеризации на основе решеток замкнутых множеств.

4. Разработка алгоритмов и программных модулей бикластеризации на основе предложенной модели и метода.

5. Проведение анализа особенностей разработанного подхода на примере решения задач анализа Интернет-данных (поиск сходства документов, исследование посещаемости сайтов и разработка рекомендательных систем).

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

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

Научная новизна работы определяется полученными в ходе решения задач исследования новыми результатами.

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

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

3. Предложена математическая модель сходства текстовых документов, сформулированная в терминах частых замкнутых множеств признаков и АФП.

4. Предложена математическая модель построения таксономий групп пользователей веб-сайтов на основе решеток формальных понятий. Указаны наилучшие способы отбора релевантных формальных понятий для построения таких таксономий.

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

Теоретическая значимость работы заключается в 1) установлении взаи-

мосвязей существующих моделей бикластеризации, методов анализа данных на основе теории решеток и поиска ассоциативных правил; 2) построении таксономии существующих методов бикластеризации и её расширении путем включения критериев классификации новых и родственных методов; 3) разработке модели бикластеризации на основе замкнутых множеств объектов и признаков, теоретическом исследовании ее свойств.

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

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

Личный вклад диссертанта. Работа продолжает развитие методов

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

АПРОБАЦИЯ РАБОТЫ Результаты работы докладывались на следующих научных семинарах и конференциях:

1. Научном семинаре Лаборатории анализа и выбора решений, ГУ-ВШЭ, 2010 и научном семинаре "Математические модели информационных технологий" кафедры анализа данных и искусственного интеллекта, ГУ-ВШЭ, 2010

2. Научно-технической конференции студентов, аспирантов и молодых спе-

циалистов "Информационные технологии в бизнесе", ГУ-ВШЭ, 2006 (доклад отмечен дипломом)

3. Трижды на национальной конференции по искусственному интеллекту, КИИ-2006, Обнинск; КИИ-2008, Дубна; КИИ-2010, Тверь.

4. На научно-технической конференции "25 лет исследований по ДСМ-методу: логика, анализ данных, интеллектуальные системы (ДСМ-2006)", РГГУ и ВИНИТИ РАН, Москва, 2006

5. Четырежды на научно-технической конференции студентов, аспирантов и молодых специалистов "Информационные технологии в экономике, бизнесе, управлении", ГУ-ВШЭ, 2007, 2008, 2009 и 2010;

6. Второй международная молодежной конференции «Искусственный интеллект: философия, методология и инновации», Санкт-Петербург, СПб-ГУ, 2007 (диплом: лучший доклад)

7. 5-ой международной конференции по Формальному Анализу Понятий, (5th International Conference on Formal Concept Analysis: Clermont-Ferrand, France, February 12-16, 2007) в рамках семинара по анализу социальных сетей (Social Network Analysis and Conceptual Structures: Exploring Opportunities)

8. 1-ой международной конференции по бизнес-информатике, ГУ-ВШЭ, Звенигород, 2007

9. 6-ой международной конференции по решеткам понятий и их приложениям (The Sixth International Conference Concept Lattices and Their Applications (CLA'08)), Olomouc, Czech Republic, 2008

10. 5-й Международной научно-технической конференции "Интегрированные модели и мягкие вычисления в искусственном интеллекте", Коломна, 2009

11. 17-й международной конференции по понятийным структурам (The 17th International Conference on Conceptual Structures, (ICCS'09)), Москва, 2009

12. Летней школе по информатике Reasoning Web 2010: Semantic Technologies for Software Engineering, TU-Dresden, Germany, 2010

Публикации. Основное содержание диссертационной работы изложено в 14 публикациях, среди которых 6 — в трудах российских конференций, 3 — в рецензируемых трудах международных конференций, и 4 — в рецензируемых российских периодических изданиях (из которых 2 статьи опубликованы в журнале из списка ВАК) и 1 статья в международном рецензируемом журнале.

Структура и объем диссертации. Диссертация состоит из четырёх глав, заключения и списка литературы. Общий объем работы — 163 страницы. Список литературы включает 93 названия.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе приведены основные определения и результаты из области бикластеризации и кластеризации, теории упорядоченных множеств, теории решеток, анализа формальных понятий (АФП). Помимо сведений из АФП, сформулированы определения и даны характеристики четырёх методов бикластеризации — метод BiMax из области биоинформатики, шумоустойчи-вые понятия, как идея расширения определения формальных понятий, устойчивых к ошибкам в данных, метод аддитивной бокс-кластеризации и поиск частых замкнутых множеств признаков, который был использован автором для реализации подхода выявления документов (почти)дубликатов.

Приведём основные определения и сведения из области бикластеризации и анализа формальных понятий, необходимые для наших целей.

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

Фактически будем работать с матрицей размера п на т, элементы которой в общем случае представляют собой действительные числа, и будем считать, что строкам матрицы соответствуют некоторые объекты, а столбцам — признаки.

Пусть дана матрица А, п — число строк, т — число столбцов, X = [х\, Х2,..., хп} — множество строк, Y = {уъ У2> ■ ■ ■, Уп} — множество столбцов. Будем использовать (X,Y) для обозначения матрицы А. Если I С X и J С Y подмножества строк и столбцов, соответственно, то Ajj = (/, J) определяет подматрицу Ajj матрицы А. Кластер строи есть подматрица матрицы А вида Aiy = {1,У), д-пя которой подмножество строк проявляет "сходное поведение" вдоль всего множества столбцов. Кластер столбцов есть подматрица матрицы Л.вида Axj = (X,J), для которой подмножество столбцов проявляет "сходное поведение" вдоль строк. Бикластер есть подматрица матрицы

А вида Ajj = (I, J), такая, что ее строки проявляют "сходное поведение" на столбцах, а столбцы - на признаках.

В рамках представленных в работе моделей требования, предъявляемые к понятию бикластера, различаются, а потому формальные определения даются только для конкретных случаев. Задача, которую решает алгоритм бикластеризации, заключается в нахождении такого множества бикластеров В = {Bk = (h,Jk)}> которое удовлетворяет некоторым формально определенным требованиям однородности. Словосочетания "сходное поведение" и "требования однородности" раскрываются в разделе, дающем определения типов бикластеров.

Приведем основные определения АФП. Пусть G и М суть множества, называемые соответственно множествами объектов и признаков, а / С GxM — отношение. Для д £ G, т € М имеет место glm если объект д обладает признаком т. Тройка К = (G,M,I) называется формальным контекстом. Для произвольных А С G и В С М соответствие Галуа определяется следующей парой отображений:

А' := {тп € М | glm для всех д € А}, В' {д £ G | glm для всех тп 6 В}.

Пара множеств (А, В) таких, что А С G, В С М, А' = В и В' = А называется формальным понятием контекста К с (формальным) объёмом А и (формальным) содержанием В.

Множество всех понятий формального контекста К образует решётку (обозначаемую через Ъ[К)) со следующими операциями:

Д(л,,в;-) = (р| л-.(П V). \J{AvBi) = ((f) П^)-

jeJ jeJ jeJ jeJ j&J jeJ

По основной теореме АФП любая полная решётка изоморфна решётке понятий некоторого формального контекста. В качестве объектов этого контекста можно, например, выбрать Л-неразложимые элементы, а в качестве признаков — V-неразложимые элементы исходной решётки.

Многозначный формальный контекст есть четвёрка (G, М, W, J), где G, М, W — множества (объектов, признаков и значений признаков, соответственно), a J — тернарное отношение J С G х М х W, задающее значение w признака то, причём:

{g, m,w) € J и (g, m,v) 6 J влечёт w = v

Процедура сведения многозначных контекстов к однозначным называется шкалированием (scaling). Для шкалирования каждый признак многозначного контекста представляется формальным контекстом, называемым шкалой.

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

Задача поиска частых множеств признаков (frequent itemsets mining) является одной из центральных тем в Data Mining. Первоначально, необходимость поиска частых множеств признаков возникла при выявлении часто покупаемых вместе товаров. Среди частых множеств признаков выделяют так называемые частые замкнутые множества признаков, которые полезны для их более компактного представления. Такое представление осуществляется без потерь информации о поддержке собственных частых подмножеств данных частых замкнутых множеств признаков. Хорошо известным фактом для специалистов по разработке данных является то, что все замкнутые частые множества признаков (т.е. при minsupp — 0) образуют решетку, эта решетка изоморфна решетке понятий контекста для соответствующей базы данных (см., например, работы М. Zaki).

Пусть дан формальный контекст К = (G,M,I). Множество признаков F С М называется частым множеством признаков, если |.Р'| > 9, где в — заданный числовой порог > 0. Ключевым понятием для данной задачи является поддержка. Поддержкой множества признаков А С М называется величина supp(A) = Значение supp{A) показывает, какая доля объектов G содержит А. Часто поддержку выражают в %. Если задано значение минимальной поддержки min_supp, то определение частого множества признаков можно переписать следующим образом. Множество признаков F С М называется частым множеством признаков если supp(F) > min_supp. Для контекста К = (G,M,I) частое множество признаков FC С М называется частым замкнутым множеством признаков, если не существует F, такого что F D FC и supp(F) = supp(FC). Используя оператор замыкания, можно дать следующее эквивалентное определение. Множество признаков FC С М называется частым замкнутым множеством признаков, если supp(FC) > min_supp и FC" = FC. Частое множество признаков FM С М называется максимальным частым множеством признаков, если не существует частого множества признаков F, такого что F D FM. Пусть FI — множество всех частых множеств признаков, FCI — множество всех частых замкнутых множеств признаков, a MFI — множество всех максимальных частых множеств признаков. Тогда, очевидно, выполнено следующее соотношение MFI С FCI С FI.

Максимальные множества признаков хотя и не позволяют вычислить поддержку всех частых множеств признаков, но являются более компактным представлением чем FCI и FI. Применение MFI оправдано для плотных контекстов, в то время как поиск всех частых множеств признаков оказывается невозможным.

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

Традиционные методы кластеризации предлагают разнообразный набор средств для решения задач группировки объектов с учетом их сходства в самых разных предметных областях. Однако эти методы имеют ряд недостатков. Например, метод K-means требует знания количества кластеров в качестве па-

раметра, адекватный выбор которого - задача аналитика. Результаты работы некоторых методов кластеризации зависят от порядка рассмотрения объектов исходной выборки. Как правило, методы кластеризации разбивают объекты на группы, но не отвечают на вопрос, в чем заключается сходство сгруппированных в один кластер объектов. Если исходные данные представлены в виде объектно-признаковой таблицы, то под кластером понимается множество строк (столбцов) такой таблицы, при этом сходство рассчитывается по всем значениям, записанным в такой строке или столбце, хотя реально у таких строк (столбцов) могут быть похожими только некоторые подмножества признаков (объектов). Отметим тот факт, что идея бикластеризации хорошо вписывается в парадигму кластер-анализа, являясь естественным расширением идей кластеризации по подпространству (только по части признаков в исходной объектно-признаковой таблице), описанных в работах А§га«/аГя и совместной кластеризации по строкам и столбцам, предложенной I. ОЫПоп'ом.

Говоря о бикластеризации стоит заметить, что в данной работе фигурируют в основном с бинарные данные {0,1}-типа и не рассматриваются методы бикластеризации, работающие на данных с вещественными значениями (такими как интервалы), на графовых моделях в качестве признаков или описаний. Тем не менее, автором приводится классификация (таксономия) таких методов.

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

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

подхода была реализована схема "шинглирования" (от англ. shingle - черепица) и составление краткого образа (скетча) документов на основе методов "п минимальных элементов в перестановке" и "минимальные элементы в п перестановках", описание которого можно найти, например, в [A. Broder, 1998, 2000]. Шинглирование осуществляется с двумя параметрами length и offset и позволяет порождать для каждого текста набор последовательностей слов или символов (шинглов) длины length, так что отступ от начала одной последовательности до начала другой последовательности в тексте имеет размер offset. Полученное таким образом множество последовательностей хэширу-ется, так что каждая последовательность получает свой хэш-код. Далее из множества хэш-кодов, соответствующему документу, выбирается подмножество фиксированного (с помощью параметра) размера с использованием случайных перестановок, описанных в работах [A. Broder, 1997, 1998, 2000]. При этом вероятность того, что минимальные элементы в перестановках хэш-кодов на множествах шинглов документов А и В (эти множества обозначаются через Fa и Fb, соответственно) совпадут, равна мере сходства этих документов sim(A, В):

P[min{n(FA)} = min{i;(FB)}) = =

Опишем предлагаемую модель. Рассматрим формальный контекст Ждо = (D,F,I), где D - множество документов, a F - множество хеш-кодов (fingerprints), отношение I показывает, что некий объект d обладает признаком / в том и только том случае, когда dlf. Для множества документов А С D множество их общих признаков А! служит описанием их сходства, а замкнутое множество А!' является кластером сходных объектов (с множеством общих признаков А'). Для произвольного В С F величина \В'\ — IÎ9 S G|Vm € B(glm)}| является поддержкой В и обозначается supp(B). Нетрудно видеть, что множество В замкнуто тогда и только тогда, когда для любого С D В имеет место supp(D) < supp(B). Именно это свойство используется для определения замкнутости в методах Data Mining. Множество В С M называется fc-частым, если \В'\ > к (то есть множество признаков В встречается в более чем к объектах), где к — параметр. Фактически будем вычислять частные замкнутые множества признаков для дуального к К op контекста, т.е. находить такие множества документов-признаков контекста Кро = (F,D,I), для которых размер множества их общих шинглов превышает заданный порог сходства. Хотя теоретически размер множества всех замкнутых множеств признаков (содержаний) может быть экспоненциальным относительно числа признаков, на практике таблицы данных сильно "разрежены" (то есть среднее число признаков на один объект весьма мало) и число замкнутых множеств невелико. Для таких случаев существуют весьма эффективные алгоритмы построения всех наиболее частых замкнутых множеств признаков (см. также обзор по алгоритмам построения всех замкнутых множеств [Kuznetsov, 2002]). В последние годы проводился ряд соревнований

по быстродействию таких алгоритмов на серии международных семинаров под общим названием FIMI (Frequent Itemset Mining Implementations). Одним из лидеров по быстродействию считается алгоритм FPmax* [Grahne, 2003], показавший наилучшие результаты по быстродействию в соревновании 2003 года. Этот алгоритм использовалься автором диссертационного исследования для построения сходства документов и кластеров сходных документов.

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

Необходимо построить "внешнюю" и "внутреннюю" таксономии некоторого целевого сайтов. Под "внешней" таксономией будем понимать иерархическую структуру аудитории целевого сайта, выявленную по данным посещений остальных сайтов выборки. Ей будет в точности соответствовать решетка формальных понятий, построенная по такому контексту Кех = (V, Sex, /), где V -множество всех посетителей целевого сайта, Sex - множество всех сайтов выборки исключая целевой, 1 - отношение инцидентности vis, имеющее место для v 6 V, s £ Sex, тогда и только тогда, когда посетитель v "ходил" на сайт s. Под "внутренней" таксономией будем понимать иерархическую структуру аудитории целевого сайта, построенную по данным посещений его собственных страниц (возможно, сгруппированных по разделам). Соответствующий контекст определяется сходным образом = (V, Sin, I), где V - множество всех посетителей целевого сайта, ¿¿п - множество всех собственных страниц целевого сайта, I — отношение инцидентности vis, имеющее место для v £ V, s Е Sin, тогда и только тогда, когда посетитель!! "ходил" на сайт s. Понятию такого контекста соответствует пара (А, В), такая что А' = { множество сай-

tob s £ S, которые посещали все посетители v £ А} = В, а В' = {множество посетителей v € V, которые посещали все сайты s S В} — А.

Остановимся подробнее на понятии индекса устойчивости формального понятия, предложенного в работах С.О. Кузнецова, который используется для отбора интересных групп посетителей при построении таксономий. Индекс устойчивости ФП служит показателем независимости содержания от частных объектов объема (наличие которых в контексте зависит от случайных факторов).

Пусть К = (G,M,I) — формальный контекст, {А, В) - некоторое формальное понятие К, тогда индекс устойчивости а понятия (А, В) определяется выражением

\{ССА\В' = А}\ -^-•

Очевидно, что 0 < а(А,В) < 1.

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

Пусть (Л, В) - некоторое ФП контекста К = (G,M, /), его поддержка определяется выражением supp(A,B) = j^j, и дано минимальное значение поддержки minsupp € [0,1], тогда решеткой-айсбергом назовем множество {{А, B)\supp{B) > minsupp}.

Использование решеток-айсбергов позволяет выявлять крупные понятия, соответствующие аудиториям наиболее посещаемых сайтов. К сожалению, размер аудитории не гарантирует того, что данная аудитория возникла не в результате влияния шума. Поэтому исследовались и некоторые другие критерии отбора релевантных ФП, например, минимальные разрезы из теории графов. Применение таких критериев возможно потому, что формальному контексту К = (G,M,I) соответствует неориентированный двудольный граф Г = (G U М, Е), где для g е G и m G М выполнено {g, тп} £ Е <£> glm. Формальному понятию {А, В) контекста К будет соответствовать биклика к а,в двудольного графа Г. В этом случае разрезом для формального понятия (Л, В) будет число ребер графа Г, имеющих одну вершину в А или В, а другую в М \ В или G \ А соответственно.

Для формального контекста К = (G, М, I) разрез ФП (А, В) определяется выражением

cui(A5) = |(lJ5')\S| + l(U

дбЛ meB

Такой индекс показывает степень связи объектов и признаков ФП с другими признаками и объектами контекста. Если говорить в терминах "пользователи-сайты", то чем меньше значение cut для некоторого понятия, тем легче отделить аудиторию (объем понятия) от пользователей других сай-

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

Формирование бикластеров и рекомендаций для рекомендательной системы Интернет-рекламы. Одна из разновидностей электронной коммерции

— контекстная Интернет-реклама. Сейчас на рынке таких услуг крупными игроками являются поисковые системы, немалую часть прибыли которых составляет так называемая поисковая реклама. Для России репрезентативными примерами служат рекламные Интернет-сервисы "Яндекс.Директ" и "Бегун". Пользователю предлагается релевантная (с точки зрения поисковой системы) его поисковому запросу реклама. В отличие от задачи предоставления пользователю наиболее интересной ему поисковой рекламы, наша задача — выявление рекламных слов, которые могут быть интересны рекламодателю. Предположим, что некая фирма F приобрела ряд рекламных слов, которые описывают предоставляемые услуги. Как правило, на рынке уже существуют компании-конкуренты, поэтому вполне разумно было бы выяснить, какие рекламные слова приобрели они. Далее можно сравнить эти множества слов с теми, что купила F и, исходя из частоты таких покупок, отобрать наиболее для нее интересные из неприобретенных. Такой механизм стимулирует продажи рекламы и позволяет устраивать своеобразный аукцион по определению цены того или иного рекламного словосочетания. Решение подобной задачи методами спектральной кластеризации описано в работах Жукова Л.Е. Цель наших экспериментов не только расширить список методов бикластеризации пригодных для решения этой задачи, но и улучшить качество предложенных рекомендаций. Ниже приведено описание математической модели задачи.

Исходный массив данных описывается формальным контекстом К^г = (F,T, 1рт), F (от firms) — множество компаний-рекламодателей, аТ (от term)

— множество рекламных словосочетаний, I — отношение инцидентности, показывающее, что фирма / € F купила словосочетание t Е Т тогда и только тогда, когда fit.

Для решения задачи последовательно применялись следующие подходы:

1. отбор по размеру объема и содержания понятий и объектно-признаковую бикластеризацию для выявления крупных рынков средствами АФП;

2. поиск ассоциативных правил для построения рекомендаций;

3. построение ассоциативных метаправил с помощью морфологического анализа;

4. построение ассоциативных метаправил с помощью онтологий (тематического каталога).

Краткое описание модели формирования рекомендаций на основе ассоциативных метаправил с помощью морфологического анализа приведено

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

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

Пусть t - некое рекламное словосочетание. Представим его в виде множества слов его образующих t = {wi,w2, ■ ■ ■ ,wn}. Основу слова w¡ обозначим через Si = stem(wi), тогда множество основ словосочетания t обозначим через Stem(t) = (Jstem(wi). Построим формальный контекст К^ = i

(T,S,Its). где Т — множество всех словосочетаний, a S — множество основ всех словосочетаний из Т, т.е. S = (J Stem(ti), Тогда ti s будет означать, что

г

во множество основ словосочетания t входит основа s.

Построим по такому контексту правила вида t —» sjTS для всех t £ Т.

ft 7

Тогда такому метаправилу контекста К ts соответствует t —> s™ — ассоциативное правило контекста Крт- Если величина поддержки и достоверности такого правила в контексте превышают некоторые пороговые значения, то можно считать ассоциативные правила, построенные по контекстуKjry, не столь интересными (их можно вывести из описания признаков).

В качестве более крупных метаправил предлагаются следующие две возможности. Во-первых, можно искать правила вида i (J sjTS, т.е. правила, в

i

правую часть которых входят все термы, имеющие хотя бы одно однокоренное

слово с исходным термом. Во-вторых, правила вида t —» (Us¿)/tS' т-е- пРа~

i

вила, термы в правой части которых содержат в своем составе те же основы, что и исходный. Довольно очевидно, что первый тип правил может привести к объединению различных словосочетаний, например "blackjack" — игровой бизнес и "black coat" — одежда. Такое объединение произошло благодаря наличию общего слова "black". А второй тип правил относится к более редким зависимостям, например, {black jack] —> {black jack game online}. Поэтому меры поддержки и достоверности при построении простых метаправил должны служить их мерой пригодности для дальнейшего использования. Предло-

ft j j

жено также использовать метаправила вида 11 —> ¿2. такие что t2TS Ç t™. Такие правила имеют простую интерпретацию, из словосочетания ¿2 следует словосочетание множество основ которого вкладывается в множество основ ¿1, например, {ink jet} —> {ink}, supp — 14, a conf — 0,7.

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

В третьей главе устанавливается связь между методами поиска ассоциативных правил и бикластеризацией. Выявляется эквивалентность определения бикластера для исследования данных генной экспрессии и формального понятия в АФП. Предлагается новый алгоритм бикластеризации на основе объектных и признаковых замыканий.

Рассмотрим алгоритм для предложенного автором определения бикластера. Предварительно введем определения объектного и признакового понятия.

Объектным понятием формального контекста К = (С, М, I) называется формальное понятие вида (д",д'), где д £ С, а признаковым понятием формального контекста К = (С?, М, I) называется формальное понятие вида (тп',т"), где т £ М.

Для краткости записи будем писать д" и д' вместо {д}" и {д}' соответственно, аналогично поступим с записью оператора Галуа на признаках. Обозначим множество всех объектных понятий формального контекста К = ((7, М, I) как ОЬ] = {(д",д')\Уд £ С}, а множество всех признаковых понятий как АНг = {(т', т")\Ут £ М}.

Для формального контекста К = (С, М, I) и любой пары объектных и признаковых понятий (д",д') £ ОЬ] и (т',т") £ АШ, связанных отношением вложения (д",д') < (т',т"), назовем объектно-признаковым бикластером (оп-бикластером) пару вида (т',д').

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

Плотностью бикластера (А, В) формального контекста К = (С,М,1)

назовем величину р(А,В) = ^рурр-

Свойство 1. 1. Если (т',д') оп-бикластер, то (д",д') < (т',т").

2. Для произвольного бикластера (А, В) справедливо соотношение 0 <

Р< 1.

3. Пусть {А, В) - формальное понятие, тогдар(А,В) = 1

Пусть дан бикластер {А, В) £ 2е х 2м и положительное целое число Ртт. такое что 0 < ртт < 1 , тогда (А, В) называется плотным в том и только том случае, когда он удовлетворяет ограничению Саепзе(рт{п, {А, В)) =

(р(Л, В) > Ртт)

т"

Рис. 1. Бикластер на основе объектных и признаковых замыканий

Свойство 2. Ограничение С,1епзе(ртт, (А, В)) = (р(А,В) > ртт) не- является ни монотонным, ни антимонотонным.

Пусть рт{п = 0, тогда верно

Утверждение 1. Для любого формального понятия (Ас, Вс) £ *В(С, М, I) существует (Аь, Вь) £ В, такой что (Ас, Вс) С (Аь, Вь).

Тот факт, что оп-биклэстер представим в виде (т!, д') наводит на мысль о том, что возможно избежать дорогостоящего вычисления оператора замыкания -(.)" (в худшем случае 0(|(?||М|)). Поэтому автором предложен алгоритм, который является улучшенной версией действующего по определению "наивного" алгоритма, и использует свойство антимонотонности оператора (.)' для оптимизации. Доказано утверждение об эквивалентности выходов этих алгоритмов.

При достаточно больших значениях ртт не все формальные понятия могут оказаться вложенными в некоторый бикластер, построенный по формальному контексту К = (С, М, I).

Утверждение 2. При некотором рт.,•„ > 0 существует К = ((?, М, I), такой что существует формальное понятие (АС,ВС) € 53((?,М,/), для которого верно, что не существует бикластера (Аь, Вь) £ В, такого что

{Ас, Вс) Е (Аь,Вь).

Оценим теоретически ресурсную временную и емкостную сложность алгоритма 1.

Число объектно-признаковых бикластеров контекста может быть гораздо меньше числа формальных понятий (в худшем случае экспоненциальное

Algorithm 1: Улучшенный алгоритм поиска бикластеров_

Data: К = (G, М, I) - формальный контекст, pmin - порог на

значение плотности оп-бикластера Result: В — {(Aj., Вк)\(А}., Вк) - оп-бикластер} begin

Obj.Size = |G| Attr.Size = |M| В <— 0 for g € G do L Obj[g] = g' for meM do |_ Attr\m] = m!

for g f- 0 to |G| do for m G Obj[g] do

if p{Attr[m},Obj[g}) > pmin then L B.Add((Attr[m\,Obj[g\))

количество от размера |G| + \M\), что подтверждается следующими утверждениями.

Утверждение 3. Для данного формального контекста К = (G, М, I) и pmin = 0 наибольшее число оп-бикластеров равно а все оп-биклаетеры порождаются за время 0(|/| • (|G| + |М|)).

Утверждение 4. Для данного формального контекста К = (G, М, I) и Pmin > 0 наибольшее число оп-бикластеров равно а все оп-бикластеры порождаются за время 0(|/| • |G| • |М|).

В четвёртой главе предлагаемые модели и методы бикластеризации использовались в серии экспериментов в нескольких предметных областях.

В качестве экспериментального материала использовалась URL-коллекция РОМИП, состоящая из 52 файлов, общего размера 4,04 Гб. Для проведения экспериментов коллекция разбивалась на несколько частей, включающих от трех до двадцати четырех файлов (приблизительно от 5% до 50% от размера всей коллекции). Параметры шинглирования, использовавшиеся в экспериментах: число слов в шингле 10 и 20, отступ между началом соседних шинглов 1. Данное значение отступа означает, что начальное множество шинглов включало все возможные последовательности цепочек слов. В экспериментах с синтаксическим методом представления исследовались оба способа составления образа документа, описанные в главе 2: "п минимальных элементов в перестановке" и "минимальные элементы в п перестановках'. Размеры результирующих образов документов выбирались в пределах от 100 до 200 шинглов. Основные блоки вычислений реализованы на языке Java, блок

7 позволяет использовать различные реализации алгоритмов для поиска частых замкнутых множеств признаков на языке С++ из репозитория FIMJ. Эксперименты проводились на персональном компьютере P-IV НТ с тактовой частотой 3.0 ГГц, объемом оперативной памяти 1024 Мб и операционной системой Windows ХР Professional и Java 2 VM фирмы Sun (версия 1.4.3). Результаты экспериментов и время, затраченное на их проведение, приводятся в основном тексте в виде таблиц и графиков.

Сравнение полученных результатов поиска с тестовой коллекцией РО-МИП позволило выявить в ней значительное количество ложных документов-дубликатов. Результаты сравнения с системой кластеризации CLUTO (одной из лучших для кластеризации документов) показали, что реализованный в ней алгоритм ClusterRB по значению F-меры 0,63 при числе кластеров равном 5000 сравним с результатами работы FPmax* на той же коллекции при значении порога 125 (Fl=0,61). При этом время работы ClusterRB составило 4 часа, тогда как FPmax* справился с задачей меньше, чем за полсекунды.

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

В качестве данных для проведения экспериментов нам предложена выборка по статистике посещений 10000 сайтов с прилагаемым плоским тематическим каталогом по 59 категориям. Для конкретных экспериментов из них были отобраны четыре сайта следующих тематик: сайт университета, сайт Интернет-магазина бытовой техники, сайт крупного банка, сайт автомобильного Интернет-салона. В качестве языков разработки применялся С# из среды MS Visual Studio 2005 и язык скриптового программирования Pyhton. 1) Для выявления исходных понятий по зашумленным данным необходимо выбирать значение порога N (мощность множества самых крупных или самых устойчивых понятий) примерно равным их числу. При большем значении порога наблюдается появление нерелевантных понятий. 2) Индекс устойчивости приемлем в задаче выявления исходных понятий по зашумленным данным для указанных типов и размеров контекстов при уровне "шума" от 1% до 5%. 3) Индекс устойчивости показывает лучшие результаты на контекстах номинальных шкал, т.е. когда наблюдается преобладание несравнимых понятий в исходной решетке.

Данные для экспериментов по рекомендательным системам принадлежат компании US Overture (ныне часть Yahoo) и описаны в работе [Zhukov, 2004]. Фактически данные представляют собой двумерный массив, в котором строкам соответствуют фирмы (advertisers), а столбцам — рекламные слова (bids). Число фирм — 2000, а число рекламных словосочетаний — 3000. Еди-

ница в ячейке означает, что фирма, соответствующая индексу строки, приобрела словосочетание, которое соответствует столбцу, ноль - отсутствие такой покупки. Число ненулевых ячеек 92345, соответственно мера разреженности равна 1 — 6ддцдд0 га 0,9846. С помощью АФП и предложенного алгоритма объектно-признаковой бикластеризации выявлены крупные рынки рекламных словосочетаний. Причем on-бикластеры более информативны, т.к. число разных тем, приходящихся на один бикластер, примерно в 1,5 раза больше, чем для случая АФП с ограничениями на размер объема и содержания. Для проверки результатов, полученных с помощью поиска ассоциативных правил, применялась модификация 10-кратного скользящего контроля (10-fold cross validation). Агрегированной мерой качества полученных правил служило среднее значение достоверности для всего порожденного множества, которая на тестовой выборке не сильно снижается по сравнению с минимальной для обучающей, т.е. (0,9 — 0,87)/0,9 « 0,03. В качестве средства валидации для метаправил также используется меру достоверности. Величина поддержки не играет большой роли, так как осуществляется поиск не столько крупных рынков или наиболее продаваемых словосочетаний, а устойчивых закономерностей при покупке. Правила с достоверностью меньше 0,5 нас не так сильно интересуют, потому что они означают, что в половине случаев покупка может произойти, а в половине — нет (своеобразная игра в подбрасывание монеты). Для метаправил значения поддержки и достоверности необходимо вычислить по контексту К ft = {F,T,Ipr)- Приведем значения этих мер в сводной таблице 0.1 для метаправил, построенных с использованием морфологии.

Таблица 0.1. Средние значения supp и conf для морфологических метаправил при min_conf = 0,5

Тип правила Среднее значение supp Среднее значение conf Число правил

t ^ s{TS 15 0,64 454

t£l>\Js¡TS 15 0,63 75

18 0,67 393

t Q tu где t¡TS С t1™ 21 0,70 3922

t ^ (J U, где t¡" С t1" i 20 0,69 673

По таблице 0.1 легко установить, что наиболее достоверными и часто

j. FT I u

встречающимися являются правила вида t —> \jU.

i

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

улучшить рекомендации и предлагают хорошее средство частотного ранжирования, что удобно при составлении Тор^ рекомендаций. Еще одно преимущество подхода состоит в возможности выявить связанные рекламные слова, но не используемые по каким-то причинам рекламодателями. Результаты бикла-стеризации на основе АФП показывают возможность выявления относительно крупных рекламных рынков (> 20 участников) в виде бикластеров (фирмы-участники, рекламные слова).

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

В заключении приведены основные результаты и перспективы дальнейших исследований.

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

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

1. Оригинальная модель и метод бикластеризации на основе объектных и признаковых замыканий. Исследованы и описаны в виде математических утверждений полезные свойства нового определения бикласте-ра. Теоретические оценки временной сложности и размера выхода алгоритма, реализующего данный метод, полиномиальны от размера входа. Это дает новый эффективный способ сокращения числа бикластеров по сравнению с поиском всех формальных понятий, количество и время поиска которых в худшем случае экспоненциальны от размера входа. Экспериментально показано, что разработанная оптимизированная (на основе свойства антимонотонности оператора Галуа) версия алгоритма в среднем в 28 раз превосходит по времени вычислений алгоритм, непосредственно проверяющий условия определения. Алгоритм позволяет эффективную параллельную реализацию, что дает дополнительные 45% сокращения времени счета на двухядерном процессоре.

2. Оригинальная модель поиска сходства текстовых документов и их кластеров на основе частых замкнутых множеств признаков. Эксперименты, проведенные с помощью ее программной реализации на больших коллекциях документов, показали превосходство по времени вычислений на 3-4 порядка по сравнению с лучшими из известных алгоритмов бикластеризации документов (разработанными в лаборатории _). Кагур^'а), при сохранении такого же качества по точности и полноте поиска. На основе модели разработан прототип системы поиска документов-дубликатов в текстах проектной документации.

3. Оригинальная модель построения "внешних" и "внутренних" таксономии аудиторий Интернет-сайтов на основе АФП и критериев отбора релевантных понятий. На основе модели создана программная реализация, позволившая провести исследование аудиторий четырех крупных Интернет-сайтов и построить их таксономии.

4. Модели выявления крупных рынков рекламных словосочетаний для контекстной рекламы и формирования рекомендаций таких словосочетаний на основе ассоциативных метаправил, использующих морфологию. Созданный прототип рекомендательной системы позволил формировать высокодостоверные рекомендации только на основе морфологического строения слов в рекламном словосочетании, минуя дорогостоящие вычисления для исходной матрицы покупок рекламы.

5. Впервые проведенное исследование связи между ассоциативными правилами, бикластеризацией и решетками понятий. Введено понятие плотности и разреженности бикластера, на основе которого исследованы би-кластеры, порождаемые ассоциативными правилами и формальными понятиями.

Основное содержание диссертационной работы изложено в следующих публикациях:

Публикации в журналах, входящих в перечень ВАК

1. Игнатов Д. И. Раскопки сетевых данных //Открытые системы. СУБД, №9, 2009, С. 34-37. 0,52 п.л.

2. Игнатов Д. И. Практикум по добыче данных //Открытые системы. СУБД, №6, 2010, С. 49-51. 0,39 п.л.

Другие публикации

3. Кузнецов С. О., Игнатов Д. И., Объедков С. А., Самохин М. В. Порождение кластеров документов дубликатов: подход, основанный на поиске частых замкнутых множеств признаков // Интернет-математика 2005. Автоматическая обработка веб-данных. — М.: "flndex", 2005. — С. 302— 319. 0,83 п.л. (вклад автора 0,6 п.л.)

4. Игнатов Д. И., Кузнецов С. О., Лопатникова В. Б., Селиц-кий И. А. Разработка и апробация системыпоиска дубликатов в текстах проектной документации //Бизнес-информатика/междисциплинарный научно-практический журнал, № 4, 2008, С. 21 - 28. 0,8 п.л. (вклад автора 0,45 п.л.)

5. Ignatov D., Janosi-Rancz К. Towards a framework for near-duplicate detection in document collections based on closed sets of attributes //Acta Universitatis Sapientiae, Informática, 1, 2 (2009), P. 215-233. 0,98 п.л. (вклад автора 0,6 п.л.)

6. Кузнецов С. О., Игнатов Д.И. О поиске сходства Интернет-документов с помощью частых замкнутых множеств признаков //Труды 10-й национальной конференции по искусственному интеллекту с международным участием (КИИ'06). - М.:Физматлит, 2006. - С. 249-258. 0,48 п.л. (вклад автора 0,28 п.л.)

7. Kuznetsov S. О., Ignatov D. I. Concept Stability for Constructing Taxonomies of Web-site Users //Proc. Satellite Workshop "Social Network Analysis and Conceptual Structures: Exploring Opportunities" at the 5th International Conference Formal Concept Analysis (ICFCA'07) / Ed. by S. Obiedkov, C. Roth., Clermont-Ferrand, France, 2007. - P. 19-24. 0,25 п.л. (вклад автора 0,15 п.л.)

8. Игнатов Д. И. Выбор вариантов с помощью методов Анализа Формальных Понятий // Труды научно-практической конференции "1-я Международная конференция по бизнес-информатике". — ГУ-ВШЭ, Звенигород, 2007. - С. 234-239. 0,2 п.л.

9. Кузнецов С. О., Игнатов Д. И. Методы разработки данных (Data Mining) для рекомендательной системы Интернет-рекламы//Труды 11-ой национальной конференции по искусственному интеллекту с международным участием (КИИ-2008).Т.2. - М.: Ленанд, 2008. - С. 34-42. 0,46 п.л. (вклад автора 0,3 п.л.)

10. Ignatov D. I., Kuznetsov S. О.. Concept-based Recommendations for Internet Advertisement //In Proceedings of The Sixth International Conference Concept Lattices and Their Applications (CLA'08) / Ed. by R. Belohlavek, S. 0. Kuznetsov. - Olomouc, Czech Republic, 2008. - P. 157-166. 0,53 п.л. (вклад автора 0,35 п.л.)

11. Игнатов Д. И., Кононыхина О. Н. Решетки формальных понятий для анализа данных социологических опросов. // Сборник научных трудов V-й Международной научно-технической конференции "Интегрированные модели и мягкие вычисления в искусственном интеллекте". Т1. — М.: Физматлит, 2009. — С. 230-240. 0,5 п.л. (вклад автора 0,3 п.л.)

12. Ignatov D. I., Kuznetsov S. О. Frequent Itemset Mining for Clustering Near Duplicate Web Documents // Proc. 17th International Conference on Conceptual Structures (ICCS'09) / Ed. by S. Rudolph, F. Dau, and S. O.Kuznetsov. - Springer-Verlag, 2009. - Vol. 5662. - P. 185-200. (Lecture Notes in Artificial Intelligence). 0,93 п.л. (вклад автора 0,6 п.л.)

13. Игнатов Д. И./Кузнецов С. О. Бикластеризация объектно-признаковых данных на основе решеток замкнутых множеств //Труды 12-ой национальной конференции по искусственному интеллекту с международным участием (КИИ-2010).Т.1. - М.: Физматлит, 2008. - С. 175-182. 0,32 п.л. (вклад автора 0,2 п.л.)

14. Игнатов Д. И., Каминская А. Ю., Магизов Р. А., Метод скользящего контроля для оценки качества рекомендательных Интернет-сервисов//Труды 12-ой национальной конференции по искусственному интеллекту с международным участием (КИИ-2010).Т.1. ~ М.: Физматлит, 2010. — С. 183-191. 0,31 п.л. (вклад автора 0,2 п.л.)

Лицензия ЛР № 020832 от 15 ноября 1993 г. Подписано в печать октября 2010 г. Формат 60 х 84/16 Бумага офсетная. Печать офсетная. Усл. печ. л. 1 Тираж 100 экз. Заказ №

Типография издательства Государственного университета - Высшей школы экономики, 125319, г. Москва, Кочновский проезд, д.З

Введение

1 Кластеризация и бикластеризация

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

1.2 Типы данных.

1.3 Типы бикластеров.

1.4 Структура бикластеров.

1.5 Алгоритмические стратегии поиска.

1.6 Классификация методов бикластеризации.

1.7 Программные средства бикластеризации.

1.8 Прикладные задачи.

1.9 Обсуждение.

2 Прикладные задачи и их вычислительные модели

2.1 Поиск сходства текстовых документов с помощью частых замкнутых множеств признаков.

2.1.1 Постановка задачи.

2.1.2 Описание вычислительной модели.

2.1.3 Методика оценки качества поиска.

2.2 Анализ данных о посещаемости сайтов с помощью АФП.

2.2.1 Постановка задачи и математическая модель.

2.2.1.1 Пути решения и возникающие проблемы.

2.2.1.2 Критерии отбора шумоустойчивых и релевантных понятиий

2.2.2 Методика оценки качества шумоустойчивых свойств способов отбора релевантных понятий.

2.3 Формирование бикластеров для рекомендательной системы Интернет-рекламы.

3 Разработка и исследование методов и алгоритмов бикластеризации на основе замкнутых множеств и их программная реализация

3.1 Ассоциативные правила в контексте бикластеризации.78

3.1.1 Ассоциативные правила: общий взгляд.

3.1.2 Связь ассоциативных правил и бикластеризации.

3.2 Связь опеределения бикластера в моделях бикластеризации для задач генной экспрессии и АФП . <.

3.3 Алгоритм бикластеризации на основе объектных и признаковых замыканий

3.4 Эмпирический анализ эффективности алгоритма бикластеризации на основе объектных и признаковых замыканий.

4 Машинные эксперименты и результаты

4.1 Поиск сходства Интернет-документов с помощью частых замкнутых множеств признаков.

4.1.1 Программная реализация и компьютерные эксперименты.

4.1.1.1 Оценка результатов с точки зрения полноты и точности поиска.

4.1.1.2 Сравнение результатов работы метода ЕРтах с результатами, полученными с помощью системы С1^о.

4.1.2 Выводы и направления дальнейшей работы.

4.2 Разработка и апробация системы поиска дубликатов в текстах проектной документации.

4.2.1 Постановка задачи и актуальность.

4.2.2 Описание системы.

4.2.3 Методы поиска дубликатов.

4.2.4 Реализация поиска дубликатов в системе.

4.2.4.1 Проведение анализа документов в Системе.

4.2.5 Подбор параметров и тестирование.

4.2.6 Направления дальнейшей работы.

4.3 Построение таксономий групп посетителей сайтов с помощью АФП . . . 126 4.3.1 Построение таксономий аудиторий веб-сайтов.

4.3.2 Исследование шумоустойчивых свойств индексов отбора релевантных понятий.

4.3.3 Выводы.

4.4 Формирование бикластеров для рекомендательной системы

Интернет-рекламы.

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

Существует широкий спектр задач, в которых требуется выявлять кластеры с сохранением объектно-признакового описания данных. К таким задачам относятся выявление групп генов, обладающих общими свойствами, поиск групп посетителей со схожими интересами для рекомендательных систем, выявление Интернет-сообществ, научных сообществ, задача анализа социальных сетей, построение автоматических каталогов и рубрикаторов в информационных системах, поиск сходства документов. Методы кластеризации, разработанные для этих целей, лежат в области кластер-анализа и получили свое собственное название - бикластеризация. Приставка би- указывает на двукомпонентность выявляемых методами бикластеризации кластеров. Например, для генетических данных первым компонентом такого кластера является множество генов, а вторым - множество экспериментов, в которых они проявляли себя сходным образом. Термин "бикластеризация" впервые упомянут в работе [61], и хотя похожие формулировки и методы встречались ранее (см. [40] ), мы, тем не менее, будем использовать это собирательное название для всей группы методов, описываемых в данной работе, которые применяются для построения таких двукомпонентных кластеров.

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

В связи с вышеизложенным, основная цель диссертационной работы работы состоит в разработке моделей, методов и алгоритмов бикластеризации на основе решеток замкнутых множеств. Другими целями являются программная реализация эффективных алгоритмов поиска бикластеров для решения практических задач анализа данных и исследование взаимосвязи различных существующих моделей и методов бикластеризации, построение их классификаци и таксономии. Последняя цель предполагает описание состояния дел в разных областях исследований, в которых нашли применение методы бикластеризации, выявление таких методов, выработку единых принципов их оценки, построение их адекватной классификации. Это помогает определить методы, которые подходят для решения задач анализа Интернет-данных (Web-mining), а именно выявление групп посетителей сайтов со сходными интересами или поведением, построения таксономий аудитории сайтов, а также задач анализа социальных сетей в Интернете и поиска нечетких веб-дубликатов. Отправной точкой такого исследования является прикладная математическая дисциплина Анализ Формальных Понятий [36]. В рамках этой области сформулировано математическое определение формальных понятий, описано построение их иерархий. Исходно формальное понятие является парой вида (объем, содержание), где под объемом понимается некоторое множество объектов, а под содержанием — множество их общих признаков. Как видим, это определение напоминает описание бикластера. Исходные данные в АФП представляются в виде объектно-признаковой матрицы, состоящей из нулей и единиц, а формальным понятием является максимальный прямоугольник такой матрицы, заполненный единицами. Это означает, что данное подмножество объектов обладает всеми признаками некоторого подмножества признаков. Далее для такого множества понятий строится их иерархия, представляющая собой полную решетку, называемую решеткой понятий. Существует ряд работ, исследующих возможности "ослабления" требований к определению формального понятия, например, шумоустойчивые понятия (в смысле [21]). Необходимость такого рода ослаблений вызвана жесткой структурой формальных понятий, требующей наличия всех признаков из содержания понятия у объектов его объема, однако в случае наличия шума возможны "выпадения" некоторых признаков из содержания понятия. В работах [15,16] предложен подход, использующий нечеткие решетки понятий, в котором значения исходных данных лежат в диапазоне [0, 1]. Причина, по которой целесообразно использование нечетких решеток, — возможность более точного описания исходных данных, например, частоты посещения пользователем веб-сайта. Еще одним важным требованием при решении задач бикластеризации является получение относительно небольшого числа бикластеров, т.к. в случае АФП подхода их количество экспоненциально растет от размера входа. Отчасти проблема порождения большого числа формальных понятий решена путем введения индекса устойчивости формального понятия [53]. В этом случае среди множества порожденных понятий отбираются те из них, для которых индекс устойчивости превышает некоторый заданный* порог. Проблемы отбора релевантных задаче формальных понятий (бикластеров) также обсуждаются в рамках работы. Что касается моделей "бокс-кластеризации", описанных в [60], то для них характерно наличие сходного подхода и параметров, которые используются для выявления шумоустойчивых понятий [21]. Также для моделей этого типа характерно наличие перекрытий или пересечений бикластеров, степень которых оказывается существенной при решении ряда задач. В задачах бикластеризации, решаемых генетиками, используется похожий аппарат, но не всегда значения входной матрицы являются булевыми, как в работе [13], в большинстве случаев они положительные вещественные (например, метод ОРЭМ [17] ). Это в свою очередь приводит к использованию статистических свойств данных при построении моделей (см. [83]). У большинства из этих методов, применяемых в биоинформатике, имеются похожие недостатки, например, проблема определения числа кластеров, проблема локального оптимума вследствие использования жадной стратегии поиска [28]. Отдельно стоят методы спектральной кластеризации, которые изначально опираются на спектральные свойства матричного представления графа связей между объектами. В последнее время эти методы активно применяются в Интернет-маркетинге, где связи "рекламодатели-слова" представлены двудольным графом [97] и помогают отыскивать потенциальных рекламодателей среди тех, кто не использует некоторые из слов, что купили их конкуренты. Фактически эти методы искусственно адаптированы для задачи бикластеризации, поскольку для найденных кластеров приходится восстанавливать их объектно-признаковую структуру (т.е. бикластер). Для большинства методов разработанных вне сообщества АФП характерно отсутствие иерархии порожденных кластеров, что затрудняет их анализ исследователем. В рамках работы будет предпринята попытка установить возможность построения такой иерархии для остальных методов бикластеризации, такая иерархия предположительно будет носить решеточный или полурешеточный характер. Также исследователями в области бикластеризацпп не используется аппарат ассоциативных правил, являющийся ключевыми в Data Mining при поиске признаковых зависимостей. Ассоциативные правила возможно порождать на признаковых описаниях бикластеров, и наоборот, приводятся теоретические оценки плотности таких бикластеров. Помимо исследователей, использующих аппарат ассоциативных правил в Data Mining, существует сообщество FIMI (Frequent Itemset Mining Implementation), изучающее проблемы поиска частых (замкнутых) множеств признаков в больших базах данных. Отметим, что замкнутые множества признаков являются в точности содержаниями формальных понятий. Поэтому как модель бикластеризации методы FIMI будут включены в обзор. Максимальные замкнутые множества признаков составляют только часть замкнутых, а потому их можно рассматривать в качестве альтернативы способам сокращения числа формальных понятий для модели АФП. Еще одним из способов такого сокращения является использование решеток-айсбергов, предложенных [79], этот подход аналогичен отбору ассоциативных правил в Data Mining по порогу величины поддержки.

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

1. Разработка математической модели и метода бикластеризации на основе решеток замкнутых множеств.

2. Исследование различных моделей и методов бикластеризации, родственных решеточным, изучение их взаимосвязи, построение их классификации.

3. Разработка на основе модели и метода алгоритмов и программных модулей бикластеризации.

4. Проведение анализа особенностей разработанного подхода на примере решения трех задач анализа Интернет-данных (поиск сходства документов, исследование посещаемости сайтов и разработка рекомендательных систем).

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

6. В ряде случаев провести сравнительный анализ особенностей методов и установить связь между используемыми вычислительными моделями.

Научная новизна работы определяется полученными в ходе решения задач исследования новыми результатами.

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

2. Установлена связь между методами бикластеризации и ассоциативными правилами. Даны теоретические оценки мер плотности и разреженности бикластеров, получаемых на основе ассоциативных правил.

3. Выявлена эквивалентность определений бикластера в некоторых моделях в биоинформатике и в АФП.

4. Предложена модель сходства текстовых документов, сформулированная в терминах частых замкнутых множеств признаков и АФП.

5. Предложена модель построения таксономий групп пользователей веб-сайтов на основе решеток формальных понятий. Указаны наилучшие способы отбора релевантных понятий для построения таких таксономий.

6. Предложена модель рекомендательной системы на основе использования морфологической структуры словосочетаний (признакового пространтсва).

7. Предложена модель рекомендательной системы на основе методов бикластеризации и ближайшего соседа, а также методика оценки качества результатов таких систем.

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

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

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

• BicAT — область применения биоинформатика,

• Concept Explorer, ToscanaJ, Galicia — сообщество АФП,

• Coron — Data Mining (ассоциативные правила и частые множества признаков),

• Cluto, Metis — графовая кластеризация,

• и Chaco — спектральная кластеризация.

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

Положения, выносимые на защиту:

1. Разработка математической модели и метода бикластеризации на основе решеток замкнутых множеств;

2. Практическая значимость и эффективность предложенных моделей и методов для анализа Интернет-данных;

3. Выявление связи бикластеризации с АФП, поиском ассоциативных правил и другими моделями бикластеризации.

Апробация работы. Основные результаты работы докладывались и обсуждались на следующих научных конференциях и семинарах:

1. Научном семинаре Лаборатории анализа и выбора решений, ГУ-ВШЭ, 2010

2. Научном семинаре "Математические модели информационных технологий" кафедры анализа данных и искусственного интеллекта, ГУ-ВШЭ, 2010

3. Научно-технической конференции студентов, аспирантов и молодых специалистов "Информационные технологии в бизнесе", ГУ-ВШЭ, 2006 (доклад отмечен дипломом)

4. 10-й национальной конференции по искусственному интеллекту (КИИ'2006), Обнинск, 2006

5. Научно-технической конференции "25 лет исследований по ДСМ-методу: логика, анализ данных, интеллектуальные системы (ДСМ-2006)" РГГУ и ВИНИТИ РАН, Москва, 2006

6. Четырежды на научно-технической конференции студентов, аспирантов и молодых специалистов "Информационные технологии в экономике, бизнесе, управлении", ГУ-ВШЭ, 2007, 2008, 2009 и 2010;

7. Второй'международная молодежной конференции «Искусственный интеллект: философия, методология и инновации», Санкт-Петербург, СПбГУ, 2007 (диплом: лучший доклад)

8. 5-ой международной конференции по Формальному Анализу Понятий, (5th International Conference on Formal Concept Analysis: Clermont-Ferrand, France, February 12-16, 2007) в рамках семинара по анализу социальных сетей (Social Network Analysis and Conceptual Structures: Exploring Opportunities)

9. 1-ой международной конференции по бизнес-информатике, ГУ-ВШЭ, Звенигород, 2007,

10. 11-ой национальной конференции по искусственному интеллекту с международным участием (КИИ-2008), г. Дубна, Россия, 2008

11. 6-ой международной конференции по решеткам понятий и их приложениям (The Sixth International Conference Concept Lattices and Their Applications (CLA'08)), Olomouc, Czech Republic, 2008

12. 5-й Международной научно-технической конференции "Интегрированные модели и мягкие вычисления в искусственном интеллекте", Коломна, 2009

13. 17-й международной конференции по понятийным структурам (The 17th International Conference on Conceptual Structures, (ICCS'09)), Москва, 2009

Диссертация состоит из введения, четырех глав, заключения и списка литературы.

Выводы и дальнейшие исследования

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

Предложенные подходы вкупе с методами Data Mining помогают улучшить рекомендации и предлагают хорошее средство частотного ранжирования, что удобно при составлении Top-N рекомендаций. Еще одно преимущество подхода состоит в возможности выявить связанные рекламные слова, но не используемые по каким-то причинам рекламодателями. Результаты бикластеризации на основе АФП показывают возможность выявления относительно крупных рекламных рынков (> 20 участников), описанных в терминах фирм-участников и рекламных слов.

В качестве дальнейших исследовательских задач отметим следующие:

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

• использование готовых онтологий типа WordNet для построения метаправил.

Заключение

В работе приведен обзор методов бикластеризации, построена их решеточная таксономия. Проведено уточнение и расширение оснований классификации бикластеров для построения более полной и точной таксономии алгоритмов и методов. Показана связь ассоциативных правил и бикластеризации. Показано, что некоторые методы разработки данных (Data Mining), такие как поиск частых множеств признаков, могут рассматриваться как методы бикластеризации. Установлена эквивалентность определения бикластеров, используемых для решения задач генной экспрессии и формальных понятий. Предложен новый алгоритм бикластеризации, основанный на решетках замкнутых множеств, его эффективность показана в сравнении с алгоритмами АФП в серии экспериментов на реальных массивах^ данных. Свойства определения бикластера на основе объектных и признаковых замыканий позволяют утверждать, что формальные понятия содержатся (не теряются) в смысле покомпонентого вложения в некотором бикластере множества бикластеров, порожденных по тем же исходным данным. Алгоритм обладает полиномиальной оценкой времени работы от размера входа, а число бикластеров не превышает количества пар "объект-признак", принадлежащих исходному отношению.

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

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

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

Предложена модель, использующая частые (замкнутые) множества признаков и АФП для поиска документов-дубликатов, экспериментально подтверждена обоснованность данной вычислительной модели на массиве РОМИП. Проведено сравнение с одним из алгоритмов системы СЬиТО, предназначенной для кластеризации текстовых документов. Эксперименты показывают значительное превосходство предложенного автором метода поиска дубликатов над алгоритмами из системы СЬиТО по временной сложности и аналогичные результаты по точности и полноте поиска.

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

В качестве возможных направлений дальнейших исследований отметим

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

• Исследование связи других методов: шумоустойчивые понятия и бокс-кластеризация, АФП и спектральная кластеризация.

1. Биркгоф Г. Теория решеток. — М.:Наука, 1989.

2. Евтушенко С.А., Система анализа данных "Concept Ехр1огег"//Труды 7-ой Национальной Конференции по Искусственному Интеллекту (КИИ-2000), Москва, 2000, с.127-134.

3. Игнатов Д.И., Кузнецов С.О. О поиске сходства Интернет-документов с помощью частых замкнутых множеств признаков // Труды 10-й национальной конференции по искусственному интеллекту с международным участием (КИИ'06). -М.:Физматлит, 2006, Т.2, стр.249-258.

4. Кедров С.А. , Кузнецов С.О. Исследование групп пользователей Интернет-ресурсами методами анализа формальных понятий и разработки данных (Data Mining) //Бизнес-информатика, №1 2007, стр. 45-51.

5. Кузнецов С.О. Устойчивость как оценка обоснованности гипотез, получаемых на основе операционального сходства// НТИ. Сер.2 1990. - N12. - С.21-29.

6. Объедков С. А., Алгоритмы и методы теории решеток и их применение в машинном обучении, Диссертация на соискание ученой степени кандидата технических наук. РГГУ, 2003.

7. Самохин М.В., Машинное обучение на узорных структурах, Диссертация на соискание ученой степени кандидата технических наук. ВИНИТИ, 2006.

8. Agrawal, R., Mannila, Н., Srikant, R., Toivonen, H., and Verkamo, A. I. Fast Discovery of Association Rules. Advances in Knowledge Discovery, and Data Mining, U. Fayyad et al., eds., pp. 307-328, Menlo Park, Calif.: AAAI Press, 1996.

9. Agrawal, R., Imielinski, T., Swami, A. Mining association rules between sets of items in large databases. Proceedings, ACM SIGMOD Conference on Management of Data, Washington D.C., pp. 207-216, 1993.

10. Agrawal, R., Gehrke, J., Gunopulos, D., and Raghavan, P. Authomatic subspace clustering of high dimensional data for data mining applications, Proc. ACM SIGMOD, pp. 94-105, 1998.

11. Abou-Rjeili, A. and Karypis, G. Multilevel Algorithms for Partitioning Power-Law Graphs. IEEE International Parallel & Distributed Processing Symposium (IPDPS) (in press), 2006.

12. Barkow, S., Bleuler, S., Prelic, A., Zimmermann, P., and Zitzler E. BicAT: a biclustering analysis toolbox, Bioinformatics, 2006 22(10):1282-1283.

13. Belohlavek, R. Lattice type fuzzy order and closure operators in fuzzy ordered sets. Proc. Joint 9th IFSA World Congress and 20th NAFIPS International Conference, 2001, Vancouver, Canada, IEEE Press, pp. 2281-2286.

14. Belohlavek, R., Vychodil, V. What is a fuzzy concept lattice? In: Proc. CLA 2005, 3rd Int. Conference on Concept Lattices and Their Applications, September 7-9, 2005, Olomouc, Czech Republic, pp. 34-45.

15. Berkhin, P. Survey of clustering data mining techniques. Technical report, Accrue Software, San Jose, CA, 2002.

16. Besson, J., Robardet, C., J-F. Boulicaut. Constraint-based mining of formal concepts in transactional data. In: Proceedings of the 8th Pacific-Asia Con-ference on Knowledge Discovery and Data Mining, 2004.

17. Besson, J., Robardet, C., Boulicaut, J-F., and Rome, S. Constraint-based bi-set mining for biologically relevant pattern discovery in microarray data. Intelligent Data Analysis journal, 9(1) :59-82, 2004.

18. Broder, A. Z., On the resemblance and containment of documents, in Proc. Compression and Complexity of Sequences (SEQS: Sequences'97)

19. Broder, A. Z., Glassman, S. C., Manasse, M. S. and Zweig, G. Syntactic clustering of the web. In Proceedings of WWW6'97, pages 391-404. Elsevier Science, April 1997.

20. Broder, A., Charikar, M., Frieze, A.M., Mitzenmacher, M. Min-Wise Independent Permutations, in Proc. STOC, 1998.

21. Broder A., Identifying and Filtering Near-Duplicate Documents, in Proc. Annual Symposium on Combinatorial Pattern Matching, 2000.i

22. Busygin, S., Jacobsen, G., and Kramer, E. Double conjugated clustering applied o leukemia microarray data. In Proceedings of the 2nd SI AM International Conference on Data Mining, Workshop on Clustering High Dimensional Data, 2002.

23. Califano, A., Stolovitzky, G., and Tu, Y. Analysis of gene expression microarays for phe-notype classification. In Proceedings of the International Conference on Computacional Molecular Biology, pages 75-85, 2000.

24. Cheng, Y. and Church, G. Biclustering of expression data. Proc. Int. Conf. Intell. Syst. Mol. Biol. pp. 93-103, 2000.

25. Cho,J., Shivakumar, N., Garcia-Molina, H. Finding replicated web collections, 1999

26. Chowdhury, A., Frieder, O., Grossman, D.A., and McCabe, M.C. Collection statistics for fast duplicate document detection, ACM Transactions on Information Systems, 20(2): 171-191, 2002

27. Davey B.A., Priestley H. A. Introduction to Lattices and Order.— Cambridge: Cambridge University Press, 2002.

28. Dhillon, I.S. Co-clustering documents and words using bipartite spectral graph partitioning. In Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'01), pages 269-274, 2001.

29. Dhillon, I.S. , Mallela, S., and Modha, Dh.S. Information-theoretical co-clustering. In Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'03), pages 89-98, 2003.

30. Eckes, T., and Orlik, P., An Error Variance Approach to Two-mode Hierachical Clustering, Journal of Classification, 10, 51-74.

31. Freeman, L.: Cliques, Galois lattices, and the structure of human social groups. Social Networks 18 (1996) 173-187.

32. Ganter, B., and Wille, R. Formal Concept Analysis: Mathematical Foundations, Springer, 1999.

33. Getz, G., Levine, E., and Domany, E. Coupled two-way clustering analysis of gene microarray data. In Proceedings of the Natural Academy of Sciences USA, pages 12079-12084, 2000.

34. Grahne, G. and Zhu, J. Efficiently Using Prefix-trees in Mining Frequent Itemsets, in Proc. FIMI Workshop, 2003.

35. Han, J. and Kamber, M. Data Mining: Concepts and Techniques. Morgan Kaufmann, 2001.

36. Hartigan, J.A. (1972). "Direct clustering of a data matrix". Journal of the American Statistical Association 67 (337): 123-9.

37. Hasnah, Ah.M. A New Filtering Algorithm for Duplicate Document Based on Concept Analysis.Journal of Computer Science, Vol. 2 Issue 5, pp. 434-440, 2006.

38. Haveliwala, T.H., Gionis, A., Klein, D., and Indyk, P. Evaluating Strategies for Similarity Search on the Web, in Proc. WWW'2002, Honolulu, 2002.

39. Hendrickson, B. and Leland, R. The Chaco User's Guide: Version 2.0, Sandia Tech Report SAND94-2692, 1994.

40. Hoad, T., and Zobel, J. Methods for identifying versioned and plagiarized documents. In Journal of the American Society or Information Science and Technology, Vol 54, I 3, 2003.

41. Hofmann, Th. and Puzicha, J. Latent class models for collaborative filtering. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 668-693, 1999.

42. Ihmels, J. et al. Defining transcription modules using large-scale gene expression, data. Bioinformatics, 20, 1993-2003, 2004.

43. Ilyinsky, S., Kuzmin, M., Melkov, A., Segalovich, I. An efficient method to detect duplicates of Web documents with the use of inverted index, in Proc. 11th Int. World Wide Web Conference (WWW'2002).

44. Karypis G. CLUTO. A Clustering Toolkit. University of Minnesota, Department of Computer Science Minneapolis, MN 55455, Technical Report: №02-017, November 28, 2003

45. Klugar, Y., Basri, R., Chang, J. T. and Gerstein, M. Spectral biclustering of microar-ray data: coclustering genes and conditions. In Genome Research, volume 13, pages 703-716, 2003.

46. Kolcz, A., Chowdhury, A., and Alspector, J. Improved Robustness of Signature-Based Near-Replica Detection via Lexicon Randomization, in Proc. KDD'04, Seattle, 2004.

47. Kuznetsov, S.O. and Obiedkov, S.A. Comparing Performance of Algorithms for Generating Concept Lattices, Journal of Experimental and Theoretical Artificial Intelligence, vol. 14 (2002), pp. 189-216.

48. Kuznetsov, S.O.: On stability of a formal concept. In SanJuan, E., ed.: JIM, Metz,France (2003)

49. Kuznetsov, S. 0.: On stability of a formal concept. Annals of Mathematics and Artificial Intelligence 49, 101-115 (2007).

50. Kuznetsov, S. O., Ignatov, D. I. Concept Stability for Constructing Taxonomies of Web-site Users//Proc. Satellite Workshop "Social Network Analysis and Conceptual

51. Structures: Exploring Opportunities "at the 5th International Conference Formal Concept Analysis (ICFCA'07), Clermont-Ferrand, P. 19-24, 2007.

52. Lazzeroni, L. and Owen, A. Plaid models for gene expression data. Technical report, Stanford University, 2000.

53. Luxenburger M. Implications partielles dans un contexte. Mathématiques, Informatique et Sciences Humaines, 113 (29) : 35-55, 1991.

54. Liu, J. and Wang, W. Op-cluster: Clustering by tendency in high dimensional space. In Proceedings of the 3rd IEEE International Conference on Data Mining, pages 187-194, 2003.

55. Madeira, S.C. and Oliveira, A. L. "Biclustering Algorithms for Biological Data Analysis: A Survey", IEEE/ACM Transactions on Computational Biology and Bioinformatics, VOL 1, NO. 1, pp. 24-45 January-March 2004.

56. Mirkin, B.G.: Additive Clustering and Qualitative Factor Analysis Methods for Similarity Matrices. Journal of classifiacation. 4, 7-31 (1987).

57. Mirkin, B.G., Arabie, P., Hubert L.: Additive Two-Mode Clustering: The Error-Variance approach Revisited. Journal of classifiacation 12, 243-263 (1995).

58. Mirkin, B.G. Mathematical Classification and Clustering. Kluwer Academic Publishers, 1996.

59. Murali,T.M. and Kasif,S. Extracting conserved gene expression motifs from gene expression data. Pac. Symp. Biocomput., 8, 77-88, 2003.

60. NIST, "Secure Hash Standard Federal Information Processing Standards Publication 180-1, 1995.

61. Pasquier, N., Bastide, Y., Taouil, R., Lakhal, L. Efficient Mining of Association Rules Using Closed Itemset Lattices, Inform. Syst., 24(1), 25-46, 1999.

62. Prelic, A., Bleuer, S., Zimmermann, P., Wille, A., Bhlmann, P., Gruissem, W., Hennig, L., Thiele, L., Zitzler, E.: A systematic comparison and evalua-tion of biclustering methods for gene expression data. Bioinformatics 22(9), 1122-1129, 2006.

63. Potthast, M., Stein, B. New Issues in Near-duplicate Detection, in Data Analysis, Machine Learning and Applications, Springer, 2007

64. Pugh, W. and Henzinger, M. Detecting duplicate and near-duplicate files United States Patent 6658423 (December 2, 2003).

65. Rasmussen, M. and Karypis, G. gCLUTO: An Interactive Clustering, Visualization, and Analysis System. UMN-CS TR-04-021, 2004.

66. Roth, C., Obiedkov, S., Kourie, D.G.: "Towards Concise Representation for Taxonomies of Epistemic Communities CLA 4th International Conference on Concept Lattices and their Applications (2006)

67. Rome, J.E., Haralick, R.M.: Towards a formal concept analysis approach to exploring communities on the world wide web. In Ganter, B., Godin, R., eds.: ICFCA 2005. Volume 3403 of LNAI. (2005) 33-48

68. Roth, C., Bourgine, P.: Lattice-based dynamic and overlapping taxonomies: the case of epistemic communities. Scientometrics 69(2) (2006)

69. Sarwar, B. M. , Karypis, G., Konstan, J. A., Riedl, J. Analysis of recommendation algorithms for e-commerce, ACM Conference on Electronic Commerce, pp. 158-167, 2000.

70. Segal, E., Taskar, B., Gasch A., Nir Friedman, and Daphne Koller. Rich probabilistic models for gene expression. In Bioinformatics, volume 17 (Suppl. 1), pages S243-S252, 2001.

71. Segal, E., Taskar, B., Gasch, A., Friedman, N., and Koller, D. Decomposing gene expression into cellular processes. In Proceedings of the Pacific Symposium on Biocomputing, volume 8, pages 89-100, 2003.

72. Sheng, Q., Moreau, Y., and De Moor, B. Biclustering micrarray data by gibbs sampling. In Bioinformatics, volume 19 (Suppl. 2), pages iil96-ii205, 2003.

73. Shepard, R.N., and Arabie, P. Additive Clustering: Representation of Similarities as Comdinations of Discrete Overlapping Properties, Psyhological Review, 86, 87 -123 (1979).

74. Shivakumar, N., Garcia-Molina, H. Finding near-replicas of documents on the web. Proceedings of Workshop on Web Databases (WebDB'98), 1998.

75. Steinbach, M., Karypis, G. and Kumar, V. A Comparison of Document Clustering Techniques. KDD Workshop on Text Mining, 2000.

76. Stumme, G., Taouil, R., Bastide, Y., Pasqier, N. and Lakhal, L. Computing Iceberg Concept Lattices with Titanic. J. on Knowledge and Data Engineering, (42)2:189-222,2002.

77. Stumme, G. and Mâdche, A. FCA Merge: Bottom-Up Merging of Ontologies. Proc.l7th Intl. Conf. on Artificial Intelligence (IJCAI '01). Seattle, WA, USA, 225-230,2001.

78. Szathmary, L., Napoli, A. and Kuznetsov S. O. ZART: A Multifunctional Itemset Miner Algorithm. LORIA Research Report A05-R-013, Feb 2005.

79. Tanay, A., Sharan, R. and Shamir, R. Discovering statistically significant biclusters in gene expression data. In Bioinformatics, volume 18 (Suppl. 1), pages S136-S144, 2002.

80. Tanay., A., Sharan, R. and Shamir, R., "Biclustering Algorithms: A Survey In Handbook of Computational Molecular Biology, Edited by Srinivas Aluru, Chapman (2004)

81. Ungar, L. and Foster, D. P. A formal statistical approach to collaborative filtering. In Proceedings of the Conference on Automated Learning and Discovery (CONALD'98), 1998.

82. Wang, H., Wang, W., Yang, J., and Yu, Ph. S. Clustering by pattern similarity in large data sets. In Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, pages 394-405, 2002.

83. White, D.R., Duquenne, V.: Social network & discrete structure analysis: Introduction to a special issue. Social Networks 18 (1996) 169-172.

84. Wille R. Restructuring Lattice Theory: an Approach Based on Hierarchies of Concepts // Ordered Sets / Ed. by I. Rival — Dordrecht;Boston: Reidel, 1982,— P. 445-470.91. http://company.yandex.ru/academic/grant/datasetsdescription.xml

85. Yang, J., Wang, W., Wang, H., and Yu. P.S. ^-clusters: Capturing subspace correlation in a large data set. In Proceedings of the 18th IEEE International Conference on Data Engineering, pages 517-528, 2002.

86. Yang, J., Wang, W., Wang, H., and Yu. P.S. Enhanced biclustering on expression data. In Proceedings of the 3rd IEEE Conference on Bioinformatics and Bioengineering, pages 321-327, 2003.

87. Zaki, M. J. and Hsiao, Ch.-J. Efficient Algorithms for Mining Closed Itemsets and Their Lattice Structure, IEEE Transaction on Knowledge and Data Engineering, Vol 17, No. 4, pp. 462-478, 2005.

88. Zhao, Y. and Karypis, G. Empirical and Theoretical Comparison of Selected Criterion Functions for Document Clustering. Machine Learning, vol. 55, pp. 311-331, 2004.

89. Zhukov, L.E. Technical Report: Spectral Clustering of Large Advertiser Datasets Part I. Overture R&D, 2004.