# 検索結果整理のためのラベルセット選出計算高速化と Wikipedia カテゴリからのラベルセット選出

細野涌城高本綺架 廣中 詩織梅村 恭司
豊橋技術科学大学
\{hosono.yuki.ql, takamoto.ayaka.nx, hironaka.shiori.ru, umemura\}@tut.jp

## 概要

我々は情報収集のために検索することが多いが，適切なキーワードを使わないと, 膨大な数の検索結果が表示されてしまう. そこで，適切なキーワード を思いつけないときでも検索結果を絞り込めるよ うに，検索結果をうまく分類できるラベルセットを 提示することを考える. 本研究では，ラベルの含ま れる文書数（文書頻度）をもとに算出した適性度を 用いて, Wikipedia カテゴリをもとに生成した複数 のラベルセットを順位付ける．ラベルセットの数が 多いため適性度の計算に時間がかかるという問題 があったが, 前処理を工夫し, 文書頻度の計算に Suffix Array を用いたアルゴリズムを利用すること で，短時間で順位付けできた。

## 1 はじめに

我々は情報収集をするとき, 膨大な数の文書に対 して検索することで情報を探すことが多いが，適切 な検索キーワードがわからないと, 膨大な数の検索結果が表示されてしまう. そのため, 我々はキー ワードを追加して検索結果の絞り込みを行う。しか し, 目的の情報に関しての知識が少ないと追加の キーワードを考えるのは難しいため, サジェストを 用いることがある. サジェストは検索ワードや多数 のユーザーの検索ログなどからキーワードを提案す る機能である $[1,2]$. サジェストにより提案される キーワードは，検索結果を絞り込むためによく使わ れているキーワードであり, 様々な粒度のキーワー ドが提案される. 本研究では, カテゴリに対応する キーワード集合（ラベルセット）を大量に用意し， その中から検索結果とマッチングのとれたものを複数提案することを考える.

検索結果には複数の話題が含まれているため, 検索結果の文書集合を共通の話題を含む複数のグルー
プに分類できれば，検索結果の整理や絞り込みに役立つと考えられる. グループ内の文書に共通する話題がキーワード（ラベル）で表現されるとき，ラベ ルには情報の抽象性の粒度があり, 様々な粒度のラ ベルがある，粒度の小さいラベルは，それよりも粒度が大きいラベルによってさらにグループ化できる こと [3] や，小さい粒度のラベルによる小グループ を，粒度が大きいラベルを用いて大グループにまと めることで，分類された文書をより整理しやすくな ること [4]がわかっている. 我々は，粒度のそろっ たラベルで検索結果が整理されている方が，ユーザ にとって理解しやすくなると考えている.

宮越ら [5] は，粒度のそろったラベルセットを事前に用意し，その中から検索結果の整理に適したラ ベルセットを順位付けて提示する手法を提案してい る. 宮越らは, 検索結果には複数の話題が含まれて いるため, 共通の話題を含む複数のグループへ検索結果を偏らず分類できるラベルセットが良いラベル セットであると考えている．実験に用いられたラベ ルセットは地域区分に関するものに限定されていた が，検索結果の整理に適したラベルセットを提示で きていた。

本研究では, あらかじめ用意するラベルセットを つくるために Wikipedia ${ }^{1)}$ を用いる. Wikipedia は多種多様な分野の記事を網羅しており，シソーラス辞書の作成にも用いられている [6] ため, この記事名 をラベルとすることで多様な話題に対応できること を期待している。また, Wikipedia の記事はカテゴ リによって分類されているため，カテゴリによって グループ化される記事の粒度はある程度そろったも のとなっている. Wikipedia カテゴリを用いて，粒度をある程度そろえたラベルセットを大量に生成 する。

本研究では, Wikipedia のカテゴリを用いて生成


した複数のラベルセットの中から，検索結果の分類 に適するラベルセットを順位付けて提示する。さら に, 検索結果とラベルセットのマッチング方法を工夫し，その結果の実行時間も報告する.

## 2 関連研究

