22

概要

Ted Jaspers が賢明にも指摘したように、私が 2012 年の最初の提案で説明した方法論は、実際には指数移動平均の特殊なケースです。このアプローチの優れた点は、再帰的に計算できることです。つまり、オブジェクトごとに単一の人気値を保存するだけでよく、イベントが発生したときにこの値を再帰的に調整できます。すべてのイベントを記録する必要はありません。

この単一の人気値は、過去のすべてのイベント (使用されているデータ型の制限内) を表しますが、新しいイベントが考慮されるにつれて、古いイベントは指数関数的に重要ではなくなります。このアルゴリズムは、さまざまな時間スケールに適応し、さまざまなトラフィック量に対応します。 . イベントが発生するたびに、次の式を使用して新しい人気値を計算できます。

(a * t) + ((1 - a) * p)

  • a— 0 から 1 の間の係数 (値が大きいほど、古いイベントが早く割引されます)
  • t— 現在のタイムスタンプ
  • p— 現在の人気値 (例: データベースに保存)

willの適切な値はa、アプリケーションによって異なります。ここa=2/(N+1)で、Nは結果に大きく影響するイベントの数です。たとえば、イベントがページ ビューであるトラフィックの少ない Web サイトでは、数日間で数百のページ ビューが予想される場合があります。N=100( ) を選択a≈0.02するのが妥当な選択です。トラフィックの多い Web サイトの場合、数日間で数百万のページ ビューが予想される場合があります。その場合、N=1000000( a≈0.000002) の方が合理的です。の値はa、時間をかけて徐々に調整する必要があります。

このポピュラリティ アルゴリズムがいかに単純であるかを説明するために、2 行の Twig マークアップで Craft CMS に実装する方法の例を次に示します。

{% set popularity = (0.02 * date().timestamp) + (0.98 * entry.popularity) %}
{% do entry.setFieldValue("popularity", popularity) %}

人気度を計算するために、新しいデータベース テーブルを作成したり、無限のイベント レコードを保存したりする必要がないことに注意してください。

覚えておくべき 1 つの注意点は、指数移動平均にはスピンアップ間隔があるため、値が正確であると見なされるまでに数回の再帰が必要なことです。これは、初期条件が重要であることを意味します。たとえば、新しいアイテムの人気が現在のタイムスタンプを使用して初期化されている場合、そのアイテムは、最終的により正確な位置に落ち着く前に、セット全体ですぐに最も人気のあるアイテムになります。これは、新しいコンテンツを宣伝したい場合に適しています。または、コンテンツを下から順に処理する場合、アプリケーションが最初に起動されたときのタイムスタンプでコンテンツを初期化できます。データベース内のすべての人気値の平均で値を初期化することで、満足のいく中間を見つけることもできるため、中間から開始します。

元の提案

アイテムの年齢と、アイテムが受け取る投票数、クリック数、または購入数に基づいて人気を計算するための提案されたアルゴリズムはたくさんあります。しかし、私が見たより堅牢な方法では、過度に複雑な計算と、データベースを乱雑にする複数の格納値が必要になることがよくあります。私は、変数 (人気値自体以外) を格納する必要がなく、1 つの単純な計算のみを必要とする、非常に単純なアルゴリズムを考えています。それはばかげて簡単です：

p = (p + t) / 2

ここで、p はデータベースに保存されている人気の値で、t は現在のタイムスタンプです。アイテムが最初に作成されるとき、pを初期化する必要があります。次の 2 つの初期化方法があります。

  1. 現在のタイムスタンプtでpを初期化します
  2. データベース内のすべてのp値の平均でpを初期化します

初期化方法 (1) は、最近追加されたアイテムに過去のアイテムよりも明らかな利点を与えることに注意してください。したがって、関連性の要素が追加されます。一方、初期化方法 (2) は、新しいアイテムを過去のアイテムと比較して同等に扱います。

初期化メソッド (1) を使用し、現在のタイムスタンプでpを初期化するとします。アイテムが最初の投票を受け取ると、pは作成時間と投票時間の平均になります。したがって、人気値pは引き続き有効なタイムスタンプを表します (最も近い整数に丸めると仮定します) が、それが表す実際の時間は抽象化されます。

この方法では、単純な計算が 1 つだけ必要であり、データベース ( p ) に格納する必要があるのは 1 つの値だけです。この方法は、特定のアイテムの人気が現在の時間を超えることは決してないため、値の暴走も防ぎます。

1 日間にわたって動作するアルゴリズムの例: http://jsfiddle.net/q2UCn/
1 年間にわたって動作するアルゴリズムの例: http://jsfiddle.net/tWU9y/

投票が 1 秒未満の間隔で着実に流れ込むことが予想される場合は、PHPmicrotime()関数などのマイクロ秒のタイムスタンプを使用する必要があります。それ以外の場合は、PHP 関数などの標準の UNIX タイムスタンプが機能しtime()ます。

私の質問ですが、このアプローチに大きな欠陥はありますか?

4

5 に答える 5

10

シンプルさを考えると、これは非常に良いアプローチだと思います。非常に興味深い結果です。

簡単な計算を行ったところ、このアルゴリズムは「人気」の意味を理解しているように見えることがわかりました。その問題は、次のような最近の投票を支持する明確な傾向があることです。

時間をかけて、100から1000の範囲の個別のタイムスタンプ値に分割するとします。t= 100で、AとB（2つのアイテム）の両方が同じP=100であると想定します。

    A gets voted 7 times on 200, 300, 400, 500, 600, 700 and 800
resulting on a final Pa(800) = 700 (aprox).

    B gets voted 4 times on 300, 500, 700 and 900 
resulting on a final Pb(900) = 712 (aprox).

t = 1000になると、AとBの両方が投票を受け取ります。

Pa(1000) = 850 with 8 votes
Pb(1000) = 856 with 5 votes

なんで？アルゴリズムにより、アイテムがより最近の投票を受け取った場合（アイテムの合計投票数が少ない場合でも）、アイテムが過去のリーダーをすばやく打ち負かすことができるためです。

シミュレーションを含む編集

OPは、次の結果を得るために変更した素晴らしいフィドルを作成しました。

http://jsfiddle.net/wBV2c/6/

Item A receives one vote each day from 1970 till 2012 (15339 votes)
Item B receives one vote each month from Jan to Jul 2012 (7 votes)

The result: B is more popular than A.

于 2012-06-20T21:28:00.080 に答える
3

問題が1つありますが、最後の24票までしかカウントされません。

p_i+1 = (p + t) / 2

2票の場合

p2 = (p1 + t2) / 2 = ((p0 + t1) /2 + t2 ) / 2 = p0/4 + t1/4 + t2/2

32票でそれを拡張すると、次のようになります。

p32 = t*2^-32 + t0*2^-32 + t1*2^-31 + t2*2^-30 + ... + t31*2^-1

したがって、符号付き32ビット値の場合、t0は結果に影響を与えません。t0は2^32で除算されるため、p32には何も寄与しません。

AとBの2つのアイテムがある場合（違いがどれほど大きくても）、両方が同じ32票を獲得した場合、それらは同じ人気になります。つまり、あなたの歴史はたった32票で戻ってきます。最後の32票が同じである場合、2032票と32票に違いはありません。

差が1日未満の場合、17票で等しくなります。

于 2012-06-21T09:08:10.840 に答える
1

欠点は、最近の投票が 1 票しかないものよりも、通常、100 票のものが意味を持つことです。ただし、適切に機能するスキームのバリエーションを考え出すことは難しくありません。

于 2012-06-20T21:07:57.713 に答える