<figure><img src="image_1.png" /></figure>

HAL
open science

Personalized Recommendation Using Extreme
Individual Guided and Adaptive Strategies

Yifei Cao, Yifei Sun, Shi Cheng, Kun Bian, Zhuo Liu, Xin Sun, Jie Yang

► To cite this version:

Yifei Cao, Yifei Sun, Shi Cheng, Kun Bian, Zhuo Liu, et al. Personalized Recommendation Using Extreme Individual Guided and Adaptive Strategies. 5th International Conference on Intelligence Science (ICIS), Oct 2022, Xi'an, China. pp.158-165, 10.1007/978-3-031-14903-0_17. hal-04666443

HAL Id: hal-04666443

https://hal.science/hal-04666443v1

Submitted on 1 Aug 2024

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_3.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
Personalized Recommendation Using Extreme Individual
Guided and Adaptive Strategies

Yifei Cao¹, Yifei Sun¹*, Shi Cheng², Kun Bian¹, Zhuo Liu¹, Xin Sun¹and Jie Yang¹

¹ School of Physics and Information Technology, Shaanxi Normal University, Xi'an, China
{yifeic,yifeis,biankun,zhuoliu,sunxin_,jieyang2021}@snnu.edu.cn

² School of Computer Science, Shaanxi Normal University, Xi'an, China
cheng@snnu.edu.cn

**Abstract.** In the era of information explosion, recommender systems have been widely used to reduce information load nowadays. However, mainly traditional recommendation techniques only paid attention on improving recommendation accuracy without considering additional criteria such as diversity, novelty. Moreover, such traditional recommendation algorithms were also struggled with matthew effect, that is, the gap between the popularity of popular and non-popular items grows. Therefore, a multi-objective recommendation model with extreme individual guided and mutation adaptation based on multi-objective evolutionary algorithms (MOEA-EIMA) is proposed in this paper. It maximizes two conflicting performance metrics termed as precision and novelty. In MOEA-EIMA, the iteration of population is guided by extreme individuals, and the adaptive mutation operator is designed for saving the better individuals. The algorithm is tested in several sparse datasets. The experiment results demonstrate the proposed algorithm can achieve a good trade-off between accuracy and novelty.

**Keywords:** Recommender systems, Multi-objective evolutionary optimization, matthew effect, accuracy, novelty

# 1 Introduction

Recommender systems are not only an important tool in our daily life, but also a key component of commercial enterprise [1]-[2]. The great commercial value and practical significance of recommendation system make it one of the hottest research projects nowadays [3]. The traditional recommendation algorithms can be divided into three types: content-based, collaborative and hybrid filtering [4]-[6].

Since some other additional criteria are as important as accuracy, more and more personalized algorithms based on multi-objective evolution are proposed [7]-[10]. Zang and Hurley [11] modeled the recommendation problem as a quadratic programming problem. Zhuo [12] introduced a hybrid algorithm which used HeatS to improve diversity and Probs to increase the accuracy. Zuo et al. [13] proposed a multi-objective recommendation algorithm combining MOEA and ProbS to improve the diversity with high accuracy. Wei et al. [14] proposed a hybrid probabilistic multi-objective
evolutionary algorithm to optimizes the profit and diversity. However, the Matthew effect, which is the growing gap between the popularity of popular and non-popular items, has not been well addressed. This will lead to the long tail problem.

In this paper, a multi-objective recommendation model with extreme individual guided and mutation adaptation called MOEA-EIMA are proposed to improve the accuracy and the novelty. In MOEA-EIMA, the top-n maximum points on the two objectives of each user are used for constitute the extreme individuals. In addition, during the process of iteration, adaptive operators make it possible to retain elites and conduct better global searches. Experimental results show that the proposed method has a good performance in improving the degree of novelty without reducing the accuracy.

