Khai Phá Dữ Liệu-Các kỹ thuật phân lớp và dự đoán

Khai Phá Dữ Liệu

Nguyễn Nhật Quang

quangnn-fit@mail.hut.edu.vn

Viện Công nghệ Thông tin và Truyền thông Trường Đại học Bách Khoa Hà Nội

Năm học 2010-2011

Nội dung môn học:

(cid:132) Giới thiệu về Khai phá dữ liệu

(cid:132) Giới thiệu về công cụ WEKA

ề

(cid:132) Tiền xử lý dữ liệu

(cid:132) Phát hiện các luật kết hợp

(cid:132) Các kỹ thuật phân lớp và dự đoán (cid:132) Các kỹ thuật phân lớp và dự đoán

(cid:137) Phân lớp bằng phương pháp học Bayes

(cid:132) Các kỹ thuật phân nhóm

Khai Phá Dữ Liệu

(cid:137) Học cây quyết định

Bài toán phân lớp

(cid:132) Bài toán phân lớp (Classification)

ập (cid:137) Đối với một tập các ví dụ/bản ghi (instances/records) – gọi là tập g (

) gọ

ộ ập

ụ

huấn luyện/học (training/learning set) (cid:132) Mỗi bản ghi được biểu diễn bằng một tập các thuộc tính, trong p (

đó có một thuộc tính phân lớp (class attribute) )

ộ

(cid:137) Tìm/học một hàm cho thuộc tính phân lớp (hàm phân lớp) đối

với các giá trị của các thuộc tính khác

(cid:132) Sử dụng một tập các ví dụ khác với các ví dụ học để

kiểm tra độ chính xác của hàm phân lớp học được – gọi là tập kiểm thử (test set) là tập kiểm thử (test set) (cid:137) Thông thường, tập dữ liệu ban đầu được chia thành 2 tập (không giao nhau): training set (để học hàm phân lớp) và test set (để kiểm thử hàm phân lớp học được) kiểm thử hàm phân lớp học được)

Khai Phá Dữ Liệu

Phân lớp vs. Dự đoán

(cid:132) Bài toán phân lớp (Classification problem)

(cid:137) Học một hàm mục tiêu có giá trị rời rạc (a discrete-valued target t

ó iá t ị ời

l d t

ột hà

( di

tiê

H function)

(cid:132) Miền giá trị: một tập các nhãn lớp (class labels) xác địn trước

(cid:137) Với mỗi ví dụ cần phân loại, hệ thống xác định nhãn lớp của nó

) (cid:132) Bài toán dự đoán/hồi quy (Prediction/regression problem)

q y (

ự

(cid:137) Học một hàm mục tiêu có giá trị liên tục (a continuous-valued

target function)

(cid:132) Miền giá trị: tập các giá trị số thực (real numbers) )

iá t ị ố th

iá t ị

Miề

tậ

