TRES: A decentralized agent-based recommender system to support B2C activities

This is the authors' version of the paper. The final publication is available at Springer, via DOI: 10.1007/978-3-642-01665-3_19

TRES: A Decentralized Agent-based Recommender System to Support B2C Activities Domenico Rosaci and Giuseppe M.L. Sarn´e DIMET, Universit` a Mediterranea di Reggio Calabria Via Graziella, Localit` a Feo di Vito 89122 Reggio Calabria, Italy {domenico.rosaci, sarne}@unirc.it

Abstract. The increasing relevance assumed by the E-Commerce in the Web community is attested by the great number of powerful and sophisticated tools developed in the last years to support traders in their commercial activities. In this scenario, recommender systems appear doubtless as a promising solution for supporting both customers’ and merchants’ activities. In this paper, we propose an agent-based recommender system, called TReS, able to help traders in Business-to-Consumer activities with useful and personalized suggestions based on interests and preferences stored in customers’ profiles, adopting a fully decentralized architecture that suitably introduces in the system both scalability and privacy protection.

1

Introduction

In the last years, E-Commerce (EC) activities are playing a key role in the Web and this is attested by the increasing number of the commercial transactions electronically performed. In particular, a great attention has been reserved for the Business-to-Consumer (B2C) activities, comparable to the retail trade of traditional commerce [7, 15]. In the previously introduced scenario, recommender systems [10, 14] appear as a promising solution for both merchants and customers. The merchants can be advantaged by the improvement of the performances for their e-Commerce sites; the customers are supported in their decision-making process by means of some useful suggestions about objects, products, or services potentially interesting for them. To carry out such an activity, recommender systems need to exploit a suitable representation (profile) of the customer’s interests and preferences. This representation can be automatically derived by monitoring and interpreting the large amount of information that users spread during their Web trading activities by considering their purchase histories, Web logs, cookies, etc. and/or by using explicit ratings directly provided by the user. A well-known solution to implement recommender systems is represented by the agent technology in which software information agents [8]) autonomously and proactively perform some tasks on the behalf of their human users. The agentbased technology has been widely used in the EC context, also for providing

users with recommendations[12], and all these systems exploit the presence of a customer profile, representing how the customers evaluate the different products and product categories. An example of these systems is EC-XAMAS, presented in [9]. However, none of these systems evaluate the customer’s interest for a product considering each different stage of the EC in a different way. In other words, if a customer accesses to a product only to read its description, his interest for that product has to be considered very different from the case the customer actually buys the product. In the past, some behavioural models have been introduced to capture the different phases carried out in an EC process [1, 3, 4]. These phases involve activities performed by the customer before, during and after the visit of merchant sites. We point out that in this paper we do not deal with the activity of the customer for finding potentially interesting sites, but only with those activities performed by the customer when he accesses to a given site. Our purpose is to support the merchant of a site in generating useful recommendations for the customer, considering the three usual stages performed by the customer himself during the interaction with the merchant, namely: (i) a site visiting stage, where the customer visits a description of a product; (ii) a negotiation stage, where the customer negotiates the price of a product with the merchant and (iii) a buying stage, where the customer actually buys the product, sending an order. It is important to remark that the main difference between TRES on EC domain and meta-search engines [6] is the negotiation process . In particular, we base our approach on a multi-agent architecture, called Trader REcommender Systems (TRES). Specifically, in TRES each trader (customer or merchant) is associated with a software agent that constructs and stores an internal profile to take into account his whole Web trading history. The agents exploit their user’s profiles in their interaction, to make the merchants capable to generate effective recommendations. The architecture we have adopted is fully decentralized, giving to each merchant the capability to generate recommendations without requiring the help of any centralized computational unit. This characteristic, on the one hand, makes the system scalable with respect to the size of the users’ community. In Section 3, we show that the cost of our recommendation algorithm linearly increases with the number of customers present in the system. On the other hand, the privacy of each customer is preserved, since the merchant retrieves information about each customer simply monitoring the customer behaviour in visiting his site. To verify the effectiveness of TReS for generating suitable suggestions, we have implemented an agent platform, called Trader Agents Community (TAC), to support customers and merchants during all the three stages of a B2C process described above. TAC agents exploit their profiles to take care of the traders in a personalized and homogeneous way by means of reciprocal message-based interactions. As a result, customers will be provided during their EC-site visits with personalized Web presentations built on-fly exploiting the generated suggestions. The paper is organized as follows: in Section 2 we present the TAC framework and the activities performed by the agents in order to monitor customers’ be-

