Effective Context-Aware Recommendations Based on Context Weighting Using Genetic Algorithm and Alleviating Data Sparsity

ABSTRACT

Context-aware collaborative filtering (CACF) is an effective approach for adapting recommendations under users’ specific contextual situations and aims to improve predictive accuracy for Context-aware recommender systems (CARSs). Incorporating context in recommender systems (RSs) considering the equal importance to all contextual dimensions is not appropriate for seeking an intelligent and useful recommendation. In this paper, we propose a Real-coded Genetic Algorithm (RCGA) based CARS framework that exploits contextual pre-filtering and contextual modeling paradigms into CACF with appropriate context feature weights for enhancing accuracy as well as the diversity of the recommendation list. Further to alleviate the data sparsity, an effective missing value prediction (EMVP) algorithm is applied into proposed framework. The accuracy based on RCGA is compared with other two schemes: Support Vector Machine (SVM) and Particle Swarm Optimization (PSO), and RCGA has shown better results. Experimental results based on real-world datasets have clearly established the effectiveness of our proposed CARS schemes.

Introduction

At the time of exceptional growth in the importance of search technologies, many researchers and practitioners focus on how interactive systems can encourage and support the users’ behavior changing with encapsulated context. Context-aware recommender systems (CARSs) offer a new perspective of multi-dimensionality that makes the recommendation more relevant and intelligent (Adomavicius and Tuzhilin 2005).

CARSs differ from traditional RSs because they not only use ratings given by users for items but also exploit both the knowledge of the contextual situations under which the ratings were acquired and the target user asking for a recommendation. More specific definition of context can be as any circumstances or conditions which affect something or someone. The significance of contextual information has been identified in many disciplines including information retrieval, e-commerce personalization, ubiquitous and mobile context-aware systems, databases, data mining, marketing, and management (Adomavicius et al. 2011). However, the aggregation of multiple contexts gathers potentially useful information that would result in the increased predictive power of CARSs. An ideal CARS should be capable of labeling each user action with an appropriate context and effectively tailor the system output to the user in that given context.

Various approaches based on context-aware collaborative filtering (CACF) have been developed to utilize the strength of traditional collaborative filtering (CF) techniques to enhance recommendation ability of CARSs to pursue different tasks other than a product/item recommendation (Shi, Larson, and Hanjalic 2014; Verbert et al. 2012). In spite of that, the danger of sparsity arises if contextual information is applied too strictly. However, data sparsity usually complicates the process of item recommendation under neighborhood-based CF domain (Shams and Haratizadeh 2017). The performance of CF-based RSs is mostly evaluated through the predictive accuracy of the recommendations. Relying on the accuracy of recommendations alone may not be enough to find the most relevant items for a user and hence the diversity can be another important quality measure/criterion in the recommendation process (Adomavicius and Kwon 2008). Though the highly desirable feature of diversity is contrasting to accuracy, many researchers have compared several filtering techniques for CARSs in terms of accuracy and diversity (Panniello, Tuzhilin, and Gorgoglione 2014). The aim of our work is to identify an influential set of context features with appropriate weights effectively learned for each individual and handling sparse data that preserves both the accuracy and diversity.

The main contributions of this paper are summarized as follows:

• We designed a context-aware recommendation scheme CACF, that is based on contextual pre-filtering and contextual modeling paradigms with a novel approach of context weighting using RCGA.

• Our proposed scheme is compared with other well-Known schemes: Support Vector Machine (SVM) and Particle Swarm Optimization (PSO) for parameter optimization.

• Further, an effective missing value prediction algorithm (EMVP) (Ma, King, and Lyu 2007) is incorporated into the proposed schemes to handle the sparsity problem.

• Finally, we generated appropriate context feature weights using RCGA for the proposed CARS which would balance both accuracy and diversity of Top-N recommended list of items for each user.

The rest of the paper is organized as follows. Section 2 provides an overview of the state-of-the-art in the areas relevant for this research work. Section 3 presents the proposed RCGA-based CARS framework and demonstrates how the missing value prediction approach is assembled to alleviate the problem of sparsity and also presents $F_{\beta }-measure$ for optimizing the tradeoff between accuracy and diversity. The experimental evaluation of aforementioned schemes is discussed in Section 4. Finally, Section 5 concludes with a discussion of the findings of our work and an outlook on future research needs and opportunities.

Related Work

With the increasing popularity of mobile apps, there is a need for CARS frameworks and models, appropriate for people who have a wide range of marketplaces where they can seek a lot of resources. A methodology is built for Context-aware mobile recommender systems, whereby users are asked to judge whether a contextual factor (e.g. Weather) influences the rating given under a certain contextual condition (e.g. The weather is cloudy) based on recommendation domain (e.g. Movie) (Campos et al. 2013). Furthermore, for providing location-based services like travel and tourism, various paradigms in Location-aware recommender system (LARS) have been proposed that use location-based ratings and real-world GPS datasets to produce personalized recommendation (Liu et al. 2013; Sarwat et al. 2014). Similarly, the long tail Context-aware music recommender systems (CAMRSs) can automatically play suitable music considering various users’ contextual information, such as weather, emotional state, running pace, location, time, social media activities, and low-level activities in real time that could save our time and effort (Wang et al. 2014).

The different application domains exhibited by different recommender algorithms show that recommendation process is not a one-size-fits-all problem. We need to have a deep understanding of choosing a recommender algorithm embedded with CARS that depends on specific domains. Most of the approaches are based on CF which strongly depends on the availability of meaningful user ratings on a large scale that leads to the problem of sparsity. Therefore, two models have been proposed: Differential Context Relaxation (DCR) and Differential Context Weighting (DCW) to deal with the problem of the sparsity of contexts (Zheng, Burke, and Mobasher 2013).

Techniques for Learning Context Feature Weights

In the following subsections, we briefly introduce some optimization techniques such as, SVM, PSO, and RCGA for learning context feature weights.

Support Vector Machine (SVM)

