(57)【特許請求の範囲】
【請求項１】
コンピューターが実行する方法であって、前記コンピューターが、
第１の単語と第２の単語との間の定量的関係を記述する前記第１の単語と前記第２の単語との間の複数の親和度が記録されたレコードであって、１又は複数の記憶媒体に格納された前記レコードにアクセスする段階、
第１の単語と第２の単語との間の親和度が１又は複数の親和度基準を満たす場合に前記第１の単語は前記第２の単語と十分に親和性があり、１つのクラスタは互いに十分に親和性のある１又は複数の単語を有し、複数の親和度に従い前記複数の単語の複数のクラスタを識別する段階、
前記クラスタを用いクラスタ分析を実行し結果を生成する段階、及び
前記クラスタ分析の結果を報告する段階、を実行し、
前記親和度は、方向親和度又は差分親和度であり、前記第１及び第２の単語からそれぞれ前記第１及び第２の単語の現れる位置へのマッピングを格納するインデックス・データ構造である転置インデックスに基づき計算される、ことを特徴とする方法。
【請求項２】
前記複数の親和度に従い前記複数の単語の複数のクラスタを識別する段階は、クラスタを構築する段階を更に有し、前記クラスタの構築は、前記コンピューターが、
前記クラスタ内にシード単語を配置する段階、並びに
前記クラスタに追加された単語のそれぞれに対し、
−各単語と現在の単語との間の前方親和度に従い前記複数の単語をソートする段階、
−前記１又は複数の親和度基準は、前記現在の単語との前方親和度基準と前記シード単語との後方親和度基準とを有し、前記１又は複数の親和度基準を満たす１又は複数の候補単語を識別する段階、及び
−前記１又は複数の候補単語を前記クラスタ内に配置する段階、を繰り返す段階、を実行することにより行われる、請求項１記載の方法。
【請求項３】
前記複数の親和度に従い前記複数の単語の複数のクラスタを識別する段階は、前記単語を前記クラスタにソートする段階を更に有し、前記ソートは、前記複数の単語のそれぞれに対し、前記コンピューターが、
前記単語のそれぞれとクラスタの第１の単語との間の親和度が閾親和度を満たしている場合に、前記単語のそれぞれを前記クラスタ内に配置する段階、及び
その他の場合に、前記単語のそれぞれを空のクラスタに配置する段階、を繰り返し実行することにより行われる、請求項１記載の方法。
【請求項４】
前記複数の親和度に従い前記複数の単語の複数のクラスタを識別する段階は、前記単語の複数の親和度ベクトルを比較する段階を更に有し、前記比較は、前記コンピューターが、
親和度ベクトルは単語と関連付けられ複数の親和度値を有し、親和度値は前記関連付けられた単語と別の単語との間の親和度を示し、前記親和度値を記録する前記複数の親和度ベクトルを求める段階、
互いに近い親和度ベクトルのセットを識別する段階、及び
クラスタ内に前記親和度ベクトルのセットと関連付けられた単語を配置する段階、を実行することにより行われる、請求項１記載の方法。
【請求項５】
前記クラスタを用いクラスタ分析を実行し結果を生成する段階は、前記コンピューターが前記クラスタに従い前記複数の単語を有するページを分類する段階、を更に有する、請求項１記載の方法。
【請求項６】
前記クラスタを用いクラスタ分析を実行し結果を生成する段階は、前記クラスタに従い前記複数の単語を有するページを分類する段階、を更に有し、前記分類は、前記コンピューターが、
前記ページの１又は複数の重要な単語を選択する段階、
前記１又は複数の重要な単語を有する前記複数のクラスタのうち１又は複数のクラスタを決定する段階、及び
前記１又は複数のクラスタに従い前記ページを分類する段階、を実行することにより行われる、請求項１記載の方法。
【請求項７】
前記クラスタを用いクラスタ分析を実行し結果を生成する段階は、前記コンピューターが前記クラスタに従い前記複数の単語を有するコーパスのコーパス特性を決定する段階、を更に有する、請求項１記載の方法。
【請求項８】
前記クラスタを用いクラスタ分析を実行し結果を生成する段階は、前記コンピューターが、
所与の検索クエリの１又は複数の検索語を有する複数のクラスタのうちの１又は複数のクラスタを決定する段階、
前記１又は複数のクラスタから１又は複数の単語を選択する段階、及び
前記選択された１又は複数の単語を報告する段階、を有する、請求項１記載の方法。
【請求項９】
前記クラスタを用いクラスタ分析を実行し結果を生成する段階は、前記コンピューターが、
所与の検索クエリの１又は複数の検索語を有する複数のクラスタのうちの１又は複数のクラスタを決定する段階、
前記１又は複数のクラスタから１又は複数の単語を選択する段階、及び
前記選択された１又は複数の単語から１又は複数の次の検索クエリを生成する段階、を有する、請求項１記載の方法。
【請求項１０】
前記クラスタを用いクラスタ分析を実行し結果を生成する段階は、前記コンピューターが、それぞれの人がユーザー識別子と関連付けられた人々の社会的ネットワークを分析する段階を更に有し、前記単語は前記ユーザー識別子を有し、
前記分析は、前記コンピューターが、前記クラスタに従い前記人々の間の１又は複数の関係を決定する段階を実行することにより行われる、請求項１記載の方法。
【請求項１１】
前記１又は複数の有形記憶媒体に格納された前記レコードにアクセスする段階は、前記コンピューターが、複数の単語を有する複数のデータ・セットから生成された親和度値にアクセスする段階、を更に有し、
前記複数の親和度に従い前記複数の単語の複数のクラスタを識別する段階は、前記コンピューターが、データ・セット毎にクラスタ・セットを識別する段階、を更に有し、
前記クラスタを用いクラスタ分析を実行し結果を生成する段階は、前記コンピューターが、第１のデータ・セットの第１のクラスタ・セットを、第２のデータ・セットの第２のクラスタ・セットと比較し、前記第１のデータ・セットと前記第２のデータ・セットとの間の関係を分析する段階、を更に有する、請求項１記載の方法。
【請求項１２】
コンピューターに、
第１の単語と第２の単語との間の定量的関係を記述する前記第１の単語と前記第２の単語との間の親和度であって、方向親和度または差分親和度である複数の親和度を記録するレコードにアクセスする段階であって、前記親和度は、前記第１及び第２の単語からそれぞれ前記第１及び第２の単語の現れる位置へのマッピングを格納するインデックス・データ構造である転置インデックスに基づき計算される、段階、
第１の単語と第２の単語との間の親和度が１又は複数の親和度基準を満たす場合に前記第１の単語は前記第２の単語と十分に親和性があり、１つのクラスタは互いに十分に親和性のある１又は複数の単語を有し、複数の親和度に従い前記複数の単語の複数のクラスタを識別する段階、
前記クラスタを用いクラスタ分析を実行し結果を生成する段階、及び
前記クラスタ分析の結果を報告する段階、を実行させるためのソフトウェアを記憶したコンピューター読取可能な記憶媒体。
【請求項１３】
前記ソフトウェアは、前記コンピューターに、クラスタを構築することにより、前記複数の親和度に従い前記複数の単語の複数のクラスタを識別させ、前記構築は、前記コンピューターに、
前記クラスタ内にシード単語を配置する段階、並びに
前記クラスタに追加された単語毎に、
−各単語と現在の単語との間の前方親和度に従い前記複数の単語をソートする段階、
−前記１又は複数の親和度基準は、前記現在の単語との前方親和度基準と前記シード単語との後方親和度基準とを有し、前記１又は複数の親和度基準を満たす１又は複数の候補単語を識別する段階、及び
−前記１又は複数の候補単語を前記クラスタ内に配置する段階、を繰り返す段階、を実行させることにより行われる、請求項１２記載のコンピューター読取可能な記憶媒体。
【請求項１４】
前記ソフトウェアは、前記コンピューターに、クラスタに単語をソートすることにより、複数の親和度に従い複数の単語の複数のクラスタを更に識別させ、前記識別は、前記コンピューターに、前記複数の単語のそれぞれに対し、
前記単語のそれぞれとクラスタの第１の単語との間の親和度が閾親和度を満たしている場合に、前記単語のそれぞれを前記クラスタ内に配置する段階、及び
その他の場合に、前記単語のそれぞれを空のクラスタに配置する段階、を繰り返し実行させることにより行われる、請求項１２記載のコンピューター読取可能な記憶媒体。
【請求項１５】
前記ソフトウェアは、前記コンピューターに、前記単語の複数の親和度ベクトルを比較することにより、前記複数の親和度に従い前記複数の単語の前記複数のクラスタを更に識別させ、前記比較は、前記コンピューターに、
親和度ベクトルは単語と関連付けられ複数の親和度値を有し、親和度値は前記関連付けられた単語と別の単語との間の親和度を示し、前記親和度値を記録する前記複数の親和度ベクトルを求める段階、
互いに近い親和度ベクトルのセットを識別する段階、及び
クラスタ内に前記親和度ベクトルのセットと関連付けられた単語を配置する段階、を実行させることにより行われる、請求項１２記載のコンピューター読取可能な記憶媒体。
【請求項１６】
前記ソフトウェアは、前記コンピューターに、前記クラスタに従い前記複数の単語を有するページを分類することにより、前記クラスタを用いクラスタ分析を実行し結果を更に生成させる、請求項１２記載のコンピューター読取可能な記憶媒体。
【請求項１７】
前記ソフトウェアは、前記コンピューターに前記クラスタに従いページを分類することにより、前記クラスタを用いクラスタ分析を実行し結果を生成させ、
前記分類は、前記コンピューターに、
前記ページの１又は複数の重要な単語を選択する段階、
前記１又は複数の重要な単語を有する前記複数のクラスタのうち１又は複数のクラスタを決定する段階、及び
前記１又は複数のクラスタに従い前記ページを分類する段階、を実行させることにより行われる、請求項１２記載のコンピューター読取可能な記憶媒体。
【請求項１８】
前記ソフトウェアは、前記コンピューターに、前記クラスタに従い前記複数の単語を有するコーパスのコーパス特性を決定することにより、前記クラスタを用いクラスタ分析を実行し結果を更に生成させる、請求項１２記載のコンピューター読取可能な記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般に語彙分析に関し、より詳細には単語親和度による単語クラスタの識別に関する。
【背景技術】
【０００２】
データのコーパスは大量の情報を持っており、必要な情報を発見するのが困難である。キーワード検索は情報発見のための主要な技術である。しかしながら、ある状況では、キーワード検索は情報を発見する際に効率的でない。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
本発明は、単語親和度による単語クラスタの識別のための方法、プログラム、及びシステムを提供する。
【課題を解決するための手段】
【０００４】
ある実施例では、単語のクラスタを識別する段階は、親和度を記録するレコードにアクセスする段階を有する。第１及び第２の単語の間の親和度は、第１及び第２の単語の間の定量的関係を記述する。単語のクラスタは、親和度に従い識別される。クラスタは、互いに十分に親和性のある単語を有する。第１及び第２の単語の間の親和度が１又は複数の親和度基準を満たす場合、第１の単語は第２の単語と十分に親和性がある。クラスタ分析はクラスタを用いて実行される。
【発明を実施するための最良の形態】
【０００５】
ある実施例では、ドメイン・オントロジーを生成し問い合わせる段階は以下を含む。
【０００６】
１．ドメイン内文書の収集
ある実施例では、文書は言葉の集合である。文書は読める文字を有し、例えば新約聖書である。文書は物語形式の文字を有する必要はない。文書は、個々に集合的に心象の内容を記述するユーザーにより入力された一式の文法標識を有してよい。文書の集合は「領域コーパス」として参照される。
【０００７】
２．領域内の関心のある言葉（「辞書の言葉」）の識別
言葉の例として、単語（例えば「tree（木）」）、句（例えば「graph  algorithm（グラフの理論）」）、名詞（例えば「New  York（ニュー・ヨーク）」）等がある。言葉（又は概念）は異なる形式を有してよい。ある場合には、異なる単語が同一の概念に用いられる。例えば「kidney  stones（腎臓結石）」と「kidney  calculi（腎結石）」は同一の概念である「kidney  stones（腎臓結石）」を表す。別の場合には、語幹は多くの変異形を有する。例えば、語幹「trre（木）」は「tree（木）」と「trees（木々）」を有する。ある実施例では、同一の言葉の形式は同一の言葉にマップされるとして扱われてよい。辞書の言葉の適切な形式は文書内に現れてもよいが、特定の辞書の言葉は如何なる文書にも現れなくてもよい。
【０００８】
辞書の言葉を識別する方法の例は、人間により作成された特定領域の辞書、例えば医学辞典を用いる段階を有する。ある実施例では、辞書の言葉のリストはコーパス内の一式の文字列から自動的に生成される。文字列は頻度によりインデックス付けされソートされ、閾値より高い頻度の文字列が選択されてよい。他の適切な統計的方法は、言葉を定めるために用いられてよい。ある実施例では、「単語」は「言葉」及び「辞書の言葉」と置き換え可能であってよい。
【０００９】
３．所与の共起文脈内の辞書の単語の共起数の計算
２つの言葉が同一の共起文脈内でそれぞれ少なくとも１回現れた場合、当該２つの言葉は同時に起こる。共起文脈の例には、文書及び段落がある。
【００１０】
４．領域オントロジーを有する方向重み付けグラフの作成
方向重み付けグラフは、辞書の言葉をノードとして、及び親和度を端の重みとして有する。「方向重み付けグラフ」は、如何なる適切なデータ構造、例えば行列、二分決定グラフ、又は二分決定グラフの集合によっても表現される同一情報の実際の表現として用いられてよい。
【００１１】
５．方向重み付けグラフの問い合わせ手順の適用
１又は複数の辞書の言葉が入力として与えられると、当該手順は当該入力された辞書の言葉と関連した１又は複数の辞書の言葉を出力する。例えば、当該手順は、１又は複数の入力された言葉に対し最も大きな差異がある方向親和度を持つ「１又は複数の」ソートされたリストを出力してよい。この場合、出力は、オントロジーが解決する領域と関連して、入力された言葉に一層緊密に関連した言葉を含む。
【００１２】
如何なる適切な親和度の定義が用いられてもよい。ある実施例では、以下が用いられてよい。
【００１３】
（１）基本親和度
A．言葉AとBとの間の基本親和度（A）は、言葉AとBの両方を含む共起文脈の数の、言葉AとBの何れかを含む共起文脈の数に対する比として定義されてよい。
A(A,B)=|AB|/|AorB|
B．言葉AとBとの間の基本親和度（A）は、言葉AとBの両方を含む共起文脈の数の、言葉Aを含む共起文脈の数又は言葉Bを含む共起文脈の数の何れかの最大値に対する比として定義されてよい。
A(A,B)=|AB|/max(|A|,|B|)
（２）方向親和度
言葉AとBとの間の方向親和度（DAff）は、Aが共起文脈に現れた場合に、Bが現れる条件付き確率として定義される。
DAff(A,B)=|AB|/|A|
つまり、方向親和度は、言葉Aを含む共起文脈の数に対する、言葉AとBの両方を含む共起文脈の数である。一般的に、DAff(A,B)はDAff(B,A)と異なる。
【００１４】
（３）差分方向親和度
言葉AとBとの間の差分方向親和度（DiffDAff）は、言葉AとBとの間の方向親和度からコーパス内の言葉Bの共通性を示す要素を差し引いたものとして定義される。コーパス内の言葉Bの共通性は、言葉Bの、コーパス内の他の言葉に対する基本親和度又は方向親和度の値に対する統計値であってよい。ある実施例では、コーパス内の言葉Bの共通性は、言葉Bの平均親和度（AA）であってよく、方向親和度の次の定義に従う。
DiffDAff(A,B)=DA(A,B)-AA(B)
言葉Bの平均親和度（AA）、又は平均方向親和度は、次のように定義される。
AA(B)=AVERAGE_xDAff(x,B)
つまり、平均親和度は、言葉Bの、共起文脈内の他の言葉に対する方向親和度の平均である。
【００１５】
図１は、単語のクラスタを識別するシステム１０のある実施例を示す。ある実施例では、システム１０は単語間の親和度から単語のクラスタを識別する。クラスタは、互いに十分に親和性のある単語を含む。ここで、十分な親和性があるとは、１又は複数の親和度基準に従い決定される。ある実施例では、システム１０はクラスタ分析を実行する。クラスタ分析の例は、ページのクラスタに従いページを分類する段階、コーパスのクラスタからコーパス特性を決定する段階、及びユーザーの文書内のクラスタに基づきユーザーを分析する段階、を有する。
【００１６】
ある実施例では、方向親和度は、特定の転置インデックスIIに基づき、所与の単語のサブセット及び辞書Ｄに対し計算されてよい。ここで、インデックスIIは例えば単語wi及びwjのエントリI(wi)及びI(wj)を含む。一般に、転置インデックスは、言葉から当該言葉の位置、つまり言葉が現れる共起文脈へのマッピングを格納するインデックス・データ構造である。D内の言葉の対wi及びwj毎に、DA(i,j)は、I(wi)内の値の数により除算されたII内のエントリI(wi)、I(wj)の連結の値として定められてよい。一般に、DA(i,j)は必ずしもDA(j,i)に等しくない。結果は、D(１,i)が格納され次にD(２,j)が格納される等の例えば行方向に如何なる適切な方法で格納されてもよい。行i毎に、|I(wi)|が格納され、次にwjとの連結の候補が続いて格納される。
【００１７】
ある実施例では、方向親和度は３つの段階で計算される。この実施例では、辞書の各言葉は固有の整数識別子を割り当てられる。転置インデックスのエントリは整数識別子に対応する。段階０で、Dに対応するIIエントリが読み出される。パラメータ(s,o)に対し、ks+oを形成する要素識別子のみが保持される。値ks+oは、検査されるべきIIエントリのサブセットを定める。この方法では、方向親和度は並列に計算される。例として、パラメータs,o(１,０)からの結果はパラメータ(３,０),(３,１),(３,２)の計算の統合から得られた結果と等しい。この段階は非常に大きい転置インデックスのDAテーブルの計算を可能にする。
【００１８】
段階１で、連結が行方向にDA(i,j)のみに対し計算される。段階２で、計算された上側の三角形UT  DA配列が読み出される。これにより、下側の三角部分は、ＵＴの置換として得られる。ある実施例では、同一次元の複数のDA配列が単一の配列に統合されてよい。大きいIIのDA配列は、パラメータ(s,i)によりsumi=０..(s-１)DAとして計算される。追加情報は、方向親和度が計算できるように、計算された連結と共に格納されてよい。ある場合には、IIエントリの候補が格納されてよい。
【００１９】
ある実施例では、DAは行方向に格納されてよい。従って、AAエントリの計算は、DAエントリの計算と並列に進められてよい。特に、AAはDAの行を、ディスクから読み出されるときに加算することにより生成され、最後に辞書のエントリの数により正規化されてよい。
【００２０】
図示された実施例では、システム１０はクライアント２０、サーバー２２、及びメモリー２４を有する。クライアント２０は、ユーザーがサーバーと通信し、言語のオントロジーを生成することを可能にする。クライアント２０は、ユーザー入力をサーバー２２へ送信し、サーバー出力（例えば、表示又は印刷）をユーザーへ提供してよい。サーバー・システム２４は、言語のオントロジーを生成するアプリケーションを管理する。メモリー２４は、サーバー・システム２４により用いられるデータを格納する。
【００２１】
図示された実施例では、メモリー２４は、ページ５０及び記録５４を格納する。ページ５０（又は文書、又は共起文脈）は、単語の集合として参照されてよい。ページ５０の例には、文書の１又は複数のページ、１又は複数の文書、１又は複数の書籍、１又は複数のウェブ・ページ、書簡（例えば、電子メール、又はインスタント・メッセージ）、及び／又は他の言葉の集合がある。ページ５０は、ページ識別子により識別されてよい。ページ５０は、１又は複数の有形のコンピューター可読媒体に電子的に格納されてよい。ページ５０は、如何なる適切なコンテンツ、例えばテキスト（文字、単語、及び／又は数字など）、画像（グラフィック、写真、又はビデオなど）、音声（録音、又はコンピューターにより生成された音）、及び／又はソフトウェア・プログラムと関連付けられてもよい。ある実施例では、ページ５０のセットはコーパスに属してよい。コーパスは、特定の主題、コミュニティ、組織、又は他のエンティティと関連付けられてよい。
【００２２】
記録５４は、ページ５０を記述する。ある実施例では、記録５４は、インデックス５８、転置インデックス６２、オントロジー６６、及びクラスタ６７を有する。インデックス５８は、ページ５０の単語を示すページ５０のインデックス・リストを有する。転置インデックス６２は、転置インデックス・リストを有する。単語（又は単語のセット）の転置インデックス・リストは、当該単語（又は単語のセット）を含むページ５０を示す。ある例では、リストWiは単語wiを含むページ５０のページ識別子を含む。リストWi&Wjは単語wi及びwiの両方を含む連結ページ５０のページ識別子を含む。リストWi＋Wjは単語wi又はwjの一方を含む離接ページ５０のページ識別子を含む。P(Wi)は、Wiのページ５０の数、つまり単語wiを含むページ５０の数である。
【００２３】
ある実施例では、リスト（インデックス・リスト又は転置インデックス・リスト等）は二分決定グラフ（BDD）として格納されてよい。ある例では、セットWiの二分決定グラフBDD（Wi）は、単語wiを有するページ５０を表す。BDD(Wi)をSatisf(BDD(Wi))に代入することにより、単語wiを有するページ５０の数P(Wi)を得る。
P(Wi)=Satisf(BDD(Wi))
従って、
P(Wi&Wj)=Satisf(BDD(Wi)ANDBDD(Wj))
P(Wi+Wj)=Satisf(BDD(Wi)ORBDD(Wj))
オントロジー６６は、言語の単語及び単語間の関係を表す。ある実施例では、オントロジー６６は単語間の親和度を表す。図示された例では、オントロジー６６は親和度行列及び親和度グラフを有する。親和度行列の例は、図３乃至図５を参照して説明される。親和度グラフの例は、図６を参照して記載される。クラスタ６７は、互いに関係している単語のクラスタを記録する。クラスタは、図７を参照して以下に詳細に記載される。
【００２４】
図示された実施例では、サーバー２２は親和度モジュール３０、及びクラスタ・モジュール３１を有する。親和度モジュール３０は、単語対の親和度を計算し、親和度行列に親和度を記録し、及び／又は親和度行列を報告する。親和度モジュール３０は、親和度グラフを生成してもよい。親和度モジュール３０は、図２を参照して以下に詳細に記載される。
【００２５】
ある実施例では、クラスタ・モジュール３１は、データ・セット内の関連要素のクラスタを識別することにより、データ・セット内のパターンを発見してよい。特定の実施例では、クラスタ・モジュール３１は単語のセット（例えば、言語又はページ５０のセット）のクラスタを識別してよい。一般に、クラスタの単語は互いに深く関連しているが、クラスタ外の単語とは関連しない。単語のクラスタは、単語のセットの主題（又は題目）を指定してよい。ある実施例では、クラスタ・モジュール３１は単語間の親和度に従い関連単語のクラスタを識別する。ある実施例では、クラスタの単語は互いに高い親和度を有しているが、クラスタ外の単語とは高い親和度を有しない。クラスタ・モジュール３１は、図７を参照して以下に詳細に説明される。
【００２６】
システム１０の構成要素は、インターフェース、ロジック、メモリー、及び／又は他の適切な構成要素を有してよい。インターフェースは入力を受信し、出力を送信し、入力及び／又は出力を処理し、及び／又は他の適切な動作を実行する。インターフェースはハードウェア及び／又はソフトウェアを有してよい。
【００２７】
ロジックは、構成要素の動作を実行し、例えば命令を実行して入力から出力を生成する。ロジックはハードウェア、ソフトウェア、及び／又は他のロジックを有してよい。ロジックは、１又は複数の有形媒体内に符号化されてよく、コンピューターにより実行されたときに動作を実行してよい。プロセッサーのような特定のロジックは、構成要素の動作を管理してよい。プロセッサーの例には、１又は複数のコンピューター、１又は複数のマイクロプロセッサー、１又は複数のアプリケーション、及び／又は他のロジックがある。
【００２８】
メモリーは情報を格納する。メモリーは１又は複数の有形のコンピューター可読媒な及び／又はコンピューターにより実行可能な記憶媒体を有してよい。メモリーの例には、コンピューター・メモリー（例えば、ランダム・アクセス・メモリー（ＲＡＭ）又は読み出し専用メモリー（ＲＯＭ）、大容量媒体（例えば、ハードディスク）、着脱可能記憶媒体（例えば、コンパクト・ディスク（ＣＤ）又はデジタル・ビデオ・ディスク（ＤＶＤ）、データベース及び／又はネットワーク記憶装置（例えば、サーバー）、及び／又は他のコンピューター可読媒体））がある。
【００２９】
本発明の範囲から逸脱することなくシステム１０に対し変更、追加、又は省略が行われて良い。システム１０の構成要素は統合されてよく、又は分離されてよい。更に、システム１０の動作は更に多くの、更に少ない、又は他の構成要素により実行されて良い。例えば、生成器４２及び４６の動作は、１つの構成要素により実行されてよい。または、親和度計算機３４の動作は１つより多い構成要素により実行されてよい。更に、システム１０の動作は、ソフトウェア、ハードウェア、及び／又は他のロジックを有する如何なる適切なロジックを用い実行されて良い。本願明細書で用いられるように、「各」の語はセットの各構成要素、又はセットの下位セットの各構成要素を表す。
【００３０】
本発明の範囲から逸脱することなく行列の例に対し変更、追加、又は省略が行われて良い。行列は、より多くの、より少ない、又は他の値を有して良い。更に、行列の値は如何なる適切な順序に配置されてもよい。
【００３１】
図２は、図１のシステム１０と共に用いられ得る親和度モジュール３０のある実施例を示す。親和度モジュール３０は、単語対の親和度を計算し、親和度行列に親和度を記録し、及び／又は親和度行列を報告する。親和度モジュール３０は、親和度グラフも生成する。
【００３２】
図示された実施例では、親和度モジュール３０は、親和度計算機３４、オントロジー生成器３８、及び単語推奨器４８、を有する。親和度計算機３４は、単語wiの、又は第１の単語wi及び第２の単語wjを有する単語対の適切な種類の親和度を計算する。親和度の例には、基本、方向、平均、差分、及び／又は他の親和度がある。
【００３３】
ある実施例では、単語推奨器４８は、シード単語を受信し、当該シード単語との閾親和度より大きい親和度を有する単語を識別する。閾親和度は、如何なる適切な値、例えば０．２５、０．５、０．７５、又は０．９５より大きいか又は等しい値を有してもよい。閾親和度は、予め設定されるか又はユーザーにより指定されてよい。
【００３４】
基本親和度は、単語wi及びwjを含むページ５０の量（例えば、数）から計算されてよい。連結ページ量は単語wi及び単語wjの両方を含むページ５０の量を表す。また、離接ページ量は単語wi及び単語wjの一方を含むページ５０の量を表す。基本親和度は、分離ページ量により除算された連結ページ量により与えられてよい。ある例では、連結ページ数は単語wi及び単語wjを含むページの数を有する。また、離接ページ数は単語wi及び単語wjを含むページの数を有する。基本親和度は、分離ページ数により除算された連結ページ数により与えられてよい。
Affinity(wi,wj)=P(Wi&Wj)/P(Wi+Wj)
図３は、基本親和度を記録する親和度行列１１０の例を示す。図示された例では、親和度行列１１０は単語w１．．．w５の対の親和度を記録する。親和度行列１１０によると、親和度は、単語w０とw１との間は０．００３、単語w０とw２との間は０．００５であり、その他同様である。
【００３５】
再び図１を参照する。親和度グループは、互いに高い親和度を有する単語対を有する。また、当該単語対はページ内容に関して単語w１及びw２の間の関係を捉えるために用いられてよい。高い親和度は、親和度グループ閾より高い親和度として指定されてよい。閾は、如何なる適切な値、例えば０．５０、０．６０、０．７５、０．９０又は０．９５より大きいか又は等しい値に設定されてよい。単語は１より多い親和度グループに属してよい。ある実施例では、親和度グループはBDDとして表されてよい。BDDのポインタは、転置インデックス６２にグループの各単語と共に格納されてよい。
【００３６】
方向親和度は、単語wjに関する単語wiの重要性を測定するために用いられてよい。親和度計算機３４は、単語wi及びwjを含むページ５０の量（例えば、数）から、単語wjを与えられた場合の単語wiの方向親和度を計算する。単語wjのページ量は単語wiを含むページ５０の量を表す。単語wjを与えられた場合の単語wiの方向親和度は、連結ページ量を単語wjのページ量により除算することにより求められる。例えば、単語wjのページ数は単語wjを含むページ５０の数を示す。単語wjを与えられた場合の単語wiの方向親和度は、連結ページ５０の数を単語wjのページ５０の数により除算することにより求められる。
DAffinity(wi,wj)=P(Wi&Wj)/P(Wi)
DAffinity(wi,wj)はDAffinity(wj,wi)と等しくない。単語wiとwjの間の方向親和度DAffinity(wi,wj)が高いことは、ページ５０が単語wjを含む場合にページ５０が単語wiを含む可能性が高いことを示す。ある例では、ページ［１２３４５６］は単語wiを含み、ページ［４２］は単語wjを含む。単語wjを含むページは単語wiも含む。従って、単語wjの観点から、単語wiは重要性が高い。単語wiを含むページの３分の１だけが単語wjも含む。従って、単語wiの観点から、単語wjは重要性が低い。
【００３７】
図４は、単語w０乃至w５の方向親和度を記録する親和度行列１２０の例を示す。この例では、単語１２４はA単語であり、単語１２８はB単語である。行列１２０の行はA単語が与えられた場合のB単語の親和度を記録し、行列１２０の列はB単語が与えられた場合のA単語の親和度を記録する。
【００３８】
再び図１を参照する。単語wiの平均方向親和度は、他の単語wjに対し計算される。ある実施例では、平均方向親和度は単語wiと他の各単語wjとの間の親和度の平均であってよい。N個の単語の単語wiの平均方向親和度は次式で与えられる。
【数１】
0005531395.tif 000002
【００３９】
図５は、平均親和度を記録する親和度行列１４０の例を示す。行１４２は単語１乃至単語５００００の基本親和度を記録する。行１４４は単語１乃至単語５００００の平均親和度を記録する。
【００４０】
再び図１を参照する。単語の平均親和度は、単語の難解さを示してよい。低い平均親和度を有する単語は、より難解な単語と考えられてよい。また、高い平均親和度を有する単語は、より平易な単語として考えられてよい。難解な単語は、より技術的、専門的、及び厳格である傾向がある。難解な単語の割合の高いページ５０は、より難解なページと考えられてよい。また、難解な単語の割合の低いページ５０は、より平易なページとして考えられてよい。ある実施例では、ユーザーは単語の難解さ及び／又は検索されるべきページ５０を指定してよい。
【００４１】
ページ５０の難解な単語は、深く関連した単語の１又は複数のクラスタを形成してよい。クラスタは共通の概念又は主題を表しうる。ページ５０の主題の数は、ページ５０の特異性を示してよい。より少ない主題を有するページ５０は、より専門的であると考えられてよい。また、より多くの主題を有するページ５０は、より専門的でないと考えられてよい。
【００４２】
単語wjに関する単語wiの差分親和度は、単語wiとwjとの間の方向親和度から、全ての他の単語に対する単語wjの平均親和度を減算したものである。差分親和度は次式のように表される。
DiffAff(wi,wj)=DAffinity(wi,wj)−AveAff(wj)
差分親和度は、ページ５０に生じる、単語wjの一般的傾向により引き起こされる偏向を除去する。特定の条件では、差分親和度は、ページが単語wjを含む場合に、当該ページが単語wiを含む確率のより高い精度を提供しうる。
【００４３】
差分親和度は種々の用途で用いられてよい。ある例では、人の名前の間の差分親和度は社会的ネットワークを調査するために用いられてよい。別の例では、言語要素の間の差分親和度は自然言語処理を調査するために用いられてよい。別の例では、製品の間の差分親和度はマーケティングを調査するために用いられてよい。
【００４４】
親和度計算機３４は、転置インデックス・リストを検索し親和度を計算するために如何なる適切な技術を用いてもよい。例えば、単語wi及びwjの両方を含むページを識別するために、親和度計算機３４は、単語wiのリストWi及び単語wjのリストWjから共通の要素、つまり共通のページ識別子を検索してよい。
【００４５】
ある実施例では、オントロジー生成器３８は、言語のオントロジー６６、例えば親和度行列又は親和度グラフを生成する。オントロジーは、基本、方向、平均、差分、及び／又は他の親和度のような如何なる適切な親和度から生成されてもよい。オントロジー６６は、如何なる適切な方法で言語から選択された単語から生成されてもよい。例えば、言語の一般的に用いられる部分からの単語、又は１又は複数の特定の主題の分野に関連する単語が選択されてよい。
【００４６】
図示された例では、オントロジー生成器３８は親和度行列生成器４２及び親和度グラフ生成器４６を有する。親和度行列生成器４２は、単語間の親和度を記録する親和度行列を生成する。親和度行列生成器４６は、単語間の親和度を表す親和度グラフを生成する。親和度グラフでは、ノードは単語を表し、ノード間の有効辺の重みはノードにより表された単語間の親和度を表す。親和度グラフは、如何なる適切な数の次元を有してもよい。
【００４７】
図６は、親和度グラフ１５０の例を示す。親和度グラフ１５０は、ノード１５４及びリンク１５８を有する。ノード１５４は単語を表す。この例では、ノード１５４Ａは単語「binary（二分）」を表す。ノード１５４間の有効辺の重みは、ノード１５４により表される単語間の親和度を表す。例えば、重みが大きいほど、親和度が大きいことを表す。ノード間のリンク１５８は、ノード１５４により表される単語間の親和度が閾親和度より高いことを示す。閾親和度は、如何なる適切な値、例えば０．２５、０．５、０．７５、又は０．９５より大きいか又は等しい値を有してもよい。
【００４８】
図７は、図１のシステム１０と共に用いられ得るクラスタ・モジュール３１のある実施例を示す。特定の実施例では、クラスタ・モジュール３１は、データ・セット内の関連要素のクラスタを識別することにより、データ・セット内のパターンを発見する。特定の実施例では、クラスタ・モジュール３１は単語のセット（例えば、言語又はページ５０のセット）のクラスタを識別してよい。一般に、クラスタの単語は互いに深く関連しているが、クラスタ外の単語とは関連しない。単語のクラスタは、単語のセットの主題（又は題目）を指定してよい。
【００４９】
ある実施例では、クラスタ・モジュール３１は単語間の親和度に従い関連単語のクラスタを識別する。ある実施例では、クラスタの単語は互いに高い親和度を有しているが、クラスタ外の単語とは高い親和度を有しない。ある実施例では、単語が十分に親和性を有する場合、単語は親和度が高いと考えられてよい。単語は、１又は複数の親和度基準を満たす場合に十分に親和性を有する。以下に例を示す。
【００５０】
如何なる適切な親和度がクラスタを識別するために用いられてもよい。ある実施例では、クラスタ・モジュール３１は方向親和度を用いる。ある単語の他の単語に関する方向親和度は、単語の共起を特徴付ける。クラスタは、同様の共起を有する単語を有する。ある実施例では、クラスタ・モジュール３１は差分親和度を用いる。差分親和度は、ページ５０に生じる、単語の一般的傾向により引き起こされる偏向を除去する。
【００５１】
図示された実施例では、クラスタ・モジュール３１はクラスタ・エンジン２１０、及びクラスタ分析器２１４を有する。クラスタ・エンジン２１０は、親和度に従い単語のクラスタを識別する。クラスタ分析器２１４は、親和度クラスタリングを行い、種々の状況を分析する。
【００５２】
クラスタ・エンジン２１０は、如何なる適切な方法で親和度により単語のクラスタを識別してもよい。クラスタを識別する方法の３つの例は、単語のセットからクラスタを構築する方法、単語をクラスタにソートする方法、及び単語の親和度ベクトルを比較する方法である。ある実施例では、クラスタ・エンジン２１０は単語のセットからクラスタを構築する。ある例では、クラスタ・エンジン２１０は、親和度*Aff(wi,wj)を有する単語のセット{wi}からクラスタＳを構築する。親和度の値*Aff(wi,wj)は、如何なる適切な種類の、例えば方向親和度DAffinity(wi,wj)又は差分親和度DiffAff(wi,wj)のような、単語wjに関する単語wiの親和度も表す。ここで提供される親和度の値の特定の例は、正規化された値と考えられてよい。この例では、Afffor(wi,wj)は前方親和度を表し、Affback(wj,wi)は後方親和度を表す。
【００５３】
この例では、クラスタＳはシード単語wqで始まる。現在の単語wxは、現行の繰り返しで、セットWからの単語と比較されているクラスタＳの単語を表す。最初に、現在の単語wxがシード単語wqに設定される。
【００５４】
繰り返しの間、現在の単語wxがクラスタＳの単語に設定される。セットWの単語wiは、当該単語の現在の単語wxとの前方親和度Afffor(wi,wx)に従い格納される。格納されたセットWの最初から開始し、親和度基準を満たす候補単語wcが識別される。親和度基準は、現在の単語wxとの前方親和度の基準を有してよい。
Afffor(wc,wx)>Thcf
また、親和度基準は、シード単語wqとの後方親和度の基準を有してよい。
Affback(wq,wc)>Thcb
ここで、Thcfは候補単語に対する前方閾値を表し、Thcbは候補単語に対する後方閾値を表す。候補単語の順序付けられたセット{wc}の第１の単語は、クラスタＳに追加される。追加された単語の数は、パラメータSizecにより与えられる。閾値Thcf及びThcbは、最小値から最大値までの範囲の如何なる適切な値を有する浮動小数点パラメータであってよい。ある例では、Thcf及びThcbの適切な値は実際の親和度のランクで順序付けられたリストから決定されてよい。例えば、リスト内の２００番目の値が用いられてよい。パラメータSizecは、如何なる適切な値を有する整数パラメータであってもよい。適切な値の例は、初期値１、２、３、又は４を含む。ある実施例では、パラメータは特定の繰り返しで変化してよい。
【００５５】
如何なる適切な数の繰り返しが実行されてもよい。ある例では、繰り返しの数は当該方法の繰り返しの前に指定されてよい。別の例では、当該数は当該方法の動作中に計算されてよい。例えば、当該数はクラスタＳの大きさの増大レートから計算されてよい。
【００５６】
別の実施例では、クラスタ・エンジン２１０は単語のセットの単語をクラスタにソートすることによりクラスタを識別する。ある例では、セットWの単語{wi}は、差分又は方向親和度のような親和度*Aff(wi,wj)に従い格納される。別の例では、単語{wi}は、和のような、単語wiの単語の別のセットQの各メンバに対する親和度の統計機能に従い格納される。セットWは、如何なる適切な方法で選択されてもよい。例えば、セットWは、クエリに最も関連するＸ単語であってよい。ここでＸは如何なる適切な値、例えば１０乃至１００、１００乃至２００、又は２００、又は更に大きい数であってよい。
【００５７】
この例では、クラスタは最初は空である。セットWからの最初の単語wiはクラスタ内に置かれる。各繰り返しで、現在の単語wxはセットWから選択される。*Aff(wx,wf)が閾親和度Thにより与えられる親和度基準を満たす場合、現在の単語wxは、クラスタ内に置かれる。ここで、wfはクラスタ内に置かれた最初の単語を表す。閾値Thは如何なる適切な値、例えば最小値０．０及び最大値１．０に対し０．１乃至０．５の範囲の値を有してよい。*Aff(wx,wf)が閾値Thを満たさない場合、現在の単語wxは空のクラスタ内に置かれる。セットWの各単語に対し繰り返しが行われる。
【００５８】
セットWの単語を処理した後、小さいクラスタは削除されてよい。例えば、Ｙ個より少ない単語を有するクラスタが削除されてよい。Ｙは如何なる適切な値、例えば３乃至５、５乃至１０、１０乃至２５、２５乃至５０の範囲の値、又は５０、又は更に大きい値であってよい。
【００５９】
クラスタ数が満足のいく範囲内にない場合、処理は、クラスタ内の配置に対しより厳格な又はより緩い基準をもたらす閾値Thの別の値で繰り返されてよい。如何なる適切な値を有するクラスタ数の最小値及びクラスタ数の最大値により、満足のいく範囲が与えられてよい。適切な値の例には、１乃至５、５乃至１０の範囲の値、又は１０、又は最小値より大きい値、及び１０乃至１５、１５乃至２０の範囲の値、又は２０、又は最大値より大きい値がある。閾値Thは、クラスタ数を増大するために増大されてよく、またクラスタ数を減少させるために減少されてよい。
【００６０】
別の実施例では、クラスタ・エンジン２１０は単語の親和度ベクトルを比較することによりクラスタを識別する。ある実施例では、親和度行列の行及び列は、親和度ベクトル<wi,*Aff(wi,w１),…,*Aff(wi,wj),…,*Aff(wi,wn)>を生成する。親和度ベクトルは単語wj,j=１,…,nに関する単語wiの親和度を表す。親和度の値*Aff(wi,wj)は、如何なる適切な種類の、例えば方向親和度又は差分親和度のような、単語wjに関する単語wiの親和度も表す。
【００６１】
ある実施例では、同一の親和度値を有する親和度ベクトルは、１つのクラスタを示す。説明を目的として、親和度ベクトルは、親和度空間における、単語の親和度の座標として考えられてよい。つまり、各親和度値*Aff(wi,wj)は、特定の次元の座標として考えられてよい。同一の親和度値を有する親和度ベクトルは、ベクトルが関連付けられている単語が親和度空間において互いに近いことを示す。つまり、ベクトルは、単語が他の単語と同一の親和度関係を有し、従って同一のクラスタ内のメンバとして適していることを示す。
【００６２】
ある親和度ベクトルが適切な距離関数により定められた他の親和度ベクトルの近傍にある場合、親和度ベクトルは同一であってよい。距離関数は、親和度ベクトルに対して、例えば所与の大きさのベクトルの標準的なユークリッド距離として、又は所与の大きさのベクトルの余弦として定められてよい。距離関数は、クラスタ・エンジン２１０又はユーザーにより指定されてよい。
【００６３】
ある実施例では、クラスタ・エンジン２１０は、クラスタ・アルゴリズムを用い、互いに近い値を有する親和度ベクトルを識別する。クラスタ・アルゴリズムの例には、直接、反復二分法、凝集、バイアス凝集、及び／又は他の適切なアルゴリズムがある。ある例では、クラスタ・エンジン２１０は、ＣＬＵＴＯのようなクラスタ・ソフトウェアを有してよい。
【００６４】
クラスタ分析器２１４は、如何なる適切な用途の分析にも親和度クラスタリングを用いてよい。ある実施例では、クラスタ分析器２１４は、親和度クラスタリングを用いページ５０を分類してよい。分類は、クラスタ識別子又は１若しくは複数のクラスタと関連付けられてよい。ある実施例では、ページ５０のクラスタが識別され、次にページ５０は当該クラスタに従い分類されてよい。別の例では、ページ５０の重要な単語が選択され、次に当該単語を含むクラスタが発見されてよい。ページ５０は次に、発見されたクラスタに従い分類されてよい。
【００６５】
ある実施例では、クラスタ分析器２１４は、親和度クラスタリングを用いページ５０のコーパスを分析してよい。コーパスは、特定の主題、１又は複数の個人のコミュニティ、組織、又は他のエンティティと関連付けられてよい。ある例では、クラスタ分析器２１４は、コーパスのクラスタを識別し、クラスタからコーパスのコーパス特性を決定してよい。コーパス特性は、コーパスに関連付けられたエンティティに関連する単語を含んでよい。１又は複数のページ５０が当該コーパス特性のクラスタを有する場合、ページ５０はエンティティに関連している。
【００６６】
ある実施例では、クラスタ分析器２１４は、親和度クラスタリングを用い、検索クエリの曖昧さの除去及び拡張を行ってよい。この実施例では、クラスタ分析器２１４は、所与の検索クエリの検索語を含むクラスタを識別する。クラスタは、別の単語、及び／又は所与の検索クエリと関連する分類を提供する。ある例では、クラスタからの単語は検索者に報告され、次の検索クエリで検索者を助けてよい。別の例では、クラスタ分析器２１４は、クラスタから単語を選択し、自動的に１又は複数の新たな検索クエリを形成してよい。クラスタ分析器２１４は、直列に又は並列に新たなクエリを実行してよい。
【００６７】
ある実施例では、クラスタ分析器２１４は、親和度クラスタリングを用い社会的ネットワークを調査してよい。ある例では、ページ５０は社会的ネットワークを理解する上での手掛かりとなりうる。このようなページの例には、書簡（例えば、手紙、電子メール、及びインスタント・メッセージ）、覚え書き、記事、及び議事録がある。これらのページ５０は、社会的ネットワークの人々の識別子（例えば、名前）を有する単語を有してよい。名前のクラスタは、当該ネットワークの人々の間の関係を分析するために識別されてよい。ある例では、差分親和度クラスタリングが用いられ、システム管理者の名前のような情報を提供せずに大部分のページ５０に現れる名前をフィルターしてよい。
【００６８】
特定の実施例では、クラスタ・モジュール２１４は、データ・セットのクラスタを結合及び／又は比較することにより、データ・セットを分析してよい。ある実施例では、重複するデータ・セットのクラスタが比較される。あるデータ・セットからのクラスタは、他のデータ・セットのクラスタに割り付けられてよい。これにより、データ・セット間の関係を理解する上での手掛かりが提供されてよい。例えば、データ・セットは、同僚のグループの文書の分析から、及びグループの社会的ネットワークの調査からであってもよい。社会的ネットワークのクラスタは、社会的ネットワークと主題との間の関係を分析するために、文書主題クラスタに割り付けられてよい。
【００６９】
本発明の特定の実施例は、１又は複数の技術的利点を提供し得る。ある実施例の技術的利点は、単語のクラスタが単語間の親和度から識別されることである。クラスタは、互いに十分に親和性のある単語を含む。ここで、十分な親和性があるとは、１又は複数の親和度基準に従い決定される。ある実施例の別の技術的利点は、クラスタ分析が実行されることである。クラスタ分析の例は、ページのクラスタに従いページを分類する段階、コーパスのクラスタからコーパス特性を決定する段階、及びユーザーの文書内のクラスタに基づきユーザーを分析する段階、を有する。本発明の特定の実施例は、上述の技術的利点の何れも有さないか、又はいくつか若しくは全てを有して良い。１又は複数の他の技術的利点は、以下の図、記載、及び請求項から当業者に直ちに明らかである。
【００７０】
本開示は特定の実施例の観点から記載されたが、これら実施例の変更及び置換は当業者に明らかであろう。従って、実施例の上述の記載は、本開示を制限するものではない。他の変化、代替、及び変更も特許請求の範囲に定められたように本開示の精神及び範囲から逸脱することなく可能である。
［関連出願］
本出願は、Ｕ．Ｓ．Ｃ§１１９（ｅ）３５に基づき、米国仮出願番号６０／９７７８１１、発明の名称「WORD  CLUSTERING  BASED  ON  AFFINITY」、代理人管理番号０７３３３８．０５５０、出願日２００７年１０月５日、発明者David(nmi)Marvit他の権利を主張する。
【００７１】
以上の実施形態に関し、更に以下の付記を開示する。
（付記１）  方法であって、
レコードは第１の単語と第２の単語との間の定量的関係を記述する前記第１の単語と前記第２の単語との間の複数の親和度を記録し、１又は複数の有形記憶媒体に格納された前記レコードにアクセスする段階、
第１の単語と第２の単語との間の親和度が１又は複数の親和度基準を満たす場合に前記第１の単語は前記第２の単語と十分に親和性があり、１つのクラスタは互いに十分に親和性のある１又は複数の単語を有し、複数の親和度に従い前記複数の単語の複数のクラスタを識別する段階、
前記クラスタを用いクラスタ分析を実行し結果を生成する段階、及び
前記クラスタ分析の結果を報告する段階、を有する方法。
（付記２）  前記親和度は、基本親和度、方向親和度、及び差分親和度を有するセットから選択された親和度を更に有する、付記１記載の方法。
（付記３）  前記複数の親和度に従い前記複数の単語の複数のクラスタを識別する段階は、クラスタを構築する段階を更に有し、前記クラスタの構築は、
前記クラスタ内にシード単語を配置する段階、並びに
前記クラスタに追加された単語のそれぞれに対し、
−各単語と現在の単語との間の前方親和度に従い前記複数の単語をソートする段階、
−前記１又は複数の親和度基準は、前記現在の単語との前方親和度基準と前記シード単語との後方親和度基準とを有し、前記１又は複数の親和度基準を満たす１又は複数の候補単語を識別する段階、及び
−前記１又は複数の候補単語を前記クラスタ内に配置する段階、を繰り返す段階、により行われる、付記１記載の方法。
（付記４）  前記複数の親和度に従い前記複数の単語の複数のクラスタを識別する段階は、前記単語を前記クラスタにソートする段階を更に有し、前記ソートは、前記複数の単語のそれぞれに対し、
前記単語のそれぞれとクラスタの第１の単語との間の親和度が閾親和度を満たしている場合に、前記単語のそれぞれを前記クラスタ内に配置する段階、及び
その他の場合に、前記単語のそれぞれを空のクラスタに配置する段階、を繰り返すことにより行われる、付記１記載の方法。
（付記５）  前記複数の親和度に従い前記複数の単語の複数のクラスタを識別する段階は、前記単語の複数の親和度ベクトルを比較する段階を更に有し、前記比較は、
親和度ベクトルは単語と関連付けられ複数の親和度値を有し、親和度値は前記関連付けられた単語と別の単語との間の親和度を示し、前記親和度値を記録する前記複数の親和度ベクトルを求める段階、
互いに近い親和度ベクトルのセットを識別する段階、及び
クラスタ内に前記親和度ベクトルのセットと関連付けられた単語を配置する段階、により行われる、付記１記載の方法。
（付記６）  前記クラスタを用いクラスタ分析を実行し結果を生成する段階は、前記クラスタに従い前記複数の単語を有するページを分類する段階、を更に有する、付記１記載の方法。
（付記７）  前記クラスタを用いクラスタ分析を実行し結果を生成する段階は、前記クラスタに従い前記複数の単語を有するページを分類する段階、を更に有し、前記分類は、
前記ページの１又は複数の重要な単語を選択する段階、
前記１又は複数の重要な単語を有する前記複数のクラスタのうち１又は複数のクラスタを決定する段階、及び
前記１又は複数のクラスタに従い前記ページを分類する段階、により行われる、付記１記載の方法。
（付記８）  前記クラスタを用いクラスタ分析を実行し結果を生成する段階は、前記クラスタに従い前記複数の単語を有するコーパスのコーパス特性を決定する段階、を更に有する、付記１記載の方法。
（付記９）  前記クラスタを用いクラスタ分析を実行し結果を生成する段階は、
所与の検索クエリの１又は複数の検索語を有する複数のクラスタのうちの１又は複数のクラスタを決定する段階、
前記１又は複数のクラスタから１又は複数の単語を選択する段階、及び
前記選択された１又は複数の単語を報告する段階、を有する、付記１記載の方法。
（付記１０）  前記クラスタを用いクラスタ分析を実行し結果を生成する段階は、
所与の検索クエリの１又は複数の検索語を有する複数のクラスタのうちの１又は複数のクラスタを決定する段階、
前記１又は複数のクラスタから１又は複数の単語を選択する段階、及び
前記選択された１又は複数の単語から１又は複数の次の検索クエリを生成する段階、を有する、付記１記載の方法。
（付記１１）  前記クラスタを用いクラスタ分析を実行し結果を生成する段階は、それぞれの人がユーザー識別子と関連付けられた人々の社会的ネットワークを分析する段階を更に有し、前記単語は前記ユーザー識別子を有し、
前記分析は、前記クラスタに従い前記人々の間の１又は複数の関係を決定する段階により行われる、付記１記載の方法。
（付記１２）  前記１又は複数の有形記憶媒体に格納された前記レコードにアクセスする段階は、複数の単語を有する複数のデータ・セットから生成された親和度値にアクセスする段階、を更に有し、
前記複数の親和度に従い前記複数の単語の複数のクラスタを識別する段階は、データ・セット毎にクラスタ・セットを識別する段階、を更に有し、
前記クラスタを用いクラスタ分析を実行し結果を生成する段階は、第１のデータ・セットの第１のクラスタ・セットを、第２のデータ・セットの第２のクラスタ・セットと比較し、前記第１のデータ・セットと前記第２のデータ・セットとの間の関係を分析する段階、を更に有する、付記１記載の方法。
（付記１３）  １又は複数のコンピューター可読有形媒体であって、符号化されたソフトウェアを有し、前記ソフトウェアは実行されると、
記録は第１の単語と第２の単語との間の定量的関係を記述する前記第１の単語と前記第２の単語との間の複数の親和度を記録するレコードにアクセスする段階、
第１の単語と第２の単語との間の親和度が１又は複数の親和度基準を満たす場合に前記第１の単語は前記第２の単語と十分に親和性があり、１つのクラスタは互いに十分に親和性のある１又は複数の単語を有し、複数の親和度に従い前記複数の単語の複数のクラスタを識別する段階、
前記クラスタを用いクラスタ分析を実行し結果を生成する段階、及び
前記クラスタ分析の結果を報告する段階、を実行する、コンピューター可読有形媒体。
（付記１４）  前記親和度は、基本親和度、方向親和度、及び差分親和度を有するセットから選択された親和度を更に有する、付記１３記載のコンピューター可読有形媒体。
（付記１５）  前記ソフトウェアは、クラスタを構築することにより、前記複数の親和度に従い前記複数の単語の複数のクラスタを識別し、前記構築は、
前記クラスタ内にシード単語を配置する段階、並びに
前記クラスタに追加された単語毎に、
−各単語と現在の単語との間の前方親和度に従い前記複数の単語をソートする段階、
−前記１又は複数の親和度基準は、前記現在の単語との前方親和度基準と前記シード単語との後方親和度基準とを有し、前記１又は複数の親和度基準を満たす１又は複数の候補単語を識別する段階、及び
−前記１又は複数の候補単語を前記クラスタ内に配置する段階、を繰り返す段階、により行われる、付記１３記載のコンピューター可読有形媒体。
（付記１６）  前記ソフトウェアは、クラスタに単語をソートすることにより、複数の親和度に従い複数の単語の複数のクラスタを更に識別し、前記識別は、前記複数の単語のそれぞれに対し、
前記単語のそれぞれとクラスタの第１の単語との間の親和度が閾親和度を満たしている場合に、前記単語のそれぞれを前記クラスタ内に配置する段階、及び
その他の場合に、前記単語のそれぞれを空のクラスタに配置する段階、を繰り返すことにより行われる、付記１３記載のコンピューター可読有形媒体。
（付記１７）  前記ソフトウェアは、前記単語の複数の親和度ベクトルを比較することにより、前記複数の親和度に従い前記複数の単語の前記複数のクラスタを更に識別し、前記比較は、
親和度ベクトルは単語と関連付けられ複数の親和度値を有し、親和度値は前記関連付けられた単語と別の単語との間の親和度を示し、前記親和度値を記録する前記複数の親和度ベクトルを求める段階、
互いに近い親和度ベクトルのセットを識別する段階、及び
クラスタ内に前記親和度ベクトルのセットと関連付けられた単語を配置する段階、により行われる、付記１３記載のコンピューター可読有形媒体。
（付記１８）  前記ソフトウェアは、前記クラスタに従い前記複数の単語を有するページを分類することにより、前記クラスタを用いクラスタ分析を実行し結果を更に生成する、付記１３記載のコンピューター可読有形媒体。
（付記１９）  前記ソフトウェアは、前記クラスタに従いページを分類することにより、前記クラスタを用いクラスタ分析を実行し結果を生成し、
前記分類は、
前記ページの１又は複数の重要な単語を選択する段階、
前記１又は複数の重要な単語を有する前記複数のクラスタのうち１又は複数のクラスタを決定する段階、及び
前記１又は複数のクラスタに従い前記ページを分類する段階、により行われる、付記１３記載のコンピューター可読有形媒体。
（付記２０）  前記ソフトウェアは、前記クラスタに従い前記複数の単語を有するコーパスのコーパス特性を決定することにより、前記クラスタを用いクラスタ分析を実行し結果を更に生成する、付記１３記載のコンピューター可読有形媒体。
（付記２１）  前記ソフトウェアは、前記クラスタを用いクラスタ分析を実行し結果を生成し、
前記クラスタ分析は、
所与の検索クエリの１又は複数の検索語を有する複数のクラスタのうちの１又は複数のクラスタを決定する段階、
前記１又は複数のクラスタから１又は複数の単語を選択する段階、及び
前記選択された１又は複数の単語を報告する段階、により行われる、付記１３記載のコンピューター可読有形媒体。
（付記２２）  前記ソフトウェアは、前記クラスタを用いクラスタ分析を実行し結果を生成し、
前記クラスタ分析は、
所与の検索クエリの１又は複数の検索語を有する複数のクラスタのうちの１又は複数のクラスタを決定する段階、
前記１又は複数のクラスタから１又は複数の単語を選択する段階、及び
前記選択された１又は複数の単語から１又は複数の次の検索クエリを生成する段階、により行われる、付記１３記載のコンピューター可読有形媒体。
（付記２３）  前記ソフトウェアは、それぞれの人がユーザー識別子と関連付けられた人々の社会的ネットワークを分析することにより、前記クラスタを用いクラスタ分析を実行し結果を生成し、前記単語は前記ユーザー識別子を有し、
前記社会的ネットワークは、
前記クラスタに従い前記人々の間の１３又は複数の関係を決定することにより分析される、付記１３記載のコンピューター可読有形媒体。
（付記２４）  前記ソフトウェアは、
複数の単語を有する複数のデータ・セットから生成された親和度値にアクセスすることにより、前記１又は複数の有形記憶媒体に格納された前記レコードにアクセスし、
データ・セット毎にクラスタ・セットを識別することにより、前記複数の親和度に従い前記複数の単語の複数のクラスタを識別し、
第１のデータ・セットの第１のクラスタ・セットを、第２のデータ・セットの第２のクラスタ・セットと比較し、前記第１のデータ・セットと前記第２のデータ・セットとの間の関係を分析することにより、前記クラスタを用いクラスタ分析を実行し結果を生成する、付記１３記載のコンピューター可読有形媒体。
（付記２５）  システムであって、
記録は第１の単語と第２の単語との間の定量的関係を記述する前記第１の単語と前記第２の単語との間の複数の親和度を記録し、１又は複数の有形記憶媒体に格納された前記レコードにアクセスする手段、
第１の単語と第２の単語との間の親和度が１又は複数の親和度基準を満たす場合に前記第１の単語は前記第２の単語と十分に親和性があり、１つのクラスタは互いに十分に親和性のある１又は複数の単語を有し、複数の親和度に従い前記複数の単語の複数のクラスタを識別する手段、
前記クラスタを用いクラスタ分析を実行し結果を生成する手段、及び
前記クラスタ分析の結果を報告する手段、を有するシステム。
【図面の簡単な説明】
【００７２】
【図１】言語の単語間の親和度から言語のオントロジーを生成するシステムのある実施例を示す。
【図２】図１のシステムと共に用いられ得る親和度モジュールのある実施例を示す。
【図３】基本親和度を記録する親和度行列の例を示す。
【図４】方向親和度を記録する親和度行列の例を示す。
【図５】平均親和度を記録する親和度行列の例を示す。
【図６】親和度グラフの例を示す。
【図７】図１のシステムと共に用いられ得るクラスタ・モジュールのある実施例を示す。
【符号の説明】
【００７３】
２０  クライアント
２２  サーバー
２４  メモリー
３０  親和度モジュール
３０  親和度モジュール
３１  クラスタ・モジュール
３１  クラスタ・モジュール
３４  親和度計算機
３８  オントロジー生成器
４２  親和度行列生成器
４６  親和度グラフ生成器
４８  単語推奨器
５０  記録
５８  インデックス
６２  転置インデックス
６６  オントロジー
６７  クラスタ
２１０  クラスタ・エンジン
２１４  クラスタ分析器
【図１】
0005531395.tif 000003
【図２】
0005531395.tif 000004
【図３】
0005531395.tif 000005
【図４】
0005531395.tif 000006
【図５】
0005531395.tif 000007
【図６】
0005531395.tif 000008
【図７】
0005531395.tif 000009