Agglomerative Independent Variable Group Analysis

Antti Honkela, Jeremias Seppä, Esa Alhoniemi

Abstract

Agglomerative Independent Variable Group Analysis (AIVGA) is a hierarchical clustering method designed to simplify complex datasets by grouping dependent variables. By utilizing a model-based approximation of mutual information, AIVGA constructs a dependency tree that identifies optimal sub-problems for predictive modeling. This approach addresses the limitations of traditional Independent Variable Group Analysis (IVGA) by providing a full structural overview of variable dependencies.

Introduction

In modern machine learning and data mining, high-dimensional datasets present significant computational challenges. One effective strategy for managing this complexity is to partition the dataset into smaller, independent groups of variables. The existing Independent Variable Group Analysis (IVGA) framework aims to achieve this by minimizing mutual information between groups. However, original IVGA implementations often rely on heuristic "hill-climbing" searches that may fail to find global optima regarding the number of groups.

This paper introduces AIVGA, an agglomerative hierarchical approach that allows researchers to visualize the complete hierarchy of dependencies. This enables the selection of the most effective granularity for specific tasks, balancing model complexity with predictive performance.

Methods

AIVGA applies the principles of agglomerative hierarchical clustering to the variable grouping problem. The process begins with each variable in its own group and iteratively merges pairs that result in the greatest decrease in a global cost function.

Dendrogram and cost history for the robot dataset. The dendrogram (left) shows the variable hierarchy, while the cost plot (right) helps identify optimal cutoff points.

A key innovation is the use of a Variational Bayes (VB) approximation of the marginal likelihood as a cost function. This serves as a computationally efficient proxy for mutual information. Each group is modeled using mixture models (Gaussian for continuous data, multinomial for categorical), with automatic pruning of unused components to maintain efficiency. The final output is a dendrogram representing the hierarchy of variable groupings, from $N$ individual groups down to a single group containing all variables.

Experimental Setup

The algorithm was evaluated using a real-world dataset from an operational assembly robot in printed circuit board manufacturing. The dataset consists of 5,016 samples with 22 nominal attributes. The primary task involved predicting attribute values using association rules, with an 80/20 train-test split.

Results and Discussion

AIVGA demonstrated significant advantages over non-hierarchical methods. In the robot dataset experiment, AIVGA identified the optimal grouping in approximately three hours, a substantial improvement over the dozens of hours required by previous approaches.

The hierarchical nature of AIVGA provides a "roadmap" of dependencies. The Bayesian cost function naturally suggests optimal cutoff points. For the robot dataset, the cost history indicated that a structure with two main groups was the most efficient representation of the data structure.

Predictive performance as a function of the number of groups. The proportion of correct predictions ("ok") peaks when the variables are divided into a small number of groups (2-4), outperforming a single monolithic model.

Predictive accuracy tests using association rules revealed that models with 2 to 4 groups outperformed a single monolithic model (1 group). As shown in the performance plots, the proportion of correct predictions ("ok") is maximized at low group counts before declining as the number of groups increases. This suggests that breaking the problem into independent sub-models can improve accuracy while reducing memory and computation requirements.

Conclusion

AIVGA offers a powerful framework for discovering the dependency structure of variables in large datasets. While the initial $O(N^2)$ complexity of fitting mixture models may be a bottleneck for very high-dimensional data, the gains in efficiency and predictive clarity are substantial. Future work may involve exploring alternative base models within the AIVGA framework and adapting the method for supervised feature selection.

Summary updated

Abstract

Independent variable group analysis (IVGA) is a method for grouping dependent variables together while keeping mutually independent or weakly dependent variables in separate groups. In this paper two variants of an agglomerative method for learning a hierarchy of IVGA groupings are presented. The method resembles hierarchical clustering, but the choice of clusters to merge is based on variational Bayesian model comparison. This is approximately equivalent to using a distance measure based on a model-based approximation of mutual information between groups of variables. The approach also allows determining optimal cutoff points for the hierarchy. The method is demonstrated to find sensible groupings of variables that can be used for feature selection and ease construction of a predictive model.
BibTeX
@inproceedings{honkela2007agglomerative,
  author = {Antti Honkela and Jeremias Seppä and Esa Alhoniemi},
  title = {{Agglomerative Independent Variable Group Analysis}},
  booktitle = {ESANN},
  year = {2007},
}
Figure