# Affinity Propagation-Based Hybrid Personalized Recommender System

Authors: Iqbal Qasim; Mujtaba Awan; Sikandar Ali; Shumaila Khan; Mogeeb A. A. Mosleh; Ahmed Alsanad; Hizbullah Khattak; Mahmood Alam
Journal: Complexity
 (2022)

---

## Abstract

A personalized recommender system is broadly accepted as a helpful tool to handle the information overload issue while recommending a related piece of information. This work proposes a hybrid personalized recommender system based on affinity propagation (AP), namely, APHPRS. Affinity propagation is a semisupervised machine learning algorithm used to cluster items based on similarities among them. In our approach, we first calculate the cluster quality and density and then combine their outputs to generate a new ranking score among clusters for the personalized recommendation. In the first phase, user preferences are collected and normalized as items rating matrix. This generated matrix is then clustered offline using affinity propagation and kept in a database for future recommendations. In the second phase, online recommendations are generated by applying the offline model. Negative Euclidian similarity and the quality of clusters are used together to select the best clusters for recommendations. The proposed APHPRS system alleviates problems such as sparsity and cold-start problems. The use of affinity propagation and the hybrid recommendation technique used in the proposed approach helps in improving results against sparsity. Experiments reveal that the proposed APHPRS performs better than most of the existing recommender systems.


---

## Body

## 1. Introduction

Recommender systems (RSs) play a vital role in the adaptive web utilizing sophisticated algorithms to reduce the ever-growing information load. Ricci et al. [1] have defined recommender systems, software tools, and techniques, which provide choices to the user for a product selection. During the past decade, the recommender system has been used in several research domains, for example, information retrieval, cognitive science, e-commerce applications, knowledge management systems, and approximation theory [2, 3]. With the popularity of social media, such product recommender systems are getting intelligent, as they often incorporate user’s comments about a particular product as input and update their underlying algorithms accordingly. However, due to the speedy growth of Internet technologies, web data is growing enormously; therefore, fetching relevant data from heterogeneous resources has become a difficult task [4]. Recommender system is an effective technology in helping users to tackle this problem by automatically recommending the related information based on their personalized preferences, which are usually stored in a user profile.Personalized recommendations are commonly presented as the items being rated. While carrying out this rating, the RS attempts to predict the most appropriate items on the basis of the user’s preferences along with other recommendation parameters that vary from portal to portal. To predict an appropriate list of choices, RSs fetch user rating information and translate that to the user-item matrix.The job of a current day recommender system is to predict item ratings and then make a recommendation close enough to the user preference. The ever-first system of recommendation named Tapestry [5] was developed in the mid 1990s. The most common research papers are focused on movie recommendation studies [6]. However, a great volume of the literature about the RS can be found to recommend music [7–9], best television show [9], best book to read [10], related document fetching in e-learning [11], knowledge system management [12], e-commerce [13], applications in markets [14], and web search [15].RSs can be divided into three main categories, including collaborative filtering (CF) and content-based and hybrid methods [16]. Content-based filtering (CB) recommendations are based on the past decisions of users. The content-based filtering is efficient in finding text and items related to a certain interest by using techniques such as Boolean queries, though it has some limitations too. The content-based techniques often have the problem of lack of diversity in items recommendation [17]. In literature, content-based approaches are widely used in information retrieval [3] and information filtering [18] research. Some approaches used in content-based systems are News Weeder [19], Info Finder [20], and News Dude [21].Collaborative filtering (CF) gathers ratings of users as opinions about certain items. The recommendation depends on the opinion of the user similarities and dissimilarities to the active user (neighbor) [22]. They aim that the collected information can be very effective for new recommendations. The collaborative filtering techniques are found to be much effective; however, it has some limitations too. One of its limitations is that the user rating analysis may be minimum; thus, the quality to recommend something would be poor. Also, collaborative filtering has common issues of sparsity, cold-start problem, and new user problem [23, 24]. Collaborative filtering algorithms are further categorized into model-based and memory-based algorithms [25]. Memory-based techniques like user-based KNN [26] use the whole user-item rating to locate k nearest neighbors for the active user and then use the ratings of these neighbors to generate recommendations. However, memory-based collaborative filtering (CF) algorithms are not scalable as the size of users grows. In contrast, model-based techniques like clustering [27] and Bayesian model [28] build a model first from the rating matrix and then use it for generating recommendations. The downside of the model-based algorithm is that the model must be rebuilt after adding a new to the rating matrix. To combine the strengths of the two stated approaches, a hybrid of model-based and memory-based techniques like Region KNN [25] and clustering-based KNN [28] can be used.Hybrid recommender systems are the systems that combine the features of two or more recommendation techniques; for example, content-based and collaborative filtering [29] are combined for the aim of using the powers of these techniques and overcoming the weaknesses of any individual technique [30, 31]. The hybrid recommender system can be much efficient for increasing prediction accuracy.In this paper, a hybrid approach has been proposed that combines collaborative filtering and content-based filtering for improving prediction accuracy and valid recommendations. Moreover, our proposed system uses both the model-based and memory-based features of collaborative filtering for clustering the user similarity and user-item rating matrix, respectively. The algorithm we have proposed for our system is a clustering algorithm named affinity propagation [32]. Affinity propagation algorithm produces clusters in a more efficient and accurate manner and hence provides better recommendations as compared to the baseline clustering algorithms. The main contributions of this work are as follows:(i)
The use of affinity propagation algorithm that is effective in case of sparse datasets.(ii)
A hybrid recommendation technique to improve the prediction and recommendation accuracy.(iii)
While utilizing the features of CF techniques, unlike classical CF recommenders, we combine the density of a cluster with the similarity measure to select a range of clusters for the generation of recommendations. This way of picking clusters gives the active user a decent set of auxiliary recommendations.The remainder of this paper is organized as follows. In Section2, some of the related works are presented. Section 3 briefly describes the affinity propagation technique. Section 4 is reserved for the proposed system. In Section 5, we have explained the experimental setup and findings of our proposed APHPRS. Finally, in Section 6, the paper is concluded.


## 2. Related Work

Recommender systems focus on presenting the most relevant information to the users. In literature, different recommender systems are available that are developed for various application domains. These recommender systems are based on different filtering techniques and utilize various recommendation methods. Bilal and Hamad in [33] proposed a recommendation system for mobile application development. The system was designed to help the mobile application developers by recommending attractive designs and artifacts. They use the collaborative filtering technique by proposing a unique measurement that takes into account both similarity and trust information to demonstrate prediction accuracy. In another work, an ontology-based recommender system was proposed for advertisement on social sites [34]. They applied shared ontology for representing advertisement as well as the interest of users. The use of ontology in recommender systems is one of the new trends in recommender system research. A system for improving the recommendation accuracy of any recommender system was proposed in [35]. They had presented an approach named Dual Training Error based Correction (DTEC) for the improvement of recommendation performance.Clustering is one of the techniques that can be utilized for accurate prediction in a recommender system. Clustering can be defined as the group of a certain set of objects based on their characteristics, aggregated according to their similarities. Clustering algorithms have been shown to surpass similarity metrics in terms of locating users that are similar to the target user. Clustering techniques also contribute to the resolving of data sparsity and high dimensionality issues [36]. Pham et al. [37] used the hierarchical clustering algorithm [38] for clustering users based on the social information of users and then used traditional collaborative filtering for rating predictions. A movie recommender system using the performance comparison of seven different clustering algorithms was proposed in [39]. They had optimized the k value of different clustering techniques for the movie recommender system. Moreover, they had applied social network analysis for verification of the recommendation quality of their proposed system. Shindi [40] proposed the centering-bunching based clustering (CBBC) algorithm for recommender systems, that is, “hybrid personalized recommender system using centering-bunching based clustering algorithm (CBBCHPRS).” CBBC algorithm is used to cluster the rating matrix. This algorithm is better than traditional k-mean and k-medoid in which centroids are initially calculated appropriately, resulting in the suitable formation of clusters; however, the technique still needs the number of clusters to be prespecified as input. Similarity measures are then used to choose the most suitable cluster/s for the generation of rating predictions. Bedi et al. [41] used an ant colony-based clustering algorithm to cluster the user-item rating matrix, and then the most similar cluster/s to the active user is/are selected for the generation of recommendations. Shindi [31] proposed a fast k-medoid algorithm to cluster the rating matrix and select the cluster that is most related to the active user for the generation of rating predictions. In this work, we propose a machine learning algorithm known as affinity propagation [32] for our proposed hybrid (of model-based and memory-based) personalized recommender system, which can automatically find the appropriate clusters in a given data set without the need for clusters number to be prespecified. The details about affinity propagation are presented in section 3.


