Tài liệu Luận văn thạc sĩ xây dựng hệ thống hỗ trợ tư vấn hướng nghiệp cho học sinh thpt tỉnh trà vinh

ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA NGUYỄN THANH PHONG XÂY DỰNG HỆ THỐNG HỖ TRỢ TƯ VẤN HƯỚNG NGHIỆP CHO HỌC SINH THPT TỈNH TRÀ VINH 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 THANH PHONG XÂY DỰNG HỆ THỐNG HỖ TRỢ TƯ VẤN HƯỚNG NGHIỆP CHO HỌC SINH THPT TỈNH TRÀ VINH 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 : Những nội dung trong luận văn này là do tôi thực hiện dưới sự hướng dẫn trực tiếp của TS. Trương Ngọc Châu. Mọi tham khảo dùng trong luận văn đều được trích dẫn rõ ràng và trung thực tên tác giả, tên công trình, thời gian, địa điểm công bố. Mọi sao chép không hợp lệ, vi phạm quy chế đào tạo, hay gian trá, tôi xin chịu hoàn toàn trách nhiệm. Tác giả Nguyễn Thanh Phong ii TÓM TẮT LUẬN VĂN XÂY DỰNG HỆ THỐNG TƯ VẤN HƯỚNG NGHIỆP CHO HỌC SINH THPT TỈNH TRÀ VINH Nguyễn Thanh Phong, học viên cao học khoá 31, chuyên ngành Khoa học máy tính Tóm tắt - Nhằm đạt được mục tiêu cuối cùng là nâng cao chất lượng và số lượng học sinh đỗ tốt nghiệp đại học đạt khá giỏi tại trường Đại học Trà Vinh ngày càng cao. Việc sử dụng phương pháp phân lớp giúp xác định được chất lượng chuyên môn của các môn thi bắt buộc và điểm xét tốt nghiệp của học sinh, từ đó giúp ban giám hiệu nhà trường tư vấn cho các em chọn đúng ngành nghề. Mặt khác, để giúp các cấp quản lý, hội đồng bộ môn, ban giám hiệu các trường trung học phổ thông xây dựng kế hoạch hợp lí hơn nhằm đạt được những mục tiêu mong muốn. Tôi nghĩ có thể vận dụng phương pháp phân lớp dựa trên cây quyết định khai thác tập dữ liệu điểm đầu vào và đầu ra của sinh viên từ đó các được cái nhìn khách quan hơn, chính xác hơn. Tìm hiểu từng ngành nghề một, tư duy nghề nghiệp có hợp với cá nhân, sở thích, nhu cầu tuyển dụng, công việc cụ thể ra sao. Từ các yêu cầu trên tôi xây dựng cây quyết định để xử lý bài toán. Học sinh có sự thay đổi trong chọn ngành học, lựa chọn cho phù hợp với điều kiện của các em. Và kết quả này sẽ là cơ sở cho việc định hướng phát triển học tập chọn ngành nghề cho các em trong tương lai. Từ khóa – Hệ thống tư vấn; hướng nghiệp; học sinh; phương pháp phân lớp; cây quyết định. BUILDING CAREER ADVISORY SYSTEM FOR HIGH SCHOOL STUDENTS OF TRA VINH PROVINCE Abstract – In order to achieve the ultimate goal is to improve the quality and number of students passing the university graduates are quite good at Tra Vinh University increasingly. The use of the layered approach helps to determine the professional qualities of compulsory and graduate school graduation exams, and helps the school administration advise them to select the right trades. On the other hand, to help administrators, departmental committees, high school administrators make more reasonable plans to achieve the desired goals. I think it is possible to manipulate the decision tree based on the decision tree to exploit the input and output data set of students from which the view is more objective and accurate. Understand each industry, occupational thinking, personal preferences, hiring, job requirements. From the above requirements, I built the decision tree to handle the problem. Students have a change in their chosen field of study, chosen to suit their condition. And this result will be the basis for the future orientation of the development of vocational education in the future. Key words - Counseling system; vocational guidance; student; Classification method; Decision tree. iii MỤC LỤC LỜI CAM ĐOAN ............................................................................................................. i TÓM TẮT LUẬN VĂN .................................................................................................. ii MỤC LỤC ...................................................................................................................... iii DANH MỤC CÁC BẢNG .............................................................................................. v DANH MỤC CÁC HÌNH .............................................................................................. vi MỞ ĐẦU ......................................................................................................................... 1 1. Lý do chọn đề tài ................................................................................................ 1 2. Mục tiêu và nhiệm vụ ......................................................................................... 2 3. Đối tượng và phạm vi nghiên cứu ...................................................................... 2 4. Phương pháp nghiên cứu .................................................................................... 3 5. Ý nghĩa đề tài ...................................................................................................... 3 6. Bố cục của luận văn ............................................................................................ 3 CHƯƠNG 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU................................................ 5 1.1. Giới thiệu chung ....................................................................................................... 5 1.2. Các khái niệm về khai phá dữ liệu ........................................................................... 5 1.3. Tại sao phải khai phá dữ liệu .................................................................................... 5 1.4. Quá trình khai phá tri thức........................................................................................ 7 1.5. Các kỹ thuật khai phá dữ liệu ................................................................................... 8 1.6. Những thách thức trong ứng dụng và nghiên cứu trong kỹ thuật khai phá dữ liệu 10 CHƯƠNG 2. PHƯƠNG PHÁP PHÂN CỤM VÀ PHÂN LỚP DỮ LIỆU TRONG KHAI PHÁ DỮ LIỆU ................................................................................................... 13 2.1. Phân cụm dữ liệu .................................................................................................... 13 2.1.1. Tổng quan về phân cụm dữ liệu.................................................................. 13 2.1.2. Các kỹ thuật phân cụm ............................................................................... 14 2.1.3. Độ đo khoảng cách: .................................................................................... 16 2.1.4. Giới thiệu thuật toán k-means ..................................................................... 17 2.2. Phân lớp dữ liệu ...................................................................................................... 19 2.2.1. Tổng quan về phân lớp dữ liệu ................................................................... 19 2.2.2. Các kỹ thuật phân lớp ................................................................................. 21 2.2.3. Cây quyết định ứng dụng trong phân lớp dữ liệu ....................................... 22 2.2.4. Xây đựng cây quyết định ............................................................................ 25 2.2.4.1. Chọn thuộc tính phân tách ......................................................................25 2.2.4.2. Độ lợi thông tin (Information gain) ........................................................26 iv 2.2.5. Thuật toán phân lớp cây quyết định ID3 .................................................... 27 2.2.6. Chuyển cây về các luật ............................................................................... 35 2.2.7. Khi nào nên sử dụng ID3 ............................................................................ 35 CHƯƠNG 3. XÂY DỰNG CÂY QUYẾT ĐỊNH ĐỂ ĐÁNH GIÁ KẾT QUẢ THI ĐẦU VÀO CỦA SINH VIÊN TRƯỜNG ĐẠI HỌC TRÀ VINH TỪ ĐÓ TƯ VẤN CHO CÁC EM CÁC NGÀNH NGHỀ TRONG TƯƠNG LAI .................................... 37 3.1. Phân tích bài toán và hướng giải quyết .................................................................. 37 3.1.1. Phát biểu bài toán........................................................................................ 37 3.1.2. Giải quyết bài toán ...................................................................................... 38 3.2. Tổng quan về phần mềm Weka .............................................................................. 38 3.3. Sử dụng phần mềm Weka để xây dựng cây quyết định để từ đó tư vấn cho các em ngành nghề trong tương lai ............................................................................................ 38 3.4. Thu thập dữ liệu ...................................................................................................... 39 3.5. Thực hiện khai phá dữ liệu ..................................................................................... 40 3.6. Sử dụng phần mềm Weka để xây dựng cây quyết định ......................................... 42 3.6.1. Giới thiệu về cây quyết định ....................................................................... 42 3.6.2. Thuật toán xây dựng cây quyết định........................................................... 43 3.6.3. Mã của thuật toán ........................................................................................ 44 3.6.4. Sử dụng phần mềm Weka ........................................................................... 45 3.7. Ứng dụng tri thức từ cây quyết định....................................................................... 48 3.7.1. Các mô-đun của hệ thống ........................................................................... 52 3.7.2. Cài đặt hệ thống .......................................................................................... 54 3.7.3. Bảng mô tả cấu trúc dữ liệu ........................................................................ 55 3.7.4. Giao diện chương trình tư vấn .................................................................... 57 KẾT LUẬN ................................................................................................................... 59 DANH MỤC TÀI LIỆU THAM KHẢO ...................................................................... 60 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. v DANH MỤC CÁC BẢNG Số hiệu Tên bảng Trang 2.1 Mô tả cấu trúc dữ liệu 27 2.2. Mô tả cấu trúc dữ liệu 31 3.1. Bảng mô tả cấu trúc tập dữ liệu trường ĐHTV 40 3.2. Mô tả cấu trúc dữ liệu 55 vi DANH MỤC CÁC HÌNH Số hiệu Tên hình Trang 1.1. 1.2. Mô tả luồng dữ liệu trong một tổ chức Quá trình phát hiện tri thức So sánh gom nhóm dữ liệu theo khoảng cách địa lý và kích thước Quá trình phân lớp dữ liệu – (a) Bước xây dựng mô hình phân lớp Quá trình phân lớp dữ liệu – (b1) Ước lượng độ chính xác mô hình Quá trình phân lớp dữ liệu – (b2) phân lớp dữ liệu mới Ví dụ cây quyết định Phân tách dữ liệu Mô hình cây quyết định Mô hình cây quyết định sau khi xét chọn thuộc tính quang cảnh Mô hình cây quyết định, sau khi áp dụng thuật toán ID3 Tập tin trước khi xử lý Loại bỏ các thuộc tính Chuẩn hóa dữ liệu Chuyển thuộc tính Numeric sang thuộc tính Nominal Cây quyết định Kết quả quả hiển thị ở khung Classifiter output Cây quyết định Sơ đồ giải thuật thêm luật vào hệ thống Sơ đồ giải thuật sửa luật vào hệ thống Sơ đồ giải thuật sửa luật vào hệ thống Mô hình kết nối WebSite voi database Lưu đồ mô tả quá trình làm Giao diện chương trình Giao diện chương trình sau khi tư vấn 6 7 2.1. 2.2. 2.3. 2.4. 2.5. 2.6. 2.7. 2.8. 2.9. 3.1. 3.2. 3.3. 3.4. 3.5. 3.6. 3.7. 3.8. 3.9. 3.10. 3.11. 3.12. 3.13. 3.14. 14 20 21 21 22 25 29 33 34 40 41 42 42 43 45 47 52 53 54 55 56 57 57 1 MỞ ĐẦU 1. Lý do chọn đề tài Sự phát triển không ngừng của ngành công nghệ thông tin nói chung và các lĩnh vực ngành công nghệ phần mềm nói riêng, việc tin học hóa các công tác quản lý trong nhiều lĩnh vực, hoạt động khác nhau đã tạo ra cho chúng ta một thư viện dữ liệu khổng lồ, sẵn sàng phục vụ bất cứ ai quan tâm. Đối với chúng ta nó là một trong những nguồn tài nguyên thông tin vô cùng giá trị, việc tận dụng kho dữ liệu này để làm cơ sở cho việc hỗ trợ ra quyết định trong công tác quản lý mang lại hiệu quả đáng kể. Nhưng vấn đề là chúng ta cần phải phân loại nguồn tài nguyên đó như thế nào để sử dụng có hiệu quả nhất trong từng lĩnh vực cụ thể. Chính vì vậy mà hiện nay các phương pháp quản trị và khai thác cơ sở dữ liệu truyền thống ngày càng không đáp ứng được nhu cầu thực tế, từ những hiện trạng này đã làm phát triển một kỹ thuật mới nhằm giải quyết bài toán này, đó là Kỹ thuật phát hiện tri thức và khai phá dữ liệu (Knowledge Discovery and Data Mining). Kỹ thuật phát hiện tri thức và khai phá dữ liệu đã và đang được nghiên cứu, ứng dụng rộng rãi trong nhiều lĩnh vực khác nhau ở các nước trên thế giới, tại Việt Nam kỹ thuật này cũng đang được nghiên cứu và dần đưa vào ứng dụng. Trong lĩnh vực giáo dục tôi nghĩ rằng từ cơ sở dữ liệu kết quả tốt nghiệp trung học phổ thông hằng năm của học sinh đang được lưu tại Phòng Khảo thí và Kiểm định chất lượng giáo dục của Sở Giáo dục. Chúng ta có thể áp dụng các kỹ thuật khai phá dữ liệu để đưa ra dự đoán và đánh giá kết quả học tập của học sinh từ đó đề ra định hướng cho học sinh chọn ngành nghề ,hướng nghề nghiệp cho học sinh v.v… Bản thân tôi hiện nay đang công tác tại Trung tâm giáo dục thường xuyên Tỉnh Trà Vinh nhận thấy đây là một vấn đề khó khăn trong chuyên môn của các đơn vị trường học nên cố gắng vận dụng những kiến thức được học tại lớp Cao học ngành Công nghệ Thông tin của Trường Đại học Đà Nẵng để đưa ra một giải pháp dự đoán, định hướng được các ngành nghề trong tương lai dựa vào kết quả học tập tốt nghiệp THPT và sở thích của học sinh. Vì những lý do như trên, tôi đề xuất chọn đề tài luận văn cao học“Xây dựng hệ thống hỗ trợ tư vấn hướng nghiệp cho học sinh trung học phổ thông tỉnh Trà Vinh” 2 2. Mục tiêu và nhiệm vụ a. Mục tiêu Mục tiêu chính của đề tài là từ cơ sở dữ liệu kết quả tốt nghiệp trung học phổ thông hằng năm của học sinh đang được lưu tại Phòng Khảo thí và Kiểm định chất lượng giáo dục của Sở Giáo dục. Chúng ta có thể áp dụng các kỹ thuật khai phá dữ liệu nhằm: - Đánh giá được kết quả học tập của học sinh lớp 12. Giúp Ban giám hiệu nhà trường có những kế hoạch cho các em. - Đưa ra các nhận xét về kết quả đậu tốt nghiệp trung học phổ thông quốc gia đối với học sinh lớp 12 của các trường THPT. Giúp Ban giám hiệu nhà trường tư vấn cho các em chọn lựa ngành nghề, phù hợp với khả năng của các em. b. Nhiệm vụ - Nghiên cứu và vận dụng các kỹ thuật về khai phá dữ liệu, các thuật toán được áp dụng cho từng kỹ thuật. - Nắm vững và vận dụng tốt kỹ thuật phân cụm trong khai phá dữ liệu, các thuật toán cơ bản trong phân cụm dữ liệu. Để phân tích kết quả học tập của học sinh. - Nắm vững và vận dụng tốt kỹ thuật phân lớp dựa trên cây quyết định để đưa ra những dự đoán về kết quả tốt nghiệp trung học phổ thông của học sinh lớp 12 của các trường THPT trong tỉnh - Đánh giá kết quả theo yêu cầu của đề tài. - Nghiên cứu đánh giá và xếp loại học trung học phổ thông; Những định hướng của Bộ về phát triển toàn diện chương trình giáo dục phổ thông. 3. Đối tượng và phạm vi nghiên cứu Trong khuôn khổ của luận văn thuộc loại nghiên cứu và ứng dụng, tôi chỉ giới hạn nghiên cứu các vấn đề sau: - Quá trình khám phá tri thức và khai phá dữ liệu. Các kỹ thuật về khai phá dữ liệu, một số thuật toán được áp dụng cho từng kỹ thuật. - Bảng ghi thông tin điểm thi đầu vào của trường Đại học Trà Vinh. - Các văn bản hướng dẫn cách đánh giá, xếp loại học sinh. 3 4. Phương pháp nghiên cứu a. Phương pháp lý thuyết - Tiến hành thu thập và nghiên cứu các tài liệu có liên quan đến đề tài. - Nghiên cứu và vận dụng các kỹ thuật về khai phá dữ liệu, các thuật toán được áp dụng cho từng kỹ thuật. - Nghiên cứu kỹ thuật phân cụm trong khai phá dữ liệu, các thuật toán cơ bản trong phân cụm dữ liệu. (thuật toán K-means). - Nghiên cứu kỹ thuật phân lớp dựa trên cây quyết định. b. Phương pháp thực nghiệm - Sử dụng phần mềm C# và SQL Server - Cài đặt ứng dụng trên môi trường Window - Kiểm tra, thử nghiệm và đánh giá kết quả. 5. Ý nghĩa đề tài a. Ý nghĩa khoa học - Hiểu được một số kỹ thuật cơ bản để khai phá dữ liệu, các chức năng và ứng dụng của khai phá dữ liệu. - Phát triển ứng dụng để góp phần phổ biến và từng bước thâm nhập sâu hơn về kỹ thuật này. b. Ý nghĩa thực tiễn - Ứng dụng những thành quả của công nghệ thông tin vào lĩnh vực giáo dục, góp phần phục vụ tốt việc tìm hiểu nghiên cứu đánh giá chất lượng giáo dục tại các trường trung học phổ thông của tỉnh Trà Vinh - Hỗ trợ công tác quản lý, đề ra định hướng và tư vấn cho các em học sinh trong tương lai 6. Bố cục của luận văn Luận văn bao gồm ba chương với các nội dung nghiên cứu như sau: Chương 1: Trình bày các khái niệm khám phá tri thức và khai phá dữ liệu, ứng dụng của khai phá dữ liệu (Data mining), quá trình phát hiện tri thức, giới thiệu các kỹ thuật khai phá dữ liệu, những lợi thế và thách thức của KPDL. 4 Chương 2: Giới thiệu về phân cụm và phân lớp dữ liệu trong khai phá dữ liệu. Trong phân cụm dữ liệu giới thiệu các kỹ thuật phân cụm dữ liệu, thuật toán k-means. Trong phân lớp dữ liệu giới thiệu các kỹ thuật phân lớp, thuật toán xây dựng cây quyết định ID3, chuyển cây về các luật. Chương 3: Xây dựng cây quyết định để đánh giá kết quả thi đầu vào của sinh viên trường Đại học trà vinh từ đó tư vấn cho các em các ngành nghề trong tương lai. 5 CHƯƠNG 1 TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 1.1. Giới thiệu chung Sự phát triển mạnh mẽ của công nghệ thông tin và ngành công nghiệp phần cứng đã làm cho khả năng thu thập và lưu trữ thông tin của các hệ thống thông tin tăng nhanh. Bên cạnh đó việc tin học hoá trong các hoạt động sản xuất, thương mại, khoa học kỹ thuật, y tế, giáo dục … đã tạo ra một lượng dữ liệu lưu trữ khổng lồ. Hàng triệu cơ sở dữ liệu đã được sử dụng, trong đó có nhiều cơ sở dữ liệu cực lớn cỡ Gigabyte, thậm chí là Terabyte. Sự bùng nổ này đã dẫn tới một yêu cầu cấp thiết là cần có những kỹ thuật và công cụ mới để tự động chuyển đổi lượng dữ liệu khổng lồ thành các tri thức có ích. Từ đó, các kỹ thuật khai phá dữ liệu đã trở thành một lĩnh vực thời sự của nền công nghệ thông tin thế giới hiện nay. 1.2. Các khái niệm về khai phá dữ liệu Các hệ thống thông tin có thể lưu trữ một khối lượng lớn dữ liệu về hoạt động hằng ngày của chúng. Từ khối dữ liệu này, các kỹ thuật trong khai phá dữ liệu (KPDL) có thể dùng để trích xuất những thông tin hữu ích mà chúng ta chưa biết. Các tri thức vừa học được có thể vận dụng để cải thiện hiệu quả hoạt động của hệ thống thông tin ban đầu. Giáo sư Tom Mitchell [8] đã đưa ra định nghĩa của KPDL như sau: “KPDL là việc sử dụng dữ liệu lịch sử để khám phá những qui tắc và cải thiện những quyết định trong tương lai.” Với một cách tiếp cận ứng dụng hơn, Tiến sĩ Fayyad [7] đã phát biểu: “KPDL, thường được xem là việc khám phá tri thức trong các cơ sở dữ liệu, là một quá trình trích xuất những thông tin ẩn, trước đây chưa biết và có khả năng hữu ích, dưới dạng các qui luật, ràng buộc, qui tắc trong cơ sở dữ liệu.” KPDL là một bước trong quy trình khám phá tri thức, nhằm: - Rút trích thông tin hữu ích, chưa biết, tiềm ẩn trong khối dữ liệu lớn - Phân tích dữ liệu bán tự động - Giải thích dữ liệu trên các tập dữ liệu 1.3. Tại sao phải khai phá dữ liệu Thông thường chúng ta coi dữ liệu như một dãy các bit, hoặc các số, ký hiệu, hoặc các “đối tượng” với một ý nghĩa nào đó khi được gửi cho một chương trình dưới 6 một dạng nhất định. Chúng ta sử dụng các bit để đo lường các thông tin và xem nó như là các dữ liệu đã được lọc bỏ các dư thừa, được rút gọn tới mức tối thiểu để đặc trưng một cách cơ bản cho dữ liệu. Chúng ta có thể xem tri thức như là các thông tin tích hợp, bao gồm các sự kiện và các mối quan hệ giữa chúng. Các mối quan hệ này có thể được hiểu ra, có thể được phát hiện, hoặc có thể được học. Nói cách khác, tri thức có thể được coi là dữ liệu có độ trừu tượng và tổ chức cao . Kho dữ liệu (Data Warehouse): là tuyển chọn các cơ sở dữ liệu tích hợp, hướng theo các chủ đề nhất định, được thiết kế để hỗ trợ cho chức năng trợ giúp quyết định, mà mỗi đơn vị dữ liệu liên quan đến một khoảng thời gian cụ thể. Kho dữ liệu thường có dung lượng rất lớn, thường là hàng Gigabytes hay có khi tới hàng Terabytes. Kho dữ liệu được xây dựng để tiện lợi cho việc truy cập từ nhiều nguồn, nhiều kiểu dữ liệu khác nhau sao cho có thể kết hợp được cả những ứng dụng của các công nghệ hiện đại và vừa có thể kế thừa được từ các hệ thống đã có từ trước. Dữ liệu được phát sinh từ các hoạt động hàng ngày và được thu thập xử lý để phục vụ công việc nghiệp vụ cụ thể của một tổ chức, vì vậy thường được gọi là dữ liệu tác nghiệp và hoạt động xử lý dữ liệu này gọi là xử lý giao dịch trực tuyến (OLPT - On Line Transaction Processing). Luồng dữ liệu trong một tổ chức được mô tả khái quát như sau: Dữ liệu tác nghiệp Kho dữ liệu cá nhân Kho dữ liệu DỮ LIỆU (Có sẵn) Kho dữ liệu nội bộ Siêu dữ liệu Hình 1.1. Mô tả luồng dữ liệu trong một tổ chức 7 Dữ liệu cá nhân không thuộc phạm vi quản lý của hệ quản trị kho dữ liệu. Nó chứa các thông tin được trích xuất ra từ các hệ thống dữ liệu tác nghiệp, kho dữ liệu và từ những kho dữ liệu nội bộ của những chủ đề liên quan bằng cách phép gộp, tổng hợp hay xử lý theo một cách nào đó. 1.4. Quá trình khai phá tri thức Khai phá dữ liệu được định nghĩa như một quá trình chắt lọc hay khám phá tri thức từ một lượng lớn dữ liệu. Thuật ngữ Data Mining ám chỉ việc tìm một tập nhỏ có giá trị từ một lượng lớn các dữ liệu thô. Có sự phân biệt giữa khái niệm "Khai phá dữ liệu" với khái niệm "Phát hiện tri thức" (Knowledge Discovery in Databases - KDD) mà theo đó, khai phá dữ liệu chỉ là một bước trong quá trình KDD. Quá trình phát hiện tri thức tiến hành qua 6 giai đoạn [4] Hình 1.2. Quá trình phát hiện tri thức Bắt đầu của quá trình là kho dữ liệu thô và kết thúc với tri thức được chiết xuất ra. Quá trình xử lý khai phá dữ liệu bắt đầu bằng cách xác định chính xác vấn đề cần giải quyết. Sau đó sẽ xác định các dữ liệu liên quan dùng để xây dựng giải pháp. Bước tiếp theo là thu thập các dữ liệu có liên quan và xử lý chúng thành dạng sao cho giải thuật khai phá dữ liệu có thể hiểu được. Về lý thuyết thì có vẻ rất đơn giản nhưng thực sự đây là một quá trình rất khó khăn gặp phải rất nhiều vướng mắc như: quản lý các tập dữ liệu, phải lặp đi lặp lại toàn bộ quá trình, v.v. Bước tiếp theo là chọn thuật toán khai phá dữ liệu thích hợp và thực hiện việc khai phá dữ liệu để tìm được các mẫu (pattern) có ý nghĩa dưới dạng biểu diễn tương 8 ứng với các ý nghĩa đó (thường thì được biểu diễn dưới dạng các luật xếp loại, cây quyết định, phát sinh luật, biểu thức hồi quy,…). - Gom dữ liệu: Là việc tập hợp dữ liệu để khai thác từ trong một cơ sở dữ liệu, một kho dữ liệu và thậm chí các dữ liệu từ các nguồn ứng dụng Web. - Trích lọc dữ liệu: Ở giai đoạn này dữ liệu được lựa chọn và phân chia theo một số tiêu chuẩn nào đó nhằm phục vụ mục đích khai thác. - Làm sạch, tiền xử lý dữ liệu: Giai đoạn này là một bước rất quan trọng trong quá trình khai phá dữ liệu. Cần làm sạch, loại bỏ các dữ liệu không đầy đủ, chặt chẽ, logic và các dữ liệu chứa giá trị vô nghĩa vì dữ liệu này nếu không được “làm sạch, tiền xử lý” thì sẽ cho ra các kết quả sai lệch nghiêm trọng. Giai đoạn này sẽ tiến hành xử lý những dạng dữ liệu không chặt chẽ nói trên. - Chuyển đổi dữ liệu: Dữ liệu được chuyển đổi hay được hợp nhất về dạng thích hợp cho việc khai phá, dữ liệu đưa ra có thể sử dụng và điều khiển được, dữ liệu sẽ được chuyển đổi về dạng phù hợp cho việc khai. - Khai phá dữ liệu: Ở giai đoạn này nhiều thuật toán khác nhau sẽ được sử dụng để trích ra các mẫu từ dữ liệu. Đây là một tiến trình cốt yếu trong đó các phương pháp thông minh được áp dụng nhằm trích rút ra mẫu dữ liệu, là bước mang tính tư duy trong khai phá dữ liệu. - Đánh giá các luật và biểu diễn tri thức: Ở giai đoạn này các kỹ thuật biểu diễn và hiển thị được sử dụng để đưa tri thức lấy ra cho người dùng. Các mẫu dữ liệu được chiết xuất ra bởi phần mềm khai phá dữ liệu. Do đó không phải bất cứ mẫu dữ liệu nào cũng đều có ý nghĩa. Vì vậy, cần phải đánh giá để chiết xuất ra các tri thức (Knowlege). Đánh giá sự hữu ích của các mẫu biểu diễn tri thức dựa trên một số phép đo. Sau đó sử dụng các kỹ thuật trình diễn và trực quan hoá dữ liệu để biểu diễn tri thức khai phá được cho người sử dụng. 1.5. Các kỹ thuật khai phá dữ liệu Hai mục đích chính của khai phá dữ liệu trong thực tế là dự đoán và mô tả a. Khai phá dữ liệu dự đoán Nhiệm vụ của khai phá dữ liệu dự đoán là đưa ra các dự đoán dựa vào các suy diễn trên dữ liệu hiện thời. Nó sử dụng các biến hay các trường trong cơ sở dữ liệu để 9 dự đoán các giá trị không biết hay các giá trị tương lai. Bao gồm các kĩ thuật: phân loại (classification), hồi quy (regression) ... Phân loại Mục tiêu của phương pháp phân loại dữ liệu là dự đoán nhãn lớp cho các mẫu dữ liệu. Quá trình phân loại dữ liệu thường gồm 2 bước: xây dựng mô hình và sử dụng mô hình để phân loại dữ liệu. • Bước 1: Xây dựng mô hình dựa trên việc phân tích các mẫu dữ liệu cho trước. Mỗi mẫu thuộc về một lớp, được xác định bởi một thuộc tính gọi là thuộc tính lớp. Các mẫu dữ liệu này còn được gọi là tập dữ liệu huấn luyện. Các nhãn lớp của tập dữ liệu huấn luyện đều phải được xác định trước khi xây dựng mô hình, vì vậy phương pháp này còn được gọi là học có giám sát. • Bước 2: Sử dụng mô hình để phân loại dữ liệu. Trước hết chúng ta phải tính độ chính xác của mô hình. Nếu độ chính xác là chấp nhận được, mô hình sẽ được sử dụng để dự đoán nhãn lớp cho các mẫu dữ liệu khác trong tương lai. Hồi quy Phương pháp hồi qui khác với phân loại dữ liệu ở chỗ, hồi qui dùng để dự đoán về các giá trị liên tục còn phân loại dữ liệu thì chỉ dùng để dự đoán về các giá trị rời rạc. Hồi quy là học một hàm ánh xạ một mục dữ liệu vào một biến dự báo giá trị thực. Các ứng dụng hồi quy có nhiều, ví dụ như đánh giá xác xuất một bệnh nhân sẽ chết dựa trên tập kết quả xét nghiệm chuẩn đoán, dự báo nhu cầu của người tiêu dùng đối với một sản phẩm mới dựa trên hoạt động quảng cáo tiêu dùng. b. Khai phá dữ liệu mô tả Kỹ thuật này có nhiệm vụ mô tả về các tính chất hoặc các đặc tính chung của dữ liệu trong CSDL hiện có. Bao gồm các kỹ thuật: phân cụm (clustering), phân tích luật kết hợp (association rules)... Phân cụm Mục tiêu chính của phương pháp phân cụm dữ liệu là nhóm các đối tượng tương tự nhau trong tập dữ liệu vào các cụm sao cho các đối tượng thuộc cùng một cụm là tương đồng còn các đối tượng thuộc các cụm khác nhau sẽ không tương đồng. 10 Phân cụm dữ liệu là một ví dụ của phương pháp học không giám sát. Không giống như phân loại dữ liệu, phân cụm dữ liệu không đòi hỏi phải định nghĩa trước các mẫu dữ liệu huấn luyện. Vì thế, có thể coi phân cụm dữ liệu là một cách học bằng quan sát (learning by observation), trong khi phân loại dữ liệu là học bằng ví dụ (learning by example).Trong phương pháp này bạn sẽ không thể biết kết quả các cụm thu được sẽ như thế nào khi bắt đầu quá trình. Vì vậy, thông thường cần có một chuyên gia về lĩnh vực đó để đánh giá các cụm thu được. Phân cụm dữ liệu được sử dụng nhiều trong các ứng dụng về phân đoạn thị trường, phân đoạn khách hàng, nhận dạng mẫu, phân loại trang Web... Ngoài ra phân cụm dữ liệu còn có thể được sử dụng như một bước tiền xử lí cho các thuật toán khai phá dữ liệu khác. Luật kết hợp Mục tiêu của phương pháp này là phát hiện và đưa ra các mối liên hệ giữa các giá trị dữ liệu trong CSDL. Mẫu đầu ra của giải thuật khai phá dữ liệu là tập luật kết hợp tìm được. Khai phá luật kết hợp được thực hiện qua 2 bước; Bước 1 ; tìm tất cả các tập mục phổ biến, một tập mục phổ biến được xác định qua tính độ hỗ trợ và thỏa mãn độ hỗ trợ cực tiểu. Bước 2; sinh ra các luật kết hợp mạnh từ tập mục phổ biến, các luật phải thỏa mãn độ hỗ trợ cực tiểu và độ tin cậy cực tiểu. Phương pháp này được sử dụng rất hiệu quả trong các lĩnh vực như marketing có chủ đích, phân tích quyết định, quản lí kinh doanh,.. 1.6. Những thách thức trong ứng dụng và nghiên cứu trong kỹ thuật khai phá dữ liệu Ở đây, ta đưa ra một số khó khăn trong việc nghiên cứu và ứng dụng kỹ thuật khai phá dữ liệu. Tuy nhiên, thế không có nghĩa là việc giải quyết là hoàn toàn bế tắc mà chỉ muốn nêu lên rằng để khai phá được dữ liệu không phải đơn giản, mà phải xem xét cũng như tìm cách giải quyết những vấn đề này. Ta có thể liệt kê một số khó khăn như sau: Các vấn đề về cơ sở dữ liệu Đầu vào chủ yếu của một hệ thống khai thác tri thức là các dữ liệu thô trong cơ sở. Phát sinh trong khai phá dữ liệu chính là từ đây, do các dữ liệu trong thực tế thường động, không đầy đủ, lớn và bị nhiễu. Trong những trường hợp khác, người ta 11 không biết cơ sở dữ liệu có chứa các thông tin cần thiết cho việc khai thác hay không và làm thế nào để giải quyết với sự dư thừa những thông tin không thích hợp này. Dữ liệu lớn: Cho đến nay, các cơ sở dữ liệu với hàng trăm trường và bảng, hàng triệu bản ghi và với kích thước đến gigabytes đã là chuyện bình thường. Hiện nay đã bắt đầu xuất hiện các cơ sở dữ liệu có kích thước tới terabytes. Các phương pháp giải quyết hiện nay là đưa ra một ngưỡng cho cơ sở dữ liệu, lấy mẫu, các phương pháp xấp xỉ, xử lý song song (Agrawal et al, Holsheimer et al). Kích thước lớn: không chỉ có số lượng bản ghi lớn mà số các trường trong cơ sở dữ liệu cũng nhiều. Vì vậy mà kích thước của bài toán trở nên lớn hơn. Một tập dữ liệu có kích thước lớn sinh ra vấn đề làm tăng không gian tìm kiếm mô hình suy diễn. Hơn nữa, nó cũng làm tăng khả năng một giải thuật khai phá dữ liệu có thể tìm thấy các mẫu giả. Biện pháp khắc phục là làm giảm kích thước tác động của bài toán và sử dụng các tri thức biết trước để xác định các biến không phù hợp. Dữ liệu động: Đặc điểm cơ bản của hầu hết các cơ sở dữ liệu là nội dung của chúng thay đổi liên tục. Dữ liệu có thể thay đổi theo thời gian và việc khai phá dữ liệu cũng bị ảnh hưởng bởi thời điểm quan sát dữ liệu. Ví dụ trong cơ sở dữ liệu về tình trạng bệnh nhân, một số giá trị dữ liệu là hằng số, một số khác lại thay đổi liên tục theo thời gian (ví dụ cân nặng và chiều cao), một số khác lại thay đổi tùy thuộc vào tình huống và chỉ có giá trị được quan sát mới nhất là đủ (ví dụ nhịp đập của mạch). Vậy thay đổi dữ liệu nhanh chóng có thể làm cho các mẫu khai thác được trước đó mất giá trị. Hơn nữa, các biến trong cơ sở dữ liệu của ứng dụng đã cho cũng có thể bị thay đổi, bị xóa hoặc là tăng lên theo thời gian. Vấn đề này được giải quyết bằng các giải pháp tăng trưởng để nâng cấp các mẫu và coi những thay đổi như là cơ hội để khai thác bằng cách sử dụng nó để tìm kiếm các mẫu bị thay đổi. Các trường không phù hợp: Một đặc điểm quan trọng khác là tính không thích hợp của dữ liệu, nghĩa là mục dữ liệu trở thành không thích hợp với trọng tâm hiện tại của việc khai thác. Các giá trị bị thiếu: Sự có mặt hay vắng mặt của giá trị các thuộc tính dữ liệu phù hợp có thể ảnh hưởng đến việc khai phá dữ liệu. Trong hệ thống tương tác, sự thiếu vắng dữ liệu quan trọng có thể dẫn đến việc yêu cầu cho giá trị của nó hoặc kiểm tra để xác định giá trị của nó. 12 Các trường bị thiếu: Một quan sát không đầy đủ cơ sở dữ liệu có thể làm cho các dữ liệu có giá trị bị xem như có lỗi. Việc quan sát cơ sở dữ liệu phải phát hiện được toàn bộ các thuộc tính có thể dùng để giải thuật khai phá dữ liệu có thể áp dụng nhằm giải quyết bài toán. Giả sử ta có các thuộc tính để phân biệt các tình huống đáng quan tâm. Nếu chúng không làm được điều đó thì có nghĩa là đã có lỗi trong dữ liệu. Độ nhiễu và không chắc chắn: Đối với các thuộc tính đã thích hợp, thì lỗi phụ thuộc vào kiểu dữ liệu của các giá trị cho phép. Các giá trị của các thuộc tính khác nhau có thể là các số thực, số nguyên, chuỗi và có thể thuộc vào tập các giá trị định danh. Các giá trị định danh này có thể sắp xếp theo thứ tự từng phần hoặc đầy đủ, thậm chí có thể có cấu trúc ngữ nghĩa. Mối quan hệ phức tạp giữa các trường: các thuộc tính hoặc các giá trị có cấu trúc phân cấp, các mối quan hệ giữa các thuộc tính để diễn tả tri thức về nội dung của cơ sở dữ liệu yêu cầu các giải thuật phải có khả năng sử dụng một cách hiệu quả các thông tin này. Ban đầu, kỹ thuật khai phá dữ liệu chỉ được phát triển cho các bản ghi có giá trị thuộc tính đơn giản. Tuy nhiên, ngày nay người ta đang tìm cách phát triển các kỹ thuật nhằm rút ra mối quan hệ giữa các biến này. Một số vấn đề khác “Quá phù hợp” (Overfitting): một giải thuật tìm kiếm các tham số tốt nhất cho sử dụng một tập dữ liệu hữu hạn, nó có thể sẽ bị tình trạng “quá độ” dữ liệu (nghĩa là tìm kiếm quá mức cần thiết gây ra hiện tượng chỉ phù hợp với các dữ liệu đó mà không có khả năng đáp ứng cho các dữ liệu lạ), làm cho mô hình hoạt động rất kém đối với các dữ liệu thử. Các giải pháp khắc phục bao gồm đánh giá chéo (crossvalidation), thực hiện theo nguyên tắc nào đó hoặc sử dụng các biện pháp thống kê khác. Sự tương tác với người sử dụng và các tri thức sẵn có: rất nhiều công cụ và phương pháp khai phá dữ liệu không thực sự tương tác với người dùng và không dễ dàng kết hợp cùng với các tri thức đã biết trước đó. Việc sử dụng tri thức miền là rất quan trọng trong khai phá dữ liệu. Đã có nhiều biện pháp nhằm khắc phục vấn đề này như sử dụng cơ sở dữ liệu suy diễn để phát hiện tri thức, những tri thức này sau đó được sử dụng để hướng dẫn cho việc tìm kiếm khai phá dữ liệu hoặc sử dụng sự phân bố và xác suất dữ liệu trước đó như một dạng mã hóa tri thức có sẵn.