Tài liệu Xây dựng hệ hỗ trợ tư vấn tuyển sinh tại trường cao đẳng cộng đồng vĩnh long

ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA NGUYỄN HOÀNG HẢI XÂY DỰNG HỆ HỖ TRỢ TƯ VẤN TUYỂN SINH TẠI TRƯỜNG CAO ĐẲNG CỘNG ĐỒNG VĨNH LONG LUẬN VĂN THẠC SỸ KỸ THUẬT Đà Nẵng, Năm 2017 ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA NGUYỄN HOÀNG HẢI XÂY DỰNG HỆ HỖ TRỢ TƯ VẤN TUYỂN SINH TẠI TRƯỜNG CAO ĐẲNG CỘNG ĐỒNG VĨNH LONG Chuyên ngành: Khoa học máy tính Mã số: 60.48.01.01 LUẬN VĂN THẠC SỸ KỸ THUẬT Người hướng dẫn khoa học: TS. TRƯƠNG NGỌC CHÂU Đà Nẵng, Năm 2017 i LỜI CAM ĐOAN Tôi xin cam đoan đề tài khoa học “Xây dựng hệ hỗ trợ tư vấn tuyển sinh tại Trường Cao đẳng Cộng đồng Vĩnh Long” này là bài nghiên cứu của chính bản thân tôi. Ngoại trừ những tài liệu tham khảo được trích dẫn trong luận văn này, tôi cam đoan toàn phần hay từng phần nhỏ của luận văn này chưa từng công bố hay được sử dụng để nhận bằng cấp ở nơi khác, các số liệu và kết quả trong luận văn này là trung thực. Tôi xin chịu trách nhiệm về luận văn của mình. Tác giả Nguyễn Hoàng Hải ii TÓM TẮT LUÂN VĂN XÂY DỰNG HỆ HỖ TRỢ TƯ VẤN TUYỂN SINH TẠI TRƯỜNG CAO ĐẲNG CỘNG ĐỒNG VĨNH LONG Học viên: Nguyễn Hoàng Hải Chuyên ngành: Khoa học máy tính Mã số: 64.08.01 Trường Đại học Bách khoa Tóm tắt: Ngành giáo dục luôn là vấn đề sống còn của bất kỳ quốc gia nào trên thế giới. Trong những năm gần đây, chính phủ Việt Nam đặc biệt đầu tư cho ngành mũi nhọn này thông qua các chính sách, nguồn vốn dành cho trang thiết bị, cơ sở hạ tầng và nghiên cứu khoa học. Trong lĩnh vực nghiên cứu khoa học, càng ngày càng có nhiều công trình khoa học về giáo dục. Với sự phát triển không ngừng của xã hội và việc ứng dụng công nghệ thông tin vào nhiều lĩnh vực là rất cần thiết. Trong công tác tuyển sinh của trường có một hệ thống hỗ trợ tư vấn là rất cần thiết. Chính vì vậy đề tài của tôi nghiên cứu về các qui chế tuyển sinh, khai phá dữ liệu với luật kết hợp và cây quyết định để xây dựng hệ thống tư vấn cho thí sinh mới tốt nghiệp trung học phổ thông, dự đoán kết quả học tập của thí sinh sau khi ra trường, dựa vào kết quả đầu vào và kết quả đầu ra của sinh viên đã học. Nghiên cứu tiến hành theo 4 bước chính: (1) Tìm hiểu công tác liên quan đến công tác tuyển sinh của trường Cao đẳng; (2) Thu thập và tiền xử lý dữ liệu tuyển sinh và kết quả học tập của Sinh viên; (3) Tìm hiểu về luật kết hợp và cây quyết định trong khai phá dữ liệu, lựa chọn thuật toán phù hợp với yêu cầu bài toán đặt ra và dữ liệu thu thập được; (4) Thực nghiệm chương trình trên máy tính và đánh giá kết quả thực tiễn. Ngoài ra, đề tài cũng xây dựng mô hình hỗ trợ tư vấn kết quả học tập cho các ngành khác nhau nhằm hỗ trợ cho các thí sinh lựa chọn ngành phù hợp với năng lực của bản thân và có thể thay thế cho cách tư vẫn thủ công của trường. BUILDING SUPPORT SYSTEMS TO SUPPORT CONSULTANCY IN VINH LONG COMMUNE COLLEGE Abstract: Education is always playing an important role of any countries all over the world. In the recent years, Vietnamese Government has been investing especially for that one via policies and capital intended for equipment, infrastructures and scientific researches. In the field of scientific research, there are more and more scientific research works for education. Society is always developing and the application of information technology on many fields that is essential. On the admission of universities or colleges, an iii consultant supporting system is very important. Therefore, my research object is about admission regulations, mining databases with combining rules and decision tree so that structuring consulting system for new graduates from high school, predicting study results for new graduate students, that is based on student’s income and outcome results. Research was implemented through four main steps: (1) comprehending any issues related to admission at the college; (2) collecting and pre-processing databases for admission and study results of students; (3) comprehending about combining rules and decision tree in databases mining , selecting appropriate algorithm that best fits the requirements and collected databases; (4) experimenting the computer program and evaluating results on the real application. Moreover, research has also structured the model of consultant supporting for student results of different majors which aim to support candidates selecting their suitable major to abilities themselves and can replace for the college’s manual consulting. iv MỤC LỤC LỜI CAM ĐOAN ................................................................................................................ i TÓM TẮT LUÂN VĂN .....................................................................................................ii MỤC LỤC .......................................................................................................................... iv DANH MỤC TỪ VIẾT TẮT ...........................................................................................vii DANH MỤC CÁC BẢNG.............................................................................................. viii DANH MỤC CÁC HÌNH ................................................................................................. ix MỞ ĐẦU .............................................................................................................................. 1 1. Lý do chọn đề tài ..................................................................................................... 1 2. Mục tiêu và nội dung nghiên cứu ............................................................................ 1 3. Đối tượng và phạm vi nghiên cứu ........................................................................... 2 4. Phuơng pháp nghiên cứu ......................................................................................... 2 5. Ý nghĩa khoa học và thực tiễn của đề tài ................................................................. 3 6. Bố cục luận văn........................................................................................................ 3 CHƯƠNG 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU ................................................. 5 1.1. Khai phá dữ liệu ............................................................................................................ 5 1.2. Một số định nghĩa mang tính mô tả về khai phá dữ liệu ............................................... 5 1.3. Các bước trong quá trình phát hiện tri thức [2] ............................................................. 5 1.4. Mô hình khai phá dữ liệu ............................................................................................... 6 1.5. Các phương pháp khai phá dữ liệu ................................................................................ 7 1.5.1. Các thành phần của giải thuật khai phá dữ liệu ................................................. 7 1.5.2. Một số phương pháp khai thác dữ liệu phổ biến ............................................... 8 1.5.2.1. Phương pháp quy nạp (Induction). ..................................................... 8 1.5.2.2. Cây quyết định và luật ......................................................................... 8 1.5.2.3. Phát hiện các luật kết hợp ................................................................... 9 1.6. Các giai đoạn của quá trình khai phá dữ liệu [1]: ....................................................... 10 1.6.1. Tìm hiểu nghiệp vụ và dữ liệu ......................................................................... 10 1.6.2. Chuẩn bị dữ liệu ............................................................................................... 10 1.6.3. Mô hình hóa dữ liệu ......................................................................................... 10 1.6.4. Hậu xử lý và đánh giá mô hình ........................................................................ 10 1.6.5. Triển khai mô hình ........................................................................................... 10 1.7. Ứng dụng trong khai phá dữ liệu ................................................................................. 11 1.8. Kết chương 1 ............................................................................................................... 12 v CHƯƠNG 2. CƠ SỞ LÝ THUYẾT VỀ LUẬT KẾT HỢP .......................................... 13 2.1. Lý thuyết về luật và luật kết hợp.................................................................................. 13 2.1.1. Luật kết hợp ..................................................................................................... 13 2.1.2. Luật thừa .......................................................................................................... 15 2.1.3. Một số tính chất của luật kết hợp[10] .............................................................. 16 2.1.4. Phát biểu bài toán khai phá luật kết hợp[11] ................................................... 18 2.1.5. Một số dạng luật trong khai phá luật kết hợp ................................................... 18 2.1.6. Các đặc trưng của luật kết hợp......................................................................... 20 2.1.6.1. Không gian tìm kiếm của luật ........................................................... 20 2.1.6.2. Độ hỗ trợ của luật ............................................................................. 22 2.2. Một số giải thuật cơ bản khai phá các tập mục phổ biến ............................................ 23 2.2.1. Phân loại các giải thuật .................................................................................... 23 2.2.2. Kỹ thuật BFS với thuật toán Apriori ............................................................... 23 2.3. Cây quyết định ............................................................................................................. 31 2.3.1. Định nghĩa........................................................................................................ 31 2.3.2. Giới thiệu cây quyết định ................................................................................. 31 2.3.3. Các kiểu cây quyết định ................................................................................... 32 2.3.4. Cấu trúc cây quyết định ................................................................................... 32 2.3.5. Sử dụng cây quyết định trong dự đoán lớp các dữ liệu chưa biết ................... 33 2.3.6. Đánh giá cây quyết định trong lĩnh vực khai phá dữ liệu: .............................. 35 2.3.7. Các thuật toán của cây quyết định: .................................................................. 35 2.3.8. Đánh giá hiệu quả phân lớp ............................................................................. 35 2.4. Thuật toán C4.5 xây dựng cây quyết định................................................................... 37 2.4.1. Tổng quan ........................................................................................................ 37 2.4.2. Mã giả của thuật toán C4.5 .............................................................................. 38 2.2.3. Thuật toán C4.5 dùng Gain-entropy ................................................................ 39 2.5. Kết chương 2 ............................................................................................................... 41 CHƯƠNG 3. XÂY DỰNG HỆ HỖ TRỢ TƯ VẤN TUYỂN SINH ............................. 42 3.1. Giới thiệu về trường CĐCĐ Vĩnh Long ...................................................................... 42 3.2. Giới thiệu về công cụ khai phá dữ liệu ........................................................................ 44 3.3. Mô hình và bài toán xậy dựng hệ hỗ trợ tư vấn tuyển sinh ......................................... 45 3.3.1. Mô hình ............................................................................................................ 45 3.3.2. Giới thiệu bài toán ........................................................................................... 46 3.4. Phân tích và thiết kế hệ thống...................................................................................... 46 3.4.1. Biểu đồ ca sử dụng........................................................................................... 46 vi 3.4.2. Biểu đồ tương tác ............................................................................................. 47 3.4.3. Biểu đồ lớp ....................................................................................................... 48 3.4.4. Biểu đồ tuần tự ................................................................................................. 48 3.4.5. Biểu đồ trạng thái ............................................................................................. 49 3.5. Xây dựng cơ sở dữ liệu................................................................................................ 49 3.6. Mô tả việc tổng hợp dữ liệu cho bài toán .................................................................... 50 3.7. Chuẩn hóa dữ liệu đầu vào cho thuật toán .................................................................. 52 3.7.1. Lọc thuộc tính (Filtering Attributes)................................................................ 53 3.7.2. Rời rạc hóa dữ liệu (Discretization) ................................................................ 54 3.8. Phân tích cơ sở dữ liệu dữ ........................................................................................... 56 3.8.1. Tìm hiểu và chuẩn bị dữ liệu ........................................................................... 56 3.8.2. Mô hình hóa dữ liệu ......................................................................................... 57 3.8.3. Đánh giá mô hình ............................................................................................. 57 3.9. Khai phá dữ liệu rút ra tri thức .................................................................................... 59 3.10. Kết chương 3 ............................................................................................................. 63 CHƯƠNG 4. TRIỂN KHAI HỆ THỐNG VÀ ĐÁNH GIÁ KẾT QUẢ ...................... 64 4.1. Biểu đồ triển khai hệ thống ......................................................................................... 64 4.2. Triển khai chương trình ............................................................................................... 64 4.2.1. Cài đặt chương trình ........................................................................................ 64 4.2.2. Hướng dẫn sử dụng .......................................................................................... 64 4.3. Hình ảnh trích ra từ chương trình demo ...................................................................... 65 4.3.1. Giao diện cài đặt chương trình......................................................................... 65 4.3.2. Giao diện trước khi chọn ngành ...................................................................... 66 4.3.3. Giao diện sau khi chọn ngành .......................................................................... 66 4.4. Đánh giá kết quả .......................................................................................................... 68 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ...................................................................... 69 DANH MỤC TÀI LIỆU THAM KHẢO ........................................................................ 70 PHỤ LỤC QUYẾT ĐỊNH GIAO ĐỀ TÀI BẢN SAO KẾT LUẬN CỦA HỘI ĐỒNG, BẢN SAO NHẬN XÉT CỦA CÁC PHẢN BIỆN. vii DANH MỤC TỪ VIẾT TẮT Tiếng Việt KPDL Khai phá dữ liệu CSDL Cơ sở dữ liệu SQL Ngôn ngữ truy vấn mang tính cấu trúc (Structured Query Language) Tiếng Anh KDD K-mean TID OLAP Knowledge Discovery Database K-mean clustering Transaction IDentifier Online Analysis Processing MOLAP multidimensional OLAP ROLAP Relational OLAP ADO Active X Data Object BFS Breadth First Search ID3 Decision tree Cart Classification and Regression Trees SLIQ Supervised Learning In Quest Sprint Scalable PaRallelization INduction of decision Trees Weka Waikato Environment for Knowledge Analysis viii DANH MỤC CÁC BẢNG Số hiệu Tên bảng bảng 2.1. 2.2. Ví dụ về một cơ sở dữ liệu dạng giao dịch – D Các tập phổ biến trong CSDL ở bảng 1 với độ hỗ trợ tối thiểu 50% Trang 13 14 2.3. Ví dụ thuật toán Apriori. 29 2.4. Bảng dữ liệu về thời tiết [9]. 33 2.5. Ví dụ về thời tiết trong 3 ngày 34 2.6 Kết quả phân lớp dữ liệu cho bảng 2.5 [9]. 34 2.7. Huấn luyện với thuộc tính phân lớp là buys computer [14] . 40 3.1. Danh sách các bảng trong CSDL 49 3.2. Cấu trúc bảng dữ liệu mẫu 50 3.3. Cấu trúc bảng kết quả luật suy diễn 50 3.4. Cấu trúc file dữ liệu của luận văn 52 3.5. Kết quả sau khi rời rạc thuộc tính TongDiemThi. 55 3.6. Mức độ quan trọng của thuộc tính 56 3.7. Giải thuật và các thuộc tính sử dụng cho hệ thống 57 3.8. Độ chính xác của các mô hình dự đoán 57 3.9. Confusion matrix trên kết quả dự đoán 4 lớp. 58 ix DANH MỤC CÁC HÌNH Số hiệu Tên bảng hình Trang 1.1 Các bước trong quá trình phát hiện tri thức. 6 2.1. Minh họa luật kết hợp không có tính tách. 17 2.2. Biểu diễn thông tin tìm kiếm dạng lới cho tập I = {1,2,3,4}. 21 2.3. Biểu diễn cây cho tập I = {1, 2, 3, 4}. 22 2.4. Hệ thống hóa các giải thuật. 23 2.5. Mô hình cây quyết định trong phân lớp dữ liệu về thời tiết [9]. 33 2.6. Quá trình train và test của classisfier. 36 2.7 Mô tả công việc của 3-fold. 37 2.8 Mô tả quá trình tính lỗi của 3-fold. 37 3.1 Trường Cao đẳng Cộng đồng Vĩnh Long - Khu 1. 42 3.2 Giao diện phần mềm Weka. 45 3.3 Mô hình giải pháp xây dựng hệ hỗ trợ tư vấn tuyển sinh. 45 3.4 Biểu đồ ca sử dụng người dùng 46 3.5 Biểu đồ ca sử dụng quản lý dữ liệu mẫu 47 3.6 Biểu đồ tương tác 47 3.7 Biểu đồ lớp các đối tượng 48 3.8 Biểu đồ chọn tư vấn 48 3.9. Biểu đồ tạo dữ liệu mẫu 49 3.10 Biểu đồ trạng thái 49 3.11 Cơ sở dữ liệu chưa chuẩn hóa. 51 3.12 Giao diện lọc thuộc tính với bộ lọc remove. 53 3.13 Cấu trúc dữ liệu sau khi lọc bỏ các thuộc tính thừa. 54 3.14 Giao diện chọn bộ lọc và thuộc tính rời rạc dữ liệu. 55 3.15 Giao diện trích chọn thuộc tính và xếp hạng thuộc tính. 56 3.16 Kết quả phân tích AUC. 58 4.1. Mô hình tổng thể của hệ thống. 64 4.2. Giao diện cài đặt chương trình. 65 4.3. Giao diện trước khi chọn ngành. 66 x Số hiệu hình Tên bảng Trang 4.4. Giao diện khi chọn ngành tổng điểm nhỏ hơn 13. 66 4.5. Giao diện khi chọn ngành tổng điểm nhỏ hơn 15. 67 4.6. Giao diện khi chọn ngành tổng điểm nhỏ hơn 21. 67 4.7. Giao diện khi chọn ngành tổng điểm nhỏ hơn 26. 68 1 MỞ ĐẦU 1. Lý do chọn đề tài Trải qua rất nhiều năm, phương thức tuyển sinh và đào tạo theo kiểu truyền thống cho thấy sự đóng góp rất lớn trong việc định hướng và phát triển của trường. Cùng với xu hướng phát triển của công nghệ thông tin và các phương tiện truyền thông, việc ứng dụng công nghệ thông tin vào công tác quản lý hiện đang là một nhu cầu cấp thiết nhằm tiết kiệm công sức và thời gian, nâng cao chất lượng đào tạo của trường. Theo đó là việc áp dụng nhiều cách thức tuyển sinh và đào tạo mới, cũng như liên kết đào tạo với các trường đại học và cao đẳng trong và ngoài nước đòi hỏi công tác quản lý phải thường xuyên có sự thay đổi, như quản lý đào tạo, quản lý tuyển sinh, quản lý điểm Đặc biệt, công tác tuyển sinh đã và đang là một vấn đề cấp thiết đến việc tồn tại và phát triển của các trường Đại học - Cao đẳng. Với thực trạng trong những năm gần đây công tác tuyển sinh của một số trường Đại học - Cao đẳng trong cả nước điều gặp nhiều khó khăn đặc biệt là các trường ở tốp dưới, Trường Cao đẳng Cộng đồng Vĩnh Long là một trong số đó. Có rất nhiều phương pháp đặt ra để giải quyết khó khăn trong công tác tư vấn tuyển sinh nhưng hiệu quả chưa cao. Hơn nữa với sự phát triển của xã hội như hiện nay, 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 ngày 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à tìm cách trích rút từ tập dữ liệu đó với 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 đó. Việc hỗ trợ tư vấn chọn ngành phù hợp với năng lực và nhu cầu của học sinh là rất cần thiết giúp cho các em định hướng được tương lai của mình. Nhận thấy được những thực trạng như trên, tôi quyết định chọn đề tài: "Xây dựng hệ hỗ trợ tư vấn tuyển sinh tại Trường Cao đẳng Cộng đồng Vĩnh Long", với mục đích áp dụng công nghệ thông tin, giảm tải chi phí và tiết kiệm thời gian trong công tác tuyển sinh nhằm nâng cao hiệu quả trong đào tạo và phát triển của trường. Đề tài nghiên cứu về công cụ khai phá dữ liệu, các luật kết hợp và thuật toán cây quyết định trong việc khai phá dữ liệu để xây dựng hệ hỗ trợ tư vấn tuyển sinh. Tôi hy vọng đề tài sẽ đáp ứng được nhu cầu thực tế cấp thiết của trường. 2. Mục tiêu và nội dung nghiên cứu 2.1. Mục tiêu của đề tài 2 Mục tiêu chung: xây dựng hệ hỗ trợ tư vấn tuyển sinh của các trường theo mô hình Cao đẳng Cộng đồng. Mục tiêu cụ thể: + Tìm hiểu sơ lượt khái quát về công tác tuyển sinh Trường Cao đẳng Cộng đồng Vĩnh Long. + Nghiên cứa ứng dụng luật kết hợp và thuât toán cây quyết định vào tập dữ liệu mẫu để xây dựng chương trình hệ hỗ trợ tư vấn tuyển sinh tại Trường Cao đẳng Cộng đồng Vĩnh Long. 2.2. Nội dung nghiên cứu - Quy trình tuyển sinh - Tổng quan về khai phá dữ liệu, tập dữ liệu mẫu, luật kết hợp và cây quyết định 3. Đối tượng và phạm vi nghiên cứu 3.1. Đối tượng nghiên cứu của đề tài gồm + Học sinh và Sinh viên: họ và tên, giới tính, ngày sinh, địa chỉ, điểm từng môn, điểm trung bình học kì, điểm trung bình năm, điểm tốt nghiệp trung học phổ thông, điểm tốt nghiệp Cao đẳng. + Quy trình tuyển sinh và quy chế xét tuyển: hồ sơ xét tuyển, đợt xét tuyển, năng khiếu để xét tuyển… + Kỹ thuật khai phá dữ liệu cụ thể là luật kết hợp và cây quyết định. 3.2. Phạm vi nghiên cứu + Kỹ thuật phân lớp: cây quyết định và luật kết hợp. + Công cụ khai phá dữ liệu, SQL server và ngôn ngữ lập trình ASP.NET + Công tác tư vấn tuyển sinh Trường Cao đẳng Cộng đồng Vĩnh Long. Đề tài thuộc loại hình nghiên cứu ứng dụng, phạm vi áp dụng của đề tài triển khai tại trường Cao đẳng Cộng đồng Vĩnh Long tỉnh Vĩnh Long 4. Phuơng pháp nghiên cứu 4.1. Nghiên cứu lý thuyết - Thu thập và nghiên cứu các tài liệu liên quan đến đề tài. - Nghiên cứu thực trạng tuyển sinh tại trường Cao đẳng Cộng đồng Vĩnh Long, tìm hiểu nhu cầu thực tế của người học và nhu cầu việc làm ngoài xã hội. 4.2. Nghiên cứu thực nghiệm 3 - Tiến hành xây dựng các giải pháp và xây dựng ứng dụng đánh giá. - Phân tích thiết kế cơ sở dữ liệu tuyển sinh và kết quả học tập của Sinh viên từ đó so sánh và dự đoán kết quả học tập của từng ngành, xây dựng hệ thống chương trình ứng dụng, triển khai xây dựng chương trình ứng dụng, kiểm tra, thử nghiệm và đánh giá kết quả. 5. Ý nghĩa khoa học và thực tiễn của đề tài 5.1. Ý nghĩa khoa học - Tìm hiểu luật kết hợp và cây quyết định trong khai phá dữ liệu. - Đề tài xây dưng ra một hệ thống tư vấn hỗ trợ tư vấn tuyển sinh của trường. 5.2. Ý nghĩa thực tiễn - Thu thập và thiết kế được kho cơ sở dữ liệu phục vụ quá trình tư vấn tuyển sinh. - Góp phần nâng cao hiệu quả trong tuyển sinh cũng như sự phát triển trong việc dạy và học của trường. 6. Bố cục luận văn Chương 1: Tổng quan về khai phá dữ liệu và phát hiện tri thức. Chương này đề cập đến các giai đoạn của quy trình phát hiện tri thức, các vấn đề chính của khai phá dữ liệu, các phương pháp, các nhiệm vụ trong khai phá dữ liệu Chương 2: Cơ sở lý thuyết về luật kết hợp và cây quyết định. Chương này trình bày một số vấn đề chính của khai phá luật kết hợp: lý thuyết luật kết hợp, bài toán khai phá và phát hiện luật kết hợp, các phương pháp phát hiện luật kết hợp, một số thuật toán điển hình giải quyết vấn đề, phân tích độ phức tạp của bài toán. Chương 3: Xây dựng hệ hỗ trợ tư vấn tuyển sinh. Nội dung của chương là áp dụng kỹ thuật khai phá luật kết hợp và cây quyết định vào trong đào tạo của trường Cao đẳng Cộng đồng Vĩnh Long. Ứng dụng này nhằm đưa ra dự báo hỗ trợ cho công tác tuyển sinh và đào tạo của trường. Chương 4: Triển khai hệ thống và đánh giá kết quả. Nội dung chương 4 tập trung phân tích yêu cầu của hệ thống, xác định các chức năng chính, xây dựng sơ đồ các hoạt động chính của ứng dụng, tiến hành cài đặt ứng dụng, thực nghiệm và đánh giá kết quả. 4 Phần phụ lục đưa ra một số modul của chương trình ứng dụng. Cuối cùng là kết luận lại những kết quả đạt được của đề tài và hướng phát triển trong tương lai. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN. TÀI LIỆU THAM KHẢO. QUYẾT ĐỊNH GIAO ĐỀ TÀI LUẬN VĂN PHỤ LỤC 5 CHƯƠNG 1 TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ PHÁT HIỆN TRI THỨC 1.1. Khai phá dữ liệu KPDL thu hút sự chú ý của nền công nghiệp thông tin và xã hội trong những năm gần đây. Với sự phát triển của công nghệ thông tin, dữ liệu lưu trữ mỗi ngày trở thành một cơ sở dữ liệu rất lớn. Dựa vào khối lượng dữ liệu này, ta dùng những kỹ thuật KPDL để chuyển dữ liệu đó thành những thông tin có ích hoặc rút ra những tri thức mới từ dữ liệu thu thập được[9]. Quá trình này kết xuất ra các tri thức tiềm ẩn từ dữ liệu giúp cho việc dự báo trong kinh doanh, các hoạt động sản xuất, ... Khai phá dữ liệu làm giảm chi phí về thời gian so với phương pháp truyền thống trước kia (ví dụ như phương pháp thống kê). 1.2. Một số định nghĩa mang tính mô tả về khai phá dữ liệu Định nghĩa của Ferruzza: “Khai phá dữ liệu là tập hợp các phương pháp được dùng trong tiến trình khám phá tri thức để chỉ ra sự khác biệt các mối quan hệ và các mẫu chưa biết bên trong dữ liệu”. Định nghĩa của Parsaye: “Khai phá dữ liệu là quá trình trợ giúp quyết định, trong đó chúng ta tìm kiếm các mẫu thông tin chưa biết và bất ngờ trong CSDL lớn”. Định nghĩa của Fayyad: “Khai phá tri thức là một quá trình không tầm thường nhận ra những mẫu dữ liệu có giá trị, mới, hữu ích, tiềm năng và có thể hiểu được”. 1.3. Các bước trong quá trình phát hiện tri thức [2] Phát hiện tri thức bao gồm nhiều giai đoạn được lặp đi lặp lại nhiều lần mà không cần phân biệt từng bước trong quá trình thực hiện. Giai đoạn 1: Hình thành, xác định và định nghĩa bài toán. Là việc tìm hiểu lĩnh vực ứng dụng từ đó hình thành bài toán, xác định các nhiệm vụ cần phải hoàn thành. Bước này sẽ quyết định cho việc rút ra được các tri thức hữu ích và cho phép chọn các phương pháp khai phá dữ liệu thích hợp với mục đích ứng dụng cùng với bản chất của dữ liệu. Giai đoạn 2: Thu thập và tiền xử lý (xử lý thô). Bước này còn được gọi là tiền xử lý dữ liệu nhằm loại bỏ nhiễu (dữ liệu dư thừa), làm sạch dữ liệu, xử lý và khắc phục vấn đề thiếu hoặc thừa dữ liệu, biến đổi dữ liệu và rút gọn dữ liệu nếu cần thiết. Bước này thường chiếm nhiều thời gian nhất (bước quan trọng) trong toàn bộ quy trình phát hiện tri thức. Giai đoạn 3: Biến đổi dữ liệu, chọn lựa một số phương pháp. Phân loại (Classification), hồi quy (Regression), phân nhóm (Clustering), quy nạp, tổng hợp kết quả (Summarization). 6 Hình 1.1. Các bước trong quá trình phát hiện tri thức. Giai đoạn 4: Khai phá dữ liệu, hay nói cách khác là trích chọn, chiết xuất ra các mẫu hay các mô hình tiềm ẩn dưới các dữ liệu có ý nghĩa, hiểu được. Giai đoạn này rất quan trọng, bao gồm các công đoạn như: chức năng, nhiệm vụ và mục đích khai phá dữ liệu, dùng phương pháp khai phá nào là thích hợp?. Giai đoạn 5: Giải thích kết quả và đánh giá các mẫu hay mô hình. Các mẫu và mô hình này là kết quả của giai đoạn 3 trong quy trình. Đây là công đoạn không thể thiếu trong quá trình khai phá tri thức. Giai đoạn 6: Hiểu và sử dụng tri thức đã tìm được, đặc biệt là làm sáng tỏ các mô tả và dự đoán. Các bước trên có thể lặp đi lặp lại một số lần, kết quả thu được có thể được lấy trên tất cả các lần thực hiện. Tóm lại: Quá trình phát hiện tri thức từ trong kho dữ liệu (KDD – Knowledge Discovery Database) là quá trình chiết xuất ra tri thức từ kho dữ liệu mà trong đó khai phá dữ liệu là công đoạn quan trọng nhất. 1.4. Mô hình khai phá dữ liệu Mô hình khai phá dữ liệu là một mô tả về một khía cạnh cụ thể của một tập dữ liệu. Nó tạo ra các giá trị đầu ra cho tập các giá trị đầu vào. Ví dụ: Mô hình hồi qui tuyến tính, mô hình phân lớp, mô hình phân nhóm. Một mô hình khai phá dữ liệu có thể được mô tả 2 mức: 7 - Mức chức năng (Function level): Mô tả mô hình bằng những thuật ngữ về dự định sử dụng. Ví dụ: phân lớp, phân nhóm. - Mức biểu diễn (representation level): Biểu diễn cụ thể một mô hình. Ví dụ: Mô hình log-linear, cây phân lớp, phương pháp láng giềng gần nhất. Các mô hình khai phá dữ liệu dựa trên 2 kiểu học: Có giám sát và không giám sát (đôi khi được nói đến như là học trực tiếp và không trực tiếp – directed and undirected learning). Các hàm học có giám sát (Supervised learning functions) được sử dụng để dự đoán giá trị. Các hàm học không giám sát được dùng để tìm ra cấu trúc bên trong, các quan hệ hoặc tính giống nhau trong nội dung dữ liệu nhưng không có lớp hay nhãn nào được gán ưu tiên. Ví dụ của các thuật toán học không giám sát gồm phân nhóm kmean (k-mean clustering) và các luật kết hợp Apriori. Một ví dụ của thuật toán học có giám sát bao gồm Naïve Bayes cho phân lớp (classification). Tương ứng có 2 loại mô hình khai phá dữ liệu: - Các mô hình dự báo (học có giám sát): + Phân lớp: Nhóm các mục thành các lớp riêng biệt và dự đoán một mục sẽ thuộc vào lớp nào. + Hồi qui (Regression): Xấp xỉ hàm và dự báo các giá trị liên tục. + Độ quan trọng của thuộc tính: Xác định các thuộc tính là quan trọng nhất trong các kết quả dự báo. - Các mô hình mô tả (học không giám sát): + Phấn nhóm (Clusterning): Tìm các nhóm tự nhiên trong dữ liệu. + Các mô hình luật kết hợp (Association models): Phân tích “giỏ hàng”. + Trích chọn đặc trưng (Feature extraction): Tạo các thuộc tính (đặc trưng) mới như là kết hợp của các thuộc tính ban đầu. 1.5. Các phương pháp khai phá dữ liệu Quá trình khai phá dữ liệu là quá trình phát hiện mẫu, trong đó, giải thuật khai phá dữ liệu tìm kiếm các mẫu đáng quan tâm theo dạng xác định như các luật, cây phân lớp, hồi quy, gom nhóm,... 1.5.1. Các thành phần của giải thuật khai phá dữ liệu Giải thuật khai phá dữ liệu bao gồm 3 thành phần chính như sau: biểu diễn mô hình, đánh giá mô hình, tìm kiếm mô hình. • Biểu diễn mô hình: Mô hình được biểu diễn bằng một ngôn ngữ L để mô tả các mẫu có thể khai thác được. Tức là người phân tích dữ liệu cần phải hiểu đầy đủ các giả thiết mô tả và cần phải diễn tả được các giả thiết mô tả nào được tạo ra bởi giải thuật. Mô hình đó sẽ được đánh giá bằng cách đưa các dữ liệu thử vào mô hình và thay đổi lại các tham số cho phù hợp nếu cần. 8 • Đánh giá mô hình: Đánh giá xem một mẫu có đáp ứng được các tiêu chuẩn của quá trình phát hiện tri thức hay không. Việc đánh giá độ chính xác dự đoán dựa trên đánh giá chéo (Cross Validation). Đánh giá chất lượng mô tả liên quan đến độ chính xác dự đoán, độ mới, khả năng sử dụng, khả năng hiểu được của mô hình. Cả hai chuẩn thống kê và chuẩn logic đều có thể được sử dụng để đánh giá mô hình. • Phương pháp tìm kiếm: Phương pháp tìm kiếm bao gồm hai thành phần: tìm kiếm tham số và tìm kiếm mô hình. - Tìm kiếm tham số: Để tối ưu hóa các tiêu chuẩn đánh giá mô hình với các dữ liệu quan sát được và với một mô tả mô hình đã định. - Tìm kiếm mô hình: Xảy ra giống như một vòng lặp qua phương pháp tìm kiếm tham số: Mô tả mô hình bị thay đổi tạo nên một họ các mô hình. = > Với mỗi một mô tả mô hình, phương pháp tìm kiếm tham số được áp dụng để đánh giá chất lượng mô hình. Các phương pháp tìm kiếm mô hình thường sử dụng các kỹ thuật tìm kiếm heuristic vì kích thước của không gian các mô hình có thể thường ngăn cản các tìm kiếm tổng thể, hơn nữa các giải pháp đơn giản không dễ đạt được. 1.5.2. Một số phương pháp khai thác dữ liệu phổ biến 1.5.2.1. Phương pháp quy nạp (Induction). Một cơ sở dữ liệu là một kho thông tin nhưng các thông tin quan trọng hơn cũng có thể được suy diễn từ kho thông tin đó. Có hai kỹ thuật chính để thực hiện việc này là suy diễn và quy nạp. • Phương pháp suy diễn: Nhằm rút ra thông tin là kết quả logic của các thông tin trong cơ sở dữ liệu. Phương pháp suy diễn dựa trên các sự kiện chính xác để suy ra các tri thức mới từ các thông tin cũ. Mẫu chiết xuất được bằng cách sử dụng phương pháp này thường là các luật suy diễn. • Phương pháp quy nạp: Phương pháp quy nạp suy ra các thông tin được sinh ra từ cơ sở dữ liệu. Có nghĩa là nó tự tìm kiếm, tạo mẫu và sinh ra tri thức chứ không phải bắt đầu với các tri thức đã biết trước. Các thông tin mà phương pháp này đem lại là các thông tin hay các tri thức cấp cao diễn tả về các đối tượng trong cơ sở dữ liệu. Phương pháp này liên quan đến việc tìm kiếm các mẫu trong CSDL. Trong khai phá dữ liệu, quy nạp được sử dụng trong cây quyết định và tạo luật. 1.5.2.2. Cây quyết định và luật • Cây quyết định: Cây quyết định là một mô tả tri thức dạng đơn giản nhằm phân các đối tượng dữ liệu thành một số lớp nhất định. Các nút của cây được gán nhãn là tên các thuộc tính, các cạnh được gán các giá trị có thể của các thuộc tính, các lá mô tả các lớp khác nhau. Các đối tượng được phân lớp theo các đường đi trên cây, qua các cạnh tương ứng với các giá trị, thuộc tính của đối tượng tới lá.