PPCS : A Personalized Product Catalogue System for On-Line Shopping

A Software Architecture for Personalized Product Catalog System for On-Line Shopping

 

Jayanta Basak, Raghuram Krishnapuram

IBM India Research Lab

Block I, Indian Institute of Technology

Hauz Khas, New Delhi 110016

India

e-mail : bjayanta@in.ibm.com, kraghura@in.ibm.com

 

and

 

Tushit Jain

Department of Electrical Engineering

Indian Institute of Technology

Madras

India.

 

 

 

 

 

Abstract

 

 

A personalized product catalog is a hierarchically arranged subset of products displayed in accordance with the interest of an individual user. In this paper, we introduce a product graph that stores the products (the product-ids) as the vertices and the similarities between product attributes in the edges. The users interests are stored in user interest hierarchy (UIH), which in turn stores one exemplar product-id in each leaf node. The product catalog is dynamically generated from the product graph and UIH. Personalized Product Catalog System (PPCS) is more storage-efficient than storing individual catalogs for individual customers.

 

 

 

 

 

  1. Introduction:

 

 

In catalogs [1], generally product categories are arranged in the form of a hierarchy such that each node down the hierarchy represents a subcategory and the leaf nodes represent the actual products. In a personalized product catalog, it is desirable to generate product hierarchies according to the user interests as opposed to having a static hierarchy. However, maintaining product hierarchies for each individual customer requires enormous storage.

 

Attempts have been made to design product catalogs based on collaborative filtering [1,2,4,5], and analysis of clickstreams. Here we present a personalized product catalog where each users interests are stored in the form of a hierarchy called User Interest Hierarchy (UIH). The products and their attributes are stored in a database table called product table (PT) and the relationships between the products are stored in the form of a graph called product graph (PG). The product table (PT) and the product graph (PG) are the static parts of the personalized product recommendation model and are common for all users. The user interest hierarchy (UIH) is a dynamic data structure and can be updated depending on his/her behavior (e.g., purchase history and clickstream) or feedback. Whenever a customer logs in, the products satisfying his interests, are retrieved from the product graph and the product table based on his/her UIH.

 

 

  1. Description of PPCS

 

Figure 1 schematically describes the software architecture for the personalized product catalog system (PPCS) where PT and PG are static data structures and UIH is specific to the user. UIH can change dynamically for each user. The interest patterns stored in the UIH correspond to a set of product attributes that are present in the product table, and the similarities that are stored in the edges of the product graph are the similarities between these product attributes.

 

Product Table (PT) stores the products in a database table in form of product-ids and the corresponding set of attributes assuming that the product attributes exhaustively address all customers interests.

 

 

 

 

 

 

 

 

Figure 1 : A schematic diagram of the software architecture of PPCS

 

 

Product Graph (PG) is described as M = {P, R} where is the set of vertices representing product-ids, and is the set of edges representing similarity indices between the attributes of products and such that

 

(1)

 

where each denotes a numeric value in [0,1] indicating the degree of similarity between the values of k-th attribute of the two products and .

 

User Interest Hierarchy (UIH) is a hierarchical representation of a users interests. Each leaf node of a UIH stores an exemplar product-id. Each node i in UIH is assigned a weight () indicating the relative degree to which user is interested in that subcategory. The UIH of a user can be built off-line, or on-line [6] (e.g., by considering the navigational pattern of a user through the web site). In the off-line mode of generation, given a set of products, a user can select a list of products of his/her choice. From the chosen list of products, a UIH can be generated by using a hierarchical clustering algorithm or by building a classification tree (classifying the products into classes chosen and not chosen) [3]. The leaf nodes containing the products the user did not like can be pruned, giving rise to the UIH. The exemplar product at each leaf node can be set by considering the most typical product in that leaf node.

 

 
3 Generation of Product Hierarchy

 

Procedure Traverse(i) describes a recursive method for generating the product catalog by traversing the UIH. Sort(i) returns a sorted list of indices to product attributes under node , sorted according to the weights (). Property(k) is a list of attributes that are associated with the nodes in the path from the root to the node k of the UIH (). Append(L1,L2) appends list L2 with list L1 and returns the concatenated list. Get_product(i) returns the exemplar product-id stored at the leaf node of UIH. Match(i,j,Property(k)) returns a value if the attributes specified by the list Property(k) takes a high value in the corresponding link. It invokes a similarity measure between two products i and j. Various similarity measures exist in the literature [7]. We have defined two measures in the following ways :

