了解FeatureHasher、碰撞和向量大小权衡

Question

在实施机器学习模型之前，我正在预处理数据。有些特征具有高基数，例如国家/地区和语言。

由于将这些特征编码为单热向量可以产生稀疏数据，因此我决定研究哈希技巧并使用Python的category_encoders，如下所示：

from category_encoders.hashing import HashingEncoder
ce_hash = HashingEncoder(cols = ['country'])
encoded = ce_hash.fit_transform(df.country)
encoded['country'] = df.country
encoded.head()

查看结果时，我可以看到碰撞

    col_0  col_1  col_2  col_3  col_4  col_5  col_6  col_7 country
0       0      0      1      0      0      0      0      0      US <━┓
1       0      1      0      0      0      0      0      0      CA.  ┃ US and SE collides 
2       0      0      1      0      0      0      0      0      SE <━┛
3       0      0      0      0      0      0      1      0      JP

进一步的调查让我看到了这篇 Kaggle 文章。散列的示例包括X 和 y。

• y的目的是什么，它有助于解决碰撞问题吗？
• 我是否应该向编码器添加更多列并将多个功能一起编码（例如国家/地区和语言）？

如何使用哈希技巧对此类类别进行编码？

更新： 根据我从 @CoMartel 获得的评论，我查看了 Sklearn FeatureHasher 并编写了以下代码来对国家/地区列进行哈希处理：

from sklearn.feature_extraction import FeatureHasher
h = FeatureHasher(n_features=10,input_type='string')
f = h.transform(df.country)
df1 = pd.DataFrame(f.toarray())
df1['country'] = df.country
df1.head()

并得到以下输出：

     0    1    2    3    4    5    6    7    8    9 country
0 -1.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0 -1.0  0.0      US
1 -1.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0 -1.0  0.0      US
2 -1.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0 -1.0  0.0      US
3  0.0 -1.0  1.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0      CA
4  0.0  0.0  0.0  0.0  0.0  0.0  0.0  1.0 -1.0  0.0      SE
5  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0      JP
6 -1.0  0.0  1.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0      AU
7 -1.0  0.0  1.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0      AU
8 -1.0  0.0  0.0  0.0  0.0  0.0  1.0  0.0  0.0  0.0      DK
9  0.0  0.0  0.0  0.0  0.0  0.0  0.0  1.0 -1.0  0.0      SE

• 这就是使用库来编码高分类的方法吗？ 价值观？
• 为什么有些值为负数？
• 您会如何选择“正确的”

  n_features

  值？
• 如何查看碰撞率？

Answer 1

这就是使用库来编码高分类的方法吗？ 价值观？

是的。您的实施没有任何问题。

您可以将哈希技巧视为一种“减少大小的单热编码，冲突风险很小，如果您可以容忍原始特征维度，则不需要使用它”。

这个想法首先由Kilian Weinberger提出。您可以在他们的论文中找到对该算法的理论和实践/经验的整体分析。

---

为什么有些值为负数？

为了避免冲突，使用了signed哈希函数。也就是说，首先使用常用的 hash 函数 对字符串进行哈希处理（例如，通过对每个字符的 ASCII 值求和将字符串转换为相应的数值，然后对

n_feature

取模以获得 (0,

n_features 中的索引) 

]）。然后使用另一个 单位输出 哈希函数，后者根据定义生成

+1

或

-1

，将其添加到第一个哈希函数产生的索引中。

伪代码（不过看起来像Python）：

def hash_trick(features, n_features):
     for f in features:
         res = np.zero_like(features)
         h = usual_hash_function(f) # just the usual hashing
         index = h % n_features  # find the modulo to get index to place f in res
         if single_bit_hash_function(f) == 1:  # to reduce collision
             res[index] += 1
         else:
             res[index] -= 1 # <--- this will make values to become negative

     return res 

---

您将如何选择“正确的”n_features 值？

根据经验，正如你可以猜到的，如果我们散列一个额外的特征（即#

n_feature + 1

），碰撞肯定会发生。因此，最好的情况是每个特征都映射到唯一的哈希值——希望如此。在这种情况下，从逻辑上讲，

n_features

应该至少等于功能/类别的实际数量（在您的特定情况下，不同国家/地区的数量）。尽管如此，请记住，这是“最好”的情况，但“从数学上来说”并非如此。因此，越高越好当然，但是多高呢？见下一篇。

---

如何查看碰撞率？

如果我们忽略第二个单位哈希函数，问题就会简化为“哈希的生日问题”。

这是一个很大的话题。对于这个问题的全面介绍，我建议您阅读this，对于一些详细的数学，我建议您阅读this答案。

简而言之，您需要知道的是，没有碰撞的概率是

exp(-1/2) = 60.65%

，这意味着至少大约有

39.35%

发生一次碰撞的机会。

因此，根据经验，如果我们有

X

个国家，并且哈希函数输出范围（即

40%

参数）为

n_feature

，则至少有

X^2

机会发生一次碰撞。换句话说，如果示例中的国家/地区数量 =

40%

，则有

square_root(n_features)

发生碰撞的可能性。当您以指数方式增加

n_features

时，碰撞的机会就会减少一半。 （就个人而言，如果不是出于安全目的，而只是从字符串到数字的简单转换，那么不值得走得太高）。

好奇读者的旁注：对于足够大的哈希函数输出大小（例如 256 位），攻击者猜测（或利用）冲突的机会几乎是不可能的（从安全角度来看）。

---

关于

y

参数，正如您已经在评论中得到的那样，它只是出于兼容性目的，未使用（

scikit-learn

在许多其他实现中都有此功能）。