Tài liệu Ứng dụng khai phá dữ liệu trong phân tích đánh giá kết quả học tập của sinh viên trường Đại học Hải Phòng

LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các kết quả nêu trong luận văn là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác. Tôi xin cam đoan rằng các thông tin trích dẫn trong luận văn đều đã được chỉ rõ nguồn gốc. Hải Phòng, ngày 15 tháng 09 năm 2015 1 LỜI CẢM ƠN Trước tiên, tôi muốn gửi lời cảm ơn sâu sắc nhất đến thầy giáo hướng dẫn, TS. Trần Đăng Hoan, nếu không có sự hướng dẫn tận tình, chu đáo của thầy tôi không thể hoàn thành luận văn này. Tôi xin chân thành cảm ơn những thầy cô giáo đã giảng dạy tôi trong suốt quá trình học tập, nghiên cứu và rèn luyện ở Trường Đại học Hàng Hải Việt Nam, những kiến thức mà tôi nhận được từ các thầy cô sẽ là hành trang giúp tôi vững bước trong tương lai. Tôi cũng xin gửi lời cảm ơn đến các bạn trong lớp Công nghệ Thông tin khóa 2013-2015 Trường Đại học Hàng Hải Việt Nam đã chia sẻ những khó khăn trong quá trình nghiên cứu. Tôi đặc biệt gửi lời cảm đến đồng chí Hà Khánh Lâm và đồng chí Đỗ Thị Thu Thủy phòng Đào tạo trường Đại học Hải Phòng đã giúp đỡ tôi rất nhiều trong quá trình thu thập dữ liệu về sinh viên. Cuối cùng, tôi muốn gửi lời cảm ơn sâu sắc đến tất cả bạn bè và đặc biệt là chồng tôi đã luôn kịp thời động viên, giúp đỡ tôi vượt qua những khó khăn trong cuộc sống để hoàn thành được luận văn này. Mặc dù đã có nhiều cố gắng để thực hiện luận văn một cách hoàn chỉnh nhất, song do vẫn còn những hạn chế về kiến thức và kinh nghiệm nên không thể tránh khỏi những thiếu sót nhất định mà bản thân chưa thấy được. Tôi rất mong được sự góp ý của quý thầy, cô giáo và các bạn đồng nghiệp để luận văn được hoàn chỉnh hơn. Tôi xin chân thành cảm ơn. MỤC LỤ 2 LỜI CAM ĐOAN......................................................................................................i LỜI CẢM ƠN...........................................................................................................ii DANH MỤC CÁC CHỮ VIẾT TẮT VÀ KÝ HIỆU..............................................v DANH MỤC CÁC BẢNG......................................................................................vi DANH MỤC CÁC HÌNH......................................................................................vii LỜI MỞ ĐẦU...........................................................................................................1 CHƯƠNG 1. KHÁI QUÁT PHÁT HIỆN TRI THỨC TỪ CƠ SỞ DỮ LIỆU......3 1.1. Sự cần thiết và ứng dụng của KDD....................................................................3 1.1.1. Sự cần thiết của KDD......................................................................................3 1.1.2. Ứng dụng của KDD.........................................................................................4 1.2. Định nghĩa và nhiệm vụ của KDD.....................................................................5 1.2.1. Định nghĩa phát hiện tri thức...........................................................................5 1.2.2. Các nhiệm vụ chính của KDD.........................................................................6 1.3. Các lĩnh vực liên quan........................................................................................6 1.4. Các quá trình khám phá tri thức.........................................................................8 1.5. Những thách thức trong nghiên cứu và ứng dụng............................................15 1.6. Khai phá dữ liệu trong giáo dục.......................................................................16 1.7. Khai phá dữ liệu sinh viên trường Đại học Hải Phòng.....................................17 1.8. Kết luận............................................................................................................17 CHƯƠNG 2. TÌM HIỂU MỘT SỐ KỸ THUẬT KHAI PHÁ DỮ LIỆU............19 2.1 Cây quyết định...................................................................................................19 2.1.1. Giới thiệu.......................................................................................................19 2.1.2. Xây dựng cây quyết định...............................................................................20 2.2 Thuật toán K-means...........................................................................................23 2.2.1. Giới thiệu.......................................................................................................23 2.2.2. Giải thuật K-means........................................................................................24 2.3. Thuật toán EM (Expectation Maximization)....................................................24 2.4. Kết luận.............................................................................................................26 3 CHƯƠNG 3. ỨNG DỤNG KHAI PHÁ DỮ LIỆU TRONG PHÂN TÍCH VÀ ĐÁNH GIÁ KẾT QUẢ HỌC TẬP CỦA SINH VIÊN ĐẠI HỌC HẢI PHÒNG..................................................................................................................27 3.1. Giới thiệu chung...............................................................................................27 3.2. Dự đoán nguy cơ sinh viên thôi học.................................................................28 3.2.1. Xác định mục tiêu của bài toán.....................................................................28 3.2.2. Mô tả công cụ thử nghiệm.............................................................................29 3.2.3. Mô tả dữ liệu thử nghiệm..............................................................................29 3.2.4. Khai phá dữ liệu............................................................................................33 3.2.5. Một số kết quả và các đánh giá phân tích......................................................35 3.3. Tìm mối tương quan giữa các môn học cơ bản với kết quả học tập của sinh viên..........................................................................................................................37 3.3.1. Mục tiêu của bài toán.....................................................................................37 3.3.2. Mô tả công cụ thử nghiệm.............................................................................39 3.3.3. Mô tả dữ liệu thử nghiệm..............................................................................39 3.3.4. Khai phá dữ liệu............................................................................................41 3.3.5. Một số kết quả và các đánh giá phân tích......................................................42 3.4. Kết luận.............................................................................................................45 KẾT LUẬN ............................................................................................................46 TÀI LIỆU THAM KHẢO......................................................................................47 4 DANH MỤC CÁC CHỮ VIẾT TẮT VÀ KÝ HIỆU Chữ viết tắt CSDL KDD EM DM SQL EDM Giải thích Cơ sở dữ liệu Knowledge Discovery in Databases Expectation maximization Data Mining Structured Query Language Educational Data Mining 5 DANH MỤC CÁC BẢNG Số bảng 2.1 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 Tên bảng Bảng dữ liệu ví dụ về sinh viên Kết quả học tập của sinh viên theo từng học kỳ Kết quả học tập đã chuyển đổi Kết quả học tập của sinh viên theo từng học kỳ Báo cáo kết quả học tập sinh viên khoa kế toán tài chính năm 2015 Chi tiết điểm học kỳ lưu ở phòng Đào tạo Chi tiết điểm học kỳ được chuyển từ bảng điểm lưu ở phòng Đào tạo Mô tả chi tiết các cụm với thuật toán EM và k=5 Mô tả chi tiết các cụm với thuật toán K-means và k=5 6 Trang 22 30 31 38 38 39 40 42 44 DANH MỤC CÁC HÌNH Số hình 1.1 1.2 1.3 2.1 2.2 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 Tên hình Nhiệm vụ chính của KDD Phát hiện tri thức và các lĩnh vực liên quan Quá trình Khám phá tri thức từ dữ liệu Mô hình cây quyết định Kết quả cây quyết định với tập dữ liệu học trong bảng 2.1 Thống kê tỷ lệ sinh viên thôi học theo năm học Danh sách các thuộc tính dùng trong dự đoán Thiết lập tỷ lệ của bộ dữ liệu kiểm thử Kết quả xây dựng mô hình dự đoán sinh viên thôi học Độ chính xác của mô hình dự đoán sinh viên thôi học Thiết lập tham số cho thuật toán EM với k=5 Thiết lập tham số cho thuật toán K-means với k=5 Kết quả phân cụm theo thuật toán EM với k=5 Kết quả phân cụm theo thuật toán K-means với k=5 7 Trang 6 7 8 19 22 28 34 34 35 37 41 41 42 43 LỜI MỞ ĐẦU Hiện nay trên thế giới khai phá dữ liệu (data mining) và phát hiện tri thức từ cơ sở dữ liệu (Knowledge Discovery in Databases - KDD) đã và đang được áp dụng một cách rộng rãi trong rất nhiều lĩnh vực khác nhau [2]. Đặc biệt, khai phá dữ liệu trong giáo dục tuy là một ngành mới nổi trong những năm gần đây nhưng nó thu hút được sự quan tâm của đông đảo cộng đồng khoa học. Năm 2005, hội thảo đầu tiên mang tên "Educational Data Mining" (EDM) đã được tổ chức tại Pittsburgh cùng với Hội nghị AAAI (Association for the Advancement of Artificial Intelligence). Sau đó, hội nghị quốc tế về khai phá dữ liệu giáo dục lần đầu tiên được tổ chức tại Canada trong hai ngày 20 và 21 tháng 6 năm 2008 với mục đích tập trung các nhà nghiên cứu từ nhiều lĩnh vực khác nhau như khoa học máy tính, thống kê, giáo dục, tâm lý học… để cùng nhau phân tích tập dữ liệu lớn từ giáo dục tìm ra lời giải đáp cho những câu hỏi quan trọng trong giáo dục. Kể từ năm 2008, Hội nghị quốc về khai phá dữ liệu giáo dục (Hội nghị quốc tế EDM) được tổ chức đều đặn hàng năm tại các đất nước khác nhau trên thế giới. Khai phá dữ liệu trong giáo dục nhằm giải đáp các câu hỏi trong giáo dục, làm sáng tỏ tiến trình học tập từ đó hỗ trợ cho các nhà quản lý giáo dục trong việc ra quyết định để nâng cao hiệu suất giảng dạy và học tập. Với số lượng lớn (khoảng hơn 20000 sinh viên đang theo học không bao gồm sinh viên theo học hệ tại chức, từ xa, liên thông) việc thực hiện công tác phân tích, đánh giá hiệu quả học tập của sinh viên trong trường Đại học Hải Phòng gặp rất nhiều khó khăn. Từ dữ liệu về lý lịch sinh viên, kết quả học tập của sinh viên vậy làm thế nào để có thể thu thập được các thông tin có ích, hỗ trợ cho việc ra quyết định chẳng hạn như: Dự đoán được những sinh viên sẽ thôi học hoặc bị buộc thôi học để từ đó có tác động kịp thời giảm số trường hợp thôi học xuống mức thấp nhất; Dự đoán số lượng trúng tuyển từ hồ sơ đăng ký vào; dự đoán lượng thí sinh nguyện vọng một, nguyện vọng hai; Dự đoán chất lượng sinh viên từ điểm đầu vào và các thông tin lý lịch; Tìm mối tương quan các môn học cơ bản (Toán, Vật lý, 1 Hóa Học, Tiếng Anh..) với các môn học chuyên ngành của sinh viên; Tìm ra nhóm sinh viên bị tụt dốc trong học tập… Thấy rõ được vai trò và tầm quan trọng của EDM trong bối cảnh hiện tại của trường Đại học Hải Phòng nên tôi đã lựa chọn đề tài “Ứng dụng khai phá dữ liệu trong phân tích đánh giá kết quả học tập của sinh viên trường Đại học Hải Phòng” cho luận văn tốt nghiệp của mình. 2 CHƯƠNG 1. KHÁI QUÁT PHÁT HIỆN TRI THỨC TỪ CƠ SỞ DỮ LIỆU Chương này trình bày tổng quan về phát hiện tri thức từ cơ sở dữ liệu (Knowledge Discovery in Databases), làm rõ mối liên hệ giữa phát hiện tri thức từ cơ sở dữ liệu và khai phá dữ liệu (Data Mining) cũng như giữa KDD với các lĩnh vực liên quan, chẳng hạn như học máy, thống kê, và cơ sở dữ liệu. Các ứng dụng trong thực tế, những thách thức trong nghiên cứu và ứng dụng của KDD cũng được trình bày trong chương này. 1.1. Sự cần thiết và ứng dụng của KDD 1.1.1. Sự cần thiết của KDD Các phương thức truyền thống nhằm chuyển dữ liệu thành các tri thức phụ thuộc vào các phân tích và giải thích của các chuyên gia. Chẳng hạn như trong lĩnh vực chăm sóc sức khỏe, các chuyên gia thường phải định kỳ phân tích các xu hướng hiện tại và các thay đổi trong dữ liệu chăm sóc sức khỏe. Sau đó họ sẽ lập một báo cáo phân tích chi tiết để gửi lên trên, báo cáo này sẽ là cơ sở để đưa ra các quyết định trong tương lai và lập kế hoạch cho công tác quản lý y tế. Trong rất nhiều lĩnh vực khác như khoa học, tài chính, tiếp thị, hoạt động bán lẻ ... hoạt động phân tích dữ liệu đều chủ yếu nhờ vào các chuyên gia có kinh nghiệm [2]. Với các lĩnh vực trên, việc tìm kiếm thông tin từ tập dữ liệu một cách thủ công mất nhiều thời gian, tiền bạc và mang tính chủ quan. Trên thực tế, trong những năm 90 với sự phát triển mạnh của công nghệ vi xử lý, công nghệ lưu trữ, công nghệ truyền thông và ứng dụng công nghệ thông tin trong nhiều lĩnh vực dẫn đến dữ liệu gia tăng một cách nhanh chóng, cách phân tích này trở nên không khả thi. CSDL gia tăng kích thước theo hai cách: 1.Số lượng các đối tượng bản ghi trong CSDL; 2. Số luợng các trường hoặc thuộc tính của một đối tượng bản ghi. Một CSDL lớn có thể bao gồm khoảng 1.000.000.000 đối tượng càng ngày càng tăng, ví dụ như các dữ liệu thiên văn. Tương tự, số lượng các trường có thể tăng lên thành 100 hay 1000 trường, ví dụ như các dữ liệu chẩn đoán bệnh [2]. Theo số liệu thông kê vào năm 2003 hãng truyền thông AT&T tiếp nhận 275 cuộc gọi/ngày lưu trữ 26 Tb thông tin về khách hàng, hãng France Telecom lưu trữ 3 30Tb thông tin về khách hàng,Walmart tiếp nhận 20 triệu giao dịch/ngày, Google tiếp nhận hơn 4 tỉ yêu cầu tìm kiếm/ngày, lưu trữ hàng trăm TB dữ liệu, Alexa internet archive lưu trữ 500Tb/7 năm…Tổng hợp lại trong năm 2002 dữ liệu trên toàn cầu tăng 5Eb. Đúng như John Naisbell đã nói “Chúng ta đang chìm ngập trong dữ liệu nhưng vẫn đói tri thức” vì có “khoảng cách rất lớn giữa khả năng sinh ra dữ liệu và khả năng sử dụng chúng” (Fayyad,1996). Dữ liệu chứa rất nhiều thông tin giá trị, có lợi cho qui trình ra quyết định nhưng với khối lượng dữ liệu khổng lồ như đã kể trên thì không thể phân tích dữ liệu bằng các phương thức thủ công và cũng không thể thực hiện được với truy vấn truyền thống (SQL) vì rất nhiều kiểu câu truy vấn mà con người quan tâm là rất khó thực hiện hay miêu tả trong ngôn ngữ vấn tin, chẳng hạn như: tìm tất cả các bản ghi nghi là gian lận, tìm tất cả các bản ghi tương tự như các bản ghi trong bảng A, không có nhiều thông tin trong các trường của CSDL…Do đó, KDD là một giải pháp cho vấn đề của thời đại thông tin số : quá tải dữ liệu [2]. 1.1.2. Ứng dụng của KDD Hiện nay, có khá nhiều các ứng dụng của khai phá dữ liệu và khám phá tri thức được triển khai, đem lại hiệu quả cao trong thực tế, phục vụ cho sản xuất kinh doanh và nghiên cứu khoa học. Trong khoa học, một trong những ngành ứng dụng chính là thiên văn học. Hệ thống SKICAT dùng để phân tích ảnh, phân loại và xếp nhóm các vật thể không gian từ các ảnh quan sát vũ trụ. Hệ thống này được dùng để xử lý 3 terabytes dữ liệu ảnh từ Đài thiên văn Palomar, với khoảng 1 tỉ vật thể không gian phát hiện được. SKICAT có thể làm được những công việc tính toán cực lớn trong việc phân loại các ảnh vật thể không rõ ràng [2]. Trong kinh doanh, các ứng dụng chính của khám phá tri thức bao gồm tiếp thị, tài chính đặc biệt là đầu tư, phát hiện gian lận, sản xuất, viễn thông. Trong tiếp thị, ứng dụng chính là hệ thống CSDL tiếp thị, phân tích các dữ liệu khách hàng để phân loại các nhóm khách hàng khác nhau và dự báo về sở thích của họ. 4 Phát hiện gian lận: Hệ thống HNC Falcon and Nestor PRISM dùng để theo dõi các gian lận thẻ tín dụng, có thể theo dõi hoạt động của hàng triệu tài khoản. Hệ thống FAIS dùng để thẩm định các giao dịch thương mại có bao gồm hoạt động chuyển tiền bất hợp pháp [2]. Trong lĩnh vực giáo dục: Ứng dụng khai phá dữ liệu nhằm giải đáp các câu hỏi quan trọng, làm sáng tỏ tiến trình học tập từ đó hỗ trợ cho các nhà quản lý giáo dục trong việc ra quyết định để nâng cao hiệu suất giảng dạy và học tập. Ứng dụng khai phá dữ liệu trong hệ thống đào tạo trực tuyến nhằm phân tích hành vi của người học. 1.2. Định nghĩa và nhiệm vụ của KDD 1.2.1. Định nghĩa phát hiện tri thức Ngoài thuật ngữ phát hiện tri thức, người ta còn dùng một số thuật ngữ khác có ý nghĩa tương tự như phân tích dữ liệu/mẫu, khai mỏ dữ liệu, khai phá dữ liệu… Nhưng tóm lại, về bản chất phát hiện tri thức liên quan đến việc phân tích các dữ liệu và sử dụng các kỹ thuật đặc biệt để tìm ra các mẫu đặc trưng trong một tập dữ liệu khổng lồ. Có nhiều định nghĩa về phát hiện tri thức đã được các tác giả khác nhau đưa ra, theo định nghĩa của Fayyad: “KDD là quá trình không tầm thường của việc xác định các mẫu tiềm ẩn có tính hợp lệ, mới lạ, có ích và có thể hiểu được trong dữ liệu” [2]. Tiến trình khai phá tri thức bao gồm các giai đoạn: Chuẩn bị dữ liệu, tìm kiếm mô hình, khai phá dữ liệu, đánh giá mẫu và sử dụng tri thức khai phá được. Thuật ngữ “mẫu tiềm ẩn” được hiểu là mối quan hệ trong dữ liệu chẳng hạn như những sinh viên học giỏi toán và tiếng anh thì có điểm trung bình cuối khóa cao, “hợp lệ” bởi vì chứng minh được tính đúng của mô hình. Thuật ngữ “mới lạ” hàm ý rằng những mẫu khai phá được là không biết trước. 5 1.2.2. Các nhiệm vụ chính của KDD L M H P D K u ồ h ự ô h ậ a á i â a i t n b t i q á ả k c t h u l o p ế ụ h i ớ h t m á ệ p á c n h ợ m s d p ẫ ự ữ u b l t i i u ế ệ ầ n u n t ự Hình 1.1 Nhiệm vụ chính của KDD Nhiệm vụ của khai phá dữ liệu thường được chia thành 2 nhóm chính [10] :  Dự báo là sử dụng một vài biến để dự báo giá trị chưa biết hoặc giá trị tương lai của các biến khác. Dự đoán bao gồm các kỹ thuật: Phân lớp, hồi qui, phát hiện sự biến đổi và độ lệch, khai thác mẫu tuần tự.  Mô tả: 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 cơ sở dữ liệu hiện có bao gồm: Phân cụm, luật kết hợp. 1.3. Các lĩnh vực liên quan Thống kê Máy học Phát hiện tri thức/ Khai phá dữ liệu Trực quan Cơ sở dữ liệu 6 Hình 1.2 Phát hiện tri thức và các lĩnh vực liên quan Phát hiện tri thức/ khai phá dữ liệu liên quan chặt chẽ đến các lĩnh vực khác như: Máy học, thống kê, cơ sở dữ liệu và trực quan. Lĩnh vực máy học và nhận dạng mẫu đan xen với khai phá dữ liệu trong hướng nghiên cứu về các thuật toán đối với các hệ thống nhằm rút ra các mẫu, các mô hình từ dữ liệu. Trọng tâm của khai phá dữ liệu là mở rộng về lý thuyết và các thuật toán đối với vấn đề tìm kiếm ra các mẫu đặc trưng trong một tập dữ liệu khổng lồ, làm thế nào để các thuật toán vẫn hoạt động hiệu quả với một tập dữ liệu đầu vào lớn. Thống kê đặc biệt có nhiều điểm chung với khai phá dữ liệu. Thống kê cung cấp một nền tảng lý thuyết vững chắc cho các bài toán phân tích dữ liệu, kiểm định mô hình và đánh giá tri thức phát hiện được [2]. Sự khác nhau cơ bản giữa khai phá dữ liệu và thống kê là ở chỗ khai phá dữ liệu là một phương tiện được dùng bởi người sử dụng cuối chứ không phải là các nhà thống kê. Những người tham gia vào phát hiện tri thức được chia ra thành 3 nhóm: những nhà chuyên môn, là những người rất am hiểu về lĩnh vực ứng dụng. Thứ hai là những nhà phân tích, đây là những người thực hiện phát hiện tri thức, họ có nhiều kiến thức về các giai đoạn của quá trình phát hiện tri thức. Thứ ba là những người sử dụng cuối cùng, họ sử dụng tri thức rút được từ quá trình phát hiện tri thức để hỗ trợ trong việc ra quyết định. Khai phá dữ liệu tự động quá trình thống kê một cách có hiệu quả, vì vậy làm nhẹ bớt công việc của người dùng đầu cuối. Như vậy, nhờ có khai phá dữ liệu, việc dự đoán và kiểm tra rất vất vả trước đây được tính, được dự đoán và kiểm tra một cách tự động bằng máy tính. Phát hiện tri thức cũng liên quan chặt chẽ đến lĩnh vực cơ sở dữ liệu. Trong giai đoạn thu thập dữ liệu và tiền xử lý dữ liệu cần nhiều kiến thức về cơ sở dữ liệu. Trực quan giúp biểu diễn tri thức phát hiện được trực quan, dễ hiểu, dễ kiểm tra. Vấn đề trực quan hóa của khai phá dữ liệu đề cập đến các khía cạnh sau: 7  Trực quan dữ liệu: tập dữ liệu dùng cho khai phá được biểu diễn, hiển thị bằng các bảng biểu, đồ thị.  Trực quan tiến trình khai phá dữ liệu.  Trực quan kết quả khai phá dữ liệu: kết quả khai phá dữ liệu được biểu diễn bằng các bảng biểu, đồ thị. 1.4. Các quá trình khám phá tri thức Các quá trình khám phá tri thức bao gồm chín giai đoạn như hình 1.3 đã chỉ ra. Evaluation and Interprelation 5, 6, 7 9. Discovered Knowledge (Visualization& Intergration) Data Mining Transformation 3 Preprocessing: Data cleaning etc. Selection & Addition 1.Domain Understanding & KDD Goals Hình 1.3 Quá trình phát hiện tri thức từ dữ liệu [1] Giai đoạn 1: Tìm hiểu lĩnh vực ứng dụng, xác định mục tiêu bài toán Cũng giống như bất kỳ dự án thông thường nào, bước đầu tiên trong quá trình phát hiện tri thức là phải tìm hiểu lĩnh vực ứng dụng, xác định rõ mục tiêu và nhiệm vụ của bài toán. Giai đoạn này là điều kiện tiên quyết cho việc trích rút tri thức và lựa chọn kỹ thuật khai phá dữ liệu thích hợp với mục tiêu của ứng dụng và 8 đặc điểm của dữ liệu. Vì vậy, để ứng dụng một cách tốt nhất khai phá dữ liệu, cần phải có một mô tả đầy đủ về mục tiêu cần đạt được. Giai đoạn 2: Thu thập dữ liệu Sau khi xác định được mục tiêu của bài toán, có một mô tả đầy đủ về mục tiêu cần đạt tới ta tiến hành thu thập các dữ liệu liên quan (các thông tin cần thiết, phù hợp với mục tiêu của quá trình khai phá dữ liệu bao gồm cả các thuộc tính sẽ được xem xét). Công việc này bao gồm thu thập những dữ liệu có sẵn, thu thập dữ liệu cần thiết bổ sung. Sau đó, ta tích hợp tất cả các dữ liệu cho việc khám phá tri thức vào một tập dữ liệu. Quá trình này là rất quan trọng vì nếu một số thuộc tính quan trọng bị bỏ qua dẫn tới toàn bộ nghiên cứu thất bại. Giai đoạn 3: Tiền xử lý Dữ liệu trong thực tế thường chưa sẵn sàng cho việc khai phá dữ liệu chẳng hạn như thiếu các thuộc tính quan tâm, thiếu giá trị của thuộc tính. Vì vào thời điểm thu thập chúng không được coi là quan trọng, các dữ liệu liên quan không được ghi lại do một nguyên nhân chủ quan, hoặc do sự cố thiết bị. Ngoài ra cũng có trường hợp các dữ liệu đã được lưu trữ nhưng vì một lý do nào đó đã bị xóa đi, cũng như việc ghi chép sự biến đổi mang tính lịch sử của các giao dịch có thể bị bỏ qua mà chỉ giữ lại những thông tin tổng hợp vào thời điểm xét. Việc trùng lặp hoặc thiếu dữ liệu có thể dẫn tới việc thống kê không chính xác, thậm chí là cho một kết quả sai hay nói một cách khác dữ liệu không chất lượng cho kết quả khai phá không tốt, những quyết định đúng đắn phải dựa trên các dữ liệu chính xác, dữ liệu tốt là chìa khóa tạo ra các mô hình giá trị và đáng tin cậy. Do đó dữ liệu cần phải được tiền xử lý. Hoạt động cơ bản của giai đoạn tiền xử lý bao gồm làm sạch dữ liệu, rút gọn dữ liệu. Hai nguyên nhân của rút gọn dữ liệu là :  Dữ liệu quá lớn, không phù hợp với khả năng xử lý của chương trình.  Thời gian thực thi chương trình quá dài. Quá trình này đòi hỏi phải có một kỹ thuật phù hợp sao cho dữ liệu sau khi được rút gọn vẫn có khả năng được khai phá hiệu quả. Việc rút gọn dữ liệu bao 9 gồm các phương pháp như tổng hợp và tổng quát hóa, giảm chiều dữ liệu, nén dữ liệu, giảm số lượng các bản ghi, rời rạc hóa.  Tổng hợp dữ liệu và tổng quát hóa dữ liệu: tổ hợp từ hai thuộc tính trở lên thành một thuộc tính, tổng quát dữ liệu cấp thấp sang dữ liệu cấp cao chẳng hạn như các thành phố tổng hợp vào vùng, khu vực, nước…  Giảm chiều dữ liệu: thực hiện trích chọn đặc trưng, tìm ra tập các thuộc tính có khả năng khai phá tốt nhất loại bỏ các thuộc tính không liên quan, dư thừa bằng phương pháp vét cạn, phương pháp heuristic, cây quyết định khi đó các thuộc tính nằm trong cấu trúc cây quyết định sẽ được lựa chọn để khai phá dữ liệu. Thuộc tính nào không được đưa vào cây quyết định sẽ bị loại bỏ, do thuộc tính đó có ảnh hưởng không lớn đến kết quả.  Cách tiếp cận chính để làm giảm số bản ghi dữ liệu là lấy mẫu ngẫu nhiên. Thay vì tiến hành khai phá trên tập toàn bộ các trường hợp, các mẫu ngẫu nhiên được thu thập. Có hai cách để lấy mẫu : - Mẫu tăng dần: Phương pháp này tiến thử nghiệm với một tập mẫu lấy từ dữ liệu nguồn, dùng mẫu này để đánh giá hiệu quả. Tiếp theo lấy các mẫu với số lượng trường hợp tăng dần và so sánh độ hiệu quả với tập mẫu trước đó. Nếu hiệu quả được cải thiện thì tiếp tục quá trình lấy mẫu, ngược lại quá trình sẽ dừng. - Mẫu trung bình: nếu chương trình chỉ có khả năng xử lý N trường hợp thì lấy k mẫu, mỗi mẫu có N trường hợp để xử lý. Dữ liệu được lấy từ các mẫu trên sẽ có kích thước nhỏ hơn nhiều so với toàn bộ kho dữ liệu. Ngoài ra, việc tổng hợp các kết quả để thu được kết quả cuối có độ sai lệch thấp hơn so với chỉ lấy một tập mẫu. Nếu số mẫu lấy đủ lớn, kết quả thu được sẽ tương đương với kết quả từ việc xử lý cả kho dữ liệu. Nhiệm vụ làm sạch dữ liệu bao gồm các công đoạn: Điền các giá trị còn thiếu; xác định các sai biệt và khử dữ liệu tạp, nhiễu; sửa chữa các dữ liệu mâu thuẫn. 10 Đối với việc xử lý dữ liệu bị thiếu có một số giải pháp sau:  Bỏ qua mẫu dữ liệu đó nếu mẫu dữ liệu chứa nhiều thuộc tính thiếu giá trị.  Điền vào các giá trị thiếu bằng tay: Phương pháp này thường tốn thời gian và có thể không khả thi cho một tập dữ liệu nguồn lớn với nhiều giá trị bị thiếu.  Bổ sung các giá trị thiếu này bằng phương pháp toán học, có thể chọn một trong ba cách sau: - Thay thế giá trị thiếu bằng một hằng số chuẩn. - Thay thế giá trị thiếu bằng giá trị trung bình cùng thuộc tính. - Thay thế giá trị thiếu bằng giá trị trung bình cùng thuộc tính và lớp Phương pháp này có ưu điểm là đơn giản, nhưng có hạn chế là giá trị thay thế không phải giá trị đúng hoàn toàn. Nếu thay thế giá trị thiếu bằng một hằng số hoặc một vài giá trị định trước sẽ làm cho dữ liệu mất tính khách quan. Ví dụ nếu giá trị thiếu được thay thế bằng trung bình của thuộc tính cùng lớp sẽ làm cho các giá trị này hội tụ vào một tập tương ứng với lớp có số trường hợp bị thiếu lớn nhất.  Bổ sung các giá trị thiếu sử dụng phương pháp logic, thường sử dụng các kỹ thuật cây quyết định hoặc luật quyết định. Phương pháp này tỏ ra có ưu thế hơn phương pháp toán học do tập luật được xây dựng trên dữ liệu thực, vì thế kết quả có độ tin cậy cao hơn. Đối với việc xử lý dữ liệu nhiễu có một số giải pháp sau:  Phương pháp chia giỏ: sắp xếp và chia dữ liệu vào các giỏ theo độ rộng (chia vùng giá trị thành N khoảng cùng kích thước), hoặc theo độ sâu (chia vùng giá trị thành N khoảng mà mỗi khoảng có chứa gần như cùng số lượng mẫu). Khử nhiễu bằng giá trị trung bình, trung tuyến, biên giỏ…  Hồi quy: Phương pháp thường dùng là hồi quy tuyến tính, để tìm ra được một mối quan hệ tốt nhất giữa hai thuộc tính (hoặc các biến), từ đó một thuộc tính có thể dùng để dự đoán thuộc tính khác. 11  Phân cụm: Các giá trị tương tự nhau được tổ chức thành các nhóm hay cụm. Các giá trị rơi ra bên ngoài các nhóm này sẽ được xem xét để làm mịn. Giai đoạn 4: Chuyển đổi dữ liệu Mục đích của chuyển đổi dữ liệu là đưa dữ liệu về dạng phù hợp với thuật toán khai phá dữ liệu. Một số kỹ thuật áp dụng cho quá trình chuyển đổi dữ liệu:  Chuyển đổi kiểu dữ liệu: Đây là một kỹ thuật đơn giản nhất. Chẳng hạn như chuyển các cột dữ liệu kiểu logic sang dạng nguyên và ngược lại.  Rời rạc hóa: biến đổi miền giá trị thuộc tính liên tục thành từng khoảng, lưu nhãn của khoảng thay cho giá trị thực. Chẳng hạn như thay thế giá trị tuổi bằng các nhãn như trẻ, trung niên, già.  Nhóm: Kỹ thuật này phân loại các giá trị trong một cột thành các nhóm, sau đó ánh xạ giá trị ban đầu sang các giá trị nhóm tương ứng. Chẳng hạn cột nghề nghiệp có những giá trị khác nhau như kỹ sư cơ khí, kỹ sư công nghệ thông tin, kỹ sư xây dựng… thì chúng ta có thể nhóm chúng lại thành nhóm kỹ sư.  Tập hợp: những thông tin lưu trữ trong cơ sở dữ liệu là rất chi tiết, chúng ta có thể tập hợp chúng lại thành vài thuộc tính tổng hợp. Chẳng hạn chúng ta muốn phân loại khách hàng dựa trên những thông tin sử dụng điện thoại hàng tháng của khách hàng, chúng ta có thể tập hợp những thông tin này thành một vài thuộc tính tổng hợp như tổng số cuộc gọi hay thời gian trung bình các cuộc gọi.  Tổng quát hóa: Dữ liệu ở mức thấp (dữ liệu nguyên thủy) có thể được thay thế bằng các khái niệm ở mức cao hơn. Chẳng hạn những loài cây có thể được tổng quát ở mức cao hơn là thực vật.  Chuẩn hóa: Một thuộc tính được chuẩn hóa bằng cách ánh xạ một cách có tỉ lệ dữ liệu về một khoảng xác định ví dụ như 0.0 đến 1.0. Chuẩn hóa là một phần hữu ích của thuật toán phân lớp trong mạng 12 noron, hoặc thuật toán tính toán độ lệch sử dụng trong việc phân lớp hay nhóm cụm các phần tử liền kề. Giai đoạn 5: Chọn kỹ thuật khai phá dữ liệu Tùy thuộc vào yêu cầu của bài toán để chọn kỹ thuật khai phá phù hợp. Bao gồm các kỹ thuật khai phá như:  Phân lớp: 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 quan hệ nào đó giữa thuộc tính dự báo và thuộc tính phân lớp. Một điều cần chú ý là khác với bài toán phân cụm, dữ liệu dùng để xây dựng mô hình (Training Data) trong bài toán phân lớp phải được xác định lớp trước (pre-Labeled). Ví dụ xác định một sinh viên thuộc có nguy cơ thôi học hoặc không thôi học, hay dự đoán bệnh dựa vào các triệu trứng lâm sàng của người bệnh. Quá trình phân lớp dữ liệu thường gồm các bước: huấn luyện mô hình, kiểm thử mô hình và tính toán sai số để đánh giá mô hình. Dữ liệu gốc sẽ được chia thành 2 phần là tập dữ liệu huấn luyên để xây dựng mô hình và tập dữ liệu kiểm thử để kiểm định mô hình tương ứng với hai bước trên. Trong kỹ thuật phân lớp chúng ta có thể sử dụng các phương pháp như: cây quyết định, K – láng giềng gần nhất, mạng noron, giải thuật di truyền, mạng Bayesian, tập mờ và tập thô.  Hồi qui: 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, điểm khác nhau chính là ở chỗ thuộc tính để dự báo là liên tục chứ không phải rời rạc.  Phát hiện mẫu tuần tự: tương tự như phát hiện luật kết hợp nhưng có thêm tính thứ tự và tính thời gian. Hướng tiếp cận này có tính dự báo cao.  Phân cụm: Mục tiêu chính của việc 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 mức độ tương tự nhau trong cùng một cụm là lớn nhất và mức độ tương tự nhau giữa các đối 13