(2)

and

(3)

the product j is retrieved if where product i is the in the leaf node of hierarchy.

 

 

Begin

Property(root) = null;

Traverse(root)

End

 

Procedure Traverse(i) //Traverses from the i-th node of UIH //

Begin

If level(i) != LEAF then

Begin

Sort(i);

For each k in Sort(i),

Begin

Property(k) = Append(Property(i), attribute(k));

Traverse(k);

End

End

Else

p = Get_product(i);

For all j in (i.e., the set of edges connected to product p in the product graph)

Begin

If != NULL then

Begin

If Match(p,j, Property(i)) = HIGH then

Begin

Set(i) = Set(i)

End

End

End

Return();

End

 

If the number of products (n) is much less than the number of customers (m), and the average number of categories a user interested (N) in is much less than the total number of products (n) then PPCS is much more storage efficient than maintaining individual product catalogs. For example, if N = 10, n = 100, and m = 1000 then the personalized catalogue requires a space of O(104) and static catalogues will require a space of O(105).

 

 

4        Experimental Results

 

To verify the effectiveness of PPCS, we have implemented a pilot model along with the necessary GUIs for retrieving cars (automobiles) of different models from a database of 200 automobiles.

The UIH is generated from a decision tree which is a classification hierarchy such that the products are divided into those which the user likes and those he does not like. UIH is obtained by removing the leaf nodes of no interest to the user. A measure for the degree of interest in a node is obtained as

 

m ( NL ) = D r( NL ) = r ( NP ) - PL.r ( NL ) (4)

 

where NL and NP are the indices of the present and parent nodes,

 

r( N ) = nN / ( yN + nN ) and PL = ( nL + yL ) / ( nP +yP )

 

nN : number of products not chosen by user at node N

yN : number of products chosen by user at node N

Figure 2 : A decision tree generated from the users feedback about his likes and dislikes for a list of products.

Figure 3 : A UIH generated from the decision tree in Figure 2.

 

It is seen from the results that with the increase in threshold (i.e., choosiness of the user), the number of products retrieved decreases in a linear fashion. The variation in the attribute values does not show much dependency on the threshold initially but decreases very rapidly after a certain value. The behavior is almost the same for both similarity measures (the figures illustrate results for the second measure).

 

 
5 Discussion

 

We proposed a software architecture for a personalized product catalog. Studies can be made for performance improvement by considering various similarity metrics and matching algorithms, and methods for on-line and off-line construction of user interest hierarchy. The present article presents one such method for the task of dynamic generation of a product catalog. The impact of this software architecture can be tested from the user satisfaction from their feedback.

 

A dual problem in the B2C paradigm is to dynamically select customers (users) for targeting certain products or advertisements so that the expected click-through is maximized. In order to perform this dual task, a customer graph (CG) may be maintained instead of a product graph where each customer is connected to every other customer based on some similarities of their profiles.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Figure 4 : The nature of variation in the number of products and different product attributes with the threshold .

 

 
 

 

References :

 

(1)        M.S. Lee and A. W. Moore, Learning Automated Product Recommendations without Observable Features : An Initial Investigator, The Robotics Institute, Carnegie Mellon University, pp. 1-35 (April 1995).

(2)        D. M. Chickering and D. Heckerman, Targeted Advertising with Inventory Management, Proc. ACM Electronic Commerce, pp. 17-20, 2000.

(3)        L. Brieman et al. Classification and Regression Trees, Wadsworth, Belmont, California, 1984.

(4)        A. Prestchner and S. Gauch, Personalization on the web, Technical Report ITTC-FY2000-TR-13591-01, Dept. of Electrical Engineering and Computer Science, University of Kansas, USA.

(5)        M. Pazzani, A framework for collaborative, content-based and demographic filtering, Artificial Intelligence Review, pp. 393-408, 1999.

(6)        D.H. Widyantoro, T.R. Iorger, and J.Yen, An adaptive algorithm for learning changes in user interests, Proc. CIKM, Kansas, 405-412, 1999.

(7)        S. Santini and R.C. Jain, Similarity measures, IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 2, pp. 871-883, 1999.