Оценка и сравнение производительности алгоритмов анализа формальных понятий

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

Государственный университет - Высшая школа экономики, Москва

Оценка и сравнение производительности алгоритмов анализа формальных понятий

А.А. Незнанов

Ф.В. Строк

Анализ формальных понятий (АФП) [formal concept analysis - FCA] - важная часть теории решёток, нашедшая широкое применение при разработке методов искусственного интеллекта [Ganter et al., 2005].

В работе исследуются конкретные реализации различных алгоритмов решения базовых задач АФП. Существует много разнообразных программных решений в области анализа формальных понятий. Однако вопросам их эффективности посвящено довольно мало исследований. Последнее серьёзное исследование датируется 2004 годом (семинар FIMI'04 [Bayardo et al., 2004]) при этом оно посвящено задачам поиска частых замкнутых множеств признаков, задаче хоть и близкой к анализу формальных понятий, однако существенно менее трудоёмкой, так как ответом является только подмножество формальных понятий, удовлетворяющих некоторым ограничениям. До этого в работе [Kuznetsov et al., 2002] были исследованы алгоритмы построения решёток формальных понятий. Результаты текущего исследования были получены в том числе на семинаре «Workshop on comparison of FCA algorithms» в рамках 17-й международной конференции по понятийным структурам IССS'09, основные цели проведения которого - выявление наиболее эффективных реализаций и зависимости их производительности от параметров входных данных (формальных контекстов).

Основные понятия АФП

Анализ формальных понятий применяется для автоматического получения онтологий на основе заданного множества объектов и характеризующих каждый объект признаков. Формально это описывается следующим образом.

Пусть - множество объектов, - множество признаков, - отношение, тогда и только тогда, когда объект g обладает признаком m. В таком случае тройка называется формальным контекстом [formal context]. Вводится оператор Галуа:

,

.

Для любых :

,

,

.

Таким образом, и определяют отображение Галуа между и . Обычно вместо и используют нотацию :

,

.

Формальное понятие [formal concept] - пара такая, что:

.

В этом случае A - называется формальным объемом [extent], а B - формальным содержанием [intent].

Из определения следует, что .

Предположим, что и - формальные понятия в контексте . Если (или, что эквивалентно, ), тогда понятие менее общее, чем , или совпадает с ним.

Получаем частичный порядок на множестве формальных понятий:

.

Формальные понятия, отсортированные в соответствии с таким порядком, образуют полную решетку, которую называют решеткой формальных понятий .

Постановка задачи

Для задач АФП было разработано и реализовано значительное количество алгоритмов. Чтобы сравнивать различные реализации алгоритмов, в предметной области было выделено следующие три характерные задачи.

T1: Породить множество всех формальных понятий, с возможность наложения ограничений на размер объема и\или содержания.

T2: Построить решетку формальных понятий (множество формальных понятий + отношение покрытия на нем).

T3: Вычислить базис импликаций Дюкена-Гига [Ganter et al., 2005].

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

Методология сравнения эффективности

Сравнительный анализ корректности и эффективности базировался на следующих основополагающих принципах.

Проведение вычислительных экспериментов и оценка вычислительной сложности в автоматическом режиме.

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

Сравнение не только на лучших и худших случаях входных данных, но и на наборах данных «средней» сложности.

Проверка корректности реализации одновременно с оценкой производительности.

В качестве тестового стенда мы использовали автоматизированную систему научных исследований «Graph Model Workshop» (АСНИ «GMW»), разработанную В.А. Коховым, С.В. Ткаченко и А.А. Незнановым. Этот программный комплекс позволяет в автоматическом режиме проводить многоэтапные вычислительные эксперименты с одновременным подсчётом времени выполнения и ведением базы данных результатов. Встроенные средства позволяют подготавливать исходные данные, анализировать эффективность и сравнивать полученные результаты.

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

Для оценки влияния накладных расходов на время выполнения алгоритмов реализациям была предоставлена возможность сохранения собственной оценки времени выполнения в базе данных результатов. Мы не будем приводить результаты сравнения внутреннего (самой реализацией) и внешнего (проводимого АСНИ) времени выполнения, так как анализ показал практически константное (с минимальной дисперсией) превышение первого над вторым на используемых исходных данных.

Основное внимание было уделено задаче T1. Для проверки корректности ответов к данной задаче был использован контроль упрощенного ответа: реализация выводила количество понятий с заданным размером объема. Эти данные в предопределенном порядке сохранились в базе результатов и автоматически сравнивались после завершения каждого эксперимента.

Исследуемые реализации

В таблице 1 перечислены реализации, которые показали корректное и устойчивое поведение. Они были исследованы в полном объёме.

Таблица 1

Подготовка исходных данных

В ходе сравнения производительности использовалось четыре типа входных данных:

1) конструктивно порождённые наборы данных;

