大规模数据挖掘：算法与Web应用

5星 · 超过95%的资源需积分: 10 106 浏览量更新于2024-07-31 1 收藏 1.99MB PDF 举报

《大规模数据挖掘》是一本由Anand Rajaraman和Jeffrey D. Ullman合作编写的书籍，两位作者分别来自Kosmix公司和斯坦福大学。本书起源于他们在斯坦福大学开设的一门高级研究生课程——CS345A，名为“Web Mining”，尽管起初是针对研究生的，但其内容已经吸引了许多高级本科生的兴趣。这本书的核心关注点在于处理大规模的数据挖掘，即那些超出了传统内存容量的数据集。在当今信息爆炸的时代，数据量的快速增长使得传统的数据处理方法变得力不从心。因此，《大规模数据挖掘》将焦点放在如何利用分布式文件系统和MapReduce这样的工具来设计并执行能在海量数据上运行的并行算法。MapReduce是一种编程模型，它允许开发者编写简化的大规模数据处理任务，通过将任务分解成可以在多台机器上独立执行的部分，从而实现高效的数据处理。书中另一核心主题是相似性搜索。在这个部分，作者详细探讨了关键的技术，如近似最近邻搜索（Approximate Nearest Neighbor Search, ANNS）以及在大规模数据集中找到相似项的方法。这些技术对于推荐系统、搜索引擎优化以及社交网络分析等领域至关重要，因为它们能帮助快速定位与用户兴趣或行为相近的信息。此外，书中的其他主要话题还包括： 1. 数据压缩和索引：随着数据量的增长，有效的数据压缩技术（如哈希表、B树等）和索引策略变得至关重要，以便于快速访问和检索数据。 2. 贝叶斯网络和概率图模型：这些统计模型用于处理不确定性，常用于预测和分类问题，尤其是在处理网络数据时，如用户行为和网页链接分析。 3. 社交网络分析：研究网络结构和节点之间的关系，例如社区检测、影响力传播和用户行为预测，这在社交媒体和在线广告等领域具有广泛应用。 4. 实时流数据处理：随着物联网(IoT)设备的普及，实时处理不断流动的数据成为一大挑战，书中会介绍如何利用窗口函数、滑动窗口等技术应对这种场景。 5. 机器学习和数据挖掘算法：尽管不是以“训练机器学习引擎”为中心，书中还是涵盖了诸如聚类、分类、关联规则学习等基础机器学习算法，以及如何在海量数据上进行优化。《大规模数据挖掘》为读者提供了一套系统性的方法论和工具，以适应在现代信息技术环境下对大规模数据进行高效分析和挖掘的需求。无论是对学术研究者还是业界专业人士，这本书都是深入理解数据密集型应用不可或缺的参考资料。

4 CHAPTER 1. DATA MINING

The cases clustered around some o f the intersections of roads. These inter-

sections were the locations of wells that had become contaminated; people who

lived nearest these wells got sick, while pe ople who lived nearer to wells that

had not been co ntaminated did not get sick. Without the ability to cluster the

data, the cause of Cholera would not have be en dis c overed. 2

1.1.5 Feature Extraction

The typical feature-based model looks for the most extreme examples of a phe-

nomenon and represents the data by these examples. If you are familiar with

Bayes nets, a branch of machine learning and a topic we do not cover in this

book, you know how a complex r e lationship between objects is represented by

ﬁnding the strongest statistical dependencies among these objects and using

only those in representing all statistical connections. Some of the important

kinds of feature extraction from large-scale data that we shall study are:

1. Frequent Itemsets. This model makes sense for data that consists of “bas-

kets” of small sets of items, as in the market-basket problem that we shall

discuss in Chapter 6. We loo k for small sets of items that appear together

in many baskets, and these “frequent itemsets” are the characterization of

the data that we seek. The orignal application of this sor t of mining was

true market baskets: the sets of items, such as hamburge r and ketchup,

that people tend to buy together when checking out at the ca sh register

of a store or super market.

2. Similar Items. Often, your data looks like a collection of sets, and the

objective is to ﬁnd pair s of sets that have a relatively large frac tion of

their elements in common. An ex ample is treating customers at an on-

line store like Amazon as the set of items they have bought. In order

for Amazon to recommend something else they might like, Amazo n can

look for “similar” customers and recommend something many of these

customers have bought. This process is called “collaborative ﬁltering.”

If customers were single-minded, tha t is, they bought only one kind of

thing, then cluster ing customers might work. However, since customers

tend to have interests in many diﬀerent things, it is more useful to ﬁnd,

for each customer, a small number of other customers who are similar

in their tastes, and represent the data by these connections. We discuss

similarity in Chapter 3.

