DistributedandParallelDatabases,14,173-192,2003 C 2003 Kluwer Academic Publishers. Manufactured in The Netherlands An Adaptive Recommendation System without Explicit Acquisition of User Relevance Feedback CYRUS SHAHABI wahabi@usc.edu YI-SHIN CHE yishinc@ usc.edu Integrated Media Systems Center and Computer Science Department, University of Southern California. Los Angeles, CA 90089-2564, USA Recommended by: Boualem Benatallah opted in e-commerce businesses for helping customers locate products they would like to purchase. In an earlier work, we introduced a recommendation system, termed Yoda, hich employs a hybrid approach that combines collaborative filtering( CF)and content-based querying to achieve higher accuracy for large-scale Web-based applications. To reduce the complexity of the hybrid approach, Yoda is structured as a tunable model that is trained off-line and employed for real-time recommendation on-line. The h-line process benefits from an optimized aggregation function with low complexity that allows the real-time gregation based on confidence values of an active user to pre-defined sets of recommendations In this paper extend Yoda to include more recommendation sets. The recommendation sets can be obtained from differen sources, such as human experts, web navigation pattens, and clusters of user evaluations. Moreover, the extended Yoda can learn the confidence values automatically by utilizing implicit users'relevance feedback through web navigations using genetic algorithms( GA). Our end-to-end experiments show while Yoda's complexity is low and remains constant as the number of users and/or items grow, its accuracy surpasses that of the basic nearest-neighbor ethod by a wide margin(in most cases more than 100%0). The experimental results also indicate that the retrieval uracy is significantly increased by using the GA-based learning mechanism. Keywords: e-commerce, recommendation systems, genetic algorithm, relevance feedbacl 1. ntroduction As the amount of available products in e-commerce businesses is burgeoning, searching for desired products among enormous offerings is becoming increasingly difficult. As a result, e-commerce users frequently suffer from information overload. To alleviate this problem, recommendation systems are being widely adopted to help customers locate products they would like to purchase. In essence, these systems apply data analysis techniques to provide a list of recommended products for each online customer. The most famous example in e-commercebusinessesisthe"customerswhobought"featureusedinAmazon.com which is basically applied to every product page on its websites. With the help of th featuresAmazon.comssystemrecommendssimilarproductstothecurrentbuyerbased on the purchase histories of previous customers who bought the same product oh- l ozog arpa and usaa u bde at geats be 30602 39 4052 4 Rnd an es ited cas, ifts from Microsoft, NCR, and Okawa Foundations
Distributed and Parallel Databases, 14, 173–192, 2003 c 2003 Kluwer Academic Publishers. Manufactured in The Netherlands. An Adaptive Recommendation System without Explicit Acquisition of User Relevance Feedback∗ CYRUS SHAHABI shahabi@usc.edu YI-SHIN CHEN yishinc@usc.edu Integrated Media Systems Center and Computer Science Department, University of Southern California, Los Angeles, CA 90089-2564, USA Recommended by: Boualem Benatallah Abstract. Recommendation systems are widely adopted in e-commerce businesses for helping customers locate products they would like to purchase. In an earlier work, we introduced a recommendation system, termed Yoda, which employs a hybrid approach that combines collaborative filtering (CF) and content-based querying to achieve higher accuracy for large-scale Web-based applications. To reduce the complexity of the hybrid approach, Yoda is structured as a tunable model that is trained off-line and employed for real-time recommendation on-line. The on-line process benefits from an optimized aggregation function with low complexity that allows the real-time aggregation based on confidence values of an active user to pre-defined sets of recommendations. In this paper, we extend Yoda to include more recommendation sets. The recommendation sets can be obtained from different sources, such as human experts, web navigation patterns, and clusters of user evaluations. Moreover, the extended Yoda can learn the confidence values automatically by utilizing implicit users’ relevance feedback through web navigations using genetic algorithms (GA). Our end-to-end experiments show while Yoda’s complexity is low and remains constant as the number of users and/or items grow, its accuracy surpasses that of the basic nearest-neighbor method by a wide margin (in most cases more than 100%). The experimental results also indicate that the retrieval accuracy is significantly increased by using the GA-based learning mechanism. Keywords: e-commerce, recommendation systems, genetic algorithm, relevance feedback 1. Introduction As the amount of available products in e-commerce businesses is burgeoning, searching for desired products among enormous offerings is becoming increasingly difficult. As a result, e-commerce users frequently suffer from information overload. To alleviate this problem, recommendation systems are being widely adopted to help customers locate products they would like to purchase. In essence, these systems apply data analysis techniques to provide a list of recommended products for each online customer. The most famous example in e-commerce businesses is the “Customers who bought” feature used in Amazon.comTM, which is basically applied to every product page on its websites. With the help of this feature, Amazon.comTM’s system recommends similar products to the current buyer based on the purchase histories of previous customers who bought the same product. ∗This research has been funded in part by NSF grants EEC-9529152 (IMSC ERC) and IIS-0082826, NIH-NLM R01-LM07061, DARPA and USAF under agreement nr. F30602-99-1-0524, and unrestricted cash gifts from Microsoft, NCR, and Okawa Foundations
SHAHABI AND CHEN In an earlier work [24], we introduced a hybrid recommendation system--Yoda, which simultaneously utilizes the advantages of clustering, content analysis, and collaborate fil- tering(CF)approaches. Basically, Yoda is a two-step approach recommendation system. During the offline process, Yoda maintains numerous recommendation lists obtained from typical navigation patterns analyzed by clustering and content analysis techniques. During the online process, the confidence value of an active user to each navigation-pattern cluster is estimated using the PPED distance measure [25] by comparing the user's navigation attern with centroid of each cluster. Finally, Yoda generates customized recommendations for the user by aggregating across recommendation lists(one list for each cluster) using the confidence values as the weights To expedite the aggregation step, we proposed an optimized fuzzy aggregation function that reduces the time complexity of aggregation from O(N X E)to O(N), where N is the number of recommended items and e is the number of clusters. Besides the advantage of efficiency, our aggregation function(similar to FALCON [31] can manage disjunctive queries while the traditional weighted average method cannot. For example, assume that the system knows all the information about users and user U is interested in the items the list of items recommended by both expert A and B while our aggregation metho rate recommended by expert A or B. The traditional weighted average method can only gene retrieve the expected list. In sum, the time complexity is reduced through a model-based technique, a clustering approach, and the optimized aggregation method. Additionally, due to the utilization of con tent analysis techniques, Yoda can detect the latent association between items and therefore provides better recommendations. Moreover, Yoda is able to collect information about user interests from implicit web navigation behaviors while most other recommendation systems 3, 9, 20, 23, 28] do not have this ability and therefore require explicit rating information from users. Consequently, Yoda puts less overhead on the users. Since content analysis techniques only capture certain characteristics of products, some desired products might not be included in the recommendation lists produced by analyzing the content. For example, picking wines based on brands, years, and descriptors might not be adequate if"smell"and"taste"are more important characteristics. In order to remedy for this problem, we extend Yoda to incorporate more recommendation lists than just web navigation patterns. These recommendation lists can be obtained from various experts, such as human experts and clusters of user evaluations. Meanwhile, because PPED is specially designed for measuring the similarity between two web navigation patterns including related data such as browsed items, view time, and sequences information, it can only be used for estimating confidence values to navigation- pattern clusters. Therefore, a leaming mechanism is needed for obtaining the complete confidence values of an active user toward all experts. We propose a learning mechanism that utilizes users'relevance feedback to improve confidence values automatically using To the best of our knowledge, only a few studies[ 18, 29]incorporate Ga for improving the user profiles. In these studies, users are directly involved in the evolution processes. Because users have to enter data for each product inquiry, they are often frustrated with this method On the contrary, in our design, users are not required to offer additional data to improve
174 SHAHABI AND CHEN In an earlier work [24], we introduced a hybrid recommendation system—Yoda, which simultaneously utilizes the advantages of clustering, content analysis, and collaborate filtering (CF) approaches. Basically, Yoda is a two-step approach recommendation system. During the offline process, Yoda maintains numerous recommendation lists obtained from typical navigation patterns analyzed by clustering and content analysis techniques. During the online process, the confidence value of an active user to each navigation-pattern cluster is estimated using the PPED distance measure [25] by comparing the user’s navigation pattern with centroid of each cluster. Finally, Yoda generates customized recommendations for the user by aggregating across recommendation lists (one list for each cluster) using the confidence values as the weights. To expedite the aggregation step, we proposed an optimized fuzzy aggregation function that reduces the time complexity of aggregation from O(N × E) to O(N), where N is the number of recommended items and E is the number of clusters. Besides the advantage of efficiency, our aggregation function (similar to FALCON [31]) can manage disjunctive queries while the traditional weighted average method cannot. For example, assume that the system knows all the information about users and user U is interested in the items recommended by expert A or B. The traditional weighted average method can only generate the list of items recommended by both expert A and B while our aggregation method can retrieve the expected list. In sum, the time complexity is reduced through a model-based technique, a clustering approach, and the optimized aggregation method. Additionally, due to the utilization of content analysis techniques, Yoda can detect the latent association between items and therefore provides better recommendations. Moreover, Yoda is able to collect information about user interests from implicit web navigation behaviors while most other recommendation systems [3, 9, 20, 23, 28] do not have this ability and therefore require explicit rating information from users. Consequently, Yoda puts less overhead on the users. Since content analysis techniques only capture certain characteristics of products, some desired products might not be included in the recommendation lists produced by analyzing the content. For example, picking wines based on brands, years, and descriptors might not be adequate if “smell” and “taste” are more important characteristics. In order to remedy for this problem, we extend Yoda to incorporate more recommendation lists than just web navigation patterns. These recommendation lists can be obtained from various experts, such as human experts and clusters of user evaluations. Meanwhile, because PPED is specially designed for measuring the similarity between two web navigation patterns including related data such as browsed items, view time, and sequences information, it can only be used for estimating confidence values to navigationpattern clusters. Therefore, a learning mechanism is needed for obtaining the complete confidence values of an active user toward all experts. We propose a learning mechanism that utilizes users’ relevance feedback to improve confidence values automatically using genetic algorithms (GA) [7]. To the best of our knowledge, only a few studies [18, 29] incorporate GA for improving the user profiles. In these studies, users are directly involved in the evolution processes. Because users have to enter data for each product inquiry, they are often frustrated with this method. On the contrary, in our design, users are not required to offer additional data to improve
AN ADAPTIVE RECOMMENDATION SYSTEM 175 the confidence values. These confidence values are corrected by the gA-based learning mechanisms using users' future navigation behaviors. Our experimental results indicate a significant increase in the accuracy of recommendation results due to the integration of the proposed learning mechanism. The remainder of this paper is organized as follows. Section 2 summarizes the related work. In Section 3, we provide an overview on the functionality of Yoda In Section 4, we discuss the detailed design of Yoda. Section 5 depicts the learning mechanism of Yoda. Section 6 describes the results of our evaluations as well as the details of the system implementation and our benchmarking method Section 7 concludes the paper 2. Related work Recommendation systems are designed either based on content-based filtering or collab- orative filtering. Both types of systems have inherent strengths and weaknesses, where content-based approaches directly exploit the product information, and the collaboration filtering approaches utilize specific user rating information Content-based filtering approaches are derived from the concepts introduced by the In- formation Retrieval (IR)community. Content-based filtering systems are usually criticized or two weaknesses 1. Content limitation: IR methods can only be applied to a few kinds of content, such as text and image, and the extracted features can only capture certain aspects of the content Over-specialization: Content-based recommendation system provides recommendations merely based on user profiles. Therefore, users have no chance of exploring new items at are not similar to those items included in their profiles The collaborative filtering(CF) approach remedies for these two problems. Typically, CF-based recommendation systems do not use the actual content of the items for recommen- dation. Moreover, since other user profiles are also considered, user can explore new items The nearest-neighbor algorithm is the earliest CF-based technique used in recommendation systems [20, 28]. With this algorithm, the similarity between users is evaluated based on their ratings of products, and the recommendation is generated considering the items visited by nearest neighbors of the user. In its original form, the nearest-neighbor algorithm uses a two-dimensional user-item matrix to represent the user profiles. This original form of CF-based recommendation systems suffers from three problems 1. Scalability: The time complexity of executing the nearest-neighbor algorithm grows linearly with the number of items and the number of users. Thus, the recommendation system cannot support large-scale applications such as Amazon. com, which provides more than 18 million unique items for over 20 million users 2. Sparsity: Due to large number of items and user reluctance to rate the items, usually the profile matrix is sparse. Therefore, the system cannot provide recommendations for some users, and the generated recommendations are not accurate
AN ADAPTIVE RECOMMENDATION SYSTEM 175 the confidence values. These confidence values are corrected by the GA-based learning mechanisms using users’ future navigation behaviors. Our experimental results indicate a significant increase in the accuracy of recommendation results due to the integration of the proposed learning mechanism. The remainder of this paper is organized as follows. Section 2 summarizes the related work. In Section 3, we provide an overview on the functionality of Yoda. In Section 4, we discuss the detailed design of Yoda . Section 5 depicts the learning mechanism of Yoda. Section 6 describes the results of our evaluations as well as the details of the system implementation and our benchmarking method. Section 7 concludes the paper. 2. Related work Recommendation systems are designed either based on content-based filtering or collaborative filtering. Both types of systems have inherent strengths and weaknesses, where content-based approaches directly exploit the product information, and the collaboration filtering approaches utilize specific user rating information. Content-based filtering approaches are derived from the concepts introduced by the Information Retrieval (IR) community. Content-based filtering systems are usually criticized for two weaknesses: 1. Content limitation: IR methods can only be applied to a few kinds of content, such as text and image, and the extracted features can only capture certain aspects of the content. 2. Over-specialization: Content-based recommendation system provides recommendations merely based on user profiles. Therefore, users have no chance of exploring new items that are not similar to those items included in their profiles. The collaborative filtering (CF) approach remedies for these two problems. Typically, CF-based recommendation systems do not use the actual content of the items for recommendation. Moreover, since other user profiles are also considered, user can explore new items. The nearest-neighbor algorithm is the earliest CF-based technique used in recommendation systems [20, 28]. With this algorithm, the similarity between users is evaluated based on their ratings of products, and the recommendation is generated considering the items visited by nearest neighbors of the user. In its original form, the nearest-neighbor algorithm uses a two-dimensional user-item matrix to represent the user profiles. This original form of CF-based recommendation systems suffers from three problems: 1. Scalability: The time complexity of executing the nearest-neighbor algorithm grows linearly with the number of items and the number of users. Thus, the recommendation system cannot support large-scale applications such as Amazon.comTM, which provides more than 18 million unique items for over 20 million users. 2. Sparsity: Due to large number of items and user reluctance to rate the items, usually the profile matrix is sparse. Therefore, the system cannot provide recommendations for some users, and the generated recommendations are not accurate
SHAHABI AND CHEN 3. Synonymy: Since contents of the items are completely ignored, latent association between items is not considered for recommendations. Thus, as long as new items are not rated they are not recommended; hence, false negatives are introduced In order to solve these problems, a variety of different techniques have been proposed Some of techniques, such as dimensionality reduction [22, 23], clustering[16], and Bayesian Network [3, 9], mainly are remedies for the scalability problem. These techniques extract characteristics(patterns)from the original dataset in an offline process andemploy only these patterns to generate the recommendation lists in the online process. Although this approach reduce the online processing cost, it often reduces the accuracy of the recommending results. Moreover, the online computation complexity keeps increasing with the number of patterns. Some other techniques, such as association rules [17, 23], content analysis [1, 2, 151, categorization [6, 12), are emphasized on alleviating the sparsity and synonymy problems Basically, these techniques analyze the Web usage data(from Web server logs )to capture the latent association between items. Subsequently, based on both item association information and user ratings, the recommendation systems can thus generate better recommendation to users. However, the online computation time concurrently increases, as more data incorporated into the recommendation progress. Additionally, because Web usage data from the server side are not reliable [26], the item association generated from Web server logs might be wrong. ith Yoda [24], we introduced a hybrid recommendation model, which consists of two steps During the offline process, Yoda generates cluster recommendation lists based on the Web usage data from the client-side through clustering and content analysis techniques This approach not only can address the scalability problem by the preprocessing work, but also can alleviate the sparsity and synonymy problems by discovering latent assoc tion between items. Since the Web usage data from the client-side can capture real user navigation behaviors, the item association discovered by the Yoda system would be more accurate. Beside the cluster recommendation lists. Yoda also maintains numerous recom- mendation lists obtained from different experts, such as human experts of the Website domain, and the cluster representatives of the user ratings. By these additional recom- mendation lists, Yoda is less impacted by the preprocessing work as compared to other systems During the online process, for each user who is using the system, Yoda estimates his/her confidence values to each expert, who provides the recommendation list, based on his/her current navigation behaviors through the PPed distance measure [25] and our GA-based learning mechanism. Subsequently, Yoda generates customized recommendations for the user by aggregating across recommendation lists using the confidence value as the weight. In order to expedite the aggregation step, Yoda employs an optimized fuzzy aggregation function that reduces the time computation complexity of aggregation from O(N X E to O(N), where N is the number of recommended items in the final recommendation list to users and E is the number of recommendation lists maintained in the system. Conse- quently, the online computation complexity of Yoda remains the same even if number of ndation lists in
176 SHAHABI AND CHEN 3. Synonymy: Since contents of the items are completely ignored, latent association between items is not considered for recommendations. Thus, as long as new items are not rated, they are not recommended; hence, false negatives are introduced. In order to solve these problems, a variety of different techniques have been proposed. Some of techniques, such as dimensionality reduction [22, 23], clustering [16], and Bayesian Network [3, 9], mainly are remedies for the scalability problem. These techniques extract characteristics (patterns) from the original dataset in an offline process and employ only these patterns to generate the recommendation lists in the online process. Although this approach can reduce the online processing cost, it often reduces the accuracy of the recommending results. Moreover, the online computation complexity keeps increasing with the number of patterns. Some other techniques, such as association rules [17, 23], content analysis [1, 2, 15], categorization [6, 12], are emphasized on alleviating the sparsity and synonymy problems. Basically, these techniques analyze the Web usage data (from Web server logs) to capture the latent association between items. Subsequently, based on both item association information and user ratings, the recommendation systems can thus generate better recommendation to users. However, the online computation time concurrently increases, as more data are incorporated into the recommendation progress. Additionally, because Web usage data from the server side are not reliable [26], the item association generated from Web server logs might be wrong. With Yoda [24], we introduced a hybrid recommendation model, which consists of two steps. During the offline process, Yoda generates cluster recommendation lists based on the Web usage data from the client-side through clustering and content analysis techniques. This approach not only can address the scalability problem by the preprocessing work, but also can alleviate the sparsity and synonymy problems by discovering latent association between items. Since the Web usage data from the client-side can capture real user navigation behaviors, the item association discovered by the Yoda system would be more accurate. Beside the cluster recommendation lists, Yoda also maintains numerous recommendation lists obtained from different experts, such as human experts of the Website domain, and the cluster representatives of the user ratings. By these additional recommendation lists, Yoda is less impacted by the preprocessing work as compared to other systems. During the online process, for each user who is using the system, Yoda estimates his/her confidence values to each expert, who provides the recommendation list, based on his/her current navigation behaviors through the PPED distance measure [25] and our GA-based learning mechanism. Subsequently, Yoda generates customized recommendations for the user by aggregating across recommendation lists using the confidence value as the weight. In order to expedite the aggregation step, Yoda employs an optimized fuzzy aggregation function that reduces the time computation complexity of aggregation from O(N × E) to O(N), where N is the number of recommended items in the final recommendation list to users and E is the number of recommendation lists maintained in the system. Consequently, the online computation complexity of Yoda remains the same even if number of recommendation lists increases
AN ADAPTIVE RECOMMENDATION SYSTEM 177 3. Overview The primary objective of a web-based recommendation system can be stated as follows Problem 1. Suppose the item-set /=[i l i is an item presented in a web-site) and u is a user interactively navigating the Web-site. The recommendation problem is to obtain the ut's wish-list I, e I. which is a list of items that are ranked based on us interests In general, to acquire a wish-list for a user, a recommendation process goes through three 1. Obtaining user perceptions: Data about user perceptions such as navigation behaviors are collected. In some systems [9, 22], these data need further processing for inferring information which is used in the later phases 2. Ranking the items: The inferred user interests are utilized to provide the predicted user wish-list 3. Adjusting user settings: The system acquires relevance feedback(or follow-up navigation behaviors)from the user and employs it to refine the user settings, which represent the user perceptions. On occasion, this phase is integrated into phase one Figure 1 illustrates the processing flow of Yoda. Suppose that music CDs are the recom- mending items in the Yoda web-site. The objective of Yoda is to provide each active user. who is using the system, a satisfactory-and-customized recommendation list of CDs by Experts wish-lists Other Experts' wish-lists Cluste Aggregat⊥on Learning List Cluster Centroi Update Confidence values User Navigation Figure 1. Processing flow of Yoda
AN ADAPTIVE RECOMMENDATION SYSTEM 177 3. Overview The primary objective of a web-based recommendation system can be stated as follows: Problem 1. Suppose the item-set I = {i | i is an item presented in a web-site} and u is a user interactively navigating the Web-site. The recommendation problem is to obtain the u’s wish-list Iu ∈ I, which is a list of items that are ranked based on u’s interests. In general, to acquire a wish-list for a user, a recommendation process goes through three steps/phases: 1. Obtaining user perceptions: Data about user perceptions such as navigation behaviors are collected. In some systems [9, 22], these data need further processing for inferring information which is used in the later phases. 2. Ranking the items: The inferred user interests are utilized to provide the predicted user wish-list. 3. Adjusting user settings: The system acquires relevance feedback (or follow-up navigation behaviors) from the user and employs it to refine the user settings, which represent the user perceptions. On occasion, this phase is integrated into phase one. Figure 1 illustrates the processing flow of Yoda. Suppose that music CDs are the recommending items in the Yoda web-site. The objective of Yoda is to provide each active user, who is using the system, a satisfactory-and-customized recommendation list of CDs by Figure 1. Processing flow of Yoda