...

入札情報推薦のための Web ページのクラスタリング手法に関する検討

by user

on
Category: Documents
6

views

Report

Comments

Transcript

入札情報推薦のための Web ページのクラスタリング手法に関する検討
情報処理学会第 74 回全国大会
5B-7
入札情報推薦のための Web ページのクラスタリング手法に関する検討
小俣
尚泰†
関根 聡一†
株式会社栗本鐵工所†
1. はじめに
我が国では入札契約適正化法の施行以来,入
札情報の Web 上での公開が進んでいる.そこで
筆者らは,Web に公開された入札情報を横断検索
できるサービス“K-Finder”を開発した[1][2].
K-Finder は,入札情報を発見しやすいインター
フェースを備えているが,特定のカテゴリに限
定した情報を抽出するためには,ユーザがキー
ワード検索機能を駆使しなければならない.そ
のため,キーワードがうまく想起できない場合,
意図した情報抽出がしづらいという問題がある.
そこで,筆者らは Web ページのクラスタリング
手法に注目し,クラスタリング結果から得られ
たカテゴリ情報に基づく情報推薦を行うことで
問題解決を図る.
2. 入札情報推薦の課題と解決手法
本稿では,ある Web ページ集合のクラスタリ
ングの結果として得られた各クラスタについて,
そ の 識 別 境 界 を 推 定 す る 手 法(以下,提案手
法)を用いて情報推薦を行うことを提案する.
ここで,識別境界の推定とは,クラスタリング
の結果から多クラス分類器を生成することを意
味する.この識別空間の中に未知のデータが到
来したとき,そのデータはどのクラスに属する
かという判別のために使用する.クラスタリン
グ結果が得られた時点で興味のあるクラスタを
選択しておけば,そのクラスに属する新しい文
書が検知されたことをユーザに通知することが
でき,ユーザが興味を持つ入札情報の推薦が可
能となる.
提 案 手 法では,図 1のクラスタ分析フロー
(以下,C-Flow),図 2の多クラス分類器作成
フ ロ ー ( 以 下 , L-Flow ) , 図 3 の 識 別 フ ロ ー
(以下,R-Flow)の3つの処理手順で構成され
ており,識別関数には C-Flow でのクラスタリン
グ結果を教師信号とする教師有り学習型の多ク
ラス分類器を用いた手法とする.同一のクラス
タリング処理を再実行して識別境界を再現する
場合と比較して,提案手法では R-Flow での識別
処理にかかる計算コストやメモリ消費量を抑え
ることができ,かつ一意な識別境界を再現でき
A Study of Web-page Clustering Methods for Bidding
Information Recommendation
Naoyasu Omata†, Soichi Sekine†
†KURIMOTO, LTD.
N 件の文書ベクトルを要素とする文書ベクトル集合
D  {d1 , d 2 ,, d N } についてクラスタ分析を行うことを
考える.
Step1)(クラスタリング)
任意の目標クラスタ数 k を与えクラスタリングを行
い,k 個のクラスタ C1 , C2 ,, Ck を得る.このとき任意
の文書ベクトル di が属するクラスタを Cdi とする.
Step2)(興味のあるクラスタの保存)
ユーザが興味を持つクラスタ集合 U を保存する.
図1
クラスタ分析フロー(C-Flow)
文書ベクトル集合 D から文書行列 D  [d1 d2  d N ] を
得る.
Step1)(次元削減)※次元削減をする場合のみ
文書ベクトル D の各要素 di が n 次元のベクトルとなる
よう次元削減を行う.ここで n は, n
 rank (D) であ
