Optimal monotone relabelling of partially non-monotone ordinal data

Abstract

Noise in multi-criteria data sets can manifest itself as non-monotonicity. Work on the remediation of such non-monotonicity is rather scarce. Nevertheless, errors are often present in real-life data sets, and several monotone classification algorithms are unable to use such partially non-monotone data sets. Fortunately, as we will show here, it is possible to restore monotonicity in an optimal way, by relabelling part of the data set. By exploiting the properties of a (minimum) flow network, and identifying pleasing properties of some maximum cuts, an elegant single-pass optimal ordinal relabelling algorithm is formulated.

AMS Subject Classification :

• 05C21
• 05C69
• 94C15

Keywords:

• ordinal data
• monotonicity
• monotone relabelling
• flow network
• maximum independent set
• maximum cut

Acknowledgements

This work was supported by a research project of the Special Research Fund of Ghent University (B/03843/01).