UNIGE document Report
previous document  unige:5811  next document
add to browser collection

The Linear Separation Problem Revisited with ACCPM

Year 2002
Collection Cahiers de recherche; 2002.11
Abstract 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.
Full text
(ISO format)
TADONKI, Claude, VIAL, Jean-Philippe. The Linear Separation Problem Revisited with ACCPM. 2002 https://archive-ouverte.unige.ch/unige:5811

408 hits



Deposited on : 2010-04-15

Export document
Format :
Citation style :