投稿日: WSDM 論文紹介

Identifying task-based sessions in search engine query logs

Lucchese, Claudio
Orlando, Salvatore
Perego, Raffaele
Silvestri, Fabrizio
Tolomei, Gabriele
In Proc. of WSDM 2011
http://dl.acm.org/citation.cfm?id=1935875

概要

ユーザのクエリログを,タスク単位で分割することを目的とした論文.論文の前半ではAOLのクエリログを用いたデータの分析を行い,後半ではクエリログをタスク単位に分割する手法の提案とその評価を行っている.

データ分析

クエリログのデータは2006年にAOLが公開したものを使用.期間は2006年3月1日から2006年5月31日で,65.7万人のユーザのデータが含まれる.
データの分析には,その中からクエリの発行数の多い上位1,000人のユーザの最初の1週間のクエリを用いた.クエリ数は1,424個であった.

まず,各ユーザが発行したクエリを時間ベースのセッションに分割する.ユーザの発行したクエリを時間順にソートし,隣り合うクエリの発行時間が26分以内であれば同じセッションとみなして分割を行う.その結果,1,424個のクエリは307のセッションに分割された.その後,各セッションのクエリをタスクごとに人手で分割する.例えば,あるユーザのあるセッションが9つのクエリq_{1},q_{2},\cdots,q_{9}を含んでおり,人手によって3つのタスクt_{1},t_{2},t_{3}が含まれていると判断されれば,各タスクとクエリを紐付けてt_{1}=\{q_{1},q_{2},q_{3},q_{4}\}, t_{2}=\{q_{5},q_{7}\}, t_{3}=\{q_{6},q_{8},q_{9}\}のようにデータを記録する.その結果,307のセッション内に554のタスクが含まれており,各タスクでの平均クエリ発行数は2.57であった.
以下はセッションとタスクの分析結果である.

  • 時間ベースのセッションの長さ
    セッションの長さについて1分単位でヒストグラムを作ると,全セッションのうちセッションの長さは1分以内のものが最も多く,全体の約36%を占める.他は,その次に割合の多い2分~3分でも5%にも満たない.平均の長さは15分.
  • 時間ベースのセッションに含まれるクエリ数
    平均で4.49個のクエリを含む.1個のみ含むセッションが最も多く,全体の約36%.
  • 1セッションあたりのタスク数
    1セッションあたり平均で1.8個のタスクを含む.307個のセッションのうち,1つのタスクのみを含むものは162個だけであり,約半分のセッションはマルチタスクから成るセッションであった.また,1,424個のクエリのうち1,046個はマルチタスクから成るセッションに含まれており,このことから約74%のクエリはマルチタスクに関するものであると言える.

手法

時間ベースのセッションをタスクに分割するための手法について述べる.手法は,時間に基づいた分割と,クエリのクラスタリングによる分割の2つに大きく分けられる.

  • 時間に基づいた分割
    セッション内の時間でソートされたクエリを,隣り合うクエリの発行時間が閾値以下であればひとまとまりのタスクとみなす.実験では閾値として5分,15分,26分を用いている.
  • クエリのクラスタリングによる分割
    クラスタリングを行うためには,任意の2クエリ間の距離を定義する必要がある.この研究では,クエリの字面の類似度と意味的な類似度から距離を求めている.

    字面の類似度では,クエリをトライグラムに分割して,2つのクエリ間でのトライグラムの共起度を基に類似度を測る手法と,編集距離を基に類似度を測る手法を組み合わせている.

    意味的な類似度では,Wikipediaを使っている.提案手法では,語tはベクトルC(t)=(c_{1},c_{2},\cdots ,c_{W})で表される.WはWikipedia内の記事数であり,c_{i}ti番目の記事との関連度を表す.関連度はtf-idfにより求める.そしてクエリqC(q)=\sum_{t \in q} C(t)により表され,クエリ間の類似度はコサイン類似度により求める.
    同様のことをWiktionaryでも行い,関連度の高い方を採用する.

    以上2つの類似度を,2種類の方法によって組み合わせる.ひとつは各類似度の線形和を用いる方法である.もうひとつは字面の類似度が閾値以下なら字面の類似度のみを用い,閾値以上であれば字面の類似度と意味的類似度のうちより類似度の高いものを用いる方法である.

    クラスタリングには4つの手法を用いる.そのうち3つの手法は既存の手法(QC-MEANS,QC-SCAN,QC-WCC)であり,残りの1つは,QC-WCCをクラスタリングの時間を短縮することを目的として著者が改善した手法(QC-HTC)である.

実験

時間に基づいた分割では,時間の閾値を短くしたからといってタスクの特定精度が上がるわけではなく,全体的に精度は低い.

クラスタリングにもとづく手法では,3つの既存手法の中ではグラフベースの手法であるQC-WCCが最も高い精度となった.著者が提案したQC-HTCは,QC-WCCよりわずかに精度は劣るが,クラスタリングを高速化できるという利点がある.
字面の類似度と意味的類似度の組合せ方は2種類提案したが,いずれの手法でも大きな差はなかった.


-WSDM, 論文紹介
-,

関連記事

A Study of Mobile Search Queries in Japan

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

Personalized Models of Search Satisfaction

Ahmed Hassan Ryen W. White In Proc. of CIKM 2013 概要 ユーザが検索セッションに対して満足したか,不満足だったかを知ることは検索エンジンの質を高めるうえ …

【論文紹介】Online Actions with Offline Impact: How Online Social Networks Influence Online and Offline User Behavior

Althoff, Tim and Jindal, Pranav and Leskovec, Jure In Proc. of WSDM 2017 概要 スマホのArgusという活動記録アプリのログから …

Modeling documents as mixtures of persons for expert finding

Serdyukov, Pavel Hiemstra, Djoerd In Proc. of ECIR2008 http://dl.acm.org/citation.cfm?id=1793313 概要 …

Perception and understanding of social annotations in web search

Fernquist, Jennifer Chi, Ed H. In Proc. of WWW 2013 http://dl.acm.org/citation.cfm?id=2488424 概要 Goo …