ハッシュバケットとは何ですか?
効率的な ML メモリ使用のためにハッシュ関数を使用して高カーディナリティのカテゴリ変数を固定サイズのベクトルにマッピングする特徴エンジニアリング手法
Summary
- ハッシュ関数（MurmurHash3など）を適用してカテゴリ特徴量を固定サイズのバケットに変換することで、高カーディナリティ変数に対するワンホットエンコーディングのメモリ爆発を回避します。
- 複数の値が同じバケットにマッピングされるハッシュ衝突を許容することで、ある程度の精度を犠牲にして、ストリーミングや大規模学習におけるメモリと計算の大幅な効率化を実現します。
- スパムフィルタリング、レコメンデーションシステム、CTR予測などでよく使用されます。これらのシステムでは、特徴空間に数百万もの一意の値が含まれる場合があり、従来のエンコーディングでは実現不可能です。
コンピューティングにおけるハッシュテーブル [ハッシュマップ] とは、キー [一意の文字列または整数] に基づいてオブジェクトにほぼ直接アクセスできるデータ構造です。ハッシュテーブルは、バケットやスロットの配列にインデックス計算を行うために、ハッシュ関数を使用し、そこから目的の値を見つけます。使用されるキーの主な特徴は次のとおりです。
- 社会保障番号、電話番号、口座番号などのキーを使用します。
- キーは一意である必要があります。
- 各キーは、値に関連付け（マッピング）されます。
ハッシュバケットは、ソートや検索の目的でデータ項目を割り当てる場合に使用されます。この作業の目的は、リンクリスト探索を短くし、特定の項目の検索にアクセスできるように、検索時間を短縮することが目的です。
バケットを使用するハッシュテーブルは、実際には配列とリンクリストの組み合わせです。配列 [ハッシュテーブル] の各要素は、リンクリストのヘッダーです。同じ場所にハッシュされる要素は、全てリストに格納されます。ハッシュ関数は、1つのバケットの中の最初のスロットに各レコードを割り当てます。スロットが埋まっている場合、空きスロットが見つかるまでバケットのスロットが順番に検索されます。バケットが埋まっている場合、レコードはテーブルの最後にある無限のオーバーフローバケットに格納されます。全てのバケットが同じオーバーフローバケットを共有します。ただし、優れた実装では、バケット間でレコードを均等に分散するハッシュ関数を使用して、オーバーフローバケットに入るレコードをできるだけ最小限にしています。
FAQ
1. ハッシュバケットとは何？
ハッシュ関数で計算した値に基づいてデータを格納する領域（バケット）のことです。
2. どうしてリンクリストが使われるの？
同じハッシュ値が出た複数の要素（衝突）をまとめて格納するためです。
3. オーバーフローバケットは何のためにある？
バケットが満杯になった場合にデータを一時的に格納する領域で、衝突処理の安全弁です。
