A novel hybrid approach improving effectiveness of recommender systems

Abstract

Recommender systems support users by generating potentially interesting suggestions about relevant products and information. The increasing attention towards such tools is witnessed by both the great number of powerful and sophisticated recommender algorithms developed in recent years and their adoption in many popular Web platforms. However, performances of recommender systems can be affected by many critical issues as for instance, over-specialization, attribute selection and scalability. To mitigate some of such negative effects, a hybrid recommender system, called Relevance Based Recommender, is proposed in this paper. It exploits individual measures of perceived relevance computed by each user for each instance of interest and, to obtain a better precision, also by considering the analogous measures computed by the other users for the same instances. Some experiments show the advantages introduced by this recommender when generating potentially attractive suggestions.

1 Introduction

The increasing amount of information available on the Web usually involves a lot of no relevant contents so that users have to spend a significant part of their navigation to search more interesting contents. A possible solution to this problem is represented by the use of recommender systems (Konstan and Riedl 2012). Over the years, they have evolved to provide users with more and more potentially useful suggestions about their interests and preferences.

To provide users with personalized suggestions, recommender systems need to collect a large amount of data on past users’ interests and preferences to appropriately represent consolidated and emerging behaviors. In the detail, users’ data can derive from the rates directly provided by them or automatically elicited by the system in monitoring their behaviors (Adomavicius and Tuzhilin 2001; Mobasher et al. 2002) and are usually represented by means of individual users’ profiles.

For the adopted approach, recommender systems can be classified in the following categories (Burke 2007): (i) Content-based (CB) that considers past users’ interests (Lops et al. 2011); (ii) Collaborative Filtering (CF), which realizes a knowledge-sharing environment to find people having similar interests for generating suggestions about items resulting unknown to the users (Breese et al. 1998; Su and Khoshgoftaar 2009); (iii) Demographic, to identify those recommender users belonging to the same demographic niche (Stiller et al. 2010); (iv) Knowledge-based, for inferring user’s needs and references (Trewin 2000). A further category, commonly recognized as the most performing, is that of the hybrid systems (Burke 2002) which combine more approaches to promote mutual synergies and improve effectiveness and efficiency of the recommendation process. Interested reader can find a more comprehensive overview on the matter in Adomavicius and Tuzhilin (2005), Burke (2002), Konstan and Riedl (2012), Manouselis and Costopoulou (2007), Montaner et al. (2004) and Wei et al. (2007).

In particular, the main characteristic of a CB recommender is the evaluation of the user’s interest in a potentially recommendable item only based on similarity measures computed between its features and those of the items stored in his /her profile (Adomavicius and Tuzhilin 2001), independently of the item popularity among other users. However, CB recommenders are unable to consider items unknown to the user, deal with a great number of item features and result to be inefficient in presence of newcomers. On the contrary, CF recommenders suggest an item only when it is popular among users (Shardanand and Maes 1995). CF recommenders are classifiable in (i) memory-based, generally effective and easy to implement (Hofmann 2004; Linden et al. 2003), that use information derived from some type of neighborhood-based process (Herlocker et al. 2002) to identify a suitable set of top-ranked items (Herlocker et al. 1999; Karypis 2001) or (ii) model based, that exploit data mining or machine learning techniques (i.e. Bayesian clustering (Miyahara and Pazzani 2000), latent semantic (Hofmann 2004), neural network (Postorino and Sarné 2011), etc.) or other approaches different from those adopted in the memory-based category. The need to compare users and items (Weng and Liu 2004) implies that CF computational costs are higher than for CB recommenders also for the usual presence of noising and sparse data. To perform more sophisticated prediction processes, such computational costs need to be released, for instance, by clustering users (Mobasher et al. 2002) and /or by pre-computing similarity measures off-line as well as recommendations (Rosaci and Sarnè 2010). Note that the latter strategy might introduce some mismatching because pre-computed suggestions may not consider the latest user’s choices.

In recent years hybrid recommender systems are increased in popularity. In fact, they allow to overcome the weaknesses of a recommendation technique with the strengths of another, although their performances also depend on the way the different components are combined together (Burke 2007). Among hybrid recommender systems, a wide part of them is based on the combination of only CB and CF algorithms due to their high complementarity degree and the excellent performances in terms of effectiveness and efficiency (Burke 2002).

In this scenario a novel hybrid recommender, called Relevance Based Recommender (RBR) is presented. It adapts the same mathematical model proposed and applied in Buccafurri et al. (2004) and Rosaci et al. (2012) to different contexts. In particular, such a mathematical model considers several contributions that assume a different mean in RBR and are differently computed with respect to Buccafurri et al. (2004) and Rosaci et al. (2012). More in detail, RBR exploits the individual measures of the relevance degree of the instances (i.e. a products or information) computed for all the users belonging to a same community. In determining such individual relevance measures, for each instance RBR takes account of the existing interdependencies among the analogous measures of all the other users within the same community and this allows RBR to improve the precision of the relevance measures. This computation involves CB and CF contributions in a unified model able to weight dynamically their reciprocal relevance for generating high-quality suggestions. Furthermore, RBR allows users to preserve their desired privacy degree about the information on their interests and preferences. To test the performance of RBR, some experiments have been performed on simulated and real users. The obtained results show a significant improvement in the effectiveness of the suggestions generated by RBR which seem to meet users’ orientations better than the other tested systems.

