D. Dürrschnabel, und G. Stumme. Graph-Based Representation and Reasoning, Seite 41--55. Cham, Springer Nature Switzerland, (2023)
Zusammenfassung
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 \$\$\backslashtextsf\NP\\$\$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 Conference Paper
%1 10.1007/978-3-031-40960-8_5
%A Dürrschnabel, Dominik
%A Stumme, Gerd
%B Graph-Based Representation and Reasoning
%C Cham
%D 2023
%E Ojeda-Aciego, Manuel
%E Sauerwald, Kai
%E Jäschke, Robert
%I Springer Nature Switzerland
%K 2023 factorization itegpub myown ordinal_factor_analysis two_dimensional
%P 41--55
%T Maximal Ordinal Two-Factorizations
%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 \$\$\backslashtextsf\NP\\$\$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.
%@ 978-3-031-40960-8
@inproceedings{10.1007/978-3-031-40960-8_5,
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 {\$}{\$}{\backslash}textsf{\{}NP{\}}{\$}{\$}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-12-14T09:34:08.000+0100},
address = {Cham},
author = {Dürrschnabel, Dominik and Stumme, Gerd},
biburl = {https://www.bibsonomy.org/bibtex/2ab45693c5282706c6aa20a36c0b3e8dd/stumme},
booktitle = {Graph-Based Representation and Reasoning},
editor = {Ojeda-Aciego, Manuel and Sauerwald, Kai and Jäschke, Robert},
interhash = {c9681a551e3d5b8ef0591dcd6017baf1},
intrahash = {ab45693c5282706c6aa20a36c0b3e8dd},
isbn = {978-3-031-40960-8},
keywords = {2023 factorization itegpub myown ordinal_factor_analysis two_dimensional},
pages = {41--55},
publisher = {Springer Nature Switzerland},
timestamp = {2023-12-14T09:34:08.000+0100},
title = {Maximal Ordinal Two-Factorizations},
year = 2023
}