投稿日: その他 論文紹介

Efficiently answering top-k typicality queries on large databases

Hua, Ming
Pei, Jian
Fu, Ada W. C.
Lin, Xuemin
Leung, Ho-Fung
In Proc. of VLDB 2007
http://dl.acm.org/citation.cfm?id=1325952

目的

典型的なオブジェクトを発見することが目的.
本論文では2種類の典型性を考えている.1つ目は”simple typicality”と呼ばれるもので,ある集合の中で典型的なオブジェクトを指す.例えば,「NBAの選手の中で典型的な選手」など.2つ目は”discriminative typicality”と呼ばれるもので,ある集合の中でのみ典型的であり,他の集合では典型的でないオブジェクトを指す.例えば「NBAのガードのポジションの選手で典型的な選手」など.
本論文ではさらに,リアルタイムな検索が可能なように高速化にも取り組んでいる.

手法

simple typicalityにおいて典型的なオブジェクトとは,集合の中で出現頻度の高いオブジェクトである,という考えを用いている.この考えに基づき,オブジェクトを引数としてもつような,集合内での確率密度関数を求め,その値をオブジェクトの出現頻度とみなす.確率密度関数はガウシアンカーネルを用いたカーネル推定により求めている.その際,オブジェクト間の距離を求める必要があるが,オブジェクトの素性を要素とするベクトルを作成することで距離を求める.
discriminative typicalityにおいて典型的なオブジェクトとは,そのオブジェクトが属する集合では出現頻度が高いが,属さない集合では出現頻度が低いようなオブジェクトである.全オブジェクト集合をS,オブジェクトoが属するオブジェクト集合をCとすると,oCにおける確率密度関数の値とS-Cにおける確率密度関数の値を調べ,差のより大きいオブジェクトを求める.

実験

実験には動物とNBAの選手のデータを使っており,いずれもデータがWebで公開されているものを使用.
動物の中で,爬虫類だけを対象にするとその中で最も典型的(simple typicality)な動物はヒメアシナシトカゲで,全動物を対象にして爬虫類として最も典型的(discriminative typicality)な動物を求めるとクサリヘビであった.
NBAの選手の中で,ガードの選手だけの中で典型的(simple typicality)な選手と,ガードとして典型的(discriminative typicality)な選手を比較すると,ガードとして典型的な選手は3ポイントシュートの値が高い選手であり,直感的にもガードとしての特徴をより備えた選手を求めることができていた.


-その他, 論文紹介
-

関連記事

Modelling User Interest for Zero-query Ranking

Liu Yang, Qi Guo, Yang Song, Sha Meng, Milad Shokouhi, Kieran McDonald, and W. Bruce Croft In Proc. …

Perception and understanding of social annotations in web search

Fernquist, Jennifer Chi, Ed H. In Proc. of WWW 2013 http://dl.acm.org/citation.cfm?id=2488424 概要 Goo …

Predicting web searcher satisfaction with existing community-based answers

Liu, Qiaoling Agichtein, Eugene Dror, Gideon Gabrilovich, Evgeniy Maarek, Yoelle Pelleg, Dan Szpekto …

What’s in a hashtag?: content based prediction of the spread of ideas in microblogging communities

sur, Oren Rappoport, Ari In Proc. of WSDM 2012 http://dl.acm.org/citation.cfm?id=2124320 概要 ツイッター上で、 …

Using information scent and need for cognition to understand online search behavior

Wu, Wan-Ching Kelly, Diane Sud, Avneesh In Proc. of SIGIR2014 http://dl.acm.org/citation.cfm?id=2609 …