Accurate and interpretable rules for user segmentation

Abstract

Various embodiments describe user segmentation. In an example, potential rules are generated by applying a frequency-based analysis to user interaction data points. Each of the potential rules includes a set of attributes of the user interaction data points and indicates that these data points belong to a segment of interest. An objective function is used to select an optimal set of rules from the potential rules for the segment of interest. The potential rules are used as variable inputs to the objective function and this function is optimized based on interpretability and accuracy parameters. Each rule from the optimal set is associated with a group of the segment of interest. The user interaction data points are segments into the groups by matching attributes of these data points with the rules.

1 . A computer-implemented method comprising:
 receiving, by a computer system, user interaction data points, wherein each user interaction data point comprises at least one attribute of a user interaction within a computer network;   generating, by the computer system, rules based on frequencies of occurrence of attributes of user interactions in the user interaction data points, wherein each rule comprises a different set of the attributes and indicates that the different set of the attributes is associated with a segment of interest;   maintaining a frequent pattern (FP) tree associated with the rules;   constructing an objective function for optimizing a parameter,   wherein the parameter is determined based on a root of the FP tree associated with the rules;   selecting, by the computer system, a set of rules from the rules based on an the objective function, wherein selecting the set of rules comprises using the rules as variables of the objective function and optimizing the objective function for the segment of interest;   segmenting, by the computer system, the user interaction data points into groups of the segment of interest based on the set of rules, wherein each group is associated with a rule from the set of rules, and wherein a user interaction data point comprising a set of attributes is added to a group based on a match between the set of attributes and the rule associated with the group; and   presenting, by the computer system on a user interface, the groups, wherein a presentation of each group presents the rule associated with the group.   
     
     
         2 . The computer-implemented method of  claim 1 , wherein the objective function comprises a combination of individual objective functions, wherein a set of the individual objective functions are associated with an interpretability parameter and a remaining set of individual objective functions are associated with an accuracy parameter. 
     
     
         3 . The computer-implemented method of  claim 2 , wherein:
 the combination is a non-linear combination that weighs the individual objective functions based on user input received at the user interface; and   the user input specifies one or more of: a total number of the rules, a maximum number of attributes that each rule should include, a precision associated with the segmenting, or a recall associated with the segmenting.   
     
     
         4 . The computer-implemented method of  claim 1 , wherein;
 the objective function comprises a combination of individual objective functions; and   an individual objective function of the individual objective functions optimizes an interpretability parameter by minimizing a size of the set of rules.   
     
     
         5 . The computer-implemented method of  claim 1 , wherein the objective function comprises a combination of individual objective functions, wherein an individual objective function of the individual objective functions optimizes an interpretability parameter by favoring a selection of a first rule comprising a first set of the attributes over a second rule comprising a second set of the attributes for addition to the set of rules based on a size of the first set of the attributes being smaller than a size of the second set of the attributes. 
     
     
         6 . The computer-implemented method of  claim 1 , wherein:
 the objective function comprises a combination of individual objective functions; and   an individual objective function of the individual objective functions optimizes an interpretability parameter by minimizing an overlap between two rules added to the set of rules.   
     
     
         7 . The computer-implemented method of  claim 6 , wherein the overlap between the two rules is determined by computing a size of a first set of attributes belonging to the segment of interest and a second set of attributes not belonging to the segment of interest such that each of the first set and the second set is covered by a union of the two rules. 
     
     
         8 . The computer-implemented method of  claim 1 , wherein the objective function comprises a combination of individual objective functions, wherein an individual objective function of the individual objective functions optimizes an accuracy parameter by minimizing a total number of user interaction data points that the set of rules incorrectly associates with the segment of interest. 
     
     
         9 . The computer-implemented method of  claim 8 , wherein the total number of user interaction data points is determined by computing a size of a set of attributes indicated as not belonging to the segment of interest and covered by at least one rule of the set of rules. 
     
     
         10 . The computer-implemented method of  claim 1 , wherein:
 the objective function comprises a combination of individual objective functions; and   the parameter is an accuracy parameter, and an individual objective function of the individual objective functions optimizes the accuracy parameter by maximizing a total number of user interaction data points that the set of rules correctly associates with the segment of interest.   
     
     
         11 . The computer-implemented method of  claim 10 , wherein the total number of user interaction data points is determined by computing a size of a set of attributes indicated as belonging to the segment of interest and covered by at least one rule of the set of rules. 
     
     
         12 . The computer-implemented method of  claim 11 , wherein the total number of user interaction data points corresponds to the root of the FP tree. 
     
     
         13 . The computer-implemented method of  claim 12 , wherein:
 the individual objective function is optimized based on computing a first score for the set of rules excluding a particular rule and on a second score for the set of rules including the particular rule; and   the first score and the second score are computed based on adjustments to a set of FP trees including the FP tree.   
     
     
         14 . The computer-implemented method of  claim 1 , further comprising:
 maintaining a second FP tree associated with a complement set of rules from the rules;   moving a rule from the complement set of rules to the set of rules; and   updating the FP tree, the parameter, and the second FP tree based on moving the rule from the complement set of rules to the set of rules.   
     
     
         15 . The computer-implemented method of  claim 1 , further comprising:
 updating the FP tree and second FP tree upon a removal of another rule from the set of rules to a complement set of rules from the rules,   wherein a total number of user interaction data points is determined from the root of the FP tree.   
     
     
         16 . The computer-implemented method of  claim 1 , wherein:
 the objective function is optimized based on computing a first score for the set of rules excluding a particular rule, on a second score for the set of rules including the particular rule, on a third score for a complement set of rules including the particular rule, and on a fourth score for the complement set of rules excluding the particular rule; and   the first score, the second score, the third score, and the fourth score are computed based on adjustments to a set of FP trees.   
     
     
         17 . A computer system comprising:
 receiving, by a computer system, user interaction data points, wherein each user interaction data point comprises at least one attribute of a user interaction within a computer network;   generating, by the computer system, rules based on frequencies of occurrence of attributes of user interactions in the user interaction data points, wherein each rule comprises a different set of the attributes and indicates that the different set of the attributes is associated with a segment of interest;   maintaining a frequent pattern (FP) tree associated with the rules;   means for constructing an objective function for optimizing a parameter, wherein the parameter is determined based on a root of the FP tree associated with the rules;   selecting, by the computer system, a set of rules from the rules based on an the objective function, wherein selecting the set of rules comprises using the rules as variables of the objective function and optimizing the objective function for the segment of interest;   means for segmenting, by the computer system, the user interaction data points into groups of the segment of interest based on the set of rules, wherein each group is associated with a rule from the set of rules, and wherein a user interaction data point comprising a set of attributes is added to a group based on a match between the set of attributes and the rule associated with the group; and   means for presenting, by the computer system on a user interface, the groups, wherein a presentation of each group presents the rule associated with the group.   
     
     
         18 . The computer system of  claim 17 , wherein the groups are used as controls of a content management system, and wherein the content management system automatically transmits targeted content to a user device based on segmenting a user interaction data point provided from the user device in a particular group of the groups. 
     
     
         19 . A non-transitory computer-readable storage medium storing instructions that, upon execution on a computer system, cause the computer system to perform operations comprising:
 receiving, by a computer system, user interaction data points, wherein each user interaction data point comprises at least one attribute of a user interaction within a computer network;   generating, by the computer system, rules based on frequencies of occurrence of attributes of user interactions in the user interaction data points, wherein each rule comprises a different set of the attributes and indicates that the different set of the attributes is associated with a segment of interest;   maintaining a frequent pattern (FP) tree associated with the rules;   constructing an objective function for optimizing a parameter,   wherein the parameter is determined based on a root of the FP tree associated with the rules;   selecting, by the computer system, a set of rules from the rules based on an the objective function, wherein selecting the set of rules comprises using the rules as variables of the objective function and optimizing the objective function for the segment of interest;   segmenting, by the computer system, the user interaction data points into groups of the segment of interest based on the set of rules, wherein each group is associated with a rule from the set of rules, and wherein a user interaction data point comprising a set of attributes is added to a group based on a match between the set of attributes and the rule associated with the group; and   presenting, by the computer system on a user interface, the groups, wherein a presentation of each group presents the rule associated with the group.   
     
     
         20 . The non-transitory computer-readable storage medium of  claim 19 , wherein:
 the objective function comprises a non-linear combination of individual objective functions; and   a first set of the individual objective functions are associated with interpretability parameters and a remaining set of individual objective functions are associated with accuracy parameters.