JP5147162B2 - オブジェクトの類似性を異種の関係に基づいて判定するための方法およびシステム - Google Patents

Description

記載の技術は一般に、オブジェクトの類似性を判定することに関し、より詳細には、類似性をオブジェクト関係に基づいて判定することに関する。

ＧｏｏｇｌｅやＯｖｅｒｔｕｒｅなど多くの検索エンジンサービスでは、インターネットを介してアクセス可能な情報を検索することができる。これらの検索エンジンサービスにより、ユーザは、ウェブページなど、ユーザに関心のあるかもしれない表示ページを検索することができる。ユーザが検索語を含む検索要求（「クエリ」とも呼ばれる）をサブミットした後、検索エンジンサービスは、これらの検索語に関係する可能性のあるウェブページを識別する。関係するウェブページを素早く識別するために、検索エンジンサービスは、ウェブページに対するキーワードのマッピングを維持管理することがある。検索エンジンサービスは、ウェブ（すなわちワールドワイドウェブ）を「クロール」して各ウェブページのキーワードを抽出することによって、このマッピングを生成することができる。ウェブをクロールするために、検索エンジンサービスは、ルートウェブページのリストを使用することができ、これらのルートウェブページを介してアクセス可能なすべてのウェブページを識別することができる。任意の特定のウェブページのキーワードは、見出しの単語、ウェブページのメタデータ中で供給される単語、強調表示されている単語等を識別するなど、様々な周知の情報検索技法を使用して抽出することができる。検索エンジンサービスは、各ウェブページが検索要求にどのくらい関連するかを示す関連性スコアを、各マッチの近さやウェブページの人気（例えばＧｏｏｇｌｅのページランク）などに基づいて計算することができる。次いで検索エンジンサービスは、これらのウェブページへのリンクを、その関連性に基づく順序でユーザに対して表示する。検索エンジンは、より一般的に、任意の文書の集まりの中で情報検索を提供することもできる。例えば、文書の集まりには、すべての米国特許、すべての連邦裁判所見解、会社のすべてのアーカイブされた文書などが含まれ得るであろう。

検索エンジンサービスは、ウェブページやクエリなど様々なオブジェクト間の類似性を測定する必要がある場合がある。例えば、検索エンジンサービスは対話式クエリ拡張を可能にする場合があるが、これはクエリ語と他の語との間での類似性計算を必要とする。別の例として、検索エンジンサービスは、ユーザがウェブページをナビゲートするのを補助するために、ウェブページを類似ウェブページのクラスタにグループ化したい場合がある。オブジェクトの類似性を判定するための典型的なアルゴリズムは、一般に、オブジェクトに関係する特徴ベクトルを使用し、次いで特徴ベクトル間の距離を類似性の指示として計算する。例えば、ウェブページは、類似性の計算に使用されるキーワードや内容などを含む特徴を有することがある。ほとんどのアルゴリズムは、類似性を判定するとき、オブジェクトに関連する特徴だけに依拠する。例えば、ウェブページ間の類似性は、ウェブページの内容だけに基づくものとすることができる。しかし、いくつかのアルゴリズムは、異種のオブジェクトに基づく特徴を計算に入れる。例えば、あるアルゴリズムはクリックスルーデータを使用し、クエリが同じ語を含む場合、またはクエリによってユーザが同じウェブページを選択することになる場合、これらのクエリは類似する。したがって、このようなクエリの特徴ベクトルは、ユーザによって選択されたクエリ結果のウェブページに関する情報を含むことになろう。

しかし、これらの技法は、あるタイプのオブジェクト間の類似性を計算するとき、関係する可能性のある別のタイプのオブジェクト間の類似性を考慮に入れることができない。すなわち、あるタイプのオブジェクトの類似性測定値は、別のタイプのオブジェクトの類似性測定値に関係する場合がある。例えば、あるクエリは、ユーザが選択またはクリックスルーする結果のウェブページ間の類似性に部分的に基づいて、別のクエリと類似する場合がある。逆に、ウェブページは、これらのウェブページをクエリの結果中で返すクエリ間の類似性に部分的に基づいて、別のウェブページと類似する場合がある。異種のオブジェクト間の関係を計算に入れた、オブジェクトの類似性を測定する技法を有することが望ましいであろう。

同じタイプおよび異なるタイプのオブジェクトとの関係、ならびにこれらのオブジェクトの別のオブジェクトに対する類似性に基づいて、オブジェクトの類似性を測定するための方法およびシステムが提供される。一実施形態では、類似性システムは、各オブジェクトタイプについて、タイプ内およびタイプ間の類似性関数を定義する。類似性システムは、あるタイプについてのタイプ内およびタイプ間の類似性関数を組み合わせて、そのタイプについての全体的な類似性関数とすることができる。類似性関数を定義した後、類似性システムは、オブジェクトの属性値を収集する。属性値は、同じタイプのオブジェクト間の関係データ（タイプ内関係と呼ばれる）、および異なるタイプのオブジェクト間の関係（タイプ間関係と呼ばれる）を含むことができる。オブジェクトの属性値を収集した後、類似性システムは、類似性が解に収束するまで反復的にオブジェクトの類似性を計算することによって、タイプ内およびタイプ間の類似性関数を解く。

