Category similarities

Abstract

Methods, systems, and apparatus for determining similarity measures between vertical categories based on users' online activities. The similarity measures are symmetric similarity measures based on both a similarity measure of a first vertical category relative to a second vertical category and a similarity measure of the second vertical category relative to the first vertical category.

1 . A computer-implemented method, comprising:
 accessing event data for user identifiers based on past user sessions associated with the user identifiers, the event data specifying events that occurred during the past user sessions;   categorizing each of the events as belonging to one or more vertical categories;   for each vertical category and each user identifier, determining a user identifier interest weight for the user identifier based on the events associated with the vertical category;   for each pair of vertical categories, determining, by one or more processors:
 a first conditional probability that a first vertical category is similar to a second vertical category of the pair of vertical categories based at least in part on the user identifier interest weights; 
 a second conditional probability that the second vertical category is similar to the first vertical category based at least in part on the user identifier interest weights, wherein the first conditional probability is different from the second conditional probability; and 
 determining, by one or more data processors, a pair of equal similarity measures based at least in part on the first and second conditional probabilities for the first and second vertical categories of the pair of vertical categories, the pair of equal similarity measures being a first measure of similarity of first vertical category with respect to the second vertical category and a second measure of similarity of the second vertical category with respect to the first vertical category, wherein the first measure is equal to the second measure; and 
   selecting advertisements for user sessions associated with a user identifier based on the pairs of equal similarity measures.   
     
     
         2 . The method of  claim 1 , further comprising:
 identifying user identifiers that are similar based at least in part on (i) the pairs of equal similarity measures and (ii) the event data for the user identifiers.   
     
     
         3 . The method of  claim 1 , wherein determining a pair of equal similarity measures comprises:
 determining a multiplicative product of the first and second conditional probabilities;   determining that the first measure is the multiplicative product; and   determining that the second measure is the multiplicative product.   
     
     
         4 . The method of  claim 1 , wherein the events include page views of web pages, advertisement click-throughs, or conversions. 
     
     
         5 . The method of  claim 1 , further comprising:
 restricting the user identifiers to only user identifiers associated with event data that specify the event of clicking on a specific advertisement;   identifying a first vertical category to which the specific advertisement belongs;   identifying a second vertical category that is similar to the identified first vertical category based at least in part on the pair of equal similarity measures for the identified first and second vertical categories; and   targeting the specific advertisement to the identified second vertical category.   
     
     
         6 . The method of  claim 1 , wherein the first measure and the second measure are based at least in part on complementary conditional probabilities for the first and second vertical categories. 
     
     
         7 . A system, comprising:
 one or more data processors; and;   a computer-readable medium coupled to the one or more data processors having instructions stored thereon which, when executed by the one or more data processors, cause the one or more data processors to perform operations comprising:   accessing event data for user identifiers based on past user sessions associated with the user identifiers, the event data specifying events that occurred during the past user sessions;   categorizing each of the events as belonging to one or more vertical categories;   for each vertical category and each user identifier, determining a user identifier interest weight for the user identifier based on the events associated with the vertical category;   for each pair of vertical categories, determining, by one or more processors:
 a first conditional probability that a first vertical category is similar to a second vertical category of the pair of vertical categories based at least in part on the user identifier interest weights; 
 a second conditional probability that the second vertical category is similar to the first vertical category based at least in part on the user identifier interest weights, wherein the first conditional probability is different from the second conditional probability; and 
 determining a pair of equal similarity measures based at least in part on the first and second conditional probabilities for the first and second vertical categories of the pair of vertical categories, the pair of equal similarity measures being a first measure of similarity of first vertical category with respect to the second vertical category and a second measure of similarity of the second vertical category with respect to the first vertical category, wherein the first measure is equal to the second measure; and 
   selecting advertisements for user sessions associated with a user identifier based on the pairs of equal similarity measures.   
     
     
         8 . The system of  claim 7 , wherein the instructions, when executed by the one or more data processors, cause the one or more data processors to further perform operations comprising:
 identifying user identifiers that are similar based at least in part on (i) the pairs of equal similarity measures and (ii) the event data for the user identifiers.   
     
     
         9 . The system of  claim 7 , wherein determining a pair of equal similarity measures comprises:
 determining a multiplicative product of the first and second conditional probabilities;   determining that the first measure is the multiplicative product; and   determining that the second measure is the multiplicative product.   
     
     
         10 . The system of  claim 7 , wherein the events include page views of web pages, advertisement click-throughs, or conversions. 
     
     
         11 . The system of  claim 7 , wherein the instructions, when executed by the one or more data processors, cause the one or more data processors to further perform operations comprising:
 restricting the user identifiers to only user identifiers associated with event data that specify the event of clicking on a specific advertisement;   identifying a first vertical category to which the specific advertisement belongs;   identifying a second vertical category that is similar to the identified first vertical category based at least in part on the pair of equal similarity measures for the identified first and second vertical categories; and   targeting the specific advertisement to the identified second vertical category.   
     
     
         12 . The system of  claim 7 , wherein the first measure and the second measure are based at least in part on complementary conditional probabilities for the first and second vertical categories. 
     
     
         13 . A computer program product, encoded on one or more memory storage devices, including instructions that when executed by one or more data processing apparatuses cause the one or more data processing apparatuses to perform operations comprising:
 accessing event data for user identifiers based on past user sessions associated with the user identifiers, the event data specifying events that occurred during the past user sessions;   categorizing each of the events as belonging to one or more vertical categories;   for each vertical category and each user identifier, determining a user identifier interest weight for the user identifier based on the events associated with the vertical category;   for each pair of vertical categories, determining, by one or more processors:
 a first conditional probability that a first vertical category is similar to a second vertical category of the pair of vertical categories based at least in part on the user identifier interest weights; 
 a second conditional probability that the second vertical category is similar to the first vertical category based at least in part on the user identifier interest weights, wherein the first conditional probability is different from the second conditional probability; and 
 determining a pair of equal similarity measures based at least in part on the first and second conditional probabilities for the first and second vertical categories of the pair of vertical categories, the pair of equal similarity measures being a first measure of similarity of first vertical category with respect to the second vertical category and a second measure of similarity of the second vertical category with respect to the first vertical category, wherein the first measure is equal to the second measure; and 
   selecting advertisements for user sessions associated with a user identifier based on the pairs of equal similarity measures.   
     
     
         14 . The computer program product of  claim 13 , wherein the instructions, when executed by the one or more data processing apparatuses, cause the one or more data processing apparatuses to further perform operations comprising:
 identifying user identifiers that are similar based at least in part on (i) the pairs of equal similarity measures and (ii) the event data for the user identifiers.   
     
     
         15 . The computer program product of  claim 13 , wherein determining a pair of equal similarity measures comprises:
 determining a multiplicative product of the first and second conditional probabilities;   determining that the first measure is the multiplicative product; and   determining that the second measure is the multiplicative product.   
     
     
         16 . The computer program product of  claim 13 , wherein the events include page views of web pages, advertisement click-throughs, or conversions. 
     
     
         17 . The computer program product of  claim 13 , wherein the instructions, when executed by the one or more data processing apparatuses, cause the one or more data processing apparatuses to further perform operations comprising:
 restricting the user identifiers to only user identifiers associated with event data that specify the event of clicking on a specific advertisement;   identifying a first vertical category to which the specific advertisement belongs;   identifying a second vertical category that is similar to the identified first vertical category based at least in part on the pair of equal similarity measures for the identified first and second vertical categories; and   targeting the specific advertisement to the identified second vertical category.   
     
     
         18 . The computer program product of  claim 13 , wherein the first measure and the second measure are based at least in part on complementary conditional probabilities for the first and second vertical categories.