HITSアルゴリズム

ハイパーリンク誘導トピック検索（HITS 、ハブとオーソリティとも呼ばれる）は、ジョン・クラインバーグによって開発された、ウェブページを評価するリンク分析アルゴリズムです。ハブとオーソリティの背後にあるアイデアは、インターネットが最初に形成されたときのウェブページの作成に関する特定の洞察に由来しています。つまり、ハブと呼ばれる特定のウェブページは、実際には保持している情報の権威ではない大規模なディレクトリとして機能していましたが、ユーザーを他の権威のあるページに直接誘導する広範な情報カタログの編集として使用されていました。言い換えれば、優れたハブは他の多くのページを指し示すページを表し、優れたオーソリティは多くの異なるハブによってリンクされているページを表します。[ 1 ]

したがって、このスキームでは、各ページに 2 つのスコアを割り当てます。ページのコンテンツの価値を推定する権威と、他のページへのリンクの価値を推定するハブ値です。

歴史

ジャーナルにおいて

科学雑誌の重要性をランク付けするために、多くの方法が使用されてきました。そのような方法の1つは、ガーフィールドのインパクトファクターです。ScienceやNatureなどのジャーナルは多数の引用で満たされているため、これらの雑誌は非常に高いインパクトファクターを持っています。したがって、ほぼ同じ数の引用を受けている2つのあまり知られていないジャーナルを比較する場合、これらのジャーナルの1つがScienceとNatureから多くの引用を受けている場合、このジャーナルをより高いランクにする必要があります。言い換えれば、重要なジャーナルから引用を受ける方が、重要でないジャーナルから引用を受けるよりも良いということです。[ 2 ]

ウェブ上

この現象はインターネットでも発生します。ページへのリンク数を数えることで、ウェブ上でのそのページの知名度を大まかに推定できますが、Yahoo!、Google、MSNなどのサイトのホームページからのリンクが2つある場合、リンク数が非常に少ないページでも目立つ可能性があります。これらのサイトは非常に重要でありながら検索エンジンでもあるため、ページは実際の関連性よりもはるかに高い順位に表示されることがあります

アルゴリズム

ルートセットをベースセットに拡張する

手順

HITSアルゴリズムの最初のステップは、検索クエリに最も関連性の高いページを取得することです。このセットはルートセットと呼ばれ、テキストベースの検索アルゴリズムによって返される上位のページを取得することで取得できます。ルートセットに、そこからリンクされているすべてのウェブページと、ルートセットにリンクされている一部のページを追加することで、ベースセットが生成されます。ベースセット内のウェブページと、それらのページ間のすべてのハイパーリンクは、フォーカスされたサブグラフを形成します。HITSの計算は、このフォーカスされたサブグラフに対してのみ実行されます。Kleinbergによると、ベースセットを構築する理由は、最も強力なオーソリティのほとんど（または多く）を確実に含めるためです。

オーソリティ値とハブ値は相互再帰によって定義されます。オーソリティ値は、そのページを指すスケーリングされたハブ値の合計として計算されます。ハブ値は、そのページが指すページのスケーリングされたオーソリティ値の合計です。実装によっては、リンクされたページの関連性も考慮されます。

アルゴリズムは一連の反復を実行し、各反復は次の 2 つの基本ステップで構成されます。

  • オーソリティの更新：各ノードのオーソリティスコアを、そのノードを指す各ノードのハブスコアの合計と等しくなるように更新します。つまり、情報のハブとして認識されているページからリンクされているノードには、高いオーソリティスコアが与えられます。
  • ハブ更新：各ノードのハブスコアを、そのノードがリンクしている各ノードのオーソリティスコアの合計と等しくなるように更新します。つまり、あるノードは、その主題のオーソリティとみなされるノードにリンクすることで、高いハブスコアを獲得します。

ノードのハブ スコアと権限スコアは、次のアルゴリズムで計算されます。

  • 各ノードのハブ スコアと権限スコアが 1 の状態から開始します。
  • 権限更新ルールを実行する
  • ハブ更新ルールを実行する
  • 各 Hub スコアをすべての Hub スコアの二乗の合計の平方根で割り、各 Authority スコアをすべての Authority スコアの二乗の合計の平方根で割って、値を正規化します。
  • 必要に応じて 2 番目の手順から繰り返します。

PageRankとの比較

HITSは、PageとBrinのPageRankと同様に、ウェブ上の文書のリンクに基づく反復アルゴリズムです。しかし、いくつか大きな違いがあります

  • これは、PageRank の場合のようにすべてのドキュメントのセットではなく、「関連」ドキュメントの小さなサブセット (「フォーカスされたサブグラフ」または基本セット) に対して処理されます。
  • これはクエリに依存します。異なるクエリに対して表示される異なるベースセットが指定されると、同じページでも異なるハブ/権限スコアが付与されることがあります。
  • 当然のことながら、インデックス作成時ではなくクエリ時に実行する必要があり、クエリ時の処理に伴うパフォーマンスの低下を伴います。
  • 単一のスコアではなく、ドキュメントごとに 2 つのスコア (ハブとオーソリティ) を計算します。
  • これは検索エンジンでは一般的に使用されていません (ただし、 Ask Jeeves/Ask.comに買収されたTeomaでは同様のアルゴリズムが使用されていたと言われています)。

