sklearnのFeatureHasherの挙動について

Question

機械学習に用いる学習データの作成中なのですが,カテゴリ変数をFeature Hashingによって次元削減してみようと思いました.
ためしに,｢月｣のカテゴリ変数を12次元→8次元化することを考えました.

from sklearn.feature_extraction import FeatureHasher
import pandas as pd ; import numpy as np
#テストデータ
test=["1","2","3","4","5","6","7","8","9","10","11","12"]
test=pd.Series(test)#本番ではdfからスライスしたseriesを使用するため
#ハッシュトリック
FH=FeatureHasher(n_features=8,input_type="string")
hashed = FH.fit_transform(test) ; hashed=hashed.toarray()
#衝突検出
arr = len(hashed)
uniqs = len(np.unique(hashed, axis=0))
print(arr,uniqs) #-->(12,10)

↑の例だと衝突してしまうのですが,テストデータが↓のような例だとうまくいきます.

test=["one1","222","three3","444","five5","666","seven7","888","nine9","1010","eleven11","1212"]
test=pd.Series(test)
#中略#
print(arr,uniqs) #-->(12,12)

原因はなんなのでしょうか?
入力文字が短すぎ,形状が他の入力文字と似ているためにハッシュ関数?がうまく働いていないのでしょうか…?

Answer 1

ハッシュを使う限り衝突のリスクはいつもあるのではないでしょうか？
ソースコード見ている限り、衝突回避のための既出の記録や変換などはないようですし、たまたまだと思います。

辞書で隣り合うキーがハッシュ計算後衝突するのも直感的には合わないので運のような…

速さなどを得ることが目的の犠牲なので、衝突が困るのであればOneHotEncodingすれば良い気がします。

---

例えば以下のような文字列で試してみるとわかりやすいです。

from sklearn.feature_extraction import FeatureHasher

conv = FeatureHasher(n_features=2, input_type='string', alternate_sign=False)

print(conv.transform(['f']))
print('-')
print(conv.transform(['ff']))
print('-')
print(conv.transform(['f'*5]))
print('-')
print(conv.transform(['fo']))
print('-')
print(conv.transform(['fou']))
print('-')
print(conv.transform(['four']))

Comments

[ddd34]

うーん…ハッシュの衝突可能性を否定するつもりはもちろんないんですが、32bit符号にそうそう簡単にぶつかられる筋合いもないんですよね
やはり自分の使い方が間違ってるのかとか、関数自体にクセがあるのかとかを考えてしまいます
色々試しているのですが
1 : STR型の数字ではなく普通の単語のような文字列を入力する
2 : 要素数とサンプル数が多い
3 : 変換前の要素次元と変換後の次元に無理がない(12→2とか)
だとほぼ衝突せず、安定的に運用できるような感じがしてきました
が、経験則的な答えではなく、ここが○○だから☓☓、回避するには△△というような技術的な解答が欲しいところです
内蔵されている符号化関数(murmurhash3)に起因するのかなあ…

[mkgrei]

おっしゃるとおりですね。
この程度のサイズでハッシュの衝突を考える前に、ハッシュ計算後の処理に注目すべきでした。

https://github.com/scikit-learn/scikit-learn/blob/a24c8b46/sklearn/feature_extraction/hashing.py#L19
https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/feature_extraction/_hashing.pyx

以上二点お読みになればすべてに納得行くかと思います。

ハッシュ計算後にそれを用いて疎行列のインデックスと値を生成しています。
ただ、その際にインプットの文字列の長さに応じて値がバラけていきます。
長さが1の文字列を使うと、1つのハッシュ値に対してその後の操作が行われます。
その際にインデックスと値の衝突がおきやすくなります。

結論から言うと、文字列長さが一番重要で、十分に長い文字列に対しては衝突の確率が大きく下がることになります。

[ddd34]

なるほど,よく分かりました.
わざわざソースコードまで読んでいただいて,お手数おかけしました
いただいた解説とあわせて,自分もコードを読みながら理解を深めていきたいと思います
どうもありがとうございました