投稿日: その他 論文紹介

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


-その他, 論文紹介
-

関連記事

Semantic Annotation of Mobility Data using Social Media

Wu, Fei and Li, Zhenhui and Lee, Wang-Chien and Wang, Hongjian and Huang, Zhuojie In Proc. of WWW 20 …

【論文紹介】The automated acquisition of suggestions from tweets

Dong, Li and Wei, Furu and Duan, Yajuan and Liu, Xiaohua and Zhou, Ming and Xu, Ke AAAI 2013 ACM, PD …

Learning from the Past: Answering New Questions with Past Answers

A. Shtok, G. Dror, Y. Maarek, and I. Szpektor In Proc. of WWW 2012 http://dl.acm.org/citation.cfm?id …

Explainable User Clustering in Short Text Streams

Zhao, Yukun and Liang, Shangsong and Ren, Zhaochun and Ma, Jun and Yilmaz, Emine and de Rijke, Maart …

It Is Not Just What We Say, But How We Say Them: LDA-based Behavior-Topic Model

Qiu, Minghui and Zhu, Feida and Jiang, Jing In Proc. of SDM 2013 概要 トピックモデルを用いて文書の生成過程をモデル化する際、通常は文書 …