Bài giảng Máy học và Mạng Neural: Bài 3 mới nhất từ TS. Vũ Đức Lung

07/08/2013

Bài 03 – Cây quyết định Decision tree learning

Nội dung

 Định nghĩa, giới thiệu  Biểu diễn mô hình/giả thuyết bằng DT.  Khả năng ứng dụng của DT.  Giải thuật học cơ bản.  Các vấn đề học với cây quyết định  Thuật toán ID3.  Các vấn đề trong DT.  Giới thiệu C4.5.

07/08/2013

Định Nghĩa

 Cây Quyết định là một cây phân lớp  Nút nội : là nút thử nghiệm  Nút lá : nút phân loại ( phân lớp )  Cây phân lớp bằng cách lọc mẫu nhập từ trên xuống  Kết quả là phân biệt và đầy đủ

Định Nghĩa

Cây quyết định có thể khác nhau trên một số khía

cạnh : – Nút thử nghiệm có thể là đơn biến hay đa biến – Có thể có 2 hoặc hơn 2 kết quả đầu ra – Các đặc trưng hoặc thuộc tính có thể là phân loại hoặc là số – Đầu ra (cuối cùng) có thể có hai hoặc nhiều lớp

07/08/2013

Định Nghĩa

 Ví dụ

Giới thiệu

Cây quyết định là phương pháp suy luận qui nạp

được sử dụng và thực hành rộng rãi nhất.

Là một phương pháp xấp xỉ hàm mục tiêu của tập các

giá trị rời rạc.

Cách biểu diễn các hàm học được

– Cây quyết định hoặc – Tập các luật if-then mà người có thể đọc được.

07/08/2013

Giới thiệu (tt)

Các phương pháp học được sử dụng rộng rãi:

Nhiệm vụ của các phương pháp học:

– ID3 – ASSISTANT – C4.5

– Tìm kiếm không gian giả thuyết hoàn chỉnh – Loại bỏ khó khăn của không gian giả thuyết có giới hạn.

Cách biểu diễn cây quyết định

 Cây quyết định phân loại các thể hiện bằng cách sắp xếp

chúng vào một cây từ gốc đến lá – Mỗi node trong cây là một thuộc tính của các thể hiện – Mỗi nhánh là một giá trị có thể có của các thuộc tính này  Cây quyết định được sử dụng trong phân lớp bằng cách duyệt từ nút gốc của cây cho đến khi đụng đến nút lá, từ đó rút ra lớp của đối tượng cần xét

07/08/2013

Mô hình cây quyết định

Ví dụ 1: Playing Tennis.

Day

Outlook

Temp.

Humidity Wind

Play tennis

Sunny

Hot

High

Weak

Sunny

Hot

High

Strong

Overcast

Hot

High

Weak

Yes

Rain

Mild

High

Weak

Yes

Rain

Cool

Normal

Weak

Yes

Rain

Cool

Normal

Strong

Overcast

Cool

Normal

Strong

Yes

Sunny

Mild

High

Weak

Sunny

Cold

Normal

Weak

Yes

Rain

Mild

Normal

Weak

Yes

Sunny

Mild

Normal

Strong

Yes

12 Overcast

Mild

High

Strong

Yes

13 Overcast

Hot

Yes

Normal

Weak

Rain

Mild

High

Strong

Decision Tree for PlayTennis

Outlook

Sunny Overcast Rain

Humidity Yes Wind

High Normal Strong Weak

No Yes No Yes

07/08/2013

Decision Tree for PlayTennis

Outlook

Sunny Overcast Rain

Humidity Each internal node tests an attribute

High Normal Each branch corresponds to an attribute value node

No Yes Each leaf node assigns a classification

Decision Tree for PlayTennis

Outlook Temperature Humidity Wind PlayTennis Sunny Hot High Weak ? No

Outlook

Sunny Overcast Rain

Humidity Yes Wind

High Normal Strong Weak

No Yes No Yes

07/08/2013

Decision Tree for Conjunction

Outlook=Sunny  Wind=Weak

Outlook

Sunny Overcast Rain

Wind No No

Strong Weak

No Yes

Decision Tree for Disjunction

Outlook=Sunny  Wind=Weak

Outlook

