Scalable user clustering based on set similarity

Abstract

Methods and apparatus, including systems and computer program products, to provide clustering of users in which users are each represented as a set of elements representing items, e.g., items selected by users using a system. In one aspect, a program operates to obtain a respective interest set for each of multiple users, each interest set representing items in which the respective user expressed interest; for each of the users, to determine k hash values of the respective interest set, wherein the i-th hash value is a minimum value under a corresponding i-th hash function; and to assign each of the multiple users to each of the respective k clusters established for the respective user, the i-th cluster being represented by the i-th hash value. The assignment of each of the users to k clusters is done without regard to the assignment of any of the other users to k clusters.

Description

technical field [0001] The present invention relates to digital data processing, and more particularly to grouping users of computer applications or systems into clusters. Background technique [0002] The operation of grouping users into clusters serves several purposes. To achieve user personalization, for example, a well-known technique, collaborative filtering, involves clustering users and recommending to users items that other users in the user cluster have expressed interest in. A user may generally be considered to express interest in an item in a variety of ways, for example, by clicking on the item, purchasing the item, or adding the item to a shopping cart. Recommendations can be presented in many ways, such as presenting to users in the form of partial search results, presenting in the form of news stories that users may want to read, identifying items that users may want to buy, and so on. [0003] One way to achieve user clustering is to first define a distan...

AI Technical Summary

Problems solved by technology

However, these techniques have disadvantages

For example, the running time of HAC is O(n 2 ), which is difficult to achieve for hundreds of millions of values ​​of n; and the k-means algorithm needs to represent the mean of the data points, which is not feasible when the data points are sets

Images