## 3. Affinity Propagation

Affinity propagation is a novel semisupervised machine learning algorithm that is used for clustering and is referred to as “clustering by passing messages between data points” [32]. It has been observed that affinity propagation can locate relevant information clusters with much fewer errors and in a short time compared with the other available techniques. The central point of a cluster, which is itself a data point, is called an exemplary. A common approach for clustering is learning a group of exemplars so that the total squared differences among data points with their closest exemplars can be minimized. Affinity propagation considers every data point to be equally probable for being selected as an exemplar and take it as a node in the network of message passing system. This approach takes as input similarities between data points. Based on the input similarities, the transfer of messages between data points took place, and eventually, an adequate number of clusters with their corresponding exemplars are generated. In contrast to other techniques, affinity propagation automatically generates the number of clusters and never requires the number of clusters to be specified in advance. The similarity between two points s(i, k) indicates how similar two points are to each other by calculating a negative Euclidean distance between them:(1)si,k=−∥Ui−Uk∥2,where i ≠ k.Affinity propagation takes a numbered values(k, k) as a similarity between each data point k, and the points that have a higher value of s(k, k) are more chances to become an exemplar. This numbered value is known as “preferences.” The number of clusters emerges according to the input preferences but also arises during the message-exchange process. Since affinity propagation assumes every data point as an exemplar initially, the preferences are kept as a common value. This preference may be set to the minimum of all input similarities that will produce clusters less in number, or it can be set to the median of all input similarities that will produce a moderate number of clusters.Moreover, the messages that are to be sent between the data points are categorized into two types: responsibility and availability [32]. The responsibility messages (i, k) are those messages that are sent from data point i to the data point k representing how well it is appropriate for data point k to be the exemplar for data point i in consideration of other probable exemplars for a point I (Figure 1(a)), while the availability messages a(i, k) are the messages that are sent from data point k to the data point i representing how well it is suitable for point i to pick point k as it is exemplary considering the support from other points that point k should be an exemplar (Figure 1(b)). At any point in time, the two messages can be consolidated for determining the exemplars. Affinity adds a value λ ∈ [0, 1] called damping factor in message passing to periodic variations of in certain circumstances. The process of message passing between data points is ended when the exemplar decision does not change for a certain number of iterations, usually 10.Figure 1
Message-exchange process of affinity propagation [32].
(a)(b)Figure2 shows the message-exchange process of affinity propagation. (A) Sending responsibilities r(i, k) are the messages sent from data points to candidate exemplars to specify the favoring value of each data point for candidate exemplar compared to other exemplars. (B) Sending availabilities a(i, k) are those messages that are sent from candidate exemplars to data points indicating the degree by which candidate exemplar can be selected as a cluster center for the data point.Figure 2
Affinity Propagation-Based Hybrid Personalized Recommender System.In the initial iteration of affinity propagation, the availabilities are initialized as zero, that is,a(i, k) = 0. The responsibilities in this step are then calculated by the rule (equation (2)). In succeeding iterations, while few data points are efficiently associated with other exemplars, their availabilities decrease lower than zero as approved using the availability update rule (equation (3)). The found negative availabilities brought much decrease in the similarity value provided as input s(i, k′) in responsibility update rule and detached the already supportive candidate exemplars. When the value is k = i, the value for responsibility r(k, k) is initialized as input preference that point k is selected as an exemplar, s(k, k), minus the largest of the similarities between point i and all other candidate exemplars. The found “self-responsibility” proves point k as an exemplar and is based on the input preference mitigated by how poorly it is to be allocated to a different exemplar [32].(2)ri,k=si,k−ai,k′+si,k′,where r(i, k) represents the update rule for responsibility, s(i, k) represents the input similarity of data point i to its exemplar k, and maxk′s.t.k′≠kai,k′+si,k′ is the maximum similarity of point i with other exemplars.(3)ai,k=0,rk,k+.The above rule of availability is used to collect information of data points as if the candidate exemplar might be helpful in making a good exemplar. The availabilitya(i, k) is set to the self-responsibility r(k, k) plus the sum of the positive responsibilities candidate exemplar k receives from other points. The proposed affinity propagation algorithm has a drawback of high computational cost. Its computational complexity is of the order O (n2t), where “n” represents the total number of the data points and “t” is the number of all iterations until final clusters are made. Moreover, the proposed algorithm may fail to produce effective results when the similarity matrix is not generated well.


## 4. The Proposed Affinity Propagation-Based Hybrid Personalized Recommender System

The proposed Affinity Propagation-Based Hybrid Personalized Recommender System (APHPRS) combines the features of content-based methods and collaborative filtering methods for handling the issues like sparsity and cold-start problems. The proposed method works in two phases (Figure2). In the offline phase, it performs the preprocessing on data. In this phase, a rating matrix is generated and normalized, and then a pairwise similarity matrix for users is generated of the normalized matrix of user-item ratings. The similarity matrix is then loaded into an affinity propagation algorithm for clustering. Once the clusters are formed, they are kept in some database file so that the clusters can be used for generating recommendations in future.The second phase (phase 2) is about generating recommendations for the active user. In this phase, the similarity metric and the number of user preferences are combined in a specific cluster for finding suitable clusters for the generation of recommendations. Moreover, the quality of item ratings in each cluster is also recorded. Based on this measure, suitable clusters get selected out of the list of chosen clusters for the rating predictions. After this step, the recommendations are generated using the weighted average of item ratings in the chosen clusters. Unlike classical collaborative recommenders, we combine the density of a cluster with the similarity measure to select a range of clusters for the generation of recommendations. This way of picking clusters gives the active user a decent set of auxiliary recommendations. The results are then further refined by choosing cluster/s having maximum quality ratings. The detailed procedure and working of the proposed APHPRS are described in the following by taking the example of the Jester dataset.Figure2 represents the proposed APHPRS system. (1) The preprocessing step: user-item rating matric is taken from the Jester dataset and normalized. After normalization, a pairwise similarity matrix between users is calculated. (2) The clustering step: it is the step where the found similarity matrix is provided to the AP algorithm for grouping those users who have similar ratings. (3) The recommendation step: in this step, the recommendations take place for active users. Here, the similarity between active users and clusters is computed to find the best clusters for generating recommendations. The rating quality of each item not rated by an active user is calculated in the selected clusters. To generate the recommendations, clusters are further selected based on the rating quality of an item. Note that step 1 and step 2 are the parts of the offline phase, while step 3 is the online phase of our proposed system.


