LỜI CAM ĐOAN
Tôi xin cam đoan đề tài khoa học “Khai phá dữ liệu và thuật toán khai
phá luật kết hợp song song ” này là công trình nghiên ứu của bản thân tôi.
c
Các số liệu và kết quả nghiên cứu nêu trong luận văn này là trung thực, được
các tác giả cho phép sử dụng và các tài liệu tham khảo như đã trình bày trong
luận văn. Tôi xin chịu trách nhiệm về luận văn của mình.
MỞ ĐẦU
Với sự bùng nổ và phát triển của công nghệ thông tin đã mang lại nhiều
hiệu quả đối với khoa học cũng như các hoạt động thực tế, trong đó khai phá dữ
liệu là một lĩnh vực mang lại hiệu quả thiết thực cho con người. Khai phá dữ
liệu đã giúp người sử dụng thu được những tri thức hữu ích từ những cơ sở dữ
liệu hoặc các kho dữ liệu khổng lồ khác.
Cơ sở dữ liệu trong các đơn vị, tổ chức kinh doanh, quản lý khoa học
chứa đựng nhiều thông tin tiềm ẩn, phong phú và đa dạng, đòi hỏi phải có
những phương pháp nhanh, phù h chính xác, hiệu quả để lấy được những
ợp,
thông tin bổ ích. Những “ tri thức” chiết suất từ nguồn cơ sở dữ liệu trên sẽ là
nguồn thông tin hỗ trợ cho lãnh đạo trong việc lên kế hoạch hoạt động hoặc
trong vi c ra quyết định sản xuất kinh doanh. T iến hành công việc như vậy
ệ
chính là thực hiện quá trình phát hiện tri thức trong cơ sở dữ liệu (Knowledge
Discovery in Database) mà trong đó k thuật khai phá dữ liệu (Data Mining)
ỹ
cho phép phát hiện những tri thức tiềm ẩn. Để lấy được thông tin mang tính tri
thức trong khối dữ liệu khổng lồ, cần thiết phải phát triển các kỹ thuật có khả
năng tích h các dữ liệu từ các hệ thống giao dịch khác nhau, chuyển chúng
ợp
thành một tập hợp các cơ sở dữ liệu ổn định có chất lượng. Các kỹ thuật như vậy
được gọi là kỹ thuật tạo kho dữ liệu và môi trường các dữ liệu nhận được khi áp
dụng các kỹ thuật tạo kho dữ liệu nói trên được gọi là kho dữ liệu (Data
Warehouse) [19, 24].
Một trong các nội dung cơ bản nhất trong khai phá dữ liệu và rất phổ biến
là phát hiện các luật kế t hợp. Phương pháp này nhằm tìm ra các tập thuộc tính
thường xuất hiện đồng thời trong cơ sở dữ liệu và rút ra các luật về ảnh hưởng
của một tập thuộc tính dẫn đến sự xuất hiện của một (hoặc một tập) thuộc tính
khác như thế nào. Bên cạnh đó, nhu cầu song s ong hóa và xử lý phân tán là rất
cần thiết hiện nay bởi kích thước lưu trữ dữ liệu ngày càng nhiều nên đòi hỏi tốc
độ xử lý cũng như dung lượng bộ nhớ hệ thống phải đảm bảo. Vì thế, yêu cầu
cần có những thuật toán song song hiệu quả cho việc phát hiện luật kết hợp.
Ứng dụng khai phá dữ liệu đã mang lại những lợi ích to lớn trong việc
tổng hợp và cung cấp những thông tin trong các nguồn cơ sở dữ liệu lớn. Hơn
nữa hiện nay nhu cầu song song hóa và xử lý phân tán là rất cần thiết bởi kích
thước d ữ liệu lưu trữ ngày càng lớn nên đòi hỏi tốc độ xử lý cũng như dung
lượng bộ nhớ hệ thống phải đảm bảo Vì thế, yêu cầu cần có những thuật toán
song song hiệu quả cho luật kết hợp.
Phương pháp nghiên c của luận văn là tổng hợp các kết quả dự a trên
ứu
các bài báo khoa ọc trong m số hội thảo quốc tế và các bài báo chuyên
h
ột
ngành, từ đó trình bày các vấn đề khai phá dữ liệu và xây dựng một số thuật
toán khai phá luật kết hợp song song.
Nội dung luận văn được trình bày trong 3 chương và phần kết luận
Chương 1: Tổng quan về khai phá dữ liệu: Giới thiệu tổng quan về quá
trình khai phá d liệu, kho dữ liệu và khai phá dữ liệu; kiến trúc của một hệ
ữ
thống khai phá dữ liệu; Nhiệm vụ chính và các phương pháp khai phá dữ liệu.
Chương 2: Khai phá luật kết hợp song song: Chương này trì nh bày tổng
quan về luật kết hợp; phát biểu bài toán khai phá dữ liệu, phát hiện luật kết hợp;
các khái ni m cơ bản luật kết hợp và các phương pháp khai phá luật kết hợp;
ệ
khai phá luật kết hợp với một số khái niệm mở rộ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 song song .
MỤC LỤC
Trang phụ bìa
Trang
Lời cám ơn
Lời cam đoan
Mục lục
Danh mục các kí hiệu, các chữ viết tắt
Danh mục các hình vẽ
Mở đầu 1
Chương 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 3
1.1. Khái niệm 3
1.2. Kiến trúc của một hệ thống khai phá dữ liệu 3
1.3. Các giai đoạn của quá trình khai phá dữ liệu 4
1.4. Một số kỹ thuật khai phá dữ liệu 6
1.5. Các cơ sở dữ liệu phục vụ cho khai phá dữ liệu 10
1.6. Các phương pháp chính trong khai phá dữ liệu 11
1.7. Các ứng dụng của khai phá dữ liệu 13
1.8. Khai phá dữ liệu và các lĩnh vực liên quan 14
1.9. Các thách thức trong phát hiện tri thức và khai phá dữ liệu 15
1.10. Kết luận chương 1 16
Chương 2: KHAI PHÁ LUẬT KẾT HỢP TRONG CƠ SỞ DỮ LIỆU
17
2.1. Mở đầu 17
2.2 Luật kết hợp 18
2.2.1 Các khái niệm cơ bản 18
2.2.2. Khai phá luật kết hợp 21
2.2.3. Cách tiếp cận khai phá luật kết hợp 22
2.3 Luật kết hợp cơ sở
24
2.3.1 Phát hiện các tập mục phổ biến 24
2.3.2 Sinh luật kết hợp 30
2.4. Khai phá luật kết hợp với một số khái niệm mở rộng
32
2.4.1. Giới thiệu 32
2.4.2. Khai phá luật kết hợp trọng số 32
2.4.3 Khai phá luật kết hợp tổng quát 43
2.5. Kết luận chương 2
49
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
50
50
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 51
3.2.1. Mô hình song song dữ liệu 51
3.2.2. Mô hình song song thao tác 51
3.3. Một số thuật toán khai phá luật kết hợp song song
52
3.3.1 Thuật toán Count Distribution (CD) 52
3.3.2. Thuật toán Data Distribution (DD) 54
3.3.3. Thuật toán Candidate Distribution 58
3.3.4. Thuật toán song song Fp-Growth 60
3.3.5 Thuật toán song song Eclat 65
3.4. Phân tích, đánh giá và so sánh việc thực hiện thuật toán
71
3.4.1. Phân tích và đánh giá thuật toán song song 71
3.4.2. So sánh việc thực hiện các thuật toán 73
3.5. Kết luận chương 3
74
Kết luận 75
Tài liệu tham khảo 77
86 trang |
Chia sẻ: maiphuongtl | Lượt xem: 2243 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu Luận văn Khai phá dữ liệu và thuật toán khai phá luật kết hợp song song, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trê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.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
51
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 kết 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
Hình 3.1. Mô hình song song dữ liệu
Mô hình song song dữ liệu thực thi thao 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.
Thao tác
1
Thao tác 1 Tập con DL 1.1
Thao tác n Tập con DL 1.n
Bộ xử lý n
Bộ xử lý 1
Thao tác 1 Tập con DL 1.1
Thao tác n Tập con DL 1.n
Bộ xử lý 1
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
52
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.
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ý
All reduce
P1 P2 P3
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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
53
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
X.count = ∑
=
p
j
j countX
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);
end;
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 toá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.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
54
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.
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.
(a) Phân hoạch CSDL
TID Items Số bộ xử lý
1 fdbe P0 2 feb
3 adb P1 4 aefc
5 ade P2 6 acfe
(b) Bước 1, 2 với k = 1
Item
Số đếm cục bộ Số đếm
tổng
thể P0 P1 P2
a 0 2 2 4
b 2 1 0 3
c 0 1 1 2
d 1 1 1 3
e 2 1 2 5
f 2 1 1 4
(c) Bước 3 với k = 1 và bước 1,2 với k=2
2-itemset
Số đếm cục bộ Số đếm
tổng
thể P0 P1 P2
ab 0 1 0 1
ac 0 1 1 2
ad 0 1 1 2
ae 0 1 2 3
af 0 1 1 2
bc 0 0 0 0
bd 1 1 0 2
be 2 0 0 2
bf 2 0 0 2
cd 0 0 0 0
ce 0 1 1 0
cf 0 1 1 0
de 0 0 1 0
df 0 0 0 1
ef 0 1 1 4
(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ể P0 P1 P2
ace 0 1 1 2
acf 0 1 1 2
ade 0 0 1 1
aef 0 1 1 2
bde 1 0 0 1
bef 2 0 0 2
cef 0 1 1 2
(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
Tập hợp tất cả Lk và các dữ liệu phân hoạch
P1 P2 P3
Phân hoạch 0 P ân hoạch 1 Phân hoạch 2
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
55
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
Dữ liệu ra: L
Phương pháp:
jC1 =1/p * | I |;
for (k=1; jkC ≠ φ; k++) do begin
// bước 1: tính các số đếm hỗ trợ cục bộ
count( jkC , 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
count( ikC , Dj);
end;
// bước 3: xác định các tập mục phổ biến ikL từ
i
kC ,
// trao đ ổi ikL 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ý
i
kL = {c | c ∈
i
kC | c.count ≥ s * |D1 ∪ D2 ∪…∪ Dp|};
Lk =
p
i
i
kL
1=
;
Ck+1 = apriori_gen(Lk);
i
kC 1+ = 1/p * | Ck+1|; // phân hoạch lại các tập mục ứng viên
end;
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ó.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
56
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 tập 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.
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:
Nhận các yêu cầu
Dữ liệu nào
được nhận ?
Cập nhật độ hỗ trợ
cho tập mục ứng cử
Xử lý
hết dữ liệu ?
Đọc một giao
dịch cục bộ
Tìm kiếm tập
mục ứng cử
NO
NO YES
YES
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
57
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
giai đoạn ( là giá trị heuristic), thuật toán này chia các tập mục phổ biến 1−L
(a) Phân hoạch CSDL
TID Items Các bộ xử lý
1 fdbe P0 2 feb
3 adb P1 4 aefc
5 ade P2 6 acfe
(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
(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
(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
(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 ∅ ∅
(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 ∅ ∅
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
58
cho các bộ xử lý sao cho mỗi bộ xử lý P i có thể sinh ra một imC (m ≥ ) duy
nhất độc lập với các bộ xử lý khác ( imC ∩
j
mC = φ, 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ử
lý có thể sinh các tập mục ứng cử trong imC 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 < : 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.
2) Bộ xử lý Pi sinh ra jkC 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
khi sinh ra jkC trong giai đoạn này.
3) Pi tính các số đếm hỗ trợ tổng thể cho các tập mục ứng cử trong jkC 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
được từ các bộ xử lý khác. Các jkL này cần cho việc cắt tỉa
j
1kC + trong bước cắt
tỉa sinh tập ứng cử.
5) Bộ xử lý Pi sinh jkL từ
j
kC 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 > :
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ý.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
59
2) Pi sinh ra jkC bằng cách sử dụng
j
1kL − cục bộ. Ta biết rằng Pi có thể
không nhận được j 1kL − 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
của một tập mục ứng cử) không có mặt trong bất kỳ j 1kL − nào với một tập mục
có mặt trong một số j 1kL − nhưng tập này chưa nhận được bởi bộ xử lý Pi. Pi
nhận biết bằng cách khảo sát jL 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
1kL − nhận được từ bộ xử lý này.
3) Pi thiết lập một giai đoạn trên D i và đếm. Sau đó Pi sinh ikL từ
i
kC và
truyền dị bộ ikL đế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ó phần 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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
60
đ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ộ DN/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 mục 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.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
61
(2) Khai phá song song và sinh tập mục phổ biến
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 gồm 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 trong [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.
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
3:4
P0
8:3
9:3
7:1 5:2
6:2
0:1
7:1
6:1
0:1
7:1
P1
3:3
9:1 8:2
9:2
5:2
6:1
5:1
6:1
7:1
0:1
7:1
5:1
3:4
8:4
P2
0:1 9:3
5:2 0:1
7:1 6:2
7:1 0:1
0:1
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
62
Để 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].
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
63
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 nhiệ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
(3 7 : 6) 0
(3 0 : 7)
6
Mức đệ qui đầu tiên
(3 6 : 6)
(5 6 : 6)
5
(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
(3 8 : 9) 9
(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
Phương pháp:
P1
3:6
P2
3:7
5:5
3:6 5:1
P1
P1
3:9
P2
3:9
8:8
9:1 8:6
3:7
P2
9:6
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
64
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)
Phương pháp:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
65
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ử Lk
đượ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ả
( ) 2/1SS
2
S
ii
i −=
cặp với tiền tố là định danh của lớp. Trong đó: |Si| là số phần
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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
66
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 giao cá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 k-subset 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ựng số đế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ộ
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
67
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
gán trọng số
2
m 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.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
68
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 cho 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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
69
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
kích thước
2
m (m là số các mục) trên vùng kênh bộ nhớ dùng chung, sau đó
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 chiề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 theo 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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
70
∑∑
∈∈
+
RrGg
Pircountpartialgcountglocal ),(_)(_
Với g ∈ G, r ∈ R: các tập mục
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
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)
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
Lớp tương đương cục bộ sau khi truyền
23
25
Lớp tương đương cục bộ (G)
34
35
Lớp tương đương cục bộ sau khi truyền
34
35
Lớp khác (R)
23
25
34
35
Lớp khác (R)
23
25
34
35
Lớp khác (R)
23
25
34
35
Hình 3.10: Quá trình chuyển đổi CSDL theo chiều dọc
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
71
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ý.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
72
Độ 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 song 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ó.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
73
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. Việc 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.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
74
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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
75
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à
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
76
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 thời 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.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
77
TÀI LIỆU THAM KHẢO
Tiếng việt
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.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
78
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.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
79
Đị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.
Các file đính kèm theo tài liệu này:
- 4LV08_CNTTLeThiVietHoa.pdf