Abstract:
System, method and computer program product for adjusting a representation of a merchandise hierarchy associated with an entity such as a retailer or wholesaler of products. Product correlation information discovered in that entity&#39;s customers&#39; shopping records are obtained and incorporated into an existing merchandise hierarchy with a constraint on the consistency with the existing hierarchy.

Description:
BACKGROUND 
       [0001]    The present invention is related generally to hierarchical organization of an entity&#39;s merchandise, i.e., product/inventory, and more specifically, to a method and system for merchandise hierarchy refinement by incorporating product correlation. More specifically, the present invention relates to a method and system of incorporating product correlation information discovered in customers&#39; shopping profiles (records) to adjust an existing merchandise hierarchy with a constraint on the consistency with the existing hierarchy. 
         [0002]    Merchandise hierarchy is a tree-like structure for organizing merchandise categories and products of an entity, e.g., a product wholesaler/retailer. It plays a key role in the business decision-making process. First, merchandise hierarchy is the base of management and operation structure: departments are usually organized according to the merchandise hierarchy and are responsible for all business related but sub-categories and products under the category, e.g., procurement, forecasting, shelf layout, etc. Moreover, merchandise analytics at levels defined in the hierarchy are the basis of business strategy adjustment, such as statistics, reporting, performance evaluation, etc. 
         [0003]    Currently, there is no mechanism for incorporating customers&#39; shopping behavior (e.g., a shopping profile or history) in such merchandise analytics. Such information is useful to facilitate improvement of the business structure and make it truly customer-oriented. 
       SUMMARY 
       [0004]    The present invention is a system and method for refining an entity&#39;s merchandise hierarchy, particularly by generating a more comprehensive merchandise hierarchy for an entity (e.g., a product retailer or wholesaler) that incorporates information representing the shopping behavior of customer(s). 
         [0005]    According to one aspect of the invention, there is provided a method of merchandise hierarchy refinement comprising: extracting first data representing a predetermined merchandise hierarchy and second data representing transaction records having a plurality of transactions related to a plurality of products; clustering the plurality of products based on the plurality of transactions; and updating the predetermined merchandise hierarchy representation based on the clustering, wherein a program using a processor unit performs one or more of the extracting, clustering and updating. 
         [0006]    Further to this aspect of the invention, the step of clustering comprises: setting a current level of the merchandise hierarchy as a bottom level of the merchandise hierarchy, initializing a new membership matrix to an existing membership matrix; applying a Genetic Algorithm to minimize an objective function, wherein in each step of the Genetic Algorithm, a new generation group of the new membership matrix satisfies a consistency constraint; repeating the initializing and applying at a next upper level of the current level until a next highest level of the merchandise hierarchy is reached; and outputting the new membership matrix. 
         [0007]    The comprehensive merchandise hierarchy helps to improve the business structure and make it truly customer-oriented which will, in turn, increase customer&#39;s satisfaction, improve operational efficiency, and reduce the cost of management. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0008]    The accompanying drawings are included to provide a further understanding of the present invention, and are incorporated in and constitute a part of this specification. The drawings illustrate embodiments of the invention and, together with the description, serve to explaining the principles of the invention. In the drawings, 
           [0009]      FIG. 1  illustrates an overview of the system and method for merchandise hierarchy refinement according to a preferred embodiment of the present invention; 
           [0010]      FIG. 2  illustrates an example of a predefined merchandise hierarchy; 
           [0011]      FIG. 3  illustrates an example of a transaction record data table; 
           [0012]      FIG. 4  illustrates an example of the refined merchandise hierarchy based on the transaction record data illustrated in  FIG. 3 , according to one embodiment; and 
           [0013]      FIG. 5  illustrates the flow chart for the method for the merchandise hierarchy refinement; and, 
           [0014]      FIG. 6  illustrates an exemplary hardware configuration for implementing the flow charts depicted in  FIGS. 1 and 5  according to one embodiment of the present invention. 
       
    
    
     DETAILED DESCRIPTION 
       [0015]      FIG. 1  illustrates an overview of a system and computer-implemented method  100  for merchandise hierarchy refinement according to a preferred embodiment of the present invention. In the system  100 , there is employed at least three processing modules: a data extraction module  101 , a cluster model with consistency constraints module  102 , and a merchandise hierarchy updater module  103 . 
         [0016]    The data extraction module ( 101 ) receives two data feeds: a first data input  11  for receiving data representing a predefined merchandise hierarchy; and, second data input  12  for receiving customers&#39; transaction records. As will be described, the received customer transaction records are preprocessed by the data extraction module  101  to obtain item similarity. 
         [0017]    The cluster model with consistency restraints  102  performs clustering over the items of each level of merchandise hierarchy by adding consistency restraints based on a ratio of mutual information. 
         [0018]    The merchandise hierarchy updater  103  performs updating of the corresponding items and updating of the links between the corresponding levels of merchandise hierarchy. 
         [0019]      FIG. 2  illustrates an example of a predefined merchandise hierarchy  200  having a tree-like structure that comprises the first data input  11  to the data extraction module ( 101 ). In particular, any common hierarchical tree representation can be input that includes representation of nodes, e.g., with pointers to their children, their parents, or both, or as items in an array with relationships between them determined by their positions in the array is input. For purposes of discussion, the merchandise hierarchy  200  is provided for an example merchandise retail entity, e.g., “J-mart,” which may be a chain of retail stores. The chain J-Mart ( 201 ) is arranged in a hierarchical manner with the top node of the tree  201  indicating the retail entity (chain). The retail entity at the top node is divided into several departments  202 , indicated as child nodes  202   a ,  202   b ,  202   c . As shown in  FIG. 2 , for example, a first child node represents a Shoes department ( 202   a ). Departments in the hierarchy are further divided into classes  203 . For example, as shown in  FIG. 2 , the Shoes department ( 202   a ) is further divided into classes including a Men&#39;s summer shoes class ( 203   a ). Classes  203  in the hierarchy are further divided into items  204 . For example, Men&#39;s summer shoes class  203   a  in the hierarchy includes products of merchandise such as the walker shoes ( 204   a ). 
         [0020]      FIG. 3  presents an example of a transaction record data table  300  that comprises the second data input  12  to the data extraction module ( 101 ).  FIG. 3  in particular gives the attributes of a transaction record, and these records with attributes are stored into a database or like memory storage structure. The example table includes main attribute columns: Transaction ID ( 301 ) and Merchandise Category ( 302 ). Merchandise Category column  302  includes items or products of the retailer that may have been subject to purchase in particular customers&#39; transactions (indicated by the Transaction ID). For example, the merchandise category shown in  FIG. 3  indicates three products: bread ( 303 ), milk ( 304 ) and fruit ( 305 ) for the merchandise category. In the transaction record data table  300 , for each transaction, a ‘1’ entry in the column represents that the product is bought and ‘0’ represents that the product is not bought. Note that the times any two products are bought together are counted as similarities between the two products. In this example table, it can be seen that milk and bread are bought together 2 times, milk and fruit are bought together 2 times, and bread and fruit are bought together 1 time. Intuitively, the more times two products are bought together, the more they complement each other. 
         [0021]    As mentioned, the data extractor module  101  preprocesses the received customer transaction records to generate item similarities, i.e., a similarities count. 
         [0022]    This similarities count data is input to the cluster model with consistency constraints module ( 102 ) in  FIG. 1 . The similarities are real numbers without complex data structures, and the manner in which they are calculated is explained in greater detail herein below. The cluster model with consistency constraints ( 102 ) in  FIG. 1  performs clustering over products of each level of the merchandise hierarchy by adding consistency constraints based on a ratio of mutual information between the predefined merchandise hierarchy and the refined hierarchy that reflects their difference. Thus, in this phase ( 102 ), the merchandise hierarchy has been refined. 
         [0023]    First, the notations used in the clustering model implemented by the consistency constraints module ( 102 ) are introduced as follows: 
         [0024]    N=number of products (e.g., N i+1  is the number of products of the level i+1 that is determined by predefined merchandise hierarchy); 
         [0025]    M=number of original categories; 
         [0026]    K=number of new categories; 
         [0027]    W={W ij }=N×N similarity matrix; 
         [0028]    D=diag{d 1 , . . . , d N }, where d 1 =Σ j W ij ; 
         [0029]    C=N×K new member matrix, wherein C i =ith row of C; 
         [0030]    T=existing category labels defined by the existing hierarchy (e.g., Tij=1 whenever product i belongs to category j. Otherwise, Tij=0. The size of matrix T is subject to the existing hierarchy that may be different from the size of C); 
         [0031]    p ij =fraction of sales volume of products in new category i and existing category j; 
         [0032]    p i *=Σ j p ij =fraction of sales volume of products in new category I; 
         [0033]    p* j =Σ i p ij =fraction of sales volume of products in existing category j; 
         [0000]    
       
         
           
             
               
                 H 
                  
                 
                   ( 
                   T 
                   ) 
                 
               
               = 
               
                 
                   - 
                   
                     
                       ∑ 
                       
                         j 
                         = 
                         1 
                       
                       M 
                     
                      
                     
                       
                         p 
                         j 
                         * 
                       
                        
                       
                         log 
                          
                         
                           ( 
                           
                             p 
                             j 
                             * 
                           
                           ) 
                         
                       
                     
                   
                 
                 = 
                 
                   Shannon 
                    
                   
                       
                   
                    
                   entropy 
                    
                   
                       
                   
                    
                   of 
                    
                   
                       
                   
                    
                   T 
                 
               
             
             ; 
           
         
       
       
         
           
             
               
                 
                   
                     I 
                      
                     
                       ( 
                       
                         C 
                         , 
                         T 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       ∑ 
                       
                         i 
                         = 
                         1 
                       
                       K 
                     
                      
                     
                       
                         ∑ 
                         
                           j 
                           = 
                           1 
                         
                         M 
                       
                        
                       
                         
                           p 
                           ij 
                         
                          
                         
                           log 
                            
                           
                             ( 
                             
                               
                                 p 
                                 ij 
                               
                               
                                 
                                   p 
                                   i 
                                   * 
                                 
                                 × 
                                 
                                   p 
                                   j 
                                   * 
                                 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
             
             
               
                 
                   
                     = 
                     
                       mutual 
                        
                       
                           
                       
                        
                       information 
                        
                       
                           
                       
                        
                       between 
                        
                       
                           
                       
                        
                       C 
                        
                       
                           
                       
                        
                       and 
                        
                       
                           
                       
                        
                       T 
                     
                   
                   ; 
                 
               
             
           
         
       
     
         [0034]    Q(C,T)=H(T)/I(C,T)=ratio of mutual information; 
         [0035]    η≧1=control parameter. 
         [0036]    It is understood that data N, M, D, K, W, p, H( )I( )Q( ) are extracted from the transaction records. 
         [0037]    Using the definitions given above, finding a clustering assignment operation is performed whereby each product is assigned a cluster label, i.e. the output matrix C, such that similar items have similar assignments is tantamount to finding a solution to the new member matrix “C” which satisfies the following objective function: 
         [0000]    
       
         
           
             
               
                 min 
                  
                 
                   
                     ∑ 
                     
                       i 
                       , 
                       
                         j 
                         = 
                         1 
                       
                     
                     N 
                   
                    
                   
                     
                       W 
                       ij 
                     
                      
                     
                       
                          
                         
                           
                             C 
                             i 
                           
                           - 
                           
                             C 
                              
                             
                                 
                             
                              
                             j 
                           
                         
                          
                       
                       2 
                     
                   
                 
               
               = 
               
                 trace 
                  
                 
                   ( 
                   
                     
                       
                         C 
                         T 
                       
                        
                       
                         ( 
                         
                           D 
                           - 
                           W 
                         
                         ) 
                       
                     
                      
                     C 
                   
                   ) 
                 
               
             
             , 
           
         
       
     
         [0038]    such that Q(C,T)≦η. 
         [0039]    The objective function which makes use of the complementary information between products means that similar products have similar cluster assignments. A description of a clustering technique that can be used is presented herein below in greater detail. 
         [0040]    The consistency constraint leverages expertise to control the extent of hierarchy change. It can be found that Q(C,T) is minimized to 1 if and only if the sales distributions with the new and existing categories are identical. The higher the confidence level of the predefined merchandise hierarchy, i.e., the confidence level that can be mirrored by parameter and adopted to only show the degree of belief in the predefined merchandise hierarchy, the smaller the value of η. In practice, the confidence level of predefined hierarchy is determined by tuning the control parameter η which is a presupposed positive constant based on the expertise to predefined merchandise hierarchy (i.e. its confidence level) before clustering. Hence, for a given η the whole bottom-up process is performed once. 
         [0041]    Accordingly, in one embodiment, an optimization algorithm is implemented for the cluster model with the following consistency constraints: Initialization: C=T. The algorithm includes:
       1. Applying a Genetic Algorithm (GA) (e.g., see reference to Holland, John H entitled Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor (1975), incorporated by reference herein) to minimize the objective function. Generally, GA algorithms are implemented in a computer simulation in which a population of abstract representations of candidate solutions to an optimization problem evolves toward better solutions. The evolution usually starts from a population of randomly generated individuals (binary representation) and happens in generations. In each generation (iteration), multiple individuals are stochastically selected from the current population based on their fitness (i.e. the corresponding value of objective function), and modified (recombined and randomly mutated) to form a new population that is then used in the next iteration. Commonly, the algorithm terminates when either a maximum number of generations has been produced, or a satisfactory fitness level has been reached. However, slightly different from the above original GA, in each iteration of the present method, it is demanded that the new generation group of variable C must satisfy the consistency constraints. Hence, in each generation those individuals breaking consistency constraints must be removed.   2. Output the final cluster assignments C, i.e., the matrix C is just the structure output. Cij=1 means product i belongs to category j and otherwise Cij=0. Therefore, the refined merchandise hierarchy may be re-drawn in terms of C such as described herein with respect to  FIG. 4 .       
 
         [0044]    The final cluster assignments C are output to the Merchandise Hierarchy updater ( 103 ) as shown in  FIG. 1 , which updates the clustering of the corresponding items according to the result computed by the Cluster Model, and updates the links between the corresponding levels of the merchandise hierarchy such as the merchandise hierarchy  200  shown in  FIG. 2 . 
         [0045]      FIG. 4  shows an example of updates  400  performed by the Merchandise Hierarchy Updater module  103 . As shown in  FIG. 4 , the original categories in the middle level only included Staple food ( 401 ) and Dairy ( 402 ). After implementing the cluster modeling performed by module  102 , besides two existing categories, a new category ‘Cluster  3 ’ ( 403 ) is generated according to cluster assignments. The new category contains two products bread ( 404 ) and milk ( 405 ) that originally belong to the Staple food ( 401 ) and Dairy ( 402 ) respectively Here, Merchandise Hierarchy Updater performs three things: first, give Cluster  3  a title, e.g. Breakfast ( 406 ) that is in accordance with the meanings of bread and milk and create a new category node Breakfast; second, discard the links from bread to Staple food ( 401 ) and from milk to Dairy ( 402 ), and add links from bread and milk to Breakfast ( 406 ); third, add a link from Breakfast ( 406 ) to its upper level nodes, e.g. create a link from Breakfast to Foodline ( 407 ). 
         [0046]    In summary, a bottom-up strategy to adjust the predefined merchandise hierarchy is adopted. The method implementing the strategy in the Merchandise Hierarchy Updater module  103  is as follows:
       1) choose a starting level in the existing hierarchy;   2) sequentially implement the three modules: the data extractor, the cluster model with consistency constraints and the merchandise hierarchy updater;   3) return to perform the second step on the upper category level of the current level;   4) output the refined merchandise hierarchy until the next highest level is reached.       
 
         [0051]      FIG. 5  illustrates a flow chart for the method  450  for the merchandise hierarchy refinement according to the present invention. In step  455 , given a hierarchy with n levels, the method includes: setting the bottom level as the current level (i.e. set current level as level i and initialize i=1). In step  460 , the clustering method is performed on the current level i and the links between the current level i and the upper level i+1 are performed. In step  465 , the links between the upper level i+1 and the next upper level I+2 are updated. After the updates in step  465 , a determination is made as to whether the current value is the next highest level in step  470 . If the current level is not the next highest level, then the upper level is set as the current level at  471  and the clustering updating in steps  460  and  465  are repeated; otherwise, the refined hierarchy is output at  475  and the process terminates. The updating of the predetermined merchandise hierarchy representation thus includes adding a new node and corresponding link connecting the new node to a parent node of said first lower or second next lower level node. 
         [0052]    In one example, as a result of implementing the present invention, the comprehensive merchandise hierarchy helps to improve the business structure and make it truly customer-oriented which will, in turn, increase customer&#39;s satisfaction, improve operational efficiency, and reduce the cost of management. For example, a new category may be created for young mothers that often buy products for themselves together with products for their baby, and baby products are no longer separately located in individual categories, such as baby milk in the diary department, or baby clothing in clothing department. 
         [0053]      FIG. 6  illustrates an exemplary hardware configuration of a computing system  500  running and/or implementing the method steps in  FIGS. 1 and 5 . The hardware configuration preferably has at least one processor or central processing unit (CPU)  511 . The CPUs  511  are interconnected via a system bus  512  to a random access memory (RAM)  514 , read-only memory (ROM)  516 , input/output (I/O) adapter  518  (for connecting peripheral devices such as disk units  521  and tape drives  540  to the bus  512 ), user interface adapter  522  (for connecting a keyboard  524 , mouse  526 , speaker  528 , microphone  532 , and/or other user interface device to the bus  512 ), a communication adapter  534  for connecting the system  500  to a data processing network, the Internet, an Intranet, a local area network (LAN), etc., and a display adapter  536  for connecting the bus  512  to a display device  538  and/or printer  539  (e.g., a digital printer of the like). 
         [0054]    Although the embodiments of the present invention have been described in detail, it should be understood that various changes and substitutions can be made therein without departing from spirit and scope of the inventions as defined by the appended claims. Variations described for the present invention can be realized in any combination desirable for each particular application. Thus particular limitations, and/or embodiment enhancements described herein, which may have particular advantages to a particular application need not be used for all applications. Also, not all limitations need be implemented in methods, systems and/or apparatus including one or more concepts of the present invention. 
         [0055]    The present invention can be realized in hardware, software, or a combination of hardware and software. A typical combination of hardware and software could be a general purpose computer system with a computer program that, when being loaded and run, controls the computer system such that it carries out the methods described herein. The present invention can also be embedded in a computer program product, which comprises all the features enabling the implementation of the methods described herein, and which—when loaded in a computer system—is able to carry out these methods. 
         [0056]    Computer program means or computer program in the present context include any expression, in any language, code or notation, of a set of instructions intended to cause a system having an information processing capability to perform a particular function either directly or after conversion to another language, code or notation, and/or reproduction in a different material form. 
         [0057]    Thus the invention includes an article of manufacture which comprises a computer usable medium having computer readable program code means embodied therein for causing a function described above. The computer readable program code means in the article of manufacture comprises computer readable program code means for causing a computer to effect the steps of a method of this invention. Similarly, the present invention may be implemented as a computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing a function described above. The computer readable program code means in the computer program product comprising computer readable program code means for causing a computer to affect one or more functions of this invention. Furthermore, the present invention may be implemented as a program storage device readable by machine, such as a processing device, microprocessor, processor unit, etc., tangibly embodying a program of instructions operated by the machine to perform method steps for causing one or more functions of this invention. 
         [0058]    The present invention may be implemented as a computer readable medium (e.g., a compact disc, a magnetic disk, a hard disk, an optical disk, solid state drive, digital versatile disc) embodying program computer instructions (e.g., C, C++, Java, Assembly languages, Net, Binary code) run by a processor (e.g., Intel® Core™, IBM® PowerPC®) for causing a computer to perform method steps of this invention. The present invention may include a method of deploying a computer program product including a program of instructions in a computer readable medium for one or more functions of this invention, wherein, when the program of instructions is run by a processor, the computer program product performs the one or more of functions of this invention. 
         [0059]    It is noted that the foregoing has outlined some of the more pertinent objects and embodiments of the present invention. This invention may be used for many applications. Thus, although the description is made for particular arrangements and methods, the intent and concept of the invention is suitable and applicable to other arrangements and applications. It will be clear to those skilled in the art that modifications to the disclosed embodiments can be effected without departing from the spirit and scope of the invention. The described embodiments ought to be construed to be merely illustrative of some of the more prominent features and applications of the invention. Other beneficial results can be realized by applying the disclosed invention in a different manner or modifying the invention in ways known to those familiar with the art.