Abstract:
A facility for identifying users that have an interest in a selected subject is described. For each of a number of actual users, the facility establishes a user behavior record describing the behavior of the actual user. The facility also establishes a user behavior record describing behavior of a virtual user. The behavior described by the user behavior record for the virtual user is made up of actions each tending to indicate an interest in the selected subject. The facility identifies a proper subset of the actual users whose user behavior records are most similar to the user behavior record of the virtual user as interested in the selected subject.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     This application is a continuation of U.S. patent application Ser. No. 11/107,405, filed Apr. 14, 2005, which is hereby incorporated by reference in its entirety. 
    
    
     TECHNICAL FIELD 
     The described technology is directed to the field of analyzing user behavior. 
     BACKGROUND 
     The process of advertising involves presenting advertising messages for a cause, such as the purchase of a product or service, to people. Advertising messages can be presented via a variety of channels, including television, print periodicals, postal mail, billboards, web pages, and electronic mail. 
     Depending upon the type of channel used for particular advertising and the specific technology that supports that channel, advertising may be targeted at different levels to specific people or groups of people. For example, in some cases, advertising presented on web pages can be targeted to specific people or groups of people. 
     Targeting advertising to particular people can provide advantages, including (1) increasing the average level of relevancy of an advertising message to the people that receive it, (2) ensuring that the advertising message is seen by the people most likely to be receptive to it, and (3) reducing the total cost of advertising by reducing the number of people to whom the message is presented. One approach to targeting advertising is population segmentation, in which groups of people are created that have common characteristics, and that are likely to be receptive to advertising messages directed to particular subjects. 
     Conventional approaches to defining segments within a population of people begin by collecting a body of profile information about each person in the population, such as information characterizing the person&#39;s web browsing activity, as well as other demographic or biographical information for the person. A user builds a query against this profile information, which is executed to identify the people in the segment, referred to as “populating” the segment. 
     While such conventional approaches to defining segments can often be completely effective at selecting the people intended by the user defining the segment, they are often difficult to use. Such a user must understand all of the information available in the profiles, understand the set of tests available in the query engine, and understand how to assemble these into a query. This process often requires the use of a fairly involved user interface. As a result, such conventional approaches are typically used only by a small number of very sophisticated users, and are very seldom used by users—such as front-line marketing and advertising personnel—who have the greatest capacity to identify and refine characteristics likely to make a person receptive to a particular cause or advertising message. 
     In view of the shortcomings of conventional segment definition techniques, a new approach to segment definitions that enabled a larger group of users to more easily and/or more effectively define segments of users who are interested in a particular subject would have significant utility. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a block diagram showing some of the components typically incorporated in at least some of the computer systems and other devices on which the facility executes. 
         FIG. 2  is a flow diagram showing steps typically performed by the facility in order to identify users having an interest in the subject. 
         FIG. 3  is a flow diagram showing steps typically performed by the facility to identify users interested in the subject based upon the set of selected actions. 
         FIG. 4  is a conceptual diagram showing an example of identifying users whose actions are most similar to the virtual user&#39;s actions using a cohort-matching technique. 
         FIG. 5  is a flow diagram showing steps typically performed by the facility in order to determine a ranking of users that reflects the user&#39;s relative level of interest in the subject, from which users interested in the subject can be identified. 
         FIG. 6  is a table diagram showing sample contents of a user behavior table documenting the behavior of a group of users. 
         FIG. 7  is a table diagram showing sample contents of a user ranking table generated by the facility in some embodiments based upon the contents of the user behavior table. 
     
    
    
     DETAILED DESCRIPTION 
     A facility for identifying users interested in a subject based upon their behavior (“the facility”) is described. In some embodiments, the facility selects a set of available actions that together demonstrate a very high level of interest in the subject. As one example, where users are able to request pages from a particular web site, the facility searches the web site for pages containing query terms that relate to the subject. The facility then selects actions for requesting pages of the web site that appear in the search result as demonstrating a very high level of interest in the subject. The facility uses the selected set of actions to identify users interested in the subject based upon comparing the actions performed by the user to the selected set of actions. 
     In some embodiments, the facility attributes the selected set of actions to a “virtual user”—that is, in an environment that indicates for each of a number of actual users the set of actions performed by those users, the facility creates an artificial user that is indicated to have performed all of the selected actions. The facility then applies cohort matching techniques—such as item recommendation techniques, user correlation techniques, or autosegmentation techniques—to identify the actual users that are most similar to the virtual user based upon a comparison of the actions that they have performed. The facility identifies these users as being interested in the subject. 
     In some embodiments, the facility applies an approach in which it determines a ranking of users that reflects the users&#39; relative level of interest in the subject. The most significant component of the ranking is the number of times that the user performed any selected action. For example, where two actions are selected by the facility, a first user who performed the first selected action 4 times would be ranked more highly than a second user who performed the first selected action once and the second selected action twice. For users that performed the same total number of selected actions, the facility ranks more highly users that performed a larger number of distinct selected actions. For example, a third user who performed the first selected action once and the second selected action once would be ranked more highly than a fourth user who performed the first selected action twice. For users that performed the same total number of selected actions and distinct selected actions, the facility ranks more highly users that performed a smaller number of distinct unselected actions. For example, a fifth user who performed the first selected action once, the second selected action once, and a first unselected action three times would be ranked more highly than a sixth user who performed the first selected action once, the second selected action once, the first unselected action once, and a second unselected action once. For users that performed the same total number of selected actions, distinct selected actions, and distinct unselected actions, the facility ranks more highly users that performed a smaller number of total unselected actions. For example, a seventh user who performed the first selected action once, the second selected action once, the first unselected action once, and the second unselected action once would be ranked more highly than a eight user who performed the first selected action once, the second selected action once, the first unselected action twice, and the second unselected action three times. 
     By identifying users interested in a subject in some or all of the ways described above, the facility enables advertisers for products and services related to the subject and other promoters for promotions relating to the subject to focus their resources on users who are likely to respond. 
       FIG. 1  is a block diagram showing some of the components typically incorporated in at least some of the computer systems and other devices on which the facility executes. These computer systems and devices  100  may include one or more central processing units (“CPUs”)  101  for executing computer programs; a computer memory  102  for storing programs and data—including data structures—while they are being used; a persistent storage device  103 , such as a hard drive, for persistently storing programs and data; a computer-readable media drive  104 , such as a CD-ROM drive, for reading programs and data stored on a computer-readable medium; and a network connection  105  for connecting the computer system to other computer systems, such as via the Internet, to exchange programs and/or data—including data structures. While computer systems configured as described above are typically used to support the operation of the facility, one of ordinary skill in the art will appreciate that the facility may be implemented using devices of various types and configurations, and having various components. 
     While various embodiments are described in terms of the environment described above, those skilled in the art will appreciate that the facility may be implemented in a variety of other environments including a single, monolithic computer system, as well as various other combinations of computer systems or similar devices connected in various ways. 
       FIG. 2  is a flow diagram showing steps typically performed by the facility in order to identify users having an interest in the subject. In step  201 , from a universe of available actions, the facility selects a set of actions that demonstrate an interest in the subject when performed by the user. For example, where users are able to request pages from a web site, the facility may select request actions for particular pages relating to the subject in step  201 . For example, the facility may identify these pages by searching for pages of the web site that contain query terms that relate to the subject. In some embodiments, the facility considers other kinds of web browsing actions, such as using a mortgage calculator or automobile configurer, entering certain information into a form, selecting a particular user interface control displayed on a web page, etc. In some embodiments, the facility considers other types of user behavior actions, such as actions involved in watching television or other video sequences, listening to radio or other audio sequences, renting or going to movies, etc. In various embodiments, the facility uses techniques such as those described in the following two patent applications, each of which is hereby incorporated by reference in its entirety: U.S. patent application Ser. No. 10/859,442, filed on Jun. 1, 2004, and U.S. patent application Ser. No. 11/048,985 filed on Feb. 1, 2005. In step  202 , as described in further detail below, the facility uses the actions selected in step  201  to identify users interested in the subject. After step  202 , these steps conclude. 
     Those skilled in the art will appreciate that the steps shown in  FIG. 2  and in each of the flow diagrams discussed below may be altered in a variety of ways. For example, the order of the steps may be rearranged; substeps may be performed in parallel; shown steps may be omitted, or other steps may be included; etc. 
       FIGS. 3 and 4  show a “virtual user” approach to identify users interested in the subject based upon the set of selected actions.  FIG. 3  is a flow diagram showing steps typically performed by the facility to identify users interested in the subject based upon the set of selected actions. In step  301 , the facility creates a virtual user by creating an indication of a new user. In step  302 , the facility attributes the actions selected in step  201  to the virtual user created in step  301 . In step  303 , the facility applies one or more cohort-matching techniques to identify users whose actions are most similar to those of the virtual user. In various embodiments, the facility uses cohort-matching techniques in step  303  such as item recommendation techniques, user correlation techniques, or auto-segmentation techniques. As one example, the techniques described in U.S. patent Ser. No. 09/629,252, filed on Jul. 27, 2000, which is hereby incorporated by reference in its entirety, may be used. After step  303 , these steps conclude. 
       FIG. 4  is a conceptual diagram showing an example of identifying users whose actions are most similar to the virtual user&#39;s actions using a cohort-matching technique. The diagram shows a behavior universe  400  containing indications of each monitored user&#39;s behavior. The indications for actual users are shown as circled As. The indication of the virtual user is shown as a circled V. Those skilled in the art will appreciate that a user&#39;s behavior may vary in a number of dimensions that is much larger than the two dimensions that are available to illustrate in the diagram. It can be seen that a behavior indication of actual users occur at varying distances from the behavior indication of the virtual user. The facility selects a subset  401  of the actual users whose behavior is the closest to that of the virtual user, and identifies these actual users as being interested in the subject. In various embodiments, the facility uses a variety of techniques to select the subset of actual users, such as choosing a radius about the virtual user that contains a predetermined percentage of the actual users; describing a non-circular region about the virtual user that contains a predetermined percentage of the actual users; selecting a “cluster” of actual users about the virtual user that is separated from the unselected actual users by a certain amount of unoccupied margin space; etc. 
     The facility uses a variety of approaches to determining distances between the virtual user and each actual user. In some embodiments, the facility applies a linear correlation approach. For each actual user, the number of actions performed by neither the virtual user nor the actual user—associated by the facility with the point (0, 0); the number of actions performed by the virtual user, but not the actual user—associated by the facility with the point (1, 0); the number of actions performed by the actual user but not the virtual user—associated by the facility with the point (0, 1); and the number of actions performed by both the virtual user and the actual user—associated by the facility with the point (1, 1). The facility applies each of these values as a weight to the corresponding point, and determines a linear least-squares estimator that includes both a mean value and a variance value. The facility then computes a single score or rank that, as a first matter, values a high mean, and, as second matter, values a low variance. 
     In some embodiments, the facility uses a relative entropy approach by determining the Kullback-Leibler distance d from a distribution of the virtual user&#39;s actions q k  to a distribution of the actual user&#39;s actions p k : 
                   d   =       ∑   k             ⁢           ⁢       p   k     ⁢           ⁢       log   2     ⁡     (       p   k       q   k       )                   (   1   )               
