特征哈希：将高基数类别特征映射到固定维度

什么是特征哈希

特征哈希（Feature Hashing），又称哈希技巧（Hashing Trick），是一种将任意数量的类别特征快速转换为固定维度数值向量的方法。它通过哈希函数将高基数（类别数量极多）的分类变量直接映射到低维整数索引，从而避免维护完整的词汇映射表。

在机器学习中，类别特征（如用户ID、城市名、商品编号）通常需要通过独热编码或嵌入层转换为数值输入。当类别数量达到百万甚至亿级时，传统独热编码会导致维度灾难和巨大的内存开销。特征哈希将原始特征值哈希成一个固定范围内的整数，再以此为索引构建特征向量，维度始终由用户指定的输出维度控制，与原始类别总量无关。

工作原理

特征哈希的核心思想是利用哈希函数将任意输入字符串或整数值映射到一个[0, D-1]的整数区间，其中D是预设的输出特征维度。

哈希过程

1. 选择输出维度D：根据模型容量、数据稀疏度和精度需求确定一个固定整数，如D = 2^18。
2. 定义哈希函数：通常使用MurmurHash、CityHash等非加密哈希函数，它们速度快且分布均匀。可以对同一输入多次哈希，或使用不同种子生成多个哈希值以缓解碰撞影响。
3. 构建特征向量：
   • 对于每个原始特征值x，计算哈希值h(x) = hash(x) % D，得到索引i。
   • 为避免符号碰撞造成信息抵消，另一种常见做法是同时使用符号哈希：sign(x) = 2 * (hash(x+seed) % 2) - 1，得到±1符号。
   • 在向量V的第i个位置累加符号值（通常对于计数特征直接累加1或sign(x)；对于二值特征，设置V[i] = sign(x)或直接置1）。
4. 结果：无论原始特征有多少个不同取值，最终都表示为一个维度为D的稀疏向量。

处理多特征与组合特征

特征哈希可以轻松处理特征交叉。例如，需要将“国家”和“城市”组合成一个新特征，只需对拼接后的字符串"国家#城市"进行哈希，无需显式枚举所有组合。这在大规模推荐系统和广告模型中极为常见。

为什么使用特征哈希

• 内存效率极高：无需存储映射字典，在线学习或流式数据场景中，新出现的类别可以即时哈希，不增加内存占用。
• 维度可控：开发者可以精确控制输出特征向量的维度，平衡模型容量与计算成本。
• 天然适应动态类别集合：在用户ID、搜索词等无限集合的特征上，新值出现时无需重新训练或扩展模型参数。
• 简化分布式实现：哈希函数的无状态特性使得并行化、数据分片变得简单，各节点无需共享稠密的映射表。
• 支持特征交叉：字符串拼接后哈希即可实现特征组合，无组合爆炸问题。

哈希碰撞的影响与缓解

特征哈希不可避免会引入碰撞：两个不同的原始类别被映射到同一个索引。碰撞会导致信息损失，本质上是将两个不同的概念混合在了同一维度上。

碰撞概率

当输出维度为D，原始类别数量为N时，碰撞概率可由生日悖论近似计算。若N=10^6，D=2^20 ≈ 1,000,000，碰撞已非常显著；实践中常取D=2^24（约1600万）以上来大幅降低碰撞率。

符号哈希的作用

通过引入随机符号（±1），即使两个类别碰撞在同一索引，它们仍然可能带有不同的符号，在梯度更新时相互抵消而非简单累加。这可以部分缓解碰撞造成的方差增大，尤其在线性模型中能保持特征的无偏性（期望意义下）。

实际缓解策略

• 增大维度：在内存允许的前提下增加D，使碰撞概率降至可忽略水平。
• 特征分桶隔离：对不同特征组（如用户特征、物品特征）使用各自的哈希空间，避免不同类型特征在同一空间碰撞。
• 使用带符号哈希：确保线性模型中的输出期望不受碰撞影响。
• 选择质量高的哈希函数：保证输出均匀分布，减少聚集碰撞。

特征哈希的实现步骤

1. 确定输出维度

根据经验法则：输出维度D至少为原始类别数量的平方除以可容忍的碰撞概率。例如，期望碰撞率低于1%，可参照公式 D > n^2 / (2 * ln(1/(1-p)))。工程实践中常直接选择2的整数次幂，如2^18 = 262,144，2^24 = 16,777,216。

2. 选择哈希函数与种子

选择速度快的非加密哈希：MurmurHash3、xxHash、CityHash。若需符号，可使用不同种子计算第二个哈希值，或直接取第一哈希值的最高位作为符号。

3. 构建特征向量

以Python伪代码为例（使用hash内置函数或hashlib）：

import hashlib

def feature_hash(value, D=2**24, seed=42):
    # 使用稳定哈希，避免Python内置hash的随机化
    h = int(hashlib.md5(f"{seed}_{value}".encode()).hexdigest(), 16)
    index = h % D
    sign = 1 if (h >> (h.bit_length() - 1)) else -1
    return index, sign

# 用于文本特征的哈希向量化（类比HashingVectorizer）
def hashing_vectorize(features, D=2**20):
    vec = [0] * D
    for f in features:
        idx, sgn = feature_hash(f, D)
        vec[idx] += sgn  # 或按权重累积
    return vec

4. 在机器学习流水线中使用

• 使用sklearn.feature_extraction.text.HashingVectorizer处理文本特征，n_features控制维度。
• 在PySpark MLlib中，HashingTF和FeatureHasher可直接用于数值和类别特征。
• 在TensorFlow中，可使用tf.strings.to_hash_bucket_*系列函数进行在线哈希。

通常对哈希后的索引进行One-Hot或嵌入（Embedding）。当D较大且数据稀疏时，可直接使用索引作为权重向量的脚标，每个索引对应一个可学习权重。

适用场景与局限性

适用场景

• 大规模在线学习：广告点击率预测、推荐系统中用户ID、广告ID等超基数特征。
• 文本分类与自然语言处理：使用词袋模型且词汇量极大时，HashingVectorizer常替代CountVectorizer。
• 特征交叉与组合特征：需要大量二阶或多阶交互特征时，哈希交叉极大降低维度。
• 流式数据与未知类别：如实时日志分析，无法预知全部类别值。

局限性

• 不可逆与不可解释：无法从哈希后的索引反推原始特征值，模型解释性差。
• 碰撞导致精度损失：当输出维度不足或碰撞严重时，模型性能可能下降。
• 不适合需要保留精确计数或频率信息的任务：如有必要，可在外部维护计数再带入哈希值乘权重。
• 参数敏感：维度D的选择对结果有影响，需要通过实验调整。

与其他方法对比

特征哈希常与嵌入结合：先用哈希分桶，再为每个桶学习一个低维稠密向量。这种方法兼顾了内存控制和表示能力，在深度学习中应用广泛（如“hash embedding”）。

动手实践建议

1. 使用sklearn的HashingVectorizer在20 Newsgroups文本数据集上比较哈希维度从2^10到2^20的分类准确率变化，观察碰撞影响。
2. 对用户ID特征，分别用独热编码、特征哈希后接线性模型，比较内存占用和AUC。
3. 尝试在哈希后引入可学习的嵌入层，构建一个小型推荐模型，调整哈希桶数量，观察性能与参数量的权衡。
4. 注意Python中hash()函数在不同进程间可能不一致，生产环境请使用hashlib或稳定的第三方哈希库。

特征哈希是以轻微精度损失换取巨大工程收益的经典技术，在工业界大規机器学习系统中不可或缺。理解其原理与权衡，能帮助你在处理海量类别数据时做出恰当的设计选择。