So-net無料ブログ作成
最適化(数理計画法) ブログトップ

応用に役立つ50の最適化問題 [最適化(数理計画法)]


応用に役立つ50の最適化問題 (応用最適化シリーズ)

応用に役立つ50の最適化問題 (応用最適化シリーズ)

  • 作者: 藤澤 克樹
  • 出版社/メーカー: 朝倉書店
  • 発売日: 2009/08
  • メディア: 単行本



買って読んでみました。

言葉の定義とか、実際の事例がまとまっている本です。

実際に自分が解きたい問題がどんぴしゃで載っているかといえば、そんな場合は滅多になく、重要なのは、自分が解きたい問題をこの本に書かれているような問題に帰着することができる能力だと思われます。

ちょっと見方や発想を変えるだけで、問題がシンプルになる場合が多く、そのあたりが分析者の力量なのかもしれません。

nice!(1)  コメント(0)  トラックバック(0) 
共通テーマ:学問

SEOの最適化 [最適化(数理計画法)]

4月になって新体制のスタート。
実際に動き出すのはGW後くらいからだろうけど。。。

ちょうど、この期が変わる時期が一番暇なので、日々の業務と離れて基礎研究っぽいにチャレンジする良い時期だ。

そこで考えたことが、
"リスティング広告の最適化みたく、ロジカルにSEOに関しても最適化できないか?"
制御できる変数が異なるのと、SEOの方が期間的に長くなるが、同じようなロジックで最適化できそうだ。

発展形として、アトリビューションっぽい方向に進むとか、SEOとリスティングの融合ってことも考えられるが、まずは、SEOでの最適化アルゴリズムを作ってみようと思う。

nice!(31)  コメント(0)  トラックバック(0) 
共通テーマ:学問

数理システム 事例紹介セミナー [最適化(数理計画法)]

数理システムにて、NUOPT 事例紹介セミナー で発表してきました。
http://www.msi.co.jp/nuopt/seminar/seminar_recruit.html

会場に着くと、思った以上に人が多く驚きですた!(・∀・)
モデルの話やら最適化の話をして、無事に終了。

2009年11月20日(金)のユーザーコンファレンスでも発表予定です。
http://www.msi.co.jp/userconf/09/

場所:アカデミーヒルズ(六本木ヒルズ 49F)
参加費:無料

5時くらいに終わったので、セミナーを聞きに来てくれた人を交え、みんなで飲みに行きました。
新宿マルイに入っている【いのこ家】という豚肉専門店。
一人4,000円~5,000円くらいで食べることができます。

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

数式を使わない最適化の簡単な原理 [最適化(数理計画法)]

数式を使わない最適化の簡単な原理

数式アレルギーの人向けに、数式を使わない最適化の簡単な原理を作ってみた。

いや、実際は数式を使わないのでかなり無理な気もするが、大きな流れや概念は外していないと思う。w

1. 施策ごとのコストとゲイン(収益)の関係を計算する。
(SPSS Clementine や数理システム VMS などを使いモデルを作る。)

この傾きが急なほど、効率が良い施策といえる。

施策にかけるコストにより三角形の大きさは異なってくるし、また、施策の種類により傾きは異なってくる。



2. 直角三角形の傾きが急なものからゆるいものまで順番に並べ替える。

簡単に理解するため、4つの施策を例に考える。
実際は、各施策の中を細分化することで、より効果の高い最適化を行うことができる。



3. 効率の悪い施策の予算を削減し、効率の良い施策に予算を配分する。



結果、最適化をすることで
・コストを削減することができる。
・収益(アクション数)を上げることができる。



実際には、ビジネス的な制約条件などのからみで、単に効率が悪いから削除しましょうってのはダメで、いくらくらい減らせるのかとか、いくらくらい増やせるのかを考えないといけない。

また、予算を割り当てる際に、線形で効果が増えるわけではないので、効率が良いからといって無制限に割り当てることはできない。
三角形の例で例えると、三角形は同じ形のまま大きくなったり小さくなったりはしないのである。

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