同じタイプおよび異なるタイプのオブジェクトとの関係、ならびにこれらのオブジェクトの別のオブジェクトに対する類似性に基づいて、オブジェクトの類似性を測定するための方法およびシステムが提供される。一実施形態では、類似性システムは、各オブジェクトタイプについて、タイプ内およびタイプ間の類似性関数を定義する。タイプ内類似性関数は、同じタイプのオブジェクト間の類似性を測定する。例えば、クエリ間のタイプ内類似性関数は、クエリをサブミットするユーザの属性に基づいてクエリの検索語がどのくらい近くマッチするかに基づくことができる。オブジェクト間のタイプ内類似性はまた、同じタイプの他のオブジェクトの類似性に依存することもできる。例えば、２つのクエリがそれぞれ第３のクエリに対して高い類似性を有する場合、２つのクエリは、より相互に類似する場合がある。このような、他のオブジェクトとの類似性に基づくオブジェクト間のタイプ内類似性は、再帰関数を定義する。タイプ間類似性関数は、類似性を含む別のタイプのオブジェクトの属性に基づいて、あるタイプの２つのオブジェクト間の類似性を測定する。例えば、ユーザがクリックスルーするあるクエリの結果のウェブページが、ユーザがクリックスルーする別のクエリの結果のウェブページと類似する場合、２つのクエリはより類似する可能性がある。別のタイプのオブジェクトの類似性もまた、あるタイプのオブジェクトとの類似性に依存することがある。さらに、あるタイプのオブジェクトの類似性が別のタイプのオブジェクトの類似性に依存することがあり、またその逆もあるので、タイプ間類似性関数は、様々なタイプ間で再帰的である。

オブジェクトのタイプは、そのタイプのオブジェクトに対し、オブジェクトの種々の属性に基づいて定義された様々な類似性定義を有することができる。例えば、ウェブページは、ウェブページの内容に基づくタイプ内類似性と、ウェブページ間のリンクに基づく別のタイプ内類似性とを有することができる。類似性システムは、あるタイプについてのタイプ内およびタイプ間の類似性関数を組み合わせて、そのタイプについての全体的な類似性関数とすることができる。一実施形態では、類似性システムは、線形式によってタイプ内およびタイプ間の類似性関数を組み合わせ、タイプ内とタイプ間の類似性関数それぞれには、そのタイプのオブジェクト間の全体的な類似性を表す際に、その知覚された精度に基づいて重みが適用される。例えば、高い精度のタイプ内類似性関数には高い重みを与え、低い精度のタイプ内類似性関数には低い重みを与えることができる。

類似性関数を定義した後、類似性システムは、オブジェクトの属性値を収集する。属性値は、同じタイプのオブジェクト間の関係データ（タイプ内関係と呼ばれる）、および異なるタイプのオブジェクト間の関係（タイプ間関係と呼ばれる）を含むことができる。例えば、ウェブページは、ウェブページのキーワードに対応する非関係ベースの属性値を有することができる。ウェブページはまた、ウェブページ間の入リンクおよび出リンクに基づくタイプ内関係を有することもできる。ウェブページは、クエリ結果からウェブページへのクリックスルーに基づく、クエリとのタイプ間関係を有することもできる。

オブジェクトの属性値を収集した後、類似性システムは、類似性が解に収束するまで反復的にオブジェクトの類似性を計算することによって、タイプ内およびタイプ間の類似性関数を解く。類似性関数の再帰的な性質のため、類似性システムは反復的アプローチを用いる。類似性システムは、類似性が初期化された状態で開始し、次いで、初期類似性に基づいて各オブジェクトタイプについて類似性関数を計算して、新しい類似性を出す。類似性システムは、新しい類似性と古い類似性との差を測定して、類似性が解に収束したかどうかを判定する。収束した場合は、この新しい類似性が解を表す。収束していない場合は、新しい類似性は古い類似性になり、類似性システムは処理を繰り返す。このように類似性システムは、あるタイプのオブジェクトの類似性を、別のタイプのオブジェクトの類似性に基づいて、また様々なタイプのオブジェクト間の関係に基づいて計算する。

