大数据挖掘：斯坦福课程精华

需积分: 17 101 浏览量更新于2024-07-18 收藏 2.91MB PDF 举报

《大规模数据挖掘》是一本由Jure Leskovec、Anand Rajaraman和Jeffrey D. Ullman共同编著的书籍，它起源于斯坦福大学多年来的教学材料，最初是作为研究生课程CS345A（Web Mining）的一部分。这门课程虽然最初针对高级研究生，但其内容已经吸引了越来越多的高级本科生的兴趣。当Jure Leskovec加入斯坦福教职后，他对课程内容进行了大幅度的重组，并引入了名为CS224W的网络分析新课程，同时对原来的CS345A课程进行了改版，将其重新命名为CS246。书中重点探讨的是大规模数据挖掘，即处理那些超出了传统计算机内存容量的数据。作者们强调的是大数据的规模，因此书中的许多案例都围绕互联网或海量数据展开。这本书汇集了三位作者在三个课程（CS345A/CS246和大型数据挖掘项目课程CS341）中教授的内容，涵盖了数据挖掘的基本理论、方法和技术，以及如何有效地处理和分析大规模数据集，包括网络结构分析、关联规则挖掘、聚类算法、异常检测、推荐系统等。《大规模数据挖掘》不仅仅关注理论，还包含了大量的实践案例和实际应用，帮助读者理解如何在现实中解决大数据挑战。此外，书中还讨论了数据获取、预处理、存储、并行计算和分布式系统等相关技术，这些都是在处理大规模数据时必不可少的环节。书中涉及的主题包括机器学习方法，如监督学习、无监督学习和半监督学习，以及它们在大规模数据集上的应用，如分类、回归和预测模型。通过对各种算法的深入剖析，读者可以掌握如何构建和优化适合大规模数据的模型，以提升数据分析的效率和准确性。《大规模数据挖掘》是一本实用且深入的指南，旨在帮助读者掌握处理和挖掘海量数据所需的技能，无论是为了学术研究还是在商业环境中进行数据驱动决策，都能提供坚实的基础。随着数据科学和云计算的发展，这本书的重要性日益凸显，对于任何希望在这个领域取得突破的人来说，都是不可或缺的学习资源。

xvi CONTENTS

10.6.3 Exercises for Section 10.6 . . . . . . . . . . . . . . . . . . 380

10.7 Counting Triangles . . . . . . . . . . . . . . . . . . . . . . . . . . 380

10.7.1 Why Count Triangles? . . . . . . . . . . . . . . . . . . . . 380

10.7.2 An Algorithm for Finding Triangles . . . . . . . . . . . . 381

10.7.3 Optimality of the Triangle-Finding Algorithm . . . . . . . 382

10.7.4 Finding Triangles Using MapReduce . . . . . . . . . . . . 383

10.7.5 Using Fewer Reduce Tasks . . . . . . . . . . . . . . . . . . 384

10.7.6 Exercises for Section 10.7 . . . . . . . . . . . . . . . . . . 385

10.8 Neighborhood Properties of Graphs . . . . . . . . . . . . . . . . . 386

10.8.1 Directed Graphs and Neighborhoods . . . . . . . . . . . . 386

10.8.2 The Diameter of a Graph . . . . . . . . . . . . . . . . . . 388

10.8.3 Tra nsitive Closure and Reachability . . . . . . . . . . . . 389

10.8.4 Tra nsitive Closure Via MapReduce . . . . . . . . . . . . . 390

10.8.5 Smart Transitive Closure . . . . . . . . . . . . . . . . . . 392

10.8.6 Tra nsitive Closure by Graph Reduction . . . . . . . . . . 393

10.8.7 Approximating the Sizes of Neighborhoods . . . . . . . . 395

10.8.8 Exercises for Section 10.8 . . . . . . . . . . . . . . . . . . 397

10.9 Summary of Chapter 10 . . . . . . . . . . . . . . . . . . . . . . . 398

10.10References for Chapter 10 . . . . . . . . . . . . . . . . . . . . . . 402

11 Dimensionality Reduction 405

11.1 Eigenvalues and Eigenvectors . . . . . . . . . . . . . . . . . . . . 405

11.1.1 Deﬁnitions . . . . . . . . . . . . . . . . . . . . . . . . . . 406

