CS 580 - Data Mining

Fall-2003

Description: Data Mining studies algorithms and computational paradigms that allow computers to find patterns and regularities in databases, perform prediction and forecasting, and generally improve their performance through interaction with data. It is currently regarded as the key element of a more general process called Knowledge Discovery that deals with extracting useful knowledge from raw data. The knowledge discovery process includes data selection, cleaning, coding, using different statistical, pattern recognition and machine learning techniques, and reporting and visualization of the generated structures. The course will cover all these issues and will illustrate the whole process by examples of practical applications. Important related technologies as Data Warehousing and  On-line Analytical Processing (OLAP) will be also discussed. The students will use recent Data Mining software.

Prerequisites: CS 501 and CS 502, basic knowledge of algebra, discrete math and statistics.

Course Objectives

To introduce students to the basic concepts and techniques of Data Mining.

To develop skills of using recent data mining software for solving practical problems.

To gain experience of doing independent study and research.

Required software: Weka 3 Data Mining System - a free Machine Learning Software in Java.

Assignments, projects and grading: There will be 8 projects requiring independent study and practical work with a data mining system for solving data mining tasks and 2 quizzes. The final grade will be based 80% on projects and 20% on quizzes. The letter grades will be calculated according to the following table:
 

A	A-	B+	B	B-	C+	C	C-	D+	D	D-	F
95-100	90-94	87-89	84-86	80-83	77-79	74-76	70-73	67-69	64-66	60-63	0-59

WEB resources

1. Data Mining
• KD Nuggets Directory
• SIGKDD
• Jiawei Han and Micheline Kamber, Data Mining: Concepts and Techniques, Morgan Kaufmann Publishers, 2000
• Data Mining Resources
• The Data Mine
• Data Miners
• Software for Data Mining / Web Mining
• Journal of Data Mining and Knowledge Discovery
• WinMine Toolkit Home Page
2. Machine Learning
• Machine Learning Database Repository at UC Irvine
• Machine Learning subject index maintained by the Knowledge Systems Laboratory, Canada
• MLnet Online Information Service
• ML Information Services maintained by the Austrian Research Institute for Artificial Intelligence (OFAI)
• David Aha's list of machine learning resources
• The AutoClass Project
• UCI - Machine Learning information, software and databases
• UTCS Machine Learning Research Group
• Microsoft Belief Networks Tools
• Machine Learning Journal Online
• Weka 3 -- Machine Learning Software in Java
• C5/See5
• MLC++, A Machine Learning Library in C++
• Web->KB project

