1
KHAI THÁC
DỮ LIỆU &
ỨNG DỤNG
(DATA MINING)
GV : NGUYỄN HOÀNG TÚ ANH
2
BÀI 4 – PHẦN 1
PHÂN LỚP DỮ
LIỆU
3
NỘI DUNG
1. Gii thiu
2. Phương pháp dựa trên cây
quyết định
3. Phương pháp dựa trên luật
4
GIỚI THIỆU
1. Phân lớp :
Cho tập các mẫu đã phân lớp trước, xây
dựng mô hình cho từng lớp
Mc đích : Gán các mu mi vào các lp
vi đ chính xác cao nht có th.
Cho CSDL D={t
1
,t
2
,…,t
n
} và tập các lớp
C={C

 Tập huấn luyện : các mẫu / bộ dành
cho xây dựng mô hình
 Mỗi mẫu/ bộ thuộc về một lớp đã
định nghĩa trước
 Tìm lut phân lp, cây quyt đnh
hoc công thc toán mô t lp
7
GIỚI THIỆU
2. Qui trình phân lớp (tt) :
Bưc 2 : S dng mô hình
Phân lớp các đối tượng chưa biết
 Xác định độ chính xác của mô hình, sử
dụng tập DL kiểm tra độc lập
 Độ chính xác chấp nhận được -> áp
dụng mô hình để phân lớp các mẫu/bộ
chưa xác định được nhãn lớp
8
Ví dụ : XD mô hình
Training
Data
NAME RANK YEARS TENURED
Mike Assistant Prof 3 no
Mary Assistant Prof 7 yes
Bill Professor 2 yes
Jim Associate Prof 7 yes
Dave Assistant Prof 6 no
Anne Associate Prof 3 no
Classification
Algorithms
IF rank = ‘professor’

1. Giới thiệu
2. Phương pháp da
trên cây quyt đnh
3. Phương pháp dựa trên luật
12
CÂY QUYẾT ĐỊNH
1. Định nghĩa
2. Xây dựng cây quyết định
3. Thuật toán xây dựng cây quyết định
4. Cách phân chia mẫu
 Độ đo để lựa chọn thuộc tính
5. Vấn đề quá phù hợp với DL
6. Ưu điểm
13
CÂY QUYẾT ĐỊNH
1. Định nghĩa
Cây quyết định là một
cấu trúc phân cấp của
các nút và các nhánh
3 loại nút trên cây:
Nút gốc
Nút nội bộ : mang tên
thuộc tính của CSDL
Nút lá : mang tên lớp
C
i
Nhánh : mang giá trị
của thuộc tính
Nút gốcNút nội bộ
Nút lá

age?
student? credit rating?
no yes
fair
excellent
<=30
>40
no noyes yes
yes
31..40
17
CÂY QUYẾT ĐỊNH
3. Thuật toán xây dựng cây quyết
định
 Hunt’s Algorithm
 CART
 ID3, C4.5
 SLIQ, SPRINT
18
CÂY QUYẾT ĐỊNH
3. Thuật toán xây dựng cây quyết định
 Ý tưởng chính :
 Phương pháp “tham lam” (greedy)
 Phân chia tập mẫu dựa trên thuộc tính cho
kết quả tối ưu hóa tiêu chuẩn
 Vn đ :
 Xác định cách phân chia các mẫu
 Dựa trên độ đo sự đồng nhất của dữ liệu
 Điều kiện dừng
19

 C
i
,D
: tập các mẫu của D thuộc lớp C
i
với i = {1, …, m}
 |C
i
, D
|, |D| : lực lượng của tập C
i
,D
và D tương ứng
 p
i
là xác sut đ mt mu bt kỳ ca D thuc v lp C
i
 Thông tin kỳ vọng để phân lớp một mẫu trong D là :
)(log)(
2
1
i
m
i
i
ppDInfo
∑
=
−=
D

=“Mua “; C
2
=“Không mua”
 |C
1, D
|= 9, |C
2, D
|=5
Thông tin kỳ vọng để phân lớp một mẫu trong D
là :
940.0
14
5
log
14
5
14
9
log
14
9
)5,9I(
22
=−−==Info(D)
24
CÂY QUYẾT ĐỊNH
 Thuộc tính A có các giá trị :{a
1
, a
2

A
−=
25
VÍ DỤ 1 : INFORMATION GAIN
g Ký hiệu :
g Lớp P: buys_computer = “Yes”
g Lớp N: buys_computer = “No”
g Info(D) = I(9, 5) =0.940
g Tính đ li thông tin cho thuc tính “age” ?
age p
j
n
j
I(p
j
, n
j
)
<=30 2 3 0.971
31…40 4 0 0
>40 3 2 0.971
971.0
5
3
log
5
3
5
2
log

)2,3(
22
=−−=I
26
VÍ DỤ 1 : INFORMATION GAIN
g Tính đ li thông tin cho thuc tính “age” ?
g Khi đó :
694.0)2,3(
14
5
)0,4(
14
4
)3,2(
14
5
)( =++= IIIDInfo
age
246.0)()()( =−= DInfoDInfoageGain
age
g Suy ra :
27
BÀI TẬP
g Thời gian : 10’
g Cho tập DL như trong ví dụ 1
g Ký hiệu :
g Lớp P: buys_computer = “Yes”
g Lớp N: buys_computer = “No”
 Tính độ lợi thông tin dựa trên phân chia theo
thuộc tính

high no excellent no
medium no fair no
low yes fair yes
medium yes excellent yes
income student credit_rating buys_computer
high no fair yes
low yes excellent yes
medium no excellent yes
high yes fair yes
income student credit_rating buys_computer
medium no fair yes
low yes fair yes
low yes excellent no
medium yes fair yes
medium no excellent no
30
VÍ DỤ 1 : IG
age?
student? credit rating?
no yes
fair
excellent
<=30
>40
no noyes yes
yes
31..40