Bandyapadhyay, Sayan ;
Fomin, Fedor V. ;
Golovach, Petr A. ;
Simonov, Kirill
Parameterized Complexity of Feature Selection for Categorical Data Clustering
Abstract
We develop new algorithmic methods with provable guarantees for feature selection in regard to categorical data clustering. While feature selection is one of the most common approaches to reduce dimensionality in practice, most of the known feature selection methods are heuristics. We study the following mathematical model. We assume that there are some inadvertent (or undesirable) features of the input data that unnecessarily increase the cost of clustering. Consequently, we want to select a subset of the original features from the data such that there is a smallcost clustering on the selected features. More precisely, for given integers l (the number of irrelevant features) and k (the number of clusters), budget B, and a set of n categorical data points (represented by mdimensional vectors whose elements belong to a finite set of values Σ), we want to select ml relevant features such that the cost of any optimal kclustering on these features does not exceed B. Here the cost of a cluster is the sum of Hamming distances (l0distances) between the selected features of the elements of the cluster and its center. The clustering cost is the total sum of the costs of the clusters.
We use the framework of parameterized complexity to identify how the complexity of the problem depends on parameters k, B, and Σ. Our main result is an algorithm that solves the Feature Selection problem in time f(k,B,Σ)⋅m^{g(k,Σ)}⋅n² for some functions f and g. In other words, the problem is fixedparameter tractable parameterized by B when Σ and k are constants. Our algorithm for Feature Selection is based on a solution to a more general problem, Constrained Clustering with Outliers. In this problem, we want to delete a certain number of outliers such that the remaining points could be clustered around centers satisfying specific constraints. One interesting fact about Constrained Clustering with Outliers is that besides Feature Selection, it encompasses many other fundamental problems regarding categorical data such as Robust Clustering, Binary and Boolean Lowrank Matrix Approximation with Outliers, and Binary Robust Projective Clustering. Thus as a byproduct of our theorem, we obtain algorithms for all these problems. We also complement our algorithmic findings with complexity lower bounds.
BibTeX  Entry
@InProceedings{bandyapadhyay_et_al:LIPIcs.MFCS.2021.14,
author = {Bandyapadhyay, Sayan and Fomin, Fedor V. and Golovach, Petr A. and Simonov, Kirill},
title = {{Parameterized Complexity of Feature Selection for Categorical Data Clustering}},
booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
pages = {14:114:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772013},
ISSN = {18688969},
year = {2021},
volume = {202},
editor = {Bonchi, Filippo and Puglisi, Simon J.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14454},
URN = {urn:nbn:de:0030drops144544},
doi = {10.4230/LIPIcs.MFCS.2021.14},
annote = {Keywords: Robust clustering, PCA, Low rank approximation, Hypergraph enumeration}
}
18.08.2021
Keywords: 

Robust clustering, PCA, Low rank approximation, Hypergraph enumeration 
Seminar: 

46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Issue date: 

2021 
Date of publication: 

18.08.2021 