?
On Suboptimality of GreConD for Boolean Matrix Factorisation of Contranominal Scales
P. 87–98.
Ignatov D. I., Yakovleva A.
In this paper we study certain properties of the GreConD algorithm for Boolean matrix factorisation, a popular technique in Data Mining with binary relational data. This greedy algorithm was inspired by the fact that the optimal number of factors for the Boolean matrix factorisation can be chosen among the formal concepts of the correspond- ing formal context. In particular, we consider one of the hardest cases (in terms of the numerous of possible factors), the so-called contranominal scales, and show that the output of GreConD is not optimal in this case. Moreover, we formally analyse its output by means of recurrences and generating functions and provide the reader with the closed form for the returned number of factors. An algorithm generating the optimal num- ber of factors and the corresponding product matrices P and Q is also provided by us for the case of contranominal scales.
Language:
English
In book
Vol. 2972. , CEUR-WS, 2021.
Karpukhina D., Fedyanin D., , in: 2023 5th International Conference on Control Systems, Mathematical Modeling, Automation and Energy Efficiency (SUMMA)Vol. 5.: IEEE, 2023. P. 888–893.
The authors focus on the maintenance of transportation systems. Its dependability is fundamental to the well-being, health and comfort of citizens. The model described in this article imitates two processes simultaneously: road deterioration and road maintenance. The main assumption is that the destruction of roads depends on the betweenness centrality of the city’s graph. The ...
Added: February 24, 2024
Kuznetsov S., Gromov V., Borodin N. et al., Lecture Notes in Computer Science 2023 P. 331–339
Some results of a computational experiment for determining the intrinsic dimension of linguistic varieties for the Bengali and Russian languages are presented. At the same time, both sets of words and sets of bigrams in these languages were considered separately. The method used to solve this problem was based on formal concept analysis algorithms. It ...
Added: February 5, 2024
Ignatov D. I., Lobachevskii Journal of Mathematics 2023 No. 44 P. 137–146
We consider two ways how to compute the number of maximal antichains in the Boolean lattice on 𝑛 elements. The first one is based on full direct enumeration, while the second ones relies on concept lattices or Galois lattices (studied in Formal Concept Analysis, an applied branch of lattice theory) and the Dedekind–MacNeille completion of a partial ...
Added: June 13, 2023
Parakal E. G., Kuznetsov S., , in: Proceedings of the 10th International Workshop "What can FCA do for Artificial Intelligence?"Vol. 3233.: CEUR Workshop Proceedings, 2022. Ch. 2 P. 9–22.
Explanations for the predictions made by Machine Learning (ML) models are best framed in terms of
abstract, high-level concepts that are easily comprehensible to human beings. The use of such concepts
constitutes a subfield of interpretability methods known as concept-based explanations. This work uses
concept-based explanations to build an intrinsically interpretable document classifier using a combination
of Formal Concept ...
Added: May 17, 2023
Gribanov D., Zolotykh N., Optimization Letters 2022 Vol. 16 No. 7 P. 1991–2018
Let a polyhedron $P$ be defined by one of the following ways:
\begin{enumerate}
\item[(i)] $P = \{x \in \RR^n \colon A x \leq b\}$, where $A \in \ZZ^{(n+k) \times n}$, $b \in \ZZ^{(n+k)}$ and $\rank A = n$,
\item[(ii)] $P = \{x \in \RR_+^n \colon A x = b\}$, where $A \in \ZZ^{k \times n}$, $b \in \ZZ^{k}$ ...
Added: October 29, 2021
Harnad J., Runov B. A., Annales de l'Institut Henri Poincare (D) Combinatorics, Physics and their Interactions 2021 Vol. 8 No. 1 P. 119–158
Weighted constellations give graphical representations of weighted branched coverings of the Riemann sphere. They were introduced to provide a combinatorial inter-pretation of the 2D Toda τ-functions of hypergeometric type serving as generating functions for weighted Hurwitz numbers in the case of polynomial weight generating functions. The product over all vertex and edge weights of a ...
Added: October 21, 2021
Gravin N., Pasechnik D., Shapiro B. et al., Analysis and Mathematical Physics 2018 Vol. 8 No. 2 P. 255–287
We show that the multivariate generating function of appropriately normalized moments of a measure with homogeneous polynomial density supported on a compact polytope P subset of R-d is a rational function. Its denominator is the product of linear forms dual to the vertices of P raised to the power equal to the degree of the ...
Added: February 25, 2021
Mazalov V. V., V. V. Gusev, Performance Evaluation 2020 Vol. 144 P. 102135
We consider a cooperative game based on a network in which nodes represent players
and the characteristic function is defined using a maximal covering by the pairs of
connected nodes. Problems of this form arise in many applications such as mobile
communications, patrolling, logistics and sociology. The Owen value, which describes
the significance of each node in the network, ...
Added: September 29, 2020
Ayzenberg A., / Series arXiv "math". 2019.
The general goal of this paper is to gather and review several methods from homotopy and combinatorial topology and formal concepts analysis (FCA) and analyze their connections. FCA appears naturally in the problem of combinatorial simplification of simplicial complexes and allows to see a certain duality on a class of simplicial complexes. This duality generalizes ...
Added: November 15, 2019
CEUR Workshop Proceedings, 2019.
Added: October 31, 2019
Makhalova T., Napoli A., Kuznetsov S., , in: CLA 2018: The 14th International Conference on Concept Lattices and Their Applications.: CEUR Workshop Proceedings, 2018.
Added: November 25, 2018
Makhalova T., , in: Искусственный интеллект в решении актуальных социальных и экономических проблем ххi века: сборник статей Всероссийской научно-практической конференции (14-18 мая 2018 г, г. Пермь).: ПГНИУ, 2018.
Cluster assessment remains one of the most actual problems in data mining. In this paper, a new approach to the selection of clusters based on a combination of measures of cluster quality is proposed. The new approach incorporates easily expert understanding of “interestingness” of clusters and does not require pre-defined parameters and thresholds. The subset ...
Added: November 25, 2018
E. F. Goncharova, Gaidel A. V., , in: CEUR Workshop ProceedingsVol. 2210: Proceedings of the International Conference Information Technology and Nanotechnology. Session Image Processing and Earth Remote Sensing .: [б.и.], 2018. P. 38–46.
To improve the performance of remote sensing images multiclass classification we propose two greedy algorithms of feature selection. The discriminant analysis criterion and regression coefficients are used as the measure of feature subset effectiveness in the first and second methods respectively. The main benefit of the built algorithms is that they estimate not the individual ...
Added: November 10, 2018
Goncharova E., Гайдель А. В., В кн.: Сборник трудов IV Международной конференции и молодёжной школы "Информационные технологии и нанотехнологии" (ИТНТ 2018).: Самара: Предприятие "Новая техника", 2018. С. 620–630.
To improve the performance of remote sensing images multiclass classification we propose two greedy algorithms of feature selection. The discriminant analysis criterion and regression coefficients are used as the measure of feature subset effectiveness in the first and second methods, respectively. The main benefit of the built algorithms is that they estimate not the individual ...
Added: November 9, 2018
Лабутин И. Н., Moskvin D., Omelchenko A. et al., Записки научных семинаров ПОМИ РАН 2018 Т. 475 С. 99–121
The article considers combinatorial problems associated with the enumeration of lambda-terms in a untyped lambda calculus, as well as in simply typed systems with a single atom in the style of Church. For the case of untyped lambda calculus a system of equations for generating functions is constructed which describes the number of lambda terms. ...
Added: October 30, 2018
A. Omelchenko, Meshkov V., Petrov M. et al., Moscow Mathematical Journal 2010 Vol. 10 No. 3 P. 611–628
Exponential generating functions for the Dyck and Motzkin triangles are constructed for various assignments of multiplicities to the arrows of these triangles. The possibility to build such a function provided that the generating function for paths that end on the axis is a priori unknown is analyzed. Asymptotic estimates for the number of paths are ...
Added: August 30, 2018
Avdoshin S. M., Набебин А. А., М.: ДМК Пресс, 2019.
The book contains the necessary information from the algorithm theory, graph theory, combinatorics. It is considered partially recursive functions, Turing machines, some versions of the algorithms (associative calculus, the system of substitutions, grammars, Post's productions, Marcov's normal algorithms, operator algorithms). The main types of graphs are described (multigraphs, pseudographs, Eulerian graphs, Hamiltonian graphs, trees, bipartite ...
Added: August 24, 2018
Bezhaeva Z., Куликов В. Л., Олехова Е. Ф. et al., В кн.: Материалы конференции «Современная математика и концепции инновационного математического образования».: ООО "Издательский дом МФО", 2016. С. 27–32.
In this paper we obtain the solution of some functional equation of Ruelle’s type using a power series with random coefficients ...
Added: December 5, 2016
Ignatov D. I., Ахматнуров М., , in: Proceedings of the Twelfth International Conference on Concept Lattices and Their Applications Clermont-Ferrand, France, October 13-16, 2015Vol. 1466.: Clermont-Ferrand: CEUR Workshop Proceedings, 2015. P. 99–110.
In this work we propose and study an approach for collaborative filtering, which is based on Boolean matrix factorisation and exploits additional (context) information about users and items. To avoid similarity loss in case of Boolean representation we use an adjusted type of projection of a target user to the obtained factor space. We have ...
Added: October 23, 2015