以下、検索エンジンのコンテキストにおける類似性システムの処理の例を提供する。類似性システムは、検索エンジンによって使用されるオブジェクト（例えばウェブページやクエリ）および関係（例えば入リンクやクリックスルー）を、有向グラフＧ＝（Ｖ，Ｅ）としてモデル化し、ノードＶは検索エンジンのオブジェクトを表し、エッジＥはオブジェクト間の関係を表す。ノードＶは、２つの部分集合Ｑ＝｛ｑ¹，ｑ²，．．．，ｑ^m｝とＰ＝｛ｐ¹，ｐ²，．．．，ｐⁿ｝とに分割することができ、Ｑはクエリを表し、Ｐはウェブページを表す。これらのウェブページおよびクエリの間の関係は、入リンク関係（ＩＬ）、出リンク関係（ＯＬ）、クリックスルー関係（ＣＴ）を含むことができる。グラフ中のノードｖについて、Ｍ_R（ｖ）は、ノードｖと関係Ｒを有する隣接ノードの集合を表す。例えば、Ｍ_IL（ｖ）は、ウェブページｖへの入リンクのソースであるウェブページの集合を表す。

は、集合中のｉ番目のウェブページを示す。類似性システムは、類似性行列Ｓを使用してオブジェクト間の類似性を表し、Ｓ［ａ，ｂ］は、オブジェクトａとｂとの類似性を表す。

類似性システムは、あるタイプのオブジェクト同士が、別のタイプの相互に関連のあるオブジェクトの類似性に部分的に基づいて類似するという原理に基づいている。あるタイプの２つのオブジェクトが別のタイプの同じ１つのオブジェクトとの関係を有する場合、２つのオブジェクトはある程度類似する。また、同じタイプの２つのオブジェクトが、別のタイプの、異なるが類似する２つのオブジェクトとの関係を有する場合も、２つのオブジェクトはある程度類似する。類似性システムは、この原理を以下の式で表す。

上式で、

は、タイプＯ₁のオブジェクトａとｂとの類似性を表す。

は、別のタイプのオブジェクトｉとｊとの間の類似性を表す。Ｒは、類似性が基づくタイプ間関係を表し、Ｃは重み係数である。ａがｂと等しい場合、

は１になるように定義される。すなわち、オブジェクトとそれ自体との類似性は、最大類似性１を定義する。ａとｂが両方ともＯ₂中の同じオブジェクトＡに関係する場合、

は１であり、これは

への最大寄与をもたらす。ａとｂのどちらかが近隣を有さない場合、すなわちＯ₂中のオブジェクトとの関係を有さない場合は、｜Ｍ_R（ａ）｜または｜Ｍ_R（ｂ）｜は０に等しくなるであろう。このような場合、類似性システムは、

を０に設定し、０による除算を防ぐ。例として、Ｏ₁がオブジェクトａおよびｂを含み、Ｏ₂がオブジェクトＡ、Ｂ、Ｃを含み、ａがＡおよびＢに関係し、ｂがＢおよびＣに関係すると仮定する。

が０．７、

が０．７、

が０．４９であり、重み係数が０．７である場合、式１を適用することにより、

は０．５である（例えば０．７／４＊（０．７＋０．４９＋１．０＋０．７））。

類似性システムは、タイプ内類似性関数とタイプ間類似性関数から得られる類似性の組み合わせに基づいて、あるタイプのオブジェクトの全体的な類似性を定義する。一実施形態では、類似性システムは、以下の式で表されるように、タイプ内類似性関数およびタイプ間類似性関数の類似性の一次結合を使用する。

上式で、Ｓ_intraおよびＳ_interは、タイプ内類似性関数およびタイプ間類似性関数から得られる類似性を表し、αおよびβは類似性に対する重みであり、α＋β＝１である。αおよびβに様々な値を割り当てることにより、類似性システムは、全体的な類似性に対する様々な類似性関数の寄与を調整することができる。前述のように、あるオブジェクトの類似性を別のオブジェクトの類似性に基づいて定義することができ、別のオブジェクトの類似性はあるオブジェクトの類似性に基づいて定義することができるので、式２は再帰的に定義することができる。一実施形態では、類似性システムは、類似性が収束する（すなわち‖Ｓⁱ−Ｓ^i-1‖＜ε（εは差分しきい値））まで類似性を計算することによって、類似性関数を反復的に解く。

検索エンジンのコンテキストでは、類似性システムは、クエリの内容だけを使用してタイプ内類似性関数を定義することができる。内容に基づくタイプ内類似性関数は、以下の式で定義することができる。

上式で、ａおよびｂはクエリであり、Ｓ_QCは、内容に基づく、クエリの内容類似性行列である。例として、クエリａおよびｂが２つの検索語（またはキーワード）を有し、一方のキーワードが共通であるとき、これらの類似性値は０．３３（すなわち１／３）になる。類似性システムは、以下の式により、ウェブページとのクリックスルー関係に基づく、クエリについてのタイプ間類似性関数を定義することができる。

