CS 332 Syllabus by Week

Fall 2011

Week 1: Top 10 Algorithms in Data Mining

Week 2: Decision Tree Construction

On-line references:

Xindong Wu, Knowledge Acquisition from Databases, Chapter 4: Constructing Decision Trees with ID3 and C4.5, Ablex Publishing Corp., U.S.A., 1995. ISBN 1-56750-206-7 (cloth cover); ISBN 1-56750-205-9 (paper cover).
Ross Quinlan, C4.5 and Beyond, 2006.
Structure of decision trees
Data input
Decision tree construction: A simplified example
The Concept Learning System (CLS)
ID3/C4.5: Choose the "best" attribute at each non-leaf node
Information Gain
Training, testing and predictive accuracy
Information gain vs the gain ratio criterion
Difficulties with decision tree construction
Overfitting
C4.5 software on mansfield.emba.uvm.edu (under /bin/kdd)
Experiments/exercises with C4.5
(A tutorial on C4.5 can be found at http://www.cs.uregina.ca/~dbd/cs831/notes/ml/dtrees/c4.5/tutorial.html)
- Copy the 3 monks databases (monk1.*, monk2.*, and monk3.*) from the /bin/kdd/data directory to your home directory, and try c4.5 (with -u) on each of them.
- Compare and contrast the C4.5 trees with ID3 (-g) trees on these problems.
- Compare and contrast the original and pruned/simplified decision trees.
- Try the -m, -c, and -s switches, and check the differences.

Week 3: Association Analysis

On-line references:

R. Agrawal, T. Imielinski, and A. Swami, Mining Associations between Sets of Items in Massive Databases, Proc. of the ACM SIGMOD Int'l Conference on Management of Data, Washington D.C., May 1993, 207-216.
R. Agrawal, and R. Srikant, Fast Algorithms for Mining Association Rules, Proc. of the 20th Int'l Conference on Very Large Databases, Santiago, Chile, Sept. 1994.
C. Faloutsos, Apriori Algorithm, 2006.
A mathematical model for association analysis
Large itemsets and association rules
Apriori: constructs large itemsets with minisup by iterations
Interestingness of Discovered Association Rules
Application examples
Association analysis vs. classification
Machine Learning Software in Java at the University of Waikato
- Installation Instructions provided by Sameer S. Pradhan
Experiments/exercises with weka.associations.Apriori
- If you run Weka on Mansfield, run
  setenv CLASSPATH /usr/bin/weka/weka-3-3-6/
  at first.
- Copy the .arff files from the /bin/weka/weka-3-3-6/data directory to your home directory, and try
  java weka.associations.Apriori (with -t) on each of them.
- Try the -N, -C, and -M switches, and check the differences.
- Generate the first 5 association rules (ordered by their confidence) for each .arff file, and list their confidence and support.
Additional topics:
- Quantitative Association Rules (Srikant & Agrawal, SIGMOD '96)
- Multiple-Level Association Rules (Han & Fu, IEEE TKDE, October 1999)
- Association Analysis with One Scan of Databases (ICDM-02)

Week 4: Clustering

On-line references:

Jiawei Han's slides on Cluster Analysis
ICDM '06 slides on The K-Means Algorithm, 2006.
ICDM '06 slides on The EM Algorithm, 2006.
Clustering: unsupervised learning
Types of clusters
Different clustering methods
k-means: iterative distance-based clustering
Dealing with discrete values in k-means
Constructing a hierarchical clustering using k-means
EM: Expectation Maximization
DBSCAN: Density-Based Clustering
How to combine clustering and classification?
How to measure the quality of clustering?
Outlier analysis

Week 5: Rule Induction, kNN and GA

On-line references:

Xindong Wu, Rule Induction with Extension Matrices, Journal of the American Society for Information Science, 49(1998), 435-454.
Classification rules
Decision lists and disjunctive normal form (DNF)
1R ("1-rule")
Steps in c4.5rules
Running c4.5rules on Mansfield
The default (or no information) rule
Rule Induction by Covering

PRISM: Constructing correct and "perfect" rules

For each class C 
  Initialize E to the instance set 
  While E contains instances in C 
    Create a rule R with an empty left-hand side (LFS) that predicts C 
    Until R is perfect (or no more attributes to use) do 
       For each attibute Ai not mentioned in R, and each value Vij 
         Check the accuaracy p/t 
          (t: total examples covered by Ai = Vij, and  
           p: positive examples covered by Ai = Vij) 
         Select the Ai = Vij that maximize p/t (and break ties by 
           choosing with the largest p) 
       Add A = Vij to R 
    Remove the examples covered by R from E 

 No & Fever  & Cough  & X-Ray & ESR  & Auscultation & Disease  
---------------------------------------------------------------- 
  1 & high   & heavy  & flack & normal & bubblelike & 
  2 & medium & heavy  & flack & normal & bubblelike & 
  3 & low    & slight & spot  & normal & dry-peep   & Pneumonia 
  4 & high   & medium & flack & normal & bubblelike &  
  5 & medium & slight & flack & normal & bubblelike & 
---------------------------------------------------------------- 
  6 & absent & slight & strip & normal & normal   &  
  7 & high   & heavy  & hole  & fast   & dry-peep & 
  8 & low    & slight & strip & normal & normal   & Tuberculosis 
  9 & absent & slight & spot  & fast   & dry-peep &  
 10 & low    & medium & flack & fast   & normal   & 
--------------------------------------------------------------------

Divide-and-Conquer vs Separate-and-Conquer
Rule induction algorithms in Weka
Classification vs prediction
Lazy vs eager learning
The k-nearest neighbor algorithm
Genetic algorithms (GA)
E-mail the instructor (xwu@cs.uvm.edu) by Friday 10/7 with the following information:
- 3 papers from the Paper Presentations in order of your preferences.

Week 6: Bayesian Methods

On-line references:

David Heckerman, Learning With Bayesian Networks, IJCAI 1999 Tutorial Notes, 1999.
Alternative hypotheses
Prior knowledge
Imperfect data indicators
Conditional probability
Bayes theorem
Maximum A Posteriori (MAP)
Naive Bayes Classifier

The PlayTennis data with Naive Bayes

Day & Outlook  & Temperature & Humidity & Windy  & PlayTennis
------------------------------------------------------------
  1 & sunny    &   hot       & high     & weak   & No
  2 & sunny    &   hot       & high     & strong & No
  3 & overcast &   hot       & high     & weak   & Yes
  4 & rain     &   mild      & high     & weak   & Yes
  5 & rain     &   cool      & normal   & weak   & Yes
  6 & rain     &   cool      & normal   & strong & No
  7 & overcast &   cool      & normal   & strong & Yes
  8 & sunny    &   mild      & high     & weak   & No
  9 & sunny    &   cool      & normal   & weak   & Yes
 10 & rain     &   mild      & normal   & weak   & Yes
 11 & sunny    &   mild      & normal   & strong & Yes
 12 & overcast &   mild      & high     & strong & Yes
 13 & overcast &   hot       & normal   & weak   & Yes
 14 & rain     &   mild      & high     & strong & No

Q: (Outlook = sunny, Temperature = cool, Humidity = high, Wind = strong)

Belief networks
Network topology
Conditional probability tables (CPT)
Joint probability distribution in a belief network
Advanced topics:
- Training belief networks
- Incremental construction of belief networks
- Inference in belief networks
The Naive Bayes algorithm in Weka, weka.classifiers.NaiveBayes
Online streaming feature selection: features to arrive one by one

Week 7: Dealing with Noise and Real-Valued Attributes (3 Lectures)

On-line references:

Xindong Wu, Knowledge Acquisition from Databases, Chapter 6: Dealing With Noise and Real-Valued Attributes, Ablex Publishing Corp., U.S.A., 1995. ISBN 1-56750-206-7 (cloth cover); ISBN 1-56750-205-9 (paper cover).
Artificial vs. real-world databases
The Monk's Problems: An example
Sources Of Noise
- Erroneous values
- Missing values (?)
- Misclassifications
- Contradictory data
- Redundant data
- Don't Care (#) values
- Incomplete attributes and uneven data distribution
- Systematic noise (and background noise)
Noise Handling
- Preprocessing
- Pre-pruning
- Post-pruning
- Dealing with unusual examples when deduction of induction results
Cross validation
Dealing with contradictions and redundancy
Expansion of Don't Care values
Handling of ? values
Generation of nonexistent examples
Light-weight leaves/rules
Stopping criteria to avoid overfitting
Overfitting vs underfitting
Occam's Razor
Reduced error pruning with a separate pruning set
Truncation of rules - TRUNC
"No match" and "multiple match" when deduction of induction results
Measure of fit
Estimate of probability
Dealing with real-valued attributes: Discretization
- Class-Separating
- The information gain heuristic
Criteria to stop the recursive splitting
Discretization in C4.5
Dealing with noise in real-valued attributes: fuzzy interpretation of discretized intervals
Random noise vs systematic noise
Impact of noise handling

Week 8: Data Mining from Very Large Databases

On-line references:

Xindong Wu, Data Mining from Very Large Databases, Invited Talk in Advanced Topics in Database Management Systems - Data Mining and Data Warehousing at the National University of Singapore, 31 July 1999.
Why large databases?
Data partitioning
Sampling techniques
Cross validation
Windowing in C4.5
Integrative windowing
Bagging, boosting, and their differences
Boosting in C5.0
Incremental batch learning
Aggregation of rules from different data sources
Leading data mining tools
- C5.0/See5, RuleQuest Research (Australia)
- Intelligent Miner, IBM
- Clementine, Integral Solutions (UK)
- DBMiner, DBMiner Technologies (Canada)
- Other data mining tools (http://www.datamininglab.com/toolcomp.html)

Week 9: Mid-Term Exam

Weeks 10-14: Paper Presentations and Essay Writing

Week 15: Course Requirements for Final Exam

Please e-mail queries and comments to xwu@cs.uvm.edu.