Customer clustering using integer programming

Abstract

Methods and apparatus are disclosed regarding an e-commerce system that clusters customers based on demographic data and purchase history data for the customers. In some embodiments, the e-commerce system solves an Integer Program that accounts for the demographic data and purchase history data in order to identify a hyperplane that splits a selected cluster of customers.

What is claimed is: 
     
         1 . A computer-implemented method, comprising:
 iteratively splitting a plurality of customers into a plurality of clusters based on purchase history data and demographic data for the plurality of customers, wherein each iteration comprises selecting a cluster of customers and splitting the selected cluster until a stopping rule is satisfied; and   tailoring services provided to a customer based on a cluster from the plurality of clusters in which the customer resides.   
     
     
         2 . The computer-implemented method of  claim 1 , wherein the tailoring comprises providing product recommendations based on the cluster in which the customer resides. 
     
     
         3 . The computer-implemented method of  claim 1 , wherein the tailoring comprises providing product promotions based on the cluster in which the customer resides. 
     
     
         4 . The computer-implemented method of  claim 1 , wherein the tailoring comprises providing coupons based on the cluster in which the customer resides. 
     
     
         5 . The computer-implemented method of  claim 1 , wherein the tailoring comprises providing coupons based on the cluster in which the customer resides. 
     
     
         6 . The computer-implemented method of  claim 1 , wherein the splitting comprises solving an Integer Program that accounts for the purchase history data and demographic data for the selected cluster. 
     
     
         7 . The computer-implemented method of  claim 1 , wherein the selecting comprises selecting a cluster that has a population greater than a limit specified by the stopping rule. 
     
     
         8 . The computer-implemented method of  claim 1 , wherein the selecting comprises selecting a cluster that has the largest population of the plurality of clusters. 
     
     
         9 . The computer-implemented method of  claim 1 , further comprising ceasing the iteratively splitting in response to determining the plurality of clusters comprises a quantity of clusters desired by the stopping rule. 
     
     
         10 . The computer-implemented method of  claim 1 , further comprising ceasing the iteratively splitting in response to determining that no cluster of the plurality of clusters comprises exceeds a population limit specified by the stopping rule. 
     
     
         11 . The computer-implemented method of  claim 1 , wherein the splitting comprises solving the following Integer Program:
 Minimize:   
       
         
           
             
               
                 ∑ 
                 
                   i 
                   = 
                   1 
                 
                 n 
               
                
               
                   
               
                
               
                 
                   ∑ 
                   
                     j 
                     = 
                     1 
                   
                   n 
                 
                  
                 
                     
                 
                  
                 
                   
                     d 
                     ij 
                   
                    
                   
                     J 
                     ij 
                   
                 
               
             
           
         
         Subject to:
   β x   i +β 0 ≦(1− I   i )· C∀i  
 
   −β x   i −β 0   ≦I   i   ·C−ε∀i  
 
     I   i   −I   j ≦1− J   ij   ∀i,j  
 
     I   i   +I   j ≦1− J   ij   ∀i,j  
 
     I   i ε{0,1}∀ i  
 
   0≦ J   ij ≦1∀ i,j  
 
 
         where n is a number of customers; m is a number of dimensions in a feature space defined by demographic data for the number of customers; x i  is a length-m coordinate vector of customer i in the feature space for i=1 . . . n; d ij  is a distance between customers i and j in transaction space according to a pre-selected distance metric; C is a large constant; ε is a small constant; I i  is an indicator variable of customer i, which is one if customer i is in cluster 1 (one side of the optimum hyperplane), and zero if the customer is in cluster 2 (the other side of the hyperplane) in the feature space; J ij  is an indicator variable for customer pair (i,j), which is equal to one if i and j are in the same cluster, and zero if they are in different clusters; β is a length-m direction vector in the feature space that defines the direction of the dividing hyperplane; and β 0  is a scalar intercept of the dividing hyperplane. 
       
     
     
         12 . A non-transitory computer-readable medium, comprising a plurality of instructions, that in response to being executed, result in a computing device:
 iteratively splitting a plurality of customers into a plurality of clusters based on purchase history data and demographic data for the plurality of customers, wherein each iteration comprises selecting a cluster of customers and splitting the selected cluster until a stopping rule is satisfied; and   tailoring services provided to a customer based on a cluster from the plurality of clusters in which the customer resides.   
     
     
         13 . The non-transitory computer-readable medium of  claim 12 , further comprising instructions that result in the computing device splitting the selected cluster by solving an Integer Program that accounts for the purchase history data and demographic data for the selected cluster. 
     
     
         14 . The non-transitory computer-readable medium of  claim 12 , further comprising instructions that result in the computing device:
 selecting a cluster that has a population greater than a limit specified by the stopping rule; and   ceasing the iteratively splitting in response to determining that no cluster of the plurality of clusters exceeds the limit specified by the stopping rule.   
     
     
         15 . The non-transitory computer-readable medium of  claim 12 , further comprising instructions that result in the computing device:
 selecting a cluster that has the largest population of the plurality of clusters; and   ceasing the iteratively splitting in response to determining the plurality of clusters comprises a quantity of clusters desired by the stopping rule.   
     
     
         16 . A computing device, comprising
 an electronic database comprising demographic data and purchase history data for a plurality of customers; and   a processor configured to:
 iteratively split a plurality of customers into a plurality of clusters based on purchase history data and demographic data for the plurality of customers, wherein each iteration comprises selecting a cluster of customers and splitting the selected cluster until a stopping rule is satisfied; and 
 tailor services provided to a customer based on a cluster from the plurality of clusters in which the customer resides. 
   
     
     
         17 . The computing device of  claim 16 , wherein the processor is further configured to split the selected cluster by solving an Integer Program that accounts for the purchase history data and demographic data for the selected cluster. 
     
     
         18 . The computing device of  claim 16 , wherein the processor is further configured to:
 select a cluster that has a population greater than a limit specified by the stopping rule; and   cease further splitting in response to determining that no cluster of the plurality of clusters exceeds the limit specified by the stopping rule.   
     
     
         19 . The computing device of  claim 16 , wherein the processor is further configured to:
 select a cluster that has the largest population of the plurality of clusters; and   cease further iteratively splitting in response to determining the plurality of clusters comprises a quantity of clusters desired by the stopping rule.