Luận văn Khai phá dữ liệu và thuật toán khai phá luật kết hợp song song

ác tập mục ứng không cần thiết. Tính độ hỗ trợ cho các tập ứng cử Với một b ản ghi t, một tập các mục ứng cử C, tìm tất cả các tập mục trong C được hỗ trợ bởi t. Trước tiên, người ta phân các tập mục ứng cử vào các nhóm sao cho các tập mục ứng cử trong mỗi nhóm có cùng thuộc tính phân loại. Mỗi nhóm lập thành một “tập cha ứng cử” (super -candidate), trong đó, mỗi “tập cha ứng c ử” gồm có 2 phần. - Phần thứ nhất là các thuộc tính phân loại chung. - Phần thứ hai là một cấu trúc dữ liệu biểu diễn tập các giá rị của thuộc tính số. Khi đó nhi ệm vụ đếm độ hỗ trợ cho tập ứng cử được thực hiện qua 2 bước: (1) Tìm “tập cha ứng cử” được hỗ trợ bởi các thuộc tính phân loại trong bản ghi. Ta sử dụng cấu trúc dữ liệu cây băm để giảm bớt số lượng các “tập cha ứng cử” cần phải kiểm tra đối với một bản ghi. (2) Thuộc tính phân loại của “tập cha ứng cử” được hỗ trợ bởi một bản ghi cho trước, nên c ần phải tìm các tập mục ứng cử nào trong “tập cha ứng cử” là được hỗ trợ. Lưu ý các tập mục ứng cử trong một “ tập cha ứng cử” có cùng các giá trị đối với thuộc tính phân loại, nhưng có các giá trị khác nhau đối với thuộc tính số. 2.5. Kết luận chương 2 Trong chương 2 trình bày tổng quan về luật kết hợp, các định nghĩa, tính chất liên quan đến luật kết hợp: độ hỗ trợ, độ tin cậy, tập mục phổ biến, phát biểu bài toán khai phá luật kết hợp. Khai phá luật kết hợp trong CSDL có thể chia thành hai bài toán con: (1) Tìm tất cả các tập mục phổ biến từ CSDL. (2) Sinh ra các luật từ các tập mục phổ biến. Tro ng chương n ày tìrnh bày một số thuật toán cơ bản phát hiện tập mục phổ biến, phát hiện luật kết hợp từ các tập mục phổ biến nhằm làm tiền đề cho các nghiên cứu sau này như cải tiến thuật toán, thuật toán song song . Ngoài ra trong chương này còn trình bày một số hướng tiếp cận trong khai phá luật kết hợp như khai phá luật kết hợp trọng số; khai phá luật kết hợp tổng quát; khai phá luật kết hợp định lượng. Chương 3 MỘT SỐ PHƯƠNG PHÁP KHAI PHÁ LU ẬT KẾT HỢP SONG SONG VÀ PH ÂN T ÍCH Đ ÁNH GI Á CÁC THUẬT TOÁN 3.1. Nguyên lý thiết kế thuật toán song song Những thuật toán, trong đó có một số thao tác có thể thực hiện đồng thời được gọi là thuật toán song song. Tổng quát hơn, thuật toán song song là một các tập tiến trình hoặc các tác vụ có thể thực hiện đồng thời và có thể trao đổi dữ liệu với nhau để kết hợp cùng giải một bài toán đặt ra [1]. Có năm nguyên lý chính trong việc thiết kế thuật toán song so ng: 1. Các nguyên lý lập lịch: Giảm thiểu các bộ xử lý sử dụng trong thuật toán sao cho thời gian tính toán không tăng (xét theo khía cạnh độ phức tạp). 2. Nguyên lý hình ống: Nguyên lý này được áp dụng khi bài toán xuất hiện một dãy các thao tác {T1, T2,…, Tn}, trong đó Ti+1 thực hiện sau khi Ti kết thúc. 3. Nguyên lý chiađể trị: Chia bài toán thành những phần nhỏ hơn, tương đối độc lập với nhau và giải quyết chúng một cách song song. 4. Nguyên lý đồ thị phụ thuộc dữ liệu: Phân tích mối quan hệ dữ liệu trong tính toán để xây dựng đồ thị phụ thuộc dữ liệu và dựa vào đó để xây dựng thuật toán song song. 5. Nguyên lý điều khiển tranh đua: Nếu hai tiến trình cùng muốn truy cập vào cùng một dữ liệu thì chúng phải tương tranh với nhau, nghĩa là chúng có thể cản trở lẫn nhau. Ngoài ra, khi thi ết kế thuật toán song song cần quan tâm đến các vấn đề sau: - Hiệu quả thực hiện của thuật toán song song có thể rất khác nhau, mà yếu tố quan trọng nhất ảnh hưởng tới độ phức tạp tính toán là cấu hình tôpô liên kết mạng của các đơn vị xử lý. - Thu ật toán song song phải được thiết kế dựa trên những kiến thức về kiến trúc máy tính, ngôn ng ữ lập trình song song và các phương pháp tính toán. 3.2. Hư ớng tiếp cận chính trong thiết kế thuật toán khai phá luật kết hợp song song Hai hư ớng tiếp cận chính trong thi ết kế thuật toán khai phá luật ếkt h ợp song song đó là: (1) Mô h ình song song d ữ liệu và (2) Mô hình song song thao tác. 3.2.1. Mô hình song song dữ liệu Bộ xử lý 1 Thao tác 1 Tập con DL 1.1 Thao tác 1  Thao tác n Tập con DL 1.n Bộ xử lý n Hình 3.1. Mô hình song song dữ liệu Mô hình song song dữ liệu th ực thi th ao tác gi ống nhau hay thực thi chỉ lệnh trên một tập con dữ liệu cùng một thời điểm. Tất cả các bộ xử lý thực hiện chương trình giống nhau. Tuy nhiên, trong chương trình này, ta có thể s ử dụng cấu trúc điều khiển if – then – else để chỉ định lệnh nào được thực thi với bộ xử lý nào, tức là một số phần ch ương trình chỉ được thực hiện trên một hoặc một vài bộ xử lý. Trong mô hình song song ữd liệu, dữ liệu cần phải phân chia thành các tập con dữ liệu để tăng tốc đạt được bằng cách giảm khối lượng dữ liệu cần được xử lý trên mỗi bộ xử lý. Thu ật toán được thiết kế dựa vào mô hình song song d ữ liệu dễ dàng thực thi, ít phụ thuộc vào kiến trúc máy tính song song và năng suất cao. Tuy nhiên, nó cũng gặp khó khăn trong vi ệc cân bằng tải công việc do sự chênh lệch dữ liệu. 3.2.2. Mô hình song song thao tác Trong mô hình song song thao tác, mỗi bộ xử lý thực thi tập chỉ thị khác nhau. Các chương trình phối hợp với nhau để hoàn thành cùng một mục tiêu. Ý tưởng của mô hình song song giao tác là giảm độ phức tạp giao tác bằng cách chia thao tác thành các thao tác nhỏ hơn để thực thi. Tập dữ liệu hoạt động trong mỗi chương trình không nhất thiết giống nhau. Bộ xử lý 1 Thao tác 1 Tập con DL 1.1 Hình 3.2. Mô hình song song thao tác Các thuật toán song song được thiết kế dựa vào mô hình song song thao tác có độ phức tạp tính toán nhỏ hơn so với các thuật toán tuần tự do thao tác được chia thành những thao tác nhỏ hơn để dễ xử lý. Tuy nhiên, việc thực thi các thuật toán này lại phụ thuộc vào kiến trúc máy tính song song và mang tính chuyên dụng. 3.3. Một số thuật toán khai phá luật kết hợp song song 3.3.1 Thuật toán Count Distribution (CD) Thuật toán sử dụng kiến trúc không chia sẻ, mỗi bộ xử lý có một bộ xử lý chính và bộ nhớ phụ riêng. Các bộ xử lý này được kết nối với nhau bởi một mạng truyền thông và có thể được truyền thông tin cho nhau bằng việc truyền thông điệp. Dựa trên mô hình song song dữ liệu, dữ liệu được phân hoạch cho các bộ xử lý, mỗi bộ xử lý thực thi công việc giống như thuật toán Apriori tuần tự nhưng thông tin bởi các bộ xử lý trên các phân hoạch dữ liệu của nó. Số đếm hỗ trợ tổng thể được thiết lập thông qua môi trường truyền thông điệp MPI. P1 P2 P3 All reduce Phân hoạch 1 Phân hoạch 2 Phân hoạch 3 Hình 3.3. Sơ đồ thuật toán Count Distribution Các kí hiệu sử dụng trong thuật toán I: Tập các mục phân biệt trong CSDL giao dịch D D1, D2,…, Dp: Các phân hoạch CSDL, p là số các bộ xử lý minsup: Độ hỗ trợ tối thiểu L: Tập các tập mục phổ biến Nội dung thuật toán: Dữ liệu vào: I, minsup, D1, D2,..., Dp Ra: L Phương pháp: C1 = I; for (k=1; Ck ≠ ö; k++) do begin // bước 1: Tính các số đếm hỗ trợ cục bộ count(Ck, Di); // bộ xử lý thứ i // bước 2: Trao đổi các số đếm hỗ trợ với các bộ xử lý khác để // thu được các số đếm hỗ trợ trong D forall tập mục X ∈ Ck do begin end;  p X.count = ∑ X j .count ; j =1 end;  // bước 3: Xác định các tập mục phổ biến và sinh các tập mục // ứng viên Ck+1 Lk = {c c∈ Ck |c,count ≥ minsup *| D ∪ D2 ∪…∪Dp}; Ck+1 = apriori_gen(Lk); return L = L ∪ L2 ∪…∪ Lk; Giải thích thuật toán Trong thu ật toán CD,CSDL D được phân hoạch thành {D1, D2,…, Dp} và phân bố lần lượt cho các bộ xử lý Pi (1 ≤ i ≤ p). Thu ật ot án g ồm 3 bước cơ bản sau: Bước 1: Mỗi bộ xử lý Pi quét phân hoạch CSDL cụ bộ D i để tính các số đếm hỗ trợ cục bộ cho các tập mục ứng cử Ck. Bước 2: Mỗi bộ xử lý trao đổi các số đếm hỗ trợ cục bộ của các tập mục ứng cử trong CSDL D bằng cách sử dụng lệnh MPI_Allreduce trong MPI. Bước 3: Các tập mục phổ biến tổng thể Lk được xác định dựa vào ngưỡng hỗ trợ minsup và các tập mục ứng cử Ck+1 được sinh ra từ Lk bằng cách áp dụng thuật toán apriori_gen() trên mỗi bộ xử lý một cách độc lập. Thuật toán CD lặp lại bước 1 → 3 cho đến khi không còn tập mục ứng cử nào được sinh ra. Ví dụ: Cho CSDL giao dịch D, minsup = 33%. Phân hoạch D cho 3 bộ xử lý P0, P1 và P2, mỗi bộ xử lý có hai giao dịch (bảng a), k chỉ số vòng lặp. (a) Phân hoạch CSDL (b) Bước 1, 2 với k = 1 (c) Bước 3 với k = 1 và bước 1,2 với k=2 Item Số đếm cục bộ Số đếm tổng thể P P P a b c d e f 0 2 0 1 2 2 2 1 1 1 1 1 2 0 1 1 2 1 4 3 2 3 5 4 0 0 1 2 TID Items Số bộ xử lý 1 fdbe P 2 feb 3 adb P 4 aefc 5 ade P 6 acfe 1 2 (d) Bư ớc 3 với k = 2 và bư ớc 1,2 với k=3 3-itemset Số đếm cục bộ Số đếm tổng thể P P P ace acf ade aef bde bef cef 0 0 0 0 1 2 0 1 1 0 1 0 0 1 1 1 1 1 0 0 1 2 2 1 2 1 2 2 0 1 2  2-itemset Số đếm cục bộ Số đếm tổng thể P0 P1 P2 ab ac ad ae af bc bd be bf cd ce cf de df ef 0 0 0 0 0 0 1 2 2 0 0 0 0 0 0 1 1 1 1 1 0 1 0 0 0 1 1 0 0 1 0 1 1 2 1 0 0 0 0 0 1 1 1 0 1 1 2 2 3 2 0 2 2 2 0 0 0 0 1 4 (e) Bư ớc 3 với k = 3 và bước 1,2 với k=4 Trả về L, thuật toán kết thúc 4-itemset Số đếm cục bộ Số đếm tổng thể P0 P1 P2 acef 0 1 1 2 Hình 3.4. Phát hiện các tập mục phổ biến bởi thuật toán song song CD 3.3.2. Thuật toán Data Distribution (DD) Trong thuật toán DD, CSDL D được phân hoạch thành {D 1, D2,…, Dp} nên mỗi bộ xử lý làm việc với một tập dữ liệu không đầy đủ, do đó việc trao đổi dữ liệu giữa các bộ xử lý là cần thiết. Ngoài ra, các tập mục ứng cử cũng được phân hoạch và phân bố cho tất cả các bộ xử lý, mỗi bộ xử lý làm việc với tập mục ứng cử Ci khác nhau. P1 P2 P3 Tập hợp tất cả Lk và các dữ liệu phân hoạch 54 Số hóa bởi Trung tâmPhHâọnchlioệạuch– 0Đại học PThháâni Nhgouạycêhn1 Phân hohạtcthp:2//www.lrc-tnu.edu.vn Hình 3.5. Sơ đồ mô tả thuật toán Data Distribution Nội dung thuật toán: Dữ liệu vào: I, minsup, D1, D2,…, Dp 1 Dữ liệu ra: L Phương pháp: C j =1/p * | I |; k for (k=1; C j ≠ ö; k++) do begin // bước 1: tính các số đếm hỗ trợ cục bộ k count( C j , Di); // bộ xử lý thứ i // bước 2: truyền các phân hoạch cơ sở dữ liệu cục bộ đến các bộ // xử lý khác, nhận các CSDL cục bộ từ các bộ xử lý truyền đến, // quét Dj (1 ≤ i ≤ p, j ≠ i) để tính số đếm hỗ trợ tổng thể broadcast(Dj); for (j=1; (j≤ p and j ≠ i); j++) do begin receive(Dj); //từ bộ xử lý j k count( C i , Dj); end; L k // bước 3: xác định các tập mục phổ biến i  k từ C i , k // trao đ ổi Li  với các bộ xử lý để thu được các tập mục phổ biến Lk. // sinh tập mục ứng cử Ck+1 // phân hoạch Ck+1 và phân bố cho tất cả các bộ xử lý k k Li = {c | c ∈ k p C i | c.count ≥ s * |D1 ∪ D2 ∪…∪ Dp|}; end; Lk = U Li ; i =1 Ck+1 = apriori_gen(Lk); k +1 C i = 1/p * | Ck+1|; // phân hoạch lại các tập mục ứng viên return L = L1 ∪ L2 ∪…∪ Lk; Thuật toán Data Disbution có 3 bước cơ bản sau: Bước 1: Mỗi bộ xử lý quét phân hoạch CSDL cục bộ để tính các số đếm hỗ trợ cục bộ của các tập mục ứng cử được phân bổ cho nó. Bước 2: Mỗi bộ xử lý truyền phân hoạch CSDL của nó đến các bộ xử lý khác và nhận các phân hoạch CSDL từ các bộ xử lý khác truyền đến, Sau đó quét các phân hoạch CSDL nhận được , để tính các số đếm hỗ trợ tổng thể của các tập mục ứng cử trong CSDL D. Bước 3: Mỗi bộ xử lý các định các tập mục phổ biến từ phân hoạch tập mục ứng cử của nó, trao đổi với các bộ xử lý khác để nhận được tất cả các tập mục phổ biến Lk và sau đó sinh ra ậtp mục ứng cử C k+1 từ Lk, từ phân hoạch Ck+1 và phân bố các phân hoạch ứng cử đó cho tất cả các bộ lý. Thuật toán DD lặp lại bước 1 → 3 cho đến khi không còn tập mục ứng cử nào được sinh ra. Phân bố dữ liệu cục bộ của thuật toán Thuật toán thông báo đến p-1 hàm nhận đồng bộ MPI để nhận dữ liệu từ các bộ xử lý. Nếu dữ liệu là tập mục được nhận từ bộ xử lý khác, trước tiên bộ xử lý sẽ xử lý dữ liệu nhận được trước khi xử lý dữ liệu cục bộ của nó. Điều này tránh tắc nghẽn dữ liệu trong đường truyền thông hay bộ đệm. Nếu không có dữ liệu được nhận, bộ xử lý sẽ đọc một tập mục (giao dịch) từ dữ liệu cục bộ và cập nhật số đếm hỗ trợ cho tập mục ứng cử. Khi tất cả dữ liệu đều được sử dụng để cập nhật tập mục ứng cử cục bộ, giai đoạn tiếp theo sẽ tìm tập mục ứng cử cho xử lý tiếp theo. Nhận các yêu cầu Dữ liệu nào được nhận ? NO Đọc một giao dịch cục bộ YES Cập nhật độ hỗ trợ cho tập mục ứng cử NO Xử lý hết dữ liệu ?  YES  Tìm kiếm tập mục ứng cử Hình 3.6: Sơ đồ luồng thuật toán Data Distribution Ví dụ: Cho CSDL giao dịch D, minsup = 33%. Phân hoạch D cho 3 bộ xử lý P0, P1 và P2, mỗi bộ xử lý có hai giao dịch (bảng a), k chỉ số vòng lặp. Thuật toán DD thực hiện (theo thứ tự a, b, c, d, e, f, g, h, i) như sau: (a) Phân hoạch CSDL TID Items Các bộ xử lý 1 fdbe P 2 feb 3 adb P 4 aefc 5 ade P 6 acfe 0 (b) Bước 1 trong giai đoạn k=1 Item Số đếm Item Số đếm Item Số đếm P0 P1 P2 a 0 c 1 e 2 b 2 d 1 f 1 1 (d) Bước 3 khi k=1 và bước 1 khi k=2 Item Số đếm Item Số đếm Item Số đếm P0 P1 P2 ab 0 bc 0 ce 1 ac 0 bd 1 cf 1 ad 0 be 0 de 1 ae 0 bf 0 df 0 af 0 cd 0 ef 1 (f) Bước 3 khi k=2 và bước 1 khi k=3 Item Số đếm Item Số đếm Item Số đếm P0 P1 P2 ace 0 aef 1 bef 0 acf 0 bde 0 cef 1 ade 0 (h) Bước 3 khi k=3 và bước 1 khi k=4 Item Số đếm Item Số đếm Item Số đếm P0 P1 P2 acef 0 ∅ ∅ 2 (c) Bước 2 trong giai đoạn k=1 Item Số đếm Item Số đếm Item Số đếm P0 P1 P2 a 3 c 2 e 5 b 4 d 3 f 4 (e) Bước 2 trong giai đoạn k=2 Item Số đếm Item Số đếm Item Số đếm P0 P1 P2 ab 1 bc 0 ce 2 ac 2 bd 2 cf 2 ad 2 be 2 de 2 ae 3 bf 2 df 1 af 2 cd 0 ef 4 (g) Bước 2 trong giai đoạn k=3 Item Số đếm Item Số đếm Item Số đếm P0 P1 P2 ace 2 aef 2 bef 2 acf 2 bde 1 cef 2 ade 1 (i) Bước 2 trong giai đoạn k=4 Bước 3 trong giai đoạn k=4 Xuất L, kết thúc thuật toán Item Số đếm Item Số đếm Item Số đếm P0 P1 P2 acef 2 ∅ ∅ Hình 3.7: Phát hiện các tập mục phổ biến bởi thuật toán song song DD 3.3.3. Thuật toán Candidate Distribution Thuật toán Candidate Distribution thực hiện phân hoạch cả dữ liệu lẫn các tập mục ứng cử. Theo cách này, mỗi bộ xử lý có thể xử lý độc lập. Trong l giai đoạn ( l là giá trị heuristic), thuật toán này chia các tập mục phổ biến L l−1 C m cho các bộ xử lý sao cho mỗi bộ xử lý P i có thể sinh ra một i (m ≥ l ) duy m nhất độc lập với các bộ xử lý khác ( Ci  m ∩ C j  = ö, i ≠ j). Trong cùng một thời điểm, dữ liệu được phân chia lại sao cho một bộ xử C m lý có thể sinh các tập mục ứng cử trong i  một cách độc lập với tất cả các bộ xử lý khác. Tùy vào tính tối ưu của việc phân chia tập mục, một số phần cơ sở dữ liệu có thể có các bản sao trên một số bộ xử lý. Nội dung thuật toán Giai đoạn k < l : Sử dụng thuật toán CD hoặc DD Giai đoạn k = 1: 1) Phân hoạch Lk+1 cho các bộ xử lý sao cho các tập Lk-1 cân bằng nhau. C k 2) Bộ xử lý Pi sinh ra j từ phân hoạch Lk-1 đã gán cho nó. Lưu ý, P i có thể truy xuất đến Lk-1 đầy đủ và do đó có thể sử dụng phương pháp cắt tỉa chuẩn C k khi sinh ra j  trong giai đoạn này. C k 3) Pi tính các số đếm hỗ trợ tổng thể cho các tập mục ứng cử trong j và CSDL được phân hoạch lại thành các Di tại thời điểm này. 4) Sau khi Pi đã xử lý tất cả các dữ liệu cục bộ của nó và mọi dữ liệu nhận L k được từ các bộ xử lý khác. Các j tỉa sinh tập ứng cử.  C này cần cho việc cắt tỉa  j k +1  trong bước cắt L C k k 5) Bộ xử lý Pi sinh j từ j và truyền dị bộ đến N-1 bộ xử lý khác bằng cách sử dụng N-1 phép chuyển dị bộ. Giai đoạn k > l : 1) Bộ xử lý P i tập hợp tất cả các tập mục phổ biến mà các bộ xử lý khác chuyển đến nó. Chúng được sử dụng trong bước cắt tỉa khi sinh tập mục ứng cử nhưng không được sử dụng trong bước kết nối. Các tập mục đã nhận đư ợc từ bộ xử lý Pj sẽ có độ dài bằng k-1 hoặc nhỏ hơn k -1 (nếu bộ xử lý P j chậm hơn) hoặc lớn hơn k-1 (nếu bộ xử lý P j nhanh hơn). Bộ xử lý P i lưu giữ một phần trong các tập mục phổ biến được chuyển đến cho mỗi bộ xử lý Pj bởi nó. Các bộ đệm dùng để nhận mỗi tập mục phổ biến sẽ phản hồi lại sau khi xử lý. C k 2) Pi sinh ra j  L bằng cách sử dụng j k −1  cục bộ. Ta biết rằng Pi có thể L không nhận được j k −1  từ tất cả các bộ xử lý khác, nên Pi phải thận trọng trong lúc cắt tỉa. Nó cần phải nhận biết được một tập mục (một tập con k -1-itemset L của một tập mục ứng cử) không có mặt trong bất kỳ j k −1  nào với một tập mục L có mặt trong một số j k −1  nhưng tập này chưa nhận được bởi bộ x ử lý Pi. Pi L nhận biết bằng cách khảo sát j l−1  sử dụng phần tiền tố với độ dài 1-1 của các tập mục cần xem xét, bằng cách tìm kiếm bộ xử lý nào trả lời và kiểm tra nếu i L k −1 nhận được từ bộ xử lý này. L k 3) Pi thiết lập một giai đoạn trên D i và đếm. Sau đó Pi sinh i  C k từ i và L k truyền dị bộ i  đến các bộ xử lý khác bằng N-1 phép chuyển dị bộ. Phân hoạch CSDL Có thể mô tả thuật toán phân hoạch Lk qua ví dụ sau: Cho L=3 là {ABC, ABD, ABE, ACD, ACE, BCD, BCE, BDE, CDE}. Sau đó: L4 = {ABCD, ABCE, ABDE, ACDE, BCDE} L5 = {ABCDE}; L6 = {} Để ý đến tập con của L3, Z = {ABC, ABD, ABE} có pầhn tiền tố chung là AB và các tập ứng cử ABCD, ABCE, ABDE, ABCDE cũng có phần tiề n tố là AB. Hàm apriori_gen() sinh ra các tập mục ứng cử này bằng cách nối các item của Z. Do đó, gi ả sử rằng, các mục trong tập mục đã được sắp thứ tự, ta có thể phân chia các t ập mục trong L3 dựa vào phần tiền tố chung có độ dài (k-1). Đảm bảo rằng không có một phân hoạch nào được gán cho nhiều hơn một bộ xử lý có thể sinh ra các tập mục ứng cử một cách độc lập (chưa tính đến bước cắt tỉa). Việc phân chia lại CSDL giao dịch theo cách: Bất kỳ một bó giao dịch nào mà hỗ trợ cho một tập mục chứa trong L k mà tập mục đó đã được gán cho một bộ xử lý thì bó giao dịch đó sẽ được sao chép sang ổ đĩa cục bộ của bộ xử lý đó. Chính vì vậy mà các bộ xử lý có thể xử lý toàn bộ dị bội. 3.3.4. Thuật toán song song Fp-Growth Dựa vào thuật toán Fp-Tree tuần tự được trình bày trong [15]. Thuật toán này, ta xây dựng một số Fp -tree cục bộ trong môi trường bộ nhớ phân tán và sử dụng mô hình “Chủ - Tớ”. Dựa trên chiến lược lập lịch làm việc động trong giai đoạn hợp nhất các mẫu điều kiện cơ sở và giai đoạn khai phá để cân bằng khối lượng công việc trong quá trình thực thi. Khai phá tập mục song song Thu ật toán khai phá mẫu phổ biến song song gồm hai nhiệm vụ chính sau: (1) Xây dựng song song FP-Tree Giai đo ạn đầu của thuật toán khai phá song song là xây dựng các FP-Tree đ ồng thời trên m ỗi bộ xử lý. Tương t ự như thuật toán CD, ta chia CSDL giao dịch D cho P bộ xử lý. Đảm bảo rằng mỗi bộ xử lý có N/P giao dịch (DN/P), N và P lần lượt là tổng số giao dịch trong CSDL và số các bộ xử lý. Việc phân hoạch CSDL D cho P bộ xử lý được thực hiện một cách ngẫu nhiên. Sau khi phân hoạch dữ liệu, công việc tiếp theo là xác định 1- itemset phổ biến ( F1-itemset) trước khi xây dựng một FP-Tree cục bộ, Mỗi bộ xử lý tính toán đếm hỗ trợ (flocal(i)) của mỗi mục i bằng cách quét phân hoạch CSDL cục bộ D N/P, tất cả các bộ xử lý đếm flocal(i) cục bộ đến bộ xử lý Chủ. Bộ xử lý Chủ tập hợp tất cả các mục và kết hợp chúng lại để sinh số đếm hỗ trợ tổng thể ( fglocal(i)). Sau đó, các  ụmc có hỗ trợ nhỏ hơn ngưỡng hỗ trợ minsup được lược bỏ. Tập các 1-itemset phổ biến thu được sẽ được truyền cho tất cả các bộ xử lý trong nhóm. Bước tiếp theo là xây dựng các FP-Tree cục bộ, Mỗi bộ xử lý quét CSDL cục bộ DN/P của nó và chèn các mục phổ biến vào trong cây FP-Tree, Việc xây dựng FP-Tree bởi mỗi bộ xử lý với CSDL cục bộ của nó giống như trong thuật toán tuần tự [15]. Ví dụ: Cho một CSDL với 12 giao dịch và 10 mục (0, 1,…, 9) như trong hình 3.3. CSDL Dđược phân hoạch cho 3 bộ xử lý P 0, P1, P2. Mỗi bộ xử lý có số giao dịch bằng nhau. Với ngưỡng hỗ trợ là 6, ta có thể xác định nhanh số đếm hỗ trợ cho các mục như sau {3:11, 8:9, 5:8, 6:7, 0:7, 7:7}. Hình 3.8 chỉ ra các FP-Tree cục bộ ban đầu được xây dựng bởi P0, P1, P2. (2) Khai phá song song và sinh tập mục phổ biến 8:3 P0 3:4  6:1 P1 3:3 9:1 8:2  5:1 6:1  P2 3:4 8:4 9:3 7:1 5:2 6:2  0:1 7:1  5:1 0:1  9:2 5:2 6:1  7:1  0:1  9:3 5:2 0:1 0:1 Bộ xử lý Các giao dịch P0 3, 7, 8, 9 0, 3, 6, 7 3, 5, 6, 8, 9 0, 3, 5, 6, 7, 8, 9 P1 0, 3, 4, 5, 9 5, 6, 7 3, 4, 5, 8, 9 0, 3, 5, 6, 7, 8, 9 P2 0, 3, 4, 8 3, 5, 6, 7, 8, 9 0, 3, 4, 7, 8, 9 0, 3, 5, 6, 8, 9 7:1  0:1 7:1 6:2 7:1 0:1 7:1 Hình 3.8: Các phân hoạch CSDL và các FP-Tree cục bộ ban đầu Phương pháp khai phá bao ồgm một số giai đoạn sau: Trong giai đoạn đầu, ta xét toàn bộ FP-Tree và tạo ra các mẫu điều kiện cơ sở. Trong giai đoạn tiếp theo, ta tập hợp các mẫu điều kiện cơ sở từ các bộ xử lý để xây dựng FP- Tree điều kiện cơ sở (CFPT) cho mỗi mục phổ biến. Giai đoạn cuối cùng là thực thi việc khai phá bằng cách xây dựng đệ qui các mẫu điều kiện cơ sở và các CFPTs cho đến khi nó sinh tất cả các tập mục phổ biến. Xây dựng các mẫu điều kiện cơ sở Mỗi bộ xử lý thăm bảng tiêu đề (1-itemset phổ biến cục bộ) của nó theo hướng từ trên xuống và tạo ra các mẫu điều kiện cơ sở cho mỗi mục phổ biến. Việc thiết lập các mẫu điều kiện cơ sở bằng cách xét toàn bộ các nút trong FP- Tree cục bộ từ trên xuống như trong thuật toán được trình bày tr ong [15]. Quá trình xây dựng các mẫu điều kiện cơ sở được minh họa trong bảng 3.1. Xây dựng FP-Tree điều kiện cơ sở Khi tất cả các mẫu điều kiện cơ sở đã tìm được, các FP -Tree điều kiện được xây dựng bằng cách hợp nhất các mẫu điều kiện cơ sở. Phương pháp hợp nhất tương tự như đã đề cập trong [15] và [23]. Với mỗi mục phổ biến, các mẫu điều kiện cơ sở được hợp nhất sao cho các số đếm hỗ trợ của các mục giống nhau được tăng lên để tính số đếm hỗ trợ tổng thể. Nếu số đếm hỗ trợ tổng thể của một mục mà nhỏ hơn ngưỡng hỗ trợ tối thiểu, mục đó sẽ được lược bỏ khỏi FP-Tree điều kiện. Quá trình này được minh họa trong bảng 3.1 với ngưỡng hỗ trợ tối thiểu là 6.0. Để sinh các FP-Tree điều kiện ta sử dụng mô hình Chủ - Tớ. Bộ xử lý Chủ chuyển các mục cần được khai phá cho các bộ x ử lý Tớ. Các bộ xử lý Tớ sinh các FP-Tree điều kiện cho các mục đó, khi bộ xử lý Tớ hoàn thành việc sinh FP-Tree điều kiện, nó chuyển một mã thông báo đến bộ xử lý Chủ yêu cầu mục kế tiếp. Nhiệm vụ của bộ xử lý chủ là lắng nghe các yêu cầu đến từ bất kì bộ xử lý Tớ. Nó trả lời bằng cách chuyển mục kế tiếp đến bộ xử lý Tớ đó. Khi mà bộ xử lý Tớ nhận mục kế tiếp từ bộ xử lý Chủ chuyển đến, nó sẽ bắt đầu sinh CFPT cho mục này. Chi phí truyền thông trong thuật toán này tương đối thấp vì mỗi bộ xử lý chỉ chuyển mã thông báo. Hơn nữa, khối lượng công việc là cân bằng giữa các bộ xử lý trong nhóm do mỗi khi một bộ xử lý Tớ nào đó hoàn thành nhiệm vụ nó nhận một nhiệm vụ khác ngay lập tức. Items Các mẫu điều kiện cơ sở Các FP-Tree điều kiện P0 P1 P2 Trước khi lượt bỏ Sau khi lượt bỏ 7 9 8 3 : 1 0 6 5 9 8 3 : 1 0 6 3 : 1 0 6 5 9 8 3 : 1 6 5 : 1 6 5 9 8 3 : 1 0 9 8 3 : 1 (3:6, 8:5, 9:5, 5:4, 6:5, 0:4) (3 : 6) 0 6 5 9 8 3 : 1 6 3 : 1 5 9 3 : 1 6 5 9 8 3 : 1 8 3 : 1 6 5 9 8 3 : 1 9 8 3 : 1 (3:7, 8:5, 9: 5, 5:4, 6:4 ) (3 : 7) 6 5 9 8 3 : 2 3 : 1 5 9 8 3 : 1 5 : 1 5 9 8 3 : 2 (3:6, 8:5, 9:5, 5:6) (3:6, 5:6) 5 9 8 3 : 2 9 3 : 1 9 8 3 : 2 9 8 3 : 2 (3:7, 8:6, 9:7) (3:7, 8:6, 9:7) 9 8 3 : 3 3 : 1 8 3 : 2 8 3 : 3 (3:9, 8:8) (3:9, 8:8) 8 3 : 3 3 : 2 3 : 4 (3 : 9) (3 : 9) 3 ∅ ∅ ∅ ∅ ∅ Bảng 3.1: Các mẫu điều kiện cơ sở và các FP-Tree điều kiện cơ sở Sinh các tập mục phổ biến Sinh các tập mục phổ biến bằng cách xây dựng lầm lượt các mẫu điều kiện cơ sở và các cây điều kiện FP-Tree bởi mỗi bộ xử lý. Khi một nh ánh của FP-Tree điều kiện được xây dựng, ta thu được các tập hợp các mục khả năng như trong thuật toán FP-Growth tuần tự được trình bày trong [15]. Mô hình song songđược áp dụng là mô hình Chủ - Tớ. Bộ xử lý Chủ chuyển các mục cơ sở cần được khai phá cho các mục này và sinh các tập mục phổ biến. Trong mô hình này, khi một bộ xử lý Tớ hoàn thành nh m vụ, nó nhận được nhiệm vụ khác ngay lập tức, điều này làm cho các bộ xử lý bận cho đến khi kết thúc quá trình khai phá. Ở đây, việc cân đối khối lượng công việc xảy ra trong thời gian thực thi (runtime). Mô hình Chủ - Tớ được duy trì cho đến khi tất cả các tập mục phổ biến được sinh ra ứng với mỗi mục phổ biến trong F1-itemset. Sau đó tất cả các bộ xử lý Tớ này chuyển các tập mục phổ biến mà nó sinh ra đến bộ xử lý Chủ, giai đoạn khai phá kết thúc. Tương ứng với mỗi mục i ∈ F1-itemset, các tập mục phổ biến được sinh đệ quy bởi các mẫu điều kiện cơ sở và các FP -Tree điều kiện được chỉ ra trong hình 3.9. Ở đây, ta có 3 bộ xử lý và vì thế 2 bộ xử lý Tớ P1, P2 sinh tập mục phổ biến; Hình 3.9 cũng chỉ ra các tập mục phổ biến của CSDL D. Bộ xử lý 1 Bộ xử lý 2 Item Các FP-Tree điều kiện mức 1 Các tập mục phổ biến Item Các FP-Tree điều kiện mức 1 Các tập mục phổ biến 7 P1 3:6 (3 7 : 6) 0 P2 3:7 (3 0 : 7) 6 P1 3:6 5:1 5:5 Mức đệ qui đầu tiên (3 6 : 6) (5 6 : 6) 5 P2 3:7 9:1 8:6 9:6 (9 5 : 7) (3 5 : 7) (8 5 : 6) (3 9 5 : 7) (3 8 5 : 6) (8 9 5 : 6) (8 3 9 5 : 6) 8 P1 3:9 (3 8 : 9) 9 P2 3:9 8:8 (3 9 : 9) (8 9 : 8) (3 8 9 : 8) Hình 3.9: Quá trình sinh tập phổ biến bởi 2 bộ xử lý P1 và P2 Nội dung thuật toán FP-Growth Vào: Các phân hoạch CSDL DN/P và minsup. Ra: Tập các mục phổ biến 1) Quét CSDL cục bộ DN/P; 2) Tính số đếm hỗ trợ cục bộ của mỗi mục i flocal(i); 3) if (Bộ xử lý chủ) then 4) for (mỗi Bộ xử lý Tớ) do 5) Nhận flocal(i); 6) Gán F1-itemset = {i| ∑flocal(i); ≥ minsup, ∀ i} và truyền F1-itemset đến các Bộ xử lý Tớ 7) else Chuy ển flocal(i), ∀ i đ ến Bộ xử lý chủ và Nhận 1-itemset ph ổ biến F1-itemset; 8) Xây dựng FP-Tree cục bộ FPTlocal của các mục trong F1-itemset bằng cách quét DN/P cục bộ. 9) Duyệt toàn bộ FPTlocal và sinh ra các mẫu điều kiện cơ sở và truyền đến tất cả các bộ xử lý; 10) if (Bộ xử lý chủ) then begin 11) for(mỗi mục phổ biến i ∈ F1-itemset) do // Lập lịch tạo ra các CFPTs 12) Nh ận yêu cầu Bộ xử lý Tớ và chuyển mục i; 13) for(mỗi mục phổ biến i ∈ F1-itemset) do // Lập lịch cho việc khai phá 14) Nh ận yêu cầu Bộ xử lý Tớ và chuyển mục i cần được khai phá; 15) for(mỗi Bộ xử lý Tớ) do 16) Tập hợp các tập mục phổ biến và xuất tất cả các tập mục phổ biến; 17) end 18) else do //hợp nhất các mẫu điều kiện cơ sở 19) Yêu c ầu mục i tiếp theo và sinh FP-Tree đi ều kiện CFPTi cho mục ;i 20) until (hết các mục phổ biến); 21) Truy ền CFPTs đến tất cả các Bộ xử lý (từ Bộ xử lý Chủ) và nhận tất cả các CFPTs; 22) do 23) Yêu c ầu mục i tiếp theo vàgọi FP-Growth-OneItem (CFPTs, null i); 24) until (hết các mục phổ biến); 25) Chuyển các tập mục phổ biến đến Bộ xử lý Chủ; Thủ tục con FP-Growth-OneItem (Tree, á, i) 1) if(Tree chứa đường dẫn đơn) and (i ≠ null) then 2) Sinh tập mục có độ hỗ trợ ≥ minsup đối với mỗi tổ hợp các nút trong đường dẫn 3) else if(i ≠ null) then 4) Sinh tập mục â = i ∪ á và Xây dựng các mẫu điều kiện cơ sở của â và CFPTâ 5) else for mỗi i trong bảng tiêu đề của Cây 6) Sinh tập mục â = i ∪ á và Xây dựng các mẫu điều kiện cơ sở của â và CFPTâ 7) if CFPTâ ≠ ∅ then FP-Growth-OneItem(CFPTâ, â, null); 3.3.5 Thuật toán song song Eclat 1) Nhóm tập mục và giao dịch Phương pháp đ ể nhóm các tập mục phổ biến có liên quan với nhau bằng cách sử dụng lược đồ phân chia lớp tương đương. Mỗi lớp tương đương chứa tập các mục ứng cử quan h ệ tương đương với nhau. Bên cạnh, ta cũng sử dụng kỹ thuật tổ chức CSDL theo chi ều dọc để nhóm các giao dịch có liên quan với nhau. Phân lớp tương đương Gọi Lk là tập cá c itemset phổ biến. Không mất t ính tổng quát, giả sử L k được sắp xếp theo thứ tự từ điển. Ta có thể phân hoạch các tập mục trong Lk thành các lớp tương đương như sau: Nếu các phần t ử trong Lk có k – 1 thành viên đầu tiên giống nhau thì chúng thuộc cùng một lớp. Ký hiệu: Lớp tương đương chứa a là Sa = [a]. Trong phạm vi một lớp, ta sinh k-itemset ứng cử bằng cách kết nối tất cả  S i  = S (S  − 1)/ 2   cặp với tiền tố là định danh của lớp. Trong đó: |Si| là số phần  2  i i   tử của lớp có định danh là i. Các k- itemset ứng cử ứng cử được sinh ta từ các lớp khác nhau sẽ độc lập với nhau. Tổ chức cơ sở dữ liệu Thuật toán Eclat sử dụng cách tổ chức dữ liệu theo chiều dọc. Với các tổ chức dữ liệu theo chiều dọc, một CSDL gồm một danh sách các mục. Mỗi mục xác định một danh s ách các định danh của giao dịch có chứa mục đó, ký hiệu tid-List. Những ưu điểm của cách tổ chức theo chiều dọc: - Nếu tid-List đã được sắp theo thứ tự tăng dần thì độ hỗ trợ của k-itemset ứng cử có thể đã được tính toán bởi phép lấy giaocác tid-List c ủa hai (k-1)- subset b ất kỳ, Với cách tổ chức này, thuật toán không cần phải duy trì cấu trúc dữ liệu phức tạp, không như cây băm và c ũng không phải sinh ra tất cả các -ksubset c ủa các giao dịch hoặc thực hiện các thao tác tìm kiếm trên cây băm. - Các tid-List chứa tất cả các thông tin liên quan về một tập mục, vì vậy, khi tính độ hỗ trợ cho một tập mục không cần phải quét toàn bộ CSDL. Vì tất cả các thông tin về một lớp tương đương là được nhóm cùng nhau nên có thể sinh ra các tập mục phổ biến trước khi chuyển sang lớp tiếp theo. Ví dụ: Giả sử tid-List của AB, AC là: T(AB) = {1, 5, 7, 10, 50}; T(AC) = {1, 4, 7, 10, 11} Thì T(AB) ∩ T(AC) sẽ cho T(ABC) = {1, 7, 10} Ta có th ể tính ngay độ hỗ trợ bằng cách đếm số phần tử trong tid-List, n ếu số phần tử của tid-List l ớn hơn hoặc bằng độ hỗ trợ tối thiểu thì chèn ABC vào L3. 2) Thuật toán song song Eclat Nội dung thuật toán Begin /* Pha khởi tạo*/ 1) Duyệt qua các phân hoạch CSDL cục bộ 2) Tính toán số đếm hỗ trợ cục bộ cho tất cả các 2-itemset 3) Xây d ựngsố đếm hỗ trợ tổng thể cho các tập mục chứa trong L2 /*Pha biến đổi*/ 4) Phân hoạch L2 thành các lớp tương đương 5) Lập lịch L2 trên tập các bộ xử lý 6) Tổ chức phân hoạch dữ liệu cục bộ theo chiều dọc 7) Truyền các tid-List có liên quan tới các bộ xử lý khác 8) L2 cục bộ = nhận các tid-List từ các bộ xử lý khác /*Pha đồng thời*/ 9) forparallel mỗi lớp tương E2 trong L2 cục bộ Compute_Frequent(E2) /*Pha rút gọn*/ 10) Tập hợp các kết quả đưa ra các kết hợp end. Giải thích thuật toán 1) Phần khởi tạo Pha khởi tạo bao gồm việc tính toán tất cả các 2 -itemset phổ biến trong CSDL cần khai phá. Ta không cần tính số đếm hỗ trợ của các 1 -itemset vì việc xác định số đếm hỗ trợ của 2 -itemset có thể đạt được chỉ trong một lần duyệt CSDL. Để tính toán cho các 2-itemset, trên mỗi bộ xử lý sử dụng một mảng cục bộ và tiến hành chỉ số hóa các mục trong CSDL theo cả hai chiều. Mặt khác, mỗi bộ xử lý tính số đếm hỗ trợ cục bộ cho các 2-itemset và thực hiện phép lấy tổng rút gọn (sum-reduction) của tất cả các bộ xử lý để xây dựng các số đếm hỗ trợ tổng thể. Kết thúc pha khởi tạo, tất cả các bộ xử lý đều có những số đếm hỗ trợ tổng thể của tất cả các 2-itemset phổ biến L2 trong CSDL. 2) Pha biến đổi gồm 2 bước Bước 1: Đầu tiên L2 được phân hoạch thành các lớp tương đương. Sau đó các lớp tương đương này được gán cho các bộ xử lý sao cho cân bằng nhau. Bước 2: CSDL đã được biến đổi từ định dạng theo chiều ngang thành chiều dọc và được phân phối lại. Do đó, trong bộ nhớ cục bộ của mỗi bộ xử lý, các tid-List của tất cả các 2-itemset trong một lớp tương đương bất kỳ được nó gán cho nó. Lập lịch phân lớp tương đương Đầu tiên, ta phân hoạch L2 thành các lớp tươ ng đương bằng cách sử dụng tiền tố chung như mô tả ở trên. Tiếp theo, phân chia cho mỗi bộ xử lý một lớp tương đương. Mỗi lớp tương đương được gán một trọng số dựa vào số các phần tử trong một lớp. Vì phải khảo sát tất cả các cặp trong bước lặp tiếp theo, nên ta  m  gán trọng số   cho một lớp với m là số các ph ần tử của lớp tương đ ương tương ứng.  2  Sắp xếp các lớp dựa theo các trọng số và lần lượt gán cho bộ xử lý đã nạp ít nhất, nghĩa là bộ xử lý đó có trọng số toàn phần của các lớp nhỏ nhất. Nếu ước lượng tốt được số các tập mục phổ biến mà có thể nhận được từ một lớp tương đương thì có thể sử dụng ước lượng này làm một trọng số. Trong phạm vi một lớp, cũng có thể lấy độ hỗ trợ trung bình của các tập mục làm trọng số. Biến đổi CSDL theo chiều dọc Sau khi phân hoạch các lớp tương đương cân bằng giữa các bộ xử lý, ta biến đổi CSDL cục bộ từ định dạng theo chiều ngang theo chiều dọc. Điều này có thể thực hiện được trong 2 bước: Bước 1: Mỗi bộ xử lý duyệt CSDL cục bộ của nó và xây dựng các tid-List cục bộ cho tất cả các 2-itemset. Bước 2: Mỗi bộ xử lý cần xây dựng các tid-List toàn cục ch o các tập mục trong các lớp tương đương của nó. Do đó, nó phải gửi các tid -List này cho các bộ xử lý khác và nhận các tid-List từ các bộ xử lý khác gửi đến. 3) Pha đồng thời Cơ sở dữ liệu đã được phân bố lại, vì vậy các tid -List của tất cả các 2 - itemset trong các lớp tương đương cục bộ của nó là đã th ường trú trên đ ĩa cục bộ. Mỗi bộ xử lý có thể tính toán tất cả các tập mục phổ biến một cách độc lập. Nó đọc trực tiếp từ bộ nhớ cục bộ các tid-List của các 2 -itemset, sau đó sinh tất cả các tập mục phổ biến có thể trước khi chuyển sang bước tiếp theo, bước này bao gồm việc quét phân hoạch CSDL cục bộ đã được biến đổi một lần. Trong phạm vi mỗi lớp tương đương, cần khảo sát tất cả các cặp 2-itemset và thực hiện lấy giao các tid-List tương ứng. Nếu số các phần tử của tid-List kết quả lớn hơn hoặc bằng độ hỗ trợ tối thiểu thì tập mục mới được bổ sung vào L3. Sau đó, tiếp tục phân hoạch L 3 thành các lớp tương đương dựa trên các tiền tố chung độ dài bằng 2. Quá trình này được lặp lại thủ tục được thực hiện như sau: Begin Compute_Frequent(Ek-1) for tất cả các itemset I1 và I2 trong Ek-1 if((I1.tidList ∩ I2tidList) ≥ minsup) Bổ sung (I1 ∪ I2) vào Lk; Phân hoạch Lk thành các lớp tương đương; forparallel mỗi lớp tương đương Ek trong Lk Compute_Frequent(Ek); End Compute_Frequent 4) Pha rút gọn Tại thời điểm cuối của pha đồng thời, chúng ta trích rút các kết quả từ mỗi bộ xử lý và đưa ra kết quả. Quá trình thực hiện các bước truyền thông khác nhau của thuật toán. *) Giai đoạn khởi tạo: Khi đã thu được các số đếm hỗ trợ của tất cả các 2 -itemset, ta cần thực hiện một phép lấy tổng rút gọn để tính số đếm tổng thể. Ta chỉ định một mảng  m  kích thước   (m là số các mục) trên vùng kênh bộ nhớ dùng chung, sau đó  2  mỗi bộ xử lý truy cập mảng chung này (theo phương thức loại từ lẫn nhau) để tăng số đếm hỗ trợ hiện hành lên bởi các số đếm hỗ trợ cục bộ của nó và rồi đợi ở rào chắn cho tới bộ xử lý cuối cùng thực hiện xong việc truy cập mảng dùng chung để tăng số đ ếm hỗ trợ. Các số đếm hỗ trợ cục bộ được sử dụng để xây dựng các tid-List đảo toàn cục. *) Giai đoạn biến đổi Mỗi bộ xử lý quét phân hoạch CSDL cục bộ của nó lần thứ hai và xây dựng các tid-List theo chềi u dọc đối với tất cả các 2 -itemset phổ biến L 2. Vì CSDL gốc ban đầu được phân hoạch theo dạng khối nên CSDL đảo của mỗi bộ xử lý gồm các vùng định danh không liên tiếp. Ta sử dụng thông tin này cùng với thông tin của các số đếm hỗ trợ cục bộ để đặt tid-List của các bộ xử lý khác gửi đến vào các khoảng trống thích hợp, vì vậy tid-List toàn cục thu được xuất hiện th eo thứ tự từ điển, Với các lưu giữ này, chú ng ta tiết kiệm được chi phí sắp xếp cho các tid-List các giao dịch được phân tán một cách ngẫu nhiên. Quá trình biến đổi được hoàn thành qua 2 bước sau: Bước 1: Biến đổi tid-List cục bộ. Trước tiên, ta chia L2 thành hai nhóm. Các ật p mục thuộc các lớp tương đương mà được gán cho bộ xử lý cục bộ, kí hiệu là G, các tập mục còn lại thuộc các lớp tương đương khác, kí hiệu là R. Với mỗi bộ xử lý Pi, bộ nhớ dành ra một vùng nhớ có kích thước ∑ glocal _ count( g ) + ∑ partial _ count(r, Pi) g∈G Với g ∈ G, r ∈ R: các tập mục r∈R partial_count(r, Pi): Số đếm hỗ trợ của tập mục r trên bộ xử lý Pi. Sau đó, mỗi bộ xử lý thực hiện việc biến đổi và ghi tid -List của các phần tử của G vào các khoảng trống thích hợp. Các phần tử của R được để trống. Hình 3.10 dưới đây mô tả bước biến đổi CSDL trên ba bộ xử lý: L2 12 13 15 23 25 34 35 Số đếm hỗ trợ tổng thể 10 13 10 15 16 14 17 Số đếm hỗ trợ cục bộ P0 3 2 10 4 11 8 5 P1 3 10 0 7 1 3 5 P2 4 1 0 4 4 3 7 Phân chia L2 thành các l ớp tương đương và gán cho các bộ xử lý P0, P1, P2 23 25 34 35 P0 – (12, 13, 15); P1 – (23, 25); P2 – (34, 35). Kí hiệu: tid- List của P0, P1, P2 lần lượt là: Lớp tương đương cục bộ (G) Lớp khác (R) 12 13 15 Lớp tương đương cục bộ sau khi truyền 12 13 15 Lớp tương đương cục bộ (G)  23 25 34 35 Lớp khác (R) 23 25 Lớp tương đương cục bộ sau khi truyền 23 25 23 25 34 35 Lớp tương đương cục bộ (G) Lớp khác (R) 34 35 Lớp tương đương cục bộ sau khi truyền 34 35 Hình 3.10: Quá trình chuyển đổi CSDL theo chiều dọc Bước 2: Truyền tid-List Một khi việc biến đổi CSDL cục bộ hoàn thành, ta cần phải nhận các tid- List của tất cả các 2 -itemset trong G từ các bộ xử lý khác truyền đến và truyền các tid-List của R đến các bộ xử lý khác. Các tid-List đến được sao chép vào các khoảng trống thích hợp. Vì các phần giao dịch là phân biệt tăng đều, các tid-List của các tập mục trong G đã được viết ra ngoài đĩa, còn trong R thì bị loại bỏ. Để truyền các tid-List cục bộ qua kênh bộ nhớ, chúng ta sử dụng lợi thế của việc truyền thông điệp nhanh ở mức người sử dụng. Mỗi bộ xử lý xác định kích thước bộ đệm (2MB) cho một vùng truyền, một vùng nhận và dùng chung một định danh. Việc truyền thông được tiến hành theo cách khóa luân phiên các pha ghi đọc. Trong pha ghi, mỗi bộ xử lý ghi các tid-List của các tập mục trong P vào vùng truyền của nó ch o đến khi đạt đến giới hạn không gian bộ đệm. Tại thời điểm này, nó đi vào pha đọc, nó lần lượt quét vùng nhận của mỗi bộ xử lý và đặt các tid -List này của G vào các khoảng trống thích hợp. Khi vùng đọc đã được quét xong, nó đi vào pha ghi. Quá trình này được lặp lại cho đến khi nhận được tất cả các tid-List bộ phận. Tại thời điểm cuối của pha này, CSDL được định dạng theo chiều dọc. Sau đó, mỗi bộ xử lý đi vào pha đồng thời và tính toán các tập mục phổ biến như mô tả ở trên. Việc phép rút gọn cuối cùng đượ c thực hiện tương tự như phép rút gọn trong pha khởi tạo. 3.4. Phân tích, đánh giá và so sánh việc thực hiện thuật toán 3.4.1. Phân tích và đánh giá thuật toán song song Đánh giá thuật toán tuần tự có thể căn cứ chủ yếu vào thời gian thực hiện tính theo hàm của kích cỡ dữ liệu vào (input). Hàm này được gọi là độ phức tạp tính toán thời gian f(n) của thuật toán và được ký hiệu là O(f(n)). Một cách hình thức, O() được định nghĩa như sau: Một thuật toán có độ phức tạp tính toán tính toán f(n) = O(g(x)) ⇔ Tồn tại số dương C và số nguyên x0 sao cho 0 ≤ f(x) ≤ C * g(x), với mọi số lượng dữ liệu vào x ≥ x0. O(1) ký hiệu cho một hằng số bất kỳ. Ngoài ra, độ phức tạp tính toán của thuật toán song song còn phụ thuộc vào kiến trúc máy tính song song và số lượng bộ xử lý được phép sử dụng trong hệ thống và do vậy phụ thuộc vào thời gian trao đổi dữ liệu giữa các bộ xử lý. Độ phức tạp thời gian là thước đo quan trọng nhất đánh giá mức độ hiệu quả của thuật toán song song. Giả sử rằng mô hình tính toán của chúng ta có p bộ xử lý; dẫn đến mức độ song song có giới hạn; ngược lại, không bị giới hạn khi số lượng bộ xử lý không bị chặn. Mức độ hiệu quả của thuật toán được thể hiện ở mức độ song song của thuật toán. Là số lượng cực đại các phép toán độc lập có thể thực hiện đồng thời ở mỗi thời điểm thực hiện của thuật toán. Ký hiệu p(w) là độ song song của thuật toán, thì thuật toán đạt hiệu quả để giải bài toán có kích cỡ w là thuật toán chỉ cần sử dụng nhiều nhất p(w) bộ xử lý. Độ phức tạp thời gian của thuật toán song so ng sử dụng p bộ xử lý để giải một bài toán có kích cỡ n là hàm f(n, p) xác định thời gian cực đại trôi qua giữa điểm bắt đầu thực hiện thuật toán bởi một bộ xử lý và thời điểm kết thúc của các bộ xử lý đối với bộ dữ liệu vào bất kỳ. Có hai thao tác khác nhau trong các thuật toán song song: Các phép toán cơ sở như: +, -, *, /, AND, OR,… Các phép truyền dữ liệu trên kênh truyền. Vì độ phức tạp thời gian của thuật toán song song được xác định bởi số các phép toán cơ s ở và số các bước truyền tải dữ liệu giữa các b ộ xử lý với nhau. Nên từ đó suy ra, đ ộ phức tạp thời gian của thuật toán song song không chỉ phụ thuộc vào mô hình tính toán mà còn ph ụ thuộc vào bộ xử lý được sử dụng. Định nghĩa liên quan đến độ phức tạp của giải thuật song song là: Định nghĩa 3.1: Một thuật toán song song có độ phức tạp tính toán O(t) với p bộ xử lý khi nó thực hiện nhiều nhất là O(t * p) phép toán cơ sở. Định nghĩa 3.2: Một thuật toán song song có độ phức tạp tính toán O(t) sử dụng nhiều bộ xử lý để thực hiện O(e) phép toán cơ sở khi cài đặt với p bộ xử lý thì sẽ có độ phức tạp thời gian là O([e/p]+t). Định nghĩa 3.3: Một thuật toán song song có độ phức tạp tính toán O(t) với p bộ xử lý có thể cài đ ặt với [p/f] bộ xử lý (1≤ f ≤ p) thì sẽ có độ phức tạp thời gian là O(f * t). Ngoài ra, trong đánh giá thuật toán song song chúng ta còn cần phải xét tới độ tăng tốc và hiệu suất của nó. 3.4.2. So sánh việc thực hiện các thuật toán Dựa vào việc thực thi của thuật toán trên CSDL khác nhau cho thấy thuật toán FP-Growth thực thi nhan h nhất, tiếp đến là thuật toán Eclat, thuật toán Candidate distribution, CD, DD. Vệic theo thứ hạng này mang tính tương đối, mỗi thuật toán đều có những ưu điểm và nhược điểm riêng. Trong số các thuật toán khai phá dữ liệu luật kết hợp song song, các thuật toán song song được cài đặt dựa trên thuật toán Apriori (chẳng hạn như thuật toán CD, DD, Candidate distribution) đợưc sử dụng phổ biến bởi vì thực thi chúng đơn giản và dễ dàng. Hơn nữa, các luật kết hợp có thể được sinh trực tiếp dựa vào cách thức khai phá tập mục. Bởi vì các tập mục ứng cử được sinh ta thì tất cả các thông tin của tập con đều được tính toán. Tốc độ thực hiện các thuật toán này tỉ lệ với số lượng các giao dịch nhưng có thể gặp khó khăn trong việc xử lý quá nhiều mục và nhiều mẫu khi CSDL quá lớn. Thuật toán song song Eclat có ưu điểm là tính toán nhanh độ hỗ trợ thông qua tập giao dịch tid-List. Thuật toán được thiết kế dựa trên mô hình song song thao tác, có ốt c độ thực thi nhanh trên hệ thống đa bộ xử lý bộ nhớ phân tán. Hạn chế chủ yếu của thuật toán này là chúng cần phải sinh ra và phân bố lại các tid-List. Hơn nữa, với một tập mục phổ biến có kích thước lớn, các phần chung chủ yếu của các tid-List này được lấy giao lặp lại nhiều lần đối với tất cả các tập con của nó. Để giảm bớt tình trạng này, một cách thiết lập tối ưu khác là chỉ kiểm tra những thay đổi trong tid-List thay cho việc lưu giữ các tid -List toàn cục thông qua các vòng ặl p sao cho nó giảm đáng kể khối lượng dữ liệu được tính toán. Thuật toán FP-Growth xử ký lượng lớn CSDL rất hiệu quả và có tốc độ thực thi tỷ lệ rất hiệu quả so với lượng giao dịch lớn, sự lặp lại nhiều lần hay lặp lại nhiều lần cục bộ các giao dịch sẽ được kết hợp lại tạo thành các nhánh của FP-Tree. Tuy nhiên ích lợi này không tăng khi tăng thêm số lượng bộ xử lý bởi vì nhiều FP -Tree cho các tập giao dịch khác nhau là hoàn toàn dư thừa. Lợi ích này cũng rất hạn chế đối với các CSDL rải rác. Thuật toán này có thể xử lý một số lượng lớn các mục bằng việc gán mục này cho nhiều bộ xử lý mà không quan tâm về không gian lưu trữ các tập mục. 3.5. Kết luận chương 3 Trong chương này đã trình bày nguyên lý thiết kế thuật toán song song và hai hướng tiếp cận chính trong việc thiết kế thuật toán khai phá luật kết hợp song song đó là: Mô hình song song dữ liệu và mô hì nh song song giao tác. Một số thuật toán khai phá luật kết hợp song song được thiết kết dựa trên hai mô hình này như thuật toán Count Distribution, Data Distribution, Candidate Distribution, Eclat, FP-Growth. Chương này cũng đánh giá chung về những ưu nhược điểm và so sánh việc thực hiện của mỗi thuật toán làm cơ sở cho việc cải tiến thuật toán và phát hiện các thuật toán song song mới KẾT LUẬN 1. Kết quả đạt được trong luận văn Khai phá dữ liệu là một lĩnh vực quan trọng, nó bao gồm nhi ều lĩnh vực và nhiều kỹ thuật khác nhau. Luận văn đề cập đến các nội dung về phát hiện tri thức, khai phá dữ liệu. Ứng dụng của khai phá dữ liệu là rất lớn và có ích trong mọi hoạt động sản xuất, kinh doanh và trợ giúp cho việc hoạch định chiến lược của các nhà quản lý cũng nh ư hỗ trợ ra quyết định. Bên cạnh, luận văn còn đề cập đến những khó khăn, thách thức trong việc ứng dụng và nghiên cứu các kỹ thuật khai phá dữ liệu. • Về mặt lý thuyết, khai phá dữ liệu là một công đoạn trong tiến trình lớn , tiến trình khám phá tri thức từ CSDL. Phương pháp khai phá dữ liệu có thể là: phương pháp sử dụng cây quyết định và luật, phương pháp quy nạp, phương pháp phát hiện luật kết hợp, các phương pháp dựa trên mẫu, mô hình phụ thuộc dựa trên đồ thị xác suất, các phương pháp phân lớp và hồi quy phi tuyến tính…, các phương pháp trên có thể áp dụng trên dữ liệu thông thường và trên tập mờ. Trong luận văn đã trình bày chi tiết các vấn đề về khai phá luật kết hợp: từ các khái niệm cơ sở, bài toán xuất phát đến mô hình hình thức , các thuật toán khai phá luật kết hợp cơ sở và các thuật toán khai phá luật kết hợp trọng số, luật kết hợp định lượng và luật kết hợp tổng quát. • Về thuật toán khai phá luật kết hợp, luận văn trình bày một số thuật toán tuần tự tiêu biểu về khai phá luật k ết hợp như: Apriori, phân hoạch, AIS, SETM,… • Trên cơ sở các thuật toán tuần tự, luận văn trình bày chi tiết các thuật toán song song như Count Distribution, Data Distribution, Candidate Distribution, Eclat, FP-Growth. Việc đánh giá thuật toán làm rõ bản c hất của luật kết hợp cũng là một trong những nội dung được trình bày trong luận văn. 2. Hướng nghiên cứu tiếp theo Trên cơ sở những nghiên cứu đã được trình bày trong luận văn, tiếp tục nghiên cứu sâu hơn các thuật toán khai phá luật kết hợp song song , tìm cách cải tiến nhằm khắc phục các nhược điểm của các thuật toán song song hiện có và các thuật toán khai phá dữ liệu song song khác để áp dụng vào một số bài toán khai phá dữ liệu phù hợp cho giai đoạn hiện nay như: quy luật thị trường, chứng khoán và bất động sản, dự đoán rủi ro tín dụng, định hướng kinh doanh, y tế… Trong quá trình học tập, tìm hiểu và nghiên cứu cùng với khoảng thời gian làm luận văn, tôi đã cố gắng tập trung tìm hiểu và tham khảo các tài liệu liên quan. Tuy nhiên do ờthi gian nghiên cứ u có hạn nên không tránh khỏi những thiếu sót rất mong nhận được sự nhận xét và những đóng góp ý kiến của các thầy cô giáo và những ai quan tâm để luận văn được hoàn thiện hơn. Tiếng việt TÀI LIỆU THAM KHẢO 1. Đoàn Văn Ban, Nguyên M ậu Hân (2006) Xử lý song song và phân tán, Nxb Khoa học & Kỹ thuật, Hà Nội. 2. Nguyễn Thanh Bình (2007), Khai phá dữ liệu: Khái niệm và kỹ thuật, Huế. 3. Đỗ Phúc (2006), Giáo trình khai phá dữ liệu , Nxb Đại học Quốc gia TP Hồ Chí Minh. 4. Hồ Thuần, Hồ Cẩm Hà (2006), Các hệ cơ sở dữ liệu Lý thuyết và Thực hành, Tập 2, Nxb Giáo dục. 5. Nguyễn Thanh Thủy (2003), Phát hi ện tri thức và khai phá dữ liệu: Công cụ, phương pháp và ứng dụng, Bài gi ảng Trường Thu, Hà Nộ.i Tiếng Anh 6. A. Savaere, E Omiecinski and S.Navathe (1995), An efficient algorihm for mining association rules in large databases, In 21st VLDB Con&. 7. Agrawal and J.Shafer (1996), Parallel mining of association rules, In IEEE Trans, on Knowledge and Data Engg, pages 8(6): 962 – 969. 8. CAI, Chun Hing (1998), Mining Association Rules With Weighted Items, The Chinese University of Hong Kong, August. 9. H.Mannila, H. Toivonen and I.Verkamo (1994), efficient algorithms for discovering association rules, In AAAI Wkshp, Knowledge Discoverry in Databases, July. 10. J.Han, J.Pei and Y.Yin (2000), Mining Frequent Pattens Without Candidate Generation, In ACM SIGMOD. 11. J.S.Park, M.Chenand P.S.Yu (1995), Efficient parallel data mining for association rules, In ACM Intl, Conf Information and Knowledge Management, November. 12. Jiamwei Li, Ying Lui, Wei-Keng Liao, Alok Choudhay (2006), Parallel Data Mining Algorithms for Association Eules and Clustering, by CRC Press, LLC. 13. Kwok-Leung Tsui, Victoria C,P. Chen, Wei Jiang, Y. Alp Aslandogan, (2001), Data Minning Methods and applications. 14. M, Holshimer, M.Kersten, H.Manila and H. Toivonen (1995), A perspectiveon databases and data mining, In lsr Ind, Conf Knowledge Discovery and Data Mining, August. 15. M.Houtsma and A.Swami (1995), Set-oriented miningof association rules in relational databases, In 1 lth Intln, Conf Data Engineeng. 16. M.J. Zaki, S.Parthasarathy, W.Li and M.Ogihara (1997), Evaluation of sampling for data mining of association rules, In 7 th Intl, Wkshp. Research Issues in Data En, gg, Apr. 17. Ming-Syan Chen, Jiawei Han and Philip S.Yu (1996), Data Mining: An Overview from a Databases Perpective, IEEE Transactions on Knowledge and Data Engineering, Vol.8, No.6, pp. 866-883. 18. Margaret H. Dunham, Yongqiao Xiao, Le Gruenwald, Zahid Hossain, (2003) A survey of Assocition rules, Department of Computer Science and Engineering Southerm Methodist University Dallas. 19. O.R.Zaiane, Mohammad El-Haijj and Paul L (2001), Fast Parallel Association Rule Mining Without Candidacy Generation, Proc. Of the IEEE 2001 International Conference in Data Minning (ICDM’2001), San Jose, CA, USA, November 29-December 2. 20. R Agmwal, H.Manila, R. Srikant, H. Toivonen and A. 1. Verkamo (1996), Fast discovery of association rules, In U.Fayyad and et al, editors, Advances in Knowledge Discovery and Data Minning. MIT Press. 21. R. Agrawal and R. Srikant, (1994), Fast algorithms for minning association rules, In 20th VL.DBConf, Sept. 22. R. Agrawal, T. Imielinski and A. Swami (1993), Minning association rules between sets of items i large databases, In ACM SIGMOD Intil. C@ Managenment of Data, May. 23. Two Crows (2005), Introduction to Data Minning and Knowledge Discovery, Edition third. 24. Usama Fayyad, Gregory Piatetsky-Shapiro, and Padhraic Smyth, (2002) From Data Minning To Discory Knowledge in Database. Địa chỉ trên Internet 25. ://www.cs.cmu.edu/~scandal/nesl/algorithms.html 26. ://computing.llnl.gov/tutorials/parallel_comp/index.html 27. MPI home page.