Сигнатура точечного множества и алгоритм классификации на её основе

Abstract

На данный момент существует большое количество задач по автоматизированной обработке многомерных данных, например, классификация, кластеризация, прогнозирование, задачи управления сложными объектами. Соответственно, возникает необходимость в развитии математического и алгоритмического обеспечения для решения возникающих задач. Целью исследования является развитие алгоритмов классификации точечных множеств на основе их пространственного распределения. В работе предлагается рассматривать данные как точки в многомерном метрическом пространстве. В работе рассмотрены подходы к описанию характеристик точечных множеств в пространствах высокой размерности и предлагается подход к описанию точечного множества на основе сигнатур, которые представляют собой характеристику заполненности точечного множества на основе расширения понятия пространственного хеширования. Обобщенный подход к вычислению сигнатур точечных множеств заключается в разбиении пространства, занимаемого множеством на регулярную сетку с помощью метода пространственного хеширования, вычисления геометрических характеристик множества в полученных ячейках и определения наиболее заполненных ячеек по каждому из пространственных измерений. Предлагается новый подход к классификации на основе сигнатур множества, который заключается в нахождении сигнатур для точек с известным значением принадлежности к некоторым классам, а для новых точек вычисляется расстояние от хеша точки до сигнатуры каждого из известных множеств, на основе чего определяется наиболее вероятный класс точки. В качестве используемых метрик предлагаются Евклидово расстояние и метрика городских кварталов. В работе проведён сравнительный анализ используемых метрик с точки зрения точности классификации. Преимуществами предложенного подхода являются простота вычислений и высокая степень точности классификации для равномерно распределенных точек. Представленный алгоритм реализован в виде программного приложения на языке Python с использованием библиотеки NumPy. Также рассмотрены варианты использования предложенного подхода для задач с не числовыми данными, такими как строковые и булевы значения. Для таких данных предложено использовать метрику Хэмминга, проведённые эксперименты показали работоспособность алгоритма для таких типов данных.

There are many unsolved problems in the field of automatic multi-dimensional data processing, for example, classification, clustering, regression, and control of complex objects. This leads to the need of development of mathematical and algorithmical background for such problems. In our research we aim to development of classification algorithms of point sets based on their spatial distribution. We propose to consider data as points in multi-dimensional metric space. The approaches to describe point set features in high dimensional spaces are viewed. The algorithm of describing of point set based on their signatures, that are spatial distribution of point set is considered. In our approach we extend spatial hashing technique. The generalized method of computation of point set signatures is to split space, occupied by point set into regular grid by the spatial hashing algorithm, then we evaluate geometrical characteristics of the set in cells of the grid and define cells, that contain most of the points for the all of coordinate axis. The new approach to classification by means of point set signatures is developed that is to find signatures of known points with the classes defined and then we compute spatial hashes for unknown points and their distance to the signatures of classes. The probable class of the tested point is defined by the minimal distance among all distances to each signature. To define distance in our approach we use Manhattan and Euclidean metric. The comparative study of impact of metrics used to the classification error is provided. The main advantage of our method is computation simplicity and low classification error for evenly distributed points. Prototype implementation of our algorithm was written in order to test this algorithm for practical classification applications. The implementation was coded in Python with use NumPy library. The use of our algorithm to the classification of non-numerical data such as texts and booleans is viewed. For such data types we propose use of Hamming distance and experiments done show practical viability for such data types.