Исследуется #Р-полная задача нахождения всех формальных понятий заданного контекста и предлагается декомпозиционный метод её решения. В качестве частей разложения предлагается использовать фрагменты исходного контекста, названные боксами. Доказано, что разделение контекста на боксы «безопасно» относительно формальных понятий: при декомпозиции ни одно формальное понятие не теряется и не появляются новые формальные понятия. Доказано, что число боксов, возникающих на каждой итерации разложения, равно числу единичных элементов 0,1-матрицы, представляющей исходный формальный контекст. Предлагается уменьшать число боксов на каждой отдельной итерации процесса декомпозиции с помощью построения взаимно непересекающихся цепей боксов. Приводятся результаты вычислительных экспериментов, свидетельствующие о существенном повышении производительности алгоритмов нахождения всех формальных понятий при применении предлагаемого декомпозиционного метода.
Скачать электронную версию публикации
Загружен, раз: 117
- Title Декомпозиционный подход к исследованию формальных контекстов
- Headline Декомпозиционный подход к исследованию формальных контекстов
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 44
- Date:
- DOI 10.17223/20710410/44/9
Ключевые слова
анализ формальных понятий, декомпозиция формального контекста, formal concept analysis, formal context decompositionАвторы
Ссылки
Биркгоф Г. Теория решеток. М.: Наука, 1984. 568 с
Ganter B. and Wille R. Formal Concept Analyses: Mathematical Foundations. Springer Science and Business Media, 2012. 314 p
Ganter B. and Obiedkov S. A. Conceptual Exploration. Berlin, Heidelberg: Springer, 2016. 315 p
Kuznetsov S. O. and Obiedkov S. A. Comparing Performance of Algorithms for Generating Concept Lattices // J. Experimental and Theoretical Artificial Intelligence. 2002. V. 14. No. 2. P. 189-216
Simon A. A. Best-of-Breed approach for designing a fast algorithm for computing fixpoints of Galois Connections // Inform. Sci. 2015. V. 295. No. 2. P. 633-649
Aslanyan L., Alipour D., and Heidari M. Comparative analysis of attack graphs // Mathem. Problems of Computer Sci. 2013. No. 40. P. 85-95
Heydari M., Morales L., Shields C. О., and Sudborough I. H. Computing Cross Associations for Attack Graphs and other Applications // Proc. 40th Ann. Hawaii Intern. Conf. on System Sciences. Big Island, Hawaii, 2007. P. 270
Li J., Liu G., Li H., and Wong L. Maximal biclique subgraphs and closed pattern pairs of the adjacency matrix: A one-to-one correspondence and mining algorithms // J. IEEE Trans. Knowledge and Data Engineering. 2007. No. 19. P. 1625-1637
Bein D., Morales L., Bein W., et al. Clustering and the biclique partition problem // Proc. 41st Ann. Hawaii Intern. Conf. on System Sciences. Big Island, Hawaii, 2008. P. 475-483
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. M.: Мир, 1982. 416 с
Дугинов О. И. Сложность задач покрытия графа наименьшим числом полных двудольных графов // Труды Института математики. 2014. Т. 22. Вып. 1. С. 51-69
Prisner E. Bicliques in graphs I: bounds on their number // Combinatorica. 2000. V. 20. P. 109-117
Wood D. R. On the maximum number of cliques in a graph // Graphs and Combinatorics. 2007. No. 23. P. 1-16
Moon J. W. and Moser L. On cliques in graphs // J. Mathematics. 1965. No. 3. P. 23-28
Pottosina S., Pottosin Y., and S edliak B. Finding maximal complete bipartite subgraphs in a graph // J. Appl. Math. 2008. V. 1. No. 1. P. 75-81
Vania M. F. Dias, Celina M. H. de Figueiredo, and Jayme L. S. Generating bicliques of a graph in lexicographic order // Theor. Comput. Sci. 2005. No. 337. P. 240-248
Дюкова Е. В., Журавлев Ю. И. Дискретный анализ признаковых описаний в задачах распознавания большой размерности // Журн. вычислит. матем. и матем. физики. 2000. Т. 40. № 8. C.1264-1278
Дюкова Е. В., Инякин А. С. О процедурах классификации, основанных на построении покрытий классов // Журн. вычислит. матем. и матем. физики. 2003. Т. 43. №12. С.1884-1895
Быкова В. В. Математические методы анализа рекурсивных алгоритмов // Журн. Сибирского федерального университета. Математика и физика. 2008. Т. 3. №1. С. 372-384
Harzheim E. Ordered Sets. New York: Springer, 2005. 390 p
Монгуш Ч. М., Быкова В. В. Программа FCACorpus концептуального моделирования тувинских текстов методами анализа формальных понятий. Свидетельство о государственной регистрации программы для ЭВМ № 2018618907, выдано Федеральной службой по интеллектуальной собственности РФ, 2018
Декомпозиционный подход к исследованию формальных контекстов | Прикладная дискретная математика. 2019. № 44. DOI: 10.17223/20710410/44/9
Скачать полнотекстовую версию
Загружен, раз: 364