The Delaunay triangulation learner and its ensembles

Abstract

The Delaunay triangulation learner (DTL), which is a new piecewise linear learner, is proposed for both regression and classification tasks. Based on the data samples in a p-dimensional feature space, the Delaunay triangulation algorithm provides a unique way of triangulating the space. The triangulation separates the convex hull of the samples into a series of disjoint p-simplices, where the samples are the vertices of the p-simplices. The DTL is constructed by fitting the responses through linear interpolation functions on each of the Delaunay simplices, and thus it approximates the whole functional by a piecewise linear function. In the ensemble learning approaches, bagging DTLs, random crystal and the boosting DTL are introduced, where the DTLs are constructed on the subspaces of the features, and the feature interactions can be captured by Delaunay triangle meshes. Extensive numerical studies are conducted to compare the proposed DTL and its ensembles with tree-based counterparts, K-nearest neighbors and the multivariate adaptive regression spline. The DTL methods show competitive performances in various settings, and particularly the DTL demonstrates its superiority over others for smooth functionals.