Building Trees: ID3 Algorithm

Loading...

来自 University of Washington 的课程

实用预测分析：模型与方法

275 个评分

University of Washington

实用预测分析：模型与方法

275 个评分

课程 2（共 4 门，Specialization Data Science at Scale）

Statistical experiment design and analytics are at the heart of data science. In this course you will design statistical experiments and analyze the results using modern methods. You will also explore the common pitfalls in interpreting statistical arguments, especially those associated with big data. Collectively, this course will help you internalize a core set of practical and effective machine learning methods and concepts, and apply them to solve some real world problems. Learning Goals: After completing this course, you will be able to: 1. Design effective experiments and analyze the results 2. Use resampling methods to make clear and bulletproof statistical arguments without invoking esoteric notation 3. Explain and apply a core set of classification methods of increasing complexity (rules, trees, random forests), and associated optimization methods (gradient descent and variants) 4. Explain and apply a set of unsupervised learning concepts and methods 5. Describe the common idioms of large-scale graph analytics, including structural query, traversals and recursive queries, PageRank, and community detection

从本节课中

Supervised Learning

Follow a tour through the important methods, algorithms, and techniques in machine learning. You will learn how these methods build upon each other and can be combined into practical algorithms that perform well on a variety of tasks. Learn how to evaluate machine learning methods and the pitfalls to avoid.

From Rules to Trees2:32

Measuring Entropy4:27

Using Information Gain to Build Trees6:21

Building Trees: ID3 Algorithm2:28

Building Trees: C.45 Algorithm4:02

Rules and Trees Recap3:54

与讲师见面

Bill Howe
Director of Research
Scalable Data Analytics

[MUSIC]

So what's the algorithm here?

Okay so to summarize this algorithm which is called the ID3 algorithm,

assume all attributes are discrete.

And we can discretize continuous attributes by bending them

into particular intervals, and I'll give you a method to do that that use lines.

And then you're gonna choose the attribute with the highest information gain, and

create branches, one for each value of the attribute.

And then partition the examples based on the selected attributes so far.

And you repeat with our main attributes on the remaining set of examples.

Okay, and so you recursively apply this.

And then the stopping conditions are well when there are not more examples left,

or all the examples along a branch are assigned the same label,

cuz there's no more decisions to make at that point.

Okay, and so in this way, you can apply this algorithm,

and build up a decision tree on your data set.

And as you can see, this isn't too hard to implement.

Maybe trickiest thing, if you're not familiar with it,

is this notion of information gain which we went through.

But other than that,

I hope you can imagine trying to write a program that would do this.

There's a little bit of bookkeeping to do about building up this data structure, but

it's not too complicated.

Okay, so what are some problems with this decision tree algorithm?

Well one is that it's expensive to train.

You have to keep inspecting this big chunks of the data set

when you make every decision.

It's also prone to overfitting, which we haven't drilled into.

But this is.

In general, what overfitting means is you do really, really,

well on your training data, but you do poorly on test data.

Which is to say that the model doesn't generalize, okay.

And so you can imagine that you get these decision trees that are very,

very good at making very precise decisions about the training set.

But you give it one new example it hasn't seen before, and

it puts it into some bucket that may or may not be right.

Okay, so there's ways around this, you can try to

prune branches of the tree that are over specialized to particular conditions.

Okay, and so remove or

aggregate subtrees that don't provide much discriminatory power.

But there's another way that we're gonna talk about in the next segment that's

very, very powerful, okay.

[MUSIC]

探索我们的目录

免费加入并获得个性化推荐、更新和优惠。

Coursera 致力于普及全世界最好的教育，它与全球一流大学和机构合作提供在线课程。

© 2018 Coursera Inc. 保留所有权利。

通过 App Store 下载

通过 Google Play 获取