検索結果を分類し，ラベル付けすることで文書の 内容を提示する研究は多数存在する. 淀川ら [7] は クラスタラベリングによって重要語を特定すること で, 内容の整理を試みた。村松ら [8] らはクラスタ ラベリングによって付与されたラベルに対して，既存の分類階層である Yahoo!カテゴリを利用した上位語を求めることで，分類した検索結果を階層化させ て整理している.これらの研究により付与されたラ ベルは粒度が不均一である. 我々は粒度が均一なラ ベルのほうが整理に適していると考えている.

Wikipediaを利用して検索結果を整理する研究も 多数存在する. Ugoら [9] は Wikipedia のリンク構造 を用いたクラスタラベリングを行い，検索結果の内容にそぐうラベルの提示を試みた。平島ら [10] は Wikipedia カテゴリに対してパレートの法則を用い たり, 分類に不適切なカテゴリの除去したりするこ とで，検索結果の内容にそぐうカテゴリを提示でき ている.

## 3 使用データ

## 3.1 文書集合

Ceek.jp News²) が 2004 年 1 月から 2020 年 5 月に収集したニュース記事から抽出した記事集合を実験に 用いる，検索結果に適するラベルセットを提示する 実験をするため, 検索結果を模した, 21 種類の選別理由のある文書集合 RR と, 選別理由のない文書集合 D を用意する. 用意した文書集合は宮越ら [5] が 実験で用いたものと同一である．選別理由のある文書集合 RR は, 本研究における分類対象であり, 記事集合から特定の単語リストのいずれかを含む文書 をランダムに最大 3,000 件抽出したものである. 選別理由のない文書集合 D は, 検索対象となる全文書集合を代表するドキュメントの集合であり, 記事集合からランダムに 30,000 件抽出したものである.

2) http://www.ceek.jp/

## 3.2 ラベルセット

多種多様な話題に対応できるよう, 我々は Wikipedia の記事名とその所属カテゴリからラベル セットを作成する．まず，各ラベルセットがそのカ テゴリに所属する記事名をラベルの集合として持 つように，すべての Wikipedia のカテゴリをラベル セットに変換する．次に，分類に不向きであるた め，ラベルセットに属するラベルが 200 種類を超え るラベルセットを削除する. 人名などが羅列された ラベルセットが取り除かれることも期待している. さらに，各ラベルセットに属するラベルから， 4 文字未満のラベルを削除する．ラベルと検索結果の マッチングをする際，「京都」が「東京都」に含まれ てしまうような, 意図しないマッチングを防ぐこと を期待している．削除するラベルを 4 文字未満とし たのは，これらのラベルを削除してもラベルセット に与える影響は小さいと見込んだためである.

本研究では, 2022 年 8 月 20 日に作成された Wikipedia 日本語版のデータベース・ダンプ3) から取得した 314,422 個のカテゴリと，1,974,022 種類の記事データをもとにラベルセットの集合 LSS を生成 した. 生成した LSS には 305,462 個のラベルセット と, $1,441,413$ 種類のラベルが属していた。

## 4 実験方法

Wikipedia カテゴリを用いて生成したラベルセッ トを使って，各 RRに適したラベルセットの適性度 を計算し，順位付ける。順位付けには宮越ら [5] が 提案した手法を用いる. 宮越らの場合よりラベル セット数が増えているため, 適性度の計算の前に分類に適する見込みのないラベルセットを削除する ことにより処理対象を減らし, 実行時間の短縮を図 る. さらに, 適性度の計算の際にはラベルが 1 回以上出現する文書数（文書頻度）を計算する必要があ る. 文書頻度を求めるために, 我々は $d f_{k}$ を高速に 数えるアルゴリズム [11]を用いる．このアルゴリ ズムは，分析対象となる文書集合に対して，前処理 の段階で Suffix Array を用いた頻度表を作成するこ とにより, 複数の単語の文書頻度を, 文書集合を逐一参照することなく求められる. このアルゴリズム を利用して計算できるように，宮越らの使用した一部の条件式を変更する．本研究ではこのアルゴリズ ムの C 言語実装を Python から呼び出して利用した。

3) https://dumps.wikimedia.org/jawiki/

その他の処理は Python で実装した。

処理全体の流れは以下の通りである。初めに，D で出現する傾向にあるラベルとラベルセットを特定 し, 分類に適する見込みがないラベルセットを削除 する. 次に, RR で出現する傾向にあるラベルセッ 卜を特定する. 最後に, 特定したラベルセットに対 して, 宮越ら [5] で提案された手法を用いて適正度 を算出し，順位付けする。

