Техническое задание на выполнение исследовательского проекта «Разработка методов построения таксономий объектов на основе решеток формальных понятий и методов бикластеризации»

	УТВЕРЖДЕНО
	Решением Бюро Совета Научного Фонда ГУ-ВШЭ от «30» января 2008 г., протокол № 1

ТЕХНИЧЕСКОЕ ЗАДАНИЕ

на выполнение исследовательского проекта

«Разработка методов построения таксономий объектов на основе решеток формальных понятий и методов бикластеризации»

№ 08-04-0022

по конкурсу Научного Фонда ГУ-ВШЭ «Учитель-Ученики» 2008-2009 гг.

Основание для проведения работы

Работа выполняется на основании решения Совета Научного Фонда ГУ-ВШЭ (протокол от 27.11.2007 г. № 2) в соответствии с результатами конкурса «Учитель-Ученики» 2008-2009 гг..
2. Направление совместных исследований

Информатика

3. Исполнители работы
Руководитель проекта - Объедков Сергей Александрович, доцент кафедры анализа данных и искусственного интеллекта отделения прикладной математики

Контактная информация о руководителе: (8(916)656-04-33, sergej.obj@gmail.com)

Исполнители:

Исполнители старше 30 лет:

нет

Исполнители моложе 30 лет:

из них:

– аспиранты нет

– студенты

Игнатов Дмитрий Игоревич, студент 2-го курса магистратуры отделения прикладной математики факультета бизнес-информатики ГУ-ВШЭ, idm-viniti@yandex.ru, 8(926)381-80-33

Селицкий Игорь Александрович, студент 2-го курса магистратуры отделения прикладной математики факультета бизнес-информатики ГУ-ВШЭ, selitsky@gmail.com, 8(926)412-35-46

Климушкин Михаил Алексеевич, студент 2-го курса бакалавриата отделения прикладной математики факультета бизнес-информатики ГУ-ВШЭ, klim290489@rambler.ru, 8(916)227-08-24

Новокрещенова Анастасия Владимировна, студентка 2-го курса бакалавриата отделения прикладной математики факультета бизнес-информатики ГУ-ВШЭ, novokreshenka@mail.ru, 8(926)840-98-56

Четвериков Дмитрий Сергеевич, студент 2-го курса бакалавриата отделения прикладной математики факультета бизнес-информатики ГУ-ВШЭ, dmchetverikov@yandex.ru, 8(926)430-82-33

Шамшурин Иван Сергеевич, студент 2-го курса бакалавриата отделения прикладной математики факультета бизнес-информатики ГУ-ВШЭ, fotzen@mail.ru, 8(926)825-99-09

Состав исполнителей проекта может изменяться в течение срока его выполнения.

Актуальность исследований

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

5. Цель, задачи и исходные данные (или информационная база) исследований

Цель исследования: Целью исследования является разработка новых и сравнительный анализ существующих методов бикластеризации в применении к построению таксономий объектов для различных предметных областей, а также адаптация этих методов, дающая возможность построения динамических таксономий, т.е. таксономий, позволяющих моделировать эволюцию соответствующих предметных областей во времени.
Задачи исследования: В работе над проектом будут исследованы методы, связанные с обобщенными описаниями объектов, например, в виде (гипер)графов с помеченными вершинами и ребрами. Модели анализа такого рода данных применимы в самых различных областях, таких как выявление социальных сообществ и групп сходных документов, науки о жизни и анализ конфликтов. В ходе работы над проектом предполагается развитие этих моделей в сторону допущения ограниченного «выпадения» отдельных элементов описания группы объектов у некоторых объектов из группы. Планируется разработка новых методов бикластеризации на основе решеток формальных понятий и изучение возможности использования аппарата ассоциативных правил на множествах признаков (являющегося одним из главных средств современных методов Data Mining) в задачах бикластеризации. В задачи исследования также входит разработка удобных средств визуализации таксономий с помощью диаграмм. Методы анализа данных, о которых идет речь, станут применимыми только при наличии эффективных алгоритмов для их реализации и поддержки. Разработка таких алгоритмов является одной из задач проекта.
Информационная база: Предполагается провести исследования по применению разрабатываемых методов бикластеризации в анализе таксономий сообществ посетителей ряда Интернет-ресурсов. Данные о посещении Интернет-ресурсов, о времени и длительности этих посещений предоставляются компанией Спайлог, группа также располагает данными о блогах французского сектора Интернет по политической тематике.

