Бикластеризация объектно-признаковых данных на основе решеток замкнутых множеств

Размещено на http://www.allbest.ru/

Бикластеризация объектно-признаковых данных на основе решеток замкнутых множеств

Введение

алгоритм бикластеризация множество

В настоящее время по сравнению с традиционным кластерным анализом методы бикластеризации завоевывают все большую популярность, особенно в рядах исследователей в области биоинформатики для изучения данных генной экспрессии Madeira et al., 2004. Это вызвано потребностью в сохранении объектно-признаковой структуры данных, например, для адекватного понимания в каких свойствах выражено сходство некоторой группы генов. Различные приложения этих методов востребованы в области анализа Интернет-данных, например, такие алгоритмы - основа некоторых рекомендательных Интернет-сервисов Ignatov et al., 2008.

В данной работе мы представляем метод бикластеризации, основанный на решетках формальных понятий. Благодаря средствам анализа формальных понятий (АФП) Ganter et al., 1999 для любых объектно-признаковых данных можно построить иерархическую структуру формальных понятий (бикластеров специального вида), позволяющую отобразить их таксономические свойства в удобном для аналитика виде. Основным недостатком решеток понятий является их громоздкость, например, для объектно-признаковой таблицы размером 10х10 число бикластеров в худшем случае равно 210. Одной из задач, на решение которой направлены усилия ученых, работающих в данном сообществе, является разработка методов по отбору наиболее полезных, релевантных понятий, сокращению размеров порождаемого множества понятий. Один из подходов заключается в ослаблении требований к формальным понятиям, в его рамках возможно не только сокращение числа порождаемых бикластеров, но успешное устранение влияния шума на результаты Besson et al., 2006. Нами предлагается метод бикластеризации, который использует только небольшую часть формальных понятий (объектные и признаковые), для порождения бикластеров особого вида. В качестве критерия отбора релевантных бикластеров применяется их плотность. В дополнение к описываемой в статье версии алгоритма предлагается ее параллельная реализация. Проводятся эксперименты на реальных данных, иллюстрирующие улучшение производительности благодаря оптимизации и распараллеливанию при различных порогах плотности.

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

Контекстом в АФП называют тройку = (G, M, I), где G -- множество объектов, M -- множество признаков, а отношение I G M говорит о том, какие объекты обладают теми или иными признаками.

Для произвольных A G и B M определены операторы Галуа:

A' = {m M | g A (g I m)};

B' = {g G | m B (g I m)}.

