Convex Polyhedron Classifier Based On Geometric Nearest Point Algorithm

In pattern classification problems,geometric methods often provide simple and intuitive solutions.A typical schema is support vector machine,Which solves the optimal hyperplane problem in the feature space can be expressed by geometric duality theory.That is,It solvs the optimal hyperplane problem can be transformed into the nearest point problem between two convex hulls of classes in the case of linear separability.Based on the review on the classic nearest point algorithms,this paper proposes several new theories and algorithms to solve the classification problem in pattern recognition.The main research work includes the following two aspects:(1)A method for determining the position relationship between a point and a convex hull is proposed,which is based on a nearest point algorithmDetermination of the position relationship between a point and a convex hull in high-dimensional space is an important research topic in the field of pattern classification.Existing determination methods usually have a relatively high computational cost.From the perspective of machine learning,this paper proposes a new Point in Convex Hull Determination(Abbr.PinCHD)algorithm.The PinCHD algorithm constructs a separating hyperplane by calculating a nearest point pair between the given point and the convex hull.If the point and convex hull are located on both sides of the hyperplane,it can be determined that the point is outside the convex hull.If the point and the convex hull are on the same side of the hyperplane,the point is determined to be within the convex hull.The advantage of PinCHD is that it does not directly calculate the convex hull of the high-dimensional point set,but directly determines the position relationship between the point and the convex hull through the nearest point algorithm.Compared with the existing convex hull methods in computational geometry,the PinCHD algorithm is simper and more intuitive,and has a lower computational cost.(2)A new convex polyhedron classifier is proposed to solve the pattern classification problemBased on the PinCHD algorithm,a new convex polyhedron classifier is proposed.If the two sample sets are convexly separable,a classifier can be constructed through the combination of hyperplanes.The classifier encloses one class of samples in a convex polyhedron and excludes the other class.The convex polyhedron classifier has the potential to deal with imbalanced classification problems,since it can realize accurate identification of the minority class of samples.In addition,it has the advantages of simple integration,easy implementation,and rapid prediction response time,making it suitable for portable devices and real-time systems.Experiments on benchmark data sets show that the convex polyhedron classifier performs better than the existing piecewise linear classifiers.The comparison evaluation with several types of support vector machines also illustrates the effectiveness and competitiveness of the proposed classifier.