第5回　近似アルゴリズム¶

本日の到達目標¶

近似アルゴリズムを使う動機（精度とコストのトレードオフ）を説明できる
Bloom Filter、Count-Min Sketch、HyperLogLogの仕組みと誤差特性を説明できる
後半のモデル選択・特徴量設計の探索を「速く回す」ための使い方を説明できる

1. なぜ近似が必要か¶

1.1 厳密な計算のコスト¶

大規模データでの「厳密な計算」は非常に高コスト：

問い	厳密な方法	コスト
ユニークユーザー数は何人か？	全ユーザーIDを集合に入れてカウント	O(N) メモリ
特定のIDは存在するか？	全IDをリストして線形探索	O(N) 時間
最も頻繁な値は何か？	全値の頻度を辞書に記録	O(N) メモリ

10億件のデータに対してこれらを繰り返すと、モデル選択のための「探索」だけで時間とリソースを大量消費する。

1.2 近似の価値¶

「正確には不要、概算で十分」 な場面は多い。

用途	許容誤差	近似手法
ユニーク数の把握	±数%	HyperLogLog
高頻度要素の検出	±小誤差	Count-Min Sketch
要素の存在確認	偽陽性あり・偽陰性なし	Bloom Filter

2. Bloom Filter¶

2.1 用途と問い¶

問い：「このIDはデータベースに存在するか？」

ユースケース - DBの前段でキャッシュヒットしないIDを早期に弾く - スパムメールフィルタ（既知のスパムドメインか？） - 重複排除（このURLは既訪問か？）

2.2 仕組み¶

データ構造：長さ m のビット配列 + k 個のハッシュ関数

挿入操作（要素 x を登録する） 1. x を k 個のハッシュ関数に通して k 個のインデックスを得る 2. それらのインデックスに対応するビットをすべて 1 にする

検索操作（要素 x が存在するか？） 1. x を同じ k 個のハッシュ関数に通す 2. 対応するビットがすべて 1 なら「存在する」（かもしれない） 3. 一つでも 0 なら「確実に存在しない」

視覚的イメージ

ビット配列: [0, 1, 0, 1, 0, 1, 1, 0, 0, 1]
               ↑     ↑        ↑         ↑
          要素 "apple" の 4 個のハッシュが指すビット（すべて1 → 存在する可能性）

2.3 誤差特性¶

誤り種類	発生	意味
偽陽性（False Positive）	あり得る	「存在する」と返すが実際はない → 無駄なDB検索が増える
偽陰性（False Negative）	絶対に起きない	「存在しない」なら確実に存在しない

偽陽性率の制御：ビット配列を大きくする・ハッシュ関数を増やすことで低減できる（ただしメモリが増える）

3. Count-Min Sketch¶

3.1 用途と問い¶

問い：「各要素の出現頻度はだいたいどのくらいか？」

ユースケース - 最頻出の検索クエリランキング - DDoS攻撃で多用されているIPアドレスの検出 - 特徴量の頻度確認（変数選択の前段）

3.2 仕組み¶

データ構造：d 行 × w 列の整数行列 + d 個のハッシュ関数（行ごとに1つ）

挿入操作（要素 x を1回観測した） 1. 行 i のハッシュ関数で x をハッシュし、列インデックス j を得る 2. 各行の matrix[i][j] に 1 を加算

検索操作（要素 x の頻度を推定する） 1. 各行でハッシュして matrix[i][j] を得る 2. d 個の値のうち最小値を頻度の推定値とする（→ Count-Min）

視覚的イメージ

        列0  列1  列2  列3  列4
行0(h0): [3,   2,   5,   1,   4]   → "apple" → h0("apple")=2 → matrix[0][2]=5
行1(h1): [1,   6,   2,   4,   3]   → "apple" → h1("apple")=1 → matrix[1][1]=6
行2(h2): [4,   2,   3,   2,   1]   → "apple" → h2("apple")=3 → matrix[2][3]=2

推定頻度 = min(5, 6, 2) = 2  ← ハッシュ衝突で大きめに見える可能性があるため最小値を使う

3.3 誤差特性¶

推定値は実際の頻度以上になることがある（過大推定）
実際の頻度より小さくなることはない
行数 d と列数 w を増やすと精度が上がる

