Blog for Data Mining Course @ NCU

Google Tech Talks on Statistial Aspects of Data Mining

2009-03-16T19:21:00.000-07:00

The following are the links to the videos of the reading assignments. The detail of this video course is available on www.stats202.com.

Reading Assignments

2009-03-02T21:45:00.000-08:00

The updated reading assignments is available on the following URL.

Course Syllabus for 2009

2009-02-22T18:50:00.000-08:00

General Information

Graduate course
Term: Spring 2009
Date and Time: Tuesday 2:00pm - 5:00pm
Location: E6- A203
Number of credits: 3 credits

Instructor: Chia-Hui Chang
Office: E6-B302
Phone: 35302
E-mail: chia at csie dot ncu dot edu dot tw
Office Hours: Monday 3:00 - 4:50 or by appointment.

Course Goals

Introducing students to the basic concepts and techniques of data mining.
Learning by doing it, i.e. developing skills of using DM algorithms for knowledge discovery.
To gain experience of doing independent study and research.

Course Topics

Preliminary (2~3weeks)
Predictive data mining (4 weeks)
Association rule mining (3 weeks)
Cluster analysis (3 weeks)
Sequence labling (2 weeks)
Learning to rank (2 weeks)

Evaluations

Two~Three Assignments: 40%
Project: 30%
Presence: 10%
Exam: 20%

Teaching Assistant

Stanley Fan
Email:
Office Hour:

Software

2009-02-03T21:09:00.000-08:00

Commercial Software

XLMiner, Data Mining Add-In For Excel.

Free and Shareware

Weka, collection of machine learning algorithms for solving real-world data mining problems. It is written in Java and runs on almost any platform.

Other software

Book summary for Tan, Steinbach and Kumar's DM book

2009-02-03T19:22:00.000-08:00

Data Mining Chapter 6 Overview

Data Mining Chapter 5 Overview

Data Mining Chapter 4 Overview

Data Mining Chapter 3 Overview

Data Mining Chapter 2 Overview

Data Mining Chapter 1 Overview

Data Mining Chapter 6 Overview

2007-05-07T22:55:00.001-07:00

本章介紹另一種廣泛應用於商業領域的探勘技術－「Association Mining」，Association Mining透過設定support threshold過濾掉不重要的itemset，限制confidence threshold以得到較高準確度的關聯規則。Association Mining的主要研究方向為如何有「效率」地找出frequent itemset及association rule，特別是在如何產生frequent itemset的研究議題中，有許多論文使用特殊的資料結構或演算法加快速度，其中最有名的演算法是Apriori。Apriori使用anti-monotone的特性，避免產生不必要的candidate itemset以減小search space。另一種不須列舉candidate itemset的方法是FP-Growth Algorithm，它能直接從FP-Tree擷取frequent itemset，但若各交易中的項目差異較大時，它須耗費相當大的記憶體，所以使用何種方法需評估目前的資料分佈情況。

一般而言，使用support及confidence仍會產生大量的pattern，而許多pattern卻不是我們想要的，甚至會誤導我們，所以另一個研究主題為如何篩選出有意義的pattern。6.7節介紹許多domain-independent的measure，例如Interest Factor、IS Measure…等，並將這些measure依Symmetric or Asymmetric、Inversion Property、Null Addition Property及Scaling Property特性加以分類。沒有一個measure能適用於所有情況，所以我們應了解各個measure的特性及優缺點，如此才能選擇適當的measure來篩選出有意義的pattern。

本章最後敘述我們在做Association Mining時，兩個可能發生的問題－「Simpson’s Paradox」及「Skewed Support Distribution」。發生Simpson’s Paradox時，表示我們忽略的某個因素，導致我們被得出的pattern所誤導。若要避免Simpson’s Paradox，可能需要擁有domain knowledge解讀關聯規則的能力，或是對該關聯規則下的資料分佈再加以分析。若發生Skewed Support Distribution時，一般會直覺地調降support threshold，但除了導致增加計算時間之外，也會產生相當多的cross-support pattern。6.8節提供一個具有anti-monotone特性的measure－「h-confidence」來過濾cross-support pattern，減少因過低的support threshold而產生的大量pattern。

學習目標

1. 了解各種產生frequent itemset的方法
2. 了解各種measure的特性
3. 了解何謂「Simpson’s Paradox」、「Skewed Support Distribution」、「cross-support pattern」

Data Mining Chapter 5 Overview

2007-05-07T22:50:00.000-07:00

第5章延續上一章的分類主題，介紹其他常見的分類技術。從較基本的rule-based及nearest-neighbor classifier開始，再介紹較複雜的Bayesian classifier、ANN及SVM。

Rule-based classifier的產生方式分為直接與間接兩種－－直接方法最主要使用sequential covering algorithm來產生規則，間接方法則從如從決策樹來轉換成規則。Rule-based classifier通常會拿來與decision tree比較，同學們應更進一步探討兩者之間的優缺點。 Nearest-neighbor classifier屬於instance-based learning，它最大的不同在於不需要建立模型，因此稱之為Lazy Learner。

