A Local Search Algorithm for the Biclustering Problem

A Local Search Algorithm for the Biclustering Problem Full article

Conference

The 10th International Conference on Analysis of Images, Social Networks and Texts
16-18 Dec 2021 , Тбилиси

Journal

Lecture Notes in Computer Science
ISSN: 0302-9743 , E-ISSN: 1611-3349

Output data

Year: 2022, Volume: 13217, Pages: 330–344 Pages count : 15 DOI: 10.1007/978-3-031-16500-9_27

Tags

Data mining · Biclustering · Heuristics · Local search

Authors

Levanova Tatyana ^1,2 , Khmara Ivan ¹

Affiliations

1	Sobolev Institute of Mathematics, Omsk Branch, Pevtsova str. 13, 644043 Omsk, Russia
2	Dostoevsky Omsk State University, Prospekt Mira 55A, 644077 Omsk, Russia

Biclustering is an approach to solving data mining problems, which consists in simultaneously grouping rows and columns of a matrix. In this paper, we solve the problem of finding a bicluster of the maximum size, the elements of which should differ from each other by no more than a given value. To solve it, a new local search algorithm has been developed, representing an iterative greedy search. For its implementation, problem-oriented neighborhoods are constructed, different rules for determining the difference of bicluster elements are used. The constructed algorithm is tested on various types of data, the results are compared with the well-known algorithm of Cheng and Church. In all the examples considered, the sizes of the found biclusters are not less than the biclusters of the Cheng and Church algorithm. At the same time, the difference between the elements of bicluster and their average value in most cases is smaller than for the Cheng and Church biclusters.

Levanova T. , Khmara I.
A Local Search Algorithm for the Biclustering Problem
Lecture Notes in Computer Science. 2022. V.13217. P.330–344. DOI: 10.1007/978-3-031-16500-9_27 Scopus РИНЦ OpenAlex

Scopus:	2-s2.0-85142684434
Elibrary:	50334907
OpenAlex:	W4313177465

DB	Citing
OpenAlex	1