数据特征处理之特征哈希（Feature Hashing）
一、特征哈希（Feature Hashing/Hashing Trick）简介
大多数机器学习算法的输入要求都是实数矩阵，将原始数据转换成实数矩阵就是所谓的特征工程（Feature Engineering），而特征哈希（feature hashing，也称哈希技巧，hashing trick）就是一种特征工程技术。它的目标就是将一个数据点转换成一个向量。
我们先看一下对分类数据（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索引：