Sunny Overcast Rain

Yes Wind Wind

Strong Weak Strong Weak

No Yes No Yes

07/08/2013

Decision Tree for XOR

Outlook=Sunny XOR Wind=Weak

Outlook

Sunny Overcast Rain

Wind Wind Wind

Strong Weak Strong Weak Strong Weak

Yes No No Yes No Yes

Decision Tree

decision trees represent disjunctions (or) of conjunctions (and)

Outlook

Sunny Overcast Rain

Humidity Yes Wind

High Normal Strong Weak

No Yes No Yes

(Outlook=Sunny  Humidity=Normal)  (Outlook=Overcast)  (Outlook=Rain  Wind=Weak)

07/08/2013

Mô hình cây quyết định

Ví dụ 2: Ngồi bàn đợi tại một restaurant:

Alternate: Có restaurant nào cạnh đây không? Bar: Liệu có khu vực quầy bar có thể ngồi không? Fri/Sat: hôm nay là thứ 8 hay thứ 7? Hungry: có đang đói không? Patrons: Số người trong restaurant (None, Some, Full) Price: khoảng giá ($, $$, $$$) Raining: ngoài trời có mưa không? Reservation: đã đặt trước chưa? Type: loại restaurant (French, Italian, Thai, Burger) WaitEstimate: thời gian chờ đợi (0-10, 10-30, 30-60, >60)

Mô hình cây quyết định

Ví dụ 2: Ngồi bàn đợi tại một restaurant:

07/08/2013

Mô hình cây quyết định

Ví dụ 2: Ngồi bàn đợi tại một restaurant:

Mô hình cây quyết định

– D = {t1, …, tn} trong đó ti= – Cơ sở dữ liệu gồm có quan hệ {A1, A2, …, Ah} – Các lớp C={C1, …., Cm}

Một cây là cây quyết định (hay Cây phân lớp) của D nếu:

– Mỗi nút trong được gán nhãn thuộc tính Ai – Mỗi cung được gán nhãn một mệnh đề thuộc tính-giá trị với thuộc tính là

nhãn nút xuất phát của cung. – Mỗi nút lá được gán nhãn Cj.

07/08/2013

Mô hình cây quyết định

Khả năng biểu diễn  Cây quyết định có khả năng dùng để biểu diễn bất cứ hàm nào.  E.g. hàm Boolean:

 Với một cây quyết định nhất quán với tập mẫu huấn luyện thì mỗi input,

output của hàm tương ứng với một đường đi trong cây. Nhưng cũng có thể khả năng khái quát hoá không cao đối với các ví dụ mới chưa biết.

Các vấn đề thường dùng cây quyết định để giải quyết

cũng cố định (vd: nóng)

– Thuộc tính thường là các giá trị rời rạc nhưng cũng cho phép xử lý trên

các giá trị thực (phải mở rộng các thuật toán cơ bản).

 Các hàm chức năng (target-functions) có các giá trị đầu ra là

 Các thể hiện được biểu diễn dưới dạng cặp thuộc tính – giá trị – Các thuộc tính này thường là cố định (vd: nhiệt độ) và các giá trị của nó

rời rạc – Trong ví dụ trên có 2 phân lớp là Yes và No

07/08/2013

Các vấn đề thường dùng cây quyết định để giải quyết

– Cây quyết định là một phương pháp xử lý tốt với các trường hợp lỗi

(lỗi trong phân lớp và lỗi trong giá trị thuộc tính)

 Có thể yêu cầu biểu diễn dưới dạng biểu thức luận lý  Dữ liệu huấn luyện có thể có lỗi.

– Classification. – Medical diagnosis – Credit risk analysis – Object classification for robot manipulator (Tan 1993)

 Dữ liệu huấn luyện có thể bị khuyết giá trị Ứng dụng:

Giải thuật học cơ bản

 Hầu hết các giải thuật học trên cây quyết định là các biến thể của giải thuật học top-down, tìm kiếm tham lam (greedy search)