The rest of this paper is organized as follows. In Section 2, the definition of the recommendation and some preliminaries of multi-objective optimization are introduced. The details of this work are given in Section 3. Section 4 presents the performances of our algorithm. Finally, we conclude our work in Section 5.

# 2 Background

## 2.1 Definition of Recommendation Problem

Let the set *Users* contains all the users and the set *Items* contains all the recommended items in the system. *R*(*i*, *α*) means the preference of a user *i* to an item *α*. As only a few numbers of products are rated by each user, recommender system should predict the preference of user for unknown products through a certain recommendation method first. Then, a recommendation list is generated based on the predicted rating i.e.,

$$ \forall i \in C, \alpha = \arg\max R \quad (1) $$

## 2.2 Multi-Objective Optimization Problem

A multi-objective optimization problem is defined as follows [15]:

$$ \min F(x) = (f_1(x), f_2(x), \dots, f_m(x))' \quad (2) $$

where $x = [x_1, x_2, \dots, x_d] \in \Omega$ is the decision vector, and $\Omega$ is the D-dimensional decision space.

The goal of a MOP is to find out a set of non-dominated to approximating the true Pareto front. The definition of Pareto set and Pareto front are shown in Eq. (3) and Eq. (4), respectively.

$$ PS = \{x \in \Omega | \neg \exists x^* \in \Omega, x^* > x\} \quad (3) $$

$$ PF = \{F(x) | x \in PS\} \quad (4) $$
## 2.3 Probs

The Probs [16] is a suitable method for the recommendation systems without explicit ratings. The specific operation is that the initial resource placed on each item is equally distributed to all neighboring users, and then redistributed back to those users' neighboring items in the same way. The transition matrix can be computed by (5), where M represents the total number of users, $k_i$ is the degree of the item node i. The element $\omega_{\alpha\beta}$ in this matrix denotes the fraction of the initial resource of $\beta$ transferred to $\alpha$.

$$ \omega_{\alpha\beta} = \frac{1}{k_{\beta}} \sum_{i=1}^{M} \frac{r_{i\alpha} r_{i\beta}}{k_i} \qquad (5) $$

# 3 Proposed Algorithm

## 3.1 Framework of MOEA-EIMA

The process of a MOEA-EIMA is divided into two stages: project scoring evaluation and multi-objective optimization. In the project evaluation stage, according to the historical user-project evaluation matrix, some project evaluation algorithms predict the unknown evaluation of the project of each input user. In the multi-objective optimization phase, the initial solution and parameters of the multi-objective optimization algorithm are initialized as a loop process. During the loop, the fitness value, which is calculated by the objective function, is calculated first. New solutions are then generated by crossover and mutation manipulation of the original solution, and the next generation solution is updated by comparing the old and new solutions. This looping process repeats until the termination condition is met. The final solution is to output the recommendation results.

## 3.2 Individual Encoding and Initialization

Generally, all the items recommended to a user will be encoding to the chromosome with their item number as a matrix. For L items will be recommended to K users separately, we build a K*L matrix as the Table 1. shows, where rows represent users and columns represent items. It should be taken a note that one item will not be recommended to a user twice and the rated item can't be recommended. This means duplicate numbers do not appear on the same line.

Since the extreme points in the prediction matrix have a positive effect on extending the Pareto-optimal front [17]. In this paper, all selectable items under each target value for each user are ranked. The top-n points on each objective are selected into the initialized individuals of the population as extreme value points in the initialization process. These extreme individuals will guide the algorithm during the evolutionary process.
<table><caption>**Table 1.** Illustration of chromosome encoding.</caption><thead><tr><th></th><th>Item 1</th><th>Item 2</th><th>...</th><th>Item L</th></tr></thead><tbody><tr><td>User 1</td><td>3</td><td>6</td><td></td><td>15</td></tr><tr><td>User 2</td><td>1</td><td>29</td><td></td><td>9</td></tr><tr><td>...</td><td></td><td>...</td><td></td><td></td></tr><tr><td>User K</td><td>17</td><td>26</td><td></td><td>10</td></tr></tbody></table>

