投稿日: その他 論文紹介

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ポイントシュートの値が高い選手であり,直感的にもガードとしての特徴をより備えた選手を求めることができていた.


-その他, 論文紹介
-

関連記事

What are you looking for? An eye-tracking study of information usage in Web search

Cutrell, Edward Guan, Zhiwei In Proc. of CHI2007 http://dl.acm.org/citation.cfm?id=1240690 概要 デスクトップ …

Information Credibility on Twitter

Castillo, Carlos Mendoza, Marcelo Poblete, Barbara In Proc. of WWW 2011 http://dl.acm.org/citation.c …

Semantic Role Labeling of Emotions in Tweets

Saif M. Mohammad Xiaodan Zhu Joel Martin In Proc. of WASSA 2014 概要 これまでにも、ツイートに含まれる感情を推定する研究は行われてきたが …

Are Web User Comments Useful for Search?

Wai Gen Yee Andrew Yates Shizhu Liu Ophir Frieder In Proc. of LSDS-IR Workshop 2009 概要 YouTubeの動画を検索 …

Spatio-temporal Dynamics of Online Memes: A Study of Geo-tagged Tweets

Kamath, Krishna Y. Caverlee, James Lee, Kyumin Cheng, Zhiyuan In Proc. of WWW 2013 http://dl.acm.org …