A novel approach to cutting decision trees

In data mining, binary classification has a wide range of applications. Cutting Decision Tree (CDT) induction is an efficient mathematical programming based method that tries to discretize the data set on hand by using multiple separating hyperplanes. A new improvement to CDT model is proposed in this study by incorporating the second goal of maximizing the distance of the correctly classified instances to the misclassification region. Computational results show that developed model achieves better classification accuracy for Wisconsin Breast Cancer database and Japanese Banks data set when compared to existing piecewise-linear models in literature. Furthermore, remarkable results are obtained for the well-known benchmarking data sets (Buba Liver Disorders, Blood Tranfusion and Pima Indian Diabetes) when compared to the original CDT model.     

A complete characterization of disjunctive conic cuts for mixed integer second order cone optimization

We study the convex hull of the intersection of a disjunctive set defined by parallel hyperplanes and the feasible set of a mixed integer second order cone optimization (MISOCO) problem. We extend our prior work on disjunctive conic cuts (DCCs), which has thus far been restricted to the case in which the intersection of the hyperplanes and the feasible set is bounded. Using a similar technique, we show that one can extend our previous results to the case in which that intersection is unbounded. We provide a complete characterization in closed form of the conic inequalities required to describe the convex hull when the hyperplanes defining the disjunction are parallel.     

Performance criteria for plastic card fraud detection tools

In predictive data mining, algorithms will be both optimized and compared using a measure of predictive performance. Different measures will yield different results, and it follows that it is crucial to match the measure to the true objectives. In this paper, we explore the desirable characteristics of measures for constructing and evaluating tools for mining plastic card data to detect fraud. We define two measures, one based on minimizing the overall cost to the card company, and the other based on minimizing the amount of fraud given the maximum number of investigations the card company can afford to make. We also describe a plot, analogous to the standard ROC, for displaying the performance trace of an algorithm as the relative costs of the two different kinds of misclassification—classing a fraudulent transaction as legitimate or vice versa—are varied.     

Threshold optimization for classification in imbalanced data in a problem of gamma-ray astronomy

We introduce a method to minimize the mean square error (MSE) of an estimator which is derived from a classification. The method chooses an optimal discrimination threshold in the outcome of a classification algorithm and deals with the problem of unequal and unknown misclassification costs and class imbalance. The approach is applied to data from the MAGIC experiment in astronomy for choosing an optimal threshold for signal-background-separation. In this application one is interested in estimating the number of signal events in a dataset with very unfavorable signal to background ratio. Minimizing the MSE of the estimation is a rather general approach which can be adapted to various other applications, in which one wants to derive an estimator from a classification. If the classification depends on other or additional parameters than the discrimination threshold, MSE minimization can be used to optimize these parameters as well. We illustrate this by optimizing the parameters of logistic regression, leading to relevant improvements of the current approach used in the MAGIC experiment.     

An Algorithm for Solving the Minimum-Norm Point Problem over the Intersection of a Polytope and an Affine Set

In this paper, we propose an efficient algorithm for finding the minimum-norm point in the intersection of a polytope and an affine set in an n-dimensional Euclidean space, where the polytope is expressed as the convex hull of finitely many points and the affine set is expressed as the intersection of k hyperplanes, k1. Our algorithm solves the problem by using directly the original points and the hyperplanes, rather than treating the problem as a special case of the general quadratic programming problem. One of the advantages of our approach is that our algorithm works as well for a class of problems with a large number (possibly exponential or factorial in n) of given points if every linear optimization problem over the convex hull of the given points is solved efficiently. The problem considered here is highly degenerate, and we take care of the degeneracy by solving a subproblem that is a conical version of the minimum-norm point problem, where points are replaced by rays. When the number k of hyperplanes expressing the affine set is equal to one, we can easily avoid degeneracy, but this is not the case for k2. We give a subprocedure for treating the degenerate case. The subprocedure is interesting in its own right. We also show the practical efficiency of our algorithm by computational experiments.     

求DEA有效最速方向的一般方法

提出经验生产可能集的支撑超平面表示形式，在献[3]的基础上，对生产可能集内任意非DEA有效的决策单元，给出在生产可能集内，求解其DEA有效最速方向，使其最速达到DEA有效的一般方向，同时指出献[4]、[7]中的两处错误。     

A Theorem on Strict Separability of Convex Polyhedra and Its Applications in Optimization

We propose a new approach to the strict separation of convex polyhedra. This approach is based on the construction of the set of normal vectors for the hyperplanes, such that each one strict separates the polyhedra A and B. We prove the necessary and sufficient conditions of strict separability for convex polyhedra in the Euclidean space and present its applications in optimization.     

Real-time computation of optimal control

