SSブログ

最適化 ~データマイニングから一歩先へ~ 第2回 [最適化(数理計画法)]

数理計画の中でも解くのが難しいといわれている整数計画問題についてです。
なぜ、解くのが難しいのか?
それは、組み合わせ爆発が起こり、【解くのにとんでもない時間がかかる!】からです。
コンピューターに計算させて、答えが出てくるのに何週間も何年もかかるようでしたら、それは解けたとは、言いがたいものがあります。

今回、ある商品(商品A, B, C)のDMとコールセンターによるアウトバンドキャンペーンを考えることにします。
まず、第一段階として、Clementineを用いてデータマイニングを行います。
デモグラフィック情報や過去の行動履歴からそれぞれの商品ごとにどういう顧客が反応してくれそうなのかというモデルを作成し、反応確率を計算します。

第二段階として、反応確率、DMの発送やコールセンターにかかるコスト、さらに、クロージングするコストを元にNPV(net present value)を計算したのが下記図になります。

ここで、NPVは、

と定義しています。

ここまでくれば、最適化するための準備は出来上がりです。
後は、いくつかの制約条件が考えられます。考えられる制約条件としては、
・同じ人に違うカードを勧めてはいけない
・コールセンターのアウトバンドでは、1家族1人まで
・1日にかけることのできるコールセンターの台数制限
・DMやコールセンターのアウトバンドコスト
と定義しています。

などが考えられます。上記の制約条件を満たしつつ

を最大にする組み合わせを求めることになるます。

インターネットモールで買い物をしたら、次の日から毎日のようにアウトバンドメールが届くようになった…経験のある方も多いかと思います。
メールなどはコストも安いため安易に送りがちですが、反応してくれそうだからといって、何通もメールを送ってしまったのでは、やがてそのメールは迷惑メールになってしまい、かえってマイナスになってしまいます。
「欲しい情報を、欲しい人に、欲しいタイミングで」を実現するためには、データマイニング+最適化が重要といえます。

統計学では、よく○×推定や□△検定といった話を展開します。
そこにはこのモデル精度は何%あるとか、検証方法はどうするといったことが議論の対象になります。
よく「その最適化の精度は?」とか「別のデータを持ってきて、この最適化を検証するには?」と質問されることがあります。
しかし、こういった発想は統計的な発想なわけで、最適化とは、

のように何億、何兆通りもある組み合わせの中から、目的を最大/最小にする組み合わせを見つけ出す作業なわけです。
この辺りが統計学の世界とは大きく異なる部分です。

小規模の最適化問題ですと、エクセルのソルバーを使って解くことができます。
しかし、大規模になるとエクセルでは解くことができません。
商用のソフトを用意する必要があります。
以前は、大規模な最適化を行えるソフトと言えば、非常に高価でした。
しかし、最近では、最適化ソフトの数も多く出回っており、かつ、お値段の方も安くなってきています。
中には線形の問題だけではなく、複雑な多次元の問題を解くことができる最適化ソフトも存在します。


nice!(0) 
共通テーマ:学問

nice! 0