ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC BÁCH KHOA HOÀNG THỊ HỒNG VÂN KHÁM PHÁ LUẬT KẾT HỢP ĐỊNH LƯỢNG HƯỚNG THỜI GIAN TRONG HỆ GIÁO DỤC THEO QUY CHẾ TÍN CHỈ Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số: 60.48.01 LUẬN VĂN THẠC SĨ TP HỒ CHÍ MINH, tháng năm 2014 CƠNG TRÌNH ĐƯỢC HỒN THÀNH TẠI TRƯỜNG ĐẠI HỌC BÁCH KHOA –ĐHQG –HCM Cán hướng dẫn khoa học : TS Nguyễn Hứa Phùng, TS Võ Thị Ngọc Châu Cán chấm nhận xét : PGS.TS Lê Hoài Bắc Cán chấm nhận xét : TS Nguyễn Chánh Thành Luận văn thạc sĩ bảo vệ Trường Đại học Bách Khoa, ĐHQG Tp HCM ngày 17 tháng 07 năm 2014 Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm: GS.TS Cao Hoàng Trụ PGS.TS Lê Hoài Bắc TS Nguyễn Chánh Thành TS Võ Thị Ngọc Châu TS Nguyễn Đức Thái Xác nhận Chủ tịch Hội đồng đánh giá LV Trưởng Khoa quản lý chuyên ngành sau luận văn sửa chữa (nếu có) CHỦ TỊCH HỘI ĐỒNG TRƯỞNG KHOA ĐẠI HỌC QUỐC GIA TP.HCM TRƯỜNG ĐẠI HỌC BÁCH KHOA CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập - Tự - Hạnh phúc NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ tên học viên: HOÀNG THỊ HỒNG VÂN MSHV: 12070557 Ngày, tháng, năm sinh: 17/03/1981 Nơi sinh: Hà Nam Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số : 60.48.01 I TÊN ĐỀ TÀI: Khám phá luật kết hợp định lượng hướng thời gian hệ giáo dục theo quy chế tín II NHIỆM VỤ VÀ NỘI DUNG: Tìm hiểu lý thuyết, cơng trình nghiên cứu liên quan đến toán khai phá luật kết hợp, khai phá luật định lượng, khai phá luật kết hợp hướng thời gian, khai phá luật kết hợp tập liệu gia tăng khai phá luật kết hợp lĩnh vực giáo dục Đề xuất giải pháp khả thi giải toán khai phá luật kết hợp định lượng hướng thời gian hệ giáo dục theo quy chế tín Tìm giải pháp cho tốn tập liệu gia tăng Tiến hành thực nghiệm, phân tích kết thu từ giải pháp khai phá gia tăng đề tài với giải pháp khai phá từ đầu Từ đó, chúng tơi đánh giá hiệu suất, chi phí giải pháp đề tài III NGÀY GIAO NHIỆM VỤ : 20/01/2014 IV NGÀY HOÀN THÀNH NHIỆM VỤ: 20/6/2014 V CÁN BỘ HƯỚNG DẪN: TS Nguyễn Hứa Phùng -TS Võ Thị Ngọc Châu Tp HCM, ngày 20 tháng năm 2014 CÁN BỘ HƯỚNG DẪN TRƯỞNG KHOA (Họ tên chữ ký) (Họ tên chữ ký) TS Võ Thị Ngọc Châu i LỜI CẢM ƠN Tôi xin gửi lời cảm ơn chân thành sâu sắc đến TS Nguyễn Hứa Phùng TS Võ Thị Ngọc Châu, khoa Khoa Học – Kỹ Thuật Máy Tính - Đại Học Bách Khoa TP.HCM Trong suốt trình thực đề cương luận văn cao học, thầy cô tận tình hướng dẫn giúp đỡ, tạo điều kiện để tơi hồn thành tốt luận văn Tôi xin gửi lời cảm ơn chân thành đến Thầy Cô khoa Khoa Học – Kỹ Thuật Máy Tính, trường Đại Học Bách Khoa TPHCM Các Thầy Cơ tận tình dạy, trang bị cho kiến thức quý báu suốt thời gian học cao học trường Tôi xin gửi lời cảm ơn đến gia đình, bạn bè đồng nghiệp hỗ trợ thời gian tinh thần, tạo điều kiện thuận lợi giúp tơi hồn thành luận văn Trong thời gian thực luận văn, hỗ trợ giúp đỡ thầy cô, gia đình, bạn bè đồng nghiệp, với cố gắng nỗ lực thân, tơi hồn thành luận văn với hết khả Mặc dù vậy, luận văn không tránh khỏi thiếu sót, kính mong q Thầy Cơ bạn tận tình bảo, góp ý để luận văn hồn thiện Tp HCM, ngày 20 tháng năm 2014 Học viên Hồng Thị Hồng Vân ii TĨM TẮT LUẬN VĂN Khai phá tri thức khai phá liệu ứng dụng rộng rãi nhiều lĩnh vực thương mại, y tế, giáo dục Một kỹ thuật khai phá liệu quan trọng then chốt lĩnh vực kỹ thuật khai phá luật kết hợp Đặc biệt, khai phá luật kết hợp lĩnh vực giáo dục lên ứng dụng quan trọng, hữu ích việc áp dụng quy trình khai phá liệu vào thực tế để nâng cao chất lượng giáo dục, chất lượng quản lý giáo dục Trong năm gần đây, việc áp dụng học chế tín đào tạo đại học nước ta với ưu điểm giúp bạn sinh viên linh động việc học việc lên kế hoạch học tập cho thân để đạt kết tốt nhất, phù hợp với khả bạn sinh viên Để hỗ trợ bạn sinh viên việc định lựa chọn môn học năm học then chốt đại học, nghiên cứu kỹ thuật khai phá luật kết hợp áp dụng vào liệu giáo dục để giải toán: “Khám phá luật kết hợp định lượng, hướng thời gian hệ giáo dục theo quy chế tín chỉ” Trong luận văn này, tập trung giải việc vấn đề tính định lượng tính thời gian liệu giáo dục để khai phá luật kết hợp định lượng, hướng thời gian hàm chứa nhiều thơng tin, tri thức hữu ích hơn, rõ ràng so với luật kết hợp luận lý thông thường Các tri thức khai phá giúp ích nhiều cho bạn sinh viên đại học hệ tín việc lập kế hoạch học tập Dữ liệu giáo dục - cụ thể liệu điểm sinh viên - có đặc điểm gia tăng theo học kỳ, năm học Do đó, đề tài nghiên cứu kỹ thuật khai phá luật kết hợp liệu gia tăng để áp dụng vào tốn đề tài nhằm tìm giải pháp tốt hơn, hiệu việc giải tốn Giải pháp thuật tốn TCISpan, khai phá mẫu định lượng hướng thời gian tập liệu gia tăng Khi liệu thêm mới, thuật toán sử dụng kết khai phá có, kết hợp với việc khai phá từ phần liệu thêm vào nhằm giảm chi phí thời gian so với giải pháp khai phá tập liệu từ đầu iii ABSTRACT Mining knowledge as well as data mining is widely used in many fields such as trade, health, education One of the important data mining techniques playing key role in these fields is association rule mining Especially, association rule mining in education today is emerging as a critical and useful application in applying the process of data mining to life to improve the educational quality, educational management quality In recent years, the application of the credit system with its advantages in higher education in our country has helped students study as well as plan their study more flexibly to achieve the best results matching each student’s ability To assist students in decision-making in course registration during the critical years of college, we studied association rule mining technique from eductional data to solve the problem: “Quantitative temporal association rule mining in an academic credit system” In this thesis, we focus on mining quantitative temporal association rules in educational databases which are more useful than traditional boolean association rules The knowledge contained in these rules will be very helpful for students in study planning Educational data - particularly studying result data of students - increase every semester, every year Therefore, we also research techniques of association rule mining from incremental datasets to propose a better, more effective algorithm in solving the thesis problem The solution is TCISpan algorithm, mining quantitative temporal patterns from incremetal datasets When the content of a dataset changes, TCISpan reuses the mining results of the original dataset and examines the incremental part in order to save processing time as compared to mining the entire updated dataset from scratch iv LỜI CAM ĐOAN Tôi xin cam đoan ngồi kết quả, thơng tin tham khảo từ cơng trình khác ghi rõ luận văn, cơng việc, kết trình bày luận văn tơi thực chưa sử dụng để lấy cấp, chứng khác Tp HCM, ngày 20 tháng năm 2014 Học viên Hoàng Thị Hồng Vân v MỤC LỤC NHIỆM VỤ LUẬN VĂN THẠC SĨ i LỜI CẢM ƠN ii TÓM TẮT LUẬN VĂN iii ABSTRACT iv LỜI CAM ĐOAN v MỤC LỤC vi DANH MỤC HÌNH ix DANH MỤC BẢNG x Chương 1: GIỚI THIỆU 1.1 Giới thiệu đề tài 1.2 Mục tiêu phạm vi nghiên cứu đề tài 1.3 Ý nghĩa đề tài 1.3.1 Ý nghĩa khoa học 1.3.2 Ý nghĩa thực tiễn đề tài 1.4 Phương pháp nghiên cứu Chương 2: CƠ SỞ LÝ THUYẾT 2.1 Các khái niệm luật kết hợp 2.1.1 Khai phá dãy phổ biến 2.1.2 Thuật toán GSP – khai phá dãy phổ biến dựa Apriori 10 2.1.3 Thuật toán PrefixSpan – khai phá dãy phổ biến dựa phép chiếu 10 2.1.4 Khai phá luật kết hợp định lượng 12 2.1.5 Khai phá luật kết hợp hướng thời gian 13 2.1.6 Khai phá luật kết hợp CSDL gia tăng 15 2.1.7 Đánh giá luật kết hợp dựa độ đo 16 Chương 3: TỔNG QUAN VỀ CÁC CƠNG TRÌNH LIÊN QUAN 20 3.1 Các cơng trình khai phá luật kết hợp giáo dục 20 3.1.1 “Ứng dụng khai phá liệu để tư vấn học tập trường cao đẳng kinh tế kỹ thuật Quảng Nam” - Phạm Cẩm Vân 20 3.1.2 “Khai phá liệu cho tư vấn lựa chọn môn học” - Phạm Thị Phúc 21 vi 3.1.3 “Discovery of Association Rules from University Admission System Data” Abdul Fattah Mashat et al 22 3.1.4 “Mining Educational Data to Improve Students’ Performance: A Case Study” - Mohammed M Abu Tair, Alaa M El-Halees 23 3.1.5 “Association Rule Mining in Learning Management Systems” - Enrique García1 et al 24 3.1.6 “Mining Postgraduate Students’ Data Using Apriori Algorithm” - Yousef Ibrahim Abu Zawayda 26 3.1.7 “Educational Data Mining: a Case Study” - Agathe Merceron, Kalina Yacef 27 3.1.8 Tổng kết nhận xét 29 3.2 Các cơng trình liên quan đến thuật toán đề tài 32 3.2.1 Thuật toán Hirate & Yamana 32 3.2.2 Thuật toán CISpan 33 3.2.3 Nhận xét 35 CHƯƠNG 4: PHÁT BIỂU BÀI TOÁN 37 4.1 Các định nghĩa, khái niệm 37 4.2 Bài toán 38 4.3 Các bước giải toán 38 4.3.1 Tiền xử lý liệu 39 4.3.2 Tìm tập phổ biến 40 4.3.3 Sinh luật kết hợp 41 Chương 5: ĐỀ XUẤT THUẬT TOÁN 43 5.1 Các định nghĩa 43 5.2 Khai phá tập mẫu định lượng hướng thời gian -Thuật toán TCISpan 46 5.2.1 Các kí hiệu sử dụng thuật tốn 46 5.2.2 Thuật toán 47 5.2.3 Ví dụ 50 5.2.4 So sánh thuật toán TCISpan Hirate & Yamana 54 5.3 Tìm tập luật từ tập phổ biến khai phá 54 5.3.1 Thủ tục Mining from list 55 5.3.2 Thủ tục Mining from tree 56 5.3.3 Ví dụ 57 vii 5.3.4 So sánh thủ tục Mining from list thủ tục Mining from tree 58 5.4 Lọc luật sử dụng độ đo 58 5.5 Minh họa tập liệu, tập mẫu, tập luật đề tài 59 5.5.1 Ví dụ tập liệu 59 5.5.2 Ví dụ tập mẫu 60 5.5.3 Ví dụ tập luật 60 Chương 6: KẾT QUẢ THỰC NGHIỆM VÀ ĐÁNH GIÁ 63 6.1 Quy trình thực nghiệm 63 6.2 Chuẩn bị liệu cho thực nghiệm 64 6.2.1 Định dạng liệu điểm sinh viên ban đầu 64 6.2.2 Định dạng liệu đầu vào thuật toán 65 6.2.3 Tiền xử lý liệu sử dụng cho thuật toán 65 6.3 Chuẩn bị thực nghiệm 66 6.3.1 Môi trường thực nghiệm 66 6.3.2 Tập liệu 66 6.4 Kết thực nghiệm đánh giá 68 6.4.1 Thực nghiệm lựa chọn giá trị min_sup, min_conf 68 6.4.2 Thực nghiệm so sánh hai giải pháp đề tài tập liệu thực 75 6.5 Kết luận 84 Chương 7: TỔNG KẾT 85 7.1 Những công việc thực 85 7.2 Hướng phát triển 86 TÀI LIỆU THAM KHẢO 87 viii Từ kết này, chúng tơi có số nhận xét sau:  Tập liệu sử dụng nhiều nhãn thời gian (học kỳ 5, 6) số lượng mẫu sinh lớn đa dạng cặp (item, timestamp)  Với giá trị min_sup, min_conf tập liệu khác cho số lượng mẫu, số lượng luật chênh lệch lớn Việc lựa chọn giá trị min_sup, min_conf tùy thuộc vào mục đích, tiêu chí người sử dụng Do giai đoạn từ kỳ đến kỳ 6, sinh viên bắt đầu bước vào giai đoạn học môn tự chọn theo sở thích lực bạn sinh viên, nên giai đoạn sinh viên cần đưa định lựa chọn môn học phù hợp với khả thân dựa kết đạt từ kì 1, 2, Do đó, đề tài tập trung vào khai phá tập liệu điểm sinh viên từ kì đến kì 6, nhằm hỗ trợ cho bạn sinh viên việc định đăng kí mơn học phù hợp với lực thời điểm quan trọng kì kỳ khóa học 6.4.2 Thực nghiệm so sánh hai giải pháp đề tài tập liệu thực Đề tài đưa hai giải pháp để giải toán đề tài Giải pháp thứ sử dụng thuật toán Hirate & Yamana (không gia tăng) để khai phá mẫu lưu mẫu khai phá danh sách, sau khai phá luật từ danh sách mẫu Giải pháp thứ 2, phát triển thuật toán TCISpan (khai phá gia tăng) để khai phá mẫu tập liệu gia tăng lưu mẫu tiền tố theo cấu trúc tiền tố đề tài (Định nghĩa - Mục 5.1), tập luật khai phá từ tập mẫu lưu tiền tố Chúng tiến hành thực nghiệm nhằm so sánh thời gian thực thi dung lượng sử dụng nhớ hai cách tiếp cận bốn trường hợp:  Trường hợp thứ nhất: min_sup, min_conf không thay đổi, liệu thay đổi  Trường hợp thứ hai: min_sup thay đổi, liệu không thay đổi, thực nghiệm với tập liệu gia tăng thêm ghi  Trường hợp thứ ba: min_sup thay đổi, liệu không thay đổi, thực nghiệm với tập liệu gia tăng cập nhật ghi  Trường hợp thứ tư: min_sup thay đổi, liệu không thay đổi, thực nghiệm với tập liệu gia tăng xóa bỏ ghi 75 Từ kết thực nghiệm, đánh giá, nhận xét ưu, khuyết điểm giải pháp lựa chọn giải pháp phù hợp tập liệu Đối với trường hợp thực nghiệm thứ ba thứ tư, thực tập liệu chúng tơi tự cập nhật xóa bỏ ghi để đánh giá thêm thuật toán TCISpan so với thuật toán Hirate & Yamana Kết thực nghiệm để tham khảo thêm Để đảm bảo kết đáng tin cậy tiến hành chạy 110 lần với tham số, sau bỏ 10 kết lấy giá trị trung bình trăm lần chạy sau làm kết cuối Trong bảng kết thực nghiệm sau đây, tỉ lệ so sánh tính theo tham số thuật toán Hirate & Yamana/tham số tương ứng thuật toán TCISpan Quy ước từ viết tắt sử dụng bảng kết thực nghiệm sau: Bảng - 10: Các từ viết tắt sử dụng bảng kết thực nghiệm Từ viết tắt Ý nghĩa Proj Số phép chiếu thực thuật toán PTime Thời gian khai phá tập phổ biến mili giây (ms) Rtime Thời gian khai phá tập luật từ tập phổ biến mili giây (ms) TTime Tổng thời gian khai phá = PTime + Ttime mili giây (ms) Mem Dung lượng nhớ sử dụng cho thuật toán megabyte (mb) 6.4.2.1 Đơn vị đo Trường hợp thứ Như trình bày phần chuẩn bị liệu, chúng tơi tiến hành gộp khóa theo học kỳ thực nghiệm sáu học kỳ, từ học kỳ đến học kỳ Theo kết thực nghiệm trước, chọn giá trị min_sup 0.03, min_conf = 0.4 số lượng tập mẫu, tập luật đầu tập liệu đầu vào đủ lớn để so sánh, đánh giá chi phí thời gian nhớ giải pháp Kết thực nghiệm liệt kê bảng sau: 76 Bảng - 11: Kết thực nghiệm trường hợp thứ Dữ liệu gốc 5_1 56_1 567_1 5_2 56_2 567_2 5_3 56_3 567_3 5_4 56_4 567_4 5_5 56_5 567_5 5_6 56_6 567_6 Dữ liệu cập nhật 5_1 56_1 567_1 5678_1 5_2 56_2 567_2 5678_2 5_3 56_3 567_3 5678_3 5_4 56_4 567_4 5678_4 5_5 56_5 567_5 5678_5 5_6 56_6 567_6 5678_6 TCISpan Proj 22 18 16 15 107 17 69 131 97 24 112 471 134 43 193 1403 163 58 310 3073 197 87 545 7176 Hirate Yamana Proj 22 23 20 23 107 46 72 136 97 53 113 473 134 72 193 1403 163 84 310 3073 197 113 545 7176 TCISpan PTime (ms) ≈0 0.15 0.48 1.09 1.10 0.94 3.44 9.51 1.40 1.53 10.77 46.33 1.27 2.17 19.80 180.33 3.44 2.82 47.42 628.53 3.41 5.65 104.47 1856.36 Hirate & Yamana PTime (ms) 0.31 0.48 1.09 1.25 1.73 1.26 4.52 12.01 2.51 2.18 12.15 63.17 2.96 2.50 28.70 246.36 3.72 4.68 63.81 817.92 6.09 7.36 134.92 2317.38 TCISpan Rtime (ms) ≈0 ≈0 ≈0 ≈0 ≈0 0.16 ≈0 0.16 ≈0 ≈0 ≈0 0.47 ≈0 0.16 ≈0 4.39 0.15 ≈0 0.63 10.90 0.93 ≈0 2.18 32.45 Hirate Yamana RTime (ms) 0.16 0.00 0.00 0.00 0.91 0.45 0.63 2.02 0.63 0.47 1.08 23.25 2.02 0.00 3.60 282.04 3.14 1.42 12.93 1887.92 4.51 1.71 48.69 14299.60 TCISpan Ttime (ms) ≈0 0.15 0.48 1.09 1.10 1.10 3.44 9.67 1.40 1.53 10.77 46.80 1.27 2.33 19.80 184.72 3.59 2.82 48.05 639.43 4.34 5.65 106.65 1888.81 77 Hirate Yamana TTime (ms) 0.47 0.48 1.09 1.25 2.64 1.71 5.15 14.03 3.14 2.65 13.23 86.42 4.98 2.50 32.30 528.40 6.86 6.10 76.74 2705.84 10.60 9.07 183.61 16616.98 TCISpan Mem (mb) 142.03 135.03 141.07 148.34 139.22 136.97 126.48 126.50 126.28 117.84 119.70 165.98 145.08 148.31 138.58 202.24 151.56 147.73 180.10 202.50 175.66 179.50 199.08 226.46 Hirate & Yamana Mem (mb) 110.26 66.70 173.93 92.90 139.79 116.53 114.40 140.57 172.49 170.54 165.93 184.15 202.44 181.84 182.63 177.68 218.12 210.08 155.56 208.42 182.97 188.24 199.07 158.73 Tỉ lệ Proj 1.00 1.28 1.25 1.53 1.00 2.71 1.04 1.04 1.00 2.21 1.01 1.00 1.00 1.67 1.00 1.00 1.00 1.45 1.00 1.00 1.00 1.30 1.00 1.00 Tỉ lệ PTime -3.20 2.27 1.15 1.57 1.34 1.31 1.26 1.79 1.42 1.13 1.36 2.33 1.15 1.45 1.37 1.08 1.66 1.35 1.30 1.79 1.30 1.29 1.25 Tỉ lệ RTime -2.81 -12.63 -49.47 -0.00 -64.25 20.93 -20.52 173.20 4.85 -22.33 440.67 Tỉ lệ TTime -3.20 2.27 1.15 2.40 1.55 1.50 1.45 2.24 1.73 1.23 1.85 3.92 1.07 1.63 2.86 1.91 2.16 1.60 4.23 2.44 1.61 1.72 8.80 Tỉ lệ Mem 0.78 0.49 1.23 0.63 1.00 0.85 0.90 1.11 1.37 1.45 1.39 1.11 1.40 1.23 1.32 0.88 1.44 1.42 0.86 1.03 1.04 1.05 1.00 0.70 Nhận xét kết thực nghiệm trường hợp thứ nhất:  Thời gian thực thi: Trong hầu hết trường hợp, thời gian thực thi giải pháp sử dụng thuật toán TCISpan nhỏ thời gian thực thi giải pháp sử dụng thuật toán Hirate & Yamana (trường hợp tốt chi phí thời gian TCISpan nhỏ gần lần so với Hirate & Yamana) Thời gian thực thi TCISpan vượt trội so với thuật toán Hirate & Yamana tập liệu có số lượng giao dịch lớn, sử dụng nhiều nhãn thời gian khác Điều chi phí khai phá tập luật từ tiền tố thuật toán TCISpan nhỏ nhiều so với chi phí khai phá tập luật từ tập phổ biến thuật toán Hirate & Yamana Chi phí khai phá mẫu TCISpan hầu hết trường hợp nhỏ chi phí khai phá mẫu Hirate & Yamana số lượng phép chiếu TCISpan hầu hết nhỏ số lượng phép chiếu Hirate & Yamana  Chi phí nhớ: Chi phí nhớ giải pháp gần nhau, TCISpan tiết kiệm không gian nhớ để lưu CSDL chiếu so với Hirate & Yamana, lại thêm không gian nhớ để lưu cấu trúc tiền tố 6.4.2.2 Trường hợp thứ hai Để thấy tác dụng việc xử lý gia tăng, định chọn tập liệu học kỳ bốn khóa 2005, 2006, 2007, 2008 Tập liệu gốc 567_6, tập liệu sau thêm 5678_6 tập liệu có số lượng giao dịch nhiều nhất, số lượng thuộc tính lớn Giá trị min_conf = 0.6, min_sup thay đổi khoảng từ 0.02 đến 0.2, bước nhảy 0.01 Kết thực nghiệm trình bày bảng sau: 78 Bảng - 12: Kết thực nghiệm trường hợp thứ hai min_ sup TCISpan Proj 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1 137234 7176 1262 319 167 95 52 36 26 Hirate & Yamana Proj TCISpan PTime (ms) Hirate & Yamana PTime (ms) 137236 18116.92 25226.00 7176 1834.93 2236.62 1262 438.69 593.23 319 152.24 220.63 167 77.20 118.95 95 53.13 83.17 52 36.03 57.87 36 24.32 40.69 26 19.98 30.26 TCISpan Mem (mb) Hirate & Yamana Mem (mb) Tỉ lệ Proj Tỉ lệ PTime 881.69 6529098.00 18998.61 6554324.00 383.09 29.93 14068.38 1864.86 16305.00 185.17 3.28 283.15 441.97 876.38 204.0012 0.47 14.48 152.71 235.11 218.06 0.30 4.47 77.50 123.42 223.09 ≈0 1.54 53.13 84.71 218.51 ≈0 0.62 36.03 58.49 212.2924 0.32 0.00 24.64 40.69 196.79 0.16 0.93 20.14 31.19 186.16 553.13 136.19 175.72 174.17 172.22 174.33 170.59 139.44 137.81 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.39 1.22 1.35 1.45 1.54 1.57 1.61 1.67 1.51 TCISpan RTime (ms) Hirate Yamana RTime (ms) TCISpan TTime (ms) 79 Hirate & Yamana TTime (ms) Tỉ lệ RTime Tỉ lệ TTime Tỉ lệ Mem 7405.21 344.99 470.04 8.74 86.33 1.98 30.81 1.54 14.90 1.59 -1.59 -1.62 0.00 1.65 5.81 1.55 1.44 0.74 0.86 0.80 0.77 0.80 0.80 0.71 0.74 Nhận xét kết thực nghiệm trường hợp thứ hai:  Thời gian thực thi: Thời gian thực thi khai phá mẫu TCISpan trung bình nhanh gấp 1.48 lần so với thuật tốn Hirate & Yamana Thêm vào đó, thời gian khai phá luật TCISpan nhanh nhiều lần so với thuật toán Hirate & Yamana, đặc biệt giá trị min_sup nhỏ, số lượng mẫu lớn Điều giải thích sau: Chi phí khai phá luật thuật toán Hirate & Yamana O(n2), chi phí khai phá luật thuật tốn TCISpan O(nk) (n số lượng mẫu, k số node trung bình con) Khi số lượng mẫu lớn (n lớn), giá trị k nhỏ nhiều so với n Ngồi ra, thuật tốn Hirate & Yamana phải thêm chi phí kiểm tra dãy có tiền tố dãy khác khơng (chi phí lớn số lượng mẫu tăng lên), TCISpan khơng chi phí kiểm tra  Chi phí nhớ: Trong hầu hết trường hợp, chi phí nhớ thuật tốn Hirate & Yamana nhỏ chi phí nhớ thuật toán TCISpan, giá trị min_sup nhỏ (0.02), số lượng mẫu khai phá lớn TCISpan lại tiết kiệm nhớ Hirate & Yamana Trong thuật toán Hirate & Yamana, mẫu khai phá lưu danh sách Khi số lượng mẫu tăng lên, danh sách mẫu lớn nên cần nhiều dung lượng nhớ để lưu danh sách Trong đó, TCISpan lưu mẫu khai phá tiền tố Khi thêm mẫu vào,TCISpan chi phí nhớ để lưu nút thêm vào mà không cần lưu toàn mẫu khai phá 6.4.2.3 Trường hợp thứ ba Ngoài việc xử lý gia tăng thao tác thêm liệu, TCISpan khai phá gia tăng tập liệu có ghi cập nhật Để tiến hành thực nghiệm với trường hợp cập nhật liệu, chọn tập liệu học kỳ bốn khóa 2005, 2006, 2007, 2008 làm tập liệu gốc (5678_6.txt), sau cập nhật sửa đổi số ghi tập liệu (cụ thể 10 ghi cuối cùng) lưu tập liệu 5678_6_update Chọn giá trị min_conf = 0.6, min_sup thay đổi khoảng từ 0.02 đến 0.2, bước nhảy 0.01 Kết thực nghiệm với hai giải pháp trình bày bảng sau: 80 Bảng - 13: Kết thực nghiệm trường hợp thứ ba min_ sup 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.10 TCISpan Proj 73732 4841 916 270 145 82 48 32 22 Hirate & Yamana PTime (ms) TCISpan RTime (ms) 130718 13483.46 24336.00 7109 1579.47 2039.10 1258 426.55 576.85 319 147.36 216.21 166 78.48 124.49 95 54.18 88.45 52 36.53 61.26 36 23.77 40.97 26 19.76 32.77 847.06 27.78 4.02 0.67 0.30 0.07 0.06 0.04 0.24 Hirate & Yamana Proj TCISpan PTime (ms) Hirate & Yamana RTime (ms) TCISpan TTime (ms) Hirate & Yamana TTime (ms) 10804277 13902.70 263.79 14.22 4.35 1.23 0.36 0.16 0.44 14330.52 1607.25 430.57 148.03 78.78 54.25 36.59 23.81 20.00 10828613 15941.80 840.64 230.43 128.84 89.68 61.62 41.13 33.21 81 TCISpan Mem (mb) Hirate & Yamana Mem (mb) 407.34 209.65 196.79 224.51 226.37 226.67 164.40 159.88 199.55 444.20 133.18 181.74 205.10 205.33 204.04 208.01 208.29 145.73 Tỉ lệ Proj 1.77 1.47 1.37 1.18 1.14 1.16 1.08 1.13 1.18 Tỉ lệ PTime Tỉ lệ RTime Tỉ lệ TTime Tỉ lệ Mem 1.80 1.29 1.35 1.47 1.59 1.63 1.68 1.72 1.66 12755.03 500.46 65.62 21.22 14.50 17.57 6.00 4.00 1.83 755.63 9.92 1.95 1.56 1.64 1.65 1.68 1.73 1.66 1.09 0.64 0.92 0.91 0.91 0.90 1.27 1.30 0.73 Nhận xét kết thực nghiệm trường hợp thứ ba:  Thời gian thực thi: Khi số lượng giao tác cập nhật chiếm tỉ lệ nhỏ so với tồn CSDL chi phí khai phá tập phổ biến từ đầu thuật toán Hirate & Yamana cao chi phí khai phá tập phổ biến gia tăng thuật toán TCISpan số phép chiếu cần thực thuật toán Hirate & Yamana lớn số phép chiếu cần thực thuật toán TCISpan  Thời gian khai phá luật chi phí nhớ hai giải pháp giống với trường hợp thực nghiệm thứ hai 6.4.2.4 Trường hợp thứ tư Đối với thao tác xóa ghi, TCISpan khai phá gia tăng tập liệu xóa ghi trường hợp tham số đưa vào giá trị min_count (thay cho giá trị min_sup) Trong trường hợp xóa ghi, sử dụng giá trị min_sup, xảy trường hợp số mẫu không phổ biến CSDL ban đầu (D), trở thành phổ biến CSDL (D’) sau xóa bỏ số ghi Các mẫu không lưu lại kết khai phá trước nên TCISpan khơng khai phá Ví dụ: Với min_sup = 0.5, giả sử D có 10 ghi, min_count = 0.5x10 = Các mẫu khai phá từ D có support_count >=5 Khi xóa ghi D để thu D’ có ghi, min_count = 0.5x8 = 4, nghĩa mẫu khai phá từ D’ có support_count >=4 Nếu sử dụng kết khai phá có từ D, số mẫu D có 4=