### 4.1. Offline Phase

The proposed APHPRS starts with an offline phase that consists of two different steps: preprocessing and clustering. The steps in this phase are done in offline mode for faster execution of recommendations and to reduce running time. As the proposed algorithm has a little high computational cost (i.e.,O (n2t)), the calculation in the offline phase prevents the system from slow recommendations. In this step, the data in the form of user-item ratings is collected and clustered using the proposed algorithm. Moreover, a similarity matrix is also obtained for the user ratings, which is then used as an input for the proposed affinity propagation algorithm. Here, in this phase, we do not need to have online processing as all of its steps are done without connection with an active user.


#### 4.1.1. Preprocessing

In this step, we took Jester dataset as input and normalized it for future processing of our system. We then compute the similarity between different entries available in the Jester dataset and fetch the similarity to the next step. The details of preprocessing are presented in the succeeding steps:(1) Jester Dataset. The Jester dataset is an online dataset for the Web-based Joke Recommender System. In the Jester dataset, each row represents a different user, while each column (except the first column) shows the rated score given by a particular user. The first column gives a specific number of jokes rated by a particular user. The remaining columns give the ratings for different jokes. The user-item rating matrix collected from Jester data consisted of item ratings on a scale of −10 to 10, and in any cell, the value 99 represents null or no rating of the item (joke). Table 1 shows a sample of the Jester dataset that we have taken only 10 entries to keep the table readable to the reader.Table 1
A sample taken from Jester dataset before normalization.
Number of jokes ratedJ1J2J3J4J5J6J7J8J9J1074−7.828.79−9.66−8.16−7.52−8.5−9.854.17−8.98−4.761004.08−0.296.364.37−2.38−9.66−0.73−5.348.889.2249999999999.039.279.039.27999948998.3599991.88.16−2.826.21991.84918.54.61−4.17−5.391.361.67.044.61−0.445.73100−6.17−3.540.44−8.5−7.09−4.32−8.69−0.87−6.65−1.847999999998.59−9.857.728.7999991006.843.169.17−6.21−8.16−1.79.271.41−5.19−4.42100−3.79−3.54−9.42−6.89−8.74−0.29−5.29−8.93−7.86−1.6723.015.155.153.016.415.158.932.523.018.16(2) Normalization. In this step, we have taken the Jester dataset (Table 1) as input and removed the first column. Table 1 represents a sample of the Jester dataset, where the first column shows the number of jokes rated by a particular user while the rest of the columns show the rated values of each joke. Note that we have picked only 10 jokes in the below table. We then normalized the ratings to the scale from 0 to 1, where 0 represents null or no rating for a particular joke (Table 2). It is noteworthy that we have kept the positive and null ratings only as the recommendations will be made on the basis of these two factors. Unlike Jester dataset, we have removed the negative ratings in the normalized rating matrix. The normalized values are calculated using (4)ni=xi−minxmaxx−minx,where ni is the value being normalized, xi is the value before normalization, min(x) is the lowest value, and max(x) is the highest-rated value. The calculated values for each rating are given in Table 2. Table 2 represents the normalized form of Jester data, where the first column has been removed, and the ratings are converted on a scale between 0 and 1. Note that the negative ratings have been skipped, as the recommendation will be made on positive ratings.Table 2
A sample of normalized rating matrix in the scale of 0 to 1 taken from Jester dataset.
UsersJ1J2J3J4J5J6J7J8J9J10U10.1090.93950.0170.0920.1240.0750.00750.70850.0510.262U20.7040.48550.8180.71850.3810.0170.46350.2330.9440.961U300000.95150.96350.95150.963500U400.9175000.590.9080.3590.810500.592U50.9250.73050.29150.23050.5680.580.8520.73050.4780.7865U60.19150.3230.5220.0750.14550.2840.06550.45650.16750.41U700000.92950.00750.8860.939500U80.8420.6580.95850.18950.0920.4150.96350.57050.24050.279U90.31050.3230.0290.15550.0630.48550.23550.05350.1070.42U100.65050.75750.75750.65050.82050.75750.94650.6260.65050.908Active user0.8640.7695000.28900.94650.67500.8060 indicates item being not rated(3) Similarity Matrix. Affinity propagation needs a pairwise matrix of similarity values to be fed as input. We have obtained the similarity among users according to their rating for items (Table 3). We have used the negative square error or Euclidean distance for calculating the similarity. The similarity matrix can be found using (5)si,k=−Ui−Uk2,where i and k can be any two users and i ≠ k.Table 3
A sample similarity matrix.
UiUks(i, k)12−3.383743513−3.404888814−1.177620321−3.383743523−5.724456324−4.076891831−3.404888832−5.724456334−1.70049841−1.177620342−4.076891843−1.700498The similarity matrix constructed for the normalized rating matrix has 10 users; hence, the similarity matrix will haven(n − 1) = 10(9) entries that will lead us to create a table having 90 entries. For the sake of brevity, a short version of that matrix is reproduced here (Table 3). Here, columns 1 and 2 represent indices of the two users, while the column represents the negative Euclidean distance between the corresponding pair of users.


#### 4.1.2. Clustering

We used affinity propagation as a clustering algorithm for grouping items based on their similarity. The default damping factor ofλ is initialized as 0.5; see details about the damping factor in Section 2. The used clustering algorithms have generated three clusters of the given similarity matrix.We have chosen affinity propagation as in this clustering algorithm, and we do not need the number of clusters to be prespecified. Moreover, the proposed algorithm is effective in the case of sparse data, and it takes advantages of data sparsity when similarities are well-conducted [42]. The details of the found clusters are shown in Table 4.Table 4
Users in each cluster with exemplar.
ClusterUserExemplar13, 7321, 4, 6, 9632, 5, 8, 1010Table4 represents the clusters found using affinity propagation. The first column shows three different clusters, while the second column shows the number of users in each cluster. In the third column, the central point (exemplar) of each cluster is recorded.


### 4.2. Online Phase

In this phase, predictions and recommendations are made for the active user. The steps of this phase are done online, as the active user is considered while processing each step. A detailed description of the online phase is given in the next sections.


#### 4.2.1. Selecting the Best Cluster(s)

Selecting the best cluster(s) for the generation of recommendations is dependent on two aspects: (1) the number of users in a cluster and (2) the similarity of that cluster with the active user. The match score of a certain cluster is obtained by(6)Matchscorei=ρi⋅smi∑i=1nρi⋅smi,where sm(i) is the similarity between the exemplar of ith cluster and the active user, ρ(i) is the density of the ith cluster, and n represents the complete set of clusters formed.A similarity measure is used to find the cluster of users having preferences that match the most with the profile of the active user. There are numeral different measures used for calculating similarities like Pearson correlation, Euclidean distance measure, and vector similarity measure. We have used Euclidean distance measure to find the similarity between the profile of an active user and cluster. The Euclidean distance can be calculated using equation (7):(7)Di=∑j=1dexpi.j−uj21/2,where d is the total number of items or attributes of a user, expi,jith attribute of the exemplar of cluster j, and uj is the jth user.Hence, the similarity of theith cluster with the active user is calculated as follows:(8)smi=1Di.The density of the cluster can be calculated using the following equation:(9)ρi=population of  users in clusteritotal population of users.The density of a cluster increases with the increase of users in a cluster and vice versa. Those clusters whose match score lies within the range (highest score −α ≤ match_score ≤ highest score) are selected for recommendations generation. In this paper, α = 0.2. By using this range, unlike collaborative filtering, not only the clusters having the highest score but also the other clusters having their scores slightly less than the maximum one are selected. The match score, density ρ, and similarity values calculated are shown in Table 5. Table 5 represents the calculated similarity sm(j) with an active user, the density ρ(i) of each cluster, and the matching score between clusters, where the first column shows the functions for different clusters, while the rest of the column shows the corresponding function measure values for each cluster.Table 5
Cluster selecting procedure.
FunctionCluster 1Cluster 2Cluster 3sm(i)0.53930.70020.6544ρ(i)0.20.40.4Match score(i)0.1660.43110.4029The clusters selected are 2 and 3 because their match score lies within the range 0.4311−0.2 ≤ match score ≤ 0.4311.


