dragonred56
New Member
Download Luận văn Luật kết hợp theo tiếp cận lý thuyết tập thô và khai phá dữ liệu song song
mục lục
Nội dung Trang
Phần mở đầu 3
Chương 1. tổng quan về khai phá dữ liệu và khai phá dữ liệu song song8
1.1. Khai phá dữ liệu và phát hiện tri thức trong Cơ sở dữ liệu 8
1.1.1. Sơ bộ về khai phá dữ liệu và phát hiện tri thức trong cơ sở dữ liệu 8
1.1.2. Nội dung của khai phá dữ liệu 11
1.1.3. Các phương pháp khai phá dữ liệu phổ biến và lựa chọn phương pháp 13
1.1.4. Ưu thế của khai phá dữ liệu 15
1.1.5. Một số thách thức trong ứng dụng và nghiên cứu kỹ thuật khai phá dữ liệu 17
1.2. Khai phá dữ liệu song song 20
1.2.1. Các hệ thống tính toán song song 21
1.2.2. Các chiến lược khai phá dữ liệu song song 26
1.2.3. Các mô hình chi phí 28
Kết luận chương 1 31
Chương 2. Luật kết hợp theo cách tiếp cận của lý thuyết tập thô 32
2.1. Khái niệm luật kết hợp và một số công nghệ phát hiện 32
2.1.1. Luật kết hợp 32
2.1.2. Một số công nghệ phát hiện luật kết hợp tuần tự 35
2.2. Luật kết hợp theo cách tiếp cận của lý thuyết tập thô 40
2.2.1. Tập thô 40
2.1.2. Luật kết hợp theo cách tiếp cận lý thuyết tập thô 42
Kết luận chương 2 51
Chương 3. Phát hiện song song luật kết hợp 52
3.1. Không gian thiết kế song song 52
3.1.1. Nền phần cứng 52
3.1.2. Mô hình song song hóa 53
3.1.3. Cách thức cân bằng tải 54
3.2. Một số mô hình phát hiện song song luật kết hợp 55
3.2.1. Các hệ phân tán bộ nhớ 55
3.2.2. Các hệ chia sẻ bộ nhớ 65
3.2.3. Các hệ phân cấp 67
3.3. Mô hình tập thô phát hiện song song luật kết hợp 70
3.3.1. Thuật toán cho mô hình tập trung 72
3.3.2. Thuật toán cho mô hình phân tán 73
Kết luận chương 3 74
Phần kết luận 75
Tài liệu tham khảo
Để tải bản DOC Đầy Đủ xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
thống phân tán, việc nghiên cứu và đề xuất các thuật toán khai phá dữ liệu song
song trong các mô hình song song là rất có ý nghĩa. Tùy thuộc vào cơ sở dữ liệu
thực tế, việc lựa chọn cách thức song song để song song hóa thuật toán khai phá dữ
liệu tuần tự là rất quan trọng (mục 1.2.2), nó ảnh h−ởng trực tiếp tới giá thành thực
hiện việc khai phá dữ liệu. Một số mô hình chi phí hình thức cho khai phá dữ liệu
song song đã đ−ợc tổng kết (mục 1.2.3).
-32-
Ch−ơng II. Luật kết hợp theo tiếp cận lý
thuyết tập thô
II.1. khái niệm Luật kết hợp và một số công nghệ phát hiện
II.1.1. Luật kết hợp
Phát hiện luật kết hợp là sự khai phá dữ liệu không đ−ợc định h−ớng hay
không có giám sát trên dữ liệu có độ dài thay đổi, nó cho ra các kết quả rõ ràng và
dễ hiểu. Mục đích của khai phá luật kết hợp là tìm tất cả các tập con các đối t−ợng
hay thuộc tính xuất hiện th−ờng xuyên trong nhiều giao dịch hay bản ghi trong cơ
sở dữ liệu, thêm vào đó là rút ra các luật về một tập con đối t−ợng có ảnh h−ớng tới
sự xuất hiện của tập con các đối t−ợng khác nh− thế nào [15].
Mặc dù phát hiện luật kết hợp có cách đặt bài toán đơn giản, nó đòi hỏi l−ợng
tính toán và truy xuất dữ liệu rất lớn. Khi dữ liệu tăng lên cả về số h−ớng (số các
thuộc tính) và kích th−ớc (số giao dịch), một trong những tính chất cần thiết của
phát hiện luật kết hợp là khả năng mở rộng đ−ợc: khả năng xử lý kho dữ liệu rất lớn.
Các thuật toán tuần tự không thể cho khả năng này trong các cơ sở dữ liệu lớn. Vì
vậy ta phải dựa vào tính toán song song và phân tán hiệu suất cao.
Tập phổ biến là cơ sở để tạo các luật kết hợp [4]. Chúng ta xem xét một ví dụ
khai phá luật kết hợp. Cho một tập các thuộc tính I = {I1, I2,..., Im}, một giao dịch T
đ−ợc định nghĩa là một tập con bất kỳ các thuộc tính trong I. Giả sử cơ sở dữ liệu D
là một tập n giao dịch, mỗi giao dịch đ−ợc gán một định danh giao dịch duy nhất
TID. Giao dịch T là hỗ trợ một tập X ⊆ I nếu nó chứa tất cả các thuộc tính trong X,
tức là X ⊆ T. Độ hỗ trợ của một tập thuộc tính X, ký hiệu σ(X), là tỉ lệ của tất cả các
giao dịch trong D hỗ trợ X.
-33-
Định nghĩa 2.1 (Tập phổ biến)
Tập X ⊆ I đ−ợc gọi là tập phổ biến nếu có σ(X) ≥ smin với smin là độ hỗ trợ
tối thiểu cho tr−ớc.
Một tập X có lực l−ợng k = |X| đ−ợc gọi là k-itemset. Có ba tính chất quan
trọng của các tập phổ biến, đó là:
- Nếu A ⊆ B với A, B là các tập thuộc tính thì σ(A) > σ(B), bởi tất cả các giao
dịch trong D hỗ trợ B thì đều phải hỗ trợ A.
- Tập cha của một tập không phổ biến là tập không phổ biến: Nếu tập thuộc
tính A không đủ độ hỗ trợ, tức là σ(A) ≤ smin thì mọi tập B chứa A cũng sẽ
không phổ biến, bởi vì σ(B) ≤ σ(A) ≤ smin.
- Tập con của tập phổ biến là tập phổ biến: Nếu tập thuộc tính B là phổ biến
trong D, tức là σ(B) ≥ smin, thì mọi tập con A của B cũng sẽ là phổ biến, bởi
σ(A) ≥ σ(B) ≥ smin.
Một tập phổ biến là cực đại nếu nó không là tập con của bất kỳ tập phổ biến nào
khác. Với khái niệm và các tính chất nêu trên của tập phổ biến, ng−ời ta đ−a ra khái
niệm luật kết hợp nh− sau đây.
Định nghĩa 2.2 (Luật kết hợp)
Một luật kết hợp là một biểu thức R: X → Y, với X và Y là các tập thuộc
tính không giao nhau X ∩ Y = ∅ và Y ≠ ∅.
Định nghĩa 2.3 (Độ hỗ trợ và độ tin cậy của luật)
Đỗ hỗ trợ của luật là xác suất của một giao dịch chứa cả X và Y: σ(X∪Y).
Độ tin cậy của một luật là xác suất có điều kiện để một giao dịch chứa Y,
nếu nó đã chứa X, và đ−ợc tính bởi:
-34-
( ) ( ) ( )( )
( )
( )X
YX
TXp
TXTYp
TXTYpR σ
σα ∪=⊆
⊆∧⊆=⊆⊆= |
Độ hỗ trợ của một luật là tần suất nó có thể xảy ra, trong khi độ tin cậy của
luật cho biết luật đó đáng tin ra sao. Một luật là thích hợp nếu nó có đủ độ hỗ trợ và
độ tin cậy: σ(R) ≥ smin (luật phổ biến) và α(R) ≥ cmin (luật mạnh), điều này chỉ xảy ra
nếu cả vế trái và vế phải của luật đó là các tập phổ biến.
Phát hiện luật kết hợp liên quan tới việc tìm ra tất cả các luật kết hợp trong cơ
sở dữ liệu có độ hỗ trợ > smin và có độ tin cậy > cmin (các luật phổ biến và mạnh).
Công việc này gồm hai b−ớc:
1. Tìm tất cả các tập thuộc tính phổ biến có độ hỗ trợ tối thiểu. Không gian tìm
kiếm để liệt kê tất cả các tập thuộc tính phổ biến là 2m, với m là số thuộc tính.
Tuy nhiên, nếu ta giả sử chiều dài giao dịch là có giới hạn, thì có thể chỉ ra
rằng phát hiện luật kết hợp về cơ bản là tuyến tính với kích th−ớc của cơ sở
dữ liệu.
2. Tạo các luật mạnh có độ tin cậy tối thiểu từ các tập thuộc tính phổ biến. Ta
tạo và thử độ tin cậy của tất cả các luật có dạng X\Y → Y, với Y ⊂ X và X phổ
biến. Vì ta phải xét mỗi tập con của X nh− là vế phải của luật, độ phức tạp của
b−ớc tạo luật là O(r.2l), với r là số tập thuộc tính phổ biến, l là kích th−ớc của
tập phổ biến lớn nhất.
Các tính chất của luật kết hợp:
- Không có phép hợp các luật: Nếu X → Z và Y → Z, không có nghĩa là X ∪ Y
→ Z. Xét tr−ờng hợp X ∩ Y = ∅, một giao dịch trong D hỗ trợ Z khi và chỉ
khi nó hỗ trợ hay X, hay Y. Độ hỗ trợ của X ∪ Y là bằng 0, và do đó độ tin
cậy của X ∪ Y → Z là bằng 0%.
-35-
- Phép tách các luật: Nếu X ∪ Y → Z thích hợp, các luật X → Z và Y → Z có
thể không thích hợp. Ví dụ trong tr−ờng hợp Z chỉ xuất hiện khi cả X và Y
xuất hiện, tức là σ(X∪Y) = σ(Z), nếu X và Y có độ hỗ trợ khá lớn so với X∪Y
thì hai luật tạo thành sẽ không có đủ độ tin cậy. Tr−ờng hợp ng−ợc lại: X →
Y∪Z ⇒ X → Y ∧ X → Z lại đúng, bởi σ(XY) ≥ σ(XYZ) và σ(XZ) ≥ σ(XYZ), do
đó độ hỗ trợ và độ tin cậy của luật nhỏ hơn đều tăng so với luật ban đầu.
- Không có tính chất bắc cầu: Nếu X → Y và Y → Z, ta không thể suy ra X →
Z. Ví dụ trong tr−ờng hợp T(X) ⊂ T(Y) ⊂ T(Z), với T(X) là tập các giao dịch
hỗ trợ X, ... và độ tin cậy tối thiểu là cmin. Giả sử α(X → Y) = α(Y → Z) = cmin,
dựa trên các giá trị độ hỗ trợ t−ơng đối ta có α(X → Z) = c2min < cmin (vì cmin <
1), nh− thế X → Z không có đủ độ tin cậy và do đó không thích hợp.
II.1.2. Một số công nghệ phát hiện luật kết hợp tuần tự [16]
Không gian tìm kiếm luật kết hợp tuần tự có thể đ−ợc thiết đặt theo những
cách d−ới đây [17].
Tìm kiếm từ d−ới lên/ Tìm kiếm lai
Trong phát hiện luật kết hợp có sử dụng quan hệ tập con ⊆ định nghĩa một
thứ tự bộ phận trên tập các itemset. Quan hệ này là đơn điệu so với độ hỗ trợ σ(X).
Thuật toán phát hiện luật kết hợp khác với cách tìm kiếm trong mạng các itemset
kết nối bởi quan hệ tập con. Hầu hết các tiếp cận sử dụng cách tìm kiếm theo mức
hay tìm-từ-d−ới-lên trong mạng để liệt kê các itemset phổ biến. Nếu đoán là có
itemset dài, cách tiếp c
Download miễn phí Luận văn Luật kết hợp theo tiếp cận lý thuyết tập thô và khai phá dữ liệu song song
mục lục
Nội dung Trang
Phần mở đầu 3
Chương 1. tổng quan về khai phá dữ liệu và khai phá dữ liệu song song8
1.1. Khai phá dữ liệu và phát hiện tri thức trong Cơ sở dữ liệu 8
1.1.1. Sơ bộ về khai phá dữ liệu và phát hiện tri thức trong cơ sở dữ liệu 8
1.1.2. Nội dung của khai phá dữ liệu 11
1.1.3. Các phương pháp khai phá dữ liệu phổ biến và lựa chọn phương pháp 13
1.1.4. Ưu thế của khai phá dữ liệu 15
1.1.5. Một số thách thức trong ứng dụng và nghiên cứu kỹ thuật khai phá dữ liệu 17
1.2. Khai phá dữ liệu song song 20
1.2.1. Các hệ thống tính toán song song 21
1.2.2. Các chiến lược khai phá dữ liệu song song 26
1.2.3. Các mô hình chi phí 28
Kết luận chương 1 31
Chương 2. Luật kết hợp theo cách tiếp cận của lý thuyết tập thô 32
2.1. Khái niệm luật kết hợp và một số công nghệ phát hiện 32
2.1.1. Luật kết hợp 32
2.1.2. Một số công nghệ phát hiện luật kết hợp tuần tự 35
2.2. Luật kết hợp theo cách tiếp cận của lý thuyết tập thô 40
2.2.1. Tập thô 40
2.1.2. Luật kết hợp theo cách tiếp cận lý thuyết tập thô 42
Kết luận chương 2 51
Chương 3. Phát hiện song song luật kết hợp 52
3.1. Không gian thiết kế song song 52
3.1.1. Nền phần cứng 52
3.1.2. Mô hình song song hóa 53
3.1.3. Cách thức cân bằng tải 54
3.2. Một số mô hình phát hiện song song luật kết hợp 55
3.2.1. Các hệ phân tán bộ nhớ 55
3.2.2. Các hệ chia sẻ bộ nhớ 65
3.2.3. Các hệ phân cấp 67
3.3. Mô hình tập thô phát hiện song song luật kết hợp 70
3.3.1. Thuật toán cho mô hình tập trung 72
3.3.2. Thuật toán cho mô hình phân tán 73
Kết luận chương 3 74
Phần kết luận 75
Tài liệu tham khảo
Để tải bản DOC Đầy Đủ xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung:
hiện khai phá dữ liệu trên các hệ thống với dữ liệu lớn, trên các hệthống phân tán, việc nghiên cứu và đề xuất các thuật toán khai phá dữ liệu song
song trong các mô hình song song là rất có ý nghĩa. Tùy thuộc vào cơ sở dữ liệu
thực tế, việc lựa chọn cách thức song song để song song hóa thuật toán khai phá dữ
liệu tuần tự là rất quan trọng (mục 1.2.2), nó ảnh h−ởng trực tiếp tới giá thành thực
hiện việc khai phá dữ liệu. Một số mô hình chi phí hình thức cho khai phá dữ liệu
song song đã đ−ợc tổng kết (mục 1.2.3).
-32-
Ch−ơng II. Luật kết hợp theo tiếp cận lý
thuyết tập thô
II.1. khái niệm Luật kết hợp và một số công nghệ phát hiện
II.1.1. Luật kết hợp
Phát hiện luật kết hợp là sự khai phá dữ liệu không đ−ợc định h−ớng hay
không có giám sát trên dữ liệu có độ dài thay đổi, nó cho ra các kết quả rõ ràng và
dễ hiểu. Mục đích của khai phá luật kết hợp là tìm tất cả các tập con các đối t−ợng
hay thuộc tính xuất hiện th−ờng xuyên trong nhiều giao dịch hay bản ghi trong cơ
sở dữ liệu, thêm vào đó là rút ra các luật về một tập con đối t−ợng có ảnh h−ớng tới
sự xuất hiện của tập con các đối t−ợng khác nh− thế nào [15].
Mặc dù phát hiện luật kết hợp có cách đặt bài toán đơn giản, nó đòi hỏi l−ợng
tính toán và truy xuất dữ liệu rất lớn. Khi dữ liệu tăng lên cả về số h−ớng (số các
thuộc tính) và kích th−ớc (số giao dịch), một trong những tính chất cần thiết của
phát hiện luật kết hợp là khả năng mở rộng đ−ợc: khả năng xử lý kho dữ liệu rất lớn.
Các thuật toán tuần tự không thể cho khả năng này trong các cơ sở dữ liệu lớn. Vì
vậy ta phải dựa vào tính toán song song và phân tán hiệu suất cao.
Tập phổ biến là cơ sở để tạo các luật kết hợp [4]. Chúng ta xem xét một ví dụ
khai phá luật kết hợp. Cho một tập các thuộc tính I = {I1, I2,..., Im}, một giao dịch T
đ−ợc định nghĩa là một tập con bất kỳ các thuộc tính trong I. Giả sử cơ sở dữ liệu D
là một tập n giao dịch, mỗi giao dịch đ−ợc gán một định danh giao dịch duy nhất
TID. Giao dịch T là hỗ trợ một tập X ⊆ I nếu nó chứa tất cả các thuộc tính trong X,
tức là X ⊆ T. Độ hỗ trợ của một tập thuộc tính X, ký hiệu σ(X), là tỉ lệ của tất cả các
giao dịch trong D hỗ trợ X.
-33-
Định nghĩa 2.1 (Tập phổ biến)
Tập X ⊆ I đ−ợc gọi là tập phổ biến nếu có σ(X) ≥ smin với smin là độ hỗ trợ
tối thiểu cho tr−ớc.
Một tập X có lực l−ợng k = |X| đ−ợc gọi là k-itemset. Có ba tính chất quan
trọng của các tập phổ biến, đó là:
- Nếu A ⊆ B với A, B là các tập thuộc tính thì σ(A) > σ(B), bởi tất cả các giao
dịch trong D hỗ trợ B thì đều phải hỗ trợ A.
- Tập cha của một tập không phổ biến là tập không phổ biến: Nếu tập thuộc
tính A không đủ độ hỗ trợ, tức là σ(A) ≤ smin thì mọi tập B chứa A cũng sẽ
không phổ biến, bởi vì σ(B) ≤ σ(A) ≤ smin.
- Tập con của tập phổ biến là tập phổ biến: Nếu tập thuộc tính B là phổ biến
trong D, tức là σ(B) ≥ smin, thì mọi tập con A của B cũng sẽ là phổ biến, bởi
σ(A) ≥ σ(B) ≥ smin.
Một tập phổ biến là cực đại nếu nó không là tập con của bất kỳ tập phổ biến nào
khác. Với khái niệm và các tính chất nêu trên của tập phổ biến, ng−ời ta đ−a ra khái
niệm luật kết hợp nh− sau đây.
Định nghĩa 2.2 (Luật kết hợp)
Một luật kết hợp là một biểu thức R: X → Y, với X và Y là các tập thuộc
tính không giao nhau X ∩ Y = ∅ và Y ≠ ∅.
Định nghĩa 2.3 (Độ hỗ trợ và độ tin cậy của luật)
Đỗ hỗ trợ của luật là xác suất của một giao dịch chứa cả X và Y: σ(X∪Y).
Độ tin cậy của một luật là xác suất có điều kiện để một giao dịch chứa Y,
nếu nó đã chứa X, và đ−ợc tính bởi:
-34-
( ) ( ) ( )( )
( )
( )X
YX
TXp
TXTYp
TXTYpR σ
σα ∪=⊆
⊆∧⊆=⊆⊆= |
Độ hỗ trợ của một luật là tần suất nó có thể xảy ra, trong khi độ tin cậy của
luật cho biết luật đó đáng tin ra sao. Một luật là thích hợp nếu nó có đủ độ hỗ trợ và
độ tin cậy: σ(R) ≥ smin (luật phổ biến) và α(R) ≥ cmin (luật mạnh), điều này chỉ xảy ra
nếu cả vế trái và vế phải của luật đó là các tập phổ biến.
Phát hiện luật kết hợp liên quan tới việc tìm ra tất cả các luật kết hợp trong cơ
sở dữ liệu có độ hỗ trợ > smin và có độ tin cậy > cmin (các luật phổ biến và mạnh).
Công việc này gồm hai b−ớc:
1. Tìm tất cả các tập thuộc tính phổ biến có độ hỗ trợ tối thiểu. Không gian tìm
kiếm để liệt kê tất cả các tập thuộc tính phổ biến là 2m, với m là số thuộc tính.
Tuy nhiên, nếu ta giả sử chiều dài giao dịch là có giới hạn, thì có thể chỉ ra
rằng phát hiện luật kết hợp về cơ bản là tuyến tính với kích th−ớc của cơ sở
dữ liệu.
2. Tạo các luật mạnh có độ tin cậy tối thiểu từ các tập thuộc tính phổ biến. Ta
tạo và thử độ tin cậy của tất cả các luật có dạng X\Y → Y, với Y ⊂ X và X phổ
biến. Vì ta phải xét mỗi tập con của X nh− là vế phải của luật, độ phức tạp của
b−ớc tạo luật là O(r.2l), với r là số tập thuộc tính phổ biến, l là kích th−ớc của
tập phổ biến lớn nhất.
Các tính chất của luật kết hợp:
- Không có phép hợp các luật: Nếu X → Z và Y → Z, không có nghĩa là X ∪ Y
→ Z. Xét tr−ờng hợp X ∩ Y = ∅, một giao dịch trong D hỗ trợ Z khi và chỉ
khi nó hỗ trợ hay X, hay Y. Độ hỗ trợ của X ∪ Y là bằng 0, và do đó độ tin
cậy của X ∪ Y → Z là bằng 0%.
-35-
- Phép tách các luật: Nếu X ∪ Y → Z thích hợp, các luật X → Z và Y → Z có
thể không thích hợp. Ví dụ trong tr−ờng hợp Z chỉ xuất hiện khi cả X và Y
xuất hiện, tức là σ(X∪Y) = σ(Z), nếu X và Y có độ hỗ trợ khá lớn so với X∪Y
thì hai luật tạo thành sẽ không có đủ độ tin cậy. Tr−ờng hợp ng−ợc lại: X →
Y∪Z ⇒ X → Y ∧ X → Z lại đúng, bởi σ(XY) ≥ σ(XYZ) và σ(XZ) ≥ σ(XYZ), do
đó độ hỗ trợ và độ tin cậy của luật nhỏ hơn đều tăng so với luật ban đầu.
- Không có tính chất bắc cầu: Nếu X → Y và Y → Z, ta không thể suy ra X →
Z. Ví dụ trong tr−ờng hợp T(X) ⊂ T(Y) ⊂ T(Z), với T(X) là tập các giao dịch
hỗ trợ X, ... và độ tin cậy tối thiểu là cmin. Giả sử α(X → Y) = α(Y → Z) = cmin,
dựa trên các giá trị độ hỗ trợ t−ơng đối ta có α(X → Z) = c2min < cmin (vì cmin <
1), nh− thế X → Z không có đủ độ tin cậy và do đó không thích hợp.
II.1.2. Một số công nghệ phát hiện luật kết hợp tuần tự [16]
Không gian tìm kiếm luật kết hợp tuần tự có thể đ−ợc thiết đặt theo những
cách d−ới đây [17].
Tìm kiếm từ d−ới lên/ Tìm kiếm lai
Trong phát hiện luật kết hợp có sử dụng quan hệ tập con ⊆ định nghĩa một
thứ tự bộ phận trên tập các itemset. Quan hệ này là đơn điệu so với độ hỗ trợ σ(X).
Thuật toán phát hiện luật kết hợp khác với cách tìm kiếm trong mạng các itemset
kết nối bởi quan hệ tập con. Hầu hết các tiếp cận sử dụng cách tìm kiếm theo mức
hay tìm-từ-d−ới-lên trong mạng để liệt kê các itemset phổ biến. Nếu đoán là có
itemset dài, cách tiếp c