Оператор (.)'' (двукратное применение оператора (.)') является оператором замыкания: он идемпотентен (A'''' = A''), монотонен (A B влечет A'' B'') и экстенсивен (A A'').

Множество объектов A G, для которого A'' = A, называется замкнутым. Аналогично для замкнутых множеств признаков - подмножеств множества M.

Пара множеств (A, B), таких, что A G, B M, A' = B и B' = A, называется формальным понятием контекста .

Множества A и B замкнуты и называются объемом и содержанием формального понятия (A, B) соответственно.

Для множества объектов A множество их общих признаков A' служит описанием сходства объектов из множества A, а замкнутое множество A'' является кластером сходных объектов (с множеством общих признаков A').

Множество объектных понятий образовано парами объектов (g'', g') для всех g G, а множество признаковых понятий - (m', m'') для всех mM.

Термин бикластер предложен в работе Миркин, 1996 и означает множество объектов, сходство которых задано посредством общих значений признаков.

Другое определение бикластера предложено в работе Barkov et al., 2006. Алгоритм Bi-Max, описанный в этой работе строит максимальные по вложению бикластеры, определяемые следующим образом.

Дано m генов, n ситуаций и бинарная таблица e такая, что e_ij=1 (ген i активен в ситуации j) или e_ij=0 (ген i не активен в ситуации j) для всех i1,m и j1,n.

Пара (G, C)2^{1,…,n}Ч2^{1,…,m} называется максимальным по вложению бикластером тогда и только тогда, когда выполнено (1) для любых iG и jC: e_ij=1 и (2) не существует (G₁,C₁) 2^{1,…,n}Ч2^{1,…,m} таких, что (a) для любых i₁G₁ и j₁C₁: e_ij=1 и (b) GG₁, СC₁ и (G₁, C₁)(G, C).

Пусть H - множество генов, S - множество ситуаций, а EHЧS - бинарное отношение задаваемое таблицей e, |H|=m, |S|=n. Верно следующее утверждение

Утверждение 1. Для любой пары (G, C), GH, CS следующие два утверждения эквивалентны.

(G, C) максимальный по вложению бикластер таблицы e;

(G, C) формальное понятие контекста (H, S, E).

В следующем разделе мы дадим определение бикластера, основанное на АФП.

Вычислительная модель

Определение 1. Если (g,m)I, то (m',g') называется объектно-признаковым бикластером или оа-бикластером с плотностью с(m',g')=|I?(m'Чg')|/(|m'||g'|).

Приведем основные свойства оа-бикластеров (рис. 1).

Утверждение 2.

1. 0?с?1.

2. оа-бикластер (m',g') является формальным понятием тогда и только тогда, когда с=1.

3. Если (m', g') - бикластер, то (g'', g')?(m', m'').

Рис. 1. оа-бикластер

Определение 2. Пусть (A,B)2^GЧ2^M будет бикластером и с_min неотрицательное действительное число такое, что 0?с_min?1, тогда (A, B) называется плотным, если он удовлетворяет ограничению с(A,B)?с_min.

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

Отношение на множестве оа-бикластеров определяется по вложению соответствующих компонент: (A, B) (C, D)AC и BD.

Утверждение 3. Ограничение с(A,B)? с_min не является ни монотонным, ни антимонотонным в смысле отношения .

Однако ограничение с_min обладает другими полезными свойствами. Если с_min=0, то мы получаем множество всех оа-бикластеров контекста . Для с_min=0 каждое формальное понятие исходного контекста содержится в некотором его оа-бикластере, т.е. верно следующее утверждение.

Утверждение 4. Для любого (A_c, B_c)B(G, M, I) существует бикластер (A_b, B_b)B такой что (A_c, B_c)(A_a, B_b).

Утверждение 5. Для данного формального контекста = (G, M, I) и с_min=0 наибольшее число оа-бикластеров равно |I|, а все оа-бикластеры порождаются за время O(|I|(|G|+|M|)).

Утверждение 6. Для данного формального контекста = (G, M, I) и с_min>0 наибольшее число оа-бикластеров равно |I|, а все оа-бикластеры порождаются за время O(|I||G||M|).

Интересующее нас множество бикластеров является результатом работы Алгоритма 1 (табл. 1).

Табл. 1.

Благодаря свойству антимонотонности оператора (.)' мы провели оптимизацию условия порождения бикластера в цикле 6-10 и избежали вычисления операции замыкания в циклах 2-3 и 4-5.

Результаты

Для экспериментальной оценки эффективности предложенного алгоритма бикластеризации была запрограммирована версия Алгоритма 1. В качестве языка реализации был выбран C# из среды разработки Microsoft Visual Studio 2008. Дополнительно была исследована возможность распараллеливания (масштабирования) алгоритма с помощью средств библиотеки Task Parallel Library, входящей в состав Microsoft .NET Framework 4.0.

Эксперименты были проведены на данных из UCI Machine Learning Repository и на массиве данных о покупке рекламных словосочетаний компании Yahoo. В таблице 2 приведено описание этих наборов данных, для каждого из них указано количество объектов, признаков, число пар принадлежащих отношению I, плотность контекста и количество его формальных понятий.

Табл. 2.

Помимо производительности алгоритмов нас интересовала зависимость количества порождаемых оа-бикластеров от выбранного порога плотности с_min, результаты экспериментов приведены в таблице 3.

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

Табл. 3.

Отношение числа порожденных понятий к количеству бикластеров показано в таблице 4.

Табл. 4.

Приведем результаты экспериментов по оценке временной эффективности алгоритмов на самом крупном из имеющихся массивов реальных данных - advertising (рис. 2).

Зависимость количества бикластеров от величины порога носит довольно плавный характер, хотя для некоторых данных UCI Machine Learning Repository это количество остается постоянным при уменьшении значения порога на 0,1, начиная с 1, для нескольких первых точек.

По рисунку 2 можно судить о том, что параллельная версия оптимизированного алгоритма работает быстрее последовательной реализации на 45%. Дополнительные эксперименты проведены на массивах данных из UCI Machine Learning Repository, результаты носят аналогичный характер.

Рис. 2. Сравнение производительности алгоритмов

Благодарности. Работа выполнена при финансовой поддержке РФФИ (проект № 08-07-92497-НЦНИЛ_а).