上式で、Ｓ_QCTは、クリックスルーに基づく、クエリの類似性行列を表す。Ｓ_PCTは、クリックスルーに基づく、ウェブページの類似性行列を表す。Ｍ_CT（ａ）は、クエリログから識別される、クエリａからウェブページへのクリックスルーを表す。Ｃ_CTは重み係数である。類似性システムは、式（３）と（４）を組み合わせて、クエリについての全体的な類似性関数とする。これは以下の式で表される。

上式で、Ｓ_Qは、クエリの全体的な類似性行列を表す。

類似性システムは、入リンクおよび出リンクのタイプ内関係、ならびにウェブページへのクリックスルーをもたらすクエリとのタイプ間関係に基づいて、ウェブページの類似性を表す。類似性システムは、２つのウェブページが同じウェブページ（または類似するウェブページ）からリンクされているときに２つのウェブページが類似する可能性があることを反映するように、入リンク関係に基づくタイプ内類似性関数を定義する。類似性システムはまた、２つのウェブページが同じウェブページ（または類似するウェブページ）にリンクしているときに２つのウェブページが類似する可能性があることを反映するように、出リンク関係に基づくタイプ間類似性関数を定義する。類似性システムは、以下の式により、出リンクおよび入リンクの関係に基づく、ウェブページについてのタイプ内類似性関数を表す。

上式で、ＡおよびＢはウェブページを表し、Ｃ_OLおよびＣ_ILは重み係数を表す。Ｓ_OLおよびＳ_ILは、出リンクおよび入リンクに基づく類似性行列である。Ｍ_OL（Ａ）は、ウェブページＡからの出リンクの宛先ウェブページを表し、Ｍ_IL（Ａ）は、ウェブページＡへの入リンクのウェブページのソースを表す。類似性システムは、以下の式により、クリックスルー関係に基づく、ウェブページについてのタイプ間類似性関数を表す。

上式で、Ｍ_CT（Ａ）は、ウェブページＡにアクセスするためにユーザがクリックスルーするクエリを表す。式８は式４（すなわちＳ_QCT）で定義され、またその逆でもあるので、これらの１対の式は再帰関数を定義する。類似性システムは、ウェブページについての全体的な類似性関数を、タイプ内類似性関数およびタイプ間類似性関数の一次結合として定義し、これは以下の式で表される。

上式で、Ｓ_Pはウェブページについての類似性行列を表し、α’、β’、γ’は重みであって、α’＋β’＋γ’＝１である。

このように類似性システムは、統一されたフレームワークを使用して、異種のオブジェクトとそれらのタイプ間関係を統合する。全体的な類似性関数は再帰的なので、類似性システムは、類似性関数を同時に、そして反復的に解く。類似性関数は、上に定義したように、以下の式で表される。

式１０でわかるように、任意の２つのクエリ間におけるタイプ間類似性は、ウェブページ類似性、タイプ内とタイプ間の両方の類似性に影響される。ウェブページ間のタイプ間類似性は、タイプ内とタイプ間の両方のクエリ類似性に影響されるので、式１０は再帰的関係を定義する。したがって、ウェブページおよびクエリの類似性は、互いに拡がり、安定状態に収束する。

図１は、一実施形態における類似性システムのコンポーネントを示すブロック図である。ウェブサイト１０１が、通信リンク１０２を介して類似性システム１１０に接続されている。類似性システムは、類似性計算コンポーネント１１１、類似性関数定義コンポーネント１１２、関係確立コンポーネント１１３、類似性関数解決コンポーネント１１４を備える。類似性計算コンポーネントは、タイプ間関係と他のタイプのオブジェクトの類似性とに基づいて、オブジェクト間の類似性を計算する。類似性計算コンポーネントは、類似性関数定義コンポーネント、関係確立コンポーネント、類似性関数解決コンポーネントを呼び出す。類似性関数定義コンポーネントは、ユーザと対話して、オブジェクトのタイプと、オブジェクト間の関係と、各タイプのオブジェクトについての様々な類似性関数とを定義することができる。関係確立コンポーネントは、収集されたデータに基づいて関係データを生成する。例えば、収集データは、クエリ、クエリ結果のウェブページ、クエリログを含むことができる。類似性関数解決コンポーネントは、定義された類似性関数を反復的に計算して更新された類似性行列を生成し、類似性行列の類似性が解に収束するまで反復する。

