Алгоритмы и методы теории решеток и их применение в машинном обучении тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Объедков, Сергей Александрович

• Объедков, Сергей Александрович
• кандидат технических наук
• 2003

Оглавление диссертации кандидат технических наук Объедков, Сергей Александрович

Введение.

Глава 1: Теория решеток п анализ формальных понятий.

1.1 Частично упорядоченные множества и решетки.

1.2 Операторы замыкания.

1.3 Операторы замыкания и системы замыкания в полурешетке.

1.4 Импликации.

1.5 Анализ формальных понятий.

Глава 2: Решетки формальных понятий в автоматическом порождении гипотез.

2.1 Импликации и ассоциативные правила.

2.2 ДСМ-метод.

2.2.1 ДСМ-метод в терминах анализа формальных понятий: Основные определения.

2.2.2 О пользе итераций.

2.2.3 Варианты ДСМ-гииотез.

Глава 3: Алгоритмы построения решеток формальных понятий и их применение для порождения гипотез.

3.1 О принципах сравнения.

3.2 Обзор алгоритмов.

3.2.1 Борда.

3.2.2 Следующее замыкание.

3.2.3 Замыкай по однотиу.

3.2.4 Линдиг.

3.2.5 Шен.

3.2.6 Нурпн.

3.2.7 Норрис.

3.2.8 Годан.

3.2.9 Добавь атом.

3.2.10 Другие алгоритмы.

3.3 Эксперименты.

3.4 Алгоритмы порождения понятий в машинном обучении.

Глава 4: Алгоритмы построения базиса импликаций.

4.1 Алгоритм Гантера вычисления базиса Дюкенна-Гига.

4. 2 Пошаговый алгоритм вычисления базиса Дгокепна—Гига.

4.2.1 Типы импликаций.

4.2.2 Описание алгоритма.

4.2.3 Экспериментальное сравнение.

Глава 5: Рассуждение в условиях частичной информации: Неполные контексты.

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

5.2 Оценка формул с помощью логики Клини.

5.3 Модальная лотка для неполных контекстов.

5.3.1 Модальная логика бессмыслицы.

5.3.2. Применение модалытоп логики бессмыслицы для оценки формул в неполных контекстах.

Введение диссертации (часть автореферата) на тему «Алгоритмы и методы теории решеток и их применение в машинном обучении»

Отправной точкой настоящей работы послужили алгоритмические потребности двух, на первый взгляд, не связанных между собой направлений исследований: ДСМ-метода автоматического порождения гипотез (Финн, 1990) с одной стороны и анализа формальных понятий (Ganter, Wille, 1999) — с другой.

ДСМ-метод представляет собой логическую теорию правдоподобного вывода (Финн, 1983, 1991), область применения которой — машинное обучение и анализ данных (Кузнецов, 1991а, б). ДСМ-рассркдение сформулировано на языке бескопечнозггачпой слабой ЛОШШ предикатов второго порядка (Anshakov et al., 1989). В случае конечных моделей формализация ДСМ-метода возможна в рамках логики первого порядка (Виноградов, 2000). В применении к анализу данных, задача, решаемая ДСМ-методом, приблизительно такова: даны положительные и отрицательные примеры некоторого свойства; требуется выявить причины наличия и отсугствпя этого свойства, причем информация о причинах должна быть доступна в таком виде, чтобы на ее основе было возможно отнести НОВЫЙ объект к положительным или отрицательным примерам свойства. ДСМ-рассуждеипс является комбинацией трех логических Процедур. На нервом шаге (ппдукция) происходит анализ и обобщение исходных данных, что позволяет выдвинуть гипотезы о причинах наличия и отсутствия рассматриваемого свойства. На втором шаге (аналогия) полученные гипотезы используются для предсказания наличия или отсутствия свойства у объектов, о которых ранее такой информации не было. Первые два шага могут итерироваться так, что иа каждом следующем шаге используется новая информация, полученная на предыдущем шаге, до тех пор, пока на каком-то шаге получение НОВОЙ информации не окажется невозможным. Тогда на третьем шаге (абдукция) проверяется способность множества гипотез, порожденных на первом шаге (во всех его итеративных воплощениях), к объяснению всего множества исходных фактов, т.е. объяснению того, почем)' тот или иной исходный объект обладает или не обладает данным свойством. Если результат проверки отрицателен, то делается вывод о том, что исходная информация недостаточна для построения надежной теории и требуется внешнее пополнение массива данных новыми объектами. В некоторых случаях механизм итераций позволяет не сообщать, являются ли новые объекты положительными или отрицательными примерами свойства: ДСМ-система попробует решить этот вопрос самостоятельно по аналогии и в случае удачи использовать полученную информацию для индуктивного построения новых гипотез о причинах наличия и отсутствия свойства.

