Что такое хеширование (трюк)?

Question

Я знаю, что хеширование объектов (трюк хеширования) используется для уменьшения размерности и обработки разреженности битовых векторов, но я не понимаю, как это работает на самом деле.Может кто-нибудь объяснить это мне. Есть ли какая-нибудь библиотека Python для хеширования функций?

Спасибо.

Answer 1

На Пандах вы можете использовать что-то вроде этого:

import pandas as pd
import numpy as np

data = {'state': ['Ohio', 'Ohio', 'Ohio', 'Nevada', 'Nevada'],
        'year': [2000, 2001, 2002, 2001, 2002],
        'pop': [1.5, 1.7, 3.6, 2.4, 2.9]}

data = pd.DataFrame(data)

def hash_col(df, col, N):
    cols = [col + "_" + str(i) for i in range(N)]
    def xform(x): tmp = [0 for i in range(N)]; tmp[hash(x) % N] = 1; return pd.Series(tmp,index=cols)
    df[cols] = df[col].apply(xform)
    return df.drop(col,axis=1)

print hash_col(data, 'state',4)

Выход будет

   pop  year  state_0  state_1  state_2  state_3
0  1.5  2000        0        1        0        0
1  1.7  2001        0        1        0        0
2  3.6  2002        0        1        0        0
3  2.4  2001        0        0        0        1
4  2.9  2002        0        0        0        1

Также на уровне Серии вы можете

импортировать numpyкак np, os import sys, pandas как pd

def hash_col(df, col, N):
    df = df.replace('',np.nan)
    cols = [col + "_" + str(i) for i in range(N)]
    tmp = [0 for i in range(N)]
    tmp[hash(df.ix[col]) % N] = 1
    res = df.append(pd.Series(tmp,index=cols))
    return res.drop(col)

a = pd.Series(['new york',30,''],index=['city','age','test'])
b = pd.Series(['boston',30,''],index=['city','age','test'])

print hash_col(a,'city',10)
print hash_col(b,'city',10)

Это будет работать для каждой серии, имя столбца будет считаться индексом Pandas.Он также заменяет пустые строки на nan и плавает все.

age        30
test      NaN
city_0      0
city_1      0
city_2      0
city_3      0
city_4      0
city_5      0
city_6      0
city_7      1
city_8      0
city_9      0
dtype: object
age        30
test      NaN
city_0      0
city_1      0
city_2      0
city_3      0
city_4      0
city_5      1
city_6      0
city_7      0
city_8      0
city_9      0
dtype: object

Если, однако, есть словарь, и вы просто хотите кодировать в горячем режиме, вы можете использовать

import numpy as np
import pandas as pd, os
import scipy.sparse as sps

def hash_col(df, col, vocab):
    cols = [col + "=" + str(v) for v in vocab]
    def xform(x): tmp = [0 for i in range(len(vocab))]; tmp[vocab.index(x)] = 1; return pd.Series(tmp,index=cols)
    df[cols] = df[col].apply(xform)
    return df.drop(col,axis=1)

data = {'state': ['Ohio', 'Ohio', 'Ohio', 'Nevada', 'Nevada'],
        'year': [2000, 2001, 2002, 2001, 2002],
        'pop': [1.5, 1.7, 3.6, 2.4, 2.9]}

df = pd.DataFrame(data)

df2 = hash_col(df, 'state', ['Ohio','Nevada'])

print sps.csr_matrix(df2)

, который даст

   pop  year  state=Ohio  state=Nevada
0  1.5  2000           1             0
1  1.7  2001           1             0
2  3.6  2002           1             0
3  2.4  2001           0             1
4  2.9  2002           0             1

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

Answer 2

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

Answer 3

Большая разреженная функция может быть получена из взаимодействия, U как пользователь и X как электронная почта, поэтому измерение U x X требует большого объема памяти. Обычно такая задача, как фильтрация спама, также имеет ограничение по времени.

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

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

Например,

"Быстрая коричневая лиса" превращается в:

h(the) mod 5 = 0

h(quick) mod 5 = 1

h(brown) mod 5 = 1

h(fox) mod 5 = 3

Используйте индекс, а не текстовое значение, экономя место.

Подведем итог некоторых приложений:

• уменьшение размерности для вектора пространственных объектов

  • текст в задании по классификации электронной почты, совместная фильтрация спама

• sparsification

• мешок слов на лету

• особенности продукта

• многозадачное обучение

Справка:

• Исходная бумага:

  1. Функция хеширования для крупномасштабного многозадачного обучения

  2. Ши, Q., Петтерсон, Дж., Дрор, Дж., Лэнгфорд, Дж., Смола, А., Стрел, А. и Вишванатан, В. (2009). ядра хэша

• Что такое хеш-трюк

• Quora

• Gionis, A., Indyk, P. & Motwani, R. (1999). Поиск сходства в больших размерах с помощью хеширования

Реализация:

• Langford, J., Li, L. & Strehl, A. (2007). VowPal Wabbit Проект онлайн обучения (Технический отчет). http://hunch.net/?p=309.