A New Genetic Algorithm Recommender System for Achieving Customer-Seller Win-Win Quiescent Point

INTRODUCTION

During recent years, the growth of internet has led to the development of recommender systems (Chen and Cheng, 2008). Recommender systems are an effective way to increase customer satisfaction and consequently, customer loyalty. These systems improve cross-selling by suggesting additional products to purchase. Generally recommender systems can be divided into three main categories: content-based, Collaborative filtering and Hybrid methods (Adomavicius and Tuzhilin, 2005; Balbanovich and Shoham, 1997). Among these categories the CF (Collaborative Filtering) has been the most popular one in recommender systems design. The term collaborative filtering was first used by Goldberg et al. (1992) and Iijima and Ho (2007).

Market segmentation is also one of the ways that attempts to discover the classes in which the consumers can be naturally grouped, according to the information available (Kim and Ahn, 2008).

In addition, K-Means clustering is the most frequently used market segmentation technique among the clustering techniques (Gehrt and Shim, 1998). Learning preferences is also a useful task in application fields such as collaborative filtering. Obtaining preference information may be easier and more natural than obtaining the labels needed for a classification or regression approach (Cohen et al., 1999; Diez et al., 2008).

Enterprises have been developing new business portals and providing large amount of product information to create more business opportunities and to expand their markets (Cho et al., 2002; Kim and Lee, 2005; Lee et al., 2002). Recommender systems have been widely used in many web sites, such as Amazon.com, CDNOW.com, Grouplens, MovieLens, etc. (Montaner et al., 2003). Most of recommender systems adopt two type of techniques, the Content-Based Filtering (CBF) and Collaborative Filtering (CF) approaches (Resnick and Varian, 1997).

With the CBF approach, the system recommends items similar to those a certain user has liked in the past (Lawrence et al., 2001; Montaner et al., 2003). The CF models can be constructed based on user or items (Hwang and Tsai, 2005). That means recommendations by CF models can be based on the rating of items and behavior of users (Montaner et al., 2003). In CF approach, the system identifies users whose tastes are similar to those of the active user and recommends items which they have liked (Sarwar et al., 2000).

Most recommendations are traditionally made merely on purchasing possibility and customers’ preferences. However, that is not enough for an enterprise. Profit margin is another crucial factor for sellers (Chen et al., 2008). Chen et al. (2008) integrated the profitability factor into traditional systems. Their study intends to more properly balance the views between customers and sellers.

The two proposed recommender systems by Chen et al. (2008), named CPPRS and HPRS, study on the basis of the purchase profitability and the product profitability. Since there are other factors that affect agreement between customer and seller, another approach is proposed in this study that searches for a quiescent point through the negotiations between them. The main strategy of this approach is to find a situation in which both sides feel an acceptable level of satisfaction. This point is called a win-win quiescent point and so present proposed recommender system is named win-win QPRS.

PROBLEM DESCRIPTION AND PROPOSED ALGORITHM

Most recommender systems take into account only customer satisfaction. In practical situations, there is another approach for completing the negotiations between seller and customer. The win-win strategy should be applied to achieve a quiescent point. That is a situation in which both the seller and the customer feel they have enough benefits in the present purchase. For example, consider the process of buying a house. The seller offers a price for a house and the buyer announces the needs and preferences, including the qualities and quantities, but after some negotiations between them a point of compromise should be reached. In electronic commerce, the interaction between two sides of purchase activity is usually carried out through the interface pages of a web site. So, it is better to use an algorithm that gathers necessary data from both sides and gives suitable recommendations such that a quiescent point is achieved. In this study a new algorithm is demonstrated that uses a win-win strategy. In addition to the preferences and needs of the customer the priorities of the seller are entered to the system. The proposed system tries to find a quiescent point that is satisfactory to both sides. Throughout the study this algorithm is called Win-Win-QP algorithm.

Definition of parameters: The parameters that are used in the proposed algorithm are defined as follow:

