¿Qué es hashing de características (hashing-trick)?

Question

Sé que el hashing de características (hashing-trick) se usa para reducir la dimensionalidad y manejar la dispersión de los vectores de bits, pero no entiendo cómo funciona realmente. ¿Alguien me puede explicar esto? ¿Hay alguna biblioteca de Python disponible para hacer hashing de características?

Gracias.

Answer 1

Here (Lo siento, no puedo agregar esto como un comentario por algún motivo). Además, la primera página de Feature Hashing for Large Scale Multitask Learning lo explica muy bien.

Answer 2

En pandas, podría utilizar algo como esto:

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) 

La salida sería

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 

también en el nivel de la serie, que podría numpy

importación, como NP, os import sys, pandas como 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) 

Esto funcionará por serie única, se asumirá que el nombre de la columna es un índice de Pandas. También reemplaza cadenas en blanco con nan y flota todo.

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 

Sin embargo, si hay un vocabulario, y que simplemente quiere a uno caliente a codificar, podría utilizar

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) 

que dará También he añadido

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 

la escarsificación del marco de datos final también. En una configuración incremental donde es posible que no hayamos encontrado todos los valores de antemano (pero de alguna manera obtuvimos la lista de todos los valores posibles de alguna manera), se puede usar el enfoque anterior. Los métodos ML incrementales necesitarían el mismo número de características en cada incremento, por lo tanto, la codificación one-hot debe producir el mismo número de filas en cada lote.

Answer 3

La característica dispersa grande se puede derivar de la interacción, U como usuario y X como correo electrónico, por lo que la dimensión de U x X requiere mucha memoria. Por lo general, tareas como el filtrado de correo no deseado también tienen limitaciones de tiempo.

Hash truco como cualquier otra función hash almacenar bits binarios (índice) que hacen posible el entrenamiento a gran escala. En teoría, más longitud hash más ganancia de rendimiento, como se ilustra en el documento original.

Asigna la función de origen en diferentes depósitos (longitud finita de espacio de entidad) para que se mantenga su semántica. Incluso cuando el spammer utiliza errores tipográficos para perderse en el radar. Aunque hay un error de distorsión, la forma heredada del hash permanece cerca.

Por ejemplo,

"el zorro marrón rápido" transformación para:

h(the) mod 5 = 0 

h(quick) mod 5 = 1 

h(brown) mod 5 = 1 

h(fox) mod 5 = 3 

Uso índice en lugar de valor de texto, ahorra espacio.

Para resumir algunas de las aplicaciones: la reducción

• dimensionalidad para alta dimensión vector de características

  • texto en tarea de clasificación de correo electrónico, filtrado colaborativo sobre el spam

• sparsification

• bolsa de palabras sobre la marcha

• cruz-Características del producto

• aprendizaje multi-tarea

Referencia:

• papel Origen:

  1. Feature Hashing para Gran Escala Multitarea Learning

  2. Shi, Q., Petterson, J., Dror, G., Langford, J., Smola, A., Strehl, A., & Vishwanathan , V. (2009). kernels Hash

• What is the hashing trick

• Quora

• Gionis, A., Indyk, P., & Motwani, R. (1999). búsqueda de similitud en dimensiones altas a través de hashing

Implementación:

• Langford, J., Li, L., & Strehl, A. (2007). Proyecto de aprendizaje en línea Vow- pal wabbit (Informe técnico). http://hunch.net/?p=309.