Using \(\epsilon \)-nets for Solving the Classification Problem

We propose a new approach for solving the classification problem, which is based on the using \(\epsilon \)-nets theory. It is showed that for separating two sets one can use their \(\epsilon \)-nets, which considerably reduce the complexity of the separating algorithm for large sets’ sizes. The necessary and sufficient conditions of separable \(\epsilon \)-nets of two sets are proved. The algorithm of building separable \(\epsilon \)-nets is proposed. The \(\epsilon \)-nets, constructed according to this algorithm, have size \(O(1/\varepsilon )\), which does not depended on the size of set. The set of possible values of \(\epsilon \) for \(\epsilon \)-nets of both sets is considered. The properties of this set and the theorem of its convergence are proved. The proposed algorithm of solving the classification problem using the \(\epsilon \)-nets has the same computational complexity as Support Vector Machine \(O(n\ln n)\) and its accuracy is comparable with SVM results.