338
CHAPTER 9. RECOMMENDATION SYSTEMS
One way of dealing with this pitfall is to cluster items and/or users. Select
any of the distance measures suggested in Section 9.3.1, or any other distance
measure, and use it to perform a clustering of, say, items. Any of the methods
suggested in Chapter 7 can be used. However, we shall see that there may
be little reason to try to cluster into a small number of clusters immediately.
Rather, a hierarchical approach, where we leave many clusters unmerged may
suﬃce as a ﬁrst step. For example, we might leave half as many clusters as
there are items.
HP
TW
SW
A
4
5
1
B
4.67
C
2
4.5
D
3
3
Figure 9.7: Utility matrix for users and clusters of items
Example 9.10 : Figure 9.7 shows what happens to the utility matrix of Fig. 9.4
if we manage to cluster the three Harry-Potter movies into one cluster, denoted
HP, and also cluster the three Star-Wars movies into one cluster SW.
✷
Having clustered items to an extent, we can revise the utility matrix so the
columns represent clusters of items, and the entry for user U and cluster C is
the average rating that U gave to those members of cluster C that U did rate.
Note that U may have rated none of the cluster members, in which case the
entry for U and C is still blank.
We can use this revised utility matrix to cluster users, again using the dis-
tance measure we consider most appropriate. Use a clustering algorithm that
again leaves many clusters, e.g., half as many clusters as there are users. Re-
vise the utility matrix, so the rows correspond to clusters of users, just as the
columns correspond to clusters of items.
As for item-clusters, compute the
entry for a user cluster by averaging the ratings of the users in the cluster.
Now, this process can be repeated several times if we like. That is, we can
cluster the item clusters and again merge the columns of the utility matrix that
belong to one cluster. We can then turn to the users again, and cluster the
user clusters. The process can repeat until we have an intuitively reasonable
number of clusters of each kind.
Once we have clustered the users and/or items to the desired extent and
computed the cluster-cluster utility matrix, we can estimate entries in the orig-
inal utility matrix as follows. Suppose we want to predict the entry for user U
and item I:
(a) Find the clusters to which U and I belong, say clusters C and D, respec-
tively.
