Phương pháp song song khai phá tập lợi ích cao dựa trên chỉ số hình chiếu

Nội dung text: Phương pháp song song khai phá tập lợi ích cao dựa trên chỉ số hình chiếu

1. Các công trình nghiên cứu phát triển CNTT và Truyền thông Tập V-1, Số 17 (37), tháng 6/2017 Phƣơng pháp song song khai phá tập lợi ích cao dựa trên chỉ số hình chiếu Parallel Method for Mining High Utility Itemsets from Projection- Based Indexing Đậu Hải Phong, Nguyễn Mạnh Hùng Abstract: High utility itemsets (HUIs) mining is Trong khai phá tập lợi ích cao có một số thách one of popular problems in data mining. Several thức sau: Thứ nhất, với khối lượng dữ liệu lớn thì parallel and sequential algorithms have been không gian tìm kiếm lớn và vấn đề về sự hợp nhất. proposed in the literature to solve this problem. All the Thứ hai, tập lợi ích cao không có tính chất đóng [7]. parallel algorithms to try reduce synchronization cost Do vậy, số lượng các ứng cử viên được sinh ra rất and caculation global profit of itemsets. In this paper, lớn và chi phí lớn về thời gian duyệt dữ liệu nhiều lần we present a parallel method for mining HUIs from CSDL để kiểm tra các ứng viên như trong một số projection-based indexing to speed up performance thuật toán [2], [8], [9] hoặc tiêu tốn nhiều thời gian and reduce memory requirements. The experimental và không gian bộ nhớ để sinh ra các cây điều kiện [10], results show that the performance and number [11], [12], Thứ ba, với khối lượng dữ liệu lớn thì candidate of our algorithm is better than some non giới hạn về thời gian tính toán và yêu cầu về bộ nhớ parallel algorithms. trên một máy tính là không đáp ứng được. Do đó, Keywords: Data Mining, Parallel Mining, Shared việc thiết kế các thuật toán dựa trên kiến trúc song Memory, High Utility, Projection index, PPB-Miner song là cần thiết. algorithm. Trong bài báo này chúng tôi xây dựng thuật toán song song PPB-Miner để khai phá tập lợi ích cao với I. GIỚI THIỆU một số đóng góp sau: Ngày nay, với sự phát triển nhanh chóng của các - Dùng bảng chỉ số để tăng tốc độ thực hiện và kỹ thuật về cơ sở dữ liệu đã tạo điều kiện cho việc giảm yêu cầu bộ nhớ. Từ bảng chỉ số của các tập lưu trữ và sử dụng dữ liệu lớn trong kinh doanh, y tế, phần tử, sinh các ứng viên, tìm tập lợi ích cao và tạo giáo dục, các tổ chức khoa học, chính phủ, Một nhanh bảng chỉ số từ tập tiền tố của nó. trong những chủ đề quan trọng trong các nghiên cứu - Sử dụng cấu trúc danh sách lợi ích (utility-list) về khai phá dữ liệu gần đây là tìm kiếm những tập để loại nhanh các ứng viên và độc lập xử lý các phần mục lợi ích cao từ cơ sở dữ liệu giao dịch. Mục tiêu tử trên từng bộ xử lý. là trích xuất các thông tin hữu ích từ dữ liệu có quan - Tối ưu lưu trữ giá trị để tính danh sách lợi ích. tâm đến lợi ích, số lượng, chi phí, của từng phần tử. Đã có các nghiên cứu được đề xuất để khai phá - Xây dựng thuật toán song song khai phá tập lợi tập lợi ích cao [1]–[6], Tuy nhiên, các thuật toán ích cao trên mô hình chia sẻ bộ nhớ. chủ yếu đều thực hiện khai phá tuần tự. Vấn đề đặt ra Nội dung tiếp theo của bài báo được tổ chức như là khi dữ liệu lớn, các thuật toán tuần tự sẽ khó đáp sau: phần II trình bày một số khái niệm và định ứng về mặt thời gian thực hiện và không gian lưu trữ. nghĩa. Các vấn đề liên quan đến khai phá tập lợi ích cao được trình bày trong phần III. Phần IV đề xuất - 31 -
2. Các công trình nghiên cứu phát triển CNTT và Truyền thông Tập V-1, Số 17 (37), tháng 6/2017 thuật toán PPB-Miner. Phần V trình bày kết quả đạt tử đó. Ký hiệu: U( ik,Tj) = S({ik}) * O(ik,Tj) là lợi ích được và so sánh với các thuật toán khác. Cuối cùng là của phần tử ik trong giao dịch Tj. kết luận. Ví dụ, U({A},T1) = 3*1 = 3; U({C},T1) = 1*2 = II. KHÁI NIỆM VÀ ĐỊNH NGHĨA 2, Cho một cơ sở dữ liệu gồm các giao dịch Ti là D = Định nghĩa 4 [2] - Lợi ích của một tập phần tử X {T1,T2,T3, Tn}, các giao dịch được xác định duy nhất trong một giao dịch Tj là tổng giá trị lợi ích tất cả phần bởi Tid, I={i1,i2,i3, in} là các phần tử (item) xuất hiện tử của tập X trong giao dịch Tj. Ký hiệu: U(X,Tj) = ∑ trong các giao dịch, X  I là tập các phần tử  ( ) – là lợi ích của tập phần tử X (itemsets). Một tập X được gọi là tập k-phần tử khi số trong một giao dịch Tj. lượng phần tử của X là k. Ví dụ, U({AC},T1) = 3*1 + 1*2 = 5. Để thuận lợi trong giải thích các khái niệm, chúng Định nghĩa 5 [2] - Lợi ích của một tập phần tử X tôi đưa ra Bảng 1. Cơ sở dữ liệu giao dịch và Bảng 2. trong cơ sở dữ liệu là tổng lợi ích của tập phần tử X Bảng lợi ích ngoài của các phần tử. trong tất cả giao dịch chứa X. Ký hiệu: AU(X) = Bảng 1. Cơ sở dữ liệu giao dịch ∑  ( ). Tid Giao dịch Ví dụ, xét tập {AC}, ta thấy {AC}, xuất hiện trong A B C D E F 1 1 0 2 1 1 1 các giao dịch: T1, T5 nên ta có: AU({AC}) = 2 0 1 25 0 0 0 U({AC},T1) + U({AC},T5) = (3*1 + 1*2) + (3*2 + 3 0 0 0 0 2 1 1*8) = 19. 4 0 1 12 0 0 0 Định nghĩa 6 [2]– Tập phần tử lợi ích cao: Tập X 5 2 0 8 0 2 0 được gọi là tập phần tử lợi ích cao (HUI – High Utility 6 0 0 4 1 0 1 7 0 0 2 1 0 0 Itemsets) nếu AU(X) ≥ minutil, ngược lại gọi X là tập 8 3 2 0 0 2 3 phần tử lợi ích thấp. Trong đó minutil là ngưỡng lợi 9 2 0 0 1 0 0 ích tối thiểu cho trước. 10 0 0 4 0 2 0 Ví dụ, lợi ích tối thiểu minutil = 12 thì {AC} là tập Bảng 2. Bảng lợi ích ngoài của các phần tử phần tử lợi ích cao. Item A B C D E F Định nghĩa 7 [2] - Lợi ích của một giao dịch là Lợi ích 3 10 1 6 5 2 tổng lợi ích của các phần tử trong giao dịch đó. Ký ∑ ( ) Định nghĩa 1 [2] - Lợi ích trong (internal utility) hiệu: TU(Tj) = – là lợi ích của giao của mỗi phần tử là giá trị của mỗi phần tử trong từng dịch Tj. giao dịch. Ký hiệu: O(ik,Tj) – là lợi ích trong của phần Ví dụ, TU(T1) = 1*3 + 2*1 + 1*6 + 1*5 + 1*2 = tử ik trong giao dịch Tj. 18, TU(T2) = 1*10 + 25*1 = 35. Ví dụ, O(A,T1) = 1; O(C,T1) = 2 trong Bảng 1. Định nghĩa 8 [2] - Lợi ích giao dịch có trọng số Định nghĩa 2 [2] - Lợi ích ngoài (external utility) của một tập phần tử X là tổng lợi ích của các giao dịch của mỗi phần tử là giá trị lợi ích của mỗi phần tử trong có chứa tập phần tử X. Ký hiệu: TWU(X) = ∑ bảng lợi ích. Ký hiệu: S({ik}) là lợi ích ngoài của phần  ( ) là lợi ích giao dịch có trọng số tử ik. của tập phần tử X. Ví dụ, S({A}) = 3; S({B}) = 10 trong Bảng 2. Ví dụ: TWU({AC}) = TU(T1) + TU(T5) = 18 + 24 Định nghĩa 3 [2] - Lợi ích của một phần tử trong = 42. giao dịch là tích của lợi ích trong và lợi ích ngoài của phần - 32 -
3. Các công trình nghiên cứu phát triển CNTT và Truyền thông Tập V-1, Số 17 (37), tháng 6/2017 Định nghĩa 9 [2] – Cho một tập phần tử X và một tập lợi ích cao từ tập tiềm năng. Thuật toán này yêu giao dịch T, sao cho X  T thì tập hợp tất cả các phần cầu phức tạp trong xây dựng và duyệt cây nhiều lần. tử đứng sau X trong T kí hiệu là T\X. Năm 2012, Mengchi Liu giới thiệu thuật toán HUI- Ví dụ, trong Bảng 1 thì T1\{AC} = {DEF}. Miner [4] khai phá tập lợi ích cao nhưng không sinh Định nghĩa 10 [2] – Lợi ích còn lại của tập phần tử tập ứng viên. Thuật toán sử dụng cấu trúc utility-list để X trong giao dịch T, kí hiệu : RU(X,T) là tổng lợi ích loại nhanh tập ứng viên và không cần duyệt dữ liệu của các phần tử trong T\X trong giao dịch T, và nhiều lần. Nhưng nhược điểm của thuật toán này là chi phí kết hợp các tập lợi ích cao là tương đối lớn. RU(X,T) = = ∑ ( ) ( ). Thuật toán UDepth [9] được Wei đưa ra thực hiện Định nghĩa 11 – Tổng lợi ích còn lại của một tập khai phá cơ sở dữ liệu theo chiều dọc. Thuật toán này phần tử X trong cơ sở dữ liệu là tổng lợi ích còn lại gồm các bước: duyệt dữ liệu để xác định TWU của của tập phần tử X trong tất cả giao dịch chứa X. Ký từng phần tử; loại bỏ các phần tử có TWU nhỏ hơn hiệu: SRU(X) = ∑  ( ). ngưỡng tối thiểu; sắp xếp lại các phần tử có TWU cao Định nghĩa 12 [4] – Cấu trúc utility-list của tập theo thứ tự giảm dần; từ mỗi phần tử ik có TWU cao, phần tử: utility-list của tập phần tử X bao gồm 3 tìm tất cả các tập có phần tử ik là tiền tố và duyệt lại cơ trường: tid, iutil, rutil. Trong đó: sở dữ liệu một lần nữa để xác định các tập lợi ích cao. - Tid là chỉ số của giao dịch chứa X; Năm 2013, Gou và cộng sự đưa ra thuật toán PB [2] - iutil là lợi ích của X trong Tid, tức là U(X, Tid); dựa trên các bảng chỉ số để tăng tốc độ thực hiện và giảm - rutil là lợi ích còn lại của X trong Tid, tức là yêu cầu bộ nhớ. Thuật toán này sử dụng bảng chỉ số của RU(X, Tid); các tập để sinh các ứng viên, tìm tập lợi ích cao và tạo nhanh bảng chỉ số từ tập tiền tố của nó. Nhược điểm của Định lý 1 [4] – Cho một utility-list của tập phần tử thuật toán này là vẫn sử dụng mô hình TWU làm ngưỡng X, nếu tổng X.iutils và X.rutils nhỏ hơn ngưỡng lợi ích trên để cắt tỉa các tập ứng viên và do mô hình này tạo ra tối thiểu (minutil) thì lợi ích của các tập phần tử mở ngưỡng cao dẫn đến số lượng ứng viên được sinh ra lớn rộng từ tập phần tử X cũng nhỏ hơn lợi ích tối thiểu. làm tốn nhiều chi phí kiểm tra ứng viên. III. VẤN ĐỀ LIÊN QUAN Năm 2015, trong [13] các tác giả đã đề xuất mô Trong phần này, chúng tôi trình bày một số nghiên hình CWU để loại bỏ tập ứng viên. Đây là mô hình cứu liên quan đến thuật toán khai phá tập lợi ích cao. tương đối hiệu quả trong các thuật toán khai phá tập III.1. Thuật toán tuần tự khai phá tập lợi ích cao lợi ích cao theo chiều sâu như [2], [9], [12], v.v Năm 2005, Ying Liu đã đưa ra thuật toán hai pha III.2. Thuật toán song song khai phá tập lợi ích cao (two-phase) để khai phá nhanh tập lợi ích cao [3]. Pha Năm 2008, A. Erwin [14] đã đề xuất thuật toán sử một, tìm tất cả các tập ứng viên có TWU lớn hơn ngưỡng dụng mô hình TWU với tăng trưởng mẫu dựa trên cấu minutil. Pha hai, với mỗi tập ứng viên tính toán chính trúc dữ liệu cây mẫu lợi ích nén (CTU-tree). Thuật toán xác lợi ích của tập đó. Với thuật toán này đòi hỏi duyệt đã song song lược đồ chiếu (projection scheme) để lưu dữ liệu nhiều lần và sinh ra nhiều ứng viên. trữ trên đĩa khi bộ nhớ chính không đủ do dữ liệu quá Năm 2010, thuật toán sử dụng cấu trúc cây mẫu lợi lớn. Kết quả thực nghiệm chỉ ra thuật toán thực hiện ích [11] được Vincent và cộng sự giới thiệu. Thuật hiệu quả với dữ liệu lớn, dày và có tập mẫu lớn. toán gồm 3 bước sau: bước 1, xây dựng cây mẫu lợi Năm 2009, B. Vo [15] và nhóm tác giả đã đề xuất ích (UP-tree); bước 2, sinh các tập tiềm năng từ UP- một phương pháp song song khai phá tập lợi ích cao tree bằng thuật toán UP-Growth; bước 3, xác định các với dữ liệu được phân chia theo chiều dọc, sử dụng - 33 -
4. Các công trình nghiên cứu phát triển CNTT và Truyền thông Tập V-1, Số 17 (37), tháng 6/2017 cấu trúc cây WIT để lưu trữ dữ liệu cục bộ trên mỗi bộ Ta loại D khỏi các giao dịch. Sau đó tiến hành sắp xử lý. Các phần tử trên mỗi SlaverSite chỉ gửi về xếp các phần tử trên mỗi giao dịch giảm dần theo AU MasterSite nếu TWU của nó lớn hơn ngưỡng tối thiểu có thứ tự lần lượt là C:57, E:45, B:40, A:24, F:12 ta và MasterSite chỉ kết hợp để khai phá tập lợi ích cao được Bảng 4. nếu các tập đó xuất hiện ở hai SlaverSite khác nhau. Bảng 4. Lợi ích UR của các phần tử trong từng Năm 2013, Kannimuthu [5] và cộng sự đã trình bày giao dịch thuật toán FUI khai phá tập lợi ích cao, các công việc Tid Giao dịch 1 (C,12), (E,10), (A,5), (F,2) được phân chia theo cách tiếp cận một master và nhiều 2 (C,35), (B,10), slave. Các giá trị lợi ích được trích xuất song song trên 3 (E,12), (F,2) các slave. Tổng lợi ích sẽ được tính ở master. Kết quả 4 (C,22), (B,10) thực nghiệm cho thấy, thời gian thực thi nhanh hơn so 5 (C,24), (E,16), (A,6) với các thuật toán trước. 6 (C,6), (F,2) 7 (C,2) 8 (E,45), (B,35), (A,15), (F,6) IV. ĐỀ XUẤT THUẬT TOÁN 9 (A,6) Trong phần này, chúng tôi trình bày thuật toán 10 (C,14), (E,10) song song PPB-Miner khai phá tập lợi ích cao dựa trên Một số cấu trúc được sử dụng trong thuật toán bảng chỉ số (IT) và bảng ứng viên (TC) nhằm tính PPB-Miner gồm: nhanh giá trị AU và SRU của các tập phần tử trong - Bảng tập ứng viên TCk có k-phần tử với tiền tố là quá trình khai phá. Áp dụng định lý 1, sử dụng tổng tập X, mỗi tập phần tử chứa: lợi ích thực tế AU(X) và iutils và rutils tương ứng với AU và SRU để tỉa ứng tổng lợi ích còn lại SRU(X) tương ứng. viên. Ví dụ, trong Bảng 5 gồm các tập ứng viên có 2 phần Để tiết kiệm bộ nhớ nhưng vẫn tính được danh tử với tiền tố {C}. sách lợi ích, với mỗi phần tử ik trong giao dịch Tj, Bảng 5. Tập ứng viên TC2 với tiền tố {C} chúng tôi lưu trữ thêm đại lượng UR. Trong đó, Itemsets AU SRU UR(ik,Tj) = U(ik,Tj) + RU(ik,Tj). CE 39 11 Với cách tổ chức dữ liệu như trên có thể tính CA 19 2 CF 10 0 U(ik,Tj) = UR(ik,Tj) - UR(ik+1,Tj) và RU(ik,Tj) = CB 57 0 UR(ik+1,Tj). Trong đó, ik+1 là phần tử ngay phía sau - Bảng chỉ số IT của tập X gồm: các giao dịch ik. Bằng cách lưu trữ này, ta có thể vừa tiết kiệm bộ X nhớ không cần lưu cả iutil và rutil. Tj chứa tập X; vị trí p của phần tử cuối cùng của tập X xuất hiện trong giao dịch T ; U(X,T ) – giá trị lợi Ví dụ, từ cơ sở dữ liệu minh họa ở Bảng 1 với j j ích của tập X trong giao dịch T ; RU(X,T ) – giá trị minutil = 56. Với lần duyệt dữ liệu lần đầu ta tính j j lợi ích các phần tử còn lại sau tập X trong giao dịch được AU và TWU của từng phần tử được kết quả như T . Ví dụ, từ Bảng 4 ta xây dựng được bảng chỉ số trong Bảng 3. Từ Bảng 3 loại D (vì TWU(D) = 50 < j ITC của tập {C} trong Bảng 6 như sau: U({C},T1) = 56) và sắp xếp giảm dần theo AU được tập HTWU1. UR({C},T1) – UR({E},T1) = 12 – 10 = 2; Bảng 3. Kết quả tính TWU và AU RU({C},T1) = UR({E},T1); tương tự với các giao Itemsets A B C D E F dịch 2, 4, 5, 6, 7, 10. Với một thứ tự đã được sắp TWU 99 102 133 50 113 87 xếp trong giao dịch thì từ bảng IT có thể xác định AU 24 40 57 24 45 12 C nhanh tập các ứng viên 2-phần tử bằng cách kết hợp C với từng phần tử sau C trong từng giao dịch. Ví - 34 -
5. Các công trình nghiên cứu phát triển CNTT và Truyền thông Tập V-1, Số 17 (37), tháng 6/2017 dụ, với giao dịch 5 và sau vị trí 1 sinh được tập các Giả sử với hai luồng xử lý, thuật toán PPB-Miner ứng viên {CE}, {CA} và có thể tính nhanh được mô tả trong Hình 1. U({CE},T5) = U({C},T5) + (UR({E},T5) - Bảng 6. Chỉ số ITC của tập {C} UR({A},T5)) = 8 + (16-6) = 18 và RU({CE},T5) = Tid Vị trí cuối U({C},Tj) RU({C},Tj) UR({A},T5) = 6. Tương tự, U({CA},T5) = 1 1 2 10 U({C},T5) + (UR({A},T5) - 0) = 8 + (6 - 0) = 14 và 2 1 25 10 RU({CA},T5) = 0 vì A là phần tử cuối cùng trong 4 1 12 10 giao dịch 5. 5 1 8 16 6 1 4 2 7 1 2 0 10 1 4 10 Database IV.1. Mô tả thuật toán PPB-Miner Local Local INPUT: cơ sở dữ liệu giao dịch, lợi ích mỗi phần database database tử, minutil - ngưỡng lợi ích tối thiểu. OUTPUT: Tất cả các tập lợi ích cao - Tính TWU, AU cục bộ - Tính TWU, AU cục bộ Công việc của Master: 1. Phân chia các giao dịch cho các luồng theo - Tính TWU, AU toàn cục - Loại phần tử có TWU thấp, lập danh sách HTWU1 phương pháp động sử dụng thư viện OpenMP giảm dần theo AU, đưa 1-HUIs vào HUIs 2. Đợi các luồng tính TWU, AU cục bộ xong thì - Phân chia giao dịch thực hiện: 2.1. Tính TWU, AU toàn cục 2.2. Từ tập I, loại các phần tử có TWU nhỏ hơn - Loại phần từ có TWU - Loại phần từ có TWU thấp thấp minutil, lập danh sách HTWU1 với các phần tử giảm - Sắp xếp các giao dịch - Sắp xếp các giao dịch dần theo AU; đưa 1-HUIs vào tập HUIs; giảm dần theo AU. giảm dần theo AU. 2.3. Phân chia các giao dịch cho các luồng và đợi các luồng thực hiện xong việc loại các phần tử có - Chia 1-itemsets trong HTWU1 cho các luồng. TWU nhỏ hơn minutil và sắp xếp các phần tử trong - k=1 giao dịch giảm dần theo AU; 4. Phân chia từng phần tử trong HTWU1 cho các luồng để khai phá HUIs. - Xây dựng ITk - Xây dựng ITk - Xây dựng TCk+1 - Xây d ựng TCk+1 - k=k+1 - k=k+1 Công việc của từng luồng (Threads): 1. Nhận dữ liệu từ Master để thực hiện tính TWU Ouput Ouput và AU cục bộ; k+1 – HUIs k+1 – HUIs L=size(k+1 – HUIs) L=size(k+1 – HUIs) 2. Nhận giao dịch từ Master và thực hiện loại các phần tử có TWU nhỏ hơn minutil và sắp xếp các phần tử trong giao dịch giảm dần theo AU T T L>1 L>1 3. Nhận phần tử i trong HTWU1 từ Master thực 1 1 hiện: F F 3.1. k=1; 3.2. X = i; 3.3. Xây dựng bảng IT của những phần tử i; Hình 1. Thuật toán PPB-Miner 1 - 35 -
6. Các công trình nghiên cứu phát triển CNTT và Truyền thông Tập V-1, Số 17 (37), tháng 6/2017 3.4. Gọi hàm PB-Miner(X,k,ITX) để khai phá tập giao dịch, bảng lợi ích ngoài tương ứng ở Bảng 1 và các HUIs; Bảng 2, ngưỡng lợi ích tối thiểu minutil = 56. //Hàm PB-Miner Công việc của Master: Bước 1, Master thực hiện phân chia các giao dịch Hàm PB-Miner(X,k,IT{x}) cho các luồng; INPUT: X – tập phần tử tiền tố; k – số phần tử Bước 2, Sau khi nhận TWU, AU cục bộ từ các trong tập; ITX – bảng chỉ số của tập X; HTWU1. luồng và thực hiện: OUTPUT: danh sách các tập có lợi ích cao. Bước 2.1, Tính TWU, AU toàn cục được kết quả như Bảng 7. //Xây dựng bảng TCk+1 với X là tiền tố dựa trên bảng IT{X} Bảng 7. Kết quả TWU và AU toàn cục 1: TCk+1={}; Itemsets A B C D E F 2: For (j,p) IT{X}{ TWU 99 102 133 50 113 87 //p là phần tử cuối cùng của tập X AU 24 40 57 24 45 12 2.1: For ip+1 Tj { Bảng 8. Bảng HTWU1 2.1.1: If (ip+1 HTWUk) {X’ = X  ip+1}; Itemsets C E B A F 2.1.2: If (X’ ∉ TCk+1) { TWU 133 113 102 99 87 . Chèn (X’, U(X,Tj) + (UR(ip+1,Tj) - UR(ip+2,Tj), UR(ip+2,Tj)) vào bảng TCk+1 AU 57 45 40 24 12 (Itemsets, AU, SRU). Bước 2.2, Từ Bảng 7, loại D vì TWU(D) = 50 56 nên đưa C và . AU(X’) = AU(X’) + U(X,T ) + (UR(i ,T ) - j p+1 j HUIs ta được HUIs = {C :57}; UR(ip+2,Tj); } Bước 2.3, Phân chia các giao dịch cho các luồng, giả } sử luồng 1 phụ trách từ giao dịch 1 đến giao dịch 5; 3: For X’ TCk+1 { luồng 2: phụ trách từ giao dịch 6 đến giao dịch 10. Đợi 3.1: If (AU(X’) + SRU(X’) ≥ minutil) { luồng 1 và luồng 2 loại các phần tử có TWU nhỏ hơn Chèn X’ vào tập HTWU ; k+1 56 và sắp xếp các phần tử trong giao dịch giảm dần theo } 3.2: If (AU(X’) minutil){ AU xong. Chèn X’ vào tập HUIs; Bước 3, Phân công: luồng 1 phụ trách khai phá } HUIs với tiền tố: C, B, F; luồng 2: phụ trách khai phá 4: For (X’ HTWUk+1){ HUIs với tiền tố: E, A. 4.1: Xây dựng IT{X’} từ IT{X} ; 4.2: k = k +1; Công việc của các luồng (Threads): 4.3: PB-Miner (X’, k, ITX’); Bước 1, Tính TWU và AU cục bộ; //tìm tập lợi ích cao theo chiều sâu với tiền tố là Bước 2, Đợi Master tính xong TWU, AU toàn cục tập {X’} và nhận phân chia giao dịch và thực hiện loại bỏ D } 5: Return HUIs; trong các giao dịch và sắp xếp lại các phần tử trong từng giao dịch giảm dần theo AU. Kết quả như Bảng IV.2. Ví dụ minh họa 4. Trong phần này chúng tôi sẽ minh họa các bước của thuật toán với hai luồng xử lý. Cơ sở dữ liệu - 36 -
7. Các công trình nghiên cứu phát triển CNTT và Truyền thông Tập V-1, Số 17 (37), tháng 6/2017 Bước 3, Giả sử phân công như sau: luồng 1 phụ Lặp lại Bước 2, với bộ (2, 1) – trong giao dịch 2, trách khai phá HUIs với tiền tố: C, B, F; luồng 2: phụ sau vị trí 1 có phần tử B HCWU1 nên tạo tập {CB} trách khai phá HUIs với tiền tố: E, A. = {C}  B. Giả sử thực hiện trên luồng 1 với phần tử C: Ta thấy, {CB} TC2 nên đưa tương ứng: Itemsets Bước 3.1, k=1; = {CB}; U({CB},T2) = U({C},T1) + (UR(B,T2) - Bước 3.2, X={C} UR(,T2)) = 25 + (10 - 0) =35; RU({CB},T2) =  Bước 3.3, Xây dựng được bảng ITC như sau: trong UR( ,T2) = 0 vào TC2(Itemsets, AU, SRU). Kết quả như Bảng 11. giao dịch 1 ta có U(C,T1) =UR(C,T1) – UR(E,T1) = 12 – 10 = 2; RU(C,T1) = UR(E,T1) = 10. Tương tự cho Bảng 11. Bảng TC2 với tiền tố C các giao dịch 2, 3, 5, 6, 7, 10. Kết quả như Bảng 9. Itemsets AU SRU CE 7 5 Bảng 9. Bảng chỉ số IT của tiền tố C C CA 5 2 Tid Vị trí cuối U(C,Tj) RU(C,Tj) CF 4 0 1 1 12 - 10 = 2 10 CB 35 0 2 1 35 - 10 = 25 10 4 1 22 - 10 = 12 10 Lặp lại Bước 2, với bộ (4, 1) - trong giao dịch 4, sau vị 5 1 24 - 16 = 8 16 trí 1 có phần tử B HTWU1 nên tạo tập {CB} = {C}  6 1 6 - 2 = 4 2 B. 7 1 2 - 0 = 2 0 2.1.3. Vì {CB} TC2 nên chỉ cập nhật giá trị AU 10 1 14 - 10 = 4 10 và SRU của {CB} trong Bảng 9 như sau: . AU({CB}) = AU({CB}) + U({C},T4) + (UR(B,T4) - Bước 3.4, Luồng 1 gọi hàm PB-Miner({C},1,ITC) UR(,T4)) = 35 + 12 + (10 - 0) = 57 ; để khai phá các tập HUIs . SRU({CB}) = SRU({CB}) + RU(,T4) = 0 + 0 = 0. Hàm PB-Miner({C},k,ITC) Tương tự, lặp lại Bước 2 với các bộ (5, 1), (6, 1), (7, 1), (10, 1) ta được kết quả bảng TC2 với tiền tố C //Xây dựng bảng TC2 với C là tiền tố dựa trên bảng ITC kết quả như Bảng 12. Bước 1, TC2={}; Bảng 12. Bảng TC2 với tiền tố C Bước 2, Với mỗi bộ (j, p) trong ITC thực hiện. Giả Itemsets AU SRU sử với bộ (1, 1) – trong giao dịch 1 và vị trí 1. CE 39 11 2.1. Với mỗi phần tử ip+1 đứng sau vị trí p trong CA 19 2 giao dịch Tj thực hiện. Giả sử với phần tử E. CF 10 0 2.1.1. Ta có, E HCWU1 nên tạo tập {CE} = C  E; CB 57 0 2.1.2. Ta có, {CE} TC2 nên đưa tương ứng: Bước 3, duyệt từng tập X’ TC2. Itemsets = {CE}; U({CE},T1) = U({C},T1) + 3.1. Chỉ có AU({CB}) + RU({CB}) = 57 + 0 = 57 (UR(E,T1) - UR(A,T1)) = 2 + (10 - 5) = 7; > 56 nên HTWU2 = ({CB}). RU({CE},T1) = UR(A,T1) = 5 vào TC2(Itemsets, 3.2. Chỉ có AU({CB}) = 57 > 56 nên HUs = HUs AU, SRU).  {CB:57} = {C:57, CB:57}. Lặp lại Bước 2.1, với hai phần tử A, F sau vị trí 1 Bước 4, với mỗi X’ HTWU2 4.1. Xây dựng bảng IT{CB} từ bảng ITC được kết trong giao dịch 1 Bảng TC2 như Bảng 10. quả như Bảng 13. Bảng 10. Bảng TC2 với tiền tố C Bảng 13. Bảng chỉ số IT của tập {CB} Itemsets AU RU {CB} CE 7 5 Tid Vị trí cuối U({CB},Tj) RU({CB},Tj) CA 5 2 2 2 35 0 CF 4 0 4 2 22 0 - 37 -
8. Các công trình nghiên cứu phát triển CNTT và Truyền thông Tập V-1, Số 17 (37), tháng 6/2017 4.2. k = k + 1; //k = 1 +1 = 2 thuật toán TP [8], PB [2]. Đầu tiên, chúng tôi giới 4.3. Gọi hàm PB-Miner({CB}, k, IT{CB}) để tìm thiệu về dữ liệu dùng để thử nghiệm. Tiếp theo là kết tất cả tập lợi ích cao với tiền tố {CB} bằng cách quả thực hiện và số lượng các tập ứng viên. duyệt 2 bộ (2, 2) và (4, 2) trong bảng IT{CB} để sinh V.1. Môi trƣờng và dữ liệu ứng viên gồm 3 phần tử. Nhưng vị trí 2 trong giao Thuật toán được thực hiện trên máy tính HP core 7 dịch 2 và 4 là vị trí cuối nên không có tập ứng viên gồm 3 phần tử nào được sinh ra. Vậy, sau khi tìm due 2.4 GHz với 4 GB bộ nhớ, chạy trên Windows 7. kiếm tập lợi ích cao với tiền tố C được HUs = {C, Chương trình chúng tôi viết bằng Visual C++ 2010 với CB}. Và kết thúc hàm PB-Miner({C},1,IT{C}). thư viện lập trình đa luồng OPENMP, số luồng thử nghiệm là 2. Dữ liệu thử nghiệm gồm: Mushroom [17] Bảng 14. So sánh số lượng ứng viên trên hai mô hình Utility-list và TWU và T30I4D100K được sinh từ bộ sinh dữ liệu của IBM Luồng Tiền [16]. Đặc điểm của bộ dữ liệu được mô tả phía dưới: Utility-list TWU tố Database T D N {C}: 115, {C}: 115, T30I4D100K 30 100.000 100 {CB}: 57, {CB}: 57, Mushroom 23 8.124 119 C {CF}: 4, {CF}: 18, {CA}: 21, {CA}: 36, Trong đó: T – là số phần tử trung bình trong một giao ng 1 {CE}:50 {CE}: 50 dịch; N – là số phần tử khác nhau; D – số giao dịch. ồ Lu {B}: 102, Các bộ dữ liệu này đều chưa có giá trị lợi ích ngoài B {BF}: 45, cho từng phần tử và trong các giao dịch chỉ cho biết {BA}: 45 phần tử xuất hiện. Do vậy, chúng tôi sinh ngẫu nhiên F {F}: 75 số lượng cho mỗi phẩn tử trong mỗi giao dịch với giá {E}:93, {E}: 107, trị thuộc từ 1 đến 5 và lợi ích ngoài của mỗi phần tử từ {EB}:45, {EB}: 45, 0.1 đến 10. Hình 2a cho biết việc phân bổ lợi ích ngoài E {EF}: 35, {EF}: 69, của các phần tử trong T30I4D100K. Hình 2b cho biết ng 2 ồ {EA}:51, {EA}: 81, việc phân bổ lợi ích ngoài của các phần tử trong Lu {EAF}: 35 {EAF}: 57 Mushroom. {A}: 87, A {AF}: 57 Luồng 1 lặp lại bước 4 tìm tập lợi ích cao với tiền tố là B, F giống như phần tử C ở trên. Tương tự, luồng 2 thực hiện tìm tập lợi ích cao với tiền tố E, A. Kết thúc quá trình khai phá với ngưỡng lợi ích tối thiểu minutil = 56 trên 2 luồng ta thu được tập lợi ích Hình 2a. Biểu đồ phân bố lợi ích ngoài của các phần tử cao HUIs = {C:57, CB:57}. trong T30I4D100K Bảng 14 sẽ cho ta thấy sử dụng mô hình utility-list hiệu quả hơn mô hình TWU trong việc cắt tỉa các ứng viên. Mô hình utility-list sinh ra 10 ứng viên còn mô hình TWU sinh ra 16 ứng viên. V. KẾT QUẢ ĐÁNH GIÁ Trong phần này, chúng tôi chỉ so sánh kết quả thực hiện thuật toán PPB-Miner với thuật toán HP [13] vì Hình 2b. Biểu đồ phân bố lợi ích ngoài của các phần tử trong Mushroom thuật toán HP đã được so sánh, đánh giá tối ưu hơn với - 38 -
9. Các công trình nghiên cứu phát triển CNTT và Truyền thông Tập V-1, Số 17 (37), tháng 6/2017 V.2. Thời gian thực hiện và số ứng viên Kết quả thử nghiệm, so sánh giữa thuật toán PPB- Miner với thuật toán HP [13] trên bộ dữ liệu T30I4D100K và Mushroom. Hình 3a so sánh thời gian thực hiện khai phá tập lợi ích cao khi thay đổi ngưỡng lợi ích tối thiểu, Hình 3b so sánh số lượng ứng viên được sinh ra tương ứng với các ngưỡng lợi ích tối thiểu khác nhau. Hình 4a, 4b so sánh thời gian thực hiện khai phá tập lợi ích cao và số ứng viên sinh ra Hình 4b. So sánh số lượng ứng viên được sinh ra với ngưỡng lợi ích khác nhau giữa hai thuật toán tương ứng với các ngưỡng lợi ích tối thiểu khác nhau trên bộ dữ liệu Mushroom. VI. KẾT LUẬN Trong bài báo này chúng tôi đã phân tích ưu, nhược điểm của một số thuật toán khai phá tập lợi ích cao đã được đề xuất trong những năm gần đây, phân tích ưu, nhược điểm của mô hình TWU, Utility-list nhằm loại bớt tập ứng viên. Trên cơ sở đó, chúng tôi đã đề xuất một cấu trúc lưu trữ tối ưu về bộ nhớ, kết hợp danh sách lợi ích và chỉ số hình chiếu trong thuật toán song song trên mô hình chia sẻ bộ nhớ dựa trên chỉ số hình chiếu. Kết quả thử Hình 3a. So sánh thời gian thực hiện với ngưỡng lợi ích khác nhau nghiệm cho thấy thời gian thực thi và số lượng ứng viên sinh ra ít hơn một số thuật toán khác. Thời gian tiếp theo, chúng tôi sẽ thử nghiệm thuật toán song song trên nền tảng Hapdoop, kiến trúc MapRedue để có thể thực hiện với các dữ liệu lớn. TÀI LIỆU THAM KHẢO [1] A. C.F. AND T. S.K, Efficient Tree Structures for Highutility Pattern Mining in Incremental Hình 3b. So sánh số lượng ứng viên được sinh ra với Databases, 2009. ngưỡng lợi ích khác nhau [2] G. CHENG LAN, T. PEI HONG, AND V. S. TSENG, An efficient projection-based indexing approach for mining high utility itemsets, 2013. [3] Y. LIU, W. LIAO, AND A. CHOUDHARY, A Fast High Utility Itemsets Mining Algorithm, Proceedings of the 1st International Workshop on Utility-based Data Mining, New York, NY, USA, 2005, pp. 90–99. [4] M. LIU AND J. QU, Mining High Utility Itemsets Without Candidate Generation, Proceedings of the 21st ACM International Conference on Information Hình 4a. So sánh thời gian thực hiện với ngưỡng lợi ích khác nhau - 39 -
10. Các công trình nghiên cứu phát triển CNTT và Truyền thông Tập V-1, Số 17 (37), tháng 6/2017 and Knowledge Management, New York, NY, USA, [14] A. ERWIN, R. P. GOPALAN, AND N. R. 2012, pp. 55–64. ACHUTHAN, Efficient Mining of High Utility [5] K. SUBRAMANIAN, P. KANDHASAMY, AND S. Itemsets from Large Datasets, Advances in SUBRAMANIAN, A Novel Approach to Extract High Knowledge Discovery and Data Mining, T. Washio, E. Utility Itemsets from Distributed Databases, Comput. Suzuki, K. M. Ting, and A. Inokuchi, Eds. Springer Inform., vol. 31, no. 6+, pp. 1597–1615, 2013. Berlin Heidelberg, 2008, pp. 554–561. [6] V. S. TSENG, B.-E. SHIE, C.-W. WU, AND P. S. [15] B. VO, H. NGUYEN, T. B. HO, AND B. LE, Parallel YU, Efficient Algorithms for Mining High Utility Method for Mining High Utility Itemsets from Itemsets from Transactional Databases, IEEE Trans Vertically Partitioned Distributed Databases, Knowl Data Eng, vol. 25, no. 8, pp. 1772–1786, Aug. Proceedings of the 13th International Conference on 2013. Knowledge-Based and Intelligent Information and [7] R. AGRAWAL AND R. SRIKANT, Fast Algorithms Engineering Systems: Part I, Berlin, Heidelberg, 2009, for Mining Association Rules in Large Databases, pp. 251–260. Proceedings of the 20th International Conference on Nhận bài ngày: 09/12/2016 Very Large Data Bases, 1994, pp. 487–499. [8] Y. LIU, W. LIAO, AND A. CHOUDHARY, A Two- SƠ LƢỢC VỀ TÁC GIẢ phase Algorithm for Fast Discovery of High Utility ĐẬU HẢI PHONG Itemsets, Proceedings of the 9th Pacific-Asia Sinh năm: 1977 Conference on Advances in Knowledge Discovery and Tốt nghiệp đại học về Hệ thống Data Mining, Berlin, Heidelberg, 2005, pp. 689–695. thông tin quản lý năm 2000 tại [9] W. SONG, Y. LIU, AND J. LI, Vertical mining trường ĐH Thăng Long; về for high utility itemsets, 2012 IEEE International CNTT năm 2006 tại HVKTQS. Conference on Granular Computing, 2012, pp. Nhận bằng thạc sỹ CNTT 2008 429–434. tại Học viện Kỹ thuật Quân sự. [10] C. F. AHMED, S. K. TANBEER, B.-S. JEONG, AND Hiện nay đang công tác tại Khoa Toán và Tin học – Y.-K. LEE, HUC-Prune: an efficient candidate trường ĐH Thăng Long. pruning technique to mine high utility patterns, Appl. Lĩnh vực nghiên cứu: Khai phá dữ liệu, Tính toán Intell., vol. 34, no. 2, pp. 181–198, Apr. 2011. song song, Cơ sở dữ liệu phân tán. [11] V. S. TSENG, C.-W. WU, B.-E. SHIE, AND P. S. Email: phong4u@gmail.com; ĐT: 0912.441.435 YU, UP-Growth: An Efficient Algorithm for High Utility Itemset Mining, Proceedings of the 16th ACM NGUYỄN MẠNH HÙNG SIGKDD International Conference on Knowledge Sinh năm 1974. Discovery and Data Mining, New York, NY, USA, 2010, pp. 253–262. Tốt nghiệp đại học về CNTT năm 1998 tại Học viện Kỹ thuật [12] A. ERWIN, R. P. GOPALAN, AND N. R. Quân sự. Bảo vệ luận án Tiến sỹ ACHUTHAN, CTU-Mine: An Efficient High Utility năm 2004 tại Trung tâm tính Itemset Mining Algorithm Using the Pattern Growth toán – Viện hàn lâm khoa học Approach, 7th IEEE International Conference on Liên bang Nga. Computer and Information Technology (CIT 2007), 2007, pp. 71–76. Hiện nay đang công tác tại [13] D. PHONG AND N. HUNG, Một mô hình hiệu quả Phòng Sau đại học – Học viện Kỹ thuật Quân sự. khai phá tập mục lợi ích cao, Các Công Trình Lĩnh vực nghiên cứu: cấu trúc dữ liệu hiện đại, khai Nghiên Cứu Phát Triển Và Ứng Dụng CNTT-TT, phá dữ liệu, phân loại gói tin hiệu năng cao. pp. 26–36, Jun. 2015. Email: manhhungk12@mta.edu.vn ĐT: 0989.146.397 - 40 -