zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

Bài giảng Máy học và mạng neural: Bài 3 - TS. Vũ Đức Lung

Chia sẻ: Ngocnga Ngocnga | Ngày: | Loại File: PDF | Số trang:36

Báo xấu

74
lượt xem 16
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài 3 cung cấp cho người học những kiến thức về cây quyết định (Decision tree learning). Trong bài này người học có thể tìm hiểu một số nội dung sau: Định nghĩa, giới thiệu về cây quyết định; 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,...và một số nội dung khác.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Máy học và mạng neural: Bài 3 - TS. Vũ Đức Lung

07/08/2013 Bài 03 – Cây quyết định Decision tree learning 1 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. 2 1
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 đủ 3 Đị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 4 2
07/08/2013 Định Nghĩa  Ví dụ 5 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. 6 3
07/08/2013 Giới thiệu (tt) Các phương pháp học được sử dụng rộng rãi: – ID3 – ASSISTANT – C4.5 Nhiệm vụ của các phương pháp học: – 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. 7 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 8 4
07/08/2013 Mô hình cây quyết định Ví dụ 1: Playing Tennis. Day Outlook Temp. Humidity Wind Play tennis 1 Sunny Hot High Weak No 2 Sunny Hot High Strong No 3 Overcast Hot High Weak Yes 4 Rain Mild High Weak Yes 5 Rain Cool Normal Weak Yes 6 Rain Cool Normal Strong No 7 Overcast Cool Normal Strong Yes 8 Sunny Mild High Weak No 9 Sunny Cold Normal Weak Yes 10 Rain Mild Normal Weak Yes 11 Sunny Mild Normal Strong Yes 12 Overcast Mild High Strong Yes 13 Overcast Hot Normal Weak Yes 9 14 Rain Mild High Strong No Decision Tree for PlayTennis Outlook Sunny Overcast Rain Humidity Yes Wind High Normal Strong Weak No Yes No Yes 10 5
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 11 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 12 No Yes No Yes 6
07/08/2013 Decision Tree for Conjunction Outlook=Sunny  Wind=Weak Outlook Sunny Overcast Rain Wind No No Strong Weak No Yes 13 Decision Tree for Disjunction Outlook=Sunny  Wind=Weak Outlook Sunny Overcast Rain Yes Wind Wind Strong Weak Strong Weak No Yes No Yes 14 7
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 15 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) 16 8
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) 17 Mô hình cây quyết định Ví dụ 2: Ngồi bàn đợi tại một restaurant: 18 9
07/08/2013 Mô hình cây quyết định Ví dụ 2: Ngồi bàn đợi tại một restaurant: 19 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. 20 10
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. 21 Các vấn đề thường dùng cây quyết định để giải quyết  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ó 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à rời rạc – Trong ví dụ trên có 2 phân lớp là Yes và No 22 11
07/08/2013 Các vấn đề thường dùng cây quyết định để giải quyết  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. – 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)  Dữ liệu huấn luyện có thể bị khuyết giá trị Ứng dụng: – Classification. – Medical diagnosis – Credit risk analysis – Object classification for robot manipulator (Tan 1993) 23 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)  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 đượ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 24 12
07/08/2013 Giải thuật học cơ bản  Điều kiện dừng – 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 25 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 – Độ 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 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ố 26 13
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. 27 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) 28 14
07/08/2013 Các vấn đề học với cây quyết định  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 • 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 đủ 29 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 30 15
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 – 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ử nghiệm – Giải pháp : giảm tối đa entropy (đo tính thuần khiết) 31 Các vấn đề học với cây quyết định  Thuộc tính không phải nhị phân (non-binary) – 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 32 16
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 33 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)  Thuộc tính nào là tốt nhất? [29+,35-] A1=? A2=? [29+,35-] True False True False [21+, 5-] [8+, 30-] [18+, 33-] [11+, 2-]  Là giải thuật tham ăn (greedy) mở rộng cây từ gốc đến ngọn 34 17
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}  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  Thông tin cần biết để phân lớp một mẫu m m si s entropy( S )   pi log 2 pi   log 2 i i 1 i 1 s s 35 Một số lưu ý  Trong trường hợp phân lớp nhị phân: entropy(S )   p log2 p  p log2 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
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 Sv G(S , A)  Entropy( S )   vValues( A) S Entropy(Sv ) 37 Information Gain  Gain(S,A): expected reduction in entropy due to sorting S on attribute A Gain(S,A)=Entropy(S) -  vvalues(A) |Sv|/|S| Entropy(Sv) m m si s entropy( S )   pi log 2 pi   log 2 i i 1 i 1 s s Entropy([29+,35-]) = -29/64 log2 29/64 – 35/64 log2 35/64 = 0.99 [29+,35-] A1=? A2=? [29+,35-] True False True False [21+, 5-] [8+, 30-] [18+, 33-] [11+, 2-] 38 19
07/08/2013 Information Gain Entropy([21+,5-]) = 0.71 Entropy([18+,33-]) = 0.94 Entropy([8+,30-]) = 0.74 Entropy([8+,30-]) = 0.62 Gain(S,A1)=Entropy(S) Gain(S,A2)=Entropy(S) -26/64*Entropy([21+,5-]) -51/64*Entropy([18+,33-]) -38/64*Entropy([8+,30-]) -13/64*Entropy([11+,2-]) =0.27 =0.12 [29+,35-] A1=? A2=? [29+,35-] True False True False [21+, 5-] [8+, 30-] [18+, 33-] [11+, 2-] 39 Ví dụ Day Outlook Temp. Humidity Wind Play? 1 Sunny Hot High Weak No 2 Sunny Hot High Strong No 3 Overcast Hot High Weak Yes 4 Rain Mild High Weak Yes 5 Rain Cool Normal Weak Yes 6 Rain Cool Normal Strong No 7 Overcast Cool Normal Strong Yes 8 Sunny Mild High Weak No 9 Sunny Cold Normal Weak Yes 10 Rain Mild Normal Weak Yes 11 Sunny Mild Normal Strong Yes 12 Overcast Mild High Strong Yes 13 Overcast Hot Normal Weak Yes 14 Rain Mild High Strong No 40 20

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.