The paper is organized as follows. Related work are discussed in Section 2, while Section 3 describes the knowledge representation adopted in RBR. The proposed recommender system is illustrated in Section 4 and some experiments to evaluate the advantages introduced by RBR are presented in Section 5. Finally, in Section 6 some conclusions are drawn.

2 Related work

Hybrid recommenders are increasingly adopted in various contexts and they differ mainly for the nature of the algorithms exploited in generating suggestions and the way they are combined. A great number of hybrid recommenders which combine CB and CF components have been proposed in the literature by exploiting a large variety of “conventional” and “novel” CB and CF techniques (Adomavicius and Tuzhilin 2005; Burke 2002; Manouselis and Costopoulou 2007; Woźniak et al. 2014) or by integrating them into a unified model. More in detail, hybrid recommenders based on CB and CF components can be classified in:

• Linear: CF and CB predictions are first separately generated and then joined by: (i) weighting ratings or votes (Claypool et al. 1999; de Campos et al. 2010; Melville et al. 2002); (ii) selecting those CB and CF predictions appearing as the most interesting on the basis of suitable metrics or priority (Popescul et al. 2001); (iii) using thresholds about the maximum number suggestions to present (Rosaci et al. 2009).

• Fusion: CB features are embedded into a CF algorithm or vice versa. For instance, in Balabanovic and Shoham (1997) and Pazzani (1999) CB techniques analyse users’ profiles and apply CF techniques to refine CB suggestions, while in Salter and Antonopoulos (2006) users profiles, represented as vectors, are indexed by means of a latent semantic and clustered to apply CB techniques.

• Unified: in this category, a global model incorporates both CB and CF approaches, e.g. rule based systems (Liu and Liou 2011), probabilistic approaches (Schein et al. 2002), learning machines (Gunawardana and Meek 2009), mobile learning agents (Rosaci and Sarnè 2013).

In the context described above, a well known hybrid recommender which linearly combines CB and CF suggestions is the Content-Boosted Collaborative Filtering (Melville et al. 2002) (CBCF). It recommends movies to users based on their past ratings, where each rating is provided on six textual classes. A user-rating matrix, which is very sparse, is built from the users’ ratings. The CB predictor adopts a bag-of-words naive Bayesian text classifier (Mitchell 1997) trained by the user’s ratings and returns a pseudo user-rating vector containing his /her actual ratings. All the pseudo user-rating vectors are joined to form a dense pseudo-ratings matrix, that is used to make CF predictions by exploiting a pure CF neighborhood-based algorithm (Herlocker et al. 1999), while the similarities among users are computed by means of a Pearson correlation.

To improve the prediction accuracy, context-aware strategies can be applied to enrich profiles with significant data. For example, MASHA (Rosaci and Sarnè 2006) and MUADDIB (Rosaci et al. 2009) are two XML agent-based CB and CF hybrid recommenders that in their predictions adapt their behaviors to consider both users’ profiles and exploited devices. MASHA presents three main characteristics: (i) it constructs a global user profile by exploiting data coming from the different devices exploited by the user and providing them with different relevance degrees; (ii) it exploits two different agent types to build such a profile. The former, called client agent is associated with each device exploited by a user and it is able to manage only information deriving from the use of just that device; the latter, called server agent, is associated with the user and collects information coming from all the user’s devices; (iii) it generates both CB and CF recommendations on the site-side by using a third agent type, called adapter agent, associated with each visited Web site. Then each client agent, which runs on the device, performs only a relatively light task for constructing its local user’s profile, while the global one is built by the more powerful server agent and the recommendations are generated in a centralized manner by the site adapter agent.

MUADDIB is a recommender that, with respect to MASHA, adopts a more efficient distributed architecture and a more effective recommendation algorithm. In particular, the MUADDIB platform exploits another type of agent, called recommender agent. Each recommender agent affiliates users similar for interests and provides to pre-compute CB and CF suggestions for them based on their global profiles and on the catalogs of the Web sites affiliated with the platform. When a user is visiting a Web site affiliated with MUADDIB, his /her device agent provides the site agent with the information for contacting the recommender agents where its visitor is affiliated to in order to receive their best personalized suggestions for him /her. Note that MUADDIB and MASHA can work as traditional hybrid recommender systems without considering the exploited devices in generating recommendations. Moreover, similarly to RBR, they significantly preserve users’ privacy by performing a consistent part of their computations on the client-side, while MUADDIB differs from them for the adoption of a full distributed architecture.

Computational costs of hybrid recommenders, which integrate CB and CF components by adopting a linear or a fusion modality, depend mainly on the computational costs of their CB and CF components. For the CB component such costs depend on the numbers of items (m) and their features (f), which give a complexity of $\mathcal {O}(f \cdot m^{2})$. CF algorithms are more expensive than CB methods because they have to compare all the items and their features for all the n users, the cost, in the worst case, is $\mathcal {O}(f \cdot m \cdot n)$. The usual high sparsity degree of users’ profiles makes this cost closer to $\mathcal {O}(f \cdot (m+n))$. In the cases of MASHA and MUADDIB, their costs are respectively $\mathcal {O}(n^{2} \cdot c)$ and $\mathcal {O}(c+p)$, where c represents the number of associated categories and p that of the partitions. On the contrary, if there is a a great number of users and items, the item-to-item CF algorithm (Linden et al. 2003) compares accessed items to similar items to search those accessed together. In this way, its computational cost depends only on the number of visited items. To save computational resources, some CF algorithms exploit clustering processes (Berkhin 2006; Jain et al. 1999) to reduce the searching space and /or compute similarities off-line. Specific analysis are required to know the computational cost of unified hybrid recommenders. In fact, their computational complexities cannot be inferred from those of the CB and CF components given the impossibility to identify the respective costs.

