Алгоритм построения разделяющей поверхности двух точечных множеств методом разбиения пространства на регулярную сетку

Abstract

В работе рассмотрен подход к решению задачи классификации данных двух точечных множеств на основе построения их разделяющей поверхности. Предлагается понятие гиперкуба, как расширение метода пространственного хеширования. Обобщенный подход к построению разделяющей поверхности двух точечных множеств заключается в разбиении пространства, занимаемого множествами на регулярную сетку с помощью метода пространственного хеширования, построения гиперкуба для полученной сетки и нахождения значений в ячейках гиперкуба методом проведения дискретизированных гиперпрямых для нахождения средней ячейки гиперкуба между двумя ячейками, принадлежащими разным классам. Наиболее вероятный класс для новых точек определяется знаком и модулем значения в той ячейке гиперкуба, в которой находится эта точка. Преимуществом предложенного подхода является простота вычислений и возможность расширения для данных произвольной размерности.

In our work the approach to solve classification problem by construction of separating surface for two point sets data is considered. The concept of hypercube as the extension of spatial hashing technique is proposed. Generalized approach to construct separating surface is splitting of the space, occupied by two point sets, into regular grid by the spatial hashing approach. Then we compute hypercube based on grid and find values in hypercube cells by drawing discrete hyperlines to find medial hypercube cell between two different classes cells. The most probable class for new points is defined by the sign and absolute value of the hypercube cell the point belongs to. The advantage of the approach proposed is computational and implementation simplicity and possibility of extending the algorithm to the data of arbitrary dimensionality.