Luận văn Thạc sĩ Công nghệ thông tin: Hệ tư vấn cho học sinh chọn tổ hợp môn thi tốt nghiệp Trung học phổ thông Quốc gia

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:79

Thêm vào BST

Báo xấu

30
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề tài luận văn thực hiện xây dựng một công cụ hỗ trợ cho học sinh trong kỳ thi tốt nghiệp THPT Quốc gia, qua đó các phương pháp xử lý và phân tích dữ liệu được áp dụng nhằm tạo ra một mô hình, kỹ thuật xử lý dữ liệu của học sinh. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Công nghệ thông tin: Hệ tư vấn cho học sinh chọn tổ hợp môn thi tốt nghiệp Trung học phổ thông Quốc gia

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÀ RỊA - VŨNG TÀU --------  -------- LÂM THỊ ANH HOÀNG HỆ TƯ VẤN CHO HỌC SINH CHỌN TỔ HỢP MÔN THI TỐT NGHIỆP TRUNG HỌC PHỔ THÔNG QUỐC GIA LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Bà Rịa – Vũng Tàu, tháng 04/2021
BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÀ RỊA - VŨNG TÀU --------  -------- LÂM THỊ ANH HOÀNG HỆ TƯ VẤN CHO HỌC SINH CHỌN TỔ HỢP MÔN THI TỐT NGHIỆP TRUNG HỌC PHỔ THÔNG QUỐC GIA Chuyên ngành: Công nghệ thông tin Mã ngành: 8480201 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. VĂN THẾ THÀNH Bà Rịa – Vũng Tàu, tháng 04/2021
Trang 1 LỜI CẢM ƠN Trong suốt quá trình nghiên cứu và thực hiện đề tài luận văn “Hệ tư vấn cho học sinh chọn tổ hợp môn thi tốt nghiệp THPT Quốc gia” tôi đã nhận được sự giúp đỡ rất nhiều của Quý Thầy Cô ở Viện Đào Tạo Quốc Tế Sau Đại Học của Trường Đại Học Bà Rịa Vũng Tàu, của anh chị đồng nghiệp, của các bạn cùng lớp và đặc biệt là sự hướng dẫn tận tình của Thầy hướng dẫn, đó là TS.Văn Thế Thành. Qua đây, tôi xin cám ơn các trường THPT trên địa bàn Thành phố Vũng Tàu đã tạo điều kiện, cung cấp số liệu của nhà trường để tôi hoàn thành luận văn tốt hơn. Trong luận văn, chắc hẳn không thể tránh khỏi những hạn chế và thiếu sót. Tôi rất mong muốn sẽ nhận được nhiều sự góp ý quý báu của Quý Thầy Cô trong hội đồng, Quý bạn đọc để tôi có thể hoàn thiện luận văn tốt hơn nữa đồng thời có thể áp dụng vào thực tiễn, ít nhiều giúp Quý Thầy Cô tư vấn học sinh THPT chọn được tổ hợp môn thi tốt nghiệp THPT. Một lần nữa, tôi xin chân thành cảm ơn Quý Thầy Cô, đồng nghiệp, bạn bè và đặc biệt là Thầy TS.Văn Thế Thành đã hướng dẫn tôi hoàn thành đề tài luận văn này.
Trang 2 LỜI CAM ĐOAN Tôi xin cam đoan đề tài luận văn “Hệ tư vấn cho học sinh chọn tổ hợp môn thi tốt nghiệp THPT Quốc gia” là công trình nghiên cứu độc lập của tôi dưới sự hướng dẫn của giáo viên hướng dẫn. Các số liệu, nêu trong luận văn được tôi thu thập từ trường THPT Trần Nguyên Hãn trên địa bàn Thành phố Vũng Tàu, kết quả của luận văn chưa được ai công bố trên bất kỳ công trình nghiên cứu nào. Tôi xin hoàn toàn chịu trách nhiệm trước hội đồng, khoa, viện sau đại học về sự cam đoan này.
Trang 3 MỤC LỤC CHƯƠNG 1. TỔNG QUAN VỀ HỆ TƯ VẤN CHO HỌC SINH CHỌN MÔN THI ..................................................................................................... 8 1.1. TỔNG QUAN VỀ NHU CẦU HỆ TƯ VẤN CHỌN MÔN THI ............ 8 1.1.1. Sự cần thiết của hệ tư vấn............................................................... 8 1.1.2. Các nghiên cứu liên quan ............................................................... 9 1.1.3. Cơ sở lý thuyết liên quan đến luận văn ......................................... 12 1.1.4. Cấu trúc hệ thống ......................................................................... 19 1.1.5. Sự đóng góp của hệ thống ............................................................ 21 1.2. ĐỐI TƯỢNG VÀ PHƯƠNG PHÁP NGHIÊN CỨU ........................... 22 1.2.1. Đối tượng nghiên cứu ................................................................... 22 1.2.2. Phương pháp nghiên cứu .............................................................. 22 1.3. LĨNH VỰC NGHIÊN CỨU ................................................................ 23 1.4. NỘI DUNG NGHIÊN CỨU................................................................ 24 1.5. QUÁ TRÌNH THỰC HIỆN ................................................................. 24 1.5.1. Các bước thực hiện ...................................................................... 24 1.5.2. Các kỹ thuật cần nghiên cứu......................................................... 25 1.5.3. Các công cụ áp dụng .................................................................... 26 1.5.4. Nội dung các chương trong luận văn ............................................ 27 1.6. TỔNG KẾT CHƯƠNG....................................................................... 28 CHƯƠNG 2. HỆ TƯ VẤN CHỌN MÔN THI TỔ HỢP CHO HỌC SINH ..................................................................................................................... 29 2.1. TỔNG QUAN .................................................................................... 29 2.2. PHÂN CỤM DỮ LIỆU DỰA TRÊN K-MEANS ................................ 30 2.2.1. Thuật toán K-Means ..................................................................... 30 2.2.2. Ví dụ thực nghiệm cho thuật toán K-means .................................. 32 2.3. MẠNG SOM ...................................................................................... 39
Trang 4 2.3.1. Cấu trúc mạng SOM ..................................................................... 39 2.3.2. Một ví dụ thực nghiệm cho việc huấn luyện mạng SOM ............... 41 2.3.3. Thuật toán chọn cụm chiến thắng ................................................. 43 2.3.4. Ví dụ thực nghiệm cho việc chọn cụm chiến thắng........................ 44 2.4. PHƯƠNG PHÁP PHÂN LỚP K-NN .................................................. 44 2.4.1. Thuật toán phân lớp k-NN ............................................................ 44 2.4.2. Ví dụ thực nghiệm cho thuật toán k-NN ........................................ 45 2.5. HỆ TƯ VẤN CHO HỌC SINH THI TỐT NGHIỆP THPT .................. 47 2.5.1. Mô hình hệ thống.......................................................................... 47 2.5.2. Quá trình huấn luyện mạng SOM ................................................. 48 2.5.3. Quá trình phân lớp, tư vấn ........................................................... 49 2.6. TỔNG KẾT CHƯƠNG....................................................................... 49 CHƯƠNG 3. THỰC NGHIỆM ................................................................. 51 3.1. GIỚI THIỆU ....................................................................................... 51 3.2. MÔ HÌNH THỰC NGHIỆM ............................................................... 52 3.3. XÂY DỰNG HỆ THỐNG .................................................................. 53 3.3.1. Thiết kế sơ đồ lớp ......................................................................... 53 3.3.2. Cài đặt cấu trúc lớp...................................................................... 54 3.4. MÔI TRƯỜNG THỰC NGHIỆM ....................................................... 57 3.4.1. Ngôn ngữ lập trình ....................................................................... 57 3.4.2. Môi trường thực nghiệm ............................................................... 58 3.4.3. Dữ liệu thực nghiệm ..................................................................... 58 3.4.4. Ứng dụng thực nghiệm trên Server ............................................... 58 3.4.5. Ứng dụng thực nghiệm trên Client................................................ 60 3.4.6. Kết quả thực nghiệm trên bộ dữ liệu có 1073 mẫu ........................ 60 3.4.7. Kết quả thực nghiệm 30% trên 5231 mẫu dữ liệu ......................... 63 3.5. TỔNG KẾT CHƯƠNG....................................................................... 65
Trang 5 KẾT LUẬN ................................................................................................. 66 TÀI LIỆU THAM KHẢO.......................................................................... 67 PHỤ LỤC.................................................................................................... 69 CÀI ĐẶT CÁC HÀM CHÍNH CỦA HỆ THỐNG ..................................... 69
Trang 6 BẢNG VIẾT TẮT GD&ĐT Giáo dục và Đào tạo HS Học sinh PH Phụ huynh THPT Trung học phổ thông
Trang 7 DANH MỤC CÁC HÌNH ẢNH Số hiệu Tên hình vẽ Trang 1.1. Mô hình học có giám sát 1.2. Mô hình học không giám sát 1.3. Mô hình gom cụm 1.4. Mô hình phân lớp 1.5. Mô hình thuật toán k-NN 1.6. Mô hình tổng quát hệ thống tư vấn 2.1. Mô hình mạng SOM 2.2. Mô hình hệ thống tư vấn học sinh 2.3. Lưu đồ quá trình huấn luyện mạng SOM 2.4. Lưu đồ dự báo và tư vấn học sinh 3.1. Mô hình thực nghiệm hệ thống dự báo 3.2. Sơ đồ lớp của hệ thống 3.3. Phân cụm dữ liệu học sinh (1075 mẫu) trên máy server 3.4. Một mô tả dữ liệu cho cụm thứ nhất 3.5. Một cụm Root dùng để quản lý các cụm dữ liệu khác 3.6. Quá trình dự báo chọn môn thi cho học sinh 3.7. Mô tả độ chính xác về học lực của học sinh 3.8. Mô tả độ chính xác về dự báo danh hiệu cho học sinh 3.9. Mô tả độ chính xác dự báo tổ hợp môn thi cho học sinh 3.10. Thời gian dự báo trung bình cho mỗi mẫu dữ liệu 3.11. Mô tả độ chính xác về học lực của học sinh 3.12. Mô tả độ chính xác về dự báo danh hiệu cho học sinh 3.13. Mô tả độ chính xác dự báo tổ hợp môn thi cho học sinh 3.14. Thời gian dự báo trung bình cho mỗi mẫu dữ liệu
Trang 8 Chương 1. TỔNG QUAN VỀ HỆ TƯ VẤN CHO HỌC SINH CHỌN MÔN THI 1.1. TỔNG QUAN VỀ NHU CẦU HỆ TƯ VẤN CHỌN MÔN THI 1.1.1. Sự cần thiết của hệ tư vấn Trước năm 2016, Bộ GD&ĐT đã công bố phương án thi tốt nghiệp đối với học sinh THPT gồm ít nhất 4 môn: 3 môn bắt buộc Toán, Ngữ văn, Ngoại ngữ và 1 môn tự chọn trong các môn Vật lý, Hóa học, Sinh học, Lịch sử, Địa lý [1]. Trên cơ sở này, các trường THPT tiến hành cho học sinh đăng ký chọn môn theo năng lực của mình. Vào ngày 28/9/2016 Bộ GD&ĐT công bố phương án thi THPT Quốc gia, đó là học sinh THPT thi 4 bài thi gồm: 3 bài thi bắt buộc Toán, Ngữ văn, Ngoại ngữ và 1 bài thi tự chọn: bài thi Khoa học Tự nhiên hoặc bài thi Khoa học Xã hội. Với bài thi Ngoại ngữ, học sinh có thể chọn thi một trong các thứ tiếng: Anh, Nga, Pháp, Trung, Đức, Nhật. Học sinh có thể dự thi cả 5 bài thi để sử dụng kết quả xét tuyển vào ĐH, CĐ [2]. Với mô hình thi này, bắt đầu năm học 2016 – 2017, các trường THPT gặp rất nhiều khó khăn như nhà trường phải sắp xếp và chia lại lớp cho học sinh lớp 12, phân công lại chuyên môn, xếp lại thời khóa biểu… Tuy nhiên, tất cả việc sắp xếp lại của nhà trường đều dựa trên mong muốn của PH và HS, tức là chỉ dựa trên ý muốn chủ quan. Phương án này mặc dù thỏa mãn được nguyện vọng của PH và HS nhưng có thể chưa phát huy hết năng lực của học sinh vì việc đăng ký chọn môn thi phần lớn dựa vào ý muốn chủ quan hoặc theo ý kiến của số đông hoặc theo nguyện vọng của PH… Việc lựa chọn này không theo sự đánh giá năng lực của bản thân cũng như không dựa trên một phương pháp phân tích có cơ sở khoa học nhất định. Vì vậy, đề tài luận văn xây dựng một hệ thống tư vấn hỗ trợ cho HS và PH chọn lựa tổ hợp môn theo đúng năng lực học tập.
Trang 9 1.1.2. Các nghiên cứu liên quan Đối với hệ thống tư vấn cho học sinh hoặc phân loại học sinh theo năng lực, nhiều nhóm nghiên cứu đã đưa ra các giải pháp khác nhau cho từng bài toán cụ thể nhằm tư vấn cho học sinh, cho nhà trường chọn lựa những định hướng để quyết định trong những trường hợp khác nhau như: sử dụng thuật toán K-means để gom cụm các học sinh theo năng lực (gồm 6 mức năng lực) dựa trên điểm số của các môn học [3], sử dụng kỹ thuật cây quyết định, Bayesian, mạng nơ-ron, kỹ thuật láng giềng, K-MEDIODS để phân lớp và gom cụm học sinh theo các thuộc tính về các mối tương quan giữa học sinh và giáo viên để phân chia học sinh vào các lớp học phù hợp [4], chia nhóm học sinh bằng thuật toán K-means dựa trên điểm trung bình của từng môn theo học kỳ để từ đó đưa ra các tư vấn phù hợp [5], phân loại học sinh dựa trên các thông tin cá nhân và nguyện vọng để từ đó tư vấn nghề nghiệp cho học sinh THPT bằng phương pháp phân cụm, phân cấp kết hợp với K-means [6], phân nhóm học sinh nhằm mở các lớp học phù hợp bằng kỹ thuật bảng đồ tự tổ chức SOM (Self-Organizing Map) và cấu trúc phân cụm phân cấp [7], sử dụng kỹ thuật học sâu kết hợp cây FP-Tree trên tiếp cận Adaboost để phân loại học sinh dựa trên điểm trung bình từng môn học theo học kỳ để từ đó định hướng cho học sinh nâng cao hiệu suất học tập [8], phân tích điểm số và đưa ra phương án học tập phù hợp bằng kỹ thuật phân cụm và phân lớp trên mạng SOM [9], nghiên cứu phương pháp học không giám sát để phân loại học sinh dựa trên kỹ thuật luật kết hợp và phân tích thành phần chính PCA (Principal component analysis) để giảm số chiều dữ liệutừ đó đánh giá hiệu suất học tập của học sinh [10], phân nhóm học sinh dựa trên mức độ học tập theo từng môn học bằng kỹ thuật SOM [11]… Oyelade và cộng sự (2010) đã tiếp cận thuật toán gom cụm K-means để dự báo hiệu suất học tập cho sinh viên. Trong bài báo này, nhóm tác giả đã thực
Trang 10 hiện phân nhóm các học sinh theo 6 mức độ học lực khác nhau (Excellent, Very Good, Good, Very Fair, Fair, Poor) để từ đó định hướng cho học sinh có kế hoạch học tập tiếp theo [3]. Với kết quả này, phương pháp chỉ tiếp cận thuật toán K-means nhằm phân nhóm các học sinh với số nhóm phải được phân hoạch từ trước, do đó nếu dữ liệu tăng trưởng thì việc phân hoạch phải thực hiện lại từ đầu và có thể tạo ra một kết quả khác. Khadir và cộng sự (2015) đã tiếp cận kỹ thuật phân cụm dựa trên bảng đồ tự tổ chức SOM nhằm phân tích hiệu suất học tập của học sinh để từ đó theo dõi định hướng các khóa học kế tiếp [9]. Quá trình phân cụm học sinh của phương pháp này được chọn lựa dựa trên việc gom cụm bộ dữ liệu để từ đó huấn luyện trọng số cho mô hình SOM. Tuy nhiên, việc phân cụm dữ liệu chỉ dựa vào việc gom nhóm các đặc tính tương tự của học sinh, do đó cần phải có một thuật toán gom cụm phù hợp cho dữ liệu tăng trưởng. Z. Fan và cộng sự (2017) sử dụng phương pháp phân cụm K-means để phân nhóm các học sinh dựa trên điểm trung bình của các môn học theo từng học kỳ [5]. Đối với phương pháp của nhóm tác giả này, các tâm cụm khởi tạo cho thuật toán K-means được chọn bằng cách chia theo từng nhóm dữ liệu, từ đó các nhóm học sinh được phân loại. Việc áp dụng thuật toán K-means cho bộ dữ liệu điểm số của học sinh chưa thể bổ sung các phần tử dữ liệu mới, hơn nữa với mỗi phần tử dữ liệu mới này chưa thể phân loại và phân lớp các học sinh. Lee và cộng sự (2019) kết hợp mạng SOM và phương pháp phân cụm phân cấp để thực hiện gom cụm học sinh theo năng lực và phân loại học sinh trên mạng SOM. Theo kết quả thực nghiệm của bài báo cho thấy việc đánh giá và phân loại học sinh có độ chính xác cao và có thể theo dõi học sinh theo dữ liệu của dòng thời gian cho mỗi học sinh [7]. Purbasari và cộng sự (2020) xây dựng một mạng SOM nhằm huấn luyện các trọng số để từ đó phân loại học sinh qua các giá trị mức độ điểm trung bình
Trang 11 theo từng môn học [11]. Trong công trình này, nhóm tác giả đưa ra các nhóm phân loại dựa vào véc-tơ chiến thắng trên mạng SOM, chưa kết hợp các phần tử láng giềng để phân loại học sinh cũng như chưa đưa ra định hướng cho học sinh về việc nâng cao hiệu suất cũng như kế hoạch học tập tiếp theo. Theo các công trình khảo sát trên, việc phân loại học sinh kết hợp giữa phân cụm K-means và mạng SOM là một phương pháp khả thi và là một chủ đề nghiên cứu thời sự. Việc đánh giá và phân loại này giúp cho quá trình phân loại không mang tính chủ quan của con người. Hơn nữa, với mỗi bộ dữ liệu mới của mỗi học sinh, phương pháp này có thể dự báo về năng lực của học sinh, phân nhóm học sinh để từ đó đưa ra những tư vấn phù hợp. Trên cơ sở này, nội dung luận văn thực hiện xây dựng một hệ tư vấn chọn lựa cho học sinh trên cơ sở dữ liệu quá khứ và dữ liệu huấn luyện để phân loại dự báo và tư vấn cho học sinh. Dữ liệu huấn luyện của học sinh được sưu tập theo năng lực điểm số và phân cụm dựa trên phương pháp K-means để từ đó làm đầu vào cho các nhóm phần tử láng giềng của mạng SOM. Trên cơ sở các phân cụm này, mạng SOM được huấn luyện các véc-tơ trọng số dựa trên bộ dữ liệu mẫu bằng cách tinh chỉnh trọng số theo phân lớp của cụm đầu ra. Sau quá trình huấn luyện, mô hình phân loại là các véc-tơ trọng số nhằm phân loại một học sinh đầu vào bất kỳ. Sau khi phân loại dựa trên véc-tơ chiến thắng, các phần tử láng giềng trong mạng SOM được trích xuất để làm cơ sở phân lớp bằng phương pháp láng giềng gần nhất k-NN. Đối với luận văn này, dữ liệu được thống kê từ các nguồn học sinh khác nhau tại các trường THPT khác nhau để từ đó xây dựng mô hình phân loại trên mạng SOM kết hợp với k-NN. Với việc phân loại này, học sinh được hỗ trợ trong việc chọn lựa các tổ hợp môn trong kỳ thi tốt nghiệp THPT Quốc gia. Ngoài ra, hệ thống này là sự kết hợp của việc cải tiến phương pháp K-means và phương pháp phân nhóm đối tượng bán giám sát theo SOM và k-NN.
Trang 12 1.1.3. Cơ sở lý thuyết liên quan đến luận văn 1.1.3.1. Phương pháp học giám sát Học có giám sát (Supervised learning)là một kỹ thuật học máy nhằm tạo ra mô hình dự báo (có thể sử dụng các phương pháp phân lớp, hồi qui) từ bộ dữ liệu huấn luyện (training data) bao gồm các cặp đối tượng đầu vào và nhãn đầu ra mong muốn.Từ đó, mô hình đã huấn luyện được sử dụng đểdự đoán nhãn lớp cho đối tượng đầu vào. Dữ liệu Phân lớp Kết quả huấn luyện Hồi qui dự đoán Hình 1.1. Mô hình học có giám sát Cho một tập hợp biến đầu vào 𝑋 = {𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑁 } và một tập nhãn tương ứng 𝑌 = {𝑦1 , 𝑦2 , 𝑦3 , … , 𝑦𝑁 }, trong đó 𝑥𝑖 , 𝑦𝑖 là các véc-tơ. Các cặp dữ liệu biết trước (𝑥𝑖 , 𝑦𝑖 ) ∈ 𝑋 × 𝑌 được gọi là tập dữ liệu huấn luyện (training data). Trong tập dữ liệu 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 𝑋 sang một phần tử (xấp xỉ) tương ứng của tập 𝑌. 𝑦𝑖 ≈ 𝑓(𝑥𝑖 ), ∀𝑖 = 1, 2, … , 𝑁 Mục đích là xấp xỉ hàm số 𝑓 thật tốt để khi có một dữ liệu 𝑥𝑘 mới, chúng ta có thể dự đoán nhãn tương ứng 𝑦𝑘 = 𝑓(𝑥𝑘 ). Thuật toán học có giám sát được chia thành hai loại chính:  Phân loại (Classification): phân loại dữ liệu là một kỹ thuật dựa trên tập huấn luyện và những giá trị là nhãn của lớp trong một thuộc tính phân lớp và sử dụng nó trong việc phân lớp dữ liệu mới. Kỹ thuật phân lớp được tiến hành 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ộ được gán nhãn thuộc về một lớp được định nghĩa trước, được xác định bởi thuộc tính
Trang 13 nhãn lớp, tập hợp của những bộ được sử dụng trong việc xây dựng mô hình được gọi là tập huấn luyện. Sử dụng mô hình nhằm 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 được gán nhãn. Trước khi sử dụng mô hình người ta thường đánh giá tính chính xác của mô hình, trong đó: nhãn được biết của bộ 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 tập hợp mẫu kiểm tra mà được phân lớp đúng dựa vào mô hình đã xây dựng, tập kiểm tra độc lập với tập được sử dụng để huấn luyện.  Hồi qui (Regression): là một kỹ thuật xác định mối quan hệ giữa hai biến số. Mô hình hồi qui cần đưa ra một dự đoán hoặc ước lượng giá trị của một biến số từ một giá trị của một hay nhiều biến số khác. 1.1.3.2. Phương pháp học không giám sát Học không giám sát (Unsupervised Learning) là một phương pháp của ngành học máy nhằm tìm ra một mô hình phù hợp với các tập dữ liệu ban đầu chưa được gán nhãn, có nghĩa là không có tập dữ liệu đầu ra đúng cho mỗi dữ liệu đầu vào. Trong phương pháp học không giám sát, một mô hình sẽ được huấn luyện để tìm ra cấu trúc hoặc các mối quan hệ giữa các tập dữ liệu đầu vào. Một trong những phương pháp học không giám sát quan trọng nhất là gom cụm (clustering). Phương pháp gom cụm nhằm tạo ra các cụm khác nhau, với mỗi cụm biểu diễn một đặc trưng nào đó của dữ liệu và phân các đầu vào mới vào các cụm theo đặc trưng của cụm đầu vào đó, có nghĩa là các dữ liệu thuộc một cụm sẽ có đặc trưng tương tự nhau. Dữ liệu Các cụm chứa Thuật toán không được các phần tử để gom cụm tương tự nhau gán nhãn Hình 1.2. Mô hình học không giám sát
Trang 14 1.1.3.3. Phương pháp học bán giám sát Học bán giám sát (Semi-Supervised Learning) là bao gồm học có giám sát và học không giám sát, điều đó có nghĩa học với tập dữ liệu huấn luyện đã được gán nhãn và dữ liệu chưa được gán nhãn.Tùy vào từng mục đích cụ thể, học bán giám sát có thể sử dụng thuật toán k-NN để phân lớphoặc phân cụm các đối tượngchưa được gán nhãn, sử dụng thuật toán K-Means để dự đoán kết quả đầu ra cho dữ liệu đã được gắn nhãn. Sau khi đạt được kết quả mong muốn, ta sử dụng thuật toán này cho bộ dữ liệu đã được phân cụm trước đó để gắn nhãn cho các cụm. 1.1.3.4. Gom cụm Gom cụm (Clustering) là mô hình gom cụm dữ liệu không có nhãn sao cho các dữ liệu cùng cụm có các tính chất tương đồng nhau và dữ liệu của hai cụm khác nhau sẽ có tính chất khác nhau. Hay nói cách khác bài toán gom cụm dữ liệu là phương pháp phân chia tập dữ liệu 𝑋 thành các cụm nhỏ dựa trên sự liên quan giữa các bộ dữ liệu trong mỗi nhóm. Để thực hiện gom cụm ta thường sử dụng thuật toán K-means, thuật toán SOM, độ đo tương tự Euclide. Gom cụm trên thuật toán K-Means: Thuật toán K-Means là một phương pháp gom cụm thuộc loại học không giám sát và được ứng dụng nhiều trong các bài toán gom cụm các dữ liệu tương tự. Ý tưởng của thuật toán gom cụm K-Means là phân chia một tập dữ liệu ban đầu thành các cụm khác nhau. Dữ liệu trong mỗi cụm có tính chất tương tự nhau. Trong đó số lượng cụm được cho trước là k. Công việc gom cụm được xây dựng trên quy tắc: các dữ liệu trong cùng một cụm phải có cùng một số đặc trưng nhất định. Hay nói cách khác, các dữ liệu trong cùng một cụm phải có sự liên quan lẫn nhau. Thuật toán gom cụm K-Means: Dữ liệu đầu vào: Một bộ dữ liệu 𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑁 , với mỗi dữ liệu là véc- tơ đặc trưng của đối tượng đầu vào. Số cụm cho trước k cụm.
Trang 15 Dữ liệu đầu ra: Bộ dữ liệu đầu vào được phân thành k cụm Trước khi thực hiện gom cụm ta chuẩn hóa dữ liệu bằng cách chuyển dữ liệu về miền giá trị [0,1]  Bước 1: Chọn k tâm cụm ngẫu nhiên𝑐1, 𝑐2, 𝑐3 , … , 𝑐𝑘  Bước 2: Với mỗi dữ liệu 𝑥𝑖 , xác định cụm của nó. Tìm tâm cụm gần nhất. Ta có thể sử dụng độ đo Euclide để tính khoảng cách giữa 𝑥𝑖 đến các tâm cụm.  Bước 3: Phân phối các mẫu dữ liệu vào k cụm, tính toán lại vị trí của tâm cụm để đảm bảo tâm của cụm nằm ở chính giữa cụm.  Bước 4: Bước 2 và Bước 3 được lặp cho tới khi vị trí của tâm cụm không thay đổi (hội tụ) Hình 1.3. Mô hình gom cụm K-means 1.1.3.5. Phân lớp Phân lớp (Classification) là quá trình phân lớp cho một đối tượng dữ liệu vào một hay nhiều lớp đã cho trước. Quá trình phân lớp là quá trình gắn nhãn cho đối tượng dữ liệu. Quá trình gồm hai bước: (1) Bước học (giai đoạn huấn luyện) là quá trình xây dựng mô hình phân lớp dữ liệu bằng cách phân tích tập dữ liệu huấn luyện đã được gán nhãn; (2) Bước phân lớp là quá trình phân lớp dữ liệu mới dựa trên mô hình đã xây dựng.
Trang 16 Hình 1.4. Mô hình phân lớp Phương pháp phân lớp k-NN k-NN (K-Nearest Neighbors algorithm) dùng để phân lớp các đối tượng đã được gắn nhãn dựa vào khoảng cách gần nhất giữa các đối tượng cần xếp lớp. Mỗi đối tượng được phân lớp dựa vào k láng giềng của nó, ta thường dùng khoảng cách Euclide để đo khoảng cách giữa các đối tượng. Thuật toán k-NN được mô tả như sau:  Bước 1: Xác định k láng giềng gần nhất.  Bước 2: Dùng độ đo Euclide để tính khoảng cách giữa đối tượng cần phân lớp với tất cả các đối tượng trong training data.  Bước 3: Sắp xếp khoảng cách theo thứ tự tăng dần và xác định k láng giềng gần nhất với các đối tượng cần phân lớp.  Bước 4: Lấy tất cả các lớp của k láng giềng gần nhất đã xác định.  Bước 5: Dựa vào phần lớn lớp của láng giềng gần nhất để xác định lớp cho các đối tượng cần phân lớp. Hình 1.5. Mô hình thuật toán k-NN
Trang 17 Trong hình trên, dữ liệu huấn luyện (training data) được mô tả bởi dấu (+) và dấu (-), đối tượng cần được xác định lớp cho nó (Query point) là hình tròn xám. Ta thấy rằng:  Trong trường hợp k láng giềng là 1 thì đối tượng cần được phân lớp sẽ là lớp –  Trong trường hợp k láng giềng là 2 thì đối tượng cần được phân lớp sẽ không xác định vì không lớp nào có số đối tượng nhiều hơn.  Trong trường hợp k láng giềng là 5 thì đối tượng cần được phân lớp sẽ là lớp + 1.1.3.7. Bản đồ tự tổ chức SOM SOM (Self Organizing Map) là một mạng nơ-ron tự tổ chức, thường được thiết kế gồm một tầng đầu vào và một tầng đầu ra với véc-tơ có giá trị trọng số tương ứng với mỗi cụm để từ đó tìm cụm có giá trị nhỏ nhất là cụm chiến thắng. Tính tự tổ chức của SOM được thực hiện bởi nguyên tắc học cạnh tranh, không giám sát nhằm tạo ra ánh xạ của dữ liệu từ không gian nhiều chiều về không gian ít chiều hơn. Điều này có nghĩa là các dữ liệu có đặc trưng tương đồng nhau thì sẽ được đại diện bởi một nơ-ron hoặc các nơ-ron gần nhau. Kết quả là hình thành nên bản đồ đặc trưng của tập dữ liệu đầu vào. Thuật toán SOM được mô tả như sau: Dữ liệu đầu vào: tập 𝑁 véc-tơ đặc trưng của bộ dữ liệu 𝑋 = {𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑁 }. Trong đó, mỗi véc-tơ 𝑥𝑖 có 𝑑 chiều 𝑥𝑖 = {𝑥𝑖1, 𝑥𝑖2 , 𝑥𝑖3 , … , 𝑥𝑖𝑑 } Dữ liệu đầu ra: bộ véc-tơ trọng số 𝑊 = {𝑤1 , 𝑤2 , 𝑤3, … , 𝑤𝑚 }. Trong đó,𝑤𝑖 = {𝑤𝑖1 , 𝑤𝑖2 , 𝑤𝑖3, … , 𝑤𝑖𝑑 }  Bước 1: Khởi tạo véc-tơ trọng số cho mỗi nơ-ron Tương ứng với mỗi véc-tơ 𝑥𝑖 có 𝑑 chiều, khởi tạo một véc-tơ trọng số 𝑤𝑖 = {𝑤𝑖1, 𝑤𝑖2, 𝑤𝑖3 , … , 𝑤𝑖𝑑 }. Tập véc-tơ trọng số của 𝑁 bộ dữ liệu là 𝑊 = {𝑤1, 𝑤2, 𝑤3 , … , 𝑤𝑚 }.
Trang 18  Bước 2: Chọn ngẫu nhiên một véc-tơ 𝑥𝑖 trong tập dữ liệu làm mẫu huấn luyện.  Bước 3: Tìm phần tử nơ-ron chiến thắng Tìm phần tử khớp nhất giữa các véc-tơ trọng số 𝑤𝑖 và véc-tơ đầu vào 𝑥𝑖 . Nơ-ron nào có véc-tơ trọng số 𝑤𝑖 gần với véc-tơ đầu vào 𝑥𝑖 nhất là nơ-ron chiến thắng. Để xác định nơ-ron chiến thắng ta có thể sử dụng khoảng cách Euclide giữa các véc-tơ trọng số 𝑤𝑖 với véc-tơ đầu vào 𝑥𝑖 .  Bước 4: Xây dựng các phần tử lân cận Bước này sẽ xác định các nơ-ron nào thuộc vùng lân cận của nơ-ron chiến thắng. Để xác định vùng lân cận, sử dụng một ngưỡng 𝛿 ∈ (0,1) gọi là bán kính lân cận. Tính khoảng cách Euclide từ tâm là phần tử nơ-ron chiến thắng đến các phần tử nơ-ron lân cận. Những phần tử nằm trong phạm vi bán kính 𝛿 là các phần tử lân cận của cụm chiến thắng.  Bước 5: Hiệu chỉnh trọng số các phần tử lân cận Trọng số của các phần tử lân cận đã được xác định ở bước 4, bao gồm cả phần tử chiến thắng sẽ được hiệu chỉnh để chúng có giá trị gần với giá trị của véc-tơ đầu vào 𝑥𝑖 đang xét.  Bước 6: Lấy bộ dữ liệu 𝑥𝑗 tiếp theo để huấn luyện. Lặp lại bước 2 cho đến khi thuật toán tối ưu. Kết quả thu được là bộ trọng số 𝑊 = {𝑤1, 𝑤2, 𝑤3 , … , 𝑤𝑚 } tốt nhất. Chính nhờ khả năng biểu diễn dữ liệu từ không gian nhiều chiều về không gian ít chiều hơn mà vẫn có thể giữ được mối quan hệ của dữ liệu trong không gian đầu vào nên mạng SOM sẽ biểu diễn được một cách trực quan sự phân bố giữa các bộ trong không gian của tập dữ liệu. Do đó, mạng SOM được ứng dụng nhiều trong các bài toán gom cụm dữ liệu. SOM là phương pháp gom cụm theo hướng tiếp cận mạng nơ-ron nhân tạo và theo thuật toán học ganh đua