入札情報推薦のための 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）の３つの処理手順で構成され
ており，識別関数には 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 の２種類
を使用し，その精度を測定した．また，それぞ
れの分類器に対して，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.