News Personalization System

Google's News Personalization System Clone Project.

Initial Contributors

• Edward Yoon (R&D center, NHN corp.)

Download

• http://www.hadoop.co.kr

Algorithm Overview

• Obtain a list of candidate stories
• For each story:
  • Obtain 3 scores (y1, y2, y3)
  • Final score = ∑ wi*yi
• User clustering algorithms (Minhash (y1), PLSI (y2))
  • Score ~ number of times this story was clicked by other users in your cluster
• Story-story covisitation (y3)
  • Score ~ number of times this story was co-clicked with other stories in your recent click history
• User clustering done offline as batch process
  • Can be run every day or 2-3 times a week
• Cluster-story counts maintained in real time
• New users
  • May not be clustered
  • Rely on co-visitation to generate recommendations

NPS Architecture

                                             +----------------------------+
                                             |  Mail Frontend Web server  |
                                             +-----+---------------+------+
                                                   |       ↑       |
                                                   ACP communication
                                                   ↓       |       ↓
                          +--------------------------------+--------------+
                          |                    intermediation DB Servers  +---+
                          +----------------------------------------+------+   |
                              ↑                    ↑               |          |
                     Reads user profile       Read contents   Update contents   |
                              |                    |               ↓          |
    +-------------------------+-----+    +---------+----------------------+   |
    |       Hbase:UserTable         |    |        Hbase:MIMETable         |   |
    |     (user profile, logs)      |    |          (MIME data)           |   |
    +-------------------------------+    +--------------------------------+   |
                              ↑                   ↑                         |
+-----------------------------+--------------------+----------------------+   |
|  Hadoop: MapReduce Jobs (e.g. Log Analysis, Network Analysis, .., etc)  |←--+
+-------------------------------------------------------------------------+

Clustering Algorithms

User clustering - MinHash

• Input: User and his clicked stories

  • S_u = {s^u₁ , s^u₂ , ... , s^u_m}

• User similarity = | S_u1 I S_u2 | / | S_u1 Y S_u2 |

• Output: User clusters.
• Similar users belong to same cluster

MinHash

• Randomly permute the universe of clicked stories

  • {s^u₁ , s^u₂ , ... , s^u_m} = {s^'₁ , s^'₂ , ... , s^'_m}

• MH(u) = min(s^u_j) min defined by permutation

  • P{MH(u₁) = MH(u₂)} = | S_u1 I S_u2 | / | S_u1 Y S_u2 |

• Pseudo-random permutation
  • Compute hash for each story and treat hash-value as permutation index

• Treat MinHash value as ClusterId

• Probabilistic clustering

Clustering - PLSI Algorithm

• Learning (done offline)
  • ML estimation
    • Learn model parameters that maximize the likelihood of the sample data
    • Ouput = P[zj|u]’s P[s|zj]’s
  • P[zj|u]’s lead to a soft clustering of users
• Runtime: we only use P[zj|u]’s and ignore P[s|zj]’s

Covisitation count

• For each story si store the covisitation counts with other stories c(si, sj)
• Candidate story: sk
• User history: s1,…, sn
• score (si, sj) = c(si, sj)/∑m c(si, sm)
• total_score(sk) = ∑n score(sk, sn)

References

• Google News Personalization: Scalable Online Collaborative Filtering
• Bigtable paper: OSDI 2006