#### 4.2.2. Calculation of Rating Quality

Rating quality any item explains how similar the ratings of different users are in any specific cluster. The rating quality can be found using(10)Qty=ubrating+meanrating2∗ubrating,where ubrating is the maximum rate score of an item and meanrating represents the mean value of item ratings in any cluster. If ubrating and mean rating values are equal, we get quality rating Qty as 1 that represents good quality. Hence, a greater value of Qty will lead to higher rating quality and vice versa. The calculated rating quality of different unrated jokes is shown in Table 6. Table 6 shows the rating quality of unrated jokes in different clusters, where the first column represents the active user unrated jokes, while the second and third columns show the corresponding quality ratings, that is, clusters 2 and 3, respectively.Table 6
Rating quality of unrated jokes in selected clusters.
Unrated jokes by an active userQuality rating in cluster 2Quality rating in cluster 3J30.6360.8685J40.75920.8112J60.74130.792J90.74290.8063


#### 4.2.3. Prediction of New Item Ratings

After finding the quality of each unrated item on the basis of rating quality, the clusters are then selected from the initially chosen clusters (Table7). Instead of selecting the cluster with the quality for an unrated item, those clusters where the quality “Qty” of each unrated item is in the range [17] are additionally retrieved from the cluster set that was initially chosen for the generation of rating predictions. In this paper, α = 0.1. Table 7 shows the ratings predicted for unrated jokes. If only one cluster is selected, then the mean rating of the item in the selected cluster is calculated; otherwise, the rating is calculated as the weighted average. For jokes 4, 6, and 9, the rating is calculated as a weighted average of ratings in clusters 2 and 3, while for joke 3, the average rating is calculated from cluster 3.Table 7
Ratings predicted for the active user.
JokesClusters selectedPredicted ratingsJ330.7064J42, 30.27J62, 30.4403J92,30.34Item’s rating is then predicted using(11)Rating=∑i=1kQtyi∗meanrating∑i=1kqtyi,where Qtyi represents the item’s quality in the chosen cluster, meanrating is the rating of the item in any selected cluster, and k represents the number of clusters being selected.


#### 4.2.4. Generation of Top-N Recommendations

Once the item ratings are predicted, the next step is to provide the active user with top-N suggestions. For example, ifN = 1, joke 3 will be suggested. For N = 2, jokes 3 and 6 will be suggested, and so on.


## 4.1. Offline Phase

The proposed APHPRS starts with an offline phase that consists of two different steps: preprocessing and clustering. The steps in this phase are done in offline mode for faster execution of recommendations and to reduce running time. As the proposed algorithm has a little high computational cost (i.e.,O (n2t)), the calculation in the offline phase prevents the system from slow recommendations. In this step, the data in the form of user-item ratings is collected and clustered using the proposed algorithm. Moreover, a similarity matrix is also obtained for the user ratings, which is then used as an input for the proposed affinity propagation algorithm. Here, in this phase, we do not need to have online processing as all of its steps are done without connection with an active user.


### 4.1.1. Preprocessing

In this step, we took Jester dataset as input and normalized it for future processing of our system. We then compute the similarity between different entries available in the Jester dataset and fetch the similarity to the next step. The details of preprocessing are presented in the succeeding steps:(1) Jester Dataset. The Jester dataset is an online dataset for the Web-based Joke Recommender System. In the Jester dataset, each row represents a different user, while each column (except the first column) shows the rated score given by a particular user. The first column gives a specific number of jokes rated by a particular user. The remaining columns give the ratings for different jokes. The user-item rating matrix collected from Jester data consisted of item ratings on a scale of −10 to 10, and in any cell, the value 99 represents null or no rating of the item (joke). Table 1 shows a sample of the Jester dataset that we have taken only 10 entries to keep the table readable to the reader.Table 1
A sample taken from Jester dataset before normalization.
Number of jokes ratedJ1J2J3J4J5J6J7J8J9J1074−7.828.79−9.66−8.16−7.52−8.5−9.854.17−8.98−4.761004.08−0.296.364.37−2.38−9.66−0.73−5.348.889.2249999999999.039.279.039.27999948998.3599991.88.16−2.826.21991.84918.54.61−4.17−5.391.361.67.044.61−0.445.73100−6.17−3.540.44−8.5−7.09−4.32−8.69−0.87−6.65−1.847999999998.59−9.857.728.7999991006.843.169.17−6.21−8.16−1.79.271.41−5.19−4.42100−3.79−3.54−9.42−6.89−8.74−0.29−5.29−8.93−7.86−1.6723.015.155.153.016.415.158.932.523.018.16(2) Normalization. In this step, we have taken the Jester dataset (Table 1) as input and removed the first column. Table 1 represents a sample of the Jester dataset, where the first column shows the number of jokes rated by a particular user while the rest of the columns show the rated values of each joke. Note that we have picked only 10 jokes in the below table. We then normalized the ratings to the scale from 0 to 1, where 0 represents null or no rating for a particular joke (Table 2). It is noteworthy that we have kept the positive and null ratings only as the recommendations will be made on the basis of these two factors. Unlike Jester dataset, we have removed the negative ratings in the normalized rating matrix. The normalized values are calculated using (4)ni=xi−minxmaxx−minx,where ni is the value being normalized, xi is the value before normalization, min(x) is the lowest value, and max(x) is the highest-rated value. The calculated values for each rating are given in Table 2. Table 2 represents the normalized form of Jester data, where the first column has been removed, and the ratings are converted on a scale between 0 and 1. Note that the negative ratings have been skipped, as the recommendation will be made on positive ratings.Table 2
A sample of normalized rating matrix in the scale of 0 to 1 taken from Jester dataset.
UsersJ1J2J3J4J5J6J7J8J9J10U10.1090.93950.0170.0920.1240.0750.00750.70850.0510.262U20.7040.48550.8180.71850.3810.0170.46350.2330.9440.961U300000.95150.96350.95150.963500U400.9175000.590.9080.3590.810500.592U50.9250.73050.29150.23050.5680.580.8520.73050.4780.7865U60.19150.3230.5220.0750.14550.2840.06550.45650.16750.41U700000.92950.00750.8860.939500U80.8420.6580.95850.18950.0920.4150.96350.57050.24050.279U90.31050.3230.0290.15550.0630.48550.23550.05350.1070.42U100.65050.75750.75750.65050.82050.75750.94650.6260.65050.908Active user0.8640.7695000.28900.94650.67500.8060 indicates item being not rated(3) Similarity Matrix. Affinity propagation needs a pairwise matrix of similarity values to be fed as input. We have obtained the similarity among users according to their rating for items (Table 3). We have used the negative square error or Euclidean distance for calculating the similarity. The similarity matrix can be found using (5)si,k=−Ui−Uk2,where i and k can be any two users and i ≠ k.Table 3
A sample similarity matrix.
UiUks(i, k)12−3.383743513−3.404888814−1.177620321−3.383743523−5.724456324−4.076891831−3.404888832−5.724456334−1.70049841−1.177620342−4.076891843−1.700498The similarity matrix constructed for the normalized rating matrix has 10 users; hence, the similarity matrix will haven(n − 1) = 10(9) entries that will lead us to create a table having 90 entries. For the sake of brevity, a short version of that matrix is reproduced here (Table 3). Here, columns 1 and 2 represent indices of the two users, while the column represents the negative Euclidean distance between the corresponding pair of users.