Основным инструментом ДСМ-метода при порожАешш гипотез о причинах свойства является операция сходства, сопоставляющая двум объектам их общую часть. Для объектов, описанных множествами признаков, сходство — максимальное общее подмножество признаков, для объектов, описанных графами — множество максимальных общих подграфов и т.д. Операция СХОДСГВа является полурешеточной операцией, что, конечно, ограничивает применимость ДСМ-метода данными, для которых возможно естественное определение такой операции, НО, вместе с тем, предоставляет в распоряжение ДСМ-метода богатый аппарат теории решеток.

Цель анализа формальных понятий — сделать теорию решеток (Birkhoff, 1979) ближе, понятнее и легче в применении для потенциального пользователя. В этом смысле анализ формальных понятий «можно рассматривать, главным образом, как часть прикладной теории решеток» (Ganter, Wille, 1999). Его методы находят применение в разных областях: машинное обучение, анализ данных и обнаружение знаний, информационный ПОПСК и Т.Д. (Carpineto, Romano, 1996; Stumme et ai, 199B; Ganter, Kuznetsov, 2000; Stumme et al, 2000). В частности, на языке формальных понятой можно сформулировать и ДСМ-метод, тем самым, охарактеризовав последний с теоретико-решеточной точки зрения (Ganter, Kuznetsov, 2000). Анализ формальных понятий основан на том, что любая полная решетка может быть представлена бинарной матрицей (Barbut, Monjardet, 1970). В применении к анализу данных одной из наиболее часто возникающих задач является задача построения по бинарной объектно-признаковой матрице, называемой формальным контекстом, решетки, называемой решеткой понятий. Решетку понятий можно рассматривать как подробную классификацию данных, использовать для нетривиальной визуализации данных (с помощью диаграммы Хассе), строить на ее основе гипотезы (например, ДСМ-гииотезы).

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

Б контексте данной работы нас интересует именно решение алгоритмических вопросов, возникающих в анализе формальных понятий и релевантных для анализа данных, и в значительно меньшей степени сами методы анализа данных, основанные на теоретико-решеточных конструкциях. Тем не менее, кажется необходимым охарактеризовать эти методы и показать, в чем состоит релевантность исследуемых алгоритмов. Этому посвящена Глава 2. Под анализом данных мы понимаем, главным образом, обнаружение в данных всевозможных зависимостей, обладающих топ или иной степенью правдоподобия, и использование этих зависимостей для восстановления полноты данных (в случае их изначальной неполноты), классификации новых данных и т.д. В Главе 2 дается определение разновидностей таких зависимостей — импликаций и ассоциативных правил — в терминах анализа формальных понятий. В последнее десятилетие, ассоциативные правила стали одним из самых популярных способов анализа данных (Agrawal et al., 1993; Agrawal, Srikant, 1994; Agrawal et al, 1996). Далее в тех же терминах кратко описаны основные идеи ДСМ-метода автоматического порождения гипотез. Теоретико-решеточная формулировка ДСМ-метода оказывается полезной во многих отношениях. В частности, она позволяет нам выявить условия осмысленности итераций — повторною применения ДСМ-метода к данным, дополненным информацией, полученной первым применением ДСМ-метода к тем же самым данным. Кроме того, становится очевидным место ДСМ-метода среди родственных ему методов. Импликации и ассоциативные правила, с одной стороны, и ДСМ-гипотезы, с другой, задают пространство, в котором находятся интересующие нас зависимости, причем ДСМ-гипотезы — наиболее осторожны и, как следствие, наиболее правдоподобны. В (Кузнецов, 2002) данное пространство рассматривается как пространство версий в смысле (Mitchel, 1978, 1982). В этом пространстве находятся и гипотезы разработанного нами совместно с П.А. Григорьевым, С.А. Евтушенко и С.О. Кузнецовым нового метода, использующего не только сходство, но и различие (Grigoriev et al, 2002). Он также описан в Главе 2.