haviours. Section 3 describes the TReS recommendation algorithm. In Section 4 some experiments are presented to evaluate our proposal. Finally, in Section 5, we draw some final conclusions.

2

An Overview of the TAC Framework

In this section, the TAC framework will be described in detail. In such a framework each customer C (resp. merchant M ) is associated to a personal agent c (resp. m). Below we will describe the knowledge representation model, the structure of each agent and the trading support provided by the agents. 2.1

Representation of Objects and Categories of Interest

The TAC agents support traders in their commercial tasks for products that meet their interests. To this aim, all the TAC agents share the same Catalogue C, representing the common agent knowledge, that describes each product category (pc). Usually, each Web page includes more product instances belonging to different product categories. The TAC agents build their users’ profiles by monitoring all the product instances and product categories accessed by the customers in order to measure the associated interests. Moreover, to determine collaborative filtering recommendations, each merchant agent also computes the similarity among its visitors by exploiting the values of interest shown in the offered product instances. Currently, the TAC catalogue adopts the six digit edition of the NAICS coding [11], an official, public, hierarchical classification used in North America to classify businesses in categories. The catalogue is implemented by means of a simple XML-Schema [2] where a product category is described by using the notion of element and the product instances are represented by XML element instances. 2.2

The Agents

Each generic user (customer or merchant) U is associated to a personal agent a, which manages the User Profile (U P ) of U . U P stores user information in a tuple hU D, W D, BDi, where: – the User Data (U D) are personal U ’s data as name, address, etc. – the Working Data (W D) contains two system parameters called Memory (ω) and Pruning (σ) thresholds, that will be described in the following, and the current product catalogue C, that is a list of product instances. – the Behaviour Data (BD) of a user contains some parameters that describe the past behaviour of the user. Each parameter has a different meaning if the user is a customer or if he is a merchant. In particular, in the case U is a customer (resp. a merchant), BD is an array that contains, for each product category pc accessed by the customer (resp. in which the merchant offers

some product), two components, called pcR and Lpc . The first component pcR represents the interest in the category pc. The second component Lpc is a list of elements, where each element lpi of Lpc is associated with a product instance pi belonging to the category pc, visited by the customer (resp. offered by the merchant). In particular, the element lpi contains some data relative to the behaviour of the customer in accessing pi (resp. the behaviour of all the customers that accessed pi) and in particular the parameter piR that represents the interest in that product instance. These data are shown in Table 1. Name Customer Merchant LV D last visit date to pi last access of a customer to pi PD Product Data of pi Product Data of pi L List of merchants that sell pi List of customers that accessed to p piR Interest rate for pi Interest rate for pi Table 1. Parameters contained in the Behavioural Data BD

Note that the meaning of the interest rates pcR and piR is different for the customer and the merchant. In particular, the pcR of a product category pc for the customer represents the customer’s interest for pc, while for the merchant it represents the interest shown by all the customers that visited products belonging to pc in the merchant’s site. Analogously, the piR of a product instance pi for the customer represents the customer’s interest for pi while for the merchant it represents the interest of all the customers that visited pi in the merchant’s site. The behaviour of an agent is as follows. When a customer visits the EC site associated with a merchant, both the customer’s and the merchant’s agent monitors the customer’s behaviour in his/her visit. Then, as a consequence of such a monitor activity, a customer (resp., a merchant) agent could take into account, with respect to a product instance pi belonging to a product category pc, the interest rate piR for that instance and the interest rate pcR for that category. More in detail, to show how an agent computes pcR (resp. piR), we adopt the following formulation: piR = ω · pcR = ω ·

