D. Dürrschnabel, and G. Stumme. (2023)cite arxiv:2304.03338Comment: 14 pages, 6 figures, 2 algorithms.
Abstract
Given a formal context, an ordinal factor is a subset of its incidence
relation that forms a chain in the concept lattice, i.e., a part of the dataset
that corresponds to a linear order. To visualize the data in a formal context,
Ganter and Glodeanu proposed a biplot based on two ordinal factors. For the
biplot to be useful, it is important that these factors comprise as much data
points as possible, i.e., that they cover a large part of the incidence
relation. In this work, we investigate such ordinal two-factorizations. First,
we investigate for formal contexts that omit ordinal two-factorizations the
disjointness of the two factors. Then, we show that deciding on the existence
of two-factorizations of a given size is an NP-complete problem which makes
computing maximal factorizations computationally expensive. Finally, we provide
the algorithm Ord2Factor that allows us to compute large ordinal
two-factorizations.
%0 Generic
%1 durrschnabel2023maximal
%A Dürrschnabel, Dominik
%A Stumme, Gerd
%D 2023
%K 2023 itegpub myown np_complete ordinal_factor_analysis two_dimension_extension
%T Maximal Ordinal Two-Factorizations
%U http://arxiv.org/abs/2304.03338
%X Given a formal context, an ordinal factor is a subset of its incidence
relation that forms a chain in the concept lattice, i.e., a part of the dataset
that corresponds to a linear order. To visualize the data in a formal context,
Ganter and Glodeanu proposed a biplot based on two ordinal factors. For the
biplot to be useful, it is important that these factors comprise as much data
points as possible, i.e., that they cover a large part of the incidence
relation. In this work, we investigate such ordinal two-factorizations. First,
we investigate for formal contexts that omit ordinal two-factorizations the
disjointness of the two factors. Then, we show that deciding on the existence
of two-factorizations of a given size is an NP-complete problem which makes
computing maximal factorizations computationally expensive. Finally, we provide
the algorithm Ord2Factor that allows us to compute large ordinal
two-factorizations.
@misc{durrschnabel2023maximal,
abstract = {Given a formal context, an ordinal factor is a subset of its incidence
relation that forms a chain in the concept lattice, i.e., a part of the dataset
that corresponds to a linear order. To visualize the data in a formal context,
Ganter and Glodeanu proposed a biplot based on two ordinal factors. For the
biplot to be useful, it is important that these factors comprise as much data
points as possible, i.e., that they cover a large part of the incidence
relation. In this work, we investigate such ordinal two-factorizations. First,
we investigate for formal contexts that omit ordinal two-factorizations the
disjointness of the two factors. Then, we show that deciding on the existence
of two-factorizations of a given size is an NP-complete problem which makes
computing maximal factorizations computationally expensive. Finally, we provide
the algorithm Ord2Factor that allows us to compute large ordinal
two-factorizations.},
added-at = {2023-04-24T11:04:51.000+0200},
author = {Dürrschnabel, Dominik and Stumme, Gerd},
biburl = {https://www.bibsonomy.org/bibtex/29dcf7585ac17738cf869999490083a41/duerrschnabel},
interhash = {c9681a551e3d5b8ef0591dcd6017baf1},
intrahash = {9dcf7585ac17738cf869999490083a41},
keywords = {2023 itegpub myown np_complete ordinal_factor_analysis two_dimension_extension},
note = {cite arxiv:2304.03338Comment: 14 pages, 6 figures, 2 algorithms},
timestamp = {2024-05-21T10:25:20.000+0200},
title = {Maximal Ordinal Two-Factorizations},
url = {http://arxiv.org/abs/2304.03338},
year = 2023
}