The proposed unified hybrid recommender RBR differs from all the cited systems mainly for the generation of the suggestions (see Section 4). Indeed, it exploits users’ relevance measures of each instance (i.e. a product or information) computed by taking account of the existing interdependencies among all the analogous measures. In the author’s knowledge, this is a unique characteristic among the recommenders and RBR can evaluate more precisely the relevance of each instance into a users’ community. Consequently, RBR allows the most interesting instances to be identified better then other recommender systems. This is shown in Section 5 where RBR is compared with CBCF (Melville et al. 2002), MASHA (Rosaci and Sarnè 2006) and MUADDIB (Rosaci et al. 2009). Finally, the better performances of RBR require significant computational costs that can be optimized by clustering users and pre-computing suggestions as described in Section 4.2.

3 The knowledge representation

The knowledge representation adopted in RBR is mainly based on the use of: (i) a common Dictionary ($\mathcal {D}$) storing those categories and instances recommendable by RBR; (ii) an individual User Profile (UP) storing those categories and instances of $\mathcal {D}$ of interest for the user on the basis of his /her monitored Web activities (for example, by exploiting one or more software agents running on his /her clients (Rosaci et al. 2013; Rosaci et al. 2009)). Other data structures used by RBR to store data temporarily and generated recommendations will be described in Section 4.1.

The Dictionary $\mathcal {D}$ is organized in categories and instances and it is periodically updated to consider new categories and instances of interest for the users. Each Dictionary category consists of a set of instances associated with it and each instance belongs to only one category. More in detail, each category c /instance i is identified by a pair of attributes (Cid _c ,Cd _c )/(Iid _i ,Id _i ), where Cid _c /Iid _i is a unique code identifying the category /instance and Cd _c /Id _i is its textual description. The Dictionary is implemented by a unique XML-Schema, shown in the Appendix.

Interests and preferences of each user with respect to the categories and the instances stored in $\mathcal {D}$ are collected in an individual user profile associated with him /her and implemented by a XML-Schema. Let u be a user and let UP ^u be his /her profile (Figure 1). The information stored in UP ^u are:

• Delta (δ ^u): a coefficient autonomously set by u in $]0,1[ \in \mathbb {R}$ and used in computing $I{W^{u}_{i}}$ measures (see below);

• Category Set ($C{S^{u}_{c}}$): a set where each element is associated with a category c of interest for u and in turn consists of:

  • Category Identifier (Cid ^c): the code associated with c in $\mathcal {D}$;

  • Category Privacy ($C{P^{u}_{c}}$): a flag set by u to 0/1 to make public /private his /her interest in c. Note that if a category is set as private then all its associated instances become private;

  • Last Category Access ($LC{A^{u}_{c}}$): the date of the last access of u to an instance belonging to the category c;

  • Category Weight ($C{W^{u}_{c}}$): a measure of the interest of u about c (see below) which ranges in $[0,1] \in \mathbb {R}$;

  • Instance Set ($I{S^{u}_{c}}$): a set where each element represents an instance i belonging to the category c visited by u and in turn consists of:

    • •  Instance Identifier (Iid ⁱ): the code associated with the instance i in $\mathcal {D}$;

    • •  Instance Privacy ($I{P^{u}_{i}}$): a flag that u sets to 0/1 to make public /private his /her interest in i;

    • •  Last Instance Access ($LI{A^{u}_{i}}$): the date of the last access of u to i;

    • •  Instance Weight ($I{W^{u}_{i}}$): a measure of the interest of u about i (see below) which ranges in $[0,1] \in \mathbb {R}$;

    • •  Individual Relevance (${\mu ^{u}_{i}}$): a coefficient, ranging in $[0,1] \in \mathbb {R}$, which takes account of the individual relevance of i for u with respect to the other instances of interest for u (see Section 4).

• User Weight (W): a set of coefficients exploited by u in computing his /her instance weight measures (see below). Each element consists of the user identifier of j (i.e. Uid _j ) and a value ${W^{u}_{j}}$, belonging to $[0,1] \in \mathbb {R}$, to weight the information provided by the user j to the user u about an instance.

Fig. 1

The XML elements of the User Profile

IW and CW measures are computed on the whole user’s Web history. To measure the user’s interest in the content of a Web page, several approaches have been proposed in the literature. In particular, in Chan (2000) the authors suggest to consider the time spent by a user on a page, its length and a possible score provided by the user to show his /her interest level about that Web page. In Parsons et al. (2004) too, the visiting time of a Web page is the main parameter considered in evaluating the user’s interest in the instances present therein, while in Rosaci and Sarnè (2006) the typology of the device exploited in its access is also taken into account. All these approaches evaluate the user’s interest in an instance belonging to a Web page by using the time spent in visiting that Web page.

In RBR, the interest of the user u about an instance i (i.e. $I{W^{u}_{i}}$) set by him /her as public is measured by two factors: (i) his /her whole past Web history in accessing i ; (ii) the time t (measured in seconds) spent by u in his /her actual visit to the page containing i . Each user can decide how to weight these two components of $I{W^{u}_{i}}$ by setting autonomously the coefficient δ ^u, a real value belonging to ]0;1[, to tune the “memory” behavior of $I{W^{u}_{i}}$. In particular, to calculate the new $I{W^{u}_{i}}$ its actual value is weighted by (1−δ ^u), while the new contribution to $I{W^{u}_{i}}$, due to the current visit of the user u to i, is weighted by δ ^u. Furthermore, when $I{W^{u}_{i}}$ is updated, its current value is decreased based on its age. This latter is computed as difference (in days) between the dates of the present and last visit to i performed by u. To this purpose, the function $\mathcal {F}(current,past)$ is exploited. Current is the actual date and past is assumed to be equal to the value of $LI{A^{u}_{i}} \in UP^{u}$, associated with the instance i. More in detail, the contribution provided by the current value of $I{W^{u}_{i}}$ is set to 0 when the last access is older than a year. Formally, $I{W^{u}_{i}}$ is calculated as:

$$ I{W^{u}_{i}} = (1 - \delta^{u}) \cdot \mathcal{F}(current,past) \cdot I{W^{u}_{i}} + \delta^{u} \cdot t $$

(1)

where

$$ \mathcal{F}(current,past)=\left\{ \begin{array}{ll} 1 - \frac {current-past}{365}, & \text{if} (current-past) \leq 365 \\ 0, & \text{otherwise} \\ \end{array} \right. $$

(2)

In this way a reasonable priority to new items is given. Then $LI{A^{u}_{i}}$ is updated to the current date and the measure of the interest of u in a public category c (i.e $C{W^{u}_{c}}$) is computed as the average of all the IW measures of the instances belonging to c and set as public by u. Finally, $LC{A^{u}_{c}}$ is set to the most recent date stored in the $LC{I^{u}_{i}}$ parameters associated with the instances belonging to c.

4 The relevance based recommender

This section describes the proposed unified hybrid Relevance Based Recommender (RBR) system. This tool exploits and adapts the mathematical model described and applied in Buccafurri et al. (2004) and Rosaci et al. (2012) in order to generate effective recommendations.

As described in the Introduction, RBR is based on the computation of a measure of relevance degree for each recommendable instance (i.e. a product or information) for each affiliated user. The RBR peculiarity is that each relevance measure takes into account explicitly the existing interdependencies among the analogous measures of all the other users by means of simple linear systems of equations. Therefore, each relevance measure permeates all the other relevance measures by assuming also a “social” dimension that makes possible to obtain more precise measures.

More in detail, let u be a user belonging to a community of n users, called $\mathcal {A}$. To build his /her opinion about an instance i (called instance relevance) the user considers (i) the measure of how much i is significant for him /her (called individual relevance), based on his /her personal point of view, and (ii) the measure of how much i is important for the other users belonging to $\mathcal {A}$ (called social relevance), by exploiting the instance relevance measures provided by the other users of $\mathcal {A}$. Moreover, RBR allows the contributions due to the individual and social relevance measures to be dynamically and individually weighted for each user.

More formally, let ${\rho _{i}^{u}}$ be the measure of the instance relevance that the user $u \in \mathcal {A}$ has for a given instance i. It is obtained by combining the individual opinion (${\mu _{i}^{u}}$) of u and a social contribution (${\gamma _{i}^{u}}$) consisting of the relevance measures of the instance i provided to u by each user $j \neq u \in \mathcal {A}$. These two components are combined in a unique measure (i.e. ${\rho _{i}^{u}}$) by means of the real coefficient ${\alpha _{c}^{u}}$ by taking into account the expertise level of u in $\mathcal {A}$ about the category c, which the instance i belongs to. In particular, a high value of α _c implies a greater relevance of μ with respect to γ in calculating the measure of the relevance ρ for an instance belonging to the category c. Therefore, the instance relevance ${\rho _{i}^{u}}$ can be generally expressed as a function $\mathcal {G}$ depending on ${\mu _{i}^{u}}$, ${\gamma _{i}^{u}}$ and ${\alpha _{a}^{c}}$ (i.e., ${\rho _{i}^{u}}=\mathcal {G}({\mu _{i}^{u}}, {\gamma _{i}^{u}}, {\alpha _{c}^{u}})$), where ρ, μ, γ and α are real values belonging to [0, 1]. In the following, μ, γ and α will be described in detail.

The individual relevance.

The individual relevance ${\mu ^{u}_{i}}$ of an instance i is computed by u based on the Interest Weight measures IW stored in his /her profile UP ^u. The IW measures are not directly available because they need to be (i) updated to the current date by using the function $\mathcal {F}$ (with $past=LI{A^{u}_{i}}$) and (ii) normalized with respect to the sum of the IW measures of all the m instances stored in UP ^u that belong to the same category c of i. Therefore, the value ${\mu ^{u}_{i}}$ for the generic instance i is computed as:

$$ {\mu^{u}_{i}}=\frac {I{W^{u}_{i}}} {\sum\limits_{r=1}^{m} I{W_{r}^{u}}} $$

(3)

The social relevance

This contribution to ${\rho ^{u}_{i}}$ is provided by ${\gamma ^{u}_{i}}$ as the average of the ρ measures of relevance of i required by u to each of the other (n−1) users belonging to his /her community $\mathcal {A}$. In computing ${\gamma ^{u}_{i}}$, each exploited relevance measure is weighted by the reliability that u assigned to the user provided it. Therefore, ${\gamma ^{u}_{i}}$ represents the measure of the relevance of i within $\mathcal {A}$ as it is perceived by u. More formally, ${\gamma ^{u}_{i}}$ is computed by the user u as:

$$ {\gamma^{u}_{i}}=\frac {1} {n-1} \cdot {\sum\limits_{j=1, \forall j \neq u}^{n-1} {W^{u}_{j}} \cdot {\rho^{j}_{i}}} $$

(4)

where ${W^{u}_{j}}$ (a real value ranging in [0, 1]) is the measure of the reliability of j computed by u to weight the relevance measure provided by j. It is based on the concordance degree between the ρ measures of u and j for the instance i. In particular, each time that u exploits an instance relevance measure provided by j, he /she also computes his /her ${W^{u}_{j}}$ value by taking account of the average of all the latest d (an integer value that is a system parameter) differences among the instance relevance measures computed by u and those provided by the user j to him /her. Note that each newcomer user has initially the maximums reliability, i.e. W = 1. Formally, ${W^{u}_{j}}$ is computed as:

$$ {W^{u}_{j}}=1- \frac {1} {d} \cdot \sum\limits_{i=1}^{d}\left| {\rho^{u}_{i}} - {\rho^{j}_{i}} \right| $$

(5)

For example, when u needs to evaluate the social relevance measure of i, belonging to c, with respect to a community of four users, he /she receives three “opinions” from the users j ₁, j ₂ and j ₃ (Fig. 2). Such opinions are represented by their instance relevance measures about the instance i (i.e. $\rho ^{j_{1}}_{i}$, $\rho ^{j_{2}}_{i}$ and $\rho ^{j_{3}}_{i}$). By assuming ${W_{j}^{u}}=1.0~\forall j$, the social relevance ${\rho _{i}^{u}}$ computed by u is ${\gamma _{i}^{u}}=(1 \cdot 0.8 + 1 \cdot 0.9 + 1 \cdot 0.4)\big /(4-1)=0.7$.

Fig. 2

The social relevance computed by the user u based on the perceived relevance of the users j ₁, j ₂ and j ₃

The ${\alpha _{c}^{u}}$ coefficient

This coefficient measures the expertise level of the user u on the category c which the instance i belongs to, within his /her community. It is used to automatically weight the social and the individual relevance contributions in computing the relevance measure of i. Therefore, a different α has to be computed for each of the p categories stored in the user profile of u with respect to the maximum Category Weight measure (CW ^max) within his /her community. However, each CW measure has to be updated to its latest LCA date by the function $\mathcal {F}$. More formally, for the category c the coefficient ${\alpha _{c}^{u}}$ is computed by u as:

$$ {\alpha_{c}^{u}}=\frac {C{W_{c}^{u}}} {CW^{max}_{c}} $$

(6)

The instance relevance

Finally, for a user u the instance relevance measure ${\rho _{i}^{u}}$ of an instance i takes account of both the individual (${\mu _{i}^{u}}$) and the social (${\gamma _{i}^{u}}$) relevance of that instance suitably weighted by u on the basis of his /her expertise level (${\alpha _{c}^{u}}$) on the category c which i belongs to. The function $\mathcal {G}$ of the (4) has the form:

$$ {\rho_{i}^{u}}={\alpha_{c}^{u}} \cdot {\mu_{i}^{u}}+(1-{\alpha_{c}^{u}}) \cdot {\gamma_{i}^{u}} $$

(7)

that, by taking account of the (3), (4) and (6), becomes:

$$ {\rho_{i}^{u}}=\frac {C{W_{c}^{u}}} {CW^{max}_{c}} \cdot \frac {I{W^{u}_{i}}} {\sum\limits_{r=1}^{m} I{W_{r}^{u}}} +\left(1-\frac {C{W_{c}^{u}}} {CW^{max}_{c}}\right) \cdot \frac {1} {n-1} \cdot {\sum\limits_{j=1}^{n-1} {W^{u}_{j}} \cdot {\rho^{j}_{i}}} $$

(8)

where m and n are respectively the numbers of instances belonging to the category c and the number of users belonging to $\mathcal {A}$.

Therefore, for all the n users belonging to $\mathcal {A}$ the instance relevance measures of i are obtained by solving a system of n linear equations in n variables (in the form of the (8)). This system is equivalent to that described in Buccafurri et al. (2004) and Rosaci et al. (2012) and admits only one solution. To compute the instance relevance measures of m instances for n users, m linear systems of n equations in n variables have to be solved.

4.1 The RBR algorithm

The RBR algorithm runs periodically in order to pre-compute updated and supposedly interesting suggestions for its users. For each user RBR suggests to him /her the first M most relevant and unvisited instances belonging to the first most attractive P categories for that user. Note that the two system parameters M and P are two positive integer values that have to be considered as two upper bounds. In presence of newcomer users and /or too many categories and instances set as private then RBR might not be able to select /identify all the desired categories and instances. Furthermore, note that usually M < < m and P < < p, where m and p are the overall numbers of instances and categories stored into the dictionary $\mathcal {D}$.

The RBR algorithm is implemented by the function RBR ( ) that in turn calls the functions Relevance ( ) and Recommendations ( ). The first one returns the most relevant instances for each category of interest with respect to the instances and the categories in $\mathcal {D}$ and the user community $\mathcal {A}$, while the other function provides to extract iteratively the most relevant M suggestions for each user. The algorithm implementing RBR is described in the form of pseudo-code in Fig. 3. The function RBR ( ) receives in input the list of the n users belonging to $\mathcal {A}$ and the integers P and M and returns in output the set $RSet_{\mathcal {A}}$ that is the set of the recommendation lists computed for each user of $\mathcal {A}$. Initially, the function RBR ( ) receives from each user his /her (i) “public” CW and IW measures (updated to the current date by the function $\mathcal {F}$ with past respectively set to LCA and LIA) and (ii) the weights W. Such values are stored in a data structure DS, associated with that user, belonging to the set DSSet collecting all these users’ data structures. To realize the two main tasks of the algorithm, first the function Relevance ( ) is called and after, for each of the n users of $\mathcal {A}$, the function Recommendations ( ) runs to generate his /her recommendation list. Then each recommendation list is joined to the set $RListSet_{\mathcal {A}}$ returned by RBR.

Fig. 3

The Relevance Based Recommender Algorithm

The first function Relevance ( ) receives in input the list of users of $\mathcal {A}$ and the set DSSet with the integers P and M and provides in output the set $RSet_{\mathcal {A}}$ storing, for each category of $\mathcal {D}$, the instances mostly significant in $\mathcal {A}$ computed on the basis of the individual public measures of interest (i.e. CW and IW) provided by each of the n users of $\mathcal {A}$. For each one of the n users of $\mathcal {A}$ the function Relevance ( ) calls the function SelectTop ( ). For each user $j \in \mathcal {A}$ this function receives in input the same user j, his /her associated data structure DS _j and the integers P and M previously described, while its output consists of the set ISet _j . The output set ISet _j stores the first M top-ranked public instances, for each of the first P top-ranked public categories of interest for j, associated with their IW value computed by j. Then the union of this set with the global set $ISet_{\mathcal {A}}$ is performed. The set $ISet_{\mathcal {A}}$ collects all the top-ranked instances in $\mathcal {A}$, for each category of $\mathcal {D}$, associated with a global IW value obtained by summing all the individual IW contributions. Let k be the number of different instances stored in $ISet_{\mathcal {A}}$, with k ≤ m, and for each of them the function InstanceRelevance ( ) is called.

The function InstanceRelevance ( ) performs the most expensive computation in RBR because it has to solve the linear system required by the mathematical model previously described for each of the k instances stored in $ISet_{\mathcal {A}}$. Let RSet _i and $RSet_{\mathcal {A}}$ be respectively the set storing the instance relevance measures computed for the instance $i \in ISet_{\mathcal {A}}$ (i.e. the ρ _i values of each user belonging to $\mathcal {A}$) and the set union of all the RSet of each instance belonging to $ISet_{\mathcal {A}}$. For each instance $i \in ISet_{\mathcal {A}}$ the function InstanceRelevance ( ) receives in input the instance i and the global set DSSet described above and returns the set RSet _i that contributes to form the global set $RSet_{\mathcal {A}}$. Finally, $RSet_{\mathcal {A}}$ is returned by the function Relevance ( ).

The second main function is Recommendations Literal( ) which selects the best M suggestions for a target user. This function receives in input a target user (i.e. j), his /her associated data structures (i.e. DS _j ), the set of instance relevance measures $IRSet_{\mathcal {A}}$ previously computed by the function Relevance ( ) and the already introduced integers P and M. The output returned by this function is a list of the M unvisited instances potentially most attractive for the user j. They are selected as described in the following. The function Visited ( ) receives the user j and his /her associated DS _j from which selects all the visited instances belonging to the P top-ranked categories of interest for j and that are returned in output in the list VList _j (for a newcomer user this set will be obviously empty). Then (i) the function Prune ( ) is called to delete from the set $RSet_{\mathcal {A}}$ all the instances visited by j and stored into the list VList _j , the remaining instances are returned in UVSet _j , (ii) the function Sort ( ) orders in RecList _j the instances of UVSet _j in a decreasing way based on their relevance measures and (iii) the function Extract ( ) returns in RecList _j the only first M unvisited instances that are the recommendations computed by RBR for j. Finally, RecList _j is returned by Recommendations ( ).

4.2 The RBR computational complexity

Let n, m and p be the overall number of considered users and those of instances and categories belonging to the dictionary $\mathcal {D}$, respectively. To compute the perceived instance relevance within a community of n users RBR has to solve a system of n linear equations in n variables that admits only one solution (Buccafurri et al. 2004; Rosaci et al. 2012). The resulting linear system is dense and if solved by using classical direct methods its computational complexity in time is of $\mathcal {O}(n^{3})$. To determine the perceived instance relevance measures of all the m instances belonging to $\mathcal {D}$, RBR requires to solve m systems of n linear equations in n variables with a complexity in time of $\mathcal {O}(m \cdot n^{3})$.

This analysis shows that RBR has a significant high cost but there some elements to assess it correctly. The first considered element to limit the computational cost takes account of users’ similarities by a clustering process, if there is a wide number of users. In RBR the adopted user profile allows an easy and effective clustering process. Therefore, let $\overline {n}$ be the average number of users for cluster, with $\overline {n}<<n$. The overall number of clusters will be approximatively $n/\overline {n}$. For each instance, RBR has to solve $(n/\overline {n})<n$ linear systems of $\overline {n}$ equations in $\overline {n}$ variables with a computational complexity of $\mathcal {O}(\frac {n}{\overline {n}} \cdot \overline {n}^{3}) = \mathcal {O}(n \cdot \overline {n}^{2}) < \mathcal {O}(n^{3})$. Furthermore, let M be the number of top-ranked instances for each considered category of interest and P the number of top-ranked categories of interest for which, in the worst case, RBR has to compute the recommendations. Commonly, it results P<<p and M<<m and therefore, in the worst case, the maximum number of instances for which their relevance measures are computed will be q = M⋅P, with q<<m. In this way, the complexity of RBR will be $\mathcal {O}(q \cdot n \cdot \overline {n}^{2}) << \mathcal {O}(m \cdot n^{3})$.

The other element is the cost C to perform a clustering. In the previously assumed hypothesis, the overall cost of this recommender will be $\mathcal {O}(C + q \cdot n \cdot \overline {n}^{2})$, where C depends on the particular clustering algorithm adopted. Finally, such recommendations are computed off-line for each user and then they can be provided to him /her in a constant time without delay for the target user. Therefore, under the usual conditions, RBR runs with a computational cost that is significantly lower than in the worst case.

5 Experiments

In this section, two different experiments to test the effectiveness of RBR in generating potentially interesting recommendations are presented. To this aim, the performances of RBR have been compared with those of other three recommender systems, namely MUADDIB, CBCF and MASHA described in Section 2. These competitors have been implemented in accordance with their descriptions respectively provided in Rosaci et al. (2009), Melville et al. (2002) and Rosaci and Sarnè (2006). Moreover, MUADDIB and MASHA have been tested without considering their adaptivity with respect to the exploited users’ devices.

The first experiment refers to more sets, different for size, of simulated users while the second one refers to the data of 80 real users. Both the experiments have required: (i) a common Dictionary consisting of 20 categories (i.e. p = 20), each one provided with 90 instances (i.e. m = 90), implemented by a unique XML Schema shown in the Appendix; (ii) 20 XML Web sites (Fig. 4), each one dealing with only three categories of interest, belonging to the common dictionary, and with 40 instances for category; (iii) 3 top-ranked categories (i.e. P = 3) and 5 top-ranked instances (i.e. M = 5); (iv) the system parameter d of (5) has been reasonably set to 5. The first 10 Web sites have been used for generating /building the user profiles (see Section 3) of the simulated /real users, while the other 10 Web sites have been exploited for measuring the performances of the tested recommenders. For sake of simplicity, all the information stored in the user profiles have been considered as public.

Fig. 4

The RBR Web site 12

For each simulated /real user u and for the g-th tested recommender system (with g = 1,⋯4) a set of recommendations has been generated and stored in a different list ${L_{g}^{u}}$ consisting of the suggestions $l_{g,s}^{u}$ (with s = 1,⋯ ,M). Then, the recommendations contained in ${L_{g}^{u}}$ have been divided into two lists of good recommendations (denoted by ${G_{g}^{u}}$) and bad recommendations (denoted by ${B_{g}^{u}}$), based on their supposed relevance for u. More in particular, the recommendations having relevance greater or equal than 0.5 have been assigned to ${G_{g}^{u}}$, while those with a relevance smaller than 0.5 have been inserted into ${B_{g}^{u}}$. To measure the quality of each recommendation generated for u, a rate $r_{g,s}^{u}$ (i.e. an integer ranging in [0, 5]) has been computed in the first experiment based on the information stored in the simulated profile or directly assigned by the real user in the other experiment. If, for u and for each suggestion $l_{g,s}^{u} \in {G^{u}_{g}}$, the rate $r_{g,s}^{u}$ is greater or equal than 3, it is considered as a true positive and inserted in the list $T{P_{g}^{u}}$ containing all the true positives of ${L_{g}^{u}}$. If $r_{g,s}^{u}$ is smaller than 3, it is considered as a false positive and inserted in the list $F{P_{g}^{u}}$ of that user. Finally, for u and for each suggestion $l_{g,s}^{u} \in {B^{u}_{g}}$, if the rate is greater or equal than 3, the suggestion is considered as a false negative and inserted in the list $F{N_{g}^{u}}$. After the first phase necessary to generate /build the user profiles, in both the experiments only the first 100 recommendation sessions have been generated by each considered recommender (i.e. about 500 suggestions for recommender).

The performances of the recommenders have been evaluated by means of the standard measures Precision (P), Recall (R) and F-measure (F) (van Rijsbergen 1974). Precision can be interpreted as the probability that a suggestion is considered relevant by the user, while Recall can be considered as the probability that it is relevant and the F-Measure represents their harmonic mean. Formally, for the user u and for the g-th recommender system ${P^{u}_{g}}$, ${R^{u}_{g}}$ and ${F^{u}_{g}}$ are computed as:

$$ {P^{u}_{g}}=\frac{|T{P^{u}_{g}}|}{|T{P^{u}_{g}} \cup F{P^{u}_{g}}|} $$

(9)

$$ {R^{u}_{g}}=\frac{|T{P^{u}_{g}}|}{|T{P^{u}_{g}} \cup F{N^{u}_{g}}|} $$

(10)

$$ {F^{u}_{g}}=\frac{2*{R^{u}_{g}}*{P^{u}_{g}}}{{R^{u}_{g}}+{P^{u}_{g}}} $$

(11)

Furthermore, the Average Precision $\overline P~^{u}_{g}$ (resp. Average Recall $\overline R~^{u}_{g}$ and Average F-Measure $\overline F~^{u}_{g}$) of each system is defined as the average of the ${P^{u}_{g}}$ (resp. ${R^{u}_{g}}$ and ${F^{u}_{g}}$) values of all the considered users.

Simulated users

For the first experiment three sets of 250 (S ₁), 500 (S ₂) and 1000 (S ₃) simulated users (and their profiles) have been built. Moreover, other 10.000 simulated users (and their profiles) have been generated and distributed on 20 clusters by means of a partitional clustering algorithm by using the Jaccard similarity measure on the basis of their generated profiles. To this purpose, each user has been represented by a pattern consisting of CW values (normalized among them) of the 20 exploited categories of interest considered in the experiment. The parameter δ (see Section 3), to tune the memory in computing the interest weights has been set to a reasonably value of 0.3.

To realize this experiment, the individual interests of the simulated users have been generated. Two different and complementary activities have been performed to this purpose. The first one refers to order into the dictionary $\mathcal {D}$ all the instances of each category based on their similarity. In this way, similar instances have sequential identifier codes. The other one refers to provide each user with a set of “behaviors”. In particular, each behavior consists of a set of categories and a little share of their instances described by means of a domain identified with an initial and an ending instance identifier code. Such behaviors result to be partially overlapped and, therefore, the same category and /or set of instances can be present more times for the same user. This allows each user to be provided with different levels of interest in the categories and in the instances of $\mathcal {D}$ based on the number of time that a category or an instance is repeated. Then, for a simulated user his /her choices of the site instances and his /her interest in the suggested instances are simulated based on assigned behaviors.

In terms of results (Table 1) RBR is always the best performer for all the considered sets/clusters of users. The advantage of RBR in terms of Average Precision (i.e., Average Recall and Average F-measure) ranges in 9 ÷ 18 % (i.e., 12 ÷ 15 % and 11 ÷ 17 %) with respect to the second best performer that is always MUADDIB. Moreover, the performances of RBR are almost similar when the size of the set increases, differently from the other tested recommender systems.

Table 1 The $\overline P~^{u}_{g}$/$\overline {R^{u}_{g}}$/$\overline {F^{u}_{g}}$ measures obtained in the case of simulated users for each recommender system, for the three sets S ₁, S ₂, S ₃, for the best cluster ($\mathcal {C}^{*}$) and in average on all the clusters ($\overline {\mathcal {C}}$)

Real users

Firstly the profiles of the 80 real users have been built by exploiting the first 10 Web sites for a three-week period. In this phase, real users set the parameter δ individually (0.42 in average with respect to all the real users). The quality of the recommendations generated by RBR and by the other recommender systems for supporting the users have been tested on the other 10 Web sites and individually ended when all the tested recommenders generated 100 recommendation lists, as above specified. The overall time required by this phase has been of about nine weeks with a minimum of about six weeks (this time varied for each of the real user based on his /her time spent on the platform).

The results (Table 2) show that in terms of Average Precision (resp. Average Recall, Average F-measure) the advantage of RBR with respect to the second best performer (i.e. MUADDIB) is 9 % (i.e., 13 % and 11 %), which substantially confirms the results of the first experiment.

Table 2 The $\overline P~^{u}_{g}$/$\overline {R^{u}_{g}}$/$\overline {F^{u}_{g}}$ measures obtained from each recommender system for the set of real users

Discussion

The experimental results show that the performances of RBR are better than the other tested recommenders, in terms of average precision, average recall and average F-measure. It is possible to argue that the advantage of RBR with respect to the other recommender systems can be attributed to its peculiarity, i.e. the dynamic interdependencies among all the computed instance relevance measures, as described in Section 4. In this way, RBR has the opportunity to identify accurately the most interesting instances to be recommended. Moreover, another characteristic behavior shown by RBR is that the performances are almost uniform when the population size becomes greater, while those of the other recommender systems change significantly.

6 Conclusions

In this paper a recommender system, called Relevance Based Recommender (RBR), able to generate personalized high quality suggestions potentially attractive for the users has been presented. For each user, RBR computes precise single relevance measures of products or information of interest for him /her. These measures takes account of the interdependencies existing among all the users’ relevance measures of such instances in order to improve their precision. Then such measures are exploited by RBR to generate personalized recommendations. Some experimental evaluations performed on simulated and real users have shown that RBR provides better performances in terms of effectiveness then some other tested recommender systems.

In the next future, researches will be addressed to improve the RBR efficiency in terms of computational complexity and investigate on a possible distributed implementation of the RBR algorithm.

Appendix

The Section Appendix presents the two XML-Schema of the Dictionary and of the User Profile described in Section 3.

The Dictionary XML-Schema

The User Profile XML-Schema