Applying memetic algorithm-based clustering to recommender system with high sparsity problem

Abstract

A new recommendation method was presented based on memetic algorithm-based clustering. The proposed method was tested on four highly sparse real-world datasets. Its recommendation performance is evaluated and compared with that of the frequency-based, user-based, item-based, k-means clustering-based, and genetic algorithm-based methods in terms of precision, recall, and F1 score. The results show that the proposed method yields better performance under the new user cold-start problem when each of new active users selects only one or two items into the basket. The average F1 scores on all four datasets are improved by 225.0%, 61.6%, 54.6%, 49.3%, 28.8%, and 6.3% over the frequency-based, user-based, item-based, k-means clustering-based, and two genetic algorithm-based methods, respectively.

Keywords

memetic algorithm / recommender system / sparsity problem / cold-start problem / clustering method

References

[1] AdomaviciusG, TuzhilinA. Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions [J]. IEEE Trans on Knowledge and Data Engineering, 2005, 17(6): 734-749

[2] ResnickP, VarianH R. Recommender systems [J]. Communications of the ACM, 1997, 40(3): 56-58

[3] SummutC, WebbG IEncyclopedia of machine learning [M], 2010, Berlin, Springer: 829-838

[4] MelvilleP, MooneyR J, NagarajanR. Content-boosted collaborative filtering for improved recommendations [C]. Proc of Intl Conf on Artificial Intell, 2002, CA, USA, American Association Intelligence: 187-192

[5] WengS S, LiuM J. Feature-based recommendations for one-to-one marketing [J]. Expert Syst with App, 2004, 26(4): 493-508

[6] SalterJ, AntonopoulosA. Cinema screen recommender agent: Combining collaborative and content-based filtering [J]. IEEE Mag on Intell Syst, 2006, 21(1): 35-41

[7] AdomaviciusG, KwonY. New recommendation techniques for multicriteria rating systems [J]. IEEE Mag on Intell Syst, 2007, 22(3): 48-55

[8] MooneyR J, RoyL. Content-based book recommending using learning for text categorization [C]. Proc of ACM Conf on Digital Libraries New York, USA: ACM, 2000195-204

[9] RicciF, WerthnerH. Case-based querying for travel planning recommendation [J]. Information Tech and Tourism, 2002, 4(3): 215-226

[10] LindenG, SmithB, YorkJ. Amazon.com recommendations item-to-item collaborative filtering [J]. IEEE Mag on Internet Computing, 2003, 7(1): 76-80

[11] ZhangF, ChangH. A collaborative filtering algorithm employing genetic clustering to ameliorate the scalability issue [C]. Proc of Intl Conf on E-Business Eng, 2006, Piscataway, USA, IEEE: 331-338

[12] LuoX, OuyangY, XiongZ. Improving neighborhood based collaborative filtering via integrated folksonomy information [J]. Pattern Recognition Letters, 2012, 33(3): 263-270

[13] SarwarB, KarypisG, KonstanJ, RiedlJ. Analysis of recommendation algorithms for e-commerce [C]. Proc of Conf on Electron Commerce New York, USA: ACM, 2000158-167

[14] AltingovdeI S, SubakanO N, UlusoyO. Cluster searching strategies for collaborative recommendation system [J]. Info Proc & Manage, 2013, 49(3): 688-697

[15] BreeseJ S, HeckermanD, KadieC. Empirical analysis of predictive algorithms for collaborative filtering [C]. Proc of Conf on Uncertainty in Artificial Intelligence, 1998, San Fracisco, USA, Morgan Kaufmann Publishers Inc: 43-52

[16] SarwarB, KarypisG, KonstanJ, RiedlJ. Item-based collaborative filtering recommendation algorithms [C]. Proc of Intl Conf on World Wide Web New York, USA: ACM, 2001285-295

[17] GoodN, SchaferJ B, KonstanJ A, BorchersA, SarwarB, HerlockerJ, RiedlJ. Combining collaborative filtering with personal agents for better recommendations [C]. Proc of Nat Conf on Artificial Intell, 1999, CA, USA, American Association Intelligence: 439-446

[18] CaoY, LiY. An intelligent fuzzy-based recommendation system for consumer electronic products [J]. Expert Syst With App, 2007, 33(1): 230-240

