PPubMed7 Jul 2022Cited 3×

LPDA: A new classification method based on linear programming LPDA: A new classification method based on linear programming

María J. Nueda, Carmen Gandía, Mariola D. Molina, Eugene Demidenko

Abstract

The search of separation hyperplanes is an efficient way to find rules with classification purposes. This paper presents an alternative mathematical programming formulation to existing methods to find a discriminant hyperplane. The hyperplane H is found by minimizing the sum of all the distances to the area assigned to the group each individual belongs to. It results in a convex optimization problem for which we find an equivalent linear programming problem. We demonstrate that H exists when the centroids of the two groups are not equal. The method is effective dealing with low and high dimensional data where reduction of the dimension is proposed to avoid overfitting problems. We show the performance of this approach with different data sets and comparisons with other classifications methods. The method is called LPDA and it is implemented in a R package available in [https://github.com/mjnueda/lpda]().

§ The Valyu brief

The paper, in five minutes

Read from the full text via Valyu Contents

LPDA is a linear‑programming based classifier that finds a discriminant hyperplane, handles high‑dimensional and imbalanced data, and matches or outperforms SVM and other methods.

What’s new

i.Formulated classification as a convex optimization problem equivalent to linear programming (LPDA)
ii.Proved existence of a separating hyperplane when group centroids differ
iii.Integrated PCA dimensionality reduction to avoid overfitting in high‑dimensional data
iv.Provided an open‑source R package implementing LPDA
v.Demonstrated performance on low‑dimensional, unbalanced, and RNA‑Seq high‑dimensional datasets

How they did it

The authors define a separation‑error function and reformulate its minimization as an equivalent linear programming problem to obtain a discriminant hyperplane. For multi‑class problems they apply pairwise LPDA and use PCA to reduce dimensionality before classification. They evaluate the method on three real datasets and compare it with SVM, LDA, Logistic Regression, and RNA‑Seq specific classifiers.

What they found

Palmdates: LPDA produced only 1 classification error versus 1, 2, and 7 errors for SVM in three variable comparisons
Default data: LPDA achieved sensitivity comparable to weighted‑SVM and higher specificity (exact numbers not reported)
Cervical cancer RNA‑Seq: LPDA (and SVM) had zero training errors, while POlda had 3 errors and NBlda had 4 errors
Cross‑validation: LPDA‑PCA error rates were similar to SVM and NBlda (exact rates not provided)

Caveats

✕Results are reported only for two‑group problems; multi‑class extension relies on pairwise comparisons
✕Performance depends on choosing the number of principal components for PCA
✕No quantitative error‑rate figures are given for some comparisons, limiting reproducibility
✕Method may be less effective for inherently non‑linear class boundaries

§ The Valyu brief

Reading the full paper and taking notes. This takes a few seconds…

§ Ask this paper

Ask a question about this paper

Valyu reads the full text and answers from what the paper actually says.

§ Related work in other archives

LPDA: A new classification method based on linear programming LPDA: A new classification method based on linear programming

The paper, in five minutes

Ask a question about this paper

Similar papers in all four archives

Similar papers in all four archives

The paper, in five minutes