## 4.1 ラベルセットとラベルの絞り込み

初めに，D で出現する傾向にあるラベルセットを 特定する.この処理は検索対象を定めた時点で行う 処理である。まず，LSSに含まれる全てのラベルの 集合 $\mathrm{L}$ を求める. その後, $\mathrm{L}$ の全ラベルに対してラ ベルの文書頻度を求める.ここでは $\mathrm{D}$ におけるラべ ル $l$ の文書頻度を $d f(l ; \mathrm{D})$ と表す. 次に式 (1)を満 たすラベルセット $L S$ を特定し, 満たさない $L S$ は LSS から削除する.ここで， $N_{\mathrm{D}}$ は D の文書数であ り, 本研究では 30,000 である. また, $M_{L S}$ はラベル セット $L S$ に属するラベル数である。なお, 式 (1) は 宮越らの論文 [5] 内の式 (4) を, 文書頻度による推定で置き換えた式である.

$
1-\prod_{l \in L S}\left(1-\frac{d f(l ; \mathrm{D})}{N_{\mathrm{D}}}\right)>\frac{2 M_{L S}}{N_{\mathrm{D}}}
$

その後, 文書頻度が 2 以上のラベルの集合 $L_{2}$ を求 め, $L_{2}$ の要素を 1 つも含まないラベルセットをLSS から削除する. 最後に, 削除後の LSS をもとにLを 再度求める. ここまでの処理により, ラベルセット は 5,253 個, ラベルは 97,708 種類に絞り込まれた。

次に RR で出現する傾向にあるラベルセットを求 める.まず，L の全ラベルに対して RRにおける文書頻度 $d f(l ; \mathrm{RR})$ を求める. 次に, $L_{2}$ から $d f(l ; \mathrm{RR})$ が 1 以上のラベルを取り出した部分集合 $R L_{1}$ を特定する. 最後に $R L_{1}$ の要素を含む LSS の部分集合 LSC を求める. RR によって LSC に含まれるラベル セット数は異なるが, 21 種類の RR で平均 4072 個 に絞り込まれた。

## 4.2 ラベルセットの順位付け

宮越ら [5] の提案手法を用いて適正度を算出し,順位付けを行う。初めに，式 (2) を満たさない，分類に不適切なラベルセットを削除する.ここで， $N_{\mathrm{RR}}$ は RR の文書数であり,「りんご農家」の RR で は 1,706, それ以外の $\mathrm{RR}$ では 3,000 である.なお,式 (2) は宮越らの論文 [5] 内の式 (3) を, 文書頻度に
よる推定で置き換えた式である.

$
1-\prod_{l \in L S}\left(1-\frac{d f(l ; \mathrm{RR})}{N_{\mathrm{RR}}}\right)>\frac{2 M_{L S}}{N_{\mathrm{RR}}}
$

次に，ラベルの適正度を求める。まず，ラベル セット $L S$ 内の各ラベルに対し式 (3)を求め， $x_{l}$ を 式 (4) のシグモイド関数に代入した值 $\sigma\left(x_{l}\right)$ をラべ ルの適正度とする。

$
\begin{gathered}
x_{l}=\frac{\frac{d f(l ; \mathrm{RR})}{N_{\mathrm{RR}}}-\frac{d f(l ; \mathrm{D})}{N_{\mathrm{D}}}}{\sqrt{\frac{\left(\frac{d f(l ; \mathrm{RR})}{N_{\mathrm{RR}}}\right)\left(1-\frac{d f(l ; \mathrm{RR})}{N_{\mathrm{RR}}}\right)}{N_{\mathrm{RR}}}+\frac{\left(\frac{d f l ; \mathrm{D})}{N_{\mathrm{D}}}\right)\left(1-\frac{d f(l ; \mathrm{D})}{N_{\mathrm{D}}}\right)}{N_{\mathrm{D}}}}} \\
\sigma\left(x_{l}\right)=\frac{1}{1+e^{-x_{l}}}
\end{gathered}
$

