Аддитивная бокс-кластеризация
В работе [56] предложена модель аддитивной кластеризации для решения проблемы бикластеризации. Помимо прочего, данная работа интересна тем, что в ней приведена обширная библиография по моделям и методам бимодальной кластеризации (two-mode clustering), которая охватывает период с 1972 по 1993. В основу подхода автор положил модель аддитивной кластеризации ([69],[55]) и адаптировал ее для бимодальных данных (например, объектно-признаковых).
В ключевой статье [56] обсуждается еще один схожий подход ошибки дисперсии (error-variance approach), предложенный в [31], проводится сравнение с ним, показано как с помощью модели аддитивной бокс-кластеризации можно преодолеть проблемы, возникающие при его использовании. Первая проблема заключается в выборе "стандартного" значения близости, используемого при построении кластеров, а вторая — в возможности выявления перекрывающихся кластеров. Помимо преодоления этих недостатков, кстати, отмеченных авторами этого метода, в модели аддитивной бокс-кластеризации оценивается вклад каждого кластера в общую сумму квадратов входных данных.
Алгоритм Apriori
Рассмотрим алгоритм Apriori, ставший первым эффективным алгоритмом поиска частых множеств признаков. Алгоритм Apriori предназначен для поиска всех частых множеств признаков. Он является поуровневым, использует стратегию поиска в ширину и осуществляет его снизу-вверх. В алгоритме используются две структуры данных:
— для хранения множества кандидатов в частые множества признаков длины
и
— для хранения частых множеств признаков длины
Алгоритм 2.5.1. Apriori(Context,min_supp)
Процедура AprioriGen для
-элементных частых множеств признаков порождает их
-надмножества и возвращает только множество потенциально частых кандидатов.
Алгоритм 2.5.2. AprioriGen(
Алгоритм Apriori был разработан для извлечения частых множеств признаков из данных о покупках, которые обычно являются разреженными и слабо коррелированными. Для таких данных число частых множеств признаков невелико, и алгоритм работает очень хорошо. Позднее, когда возникла необходимость поиска частых множеств признаков в плотных, сильно коррелированных данных, оказалось, что Apriori неэффективно работает на таких массивах. Как следствие, для решения проблемы были предложены различные варианты оптимизации и расширения исходного алгоритма (например, Apriori-Close, Pascal, Zart).
Алгоритм BiMax
В обзоре[13] проводится систематическое сравнение пяти алгоритмов бикластеризации с предложенным авторами методом BiMax. И хотя каждый из алгоритмов взятых для сравнения придерживается своей собственной вычислительной модели, авторы обзора используют их только для анализа 0/1 данных. Преобразование значений в исходных наборах данных генной экспрессии к бинарным происходит путем нормализации их логарифмов и последующей дискретизации.
Алгоритм DR-miner
Все семейство бимножеств, упорядоченное по отношению
и верхним элементом
множество подрешеток из
и
Алгоритм 2.3.1. DR-miner
Алгоритм DR-miner начинает работу с полной решетки
и затем рекурсивно распространяет ограничения, используя функцию Prop. Далее проверяется соответсвие полученной подрешетки введенным ограничениям посредством функции Prune, и порождаются две новых подрешетки, благодаря функции Enum (см. Алгоритм 2.3.1).
Процедура Enumeration. Пусть
таким образом, где
или
возвращает один элемент
Процедура Pruning. Подрешетка более не рассматривается, если среди ее бимножеств нет удовлетворяющих ограничениям. Пусть функция
возвращает
тогда и только тогда, когда монотонному ограничению
(по отношению
Пусть функция
возвращает
тогда и только тогда, когда aнтимонотонному ограничению
(по отношению
Антимонотонное ограничение
используется в качестве
не является ни монотонным, ни антимонотонным ограничением.
применяется для того, чтобы элементы, не принадлежащие подрешетке (т.е., те элементы, которые могут быть включены в бимножества), могли содержать больше нулей на верхнем элементе, чем внутренние, принадлежащие нижнему элементу (элементы принадлежащие каждому бимножеству). Пусть функция
определяется следующим образом:
 |
В алгоритме DR-Miner используется функция
, определённая так.
Процедура Propagation.
и
могут быть использованы для уменьшения размера подрешетки посредством перемещения объектов из
в
или вне
и
 |
, определяемая как
называется листом, когда она содержит только одно бимножество, т.е.
Назад Содержание Вперёд
Алгоритмические стратегии поиска
Алгоритмы бикластеризации могут порождать либо один бикластер, либо несколько, в зависимости от типа задачи. Например, алгоритм Ченга и Черча [25] находит один бикластер за проход, а для нахождения следующих необходимо маскировать найденный случайными числами и выполнить повторный запуск алгоритма. Другие бикластерные подходы позволяют находить множество бикластеров за проход. Существуют также алгоритмы, которые позволяют осуществлять одновременное выявление бикластеров.
Принимая во внимание вычислительную сложность проблемы, было предложено большое число эвристик. Эти стратегии поиска можно разделить на пять классов:
итеративная комбинация кластеризации по строкам и столбцам;
стратегия разделяй и властвуй;
жадная стратегия итеративного поиска;
полное перечисление бикластеров;
определение параметров распределения.
Анализ данных посещаемости сайтов с помощью ФАП
С момента создания сайта перед его владельцами и, возможно, потенциальными рекламодателями встает вопрос учета количества посещений с целью определения популярности ресурса и выявления целевой аудитории. Сейчас рынок таких услуг довольно широко представлен рядом компаний, которые готовы предоставить владельцам сайтов различные счетчики посещений, учитывающие как количество посещений отдельными пользователями, так и их географию, текущее время и продолжительность посещения.
Как показывает развитие отрасли, для эффективного анализа структуры аудиторий сайтов статистической информации недостаточно. Владельца сайта часто интересуют подгруппы его целевой (постоянной) аудитории. Например, покупатели бытовой техники в Интернет-магазине могут отличаться по различным категориям (домохозяйки, лица, недавно сделавшие ремонт, или новоселы, владельцы заведений общепита и т.д.). Это дает владельцам сайтов возможность корректировать предлагаемые услуги, выбирать адекватные рекламные средства, выстраивать линейку продуктов и т.п.
Выводы о принадлежности к той или иной группе целевой аудитории можно сделать, анализируя поведение посетителей сайта, а именно, рассматривая посещение ими же других сайтов и выдвигая соответствующие гипотезы. Наш подход основан на применение решеток формальных понятий, неплохо зарекомендовавших себя при анализе структур научных сообществ и других, по сути, социологических исследованиях. Ниже мы опишем постановку задачи и спектр возможных путей ее решения, а также пути преодоления возникающих трудностей.
Постановка задачи
Компания Spylog — одна из ведущих фирм на российском рынке, специализирующаяся на сборе и анализе статистики посещаемости веб-сайтов. В рамках сотрудничества нами решается задача построения релевантной таксономии сайтов. В качестве данных для проведения экспериментов нам предложена выборка по статистике посещений 10000 сайтов с прилагаемым плоским тематическим каталогом по 59 категориям. Для конкретных экспериментов мы отобрали из них четыре сайта следующих тематик: сайт университета, сайт Интернет-магазина бытовой техники, сайт крупного банка, сайт автомобильного Интернет-салона.
Необходимо построить "внешнюю" и "внутреннюю" таксономии каждого из сайтов. Под "внешней" таксономией мы будем понимать иерархическую структуру аудитории целевого сайта, выявленную по данным посещений остальных сайтов выборки. Ей будет в точности соответствовать решетка формальныx понятий, построенная по контексту
— множество всех посетителей целевого сайта,
— множество всех сайтов выборки за исключением целевого сайта,
— отношение инцидентности
"ходил" на сайт
Под "внутренней" таксономией будем понимать иерархическую структуру аудитории целевого сайта построенную по данным посещений его собственных страниц (возможно сгруппированных по разделам). Соответствующий контекст определяется сходным образом
— множество всех посетителей целевого сайта,
— множество всех собственных страниц целевого сайта,
— отношение инцидентности
тогда и только тогда, когда посетитель
"ходил" на сайт
множество сайтов
множество посетителей
Исходные данные для построения "внешней" таксономии для каждого сайта представляются в виде файла записей следующего формата:
id; \\id посетителя;
last_ts; \\время первого захода на сайт;
first_ts; \\время последнего захода на сайт;
num; \\количество совершенных сессий за все время знакомства с сайтом.
Для построения внутренней таксономии используется аналогичная структура с дополнительным полем url_page, соответствующим посещенной странице данного сайта. По этим данными формируются описанные выше контексты. Ниже описываются способы отбора посетителей и сайтов для формирования контекстов.
Пути решения и возникающие проблемы
Несмотря на то, что выборка из 10000 сайтов сравнительно мала для российского Интернет-пространства, использование всей информации для анализа аудитории конкретного сайта влечет слишком большие вычислительные затраты. А построенные таксономии, представленные диаграммами решеток понятий, громоздки для визуального анализа и последующей интерпретации. Обсудим пути сокращения размера входных данных.
Отбор только тех посещений, которые превышают некоторый порог посещаемости. Это дает существенное сокращение числа объектов контекста, например, для 100000 посетителей порог посещаемости, поднятый до 20, может дать сокращение почти в 100 раз.
Отбор признаков (сайтов) можно также организовать по посещаемости, т.е. учитывать при составлении контекста только те сайты, на которых данные посетители бывали больше заданного числа раз. Таким образом, из контекста исключаются сайты, не релевантные для данной аудитории.
Целевой сайт также целесообразно рассматривать в терминах сайтов определенной тематики., например, в терминах сайтов газет или финансовых учреждений. Если учесть, что такие группы относительно невелики — 100-500 сайтов, то такой прием дает также существенное сокращение размера контекста.
Для контекста, построенного по внутренней структуре сайта, можно укрупнять признаки, уменьшая, тем самым, их количество. Например, если посетители сайта банка имеют личную страницу, то целесообразно считать все такие страницы одним признаком "личная страница". Аналогично можно поступить со страницами товаров, принадлежащих к одной товарной группе.
Предоставленные данные охватывают период около года, поэтому целесообразно выделить некий временной интервал и учитывать посещения, приходящиеся на него. Интервалом может быть месяц, день, время суток и т.п.
Но даже при таком сокращении размера входа, т.е. контекста, решетки понятий, а следовательно, и диаграммы имеют большие размеры и не слишком удобны для работы аналитика. Например, для контекста размера 4125×225 порождается 57 329 понятий.
Обсудим теперь, каким образом добиться уменьшения размера решетки на этом этапе, по возможности, без потери значимой информации.
Использование индекса устойчивости понятий для отбора наиболее устойчивых понятий [48], т.е. понятий, индекс устойчивости которых превышает заданный порог. Мы использовали пороги, начиная от 0.9, что соответствовало 100-200 наиболее устойчивым понятиям.
Применение отбора понятий по размеру объема, что соответствует построению решетки понятий, называемой айсбергом. Например, отбор 100 верхних понятий из всех понятий контекста, отсортированных по размеру объема.
Использование вложенных диаграмм, хотя и не позволяет сократить число понятий, но является удобным средством для визуализации решеток, учитывающим, например, разные тематики признаков. Например,
и
Возможность комбинирования отбора по устойчивости и построения вложенных диаграмм. См. работу [63]
"Склеивание" понятий на основе ассоциативных правил, т.е. фактически, добавление ассоциативного правила как импликации, что приведет к уменьшению размера решетки.
Использование импликаций и ассоциативных правил как дополнительное средство выявления зависимостей. Поиск наиболее интересных импликаций следует производить, исходя из расположения понятий в решетке.
Остановимся подробнее на понятии индекса устойчивости [48, 49], который мы используем для отбора интересных групп посетителей при построении таксономий. С одной стороны, индекс устойчивости формального понятия служит показателем независимости содержания от частных объектов объема (наличие которых в контексте зависит от случайных факторов). С другой стороны, индекс устойчивости показывает, насколько сильно объем понятия отличается от похожих меньших объемов (если такая разница мала, то объем относится к устойчивой категории). Отметим, что впервые понятие устойчивости было предложено в работе [5].
Определение 5.1 Пусть
— формальный контекст,
некоторое формальное понятие
понятия
определяется выражением
Очевидно, что
.
Даже если описание данных зашумлено, то понятия с индексом устойчивости, близким к 1, вероятно, объективно отражают реальное положение дел. Индекс устойчивости показывает, насколько стабильны интересы групп посетителей, даже если некоторые из более не активны.
Обсудим теперь важные для интерпретации особенности построения решеточных таксономий.
При отборе посетителей по порогу посещаемости есть опасность построить таксономию для поведения поисковых роботов, а не реальных людей, интересующих владельца сайта. Когда порог по посещаемости велик, а промежуток времени, в течение которого происходили посещения, короткий, мы, фактически, исследуем поведение "поисковых маньяков" и поисковых роботов. Поэтому необходимо устанавливать разумные пороги по посещаемости как сверху, так и снизу, а также целесообразно использовать относительные пороги.
Чтобы выявить схожие аудитории людей, не посещающих целевой сайт, можно расширить исходный контекст добавлением в него таких пользователей, причем таких, которые посещают сайты, уже входящие в контекст.
Работа одновременно с внутренней структурой "целевого" сайта и прочими сайтами (признаки — сайты из имеющегося десятитысячного списка и страницы целевого сайта). В случае с сайтом университета это позволит, например, сравнить устремления людей, интересующихся разными факультетами.
Работа с контекстом
Для построения исходных контекстов можно отбирать только те сайты из десяти тысяч, размер пересечений аудитории которых с аудиторией целевого сайта не ниже некоторого порога. Это даст сокращение размера контекста и, возможно, повысит релевантность результатов.
Результаты
Рассмотрим некоторые результаты, полученные нами в ходе анализа посещаемости сайта ГУ-ВШЭ за ноябрь 2006 года. Мы построили как внутреннюю, так и внешние таксономии сайта. В качестве внешних сайтов мы рассматривали ресурсы новостной тематики, финансовых и образовательных учреждений. Приведем пример внешней таксономии для посетителей ГУ-ВШЭ в терминах ресурсов новостных сайтов. Отметим, что рассматриваемый временной промежуток — месяц, а порог на число посещений сайта ГУ-ВШЭ каждым пользователем равен 20.
Рис. 5.4. Решетка айсберг для 25-ти самых крупных понятий
На диаграмме решетки-айсберга для 25- ти понятий, имеющих наибольших объем, видны узлы, соответствующие СМИ середины политического спектра, которые посещаются "всеми" и потому не выявляют социальных групп.
Рис. 5.6. Частично упорядоченное множество 25-ти самых устойчивых понятий
Решетка понятий по 25-ти самым устойчивым понятиям содержит некоторые социологически значимые группы посетителей, такие как АИФ ("желтая пресса"), Cosmopolitan, Эксперт (профессионально-аналитические обзоры).
Выводы
Первые результаты придают уверенность в том, что средства ФАП окажутся подходящими для решения задачи выявления сообществ посетителей сайтов. В качестве направлений дальнейшей работы стоит выделить учет временных характеристик посещений и их последовательности. Необходимо обратить внимание на средства визуализации, такие как диаграммы вложенных решеток.
Назад Содержание Вперёд
Ассоциативные правила: общий взгляд
Дадим основные определения.
Определение 2.32 Пусть дан контекст
— множество объектов,
— множество признаков (items),
— отношение инцидентности. Ассоциативным правилом контекста
называется выражение вида
Определение 2.33 Поддержкой (support) ассоциативного правила
называется величина
Значение
показывает, какая доля объектов
содержит
Определение 2.34 Достоверностью (confidence) ассоциативного правила
называется величина
Значение
показывает, какая доля объектов, обладающих
Для аналитика обычно интересны ассоциативные правила с поддержкой supp и степенью достоверности conf не ниже заданных значений min_supp и min_conf соответственно. Для решения этой задачи можно построить все частые множества признаков. Напомним, что множество признаков
называется частым, если оно принадлежит большому числу объектов, то есть
— некоторый порог. Для этапа нахождения частых множеств признаков можно использовать алгоритм Apriori.
Частое ассоциативное правило получают из частого подмножества признаков
разбиением его на два подмножества
,
) — заключением ассоциативного правила. При таком разбиении
на
и
нужно проследить за тем, чтобы достоверность ассоциативного правила
была не ниже заданной.
Отметим, что ассоциативные правила при значениях
и
являются импликациями рассматриваемого контекста. Иногда ассоциативные правила записывают в форме
Ассоциативные правила в контексте бикластеризации
В сообществе DataMining ассоциативные правила являются, пожалуй, одним из наиболее востребованных инструментов для исследования признаковых зависимостей. И хотя ассоциативные правила явно не относятся к методам бикластеризации мы не только укажем на их тесную связь с ФАП, но и покажем, как менее "жесткие", чем формальные понятия, бикластеры могут быть получены с помощью ассоциативных правил.
Одной из первых работ, положившей начало применению ассоциативных правил промышленного масштаба в середине 90-х годов прошлого века, была [10]. Однако ранее в анализе формальных понятий изучались так называемые частичные импликации [52], которые фактически и были переоткрыты как ассоциативные правила в сообществе DataMining. Появление раздела, посвященного задаче поиска ассоциаций, обосновано также тем, что, оказывается, с бискластеризацией их связывают не только теоретические рассмотрения, но и общие прикладные задачи.
Библиография
1
Биркгоф Г. Теория решеток. – М.:Наука, 1989.
2
Евтушенко С.А., Система анализа данных "Concept Explorer," труды 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
Кузнецов С.О., Игнатов Д.И., Объедков С.А., Самохин М.В. Порождение кластеров документов дубликатов: подход, основанный на поиске частых замкнутых множеств признаков. Интернет-математика 2005. Автоматическая обработка веб-данных. Москва: Яndex, 2005, стр. 302-319.
7
Объедков С.А., Алгоритмы и методы теории решеток и их применение в машинном обучении, Диссертация на соискание ученой степени кандидата технических наук. РГГУ, 2003.
8
Самохин М.В., Машинное обучение на узорных структурах, Диссертация на соискание ученой степени кандидата технических наук. ВИНИТИ, 2006.
9
R. Agrawal, H. Mannila, R. Srikant, H. Toivonen, and A. Inkeri Verkamo, “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.
10
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.
11
Amine Abou-Rjeili and George Karypis. Multilevel Algorithms for Partitioning Power-Law Graphs. IEEE International Parallel & Distributed Processing Symposium (IPDPS) (in press), 2006.
12
Badrul M. Sarwar, George Karypis, Joseph A. Konstan, John Riedl, "Analysis of recommendation algorithms for e-commerce",ACM Conference on Electronic Commerce, pp. 158-167, 2000.
13
Barkow, S., Bleuler, S., Prelic, A., Zimmermann, P., and E. Zitzler. BicAT: a biclustering analysis toolbox, Bioinformatics, 2006 22(10):1282-1283.
14
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.
15
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.
16
Ben-Dor,A., Chor,B., Karp,R. and Yakhini,Z. Discovering local structure in gene expression data: the order-preserving sub-matrix problem. In Proceed-ings of the 6th Annual International Conference on Computational Biology, ACM Press, New York, NY, USA, pp. 49-57, 2002.
17
J. Besson, C. Robardet, 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.
18
J. Besson, C. Robardet, J-F. Boulicaut, and S. Rome. Constraint-based bi-set mining for biologically relevant pattern discovery in microarray data. Intelligent Data Analysis journal, 9(1) :59–82, 2004.
19
Besson, J., Robardet, C., Boulicaut, J.F.: Mining a New Fault-Tolerant Pattern Type as an Alternative to Formal Concept Discovery, In: Schärfe, H.,Hitzler, P., Øhrstrøm, P. (eds.) ICCS 2006. LNCS (LNAI), vol. 4068, pp. 144-157. Springer, Heidelberg (2006).
20
A. Broder, On the resemblance and containment of documents, in Proc. Compression and Complexity of Sequences (SEQS: Sequences'97)
21
A. Broder, M. Charikar, A.M. Frieze, M. Mitzenmacher, Min-Wise Independent Permutations, in Proc. STOC, 1998.
22
A. Broder, Identifying and Filtering Near- Duplicate Documents, in Proc. Annual Symposium on Combinatorial Pattern Matching, 2000.
23
Stanislav Busygin, Gerrit Jacobsen, and Ewald Kramer. Double conjugated clustering applied o leukemia microarray data. In Proceedings of the 2nd SIAM International Conference on Data Mining, Workshop on Clustering High Dimensional Data, 2002.
24
Andrea Califano, Gustavo Stolovitzky, and Yunai Tu. Analysis of gene expression microarays for phenotype classification. In Proceedings of the International Conference on Computacional Molecular Biology, pages 75–85, 2000.
25
Cheng,Y. and Church,G. Biclustering of expression data. Proc. Int. Conf. Intell. Syst. Mol. Biol. pp. 93-103, 2000.
26
J. Cho, N. Shivakumar, H. Garcia-Molina, Finding replicated web collections, 1999
27
A. Chowdhury, O. Frieder, D.A.Grossman, and M.C. McCabe, Collection statistics for fast duplicate document detection, ACM Transactions on Information Systems, 20(2): 171-191, 2002
28
Davey B. A., Priestley H. A. Introduction to Lattices and Order. – Cambridge: Cambridge University Press, 2002.
29
Inderjit S. Dhillon. 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.
30
Inderjit S. Dhillon, Subramanyam Mallela, and Dharmendra S. Modha. 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.
31
Eckes, T., and Orlik, P., An Error Variance Approach to Two-mode Hierachical Clustering, Journal of Classification, 10, 51-74.
32
Freeman, L.: Cliques, Galois lattices, and the structure of human social groups. Social Networks 18 (1996) 173–187.
33
Ganter, B., and Wille, R. Formal Concept Analysis: Mathematical Foundations, Springer, 1999.
34
G. Getz, E. Levine, and E. Domany. Coupled two-way clustering analysis of gene microarray data. In Proceedings of the Natural Academy of Sciences USA, pages 12079–12084, 2000.
35
G. Grahne and J. Zhu, Efficiently Using Prefix-trees in Mining Frequent Itemsets, in Proc. FIMI Workshop, 2003.
36
J. Han and M. Kamber, Data Mining: Concepts and Techniques. Morgan Kaufmann, 2001.
37
Hartigan JA (1972). "Direct clustering of a data matrix". Journal of the American Statistical Association 67 (337): 123-129.
38
Ahmad M. Hasnah. A New Filtering Algorithm for Duplicate Document Based on Concept Analysis.Journal of Computer Science, Vol. 2 Issue 5, pp. 434-440, 2006.
39
P. Becker, J. H. Correia. “The ToscanaJ Suite for Implementing Conceptual Information Systems”. In: Formal Concept Analysis. Ed. by Bernhard Ganter, Gerd Stumme, and Rudolf Wille. Vol. 3626. Lecture Notes in Computer Science. Berlin, Heidelberg, and New York: Springer–Verlag, pp. 324–348,2005.
40
T. H. Haveliwala, A. Gionis, D. Klein, and P. Indyk , Evaluating Strategies for Similarity Search on the Web, in Proc. WWW'2002, Honolulu, 2002.
41
Bruce Hendrickson and Robert Leland. The Chaco User's Guide: Version 2.0, Sandia Tech Report SAND94-2692, 1994.
42
Thomas Hofmann and Jaz Puzicha. Latent class models for collaborative filtering. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 668–693, 1999.
43
Ihmels,J. et al. Defining transcription modules using large-scale gene expression, data. Bioinformatics, 20, 1993-2003, 2004.
44
S. Ilyinsky, M.Kuzmin, A. Melkov, I. Segalovich, 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).
45
Yuval Klugar, Ronen Basri, Joseph T. Chang, and Mark Gerstein. Spectral biclustering of microarray data: coclustering genes and conditions. In Genome Research, volume 13, pages 703–716, 2003.
46
A. Kolcz, A. Chowdhury, J. Alspector, Improved Robustness of Signature-Based Near-Replica Detection via Lexicon Randomization, in Proc. KDD'04, Seattle, 2004.
47
S.O. Kuznetsov and S.A. Obiedkov, 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. O.: On stability of a formal concept. Annals of Mathematics and Artificial Intelligence 49, 101-115 (2007).
50
Sergei O. Kuznetsov, Dmitrii I. Ignatov, 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), Clermont-Ferrand,P. 19-24, 2007.
51
Laura Lazzeroni and Art Owen. Plaid models for gene expression data. Technical report, Stanford University, 2000.
52
Luxenburger M. Implications partielles dans un contexte. Mathematiques, Informatique et Sciences Humaines, 113 (29) : 35-55, 1991.
53
Jinze Liu and Wei Wang. Op-cluster: Clustering by tendency in high dimensional space. In Proceedings of the 3rd IEEE International Conference on Data Mining, pages 187–194, 2003.
54
Sara C. Madeira and Arlindo L. Oliveira, "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.
55
Mirkin, B.G.: Additive Clustering and Qualitative Factor Analysis Methods for Similarity Matrices. Journal of classifiacation 4, 7-31 (1987).
56
Mirkin, B.G., Arabie, P., Hubert L.: Additive Two-Mode Clustering: The Error-Variance approach Revisited. Journal of classifiacation 12, 243-263 (1995).
57
Mirkin, B.G. Mathematical Classification and Clustering. Kluwer Academic Publishers, 1996.
58
Murali,T.M. and Kasif,S. Extracting conserved gene expression motifs from gene expression data. Pac. Symp. Biocomput., 8, 77-88, 2003.
59
N. Pasquier, Y. Bastide, R. Taouil, L. Lakhal, Efficient Mining of Association Rules Using Closed Itemset Lattices, Inform. Syst., 24(1), 25-46, 1999.
60
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.
61
W. Pugh, M. Henzinger, Detecting duplicate and near- duplicate files United States Patent 6658423 (December 2, 2003).
62
Matt Rasmussen and George Karypis. gCLUTO: An Interactive Clustering, Visualization, and Analysis System. UMN-CS TR-04-021, 2004.
63
Camille Roth, Sergei Obiedkov, Derrick G. Kourie: "Towards Concise Representation for Taxonomies of Epistemic Communities",CLA 4th International Conference on Concept Lattices and their Applications (2006)
64
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
65
Roth, C., Bourgine, P.: Lattice-based dynamic and overlapping taxonomies: the case of epistemic communities. Scientometrics 69(2) (2006)
66
Eran Segal, Ben Taskar, Audrey Gasch, Nir Friedman, and Daphne Koller. Rich probabilistic models for gene expression. In Bioinformatics, volume 17 (Suppl. 1), pages S243–S252, 2001.
67
Eran Segal, Ben Taskar, Audrey Gasch, Nir Friedman, and Daphne Koller. Decomposing gene expression into cellular processes. In Proceedings of the Pacific Symposium on Biocomputing, volume 8, pages 89–100, 2003.
68
Qizheng Sheng, Yves Moreau, and Bart De Moor. Biclustering micrarray data by gibbs sampling. In Bioinformatics, volume 19 (Suppl. 2), pages ii196–ii205, 2003.
69
Shepard, R.N., and Arabie, P. Additive Clustering: Representation of Similarities as Comdinations of Discrete Overlapping Properties, Psyhological Review, 86, 87 -123 (1979).
70
N. Shivakumar, H. Garcia-Molina, Finding near-replicas of documents on the web. Proceedings of Workshop on Web Databases (WebDB'98), 1998.
71
Michael Steinbach, George Karypis and Vipin Kumar. A Comparison of Document Clustering Techniques. KDD Workshop on Text Mining, 2000.
72
G. Stumme and R. Taouil and Y. Bastide and N. Pasqier and L. Lakhal. Computing Iceberg Concept Lattices with Titanic. J. on Knowledge and Data Engineering, (42)2:189-222,2002.
73
G. Stumme, A. Madche. FCA Merge: Bottom-Up Merging of Ontologies. Proc. 17th Intl. Conf. on Artificial Intelligence (IJCAI '01). Seattle, WA, USA, 225-230,2001.
74
L. Szathmary and A. Napoli. CORON: A Framework for Levelwise Itemset Mining Algorithms. In B. Ganter, R. Godin, and E. Mephu Nguifo, editors, Supplementary Proceedings of The Third International Conference on For-mal Concept Analysis ICFCA '05, Lens, France, pages 110-113, Feb 2005.
75
L. Szathmary, A. Napoli, and S. O. Kuznetsov. ZART: A Multifunctional Itemset Miner Algorithm. LORIA Research Report A05-R-013, Feb 2005.
76
Amos Tanay, Roded Sharan, and Ron Shamir. Discovering statistically significant biclusters in gene expression data. In Bioinformatics, volume 18 (Suppl. 1), pages S136–S144, 2002.
77
A. Tanay. R. Sharan, and R. Shamir, "Biclustering Algorithms: A Survey", In Handbook of Computational Molecular Biology, Edited by Srinivas Aluru, Chapman (2004)
78
Chun Tang, Li Zhang, Idon Zhang, and Murali Ramanathan. Interrelated two-way clustering: an unsupervised approach for gene expression data analysis. In Proceedings of the 2nd IEEE International Symposium on Bioinformatics and Bioengineering, pages 41–48, 2001.
79
Lyle Ungar and Dean P. Foster. A formal statistical approach to collaborative filtering. In Proceedings of the Conference on Automated Learning and Discovery (CONALD’98), 1998.
80
Petko Valtchev, David Grosser, Cyril Roume, Mohamed Rouane Hacene, GALICIA: an open platform for lattices, in Using Conceptual Structures: Contributions to the 11th Intl. Conference on Conceptual Structures (ICCS'03), pp. 241-254, Dresde (DE), Shaker Verlag, 2003.
81
Haixun Wang, Wei Wang, Jiong Yang, and Philip S. Yu. 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.
82
White, D.R., Duquenne, V.: Social network & discrete structure analysis: Introduction to a special issue. Social Networks 18 (1996) 169–172.
83
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.
84
Jiong Yang, Wei Wang, Haixun Wang, and Philip Yu.
-clusters: Capturing subspace correlation in a large data set. In Proceedings of the 18th IEEE International Conference on Data Engineering, pages 517–528, 2002.
85
Jiong Yang, Wei Wang, Haixun Wang, and Philip Yu. Enhanced biclustering on expression data. In Proceedings of the 3rd IEEE Conference on Bioinformatics and Bioengineering, pages 321–327, 2003.
86
Mohammed J. Zaki, Ching-Jui Hsiao, 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.
87
Y.Zhao and G. Karypis, Empirical and Theoretical Comparison of Selected Criterion Functions for Document Clustering. Machine Learning, vol. 55, pp. 311-331, 2004.
88
L.Е. Zhukov. Technical Report: Spectral Clustering of Large Advertiser Datasets Part I. Overture R&D, 2004.
Бикластеризация
В этом разделе мы опишем проблематику задачи и дадим основные определения, которыми оперирует бикластеризация как метод анализа данных. Помимо это будут приведены основания для классификации методов и алгоритмов бикластеризации. В качестве таких оснований выступают следующие критерии: типы бикластеров, структура бикластеров, получаемых в ходе анализа, а также стратегии поиска, которые используют рассматриваемые алгоритмы. Отметим, что основания для классификации алгоритмов были даны раннее португальским ученым Сарой Мадейра (см. обзор по методам бикластеризации генетических данных []).
Мы используем выявленные критерии для построения таксономии методов и дополняем существующую классификацию. В частности, мы рассматриваем методы бикластеризации, которые возникли вне области биоинформатики и предназначены для решения других задач, а также теми методами, которые появились позже написания обзора [] или не вошли в него. По этой же причине мы не рассматриваем подробно те модели, которые описаны в обзорах [], [] и []. В качестве еще одного критерия классификации можно использовать область применения метода, но для этого необходимо строго типизировать задачи.
Бикластеризация электоральных данных
Существуют и менее распространенные приложения бикластеризации, опирающиеся, например, на данные о голосовании. В этом случае необходимо выявлять подмножества строк избирателей, придерживающихся похожих политических взглядов и проявляющих сходное электоральное поведение на подмножестве рассматриваемых признаков.
Хартиган[37] применял бикластеризацию для двух массивов данных. Первый массив — данные о голосовании на президентских выборах США, отражающие процент голосов, которые были отданы за республиканцев в южных штатах в период с 1900 г. по 1968 г. Второй массив данных о голосовании в ООН в 1969 г. и 1970 г. В первом случае матрица состоит из множества строк, представляющих штаты, и множества столбцов, соответствующих годам. Каждое значение
представляет процент голосов штата
в году
Бикластер в этом случае — это подмножество штатов со сходными результатами голосования на подмножестве годов. Для второго набора строки соответствуют странам, а столбцы — предложениям по обсуждаемым вопросам. Бикластером является множество стран со сходными голосами на подмножестве обсуждаемых предложений.
Благодарности
В своей исходной версии данная работа представляет собой магистерское диссертационное исследование, поддержанное в рамках проекта «Учитель-ученики» ГУ-ВШЭ № 08-04-0022 «Разработка методов построения таксономий объектов на основе решеток формальных понятий и методов бикластеризации». Автор выражает благодарности аспиранту факультета ВМиК МГУ Кудрявцеву Юрию и доценту кафедры анализа данных и искусственного интеллекта ГУ-ВШЭ Объедкову Сергею за внимательное прочтение работы, выявление ошибок и ценные замечания. Отдельная благодарность Кудрявцеву Юрию за подготовку трансляции данного обзора из формата TeX в HTML.
Назад Содержание
Частично упорядоченные множества и решётки
Определение 2.1 Бинарное отношение
на некотором множестве
называется отношением (нестрогого) частичного порядка, если для
:
(рефлексивность);
и
, то
(антисимметричность);
и
, то
(транзитивность).
Множество S с определённым на нем отношением частичного порядка
(частично упорядоченное множество) обозначается
. Если
, то говорят, что элемент
меньше, чем
или равен ему. Если для
не существует
, такого что
, то
называют максимальным элементом
(относительно
).
Если
и
, то пишут
и говорят, что
строго меньше, чем
.
Определение 2.2 Пусть
— частично упорядоченное множество. Элемент
называется соседом снизу элемента
, если
и
. В этом случае
называется соседом сверху
(обозначается
). Направленный граф отношения
называется графом покрытия.
Конечное частично упорядоченное множество
может быть графически представлено с помощью диаграммы Хассе (или просто диаграммы [1]). Элементы
изображаются в виде точек. Если
, то
размещается "над"
(вертикальная координата
больше вертикальной координаты
), и две точки соединяются линией.
Определение 2.3 Верхней гранью подмножества
в упорядоченном множестве
называется элемент
, такой что
для всех
. Точная верхняя грань множества
(называемая также наименьшей верхней гранью или супремумом) множества
(обозначается sup
) есть верхняя грань
такая, что
для любой верхней грани
подмножества
. Двойственным образом (с заменой
на
) определяется понятие точной (наибольшей) нижней грани или инфимума inf
.
Определение 2.4 Бинарная операция
называется полурешёточной, если для некоторого
и любых
:
(идемпотентность);
(коммутативность);
(ассоциативность);
.
Для
и
мы пишем
вместо
. Если
, то
.
Определение 2.5 Множество
с определённой на нем полурешёточной операцией
называется полурешёткой
.
Полурешёточная операция
задает два частичных порядка
и
на
(
):
Тогда множество с определённой на нем полурешёточной операцией
будем называть нижней полурешёткой (относительно частичного порядка
) и верхней полурешёткой (относительно частичного порядка
).
Определение 2.6 Пусть
— полурешётка. Множество
называется системой замыканий [33] или семейством Мура [1] (относительно
), если
.
Очевидно, что система замыканий (относительно
)
с определённой на ней операцией,
и
, образует полурешётку.
Определение 2.7 Упорядоченное множество
с определёнными на нем полурешёточными операциями
и
называется решёткой, если
и
являются, соответственно, нижней и верхней полурешётками (относительно
).
Операции
и
называют операциями взятия точной нижней и верхней грани в решётке, или инфимума и супремума соответственно.
Определение 2.8 Подрешёткой решётки
называется подмножество
такое, что если
,
, то
и
.
Полурешёточные операции
и
удовлетворяют в решётках следующему условию:
(поглощение).
Из любой конечной полурешётки можно получить решётку добавлением одного (максимального или минимального в зависимости от типа полурешетки) элемента.
Решётка называется полной, если у каждого подмножества его элементов есть супремум и инфимум (всякая конечная решётка является полной).
Определение 2.9 Интервал
состоит из всех элементов
. Порядковым фильтром (идеалом) решётки
называется подмножество
такое, что если
,
и
, то
(соответственно,
,
и
, то
).
Элемент
решётки называется инфимум-неразложимым или
-неразложимым (или неразложимым в пересечение), если для любых
и
, не выполняется
. Элемент
решётки называется супремум-неразложимым или
-неразложимым (или неразложимым в объединение), если для любых
и
не выполняется
.
Подмножество
полной решётки
называется инфимум-плотным, если
, и супремум-плотным, если
).
Определение 2.10 Пусть
и
— частично упорядоченные множества. Пара отображений
и
называется соответствием Галуа между частично упорядоченными множествами
и
, если для любых
и
:
;
;
и
.
Приведённые условия эквивалентны одному:
[1,33,28].
Назад Содержание Вперёд
Частые (замкнутые) множества признаков
Задача поиска частых множеств признаков (frequent itemsets mining) является одной из центральных тем в DataMining. Первоначально необходимость поиска частых множества признаков возникла при выявлении часто покупаемых вместе товаров в базах данных транзакций. Неформально ее можно описать так: дана большая база данных транзакций (покупок); необходимо найти все часто покупаемые наборы товаров, число покупок которых превышает заданный пользователем порог.
В настоящее время набор приложений, в которых основным этапом является построение частых множеств признаков, существенно расширился, например, это поиск ассоциативных правил (см. раздел2.6), сильных правил (strong rules), корреляций, секвенциальных правил, эпизодов (episodes), многомерных образов (multidimensional patterns) и многие другие задачи анализа данных [36].
Среди частых множеств признаков выделяют так называемые частые замкнутые множества признаков, которые полезны для их более компактного представления. Такое представление осуществляется без потерь информации о поддержке собственных частых подмножеств данных частых замкнутых множеств признаков.
Хорошо известным фактом для сообщества DataMining является то, что все замкнутые частые множества признаков (т.е. при
Ниже будут даны основные определения; для единства изложения и общности понимания которых будем использовать терминологию, принятую в ФАП. Приведем также классический алгоритм для поиска частых множеств признаков Apriori [9], который не утратил своей актуальности и стал отправной точкой для огромного числа других алгоритмов. Обсудим также связь ФАП и поиска частых замкнутых множеств признаков, которая позволяет рассматривать оба метода в контексте бикластеризации.
Другие системы бикластеризации
Стоит отдельно упомянуть системы бикластеризации на графах и спектральной кластеризации. Система CLUTO [71,87] — библиотека алгоритмов для кластеризации как данных небольшой размерности, так и многомерных, а также анализа свойств различных кластеров. Авторы рекомендуют использовать CLUTO для кластеризации данных во многих областях, таких как информационный поиск, базы данных транзакций, Интернет и биология. В программе реализована кластеризация на графах, различные меры сходства, поддерживается поиск клик графа и частых множеств признаков, реализованы удобные средства визуализации gCluto [62].Отличительная особенность программы заключается в возможности анализа больших массивов, содержащих сотни тысяч объектов и десятки тысяч признаков.
Две других системы предназначенные для графовой кластеризации — это Chaco [41] и METIS [11]. Укажем, что Metis отличается высокой скоростью вычислений для больших массивов данных, а в Chaco реализована спектральная кластеризация на графах. Не будем подробно их описывать, но укажем на то, что поиск клик и их различных ослаблений в двудольном графе (в том числе и взвешенном) сводится к постановкам задач бикластерзации. А это означает, что такие системы можно рассматривать как системы бикластеризации.
Формальный анализ понятий (ФАП)
Определение 2.11 Формальный контекст
есть тройка
, где
— множество, называемое множеством объектов,
— множество, называемое множеством признаков,
— отношение.
Отношение
интерпретируется следующим образом: для
,
имеет место
, если объект
обладает признаком
.
Для формального контекста
и произвольных
и
определена пара отображений:
которые задают соответствие Галуа между частично упорядоченными множествами
и
(см. Раздел 2.1.1), а оператор
является оператором замыкания на
— дизъюнктном объединении
и
, т.е. для произвольного
или
имеют место следующие соотношения [1]:
(экстенсивность),
(идемпотентность),
если
, то
(изотонность).
Множество
называется замкнутым, если
[1].
Определение 2.12 Формальное понятие формального контекста
есть пара
, где
,
,
и
. Множество
называется объёмом, а
— содержанием понятия
.
Очевидно, что объем и содержание произвольного формального понятия являются замкнутыми множествами.
Множество формальных понятий контекста
, которое мы будем обозначать посредством
, частично упорядочено по вложению объёмов: формальное понятие
является менее общим
(более частным), чем понятие
,
, если
, что эквивалентно
(
— обобщение
).
В работе [1] было показано, что подмножества произвольного множества, замкнутые относительно заданной на нем операции замыкания, образуют полную решётку, а в работах [83,33] — что множество всех понятий формального контекста
образует полную решётку.
Определение 2.13 Множество понятий контекста
образует решётку
, где
. и
. Такие решётки называют решётками понятий, или решётками Галуа [33].
Любая полная решётка изоморфна решётке понятий некоторого формального контекста [33]. В качестве объектов этого контекста нужно выбрать
-неразложимые элементы, а в качестве признаков —
-неразложимые элементы исходной решётки. Тогда объект
в контексте будет обладать признаком
, если элемент решётки, соответствующий
.
Определение 2.14 Строчно- (столбцево-) редуцированным называется такой формальный контекст, в котором всякое объектное (признаковое) понятие является
-неразложимым (
-неразложимым). Редуцированным называется формальный контекст, являющийся одновременно строчно- и столбцево-редуцированным.
Определение 2.15 Пусть дан
— формальный контекст и
называется импликацией (на множествах признаков), если
(или
), т.е. все объекты из
, обладающие множеством признаков
, обладают также множеством признаков
.
Аналогичным образом определяются импликации на множествах объектов. Наличие импликации
в контексте
соответствует тому, что в диаграмме решётки
формальное понятие
находится ниже формального понятия
.
Импликации формального контекста удовлетворяют аксиомам Армстронга [33] для произвольных
:
;
если
то
;
если
и
то
.
Помимо определённых выше однозначных (one-valued) формальных контекстов в анализе формальных понятий изучаются многозначные (many-valued) контексты:
Определение 2.16 Многозначный формальный контекст есть четвёрка
— множества (объектов, признаков и значений признаков, соответственно), а
— тернарное отношение
признака
причём:
Многозначные признаки могут рассматриваться как отображения
вместо
.
Процедура сведения многозначных контекстов к однозначным называется шкалированием (scaling). Для шкалирования каждый признак многозначного контекста представляется формальным контекстом, называемым шкалой.
Определение 2.17 Шкала для признака
многозначного контекста
есть (однозначный) контекст
такой, что
. Объекты в шкале называются значениями шкалы, а признаки — признаками шкалы.
Определение 2.18 Пусть задан многозначный контекст
и шкалы
, тогда производным контекстом будем называть контекст
, где множество признаков
(
) и отношение
и
.
В нашей работе для построения таксономии алгоритмов использовалось два варианта шкалирования — порядковое шкалирование и номинальное шкалирование. Порядковая шкала
используется для признаков, значения которых упорядочены относительно некоторого порядка
, а обладание объектом некоторым значением признака влечёт обладание всеми меньшими значениями признака. С помощью номинальной шкалы
представляют несравнимые между собой значения признаков, например, цвет.
Возможные виды шкалирования рассмотрены в [33].
Назад Содержание Вперёд
Формирование бикластеров для рекомендательной системы Интернет-рекламы
Одна из разновидностей электронной коммерции — контекстная Интернет-реклама. Сейчас на рынке таких услуг крупными игроками являются поисковые системы, немалую часть прибыли которых составляет так называемая поисковая реклама. Для России репрезентативными примерами служат рекламные Интернет-сервисы "Яндекс.Директ" и "Бегун".
Пользователю предлагается реклама, релевантная (с точки зрения поисковой системы) его поисковому запросу. В этом разделе мы не будем рассматривать задачу предоставления пользователю наиболее интересной ему поисковой рекламы. Наша задача — выявление рекламных слов, которые могут быть интересны рекламодателю.
Предположим, что некая фирма F приобрела ряд рекламных слов, которые описывают предоставляемые услуги. Как правило, на рынке уже существуют компании-конкуренты, поэтому вполне разумно было бы выяснить, какие рекламные слова приобрели они. Далее можно сравнить эти множества слов с теми, что купила F и, исходя из частоты таких покупок, отобрать наиболее интересные слова для нее из числа неприобретенных. Такой механизм стимулирует продажи рекламы и позволяет устраивать своеобразный аукцион по определению цены того или иного рекламного словосочетания.
Решение подобной задачи методами спектральной кластеризации описано в [88]. Цель наших экспериментов — не только расширить список методов бикластеризации, пригодных для решения этой задачи, но и улучшить качество предложенных рекомендаций. Ниже приведено описание исходного набора данных, постановка задачи, предложены методы для ее решения, описаны проведенные эксперименты и полученные результаты.
Постановка задачи и исходные данные
Данные для экспериментов принадлежат компании US Overture (ныне часть Yahoo) и описаны в работе [88]. Фактически, данные представляют собой двумерный массив, в котором строкам соответствуют фирмы (advertisers), а столбцам — рекламные слова (bids). Число фирм — 2000, а число рекламных словосочетаний — 3000. Число ненулевых ячеек 92345, соответственно, мера разреженности равна
Рис. 5.7. Исходные данные
Минимальное число заполненных ячеек в строке — 13. Это означает, что фирмы, представленные в наборе данных, покупают минимум 13 рекламных слов. Максимальное число заполненных ячеек в строке — 947. Минимальное число заполненных ячеек в столбце — 18, т.е. одно словосочетание покупает не меньше 18 фирм. Максимальное число непустых ячеек в столбце — 159.
По этим данным требуется построить бикластеры (фирмы, рекламные слова), которые представляют собой сегменты рынка. Далее такие бикластеры можно использовать для создания рекомендаций для фирм, действующих на этом же рынке, но не совершившим покупки слов, входящих в такой бикластер. В случае бикластеризации, допускающей незаполненные ячейки внутри бикластера, рекламные слова, отвечающие таким ячейкам, можно рассматривать в качестве кандидатов для рекомендаций.
Подобные рекомендации можно представлять в виде правил: "если фирма приобрела рекламное словосочетание A, то имеет смысл предложить ей словосочетание B". Такие правила "если-то" хорошо вписываются в парадигму поиска ассоциаций. В существующей научной литературе неоднократно описывались рекомендательные системы, основанные на анализе ассоциативных правил, см. [12]. Эти методы наряду с другими, используемыми в рекомендательных системах, показывают приемлемые результаты. Ниже мы опишем, как можно использовать семантическую и морфологическую информацию, заложенную в описании признаков (рекламных слов), и, тем самым, улучшить качество рекомендационных правил.
Вычислительная модель
Исходный массив данных описывается формальным контекстом
,
(от firms) — множество компаний-рекламодателей, а
(от term) — множество рекламных словосочетаний,
— отношение инцидентности, показывающее, что фирма
купила словосочетание
тогда и только тогда, когда
Для решения задачи мы последовательно применяли следущие подходы и алгоритмы:
алгоритм D-miner для выявления крупных рынков средствами ФАП;
поиск ассоциативных правил для построения рекомендаций;
построение ассоциативных метаправил с помощью морфологического анализа;
построение ассоциативных метаправил с помощью онтологий (тематического каталога);
1) Алгоритм D-miner — выявление крупных рынков средствами ФАП.
Алгоритм D-miner подробно описан в работах [18] и [17]. Основное предназначение алгоритма — построение множества понятий по заданному контексту при ограничениях на размер объема и содержания. Фактически, задавая ограничение на размер объема понятия, мы строим так называемую решетку-айсберг. Аналогично при ограничении на размер содержания, мы строим "нижний" айсберг (т.е. нижнюю часть решетки).
Алгоритм D-miner принимает на вход контекст и два параметра — минимальные размеры объема понятия и содержания. При отличных от нуля ограничениях на размеры понятия на выходе алгоритма мы получим частично упорядоченное множество, представляющее "полосу" из средней части решетки, либо результат алгоритма будет пуст, если нет понятий, удовлетворяющих условиям отбора. Отметим, что алгоритм имеет приемлемую вычислительную сложность —
Минимальный размер |
Минимальный | Число |
| объема понятия | размер содержания | формальных понятий |
0 |
0 | 8 950 740 |
| 10 | 10 | 3 030 335 |
| 15 | 10 | 759 963 |
| 15 | 15 | 150 983 |
| 15 | 20 | 14 226 |
| 20 | 15 | 661 |
| 20 | 20 | 0 |
| 20 | 16 | 53 |
Приведем примеры содержания формальных понятий для случая
Рынок услуг по размещению сайтов
affordable hosting web, business hosting web, cheap hosting, cheap hosting site web, cheap hosting web, company hosting web, cost hosting low web, discount hosting web, domain hosting, hosting internet, hosting page web, hosting service, hosting services web, hosting site web, hosting web
Рынок азартных игр.
black casino jack, black gambling jack, black jack online, casino gambling, casino gambling online, casino game online, casino internet, casino line, casino net, casino online, casino roulette, casino slot, craps online, gambling internet, gambling online
Гостиничный бизнес.
angeles hotel los, atlanta hotel, baltimore hotel, dallas hotel, denver hotel, diego hotel san, francisco hotel san, hotel houston, hotel miami, hotel new orleans, hotel new york, hotel orlando, hotel philadelphia, hotel seattle, hotel vancouver
2) Рекомендации на основе ассоциативных правил.
По данному контексту построим с помощью программы Coron (см. раздел 3.3) информативный базис ассоциативных правил [75]. Информативный базис выбран нами, во-первых, для более компактного представления множества правил, а во-вторых, для повышения вычислительной эффективности. Напомним, что идея базиса состоит в том, что все остальные ассоциативные правила выводимы из него с помощью аксиом Армстронга. Результаты работы алгоритма приведены в таблице 5.2.
 |
 |
 |
 |
число правил |
| 30 | 86 | 0,9 | 1 | 101 391 |
| 30 | 109 | 0,8 | 1 | 144 043 |
minsupp=30, minconf=0,9
, supp=30 [1.50%]; conf=0.909 [90.91%];
, supp=41 [2.05%]; conf=0.820 [82.00%];
Величина поддержки
для первого правила означает, что словосочетания "game slot" и "casino gambling online" купили 30 фирм. Величина достоверности
означает, что 90,9% фирм, которые покупают словосочетание "game slot", также покупают и "casino gambling online".
Далее для формирования рекомендаций для каждой конкретной фирмы можно применять подход, предложенный в [12]. Для покупателя слов
находим все ассоциативные правила, в левой части которых содержатся им купленные слова. Далее строим множество
— уникальных рекламных словосочетаний, не купленных
ранее. Затем упорядочиваем найденные словосочетания по убыванию величины достоверности правил, в правую часть которых они входят. Если покупка одного и того же словосочетания предсказана несколькими правилами, то мы рассматриваем ассоциацию с наибольшей достоверностью.
3) Построение метаправил на основе морфологии рекламных слов признакового пространства.
Рассмотрим в качестве дополнительного знания имеющееся признаковое пространство, а именно, тот факт, что каждый признак является словом или словосочетанием. Вполне очевидно, что синонимичные словосочетания принадлежат к одному сегменту рынка. Конечно, в штате компаний, занимающихся контекстной рекламой, существуют тематические каталоги, составленные экспертами, но ввиду большого количества рекламных слов (несколько тысяч) наполнение каталога "вручную" является сложной задачей.
Для построения тематического каталога рекламных словосочетаний могут потребоваться словари синонимов, а из-за того, что такие словосочетания не всегда являются словами или сочетаниями двух слов, такие словари редки. К тому же, рекламное словосочетание может включать специфические сокращения, отсутствующие в словарях синонимов общего назначения. Поэтому в качестве первого приближения для решения такой задачи можно использовать стемминг, или выделение основы слова. Опишем последовательность действий при извлечении знаний с помощью стемминга.
Пусть
обозначим через
обозначим через
— множество всех словосочетаний, а
— множество основ всех словосочетаний из
будет означать, что во множество основ словосочетания
входит основа
Построим по такому контексту правила вида
для всех
соответствует
— ассоциативное правило контекста
превышают некоторые пороговые значения, то можно считать ассоциативные правила, построенные по контексту
В качестве более крупных метаправил мы предлагаем следующие две возможности. Во-первых, можно искать правила вида
Мы предлагаем также использовать метаправила вида
следует словосочетание, множество основ которого вкладывается в множество основ
Примеры метаправил.
{mail order phentermine} → {adipex online order, adipex order,adipex phentermine,
phentermine prescription, phentermine purchase, phentermine sale},
Supp = 19; Conf = 0,95;
{distance long phone} → {call distance long phone, carrier distance long phone,
distance long phone rate, distance long phone service},
Supp = 37, Conf = 0,88;
4) Построение онтологии и семантических метаправил на ее основе. Несмотря на то, что в информатике не существует общего формального определения понятия онтологии, можно выделить его основные черты: понятия, иерархическое отношение IS-A и другие отношения. Мы будем следовать определению, приведенному в [72]:
Определение 5.2
Онтология — это кортеж
— множество, элементы которого называются понятиями,
— частичный порядок на
— множество, элементы которого называются именами отношений (или просто отношениями) и
— функция, которая сопоставляет каждому отношению его арность.
В нашем случае множество понятий — все рекламные слова, упорядоченные отношением быть "более общим понятием". Например, в нашей онтологии для рынка лекарств и медицинских средств понятие "медицинские препараты" — более общее, чем "витамины".
В нашем случае будем использовать упрощенную "древесную" онтологию. Введем два оператора, действующих на множестве рекламных слов
уровней выше, и оператор соседства
Теперь определим два вида метаправил для онтологии: правила общности
и правила соседства
Примеры метаправил для рынка медикаментов.
Правило вида
{B_VITAMIN} → {B_COMPLEX_VITAMIN, B12_VITAMIN, C_VITAMIN, D_VITAMIN,
DISCOUNT_VITAMIN, E_VITAMIN, HERB_VITAMIN, MINERAL_VITAMIN,
MULTI_VITAMIN, SUPPLEMENT_VITAMIN, VITAMIN}
Правило вида
Верификация результатов
Для проверки результатов, полученных нами с помощью поиска ассоциативных правил, мы применяем скользящий контроль (cross validation). Для это мы разбиваем исходную выборку случайным образом на 10 частей, далее последовательно используем одну часть в качестве контрольной выборки (test set), а остальные 9 рассматриваем как единую обучающую выборку(training set). При этом ассоциативные правила, полученные нами по обучающей выборке, будем записывать в виде
Тогда мерой качества такого ассоциативного правила при проверке на контрольной выборке будет служить величина
Мы построили 10 множеств ассоциативных правил для 10-ти различных выборок по 1800 фирм каждая и вычислили величину достоверности таких правил на контрольной выборке, содержащей 200 объектов. Ассоциативные правила мы искали для значений минимальной поддержки 27 (
от размера выборки) и минимальной достоверности 0,9 (
где
— множество ассоциативных правил полученных по
| Число | Число | mean_conf | Число правил | mean_conf | |
| правил | подтвержденных правил | min_conf=50% | (min_conf=50%) | ||
1 |
147170 | 73025 | 0,77 | 65556 | 0,84 |
| 2 | 69028 | 68709 | 0,93 | 68495 | 0,93 |
| 3 | 89332 | 89245 | 0,95 | 88952 | 0,95 |
| 4 | 107036 | 93078 | 0,84 | 86144 | 0,90 |
| 5 | 152455 | 126275 | 0,82 | 113008 | 0,90 |
| 6 | 117174 | 114314 | 0,89 | 111739 | 0,91 |
| 7 | 131590 | 129826 | 0,95 | 128951 | 0,96 |
| 8 | 134728 | 120987 | 0,96 | 106155 | 0,97 |
| 9 | 101346 | 67873 | 0,72 | 52715 | 0,92 |
| 10 | 108994 | 107790 | 0,93 | 106155 | 0,94 |
means |
115885 | 99112 | 0,87 | 92787 | 0,92 |
Усредненная достоверность правил на контрольной выборке не сильно снижается по сравнению с минимальной достоверностью для обучающей выборки, т.е.
В качестве средства валидации для метаправил мы используем меру достоверности. Величина поддержки не играет большой роли, так как мы ищем не столько крупные рынки или наиболее продаваемые словосочетания, сколько устойчивые закономерности при покупке. Правила с достоверностью меньше 0.5 нас не так сильно интересуют, потому что они означают, что в половине случаев покупка может произойти, а в половине — нет (своеобразная игра в подбрасывание монеты).
Для ассоциативных правил мы изначально задались высоким уровнем достоверности — 0.8 и 0.9. Для метаправил значения поддержки и достоверности необходимо вычислить по контексту
| Тип правила | Среднее значение supp | Среднее значение conf | Число правил |
| Тип правила | Среднее значение supp | Среднее значение conf | Число правил |
, такие что
, такие что
Наиболее достоверные правила может дать онтология (в данной задаче — заранее составленный экспертами каталог).
Выводы и дальнейшие исследования
Полученные результаты показывают, что часть зависимостей в базе данных покупок рекламных слов можно выявлять автоматически, не прибегая к трудоемким методам, а используя стандартные методы компьютерной лингвистики. Предложенные подходы вкупе с с методами Data Mining помогают улучшить рекомендации и обеспечивают хорошее средство частотного ранжирования, что удобно при составлении Top-N рекомендаций. Еще одно преимущество подхода состоит в возможности выявить связанные рекламные слова, не используемые по каким-то причинам рекламодателями. Результаты бикластеризации на основе ФАП показывают возможность выявления относительно крупных рекламных рынков (более 20-ти участников), описанных в терминах фирм-участников и рекламных слов.
В качестве дальнейших исследовательских задач отметим следующие:
проверка предложенного подхода на больших массивах реальных данных с применением методов скользящего контроля (разбиение исходного массива на обучающую и тестовую выборку);
использование готовых онтологий типа WordNet для построения метаправил.
Назад Содержание Вперёд
Информационный поиск (Information Retrieval): бикластеризация документов
В задачах информационного поиска и анализа текстов (text mining) бикластеризация применяется для обнаружения кластеров документов, обладающих сходными свойствами только по нескольким признакам, таким как слова и изображения. Такая информация очень важна для запросов и индексации поисковых интернет-систем. Диллон в своей работе [29] использует бикластеризацию для одновременного группирования документов и слов. Исходные данные представляют собой матрицу F, в которой строки отвечают словам, а столбцы — документам, а ненулевой элемент
показывает присутствие слова
в документе
показывает число вхождений слова
в документ
— общее число документов, а
— число документов, содержащих слово
Проблемы кластеризации документов и слов в отдельности хорошо изучены в контексте информационного поиска и анализа текстов. Однако кластеризации лишь по одному измерению оказывается недостаточно. Допустим, имеется коллекция документов никак не сгруппированных. Тогда кластеризация помогает организовать коллекцию для целей дальнейшей навигации и поиска. Слова могут быть кластеризованы на основе документов в которых они встречаются. Кластеры слов полезны для автоматического построения статистических тезаурусов, уточнения запросов и автоматической классификации документов.
В этой работе Диллон пытается выявить подмножества слов и документов, сильно связанных друг с другом. В его модели, как и в работе Танай и др.[76], матрице исходных данных сопоставляется двудольный граф, и автор использует спектральный подход, похожий на предложенный Клугер и др. [45]. Эксперименты проводятся на трех коллекциях документов: Medline (1033 медицинских статьи), Cranfield (1400 статей про системы аэронавтики) и Cisi (1460 статьи по информационному поиску). Другие примеры бикластеризации для этого типа матриц можно найти в работе Диллона [30].
Для задачи выявления документов-дубликатов было предпринято две относительно успешные попытки использования ФАП и частых замкнутых множеств признаков (см. работы Кузнецова и Игнатова [6,3] и более позднюю статью другого исследователя [38]). Подробное описание постановки задачи, вычислительной модели см. в разделе 4.1.
Интернет-приложения: e-commerce, recommendation systems, collaborative filtering, target marketing
Методы бикластеризации могут быть использованы для так называемой коллаборативной фильтрации (collaborative filtering) при обнаружении групп покупателей со сходными предпочтениями в виде некого подмножества товаров (задача целевого маркетинга). Похожая ситуация имеет место в рекомендательных системах, где бикластеры предоставляют информацию о сходных интересах групп посетителей.
Необходимо отметить, что рекомендательные системы и целевой маркетинг — важные приложения в области электронной коммерции (см., например, [12]). В таких приложениях основной целью является обнаружение групп покупателей, ведущих себя похожим образом, чтобы предсказать их интересы и предложить адекватные рекомендации. Отметим несколько работ, освещающих вопросы применения методов бикластеризации к таким данным.
Джионг Янг и др. [84,85] использовали для проведения экспериментов массив данных MovieLens, собранный исследовательской группой GroupLens университета Миннесоты. Массив данных представляет собой матрицу, строки которой описывают 943 покупателя, а столбцы — 1682 фильма. Значения матрицы — целые числа от 1 до 10, они представляют рейтинг, который покупатель присвоил фильму. Матрица довольно разреженная, т.к. покупатель оценивает в среднем менее 10% фильмов. Хайксун Янг и др. [81] также провели эксперименты на этих данных.
Хоффман и Пузича [42] применяли бикластеризацию для коллаборативной фильтрации на массиве EachMovie, который состоит из данных, собранных в Интернете для почти трех миллионов предпочтений с оценками от 0 до 5. Унгар и Фостер [79] также используют данные о фильмах, в которых учитывается лишь факт просмотра фильма, поэтому анализируемая матрица — бинарная.
Другим примером является рынок Интернет-рекламы, для которого актуален поиск бикластеров, представляющих отдельные рынки, т.е. множества покупателей и приобретаемых ими рекламных словосочетаний (см. [88]). Решение аналогичной задачи описывается и в данной работе (см. раздел 5.3).
Классификация методов бикластеризации
Теперь, когда четко выделены основания для классификации алгоритмов бикластеризации, построим их таксономию. В таблице1.3 для каждого алгоритма, вошедшего в обзор, в соответствующих столбцах указаны тип бикластера, структура порождаемых бимножеств, количество бикластеров, порожденных за один запуск алгоритма, и стратегия поиска.
| Алгоритм | Тип бикластера | Структура | Порождение | Стратегия поиска |
| Block Clustering [37] | Constant | f | One Set at a Time | Div-and-Conq |
-biclusters [25] |
Coherent Values | i | One at a Time | Greedy |
| FLOC [84,85] | Coherent Values | i | Simultaneous | Greedy |
| pClusters [81] | Coherent Values | g | Simultaneous | Exh-Enum |
| Plaid Models [51] | Coherent Values | i | One at a Time | Dist-Ident |
| PRMs [66,67] | Coherent Values | i | Simultaneous | Dist-Ident |
| CTWC [34] | Constant Columns | i | One Set at a Time | Clust-Comb |
| ITWC [78] | Coherent Values | d,e | One Set at a Time | Clust-Comb |
| DCC [23] | Constant | b,c | Simultaneous | Clust-Comb |
-Patterns [24] |
Constant Rows | i | Simultaneous | Greedy |
| Spectral [45] | Coherent Values | c | Simultaneous | Greedy |
| Gibbs [68] | Constant Columns | d,e | One at a Time | Dist-Ident |
| OPSMs [16] | Coherent Evolution | a,i | One at a Time | Greedy |
| SAMBA [77] | Coherent Evolution | i | Simultaneous | Exh-Enum |
| xMOTIFs [58] [19] | Coherent Evolution | a,i | Simultaneous | Greedy |
| OP-Clusters [53] | Coherent Evolution | i | Simultaneous | Exh-Enum |
Мы используем решеточную таксономию алгоритмов, так как она лишена недостатков древесной, когда наследование свойств от различных надклассов невозможно для одного и того же подкласса. Данная таксономия построена средствами ФАП, а исходная таблица 1.3 посредством шкалирования сведена к объектно-признаковому представлению в виде бинарной матрицы.
Рис. 1.1. Таксономия алгоритмов бикластеризации
Мы предлагаем расширить указанную таксономию за счет введения дополнительного признака — типа исходных значений. Помимо этого, представляется желательным учесть тип бикластеров, в котором возможно присутствие некоторого числа нулевых значений, т.к. это один из способов ослабления требования к формальным понятиям. Для случая иерархической структуры бикластеров можно выделить и отдельно рассмотреть частичный (решеточный) порядок в качестве подтипа.
Для пополнения таксономии объектами мы предлагаем включить алгоритмы, используемые в ФАП для поиска формальных понятий, алгоритмы поиска частых (замкнутых) множеств признаков, алгоритм аддитивной бокс-кластеризации, DR-miner и D-miner из области DataMining, BiMax — разработанный для анализа генетических данных. Перечисленные алгоритмы, за исключением бокс-кластеризации, работают только с 0/1 данными, поэтому в таксономии им соответствует подрешетка, порожденная признаком
"
-данные".
Методы бикластеризации для анализа интернет-данных
,
кафедра анализа данных и искусственного интеллекта ГУ-ВШЭ
Дмитрий Игнатов,
кафедра анализа данных и искусственного интеллекта ГУ-ВШЭ
Назад Содержание Вперёд
Дмитрий Игнатов,
кафедра анализа данных и искусственного интеллекта ГУ-ВШЭ
Назад Содержание Вперёд
Дмитрий Игнатов,
кафедра анализа данных и искусственного интеллекта ГУ-ВШЭ
Назад Содержание Вперёд
Дмитрий Игнатов,
кафедра анализа данных и искусственного интеллекта ГУ-ВШЭ
Назад Содержание Вперёд
Дмитрий Игнатов,
кафедра анализа данных и искусственного интеллекта ГУ-ВШЭ
Назад Содержание Вперёд
Дмитрий Игнатов,
кафедра анализа данных и искусственного интеллекта ГУ-ВШЭ
Назад Содержание Вперёд
Дмитрий Игнатов,
кафедра анализа данных и искусственного интеллекта ГУ-ВШЭ
Назад Содержание Вперёд
Дмитрий Игнатов,
кафедра анализа данных и искусственного интеллекта ГУ-ВШЭ
Назад Содержание Вперёд
Дмитрий Игнатов,
кафедра анализа данных и искусственного интеллекта ГУ-ВШЭ
Назад Содержание Вперёд
Дмитрий Игнатов,
кафедра анализа данных и искусственного интеллекта ГУ-ВШЭ
Назад Содержание Вперёд
Дмитрий Игнатов,
кафедра анализа данных и искусственного интеллекта ГУ-ВШЭ
Назад Содержание
Описание алгоритма
Алгоритм BiMax следует стратегии "разделяй и властвуй". Первоначально алгоритм определяет области матрицы
Идея, лежащая в основе алгоритма, состоит в следующем: исходная матрица
разбивается на три подматрицы, одна из которых содержит только нулевые значения и в дальнейшем не рассматривается. Затем алгоритм рекурсивно применяется к оставшимся двум подматрицам
и
Для обработки подматрицы
необходимы специальные операции, чтобы гарантировать максимальность по вложению бикластеров. Проблема возникает в том случае, если
содержит части бикластеров, найденных в
допустим, если
обладает одним или несколькими столбцами с каждым множеством столбцов
из
, т.е.
.
Алгоритм 2.2.1. BiMax(E)
Описание модели
Вычислительная модель предполагает, что существует только два возможных уровня генной экспрессии: изменение и отсутствие изменения для данного эксперимента. Множество из m экспериментов для n генов может быть представлено бинарной матрицей
, где ячейка
равна
, если ген
проявился для условия
, иначе 0. Бикластер
соответствует подмножеству генов
определяет подматрицу E для которой все элементы равны 1. Отметим, что согласно такому определению каждая ячейка
Определение 2.19
Пара
называется максимальным по вложению бикластером тогда и только тогда, когда (1)
и (2)
такой, что (a)
и (b)
.
Отметим, что такие максимальные по вложению бикластеры довольно давно и хорошо исследованы с точки зрения алгебраической структуры в рамках ФАП. Это подтверждает следующее утверждение.
Предложение 2.1
Определение максимального по вложению бикластера 2.19 и определение формального понятия 2.12 эквивалентны.
Благодаря утверждению 2.1, для бикластеров, предложенных в этой вычислительной модели, можно построить иерархию по отношению покрытия, графически представляющую собой диаграмму решетки формальных понятий.
возрастет. Знак
не зависит от действий на предыдущих шагах, что влечет естественное условие прекращения добавления элементов — изменение
становится положительным для любой внешней строки
(или столбца
Рассмотрим критерий аддитивной кластеризации (2.4) более подробно. Очевидно, что (2.5) можно переписать следующим образом.
В последнем выражении первое слагаемое — постоянная величена; раскрывая скобки под знаком суммирования во втором слагаемом приходим к новой записи критерия (2.5). Критерий (2.5) представляет собой разность постоянного члена
и
 |
(2.7) |
Теперь для минимизации критерия (2.5) необходимо максимизировать (2.7). Критерий (2.7) позволяет лучше интерпретировать условие оптимальности, основанное на изменении знака (2.6) с отрицательного на положительный, когда
оптимально. В самом деле, приращение (2.7), когда
добавляется к
(
остается без изменений), равно:
 |
(2.8) |
Для простоты положим, что
положительно. В этом случае
будет отрицательным, когда среднее значение
 |
(2.9) |
меньше, чем
в качестве
должен включать только те объекты
и
(см. (2.9)) и
не меньше половины максимального значения. Такой выбор
приводит к обнаружению бокс-кластеров с большими внутренними значениями сходства. Оптимальное значение
 |
(2.10) |
Для оптимального значения
из (2.10) при его подстановке в критерий
из (2.7) получим
 |
(2.11) |
Как видим, эта форма критерия (2.7) не содержит
(определенного по формуле (2.10) ) и может быть легко преобразована для случая, когда оптимальное значение
отрицательно.
Назад Содержание Вперёд
Описание модели DR-бимножеств
Бимножеством будем называть пару
.
Частным случаем бимножеств являются формальные понятия. Приведем определения, которые помогут провести обобщение формальных понятий до бимножеств.
Определение 2.20 Обозначим через
число нулевых значений объекта
на признаках из
, т.е.
. Сходным образом через
определим число нулевых значений признака y на объектах из
.
Теперь формальные понятия можно ввести с помощью леммы.
Лемма 2.1 Бимножество (X,Y) является формальным понятием контекста K тогда и только тогда, когда выполняются следующие условия:
  |
(2.1) |
  |
(2.2) |
Отношение "быть более частным" (отношение "специализации") в модели вводится иначе, чем это принято для решеток понятий. А именно, требование антимонотонности для содержания понятия заменяется требованием монотонности.
Определение 2.21 Отношение "быть более частным" определяется следующим образом:
тогда и только тогда, когда
и
называется антимонотонным в смысле отношения
тогда и только тогда, когда
таких, что
называется монотонным в смысле отношения
тогда и только тогда, когда
означает, что бимножество
удовлетворяет ограничению
Ограничение на минимальный размер компонент бимножества выглядит следующим образом
. Такое ограничение монотонно по отношению
.
С помощью монотонного ограничения на допустимое число нулей, приходящихся на признак или объект, можно контролировать число нулей внутри бимножества, сохраняя при этом строгую связь между компонентами бимножества.
Определение 2.22 Пусть даны бимножество
и положительное целое число
, тогда
называется плотными тогда и только тогда, когда оно удовлетворяет антимонотонному ограничению
и
Необходимо извлекать такие бимножества
, для которых объекты
(соответственно, признаки
(соответственно на объектах из
(соответственно, на объектах
выражает разность нулевых значений внутри и вне бимножеств.
Определение 2.23 Пусть даны бимножество
и положительное целое число
называется релевантным тогда и только тогда, когда оно удовлетворяет следующему ограничению:
и
Фактически, плотные и релевантные бимножества являются обобщением формальных понятий, которые можно рассматривать как бимножества при значениях
и
— обобщение первого уравнения леммы 2.1 ,
обобщает второе уравнение этой леммы, означающее, что все внешние элементы по отношению к данному бимножеству содержат по крайней мере
нулевых значений в дополнение к уже имеющимся для каждого внутреннего элемента. Параметр
отвечает за плотность внутри бимножества, а параметр
показывает значимость разности с внешними элементами. Свойство
антимонотонно по отношению
и может быть использовано для эффективного отсечения. Свойство
не является ни монотонным, ни антимонотонным, но его также можно эффективно использовать.
Определение 2.24 Пусть дано плотное и релевантное бимножество
(т.е. удовлетворяющее
называется DR-бимножеством тогда и только тогда, когда оно максимально по отношению
такого, что
удовлетворяет
и
Множество всех таких пар контекста
при заданных
и
обозначается как
. Отметим, что для объектов и признаков можно ввести различные пороги
и
.
Назад Содержание Вперёд
Основные определения и свойства
Дадим определение частого множества признаков в терминах ФАП.
Определение 2.25 Пусть дан формальный контекст
. Множество признаков
называется частым множеством признаков, если
, где
— заданный числовой порог
.
Здесь контекст
представляет собой объектно-признаковую таблицу, которую можно интерпретировать как базу данных покупок,
— множество транзакций, а
— множество товаров.
Ключевым понятием для данной задачи является поддержка.
Определение 2.26 Пусть дан формальный контекст
. Поддержкой множества признаков
называется величина
Значение
показывает, какая доля объектов
содержит
Если задано значение минимальной поддержки
Определение 2.27 Пусть дан формальный контекст
называется частым множеством признаков, если
Дадим определения частых замкнутых множеств признаков и максимальных частых множеств признаков.
Определение 2.28 Пусть дан формальный контекст
. Множество признаков
называется частым замкнутым множеством признаков, если
и не существует
и
Используя оператор замыкания, можно дать следующее определение, эквивалентное 2.28.
Определение 2.29 Пусть дан формальный контекст
. Множество признаков
называется частым замкнутым множеством признаков, если
и
.
Определение 2.30 Пусть дан формальный контекст
. Множество признаков
называется максимальным частым множеством признаков, если
и не существует
, такого что
и
.
Пусть
— множество всех частых множеств признаков,
— множество всех частых замкнутых множеств признаков,
— множество всех максимальных частых множеств признаков. Тогда, очевидно, выполнено следующее соотношение
.
Как уже было отмечено выше, частые замкнутые множества позволяют компактно представлять все множество частых признаков без потерь информации об их частоте. Максимальные множества признаков, хотя и являются компактным представлением даже меньшего размера, не позволяют вычислить поддержку всех частых множеств признаков.
Тем не менее, применение максимальных частых множеств признаков оправдано для плотных контекстов, например, для данных телекоммуникационных компаний, данных переписи, данных последовательностей, изучаемых в биоинформатике. Это связано с тем, что для частого множества признаков длины
приходится вычислять
его частых подмножеств на ранних этапах работы алгоритмов, таких как Apriori. Поэтому MFI помогают понять структуру извлекаемых множеств признаков в указанных выше задачах (в случае плотных контекстов, для которых длина частых множеств признаков довольно часто равна 30-40), в то время как поиск всех частых множеств признаков оказывается невозможным.
Отметим два важных для практической реализации свойства частых множеств признаков.
Свойство 2.1 (нисходящее замыкание). Все подмножества частого множества признаков являются частыми.
Название свойства "нисходящее замыкание" (downward closure) обязано тому, что множество частых множеств признаков замкнуто по вложению.
Свойство 2.2 (антимонотонность). Все надмножества множества признаков, не являющего частым, не частые.
Свойство 2.1 позволяет создавать алгоритмы, использующие поуровневый поиск частых множеств признаков. А свойство антимонотонности помогает сократить число шагов такого поиска, т.е. не рассматривать надмножества множеств признаков, не являющихся частыми. Алгоритмы поиска частых множеств признаков, использующие эти два свойства, называются поуровневыми (levelwise).
Пример 2.1 Объектно-признаковая таблица транзакций
| Покупатели/товары | Пиво | Пряники | Молоко | Мюсли | Чипсы |
С |
1 | 0 | 0 | 0 | 1 |
С |
0 | 1 | 1 | 1 | 0 |
С |
1 | 0 | 1 | 1 | 1 |
С |
1 | 1 | 1 | 0 | 1 |
С |
0 | 1 | 1 | 1 | 1 |
Пиво, Чипсы
Молоко, Пиво, Чипсы
Назад Содержание Вперёд
Поиск сходства Интернет-документов с помощью частых замкнутых множеств признаков.
У множества документов в Интернете имеются дубликаты, в связи с чем необходимы средства эффективного вычисления кластеров документов-дубликатов [20, 21, 22, 26, 27, 40, 44, 46, 70, 61]. В этом разделе описываются исследования, посвященные применению алгоритмов Data Mining для поиска кластеров дубликатов с использованием синтаксических и лексических методов составления образов документов. На основе экспериментов делаются некоторые выводы о способе выбора параметров методов.
Постановка задачи
У огромного числа документов (по некоторым источникам до 30%) в Интернете имеются дубликаты, и поисковые машины должны обладать эффективными средствами вычисления кластеров дубликатов. Происхождение дубликатов может быть разным — от дублирования компаниями собственной информации на разных серверах (создание зеркал) до злонамеренных — обмана программ индексаторов веб-сайтов, незаконного копирования и спамерских рассылок.
Обычно дубликаты документов определяются на основе отношения сходства на парах документах: два документа сходны, если некоторая числовая мера их сходства превышает некоторый порог [20]. По отношению сходства вычисляются кластеры сходных документов, например, по транзитивному замыканию отношения сходства [20]. Вначале, после снятия HTML-разметки документы, как линейные последовательности слов (символов), преобразуются во множества. Здесь двумя основными схемами (определяющими весь возможный спектр смешанных методов) являются синтаксические и лексические методы. К синтаксическим относится метод шинглирования [22], в котором документ в итоге представляется набором хеш-кодов; этот метод испоьзовался в поисковых системах Google и AltaVista. В лексических методах [44] большое внимание уделяется построению словаря — набора дескриптивных слов; известны его разновидности, такие I-match и метод ключевых слов Ильинского [44].
На втором этапе из документа, представленного множеством синтаксических или лексических признаков, выбирается подмножество признаков, образующее краткое описание (образ) документа. На третьем этапе определяется отношение сходства на документах с помощью некоторой метрики сходства, сопоставляющей двум документам число в интервале [0, 1], и некоторого параметра — порога, выше которого находятся документы-дубликаты.
На основе отношения сходства документы объединяются в кластеры (полу-)дубликатов. Определение кластера также может варьироваться. Одно из возможных определений, часто используемых на практике (например, в компании AltaVista), но наиболее слабых, упоминается в обзоре [20]: если документам Интернета сопоставить граф, вершины которого соответствуют самим документам, а ребра — отношению «быть (почти) дубликатом», то кластером объявляется компонента связности такого графа. Достоинством такого определения является эффективность вычислений. Недостаток такого подхода очевиден: отношение «быть (почти) дубликатом» не является транзитивным, поэтому в кластер сходных документов могут попасть абсолютно разные документы.
В качестве противоположного — «самого сильного» — определения кластера, опирающимся на отношение «быть (почти) дубликатом», можно принять клики графа. При этом каждый документ из кластера должен быть сходным со всеми другими документами того же кластера. Такое определение кластера более адекватно передает представление о групповом сходстве, но, к сожалению, практически не применимо в масштабе Интернета, поскольку поиск клик в графе — классическая труднорешаемая задача.
Исходя из предложенных формулировок, можно было бы находить необходимый баланс между соответствием определения кластеров множествам «в самом деле» сходных документов и сложностью вычисления кластеров. Здесь мы рассматриваем сходство не как отношение на множестве документов, а как операцию, сопоставляющую двум документам множество общих элементов их сокращенных описаний, где в качестве элементов описания выступают либо синтаксические, либо лексические единицы. Кластер дубликатов определяется как множество документов, у которых число общих элементов описания превышает определенный порог.
Приводятся результаты экспериментальной проверки данного метода на основе сравнения результатов его применения (для разных значений порогов) со списком дубликатов, составленным на основе результатов применения других методов к тому же множеству документов. Исследовалось влияние на результат следующих параметров модели: использование синтаксических или лексических методов представления документов, использование методов «n минимальных элементов в перестановке» и «минимальные элементы в n перестановках» [20], параметры шинглирования, величина порога сходства образов документов. Одна из задач проекта заключалась в том, чтобы связать вычисление попарного сходства образов документов с построением кластеров документов, чтобы, с одной стороны, получаемые кластеры были бы независимы от порядка рассмотрения документов (в отличие от методов кластерного анализа), а с другой стороны гарантировали бы наличие реального попарного сходства всех образов документов в кластере.
Описание вычислительной модели
В качестве методов представления документов (создания образа документа) использовались стандартные синтаксические и лексические подходы с разными параметрами.
В рамках синтаксического подхода была реализована схема шинглирования и составление краткого образа (скетча) документов на основе методов «n минимальных элементов в перестановке» и «минимальные элементы в n перестановках», описание которых можно найти, например, в [21, 22].
Программа shingle с двумя параметрами length и offset порождает для каждого текста набор последовательностей слов (шинглов) длины length, так что отступ от начала одной последовательности до начала другой последовательности в тексте имеет размер offset. Полученное таким образом множество последовательностей хэшируется, так что каждая последовательность получает свой хэш-код.
Далее из множества хэш-кодов, соответствующему документу, выбирается подмножество фиксированного (с помощью параметра) размера с использованием случайных перестановок, описанных в работах [20, 21, 22]. При этом вероятность того, что минимальные элементы в перестановках хэш-кодов на множествах шинглов документов A и B (эти множества обозначаются через
и
Основные определения, связанные с частыми замкнутыми множествами, естественно, даются в терминах анализа формальных понятий (ФАП) [33]. Мы рассматриваем формальный контекст
показывает, что некий объект
обладает признаком
в том и только том случае, когда
множество их общих признаков
служит описанием их сходства, а замкнутое множество
является кластером сходных объектов (с множеством общих признаков
величина
является поддержкой B и обозначается supp(B).
Нетрудно видеть, что множество
замкнуто тогда и только тогда, когда для любого
имеет место
Множество
называется
(то есть множество признаков B встречается в более чем
объектах), где
— параметр.
Вычисление частых замкнутых множеств признаков (содержаний) приобрело важность в Data Mining благодаря тому, что по этим множествам эффективно вычисляются множества всех ассоциативных правил [59]. Фактически, мы будем вычислять частные замкнутые множества признаков для контекста, дуального к
Хотя теоретически размер множества всех замкнутых множеств признаков (содержаний) может быть экспоненциальным относительно числа признаков, на практике таблицы данных сильно "разрежены" (то есть среднее число признаков на один объект весьма мало), и число замкнутых множеств невелико. Для таких случаев существуют весьма эффективные алгоритмы построения всех наиболее частых замкнутых множеств признаков (см. также обзор по алгоритмам построения всех замкнутых множеств [47]).
В последние годы проводился ряд соревнований по быстродействию таких алгоритмов на серии международных семинаров под общим названием FIMI (Frequent Itemset Mining Implementations). Пока лидером по быстродействию считается алгоритм FPmax* [35], показавший наилучшие результаты по быстродействию в соревновании 2003 года. Мы использовали этот алгоритм для построения сходства документов и кластеров сходных документов. При этом в роли объектов выступали элементы описания (шинглы или слова), а в роли признаков — документы. Для такого представления «частыми замкнутыми множествами» являются замкнутые множества документов, для которых число общих единиц описания в образах документов превышает заданный порог.
Программная реализация и компьютерные эксперименты
Программные средства для проведения экспериментов в случае синтаксических методов включали следующие блоки:
парсер формата XML для коллекции ROMIP;
снятие html-разметки;
нарезка шинглов с заданными параметрами;
хэширование шинглов;
составление образа документов путем выбора подмножества (хэш-кодов) шинглов с помощью методов «n минимальных элементов в перестановке» и «минимальные элементы n n перестановках»;
cоставление по результатам методов 4-5 инвертированной таблицы «список идентификаторов документов—шингл» — подготовка данных к формату программ вычисления замкнутых множеств;
вычисление частых замкнутых множеств с заданным порогом общего числа документов, в которое входит данное множество шинглов: программа MyFim (реализующая алгоритм FPmax*);
сравнение со списком дубликатов РОМИП – программа Comparator.
В качестве экспериментального материала нами использовалась URL-коллекция РОМИП, состоящая из 52 файлов общего размера 4,04 Гб. Для проведения экспериментов коллекция разбивалась на несколько частей, включающих от трех до двадцати четырех файлов (приблизительно от 5% до 50% от размера всей коллекции).
В экспериментах использовались следующие пПараметры шинглирования: число слов в шингле 10 и 20, отступ между началом соседних шинглов 1. Данное значение отступа означает, что начальное множество шинглов включало все возможные последовательности цепочек слов.
Эксперименты проводились на персональном компьютере P-IV HT с тактовой частотой 3.0 ГГц, оперативной памятью объемом в 1024 Мб и операционной системой Windows XP Professional. Результаты экспериментов и время, затраченное на их проведение, частично приводятся в следующих таблицах и рисунках.
(1) Результаты работы метода “
минимальных элементов в перестановке”
FPmax |
All Pairs of Duplicates | Unique pairs of duplicates | Common pairs | |||
Input |
Threshold | ROMIP | Test | ROMIP | Test | |
b_1_20_s_100_n1-6.txt |
100 | 33267 | 7829 | 28897 | 3459 | 4370 |
| b_1_20_s_100_n1-6.txt | 95 | 33267 | 11452 | 26729 | 4914 | 6538 |
| b_1_20_s_100_n1-6.txt | 90 | 33267 | 17553 | 22717 | 7003 | 10550 |
| b_1_20_s_100_n1-6.txt | 85 | 33267 | 22052 | 21087 | 9872 | 12180 |
b_1_20_s_100_n1-12.txt |
100 | 105570 | 15072 | 97055 | 6557 | 8515 |
| b_1_20_s_100_n1-12.txt | 95 | 105570 | 20434 | 93982 | 8846 | 11588 |
| b_1_20_s_100_n1-12.txt | 90 | 105570 | 30858 | 87863 | 13151 | 17707 |
| b_1_20_s_100_n1-12.txt | 85 | 105570 | 41158 | 83150 | 18738 | 22420 |
b_1_20_s_100_n1-24.txt |
100 | 191834 | 41938 | 175876 | 25980 | 15958 |
| b_1_20_s_100_n1-24.txt | 95 | 191834 | 55643 | 169024 | 32833 | 22810 |
| b_1_20_s_100_n1-24.txt | 90 | 191834 | 84012 | 155138 | 47316 | 36696 |
| b_1_20_s_100_n1-24.txt | 85 | 191834 | 113100 | 136534 | 57800 | 55300 |
b_1_10_s_120_n1-6.txt |
120 | 33267 | 7725 | 29065 | 523 | 4202 |
| b_1_10_s_120_n1-6.txt | 115 | 33267 | 11763 | 26586 | 5082 | 6681 |
| b_1_10_s_120_n1-6.txt | 110 | 33267 | 11352 | 26547 | 4632 | 6720 |
b_1_10_s_150_n1-6.txt |
150 | 33267 | 6905 | 28813 | 2451 | 4454 |
| b_1_10_s_150_n1-6.txt | 145 | 33267 | 9543 | 27153 | 3429 | 6114 |
| b_1_10_s_150_n1-6.txt | 140 | 33267 | 13827 | 24579 | 5139 | 8688 |
| b_1_10_s_150_n1-6.txt | 135 | 33267 | 17958 | 21744 | 6435 | 11523 |
| b_1_10_s_150_n1-6.txt | 130 | 33267 | 21384 | 19927 | 8044 | 13340 |
| b_1_10_s_150_n1-6.txt | 125 | 33267 | 24490 | 19236 | 10459 | 14031 |
b_1_10_s_180_n1-6.txt |
170 | 33267 | 9834 | 27457 | 4024 | 5810 |
| b_1_10_s_180_n1-6.txt | 130 | 33267 | 38402 | 20142 | 25277 | 13125 |
| b_1_10_s_180_n1-6.txt | 120 | 33267 | 55779 | 19966 | 42478 | 13301 |
b_1_10_s_200_n1-6.txt |
200 | 33267 | 5083 | 29798 | 1614 | 3469 |
| b_1_10_s_200_n1-6.txt | 195 | 33267 | 6700 | 28661 | 2094 | 4606 |
| b_1_10_s_200_n1-6.txt | 190 | 33267 | 8827 | 27516 | 3076 | 5751 |
| b_1_10_s_200_n1-6.txt | 170 | 33267 | 12593 | 25866 | 5192 | 7401 |
| b_1_10_s_200_n1-6.txt | 135 | 33267 | 48787 | 19987 | 35507 | 13280 |
| b_1_10_s_200_n1-6.txt | 130 | 33267 | 57787 | 19994 | 44514 | 13273 |
(2) Результаты работы метода “минимальные элементы в n перестановках”.
| FPmax | All Pairs of Duplicates | Unique pairs of duplicates | Common pairs | |||
| Input | Threshold | ROMIP | Test | ROMIP | Test | |
| m_1_20_s_100_n1-3.txt | 100 | 16666 | 4409 | 14616 | 2359 | 2050 |
| m_1_20_s_100_n1-3.txt | 95 | 16666 | 5764 | 13887 | 2985 | 2779 |
| m_1_20_s_100_n1-3.txt | 90 | 16666 | 7601 | 12790 | 3725 | 3876 |
| m_1_20_s_100_n1-3.txt | 85 | 16666 | 9802 | 11763 | 4899 | 4903 |
| m_1_20_s_100_n1-6.txt | 100 | 33267 | 13266 | 28089 | 8088 | 5178 |
| m_1_20_s_100_n1-6.txt | 95 | 33267 | 15439 | 26802 | 8974 | 6465 |
| m_1_20_s_100_n1-6.txt | 90 | 33267 | 19393 | 24216 | 10342 | 9051 |
| m_1_20_s_100_n1-12.txt | 100 | 105570 | 21866 | 95223 | 11519 | 10347 |
| m_1_20_s_100_n1-12.txt | 95 | 105570 | 25457 | 93000 | 12887 | 12570 |
минимальных элементов в перестановке" и метода "минимальные элементы в
перестановках".
| Subcollection | Number of documents | Method | Time elapsed, sec | Shingling parameter | |
| length of shingle | image size | ||||
| narod.1-3.xml | 26077 | n-min | 312 | 20 | 100 |
| narod.1-6.xml | 53539 | n-min | 622 | 20 | 100 |
| narod.1-12.xml | 110997 | n-min | 1360 | 20 | 100 |
| narod.1-24.xml | 223804 | n-min | 2435 | 20 | 100 |
| narod.1-3.xml | 26077 | min in n | 924 | 20 | 100 |
| narod.1-6.xml | 53539 | min in n | 1905 | 20 | 100 |
| narod.1-12.xml | 110997 | min in n | 3617 | 20 | 100 |
| narod.1-24.xml | 223804 | min in n | 7501 | 20 | 100 |
| narod.1-3.xml | 26077 | n-min | 277 | 10 | 100 |
| narod.1-6.xml | 53539 | n-min | 563 | 10 | 100 |
| narod.1-12.xml | 110997 | n-min | 1118 | 10 | 100 |
| narod.1-24.xml | 223804 | n-min | 2348 | 10 | 100 |
| narod.1-3.xml | 110997 | n-min | 315 | 10 | 120 |
| narod.1-6.xml | 223804 | n-min | 622 | 10 | 120 |
| narod.1-3.xml | 110997 | n-min | 388 | 10 | 150 |
| narod.1-6.xml | 223804 | n-min | 745 | 10 | 150 |
| narod.1-6.xml | 223804 | n-min | 1312 | 10 | 180 |
| narod.1-6.xml | 223804 | n-min | 2585 | 10 | 200 |
| narod.1-6.xml | 223804 | n-min | 541 | 5 | 100 |
| narod.1-6.xml | 223804 | n-min | 611 | 15 | 100 |
| narod.1-6.xml | 223804 | min in n | 2101 | 10 | 200 |
(3) Время работы FPmax* для метода “
минимальных элементов в перестановке”.
| Input | Threshold | Time elapsed, |
| sec | ||
| b_1_20_s_100_n1-6.txt | 100 | 1,2 |
| b_1_20_s_100_n1-6.txt | 95 | 2,0 |
| b_1_20_s_100_n1-6.txt | 90 | 3,1 |
| b_1_20_s_100_n1-6.txt | 85 | 5,3 |
| b_1_20_s_100_n1-12.txt | 100 | 3,0 |
| b_1_20_s_100_n1-12.txt | 95 | 9,0 |
| b_1_20_s_100_n1-12.txt | 90 | 14,2 |
| b_1_20_s_100_n1-12.txt | 85 | 25,7 |
| b_1_20_s_100_n1-24.txt | 100 | 16,1 |
| b_1_20_s_100_n1-24.txt | 95 | 120,0 |
| b_1_20_s_100_n1-24.txt | 90 | 590,4 |
| b_1_20_s_100_n1-24.txt | 85 | 1710,6 |
| b_1_10_s_150_n1-6.txt | 150 | 1,75 |
| b_1_10_s_150_n1-6.txt | 145 | 3,265 |
| b_1_10_s_150_n1-6.txt | 140 | 19,609 |
| b_1_10_s_150_n1-6.txt | 135 | 97,046 |
| b_1_10_s_150_n1-6.txt | 130 | 36,609 |
| b_1_10_s_150_n1-6.txt | 125 | 11,75 |
Рис. 5.2. Время работы алгоритма FPmax* для размера образа документа n=150
(4) Время работы FPmax* для метода “минимальные элементы в
перестановках”.
| Input | Threshold | Time elapsed, |
| sec | ||
| m_1_20_s_n1-3.txt | 100 | 3,4 |
| m_1_20_s_n1-3.txt | 95 | 3,9 |
| m_1_20_s_n1-3.txt | 90 | 7,0 |
| m_1_20_s_n1-6.txt | 100 | 16,4 |
| m_1_20_s_n1-6.txt | 95 | 4479,6 |
| m_1_20_s_n1-6.txt | 90 | 7439,4 |
| m_1_20_s_n1-12.txt | 100 | 291,36 |
| m_1_20_s_n1-12.txt | 95 | 40418,796 |
Наклон верхней линии при учете логарифмического масштаба диаграмм напоминает о том, что теоретическая временная сложность (в худшем случае) работы алгоритма экспоненциальна.
(5) Сравнение эффективности алгоритмов поиска максимальных замкнутых множеств.
Рис. 5.4. Время работы алгоритмов FIM и AddIntent
По диаграмме видно, что наилучшие результаты показали алгоритмы Fpmax* и Afopt. А алгоритм AddIntent* из сообщества FCA-алгоритмов даже превзошел Mafia из FIMI, что является неплохим результатом для, как правило, более ресурсоемких алгоритмов первой группы.
Выводы и направление дальнейшей работы
По результатам наших экспериментов по использованию методов порождения частых замкнутых множеств в сочетании с традиционными синтаксическими и лексическими средствами можно сделать следующие выводы.
Методы порождения частых замкнутых множеств представляют эффективный способ определения сходства документов одновременно с порождением кластеров сходных документов.
На результаты синтаксических методов определения дубликатов значительное влияние оказывает параметр «длина шингла». Так, в наших экспериментах результаты для длины шингла, равной 10, были существенно ближе к списку дублей РОМИП, чем для длины шингла, равной 20, 15 и 5.
В экспериментах для всех значений параметров не было обнаружено существенного влияния использования метода «минимальные элементы в n перестановках» на качество результатов. По-видимому, на практике достаточно случайности, задаваемой отбором шинглов с помощью метода «n минимальных элементов в перестановке».
Необходимы дальнейшие эксперименты с использованием различных значений параметров синтаксических методов и сравнение результатов с результатами применения лексических методов, в которых используются инвертированные индексы коллекций. Необходимо сравнение методов кластеризации, в которых применяются замкнутые множества признаков, с алгоритмами, основанными на поиске минимальных разрезов вершин (cut) в двудольных графах, в которых множества вершин соответствуют множествам документов и множествам признаков [29, 87]. Эти методы родственны, поскольку замкнутые множества документов естественным образом выражаются через минимальные разрезы такого рода двудольных графов.
Назад Содержание Вперёд
Постановка задачи и основные определения
Под термином бикластеризация понимается широкий круг задач и методов, а потому для него в научной литературе существует целый ряд синонимов: совместная кластеризация (simultaneous clustering), кокластеризация (co-clustering), двувходовая кластеризация (two-way clustering), кластеризация подпространства (subspace clustering), двумерная кластеризация (bi-dimensional) и бокс-кластеризация (box-clustering). Повышенный интерес к бикластеризации и выделение ее в самостоятельную область анализа данных возникли в связи задачей анализа массивов генетических данных (microarray data analysis). Поэтому, прежде чем дать основные определения из области бикластеризации, мы опишем задачи анализа генетических данных и то, как бикластеринг оказывается полезен для их решения.
Обычно данные генной экспрессии (gene expression data) представляют собой матрицу, в которой строки соответствуют генам, а столбцы — условиям. Каждый элемент такой матрицы отражает уровень экспрессии некоторого гена при заданном условии и представлен действительным числом, как правило, логарифмом относительного содержания информационной РНК (mRNA) гена при этом условии. Такие матрицы, как правило, изучают в двух размерностях, в размерности генов или столбцов. Этим способам анализа соответствует выявление экспрессии шаблонов генов посредством сравнения строк или столбцов. Общие задачи такого анализа включают в себя:
группировку генов согласно их экспрессии для множества условий;
классификацию нового гена по известной экспрессии его и других генов для установленной классификации;
группировку условий, основанная на экспрессии конкретного множества генов;
классификацию нового образца при известной экспрессии генов и условиях эксперимента.
Методы кластеризации могут быть использованы для группирования либо генов, либо условий, а потому явно решают задачи 1 и 3, указанные выше, и неявно — 2 и 4. Но применение методов кластеризации к анализу данных генной экспрессии ведет к значительным сложностям. Активационные образцы образуют группы генов только при определенных экспериментальных условиях. Таким образом, понимание клеточных процессов указывает на то, что необходимо искать множество генов, ведущих себя слаженно и совместно выраженных только при некоторых экспериментальных условиях, и почти независимо при других условиях. А значит, необходимы специальные методы поиска таких локальных образцов, которые могли бы играть ключевую роль в открытии новых генетических взаимодействий [].
В отличие от методов кластеризации, алгоритмы бикластеризации находят группы генов, проявляющих сходную активность для некоторого подмножества экспериментальных условий. Поэтому подход бикластеризации позволяет успешно решать задачи, в которых возникает одна или сразу несколько таких ситуаций, как:
только небольшое множество генов, участвующих в клеточном процессе, представляют интерес;
интересующий исследователя клеточный процесс происходит только при некотором подмножестве условий;
один ген может участвовать во многих взаимодействиях, которые как могут быть совместно активными, так и не могут для всех условий.
Поэтому предлагаемые методы бикластеризации должны следовать требованиям, перечисленным ниже.
Кластер генов необходимо определять в соответствии только подмножеству условий.
Кластер условий необходимо определять в соответствии только подмножеству генов.
Кластеры не должны быть исключающими и/или полными (гены или условия могут принадлежать ко многим кластерам или вообще ни к одному, а также могуть быть сгруппированы по подмножеству условий или генов соответственно).
В качестве дополнительного требования можно отметить робастность, понимаемую как наличие мощного (с точки зрения сложности процесса генетической регуляции) инструмента анализа и устойчивость к шуму в исходных данных.
Фактически, мы будем работать с матрицей размера n на m, элементы которой в общем случае представляют собой действительные числа. Абстрагируясь от задач анализа генетических данных мы будем считать, что строкам матрицы соответствуют некоторые объекты, а столбцам — признаки. Пусть дана матрица
,
— строк,
— число столбцов,
— множество строк,
— множество столбцов. Будем использовать
для обозначения матрицы
. Если
и
подмножества строк и столбцов соответственно, то
определяет подматрицу
матрицы
.
Кластер строк есть подматрица матрицы
вида
, для которой подмножество строк проявляет "сходное поведение" вдоль всего множества столбцов.
Кластер столбцов есть подматрица матрицы
вида
, для которой подмножество столбцов проявляет "сходное поведение" вдоль строк. Бикластер есть подматрица матрицы
вида
, такая что ее строки проявляют "сходное поведение" на столбцах и наоборот.
Отметим, что мы дали недостаточно формальное определение бикластера. В рамках моделей, представленных в работе, требования, которые предъявляются к понятию бикластера, различаются, а потому формальные определения даются нами только для конкретных случаев. Задача, которую решает алгоритм бикластеризации, заключается в нахождении такого множества бикластеров
Приложения в биологии: анализ генетических данных
Как уже было указано в разделе1.1, задача бикластеризации в последние годы приобрела большую популярность в связи с растущей потребностью в анализе генетических данных. Почти каждая работа в этой области, описывающая новый алгоритм бикластеризации, содержит раздел посвященный экспериментам на реальных данных.
Приведем несколько примеров. Ченг и Черч в работе [25] применяют бикластеризацию к двум матрицам генной экспрессии, а именно, к данным, описывающим клетки дрожжей (Yeast Saccharomyces Cerevisiae) для 2884 генов и 17 условий, и к данным о B-клетках человека (B-cells) для 4026 генов и 96 условий. Танг и др. [78] применяют алгоритм ITWC к данным генной экспрессии с 4132 генами и 48 примерами пациентов множественного склероза, а Бен-Дор и др. [16] используют данные о раке груди для 3226 генов при 22 различных экспериментальных условиях.
Напомним, что основная задача такого анализа — выявление групп генов, проявляющих сходное поведение только при определенных условиях. В дальнейшем специалист генетик на основании проведенного анализа выдвигает гипотезу о том, является ли данная группа генов причиной исследуемой болезни.
Помимо данных генной экспрессии, в качестве приложений в биологии можно привести пример из работы Лиу и Ванга [53], которые анализировали активность лекарственных препаратов на матрице из 10000 строк и 30 столбцов, в которой каждой строке соответствовало химическое вещество, а столбцы представляли его признаки.
В сообществе рассматриваются и другие массивы генетических данных, в основном относящихся к раковым заболеваниям, таким как лимфома.
Программные средства бикластеризации
Разработано довольно большое количество программных систем, которые можно отнести к программам бикластеризации. Как правило, такие системы служат нуждам какой-либо конкретной области, и методы бикластеризации являются одним из инструментов, доступных аналитику наряду с традиционными методами анализа данных (например, кластеризацией). В этой части работы мы не будем детально описывать каждую из рассматриваемых систем, и приведенный их перечень будет далеко не полным.
Суть в том, что для каждой области применения мы укажем хотя бы одно из такое средство и кратко опишем его возможности. Основными областями применения в нашем рассмотрении являются биоинформатика (генетические данные), Data Mining, Формальный Анализ Понятий, социальные сети, графовая и спектральная кластеризация.
Программные средства сообщества ФАП
Среди программных средств в области ФАП отметим только три наиболее часто используемые исследователями программы, находящиеся в свободном доступе: Concept Explorer [2], ToscanaJ [39] и Galicia [80]. Кратко опишем их назначение и возможности.
Все они пригодны для построения решеток понятий и отображения их диаграмм. Отличительными особенностями ConceptExplorer являются удобный интерфейс, наличие нескольких способов рисования диаграммы решетки, а также поиск базиса импликаций и ассоциативных правил. Помимо этого, ConExp поддерживает исследование признаков — интерактивную процедуру приобретения знаний.
Программа ToscanaJ позволяет строить вложенные диаграммы решеток понятий, шкалировать признаки в смысле ФАП, устанавливать связь с базами данных и предоставляет некоторые возможности, учитывающие динамику решеток.
Программа Galicia не отличается удобным интерфейсом, но предоставляет массу возможностей, а именно, позволяет шкалировать признаки,строить решетки-айсберги, находить базис импликаций, множество генераторов для данного понятия и отображать трехмерную диаграмму решетки понятий.
Шумоустойчивые понятия
В связи с тем, что в исходных 0/1 данных, имеющих объектно-признаковую природу, могут присутствовать ошибочные значения (пропущенные объекты/признаки или напротив лишние) использование Формального Анализа Понятий приводит к увеличению количества формальных понятий. Чтобы избежать порождения таких нерелевантных понятий, необходимы новые типы структур, учитывающие шум такого рода. В качестве одной из таких структур в работе [19] предложено понятие плотного и релевантного бимножеств (DR-bi-set). Одно из свойств DR-бимножества, называющееся плотностью, состоит в том, что внутри подматрицы, образующей такое бимножество, допускается некоторое количество нулей. Формальное понятие является частным случаем DR-бимножества, для которого число нулевых элементов внутри подматрицы равно 0. Ниже будут рассмотрены основные определения и свойства DR-бимножеств, а также приведено описание алгоритма DR-miner.
Система бикластеризации генетических данных BicAT
Опишем систему BicAT, разработанную швейцарскими учеными, которые специализируются в области биоинформатики и анализа генетических данных. Отметим также, что данное программное обеспечение свободно распространяется.
В системе BicAT реализованы следующие методы бикластеризации:
алгоритм Ченга и Черча (CC), в котором используется величина среднеквадратичного остатка[25];
алгоритм итеративной сигнатуры (the Iterative Signature Algorithm, ISA), в котором ищутся подматрицы, представляющие собой неподвижные точки [43];
алгоритм, сохраняющий порядок на подматрицах (the Order-Preserving Submatrix Algorithm, OPSM) и обнаруживающий большие подматрицы, для которых линейный порядок, заданный на столбцах, выполняется на всех строках [16];
алгоритм xMotifs — итеративный метод, отыскивающий бикластеры с квази-постоянными значениями выражений [58];
Bimax — точный алгоритм бикластеризации, основанный на стратегии "разделяй и властвуй", которая приспособлена для нахождения всех максимальных биклик в соответствующем графовом представлении матрицы [60].
Дополнительно реализованы две стандартных процедуры кластеризации, а именно, иерархическая кластеризация и метод K-средних.
Кратко опишем основные функции и возможности системы бикластеризации BicAT.
Матрица исходных данных отображается в главном окне системы в виде так называемой тепловой карты (меньшим значениям степени проявления генов соответствует зеленый цвет, большим — красный). К средствам предобработки данных, реализованным в системе, можно отнести нормализацию, дискретизацию и логарифмирование входных значений. Подобные процедуры необходимы для адекватной работы методов; например, метод Bimax принимает в качестве входных данных только двоичные матрицы, а следовательно, бинарная дискретизация значений необходима.
Результаты работы каждого метода отображаются в виде древесной структуры в левой области главного окна системы. Там же отображаются узлы дерева, соответствующие исходным наборам данных и результатам предобработки. Для каждого из методов бикластеризации можно задать специфические параметры, например, число кластеров для метода CC или ограничения на размер бикластера для метода Bimax.
В системе реализованы средства поиска бикластеров по имени гена и/или признака, а также механизм фильтрации результатов бикластеризации по размеру бикластеров (сверху и снизу) и степени их перекрытия. Помимо таких, очевидно, необходимых средств постобработки, в системе реализован метод парного анализа генов (Gene Pair Analysis), позволяющий исследовать совстречаемость пар генов.
В системе приняты соглашения об именовании наборов данных и результатов анализа, существует возможность их экспорта в текстовый формат.
Система Coron для Data Mining
Система анализа данных Coron[74] предназначена для поиска частых множеств признаков и ассоциативных правил. Следует особо отметить, что данный продукт является результатом диссертационной работы Ласло Затмари.
Программа обладает неплохим графическим интерфейсом, собственным форматом данных, возможностью работы с базами данных. Для поиска частых множеств признаков используются наиболее эффективные алгоритмы сообщества FIM, а также алгоритмы, разработанные самим автором [75]. Поиск ассоциативных правил также использует эффективные алгоритмы, опирающиеся на достижения ФАП и оказавшиеся полезными для компактного представления правил и построения их базисов. Еще одним достоинством продукта является свободный доступ и кроссплатформенность (в смысле технологии Java).
Социальные сети: выявление сообществ
В последние годы возобновился интерес к междисциплинарным исследованиям в области анализа социальных сетей, в которых задействованы математическая социология и информатика, опирающиеся на аппарат теории графов. Усилия в этом направлении в значительной степени поддерживаются благодаря новым вычислительным возможностям и доступности электронных данных для некоторых социальных систем: сообществ ученых, людей, ведущих личные электронные дневники (weblogers), покупателей интернет-магазинов, сетей друзей, сайтов знакомств и так далее.
В частности, в центре многих текущих исследований находятся сети знаний, т.е. сети взаимодействий, в которых агенты производят знания или обмениваются ими. В число исследований входит выявление сообществ, рассматриваемое как нахождение агентов, которые обладают множеством общих признаков. Анализ социальных сетей специализируется на методах выявления, описания и правдоподобной организации различных видов социальных сообществ. Для анализа социальных аспектов сообществ основной интерес представляют лидеры, периферийные члены, межгрупповое и внутригрупповое взаимодействие.
Решетки понятий, которые мы рассматриваем как способ бикластерзации, успешно применялись для анализа эпистемических сообществ[65,63] (т.е. агентов, имеющих дело с одинаковыми темами, например, научные сообщества или пользователи блогов) или филиальных сетей (акторы принадлежат одной и той же организации). Успех этого подхода обусловлен наличием таксономий бикластеров, что оказывается полезным при иерархическом описании групп акторов в терминах сходства интересов.
Отметим ключевые работы, которые способствовали росту интереса к исследованиям в этой области. В начале 90-х известный американский социолог Линтон Фриман стал применять решетки понятий в контексте социальных исследований [32], другой важной фигурой является французский исследователь Винсент Дюкен [82]. Часть работ, в которых используется ФАП, связана с исследованием веб-сообществ, например, статья [64]. С применением ФАП проводились также исследования посещаемости сайтов, а именно, выполнялось построение таксономий групп посетителей, см. работы Кузнецова и Игнатова [50] и Кедрова и Кузнецова [4]. Более подробно постановка задачи исследования посещаемости сайтов и пути ее решения обсуждаются в разделе 4.2.
Структура бикластеров
Среди разработанных алгоритмов представлены как те, что находят только один бикластер, так и алгоритмы, порождающие множество бикластеров. Бикластеры, входящие в такое множество, могут иметь различную структуру. Приведем перечень возможных вариантов структуры бикластеров:
исключающие по строкам и столбцам бикластеры (прямоугольные диагональные блоки после переупорядочивания строк и столбцов);
неперекрывающиеся бикластеры со структурой шахматной доски;
бикластеры, исключающие пересечения по строкам;
бикластеры, исключающие пересечения по столбцам;
неперекрывающиеся бикластеры с древесной структурой;
неперекрывающиеся не исключающие пересечения бикластеры;
перекрывающиеся бикластеры с иерархической структурой;
произвольно расположенные перекрывающиеся бикластеры.
Таблица 1.2. Примеры структуры бикластеров
В таблице 1.2 проиллюстрированы различные типы структуры бикластеров. На рисунке буквой a обозначен одиночный бикластер, исключающие пересечения по строкам и столбцам бикластеры, неперекрывающиеся бикластеры со структурой шахматной доски, бикластеры, исключающие пересечения по строкам, бикластеры, исключающие пересечения по столбцам, неперекрывающиеся бикластеры с древесной структурой, неперекрывающиеся, не исключающие пересечения бикластеры, перекрывающиеся бикластеры с иерархической структурой и произвольно расположенные перекрывающиеся бикластеры.
Связь ассоциативных правил и бикластеризации
Пусть даны два соседних формальных понятия в смысле отношения покрытия
и
определяет бикластер
— достоверность признакового ассоциативного правила для этих понятий, а
— достоверность объектного ассоциативного правила. Тогда максимальное число незаполненных (нулевых) ячеек в таком бикластере определяется величиной
очевидно, что
Назад Содержание Вперёд
Связь частых замкнутых множеств признаков и ФАП
В сообществе ФАП хорошо известен тот факт, что семейства частых множеств обладают решеточной структурой (см., например, [59]). Приведем определение решетки замкнутых частых множеств признаков.
Определение 2.31 Пусть дан формальный контекст
и множество всех частых замкнутых множеств признаков
для
образует полную решетку, называемую решеткой частых замкнутых множества признаков.
Отметим, что такая решетка изоморфна решетке понятий соответствующего контекста, а ее элементы совпадают с содержаниями понятий. Если задать ограничение на величину поддержки, то мы получим так называемую решетку-айсберг, т.е. верхнюю часть
и формальных понятий см. [72].
Теория решёток и Формальный Анализ Понятий
Формальный Анализ Понятий — область прикладной математики, объектами исследования в которой являются (формальные) понятия и их иерархии. Прилагательное "формальный" указывает на наличие строгого математического определения понятия, как пары множеств, называемых, следуя традициям принятым в философии, объемом и содержанием. Формализация этих определений стала возможной благодаря использованию аппарата алгебраической теории решеток. Включение подраздела, посвященного ФАП, в раздел о методах и моделях бикластеризации обосновано широким спектром задач из области анализа данных, в которых ключевым является поиск бикластеров особого рода — формальных понятий. Мы не будем описывать алгоритмы ФАП в данной работе, поскольку им посвящены целые обзоры[47], а дадим лишь основные определения, составляющие основу вычислительной модели наших экспериментов.
Типы бикластеров
Укажем основные типы бикластеров, которые обнаруживают различные алгоритмы бикластеризации:
бикластер с постоянными значениями;
бикластер с постоянными значениями по строкам или столбцам;
бикластер с когерентными значениями;
бикластер с когерентными изменениями.
Таблица 1.1. Примеры различных типов бикластеров
В таблице1.1 приведены примеры основных типов бикластеров. Дадим пояснения: бикластер с постоянными значениями, бикластер с постоянными значениями по строкам, бикластер с постоянными значениями по столбцам, когерентные значения в рамках аддитивной модели, когерентные значения в рамках мультипликативной модели, когерентное изменение по всему бикластеру, когерентное изменение по строкам, когерентное изменение по столбцам, когерентное возрастание и/или убывание значений генной экспрессии.
Типы данных
Как уже говорилось выше, исходные данные представляют собой числовую матрицу. Значения этой матрицы в зависимости от необходимого представления данных могут принадлежать множеству действительных чисел или только лишь множеству
. Значительная часть алгоритмов бикластеризации работает только с бинарными данными, например, BiMax, DR-miner и все алгоритмы поиска формальных понятий и частых (замкнутых) множеств признаков. И хотя существуют техники сведения вещественных и целочисленных данных к бинарным, такие как дискретизация и шкалирование, представляется необходимым четко разделять методы по типу данных.
В настоящее время методы кластерного
В настоящее время методы кластерного анализа являются востребованными в огромном количестве прикладных задач разных областей науки и техники. Сама область кластеризации, несмотря на непрерывное развитие и появление новых приложений, имеет прочную теоретическую базу и подтвержденные результаты. Изначально постановки задач кластеризации и классификации очень близки, основное отличие состоит в том, что решение проблемы классификации требует отнести некий анализируемый объект к наперед заданному классу, а в случае кластеризации такие классы необходимо породить на основе свойств исследуемых объектов. Не случайно поэтому в машинном обучении кластер-анализ называют обучением без учителя.
Ключевым понятием кластер-анализа является сходство объектов, которое, как правило, выражается математически посредством меры (метрики) близости. На основе значения этой меры делается вывод о близости объектов и принимается решение об их принадлежности одному кластеру. Несмотря на то, что человеку привычнее воспринимать объектно-признаковое описание данных, в ходе кластер-анализа такое представление обычно теряется, его заменяет матрица сходства, например, объектов. Да и в самих кластерах общее признаковое описание составляющих их объектов явно не выражено. А это приводит к появлению абсурдных классов объектов, например, хорошо известна цепочка слов превращающих "муху" в "слона". Оказывается, некоторые методы кластеризации работают таким образом, что "мухи" и "слоны" оказываются в одном кластере. Помимо этого, не ясно, что общего может быть между огурцом и ботинком, окажись они объектами некоторого кластера. Но в терминах признакового описания мы можем выяснить, что огурец такой же шершавый, как и ботинок из крокодиловой кожи, да и цветом не отличается.
Приведенные примеры кажутся забавными, но в реальных задачах, где цена ошибочного разбиения на классы велика, а невозможность интерпретации результатов экспериментов грозит провалом исследований, такие недостатки методов кластеризации могут иметь существенное значение. Например, при решении задачи поиска документов-дубликатов для Web-страниц, с которой вполне успешно справляются поисковые системы, такие как Google или Yandex, в одном кластере могут оказаться совершенно непохожие документы. К этому приводит тот факт, что существует цепочка документов, в которой каждый документ сходен в чем-то с соседним, но сходство это не транзитивно, а потому общее признаковое описание таких документов при вычислении сходства на каждом шаге не учитывается. В результате страдает пользователь поисковой системы, от которого скрыты эти неверно выявленные нечеткие дубликаты, и поэтому поиск рискует оказаться нерелевантным.
Существует широкий спектр задач, в которых требуется выявлять кластеры с сохранением объектно-признакового описания данных. Это задачи выявления групп генов, обладающих общими свойствами, в биоинформатике, поиск групп посетителей со схожими интересами для рекомендательных систем, выявление интернет-сообществ, научных сообществ, задача анализа социальных сетей, построение автоматических каталогов и рубрикаторов в информационных системах, поиск документов-дубликатов.
Методы кластеризации, разработанные для этих целей, лежат в области кластер-анализа и получили свое собственное название — бикластеризация. Приставка би- указывает на двукомпонентность кластеров, выявляемых методами бикластеризации. Например, для генетических данных первым компонентом такого кластера является множество генов, а вторым — множество экспериментов, в которых они проявляли себя сходным образом. Термин "бикластеризация" впервые упомянут в работе[], и хотя похожие формулировки и методы встречались ранее (см. [] ), мы, тем не менее, будем использовать это собирательное название для всей группы методов, описываемых в данной работе, которые применяются для построения таких двукомпонентных кластеров.
В связи с вышеизложенным, основная цель обзора состоит в том, чтобы описать состояние дел в разных областях исследований, в которых нашли применение методы бикластеризации, выявить такие методы, выработать единые принципы их оценки, построить их адекватную классификацию. А также определить те из них, которые подходят для решения задач анализа интернет-данных (Web-mining), а именно выявления групп посетителей сайтов со сходными интересами или поведением, построения таксономий аудитории сайтов, а также задач анализа социальных сетей в Интернете и поиска нечетких веб-дубликатов. Отправной точкой такого исследования является прикладная математическая дисциплина Формальный Анализ Понятий (ФАП) [].
В рамках этой области сформулировано математическое определение формальных понятий, описано построение их иерархий. Исходно формальное понятие является парой вида (объем, содержание), где под объемом понимается некоторое множество объектов, а под содержанием — множество их общих признаков. Как видим, это определение напоминает описание бикластера. Исходные данные в ФАП представляются в виде объектно-признаковой матрицы, состоящей из нулей и единиц, а формальным понятием является максимальный прямоугольник такой матрицы, заполненный единицами. Это означает, что данное подмножество объектов обладает всеми признаками некоторого подмножества признаков.
Далее для такого множества понятий строится их иерархия, представляющая собой полную решетку, называемую решеткой понятий. Существует ряд работ, исследующих возможности "ослабления" требований к определению формального понятия, например, шумоустойчивые понятия (в смысле []). Необходимость такого рода ослаблений вызвана жесткой структурой формальных понятий, требующей наличия всех признаков из содержания понятия у объектов его объема, однако в случае наличия шума возможны "выпадения" некоторых признаков из содержания понятия.
В работах [,] предложен подход, использующий нечеткие решетки понятий, в котором значения исходных данных лежат в диапазоне [0, 1]. Причина, по которой целесообразно использование нечетких решеток — возможность более точного описания исходных данных, например, частоты посещения пользователем веб-сайта. Еще одним желательным требованием является сокращение числа таких бикластеров, так как при применении подхода ФАП их количество экспоненциально растет от размера входа. Отчасти проблема порождения большого числа формальных понятий решена путем введения индекса устойчивости формального понятия []. В этом случае из множества порожденных понятий отбираются те из них, для которых индекс устойчивости превышает некоторый заданный порог. Проблемы отбора релевантных задаче формальных понятий (бикластеров) также обсуждаются в рамках работы.
Что касается моделей "бокс-кластеризации", описанных в [], то для них характерно наличие сходного подхода и параметров, которые используются для выявления шумоустойчивых понятий []. Для моделей этого типа также характерно наличие перекрытий или пересечений бикластеров, степень которых оказывается существенной при решении ряда задач. В задачах бикластеризации, решаемых генетиками, используется похожий аппарат, но не всегда значения входной матрицы являются булевыми, как в работе [], в большинстве случаев они положительные вещественные (например, метод OPSM [] ). Это, в свою очередь, приводит к использованию статистических свойств данных при построении моделей (см. []). У большинства из этих методов, применяемых в биоинформатике, имеются похожие недостатки, например, проблема определения числа кластеров, проблема локального оптимума вследствие использования жадной стратегии поиска [].
Отдельно стоят методы спектральной кластеризации, которые изначально опираются на спектральные свойства матричного представления графа связей между объектами. В последнее время эти методы активно применяются в Интернет-маркетинге, где связи "рекламодатели-слова" представлены двудольным графом [] и помогают отыскивать потенциальных рекламодателей среди тех, кто не использует некоторые из слов, что купили их конкуренты. Фактически, эти методы искусственно адаптированы для задачи бикластеризации, поскольку для найденных кластеров приходится восстанавливать их объектно-признаковую структуру (т.е. бикластер).
Для большинства методов, происходящих не из сообщества ФАП, характерно отсутствие иерархии порожденных кластеров, что затрудняет их анализ исследователем. В рамках работы будет предпринята попытка установить возможность построения такой иерархии для остальных методов бикластеризации; такая иерархия предположительно будет носить решеточный или полурешеточный характер.
Исследователями вне ФАП также не используется аппарат ассоциативных правил, являющихся ключевыми в Data Mining при поиске признаковых зависимостей. Ассоциативные правила можно порождать на признаковых описаниях бикластеров, предполагается проведение соответствующих экспериментов. Помимо исследователей, использующих аппарат ассоциативных правил, в Data Mining существует сообщество FIMI (Frequent Itemset Mining Implementation), изучающее проблемы поиска частых (замкнутых) множеств признаков в больших базах данных. Отметим, что замкнутые множества признаков являются в точности содержаниями формальных понятий. Поэтому, как модель бикластеризации, методы FIMI будут включены в обзор.
Максимальные замкнутые множества признаков составляют только часть замкнутых, а потому их можно рассматривать в качестве альтернативы способам сокращения числа формальных понятий для модели ФАП. Еще одним из способов такого сокращения является использование решеток-айсбергов, предложенных в [], этот подход аналогичен отбору ассоциативных правил в Data Mining по порогу величины поддержки.
В соответствии с целью исследования были поставлены следующие задачи:
Выявить и описать методы бикластеризации, использующиеся в различных областях анализа данных, но не вошедшие в современные научные обзоры других исследователей;
Построить таксономию алгоритмов и моделей бикластеризации на основе хорошо структурированных критериев;
Привести обзор областей применения методов бикластеризации;
Составить перечень программных средств бикластеризации по областям применения;
Выбрать и реализовать некоторые из алгоритмов для проведения экспериментов на массивах Интернет-данных;
Показать пригодность методов бикластеризации для анализа Интернет-данных на экспериментальном материале;
В ряде случаев провести сравнительный анализ особенностей методов и установить связь между используемыми вычислительными моделями.
В рамках работы не оставлены без внимания системы поиска бикластеров, приводится их обзор. В частности, это системы
BicAT — область применения биоинформатика,
Concept Explorer, ToscanaJ, Galicia — сообщество ФАП,
Coron — Data Mining (ассоциативные правила и частые множества признаков),
Cluto, Metis — графовая кластеризация,
и Chaco — спектральная кластеризация.
Обзор состоит из введения, пяти разделов, заключения и списка литературы.
В разделе — "Бикластеризация" описана одноименная задача, указано на ее ключевую роль в анализе данных генетической экспрессии. Приводятся основания для классификации методов и моделей бикластеризации. Определяются типы бикластеров, их структура, стратегии поиска алгоритмов и области значений исходных данных. Построена решеточная таксономия методов бикластеризации.
В разделе — "Методы и модели бикластеризации" приводится обзор различных подходов анализа данных, учитывающих их объектно-признаковый характер. Даны основные определения теории решеток и ФАП. Показана связь ассоциативных правил с бикластерами определенного типа.
Раздел — "Программные средства бикластеризации" содержит краткий обзор программного обеспечения, которое призвано решать задачи бикластеризации в различных предметных областях.
Раздел — "Прикладные задачи" представляет собой краткий обзор основных областей применения алгоритмов бикластеризации с указанием библиографии и пригодных для решения соответсвующих задач методов.
Раздел — "Эксперименты на массивах Интернет-данных" описывает результаты применения изучаемых подходов к решению задач поиска документов-дубликатов в Интернете, выявления Интернет-сообществ пользователей на основе статистики посещаемости сайтов и рекомендаций в системах контекстной рекламы.
В работе дан обзор методов
В работе дан обзор методов бикластеризации, построена их решеточная таксономия. Показана связь ассоциативных правил и бикластеризации. Проведена серия экспериментов на реальных массивах Интернет-данных.
Предложена математическая модель ассоциативных метаправил для формирования рекомендаций в системах контекстной Интернет-рекламы. Для их построения использован ФАП, алгоритмы поиска ассоциаций, а также элементы компьютерной лингвистики, такие как стемминг. Во втором важном типе метаправил используется понятие онтологии.
Основное преимущество этих методов состоит в том, что без предварительного анализа самих данных можно сгенерировать высоко достоверные рекомендации. Это позволяет выдавать рекомендации уже на ранних этапах деятельности, когда клиентская база не велика. Результаты подтверждены экспериментально. Помимо этого показана состоятельность методов ФАП для выявления относительно крупных рынков рекламодателей и слов.
Предложена модель, в которой для поиска документов-дубликатов используются частые (замкнутые) множества признаков и ФАП. Экспериментально подтверждена обоснованность данной вычислительной модели на массиве РОМИП.
Для выявления сообществ посетителей сайтов и построения их таксономий предложено использовать аппарат ФАП. Применение индекса устойчивости позволяет проводить визуализацию относительно больших массивов данных о посещаемости, что является полезным средством для веб-аналитика.
В качестве возможных направлений дальнейших исследований отметим следующее:
изучение свойств бикластеров:
определение степени перекрытия бикластеров, густоты внутри бикластера и густоты вне;
оценка возможности определения порядка на бикластерах, анализ их алгебраической структуры;
изучение связи некоторых параметров бикластеризации с индексами типа устойчивости;
уточнение и расширение оснований для классификации бикластеров для построения более полной и точной таксономии алгоритмов и методов;
исследование связи методов: шумоустойчивые понятия и бокс-кластеризация, ФАП и спектральная кластеризация.
