  In the domain of online advertising, our aim is to serve the best ad to a
user who visits a certain webpage, to maximize the chance of a desired action
to be performed by this user after seeing the ad. While it is possible to
generate a different prediction model for each user to tell if he/she will act
on a given ad, the prediction result typically will be quite unreliable with
huge variance, since the desired actions are extremely sparse, and the set of
users is huge (hundreds of millions) and extremely volatile, i.e., a lot of new
users are introduced everyday, or are no longer valid. In this paper we aim to
improve the accuracy in finding users who will perform the desired action, by
assigning each user to a cluster, where the number of clusters is much smaller
than the number of users (in the order of hundreds). Each user will fall into
the same cluster with another user if their event history are similar. For this
purpose, we modify the probabilistic latent semantic analysis (pLSA) model by
assuming the independence of the user and the cluster id, given the history of
events. This assumption helps us to identify a cluster of a new user without
re-clustering all the users. We present the details of the algorithm we
employed as well as the distributed implementation on Hadoop, and some initial
results on the clusters that were generated by the algorithm.