11.1.2 Computing Eigenvalues and Eigenvectors . . . . . . . . . 406

11.1.3 Finding Eigenpairs by Power Iteration . . . . . . . . . . . 408

11.1.4 The Matrix of Eigenvectors . . . . . . . . . . . . . . . . . 411

11.1.5 Exercises for Section 11.1 . . . . . . . . . . . . . . . . . . 411

11.2 Principal-Component Analysis . . . . . . . . . . . . . . . . . . . 412

11.2.1 An Illustrative Example . . . . . . . . . . . . . . . . . . . 413

11.2.2 Using Eigenvectors for Dimensionality Reduction . . . . . 416

11.2.3 The Matrix of Distances . . . . . . . . . . . . . . . . . . . 417

11.2.4 Exercises for Section 11.2 . . . . . . . . . . . . . . . . . . 418

11.3 Singular-Value Decomposition . . . . . . . . . . . . . . . . . . . . 418

11.3.1 Deﬁnition of SVD . . . . . . . . . . . . . . . . . . . . . . 418

11.3.2 Interpretation of SVD . . . . . . . . . . . . . . . . . . . . 420

11.3.3 Dimensionality Reduction Using SVD . . . . . . . . . . . 422

11.3.4 Why Zeroing Low Singular Values Works . . . . . . . . . 423

11.3.5 Querying Using Concepts . . . . . . . . . . . . . . . . . . 425

11.3.6 Computing the SVD of a Matrix . . . . . . . . . . . . . . 426

11.3.7 Exercises for Section 11.3 . . . . . . . . . . . . . . . . . . 427

11.4 CUR Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . 428

11.4.1 Deﬁnition of CUR . . . . . . . . . . . . . . . . . . . . . . 429

11.4.2 Choosing Rows and Columns Properly . . . . . . . . . . . 430

11.4.3 Constructing the Middle Matrix . . . . . . . . . . . . . . 431

11.4.4 The Complete CUR Decomposition . . . . . . . . . . . . 432

CONTENTS xvii

11.4.5 Eliminating Duplicate Rows and Columns . . . . . . . . . 433

11.4.6 Exercises for Section 11.4 . . . . . . . . . . . . . . . . . . 434

11.5 Summary of Chapter 11 . . . . . . . . . . . . . . . . . . . . . . . 434

11.6 References for Chapter 11 . . . . . . . . . . . . . . . . . . . . . . 436

12 Large-Scale M achine Learning 439

12.1 The Ma chine-Learning Model . . . . . . . . . . . . . . . . . . . . 440

12.1.1 Tra ining Sets . . . . . . . . . . . . . . . . . . . . . . . . . 440

12.1.2 Some Illustrative E xamples . . . . . . . . . . . . . . . . . 440

12.1.3 Approaches to Machine Learning . . . . . . . . . . . . . . 443

12.1.4 Machine-Learning Ar chitecture . . . . . . . . . . . . . . . 444

12.1.5 Exercises for Section 12.1 . . . . . . . . . . . . . . . . . . 447

12.2 Perceptrons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447

12.2.1 Tra ining a Perceptron with Zero Threshold . . . . . . . . 447

12.2.2 Convergence o f Perceptrons . . . . . . . . . . . . . . . . . 451

12.2.3 The Winnow Algorithm . . . . . . . . . . . . . . . . . . . 451

12.2.4 Allowing the Thres hold to Vary . . . . . . . . . . . . . . . 453

12.2.5 Multiclass Perceptrons . . . . . . . . . . . . . . . . . . . . 455

12.2.6 Tra nsforming the Tra ining Set . . . . . . . . . . . . . . . 456

12.2.7 Problems With Perceptrons . . . . . . . . . . . . . . . . . 457

12.2.8 Parallel Implementation of Perceptrons . . . . . . . . . . 458

12.2.9 Exercises for Section 12.2 . . . . . . . . . . . . . . . . . . 459

12.3 Support-Vector Machines . . . . . . . . . . . . . . . . . . . . . . 461

12.3.1 The Mechanics of an SVM . . . . . . . . . . . . . . . . . . 461

12.3.2 Normalizing the Hyperplane . . . . . . . . . . . . . . . . . 462

