Модели, алгоритмы и программные средства бикластеризации на основе замкнутых множеств тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Игнатов, Дмитрий Игоревич

• Игнатов, Дмитрий Игоревич
• кандидат технических наук
• 2010

Оглавление диссертации кандидат технических наук Игнатов, Дмитрий Игоревич

Введение

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

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Игнатов, Дмитрий Игоревич, 2010 год

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.