The Support Vector Machine (SVM) is a statistical learning theory, based on data mining method developed by Vapnik and the principle of Structural Risk Minimization is implemented by constructing an optimal separating hyperplane (Min and Han 2005; Min, Lee, and Han 2006). A linear SVM classifier is a hyperplane that separates all items into two classes, such as, like and dislike for each active user $u_a$. Suppose $n$ training samples have pairs $\left(x_1,y_1\right),\left(x_2,y_2\right),\left(x_3,y_3\right),\dots ,\left(x_n,y_n\right)$ where $x_i=\left(x_{i1},x_{i2},\dots ,x_{im}\right)$ are a set of input context features, and $x_i\in R^n$ and $y_i\in \left\{-1,1\right\}$ are corresponding outputs, 1 for like and −1 for dislike class. The task of linear SVM is to learn feature weights by mapping all pairs $\left(x_i,y_i\right)$ into separating hyperplanes $u_j=\vec{w}\cdot \vec{x}\pm b$, where $\vec{w}$ is the vector of context feature weights and $\vec{x}$ is the vector of input context features. The target is to maximize the distance of the hyperplanes to the nearest of the like and dislike classes. Maximizing the margin can be expressed as an optimization problem: $min\frac{1}{2}{\vec{w}}^2$ subject to $y_i\left(\vec{w}\cdot \vec{x}\pm b\right)\ge 1$, $\mathrm{\forall }i$ where $x_i$ is the $i^{th}$ training samples.

Particle Swarm Optimization (PSO)

Inspired by the collective behavior of birds and fishes, and the concept of evolutionary algorithm, Particle Swarm Optimization (PSO) algorithm was developed by Kennedy and Eberhart (1995). It is an evolutionary computation technique based on swarm intelligence. For solving complex optimization problems, it is easy to implement and computationally less expensive in terms of both speed and memory requirements (Osuna-Enciso et al. 2016). PSO starts with a population of random solutions, and each individual solution is named as “particle” which represents a potential solution. Each particle is treated as a point in $n$-dimensional space. The $i^{th}$ particle is represented as $z_i=\left(z_{i1},z_{i2},\dots ,z_{im}\right)$. The best previous position of any particle is recorded and represented as $p_i=\left(p_{i1},p_{i2},\dots ,p_{in}\right)$. The index of globally best particle’s position is represented as $p_g$ and the velocity (i.e. rate of change of a particle’s position) is represented as $v_i=\left(v_{i1},v_{i2},\dots ,v_{in}\right)$. The updated velocity $v_{in}^{k+1}$ and position $z_{in}^{k+1}$ of the $i^{th}$ particle at the $k^{th}$ iteration are:

(1) $v_{in}^{k+1}=\sigma \cdot v_m^k+l_1\cdot ran{d}_1\cdot \left(p_{in}-z_{in}^k\right)+l_2\cdot ran{d}_2\cdot \left(p_{gn}-z_{in}^k\right)$(1)

(2) $z_{in}^{k+1}=z_{in}^k+v_{in}^{k+1}$(2)

where $l_1$ and $l_2$ are learning factors, $\sigma$ is inertia weight for balancing the global and local search, $ran{d}_1$ and $ran{d}_2$ are random values in the range between $0$ and $1$.

Real-Coded Genetic Algorithm (RCGA)

Genetic Algorithm (GA) (Goldberg 1989) has received considerable attention toward handling any kind of objective function and any kind of constraints, i.e. linear or non-linear, defined on discrete, continuous or mixed search spaces. Most studies on feature weighting have used GA as the main heuristic method for determining weight vector (Noori 2015). The basic building blocks of binary GAs are genes and chromosomes. Chromosomes are evaluated by running GA for the respective parameter configuration and each GA uses a small-sized population of chromosomes to alleviate the problem of slow convergence, without losing potential solution (Wahde 2008). The conventional binary GA encodes the gene as a binary bit and chromosome as a string of binary bits. Whereas RCGA encodes the parameters in continuous domain representing genes as floating-point number and chromosome as a vector of floating-point numbers. In RCGA scheme, a chromosome length becomes much shorter than binary coding scheme (Blanco, Delgado, and Pegalaja 2001).

Proposed RCGA-based CARS Framework

The goal of the proposed framework is to enhance the capability of CARSs by improving the predictive accuracy. It combines a proposed novel aspect of context weighting using RCGA with features of state-of-the-art CARSs framework. The purpose of Context-Aware Collaborative Filtering (CACF) algorithm is to recommend a list of new items with current context for a particular active user based on his past experiences and like-minded users having experience in a similar context. The real coding approach seems particularly natural when tackling the problem of optimizing parameters with the variables in continuous domains (Herrera, Lozano, and Verdegay 1998). Therefore, we use RCGA to learn the individual user’s preferences for quality recommendations. The contextual pre-filtering and contextual modeling-based CACF algorithm is proposed for the CARS framework. Further to establish the superiority of our proposed RCGA, we have compared it with other two schemes, SVM and PSO.

The RCGA-based CARS framework exploits the idea of context weighting scheme into CACF algorithm, signifies the contribution of each context feature is weighted, where weighting vector $W=\left(w_1,w_2,\dots ,w_k\right)$ consists of real values lies between $\left\{0,1\right\}$ and the sum of weights equal to $1$. More specifically, there is a list of $n$ users $U=\left(u_1,u_2,\dots ,u_n\right)$, a list of $m$ items $I=\left(i_1,i_2,\dots ,i_m\right)$, and a list of $k$ context features $C=\left(c_1,c_2,\dots ,c_k\right)$. Each user u has a list of items experienced in certain contexts. We have given a target context $C_a$ for an active user $u_a$, we need to assess how much to weight a rating $r_{u_a,i,C_j}$ issued in some different context $C_j$, subject to a weighting vector $W$. Context weighting using RCGA can be considered as a novel approach for CARSs which requires an optimal set of context feature weights for each user.

Data Collection

To anticipate the relevance of an item for a user in a certain context, it needs to be filled with the value of each context feature through users’ past history which helps in providing personalized recommendations. The acquired contextual information is either static or dynamic in nature, but we picked up only the static nature of the context. Such information is explicitly captured, i.e. input given by users.