1. Introduction
• Topics:
• What is data mining?
• Related technologies - Machine Learning, DBMS, OLAP, Statistics
• Data Mining Goals
• Stages of the  Data Mining Process
• Data Mining Techniques
• Knowledge Representation Methods
• Applications
• Example: weather data
• Reading: Lecture notes - Chapter 1, Witten & Frank - Chapter 1, KDnuggets news article RE: Statisticians vs Data Miners.
• Lecture slides: Witten & Frank, Examples of Data Mining Systems: Weka 3, DBMiner.
2. Data Warehouse and OLAP
• Topics:
• Data Warehouse and DBMS
• Multidimensional data model
• Lattice of data cubes
• OLAP operations
• Reading: Lecture notes - Chapter 2, Data Cube: A Relational Aggregation ...(a paper by Jim Gray et al).
• Lecture slides: Han & Kamber.
• Project 1 - create a data cube (due 9/11/03)
3. Data preprocessing
• Reading: Lecture notes - Chapter 3, Witten & Frank - Chapter 2, Section 7.2.
• Topics
• Data cleaning
• Data transformation
• Data reduction
• Discretization and generating concept hierarchies
• Preparing the input: The ARFF file format
• Installing and using the Weka Data Mining system. See also Weka 3 -- Tips & Tricks
• Experiments with Weka - filters, discretization
• Project 2 - Data preparation(due 9/19/2003)
4. Data mining knowledge representation
• Topics
• Task relevant data
• Background knowledge
• Interestingness measures
• Representing input data and output knowledge
• Visualization techniques
• Experiments with visualization: notes on visualizing and analyzing instance spaces
• Reading: Lecture notes - Chapter 4, Witten & Frank - Chapters 2, 3. Lecture slides: Witten & Frank - Chapter 2, Witten & Frank - Chapter 3.
• Project 3 - Data visualization(due 9/25/2003)
5. Attribute-oriented analysis
• Topics:
• Attribute generalization
• Attribute relevance
• Class comparison
• Statistical measures
• Experiments: Attribute Selection with Weka (Instance-based: RefiefF and Entropy-based: InfoGain, GainRatio)
• Reading: Lecture notes - Chapter 5, Witten & Frank - Section 7.1.
6. Quiz 1
7. Data mining algorithms: Association rules
• Topics:
• Motivation and terminology
• Example: mining weather data
• Basic idea: item sets
• Generating item sets and rules efficiently
• Correlation analysis
• Approximate Association Rule Mining: dealing with missing values and numeric data
• Experiments: Association rule mining
• Reading: Lecture notes - Chapter 6, Witten & Frank - Section 4.5.
• Lecture slides: Witten & Frank.
• Advanced reading: Approximate Association Rule Mining.
• Project 4 - Association mining (due 10/16/2003)
8. Data mining algorithms: Classification
• Topics:
• Basic learning/mining tasks
• Inferring rudimentary rules: OneR algorithm
• Decision trees
• Covering rules
• Experiments with Weka - ZeroR, OneR, J48, Prism.
• Reading: Lecture notes - Chapter 7, Witten & Frank - Sections 4.1, 4.3, 4.4.
• Lecture slides: Witten & Frank
• Project 5 - Classification (due 10/31/2003)
9. Data mining algorithms: Prediction
• Topics:
• The prediction task
• Statistical (Bayesian) classification
• Bayesian networks
• Instance-based methods (nearest neighbor)
• Linear models
• Experiments with Prediction
• Reading: Lecture notes - Chapter 8, Witten & Frank - Sections 4.2, 4.6, 4.7.
• Additional reading on Bayesian Networks: MSBNx technical report
• Additional software: Microsoft Bayesian Network Tool
• Lecture slides: Witten & Frank.
• Project 6 - Prediction (due 11/13/03)
10. Evaluating what's been learned
• Topics:
• Basic issues
• Training and testing
• Estimating classifier accuracy (holdout, cross-validation, leave-one-out)
• Combining multiple models (bagging, boosting, stacking). Lecture slides: Witten & Frank.
• Minimum Description Length Principle (MLD)
• Experiments with various evaluation techniques
• Reading: Lecture notes - Chapter 9, Witten & Frank - Sections 5.1-5.4, 5.7, 5.9, 7.4.
• Lecture slides: Witten & Frank.
11. Quiz 2
12. Mining real data
• Hepatitis data description
• Hepatitis data (ARFF file)
• Experiments with the Hepatitis data
• Project 7 - mining the Hepatitis data (due 12/11/03)
13. Clustering
• Topics:
• Basic issues in clustering. Example: clustering cells.
• First conceptual clustering system: Cluster/2
• Partitioning methods: k-means, expectation maximization (EM)
• Hierarchical methods: distance-based agglomerative and divisible clustering
• Conceptual clustering: Cobweb
• Experiments with Weka - k-means, EM, Cobweb
• Reading: Lecture notes - Chapter 10, Witten & Frank - Section 6.6.
• Lecture slides: Witten & Frank.
• Project 8 - Clustering (due 12/18/03)
14. Advanced techniques and applications Reading: Witten & Frank - Chapter 9.
• Relational data mining: building relational concepts, using more elaborated background knowledge.
• Relational Languages for Leanring
• Lecture Notes in Machine Learning - see Chapters 6,7,8.
• Text mining: extracting attributes (keywords), structural approaches (parsing, soft parsing).
• Bayesian approach to classifying text - slides from Tom Mitchell's book on ML.
• Web Mining: classifying web pages, extracting knowledge from the web.
• The Web->KB project - a Web Mining project at CMU.
• Data Mining on Symbolic Knowledge Extracted from the Web - a paper describing an approach to Web Mining.
• Mining the World Wide Web - a book on the information retrieval approach (text search).
• Web Usage Analysis and User Profiling - 1999 SIGKDD Conference
• Working papers
• Semantic Web Mining
• Semantic Web
• Semantic Web Home Page
• Semantic Web Road map
• The W3C Semantic Web Activity
• The DARPA Agent Markup Language (DAML)
• An example of a semantic web page
• Web Ontology
• A Web Ontology example
• Resource Description Framework (RDF)
• RDF Example: WWW Proposal
• Semantic Web Mining
• Semantic Web Mining workshop (ECML/PKDD-2001)
• Ontology Discovery for the Semantic Web Using Hierarchical Clustering - a paper describing the use of Cobweb for Web Mining
• RDF Crawler

Project 1 - create a data cube

Quiz 1

Quiz 2