類似性システムが実現されるコンピューティングデバイスは、中央処理装置、メモリ、入力デバイス（例えばキーボードやポインティングデバイス）、出力デバイス（例えば表示デバイス）、記憶デバイス（例えばディスクドライブ）を備えることができる。メモリおよび記憶デバイスは、類似性システムを実現する命令を含むことのできるコンピュータ可読媒体である。また、データ構造およびメッセージ構造は、通信リンク上の信号としてデータ伝送媒体を介して記憶または伝送することができる。インターネット、ローカルエリアネットワーク、ワイドエリアネットワーク、ポイントツーポイントダイヤルアップ接続など、様々な通信リンクを使用することができる。

類似性システムは、様々な動作環境で実現することができる。使用に適するであろう様々な周知のコンピューティングシステム、環境、構成には、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルドデバイスまたはラップトップデバイス、マルチプロセッサシステム、マイクロプロセッサベースのシステム、プログラム可能な民生用電子機器、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータが含まれ、また、これらのシステムまたはデバイスのいずれかを含む分散コンピューティング環境などが含まれる。

類似性システムは、プログラムモジュールなど、１つまたは複数のコンピュータまたはその他のデバイスによって実行されるコンピュータ実行可能命令の一般的なコンテキストで述べることができる。一般に、プログラムモジュールは、特定のタスクを実行するか特定の抽象データ型を実現するルーチン、プログラム、オブジェクト、コンポーネント、データ構造などを含む。通常、プログラムモジュールの機能は、様々な実施形態で望まれるように組み合わせたり、分散させたりすることができる。

図２は、一実施形態における類似性関数定義コンポーネントの処理を示す流れ図である。ブロック２０１〜２０９で、コンポーネントは、各オブジェクトタイプを選択し、そのタイプのオブジェクトについてタイプ内およびタイプ間の類似性関数を定義しながらループする。一実施形態では、コンポーネントは、ユーザと対話して、オブジェクト間のタイプ内関係およびタイプ間関係を定義することができる。コンポーネントはまた、クエリの検索語に基づく類似性など、オブジェクト間の類似性に再帰的に基づかない類似性関数を定義することもできる。ブロック２０１で、コンポーネントは、次のオブジェクトタイプを選択する。判定ブロック２０２で、すべてのオブジェクトタイプがすでに選択されている場合は、コンポーネントはリターンし、そうでない場合は、コンポーネントはブロック２０３で継続する。ブロック２０３で、コンポーネントは、選択されたタイプについて次のタイプ内関係を選択する。判定ブロック２０４で、すべてのタイプ内関係がすでに選択されている場合は、コンポーネントはブロック２０６で継続し、そうでない場合は、コンポーネントはブロック２０５で継続する。ブロック２０５で、コンポーネントは、選択されたタイプおよび関係についてタイプ内類似性関数を定義する。次いでコンポーネントは、ブロック２０３にループして次のタイプ内関係を選択する。ブロック２０６で、コンポーネントは、選択されたタイプについて次のタイプ間関係を選択する。判定ブロック２０７で、すべてのタイプ間関係がすでに選択されている場合は、コンポーネントはブロック２０９で継続し、そうでない場合は、コンポーネントはブロック２０８で継続する。ブロック２０８で、コンポーネントは、選択されたタイプおよび関係についてタイプ間類似性関数を定義する。次いでコンポーネントは、ブロック２０６にループして次のタイプ間関係を選択する。ブロック２０９で、コンポーネントは、選択されたタイプについて定義されたタイプ内類似性関数およびタイプ間類似性関数を組み合わせることによって、全体的な類似性関数を定義する。コンポーネントは、組み合わされた類似性関数のそれぞれに重み係数を適用することができる。コンポーネントは、ブロック２０１にループして次のオブジェクトタイプを選択する。

図３は、一実施形態における関係確立コンポーネントの処理を示す流れ図である。コンポーネントは、収集されたデータを処理し、関係データを生成する。ブロック３０１〜３０８で、コンポーネントは、各オブジェクトタイプを選択し、そのオブジェクトタイプについて関係データを生成しながらループする。ブロック３０１で、コンポーネントは、次のオブジェクトタイプを選択する。判定ブロック３０２で、すべてのタイプがすでに選択されている場合は、コンポーネントはリターンし、そうでない場合は、コンポーネントはブロック３０３で継続する。ブロック３０３で、コンポーネントは、選択されたタイプについて次のタイプ内関係を選択する。判定ブロック３０４で、すべてのタイプ内関係がすでに選択されている場合は、コンポーネントはブロック３０６で継続し、そうでない場合は、コンポーネントはブロック３０５で継続する。ブロック３０５で、コンポーネントは、選択されたタイプおよび選択されたタイプ内関係について、関係データの要素を設定する。次いでコンポーネントは、ブロック３０３にループして次のタイプ内関係を選択する。ブロック３０６で、コンポーネントは、選択されたタイプについて次のタイプ間関係を選択する。判定ブロック３０７で、すべてのタイプ間関係がすでに選択されている場合は、コンポーネントはブロック３０１にループして次のオブジェクトタイプを選択し、そうでない場合は、コンポーネントはブロック３０８で継続する。ブロック３０８で、コンポーネントは、選択されたタイプおよび選択されたタイプ間関係について、関係データの要素を設定する。次いでコンポーネントは、ブロック３０６にループして、選択されたタイプについて次のタイプ間関係を選択する。

