CSG230: Data Mining Techniques

CSG230: Data Mining Techniques (Spring 2008)

NEWS

News will be added here.
Slides: Intro, Association, Classification, Clustering, Data Warehousing, Distance-based Indexing, Data Preprocessing, Summary.
Grades.
Quiz 1 preparation
- Refer to some transactional database (e.g. on slide 24 or 54), tell the frequency and support of an arbitrary association rule; run FP-Growth; run MaxMiner; run CLOSET;
- Refer to some sequence database (e.g. on slide 91), given a subsequence, e.g. <ac>, find the projected DB; find all frequent sub-sequences that starts with this prefix using PrefixSpan.
- Given a training dataset, compute conditional entropy for every attribute, and build a decision tree.
Quiz 2 preparation
- Given a training dataset, perform pre-computation for the naive Baysian classifier. Using the pre-computed result to do prediction given a new data record.
- Given some description, e.g. among the non-smokers who drink alcohol, 5% have lung cancer, draw the most likely Baysian network and tell what probabilities are needed to make the network complete. Using a Baysian network to compute certain probabilities.
- Tell the general idea of using neural network and SVM for classification.
- Given some objects and a value k, perform k-means clustering.
- Given some objects, threshold T and branching factor B, construct an CF-tree.
Quiz 3 preparation
- Tell the general idea of the basic version of the CURE algorithm. If you are given a cluster of points, e.g. (0,-1), (0,2), (0,4), (2,0), (2,2), (2,5), what will CURE choose to be the representative points for the cluster, if C=2 and alpha=0? What if alpha=0.5?
- Tell the general idea of DBSCAN. Given a list of points (like the example I gave in class), run DBSCAN. For each object, tell whether it is a core object, border object, or outlier object.
- What is a data warehouse? What is ETL? What is OLAP? What is a star schema? What is ROLAP? What is MOLAP?
- Given the dimensional hierarchies on slide 26 of the data warehousing slides, how many cuboids are there in total? Starting from the base cuboid (Product, Office, Day), what OLAP operations are needed to list the sales of all products in the "Clothes" category in every country for all every month between January to May?
- Study the "multi-way array aggregation for cube computation" example on slide 47 of the data warehousing slides. What will the answers be if the 400 values in dimension B is divided into 10 pieces instead of 4?
- Given a base table (e.g. the one on slide 50 of the data warehousing slides), use BUC to compute an iceberg cube. Change the base table and try again. For instance, let the first three records have P=p1 and the last three records have P=p2.
- Assume the existence of a one-dim array B[1] to B[n], where B[i]=2 for every i. Assume a prefix-sum array A is maintained, such that A[i] = the sum of B[1] through B[i]. For instance, A[1]=2, A[2]=4, A[3]=6. How would you compute a range-sum query, e.g. find the sum of B[4] through B[12]? What's the worst-case asympotic cost? How would you update A, if an element in B is changed, e.g. B[3] becomes 10? Tell how you can use a binary tree to efficiently support the range-sum query and the update.
- Tell the general idea of the dynamic data cube.
Final preparation
- Including all quiz 1, quiz 2, and quiz 3 preparations.
- What's the general idea of regression?
- Suppose at the root node of a VP-tree, maxDL=30, minDR=40. To find the objects who distance to q < δ, under what condition will you examine the left tree and only the left tree?
- Given a set of records, e.g. {0, 6, 8, 14}, perform min-max, z-score, and decimal scaling normalization.
- Given a 2D histogram, answer an range-sum aggregation query, i.e. to find the number of objects in a given region.

Instructor

Donghui Zhang
Office Hours: Tu W 4-5:30pm
Office: 478 WVH
Phone: x2177
Email: donghui AT ccs.neu.edu
Lecture: W 6:00-9:00pm. 102WVG.

TA

Jian Wen <jarodwen AT ccs.neu.edu>, office hour Tu 4-7pm, 472WVH.
Tianhua Zheng <tianhua AT ccs.neu.edu> office hour F 1:30-3, 5:30-7pm, 472WVH.

Overview

This course introduces basic data mining techniques. We will cover four aspects of data mining including association rules, cluster Analysis, classification, and data warehousing. The class projects involve solving a real industrial problem, and implementing some fundamental data mining algorithm.

Prerequisite

Knowledge of Java and algorithms.

Grading

Quizzes: 30%
Project 1: 20%
Project 2: 15%
Final 35%

Textbook

Data Mining -- Concepts and Techniques, Jiawei Han and Micheline Kamber, 2nd edition, published by Morgan Kaufmann Publishers, ISBN 1-55860-901-6.

Projects

Project 1: Try your best to design algorithms that can beat the current algorithm of Netflix in predicting the ratings that a customer gives to a movie. Details are here. A more detailed version with background information is here. Deadline: April 1.
Project 2: Implement a fundamental data mining algorithm with GUI. Details are here. Deadline: April 15.

Class Schedule

	Date	Lecture	Quiz & Milestone
Week 1	Jan 9	Introduction, project.
Week 2	Jan 16	Chp 5: Association.
Week 3	Jan 23	Chp 5.
Week 4	Jan 30	Chp 5.
Week 5	Feb 6	Chp 6: Classification.	Quiz 1
Week 6	Feb 13	Chp 6.
Week 7	Feb 20	Chp 6
Week 8	Feb 27	Chp 2: Data Preprocessing.	Quiz 2
Week 9	Mar 5	No class (Spring break)
Week 10	Mar 12	Chp 3. Data Warehousing.
Week 11	Mar 19	Chp 4. Data Cube.
Week 12	Mar 26	Chp 7: Clustering.	Quiz 3
Week 13	Apr 2	Chp 7
Week 14	Apr 9	No class (instructor travels)
Week 15	Apr 16	Chp 8 & 9 Advanced topics.
Final Exam	Apr 23

Academic Honesty

Northeastern University is committed to the principles of intellectual honesty and integrity. All members of the Northeastern Community are expected to maintain complete honesty in all academic work, presenting only that which is their own work in tests and assignments. If you have any questions regarding the proper attribution of the work of others, contact your professor prior to submitting the work for evaluation.