投稿日: その他 論文紹介

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


-その他, 論文紹介
-,

関連記事

Fusion Helps Diversification

Liang, Shangsong and Ren, Zhaochun and de Rijke, Maarten In Proc. of SIGIR 2014 概要 検索結果を多様化する際に、複数の検 …

A Study of Mobile Search Queries in Japan

Ricardo Baeza-yates Georges Dupret Javier Velasco In Proc. of WWW2007 概要 デスクトップ検索とモバイル検索の日本語のクエリログに着 …

Search engine click spam detection based on bipartite graph propagation

Li, Xin Zhang, Min Liu, Yiqun Ma, Shaoping Jin, Yijiang Ru, Liyun In Proc. of WSDM 2014 http://dl.ac …

Mining long-term search history to improve search accuracy

Tan, Bin Shen, Xuehua Zhai, ChengXiang In Proc. of KDD2006 http://dl.acm.org/citation.cfm?id=1150493 …

【論文紹介】Exploiting ranking factorization machines for microblog retrieval

Qiang, Runwei and Liang, Feng and Yang, Jianwu CIKM 2013 ACM, PDF 概要 入力として与えられたクエリに対してランキングされたツイートのリ …