Tài liệu Phát triển hệ thống dự đoán điểm thi tốt nghiệp của học sinh thpt sử dụng kỹ thuật rừng ngẫu nhiên hồi quy

UBND TỈNH BÌNH DƯƠNG TRƯỜNG ĐẠI HỌC THỦ DẦU MỘT PHẠM THỊ HẢO PHÁT TRIỂN HỆ THỐNG DỰ ĐOÁN ĐIỂM THI TỐT NGHIỆP CỦA HỌC SINH THPT SỬ DỤNG KỸ THUẬT RỪNG NGẪU NHIÊN HỒI QUY CHUYÊN NGÀNH: HỆ THỐNG THÔNG TIN MÃ NGÀNH: 8480104 LUẬN VĂN THẠC SĨ BÌNH DƯƠNG, NĂM 2019 UBND TỈNH BÌNH DƯƠNG TRƯỜNG ĐẠI HỌC THỦ DẦU MỘT PHẠM THỊ HẢO PHÁT TRIỂN HỆ THỐNG DỰ ĐOÁN ĐIỂM THI TỐT NGHIỆP CỦA HỌC SINH THPT SỬ DỤNG KỸ THUẬT RỪNG NGẪU NHIÊN HỒI QUY 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 xin cam đoan luận văn “Phát triển hệ thống dự đoán điểm thi tốt nghiệp của học sinh trung học phổ thông sử dụng kỹ thuật rừng ngẫu nhiên hồi quy” là công trình nghiên cứu của tôi dưới sự hướng dẫn của PGS.TS Quản Thành Thơ xuất phát trên yêu cầu thực tế trong việc giảng dạy của tôi tại trường trung học phổ thông. Những nội dung được trình bày trong luận văn là quá trình học tập, tiếp thu và tích lũy kiến thức và là kết quả nghiên cứu của tôi, chưa từng công bố trước đây dưới bất cứ hình thức nào. Bình Dương, ngày … tháng… năm… Tác giả Phạm Thị Hảo LỜI CẢM ƠN Tôi xin chân thành cảm ơn quý thầy cô giáo trong khoa Kỹ thuật công nghệ trường đại học Thủ Dầu Một đã dạy dỗ truyền đạt những kiến thức quý báu cho tôi. Đặc biệt, tôi xin gửi lời cảm ơn sâu sắc đến PGS.TS Quản Thành Thơ đã tận tình hướng dẫn tôi để hoàn thành công trình nghiên cứu này. Tôi xin kính chúc quý thầy cô giáo luôn dồi dào sức khỏe để có thể tiếp tục sự nghiệp trồng người cao cả của mình. TÓM TẮT LUẬN VĂN Trong những năm gần đây, kì thi tốt nghiệp trung học phổ thông quốc gia thường xuyên được đổi mới về hình thức thi và nội dung đề thi. Do đó, giáo viên, phụ huynh và học sinh khối 12 ở các trường phổ thông càng quan tâm hơn nữa đến vấn đề học sinh được bao nhiêu điểm khi thi, liệu với những điểm đó có thể xét được các trường đại học nào… Vấn đề tiên đoán số điểm thi, các giáo viên giảng dạy trực tiếp có thể đoán được dựa trên năng lực học tập của các em hoặc các bậc phụ huynh sẽ đi xem bói để nghe thầy bói phán mà không có cơ sở khoa học nào, đôi khi dựa trên cảm tính. Ở lĩnh vực dự đoán, có rất nhiều mô hình sử dụng các kĩ thuật khác nhau như Weka, logic mờ, rừng ngẫu nhiên hồi quy… Rừng ngẫu nhiên là một phương pháp học tập chung để phân loại, hồi quy và các nhiệm vụ khác hoạt động bằng cách xây dựng vô số cây quyết định tại thời điểm đào tạo và đưa ra phân lớp (phân loại) hoặc dự đoán trung bình (hồi quy) của các cây riêng lẻ. Kể từ khi được giới thiệu bởi Breiman (2001), kĩ thuật rừng ngẫu nhiên đã thành công như một phương pháp phân loại và hồi quy có độ chính xác khá cao, được áp dụng vào nhiều mô hình tiên đoán. Trong đề tài luận văn này, tôi đề xuất một mô hình tiên đoán điểm thi tốt nghiệp trung học phổ thông quốc gia cho học sinh. Mô hình lấy điểm tổng kết các môn có tham gia thi để làm tập huấn luyện và tập kiểm thử trong kĩ thuật rừng hồi quy ngẫu nhiên để đưa ra các điểm dự đoán. Sau đó tiếp tục xây dựng hệ thống dự đoán điểm trên website để người dùng có thể nhập và dự đoán dựa vào mô hình đã xây dựng ở trên. 1 MỤC LỤC Đề mục ..................................................................................................... Trang Chương 1: Giới thiệu .................................................................................. 3 1.1 Đặt vấn đề ............................................................................................... 3 1.2 Mục tiêu và phạm vi nghiên cứu ............................................................ 3 1.3 Tổng quan về luận văn............................................................................ 4 Chương 2: Kiến thức nền tảng .................................................................. 5 2.1 Khai phá dữ liệu...................................................................................... 5 2.2 Học máy .................................................................................................. 6 2.3 Phương pháp rừng hồi quy ngẫu nhiên .................................................. 16 Chương 3: Xây dựng mô hình tiên đoán điểm bằng Random Forest ... 21 3.1 Kiến thức tổng quát của hệ thống ........................................................... 21 3.2 Mô tả dữ liệu của bài toán ...................................................................... 22 3.3 Chuẩn hóa dữ liệu để đưa vào mô hình Random Forest ........................ 23 Chương 4: Thí nghiệm ............................................................................... 24 4.1 Tập dữ liệu .............................................................................................. 24 4.2 Các thiết lập ............................................................................................ 24 4.3 Kết quả thực nghiệm ............................................................................... 25 4.4 Website tiên đoán điểm thi tốt nghiệp .................................................... 26 Chương 5: Công nghệ sử dụng .................................................................. 28 5.1 Ngôn ngữ lập trình .................................................................................. 28 5.2 Thư viện .................................................................................................. 28 5.3 Công cụ và thiết bị .................................................................................. 29 Chương 6: Tổng kết .................................................................................... 30 6.1 Kết quả đạt được ..................................................................................... 30 6.2 Tồn tại và hạn chế ................................................................................... 30 6.3 Hướng phát triển ..................................................................................... 30 THAM KHẢO ............................................................................................. 31 2 Chương 1. Giới thiệu 1.1 Đặt vấn đề Hàng năm, thi tốt nghiệp trung học phổ thông quốc gia luôn là mối quan tâm hàng đầu của phụ huynh và học sinh khối 12 trên cả nước. Gia đình luôn tạo điều kiện và thầy cô giáo luôn dành những nội dung ôn tập sâu sát nhất cho học sinh để các em đạt được điểm cao trong kì thi này, dành hi vọng sẽ đỗ tốt nghiệp và đỗ vào một trường đại học nào đó. Khi dạy các em trên lớp, thường thì các giáo viên căn cứ vào lực học có thể đưa ra những dự đoán điểm thi sắp tới cho học sinh. Từ những dự đoán này, các em có thể biết năng lực của mình đang đến đâu, cần phải nỗ lực thêm thế nào, mình có thể xét những trường đại học, cao đẳng nào thì vừa tầm… Tuy nhiên, những dự đoán đó chỉ là cảm tính, nhiều khi có pha thêm tình cảm của giáo viên nữa mà không có cơ sở khoa học nào. Xuất phát từ thực tiễn trên, đề tài này sử dụng kĩ thuật Random Forest Regression lấy dữ liệu là điểm tổng kết của các môn thi tốt nghiệp trung học phổ thông quốc gia để tiên đoán ra điểm thi tốt nghiệp của các em, đồng thời cập nhật điểm chuẩn của các trường đại học khu vực miền Nam của năm trước cho các em sự so sánh và dự đoán có thể xét được vào trường nào cho tương lai. 1.2 Mục tiêu và phạm vi nghiên cứu Thu thập dữ liệu điểm tổng kết các môn học của học sinh khối 12 lấy từ các trường THPT trên địa bàn huyện Phú Riềng của năm học 2017 – 2018. Đề xuất một mô hình Random Forest Regression vào việc phân loại điểm tổng kết của học sinh, sử dụng kĩ thuật phân lớp. Xây dựng một hệ thống sử dụng mô hình đã được huấn luyện để tiên đoán ra điểm thi tốt nghiệp trung học phổ thông quốc gia, từ đó xây dựng một website có thể tiên đoán điểm thi tốt nghiệp trung học phổ thông quốc gia khi người dùng nhập điểm tổng kết các môn có liên quan đến kì thi. 3 1.3 Tổng quan về luận văn Chương 1 Nội dung Giới thiệu chung về đề tài và tổng quan của luận văn Các kiến thức nền tảng cần có để xây dựng hệ thống dự đoán điểm. 2 Trong đó là những kiến thức về khai phá dữ liệu, các phương pháp học máy phổ biến và phương pháp rừng hồi quy ngẫu nhiên Trình bày về việc xây dựng mô hình tiên đoán điểm dựa trên kĩ 3 thuật Random Forest Regression, trong đó có kiến trúc tổng quát của hệ thống, mô tả dữ liệu và chuẩn hóa dữ liệu để đưa vào mô hình. Trình bày thí nghiệm của mô hình, bao gồm thực hiện thí nghiệm, 4 đánh giá kết quả của thí nghiệm dựa trên nhiều tập dữ liệu và trực quan hóa lên website. 5 6 Trình bày các công nghệ để hoàn thành đề tài bao gồm ngôn ngữ lập trình, các thư viện đã sử dụng và các công cụ liên quan. Tổng kết, đánh giá những tồn tại, hạn chế của đề tài, tìm hướng khắc phục và hướng phát triển của đề tài trong tương lai. Bảng 1 – Tổng quan về luận văn 4 Chương 2. Kiến thức nền tảng 2.1 Khai phá dữ liệu (Data Mining) 2.1.1 Khái niệm về khai phá dữ liệu Khai phá dữ liệu là quá trình khám phá các mẫu trong các tập dữ liệu lớn liên quan đến các phương pháp tại điểm giao nhau của máy học, thống kê và hệ thống cơ sở dữ liệu. Khai phá dữ liệu là một lĩnh vực liên ngành của khoa học và thống kê máy tính với mục tiêu tổng thể là trích xuất thông tin (bằng những phương pháp thông minh) từ bộ dữ liệu và chuyển đổi thông tin thành cấu trúc dễ hiểu để sử dụng tiếp dữ liệu. 2.1.2 Mục tiêu của khai phá dữ liệu Mục tiêu của khai phá dữ liệu là trích xuất các mẫu và kiến thức từ một lượng lớn dữ liệu. Khai phá dữ liệu là một từ thông dụng và thường được áp dụng cho bất kỳ dạng dữ liệu nào hoặc bất kỳ quy trình xử lý thông tin quy mô lớn nào (thu thập, trích xuất, lưu trữ, phân tích và thống kê) cũng như bất kỳ ứng dụng nào của hệ thống hỗ trợ quyết định bằng máy tính, bao gồm cả trí tuệ nhân tạo (Ví dụ: học máy) và kinh doanh thông minh. 2.1.3 Nhiệm vụ của khai phá dữ liệu Nhiệm vụ khai phá dữ liệu thực tế là phân tích bán tự động hoặc tự động một lượng lớn dữ liệu để trích xuất các mẫu thú vị chưa biết trước đây, như các nhóm các bản ghi dữ liệu (phân tích cụm), bản ghi bất thường (phát hiện bất thường) và phụ thuộc (khai thác quy tắc luật kết hợp, khai thác mô hình tuần tự). Điều này thường liên quan đến việc sử dụng các kỹ thuật cơ sở dữ liệu như các chỉ số không gian. Hình 1 – Minh họa về khai phá dữ liệu 5 2.2. Học máy (Machine Learning) 2.2.1 Khái niệm học máy Học máy là một lĩnh vực của trí tuệ nhân tạo liên quan đến việc nghiên cứu và xây dựng các kĩ thuật cho phép các hệ thống "học" tự động từ dữ liệu để giải quyết những vấn đề cụ thể. Tương quan với khai phá dữ liệu về một số phương pháp và công cụ, tuy nhiên đặc điểm khác biệt của học máy là dự đoán một số thông tin của dữ liệu dựa trên những đặc tính đã biết. 2.2.2 Các loại hệ thống máy học Có rất nhiều loại hệ thống Machine Learning khác nhau, sau đây là cách phân loại chúng theo các danh mục rộng dựa trên: • Có được đào tạo với sự giám sát của con người hay không (học có giám sát, học không giám sát, học bán giám sát và học tăng cường) • Có thể học tăng dần hay không (online learning so với batch learning) • Hoạt động bằng cách đơn giản là so sánh các điểm dữ liệu mới với các điểm dữ liệu đã biết, hoặc thay vào đó phát hiện các mẫu trong dữ liệu đào tạo và xây dựng một mô hình dự đoán, giống như các nhà khoa học thường làm (học tập dựa trên ví dụ so với dựa trên mẫu) Những tiêu chí này không độc quyền, có thể kết hợp chúng theo bất kỳ cách nào tuỳ thích. Ví dụ, bộ lọc thư rác tối tân nhất có thể học nhanh bằng cách sử dụng mô hình mạng nơ-ron sâu được đào tạo bằng cách sử dụng các ví dụ về thư rác và ham; điều này làm cho nó trở thành một hệ thống học tập trực tuyến, theo mô hình, có giám sát. 2.2.2.1 Học có giám sát Trong học tập có giám sát, dữ liệu đào tạo chúng ta cung cấp cho thuật toán bao gồm các giải pháp mong muốn, được gọi là nhãn (Hình 2) 6 Hình 2 - Một bộ đào tạo có nhãn cho việc học có giám sát (ví dụ: phân loại thư rác) Một công việc học tập có giám sát điển hình là phân loại. Bộ lọc thư rác là một ví dụ điển hình cho việc này: nó được đào tạo với nhiều email mẫu cùng với lớp của nó (spam hoặc ham) và nó phải học cách phân loại email mới. Một công việc điển hình khác là dự đoán một giá trị số mục tiêu, chẳng hạn như giá của một chiếc xe, đưa ra một bộ tính năng (số dặm, tuổi, thương hiệu, v.v.) được gọi là dự đoán. Loại công việc này được gọi là hồi quy (Hình 3). Để huấn luyện hệ thống, chúng ta cần cung cấp cho nó nhiều ví dụ về ô tô, bao gồm cả dự đoán và nhãn của chúng (ví dụ: giá của chúng). Hình 3 - Hồi quy 7 Lưu ý rằng một số thuật toán hồi quy cũng có thể được sử dụng để phân loại và ngược lại. Ví dụ: Hồi quy logistic thường được sử dụng để phân loại, vì nó có thể xuất ra một giá trị tương ứng với xác suất thuộc về một lớp nhất định (ví dụ: 20% khả năng là spam). Dưới đây là một số thuật toán học tập có giám sát quan trọng nhất. • K-nearest neighbors • Hồi quy tuyến tính - Linear Regression • Hồi quy Logistics • Support Vector Machines (SVMs) • Cây quyết định và rừng ngẫu nhiên - Decision Trees and Random Forests • Mạng nơ-ron 2.2.2.2 Học không giám sát Trong học tập không giám sát, dữ liệu đào tạo không được gắn nhãn (Hình 4). Hệ thống cố gắng học mà không có hướng dẫn Hình 4 - Một bộ đào tạo không có nhãn cho việc học tập không giám sát. Dưới đây là một số thuật toán học tập không giám sát quan trọng nhất: • Phân cụm: o K-means o Phân tích cụm phân cấp - Hierarchical Cluster Analysis (HCA) o Sự tối đa hóa kỳ vọng - Expectation Maximization • Trực quan hoá và giảm số chiều: o Principal Component Analysis (PCA) o Kernel PCA o Locally-Linear Embedding (LLE) o t-distributed Stochastic Neighbor Embedding (t-SNE) 8 • Học theo các quy tắc luật kết hợp: o Apirori o Eclat Ví dụ: giả sử chúng ta có rất nhiều dữ liệu về khách truy cập blog của mình. Chúng ta có thể muốn chạy một thuật toán phân cụm để cố gắng phát hiện các nhóm khách truy cập tương tự (Hình 5). Chúng ta không bao giờ nói với thuật toán mà khách truy cập thuộc về nhóm nào: nó tìm thấy các kết nối đó mà không cần sự giúp đỡ của chúng ta. Ví dụ: có thể nhận thấy rằng 40% khách truy cập của chúng ta là nam giới yêu thích truyện tranh và thường đọc blog của chúng ta vào buổi tối, trong khi 20% là những người yêu thích khoa học viễn tưởng trẻ ghé thăm vào cuối tuần, v.v. Nếu chúng ta sử dụng thuật toán phân cụm theo phân cấp, nó cũng có thể chia mỗi nhóm thành các nhóm nhỏ hơn. Điều này có thể giúp chúng ta nhắm mục tiêu bài viết của chúng ta cho mỗi nhóm. Hình 5 - Phân cụm Các thuật toán trực quan cũng là ví dụ điển hình của các thuật toán học không giám sát: chúng cung cấp cho chúng rất nhiều dữ liệu phức tạp và không có nhãn, và chúng đưa ra biểu diễn 2D hoặc 3D của dữ liệu của chúng ta mà có thể dễ dàng được vẽ (Hình 6). Các thuật toán này cố gắng bảo tồn càng nhiều cấu trúc càng tốt (ví dụ: cố gắng giữ các cụm riêng biệt trong không gian đầu vào không bị chồng chéo trong quá trình trực quan hóa), vì vậy chúng có thể hiểu cách tổ chức dữ liệu và có thể xác định các mẫu không bị ảnh hưởng. 9 Hình 6 - Ví dụ về một cụm ngữ nghĩa Một công việc là giảm kích thước chiều, trong đó mục tiêu là đơn giản hóa dữ liệu mà không mất quá nhiều thông tin. Một trong những cách để làm điều này là gộp một số tính năng tương quan thành một. Ví dụ, số dặm của xe hơi có thể rất tương quan với tuổi của nó, vì vậy thuật toán giảm kích thước sẽ hợp nhất chúng thành một tính năng đại diện cho sự hao mòn của xe hơi. Điều này được gọi là tỉa tính năng. Một công việc quan trọng khác nữa là phát hiện bất thường, ví dụ, phát hiện các giao dịch thẻ tín dụng bất thường để ngăn chặn gian lận, phát hiện lỗi sản xuất hoặc tự động xóa các ngoại lệ khỏi bộ dữ liệu trước khi đưa nó vào thuật toán học khác. Hệ thống được huấn luyện với các ví dụ bình thường và khi nhìn thấy một ví dụ mới, nó có thể cho biết liệu nó trông giống như một phiên bản bình thường hay liệu nó có khả năng là một sự bất thường. 10 Hình 7 - Phát hiện bất thường Cuối cùng, một công việc không giám sát phổ biến khác là học theo quy tắc kết hợp, trong đó mục tiêu là đào sâu vào một lượng lớn dữ liệu và khám phá mối quan hệ thú vị giữa các thuộc tính. Ví dụ: giả sử chúng ta sở hữu một siêu thị. Chạy một quy tắc kết hợp trên nhật ký bán hàng của chúng ta có thể tiết lộ rằng những người mua nước sốt thịt nướng và khoai tây chiên cũng có xu hướng mua bít tết. Vì vậy, chúng ta có thể sẽ muốn đặt các mặt hàng này gần nhau. 2.2.2.3 Học bán giám sát Một số thuật toán có thể xử lý dữ liệu đào tạo được dán nhãn một phần, thường là rất nhiều dữ liệu chưa được gắn nhãn và một ít dữ liệu được dán nhãn. Điều này được gọi là học bán giám sát (Hình 8). Hình 8 - Học bán giám sát Một số dịch vụ lưu trữ ảnh, như Google Photos, là ví dụ điển hình cho loại này. Khi bạn tải tất cả ảnh gia đình lên dịch vụ, nó sẽ tự động nhận ra rằng cùng một người 11 A xuất hiện trong các ảnh khác nhau. Đây là phần không được giám sát của thuật toán (phân cụm). Bây giờ tất cả những gì hệ thống cần là để bạn nói cho chúng biết những người này là ai. Chỉ cần một nhãn cho mỗi người và nó có thể đặt tên cho mọi người trong mỗi ảnh, rất hữu ích cho việc tìm kiếm ảnh. Hầu hết các thuật toán học bán giám sát là sự kết hợp của các thuật toán không giám sát và giám sát. Ví dụ, các mạng tin tưởng sâu (deep belief networks) dựa trên các thành phần không được giám sát được gọi là các máy Boltzmann hạn chế (restricted Boltzmann machines) bị xếp chồng lên lẫn nhau. RBM được đào tạo tuần tự theo cách không giám sát, và sau đó toàn bộ hệ thống được tinh chỉnh bằng cách sử dụng các kỹ thuật học tập có giám sát. 2.2.2.4 Học tăng cường Học tăng cường là một con kiểu rất khác. Hệ thống học tập, được gọi là một tác nhân trong bối cảnh này, có thể quan sát môi trường, lựa chọn và thực hiện các hành động và nhận lại kết quả tốt (hoặc kết quả xấu như trong hình 9). Sau đó, nó phải tự học theo chiến thuật tốt nhất, được gọi là chính sách, để nhận kết quả tốt nhiều nhất theo thời gian. Chính sách sẽ xác định hành động nào mà tác nhân nên chọn khi nó ở trong một tình huống nhất định. Hình 9 - Học tăng cường Ví dụ, nhiều robot thực hiện các thuật toán học tăng cường để học cách đi bộ. Chương trình AlphaGo của DeepMind cũng là một ví dụ điển hình của học tăng 12 cường: nó đã trở thành tiêu đề vào tháng 3 năm 2016 khi đánh bại nhà vô địch thế giới Lee Sedol tại trò chơi cờ vây. Nó học được chính sách chiến thắng của mình bằng cách phân tích hàng triệu trò chơi, và sau đó chơi nhiều trò chơi với chính nó. Việc học đã bị tắt trong các trò chơi chống lại nhà vô địch; AlphaGo chỉ đang áp dụng chính sách mà nó đã học. 2.2.3 Một số phương pháp học máy có giám sát phổ biến 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 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 này thuật toán này bị đánh giá là thấp nhất Hình 10 - Ví dụ về hồi quy tuyến tính đơn giản, có một biến độc lập 2.2.3.2 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ó. 13 Hình 11 – Ví dụ về thuật toán K-nearest neighbors 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. Hình 12 –Kết quả phân cụm K -means cho tập dữ liệu hoa Iris 2.2.3.4 Thuật toán cây quyết định (Decision trees) Cây quyết định 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 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. 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. 14 Hình 13 – Ví dụ về cây quyết định 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 (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) phân loại như: giới tính (nam hay nữ), một trận đấu có diễn ra hay không. Mỗi cây quyết định cho môt tập quy tắc phân lớp hoặc hồi quy: •  Mỗi đường di từ gốc đến là cho 1 luật •  Mỗi nút ≠ lá biểu thị một thuộc tính/điều kiện kiểm tra •  Mỗi cạnh biểu thị giá trị kiểm tra của thuộc tính tương ứng •  Mỗi lá cho một giá trị nhãn xác định bởi luật Hình 14 – Ví dụ về bài toán sử dụng cây quyết định 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. 15 2.3 Phương pháp Random Forest Regression 2.3.1 Khái niệm chung về rừng ngẫu nhiên Rừng ngẫu nhiên là một phương pháp học tập chung để phân loại, hồi quy và các nhiệm vụ khác, hoạt động bằng cách xây dựng vô số cây quyết định tại thời điểm đào tạo và đưa ra lớp (phân loại) hoặc dự đoán trung bình (hồi quy) của các cây riêng lẻ. Rừng ngẫu nhiên 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. 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. 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). Hình 15 - Ví dụ minh họa về rừng ngẫu nhiên Rừng ngẫu nhiên là một bộ nhận dạng bao gồm một tập bộ phân lớp cơ sở dạng cây quyết định được kết hợp theo phương thức bỏ phiếu. Các bộ cơ sở được xây dựng từ các tập dữ liệu con với tập con đặc trưng khác nhau được lấy ngẫu nhiên từ tập dữ liệu quan sát được. Theo một số đánh giá của các nhà khoa học thì thuật toán Random Forest có một số lợi thế như khả năng miễn nhiễm với những dữ liệu vô nghĩa, các đặc trưng không quan trọng và nhầm lẫn trong dữ liệu đầu vào. Random Forest là một trong những thuật toán học máy phổ biến nhất và mạnh mẽ nhất, thường được sử dụng trong các mô hình dự đoán, cho kết quả khả quan so với các thuật toán khác. 16