Bayesian Classifier使用條件機率的概念來建立模型，它特別適合資料即使擁有相同的屬性值，卻屬於不同的類別的情況。但要注意的是它假設屬性間的關係獨立，所以在某些情況下，其分類能力會不如於考慮屬性間關係的Bayesian Belief Networks。同學們在決定使用何種classifier時，應特別注意屬性間的關係程度所造成的影響。

ANN模擬人類大腦的神經元運作模式來建立與其相似功能的模型，在使用此分類技術時，應先決定神經元數目、層級數等參數來決定模型的學習能力。理論上，ANN所逼近的函數具備學習任何事物的能力，但如何設定適當的參數是個難題。本章對ANN只有簡短的介紹，有興趣的同學可自行研讀其它書籍。

SVM起源於統計理論，找出一個函數具備maximal margin hyperplane以達到最小化generalization error的目的。它可分為Linear SVM及Non-Linear SVM，而non Linear SVM特別適合處理非線性可區隔的資料，但SVM處理Multiclass Problem時需要建立多個classifier才能進行分類。

本章除了介紹分類技術之外，也討論兩種Ensemble Methods以提高分類的準確度－－「bagging」與「boosting」，兩者的差別在於boosting會在每一回合結束後調整權重，使得學習效果更好。最後一個小節探討Class Imbalance Problem，有時我們會特別注意不常出現的類別，但許多分類技術卻會被佔大多數的類別所主導，此時我們常用的準確度衡量標準就不代表任何意義了。本節介紹許多替代的衡量標準，例如Confusion Matrix、F-Measure、ROC Curve，或是使用Cost-Sensitive Learning以避免發生嚴重的分類錯誤。

學習目標

1. 了解各種分類技術的特性，以求在不同的情況之下選擇適當的技術
2. 了解Ensemble Method的流程及為何能提高分類準確度
3. 有能力判斷在不同的情況下使用何種的衡量標準，而不是只會選擇Accuracy

Data Mining Chapter 4 Overview

2007-05-07T22:49:00.000-07:00

我們已經在前二章學習了各種資料的型態及許多前置處理的方法，從本章開始，我們將進入探勘技術的相關演算法。分類是資料分析中最常見的工作之一，本章即從分類的基本概念開始，介紹其中最簡單且具代表性的分類技術－－決策樹。決策樹的建立主要在決定每個節點所採用的區隔條件，最常用的便是利用Information Gain來評估那種區隔屬性最佳。因此決策樹的建立對離散型資料來說最為容易，比較麻煩的是處理數值型屬性，這時我們必須決定如何分裂屬性才會獲得最好結果。

分類模型的好壞可以準確率或錯誤率為評量，一般而言模型愈複雜或是訓練時間愈久，training error愈低，而testing error則可能減少(underfitting)，也可能增加(overfitting)。但由於testing error在訓練時是未知的，因此本章討論幾個預估generalization error的方法，做為training error的輔助，以避免可能發生的兩種狀況－overfitting及underfitting。

本章最後介紹利用測試集(test data)來衡量不同分類模型的效能。當我們透過同一份測試集來比較不同模型時，若只以簡單的分類準確率來評斷好壞是不客觀的，尤其若是使用不同的測試集更是如此，所以此時我們可利用統計檢定來評斷不同模型之間的效能差異，是否存在statistically significant，藉以得到較客觀的結果。

學習目標
1. 決策樹建立演算法
- Splitting Evaluation: Entropy, Gini Index, Misclassification Error.
- Generalization error的估計方法
2. 了解overfitting及underfitting的問題
3. 了解各種比較classifier的方法。

Data Mining Chapter 3 Overview

2007-03-22T21:37:00.000-07:00

本章可視為前一章主題「Data」的延伸，最主要是針對資料進行探索式分析，用以了解資料的特性，並幫助我們選擇適當的前置處理及後續資料資料的技術。本章包含三個重要的主題－Summary Statistics、Visualization和OLAP。Summary Statistics是利用統計常用的一些measure來描述資料集的特性；Visualization是利用人類比機器所擁有更強大功能的眼睛來看出資料的特性，因此如何將資料視覺化，讓我們能更輕易地觀察出資料的特性，是第二部份的挑戰；OLAP 操作通常附屬於資料庫或資料倉儲，它除了包含前面二者(Summary Statistics、Visualization)的功能之外，還提供分析高維度資料集Data Cube的五項操作(Slicing、Dicing、Roll-Up、Drill-Down及Pivot)。基本上，本章內容並不難。圖的部分不僅要能看懂，更要曉得該圖所要傳達的是何種資料的特性及關係。OLAP部分則會出作業以供同學們熟悉。

學習目標

1. 了解各種統計measure所代表的意義
variance, covariance, correlation, the p%th percentile
2. 了解各種現有資料視覺化方法及其優缺點
parallel coordinate, star coordinate
3. 了解OLAP及其操作元如何做為資料視覺化工具
multi-dimensional data model, cube operations: slice and dice, roll-up and drill-down

Data Mining Chapter 2 Overview

2007-03-09T17:01:00.000-08:00

