プログラマのための数学

さて、僕は最近ECナビの検索エンジンのリニューアル版を開発しているのだが、これにひとつ付け加えたい機能があった。
それは検索結果に対してさらに価格で絞り込むテキストリンクを表示するというもので、例えばこういったものだ。

価格
すべての価格

• JPY 0 - 1000 (717)
• JPY 1000 - 1500 (464)
• JPY 1500 - 2000 (531)
• JPY 2000 - 3000 (526)
• JPY 3000 - 4000 (309)
• JPY 4000 - 5000 (175)
• JPY 5000 - 8000 (250)
• JPY 8000 - 10000 (70)
• JPY 10000 - 15000 (90)
• JPY 15000 - 20000 (57)
• JPY 20000 - 30000 (43)
• JPY 30000 - 50000 (40)

何度かAmazonで検索してみたが、どんな商品を検索しても毎回同じ価格帯が表示される。これの実装方法は分かりやすい。価格帯のテーブルを持っており、各商品のレコードは値段に応じてそれぞれ属する価格帯のIDを持っているのだろう。全文検索なので、SQLでアクセスするわけではないだろうけど、擬似的にSQLで書くと次のような集計を行っていると考えるのが妥当だ。

SELECT price_range, count(*) FROM items GROUP BY prace_range;

そしてこれを真似するにあたって、すぐに思いつく問題点が3つほどある。

1. 価格帯テーブルをどのように設計するかという問題は易しくて難しい
2. 価格帯テーブルをトライアンドエラーで色々なパターンを試したり後から修正するコストが高い
3. 膨大な検索結果に対する集計のコストが高い

価格帯テーブルの設計について、僕と異なる考えを持つプロデューサがいるかもしれない（ヒント：きっといる）。例えば「19,800〜24,800円くらいの商品が売れ筋なので、15,000〜20,000円の幅ではなく15,000〜25,000円の幅にしてくれ」とかね。
修正自体は難しいことではないけど、15,000〜30,000円の商品が今扱ってる1400万件の商品の内どのくらいあるか分からないが仮に20%くらいだとしても280万件ほどの更新処理を走らせる必要があり、そんなにすぐ終わる話ではない。
その割りに適切な価格帯設計というのは難しく、おそらく統計的な手法 ―― 二種類の価格帯テーブルを用意しておき、お客様の半々にそれぞれの内容を表示して、統計的に有意な販売実績の差があるか見るとか ―― によってしか評価できない。
あと、ストップワードと言われる大して絞り込めないキーワードで検索されたときのように、検索結果が膨大なときにこの集計をかけるとちょっと時間がかかりそうだ。実際Amazonでも、Amazon全体から検索したときは価格帯が表示されず、「エレクトロニクスからipodを検索」のようにカテゴリを絞ってやらないと表示されない。
この機能がどれくらい使われるのか分からない、というよりあまり使われないような気がするけどその割りにずいぶんコストと手間がかかりそうだ。

別なところはどうやっているだろう？

価格帯を指定して絞り込む

• 〜 1,999円
• 2,000 〜 3,999円
• 4,000 〜 10,999円
• 11,000円 〜

この結果はちょっと奇妙だ。2,000〜3,999円の間は2000円なのに4,000〜10,999円の間は7,000円もある。何で価格幅が一定じゃないんだろう？第一4,000円はまだしも11,000円なんて区切りとしては実に中途半端だ。それに検索するたびに価格帯が違う。

価格で絞込み

• 〜1,999円(2405)
• 2,000円〜3,999円(1795)
• 4,000円〜8,999円(1606)
• 9,000円〜(1453)

ふーむ。
楽天と価格コムはプロプライエタリな全文検索エンジンを利用しており、確かそれは同じ製品だったように思う。どうもこれはそいつの機能のようだ。それにしてもどうやって価格帯を決定しているんだろう？
何度か価格コムで検索していると気づいたことがあり、ほぼ毎回提示される価格帯は4つで、4つの価格帯それぞれで絞り込まれる件数は大体等しいようだ。
なるほど。これは中央値を使っているのか。
中央値だって？中央値って何だ？
一応高校数学の確率統計のところで習うはずだけど、中央値というのはその名の通り順番に並べたときに真ん中に来る値だ。例えばipodで検索した結果、ipod用の液晶保護フィルム3件とipod本体2件が引っかかり、値段が{ 100円, 200円, 500円, 30,000円, 50,000円 }だったとすると、この検索結果の価格の中央値は500円だ。この例ですぐ分かるように中央値は平均値とあまり相関しない。
そうと分かれば、以下のようにすると楽天と価格コムと同様の価格帯表示を実現できる。

1. 検索結果の件数Nと価格の中央値C1を求める
2. 中央値C1を、C1付近の区切りのいい数値C1'(4000円とか)に丸める
3. 同じ検索条件で0円〜C1'円の件数N1、中央値C0円とそれを丸めたC0'円を求める
4. 同じ検索条件で0円〜C0'円の件数N0を求める
5. 同じ検索条件でC1'円〜の件数N3、中央値C2円とそれを丸めたC2'円を求める
6. 同じ検索条件でC1'円〜C2'円の件数N2を求める

これで求めた値を使って、

• 〜C0'円(N0件)
• C0'〜C1'円(N1-N0件)
• C1'〜C2'円(N2件)
• C2'円〜(N3-N2件)

という具合に表示してやればよい。
実際には楽天と価格コムが同時に別な場所でこのやり方を思いついたというよりは、おそらくこういう機能が彼らが使っている全文検索エンジンにあらかじめ組み込まれているのだろう。どう見ても結果が似すぎている。
これを実現するのに必要な機能は

• 数値の範囲で絞り込む機能
• 検索結果の件数を求める機能
• 検索結果の中央値を求める機能
• 数値を区切りのいい数値に丸める関数

の4つだけで、上2つは普通の全文検索エンジンは持っていそうだ。区切りのいい数値に丸める機能は、どんな丸め方をしたいかは場合によって違うだろうけど、ある程度方針があれば簡単に実装できるし、全文検索エンジン自体がその機能を提供する必要はない。
中央値を求めるオペレーションを持っている全文検索エンジンはそんなに多くないだろうけど、例えば検索結果のうちa件目-b件目を取得する機能があれば簡単に実現できて、価格でソートしてint(N/2)件目から1件だけ取得してやればそれが中央値だ。
まあ残念ながら僕達が使っている全文検索エンジンはどちらの機能も持っていないのだが。

「プログラマのための数学」にたどり着く前の前提説明で長くなったので以下次号。
来週のサザエさんは、
別な方法で同様の機能を実現する
です。んがんぐ。