được chọn dựa trên độ đo thống kê hoặc độ đo heuristic – Tiếp tục lặp lại việc xây dựng cây quyết định cho các nhánh

 Giải thuật học gồm các bước như sau: – Cây được thiết lập từ trên xuống dưới – Rời rạc hóa các thuộc tính dạng phi số – Các mẫu huấn luyện nằm ở gốc của cây – Chọn một thuộc tính để phân chia thành các nhánh. Thuộc tính

07/08/2013

Giải thuật học cơ bản

– Tất cả các mẫu rơi vào một nút thuộc về cùng một lớp (nút lá) – Không còn thuộc tính nào có thể dùng để phân chia mẫu nữa – Không còn lại mẫu nào tại nút

 Điều kiện dừng

Lựa chọn thuộc tính phân lớp

 Độ đo để lựa chọn thuộc tính:

Thuộc tính được chọn là thuộc tính có lợi nhất cho quá trình phân lớp

(tạo ra cây nhỏ nhất)  Có 2 độ đo thường dùng

một thành viên tùy ý của S – Chỉ số Gini (Gini index)

• Giả sử tất cả các thuộc tính dạng số • Giả sử tồn tại một vài giá trị có thể phân chia giá trị của từng thuộc

tính

• Có thể biến đổi để áp dụng cho thuộc tính phi số

– Độ lợi thông tin (Information gain) • Giả sử tất cả các thuộc tính dạng phi số • Có thể biến đổi để áp dụng cho thuộc tính số • Xác định số bits tối thiểu của thông tin cần để mã hóa phân loại

07/08/2013

Một số vấn đề với DT

Không gian tìm kiếm khổng lồ. Lựa chọn thuộc tính để phân hoạch ntn? Cách phân hoạch ra sao? Quản lý cấu trúc cây ntn? Tiêu chuẩn dừng? Các vấn đề với dữ liệu huấn luyện. Các vấn đề với thuộc tính dữ liệu. Over-fitting và nhu cầu đơn giản hoá mô hình.

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

 Chọn lựa kiểu cho thử nghiệm  Dùng Độ lợi thông tin (information gain) để chọn thử nghiệm  Thuộc tính không phải nhị phân (non-binary)

07/08/2013

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

• Giá trị thuộc tính ở nút thử nghiệm là 0 hoặc 1

– Thuộc tính phân loại ( không phải nhị phân )

• Chia giá trị thuộc tính vào các tập con phân biệt và đầy đủ

 Chọn lựa kiểu cho thử nghiệm – Thông thường có n thuộc tính – Thuộc tính nhị phân

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

 Ví dụ chọn lựa kiểu cho thử nghiệm

07/08/2013

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

 Dùng Độ lợi thông tin (information gain) để chọn thử

nghiệm

– Giải pháp : giảm tối đa entropy (đo tính thuần khiết)

nghiệm – Vấn đề : chọn thứ tự các thử nghiệm – Với các thuộc tính phân loại và số => chọn giá trị thích hợp cho thử

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

– Vẫn sử dụng kỹ thuật trên – Đặt ngưỡng với miền giá trị thực – Chọn gom nhóm phân loại với những giá trị phân loại

 Thuộc tính không phải nhị phân (non-binary)

07/08/2013

Mạng tương đương với cây Quyết định

 Cây Quyết định luận lý đơn biến cài đặt hàm DNF (disjunctive normal form) sẽ tương đương với mạng neuron truyền thẳng 2 lớp

Giải thuật ID3

 Lựa chọn thuộc tính phân lớp dựa trên độ lợi thông tin (Information gain)

[29+,35-]

 Thuộc tính nào là tốt nhất?

A2=?

[29+,35-] A1=?

True False True False

[8+, 30-]

[18+, 33-] [11+, 2-] [21+, 5-]

 Là giải thuật tham ăn (greedy) mở rộng cây từ gốc đến ngọn

07/08/2013

Độ đo sự đồng nhất của mẫu

 pi: tần suất xuất hiện của các mẫu trong lớp Ci với i = {1, …, m}

 Thông tin cần biết để phân lớp một mẫu

 S: số lượng tập huấn luyện  Si: số các mẫu của S nằm trong lớp Ci

Một số lưu ý

 Trong trường hợp phân lớp

– Entropy = 0: khi tất cả thuộc về

1 lớp

– Entropy = 1: số lượng các ví dụ

ở cả hai lớp bằng nhau – Còn lại: 0

