S u rv e y pa p e r

---

Knowl Inf Syst (2008) 14:1–37

DOI 10.1007/s10115-007-0114-2

S U RV E Y PA P E R

Top 10 algorithms in data mining

Xindong Wu

· Vipin Kumar · J. Ross Quinlan · Joydeep Ghosh · Qiang Yang ·

Hiroshi Motoda

· Geoffrey J. McLachlan · Angus Ng · Bing Liu · Philip S. Yu ·

Zhi-Hua Zhou

· Michael Steinbach · David J. Hand · Dan Steinberg

Received: 9 July 2007 / Revised: 28 September 2007 / Accepted: 8 October 2007

Published online: 4 December 2007

© Springer-Verlag London Limited 2007

Abstract

This paper presents the top 10 data mining algorithms identified by the IEEE

International Conference on Data Mining (ICDM) in December 2006: C4.5, k-Means, SVM,

Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART. These top 10 algorithms

are among the most influential data mining algorithms in the research community. With each

algorithm, we provide a description of the algorithm, discuss the impact of the algorithm, and

review current and further research on the algorithm. These 10 algorithms cover classification,

X. Wu (

B

)

Department of Computer Science, University of Vermont, Burlington, VT, USA

e-mail: [e-mail]

V. Kumar

Department of Computer Science and Engineering,

University of Minnesota, Minneapolis, MN, USA

e-mail: [e-mail]

J. Ross Quinlan

Rulequest Research Pty Ltd,

St Ives, NSW, Australia

e-mail: [e-mail]

J. Ghosh

Department of Electrical and Computer Engineering,

University of Texas at Austin, Austin, TX 78712, USA

e-mail: [e-mail]

Q. Yang

Department of Computer Science,

Hong Kong University of Science and Technology,

Honkong, China

e-mail: [e-mail]

H. Motoda

AFOSR/AOARD and Osaka University,

7-23-17 Roppongi, Minato-ku, Tokyo 106-0032, Japan

e-mail: [e-mail]

123

---

2

X. Wu et al.

clustering, statistical learning, association analysis, and link mining, which are all among the

most important topics in data mining research and development.

0 Introduction

In an effort to identify some of the most influential algorithms that have been widely used

in the data mining community, the IEEE International Conference on Data Mining (ICDM,

http://www.cs.uvm.edu/~icdm/

) identified the top 10 algorithms in data mining for presen-

tation at ICDM ’06 in Hong Kong.

As the first step in the identification process, in September 2006 we invited the ACM KDD

Innovation Award and IEEE ICDM Research Contributions Award winners to each nomi-

nate up to 10 best-known algorithms in data mining. All except one in this distinguished

set of award winners responded to our invitation. We asked each nomination to provide the

following information: (a) the algorithm name, (b) a brief justification, and (c) a representa-

tive publication reference. We also advised that each nominated algorithm should have been

widely cited and used by other researchers in the field, and the nominations from each nomi-

nator as a group should have a reasonable representation of the different areas in data mining.

G. J. McLachlan

Department of Mathematics,

The University of Queensland, Brisbane, Australia

e-mail: [e-mail]

A. Ng

School of Medicine, Griffith University,

Brisbane, Australia

B. Liu

Department of Computer Science,

University of Illinois at Chicago, Chicago, IL 60607, USA

P. S. Yu

IBM T. J. Watson Research Center,

Hawthorne, NY 10532, USA

e-mail: [e-mail]

Z.-H. Zhou

National Key Laboratory for Novel Software Technology,

Nanjing University, Nanjing 210093, China

e-mail: [e-mail]

M. Steinbach

Department of Computer Science and Engineering,

University of Minnesota, Minneapolis, MN 55455, USA

e-mail: [e-mail]

D. J. Hand

Department of Mathematics,

Imperial College, London, UK

e-mail: [e-mail]

D. Steinberg

Salford Systems,

San Diego, CA 92123, USA

e-mail: [e-mail]

123

---

Top 10 algorithms in data mining

3

After the nominations in Step 1, we verified each nomination for its citations on Google

Scholar in late October 2006, and removed those nominations that did not have at least 50

citations. All remaining (18) nominations were then organized in 10 topics: association anal-

ysis, classification, clustering, statistical learning, bagging and boosting, sequential patterns,

integrated mining, rough sets, link mining, and graph mining. For some of these 18 algorithms

such as k-means, the representative publication was not necessarily the original paper that

introduced the algorithm, but a recent paper that highlights the importance of the technique.

These representative publications are available at the ICDM website (

http://www.cs.uvm.

edu/~icdm/algorithms/CandidateList.shtml

).

In the third step of the identification process, we had a wider involvement of the research

community. We invited the Program Committee members of KDD-06 (the 2006 ACM SIG-

KDD International Conference on Knowledge Discovery and Data Mining), ICDM ’06 (the

2006 IEEE International Conference on Data Mining), and SDM ’06 (the 2006 SIAM Inter-

national Conference on Data Mining), as well as the ACM KDD Innovation Award and IEEE

ICDM Research Contributions Award winners to each vote for up to 10 well-known algo-

rithms from the 18-algorithm candidate list. The voting results of this step were presented at

the ICDM ’06 panel on Top 10 Algorithms in Data Mining.

At the ICDM ’06 panel of December 21, 2006, we also took an open vote with all 145

attendees on the top 10 algorithms from the above 18-algorithm candidate list, and the top 10

algorithms from this open vote were the same as the voting results from the above third step.

The 3-hour panel was organized as the last session of the ICDM ’06 conference, in parallel

with 7 paper presentation sessions of the Web Intelligence (WI ’06) and Intelligent Agent

Technology (IAT ’06) conferences at the same location, and attracting 145 participants to

this panel clearly showed that the panel was a great success.

1 C4.5 and beyond

1.1 Introduction

Systems that construct classifiers are one of the commonly used tools in data mining. Such

systems take as input a collection of cases, each belonging to one of a small number of

classes and described by its values for a fixed set of attributes, and output a classifier that can

accurately predict the class to which a new case belongs.

These notes describe C4.5 [

64

], a descendant of CLS [

41

] and ID3 [

62

]. Like CLS and

ID3, C4.5 generates classifiers expressed as decision trees, but it can also construct clas-

sifiers in more comprehensible ruleset form. We will outline the algorithms employed in

C4.5, highlight some changes in its successor See5/C5.0, and conclude with a couple of open

research issues.

1.2 Decision trees

Given a set S of cases, C4.5 first grows an initial tree using the divide-and-conquer algorithm

as follows:

• If all the cases in S belong to the same class or S is small, the tree is a leaf labeled with

the most frequent class in S.

• Otherwise, choose a test based on a single attribute with two or more outcomes. Make

this test the root of the tree with one branch for each outcome of the test, partition S into

corresponding subsets S

1

, S

2

, . . . according to the outcome for each case, and apply the

same procedure recursively to each subset.

123

---