投稿日: その他 論文紹介

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の精度でクラスタリングができていた.


-その他, 論文紹介
-,

関連記事

Unsupervised Semantic Similarity Computation between Terms Using Web Documents

Elias Iosif Alexandros Potamianos In IEEE Transactions on Knowledge and Data Engineering, Vol.22, Nu …

Fighting search engine amnesia: reranking repeated results

Shokouhi, Milad White, Ryen W. Bennett, Paul Radlinski, Filip In Proc. of SIGIR 2013 http://dl.acm.o …

Contextual queries express mobile information needs

Hinze, Annika M. Chang, Carole Nichols, David M. In Proc. of MobileHCI 2010 http://dl.acm.org/citati …

Deciphering Mobile Search Patterns: A Study of Yahoo! Mobile Search Queries

Yi, Jeonghee Maghoul, Farzin Pedersen, Jan In Proc. of WWW2008 http://dl.acm.org/citation.cfm?id=136 …

Sentiment-Based Topic Suggestion for Micro-Reviews

Ziyu Lu, Nikos Mamoulis, Evaggelia Pitoura, Panayiotis Tsaparas In Proc. of ICWSM 2016 概要 Foursquare …