nhị phân:

07/08/2013

Độ lợi thông tin

 Thuộc tính A có các giá trị {a1, a2, …,an}  Dùng thuộc tính A để phân chia tập huấn luyện thành n tập

con {S1, S2, …, Sn}

 Độ lợi thông tin dựa trên phân nhánh bằng thuộc tính A:  Tại mỗi cấp, chúng ta chọn thuộc tính có độ lợi lớn nhất để phân nhánh cây hiện tại

Information Gain

Entropy([29+,35-]) = -29/64 log2 29/64 – 35/64 log2 35/64 = 0.99

 Gain(S,A): expected reduction in entropy due to sorting S on Gain(S,A)=Entropy(S) - vvalues(A) |Sv|/|S| Entropy(Sv) attribute A

[29+,35-] A1=? [29+,35-] A2=?

True False True False

[21+, 5-] [8+, 30-] [18+, 33-] [11+, 2-]

07/08/2013

Information Gain

Entropy([18+,33-]) = 0.94 Entropy([8+,30-]) = 0.62 Gain(S,A2)=Entropy(S) -51/64*Entropy([18+,33-]) -13/64*Entropy([11+,2-]) =0.12

[29+,35-] A1=? A2=? Entropy([21+,5-]) = 0.71 Entropy([8+,30-]) = 0.74 Gain(S,A1)=Entropy(S) -26/64*Entropy([21+,5-]) -38/64*Entropy([8+,30-]) =0.27 [29+,35-]

True False True False

[11+, 2-]

[18+, 33-] [21+, 5-] [8+, 30-]

Ví dụ

Day

Outlook

Temp.

Humidity Wind

Play?

Sunny

Hot

High

Weak

Sunny

Hot

High

Strong

Yes

Overcast

Hot

High

Weak

Yes

Rain

Mild

High

Weak

Yes

Rain

Cool

Normal

Weak

Rain

Cool

Normal

Strong

Yes

Overcast

Cool

Normal

Strong

Sunny

Mild

High

Weak

Yes

Sunny

Cold

Normal

Weak

Yes

Rain

Mild

Normal

Weak

Yes

Sunny

Mild

Normal

Strong

Yes

12 Overcast

Mild

High

Strong

Yes

13 Overcast

Hot

Normal

Weak

Rain

Mild

High

Strong

07/08/2013

Ví dụ

 Ta có

– S = 14 – m = 2 – C1 = “Yes”, C2 = “No” – S1 = 9, S2 = 5

Ví dụ

Humidity

High

Normal

[3+, 4-]

[6+, 1-]

E=0.592

E=0.985

Gain(S,Humidity)

=0.940 – (7/14)*0.985 – (7/14)*0.592

=0.151

07/08/2013

Ví dụ

Wind

Weak

Strong

[6+, 2-]

[3+, 3-]

E=1.000

E=0.811

Gain(S,Wind)

=0.940 – (8/14)*0.811 – (6/14)*1.000

=0.048

Ví dụ

Temperature

Hot

Mild

Cold

[2+, 2-]

[4+, 2-]

[3+, 1-]

Gain(S,Temperature) = 0.029

07/08/2013

Ví dụ

Outlook

Sunny

Overcast

Rain

[2+, 3-]

[4+, 0-]

[3+, 2-]

E=0.971

E=0.000

E=0.971

Gain(S,Wind)=0.048

Gain(S,Humidity)=0.151

Gain(S,Outlook)

Gain(S,Temperature) = 0.029

=0.940 – (5/14)*0.971

– (4/14)*0.0 – (5/14)*0.0971

=0.247

Ví dụ

Outlook

Sunny

Overcast

Rain

???

Yes

???

Which attribute should be tested here?

Gain(Ssunny, Humidity) = 0.971 – (3/5)*0.0 – (2/5)*0.0 = 0.971 Gain(Ssunny, Temperature) = 0.971 – (2/5)*0.0 – (2/5)*1.0 – (1/5)*0.0 = 0.571 Gain(Ssunny, Wind) = 0.971 – (2/5)*1.0 – (3/5)*0.918 = 0.02

07/08/2013

ID3 Algorithm

Outlook

Sunny Overcast Rain

