skip to main content

Title: A Better Decision Tree: The Max-Cut Decision Tree with Modified PCA Improves Accuracy and Running Time

Decision trees are a widely used method for classification, both alone and as the building blocks of multiple different ensemble learning methods. The Max Cut decision tree introduced here involves novel modifications to a standard, baseline variant of a classification decision tree, CART Gini. One modification involves an alternative splitting metric, Max Cut, based on maximizing the distance between all pairs of observations that belong to separate classes and separate sides of the threshold value. The other modification, Node Means PCA, selects the decision feature from a linear combination of the input features constructed using an adjustment to principal component analysis (PCA) locally at each node. Our experiments show that this node-based, localized PCA with the Max Cut splitting metric can dramatically improve classification accuracy while also significantly decreasing computational time compared to the CART Gini decision tree. These improvements are most significant for higher-dimensional datasets. For the example dataset CIFAR-100, the modifications enabled a 49% improvement in accuracy, relative to CART Gini, while providing a$$6.8 \times$$6.8×speed up compared to the Scikit-Learn implementation of CART Gini. These introduced modifications are expected to dramatically advance the capabilities of decision trees for difficult classification tasks.

Award ID(s):
1760102 2112533
Publication Date:
Journal Name:
SN Computer Science
Springer Science + Business Media
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    We study the structure of the Liouville quantum gravity (LQG) surfaces that are cut out as one explores a conformal loop-ensemble$$\hbox {CLE}_{\kappa '}$$CLEκfor$$\kappa '$$κin (4, 8) that is drawn on an independent$$\gamma $$γ-LQG surface for$$\gamma ^2=16/\kappa '$$γ2=16/κ. The results are similar in flavor to the ones from our companion paper dealing with$$\hbox {CLE}_{\kappa }$$CLEκfor$$\kappa $$κin (8/3, 4), where the loops of the CLE are disjoint and simple. In particular, we encode the combined structure of the LQG surface and the$$\hbox {CLE}_{\kappa '}$$CLEκin terms of stable growth-fragmentation trees or their variants, which also appear in the asymptotic study of peeling processes on decorated planar maps. This has consequences for questions that do a priori not involve LQG surfaces: In our paper entitled “CLE Percolations” described the law of interfaces obtained when coloring the loops of a$$\hbox {CLE}_{\kappa '}$$CLEκindependently into two colors with respective probabilitiespand$$1-p$$1-p. This description was complete up to one missing parameter$$\rho $$ρ. The results of the present paper about CLE on LQG allow us to determine its value in terms ofpand$$\kappa '$$κ. It shows in particular that$$\hbox {CLE}_{\kappa '}$$CLEκand$$\hbox {CLE}_{16/\kappa '}$$CLE16/κare related via a continuum analog of the Edwards-Sokal coupling between$$\hbox {FK}_q$$FKqpercolation and theq-state Potts model (which makes sense evenmore »for non-integerqbetween 1 and 4) if and only if$$q=4\cos ^2(4\pi / \kappa ')$$q=4cos2(4π/κ). This provides further evidence for the long-standing belief that$$\hbox {CLE}_{\kappa '}$$CLEκand$$\hbox {CLE}_{16/\kappa '}$$CLE16/κrepresent the scaling limits of$$\hbox {FK}_q$$FKqpercolation and theq-Potts model whenqand$$\kappa '$$κare related in this way. Another consequence of the formula for$$\rho (p,\kappa ')$$ρ(p,κ)is the value of half-plane arm exponents for such divide-and-color models (a.k.a. fuzzy Potts models) that turn out to take a somewhat different form than the usual critical exponents for two-dimensional models.

    « less
  2. Abstract

    We consider thecapacitated cycle covering problem: given an undirected, complete graphGwith metric edge lengths and demands on the vertices, we want to cover the vertices with vertex-disjoint cycles, each serving a demand of at most one. The objective is to minimize a linear combination of the total length and the number of cycles. This problem is closely related to the capacitated vehicle routing problem (CVRP) and other cycle cover problems such as min-max cycle cover and bounded cycle cover. We show that a greedy algorithm followed by a post-processing step yields a$$(2 + \frac{2}{7})$$(2+27)-approximation for this problem by comparing the solution to a polymatroid relaxation. We also show that the analysis of our algorithm is tight and provide a$$2 + \epsilon $$2+ϵlower bound for the relaxation.

  3. Abstract

    Two-dimensional electron systems subjected to high transverse magnetic fields can exhibit Fractional Quantum Hall Effects (FQHE). In the GaAs/AlGaAs 2D electron system, a double degeneracy of Landau levels due to electron-spin, is removed by a small Zeeman spin splitting,$$g \mu _B B$$gμBB, comparable to the correlation energy. Then, a change of the Zeeman splitting relative to the correlation energy can lead to a re-ordering between spin polarized, partially polarized, and unpolarized many body ground states at a constant filling factor. We show here that tuning the spin energy can produce fractionally quantized Hall effect transitions that include both a change in$$\nu$$νfor the$$R_{xx}$$Rxxminimum, e.g., from$$\nu = 11/7$$ν=11/7to$$\nu = 8/5$$ν=8/5, and a corresponding change in the$$R_{xy}$$Rxy, e.g., from$$R_{xy}/R_{K} = (11/7)^{-1}$$Rxy/RK=(11/7)-1to$$R_{xy}/R_{K} = (8/5)^{-1}$$Rxy/RK=(8/5)-1, with increasing tilt angle. Further, we exhibit a striking size dependence in the tilt angle interval for the vanishing of the$$\nu = 4/3$$ν=4/3and$$\nu = 7/5$$ν=7/5resistance minima, including “avoided crossing” type lineshape characteristics, and observable shifts of$$R_{xy}$$Rxyat the$$R_{xx}$$Rxxminima- the latter occurring for$$\nu = 4/3, 7/5$$ν=4/3,7/5and the 10/7. The results demonstrate both size dependence and the possibility, not just of competition between different spin polarized states at the same$$\nu$$νand$$R_{xy}$$Rxy, but also the tilt- or Zeeman-energy-dependent- crossover between distinct FQHE associated withmore »different Hall resistances.

    « less
  4. Abstract

    We present here a characterization of the low background NaI(Tl) crystal NaI-33 based on a period of almost one year of data taking (891 kg$$\times $$×days exposure) in a detector configuration with no use of organic scintillator veto. This remarkably radio-pure crystal already showed a low background in the SABRE Proof-of-Principle (PoP) detector, in the low energy region of interest (1–6 keV) for the search of dark matter interaction via the annual modulation signature. As the vetoable background components, such as$$^{40}$$40K, are here sub-dominant, we reassembled the PoP setup with a fully passive shielding. We upgraded the selection of events based on a Boosted Decision Tree algorithm that rejects most of the PMT-induced noise while retaining scintillation signals with > 90% efficiency in 1–6 keV. We find an average background of 1.39 ± 0.02 counts/day/kg/keV in the region of interest and a spectrum consistent with data previously acquired in the PoP setup, where the external veto background suppression was in place. Our background model indicates that the dominant background component is due to decays of$$^{210}$$210Pb, only partly residing in the crystal itself. The other location of$$^{210}$$210Pb is the reflector foil that wraps the crystal. We now proceed to designmore »the experimental setup for the physics phase of the SABRE North detector, based on an array of similar crystals, using a low radioactivity PTFE reflector and further improving the passive shielding strategy, in compliance with the new safety and environmental requirements of Laboratori Nazionali del Gran Sasso.

    « less
  5. Abstract

    In this paper we disprove part of a conjecture of Lieb and Thirring concerning the best constant in their eponymous inequality. We prove that the best Lieb–Thirring constant when the eigenvalues of a Schrödinger operator$$-\Delta +V(x)$$-Δ+V(x)are raised to the power$$\kappa $$κis never given by the one-bound state case when$$\kappa >\max (0,2-d/2)$$κ>max(0,2-d/2)in space dimension$$d\ge 1$$d1. When in addition$$\kappa \ge 1$$κ1we prove that this best constant is never attained for a potential having finitely many eigenvalues. The method to obtain the first result is to carefully compute the exponentially small interaction between two Gagliardo–Nirenberg optimisers placed far away. For the second result, we study the dual version of the Lieb–Thirring inequality, in the same spirit as in Part I of this work Gontier et al. (The nonlinear Schrödinger equation for orthonormal functions I. Existence of ground states. Arch. Rat. Mech. Anal, 2021. In a different but related direction, we also show that the cubic nonlinear Schrödinger equation admits no orthonormal ground state in 1D, for more than one function.