Neighbor Generation

One critical step of CACF is to compute the similarity between users interact with items in similar context features and identify the users with similar inclinations, which is useful for the generation of the relevant neighborhood set. The original CF-based recommendation scenario is most familiar, mature, and widely implemented to filter out the undesired list of users. The CACF follows the same scenario of CF which leverages the pervasive contextual information such that a user’s preference is not only predicted from opinions of similar users but also from feedback of other users in a context similar to that the user currently is in.

Similarity Computation of Context Features

The notion of context similarity computation is to give a higher importance to ratings of items when the computed context similarity is high. Selecting top neighbors $N_{u_a},W,{\mu }_1$ of the active user $u_a$ for target item $i$ under context feature vector $C_a$ satisfying threshold value ${\mu }_1$ using weighted Jaccard metric $J\left(C_a,C_j,W\right)$, we need to assess how much to weight a rating $r_{u_a,i,C_j}$ issued in some different context vector $C_j=\left(c_1,c_2,\dots ,c_k\right)$ subject to a weighting vector $W$. The context similarity computation metric $J\left(C_a,C_j,W\right)$ and top neighbors $N_{u_a,W,{\mu }_1}$ are defined as:

(3) $J\left(C_a,C_j,W\right)=\frac{{\sum }_{c_f\in C_a\cap C_j}{W}_{c_f}}{{\sum }_{c_f\in C_a\cup C_j}{W}_{c_f}}$(3)

(4) $N_{u_a,W,{\mu }_1}=\left\{u:{max}_{r_{u,i}}\left(J\left(C_a,C_j,W\right)>{\mu }_1\right)\right\}$(4)

Computation of Users’ Similarity

The traditional similarity measure matrices gauge efficiently that how closely the opinions of a user’s pair match, taking into account only the ratings made by such pair. Although they rely only on computing the degree of agreement based on the set of items co-rated by the users, Pearson Correlation Coefficient (PCC) is the most popular among them (Chen 2005; Anand 2011). The modified CACF technique computed to measure users’ similarity using Equations (5)(5) $T_{{\mu }_2}=\left\{\left(I_a,C_a,C_j\right):\mathrm{\exists }{r}_{u_a,i,C_a},r_{u_j,i,C_j}\cdot J\left(C_a,C_j,W\right)>{\mu }_2\right\}$(5) and (6) respectively.

(5) $T_{{\mu }_2}=\left\{\left(I_a,C_a,C_j\right):\mathrm{\exists }{r}_{u_a,i,C_a},r_{u_j,i,C_j}\cdot J\left(C_a,C_j,W\right)>{\mu }_2\right\}$(5)

(6) $\begin{array}{rl}& si{m}_W\left(u_a,u_j,W,{\mu }_2\right)\\ & =\frac{{\sum }_{\left(i,C_a,C_j\right)\in T_{{\mu }_2}}\left(r_{u_a,i,C_a}-{\bar{r}}_{u_a}\right)\left(r_{u_j,i,C_j}-{\bar{r}}_{u_j}\right)\left(J\left(C_a,C_j,W\right)\right)}{\sqrt{{\sum }_{\left(i,C_a,C_j\right)\in T_{{\mu }_2}\left(i,C_a,C_j\right)\in T_{{\mu }_2}}{\left(r_{u_a,i,C_a}-{\bar{r}}_{u_a}\right)}^2{\left(r_{u_j,i,C_j}-{\bar{r}}_{u_j}\right)}^2{\left(J\left(C_a,C_j,W\right)\right)}^2}}\end{array}$(6)

where ${\mu }_2$ is second similarity threshold, $T_{{\mu }_2}$ is the set of all collected items $I_a$, and pair of context feature vectors $C_a$ and $C_j$ is used for users $u_a$ and $u_j$ respectively, such that each has rated $i$ in that context with $J\left(C_a,C_j,W\right)>{\mu }_2$. We follow two stages in the recommendation process leading to two paradigms contextual pre-filtering and contextual modeling. Our assumption here, the given ratings of more similar contexts are more reliable for further predictions. However, there is a limit to this effect that context features with low similarity may add irrelevant ratings to the predictions. So, we use two similarity thresholds ${\mu }_1$ and ${\mu }_2$ to filter ratings for each stage.

Learning Context Feature Weights Using RCGA

The similarity is computed in terms of individual context feature similarity using weighted Jaccard measure and users’ similarity using modified PCC, treats all context features equally important, and considers all weights, i.e. $w_i^{\prime s}$ are equal. This may not truly reflect the contribution of each context feature toward the similarity where users put different weights to different features (Agrawal and Bharadwaj 2013). To overcome such limitation, we adopt RCGA approach, which is one of the most effective and appropriate techniques for optimization problem.

Chromosome Representation

In our RCGA-based approach, each chromosome is represented as a set of weights $\left\{w_1,w_2,\dots ,w_{10}\right\}$, where each weight has two variables which indicate the maximum and minimum limits for weights in the range of valid values. Our approach shows how the weights defining users’ priorities can be evolved by the RCGA to learn the personal preferences of users and provide tailored suggestions. These weights are generated offline to every context feature for each user and determined in such a way that the sum of all weights is equal to $1$, i.e. $\sum w_i=1$. Initially, we considered all weights are equally distributed, indicating that user $u$ is giving equal priorities to all features. The potential to the problem of evolving context feature weights $W\left(u_a\right)$ for the active user $u_a$ is represented as a set of weights $W_{cf}=\left\{w_1,w_2,\dots ,w_{10}\right\}$, where $W_{cf}$ is the weight is associated with each context feature $c_f\in \left(c_1,c_2,\dots ,c_{10}\right)$ whose chromosome is a sequence of floating point numbers.

Crossover and Mutation Operators