Humidity Wind

Yes [D3,D7,D12,D13]

High Normal Strong Weak

No Yes No Yes

[D4,D5,D10] [D6,D14] [D8,D9,D11] [D1,D2]

Biến đổi cây quyết định thành luật

 Biểu diễn tri thức dưới dạng luật IF-THEN  Mỗi luật tạo ra từ mỗi đường dẫn từ gốc đến lá  Mỗi cặp giá trị thuộc tính dọc theo đường dẫn tạo nên phép kết (phép AND – và)

 Các nút lá mang tên của lớp

07/08/2013

Biến đổi cây quyết định thành luật

Outlook

Sunny

Overcast

Rain

Humidity

Yes

Wind

High

Normal

Strong

Weak

Yes

R1: If (Outlook=Sunny)  (Humidity=High) Then Play=No R2: If (Outlook=Sunny)  (Humidity=Normal) Then Play=Yes R3: If (Outlook=Overcast) Then Play=Yes R4: If (Outlook=Rain)  (Wind=Strong) Then Play=No R5: If (Outlook=Rain)  (Wind=Weak) Then Play=Yes

Ưu và khuyết điểm của ID3

Không gian giả thuyết:

là một tập hợp các cây quyết định

07/08/2013

Ưu và khuyết điểm của ID3

 Ưu điểm:

– Không gian giả thuyết này là đầy đủ (gồm các giá trị rời rạc hữu hạn: Yes/ No) giả thuyết chắc chắn thuộc về không gian này

– Dễ xây dựng – Phân lớp mẫu mới nhanh – Dễ dàng diễn giải cho các cây kích thước nhỏ

– Tại mỗi bước, ID3 xét hết tất cả các mẫu huấn luyện, đưa ra kết quả dựa vào thống kê kết quả ít bị lỗi

Ưu và khuyết điểm của ID3

 Khuyết điểm

– Phương pháp thực hiện của ID3 là phương pháp leo đồi đi từ đơn giản đến phức tạp, chỉ duy trì một tình trạng giả thuyết  giả thuyết không có khả năng đại diện toàn cục – Không quay lui (No Backtracking)  cực tiểu địa phương – Gặp tình trạng quá khớp (Overfitting)

07/08/2013

Ví dụ Ngồi bàn đợi tại một restaurant

Cây quyết định học bởi ID3 từ ví dụ 2 mô hình cây

quyết định:

Nhỏ hơn cây quyết định đưa ra lúc đầu

Thiên hướng quy nạp (Inductive Bias)

 Vì dữ liệu huấn luyện thường hạn chế, nên thường được khái quát hóa theo một số khía cạnh nào đóheuristic (sử dụng inductive bias)

 Inductive bias đề cập đến những giả định bổ sung (additional assumptions) mà người học sẽ dùng để dự đoán đầu ra đúng cho các tình huống chưa gặp phải trước đây. Inductive bias: thường sử dụng cho những cây quyết định nhỏ

– Restriction Bias: giới hạn một số giả thuyết trong quá trình học – Preference Bias: có sự ưu tiên cho một số giả thuyết

•  Phân loại:

 ID3 thuộc preference bias

07/08/2013

Occam’s razor

 Thế giới vốn dĩ là đơn giản  Cách giải thích đơn giản nhất bao phủ được toàn bộ dữ liệu là cách hiệu quả nhất

William of Ockham (1285–1349)

 Tại sao???

Occam’s razor

– Số lượng giả thuyết ngắn, đơn giản thường ít hơn nhiều so với số lượng

các giả thuyết dài, phức tạp

– Các giả thuyết ngắn thường tránh được sự trùng hợp ngẫu nhiên

 Lí do:

– Nếu có nhiều giả thuyết ngắn, thì cái nào là phù hợp??? – Kích thước của giả thuyết là bao nhiêu thì tốt?  tùy thuộc vào cách xác định của mỗi người  có thể cho kết luận khác nhau trên cùng một vấn đề

 Hạn chế:

07/08/2013

Thiên hướng quy nạp của ID3

 Ưu tiên chọn cây ngắn  Chọn cây với các thuộc tính có độ lợi thông tin lớn nhất mà gần gốc nhất

