Mining the Interval Pattern of the Biomedical Clusters using Greedy Algorithms
Alexey V Galatenko, Stepan A Nersisyan, Vera V Pankratieva
Progress in Computing Applications, Vol. 9, No. 1, 2020.
DOI: https://doi.org/10.6025/pca/2020/9/1/17-23
Link: http://www.dline.info/pca/fulltext/v9n1/pcav9n1_4.pdf
Abstract:
Interval pattern concepts are a particular case of pattern structures. They can be used to clusterize rows of a
numerical formal context (data matrix): two rows are close to each other if their entries at the corresponding positions fall
within a given interval.
The problem of mining interval pattern concepts has much in common with the known problem related to computational
geometry: given a nite set of points in the Euclidean space, position a box of a given size in such a way that it encloses as many
points as possible. This problem and its variations have been thoroughly studied in the case of a plane; however, the authors
are not aware of the existence of algorithms which in a reasonable time produce an exact solution in the space of an arbitrary
dimension.
There exists an approximate greedy algorithm for solving this problem. It produces a solution with time which is linear in the
number of points and polynomial in dimension. We apply a clustering approach based on that algorithm to the gene expression
table from the dataset â€œThe Cancer Cell Line Encyclopediaâ€. The resulting partition well agrees with a priori known biological
factors.