図４は、一実施形態における類似性関数解決コンポーネントの処理を示す流れ図である。ブロック４０１で、コンポーネントは、類似性行列を初期化する。例えば、コンポーネントは、対角線の類似性値を１に設定して最大類似性を示し、他の類似性値を乱数に設定することができる。ブロック４０２で、コンポーネントは、少なくとも１回の反復が実行されるように、差分値を非常に大きい数に設定する。ブロック４０３〜４０８で、コンポーネントは、複数の反復での全体的な類似性関数を計算して、類似性値が解に収束するまで類似性行列を更新しながらループする。ブロック４０３で、コンポーネントは次の反復を選択する。判定ブロック４０４で、このタイプの類似性についての差分値の合計がしきい値差分未満である場合は、解は収束しており、コンポーネントはリターンする。そうでない場合は、コンポーネントはブロック４０５で継続する。ブロック４０５で、コンポーネントは次のオブジェクトタイプを選択する。判定ブロック４０６で、すべてのタイプがすでに選択されている場合は、コンポーネントはブロック４０８で継続し、そうでない場合は、コンポーネントはブロック４０７で継続する。ブロック４０７で、コンポーネントは、選択されたタイプについて類似性関数を計算して、選択されたタイプについての類似性行列を更新し、次いでブロック４０５にループして次のタイプを選択する。ブロック４０８で、コンポーネントは、選択されたタイプについて、この反復の類似性値と前の反復の類似性値との差を計算する。次いでコンポーネントは、ブロック４０３にループして次の反復を開始する。

図５は、一実施形態における類似性計算コンポーネントの処理を示す流れ図である。コンポーネントは、オブジェクトのタイプを渡され、そのタイプについての類似性行列を更新する。ブロック５０１で、コンポーネントは、渡されたタイプについて次のタイプ内類似性関数を選択する。判定ブロック５０２で、すべてのタイプ内類似性関数がすでに選択されている場合は、コンポーネントはブロック５０４で継続し、そうでない場合は、コンポーネントはブロック５０３で継続する。ブロック５０３で、コンポーネントは、渡されたタイプの各オブジェクトについて、新しい類似性値を計算する。次いでコンポーネントは、ブロック５０１にループして次のタイプ内類似性関数を選択する。ブロック５０４で、コンポーネントは、渡されたタイプについて次のタイプ間類似性関数を選択する。判定ブロック５０５で、すべてのタイプ間類似性関数がすでに選択されている場合は、コンポーネントはブロック５０７で継続し、そうでない場合は、コンポーネントはブロック５０６で継続する。ブロック５０６で、コンポーネントは、選択されたタイプ間類似性関数を使用して、渡されたタイプの各オブジェクトについて新しい類似性値を計算する。次いでコンポーネントは、ブロック５０４にループして次のタイプ間類似性関数を選択する。ブロック５０７で、コンポーネントは、重みを使用して行列を組み合わせ、現在の反復で渡されたタイプについての全体的な類似性を生成する。次いでコンポーネントはリターンする。

本明細書では説明のために類似性システムの特定の実施形態について述べたが、本発明の趣旨および範囲を逸脱することなく様々な修正を加えることができることを当業者は理解するであろう。したがって、本発明は、添付の特許請求の範囲による以外には限定されない。

一実施形態における類似性システムのコンポーネントを示すブロック図である。 一実施形態における類似性関数定義コンポーネントの処理を示す流れ図である。 一実施形態における関係確立コンポーネントの処理を示す流れ図である。 一実施形態における類似性関数解決コンポーネントの処理を示す流れ図である。 一実施形態における類似性計算コンポーネントの処理を示す流れ図である。

符号の説明

１０１ ウェブサイト１
１０１ ウェブサイトＮ
１０２ 通信リンク
１１０ 類似性システム
１１１ 類似性計算
１１２ 類似性関数定義
１１３ 関係確立
１１４ 類似性関数解決

Claims (31)

