Проверяем уникальность выборок в методе бустрепа при помощи хешей

Антон Лях — Thu, 29 Jun 2023 12:03:20 +0300

Где-то в крымском лесу

Это продолжение серии заметок об анализе биологических данных.

Сегодня рассмотрим частную задачу, которая может возникнуть при использования метода бустрепа.

Дано множество объектов. Необходимо случайным образом составить из них неповторяющиеся выборки. Задача заключается в проверке уникальности каждой выборки. Для этого используем хеш.

Бутстреп

Метод бустрепа предполагает, что из множества исходных данных мы создаем случайную выборку и вычисляем по ней некоторые статистические величины: среднее, дисперсию и тому подобные. Затем мы создаем новую случайную выборку, вычисляем новые величины и так продолжаем очень много раз. В результате по полученным значениям мы оцениваем реальные статистические величины. Достоверность оценок как раз достигается за счет многократного выбора.

Немного о бустрепе.

Уникальные выборки

В классическом бустреп-анализе могут повторяться как сами выборки, так и элементы в каждой выборке. Но в данной случае нам нужно создать совокупность уникальных выброк. Для проверки уникальности каждой выборки используем хеш.

Хеш — это математическое преобразование, переводящее произвольный входной массив данных в строку фиксированной длины, состоящую из букв и цифр. Хеш считается хорошим, если он устойчив к колизиям — это когда невозможно получить из различных входных последовательностей одинаковые хеши.
Group-IB: Хеш четкий и хеш нечеткий.

Хеш

Для создания хеша объединим все элементы выборки (их значения, идентификаторы или названия) в одну строку и вычислим хеш строки. Затем проверим, встречался ли такой хеш ранее (в массиве сохраненных хешей). Если его там нет, значит выборка уникальная.

Вот как можно составить строку для хеширования из данных.

Если данные — это символы, например названия, тогда объединяем их в одну строку:
’ellipse’ + ’convex’ + ’square’ + ’curve’ → ’ellipseconvessquarecurve’.
Если данные — это числа, то считаем их строками и тоже объединяем в одну строку:
17.5 + 21.1 + 33.333 + 77.00098 + 1 + 0.008 → ’17.521.133.33377.0009810.008’

Алгоритмов хеширования много. Среди них наиболее распространены: MD5, SHA-1, SHA-2, SHA-256. Используйте любой.

Вот хеши SHA-256 двух вышенаписанных строк:

ellipseconvessquarecurve → 6d80b7d933b69b974189bd2a61b90a05f050c62afa055fb5a033f36114d360a2
17.521.133.33377.0009810.008 → d1a728197a46f18060a0c2533938c881b0d48e8e65358f21f1d86dd0f5f1612b

Успехов в анализе данных.

Математик среди биологов: заметки с тегом SHA-256

Проверяем уникальность выборок в методе бустрепа при помощи хешей

Бутстреп

Уникальные выборки

Хеш