(57)【要約】【課題】文書ページ集合に関して生成されたクラスタリングを評価する方法を提供する。【解決手段】文書ページ集合に関して生成されたクラスタリングを評価する方法において、文書ページ集合を取得するステップと、前記集合内の各文書ページはひとつまたは複数の特徴を有し、前記ひとつまたは複数の特徴はページレイアウト属性を画定し、各文書ページ上の前記ひとつまたは複数の特徴から情報を抽出するステップと、各文書ページ上の前記ひとつまたは複数の特徴に関する特徴ベクトルを構築するステップと、各特徴に特徴重みを割り当てるステップと、前記特徴重みと前記特徴ベクトルに基づいて距離関数を計算するステップと、前記距離関数を使用して前記文書ページ集合をクラスタリングするステップと、を含む。【選択図】図４
2007080263.tif 000002
【特許請求の範囲】
【請求項１】
文書ページ集合に関して生成されたクラスタリングを評価する方法において、
文書ページ集合を取得するステップと、前記集合内の各文書ページはひとつまたは複数の特徴を有し、前記ひとつまたは複数の特徴はページレイアウト属性を画定し、
前記集合から文書ページのサンプルを選択するステップと、
前記文書ページサンプルに関する基準クラスタリングを計算するステップと、
前記サンプル内の各文書ページ上の前記ひとつまたは複数の特徴から情報を抽出するステップと、
各文書ページ上の前記ひとつまたは複数の特徴に関する特徴ベクトルを構築するステップと、
各特徴に特徴重みを割り当てるステップと、
前記文書ページサンプル内のいずれか２ページ間の距離関数を、前記特徴重みと前記特徴ベクトルに基づいて計算するステップと、
前記距離関数をクラスタリングアルゴリズムの中で使用して前記文書ページサンプルをクラスタリングし、前記文書ページサンプルに関して生成されたクラスタリングを取得するステップと、
前記基準ステップを前記生成されたクラスタリングと比較するステップと、
を含むことを特徴とする方法。
【請求項２】
請求項１に記載の方法において、
前記ひとつまたは複数の特徴から抽出された前記情報は、各文書ページ上の段落の数、各文書ページ上の前記段落の総面積、各文書ページ上の前記段落の座標、各文書ページ上の前記段落の幅、各文書ページ上の前記段落の高さ、各文書ページ上の１段落あたりのテキストボックスの数と、各文書ページ上の前記段落のフォントサイズからなるグループから選択される情報であることを特徴とする方法。
【請求項３】
請求項１に記載の方法において、
前記ひとつまたは複数の特徴から抽出された前記情報は、各文書ページ上の画像の数、各文書ページ上の前記画像の総面積、各文書ページ上の前記画像の幅、各文書ページ上の前記画像の高さ、各文書ページ上のＳＶＧ画像の数からなるグループから選択される情報であることを特徴とする方法。
【請求項４】
請求項１に記載の方法において、
前記生成されたクラスタリングと前記基準クラスタリングは異なることがわかり、さらに、
各特徴への前記特徴重みを調整するステップと、
前記文書ページ内のいずれか２ページ間の距離関数を、前記調整された特徴重みと前記特徴ベクトルに基づいて計算するステップと、
前記距離関数をクラスタリングアルゴリズムの中で使用して前記文書ページサンプルをクラスタリングし、前記文書ページサンプルに関する生成されたクラスタリングを取得するステップと、
前記基準クラスタリングを前記生成されたクラスタリングと比較するステップと、
を含むことを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文書ページ集合のクラスタリングに関し、より詳しくは、文書ページ集合を、ページレイアウト属性に基づいてクラスタリングする方法に関する。
【背景技術】
【０００２】
文書集合を概念的に有意味のクラスタに分ける問題については、さまざまな研究がなされている。多くのクラスタリングタスク（clustering task）では、ラベル付与されていないデータは非常に多いが、ラベル付与されたデータは限定的で、生成にコストがかかる。その結果、少ないラベル付きデータを利用して、ラベル付与されていないデータのクラスタリングを支援し、これに偏りをもたせる準教師ありクラスタリング(semi-supervised clustering)が開発された。準教師ありクラスタリングの既存の方法は、制約ベースの方法と距離ベース（距離関数ベース）の方法という２つの一般的手法に分けられる。制約ベースの方法では、クラスタリングアルゴリズムそのものが、利用可能なラベルや制約を使ってデータの適正なクラスタリングの検索に偏りをもたせるように修正される。距離ベースの方法では、距離測度を利用する既存のクラスタリングアルゴリズムが用いられる。ただし、距離測度はまず、教師ありデータの中のラベルまたは制約を満たすように訓練される。文書集合クラスタリングの各種の方法が、“System and Method of Context Vector Generation and Retrieval”と題する米国特許第５，６１９，７０９号、“Method for Document Comparison and Classification Using Document Image Layout”と題する米国特許第６，５４２，６３５号、“System and Method for Quantitatively Representing Data Objects in Vector Space”と題する米国特許第６，５９８，０５４号、“User Interface for Displaying Document Comparison Information”と題する米国特許第６，６５８，６２６号、“System and Method for Quantitatively Representing Data Objects in Vector Space”と題する米国特許第６，９２２，６９９号に記載されている。
【０００３】
【特許文献１】米国特許第５，６１９，７０９号明細書
【特許文献２】米国特許第６，５４２，６３５号明細書
【特許文献３】米国特許第６，５９８，０５４号明細書
【特許文献４】米国特許第６，６５８，６２６号明細書
【特許文献５】米国特許第６，９２２，６９９号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００４】
文書集合をクラスタリングするための従来の試みは一般に、その文書グループから固有の有意味単語を抽出し、これらの単語を特徴として扱い、各文書を、この特徴空間における特定の重み付けされた単語出現頻度のベクトルとして表すことに基づいている。通常、単語数が一般に数千以上の中程度の大きさの文書グループの中でさえも、多数の単語が存在するため、文書ベクトルは非常に高次元のものとなる。したがって、この分野では、意味よりもレイアウトに基づいて文書ページをクラスタリングする方法及びクラスタリングを評価する方法が求められている。準教師ありクラスタリングに距離ベースの手法を用いることにより、文書ページ集合を、文書ページレイアウト属性に基づいて、効率的にクラスタリングすることができる。
【０００５】
本発明は、文書ページ集合に関して生成されたクラスタリングを評価する方法を提供する。
【課題を解決するための手段】
【０００６】
本願で説明する態様によれば、文書ページ集合に関して生成されたクラスタリングを評価する方法において、ある文書ページ集合を取得するステップと（その集合の中の各文書ページはひとつまたは複数の特徴を有し、ひとつまたは複数の特徴は、ページレイアウト属性を画定するものであり）、その集合から文書ページのサンプルを選択するステップと、その文書ページサンプルに関する基準クラスタリングを計算するステップと、そのサンプル中の各文書ページのひとつまたは複数の特徴から情報を抽出するステップと、各文書ページのひとつまたは複数の特徴に関する特徴ベクトルを構築するステップと、各特徴に特徴重みを割り当てるステップと、その文書ページサンプルにおけるいずれか２ページの間の距離関数を、特徴重みと特徴ベクトルに基づいて計算するステップと、クラスタリングアルゴリズムの中でその距離関数を使用してその文書ページサンプルをクラスタリングし、その文書ページサンプルに関する生成されたクラスタリングを得るステップと、基準クラスタリングと生成されたクラスタリングを比較するステップとを含む。
【発明の効果】
【０００７】
本発明によれば、文書ページ集合に関して生成されたクラスタリングを評価する方法を提供することができる。
【発明を実施するための最良の形態】
【０００８】
本実施形態に係る文書ページ集合をクラスタリングする方法を説明する。文書ページ集合をクラスタリングする方法においては、その集合から抽出したある文書ページサンプルに関する基準クラスタリングを計算し、そのサンプル内の文書ページの各々から、ひとつまたは複数の特徴を抽出し、これに重みを割り当て、その文書ページサンプルの中の２ページ間の距離関数を、割り当てられた特徴重みに基づいて計算し、その文書ページサンプルをクラスタリングアルゴリズムに当てはめて、その文書ページサンプルのクラスタリングを生成し、生成されたクラスタリングを基準クラスタリングと比較し、変更が必要であれば、新しい特徴重みを割り当て、学習された特徴重みを使って、その文書ページ集合をクラスタリングアルゴリズムに当てはめる。
【０００９】
文書とは、本実施形態において、視覚的に認知可能なデータを含む印刷物または書込み物および、印刷物または書込み物を生成するのに使用される電子もしくはデータファイルを指す。文書は、ハードコピー、電子文書ファイル、ひとつまたは複数の電子画像、印刷操作による電子データ、電子通信に添付されたファイルあるいは、その他の形態の電子的通信からのデータのいずれでもよい。文書ページ集合または文書ページの集合とは、本願で使用する場合、たとえば、これらに限定されないが、少なくとも２枚（２葉、２個）のページ、シート、ラベル、ボックス、パッケージ、タグ、ボード、看板および、以下に定義する書込み面を含む、または備えるその他の品目を包含する。一般に、文書ページ集合は２ページを超えるページからなる。ある実施例において、文書ページ集合は少なくとも６ページからなる。ある実施例において、文書ページ集合は少なくとも２０ページからなる。また、ある実施例において、文書ページ集合は少なくとも５０ページからなる。書込み面とは、本願において、たとえば、これらに限定されないが、紙、ボール紙、アセテート、プラスチック、織物、金属、木、裏に粘着面を有する資材および同様の表面を含む。
【００１０】
特徴とは、本実施形態において、下記に限定されるものではないが、たとえば、段落、画像（アイコン、グラフィックス、絵、クリップアート）、ページ番号、表およびグラフ等を含む文書に見られる属性を指す。また、特徴から抽出される情報とは、下記に限定されるものではないが、たとえば、ある文書ページの中の段落の数（特徴１つ）、ある文書ページ上のすべての段落の総面積（特徴１つ）、段落の左上および右下隅の座標（各段落には４つの座標、つまり、左上ｘ座標（Ｘ１）、左上ｙ座標（Ｙ１）、右下ｘ座標（Ｘ２）、右下ｙ座標（Ｙ２）があり、各座標は最小、最大、平均、四分位数という５つの数値で表され、特徴の合計は２０となる）、段落の幅と高さ（特徴１０個）、１段落あたりのテキストボックスの数（特徴５つ）、段落のフォントサイズ（特徴５つ）、あるページの画像の数（特徴１つ）、あるページの画像の総面積（特徴１つ）、画像の幅と高さ（特徴１０個）、ＳＶＧ画像の数（特徴１つ）、縦方向への充満度(vertical fill degree)（特徴１つ−すべてのテキストと画像がＹ軸に投影され、Ｙ軸上の占有空間のパーセンテージが特徴として使用される）、縦方向の余白の数（特徴１つ−テキストの行間や画像間の余白数を出力し、そのページの充満度(fill degree)と断片化に関する指標とする）、縦方向の余白の大きさ（特徴５つ−そのページの縦方向の余白の各々が記録され、５つの数値を特徴として使用）、ある番号で終わるテキストボックスの数（特徴１つ）、左、右、片側、両側の段落面積（特徴４つ−全段落のグループを、完全にページの左半分に入るもの、完全にページの右半分に入るもの、両方にまたがるものに分割する。第一のグループの総面積（左側の段落の面積）、第二のグループの総面積（右側の段落の面積）、第一と第二のグループ両方の総面積（片側の段落の面積）、第三のグループの総面積（両側の段落の面積）が合計される）、左、右、片側、両側の画像の面積（特徴４つ）およびページ番号（特徴１つ）である。特徴の中には他の特徴から導かれるものもある。たとえば、幅と高さは、座標から計算できる。いくつかの特徴については、複数の表現が選択される。たとえば、１段落あたりのテキストボックスの数は、あるページの全段落の平均または平均値で表現されることもある。全体的分布をより明確に把握するために、最小値、最大値、平均値、四分位数（全範囲の２５％と７５％の数値）が加えられる。
【００１１】
図１は、文書ページ集合１００を構成する６種類の文書ページタイプの固有で特徴的なページレイアウト属性（特徴ともいう）の例を示す図である。文書ページ集合１００は、タイトルページ１１５、１段組のテキストページ１３０、２段組のテキストページ１４５、２つの画像を含む１段組のテキストページ１６０、異なる幅の段組と３つの画像を含む混合テキストページ１７５、目次ページ１９０からなる。当業者は、文書ページ集合１００に下記のような特徴のいずれかを含むどのような文書ページレイアウトも含まれる可能性があることを理解するであろう。
【００１２】
図２は、図１の異なる幅の段組と３つの画像を含む混合テキストページ１７５の分解図である。異なる幅の段組と３つの画像を含む混合テキストページ１７５の文書ページレイアウトには、ひとつまたは複数の特徴、たとえば、まとめて示される画像２００、まとめて示される段落２２０、ページ番号２４０が含まれる。
【００１３】
図３は、本願で開示する方法を使って、図２の異なる幅の段組と３つの画像を含む混合テキストページ１７５から抽出された特徴情報のいくつかの例を示す。たとえば、その文書ページの第一段落の段落座標には、左上Ｘ座標（Ｘ１）、左上Ｙ座標（Ｙ１）、右下Ｘ座標（Ｘ２）、右下Ｙ座標（Ｙ２）がある。全体の分布をよりよく把握するために、各座標（Ｘ１，Ｘ２，Ｙ１，Ｙ２）は、５つの地点、つまり最小、最大、平均値、四分位数によって表される。
【００１４】
図４は、文書ページ集合をクラスタリングする方法を構成するステップを説明するフロー図であり、その文書ページ集合の各ページにはひとつまたは複数の特徴がある。この方法には、その集合から抽出された文書ページのサンプルに関する基準クラスタリングを計算するステップと、その文書ページのサンプルに関する距離関数を、そのサンプルの各文書ページに関わるひとつまたは複数の特徴の重みに基づいて学習するステップと、その距離関数をクラスタリングアルゴリズムに当てはめ、その文書ページの集合をクラスタリングするステップが含まれる。
【００１５】
その方法は、ステップＳ４００から始まり、ステップＳ４０７に示されるように、ユーザがクラスタリングしたいと望む文書ページ集合を取得するステップを含む。集合の文書ページの各々は、ひとつまたは複数の特徴を有する。ステップＳ４１４で、その集合の文書ページのサンプルが選択される。ステップＳ４２１で、この文書ページサンプルには、基準クラスタリングを計算するように注釈が付けられる。ステップＳ４２１では、ユーザがその文書ページサンプルを閲覧し、サンプルを手でクラスタリングして、基準クラスタリングを生成する。注釈を付けるプロセスについて、図５に図示して後でさらに詳しく説明する。
【００１６】
文書ページサンプルが手でクラスタリングされ、基準クラスタリングが計算された後、ステップＳ４２８において、ユーザは注釈が付けられた文書ページサンプルを電子文書処理システムに入力する。通常、電子文書処理システムは一般に、文書ページのハードコピーサンプルの全体的外観（つまり、コンテンツや基本的グラフィックレイアウト）を電子的に取り込む入力装置と、ユーザが文書ページサンプルの電子バージョンを作り、編集し、その他操作することができるようにプログラムされたコンピュータと、文書ページサンプルの電子バージョンのハードコピーレンダリングを生成するためのプリンタとを備える。入力装置は、以下の周知の装置のうちのひとつまたは複数を備えていてもよい。コピー機、電子写真システム、静電複写機、デジタル画像スキャナ（たとえば、フラットベッドスキャナまたはファクシミリ機）、取り外し可能な媒体（ＣＤ、フロッピー（登録商標）ディスク、テープその他記憶媒体）上に文書ページサンプルのデジタル表現を記憶させたものを内部に保持するディスク読取機、あるいはその上に文書ページサンプルが画像として記録されたハードディスクもしくはその他のデジタル記憶媒体。当業者は、本願の方法が、文書ページサンプルのデジタル化表現を記憶するのに適したどの装置でも実現できることを理解するであろう。
【００１７】
文書ページサンプルは、それについてひとつまたは複数の特徴を抽出できるどのような電子フォーマットでもよく、たとえば、これらに限定されないが、ＡＳＣＩＩ、ＰｏｓｔＳｃｒｉｐｔ、ＰＤＦ、ＨＴＭＬ、ＸＭＬ（特に、ＸＨＴＭＬとＳＶＧ）等のオープンフォーマットがある。Ｍｉｃｒｏｓｏｆｔ  Ｗｏｒｄ、Ｅｘｃｅｌ、ＰｏｗｅｒＰｏｉｎｔ等の文書タイプは、適正なソフトウェア（ＰＤＦ２ＸＭＬまたはＣａｍｂｒｉｄｇｅＤｏｃｓ等として入手可能）によってＸＭＬフォーマットに変換できる。ある実施例において、文書ページサンプルはＸＭＬフォーマットである。ＸＭＬフォーマットは、たとえば、これらに限定されないが、ＴＥＸＴ、ＰＡＲＡＧＲＡＰＨ、ＩＭＡＧＥ等の特徴を表示できる。ひとつまたは複数の特徴には、その文書ページの上のそのひとつまたは複数の特徴のｘ位置とｙ位置、ひとつまたは複数の特徴の幅と高さおよび、テキストフォント名やサイズ等のその他の情報を示す属性がマークされる。ステップＳ４３５に示されているように、そのサンプルの各文書ページについて、ＸＭＬ文書のひとつまたは複数の特徴に関する情報が抽出される。
【００１８】
各文書ページについて特徴情報が抽出されると、ステップＳ４４２に示されているように、ｎ次元の特徴ベクトルが作られる。たとえば、ｐｉ，ｐｊの２ページについて、特徴ベクトルｆｉ，ｆｊが作られる。ページｐｉとページｐｊの間の距離関数ｄ（ｐｉ，ｐｊ）は、そのページの異なる特徴の間の距離の加重和であり、下記（１）のように表される。
【数１】
2007080263.tif 000003
【００１９】
特徴に関するｎ個の距離関数ｄｋは、ちょうど特徴の数値の差の絶対値｜ｆｉ［ｋ］−ｆｊ［ｋ］｜であることが多い。いくつかの特徴、特に面積の特徴（つまり、段落の面積、画像の面積）については、その距離｜ｆｉ［ｋ］−ｆｊ［ｋ］｜の平方根が代わりに使用される。ここで開示する実施例は、特定の選択に限定されない。重要なステップは、ステップＳ４４９において特徴重みλｋを学習することである。特徴重みの数値を探すために、探索が行われる。ひとつまたは複数の特徴の重みに初期値が割り当てられ、この初期値から距離関数が計算される。距離関数をクラスタリングアルゴリズムの中で使用し、その文書ページサンプルのクラスタリングが生成される。生成されたクラスタリングは、基準クラスタリングと比較して評価され、この評価に基づき、特徴重みが修正されるか、そのままにされる。探索と評価のステップについては、図７，図９に示し、後で詳しく説明する。
【００２０】
ステップＳ４７０で探索と評価のステップが実行され、特徴重みが決定されると、方法はステップＳ４７７に進む。まず、ステップＳ４５６に示されるように、文書ページ集合全体を電子処理システムによって処理し、同じ特徴が文書ページ集合全体から抽出されるようにする。特徴抽出プロセスの結果、ステップＳ４６３に示されるように、はるかに大きな特徴ベクトルグループができる。次に、ステップＳ４７７に示されるように、文書ページサンプルから決定された特徴の重みを使って、距離関数をクラスタリングアルゴリズムに入れることにより、全体集合に関する距離関数を決定する。その結果、ステップＳ４８４に示されるように、完全な文書ページ集合のクラスタリングが得られる。方法は、ステップＳ４９１で終了する。
【００２１】
図５は、基準クラスタリングを生成するための方法を説明するフロー図である。この方法はステップＳ５００から始まり、ステップＳ５１０に示されるように、ユーザはある文書ページ集合から文書ページサンプルを取得する。ステップＳ５２０で、ユーザはサンプルの最初の文書ページを検討し、そのページを基準クラスタリングの第一のクラスタに入れる。当初、基準クラスタリングは空で、文書ページを一切含まない。この方法はステップＳ５３０に進み、ここで、文書ページのサンプルを確認し、他にも文書ページがあるか判断する。他の文書ページが存在する場合、方法はステップＳ５４０に進み、そのサンプルの中の次の文書ページについて検討が行われる。ステップＳ５５０に示されるように、文書ページを検討し、現在検討中の文書ページに関する基準クラスタリングの中にクラスタが存在するか判断する。クラスタが存在すれば、ステップＳ５６０に示されるように、その文書ページを基準クラスタリングの中のそのクラスタに追加する。その文書ページが既存のクラスタのいずれにも属さない場合、ステップＳ５７０に示されるように、基準クラスタリングの中に新しいクラスタを作る。方法はステップＳ５３０に戻り、そのサンプルの中のすべての文書ページが検討され、基準クラスタリングのクラスタの中に入れられるまで、ステップＳ５４０，Ｓ５５０，Ｓ５６０，Ｓ５７０を繰り返す。そのサンプルのすべての文書ページが検討され、基準クラスタリングのクラスタの中に入れられると、方法はステップＳ５８０に進み、完全な基準クラスタリングが作られる。
【００２２】
図６は、文書ページサンプルに関する正しい特徴の重みと距離関数を判断するための探索および評価ステップを示す略図である。図６に示される探索および評価ステップは、反復的な準教師ありクラスタリング手法に基づくものである。他の実施例では、探索と評価は単純探索による方法に基づく。また、他の実施例では、探索と評価は遺伝的アルゴリズムによる方法に基づく。
【００２３】
単純探索に基づく方法の場合、文書ページ集合の文書ページサンプル６００を取得し、各ページに関する特徴情報を抽出し、特徴ベクトルグループ６１０を作る。当初、すべての特徴重み６２０に数値１／ｎ（ただし、ｎは特徴の総数）が与えられる。そのサンプルの中の２枚の文書ページの間の距離６３０が上述のように判断され、次に、その文書ページはクラスタリングアルゴリズム６４０に与えられる。クラスタリングアルゴリズム６４０は、いくつかの生成されたクラスタリング６５０を作り、生成されたクラスタリング６５０を基準クラスタリング（「正しいクラスタリング」とも呼ばれる）６６０と比較する（６７０）。次に、特徴をひとつひとつ検討し、それぞれの特徴重み６２０を、特定の係数αを用いて特徴を乗じることによって大きくする。このように重み６２０を更新したことでクラスタリング６５０が改善された場合は、更新された数値が保持される。それ以上改善されなくなるまで、反復手順を繰り返す。ある実施例において、αの数値は約１．１から約２０の範囲である。
【００２４】
遺伝的アルゴリズムによる方法では、特徴重み６２０は染色体として記号化される。染色体プールが作られる。各染色体において、特徴重み６２０の各々が０．０から１．０の間のランダムな数字に初期設定される。突然変異（ランダムな数値への再初期化）、交差および淘汰の通常の操作が適用される。淘汰は染色体の適性に基づいており、これは染色体の中で記号化された特徴重み６２０に応じたクラスタリング６５０の評価に対応する。プールの大きさ以外のパラメータとして、世代の数、突然変異の可能性、交差の可能性および当業者の間で周知のその他のパラメータがある。
【００２５】
他の実施例において、使用されるクラスタリングアルゴリズム６４０は、最短距離法（シングルリンク=single-link）、最長距離法（コンプリートリンク=complete-link）、平均距離法（アベレージリンク=average-link）を用いたクラスタリングを含む、階層的塊集的クラスタリングアルゴリズムである。塊集的クラスタリングにおいては、各オブジェクトは当初、別の集団（クラスタ）として扱われる。次に、クラスタは類似性に基づいて連続的に組み合わされ、残りのクラスタがひとつになった時、あるいは特定の終了条件が満たされた時に終了する。ある実施例において、クラスタリングアルゴリズムは、平均距離法クラスタリングアルゴリズムである。当業者は、本願で開示する方法がどのクラスタリングアルゴリズムでも使用でき、その上でさらに、本願で開示する実施形態の範囲と精神に含まれると理解できるであろう。
【００２６】
図７は、図６の略図に基づく反復的方法を説明するフロー図である。この方法のステップにより、生成されたクラスタリングと基準クラスタリングの間の類似性を最大にする特徴重みを見出すことができる。方法はステップＳ７００から始まり、ステップＳ７０７に示されるように、文書ページ集合から文書ページサンプル６００を取得するステップを含む。ユーザは、文書ページサンプル６００を電子文書処理システムに入力する。ステップＳ７１４で、特徴ベクトルグループ６１０は、そのサンプルの最初の文書ページから特徴を抽出することによって構築される。ステップＳ７２１で、サンプルをチェックし、そのサンプルの中に他にも文書ページがあるか否か判断する。他の文書ページがあれば、ステップＳ７２８に示されるように、そのページの特徴が抽出され、特徴ベクトルグループ６１０に加えられる。そのサンプルのすべての文書ページサンプル６００から特徴を抽出し終わると、方法はステップＳ７３５に進む。ステップＳ７３５で、特徴重み６２０が、ランダムに、あるいはすべて同じ設定になるよう初期化される（前者は、遺伝的アルゴリズム、後者は単純探索の場合）。特徴重み６２０が確定されると、ステップＳ７４２で特徴重み６２０が距離式に組み込まれ、ステップＳ７４９で、いずれか２ページ間の距離関数６３０が計算される。すると、ステップＳ７５６に示されるように、文書ページサンプル６００が、距離関数６３０とクラスタリングアルゴリズム６４０を使ってクラスタリングされ、その結果、サンプルのクラスタリング６５０（生成されたクラスタリングとも言われる）が得られる。ステップＳ７６３に示されるように、このクラスタリング６５０は、人為的に与えられたクラスタリング６６０と比較して評価される（６７０）。評価６７０の結果が類似していれば、ステップＳ７９８に示されるように、特徴重み６２０が結果として出力される。類似していなければ、ステップＳ７７０に示されるように、再び反復ステップが実行され、特徴重みが修正される。ステップＳ７７７で、新しい特徴重みが距離式に組み込まれ、ステップＳ７８４で、２ページ間の新しい距離関数６３０が計算される。ステップＳ７９１で、文書ページサンプル６００は、新しい距離関数６３０とクラスタリングアルゴリズム６４０を使ってクラスタリングしなおされ、新たに生成されたクラスタリング６５０が得られる。このクラスタリング６５０は、ステップＳ７６３で、人為的に与えられた基準クラスタリング６６０と比べて評価される（６７０）。このプロセスは、生成されたクラスタリングと基準クラスタリングが類似するまで繰り返される。単純方法の場合、特徴重みはひとつひとつ増加され、遺伝的アルゴリズムにおいては、突然変異や交差等の遺伝的操作が用いられ、評価に続いて淘汰ステップが実行される。
【００２７】
探索アルゴリズムにフィードバックを返すために、特定の特徴重みを選んで得られたクラスタリングを評価しなければならない。つまり、生成されたクラスタリングを基準クラスタリングと比較しなければならない。２つのクラスタリングを比較するために、たとえば、これらに限定されないが、ＲＡＮＤインデックス、Ｊａｃｑｕａｒｄ類似性インデックス、距離のｓｐｌｉｔとｊｏｉｎ、情報量の偏差等、各種の評価インデックスが提案されてきた。他の実施例において、情報量の偏差が評価方法として使用される。
【００２８】
図８は、文書ページサンプルについて、特徴重みと距離関数を判断するための探索および評価ステップを示す略図である。図８に示される探索および評価ステップは、直接的な準教師あり分類法に基づく。他の実施例において、探索と評価は最大エントロピー分類法に基づく。また、他の実施例において、探索と評価は線形計画による分類方法に基づく。
【００２９】
図８では、文書ページ集合の文書ページサンプル８００が取得され、各ページに関連する特徴情報が抽出され、特徴ベクトルグループ８１０が作られる。特徴ベクトルグループを使い、分類８２０の問題が構築される。基準クラスタリング８７０は、サンプル８００の中の２ページが同じクラスタに含まれるか、異なるクラスタに含まれるかを判断するのに使用される。構築されたクラス分類器８２０から特徴重み８３０が抽出され、これが、クラスタリングアルゴリズム８５０で使用される距離測度８４０を形成する。すると、クラスタリングアルゴリズム８５０は、文書ページ集合のクラスタリング８６０に使用できる。
【００３０】
最大エントロピー法の場合、最大エントロピー分類法を使って、特徴重み８３０を検出する。同じクラスタと異なるクラスタの２つのクラスが作られる。最大エントロピークラス分類器８２０に関して、当初のクラスタリング問題の２つの地点（文書ページ）の各ペアについて訓練サンプルが作られる。新しい個々の訓練サンプルにはｎ個の特徴、つまり、ｎ個の特徴距離の数値ｄκ（ｆｉ［ｋ］，ｆｊ［ｋ］）がある。訓練サンプルごとに、ペアの両方の地点が基準クラスタリング８７０の中の同じクラスタにあれば、同じクラスタの分類が与えられ、そうでなければ、そのサンプルには異なるクラスタの分類が与えられる。作られたサンプルセットについて最大エントロピー分類を実行する。最大エントロピーアルゴリズムは、各特徴に特定の重みが割り当てられたモデルを作る。そのモデルからｎ個の重みが抽出され、当初の問題に関する学習された特徴重み８３０として出力する。
【００３１】
線形計画法の場合、出力される特徴重み８３０は、最適化目標を再定式化することによって一度に計算される。この目標は、当初の問題から線形計画を導き出すことであり、こうすることで、標準的なテクニックを用いて解決できるようになる。２つの地点（文書ページ）のペア（ｐｉ，ｐｊ）のすべてが考慮される。Ｓは２地点両方が同じクラスタに属する２地点ペアのグループであり、Ｔは２地点がそれぞれ異なるクラスタに属する２地点ペアのグループである。
【００３２】
ｐｉとｐｊが同じクラスタに入る場合（つまり、（ｐｉ，ｐｊ）∈Ｓ）、この２つの文書ページを使って最適化目標を定式化する。目標は、同じクラスタ内の地点間の距離８４０を最小にするような特徴重み８３０を見つけることである。このため、最適化目標は、Ｓの２地点ペア間のすべての距離８４０の合計を最小にすることであり、下記（２）のように表される。
【数２】
2007080263.tif 000004
【００３３】
ｐｉとｐｊが同じクラスタにない場合（つまり、（ｐｉ，ｐｊ）∈Ｔ）、制約が定式化される。このようなペアの各々について、これら２地点間の距離は、同じクラスタの地点間の距離より大きいはずであり、下記（３）のように表される。
【数３】
2007080263.tif 000005
【００３４】
制約の中で、第一の加数は、Ｔの２地点ｐｉとｐｊの間の距離である。第二項は、正規化された最適化目標、つまり、同じクラスタの地点間の平均距離である。異なるクラスタの地点間の距離は、それより特定の数値∈＞０だけ大きいはずである。この定義により、多数の制約が得られる。重みはすべて、負ではない数とされる。このように定義された線形計画により、特徴重みのグループ８３０が得られる。線形計画には解がない場合もあるが、当業者は、解の近似値を得る方法があることを理解するであろう。
【００３５】
図９は、図８の略図に基づく直接的な方法を説明するためのフロー図である。この方法はステップＳ９００から始まり、ステップＳ９０７に示されるように、文書ページ集合の文書ページサンプルを取得するステップを含む。ステップＳ９１４で、そのサンプルの第一の文書ページから特徴を抽出することによって特徴ベクトルグループが構築される。ステップＳ９２１で、そのサンプルをチェックし、そのサンプルの中に他にも文書ページがあるか判断する。他の文書ページがあれば、ステップＳ９２８に示されるように、そのページの特徴が抽出され、特徴ベクトルグループに追加され、これは個々のページの特徴値の距離からなる。そのサンプル中のすべての文書ページが見直されたら、ステップＳ９３５に示されるように、分類問題が構築される。分類対象データは異なるページのペア全部であり、これらは、ステップＳ９４２に示されるように、基準クラスタリングに基づいて同じクラスタに入るか、あるいは異なるクラスタに入るか分類される。分類情報は、基準クラスタリングを見ることによって得ることができる。基準クラスタリングは、図５の方法に基づいて計算される。ステップＳ９４９に示されるように、クラス分類器は、構成されたデータで訓練される。ステップＳ９５６で出力されたクラス分類器は、ステップＳ９６３に示されるように、クラス分類器から特徴重みを抽出するのに使用でき、その結果得られた特徴重みは、ステップＳ９７０に示されるように、文書ページ集合のクラスタリングにそのまま利用できる。
【００３６】
図１０は、特徴重みが決定された後に文書ページ集合全体をクラスタリングする方法を説明するフロー図である。特徴重みの決定は、図７または図９に示す方法のいずれかで実現できる。この方法は、ステップＳ１０００から始まり、ステップＳ１０１０に示されるように、文書ページ集合を取得するステップを含む。ステップＳ１０２０で、その集合の第一の文書ページから、上述の電子文書処理システムを使って特徴を抽出することによって特徴ベクトルグループが構築される。ステップＳ１０３０で、集合をチェックし、そのサンプル内に他にも文書ページがあるか判断する。他の文書ページがあれば、ステップＳ１０４０に示されるように、そのページの特徴が抽出され、特徴ベクトルグループに追加される。文書ページ集合全体からの特徴が抽出されたら、方法はステップＳ１０５０に進み、特徴ベクトルグループが完成する。ステップＳ１０６０で、図７または図９に示された方法のいずれかから得られた特徴重みが電子文書処理システムに取り込まれる。ステップＳ１０７０で特徴重みが距離式の中に組み込まれ、ステップＳ１０８０で２ページ間の距離測度が計算される。この測度に基づき、ステップＳ１０９０に示されるように、それらの特徴ベクトルによって表されるページグループ全体をクラスタリングすることができる。その結果得られたクラスタリングがこの方法の出力となる。
【００３７】
本願で開示した方法は、文書ページ集合のクラスタリングに関するものであるが、当業者は、この方法が上記以外にも、たとえば、これらに限定されないが、科学者がたんぱく質をホモロジ群にクラスタリングする場合、ユーザがレガシーの文書変換のために文書ページをクラスタリングする場合、会社が顧客を顧客グループにクラスタリングする場合、人がウェブページをカタログにクラスタリングする場合、また、画像を異なるグループにクラスタリングする場合等のクラスタリングに使用できると理解するであろう。
【００３８】
また、文書ページ集合の距離関数を計算する方法は、文書ページ集合を取得するステップと、前記集合内の各文書ページはひとつまたは複数の特徴を有し、前記ひとつまたは複数の特徴はページレイアウト属性を画定し、各文書ページ上の前記ひとつまたは複数の特徴から情報を抽出するステップと、各文書ページ上の前記ひとつまたは複数の特徴に関する特徴ベクトルを構築するステップと、各特徴に特徴重みを割り当てるステップと、前記特徴重みと前記特徴ベクトルに基づいて距離関数を計算するステップと、を含むものである。
【００３９】
また、文書ページ集合をクラスタリングする方法において、文書ページ集合を取得するステップと、前記集合内の各文書ページはひとつまたは複数の特徴を有し、前記ひとつまたは複数の特徴はページレイアウト属性を画定し、各文書ページ上の前記ひとつまたは複数の特徴から情報を抽出し、特徴ベクトルを構築するステップと、各特徴に関して割り当てられた特徴重みに基づいて距離関数を計算するステップと、前記距離関数を用いて前記文書ページ集合をクラスタリングするステップと、を含むものである。
【００４０】
なお、上記の図面はここで開示する実施例を示しているが、明細書中に記載されているとおり、他の実施例も想定される。この開示は、限定としてではなく、代表として図中の実施例を紹介したものである。当業者であれば、ここに開示する実施例の原理の範囲と精神に含まれるその他多数の改変や実施例を考案できる。
【図面の簡単な説明】
【００４１】
【図１】文書ページ集合１００を構成する６種類の文書ページタイプの固有で特徴的なページレイアウト属性（特徴ともいう）の例を示す図である。
【図２】図１の異なる幅の段組と３つの画像を含む混合テキストページ１７５の分解図である。
【図３】図２の異なる幅の段組と３つの画像を含む混合テキストページ１７５から抽出された特徴情報のいくつかの例を示す図である。
【図４】文書ページ集合をクラスタリングする方法を構成するステップを説明するフロー図である。
【図５】基準クラスタリングを生成するための方法を説明するためのフロー図である。
【図６】文書ページサンプルに関する正しい特徴の重みと距離関数を判断するための探索および評価ステップを示す略図である。
【図７】図６の略図に基づく反復的方法を説明するフロー図である。
【図８】文書ページサンプルについて、特徴重みと距離関数を判断するための探索及び評価ステップを示す略図である。
【図９】図８の略図に基づく直接的な方法を説明するためのフロー図である。
【図１０】特徴重みが決定された後に文書ページ集合全体をクラスタリングする方法を説明するフロー図である。
【符号の説明】
【００４２】
１００  文書ページ集合、１１５  タイトルページ、１３０  １段組のテキストページ、１４５  ２段組のテキストページ、１６０  ２つの画像を含む１段組のテキストページ、１７５  異なる幅の段組と３つの画像を含む混合テキストページ、１９０  目次ページ、２００  画像、２２０  段落、２４０  ページ番号。
【図１】
2007080263.tif 000006
【図２】
2007080263.tif 000007
【図３】
2007080263.tif 000008
【図４】
2007080263.tif 000009
【図５】
2007080263.tif 000010
【図６】
2007080263.tif 000011
【図７】
2007080263.tif 000012
【図８】
2007080263.tif 000013
【図９】
2007080263.tif 000014
【図１０】
2007080263.tif 000015