1. オブジェクト間の類似性の測定値を生成するためのコンピュータシステムによって実行される方法であって、各オブジェクトは複数のタイプのうちの１つを有し、１つのタイプはタイプ内関係を有し、タイプの対はタイプ間関係を有し、前記コンピュータシステムは、
   各タイプにつき、
   そのタイプの類似性がタイプ内関係に基づくとき、そのタイプのオブジェクト間の類似性を測定する当該関係ごとのタイプ内類似性関数と、
   そのタイプの類似性がタイプ間関係に基づくとき、別のタイプのオブジェクトの類似性に基づいてそのタイプのオブジェクト間の類似性を測定する当該関係ごとのタイプ間類似性関数であって、当該タイプ間類似性関数は、そのタイプの第１のオブジェクトと第２のオブジェクトの類似性について生成し、前記第１のオブジェクトと第２のオブジェクトの類似性は、前記第１のオブジェクトと関係を有するオブジェクトと前記第２のオブジェクトと関係を有するオブジェクトから成る前記別のタイプのオブジェクトの対の間の類似性の加重平均であるタイプ間類似性関数と、
   そのタイプについての任意のタイプ内類似性関数および任意のタイプ間類似性関数に基づいてそのタイプのオブジェクト間の類似性を測定する類似性関数と、
   各関係につき、オブジェクト間のその関係を定義するデータと
   を格納するメモリ含み、前記方法は、
   前記メモリに含まれるデータによって定義される関係に基づいて、前記コンピュータシステムのプロセッサが、前記オブジェクト間の類似性の測定値が収束するまで、前記類似性関数を反復的に解くことと
   を備えることを特徴とする方法。
2. あるタイプについてのタイプ内類似性関数は、そのタイプの類似性関数に基づいて再帰的に定義されることを特徴とする請求項１に記載の方法。
3. あるタイプについてのタイプ間類似性関数は、別のタイプの類似性関数に基づいて再帰的に定義されることを特徴とする請求項１に記載の方法。
4. あるタイプについての前記類似性関数は、そのタイプについてのタイプ内およびタイプ間の類似性関数の一次結合であることを特徴とする請求項１に記載の方法。
5. 各タイプ内およびタイプ間の類似性関数に重みが与えられることを特徴とする請求項４に記載の方法。
6. そのタイプについての前記タイプ内およびタイプ間の類似性関数に対する重みの合計は１であることを特徴とする請求項５に記載の方法。
7. 前記タイプ間類似性関数は、そのタイプの第１および第２のオブジェクトについての類似性を測定し、該類似性が他のタイプのオブジェクトの対の間の類似性であって、前記第１のオブジェクトと関係を有する前記対の一方のオブジェクトと前記第２のオブジェクトと関係を有する前記対の他方のオブジェクトを有する前記他のタイプのオブジェクトの対の間の類似性に基づくことを特徴とする請求項１に記載の方法。
8. 前記類似性関数は、ある反復から次の反復への類似性に基づく差分尺度が収束するときに解かれることを特徴とする請求項７に記載の方法。
9. 前記類似性関数は、ある反復から次の反復への類似性に基づく差分尺度がしきい値差分未満のときに解かれることを特徴とする請求項７に記載の方法。
10. オブジェクトの前記タイプはウェブページおよびクエリを含み、クエリとウェブページとの間のタイプ間関係はクエリからウェブページへのクリックスルーに基づくことを特徴とする請求項１に記載の方法。
11. オブジェクトの前記タイプはウェブページおよびクエリを含み、ウェブページについてのタイプ内関係は入リンクおよび出リンクに基づき、ウェブページとクエリとの間のタイプ間関係はクエリからウェブページへのクリックスルーに基づくことを特徴とする請求項１に記載の方法。
12. オブジェクト間の類似性の測定値を生成するためにコンピュータシステムを制御するための命令を収容したコンピュータ可読媒体であって、各オブジェクトは複数のタイプの１つを有し、前記コンピュータシステムは、
    各タイプにつき、そのタイプについてタイプ内類似性が定義されたときそのタイプのオブジェクト間のタイプ内類似性と、そのタイプについてタイプ間類似性が定義されたとき別のタイプのオブジェクトの類似性に基づくそのタイプのオブジェクト間のタイプ間類似性とに基づいて、そのタイプのオブジェクト間の類似性を測定する類似性関数であって、そのタイプの第１のオブジェクトと第２のオブジェクトのタイプ間類似性は、前記第１のオブジェクトと関係を有するオブジェクトと前記第２のオブジェクトと関係を有するオブジェクトから成る前記別のタイプのオブジェクトの対の間のタイプ内類似性の加重平均である類似性関数と、
    各関係につき、オブジェクト間のその関係を定義するデータと
    を格納するメモリ含み、前記命令は、前記コンピュータシステムのプロセッサに
    前記メモリに含まれるデータによって定義される前記関係に基づいて、前記オブジェクト間の類似性の測定値が収束するまで、前記類似性関数を反復的に解かせることを特徴とするコンピュータ可読媒体。