### 4.1.2. Clustering

We used affinity propagation as a clustering algorithm for grouping items based on their similarity. The default damping factor ofλ is initialized as 0.5; see details about the damping factor in Section 2. The used clustering algorithms have generated three clusters of the given similarity matrix.We have chosen affinity propagation as in this clustering algorithm, and we do not need the number of clusters to be prespecified. Moreover, the proposed algorithm is effective in the case of sparse data, and it takes advantages of data sparsity when similarities are well-conducted [42]. The details of the found clusters are shown in Table 4.Table 4
Users in each cluster with exemplar.
ClusterUserExemplar13, 7321, 4, 6, 9632, 5, 8, 1010Table4 represents the clusters found using affinity propagation. The first column shows three different clusters, while the second column shows the number of users in each cluster. In the third column, the central point (exemplar) of each cluster is recorded.


## 4.1.1. Preprocessing

In this step, we took Jester dataset as input and normalized it for future processing of our system. We then compute the similarity between different entries available in the Jester dataset and fetch the similarity to the next step. The details of preprocessing are presented in the succeeding steps:(1) Jester Dataset. The Jester dataset is an online dataset for the Web-based Joke Recommender System. In the Jester dataset, each row represents a different user, while each column (except the first column) shows the rated score given by a particular user. The first column gives a specific number of jokes rated by a particular user. The remaining columns give the ratings for different jokes. The user-item rating matrix collected from Jester data consisted of item ratings on a scale of −10 to 10, and in any cell, the value 99 represents null or no rating of the item (joke). Table 1 shows a sample of the Jester dataset that we have taken only 10 entries to keep the table readable to the reader.Table 1
A sample taken from Jester dataset before normalization.
Number of jokes ratedJ1J2J3J4J5J6J7J8J9J1074−7.828.79−9.66−8.16−7.52−8.5−9.854.17−8.98−4.761004.08−0.296.364.37−2.38−9.66−0.73−5.348.889.2249999999999.039.279.039.27999948998.3599991.88.16−2.826.21991.84918.54.61−4.17−5.391.361.67.044.61−0.445.73100−6.17−3.540.44−8.5−7.09−4.32−8.69−0.87−6.65−1.847999999998.59−9.857.728.7999991006.843.169.17−6.21−8.16−1.79.271.41−5.19−4.42100−3.79−3.54−9.42−6.89−8.74−0.29−5.29−8.93−7.86−1.6723.015.155.153.016.415.158.932.523.018.16(2) Normalization. In this step, we have taken the Jester dataset (Table 1) as input and removed the first column. Table 1 represents a sample of the Jester dataset, where the first column shows the number of jokes rated by a particular user while the rest of the columns show the rated values of each joke. Note that we have picked only 10 jokes in the below table. We then normalized the ratings to the scale from 0 to 1, where 0 represents null or no rating for a particular joke (Table 2). It is noteworthy that we have kept the positive and null ratings only as the recommendations will be made on the basis of these two factors. Unlike Jester dataset, we have removed the negative ratings in the normalized rating matrix. The normalized values are calculated using (4)ni=xi−minxmaxx−minx,where ni is the value being normalized, xi is the value before normalization, min(x) is the lowest value, and max(x) is the highest-rated value. The calculated values for each rating are given in Table 2. Table 2 represents the normalized form of Jester data, where the first column has been removed, and the ratings are converted on a scale between 0 and 1. Note that the negative ratings have been skipped, as the recommendation will be made on positive ratings.Table 2
A sample of normalized rating matrix in the scale of 0 to 1 taken from Jester dataset.
UsersJ1J2J3J4J5J6J7J8J9J10U10.1090.93950.0170.0920.1240.0750.00750.70850.0510.262U20.7040.48550.8180.71850.3810.0170.46350.2330.9440.961U300000.95150.96350.95150.963500U400.9175000.590.9080.3590.810500.592U50.9250.73050.29150.23050.5680.580.8520.73050.4780.7865U60.19150.3230.5220.0750.14550.2840.06550.45650.16750.41U700000.92950.00750.8860.939500U80.8420.6580.95850.18950.0920.4150.96350.57050.24050.279U90.31050.3230.0290.15550.0630.48550.23550.05350.1070.42U100.65050.75750.75750.65050.82050.75750.94650.6260.65050.908Active user0.8640.7695000.28900.94650.67500.8060 indicates item being not rated(3) Similarity Matrix. Affinity propagation needs a pairwise matrix of similarity values to be fed as input. We have obtained the similarity among users according to their rating for items (Table 3). We have used the negative square error or Euclidean distance for calculating the similarity. The similarity matrix can be found using (5)si,k=−Ui−Uk2,where i and k can be any two users and i ≠ k.Table 3
A sample similarity matrix.
UiUks(i, k)12−3.383743513−3.404888814−1.177620321−3.383743523−5.724456324−4.076891831−3.404888832−5.724456334−1.70049841−1.177620342−4.076891843−1.700498The similarity matrix constructed for the normalized rating matrix has 10 users; hence, the similarity matrix will haven(n − 1) = 10(9) entries that will lead us to create a table having 90 entries. For the sake of brevity, a short version of that matrix is reproduced here (Table 3). Here, columns 1 and 2 represent indices of the two users, while the column represents the negative Euclidean distance between the corresponding pair of users.


## 4.1.2. Clustering

We used affinity propagation as a clustering algorithm for grouping items based on their similarity. The default damping factor ofλ is initialized as 0.5; see details about the damping factor in Section 2. The used clustering algorithms have generated three clusters of the given similarity matrix.We have chosen affinity propagation as in this clustering algorithm, and we do not need the number of clusters to be prespecified. Moreover, the proposed algorithm is effective in the case of sparse data, and it takes advantages of data sparsity when similarities are well-conducted [42]. The details of the found clusters are shown in Table 4.Table 4
Users in each cluster with exemplar.
ClusterUserExemplar13, 7321, 4, 6, 9632, 5, 8, 1010Table4 represents the clusters found using affinity propagation. The first column shows three different clusters, while the second column shows the number of users in each cluster. In the third column, the central point (exemplar) of each cluster is recorded.


## 4.2. Online Phase

In this phase, predictions and recommendations are made for the active user. The steps of this phase are done online, as the active user is considered while processing each step. A detailed description of the online phase is given in the next sections.


### 4.2.1. Selecting the Best Cluster(s)

