Хэширование на основе полярных координат для сокращения размерности данных

Abstract

RU: Актуальность. Для сокращения размерности данных в задачах распознавания и диагностирования на основе хэширования возникает необходимость сокращение временных затрат на формирование хэширующего преобразования. Цель. Цель работы – уменьшение временных затрат на сокращение размерности данных путем создания метода хэширования, не требующего решения оптимизационной задачи поиска наилучшего случайного преобразования, а также уменьшение потерь локальных свойств признакового пространства. Метод. Предложен метод формирования хэша, который переводит координаты экземпляров из исходной системы признаков в многомерную полярную систему координат, на основе которых, дискретизируя полярные координаты, с помощью эвристик различным способами кодирует и комбинирует значения дискретизированных полярных координат, формируя хэши экземпляров, из которых в качестве результирующего преобразования выбирает наилучшее в системе заданных критериев на основе минимизации числа коллизий, при которых экземпляры разных классов и разными значениями исходных признаков, получают одинаковые хэши. Это позволяет автоматизировать формирование хэширующих преобразований, исключить необходимость решения оптимизационных задач перебора случайных проекций, обеспечив сокращение затрат времени, а также делает хэширующее преобразование более свободным от навязывания данным разбиения признакового пространства, неприсущей им природы, что позволяет повысить обобщающие свойства и точность преобразований. Предложены критерии оценивания качества хэширующих преобразований, включающие определение числа позитивных и негативных коллизий, а также оценивания на их основе вероятностей соответствующих коллизий. Это позволяет автоматизировать анализ и выбор хэширующих преобразований для сокращения размерности данных в задачах распознавания и диагностирования. Результаты. Проведено экспериментальное исследование, подтвердившее работоспособность предложенных методов при решении практических задач. Выводы. Разработанное математическое обеспечение может быть рекомендовано для решения задач сокращения размерности данных. UK: Актуальність. Для скорочення розмірності даних в задачах розпізнавання та діагностування на основі гешування виникає необхідність скорочення витрат часу на формування гешувального перетворення. Мета. Мета роботи – зменшення витрат часу на скорочення розмірності даних шляхом створення методу гешування, що не потребує вирішення оптимізаційної задачі пошуку найкращого випадкового перетворення, а також зменшення втрат локальних властивостей простору ознак. Метод. Запропоновано метод формування гешу, який переводить координати екземплярів з вихідної системи ознак у багатовимірну полярну систему координат, на основі яких, дискретизуючи полярні координати, за допомогою евристик різним способами кодує і комбінує значення дискретизованих полярних координат, формуючи геші екземплярів, з яких в якості результуючого перетворення вибирає найкраще у системі заданих критеріїв на основі мінімізації кількості колізій, при яких екземпляри різних класів і різних значеннях вихідних ознак, отримують однакові геши. Це дозволяє автоматизувати формування гешувальних перетворень, виключити необхідність вирішення оптимізаційних задач перебору випадкових проекцій, забезпечивши скорочення витрат часу, а також робить гешувальне перетворення більш вільним від нав'язування даним розбиття простору ознак, непритаманної їм природи, що дозволяє підвищити узагальнюючі властивості і точність перетворень. Запропоновано критерії оцінювання якості гешувальних перетворень, що містять визначення кількостей позитивних і негативних колізій, а також оцінювання на їхній основі ймовірностей відповідних колізій. Це дозволяє автоматизувати аналіз і вибір гешувальних перетворень для скорочення розмірності даних в задачах розпізнавання та діагностування. Результати. Проведено експериментальне дослідження, яке підтвердило працездатність запропонованих методів при вирішенні практичних завдань. Висновки. Розроблене математичне забезпечення може бути рекомендовано для вирішення завдань скорочення раз-мірності даних. EN: Context. To reduce the data dimensionality of in recognition and diagnostics problems based on hashing, it becomes necessary to reduce the time spent on generating a hashing transformation. Objective. The purpose of the work is to reduce the time spent on reducing the dimension of data by creating a hashing method that does not require solving the optimization problem of finding the best random transformation, as well as reducing the loss of local properties of the feature space. Method. A hash generation method is proposed. It converts the instance coordinates from the original feature system into a multidimensional polar coordinate system, on which basis discretize polar coordinates using heuristics, in various ways encodes and combines the values of the discretized polar coordinates, forming hashes of instances, from which as the resulting transformation selects the best one in the system of given criteria based on minimizing the number of collisions in which instances of different classes and different values of the original features receive the same hashes. This makes possible to automate the formation of hashing transformations, eliminate the need to solve optimization problems of enumerating random projections, ensuring a reduction in time consumption, and also makes the hashing transformation freer from imposing the data on the partitioning of the feature space, of a non-inherent nature, which allows increase the generalizing properties and accuracy of transformations. Criteria for evaluating the quality of hashing transformations are proposed, including determining the number of positive and negative collisions, as well as evaluating the probabilities of the corresponding collisions on their basis. This makes it possible to automate the analysis and selection of hashing transformations to reduce the dimension of the data in the problems of recognition and diagnosis. Results. An experimental study has been carried out, which has confirmed the efficiency of the proposed methods in solving practical problems. Conclusions. The developed mathematical support can be recommended for solving problems of data dimension reduction.