数理システム ユーザコンファレンス 2008 [最適化(数理計画法)]

『数理システム ユーザコンファレンス 2008』に行って来た。

今回は、データマイニングってよりNUOPTを中心とした数理計画の事例を聴くことにした。

面白いと思ったのは、
・西尾 明氏(棋士五段)、常盤 秀樹氏(日本将棋連盟)による『日本将棋連盟・関東奨励会における対戦表自動作成システムの導入事例』

・田辺 隆人氏による『数理計画法を用いた自動勤務表作成』

の2つだった。

両方とも、問題としては、ナーススケジューリング問題になるのだが、どちらも1-0整数計画問題で解くことができる。
どっちも、単にこうして解けますよという数学的な講演だけではなく、問題の背景や、実際にプロジェクトを進めていく中での苦労話などが盛りだくさんだった。

難しい堅い話の中に、ほっと和むようなちょっとした笑い話もあり、とても面白いものだった。


Excelで学ぶ実験計画法―シックスシグマと重回帰分析

Excelで学ぶ実験計画法―シックスシグマと重回帰分析

  • 作者: 菅 民郎
  • 出版社/メーカー: オーム社
  • 発売日: 2002/04
  • メディア: 単行本



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

数理システム ユーザーコンファレンス 2008 [最適化(数理計画法)]

数理システム ユーザーコンファレンス 2008

数理システムからダイレクトメールが来た。
今年も六本木ヒルズのアカデミーヒルズでユーザーコンファレンスがあるようだ。

先日参加した SPSS Directions は、マーケティング色が強いセミナーだったが、
数理の場合は、より数理色が強い気がする。

最近、NUOPTを使った案件も増えてきているので、データマイニングというよりは、数理計画を勉強しに参加してみようかと思う。

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

ナース・スケジューリング問題 [最適化(数理計画法)]

NUOPTの無料スキルアップセミナーに参加してきた。

数理計画法に関しては、丸投げすることが多く、実際に手を動かすことが少ないのだが、たまには実際に自分でプログラムすることって大切ですよね。

何ができるかとか、これとこれを組み合わせれば、○○ができる、な~んてことも発想するヒントにもなります。

個人的に面白かったのは、ナース・スケジューリング問題ってのがあるのだが、実は、日本将棋連盟も数理計画法を使っているとか。

順位戦の対戦表だったか、奨励会の対戦表だったか、まぁ、そのあたりの対戦表を作るのに、人が考えているとやたら時間がかかるので、この数理計画法を使っているらしい。


将棋世界 2008年 11月号 [雑誌]

将棋世界 2008年 11月号 [雑誌]

  • 作者:
  • 出版社/メーカー: 日本将棋連盟
  • 発売日: 2008/10/03
  • メディア: 雑誌



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

最適化の実装 [最適化(数理計画法)]

仕事が激忙しくて死亡すんぜんですた。(´д`)

大規模最適化、BTなど同時並行で進んでおり、その〆切りが今日。
最適化にかけるモデルは実験でもバッチリ効果がでているので、次は、このモデルを使っての最適化だ。

無事、配信できそうになったので、一安心。
後は、結果がどうなるか。

でも、働きすぎはよくないな。

nice!(0) 
共通テーマ:仕事

大規模最適化割り当て問題 [最適化(数理計画法)]

9月末〆切りのプロジェクトが多発している。
ちょっと、いや、かなり疲労気味。(´д`)

先日、大規模最適化割り当て問題のプログラムが納品された。

通常、リコメンドというのは、ユーザが望むものを出せば良いのだろうが、ユーザだけでなく、広告を出向してくれているクライアントの両方のCSを満たすためには、どうしても最適化問題を解く必要が出てくる。

規模としては、数千ユーザと比較的小規模のものから、数百万という超巨大な規模の問題を解かないといけない。