Cây định danh (1)

Hair color

blonde brown

red

Lotion used

 Emily

Alex Pete John

Dana Katie

Sarah Annie

No Yes

07/08/2013

Cây định danh (2)

Height

Tall

Short

Average

Weight

Hair color

Dana Pete

Heavy

Average

Blonde Red

Brown

Light

Hair color

Sarah

Alex

Weight

Brown

Red

Blonde

Heavy

Light

Average

Emily

John

Katie

Annie

Cây định danh (1)

Hair color

blonde brown

red

Lotion used

 Emily

Alex Pete John

No Yes

Dana Katie

Sarah Annie

Chọn cây 1

07/08/2013

Cây định danh (3)

Height

Tall

Short

Average

Weight

Gain = 0.97

Hair color

Dana Pete

Heavy

Average

Blonde Red

Brown

Light

Hair color

Sarah

Weight

Brown

Red

Blonde

Gain = 0.85

Emily

John

Katie

Annie

Cây định danh (4)

Height

Tall

Average

Short

Gain = 0.85

Weight

Hair color

Dana Pete

Heavy

Average

Blonde Red

Brown

Light

Hair color

Sarah

Gain = 0.95

Weight

Brown

Red

Blonde

Emily

John

Katie

Annie

07/08/2013

Cây định danh (3)

Height

Tall

Short

Average

Weight

Gain = 0.97

Hair color

Dana Pete

Heavy

Average

Blonde Red

Brown

Light

Hair color

Sarah

Weight

Gain = 0.85

Brown

Red

Blonde

Emily

John

Katie

Annie

Chọn cây 3

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

Kết hợp các thuộc tính có giá trị liên tục Lựa chọn thuộc tính bằng độ đo thay thế Xử lý mẫu huấn luyện với thuộc tính có giá trị khuyết Xử lý thuộc tính với chi phí khác nhau  Tập trung cho thuật toán ID3

07/08/2013

Thuộc tính có giá trị liên tục

Thuật toán ID3 bắt buộc dùng thuộc tính có giá trị rời

rạc – Thuộc tính đích, dùng ra quyết định – Thuộc tính dẫn dắt quyết định

Phân chia giá trị liên tục thành các khoảng rời rạc, và

có thể đưa vào cây quyết định

Cho A là thuộc tính có giá trị liên tục, việc phân tách

tạo 2 giá trị logic Ac với: với c là điểm phân tách  Chọn giá trị c tối ưu?

Giới thiệu C4.5

 Là phần mềm cài đặt và cải tiến ID3, tác giả Ross

Quinlan.

Địa chỉ download (program, source code in C,

documentation):

http://www2.cs.uregina.ca/~dbd/cs831/notes/ml/dtree s/c4.5/tutorial.html

Gói phần mềm WEKA (source code in JAVA): http://www.cs.waikato.ac.nz/ml/weka/

07/08/2013

Đọc thêm

 Giáo trình - chương 3.  R. Quinlan, C4.5: Programs for Machine Learning,

Morgan Kaufmann, 1993.

Câu hỏi ôn tập

cây quyết định là gì?

1. 2. Nêu các đặc điểm của các bài toàn giải bằng cây

quyết định

3. Trình bày thuật toán học cho cây quyết định? 4. Trình bày nội dung/đặc điểm của thuật toán ID3. 5. Nêu các vấn đề và giải pháp trong học/khái quát hoá

của ID3.

6. Nêu các vấn đề và giải pháp trong xử lý thuộc tính

của ID3.

7. Ứng dụng C4.5 để giải các bài toán thực tế.

07/08/2013

Bài tập mẫu 1

Dùng ID3 vẽ cây quyết định khi biết tập dữ liệu training sau:

Bài tập mẫu 2

An muốn áp dụng giải thuật ID3 để xây dựng cây quyết định với tập dữ liệu rèn luyện trên. Áp dụng các công thức tính entropy và gain, hãy giúp An xác định thuộc tính nào (A1, A2 hay A3) là thuộc tính tốt nhất để hỏi đầu tiên nhằm tạo ra một cây quyết định đơn giản nhất. (Lưu ý: phải trình bày các tính toán entropy và gain để đi đến kết luận).

07/08/2013