ρi log10 (10+Ni ) ρi log10 (10+Ni )

+ (1 − ω) · + (1 − ω) ·

piR log10 (10+∆) pcR log10 (10+∆)

This formulation shows that piR (resp. pcR) is computed as a weighted sum of two contributions. The first contribution, weighted by ω, represents the effect of a customer’s visit to the involved product instance (resp. category) in the current stage i. This contribution is computed as the ratio between the parameter ρi (belonging to [0..1], that measures the importance given by the customer to the

stage i (ρi = 1 means maximum importance), and the value log10 (10+Ni ), where Ni is the number of times the same stage i has been performed for the same product (resp. category) in the same day. This means that repeated accesses to the same product instance (resp. category) in the same stage are considered with a (logarithmic) decreasing importance, since they are not actually “new” accesses to the product (resp. category). The second contribution, weighted by 1 − ω, represents the effect to the past activities of the customer with respect to the involved product instance (resp. category). High values for the ω parameter give more relevance to the most recent access and vice versa. Moreover, ∆ is the temporal distance expressed in days between the date of the current visit and the last visit LV D with respect to the visited pi (resp., pc). Note that the logarithmic decreasing we have adopted in the formulas above is an arbitrary choice, fruitfully tested in our experiments. 2.3

The Trading Support

TAC is a message-based framework designed to transfer, in a consistent and efficient way, the business information in order to permit of supporting and monitoring the activities carried out in a B2C process by merchant and customer agents. The different activities occurring within a B2C process require the exchange of several message typologies that will be briefly described below. Note that, in the adopted formulation, the first subscript of a message identifies the sender while the second identifies the receiver. Moreover, we denote by data an XML document, whose content is structured in three sections: (i) Header, containing sender, receiver, EC stage, and product identifier; (ii) Products, that stores the product data; (iii) Financial, relative to all the financial information needed to perform a payment. – IN Fx,y (data): it requires/provides commercial information about a product; – REQ IN Vc,m (data): it requires an invoice for a product offered by a merchant m; – IN Vm,c (data): it contains the invoice required with REQ IN Vc,m (data); – P Px,y (data): it is used to negotiate any commercial detail not fixed or specified (i.e., the price for products without fixed price); – P Oc,m (data) (resp., P O Am,c (data) or P O Rm,c (data)): it is the purchase order with respect to IN Vm,c (data) (resp., the notify of acceptance or rejection); – M T Oc,m (data) (resp.,M T O Am,c (data) or M T O Rm,c (data)): it notifies that the payment has been performed (resp., received or not received); EC-site Visit Support stage (s=1) During an EC-site visit a customer sends the message IN Fc,m to a merchant for requiring commercial information about an offered product and he/she in his/her turn will answer with another message IN Fm,c containing the required information. Negotiation Support stage (s=2) In this stage are fixed all the trading details as price, quantity, delivery modality and so on. More in detail, this

stage starts with the messages REQ IN Vc,m and IN Vm,c exchanged between the traders. If the customer accepts the customer’s commercial proposal contained in IN Vm,c , then this stage ends. Otherwise, if it is possible, the two traders use in an alternative manner P Px,y messages to negotiate all the trading details; when an agreement has been achieved, then the REQ IN Vc,m and IN Vm,c messages will be again exchanged. Purchase Support stage (s=3) After the “Negotiation” step, if the customer wants to purchase a products he/she sends the message P Oc,m to the merchant that can accept/refuse by means of P O Am,c (data)/P O Rm,c (data). If the purchase order is accepted, then the customer performs the payment and informs the merchant with an M T Oc,m message; after this, the customer receives an M T O Am,c (resp. M T O Rm,c ) message to confirm he has received (resp. he has not received) the payment.

3

The Recommendation Algorithm

In this section we present the recommendation algorithm exploited by TReS to generate useful suggestions by using both a content-based and a collaborative filtering approach. When a customer visits the site of a merchant, the algorithm is executed by the merchant’s agent to generate suggestions for the customer. The algorithm exploits the information stored into both the merchant’s agent and the customer’s agent and generates a list of product instances contained in the merchant’s site appearing as the most promising to meet the customer’s interests. The behaviour of the algorithm is represented by the function Recommend (Figure 1). The input of this function is the customer’s agent c and its outputs are the lists L3 and L4 of product instances exploited by the merchant m to build an on-fly personalized Web site presentation for c. Within this function, the auxiliary function extract pc is called; it receives as input the BD section of the m’s profile and returns the list L1 containing those product categories belonging to the catalogue C of the merchant m. Then m sends the list L1 to c by using the function send, while the function receive waits for the response of c, consisting in the list L2. This list includes the v product categories that better meet the interests of the customer (where v is an integer parameter arbitrarily chosen by c). When L2 is received, the function contentbased pi is called and returns the list L3 containing the first y product instances having the highest rates for each of the v product categories stored in L2 (also y is a parameter arbitrarily set by m). The next step deals with the generation of collaborative filtering recommendations. First, the algorithm constructs the array of lists P C, where each array element is a list associated to a customer i that accessed the site in the past and contains the v most interesting product categories. To this aim the function customersInterests is called, receiving the BD data of the profile of m and the integer v as input. Each array element P C[i] is a list constructed (i) by computing for the user i the average apc of the piR values of all the product

instances for each product category pc (this average represents a global measure of the agent interest in pc) and (ii) by ordering all the apc values in a decreasing order and (iii) by selecting, for each user, the v product categories having the highest apc values. When P C has been computed, the function collaborativefiltering pi is called; it receives in input the list L2 (provided by c), the array of lists P C, the BD section of the merchant agent’s profile and the two integers z and x, arbitrarily set by m. This function exploits P C to compute the similarity degree between c and the customers that have interacted with m in the past; this measure will be used by m to select the z agents most similar to c. Thus, for each product category in L2 considered by c, all the product instances having the higher piR are selected and inserted in the list L4. The list L4 contains, for each of the z customers most similar to c, the x product instances with the highest rate. More in detail, the similarity between the customer c and a generic customer k that visited in the past the merchant’s site is computed as the average of the contributions lpc associated with the product categories common to the list L2 provided by the customer c and the list P C[k] associated to the customer k in the merchant’s profile. For example, suppose that the product category pc belongs both to L2 and P C[k]; also suppose that the interest rate of pc in L2 is equal to r while the interest rate of pc in P C[k] is equal to s. In this case, the contribution lpc of pc to the similarity between c and k is equal to |r − s)|. The overall similarity between c and k is computed as the average of all the lpc values. On the customer agent side, when the list L1 coming from the merchant agent m is received, the function categoriesOfInterest is executed. This function calls the function extract pc to obtain the list L5 containing the product categories of interest for c. After that, the function intersection pc is called and the intersection L1 ∩ L5 is computed. The function select pc receives as input the list L6 and an integer v and then it orders L6 in a decreasing order based on the pcR value of the customer’s profile; finally, it returns the first v product categories. The resulting list is the new L2, returned as the output of categoriesOfInterest. In order to preserve customer’s privacy, we observe that TReS faces such an issue in a simple and effective way. Specifically, the customer sends to the merchants only the selection of interesting category it has internally performed, without revealing its profile. In other words, the selection of the interesting category is done on the customer side. On the other hand, the merchant’s generates the collaborative filtering recommendations without revealing to the customer any data relative to other customers, operating in this case on the merchant side. Now we analyze how the time cost required by TRES to perform the recommendation task. In this analysis, we denote by n, p and q, the number of customers, the number of different categories present in the catalogue, and the number of maximum product instances in a category, respectively.

