Модели, методы и комплексы программ построения зависимостей, основанные на решетках замкнутых множеств тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Бабин, Михаил Александрович

• Бабин, Михаил Александрович
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Бабин, Михаил Александрович

Введение

1 Построение зависимостей в данных с помощью решеток замкнутых множеств: основные понятия и состояние предметной области

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

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

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

1.1.3 Теория алгоритмов и вычислительная сложность

1.2 Модели зависимостей и их вычисление

1.3 Минимальная модель знаний о предметной области: минимальный базис импликаций.

1.4 Задачи и алгоритмы построения гипотез

2 Базисы импликаций и функциональных зависимостей

2.1 Квазизамкнутые множества и псевдосодержания.

2.2 Структура минимальных базисов импликаций.

2.3 Функциональные зависимости и импликации.

2.4 Распознавание псевдосодержапий.

2.5 Лектически максимальные псевдосодержания и перечисление максимальных псевдосодсржаний.

2.6 Распознавание существенных содержаний.

2.6.1 Посылка импликации из минимального базиса

2.7 Базис импликаций с двухэлементными посылками.

2.8 Приближенный базис импликаций.

2.8.1 Результаты экспериментов.

3 Базисы импликаций и общие содержания

3.1 Связь базиса импликаций с общими содержаниями

3.2 Общий метод поиска минимального базиса импликаций через общие содержания.

3.2.1 Поиск собственных посылок через общие содержания

3.3 Интенсионально связанные понятия.

3.4 Понятия с общими содержаниями.

3.5 Сцепления и общие содержания

4 Обучение гипотезам

4.1 Теоретико-решеточная интерпретация гипотез и классификации

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

4.3 Распределенное обучение гипотезам.

4.4 Устойчивость понятий и гипотез.

4.5 Приближенный подсчет числа замкнутых и незамкнутых множеств.

4.6 Индекс вероятностной устойчивости.

4.7 Анализ результатов вычислений индекса вероятностной устойчивости

4.8 Устойчивые гипотезы: Результаты экспериментов с данными по токсичности химических соединений.

5 Комплекс программ

5.1 Программный комплекс Cordiet

5.2 Программная реализация построения базисов импликаций

5.3 Программная реализация алгоритма вычисления оператора замыкания общих содержаний

5.4 Программная реализация распределенного обучения гипотезам

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

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

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

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

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

• Эффективные алгоритмы порождения приближенных базисов импликаций, множества минимальных ДСМ-гипотез

• Эффективные алгоритмы распознавания псевдосодержаний, задающих оптимальный базис импликаций

• Модели оценивания импликативных зависимостей и эффективное вычисление оценок этих зависимостей

Так например, сложность распознавания псевдосодержаний, задающих оптимальный базис зависимостей (импликаций) была одной из основных открытых задач АФГ1 на протяжении многих лет (список открытых задач АФГТ [89] задачи 2,8,9).

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

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

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

Научная новизна. В диссертации получены следующие основные новые научные результаты, которые выносятся на защиту:

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

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

3. Доказана трудноразрешимость вычисления минимальных гипотез в стандартной постановке

4. Предложена и эксперимен тально проверена модель распределенного обучения гипотезам - импликативным зависимостям для задачи машинного обучения.

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

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

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

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

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

10. Разработан комплекс программ, реализующий предложенные алгоритмы, который был встроен в коллективно разрабатываемый в Отделении прикладной математики и информатики НИУ ВШЭ комплекс программ.

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

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

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

Апробация результатов работы. Основные результаты работы докладывались и обсуждались на следующих научных конференциях:

1. 8-ой международной конференции по анализу формальных понятий (8th International Conference on Formal Concept Analysis), Агадир, Марокко, 2010.

2. 7-ой международной конференции по решеткам понятий и их приложениям (7th International ConfereGnce on Concept Lattices and Their

Applications), Севилья, Испания, 2010. [Награда за лучшую статью]

