Keywords

1 Introduction

Algorithms of k-nearest neighbors (kNN) [1] due to their simplicity and efficiency are successfully used in many multiclass problems of pattern recognition and image analysis. The kNN rule is that it assigns a test object to the most common class among its k nearest neighbors. Despite the great success achieved in many applied problems, its application is limited by the well-known drawbacks: the limitation of the dimension of the feature space and the number of objects in the training set. For kNN, the problems of the influence of noise and small training sets remain.

Another well-known method in machine learning is the support vector machines (SVM) [2]. Designed for binary classification, it is widely used in all kinds of pattern recognition problems. SVM is highly generalizable and handles high-dimensional data easily. However, it does not directly solve multiclass problems.

In this paper, we consider the nearest convex hull (NCH) classifier, which is conceptually related to both kNN and SVM. NCH is an intuitive geometric classification method that assigns a test point to the class whose convex hull is closest to it. The useful properties of NCH are:

  1. 1.

    NCH classifies multi-class problems easily in a straightforward way.

  2. 2.

    NCH is well suited for biometrics problems with a large number of classes and small volumes of learning samples by class: problems of recognizing people by faces [7] or fingerprints.

  3. 3.

    Since, NCH is resistant to the problems of small learning samples and noise, since the elimination of one point of an element of the convex set does not affect or only locally affects the entire convex hull.

This article is organized as follows. First, we give a definition of a convex hull, then a classifier is formulated based on the description of classes in the form of convex hulls in general, approaches to determining the proximity of a test point to the convex hull of a class are given, which are used in classification algorithms for the nearest convex hull. These approaches include: the SVM-based method used in [3], the Lightweight nearest convex hull method (LNCH), based on calculating the projection of the class onto the direction from the test point to the centroid of the class [4] and the method [6] based on the application of linear programming [5]. All of the above approaches provide only an approximate estimate of the proximity parameter. At the end of the article, a classification algorithm based on the use of linear programming is described, the results of experimental studies are given, and a conclusion is formulated, thanks and a list of references are given.

2 The Definition of a Classifier Based on the Convex Hull Representation of Classes

Let the learning set of one class have the form \( \text{X} = \{ {\mathbf{x}}_{i} ,\,\,{\mathbf{x}}_{i} \in R^{n} ,\;\,i = 1,2, \ldots ,k\} \). Then the convex hull generated by this set is defined as

$$ conv\,(\text{X} ) = \left\{ {{\mathbf{v}}:{\mathbf{v}} = \sum\limits_{i = 1}^{k} {a_{i} {\mathbf{x}}_{i} ,\quad 0 \le a_{i} ,\quad \sum\limits_{i = 1}^{k} {a_{i} = 1,\quad {\mathbf{x}}_{i} \in X} } } \right\} $$

where \( a_{i} \) - are scalar non-negative coefficients. For \( m \) classes, we have \( m \) sets of \( \text{X}_{i} ,\,i = 1,2, \ldots ,m \) and, accordingly, \( m \) convex hulls \( conv\left( {\text{X}_{i} } \right),\;i = 1,2, \ldots ,m \). The simplest classifier for an arbitrary requested point \( {\mathbf{x}} \) will use the following rule.

Rule A:

If \( {\mathbf{x}} \) is inside \( conv\left( {\text{X}_{p} } \right) \), then it belongs to class \( p \), otherwise it belongs to another class or its affiliation is undefined.

Leaving aside the question of how to determine the location of \( {\mathbf{x}} \) “inside \( conv\left( {\text{X}_{p} } \right) \)”, you need to decide what to do if \( {\mathbf{x}} \) is inside several convex hulls at the same time (the case of their intersection) or \( {\mathbf{x}} \) is not in any convex hull. In these cases, a way out can be found by introducing the concept of the distance from \( {\mathbf{x}} \) to the convex hull of the i-th class \( d_{i} \left( {{\mathbf{x}},conv(\text{X}_{i} )} \right) \). Then the classification algorithm can be formulated as follows.

Rule B

  • If \( {\mathbf{x}} \) is inside only one convex hull \( conv\left( {\text{X}_{p} } \right) \), then it belongs to class \( p \).

  • If \( {\mathbf{x}} \) is outside the convex hulls of all classes, then it belongs to the class i, distance \( d_{i} \left( {{\mathbf{x}},conv(\text{X}_{i} )} \right) \) to which is less.

  • If \( {\mathbf{x}} \) is inside several convex hulls, then its membership is undefined.

In this case, two points present difficulties. It is necessary to determine how to check the location of the test vector \( {\mathbf{x}} \): inside \( conv\left( \text{X} \right) \) or outside it. In addition, it is necessary to remove the uncertainty of the membership of the vector \( {\mathbf{x}} \) in the case when it enters into two or more convex hulls.