Those skilled in the art will appreciate that the facility could use a number of other such approaches.
 
       FIGS. 5-7  illustrate the approach of determining a ranking of users that reflects the user&#39;s relative level of interest in the subject.  FIG. 5  is a flow diagram showing steps typically performed by the facility in order to determine a ranking of users that reflects the user&#39;s relative level of interest in the subject, from which users interested in the subject can be identified. In some embodiments, the facility applies the steps shown in  FIG. 5  to each pair of users in order to determine which user of the pair should be more highly ranked. In step  501 , if the total number of selected actions performed by the two users is equal, then the facility continues in step  503 , else the facility continues in step  502 . In step  502 , the facility ranks more highly the user who performed a larger number of total selected actions. Step  502  is based upon the observation that a greater level of interest in a subject causes a user to perform a greater number of total actions that relate to that subject. After step  502 , these steps conclude. 
     In step  503 , if the number of distinct selected actions performed by the two users is equal, then the facility continues in step  505 , else the facility continues in step  504 . In step  504 , the facility ranks more highly the user who performed the larger number of distinct selected actions. Step  504  is based upon the observation that among users who have performed the same total number of actions related to a subject, the user who has performed more distinct actions relating to the subject tends to be more interested in the subject than users that repeat a smaller number of such actions a larger number of times. After step  504 , these steps conclude. 
     In step  505 , if the number of distinct unselected actions performed by the two users is equal, then the facility continues in step  507 , else the facility continues in step  506 . In step  506 , the facility ranks more highly the user who performed a smaller number of distinct unselected actions. Step  506  is based upon the observation that, where a user has a higher level of interest in a subject, a higher percentage of all of the user&#39;s discrete actions relate to the subject. After step  506 , these steps conclude. 
     In step  507 , if the total number of unselected actions performed by the two users is equal, then the facility continues in step  509 , else the facility continues in step  508 . In step  508 , the facility ranks more highly the user who performed a smaller number of total unselected actions. Step  508  is based upon the observation that, where a user has a higher level of interest in a subject, a higher percentage of all of the user&#39;s total actions relate to the subject. After step  508 , these steps conclude. 
     In step  509 , the facility ranks the users equally, or randomly selects a user to be ranked higher, or uses some other basis to rank the two users relative to one another (not shown). After step  509 , these steps conclude. 
     An example of the process shown in  FIG. 5  is illustrated in  FIGS. 6 and 7 .  FIG. 6  is a table diagram showing sample contents of a user behavior table documenting the behavior of a group of users. The table  600  is comprised of rows such as rows  601 - 607 , each corresponding to a different user. Each row is divided into the following columns: a user ID column  611  containing a unique identifier for the user; an action  1  column  612  showing the number of times that the user has performed a first action, which has been selected as relevant to the subject; an action  2  column  613  showing the number of times that the user has performed a second action that has not been selected as being relevant to the subject; an action  3  column  614  showing the number of times that the user has performed a third action that has not been selected as being relevant to the subject; an action  4  column  615  showing the number of times that the user has performed a fourth action, which has been selected as relevant to the subject; and an action  5  column  616  showing the number of times that the user has performed a fifth action that has not been selected as being relevant to the subject. For example, row  601  shows that a user having user ID  1  performed selected action  1  ten times, performed unselected action  2  one time, performed unselected action  3  two times, performed selected action  4  eleven times, and performed unselected action  5  six times. 
     While  FIG. 6  and each of the table diagrams discussed below show a table whose contents and organization are designed to make them more comprehensible by a human reader, those skilled in the art will appreciate that actual data structures used by the facility to store this information may differ from the table shown, in that they, for example, may be organized in a different manner; may contain more or less information than shown; may be compressed and/or encrypted; etc. 
       FIG. 7  is a table diagram showing sample contents of a user ranking table generated by the facility in some embodiments based upon the contents of the user behavior table. The user ranking table  700  is made up of rows, such as rows  701 - 707 , each corresponding to a different user. Columns  711 - 716  contain user behavior information and correspond to columns  611 - 616  of the user behavior table. Columns  721 - 724  contain metrics derived from the user behavior information that the facility uses to determine the ranking. Ranking column  731  reflects a ranking determined by the facility that indicates the relative level of interest of these users in the subject, where a lower ranking value reflects a higher rank (e.g., the rank value 1 shown in row  701  reflects the highest rank). 
     Total selected column  721  indicates the total number of times the user performed any selected action—here the sum of the contents of columns  712  and  714 , containing the total number of times each user performed selected actions  1  and  4 , respectively. For example, in row  702 , it can be seen that the user having user ID  2  performed action  1  eleven times and action  4  twelve times, for a total of twenty-three in column  721 . Distinct selected column  722  contains an indication of the number of selected actions that a user performed at least one time. For example, in row  702 , it can be seen that the user having user ID  2  performed both of the two selected actions one and four at least once, and therefore has the value 2 in distinct selected column  722 . Distinct unselected column  723  indicates the number of unselected actions the user performed at least once. For example, in row  702 , it can be seen that the user having user ID  2  performed only one of the three unselected actions (action  3 , but not action  2  or action  5 ) one or more times. Accordingly, column  723  contains the value 1. The total unselected column  724  indicates the total number of times the user performed any unselected action—here the sum of the contents of columns  713 ,  714 , and  716 . In row  703 , it can be seen that the user having user ID  6  performed unselected action  2  six times, unselected action  3  seven times, and unselected action  5  four times for a total of seventeen in column  724 . 
     Using the steps shown in  FIG. 5 , the facility determines the contents of rank column  731 . It can be seen in column  721  that row  701  has the highest number of total selected actions, twenty-six. Accordingly, it receives the highest rank. It can be seen that rows  702  and  703  both have the same second-highest total number of selected actions, twenty-three. Accordingly, each of these rows will be ranked either second or third. Row  702  is ranked second based upon having a higher number of distinct selected actions, two, than row  703 , one. Rows  704 - 707  all have the same total number of selected actions, twenty-one, and number of distinct selected actions twenty-two. Because row  704  has a smaller number of distinct unselected actions, one, than rows  705 - 707 , it is ranked higher than rows  705 - 707 . Rows  705 - 707  all have the same number of total selected actions, distinct selected actions, and distinct unselected actions, so they are further differentiated based upon total number of unselected actions. Because row  705  has the smallest number of total unselected actions among these three rows, nine, it is ranked fifth. Rows  706 - 707  have the same number of total selected actions, distinct selected actions, distinct unselected actions, and total unselected actions, and are therefore ranked the same, sixth. In some embodiments, the facility employs some other basis for performing a relative ranking of these rows, such as random selection. 
     In some embodiments, the facility selects a subset of the rows of these or ranking table starting at the highest rank and extending to some lower rank. In some embodiments, a predetermined percentage of the rows are selected. In some embodiments, the facility uses a variety of other selection techniques to identify users interested in the subject. 
     In some embodiments, the facility performs the ranking in ways that differ from the approach described above. In some embodiments, the facility omits or combines factors among the four factors described. In some embodiments, rather than comparing each pair of users to determine their relative ranking, the facility independently determines a numerical score for each user. In some embodiments, the facility uses a multiple digit number for the score, and allocates one or more of the lowest-order digits of the number to the least significant factor, allocates one or more of the next most significant digits to the next most significant factor, and so on. For example, for user having user ID  3  shown in row  704   FIG. 7 , the facility may determine the score 21029884, where the “21” is copied from column  721 , the “02” is copied from column  722 , the “98” is determined by subtracting the value 1 contained in column  723  from 99, and the “84” is determined by subtracting the value 15 contained in column  724  from 99. In some embodiments, the facility uses other encoding schemes to generate a numerical score for each user that leads to the same or a similar relative ranking result. 
     After the facility has identified users interested in the subject, advertisements or other promotions relating to the subject may be targeted to the identified users. In some embodiments, the facility uses advertising or other promotion techniques described in U.S. patent application Ser. No. 11/087,378, filed on Mar. 22, 2005, which is hereby incorporated by reference in its entirety. In some embodiments, the operator of the facility directly uses the list of identified users to itself target advertisements or other promotions to the identified users. In some embodiments, the operator of the facility sells a list of the identified users for use by other advertisers or promoters. In some embodiments, the facility uses techniques described in the following two patent applications, each of which is hereby incorporated by reference in its entirety: U.S. Patent Application No. 60/626,576, filed on Nov. 9, 2004, and U.S. Patent Application No. 60/623,379, filed on Oct. 29, 2004. 
     It will be appreciated by those skilled in the art that the above-described facility may be straightforwardly adapted or extended in various ways. For example, the facility may be used to identify users in a wide variety of subjects, based upon a wide variety of different types of actions, in support of a wide variety of promotion techniques. While the foregoing description makes reference to particular embodiments, the scope of the invention is defined solely by the claims that follow and the elements recited therein.