a Recommender system Based on Genetic Algorithm for Music Data Hyun-Tae Kim, Eungyeong Kim, Jong-Hyun Lee, Chang Wook Ahn School of Information Communication Engineering Sungkyunkwan University (SKKU) Cheoncheon-dong, Suwon 440-746, SKorea *cwan @skku. edu(corresponding author Abstract -Nowadays, recommender systems are widely In this paper, a new recommender system for implemented in E-commerce websites to assist customers in music data b g the content-based filter finding the items they need A recommender system should technique with active genetic algorithm. We also be able to provide users with useful information about the consider the unique properties of each music track, such as items that might interest them. The ability of promptly tempo, pitch and chord. We use a music feature extraction responding to changes in user's preference is a valuable as tool to analyze these properties. The results of the extraction for such systems. This paper presents an innovative consist in the database of our proposed system. We expect recommender system for music data that combines two that the proposed system will provide more suitable methodologies, the content-based filtering technique and the information, which adapts to the preference of each user, by interactive genetic algorithm. The proposed system aims to effectively adapt and respond to immediate changes in use applying the genetic algorithm to the system. The user ferences. The experiments conducted in an objective pref manner exhibit that our system is able to recommend items acquiring records, the recommender system analyzes and suitable with the subjective favorite of each individual user. recommends items that are appropriate with their own favorite mender system; user's prej This paper is organized as follow. Section II reviews interactive genetic algorithm; content-based related work. Section ii describes the structure of our recommender system and explains how to op erate genetic algorithm in this system. In Section IV, we provide In daily life it is often necessary to make a decision experimental results and analysis. Finally, Section V without resort to enough personal experience of various concludes this paper alternatives. When the alternatives domain is quite large, it is difficult for users to make an appropriate decision. For IL. RELATED WORK example, many people might rely on recommendations from A. Recommender Systems knowledge or advertisements, and reviews about and book in magazines. Such diverse references ma The main issue of a recommender system is how to recommend items tailored with users preference from Ip the users in making a proper choice. In this regard, a resources. The recommender system also has to recognize recommender system has the same usefulness, but provides the users with a refined list of alternatives tailored with their and provide items corresponding with favorite of users. In own preferences [1],[2 order to resolve this matter, there are two main approaches Recommender systems are useful for people living in collaborative filtering and content-based filtering [4] these days. After the 1990s of the 20th century, the Internet In the collaborative filtering approach, the recommender technologies, especially World Wide Web, have grown with system provides recommendation by collecting users astonishing speed. With this change, there are numerous profiles and discovers relations between each profile. After resources, such as document, photo and music data, which identifying correlation of each profile, the system classifies are accessible on the Internet. Many of end users having profiles that are similar to the others. The customers will face the problem that which resource is more ystem then recommends items derived from other profiles suitable than the others. Many of the largest commerce in the same group. The advantage of this approach, thus, is websites, thus, have already been using recommender that it has a high possibility to recommend items tems to assist their customers in searching items they corresponding with users preference by providing ould like to purchase, such as the b-commerce web site environments in which each user can share his or her own Amazon.comandthesearchengineofGooglecomTheseprofile[51,[6] In the altermative approach, the content-based filt systems provide with the search results tailored to users own the recommender system examines the description of the preference 3] items which are rated higher than others from users. After 978-1-4244-6349-7/10/$26.00@2010EEE V6414
! " # $ % & ' ( )$ ! & &. , - * ,+ $ . 00/ 201 3 '. 4&&3* 5 + ! " ! # $ # $ (3 (6 7,$ (76 ( & . 5 85 - -3% - 9 & 55 5 3 : 8 5 5 5 ; & . - -. A @?A3 5 5 - 3 >BB/ ?/ ( 5% %%< - . . 53 % 5 . < ( 3 .5 < . < 3 .< - < . & 5 ! .< = 3 3 3 5 -. ; . 5 @CA3 ( 55 .5 5 . < < < 9 . - 3 % 9 5 5 & 5 5 3% 8 =5 5 3 8 < 5 5 3% 85 5 5 . 5 - < .5 5 < 55 3 5 < 3 9 = 55 5 . . - 3 55 = .3 (( -. . &3 ((( < 85 . 5 3 ( (D .5 - 85 3 : D 55 3 ((3 !# !%7 . . ; 5 3 = 5 - 5 . - 3 ( - . 55 E @0A3 ( < - 55 5 - < ; 5 - <. 5 3 5 - 5 3 - 5 53 - 55 5 < 5 . ; 5 < 5 - - . . 5 @FA @1A3 ( - 55 < 8 5 . 3 978-1-4244-6349-7/10/$26.00 c 2010 IEEE V6-414
een Number Artst examined items and all of the remaining items. The system ExTracted Hearnes then makes recommendation of new items by ordering based on its high similarities with the selected items [5], [6 However, the content-based approach has the limitation such that it focuses on only the accessed items and is not prompt to immediate changes in the potential interest of Figure 1. The composition of individuals users. To overcome these limitations. we combine the content-based filtering approach and the genetic algorithm in A. Feature Extraction Phase ur proposed system. In this phase, we perform feature extraction to each B. Music feature extraction music track using CLAM; all of music track are formatted as The feature extraction is a technique that derives MP3(Mpeg-1 Audio Layer 3). The CLAM outputs properties from specific data, such as music, document and extraction results as XML files containing music features of photo. It is also each track. The system then parses the XMl files to generate for grouping static resources. In our initial individuals for IGA. Our proposed system considers proposed system, we employ the content-based filtering to five extracted features which consist of real numbers. Fig. 1 acquire information from music data. The analysis of items is shows the example of an IGA's individual composed of the sential step of filtering items in the content-based ng approach. We then use a feature extraction tool (i.e. extracted features M) to analyze the properties of items B. Evaluation phase As a software framework for research and application development on the audio and music domain, the CLaM The proposed recommender system grants its users the role of evaluation the fitness value of each music track. each provides complex audio signal analysis, transformations and user assigns his or her own rating scores to music tracks according to their subjective preferences. By this means of C. Interactive Genetic Algorithm the scoring metric, the users can represent their favor rating enetic Algorithms(GAs)are stochastic search methods to different recommended items. The recommender system inspired from the mechanism of natural evolution and evolves a population based on user evaluation data genetic inheritance. GAs work on a population of candidate C. Interactive Ga Phase solutions; each solution has a fitness value indicating its Interactive Ga phase is the fundamental component of closeness to the optimal solution of the problem. The our system since it proposes promising items (i.e. music solutions having higher fitness values than others are track) to the users based on their own evaluations selected and also survive to the next generation. GAs then Similar to the genetic algorithm, IGA also works on the produce better offspring (i.e. new solutions)by the basis of genetic inheritance and it has evolutionary operators combination of selected solutions. The methods can discover, (i. e, selection, crossover and mutation) preserve, and propagate promising sub-solutions [7],[ 8] In this system, we do not consider mutation because we Interactive Genetic Algorithm (IGA) is also an focus on finding items which are most appropriate to us optimization method as the genetic algorithm. In IGA however the fitness values of candidate solutions are based preferences. Since the mutation operator would cause candidate solutions to deviate from the common pattem on the evaluations of users according to their own discovered by the evolution process, it should omit. Fig. 2 preferences [9]. Our proposed system uses IGa to recognize shows how to operate Interactive Ga phase in this system user favorite since the user can judge the fitness value of each solution (i.e, music track). The user preference, thus, evaluation (i.e, Evaluation Phase) and the algorithm executes three separate steps (Selection, Crossover and IIL. SYSTEM OVERVIEW Matching)as shown in Fig. 2 1) Selection: We apply the truncation selection method The recommender system described in this pa n the genetic algorithms. The content-based this system, since the item having lower rating scores technique is applied to generate the initial population of hould not be considered to make new recommendation genetic algorithms. In the proposed system, we employ the elitism to impose high selection pressure to favor the top T% interactive genetic algorithm so that the users can directly evaluate fitness values of candidate solution themselves. Due (the constant variable T) candidate solutions having higher to the subjective evaluations, our system can recognize and itness values. The remaining items having lower rating recommend items tailored with different user preferences scores are then discarded [10], [11]. After the selection, half recommender system is divided into three ph of the selected items would be applied the crossover operator follow: feature extraction, evaluation and Interactive Ga in a probabilistic manner. phase http://www.clam-project.org Volume 6] 2010 2nd International Conference on Computer Engineering and Technology V6-415
5 = " ! # *+ 5 - 3. & 5 5 G - 5 5 5EKK...3 5 I3 : >3 5 - &# ( 5 . 5 8 & $#G & LC *5 > # C+3 $# 5 8 M# &3 5 M# - (3 7 5 5 -8 . .8 5 (; - 5 8 3 &# 5 5 - - &3! . & /A @>>A3 . <55 - 5 5 << 3 [Volume 6] 2010 2nd International Conference on Computer Engineering and Technology V6-415
Evaluation From User Evaluation distance(s, t) ,(S1-t,)(1) Evaluation phase where distance(s, t)is the Euclidean distance between two nteractive G Phase items. The variable n is the number of music features and m Selection indicates the length of each property Truncation Selection Note that before calculating distance between two items, the values of music features are normalized to the range of o and l IV. THE EXPERIMENT Probability P In this section, we describe the implementation of our P To assess the performance of our proposed system, we performed experiments on the built website, 10 users were asked to evaluate 7 pages(a total of 70 items per each user) (3)Repeat step(2)as same as X(t+1) he evaluation results were automatically collected in our system's database. We measured the average score of rating for each page. However, we excluded two malevolence users Figure 3. The operation of BLX-a Crossover (in evaluating scores) by inspecting the scores of successive 2)Crossover: In the crossover step, the system executes Artst Name Rating BLX-a Crossover [12], because the music features are My love (Feat. NC Mong) ★★★★★ represented as real numbers in this system. Fig. 3 shows 3 KMiI how to apply BLX-a Crossover on the selected individuals. s Samey alate similarity 78 Super unior Somy Soy between music features of selected items resulted from the ★女女女安 previous operations and all the remaining items in the 6 4Nna ★★★安安 system storage. Each individual has its own unique 9 After chod 安女女女女 properties extracted by CLAM(descried in Feature 13 Dmamk uo ★★★★女 Extraction Phase). This system, thus, calculates the SG Wannabe 女女女女卖 similarity by checking the distance of the properties of each ★★女女 Figure 4. The experiment website V6-416 10 2nd International Conference on Computer Engineering and Technology TVolume 6]
: ?3 5 ( -5 : C3 5 #M O$ - +' )( - 5 8 #M O $ - @>?A ++3 * + - - - > ? > * + > . * + ! 3 (D3 !!ML!(!6 ( . //3 ! - 5 >/ 3 5 / . & -25* 2/ 5 +3 - . ;<3% - 53 .- .8. - * - +< 5 - 53 : 03 85 .< V6-416 2010 2nd International Conference on Computer Engineering and Technology [Volume 6]
Communications of the ACM, vol 40, no 3, pp 56-58, 1997. [1 P. Resnick and H. R. Varian, " Recommender [2]L. Terveen and w. Hill, "Beyond Recommender Systems: Helping cople Help Each Othe HCI in the New Millennium, pp. 487- 3]J. Schafer, J Konstan, and J. Riedl, "Recommender Systems in E- the Ist ACM conference on Electronic commerce, pp 158-166, NY: USA, 1999 14 M. Balabanovic and Y. Shoham, "FAB: Content-based, Collaborative Recommendation, Communications of the ACM, vol 5]R. Burke, "Hybrid Web Recommender Systems, "Lecture Notes in The number of items rated over 80 Heidelberg, 200 Figure 5. The experiment result of 10 users for 7 pages for Collaborative Demographic Filtering, " Artificial Intelligence Review, voL 13,no5- g 6,pp.394408,1999 recommender system. We did not consider results of the first 7 M. Mitchell, dn Introduction to Genetic Algorithm, MIT Press, 1998 items on this page than other pages. Besides, the users need [8] D. E Gold berg and J.H. Holland, "Genetic Algorithms and Ma page since users tend to rate too much higher values for to become familiar with the rating mechanism of our system. [9 H. Takagi, "Interactive Evolutionary Computation: Fusion of the Also, we measured the number of items that were rated over 80 for each pages because these items have more impact to Proceedings of the IEEE, vol. 89, pp. 1275-1296, 200 trace users'preference than others. As seen in the figure, the [10] D. Thierens and D. Goldberg, "Elitist Recombination: An Integrated (i.e, as the generation goes by/ l e page number scores gradually improve as the Conference on Evolutionary Computation, pp. 508-512, 1994 re satisfied with the recommendation made by our [J J. E Crow and m ra,"Efficiency of Truncation system. In other words, the results prove the efficacy of our Proceedings of the National Academy of Sciences of the f America, voL. 76, no. 1, pp 396- recommender system in detecting and tracing the preference [12J F. Herrera, M. Lozano, and J. L. Verdegay, " Tackling Real-coded of each user ms:Operators and Tools for Behavioural Analysis, Artificial Intelligence Review, voL. 12, pp. 265-319, 1998 V CONCLUSION In this paper, we presented a novel recommender system for or music data. Our proposed system is able to recognize the preference of users and then adaptively recommend music tracks appropriate for their present atmosphere To construct the system, we incorporated the main interactive genetic algorithm-based engine with the content- based filtering method. First, the unique features of each music track are extracted. We then apply the interactive genetic algorithm to obtain the most appropriate tracks to recommend to users. The proposed system enables users to evaluate the fitness of each recommended item according to eir preferences. Therefore, our system can gradually adapt its recommendation with the subjective decision of each user. The experimental results exhibited that the average scores, which are objectively collected by means of user aluations, increases by degrees as th denotes that the proposed system can help the users obtain various music tracks suitable with their own preference. Therefore, we believe that the recommender system retains enough potential to be implemented and applied to other platforms(e.g, standalone program, web service and mobile device) This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government(MEST)(No. 2009-0066229 Volume 6] 2010 2nd International Conference on Computer Engineering and Technology V6-417
: F3 85 >/ 25 :3 F . 5 5 5 3% 5 - 5 53 A L3 & 3 3 D P Q # - 30/ 3C 553F1RFH >BB23 @?A #3 - %3 P E 5 L 5 5!7 Q . " # / 0 553 0H2R F/B % ?//>3 @CA "3 "3 "3 P ! Q & # ( 553>FHR>11 6JE, >BBB3 @0A 3 BB23 @FA 3 & P 553 C22R0/H 5 E C 3F 1 553CB0R0/H >BBB3 @2A 3 " ! # ( L >BBH3 @HA 3!3 BHH3 @BA 3 & P( - !- $ 5 E : $5?2FR>?B1 ?//> @>/A 3 3 ? >BB03 @>>A "3:3$ . 3 P! Q & # / # 2 - 321 3> 553CB1RCBB >B2B3 @>?A :3 3 # = "3 #3 D P & E75 - Q " 0 - 3>? 553?1FRC>B >BBH3 [Volume 6] 2010 2nd International Conference on Computer Engineering and Technology V6-417