Алгоритм построения разделимых ε-сетей двух множеств

Abstract

Предложен новый метод решения задачи классификации, основанный на разделении двух множеств в пространстве Rᵈ. Доказаны необходимые и достаточные условия ε-разделимости. Сформулирован алгоритм построения разделимых ε-сетей двух множеств размера [ 2d/ε ]. Рассмотрен пример использования данного алгоритма для двух множеств, сгенерированных из нормально распределенных совокупностей. Результаты классификации предложенного метода сравниваются с результатами классификации по методу опорных векторов.

Запропоновано новий метод розв’язання задачі класифікації, що базується на відокремленні двох множин у просторі Rᵈ. Доведено необхідні і достатні умови ε-відокремлюваності. Сформульований алгоритм побудови відокремлюваних ε--сіток двох множин розміром [ 2d/ε ]. Розглянуто приклад використання цього алгоритму для двох множин, згенерованих з нормально розподілених сукупностей. Результати класифікації запропонованого методу порівняні з результатами класифікації за методом опорних векторів.

The authors propose a new method to solve classification problem based on separation of two sets in space Rᵈ. The necessary and sufficient conditions of ε-separability are proved. The algorithm of constructing two separable ε-nets of size [2d/ε]is proposed. The paper contains an example of applying this algorithm to two sets generated from normally distributed sets. The classification results for the proposed method and for support vector machines are compared.