1.2 Statistical Limits on Data Mining

A common sort of data-mining problem involves discovering unusual events

hidden within massive amounts of data. This section is a discussion of the

problem, including “Bonferroni’s Principle,” a warning against overzealous use

of data mining.

1.2. STATISTICAL LIMITS ON DATA MINING 5

1.2.1 Total Information Awareness

In 2002, the Bush administration put forward a plan to mine all the data it c ould

ﬁnd, including credit-card receipts, hotel records, travel data, and many other

kinds of informatio n in order to track terro rist activity. This idea naturally

caused great concern among privacy advocates, and the project, called TIA,

or Total Information Awareness, was eventually killed by Congress, although

it is unclear whether the project in fact exists under another name. 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 technical

questions about its feasibility and the realism of its as sumptions.

The concern raised by many is that if you look at so much data, and you

try to ﬁnd within it 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.

1.2.2 Bonferroni’s Principle

Suppose you have a certain amount of data, and you look for events of a cer-

tain typ e within that data. Yo u can expect events of this type to occur, even if

the data is co mpletely random, and the number of occurrences of these events

will grow as the size o f 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 respo nses 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 occur rences as if they

were real. Calculate the expected number of occurrences of the events you are

looking for, on the as sumption that data is random. If this number is signiﬁ-

cantly larger than the number of real instances you hop e to ﬁnd, then you must

exp ect almost anything you ﬁnd to be bogus, i.e., a statistical artifact rather

than evidence of what you are looking for. This obs e rvatio n is the informal

statement of Bonferroni’s principle.

In a situation like searching for terrorists, where we expect that there are

few terr orists ope rating at any one time, Bonferroni’s principle says that we

may o nly detect terrorists by looking fo r events that are s o rare that they are

unlikely to occur in random data. We shall give an extended example in the

next section.

6 CHAPTER 1. DATA MINING

1.2.3 An Example of Bonferroni’s Principle

Suppose there are believed to be some “evil-doers” out there, and we want

to detect them. Suppose further tha t we have reason to believe that periodi-

cally, evil-doers gather at a hotel to plot their evil. Le t us ma ke the following

assumptions about the size of the problem:

1. There are one billion people who might be evil-doers .

2. Everyone goes to a hotel one day in 100.

3. A hotel holds 100 peo ple. Hence, there are 100,000 hotels — enough to

hold the 1% of a billion people who visit a hotel on any given day.

4. We shall examine hotel records for 1000 days.

To ﬁnd evil-do e rs in this data, we shall look for people who, on two diﬀerent

days, were both at the same hotel. Suppose, however, that there really are no

evil-doers. That is , everyone behaves a t random, deciding with probability 0.01

to visit a hotel on any given day, and if so , choosing one of the 10

hotels at

random. Would we ﬁnd any pairs of people who appear to b e evil-doers?

We c an do a simple approximate calculation as follows. The probability of

any two pe ople both deciding to visit a hotel on any given day is .0001. The

chance that they will visit the same hotel is this probability divided by 10

the number of hotels. Thus, the chance that they will visit the same hotel on

one given day is 10

−9

. The chance that they will visit the same hotel on two

diﬀerent given days is the square of this number, 10

−18

. Note that the hotels

can be diﬀerent on the two days.

Now, we must consider how many e vents will indicate evil-doing. An “event”

in this s e nse is a pair o f p e ople and a pair of days, such that the two people

were at the same hotel on each of the two days. To simplify the arithmetic, note

that for large n,





is about n

/2. We shall use this a pproximation in what

follows. Thus, the number of pa irs of people is





= 5 × 10

. The number

of pairs of days is



1000



= 5 × 10

. The ex pected number of events that look

like evil-doing is the product of the number of pairs of pe ople, the number of

pairs of days, and the probability that any one pair of people and pair of days

is an instance of the behavior we are looking for. That number is

5 × 10

× 5 × 10

× 10

−18

= 250, 000

That is, there will be a quarter of a million pairs of peo ple who look like evil-

doers, even though they are not.

Now, suppose there r e ally are 10 pairs of evil-doers out there. The police

will need to investigate a quarter of a million other pairs in order to ﬁnd the real

evil-doers. In addition to the intrusion on the lives of half a million innocent

people, the work involved is suﬃciently great that this approach to ﬁnding

evil-doers is probably not feasible.

1.3. THINGS USEFUL TO KNOW 7

1.2.4 Exercises for Section 1.2

Exercise 1.2.1 : Using the information from Section 1.2.3, what would be the

number of suspected pairs if the following changes were made to the data (and

all other numbers r emained as they were in that section)?

a) The numb er of days of obser vation was rais e d to 2000 .