Selecting the best cluster(s) for the generation of recommendations is dependent on two aspects: (1) the number of users in a cluster and (2) the similarity of that cluster with the active user. The match score of a certain cluster is obtained by(6)Matchscorei=ρi⋅smi∑i=1nρi⋅smi,where sm(i) is the similarity between the exemplar of ith cluster and the active user, ρ(i) is the density of the ith cluster, and n represents the complete set of clusters formed.A similarity measure is used to find the cluster of users having preferences that match the most with the profile of the active user. There are numeral different measures used for calculating similarities like Pearson correlation, Euclidean distance measure, and vector similarity measure. We have used Euclidean distance measure to find the similarity between the profile of an active user and cluster. The Euclidean distance can be calculated using equation (7):(7)Di=∑j=1dexpi.j−uj21/2,where d is the total number of items or attributes of a user, expi,jith attribute of the exemplar of cluster j, and uj is the jth user.Hence, the similarity of theith cluster with the active user is calculated as follows:(8)smi=1Di.The density of the cluster can be calculated using the following equation:(9)ρi=population of  users in clusteritotal population of users.The density of a cluster increases with the increase of users in a cluster and vice versa. Those clusters whose match score lies within the range (highest score −α ≤ match_score ≤ highest score) are selected for recommendations generation. In this paper, α = 0.2. By using this range, unlike collaborative filtering, not only the clusters having the highest score but also the other clusters having their scores slightly less than the maximum one are selected. The match score, density ρ, and similarity values calculated are shown in Table 5. Table 5 represents the calculated similarity sm(j) with an active user, the density ρ(i) of each cluster, and the matching score between clusters, where the first column shows the functions for different clusters, while the rest of the column shows the corresponding function measure values for each cluster.Table 5
Cluster selecting procedure.
FunctionCluster 1Cluster 2Cluster 3sm(i)0.53930.70020.6544ρ(i)0.20.40.4Match score(i)0.1660.43110.4029The clusters selected are 2 and 3 because their match score lies within the range 0.4311−0.2 ≤ match score ≤ 0.4311.


### 4.2.2. Calculation of Rating Quality

Rating quality any item explains how similar the ratings of different users are in any specific cluster. The rating quality can be found using(10)Qty=ubrating+meanrating2∗ubrating,where ubrating is the maximum rate score of an item and meanrating represents the mean value of item ratings in any cluster. If ubrating and mean rating values are equal, we get quality rating Qty as 1 that represents good quality. Hence, a greater value of Qty will lead to higher rating quality and vice versa. The calculated rating quality of different unrated jokes is shown in Table 6. Table 6 shows the rating quality of unrated jokes in different clusters, where the first column represents the active user unrated jokes, while the second and third columns show the corresponding quality ratings, that is, clusters 2 and 3, respectively.Table 6
Rating quality of unrated jokes in selected clusters.
Unrated jokes by an active userQuality rating in cluster 2Quality rating in cluster 3J30.6360.8685J40.75920.8112J60.74130.792J90.74290.8063


### 4.2.3. Prediction of New Item Ratings

After finding the quality of each unrated item on the basis of rating quality, the clusters are then selected from the initially chosen clusters (Table7). Instead of selecting the cluster with the quality for an unrated item, those clusters where the quality “Qty” of each unrated item is in the range [17] are additionally retrieved from the cluster set that was initially chosen for the generation of rating predictions. In this paper, α = 0.1. Table 7 shows the ratings predicted for unrated jokes. If only one cluster is selected, then the mean rating of the item in the selected cluster is calculated; otherwise, the rating is calculated as the weighted average. For jokes 4, 6, and 9, the rating is calculated as a weighted average of ratings in clusters 2 and 3, while for joke 3, the average rating is calculated from cluster 3.Table 7
Ratings predicted for the active user.
JokesClusters selectedPredicted ratingsJ330.7064J42, 30.27J62, 30.4403J92,30.34Item’s rating is then predicted using(11)Rating=∑i=1kQtyi∗meanrating∑i=1kqtyi,where Qtyi represents the item’s quality in the chosen cluster, meanrating is the rating of the item in any selected cluster, and k represents the number of clusters being selected.


### 4.2.4. Generation of Top-N Recommendations

Once the item ratings are predicted, the next step is to provide the active user with top-N suggestions. For example, ifN = 1, joke 3 will be suggested. For N = 2, jokes 3 and 6 will be suggested, and so on.


## 4.2.1. Selecting the Best Cluster(s)

Selecting the best cluster(s) for the generation of recommendations is dependent on two aspects: (1) the number of users in a cluster and (2) the similarity of that cluster with the active user. The match score of a certain cluster is obtained by(6)Matchscorei=ρi⋅smi∑i=1nρi⋅smi,where sm(i) is the similarity between the exemplar of ith cluster and the active user, ρ(i) is the density of the ith cluster, and n represents the complete set of clusters formed.A similarity measure is used to find the cluster of users having preferences that match the most with the profile of the active user. There are numeral different measures used for calculating similarities like Pearson correlation, Euclidean distance measure, and vector similarity measure. We have used Euclidean distance measure to find the similarity between the profile of an active user and cluster. The Euclidean distance can be calculated using equation (7):(7)Di=∑j=1dexpi.j−uj21/2,where d is the total number of items or attributes of a user, expi,jith attribute of the exemplar of cluster j, and uj is the jth user.Hence, the similarity of theith cluster with the active user is calculated as follows:(8)smi=1Di.The density of the cluster can be calculated using the following equation:(9)ρi=population of  users in clusteritotal population of users.The density of a cluster increases with the increase of users in a cluster and vice versa. Those clusters whose match score lies within the range (highest score −α ≤ match_score ≤ highest score) are selected for recommendations generation. In this paper, α = 0.2. By using this range, unlike collaborative filtering, not only the clusters having the highest score but also the other clusters having their scores slightly less than the maximum one are selected. The match score, density ρ, and similarity values calculated are shown in Table 5. Table 5 represents the calculated similarity sm(j) with an active user, the density ρ(i) of each cluster, and the matching score between clusters, where the first column shows the functions for different clusters, while the rest of the column shows the corresponding function measure values for each cluster.Table 5
Cluster selecting procedure.
FunctionCluster 1Cluster 2Cluster 3sm(i)0.53930.70020.6544ρ(i)0.20.40.4Match score(i)0.1660.43110.4029The clusters selected are 2 and 3 because their match score lies within the range 0.4311−0.2 ≤ match score ≤ 0.4311.


## 4.2.2. Calculation of Rating Quality

Rating quality any item explains how similar the ratings of different users are in any specific cluster. The rating quality can be found using(10)Qty=ubrating+meanrating2∗ubrating,where ubrating is the maximum rate score of an item and meanrating represents the mean value of item ratings in any cluster. If ubrating and mean rating values are equal, we get quality rating Qty as 1 that represents good quality. Hence, a greater value of Qty will lead to higher rating quality and vice versa. The calculated rating quality of different unrated jokes is shown in Table 6. Table 6 shows the rating quality of unrated jokes in different clusters, where the first column represents the active user unrated jokes, while the second and third columns show the corresponding quality ratings, that is, clusters 2 and 3, respectively.Table 6
Rating quality of unrated jokes in selected clusters.
Unrated jokes by an active userQuality rating in cluster 2Quality rating in cluster 3J30.6360.8685J40.75920.8112J60.74130.792J90.74290.8063


## 4.2.3. Prediction of New Item Ratings