Genetic operators are used in GA to maintain genetic diversity. In general, the gathered information resulting from GA is done by the selection mechanism is referred as exploitation, while exploration is searching for new regions within search space by Genetic operators. Although a number of crossover and mutation operators are suggested and applied for RCGA (Agrawal and Bharadwaj 2013). We employed the mostly used operators arithmetic crossover and uniform mutation for RCGA-based CARS. Crossover creates two new child chromosomes by allowing two parent chromosomes to exchange meaningful information, while mutation is used to maintain the genetic diversity of the population by introducing a completely new member into the parent chromosome. Figure 1 illustrates with an example of how RCGA operators work.

Figure 1. RCGA operators (a) Arithmetic crossover with a random value $r=0.251$ and (b) Uniform mutation with selected gene $i=10$ replaces with $\left({\alpha }_{10},{\beta }_{10}\right)=0.4854$.

Fitness Function

Finding an appropriate fitness function is a challenging task for GA applications (Goldberg 1989). Each individual candidate solution in the population is assessed for its quality score known as the fitness score. A fitness function is an objective function that prescribes the optimality of a solution (chromosome) in a GA so that a particular chromosome may be ranked against all the other chromosomes. By applying GA operators, optimal chromosomes are allowed to breed and mix their datasets producing a new generation that will hopefully be better. An ideal fitness function correlates closely with the algorithm’s goal, and yet may be computed quickly. For each chromosome in the population, CACF is applied and Mean Absolute Error (MAE) is computed using Equation (7)(7) $fitness\left(u_a\right)=\frac{1}{\left|S_a^{TE}\right|}\sum _{j=1}^{\left|S_a^{TE}\right|}\left|r_{a,j}-P{r}_{a,j}\right|$(7) as the average difference between actual rating and predicted rating for all users in the training set which is also used as a fitness score for that set of weights.

(7) $fitness\left(u_a\right)=\frac{1}{\left|S_a^{TE}\right|}\sum _{j=1}^{\left|S_a^{TE}\right|}\left|r_{a,j}-P{r}_{a,j}\right|$(7)

Each user $u$ contains $10$ genes corresponding to weights for each context feature, which are evolved by an elitist approach. When the weight for any context feature is zero, that feature is ignored, which enables feature selection to be adaptive to each user’s preference. Such weights are used in Equations (3-6)(3) $J\left(C_a,C_j,W\right)=\frac{{\sum }_{c_f\in C_a\cap C_j}{W}_{c_f}}{{\sum }_{c_f\in C_a\cup C_j}{W}_{c_f}}$(3) to generate neighborhood set on the basis of users’ similarity and context similarity. The chromosome search space for RCGA is defined in range $\left[0,1\right]$, i.e. initially we assume that each weight lies between $0$ and $1$. Finally, the chromosome that gives the minimum MAE is chosen (such as minimization problem) which is suitable for our work.

Recommendation

To make recommendation accurate for an active user $u_a$ and a neighborhood set matching with a similar profile of the active user, it is necessary to find items experienced by users in the neighborhood set that the active user has not experienced before. After neighbors’ selection, the next step is to utilize similarity values for the computation of predicted ratings. The predicted rating $P_{u_a,i,W}$ of an item $i$ for an active user $u_a$ is obtained by using Equation (8)(8) $P_{u_a,i,W}={\bar{r}}_{u_a,C_a}+\frac{{\sum }_{u\in N_{u_a,W,{\mu }_1}}\left(\left(r_{u_j,i,C_j}-{\bar{r}}_{u_j,C_a}\right)\times si{m}_W\left(u_a,u_j,W,{\mu }_2\right)\right)}{{\sum }_{u\in N_{u_a,W,{\mu }_1}}si{m}_W\left(u_a,u_j,W,{\mu }_2\right)}$(8) .

(8) $P_{u_a,i,W}={\bar{r}}_{u_a,C_a}+\frac{{\sum }_{u\in N_{u_a,W,{\mu }_1}}\left(\left(r_{u_j,i,C_j}-{\bar{r}}_{u_j,C_a}\right)\times si{m}_W\left(u_a,u_j,W,{\mu }_2\right)\right)}{{\sum }_{u\in N_{u_a,W,{\mu }_1}}si{m}_W\left(u_a,u_j,W,{\mu }_2\right)}$(8)

The main steps of the proposed RCGA-based CARS using a hybrid CACF algorithm to perform recommendation task are summarized as follows and also depicted in Figure 2:

Figure 2. Schematic view of the RCGA-based CARS.

Step 1. Input data

In this step, users’ profiles, items’ profiles, and value of context features with ratings are collected in the form of $User\times Item\times Contexts\left(c_1,c_2,\dots ,c_k\right)\to Ratings$, where $c_1,c_2,\dots .,c_k$ are context features.

Step 2. Learning context feature weights using RCGA

Context feature weights for each individual are learned by applying RCGA and finding the best fitness score using Equation (7)(7) $fitness\left(u_a\right)=\frac{1}{\left|S_a^{TE}\right|}\sum _{j=1}^{\left|S_a^{TE}\right|}\left|r_{a,j}-P{r}_{a,j}\right|$(7) . Let $\left\{w_1,w_2,\dots ,w_k\right\}$ be the context feature weights for an active user.

Step 3. Neighborhood set generation

1. Compute the context similarity $J\left(C_a,C_j,W\right)$ for an active user with context feature weights using Equation (3)(3) $J\left(C_a,C_j,W\right)=\frac{{\sum }_{c_f\in C_a\cap C_j}{W}_{c_f}}{{\sum }_{c_f\in C_a\cup C_j}{W}_{c_f}}$(3) , and then generate the neighborhood set $N_{u_a,W,{\mu }_1}$ using Equation (4)(4) $N_{u_a,W,{\mu }_1}=\left\{u:{max}_{r_{u,i}}\left(J\left(C_a,C_j,W\right)>{\mu }_1\right)\right\}$(4) .

2. Compute the similarity $si{m}_w\left(u_a,u_j,W,{\mu }_2\right)$ between all pairs of users from the generated neighborhood set in Step 3(a) with context feature weights by using Equations (5)(5) $T_{{\mu }_2}=\left\{\left(I_a,C_a,C_j\right):\mathrm{\exists }{r}_{u_a,i,C_a},r_{u_j,i,C_j}\cdot J\left(C_a,C_j,W\right)>{\mu }_2\right\}$(5) and (6), and then generate final neighborhood set.

