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

Анотація

На даний момент існує велика кількість задач з автоматизованої обробки багатовимірних даних, наприклад, класифікація, кластеризація, прогнозування, задачі з керування складними об’єктами. Відповідно, виникає необхідність в розвитку математичного та алгоритмічного забезпечення для розв’язання таких задач. Метою дослідження є розвиток алгоритмів класифікації точкових множин на основі їх просторового розподілу. В дослідженні пропонується розглядати дані як точки в багатовимірному метричному просторі. В роботі розглянуто підходи до опису характеристик точкових множин в просторах високої розмірності та пропонується підхід до опису точкової множини на основі сигнатур, які представляють характеристику заповненості точкової множини на основі розширення поняття просторового хешування. Узагальнений підхід до обчислення сигнатур точкових множин полягає в розбитті простору, що займає множина на регулярну сітку з використанням методу просторового хешування, обчислення геометричних характеристик множини в отриманих клітинах сітки та визначення найбільш заповнених клітин за кожним з просторових вимірів. Пропонується новий підхід до розв’язання задачі класифікації на основі сигнатур множин, який полягає в визначенні сигнатур для точок з відомою належністю до заданих класів, а для невідомих точок обчислюється відстань від хешу цієї точки до сигнатур усіх заданих класів, на основі відстані визначається найбільш вірогідний клас точки. В якості метрик пропонується використання Евклідової відстані та метрики міських кварталів. У роботі проведений порівняльний аналіз використаних метрик з точки зору точності класифікації. До переваг розробленого підходу можна віднести простоту обчислень та високий ступінь точності класифікації для рівномірно розподілених точок. Представлений алгоритм реалізовано у вигляді програмного додатку на мові програмування Python з використанням бібліотеки NumPy. Також розглянуто варіанти використання запропонованого підходу для задач з нечисловими даними, такими як текстові та булеві значення. Для таких типів даних запропоновано використання метрики Геммінга, проведені експерименті показали доцільність використання алгоритму для таких типів даних