【推荐系统中的Hash 1】Hash Trick：原始数据—＞特征，尽可能避免冲突

哈希的本质是得到key

一、Hash Trick（原始数据—>特征，尽可能避免冲突）

早期的特征处理方法主要是one-hot和记数。

这两种方法的缺点是都需要建立高维度的稀疏矩阵，并且泛化性很差，比如垃圾邮件检测任务：

i make ten thousand dollars per week just surfing the web! (label=1)

are you free for a meeting early next week? (label=0)

建立词表，one-hot 特征，可以送入分类器训练：

[1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0] （label=1）

[0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 0] （label=0）

但是很容易规避检测，比如

ii mayke are you th0usands of free for a $$$s surf1ing teh webz meeting early next week

-> [0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 0]

这封邮件里面包含了某些用户自己创造的单词，这些单词在我们的词汇表中没有，但它是一封垃圾邮件。

Hash trick同时考虑了上面两种思想，构造特征工程既可以避免高维稀疏矩阵，也可以具有更好的泛化性。

hash table

建立哈希表。

哈希表是一种数据结构，它是根据键值（key）来直接访问内存存储位置的数据结构。每个哈希表都是用一个哈希函数（也叫散列函数，hash function）来实现键-值（key-value）对的映射。这种函数可以将任何一种数据或者消息压缩成摘要（即散列值），使得其数据量变小且格式固定。理想的散列函数会把不同的键散列到不同的块中，但是大多数哈希表都存在哈希碰撞（hashing collision）的可能，即不同的键可能会被映射到相同的值上。（是优点也有缺点）

在运用哈希表的时候，通常我们需要定义输出的范围，例如假设我们希望将输出范围定义在0-N之间，那么我们就可以使用一个函数，可以将输入数据散列到[0,n-1]之间即可。假设我们创建如下的哈希函数，可以将单词映射成五种类别，即0-4索引：

这样对于"The quick Brown fox" 这句话经过特征哈希Feature Hashing得到的特征向量：
$$v=[1,2,0,1,0]$$
首先Hash地址空间（类似于词汇表）的大小为5，所以特征向量的长度即为5，索引值为0-4，特征向量每一维的取值为该索引出现的次数。根据Hash映射：“The”: 0, “quick”: 1, “Brown”: 1, “fox”: 3。对Hash后的得到的索引进行计数。于是Hash后的特征向量为v=[1, 2, 0, 1, 0]。

真正特征工程中的哈希方法其实是 “mod 5”部分，真实意义上的哈希函数 h() 一般被看作生成器。