16
CHAPTER 1. DATA MINING
The Matthew Eﬀect
Often, the existence of power laws with values of the exponent higher than
1 are explained by the Matthew eﬀect. In the biblical Book of Matthew,
there is a verse about “the rich get richer.” Many phenomena exhibit this
behavior, where getting a high value of some property causes that very
property to increase. For example, if a Web page has many links in, then
people are more likely to ﬁnd the page and may choose to link to it from
one of their pages as well. As another example, if a book is selling well
on Amazon, then it is likely to be advertised when customers go to the
Amazon site. Some of these people will choose to buy the book as well,
thus increasing the sales of this book.
be the number of times the xth word in the order appears, then you get
a power law, although with a much shallower slope than that of Fig. 1.3.
Zipf’s observation was that y = cx−1/2. Interestingly, a number of other
kinds of data follow this particular power law. For example, if we order
states in the US by population and let y be the population of the xth
most populous state, then x and y obey Zipf’s law approximately.
1.3.7
Exercises for Section 1.3
Exercise 1.3.1: Suppose there is a repository of ten million documents. What
(to the nearest integer) is the IDF for a word that appears in (a) 40 documents
(b) 10,000 documents?
Exercise 1.3.2: Suppose there is a repository of ten million documents, and
word w appears in 320 of them. In a particular document d, the maximum
number of occurrences of a word is 15. Approximately what is the TF.IDF
score for w if that word appears (a) once (b) ﬁve times?
! Exercise 1.3.3: Suppose hash-keys are drawn from the population of all non-
negative integers that are multiples of some constant c, and hash function h(x)
is x mod 15. For what values of c will h be a suitable hash function, i.e., a
large random choice of hash-keys will be divided roughly equally into buckets?
Exercise 1.3.4: In terms of e, give approximations to
(a) (1.01)500 (b) (1.05)1000 (c) (0.9)40
Exercise 1.3.5: Use the Taylor expansion of ex to compute, to three decimal
places: (a) e1/10 (b) e−1/10 (c) e2.