3 Determining the Distance from the Test Point to the Convex Hull

If \( {\mathbf{x}} \) is not inside \( conv\left( \text{X} \right) \), the minimum distance \( d\left( {{\mathbf{x}},\,conv(\text{X} )} \right) \) can be determined as in [3], using the support vector machines (SVM). In the case when \( {\mathbf{x}} \) is inside \( conv\left( \text{X} \right) \), the SVM method does not give an exact solution due to the dependence of the obtained weight vector on classification errors.

In papers [4, 6], approaches to the approximate definition of \( d\left( {{\mathbf{x}},\,conv(\text{X} )} \right) \) are proposed regardless of the location of the test point.

3.1 Lite Distance Determination Method

The paper [4] describes a lightweight method for determining the distance regardless of the location of \( {\mathbf{x}} \) in relation to \( conv\left( \text{X} \right) \). For data \( {\mathbf{x}} \) and \( conv\left( \text{X} \right) \), the method consists in analyzing the projections of nodes \( conv\left( \text{X} \right) \) onto the unit vector u, directed from test point \( {\mathbf{x}} \) to centroid \( {\mathbf{c}} \) of class X, i.e. \( {\mathbf{u}} = {{\left( {{\mathbf{c}} - {\mathbf{x}}} \right)} \mathord{\left/ {\vphantom {{\left( {{\mathbf{c}} - {\mathbf{x}}} \right)} {norm\left( {{\mathbf{c}} - {\mathbf{x}}} \right)}}} \right. \kern-0pt} {norm\left( {{\mathbf{c}} - {\mathbf{x}}} \right)}} \). The analysis is carried out by the following algorithm.

figure a

As a result of executing this algorithm for a given test point and m classes we obtain m pairs \( (\text{F}_{i} ,\,\,d_{i} ),\;i = 1,2, \ldots ,m \), where \( \text{F}_{i} \) – is the i-th class intersection mark with \( {\mathbf{x}} \) (\( \text{F}_{i} \) = 0, if \( {\mathbf{x}} \) is outside \( conv\left( {\text{X}_{i} } \right) \), and \( \text{F}_{i} \) = 1, if \( {\mathbf{x}} \) is inside \( conv\left( {\text{X}_{i} } \right) \)), \( d_{i} \) - parameter of distance to \( conv\left( {\text{X}_{i} } \right) \). Further, the following rule is used for classification.

Rule B

  • If \( {\mathbf{x}} \) is inside only one convex hull \( conv\left( \text{X} \right) \), then it belongs to this class,

  • otherwise, if it is inside several convex hulls, then it belongs to the class into which it entered most deeply, i.e. for which \( d\left( {{\mathbf{x}},\,conv(\text{X} )} \right) \) is maximum,

  • otherwise (\( {\mathbf{x}} \) is outside the convex hulls of all classes) it belongs to the class for which \( d\left( {{\mathbf{x}},\,conv(\text{X} )} \right) \) is minimal

3.2 A Method Based on Linear Programming

In paper [5], the optimal solution \( z^{ * } \) of the following LP1 linear programming problem was considered. Given set \( \text{X} = \{ {\mathbf{x}}_{i} ,\,\,{\mathbf{x}}_{i} \in R^{n} ,\;\,i = 1,2, \ldots ,m\} \) and point \( {\mathbf{b}} \in \text{R}^{n} \), and the origin must be inside conv(X) (P = conv(X)).

$$ \begin{array}{*{20}l} {\text{LP1}} \hfill \\ {z = \hbox{min} \sum\limits_{i = 1}^{m} {\lambda_{i} } } \hfill \\ {\text{Provided that}} \hfill \\ {\sum\limits_{i = 1}^{m} {\lambda_{i} {\mathbf{x}}_{i} } = {\mathbf{b}},} \hfill \\ {\lambda_{i} \ge 0,\,i = 1, \ldots ,m,} \hfill \\ \end{array} $$

where b is an arbitrary nonzero vector.

For this problem, the following statement was formulated and proved [5].

If \( z^{ * } \) is an optimal solution to LP1 problem for some \( {\mathbf{b}} \ne 0 \), then

  1. 1.

    \( z^{ * } < 1 \), if and only if b is inside P

  2. 2.

    \( z^{ * } = 1 \), if and only if b is on the boundary of P

  3. 3.

    \( z^{ * } > 1 \), if and only if b is outside P