•	Effective factors (F_i): These are factors that may affect decision making by both customer and seller. Quality of product, price and model are examples of effective factors
•	Customer Satisfaction, CS (F_i): Achieving each factor causes a satisfaction value in customer’s opinion. This value is entered to the system through the customer interface
•	Seller Satisfaction, SS (F_i): Achieving each factor causes a satisfaction value in seller’s opinion. This value is entered to the system through the seller interface
•	Customer Importance level, CI (F_i): Each of the effective factors have different level of importance in customer’s opinion. The values of CI (F_i) are entered to the system through customer interface
•	Seller Importance level, SI (F_i): Each of the effective factors have different level of importance in seller’s opinion. The values of SI (F_i) are entered to the system through seller interface
•	Customer Pleasure, CP (F_i): Each value of the effective factors that is suggested causes a pleasure value for the customer. This value is the product of CI (F_i) and CS (F_i)
•	Seller Pleasure, SP (F_i): Each case of effective factors that is suggested causes a pleasure value for the seller. This value is the product of SI (F_i) and SS (F_i)
•	Total Customer Pleasure, TCP: This is the sum of all customer pleasure values according to different factors
•	Total Seller Pleasure, TSP: The sum of all seller pleasure values according to different factors

Flowchart:

Step 1:

The general procedure of Win-Win-QP Algorithm is introduced. As shown in Fig. 1, in the first step interests and preferences of both customer and seller are entered to the system


Fig. 1:	General procedure of win-win-QP recommender system

In fact the customer gives the first suggestion for the features of item. This suggestion provides us with a specified value of satisfaction and pleasure in both sides. The system calculates these values and decides if a modification is needed in the first suggestion. The criterion for accepting a suggestion is reaching a point in which the value of pleasure of both sides is acceptable. If necessary, modification will be done and again the evaluation will be repeated until the quiescent point is achieved.

Step 2:	Enter the satisfaction levels due to each factor from the seller and customer opinion (through the user interface of the system and put into Tables 1 and 2)
Step 3:	Enter the importance of each factor from the opinion of customer and seller (entered through the user interface of the system and put into Table 3)
Step 4:	Enter the first suggestion of customer and set it as the first point of negotiation (through the user interface of the system)
Step 5:	Get the marginal acceptable value of difference between the customer pleasure and seller pleasure and M denotes this value
Step 6:	Calculate the value of customer and seller pleasure according to each factor in the given suggestion by the following formulas:

CP (F_iz) = CI(F_i)xCS(F_iz)
SP (F_iz) = SI(F_i)xSS(F_iz)

Step 7:	Calculate the total value of pleasure of seller and customer by adding the current pleasure values of all factors. Name them as TSP and TCP
Step 8:	Calculate the difference between the TSP and TCP by the following formula:

Table 1:	Customer Satisfaction CS (F_iz)

Table 2:	Seller Satisfaction SS (F_iz)

Table 3:	Customer and seller importance levels

Diff = (Max CP-Max SP)/[0.5(CP+SP)]

So, the objective function is:

O.F: Minimize (Max TCP-Max TSP)

where, Max TCP and Max TSP in each step are the earlier values of TCP and TSP.

Step 9:	The main criterion for processing each step is as follows:
IF 0<Diff<M: Then the suggestion is finalized
Otherwise: Modify the suggestion

It means that the difference between the currently calculated TCP and TSP (named Diff) should be compared. If it is not placed inside the allowed margin the suggestion should be modified as follows:

•	Find the factor with minimum importance level among the customer’s opinion. Change this factor from z to z’ state. This change should satisfy the following two constrains simultaneously:
CS (F_iz’)-CS (F_iz)<0 SS (F_iz’)-SS (F_iz)>0
•	Recalculate Diff. If it is inside the acceptable margin M, so the suggestion is finalized. Otherwise go to previous sub-step a
•	Continue by using the next factors until M reached inside the allowed region

Step 10:

Recommend the best fitted suggestion, using the last step of modifications

A SAMPLE SIMULATION OF THE WIN-WIN-QP ALGORITHM

For more convenience and clarity, a sample clothing e-shop is used as an example, where, a customer decides to buy an overcoat and thereby the negotiations between seller and customer are started.

Consider that n factors are affecting the decision-making of both seller and customer. Let F = {F_i}, i = 1,..,n be the set of effective factors. Each of these factors should have z cases. Let F_i = {F_iz}, i = 1,..,n and z = 1,..,Z be the set of cases of factors.

Example 1: Consider a clothing e-shop. A customer decides to buy an overcoat. The effective factors are as follow:

F = {F₁, F₂, F₃} = {model, price, material}

Model of overcoat has three cases:

