Feature hashing(特征哈希)

Feature hashing(特征哈希)

在机器学习中，特征哈希也称为哈希技巧（类比于核技巧），是一种快速且空间利用率高的特征向量化方法，即将任意特征转换为向量或矩阵中的索引。它通过对特征应用散列函数并直接使用特征的散列值作为索引来工作，而不是在关联数组中查找索引。

例子

在典型的文档分类任务中，机器学习算法（包括学习和分类）的输入是自由文本。 因此，构造了BOW表示：每个单词被抽取并计数，并且在训练集中的每个不同的单词都定义了训练集和测试集中每个文档的一个特征（独立变量）。
但是，机器学习算法通常用数值向量来定义。 因此一个文档集中的单词被认为是一个文档矩阵，其中每行是一个文档，每列是一个特征/单词; 在这个矩阵中的i,j项捕获了文档i中词汇表的第j项的频率（或权重）。根据Zipf定律，这些向量通常极其稀疏。
常用的方法是在训练时或在此之前构建训练集词汇表的字典表示，并用它将单词映射到索引。 例如这三个文档

• John likes to watch movies.
• Mary likes movies too.
• John also likes football.

可以使用字典转换成文档矩阵

$$\begin{pmatrix} \textrm{John} & \textrm{likes} & \textrm{to} & \textrm{watch} & \textrm{movies} & \textrm{Mary} & \textrm{too} & \textrm{also} & \textrm{football} \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \end{pmatrix}$$

（和常见的文档分类和聚类一样，标点符号被删除了）
这个过程的问题在于，这些字典占用大量的存储空间并且规模随着训练集的增长而增长。 如果词典保持不变，对手可能会尝试发现不存在于存储词典中的新单词或拼写错误，来绕开机器学习的过滤器。 这就是为什么Yahoo!尝试使用特征哈希进行垃圾邮件过滤的原因。
哈希技巧并不局限于文本分类和类似文档的任务，也可以应用于任何涉及大规模（可能是无限的）特征的问题。

使用哈希技巧进行特征向量化

和维护一个字典不同，使用哈希技巧的特征向量化器可以把哈希函数$h$应用于特征（例如单词）来构建一个预定义长度的向量，然后将哈希值直接用作特征索引并更新结果向量。

def hashing_vectorizer(features, N):
     x = N * [0]
     for f in features:
         h = hash(f)
         idx = h % N
         x[idx] += 1
     return x
1
2
3
4
5
6
7

因此，如果我们的特征向量是[“cat”,”dog”,”cat”], hash function 是$hash(x_f)$，如果$x_f$是“cat”，结果是1，如果$x_f$是“dog”，结果是2。我们设定输出特征向量的维度(N)是4，那么输出$x$就是[0,2,1,0]。建议使用第二个单比特输出的 hash function $ξ$来确定更新值的符号，以抵消hash冲突的影响。如果使用这样的hash函数，则该算法变为

def hashing_vectorizer(features, N):
     x = N * [0]
     for f in features:
         h = hash(f)
         idx = h % N
         if ξ(f) == 1:
             x[idx] += 1
         else:
             x[idx] -= 1
     return x
1
2
3
4
5
6
7
8
9
10

上面的代码实际上将每个样本转换为一个向量。 优化后的版本会生成一个$(h，ξ)$对的流，并让学习和预测算法消耗这些流。

tips:

• 一般来说，我们使用向量的维数可能非常大，例如$2^{25}$或类似大小。
• 向量会非常稀疏，因此使用一种节省空间的格式进行存储，例如，一个向量存储不为0的值，另一个向量存储这些值所在的列号。
• 可以使用第二个hash函数，它返回+1或-1来决定是否对向量进行加减。这将使冲突最小化，使向量的维度发挥巨大的价值。

References:

Wikipedia Feature hashing

Feature Hashing for Large Scale Multitask Learning.