Tài liệu Luận văn sư phạm tìm hiểu về khai phá dữ liệu bằng cây quyết định và ứng dụng hướng nghiệp

TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 VIỆN CÔNG NGHỆ THÔNG TIN TRẦN THỊ THÙY LINH TÌM HIỂU VỀ KHAI PHÁ DỮ LIỆU BẰNG CÂY QUYẾT ĐỊNH VÀ ỨNG DỤNG HƯỚNG NGHIỆP KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành: Sư phạm Tin học Người hướng dẫn khoa học ThS. Đỗ Thị Lan Anh HÀ NỘI, 2019 LỜI CẢM ƠN Em xin chân thành cảm ơn cô giáo ThS. Đỗ Thị Lan Anh, giảng viên Viện Công nghệ thông tin, trường Đại học Sư phạm Hà Nội 2, người đã trực tiếp hướng dẫn em trong suốt thời gian qua để em có thể hoàn thành khóa luận này. Em xin gửi lời cảm ơn tới các thầy, cô giáo trong Viện Công nghệ thông tin, các bạn lớp K41 – Sư Phạm tin học đã tạo điều kiện, động viên khích lệ em trong suốt quá trình học tập và nghiên cứu. Do thời gian nghiên cứu còn hạn chế nên những vấn đề mà em trình bày trong khóa luận sẽ không tránh khỏi những thiếu xót. Em kính mong nhận được những ý kiến đóng góp từ thầy cô và các bạn để bài khóa luận của em được hoàn thiện hơn. Em xin trân thành cảm ơn! Hà Nội, ngày tháng 5 năm 2019 Sinh viên Trần Thị Thùy Linh LỜI CAM ĐOAN Tôi xin cam đoan khóa luận này được hoàn thành bằng sự cố gắng của bản thân, dưới sự hướng dẫn tận tình của cô giáo ThS. Đỗ Thị Lan Anh và tham khảo một số tài liệu đã được ghi rõ nguồn. Khóa luận hoàn toàn không sao chép từ tài liệu có sẵn nào. Kết quả nghiên cứu không trùng lặp với các tác giả khác. Nếu sai, tôi xin hoàn toàn chịu trách nhiệm! Hà Nội, ngày tháng 5 năm 2019 Sinh viên Trần Thị Thùy Linh DANH MỤC CÁC HÌNH Hình 2.1: Cây quyết định được xây dựng theo thuật toán CLS ............... 11 Hình 2.2: Mở rộng nhánh bên trái của cây quyết định ............................. 12 Hình 2.3: Mở rộng nhánh bên phải cây quyết định ................................... 13 Hình 2.4: Phân chia theo các giá trị của thuộc tính ................................... 32 Hình 2.5: Cây quyết định có ngưỡng cho phép tách.................................. 34 Hình 2.6: Kết quả sử dụng thuật toán C4.5 ................................................ 35 Hình 3.1: Đăng nhập ..................................................................................... 39 Hình 3.2: Đăng ký ......................................................................................... 39 Hình 3.3: Làm trắc nghiệm .......................................................................... 40 Hình 3.4: Kết quả .......................................................................................... 40 Hình 3.5: Kết quả .......................................................................................... 41 Hình 3.6: Lưu trữ thông tin ......................................................................... 41 DANH MỤC CÁC BẢNG Bảng 2.1. Tập dữ liệu huấn luyện quyết định đi Picnic ............................... 11 Bảng 2.2. Thống kê mối quan hệ mức độ thực phẩm cần cung cấp và độ tuổi................................................................................................................... 29 Bảng 2.3. Minh họa tìm ngưỡng ................................................................... 33 MỤC LỤC LỜI CẢM ƠN LỜI CAM ĐOAN MỞ ĐẦU .......................................................................................................... 1 1. Lý do chọn đề tài ......................................................................................... 1 2. Mục đích và nhiệm vụ nghiên cứu ............................................................. 1 3. Phương pháp nghiên cứu............................................................................ 1 4. Nội dung chính của đề tài ........................................................................... 2 CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU ............................. 3 1.1. Khái niệm .................................................................................................. 3 1.2. Các bước khai phá dữ liệu....................................................................... 3 1.2.1. Tìm hiểu bài toán ................................................................................... 3 1.2.2. Thu thập và xử lý dữ liệu ....................................................................... 3 1.2.3. Khai phá dữ liệu và lựa chọn giải thuật phù hợp ................................ 3 1.2.4. Phân tích đánh giá ................................................................................. 3 1.2.5. Sử dụng kết quả...................................................................................... 3 1.3. Một số kỹ thuật khai phá dữ liệu ............................................................ 4 1.3.1. Phân lớp dữ liệu ..................................................................................... 4 1.3.2. Phân cụm dữ liệu ................................................................................... 5 1.3.3. Sử dụng luật kết hợp ............................................................................. 6 1.3.4. Sử dụng cây quyết định ........................................................................ 7 CHƯƠNG 2: CÁC PHƯƠNG PHÁP KHAI PHÁ DỮ LIỆU BẰNG CÂY QUYẾT ĐỊNH ................................................................................................. 8 2.1 Kỹ thuật khai phá dữ liệu sử dụng cây quyết định................................ 8 2.1.1. Các kiểu cây quyết định ......................................................................... 8 2.1.2. Đánh giá cây quyết định trong lĩnh vực khai phá dữ liệu ................... 8 2.1.3. Xây dựng cây quyết định........................................................................ 9 2.2. Các thuật toán sử dụng cây quyết định ................................................. 9 2.2.1. Thuật toán CLS ...................................................................................... 9 2.2.2. Thuật toán ID3 ..................................................................................... 13 2.2.3 Thuật toán C4.5 .................................................................................... 25 2.3 Cắt tỉa cây quyết định ............................................................................. 35 2.4 Đánh giá về các thuật toán ..................................................................... 36 CHƯƠNG 3: XÂY DỰNG ỨNG DỤNG .................................................... 38 3.1. Lựa chọn thuật toán ............................................................................... 38 3.2. Lựa chọn ngôn ngữ lập trình ................................................................ 38 3.3. Chương trình .......................................................................................... 38 3.3.1. Phát biểu bài toán ................................................................................ 38 3.3.2. Yêu cầu bài toán ................................................................................... 38 3.3.3. Giao diện chương trình........................................................................ 39 3.3.4. Đánh giá kết quả chương trình ........................................................... 41 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ................................................... 43 TÀI LIỆU THAM KHẢO ............................................................................ 44 MỞ ĐẦU 1. Lý do chọn đề tài Ngày nay, với sự phát triển về mọi mặt của đời sống từ văn hóa, giáo dục cho đến công nghệ và đặc biệt lĩnh vực công nghệ thông tin có những bước phát triển chóng mặt. Cùng với sự phát triển thì lượng dữ liệu thu thập được ngày càng nhiều, lượng thông tin được lưu trữ trên các thiết bị ngày càng tăng lên. Để tìm ra những thông tin hữu ích trong lượng dữ liệu khổng lồ ngày càng khó. Chính vì vậy mà hiện nay đã phát triển một kỹ thuật mới nhằm tìm ra những thông tin hữu ích đó chính là khai phá dữ liệu. Nghề nghiệp là một vấn đề quan trọng đối với mỗi con người, có rất nhiều các bạn đang rất băn khoăn về việc lựa chọn nghề nghiệp cho bản thân mình, đặc biệt đối với những học sinh lớp 12. Do vậy việc hướng nghiệp cho học sinh trung học phổ thông là hết sức cần thiết. Trước những thực tế đó, tôi chọn đề tài: “Tìm hiểu về khai phá dữ liệu bằng cây quyết định và ứng dụng hướng nghiệp” cho khóa luận tốt nghiệp của mình. 2. Mục đích và nhiệm vụ nghiên cứu - Mục đích: Từ việc nghiên cứu phương pháp khai phá dữ liệu bằng cây quyết định để xây dựng mô hình phân tích kết quả học tập và đưa ra tư vấn nghề nghiệp cho học sinh. - Nhiệm vụ nghiên cứu: + Tìm hiểu các kỹ thuật về khai phá dữ liệu, các thuật toán được áp dụng cho từng kỹ thuật. + Áp dụng thuật toán cơ bản trong cây quyết định để phân tích kết quả học tập của học sinh. 3. Phương pháp nghiên cứu - Phương pháp nghiên cứu lí thuyết: Tìm hiểu và lựa chọn phương pháp khai phá dữ liệu cho phù hợp. - Phương pháp nghiên cứu thu thập thông tin, phân tích số liệu: 1 Thu thập thống kê số liệu từ khảo sát sinh viên, phân tích các dữ liệu, tham khảo tài liệu của các chuyên gia hướng nghiệp cho học sinh để có được các kinh nghiệm. 4. Nội dung chính của đề tài Ngoài phần mở đầu, kết luận, tài liệu tham khảo, phụ lục luận văn bao gồm 3 chương CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU CHƯƠNG 2: CÁC PHƯƠNG PHÁP KHAI PHÁ DỮ LIỆU BẰNG CÂY QUYẾT ĐỊNH CHƯƠNG 3: XÂY DỰNG ỨNG DỤNG 2 CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 1.1 Khái niệm Khai phá dữ liệu là một tập hợp các kỹ thuật được sử dụng để tự động khai thác và tìm ra các mối quan hệ lẫn nhau của dữ liệu trong một tập hợp dữ liệu khổng lồ và phức tạp, đồng thời cũng tìm ra các mẫu tiềm ẩn trong tập dữ liệu đó. [6] Các tên gọi khác như: Knowledge Mining (khai phá tri thức), knowledge extraction (chắt lọc tri thức), data/patern analysis (phân tích dữ liệu/mẫu), data archaeoloogy (khảo cổ dữ liệu), datadredging (nạo vét dữ liệu),... 1.2 Các bước khai phá dữ liệu 1.2.1 Tìm hiểu bài toán Đây là bước đầu trong khai phá dữ liệu nhằm xác định các tri thức của lĩnh vực, các mục đích của bài toán và xây dựng được bài toán cụ thể giúp định hướng cho giai đoạn tiếp theo trong khai phá dữ liệu. 1.2.2 Thu thập và xử lý dữ liệu Đây là giai đoạn quan trọng nhất của quá trình khai phá vì thông tin thu thập được chưa đầy đủ, chính xác cần phải xử lý, chọn lọc nếu không sẽ dẫn đến những kết quả không mong muốn trong khai phá dữ liệu. 1.2.3 Khai phá dữ liệu và lựa chọn giải thuật phù hợp Sau khi dữ liệu được thu thập, xử lý sẽ bắt đầu lựa chọn phương pháp khai phá phù hợp với dữ liệu có được. 1.2.4 Phân tích đánh giá Dựa trên một số tiêu chí tiến hành kiểm tra và chọn lọc nguồn tri thức thu được. 1.2.5 Sử dụng kết quả Sau quá trình chắt lọc, tìm kiếm tri thức tìm ra được đem vảo sử dụng. Các kết quả của quá trình phát hiện tri thức có thể được đưa và ứng dụng trong các lĩnh vực khác nhau. 3 1.3 Một số kỹ thuật khai phá dữ liệu 1.3.1. Phân lớp dữ liệu Mục đích của phân lớp là dự đoán các nhãn phân lớp cho các bộ dữ liệu mới. Kỹ thuật phân lớp bao gồm hai bước: Xây dựng mô hình và sử dụng mô hình. - Xây dựng mô hình: Là mô tả một tập những lớp được định nghĩa trước trong đó: Mỗi bộ hoặc mẫu được gán thuộc về một lớp được định nghĩa trước như là được xác định bởi thuộc tính nhãn lớp, tập hợp của những bộ được sử dụng trong việc sử dụng mô hình được gọi là tập huấn luyện. Mô hình được biểu diễn là những luật phân lớp, cây quyết định và những công thức toán học. - Sử dụng mô hình: Việc sử dụng mô hình phục vụ cho mục đích phân lớp dữ liệu trong tương lai hoặc phân lớp cho những đối tượng chưa biết đến. Trước khi sử dụng mô hình người ta thường phải đánh giá tính chính xát của mô hình trong đó: Nhãn được biết của mẫu kiểm tra được so sánh với kết quả phân lớp của mô hình, độ chính xác là phần trăm của tập hợp mẫu kiêm tra mà phân loại đúng bởi mô hình, tập kiểm tra là độc lập với tập huấn luyện. [2] * Một số thuật toán về phân lớp dữ liệu: - Phân lớp dữ liệu với quy nạp cây quyết định: + Cây quyết định là một dạng đặc biệt của cấu trúc cây. Mỗi nút bên trong biểu thị một sự kiểm tra trên một thuộc tính. Mỗi nhánh biểu thị kết quả cụ thể của sự kiểm tra đó. Mỗi nút lá biểu thị một nhãn lớp. + Cách áp dụng cây quyết định cho phân lớp dữ liệu: Những đối tượng cần phân lớp, giá trị các thuộc tính của đối tượng được đưa vào phân tích trên cây quyết định. Sau quá trình phân tích, mỗi đối tượng tương ứng có một đường đi từ gốc đến một nút lá chứa kết quả dự báo kết quả phân lớp cho những đối tượng đó - Phân lớp dữ liệu với Bayesian: + Trong lĩnh vực khai phá dữ liệu, Bayesian là kỹ thuật phân lớp dựa vào việc tính xác suất có điều kiện. 4 Công thức tính xác suất có điều kiện có dạng: P(H/X) = 𝑋 𝐻 𝑃( ) 𝑃(𝐻) 𝑃(𝑋) Trong đó: + P(H/X) là xác suất hậu của H điều kiện X. + P(H) là tiền xác suất của H. + P(X/H) là hậu xác suất của X xác định điều kiện trên H. + P(X) là tiền xác suất của X. 1.3.2 Phân cụm dữ liệu Phân cụm dữ liệu là quá trình phân chia một tập dữ liệu ban đầu thành các cụm dữ liệu sao cho các đối tượng trong cùng một cụm là tương đồng. Trong quá trình phân cụm dữ liệu thì vấn đề trở ngại lớn nhất đó là nhiễu. Nhiễu xuất hiện trong quá trình thu thập thông tin chưa chính xác. Vì vậy phải khử nhiễu trong quá trình phân cụm dữ liệu. * Các vấn đề con cơ bản của phân cụm dữ liệu cần giải quyết đó là: - Biểu diễn dữ liệu. - Xây dựng hàm tính độ tương tự. - Xây dựng các tiêu chuẩn phân cụm. - Xây dựng mô hình cho cấu trúc cụm dữ liệu. - Xây dựng thuật toán phân cụm và xác lập các điều kiện khởi tạo. - Xây dựng các thủ tục biểu diễn và đánh giá kết quả phân cụm. * Một số kiểu dữ liệu trong phân cụm: - Phân loại dựa trên kích thước miền: Cách phân loại này phân biệt các đối tượng dữ liệu dựa trên lích thước miền của đối tượng đó, hay là các giá trị khác nhau của vùng đó. Giả sử cơ sở dữ liệu X và k đối tượng. Nếu a, b, c là 3 đối tượng của X thì chúng sẽ có dạng: a = (a1, a2, a3, ..., ay), b = (b1, b2, b3,..., by), c = (c1, c2, c3,..., cy) Với y là số chiều và ai, bi, ci với 1 ≤ i ≤ y là các thuộc tính tương ứng của các đối tượng. 5 Các loại dữ liệu dựa trên kích thước miền: + Thuộc tính liên tục: Miền giá trị của các thuộc tính này là các miền liên tục. Ví dụ như âm thanh, nhiệt độ. + Thuộc tính rời rạc: Miền giá trị của thuộc tính này là các miền các giá trị rời rạc. Ví dụ như số quả táo, số bông hoa. - Phân loại dựa vào phép đo: Giả sử hai đối tượng a, b và giá trị thuộc tính x của mỗi đối tượng tương ứng là ax, bx. Ta có các lớp sau: + Thuộc tính định danh: Các giá trị ở lớp này chỉ có phép toán so sánh bằng (ax = bx) hoặc không bằng (ax ≠ bx). + Thuộc tính có thứ tự: Là thuộc tính định danh nhưng có thêm tính thứ tự. Nếu a và b là 2 thuộc tính thứ tự thì có thể xác định a = b, a ≠ b, a < b, a > b. + Thuộc tính có khoảng cách: Với thuộc tính có khoảng cách có thể xác định một thuộc tính đứng trước hay đứng sau một thuộc tính khác với khoảng là bao nhiêu. Nếu ax < bx thì có thể nói b cách a một khoảng là bx - ax tương ứng với thuộc tính thứ x. * Các phương pháp phân cụm: - Phương pháp phân cấp. - Phương pháp phân hoạch. - Phương pháp dựa trên mật độ. - Phương pháp dựa vào lưới. - Phương pháp dựa vào mô hình. 1.3.3 Sử dụng luật kết hợp Định nghĩa: Một luật kết hợp thường được kí hiệu là xRy hoặc X →Y, trong đó X, Y là tập con các mục của tập mục I và X ∩ Y = Ø; X được gọi là tiên đề và Y được gọi là hệ quả của luật hay X là giả thiết còn Y là kết luận.[2] Hai tham số quan trọng của luật kết hợp là độ hỗ trợ và độ tin cậy. Nó làm thước đo cho tính tin cậy và mức độ chính xác của luật. 6 Mục đích của luật kết hợp là tìm ra mối quan hệ giữa các đối tượng trong cơ sở dữ liệu. Từ đó ứng dụng các luật vừa tìm được vào những mục đích cụ thể để đạt kết quả tốt nhất. Ví dụ ta có luật: Những người mua dầu ăn, muối, bột ngọt, nước mắm => Đây là những bà mẹ nội trợ. Hay những người mua muối sẽ mua bột ngọt, dầu ăn, ta sẽ quan tâm đến nhu cầu mua hàng của đối tượng khách hàng này để đưa ra luật hỗ trợ phù hợp. * Một số thuật toán cơ bản trong khai phá dữ liệu - Thuật toán APPIORI - Thuật toán FB – Growwth - Thuật toán AIS - Thuật toán STEAM 1.3.4 Sử dụng cây quyết định Cây quyết định là cấu trúc biểu diễn dưới dạng cây. Trong đó mỗi nút trong tương ứng với một biến. Đường nối giữa nó với nút con của nó thể hiện giá trị cụ thể cho biến đó. Mỗi nút lá đại diện cho giá trị dự đoán của biến mục tiêu. Đỉnh trên cùng gọi là gốc. Cây quyết định được sử dụng để xây dựng một kế hoạch nhằm đạt được mục tiêu mong muốn. Cây quyết định nhằm hỗ trợ quá trình ra quyết định. 7 CHƯƠNG 2: CÁC PHƯƠNG PHÁP KHAI PHÁ DỮ LIỆU BẰNG CÂY QUYẾT ĐỊNH 2.1 Kỹ thuật khai phá dữ liệu sử dụng cây quyết định 2.1.1 Các kiểu cây quyết định Có hai kiểu cây quyết định: - Cây hồi quy: Ước lượng các hàm có giá trị là số thực thay vì sử dụng cho các nhiệm vụ phân loại. - Cây phân loại: Nếu x có các nhiệm vụ phân loại như: Thời tiết (nắng hay mưa), kết quả (thắng hay thua). 2.1.2 Đánh giá cây quyết định trong lĩnh vực khai phá dữ liệu * Ưu điểm: - Cây quyết định tương đối dễ hiểu. Người ta có thể hiểu được mô hình của cây quyết định chỉ cần sau khi được giải thích gắn gọn. - Việc chuẩn bị dữ liệu cho cây quyết định là cơ bản hoặc không cần thiết. Trong khi đó, các kỹ thuật khác thường đòi hỏi phải xử lý dữ liệu, cần tạo ra các biến phụ hay loại bỏ các dữ liệu rỗng. - Cây quyết định có thể xử lý các dữ liệu bằng số, liên tục và dữ liệu dạng phân loại rời rạc. Các kỹ thuật khác thường xuyên để phân tích các bộ dữ liệu chỉ gồm các thuộc tính có giá trị hoặc rời rạc. Chẳng hạn, các luật quan hệ chỉ có thể dùng cho các biến tên loại rời rạc. - Cây quyết định là một mô hình hộp trắng. Nếu có thể quan xát một tình huống cho trước trong một mô hình, thì dễ dàng có thể giải thích điều kiện đó bằng logic boolean. - Có thể thẩm định một mô hình cây quyết định bằng cách kiểm tra thống kê. Điều này làm cho ta có thể tin tưởng vào kết quả của mô hình. - Cây quyết định có thể xử lý tốt một đối tượng dữ liệu lớn trong thời gian ngắn. Có thể dùng máy tính cá nhân để phân tích các lượng dữ liệu lớn trong thời gian đủ ngắn để cho phép các nhà chiến lược đưa ra quyết định dựa trên phân tích của cây quyết định. 8 * Nhược điểm: - Xảy ra lỗi khi có quá nhiều lớp: Một cây quyết định chỉ thao tác với những lớp giá trị nhị phân. Số khác lại có thể chỉ định các bản ghi vào một số lớp bất kỳ, những dễ xảy ra lỗi khi số ví dụ huấn luyện ứng với một lớp là nhỏ. - Chi phí tính toán đắt: Vì cây quyết định có nhiều node trong trước khi đến lá cuối cùng. Tại từng node cần tính một độ đo trên từng thuộc tính, với thuộc tính liên tục phải thêm thao tác sắp xếp lại dữ liệu theo thứ tự giá trị của tập thuộc tính đó. Sau đó mới có thể chọn được thuộc tính phát triển và tương ứng là một phân chia tốt nhất. 2.1.3 Xây dựng cây quyết định Để xây dựng cây quyết định có thể thực hiện bằng thuật toán nhất đinh nào đó, nhưng quá trình xây dựng cây gồm 3 giai đoạn: - Giai đoạn 1: Tạo dựng cây Giai đoạn này phát triển bắt đầu từ gốc, đến từng nhánh và phát triển quy nạp theo cách thức chia để trị để đến khi đạt được cây quyết định với tất cả các lá được gán nhãn lớp. - Giai đoạn 2: Cắt tỉa cây Đây là công việc để tối ưu hóa cây, khái quát hóa để tăng độ chính xác của cây bằng cách loại bỏ sự phụ thuộc vào mức độ nhiễu. - Giai đoạn 3: Đánh giá cây Dùng để đánh giá độ chính xác của cây kết quả. Tiêu chí đánh giá là tổng số mẫu được phân lớp chính xác trên tổng số mẫu đưa vào. 2.2. Các thuật toán sử dụng cây quyết định 2.2.1 Thuật toán CLS Thuật toán CLS được Hoveland và Hint giới thiệu lần đầu tiên vào những năm 50 của thế kỷ XX. Thuật toán này được thiết kế theo chiến lược chia để trị từ trên xuống. CLS là một thuật toán được phát minh ra sớm nhất so với các thuật toán khác. Nó được đem ra áp dụng cho các cơ sở dữ liệu chứa ít thuộc tính, giá trị các 9 thuộc tính được phân loại hay rời rạc. Cùng với một tập dữ liệu đầu vào, thuật toán có thể cho các kết quả khác nhau. Do thuật toán này chưa có tiêu chí để lựa chọn thuộc tính trong quá trình xây dựng. Thuật toán CLS khá đơn giản, dễ cài đặt phù hợp giải quyết trong các nhiệm vụ đơn giản. Nó gồm các bước sau: - Tạo một nút T, nút này gồm tất cả các mẫu của tập huấn luyện. - Nếu tất cả các mẫu trong T có thuộc tính quyết định mang giá trị “YES” (hay thuộc cùng một lớp), thì gán nhãn cho nút T là “YES” và dừng lại. T lúc này là nút lá. - Nếu tất cả các mẫu trong T có thuộc tính quyết định mang giá trị “NO” (hay thuộc cùng một lớp), thì gán nhãn cho nút T là “NO” và dừng lại. T lúc này là nút lá. - Trường hợp ngược lại các mẫu của tập huấn luyện thuộc cả hai lớp “YES” và “NO” thì: + Chọn một thuộc tính X trong tập thuộc tính của tập mẫu dữ liệu. X có các giá trị v1, v2, ...vn. + Chia tập mẫu trong T thành các tập con T1, T2, T3,...Tn. Chia theo các giá trị của X. + Tạo n nút con Ti (i=1,2,..n) với nút cha là T. + Tạo các nhánh nối từ nút T đến các nút Ti (i = 1, 2, 3,..n) Thực hiện lặp cho các nút con Ti (i = 1, 2, .. n) và quay lại bước 2. Ví dụ: Cho tập dữ liệu huấn luyện thể hiện trong bảng, xây dựng cây quyết định đi Picnic. Ngày Áo Quần Giày Phương Tiện Đi Picnic N1 Áo dài Quần Jean Bốt Bus Không N2 Áo dài Quần Jean Bốt Xe máy Không N3 Áo phông Quần Jean Bốt Bus Có N4 Áo sơ mi Quần vải Bốt Bus Có 10 N5 Áo sơ mi Quần ngố Thể thao Bus Có N6 Áo sơ mi Quần ngố Thể thao Xe máy Không N7 Áo phông Quần ngố Thể thao Xe máy Có N8 Áo dài Quần vải Bốt Bus Không N9 Áo dài Quần ngố Thể thao Bus Có N10 Áo sơ mi Quần vải Thể thao Bus Có N11 Áo dài Quần vải Thể thao Xe máy Có N12 Áo dài Quần vải Bốt Xe máy Có N13 Áo phông Quần Jean Thể thao Bus Có N14 Áo sơ mi Quần vải Bốt Xe máy Không Bảng 2.1: Tập dữ liệu huấn luyện quyết định đi Picnic Bảng dữ liệu trên là một tập các mẫu mô tả quyết định đi Picnic. Ở bảng trên, thuộc tính Ngày được dùng để định danh (chỉ số). Các thuộc tính quần, áo, giầy, phương tiện là các thuộc tính ứng cử viên được dùng để xét. Còn thuộc tính đi picnic là thuộc tính khẳng định được dùng để phân lớp các mẫu dữ liệu. Khi đó cây quyết định được xây dựng theo thuật toán CLS đối với tập dữ liệu trong bảng được xây dựng như sau: Chọn thuộc tính Áo = {Áo sơ mi, Áo phông, Áo dài} ta có cây như sau: Áo [N1, N2, N3, N4, N5, N6, N7, N8, N9, N10, N11, N12, N13, N14] Áo dài [N1, N2, N8, N9, N11] Áo phông [N3, N7, N12, N13] Áo sơ mi [N4, N5, N6, N10, N14] Hình 2.1: Cây quyết định được xây dựng theo thuật toán CLS Với giá trị thuộc tính Áo = ”Áo dài “ các giá trị thuộc tính Đi Picnic của {N3, N7, N12, N13} đều có giá trị là có, chúng thuộc cùng lớp “có”. Đây là nút lá có nhãn là “có”. 11 Tiếp theo chọn thuộc tính Giầy = {bốt, thể thao} để mở rộng cho nhánh bên trái của cây, chúng ta được cây như hình 2.2 như sau: Áo [N1, N2, N3, N4, N5, N6, N7, N8, N9, N10, N11, N12, N13, N14] Áo dài Áo phông [N3, N7, N12, N13] Giầy [N1, N2, N8, N9, N11] Bốt Có Áo sơ mi [N4, N5, N6, N10, N14] Không Giầy thể thao Không Có Hình 2.2: Mở rộng nhánh bên trái của cây quyết định Chọn thuộc tính Phương tiện = {xe bus, xe máy} để mở rộng cho nhánh bên phải chúng, ta được cây con sau: 12 Áo [N1, N2, N3, N4, N5, N6, N7, N8, N9, N10, N11, N12, N13, N14] Áo dài Giầy Áo phông [N3, N7, N12, N13] [N1, N2, N8, N9, N11] Bốt Có Giầy thể thao Không Áo sơ mi Phương tiện [N4, N5, N6, N10, N14] Xe máy Xe bus Có Không Có Hình 2.3: Mở rộng nhánh bên phải cây quyết định Hình 2.3 là kết quả thu được khi áp dụng thuật toán CLS cho tập dữ liệu huấn luyện trong bảng 2.1 với thứ tự các thuộc tính áo, giầy, phương tiện. Nếu áp dụng thuật toán CLS với thứ tự khác của thuộc tính ta sẽ thu được cây kết quả có hình dạng khác. 2.2.2 Thuật toán ID3 Thuật toán ID3 được công bố bởi Quainlan vào cuối thập niên 70 của thế kỷ XX. Sau đó, thuật toán ID3 được giới thiệu và trình bày trong mục Induction on decision tree, machine learning năm 1986. ID3 là một thuật toán đơn giản nhưng tỏ ra thành công trong nhiều lĩnh vực. ID3 thể hiện các khái niệm ở dạng cây quyết định. Biểu diễn này cho phép chúng ta xác định phân loại của đối tượng bằng cách kiểm tra giá trị của nó trên một số thuộc tính nào đó. Nhiệm vụ của thuật toán ID3 là học cây quyết định từ một tập dữ liệu rèn luyện. Giải thuật có: - Đầu vào: Một tập hợp các mẫu dữ liệu. Mỗi mẫu bao gồm các thuộc tính mô tả một tình huống hoặc một đối tượng nào đó và một giá trị phân loại của nó. 13