Discovery of Pairwise Ordinal Edit Rules

Milan Peelman, Antoon Bronselaer, Guy De TréIfsa/eusflat/agop 2021 · DOI

Abstract

Edit rules are simple tuple-level constraints that concisely model which tuples are not permitted in a consistent relation. Previously, developed algorithms mostly assumed nominal data. This implies that ordinal data either had to be discarded or discretized according to expert knowledge. We can omit this by working with the ordinal data directly. In this paper we explore the discovery of low lift pairwise ordinal edit rules and propose an efficient algorithm employing several pruning strategies derived from the lift measure. Our experiments show that we can obtain a similar precision as nominal algorithms, while having an acceptable computational cost.

Introduction

In data management, "edit rules" are essential tools used to define which combinations of values are prohibited in a consistent database. Traditionally, research in this area has been divided into two primary categories: nominal rules, which treat data as unordered categories (e.g., Color: Red, Blue), and linear rules, which assume data is continuous and additive (e.g., Salary < Expenses).

However, a significant gap exists for ordinal data—data that possesses a clear order but lacks a measurable "distance" between values (e.g., "Low," "Medium," "High"). Researchers often force ordinal data into nominal categories, losing valuable order information, or treat it as linear, making unfounded assumptions about the numerical distance between categories. This paper introduces a formal framework for discovering ordinal edit rules specifically designed for these settings.

Defining Pairwise Ordinal Edit Rules

The authors propose defining an ordinal edit rule as a forbidden region formed by the cross-product of intervals on two ordered attributes. By defining rules as intervals on a "chain" (a totally ordered set), the framework maintains the expressive power of nominal rules while respecting the inherent ordering of the data.

A forbidden region defined by the cross-product of intervals on two ordinal attributes.

Unlike linear edit rules, ordinal rules can capture "rectangular" forbidden zones that do not necessarily follow a straight line. This capability is crucial for modeling complex, non-linear constraints that are common in real-world datasets.

Discovery via Lift and the OrdinalBinaryLiftMiner

To automate the discovery of these rules, the researchers utilize a lift measure ($\lambda$). In this context, a "low lift" indicates a region in the data space containing significantly fewer records than expected if the attributes were independent. These sparse regions are prime candidates for edit rules, as their rarity often suggests a logical inconsistency or data quality issue.

Searching all possible interval combinations is computationally expensive, scaling at $O(|A_1||A_2|)$ for every pair of attributes. To address this, the authors introduced the OrdinalBinaryLiftMiner algorithm, which employs two key mathematical pruning strategies:

  1. Lower Bound Thresholds: If the lift threshold is mathematically too low for any rules to exist based on the record count, the search is terminated early.
  2. Attribute Split Boundaries: If a specific split already exceeds the threshold, the algorithm can bypass checking further sub-intervals, significantly reducing the search space.

Experimental Evaluation

The approach was evaluated on two real-world datasets: the Adult Dataset (~32,000 instances) and the EudraCT (European Union Drug Regulating Authorities Clinical Trials) dataset (~86,000 instances). The EudraCT dataset was particularly valuable as it provided a "ground truth" for pairwise rules to measure precision.

Visualization of data density and discovered rule boundaries for the Age and Income attributes.

Key Results

  • Precision: On the EudraCT dataset, the algorithm achieved 100% precision at a very low lift threshold ($\tau = 0.01$). While precision decreased as the threshold increased (allowing for "noisier" rules), it remained comparable to established nominal algorithms.
  • Efficiency: The pruning strategies proved highly effective. For small values of $\tau$, the pruned algorithm maintained a near-linear runtime relative to the threshold, outperforming naive search methods.
  • Data Quality: The discovered rules successfully identified logical inconsistencies, such as impossible combinations of age and education level, which standard nominal checks might overlook.

Conclusion and Future Work

This research demonstrates that ordinal edit rules can be discovered efficiently without manual discretization. While currently restricted to pairwise attributes and optimized for monotonic relationships, the framework provides a robust foundation for data cleaning in ordinal contexts. Future work will focus on extending the algorithm to handle conditional ordinal relationships involving three or more variables and developing advanced rule implication methods that fully exploit the total order of the data.

Summary updated

BibTeX
@inproceedings{peelman2021discovery,
  author = {Milan Peelman and Antoon Bronselaer and Guy De Tré},
  title = {{Discovery of Pairwise Ordinal Edit Rules}},
  booktitle = {Ifsa/eusflat/agop},
  year = {2021},
  doi = {10.2991/asum.k.210827.015},
}
Figure