通常は、実時間内に実行させることは無理なのだが、クラスタ化するなどの処理をかませることで十分に実時間内に解くことができる。

どれくらいの効果があるのか、非常に楽しみだ。

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

BT(behavior targeting)からBT最適化へ [最適化(数理計画法)]

最近、社内でBT(behavior targeting)メールの案件が活発化している。

これだけ、案件が増えてくると、各事業ごとにモデルを作っているわけには行かないので、モデルのコアとなる部分は同じで作ることにした。
微妙なパラメータ部分に関しては、各事業ごとにパラメータで自己学習する様にしておいた。

グルメ領域と住宅領域に関して、BTとランダムのABテストを行ったところ、なんとBTの方が2倍~3倍の効果がでることが解った。
モデルは、アソシエーションでもなく、協調フィルタリングでもなく、自己作成のモデル。

実際に、社内の人や自分に対して、欲しい物がリコメンドされるのかをみたところ、確かに驚くほどピッタリとしたものが選ばれている。w
後は、その中で、ど真ん中のストライクをリコメンドするのか、ボールではないが、ギリギリストライクのものをリコメンドするのかといったさじ加減も必要になってくる。

次の展開としては、大規模割り当ての数理計画問題だ。
ユーザーが欲しいものをリコメンドするだけでなく、広告を出向しているクライアントなどのことも考えないといけない。
かといって、余剰在庫ばっかり送られたらユーザは、怒ってしまう。
このあたりのことは、データマイニングというよりも、最適化問題で解くのが良いだろう。

ここで問題となってくるのは、ユーザー数、商品数ともに巨大な場合、どのように解くのか?という大きな問題が残ってくる。
詳しくは書けないが、この問題も無事に解決できそうである。

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

大規模、最適化問題 [最適化(数理計画法)]

いつもお世話になっている方のご紹介で、慶応大学に行ってきました。

常々、大規模の最適化問題が解ければと思っているのですが、真正面から問題を解こうとしても、現状は、実時間内で解けない場合が多いです。

そこは、いかに問題をシンプルに置き換えるかとか、1-0整数計画問題から線形計画問題への置き換えなど、うまく問題を近似してあげることで解くことができそう。
このあたりの考え方やテクニックは、その道のプロに聞くのが一番ですね。

先生のオススメソフトとしては、
・CPLEX
http://www.ilog.com/

・NUOPT
http://www.msi.co.jp/nuopt/
らしい。

イメージとしては、大学の先生は自分でソフトを作っているのかと思っていたのですが、実際は、コアの部分は、上記の様なソフトを使って、その周りの部分を自作しているのが多いようです。

上手くクレメンタインに実装できないものか、、、とも考えていますが、
なかなか時間がありません。。。(´д`)


~備忘録~
高速化のための手法
・カラムジェネレーション
・分割統治法

単体法と内点法

ハードコンストレインとソフトコンストレイン

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

BT(behavior targeting)広告の最適化 完成♪ [最適化(数理計画法)]

リスティング広告(キーワード広告)を応用すれば、
 モデル → 最適化
 Clementine → NUOPT
ってのが、できそうだなぁってことを当初考えていた。

が、ちょっとした工夫をすると、Clementineだけで、最適化とシミュレーションまでできることを発見。
Clementine君だけで完結させると、NUOPT(最適化)のプログラミングが省けるし、ランタイムのライセンスもかからないので、何かとお得である。

当初の予定では、モデル作成が2週間、最適化が2週間くらいで1ヶ月くらいかかるんじゃないかって思っていたが、意外とサクッっと2週間くらいで完成した。

ただ、データ量が半端じゃないので、あらかじめ、raw data からデータマートを作成しておいたほうがよさそうだ。

クレメンタインの入門書としてあるのは、これ↓くらい。

SPSSクレメンタインによるデータマイニング

SPSSクレメンタインによるデータマイニング

  • 作者: 牛田 一雄
  • 出版社/メーカー: 東京図書
  • 発売日: 2003/10
  • メディア: 単行本


この本だけだと、Clementine でできることの1%くらいしか使えない気がする。(´д`)

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

