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

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

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

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

Компания “Спайлог” применяет в задаче исследованияаудитории целевого веб-сайта предложенные в работе методы построения решеточных таксономий, а компания “Кварта-ВК” успешно реализовала проектпо разработке системы поиска документов-дубликатов в текстах проектнойдокументации на основе предложенного в диссертационной работе подхода иметодики настройки и оценки качества такого поиска.

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

Работа продолжает развитие методовобъектно-признакового представления данных, на которых сходство, определяемое как алгебраическая операция с некоторыми свойствами, задается через общее признаковое описание объектов. Личный вклад диссертанта состоитв разработке оригинальных методов решения задачи построения приближенного описания объектно-признаковых кластеров (бикластеров) и реализацииэффективных программных средств, а также проведении исследований с использованием этих средств.АПРОБАЦИЯ РАБОТЫРезультаты работы докладывались на следующих научных семинарах иконференциях:1.

Научном семинаре Лаборатории анализа и выбора решений, ГУ-ВШЭ,2010 и научном семинаре “Математические модели информационныхтехнологий” кафедры анализа данных и искусственного интеллекта, ГУВШЭ, 20102. Научно-технической конференции студентов, аспирантов и молодых спе-8циалистов “Информационные технологии в бизнесе”, ГУ-ВШЭ, 2006 (доклад отмечен дипломом)3. Трижды на национальной конференции по искусственному интеллекту,КИИ-2006, Обнинск; КИИ-2008, Дубна; КИИ-2010, Тверь.4. Научно-техническая конференция “25 лет исследований по ДСМ-методу:логика, анализ данных, интеллектуальные системы (ДСМ-2006)”, РГГУи ВИНИТИ РАН, Москва, 20065. Четырежды на научно-технической конференции студентов, аспирантови молодых специалистов “Информационные технологии в экономике,бизнесе, управлении”, ГУ-ВШЭ, 2007, 2008, 2009 и 2010;6.

Второй международная молодежной конференции «Искусственный интеллект: философия, методология и инновации», Санкт-Петербург, СПбГУ, 2007 (диплом: лучший доклад)7. 5-ой международной конференции по Формальному Анализу Понятий, (5th International Conference on Formal Concept Analysis: ClermontFerrand, France, February 12-16, 2007) в рамках семинара по анализусоциальных сетей (Social Network Analysis and Conceptual Structures:Exploring Opportunities)8.

1-ой международной конференции по бизнес-информатике, ГУ-ВШЭ,Звенигород, 20079. 6-ой международной конференции по решеткам понятий и их приложениям (The Sixth International Conference Concept Lattices and TheirApplications (CLA’08)), Olomouc, Czech Republic, 200810. 5-й Международной научно-технической конференции “Интегрированные модели и мягкие вычисления в искусственном интеллекте”, Коломна, 200911. 17-й международной конференции по понятийным структурам (The 17thInternational Conference on Conceptual Structures, (ICCS’09)), Москва,200912. Летней школе по информатике Reasoning Web 2010: SemanticTechnologies for Software Engineering, TU-Dresden, Germany, 2010Публикации.

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

Общий объем работы — 163 страницы. Список литературы включает 93 названия.КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫВо введении обоснована актуальность исследуемой проблемы, сформулирована цель и задачи диссертационной работы, перечислены полученные входе работы результаты, их практическая ценность, представлены положения,выносимые на защиту, и описана структура диссертации.В первой главе приведены основные определения и результаты из области бикластеризации и кластеризации, теории упорядоченных множеств,теории решеток, анализа формальных понятий (АФП). Помимо сведений изАФП сформулированы определения и даны характеристики четырёх методовбикластеризации — метод BiMax из области биоинформатики, шумоустойчивые понятия, как идея расширения определения формальных понятий, устойчивых к ошибкам в данных, метод аддитивной бокс-кластеризации и поискчастых замкнутых множеств признаков, который был использован нами дляреализации подхода выявления документов (почти)дубликатов.Приведём основные определения и сведения из области бикластеризации и анализа формальных понятий, необходимые для наших целей.Под термином бикластеризация понимается широкий круг методов,а потому для него в научной литературе существует целый ряд синонимов: совместная кластеризация (simultaneous clustering), кокластеризация(co-clustering), двувходовая кластеризация (two-way clustering), кластеризация подпространства (subspace clustering), двумерная кластеризация (bidimensional) и бокс-кластеризация (box-clustering).

Повышенный интерес кбикластеризации и выделение ее в самостоятельную область анализа данных возник в связи с задачей анализа генетических данных (microarray dataanalysis). Поэтому в первой главе, прежде чем дать основные определенияиз области бикластеризации, мы описываем задачи анализа данных геннойэкспресси и то, как бикластеризация оказывается полезна для их решения.Фактически мы будем работать с матрицей размера на , элементыкоторой в общем случае представляют собой действительные числа, и будемсчитать, что строкам матрицы соответствуют некоторые объекты, а столбцам— признаки.Пусть дана матрица , — число строк, — число столбцов, ={1 , 2 , .

. . , } — множество строк, = {1 , 2 , . . . , } — множество столбцов. Будем использовать (, ) для обозначения матрицы . Если ⊆ и ⊆ подмножества строк и столбцов, соответственно, то = (, ) определяет подматрицу матрицы . Кластер строк есть подматрица матрицы вида = (, ), для которой подмножество строк проявляет “сходное поведение” вдоль всего множества столбцов. Кластер столбцов есть подматрицаматрицы вида = (, ), для которой подмножество столбцов проявляет “сходное поведение” вдоль строк.