数据特征处理之特征哈希（Feature Hashing）

#### 一、特征哈希（Feature Hashing/Hashing Trick）简介
大多数机器学习算法的输入要求都是实数矩阵，将原始数据转换成实数矩阵就是所谓的特征工程（[Feature Engineering](https://www.datalearner.com/blog_list/tag/%E7%89%B9%E5%BE%81%E5%B7%A5%E7%A8%8B "Feature Engineering")），而特征哈希（feature hashing，也称哈希技巧，hashing trick）就是一种特征工程技术。它的目标就是将一个数据点转换成一个向量。

<center>![](https://image.slidesharecdn.com/june10435pmdeepsense-150618234407-lva1-app6891/95/machine-learning-on-hadoop-data-lakes-12-638.jpg?cb=1434671127)</center>
<center></center>

我们先看一下对分类数据（categorical data）和文本数据（text data）进行特征工程处理的一般方法。

分类变量（category variable）就是一组有有限值（finite number of values）的变量。如身份证号、广告类别等。最常见的对分类变量的处理是使用独热模型（one-hot encoding）：创建$N$个二元变量，其中$N$是该分类变量所有可能的取值数量。

而对于文本数据的特征处理，最简单的方法是词袋模型（bag-of-word model）：创建$N$个二元变量，其中N是词汇的数量（即不同单词的数量）。对于每个文档来说，创建一个$N$维向量，文档中包含的某个词汇的数量即是这个向量中词汇对应的索引的值。

可以看到，这两种方法非常类似，都创建了高维稀疏的矩阵。而特征哈希是以哈希表（hash table）的方式来实现这两种转换方法。下面简要介绍一下哈希表。

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

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

```
h(the) mod 5 = 0
h(quick) mod 5 = 1
h(brown) mod 5 = 1
h(fox) mod 5 = 3
```

那么对于某句话：
`the quick brown fox`
来说，其使用哈希特转换的向量就是：
`(1,2,0,1,0)`

哈希表有如下特性：
- 相同的输入可能有相同的输出（一般情况下比例不高）
- 不同的输出一定对应不同的输入
- 正向计算很简单，反向计算很困难
- 根据输入查找输出效率很高

#### 三、简单的案例
我们以垃圾邮件检测（spam）为例（这属于文本分类的一个应用），假设有如下两封邮件，第一封邮件是垃圾邮件，第二封邮件不是垃圾邮件：

```
i make ten thousand dollars per week just surfing the web! (spam)
are you free for a meeting early next week? (not spam)
```

使用词袋模型，我们构造如下的索引表：
```
i: 0
make: 1
ten: 2
thousand: 3
dollars: 4
per: 5
week: 6
just: 7
surfing: 8
the: 9
web: 10
are: 11
you: 12
free: 13
for: 14
a: 15
meeting: 16
early: 17
next: 18
```
总共19个词汇量，我们创建一个19维的向量，得到如下结果：

```
i make ten thousand dollars per week just surfing the web! (spam)
-> [1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0]
are you free for a meeting early next week? (not spam)
-> [0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 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]
```

这封邮件里面包含了某些用户自己创造的单词，这些单词在我们的词汇表中没有，但是实际上我们依然可以识别出来，它是一封垃圾邮件。但是，用上述词袋模型转换的结果却是和前面第二封邮件类似的向量。显然，分类模型会把它归为正常邮件中。因此，上述特征工程显然不能满足要求。

除此之外，使用上述特征工程方法还有一个巨大的问题就是通常会创建非常高维的稀疏向量。假设我们有100万邮件作为训练集，每封邮件平均只有几十个单词，但词汇表可能有数十万，这样创建出来的输入数据是一个高维稀疏矩阵，这对很多机器学习算法来说并不是友好的输入。

如果使用上述的哈希特征方法，就可以将所有的原始数据转换成指定范围内的散列值。这样做有几个好处：

1. 即便对于不在词汇表中的单词，我们依然可以计算出一个散列值，因此不容易被规避，也不需要事先准备词汇表，新特征的转换对输入特征的长度不影响（因为事先已经定义好了散列范围）
2. 只需要散列新来的数据，并不需要重新对所有数据进行哈希处理，所以支持在线学习
3. 经过哈希特征工程之后，原来非常稀疏的向量可能会变得不那么稀疏
4. 尽管有散列冲突，但是研究和实践表明，这种影响很小。

哈希特征工程的比较大的缺点是缺乏可解释性，因为特征被处理成无法解释的散列值了。尽管如此，这个技巧才很多时候非常有用。

#### 特征哈希的使用技巧

使用哈希特征的时候需要选择散列的范围，这个并没有统一的标准。较小的散列范围会导致较多的冲突，影响准确性，较大的范围会占用较高的内存和花费较多的训练时间。因此，在实际情况中，要根据你的目标选择，如果不考虑训练时间的话，可以考虑使用较大范围的散列结果。

数据特征处理之特征哈希（Feature Hashing）

相关博客

最热博客