Tài liệu Hệ thống tư vấn và phân loại học sinh sử dụng kỹ thuật học máy tính

UBND TỈNH BÌNH DƯƠNG TRƯỜNG ĐẠI HỌC THỦ DẦU MỘT HỌ VÀ TÊN: TRÀ NHẤT LAN LUẬN VĂN TỐT NGHIỆP HỆ THỐNG TƯ VẤN VÀ PHÂN LOẠI HỌC SINH SỬ DỤNG KỸ THUẬT HỌC MÁY CHUYÊN NGÀNH: HỆ THỐNG THÔNG TIN MÃ NGÀNH: 8480104 LUẬN VĂN THẠC SỸ NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS QUẢN THÀNH THƠ BÌNH DƯƠNG, năm 2019 LỜI CAM ĐOAN Đề tài “Xây dựng hệ thống tư vấn và phân loại học sinh sử dụng kỹ thuật học máy” là công trình nghiên cứu do tôi thực hiện. Các số liệu, kết quả nêu trong luận văn là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác. Tác giả xin cam đoan những lời nêu trên là hoàn toàn đúng sự thật. Bình Dương, ngày 28 tháng 2 năm 2019 Học viên TRÀ NHẤT LAN Trang: i LỜI CẢM ƠN Em xin được gửi lời cảm ơn chân thành đến quý Thầy Cô Trường Đại học Thủ Dầu Một đã trang bị cho em những kiến thức, kỹ năng cần thiết trong suốt khóa học để em có thể hoàn thành được nội dung chương trình học của trường. Em chân thành cảm ơn Thầy PGS.TS. Quản Thành Thơ đã khuyến khích, động viên và tận tình hướng dẫn em trong quá trình thực hiện luận văn thạc sỹ. Chúng tôi rất mong nhận được sự góp ý của quý thầy cô để luận vặn đạt được kết quả tốt nhất. Cuối cùng, em xin cảm ơn gia đình, bạn bè, đồng nghiệp đã luôn động viên, giúp đỡ em trong suốt quá trình học và hoàn thành luận văn này. Tôi xin chúc quý thầy cô, các bạn thật nhiều sức khỏe, nhiều niềm vui trong cuộc sống, thành công trong công việc. Trang: ii MỤC LỤC DANH MỤC TỪ VIẾT TẮT ......................................................................................... v DANH MỤC CÁC BẢNG ............................................................................................. v DANH MỤC BIỂU ĐỒ, ĐỒ THÌ, HÌNH ẢNH, SƠ ĐỒ .............................................. v TÓM TẮT LUẬN VĂN ................................................................................................ vi MỞ ĐẦU ........................................................................................................................ 1 CHƯƠNG 1. GIỚI THIỆU ............................................................................................ 2 1.1. Phân lớp dữ liệu ................................................................................................. 2 1.2. Tình hình nghiên cứu ......................................................................................... 2 1.3. Mục tiêu của đề tài ............................................................................................. 2 1.4. Nội dung và phương pháp nghiên cứu ............................................................... 2 CHƯƠNG 2. MÔ HÌNH VÀ PHƯƠNG PHÁP NGHIÊN CỨU .................................. 4 2.1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU ........................................................ 4 2.1.1. Khái niệm .................................................................................................. 4 2.2. MỘT PHƯƠNG PHÁP HỌC MÁY PHỔ BIẾN .............................................. 5 2.2.1. Khái niệm học máy.................................................................................... 5 2.2.2. Một số phương pháp học máy ................................................................... 5 2.2.2.1. Học có giám sát ...................................................................................... 5 2.2.2.2. Học không có giám sát ........................................................................... 6 2.2.2.3. Học bán giám sát .................................................................................... 6 2.2.3. Một số thuật toán học máy ........................................................................ 6 2.2.3.1. Hồi quy tuyến tính (Linear regression) .................................................. 6 2.2.3.2. Thuật toán cây quyết định (Decision trees) ............................................ 7 2.2.3.3. Thuật toán K_means ............................................................................... 7 2.2.3.4. Thuật toán K láng giềng gần nhất (K-nearest neighbors) ...................... 7 2.3. PHƯƠNG PHÁP RANDOM FOREST ............................................................. 7 2.3.1. Cây quyết định ........................................................................................... 7 2.3.2. Rừng ngẫu nhiên (Random Forest) ........................................................... 8 2.4. Một số công trình nghiên cứu liên quan ............................................................ 8 CHƯƠNG 3. XÂY DỰNG MÔ HÌNH DỰ ĐOÁN ĐIỂM CỦA HỌC SINH DÙNG RANDOM FOREST ........................................................................................ 10 3.1. MÔ TẢ DỮ LIỆU BÀI TOÁN ........................................................................ 10 3.2. MÔ HÌNH HUẤN LUYỆN ............................................................................. 13 Trang: iii 3.2.1. MÔ HÌNH DÙNG TRONG RANDOM FOREST ................................. 13 3.2.2. Xây dựng Cây quyết định dùng CART ................................................... 13 3.2.3. Xây dựng Rừng ngẫu nhiên (Random Forest) ........................................ 14 3.2.4. Áp dụng Rừng ngẫu nhiên ....................................................................... 15 3.3. GIAO DIỆN ..................................................................................................... 15 3.4. Chức năng dự đoán: ......................................................................................... 15 3.4.1. Chức năng dự đoán các môn khối tự nhiên ............................................. 18 3.4.2. Chức năng dự đoán các môn khối xã hội: ............................................... 19 3.5. Chức năng phân loại và tư vấn học sinh .......................................................... 19 3.6. Các bước tiền xử lý dữ liệu .............................................................................. 20 CHƯƠNG 4. THỰC NGHIỆM .................................................................................... 23 4.1. Mô tả dữ liệu huấn luyện ................................................................................. 23 4.2. Dữ liệu huấn luyện ........................................................................................... 23 4.3. Tính độ tương quan .......................................................................................... 24 4.4. So sánh với các thuật toán học máy khác ........................................................ 25 4.5. So sánh độ tương khối xã hội ........................................................................... 26 4.6. So sánh độ tương quan khối tự nhiên............................................................... 27 CHƯƠNG 5. GIAO DIỆN HỆ THỐNG ...................................................................... 28 5.1. Ngôn ngữ lập trình: .......................................................................................... 28 5.1.1. Ngôn ngữ lập trình Python 3.6 ................................................................ 28 5.2. Công cụ hỗ trợ .................................................................................................. 28 5.2.1. Phần mềm Jupyter Notebook .................................................................. 28 5.2.2. Visual Studio Code .................................................................................. 28 5.3. Thư viện hỗ trợ................................................................................................. 28 5.3.1. Thư viện numpy ...................................................................................... 28 5.3.2. Thư viện Pandas ...................................................................................... 29 CHƯƠNG 6. KẾT QUẢ ĐẠT ĐƯỢC VÀ HẠN CHẾ ............................................... 30 6.1. Kết quả đạt được đã làm được ......................................................................... 30 6.2. Hạn chế: ........................................................................................................... 30 6.3. Khuyến nghị ..................................................................................................... 30 TÀI LIỆU THAM KHẢO ............................................................................................ 31 Trang: iv DANH MỤC TỪ VIẾT TẮT 1. CART: Classification and Regression Tree 2. AI: Artificial Intelligence 3. RF: Random Forest 4. KNN: K – Nearest Neighbors DANH MỤC CÁC BẢNG 1. BẢNG 1: Thông kê độ tương quan của thuật toán. 2. BẢNG 2: Só sánh độ tương quan só với các thuật toán khác DANH MỤC BIỂU ĐỒ, ĐỒ THÌ, HÌNH ẢNH, SƠ ĐỒ 1. Hình 1: Quy trình khai phá dữ liệu. 2. Hình 2: Mô tả dữ liệu điểm năm học lớp 10. 3. Hình 3: Mô tả dữ liệu điểm năm học lớp 11. 4. Hình 4: Mô tả dữ liệu điểm năm học lớp 12. 5. Hình 5: Mô tả dữ liệu điểm thi tốt nghiệp. 6. Hình 6: Quy trình huấn luyện RF. 7. Hình 7: Quy trình xây dựng RF. 8. Hình 8: Minh họa mô hình hoạt động của hệ thống. 9. Hình 9: Quy trình hoạt động của hệ thống. 10. Hình 10: Minh họa module khối các môn tự nhiên. 11. Hình 11: Minh họa module khối các môn xã hội 12. Hình 12: Minh họa dự đoán các môn khối tự nhiên 13. Hình 13: Minh họa dự đoán các môn khối xã hội. 14. Hình 14: Quy trình chức năng phân loại và tư vấn 15. Hình 15: Minh họa dữ liệu điểm lớp 10. 16. Hình 16: Minh họa dữ liệu điểm đã được chuẩn hóa. 17. Hình 17: Minh họa dữ liệu huấn luyện. 18. Hình 18: Minh họa thuộc tính dữ liệu. 19. Hình 19: So sánh độ tương quan của khối xã hội 20. Hình 20: So sánh độ tương quan của khối tự nhiên. Trang: v TÓM TẮT LUẬN VĂN Với tốc độ phát triển mạnh mẽ của công nghệ thông tin thì việc ứng dụng công nghệ thông tin vào các lĩnh vực như: ý tế, giáo dục, kinh doanh được áp dụng rộng rãi. Trong đó lượng dữ liệu thu được là rất lớn, muốn khai thác được nguồn dữ liệu này thì việc áp dụng các phương pháp khai phá dữ liệu và học máy là rất cần thiết. Luận văn áp dụng kỹ thuật học máy để dự đoán kết quả thi tốt nghiệp trước kì thi tốt nghiệp của học sinh, luận văn được chia làm 6 chương. Chương 1: giới thiệu tình hình nghiên cứu và lý do chọn đề tài luận văn và mục tiêu thực hiện luận văn. Chương 2: giới thiệu các kiến thức nền tảng về khai thác dữ liệu và Trí tuệ nhận tạo (AI), và một số phương pháp học máy như: học có giám sát, học không có giám sát, học bán giám sát, học tăng cường. Giới thiệu về một số thuật toán của học máy cùng việc ứng dụng thuật toán Random Forest để dự đoán điểm thi trước kì thi tốt nghiệp của học sinh. Chương 3: mô tả về dữ liệu điểm của học sinh từ năm học lớp 10, lớp 11, lớp 12 và dữ liệu điểm thi tốt nghiệp của học sinh từ năm 2015 đến 2018 của học sinh trường Phổ Thông Trung Học Thanh Tuyền, từ dữ liệu ta tiến hành các bước chuẩn hóa dữ liệu điểm của học sinh để áp dụng vào mô hình hệ thống. Luận văn giới thiệu việc xây dựng mô hình CART và việc áp dụng thuật toán Random Forest vào bài toán dự đoán điểm thi tốt nghiệp của học sinh. Áp dụng thuật toán để xây dựng giao diện của hệ thống dự đoán điểm thi tốt nghiệp của học sinh. Chương 4: từ việc xây dựng hệ thống ta tiến hành kiểm thử và tính độ chính xác của mô hình hệ thống bằng công thức R Square Chương 5: giới thiệu về các chức năng của hệ thống và việc ứng dụng các ngôn ngữ lập trình, công cụ hỗ trợ và các thư việc hỗ trợ trong việc xây dựng hệ thống dự đoán điểm thi trước kì thi tốt nghiệp của học sinh. Chương 6: Đánh giá kết quả đạt được và những hạn chế trong việc áp dụng mô hình Random Forest (RF) vào xây dựng hệ thống và hướng phát triển sắp tới. Trang: vi MỞ ĐẦU Ngày nay nhu cầu ứng dụng công nghệ thông tin vào trong ngành giáo dục được ứng dụng rộng rãi trong các trường đại học, cao đẳng, trung cấp, trường Phổ Thông Trung Học. Nhưng đối với học sinh Phổ Thông Trung Học thì nhu cầu cần dự đoán điểm thi trước kì thi tốt nghiệp là một yêu cầu rất quan trọng. Từ đó học sinh sẽ tìm hiểu trường nào phù hợp, tham khảo một số ngành học trước kì thi để chuẩn bị trước khi nộp hồ sơ xét tuyển tuyển sinh đại học, cao đẳng, trung cấp. Nhằm giúp các em có thể dự đoán trước được điểm thi của mình có thể đạt được khi thi tốt nghiệp Trung Học Phổ Thông Quốc Gia, dưới sự hướng dẫn của thầy PGS.TS Quản Thành Thơ, tôi đã chọn đề tài nghiên cứu: “xây dựng hệ thống tư vấn và phân loại học sinh sử dụng kỹ thuật học máy” dựa trên cơ sở dữ liệu điểm của các môn học trong 3 năm học liên tiếp và điểm thị tốt nghiệp trước đó là lớp 10, 11, 12 và điểm thi tốt nghiệp. Hệ thống sẽ dự đoán điểm thi tốt nghiệp của học sinh trước kì thi tốt nghiệp để các em có thể biết trước năng lực của mình và sẽ cố gắn trong kì thi sắp tới từ đó các em cũng có thể biết được mình nên chọn trường nào để xét tuyển, ngành nào cho phù họp với bản thân của các em. Hệ thống sẽ dự đoán điểm thi của học sinh theo hai khối là khối các môn học tự nhiên và khối các môn học xã hội cho phù hợp với kết quả dự thi của các em. Dữ liệu của luận văn được lấy từ dữ liệu điểm thực tế của trường Phổ Thông Thanh Tuyền với dữ liệu từ năm 2015 đến năm 2018 và điểm thi tốt nghiệp của những năm này. “Hệ thống tư vấn và phân loại học sinh sử dụng kỹ thuật học máy” của em là sử kỹ thuật RF (Random forest Regression) để dự đoán điểm thi tốt nghiệp theo khối các môn học tự nhiên và khối các môn học xã hội dựa trên dữ liệu điểm của những năm học gần đây nhất. Trang: 1 CHƯƠNG 1. GIỚI THIỆU 1.1. Phân lớp dữ liệu Ngày nay phân lớp dữ liệu là trong những hướng nghiên cứu chính của khai phá dữ liệu. Phân lớp và dự đoán là hai dạng của phân tích dữ liệu nhằm rút ra một mô hình mô tả các lớp dữ liệu quan trọng hay dự đoán xu hướng dữ liệu trong tương lai. Phân lớp dự đoán những nhãn xác định hay những giá trị dữ liệu rời rạc có nghĩa là phân lớp thao tác với những đối tượng dữ liệu mà có bộ giá trị là biết trước. trong khi đó dự đoán lại xây dựng mô hình với các hàm nhận giá trị liên tục. 1.2. Tình hình nghiên cứu Trên thực tế, đã có nhiều nghiên cứu về phân lớp dữ liệu trong tất cả các lĩnh vực như: y tế, ngân hàng, khách sạn, siêu thị, giáo dục, … Nhưng ở Việt Nam thì lĩnh vực giáo dục thì có ít nghiên cứu về việc chuẩn đoán điểm thi tốt nghiệp trước kì thi tốt nghiệp Trung Học Phổ Thông dựa vào việc phân lớp dữ liệu dựa vào điểm của 3 năm học cấp ba và điểm thi tốt nghiệp Trung Học Phổ Thông những năm học trước đó (từ lớp 10 đến lớp 12 và điểm thi tốt nghiệp Trung Học Phổ Thông). 1.3. Mục tiêu của đề tài Khai thác dữ liệu điểm của học sinh ba năm học và điểm thi tốt nghiệp Trung Học Phổ Thông của học sinh. Từ dữ liệu điểm đã được tiền xử lý để phù hợp với việc “xây dựng hệ thông phân loại và tư vấn sử dụng kĩ thuật học máy”. Xây dựng hệ thống dự đoán điểm thi tốt nghiệp của học sinh trước kì thi tốt nghiệp theo hai khối: khối các môn học tự nhiên và khối các môn học xã hội. Từ đó, giúp cho học sinh biết được khả năng kiến thức của mình trước kì thi tốt nghiệp để có sự lựa chọn tốt hơn cho việc chọn trường, chọn ngành để xét tuyển sinh đại học trong các kì tuyển sinh đại học, cao đẳng, trung cấp trong năm học. 1.4. Nội dung và phương pháp nghiên cứu Nội dung chính là nghiên cứu về khai phá dữ liệu điểm của học sinh để xây dựng hệ thống và tư vấn và phân loại học sinh sử dụng kỹ thuật học máy. Trang: 2 Nghiên cứu là sự kết hợp giữa khai phá dữ liệu và thuật toán RF (Random Forest) để đưa ra dự đoán điểm thi trước kì thi tốt nghiệp Trung Học Phổ Thông Quốc Gia. Trang: 3 CHƯƠNG 2. MÔ HÌNH VÀ PHƯƠNG PHÁP NGHIÊN CỨU 2.1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 2.1.1. Khái niệm Khai phá dữ liệu (data mining) hay khám phá tri thức từ dữ liệu (knowledge discovery from data) là việc trích rút ra được các mẫu hoặc tri thức quan trọng (không tầm thường, ẩn, chưa được biết đến và có thể hữu ích) từ một lượng dữ liệu lớn để phục vụ cho một đích hữu ít trong công việc [1]. Quá trình khai phá dữ liệu phải được thực hiện theo các bước sau:  Tìm hiểu lĩnh vực và mục đích của bài toán, tri thức cụ thể của bài toán  Thu thập tập dữ liệu phù hợp  Làm sạch và tiền xử lý dữ liệu  Giảm kích thước dữ liệu, chuyển đổi dữ liệu  Lựa chọn chức năng khai phá dữ liệu: phân loại, gom cụm, dự báo, sinh ra các luật kết hợp.  Lựa chọn giải thuật khai phá dữ liệu phù hợp  Tiến hành khái phá dữ liệu.  Đánh giá kết quả thu được và biểu diễn tri thức.  Sử dụng tri thức được khai phá vào bài toán. Quá trình khai phá dữ liệu được biểu diễn theo mô hình sau: Hình 1: Quy trình khai phá dữ liệu Trang: 4 2.2. MỘT PHƯƠNG PHÁP HỌC MÁY PHỔ BIẾN 2.2.1. Khái niệm học máy Những năm gần đây, Trí Tuệ Nhân Tạo (AI), và cụ thể hơn là học máy nổi lên như một bằng chứng của cuộc cách mạng công nghiệp lần thứ tư. AI đang được ứng dụng rộng rãi vào mọi lĩnh vực trong đời sống mà có thể chúng ta không nhận ra. Xe tự hành của Google và Tesla, hệ thống tự gán nhãn khuôn mặt trong ảnh của Facebook, trợ lý ảo Siri của Apple, hệ thống gợi ý sản phẩm của Amazon, hệ thống gợi ý phim của Netflix, máy chơi cờ vây AlphaGo của Google DeepMind, …, chỉ là một trong những ứng dụng của AI vào trong cuộc sống. Học máy là một phần của AI hay học máy là một lĩnh vực nhỏ của Khoa Học Máy Tính, nó có khả năng tự học hỏi dựa trên dữ liệu đưa vào mà không cần phải được lập trình cụ thể [9]. Những năm gần đây, khi mà khả năng tính toán của các máy tính được nâng lên một tầm cao mới và lượng dữ liệu khổng lồ được thu thập bởi các hãng công nghệ lớn, học máy đã tiến thêm một bước dài và một lĩnh vực mới được ra đời gọi là học sâu. Học sâu đã giúp máy tính thực thi những việc tưởng chừng như không thể vào 10 năm trước. ví dụ: phân loại cả ngàn vật thể khác nhau trong các bức ảnh, tự tạo chú thích cho ảnh, bắt chước giọng nói và chữ viết của con người, giao tiếp với con người, hay thậm chí cả sáng tác văn hay âm nhạc. 2.2.2. Một số phương pháp học máy 2.2.2.1. Học có giám sát Học có giám sát là thuật toán dự đoán đầu ra của một dữ liệu mới dựa trên các cặp dữ liệu vào và ra đã biết từ trước. Cặp dữ liệu này còn được gọi là dữ liệu, nhãn. Học có giám sát là nhóm phổ biến nhất trong các thuật toán học máy. Một cách toán học, học có giám sát là khi chúng ra có một tập hợp biến đầu vào X= {x1, x2, …, xn} X= {x1, x2, …, xn} và một tập hợp nhãn tương ứng Y={y1, y2, …, yn} Y= {y1, y2, …, yn}, trong đó xi, yi là các vector. Các cặp dữ liệu biết trước (xi, yi) ∈X×Y (xi, yi) ∈X×Y được gọi là tập dữ liệu huấn luyện. Từ tập dữ liệu huấn luyện này, chúng ta cần tạo ra một hàm số ánh xạ mỗi phần tử từ tập X sang một phần tử tương ứng của tập Y: Trang: 5 yi≈f(xi), ∀i=1,2, …, n yi≈f(xi), ∀i=1,2, …, n. Mục đích là xấp xỉ hàm số f thật tốt để khi có một dữ liệu x mới, chúng ta có thể tính được nhãn tương ứng của nó y=f(x). 2.2.2.2. Học không có giám sát Trong thuật toán này, chúng ta không biết được kết quả hay nhãn mà chỉ có dữ liệu đầu vào. Thuật toán không giám sát sẽ dựa vào cấu trúc của dữ liệu để thực hiện một công việc nào đó, ví dụ như phân nhóm hoặc giảm số chiều của dữ liệu để thuận tiện trong việc lưu trữ và tính toán. Một cách toán học, học không giám sát là khi chúng ta chỉ có dữ liệu vào X mà không biết nhãn Y tương ứng. Những thuật toán loại này được gọi là học không giám sát vì không giống như học có giám sát, chúng ta không biết câu trả lời chính xác cho mỗi dữ liệu đầu vào. Giống như khi ta học, không có thầy cô giáo nào chỉ cho ta biết đó là chữ A hay chữ B. Cụm không giám sát được đặt tên theo nghĩa này. 2.2.2.3. Học bán giám sát Các bài toán khi chúng ta có một lượng lớn dữ liệu X nhưng chỉ một phần trong chúng được gán nhãn được gọi là học bán giám sát. Những bài toán thuộc nhóm này nằm giữa hai nhóm được nêu bên trên. Một ví dụ điển hình của nhóm này là chỉ có một phần ảnh hoặc văn bản được gán nhãn (ví dụ bức ảnh về người, động vật hoặc các văn bản khoa học, chính trị) và phần lớn các bức ảnh, văn bản khác chưa được gán nhãn được thu thập từ internet. Thực tế cho thấy rất nhiều các bài toán học máy thuộc vào nhóm này vì việc thu thập dữ liệu có nhãn tốn rất nhiều thời gian và có chi phí cao. Rất nhiều loại dữ liệu thậm chí cần phải có chuyên gia mới gán nhãn được (ảnh y học chẳng hạn). 2.2.3. Một số thuật toán học máy 2.2.3.1. Hồi quy tuyến tính (Linear regression) Hồi quy tuyến tính là một thuật toán học có giám sát dự đoán một kết quả dựa trên các tính năng liên tục. Hồi quy tuyến tính linh hoạt theo nghĩa nó có thể chạy trên một biến duy nhất (hồi qui tuyến tính đơn giản) hoặc trên nhiều tính năng (hồi quy đa Trang: 6 tuyến tính nhiều). Hồi quy tuyến tính hoạt động bằng cách gán giá trị tối ưu cho các biến để tạo ra một đường thẳng (ax + b) sẽ được sử dụng để dự đoán một đầu ra. Hiện nay thuật toán này bị đánh giá là thấp nhất [9]. 2.2.3.2. Thuật toán cây quyết định (Decision trees) Thuật toán cây quyết định là một hình thức học có giám sát được sử dụng cho mục đích phân loại và hồi quy. Cây quyết định thường được sử dụng cho các mục đích phân loại. Trong thuật toán này, chúng ta chia thành hai hoặc các nhóm tập hợp. Điều này được thực hiện dựa trên các biến thuộc tính quan trọng nhất hoặc các biến độc lập để phân loại các nhóm có thể được. Thông thường, các thuộc tính quan trọng nhất trong quy trình sẽ gần với gốc của cây. Thuật toán cây quyết định đang ngày càng trở nên phổ biến và có thể xem như là một thuật toán mạnh mẽ cho tất cả các khoa học dữ liệu, đặc biệt là khi kết hợp với các kỹ thuật như random forests, boosting, và bagging. 2.2.3.3. Thuật toán K_means K-means là một thuật toán học không giám sát phổ biến thường được sử dụng để giải quyết vấn đề phân cụm. “K” đề cập đến số lượng người dùng nhập vào của các cụm. Thuật toán bắt đầu với các điểm được chọn ngẫu nhiên và sau đó tối ưu hóa các cụm bằng công thức khoảng cách để tìm nhóm các điểm dữ liệu tốt nhất. Cuối cùng, các nhà khoa học dữ liệu chọn đúng giá trị K. 2.2.3.4. Thuật toán K láng giềng gần nhất (K-nearest neighbors) K- láng giềng gần nhất (KNN) là một thuật toán phân loại có giám sát. Thuật toán KNN dựa vào các tâm điểm khác nhau và so sánh khoảng cách sử dụng một số chức năng. Sau đó, nó phân tích các kết quả và chỉ định mỗi điểm tối ưu nhất trong mỗi nhóm, để xác định điểm gần nhất với nó. 2.3. PHƯƠNG PHÁP RANDOM FOREST 2.3.1. Cây quyết định Cây quyết định (Decision tree) là một trong những thuật toán học máy đơn giản và phổ biến hiện nay. Cây quyết định là một phương pháp học có giám sát không tham Trang: 7 số. Mục tiêu là tạo ra một mô hình dự đoán giá trị của biến mục tiêu bằng cách học các quy tắc quyết định đơn giản được suy ra từ các đặc trưng trước của dữ liệu [8]. Trong mô hình cây quyết định, mỗi nút là một tập hợp các mẫu dữ liệu, các nhánh từ một nút là các điều kiện xét trên cùng một thuộc tính, các nút lá là các phân lớp. Có 2 loại cây quyết định: Cây hồi quy (Regression tree) ước lượng các hàm giá có giá trị là số thực thay vì được sử dụng cho các nhiệm vụ phân loại [8]. (ví dụ: ước tính giá một ngôi nhà hoặc khoảng thời gian một bệnh nhân nằm viện) Cây phân loại (Classification tree), nếu y là một biến phân loại như: giới tính (nam hay nữ), một trận đấu có diễn ra hay không. 2.3.2. Rừng ngẫu nhiên (Random Forest) Rừng ngẫu nhiên (RF) là một thuật toán học máy có giám sát, sử dụng các cây quyết định để làm nền tảng. Như tên gọi của nó, rừng ngẫu nhiên áp dụng các tính chất ngẫu nhiên dựa vào thuật toán cây quyết định [7]. Sau đó, Rừng ngẫu nhiên sẽ lựa chọn các kết quả dự đoán có số lượng cây cho ra nhiều nhất (classification) hay gần nhất (regression). 2.4. Một số công trình nghiên cứu liên quan Trong phần này sẽ nói đến các chủ đề liên quan và ứng dụng thuật toán Rangdom Forest vào trong việc phân loại và tuyên đón một số kết quả của nghiên cứu. Nghiên cứu của áp dụng thuật toán Random Forest để xây dựng bản đồ sử dụng đất, thảm phủ của tỉnh Đắk Lắk của nhóm tác giả Nguyễn Thị Thanh Hương và Đoàn Minh Trung trường đại học Nông Lâm Tây Nguyên đã nghiên cứu sử dụng phương pháp Random Forest chạy trên môi trường R để xây dựng bản đồ thảm phủ của tỉnh Đắk Lắk [7]. Nghiên cứu của Đồng Thị Ngọc Lan [2011] Trường đại học Công Nghệ Thông Tin đã áp dụng thuật toán Random Forest để giải quyết bài toán trích chọn thuộc tính nhằm làm tăng tính hiệu quả phân lớp đối với dữ liệu đa chiều [1]. Nghiên cứu của Nguyễn Bá Quân [2016] trường đại học Công Nghệ Hà Nội đã ứng dụng các phương pháp dự đoán và ứng dụng vào bài toán đoán nhận khả nằng ức chế gen của siRNA [2]. Nghiên cứu đã áp dụng các phương pháp học máy trong đó có Trang: 8 cả phương pháp Random Forest vào dự đoán ức chế gen để hỗ trợ cho y học trong việc điều chế thuốc. Trang: 9 CHƯƠNG 3. XÂY DỰNG MÔ HÌNH DỰ ĐOÁN ĐIỂM CỦA HỌC SINH DÙNG RANDOM FOREST 3.1. MÔ TẢ DỮ LIỆU BÀI TOÁN Dữ liệu là điểm các môn học ba năm liền từ lớp 10, 11, 12 và điểm thi tốt nghiệp của các em học sinh trường Phổ Thông Thanh Tuyền từ năm 2015 đến năm 2018. Tổng số dòng dữ liệu khoản 750 dòng được thệ hiện trên bố tập tin là điểm lớp 10, điểm lớp 11, điểm số 12, điểm thi tốt nghiệp. Tập tin dữ liệu điểm lớp 10 thể hiện điểm học của năm học đó gồm có 750 dòng và 18 cột dữ liệu. Cột dữ liệu gồm các thuộc tính sau: số thứ tự, họ tên học sinh, môn Toán, môn Lý, môn Hóa, môn Sinh, môn Tin học, môn Văn, môn Sử, môn Địa, môn Ngoại ngữ, môn Giáo dục công dân, môn Công nghệ, môn Thể dục, môn Giáo dục quốc phòng, cột điểm trung bình, cột học lực, cột hạnh kiểm. Hình 2: Mô tả dữ liệu điểm năm học lớp 10 Tập tin dữ liệu điểm lớp 11 thể hiện điểm học của năm học đó gồm có 750 dòng và 18 cột dữ liệu. Cột dữ liệu gồm các thuộc tính sau: số thứ tự, họ tên học sinh, môn Toán, môn Lý, môn Hóa, môn Sinh, môn Tin học, môn Văn, môn Sử, môn Địa, môn Trang: 10 Ngoại ngữ, môn Giáo dục công dân, môn Công nghệ, môn Thể dục, môn Giáo dục quốc phòng, cột điểm trung bình, cột học lực, cột hạnh kiểm. Hình 3: Mô tả dữ liệu điểm năm học lớp 11 Tập tin dữ liệu điểm lớp 12 thể hiện điểm học của năm học đó gồm có 750 dòng và 18 cột dữ liệu. Cột dữ liệu gồm các thuộc tính sau: số thứ tự, họ tên học sinh, môn Toán, môn Lý, môn Hóa, môn Sinh, môn Tin học, môn Văn, môn Sử, môn Địa, môn Ngoại ngữ, môn Giáo dục công dân, môn Công nghệ, môn Thể dục, môn Giáo dục quốc phòng, cột điểm trung bình, cột học lực, cột hạnh kiểm. Trang: 11 Hình 4: Mô tả dữ liệu điểm năm học lớp 12 Hình 5: Mô tả dữ liệu điểm thi lớp tốt nghiệp Trang: 12 Tập tin dữ liệu điểm thi tốt nghiệp thể hiện điểm thi các môn thi tốt nghiệp có 750 dòng và 18 cột dữ liệu. Cột dữ liệu gồm các thuộc tính sau: số thứ tự, lớp, họ tên học sinh, số chứng minh nhân dân, giới tính, ngày sinh, nơi sinh, dân tộc, mã tên hội đồng, môn Toán, môn Lý, môn Hóa, môn Sinh, môn Văn, môn Sử, môn Địa, môn Ngoại ngữ, môn Giáo dục công dân. 3.2. MÔ HÌNH HUẤN LUYỆN 3.2.1. MÔ HÌNH DÙNG TRONG RANDOM FOREST Để áp dụng mô hình huấn luyện RF vào bài toán dự đoán điểm thi trước kì thi tốt nghiệp được xây dựng theo hình minh họa sao sau: Hình 6: Quy trình huấn luyện của RF 3.2.2. Xây dựng Cây quyết định dùng CART CART: Classification and Regression Tree là một cây nhị phân. Ở mỗi nút của cây sẽ là điều kiện để phân chia tập dữ liệu theo một thuộc tính. Đối với bài toán hồi quy, giả sử tại nút I, chúng ta sẽ chia tập dữ liệu thành 2 tập con như sau: 𝐼 <= {𝑖 ∶ 𝑋ị𝑗 < 𝑉} 𝑎𝑛𝑑 𝐼 ≥ {𝑖 ∶ 𝑋ị𝑗 ≥ 𝑉} Sau đó chúng ta tính giá trị trung bình β của nhãn mỗi tập: Trang: 13