•	F₁ = {F₁₁, F₁₂, F₁₃} = {past model, finishing season model, new model}. Similarly the price and material have cases as follow:
•	F₂ = {F₂₁,F₂₂,F₂₃} = {low, medium, high}
•	F₃ = {F₃₁,F₃₂,F₃₃} = {plastic, synthetic leather, natural leather}

When the customer decides to buy something, some of the effective factors have more priority and importance. Let CI (F_i) be the degree of importance of factor F_i in the customer’s opinion. Similarly let SI (F_i) be the degree of importance of a factor F_i in the seller’s opinion.

If the needs and preferences of the customer are to be satisfied, a considerable value of satisfaction will be achieved. Let CS (F_iz) and SS (F_iz) be customer and seller satisfaction functions due to the effective factors, respectively.

Example 2: Table 1 and 2 show the levels of customer and seller satisfaction, named CS (F_iz) and SS (F_iz), according to each effective factor in example 1. The range of satisfaction is considered between 0 and 10. The highest level of satisfaction is 10.

When a customer decides to buy an item, some factors are more important in decision-making. For example it might be very important to find the favorite model, but the price and material have lower importance. This depends on many factors such as age of customer, budget and application of purchased item and so on. Table 3 shows the degree of importance of a factor like F_i in the customer’s and the seller’s opinions, CI (F_i) and SI(F_i), in example 1. The query interface form in e-shop website is used to gather all of these values. A value of 10 for CI (F_i) or SI (F_i) is considered as maximum importance level and zero is the lowest level of importance. Table 3 shows that for the active customer, the model of purchased clothing is very important (CI (F₁) = 10), where as the material is not too important (CI (F₃) = 5).

The values of pleasure of customer (CP) and of seller (SP) due to each selection can be calculated by Eq. 1 and 2.

CP (F_iz) = CI (F_i)×CS (F_iz)

(1)

SP (F_iz) = SI (F_i)×SS (F_iz)

(2)

Example 3: The pleasure matrices for customer and seller of example 2 are briefly shown in Table 4 and 5, respectively only some necessary entries are shown.

Table 4:	Pleasure values of customer (CP) due to factors

Table 5:	Pleasure values of Seller (SP) due to factors

ow suppose that all the needs and preferences announced by the customer are accepted. The data include new model, medium price and natural leather that correspond to {F₁₃, F₂₂, F₃₁}. Then the total pleasure value of the customer can be calculated as: TCP = 100+40+50 = 190 (Underlined number in Table 4 are used).

Similarly, the total pleasure value of the seller can be calculated as follows:

TSP = 56 + 35 + 14 = 105 (Underlined numbers in Table 5 are used).

Comparing the last two numbers, it can be concluded that the level of seller pleasure is far less than that of the customer. For achieving a quiescent point, two objectives should be considered:

•	The pleasure values of each of the customer and the seller should be kept maximize
•	The difference between the two pleasure values should be minimized

So, the objective function is:

O.F: Minimize (Max CP-Max SP)

(3)

Consider the maximum allowed difference between customer and seller pleasure values is defined by M as follows:

Table 6:	Improving suggestion set according to importance values

0<(Max CP-Max SP)/[0.5(CP+SP)]<M

(4)

Example 4: Let M = 20%. Then by using the calculated values of CP and SP in example 3 the following can be inferred:

(190-105)/[0.5(190+105)] = 0.576*100% = 57.6%>M

While the above-mentioned criterion is not verified, the process of updating CP and SP values must be repeated.

Hence, Eq. 3 and 4 should be used for maximizing CP and SP.

The above procedure is shown in Table 6, where:

•	ΔCS and ΔSS, respectively are the changes in customer and seller satisfaction values due to change in state of factors
•	ΔTCP and ΔTSP are the changes in total values of customer and seller pleasures, respectively, such that: ΔTCP = ΔCSCI, ΔTSP = ΔSSSI
•	New TCP = (Previous value of TCP)+ ΔTCP
•	New TSP = (Previous value of TSP)+ΔTSP

As is shown in the fourth row of Table 6, the final suggestion is {F₁₃, F₂₃, F₃₂} that corresponds to new model, high price and synthetic leather. The material factor is changed in first row because it has the least value of importance for customer (CI (F₃) = 5). In third row, changing F₃₂ to F₃₃is not allowed since it would cause decrease in both customer and seller satisfaction values. Therefore no modification is performed for the decrease in the gap between them. The next level of importance is that of F_2.. So, the next step of modification is performed on F₂.

