投稿日: その他 論文紹介

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


-その他, 論文紹介
-,

関連記事

Extending Faceted Search to the General Web

Kong, Weize Allan, James In Proc. of CIKM2014 http://dl.acm.org/citation.cfm?id=2661964 概要 ファセットを提示す …

Improving passage ranking with user behavior information

Weize Kong Elif Aktolga James Allan In Proc. of CIKM 2013 概要 検索中のユーザの振る舞いを基に検索結果をリランキングする研究はこれまでにも行わ …

Spatio-Temporal Topic Modeling in Mobile Social Media for Location Recommendation

Bo, Hu and Mohsen, Jamali and Martin, Ester In Proc. of ICDM 2013 概要 チェックインサービス等でのユーザと場所と時刻を考慮したモデル化 …

Topic-Driven Reader Comments Summarization

Ma, Zongyang and Sun, Aixin and Yuan, Quan and Cong, Gao In Proc. of CIKM 2012 概要 ニュース記事のコメントをトピックごと …

Your neighbors affect your ratings: on geographical neighborhood influence to rating prediction

Hu, Longke and Sun, Aixin and Liu, Yong In Proc. of SIGIR 2014 概要 店sの周辺の店の情報を利用することで、ユーザuのsに対するレーティン …