一般而言，在進行探勘工作之前必須先評估所輸入資料，並做適當的前置處理工作，以便能應用在後續的探勘工作。本章將從資料本身的型態開始討論，敘述各型態資料的特性；其次探討三個常見的資料品質問題，並進行Cleaning。另外為了使資料適用於特定的探勘技術，我們通常要做資料的前置處理，例如Data Reduction、Feature Selection、Normalization、Discretization等來轉換原始資料。最後則是資料彼此間的關係(Similarity、Dissimilarity)的計算方法。概括而言，本章內容尚屬概念性介紹，並無較難理解的演算法，唯一的數學是統計的PCA及線代的SVD，請同學多花一點時間讀Appendix。

學習目標

了解何謂data matrix, transactional data, sequential data, sequence data及time series data
區分不同的資料屬性based on 4 properties: distinctness, order, addition, multiplication
資料品質的問題：outlier&noise, missing data, duplicate
資料前置處理工作：

Data Reduction by Samping
Dimension Reduction via PCA
Feature Selection by specific filtering algorithms
Feature Creation by feature extraction, mapping to new space, feature construction
Normalization
Discretization by equal width, equal depth, or clustering

Proximity Measure (distance and similarity)

Similarity: Jaccard measure, cosine measure, pearson's correlatio
Distance: Euclidean, mahalanobis distance

其他可能遭遇問題：例如

資料量過多或過少時
Attributes超過演算法處理上限
使用Regression時只能輸入數值型屬性的資料

Data Mining Chapter 1 Overview

2007-03-09T16:39:00.000-08:00

本章主要目的是讓初學者對資料探勘有初步的認識。書中一開始從人類為了要迅速掌握大量資料所隱藏的意義的角度來切入，並舉了許多Data Mining的應用來彰顯Data Mining的必要性及其威力。1.4節概述Data Mining Task可分為Predictive task及Descriptive task，再各自利用對資料不同的觀點來分成六種task(Classification、Clustering、Association analysis、Regression、Sequential Pattern Discovery及Deviation Detection)。最後本章也提及Data Mining於未來發展所將面臨的挑戰。

學習目標

什麼是Data Mining? 其挖掘知識的程序為何? (ppt 5)
為什麼我們需要Data Mining? 它能帶來什麼好處? (ppt 2 3 4)
六個常用 Data Mining Task的定義
Classification (ppt 10)
Clustering (ppt 17)
Association Rule Discovery (ppt 23)
Sequential Pattern Discovery (ppt 27)
Regression (ppt 29)
Deviation Detection (ppt 30)

Tentative Schedule

2007-03-02T00:58:00.000-08:00

Week 1 to 8: Instructor Teaching
Week 9: Mid-term Exam
Week 10 to 12: Reading Assignment
Week 13 to 15: Case Study
Week 16 to 18: Project presentation

Grading Policy

2007-03-02T00:56:00.000-08:00

Homework (25%)
Mid-term (25%)
Paper presentation (20%)
Final project (20%)
Course involvement (10%)

Course Syllabus for 2007

2007-02-26T21:34:00.000-08:00

Course Topics

Introduction
Data Preprocessing
Exploring Data
Classication: Basic Concepts, Decision Trees, and Model Evaluation
Classication: Alternative Techniques
Association Analysis: Basic Concepts and Algorithms
Association Analysis: Advanced Concepts
Cluster Analysis: Basic Concepts and Algorithms
Cluster Analysis: Additional Issues and Algorithms

Schedule

Week 1 to 8: Instructor Teaching
Week 9: Mid-term Exam
Week 10 to 12: Reading Assignment
Week 13 to 15: Case Study
Week 16 to 18: Project presentation

Textbooks

Pang-Ning Tan, Michael Steinbach, and Vipin Kumar, Introduction to Data Mining, Pearson International Edition, 2005. Slides: http://www-users.cs.umn.edu/~kumar/dmbook/index.php
Data Mining: Concepts and Techniques, J. Han and M. Kamber, Morgan Kaufmann , 2000. Slides: http://www.cs.sfu.ca/~han/DM_Book.html
Ethem Alpaydin, Introduction to Machine Learning, MIT Press, 2004. Slides: http://www.cs.umd.edu/class/spring2004/cmsc726/courseTopicsPage.html

Grading Policy

Homework (25%)
Mid-term (25%)
Paper presentation (20%)
Final project (20%)
Course involvement (10%)

Textbooks

2007-02-26T21:28:00.000-08:00

Pang-Ning Tan, Michael Steinbach, and Vipin Kumar, Introduction to Data Mining, Pearson International Edition, 2005. Slides: http://www-users.cs.umn.edu/~kumar/dmbook/index.php
Data Mining: Concepts and Techniques, J. Han and M. Kamber, Morgan Kaufmann , 2000. Slides: http://www.cs.sfu.ca/~han/DM_Book.html
Ethem Alpaydin, Introduction to Machine Learning, MIT Press, 2004. Slides: http://www.cs.umd.edu/class/spring2004/cmsc726/courseTopicsPage.html