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 (Fi): 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 (Fi): Achieving each
factor causes a satisfaction value in customers opinion. This value
is entered to the system through the customer interface |
• |
Seller Satisfaction, SS (Fi): Achieving each factor
causes a satisfaction value in sellers opinion. This value is entered
to the system through the seller interface |
• |
Customer Importance level, CI (Fi): Each of the
effective factors have different level of importance in customers
opinion. The values of CI (Fi) are entered to the system
through customer interface |
• |
Seller Importance level, SI (Fi): Each of the
effective factors have different level of importance in sellers opinion.
The values of SI (Fi) are entered to the system through
seller interface |
• |
Customer Pleasure, CP (Fi): Each value of the
effective factors that is suggested causes a pleasure value for the
customer. This value is the product of CI (Fi) and CS (Fi) |
• |
Seller Pleasure, SP (Fi): Each case of effective
factors that is suggested causes a pleasure value for the seller.
This value is the product of SI (Fi) and SS (Fi) |
• |
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 (Fiz) = CI(Fi)xCS(Fiz)
SP (Fiz) = SI(Fi)xSS(Fiz)
|
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 (Fiz) |
|
Table 2: |
Seller Satisfaction SS (Fiz) |
|
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 customers
opinion. Change this factor from z to z state. This change should
satisfy the following two constrains simultaneously: |
CS (Fiz)-CS (Fiz)<0
SS (Fiz)-SS (Fiz)>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 = {Fi }, i = 1,..,n be the set of effective factors.
Each of these factors should have z cases. Let Fi = {Fiz},
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 = {F1, F2, F3}
= {model, price, material} |
Model of overcoat has three cases:
• |
F1 = {F11, F12, F13}
= {past model, finishing season model, new model}. Similarly the price
and material have cases as follow: |
• |
F2 = {F21,F22,F23} =
{low, medium, high} |
• |
F3 = {F31,F32,F33} =
{plastic, synthetic leather, natural leather} |
When the customer decides to buy something, some of the effective factors
have more priority and importance. Let CI (Fi) be the degree
of importance of factor Fi in the customers opinion. Similarly
let SI (Fi) be the degree of importance of a factor Fi
in the sellers opinion.
If the needs and preferences of the customer are to be satisfied, a considerable
value of satisfaction will be achieved. Let CS (Fiz) and SS
(Fiz) 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 (Fiz)
and SS (Fiz), 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 Fi in the customers and the
sellers opinions, CI (Fi) and SI(Fi), 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 (Fi) or SI (Fi)
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 (F1)
= 10), where as the material is not too important (CI (F3)
= 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 (Fiz) = CI (Fi)×CS
(Fiz) |
(1) |
SP (Fiz) = SI (Fi)×SS
(Fiz) |
(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 {F13, F22, F31}. 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 = ΔCS*CI,
ΔTSP = ΔSS*SI |
• |
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 {F13, F23, F32} 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 (F3) = 5). In third row, changing F32
to F33 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 F2.. So, the next step of modification
is performed on F2.
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.