"机器学习十大算法.pdf详解：C4.5算法的特点及应用"

需积分: 5 119 浏览量更新于2024-01-25 收藏 8.82MB PDF 举报

《机器学习十大算法.pdf》中提到了C4.5算法，本文将对该算法进行详细描述。 C4.5算法是一种决策树算法，其目标是根据已有的训练数据集构建一个可以对未知数据进行分类的决策树模型。C4.5算法的名称中的“4.5”表示其是ID3算法的延伸和改进版本。 C4.5算法的描述在《机器学习十大算法.pdf》的第一章中有详细介绍。算法的整体流程可以分为三个主要步骤：特征选择、生成决策树和剪枝。特征选择阶段通过计算数据集中每个特征的信息增益或增益率来确定最佳划分特征。生成决策树阶段通过递归地选择最佳划分特征并将数据集划分为子集来构建决策树。剪枝阶段通过修剪决策树的一些叶节点来减少过拟合。 C4.5算法具有一些独特的特点，其中一项是树的剪枝。树剪枝是一种减少模型复杂度的技术，可以提高模型的泛化能力。C4.5算法采用的是悲观剪枝策略，即首先将整个数据集作为训练集构建决策树，然后通过交叉验证方法评估和选择最佳的子树，最后将该子树作为最终结果。另一个值得注意的特点是对连续属性的改进使用。在传统的决策树算法中，连续属性的处理通常是离散化，即将连续属性划分为一系列离散的取值。而C4.5算法提出了一种更优雅的处理方法，即通过选择一个阈值将连续属性划分为两个取值，然后在此基础上构建决策树。 C4.5算法还处理了缺失值的问题。在训练数据中，经常会出现一些关键属性的缺失值，这对于模型的构建产生一定影响。C4.5算法通过引入缺失值处理机制，将缺失值视为一种特殊取值，并根据缺失值的情况采取不同的决策方式。除了以上提到的特点，C4.5算法还具有其他一些优点。首先，C4.5算法具有较好的解释性，生成的决策树模型可以直观地展示数据集的分类规则。其次，C4.5算法对于噪声和不相关特征具有较强的鲁棒性，能够处理包含有噪声或冗余特征的数据。另外，C4.5算法还能够处理多类别分类问题，不仅限于二分类。然而，C4.5算法也存在一些局限性。首先，由于C4.5算法是自顶向下生成决策树的，因此可能产生过拟合问题。其次，对于数据集中存在大量离散型特征的情况，C4.5算法的计算复杂度会显著增加。此外，C4.5算法对于长尾分布的数据集表现较差，容易偏向于出现频率较高的类别。总的来说，C4.5算法是一种经典的决策树算法，具有较好的适应性和解释性。通过对特征选择、决策树生成和剪枝等方面的改进，C4.5算法在实际应用中取得了较好的效果。然而，C4.5算法也存在一些局限性，需要根据具体问题的特点选择合适的算法。了解C4.5算法的特点和优缺点，有助于更好地理解和应用该算法。

1.7 Exercises 15

The descriptive line of research originates from association rules, a popular tech-

nique in the KDD community [1, 2] (see Chapter 4). Traditionally, associations are

between two sets, X and Y , of items, denoted by X → Y , and evaluated by measures

such as support (the fraction of instances in the dataset that have both X and Y ) and

conﬁdence (the fraction of instances with X that also have Y). The goal of associ-

ation rule mining is to ﬁnd all associations satisfying given support and conﬁdence

thresholds. CBA (Classiﬁcation based on Association Rules) [20] is an adaptation

of association rules to classiﬁcation, where the goal is to determine all association

rules that have a certain class label in the consequent. These rules are then used to

build a classiﬁer. Pruning is done similarly to error estimation methods in C4.5. The

key difference between CBA and C4.5 is the exhaustive search for all possible rules

and efﬁcient algorithms adapted from association rule mining to mine rules. This

thread of research is now an active one in the KDD community with new variants and

applications.

1.6.6 Redescriptions

Redescriptions are a generalization of rules to equivalences, introduced in [32]. As

the name indicates, to redescribe something is to describe anew or to express the

same concept in a different vocabulary. Given a vocabulary of descriptors, the goal of

redescription mining is to construct two expressions from the vocabulary that induce

the same subset of objects. The underlying premise is that sets that can indeed be

deﬁned in (at least) two ways are likely to exhibit concerted behavior and are, hence,

interesting. The CARTwheels algorithm for mining redescriptions grows two C4.5-

like trees in opposite directions such that they are matched at the leaves. Essentially,

one tree exposes a partition of objects via its choice of subsets and the other tree

tries to grow to match this partition using a different choice of subsets. If partition

correspondence is established, then paths that join can be read off as redescriptions.

CARTwheels explores the space of possible tree matchings via an alternation process

whereby trees are repeatedly regrown to match the partitions exposed by the other

tree. Redescription mining has since been generalized in many directions [19, 24, 37].

1.7 Exercises

1. Carefully quantify the big-Oh time complexity of decision tree induction with

C4.5. Describe the complexity in terms of the number of attributes and the

number of training instances. First, bound the depth of the tree and then cast

the time required to build the tree in terms of this bound. Assess the cost of

pruning as well.

2. Design a dataset with continuous-valued attributes where the decision boundary

between classes is not isothetic, that is, it is not parallel to any of the coordinate

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.

剩余217页未读，继续阅读

承让@

粉丝: 8
资源: 380

"机器学习十大算法.pdf详解：C4.5算法的特点及应用"

十大必须掌握的机器学习算法.pdf

机器学习10大经典算法..pdf

机器学习10大算法.zip

机器学习PLA算法.pdf

机器学习十大算法.zip

人工智能之机器学习常见算法.pdf

一种示例式机器学习新算法.pdf

机器学习算法概述.pdf

机器学习算法比较.pdf

机器学习算法步骤.pdf

最新资源