2) случайно порожденные наборы данных;

3) наборы данных из репозитория UCI [Frank, 2010];

4) данные, предложенные участниками семинара.

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

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

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

Для проведения первоначального сравнения мы использовали три набора данных, характеристики которых приведены в таблице 2.

Таблица 2

Получение результатов

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

Все протоколируемые эксперименты проводились на компьютере с процессором Intel Core 2 Quad 2,4 ГГц, 4 ГБ оперативной памяти и операционной системой Microsoft Windows 7. Это позволило создать уникальную базу данных для тонкого анализа поведения алгоритмов и особенностей их реализации. Демонстрационные прогоны проводились и с использованием других вычислительных средств.

Примеры оценки и сравнения эффективности

На первом наборе данных были протестированы все 4 реализации. Однако AddIntent и Norris проявили себя как значительно более медленные по времени программы, так что мы исключим их из дальнейшего рассмотрения.

На рис. 1 представлено поведение всех четырёх реализаций на первой тестовой базе. На этом и последующих рисунках графики соотносятся с реализациями алгоритмов по следующим правилам: AddIntent обозначается квадратами, Norris - ромбами, InClose - треугольниками, FCbO - кругами.

Рис. 1. Контексты 100*100

Рис. 2. Контексты 100*100, без AddIntent

Рис. 3. Контексты 100*100, только FCbO и InClose

Две реализации, FCbO и InClose, вели себя схожим образом при тестировании на всех трех базах входных данных. Однако в то время, как FCbO менее чувствителен к росту плотности входного контекста, InClose оказался менее зависим от размера входных данных (рис. 4 и рис. 5).

Рис. 4. Контексты 250*250

Рис. 5. Контексты с постоянной плотностью 0,05

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

Это можно объяснить тем фактом, в что в рамках семинара «Workshop on comparison of FCA algorithms» авторы соответствующих реализаций обменялись идеями по поводу методов считывания исходных данных из файлов и доработали реализации, что положительно сказалось как на абсолютном времени работы, так и на распределении мест (InClose первоначально уступал в этом тесте порядка 5-7% времени). Тем не менее принципиальные отличия алгоритмов не были сглажены, InClose работает с данными, представленными в формате .cxt ([Burmeister, 1996]), в то время, как FCbO ориентирован на обработку данных в файлах .fimi ([FIMI, 2003]). Помимо этого, Jan Outrata, один из разработчиков FCbO, в рамках семинара утверждал, что данный алгоритм легко распараллеливается.

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

Список литературы

алгоритмизация автоматический онтология формальный

1. [Кузнецов, 1993] Кузнецов С.О. Быстрый алгоритм построения всех пересечений объектов из конечной полурешетки // НТИ Сер. 2. - 1993, № 1.

2. [Bayardo et al., 2004] Bayardo R., Goethals B., Zaki M.J. Workshop on Frequent Itemset Mining Implementations (FIMI'04) in Proceedings of the IEEE ICDM Workshop on Frequent Itemset Mining Implementations . Brighton, UK, November 1, 2004 (http://sunsite.informatik.rwth-aachen.de/Publications/CEUR-WS/. Vol-126).

3. [Burmeister, 1996] Burmeister P. Formal concept analysis with ConImp: Introduction to the basic features. Technical report, TU-Darmstadt, Darmstadt, Germany, 1996.

4. [FIMI, 2003] Frequent Itemset Mining Dataset Repository (http://fimi.cs.helsinki.fi/data).

5. [FIMI, 2004] Frequent Itemset Mining Implementations Repository (http://fimi.cs.helsinki.fi).

6. [Frank et al., 2010] Frank A., Asuncion,A. (2010). UCI Machine Learning Repository (http://archive.ics.uci.edu/ml). Irvine, CA: University of California, School of Information and Computer Science.

7. [Ganter et al., 2005] Ganter B., Stumme G., Wille R., eds. (2005). Formal Concept Analysis: Foundations and Applications, Lecture Notes in Artificial Intelligence, no. 3626, Springer-Verlag.

8. [Kuznetsov et al., 2002] Kuznetsov S.O., Obiedkov S.A. Comparing performance of algorithms for generating concept lattices. J. Exp. Theor. Artif. Intell.: 2002. № 14 (2-3).

9. [Merwe et al., 2004] Merwe D., Obiedkov S., Kourie D. AddIntent: A New Incremental Algorithm for Constructing Concept Lattices, Second International Conference on Formal Concept Analysis, ICFCA 2004 Sydney, Australia, February 23-26, 2004 Proceedings.

10. [Norris, 1978] Norris E.M. An algorithm for computing the maximal rectangles in a binary relation, Revue Roumaine de Mathйmatiques Pures et Appliquйes. 1978. № 23 (2).

Размещено на Allbest.ru