b) The number of people observed was raised to 2 billion (and there were

therefore 200,000 hotels).

c) We only reported a pair as suspect if they were at the same hotel at the

same time on three diﬀerent days.

! Exercise 1.2.2 : Suppo se we have information about the supermarket pur-

chases of 100 million people. Each person goes to the supermarket 100 times

in a year and buys 10 of the 100 0 items that the supermarket sells. We believe

that a pair of terrorists will buy exactly the same set of 10 items (perhaps the

ingredients for a bomb?) at some time during the year. If we search for pairs of

people who have bought the s ame set of items, would we expect that any such

people found were truly terrorists?

1.3 Things Useful to Know

In this section, we oﬀer brief introductions to subjects that you may or may

not have seen in your study of other courses. Each will be useful in the study

of data mining. They include:

1. The TF.IDF measure of word importance.

2. Hash functions and their use.

3. Secondary storage (disk) and its eﬀect on running time of algorithms.

4. The ba se e of natural logarithms and identities involving that constant.

5. Power laws.

1.3.1 Importance of Words in Documents

In several applications of data mining, we shall be face d with the problem of

categorizing documents (sequences of words) by their topic. Typically, topics

are identiﬁed by ﬁnding the s pecial words that characterize documents about

that topic. For instance, articles about baseball would tend to have many

occurrences of words like “ball,” “bat,” “pitch,”, “run,” and so on. Once we

That is, assume our hypothesis that terrorists will surely buy a set of 10 items in common

at some time during the year. We don’t want to address the matter of whether or not terrorists

would necessarily do so.

8 CHAPTER 1. DATA MINING

have classiﬁed doc uments to determine they are about baseball, it is not hard

to notice that words such as these appear unusually frequently. However, until

we have made the classiﬁcation, it is not possible to identify these words as

characteristic.

Thus, classiﬁcation often starts by looking at documents, and ﬁnding the

signiﬁcant words in those documents. Our ﬁrst guess might be that the words

appearing most frequently in a document are the mos t signiﬁcant. However,

that intuition is exactly oppo site of the truth. The most frequent words will

most surely b e the common words such as “the” or “and,” which help build

ideas but do not carry a ny s igniﬁcance themselves. In fact, the several hundred

most common words in English (called stop words) are often removed from

documents before any attempt to classify them.

In fac t, the indicators of the topic are r e latively rare words. However, not

all rare words are eq ually use ful a s indicators. There are certain words, for

example “notwithstanding” or “albeit,” that appear rarely in a collection of

documents, yet do not tell us anything useful. On the other hand, a word like

“chukker” is probably equally rare, but tips us oﬀ that the document is about

the sport of polo. The diﬀerence between rar e words that tell us something and

those that do not has to do with the concentration of the useful words in just a

few documents. Tha t is, the presence of a word like “alb e it” in a document does

not make it terribly more likely that it will appear multiple times. However,

if an article mentions “chukker” once , it is likely to tell us what happened in

the “ﬁrst chukker,” then the “second chukker,” and so on. That is, the word is

likely to be r e peated if it appears at all.

The formal measure of how concentrated into relatively few documents are

the occurrences of a given word is called TF.IDF (Term Frequency times In-

verse Document Frequency). It is normally computed as follows. Suppose we

have a collection of N documents. Deﬁne f

to be the frequency (number of

occurrences) of term (word) i in document j. Then, deﬁne the term frequency

to be:

max

That is, the term frequency of term i in document j is f

normalized by dividing

it by the maximum number of occurr e nce s of any term (perhaps excluding stop

words) in the same document. Thus, the most frequent term in document j

gets a TF of 1, and other terms get fractions as their term frequency for this

document.

The IDF for a term is deﬁned as follows. Suppose term i appears in n

of the N documents in the collection. Then IDF

= log

(N/n

). The TF.IDF

score for term i in document j is then deﬁned to be TF

× IDF

. The terms

with the highest TF.IDF sco re are often the terms that best characterize the

topic of the document.

Example 1.3 : Suppose our repos itory consists of 2

= 1,0 48,576 documents.

Suppose word w appears in 2

= 1024 of these documents. Then IDF

剩余339页未读，继续阅读

zcwang_tju

粉丝: 0
资源: 2

大规模数据挖掘：算法与Web应用

Mining of Massive Datasets

斯坦福大学book-Mining of Massive Datasets

Anand.Rajaraman-Mining of Massive Datasets

mining of massive datasets中文版

推荐系统参考文献推荐系统参考文献

fundamentals of massive mimo

大模型 英文怎么翻译

NMPnet pytorch

public dataset for AI

中兴massive mimo 白皮书 csdn

最新资源

大模型英文怎么翻译