Tài liệu ứng dụng kỹ thuật khai phá dữ liệu để tư vấn học tập cho sinh viên tại trường đại học quảng bình

MỤC LỤC TRANG BÌA LỜI CAM ĐOAN TRANG TÓM TẮT LUẬN VĂN MỤC LỤC DANH MỤC CÁC THUẬT NGỮ, CHỮ VIẾT TẮT DANH MỤC BẢNG DANH MỤC CÁC H NH MỞ ĐẦU ......................................................................................................................... 1 1. Lý do chọn đề tài. ............................................................................................... 1 2. Tính cấp thiết của đề tài ...................................................................................... 2 3. Mục tiêu đề tài .................................................................................................... 2 . Nội dung nghiên c u........................................................................................... 3 5. Đối tượng và phạm vi nghiên c u ...................................................................... 3 . hư ng ph p nghiên c u .................................................................................... 3 7. Ý nghĩa khoa học, tính khả thi của đề tài ........................................................... 3 8. Bố cục của luận văn ............................................................................................ 3 CHƯƠNG 1. TỔNG QUAN KHAI HÁ DỮ LIỆU ..................................................... 5 1.1. Giới thiệu .............................................................................................................. 5 1.2. C c ng dụng của khai ph dữ liệu ...................................................................... 5 1.3. C c bước của qu trình khai ph dữ liệu .............................................................. 6 1.4. C c phư ng ph p trong khai phá dữ liệu ............................................................. 7 1.4.1. hân lớp (classification) ................................................................................ 7 1.4.2. Hồi qui (regression) ....................................................................................... 8 1.4.3. Phân nhóm (clustering).................................................................................. 8 1.4.4. Tổng hợp (summarization) ............................................................................ 8 1.4.5. Mô hình ho sự phụ thuộc (dependency modeling) ...................................... 8 1.4.6. h t hiện sự biến đổi và độ lệch (change and deviation dectection) ............. 9 1.5. C c Kỹ thuật khai ph dữ liệu .............................................................................. 9 1.5.1. C c thành phần của qu trình khai ph dữ liệu ........................................... 10 1.5.2. Kỹ thuật suy diễn/quy nạp ........................................................................... 11 1.5.3. Kỹ thuật ng dụng K-l ng giềng gần .......................................................... 12 1.5.4. Kỹ thuật sử dụng cây quyết định và luật ..................................................... 12 1.5.5. Kỹ thuật ph t hiện luật kết hợp ................................................................... 13 1.6. Những th ch th c trong nghiên c u và ng dụng kỹ thuật khai ph dữ liệu ..... 14 1.7. Một số vấn đề th ch th c của khai ph dữ liệu .................................................. 16 CHƯƠNG 2: NGHIÊN CỨU MẠNG NƠRON NHÂN TẠO VÀ XÂY DỰNG MÔ H NH DỰA TRÊN MẠNG NƠRON ........................................................................... 18 2.1. Giới thiệu về mạng n ron nhân tạo .................................................................... 18 2.1.1. Kh i niệm .................................................................................................... 18 2.1.2. Lịch sử ph t triển của mạng n ron nhân tạo ............................................... 18 2.2. Mạng n ron nhân tạo .......................................................................................... 20 2.2.1. Mô hình mạng n ron nhân tạo .................................................................... 20 2.2.2. hân loại cấu trúc mạng n ron nhân tạo ..................................................... 22 2.3. C c hình th c học của mạng n ron nhân tạo ..................................................... 26 2.3.1. Kh i niệm .................................................................................................... 26 2.3.2. Học có giám sát ........................................................................................... 26 2.3.3. Học không có gi m s t ................................................................................ 28 2.3.4. Học tăng cường............................................................................................ 28 2.4. Một số phư ng ph p huấn luyện mạng n ron nhân tạo: .................................... 32 2.5. Mô tả bài to n đào tạo tại Trường Đại học Quảng Bình .................................... 33 2.6. Áp dụng mô hình để tư vấn chọn môn học tự chọn CCNN dựa trên ANN ....... 35 2.7. Phân tích bài toán ............................................................................................... 38 2.8. Áp dụng mô hình để tư vấn môn tự chọn cho sinh viên Đại học Quảng Bình .. 41 2.9. Huấn luyện mô hình bằng thuật to n lan truyền ngược ..................................... 42 2.10. Kết luận............................................................................................................. 43 CHƯƠNG 3. HÁT TRIỂN ỨNG DỤNG .................................................................. 44 3.1. Thiết kế hệ thống ................................................................................................ 44 3.1.1. Ch c năng Quản lý User ............................................................................. 44 3.1.2. Ch c năng xây dựng tập dữ liệu .................................................................. 47 3.1.3. Ch c năng dự b o kết quả ........................................................................... 49 3.2. Công nghệ ng dụng trong đề tài ....................................................................... 51 3.3. Chư ng trình thực nghiệm và kết quả ................................................................ 52 3.3.1. Môi trường cài đặt ........................................................................................... 52 3.3.2. Cấu trúc tập tin ................................................................................................ 52 3.3.3. Một số giao diện chính của hệ thống ............................................................... 52 3.3.4. Kết quả thực nghiệm........................................................................................ 56 KẾT LUẬN VÀ HƯỚNG HÁT TRIỂN .................................................................... 59 TÀI LIỆU THAM KHẢO ............................................................................................. 61 QUYẾT Đ NH GIAO Đ TÀI LUẬN VĂN THẠC (BẢN AO) BẢN AO KẾT LUẬN CỦA HỘI ĐỒNG, BẢN AO NHẬN XÉT CỦA CÁC HẢN BIỆN. TRANG TÓM TẮT LUẬN VĂN ỨNG DỤNG KỸ THUẬT KHAI PHÁ DỮ LIỆU ĐỂ TƯ VẤN HỌC TẬP CHO SINH VIÊN TẠI TRƯỜNG ĐẠI HỌC QUẢNG BÌNH Học viên: Lê Quốc Hoàng Chuyên ngành: Khoa học m y tính Mã số: 0. 8.01.01 Khóa: 3 Trường Đại học B ch khoa - ĐHĐN Tóm tắt - Trong học chế tín ch , qu trình chọn môn học tự chọn của sinh viên được xem là một hệ thống với nhiều đầu vào và một đầu ra, trong đó c c kết quả điểm tổng kết t ng môn học trong qu kh là đầu vào và kết quả điểm tổng kết của môn tự chọn là đầu ra. Để giải quyết bài to n, luận văn tập trung vào nghiên c u tổng quan về khai ph dữ liệu cụ thể là c c phư ng ph p, kỹ thuật trong khai ph dữ liệu và ng dụng của khai ph dữ liệu, lựa chọn phư ng ph p để ng dụng cho đề tài. T những nghiên c u về khai ph dữ liệu t c giả đi sâu vào tìm hiểu thuật to n mạng n ron nhân tạo nhiều lớp, c c hình th c học và phư ng ph p huấn luyện mạng n ron nhân tạo với giải thuật học lan truyền ngược có thể p dụng vào thực hiện ch c năng tư vấn môn tự chọn cho sinh viên dựa vào kết quả học tập c c k trước đó. Và t đó tư vấn cho giảng viên, cố vấn học tập có thể chọn cho sinh viên hoặc sinh viên tự chọn cho mình môn tư chọn đạt kết quả cao nhất t đó chọn được học phần tự chọn phù hợp với năng lực sinh viên. Từ khóa – mạng n ron nhân tạo; khai ph dữ liệu; lan truyền ngược; tư vấn học tập; dự b o kết quả. APPLICATION OF DATA MINING TECHINQUE TO RECOMMEND SUBJECTS FOR STUDENT AT QUANGBINH UNIVERSITY Abstract - In the course credit, students’ seclecting an optional course is considered as a system with multiple inputs and one output, in which the results of the final credits of each subject in the past are inputs and the final scores of the optional course are outputs. To address the issue, the thesis focuses on studying data mining overview, namely methods, techniques in data mining and application of data mining, and selecting the method to apply for topic. From the previous studies, the author emphasizes on getting a deep insight in data mining to the study of artificial neural network multiplicity algorithms, learning methods and methods of artificial neural network training with backpropagation algorithm that could be possibly applied to the reality. It is a function of counseling electives for students based on the results of previous studies. From then on, faculty advisors, learning adviser students can choose their own electives to achieve the highest results, thereby selecting the appropriate electives for the students. Key words - artificial neural networks; Data mining; back propagation; academic counseling; Forecast results. DANH MỤC CÁC THUẬT NGỮ, CHỮ VIẾT TẮT T viết t t Ý nghĩa ANN Mạng n ron nhân tạo CCNN Mô hình thuật to n CSDL C s dữ liệu SQL Ngôn ngữ truy vấn QL CVHT Cố vấn học tập SV Sinh viên DANH MỤC BẢNG Bảng 2.1. Chư ng trình đào tạo học k 1 ......................................................................33 Bảng 2.2. Học phần tự chọn trong học k tiếp theo ......................................................34 Bảng 2.3. Dữ liệu điểm môn tự chọn văn học. ..............................................................36 Bảng 2. . Dữ liệu điểm môn tự chọn mỹ học. ..............................................................36 Bảng 2.5. Dữ liệu điểm môn tự chọn gi o dục dân số và môi trường. .........................37 Bảng 2. . Dữ liệu điểm của sinh cần tư vấn ..................................................................38 Bảng 2.7. Học phần b t buộc học k 1 của ngành gi o dục mầm non ..........................38 Bảng 2.8. Bảng tổng hợp kết quả học k 1 của sinh viên .............................................39 Bảng 2.9. Học phần b t buộc học k 2 ..........................................................................40 Bảng 2.10. Nhóm học phần tự chọn ..............................................................................40 Bảng 3.1. Kịch bản “Quản lý User” ..............................................................................45 Bảng 3.2. Kịch bản “xây dựng tập dữ liệu” ..................................................................47 Bảng 3.3. Kịch bản “dự b o kết quả” ...........................................................................49 DANH MỤC CÁC HÌNH Hình 1.1. Quy trình ph t hiện tri th c ............................................................................6 Hình 2.1. Mô hình mạng n ron nhân tạo . ....................................................................21 Hình 2.2. Hàm dạng dấu ................................................................................................22 Hình 2.3. Hàm bước nhị phân .......................................................................................23 Hình 2.4. Hàm sigmoid .................................................................................................23 Hình 2.5. Mạng n ron truyền thẳng nhiều lớp. .............................................................24 Hình 2. . Mạng hồi qui..................................................................................................25 Hình 2.7. Mô hình dự b o kết quả học phần CCNN .....................................................37 Hình 2.8. Mô hình dự b o chọn môn tự chọn ...............................................................42 Hình 3.1. Mô hình use case tổng qu t ...........................................................................44 Hình 3.2. Biểu đồ tuần tự của ch c năng Quản lý user .................................................46 Hình 3.3. Biểu đồ tuần tự của cộng t c Quản lý user ....................................................47 Hình 3. . Biểu đồ tuần tự của ch c năng xử lý dữ liệu .................................................48 Hình 3.5. Biểu đồ cộng t c của ch c năng xây dựng tập dữ liệu ..................................49 Hình 3. . Biểu đồ tuần tự của ch c năng dự b o. .........................................................50 Hình 3.7. Biểu đồ cộng t c của ch c năng dự b o ........................................................51 Hình 3.8. Màn hình chính ..............................................................................................53 Hình 3.9. Ch c năng xử lý dữ liệu ................................................................................53 Hình 3.10. Thông số mạng ............................................................................................54 Hình 3.11. Huấn luyện mạng .........................................................................................54 Hình 3.12. Kiểm thử dữ liệu ..........................................................................................55 Hình 3.13. Dự b o cho sinh viên ...................................................................................55 Hình 3.1 . Dự b o giảng viên/chuyên viên/cố vấn học tập ..........................................56 1 MỞ ĐẦU 1. Lý do chọn đề tài. Trong những năm gần đây, khi công nghệ thông tin đang ngày càng ph t triển mạnh mẽ thì vấn đề khai ph dữ liệu đã và đang tr thành một trong những hướng nghiên c u chính trong lĩnh vực khoa học m y tính và công nghệ tri th c. Khai ph dữ liệu được ng dụng thành công vào rất nhiều c c lĩnh vực kh c nhau như thư ng mại, tài chính, thị trường ch ng kho n, y học, sinh học, gi o dục và viễn thông,... Hình th c đào tạo tín ch là một phư ng ph p đào tạo tiên tiến trên thế giới và đang được p dụng rộng rãi tại một số trường đại học của Việt Nam hiện nay. Ưu điểm của hình th c đào tạo này là tính liên thông giữa c c hệ đào tạo, giữa c c trường để tạo điều kiện cho việc hội nhập với gi o dục thế giới. Vì lý do đó mà chủ trư ng của nhà nước là m rộng p dụng hình th c đào tạo tín ch trong mạng lưới c c trường đại học, cao đẳng trong nước giai đoạn 2001- 2010. Trường Đại học Quảng Bình đã p dụng hình th c học theo tín ch t năm học 2008 đến nay. Theo tinh thần của học chế tín ch sinh viên có thể tự xây dựng kế hoạch học tập cho cả qu trình học của mình suốt khóa học. Có nghĩa là tùy theo năng lực và điều kiện của bản thân sinh viên sẽ đăng ký học phần nhiều hay ít trong mỗi học k nhưng vẫn đảm bảo đúng thời hạn đào tạo theo qui định của Nhà trường. Nhưng thực trạng hiện nay là hầu hết sinh viên vẫn đăng ký học phần theo kế hoạch đào tạo của chư ng trình khung theo học k mà chưa có một sự định hình riêng con đường học tập của bản thân. Trường hợp những sinh viên giỏi có thể đăng ký để đẩy nhanh tiến độ học tập và rút ng n thời gian đào tạo mà vẫn đảm bảo kết quả học tập tốt, phù hợp với điều kiện thời gian và năng lực. Trường hợp những sinh viên có năng lực yếu h n có thể đăng ký dàn trải h n sao cho kết quả học tập được giữ m c tốt nhưng vẫn tuân thủ thời gian đào tạo tại trường. Việc tự xây dựng một lộ trình tối ưu phù hợp với năng lực học tập của t ng sinh viên theo tinh thần học chế tín ch hầu như vẫn chưa thể hiện được tính hiệu quả của nó. Do đó việc xây dựng một công cụ hỗ trợ đề xuất cho sinh viên c c lộ trình học tập phù hợp theo năng lực và điều kiện thời gian trong suốt khóa học là một nhu cầu cần thiết và h a hẹn sẽ là công cụ đ c lực giúp cho sinh 2 viên quản lý kế hoạch học tập một c ch hiệu quả để chủ động h n trong việc chuẩn bị hành trang cho tư ng lai của mình. Trước những th ch th c đặt ra về khai ph dữ liệu, để hỗ trợ tốt nhất cho sinh viên và tăng cường ng dụng công nghệ thông tin trong hoạt động và quản lý đào tạo nhằm tăng hiệu quả và nâng cao chất lượng đào tạo tại Trường Đại học Quảng Bình thì việc xây dựng c c hệ thống phục vụ sinh viên là rất cần thiết. Vì vậy tôi quyết định lựa chọn chọn đề tài “Ứng dụng kỹ thuật khai ph dữ liệu để tư vấn học tập cho sinh viên tại Trường Đại học Quảng Bình” làm đề tài tốt nghiệp luận văn cao học. 2. Tính cấp thiết của đề tài Với thực trạng đã nêu trên, việc xây dựng một công cụ hỗ trợ đề xuất cho sinh viên c c lộ trình học tập phù hợp theo năng lực và điều kiện thời gian trong suốt khóa học là một nhu cầu cần thiết và h a hẹn sẽ là công cụ đ c lực giúp cho sinh viên quản lý kế hoạch học tập một c ch hiệu quả, chủ động h n trong việc chuẩn bị hành trang cho tư ng lai của mình. Đối với hình th c đào tạo tín ch sinh viên phải đăng ký học phần b t buộc và tự chọn dưới sự tư vấn của CVHT. Vậy làm sao để đảm bảo sinh viên chọn được những học phần phù hợp với năng lực bản thân và s p xếp lộ trình học sao cho đạt hiệu quả nhất ? Liệu CVHT có thể tư vấn cho sinh viên cả lớp chọn kế hoạch học tập phù hợp trong khi không thể tiếp cận toàn bộ dữ liệu điểm của sinh viên? Để giải quyết c c vấn đề nêu trên, chúng tôi tiến hành nghiên c u thực hiện đề tài Ứng dụng kỹ thuật khai ph dữ liệu để tư vấn học tập cho sinh viên tại Trường Đại học Quảng Bình. 3. Mục tiêu đề tài - Hiểu được c c vấn đề liên quan đến khai ph dữ liệu. - Nghiên c u lý thuyết mạng n ron. - Áp dụng thuật to n mạng n ron để xây dựng ng dụng tư vấn chọn môn học tự chọn cho sinh viên. - Hỗ trợ phòng Đào tạo, c c Khoa chuyên ngành và c c CVHT, gi o viên chủ nhiệm có thể tư vấn cho sinh viên trong việc chọn học phần. - Nâng cao chất lượng đào tạo tại Trường Đại học Quảng Bình. 3 4. N i dung nghiên c u - Nghiên c u lý thuyết về kỹ thuật ph t hiện tri th c và khai ph dữ liệu. - Chuẩn bị nguồn dữ liệu, bao gồm dữ liệu điểm kết quả học tập của sinh viên. - Cài đặt thử nghiệm mô hình khai ph dữ liệu: Mạng n ron nhân tạo (Neural Network). - Áp dụng mô hình để giải quyết bài to n. 5. Đối tượng và phạm vi nghiên c u - Đối tượng nghiên c u của đề tài là khai ph dữ liệu điểm sinh viên, thuật to n mạng n ron nhân tạo và lan truyền ngược. - Trong khuôn khổ của một luận văn, tôi ch giới hạn thực nghiệm tạo ng dụng tư vấn môn học tự chọn cho sinh viên ngành Gi o dục mầm non – Khoa ư phạm Tiểu học Mầm non - Trường Đại học Quảng Bình. 6. Phương pháp nghiên c u - Thu thập, đọc hiểu, phân tích thông tin, dữ liệu t c c tài liệu, gi o trình, s ch liên quan đến khai ph dữ liệu. - Tiến hành nghiên c u và p dụng thuật to n mạng n ron để xây dựng ng dụng tư vấn học phần tự chọn cho sinh viên tại Trường Đại học Quảng Bình phù hợp nhất. 7. Ý nghĩa khoa học, tính khả thi của đề tài Trường Đại học Quảng Bình đang thực hiện việc ng dụng công nghệ thông tin vào công t c dạy và học rất tốt. Việc xây dựng ng dụng tự vấn môn tự chọn sẽ hỗ trợ cho sinh viên trong việc lựa chọn phư ng ph p học và môn học để đạt kết quả tốt trong c c học k kế tiếp. Ý tư ng xuất ph t t nhu cầu thực tế của Nhà trường nên đề tài mang tính ng dụng cao, thiết thực hỗ trợ nâng cao hoạt đào tạo của nhà trường. 8. Bố cục của luận văn Ngoài phần m đầu và kết luận, luận văn gồm ba chư ng: 4 Chương 1: Chư ng này chủ yếu nghiên c u tổng quan về khai phá dữ liệu cự thể là c c phư ng ph p, kỹ thuật trong khai phá dữ liệu và ng dụng của khai phá dữ liệu, lựa chọn phư ng ph p để ng dụng cho đề tài. Chương 2: Nghiên c u và đi sâu vào tìm hiểu thuật to n mạng n ron nhân tạo, c c hình th c học và một số phư ng ph p huấn luyện mạng n ron nhân tạo. ng dụng thuật to n lan truyền ngược cho mô hình mạng n ron. Chương 3: Nghiên c u xây dựng ng dụng, trong chư ng này c c nội dung đề cập đến đó là: Mô tả bài to n, đề xuất mô hình p dụng thuật to n lan truyền ngược để xây dựng ng dụng. h t triển xây dựng demo ng dụng thực hiện ch c năng tư vấn học phần cho sinh viên dựa vào kết quả học tập c c k . Và t đó tư vấn cho giảng viên, CVHT có thể chọn cho sinh viên hoặc V tự chọn cho mình môn tư chọn đạt kết quả cao nhất t đó chọn được học phần tự chọn phù hợp nhất với sinh viên. 5 Chương 1: TỔNG QUAN KHAI PHÁ DỮ LIỆU 1.1. Giới thiệu Khai ph dữ liệu được dùng để mô tả qu trình ph t hiện ra tri th c trong C DL. Quá trình này là việc tính to n để tìm ra c c mẫu trong c c bộ dữ liệu liên quan đến c c bộ dữ liệu lớn giúp cho việc dự b o trong m y học, thống kê và c c hệ thống c s dữ liệu. Tùy vào c ch tiếp cận, mục tiêu khai ph dữ liệu mà c c Nhà khoa học đã đưa ra một số định nghĩa như sau [1]: Đị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 C DL 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.2. Các ng dụng của khai phá dữ liệu h t hiện tri th c và khai ph dữ liệu liên quan đến nhiều ngành, nhiều lĩnh vực: dự b o, trí tuệ nhân tạo, c s dữ liệu, thuật to n, tính to n song song và tốc độ cao, thu thập tri th c cho c c hệ chuyên gia, quan s t dữ liệu... Đặc biệt ph t hiện tri th c và khai ph dữ liệu rất gần gũi với lĩnh vực dự b o, sử dụng c c phư ng ph p dự b o để mô hình dữ liệu và ph t hiện c c mẫu, luật ... . Khai ph dữ liệu có nhiều ng dụng trong thực tế, ví dụ như: + Bảo hiểm, tài chính và thị trường ch ng kho n: phân tích tình hình tài chính và dự b o gi của c c loại cổ phiếu trong thị trường ch ng kho n. Danh mục vốn và gi , lãi suất, dữ liệu thẻ tín dụng, ph t hiện gian lận, ... + Dự b o, phân tích dữ liệu và hỗ trợ ra quyết định. + Điều trị y học và chăm sóc y tế: một số thông tin về chuẩn đo n bệnh lưu trong c c hệ thống quản lý bệnh viện. hân tích mối liên hệ giữa c c triệu ch ng bệnh, chuẩn đo n và phư ng ph p điều trị (chế độ dinh dưỡng,...) 6 + ản xuất và chế biến: Quy trình, phư ng ph p chế biến và xử lý sự cố. + Khai phá văn bản và khai ph Web: hân lớp văn bản và c c trang Web, tóm t t văn bản,... + Lĩnh vực khoa học: Quan s t thiên văn, dữ liệu gene, dữ liệu sinh vật học, tìm kiếm, so s nh c c hệ gene và thông tin di truyền, mối liên hệ gene và một số bệnh di truyền, ... Mạng viễn thông: hân tích c c cuộc gọi điện thoại và hệ thống gi m s t lỗi, sự cố, chất lượng dịch vụ, ... 1.3. Các bước của quá trình khai phá dữ liệu Quy trình khai ph dữ liệu thường tuân theo c c bước sau:[2] Hình 1.1. Quy trình phát hiện tri thức [2] Bước 1: Hình thành, xác định và định nghĩa bài toán. Là 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 và bản chất của dữ liệu. 7 Bước 2: Thu thập và tiền xử lý dữ liệu. Là thu thập và xử lý thô, còn được gọi là tiền xử lý dữ liệu nhằm loại bỏ nhiễu (làm sạch dữ liệu), xử lý việc thiếu dữ liệu (làm giàu 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 trong toàn bộ qui trình ph t hiện tri th c. Do dữ liệu được lấy t nhiều nguồn kh c nhau, không đồng nhất, … có thể gây ra c c nhầm lẫn. au bước này, dữ liệu sẽ nhất qu n, đầy đủ, được rút gọn và rời rạc ho . Bước 3: Khai phá dữ liệu, rút ra các tri thức. Là khai ph dữ liệu, hay nói c ch kh c là trích ra c c mẫu hoặc/và c c mô hình ẩn dưới c c dữ liệu. 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 của khai ph dữ liệu, dùng phư ng ph p khai ph nào? Thông thường, c c bài to n khai ph dữ liệu bao gồm: c c bài to n mang tính mô tả - đưa ra tính chất chung nhất của dữ liệu, c c bài to n dự b o – bao gồm cả việc ph t hiện c c suy diễn dựa trên dữ liệu hiện có. Tu theo bài to n x c định được mà ta lựa chọn c c phư ng ph p khai ph dữ liệu cho phù hợp. Bước 4: Sử dụng các tri thức phát hiện được. Là hiểu 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 trung bình trên tất cả c c lần thực hiện. C c kết quả của qu trình ph t hiện tri th c có thể được đưa và ng dụng trong c c lĩnh vực kh c nhau. Do c c kết quả có thể là c c dự đo n hoặc c c mô tả nên chúng có thể được đưa vào c c hệ thống hỗ trợ ra quyết định nhằm tự động hoá quá trình này. 1.4. Các phương pháp trong khai phá dữ liệu Qu trình khai ph dữ liệu là qu trình ph t hiện ra mẫu thông tin. Trong đó, giải thuật khai ph tìm kiếm c c mẫu đ ng quan tâm theo dạng x c định như c c luật, phân lớp, hồi quy, cây quyết định, ... 1.4.1. Phân lớp (classification) Là việc x c định một hàm nh xạ t một mẫu dữ liệu vào một trong số c c lớp đã được biết trước đó. Mục tiêu của thuật to n phân lớp là tìm ra mối liên kết giữa thuộc tính dự b o và thuộc tính phân lớp. Như thế qu trình phân lớp có thể sử dụng mối liên kết này để dự b o cho c c mục mới. C c kiến th c được ph t hiện biểu diễn dưới dạng 8 c c luật theo c ch sau: “Nếu các thuộc tính dự báo của một mục thoả mãn điều kiện của các tiền đề thì mục nằm trong lớp chỉ ra trong kết luận” [5]. 1.4.2. Hồi qui (regression) Là việc học một hàm nh xạ t một mẫu dữ liệu thành một biến dự đo n có gi trị thực. Nhiệm vụ của hồi quy tư ng tự như phân lớp, ch kh c chỗ thuộc tính để dự b o là liên tục ch không phải rời rạc [5]. Việc dự b o c c gi trị số thường được làm b i c c phư ng ph p thống kê cổ điển, chẳng hạn như hồi quy tuyến tính. Tuy nhiên, phư ng ph p mô hình ho cũng được sử dụng, ví dụ: cây quyết định. 1.4.3. Phân nhóm (clustering) Là việc mô tả chung để tìm ra c c tập hay c c nhóm, loại mô tả dữ liệu. C c nhóm có thể t ch nhau hoặc phân cấp hay gối lên nhau. Có nghĩa là dữ liệu có thể v a thuộc nhóm này lại v a thuộc nhóm kh c. C c ng dụng khai ph dữ liệu có nhiệm vụ phân nhóm như ph t hiện tập c c kh ch hàng có phản ng giống nhau trong C DL tiếp thị; x c định c c quang phổ t c c phư ng ph p đo tia hồng ngoại, … Liên quan chặt chẽ đến việc phân nhóm là nhiệm vụ đ nh gi dữ liệu, hàm mật độ x c suất đa biến/ c c trường trong CSDL [5, 6]. 1.4.4. Tổng hợp (summarization) Là công việc liên quan đến c c phư ng ph p tìm kiếm một mô tả tập con dữ liệu. Kỹ thuật tổng hợp thường p dụng trong việc phân tích dữ liệu có tính thăm dò và b o c o tự động. Nhiệm vụ chính là sản sinh ra c c mô tả đặc trưng cho một lớp. Mô tả loại này là một kiểu tổng hợp, tóm t t c c đặc tính chung của tất cả hay hầu hết c c mục của một lớp. C c mô tả đặc trưng thể hiện theo luật có dạng sau: “Nếu một mục thuộc về lớp đã ch trong tiền đề thì mục đó có tất cả c c thuộc tính đã nêu trong kết luận”. Lưu ý rằng luật dạng này có c c kh c biệt so với luật phân lớp. Luật ph t hiện đặc trưng cho lớp ch sản sinh khi c c mục đã thuộc về lớp đó. 1.4.5. Mô hình hoá sự phụ thuộc (dependency modeling) Là việc tìm kiếm một mô hình mô phỏng sự phụ thuộc giữa c c biến, thuộc tính theo hai m c: M c cấu trúc của mô hình mô tả thường dưới dạng đồ thị. Trong đó, c c biến phụ thuộc bộ phận vào c c biến kh c. M c định lượng mô hình mô tả m c độ phụ thuộc. Những phụ thuộc này thường được biểu thị dưới dạng theo luật “nếu – thì” (nếu 9 tiền đề là đúng thì kết luận đúng). Về nguyên t c, cả tiền đề và kết luận đều có thể là sự kết hợp logic của c c gi trị thuộc tính. Trên thực tế, tiền đề thường là nhóm c c gi trị thuộc tính và kết luận ch là một thuộc tính. H n nữa hệ thống có thể ph t hiện c c luật phân lớp trong đó tất cả c c luật cần phải có cùng một thuộc tính do người dùng ch ra trong kết luận. 1.4.6. Phát hiện sự biến đổi và độ lệch (change and deviation dectection) Nhiệm vụ này tập trung vào kh m ph hầu hết sự thay đổi có nghĩa dưới dạng độ đo đã biết trước hoặc gi trị chuẩn, ph t hiện độ lệch đ ng kể giữa nội dung của tập con dữ liệu thực và nội dung mong đợi. Hai mô hình độ lệch hay dùng là lệch theo thời gian hay lệch theo nhóm. Độ lệch theo thời gian là sự thay đổi có ý nghĩa của dữ liệu theo thời gian. Độ lệch theo nhóm là sự kh c nhau của giữa dữ liệu trong hai tập con dữ liệu, đây tính cả trường hợp tập con dữ liệu này thuộc tập con kia, nghĩa x c định dữ liệu trong một nhóm con của đối tượng có kh c đ ng kể so với toàn bộ đối tượng không? Theo c ch này, sai sót dữ liệu hay sai lệch so với gi trị thông thường được ph t hiện [5, 6]. Vì những nhiệm vụ này yêu cầu số lượng và c c dạng thông tin rất kh c nhau nên chúng thường ảnh hư ng đến việc thiết kế và chọn phư ng ph p khai ph dữ liệu kh c nhau. Ví dụ như phư ng ph p cây quyết định (sẽ được trình bày dưới đây) tạo ra được một mô tả phân biệt được c c mẫu giữa c c lớp nhưng không có tính chất và đặc điểm của lớp. 1.5. Các Kỹ thuật khai phá dữ liệu Khai ph dữ liệu là lĩnh vực mà con người luôn tìm c ch đạt được mực đích sử dụng thông tin của mình. Qu trình khai ph dữ liệu là qu trình ph t hiện mẫu, trong đó kỹ 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. Một số kỹ thuật thường được p dụng trong c c hệ thống: sử dụng công cụ truy vấn, xây dựng cây quyết định, dựa theo khoảng c ch (K-l ng giềng gần), gi trị trung bình, ph t hiện luật kết hợp, … [6,7] Các kỹ thuật trên có thể được mô phỏng và được tích hợp vào c c hệ thống lai để khai ph dữ liệu theo dự b o. 10 1.5.1. Các thành phần của quá trình 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 và phư ng ph p tìm kiếm [6, 7]. a. Biểu diễn mô hình: Mô hình được biểu diễn theo một ngôn ngữ L nào đó để miêu tả c c mẫu có thể khai phá được. Mô tả mô hình rõ ràng thì học m y sẽ tạo ra mẫu có mô hình chính x c cho dữ liệu. Tuy nhiên, nếu mô hình qu lớn thì khả năng dự đo n của học m y sẽ bị hạn chế. Như thế sẽ làm cho việc tìm kiếm ph c tạp h n cũng như hiểu được mô hình là không đ n giản hoặc sẽ không thể có c c mẫu tạo ra được một mô hình chính x c cho dữ liệu. Ví dụ mô tả cây quyết định sử dụng phân chia c c nút theo 1 trường dữ liệu, chia không gian đầu vào thành c c siêu phẳng song song với trục c c thuộc tính. hư ng ph p cây quyết định như vậy không thể khai ph được dữ liệu dạng công th c X=Y dù cho tập học có quy mô lớn thế nào đi nữa. Vì vậy, việc quan trọng là người phân tích dữ liệu cần phải hiểu đầy đủ c c giả thiết miêu tả. Một điều cũng kh quan trọng là người thiết kế giải thuật cũng 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 nào. Khả năng miêu tả mô hình càng lớn thì càng làm tăng m c độ nguy hiểm do bị học qu và làm giảm đi khả năng dự đo n c c dữ liệu chưa biết. H n nữa, việc tìm kiếm sẽ càng tr lên ph c tạp h n và việc giải thích mô hình cũng khó khăn h n. Mô hình ban đầu được x c định bằng c ch kết hợp biến đầu ra (phụ thuộc) với c c biến độc lập mà biến đầu ra phụ thuộc vào. au đó phải tìm những tham số mà bài to n cần tập trung giải quyết. Việc tìm kiếm mô hình sẽ đưa ra được một mô hình phù hợp với tham số được x c định dựa trên dữ liệu (trong một số trường hợp kh c thì mô hình và c c tham số lại thay đổi để phù hợp với dữ liệu). Trong một số trường hợp, tập c c dữ liệu được chia thành tập dữ liệu học và tập dữ liệu thử. Tập dữ liệu học được dùng để làm cho tham số của mô hình phù hợp với dữ liệu. Mô hình sau đó sẽ được đ nh gi bằng c ch đưa c c dữ liệu thử vào mô hình và thay đổi c c tham số cho phù hợp nếu cần. Mô hình lựa chọn có thể là phư ng ph p thống kê như , … một số giải thuật học m y (ví dụ như cây quyết định và c c quyết định học có thầy kh c), mạng neuron, suy diễn hướng tình huống (case based reasoning), c c kỹ thuật phân lớp. 11 b. Đánh giá mô hình: Là việc đ nh gi , ước lượng c c mô hình chi tiết, chuẩn trong qu trình xử lý và ph t hiện tri th c với sự ước lượng có dự b o chính x c hay không và có thoả mãn c s logic hay không? Ước lượng phải được đ nh gi chéo (cross validation) với việc mô tả đặc điểm bao gồm dự b o chính x c, tính mới lạ, tính hữu ích, tính hiểu được phù hợp với c c mô hình. Hai phư ng ph p logic và thống kê chuẩn có thể sử dụng trong mô hình kiểm định. c. Phương pháp tìm kiếm: hư ng ph p này bao gồm hai thành phần: tìm kiếm tham số và tìm kiếm mô hình. Trong tìm kiếm tham số, giải thuật cần tìm kiếm c c 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. Việc tìm kiếm không cần thiết đối với một số bài to n kh đ n giản: c c đ nh gi tham số tối ưu có thể đạt được bằng c c c ch đ n giản h n. Đối với c c mô hình chung thì không có c c c ch này, khi đó giải thuật “tham lam” thường được sử dụng lặp đi lặp lại. Ví dụ như phư ng ph p giảm gradient trong giải thuật lan truyền ngược (backpropagation) cho c c mạng neuron. 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 (closed form) không dễ đạt được. 1.5.2. Kỹ thuật suy diễn/quy nạp 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 [6, 7]. Kỹ thuật 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. Ví dụ như to n tử liên kết p dụng cho bảng quan hệ, bảng đầu ch a thông tin về c c nhân viên và phòng ban, bảng th hai ch a c c thông tin về c c phòng ban và c c trư ng phòng. Như vậy sẽ suy ra được mối quan hệ giữa c c nhân viên và c c trư ng phòng. hư 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. 12 Kỹ thuật 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. hư ng ph p này liên quan đến việc tìm kiếm c c mẫu trong C DL. 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.3. Kỹ thuật ứng dụng K-láng giềng gần ự miêu tả c c bản ghi trong tập dữ liệu khi trỏ vào không gian nhiều chiều là rất có ích đối với việc phân tích dữ liệu. Việc dùng c c miêu tả này, nội dung của vùng lân cận được x c định, trong đó c c bản ghi gần nhau trong không gian được xem xét thuộc về lân cận (hàng xóm – l ng giềng) của nhau. Kh i niệm này được dùng trong khoa học kỹ thuật với tên gọi K-l ng giềng gần, trong đó K là số l ng giềng được sử dụng. hư ng ph p này rất hiệu quả nhưng lại đ n giản. Ý tư ng thuật to n học Kl ng giềng gần là “thực hiện như c c l ng giềng gần của bạn đã làm”. 1.5.4. Kỹ thuật sử dụng cây quyết định và luật Với kỹ thuật phân lớp dựa trên cây quyết định, kết quả của qu trình xây dựng mô hình sẽ cho ra một cây quyết định. Cây này được sử dụng trong qu trình phân lớp c c đối tượng dữ liệu chưa biết hoặc đ nh gi độ chính x c của mô hình. Tư ng ng với hai giai đoạn trong qu trình phân lớp là qu trình xây dựng và sử dụng cây quyết định. Qu trình xây dựng cây quyết định b t đầu t một nút đ n biểu diễn tất cả c c mẫu dữ liệu. au đó, c c mẫu sẽ được phân chia một c ch đệ quy dựa vào việc lựa chọn c c thuộc tính. Nếu c c mẫu có cùng một lớp thì nút sẽ tr thành l , ngược lại ta sử dụng một độ đo thuộc tính để chọn ra thuộc tính tiếp theo làm c s để phân chia c c mẫu ra c c lớp. Theo t ng gi trị của thuộc tính v a chọn, ta tạo ra c c nh nh tư ng ng và phân chia c c mẫu vào c c nh nh đã tạo. Lặp lại qu trình trên cho tới khi tạo ra được cây quyết định, tất cả c c nút triển khai thành l và được g n nhãn. Qu trình đệ quy sẽ d ng lại khi một trong c c điều kiện sau được thỏa mãn: + Tất cả c c mẫu thuộc cùng một nút. + Không còn một thuộc tính nào để lựa chọn. 13 + Nh nh không ch a mẫu nào. hần lớn c c giải thuật sinh cây quyết định đều có hạn chế chung là sử dụng nhiều bộ nhớ. Lượng bộ nhớ sử dụng tỷ lệ thuận với kích thước của mẫu dữ liệu huấn luyện. Một chư ng trình sinh cây quyết định có hỗ trợ sử dụng bộ nhớ ngoài song lại có nhược điểm về tốc độ thực thi. Do vậy, vấn đề t a bớt cây quyết định tr nên quan trọng. C c nút l không ổn định trong cây quyết định sẽ được t a bớt. 1.5.5. Kỹ thuật phát hiện luật kết hợp Kỹ thuật này nhằm ph t hiện ra c c luật kết hợp giữa c c thành phần dữ liệu trong c s dữ liệu. 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. Ta có thể lấy một ví dụ đ n giản về luật kết hợp như sau: sự kết hợp giữa hai thành phần A và B có nghĩa là sự xuất hiện của A trong bản ghi kéo theo sự xuất hiện của B trong cùng bản ghi đó: A => B. Cho một lược đồ R={A1, …, Ap} c c thuộc tính với miền gi trị {0,1}, và một quan hệ r trên R. Một luật kết hợp trên r được mô tả dưới dạng X=>B với X B R và R\X. Về mặt trực gi c, ta có thể ph t biểu ý nghĩa của luật như sau: nếu một bản ghi của bảng r có gi trị 1 tại mỗi thuộc tính thuộc X thì gi trị của thuộc tính B cũng là 1 trong cùng bản ghi đó. Ví dụ như ta có tập c s dữ liệu về c c mặt hàng b n trong siêu thị, c c dòng tư ng ng với c c ngày b n hàng, c c cột tư ng ng với c c mặt hàng thì gi trị 1 tại ô (20/10, b nh mì) x c định rằng b nh mì đã b n ngày hôm đó cũng kéo theo sự xuất hiện gi trị 1 tại ô (20/10, b ). Cho W R, đặt s(W,r) là tần số xuất hiện của W trong r được tính bằng tỷ lệ của c c hàng trong r có gi trị 1 tại mỗi cột thuộc W. Tần số xuất hiện của luật X=>B trong r được định nghĩa là s(X s(X {B}, r) còn gọi là độ hỗ trợ của luật, độ tin cậy của luật là {B}, r)/s(X, r). Ở đây X có thể gồm nhiều thuộc tính, B là gi trị không cố định. Nhờ vậy mà không xảy ra việc tạo ra c c luật không mong muốn trước khi qu trình tìm kiếm b t đầu. Điều đó cũng cho thấy không gian tìm kiếm có kích thước tăng theo hàm mũ của số lượng c c thuộc tính đầu vào. Do vậy cần phải chú ý khi thiết kế dữ liệu cho việc tìm kiếm c c luật kết hợp. Nhiệm vụ của việc ph t hiện c c luật kết hợp là phải tìm tất cả c c luật X=>B sao cho tần số của luật không nhỏ h n ngưỡng σ cho trước và độ tin cậy của luật không 14 nhỏ h n ngưỡng θ cho trước. T một c s dữ liệu ta có thể tìm được hàng nghìn và thậm chí hàng trăm nghìn c c luật kết hợp. Ta gọi một tập con X R là thường xuyên trong r nếu thỏa mãn điều kiện s(X, r)≥σ. Nếu biết tất cả c c tập thường xuyên trong r thì việc tìm kiếm c c luật rất dễ dàng. Vì vậy, giải thuật tìm kiếm c c luật kết hợp trước tiên đi tìm tất cả c c tập thường xuyên này, sau đó tạo dựng dần c c luật kết hợp bằng c ch ghép dần c c tập thuộc tính dựa trên m c độ thường xuyên. 1.6. Những thách th c trong nghiên c u và ng dụng kỹ thuật khai phá dữ liệu Trong phần này, một số vấn đề liên quan đến CSDL và các th ch th c trong việc nghiên c u và ng dụng kỹ thuật khai ph dữ liệu được trình bày để cho thấy xu hướng và tiềm năng của lĩnh vực này hiện nay [7]. Khai ph c c dữ liệu thô để ph t hiện ra tri th c mới. 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 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 phá hay không và làm thế nào để giải quyết với sự dư CSDL 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 CSDL có kích thước lên 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. 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 tất cả các CSDL 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. 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ậy thay đổi dữ liệu nhanh chóng có thể làm cho c c mẫu khai phá được trước đó mất gi trị. H n nữa, c c biến