In database of the recommender system the items are categorized into price classes, material groups and model categories. In the above example, the recommender system finally suggests purchasing an item having high price but new model with synthetic leather material. Such an item would satisfy both seller and customer within an acceptable margin.

GENETIC ALGORITHM IMPLEMENTATION

The genetic algorithm is considered as a useful method for finding the best fitted solutions in the proposed algorithm. For the above example, the chromosomes are considered with a 9 bit structure including three genes, according to the three effective factors named model, price and material. Each gene contains 3 bits of 0 or 1, resulting 8 states. But since each factor in this example has only three states, so, the value of each gene is divided by 3 and the remainder is considered as the final value of gene. The fitness function is calculated as follows:

Fitness = (Absolute value of ((TCP-TSP)/
(0.5x(TCP+TSP)))×100%

The population of chromosome pool is considered 4 and the first population is produced randomly. For the next generation, first a random number is produced, if it is less than 0.8 cross over is done in a random place. Again a random number is produced and if it is less than 0.2 the mutation is done. The fitness value is calculated and is compared with the marginal difference of pleasure of seller and customer. The generations are reproduced until the value of fitness is reached inside the desired margin. Figure 2 shows the user interface of the program. The customer enters the favorite model, price and material. Also both the seller and customer enter their preferences and importance levels due to each of the effective factors.

At the first, the program announces that the value of satisfaction of seller and customer is or is not inside the selected margin (10% in this example). Then the genetic algorithm produces new recommendations until it reaches the final quiescent point.

RESULTS

In the first run, the customer suggests to buy an overcoat of new mode, medium price and natural leather, as shown in Fig. 2. This suggestion causes a 57% difference between pleasure value of seller and customer. So, this can not be considered as the quiescent point. The GA starts to make new suggestions and finally reaches a difference value of 8%, which is inside the desired level, as shown in Fig. 3. At this point, a finishing mode overcoat with medium price and natural leather is recommended to both seller and customer.

In the second run, the importance levels of customer and seller are changed but the same initial suggestion is made by the customer. The GA algorithm outputs more than one suggestion. As shown in Fig. 4, the difference value of pleasure levels of the third, fourth and fifth suggestions are placed inside the desired level.


Fig. 2:	User Interface of Win-Win-QA, initialization step


Fig. 3:	Comparison of pleasure levels in the first run


Fig. 4:	Comparison of pleasure levels in the second run

So, it is possible for both the customer and seller to choose one of them.

In the third run, the initial suggestion of the customer is changed. As shown in Fig. 5, two final suggestions are given to the customer and seller that have difference less than 10%. The initial suggestion of the customer was a new mode overcoat, cheap price and synthetic leather. The final suggestion by GA algorithm was a past mode overcoat with expensive price and natural leather.


Fig. 5:	Comparison of pleasure levels in the third run

CONCLUSION

When there is a high difference value of pleasure at the initial suggestion of the customer, the algorithm approaches a quiescent point that has better difference value, but not necessarily a higher value of pleasure of the both sides (Fig. 3). Changing the importance levels of seller and customer with the same initial suggestion leads to different solutions, but still approaching lowest value of difference of pleasures in final suggestions (Fig. 4).

Whenever the algorithm approaches to the desired solution very soon, it can give more and more new suggestions, all placing inside the desired margin of difference value of pleasure, but it losses the value of pleasure (Fig. 5). So, it is needed to combine the marginal difference value criteria with a minimum permitted value of customer pleasure. But notice that this case has the best approach to the trend of customer graph.

Genetic algorithm is useful in finding the best fitted suggestions. It is possible to change the marginal values of fitness function and get other results. In this approach 0.8 and 0.2 were selected for crossover and mutation based on our experience.

The algorithm reaches a point that both the customer and the seller feel they are winners. This leads to more probability of completing a purchase since both sides are satisfied. Although when the pleasure level of customer decreases, but reaching the quiescent point causes more trust and agreement between seller and customer. In many contracts this agreement is too important for starting the procedure of a successful business. In future studies, the procedure of making new suggestions could be improved and also a margin value of minimum pleasure for customer could be considered as criteria for decision-making. This means that during calculations the value of customer pleasure should not be less than a minimum value. More factors could be considered as effective factors. Changing the marginal value of desired difference of pleasure levels is another parameter that produces different suggestions.