Multi-polytope machine for classification

Patent metadata

Field	Value
Publication number	US-12586002-B2
Application number	US-202117491494-A
Country	US
Kind code	B2
Filing date	Sep 30, 2021
Priority date	Sep 30, 2021
Publication date	Mar 24, 2026
Grant date	Mar 24, 2026

Abstract

A computer implemented method of generating a classifier engine for machine learning includes receiving a set of data points. A semi-supervised k-means process is applied to the set of data points from each class. The set of data points in a class is clustered into multiple clusters of data points, using the semi-supervised k-means process. Multi-polytopes are constructed for one or more of the clusters from all classes. A support vector machine (SVM) process is run on every pair of clusters from all classes. Separation hyperplanes are determined for the clustered classes. Labels are determined for each cluster based on the separation by hyperplanes.

First claim

What is claimed is:

1 . A computer-implemented method for improving an efficiency of a computing device in generating a classifier engine for machine learning, the computer-implemented method comprising:
receiving a plurality of data points; applying a semi-supervised k-means process to a first set of data points of the plurality of data points and a second set of data points of the plurality of data points, wherein
the first set of data points is labeled with a first class of a plurality of classes and
the second set of data points is labeled with a second class of the plurality of classes, different from the first class;
clustering the first set of data points and the second set of data points into a first plurality of clusters and a second plurality of clusters, respectively, using the semi-supervised k-means process; constructing multi-polytopes for the first plurality of clusters and the second plurality of clusters; training, based on the constructing of the multi-polytopes, a plurality of support vector machine (SVM) classifiers, wherein each SVM classifier of the plurality of SVM classifiers is trained on a respective pair of clusters within the first plurality of clusters and the second plurality of clusters; determining, using the trained plurality of SVM classifiers, separation hyperplanes for the first plurality of clusters and the second plurality of clusters; and determining labels for each cluster of the first plurality of clusters and each cluster of the second plurality of clusters, based on the separation hyperplanes.

2 . The computer-implemented method of claim 1 , further comprising clustering positive classes of data points of the plurality of data points separately from negative classes of data points of the plurality of data points.

3 . The computer-implemented method of claim 1 , further comprising:
identifying information from one of the first plurality of clusters or the second plurality of clusters; and using the identified information as a constraint in determining remaining of the one of the first plurality of clusters or the second plurality of clusters.

4 . The computer-implemented method of claim 1 , further comprising:
determining misclassification measurements in the first plurality of clusters and the second plurality of clusters; and training the semi-supervised k-means process for improved clustering based on the misclassification measurements.

5 . The computer-implemented method of claim 1 , wherein the separation hyperplanes are non-linear boundaries between the respective pair of clusters.

6 . The computer-implemented method of claim 1 , wherein the semi-supervised k-means process is regularized.

7 . A computer program product for improving a computing efficiency of a computing device in generating a classifier engine for machine learning, the computer program product comprising:
one or more non-transitory computer readable storage media, and program instructions collectively stored on the one or more non-transitory computer readable storage media, the program instructions comprising:
receiving a plurality of data points;
applying a semi-supervised k-means process to a first set of data points of the plurality of data points and a second set of data points of the plurality of data points, wherein
the first set of data points is labeled with a first class of a plurality of classes, and
the second set of data points is labeled with a second class of the plurality of classes, different from the first class;

clustering the first set of data points and the second set of data points into a first plurality of clusters and a second plurality of clusters, respectively, using the semi-supervised k-means process;
constructing multi-polytopes for the first plurality of clusters and the second plurality of clusters;
training, based on the constructing of the multi-polytopes, a plurality of support vector machine (SVM) classifiers, wherein each SVM classifier of the plurality of SVM classifiers is trained on a respective pair of clusters within the first plurality of clusters and the second plurality of clusters;
determining, using the trained plurality of SVM classifiers, separation hyperplanes for the first plurality of clusters and the second plurality of clusters; and
determining labels for each cluster of the first plurality of clusters and each cluster of the second plurality of clusters, based on the separation hyperplanes.

8 . The computer program product of claim 7 , wherein the program instructions further comprise clustering positive classes of data points of the plurality of data points separately from negative classes of data points of the plurality of data points.

9 . The computer program product of claim 7 , wherein the program instructions further comprise:
identifying information from one of the first plurality of clusters or the second plurality of clusters; and using the identified information as a constraint in determining remaining of the one of the first plurality of clusters or the second plurality of clusters.

10 . The computer program product of claim 7 , wherein the program instructions further comprise:
determining misclassification measurements in the first plurality of clusters and the second plurality of clusters; and training the semi-supervised k-means process for improved clustering based on the misclassification measurements.

11 . The computer program product of claim 7 , wherein the separation hyperplanes are non-linear boundaries between the respective pair of clusters.

12 . The computer program product of claim 7 , wherein the semi-supervised k-means process is regularized.

13 . A computer server for improving computational efficiency in generating a classifier engine for machine learning, the computer server comprising:
a network connection; one or more computer readable storage media; a processor coupled to the network connection and coupled to the one or more computer readable storage media; and a computer program product comprising program instructions collectively stored on the one or more computer readable storage media, the program instructions comprising:
receiving a plurality of data points;
applying a semi-supervised k-means process to a first set of data points of the plurality of data points and a second set of data points of the plurality of data points, wherein
the first set of data points is labeled with a first class of a plurality of classes, and
the second set of data points is labeled with a second class of the plurality of classes, different from the first class;

clustering the first set of data points and the second set of data points into a first plurality of clusters and a second plurality of clusters, respectively, using the semi-supervised k-means process;
constructing multi-polytopes for the first plurality of clusters and the second plurality of clusters;
training, based on the constructing of the multi-polytopes, a plurality of support vector machine (SVM) classifiers, wherein each SVM classifier of the plurality of SVM classifiers is trained on a respective pair of clusters within the first plurality of clusters and the second plurality of clusters;
determining, using the trained plurality of SVM classifiers, separation hyperplanes for the first plurality of clusters and the second plurality of clusters; and
determining labels for each cluster of the first plurality of clusters and each cluster of the second plurality of clusters, based on the separation hyperplanes.

14 . The computer server of claim 13 , wherein the program instructions further comprise cluste

Assignees

• IBM

Inventors

• Phan Dzung Tien
• Nguyen Lam Minh
• Kalagnanam Jayant R
• Reddy Chandrasekhara K
• Jayaraman Srideepika

Classifications

• G06N20/10 Primary

  using kernel methods, e.g. support vector machines [SVM] · CPC title