Step 4. Prediction computation and recommendation

Compute predicted rating $P_{u_a,i,W}$ based on adapted Resnick’s prediction formula by using Equation (8)(8) $P_{u_a,i,W}={\bar{r}}_{u_a,C_a}+\frac{{\sum }_{u\in N_{u_a,W,{\mu }_1}}\left(\left(r_{u_j,i,C_j}-{\bar{r}}_{u_j,C_a}\right)\times si{m}_W\left(u_a,u_j,W,{\mu }_2\right)\right)}{{\sum }_{u\in N_{u_a,W,{\mu }_1}}si{m}_W\left(u_a,u_j,W,{\mu }_2\right)}$(8) and finally recommend top-$N$ list of items for $u_a$.

Alleviating the Problem of Sparsity

In this section, we consider the framework for the effective missing value prediction (EMVP) follows the basic outline suggested by Ma, King, and Lyu (2007). It exploits both the ratings associated with context features and feature-based similarity among the similar breeds to predict the strength of users’ preferences according to the situation not yet provided. As illustrated in Figure 3a, the rating scale $1-5$ represents the users’ fondness of or preference toward the item within some contextual situation, and shaded blocks represent items rated for a given context feature vector in which rating is not available yet. Our approach utilizes the information linked up a user’s choices or preferences with the context in which the user rated an item to predict the shaded block (missing value) if possible. Otherwise, set it to zero, as seen in Figure 3b. The adapted EMVP algorithm consists of two components: Neighborhood set selection and Missing value prediction.

Figure 3. The (m x n) user-item subset matrix of movie dataset: (a) before missing value prediction. (b) after missing value prediction.

Neighborhood Set Selection

To predict missing value, both users’ similarity and items’ similarity are equally important. PCC is used to measure users’ similarity and items’ similarity. It involves context feature similarity using weighted Jaccard similarity measure which determines how relevant the ratings are under a given context for the active user when prediction occurs. For predicting every missing value $r_{u_a,i}$, a set of similar users $S\left(u_j\right)$ toward user $u_a$ can be generated according to:

(9) $S\left(u_j\right)=\left\{u_a:\left(si{m}^{\prime }\left(u_a,u_j\right)>\phi ,u_a\ne u_j\right)\right\}$(9)

Meanwhile, for predicting every missing value $r_{u_a,i}$, a set of similar items $S\left(i_j\right)$ toward item $i_a$ can be generated according to

(10) $S\left(i_j\right)=\left\{i_a:\left(si{m}^{\prime }\left(i_a,i_j\right)>\omega ,i_a\ne i_j\right)\right\}$(10)

where $\phi$ is a threshold parameter for users’ similarity and $\omega$ is a threshold parameter for items’ similarity. If the value of similarity computed between chosen neighbor and target user computed by using Equations (9)(9) $S\left(u_j\right)=\left\{u_a:\left(si{m}^{\prime }\left(u_a,u_j\right)>\phi ,u_a\ne u_j\right)\right\}$(9) and (10(10) $S\left(i_j\right)=\left\{i_a:\left(si{m}^{\prime }\left(i_a,i_j\right)>\omega ,i_a\ne i_j\right)\right\}$(10) ) exceeds the threshold, then the neighbor is selected as a similar user or similar item, otherwise neglected.

Missing Value Prediction

The missing value prediction algorithm systematically combines contextual information into both user-based CF and item-based CF approaches to take advantage of both user correlations and item correlations in the $user-item-context$ matrix which make the prediction more accurate. It will predict the missing value only if it will bring positive influence for the recommendation of active users instead of predicting every missing value of the matrix. If $S\left(u_j\right)=\varphi \mathrm{\Lambda }S\left(i_j\right)=\varphi$ then the predicted missing value $P\left(r_{u_a,i_a,C_a}\right)$ is set to zero, whereas, in other cases, the missing values are predicted using Equations (11(11) $\begin{array}{rl}& P\left(r_{u_a,i_a,C_a}\right)={\alpha }^{\prime }\times \left({\bar{u}}_a+\frac{{\sum }_{u_aϵS\left(u_j\right)}si{m}^{\prime }\left(u_a,u_j\right)\left(r_{u_a,i}-{\bar{u}}_a\right)J\left(C_a,C_j,W\right)}{{\sum }_{u_aϵS\left(u_j\right)}si{m}^{\prime }\left(u_a,u_j\right)J\left(C_a,C_j,W\right)}\right)\\ & +\left(1-{\alpha }^{\prime }\right)\times \left({\bar{i}}_a+\frac{{\sum }_{i_a\in S\left(i_j\right)}si{m}^{\prime }\left(i_a,i_j\right)\left(r_{u_a,i}-{\bar{i}}_a\right)J\left(C_a,C_j,W\right)}{{\sum }_{i_a\in S\left(i_j\right)}si{m}^{\prime }\left(i_a,i_j\right)J\left(C_a,C_j,W\right)}\right)\end{array}$(11) –13(13) $P\left(r_{u_a,i_a,C_a}\right)=\left({\bar{i}}_a+\frac{{\sum }_{i_a\in S\left(i_j\right)}si{m}^{\prime }\left(i_a,i_j\right)\left(r_{u_a,i}-{\bar{i}}_a\right)J\left(C_a,C_j,W\right)}{{\sum }_{i_a\in S\left(i_j\right)}si{m}^{\prime }\left(i_a,i_j\right)J\left(C_a,C_j,W\right)}\right)$(13) ).

If $S\left(u_j\right)\ne \varphi \mathrm{\Lambda }S\left(i_j\right)\ne \varphi$, the prediction of missing value $P\left(r_{u_a,i_a,C_a}\right)$ is defined as:

(11) $\begin{array}{rl}& P\left(r_{u_a,i_a,C_a}\right)={\alpha }^{\prime }\times \left({\bar{u}}_a+\frac{{\sum }_{u_aϵS\left(u_j\right)}si{m}^{\prime }\left(u_a,u_j\right)\left(r_{u_a,i}-{\bar{u}}_a\right)J\left(C_a,C_j,W\right)}{{\sum }_{u_aϵS\left(u_j\right)}si{m}^{\prime }\left(u_a,u_j\right)J\left(C_a,C_j,W\right)}\right)\\ & +\left(1-{\alpha }^{\prime }\right)\times \left({\bar{i}}_a+\frac{{\sum }_{i_a\in S\left(i_j\right)}si{m}^{\prime }\left(i_a,i_j\right)\left(r_{u_a,i}-{\bar{i}}_a\right)J\left(C_a,C_j,W\right)}{{\sum }_{i_a\in S\left(i_j\right)}si{m}^{\prime }\left(i_a,i_j\right)J\left(C_a,C_j,W\right)}\right)\end{array}$(11)

It needs to be considered those special cases when either do not get similar users’ set or similar items’ set, then it would fully utilize the information that makes predictions of missing values accurate as possible by follows.

If $S\left(u_j\right)\ne \varphi \mathrm{\Lambda }S\left(i_j\right)=\varphi$, the prediction of missing value $P\left(r_{u_a,i_a,C_a}\right)$ is defined as

(12) $P\left(r_{u_a,i_a,C_a}\right)=\left({\bar{u}}_a+\frac{{\sum }_{u_aϵS\left(u_j\right)}si{m}^{\prime }\left(u_a,u_j\right)\left(r_{u_a,i}-{\bar{u}}_a\right)J\left(C_a,C_j,W\right)}{{\sum }_{u_aϵS\left(u_j\right)}si{m}^{\prime }\left(u_a,u_j\right)J\left(C_a,C_j,W\right)}\right)$(12)

If $S\left(u_j\right)=\varphi \mathrm{\Lambda }S\left(i_j\right)\ne \varphi$, the prediction of missing value $P\left(r_{u_a,i_a,C_a}\right)$ is defined as

(13) $P\left(r_{u_a,i_a,C_a}\right)=\left({\bar{i}}_a+\frac{{\sum }_{i_a\in S\left(i_j\right)}si{m}^{\prime }\left(i_a,i_j\right)\left(r_{u_a,i}-{\bar{i}}_a\right)J\left(C_a,C_j,W\right)}{{\sum }_{i_a\in S\left(i_j\right)}si{m}^{\prime }\left(i_a,i_j\right)J\left(C_a,C_j,W\right)}\right)$(13)

Optimizing the Tradeoff between Accuracy and Diversity Using RCGA

The set of recommended item list should maintain a certain level of diversity with compromising certain level of accuracy, since the increasing diversity level can help commercial sites to promote long tail items sell. In order to suggest highly idiosyncratic and personalized products, one should consider offering not only accurate, but also diverse recommendations to fulfill users’ satisfaction. Our primary goal is to improve users’ satisfaction by maximizing the relevance of the suggested items to the target user. In this paper, we focus on aggregate diversity computation with measure dissimilarity between the pair of recommendation items on the basis of assigned weights to each context feature for users. For dissimilarity measure, we use the weighted Euclidean distance as given below.

(14) $dist\left(i_a,i_j,W\right)=\sqrt{\sum _{j=1}^{n}W{\left(C_{i_a}-C_{i_j}\right)}^2}$(14)

The dissimilarity $dist\left(i_a,i_j,W\right)$ between pair of items $i_a$ and $i_j$ is calculated by the given value of context features $C_{i_a}$ for item $i_a$ and $C_{i_j}$ for item $i_j$ respectively with learned weights $W$ assigned for active user $u_a$ The following steps are used to compute aggregate diversity using S-TDE (Premchaiswadi et al. 2013) for top-$N$ recommendations, the items must be ranked in descending order based on their predicted ratings before suggesting to active user $u_a$. For evaluation of such ranking, the number of actual relevant items $\left|L_a\cap L_p\right|$ in the recommended list of a user is calculated. Where $L_a$ and $L_p$ are the target list of all items and predicted relevant items, respectively. Due to each item in a recommendation list can effect on the total diversity value of recommendations differently, Total diversity Effect (TDE) (Premchaiswadi et al. 2013) of items in top-$N$ recommendations rely on the dissimilarities between each pair of items in the list. So, TDE is calculated with the help of Equation (15)(15) $TDE={\sum }_{j=1\dots \left|L_p\right|}dist\left(i_a,i_j,W\right);a\ne j,C_{i_a}\ne C_{i_j}$(15) .

(15) $TDE={\sum }_{j=1\dots \left|L_p\right|}dist\left(i_a,i_j,W\right);a\ne j,C_{i_a}\ne C_{i_j}$(15)

The total diversity $div\left(L_p\right)$ of the recommendation list $L_p$ is defined as the average distance between all possible pairs of items in the list is calculated using Equation (16)(16) $div\left(L_p\right)=\frac{TDE}{\left|L_p\right|\cdot \left(\left|L_p\right|-1\right)/2}$(16) .

(16) $div\left(L_p\right)=\frac{TDE}{\left|L_p\right|\cdot \left(\left|L_p\right|-1\right)/2}$(16)

Then, we measure recommendation diversity as the total number of distinct items that are being recommended across all users. We aggregate all diversity of the recommendation list $TL$ for all users to get average diversity $avgdiv\left(TL\right)$.

(17) $avgdiv\left(TL\right)=\frac{{\sum }_{L_p\in TL}div\left(L_p\right)}{\left|TL\right|}$(17)

Finally, we propose a set of context feature weights learned by RCGA for each individual applying in $F_{\beta }-measure$ formula, which satisfy both accuracy and diversity in an optimum level. The $F_{\beta }-measure$ summarized both accuracy and diversity in terms of threshold $\beta$ to establish a balanced relationship between the accuracy $A$ and diversity $D$.

(18) $F_{\beta }-measure\left(A,D\right)=\left(1+{\beta }^2\right)\frac{A\times D}{A+D}$(18)

Experiments and Results