Важным для нас фактом теоретико-решеточной интерпретации ДСМ-метода является применимость (и даже необходимость) алгоритмов построения решеток понятий для порождения ДСМ-гппотез. Два основных алгоритма анализа формальных понятий согласно (Ganter, 1984) — это алгоритмы построения (по формальному контексту) решетки понятий и базиса импликаций (т.е., минимального множества импликаций, из которого могут быть получены все импликации с помощью определенных правил вывода). Как показано в (Zaki, Ogihara, 1998; Pasquier et al, 1999a), базис ассоциативных правил вычисляется на основе решетки понятий и базиса импликаций.

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

Известно большое число алгоритмов, строящих решетку понятий. Основная вычислительная проблема состоит в том, что число понятий в худшем случае может быть экспоненциально велико от размера входа, т.е. от числа объектов и признаков контекста (бинарной таблицы). Поэтому теоретически хорошим может считаться алгоритм, имеющий временную сложность, линейную от числа понятий. В Главе 3 мы даем теоретическое и экспериментальное сравнение алгоритмов построения решеток ПОНЯТИЙ, выполненное совместно с С.О. Кузнецовым. Некоторые пз сравшгваемых алгоритмов широко известны (Norris, 1978; Ganter, 1984; Godin, 1995), другие сообщены нам авторами, но опубликованы пока только как препринты (Ferré, 2002; Van Der Merwe, Kourie, 2002), третьи имеют только приблизительные аналоги в литературе (Bordât, 1986) или были существенно переработаны нами с целью повышения быстродействия (Chein, 1969).

Несколько иначе обстоит дело с алгоритмами построения канонического базиса импликаций — базиса Дюкенна-Гига (Guigues, Duqueiine, 1986). Собственно, известен только один алгоритм, выполняющий эту задачу напрямую — алгоритм Гантера (Ganter, 1984). Вместе с В. Дкженном мы разработали новый алгоритм построения базпеа импликаций, описанию и обоснованию которого и посвящена Глава 4. В большинстве случает!, этот алгоритм позволяет добиться существенного ускорения по сравнению с алгоритмом Гантера; другим его преимуществом является способность работать в пошаговом режиме: обновлять базис, не перестраивая его целиком, при добавлении в контекст нового признака.

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

Заключение диссертации по теме «Теоретические основы информатики», Объедков, Сергей Александрович

ЗАКЛЮЧЕНИЕ

Подводя итоги, можно сказать, что в диссертации получены новые теоретические результаты в области анализа формальных понятий и машинного обучения. Рассмотрены варианты использования теории решеток и анализа формальных понятий в области машинного обучения. Дана теоретико-решеточная характеристика некоторых свойств ДСМ-метода автоматического порождения гипотез. Разработаны новые и улучшены известные алгоритмы построения решеток понятий (решеток Галуа) и базиса импликаций. Проведено их теоретическое и эксперггментальное сравнение; рассмотрены возможности их адаптации к задачам анализа данных.

В процессе работы над диссертацией автором были получены следующие основные научные результаты:

1. Разработаны новые и улучшены известные ранее алгоритмы построения решеток понятий и базиса импликации. Новые алгоритмы и новые версии известных алгоритмов работают в целом быстрее предшественников.

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

3. Предложен новый метод анализа данных, основанный на идее различия положительного и отрицательного примера свойства как причины этого свойства. Новый метод анализа данных демонстрирует возможность рационального использования пространства между минимальными посылками импликаций и минимальными ДСМ-гипотезами.

