1. CẢI TIẾN THUẬT TOÁN KHAI PHÁ DỮ LIỆU TUẦN TỰ CMSPAM CHO TRƯỜNG HỢP DỮ LIỆU THƯA Nguyễn Mạnh Sơn *, Đặng Ngọc Hùng+ * Khoa CNTT1 – Học Viện Công Nghệ Bưu Chính Viễn Thông Email: sonnm@ptit.edu.vn + Khoa CNTT1 – Học Viện Công Nghệ Bưu Chính Viễn Thông Email: hungdn@ptit.edu.vn Abstract — Khai phá mẫu tuần tự (SPM) nhiều lĩnh vực khác như phân tích DNA, tư được ứng dụng rộng rãi trong các bài toán vấn điều trị bệnh, dự báo thiên tai, phân tích thương mại điện tử và ra quyết định. Các mẫu truy cập website …. thuật toán SPM tiêu biểu đã được áp dụng Phần lớn các thuật toán ban đầu cho bài trong nhiều hệ thống tư vấn, dự báo … như GSP, SPAM, CMSPAM. Bài báo sẽ phân tích toán khai phá mẫu tuần tự đều dựa trên tính ưu nhược điểm của các thuật toán và đề xuất chất Apriori được sử dụng trong khai phá một cải tiến cho thuật toán CMSPAM. Thuật luật kết hợp ([1],[2],[3]). Tính chất này cho toán cải tiến được đặt tên là CMSPAME cho rằng: mọi mẫu con (sub-pattern) của một hiệu quả tốt hơn đối với trường hợp dữ liệu mẫu phổ biến (frequent pattern) cũng chính thưa và vẫn giữ nguyên được hiệu năng như là một mẫu phổ biến. Dựa trên tính chất này, thuật toán CMSPAM trong các trường hợp rất nhiều các thuật toán được đề xuất như: khác. AprioriAll, AprioriSome, DynamicSome (Agrawal và Srikan 1995), GSP (Skrikant và Keywords— Khai phá dữ liệu tuần tự, SPM, Agrawal 1996) với phương pháp định dạng cải tiến CMSPAM, thuật toán CMSPAME. bộ nhớ theo chiều ngang (horizontal database format) ([2],[3]). Tuy nhiên khi các I. GIỚI THIỆU CSDL ngày càng lớn, thì phương pháp định Bài toán khai phá mẫu tuần tự (Sequential dạng bộ nhớ theo chiều ngang tỏ ra thiếu Pattern Mining - SPM) được R. Agrawal và hiệu quả [3]. Các phương pháp định dạng bộ R. Srikant giới thiệu vào năm 1995 [1]. Cho nhớ theo chiều dọc (vertical database một tập các dãy tuần tự, trong đó mỗi dãy format) mà tiêu biểu là thuật toán SPAM bao gồm một tập các giao dịch, và mỗi giao (Sequential PAttern Mining using A Bitmap dịch bao gồm một tập các phần tử, cùng một Representation) [4] với ý tưởng chính là sử ngưỡng phổ biến (minsup), khai phá mẫu dụng bitmap để lưu trữ CSDL đồng thời hỗ tuần tự tìm ra tất cả các chuỗi (subsequence) trợ tính toán giá trị hỗ trợ mà không phải phổ biến, là dãy tuần tự xuất hiện trong tập quét lại CSDL. Các thử nghiệm cho thấy dữ liệu với tần số không nhỏ hơn ngưỡng SPAM tìm được toàn bộ kết quả trùng khớp phổ biến. SPM ngày càng được sử dụng rộng với thuật toán GSP nhưng với tốc độ nhanh rãi trong thương mại điện tử (phân tích, dự hơn đáng kể [4]. báo xu hướng mua sắm, quản lý kho hàng, Các thuật toán sử dụng bitmap sau này như …) và cũng được ứng dụng hiệu quả cho Số 02 & 03 (CS.01) 2017 TẠP CHÍ KHOA HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 71
  2. CMSPAM(2014) và CMSPADE(2014) đều người dùng có thể cách xa nhau về mặt thời dựa trên ý tưởng của SPAM ([5],[6],[7]). gian. Và như vậy, nói chung các hệ thống Cơ sở dữ liệu bitmap theo chiều dọc thương mại điện tử sẽ đều gặp phải trường (Vertical Database Bitmap-VDB) có thể hợp dữ liệu thưa, tức là số giao dịch trung được hiểu đơn giản là một CSDL mà mỗi bình trên một người dùng và số sản phẩm hàng đại diện cho một item và đưa ra danh trung bình trong một lần giao dịch không sách thứ tự xuất hiện của item đó trong cao. CSDL Thuật toán cải tiến được chúng tôi đặt tên Thuật toán SPAM có 3 điểm đáng chú ý là CMSPAME đưa ra một số thay đổi riêng [4]: cho trường hợp dữ liệu thưa. Các thử nghiệm SPAM sử dụng bitmap để lưu trữ cơ sở dữ đã được thực hiện trên bộ dữ liệu chuẩn của liệu theo chiều dọc: đặc điểm này giúp tính P. Fournier-Viger [8] và cho ra kết quả tốt toán giá trị hỗ trợ cho mỗi item một cách hơn khá rõ ràng về mặt hiệu năng (thời gian nhanh chóng mà không cần duyệt lại toàn bộ chạy thuật toán). cơ sở dữ liệu như các thuật toán sử dụng cơ sở dữ liệu theo chiều ngang. Việc sử dụng II. THUẬT TOÁN KHAI PHÁ DỮ LIỆU bitmap để lưu trữ dữ liệu giúp giảm kích CMSPAM thước bộ nhớ và tăng khả năng tính toán cho Thuật toán CMSPAM được đưa ra với các phép cắt tỉa chuỗi tuần tự của thuật toán. mục tiêu giảm bớt số lượng ứng cử được SPAM sử dụng các phép mở rộng S-step, sinh ra trong mỗi bước mà vẫn đảm bảo kết I-Step và các phép cắt tỉa S-Step Pruning, I- quả đúng đắn. Step Pruning để tăng tốc độ xử lý. Phương Thay vì phải sinh ra tập ứng cử sau mỗi pháp này giúp cho thuật toán sinh ra ít ứng bước mở rộng của thuật toán SPAM, cử viên hơn và vẫn đảm bảo tính chính xác. CMSPAM sẽ sinh ra tập ứng cử có thể cho SPAM kiểm tra các ứng cử thỏa mãn giá trị mỗi item ngay sau khi quét CSDL mà vẫn minsup một cách nhanh chóng thông qua các đảm bảo không bỏ sót bất cứ ứng viên thích phép toán trên dãy bit. hợp nào. Như vậy CMSPAM sẽ làm giảm Tập ứng cử của thuật toán SPAM vẫn chi phí bộ nhớ cũng như giảm thời gian thực chưa tối ưu. Tuy giảm thiểu được số lượng hiện của thuật toán. lớn các ứng viên sinh ra sau mỗi bước nhờ các phép mở rộng, tập ứng cử của thuật toán Thuật toán CMSPAM SPAM vẫn chứa nhiều giá trị không phổ Input Một cơ sở dữ liệu tuần tự S và biến, hoặc không xuất hiện trong CSDL. giá trị ngưỡng phổ biến Năm 2014 các nhà khoa học P. Fournier- Output Tập đầy đủ các mẫu tuần tự F Pamameters: Viger, A. Gomariz, M. Campos và Rincy S: Tập dữ liệu Thomas đã đề xuất một thuật toán mới có tên Minsup: Giá trị ngưỡng phổ biến Method: Nội dung hàm SPAM(minsup, S) CMSPAM, khắc phục được những nhược // Bước1: Quét Cơ sở dữ liệu SDB để tạo điểm của thuật toán SPAM [5]. Bài báo sẽ cơ sở dữ liệu theo chiều dọc VDB tập trung đi sâu phân tích và thử nghiệm sid = tid = 0; thuật toán CMSPAM, sau đó đề xuất một cải FOR(each item s ∈ 𝑆𝐷𝐵){ tiến thuật toán này cho kết quả về hiệu năng IF(s is end of transation){ tốt hơn trong trường hợp dữ liệu thưa. tid++ Vì sao trường hợp dữ liệu thưa ngày càng }ELSE IF(s is end of sequence){ được quan tâm, nhất là trong các bài toán tư sid++ vấn cho thương mại điện tử? Trong các hệ tid = 0 thống thương mại điện tử nói chung, số }ELSE{ lượng người dùng ngày càng lớn và còn tiếp bitmapItem = VDB.get[s] tục tăng nhanh trong thời gian tới. Tuy IF(bitmapItem = nhiên, tỉ lệ người dùng thực hiện nhiều giao NULL){ dịch không lớn và các giao dịch của một VDB.add(s,new Số 02 & 03 (CS.01) 2017 TẠP CHÍ KHOA HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 72
  3. bitmap()) CMAPi hoặc CMAPs. } Trong bước 4 của thuật toán, thủ tục cắt tỉa bitmapItem.registerBit(sid, DFS-Pruning được gọi đến. Bảng 3 trình bày tid); thủ tục này. Bản chất thủ tục này là một thao tác duyệt theo chiều sâu kiểu đệ quy có phân nhánh dựa trên việc xét phần tử thuộc về một } } trong hai tập S và I đã được xây dựng từ thủ // Bước 2: Quét Cơ sở dữ liệu chiều dọc tục CREATECMAP ở trên. VDB để loại bỏ những item không phổ biến, tập F chứa danh sách các item phổ biến . FOR(each item s ∈ 𝑉𝐷𝐵){ Hàm CREATECMAP(SDB, F) IF(s is frequent) { Input Một cơ sở dữ liệu tuần tự F = F ∪ s SDB và tập các item phổ biến F }ELSE Output Tập ứng cử CMAP i , CMAPs VDB remove s Pamameters: Ý nghĩa các tham số 1. SDB : tập cơ sở dữ liệu tuần tự 2. F: tập các item phổ biến } CREATECMAP() // Bước 3 : Thực hiện khởi tạo CMAP CMAP i = CMAPs= ∅ CREATECMAP(SDB, F, minsup) FOR transaction k ∈ VDB{ equalSet = ∅ // Bước 4 : Thực hiện mở rộng và cắt tỉa FOR item i ∈ k { chuỗi phổ biến IF i ∉ equalSet equalSet add i FOR(each item s ∈ 𝐹) IF i ∉ F DFS-Pruning(, CMAP i [s], Continue; CMAP s [s],s) FOR item j>i ∈ k{ IF j ∉ F Bảng 1: Thuật toán CMSPAM Continue; IF i,j ∈ 𝑠𝑎𝑚𝑒 𝑖𝑡𝑒𝑚𝑠𝑒𝑡{ IF i≠ 𝑗 CMPSPAM bổ sung khái niệm cơ sở dữ CMAP i [i] add j liệu đồng thời CMAP: là một cấu trúc ánh xạ support++ mỗi item k ∈ I với tập item được mở rộng equalSet add j } của k [5]. Thuật toán định nghĩa hai CMAP ELSE{ là CMAPi và CMAPs. CMAPs[i] add j support++; - CMAP i ánh xạ mỗi item k với tập } cm i (k) chứa tất cả cái item j ∈ I, j là } item được mở rộng bằng phép mở rộng } } i-step và giá trị hỗ trợ không nhỏ hơn Bảng 2: Hàm CREATECMAP minsup. - CMAP s ánh xạ mỗi item k với tập Hàm DFS-Pruning(, S n , I n ,k) cm s (k) chứa tất cả cái item j∈ I, j là Input Chuỗi tiền tố s, tập ứng cử item được mở rộng bằng phép mở rộng Sn, In s-step và giá trị hỗ trợ không nhỏ hơn Pamameters: Ý nghĩa các tham số minsup. 1. s: chuỗi tiền tố hiện tại Thuật toán CMSPAM và ý nghĩa từng 2. S n: Tập ứng cử theo phép mở rộng bước của thuật toán đã trình bày trong Bảng S-Step 1. Tập ứng cử theo phép mở rộng Trong bước 3 của thuật toán CMSPAM, 3. In : hàm CREATECMAP sẽ được gọi để tạo I-Step CSDL đồng thời CMAP. Thủ tục này được 4. k: là item cuối cùng trong chuỗi trình bày trong Bảng 2. Với mỗi item trong chuỗi giao dịch, thuật toán sẽ sử dụng phép DFS-Pruning ((s 1 ,s 2 …, s k ),S n , mở rộng i-step hoặc s-step để bổ sung vào I n ,k) Số 02 & 03 (CS.01) 2017 TẠP CHÍ KHOA HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 73
  4. S temp = ∅ Data Số Số sản Số sản Số sản I temp ∅ chuỗi phẩm phẩm phẩm = TB TB FOR (each i ∈ S n ) trong khác IF ((s 1 , …, s k, {i}) is frequent & i chuỗi nhau ∈ CMAP s [k] & support(i) >= minsup) trong chuỗi S temp S temp ∪ {i} = Bible 36369 13905 21.6 17.84 FOR (each i ∈ S temp ) DFS-Pruning((s 1 , …, s k, {i}) , S temp , KDDcup2000 77512 3340 4.62 6.07 S temp ) MSNBC 31790 17 13.33 5.33 FOR (each i ∈ I n ) IF ((s 1 , …, s k, {i}) is frequent & & Bảng 4: Thống kê tập dữ liệu kiểm thử i ∈ CMAP i [k]& support(i) >= minsup) I temp = I temp ∪ {i} FOR (each i ∈ I temp ) Thử nghiệm 1 với CSDL BIBLE (Bảng DFS-Pruning((s 1 , …, s k, {i}) , S temp , 5 và Hình 1) cho thấy đối với CSDL có đặc I temp ) trưng là có nhiều sản phẩm mà mỗi chuỗi đều gồm nhiều giao dịch, nhiều sản phẩm thì Bảng 3: Hàm DFS-Pruning SPAM và CMSPAM nhanh hơn rất nhiều so với thuật toán GSP do không phải xử lý một Để đánh giá hiệu quả của CMSPAM, số lượng lớn các mẫu sinh ra tại mỗi lần lặp chúng tôi thử nghiệm trên bộ dữ liệu SPMF đồng thời không phải quét CSDL nhiều lần. [8]. Cách thức thử nghiệm và đánh giá tương Giá trị minsup càng nhỏ thì thuât toán tự như trong [6]. CMSPAM càng tỏ ra hiệu quả hơn so với Tất cả các tập dữ liệu dùng để kiểm thử thuật toán SPAM do hạn chế được số ứng cử thuật toán đều tuân theo cấu trúc sau: viên sinh ra sau mỗi lần lặp. ……. Minsup 0.5 0.25 0.1 0.05 0.025 Trong đó : GSP 5421 7015 11114 57266 132568 SPAM 3615 4025 5316 12330 32756 : Là một giao dịch, các item trong CMSPAM 3531 3858 4831 7666 15529 cùng một giao dịch phân cách nhau bởi Result Set 5 22 174 774 3285 dấu cách. Bảng 5: Thử nghiệm CMSPAM với BIBLE : Là một chữ số dùng để phân biệt các giao dịch với nhau Biểu đồ thời gian thực thi với (trong dữ liệu chọn số -1). CSDL BIBLE : Là một chữ số dùng 200000 để ký hiệu kết thúc một chuỗi tuần tự (trong dữ liệu chọn số -2). 0 Việc kiểm thử các thuật toán sẽ sử dụng 0.5 0.25 0.1 0.05 0.025 3 CSDL được liệt kê trong Bảng 4. Các thử GSP SPAM CMSPAM nghiệm sẽ thực hiện trên từng bộ dữ liệu và thống kê thời gian chạy của thuật toán khi Hình 1: Biểu đồ kết quả kiểm thử thuật toán thay đổi ngưỡng minsup. Dựa trên kết quả, GSP, SPAM, CMSPAM với bộ dữ liệu chúng tôi sẽ vẽ biểu đồ so sánh hiệu năng BIBLE thuật toán với trục hoành là ngưỡng minsup (giảm dần), trục tung là thời gian. Chúng tôi Thử nghiệm 2 trên KDDCUP 2000 với lựa chọn ba thuật toán để so sánh gồm GSP, 77512 khách hàng, 3340 sản phẩm, mỗi SPAM và CMSPAM. khách hàng có trung bình 6.07 sản phẩm giao dịch với 4.62 sản phẩm khác nhau. Kết quả cho trong Bảng 6 và Hình 2 cũng tương đồng như thử nghiệm với BIBLE. CMSPAM luôn cho kết quả tốt hơn về thời gian. Số 02 & 03 (CS.01) 2017 TẠP CHÍ KHOA HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 74
  5. III. THUẬT TOÁN CMSPAME Minsup 0.5 0.25 0.1 0.05 0.025 GSP 3268 4661 6875 12548 17230 Sau khi cài đặt và thử nghiệm thuật toán SPAM 1025 1241 1446 1552 1684 CMSPAM, chúng tôi nhận thấy trong bước 1 CMSPAM 958 971 987 1037 1124 của thuật toán: quét cơ sở dữ liệu SDB để tạo Result Set 0 0 0 0 10 cơ sở dữ liệu theo chiều dọc VDB, thuật toán Bảng 6: Kết quả kiểm thử CMSPAM với tập sẽ quét toàn bộ CSDL để tính toán giá trị hỗ dữ liệu KDDCUP 2000 trợ của từng item. Ngay sau đó trong bước 2 thuật toán sẽ loại bỏ những item có giá trị hỗ Biểu đồ thời gian thực thi với CSDL trợ nhỏ hơn minsup. Những item còn lại sẽ KDDCUP 2000 là những item phổ biến. Như vậy trong bước 20000 1 việc quét và tính toán giá trị hỗ trợ của các item không phổ biến là không hiệu quả vì 0 ngay trong bước 2 những item này sẽ bị loại 0.5 0.25 0.1 0.05 0.025 bỏ và không được sử dụng trong phần còn lại GSP SPAM CMSPAM của thuât toán. Chúng tôi nhận định việc giảm thiểu Hình 2: Kiểm thử thuật toán GSP, SPAM, những phép duyệt và tính toán giá trị hỗ trợ CMSPAM với bộ dữ liệu KDDCUP2000 của các item này sẽ cải thiện được tốc độ xử lý của thuật toán. Đặc biệt là với những bộ Thử nghiệm 3 trên MSNBC với 31790 dữ liệu thưa, tức là CSDL chứa một số lượng khách hàng, 17 sản phẩm, mỗi khách có lớn các item và chuỗi tuần tự nhưng số giao trung bình 13.33 sản phẩm giao dịch với dịch trung bình với một khách hàng là thấp. 5.33 sản phẩm khác nhau. Kết quả thử Câu hỏi đặt ra là làm sao chúng ta biết nghiệm trong Bảng 7 và Hình 3. những item nào là item phổ biến, những item nào là không phổ biến trong khi chưa tính Minsup 0.5 0.25 0.1 0.05 0.025 toán được giá trị hỗ trợ của các item này. GSP 2523 12053 26754 96054 293921 SPAM 1121 1666 4038 9701 22800 Để giải quyết câu hỏi này, chúng tôi đề CMSPAM 748 1361 3465 8972 20047 xuất một cải tiến cho thuật toán CMSPAM Result Set 5 44 338 1478 6068 dựa trên ý tưởng đánh giá cận trên và đánh Bảng 7. Kiểm thử với tập dữ liệu MNSBC dấu để loại bỏ việc phải tính toán lại với các item không thể cho giá trị tốt hơn ngưỡng Biểu đồ thời gian thực thi với CSDL minsup. Cụ thể: MNSBC - Trong mỗi bước duyệt item từ lần quét 400000 CSDL đầu tiên, chúng ta sẽ tính toán 200000 giá trị hỗ trợ lớn nhất có thể đối với item đó (giả sử item đó xuất hiện trong 0 0.5 0.25 0.1 0.05 0.025 tất cả các chuỗi tuần tự còn lại). - Nếu giá trị hỗ trợ tốt nhất này không GSP SPAM CMSPAM thể vượt quá giá trị minsup thì item đó chắc chắn sẽ là item không phổ biến và Hình 3. Kiểm thử thuật toán GSP, SPAM, việc tính toán giá trị hỗ trợ thực tế của CMSPAM với bộ dữ liệu MNSBC item trong các chuỗi tuần tự còn lại là không cần thiết. Các thử nghiệm cho thấy tốc độ của - Gắn thêm một thuộc tính đánh dấu SPAM và CMSPAM vẫn nhanh hơn rất (Flag) trong mỗi đối tượng item. nhiều so với thuật toán GSP trong cả hai - Flag có giá trị bằng false có nghĩa trường hợp số chuỗi tuần tự nhiều hay ít. Và là item đó không thể là một item thuật toán CMSPAM luôn cho kết quả hiệu phổ biến và sẽ không được tiếp tục năng tốt hơn SPAM. tính toán giá trị hỗ trợ. - Flag có giá trị bằng true nghĩa là chưa thể xác định được tính phổ Số 02 & 03 (CS.01) 2017 TẠP CHÍ KHOA HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 75
  6. biến của item đó và tiếp tục tính Method: Nội dung hàm CMSPAME(minsup , S) // Bước1:Quét Cơ sở dữ liệu SDB để tạo toán giá trị hỗ trợ. cơ sở dữ liệu theo chiều dọc VDB Ví dụ minh họa với CSDL như trong Bảng 8, sid = tid = 0; minsup = 50% FOR(each item s ∈ 𝑆𝐷𝐵){ IF(s is end of transation){ Customer Sequence Data tid++ ID 1 }ELSE IF(s is end of sequence){ sid++ 2 }ELSE{ 3 IF (s.flag = false) continue 4 bitmapItem = VDB.get[s] 5 IF(bitmapItem = NULL){ VDB.add(s,new bitmap()) Bảng 8: CSDL tuần tự minh họa } Xét chuỗi tuần tự s = . Với item i = {90} ta thấy dù i xuất hiện trong IF(bitmapItem.getSupport + chuỗi cuối cùng thì giá trị hỗ trợ tối đa của (sequencesSize - sid ) < minsup){ s.flag = false item i = {90} cũng chỉ là 2 nhỏ hơn giá trị continue minsup của bài toán. Như vậy việc duyêt và } tính toán giá trị hỗ trợ của item i trong chuỗi tuần tự cuối cùng theo cách thông thường là bitmapItem.registerBit(sid, tid); không cần thiết. Tương tự là với các item } } {70}, {80}. Đối với các CSDL nhỏ việc giảm thiểu // Bước 2 :Quét Cơ sở dữ liệu chiều dọc các phép toán này là không đáng kể nhưng VDB để loại bỏ những item không phổ biến, tập F chứa danh sách các item phổ với những CSDL có số chuỗi tuần tự lên tới biến . hàng nghìn, trăm nghìn thì chúng ta có thể FOR(each item s ∈ 𝑉𝐷𝐵){ giảm thiểu một số lượng lớn các phép toán. IF(s is frequent) { Giả sử ta có CSDL có 1.000.000 bản ghi F = F ∪ s với giá trị minsup = 40%, nếu có 1 item j chỉ }ELSE xuất hiện ở bản ghi thứ 600.001 và xuất hiện VDB remove s } trong toàn bộ các bản ghi sau đó (từ bản ghi 600.002 đến bản ghi 999.999). Vậy giá trị hỗ // Bước 3 : thực hiện khởi tạo CMAP trợ tối đa của item j sẽ là 399.999 < minsup. CREATECMAP(SDB,F,minsup) Trong khi thuật toán CMSPAM vẫn duyệt // Bước 4 : Thực hiện mở rộng và cắt tỉa qua và tính toán giá trị hỗ trợ cho 399.998 chuỗi lần xuất hiện phía sau của item j. Việc này FOR(each item s ∈ 𝐹) gây lãng phí và làm giảm tốc độ xử lý của DFS- Pruning(,CMAP i [s],CMAP s [s]) thuật toán. Vì thế nhóm chúng tôi tin rằng thực hiện cải tiến như trên sẽ giúp tăng hiệu Bảng 9: Thuật toán CMSPAME năng của CMSPAM. Thuật toán CMSPAME Thuật toán cải tiến được chúng tôi đặt Input Một cơ sở dữ liệu tuần tự S, và giá trị ngưỡng minsup do tên là CMSPAME. Bảng 9 mô tả thuật toán, người sử dụng đặt ra một số hàm và chương trình con vẫn giữ Output Tập đầy đủ các mẫu tuần tự F nguyên như trong CMSPAM đã trình bày Method Chương trình chính: trong mục II. Gọi hàm CMSPAME(minsup , S) Pamameters: Ý nghĩa các tham số Cải tiến của chúng tôi không thay đổi các 1. S:Tập dữ liệu tính toán chính của CMSPAM nên vẫn đảm 2. Minsup:Giá trị minsup bảo tính chính xác như CMSPAM. Độ phức tạp tính toán của thuật toán cũng không tốt hơn vì trường hợp xấu nhất thuật toán vẫn Số 02 & 03 (CS.01) 2017 TẠP CHÍ KHOA HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 76
  7. phải quét hết các item trong cơ sở dữ liệu thời gian chạy của thuật toán CMSPAME SDB. Tuy nhiên, với trường hợp dữ liệu thưa được cải thiện rõ rệt so với CMSPAM, tất cả như đã phân tích, bước đánh dấu và ước các giá trị thời gian chạy của CMSPAME lượng cận trên sẽ giúp giảm không gian tính đều nhỏ hơn so với CMSPAM. toán và tăng hiệu năng của thuật toán. Các thử nghiệm trong phần IV sẽ minh chứng Thử nghiệm 2 với BIBLE: gồm 36369 cho nhận định này. khách hàng, 13905 sản phẩm, mỗi khách hàng có trung bình 21.6 sản phẩm giao dịch IV. THỬ NGHIỆM VÀ ĐÁNH GIÁ với 17.84 sản phẩm khác nhau, tổng cộng có CMSPAME 787066 lượt đọc item từ CSDL. Kết quả thử Để so sánh hai thuật toán CMSPAME và nghiệm 2 cho trong Bảng 11 và Hình 5. CMSPAM, chúng tôi tiến hành thử nghiệm Đối với CSDL trên có đặc trưng là có với 3 bộ dữ liệu tương tự như đã thực hiện nhiều sản phẩm mà mỗi chuỗi đều gồm trong phần II. nhiều giao dịch và nhiều sản phẩm. Tốc độ Thử nghiệm 1 với KDDCUP 2000 gồm xử lý của thuật toán CMSPAME cải thiện 77512 khách hàng, 3340 sản phẩm, mỗi hơn so với thuật toán CMSPAM tuy nhiên khách hàng có trung bình 6.07 sản phẩm chênh lệch là không nhiều. Giá trị minsup giao dịch với 4.62 sản phẩm khác nhau, tổng càng lớn thì thời gian xử lý chênh lệch giữa cộng có 358278 lượt đọc item từ CSDL. Kết 2 thuật toán càng rõ hơn. quả thử nghiệm 1 cho trong Bảng 10 và Hình 4. Minsup 0.5 0.25 0.1 0.05 0.025 CMSPAM 3531 3858 4831 7666 15529 Minsup 0.5 0.25 0.1 0.05 0.025 CMSPAME 2476 2847 3894 6808 14811 CMSPAM 958 971 987 1037 1124 Kết quả 5 22 174 774 3285 CMSPAME 621 638 661 716 806 Số lượt item bỏ 278112 112219 33823 12533 4216 Kết quả 0 0 0 0 10 qua Số lượt đọc item 176319 86727 34241 15178 5554 Tỉ lệ lượt đọc 35.33 14.26 4.30 1.59 0.06 bỏ qua item bỏ qua(%) Tỉ lệ lượt đọc 49.21 24.27 9.55 4.23 1.55 Thời gian chênh 1055 1011 937 858 718 item bỏ qua(%) lệch Thời gian chênh 337 333 326 321 318 Tỉ lệ thời gian 29.87 26.20 19.39 11.19 4.62 lệch giảm thiểu(%) Tỉ lệ thời gian 35.17 34.29 33.03 30.95 28.29 giảm thiểu(%) Bảng 11: Kết quả kiểm thử thuật toán CMSPAM và CMSPAME với bộ dữ liệu Bảng 10: Kết quả kiểm thử thuật toán BIBLE CMSPAM và CMSPAME với bộ dữ liệu KDDCUP 2000 Biểu đồ thời gian thực thi với CSDL BIBLE Biểu đồ thời gian thực thi với CSDL KDDCUP 2000 20000 1500 15000 10000 1000 5000 500 0 0 0.5 0.25 0.1 0.05 0.025 0.5 0.25 0.1 0.05 0.025 CMSPAM CMSPAME CMSPAM CMSPAME Hình 5: Biểu đồ kết quả kiểm thử thuật toán CMSPAM và CMSPAME với bộ dữ liệu Hình 4: Biểu đồ kết quả kiểm thử thuật toán BIBLE CMSPAM và CMSPAME với bộ dữ liệu KDDCUP 2000 Thử nghiệm 3 với MSNBC gồm 31790 khách hàng, 17 sản phẩm, mỗi khách hàng Kết quả thử nghiệm 1 cho thấy với bộ dữ có trung bình 13.33 sản phẩm giao dịch với liệu có đặc trưng thưa như KDDCUP2000, Số 02 & 03 (CS.01) 2017 TẠP CHÍ KHOA HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 77
  8. 5.33 sản phẩm khác nhau, tổng cộng có Dựa trên việc phân tích của trường hợp 423776 lượt đọc item từ CSDL. CSDL lớn với rất nhiều người dùng nhưng Minsup 0.5 0.25 0.1 0.05 0.025 số giao dịch và số sản phẩm giao dịch trong CMSPAM 748 1361 3465 8972 20847 một lần không nhiều (trường hợp dữ liệu CMSPAME Kết quả 710 5 1291 44 3454 338 8976 1478 20939 6068 thưa), chúng tôi đã đề xuất thuật toán cải tiến Số lượt item bỏ qua 52744 6430 304 44 7 CMSPAME. Các thử nghiệm đã cho thấy Tỉ lệ lượt đọc item bỏ qua(%) 12.44 1.51 0.07 0.01 0.0017 thuật toán cải tiến có hiệu năng tốt hơn so Thời gian chênh lệch(ms) 38 70 11 -0.04 -92 với CMSPAM trong các bài toán có nhiều sản phẩm, số lượng giao dịch lớn đồng thời Tỉ lệ thời gian giảm 5.08 5.14 0.39 - - thiểu(%) yêu cầu giá trị ngưỡng phổ biến (minsup) cao. Bảng 12: Kết quả kiểm thử thuật toán Nhóm tác giả sẽ tiếp tục phát triển thuật CMSPAM và CMSPAME với bộ dữ liệu toán để hướng tới việc áp dụng trong các hệ MNSBC thống thương mại điện tử có cùng đặc trưng dữ liệu thưa như đã phân tích. Biểu đồ thời gian thực thi với CSDL MNSBC VI. TÀI LIỆU THAM KHẢO 25000 20847 20939 [1] R. Agrawal and R. Srikant. “Mining 20000 sequential patterns”. In Proc. 1995 Int. Conf. Data Engineering (ICDE’95), 15000 pages 3–14, Taipei, Taiwan, 1995. 8972 8976 [2] Q. Zhao and S. S. Bhowmick. 10000 “Sequential Pattern Mining: A Survey”, Technical Report, CAIS, 5000 3465 3454 Nanyang Technological University, 748 710 1361 1291 Singapore, No. 2003118, 2003. 0 0.5 0.25 0.1 0.05 0.025 [3] J. Han, H. Cheng, D. Xin, X. Yan: “Frequent pattern mining: current CMSPAM CMSPAME status and future directions”. Springer Hình 6: Biểu đồ kết quả kiểm thử thuật toán Science+Business Media, LLC, 2007. CMSPAM và CMSPAME với bộ dữ liệu [4] J. Ayres, J. Gehrke, T. Yiu, and J. MNSBC Flannick. “Sequential PAttern Mining using A Bitmap Kết quả trong Bảng 12 và Hình 6 cho thấy Representation”,SIGKDD, pp. 429– với đặc trưng của bộ dữ liệu này là có rất ít 435, 2002. sản phẩm (chỉ có 17 giao dịch) khiến cho [5] P. Fournier-Viger, A. Gomariz, M. thuật toán CMSPAME không cải thiện nhiều Campos and R. Thomas. “Fast Vertical tốc độ xử lý so với thuật toán CMSPAM. Mining of Sequential Patterns Using Đặc biệt với 2 giá trị minsup 0.05 và 0.025 Co-occurrence Information”, 2014. thời gian thực thi của CMSPAME còn lớn [6] M. Verma, D. Meht. “Sequential hơn so với thuật toán CMSPAM. Nguyên Pattern Mining: A Comparison nhân là số lượt đọc item bỏ qua là quá nhỏ between GSP, SPADE and Prefix (44 và 7) không đáng kể so với toàn bộ số SPAN”, IJEDR, Volume 2, Issue 3, lượt đọc item của toàn bộ CSDL. 2014. [7] M. J. Zaki, “SPADE: An Efficient V. KẾT LUẬN Algorithm for Mining Frequent Bài báo đã tìm hiểu về khai phá dữ dữ Sequences”, In: Machine Learning. liệu tuần tự (SPM) và các thuật toán liên Number 1/2 Vol. 42, 2001. quan. Chúng tôi đã đi sâu tìm hiểu thuật toán [8] P. Fournier-Viger. “An Open-Source khai phá dữ liệu CMSPAM và tiến hành thử Data Mining Library”, online at: nghiệm để chứng tỏ ưu điểm của thuật toán này với các thuật toán trước đó. Số 02 & 03 (CS.01) 2017 TẠP CHÍ KHOA HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 78
  9. http://www.philippe-fournier- viger.com/spmf/index.php?link=datase ts.php Nhóm tác giả: ThS. Nguyễn Mạnh Sơn: hiện tại là giảng viên khoa CNTT1 – Học viện công nghệ Bưu chính Viễn thông. Các hướng nghiên cứu chính: Khai phá dữ liệu từ mạng xã hội, học máy và tư vấn, tối ưu hóa thuật toán. ThS. Đặng Ngọc Hùng: hiện tại là giảng viên khoa CNTT1 – Học viện Công nghệ Bưu chính Viễn thông. Các hướng nghiên cứu chính: Khai phá dữ liệu từ mạng xã hội, các hệ thống thông tin. Số 02 & 03 (CS.01) 2017 TẠP CHÍ KHOA HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 79