投稿日: その他 論文紹介

Improving the exploration of tag spaces using automated tag clustering

Radelaar, Joni
Boor, Aart-Jan
Vandic, Damir
Van Dam, Jan-Willem
Hogenboom, Frederik
Frasincar, Flavius
In Proc. of ICWE 2011
http://dl.acm.org/citation.cfm?id=2027797

概要

タグのクラスタリングをsyntacticとsemanticの両方の観点から行う.それぞれの観点のクラスタリングには,既存手法やそれを少し拡張したものを使用.これまでの研究よりも大規模なデータでクラスタリングを行ったことがこの論文のcontributionのひとつ.

手法

・syntacticな観点からのクラスタリング
タグのスペルミスなどを発見してひとつのタグにまとめる.例えばnewyork,ynewyok,nwyorkの3つを1つのクラスタにして,そのクラスタにnewyorkとラベル付けするのが目的.
提案手法では,まずタグをノード,タグ間の類似度を枝の重みとするグラフを作成する.類似度はLevenshtein distanceという編集距離に基づく類似度とタグの共起に基づく類似度の線形和により求める.類似度が閾値以上の場合のみノード間の枝が存在する.このようにして作成されたグラフにおいて,枝がつながっている部分をひとつのクラスタと見なし,各クラスタで最も使用される頻度の高いタグをそのクラスタの代表タグとする.次のsematicな観点からのクラスタリングでは,この代表タグのみを使用する.

・semanticな観点からのクラスタリング
clustering-by-committee-based algorithmという手法を拡張したものを用いてクラスタリング.1つのタグが1つのクラスタを表す状態から始め,あるタグに対してあるクラスタ内の全タグとの平均類似度が閾値以上であればマージする.その際,3つのヒューリスティックも用いる.
1つ目は,あるクラスタが別のクラスタの部分集合になっていた場合,小さい方のクラスタを削除するというもの.
2つ目は,小さいクラスタcと大きいクラスタCがあったときに,c-Cの要素数が閾値以下であれば2つのクラスタをマージするというもの.閾値はcのサイズに応じて動的に変わる.
3つ目は,c-Cの各要素とCの各要素の平均類似度が閾値以上であれば2つのクラスタをマージするというもの.こちらの閾値は固定されている.

実験

2009年にFlickrにアップロードされた画像を使用.3,900万枚の画像,20万のユーザ,102万のタグを含む.そこからノイズであるようなタグの除去を行う.例えば,133枚以下の画像にしか付与されていないタグは除くなど.
評価指標には既存のクラスタリング評価指標を使用.
syntacticな観点でのクラスタリングの評価では,クラスタリングが終了した後100個のクラスタをランダムに選択してラベリングの正しさを評価.0.89の精度でラベリングができていた.
semanticな観点でのクラスタリングにおいては,0.86の精度でクラスタリングができていた.


-その他, 論文紹介
-,

関連記事

Are Web User Comments Useful for Search?

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

【論文紹介】A Peek Into the Future: Predicting the Popularity of Online Videos

Shuxin Ouyang, Chenyu Li, Xueming Li Access, 2016 IEEE, PDF 概要 中国のYouTubeに相当するYoukuの動画を対象にして、動画の投稿後7 …

Addressing people’s information needs directly in a web search result page

Chilton, Lydia B. Teevan, Jaime In Proc. of WWW 2011 http://dl.acm.org/citation.cfm?id=1963413 概要 最近 …

【論文紹介】Why People Search for Images using Web Search Engines

Xiaohui Xie, Yiqun Liu, Maarten de Rijke, Jiyin He, Min Zhang, Shaoping Ma WSDM 2018 ACM, PDF 概要 画像検 …

Identifying topical authorities in microblogs

Pal, Aditya Counts, Scott In Proc. of WSDM2011 http://dl.acm.org/citation.cfm?id=1935843 概要 あるキーワードに …