行動ターゲティング広告(BT広告)と最適化 [最適化(数理計画法)]

行動ターゲティング広告(BT広告)と最適化

行動ターゲティング広告って、『Behavioral Targeting』書かれているものもあれば、『Behavior Targeting』って書かれているものもあって、どっちなんだろう。
GoogleやYahoo!で調べたら、数的には、『Behavior Targeting(行動ターゲティング)』ってのが多いが、『Behavioral Targeting(行動のターゲティング)』ってのもかなりの数が出てくる。
「行動」も「行動の」もそんなに差はないんだろうか。

さてさて、BTメールの方も第2回配信が終わって、その結果を検証した。
第3回から、データマイニング⇒最適化を使ってみようかと思っている。

そこで、数理システムのNUOPTを引っ張り出してきた。
最適化って奥が深い。


nice!(0) 
共通テーマ:仕事

MATLAB Optimization Toolbox User's Guide:解を探す [最適化(数理計画法)]

MATLAB Optimization Toolbox User's Guide:解を探す

マニュアルには、

解を探す
最適化問題を解くためには、
[x, fval] =lsqlin(C, d, [], [], Aeq, beq)
と入力します。lsqlin は、つぎのように出力します。
x = 0.3333
0.6667
1.3333
fval = 2.3333
最小は点 x で最小となり、 fval は x から原点への距離の二乗です。

と書かれています。

が、これだけでは、どこにどう入力すれば良いのか、さ~ぱり解りません。。。orz

あれこれ、いじってみたら

こんなところにTool Boxを発見しました。(・∀・)!

そして、
C: eye(3)
d: zeros(3,1)
Aeq: [1 2 4]
beq: [7]
と入力し、Startを実行すると、答えが出ました。

MATLABってなんか使いにくい。。。
慣れるまでに時間がかかりそうです。
モジ(((*´ε` *)(* ´З`*)))モジ


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

MATLAB:マニュアルR14Optimization Toolbox:サイバネットシステム [最適化(数理計画法)]

MATLAB:マニュアルR14Optimization Toolbox:サイバネットシステム
http://dl.cybernet.co.jp/matlab/support/manual/r14/toolbox/optim/

MATLABというオモチャをインストールしたのだが、ようやく遊ぶことができた。
最適化の例題が載っていたので、サクッっとやってみる。

例題の問題は、平面上の原点に最も近い点を探すこと。
この数式を変形すると

つまり、平面

上の点から原点への距離を最小にすることになります。

制約条件:


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

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

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

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

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

ここで、NPVは、

と定義しています。

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

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

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

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

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

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

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


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

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

今は昔、、、
データマイニングという言葉がなかった頃、データは何かアクションを行わないと集めることができませんでした。
その一つがアンケートです。
きちんとサンプリングを行い、精錬されたデータに対し、統計的アプローチ(推定・検定など)を行っていました。

しかし、現在では、POSデータなどのトランザクションデータをはじめ、テキストデータやWeb Logデータがどんどん集まってきます。
その中からデータとの長い戦いが始まったのでした。

特にアクセスログの場合、データ容量が半端ではありません。
メガの世界から、すぐにギガの世界へ、そして、テラデータの世界へと飛び込んでしまいます。
そこで、必要なデータを取捨選択し、加工する必要があります。
データを上手くハンドリングすることがマイニングの成功に繋がっているのではないでしょうか…

データ解析やデータマイニングの先にあるものは、、、
それは最適化です。

アメリカなどは、この最適化を使ったマーケティングが進んでいます。
しかし、日本では、最適化という存在を知らない人も少なくはないでしょう。

何回かに分け、最適化の話を展開したいと思います。


nice!(0) 
共通テーマ:学問
最適化(数理計画法) ブログトップ