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

• Автор: Игнатов, Дмитрий Игоревич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Москва
• Количество страниц: 151 с.

Оглавление
Введение

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 Ассоциативные правила в контексте бикластеризации
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 Сравнение результатов работы метода РРтах с результатами, полученными с помощью системы СЫо. .
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 Построение таксономий групп посетителей сайтов с помощью АФП . . .
4.3.1 Построение таксономий аудиторий вебсайтов
4.3.2 Исследование шумоустойчивых свойств индексов отбора релевантных понятий.
4.3.3 Выводы
4.4 Формирование бикластеров для рекомендательной системы
Интернетрекламы
Заключение
Литература


Даны теоретические оценки мер плотности и разреженности бикластеров, получаемых на основе ассоциативных правил. Выявлена эквивалентность определений бнкластера в некоторых моделях в биоинформатике и в АФП. Предложена модель сходства текстовых документов, сформулированная в 'терминах частых замкнутых множеств признаков и АФП. Предложена модель построения таксономий групп пользователей веб-сайтов на основе решеток формальных понятий. Указаны наилучшие способы отбора релевантных понятий для построения таких таксономий. Предложена модель рекомендательной системы на основе использования морфологической структуры словосочетаний (признакового пространтсва). Предложена модель рекомендательной системы на основе методов бикластеризации и ближайшего соседа, а также методика оценки качества результатов таких систем. Теоретическая значимость работы заключается 1) в установлении взаимосвязей существующих моделей бикластеризацин, методов анализа данных на основе теории решеток и ассоциативных правил, а также выявлении эквивалентности некоторых вычислительных моделей, используемых при анализе данных генной экспрессии и АФП; 2) в построении таксономии существующих методов бикластеризации и ее расширении путем включения дополнительных критериев классификации новых и родственных методов; 3) в разработке модели бикластеризации на основе замкнутых множеств объектов и признаков, теоретическом исследовании ее свойств. Практическая значимость работы состоит в разработке эффективных моделей и методов поиска документов-дубликатов, построения таксономий веб-пользователей и моделей и алгоритмов рекомендательных систем на основе бикластеризации. Важным практическим достижением является программная реализация метода построения бикластеров, предложенного автором, количество таких бикластеров сравнимо с количеством пар во входной объектно-признаковой таблице, что существенно меньше теоретической оценки размера соответствующей решетки понятий. Два успешных внедрения предложенных методов позволяют говорить о востребованности и пользе полученных результатов. Компания “Спайлог” применяет в задачах исследования аудитории целевого веб-сайта предложенные в работе методы построения решеточных таксономий, а компания “Кварта-ВК” успешно реализовала проект по разработке системы поиска документов-дубликатов в текстах проектной документации на основе предложенного в диссертационной работе подхода и методики настройки и оценки качества такого поиска. Также отобраны и программно реализованы некоторые другие вычислительные процедуры построения бикластеров. В рамках работы не оставлены без внимания системы поиска бикластеров, приводится их обзор. Chaco — спектральная кластеризация. Для дальнейших исследований важным является изучение свойств бикластеров. А именно: исследование зависимости числа бикластеров от размеров входа, степени перекрытия бикластеров, густоты внутри бикластера и густоты вне; оценка возможности определения порядка на бикластерах, анализ их алгебраической структуры; изучение связи некоторых параметров бикластеризации с индексами типа устойчивости, отражающими различие в количестве признаков между соседними объектами. Выявление связи бикластеризации с АФП, поиском ассоциативных правил и другими моделями бикластеризации. Апробация работы. ГУ-ВШЭ, Звенигород, . КИИ-), г. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Во введении раскрывается актуальность темы диссертации, формулируются проблемы исследования, предмет исследования, определяется цель работы, описываются методы исследования, излагаются основные научные результаты, обосновывается теоретическая и практическая значимость работы, даётся её общая характеристика. В Главе 1 — “Кластеризация и бикластеризация” описана постановка задачи бикластерзации, указано на ее ключевую роль в анализе данных генетической экспрессии. Приводятся основания для классификации методов и моделей бикластеризации. Определяются типы бикластеров, их структура, стратегии поиска алгоритмов и области значений исходных данных.