6. Новизна работы в сравнении с имеющимися в данной области исследованиями
В методах объектно-признаковой кластеризации (бикластеризации) не происходит потери информации о сути сходства между объектами, а каждая группа сходных объектов характеризуется множеством общих признаков. К таким методам относятся методы анализа данных, основанные на решетках понятиях. Эти методы имеют недостатки, связанные с игнорированием зашумленности в данных, а также связанные с большим числом порождаемых групп. Для устранения этих недостатков необходимо рассматривать модели с параметрами, задающими допустимое число исключений. Такие модели позволят порождать небольшое (например, заданное) число групп объектов с управляемым уровнем пересечения групп.
7. Методология исследований

Методы исследований основаны на:

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

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

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

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

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

8. Ожидаемые результаты исследований, форма их представления и предполагаемое использование результатов исследований в деятельности ГУ-ВШЭ

– в 2008 г

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

– в 2009 г.

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

9. Функции «молодых» участников в представленном проекте, научный результат этого проекта для молодого участника коллектива (научная статья, самостоятельная или в соавторстве, доклад на научной конференции, соавторство в аналитической записке для государственных органов и т.д.)
Молодые участники проекта изучают литературу по проекту, участвуют в обсуждении предлагаемых математических моделей бикластеризации, занимаются программной реализацией алгоритмов, проводят компьютерные эксперименты, участвуют в написании отчетов и публикаций, выступают с докладами на конференциях.
10. Общий объем финансирования проекта

Всего 1600000 руб., в том числе

в 2008 г. 800 000 руб.

в 2009 г. 800 000 руб.

Объемы финансирования распределяются по годам одинаково, не менее 50% от объема финансирования по статье «Заработная плата» в рамках общего объема финансирования по проекту должно ежегодно выделяться молодым участникам коллектива. Неизрасходованные в первый год выполнения проекта средства автоматически переходят на следующий год.

Финансирование проектов происходит в четыре этапа.

1-ый этап – с 10 января 2008 года до 15 октября 2008 года в объеме, равном 60 % от утвержденного Советом Фонда (протокол от 27.11.2007 г. № 2) объема финансирования проекта на 2008 год;

2-ой этап - до 15 декабря 2008 года в случае предоставления промежуточного научного отчета по первому этапу проекта в объеме, равном 40 % от утвержденного Советом Фонда или Бюро Совета Фонда объема финансирования проекта на 2008 год;

3-ий этап – с 10 января 2009 года до 15 октября 2009 года в случае положительной экспертизы промежуточного научного отчета в объеме, равном 60 % от утвержденного Бюро или Советом Научного Фонда объема финансирования проекта на 2009 год;

4-ый этап – до 15 декабря 2009 года в случае положительной экспертизы итогового научного отчета в объеме, равном 40 % от утвержденного Бюро или Советом Фонда объема финансирования проекта на 2009 год.
11. Основные условия и требования к выполнению работы
Результаты поддержанного проекта подлежат опубликованию (выпуску в свет). Опубликованными результатами поддержанного проекта являются вышедшие или принятые к печати монографии, сборники, научно-практические пособия, статьи в ведущих российских и зарубежных изданиях и иные способы выпуска в свет результатов поддержанного проекта. Авторы, входящие в состав коллектива поддержанного проекта, при опубликовании результатов исследований в рамках проекта должны упомянуть о поддержке своих исследований Научным Фондом.

Результаты итогового научного отчета (публикации) по проекту в обязательном порядке публикуются на сайте Научного фонда ГУ-ВШЭ.

Исполнители проекта представляют промежуточные и итоговые результаты проекта (в форме докладов и презентаций) на ежегодной школе-семинаре для «молодых» участников проектов «Учитель - ученики», организуемой ежегодно в ноябре после представления отчета и проведении его экспертизы. В обсуждении проектов участвуют эксперты и координаторы Научного Фонда ГУ-ВШЭ.

На завершающем этапе реализации проекта в обязательном порядке проводится обсуждение результатов проекта на научных семинарах в ГУ-ВШЭ в рамках выбранного направления исследований (это могут быть постоянно действующие семинары отдельных подразделений ГУ-ВШЭ, в том числе и семинар под руководством Ясина Е.Г.) и/или вне ГУ-ВШЭ. С целью привлечения заинтересованной аудитории Дирекцией корпоративного портала ГУ-ВШЭ и Научным Фондом ГУ-ВШЭ может быть оказана информационная поддержка мероприятия.
Руководитель работ,

доцент кафедры анализа данных

и искусственного интеллекта

отделения прикладной математики________________ (Объедков С.А.)

подпись