An Adaptive lifestyle recommender system Using a Genetic Algorithm Supiya Ijin Department of Computer Science University Colleg Gower Street London WCIE 6BT jin @cs. ucl. ac Abstract recommender system as a generic descriptor that Recommender systems are new types of internet represents various recommendation/prediction techniques based software tools, designed to help users find including collaborative, social, and content based their way through today' s complex on-line shops filtering, Bayesian networks and association rules [5, 6]. In and entertainment websites. This paper provides this paper, we adopt the latter definition when referring to an overview of current recommender systems recommender systems and then outlines a new lifestyle recommender System, which will employ techniques such as 2 CURRENT RECOMMENDE evolutionary search and a 3D avatar to provide tailored and friendly suggestions for users SYSTEMS There are a number of websites that incorporate 1 INTRODUCTION recommender system technologies. Here we will describe The rapid expansion of the Internet has brought about a three systems that exemplify the main approaches in this area new market for trading. Electronic commerce or e- commercehasenabledbusinessestoopenuptheirMovielens(httP://www.movielens.umn.edu),awell products and services to a massive client base that was known research movie recommendation website, makes once available only to the largest multinational use of collaborative filtering technology to make its becomes increasingly fierce, consumers are faced with a build ,ons. This technology captures user preferences to companies. As the competition between businesses Suggest ofile by asking the user to rate movies. It myriad of choices. Although this might seem to be searches for similar profiles (ie users that share the same nothing but beneficial to the consumer, the sheer wealth or similar taste) and uses them to generate new of information relating to the various choices can be suggestions. One shortcoming that most websites using overwhelming. One would normally rely on the opinions collaborative filtering suffer from is that they do not have and advice of friends or family members but any facility to provide explanations of how unfortunately even they have limited knowledge recommendations are derived. This is addressed in [71 which proposes explanation facilities for recommender Recommender systems provide one way of circumventing systems in order to increase users' faith in the suggestions this problem. As the name suggests, their task is to The dataset collected through the movie lens website has recommend or suggest items or products to the customer been made available for research purposes and shall be based on his/her preferences. These systems are often E-commerce websites as marketing tools to ed to test the lifestyle recommender system.) Increase revenue bypresentingproductsthatthecustomerBycontrastLibRa(httP://www.cs.utexas.edu/users/ is likely to buy. An internet site using a recommender libra) combines a conte approac achine exploit knowledge of customers' likes and learning to make book recommendations. The content dislikes to build an understanding of their individual based approach differs from collaborative filtering in that needs and thereby increase customer loyalty [1, 2] From the literature, it seems that the definition of the term sense of "community"which forms the basis of recommender system"varies depending on the author. collaborative filtering. It also uses Bayesian text Some researchers use the concepts: " recommender categorisation machine learning techniques to build a system","collaborative filtering"and"social filtering. model of each user's preferences relative to the content of interchangeably 3 Conversely, others regard the items. Although the model is very small and fast and
An Adaptive Lifestyle Recommender System Using a Genetic Algorithm Supiya Ujjin Department of Computer Science University College London Gower Street, London WC1E 6BT s.ujjin@cs.ucl.ac.uk Abstract Recommender systems are new types of internetbased software tools, designed to help users find their way through today’s complex on-line shops and entertainment websites. This paper provides an overview of current recommender systems, and then outlines a new Lifestyle Recommender System, which will employ techniques such as evolutionary search and a 3D avatar to provide tailored and friendly suggestions for users. 1 INTRODUCTION The rapid expansion of the Internet has brought about a new market for trading. Electronic commerce or ecommerce has enabled businesses to open up their products and services to a massive client base that was once available only to the largest multinational companies. As the competition between businesses becomes increasingly fierce, consumers are faced with a myriad of choices. Although this might seem to be nothing but beneficial to the consumer, the sheer wealth of information relating to the various choices can be overwhelming. One would normally rely on the opinions and advice of friends or family members but unfortunately even they have limited knowledge. Recommender systems provide one way of circumventing this problem. As the name suggests, their task is to recommend or suggest items or products to the customer based on his/her preferences. These systems are often used by E-commerce websites as marketing tools to increase revenue by presenting products that the customer is likely to buy. An internet site using a recommender system can exploit knowledge of customers' likes and dislikes to build an understanding of their individual needs and thereby increase customer loyalty [1, 2]. From the literature, it seems that the definition of the term “recommender system” varies depending on the author. Some researchers use the concepts: “recommender system”, “collaborative filtering” and “social filtering” interchangeably [3,4]. Conversely, others regard “recommender system” as a generic descriptor that represents various recommendation/prediction techniques including collaborative, social, and content based filtering, Bayesian networks and association rules [5,6]. In this paper, we adopt the latter definition when referring to recommender systems. 2 CURRENT RECOMMENDER SYSTEMS There are a number of websites that incorporate recommender system technologies. Here we will describe three systems that exemplify the main approaches in this area. MovieLens (http://www.movielens.umn.edu), a wellknown research movie recommendation website, makes use of collaborative filtering technology to make its suggestions. This technology captures user preferences to build a profile by asking the user to rate movies. It searches for similar profiles (i.e. users that share the same or similar taste) and uses them to generate new suggestions. One shortcoming that most websites using collaborative filtering suffer from is that they do not have any facility to provide explanations of how recommendations are derived. This is addressed in [7] which proposes explanation facilities for recommender systems in order to increase users' faith in the suggestions. (The dataset collected through the MovieLens website has been made available for research purposes and shall be used to test the lifestyle recommender system.) By contrast, LIBRA (http://www.cs.utexas.edu/users/ libra) combines a content-based approach with machine learning to make book recommendations. The contentbased approach differs from collaborative filtering in that it analyses the contents of the items being recommended. Furthermore, each user is treated individually - there is no sense of “community” which forms the basis of collaborative filtering. It also uses Bayesian textcategorisation machine learning techniques to build a model of each user's preferences relative to the content of the items. Although the model is very small and fast and
as accurate as collaborative fltering technique 3], it is Every time a vote is submitted by a user, it is recorded in often built off-line which can take anything from hours up the database with a timestamp. The movie information in to days. This method is therefore not suitable in a the dataset includes genres, and theatre and video release dynamic environment where user preference model needs dates to be updated frequently. The key advantage of this Figure 1 shows how the evolutionary profile matcher is approach is that explanations can be very easily produced sed within the system However a content-based approach is inappropriate when the items being considered are in a non-textual form such as images, and video or music clips Dooyoo(http://www.dooyoo.co.uk)operatesinaslightly Interfac different way. It too is a useful resource that provides recommendations to those seeking advice. but it focuses mainly on gathering qualitative opinions from its users, Matched Profies H and then making them available to others. Visitors will often submit reviews on items or services ranging from ealth spas to mobile phones. These items are categorised Profile Matcher in a similar fashion to the layout on a structured search engine, such as Yahoo! While Dooyoo is not a recommender system in the normal sense, it tries Profile Lifesty encourage the concept of community by allowing users to rate things, evaluate the"usefulness" of other people's reviews,and establish "circles of friends-people who share similar opinions on various issues. In focussing on Figure 1: Block diagram of the Lifestyle Recommender opinions in the form of short reviews, Dooyoo can already System provide explanations" that are not present in most other recommender systems 3.2 EVOLUTIONARY PROFILE MATCHER 3 BUILDING A LIFESTYLE The success of a collaborative filtering system is highly dependent upon the effectiveness of the algorithm in RECOMMENDER SYSTEM finding the set of profiles(nearest neighbours)which are most similar to that of the current user it is vital that for a 3.1 SYSTEM OVERⅤIEW particular selection method, only the best or closest This work focuses on the development of a Lifestyle recommendations for the user. There is little tolerance for Recommender System. It will gather preferences from inaccurate or irrelevant predictions users on a broad range of topics allowing recommendations to be made for general lifestyle A standard nearest neighbour algorithm consists of three activities such as shopping for clothes, eating out and main tasks: profile selection, profile matching and best going to the cinema profile collection. In an ideal world, the entire database of rofiles would be used to select the best possible profiles The system is based around a collaborative filtering However this is not al ways a feasible option, especially approach, building up profiles of users and then using an when the dataset is very large or if resources are not algorithm to find profiles similar to the current user. available. As a result, most systems opt for random Selected data from those profiles are then used to build sampling and this process is the responsibility of the recommendations. Because profiles contain many profile selection part of the algorithm. The profile attributes, many of which have sparse or incomplete data matching process then computes the distance or similarity [7I, the task of finding appropriate similarities is often between the selected profiles and the current profile using difficult. To overcome these problems, current systems a distance function. Finally, the profiles that are most ( such as MovieLens) use stochastic and heuristic-based similar are gathered by the best profile collection process models to speed up and improve the quality of profile matching. This research takes such ideas one step further. This research focuses on the profile matching task.From by applying a random-based search algorithm known the analysis of Breese et al [3], it seems that most current an evolutionary algorithm to the problem of profile systems use standard algorithms that consider only voting information as the feature on which the comparison between two profiles is made. However in In this research, the Movielens dataset will be used for real life, the way in which two people are said to be initial experiments. It contains many parameters or similar is not based solely on whether they have features which can also be used when we extend the complimentary opinions on a specific subject e.g. movie system for other lifestyle activities. Demographic ratings, but also on other factors such as their background information such as age, gender, occupation and postal and personal details. If we apply this to the profile code is collected when a new user registers on the system. matcher, issues such as demographic and lifestyle
as accurate as collaborative filtering technique [3], it is often built off-line which can take anything from hours up to days. This method is therefore not suitable in a dynamic environment where user preference model needs to be updated frequently. The key advantage of this approach is that explanations can be very easily produced. However a content-based approach is inappropriate when the items being considered are in a non-textual form such as images, and video or music clips. Dooyoo (http://www.dooyoo.co.uk) operates in a slightly different way. It too is a useful resource that provides recommendations to those seeking advice, but it focuses mainly on gathering qualitative opinions from its users, and then making them available to others. Visitors will often submit reviews on items or services ranging from health spas to mobile phones. These items are categorised in a similar fashion to the layout on a structured search engine, such as Yahoo! While Dooyoo is not a recommender system in the normal sense, it tries to encourage the concept of community by allowing users to rate things, evaluate the “usefulness” of other people's reviews, and establish “circles of friends” - people who share similar opinions on various issues. In focussing on opinions in the form of short reviews, Dooyoo can already provide “explanations” that are not present in most other recommender systems. 3 BUILDING A LIFESTYLE RECOMMENDER SYSTEM 3.1 SYSTEM OVERVIEW This work focuses on the development of a Lifestyle Recommender System. It will gather preferences from users on a broad range of topics allowing recommendations to be made for general lifestyle activities such as shopping for clothes, eating out and going to the cinema. The system is based around a collaborative filtering approach, building up profiles of users and then using an algorithm to find profiles similar to the current user. Selected data from those profiles are then used to build recommendations. Because profiles contain many attributes, many of which have sparse or incomplete data [7], the task of finding appropriate similarities is often difficult. To overcome these problems, current systems (such as MovieLens) use stochastic and heuristic-based models to speed up and improve the quality of profile matching. This research takes such ideas one step further, by applying a random-based search algorithm known as an evolutionary algorithm to the problem of profile matching. In this research, the MovieLens dataset will be used for initial experiments. It contains many parameters or features which can also be used when we extend the system for other lifestyle activities. Demographic information such as age, gender, occupation and postal code is collected when a new user registers on the system. Every time a vote is submitted by a user, it is recorded in the database with a timestamp. The movie information in the dataset includes genres, and theatre and video release dates. Figure 1 shows how the evolutionary profile matcher is used within the system. Figure 1 : Block diagram of the Lifestyle Recommender System. 3.2 EVOLUTIONARY PROFILE MATCHER The success of a collaborative filtering system is highly dependent upon the effectiveness of the algorithm in finding the set of profiles (nearest neighbours) which are most similar to that of the current user. It is vital that for a particular selection method, only the best or closest profiles are chosen and used to generate new recommendations for the user. There is little tolerance for inaccurate or irrelevant predictions. A standard nearest neighbour algorithm consists of three main tasks: profile selection, profile matching and best profile collection. In an ideal world, the entire database of profiles would be used to select the best possible profiles. However this is not always a feasible option, especially when the dataset is very large or if resources are not available. As a result, most systems opt for random sampling and this process is the responsibility of the profile selection part of the algorithm. The profile matching process then computes the distance or similarity between the selected profiles and the current profile using a distance function. Finally, the profiles that are most similar are gathered by the best profile collection process. This research focuses on the profile matching task. From the analysis of Breese et. al [3], it seems that most current systems use standard algorithms that consider only “voting information” as the feature on which the comparison between two profiles is made. However in real life, the way in which two people are said to be similar is not based solely on whether they have complimentary opinions on a specific subject e.g. movie ratings, but also on other factors such as their background and personal details. If we apply this to the profile matcher, issues such as demographic and lifestyle
information which include users age, gender and movie distance function, such as correlation 3]. The closer a different importance or priority on each feature. These nres must also be taken into account. Every user places the results are to the standard results. the fitter the solution. The problem with this method is that the priorities can be quantified or enumerated. Here we refer algorithm will try to evolve towards this standard to these as feature weights. For example, if a male user algorithm and put the highest weight on movie prefers to be given recommendations based on the men. ther would be higher than other features. In order to 2. The fitness function could take the form of implement a truly personalised recommender system, supervised learning. For each set of feature weights these weights need to be captured and fine-tuned to reflect a group of"best profiles are gathered. From these, each users preferenc recommendations of movies and their predicted a potential solution to the problem of evolving feature ratings are recorded. These can be compared against weights is represented as a set of weights as shown below the actual values if the current user had already voted in Figure 2 for the same titles The differences between the actual and predicted votes are used as fitness score to guide future generations of weight evolution. This would only be suitable if the user has actively voted otherwise the intersection between recommended Figure 2: Phenotype of an individual in the population items and those already voted for by the current user would return very few titles or even none. In the latter case, this approach will fail, as a fitness score here Wi is the weight associated with feature i whose cannot be determined genotype is a string of binary values. Each individual contains n features or genes 3. To address this problem, the user himself can be treated as a fitness function this involves obtaining A standard genetic algorithm will be used to generate the feedback from the user by asking him to judge the initial set of feature weights which every new user will quality of recommendations [8]. His input is used to inherit. Following this process, the evolved values will be help derive fitness scores for the current set of feature stored on the user's local machine, together with a copy weights. This fitness score will give a highly accurate of the genetic algorithm program which will then be view of user's preferences. However, it is unlikely responsible for fine-tuning them to suit each individual that every user will be willing to participate in ever This way the processing load on the server would b recommendation. Therefore, a hybrid of both user reduced and parallelism can be achieved and supervised learning fitness functions may be The comparison between two profiles can now be conducted using a modified distance function which takes into account multiple features. One example of this could 3.3 CONSUMER INTERACTION be a simple Pythagorean distance measure(with a suitable As we have seen, recommender systems can bring added normalisation method, not described here). When the value to e-commerce websites by being able to understand weight for certain feature is zero, that feature is ignored. the users' preferences and needs. One possible way to take This way the feature selection is adaptive to each user's this further is to introduce a"character"to enhance the preferences. way in which both items can be recommended to, and feedback received from the customer This character or avatar would be a visual representative of the website with which customers can interact. The rationale behind v(x-y2)2 this is that a user would find it easier to relate to another person or character than a standard web interface. There is then the possibility of a relationship being established between user and avatar. From the point of view of the here Dx, is the similarity between user x and user y. The website owner, such a relationship would encourage value, w, is the weight of the current user for feature i increased usage of the website and allow more preference whilst x, and yi are the associated values recorded in the to be captured which would consequently lead to There are three possible fitness functions that can be used Thea. ccurate recommendations profiles of the two users respectively recommender system will employ the use of to judge the fitness of the feature weights of the current to interact with the user. figure 2 shows an user of the avatar to be used for the lifestyle recommender system 1. The results obtained from the modified distance function can be compared with those of a standard
information which include user’s age, gender and movie genres must also be taken into account. Every user places a different importance or priority on each feature. These priorities can be quantified or enumerated. Here we refer to these as feature weights. For example, if a male user prefers to be given recommendations based on the opinions of other men, then his feature weight for gender would be higher than other features. In order to implement a truly personalised recommender system, these weights need to be captured and fine-tuned to reflect each user’s preference. A potential solution to the problem of evolving feature weights is represented as a set of weights as shown below in Figure 2. W1 W2 W3 … Wn Figure 2: Phenotype of an individual in the population. where Wi is the weight associated with feature i whose genotype is a string of binary values. Each individual contains n features or genes. A standard genetic algorithm will be used to generate the initial set of feature weights which every new user will inherit. Following this process, the evolved values will be stored on the user’s local machine, together with a copy of the genetic algorithm program which will then be responsible for fine-tuning them to suit each individual. This way the processing load on the server would be reduced and parallelism can be achieved. The comparison between two profiles can now be conducted using a modified distance function which takes into account multiple features. One example of this could be a simple Pythagorean distance measure (with a suitable normalisation method, not described here). When the weight for certain feature is zero, that feature is ignored. This way the feature selection is adaptive to each user’s preferences. ∑= = − n i x y i i i D w x y 1 2 , ( ) where Dx,y is the similarity between user x and user y. The value, wi, is the weight of the current user for feature i, whilst xi and yi are the associated values recorded in the profiles of the two users respectively. There are three possible fitness functions that can be used to judge the fitness of the feature weights of the current user: 1. The results obtained from the modified distance function can be compared with those of a standard distance function, such as correlation [3]. The closer the results are to the standard results, the fitter the solution. The problem with this method is that the algorithm will try to evolve towards this standard algorithm and put the highest weight on movie ratings. 2. The fitness function could take the form of supervised learning. For each set of feature weights, a group of ‘best’ profiles are gathered. From these, recommendations of movies and their predicted ratings are recorded. These can be compared against the actual values if the current user had already voted for the same titles. The differences between the actual and predicted votes are used as fitness score to guide future generations of weight evolution. This would only be suitable if the user has actively voted, otherwise the intersection between recommended items and those already voted for by the current user would return very few titles or even none. In the latter case, this approach will fail, as a fitness score cannot be determined. 3. To address this problem, the user himself can be treated as a fitness function. This involves obtaining feedback from the user by asking him to judge the quality of recommendations [8]. His input is used to help derive fitness scores for the current set of feature weights. This fitness score will give a highly accurate view of user’s preferences. However, it is unlikely that every user will be willing to participate in every recommendation. Therefore, a hybrid of both user and supervised learning fitness functions may be required. 3.3 CONSUMER INTERACTION As we have seen, recommender systems can bring added value to e-commerce websites by being able to understand the users' preferences and needs. One possible way to take this further is to introduce a “character” to enhance the way in which both items can be recommended to, and feedback received from the customer. This character or avatar would be a visual representative of the website with which customers can interact. The rationale behind this is that a user would find it easier to relate to another person or character than a standard web interface. There is then the possibility of a relationship being established between user and avatar. From the point of view of the website owner, such a relationship would encourage increased usage of the website and allow more preference data to be captured which would consequently lead to more accurate recommendations. The lifestyle recommender system will employ the use of a 3D avatar to interact with the user. Figure 2 shows an early version of the avatar to be used for the lifestyle recommender system
0y①为 [4] Goldberg. K, Roeder, T, Gupta, D and Pe August 2000. Eigentaste: A Constant Time Collaborative Filtering Algorithm. UCB ERL I know you lI love this filn Cock it out. Technical Report M00/41 f you' ve already soon it, tell me what you think. [5] Terveen, L. and W.2001 Recommender Systems: Helping People Hel Other. In HCI In The New Millenium, Carroll THE KOWARENAI ★★★★y Addison-Wesley. smess:this fileisalvetrisxeteten [6] Delgado, J.A. February 2000. Agent-Based Information Filtering and Recommender Systems on the Internet. PhD thesis, Nagoya Institute of [7 Herlocker, J L, Konstan, J. A. and Riedl, J. 2000 YOUR OPINION Explaining Collaborative Recommendations. Proceedings of the ACm 2000 Lifestyle O Love it O Not sure. O Hate it Conference on Computer Supported Cooperative e [8] Bentley, P J. 2001. Creative Evolutionary Systems Morgan Kaufman pub Figure 3: Lifestyle Recommender System Avata interface 4. SUMMARY as electronic commerce and on-line entertainment internet sites multiply, and as the number of novice users of the internet increases, there is a greater need for tailored and friendly software advisors. As described in this paper, recommender systems provide such a solution for users. By employing the evolutionary profile matching technique, users' preferences can be captured more accurately and this should improve quality recommendation Acknowledgments Thanks to Philip Treleaven for his guidance, Peter Bentley for introducing me to the field of Evolutionary Computation and Akira Sato for implementing the Avatar web interface. This work is funded by a scholarship provided by the Thai government References [1] Schafer, J B, Konstan, J. A. and Riedl, J. January 2001. E-Commerce Recommendation Applications Journal of Data Mining and Knowledge Discovery [2] Schafer, J B, Konstan, J. and Riedl, J. 1999 Recommender Systems in E-Commerce. Proceedings of the ACm 1999 Conference on Electronic [3] Breese, J.S., Heckerman, D. and Kadie, C. 1998 Empirical analysis of predictive algorithms for collaborative filtering. In Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence pp.43-52
Figure 3: Lifestyle Recommender System Avatar interface. 4. SUMMARY As electronic commerce and on-line entertainment internet sites multiply, and as the number of novice users of the internet increases, there is a greater need for tailored and friendly software advisors. As described in this paper, recommender systems provide such a solution for users. By employing the evolutionary profile matching technique, users' preferences can be captured more accurately and this should improve quality of recommendation. Acknowledgments Thanks to Philip Treleaven for his guidance, Peter Bentley for introducing me to the field of Evolutionary Computation and Akira Sato for implementing the Avatar web interface. This work is funded by a scholarship provided by the Thai Government. References [1] Schafer, J.B., Konstan, J. A. and Riedl, J. January 2001. E-Commerce Recommendation Applications. Journal of Data Mining and Knowledge Discovery. [2] Schafer, J.B., Konstan, J. and Riedl, J. 1999. Recommender Systems in E-Commerce. Proceedings of the ACM 1999 Conference on Electronic Commerce. [3] Breese, J.S., Heckerman, D. and Kadie, C. 1998. Empirical analysis of predictive algorithms for collaborative filtering. In Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence, pp. 43-52. [4] Goldberg, K., Roeder, T., Gupta, D. and Perkins, C. August 2000. Eigentaste: A Constant Time Collaborative Filtering Algorithm. UCB ERL Technical Report M00/41 [5] Terveen, L. and Hill, W. 2001. Beyond Recommender Systems: Helping People Help Each Other. In HCI In The New Millenium, Carroll, J. ed. Addison-Wesley. [6] Delgado, J.A. February 2000. Agent-Based Information Filtering and Recommender Systems on the Internet. PhD thesis, Nagoya Institute of Technology. [7] Herlocker, J.L., Konstan, J. A. and Riedl, J. 2000. Explaining Collaborative Filtering Recommendations. Proceedings of the ACM 2000 Conference on Computer Supported Cooperative Work. [8] Bentley, P. J. 2001. Creative Evolutionary Systems. Morgan Kaufman Pub