13. 前記類似性関数は、線形式のセットを定義することを特徴とする請求項１２に記載のコンピュータ可読媒体。
14. 類似性関数は、異なるタイプのオブジェクトの類似性に基づいて再帰的に定義されることを特徴とする請求項１２に記載のコンピュータ可読媒体。
15. 類似性関数は、種々の関係についてのそのタイプのオブジェクトの類似性に基づいて再帰的に定義されることを特徴とする請求項１２に記載のコンピュータ可読媒体。
16. あるタイプについての前記類似性関数は、そのタイプについてのタイプ内およびタイプ間の類似性関数の一次結合であることを特徴とする請求項１２に記載のコンピュータ可読媒体。
17. 各タイプ内およびタイプ間の類似性に重みが与えられることを特徴とする請求項１６に記載のコンピュータ可読媒体。
18. そのタイプについての前記タイプ内およびタイプ間の類似性に対する重みの合計は１であることを特徴とする請求項１７に記載のコンピュータ可読媒体。
19. 前記タイプ間類似性関数は、そのタイプの第１および第２のオブジェクトについての類似性を生成し、該類似性は、他のタイプのオブジェクトの対の間の類似性であって、前記第１のオブジェクトと関係を有する前記対の一方のオブジェクトと前記第２のオブジェクトと関係を有する前記対の他方のオブジェクトを有する前記他のタイプのオブジェクトの対の間の類似性に基づくことを特徴とする請求項１２に記載のコンピュータ可読媒体。
20. 前記類似性関数は、ある反復から次の反復への類似性に基づく差分尺度が収束するときに解かれることを特徴とする請求項１９に記載のコンピュータ可読媒体。
21. 前記類似性関数は、ある反復から次の反復への類似性に基づく差分尺度がしきい値差分未満のときに解かれることを特徴とする請求項１９に記載のコンピュータ可読媒体。
22. オブジェクトの類似性スコアを計算するためのコンピュータシステムであって、各オブジェクトは複数のタイプの１つを有し、各タイプは別のタイプとのタイプ間関係を有し、
    各タイプにつき、そのタイプについてタイプ内類似性が定義されたときそのタイプのオブジェクト間のタイプ内類似性と、そのタイプのオブジェクトと別のタイプのオブジェクトとの間のタイプ間類似性とに基づいてそのタイプのオブジェクトの対の類似性スコアを提供する類似性関数であって、前記タイプ間類似性は前記別のタイプのオブジェクトの対の間の類似性スコアと、オブジェクトの対の間のタイプ間関係とに基づいて再帰的に定義され、そのタイプの第１のオブジェクトと第２のオブジェクトのタイプ間類似性は、前記第１のオブジェクトと関係を有するオブジェクトと前記第２のオブジェクトと関係を有するオブジェクトから成る前記別のタイプのオブジェクトの対の間のタイプ内類似性の加重平均である、類似性関数を格納するメモリと、
    前記類似性スコアが収束するまで、前記メモリに含まれる類似性関数を反復的に呼び出すことによって、オブジェクトのセットについて定義されたタイプ間関係に基づいて前記類似性関数を解くプロセッサと
    を備えたことを特徴とするコンピュータシステム。
23. 前記類似性関数は、線形式のセットを定義することを特徴とする請求項２２に記載のコンピュータシステム。
24. １つのタイプは、そのタイプのオブジェクト間のタイプ内関係を有し、前記類似性関数はそのタイプのオブジェクト間のタイプ内関係に基づく前記オブジェクト間のタイプ内類似性にさらに基づくことを特徴とする請求項２２に記載のコンピュータシステム。
25. あるタイプについてのタイプ内類似性は、そのタイプのオブジェクトと別のタイプのオブジェクトとの間のタイプ間類似性に基づくことを特徴とする請求項２４に記載のコンピュータシステム。
26. 類似性関数は、種々のタイプ内関係についてのオブジェクトのタイプ内類似性に基づいて再帰的に定義されることを特徴とする請求項２４に記載のコンピュータシステム。
27. あるタイプについての前記類似性関数は、そのタイプについてのタイプ内およびタイプ間の類似性関数の一次結合であることを特徴とする請求項２４に記載のコンピュータシステム。
28. 各タイプ内およびタイプ間の類似性関数に重みが与えられることを特徴とする請求項２７に記載のコンピュータシステム。
29. そのタイプについての前記タイプ内およびタイプ間の類似性関数に対する重みの合計は１であることを特徴とする請求項２８に記載のコンピュータシステム。
30. 前記類似性スコアは、ある反復から次の反復への類似性に基づく差分尺度が差分しきい値未満のときに収束することを特徴とする請求項２２に記載のコンピュータシステム。
31. 前記類似性関数は、ある反復から次の反復への類似性に基づく差分尺度がしきい値差分未満のときに解かれることを特徴とする請求項２２に記載のコンピュータシステム。

Images