(

(cid:137) Với mỗi ví dụ cần dự đoán, hệ thống xác định giá trị dự đoán của

nó

Khai Phá Dữ Liệu

Học có vs. không có giám sát

(cid:132) Học có giám sát (supervised learning)

(cid:137) Mỗi ví dụ học gồm 2 phần: mô tả (biểu diễn) của ví dụ học, và (cid:137) Mỗi ví dụ học gồm 2 phần: mô tả (biểu diễn) của ví dụ học và nhãn lớp (hoặc giá trị đầu ra mong muốn) của ví dụ học đó

(cid:137) Bài toán học phân lớp (classification problem)

D_train = {(, )} D train = {( )}

(cid:137) Bài toán học dự đoán/hồi quy (prediction/regression problem)

D_train = {(, )}

(cid:132) Học không có giám sát (unsupervised learning)

(cid:137) Mỗi ví dụ học chỉ chứa mô tả (biểu diễn) của ví dụ học đó - mà

không có bất kỳ thông tin nào về nhãn lớp hay giá trị đầu ra mong không có bất kỳ thông tin nào về nhãn lớp hay giá trị đầu ra mong muốn của ví dụ học đó

(cid:137) Bài toán học phân cụm (Clustering problem)

Tập học D_train = {()} Tập học D train = {()}

Khai Phá Dữ Liệu

Các khái niệm cơ bản về xác suất

(cid:132) Giả sử chúng ta có một thí nghiệm (ví dụ: đổ một quân xúc sắc) mà

kết quả của nó mang tính ngẫu nhiên (phụ thuộc vào khả năng có thể xảy ra)

(cid:132) Không gian các khả năng S. Tập hợp tất cả các kết quả có thể xảy ra Ví dụ: S {1,2,3,4,5,6} đối với thí nghiệm đổ quân xúc sắc Ví dụ: S= {1 2 3 4 5 6} đối với thí nghiệm đổ quân xúc sắc

ố

ắ

ổ

(cid:132) Sự kiện E. Một tập con của không gian các khả năng Ví dụ: E= {1}: kết quả quân súc xắc đổ ra là 1 Ví dụ: E= {1,3,5}: kết quả quân súc xắc đổ ra là một số lẻ ế

(cid:132) Không gian các sự kiện W. Không gian (thế giới) mà các kết quả của

ự ệ

sự kiện có thể xảy ra

Ví dụ: W bao gồm tất cả các lần đổ súc xắc

(cid:132) Biến ngẫu nhiên A. Một biến ngẫu nhiên biểu diễn (diễn đạt) một sự

kiện, và có một mức độ về khả năng xảy ra sự kiện này kiện và có một mức độ về khả năng xảy ra sự kiện này

Khai Phá Dữ Liệu

Biểu diễn xác suất

P(A): “Phần của không gian (thế giới) mà trong đó A là đúng”

(

g g

Không gian sự kiện (không gian của tất cả các giá trị có thể xảy ra của A)

Không gian mà trong đó A là đúng

Không gian mà Không gian mà trong đó A là sai

Khai Phá Dữ Liệu

[http://www.cs.cmu.edu/~awm/tutorials] [http://www cs cmu edu/~awm/tutorials]

Các biến ngẫu nhiên Bool

(cid:132) Một biến ngẫu nhiên Bool có thể nhận một trong 2 giá trị

đúng (true) hoặc sai (false) đúng (true) hoặc sai (false)

(cid:132) Các tiên đề

• 0 ≤ P(A) ≤ 1 • 0 ≤ P(A) ≤ 1

• P(true)= 1

P(false) 0 • P(false)= 0

• P(A V B)= P(A) + P(B) - P(A ∧ B)

(cid:132) Các hệ quả (cid:132) Các hệ quả

• P(not A)≡ P(~A)= 1 - P(A)

P(A) P(A ∧ B) + P(A ∧ B) • P(A)= P(A ∧ B) + P(A ∧ ~B)

Khai Phá Dữ Liệu

Các biến ngẫu nhiên nhiều giá trị

(

) g

2 vA

if 0 i

(

Một biến ngẫu nhiên nhiều giá trị có thể nhận một trong số k (>2) giá trị {v1,v2,…,vk} k ) =

1 =∧=

≠

vAP i

P(A=v1 V A=v2 V ... V A=vk) = 1

( (

) )

... ∨∨

∨

vAP vAP 1 1

vA vA =∨∨=∨= 2 2

vA vA i

∑ = ∑ ( vAP vAP (

1 =

1) =

jvAP

=∑ (

1=j

...

vABP

(

)

∧

=∧

( BP

[

] )

vA 1

vA =∨∨=∨= 2

vA i

∑

1j= 1 j

Khai Phá Dữ Liệu

[http://www.cs.cmu.edu/~awm/tutorials]

Xác suất có điều kiện (1)

(cid:132) P(A|B) là phần của không gian (thế giới) mà trong đó A

là đúng, với điều kiện (đã biết) là B đúng là đúng, với điều kiện (đã biết) là B đúng

(cid:132) Ví dụ

•A: Tôi sẽ đi đá bóng vào ngày mai

•B: Trời sẽ không mưa vào ngày mai

•P(A|B): Xác suất của việc tôi sẽ đi đá bóng vào

ngày mai nếu (đã biết rằng) trời sẽ không mưa (vào ngày mai) i)

Khai Phá Dữ Liệu

Xác suất có điều kiện (2)

) )

Định nghĩa: Định nghĩa:

BAP BAP | |

( (

) )

( ( , , BAP BP ( )

Các hệ quả:

ệ q

P(A,B)=P(A|B).P(B)

Không gian gian mà trong đó B đúng đú

P(A|B)+P(~A|B)=1

Không gian mà trong đó A đúng g

( (

| |

1) ) =

i BvAP =

∑ ∑

1 =

Khai Phá Dữ Liệu

Các biến độc lập về xác suất (1)

(cid:132) Hai sự kiện A và B được gọi là độc lập về xác suất nếu xác suất của sự kiện A là như nhau đối với các trường g hợp:

• Khi sự kiện B xảy ra, hoặc • Khi sự kiện B không xảy ra hoặc • Khi sự kiện B không xảy ra, hoặc • Không có thông tin (không biết gì) về việc xảy ra của sự kiện B

(cid:132) Ví dụ (cid:132) Ví dụ

•A: Tôi sẽ đi đá bóng vào ngày mai

g g y

ậ

•B: Tuấn sẽ tham gia trận đá bóng ngày mai

•P(A|B) = P(A)

→ “Dù Tuấn có tham gia trận đá bóng ngày mai hay không cũng không ảnh hưởng tới quyết định của tôi về việc đi đá bóng ngày mai.” ả h h ở i ”

ết đị h ủ tôi ề iệ đi đá bó

tới

Khai Phá Dữ Liệu

Các biến độc lập về xác suất (2)

Từ định nghĩa của các biến độc lập về xác suất P(A|B) P(A), chúng ta thu được các luật như sau P(A|B)=P(A), chúng ta thu được các luật như sau

• P(~A|B) = P(~A)

• P(B|A) = P(B)

• P(A,B) = P(A). P(B)

• P(~A,B) = P(~A). P(B)

• P(A,~B) = P(A). P(~B)

• P(~A,~B) = P(~A). P(~B)

Khai Phá Dữ Liệu

Xác suất có điều kiện với >2 biến

(cid:132) P(A|B,C) là xác suất của A đối với (đã

biết) B và C biết) à C

(cid:132) Ví dụ

• A: Tôi sẽ đi dạo bờ sông vào sáng mai

• B: Thời tiết sáng mai rất đẹp

• C: Tôi sẽ dậy sớm vào sáng mai i

C Tôi ẽ dậ ớ

P(A|B,C) P(A|B C)

• P(A|B,C): Xác suất của việc tôi sẽ đi dạo

ọ

(

dọc bờ sông vào sáng mai, nếu (đã biết rằng) g) g thời tiết sáng mai rất đẹp và tôi sẽ dậy sớm vào sáng mai

Khai Phá Dữ Liệu

Độc lập có điều kiện

(cid:132) Hai biến A và C được gọi là độc lập có điều kiện đối với biến B, nếu xác suất của A đối với B bằng xác suất của A biến B, nếu xác suất của A đối với B bằng xác suất của A đối với B và C

ị

(cid:132) Công thức định nghĩa: P(A|B,C) = P(A|B)

(cid:132) Ví dụ

• A: Tôi sẽ đi đá bóng vào ngày mai • B: Trận đá bóng ngày mai sẽ diễn ra trong nhà • C: Ngày mai trời sẽ không mưa • P(A|B,C)=P(A|B) P(A|B,C) P(A|B) → Nếu biết rằng trận đấu ngày mai sẽ diễn ra trong nhà, thì xác suất của việc tôi sẽ đi đá bóng ngày mai không phụ thuộc vào thời tiết vào thời tiết

Khai Phá Dữ Liệu

Các quy tắc quan trọng của xác suất

(cid:132) Quy tắc chuỗi (chain rule)

• P(A,B) = P(A|B).P(B) = P(B|A).P(A) • P(A B) = P(A|B) P(B) = P(B|A) P(A)

• P(A|B) = P(A,B)/P(B) = P(B|A).P(A)/P(B)

P(A,B|C) P(A,B,C)/P(C) P(A|B,C).P(B,C)/P(C) • P(A,B|C) = P(A,B,C)/P(C) = P(A|B,C).P(B,C)/P(C)

= P(A|B,C).P(B|C)

(cid:132) Độc lập về xác suất và độc lập có điều kiện Độc lập về xác suất và độc lập có điều kiện

• P(A|B) = P(A); nếu A và B là độc lập về xác suất

P(A,B|C) P(A|C).P(B|C); nếu A và B là độc lập có điều • P(A,B|C) = P(A|C).P(B|C); nếu A và B là độc lập có điều kiện đối với C

• P(A1,…,An|C) = P(A1|C)…P(An|C); nếu A1,…,An là độc lập

có điều kiện đối với C có điều kiện đối với C

Khai Phá Dữ Liệu

Định lý Bayes

(

DhP |

(

)

hPhDP | ). )( (DP DP ) ) (

(cid:132) P(h): Xác suất trước (prior probability) của giả thiết (vd: phân

lớp) h

(cid:132) P(D): Xác suất trước của sự kiện tập dữ liệu D được quan sát

ấ ủ

(cid:132) P(D|h): Xác suất của sự kiện tập dữ liệu D được quan sát,

nếu biết rằng giả thiết h là đúng

(cid:132) P(h|D): Xác suất (có điều kiện) của giả thiết h là đúng, nếu (cid:132) P(h|D): Xác suất (có điều kiện) của giả thiết h là đúng nếu

biết rằng tập dữ liệu D được quan sát → Các phương pháp suy diễn dựa trên xác suất sẽ sử dụng xác suất có điều kiện (posterior probability) này! dụng xác suất có điều kiện (posterior probability) này!

Khai Phá Dữ Liệu

Định lý Bayes – Ví dụ (1)

Giả sử chúng ta có tập dữ liệu sau (dự đoán 1 người có chơi tennis)?

Ngày Ngoài trời Ngày Ngoài trời

Nhiệt độ Nhiệt độ

Độ ẩm Độ ẩm

Chơi tennis Chơi tennis

Gió Gió

Nắng

Nóng

Cao

Yếu

Không

Nắng

Nóng

Cao

Mạnh

Không

N3 N3

Âm u Â

Nóng Nó

Cao C

Yếu Yế

Có Có

Mưa

Cao

Bình thường

Yếu

Có

Mưa

Mát mẻ

Bình thường

Yếu

Có

Mưa

Mát mẻ ẻ

Bình thường

Mạnh

Không

Âm u

Mát mẻ

Bình thường

Mạnh

Có

Nắng

Bình thường

Cao

Yếu

Không

Nắng ắ

Mát mẻ

Bình thường

Yếu ế

Có

N10

Mưa

Bình thường

Yếu

Có

N11

Nắng

Bình thường

Mạnh

Có

N12

Âm u

Bình thường

Cao

Mạnh

Có

Khai Phá Dữ Liệu

[Mitchell, 1997]

Định lý Bayes – Ví dụ (2)

(cid:132) Giả thiết h: Anh ta chơi tennis

(cid:132) Tập dữ liệu D: Ngoài trời là nắng và Gió là mạnh Tập dữ liệu D: Ngoài trời là nắng và Gió là mạnh

(cid:132) Xác suất P(h): Xác suất rằng anh ta chơi tennis (bất kể

) Ngoài trời như thế nào và Gió ra sao)

(cid:132) Xác suất P(D): Xác suất rằng Ngoài trời là nắng và Gió là

mạnh

(cid:132) P(D|h): Xác suất rằng Ngoài trời là nắng và Gió là mạnh,

nếu biết rằng anh ta chơi tennis

(cid:132) P(h|D): Xác suất rằng anh ta chơi tennis, nếu biết rằng P(h|D): Xác suất rằng anh ta chơi tennis nếu biết rằng Ngoài trời là nắng và Gió là mạnh

(cid:137) Giá trị xác suất có điều kiện này sẽ được dùng để dự đoán xem anh ta có

chơi tennis hay không?

Khai Phá Dữ Liệu

Cực đại hóa xác suất có điều kiện

(cid:132) Với một tập các giả thiết (các phân lớp) có thể H, hệ thống học

g

p

y

(

sẽ tìm giả thiết có thể xảy ra nhất (the most probable hypothesis) h(∈H) đối với các dữ liệu quan sát được D

(cid:132) Giả thiết h này được gọi là giả thiết cực đại hóa xác suất có

điều kiện (maximum a posteriori – MAP)

arg

DhP |

(

)

hMAP =

max Hh∈

(

(bởi định lý Bayes)

h MAP

arg max Hh∈ Hh ∈

hPhDP | ). )( (DP ( ) ) DP

hPhDP | )(

(

h MAP

(P(D) là như nhau ) đối với các giả thiết h) g

arg max Hh∈ Hh ∈

Khai Phá Dữ Liệu

MAP – Ví dụ

(cid:132) Tập H bao gồm 2 giả thiết (có thể)

• h1: Anh ta chơi tennis • h2: Anh ta không chơi tennis

(cid:132) Tính giá trị của 2 xác xuất có điều kiện: P(h1|D), P(h2|D) (cid:132) Giả thiết có thể nhất hMAP=h1 nếu P(h1|D) ≥ P(h2|D); ngược

lại thì hMAP=h2

(cid:132) Bởi vì P(D)=P(D,h1)+P(D,h2) là như nhau đối với cả 2 giả (cid:132) Bởi vì P(D)=P(D h )+P(D h ) là như nhau đối với cả 2 giả

thiết h1 và h2, nên có thể bỏ qua đại lượng P(D)

ậy,

( | 1)

( 1)

(cid:132) Vì vậy, cần tính 2 biểu thức: P(D|h1).P(h1) và P(D|h2).P(h2), và đưa ra quyết định tương ứng • Nếu P(D|h1).P(h1) ≥ P(D|h2).P(h2), thì kết luận là anh ta chơi tennis • Ngược lại, thì kết luận là anh ta không chơi tennis

i thì kết l ậ là

h t khô

h i t

Khai Phá Dữ Liệu

Đánh giá khả năng xảy ra cao nhất

(cid:132) Phương pháp MAP: Với một tập các giả thiết có thể H, cần g

ự ạ

ộ g

ị

tìm một giả thiết cực đại hóa giá trị: P(D|h).P(h) ( )

( | )

iả thiết đề

ất t ớ

(cid:132) Giả sử (assumption) trong phương pháp đánh giá khả năng xảy ra cao nhất (maximum likelihood estimation – MLE): Tất cả các giả thiết đều có giá trị xác suất trước như nhau: Tất ả á ó iá t ị á P(hi)=P(hj), ∀hi,hj∈H g

g p p

ự ạ

ị ( | ); (cid:132) Phương pháp MLE tìm giả thiết cực đại hóa giá trị P(D|h);

trong đó P(D|h) được gọi là khả năng xảy ra (likelihood) của dữ liệu D đối với h

(cid:132) Giả thiết cực đại hóa khả năng xảy ra (maximum likelihood lik lih d

đ i hó khả ă

ả

(

Giả thiết hypothesis)

hDP

(

)

h MLE

arg max Hh∈ Hh ∈

Khai Phá Dữ Liệu

MLE – Ví dụ

(cid:132) Tập H bao gồm 2 giả thiết có thể

• h1: Anh ta chơi tennis • h2: Anh ta không chơi tennis D: Tập dữ liệu (các ngày) mà trong đó thuộc tính Outlook có giá trị Sunny

và thuộc tính Wind có giá trị Strong

(cid:132) Tính 2 giá trị khả năng xảy ra (likelihood values) của dữ liệu D

đối với 2 giả thiết: P(D|h1) và P(D|h2)

• P(Ngoài-trời=Nắng, Gió=Mạnh | h1) = 1/8 • P(Ngoài-trời=Nắng Gió=Mạnh | h ) = 1/8 • P(Ngoài-trời=Nắng, Gió=Mạnh | h2) = 1/4

g ợ

(cid:132) Giả thiết MLE hMLE=h1 nếu P(D|h1) ≥ P(D|h2); và ngược

MLE

lại thì hMLE=h2

ậ

ạ

→ Bởi vì P(Ngoài-trời=Nắng, Gió=Mạnh | h1) < P(Ngoài- trời=Nắng, Gió=Mạnh | h2), hệ thống kết luận rằng: Anh ta sẽ | 2), ệ không chơi tennis!

Khai Phá Dữ Liệu

Phân loại Naïve Bayes (1)

(cid:132) Biểu diễn bài toán phân loại (classification problem)

• Một tập học D_train, trong đó mỗi ví dụ học x được biểu diễn là • Một tập học D train trong đó mỗi ví dụ học x được biểu diễn là

một vectơ n chiều: (x1, x2, ..., xn)

• Một tập xác định các nhãn lớp: C={c1, c2, ..., cm} • Với một ví dụ (mới) z, z sẽ được phân vào lớp nào?

(cid:132) Mục tiêu: Xác định phân lớp có thể (phù hợp) nhất đối với z

arg

)

MAP

cP ( i

max Cc i∈

c c

arg arg

cP ( ( cP

| |

z z

,...,

z z

) )

MAP MAP

i i

z z 1 1

2 2

max max Cc i∈

)

zP ( 1

(bởi định lý Bayes)

arg

MAP

,..., , , z

| n ,..., ,...,

cPc ). ( i ) ) z

z , 2 ( ( zP 1 1

2 2

n n

max Cci∈ Cc i∈

Khai Phá Dữ Liệu

Phân loại Naïve Bayes (2)

(cid:132) Để tìm được phân lớp có thể nhất đối với z…

arg

,...,

| |

) )

MAP

zP ( ( 1

cPc ( ). ) ( i

(P(z1,z2,...,zn) là z ) là (P(z z như nhau với các lớp)

max Cc i∈

(cid:132) Giả sử (assumption) trong phương pháp phân loại Naïve (cid:132) Giả sử (assumption) trong phương pháp phân loại Naïve Bayes. Các thuộc tính là độc lập có điều kiện (conditionally independent) đối với các lớp

( zP

,...,

)

( zP 1

n n ∏ 1 j = (cid:132) Phân loại Naïve Bayes tìm phân lớp có thể nhất đối với z (cid:132) Phân loại Naïve Bayes tìm phân lớp có thể nhất đối với z

arg

( cP

( zP

)

j j

∏ ). 1 =

max Cc ∈ i

Khai Phá Dữ Liệu

Phân loại Naïve Bayes – Giải thuật

(cid:132) Giai đoạn học (training phase), sử dụng một tập học Đối với mỗi phân lớp có thể (mỗi nhãn lớp) ci∈C

ộ p

ộ

ị

• Tính giá trị xác suất trước: P(ci) • Đối với mỗi giá trị thuộc tính xj, tính giá trị xác suất xảy ra của giá trị thuộc tính đó đối với một phân lớp ci: P(xj|ci) ( j| i)

p i

(cid:132) Giai đoạn phân lớp (classification phase), đối với một ví dụ mới

• Đối với mỗi phân lớp ci∈C, tính giá trị của biểu thức:

( xP

)

( cP i

c i

∏ ).

1 =

• Xác định phân lớp của z là lớp có thể nhất c*

arg

( xP

)

( cP i

c i

∏ ).

max Cci Cc ∈ ∈

1 1 =

Khai Phá Dữ Liệu

Phân lớp Naïve Bayes – Ví dụ (1)

Một sinh viên trẻ với thu nhập trung bình và mức đánh giá tín dụng bình thường sẽ mua một cái máy tính?

Rec. ID Income Student Credit_Rating Buy_Computer Age

Young 1 High No Fair No

Young 2 High No Excellent No

Medium 3 High No Fair Yes

Old Old 4 4 Medium M di No N Fair F i Yes Y

Old 5 Low Yes Fair Yes

Old 6 Low Yes Excellent No

Medium Medium 7 7 Low Low Yes Yes Excellent Excellent Yes Yes

Young 8 Medium No Fair No

Young 9 Low Yes Fair Yes

Old 10 Medium Yes Fair Yes

Young 11 Medium Yes Excellent Yes

Medium 12 Medium No Excellent Yes

Medium 13 High Yes Fair Yes

Khai Phá Dữ Liệu

http://www.cs.sunysb.edu /~cse634/lecture_notes/0 7classification.pdf

Old 14 Medium No Excellent No

Phân lớp Naïve Bayes – Ví dụ (2)

(cid:132) Biểu diễn bài toán phân loại

• z = (Age=Young Income=Medium Student=Yes Credit Rating=Fair) z (Age Young,Income Medium,Student Yes,Credit_Rating Fair) • Có 2 phân lớp có thể: c1 (“Mua máy tính”) và c2 (“Không mua máy

tính”)

(cid:132) Tính giá trị xác suất trước cho mỗi phân lớp

• P(c1) = 9/14 • P(c2) = 5/14 • P(c ) = 5/14

(cid:132) Tính giá trị xác suất của mỗi giá trị thuộc tính đối với mỗi phân lớp

( g

g| 1)

• P(Age=Young|c1) = 2/9; ; • P(Income=Medium|c1) = 4/9; • P(Student=Yes|c1) = 6/9; • P(Credit_Rating=Fair|c1) = 6/9;

Khai Phá Dữ Liệu

Phân lớp Naïve Bayes – Ví dụ (3)

(cid:132) Tính toán xác suất có thể xảy ra (likelihood) của ví dụ z đối với mỗi

phân lớp ố• Đối với phân lớp c1

• Đối với phân lớp c2

(cid:132) Xác định phân lớp có thể nhất (the most probable class)

• Đối với phân lớp c1

P(c1).P(z|c1) = (9/14).(0.044) = 0.028 P(c ) P(z|c ) = (9/14) (0 044) = 0 028

• Đối với phân lớp c2

P(c2).P(z|c2) = (5/14).(0.019) = 0.007

→ Kết luận: Anh ta (z) sẽ mua một máy tính!

Khai Phá Dữ Liệu

Phân lớp Naïve Bayes – Vấn đề (1)

(cid:132) Nếu không có ví dụ nào gắn với phân lớp ci có giá trị thuộc tính xj…

ậy

, P(xj|ci)=0 , và vì vậy: ( j| i)

xP ( ( xP

| |

0) 0) = =

cP ( ( cP i

c c i

∏ ∏ ). )

=j 1

) )

( (

(cid:132) Giải pháp: Sử dụng phương pháp Bayes để ước lượng P(xj|ci) mp

)

( xP

c i

j )

, xcn i cn ( i

ụ ọ g

ợ g

( i)

p i • n(ci): số lượng các ví dụ học gắn với phân lớp ci • n(ci,xj): số lượng các ví dụ học gắn với phân lớp ci có giá trị thuộc

tính xj

• p: ước lượng đối với giá trị xác suất P(xj|ci)

→ Các ước lượng đồng mức: p=1/k, với thuộc tính fj có k giá trị có thể

• m: một hệ số (trọng số)

→ Để bổ sung cho n(ci) các ví dụ thực sự được quan sát với thêm

m mẫu ví dụ với ước lượng p

Khai Phá Dữ Liệu

Phân lớp Naïve Bayes – Vấn đề (2)

(cid:132) Giới hạn về độ chính xác trong tính toán của máy tính P(xj|ci)<1, đối với mọi giá trị thuộc tính xj và phân lớp ci •P(xj|ci)<1 đối với mọi giá trị thuộc tính xj và phân lớp ci • Vì vậy, khi số lượng các giá trị thuộc tính là rất lớn, thì:

( ( xP

) )

| | j c j

i i

∏ ∏

lim n ∞→

⎛ ⎜ ⎜ ⎜ ⎝

⎞ ⎟ =⎟ ⎟ ⎠

(cid:132) Giải pháp: Sử dụng hàm lôgarit cho các giá trị xác suất

arg

log

( xP

)

( cP i

c i

∏ ).

max Cc ∈ i

1 =

⎡ ⎢ ⎣

⎤ ⎥ ⎦

⎞ ⎟ ⎟ ⎠

arg

log

)

log

( xP

)

( cP i

c i

∑

max Cc ∈ i

1 =

⎛ ⎜ ⎜ ⎝ ⎛ ⎜ ⎜ ⎝

⎞ ⎟ ⎟ ⎠

Khai Phá Dữ Liệu

Phân loại văn bản bằng NB (1)

(cid:132) Biểu diễn bài toán phân loại văn bản

• Tập học D_train, trong đó mỗi ví dụ học là một biểu diễn văn bản gắn với

một nhãn lớp: D = {(dk, ci)}

• Một tập các nhãn lớp xác định: C = {ci}

(cid:132) Giai đoạn học (cid:132) Giai đoạn học

• Từ tập các văn bản trong D_train, trích ra tập các từ khóa

(keywords/terms): T = {tj} • Gọi D ci (⊆D train) là tập các văn bản trong D train có nhãn lớp ci Gọi D_ci (⊆D_train) là tập các văn bản trong D_train có nhãn lớp ci • Đối với mỗi phân lớp ci

cD _ i

)

cP ( i

- Tính giá trị xác suất trước của phân lớp ci:

)

(

, tdn k

- Đối với mỗi từ khóa tj, tính xác suất từ khóa tj xuất hiện đối với lớp ci ) 1 +

cDd i

( tP

)

j j

(n(dk,tj): số lần xuất hiện của từ khóa tj trong văn bản dk) từ khóa tj trong văn bản dk)

( (

) )

+ +

, tdn td mk

) T ) T

( ( ∑ ∑

cDd

( ∑ ∈ _ ∑∈ ∑

T ∈

Khai Phá Dữ Liệu

Phân loại văn bản bằng NB (2)

(cid:132) Để phân lớp cho một văn bản mới d (cid:132) Giai đoạn phân lớp (cid:132) Giai đoạn phân lớp

• Từ văn bản d, trích ra tập T_d gồm các từ khóa (keywords) tj đã

được định nghĩa trong tập T (T_d ⊆ T)

ất hiệ đối ới lớ

ất từ khó

) Xá

ti

• Giả sử (assumption). Xác suất từ khóa tj xuất hiện đối với lớp

Giả ử ( ci là độc lập đối với vị trí của từ khóa đó trong văn bản

P(tj ở vị trí k|ci) = P(tj ở vị trí m|ci), ∀k,m

• Đối với mỗi phân lớp ci, tính giá trị likelihood của văn bản d đối

với ci

( cP

( tP

)

∏

_ dT dT

). t t j ∈ ∈ • Phân lớp văn bản d thuộc vào lớp c*

arg

( cP

( tP

)

j j

). t

∏ _ dT

max Cc ∈ i

∈ j

Khai Phá Dữ Liệu

Học cây quyết định – Giới thiệu

(cid:132) Học cây quyết định (Decision tree –DT– learning)

• Để học (xấp xỉ) một hàm mục tiêu có giá trị rời rạc (discrete- • Để học (xấp xỉ) một hàm mục tiêu có giá trị rời rạc (discrete-

valued target function) – hàm phân lớp

• Hàm phân lớp được biểu diễn bởi một cây quyết định

(cid:132) Một cây quyết định có thể được biểu diễn (diễn giải) bằng một

tập các luật IF-THEN (dễ đọc và dễ hiểu)

(cid:132) Học cây quyết định có thể thực hiện ngay cả với các dữ liệu có ó

ết đị h ó thể th

ả ới á dữ liệ

hiệ

H chứa nhiễu/lỗi (noisy data)

ộ

(cid:132) Là một trong các phương pháp học quy nạp (inductive

g p p ọ q y ạp (

p learning) được dùng phổ biến nhất

(cid:132) Được áp dụng thành công trong rất nhiều các bài toán ứng

dụng thực tế d tế th

Khai Phá Dữ Liệu

Ví dụ về DT: Những tin tức nào mà tôi quan tâm?

“sport”?

is present

is absent

“player”?

“football”?

is absent

is present

is absent

Interested

“goal”?

Interested

Uninterested

is absent

is present

Interested

Uninterested

• (…,“sport”,…,“player”,…)

→ Interested

• (…,“goal”,…)

→ Interested

• (…, sport ,…) • ( ) “sport”

→ Uninterested → Uninterested

Khai Phá Dữ Liệu

Ví dụ về DT: Một người có chơi tennis không?

Outlook=?

Sunny

Rain

Overcast

Humidity=?

Wind=?

Yes

Strong

Weak

Normal

High

Yes

• (Outlook=Overcast, Temperature=Hot, Humidity=High,

→ Yes

Wind=Weak)

St o g) • (Outlook=Rain, Temperature=Mild, Humidity=High, Wind=Strong)

g ,

a → No

• (Outlook=Sunny, Temperature=Hot, Humidity=High, Wind=Strong)

→ No → No

Khai Phá Dữ Liệu

Biểu diễn cây quyết định (1)

(cid:132) Mỗi nút trong (internal node) biểu diễn một thuộc tính cần kiểm tra giá trị (an attribute to be tested) đối với các ví dụ kiểm tra giá trị (an attribute to be tested) đối với các ví dụ

(cid:132) Mỗi nhánh (branch) từ một nút sẽ tương ứng với một giá

trị có thể của thuộc tính gắn với nút đó trị có thể của thuộc tính gắn với nút đó

(cid:132) Mỗi nút lá (leaf node) biểu diễn một phân lớp (a

classification))

(cid:132) Một cây quyết định học được sẽ phân lớp đối với một ví

dụ, bằng cách duyệt cây từ nút gốc đến một nút lá

yệ

ụ,

ộ

→ Nhãn lớp gắn với nút lá đó sẽ được gán cho ví dụ cần phân lớp

Khai Phá Dữ Liệu

Biểu diễn cây quyết định (2)

(cid:132) Một cây quyết định biểu diễn một phép tuyển (disjunction) của các kết hợp (conjunctions) của các ràng buộc đối với của các kết hợp (conjunctions) của các ràng buộc đối với các giá trị thuộc tính của các ví dụ

(cid:132) Mỗi đường đi (path) từ nút gốc đến một nút lá sẽ tương (cid:132) Mỗi đường đi (path) từ nút gốc đến một nút lá sẽ tương ứng với một kết hợp (conjunction) của các kiểm tra giá trị thuộc tính (attribute tests)

(cid:132) Cây quyết định (bản thân nó) chính là một phép tuyển

(disjunction) của các kết hợp (conjunctions) này

(cid:132) Các ví dụ

→ Hãy xét 2 cây quyết định đã nêu ở trước…

Khai Phá Dữ Liệu

Những tin tức nào mà tôi quan tâm?

“sport”?

is present

is absent

“player”?

“football”?

is present

is absent

is present

Interested

“goal”?

Uninterested

Interested

is present

is absent

Interested

Uninterested

( p aye

[(“sport” is present) ∧ (“player” is present)] ∨ [( spo t

s p ese t)]

s p ese t)

[(“sport” is absent) ∧ (“football” is present)] ∨

[( sport is absent) ∧ ( football is absent) ∧ ( goal is present)] [(“sport” is absent) ∧ (“football” is absent) ∧ (“goal” is present)]

Khai Phá Dữ Liệu

Một người có chơi tennis không?

Outlook=?

Sunny

Rain

Overcast Overcast

Humidity=?

Wind=?

Yes

High

Strong

Weak

Normal Normal

Yes

[(Outlook=Sunny) ∧ (Humidity=Normal)] ∨

(Outlook Overcast) ∨ (Outlook=Overcast) ∨

[(Outlook=Rain) ∧ (Wind=Weak)]

Khai Phá Dữ Liệu

Giải thuật ID3 – Ý tưởng

(cid:132) Thực hiện quá trình tìm kiếm greedy search đối với không gian các cây

quyết định có thể

(cid:132) Xây dựng (học) một cây quyết định theo chiến lược top-down, bắt đầu

từ nút gốc

(cid:132) Ở mỗi nút, thuộc tính kiểm tra (test attribute) là thuộc tính có khả năng (cid:132) Ở mỗi nút thuộc tính kiểm tra (test attribute) là thuộc tính có khả năng

phân loại tốt nhất đối với các ví dụ học gắn với nút đó

(cid:132) Tạo mới một cây con (sub-tree) của nút hiện tại cho mỗi giá trị có thể

của thuộc tính kiểm tra, và tập học sẽ được tách ra (thành các tập con) của thuộc tính kiểm tra và tập học sẽ được tách ra (thành các tập con) tương ứng với cây con vừa tạo

(cid:132) Mỗi thuộc tính chỉ được phép xuất hiện tối đa 1 lần đối với bất kỳ một

đường đi nào trong cây đ ờ â đi à t

(cid:132) Quá trình phát triển (học) cây quyết định sẽ tiếp tục cho đến khi…

• Cây quyết định phân loại hoàn toàn (perfectly classifies) các ví dụ học, hoặc • Tất cả các thuộc tính đã được sử dụng

Khai Phá Dữ Liệu

Giải thuật ID3

l b l R t

th t

f th

ID3_alg(Training_Set, Class_Labels, Attributes) Create a node Root for the tree If all instances in Training_Set have the same class label c, Return the tree of the i If

i i

ll i single-node Root associated with class label c

If the set Attributes is empty, Return the tree of the single-node Root associated with

class label ≡ Majority_Class_Label(Training_Set)

A ← The attribute in Attributes that “best” classifies Training_Set The test attribute for node Root ← A For each possible value v of attribute A

tt ib t

th t

t “

Add a new tree branch under Root, corresponding to the test: “value of attribute A is v” ” Add Compute Training_Setv = {instance x | x ⊆ Training_Set, xA=v} If (Training_Setv is empty) Then

Create a leaf node with class label ≡ Majority Class Label(Training Set) Create a leaf node with class label Majority_Class_Label(Training_Set) Attach the leaf node to the new branch

Else Attach to the new branch the sub-tree ID3_alg(Training_Setv,

Class_Labels, {Attributes \ A})

Return Root R t

Khai Phá Dữ Liệu

Lựa chọn thuộc tính kiểm tra

(cid:132) Rất quan trọng: tại mỗi nút, chọn thuộc tính kiểm tra như thế nào? ụ ọ g (cid:132) Chọn thuộc tính quan trọng nhất cho việc phân lớp các ví dụ học gắn

ệ p

ọ g

ọ

ộ với nút đó

(cid:132) Làm thế nào để đánh giá khả năng của một thuộc tính đối với việc

ụ ọ

phân tách các ví dụ học theo nhãn lớp của chúng? p → Sử dụng một đánh giá thống kê – Information Gain

(cid:132) Ví dụ: Xét bài toán phân lớp có 2 lớp (c1, c2)

→ Thuộc tính nào, A1 hay A2, nên được chọn là thuộc tính kiểm tra? → Thuộc tính nào A hay A nên được chọn là thuộc tính kiểm tra?

v11

A2=? (c1: 35, c2: 25) v22

v21

A1=? (c1: 35, c2: 25) v13

v12

c1: 21 c2: 9 : 9

c1: 5 c2: 5 : 5

c1: 9 c2: 11 : 11

c1: 27 c2: 6 : 6

c1: 8 c2: 19 : 19

Khai Phá Dữ Liệu

Entropy

(cid:132) Một đánh giá thường được sử dụng trong lĩnh vực Information Theory ộ ập (cid:132) Để đánh giá mức độ hỗn tạp (impurity/inhomogeneity) của một tập

ạp ( p

ộ

(cid:132) Entropy của tập S đối với việc phân lớp có c lớp

Entropy

)( S

log.

p i

∑ −

=i 1

trong đó pi là tỷ lệ các ví dụ trong tập S thuộc vào lớp i, và 0.log20=0

ệ p

ập

p (cid:132) Entropy của tập S đối với việc phân lớp có 2 lớp

py Entropy(S) = -p1.log2p1 – p2.log2p2

(cid:132) Ý nghĩa của entropy trong lĩnh vực Information Theory

→ Entropy của tập S chỉ ra số lượng bits cần thiết để mã hóa lớp của một

phần tử được lấy ra ngẫu nhiên từ tập S

Khai Phá Dữ Liệu

Entropy – Ví dụ với 2 lớp

(cid:132) S gồm 14 ví dụ, trong đó 9 ví dụ thuộc về lớp c1

và 5 ví dụ thuộc về lớp c2 và 5 ví dụ thuộc về lớp c

)

(cid:132) Entropy của tập S đối với phân lớp có 2 lớp: Entropy(S) = -(9/14).log2(9/14)-

S ( y p o r t n E

2 (5/14).log2(5/14) ≈ 0.94

0.5

(cid:132) Entropy =0, nếu tất cả các ví dụ thuộc cùng một

0 1

lớp (c1 hoặc c2) lớp (c hoặc c )

(cid:132) Entropy =1, số lượng các ví dụ thuộc về lớp c1 bằng số lượng các ví

dụ thuộc về lớp c2 dụ thuộc về lớp c2

(cid:132) Entropy = một giá trị trong khoảng (0,1), nếu như số lượng các ví dụ

thuộc về lớp c1 khác với số lượng các ví dụ thuộc về lớp c2

Khai Phá Dữ Liệu

0.5 p1 p1

Information Gain

(cid:132) Information Gain của một thuộc tính đối với một tập các ví dụ:

• Mức độ giảm về Entropy • Bởi việc phân chia (partitioning) các ví dụ theo các giá trị của thuộc tính đó

ở

ủ

(cid:132) Information Gain của thuộc tính A đối với tập S

Gain

AS ,( )

Entropy

S )(

Entropy

(

)

−

∑

S | S | v S |

| | |

Values

(

)

v ∈

trong đó Values(A) là tập các giá trị có thể của thuộc tính A, và

Sv = {x | x∈S, xA=v}

(cid:132) Trong công thức trên, thành phần thứ 2 thể hiện giá trị Entropy sau khi tập S được phân chia bởi các giá trị của thuộc tính A sau khi tập S được phân chia bởi các giá trị của thuộc tính A

ế

(cid:132) Ý nghĩa của Gain(S,A): Số lượng bits giảm được (reduced) đối với việc mã hóa lớp của một phần tử được lấy ra ngẫu nhiên từ tập S, khi biết giá trị của thuộc tính A

Khai Phá Dữ Liệu

Tập các ví dụ học

Xét tập dữ liệu S ghi lại những ngày mà một người chơi (không chơi) tennis:

Day Outlook Temperature Humidity Play Tennis Wind

D1 Sunny Hot High Weak No

D2 Sunny Hot High Strong No

D3 Overcast Hot High Weak Yes

D4 D4 Rain R i Mild Mild High Hi h Weak W k Yes Y

D5 Rain Cool Normal Weak Yes

D6 Rain Cool Normal Strong No

D7 D7 Overcast Overcast Cool Cool Normal Normal Strong Strong Yes Yes

D8 Sunny Mild High Weak No

D9 Sunny Cool Normal Weak Yes

D10 Rain Mild Normal Weak Yes

D11 Sunny Mild Normal Strong Yes

D12 Overcast Mild High Strong Yes

D13 Overcast Hot Normal Weak Yes

D14 Rain Mild High Strong No

Khai Phá Dữ Liệu

[Mitchell, 1997]

Information Gain – Ví dụ

(cid:132) Hãy tính giá trị Information Gain của thuộc tính Wind đối với tập học S

– Gain(S,Wind)?

(cid:132) Thuộc tính Wind có 2 giá trị có thể: Weak và Strong

(cid:132) S = {9 ví dụ lớp Yes và 5 ví dụ lớp No}

(cid:132) Sweak = {6 ví dụ lớp Yes và 2 ví dụ lớp No có giá trị Wind=Weak} (cid:132) Sstrong = {3 ví dụ lớp Yes và 3 ví dụ lớp No có giá trị Wind=Strong}

Gain

S ,(

Wind

)

Entropy

S )(

Entropy

(

)

−

∑

| |

S v S

| |

Strong

}

v Weak { ∈

Entropy

S )(

).14/8(

Entropy

(

)

).14/6(

Entropy

(

)

−

S Weak

Strong

94.0 94.0

14/8( 14/8(

)81.0).( )81.0).(

14/6( 14/6(

048 048

−

.0)1).( .0)1).( =

Khai Phá Dữ Liệu

Học cây quyết định – Ví dụ (1)

(cid:132) Tại nút gốc, thuộc tính nào trong số {Outlook, Temperature,

ợ

ọ

ộ

}

Humidity, Wind} nên được chọn là thuộc tính kiểm tra?

• Gain(S, Outlook) = ... = 0.246 • Gain(S, Temperature) = ... = 0.029 • Gain(S Humidity) = Gain(S, Humidity) = ... = 0.151 = 0 151 • Gain(S, Wind) = ... = 0.048

→Vì vậy, Outlook được chọn là thuộc tính kiểm tra cho nút gốc!

S={9+, 5-}

Outlook=?

Sunny

Rain

Overcast Overcast

Node1

Node2

Yes } SOvercast={4+, 0-} Overcast {

SSunny={2+, 3-} SS ={2+ 3-}

SRain={3+, 2-} SR i ={3+ 2-}

Khai Phá Dữ Liệu

Học cây quyết định – Ví dụ (2)

(cid:132) Tại nút Node1, thuộc tính nào

Outlook=? S={9+, 5-}

idi

Sunny

Overcast

Rain

SSunny= {2+, 3-}

Node2 Node2

Humidity=? H idit ?

Yes Yes SOvercast= {4+, 0-}

trong số {Temperature, Humidity, Wind} nên được i d} ê đ chọn là thuộc tính kiểm tra? Lưu ý! Thuộc tính Outlook bị loại ra bởi loại ra, bởi vì nó đã được sử ì nó đã đ ợc sử dụng bởi cha của nút Node1 (là nút gốc)

SRain= {3+, 2-}

High High

Normal Normal

• Gain(SSunny, Temperature) =...= Temperature) = = • Gain(S 0.57

Node3

Node4

...

• Gain(SSunny, Humidity) = ... = 0.97 • Gain(SSunny, Wind) = ... = 0.019 0.019 Gain(SSunny, Wind)

S SHigh= {0+, 3-}

S SNormal= {2+, 0-}

→Vì vậy, Humidity được chọn là thuộc tính kiểm tra cho nút Node1!

Khai Phá Dữ Liệu

Học cây quyết định – Chiến lược tìm kiếm (1)

(cid:132) ID3 tìm kiếm trong không gian các giả thiết (các cây

quyết định có thể) một cây quyết định phù hợp (fits) các quyết định có thể) một cây quyết định phù hợp (fits) các ví dụ học

ID3 thực hiện chiến lược tìm kiếm từ đơn giản đến phức (cid:132) ID3 thực hiện chiến lược tìm kiếm từ đơn giản đến phức tạp, bắt đầu với cây rỗng (empty tree)

(cid:132) Quá trình tìm kiếm của ID3 được điều khiển bởi độ đo

ợ

ộ

đánh giá Information Gain

y (cid:132) ID3 chỉ tìm kiếm một (chứ không phải tất cả các) cây

g p

(

)

quyết định phù hợp với các ví dụ học

Khai Phá Dữ Liệu

Học cây quyết định – Chiến lược tìm kiếm (2)

(cid:132) Trong quá trình tìm kiếm, ID3 không thực hiện quay lui

(not backtrack) (not backtrack)

→ Chỉ đảm bảo tìm được lời giải tối ưu cục bộ (locally optimal

solution) – chứ không đảm bảo tìm được lời giải tối ưu tổng thể (globally optimal solution) (globally optimal solution)

→ Một khi một thuộc tính được chọn là thuộc tính kiểm tra cho một

nút, thì ID3 không bao giờ cân nhắc lại (backtracks to reconsider) lựa chọn này à

id ) l

(cid:132) Ở mỗi bước trong quá trình tìm kiếm, ID3 sử dụng một đánh giá thống kê (Information Gain) để cải thiện giả thiết hiện tại giá thống kê (Information Gain) để cải thiện giả thiết hiện tại

→ Nhờ vậy, quá trình tìm kiếm (lời giải) ít bị ảnh hưởng bởi các lỗi

(nếu có) của một số ít ví dụ học

Khai Phá Dữ Liệu

Ưu tiên trong học cây quyết định (1)

(cid:132) Cả 2 cây quyết định dưới đây đều phù hợp với tập học đã cho

(cid:132) Vậy thì, cây quyết định nào sẽ được ưu tiên (được học) bởi Vậy thì cây quyết định nào sẽ được ưu tiên (được học) bởi giải thuật ID3?

Outlook=? O tl k ?

Outlook=?

Yes Y

Temperature=?

Wind=?

Humidity=?

Wind=?

Sunny Rain Sunny Rain Overcast Overcast

No No

Yes Yes

No No

Yes Yes

No No

Yes Yes

No No

Yes Yes

Humidity=? Humidity=?

Hot Strong Weak High Normal Strong Weak Cool Mild

Yes

Khai Phá Dữ Liệu

High Normal

Ưu tiên trong học cây quyết định (2)

(cid:132) Đối với một tập các ví dụ học, có thể tồn tại nhiều (hơn 1)

cây quyết định phù hợp với các ví dụ học này cây quyết định phù hợp với các ví dụ học này

(cid:132) Cây quyết định nào (trong số đó) được chọn?

(cid:132) ID3 chọn cây quyết định phù hợp đầu tiên tìm thấy trong

ết đị h hù h

đầ tiê tì

thấ t

â ID3 h quá trình tìm kiếm của nó

→Lưu ý là trong quá trình tìm kiếm, giải thuật ID3 không bao giờ

cân nhắc lại các lựa chọn trước đó (without backtracking)

(cid:132) Chiến lược tìm kiếm của giải thuật ID3

• Ưu tiên các cây quyết định đơn giản (ít mức độ sâu) iả (ít ứ độ â ) ết đị h đ

Ư tiê

• Ưu tiên các cây quyết định trong đó một thuộc tính có giá trị

Information Gain càng lớn thì sẽ là thuộc tính kiểm tra của một nút càng gần nút gốc ố ầ

Khai Phá Dữ Liệu

Các vấn đề trong học cây quyết định

(cid:132) Cây quyết định học được quá phù hợp (over-fit) với các

ví dụ học ví dụ học

(cid:132) Xử lý các thuộc tính có kiểu giá trị liên tục (kiểu số thực)

(cid:132) Các đánh giá phù hợp hơn (tốt hơn Information Gain) đối ti G i ) đối

(tốt h

I f

h Cá đá h iá hù h với việc xác định thuộc tính kiểm tra cho một nút

(cid:132) Xử lý các ví dụ học thiếu giá trị thuộc tính (missing-value (cid:132) Xử lý các ví dụ học thiếu giá trị thuộc tính (missing value

attributes)

(cid:132) Xử lý các thuộc tính có chi phí (cost) khác nhau (cid:132) Xử lý các thuộc tính có chi phí (cost) khác nhau

→ Cải tiến của giải thuật ID3 với tất cả các vấn đề nêu trên

được giải quyết: giải thuật C4.5 được giải quyết: giải thuật C4 5

Khai Phá Dữ Liệu

Khai Phá Dữ Liệu-Các kỹ thuật phân lớp và dự đoán

Chủ đề:

Trực quan hóa dữ liệu