本研究は、Webユーザの行動を記録した大規模のウェブアクセスサーバのアクセスログを解析できる並列ウェブマイニングプラットフォームの開発に関して、標準ハードウェアから成る大規模PCクラスタ上での実装と性能評価を中心に研究した成果をまとめたものである.

近年、World　Wide　Web（以下Webと略する）の急速な発展でWeb全体の構造やコンテンツおよびWebを利用するユーザの行動を解析するウェブマイニングが注目されている．ウェブマイニングはウェブデータを解析するデータマイニング技術と定義されている．本研究では、主にユーザ行動を記録する大規模のアクセスログを対象にしている．

今日のウェブサイトは基本的には静的なWebページを用意しておき、全てのアクセスに対して同一のページを提供しているが、当該ユーザにとって必要な情報だけをそのユーザのコンテキストに合わせて、選別して提供する技術、すなわち、パーソナリゼーション技術が重要になってくる．さらに携帯電話をはじめとするモバイルデバイスからのインターネット利用が急激に増加しており、個別ユーザに合う先読み及びキャッシュも不可欠である．

そのためにウェブログ等に蓄積されているユーザ履歴から有用なアクセスパターンの発掘が必要不可欠だが，その処理は多くの計算量を要する．Yahooは一日のユーザログは約40GBに上ると1999年5月のWWW8国際会議で発表している．ユーザのアクセスパターンを抽出するには少なくとも1カ月程度のログデータのマイニングが不可欠であるから、1TB以上の大容量データということになる．

そのようなタスクを処理できる並列プラットフォームとして，コストパフォーマンスの高いPCクラスタ上で，ウェブアクセスパターンマイニングシステムを提唱し，実際に構築した．システム設計で，データマイニングエンジンとしてPCクラスタを組み合わせることで柔軟性の向上，スケラビリティー及び応答時間短縮という目的が達成できる．

また、大規模なウェブサイトにはバックボーンデータベースからウェブページを生成する動的ページが主流になりつつあるが、メタデータによるCGIパラメータ抽出とデータベーススキーマ設計で動的ページのアクセスログにも対応できるようになっている．

プラットフォームの中心となるものはpattern-growthという現代最頻出パターンマイニングアルゴリズムのパラダイムに基づく並列アルゴリズムである．そのパラダイムの代表的なFP-growthという頻出パターンマイニングアルゴリズムは、トランザクションデータベースをFP-treeというメモリ上データ構造に圧縮することで、それまで発表されたアルゴリズムよりはるかに高速であることが示された．しかしツリーような特殊なデータ構造の並列実行は、PCクラスタのような無共有型並列計算機では、特に困難である．本研究では、投入されるノード数に得られる高速化、いわゆる台数効果を向上させるために、並列実行単位の粒度を予測できるpath depthと呼ばれるパラメータを活用して、実行ノード間の負荷を均等化する新たなメカニズムを開発し、32台の実行ノードで23倍高速化されたことを図2（右）で示されている．図2（左）に従来の並列アルゴリズムであるHPAに比較した結果では一桁以上高速化されている．

さらにPCクラスタ上の実装では、ツリー構造がメモリ上に収めなければならないという制約のため、PCクラスタノードに分散したツリー構造に消費される全体メモリがシステムのスケラビリティーを決定する要因である．その全体メモリの最適化として、共通のアイテムヘッダーを持つツリー枝の動的な移送も提案した．またパソコン技術の急速な進歩により、PCクラスタを構成するノードを追加する際には新ノードが必ずしも同様の構成が得られるわけではなく、CPU能力の異なるパソコンが混在するヘテロ環境になるのである．そのような環境下で、すべてのノードに従来のアルゴリズムを実行すると旧ノードがシステム全体のボトルネックになりかねず、異なる構成に応じる負荷分散が必要になる．提案されたメカニズムはヘテロ環境にも対応できることになっている．

頻出パターンマイニングに時系列という制約を加えたウェブアクセスパターンマイニングも同じフレームワークで実現できるが、従来の方式では、通信量が大きくなり、効率が悪化する．良好な台数効果を得るために通信圧縮の新しい方式も開発した．従来の方式では一つのユーザセッションでindex.htmlが繰り返し訪れられるような複製アイテムに対して新たなサブデータベースを生成し、他ノードに送信するが、直接、ツリーのノードにあるアイテムのカウントに反映することにより、余分なサブデータベース生成を回避できた．

抽出されたウェブアクセスパターンの数が通常、膨大のため、人間が直感的に理解しやすいようにユーザ行動可視化ツールNavizをプラットフォーム上実装した．Navizはユーザのアクセスパターンの関連性をノードの配置パラメータとすることで複雑な解析結果を直感的に理解することができるだけではなく、様々な検索条件の下で個々ユーザアクセスパターンを追跡・比較することもできる．