最後にラベルセットの適正度を求める. ラベル セット $L S$ の適正度は $L S$ 内の全ラベルの適正度の平均であり, 式 (5) の $s_{L S}$ で表される.この適正度に 従いラベルセットの順位付けを行う。

$
s_{L S}=\frac{\sum_{l \in L S} \sigma\left(x_{l}\right)}{M_{L S}}
$

## 4.3 実行時間の計測方法

ラベルセットの順位付けは検索時に行うことを想定しているため, 処理速度が求められる. そこで,本研究では RR を読み込んでからラベルセットの順位付けを行うまでの実行時間を調べることで，検索時に行うに足る処理速度か判断する。本稿では，各 $R R$ に対して 10 回実行した時間の平均を報告する.

実験に用いた PC の OS は Windows 10 Home であ り, CPU は Intel Core i7-9700,メモリは 32GB であ る. Python 3.8.10 で実行し, $\mathrm{C}$ 言語で実装されたア ルゴリズムのコンパイルは GCC 9.4.0 で行った。ま た，時間計測には， $\mathrm{C}$ 言語で実装されたアルゴリズ ムの前処理は time モジュールの pref_counter 関数 を，その他の処理はprocess_time 関数を用いた。

## 5 実験結果 $\cdot$ 考察

我々は， 21 種類の RR に対して，4 節で説明した 方法で適正度を求め, ラベルセットを順位付けし た。本節では RR「Jリーグ」に対するラベルセット の順位付け結果のみ示す. その他 20 種類の RRに対 する順位付け結果は付録 A に示した。また，本節で は各 RRにおける実行時間も示す.この実行時間を もとに，実際の検索で用いるに足るかを判断する.

RR「Jリーグ」に対するラベルセットの順位付け 結果を表 1 に 10 位まで示す. ラベル数が 10 以上の
表 $1 \mathrm{~J}$ リーグに対するラベルセットの順位付け結果

 & 0.98 & 1 \\

に関するラベルセットであるため, J リーグの内容 と関連のあるラベルセットだと考える。一方，ラベ ル数が 1 のラベルセットはラベルセット名だけでは ラベルの内容が不明であった. ラベルセット内のラ ベルを用いて検索結果を分類することを考えると， ラベル数 1 のラベルセットは分類に不適切であり, ラベルの内容も名前だけで予測しづらいため，ラベ ル数が 1 のラベルセットは取り除かなければならな いと考える. なお, 平島らの研究 [10] では, ラベル 数が 3 以下のラベルセットがあらかじめ取り除かれ ている.

次に，各 RRにおける実行時間を表 2 に示す．RR 「震源地」以外では, 平均約 3.6 秒で順位付けできた ため, 実際の検索時に行う処理として許容できる速 さだと考える. RR「震源地」で遅くなった原因は, RR「震源地」には文書の 7 割以上を英語が占めてい表 2 各RRにおける実行時間

るものが存在するためである．文書頻度を求める際 に用いたアルゴリズムの実装は日本語で記述された 文書に対して使うことを想定している。このアルゴ リズムは反復度という特徴量を用いているが，英語 は反復度が日本語よりも大きいため [12], 英語が多 く含まれる文書集合は適していなかった。アルゴリ ズムの実装を反復度が大きい単語を考慮するように 変更することにより，英語が多く含まれる文書集合 に対しても，他の文書集合と同様に数秒程度で処理 を終えられると考える。

## 6 おわりに

本研究では, Wikipedia カテゴリを用いて生成し た複数のラベルセットの中から, 検索結果の分類に 適するラベルセットをほぼ数秒で順位付けて提示 することができた。上位に選ばれたラベルセットの うち, ラベル数が 10 以上のラベルセットをみると,文書の内容に関連するラベルセットを提示できたと 考える. 今後の課題として, ラベル数が少ないラベ ルセットの削除は行うことが必要であるとわかって いる.

## 参考文献

[1] Zhiyong Zhang and Olfa Nasraoui. Mining search engine query logs for query recommendation. In Proceedings of the 15th International Conference on World Wide Web, pp. 1039-1040, 2006.

[2] Sumit Bhatia, Debapriyo Majumdar, and Prasenjit Mitra. Query suggestions in the absence of query logs. In Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 795-804, 2011.