This section illustrates the results of the computational experiments performed to evaluate and analyze the effectiveness of the proposed RCGA-based CARS. The following subsections describe the set of experiments that we have conducted to examine the effectiveness of our new context weighting scheme. Particularly, we address the following three issues. First, we analyze the performance of the proposed CARS framework in terms of accuracy by considering two cases (a) CARS with equal context feature weights and (b) CARS with learned context feature weights. Second, in order to handle the sparsity problem we use learned context feature weights and employing EMVP algorithm. Finally, we analyze the tradeoff between accuracy and diversity of the CARS for the two real-world datasets discussed below.

Experimental Settings

To carry out experiments, we take two real-world datasets to evaluate our proposed model. In the area of movie, the movie dataset extracted from LDOS-CoMoDa dataset.¹ The description of $10$ opted context features is presented in Table 1. The Restaurant-Customer dataset extracted from UCI Machine Learning Repository² is also used for our experiments. Users added and rated new and existing restaurants filled with $10$ opted context features described in Table 2. We performed experiments with gathering 10 random splits into training and active users. For each random split, three different sets of sample users (3, 5, and 10) were chosen randomly as active users, and remaining users were treated as training users for proposed RCGA-based CARS. Such random splits are intended for the execution of ten-fold cross-validation, where all experiments are repeated for $split1,split2,\dots ,split10$. The set of training users is used to find a set of neighbors for the active user, while the set of active users is used to test the performance of the system. To perform a context feature weights learning process for each dataset, we use different chromosome structures with $10$ weights represented in Figures 4 and 5.

Table 1. Context features in Movie Dataset.

Context Features	Description
Time	Morning, Afternoon, Evening, Night
Daytype	Weekday, Weekend, Holiday
Season	Spring, Summer, Autumn, Winter
Location	Home, Public place, Friend’s home
Weather	Sunny, Rainy, Stormy, Snowy, Cloudy
Social	Alone, Partner, Friends, Colleagues, Parents, Public, Family
Mood Physical Decision Interaction	Positive, Neutral, Negative Healthy, Ill User picked the item, Item suggested by other First n-th

Table 2. Context features in Restaurant-Customer dataset.

Context Features	Description
R-alcohol	No-alcohol, Wine-beer, Full-bar
R-accessible	Completely, No-accessible
R-price	Low, Medium, High
R-ambience	Familiar, Quite
R-area	Open, Closed
C-ambience	Family, Solitary, Friends
C-marital-status C-transport C-interest C-personality	Single, Married, Widow On foot, Public, Car owner Variety, Technology, None Thrifty-protector, Hunter-ostentatious, Hard-worker

Figure 4. The structure of chromosome in Movie dataset.

Figure 5. The structure of chromosome in Restaurant-Customer dataset.

In order to demonstrate relative performances of the following schemes:

• Context-aware collaborative filtering with equal weights (CE).

• Context-aware collaborative filtering with learned weights using SVM (CW-SVM).

• Context-aware collaborative filtering with learned weights using PSO (CW-PSO).

• Context-aware collaborative filtering with learned weights using RCGA (CW-RCGA).

• Proposed RCGA-based CARS framework (CW-ERCGA).

• The proposed framework is further enhanced using learned weights with $F_{\beta }-measure$ (CW-ERCGA-F).

We have conducted three experiments:

• Experiment 1: Variation of Context feature weights depending on user-to-user using SVM, PSO, and RCGA.

• Experiment 2: Resolving the problem of sparsity using EMVP algorithm with the RCGA.

• Experiment 3: Learned context feature weights using RCGA for controlling the tradeoff between accuracy and diversity.

Results and Discussion

In this section, we present the results of the experimental evaluation with two different real-world datasets to show a generic approach in RCGA-based CARS framework.

Variation of Context Feature Weights Depending on User-to-user Using SVM, PSO, and RCGA

In the first experiment, we calculated the weights of each context feature for each individual user by CACF scheme using some of the parameters optimizing techniques SVM, PSO, and RCGA. We took $10$ sample sets of active users to test the importance of context features for each user and compared with other traditional CE scheme. The CE scheme computes the MAE using equal weights for each context feature contributing in similarity computation for each user $u_i:w_i=\frac{1}{10}$ and the other schemes CW-SVM uses SVM and CW-PSO uses PSO (see Table 3) for learning context feature weights. The proposed scheme CW-RCGA uses an elitist GA for evolving the context feature weights for each user separately based on parameter values as shown in Table 4. RCGA process begins with roulette wheel selection for the next generation, followed by the real value assignment for each of the 10 genes in the range [0, 1] and the normalized weights are such that $\sum _{i=1}{w}_i=1$.

Table 3. PSO parameter values used in Experiment.

Parameter Name	Parameter Value	Description
Ineria weight	0.9	The large value of inertia weight facilitates a global search and small value facilitates a local search.
Learning factor l1	2.0	It is the cognition parameter which represents how much the particle trusts its own past experience.
Learning factor l2	2.0	It is the social parameter which represents how much the particle trust the swarm.

Table 4. GA parameter values used in Experiment.

Parameter Name	Parameter Value	Description
Population size	10	The size of chromosome in the population n at each generation.
Minimum number of generations	10	After 10 iterations, the next iteration continues until the fitness score of the best chromosome is either less than or equal to previous fitness value, a good solution is found and this set of weights is used as a final set of context feature weights for that user.
Crossover probability	0.8	In each generation, 80% new chromosomes are generated using Arithmetic Crossover.
Mutation probability	0.2	In each generation, 20% new chromosomes are generated using Uniform Mutation.

RCGA learns context feature weights using the actual ratings in the training set for the active user and computes the fitness score using Equation (7)(7) $fitness\left(u_a\right)=\frac{1}{\left|S_a^{TE}\right|}\sum _{j=1}^{\left|S_a^{TE}\right|}\left|r_{a,j}-P{r}_{a,j}\right|$(7) . This process is repeated until the fitness score does not improve for $10$ consecutive generations. Therefore, the number of generations will vary with the fitness score of weights for each user as depicted in Figure 6. It is proved by Figure 7 that each user has a different proportion of affinity toward various context features and CW-RCGA outperforms other schemes CW-PSO, CW-SVM, and CE (see Table 5).

