Instagram的熱門趨勢發現算法

jopen 9年前發布 | 10K 次閱讀 算法

不久前，照片分享應用 Instagram 推出了搜索與瀏覽功能。瀏覽頁面上的熱門標簽和地點是社區中一些最受歡迎的內容，而其背后是一個每天可以解析 7000 多萬張新增圖片的系統。近日，Instagram 技術博客介紹了支撐該系統的熱門趨勢發現算法。

直觀地講，熱門標簽是一個比平時用得多的標簽，而這種情況是由那個時刻發生的特定事件所導致。比如，在 Instagram 撰寫那篇博文時，#equality 就是一個熱門標簽，即當時有許多人用它分享圖片：

Instagram的熱門趨勢發現算法

趨勢識別

通過標簽熱度變化可以識別趨勢。Instagram 認為，一個良好的趨勢要具備三個要素：

  • 流行度——社區中要有許多人對該趨勢感興趣

  • 新穎性——該趨勢是關于一些新東西

  • 時效性——該趨勢是在真實事件發生時出現在 Instagram 上的
    • </ul>

    識別趨勢需要量化當前觀察到的活動（分享照片和視頻的數量）與預期活動的差異。如果前者高于后者，就可以確定某個趨勢。比如上文提到的標 簽#equality，通常每個小時只有幾張照片及視頻用到它。但從太平洋時間上午 7 點開始，有數以千計的人用它分享內容。就是說，活動多于預期，標簽#equality 代表一種趨勢。

    對于每個標簽和地點，他們會記錄過去七天中每五分鐘內有多少媒質在分享時用到了它，該數量表示為C(h, t)，即標簽h在時間點t的計數（也就是，在t-5 到t時段里以h作為標簽的帖子數量）。由于該計數在不同的標簽或不同的時點之間差別很大，所以將其規范化為在時點t觀察到h的概率P(h, t)。此外，他們還構建了一個模型，用于計算預期數量C’(h, t)，并得出預期概率P’(h, t)。現在，就可以使用一種常見的概率差異度量方法“KL 散度（KL divergence）”計算實際概率與預期概率的差異，公式如下：

    S(h, t) = P (h, t) * ln (P(h, t)/P’(h, t))

    </blockquote>

    其中，P(h, t)可以體現流行度，P(h, t)/P’(h, t)可以體現新穎性，而t則體現出時效性。

    趨勢預測

    預測是指根據過去的觀察計算預期基準概率。在這個過程中，需要權衡準確性與計算的時空復雜度。通常，準確性會與時空復雜度呈一定的正比關系。他 們測試了不同的可選方案，包括取上周同一時間的計數、回歸模型、神經網絡。最終，他們選擇使用上周測量值中的最大概率，這有如下好處：

    • 容易計算，內存需求相對較低

    • 可以抑制具有高方差的非趨勢

    • 可以快速識別新興的趨勢
      • </ul>

      這里有兩點需要說明一下。一是，由于大多數標簽在五分鐘內的計數都非常小，甚至為0，所以他們在計算舊的計數時以小時為單位，而且他們會查看幾 個小時的數據，以最小化隨機使用高峰的干擾。二是，如果某個標簽過去沒有出現過，那么他們會將該標簽在那個時間窗口內的計數置為3，依據是大多數標簽在一 個小時出現次數都不超過3。

      趨勢排列

      這一步是根據 KL 散度值S(h, t)排列標簽。他們發現，部分趨勢消失地很快，但實際上仍然有人對其感興趣。為了解決這個問題，他們引入了指數衰減函數，用它定義趨勢的生存期。S(h, tmax)=SM (h)表示標簽h在時點 tmax 時取得最大 KL 散度值，則其指數衰減值為：

      Sd (h, t) = SM (h) * (?)^((t - tmax)/half-life)

      </blockquote>

      其中，衰減參數“半衰期（half-life）”為 2 小時，是指SM (h)每過兩個小時就會減半。

      趨勢聚合

      通常，人們會用多個標簽描述同一事件，當一個事件熱門時，描述該事件的多個標簽都會成為趨勢。因此，需要將這些概念上相同的標簽聚合成一個趨 勢。這有兩個方面的工作：一是識別出談論同一事件的標簽，二是找出最能代表該事件的標簽。對于第一項，他們通過以下維度計算標簽相似度：

      • 共現率——在最近的媒質中，一個標簽同其它標簽一起出現的次數。

      • 編輯距離——同一標簽的不同拼寫（或錯別字），通過 Levenshtein 距離來計算。

      • 主題分布——描述同一事件、但拼寫不同（如#gocavs、#gowarriors）的標簽不大可能一起出現。他們將標題中的標簽通過一個內部工具分類到一組預定義的主題中。然后計算每個標簽的主題分布，并使用 TF-IDF 將其標準化。
        • </ul>

        趨勢聚合過程即是根據每一對趨勢標簽的相似度將它們分組。

        系統設計

        他們將趨勢發現后臺設計成一個有四個節點的流處理應用程序，如下圖所示：

        Instagram的熱門趨勢發現算法

        每個節點都有特定的作用：

        • pre-processor——從原始媒質中抽取所需數據。

        • parser——抽取描述照片或視頻的標簽或地點，并過濾。

        • scorer——統計每個趨勢在某個時段內的出現次數，并計算 KL 散度值S(h, t)。

        • ranker——將所有的候選趨勢聚合并排序。
          • </ul>

          該系統需要實時處理大量數據，并具有高效和容錯特性。上述線性架構使他們可以將趨勢劃分，并啟動每個節點的多個實例，實現并行處理。而且，某個劃分或實例出現問題都不會影響整個系統。

          上面討論的是趨勢發現過程，而發現的趨勢通過下圖所示的方式提供給應用請求：

          Instagram的熱門趨勢發現算法

          可以看出，來自 Instagram 應用的趨勢標簽和地點請求不會增加趨勢發現后臺的負載，因為應用的請求是由 memcached 緩存和 Postgres 數據庫提供，其中數據庫中存儲了 ranker 的計算結果。

          后續，他們考慮將該項目分解成多個更小的問題，每個問題由具有特定功能的組件單獨處理。這樣，他們團隊中的每個人就可以一次只關注一個問題。

          來自: InfoQ
           本文由用戶 jopen 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。
           轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。
           本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！
            本文地址：http://www.baiduhome.net/news/view/c45133