Recommender systems : un approccio di ottimizzazione lineare intera

With the development of e-commerce sites, many sellers have decided to invest in Recommender Systems (RS), which analyze interest patterns of users in the products allowing to provide for a potential choices personal "recommendation". Due to the remarkable growth of the number of purchases made by users, these systems lead to obvious benefits in terms of income. In this thesis, three models of Mixed Integer Linear Programming (MILP) are proposed, which are compared with two of the most important Collaborative Filtering algorithms of RS, namely Biased Matrix Factorization (BMF) and Bayesian Personalized Ranking Matrix Factorization (BPRMF), both based on non linear optimization. The starting point of the first model is to exploit the BMF algorithm, adapting it in order to obtain a linear mixed integer type modeling. In the second model a piecewise linearized penalty term has been introduced in order to approximate the quadratic penalty adopted in BMF. At the end, in the third MILP model proposed the concepts of "concordant couples" and "discordant couples" are considered, which Kendall uses to calculate the Kendall Rank Correlation Coefficient, namely a coefficient to measure the accuracy of the predicted ratings. The comparison between the three models and the two non linear optimization based algorithms has been performed using two metrics of accuracy: Root Mean Square Error (RMSE) and Mean Average Precision (MAP). Using data from the data base provided by MovieLens, the obtained results highlight good values in terms of RMSE, but a MAP which is better only in certain cases.

Con lo sviluppo dei siti e-commerce molti venditori hanno deciso d’investire nei Sistemi di Raccomandazione (SR), che analizzando i pattern d'interesse degli utenti nei prodotti permettendo di fornire una “raccomandazione” personale sulle potenziali scelte. A Causa della notevole crescita del numero di acquisti effettuati dagli utenti, tali sistemi portano a evidenti benefici in termini di guadagno. In questa tesi, si propongono tre modelli di Programmazione Lineare Misto Intera (PLMI) che vengono confrontati con due tra i più importanti algoritmi di Filtraggio Collaborativo dei SR, ovvero Biased Matrix Factorization (BMF) e Bayesian Personalized Ranking Matrix Factorization (BPRMF), entrambi basati su metodi di ottimizzazione non lineare. Il punto di partenza del primo modello è di sfruttare l'algoritmo BMF, adattandolo in modo da ottenere un problema di ottimizzazione di tipo lineare misto intera. Nel secondo modello è stato introdotto un termine di penalità lineare a tratti in modo da approssimare la penalizzazione quadratica adottata nel BMF. Infine, nel terzo modello di PLMI proposto vengono considerati i concetti di “coppie concordanti” e “coppie discordanti” che Kendall usa per calcolare il Kendall Rank Correlation Coefficient, ossia un coefficiente per misurare l'accuratezza dei rating predetti. Il confronto tra i tre modelli e i due algoritmi basati sull’ottimizzazione non lineare è stato effettuato usando due metriche d’accuratezza: Root Mean Square Error (RMSE) e Mean Average Precision (MAP). Utilizzando i dati del data base fornito da MovieLens, i risultati ottenuti mostrano dei buoni valori in termini di RMSE, ma si ha un MAP migliore solo in determinati casi.