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

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

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

Что такое хеш-функция?

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

Например, представьте функцию, которая принимает непустые строки, содержащие символы ASCII a-z, и сопоставляет их с их первым символом. С этой хеш-функцией есть серьезная проблема, которую мы обсудим позже, а пока давайте воспользуемся ею в качестве нашего примера. (Посмотрите, сможете ли вы определить проблему)

Мы видим, что существует множество возможных входов - фактически бесконечное число - и только 26 возможных выходов.

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

Общие свойства хэш-функций в интеллектуальном анализе данных

  • У них есть фиксированное и конечное количество возможных выходов, которое меньше количества возможных входов. Это имеет несколько значений. Во-первых, это означает, что несколько входов могут хешировать один и тот же выход (как «abc» и «apple» имеют букву «a» в нашем примере). Мы называем это столкновением . Во-вторых, это означает, что если бы вы хэшировали все свои данные и сохраняли количество хешей, вы, вероятно, сохраняли бы гораздо меньше информации, чем если бы вы сохранили количество элементов в наборе данных (в зависимости от ваших данных и какую хэш-функцию вы выберете). Например, подсчет того, сколько раз встречается каждое слово в книге, потребует гораздо больше памяти, чем отслеживание того, сколько слов в книге начинается с каждой буквы в алфавите.

… Несколько входов могут хешировать один и тот же выход. Мы называем это столкновением .

  • Большинство хеш-функций нельзя отменить. Для конкретных выходных данных невозможно определить, какие исходные входные данные привели к их созданию. В нашем примере, если бы нам сказали, что какой-то вход хешируется в выход «a», мы не сможем сказать, был ли этот вход «яблоком», «муравьедом», «abc» или какой-либо другой строкой, начинающейся с «А».
  • Хеш-функции детерминированы. Определенный ввод будет всегда генерировать один и тот же вывод. Это правило верно для хэш-функций независимо от дисциплины, в которой они используются.
  • Все выходные данные должны иметь равную вероятность появления. Это важно, потому что это влияет на способ возникновения столкновений. Обычно мы хотим, чтобы все входные данные имели равную вероятность столкновений. Как вы уже догадались, в нашем примере функции есть явный пробел. Вероятность появления вывода равна вероятности того, что строка начинается с этой конкретной буквы. Поскольку мы ничего не знаем о распределении входных строк, небезопасно предполагать, что все наши выходные данные будут иметь равную вероятность появления. Если, например, мы выбираем строки из английского словаря, то будет больше слов, начинающихся с «t», чем, например, слов, начинающихся с «x».

Обычно мы хотим, чтобы все входные данные имели равную вероятность столкновений.

Общие хеш-функции и альтернатива нашему примеру

Одна из очень распространенных хеш-функций - это Дайджест сообщения 5, или сокращенно MD5. Secure Hash Algorithms (SHA) - это довольно распространенное семейство хеш-функций. Но будьте очень осторожны: многие хеш-функции, включая MD5 и несколько функций SHA, оказались небезопасными для криптографического использования. Однако насчет интеллектуального анализа данных это не касается.

Чтобы исправить проблему неоднородности, которую мы наблюдали в нашем примере, мы могли бы просто использовать функцию MD5 и сохранить первые N цифр хеша MD5. Рассмотрение псевдокода для алгоритма MD5 показывает нам, что символы имеют равную вероятность появления в хэше, что удовлетворяет нашему условию единообразия. Чтобы настроить количество ожидаемых столкновений, мы можем просто выбрать другое значение N.

Какое ожидаемое количество столкновений?

Проверьте свои знания о хэш-функциях, попытавшись решить указанную ниже проблему.

Предположим:

  • Подбираем 20000 уникальных слов
  • Мы хэшируем их согласно методу, описанному выше, используя хеш MD5 и сохраняя первые N символов результирующей строки хеширования. Эти первые N символов становятся последней хеш-строкой, которую мы будем использовать.
  • Каково ожидаемое количество коллизий для хеш-строки, состоящей из всех нулей, при N = 1? N = 2? N = 5?
  • Почему мы можем избежать выбора N = 5?

Примечание. Хеши MD5 представляют собой буквенно-цифровые строки.

Что я могу делать с хеш-функциями?

Есть несколько действительно интересных приложений, о которых я напишу в будущем, в том числе фильтры Блума, хеширование с учетом местоположения и алгоритм PCY - усовершенствование алгоритма априори, о котором я писал в Интуиция, лежащая в основе Априорный алгоритм . Следите за этими сообщениями в будущем.

Вам нравится наука о данных / машинное обучение / интеллектуальный анализ данных? Есть ли что-нибудь особенное, о чем вы хотели бы, чтобы я писал? Дайте мне знать в комментариях ниже!