る自然数であり,識別関数の精度が最大となるような,
なるべく小さい数とする.
Step2)(学習)
N 件の文書ベクトル集合 D を訓練サンプル, Cdi を教
師信号とし多クラス分類器を作成する.この際に,ある
文書 x がどのクラスに属するかを推定するための識別関
数 f (x) を得る.
Step3)(識別関数の保存)
Step2)で得られた識別関数 f (x) を保存する.
図2
多クラス分類器作成フロー(L-Flow)
Step1)(所属クラスタの推定)
未知の文書から得られる文書ベクトル x が属するクラ
スタ Cx は,識別関数 f (x) の出力として得られる.
Step2)(興味文書かどうかの推定)
Step1)で得られたクラスタが U に含まれる場合は,文
書ベクトル x はユーザが興味を持つ文書であると推定で
きる.
図3
識別フロー(R-Flow)
るという特長を持つ.
3. 提案手法に関する実験
提案手法の実装の検討を行うため,提案手法
のプロトタイプを作成し,その性能を検証する
ための実験を行った.まず,適切な分類器の選
定 を す る た め に Naïve Bayes ( 以 下 , NB ) と
Support Vector Machine(以下,SVM)の比較の実
験を行った.次に,SVM については,パラメータ
調整前後の状況と汎化性能の検討をするための
実験を行った.具体的な実験内容を以下に述べ
る.
3.1. 実験データ
表 1 に示す条件にて K-Finder で検索した結
1-515
Copyright 2012 Information Processing Society of Japan.
All Rights Reserved.
情報処理学会第 74 回全国大会
情報区分
フリーワード
都道府県
発注機関
ファイルタイプ
日付(更新日)
フィルタ条件
K-Finder での検索条件
100.0%
入札公告
なし
大阪府
大阪市
全ての形式
2011/06/25~2011/12/22
低
90.0%
80.0%
Accuracy
表1
70.0%
60.0%
Naive Bayes
50.0%
Naive Bayes (Dimension Reduction)
SVM
40.0%
SVM (Dimension Reduction)
30.0%
5
10
20
40
80
cluster number
図 4 Naïve Bayes と SVM の再代入法によるテスト結果
100.0%
95.0%
90.0%
85.0%
Accuracy
果から,上位 1,000 件の文書ベクトル集合 D を
得る.各文書ベクトルは,該当する発注機関及
び情報区分の用途に特化して構成された入札情
報フィルタ[2]により素性選択された索引語の有
無を要素としている.現行の K-Finder では 1000
次元となるよう調整をしているため,文書行列
D を構成する場合には 1000×1000 行列となるデ
ータが得られる.以降に説明する実験では,こ
のデータを用いた.
3.2. NB と SVM の比較
L-Flow で使用する分類器に NB と SVM の2種類
を使用し,その精度を測定した.また,それぞ
れの分類器に対して,L-Flow の Step1 の次元削
減の有無による影響を測定した.L-Flow と RFlow に使用するサンプルは同一となる再代入法
により検証を行った.C-Flow では,階層的凝集
クラスタリング(以下,HAC)を使用した.
図 4に実験結果を示す.NB ではクラスタ数 k
が大きくなるにつれて精度が顕著に低下する.
このことは,k の大きさが問題の複雑度合いを示
しているといえる.しかしながら,次元削減を
した場合は,その低下率が軽減されており,次
元削減が精度に良い影響を与えているといえる.
SVM の結果を見ると,k 値に依存せず全て 100%の
精度という結果であったため,次元削減の有無
の影響は判断できない.NB と SVM を比較すると,
k が大きい領域では NB が極めて不利であり,提
案手法の実現に NB は適さないといえる.
3.3. SVM のパラメータ最適化と汎化性能
前述の実験と同様に L-Flow で使用する分類器
に SVM を使用し,その精度を再度測定した.こ
の際に SVM のパラメータの調整を行った場合,
行わない場合の 2 つの測定パターンを追加した.
ま た , 分 類 器 の 精 度 検 証 方 法 に は , 10-fold
cross validation を用いた.
図 5に実験結果を示す.いずれの結果もクラ
スタ数 k が大きくなるにつれて精度が低下する
傾向にあるが,パラメータ最適化前の結果から
は,次元削減が精度の向上に大きく寄与してい
ることが確認できる.したがって,次元削減は
SVM においても精度に良い影響を与えるといえる.
80.0%
75.0%
70.0%
SVM
65.0%
SVM (Dimension Reduction)
60.0%
SVM (Optimized Parameter )
55.0%
SVM (Optimized Parameter , Dimension Reduction)
50.0%
5
10
20
40
80
cluster number
図 5 パラメータ最適化前後の SVM の精度
パラメータ最適化後の結果を見ると,パラメー
タを最適化しない場合に比べて大きく精度が向
上している.次元削減についても,わずかなが
らではあるが精度にも良い影響を与えているこ
とが確認できた.
4. まとめ
本稿では,あるクラスタリングの結果から得
られた識別境界を推定するための 3 つの処理フ
ローから構成される手法について検討を行った.
その結果,クラスタ数 k が大きいほどクラスタ
再現問題の複雑度合いが高まることがわかった.
広い範囲のクラスタ数をカバーするためには,
分類器はパラメータを最適化した SVM が望まし
く,次元削減は認識処理の処理速度の観点から
も実施するのが適切であるとの判断を得ること
ができた.今後の課題として,提案手法を組み
込んだ情報推薦サービスを作成し,興味文書が
再現できるかどうかについて,ユーザテストを
通じて検証を行う必要がある.
参考文献
[1] 入札情報検索サービス K-Finder
http://www.kurimoto-tech.net/k-finder/
[2] 小俣尚泰,関根聡一:入札情報の探索を目的とする
Web 検索エンジンの開発,日本データベース学会論
文誌 Vol.9, No.3, pp.1-6, 2011.2
1-516
Copyright 2012 Information Processing Society of Japan.
All Rights Reserved.
Fly UP