Informatics and Applications
2018, Volume 12, Issue 1, pp 40-48
ON THE FORMALIZATION OF TASKS SEARCHING DENSE SUBMATRICES IN BOOLEAN SPARSE MATRICES
Abstract
In a significant part of data mining applications such as microbiology, gene expression data, text and web information, market baskets, customer environments, input information is represented as a two-dimensional matrix "subjects-objects" ("clients-services"). The main goal of such problems is biclustering of data, based on the selection of groups in a certain sense of similar rows and columns. A lot of such problems is characterized by strong sparseness of the corresponding matrices. An important aspect of biclustering is the search in some sense of dense submatrices in boolean matrices, which is the main purpose of this research. The author formalizes subject area within the framework of algebraic approach, describes the systems of universal and local constraints, proposes and proves the corresponding criteria for solvability of the problems under consideration.
[+] References (12)
- Zhuravlev, Yu. I. 1977. Korrektnye algebry nad mnozhest- vami nekorrektnykh (evristicheskikh) algoritmov. Chast' I [Correct algebras over sets of incorrect (heuristic) algorithms. Part I]. Kibernetika [Cybernetics] 4:5-17.
- Zhuravlev, Yu. I. 1977. Korrektnye algebry nad mno- zhestvami nekorrektnykh (evristicheskikh) algoritmov. Chast' II [Correct algebras over sets of incorrect (heuristic) algorithms. Part II]. Kibernetika [Cybernetics] 6:21-27.
- Zhuravlev, Yu. I. 1978. Korrektnye algebry nad mno- zhestvami nekorrektnykh (evristicheskikh) algoritmov. Chast' III [Correct algebras over sets of incorrect (heuristic) algorithms. Part III]. Kibernetika [Cybernetics] 2:35- 43.
- Mirkin, B. 1996. Mathematical classification and clustering. Kluwer Academic Publs. 439 p.
- Hartigan, J.A. 1972. Direct clustering of a data matrix. J. Am. Stat. Assoc. 67(337):123-129.
- Cheng, Y., and G. M. Church. 2000. Biclustering of expression data. Conference (International) on Intelligent Systems for Molecular Biology. AAAI Press. P 93-103.
- Tanay, Y., R. Sharan, and R. Shamir. 2002. Discovering statistically significant biclusters in gene expression data. Bioinformatics 18(Suppl. 1):136-144.
- Rudakov, K.V. 1986. O nekotorykh universal'nykh ogranicheniyakh dlya algoritmov klassifikatsii [Some universal constraints for classification algorithms]. Zh VMMF [Comp. Math. Math. Phys.] 26(11):1719-1730.
- Rudakov, K.V. 1987. Universal'nye i lokal'nye ogranicheniya v probleme korrektsii evristicheskikh al- goritmov [Universal and local constraints in the problem of correction of heuristic algorithms]. Kibernetika [Cybernetics] 2:30-35.
- Rudakov, K.V. 1988. O primenenii universal'nykh ogranicheniy pri issledovanii algoritmov klassifikatsii [About the application of universal constraints in the research ofclassification algorithms]. Kibernetika [Cybernetics] 1:1-5.
- Rudakov, K. V. 1989. Ob algebraicheskoy teorii universal'nykh i lokal'nykh ogranicheniy dlya zadach klassifikatsii [About the algebraic theory of universal and local constraints for classification problems]. Raspoznavanie, klassifikatsiya, prognoz [Recognition, classification, forecast]. Moscow: Nauka. 176-201.
- Rudakov, K.V., and Yu. V. Chekhovich. 2002. Design of trend-identification algorithms with learning (algebraic approach). Comput. Math. Modeling 13(3):281-293.
[+] About this article
Title
ON THE FORMALIZATION OF TASKS SEARCHING DENSE SUBMATRICES IN BOOLEAN SPARSE MATRICES
Journal
Informatics and Applications
2018, Volume 12, Issue 1, pp 40-48
Cover Date
2018-03-30
DOI
10.14357/19922264180105
Print ISSN
1992-2264
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
sparse matrices; dense submatrices; algebraic approach; set-theoretic constraints; biclustering
Authors
I. S. Aleshin 
Author Affiliations
Faculty of Computational Mathematics and Cybernetics, M.V. Lomonosov Moscow State University, GSP-1, Leninskie Gory, Moscow 119991, Russian Federation
|