void Recommend(customerAgent c, ListOfProductInstancesL3, ListOfProductInstancesL4) { ListOfProductCategories L1=extract pc(m.UP.BD); send(L1,c.Ad); ListOfProductCategories L2=receive( ); ListOfProductInstances L3=contentbased pi(L2, m.UP.BD, y); ListsOfCustomersInterests P C[ ]=customersInterests(m.UP.BD, v); ListOfProductInstances L4=collaborativefiltering pi(L2, P C[ ], m.UP.BD, z, x); return; } ListOfProductCategories categoriesOfInterest(ListofProductCategories L1) { ListOfProductCategories L5=extract pc(c.UP.BD); ListOfProductCategories L6=intersection pc(L1, L5); ListOfProductCategories L2=select pc(L6,v); return L2; }

Fig. 1. The TRES recommendation algorithm.

More in detail, the function extract pc computes the product categories of interest for c by comparing the number of items in the site catalogue with those present in the customer’s profile presenting a cost O(p2 ). The function contentbased pi examines q product instances for each one of the v product categories contained in L2. By considering that in the worst case v is equal to p, the cost of this function is O(p · q). The function customersInterests considers q product instances for each one of the v product categories selected by c for each of the n (in the worst case) users. The cost of this function is O(n · p · q). Finally, the function collaborativefiltering pi computes the similarity between the customer c and the other p customers by analyzing the v product categories selected by c with the product categories stored in the profiles of the other customers. The cost of collaborativefiltering pi is thus O(n·p2 +p·q). By considering that the number of product instances of a seller is usually greater than the number of product categories included in the catalogue, it is reasonable to assume that p is greater or equal to q. In this case, the computational cost of the function Recommend results mainly influenced by the cost of the function customersInterests and can be assumed as O(n · q 2 ). On the customer side the computational cost of productOfInterest is O(p2 ). In fact, the function extract pc and intersection pc have a computational cost O(p2 ), while the function select pc is driven by the computational cost of the used sort algorithm that we can assume as O(p · logp).