4. HyperLogLog（HLL）¶

4.1 用途と問い¶

問い：「ユニークな要素数（濃度/カーディナリティ）はいくつか？」

ユースケース - DAU（日次アクティブユーザー数）の推定 - データセットのカラムのユニーク値数を素早く把握 - 結合の前にカーディナリティを見積もる

4.2 仕組み（直観）¶

キーアイデア：ハッシュ値の2進数表現における「先頭からの0の最長連続数」が大きいほど、多くのユニーク要素が観測された証拠

観測要素  → ハッシュ値（2進） → 先頭0の数
"apple"  → 0001101...        → 3
"banana" → 0000011...        → 5
"cherry" → 1001110...        → 0
...

ランダムなハッシュで最長k個の0が出る確率 ≈ 1/2^k
→ 最長0連続数が k なら、約 2^k 個のユニーク要素が存在すると推定

実際には複数のバケットに分けて平均化することで精度を上げる。

4.3 誤差特性¶

標準誤差率 ≈ 1.04 / √m（m = バケット数）
m = 1024 バケットで誤差率 ≈ 3.3%
使用メモリ：数KB〜数十KBで数十億要素のカーディナリティを推定可能

比較（10億ユニークIDの場合）

手法	メモリ	誤差
正確な集合（HashSet）	~8GB	0%
HyperLogLog（m=1024）	~5KB	~3%

5. 後半の分析への応用¶

5.1 特徴量候補の絞り込み¶

第6〜14回の分析では、数十〜数百の特徴量候補から選択する作業が発生する。

近似を使ったプレスクリーニング：

確認作業	使用する近似手法	代替方法（遅い）
変数のユニーク数が多すぎないか	HyperLogLog	`SELECT COUNT(DISTINCT col)`
ある値が十分な頻度で出るか	Count-Min Sketch	`GROUP BY col ORDER BY count`
重複データが混入していないか	Bloom Filter（ID重複）	full scan + dedup

5.2 近似 → 精密の2段階設計¶

全候補変数（数百列）
     ↓ 近似集計で素早くチェック（HLL等）
有望候補に絞り込み（数十列）
     ↓ 精密な相関・VIF計算
最終候補（数列）
     ↓ モデル学習・評価

利点：初期スクリーニングを軽量に済ませることで、本格的な計算を有望候補に集中できる。

6. 基盤リンクの整理¶

基盤概念	本回での役割	後半分析での意味
列指向	近似に必要な列だけ読んでさらに高速化	変数スクリーニングを列単位で軽量実行
整合性	近似でも同一抽出条件下で比較可能	同じデータで各候補を比較する
DAG	近似→精密計算の段階設計をDAGで管理	スクリーニング→本格評価の流れを固定
近似	核心：頻度・基数・存在判定を軽量推定	探索コストを下げて試行回数を増やす

7. 本日のまとめ¶

Bloom Filter：存在確認を定メモリで高速に。偽陰性なし・偽陽性あり
Count-Min Sketch：頻度推定を定メモリで高速に。過大推定のみ
HyperLogLog：カーディナリティ推定を数KBで。数%の誤差許容
これらをプレスクリーニングに使うことで、後半の分析探索を効率化できる

前半（第1〜5回）のまとめ¶

回	テーマ	後半への接続
1	5V・品質課題・変数定義	何を予測するか・どのデータを使うかの出発点
2	列指向・インデックス	特徴量の反復追加・比較を支えるI/O基盤
3	CAP定理・整合性	訓練/検証の再現可能な切り出し設計
4	DAG・ウィンドウ関数	時間窓特徴量の生成と実験パイプラインの管理
5	近似アルゴリズム	変数スクリーニングの高速化

次回予告¶

第6回からは後半：多変量解析に入る。
第6回では 重回帰分析①：残差二乗和の最小化による偏回帰係数の推定と解釈を扱う。

事後課題¶

以下を調べ、A4半枚程度でまとめること： 1. Apache Spark の approxCountDistinct 関数が内部的にどのアルゴリズムを使っているか調べる 2. 本日学んだ3つの近似手法から1つ選び、後半の多変量解析でどの場面に応用できるか具体的に提案する

第5回 近似アルゴリズム¶