A new approach to the real-time implementation of time-optimal control for linear systems with a bounded control is proposed. The computational costs are separated between preliminary computations and computations in the course of the control process. The preliminary computations are independent of the particular initial condition and are based on the approximation of sets reachable in different times by a collection of hyperplanes. Methods for constructing hyperplanes and selecting a supporting hyperplane are described. Methods are proposed for approximately finding the normalized vector of initial conditions of the adjoint system, the driving time, and the switching times of the time-optimal control, and an iterative method for their refinement is developed. The computational complexity of the method is estimated. The computational algorithm is described, and simulation and numerical results are presented.     

The extended supporting hyperplane algorithm for convex mixed-integer nonlinear programming

A new deterministic algorithm for solving convex mixed-integer nonlinear programming (MINLP) problems is presented in this paper: The extended supporting hyperplane (ESH) algorithm uses supporting hyperplanes to generate a tight overestimated polyhedral set of the feasible set defined by linear and nonlinear constraints. A sequence of linear or quadratic integer-relaxed subproblems are first solved to rapidly generate a tight linear relaxation of the original MINLP problem. After an initial overestimated set has been obtained the algorithm solves a sequence of mixed-integer linear programming or mixed-integer quadratic programming subproblems and refines the overestimated set by generating more supporting hyperplanes in each iteration. Compared to the extended cutting plane algorithm ESH generates a tighter overestimated set and unlike outer approximation the generation point for the supporting hyperplanes is found by a simple line search procedure. In this paper it is proven that the ESH algorithm converges to a global optimum for convex MINLP problems. The ESH algorithm is implemented as the supporting hyperplane optimization toolkit (SHOT) solver, and an extensive numerical comparison of its performance against other state-of-the-art MINLP solvers is presented.     

Optimization over the efficient set using an active constraint approach

In this work the problem of maximizing a nonlinear objective over the set of efficient solutions of a multicriteria linear program is considered. This is a nonlinear program with nonconvex constraints. The approach is to develop an active constraint algorithm which utilizes the fact that the efficient structure in decision space can be associated in a natural way with hyperplanes in the space of objective values. Examples and numerical experience are included.     

Risk Estimation for Classification Trees

This article is a study of techniques for bias reduction of estimates of risk both globally and within terminal nodes of CART^R classification trees. In Section 5.4 of Classification and Regression Trees, Leo Breiman presented an estimator that has two free parameters. An empirical Bayes method was put forth for estimating them. Here we explain why the estimator should be successful in the many examples for which it is. We give numerical evidence from simulations in the two-class case with attention to ordinary resubstitution and seven other methods of estimation. There are 14 sampling distributions, all but one simulated and the remaining concerning E. coli promoter regions. We report on varying minimum node sizes of the trees; prior probabilities and misclassification costs; and, when relevant, the numbers of bootstraps or cross-validations. A variation of Breiman's method in which repeated cross-validation is employed to estimate global rates of misclassification was the most accurate from among the eight methods. Exceptions are cases for which the Bayes risk of the Bayes rule is small. For them, either a local bootstrap .632 estimate or Breiman's method modified to use a bootstrap estimate of the global misclassification rate is most accurate.     

Maximizing upgrading and downgrading margins for ordinal regression

In ordinal regression, a score function and threshold values are sought to classify a set of objects into a set of ranked classes. Classifying an individual in a class with higher (respectively lower) rank than its actual rank is called an upgrading (respectively downgrading) error. Since upgrading and downgrading errors may not have the same importance, they should be considered as two different criteria to be taken into account when measuring the quality of a classifier. In Support Vector Machines, margin maximization is used as an effective and computationally tractable surrogate of the minimization of misclassification errors. As an extension, we consider in this paper the maximization of upgrading and downgrading margins as a surrogate of the minimization of upgrading and downgrading errors, and we address the biobjective problem of finding a classifier maximizing simultaneously the two margins. The whole set of Pareto-optimal solutions of such biobjective problem is described as translations of the optimal solutions of a scalar optimization problem. For the most popular case in which the Euclidean norm is considered, the scalar problem has a unique solution, yielding that all the Pareto-optimal solutions of the biobjective problem are translations of each other. Hence, the Pareto-optimal solutions can easily be provided to the analyst, who, after inspection of the misclassification errors caused, should choose in a later stage the most convenient classifier. The consequence of this analysis is that it provides a theoretical foundation for a popular strategy among practitioners, based on the so-called ROC curve, which is shown here to equal the set of Pareto-optimal solutions of maximizing simultaneously the downgrading and upgrading margins.     

Truncated second main theorem with moving targets

We prove a truncated Second Main Theorem for holomorphic curves intersecting a finite set of moving or fixed hyperplanes. The set of hyperplanes is assumed to be non-degenerate. Previously only general position or subgeneral position was considered.

     

