偽陽性確率
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/07/15 00:00 UTC 版)
要素数 n {\displaystyle n} とフィルターサイズ m {\displaystyle m} から偽陽性確率 p {\displaystyle p} を求めたグラフ。最適なハッシュ関数の個数 k = ( m / n ) ln 2 {\displaystyle k=(m/n)\ln 2} を前提としている。 ハッシュ関数は配列上の各位置を同じ確率で選択するものとする。要素をひとつ追加する際、あるビットが特定のハッシュ関数で 1 にセットされない確率は次のようになる。 1 − 1 m {\displaystyle 1-{\frac {1}{m}}} . 従って k 個のハッシュ関数のいずれによっても、1つのビットが 1 にセットされない確率は次のようになる。 ( 1 − 1 m ) k {\displaystyle \left(1-{\frac {1}{m}}\right)^{k}} . n 個の要素を追加した状態で、あるビットがいまだに 0 である確率は次のようになる。 ( 1 − 1 m ) k n {\displaystyle \left(1-{\frac {1}{m}}\right)^{kn}} ; したがって、逆に 1 となっている確率は次のとおり。 1 − ( 1 − 1 m ) k n {\displaystyle 1-\left(1-{\frac {1}{m}}\right)^{kn}} . ある要素ではないと分かっているデータに対してそれが集合の要素であるかどうかをテストしたとする。このときハッシュ関数で得られる k 個のビットそれぞれが 1 となっている確率は上記の通りである。全てが 1 となっている確率、すなわちブルームフィルタがそのデータが集合の要素であると誤って判定してしまう確率は次のようになる。 ( 1 − ( 1 − 1 m ) k n ) k ≈ ( 1 − e − k n / m ) k {\displaystyle \left(1-\left(1-{\frac {1}{m}}\right)^{kn}\right)^{k}\approx \left(1-e^{-kn/m}\right)^{k}} . 明らかに、m（配列のビット数）が大きければ偽陽性の発生率は低くなり、n（追加する要素数）が多くなれば偽陽性の発生率は高くなる。いま m と n が決まっているとき、偽陽性発生率を最小にする k（ハッシュ関数の個数）は次のようになる。 k = m n ln 2 ≈ 9 m 13 n ≈ 0.7 m n {\displaystyle k={\frac {m}{n}}\ln 2\approx {\frac {9m}{13n}}\approx 0.7{\frac {m}{n}}} , このときの偽陽性の発生確率は次の通り。 ( 1 2 ) k ≈ 0.6185 m / n {\displaystyle \left({\frac {1}{2}}\right)^{k}\approx {0.6185}^{m/n}} .
※この「偽陽性確率」の解説は、「ブルームフィルタ」の解説の一部です。
「偽陽性確率」を含む「ブルームフィルタ」の記事については、「ブルームフィルタ」の概要を参照ください。
- 偽陽性確率のページへのリンク
