Unsupervised Features Ranking via Coalitional Game Theory for Categorical Data
Not all real-world data are labeled, and when labels are not available, it is
often costly to obtain them. Moreover, as many algorithms suffer from the curse
of dimensionality, reducing the features in the data to a smaller set is often
of great utility. Unsupervised feature selection aims to reduce the number of
features, often using feature importance scores to quantify the relevancy of
single features to the task at hand. These scores can be based only on the
distribution of variables and the quantification of their interactions. The
previous literature, mainly investigating anomaly detection and clusters, fails
to address the redundancy-elimination issue. We propose an evaluation of
correlations among features to compute feature importance scores representing
the contribution of single features in explaining the dataset's structure.
  Based on Coalitional Game Theory, our feature importance scores include a
notion of redundancy awareness making them a tool to achieve redundancy-free
feature selection. We show that the deriving features' selection outperforms
competing methods in lowering the redundancy rate while maximizing the
information contained in the data. We also introduce an approximated version of
the algorithm to reduce the complexity of Shapley values' computations.