詳細

ランキング付けを開始するには、各ページについてととします。2種類の更新、つまり権威更新ルールとハブ更新ルールを検討します。各ノードのハブ／権威スコアを計算するために、権威更新ルールとハブ更新ルールを繰り返し適用します。ハブ権威アルゴリズムのkステップ適用では、最初に権威更新ルールをk回適用し、次にハブ更新ルールをk回適用します あうとひ（ぷ）＝1{\displaystyle \mathrm {auth} (p)=1}ひうb（ぷ）＝1{\displaystyle \mathrm {ハブ} (p)=1}ぷ{\displaystyle p}

オーソリティ更新ルール

各 について、に更新します。ここではページ にリンクしているすべてのページです。つまり、ページのオーソリティスコアは、そのページを指しているすべてのページのハブスコアの合計です ぷ{\displaystyle p}あうとひ（ぷ）{\displaystyle \mathrm {auth} (p)}あうとひ（ぷ）＝∑q∈Pとoひうb（q）{\displaystyle \mathrm {auth} (p)=\displaystyle \sum \nolimits _{q\in P_{\mathrm {to} }}\mathrm {hub} (q)}Pとo{\displaystyle P_{\mathrm {to} }}ぷ{\displaystyle p}

ハブ更新ルール

各について、に更新します。ここで、 はページがリンクしているすべてのページです。つまり、ページのハブスコアは、そのページがリンクしているすべてのページのオーソリティスコアの合計です ぷ{\displaystyle p}ひうb（ぷ）{\displaystyle \mathrm {ハブ} (p)}ひうb（ぷ）＝∑q∈Pfromあうとひ（q）{\displaystyle \mathrm {hub} (p)=\displaystyle \sum \nolimits _{q\in P_{\mathrm {from} }}\mathrm {auth} (q)}Pfrom{\displaystyle P_{\mathrm {from} }}ぷ{\displaystyle p}

正規化

ノードの最終的なハブ・オーソリティスコアは、アルゴリズムを無限に繰り返した後に決定されます。ハブ更新ルールとオーソリティ更新ルールを直接反復適用すると値が発散するため、反復ごとに行列を正規化する必要があります。したがって、このプロセスから得られる値は最終的に収束します

擬似コード

G := G内の各ページpについて、 ページ集合を実行する p.auth = 1 // p.authはページpのオーソリティスコアp.hub = 1 // p.hubはページpのハブスコア（ 1からkまでのステップ）do // kステップでアルゴリズムを実行する ノルム = 0 G内の各ページpに対して 、まずすべての権限値を更新します。p .auth = 0 を p.incomingNeighbors内の各ページqに対して実行します。//p.incomingNeighborsはpにリンクするページのセットです。p .auth += q .hub norm += square( p .auth) // 正規化するために二乗された認証値の合計を計算する ノルム = sqrt(ノルム) Gの各ページpに対して 、認証スコアを更新します。p .auth = p .auth / norm // 認証値を正規化します。 ノルム = 0 G内の各ページpに対して、次の処理を実行します // 次に、すべてのハブ値を更新します p .hub = 0 p.outgoingNeighbors内の各ページrに対して、次の処理を実行します// p.outgoingNeighborsは、 pがリンクする ページのセットですp .hub += r .auth norm += square( p .hub) // 正規化するためにハブ値の二乗の合計を計算する ノルム = sqrt(ノルム) Gの各ページpに対して、次の操作を実行します // 次に、すべてのハブ値を更新します p .hub = p .hub / norm // ハブ値を正規化します

上記の疑似コードでは、ハブと権限の値が収束しています。

以下のコードは収束しません。これは、アルゴリズムの実行ステップ数を制限する必要があるためです。しかし、これを回避する一つの方法は、各「ステップ」の後にハブ値とオーソリティ値を正規化することです。正規化とは、オーソリティ値をすべてのオーソリティ値の平方和の平方根で割り、ハブ値をすべてのハブ値の平方和の平方根で割ることです。上記の擬似コードはまさにこれを行っています。

収束しない擬似コード

G  := G内の各ページpについて、 p.auth = 1とします// p.authはページpのオーソリティスコアですp.hub = 1 // p.hubはページpのハブスコアですfunction HubsAndAuthorities( G ) for step from 1 to k do // k ステップのアルゴリズムを実行します。 各ページp in Gを実行します 。// 最初にすべての権限値を更新します 。p .auth = 0 です。各ページq in p.incomingNeighborsを実行します。// p.incomingNeighbors は、 p にリンクするページのセットです。p .auth += q .hub です。各ページp in Gを実行します 。// 次に、すべてのハブ値を更新します 。p .hub = 0 です。各ページr in p.outgoingNeighborsを実行します。// p.outgoingNeighbors は、 pがリンクする ページのセットです。p .hub += r .auth

参照

参考文献

  1. ^ Christopher D. Manning、Prabhakar Raghavan、Hinrich Schütze (2008). 「情報検索入門」ケンブリッジ大学出版局. 2008年11月9日閲覧
  2. ^ Kleinberg, Jon (1999年12月). 「ハブ、権威、そしてコミュニティ」コーネル大学. 2008年11月9日閲覧。
「 https://en.wikipedia.org/w/index.php?title=HITS_algorithm&oldid=1318782443」より取得