Computing optimized rectilinear regions for association rules

Abstract

We address the problem of finding useful regions for two-dimensional association rules and decision,trees. In a previous paper we presented efficient algorithms for computing optimized x-monotone regions, whose intersections with any vertical line are always undi-vided. In practice, however, the quality of x-monotone regions is not ideal, because the boundary of an x-monotone region tends to be notchy, and the region is likely to overfit a training dataset too much to give a good prediction for an unseen test dataset. T ” +l.:,-*..- ”..r.3:,,+,,.A _..^.. a”,, +t.,..^ _,.c., mn”,d 11 ‘ u111a yc4pcx *yT I,IOLl.z~U p’“p”uG cur UDrj “1 0, IGLLL-linear region whose intersection with any vertical line and whose intersection with any horizontal line are both undivided, so that the boundary of any rectilin-ear region is never notchy. This property is studied from a theoretical viewpoint, Experimental tests con-firm that the rectilinear region less overfits a training database and thefore provides a better prediction for unseen test data. We also present a novel efficient al-gorithm for computing optimized rectilinear regions. 1