[19] ParkY J, ChangK N. Individual and group behavior-based customer profile model for personalized product recommendation [J]. Expert Syst with App, 2009, 36(2): 1932-1939

[20] LinP, YangF, YuX, XuQ. Personalized e-commerce recommendation based on ontology [C]. Proc of Int Conf on Internet Computing in Science and Engineering, 2008, Piscataway, USA, IEEE: 201-206

[21] ZhangJ, WangY, VassilevaJ. SocConnect: A personalized social network aggregator and recommender [C]. Info Proc & Manage, 2013, 49(3): 721-737

[22] Fernandez-lunaJ M, HueteJ F, CastellsP. Personalization and recommendation in information access [J]. Info Proc & Manage, 2013, 49(3): 637-639

[23] MarungUA novel clustering method and its application to E-commerce recommendation systems [D], 2013, Chiang Mai, Chiang Mai University

[24] KrasnogorN, SmithJ. A tutorial for competent memetic algorithms: model, taxonomy, and design issues [J]. IEEE Trans on Evol Computation, 2005, 9(5): 474-488

[25] NeriF, CottaC, MoscatoPHandbook of Memetic Algorithms [M], 2012, Berlin, Springer: 1-370

[26] YustaS C. Different metaheuristic strategies to solve the feature selection problem [J]. Pattern Recognition Letters, 2009, 30(5): 525-534

[27] GuimaraesF G, CampeloF, IgarashiH, LowtherD A, RamirezJ A. Optimization of cost functions using evolutionary algorithms with local learning and local search [J]. IEEE Trans on Magnetics, 2007, 43(4): 1641-1644

[28] HrncicD, MernikM, BryantB R. Improving grammar inference by a memetic algorithm [J]. IEEE Trans on Syst Man, and Cybernetics, 2012, 42(5): 692-703

[29] WangZ, SunX. An efficient web query optimization algorithm based on LDA and MA [C]. Proc of Int Conf on Multimedia and Inform Tech, 2008, Piscataway, USA, IEEE: 50-53

[30] NeriF, MininnoE. Memetic compact differential evolution for cartesian robot control [J]. IEEE Mag on Computational Intell, 2010, 5(2): 54-65

[31] AydemirM E, GunelT, KarginS, ErerI, KurnazS. SAR image processing by a memetic algorithm [C]. Proc of Int Conf on Recent Advances in Space Technologies, 2005, Piscataway, USA, IEEE: 684-687

[32] BanatiH, MehtaS. Memetic collaborative filtering based recommender system [C]. Proc of Int Conf on Inf Tech for Real World Problems, 2010, Washington DC, USA, IEEE Computer Society: 102-107

[33] AngJ H, TanK C, MamunA A. An evolutionary memetic algorithm for rule extraction [J]. Expert Syst With App, 2010, 37(2): 1302-1315

[34] GoldbergD EGenetic algorithms in search, optimization, and machine learning [M], 1989, Boston, USA, Addison-Wesley Publishing Company, Inc.: 1-432

[35] KimK J, AhnH. A recommender system using GA k-means clustering in an online shopping market [J]. Expert Syst With App, 2008, 34(2): 1200-1209

[36] JainA K, MurtyM N, FlynnP J. Data clustering: A review [J]. ACM Computing Surveys, 1999, 31(3): 265-323

[37] JainA K. Data clustering: 50 years beyond k-means [J]. Pattern Recognition Letters, 2010, 31(8): 651-666

[38] MarungU, Theera-umponN, AuephanwiriyakulS. Visual clustering method using genetic algorithm and image manipulation [C]. Proc of IEEE Int Symp on Intell Signal Process and Commun Syst, 2011, Piscataway, USA, IEEE: 1-5

[39] DunnJ C. A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters [J]. Journal of Cybernetics, 1973, 3(3): 32-57

[40] KarypisG. Evaluation of item-based top-N recommendation algorithms [C]. Proc of Int Conf Inf and Knowledge Manage, 2001, New York, USA, ACM: 247-254

[41] HerlockerJ L, KonstanJ A, TerveenL G, RiedlJ T. Evaluating collaborative filtering recommender systems [J]. ACM Trans on Inf Syst, 2004, 22(1): 5-53