6
CHAPTER 1. DATA MINING
1.2.1
Total Information Awareness
Following the terrorist attack of Sept. 11, 2001, it was noticed that there were
four people enrolled in diﬀerent ﬂight schools, learning how to pilot commercial
aircraft, although they were not aﬃliated with any airline. It was conjectured
that the information needed to predict and foil the attack was available in
data, but that there was then no way to examine the data and detect suspi-
cious events. The response was a program called TIA, or Total Information
Awareness, which was intended to mine all the data it could ﬁnd, including
credit-card receipts, hotel records, travel data, and many other kinds of infor-
mation in order to track terrorist activity. Now information integration – the
idea of relating and combining diﬀerent data sources to obtain insights that are
not available from any one source – is often a key step on the way to solving
an important problem.
TIA naturally caused great concern among privacy advocates, and the pro-
ject was eventually killed by Congress. It is not the purpose of this book to
discuss the diﬃcult issue of the privacy-security tradeoﬀ. However, the prospect
of TIA or a system like it does raise many technical questions about its fea-
sibility. In this section, we wish to focus on one particular technical problem:
if you look in your data for too many things at the same time, you will see
things that look interesting, but are in fact simply statistical artifacts and have
no signiﬁcance. That is, if you search your data for activities that look like
terrorist behavior, are you not going to ﬁnd many innocent activities – or even
illicit activities that are not terrorism – that will result in visits from the police
and maybe worse than just a visit? The answer is that it all depends on how
narrowly you deﬁne the activities that you look for. Statisticians have seen
this problem in many guises and have a theory, which we introduce in the next
section, for avoiding this sort of error.
1.2.2
Bonferroni’s Principle
Suppose you have a certain amount of data, and you look for events of a cer-
tain type within that data. You can expect events of this type to occur, even if
the data is completely random, and the number of occurrences of these events
will grow as the size of the data grows. These occurrences are “bogus,” in the
sense that they have no cause other than that random data will always have
some number of unusual features that look signiﬁcant but aren’t. A theorem
of statistics, known as the Bonferroni correction gives a statistically sound way
to avoid most of these bogus positive responses to a search through the data.
Without going into the statistical details, we oﬀer an informal version, Bon-
ferroni’s principle, that helps us avoid treating random occurrences as if they
were real. Calculate the expected number of occurrences of the events you are
looking for, on the assumption that data is random. If this number is signiﬁ-
cantly larger than the number of real instances you hope to ﬁnd, then you must
expect almost anything you ﬁnd to be bogus, i.e., a statistical artifact rather
