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 thi hiệu quả ở các giai đoạn đầu, thuật toán Apriori -TID thực thi hiệu quả ở các giai đoạn sau. Phương pháp của thuật toán Apriori -Hybrid là sử dụng thuật toán Apriori ở các giai đoạn đầu và chuyển sang sử dụng thuật toán Apriori-TID ở các giai đoạn sau, được trình bày chi tiết trong [21]. § Thuật toán AIS (Agrawal Imielinski Swami) Trong thuật toán AIS, tập các mục ứng cử được sinh ra và được tính khi quét toàn bộ CSDL. Với mỗi giao dịch t, thuật toán chọn các tập mục phổ biến nào đã được phát hiện ở giai đo ạn trước có chứa trong giao dịch t. Các tập mục ứng cử mới được sinh ra bằng việc mở rộng các tập phổ biến này với các mục khác trong giao dịch t [ 18, 21]. § Thuật toán DIC (Dynamic Itemset Counting) Thuật toán DIC bắt đầu tính độ hỗ trợ cho các k-itemset sau khi quét ((k - 1) * M) giao dịch, M < D và dừng việc t ính sau khi các k-itemset này được thấy trong tất cả các giao dịch. Thuật toán Apriori là trường hợp đặc biệt của thuật toán DIC, ứng với M = D. Vì vậy, thuật toán DIC thực hiện tốt hơn thuật toán Apriori nếu M được chọn thích hợp [18, 21]. § Thuật toán OCD (Of-line Candidate Determination) Kỹ thuật OCD được giới thiệu bởi Mannila vào năm 1994, dựa vào ý tưởng “các mẫu có kích thước nhỏ thường là khá tốt cho việc tìm kiếm các tập mục phổ biến”. Kỹ thuật này sử dụng các kết quả của phép phân tích tổ hợp thông tin thu được ở các giai đoạn trước , để lo ại bỏ đi các tập mục ứng cử không cần thiết. Nếu một tập Y ⊆ I là một tập không phổ biến thì cần quét ít nhất (1 - s) giao dịch trong CSDL, s là ngưỡng hỗ trợ. Vì vậy, đối với những giá trị ngưỡng hỗ trợ s nhỏ thì hầu như toàn bộ các giao dịch phải được quét. Thuật toán OCD sinh ra một tập tất cả các k-itemset phổ biến Lk [18, 20]. § Thuật toán phân hoạch [21] Thu ật toán này chia CSDL thành các phân hoạch nhỏ, mỗi phân hoạch có thể được lưu trữ trên bộ nhớ chính. Cho các phân hoạch của CSDL D là D1, D2, …, Dp. Lần quét đầu tiên, thuật toán tìm các tập mục phổ biến trong mỗi phân hoạch Di (1 ≤ i ≤ p) gọi là tập mục phổ biến cục bộ. Mỗi tập mục phổ biến cục b ộ Li có thể được tìm thấy bằng cách sử dụng thuật toán Apriori. Lần quét thứ nhì, thuật toán này sử dụng tính chất, tập mục phổ thỏa trên CSDL toàn cục phải là tập mục phổ biến cục bộ trong ít nhất một phân hoạch của CSDL nào đó. Sau đó, ta hợp các tập mục phổ biến cục bộ được tìm thấy trong mỗi phân hoạch để tạo ra các tập mục ứng cử và thực hiện tính độ hỗ trợ tổng thể trên CSDL D, để tìm tất cả các tập mục phổ biến. Thuật toán này thực thi tốt trên máy tính song song. Thuật toán Apriori thực hiện tốt hơn thuật toán phân hoạch chỉ khi nào ngưỡng hỗ trợ có giá trị cao. 2.3.2 Sinh luật kết hợp Để sinh các luật, với mỗi tập mục phổ biến l , ta tìm tất cả các tập con khác rỗng của l . Với mỗi tập a ⊂ l tìm được, ta sinh ra luật a ⇒ ( l - a) nếu tỷ số sup(l) sup(a)  ≥ mincorf. Thủ tục sinh ra các tập mục con của một tập mục phổ biến là thủ tục để quy, được mô tả như sau: Với tập mục phổ biến {A, B, C, D}, đầu tiên ta chọn tập con là {A, B, C}, rồi sau đó chọn tập con là {A, B} … Khi đó, nếu ∃ a ⊂ l và luật a ⇒ ( l - a) có độ tin cậy nhỏ hơn minconf thì ta không cần phải xem xét các luật có tiền đề là a’, ∀ a’ ⊆ a. Chẳng hạn, nế u ABC ⇒ D Có độ tin cậy nhỏ hơn minconf thì ta không cần phải kiểm tra luật AB ⇒ CD vì AB ⊂ ABC nên sup(AB) ≥ sup(ABC) và do đó  sup( ABCD) ≤ sup( ABCD) < minconf. sup( ABC) sup( AB) 2.3.2.1 Thuật toán sinh luật đơn giản Vào: Tập các tập mục phổ biến Lk Ra: Tập luật Phương thức: forall tập mục phổ biến lk ∈ Lk, k ≥ 2 do call genrules(lk, lk); procedure gsnrules(lk: k-itemset phổ biến; am: m-itemset phổ biến); A = {(m - 1)-itemset am-1am-1 ⊂ am}; forall am-1 ∈ A do begin conf = sup(lk)/sup(am-1); if (conf ≥ minconf) then begin xuất ra luật am-1 ⇒ (lk – am-1); if ((m - 1) > 1) then call genrules(lk, am - 1); 0 // sinh ra các luật có tiền đề là tập con của am-1 end end 2.3.2.2 Thuật toán sinh luật nhanh Như đã đề cập ở trên với mỗi tập mục phổ biến l , nếu luật a ⇒ ( l – a) không thỏa minconf thì ∀a’ ⊆ a, luật a’ ⇒ ( l – a’) cũng không thỏa. Ngược lại, nếu luật ( l – c) ⇒ c thỏa minconf thì t ất cả các luật (l – c’) ⇒ c’ cũng thỏa minconf, với ∀c’ ⊆ c. Bởi vì ( l – c) ⊆ ( l – c’) (do c’⊆ c), suy ra sup( l – c) ≥ sup( l – c’) và minconf ≤ sup(l) sup(l) , do đó lu ật (l – c’)⇒ c’ cũng thỏa minconf. sup(l − c) ≤ sup(l − c') Như vậy, từ một tập mục phổ biến l , trước hết, ta sinh tất cả các luật với 1-itemset trong mệnh đề kết quả. Sau đó, sử dụng các mệ nh đề kết quả và hàm apriori_gen() để sinh các mệnh đề kết quả có thể của luật bao gồm 2-item, 3-item... [22] 2.4. Khai phá luật kết hợp với một số khái niệm mở rộng 2.4.1. Giới thiệu Một số khai niệm mở rộng của các luật kết hợp đó là: Luật kết hợp định lượng, Luật kết hợp tổng quát, Luật kết hợp trọng số... Việc khai phá luật kết hợp dựa trên các khái nệim mở rộng này cho phép người ta phát hiện được nhiều luật kết hợp mà các thuật toán khai phá luật kết hợp cơ sở không tìm thấy được. Ví dụ, với luật kết hợp định lượng cho phép người ta phát biểu một luật có dạng như sau “Nếu các khách hàng mua ít nhất 3 mặt hàng A thì cũng mua từ 5 đến 10 mặt hàng B“. 2.4.2. Khai phá luật kết hợp trọng số 4.2.2.1. Luật kết hợp trọng số nhị phân Định nghĩa 2.5: Trọng số của một tập mục w(0 ≤ w ≤ 1) biểu thị cho mức độ quan trọng của tập mục đó. Chẳng hạn: Nếu tập mục X có trọng số w = 0.95 thì ta nói rằng nó quan trọng hơn khi X có trọng số là w = 0.10 trên cùng cơ sở dữ liệu giao dịch D. Định nghĩa 2.6: Luật kết hợp trọng số nhị phân (Binary weighted Association Rule): Là luật có dạng X ⇒ Y với tập các mục I = {i1, i2, ..., in} trên cơ sở dữ liệu giao dịch D, X ⊂ I, Y⊂ I và X ∩ Y = ∅. Định nghĩa 2.7: Độ hỗ trợ trọng số (không chuẩn hóa) của luật kết hợp trọng số nhị phân X ⇒ Y được định nghĩa. w sup port ( X  ⇒ Y ) =     ∑ w j  * sup(X ∪ Y )  (2.4)  i j ∈( X ∪Y )  Trong đó, {w1, w2, …, wn} là trọng số tương ứng của các mục {i1, i2, ..., in}. Tương tự như trong luật kết hợp Boolean, việc tìm các luật kết hợp đáng quan tâm dựa vào hai ngưỡng cho trước: độ hỗ trợ trọng số tối thiểu ( wminsup) và độ tin cậy trọng số tối thiểu (minconf) [8]. Định nghĩa 2.8: Một k-itemset X được gọi là tập mục trọng số không phổ biến nếu độ hỗ trợ trọng số của X nhỏ hơn độ hỗ trợ trọng số tối thiểu hay      ∑ w j  * sup(X ) < w min sup . Ngược lại X là tập mục phổ biến [8].  i j ∈X  Định nghĩa 2.9: Một luật kết hợp trọng số nhị phân X ⇒ Y được gọi là luật đáng quan tâm nếu độ tin cậy của luật X ⇒ Y lớn hơn hoặc bằng độ tin cậy trọng số tối thiểu và tập mục ( X ∪ Y) là tập mục trọng số phổ biến. TID Giao dịch 1 1 2 4 5 2 1 4 5 3 2 4 5 4 1 2 4 5 5 1 3 5 6 2 4 5 7 2 3 4 5 Ví dụ: Cho dữ liệu giao dịch D như sau: Mã vạch Items Tổng lợi nhuận Các trọng số 1 Nho 100 0.1 2 Cam 300 0.3 3 Sữa 400 0.4 4 Đường 800 0.8 5 Thịt 900 0.9 Bảng 2.1.a. Thông tin của một cửa hàng bán lẻ Bảng 2.1.b. Tập giao dịch D của cửa hàng Khi đó, nếu wminsup = 0.4 thì tập mục {2, 5} sẽ là tập mục trọng số phổ biến vì (0.3 + 0.9)* 5/7 = 0.86 > 0.4. Tương tự, các tập mục {4, 5}, {2, 4, 5}, cũng là các tập mục trọng số phổ biến. Khái niệm biên k-support (k-support bound) Hàm apriori_gen() được kế thừa trong khai phá luật kết hợp trọng số. Tuy nhiên, ý nghĩa cả độ hỗ trợ trong trường hợp này bị thay đổi. Với độ hỗ trợ trọng số được định nghĩa như trên thì tính chất 2.3 có thể không được bảo toàn, nghĩa là nếu một tập mục X là một tập mục trọng số phổ biến thì các tập con của X chưa hẳn đã là các tập mục trọng số phổ biến. Giả sử X1, X2, …, Xn là n tập con của X, khi đó ta có: wsuppprt(X) > min(wsupport(X1),…, wsupport(Xn)) (2.5) Cho một CSDL giao dịch với các giao dịch T, số đếm hỗ trợ (gọi tắt là số đếm) của tập mục X, ký hiệu SC(X) là ốs các giao dịch chứa X và thỏa mãn điều kiện sau nếu X là một tập mục phổ biến: SC ( X ) = min sup* T ∑ w j i j∈X  (2.6) Bổ đề 2.1. Gọi I là tập tất cả các mục. Giả sử Y là một q-itemset, q< k. Trong tập các mục còn lại (I-Y), đặt các mục này với (k-q) các trọng số lớn nhất là ir1, ir2,…, irk-p. Khi đó, trọng số tối đa của bất kỳ k-itemset chứa Y là: W (Y , k ) = k −q j ∑ w j + ∑ wr  (2.7) i j ∈Y j =1 Trong đó ∑ w j i j∈Y k −q j là tổng các trọng số của q-itemset Y và ∑ wr j =1  là tổng của (k-q) các trọng số tối đa của các mục còn lại. Từ bất đẳng thức (2.6), số đếm tối thiểu của k-itemset phổ biến chứa Y cho bởi: B(Y , k ) =  w min sup* T   (2.8)    W (Y , k )  Ta gọi B(Y, k) là hàm xác định biên k-support của Y, ta sử dụng kí hiệu   để lấy cận trên của w min sup* T W (Y , k )  vì hàm B(Y, k) trả về giá trị nguyên [ 8]. Thuật toán khai phá luật kết hợp trọng số (không chuẩn hóa) Thuật toán khai phá luật kết hợp trọng số kế thừa thuật toán của hàm apriori_gen(). Do tính chất của trọng số của các tập mục nên trong một số bước có thể có sự khác biệt. Trước tiên, ta cũng sinh ra các tập mục trọng số phổ biến với kích thước tăng dần nhưng do các tập con của các tập mục phổ biến có thể không phải là các tập mục phổ biến nên ta không t hể sinh ra các k-itemset ứng cử một cách dễ dàng từ tập các (k-1)-itemset phổ biến như trong thuật toán Apriori. Chính vì vậy ta phải tìm cách lưu giữ các k -itemset mà chúng có thể sinh ra các j-itemset phổ biến (j ≤ k) trong các giai đoạn sau. Để trích chọ n các k-itemset từ CSDL, ta s ử dụng các giá trị biên j-support. Trong quá trình thực hiện, các biên j-support sẽ được tính toán cho tất cả các k -itemset ứng cử, j là một số bất kỳ giữa k và kích thước lớn nhất có thể của tập mục phổ biến. Nếu số đếm của k-itemset nào đó mà nhỏ hơn tất cả các biên j -support thì ta có thể nói rằng nó không thể là tập con của bất kỳ tập mục trọng số phổ biến nào trong giai đoạn tiếp theo. Vì thế, nó có thể được cắt tỉa đi, k-itemset nào có th ể sử dụng để tạo ra các tập mục trọng số phổ biến trong giai đoạn kế tiếp sẽ được lưu giữ vào Ck. Thuật toán khai phá luật kết hợp trọng số (nhị phân không chuẩn hóa) (MINVAL(O)) Các ký hiệu trong thuật toán: D: Cơ sở dữ liệu giao dịch; w: Tập các trọng số của các mục Lk: Tập các k-itemset phổ biến Ck: Tập các k-itemset trọng số ứng cử SC(X): Số lượng giao dịch chứa tập mục X wminsup: Ngưỡng hỗ trợ trọng số; minconf – Ngưỡng tin cậy size: Kích thư ớc tối đa của các tập mục trọng số phổ biến tiềm năng trong D. Nội dung thuật toán MINVAL(O) Vào: D, wminsup, minconf, wi (trọng số của các mục) đã được sắp xếp theo thứ tự tăng dần, tổng số các giao dịch và tổng số các mục. Ra: Một danh sách của các luật đáng quan tâm Thuật toán chính (wminsup, minconf, D, w) L = ö; for(i=1; i<= size; i++) do Ci = Li = ö; for(mỗi giao dịch) do (SC, C1, size) = Counting(D,w); k=1; while (|Ck|>= k) do begin k++; Ck = Join(Ck-1); Ck=Prune(Ck); (Ck, Lk)=Checking(Ck, D); L = L ∪ Lk; end; Rule(SC, L); end; Giải thích thuật toán (1) Ở giai đoạn 1, tất cả các tập mục ứng cử và kích thước tối đa của các tập mục trọng số phổ biến tiềm năng và số đếm hỗ trợ của các 1-itemset được sinh ra bởi thủ tục Counting(D, w) và được gán cho C1, size, SC(X). Hàm này được thực hiện bằng cách quét cơ sở dữ liệu D, cập nhật số đếm hỗ trợ của các mục và kiểm tra cận trên của size. Hơn nữa, biên k-support sẽ được tính toán trong giai đoạn này và đẩy các tập mục ứng cử vào C1. (2) Sinh các tập mục trọng số phổ biến và các tập mục trọng số ứng cử: i- Sinh ra Ck từ Ck-1 bởi thủ tục Join(Ck-1). Thủ tục này thực hiện nối hai (k-1)-itemset nào đó thuộc C k-1 với nhau để tạo thành một k-itemset rồi đẩy vào Ck (tương tự bước nối trong hàm apriori_gen()). ii- Một tập mục sẽ được cắt tỉa bởi hàm Prune(Ck) nếu nó thỏa mãn một trong các trường hợp sau: - Một tập con của tập mục ứng cử Ck không có mặt trong Ck-1. - Ước lượng một cận trên số đếm hỗ trợ (SC) của tập mục X (X đã được nối), đó là SC tối thiểu trong số k các (k-1)-subset khác nhau của X trong Ck-1. Nếu cận trên ước lượng SC chỉ ra tập mục X không phải là một tập con của bất kỳ một tập mục phổ biến nào trong giai đoạn kế tiếp (bằng việc tính toán các biên k-support cho tất cả các itemset) thì tập mục X sẽ được cắt tỉa. iii- Thủ tục tiếp theo sẽ quyết CSDL giao dịch, cập nhật số đếm của tất cả các tập mục ứng cử trong Ck. Sau đó, thực hiện việc cắt tỉa các tập mục ứng cử không thỏa mãn các biên SC của tất cả các tập mục trọng số phổ biến tiềm năng. Các tập mục ứng cử còn lại sẽ được lưu giữ vào Ck. Lúc này Lk sẽ được sinh ta từ Ck bằng cách kiểm tra độ hỗ trợ trọng số thực tế của các tập mục. Bước này được thực hiện bởi các thủ tục Checking(Ck, D) (3) Thủ tục Rule(SC, L) tìm tất cả các luật kết hợp từ các tập mục phổ biến L đã được tìm thấy ở trên với độ tin cậy tối thiểu minconft. 2.4.2.2. Khai phá luật kết hợp trọng số chuẩn hóa Định nghĩa 2.10: Một k-itemset X đư ợc gọi là một tập mục không phổ biến (small itemset) n ếu độ hỗ trợ trọng số chuẩn hóa của nó nhỏ hơwn minsup. Ngh ĩa là:  =1   ∑ w j   * sup port( X ) < w min sup  (2.9)  j  k  i ∈( X )  Định nghĩa 2.11: Độ hỗ trợ trọng số chuẩn hóa (Nomalized Weighted Support) của một luật X ⇒ Y được cho bởi biểu thức sau:  =1   ∑ w j   * sup port( X ∪ Y )  (2.10)  j  k  i ∈( X ∪Y )  Trong đó, k là kích thước của tập mục (X ∪ Y). Ngược lại, tập mục X sẽ được gọi là k-itemset trọng số phổ biến. Định nghĩa 2.12: Một luật kết hợp trọng số chuẩn hóa nhị phân X ⇒ Y được gọi là đáng quan tâm nếu độ tin cậy của luật X ⇒ Y lớn hơn hoặc bằng độ tin cậy tối thiểu (minconf) và (X ∪ Y) là m ột tập mục trọng số phổ biến (chuẩn hóa). Định nghĩa 2.13: Số đếm hỗ trợ tối thiểu của một k -itemset phổ biến chứa Y được gọi là biên k-support của tập mục Y với trọng số chuẩn hóa và được cho bởi:  B(Y , k ) = k *   w min sup   W (Y , k )  * T  (2.11) Cách tiếp cận khác cho trường hợp trọng số chuẩn hóa Ta thiết lập một thuật toán trong đó việc sinh ra các tập mục trọng số phổ biến tương tự như trong hàm appriori_gen() cũng như việc cắt tỉa các tập mục ứng cử trong mỗi giai đoạn. Tuy nhiên, tính chất “Tập con của một tập mục phổ biến là một tập mục phổ biến” sẽ không còn đúng trong trường hợp trọng số chuẩn hóa. Định nghĩa 2.14: Tập cha bật thấp ( low-order superset): Cho một tập mục X = {x1, x2, xn}, đặt trọng số nhỏ nhất của các mục là w i. Một tập mục Y = X ∪ Z, Z có các trọng số đều nhỏ hơn wi. Thì Y được gọi là một tập cha bậc thấp của X. Định nghĩa 2.15: Tập con bật cao ( high-order subset): Một tập mục Y⊂ X trong đó, mỗi tập mục của Y đều có trọng số lớn hơn hoặc bằng trọng số mỗi mục trong (X – Y), được gọi là một tập con bậc cao của X. Bổ đề 2.2: Nếu một tập mục Y là phổ biến thì bất kỳ tập con bật cao nào của Y cũng phải là tập mục phổ biến. Chứng minh: Cho X là một tập con bật cao của Y. Trọng số trung bình của X là lớn hơn hoặc bằng trọng số trung bình của Y. Độ hỗ trợ của X lớn hơn hoặc bằng độ hỗ trợ của Y. Do đó, độ hỗ trợ trọng số của X sẽ lớn hơn hoặc bằng độ hỗ trợ trọng số của Y. Vậy nếu Y là tập mục phổ biến thì X cũng là tập mục phổ biến. Bổ đề 2.3: Một (k+1)-itemset X phổ biến phải là một tập cha bật thấp của một số k-itemset phổ biến Y. Chứng minh: Nếu X là tập mục phổ biến, thì từ bổ đề 2.2, bất kỳ tập con bật cao nào của X cũng phải là một tập mục phổ biến. Gọi x là một mục thuộc X với trọng số thấp nhất. Khi đó Y = X – x là một tập con bật cao của X và l à tập phổ biến. Vậy, X là một tập cha bật thấp của Y. Thuật toán khai phá luật kết hợp trọng số chuẩn hóa (MINVAL(W)) Ký hiệu trong thuật toán: D: Cơ sở dữ liệu giao dịch; w: Tập các trọng số của các mục Lk: Tập các k-itemset phổ biến Ck: Tập các k-itemset trọng số ứng cử SC(X): Số lượng giao dịch chứa tập mục X wminsup: Ngưỡng hỗ trợ trọng số chuẩn hóa Ck: Tập các i-temset ứng cử. Nội dung thuật toán MINVAL(W) Vào: D, wminsup, minconf, wi (trọng số của các mục) được sắp xếp theo thứ tự tăng dần, tổng số giao dịch và tổng số các mục. Ra: Một danh sách của các luật trọng số chuẩn hóa đáng quan tâm. Thuật toán chính (wminsup, minconf, D, w) L = ö; for (i=1; i<= size; i++) Ci = Li = ö; for (mỗi giao dịch) do (SC, C1, size)=counting(D, w); k=1; while(Ck ≠ö) do begin k++; Ck = Join(Ck-1); Ck=Prunce(Ck); (Lk)=Checking(Ck, D); L = L ∪ Lk; Giải thích end; Rule(SC, L) end; (1) Ở giai đoạn 1, thuật toán MINVAL(W) giống như trong thuật toán MINVAL(O) với thủ tục Counting(D, w). (2) Các t ập mục trọng s ố phổ biến và tập mục ứng cử được sinh ra như sau: - Các thủ tục Join, Prune và Checking sinh ra Lk và Ck. Công việc chính của bước Join(Lk-1) là sinh ra Ck. Theo bổ đề 2.3, một itemset ứng cử phải là một tập cha bật thấp của một số (k-1)-itemset phổ biến. Trong bước này, ta nối các tập mục trọng số phổ biến trong Lk-1 với một trong các tập mục có trọng số thấp hơn để có tạo ra một tập cha bật thấp. - Khi thực hiện thủ tục Prune, một k-itemset X ửng cử sẽ được cắt tỉa nếu tất cả các biên j-support của X (j ≤ k) đều lớn hơn số đếm hỗ trợ nhỏ nhất trong số các (k-1)-subset của X, đó là một ước lượng và là một cận trên số đếm hỗ trợ của k-itemset X. Sự khác nhau giữa phương pháp tỉa này và phương pháp tỉa trong hàm apriori_gen() ở chỗ, phương pháp này không cần phải kiểm tra các tập con của các tập mục phổ biến thay vào đó nó sử dụng các giá trị biên support. - Thủ tục Ch eck ing sẽ th ực h iện tương tự như MINVAL(O), chỉ có sự khác biệt, các tâp mục ứng cử còn lại sẽ là tập các tập mục phổ biến Lk và giai đoạn kế tiếp sẽ dựa vào Lk để sinh ra các tập ứng cử. (3) Thủ tục Rule(SC, L) thực hiện sinh các luật từ các tập mục trọng số phổ biến tương tự như trong thuật toán MINVAL(O). 2.4.2.3 Khai phá luật kết hợp trọng số với phương pháp lấy mẫu Trong 2 thuật toán trê n, thời gian xử lý sẽ rất lớn nếu số lượng giao dịch cần xử lý quá lớn (do cần phải quét toàn bộ CSDL). Sử dụng phương pháp lấy mẫu để khắc phục điều này. Kỹ thuật lấy mẫu Kỹ thuật lấy mẫu ở đây là kỹ thuật lấy mẫu ngẫu nhiên được sử dụng trong các bài toán xác suất thống kê. Kỹ thuật ngẫu nhiên đơn giản SRS (Simple Random Sampling) là kỹ thuật chọn ngẫu nhiên n đ ơn vị từ N đơn vị. Mỗi cách C N lấy mẫu là một trong n  cách, do đó xác suất của việc là  1 . Vấn đề chính là C n N của kỹ thuật SRS là phải tính toán kích thước mẫu sao cho độ chính xác của mẫu là đảm bảo. Để tính toán số lượng mẫu cần thiết, ta sẽ bắt đầu từ độ hỗ trợ của các tập mục. Gọi y là số lần xuất hiện của tập mục X trong cơ sở dữ liệu D, N là tổng số giao dịch. Xác suất chọn lựa giao dịch chứa X sẽ là: Px = y /N (2.12) Nói cách khác, xác suất chọn giao dịch chứa X sẽ là: p = y /N (2.13) Gọi n là số mẫu cần lấy. Khi kích thước phải đủ lớn, giả sử xác suất lựa chọn giao dịch là p, nghĩa là, p là một hằng đối với mỗi lần chọn. Điều này nói lên rằng xác xuất mà một mẫu chứa m lần xuất hiện của tập X sẽ là: r m P ( y = m) = C n p m (1 − p) n−m (2.14) Từ trên, với ước lượng pˆ = với pˆ trung bình và có độ lệch là : m , giả sử rằng pˆ được phân phối chuẩn n N − n N − 1 p(1 − p) n  (2.15) Với kỹ thuật lấy mẫu ngẫu nhiên đơn giản, ta chọn một số dư sai số (margin of error) d theo xác xấut ước lượng pˆ và hệ số rủi ro (risk factor) á thỏa mãn : Pr(| pˆ - p|) ≥ d)= á (2.16) Giá trị d biểu thị biên lỗi, còn á biểu thị xác xuất ước lượng vượt qua ngoài biên d. Do sự phân phối chuẩn của pˆ , ta có: d = Z á 2 N − n N − 1 p(1 − p) n  (2.17) Ở đây, Zá/2 là một giá trị sao cho tích phân của mật độ chuẩn từ Z á/2 đến ∞ bằng á/2. Do đó: n = n0 1 + n0 N z 2 p(1 − p) á / 2 n 0 d 2  (2.18) Trong công thức tính toán n trên, có tham 3 số chưa biết là d, á và p. Giá trị cực đại của n0 tìm được khi p =1/2. Do đó, ta có tểh ấn định p =1/2 để tính cho n, nghĩa là:     z 2  1   N .Z 2 n =  á / 2   = á / 2 (2.19)  4d 2  z 2  4d 2 N + Z 2   1 + á / 2  á / 2 Thuật toán chọn mẫu  4d 2 N  Ý tưởng: Khi th ực hiệnxử lý, trước hết chọn mẫu ngẫu nhiên từ CSDL với kích thư ớc n. Tiếp theo, sử dụng thuật toán MINVAL(O) hoặc MINVAL(W). Một số ký hiệu sử dụng trong thuật toán Z : giá trị của Zá/2 á : Hệ số rủi ro d : Biên lỗi n : Kích thước mẫu N : Tổng số giao dịch trong toàn bộ CSDL S : Tập các giao dịch sau khi lấy mẫu (từ CSDL của mẫu) Ti : Giao dịch thử i Vào: N, wminsup, minconf, d và á Ra: Một danh sách các luật đáng quan tâm với hệ số rủi ro á Thuật toán SRS 1) Thuật toán lấy mẫu (wminsup, minconf, D, w, á, d, n, N) 2) Z = Calculate(á); N .Z 2 3) n = ; 4d 2 N + Z 2 4) for(i = 1; I ≤ n; i ++) a[i] = GenRamdom(N); 5) Sort(a); 6) for each transaction Ti in D (i = 1..N) 7) if (i = a[i]) 8) S = S ∪ Ti 9) Execute(wminsup, minconf, S, w) Các thủ tục sử dụng trong thuật toán này: Calculate(() : Tính toán giá trị Zá/2 từ phân phối chuẩn GenRandom(N): Sinh số nguyên ngẫu nhiên trong khoản g [1, N] Sort(a) : Sắp xếp mảng a theo thứ tự tăng dần Execute(wminsup, minconf, S, w): Thực hiện một trong hai thuật toán MINVAL(O) hoặc MINVAL(W) trên tập mẫu các giao dịch S. 2.4.3 Khai phá luật kết hợp tổng quát Tập các mục I = {i1, i2, ..., in} trong các bài toán khai phá lu ật kết hợp cơ sở nêu trên đư ợc coi là bình đẳng với nhau. Tuy nhiên, trong thực tế, có nhiều trường hợp cần phải phân cấp cho các mục này. Ví dụ, I = {Áo vét, quần áo khoác, …}, người ta thư ờng nói Áo vét là một loại Quần áo khoác. Trong nh ững trường hợp như vậy, người ta bi ểu diễn các mục của tập Ithành m ột cây phâncấp. Sự phân cấp có thể được sử dụng để cắt tỉa những luật không đáng quan tâm hoặc không mang thêm một thông tin nào mới hơn so với các luật liên quan đến mức trên của nó. Gọi I = {i1, i2, .., in} là tập mục. G là một cây đồ thị có hướng trên các mục của I. Một cạnh trên G đi từ p → q mô tả một quan hệ, p được gọi là cha của q và q được gọi là con của p. Ta sử dụng những chữ cái viết thường để ký hiệu cho các mụ c, các chữ cái viết hoa để ký hiệu cho các tập mục. x) được gọi là một tổ tiên của x (x đ ược gọi là con ch áu của x) ) nếu có một cạnh đi từ x) đến x. Lưu ý rằng, một nút của G không được coi là tổ tiên của chính nó. Gọi D là cơ sở dữ liệu giao dịch, trong đó mỗi giao dịch T là một tập các mục, T ⊆ I. Ta nói rằng, giao dịch T hỗ trợ cho mục x ∈ I nếu x có mặt trong T hoặc x là một tổ tiên của một số mục trong T. Một giao dịch T hỗ trợ một tập X ⊆ I nếu T hỗ trợ cho mỗi mục trong X. Định nghĩa 2.15: Một luật kết hợp tổng quát là luật có dạng X ⇒ Y, trong đó X ⊂ I, Y ⊂ I, X ∩ Y = ∅ và không có mục nào trong Y là tổ tiên của một mục nào đó trong X. Luật X ⇒ Y tồn tại trên D với một độ tin cậy c và m ột độ hỗ trợ có ý nghĩa như định nghĩa 2.1, 2.2. Việc đưa vào thêm điều kiện không có một mục nào trong Y là tổ tiên của một mục nào đó trong X là để tránh trường hợp xuất hiện luật có dạng x ⇒ x) , luật này luôn luôn có độ tin cậy bằng 100%. Sở dĩ gọi luật X ⇒ Y là luật tổng quát vì cả X và Y có thể chứa các mục ở bất kỳ mức nào của cây phân cấp G. Bài toán khai phá luật kết hợp tổng quát thực chất cũng chỉ khai phá các luật mà độ hỗ trợ và độ tin cậy của nó lớn hơn hoặc bằng các ngưỡng minsup và minconf tương ứng. Gọi Pr(X) là xác suất mà tất cả các mục trong X được chứa trong một giao dịch. Khi đó: sup(X ⇒ Y) = Pr(X ∪ Y) (2.20) conf(X ⇒ Y) = Pr(Y \ X) (2.21) Nếu tập {x, y} có độ hỗ trợ tối thiểu thì các tập{x, y) }, { x) , y},{ x) , y) } cũng sẽ có độ hỗ trợ tối thiểu. Tuy nhiên, nếu luật x ⇒ y có độ hỗ trợ tối thiểu và có độ tin cậy tối thiểu thì chỉ có luật x ⇒ y) mới đảm bảo có cả độ hỗ trợ tối thiểu lẫn độ tin cậy, còn các luật x) ⇒ y, x) ⇒ y) chỉ có độ hỗ trợ tối thiểu nhưng chưa hẳn đã có độ tin cậy tối thiểu. Độ hỗ trợ của một mục trong cây phân cấp G là không bằng tổng các độ hỗ trợ của các mục con của chúng vì một số mục con có mặt trong một giao dịch đơn. Do đó, ta không tựr c tiếp suy ra các luật trên các mục ở mức cao của cây phân cấp từ các luật tại mức thấp hơn. Các luật đáng quan tâm (Interesting rules) Luật X ⇒ Y là không đáng quan tâm nếu sup(X ⇒ Y) ≈ sup(X) ∗ sup(Y) và sử dụng giá trị chi-square(÷2) để ki ểm tra luật về ý nghĩa thống kê. Tuy nhiên, điều kiệ n này không cắt tỉa được nhiều luật nên người ta sử dụng thông tin trong cây phân cấp để đưa ra một điều kiện khác cho phép cắt tỉa được nhiều luật hơn. Z Z Gọi ) ) là một tổ tiên của Z (Z và )  là các tập mục, Z, ) Z ⊆ É  ) nếu có thể tạo Z từ Z bằng cách thay thế một hoặc một số mục trong Z bởi các tổ tiên của ) chúng và Z và Z có cùng số lượng mục. ) ) ) ) Các luật X ⇒ Y , X ⇒ Y , X ⇒ Y ) được gọi là tổ tiên của luật X ⇒ Y. ) Cho trước một tập luật, ta gọi X ⇒ Y là tổ tiên đ óng của X ⇒ Y nếu ⇒ không tồn tại luật X’ ⇒ Y’ mà X’⇒ Y’ là tổ tiên của X ⇒ Y và ) ) là tổ X Y ) tiên của X’ ⇒ Y’(Tương ựt ) áp dụng định lý này cho các luật X ⇒ Y , X ⇒ Y ). Với một luật X ⇒ Y, đặt Z = X ∪Y. Độ hỗ trợ của Z sẽ bằng độ hỗ trợ Z của luật X ⇒Y. Ký hiệu E ) [Pr(Z )]  là độ