3. 9-ой международной конференции но анализу формальных понятий (9th International Conference on Formal Concept Analysis), Никосия, Кипр, 2011.

4. 10-ой международной конференции по анализу формальных понятий (8th International Conference on Formal Concept Analysis), Лёвен, Бельгия, 2012.

Публикации. Основные результаты работы изложены в б научных статьях из которых 4 опубликованы в рецензируемых трудах международных конференций (индексируемыми системами Web of Science и Scopus) и 2 опубликованы в журналах из списка ВАК. Также 1 статья принята к публикации в международный рецензируемый журнал.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Бабин, Михаил Александрович

Основные результаты и выводы работы:

1. Результаты, связанные с базисами импликаций:

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

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

2. Результаты, связанные с минимальными гипотезами:

2.1 Доказана трудноразрешимость вычисления минимальных гипотез в стандартной постановке.

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

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

3. Результаты, связанные с индексом устойчивости формальных понятий и гипотез:

3.1 Предложена и экспериментально проверена модель оценивания гипотез и формальных понятий - индекс вероятностной устойчивости.

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

Заключение

В диссертационной работе приведен обзор методов поиска строгих зависимостей в данных. В 2006 году участниками конференции ICFCA в Ленсе (Lens, Франция) был составлен список наиболее важных открытых задач в АФП. Одной из них была задача о сложности распознавания псевдосодержаний, которая была решена в данной диссертационной работе и опубликована в [31] (публикации, где рассматривалась данная задача и считалась открытой: [74, 89, 90, 91, 92, 38]). Эта задача была также представлена как открытая на Дрезденской конференции по дискретной математике в 2002 году.

