C4.5决策树：机器学习十大算法解析

需积分: 9 128 浏览量更新于2024-07-22 收藏 3.31MB PDF 举报

"这篇文档是关于机器学习中最顶级的十个算法之一——C4.5决策树算法的介绍。" 在机器学习领域，C4.5算法是一个极为重要的分类方法，尤其在数据挖掘中有着广泛的应用。它属于监督学习的范畴，主要用于解决已知属性值的数据集分类问题。C4.5的目标是从一系列属性中学习到一个映射关系，将这些属性值映射到特定的类别，以便对新的、未见过的实例进行分类。 1.1 引言 C4.5算法由Ross Quinlan开发，它是ID3算法的升级版，处理连续属性和缺失值的能力更加强大。该算法不仅适用于离散型数据，也能够处理连续型数据，从而提高了其在实际问题中的适应性。 1.2 算法描述 C4.5算法通过构建决策树来实现分类。在构建过程中，它根据信息增益或信息增益比选择最优属性进行划分，以最大程度地减少熵或信息不纯度。这确保了决策树的构建是基于特征的重要性。 1.3 C4.5特性 - **树修剪**：C4.5通过后剪枝策略来防止过拟合，即当一个分支不能进一步提高分类准确率时，会将其简化。 - **连续属性的处理**：不同于ID3仅处理离散属性，C4.5能有效处理连续属性，通过创建基于属性阈值的分裂。 - **处理缺失值**：C4.5可以处理数据集中存在的缺失值，通过引入特殊节点来考虑缺失值的可能情况。 - **规则集诱导**：除了决策树，C4.5还能生成类规则，使得解释模型更加直观。 1.4 软件实现讨论 C4.5算法有多种软件实现，如Weka，R语言的rpart包等，这些工具为用户提供了便捷的接口来应用和操作C4.5算法。 1.5 示例文档中提供了两个案例，分别是高尔夫数据集和大豆数据集，用以展示C4.5算法的实际应用和效果。 1.6 高级主题 - **从二级存储挖掘**：讨论如何在大型数据集上运行C4.5，这涉及到数据的存储和检索策略。 - **倾斜决策树**：扩展了传统的轴平行决策树，允许根据多个属性的组合来划分数据。 - **特征选择**：通过减少非重要特征，优化决策树的性能和可理解性。 - **集成方法**：如随机森林，通过构建多个C4.5决策树并结合它们的预测来提高分类的稳定性和准确性。 - **分类规则**：C4.5不仅可以生成决策树，还能产生类规则，这些规则对于理解和解释分类结果很有帮助。 - **重新描述**：通过对决策树进行重组和简化，提高模型的简洁性和可解释性。 1.7 练习与参考文献章节末尾通常包含练习题目，用于巩固理解和深入学习，并列出了相关的参考文献供进一步研究。 C4.5算法在机器学习中扮演着重要角色，它的高效性和灵活性使其在各种任务中都有所应用，例如信用卡欺诈检测、医学诊断和市场分割等。理解和掌握这一算法，对于提升机器学习实践能力至关重要。

16 C4.5

axes. Apply C4.5 on this dataset and comment on the quality of the induced

trees. Take factors such as accuracy, size of the tree, and comprehensibility into

account.

3. An alternative way to avoid overﬁtting is to restrict the growth of the tree rather

than pruning back a fully grown tree down to a reduced size. Explain why such

prepruning may not be a good idea.

4. Prove that the impurity measure used by C45 (i.e., entropy) is concave. Why is

it important that it be concave?

5. Derive Equation (1.1). As stated in the text, use the normal approximation to

the Bernoulli random variable modeling the error rate.

6. Instead of using information gain, study how decision tree induction would be

affectedif we directly selected the attribute with the highest prediction accuracy.

Furthermore, what if we induced rules with only one antecedent? Hint: Yo u

are retracing the experiments of Robert Holte as described in R. Holte, Very

Simple Classiﬁcation Rules Perform Well on Most Commonly Used Datasets,

Machine Learning, vol. 11, pp. 63–91, 1993.

7. In some machine learning applications, attributes are set-valued,for example,an

object can have multiple colors and to classify the object it might be important to

model color as a set-valued attribute rather than as an instance-valued attribute.

