Identifying Most Predictive Items

Markus Wawryniuk, Daniel A. Keim

Abstract

Traditional association rule mining often relies on discretization to handle numerical data, a process that frequently introduces bias or loses critical information. This paper proposes a novel framework to identify categorical items that significantly alter the distribution of a numerical attribute. By employing the non-parametric Kolmogorov-Smirnov (KS) test and hierarchical agglomerative clustering, the authors identify itemsets that serve as strong predictors for specific distribution shapes. Experimental results on the UCI Adult dataset demonstrate that items like "Own-child" and "Never-married" are highly predictive of specific age profiles, validating the method's ability to capture nuanced relationships without arbitrary binning.

Introduction

In data mining, the Apriori framework is widely used to discover relationships between categorical items. However, real-world datasets often contain a mix of categorical and numerical attributes. The conventional approach to integrating numerical data involves discretization—partitioning continuous values into discrete intervals. This "binning" process is inherently problematic: wide bins obscure detail, while narrow bins reduce statistical significance. This paper addresses the challenge of identifying items that impact a numerical attribute's distribution without pre-emptive discretization.

Methodology

The proposed framework treats numerical data as a continuous distribution, utilizing a three-stage process:

1. Kolmogorov-Smirnov (KS) Test

To compare the distribution of a numerical attribute within a specific itemset against the global population, the authors utilize the KS-test. Unlike the t-test, which focuses on means, the KS-test is distribution-free and measures the maximum distance between two cumulative distribution functions (CDFs). This allows for the detection of shifts in skewness, variance, and overall shape.

Critical values $c(\alpha)$ for the Kolmogorov-Smirnov test at various significance levels $\alpha$.

The significance of the deviation is determined using critical values $c(\alpha)$, as shown in the table above. The paper also introduces a normalized KS-value to account for varying sample sizes across different itemsets, ensuring that small groups do not appear disproportionately unusual.

2. Distribution Clustering

Since multiple itemsets may exert similar influences on a numerical attribute, the authors apply hierarchical agglomerative clustering. Itemsets are grouped based on the similarity of the distribution shapes they produce, effectively identifying common "profiles" within the data.

3. Bayesian Prediction

To quantify the predictive power of individual items, the authors apply Bayes’ Law to calculate the probability $P(C_i | j)$, where $C_i$ is a distribution cluster and $j$ is an item. This metric identifies "anchor" items that strongly suggest a specific numerical outcome regardless of the other items present in the set.

Experimental Evaluation

The framework was evaluated using the Adult dataset from the UCI Machine Learning Repository, containing census data with 13 attributes. Age was selected as the target numerical attribute due to its intuitive interpretability and the ease with which results can be verified (e.g., the expectation that "Never-married" individuals are younger).

Results and Discussion

The analysis revealed several key insights:

  • High-Impact Items: Items such as "Never-married" and "Own-child" exhibited the highest KS values (> 22), indicating a profound shift toward younger age distributions. In contrast, "United-States" showed a KS value near zero, suggesting it has negligible predictive power for age in this context.
  • Cluster Profiles: The algorithm successfully identified three distinct age profiles: a global average cluster, a "missing youth" cluster (containing items like "Widowed" or "7th-8th grade education"), and a "youth-dominated" cluster (dominated by items like "Never-married").
  • Predictive Accuracy: Bayesian analysis confirmed that the item "Own-child" has a 0.996 probability of belonging to the youth-dominated cluster, marking it as a near-perfect predictor within the dataset.

Conclusion

By avoiding the "binning bottleneck," this methodology preserves the natural structure of numerical data and identifies items that act as distribution anchors. While the current approach requires manual parameter setting for support and clustering, future work will focus on automating these selections and exploring the combinatorial impact of multiple items on distribution shifts.

Summary updated

BibTeX
@inproceedings{wawryniuk2004identifying,
  author = {Markus Wawryniuk and Daniel A. Keim},
  title = {{Identifying Most Predictive Items}},
  booktitle = {PaRMa},
  year = {2004},
}
Figure