4. Осуществлена теоретико-решеточная интерпретация итераций в ДСМ-методе (повторного применения метода к массиву, обогащенному новыми данными, полученными в результате предыдущих применений метода). Описаны условия, необходимые и достаточные для того, чтобы итерации привели к появлению новых данных.

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

Список литературы диссертационного исследования кандидат технических наук Объедков, Сергей Александрович, 2003 год

1. Виноградов Д.В. Формализацияправдоподобньгх рассуждений в логике предикатов. НТИ, Сер. 2 (11), С. 17-20, 2000.

2. Гандлевскин С. Трепанация черепа. Саггкт-Петербург: Пушкинский фонд, 1996.

3. Гршорьев П., Количественная аргументация гипотез о структурных зависимостях. Труды Седьмой национальной конференции по искусственному интеллекту (ШПГ2000), Переславль-Залесский, С. 37 — 43, 2000.

4. Евтушенко С. Исследование и разработка алгоритмов построения концептуальных решеток, Магистерская аттестационнаяработа, НТУУ «КПИ», Киев, 2000.

5. Забежайло М.И., Ивашко В.Г., Кузнецов С.О., Михеенкова М.А., Хазановский К.П., Аншаков О.М. Алгоритмические и программные средства ДСМ-метода автоматического порождения гипотез. HTII, Сер. 2 (10): С. 1 14, 1987.

6. Кузнецов С.О. Интерпретация на графах и сложностные характеристики задач поиска закономерностей определенного вида. HTII, сер. 2 (1): С. 23-28,1989.

7. Кузнецов С.О. ДСМ-метод как системаавтоматического обучения. Итоги науки и техники, сер. Информатика, 15: С. 17 — 54, 1991а.

8. Кузнецов С.О. Модели и методыавтоматического обучения. 11тоги Науки и Техники, сер. Вычислительные науки, 7: С. 89-137,19916.

9. Кузнецов С.О. Быстрый алгоритм построения всех пересечений объектов из конечной полурешетки. HUI, Сер. 2 (1): 17 — 20, 1993.

10. Кузнецов С., Объедков С. Алгоритмыпостроения множества всех понятий и егодиаграммы Хассе. Труды 4-ой Международной конференции «Интеграция, информационные технологии, телекоммуникации» (НТИ—99), Москва, С. 230-234,1999.

11. Кузнецов С., Объедков С. Алгоритмы построения множества всех понятий формального контекста и его диаграммы Хассе. Известия Академии наук. Теория и системы управления (1): С. 120 — 129, 2001.

12. Кузнецов С.О. Теория машинного обучения в решетках формальных понятий, Диссертация на соискание ученой степени доктора физико-математических наук.1. ВИНИТИ, 2002.

13. Мейер Д. Теория реляционных баз данных. Москва: Мир, 1987.

14. Объедков С. Алгоритмы порожденияминимальных пересечений. Труды 3-ей Международной конференции «Информационные ресурсы, интеграция, технологии» (НТИ—97), Москва, 1997.

15. Объедков С. Алгоритмические аспекты ДСМ-метода автоматического порождения гипотез. НТИ, Сер. 2 (1 2): С. 64 - 75, 1999.

