(57)【特許請求の範囲】
【請求項１】
複数のページが含む全てのブロック内におけるイメージ間の関連性を判定するためのコンピュータによって行われる方法であって、前記複数のページの各々は、１つまたは複数のブロックを含み、前記複数のブロックの各々は、１つまたは複数のイメージおよびリンクを含む方法において、該方法は、
ブロックとページの組み合わせごとに、ページからブロックへの行列生成コンポーネントが、前記ページに対する前記ブロックの重要度の指標を計算するステップと、
ページとブロックの組み合わせごとに、ブロックからページへの行列生成コンポーネントが、前記ブロックに対する前記ページの重要度の指標を計算するステップと、
イメージとブロックの組み合わせごとに、ブロックからイメージへの行列生成コンポーネントが、前記ブロックに対する前記イメージの重要度の指標を計算するステップと、
イメージからイメージへの行列生成コンポーネントが、前記ページに対するブロックの重要度の指標と、前記ブロックに対するページの重要度の指標と、前記ブロックに対するイメージの重要度の指標とを組み合わせることにより、別のイメージに対するイメージの関連性のイメージ間指標を計算するステップと、
計算された前記別のイメージに対するイメージの関連性のイメージ間指標をメモリに格納するステップと
を具備したことを特徴とする方法。
【請求項２】
前記ブロックに対するページの重要度の指標は、ユーザが、各他のページに通じるリンクを各ブロックから選択する確率である、ことを特徴とする請求項１に記載の方法。
【請求項３】
前記ページに対するブロックの重要度の指標は、ユーザが前記ページの各ブロックに注目する確率である、ことを特徴とする請求項１に記載の方法。
【請求項４】
前記ブロックに対するイメージの重要度の指標は、ユーザが各ブロックの各イメージに注目する確率である、ことを特徴とする請求項１に記載の方法。
【請求項５】
前記ブロックに対するページの重要度の指標は、ユーザが、各他のページに通じるリンクを各ブロックから選択する確率であり、前記ページに対するブロックの重要度の指標は、ユーザが、前記ページの各ブロックに注目する確率であり、前記ブロックに対するイメージの重要度の指標は、ユーザが各ブロックの各イメージに注目する確率である、ことを特徴とする請求項１に記載の方法。
【請求項６】
前記イメージ間指標から前記イメージのランクを計算するステップを含む、ことを特徴とする請求項１に記載の方法。
【請求項７】
前記計算されるランクは、任意のイメージから開始したユーザが、イメージ間の任意数の多数回の遷移の後に別のイメージに移る確率に基づく、ことを特徴とする請求項６に記載の方法。
【請求項８】
前記イメージ間指標は、次のように計算され、
ＷＩ＝ＹＴＷＢＹ
ここでＷＩは、前記イメージ間指標の行列であり、Ｙは、イメージからブロックへの指標の行列であり、
ＷＢ＝ＺＸ
ここでＷＢは、ブロックからブロックへの指標の行列であり、Ｚは、前記ブロックに対するページの重要度の指標の行列であり、Ｘは、前記ページに対するブロックの重要度の指標の行列である、ことを特徴とする請求項１に記載の方法。
【請求項９】
前記イメージ間指標に基づいて各イメージのベクトル表現を生成するステップと、
各自のベクトル表現に基づいてイメージのクラスタを識別するステップであって、クラスタ中のイメージは互いに関連しているステップと、
をさらに具備していることを特徴とする請求項１に記載の方法。
【請求項１０】
前記ベクトル表現を生成するステップは、目的関数を最小にするベクトル表現を選択するステップを含む、ことを特徴とする請求項９に記載の方法。
【請求項１１】
前記目的関数は、イメージの各対の前記ベクトル表現間の距離の二乗に、前記計算された確率から得られる前記イメージの対の類似度を乗じた合計である、ことを特徴とする請求項１０に記載の方法。
【請求項１２】
請求項１乃至１１の何れかに記載の方法を実行するための実行可能コードを含むコンピュータ可読媒体。
【請求項１３】
複数のページが含む全てのブロック内にあるイメージ間の関連性を判定するコンピュータシステムであって、前記複数のページの各々は、１つまたは複数のブロックを含み、前記複数のブロックの各々は、１つまたは複数のイメージおよびリンクを含み、
前記ページと前記ブロックの組み合わせごとに計算される、ブロックに対するページの重要度の指標と、
前記ブロックと前記ページの組み合わせごとに計算される、ページに対するブロックの重要度の指標と、
前記イメージと前記ブロックの組み合わせごとに計算される、ブロックに対するイメージの重要度の指標と、
前記ブロックに対するページの重要度の指標と、前記ページに対するブロックの重要度の指標と、前記ブロックに対するイメージの指標とを組み合わせることにより、別のイメージに対するイメージの関連性のイメージ間の指標を計算する手段と、
を具備したことを特徴とするコンピュータシステム。
【請求項１４】
ブロックに対するページの重要度の指標を、ユーザが、各他のページに通じるリンクを各ブロックから選択する確率として計算する手段を含む、ことを特徴とする請求項１３に記載のコンピュータシステム。
【請求項１５】
ページに対するブロックの重要度の指標を、ユーザが前記ページの各ブロックに注目する確率として計算する手段を含む、ことを特徴とする請求項１３に記載のコンピュータシステム。
【請求項１６】
ブロックに対するイメージの重要度の指標を、ユーザが各ブロックの各イメージに注目する確率として計算する手段を含む、ことを特徴とする請求項１３に記載のコンピュータシステム。
【請求項１７】
前記イメージ間指標から、前記イメージのランクを計算する手段を含む、ことを特徴とする請求項１３に記載のコンピュータシステム。
【請求項１８】
前記計算されるランクは、任意のイメージから開始したユーザが、イメージ間の任意数の多数回の遷移の後に別のイメージに移る確率に基づく、ことを特徴とする請求項１７に記載のコンピュータシステム。
【請求項１９】
前記イメージ間指標に基づいて各イメージのベクトル表現を生成する手段と、
各自のベクトル表現に基づいてイメージのクラスタを識別する手段であって、クラスタ中のイメージは互いに関連している手段と、
を含むことを特徴とする請求項１３に記載のコンピュータシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般にはウェブページの分析に関し、より詳細には、ウェブページのイメージの関連性(relatedness)に関する。
【背景技術】
【０００２】
ＧｏｏｇｌｅやＯｖｅｒｔｕｒｅといった検索エンジンサービスの多くは、インターネットを介してアクセスすることができる情報の検索を提供する。そうした検索エンジンサービスにより、ユーザは、ユーザの関心の対象となる可能性のあるウェブページなどの表示ページを検索することができる。ユーザが検索語を含む検索要求を提出すると、検索エンジンサービスは、その検索語に関連する可能性のあるウェブページを識別する。関連するウェブページを迅速に識別するために、検索エンジンサービスは、キーワードとウェブページとの対応付けを保持することができる。この対応付けは、ウェブ（すなわちＷｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ）を「クローリング（巡回：crawling）および索引付け(：インデックシングindexing)」して、各ウェブページのキーワードを識別することによって生成することができる。ウェブをクローリングするために、検索エンジンサービスは、ルートウェブページのリストを使用して、そのルートウェブページを通じてアクセスできるすべてのウェブページを識別することができる。特定のウェブページのキーワードは、見出しにある単語、ウェブページのメタデータ中に供給される単語、ハイライト表示される単語などを識別するなどの、各種のよく知られる情報検索技術を使用して識別することができる。そして、検索エンジンサービスは、それぞれの一致の近接度、ウェブページの人気度（例えばＧｏｏｇｌｅのＰａｇｅＲａｎｋ）などに基づいて、検索結果のウェブページをランク付けする。検索エンジンサービスは、ウェブページの情報がどれだけ検索要求に関連する可能性があるか否かを示す関連度スコアも生成することができる。そして、検索エンジンサービスは、ユーザに、それぞれのランクに基づいた順序でそれらのウェブページへのリンクを表示する。
【０００３】
多くのウェブページは、多くのイメージを含み得る点でグラフィック指向であるが、従来の検索エンジンサービスは、一般に、ウェブページの文字内容のみに基づいて検索を行う。しかし、イメージに基づいてウェブページの検索を支援する試みが、これまでにいくつかなされている。例えば、あるウェブページを閲覧するユーザが、そのウェブページにあるイメージに関連するイメージを含んでいる他のウェブページを特定したい場合がある。イメージに基づく検索技術は、通例は、内容に基づくか、リンクに基づくかのいずれかであり、イメージの分析を助けるために追加的にイメージの周辺にあるテキストを使用する。内容に基づく技術は、イメージの索引付けのために低レベルの視覚的情報を使用する。内容に基づく検索技術は、計算処理上非常にコストがかかるので、ウェブ上のイメージ検索には実用的でない。リンクに基づく検索技術では、通例、同じウェブページ上のイメージは関連する可能性が高く、同じウェブページによって互いにリンクされているウェブページ上のイメージは関連性があると想定する。不都合な点として、こうした想定は、主として、１つのウェブページには多くの異なる話題に関連する内容がある場合がので、多くの状況では適当でない。例えば、ニュースを扱うウェブサイトのウェブページは、国際政治の出来事に関連する内容と、一国のスポーツイベントに関連する内容を含む場合がある。そのような場合、一国のスポーツイベントに関連するスポーツチームの写真が、国際政治の出来事に関連する内容からリンクされたウェブページに関連することは考えにくい。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
従来の内容に基づく検索技術ほど計算処理上高コストでなく、また、従来のリンクに基づく検索技術と異なって、１つのウェブページ上に出現する可能性のある多種多様な話題を考慮する、イメージに基づく検索技術を得ることが望ましい。
【課題を解決するための手段】
【０００５】
リンクおよびページレイアウトの分析に基づいて、ページのイメージ間の関連性(relatedness)を判定するシステムを提供する。リンク分析システム(link analysis system)が、まずページにあるブロックを識別し、次いで、ページに対するブロックの重要度(importance of the blocks to pages)、ブロックに対するページ(pages to block)の重要度、およびブロックに対するイメージ(images to blocks)の重要度を分析することにより、イメージ間の関連性(relatedness between images)を判定(determine)する。この分析に基づいて、リンク分析システムは、各イメージが他の各イメージに関連する度合い(degree)を判定する。別のイメージに対するイメージの関連性は、ページレベルの重要度(page-level importance)ではなく、ページよりも小さな単位であるブロックのレベルの重要度に基づくので、この関連性は、従来のリンクに基づく検索技術に比べてより正確な関連性の表現(representation of relatedness)となる。
【発明を実施するための最良の形態】
【０００６】
リンクとページのレイアウトの分析に基づいてページのイメージの関連性を判定する方法およびシステムを提供す。一実施形態では、リンク分析システムが、まずウェブページ中のブロックを識別し、次いでウェブページに対するブロックの重要度、ブロックに対するウェブページの重要度、および、ブロックに対するイメージの重要度を分析することにより、イメージ間の関連性を判定する。この分析に基づいて、リンク分析システムは、各イメージが他の各イメージに関連する度合いを判定する。ウェブページのブロックは、同様の話題に関連するように思われるウェブページの領域である。例えば、国際政治の出来事に関連するニュース記事が１つのブロックに相当し、一国のスポーツイベントに関連するニュース記事が別のブロックに相当する。ページに対するブロックの重要度は、ユーザが、そのページを閲覧する際にそのブロックに注目する確率を表すことができる。ブロックに対するページの重要度は、ユーザが、そのブロックから、そのページへのリンクを選択する確率を表すことができる。ブロックに対するイメージの重要度は、ユーザがそのブロックを見る際にそのイメージに注目する確率を表すことができる。ページとブロックの対およびイメージとブロックの対について、これらの重要度の数値指標を計算すると、リンク分析システムは、計算されたページに対するブロックの重要度と、計算されたブロックに対するページの重要度と、計算されたブロックに対するイメージの重要度を組み合わせることにより、各イメージと他の各イメージとの関連性の指標を生成する。あるイメージの別のイメージに対する関連性は、ページレベルの重要度ではなくブロックレベルの重要度に基づくので、この関連性は、従来のリンクに基づく検索技術よりも正確な関連性の表現になる。
【０００７】
リンク分析システムは、イメージ間の関連性を使用して、イメージのランク付けを生成することもできる。このランク付けは、任意のイメージを見始めたユーザが、任意数の複数回のイメージ間の遷移を経た後に別のイメージに移る確率に基づくことができる。リンク分析システムは、イメージ間の関連度に基づいてイメージのベクトル表現を生成し、そのベクトル表現にクラスタリングアルゴリズムを適用して、関連するイメージのクラスタを識別することもできる。
【０００８】
図１は、ウェブページの集まりの例におけるブロック、イメージ、およびリンクを説明するブロック図である。このウェブページの集まりには、ウェブページ１〜４が含まれる。ウェブページ内のブロックは長方形で表され、ブロック内のイメージは円で表され、ブロック内にあるリンクは、ブロックからリンク先のウェブページへの方向をつけた矢印で表される。ウェブページ１は、ブロック１を含み、ブロック１は、イメージ１および２とリンク１および２を含んでいる。ウェブページ２は、イメージ３とリンク３を含んでいるブロック２と、イメージ４とリンク４を含んでいるブロック３を含む。ウェブページ３は、イメージ５とリンク５および６を含んでいるブロック４と、イメージ６およびリンク７を含んでいるブロック５を含む。ウェブページ４は、ブロック５を含み、ブロック５は、イメージ７、８、９、１０、およびリンク８を含んでいる。リンク分析システムは、イメージの関連性を、ウェブページ全体ではなくブロックに基づかせるので、あるイメージの他のイメージに対する関連性は、イメージの話題のより正確な表現に基づく可能性が高い。例えば、ウェブページ２は、ブロック２および３を含んでおり、それらのブロックは、それぞれ国際政治の出来事と一国のスポーツイベントなど異なる話題を対象とする可能性がある。リンク分析システムは、イメージ４を含むブロック３はウェブページ４へのリンク４を有するので、イメージ４は、ウェブページ３のイメージよりもウェブページ４のイメージにより密接に関連することを識別することができる。例えば、ブロック３は、ウェブページ４へのリンクを含むが、ウェブページ３へのリンクは含まないので、ウェブページ４は、ウェブページ３よりもスポーツに関連する可能性が高い。そのため、イメージ４は、ウェブページ３のイメージ５および６よりも、イメージ７、８、９、１０に関連する可能性が高い。ブロックレベルの分析を利用しない技術では、ウェブページ２のブロック２とブロック３を区別しないので、イメージ４は、ウェブページ３とウェブページ４に等しく関連すると識別する可能性がある。
【０００９】
一実施形態では、リンク分析システムは、ブロックとページの組み合わせごとに、ブロックに対するページの重要度を、そのブロックにあるリンクを選択するユーザがそのページへのリンクを選択する確率として計算する。ブロックにページへのリンクがない場合、確率はゼロになる。ブロックがあるページへのリンクを持つ場合、リンク分析システムは、ユーザが、そのブロックの各リンクを等しい確率で選択すると想定することができる。確率のブロックからページへの行列は、次の式で定義される。
【００１０】
【数１】
0004634214.tif 000002
【００１１】
ここでＺｉｊは、ブロックｉにあるリンクを選択するユーザがページｊへのリンクを選択する確率を表し、ｓｉは、ブロックｉのリンク数である。図１のウェブページのブロックからページへの行列Ｚが表１に示される。表１の行は、ブロックを表し、列は、ページを表す。この例では、ブロック４にあるリンクを選択するユーザがウェブページ２へのリンクを選択する確率は０．５である。
【００１２】
【表１】
0004634214.tif 000003
【００１３】
一実施形態では、リンク分析システムは、ページとブロックの組み合わせごとに、ページに対するブロックの重要度を、そのブロックがそのページの最も重要なブロックである確率として計算する。あるページに含まれないブロックがそのページの最も重要なブロックである確率は、ゼロである。リンク分析システムは、１つのページに含まれる各ブロックは、等しい確率で最も重要なブロックとなると想定することができる。ページからブロックへの確率の行列は、次の式で定義される。
【００１４】
【数２】
0004634214.tif 000004
【００１５】
ここでＸｉｊは、ブロックｊがページｉの最も重要なブロックである確率を表し、ｓｉは、ページｉにあるブロックの数である。
【００１６】
一実施形態では、リンク分析システムは、ブロックがページの最も重要なブロックである確率を、そのブロックの位置、サイズ、フォント、色、および他の物理的属性に基づいて計算する。例えば、ページの真中に中心が置かれた大きなブロックは、ページの左下の隅にある小さなブロックよりも重要である可能性がある。ブロックの重要度と、ブロックのコヒーレンシー（ｃｏｈｅｒｅｎｃｙ）の度合いを計算する技術が２００４年４月２９日出願  米国特許出願第              号「Method and System for Calculating Importance of a Block Within a Display Page」に記載される同文献は、参照により本明細書に組み込まれる。ページからブロックへの行列(page-to-block matrix)Ｘは、より一般的には次のように表すことができる。
【００１７】
【数３】
0004634214.tif 000005
【００１８】
ここでｆｐｉは、ブロックｊがページｉの最も重要なブロックである確率を表す関数である。一実施形態では、関数ｆｐｉは、ブロックｊのサイズを、ページｉが表示された際の画面の中心からブロックの中心までの距離で割った数として定義される。関数ｆは、次のように定義することができる。
【００１９】
【数４】
0004634214.tif 000006
【００２０】
ここでαは、１つのブロックについて関数の値の合計が１になることを保証する正規化係数である。関数ｆは、ユーザが、ページｉを閲覧する際にブロックｊに注目する確率と考えることができる。図１のウェブページのページからブロックへの行列Ｘが表２に示される。表２の行はページを表し、列はブロックを表す。この例では、ブロック４がウェブページ３の最も重要なブロックである確率は、０．８である。
【００２１】
【表２】
0004634214.tif 000007
【００２２】
一実施形態では、リンク分析システムは、ブロックとイメージの各組み合わせについて、ブロックに対するイメージの重要度を、そのイメージがそのブロックの最も重要なイメージである確率として計算する。ブロックがあるイメージを含まない場合、そのイメージがそのブロックの最も重要なイメージである確率はゼロになる。リンク分析システムは、ブロックの各イメージは、等しい確率で最も重要なイメージになると想定することができる。リンク分析システムは、イメージの相対的なサイズ、ブロック内のイメージの位置を利用するなど、ブロックに対するイメージの他の重要度の基準を用いてもよい。ブロックからイメージへの確率の行列は、次の式で定義される。
【００２３】
【数５】
0004634214.tif 000008
【００２４】
ここでＹｉｊは、イメージｊがブロックｉの最も重要なイメージである確率を表し、ｓｉは、ブロックｉにあるイメージの数である。図１のウェブページのブロックからイメージへの行列Ｙが、表３に示される。表３の行はブロックを表し、列はイメージを表す。この例では、イメージ２がブロック１の最も重要なイメージである確率は０．５である。
【００２５】
【表３】
0004634214.tif 000009
【００２６】
一実施形態では、リンク分析システムは、順序付けられたページの対それぞれについて、別のページに対するあるページの重要度を、その対の第１のページを閲覧するユーザが、その対の第２のページへのリンクを選択する確率として計算する。リンク分析システムは、第１のページの各ブロックについて、そのブロックが第１のページの最も重要なブロックである確率と、第２のページがそのブロックにとって最も重要なページである確率をかけて合計することにより、各対の確率を計算する。したがって、別のページに対するあるページの重要度は、ユーザは、ページ中の最も重要なブロックにあるリンクを選択することを好む可能性があるという点で加味される。ページとページ間の確率の行列が以下によって表される。
Ｗｐ＝ＸＺ                                （６）
【００２７】
ここでＷｐは、ページとページ間の行列を表す。Ｗの確率は、代わりに次のように表すこともできる。
Ｐｒｏｂ（β｜α）＝Σｂ∈α  Ｐｒｏｂ（β｜ｂ）Ｐｒｏｂ（ｂ｜α）      （７）
【００２８】
ここでαは、対の第１のページを表し、βは、対の第２のページを表す。図１のウェブページのページとページ間の行列Ｗｐが、表４に示される。この例では、ページ３を閲覧するユーザがページ２に移る確率は０．４である。
【００２９】
【表４】
0004634214.tif 000010
【００３０】
リンク分析システムは、順序付けられたブロックの対それぞれについて、別のブロックに対するあるブロックの重要度を、その対の第１のブロックを閲覧しているユーザが、その対の第２のブロックを含むページへのリンクを選択し、第２のブロックがそのページで最も重要であることを発見する確率として計算する。リンク分析システムは、第１のブロックにあるリンクを選択するユーザが、第２のブロックを含むページへのリンクを選択する確率と、その第２のブロックがそのページで最も重要なブロックである確率をかけて合計することにより、各対の確率を計算する。したがって、別のブロックに対するあるブロックの重要度は、第１のブロックを閲覧するユーザが、第２のブロックを含むページへのリンクを選択し、第２のブロックに注目することを意味する。これらの確率のブロックとブロックの行列は、次により表される。
ＷＢ＝ＺＸ                                                  （８）
【００３１】
ここでＷＢは、ブロックとブロック間の行列を表す。Ｗの確率は、代わりに次のように表すこともできる。
ＷＢ（ａ，ｂ）＝Ｐｒｏｂ（ｂ｜ａ）
＝Σγ∈ＰＰｒｏｂ（γ｜ａ）Ｐｒｏｂ（ｂ｜γ）
＝Ｐｒｏｂ（β｜ａ）Ｐｒｏｂ（ｂ｜β）
＝Ｚ（ａ，β）Ｘ（β，ａ），  ａ，ｂ∈Ｂ      （９）
【００３２】
図１のウェブページのブロックとブロック間の行列ＷＢは、次の表５に示してある。この例では、ブロック４を閲覧するユーザがページ２にジャンプし、ブロック３に注目する確率は０．２５である。
【００３３】
【表５】
0004634214.tif 000011
【００３４】
一実施形態において、リンク分析システムは、同じページにある２つのブロックが関連する可能性がある確率を、ブロックとブロック間の行列に加味する。この点が変更されたブロックとブロック間の行列は、次のように表される。
ＷＢ＝（１−ｔ）ＺＸ＋ｔＤＵ                                （１０）
【００３５】
ここでＤは、対角行列Ｄｉｉ＝ΣｊＵｉｊであり、Ｕは、コヒーレンス行列であり、ｔは重み係数である。行列Ｕは、次のように定義される。
【００３６】
【数６】
0004634214.tif 000012
【００３７】
ここでＤＯＣは、ブロックｉとブロックｊの両方を含む最小のブロックのコヒーレンシーの度合いである。大半の事例では、同じページにある異なるブロックは異なる話題に関連するので、重み係数ｔは、通例は、最小の値（０．１未満など）に設定することができる。
【００３８】
リンク分析システムは、順序付けられたイメージの対それぞれについて、その対の第１のイメージがその対の第２のイメージに関連する確率を計算する。リンク分析システムは、第１のイメージを含んでいる各ブロックと第２のイメージを含んでいる各ブロックとの組み合わせについてブロック間の確率を合計することにより、確率を計算する。それらの確率のイメージとイメージ間の行列は、次のように表される。
ＷＩ＝ＹＴＷＢＹ                                              （１２）
【００３９】
ここでＷＩは、イメージとイメージ間の行列を表す。図１のウェブページのイメージとイメージ間の行列ＷＩは、次の表６に示してある。この例では、ブロック１０を閲覧するユーザが次にページ３を閲覧し、ブロック５に注目する確率は、０．０５である。
【００４０】
【表６】
0004634214.tif 000013
【００４１】
一実施形態において、リンク分析システムは、同じページにある２つのブロックが関連する可能性がある確率を、イメージとイメージ間の行列に加味する。この点を変更したイメージとイメージ間の行列は、次のように表される。
ＷＩ＝ｔＤＹＴＹ＋（１−ｔ）ＹＴＷＢＹ                        （１３）
【００４２】
ここでｔは重み係数であり、Ｄは、
Ｄｉｉ＝Ｅｊ（ＹＴＹ）ｉｊ                                    （１４）
を表す対角行列である。
【００４３】
同じブロックにある２つのイメージは関連する可能性が高いので、重み係数ｔは、大きな値（例えば０．７〜０．９）に設定することができる。
【００４４】
一実施形態において、リンク分析システムは、イメージとイメージ間の行列から各イメージのベクトル表現を生成する。リンク分析システムは、イメージとイメージ間の行列によって示されるイメージの対の間の類似性を考慮する最小二乗法を使用してベクトルを生成する。リンク分析システムは、初めに、イメージとイメージ間の行列を、次によって表される類似度行列(similarity matrix)に変換する。
【００４５】
【数７】
0004634214.tif 000014
【００４６】
ここでＳは、類似度行列を表す。ｙｉがイメージｉのベクトル表現である場合、イメージベクトルの最適な集合は、次の目的関数を使用して得られるｙ＝（ｙ１，．．．，ｙｍ）になる。
【００４７】
【数８】
0004634214.tif 000015
【００４８】
ここでＤは対角行列であり、Ｄｉｉが、類似度行列Ｓのｉ番目の行の値の合計である場合、最小化問題は、次のようになる。
【００４９】
【数９】
0004634214.tif 000016
【００５０】
ここでＬは、Ｄ−Ｓに等しい。この解は、一般固有値問題の最小固有値の解法によって与えられる。
Ｌｙ＝λｙ                        （１８）
【００５１】
（ｙ０，λ０），（ｙ１，λ１），．．．，（ｙｍ−１，．．．，λｍ−１）が式１６の解である場合、λ０＜λ１＜．．．＜λｍ−１であり、したがって、λ０＝０、そしてｙ０＝（１，１，．．．，１）となる。リンク分析システムは、イメージをｋ次元のユークリッド空間で表す固有ベクトル１〜Ｋを選択する。イメージのベクトルは、次のように表される。
イメージｊ←（ｙｉ（ｊ），．．．，ｙｋ（ｊ））        （１９）
【００５２】
ここでｙｉ（ｊ）は、ｙｉのｊ番目の要素を表す。
【００５３】
リンク分析システムは、イメージベクトル間の距離がイメージ間の意味的な類似度を表すようにベクトルで各イメージを表すことにより、関連性のあるイメージのクラスタを識別する。イメージベクトルに各種のクラスタリングアルゴリズムを適用することにより、意味的に関連するイメージのクラスタを識別することができる。そうしたクラスタリングアルゴリズムには、スペクトルグラフ理論のＦｉｅｄｌｅｒベクトルや、ｋ−ｍｅａｎｓクラスタリングなどがある。
【００５４】
イメージのクラスタリングを使用することにより、閲覧(browsing)を支援することができる。例えば、ウェブページを閲覧(browsing)する際に、ユーザは、イメージを選択し、関連するイメージを見ることを要求することができる。すると、選択されたイメージとともにクラスタリングされているイメージを含むウェブページが、要求の結果として提示される。一実施形態では、ウェブページは、各イメージのイメージベクトルと、選択されたイメージのイメージベクトルとの距離に基づく順序で提示することができる。
【００５５】
イメージのクラスタリングを使用することにより、意味的に関連するイメージの多次元の視覚化を提供することもできる。ウェブページの集まりにあるイメージに対してイメージベクトルをが生成することができる。クラスタが識別されると、システムは、異なる固有ベクトルに基づいてクラスタを表す２次元の格子に各クラスタの指示を表示することができる。
【００５６】
リンク分析システムは、イメージとイメージ間の行列に基づいてイメージをランク付けすることができる。イメージとイメージ間の行列(image-to-image matrix)は、イメージからイメージに遷移する確率(probability of transitioning from image to image)を表す。ユーザは、あるイメージに無作為に遷移することが考えられる。これを考慮に入れるために、リンク分析システムは、この無作為性をイメージとイメージ間の行列に加味する確率遷移行列を次のように生成する。
Ｐ＝εＷ＋（１−ε）Ｕ                                （２０）
【００５７】
ここでＰは、確率遷移行列(probability transition matrix)であり、εは、重み係数（例えば０．１〜０．２）であり、Ｕは、均等な遷移の確率の遷移行列である（すべてのｉ，ｊについてＵｉｊ＝１／ｍ）。Ｕが導入されるため、グラフが連結され、グラフのランダムウォークの定常分布が存在する。イメージのランクは、次のように表すことができる。
ＰＴπ＝π                                              （２１）
【００５８】
ここでπは、イメージのランクを表す固有値１を有するＰＴの固有ベクトルである。π（πｉ，πｉ，．．．，πｍ）は、定常確率分布を表し、πｉは、イメージｉのランクを表す。
【００５９】
図２は、一実施形態におけるリンク分析システムの構成要素を示すブロック図である。リンク分析システム２００は、ウェブページストア(a web page store)２０１、イメージランク計算コンポーネント(a calculate image rank component)２０２、イメージクラスタ識別コンポーネント(an identify image cluster component)２０３、イメージとイメージ間の行列生成コンポーネント(a generate image-to-image matrix component)２１１を含む。イメージとイメージ間の行列生成コンポーネント２１１は、ブロック識別コンポーネント(an identify blocks component)２１２、ブロックからページへの行列生成コンポーネント(a generate block-to-page matrix component)２１３、ページからブロックへの行列生成コンポーネント(a generate page-to-block matrix component)２１４、および、ブロックからイメージへの行列生成コンポーネント(a generate block-to-image matrix component)２１５を使用して、イメージとイメージの関連性(image-to-image relatedness)を示す行列を生成する。ウェブページストアは、ウェブページの集まりを保持する。イメージランク計算コンポーネントは、イメージとイメージ間の行列生成コンポーネントを使用して、イメージ間の関連度を計算し、次いでその関連度の計算結果を用いてイメージをランク付けする。イメージクラスタ識別コンポーネントは、イメージとイメージ間の行列生成コンポーネントを使用して、イメージ間の関連度を計算し、行列に基づくイメージのベクトル表現を生成し、生成されたベクトルを使用してイメージのクラスタを識別する。図２には示していないが、リンク分析システムは、ウェブページのイメージ以外のランク付け要素を計算するコンポーネントを含むこともできる。例えば、リンク分析システムは、式２０および式２１のランク付けをブロックとブロック間の行列に適用してブロックをランク付けし、ページとページ間の行列に適用してページ自体をランク付けすることができる。
【００６０】
リンク分析システムをが実施するためのコンピューティングデバイスは、中央演算処理装置、メモリ、入力装置（キーボードやポインティングデバイスなど）、出力装置（表示装置など）、および、記憶装置（ディスクドライブなど）を含む。メモリと記憶装置は、リンク分析システムを実施する命令を保持することができるコンピュータ可読媒体である。また、データ構造とメッセージ構造は、記憶しても、通信リンク上の信号などのデータ伝送媒体を介して送信してもよい。インターネット、ローカルエリアネットワーク、ワイドエリアネットワーク、２地点間ダイヤルアップ接続など、各種の通信リンクを使用することができる。
【００６１】
図２は、リンク分析システムを実施することが可能な適切な動作環境の例を示す。この動作環境は、適切な動作環境の一例に過ぎず、リンク分析システムの使用または機能性の範囲についての限定を示唆するものではない。使用に適する可能性がある他のよく知られたコンピューティングシステム、環境、および構成には、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルドあるいはラップトップデバイス、マルチプロセッサシステム、マイクロプロセッサを利用したシステム、プログラム可能な家庭電化製品、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、上記のシステムあるいはデバイスを含む分散コンピューティング環境などがある。
【００６２】
リンク分析システムは、１つまたは複数のコンピュータまたは他のデバイスによって実行されるプログラムモジュールなどのコンピュータ実行可能命令との一般的関係で説明することができる。一般に、プログラムモジュールには、特定のタスクを行うか、特定の抽象データ型を実施するルーチン、プログラム、オブジェクト、コンポーネント、データ構造などが含まれる。通例、プログラムモジュールの機能は、各種の実施形態で必要に応じて組み合わせても、分散してもよい。
【００６３】
図３は、一実施形態におけるイメージとイメージ間の行列生成コンポーネントの処理を説明する流れ図である。ブロック３０１において、コンポーネントは、ウェブページストアに記憶されたウェブページ中のブロックを識別する。ブロック３０２において、コンポーネントは、ブロックからページへの行列生成コンポーネントを呼び出す。ブロック３０３において、コンポーネントは、ページからブロックへの行列生成コンポーネントを呼び出す。ブロック３０４において、コンポーネントは、ブロックからイメージへの行列生成コンポーネントを呼び出す。ブロック３０５において、コンポーネントは、ブロックとブロック間の行列を生成する。ブロック３０６において、コンポーネントは、イメージとイメージ間の行列を生成し、そして完了する。
【００６４】
図４は、一実施形態におけるブロックからページへの行列生成コンポーネントの処理を説明する流れ図である。ブロック４０１〜４０８において、コンポーネントは、各ページ、各ページにある各ブロック、各ブロックにある各リンクの選択をループで行い、そのリンクのリンク先であるページの、そのブロックに対する重要度を設定する。ブロック４０１において、コンポーネントは、次のページを選択する。判定ブロック４０２において、すべてのページがすでに選択されている場合は、コンポーネントは、ブロックからページへの行列を返し、そうでない場合、コンポーネントは、ブロック４０３に進行する。ブロック４０３において、コンポーネントは、選択されたページの次のブロックを選択する。判定ブロック４０４において、選択されたページのすべてのブロックがすでに選択されている場合、コンポーネントは、ブロック４０１にループして次のページを選択し、そうでない場合、コンポーネントは、ブロック４０５に進む。ブロック４０５において、コンポーネントは、選択されたブロックにあるリンクの数を数える。ブロック４０６において、コンポーネントは、選択されたブロックの次のリンクのリンク先ページを選択する。判定ブロック４０７において、選択されたブロックのリンク先ページがすでにすべて選択されている場合、コンポーネントは、ブロック４０３にループして次のブロックを選択し、そうでない場合、コンポーネントはブロック４０８に進む。ブロック４０８において、コンポーネントは、そのブロックに対するリンク先ページの重要度を設定し、ブロック４０６にループして、選択されたブロックの次のリンクのリンク先ページを選択する。
【００６５】
図５は、一実施形態におけるページからブロックへの行列生成コンポーネントの処理を説明する流れ図である。ブロック５０１〜５０６において、コンポーネントは、各ページと、各ページにある各ブロックの選択と、選択されたページに対するそのブロックの重要度の設定をループで行う。ブロック５０１において、コンポーネントは、ウェブページストアの次のページを選択する。判定ブロック５０２において、すべてのページがすでに選択されている場合、コンポーネントは、ページからブロックへの行列を返し、そうでない場合、コンポーネントは、ブロック５０３に進む。ブロック５０３において、コンポーネントは、選択されたページの次のブロックを選択する。判定ブロック５０４において、選択されたページのブロックがすでにすべて選択されている場合、コンポーネントは、ブロック５０１にループして次のページを選択し、そうでない場合、コンポーネントはブロック５０５に進む。ブロック５０５において、コンポーネントは、選択されたページに対する選択されたブロックの重要度を計算する。ブロック５０６において、コンポーネントは、選択されたページに対する選択されたブロックの重要度を設定し、ブロック５０３にループして、選択されたページの次のブロックを選択する。
【００６６】
図６は、一実施形態におけるブロックからイメージへの行列生成コンポーネントの処理を説明する流れ図である。ブロック６０１〜６０７において、コンポーネントは、各ページ、各ページにある各ブロック、および各ブロックにある各イメージの選択と、選択されたブロックに対するイメージの重要度の設定をループで行う。ブロック６０１において、コンポーネントは、ウェブページストアの次のページを選択する。判定ブロック６０２において、すでにすべてのページが選択されている場合、コンポーネントは、ブロックからイメージへの行列を返し、そうでない場合、コンポーネントは、ブロック６０３に進む。ブロック６０３において、コンポーネントは、選択されたページの次のブロックを選択する。判定ブロック６０４において、選択されたページのブロックがすでにすべて選択されている場合、コンポーネントは、ブロック６０１にループして次のページを選択し、そうでない場合、コンポーネントは、ブロック６０５に進む。ブロック６０５において、コンポーネントは、選択されたブロック中のイメージの数を数える。ブロック６０６において、コンポーネントは、選択されたブロックの次のイメージを選択する。判定ブロック６０７において、選択されたブロックのすべてのイメージがすでに選択されている場合、コンポーネントは、ブロック６０３にループして次のブロックを選択し、そうでない場合、コンポーネントは、ブロック６０８に進む。ブロック６０８において、コンポーネントは、選択されたブロックに対する選択されたイメージの重要度を設定し、ブロック６０６にループして、選択されたブロックの次のイメージを選択する。
【００６７】
本明細書では説明のためにリンク分析システムの具体的な実施形態について記載してあるが、当業者は、本発明の主旨および範囲から逸脱することなく、各種変更を加えることが可能であることを認識できよう。したがって、本発明は、特許請求の範囲によって以外は限定されない。
【図面の簡単な説明】
【００６８】
【図１】ウェブページの集まりの例におけるブロック、イメージ、およびリンクを示すブロック図である。
【図２】一実施形態のリンク分析システムにおける構成要素を示すブロック図である。
【図３】一実施形態におけるイメージからイメージへの行列生成コンポーネントの処理を説明した流れ図である。
【図４】一実施形態におけるブロックからページへの行列生成コンポーネントの処理を説明した流れ図である。
【図５】一実施形態におけるページからブロックへの行列生成コンポーネントの処理を説明した流れ図である。
【図６】一実施形態におけるブロックからイメージへの行列生成コンポーネントの処理を説明した流れ図である。
【符号の説明】
【００６９】
２００  リンク分析システム
２０１  ウェブページストア
２０２  イメージランクの計算
２０３  イメージクラスタの識別
２１１  イメージ−イメージ行列の生成
２１２  ページのブロック識別
２１３  ブロック−ページ行列の生成
２１４  ページ−ブロック行列の生成
２１５  ブロック−イメージ行列の生成
【図１】
0004634214.tif 000017
【図２】
0004634214.tif 000018
【図３】
0004634214.tif 000019
【図４】
0004634214.tif 000020
【図５】
0004634214.tif 000021
【図６】
0004634214.tif 000022