Identify decision tests that can be performed on set-valuedattributes and explain

which can be readily incorporated into the C4.5 system for growing decision

trees.

8. Instead of classifying an instance into a single class, assume our goal is to obtain

a ranking of classes according to the (posterior) probability of membership of

the instance in various classes. Read F. Provost and P. Domingos, Tree Induction

for Probability Based Ranking, Machine Learning, vol. 52, no. 3, pp. 199–215,

2003, who explain why the trees induced by C4.5 are not suited to providing

reliable probability estimates; they also suggest some ways to ﬁx this problem

using probability smoothing methods. Do these same objections and solution

strategy apply to C4.5 rules as well? Experiment with datasets from the UCI

repository.

9. (Adapted from S. Nijssen and E. Fromont, Mining Optimal Decision Trees

from Itemset Lattices, Proceedings of the 13th ACM SIGKDD International

Conference on Knowledge Discovery and Data Mining, pp. 530–539, 2007.)

The trees induced by C4.5 are driven by heuristic choices but assume that our

goal is to identify an optimal tree. Optimality can be posed in terms of various

considerations; two such considerations are the most accurate tree up to a

certain maximum depth and the smallest tree in which each leaf covers at least

k instances and the expected accuracy is maximized over unseen examples.

Describe an efﬁcient algorithm to induce such optimal trees.

10. First-order logic is a more expressive notation than the attribute-value repre-

sentation considered in this chapter. Given a collection of ﬁrst-order relations,

describe how the basic algorithmic approach of C4.5 can be generalized to use

References 17

ﬁrst-order features. Your solution must allow the induction of trees or rules of

the form:

grandparent(X,Z) :- parent(X,Y), parent(Y,Z).

that is, X is a grandparent of Z if there exists Y such that Y is the parent of

X and Z is the parent of Y. Several new issues result from the choice of ﬁrst-

order logic as the representational language. First, unlike the attribute value

situation, ﬁrst-order features (such as parent(X,Y)) are not readily given

and must be generalized from the speciﬁc instances. Second, it is possible to

obtain nonsensical trees or rules if the variables participate in the head of a rule

but not the body, for example:

grandparent(X,Y) :- parent(X,Z).

Describe how you can place checks and balances into the induction process

so that a complete ﬁrst-order theory can be induced from data. Hint: You are

exploring the ﬁeld of inductive logic programming [9], speciﬁcally, algorithms

such as FOIL [29].

References

[1] R. Agrawal, T. Imielinski, and A. N. Swami. Mining association rules between

sets of items in large databases. In Proceedings of the ACM SIGMOD Interna-

tional Conference on Management of Data (SIGMOD’93), pp. 207–216, May

1993.

[2] R. Agrawal and R. Srikant. Fast algorithms for mining association rules in large

databases. In Proceedings of the 20th International Conference on Very Large

Databases (VLDB’94), pp. 487–499, Sep. 1994.

[3] A. Asuncion and D. J. Newman. UCI Machine Learning Repository, 2007.

http://www.ics.uci.edu/∼mlearn/MLRepository.html. University of California,

Irvine, School of Information and Computer Sciences.

[4] L. Breiman, J. Friedman, C. J. Stone, and R. A. Olshen. Classiﬁcation and

Regression Trees. Chapman & Hall/CRC, Jan. 1984.

[5] C. E. Brodely and P. E. Utgoff. Multivariate Decision Trees. Machine Learning,

19:45–77, 1995.

[6] P. Clark and T. Niblett. The CN2 Induction Algorithm. Machine Learning,

3(4):261–283, 1999.

[7] W. Cohen. Fast Efﬁcient Rule Induction. In Proceedings of the Twelfth Inter-

national Conference on Machine Learning, pp. 115–123, 1995.

18 C4.5

[8] T. G. Dietterich. An Experimental Comparison of Three Methods for Con-

structing Ensembles of Decision Trees: Bagging, Boosting, and Randomiza-

tion. Machine Learning, 40(2):139–157, 2000.

[9] S. Dzeroski and N. Lavrac, eds. Relational Data Mining. Springer, Berlin, 2001.

[10] U. M. Fayyad and K. B. Irani. On the Handling of Continuous-Valued Attributes

