18
CHAPTER 1. DATA MINING
an on-line algorithm compared with the performance of the optimal algorithm
that is allowed to see all the data before making any decisions. These ideas are
used to give good algorithms that match bids by advertisers for the right to
display their ad in response to a query against the search queries arriving at a
search engine.
Chapter 9 is devoted to recommendation systems. Many Web applications
involve advising users on what they might like. The Netﬂix challenge is one
example, where it is desired to predict what movies a user would like, or Ama-
zon’s problem of pitching a product to a customer based on information about
what they might be interested in buying. There are two basic approaches to
recommendation. We can characterize items by features, e.g., the stars of a
movie, and recommend items with the same features as those the user is known
to like. Or, we can look at other users with preferences similar to that of the
user in question, and see what they liked (a technique known as collaborative
ﬁltering).
In Chapter 10, we study social networks and algorithms for their analysis.
The canonical example of a social network is the graph of Facebook friends,
where the nodes are people, and edges connect two people if they are friends.
Directed graphs, such as followers on Twitter, can also be viewed as social
networks.
A common example of a problem to be addressed is identifying
“communities,” that is, small sets of nodes with an unusually large number of
edges among them. Other questions about social networks are general questions
about graphs, such as computing the transitive closure or diameter of a graph,
but are made more diﬃcult by the size of typical networks.
Chapter 11 looks at dimensionality reduction. We are given a very large
matrix, typically sparse. Think of the matrix as representing a relationship
between two kinds of entities, e.g., ratings of movies by viewers. Intuitively,
there are a small number of concepts, many fewer concepts than there are
movies or viewers, that explain why certain viewers like certain movies. We
oﬀer several algorithms that simplify matrices by decomposing them into a
product of matrices that are much smaller in one of the two dimensions. One
matrix relates entities of one kind to the small number of concepts and another
relates the concepts to the other kind of entity. If done correctly, the product
of the smaller matrices will be very close to the original matrix.
Finally, Chapter 12 discusses algorithms for machine learning from very
large datasets.
Techniques covered include perceptrons, support-vector ma-
chines, ﬁnding models by gradient descent, nearest-neighbor models, and deci-
sion trees.
1.5
Summary of Chapter 1
✦Data Mining: This term refers to applying the powerful tools of computer
science to solve problems in science, industry, and many other application
areas. Frequently, the key to a successful application is building a model
