PHẦN MỞ ĐẦU. 1 1 Tính cấp thiết của đề tài. 1 2 Đối tƣợng nghiên cứu. Phạm vi nghiên cứu.
2 4 Mục tiêu nghiên cứu của đề tài. 2 5 Phƣơng pháp nghiên cứu. 2 6 Kết cấu của luận văn. 3 CHƢƠNG 1 TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ BÀI TOÁN PHÂN LỚP.
4 1 1 Tổng quan về khai phá dữ liệu. 4 1 1 2 Kiến trúc của một hệ thống khai phá dữ liệu. 7 1 2 Các hƣớng tiếp cận và kỹ thuật chính trong khai phá dữ liệu. Luật kết hợp.
10 1 3 Các dạng dữ liệu c thể khai phá. 11 1 4 Một số ứng dụng của khai phá dữ liệu. 12 1 5 Bài toán phân lớp. 13 1 5 2 Một số phƣơng pháp giải bài toán phân lớp.
14 1 6 Kết luận chƣơng 1. 17 vi CHƢƠNG 2 CÂY QUYẾT ĐỊNH VÀ CÁC THUẬT TOÁN XÂY DỰNG CÂY QUYẾT ĐỊNH. 18 2 1 Tổng quan về cây quyết định. 18 2 2 Thiết kế cây quyết định.
19 2 2 1 Xử lý dữ liệu. 19 2 2 3 Tiêu chuẩn tách. 19 2 2 4 Tiêu chuẩn dừng. 20 2 3 Phƣơng pháp tổng quát xây dựng cây quyết định.
20 2 4 Phƣơng pháp xây dựng cây quyết định ID3. 23 2 4 1 Tiêu chí lựa chọn thuộc tính để phân lớp. 23 2 4 2 Thuật toán ID3. 24 2 4 3 Độ phức tạp tính toán.
31 2 5 Phƣơng pháp xây dựng cây quyết định C4 5. 32 2 5 2 Xác định điểm chia tốt nhất .3 Một số vấn đề với thuộc tính. 35 2 6 Kết luận chƣơng 2. 37 CHƢƠNG 3 PHƢƠNG PHÁP XẾP LOẠI NGHIỆP TỐT NGHIỆP SINH VIÊN DỰA TRÊN CÂY QUYẾT ĐỊNH.
38 3 1 Bài toán xếp loại kết quả học tập sinh viên. 38 3 2 Tổ chức đào tào và xếp loại sinh viên của Khoa CNTT. Xây dựng cây quyết định và xếp loại tốt nghiệp sinh viên. 42 3 3 1 Tiền xử lý dữ liệu.
42 3 3 2 Cài đặt thuật toán xây dựng mô h nh cây quyết định. 54 3 4 Thử nghiệm và đánh giá. 56 3 4 Kết luận chƣơng 3. 60 TÀI LIỆU THAM KHẢO.
61 vii KÝ HIỆU VÀ TỪ VIẾT TẮT Các từ viết tắt: CSDL Cơ sở dữ liệu DT Cây quyết định (Decision Tree) ID3 Iterative Dichotomiser 3 IG Information Gain CART Classification and Regression Trees CHAID Chi-square Automatic Interaction Detection viii DANH MỤC CÁC BẢNG BIỂU Bảng 2 1 Bảng quyết định minh họa Ví dụ 2 1. 21 Bảng 2 2 Bảng quyết định minh họa thuật toán ID3. 27 Bảng 2 3 Tập dữ liệu c giá trị liên tục. 33 Bảng 3 1 Trích bảng điểm tích lũy các học phần của sinh viên.
42 Bảng 3 2 Bảng tổng hợp kết quả học tập của sinh viên. 43 Bảng 3 3 Bảng tổng hợp kết quả học tập của sinh viên K55 khoa Công nghệ thông tin. 44 Bảng 3 4 Thống kê số sinh viên đƣợc xếp loại A, B, C của tập dữ liệu học. 56 Bảng 3 5 Tổng hợp kết quả xếp loại tốt nghiệp của sinh viên bằng cây quyết định với thử nghiệm 90% học và 10% kiểm tra.
57 Bảng 3 6 Thống kê số sinh viên đƣợc xếp loại A, B, C của tập dữ liệu học. 57 Bảng 3 7 Tổng hợp kết quả xếp loại tốt nghiệp của sinh viên bằng cây quyết định với thử nghiệm 90% học và 10% kiểm tra. 58 ix DANH MỤC CÁC HÌNH VẼ H nh 1 1 Quá tr nh khai phá dữ liệu. 5 H nh 1 2 Kiến trúc của một hệ thống khai phá dữ liệu.
7 H nh 1 3 Mô tả luật kết hợp. 11 H nh 1 4 Bài toán phân lớp. 14 Hình 1 5 Xây dựng mô h nh phân lớp. 15 H nh 1 6 Ƣớc lƣợng độ chính xác của mô h nh.
16 H nh 1 7 Phân lớp dữ liệu mới. 16 H nh 2 1 Ví dụ cây quyết định ứng với bảng quyết định 2 1. 22 H nh 2 2 Cây quyết định bƣớc đầu ví dụ 2 2. Cây quyết định đƣợc xây dựng theo thuật toán ID3 ứng với Bảng quyết định 2 2.
Minh họa phân chia thuộc tính liên tục. 35 H nh 3 1 Sơ đ Xây dựng và sử dụng mô h nh cây quyết định xếp loại kết quả tốt nghiệp của sinh viên. 40 H nh 3 2 Biểu đ thống kê số sinh viên đƣợc xếp loại A (Giỏi), B (Khá), C (Trung bình). 53 H nh 3 3 Biểu đ thống kê tổng số điểm của từng loại điểm của dữ liệu.
54 H nh 3 4 Sơ đ kiến trúc cài đặt ứng dụng xếp loại sinh viên. 54 H nh 3 5 Các lớp của g i Data. 55 H nh 3 6 Các lớp của g i DecisionTree. 55 1 PHẦN MỞ ẦU 1.
Tính cấp thiết của đề tài Ngày nay với sự phát triển của công nghệ thông tin, chúng ta đang bƣớc vào nền công nghiệp 4.0 nền tảng của nó là trí tuệ nhân tạo, tự động hóa và các hệ thống thông minh Trƣớc những yêu cầu của thực tế các nghiên cứu phát triển các ứng dụng của công nghệ thông tin ngày càng mạnh mẽ. Nhiều hƣớng nghiên cứu đã mở ra nhƣ: trí tuệ nhân tạo, khai phá dữ liệu, rô bốt, hệ không ngƣời lái,… Nh n chung tất cả các hƣớng đều nhắm tới việc tạo ra các hệ thống thông minh có khả năng lập luận. Một trong những hƣớng nghiên cứu giải quyết bƣớc đầu cho yêu cầu này là khai phá dữ liệu nhằm xây dựng dựng đƣợc các mô hình có khả năng dự đoán với các thông tin trong tƣơng lai Trong khai phá dữ liệu đƣợc chia thành nhiều bài toán khác nhau nhƣ phân lớp, phân cụm, nhận dạng mẫu, luật kết hợp. Bài toán phân lớp dữ liệu là một trong những bài toán điển hình trong lĩnh vực khai phá dữ liệu.
Nhiều phƣơng pháp đề xuất để giải quyết bài toán này nhƣ cây quyết định, mạng nơ ron, máy v c tơ hỗ trợ (SVM), hệ mờ dựa trên luật,. Một trong những hƣớng tiếp cận hiệu quả và có ứng dụng nhiều trong thực tiễn đ là cây quyết định đƣợc Quinland đề xuất lần đầu cuối những năm 1970 và đầu những năm 1980 trong [8] Quinland đã phát triển thành công phần mềm gọi ID3. Kết quả nghiên cứu này tiếp tục đƣợc E. Quinlan phát triển thành công C4.5 khắc phục một số hạn chế của cây ID3 Cho đến nay cây quyết định có nhiều phiên bản cải tiến nhƣ CART, CHAID,.
[5] Ở Việt Nam chúng ta hiện nay, theo qui chế đào tạo đại học của Bộ Giáo dục và đào tạo hầu hết các trƣờng đại học, cao đẳng đã chuyển từ đào tạo niên chế sang đào tạo theo tín chỉ giống nhƣ các nền giáo dục tiên tiến trên thế giới. Với hệ thống đào tạo theo tín chỉ th điểm của các môn học đƣợc cho bằng chữ: A, B, C, D, F [2]. Với các điểm chữ này chúng ta không thể xếp loại đƣợc sinh 2 viên theo thang chia: Yếu, Trung bình, Khá, Giỏi, Xuất sắc Để giải quyết vấn đề này ngƣời ta lại chuyển đổi các điểm chữ về điểm số, quá trình chuyển đổi từ số thành chữ và ngƣợc lại là một phép chuyển đổi mất mát thông tin dẫn đến có nhiều thiệt thòi cho sinh viên. Để giải quyết vấn đề nêu trên, đòi hỏi chúng ta cần xây dựng một phƣơng pháp xếp loại sinh viên dựa trên chính các điểm chữ.
Từ yêu cầu đ trong luận văn này chúng tôi tập trung nghiên cứu và đề xuất một phƣơng pháp xếp loại sinh viên trực tiếp trên điểm chữ bằng mô hình cây quyết định. ối tƣợng nghiên cứu Đối tƣợng nghiên cứu: khai phá dữ liệu, các hƣớng tiếp cận giải bải toán phân lớp, cây quyết định, phƣơng pháp đánh giá xếp loại sinh viên. Phạm vi nghiên cứu Phạm vi nghiên cứu: tập trung nghiên cứu phƣơng pháp xây dựng xây dựng cây quyết định, phƣơng pháp lập luận trên cây quyết định Cài đặt thử nghiệm thuật toán xây dựng mô h nh trên cơ sở dữ liệu sinh viên trƣờng khoa Công nghệ thông tin – Trƣờng Đại học Giao thông vận tải. Mục tiêu nghiên cứu của đề tài Tìm hiểu sâu hơn các kiến thức về khai phá dữ liệu, các bài toán đang đƣợc giải quyết trong khai phá dữ liệu, phƣơng pháp xây dựng cây quyết định, xây dựng thành công hệ thống học máy tạo ra cây quyết định từ cơ sở dữ liệu điểm của sinh viên.
Phƣơng pháp nghiên cứu Nghiên cứu lý thuyết kết hợp với cài đặt thực nghiệm, phân tích đánh giá trên dữ liệu thực tế. Kết cấu của luận văn Chƣơng 1 Tổng quan về khai phá dữ liệu và bài toán phân lớp Chƣơng 2 Cây quyết định và các phƣơng pháp xây dựng cây quyết định Chƣơng 3 Phƣơng pháp xếp loại tốt nghiệp sinh viên dựa trên cây quyết định 4 CHƢƠNG 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ BÀI TOÁN PHÂN LỚP 1. Tổng quan về khai phá dữ liệu 1.
Khái niệm Khai phá dữ liệu (data mining) là một khái niệm ra đời vào những năm cuối của thập kỷ 1980. Nó là quá trình khám phá thông tin ẩn đƣợc tìm thấy trong các cơ sở dữ liệu có thể xem nhƣ là một bƣớc trong quá trình khám phá tri thức Data Mining là gia đoạn quan trọng nhất trong tiến trình khai phá tri thức từ cơ sở dữ liệu, các tri thức này hỗ trợ trong việc ra quyết định trong khoa học và kinh doanh. Giáo sƣ Tom Mitchell [16] đã đƣa ra định nghĩa của Khai phá dữ liệu nhƣ sau: “Khai phá dữ liệu là việc sử dụng dữ liệu lịch sử để khám phá những qui tắc và cải thiện những quyết định trong tƣơng lai ” Với một cách tiếp cận ứng dụng hơn, Tiến sĩ Fayyad [17] đã phát biểu: “Khai phá dữ liệu, thƣờng đƣợc xem là việc khám phá tri thức trong các cơ sở dữ liệu, là một quá trình trích xuất những thông tin ẩn, trƣớc đây chƣa biết và có khả năng hữu ích, dƣới dạng các qui luật, ràng buộc, qui tắc trong cơ sở dữ liệu ” hay n i cách khác “Khai phá dữ liệu - Data Mining là tiến trình khám phá tri thức tiềm ẩn trong các cơ sở dữ liệu. Cụ thể hơn, đ là tiến trình trích lọc, sản sinh những tri thức hoặc các mẫu tiềm ẩn, chƣa biết nhƣng hữu ích từ cơ sở dữ liệu lớn” [3].