### 3.3 The Two Objectives

Since the scoring matrix is generally a sparse matrix, predicted rating should be calculated based on Probs first just as Section 2.3 said. Each item rated or unrated will have its own predictive rating which equal to $f'_{\alpha}$. We measured the accuracy as following formula for each user:

$$PR = \frac{\sum_{U \in S} \sum_{i=1}^{N} f'_{\alpha_{u,i}}}{P * L} \qquad (6)$$

where S is the user number, N is the number of items to be recommended, $f'_{\alpha_{u,i}}$ is the predicted rating for item i given by user u, P denotes the population size, L means the length of recommendation list.

Recommend popular products all the time will maintain the high accuracy of the recommendation system. Novelty is a measure of a recommender's ability to recommend non-hot form items to users, so high novelty can often lead to lower accuracy. The novelty of the recommended list is calculated from the item's self-information. The self-information of item i can be calculated as:

$$SI_i = \log_2(\frac{M}{k_i}) \qquad (7)$$

where $k_i$ is the degree of the item i.

The mean value of the sum of all items' self-information given by the computing system to all users is the novelty of the recommended result.

$$Nov(N) = \frac{1}{SN} \sum_{u=1}^{S} \sum_{i \in O_L^u} SI_i \qquad (8)$$

where $O_L^u$ is the list recommended to user u.

### 3.4 Genetic Operators

The uniform crossover is more applicable to our work. Since it is not possible to recommend an item twice to a user at the same time, we need to add a judgment to the crossover to avoid generating invalid solutions. This judgment identifies elements that are identical in both parents and passes them directly to the offspring. The other elements follow the following operation. A random number is generated in [0,1], and if
this number is greater than 0.5, child 1 will get the corresponding allele from parent 1. Otherwise the allele will be obtained from parent 2. The graphical representation of the crossover operator is shown in Fig. 1.

<figure><img src="image_4.png" /><figcaption>Fig. 1. Illustration of crossover operator. Only the positions without slash perform crossover. Two generated random numbers are 0.2 and 0.6, respectively</figcaption></figure>

In the mutation operation, the following formula is used to adjust the individual mutation rate so that it changes smoothly:

$$p_m^i = \begin{cases} \frac{0.5}{1 + e^{-\alpha_1(i - N_s)}}, & i < N_s \\ \frac{0.5}{1 + e^{-\alpha_2(i - N_s)}}, & i \ge N_s \end{cases} \qquad (9)$$

where the parameters $\alpha_1$, $\alpha_2$ and $N_s$ are set to 0.2, 0.1, 0.4, respectively.

# 4 Experiments and Analysis

## 4.1 Experiment Settings

The performance of the algorithm is evaluated on the datasets from MovieLens. This data set can be downloaded from the web of GroupLens Research (http://www.grouplens.org/). This data set contains 943 users and 1682 movies. Since the Probs algorithm is applied to the 0-1 rating system, an item will be rated as 1 if its score is equal or greater than 3, and otherwise, it will be rated as 0.

As for the partition of the data set, we divided the whole data set into five disjoint parts. Then we randomly select 80% of the data as the training set, and 20% of the data set constitutes the test set. The sparsity, which is defined as the number of links divided by the total number of user-object pairs, of all training data sets is $5.94 \times 10^{-3}$. A sparse data set indicates that only a few items are rated by users. This means the recommendation systems may face the cold-start problem. The parameter setting is shown in Table 2.

Precision is widely used to measure the accuracy of recommendations [18]. For a given user $i$, precision $P_i(L)$ is defined as

$$P_i(L) = \frac{d_i(L)}{L} \qquad (10)$$
where $d_i(L)$ is the number of relevant items, which are in the recommendation list and also preferred by user $i$ in the probe set. The obtained mean precision of all users can reveal recommendation accuracy of RSs.

Besides, the hypervolume [19] is adopted as the performance metrics.

<table><caption>**Table 2.** Parameter settings of the algorithm.</caption><thead><tr><td>Algorithms</td><td>Parameters Settings</td></tr></thead><tbody><tr><td>User-based-CF</td><td>L=10</td></tr><tr><td>MF</td><td>L=10</td></tr><tr><td>MOEA-Probs</td><td>Pc=0.8, Pm=1/L, L=10, Gen=3000</td></tr><tr><td>MOEA-EIMA</td><td>Pc=0.8, L=10, Gen=3000</td></tr></tbody></table>

## 4.2 Experimental Results

In this section, we compare MOEA-EGMA with four existing algorithms (i.e., MOEA-EPG, MOEA-Probs, and User-based-CF). To study the effectiveness of MOEA-EIGA, the final PF with the highest hypervolume for every data set are shown in Fig. 2. The mean hypervolume values of the non-dominated solutions form 30 independent runs are shown in Table 3.

<figure><img src="image_5.png" /><figcaption>**Fig. 2.** Final recommendation results for (a) Movielens 1, (b) Movielens 2, (c) Movielens 3, (d) Movielens 4, (e) Movielens 5</figcaption></figure>
In Fig. 2, Experimental results show that MOEA-EIGA can obtain better novelty at the same accuracy under sparse matrices than User-based-CF. MOEA-EPG have a better performance for the accuracy. For the novelty, MOEA-Probs performs better. Adaptive operators give higher-ranked individuals a lower probability of variation, while lower-ranked individuals have a higher probability of variation. This makes MOEA-EIGA a great improvement in both accuracy and novelty. The guidance of the extremum individual ensures the MOEA-EIMA can always get a longer Pareto front than others. The highest mean hypervolume indicate that the MOEA-EIMA performs more steadily than MOEA-Probs and MOEA-EPG. Since the two objectives are non-negative obviously, the reference point for computing hypervolume is set to the origin.

<table><caption>Table 3. HV comparison results</caption><thead><tr><th>Data Set</th><th>MOEA-EIMA</th><th>MOEA-EPG</th><th>MOEA-ProbS</th></tr></thead><tbody><tr><td>Movielens 1</td><td><strong>2.7890</strong></td><td>0.8395</td><td>0.6035</td></tr><tr><td>Movielens 2</td><td><strong>3.5887</strong></td><td>1.3691</td><td>1.1346</td></tr><tr><td>Movielens 3</td><td><strong>4.2556</strong></td><td>1.7183</td><td>1.5424</td></tr><tr><td>Movielens 4</td><td><strong>4.4805</strong></td><td>1.8332</td><td>1.7055</td></tr><tr><td>Movielens 5</td><td><strong>4.4639</strong></td><td>1.9265</td><td>1.7193</td></tr></tbody></table>

# 5 Conclusions

In this article, the accuracy and novelty are used as indicators to build multi-objective models to try to solve the Matthew effect in the recommendation system. In the initialization phase we added two extreme individuals on accuracy and novelty to enhance the local search. Adaptive variation operators are added to the cross-variation phase to make sure the top-ranking individuals have a lower mutation probability. Experimental results show that the algorithm is effective and efficient to find a set of trade-off solutions between recommending popular items and non-hot items.

Although the algorithm has increased the novelty of the recommendation system, the value of non-popular goods is far higher than imagined, that is, the long tail problem has not been better solved. Our future work will focus on how to better extract the value of non-popular commodities and apply it to large-scale data sets.

*Acknowledgement.* This work was supported by the National Natural Science Foundation of China (Grant No. 61703256, 61806119), Natural Science Basic Research Plan in Shaanxi Province of China (Program No. 2022JM-381, 2017JQ6070) and the Fundamental Research Funds for the Central Universities (Program No. GK201803020, GK201603014).

# References

1. Resnick, P., Varian, H. R.: Recommender systems. Communications of the ACM, 40(3), 56–58 (1997)
2. Bobadilla, J., Ortega, F., Hernando, A., Gutiérrez, A.: Recommender systems survey. Knowledge-Based Systems, 46, 109-132 (2013).

3. Shi, X., Wei, F., Zhang, G.: A Personalized Recommendation Algorithm Based on MOEA-ProbS. Springer, Cham (2018)

4. Adomavicius, G., Tuzhilin, A.: Toward the next generation of recommender systems: a survey of the state-of-the-art and possible extensions. IEEE Transactions on Knowledge and Data Engineering, 17(6), 734-749 (2005)

5. Pazzani, M. J., D Billsus.: Content-based recommendation systems. Springer-Verlag (2007)

6. Yang, Z., Lin, X., Cai, Z.: Collaborative filtering recommender systems. Foundations & Trends® in Human Computer Interaction, 4(2), 81-173 (2007)

7. Wang J., Liu Y., Sun J., Jiang Y., Sun C.: Diversified Recommendation Incorporating Item Content Information Based on MOEA/D, 2016 49th Hawaii International Conference on System Sciences (HICSS), pp. 688-696 (2016)

8. Mcnee, S. M., Riedl, J., Konstan, J. A.: Being accurate is not enough: How accuracy metrics have hurt recommender systems. Extended Abstracts Proceedings of the 2006 Conference on Human Factors in Computing Systems, CHI 2006, Montréal, Québec, Canada, April (2006)

9. Hurley, N., Zhang, M.: Novelty and diversity in top-n recommendation -- analysis and evaluation. ACM Transactions on Internet Technology, 10(4), 14 (2011)

10. Castells, P., Vargas, S., Wang, J.: Novelty and diversity metrics for recommender systems: choice, discovery and relevance. Proceedings of International Workshop on Diversity in Document Retrieval (2011)

11. Zhang, M., Hurley, N.: Avoiding monotony: improving the diversity of recommendation lists. In: Proceedings of the ACM Conference on Recommender Systems, New York, pp. 123-130 (2008)

12. Zhou, T., Kuscsik, Z., Liu, J.G., Medo, M., Wakeling, J.R., Zhang, Y.C.: Solving the apparent diversity-accuracy dilemma of recommender systems. Proc. Natl. Acad. Sci. 107(10), 4511-4515 (2010)

13. Zuo, Y., Gong, M., Zeng, J., et al.: Personalized recommendation based on evolutionary multi-objective optimization. IEEE computational intelligence magazine, 10(1), 52-62 (2015)

14. Wei, G., Wu, Q., Zhou, M. C.: A hybrid probabilistic multiobjective evolutionary algorithm for commercial recommendation systems. IEEE Transactions on Computational Social Systems, PP(99), 1-10 (2021)

15. Adomavicius, G., Manouselis, N., Kwon, Y. O.: Multi-criteria recommender systems In: Ricci, F., Rokach, L., Shapira, B., Kantor, P. (eds) Recommender Systems Handbook. Springer, Boston, MA (2011)

16. Zhou T, Ren J, Medo M, Zhang Y.: Bipartite network projection and personal recommendation. Physical review, E. Statistical, nonlinear, and soft matter physics, 76(4 Pt.2):046115-1-046115-7-0 (2007)

17. Lin, Q., Wang, X., Hu, B., Ma, L., Chen, F., Li, J.: Multiobjective personalized recommendation algorithm using extreme point guided evolutionary computation. Complexity (2018)

18. Beume, N., Naujoks, B., Emmerich, M.: SMS-emoa: multiobjective selection based on dominated hypervolume. European Journal of Operational Research, 181(3), 1653-1669 (2007)

19. Sun, Y., Bian, K., Liu, Z., Sun, X., Yao, R.: Adaptive Strategies Based on Differential Evolutionary Algorithm for Many-Objective Optimization. Discrete Dynamics in Nature and Society (2021)