検索エンジン技術のランキングアルゴリズムを解読する

[[117973]]

1. ページランク

PageRank は、世界で最も人気のある検索エンジンである Google が採用しているアルゴリズム戦略です。各 Web ページのハイパーリンク情報に基づいて Web ページの重みを計算し、検索エンジンの結果を最適化するために使用されます。ラリー・ペイジ氏によって提案されました。

簡単に言えば、PageRank アルゴリズムは各 Web ページの総合スコアを計算します。つまり、Web ページ A が Web ページ B にリンクしている場合、Web ページ B は 1 ポイントを獲得します。リンク先のウェブページは、リンク先のウェブページごとに異なるポイントが与えられます。ページのスコアは、そのページにリンクしているすべてのページの重要度に基づいて再帰アルゴリズムによって算出されます。

PageRank アルゴリズムの基本原理は次のように導き出されます。

PR(A) = (1-d) + d*(PR(T ₁ )/C(T ₁ ) + ... + PR(T _n )/C(T _n ))

このうち、PR(A)はWebページAのPR値を指します。

T1 _、 T2 _、 ...、 _{Tn は、} Web ページ A からリンクされている Web ページを参照します。

PR(T _i )はWebページT _i (i=1, 2, ..., n)のPR値を表します。

C(T _i )はWebページT _i (i=1, 2, ..., n)のアウトバウンドリンクの数を表します。

D は減衰係数で、0<d<1 であり、通常は 0.85 とされます。

上記の式から、Web ページの PR 値に影響を与える主な要因は次のようになります。

• （１）ウェブページへのインバウンドリンクの数。
• （２）このウェブページにリンクしているウェブページのページランク値。
• （３）ウェブページにリンクしているウェブページからのアウトバウンドリンクの数。

上記の分析に基づいて、Web ページのインバウンド リンクが多いほど、これらのインバウンド リンクの PR 値が高くなり、これらの Web ページ自体のアウトバウンド リンクが少ないほど、Web ページの PR 値が高くなると判断できます。

Google は各 Web ページに初期 PR 値 (1-d) を割り当て、その後 PageRank アルゴリズムを使用して PR 値を収束および計算します。

ウェブページのインバウンドリンクとアウトバウンドリンクの関係は常に変化するため、PR 値も更新する必要があります。スケジュールされたタスクを使用して、ウェブページの最終的な PR 値がバランスのとれた安定した状態になるように、繰り返し計算と更新を行うことができます。

Google のクエリ プロセスは次のとおりです。まず、ユーザーが入力したクエリ キーワードに従って Web データベース内の Web ページを照合し、次に、一致した Web ページを独自の PR ランキングに従ってユーザーに提示します。

さらに、検索結果リスト内の Web ページの位置は、Web ページ内の検索語の位置など、他の多くの要因にも関連しています。

PageRank の欠点は、リンクの価値を考慮しないことです。これは一般的な検索エンジンには適していますが、トピック関連の垂直検索エンジンには適した戦略ではありません。

ヒット

PageRank アルゴリズムは、外部リンクの重みの貢献を平均化します。つまり、異なるリンクの重要性は考慮されません。ただし、ページ リンクの一部は広告、ナビゲーション、または注釈リンクである可能性があり、平均重みは明らかに実際の状況と一致しません。

HITS (Hyperlink Induced Topic Search) アルゴリズムは、垂直精度を向上できる古典的なテーマ情報抽出戦略です。

1. 原則

HITS アルゴリズムは Jon Kleinberg によって提案されました。各 Web ページのオーソリティとハブの 2 つの値を計算します。

（１）権威あるウェブページ

ウェブページが複数回引用されている場合、そのウェブページは非常に重要である可能性があります。また、ウェブページが複数回引用されていない場合でも、重要なウェブページによって引用されている場合は、非常に重要である可能性があります。ウェブページの重要性は、引用先のウェブページに均等に伝達されます。このタイプの Web ページは、権威のある Web ページと呼ばれます。

（２）ハブウェブページ

権威ある Web ページへのリンクのコレクションを提供する Web ページは、それ自体は重要ではないか、またはそれを指す Web ページがほとんどないかもしれませんが、特定のトピックに関する最も重要なサイトへのリンクのコレクションを提供します。このような Web ページはハブ ページと呼ばれます。

（３）アルゴリズム思考

まず、一般的な検索エンジンを使用して、Web ページの初期サブセット I を取得します。もちろん、I 内のページはすべて、ユーザーのクエリ条件に非常に関連しています。次に、I が指す Web ページと I を指している Web ページを含めて、基本セット E を形成します。E 内の各ページには、それぞれ a と h で示される権威重みとハブ重みがあります。a の値は、クエリ条件に対する Web ページの関連性を示し、h は、ページによってリンクされている関連ページの数を反映します。 a=(a ₁ , a ₂ , ..., a _n ) および h=(h ₁ , h ₂ , ..., h _n ) は、E 内のすべての Web ページのオーソリティ ベクトルとハブ ベクトルを表します。最初に、すべての a _iと h _{i は}1 に設定され、計算には次の式が使用されます。

このうち、B(i)とF(i)はそれぞれ、Webページを指すWebページリンクのセットと、Webページによって指されるWebページリンクのセットを表します。 n*n 行列 A を使用して、セット E 内の Web ページ ノード間の接続を表します。ノード i とノード j の間に接続がある場合、A[i,j]=1、A[i,j]=0 になります。したがって、上記の式は次のように表すことができます。

収束するまで a と h を繰り返し計算します。したがって、 A ^T A と AA ^{T を}見つけることに焦点を当てます。 *** 権威とハブの値で並べ替え、a 値と h 値がしきい値 M より大きい Web ページを選択します。

ウェブページが多くの優れたハブによって参照されている場合、その権威値はそれに応じて増加します。また、ウェブページが多くの優れた権威ページを参照している場合、ハブ値もそれに応じて増加します。 HITS アルゴリズムは、ハブ値が大きい Web ページとオーソリティ値が大きい Web ページのセットを出力します。

2. 欠陥

HITS アルゴリズムは垂直精度をある程度向上させますが、次のような欠点もあります。

（1）HITSアルゴリズムは、ウェブページの内容の違いを無視し、リンクされた各ウェブページに同じ重み定数を割り当てます。これは、各ウェブページには広告リンクなどの無関係なリンクされたウェブページが含まれているためです。これらの無関係なウェブページを関連するウェブページと同じように扱うと、トピックドリフトに簡単につながる可能性があります。

（２）URLセットEが最初に形成されるとき、初期セットIのウェブページの無関係なリンクもEに追加され、不要なダウンロードの量が増加し、より多くの無関係なウェブページが計算に参加することになり、精度に一定の影響を与えます。

3. 改善点

改善の方向性は以下のとおりです。

（１）トピックドリフト

（２）ダウンロードフィルタリング

オリジナルリンク: http://blog.chinaunix.net/uid-22312037-id-4408642.html