in Decision Tree Generation. Machine Learning, 8(1):87–102, Jan. 1992.

[11] Y. Freund and L. Mason. The Alternating Decision Tree Learning Algorithm.

In Proceedings of the Sixteenth International Conference on Machine Learning

(ICML 1999), pp. 124–133, 1999.

[12] Y. Freund and R. E. Schapire. A Short Introduction to Boosting. Journal of the

Japanese Society for Artiﬁcial Intelligence, 14(5):771–780, Sep. 1999.

[13] J. H. Friedman. A Recursive Partitioning Decision Rule for Nonparametric

Classiﬁcation. IEEE Transactions on Computers, 26(4):404–408, Apr. 1977.

[14] J. Gehrke, V. Ganti, R. Ramakrishnan, and W.-H. Loh. BOAT: Optimistic De-

cision Tree Construction. In Proceedings of the ACM SIGMOD International

Conference on Management of Data (SIGMOD’99), pp. 169–180, 1999.

[15] J. Gehrke, R. Ramakrishnan, and V. Ganti. RainForest: A Framework for Fast

Decision Tree Construction of Large Datasets. Data Mining and Knowledge

Discovery, 4(2/3):127–162, 2000.

[16] E. B. Hunt, J. Marin, and P. J. Stone. Experiments in Induction. Academic Press,

New York, 1966.

[17] R. Kohavi, D. Sommerﬁeld, and J. Dougherty. Data Mining Using MLC++: A

Machine Learning Library in C++. In Proceedings of the Eighth International

Conference on Tools with Artiﬁcial Intelligence (ICTAI ’96), pp. 234–245, 1996.

[18] D. Koller and M. Sahami. Toward Optimal Feature Selection. In Proceedings

of the Thirteenth International Conference on Machine Learning (ICML’96),

pp. 284–292, 1996.

[19] D. Kumar, N. Ramakrishnan, R. F. Helm, and M. Potts. Algorithms for Sto-

rytelling. In Proceedings of the Twelfth ACM SIGKDD International Con-

ference on Knowledge Discovery and Data Mining (KDD’06), pp. 604–610,

Aug. 2006.

[20] B. Liu, W. Hsu, and Y. Ma. Integrating Classiﬁcation and Association Rule

Mining. In Proceedings of the Fourth International Conference on Knowledge

Discovery and Data Mining (KDD’98), pp. 80–86, Aug. 1998.

[21] M. Mehta, R. Agrawal, and J. Rissanen. SLIQ: A Fast Scalable Classiﬁer for

Data Mining. In Proceedings of the 5th International Conference on Extending

Database Technology (EDBT’96), pp. 18–32, Mar. 1996.

[22] S. K. Murthy, S. Kasif, and S. Salzberg. A System for Induction of Oblique

Decision Trees. Journal of Artiﬁcial Intelligence Research, 2:1–32, 1994.

References 19

[23] D.W. Opitz and R. Maclin. Popular Ensemble Methods: An Empirical Study.

Journal of Artiﬁcial Intelligence Research, 11:169–198, 1999.

[24] L. Parida and N. Ramakrishnan. Redescription Mining: Structure Theory and

Algorithms. In Proceedings of the Twentieth National Conference on Artiﬁcial

Intelligence (AAAI’05), pp. 837–844, July 2005.

[25] J. R. Quinlan. Induction of Decision Trees. Machine Learning, 1(1):81–106,

1986.

[26] J. R. Quinlan. Simplifying Decision Trees. Technical Report 930, MIT AI Lab

Memo, Dec. 1986.

[27] J. R. Quinlan. Decision Trees as Probabilistic Classiﬁers. In P. Langley, ed.,

Proceedings of the Fourth International Workshop on Machine Learning. Mor-

gan Kaufmann, CA, 1987.

[28] J. R. Quinlan. Unknown Attribute Values in Induction. Technical report, Basser

Department of Computer Science, University of Sydney, 1989.

[29] J. R. Quinlan. Learning Logical Deﬁnitions from Relations. Machine Learning,

5:239–266, 1990.

[30] J.R. Quinlan. C4.5: Programsfor MachineLearning. MorganKaufmann, 1993.

[31] J. R. Quinlan. Improved Use of Continuous Attributes in C4.5. Journal of

