(57)【要約】差分ＬＳＩ（ＤＬＳＩ）空間に対する差分文書ベクトルの射影と距離を組み合わせた使用に基づく自動文書分類方法。この方法は、ＤＬＳＩ空間ベースの分類子を設定することと、事後確率関数を使用して所与のクラスタに属する文書の可能性を評価するためにそのような分類子を使用することを含む。【特許請求の範囲】
【請求項１】
文書分類のためにＤＬＳＩ空間ベースのクラシファイアを設定する方法において、
語および名詞句のター厶をストップ・ワードから区別するために文書を前処理するステップと、
タームリスト並びに大域的重みを設定することによってシステムタームを構成するステップと、
収集された文書の文書ベクトル並びに各クラスタの重心ベクトルを正規化するステップと、
内部文書行列
【数１】
2004536383.tif 000043
による差分ター厶を構成するステップであって、前記行列の各列が差分内部文書ベクトルであるステップと、
内部文書行列ＤＩによる差分タームをＳＶＤアルゴリズムによってＤＩ＝ＵＩＳＩＶＴＩ（ＳＩ＝ｄｉａｇ（δＩ１，δＩ２，．．．））に分解し、次いで
【数２】
2004536383.tif 000044
の合成を行い、適切なｋＩを使用して近似ＤＩを求めるステップと、
内部差分文書ベクトルの尤度関数を設定するステップと、
外部文書行列
【数３】
2004536383.tif 000045
によるタームを構成するステップであって、前記外部文書行列の各列が外部差分文書ベクトルであるステップと、
ＤＥを、当該ＳＶＤアルゴリズムを使用してＤＥ＝ＵＥＳＥＶＴＥ（ＳＥ＝ｄｉａｇ（δＥ，１，δＥ，２））に分解し、次いでＤＥを近似するために適切なｋＥを使用して
【数４】
2004536383.tif 000046
を定義するステップと、
外部差分文書ベクトルの尤度関数を設定するステップと、
事後関数を設定するステップと、
文書を自動的に分類するために当該ＤＬＳＩ空間ベースのクラシファイアを使用するステップと
を含む方法。
【請求項２】
データベースのクラスタに従って文書を分類するためのＤＬＳＩ空間ベースのクラシファイアを使用した自動文書分類方法において、
ａ）ターム並びに文書内における前記タームの出現頻度を生成することによって文書ベクトルを設定するステップであって、当該文書に対して正規化された文書ベクトルＮが求められるステップと、
ｂ）分類されるべき当該文書を使用して差分文書ベクトルｘ＝Ｎ−Ｃを構成するステップであって、Ｃはクラスタの中心または重心を与える正規化されたベクトルであるステップと、
ｃ）当該文書に対して内部文書尤度関数Ｐ（ｘ｜ＤＩ）を計算するステップと、
ｄ）当該文書に対して外部文書尤度関数Ｐ（ｘ｜ＤＥ）を計算するステップと、
ｅ）ベイズ事後確率関数Ｐ（ＤＩ｜ｘ）を計算するステップと、
ｆ）当該データベースのクラスタごとにステップｂ−ｅを反復するステップと、
ｇ）最大のＰ（ＤＩ｜ｘ）を有するクラスタを当該文書が属する可能性が最も高いクラスタとして選択するステップと、
ｈ）当該文書を当該選択されたクラスタで分類するステップと
を含む方法。
【請求項３】
当該正規化された文書ベクトルＮが、方程式
【数５】
2004536383.tif 000047
を使用して求められる請求項２に記載の方法。
【請求項４】
文書分類のためにＤＬＳＩ空間ベースのクラシファイアを設定する方法において、
内部文書行列による差分タームを設定するステップであって、当該行列の各列が文書と当該文書が属しているクラスタの重心の間の差分を示すステップと、
内部ＤＬＳＩ空間を識別するために、当該差分タームを内部文書行列によりＳＶＤアルゴリズムによって分解するステップと、
差分内部文書ベクトルである差分文書ベクトルに対して確率関数を設定するステップと、
当該差分文書ベクトルから当該内部ＤＬＳＩ空間への射影および距離に従って当該確率関数を計算するステップと、
外部文書行列による差分タームを設定するステップであって、当該行列の各列が、文書ベクトルと当該文書を含まないクラスタの重心ベクトルとの間の差分文書ベクトルを示すステップと、
外部ＤＬＳＩ空間を識別するために、当該差分タームを外部文書行列によりＳＶＤアルゴリズムによって分解するステップと、
差分外部文書ベクトルである差分文書ベクトルに対して確率関数を設定するステップと、
クラスタに属する文書の最も確率の高い類似性測度を提供するために、当該差分内部文書ベクトルおよび当該差分外部文書ベクトルを使用して事後尤度関数を設定するステップと、
文書を自動的に分類するために当該ＤＬＳＩ空間ベースのクラシファイアを使用するステップと
を含む方法。
【請求項５】
差分内部文書ベクトルである差分文書ベクトルに対して確率関数を設定する当該ステップが、方程式
【数６】
2004536383.tif 000048
を使用して実行され、上式で、
【数７】
2004536383.tif 000049
、ｒＩは行列ＤＩのランクである請求項４に記載の方法。
【請求項６】
差分外部文書ベクトルである差分文書ベクトルに対して確率関数を設定する当該ステップが、方程式
【数８】
2004536383.tif 000050
を使用して実行され、上式で、
【数９】
2004536383.tif 000051
、ｒＥは行列ＤＥのランクである請求項４に記載の方法。
【請求項７】
事後尤度関数を設定する当該ステップが、方程式
【数１０】
2004536383.tif 000052
を使用して実行され、上式でＰ（ＤＩ）はｎｃをデータベース内のクラスタ数とした場合に１／ｎｃに設定され、Ｐ（ＤＥ）は１−Ｐ（ＤＩ）に設定される請求項４に記載の方法。
【請求項８】
文書を自動的に分類するために当該ＤＬＳＩ空間ベースのクラシファイアを使用する当該ステップが、
ａ）当該文書に対して正規化された文書ベクトルＮを求めるように、ターム並びに当該文書内における前記タームの出現頻度を生成することによって文書ベクトルを設定するステップと、
ｂ）分類されるべき当該文書を使用して差分文書ベクトルＸ＝Ｎ−Ｃを構成するステップであって、Ｃはクラスタの中心または重心を与える正規化されたベクトルであるステップと、
ｃ）当該文書に対して内部文書尤度関数Ｐ（ｘ｜ＤＩ）を計算するステップと、
ｄ）当該文書に対して外部文書尤度関数Ｐ（ｘ｜ＤＥ）を計算するステップと、
ｅ）ベイズ事後確率関数Ｐ（ＤＩ｜ｘ）を計算するステップと、
ｆ）データベースのクラスタごとにステップｂ−ｅを反復するステップと、
ｇ）最大のＰ（ＤＩ｜ｘ）を有するクラスタを当該文書が属する可能性が最も高いクラスタとして選択するステップと、
ｈ）当該文書を当該選択されたクラスタで分類するステップと
を含む請求項４に記載の方法。
【請求項９】
当該正規化された文書ベクトルＮが、方程式
【数１１】
2004536383.tif 000053
を使用して求められる請求項８に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文書分類の分野に関し、より詳細には、差分ＬＳＩ（ＤＬＳＩ）空間に対する差分文書ベクトルの射影と距離を組み合わせ併用した自動文書分類法に関する。
【背景技術】
【０００２】
文書分類は、職場での文書処理においてのみならず、効率的な情報検索システムを実施する際にも重要である。後者は、インターネットのような分散型コンピュータ・ネットワークの爆発的普及に伴い、ますます重要になってきている。たとえば、Ｙａｈｏｏ（登録商標）における最も普及した文書分類タスクでさえ完全に人手によって行われている。
【０００３】
ベクトル空間モデルは、各文書がタームのベクトルとして表現される場合に文書分類で広範に使用されている。文書を文書ベクトルで表現するには、対応するタームの出現頻度を一般に評価し、その構成要素に重みが割り当てられる。この場合、標準的なパターン認識および機械学習法が文書分類のために使用される。
【０００４】
任意の自然言語に組み込まれた固有の柔軟性を考慮すると、使用されている莫大な数のタームを含んでいる任意の実用文書の特徴表示空間を表現するには驚異的な次元数が必要となる。高速の分類アルゴリズムを開発することができた場合、解決されるべき最初の問題は、より小さなサブ空間への文書タームの射影を可能にする次元数低減方式である。
【０００５】
基本的に、文書を射影し、または文書の次元を低減するには２種類の方法がある。１つは、しばしば打ち切りと称される局所的方法であり、ここでは複数の「重要でない」または「関係のない」タームが文書ベクトルから削除され、タームの重要性は、文書内におけるそのタームの出現頻度に基づいてシステムに重み付けすることによってしばしば評価される。この方法が局所的と呼ばれるのは、各文書は異なるサブ空間に射影されるが、ベクトルがスパースなため文書ベクトルにおけるその効果が最小限であるからである。別の方式は大域的方法と呼ばれ、ここでは削除されるべきタームがまず選定され、その結果、各文書から同じタームを削除してすべての文書ベクトルが同一サブ空間に射影することが保証される。この過程で、大域的方法は各文書特有の特徴に対する適応性の重要な特性の一部を失う。したがって、この適応性を改善するためのいくつかの方法が求められている。
【０００６】
画像処理および画像認識で広範に使用されている固有値分解方法と同様に、ＳＶＤ（Ｓｉｎｇｕｌａｒ  Ｖａｌｕｅ  Ｄｅｃｏｍｐｏｓｉｔｉｏｎ）によるＬＳＩ（Ｌａｔｅｎｔ  Ｓｅｍａｎｔｉｃ  Ｉｎｄｅｘｉｎｇ）は、文書解析および抽出における次元数低減方式に関する最も効率的な方法であることが証明されており、経験的学習に裏付けられた良好なパフォーマンスにより文書検索に導入された場合にクラシファイアに強力なツールを提供する。ＬＳＩベースの次元数低減に特異の利点は、同じ次元のすべての可能な空間上へのすべての射影のうち、ＬＳＩ空間上への一組の文書ベクトルの射影が元の文書ベクトルへの可能な限り最低の最小二乗距離を有することにある。これは、ＬＳＩが次元低減に対する最適な解決策を発見することを暗示している。次元数低減の役割に加え、ＳＶＤによるＬＳＩは、タームを削除するとういう単純な方式では対処することが期待できない同義語および多義語の問題の影響を抑える上でも効果的である。語意曖昧性除去問題としても周知の同義語および多義語の問題の原因は、いかなる自然言語の文脈依存文法固有の特徴にまでさかのぼることができる。これら２つの利点を有することから、ＬＳＩは最も普及した次元数低減ツールを提供するということが判明している。
【０００７】
大域的射影方式は、各文書特有の特徴に適応する際に難点があり、このような欠点に起因した文書クラシファイアの不都合なパフォーマンスを改善するために方法を開発する必要がある。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
上記事項に鑑みて、本発明の１つの目的は、個々の文書特有の特徴に対する適応性を維持した文書クラシファイア方法である。
【課題を解決するための手段】
【０００９】
この目的および他の目的に従い、本発明は新しい効率的な教師あり文書分類手順を発表する。これにより所与の数のラベル付き文書からの学習はデータベース内の有限数の適切なクラスタに事前分類され、開発されたクラシファイアは、分類の段階で適切なクラスタに導入された新しい文書から任意の文書を選択し、分類する。
【００１０】
本発明のクラシファイアは、各文書ベクトルから当該各文書ベクトルが射影されるＬＳＩ空間への距離を利用する。ＬＳＩ空間への距離と、そこに対する射影とを利用することによって、文書クラシファイアのパフォーマンス並びに堅牢さが向上する。これを行うために、メジャー・ベクトル空間は、正規化された内部文書ベクトルおよび外部文書ベクトルと、クラスタの正規化された重心ベクトルの間の差分から構成される差分ＬＳＩ（すなわちＤＬＳＩ）である。ここで内部文書および外文書とは、それぞれに所与のクラスタ内、または外に含まれる文書を意味している。文書がクラスタに属している可能性を評価するために、新しいクラスタは、複数の差分文書ベクトルに対するベイズ事後確率関数を、ＤＬＳＩ空間上へのそれらの射影とＤＬＳＩ空間へのそれらの距離とに基づいて設定し、最高の確率を有する候補を選択する。
【００１１】
差分文書ベクトルおよびＤＳＬＩベクトルの概念に基づいて、少なくとも３つの特定の特性が新しい文書分類方式に導入される。第１に、文書とクラスタの重心ベクトルの間における語用法の違いを示す差分文書ベクトルからＤＬＳＩ空間への特徴的距離と、ＤＬＳＩ空間上への差分文書の射影とを利用することによって、差分文書ベクトルは特定文書とクラスタとの間の関係を捕らえることが可能になる。第２に、同義語および多義語に関する自然言語の文脈依存意味文法の主要な問題は、複数ＬＳＩを使用したメジャー空間射影法によって抑えることができる。最後に、ＤＬＳＩ空間上への差分文書ベクトルの射影とＤＬＳＩ空間への距離とを利用する事後尤度関数に対する最大数は、クラスタに属する文書の信頼度を評価する上で一貫した計算方法を提供する。
【００１２】
本発明によれば、ある文書が与えられた場合、その文書ベクトルとその正規化された形式は、当該文書に出現するタームと、当該文書および可能ならば他の文書におけるそのタームの出現頻度とを利用して直接的に設定することができる。クラスタの重心は、そのメンバーの正規化されたベクトルの合計の平均によって求められる。一対の正規化された文書ベクトルの余弦は、当該一対の正規化された文書ベクトルの長さを測定する。
【００１３】
内部ＤＬＳＩ空間、すなわちＩ−ＤＬＳＩ空間を求めるには、行列の列ごとに内部文書行列による差分タームが構成されるが、この場合、行列の各列は文書と当該文書が属するクラスタの重心との間の距離を示している。次に、特異ベクトル分解方法を利用して、最大特異値に関連付けられたメジャー左特異ベクトルは、内部ＤＬＳＩ空間、すなわちＩ−ＤＬＳＩ空間と呼ばれるメジャー・ベクトル空間として選択される。Ｉ−ＤＬＳＩ空間は差分内部文書ベクトルを概略記述する際に効果的であり、差分内部文書ベクトルからＤＬＳＩ空間への距離は、特定の差分文書ベクトル特有の特徴に対する適応性を改善するための追加情報として効果的に使用することができる。分類すべき新しい文書が与えられると、複数クラスタからリコールされるべき最善の候補クラスタが、所与の差分内部文書ベクトルである可能性が最も高い複数クラスタ中から選択することができる。差分内部文書ベクトルである差分文書ベクトルに対する確率関数は、差分文書ベクトルからＩ−ＤＬＳＩ空間への射影および距離に従って計算される。
【００１４】
外部ＤＬＳＩ空間、すなわちＥ−ＤＬＳＩ空間も、外部文書行列により差分タームを設定することによって求めることができる。この場合、行列の各列は、文書ベクトルと当該文書を含まないクラスタの重心ベクトルとの間の差分文書ベクトルを示している。次いで外部ＤＬＳＩ空間は、最大特異値に関連付けられたメジャー左特異ベクトルによって構成することができる。内部ＤＬＳＩ空間におけるのと同様に、空間は、大域的記述機能に加え、特定の差分文書ベクトル特有の特徴に対する改善された適応性も共有する。分類すべき新しい文書が与えられると、複数クラスタからリコールされるべき最善の候補クラスタを、所与の差分内部文書ベクトルである可能性が最も低い複数クラスタ中から選択することができる。
【００１５】
差分内部文書ベクトルおよび差分外部文書ベクトルの概念を統合することによって、ベイズ事後尤度関数が設定され、これによりクラスタに属する文書の最も確率の高い類似性測度が提供される。上述のように、本発明によるＩ−ＤＬＳＩおよびＥ−ＤＬＳＩ空間上への差分文書ベクトルの射影、およびベクトルから当該空間への距離は、従来のＬＳＩ空間ベース方式に優る利点を有している。すなわちＬＳＩ空間ベース方式における角度の余弦の役割に等しい差分文書ベクトルの射影の長さの役割に加えて、差分文書ベクトルから射影されたＤＬＳＩ空間への距離は、大域的方法が一般的に失敗する個々の文書の類似性測度の評価を可能にする。本発明は、差分ベクトルからＤＬＳＩ空間への射影並びに距離を使用して、より豊富な情報を提供する。
【００１６】
本発明のこれら、および他の特徴は、本発明の意図する利点の多くと共に、添付の図面に関してなされる以下の説明を参照すると、さらに容易に明らかになろう。
【発明を実施するための最良の形態】
【００１７】
本発明の望ましい実施形態を説明する際、明瞭化のために特定のターム法を採用する。しかし本発明は、このようにして選択された特定のタームに限定することを意図しておらず、各特定のタームは、類似の目的を達成するために類似の方法で動作するすべての技術的等価物を含むことが理解されよう。
【００１８】
まずいくつかの基本的概念として、タームは少なくとも２つの文書に現れる語または句と定義する。「ａ」、「ｔｈｅ」、「ｏｆ」などのいわゆるストップ・ワードは除外する。文書中に現れるタームを、ｔ１，ｔ２，．．．，ｔｍとして代表的に選択し、リストするものとする。
【００１９】
集合中の文書ｊごとに、実ベクトル（ａ１ｊ，ａ２ｊ，．．．ａｍｊ）を有するタームのそれぞれにａｉｊ＝ｆｉｊ・ｇｉが割り当てられる。この場合、ｆｉｊは文書におけるタームの重要性を示す文書のタームｔｉの局所的重み付けであり、ｇｉは文書を表現する際のタームの重要性を示すパラメータである、すべての文書の大域的重みである。局所的重みは、生の出現数、出現数のブールまたは対数でもよい。大域的重みは、重み付けなし（均一）、定義域固有、またはエントロピ重み付けとすることもできる。局所的重みと大域的重みのどちらも文献で十分に研究されており、本明細書ではこれ以上説明しない。一例を以下に示す。
【００２０】
【数１】
2004536383.tif 000002
上式で、
【００２１】
【数２】
2004536383.tif 000003
であり、ｄｉは集合にタームｔｉが現れる合計回数、Ｏｉｊは文書ｊ中タームｔｉがに現れる合計回数、ｎは集合内の文書の数である。以下の式により、文書ベクトル（ａ１ｊ，ａ２ｊ，．．．ａｍｊ）を（ｂ１ｊ，ｂ２ｊ，．．．ｂｍｊ）として正規化することができる。
【００２２】
【数３】
2004536383.tif 000004
クラスタの正規化された重心ベクトルＣ＝（ｃ１，ｃ２，．．．ｃｍ）は、
【００２３】
【数４】
2004536383.tif 000005
のように正規化されたベクトルを用いて計算することができる。ここで（ｓ１，ｓ２，．．．ｓｍ）ＴはＴ１，Ｔ２，．．．，Ｔｋのように正規化されたクラスタのメンバー文書の平均ベクトルである。ベクトル（ｓ１，ｓ２，．．．ｓｍ）Ｔは
【００２４】
【数５】
2004536383.tif 000006
のように表すことができる。
【００２５】
差分文書ベクトルはＴ−Ｃと定義される。ここで、ＴおよびＣは、それぞれ上記のような何らかの基準を満たす正規化された文書ベクトルおよび正規化された重心ベクトルである。
【００２６】
差分内部文書ベクトルＤＩはＴ−Ｃと定義された差分文書ベクトルである。ここで、ＴおよびＣは、それぞれに文書Ｔを含むクラスタの正規化された文書ベクトルおよび正規化された重心ベクトルである。
【００２７】
差分外部文書ベクトルＤＥはＴ−Ｃと定義された差分文書ベクトルである。ここで、ＴおよびＣは、それぞれに文書Ｔを含まないクラスタの正規化された文書ベクトルおよび正規化された重心ベクトルである。
【００２８】
内部文書行列および外部文書行列ＤＩおよびＤＥによる差分タームは、それぞれに行列と定義されており、その各列はそれぞれに差分内部文書ベクトルおよび差分外部文書ベクトルを含んでいる。
【００２９】
事後モデルに従い、たとえばランクｉ≦ｑ＝ｍｉｎ（ｍ，ｎ）の文書ｍ×ｎ行列Ｄによる任意の差分タームは、それが内部文書行列ＤＩによる差分タームかまたは外部文書行列ＤＥによる差分タームかに関わらず、ＳＶＤによって３つの行列の積に分解することができる。すなわちＤ＝ＵＳＶＴであり、Ｕ（左特異行列）とＶ（右特異行列）はそれぞれにｍ×ｑおよびｑ×ｎのユニタリ行列であり、ＵおよびＶの最初のｒ列はそれぞれ、ＤＤＴおよびＤＴＤの固有ベクトルである。ここでＳはＳ＝ｄｉａｇ（δ１，δ２，．．．，δｑ）で表される特異行列と呼ばれ、δｉはＤＤＴの固有値の非負数平方根で、ｉ≦ｒの場合はδｉ＞０であり、ｉ＞ｒの場合はδｉ＝０である。
【００３０】
Ｓの対角要素を絶対値の降順にソートする。新たな既約行列Ｓｋを求めるには、Ｓのｋ×ｋの左上角の行列（ｋ＜ｒ）を保持して、他のタームを削除する。同様に、ＵおよびＶの左端ｋ個の列を保持することによって２つの新たな行列ＵｋおよびＶｋを求める。Ｕｋ、Ｓｋ、とＶＴｋの積によって、Ｄにほぼ等しいＤの既約行列Ｄｋ求める。
【００３１】
元の行列から、ｋの適切な値、すなわち次元の低減度を選択することは、応用例のタイプによって異なる。一般に１０００≦ｎ≦３０００の場合、ｋ≧１００が選定され、対応するｋは通常、内部文書行列による差分タームの場合は外部文書行列による差分タームの場合よりも小さい。何故ならば、外部文書行列による差分タームは、通常、内部文書行列による差分タームが有するよりも多くの列を有するからである。
【００３２】
各差分文書ベクトルｑは、Ｕｋのｋ個の列で張られたｋ次元事実空間上への射影を発見することができる。この射影はＵＴｋｑによって容易に求めることができる。
【００３３】
差分内部（外部）文書ベクトルの平均Ｘ−は、ほぼ０であることに注目すると、形成された差分ベクトルは高次元ガウス分布に従うものとすると、任意の差分ベクトルｘの尤度は以下の式によって求められる。
【００３４】
【数６】
2004536383.tif 000007
上式でｄ（ｘ）＝ｘＴΣ−１ｘであり、Σは、
【００３５】
【数７】
2004536383.tif 000008
によって表されるトレーニング・セットから計算された分布の共分散である。
【００３６】
δ−２ｉがＤＤＴの固有値を構成するので、Ｓ２＝ＵＴＤＤＴＵであり、したがってｄ（ｘ）＝ｎｘＴ（ＤＤＴ）−１ｘ＝ｎｘＴＵＳ−２ＵＴｘ＝ｎｙＴＳ−２ｙであり、ここでｙ＝ＵＴｘ＝（ｙ１，ｙ２，．．．，ｙｎ）Ｔである。
【００３７】
Ｓは対角行列なので、ｄ（ｘ）は
【００３８】
【数８】
2004536383.tif 000009
のようなより単純な形式で表すことができる。これを
【００３９】
【数９】
2004536383.tif 000010
のように評価すると最も好都合である。上式で、
【００４０】
【数１０】
2004536383.tif 000011
である。実際には、入手可能なδｉ（ｉ≦ｋ）に関数（たとえば１／ｉ）を適合させることによってδｉ（ｉ＞ｋ）を推定するが、または相対的確率を比較するだけでよいため、ρ＝δ２ｋ＋１／２とすることもできる。Ｕの列は直交ベクトルであるため、
【００４１】
【数１１】
2004536383.tif 000012
を
【００４２】
【数１２】
2004536383.tif 000013
によって推定することができる。したがって、尤度関数Ｐ（ｘ｜Ｄ）は以下のように推定することができる。
【００４３】
【数１３】
2004536383.tif 000014
上式で、
【００４４】
【数１４】
2004536383.tif 000015
、ｒは行列Ｄのランクである。実際には、ρはδ２ｋ＋１／２として選定することができ、ｒはｎとすることができる。方程式（２）で、項
【００４５】
【数１５】
2004536383.tif 000016
はＤＬＳＩ空間上へのｘの射影を表しており、ε（ｘ）はｘからＤＬＳＩ空間への距離を近似することに留意されたい。
【００４６】
Ｐ（ｘ｜Ｄ）とＰ（ｘ｜ＤＥ）の両方とも計算された場合、ベイズ事後関数は以下のように計算することができる。
【００４７】
【数１６】
2004536383.tif 000017
上式で、Ｐ（ＤＩ）は、ｎｃをデータベース内のクラスタ数として１／ｎｃに設定され、Ｐ（ＤＥ）は１−Ｐ（ＤＩ）に設定される。Ｐ（ＤＩ）は、クラスタが非オーバーラップでなくてもよい場合、データベース内のクラスタ数で割った平均リコール数に設定することもできる。
【００４８】
本発明によるＤＬＳＩ空間ベースクラシファイアの設定を図１に要約する。タームを識別し、語または名詞句をストップ・ワードから区別するためにステップ１００で文書が前処理される。次いでタームリスト並びに大域的重みを設定することによってステップ１１０でシステムタームが構成される。プロセスはステップ１２０の、収集されたすべての文書の文書ベクトル並びに各クラスタの重心ベクトルの正規化を続ける。文書ベクトルの正規化に続いて、文書行列による差分タームは、内部文書または外部文書構成により構成することができる。
【００４９】
ステップ１３０の内部文書行列構成による差分タームの分解で、それぞれの列が差分内部文書ベクトルとなるように、内部文書行列
【００５０】
【数１７】
2004536383.tif 000018
によって差分タームを構成する。ｓ要素を有する列の場合、複数列内での一次従属性を回避するためにＤＩのｍ−１差分内部文書ベクトルを含めることができる。
【００５１】
ステップ１４０で差分タームは、内部文書行列ＤＩによって、ＳＶＤアルゴリズムにより、ＤＩ＝ＵＩＳＩＶＴＩ（ＳＩ＝ｄｉａｇ（δＩ，１，δＩ，２．．．））に分解・近似され、次いで
【００５２】
【数１８】
2004536383.tif 000019
の合成が行われ、適切なｋＩのタームの近似ＤＩが求められる。ステップ１５０では、以下に従って内部差分文書ベクトルの尤度関数が設定される。
【００５３】
【数１９】
2004536383.tif 000020
上式で、
【００５４】
【数２０】
2004536383.tif 000021
、ｒＩは行列ＤＩのランクである。実際には、ｎＩとｍの両方とも十分に大きい場合、ｒＩをｎ１に設定し、ρＩを
【００５５】
【数２１】
2004536383.tif 000022
に設定することができる。
【００５６】
ステップ１６０で、外部文書行列構成による差分タームの分解によって、各列が外部差分文書ベクトルとなるように外部文書行列
【００５７】
【数２２】
2004536383.tif 000023
によってタームを構成する。ステップ１７０で、差分タームＤＥはＳＶＤアルゴリズムを利用してＤＥ＝ＵＥＳＥＶＴＥ（ＳＥ＝ｄｉａｇ（δＥ，１，δＥ，２，．．．））に分解・近似され、次いでＤＥを近似するために適切なｋＥを使用して
【００５８】
【数２３】
2004536383.tif 000024
を定義する。ステップ１８０では、以下に従って外部差分文書ベクトルの尤度関数が設定される。
【００５９】
【数２４】
2004536383.tif 000025
上式で、
【００６０】
【数２５】
2004536383.tif 000026
、ｒＥは行列ＤＥのランクである。実際には、ｎＥとｍの両方とも十分に大きい場合、ｒＥはｎＥに設定され、ρＥは
【００６１】
【数２６】
2004536383.tif 000027
に設定される。
【００６２】
内部文書または外部文書行列の構成の終結に際して、ステップ１９０では、以下に従って事後関数が設定される。
【００６３】
【数２７】
2004536383.tif 000028
上式で、Ｐ（ＤＩ）は、ｎｃをデータベース内のクラスタ数とした場合に１／ｎｃに設定され、Ｐ（ＤＥ）は１−Ｐ（ＤＩ）に設定される。
【００６４】
本発明のＤＬＳＩ空間ベースクラシファイアによる自動分類を図２に要約する。ステップ２００では、方程式（１）から当該文書に対する正規化された文書ベクトルＮを求めるように、ターム並びに文書内におけるそれらの出現頻度を生成することによって文書ベクトルが設定される。
【００６５】
次いでステップ２１０で、データベースのクラスタごとに一群の手順が反復される。より具体的には、ステップ２１１で、分類されるべき文書を使用して差分文書ベクトルｘ＝Ｎ−Ｃが構成される。ここで、Ｃはクラスタの中心または重心を与える正規化されたベクトルである。ステップ２１２、２１３に示すように、文書に対して内部文書尤度関数Ｐ（ｘ｜ＤＩ）または外部文書尤度関数Ｐ（ｘ｜ＤＥ）を計算することができる。次いでステップ２１４で、ベイズ事後確率関数Ｐ（ＤＩ｜ｘ）が計算される。最後に、ステップ２２０で最大Ｐ（ＤＩ｜ｘ）を有するクラスタがリコール候補として選択される。
【００６６】
本発明を以下の例によって実証することができる。次の８つの文書がデータベースにあると仮定する。
Ｔ１：Ａｌｇｅｂｒａ  ａｎｄ  Ｇｅｏｍｅｔｒｙ  Ｅｄｕｃａｔｉｏｎ  Ｓｙｓｔｅｍ（代数および幾何の教育システム）
Ｔ２：Ｔｈｅ  Ｓｏｆｔｗａｒｅ  ｏｆ  Ｃｏｍｐｕｔｉｎｇ  Ｍａｃｈｉｎｅｒｙ（計算機のソフトウェア）
Ｔ３：Ａｎａｌｙｓｉｓ  ａｎｄ  Ｅｌｅｍｅｎｔｓ  ｏｆ  Ｇｅｏｍｅｔｒｙ（幾何の解析および要素）
Ｔ４：Ｉｎｔｒｏｄｕｃｔｉｏｎ  ｔｏ  Ｍｏｄｅｒｎ  Ａｌｇｅｂｒａ  ａｎｄ  Ｇｅｏｍｅｔｒｙ（現代代数および幾何入門）
Ｔ５：Ｔｈｅｏｒｅｔｉｃａｌ  Ａｎａｌｙｓｉｓ  ｉｎ  Ｐｈｙｓｉｃｓ（物理学における理論解析）
Ｔ６：Ｉｎｔｒｏｄｕｃｔｉｏｎ  ｔｏ  Ｅｌｅｍｅｎｔｓ  ｏｆ  Ｄｙｎａｍｉｃｓ（力学の要素入門）
Ｔ７：Ｍｏｄｅｒｎ  Ａｌｕｍｉｎａ（現代アルミナ）
Ｔ８：Ｔｈｅ  Ｆｏｕｎｄａｔｉｏｎ  ｏｆ  Ｃｈｅｍｉｃａｌ  Ｓｃｉｅｎｃｅ（化学の基礎）
【００６７】
これらの文書は、Ｔ１，Ｔ２∈Ｃ１，Ｔ３，Ｔ４∈Ｃ２，Ｔ５，Ｔ６∈Ｃ３，およびＴ７，Ｔ８∈Ｃ４の４つのクラスタに属していることが知られている。ここで、Ｃ１はコンピュータ関連フィールドに属しており、Ｃ２は数学に属しており、Ｃ３は物理に属しており、Ｃ４は化学に属している。本発明のクラシファイアは、次に続く新しい文書Ｎ：「Ｔｈｅ  Ｅｌｅｍｅｎｔｓ  ｏｆ  Ｃｏｍｐｕｔｉｎｇ  Ｓｃｉｅｎｃｅ（電子計算学の要素）」を以下のように分類するように設定することができる。
【００６８】
本実施例では「共通の」単語の従来の一致方法は機能しない。何故ならば、新しい文書内の単語「ｃｏｍｐｕｔｉｎｇ」および「ｓｃｉｅｎｃｅ」はＣ１とＣ４に別々に出現し、単語「ｅｌｅｍｅｎｔ」はＣ２とＣ３の両方で同時に出現し、複数文書で単に「共通の」単語を数えることによって分類の適切な候補はまったく示されない。
【００６９】
本実施例の場合、ＤＬＳＩベースのクラシファイアとＬＳＩベースのクラシファイアの設定は、単に出現頻度を数えるだけの表１のような文書行列によるタームを求めるデータベースの文書ベクトルを設定することによって開始される。正規化された形式を表２に示す。
【００７０】
【表１】
2004536383.tif 000029
【００７１】
【表２】
2004536383.tif 000030
新しい文書Ｎに対する文書ベクトルは、
（０，０，０，０，１，０，０，１，０，０，０，０，０，０，１，０，０，０）Ｔによって求められ、正規化された形式は、
０，０，０，０，０．５７７３５０２６９，０，０，０．５７７３５０２６９，０，０，０，０，０，０，０．５７７３５０２６９，０，０，０）Ｔによって求められる。
【００７２】
ＤＬＳＩ空間ベースのクラシファイアの場合、各クラスタの重心の正規化された形式は表３で求めることができる。
【００７３】
【表３】
2004536383.tif 000031
【００７４】
前節の手順に引き続き、文書行列Ｄ１８×４Ｉによる内部差分タームと文書行列Ｄ１８×４Ｅによる外部差分タームの両方を、それぞれ表４および表５のように構成することができる。
【００７５】
【表４】
2004536383.tif 000032
【００７６】
【表５】
2004536383.tif 000033
【００７７】
Ｄ１およびＤＥが与えられると、これらはＳＶＤアルゴリズムを使用してＤ１＝Ｕ１Ｓ１ＶＴ１とＤＥ＝ＵＥＳＥＶＴＥＩに分解される。上式で、
【００７８】
【数２８】
2004536383.tif 000034
【００７９】
【数２９】
2004536383.tif 000035
である。
【００８０】
δｋ−δｋ＋１が十分な大きさに維持されるように個数ｋが選定される。分類子をテストする一例としてはｋＩ＝ｋＥ＝１およびｋＩ＝ｋＥ＝３である。次に方程式（３）、（４）、および（５）を使用すると、表６に示すように差分文書ベクトルｘ＝Ｎ−Ｃｉ（ｉ＝１，２，３，４）ごとにＰ（ｘ｜ＤＩ）、Ｐ（ｘ｜ＤＥ）、最終的にはＰ（ＤＩ｜ｘ）を計算することができる。最大のＰ（ＤＩ（Ｎ−Ｃｉ））を有するＣｉが、新しい文書Ｎが属するクラスタとして選定される。どちらのｎＥも実際には非常に小さいので本発明者らは、ここで、
【００８１】
【数３０】
2004536383.tif 000036
を設定したことに留意されたい。表６の最終行から、一組のパラメータｋＩ＝ｋＥ＝１またはｋＩ＝ｋＥ＝３が選定されたか否かに関わらず、クラスタ２、すなわち「Ｍａｔｈｅｍａｔｉｃｓ」を選定すべきであることが理解できる。
【００８２】
【表６】
2004536383.tif 000037
【００８３】
ＬＳＩベースのクラシファイアは、まずＬＳＩ空間を設定するために文書行列によるターム上でＳＶＤアルゴリズムを使用することによって機能し、次いでＬＳＩ空間内で分類が完了する。
【００８４】
現在の簡単な例の場合、ＬＳＩベースのクラシファイアは以下のようにして設定することができる。最初に、表２に示す文書行列による正規化されたタームを分解するためにＳＶＤが使用される。２番目に、ＬＳＩ空間が選択される。３番目に、ＬＳＩ空間内のすべての文書Ｔ１，Ｔ２，．．．，Ｔ８に対する近似文書が探し出される。４番目に、各クラスタの重心が求められ、最後に、分類されるべき新しい文書Ｎに対する文書ベクトルの類似性が計算され、これによって余弦公式に基づいて重心ベクトルが求められ、分類されるべき文書ベクトルとの最大の類似性を有するクラスタが求められる。
【００８５】
表２の文書行列Ｄによる正規化されたタームがＳＶＤアルゴリズムによってＵＳＶＴに分解される。ここで、
【００８６】
【数３１】
2004536383.tif 000038
である。
【００８７】
ＤＬＳＩの計算のように、δｋ−δｋ＋１が十分に大きくなるように最大の固有値を計算する際に使用される個数ｋが選定される。結果をテストするためにクラシファイアを設定する一例として、ｋ＝６およびｋ＝２を作成する。類似性がＬＳＩ空間内のベクトル間の角度として計算されることに注目すると、ｋが１よりも大きくなるようにＬＳＩ空間の次元は少なくとも２であるべきである。ｋが選定されると、文書行列ＤによるタームはＤｋ＝ＵｋＳｋＶＴｋによって近似することができる。したがって、ＬＳＩ空間上への文書Ｔｉの射影は、ｅｉを８×８の識別行列のｉ番目の列と定義して、ＳｋＶＴｋｅｉとなるよう計算される。文書のこれらの射影を表７に示す。類似性はＬＳＩ空間内の角度の余弦として計算されるので、各クラスタの重心ベクトルは正規化されたメンバー文書の平均値として計算すべきである。これらの重心ベクトルを表８に示す。ここで、表のＣｉはクラスタＣｉの重心を示している。ＬＳＩ空間内における分類されるべき文書、文書Ｎの射影も表８に示す。ここで、射影は、Ｎを正規化されたベクトルとしてＵＴｋＮとして計算される。重心ベクトルとＬＳＩ空間内の文書との間の類似性は、以下に表すように、空間内の角度の余弦に従って計算される。
【００８８】
【数３２】
2004536383.tif 000039
【００８９】
類似性の結果を表９に示し、ｋ＝２およびｋ＝６の両方の場合に、文書Ｎが属する可能性が最も高いクラスタはＣ３、すなわち「Ｐｈｙｓｉｃｓ」であることを導く。
【００９０】
【表７】
2004536383.tif 000040
【００９１】
【表８】
2004536383.tif 000041
【００９２】
【表９】
2004536383.tif 000042
【００９３】
この単純な実施例の場合、ＤＬＳＩ空間ベース方式は、Ｉ−ＤＬＳＩおよびＥ−ＤＬＳＩ空間に対して１次元または３次元を使用してクラシファイアから文書「Ｔｈｅ  Ｅｌｅｍｅｎｔｓ  ｏｆ  Ｃｏｍｐｕｔｉｎｇ  Ｓｃｉｅｎｃｅ」に対する最適なクラスタを求める。
【００９４】
しかしＬＳＩ方式は、２次元または４次元ＬＳＩ空間を使用して計算されたクラシファイアのどちらに対してもこれを予測することができない。特定の実施例に関して、ＤＬＳＩ空間に対する１次元または３次元と、ＬＳＩ空間に対する２次元または４次元は、選定するために最適な次元を表していることに留意されたい。
【００９５】
１つの実施例だけを具体的に説明したが、この実施例は例示のみによって与えられたものであることが理解されよう。したがって上記の説明は、本発明の原理のみの説明と見なされるべきである。本発明は様々な文書分類タスクに対処するよう構成することができ、本発明の多くの応用例は当業者には容易に想起されよう。したがって、開示した特定の実施例、または図示および記述した構成および動作通りに本発明を限定することは望まない。むしろ本発明の範囲に含まれるすべての適切な修正形態および等価形態を用いることができる。
【図面の簡単な説明】
【００９６】
【図１】本発明によるＤＬＳＩ空間ベース分類子の設定を説明する流れ図である。
【図２】本発明によるＤＬＳＩ空間ベース分類子による文書の自動分類手順を示す流れ図である。
【図１】
2004536383.tif 000054
【図２】
2004536383.tif 000055
【国際公開パンフレット】
2004536383.tif 000056
2004536383.tif 000057
2004536383.tif 000058
2004536383.tif 000059
2004536383.tif 000060
2004536383.tif 000061
2004536383.tif 000062
2004536383.tif 000063
2004536383.tif 000064
2004536383.tif 000065
2004536383.tif 000066
2004536383.tif 000067
2004536383.tif 000068
2004536383.tif 000069
2004536383.tif 000070
2004536383.tif 000071
2004536383.tif 000072
2004536383.tif 000073
2004536383.tif 000074
2004536383.tif 000075
2004536383.tif 000076
2004536383.tif 000077
2004536383.tif 000078
2004536383.tif 000079
2004536383.tif 000080
2004536383.tif 000081
2004536383.tif 000082
2004536383.tif 000083
2004536383.tif 000084
2004536383.tif 000085
2004536383.tif 000086
【国際公開パンフレット（コレクトバージョン）】
2004536383.tif 000087
2004536383.tif 000088