4

Experiments

In this section, we present some experiments devoted to show the effectiveness of TRES to generate useful suggestions for supporting users during their B2C activities. The experiments presented below have been realized by using a TAC prototype, developed in JADE [5]).

Table 2. Performances of different TRES compared to EC-XAM AS in the generation of suggestions (global/content-based/collaborative filtering). T RES

EC-XAM AS

Pre 0.874/0.808/0.847 0.663/0.648/0.655 Rec 0.835/0.812/0.824 0.613/0.584/0.611 F 0.841/0.804/0.831 0.636/0.605/0.633

For this experiment we have (i) built a family of 18 XML EC Web sites by using the NAICS coding as common vocabulary, represented by a unique XML Schema, with 760 product instances belonging to 9 NAICS categories and (ii) monitored a set of real users in their B2C activities within the TAC framework. The first 9 sites has been used to obtain an initial profile of the customers’ interests and preferences without to exploit any recommendation support and to determine the value of the ρ parameters. Based on such profiles and ρ values the recommendations have been generated by the merchant agents relatively to the other 9 sites. We have compared the performances of TRES with a classical recommender system approach, namely EC-XAMAS [9]. The main difference between ECXAMAS and TRES is that EC-XAMAS does not consider the different EC stages to compute the interest rates. Instead, both TRES and XAMAS needs an initialization process to collect user interests To evaluate the results of the experiments, we have inserted in a list, called A, the product instances suggested by the merchant agent and in a list, called B, the corresponding customer’s choices. We have compared the corresponding elements in the two lists in order to measure the effectiveness of the proposed suggestions. In particular, we have adopted some standard performance metrics, namely precision, recall and F-measure [13]. Precision is defined as the share of the product instances actually visited by the customer among those recommended by the system. Recall is the share of the product instances suggested by the system among those chosen by the customer. F-Measure represents the harmonic mean between Precision and Recall. The performance of the content-based and collaborative filtering components have been considered both in an integrated way and separately for the two approaches. The parameters v, y, z and x of TRES have been set to 2, 3, 2 and 3, respectively (see Section 3). In terms of results (see Table 2) TRES outperforms the approach EC-XAMAS with respect to all the three measures. In particular, the F-measure of TRES is better than EC-XAMAS with respect to global, content-based and collaborative filtering component of about 32 percent. We argue that the better results of TRES with respect to EC-XAMAS are due to the more sophisticated modelling of the customer’s behaviour of TRES, that consider all the stages of the B2C process, while EC-XAMAS model the whole process in a uniform way. This ppropriate modelling is usefully exploited by TRES when generating recommendations, that thus result very effective.

