« 国際会議WWW2009論文感想その5 | トップページ | AdaBoost アルゴリズム (ブースティング) »

国際会議WWW2009論文感想その6

Reinier H. van Leuken, Lluis Garcia, Ximena Olivares, Roelof van Zwol: Visual diversification of image search results, Proc. of WWW 2009, pp. 341-350, 2009.

イメージ検索の結果をクラスタリングしようという内容である.イメージ検索をすると,良く似た画像が繰り返し出てくることがあるが,クラスタリングにより,それらを集約化すれば,検索結果の多様性を高めることができるというものである.

イメージのクラスタリングなど,やり尽くされて,もう骨も残っていないような研究分野ではあるが,これは(1) 元のランキング結果も考慮する,(2) どんなクエリに対してもオンラインでリアルタイムにクラスタリングを行う,ことを売りにしている.

クラスタリングに用いる特徴量としては,目新しいものを提案しているわけではない.具体的には,Color histogram (RGBの色空間を64分割し,各色の出現頻度を求めたもの),Color layout(画像を空間的に64分割し,その色平均を求めたもの),Scalable color(HSV色空間のヒストグラムにHaar変換を施したもの),CEDD(フィルタを用いて,垂直,水平,斜め45度のエッジの有無を検出したもの),Edge histogram(画像を空間的に16分割し,そこにエッジが含まれるかどうかを判定したもの),Tamura(Tamuraらが開発したテキスチャ特徴量(粗さ,コントラスト,方向性,線らしさ,規則性,でこぼこさ))を用いている.

クラスタリングアルゴリズムとしては,K-meansや凝集法,Newmanの手法と言った繰り返し計算を必要とするものではなく,以下のようなものを提案している.

Folding:検索結果のランキング上位からをクラスタ代表を選び,ランキングの下位に向かって,逐次クラスタ代表を選ぶ.具体的には,すでに選んだクラスタ代表と十分に距離が遠ければ,新しいクラスタ代表として採用する.ランキングを一通りなめた後,残った画像を最近某法に基づき,クラスタに割り当てる.

Mamin:ランダムに代表R1を選ぶ.次にR1から最も距離が遠くなる画像を代表R2として選ぶ.以降の代表はすでに選ばれた代表との距離のうち最小となるものが最大である画像を選ぶ.この処理を前期最大最少距離が閾値以下になるまで行う.代表を選び終えれば,残った画像を最近某法に基づき,クラスタに割り当てる.

Reciprocal election:「各画像iごとに,i以外の残りの画像を,iとの類似度に基づきランキングしてリストLiを作る.Li中の各画像に対して,Li中でのランクrの逆数をスコアとしてV[j]に足す.」このプロセスをすべての画像に対して行う.これにより,各画像からみて,それに近い画像を探したときに,最も代表らしい画像を探すことになる.さらに,「Vから最大スコアを持つ画像Riを取り出し,それをクラスタ代表とする.残りの画像に対し,残りの画像の一つsが持つランキングリストLsの中に,Riがトップm位以内にあれば,sをRiのクラスタに入れる.取り出した画像はVから除く」を,Vが空になるまで繰り返す.

評価は,人間に特定クエリに対する検索結果を見せて,それをクラスタリングさせ,それを正解としている.その正解のクラスタリングに対して,Folwkes-Mallows indexとVariation of informationを用いて評価を行っている.評価結果は,Folwkes-Mallows indexでは,Flodingが一番良い結果を示している.Variation of informationでは,Reciprocal electionが一番良い結果を示している.統計的な有意差も出している.指標によって結果が異なるので,結局どのアルゴリズムが良いの?という疑問が残るが,これは裏返せばそれだけクラスタリングの評価というものは難しいことを示している.こういう感覚は,実践的にクラスタリングの研究を行っている者だけが分かると言える.

本論文の感想であるが,非常によくまとまった論文であると言える.研究分野はともかく,これから論文を書く初学者にとっては書き方を参考にしてよい論文と言えるであろう.ただ,一点,研究内容に関して不満を上げるとすれば,本研究の貢献はどんなクエリに対してもオンラインでリアルタイムにクラスタリングを行うことにある.このことはもう少しアピールしても良いのではないかと思う.また,評価はクラスタリングの質を重視しているが,クラスタリングの実行速度に関しても評価すべきである.アルゴリズムにおける繰り返しの有無が,速度に決定的違いをもたらすのは自明ではあるが,この評価があれば,どのぐらいのパフォーマンスの改善があるかを示すことができるので,より良い論文になると考える.

|

« 国際会議WWW2009論文感想その5 | トップページ | AdaBoost アルゴリズム (ブースティング) »

Web研究」カテゴリの記事