プラットフォームの実応用としてNTT研究所のモバイルインフォサーチ(MIS)及び（株）NTT番号情報のi-Townpageサイトにおける実ウェブログを対象にしたマイニングを行った．I-Townpageログマイニング応用として問合わせ拡張による推薦システムも開発した．そのシステムはi-Townpageの業種階層構造を考慮してアクセスパターンのクラスタによる推薦を行っている．

ウェブマイニングシステム

HPAとの比較（左）台数効果（右）

本論文は「Parallel Platform for Large Scale Web Usage Mining(大規模ウェブログマイニングの為の並列プラットフォームに関する研究)」と題し，Webユーザの行動を記録した大容量ウェブアクセスログを解析するための並列ウェブマイニングプラットフォームの構築法を明らかにすることを目的とし、ウェブログマイニングの効率の良い並列アルゴリズムを提案するとともに、PCクラスタ上に当該アルゴリズムを実装、性能評価することによりその有効性を明らかにしており、8章から構成される．

第1章は”Introduction”（序論）であり、本研究の背景、目的、及び位置付けについて述べている．

第2章は”Web Usage Mining”（ウェブログマイニング）と題し、ウェブマイニングにおける既存の関連研究、アクセスログのマイニング処理全体の概要、および頻出パターンマイニング、時系列パターンマイニング等の代表的なマイニング技術を説明している．

第3章は“PC Cluster Based Web Usage Mining Platform”（PCクラスタ上のウェブログマイニングプラットフォーム）と題し、大規模アクセスログの柔軟な処理を可能とするための高性能プラットフォームに対する要件を整理し、当該用件を満たすPCクラスタによるウェブマイニングシステムの構成を提案している。

第4章は“Parallel Algorithm to Mine Frequent Patterns”（頻出パターンマイニングの並列アルゴリズム）と題し、頻出パターンマイニングアルゴリズムFP-growthの並列化手法を提案している．FP-growthは、トランザクションデータベースをFP-treeと呼ばれる主記憶上データ構造に圧縮し展開することにより、広く利用されてきたAprioriアルゴリズムに比べ、大幅な高速化を達成しているが、木状の複雑なデータ構造を操作するため、PCクラスタ等の無共有型並列計算機上での並列化は困難と考えられ従来試みられて来なかった。本章では、FP木に基づく新しい並列アルゴリズムを提案している。粒度を実行時に調整可能とし、ノード間の動的負荷分散機構を提案している．加えて、FP-tree枝の重複を減らし、実行時メモリ消費量を最適化する手法も提案している。

第5章は“Parallel Algorithm to Mine Web Access Sequence Patterns”（並列ウェブアクセスシーケンスパターンマイニングの並列アルゴリズム）と題し、時系列パターンの一種であるウェブアクセスパターン(WAP)の並列マイニング手法を提案している．第4章で提案された手法を拡張し、WAP-treeのノードにあるアイテムのカウント情報を直接操作する新しい高速なシーケンスマイニングアルゴリズムを提案している。

第6章は“Performance Evaluation of Parallel Algorithms on PC Cluster”（PCクラスタ上の並列アルゴリズム性能評価）と題し、第4章と第5章で提案された並列ウェブマイニング方式をPCクラスタ上で実装し、性能評価の結果を詳細な実行トレースを解析することにより、提案手法の有効性を定量的に明らかにしている．頻出パターンマイニングの場合，アプリオリを基本とする従来の並列アルゴリズムHPAに比べ一桁以上高速化されており、32台の実行ノードで23倍の高速化が達成出来ることを示している．叉、動的にFP-treeを再構築しメモリ消費量を最適化することにより、16ノード以上の場合において、30％以上のメモリ空間の節約が可能であることが示されている．

第7章は“Applying the Platform on Logs of Location Aware Portal Sites”（位置情報サービスポータルサイトのログへの適用）と題し、提案されたプラットフォームを位置情報ポータルサイトMobile Info Search(MIS)及び電話番号情報サイトiTOWNPAGEのアクセスログに適用することにより推薦システムなどを構築し、提案したウェブマイニングシステムの有効性を明らかにしている．

第8章 “Conclusion”（結論）は、本論文の成果と今後の課題について検討している.

以上これを要するに，本論文は，大規模ウェブログマイニングを可能とするPCクラスタを用いたプラットフォームの構築を目的とし、FP木に基づく新しい並列頻出パタンマイニングアルゴリズムを提案するとともに、実装によりその高い性能を確認し、実際の大容量アクセスログを用いることにより提案プラットフォームの有効性を明らかにしており，電子情報工学上貢献するところが少なくない．

よって本論文は博士（工学）の学位請求論文として合格と認められる．