В отличие от классического минимального базиса импликаций, для которого все известные алгоритмы построения имеют экспоненциальную оценку сложности, среднее время работы построения приближенного базиса импликаций полиномиально и оценивается как 0(\J\\М\ ■ (|С||М| + |J7"||M|) • £-1), где J ~ минимальный базис импликаций, а е - параметр точности приближенного базиса импликаций. Проведенные на реальных данных эксперименты показали, что размер приближенного базиса был значительно меньше (иногда в сотни раз).

В работе было доказано, что если Р ф NP, то невозможно найти все минимальные ДСМ-гипотезы за полиномиальное от размера выхода время. Модель распределенного обучения гипотезам показала значительное сокращение количества гипотез по отношению к числу ДСМ-гипотез в стандартной постановке. Линейный по времени алгоритм вычисления оператора замыканий системы замыканий общих содержаний позволил быстро перечислять все общие гипотезы.

В данной работе была доказана трудность аппроксимации индекса классической устойчивости формальных понятий (с полиномиально ограниченной относительной ошибкой). Была предложена модель вероятностного индекса устойчивости формальных понятий, которая соответствует аппроксимации классического индекса устойчивости с ограниченной абсолютной ошибкой и может быть вычислена за полиномиальное время. Проведенные эксперименты показали, что применение вероятностного индекса устойчивости, при использовании ДСМ-метода, уменьшает число некласси-фицируемых объектов па ~ 43% при увеличении количества ошибок классификации на « 23% (число неклассифицируемых объектов, при использовании стандартных ДСМ-гипотез ^ 46%).

Список литературы диссертационного исследования кандидат физико-математических наук Бабин, Михаил Александрович, 2012 год

1. Бабин М.А. О приближенном базисе импликаций // Научно-техническая информация. Серия: Информационные процессы и системы, №8, С. 20-23, 2012.

2. Бабин М.А., Кузнецов С.О. О теоретико-решеточной интерпретации задач поиска гипотез и зависимостей // Научно-техническая информация. Серия: Информационные процессы и системы, №10, С. 18-22, 2011.

3. Бабин М.А., Кузнецов С.О. Связи между решетками понятий и сложность их вычисления // Труды МФТИ, том 4 №2(14), С. 73-80, 2012.

4. Биркгоф Г. Теория решеток // М.: Наука, 1984.

5. Банник В.Н., Червоненкис А.Я. Теория распознавания образов // М., Наука, С.418, 1974.

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

7. Гретцер Г. Общая теория решеток // М.: Мир, 1982.

8. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи // М.: Мир, 1982.

9. Кузнецов С.О. Интерпретация на графах и сложностные характеристики задач поиска закономерностей определенного вида // НТИ, Сер.2, Ш., С.23 28, 1989.

10. Кузнецов С.О. Устойчивость как оценка обоснованности гипотез, получаемых на основе операционального сходства // НТИ, Сер.2, №12, С.21-29, 1990.

11. Кузнецов С.О. Введение в ДСМ-метод // Семиотика и информатика, Вып. 31, С.5-40, 1991.

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

13. Кузнецов С.О. Сложность алгоритмов обучения и классификации, основанных на поиске пересечения множеств // НТИ, Сер.2, №9, С.8-15, 1991.

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

15. Кузнецов С.О. Алгоритмическая сложность порождения гипотез и классификаций, основанных на поиске пересечения множеств // Доклады АН.-335, №3, С.300-303, 1994.

16. Кузнецов С.О., Финн В.К. О модели обучения и классификации, основанной на операции сходства // Обозрение Прикладной и Промышленной Математики, 3, №1, С.66-90, 1996.

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

18. Кузнецов С.О. Автоматическое обучение на основе анализа формальных понятий // Автоматика и телемеханика, №10, С.3-27, 2001.

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

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

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

22. Финн В.К. Об обобщенном ДСМ-методе автоматического порождения гипотез // Семиотика и информатика, Вып.29, С.93-123, 1989.

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

24. Финн В.К., Михеенкова М.А. О ситуационном расширении ДСМ-мстода автоматического порождения гипотез // НТИ, Сер.2, №11, С.20-30, 2000.

25. Anshakov О.М., Firm V.K., Skvortsov D.P. On axiomatization of many-valued logics associated with the formalization of plausible reasonings // Stud. Log., vol. 25, No. 4, p.23-47, 1989.

26. Agrawal R., Imielinski T., Swami A. N. Mining Association Rules between Sets of Items in Large Databases // SIGMOD Conference, p.207-216, 1993.

27. Agrawal R., Srikant R. Fast Algorithms for Mining Association Rules in Large Databases // Journal of Computer Science and Technology, vol. 15, Issue 6, p.487-499, 1994.

28. Angluin D., Frazier M., Pitt L. Learning Conjunctions of Horn Clauses // Machine Learning, vol. 9, p. 147-164, 1992.

29. Armstrong W.W. Dependency structure of data base relationships // Proc. IFIP Congress, Geneva, p.580-583, 1974.

30. Babin M.A., Kuznetsov S.O. On Links between Concept Lattices and Related Complexity Problems // Proc. 8th Int. Conf. on Formal Concept Analysis (ICFCA'10), Lecture Notes in Artificial Intelligence, Springer, vol. 5986, p.138-144, 2010.

31. Babin M.A., Kuznetsov S.O. Recognizing Pseudo-intents is coNP-complete // Proc. CLA 2010, p.294-301, 2010.

32. Babin M.A., Kuznetsov S.O. Enumerating Minimal Hypotheses and Dualizing Monotone Boolean Functions on Lattices // Proc. 9th Int. Conf. on Formal Concept Analysis (ICFCA'll), Lecture Notes in Artificial Intelligence, Springer, vol. 6628, p.42-48, 2011.

33. Babin M.A., Kuznetsov S.O. Approximating Concept Stability // Proc. 10th Int. Conf. on Formal Concept Analysis (ICFCA'12), Lecture Notes in Artificial Intelligence, Springer, vol. 7278, p.7-15, 2012.

34. Babiri M.A., Kuznetsov S.O. Computing Premises of a Minimal Cover of Functional Dependencies is Intractable // Discrete Applied Mathematics, принята к публикации, 2012.

35. Bastide Y., Lakhal L., Pasquier N., Taouil R. Efficient Mining of Association Rules Based on Using Closed Itemset Lattices // J. Inf. Systems, vol. 24, p.25-46, 1999.

36. Bishop C.M. Pattern Recognition and Machine Learning // Information Science and Statistics, Springer, 2006.

37. Borchmann D., Distel F., Ryssel U. Fast Computation of Proper Premises // Proc. International Conference on Concept Lattices and Their Applications(CLA'2011), Nancy (France), 2011.

38. Distel F. Hardness of enumerating pseudo-intents in the lectic order // Proc. ICFCA 2010, Lecture Notes in Artificial Intelligence, vol. 5986, p. 124-137, Springer, 2010.

39. Distel F., Sertkaya В. On the complexity of enumerating pseudo-intents // Discrete Applied Mathematics, vol. 159, no.6, p.450-466, 2011.

40. Dyer M., Goldberg L.A., Greenhill C., Jerrum C. On the relative complexity of approximate counting problems, Proc. APPROX 2000, p.108-119, 2000.

41. Duquenne V., Guigues J. L. Families minimales d'implications informatives resultant d'un tableau de données binaries / / Mathématiques, Informatique et Sciences Humaines, 95, p.5-18, 1986.

42. Duquenne V., Obicdkov S.A. Attribute-incremental construction of the canonical implication basis // Annals of Mathematics and Artificial Intelligence, 49(l-4):7799, 2007.

43. Egho E., Jay N., Raissi C., Napoli A. A FCA-based Analysis of Sequential Care Trajectories // Proc. 8th of the International Conference on Concept Lattices and Their Applications (CLA'2011), Nancy (France), p.362-376, 2011.

44. Eiter T., Ibaraki T., Makino K. Computing Intersections of Horn Theories for Reasoning with Models // Proc. National Conference on Artificial Intelligence (AAAI'98), Madison, Wisconsin, July 26-30, p.292-297, 1998.

45. Falk I., Gardent C. Combining Formal Concept Analysis and Translation to Assign Frames and Thematic Role Sets to French Verbs // Proc. International Conference Concept Lattices and Their Applications (CLA'2011), Nancy (France), 2011.

46. Falk I., Gardent C. Bootstrapping a Classification of French Verbs Using Formal Concept Analysis // Proc. Interdisciplinary Workshop on Verbs, Pisa (Italy), 2011.

47. Falk I., Gardent C., Lorenzo A. Using Formal Concept Analysis to Acquire Knowledge about Verbs // Proc. 7th of the International Conference on Concept Lattices and Their Applications (CLA'2010), p. 151-162, 2010.

48. Feldman R., Sanger J. The text mining handbook: advanced approaches in analyzing unstructured data // Cambridge University Press, 2007.

49. Fredman M.L., Khachiyan L. On the complexity of dualization of monotone disjunctive normal forms // Journal of Algorithms, vol. 21, p.618-628, 1996.

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

51. Ganter B. Lattices of Rough Set Abstractions as P-Products // Proc. ICFCA 2008, Lecture Notes in Computer Science, vol. 4933, p. 199-216, 2008.

52. Ganter B., Kuznetsov S. Formalizing Hypotheses with Concepts, Proc. 8th Int. Conf. on Conceptual Structures, ICCS'00, Lecture Notes in Artificial Intelligence, vol. 1867, p.342-356, 2000.

53. Ganter B., Kuznetsov S.O. Hypotheses and Version Spaces // Proc. 10th Int. Conf. on Conceptual Structures, ICCS'03, Lecture Notes in Artificial Intelligence, vol. 2746, p.83-95, 2003.

54. Ganter B., Wille R. Formal Concept Analysis: Mathematical Foundations // Springer, Berlin, 1999.

55. Garcy M.R., Johnson D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness // W. H. Freeman, 1979.

56. Gold E.M. Language identification in the limit // Information and Control, vol. 10, p.447-474, 1967.

57. Jay N., Kohler F., Napoli A. Analysis of Social Communities with Iceberg and Stability-Based Concept Lattices // Proc. 6th International Conference on Formal Concept Analysis (ICFCA'2008), p.258-272, 2008.

58. Jerrum M. R., Valiant L.G., Vazirani V.V. Random generation of combinatorial structures from a uniform distribution // Theoretical Computer Science, vol. 43, no. 2-3, p. 169-188, 1986.

59. Jiawei H., Jian P., Yiwen Y., Runying M. Mining frequent patterns without candidate generation // Data Mining and Knowledge Discovery, vol. 8, p.53-87, 2004.

60. Johnson D.S., Papadimitriou C.H., Yannakakis M. On Generating All Maximal Independent Sets // Informaion Processing Letters, vol. 27, no. 3, p.119-123, 1988.

61. Kavvadias D. J., Sideri M., Stavropoulos E. C. Generating All Maximal Models of a Boolean Expression, 1999.

62. Kavvadias D.J., Stavropoulos E.C. An Efficient Algorithm for the Transversal Hypergraph Generation //J. Graph Algorithms Appl., vol. 9(2), p.239-264, 2005.

63. Khardon R. Translating between Horn Representations and their Characteristic Models //J. Artificial Intelligence, vol. 3, p.349-372, 1995.

64. Kivinen J., Mannila H. Approximate Inference of Functional Dependenciesfrom Relations // Theoretical Computer Science, vol. 149, no. 1, p. 129149, 1995.

65. Klimushkin M., Obiedkov S.A., Roth C. Approaches to the Selection of Relevant Concepts in the Case of Noisy Data // Proc. 8th International Conference on Formal Concept Analysis (ICFCA'2010), p.255-266, 2010.

66. Kourie D.G., Obiedkov S.A., Roth C. Towards Concise Representation for Taxonomies of Epistemic Communities // Proc. International Conference Concept Lattices and Their Applications (CLA'2006), Tunis (Tunisia), p.240-255, 2006.

67. Kuznetsov S.O. Stability as an estimate of the degree of substantiation of hypotheses derived on the basis of operational similarity // Nauchn. Tekh. Inf., ser 2., №12, p.21-29, 1990.

68. Kuznetsov S.O. On Computing the Size of a Lattice and Related Decision Problems // Order, 18(4), p.313-321, 2001.

69. Kuznetsov S.O. Machine Learning on the Basis of Formal Concept Analysis // Automation and Remote Control, vol. 62, no. 10, 2001.

70. Kuznetsov S.O., Obiedkov S.A. Comparing performance of algorithms for generating concept lattices //J. Exp. Theor. Artif. Intell., 14, 2-3, p.189-216, 2002.

71. Kuznetsov S.O. Stability of a Formal Concept // Proc. 4th Journee d'Informatique Messine (JIM'03), Metz, 2003.

72. Kuznetsov S.O. On the intractability of computing Duquenne-Guigues base //J. Universal Computer Sciencc, vol. 10, no. 8, p.927-933, 2004.

73. Kuznetsov S.O. Complexity of Learning in Concept Lattices from Positive and Negative Examples // Discrete Applied Mathematics, 110. 142, p. 111125, 2004.

74. Kuznetsov S.O. On Stability of a Formal Concept // Annals of Mathematics and Artificial Intelligence, vol. 49, p. 101-115, 2007.

75. Kuznetsov S.O., Obiedkov S.A. Counting pseudo-intents and #P-completeness // Proc. ICFCA 2006, Lecture Notes in Computer Science, vol. 3874, p.306—308, Springer, 2006.

76. Kuznetsov S.O., Obiedkov S.A. Some decision and counting problems of the Duquenne-Guigues basis of implications // Discrete Applied Mathematics, 156(11), p. 1994-2003, 2008.

77. Krôtzsch M. and Malik G. The Tensor Product as a Lattice of Regular Galois Connections // Proc. 4th Inernational Conference on Formal Concept Analysis (ICFCA'2006), Lecture Notes in Artificial Intelligence (LNAI), vol. 3874, p.89-104, Springer 2006.

78. Loshin D. Master Data Management // Morgan Kaufmann Publishers, 2009.

79. Mannila H., Râihâ K. The design of relational databases // Addison Wesley, 1992.

80. Mohammed Z.J. Scalable algorithms for association mining // IEEE Transactions on Knowledge and Data Engineering, vol. 12(3), p.372-390, 2000.

81. Motwani R., Raghavan P. Randomized Algorithms // Cambridge University Press, 1995.

82. Nienhuys-Cheng S.-H., Wolf R. Foundations of Inductive Logic Programming, // Lecture Notes in Artificial Intelligence, vol. 1228, 1997.

83. Obiedkov S.A., Roth C., Kourie D.G. On Succinct Representation of Knowledge Community Taxonomies with Formal Concept, Analysis // Int. J. Found. Comput. Sci., 19(2), p.383-404, 2008.

84. Obiedkov S.A., Roth C., Kourie D.G. Towards Concise Representation for Taxonomies of Epistemic Communities // Proc. 4th International Conference Concept Lattices and Their Applications (CLA'2006), p.240-255, 2008.

85. Piatetsky-Shapiro G. Discovery, Analysis, and Presentation of Strong Rules // Knowledge Discovery in Databases, p.229-248, 1991.

86. Poelmans J., Elzinga P., Neznanov A., Dedene G., Viaene S., Kuznetsov S.O. Human-Centered Text Mining: A New Software System // ICDM 2012, p.258-272, 2012.

87. Priss U. Some open problems in Formal Concept Analysis // Proc. ICFCA 2006, 2006.

88. Rudolph S. Some notes on pseudo-closed sets // Proc. ICFCA 2007, Lecture Notes in Computer Science, vol. 4390, p.151-165, Springer, 2007.

89. Sertkaya B. Towards the complexity of recognizing pseudo-intents // Proc. ICCS 2009, Lecture Notes in Computer Science, vol. 5662, p.284-292, Springer, 2009.

90. Sertkaya B. Some computational problems related to pseudo-intents // Proc. ICFCA 2009, Lecture Notes in Computer Science, vol. 5662, p.284-292, Springer, 2009.

91. Singh K., Singh R. A Descriptive Classification of Causes of Data Quality Problems in Data Warehousing // International Journal of Computer Science Issue, vol. 7, Issue 3, No. 2, 2010.

92. Solomonoff R.J. A formal theory of inductive inference // Information and Control, vol. 7, p. 224-254, 1964.

93. Valiant L.G. The complexity of computing the permanent // Theoretical Computer Science, 8, No. 2, p. 189-201, 1979.

94. Valiant L.G. The Complexity of Enumeration and Reliability Problems // SIAM J. Comput., 8, no. 3, p.410-421, 1979.

95. Valiant L.G. A theory of the learnable // Coinmun. ACM, 27, no. 11, p.1134-1142, 1984.

96. Wille R. Restructuring Lattice Theory: an Approach Based on Hierarchies of Concepts // Ordered Sets, Reidel, p.445-470, Dordrecht-Boston, 1982.

97. Wille R. Conceptual Structure of Multicontexts // Proc. 4th International Conference on Conceptual Structures, Lecture Notes in Artificial Intelligence (LNAI), vol. 1115, p.23-39, Springer, 1996.

98. Сайт репозитория машинного обучения UCI http://archive.ics.uci.edu/ml/