Оценка информативности и отбор экземпляров на основе хэширования

Abstract

RU: Актуальность. Для сокращения размерности данных при построении диагностических и распознающих моделей возникает необходимость отбора наиболее информативных экземпляров, а также отбора наиболее информативных признаков. Затраты времени на отдельную реализацию данных процедур являются высокими вследствие итеративности и взаимосвязанности данных процедур. Цель. Цель работы – сокращение временных затрат на сокращение размерности данных путем создания метода отбора наиболее информативных экземпляров на основе хэширования. Метод. Предложен метод расчета весов для определения хэшей экземпляров, который детерминированным способом определяет веса признаков на основе их рангов, которые, в свою очередь, определяет с учетом числа равных разбиений диапазонов признаков, минимально достаточного для выделения кластеров на оси признака с приемлемой точностью. Это позволяет исключить необходимость итеративного перебора различных комбинаций признаков, определения случайных проекций признаков, а также решение итеративных оптимизационных задач поиска наилучшей проекции признаков, что существенно сокращает затраты времени на расчет весов, при этом обеспечивая локальную чувствительность хэша. Полученные хэши возможно использовать как для отбора экземпляров, так и для отбора признаков. Предложен метод определения индивидуальной и групповой значимости экземпляров выборки, в котором использует как меру сходства расстояния между хэшами экземпляров и по аналогии с методом потенциалов находит потенциалы, наводимые классами на каждый экземпляр, а на их основе определяет показатели значимости экземпляров, исходя из того, что экземпляр в пространстве признаков тем информативнее, чем меньше минимальная разность потенциалов классов, наводимых на экземпляр. Предложен метод определения оценок информативности признаков, который на основе нормирования весов, полученных при формировании хэшей, определяет показатели информативности признаков, отдавая предпочтение признакам с меньшим числом разбиений. Результаты. Проведено экспериментальное исследование, подтвердившее работоспособность предложенных методов при решении практических задач. Выводы. Разработанное математическое обеспечение может быть рекомендовано для решения задач сокращения размерности данных. UK: Актуальність. Для скорочення розмірності даних при побудові діагностичних і розпізнавальних моделей виникає необхідність відбору найбільш інформативних екземплярів, а також відбору найбільш інформативних ознак. Витрати часу на окрему реалізацію даних процедур є високими внаслідок ітеративності і взаємопов'язаності цих процедур. Мета. Мета роботи – скорочення витрат часу на скорочення розмірності даних шляхом створення методу відбору найбільш інформативних екземплярів на основі хешування. Метод. Запропоновано метод розрахунку ваг для визначення хешів екземплярів, який детермінованим способом визначає ваги ознак на основі їх рангів, які, у свою чергу, визначає з урахуванням кількості рівних розбиттів діапазонів ознак, мінімально достатньої для виділення кластерів на вісі ознаки з прийнятною точністю. Це дозволяє виключити необхідність ітеративного перебору різних комбінацій ознак, визначення випадкових проекцій ознак, а також вирішення ітеративних оптимізаційних задач пошуку найкращої проекції ознак, що істотно скорочує витрати часу на розрахунок ваг, при цьому забезпечуючи локальну чутливість хеша. Отримані хеші можливо використовувати як для відбору екземплярів, так і для відбору ознак. Запропоновано метод визначення індивідуальної та групової значимості екземплярів вибірки, що використовує як міру подібності відстань між хешами зразків і за аналогією з методом потенціалів знаходить потенціали, що наводяться класами на кожен екземпляр, а на їх основі визначає показники значущості екземплярів, виходячи з того, що екземпляр в просторі ознак тим інформативніше, чим менше мінімальна різниця потенціалів класів, що наводяться на екземпляр. Запропоновано метод визначення оцінок інформативності ознак, який на основі нормування ваг, отриманих при формуванні хешів, визначає показники інформативності ознак, віддаючи перевагу ознаками з меншою кількістю розбиттів. Результати. Проведено експериментальне дослідження, яке підтвердило працездатність запропонованих методів при вирішенні практичних завдань. Висновки. Розроблене математичне забезпечення може бути рекомендовано для вирішення завдань скорочення розмірності даних. EN: Context. To reduce the data dimensionality in the diagnostic and recognition model construction, it becomes necessary to select the most informative instances, as well as to select the most informative features. The time spent on the separate implementation of these procedures is high due to the iterativity and interconnectedness of these procedures. Objective. The purpose of this work is to reduce the time spent on reducing the data dimensionality by creating a method for selecting the most informative instances based on hashing. Method. A method for calculating weights for determining the hashes of instances is proposed, which determines the weights of features based on their ranks in a deterministic way, which, in turn, determines, taking into account the number of equal partitions of the ranges of features, the minimum sufficient to distinguish clusters on the axis of the feature with acceptable accuracy. This eliminates the need for iterative enumeration of various combinations of features, determining random projections of features, as well as solving iterative optimization problems of finding the best projection of features, which significantly reduces the time spent on calculating weights, while ensuring the local sensitivity of the hash. The hashes obtained can be used both for the selection of instances and for the selection of features. A method for determining the individual and group significance of sample instances is proposed, in which it uses the distance between the hashes of the instances as a measure of similarity and, by analogy with the potential method, finds the potentials induced by the classes for each instance, and on their basis determines the indicators of the significance of the instances, based on the fact that the instance in the feature space, the more informative the less the minimum potential difference of the classes induced on the specimen. A method for determining the estimates of the informativeness of features is proposed, which, on the basis of normalizing the weights obtained during the formation of hashes, determines the indicators of the informativeness of features, giving preference to features with a smaller number of partitions. Results. An experimental study has been carried out, which has confirmed the efficiency of the proposed methods in solving practical problems. Conclusions. The developed software can be recommended for solving problems of data dimension reduction.