The Supersolvable Order of Hyperplanes of an Arrangement

This paper mainly gives a sufficient and necessary condition for an order of hyperplanes of a graphic arrangement being supersolvable. In addition, we give the relations between the set of supersolvable orders of hyperplanes and the set of quadratic orders of hyperplanes for a supersolvable arrangement.     

基于改进Adaboost的信用评价方法

网络借贷环境下基于Adaboost的信用评价方法具有较高的基分类器分歧度和样本误分代价。现有研究没有考虑分歧度和误分代价对基分类器样本权重的影响,从而降低了网络借贷信用评价结果的有效性。为此,提出一种基于改进Adaboost的信用评价方法。该方法根据基分类器的误分率,样本在不同基分类器上分类结果的分歧程度,以及样本的误分代价等因素,调整Adaboost模型的样本赋权策略,使得改进后的Adaboost模型能够对分类困难样本和误分代价高的样本实施有针对性的学习,从而提高网络借贷信用评价结果的有效性。基于拍拍贷平台数据的实验结果表明,提出的方法在分类精度和误分代价等方面显著优于传统的基于Adaboost的信用评价方法。     

Hyperplane arrangements with a lattice of regions

A hyperplane arrangement is a finite set of hyperplanes through the origin in a finite-dimensional real vector space. Such an arrangement divides the vector space into a finite set of regions. Every such region determines a partial order on the set of all regions in which these are ordered according to their combinatorial distance from the fixed base region.We show that the base region is simplicial whenever the poset of regions is a lattice and that conversely this condition is sufficient for the lattice property for three-dimensional arrangements, but not in higher dimensions. For simplicial arrangements, the poset of regions is always a lattice.In the case of supersolvable arrangements (arrangements for which the lattice of intersections of hyperplanes is supersolvable), the poset of regions is a lattice if the base region is suitably chosen. We describe the geometric structure of such arrangements and derive an expression for the rank-generating function similar to a known one for Coxeter arrangements. For arrangements with a lattice of regions we give a geometric interpretation of the lattice property in terms of a closure operator defined on the set of hyperplanes.The results generalize to oriented matroids. We show that the adjacency graph (and poset of regions) of an arrangement determines the associated oriented matroid and hence in particular the lattice of intersections.The work of Anders Björner was supported in part by a grant from the NSF. Paul Edelman's work was supported in part by NSF Grants DMS-8612446 and DMS-8700995. The work of Günter Ziegler was done while he held a Norman Levinson Graduate Fellowship at MIT.     

Finding strong defining hyperplanes of PPS using multiplier form

The production possibility set (PPS) is defined as the set of all inputs and outputs of a system in which inputs can produce outputs. In this paper, we deal with the problem of finding the strong defining hyperplanes of the PPS. These hyperplanes are equations that form efficient surfaces. It is well known that the optimal solutions of the envelopment formulation for extreme efficient units are often highly degenerate and, therefore, may have alternate optima for the multiplier form. Every optimal solution of the multiplier form yields a hyperplane which is supporting at the PPS. We will show that the hyperplane which corresponds to an extreme optimal solution of the multiplier form (in evaluating an efficient DMU), and whose components corresponding to inputs and outputs are non zero is a strong defining hyperplane of the PPS. This will be discussed in details in this paper. These hyperplanes are useful in sensitivity and stability analysis, the status of returns to scale of a DMU, incorporating performance into the efficient frontier analysis, and so on. Using numerical examples, we will demonstrate how to use the results.     

A new method for complete ranking of DMUs

So far numerous models have been proposed for ranking the efficient decision-making units (DMUs) in data envelopment analysis (DEA). But, the most shortcoming of these models is their two-stage orientation. That is, firstly we have to find efficient DMUs and then rank them. Another flaw of some of these models, like AP-model (A procedure for ranking efficient units in data envelopment analysis, Management Science, 39 (10) (1993) 1261–1264), is existence of a non-Archimedean number in their objective function. Besides, when there is more than one weak efficient unit (or non-extreme efficient unit) these models could not rank DMUs. In this paper, we employ hyperplanes of the production possibility set (PPS) and propose a new method for complete ranking of DMUs in DEA. The proposed approach is a one stage method which ranks all DMUs (efficient and inefficient). In addition to ranking, the proposed method determines the type of efficiency for each DMU, simultaneously. Numerical examples are given to show applicability of the proposed method.     

Finding weak defining hyperplanes of PPS of the BCC model

Production possibility set (PPS) is intersection of the several halfspaces. Every halfspace corresponds with one strong or weak defining hyperplane (facet). This research proposes a method to find weak defining hyperplanes of PPS of BCC model. We state and prove some properties relative to our method. Numerical examples are provided for illustration.