340
CHAPTER 9. RECOMMENDATION SYSTEMS
(b) Then, construct from the original matrix of Fig. 9.8 a new matrix whose
rows correspond to users, as before, and whose columns correspond to
clusters. Compute the entry for a user and cluster of items by averaging
the nonblank entries for that user and all the items in the cluster.
(c) Compute the cosine distance between each pair of users, according to your
matrix from Part (b).
9.4
Dimensionality Reduction
An entirely diﬀerent approach to estimating the blank entries in the utility
matrix is to conjecture that the utility matrix is actually the product of two
long, thin matrices. This view makes sense if there are a relatively small set
of features of items and users that determine the reaction of most users to
most items. In this section, we sketch one approach to discovering two such
matrices; the approach is called “UV-decomposition,” and it is an instance of
a more general theory called SVD (singular-value decomposition).
9.4.1
UV-Decomposition
Consider movies as a case in point. Most users respond to a small number
of features; they like certain genres, they may have certain famous actors or
actresses that they like, and perhaps there are a few directors with a signiﬁcant
following. If we start with the utility matrix M, with n rows and m columns
(i.e., there are n users and m items), then we might be able to ﬁnd a matrix
U with n rows and d columns and a matrix V with d rows and m columns,
such that UV closely approximates M in those entries where M is nonblank.
If so, then we have established that there are d dimensions that allow us to
characterize both users and items closely. We can then use the entry in the
product UV to estimate the corresponding blank entry in utility matrix M.
This process is called UV-decomposition of M.


5
2
4
4
3
3
1
2
4
1
2
3
1
4
2
5
4
3
5
4
4
5
4


=


u11
u12
u21
u22
u31
u32
u41
u42
u51
u52


×
 v11
v12
v13
v14
v15
v21
v22
v23
v24
v25

Figure 9.9: UV-decomposition of matrix M
Example 9.11 : We shall use as a running example a 5-by-5 matrix M with
all but two of its entries known. We wish to decompose M into a 5-by-2 and
2-by-5 matrix, U and V , respectively. The matrices M, U, and V are shown
in Fig. 9.9 with the known entries of M indicated and the matrices U and