Artiﬁcial Intelligence Research, 4:77–90, 1996.

[32] N. Ramakrishnan, D. Kumar, B. Mishra, M. Potts, and R. F. Helm. Turning

CARTwheels: An Alternating Algorithm for Mining Redescriptions. In Pro-

ceedings of the Tenth ACM SIGKDD International Conference on Knowledge

Discovery and Data Mining (KDD’04), pp. 266–275, Aug. 2004.

[33] R. Rastogi and K. Shim. PUBLIC: A Decision Tree Classiﬁer that Integrates

Building and Pruning. In Proceedings of the 24th International Conference on

Very Large Data Bases (VLDB’98), pp. 404–415, Aug. 1998.

[34] J. C. Shafer, R. Agrawal, and M. Mehta. SPRINT: A Scalable Parallel Classiﬁer

for Data Mining. In Proceedings of the 22th International Conference on Very

Large Data Bases (VLDB’96), pp. 544–555, Sep. 1996.

[35] I. H. Witten and E. Frank. Data Mining: Practical Machine Learning Tools and

Techniques. Morgan Kaufmann, 2005.

[36] X.Wu, V.Kumar, J. R. Quinlan, J. Ghosh, Q. Yang, H. Motoda, G. J. McLachlan,

A. Ng, B. Liu, P. S. Yu, Z.-H. Zhou, M. Steinbach, D. J. Hand, and D. Steinberg.

Top 10 Algorithms in Data Mining. Knowledge and Information Systems,

14:1–37, 2008.

[37] L. Zhao, M. Zaki, and N. Ramakrishnan. BLOSOM: A Framework for Mining

Arbitrary Boolean Expressions over Attribute Sets. In Proceedings of the

Twelfth ACM SIGKDD International Conference on Knowledge Discovery and

Data Mining (KDD’06), pp. 827–832, Aug. 2006.

Chapter 2

K-Means

Joydeep Ghosh and Alexander Liu

Contents

2.1 Introduction ............................................................ 21

2.2 The k-means Algorithm ................................................. 22

2.3 Available Software ...................................................... 26

2.4 Examples ............................................................... 27

2.5 Advanced Topics ........................................................ 30

2.6 Summary ............................................................... 32

2.7 Exercises ............................................................... 33

References ................................................................... 34

2.1 Introduction

In this chapter, we describe the k-means algorithm, a straightforward and widely

used clustering algorithm. Given a set of objects (records), the goal of clustering

or segmentation is to divide these objects into groups or “clusters” such that objects

withina grouptendto bemore similartoone anotherascompared toobjects belonging

to different groups. In other words, clustering algorithms place similar points in the

same cluster while placing dissimilar points in different clusters. Note that, in contrast

to supervised tasks such as regression or classiﬁcation where there is a notion of a

target value or class label, the objects that form the inputs to a clustering procedure

do not come with an associated target. Therefore, clustering is often referred to

as unsupervised learning. Because there is no need for labeled data, unsupervised

algorithms are suitable for many applications where labeled data is difﬁcult to obtain.

Unsupervised tasks such as clustering are also often used to explore and characterize

the dataset before running a supervised learning task. Since clustering makes no use

of class labels, some notion of similarity must be deﬁned based on the attributesof the

objects.The deﬁnition ofsimilarityand themethodin which pointsare clustered differ

based on the clustering algorithm being applied. Thus, different clustering algorithms

are suited to different types of datasets and different purposes. The “best” clustering

algorithm to use therefore depends on the application. It is not uncommon to try

several different algorithms and choose depending on which is the most useful.

剩余192页未读，继续阅读

DMer_CS

粉丝: 0
资源: 1

C4.5决策树：机器学习十大算法解析

Python Machine Learning. Machine Learning and Deep Learning with Py, scikit

Machine Learning - Tom Mitchell

where can I get the latest information on machine learning?

Machine Learning specific learning route

Machine learning knowledge outline

现有rule-based learning和machine learning的差异点

给Machine learning has a positive impact on economic growth列三个论点，三个分论点，，并给出论据

how are machine learning used in math proof?

Matlab怎么加载Statistics and Machine Learning Toolbox包

那怎么安装这个工具箱 Statistics and Machine Learning Toolbox

最新资源