NewsPersonalizationSystem

1. News Personalization System
   1. Initial Contributors
   2. Download
2. Algorithm Overview
3. NPS Architecture
4. Clustering Algorithms
   1. User clustering - MinHash
      1. MinHash
   2. Clustering - PLSI Algorithm
   3. Covisitation count
5. References

---

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