Từ khi trí tuệ nhân tạo sinh ra cho đến nay, người ta không ngừng thực thi những khu công trình nghiên cứu và điều tra để đưa tư tưởng điều tra và nghiên cứu cùng với máy tính để ứng dụng vào việc xử lý những việc làm trong thực tiễn đời sống. Một trong những nguyên do làm cho trí tuệ nhân tạo trở thành một trong những nghành mũi nhọn trong thời đại lúc bấy giờ là việc làm cho máy tính trở nên mưu trí hơn, nói đơn cử hơn là người ta tìm cách tạo ra những chương trình mưu trí hơn có năng lực xử lý những yếu tố trong thực tiễn như cách xử lý của con người. Một trong những nghành lý thú của trí tuệ nhân tạo được đề cập trong chuyên đề này là Học máy. Học máy là hướng tiếp cận trong đó thay vì con người phải chỉ ra những tri thức thiết yếu để xử lý bài toán, máy tính sẽ tự động hóa rút trích tri thức này một cách từ những tài liệu được cung ứng. Học máy mô phỏng quy trình học của con người qua những mức từ đơn thuần đến phức tạp : tiên phong máy tính ghi nhớ những trường họp đã Open và sau cuối học những trường hợp tổng quát chưa từng Open. Trong một bài toán học máy, nguồn vào là một tập tài liệu đào tạo và giảng dạy gồm có những mẫu tài liệu. Mỗi mẫu tài liệu gồm có một tập giá trị ứng với những thuộc tính. Tập thuộc tính được chia làm hai phần : thuộc tính quan sát và thuộc tính tác dụng. Mục tiêu của học máy là tìm một ánh xạ từ thuộc tính quan sát vào thuộc tính tác dụng ( tìm moi quan hệ giữa thuộc tính quan sát và thuộc tính hiệu quả ) ứng với tập dữ liệu huấn luyện và đào tạo. Ánh xạ này sẽ được vận dụng lên những mẫu quan sát mới để rút ra hiệu quả tương ứng .
40 trang |
Chia sẻ: ngtr9097
| Lượt xem : 3756
| Lượt tải: 5
Bạn đang xem trước 20 trang
tài liệu Đề tài Trí tuệ nhân tạo – Học máy, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
MỤC LỤC NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN HỌC MÁY Giới thiệu học máy Từ khi trí tuệ nhân tạo sinh ra cho đến nay, người ta không ngừng thực thi những khu công trình điều tra và nghiên cứu để đưa tư tưởng nghiên cứu và điều tra cùng với máy tính để ứng dụng vào việc xử lý những việc làm trong thực tiễn đời sống. Một trong những nguyên do làm cho trí tuệ nhân tạo trở thành một trong những nghành nghề dịch vụ mũi nhọn trong thời đại lúc bấy giờ là việc làm cho máy tính trở nên mưu trí hơn, nói đơn cử hơn là người ta tìm cách tạo ra những chương trình mưu trí hơn có năng lực xử lý những yếu tố thực tiễn như cách xử lý của con người. Một trong những nghành nghề dịch vụ lý thú của trí tuệ nhân tạo được đề cập trong chuyên đề này là Học máy. Học máy là hướng tiếp cận trong đó thay vì con người phải chỉ ra những tri thức thiết yếu để xử lý bài toán, máy tính sẽ tự động hóa rút trích tri thức này một cách từ những tài liệu được phân phối. Học máy mô phỏng quy trình học của con người qua những mức từ đơn thuần đến phức tạp : tiên phong máy tính ghi nhớ những trường họp đã Open và ở đầu cuối học những trường hợp tổng quát chưa từng Open. Trong một bài toán học máy, nguồn vào là một tập tài liệu huấn luyện và đào tạo gồm có những mẫu tài liệu. Mỗi mẫu tài liệu gồm có một tập giá trị ứng với những thuộc tính. Tập thuộc tính được chia làm hai phần : thuộc tính quan sát và thuộc tính tác dụng. Mục tiêu của học máy là tìm một ánh xạ từ thuộc tính quan sát vào thuộc tính tác dụng ( tìm moi quan hệ giữa thuộc tính quan sát và thuộc tính tác dụng ) ứng với tập dữ liệu huấn luyện và đào tạo. Ánh xạ này sẽ được vận dụng lên những mẫu quan sát mới để rút ra hiệu quả tương ứng. Bảng dưới đây trình diễn một ví dụ của học máy, bài toán Dự kiến việc có chơi đánh tennis hay không. # Outlook Temperature Humidity Wind Target 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 Cool 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 Trong bài toán này, học máy sẽ tìm một mối quan hệ giữa những thuộc tính quan sát : Outlook ( quang cảnh ), Temperature ( Nhiệt độ ), Humidity ( Độ ẩm ), Wind ( Sức gió ) với thuộc tính tác dụng Target. Kết quả này sẽ dùng Dự kiến giá trị Target khi nhập vào thuộc tính quan sát cho những mẫu mới ví dụ : # Outlook Temperature Humidity Wind Target 15 Sunny Mild Normal Strong ? 16 Rain Cool High Strong ? Việc Dự kiến cho mẫu 15 hoàn toàn có thể tương đối thuận tiện, vì mẫu này có những giá trị quan sát tương tự như mẫu số 11 nên giá trị Target cũng tương tự như là Yes ( trường hợp học máy đơn thuần – ghi nhớ ). Tuy nhiên việc Dự kiến cho mẫu 16 sẽ khó khăn vất vả hơn vì mẫu này không giống bất kể một trong những mẫu đã biết. Đây là trường hợp tổng quát của học máy – gặp những trường hợp chưa từng Open. Các phương pháp học máy đưa ra nhằm mục đích xử lý bài toán trong trường hợp tổng quát. Phần I : Cây quyết định hành động Trong triết lý quyết định hành động ( ví dụ điển hình quản lí rủi ro đáng tiếc ), một cây quyết định hành động ( decision tree ) là một đồ thị của những quyết định hành động và những hậu quả hoàn toàn có thể của nó ( gồm có rủi ro đáng tiếc và hao phí tài nguyên ). Cây quyết định hành động được sử dụng để kiến thiết xây dựng một kế hoạch nhằm mục đích đạt được tiềm năng mong ước. Các cây quyết định hành động được dùng để tương hỗ quy trình ra quyết định hành động. Cây quyết định hành động là một dạng đặc biệt quan trọng của cấu trúc cây. Giới thiệu chung Trong nghành học máy, cây quyết định hành động là một kiểu quy mô dự báo ( predictive Model ), nghĩa là một ánh xạ từ những quan sát về một sự vật / hiện tượng kỳ lạ tới những Kết luận về giá trị tiềm năng của sự vật / hiện tượng kỳ lạ. Mỗi một nút trong ( internal node ) tương ứng với một biến ; đường nối giữa nó với nút con của nó bộc lộ một giá trị đơn cử cho biến đó. Mỗi nút lá đại diện thay mặt cho giá trị Dự kiến của biến tiềm năng, cho trước những giá trị của những biến được trình diễn bởi đường đi từ nút gốc tới nút lá đó. Kỹ thuật học máy dùng trong cây quyết định hành động được gọi là học bằng cây quyết định hành động, hay chỉ gọi với cái tên ngắn gọn là cây quyết định hành động. Học bằng cây quyết định hành động cũng là một giải pháp thông dụng trong tìm hiểu và khám phá tài liệu. Khi đó, cây quyết định hành động diễn đạt một cấu trúc cây, trong đó, những lá đại diện thay mặt cho những phân loại còn cành đại diện thay mặt cho những tích hợp của những thuộc tính dẫn tới phân loại đó. Một cây quyết định hành động hoàn toàn có thể được học bằng cách chia tập hợp nguồn thành những tập con dựa theo một kiểm tra giá trị thuộc tính. Quá trình này được lặp lại một cách đệ quy cho mỗi tập con dẫn xuất. Quá trình đệ quy triển khai xong khi không hề liên tục triển khai việc chia tách được nữa, hay khi một phân loại đơn hoàn toàn có thể vận dụng cho từng thành phần của tập con dẫn xuất. Một bộ phân loại rừng ngẫu nhiên ( random forest ) sử dụng một số ít cây quyết định hành động để hoàn toàn có thể cải tổ tỉ lệ phân loại. Cây quyết định hành động cũng là một phương tiện đi lại có tính diễn đạt dành cho việc giám sát những Xác Suất có điều kiện kèm theo. Cây quyết định hành động hoàn toàn có thể được miêu tả như là sự phối hợp của những kỹ thuật toán học và đo lường và thống kê nhằm mục đích tương hỗ việc miêu tả, phân loại và tổng quát hóa một tập tài liệu cho trước. Dữ liệu được cho dưới dạng những bản ghi có dạng : Biến phụ thuộc vào ( dependant variable ) y là biến mà tất cả chúng ta cần tìm hiểu và khám phá, phân loại hay tổng quát hóa. là những biến sẽ giúp ta triển khai việc làm đó. Các khái niệm cơ bản 2.1. Cây quyết định hành động : Là một quy mô tài liệu mã hóa phân bổ của nhãn lớp ( cũng là y ) theo những thuộc tính dùng để Dự kiến. Đây là một đồ thị có hướng phi quy trình dưới dạng một cây. Nút gốc ( nút nằm trên đỉnh ) đại diện thay mặt cho hàng loạt tài liệu. Cây quyết định hành động thường thì được sử dụng cho việc đạt được thông tin cho mục đính tạo quyết định hành động. Cây quyết định hành động mở màn với một nút gốc từ đó user nhận được những hành vi. Từ nút này, user chia ra mỗi nút theo cách đệ quy theo giải thuật học cây quyết định hành động. Kết quả ở đầu cuối là một cây quyết định hành động trong đó mỗi nhánh biểu lộ một trường hợp hoàn toàn có thể của quyết định hành động và hệ quả của quyết định hành động đó. 2.2. Ví dụ bài toán chơi đánh tennis để lý giải cây quyết định hành động Người quản trị của một câu lạc bộ chơi đánh tennis gặp rắc rối chuyện những thành viên đến hay không đến. Có ngày ai cũng muốn chơi đánh tennis nhưng số nhân viên cấp dưới câu lạc bộ lại không đủ ship hàng. Có hôm thì chẳng ai đến chơi, và câu lạc bộ lại thừa nhân viên cấp dưới. Mục tiêu của Người quản trị là tối ưu hóa số nhân viên cấp dưới ship hàng mỗi ngày bằng cách dựa vào thời tiết để đoán xem khi nào người ta sẽ đến chơi đánh tennis. Để triển khai điều đó, anh cần hiểu được tại sao người mua quyết định hành động chơi và tìm hiểu và khám phá xem có cách lý giải nào cho việc đó hay không. Vậy là trong hai tuần, anh ta tích lũy thông tin về : Trời Outlook ( quang cảnh ), Temperature ( Nhiệt độ ), Humidity ( Độ ẩm ), Wind ( Sức gió ) với thuộc tính hiệu quả Target. Dữ liệu như sau : # Outlook Temperature Humidity Wind Target 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 Cool 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 Sau đó, để xử lý bài toán, người ta đã đưa ra một quy mô cây quyết định hành động. Kết luận thứ nhất : nếu trời nhiều mây, người ta luôn luôn chơi đánh tennis. Tiếp theo, ta lại chia nhóm trời nắng thành hai nhóm con. Ta thấy rằng người mua không muốn chơi golf nếu nhiệt độ cao. Cuối cùng, ta chia nhóm trời có gió thành hai và thấy rằng người mua sẽ không chơi đánh tennis nếu trời nhiều gió. Và đây là giải thuật ngắn gọn cho bài toán miêu tả bởi cây phân loại. Người quản trị phần nhiều cho nhân viên cấp dưới nghỉ vào những ngày trời nắng và ẩm, hoặc những ngày gió mạnh. Vì phần đông sẽ chẳng có ai chơi trong những ngày đó. Vào những hôm khác, khi nhiều người sẽ đến chơi đánh tennis, anh ta hoàn toàn có thể thuê thêm nhân viên cấp dưới thời vụ để phụ giúp việc làm. Kết luận là cây quyết định hành động giúp ta biến một màn biểu diễn tài liệu phức tạp thành một cấu trúc đơn thuần hơn rất nhiều. Các kiểu cây quyết định hành động Cây quyết định hành động còn có hai tên khác : Cây hồi quy ( Regression tree ) : ước đạt những hàm có giá trị là số thực thay vì được sử dụng cho những trách nhiệm phân loại. ( ví dụ : ước tính giá một ngôi nhà hoặc khoảng chừng thời hạn một bệnh nhân nằm viện ) Cây phân loại ( Classification tree ) : là một biến phân loại như : giới tính ( nam hay nữ ), hiệu quả của một trận đấu ( thắng hay thua ). Ưu điểm cây quyết định hành động Cây quyết định hành động dễ hiểu. Người ta hoàn toàn có thể hiểu quy mô cây quyết định hành động sau khi được lý giải ngắn. Việc sẵn sàng chuẩn bị tài liệu cho một cây quyết định hành động là cơ bản hoặc không thiết yếu. Các kỹ thuật khác thường yên cầu chuẩn hóa dữ liệu, cần tạo những biến phụ ( dummy variable ) và vô hiệu những giá trị rỗng. Cây quyết định hành động hoàn toàn có thể giải quyết và xử lý cả tài liệu có giá trị bằng số và tài liệu có giá trị là tên thể loại. Các kỹ thuật khác thường chuyên để nghiên cứu và phân tích những bộ tài liệu chỉ gồm một loại biến. Chẳng hạn, những luật quan hệ chỉ hoàn toàn có thể dùng cho những biến tên, trong khi mạng nơ-ron chỉ hoàn toàn có thể dùng cho những biến có giá trị bằng số. Cây quyết định hành động là một mô hình hộp trắng. Nếu hoàn toàn có thể quan sát một trường hợp cho trước trong một quy mô, thì hoàn toàn có thể thuận tiện lý giải điều kiện kèm theo đó bằng logic Boolean. Mạng nơ-ron là một ví dụ về quy mô hộp đen, do lời lý giải cho tác dụng quá phức tạp để hoàn toàn có thể hiểu được. Có thể thẩm định và đánh giá một quy mô bằng những kiểm tra thống kê. Điều này làm cho ta hoàn toàn có thể tin yêu vào quy mô. Cây quyết định hành động hoàn toàn có thể giải quyết và xử lý tốt một lượng tài liệu lớn trong thời hạn ngắn. Có thể dùng máy tính cá thể để nghiên cứu và phân tích những lượng tài liệu lớn trong một thời hạn đủ ngắn để cho phép những nhà kế hoạch đưa ra quyết định hành động dựa trên nghiên cứu và phân tích của cây quyết định hành động. Phần II : Thuật toán ID3 1. Thuật toán : Thuật toán ID3 do Ross Quinlan đề xuất kiến nghị dùng để kiến thiết xây dựng những cây quyết định hành động thỏa những đặc thù trên. Thuật toán tuân theo nguyên tắc dao cạo Occam để thiết kế xây dựng những cây quyết định hành động bằng cách ở mỗi bước kiểm tra, nỗ lực chọn thuộc tính ( nút nhánh ) đơn thuần nhất. Để xác lập độ đơn thuần của thuộc tính, ID3 sử dụng giá trị độ đo là entropy thông tin ( độ hỗn loạn thông tin ). Với một thuộc tính cho trước, một tập tài liệu được chia thành n tập con với những tỷ suất Pi tương ứng ( ví dụ, với thuộc tính Target, tập dữ liệu giảng dạy được chia thành 2 tập con Yes với Po = 9/14 và tập con No với P. ; = 5/14 ). Khi đó, entropy của tập dữ liệu trên thuộc tính được chọn là : n H Ví dụ, entropy của tập dữ liệu đánh tennis theo thuộc tính hiệu quả là : H = – 9/14 * log29 / 14 – 5/14 * log25 / 14 = 0,94 Entropy đo độ hỗn loạn của một tập. Entropy càng cao thì độ hỗn loạn của tập đó càng cao. Tập dữ liệu là trọn vẹn giống hệt khi entropy = 0. Và trong trường hợp tập dữ liệu có 2 lớp, tập dữ liệu trọn vẹn hỗn loạn sẽ có entropy = 1. Thuật toán ID3 : Bắt đầu với nút gốc, 1. Chọn A ß thuộc tính quyết định hành động ” tốt nhất ” cho nút sau đó Gán A là thuộc tính quyết định hành động cho nút Với mỗi giá trị của A, tạo nhánh con mới của nút Phân loại những mẫu giảng dạy cho những nhánh Nếu những mẫu huấn luyện và đào tạo trong một nhánh được phân loại trọn vẹn ( như nhau một loại ) thì NGƯNG, ta được một nút lá. Ngược lại, lặp với những nút nhánh mới. Thuộc tính tốt nhất ở đây là thuộc tính có entropy trung bình thấp nhất theo thuộc tính hiệu quả. Entropy trung bình của một thuộc tính bằng trung bình theo tỉ lệ của entropy những nhánh : 2. Ví dụ : Áp dụng thuật toán ID3 cho bài toán học chơi đánh tennis : * Lưu ý : Các số khoan tròn của toàn bộ hình bên dưới đều có thuộc tính Target là Yes, ngược lại là No. Ÿ Lặp lần 1 : Xét lần lượt những thuộc tính Outlook : # Outlook Temperature Humidity Wind Target 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 Cool 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 Outlook Rain Overcast Sunny 6 10 5 14 4 3 7 12 13 1 2 11 8 9 HRain = – 3/5 * log23 / 5 – 2/5 * log22 / 5 = 0,97 HOvercast = – 4/4 * log24 / 4 – 0/4 * log20 / 4 = 0 HSunny = – 2/5 * log22 / 5 – 3/5 * log23 / 5 = 0,97 AE ( Outlook ) = 5/14 * 0,97 + 4/14 * 0 + 5/14 * 0,97 = 0,693 Temperature : # Outlook Temperature Humidity Wind Target 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 Cool 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 Temperature Hot Mid Cool 13 3 4 5 10 11 12 9 7 1 2 8 14 6 HHot = – 2/4 * log22 / 4 – 2/4 * log22 / 4 = 1 HMid = – 4/6 * log24 / 6 – 2/6 * log22 / 6 = 0,918 HCool = – 3/4 * log23 / 4 – 1/4 * log21 / 4 = 0,811 AE ( Temperature ) = 4/14 * 1 + 6/14 * 0,918 + 4/14 * 0,811 = 0,911 Humidity : # Outlook Temperature Humidity Wind Target 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 Cool 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 HHigh = – 3/7 * log23 / 7 – 4/7 * log24 / 7 = 0,985 HNormal = – 6/7 * log26 / 7 – 1/7 * log21 / 7 = 0,592 AE ( Humidity ) = 7/14 * 0,985 + 7/14 * 0,592 = 0,79 Humidity High Normal 13 3 4 5 10 11 12 9 7 1 2 8 14 6 Wind : # Outlook Temperature Humidity Wind Target 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 Cool 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 Wind Weak Strong 13 3 4 5 10 11 12 9 7 1 2 8 14 6 Hweak = – 2/8 * log22 / 8 – 6/8 * log26 / 8 = 0,81 HStrong = – 3/6 * log23 / 6 – 3/6 * log23 / 6 = 1 AE ( Wind ) = 8/14 * 0,81 + 6/14 * 1 = 0,89 So sánh ta thấy thuộc tính Outlook có entropy trung bình thấp nhất nên ta chọn thuộc tính này làm gốc. Lặp lần 2 : Xét nhánh Rain Xét những thuộc tính Temperature # Outlook Temperature Humidity Wind Target 4 Rain Mild High Weak Yes 5 Rain Cool Normal Weak Yes 6 Rain Cool Normal Strong No 10 Rain Mild Normal Weak Yes 14 Rain Mild High Strong No Temperature Hot Cool 4 5 10 14 6 Entropy trung bình : HMid = – 2/3 * log22 / 3 – 1/3 * log21 / 3 = 0,918 HCool = – 1/2 * log21 / 2 – 1/2 * log21 / 2 = 1 AE ( Temperature ) = 3/5 * 0,918 + 2/5 * 1 = 0,8308 Xét những thuộc tính Humidity # Outlook Temperature Humidity Wind Target 4 Rain Mild High Weak Yes 5 Rain Cool Normal Weak Yes 6 Rain Cool Normal Strong No 10 Rain Mild Normal Weak Yes 14 Rain Mild High Strong No Humidity High Normal 4 5 10 14 6 Entropy trung bình : HHigh = – 1/2 * log21 / 2 – 1/2 * log21 / 2 = 1 HNormal = – 2/3 * log22 / 3 – 1/3 * log21 / 3 = 0,918 AE ( Humidity ) = 2/5 * 1 + 3/5 * 0,918 = 0,9508 Xét những thuộc tính Wind : # Outlook Temperature Humidity Wind Target 4 Rain Mild High Weak Yes 5 Rain Cool Normal Weak Yes 6 Rain Cool Normal Strong No 10 Rain Mild Normal Weak Yes 14 Rain Mild High Strong No Wind Weak Strong 4 5 10 14 6 Entropy trung bình : HHigh = – 3/3 * log23 / 3 – 0/3 * log20 / 3 = 0 HNormal = – 0/2 * log20 / 2 – 2/2 * log22 / 2 = 0 AE ( Humidity ) = 0 Thuộc tính Wind có entropy trang bình thấp nhất nên chọn làm nút nhánh. Lặp lần 3 : Xét nhánh Sunny Xét những thuộc tính Temperature # Outlook Temperature Humidity Wind Target 1 Sunny Hot High Weak No 2 Sunny Hot High Strong No 8 Sunny Mild High Weak No 9 Sunny Cool Normal Weak Yes 11 Sunny Mild Normal Strong Yes Temperature Mid Hot Cool 9 11 1 8 2 HMid = – 1/2 * log21 / 2 – 1/2 * log21 / 2 = 1 HHot = – 0/2 * log20 / 2 – 2/2 * log20 / 2 = 0 HCool = – 1 * log21 – 0 * log20 = 0 AE ( Temperature ) = 2/5 * 1 + 0 + 0 = 0,4 Xét những thuộc tính Humidity # Outlook Temperature Humidity Wind Target 1 Sunny Hot High Weak No 2 Sunny Hot High Strong No 8 Sunny Mild High Weak No 9 Sunny Cool Normal Weak Yes 11 Sunny Mild Normal Strong Yes Humidity High Normal 9 8 11 1 2 Entropy trung bình : HHigh = – 0/3 * log20 / 3 – 3/3 * log23 / 3 = 0 HNormal = – 2/2 * log22 / 2 – 0 = 0 AE ( Humidity ) = 0 Thuộc tính Humidity có entropy trung bình thấp nhất nên chọn làm nút nhánh. à Cây quyết định hành động hiệu quả : • Sau khi thiết kế xây dựng cây, ta hoàn toàn có thể rút ra những luật tương ứng bằng cách duyệt những đường đi trên cây từ nút gốc đến nút lá, mỗi đường đi ứng với một luật : L1 : Nếu Outlook = Overcast thì chơi đánh tennis. L2 : Nếu Outlook = Rain và Wind = Weak thì chơi đánh tennis. L3 : Nếu Outlook = Rain và Wind = Strong thì không chơi đánh tennis. L4 : Nếu Outlook = Sunny và Hub = High thì không chơi đánh tennis. L5 : Nếu Outlook = Sunny và Hub = Normal thì chơi đánh tennis. Lưu ý : Một phiên bản khác của thuật toán ID3 sử dụng Informatic Gain thay cho entropy để chọn thuộc tính quyết định hành động. Công thức tính Informatic Gain như sau : Gain ( A ) = Entropy ( S ) – Entropy ( A ) Trong đó : S là tập mẫu và A là một thuộc tính. Entropy ( S ) : độ hỗn loạn của tập S. Entropy ( A ) : độ hỗn loạn trung bình của thuộc tính A ( cách tính như trên ) Nguyên tắc triển khai : tựa như trên ngoại trừ Gain lớn nhất. Phần II : Thuật toán QuinLan 1. Thuật toán : Quinlan quyết định hành động thuộc tính phân hoạch bằng cách kiến thiết xây dựng những vector đặc trưng cho mỗi giá trị của từng thuộc tính dẫn xuất và thuộc tính tiềm năng. Cách tính đơn cử như sau : Với mỗi thuộc tính dẫn xuất A còn hoàn toàn có thể sử dụng để phân hoạch, tính : VA ( j ) = ( T ( j, r1 ), T ( j, r2 ), …, T ( j, rn ) ) T ( j, ri ) = ( tổng số thành phần trong phân hoạch có giá trị thuộc tính dẫn xuất A là j và có giá trị thuộc tính tiềm năng là ri ) / ( tổng số thành phần trong phân hoạch có giá trị thuộc tính dẫn xuất A là j ) * Trong đó : r1, r2, …, rn là những giá trị của thuộc tính tiềm năng * Như vậy nếu một thuộc tính A hoàn toàn có thể nhận một trong 5 giá trị khác nhau thì nó sẽ có 5 vector đặc trưng. Một vector V ( Aj ) được gọi là vector đơn vị chức năng nếu nó chỉ có duy nhất một thành phần có giá trị 1 và những thành phần khác có giá trị 0. Thuộc tính được chọn để phân hoạch là thuộc tính có nhiều vector đơn vị chức năng nhất. 2. Ví dụ : Bài toán Dự kiến việc chơi đánh tennis # Outlook Temperature Humidity Wind Target 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 Cool 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 Phân hoạch lần 1 : VOutlook ( Sunny ) = ( 2/5, 3/5 ) VOutlook ( Overcast ) = ( 4/4, 0/4 ) = ( 1, 0 ) { vector đơn vị chức năng }
