S. Bandyapadhyay, F. Fomin, P. Golovach, K. Simonov:

"Parameterized Complexity of Feature Selection for Categorical Data Clustering";

Talk: International Symposium on Mathematical Foundations of Computer Science (MFCS), Tallinn (Estonia); 2021-08-23 - 2021-08-27; in: "46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)", LIPICS, 202 (2021), ISBN: 978-3-95977-201-3; 1 - 14.

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 small-cost clustering

on the selected features. More precisely, for given integers ℓ (the number of irrelevant features)

and k (the number of clusters), budget B, and a set of n categorical data points (represented by

m-dimensional vectors whose elements belong to a finite set of values Σ), we want to select m − ℓ

relevant features such that the cost of any optimal k-clustering on these features does not exceed

B. Here the cost of a cluster is the sum of Hamming distances (ℓ0-distances) 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, |Σ|) · mg(k,|Σ|) · n2 for some functions f and g. In other words,

the problem is fixed-parameter 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 Low-rank 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.

http://dx.doi.org/10.4230/LIPIcs.MFCS.2021.14

https://publik.tuwien.ac.at/files/publik_300323.pdf

Created from the Publication Database of the Vienna University of Technology.