投稿日: その他 論文紹介

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


-その他, 論文紹介
-

関連記事

Measuring Pair-Wise Social Influence in Microblog

Zibin Yin Ya Zhang In Proc. of SocialCom 2012 概要 Weibo上でのリツイートのモデル化を提案。提案モデルを使うことで、ユーザAのツイートがフォロワーのユ …

Can social features help learning to rank youtube videos?

Chelaru, Sergiu Viorel Orellana-Rodriguez, Claudia Altingovde, Ismail Sengor In Proc. of WISE 2012 概 …

Placing Videos on a Semantic Hierarchy for Search Result Navigation

Tan, Song Jiang, Yu-Gang Ngo, Chong-Wah ACM TOMM 2014 http://dl.acm.org/citation.cfm?id=2578394 概要 「 …

Efficient multiple-click models in web search

Guo, Fan Liu, Chao Wang, Yi Min In Proc. of WSDM2009 概要 クリックモデルに関するこれまでの研究では、ユーザはクエリを入力して1度検索結果をクリック …

Adaptive Query Suggestion for Difficult Queries

Liu, Yang Song, Ruihua Chen, Yu Nie, Jian-Yun Wen, Ji-Rong In Proc. of SIGIR 2012 http://dl.acm.org/ …