After finding the quality of each unrated item on the basis of rating quality, the clusters are then selected from the initially chosen clusters (Table7). Instead of selecting the cluster with the quality for an unrated item, those clusters where the quality “Qty” of each unrated item is in the range [17] are additionally retrieved from the cluster set that was initially chosen for the generation of rating predictions. In this paper, α = 0.1. Table 7 shows the ratings predicted for unrated jokes. If only one cluster is selected, then the mean rating of the item in the selected cluster is calculated; otherwise, the rating is calculated as the weighted average. For jokes 4, 6, and 9, the rating is calculated as a weighted average of ratings in clusters 2 and 3, while for joke 3, the average rating is calculated from cluster 3.Table 7
Ratings predicted for the active user.
JokesClusters selectedPredicted ratingsJ330.7064J42, 30.27J62, 30.4403J92,30.34Item’s rating is then predicted using(11)Rating=∑i=1kQtyi∗meanrating∑i=1kqtyi,where Qtyi represents the item’s quality in the chosen cluster, meanrating is the rating of the item in any selected cluster, and k represents the number of clusters being selected.


## 4.2.4. Generation of Top-N Recommendations

Once the item ratings are predicted, the next step is to provide the active user with top-N suggestions. For example, ifN = 1, joke 3 will be suggested. For N = 2, jokes 3 and 6 will be suggested, and so on.


## 5. Experimental Setup

### 5.1. Clustering Performance Evaluation

