Open access

The Linear Separation Problem Revisited with ACCPM

  • Cahiers de recherche; 2002.11
Publication date2002

We investigate the use of ACCPM (Analytic Center Cutting Plane Method) for solving the linear separation problem, which is an important instance of the general data mining concept. Given two disjoints subsets of points, the problem is to find a hyperplane which separates these two subsets as well as possible. Our method consists of minimizing the total sum of misclassification gaps. For a large amount of data, the number of global iterations in the ACCPM process can be reduced by splitting the objective into several parts. Hence, we reduce the total time cost involved by the evaluations of the objective and its subsgradients. However, as the number of cuts increases with the number of subfunctioins, the time cost associated with becomes considerable. Therefore, we have to achieve a certain balance between the gain in the objective evaluations and the price we pay for the additional cuts generated. After providing an algorithm to compute a good starting point wich yields a faster convergence, we perform some experiments with four sample databases over various disaggregated forms. We have used a 500 Mhz SUN Ultrasparc with 256 MB of RAM. The report of measured execution times shows that the method is quite efficient, and the compromise previously explained is well illustrated. An asymptotic time analysis is provided and from this, we derive an expression approximating the value of the optimal partition size.

Citation (ISO format)
TADONKI, Claude, VIAL, Jean-Philippe. The Linear Separation Problem Revisited with ACCPM. 2002
Main files (1)
  • PID : unige:5811

Technical informations

Creation04/15/2010 12:20:21 PM
First validation04/15/2010 12:20:21 PM
Update time03/14/2023 3:26:41 PM
Status update03/14/2023 3:26:41 PM
Last indexation01/15/2024 7:44:02 PM
All rights reserved by Archive ouverte UNIGE and the University of GenevaunigeBlack