[3] 平川秀樹, 木村和広. 概念体系を用いた概念抽象化手法と語義判定におけるその有効性の 評価. 情報処理学会論文誌, Vol. 44, No. 2, pp. 421-432, 2003 .

[4] Hiroyuki Toda and Ryoji Kataoka. A search result clustering method using informatively named entities. In Proceedings of the 7th Annual ACM International Workshop on Web Information and Data Management, pp. 81-86, 2005.

[5] 宮越遥, 吉田光男, 梅村恭司. 文書整理に用い る分類リスト順位付けの試み. 第 14 回データ 工学と情報マネジメントに関するフォーラム. G43-3, 2022.

[6] 中山浩太郎, 原隆浩, 西尾章治郎. Wikipedia マイニングによるシソーラス辞書の構築手法. 情報処理学会論文誌, Vol. 47, No. 10, pp. 2917-2928, 2006.

[7] 淀川翼, 加登一成, 伊東栄典. 単語の分散表現を用いた文書クラスタのラベル推定. 人工知能学会第二種研究会資料, Vol. 2019, No. SWO-049, p. 03, 2019.

[8] 村松亮介, 福田直樹, 石川博. 分類階層を利用 した検索エンジンの検索結果の構造化とその 提示方法の改良. 第 19 回データ工学ワーク ショップ. B6-3, 2008.

[9] Ugo Scaiella, Paolo Ferragina, Andrea Marino, and Massimiliano Ciaramita. Topical clustering of search results. In Proceedings of the Fifth ACM International Conference on Web Search and Data Mining, pp. 223-232, 2012.

[10] 平島峻成, 吉田光男, 梅村恭司. 新聞記事検索結果に対する分類ラベル生成における Wikipedia カテゴリ情報の利用法. 第 11 回データ工学と 情報マネジメントに関するフォーラム. G2-4,
2019.

[11] Kyoji Umemura and Kenneth Church. Substring statistics. In Computational Linguistics and Intelligent Text Processing, pp. 53-71, 2009.

[12] Yoshiyuki Takeda, Kyoji Umemura, and Eiko Yamamoto. Deciding indexing strings with statistical analysis. In Proceedings of the Third NTCIR Workshop on Research in Information Retrieval, Automatic Text Summarization and Question Answering, pp. 79-85, 2002.
表 3 すべての RRに対するラベルセットの順位付け結果

 &  &  &  &  &  &  &  &  &  &  &  &  &  &  &  &  \\

## A すべてのRRに対する順位付け結果

表 3 にすべての RR に対するラベルセットの順位付け結果を示した。ここに示したラベルセットは, 各 RR に対して最も適正度が高いラベルセットのみ取り出したものである. 行はRRを，列はラベルセットを示し ている。各セルは RRに対するラベルセットの適正度を示している。赤く塗りつぶされたセルは, 該当する RR（行）において最も適正度が高いことを示している. セルの值がハイフン (-) となっているラベルセット は，該当する RRにおいて LSC に含まれず，適正度の計算対象外であったことを示している．また，セルの 值が 0 となっているラベルセットは, 該当する RRにおいて式 (2) を満たさず，適正度の計算対象外であった ことを示している.

表 3 をると，フィギュアスケートの RRに対して，シスメックス（坂本花織選手などが所属する企業）と いうラベルセットの適正度が最も高いことが分かる. そのため, シスメックスのラベルセットにより, フィ ギュアスケートの内容の一部を捉えられていると考える。しかしながら，マンゴーやみかんの RR に対して サトウキビ属の適正度が高いなど，記事の内容とはおよそ的外れなラベルセットが分類に適すると判定され たものも存在することが分かった，さらに，ハイチ系日本人や，仏教系政党といった，ラベルセット名だけ では内容が予測しづらいラベルセットが存在することも分かった。検索結果の内容にそぐわなかったり, ラ ベルセット名から内容が予測しづらいラベルセットを削除するために, 平島らの研究 [10] のようにラベル数 が 3 以下のラベルセットを取り除くべきだと考える.
 細野涌城高本綺架 廣中 詩織梅村 恭司 豊橋技術科学大学 \{hosono.yuki.ql, takamoto.ayaka.nx, hironaka.shiori.ru, umemura\}@tut.jp  