16. Объедков С. Эффективное построение множества понятий и его диаграммы Хассе. Труды Седьмой национальной конференции по исгусственному интеллекту (КИИ'2000), Переславль-Залесский, С. 59— 66, 20006.

17. Панкратов Д.В., Михеенкова М.А. Об интеллектуальной системе анализа социологического поведения. Труды Седьмой национальной конференции по искусственному интеллекту (КИИ'2000), Переславль-Залесский, С. 76—82, 2000.

18. Панкратов Д.В. Логические и программные средства качественного анализа социологических данных, Диссертация на соискание ученой степени кандидата технических наук. ВИНИТИ, 2001.

19. Путрин А.В. Описание программной реализации ДСМ-систем для прогнозирования химической канцерогенности. HTII, Сер. 2 (12): С. 34 — 39,1999.

20. Финн В.К. О машинно-ориентированной формализации правдоподобных рассуждений в стиле Ф. Бэкона — Д.С. Милля. Семиотика и информатика, 20: С. 35— 101,1983.

21. Финн В.К. Правдоподобные выводы иправдоподобные рассуждения. Итоги науки и техн., Сер. Теория вероятностей Мат. стат. Теор. Кибернет., 28: С. 3 84,1988.

22. Финн В.К. ДСМ-метод автоматического порождения гипотез с отношением порядка. Семиотика и информатика, 31: С. 69 -103,1990.

23. Финн В.К. Правдоподобные рассуждения в интеллектуальных системах типа ДСМ. Итоги науки и техники, Сер. Информатика, 15 «Интеллектуальные информационные системы»: С. 54 101,1991.

24. Agrawal R., Imielinski Т., Swami A. Miningassociation rules between sets of items in large databases, Proceedings, ACM SIGMOD Conference on Management of Data, Washington D.C., pp. 207-216,1993.

25. Agrawal R., Srikant R. Fast algorithms for mining association rules. Proceedings, 20"' International Conference on Very Large Databases, Santiago, Chile, 1994.

26. Agrawal R., Manilla H., Srikant R., Toivonen H., Verkamo A.I. Fast discovery of association rules. In U. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy (eds) Advances in Knowledge Discover}' and Data Mining. Menlo Park CA: AAAI Press, 1996.

27. Aho A.V., Hopcroft J.E., Ullmann J.D. Data Structures and Algorithms. Reading: Addison— Wesley, 1983.

28. Akers S.B. Binary decision diagrams. IEEE Transactions on Computers, C-27 (6): 509—516, 1978.

29. Anshakov O.M., Finn V.K., Skvortsov, D.P. On axiomatization of many-valued logics associated with the formalization of plausible reasonings. Stud. Log., 25 (4): 23-47,1989.

30. Armstrong W.W. Dependency structure of data base relationships. Proceedings, IFIP Congress, Geneva, Switzerland, pp. 580-583, 1974.

31. Barbut M., Monjardet B. Ordre et classification, II. Paris : Hachette, 1970.

32. Birkhoff G.D. Lattice Theory. Amer. Math. Soc., 1979.

33. Blackburn P., de Rijke M., Venema, Y. Modal Logic. Cambridge: Cambridge University Press, 2001.

34. Blake C.L., Merz C.J. UCI Repository of machine learning databaseshttp: / / www.ics.uci.edu/~mlearn/MLReposi tory.html., Irvine, CA: University of California, Department of Information and Computer Science, 1998.

35. Bordât J.P. Calcul pratique du treillis de Galois d'une correspondance. Math. Sci. Hum., 96: 31-47,1986.

36. Burmeister P., Holzer, R. On the treatment of incomplete knowledge in formal concept analysis. Proceedings 8th Int. Conf. on Conceptual Structures, ICCS 2000, Lecture Notes in Artificial Intelligence, 1867, Darmstadt, Germany, pp. 385-398, 2000.

37. Carpineto C., Romano, G. A. A lattice conceptual clustering system and its application to browsing retrieval. Machine Learning., 24: 95— 122,1996.

38. Chein M. Algorithme de recherche des sous-matrices premières d'une matrice. Bull. Math. Soc. Sci. Math. R.S. Roumanie, 13: 21-25,1969.

39. Coupland D. Microserfs. London: Flamingo, 1996.

40. Davey B.A., Priestley H.A. Introduction to Lattices and Order. Cambridge: Cambridge University Press, 1990.

41. Doignon J.-P., Falmagne J.-C. Knowledge Spaces. Berlin: Springer, 1999.

42. Dowling C.E. On the irredundant generation of knowledge spaces. J. Math. Pych., 37 (1): 4962,1993.

43. Duquenne V. Towards an intentional logic of symptoms. Current Psychology of Cognition, 15 (3): 323-345,1996.

44. Ferré S. Incremental Concept Formation Made More Efficient by die Use of Associative Concepts, INRIA Research Report no 4569, 2002.

45. Finn V.K., Grigolia, R. Nonsense logics and their algebraic properties. Theoria, LIX (Parts 1—3): 207-273,1993.

46. Fitting M.C. Many-valued modal logics, I—II. Fundamenta Informaticae, 15: 235—254,1991; 17: 55-73,1992.

47. Ganter B. Two Basic Algorithms in Concept Analysis, FB4-Preprint No. 831, TH Darmstadt, 1984.

48. Ganter B., Reuter K. Finding all closed sets: A general approach. Order, 8: 283-290, 1991.

49. Ganter B., Bittner, P.A. Conceptual Browsing Tool Using Lattices, unpublished manuscript,1998.

50. Ganter B., Wille R. Formal Concept Analysis:

51. Mathematical Foundations. Heidelberg: Springer,1999.

52. Ganter B., Kuznetsov S. Formalizing hypotheses with concepts. Proceedings, 8th International Conference on Conceptual Structures, ICCS 2000, Pecture Notes in Artificial Intelligence, 1867, Darmstadt, Germany, pp. 342-356, 2000.

53. Godin R., Missaoui R., Alaoui H. Incremental concept formation algorithms based on Galois lattices. Computation Intelligence, 11 (2): 246-267,1995.

54. Goldberg L.A. Efficient Algorithmsfor Listing

55. Combinatorial Structures. Cambridge: Cambridge1. University Press, 1993.j 7

56. Grigoriev P., Kuznetsov S., Obiedkov S., Yevtushenko S. On a version of Mill'smethod of difference. Proceedings, ECAP 2002 International Workshop on Advances in Formal Concept Analysis for Knowledge Discovery in Databases, Lyon, France, pp. 26—31, 2002.

57. Guénoche A. Construction du treillis de Galois d'une relation binaire. Math. Inf Sei. Hum., 109: 41-53,1990.

58. Guigues J.-L., Duquenne V. Familles minimales d'implications informatives résultant d'un tableau de données binaires, Preprint of the groupe mathématique et psychologie, Univ. R. Descartes, Paris, 1983.

59. Guigues J.-L., Duquenne V. Familles minimales d'implications informatives résultant d'un tableau de données binaires. Math. Sei. Humaines, 95: 5-18,1986.

60. Holzer R. Methoden der formalen Begriffsanalyse bei der Behandlung unvollständigen Wissens. Dissertation, Shaker-Verlag, 2001.

61. Hughes G.E., Cresswell M.J. A New Introduction to Modal Logic. Roudedge, 1996.

62. Johnson D.S., Yannakakis M., Papadimitriou C.H. On generating all maximal independent sets. InfProc. Ut., IT. 119-123,1988.

63. Kuznetsov S., Obiedkov S. Algorithms for the Construction of the Set of All Concepts and Their line Diagram, Preprint MATH-A1-05, TU-Dresden, 2000.

64. Kuznetsov S.O. On computing the size of alattice and related decision problems. Order, 18 (4): 13-21,2001.

65. Kuznetsov S., Obiedkov S. Comparingperformance of algorithms for generating concept lattices. Journal of Experimental and

66. Mannila H., Ràilià K.J. The Design of Relational Databases, Addison Wesley, 1992.

67. Mephu Nguifo E., Njiwoua P. Using lattice-based framework as a tool for feature extraction. In H. Liu and H. Motoda (eds) Construction and Selection: A DataMiningPerspective. Boston MA: Kluwer, pp. 205-216,1998.

68. Mill J.S. A System of Logic, Ratio cinative and Inductive: Being a Connected View of the Principles of Evidence, and Methods of Scientific Integration, London: J.W. Parker, 1843.

69. Mitchell T. Version Space: An Approach to Concept Learning, PhD Thesis, Stanford University, 1978.

70. Mitchell T. Generalization as search. Artificial Intelligence, 18(2), 1982.

71. Mohr J., Duquenne V. The duality of culture and practice: Poverty relief in New-York City, 1888-1917 Theory and Society, 26: 305-356, 1997.

72. Norris E.M. An algorithm for computing the maximal rectangles in a binary relation. Revue Roumaine de Mathématiques Pitres et Appliquées, 23 (2): 243-250,1978.

73. Nourine L., Raynaud O. A fast algorithm for building lattices. Information Processing Tetters, 71: 199-204,1999.

74. Obiedkov S. Modal logic for evaluating formulas in incomplete contexts. Proceedings, 10"' International Conference on Conceptual Structures, ICCS 2002, Lecture Notes in Artificial Intelligence, 2393, Borovets, Bulgaria, pp. 314-325, 2002.

75. Pasquier N., Bastide Y., Taouil R., Lakhal L.

76. Closed set based discover^7 of small covers for association rules, In Proceedings, BDA Conference, pp. 361-381,1999a.

77. Pasquier N., Bastide Y., Taouil R., Lakhal L. Discovering frequent closed itemsets for association rules. Proceedings, 7"' Int. Confi

78. Database Theoy ßCDT'99), Jerusalem, Israel, pp. 398-416,1999b.

79. Pasquier N., Bastide Y., Taouil R., Lakhal L. Efficient mining of association rules using closed itemset lattices. Information Systems, 24 (1): 25^16,1999c.

80. PeiJ, Han J., Mao R. CLOSET: an efficientalgorithm for mining frequent closed itemsets. Proceedings, 4th International Conference on Knowledge Discovery and Data Mining, pp. 21-30, 2000.

81. Stumme G., Wille R., Wille U. Conceptual knowledge discover}7 in databases using formal concept analysis methods. Proceedings, Z'1 European Symposium on Principles of Data Mining and Knowledge Discovery (PKDD '98), Nantes, France, pp. 450^458,1998.

