Journal of Applied Sciences 9(2): 320-326, 2009 ISSN1812-5654 O 2009 Asian Network for Scientific Information A New Genetic Algorithm Recommender System for Achieving Customer-Seller win-Win Quiescent Point iA.A. Niknafs. 2A. Niknafs and M.E. Shiri Department of Computer Engineering, Shahid Bahonar University of Kerman, Kerman, Iran Department of Information Technology, Tarbiat Modares University, Tehran,Iran Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran Abstract: In this study, a new algorithm for considering the benefits of both customer and seller is proposed which is based on a win-win strategy in trade negotiations. This approach causes both sides to achieve a win quiescent point. In traditional commerce, this is done by negotiations between seller and customer. In this proposed method the preferences and needs of customer and seller are captured through the user interface. The algorithm compromises these two groups of factors and offers one or more recommendations that are satisfactory to both sides as much as possible. Although the system is designed based on the typical framework of collaborative filtering, yet it considers additional factor to item and customer that is the seller. The genetic algorithm is considered as a useful method for finding the best solutions for this problem. A simple example of e-negotiation between seller and customer is simulated and implemented using C No. and SQL server. The main application of the algorithm is in sophisticated ecommerce projects like tenders and contracts The experiments results show the feasibility of the system and both customer and seller satisfaction. Key words: Recommendation, collaborative filtering, decision support system, win-win strategy, customer INTRODUCTION as collaborative filtering. Obtaining preference information may be easier and more natural than obtaining the labels During recent years, the growth of internet has led to needed for a classification or regression approach the development of recommender systems(Chen and (Cohen et al., 1999, Diez et al., 2008) Cheng, 2008). Recommender systems are an effective way Enterprises have been developing new business to increase customer satisfaction and consequently, portals and providing large amount of product information customer loyalty. These systems improve cross-selling by to create more business opportunities and to expand their suggesting additional products to purchase. Generally markets(Cho et al., 2002; Kim and Lee, 2005; Lee et al recommender systems can be divided into three main 2002). Recommender systems have been widely used in categories:content-basedCollaborativefilteringandmanywebsitessuchasAmazoncomCdnoW.com, Hybrid methods(Adomavicius and Tuzhilin, 2005: Grouplens, MovieLens, etc (Montaner et al., 2003). Most Balbanovich and Shoham, 1997). Among these categories of recommender systems adopt two type of techniques the CF(Collaborative Filtering )has been the most popular the Content-Based Filtering( CBF)and Collaborative one in recommender systems design. The term Filtering(CF)approaches(Resnick and Varian, 1997 collaborative filtering was first used by Goldberg et al ith the CBF approach, the system recommends (1992)and Iijima and Ho(2007) items similar to those a certain user has liked in the past at Market segmentation is also one of the ways that (Lawrence et al., 2001; Montaner et al, 2003). The CF tempts to discover the classes in which the consumers models can be constructed based on user or items be naturally grouped, according to the information(Hwang and Tsai, 2005 ) That means re by available(Kim and Ahn, 2008) CF models can be based on the rating of items and In addition, K-Means clustering is the most behavior of users(Montaner et al., 2003). In CF approach, frequently used market segmentation technique among the system identifies users whose tastes are similar to the clustering techniques(Gehrt and Shim, 1998). Leaming those of the active user and recommends items which preferences is also a useful task in application fields such they have liked Sarwar et al., 2000) orresponding Author: Ali Akbar Niknafs, Department of Computer Engineering, Shahid Bahonar University of Kerman, 22 Bahman Blvd. Kerman, Iran Tel: +98 21 44443230 Fax: +98 21 444432
J. Applied Sci.,9(2):320-326,2009 Most recommendations are traditionally made merely Customer Satisfaction, CS(F): Achiev ing each on purchasing possibility and customers' preferences factor causes a satisfaction value in customer's However, that is not enough for an enterprise. Profit opinion margin is another crucial factor for sellers( Chen et al the customer interface 2008). Chen et al. (2008)integrated the profitability into traditional systems. Their study intends to more Seller Satisfaction, SS (F): Achiev ing each factor properly balance the views between customers and causes a satisfaction value in seller's opinion. This value is entered to the system through the seller The two proposed recommender systems by interface Chen et al.(2008), named CPPRS and HPRS, study on the Customer Importance level, CI(F): Each of the basis of the purchase profitability and the product effective factors have different level of importance in profitability. Since there are other factors that affect customer's opinion. The values of CI (F)are entered agreement between customer and seller, another to the system through customer interface approach is proposed in this study that searches for a. Seller Importance level, SI (FD: Each of the effective quiescent point through the negotiations between factors have different level of importance in sellers them. The main strategy of this approach is to find a opinion. The values of SI (F) are entered to the situation in which both sides feel an acceptable level of system through seller interface satisfaction. This point is called a win-win quiescent point Customer Pleasure, CP F): Each value of the and so present proposed recommender system is named effective factors that is suggested causes a pleasure win-win QPRS value for the customer. This value is the product of CI(F)and CS(FD) PROBLEM DESCRIPTION AND PROPOSED ALGORITHM Seller Pleasure, SP (F): Each case of effective factors that is suggested causes a pleasure value for Most recommender systems take into account only the seller. This value is the product of SI(F) and SS there is another approach for completing the negotiations Total Customer Pleasure, TCP: This is the sum of all between seller and customer. The win-win strategy should customer pleasure values according to rent be applied to achieve a quiescent point. That is a situation in which both the seller and the customer feel they have Total Seller Pleasure, TSP: The sum of all seller enough benefits in the present purchase. For example pleasure values according to different factor consider the process of buy ing a house. The seller offers a price for a house and the buyer announces the needs flowchart and preferences, including the qualities and quantities but after some negotiations between them a point of compromise should be reached. In electronic commerce Step 1: The general procedure of Win-Win-QP the interaction between two sides of purchase activity is lgorithm is introduced. As shown lt usually carried out through the interface pages of a web the first step interests and preferences of both site.So, it is better to use an algorithm that gathers customer and seller are entered to the system necessary data from both sides and gives suitable recommendations such that a quiescent point is achieved Part 1, Data entry: Prefer In this study a new algorithm is demonstrated that uses a user interface) including satisfaction levels and importance levels. strategy. In addition to the preferences and needs of the customer the priorities of the seller are entered to Part 2, Evaluation: Calculating the pleasure and satisfaction of the system. The proposed system tries to find a quiescent seller and customer due to the current suggestion, evaluating the result point that is satisfactory to both sides. Throughout the study this algorithm is called Win-Win-QP algorithm Part 3, Modification: Deciding ahout the suggestion. if it is not suitable for both sides of negotiation, modify it and repeat part Definition of parameters: The parameters that are used in the proposed algorithm are defined as follow: Part 4, Finalizing the suggestion: Give the final suggestion as a Effective factors (F): These are factors that may 1n-win quiescent point affect decision making by both customer and seller Quality of product, price and model are examples of Fig. 1: General procedure of win-win-QP recommender effective factors system
J. Applied Sci.,9(2):320-326,2009 In fact the customer gives the first suggestion fo Diff=(Max CP-Max SP)/[O5(CP+SP) features of item. This suggestion provides us with a specified value of satisfaction and pleasure in both sides the objective function is The system calculates these values and decides if a modification is needed in the first suggestion. The OF: Minimize(Max TCP-Max TSP criterion for accepting a suggestion is reaching a point in which the value of pleasure of both sides is acceptable If where, Max TCP and Max TSP in each step are the earlier necessary,modification will be done and again the values of TCP and TSP evaluation will be repeated until the quiescent point is Step 9: The main criterion for processing each step is as follows Step 2: Enter the satisfaction levels due to each factor from the seller and customer opinion(through IF O<Diff<M: Then the suggestion is finalized the user interface of the system and put into Otherwise: Modify the suggestion Tables 1 and 2) Step 3: Enter the importance of each factor from the It means that the difference between the currently opinion of customer and seller(entered through calculated TCP and TSP (named Diff)should b the user interface of the system and put into compared If it is not p l aced inside the allowed margin the suggestion should be modified as follows Table 3) Step 4: Enter the first suggestion of customer and set it as the first point of negotiation( through the user Find the factor with minimum importance level among interface of the system) the customer's opinion Change this factor from z to Step 5: Get the marginal acceptable value of difference z' state. This change should satisfy the following two constrains simultaneously: between the customer pleasure and seller pleasure and M denotes this value CS (Firn- CS(Fi<0 Step 6: Calculate the value of customer and seller SS(Fxy-SS(FO pleasure according to each factor in the given stion by the following formul Recalculate Diff. If it is inside the acceptable margin so the suggestion is finalized. Otherwise go to CP(F)=CI(F)XCS(Fi) previous sub-step a P(F1)=S(F)×SS(F1) Continue by using the next factors until M reached inside the allowed region Step 7: Calculate the total value of pleasure of seller and customer by adding the current pleasure values Step 10: Recommend the best fitted suggestion, using of all factors. Name them as TSP and TCP the last step of modifications Step 8: Calculate the difference between the TSP and TCP by the following formula A SAMPLE SIMULATION OF THE WIN-WIN-QP ALGORITHM le 1: Customer Satisfaction CS ( Fn) e-shop is used as an example, customer decides F ( Material) to buy an overcoat and thereb gotiations between seller and customer are started Table 2: Seller Satisfaction SS (Fn) Consider that n factors are affecting the decision- making of both seller and customer. Let F=F,3 ,n 10 be the set of effective factors. Each of these factors 3 should have z cases. Let F-Fi,i=I,n and z=1,Z be the set of cases of factors Table 3: Customer and seller importance levels 10 Example 1: Consider a clothing e-shop. A custom decides to buy an overcoat. The effective factors are follow
J. Applied Sci.,9(2):320-326,2009 F-F, F2, F,3=model, price, material y Table 4: Pleasure values of customer(CP) due to factors Model of overcoat has three cases Due to model factor F,=Fus Fu Fu=past model, finishing season model, new model;. Similarly the price and material have cases as follow: Due to price factor F2=F2, Fn, F233=(low, medium, highi F3-2F31F32, F333=aplastic, synthetic leather, natural Faz Due to material factor 50 of the effective factors have more priority and importance. F et CI(F) be the degree of importance of factor F, in the Table 5: Pleasure values of Seller (SP) due to factors customers opinion. Similarly let SI(F) be the degree of importance of a factor F, in the seller's opinion If the needs and preferences of the customer are to be Due to model factor achieved. Let CS(Fi)and SS(F ) be customer and seller F"2101046 satisfied, a considerable value of satisfaction will be F satisfaction functions due to the effective factors, Due to price factor 2468 Example 2: Table I and 2 show the levels of customer and Due to material factor seller satis faction, named CS(F 2)and SS (F ) according Fs 7 satis faction is considered between O and 10. Ihe huighest Faz level of satis faction is 10 Now suppose that all the needs and preferences When a customer decides to buy an item, some announced by the customer are accepted. The data factors are more important in decision-making. For include new model, medium price and natural leather that example it might be very important to find the favorite orrespond to F3, F22, F33. Then the total pleasure value model, but the price and material have lower importand of the customer can be calculated as: TCP= 100+40+50 This depends on many factors such as age of customer, 190(Underlined mumber in Table 4 are used budget and application of purchased item and so on Similarly, the total pleasure value of the seller can b Table 3 shows the degree of importance of a factor like F. calculated as follows in the customer's and the seller's opinions, CI (F)and TSP=56+35+14=105(Underlined numbers in SI(F ) in example 1. The query interface form in e-shop Table 5 are used) website is used to gather all of these values. A value of 10 Comparing the last two numbers, it can be concluded for CI(F)or SI(F)is considered as maximum importance that the level of seller pleasure is far less than that of the level and zero is the lowest level of importance. Table 3 customer. For achieving a quiescent point, two objectiv shows that for the active customer, the model of should be considered. purchased clothing is very important(CI(F1)=10), where as the material is not too important(CI(F3)=5 The pleasure values of each of the customer and the The values of pleasure of customer(CP)and of seller seller should be kept maximize (SP)due to each selection can be calculated by Eq. 1. The difference between the two pleasure and 2 should be minimized CP(F)=CI (F)XCS (F) So, the objective function SP(F2)=S(F)×SS(F2) O F: Minimize(Max CP-Max SP) Example 3: The pleasure matrices for customer and seller Consider the maximum allowed difference between of example 2 are briefly shown in Table 4 and 5, customer and seller pleasure values is defined by M as respectively only some necessary entries are shown
J. Applied Sci.,9(2):320-326,2009 Table 6: Improving suggestion set according to importance values Ingestion set Changing factor Changed state I ACs ASs ATCP ATSP New TCP New TSP Diff(o) Modification 4 Needed . Not allowed Fus, F, Fr) <( Max CP-Max SP)[O5(CP+SP)<M (4) chromosomes are considered with a 9 bit structure including three genes, according to the three effective Example 4: Let M=20%. Then by using the calculated factors named model, price and material. Each gene values of CP and SP in example 3 the following can be contains 3 bits of o or 1, resulting 8 states. But since each inferred factor in this example has only three states, so, the value of each gene is divided by 3 and the remainder is (190-105[0.5(190+105=0.576*1009=57.69 considered as the final value of gene. The fitness function is calculated as follow While the above-mentioned criterion is not verifie the process of updating CP and SP values must be Fitness=(Absolute value of ((TCP-TSP) repeate (0.5×(TCP+TSP))×100 Hence, Eq 3 and 4 should be used for maximizing CP The population of chromosome pool is considered 4 The above procedure is shown in Table 6, wh and the first population is produced randomly. For the next generation, first a random number is produced, if it is ACS and ASS, respectively are the changes in less than 0.8 cross over is done in a random place Again customer and seller satisfaction values due to change om number is produced and if it is less than 0. 2 the in state of factors mutation is done, The fitness value is calculated and is ATCP and atsp are the changes in total values of compared with the marginal difference of pleasure of seller customer and seller pleasures, respectively, such and customer. The generations are repre oduced until the that:△TCP=△Cs*C,△TSP=△Ss*sI value of fitness is reached inside the desired margin. New TCP=(Previous value of TCP) ATCP Figure 2 shows the user interface of the program. The New TSP=(Previous value of TSP)+ATSP customer enters the favorite model, price and material Also both the seller and customer enter their preferences in the fourth row of Table 6. the fina and importance levels due to each of the effective factors As is At the first, the program announces that the value of suggestion is F13, F2, F323 that corresponds to new atisfaction of seller and customer is or is not inside the model, high price and synthetic leather. The material selected margin (10% in this example). Then the genetic factor is changed in first row because it has the least algorithm produces new recommendations until it reaches value of importance for customer(CI(F)=5). In third row, the final quiescent point decrease in both customer and seller satisfaction values RESULTS Therefore no modification is performed for the decrease in the gap between them. The next level of importance is that In the first run, the customer suggests to bi of F2. So, the next step of modification is performed on F2. overcoat of new mode, medium price and natural leath In database of the recommender system the items are as shown in Fig. 2. This suggestion causes a 57%o categorized into price classes, material groups and model difference between pleasure value of seller and customer categories. In the above example, the recommender So, this can not be considered as the quiescent point. The ystem finally suggests purchasing an item having high GA starts to make new suggestions and finally reaches a price but new model with synthetic leather material. Such difference value of 8%, which is inside the desired level item would satisfy both seller and customer within an overcoat with medium price and natural leather is recommended to both seller and custome GENETIC ALGORITHM IMPLEMENTATION In the second run, the importance levels of custom me he genetic algorithm is considered as a useful made by the customer. The GA algorithm outputs more od for finding the best fitted solutions in the than one suggestion. As shown in Fig 4, the difference proposed algorithm. For the above example, the value of pleasure levels of the third, fourth and fifth
J. Applied Sci.,9(2):320-326,2009 avorite Suggestion Preferences of customer Preferences of seller ChartRepoit) new mode /hat is your favorite price range: medium what is your favorite material: atural leather choose the margin of difference between pleasure of seller and customer: 10% y uf suggestion Is natural leather customer and 105 for seller The percentage difference of pleasures is try the give you Fig. 2: User Interface of Win-Win-QA, initialization step Customer Customer Seller Linear(Customer Fig. 3: Comparison of pleasure levels in the first run 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 approaches a quiescent point that has better difference value, but not necessarily a higher value of pleasure of H Seller Linear ( Customer) the both sides(Fig 3). Chang ing 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: Comparison of pleasure levels in the second run(Fig. 4) Whenever the algorithm approaches to the desired suggestions are placed inside the desired level. So, it is solution very soon, it can give more and more new ble for both the customer and seller to choose suggestions, all placing inside the desired margin of of them difference value of pleasure, but it losses the value of In the third run, the initial suggestion of the customer pleasure (Fig. 5). So, it is needed to combine the is changed. As shown in Fig. 5, two final suggestions marginal difference value criteria with a minimum given to the customer and seller that have difference less permitted value of customer pleasure. But notice that this than 10%. The initial suggestion of the customer was se has the best approach to the trend of custom The final suggestion by GA algorithm was a past mode Genetic algorithm is useful in finding the best fitted overcoat with expensive price and natural leather suggestions, It is possible to change the marginal values
J. Applied Sci.,9(2):320-326,2009 of fitness function and get other results. In this approach Cohen, W.W., R.E. Shapire and Y. Singer, 1999. Learning 0.8 and 0.2 were selected for crossover and mutation to order things, J. Artificial Intell. Res, 10. 243-270 based on our experience Diez, J, J.J. D Coz, O, Luaces and A. Bahamonde, 2008 he algorithm reaches a point that both the customer Clustering people according to their pre eference and the seller feel they are winners. This leads to more criteria. Expert Syst. Appl., 34: 1274-1284 probability of completing a purchase since both sides are Gehrt, K.C. and s Shim, 1998. A Shopping Orientation satisfied. Although when the pleasure level of customer segmentation of French consumers: Implications for decreases, but reaching the quiescent point causes more catalog marketing. J Interact. Market, 12: 34-46 trust and agreement between seller and customer. In many Goldberg, D, D. Nichols, B M Oki and D. Terry,1992 contracts this agreement is too important for starting the Using collaborative filtering to weave an information procedure of a successful business. In future studies, the estry. Commun. ACM, 35: 61-70 procedure of making new suggestions could be improved Hwang, C.S. and P.J. Tsai, 2005. A collaborative and also a margin value of minimum pleasure for customer could be considered as criteria for decision-making. This clusters. Lecture Note Comput. Sci, 3806: 463-469 means that during calculations the value of customer Iijima, J. and S. Ho, 2007. Common Structure and pleasure should not be less than a minimum value. More properties of filtering systems, E-Commerce Res factors could be considered as effective factors Changing Appl,6:139-145 the marginal value of desired difference of pleasure levels Kim, J. and E. Lee, 2005 emantic web recommender is another pararmeter that produces different suggestions systems based personalization service for uery pattern. Lecture Notes 828:848857 REFERENCES Kim, K.J. and H. Ahn, 2008. A recommender system using Adomavicius, G. and A. Tuzhilin, 2005. Toward the next GA K-means clustering in an online shopping market Expert Syst. Appl., 34: 1200-1209 generation of recommender systems: A survey of the Lawrence, R.D., G.S. Almasi, V Kotlyar,MSViveros and state-of-the-art and possible extensions. IEEE Trans Duri, 2001. Personalization of supermarket product Knowledge Data Eng, 17: 734-749 Balbanovich M. and Y. Shoham, 1997. Content Based recommendations. Data Mining Knowledge Discov 5:11-32 Collaborative recommendation. Commun. ACM, Lee. W.P. C.H. Liu and C C Lu, 2002. Intelligent agent 40:66-72 based systems for personalized recommendations Chen, L.S., F H. Hsu M.C. Chen and Y C. Hsu, 2008 internet commerce. Expert Syst. Appl, 22: 275-284 Developing recommender systems with the Montaner, M, B. Lopez and J.L.D. LRosa,2003.A consideration of product profitability for sellers conomy of recommender agents on the Internet Inform.Sci,178:1032-1048 rtificial Intell. Rev. 19: 285-330 Chen, Y L and L.C. Cheng, 2008. A Novel Collaborative Resnick, P and H.R. Varian, 1997. Recommender systems filtering approach for recommending ranked items Commun. ACM. 40: 56-58 Expert Syst. Appl, 34: 2396-2405 war, B, G. Karypis, J. Konstan and J. Riedl, 2000 Cho, Y.H., J.K. Kim and S.H. Kim, 2002. A personalized Analysis of recommendation algorithms for recommender system based on web usage mining e-commerce. proceeding of the 2nd ACM Conference and decision tree induction. Expert Syst. Appl Electronic Commerce, October 17-20, Minneapolis 23:329-342 MN,USA. ACM, Pp: 158-167