The k-means range algorithm for personalized data clustering in e-commerce

Georgios P. Papamichail and Dimitrios P. Papamichail
European Journal of Operational Research
Volume 177, Issue 3 , 16 March 2007, Pages 1400-1408
http://dx.doi.org/10.1016/j.ejor.2005.04.011

k-meansクラスタリングとrange treeを融合した．
とアブストラクトに書いてあるものの，ただ単にenumerationをrange treeを用いて行なって，その後でk-meansクラスタリングを行なっただけのような気がする．

Multi-criteria auctions without full comparability of bids

Yves De Smet
European Journal of Operational Research
Volume 177, Issue 3 , 16 March 2007, Pages 1433-1452
http://dx.doi.org/10.1016/j.ejor.2005.04.014

オークション理論と多目的決定理論の融合．
オークション理論では属性が複数ある場合は，多属性オークションとか多次元オークションという概念があるようだけども，ここで考えている多目的オークションでは，bid同士が比較可能でなくてもよい．
それによって解かなければならない問題がいろいろと出てくるようだ．
私好みの考え方に見える．

k-intolerant capacities and Choquet integrals

Jean-Luc Marichal
European Journal of Operational Research
Volume 177, Issue 3 , 16 March 2007, Pages 1453-1468
http://dx.doi.org/10.1016/j.ejor.2005.04.015

関数F: [0,1]^n→[0,1]をn個の属性値を1つにまとめ上げる集約関数と見なす．(決定理論ではよくある概念．)
自然数kに対してFがat most k-torelantであることを，任意のxに対してF(x)≦OS_k(x)となることと定義する．
ただし，OS_k(x)とはxの成分の中でk番目に小さいものとする．(順序統計量みたいなもの．)
この概念をChoquet積分 (ショケ積分) に適用して，また関数がどれほどk-torelantっぽいかという指標なども提案して (これがk-intolerant capacity)，性質を調べたり，実際の小さな決定問題の例に応用している．
ちなみにショケ積分はファジィ積分とも呼ばれてるものの一種であるはずで，ショケ積分は離散最適化で出てくるLovasz extensionとも同値な概念．

ニコリ購入

週末にようやくニコリの最新刊を購入した．
表紙の暗号だけど，今回はすらっと解けた．
前半のペンシルパズルはだいたい解いた．
スリザーリンクにだいぶ慣れてきた．今後はカックロも鍛えていかなきゃ．

ページランクの「アイデアそのものは極めて凡庸」？

牧野さんの日誌からたどって「グーグルが無敵ではないことはエンジニアだけが知っている」という記事を読んでみた。

理論家としては、何かしらのアイデアが「自明」とか「極めて凡庸」と言われたりすることにすごく抵抗があって、それは個人的な感情なので押し殺すことにしても、ページランクのアイデアそのものが極めて凡庸であると私は思わない。
まず、アイデアを思いつくこととアイデアを理解できることはまったく別なことだということは明らかだから、アイデアが凡庸かどうかということでアイデアの良し悪しを判断してはいけない。
そして、私がページランクというアイデアが凡庸でないと思ってる理由は、複雑なことを考えずに単純化して、実際計算できるレベルにまで落としたことだと思う。
Webをグラフとして考えることはページランク以前にもあったと思うけど、そのときにノードの重要度みたいなものを測定しようとしたとき、いろいろと複雑なことを考えることはできるけれども、それを全部排除してできるだけ単純なランダムサーファーモデルを使って、ランダムジャンプも導入してマルコフ連鎖をergodicにするというトリックを使って、意味がありそうなモデル化をしたことだと思う。
それによって問題は (比較的単純な) 固有値計算になったのだから、かなり単純なモデル化だと思う。
それを実際に使えるレベルまで``engineer''したこと自体が一番評価されるべきところではあると思うけれども、それはその記事や牧野さんも言及してることなので省略。

あと、「論文の被参照構造（リンクポピュラリティ）の計算なんて、教科書の演習問題にさえ載っていそうなテーマだ」というのは数学の演習問題がどういうものなのか (またはどういうものであるべきか) というものを理解していない発言で、そういう人が「大学の一般教養レベルの初等数学をきちんと学んだ者であれば…」というような言い方をしてしまうのは困ったことだと思う。
(もっとも、ここでいう「教科書」が数学の教科書なのかどうかは分からないけど。)

NP完全性がどういう概念か理解していただけてないのは理論家の宣伝不足であるとも思うし、``NP完全であればあきらめる''というような間違った理論家像をいだかれてしまっているのも理論家の宣伝不足ではあると思うので、その点は私の力不足かな、とも思う。

誤解がないように注記しておくと、その記事の「イノベーション＝エンジニアの士気」からの話の流れは嫌いじゃなくて、好きなほうです。
ひっかかったのは「極めて凡庸」かどうか、というところ『だけ』なので、誤解ないよう。

ちなみに私がGoogleを使い始めたのは修士課程にいたころだと思うけど、それまではAltavistaを使っていて、レスポンス時間を比較してGoogleに乗り換えたことを記憶している。Googleはかなり速かった (いまでも速い)。
その他、Altavistaでポリトープを検索するとポリトロープ (宇宙科学の概念) がたくさん返ってきたけど、Googleではそういうことがなかった、っていう理由もあった。
ページランク自体にはそれほど興味なかったと思う、自分は。

アルゴリズム・サイエンス：出口からの超入門

アルゴリズム・サイエンス:出口からの超入門 (アルゴリズム・サイエンスシリーズ 2―超入門編)

「NP完全であればあきらめる」というような間違ったアルゴリズム研究者像を払拭するためには、とりあえずこの本かと。