5

Conclusion

This paper presents a recommender system, called TRES, able to act both as content-based and collaborative filtering recommender, to support traders in their B2C activities in a suitable and personalized way, taking into account customers’ interests and preferences. The customers’ privacy is assured since the customer does not send any private information to the merchant, but autonomously select interesting items from the catalogue sent by the merchant. Some interesting results have been obtained by experimental simulations. The effectiveness of the suggestions generated by TRES are resulted better than a traditional recommender system that does not consider the different trading phases involved in B2C activities. Moreover, the fully distributed architecture makes the performances of TRES highly scalable in heavily accessed B2C environments.

References 1. J.F. Engel, R.D. Blackwell, and P.W. Miniard. Consumer Behaviour. Int. ed. The Dryden Press, London, UK, 1995. 2. Extensible Markup Language (XML) Schema URL. http://www.w3.org/XML/Schema. 2008. 3. S. Feldman. The Objects of the E-Commerce, Keynote speech at ACM 1999 Conf. on OOPLSA, Denver, 1999. http://www.ibm.com/iac/oopsla99-sifkeynote.pdf, 1999. 4. R. H. Guttman, A. Moukas, and P. Maes. Agents as Mediators in Electronic Commerce. Electronic Markets, 8(1), 1998. 5. Java Agent DEvelop. framew. (JADE) URL. http://jade.tilab.com/. 2008. 6. J.J Jung. Ontological framework based on contextual mediation for collaborative information retrieval. Information Retrieval, 10(1):85–109, 2007. 7. R. J. Kauffman and E. A. Walden. Economics and Electronic Commerce: Survey and Directions for Research. Int. J. Electr. Com., 5(4):5–116, 2001. 8. P. Maes. Agents that Reduce Work and Information Overload. Commun. ACM, 37(7):30–40, 1994. 9. Pasquale De Meo, Domenico Rosaci, Giuseppe M. L. Sarn`e, Domenico Ursino, and Giorgio Terracina. Ec-xamas: Supporting e-commerce activities by an xml-based adaptive multi-agent system. Appl. Artif. Intell., 21(6):529–562, 2007. 10. M. Montaner, B. Lopez, and J.L. de la Rosa. A Taxonomy of Recommender Agents on the Internet. J. on Web Semantics (JWS), 19(4):285–330, 2004. 11. North America Industry Classifications (NAICS) URL. http://www.census.gov/naics/2007/index.html. 2008. 12. L. Palopoli, D. Rosaci, and D. Ursino. Agents’ roles in b2c e-commerce. AI Commun., 19(2):95–126, 2006. 13. C. J. van Rijsbergen. Information Retrieval. Butterworth, 1979. 14. K. Wei, J. Huang, and S. Fu. A Survey of E-Commerce Recommender Systems. In Proc. of the 13th Int. Conf. on Service Systems and Service Management, pages 1–5, Washington, DC, USA, 2007. IEEE Computer Society. 15. V. Zwass. Electronic Commerce and Organizational Innovation: Aspects and Opportunities. Int. J. Electron. Com., 7(3):7–37, 2003.