This can be illustrated with the help of Fig. 1. The above statement creates the prerequisites both for determining that the vector x is inside the convex hull and for estimating the proximity of a given point to the convex hull of the class based on solving a linear programming problem [6]. Theoretical considerations and experiments show that the ratio of the distance from a point to the convex hull D (along the ray from the origin to the test point b) to the length of the vector b is equal to the ratio |z* − 1| to z*. That is, it is true regardless of the location of the test point (F = 1 or F = 0)

Fig. 1.
figure 1

The figure shows: a set of points X in a multidimensional space, P is a convex hull, c is the origin, b1, b2, b3 are test points (vectors), z* are the optimal values of the objective function z for these points (examples).

Full size image
$$ \frac{\text{D}}{{\left\| {\mathbf{b}} \right\|}} = \frac{{\left| {z^{ * } - 1} \right|}}{{z^{ * } }} $$

whence follows

$$ {\text{D}} = \left\| {\mathbf{b}} \right\| \cdot \left| {z^{ * } - 1} \right|/z^{ * } $$

Since the ray used is not perpendicular to the facet it “pierces”, the determined distance D is an approximation of the true distance to the convex hull. In order to increase the accuracy of such approximation, it is advisable to align the origin of coordinates with the centroid of the set X before measuring.

4 The Nearest Convex Hull Algorithm Based on the Linear Programming Method

The principle of measuring the distance from the tested (test) point \( {\mathbf{x}} \) to the convex hull described above can be used to construct a multi-class classifier of the nearest convex hull. Before solving the LP1 problem for each class of points \( \text{X}_{i} \), it is necessary to place the origin at the centroid point of this class. After finding the optimal solution to LP1 problem, we introduce a label F, which shows the location of \( {\mathbf{x}} \): inside or outside the given convex hull. F = 0 if \( z^{ * } \ge 1 \) (point outside or on the boundary of the convex hull), and F = 1 if \( z^{ * } < 1 \) (point inside the convex hull). Then for a given \( {\mathbf{x}} \) and \( \text{X}_{i} \) we get a pair (F, \( \text{D}_{i} \)).

For a given \( {\mathbf{x}} \) and m classes \( \text{X}_{i} ,\,i = 1,2, \ldots ,m \) we get m pairs \( (\text{F}_{i} ,\,D_{i} ),\;i = 1,2, \ldots ,m \). Further, the classification is carried out according to the following decision rule.

  1. 1.

    If no pair contains F = 1, then the number of the recognized class is given by formula \( class\left( {\mathbf{x}} \right) = \;\mathop {\arg \hbox{min} }\limits_{i = 1,2, \ldots m} d_{i} \left( {{\mathbf{x}},\,conv(\text{X}_{i} )} \right) \).

  2. 2.

    If only one pair contains F = 1, then the number of the recognized class is equal to the index of this pair.

  3. 3.

    If several pairs (possibly all) contain F = 1 and the indices of these pairs form a set G, then the number of the recognized class is chosen from these classes so that \( class\left( {\mathbf{x}} \right) = \;\mathop {\arg \hbox{max} }\limits_{i \in G} d_{i} \left( {{\mathbf{x}},\,conv(\text{X}_{i} )} \right) \). The penetration of the test point into this class turns out to be the greatest.

As a description of classes, it is better to use not the original sets \( \text{X}_{i} \), but only the vertices of their convex hulls. To do this, it is necessary to calculate the set of vertices of the convex hulls of the classes from the initial learning set. This is an easier task. This significantly reduces the running time of the linear programming algorithm. Using the vertex list at the learning stage makes it more accurate to determine the center of the convex hull, which can affect the accuracy of determining the distance D.

5 Experimental Research

The described algorithm for the classification of the nearest convex hull using linear programming was tested on a two-class problem of medical diagnostics of breast cancer [8]. A sample of 683 people was used (444 cases of healthy and 239 cases of sick). To form the control sample, the classes were divided in half. Convex hulls were constructed from the first halves of the samples. The second half of the samples were used as test samples. The average classification error on test samples was 2.15%, which is better than the same indicator when solving this problem with other classification algorithms [6].

6 Conclusion

This paper discusses approaches to pattern recognition algorithms based on the representation of classes as convex hulls in a multidimensional feature space. For classification algorithms based on the nearest convex hull, different approaches to assessing the proximity of a test point to a convex hull are considered: based on the analysis of the directed penetration depth and based on the use of linear programming. Both approaches estimate the distance from the test point to the convex hull along the ray from the class centroid to the test point. As shown by the results of experiments, the method using linear programming is characterized by high recognition quality. It is easy to implement, does not require any parameter setting, and can be easily used to solve multiclass problems, especially biometrics problems with a large number of classes and small volumes of learning samples by class.