(57)【要約】【課題】  ウェブ文書のクラスタリングの精度と効率を大幅に高めることができるウェブ文書クラスタリング方法およびシステムを提供する。【解決手段】  ウェブ文書クラスタリング方法およびシステムが提供される。ウェブ文書クラスタリング方法は、複数のウェブ文書を入力するステップと、入力されたウェブ文書のリンク情報とディレクトリ構造情報とを収集するステップと、収集されたリンクとディレクトリ構造に基づいて、前記複数のウェブ文書の階層構造を抽出するステップと、抽出された階層構造に基づいて、前記複数のウェブ文書から成る１つ以上のクラスタを生成して出力するステップとを含む。【選択図】  図１
2009104591.tif 000002
【特許請求の範囲】
【請求項１】
複数のウェブ文書を入力するステップと、
入力された前記ウェブ文書のハイパーリンクとディレクトリ構造に関する情報を収集するステップと、
収集された前記ハイパーリンクと前記ディレクトリ構造とに基づいて、前記複数のウェブ文書の階層構造を抽出するステップと、
抽出された前記階層構造に基づいて、前記複数のウェブ文書からなる少なくとも１のウェブ文書クラスタを生成して出力するステップと
を備えることを特徴とするウェブ文書クラスタリング方法。
【請求項２】
生成したウェブ文書クラスタ間の階層関係を出力するステップを含むことを特徴とする請求項１に記載のウェブ文書クラスタリング方法。
【請求項３】
前記階層構造を抽出した後、入力した前記各ウェブ文書のリンクコレクションを分析することにより、前記階層構造を訂正するステップをさらに含むことを特徴とする請求項１に記載のウェブ文書クラスタリング方法。
【請求項４】
前記階層構造を抽出するステップが、
収集した前記ディレクトリ構成に従って第１の階層構造を確定するステップと、
複数の前記ウェブ文書間の前記第１の階層構造に含まれないウェブ文書について、前記ウェブド文書のリンクに従って第２の階層構造を確定するステップと、
前記第１の階層構造と前記第２の階層構造を結合して最終的な階層構造を確定するステップを含むことを特徴とする請求項１に記載のウェブ文書クラスタリング方法。
【請求項５】
前記第１の階層構造における祖先−子孫関係の判定において、
ウェブ文書Ａがインデックス文書で、当該ウェブ文書Ａのディレクトリパスがウェブ文書Ｂあるいはウェブ文書Ｂの祖先のディレクトリパスと同じである場合、前記ウェブ文書Ａを前記ウェブ文書Ｂの祖先として判定し、
前記第２の階層構造における祖先−子孫関係の判定において、
ウェブド文書Ｂのインバウンドリンク集合がウェブ文書Ａのアウトバウンドリンク集合の部分集合である場合、前記ウェブ文書Ａを前記ウェブ文書Ｂの祖先として判定することを特徴とする請求項４に記載のウェブ文書クラスタリング方法。
【請求項６】
階層構造を抽出する処理において、収集したリンク内のリンクノイズを取り除くステップをさらに含むことを特徴とする請求項１に記載のウェブ文書クラスタリング方法。
【請求項７】
各クラスタは、中心的ウェブ文書及び前記階層構造において前記中心的ウェブ文書の子孫であるウェブ文書を含むことを特徴とする請求項１に記載のウェブ文書クラスタリング方法。
【請求項８】
複数のウェブ文書を入力する入力手段と、
入力された前記ウェブ文書のハイパーリンクとディレクトリ構造に関する情報を収集する収集手段と、
収集された前記ハイパーリンクと前記ディレクトリ構造とに基づいて、前記複数のウェブ文書の階層構造を抽出する抽出手段と、
抽出された前記階層構造に基づいて、前記複数のウェブ文書からなる少なくとも１以上のクラスタを生成して出力する出力手段と
を備えることを特徴とするウェブ文書クラスタリングシステム。
【請求項９】
前記出力手段が、さらに、生成したウェブ文書クラスタ間の階層関係を出力することを特徴とする請求項８に記載のウェブ文書クラスタリングシステム。
【請求項１０】
前記抽出手段と前記出力手段の間に、前記階層構造を抽出した後、入力した前記各ウェブ文書のリンクコレクションを分析することにより、前記階層構造を訂正する訂正手段をさらに備えることを特徴とする請求項８に記載のウェブ文書クラスタリングシステム。
【請求項１１】
前記抽出手段が、
収集した前記ディレクトリ構成に従って第１の階層構造を確定し、
複数の前記ウェブ文書間の前記第１の階層構造に含まれないウェブ文書について、前記ウェブド文書のリンクに従って第２の階層構造を確定し、
前記第１の階層構造と前記第２の階層構造を結合して最終的な階層構造を確定することを特徴とする請求項８に記載のウェブ文書クラスタリングシステム。
【請求項１２】
前記第１の階層構造における祖先−子孫関係の判定において、
ウェブ文書Ａがインデックス文書で、当該ウェブ文書Ａのディレクトリパスがウェブ文書Ｂあるいはウェブ文書Ｂの祖先のディレクトリパスと同じである場合、前記ウェブ文書Ａを前記ウェブ文書Ｂの祖先として判定し、
前記第２の階層構造における祖先−子孫関係の判定において、
ウェブド文書Ｂのインバウンドリンク集合がウェブ文書Ａのアウトバウンドリンク集合の部分集合である場合、前記ウェブ文書Ａを前記ウェブ文書Ｂの祖先として判定することを特徴とする請求項１１に記載のウェブ文書クラスタリングシステム。
【請求項１３】
階層構造を抽出する処理において、収集したリンク内のリンクノイズを取り除くノイズ除去手段をさらに備えることを特徴とする請求項８に記載のウェブ文書クラスタリングシステム。
【請求項１４】
各クラスタは、中心的ウェブ文書及び前記階層構造において前記中心的ウェブ文書の子孫であるウェブ文書を含むことを特徴とする請求項８に記載のウェブ文書クラスタリングシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ウェブ情報の抽出・マイニング技術に関し、特にウェブ文書クラスタリング方法およびシステムに関する。
【背景技術】
【０００２】
ＷＷＷ（Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ）は、今や、情報の発信と収集に欠かせない媒体として広く普及している。ＷＷＷを介してやり取りされる情報は、量が膨大、内容が多様、異種データの混在、配布が容易といった特徴を有する一方で、大部分が暗黙的であるという特徴も併せ持つ。こうした中、ウェブ情報の抽出・マイニング技術は、人々がウェブと情報を最大限に利用する上できわめて重要な技術として知られている。事実、ウェブ情報の抽出とマイニングはすでに最も注目を集める研究分野の１つとなっており、これらの技術をベースとしたアプリケーションや製品も市場で人気を集めている。
【０００３】
ドキュメントクラスタリング、すなわち文書のクラスタリングは、一般的情報のマイニング技術の一種であり、文書間の類似度と関係を利用する手段として使用されている。ドキュメントクラスタリングでは、高い類似度や強い関係を有する文書は同じグループに属し、異なるグループに属する文書間には大きな隔たりがあるようにして、複数の意味のあるグループが作成される。グループ化処理は自動的に実行されるが、グループの事前定義は行われない。クラスタリングを実行すると系統的に編成された文書集合が得られることから、ドキュメントクラスタリングは、情報検索などの情報抽出システムの効率性と効果を向上させるためや、検索結果を閲覧しやすいように編成する目的で広く利用されている。ウェブの情報量は膨大なので、クラスタリングは、ウェブドメイン内の情報抽出を効率的かつ高精度に行えるようにする上でとりわけ重要な役割を果たしている。
【０００４】
ウェブ文書をクラスタ化する目的は、事前に選択したウェブ文書集合をいくつかの意味のあるグループに自動的に分割することである。このとき、グループの事前定義は行われない。また、同じグループに属する文書間の類似度または関係が、異なるグループに属する文書間のそれよりもはるかに高くなるようにグループ化される。しかし、類似度と関係は測定基準によって定義のされ方が異なるため、クラスタ分析の対象が同じ文書集合の場合でも、どの側面に注目するかによって結果は異なったものとなる。例えば、企業のウェブサイトに含まれる製品関連のウェブページの場合であれば、クラスタリングは、コンテンツのタイプに応じてニュースのページ、広告のページ、ショッピングのページ等にグループ化する場合や、製品カテゴリに応じてこれらのページを複数の製品クラスタ（１つのクラスタは、同一製品に関する全ページで構成される）にグループ化する場合などに使用される。そのため、ウェブ文書のクラスタリングにおいては、使い勝手がよく、なおかつ高精度で効率的なクラスタリング方法をデザインする方法が一般的な問題となっている。
【０００５】
技術的には、ドキュメントクラスタリング方法をデザインする際の主要プロセスは、（１）そのクラスタリングの目的に適しており、かつ高効率を期待できる文書特徴を選択する、そして（２）これらの文書特徴に基づいてクラスタリングメカニズムをモデル化する、という２つの作業で構成される。以下では、この２つの側面から既存の技術的解決策を検討する。
【０００６】
特徴選択の側面では、ウェブ文書のクラスタリングにおける既存の解決策は、クラスタリングに使用する特徴の種類によって、（１）文書のコンテンツに基づくクラスタリング、（２）ハイパーリンク情報に基づく（コンテキストに基づく）クラスタリング、（３）ウェブ利用情報に基づくクラスタリング、（４）ハイブリッドクラスタリング、という４つのカテゴリに分類できる。従来の解決策において最も一般的なのは、コンテンツに関連する特徴（すなわち、文書内のテキスト情報）を使用するドキュメントクラスタリング方法である。ウェブ文書のクラスタリングの場合は、コンテンツに関連する特徴には、コンテンツのテキスト情報に加えて、ウェブページのＨＴＭＬ構造も含まれる。さらに、ウェブの中心的な特徴はハイパーリンクなので、ウェブ文書のクラスタリングにおいては、リンク関連情報がコンテンツ関連情報と同等かそれ以上に重要となる。そのため、ハイパーリンク情報に基づくドキュメントクラスタリングはますます多く利用されるようになっている。また、閲覧履歴、閲覧パスといったウェブユーザの利用情報の記録が可能なことから、利用情報を利用してウェブ文書間の関係を評価する解決策もある。しかし、ウェブ文書のコンテンツのみを考慮する場合は、ウェブページの多くはテキスト情報を少ししか含まず、ＨＴＭＬ構造も不規則なため、通常のケースでは情報量が不足する。一方、ハイパーリンク情報やウェブ利用情報のみを考慮する場合には、リンクや閲覧行動の多くは無作為で主観的なため、意味のある情報が得られない。そのため、一般的ウェブ文書のクラスタリングでは、通常ハイブリッド解決策がデザインされる。
【０００７】
クラスタリングメカニズムのモデル化の側面から見た場合、既存のほぼすべての解決策はピアツーピア解析モデルをベースとしている。これらの解決策は、具体的には、文書間の類似度（通常は類似度スコアで表される）を直接または間接的に解析し、その結果に従って文書をクラスタリングする（類似度の高い文書をグループ化してクラスタにする）ためのアルゴリズムをデザインする。具体的な類似度解析モデルは、ルールに基づいて設定されるか、もしくは機械学習を利用して設定される。
【０００８】
以下に、従来技術の代表的な解決策をいくつか紹介する。
【０００９】
非特許文献１（Ｖ．Ｃｒｅｓｃｅｎｚｉ，Ｐ．Ｍｅｒｉａｌｄｏ，Ｐ．Ｍｉｓｓｉｅｒ．Ｃｌｕｓｔｅｒｉｎｇ  ｗｅｂ  ｐａｇｅｓ  ｂａｓｅｄ  ｏｎ  ｔｈｅｉｒ  ｓｔｒｕｃｔｕｒｅ（ウェブページの構造に基づくクラスタリング）．Ｄａｔａ＆Ｋｎｏｗｌｅｄｇｅ  Ｅｎｇｉｎｅｅｒｉｎｇ  ５４（２００５）２７９−２９９）では、データ集約型ウェブサイトのページをクラスタ化するための解決策として、リンクコレクション（同じレイアウトと表現特性を有する同一ページ上のリンクの集合）とページのドキュメントオブジェクトモデル（ＤＯＭ）構造を解析する方法が示されている。サイトへのエントリポイントは、単一のシードページである。シードページは最初のクラスのメンバーとなり、そのページのリンクコレクションが抽出されて優先待ち行列に取り込まれる。その後、待ち行列から１つのリンクコレクションが選択されて、これらのリンクがポイントするページの部分集合を取り込むステップが実行され、待ち行列が空になるまでこれが繰り返される。取り込まれたページは、ページ構造の類似度（ページ構造のＤＯＭツリーに関して定義される）に従ってクラスタ化される。その候補クラスはモデルに新規追加すべきものか、あるいは既存のクラスと併合すべきものかについて判定する方法としては、最小記述長（ＭＤＬ）の原理が採用されている。
【００１０】
非特許文献２（Ｘ．Ｈｅ，Ｈ．Ｚｈａ，Ｃ．Ｈ．Ｑ．Ｄｉｎｇ，ｅｔｃ．Ｗｅｂ  ｄｏｃｕｍｅｎｔ  ｃｌｕｓｔｅｒｉｎｇ  ｕｓｉｎｇ  ｈｙｐｅｒｌｉｎｋ  ｓｔｒｕｃｔｕｒｅｓ（ハイパーリンク構造を使用したウェブ文書のクラスタリング）．Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｓｔａｔｉｓｔｉｃｓ＆Ｄａｔａ  Ａｎａｌｙｓｉｓ  ４１（２００２）：１９−４５）では、ウェブページのクラスタリングに使用する基本的特徴はハイパーリンク構造であり、テキスト情報と共用引用情報もその中に結合される。このクラスタリングは、相互にリンクが張られたページはそうでないページよりも類似度が高いことを中核的概念とし、クラスタリング問題はリンクグラフ分割問題に変換される。リンク構造からの類似度重みは、テキスト情報の類似度情報によって調整され、２つのページが共用引用されている場合はこの重みが増大される。
【００１１】
さらに、特許文献１［特開２００４−３４１９４２号公報］では、ＵＲＬから取り込んだドメイン名、ディレクトリ名、ファイル名に基づいて２文書間の類似度を解析することによって、ウェブ文書のクラスタリングを行う。
【００１２】
本発明に対する理解を深めるため、上記文献の開示内容のすべてが、そのあらゆる趣旨においてここに援用される。
【特許文献１】特開２００４−３４１９４２号公報
【非特許文献１】Ｖ．Ｃｒｅｓｃｅｎｚｉ，Ｐ．Ｍｅｒｉａｌｄｏ，Ｐ．Ｍｉｓｓｉｅｒ．Ｃｌｕｓｔｅｒｉｎｇ  ｗｅｂ  ｐａｇｅｓ  ｂａｓｅｄ  ｏｎ  ｔｈｅｉｒ  ｓｔｒｕｃｔｕｒｅ（ウェブページの構造に基づくクラスタリング）．Ｄａｔａ＆Ｋｎｏｗｌｅｄｇｅ  Ｅｎｇｉｎｅｅｒｉｎｇ  ５４（２００５）２７９−２９９
【非特許文献２】Ｘ．Ｈｅ，Ｈ．Ｚｈａ，Ｃ．Ｈ．Ｑ．Ｄｉｎｇ，ｅｔｃ．Ｗｅｂ  ｄｏｃｕｍｅｎｔ  ｃｌｕｓｔｅｒｉｎｇ  ｕｓｉｎｇ  ｈｙｐｅｒｌｉｎｋ  ｓｔｒｕｃｔｕｒｅｓ（ハイパーリンク構造を使用したウェブ文書のクラスタリング）．Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｓｔａｔｉｓｔｉｃｓ＆Ｄａｔａ  Ａｎａｌｙｓｉｓ  ４１（２００２）：１９−４５
【発明の開示】
【発明が解決しようとする課題】
【００１３】
しかし、これら既存の解決策をもってしても未解決の問題がある。まず、非特許文献１の方法では、データ集約型ウェブサイトに限定してページのクラスタリングを実行することができるが、構造に少しでもノイズがあるウェブサイトの場合には、この方法は適用できない。その理由は、非限定的なデータ集約型の状況では、構造の類似度はトピックやコンテンツの類似度を示唆できないためである。したがって、この方法は限定的すぎ、全体としては十分な精度を確保できないという問題を抱える。非特許文献２の解決策は、学習をベースとするクラスタリングアルゴリズムを使用しているが、サンプルコーパスを収集してタグを付加するための手作業がボトルネックとなり、効率性の面で問題がある。また、サンプルコーパスによって結果にバイアスがかかるという問題や、対象範囲が広すぎるため、ある特定の状況では十分な精度が保証されないという問題もある。逆に特許文献１［特開２００４−３４１９４２号公報］は、対象範囲が限定的すぎて通常の状況に対処できないことが問題となる。これは、圧倒的多数のウェブサイト（特に、パラメータベースのＵＲＬを持つ動的ウェブサイト）においては、ＵＲＬは概して標準的ではなく、意味あるものではないためである。したがって、上記の観察に基づけば、高精度と効率性の不足が既存の解決策に共通する問題点であることが明らかである。
【００１４】
また、クラスタリングの効率性に関して、既存の解決策によって取り組まれていない問題がもう１つある。既存の解決策はすべてピアツーピア類似度解析をベースとしているため、その結果として得られるクラスタは平坦な構造にしかならない。平坦な構造とは、異なるクラスタ内の文書は同じクラスタ内の文書に比較して類似度がはるかに低いということを除けば、異なるクラスタの間に関係がない状態を指す。このようなクラスタリング結果は、単一の側面または単一の階層から見た文書間の類似度しか反映していないので、その類似度側面または階層を他に移行させるためには、クラスタリングの特徴とモデルを大幅に修正しなければならなくなる。例えば、ある企業のウェブサイト上の製品ページに対してクラスタリング解析を行う場合には、製品ごとにページをグループ分けする（１つのクラスタが１つの製品を表す）か、または製品カテゴリごとにページをグループ分けする（１つのクラスタが１つの製品カテゴリを表す）という２通りの方法がある。２つ目のクラスタリング目標は１つ目のクラスタリング目標よりも類似度の階層が高いため、この２つは階層的に関連づけることができる。しかし、既存の解決策では２種類のクラスタリング結果を順次に得ることはできても同時に得ることは不可能なので、相互の関連づけを自動的に行うことができない。したがって、これらのクラスタリング方法は全体として見ると効率性に欠けているといわざるを得ない。
【００１５】
（発明の目的）
【００１６】
本発明は、従来技術におけるクラスタリング方法が抱える、精度と効率性が低いという問題を解決することを目的とする。
【課題を解決するための手段】
【００１７】
本発明の一態様によれば、ウェブ文書クラスタリング方法であって、複数のウェブ文書を入力するステップと、入力されたウェブ文書のハイパーリンクとディレクトリ構造に関する情報を収集するステップと、収集されたハイパーリンクとディレクトリ構造とに基づいて、前記複数のウェブ文書の階層構造を抽出するステップと、抽出された階層構造に基づいて、前記複数のウェブ文書から成る１つ以上のクラスタを生成して出力するステップとを備えることを特徴とするウェブ文書クラスタリング方法が提供される。
【００１８】
本発明の他の態様によれば、ウェブ文書クラスタリングシステムであって、複数のウェブ文書を入力する入力手段と、入力されたウェブ文書のハイパーリンクとディレクトリ構造に関する情報を収集する収集手段と、収集されたハイパーリンクとディレクトリ構造とに基づいて、前記複数のウェブ文書の階層構造を抽出する抽出手段と、抽出された階層構造に基づいて、前記複数のウェブ文書から成る１つ以上のクラスタを生成して出力する出力手段とを備えることを特徴とするウェブ文書クラスタリングシステムが提供される。
【００１９】
本発明の基本的な実施例においては、従来技術と同様に、ウェブ文書のクラスタリングを行うための基本的特徴として、ウェブサイト上のウェブページ間におけるハイパーリンク関係が採用されている。ただし、本発明は、ハイパーリンク関係を利用して、ウェブ文書集合の階層（祖先−子孫）構造のマイニングと抽出を行ってクラスタリングを実行するという点で従来技術と異なる。一方、階層的祖先−子孫構造の抽出に関しては、本発明はハイパーリンク関係をベースとする解析アルゴリズムを採用している。このアルゴリズムとは、具体的には、２文書間のインバウンドリンク集合とアウトバウンドリンク集合との比較に基づいて、ウェブページ間の階層的祖先−子孫関係を抽出し、これらの文書がドメインディレクトリ構造を有する場合には、ハイパーリンク関係に基づいてそのディレクトリ構造を解析結果に直接結合することにより、最終的な階層構造を得るアルゴリズムである。本発明の一実施例においては、生成される階層構造は文書ツリーである。この文書ツリーは、その後の文書のクラスタリングに使用される。この文書ツリーでは、階層構造内の深度にかかわらず、各文書はその子孫と共にクラスタを構成する。そのため、クラスタ間の階層関係は、文書ツリー全体に存在するノードの関係を反映したものとなる。端的には、本発明のクラスタリング方法は、クラスタリングを実行するだけでなく、クラスタ間の階層関係も自動的に取得するのである。
【００２０】
さらに、本発明ではインバウンドリンク集合とアウトバウンドリンク集合間のインクルード関係が文書のクラスタリングを行うための特徴として利用されるため、無作為もしくは意味のないハイパーリンク情報による混乱が減少し、クラスタリング結果の精度が大幅に向上する。一方、この特徴は学習ではなく単純なルールに基づいて利用されるため、十分な効率性が確保される。
【発明の効果】
【００２１】
上記のように、本発明によるクラスタリング結果にはクラスタに加えてクラスタ間の階層関係も含まれるため、本発明の方法によれば、類似度レベルの異なるクラスタリング結果を同時に取得して相互に関連付けることが可能になる。これにより、全体的な効率性が向上する。
【００２２】
さらに、本発明において生成される文書集合の階層構造（すなわち、文書ツリー）を任意の付加的な結果として使用すると、他のウェブ情報抽出タスクを実現することも可能になる。
【００２３】
本発明の上記および他の特徴と利点は、図面を参照しながら下記の詳細な説明を読むことによりさらに明白となるであろう。ただし、本発明の範囲は、本書で説明する特定の具体例または実施例に限定されないことに留意されたい。
【発明を実施するための最良の形態】
【００２４】
以下では、添付図面を参照して、本発明の例示的実施例を説明する。ただし、ここで説明する実施例は例示を唯一の目的とするものであり、本発明はこれら特定の実施例に限定されるものではない。
【００２５】
図１は、本発明の第１の実施例によるウェブ文書クラスタリングシステム１００を示すブロック図である。図示するように、システム１００は、入力手段１０１と、収集手段１０２、抽出手段１０３と、出力手段１０４と、ウェブ文書ベース１０５とを含む。システム１００は、入力手段１０１を使用してウェブ文書ベース１０５から複数のウェブ文書を取得し、一連の処理の後、その結果得られたこれらのウェブ文書のクラスタとクラスタ間の階層関係とを出力手段１０４から出力する。ウェブ文書ベース１０５は、ウェブクローラ＆ウェブページ解析モジュール（図示せず）によってネットワークから取得したウェブ文書のコレクションを格納する。
【００２６】
次に、図２を参照して、図１に示すウェブ文書クラスタリングシステム１００の動作プロセスを説明する。図２は、図１に示すウェブ文書クラスタリングシステムの動作２００の一例を示すフローチャート図である。プロセス２００は、入力手段１０１による複数のウェブ文書の入力から始まる（ステップ２０１）。続いてステップ２０２において、収集手段１０２は、リンク関係とこれらのウェブ文書のディレクトリ構造に関する情報を収集する。収集されたリンク関係とディレクトリ構造の情報は、階層構造を抽出するための直接ソースデータとして抽出手段１０３に供給される。収集されたリンク関係とディレクトリ構造の情報を受け取った抽出手段１０３は、ステップ２０３において、これらのウェブ文書を解析して祖先−子孫関係を導出することにより、ウェブ文書のコレクション全体の階層構造を抽出する。続いてステップ２０４において、出力手段１０４は、抽出手段１０３によって生成された階層構造を使用してウェブ文書をクラスタ化し、同時に、生成したクラスタ間の階層関係を取得する。これでプロセス２００は終了する。
【００２７】
前述したように、ウェブ文書に関するハイパーリンク情報やディレクトリ構造情報などの直接的で明示的な関係情報は、ウェブ文書の階層構造の抽出に必要な直接ソースデータであり、階層構造の抽出に有効な特徴とみなされる。そのため、本発明においては、必要なハイパーリンク情報とディレクトリ構造情報を入力されたウェブ文書から抽出・収集することが重要な前処理となる。以下では、この前処理について詳細に説明する。
【００２８】
まず、ウェブ文書のディレクトリ構造は、ウェブ文書のＵＲＬに含まれるウェブサーバの階層的ディレクトリ構造を調べて取得することにより抽出することができる。例えば、ディレクトリ構造において、ｈｔｔｐ：／／ｗｗｗ．ａｂｅ．ｃｏｍ／ｄのＵＲＬを有する文書がｈｔｔｐ：／／ｗｗｗ．ａｂｃ．ｃｏｍ／ｄ／ｅ．ｈｔｍｌのＵＲＬを有する文書の親であるとする。ディレクトリ構造情報の抽出は、ウェブ文書ＵＲＬのペアごとにルールに基づく判定を実行することによって行う。１つのＵＲＬはディレクトリパスとファイル名という２つの部分で構成されることは、既知の事実である。例えば、ｈｔｔｐ：／／ｗｗｗ．ａｂｅ．ｃｏｍ／ｄ／ｅ．ｈｔｍｌというＵＲＬであれば、ディレクトリパスはｈｔｔｐ：／／ｗｗｗ．ａｂｃ．ｃｏｍ／ｄ、ファイル名はｅ．ｈｔｍｌである。この例では、ＵＲＬのファイル名以外の部分を、当該ＵＲＬのディレクトリパスのインデックスドキュメントとみなすこととする。ｉｎｄｅｘ．＊、ｄｅｆａｕｌｔ．＊、ｈｏｍｅ．＊のような特別な意味を示すファイル名を有する文書も、同様にインデックスドキュメントとみなす。そして、これに基づいて、ディレクトリ構造において文書Ａは文書Ｂの祖先であり、Ａはインデックスドキュメントであり、ＡはＢと同じディレクトリまたは祖先ディレクトリパスを有する、というルールを定義する。ウェブ文書集合の抽出済みディレクトリ構造情報は、２要素集合｛（祖先，子孫）｜「祖先，子孫」は当該ウェブ文書集合に含まれ、ディレクトリ構造において「祖先」は「子孫」の祖先である｝として設定される。ここで、ディレクトリ構造における祖先−子孫関係を定義するための上記ルールは一例にすぎないことに留意する必要がある。当該技術に精通する当業者には、他のルールを使用して、ウェブサーバ上に格納されるディレクトリ構造に基づいて、ウェブ文書間の祖先−子孫関係を抽出できることは容易に理解されるであろう。
【００２９】
ディレクトリ構造情報は階層的であり、すでにウェブ文書集合の階層情報の一部を反映しているため、階層構造抽出作業では、ディレクトリ構造に祖先−子孫関係が示されていないウェブ文書の間に祖先−子孫関係があるかどうかを判定する（すなわち、暗黙的な階層構造を抽出する）だけでよい。本発明の一実施例においては、これはウェブ文書間のハイパーリンク関係を解析することで達成できる。
【００３０】
ハイパーリンクは、１つの文書から別の文書に到達するためのナビゲーションリンクである。前者の文書は「リンク元文書」と呼ばれ、後者の文書は「リンク先文書」と呼ばれる。ハイパーリンクは、リンク元文書とリンク先文書との間のコンテキスト上またはコンテンツ上のつながりを示す。ハイパーリンクの抽出は、従来技術ですでに紹介されている任意の手法を用いて実行できる。一例としては、各文書のｈｔｍｌソースコードを解析し、各リンクのＨＴＭＬタグ（＜ａ＞）のｈｒｅｆ値を抽出する手法が挙げられる。そのため、ここではハイパーリンク情報の抽出処理の説明は省略する。ウェブ文書集合の抽出済みハイパーリンク情報は、さらに、２要素集合｛（リンク元，リンク先）｜「リンク元，リンク先」は当該ウェブ文書集合に含まれ、リンク元からリンク先へのハイパーリンクが少なくとも１つ存在する｝の形でも設定される。
【００３１】
同じ主題に関連するウェブ文書で構成されるグループがあるとすると、外部からこのグループへのリンクは、下位文書に張られるよりも上位文書に張られる方がはるかに多く、下位文書に張られるリンクのほとんどは同じグループの他の文書からのリンクであるのが一般的である。本発明では、これに基づいて、文書Ａは文書Ｂの祖先であり、文書Ｂのインバウンドハイパーリンク集合は文書Ａのアウトバウンドハイパーリンク集合の部分集合であると判定する。ここで、ウェブ文書のハイパーリンク関係に基づく階層構造における祖先−子孫関係を定義するための上記ルールは一例にすぎないことに留意する必要がある。当該技術に精通する当業者には、ウェブ文書間のハイパーリンク関係に基づいて階層構造を抽出するために、他のルールも使用できることは容易に理解されるであろう。
【００３２】
上記に基づけば、１つのウェブ文書集合の完全な階層構造は、ウェブ文書のディレクトリ構造に関する解析結果とハイパーリンク関係に関する解析結果とを結合することにより得られる。階層構造は、ウェブ文書集合に含まれるウェブ文書間の祖先−子孫関係を表すために使用できる。例えば、ウェブ文書集合をＳとし、Ｓの階層構造をＨ（Ｓ）とし、Ｓのディレクトリ構造をＤとし、Ｓ内の２つのウェブ文書をＰｉ、Ｐｊとし、Ｐｉのアウトバウンドリンク集合とＰｊのインバウンドリンク集合をそれぞれＯＵＴｉ（Ｓ）、１Ｎｊ（Ｓ）とすると、ＰｉおよびＰｊ間の祖先−子孫関係は次のように定義できる。
（Pi,Pj）∈H(S)⇔（（Pi,Pj）∈D）∨(OUTi(S)⊇INj(S)）
【００３３】
図３は、ウェブ文書の階層構造３００ａの一例を示す。この図には、ウェブページと、階層構造３００ａに基づいて生成されたクラスタ構造３００ｂが示されている。図示するように、ウェブページの階層構造３００ａはツリー形状として構成されている。この図では、ページＡはページＡ１およびＡ２の祖先、ページＡ１はページＡ１１、Ａ１２、およびＡ１３の祖先、ページＡ２はページＡ２１およびＡ２２の祖先、ページＡ１１はページＡ１１１およびＡ１１２の祖先である。
【００３４】
再度図２を見ると、階層構造が抽出された後には、結果はウェブ文書のクラスタリングに直接使用できることが示されている（ステップ２０４）。通常、１つのウェブ文書とその子孫ウェブ文書はすべてある階層の同じ主題に関連しているので、これらの文書は、親ウェブ文書を中心とした文書クラスタとしてグループ化することができる。図３に示すように、例えば、ページＡ１１とその子孫ページＡ１１１およびＡ１１２は、ページＡ１１を中心とするクラスタＡ１１としてまとめることができる。さらに、ページＡ１は、クラスタＡ１１、ページＡ１２およびＡ１３と共に、別のクラスタＡ１を構成することができ、以下同様である。したがって、図３のクラスタ構造３００ｂが示すように、これらの中心的文書の階層構造が直感的な階層的クラスタリング結果を生み出すため、クラスタ構造が得られると同時に、クラスタ間の階層関係も明確な形で取得されるのである。さらに、中間結果（すなわち、ウェブ文書集合の階層構造）もまた、情報抽出に関連する他のタスクに利用可能な副産物とみなすことができる。
【００３５】
図４は、本発明の第２の実施例によるウェブ文書クラスタリングシステム１００ａを示すブロック図である。図１に示す第１の実施例と比較すると、図４のシステム１００ａは訂正手段１０６とノイズ除去手段１０７とをさらに含む点が異なる。訂正手段１０６は抽出手段１０３と出力手段１０４との間に配置されてそれぞれに結合され、抽出手段１０３で生成された階層構造を訂正するために使用される。ノイズ除去手段１０７も抽出手段１０３に結合され、抽出手段１０３と連携して、階層構造抽出プロセスで行われる階層構造抽出の精度を損なう恐れのあるリンクノイズを除去するために使用される。クラスタリングシステム１００ａの他の構成要素は、図１のシステム１００と同じ機能を有するため、ここでは詳細な説明は省略する。
【００３６】
図５は、図４に示すウェブ文書クラスタリングシステム１００ａの動作５００の一例を示すフローチャート図である。図２のプロセスと同様に、プロセス５００は、複数のウェブ文書の入力から始まる（ステップ５０１）。ステップ５０２において、入力されたウェブ文書のハイパーリンク関係とディレクトリ構造が抽出され、収集される。次にステップ５０３において、収集されたハイパーリンク関係とディレクトリ構造に基づいて、これらのウェブ文書の階層構造が抽出される。ここで第１の実施例と異なる点は、階層構造抽出プロセスに、リンクノイズを除去するためのノイズ除去手段１０７が追加されていることである。ここでのリンクノイズとは、下位文書から上位文書に戻るリンクを意味する。これらのリンクは、実際のウェブサイト上でよく行われるウェブ文書のチェックアップをスムーズに行うために設定される。本発明の一例においては、ウェブ文書の階層構造の抽出は反復収束プロセスとして実行される。ノイズ除去手段１０７は、中間階層構造が抽出されるたびに、取得されたハイパーリンク関係から子孫→祖先の逆リンクをすべて除去することで、リンクノイズを除去することができる。これにより改善されたハイパーリンク関係は次の階層構造の抽出に使用され、最終的な階層構造が確定されるまでこれが繰り返される（すなわち、収束）。ただし、本発明はここで説明する例に限定されず、ハイパーリンク関係に含まれるリンクノイズを除去するための他の適切な方法も使用できることは当業者には明らかである。
【００３７】
階層構造内のリンクノイズが除去されても、実際のウェブでは不合理もしくは誤ったハイパーリンクが存在することがあるので、最終的なクラスタにある程度のエラーが含まれる可能性がある。そのため、より適正なクラスタリング結果を得るために、リンクノイズを除去した階層構造は訂正手段１０６に供給され、ここで階層構造のさらなる訂正が行われる（ステップ５０４）。本実施例では、階層構造の訂正はリンクコレクションに基づいて実行される。ただし、階層構造訂正プロセスはここで説明する例に限定されず、当業者は他の階層構造訂正方法を容易に考案することができる。
【００３８】
リンクコレクションとは、同一文書内で同じレイアウトおよび表現特性を有するリンクの集合を意味し、通常はその文書における１つの意味的ブロックとなる。一般に、同一リンクコレクション内のリンクの宛先は同じ意味的階層レベルにあることが多いため、文書作成者の視点からクラスタ化できる可能性が高い。この想定に基づくと、同じリンクコレクション内にあり、階層構造内には存在しないリンクを補完することにより、生成された階層的クラスタリング結果を自動的に訂正することができる。
【００３９】
図６に、リンクコレクションに基づいて階層構造を訂正するプロセスの一例を示す。この図では、抽出手段は階層構造６００ａを抽出している。ここで、ページＰはツリー構造内のページＰ１、Ｐ２、Ｐ３、Ｐ４の親（直接祖先）であり、ページＰ１、Ｐ２、Ｐ３、Ｐ４は集合Ｓｏｎ（Ｐ）を形成する。各文書Ｐとその子（直接子孫）文書において、ＰがリンクコレクションＬＣを有し、その宛先のほとんどがＳｏｎ（Ｐ）内にある場合には、ＬＣの他の宛先もまたＰの息子とみなし、それらを階層構造に含めて補完する。図６に示すように、ページＰのリンクコレクションはページＰ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、およびＰ６を含む。ページＰ１、Ｐ２、Ｐ３、Ｐ４は階層構造内ではページＰの息子として識別されているので、ページＰ５、Ｐ６もまたページＰの息子とみなされる。したがって、ページＰ５、Ｐ６は階層構造６００ａに補完的に取り込まれて、図６に示す訂正済み階層構造６００ｂが生成される。ここで、図６の訂正プロセスは一例にすぎず、本発明はこの特定の例に限定されないことに留意されたい。
【００４０】
図５に戻ると、階層構造の訂正が完了した後、ステップ５０５において、訂正済み階層構造はウェブ文書のクラスタリングに使用されている。これにより、ウェブ文書の最終的なクラスタと、これらのクラスタ間の階層関係が得られる。これでプロセス５００は終了する。
【００４１】
前述では、本発明の第１および第２の実施例に関して説明を行ってきた。以下では、図７を参照して、本発明の応用例を示す。図７の例では、本発明は、企業ウェブサイト上の製品関連ウェブページに対してクラスタリングを実行し、このウェブサイトから製品とそのプロファイル情報を高精度かつ高効率に抽出するために使用されている。
【００４２】
プロセス７００は企業ウェブサイトの入力から始まる（ステップ７０１）。その後、ステップ７０２において、ウェブサイト内のウェブページの最初のフィルタリングが行われる。これにより、会社紹介やニュースなどの無関係なページが除去され、製品関連ウェブページのみが残る。ステップ７０３において、製品プロファイルに関連する可能性の高いページを得るために、残ったウェブページがさらにフィルタリングされる。このフィルタリングでは、プロファイル情報を含まないことが明白な製品関連ページ（例えば、製品リストのページ）が区別して除去される。これら２つのフィルタリングプロセスは、例えばキーワードに基づくフィルタリング方法など、既存の解決策から任意に選んで実行できる。これに続いて行われる製品クラスタリングでは、高精度と高効率を確保するために、クラスタリングへのノイズ情報の導入を予防する措置をとることが有効なのは明白である。
【００４３】
次に、ステップ７０１において、製品プロファイル情報に関連するウェブページの部分集合に対して、本発明の方法によって製品関連文書のクラスタリングが実行される。ステップ７０１には、図５に示す本発明の第２の実施例に対応するサブステップ７０４〜７０７が含まれる。すなわち、最初にステップ７０４において、フィルタリングにより得られたウェブ文書の部分集合のハイパーリンク関係とディレクトリ構造が抽出され、収集される。ここでは、第２の実施例とは異なり、各ウェブページのインバウンドリンクとアウトバウンドリンクはプロファイル関連ページの部分集合内で必ずしも近くに存在しなくてもよく、インバウンドリンクのソース（出発点）とアウトバウンドリンクの宛先（到達点）は製品関連ページの集合全体、すなわちステップ７０２の出力のどこにあってもよい。プロファイル関連文書自体を除くすべての製品関連文書が製品クラスタリングに役立つ手がかりとなることを考慮すると、ステップ７０４をこのようにカスタマイズすることで、ページのクラスタリングの精度が高まることは明らかである。続くステップ７０５では、図５に示すのとまったく同じプロセスを用いて、プロファイルで構成されるウェブページの部分集合の階層構造を抽出することができる。ステップ７０６において、抽出された階層構造が訂正される。ここでは、第２の実施例とは異なり、階層構造の最上層も訂正することが可能である。それは、企業ウェブサイトの全体を使用して、リンクの大部分が最上層文書を宛先とするリンクコレクションが検出されるからである。これにより、階層構造抽出に伴うエラーだけでなく、文書のフィルタリングプロセスに伴うエラーも訂正できるようになり、ウェブページクラスタリングの精度がさらに高まる。その後、ステップ７０７において、訂正された階層構造を使用して製品関連ウェブページが特定される（クラスタリング）。クラスタリングに使用されたウェブページ部分集合にはプロファイル関連ページしか含まれないので、階層構造の最上層の各ページは１つの製品を表し、そのすべての子孫の集合がこの製品の完全なプロファイルとなる。
【００４４】
製品関連ウェブページのクラスタリング完了後、各製品の全プロファイルページに含まれる情報を結合して、完全な製品プロファイルが取得される（ステップ７０８）。ステップ７０９において、クラスタリング結果と共に、その完全なプロファイルが出力される。これでプロセス７００は終了する。上記では本発明の一応用例について説明したが、本発明はこの特定の応用例に限定されないことは容易に理解できる。ネットワーク情報の識別、クラスタリング、解析に係る本発明の他の応用例が可能であることは、当業者には明らかである。
【００４５】
上記では、本発明の第１および第２の実施例によるウェブ文書クラスタリングシステムおよび方法について説明した。本発明のクラスタリング方法では、ウェブ文書の階層構造を抽出することにより、ウェブ文書のクラスタリングを実行できることに加えて、生成されたクラスタの階層関係も自動的に得ることができる。
【００４６】
さらに、本発明はドキュメントクラスタリングを実行するための特徴としてインバウンドリンク集合とアウトバウンドリンク集合の間のインクルード関係を利用するため、無作為かまたは意味のないハイパーリンク情報による混乱が減少し、クラスタリング結果の精度が大幅に向上する。また、この特徴は学習ではなく単純なルールに基づいて利用されるため、十分な効率性が確保される。
【００４７】
さらに、本発明によるクラスタリング結果にはクラスタに加えてクラスタ間の階層関係も含まれるため、本発明の方法によれば、類似度レベルの異なるクラスタリング結果を同時に取得して相互に関連付けることが可能になる。これにより、全体的な効率性が向上する。
【００４８】
上記では、添付図面を参照して本発明の特定の実施例について説明してきたが、本発明は添付図面に示した特定の構成およびプロセスに限定されるものではない。簡素化のため、この説明では、よく知られた方法や手法の説明を省略している。また、実施例の説明では、いくつかの具体的なステップを提示して説明したが、本発明の方法のプロセスはこれらのステップに限定されるものではない。これらのステップは、本発明の精神と実質的な特性から逸脱することなく変更、修正、補完が可能であり、また一部ステップについては順序の入れ替えも可能なことは、当業者には理解されるであろう。
【００４９】
本発明の各要素は、ハードウェア、ソフトウェア、ファームウェア、またはその組み合わせで実装され、システム、サブシステム、そのコンポーネントもしくはサブコンポーネント内で利用される。ソフトウェアで実装された場合、本発明の各要素はプログラムもしくはコードセグメントとして必要なタスクを実行するために使用される。プログラムまたはコードセグメントは、機械読取り可能な媒体に格納することも、あるいは、伝送媒体もしくは通信リンクを介して搬送波内に具現化されたデータ信号により伝送することもできる。「機械読取り可能な媒体」には、情報を格納または伝送できるあらゆる媒体が含まれる。機械読取り可能な媒体の例としては、電子回路、半導体記憶装置、ＲＯＭ、フラッシュメモリ、消去可能ＲＯＭ（ＥＲＯＭ）、フロッピーディスク、ＣＤ−ＲＯＭ、光ディスク、ハードディスク、光ファイバー媒体、無線周波（ＲＦ）リンク等が挙げられる。コードセグメントは、インターネット、イントラネット等のコンピュータネットワークを介してダウンロードすることもできる。
【００５０】
上記では本発明を特定の実施例を参照して説明したが、本発明は上記の特定の実施例や、図面に示した特定の構成に限定されるものではない。例えば、図示した一部のコンポーネントは、互いに組み合わせて１つのコンポーネントとしたり、１つのコンポーネントを複数のサブコンポーネントに分割したり、他の既知のコンポーネントを追加したりすることもできる。また、動作プロセスも同様に、例に示されたものに限定されない。本発明はその精神と主要な特徴から逸脱することなく他の様々な形態で実装できることは、当該技術に精通した当業者により理解されるであろう。したがって、本発明の実施例はあらゆる点において例示的であり、限定的なものではない。本発明の範囲は前述の説明よりむしろ付記した特許請求の範囲に示されており、各請求項と等価な意味と範囲に含まれるあらゆる変更がそれに包含される。
【図面の簡単な説明】
【００５１】
本発明の上記および他の特徴と利点は、図面を参照しながら下記の詳細な説明を読むことにより、より完全に理解することができる。
【００５２】
【図１】本発明の第１の実施例によるウェブ文書クラスタリングシステム１００を示すブロック図である。
【図２】図１に示すウェブ文書クラスタリングシステムの動作２００の一例を示すフローチャート図である。
【図３】ウェブ文書の階層構造に基づいて文書のクラスタリングを実行する場合の一例を示す概略図である。この図では、この処理により生成されるウェブ文書階層構造３００ａとクラスタ構造３００ｂが示されている。
【図４】本発明の第２の実施例によるウェブ文書クラスタリングシステム１００ａを示すブロック図である。
【図５】図４に示すウェブ文書クラスタリングシステムの動作５００の一例を示すフローチャート図である。
【図６】リンクコレクションに基づいて階層構造を訂正するプロセスの一例を示す概略図である。
【図７】企業ウェブサイトの製品に関してウェブ文書のクラスタリングを実行する場合の本発明の応用例を示す図である。
【符号の説明】
【００５３】
１０１：入力手段
１０２：収集手段
１０３：抽出手段
１０４：出力手段
１０５：ウェブ文書ベース
１０６：訂正手段
１０７：ノイズ除去手段
【図１】
2009104591.tif 000003
【図２】
2009104591.tif 000004
【図３】
2009104591.tif 000005
【図４】
2009104591.tif 000006
【図５】
2009104591.tif 000007
【図６】
2009104591.tif 000008
【図７】
2009104591.tif 000009
【外国語明細書】
2009104591000001.pdf