D. Anand, KK Bharadwaj/ Expert Systems with Applications 38(2011)5101-5109 with a set to a value which results in the least mae this scheme of The uss for user uand item i is defined as estimating o would hereafter be referred to as the fixed- scheme User specific sparsity measure 3. Novel schemes for estimating parameter a where nu is the number of items rated by user u A framework combining predictions from local and global 3. 1.3. User and item specif Varsity measures neighbors was discussed in Section 2. The parameter o serves Sometimes the superiority of global predictions over local ones to adjust the weight that we give to global neighbors with re- so depend on the type of items rated by the user For example the ards to the weight that we give to the local neighbors. When local neighbors for a user, with eclectic tastes who has rated sev- the ratings matrix is dense then generally the local neighbor eral items which have not been experienced by a large majority hood set is rich enough to enable prediction for the activ of users, may be scarce. When the local neighborhood is meager. user,in which case the predictions from local neighborhood global neighbors can contribute to improvement in accuracy of should be weighed more. However, when the ratings matrix predictions. This means that the sparsity measure should take into is sparse, the local neighborhood set generated may account not only the active user, but also the item for which the lead to low qua commendations. and therefore it need rating needs to be predicted. Three sparsity measures, which cap- to be enriched globally similar neighbors and for better ture sparsity at user-item level, are introduced belov predictions In this section we propose several sparsity measures whic Local global rat enable the global neighbors to be weighed according to the active One simple measure is to find the of number of local er and the item whose vote needs to be predicted. To the best of neighbors to the number of global bors who have rated our knowledge there has been no previous attempt at quantifying the item. It is to be noted that the r of global neighbors the various facets of sparseness in data and to use them in the pre- always exceeds or is equal to the number of local neighbors. diction process. The "sparsity problem"in collaborative filtering This is due to the fact that simd(x, y)> sim(x, y). The LGR for a refers to inability to find a sufficient quantity of good quality user u and item i is defined as: neighbors to aid in the prediction process due to insufficient over lap of ratings between the active user and his neighbors. This can LGR(u,i=1-Luil (10) lappen when the ratings matrix is sparse, or the number of users anticipating is not large. Even when the data is dense enough to where Lui is the set of local neighbors of user u who have rated item i, allow quality predictions for most users, some users may not have Gui is the set of global neighbors of user u who have rated item i. rated enough items or may have rated items not rated by most User-item specific sparsity measure(UIS1)The UISI measure people, with the result that such users get poor quality predictions bases the sparsity measurement on the ratio of number of local sers whose local neighborhood set is sparse can thus be aided by neighbors who have rated a particular item to the total number using predictions from the global neighborhood set. Thus intui- of people who have rated the item i.e. the UiSl for a user u and tively the value of o should depend on the user and the item whose item I rating is to be predicted. The proposed work introduces several UIS1(u, i)=1 (11) estimates for a, which captures the various aspects of sparseness in the data where Ni is the set of users who have rated item i 3. 1. Individual sparsity measures User-item specific sparsity measure2 (UIS2)The UIS2 measure In this section we introduce several sparsity measures namely. computation is founded on the ratio of number of local neigh- OS (overall sparsity measure), USS(user specific sparsity measure). bors who have rated a particular item to the total number of LGR (local global ratio), UISI (user item based sparsity measure 1) users in the local neighborhood set ie. the UIS2 for a user u and UiS2 (user item based sparsity measure 2). and item i is defined as: 3.1.1. Overall sparsity measure(oS) The overall sparsity measure captures the level of sparsity in the where Lu is the set of local neighbors for user u. entire rating matrix. This sparsity measure is universal i.e. the a computed is fixed for all users. The overall sparsity measure 3. 2. Unified measure of sparsity(UMS)-GA approach defined as The various measures of sparsity, described in Section 3, encap- Overall sparsity measure =1 nUsers items (8) sulate the diverse factors that come into play. when deciding the extent to which the local and global predictions should influence where nR is the total number of ratings which exist, nUsers is the he final prediction. The performance of each sparsity measure is total number of users in the system and nitems is the total number ataset dependent and hence the quality offered, varies across sev eral datasets. The sparsity measure, which best reflects the balance items between local and global predictions may differ from user to user and also may evolve over time. The idea of unifying the various 3. 1.2. User specific sparsity measure(USS) sparsity measures to derive a single weight which works best for The user specific sparsity measure is based on the intuition that the active user, is propitious. The sparsity measures can be coa- users who have rated very few items are less likely to get reliable lesced into a unified sparsity measure(UMS) by considering a us need to depend more on global neighbor- weighted average of all the sparsity measures, where a sparsity hood set. The USS is user-dependent, but remains the same across easure more representative of the users preference for local/glo- all items whose rating needs to be predicted bal predictions, has a higher value.with a set to a value which results in the least MAE. This scheme of estimating a would hereafter be referred to as the fixed-a scheme 2. 3. Novel schemes for estimating parameter a A framework combining predictions from local and global neighbors was discussed in Section 2. The parameter a serves to adjust the weight that we give to global neighbors with re￾gards to the weight that we give to the local neighbors. When the ratings matrix is dense then generally the local neighbor￾hood set is rich enough to enable prediction for the active user, in which case the predictions from local neighborhood should be weighed more. However, when the ratings matrix is sparse, the meager local neighborhood set generated may lead to low quality recommendations, and therefore it needs to be enriched by the globally similar neighbors and for better predictions. In this section we propose several sparsity measures which enable the global neighbors to be weighed according to the active user and the item whose vote needs to be predicted. To the best of our knowledge there has been no previous attempt at quantifying the various facets of sparseness in data and to use them in the pre￾diction process. The ‘‘sparsity problem” in collaborative filtering refers to inability to find a sufficient quantity of good quality neighbors to aid in the prediction process due to insufficient over￾lap of ratings between the active user and his neighbors. This can happen when the ratings matrix is sparse, or the number of users participating is not large. Even when the data is dense enough to allow quality predictions for most users, some users may not have rated enough items or may have rated items not rated by most people, with the result that such users get poor quality predictions. Users whose local neighborhood set is sparse can thus be aided by using predictions from the global neighborhood set. Thus intui￾tively the value of a should depend on the user and the item whose rating is to be predicted. The proposed work introduces several estimates for a, which captures the various aspects of sparseness in the data. 3.1. Individual sparsity measures In this section we introduce several sparsity measures namely, OS (overall sparsity measure), USS (user specific sparsity measure), LGR (local global ratio), UIS1 (user item based sparsity measure 1) and UIS2 (user item based sparsity measure 2). 3.1.1. Overall sparsity measure(OS) The overall sparsity measure captures the level of sparsity in the entire rating matrix. This sparsity measure is universal i.e. the a computed is fixed for all users. The overall sparsity measure is defined as: Overall sparsity measure ¼ 1 nR nUsers  nItems ð8Þ where nR is the total number of ratings which exist, nUsers is the total number of users in the system and nItems is the total number of items. 3.1.2. User specific sparsity measure(USS) The user specific sparsity measure is based on the intuition that users who have rated very few items are less likely to get reliable local neighbors and thus need to depend more on global neighbor￾hood set. The USS is user-dependent, but remains the same across all items whose rating needs to be predicted. The USS for user uand item i is defined as: User specific sparsity measure ¼ 1 nu max u2U ðnuÞ ð9Þ where nu is the number of items rated by user u. 3.1.3. User and item specific sparsity measures Sometimes the superiority of global predictions over local ones also depend on the type of items rated by the user. For example the local neighbors for a user, with eclectic tastes who has rated sev￾eral items which have not been experienced by a large majority of users, may be scarce. When the local neighborhood is meager, global neighbors can contribute to improvement in accuracy of predictions. This means that the sparsity measure should take into account not only the active user, but also the item for which the rating needs to be predicted. Three sparsity measures, which cap￾ture sparsity at user-item level, are introduced below.  Local global ratio (LGR) One simple measure is to find the ratio of number of local neighbors to the number of global neighbors who have rated the item. It is to be noted that the number of global neighbors always exceeds or is equal to the number of local neighbors. This is due to the fact that simG(x,y) P simL(x,y). The LGR for a user u and item i is defined as: LGRðu; iÞ ¼ 1 jLu;ij jGu;ij ð10Þ where Lu,i is the set of local neighbors of user u who have rated item i, Gu,i is the set of global neighbors of user u who have rated item i.  User-item specific sparsity measure1 (UIS1) The UIS1 measure bases the sparsity measurement on the ratio of number of local neighbors who have rated a particular item to the total number of people who have rated the item i.e. the UIS1 for a user u and item i is defined as: UIS1ðu; iÞ ¼ 1 jLu;ij jNij ð11Þ where Ni is the set of users who have rated item i.  User-item specific sparsity measure2 (UIS2) The UIS2 measure computation is founded on the ratio of number of local neigh￾bors who have rated a particular item to the total number of users in the local neighborhood set i.e. the UIS2 for a user u and item i is defined as: UIS2ðu; iÞ ¼ 1 jLu;ij jLuj ð12Þ where Lu is the set of local neighbors for user u. 3.2. Unified measure of sparsity(UMS)–GA approach The various measures of sparsity, described in Section 3, encap￾sulate the diverse factors that come into play, when deciding the extent to which the local and global predictions should influence the final prediction. The performance of each sparsity measure is dataset dependent and hence the quality offered, varies across sev￾eral datasets. The sparsity measure, which best reflects the balance between local and global predictions may differ from user to user and also may evolve over time. The idea of unifying the various sparsity measures to derive a single weight which works best for the active user, is propitious. The sparsity measures can be coa￾lesced into a unified sparsity measure(UMS) by considering a weighted average of all the sparsity measures, where a sparsity measure more representative of the user’s preference for local/glo￾bal predictions, has a higher value. 5104 D. Anand, K.K. Bharadwaj / Expert Systems with Applications 38 (2011) 5101–5109