The performance of the proposed clustering algorithm was evaluated using the IRIS dataset that is available in the UCI repository (https://archive.ics.uci.edu/ml/datasets/Iris). The IRIS dataset contains a total of 150 objects divided into three main classes, where each class has 50 objects. The classes are labelled as “Setosa,” “Versicolor,” and “Virginica.” The performance of clusters was evaluated in terms of the accuracy of grouping each and every object according to the true classes. In the experiments, we compared the proposed algorithm with many baseline algorithms used for clustering. The proposed affinity propagation algorithm outperforms the existing algorithm as it clusters the object more accurately (see Table 8). The accuracy has been improved due to the message sending process of the proposed algorithm. Moreover, the proposed algorithm does not need the cluster number to be prespecified, and it automatically generates the cluster centroids (exemplars).Table 8
Clustering performance on IRIS dataset by the proposed algorithm and baseline algorithms.
IRIS classesClustering algorithmsk-meansk-mediodsCBBCAffinity propagationSetosa50505050Versicolor34414447Virginica66595653Table8 shows the evaluation of the proposed clustering algorithm on the IRIS dataset. In this table, the first column represents the various classes of the IRIS dataset and the second column holds the different algorithms and their clustering results. This table clearly reveals that the affinity propagation algorithm generates the clusters with more accuracy.


### 5.2. Performance Evaluation of the Proposed Recommender System

APHPRS has been implemented in MATLAB version 7.8. The experiment was conducted on the Jester dataset. We also implemented another collaborative filtering-based recommender system [43] manually for performance comparison, using R-precision and MAE metrics. To evaluate the performance, we have used two different sizes of datasets. Dataset 1 is a small subset of Jester data that consists of a user-item rating matrix having 10 users and 10 jokes (Table 2). Dataset 2 is a large subset of the Jester dataset consisting of 70,000 users and 100 jokes. The proposed APHPRS was evaluated by checking its prediction quality and recommendation quality.Prediction quality is tested by relating the predicted user rating to the test set of actual user ratings. For the evaluation of predictive accuracy, Mean Absolute Error (MAE) is used as a universal metric [44]. Hence, we used the MAE metric for evaluating the prediction quality of the proposed APHPRS. If we represent the set of rating prediction for items as p1, p2, p3, …, pN, and represent the set of corresponding actual user ratings as q1, q2, q3, …, qN, then MAE can be computed using(12)MAE=∑i=1Npi–qiN.The low MAE value will lead to greater quality of a recommender system, that is, smaller values of MAE, indicating that rating predictions are much similar to real ratings. For the experiment on dataset 1, we have randomly selected 7 different users from the Jester dataset and gradually increased the size of the test set from 1, 2, 3, 4, 5, 6, and 7 (Figure3). We have compared our proposed APHPRS system with the existing hybrid personalized recommender system using a centering-bunching-based clustering algorithm (CBBCHPRS) [40]. The proposed algorithm and the CBBCHPRS both use the same number of users of the Jester dataset.Figure 3
MAE for the two recommender systems for dataset 1.Figure3 represents the MAE calculated for our proposed APHPRS in comparison with CBBCHPRS. The result shows that our proposed system has a smaller MAE that will generate better recommendations as compared to other recommender systems. In the figure, the horizontal numbers show seven different items of the Jester dataset, while the vertical numbers show the corresponding MAE score of both systems for the selected items.The MAE curves of our algorithm in Figure3 are superior as compared to the other algorithm, which shows that our algorithm generates quality predictions for item ratings. For recommendation quality, the most widely used metrics are precision and recall. Precision is the recommended items that are relevant out of the total number of recommended items. A recall is the number of relevant recommended items out of the total number of relevant items. These two metrics are problematic in a case when at a given cutoff point, for example, precision@N, the number of relevant recommendations is less than Said et al. [43] have proposed a metric for recommendation quality, called R-precision. It has been shown empirically that R-precision reflects more accurately the quality of recommendation compared to the traditionally used metrics. Hence, we used R-precision for the evaluation of the recommendation quality of our recommender system. R-precision is computed as(13)R−precision=rR,where R shows the total number of relevant recommendations, while r is the number of retrieved recommendations that are relevant. Here, R is used as a cutoff point and varies from query to query. For the experiment on dataset 1, we randomly selected 6 different users from the Jester dataset and generated top 1, 2, 3, 4, 5, and 6 recommendations. The results obtained are shown in Figure 4.Figure 4
R-precision for the two recommender systems for dataset 1.Figure4 shows R-precision generated for the top-N recommendations. The results were compared with CBBCHPRS, which shows that our proposed APHPRS has better performance in comparison with other systems.Another experiment was performed on dataset 2, where we randomly selected 10 different users from the Jester dataset and gradually increased the size of the test set from 3, 6, 9, 12, 15, 18, 21, 24, 25, and 27. The results obtained are shown in Figure4.A second experiment has been conducted using a different dataset (dataset 2) taken from Jester data. For this experiment, we randomly selected 10 active users from the Jester dataset and generated the top 5, 10, and 15 recommendations. The results of the second experiment were compared with Bat Algorithm (BA) used in [45]. The results obtained show that our proposed recommender system produces high R-precision as compared to the existing BA.Figure5 represents the MAE calculated for our proposed APHPRS in comparison with the BA algorithm using dataset 2. The results show that our proposed system has a smaller MAE in most cases as compared to other systems. In this figure, the MAE values of the ten users were summed up for each top-N recommendation.Figure 5
MAE for the two recommender systems for dataset 2.A second experiment has been conducted using dataset 2 taken from Jester data. For this experiment, we randomly selected 10 different users from the Jester dataset and generated the top 5, 10, and 15 recommendations. The experiment was conducted to find theR-precision values. The results obtained show that our proposed recommender system produces high R-precision as compared to the existing BA (Figure 6).Figure 6
R-precision for the two recommender systems for dataset 2.It can be seen in Figure6 that the R-precision values of our system are higher than those of the other system, which indicates the quality of our recommendations.


## 5.1. Clustering Performance Evaluation

The performance of the proposed clustering algorithm was evaluated using the IRIS dataset that is available in the UCI repository (https://archive.ics.uci.edu/ml/datasets/Iris). The IRIS dataset contains a total of 150 objects divided into three main classes, where each class has 50 objects. The classes are labelled as “Setosa,” “Versicolor,” and “Virginica.” The performance of clusters was evaluated in terms of the accuracy of grouping each and every object according to the true classes. In the experiments, we compared the proposed algorithm with many baseline algorithms used for clustering. The proposed affinity propagation algorithm outperforms the existing algorithm as it clusters the object more accurately (see Table 8). The accuracy has been improved due to the message sending process of the proposed algorithm. Moreover, the proposed algorithm does not need the cluster number to be prespecified, and it automatically generates the cluster centroids (exemplars).Table 8
Clustering performance on IRIS dataset by the proposed algorithm and baseline algorithms.
IRIS classesClustering algorithmsk-meansk-mediodsCBBCAffinity propagationSetosa50505050Versicolor34414447Virginica66595653Table8 shows the evaluation of the proposed clustering algorithm on the IRIS dataset. In this table, the first column represents the various classes of the IRIS dataset and the second column holds the different algorithms and their clustering results. This table clearly reveals that the affinity propagation algorithm generates the clusters with more accuracy.


## 5.2. Performance Evaluation of the Proposed Recommender System

APHPRS has been implemented in MATLAB version 7.8. The experiment was conducted on the Jester dataset. We also implemented another collaborative filtering-based recommender system [43] manually for performance comparison, using R-precision and MAE metrics. To evaluate the performance, we have used two different sizes of datasets. Dataset 1 is a small subset of Jester data that consists of a user-item rating matrix having 10 users and 10 jokes (Table 2). Dataset 2 is a large subset of the Jester dataset consisting of 70,000 users and 100 jokes. The proposed APHPRS was evaluated by checking its prediction quality and recommendation quality.Prediction quality is tested by relating the predicted user rating to the test set of actual user ratings. For the evaluation of predictive accuracy, Mean Absolute Error (MAE) is used as a universal metric [44]. Hence, we used the MAE metric for evaluating the prediction quality of the proposed APHPRS. If we represent the set of rating prediction for items as p1, p2, p3, …, pN, and represent the set of corresponding actual user ratings as q1, q2, q3, …, qN, then MAE can be computed using(12)MAE=∑i=1Npi–qiN.The low MAE value will lead to greater quality of a recommender system, that is, smaller values of MAE, indicating that rating predictions are much similar to real ratings. For the experiment on dataset 1, we have randomly selected 7 different users from the Jester dataset and gradually increased the size of the test set from 1, 2, 3, 4, 5, 6, and 7 (Figure3). We have compared our proposed APHPRS system with the existing hybrid personalized recommender system using a centering-bunching-based clustering algorithm (CBBCHPRS) [40]. The proposed algorithm and the CBBCHPRS both use the same number of users of the Jester dataset.Figure 3
MAE for the two recommender systems for dataset 1.Figure3 represents the MAE calculated for our proposed APHPRS in comparison with CBBCHPRS. The result shows that our proposed system has a smaller MAE that will generate better recommendations as compared to other recommender systems. In the figure, the horizontal numbers show seven different items of the Jester dataset, while the vertical numbers show the corresponding MAE score of both systems for the selected items.The MAE curves of our algorithm in Figure3 are superior as compared to the other algorithm, which shows that our algorithm generates quality predictions for item ratings. For recommendation quality, the most widely used metrics are precision and recall. Precision is the recommended items that are relevant out of the total number of recommended items. A recall is the number of relevant recommended items out of the total number of relevant items. These two metrics are problematic in a case when at a given cutoff point, for example, precision@N, the number of relevant recommendations is less than Said et al. [43] have proposed a metric for recommendation quality, called R-precision. It has been shown empirically that R-precision reflects more accurately the quality of recommendation compared to the traditionally used metrics. Hence, we used R-precision for the evaluation of the recommendation quality of our recommender system. R-precision is computed as(13)R−precision=rR,where R shows the total number of relevant recommendations, while r is the number of retrieved recommendations that are relevant. Here, R is used as a cutoff point and varies from query to query. For the experiment on dataset 1, we randomly selected 6 different users from the Jester dataset and generated top 1, 2, 3, 4, 5, and 6 recommendations. The results obtained are shown in Figure 4.Figure 4
R-precision for the two recommender systems for dataset 1.Figure4 shows R-precision generated for the top-N recommendations. The results were compared with CBBCHPRS, which shows that our proposed APHPRS has better performance in comparison with other systems.Another experiment was performed on dataset 2, where we randomly selected 10 different users from the Jester dataset and gradually increased the size of the test set from 3, 6, 9, 12, 15, 18, 21, 24, 25, and 27. The results obtained are shown in Figure4.A second experiment has been conducted using a different dataset (dataset 2) taken from Jester data. For this experiment, we randomly selected 10 active users from the Jester dataset and generated the top 5, 10, and 15 recommendations. The results of the second experiment were compared with Bat Algorithm (BA) used in [45]. The results obtained show that our proposed recommender system produces high R-precision as compared to the existing BA.Figure5 represents the MAE calculated for our proposed APHPRS in comparison with the BA algorithm using dataset 2. The results show that our proposed system has a smaller MAE in most cases as compared to other systems. In this figure, the MAE values of the ten users were summed up for each top-N recommendation.Figure 5
MAE for the two recommender systems for dataset 2.A second experiment has been conducted using dataset 2 taken from Jester data. For this experiment, we randomly selected 10 different users from the Jester dataset and generated the top 5, 10, and 15 recommendations. The experiment was conducted to find theR-precision values. The results obtained show that our proposed recommender system produces high R-precision as compared to the existing BA (Figure 6).Figure 6
R-precision for the two recommender systems for dataset 2.It can be seen in Figure6 that the R-precision values of our system are higher than those of the other system, which indicates the quality of our recommendations.


## 6. Conclusion

Recommender systems are the tools and techniques used for handling a load of information by filtering a large amount of information and then suggesting a piece of information relevant to the user. This paper proposed APHPRS, an Affinity Propagation-Based Hybrid Personalized Recommender System collecting user preferences of the matrix of items rated by different users, clustered it, and generated recommendations for the user. The clustering method used in this work outperforms other baseline methods as tested on IRIS data; however, this method fails to produce effective results when the similarity matrix is not calculated well. We have combined the features of content-based approaches and collaborative filtering approaches for making the system hybrid. The previous work done in this domain suggests that only similarity score was considered by the existing recommender systems, whereas we incorporated the cluster’s quality and density and combined both with the similarity score for selecting a range of quality clusters for recommendations. This helps in discovering the additional clusters which have similarities in accordance with user preference. Evaluation of our proposed APHPRS was made using the Jester dataset. Furthermore, the APHPRS is compared with another hybrid system CBBCHPRS. The performance of our system was evaluated in terms of prediction quality and recommendation quality. The prediction quality was calculated using the MAE score, while recommendation quality was measured in terms ofR-precision. The slight decrease in the MAE score is evidence that sparsity has less impact on our proposed system. Similarly, the R-precision of our proposed system is much higher as compared to the existing systems. The increase in R-precision shows that our proposed approach has better results in recommending items.In future work, we will use the Seed Affinity Propagation (SAP) algorithm that is an advanced version of affinity propagation for finding clusters. We will also consider ontology as a knowledge base for improving prediction accuracy in the future.



---

*Source: 6958596-2022-01-28.xml*