Table 5. Comparison of MAE using various CARS approaches CE, CW-SVM, CW-PSO and CW-RCGA in terms of accuracy using two datasets.

CARS Schemes	Movie Dataset (MAE)			Restaurant-Customer Dataset(MAE)
	3 Users	5 Users	10 Users	3 Users	5 Users	10 Users
CE	0.8796	0.8542	1.7428	0.4748	0.5493	0.5896
CW-SVM	0.8643	0.8402	1.6272	0.4722	0.4601	0.5135
CW-PSO	0.8726	0.8450	1.0416	0.4755	0.4514	0.4909
CW-RCGA	0.8565	0.7649	0.9726	0.4564	0.4090	0.4528

Figure 6. Variations in number of generations with fitness value for (a) Movie dataset (b) Restaurant-Customer dataset.

Figure 7. Comparison of evolved context feature weights for users in two datasets: (a) User 1 and User 2 in Movie dataset and (b) User 6 and User 7 in Restaurant-Customer dataset.

Resolving the Problem of Sparsity Using EMVP Algorithm with the RCGA

In the second experiment, we have tried to resolve the problem of high sparsity of contextual information in the rating matrix due to the fact that most users have not rated items under a similar context which is the main cause of low accuracy in the recommendation process. The EMVP algorithm works with the option of not to predict the missing value if it does not meet the predefined criteria, but it prevents from a bad prediction on missing value also. Our next idea is to propagate contextual information from one user to another in order to reduce the sparsity of contextual information.

Ideally, the configurable parameters should be set in a training set which indicate how we learned best suited CW-ERCGA’s parameters for desirable MAE. We assessed the impact of the various parameters on the predictive performance of CW-RCGA. For this purpose, we randomly choose different sets of parameters and picked the best one that gives a desirable MAE score over the testing set of active users. Naturally, the minimum MAE is attained for the best configuration of CW-ERCGA. It is evident from Figure 8 that the different parameters have a substantially different influence on the predictive performance of CW-ERCGA. The parameters $\phi$ and $\omega$ determine how many missing values that need to be predicted. If it sets too high, most of the missing values cannot be predicted, and if it sets too low, every user/item will obtain too many neighbor users/items which would cause the inaccuracy as well as an increase in the computation cost. Accordingly, to simplify our model we set ${\alpha }^{\prime }=0.5$, which balances the information from users and items and takes advantage of both types of CF (item-based CF and user-based CF). We plotted the results obtained by CW-RCGA against the results from CW-ERCGA over different sets of active users (see Figure 9). The results clearly demonstrate that CW-ERCGA outperforms CW-RCGA.

Figure 8. Comparison of evolved context feature weights for users in two datasets: (a) User 1 and User 2 in Movie dataset and (b) User 6 and User 7 in Restaurant-Customer dataset.

Figure 9. Comparison of MAEs between CW-RCGA and CW-ERCGA using two datasets: (a) Movie dataset (b) Restaurant-Customer dataset.

Learned Contextual Weights Using RCGA for Controlling the Tradeoff between Accuracy and Diversity

In the third experiment, we focus on the quality of top-$N$ recommendation of items in such order that the diversity is improved, while recommendation accuracy still mentioned. The effects of the top-$N$ list on both diversity and accuracy are conversely changing direction, while the diversity tends to increase with the values of top-$N$ increase (see Figure 10). We design the experiment to establish the balance between diversity and accuracy using the $F_{\beta }-measure$ approach and set the parameter value $\beta$ according to the preference of users on various application domains, such as, $\beta =1$ for Movie dataset and $\beta =0.5$ for the Restaurant-Customer dataset. Finally, we use RCGA for learning those weights to identify appropriate context features for each user that matches their criteria and give effective recommendation solutions. The results across all the evaluation triplets of accuracy, diversity, and $F_{\beta }-measure$ together with the learned context feature weights are depicted in Figure 11.

Figure 10. Top-N item recommendations with diversity for five samples of active users in two different datasets: (a) Movie dataset and (b) Restaurant-Customer dataset.

Figure 11. Effect of learned context feature weights on recommendation accuracy and diversity using RCGA in two CARS schemes CW-ERCGA and CW-ERCGA-F.

Conclusions and Future Directions

We have presented a real-coded genetic algorithm (RCGA) based CARS framework, where context features are weighted according to individual user’s preferences and choices. By using RCGA each user’s priority for each contextual feature is captured and that has significantly enhanced the performance in terms of both accuracy and diversity. The major issue in this approach is time complexity; however, this difficulty is resolved by performing offline learning of weights and the best set of weights are then stored on the user’s local machine, in a separate weight matrix which can be used for online recommendations (Al-Shamri and Bharadwaj 2008). Our work aims to address the sparsity problem in CARS by utilizing missing value prediction and optimize the tradeoff between accuracy and diversity using $F_{\beta }-measure$. We analyzed the effectiveness of different CARS schemes and compare their performance with the proposed scheme. Experimental results based on two real-world datasets show that the proposed context weighting scheme leads to a significant improvement as compared to other schemes.

One of the important directions in the future work would be toward enhancing the capability of the proposed CF-based CARS through hybridization with Reclusive method (Kant and Bharadwaj 2013). We would also consider the exploitation of spatio-temporal contextual information into mobile applications and incorporation of trust-distrust propagation mechanism to further enhance the recommendation accuracy of the proposed scheme (Anand and Bharadwaj 2013; Cao et al. 2008; Park, Park, and Cho 2015). As a further research, we would also like to extend the proposed framework of CARS considering multicriteria contextual information (Yi-Chung 2014) and the dynamic nature of context feature (Hee and Keith 2004) with different feature values for leveraging its recommendation capability to generate recommendations for both individual users as well as groups (Contreras, Maria, and Jordi 2015).

Notes

1. https://www.lucami.org/index.php/research/ldos-comoda-dataset/.

2. https://archive.ics.uci.edu/ml/datasets/.