1.6. REFERENCES FOR CHAPTER 1
19
of the data, that is, a summary or relatively succinct representation of
the most relevant features of the data.
✦Bonferroni’s Principle: If we are willing to view as an interesting fea-
ture of data something of which many instances can be expected to exist
in random data, then we cannot rely on such features being signiﬁcant.
This observation limits our ability to mine data for features that are not
suﬃciently rare in practice.
✦TF.IDF: The measure called TF.IDF lets us identify words in a collection
of documents that are useful for determining the topic of each document.
A word has high TF.IDF score in a document if it appears in relatively few
documents, but appears in this one, and when it appears in a document
it tends to appear many times.
✦Hash Functions: A hash function maps hash-keys of some data type to
integer bucket numbers. A good hash function distributes the possible
hash-key values approximately evenly among buckets. Any data type can
be the domain of a hash function.
✦Indexes: An index is a data structure that allows us to store and retrieve
data records eﬃciently, given the value in one or more of the ﬁelds of the
record. Hashing is one way to build an index.
✦Storage on Disk: When data must be stored on disk (secondary memory),
it takes very much more time to access a desired data item than if the same
data were stored in main memory. When data is large, it is important
that algorithms strive to keep needed data in main memory.
✦Power Laws: Many phenomena obey a law that can be expressed as
y = cxa for some power a, often around −2. Such phenomena include the
sales of the xth most popular book, or the number of in-links to the xth
most popular page.
1.6
References for Chapter 1
[8] is a clear introduction to the basics of data mining. [3] covers data mining
principally from the point of view of machine learning and statistics.
The
diﬀerence between the statistical approach and the computational approach to
data mining is expressed in [1].
For construction of hash functions and hash tables, see [5]. Details of the
TF.IDF measure and other matters regarding document processing can be
found in [6].
See [4] for more on managing indexes, hash tables, and data
on disk.
Power laws pertaining to the Web were explored by [2]. The Matthew eﬀect
was ﬁrst observed in [7].
