On Algebraic Approach of R. Wille and B. Ganter in the Investigation of Texts
View/ Open:
URI (for links/citations):
https://elib.sfu-kras.ru/handle/2311/33617Author:
Bykova, Valentina V.
Mongush, Choduraa M.
Быкова, Валентина В.
Монгуш, Чодураа М.
Date:
2017-09Journal Name:
Журнал Сибирского федерального университета. Математика и физика. Journal of Siberian Federal University. Mathematics & Physics;2017 10 (3)Abstract:
The statement of the problem of a binary classification by precedents using formal concept lattices is
given, in which the initial data are two binary contexts. It is specified that this problem is intractable
due to the high computational complexity of discovery process of the formal concept and constructing for
them of the lattices. The decomposition reception, which allows reducing the computational complexity of
this process is proposed and theoretically justified. The reduction of computational complexity is achieved
by separation of every initial context on polynomial number of boxes (subcontexts), followed by a search
of the formal concepts in each selected box. The results of computational experiments are presented and
they confirm the effectiveness of the proposed of reception of the reducing computational complexity Приведена постановка задачи бинарной классификации по прецедентам с использованием реше-
ток формальных понятий, в которой исходными данными выступают два бинарных контекста.
Отмечено, что данная задача труднорешаема за счет высокой вычислительной сложности про-
цесса выявления формальных понятий и построения для них решеток. Предложен и теорети-
чески обоснован декомпозиционный прием, позволяющий снизить вычислительную сложность
этого процесса. Снижение вычислительной сложности достигается за счет разделения всякого
исходного контекста на полиномиальное число боксов (подконтекстов) с последующим поиском
формальных понятий в каждом выделенном боксе. Представлены результаты вычислительных
экспериментов, подтверждающие эффективность предложенного приема снижения сложности
вычислений