Tài liệu Phân lớp dữ liệu sinh viên để tư vấn học sinh lựa chọn ngành trong trung tâm elearning

BỘ GIÁO DỤC VÀ ĐÀO TẠO NGUYỄN HỮU TOÀN TRƢỜNG ĐẠI HỌC MỞ HÀ NỘI LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN CHUYÊN NGÀNH: CÔNG NGHỆ THÔNG TIN PHÂN LỚP DỮ LIỆU SINH VIÊN ĐỂ TƢ VẤN HỌC SINH LỰA CHỌN NGÀNH TRONG TRUNG TÂM ELEARNING NGUYỄN HỮU TOÀN 2016 - 2018 HÀ NỘI - 2018 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC MỞ HÀ NỘI LUẬN VĂN THẠC SỸ PHÂN LỚP DỮ LIỆU SINH VIÊN ĐỂ TƢ VẤN HỌC SINH LỰA CHỌN NGÀNH TRONG TRUNG TÂM ELEARNING NGUYỄN HỮU TOÀN CHUYÊN NGÀNH : CÔNG NGHỆ THÔNG TIN MÃ SỐ: 8.48.02.018 PGS.TS. NGUYỄN QUANG HOAN HÀ NỘI - 2018 LỜI CAM ĐOAN Tôi cam đoan đây là công trình nghiên cứu của riêng tôi. 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. Hà Nội, ngày 28 tháng 12 năm 2018 HỌC VIÊN Nguyễn Hữu Toàn i LỜI CẢM ƠN Em xin chân thành cảm ơn Trung tâm Đào tạo Elearning – Trƣờng Đại học Mở Hà Nội đã tạo điều kiện thuận lợi giúp em hoàn thành luận văn này. Em xin chân thành cảm ơn sự hƣớng dẫn, chỉ bảo tận tình của PGS.TS. Nguyễn Quang Hoan trong suốt thời gian thực hiện đề tài, cảm ơn thày đã luôn dành thời gian giúp đỡ em để có thể hoàn thành đƣợc luận văn này. Em xin bày tỏ lòng biết ơn đến các thầy cô trong Khoa Đào tạo Sau Đại học Trƣờng Đại học Mở Hà Nội đã cung cấp những kiến thức quý báu cho tôi trong suốt quá trình học tập và nghiên cứu tại trƣờng. Tôi cũng xin gởi lời cảm ơn đến gia đình, bạn bè và những ngƣời thân luôn quan tâm và giúp đỡ tôi trong suốt thời gian học tập và làm luận văn. Do thời gian và kiến thức có hạn nên luận văn chắc không tránh khỏi những thiếu sót nhất định. Kính mong nhận đƣợc sự thông cảm và đóng góp ý kiến của quý Thầy Cô và các bạn. ii MỤC LỤC LỜI CAM ĐOAN .............................................................................................. i LỜI CẢM ƠN ................................................................................................... ii MỤC LỤC ........................................................................................................ iii DANH MỤC CÁC THUẬT NGỮ VIẾT TẮT TIẾNG ANH ......................... v DANH MỤC CHỮ VIẾT TẮT TIẾNG VIỆT ................................................ vi DANH SÁCH CÁC BẢNG ............................................................................ vii DANH SÁCH CÁC HÌNH VẼ ...................................................................... viii LỜI MỞ ĐẦU ................................................................................................... 1 CHƢƠNG 1. PHƢƠNG PHÁP PHÂN LỚP DỮ LIỆU .................................. 4 1.1. Khái quát về phân lớp dữ liệu ..........................................................................4 1.1.1. Phân lớp dữ liệu .......................................................................................4 1.1.2. Các vấn đề liên quan đến phân lớp dữ liệu ..............................................8 1.2. Phân lớp dữ liệu bằng cây quyết định ............................................................11 1.2.1. Định nghĩa .............................................................................................. 11 1.2.2. Xây dựng cây quyết định ........................................................................12 1.2.3. Các đặc trưng trong phân lớp dữ liệu sử dụng cây quyết định ..............12 1.2.4 Đánh giá cây quyết định trong phân lớp dữ liệu .....................................14 1.3. Phân lớp dữ liệu bằng mạng Naïve Bayes .....................................................16 1.4. Phân lớp dữ liệu bằng Neural Network .........................................................17 1.5. Tình hình nghiên cứu các giải thuật hiện nay ................................................18 1.6. Kết luận chƣơng 1 ..........................................................................................19 CHƢƠNG 2. GIẢI THUẬT C4.5 VÀ NAIVE BAYES ................................ 20 2.1. Giải thuật C4.5 ...............................................................................................20 2.1.1. Tổng quan về giải thuật ..........................................................................20 2.1.2. Sử dụng Gain – Entropy làm độ lựa chọn thuộc tính “tốt nhất” ...........22 2.1.3. Ví dụ minh họa cho giải thuật C4.5 ........................................................23 2.1.4. Xử lý những giá trị thiếu trong C4.5 ......................................................29 2.1.5. Tránh quá vừa dữ liệu ............................................................................30 2.1.6. Chuyển đổi từ cây quyết định sang luật .................................................31 2.1.7 Hiệu quả cho những tập dữ liệu vừa và nhỏ ...........................................32 iii 2.2. Giải thuật Naïve Bayes đơn giản ...................................................................32 2.2.1. Ý tưởng và mục đích của giải thuật ........................................................32 2.2.2. Thuật giải Naïve Bayes ...........................................................................32 2.2.3. Ví dụ minh họa cho giải thuật Naïve Bayes ...........................................34 2.3. Đánh giá độ hiệu quả của thuật giải dùng ma trận ........................................35 2.4. Kết luận chƣơng 2 ..........................................................................................38 CHƢƠNG 3. PHÂN LỚP DỮ LIỆU SINH VIÊN VÀ ỨNG DỤNG TƢ VẤN CHỌN NGÀNH .............................................................................................. 39 3.1. Giới thiệu bài toán .........................................................................................39 3.2. Khảo sát và thu thập dữ liệu ..........................................................................40 3.3. Xử lý dữ liệu ..................................................................................................45 3.3.1. Trích chọn đặc trưng ..............................................................................45 3.3.2 Chuyển đổi dữ liệu ...................................................................................45 3.3.3. Làm sạch dữ liệu.....................................................................................47 3.4 Phân lớp dữ liệu sinh viên sử dụng giải thuật C4.5 ........................................47 3.4.1. Áp dụng giải thuật ..................................................................................47 3.4.2 Chạy giải thuật C4.5 (J48) trên phần mềm Weka ...................................48 3.5 Ứng dụng tƣ vấn chọn ngành sử dụng giải thuật Naïve Bayes ......................57 3.5.1 Tổng quan về ứng dụng ...........................................................................57 3.5.2 Mô hình cấu trúc hệ thống.......................................................................58 3.5.3 Phân tích và thiết kế hệ thống .................................................................58 3.6 So sánh kết quả giải thuật C4.5 và Naïve Bayes ............................................70 3.7 Kết luận chƣơng 3 ...........................................................................................71 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ...................................................... 72 1. Kết quả đạt đƣợc từ nghiên cứu ........................................................................72 2. Đóng góp luận văn ............................................................................................72 3. Hạn chế .............................................................................................................73 DANH MỤC TÀI LIỆU THAM KHẢO ........................................................ 74 PHỤ LỤC ........................................................................................................ 76 iv DANH MỤC CÁC THUẬT NGỮ VIẾT TẮT TIẾNG ANH Viết tắt Tiếng Anh Tiếng Việt ACC Accuracy Độ chính xác ANN Artificial Neural Network Mạng nơ-rôn nhân tạo FDR False Discovery Rate Tỷ lệ khám phá sai FN False Negative Sai âm tính FNR False Negative Rate Tỷ lệ bỏ lỡ hoặc tỷ lệ nhầm sang âm FOR False Omission Rate Tỷ lệ bỏ sót sai FP False Positive Nhầm sang dƣơng G Gain Độ lợi GR Gain Ratio Tỉ số độ lợi ID3 Inductive Dichotomizer 3 Giải thuật quy nạp cây ID3 IG Information Gain Độ lợi thông tin MCC Matthews Correlation Coefficient Hệ số tƣơng quan Matthews MLP Multilayer Perceptron Mạng nơ-rôn Perceptron N Condition Negatives Điều kiện phủ định NB Naïve Bayes Naïve Bayes (Giải thuật Bayes) NN Neural Network Mạng nơ-rôn Perceptron NPV Negative Predictive Value Giá trị tiên đoán âm P Condition Positive Điều kiện dƣơng PPV Precision or positive predictive value Giá trị tiên đoán chính xác hoặc tích cực SplitInfor Split Information Thông tin của phân phối dữ liệu SQL Structured Query Language Ngôn ngữ truy vấn mang tính cấu trúc TN True Negative Âm tính thực TNR Specificity or True Negative Rate Cụ thể hoặc tỷ lệ tiêu cực thực sự TP True Positive Dƣơng tính thực TPR Sensitivity - Recall Tỷ lệ thực dƣơng v DANH MỤC CHỮ VIẾT TẮT TIẾNG VIỆT Chữ viết tắt Chữ gốc CĐ Cao đẳng CNTT Công nghệ Thông tin CSDL Cơ sở dữ liệu ĐH Đại học ĐTB Điểm trung bình G Giỏi K Khá KPDL Khai phá dữ liệu KT Kế toán LKT Luật Kinh tế NNA Ngôn ngữ Anh NNLT Ngôn ngữ lập trình NST Nhóm sở thích QĐ QTKD Quyết định Quản trị Kinh doanh ST SV Sở thích Sinh viên TB Trung bình THPT Trung học phổ thông vi DANH SÁCH CÁC BẢNG Bảng 2.1. Bảng cơ sở dữ liệu dự đoán chọn ngành...................................................23 Bảng 2.2. Bảng cơ sở dữ liệu dự đoán ngành cho học sinh ......................................34 Bảng 2.3. Ma trận Confusion [13,14] ......................................................................36 Bảng 3.1. Bảng cấu trúc dữ liệu ................................................................................40 Bảng 3.2. Bảng tập luật áp dụng giải thuật C4.5 ......................................................54 Bảng 3.3. Bảng thông tin dữ liệu khảo sát ................................................................ 59 Bảng 3.4. Bảng thông tin dữ liệu đã đƣợc làm sạch .................................................60 Bảng 3.5. Bảng thông tin nhóm sở thích và khả năng ..............................................60 Bảng 3.6. Bảng thông tin học sinh tham gia tƣ vấn ..................................................61 Bảng 3.7. Bảng thông tin kết quả dự đoán chọn ngành ............................................61 Bảng 3.8. Dữ liệu mẫu cần dự báo trong Bayes........................................................66 Bảng 3.9. Kết quả so sánh thuật toán Bayes .............................................................68 Bảng 3.10. Dữ liệu mẫu cần dự báo ..........................................................................70 Bảng 3.11. Kết quả so sánh giải thuật Bayes và C4.5...............................................71 vii DANH SÁCH CÁC HÌNH VẼ Hình 1.1. Bài toán phân lớp dữ liệu ..........................................................................04 Hình 1.2. quá trình phân lớp dữ liệu – Bƣớc xây dựng mô hình phân lớp ...............06 Hình 1.3. Quá trình phân lớp dữ liệu – Phân lớp dữ liệu mới ..................................07 Hình 1.4. Ƣớc lƣợng độ chính xác của mô hình phân lớp với PP holdout ...............10 Hình 1.5. Ví dụ về cây quyết định ............................................................................11 Hình 2.1. Mã giả giải thuật C4.5 ...............................................................................21 Hình 2.2. Ví dụ về Cây quyết định hoàn chỉnh .........................................................29 Hình 3.1. Giao diện đăng ký thông tin tham gia khảo sát .........................................41 Hình 3.2. Giao diện nhóm ngƣời thực tế ...................................................................42 Hình 3.3. Giao diện nhóm ngƣời thích nghiên cứu ...................................................42 Hình 3.4. Giao diện nhóm ngƣời có tính xã hội........................................................43 Hình 3.5. Giao diện ngƣời dám nghĩ dám làm ..........................................................43 Hình 3.6. Giao diện ngƣời công chức – văn phòng ..................................................44 Hình 3.7. Giao diện kết quả đánh giá khả năng và sở thích ......................................44 Hình 3.8. Giao diện khảo sát điểm ............................................................................45 Hình 3.9. Giao diện Weka .........................................................................................49 Hình 3.10. Giao diện Preprocess ...............................................................................49 Hình 3.11. Giao diện chọn file dữ liệu ......................................................................50 Hình 3.12. Giao diện Classify 1 ................................................................................50 Hình 3.13. Giao diện chọn giải thuật ........................................................................51 Hình 3.14. Giao diện Classify 2 ................................................................................51 Hình 3.15. Kết quả Classifer Output .........................................................................52 Hình 3.16. Cây quyết định sử dụng giải thuật C4.5 trong Weka .............................. 53 Hình 3.17. Mô hình cấu trúc hệ thống ......................................................................58 Hình 3.18. Giao diện đăng ký thông tin tham gia tƣ vấn ..........................................62 Hình 3.19. Giao diện lựa chọn khả năng và sở thích ................................................63 Hình 3.20. Giao diện kết quả đánh giá khả năng và sở thích ....................................64 Hình 3.21. Giao diện nhập điểm môn học để đƣa ra dự đoán ..................................65 Hình 3.22. Chọn dữ liệu dự đoán ..............................................................................67 Hình 3.23. Chuyển sang Plain text ............................................................................67 Hình 3.24. Kết quả dự đoán trên weka......................................................................68 Hình 3.25. Kết quả khi chạy giải thuật Naïve Bayes trên Weka .............................. 69 viii LỜI MỞ ĐẦU 1. Tính cấp thiết của đề tài Trong những thập niên gần đây, công nghệ thông tin phát triển mạnh mẽ và việc ứng dụng công nghệ thông tin trong nhiều lĩnh vực đời sống, kinh tế xã hội đã làm lƣợng dữ liệu đƣợc thu thập và lƣu trữ ở các hệ thống thông tin tăng lên một cách nhanh chóng. Trƣớc tình hình đó việc khai thác và lọc những dữ liệu có ích từ dữ liệu khổng lồ đó là việc cần thiết, đóng vai trò quyết định thành công trong mọi hoạt động. Các dữ liệu chắt lọc sẽ giúp cải thiện hoạt động trong hiện tại, đƣa ra những nhận định, giải pháp sẽ giúp nâng cao chất lƣợng tốt hơn. Với những lý do đó nhu cầu phát triển các kỹ thuật thu thập, lƣu trữ, phân tích dữ liệu… đƣợc đặt ra và nó đòi hỏi phải xử lý thông minh và hiệu quả hơn. Từ đó đã làm phát triển kĩ thuật mới và với kĩ thuật này cho phép chúng ta khai thác tri thức hữu dụng hơn Chúng ta có thể thấy rằng hầu hết học sinh sau khi hoàn tất chƣơng trình lớp 12 đều lựa chọn cho mình những trƣờng Đại học, Cao đẳng….Thông qua việc chọn trƣờng, chọn ngành nghề sẽ giúp các em có đƣợc kiến thức,kỹ năng để đáp ứng nhu cầu trong xã hội.Việc chọn đúng ngành nghề giúp các em lựa chọn đƣợc hƣớng đi phù hợp với khả năng của bản thân và tránh khỏi những lựa chọn vội vàng. Do rất nhiều yếu tố khách quan, chủ quan khác và đa phân các em ở các tỉnh thành, việc tiếp cận các thông tin về chọn ngành nghề cũng hạn chế và thiếu thiếu thông tin để lựa chọn và định hƣớng cho mình. Việc chọn đúng ngành học trong bối cảnh kinh tế ,xã hội hiện nay nhằm tránh việc có nhiều cá nhân lựa chọn sai nghề sẽ dẫn tới giảm sút chất lƣợng đào tạo,gây lãng phí cho công tác đào tạo và đào tạo lại. Học tập là một quá trình dài và tốn nhiều thời gian công sức cũng nhƣ tiền bạc của cá nhân vì vậy việc định hƣớng chọn đúng ngành nghề sẽ giúp cho các em tránh khỏi những vấn đề trên.Vì vậy việc tƣ vấn chọn ngành nghề phù hợp với học sinh THPT là điều cần thiết. 1 Với lý do trên, tôi chọn đề tài “Phân lớp dữ liệu sinh viên để tƣ vấn học sinh lựa chọn ngành tại Trung tâm E-learning”. Đề tài thực hiện việc khai phá dữ liệu của sinh viên trong việc lựa chọn ngành học tại Trung tâm Elearning – Trƣờng Đại học Mở Hà Nội để dự đoán ngành học cho học sinh THPT. 2. Tổng quan nghiên cứu Trong quá trình hoạt động, con ngƣời tạo ra nhiều dữ liệu nghiệp vụ. Các tập dữ liệu đƣợc tích lũy có kích thƣớc càng lớn, và có thể chứa nhiều thông tin ẩn dạng những quy luật chƣa đƣợc khám phá. Chính vì vậy một nhu cầu đặt ra là cần tìm cách trích rút từ tập dữ liệu đó các luật về phân lớp dữ liệu hay dự đoán những xu hƣớng dữ liệu tƣơng lai. Những quy tắc nghiệp vụ thông minh đƣợc tạo ra sẽ phục vụ đắc lực cho các hoạt động thực tiễn, cũng nhƣ phục vụ đắc lực cho quá trình nghiên cứu khoa học. Công nghệ phân lớp và dự đoán dữ liệu ra đời để đáp ứng mong muốn đó. Công nghệ phân lớp dữ liệu đã, đang và sẽ phát triển mạnh mẽ trƣớc những khao khát tri thức của con ngƣời. Trong những năm qua, phân lớp dữ liệu đã thu hút sự quan tâm của các nhà nghiên cứu trong nhiều lĩnh vực khác nhau. Công nghệ này cũng ứng dụng trong nhiều lĩnh vực thực tế nhƣ: thƣơng mại, nhà băng, maketing, nghiên cứu thị trƣờng, bảo hiểm, y tế, giáo dục v.v. Nhiều kỹ thuật phân lớp đã đƣợc đề xuất nhƣ: Phân lớp cây quyết định (Decision Tree Classification), phân lớp Bayesian (Bayesian Classifier), phân lớp K- hàng xóm gần nhất (K-Nearest Neighbor Classifier), mạng Nơron, phân tích thống kê. Trong các kỹ thuật đó, cây quyết định đƣợc coi là công cụ mạnh, phổ biến và đặc biệt thích hợp cho data mining. Trong các mô hình phân lớp, giải thuật phân lớp là nhân tố chủ đạo. Do vậy cần xây dựng những giải thuật có độ chính xác cao, thực thi nhanh đi kèm với khả năng mở rộng đƣợc để có thao tác với những tập dữ liệu ngày càng lớn. 3. Mục đích nghiên cứu Tìm hiểu các kỹ thuật phân lớp dữ liệu, sử dụng thuật toán C4.5 và Naïve Bayes để phân lớp dữ liệu sinh viên nhằm đƣa ra dự đoán lựa chọn ngành cho học sinh. 2 Xây dựng ứng dụng hỗ trợ học sinh lựa chọn ngành học 4. Đối tƣợng và phạm vi nghiên cứu Đối tƣợng nghiên cứu: Các sinh viên đã và đang học trong Trung tâm Elearning – Trƣờng Đại học Mở Hà Nội. Phạm vi nghiên cứu: + Các phƣơng pháp phân lớp trong khai phá dữ liệu + Dữ liệu thực tại dựa vào kết quả khảo sát thực tế của sinh viên trong Trung tâm Elearning + Giới hạn thử nghiệm phân lớp theo một số đặc trƣng đầu vào đƣợc cho là cơ bản nhất , sau đó có thể mở rộng thêm các đặc trƣng cũng nhƣ các bản ghi khác + Trong quá trình triển khai, tôi tính một số phép tính tiêu biểu sau đó ứng dụng để chạy thực nghiệm. 5. Phƣơng pháp nghiên cứu + Tìm hiểu và lựa chọn phƣơng pháp KPDL thích hợp + Khảo sát, thu thập, phân tích, thiết kế cơ sở dữ liệu + Chọn công cụ tiên tiến xử lý + Triển khai xây dựng, mô phỏng, so sánh và đánh giá 3 CHƢƠNG 1. PHƢƠNG PHÁP PHÂN LỚP DỮ LIỆU 1.1. Khái quát về phân lớp dữ liệu 1.1.1. Phân lớp dữ liệu Một trong các nhiệm vụ chính của khai phá dữ liệu là giải quyết bài toán phân lớp. Đầu vào của bài toán phân lớp là một tập các mẫu học đã đƣợc phân lớp trƣớc, mỗi mẫu đƣợc mô tả bằng một số thuộc tính. Các thuộc tính dùng để mô tả một mẫu gồm hai loại là thuộc tính liên tục và thuộc tính rời rạc. Trong số các thuộc tính rời rạc có một thuộc tính đặc biệt là phân lớp, mà các giá trị của nó đƣợc gọi là nhãn lớp. Thuộc tính liên tục sẽ nhận các giá trị có thứ tự, ngƣợc lại thuộc tính rời rạc sẽ nhận các giá trị không có thứ tự. Ngoài ra, các thuộc tính có thể nhận giá trị không xác định (chẳng hạn, vì những lý do khách quan ta không thể biết đƣợc giá trị của nó). Chú ý rằng nhãn lớp của tất cả các mẫu không đƣợc phép nhận giá trị không xác định. Nhiệm vụ của quá trình phân lớp là thiết lập đƣợc ánh xạ giữa giá trị của các thuộc tính với các nhãn lớp. Mô hình biểu diễn quan hệ nói trên sẽ đƣợc dùng để xác định nhãn lớp cho các quan sát mới không nằm trong tập mẫu ban đầu. Hình 1.1: Bài toán phân lớp dữ liệu Ngày nay, phân lớp dữ liệu (Classification) là một trong những hƣớng nghiên cứu chính của khai phá dữ liệu. Thực tế đặt ra nhu cầu là từ một cơ sở dữ liệu với nhiều thông tin ẩn con ngƣời có thể trích rút ra các quyết định nghiệp vụ thông minh. Phân lớp và dự đoán là hai dạng của phân tích dữ liệu nhằm trích rút ra 4 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 tƣơng lai. Phân lớp dự đoán giá trị của những nhãn xác định (Categorical Label) hay những giá trị rời rạc (Discrete Value), có nghĩa là phân lớp thao tác với những đối tƣợng dữ liệu mà có bộ dữ liệu 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. Ví dụ mô hình dự báo thời tiết có thể cho biết thời tiết ngày mai là mưa, hay nắng dựa vào những thông số về độ ẩm, sức gió, nhiệt độ v.v của ngày hôm nay và các ngày trước đó. Hay nhờ các luật của xu hướng mua hàng của khách hàng trong siêu thị, các nhân viên kinh doanh có thể đưa ra những quyết sách đúng đắn về lượng hàng hóa cũng như các chủng loại bày bán v.v. Một mô hình dự đoán có dự đoán được lượng tiền tiêu dùng của khách hàng tiềm năng dựa trên những thông tin về thu nhập và nghề nghiệp của khách hàng. Trong những năm qua, phân lớp dữ liệu đã thu hút sự quan tâm của các nhà nghiên cứu trong nhiều lĩnh vực khác nhau nhƣ học máy (Machine Learning), hệ chuyên gia (Expert System), thống kê (Statistics) v.v. Công nghệ này cũng đƣợc ứng dụng trong nhiều lĩnh vực khác nhau nhƣ: Thƣơng mại, maketing, nhà băng, nghiên cứu thị trƣờng, bảo hiểm, y tế, giáo dục v.v. Phần lớn các giải thuật ra đời đều sử dụng cơ chế dữ liệu cƣ trú trong bộ nhớ (Memory Resident), thƣờng thao tác với lƣợng dữ liệu nhỏ. Một số giải thuật ra đời sau này đã sử dụng kỹ thuật cƣ trú trên đĩa cải thiện đáng kể khả năng mở rộng của giải thuật với những tập dữ liệu lớn lên tới hàng tỷ bản ghi. Quá trình phân lớp dữ liệu gồm hai bƣớc [9]: - Bước thứ nhất (learning) Quá trình học nhằm xây dựng một mô hình mô tả một tập các lớp dữ liệu hay các khái niệm định trƣớc. Đầu vào của quá trình này là một tập dữ liệu có cấu trúc đƣợc mô tả bằng các thuộc tính và đƣợc tạo ra từ tập các bộ giá trị của các thuộc tính đó. Mỗi bộ giá trị đƣợc gọi chung là một phần tử dữ liệu (Data Tuple), có thể là các mẫu (Sample), ví dụ (Example), đối tượng (Objiect), bản ghi (Record) hay trường hợp (Case). Luận văn sử dụng các thuật ngữ này với nghĩa tƣơng đƣơng. Trong tập dữ liệu này, mỗi phần tử dữ liệu đƣợc giả sử thuộc về một lớp định trƣớc, lớp ở đây là giá trị của một thuộc tính đƣợc chọn làm thuộc tính gán nhãn lớp hay 5 thuộc tính phân lớp (Class Lable Attribute). Đầu ra của bƣớc này thƣờng là các quy tắc phân lớp dƣới dạng luận if – then, cây quyết định, công thức logic hay mạng nơron. Quá trình này đƣợc mô tả nhƣ trong Hình 1.2 Giải thuật phân lớp Tập dữ liệu đào tạo Tuoi 3030+ 30+ 50+ 55+ 50+ 3055+ Ngoại ngữ K K G G K G G K QD Yes Yes Yes No No No Yes No Mô hình (phân lớp) IF Tuoi = 55+ AND Ngoaingu = K THEN QD = No IF Tuoi = 50+ AND Ngoaingu = G THEN QD = Yes Hình 1.2: Quá trình phân lớp dữ liệu – Bƣớc xây dựng mô hình phân lớp Hay nói cách khác, 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át đị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. - Bước thứ hai Bƣớc thứ hai dùng mô hình đã xây dựng ở bƣớc trƣớc để phân lớp dữ liệu mới. Trƣớc tiên độ chính xác mang tính chất dự đoán của mô hình phân lớp vừa tạo ra đƣợc ƣớc lƣợng. Holdout là một kỹ thuật đơn giản để ƣớc lƣợng độ chính xác đó. Kỹ thuật này sử dụng một tập dữ liệu kiểm tra với các mẫu đã đƣợc gán nhãn lớp. Các mẫu này đƣợc chọn ngẫu nhiên và độc lập với các mẫu trong tập dữ liệu đào tạo. Độ chính xác của mô hình trên tập dữ liệu kiểm tra đã đƣa là tỉ lệ phần trăm các mẫu trong tập dữ liệu kiểm tra đƣợc mô hình phân lớp đúng (so với thực tế). Nếu độ chính xác của mô hình đƣợc ƣớc lƣợng dựa trên tập dữ liệu đào tạo thì kết quả thu 6 đƣợc là rất khả quan vì mô hình luôn có xu hƣớng “quá vừa” dữ liệu. Quá vừa dữ liệu là hiện tƣợng kết quả phân lớp trùng khít với dữ liệu thực tế vì quá trình xây dựng mô hình dữ phân lớp từ tập dữ liệu đào tạo có thể đã kết hợp những đặc điểm riêng biệt của tập dữ liệu đó. Do vậy cần sử dụng một tập dữ liệu kiểm tra độc lập với tập dữ liệu đào tạo. Nếu độ chính xác của mô hình là chấp nhận đƣợc, thì mô hình đƣợc sử dụng để phân lớp những dữ liệu tƣơng lai, hoặc những dữ liệu mà giá trị của thuộc tính phân lớp là chƣa biết. Bộ phân lớp (Mô hình) Tập dữ liệu kiểm tra Tuoi 3030+ 30+ 50+ 55+ Ngoại ngữ K K G G K QD Yes Yes Yes No No QD Yes Yes Yes No No Hình 1.3: Quá trình phân lớp dữ liệu – Phân lớp dữ liệu mới 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ác 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. Việc học trong mô hình phân lớp là học có giám sát tức là: tập dữ liệu huấn luyện (quan sát, thẩm định v.v.) đi đôi với những nhãn chỉ định lớp quan sát, những dữ liệu mới đƣợc phân lớp dựa trên tập huấn luyện. Ngƣợc lại với hình thức học đƣợc giám sát là hình thức học không đƣợc giám sát lúc đó nhãn lớp của tập dữ liệu huấn luyện là không đƣợc biết đến. 7 Trong mô hình phân lớp, giải thuật phân lớp dữ vai trò trung tâm, quyết định tới sự thành công của mô hình phân lớp. Do vậy, chìa khóa của vấn đề phân lớp dữ liệu là tìm đƣợc một giải thuật phân lớp nhanh, hiệu quả, có độ chính xác cao và có khả năng mở rộng đƣợc; trong đó, khả năng mở rộng của giải thuật đƣợc đặc biệt chú trọng và phát triển [9]. Có thể liệt kê ra đây các kỹ thuật phân lớp đã đƣợc sử dụng trong những năm qua : - Phân lớp cây quyết định (Decision Tree Classification) - Bộ phân lớp Bayesian (Bayesian Classifier) - Mô hình phân lớp K-hàng xóm gần nhất (K-Nearest Neighbor Classifier) Mạng nơron Phân tích thống kê - Các giải thuật di truyền Phương pháp tập thô (Rough Set Approach) 1.1.2. Các vấn đề liên quan đến phân lớp dữ liệu 1.1.2.1. Chuẩn bị dữ liệu cho việc phân lớp Việc tiền xử lý dữ liệu cho quá trình phân lớp là một việc làm không thể thiếu và có vai trò quan trọng quyết định tới việc có áp dụng đƣợc mô hình phân lớp hay không. Quá trình tiền xử lý dữ liệu sẽ giúp cải thiện độ chính xác, tính hiệu quả và khả năng mở rộng đƣợc của mô hình phân lớp. Quá trình tiền xử lý dữ liệu gồm các công việc sau: - Làm sạch dữ liệu Làm sạch dữ liệu liên quan đến việc xử lý lỗi (Noise) và giá trị thiếu (Mising Value) trong tập dữ liệu ban đầu. Noise là các lỗi ngẫu nhiên hay các giá trị không hợp lệ của các biến trong tập dữ liệu. Để xử lý với tập lỗi này có thể dùng kỹ thuật làm trơn. Missing value là những ô không có giá trị của các thuộc tính. Giá trị lỗi có thể do lỗi chủ quan trong quá trình nhập liệu, hoặc trong trƣờng hợp cụ thể giá trị của các thuộc tính đó không có, hay không quan trọng. Kỹ thuật xử lý ở đây có thể thay giá trị thiếu bằng giá trị phổ biến nhất của thuộc tính đó hoặc bằng giá trị có thể xảy ra nhất dựa trên thống kê. Mặc dù phần lớn giải thuật phân lớp đều có cơ chế xử lý với những giá trị thiếu và lỗi trong tập dữ liệu, nhƣng bƣớc tiền xử lý này có thể làm giảm sự hỗn độn trong quá trình học (xây dựng mô hình phân lớp). 8 - Phân tích sự cần thiết của dữ liệu Có rất nhiều thuộc tính trong tập dữ liệu có thể hoàn toàn không cần thiết hay liên quan đến một bài toán phân lớp cụ thể. Ví dụ dữ liệu về ngày trong tuần hoàn toàn không cần thiết đối với ứng dụng phân tích độ rủi ro của các khoản tiền cho vay của ngân hàng, nên thuộc tính này là dƣ thừa. Phân tích sự cần thiết của dữ liệu nhằm mục đích loại bỏ những thuộc tính không cần thiết, dƣ thừa khỏi quá trình học vì những thuộc tính đó sẽ làm chậm, phức tạp và gây ra sự hiểu sai trong quá trình học dẫn tới một mô hình phân lớp không dùng đƣợc. - Chuyển đổi dữ liệu Việc khái quát hóa dữ liệu lên mức khái niệm cao hơn đôi khi là cần thiết trong quá trình tiền xử lý. Việc này đặc biệt hữu ích với những thuộc tính liên tục (Continuous Attribute or Numeric Attribute). Ví dụ các giá trị số của thuộc tính Tuoi của viên chức có thể khái quát hóa thành các dãy giá trị rời rạc: 30-, 30+, 50+, 55+. Tƣơng tự, với những thuộc tính rời rạc (Categorical Attribute) nhƣ địa chỉ phố có thể đƣợc khái quát hóa lên thành phố. Việc khái quát hóa làm cô đọng dữ liệu học nguyên thủy, vì vậy các thao tác vào/ra liên quan đến quá trình học sẽ giảm. 1.1.2.2. So sánh các mô hình phân lớp Trong từng ứng dụng cụ thể cần lựa chọn mô hình phân lớp phù hợp. Việc lựa chọn đó căn cứ vào sự so sánh các mô hình phân lớp khác nhau, dựa trên các tiêu chuẩn sau:  Độ chính xác dự đoán (Predictive Accuracy): Độ chính xác là khả năng của mô hình để dự đoán chính xác nhãn lớp của dữ liệu mới hay dữ liệu chƣa biết.  Tốc độ (Speed): Tốc độ là chi phí tính toán liên quan đến quá trình tạo ra và sử dụng mô hình.  Sức mạnh (Robustness): Sức mạnh là khả năng mô hình tạo ra những dự đoán đúng từ những dữ liệu noise hay dữ liệu với những giá trị thiếu.  Khả năng mở rộng (Scalability): là khả năng thực thi hiệu quả trên lƣợng lớn dữ liệu của mô hình đã học.  Tính hiểu được (Interpretability): Tính hiểu đƣợc là mức độ hiểu và hiểu rõ những kết quả sinh ra bởi mô hình đã học.  Tính đơn giản (Simplicity): Tính đơn giản liên quan đến kích thƣớc của cây quyết định hay độ cô đọng của các luật. 9 Trong các tiêu chuẩn trên, khả năng mở rộng của mô hình phân lớp đƣợc nhấn mạnh và chú trọng phát triển, đặc biệt với cây quyết định [9]. 1.1.3. Một số phương pháp đánh giá độ chính xác mô hình phân lớp Ƣớc lƣợng độ chính xác của bộ phân lớp là quan trọng ở chỗ nó cho phép dự đoán đƣợc độ chính xác của các kết quả phân lớp những dữ liệu tƣơng lai. Độ chính xác còn giúp so sánh các mô hình phân lớp khác nhau. Dƣới đây là hai phƣơng pháp đánh giá phổ biến là Holdout và K-Fold Cross-Validation. Cả hai phƣơng pháp này đều dựa trên các phân hoạch ngẫu nhiên tập dữ liệu ban đầu. - Phương pháp Holdout Dữ liệu đƣa ra đƣợc phân chia ngẫu nhiên thành 2 phần là: tập dữ liệu đào tạo và tập dữ liệu kiểm tra. Thông thƣờng 2/3 dữ liệu cấp cho dữ liệu đào tạo, phần còn lại cho tập dữ liệu kiểm tra [9]. Lấy từ bộ Tập dữ liệu đào tạo phân lớp Dữ liệu Ƣớc lƣợng độ chính xác Tập dữ liệu kiểm tra Hình 1.4: Ƣớc lƣợng độ chính xác của mô hình phân lớp với phƣơng pháp holdout - Phương pháp K-Fold Cross-Validation Tập dữ liệu ban đầu đƣợc chia ngẫu nhiên thành k tập con (Fold) có kích thƣớc xấp xỉ nhau S1,S2,…,Sk. Quá trình phân lớp và test đƣợc thực hiện k lần. Tại lần lặp thứ i, Si là tập dữ liệu kiểm tra, các tập còn lại hợp thành tập dữ liệu đào tạo. Có nghĩa là đầu tiên việc phân lớp đƣợc thực hiện trên các tập S2, S3,…Sk sau đó test trên tập S1, tiếp tục quá trình phân lớp đƣợc thực hiện trên tập S2,S3,S4,…,Sk sau đó test trên tập S2 và cứ tiếp tục. Độ chính xác là toàn bộ số phân lớp đúng từ k lần lặp chia cho tổng số mẫu của tập dữ liệu ban đầu. 10