12.3.3 Finding Optimal Approximate Separators . . . . . . . . . 464

12.3.4 SVM Solutions by Gradient Descent . . . . . . . . . . . . 467

12.3.5 Stochastic Gradient Descent . . . . . . . . . . . . . . . . . 471

12.3.6 Parallel Implementation of SVM . . . . . . . . . . . . . . 471

12.3.7 Exercises for Section 12.3 . . . . . . . . . . . . . . . . . . 472

12.4 Learning from Nearest Neighbors . . . . . . . . . . . . . . . . . . 472

12.4.1 The Framework for Nearest- Neighbor Calculations . . . . 473

12.4.2 Learning with One Nearest Neighbor . . . . . . . . . . . . 473

12.4.3 Learning One-Dimensional Functions . . . . . . . . . . . . 474

12.4.4 Kernel Regression . . . . . . . . . . . . . . . . . . . . . . 477

12.4.5 Dealing with High-Dimensional Euclidean Data . . . . . . 477

12.4.6 Dealing with Non-Euclidean Distances . . . . . . . . . . . 479

12.4.7 Exercises for Section 12.4 . . . . . . . . . . . . . . . . . . 479

12.5 Comparison of Learning Methods . . . . . . . . . . . . . . . . . . 480

12.6 Summary of Chapter 12 . . . . . . . . . . . . . . . . . . . . . . . 481

12.7 References for Chapter 12 . . . . . . . . . . . . . . . . . . . . . . 483

2 CHAPTER 1. DATA MINING

and standar d deviation of this Gaussian distribution completely characterize the

distribution and would become the model of the data. 2

1.1.2 Machine Learning

There are some who regard data mining as synonymous with machine learning.

There is no question that s ome data mining appropriately uses algorithms from

machine learning. Machine-learning practitioners use the data as a training s et,

to train an algorithm of one of the many types used by machine-learning prac -

titioners, such a s Bayes nets, support-vector machines, decision trees, hidden

Markov models, and many others.

There are situations where using data in this way makes se ns e. The typical

case where machine learning is a good approach is when we have little idea of

what we are looking for in the data . For exa mple, it is rather unclear what

it is about movies that makes certain movie-goers like or dislike it. Thus,

in answering the “Netﬂix challenge” to devise an algorithm that predicts the

ratings of movies by users, based on a sample of their responses, machine-

learning algorithms have proved quite successful. We shall discuss a s imple

form of this type of algorithm in Section 9.4 .

On the other hand, machine learning has not proved successful in situations

where we can describe the goals of the mining more directly. An interesting

case in point is the attempt by WhizBang! Labs

to use machine learning to

locate people’s resumes on the Web. It was not able to do better than algorithms

in the typical resume. Since everyone who has looked at or written a r esume has

a pretty good idea of what resumes contain, there was no mystery about what

makes a Web page a resume. Thus, there was no advantage to machine-learning

over the direct design of an algorithm to discover resumes.

1.1.3 Computational Approaches to Modeling

More recently, computer scientists have looked at data mining as an algorithmic

problem. In this case, the model of the data is simply the answer to a complex

query about it. For instance, given the set of numbers of Example 1.1, we might

compute their average and standard deviation. Note that these values might

not be the parameters of the Ga ussian that best ﬁts the data, although they

will almost certainly be very close if the size of the data is large.

There are ma ny diﬀerent approaches to modeling data. We have already

mentioned the poss ibility of constructing a statistical process whereby the data

could have b e e n generated. Most other approaches to modeling can b e describe d

as either

1. Summarizing the data succinctly and approximately, or

This startup attempted to use machine learning to mine large-scale data, and hired many

of the top machine-learning people to do so. Unfortunately, it was not able to sur vive.

剩余512页未读，继续阅读

yimingpeng

粉丝: 0
资源: 7

大数据挖掘：斯坦福课程精华

Mining of Massive Datasets（2nd edition）

Mining of Massive Datasets.pdf

《Mining of Massive Datasets》

mining of massive datasets中文版

fundamentals of massive mimo

大模型 英文怎么翻译

NMPnet pytorch

public dataset for AI

中兴massive mimo 白皮书 csdn

massive mimo networks spectral

最新资源

大模型英文怎么翻译