82. Stumme G., Taouil R., Bastide Y., Pasquier N., Lakhal L. Fast computation of concept lattices using data mining techniques. Proceedings, 7'h Int. Workshop on Knowledge Representation Meets Databases (KRDB 2000), Berlin, Germany, pp. 129-139, 2000.

83. Taouil R., Bastide Y. Computing proper implications. Proceedings, ICCS-2001 International Workshop on Concept Eattices-Based Theory, Methods and Tools for Knowledge Discovery in Databases (CEKDD'01), Stanford CA, USA, pp. 49-61,2001.

84. Valtchev P., Missaoui R., Lebrun P. A Partition-Based Approach towards Building Galois (Concept) Lattices, Rapport de recherche no. 2000-08, Département d'Informatique, UQAM, Montreal, Canada, 2000.

85. Valtchev P., Missaoui R. Building concept

86. Galois) lattices from parts: Generalizing the incremental methods. Proceedings, 9h International Conference on Conceptual Structures, ICCS 2001, Eecture Notes in Artificial Intelligence, 2120, Stanford CA, USA, pp. 290-303, 2001.

87. Van Der Merwe F.J., Kourie D.G. AddAtom: an incremental algorithm for constructingconcept lattices and concept sublattices, Technical report, Department of Computer Science, University of Pretoria, 2002.

88. Wild M. Computations with Finite Closure

89. Systems and Implications, Preprint No. 1708, TH Darmstadt, 1994.

90. Wille R. Restructuring lattice theory: an approach based on hierarchies of concepts. In I. Rival (ed) Ordered Sets, Dordrecht-Boston: Reidel, pp. 445-470,1982.

91. Yevtushenko S. BDD-based algorithms for the construction of the set of all concepts.

92. Contributions to ICCS 2002, Borovets, Bulgaria, pp. 61-73, 2002.

93. Zaki. M.J., Ogihara M. Theoretical foundations of association rules. Proceedings, 3'J SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discoveiy, 1998.

94. Zaki M.J., Hsiao C. Charm: an efficient algorithm for closed association rule mining, Technical report 99-10, Computer Science, Rensselaer Polytechnic Institute, 1999.1. POCClht'JHAU1. ГОСУ ЦШГ.'ШИЛГлбйблйохй^ ,