9.3. COLLABORATIVE FILTERING
337
As we suggested in (1) above, one way of predicting the value of the utility-
matrix entry for user U and item I is to ﬁnd the n users (for some predetermined
n) most similar to U and average their ratings for item I, counting only those
among the n similar users who have rated I. It is generally better to normalize
the matrix ﬁrst. That is, for each of the n users subtract their average rating
for items from their rating for i. Average the diﬀerence for those users who
have rated I, and then add this average to the average rating that U gives for
all items. This normalization adjusts the estimate in the case that U tends to
give very high or very low ratings, or a large fraction of the similar users who
rated I (of which there may be only a few) are users who tend to rate very high
or very low.
Dually, we can use item similarity to estimate the entry for user U and item
I. Find the m items most similar to I, for some m, and take the average rating,
among the m items, of the ratings that U has given. As for user-user similarity,
we consider only those items among the m that U has rated, and it is probably
wise to normalize item ratings ﬁrst.
Note that whichever approach to estimating entries in the utility matrix we
use, it is not suﬃcient to ﬁnd only one entry. In order to recommend items to
a user U, we need to estimate every entry in the row of the utility matrix for
U, or at least ﬁnd all or most of the entries in that row that are blank but have
a high estimated value. There is a tradeoﬀregarding whether we should work
from similar users or similar items.
• If we ﬁnd similar users, then we only have to do the process once for user
U. From the set of similar users we can estimate all the blanks in the
utility matrix for U. If we work from similar items, we have to compute
similar items for almost all items, before we can estimate the row for U.
• On the other hand, item-item similarity often provides more reliable in-
formation, because of the phenomenon observed above, namely that it is
easier to ﬁnd items of the same genre than it is to ﬁnd users that like only
items of a single genre.
Whichever method we choose, we should precompute preferred items for each
user, rather than waiting until we need to make a decision. Since the utility
matrix evolves slowly, it is generally suﬃcient to compute it infrequently and
assume that it remains ﬁxed between recomputations.
9.3.3
Clustering Users and Items
It is hard to detect similarity among either items or users, because we have
little information about user-item pairs in the sparse utility matrix.
In the
perspective of Section 9.3.2, even if two items belong to the same genre, there
are likely to be very few users who bought or rated both. Likewise, even if
two users both like a genre or genres, they may not have bought any items in
common.
