Luận văn Khai phá dữ liệu ứng dụng trong đào tạo

bỏ mục có support < minsup C2 2 - itemset {A, B} {A, C} {A, E} {B, C} {B, E} {C, E} C2 2 - itemset {A, B} {A, C} {A, E} {B, C} {B, E} {C, E} Tỉa L1 1 - itemset Count-support {A} 2 - 50% {B} 3 – 75% {C} 3 – 75% {E} 3 - 75% Kết nối L1 & L1 L2 2 - itemset Count-support {A, C} 2 – 50% {B, C} 2 – 50% {B, E} 3 – 75% {C, E} 2 – 50% Kết nối L2 & L2 Tỉa C3 3 - itemset Count- support {B, C, E} 2 - 50% Quét toàn bộ D C2 2 - itemset {A, B} {A, C} {A, E} {B, C} {B, E} {C, E} Quét toàn bộ D C2 2 - itemset Count-support {A, B} 1 – 25% {A, C} 2 – 50% {A, E} 1 – 25% {B, C} 2 – 50% {B, E} 3 – 75% {C, E} 2 – 50% Xóa bỏ mục có support < minsup Xóa bỏ mục có support < minsup L3 3 - itemset Count- support {B, C, E} 2 - 50% 3 - itemset {B, C, E} 3 - itemset {B, C, E} 43 Một số biến thể của giải thuật Apriori Giải thuật Apriori_TID là phần mở rộng theo hướng tiếp cận cơ bản của giải thuật Apriori. Thay vì dựa vào cơ sở dữ liệu thô, giải thuật AprioriTID biểu diễn bên trong mỗi giao dịch bởi các ứng viên hiện hành. 1. L1= {Large 1-itemset}; 2. C’1 = Database D; 3. for (k=2; Lk-1  ; k++) do 4. Begin 5. Ck = apriori_gen(Lk-1); 6. C’k = ; 7. for tất cả t  C’k-1 do 8. begin // xác định tập ứng viên trong Ck chứa trong giao dịch với định //danh t. Tid (Transaction Code) 9. Ct = c  Ck | (c-c[k])  t.Set_of_ItemSets ^ (c-c[k-1] t.Set_of_ItemSets 10. for những ứng viên c  Ct do c.count ++; 11. if (Ct) then C’k+= 12. end 13. Lk = c Ck | c.count  minsup; 14. End 15. return = kLk; Thuật toán này cũng sử dụng hàm apriori_gen để sinh ra các tập ứng cử viên cho mỗi giai đoạn. Nhưng thuật toán này không dùng CSDL D để đếm các support với các giai đoạn k > 1 mà sử dụng tập C’k. Mỗi phần tử của C’k có dạng , trong đó mỗi Xk là một tập phổ biến k_itemset tiềm năng trong giao dịch Tid. Khi k = 1, C’k tương ứng với D, trong đó mỗi item i được coi là một itemset {i}. Với k>1, C’k được sinh ra bởi C’k+= . Phần tử của C’k tương ứng với giao dịch t là <t.Tid, {c | c chứa trong t}>. Nếu một giao dịch không chứa bất kỳ tập ứngviên k_itemset nào thì C’k sẽ không có một điểm vào nào cho giao dịch này. Do đó, số lượng điểm vào trong C’k có thể nhỏ hơn số giao dịch trong CSDL, đặc biệt với k lớn. Hơn nữa, với các giá trị k khá lớn, mỗi điểm vào có thể nhỏ hơn giao dịch tương ứng vì một số ứng viên đã được chứa trong giao dịch. Tuy nhiên, với các giá trị k nhỏ, mỗi điểm vào có thể lớn hơn giao dịch tương ứng vì một một điểm vào trong C’k bao gồm tất cả các ứng viên k_itemset được chứa trong giao dịch. Giải thuật AprioriHybrid kết hợp cả hai hướng tiếp cận trên. Ngoài ra còn có một số các giải thuật tựa Apriori(TID), chúng được định hướng để cài trực tiếp trong SQL. 44 Giải thuật DIC là một biến thể khác nữa của giải thuật Apriori. Giải thuật DIC làm giảm đi khoảng phân biệt nghiêm ngặt giữa việc đếm và việc phát sinh các ứng viên. Bất kỳ ứng viên nào tới được ngưỡng minsupp, thì giải thuật DIC bắt đầu phát sinh thêm các ứng viên dựa vào nó. Để thực hiện điều này giải thuật DIC dùng một prefix-tree (cây tiền tố). Ngược với hashtree, mỗi nút (nút lá hoặc nút trong) của prefix-tree được gán một ứng viên xác định trong tập phổ biến. Cách sử dụng cũng ngược với hashtree, bất cứ khi nào tới được một nút ta có thể khẳng định rằng tập item đã kết hợp với nút này trong giao tác đó. Hơn nữa, việc xác định độ hỗ trợ và phát sinh ứng viên khớp nhau sẽ làm giảm đi số lần duyệt cơ sở dữ liệu. 2.3.2.Kỹ thuật DFS Giả sử việc đếm các thể hiện được thực hiện trên tập các ứng viên có kích thước hợp lý, với mỗi tập các ứng viên đó thì cần một thao tác duyệt cơ sở dữ liệu. Chẳng hạn như, giải thuật Apriori dựa vào BFS thực hiện duyệt cơ sở dữ liệu mỗi k-kích thước ứng viên một lần. Khi thực hiện tìm kiếm ưu tiên theo chiều sâu (DFS) tập ứng viên chỉ gồm chỉ gồm một nút của cây từ phần 2.2.2. Một điều hiển nhiên là nếu phải thực hiện duyệt cơ sở dữ liệu cho mỗi nút thì tổng chi phí kết quả thật khổng lồ. Vì thế việc kết hợp DFS với việc đếm các thể hiện là không thật sự thích hợp. 2.5. Thuật toán AIS 2.5.1. Bài toán đặt ra Đầu tiên, duyệt toàn bộ CSDL để tìm tất cả các tập mục phổ biến L1. Tiếp theo, chừng nào Lk-1 ! =  ( k >= 2) 1. Tìm tập các ứng cử viên bằng cách quét toàn bộ CSDL, với mỗi giao dịch, ta tìm tổ hợp chập k của các mục có trong giao dịch và xác định các mục trong tổ hợp này có là phổ biến hay không? Nếu không phải thì bỏ qua. Trái lại, ta bổ sung tổ hợp đó vào tập hợp ứng cử viên bằng cách: kiểm tra xem tổ hợp này đã nằm trong tổ hợp ứng cử viên hay chưa? Nếu chưa thì bổ sung thêm và tăng độ hỗ trợ lên 1. Trái lại, tăng độ hỗ trợ của tổ hợp tương ứng trong tập ứng cử viên thêm 1. 2. Duyệt toàn bộ các ứng cử viên, loại bỏ tất các tổ hợp có độ hỗ trợ nhỏ hơn độ hỗ trợ yêu cầu của người sử dụng. Cuối cùng ta được tất cả các tập mục phổ biến thoả mãn, có độ hỗ trợ tối thiểu lớn hơn hoặc bằng độ hỗ trợ tối thiểu mà người sử dụng yêu cầu. 45 Thuật toán hoàn toàn sử dụng chiến lược “vét cạn”, xem xét toàn bộ các tập mục phổ biến bằng cách sinh tổ hợp tập các mục và kiểm tra độ hỗ trợ. 2.5.2. Thuật toán AIS Input: CSDL minsup Output: Các tập mục phổ biến 1. L1={ Các tập mục phổ biến }. 2. For ( k=2;Lk-1  ; k++ ) 3.{ Ck = ; 4. for ( tất cả các giao dịch t D ) 5.  Lt = subSet (Lk-1; t); 6. // Các tập mục phổ biến thuộc Lk-1 chứa trong giao dịch t 7. for (tất cả các tập mục phổ biến lt Lt) 8.  Ct = tăng lt thêm một mục có trong giao dịch t; 9. for (Các ứng cử viên c  Ct ) 10. if ( c  Ck) tăng biến đếm của c thêm l cho mục tương ứng thuộc Ck 11. else add c vào Ck và tăng biến đếm tương ứng thêm 1) 12.  13.  14. Lk =  c  Ck  c.count  minsup  15.  16.return L = kLk Ví dụ minh hoạ thuật toán AIS Cho CSDL trong bảng sau. Giả sử với độ hỗ trợ tối thiểu là 2 giao dịch CSDL L1 TID Các mục Tập mục Độ hỗ trợ 100 1, 3, 4 1 2 200 2, 3, 5 2 3 300 1, 2, 3, 5 3 3 400 2, 5 5 3 C2 L2 Tập mục Độ hỗ trợ Tập mục Độ hỗ trợ 1, 3 2 1, 3 2 1, 4 1 2, 3 2 46 3, 4 1 2, 5 3 2, 3 2 3, 5 2 2, 5 3 3, 5 2 1, 2 1 1, 5 1 C3 L3 Tập mục Độ hỗ trợ Tập mục Độ hỗ trợ 1,3,4 1 2,3,5 2 2,3,5 2 1,2,3 1 1,2,5 1 1,3,5 1 C4 Tập mục Độ hỗ trợ 1,2,3,5 1 Bảng 2.7. Ví dụ thuật toán AIS Theo bước 1 của thuật toán, ta thu được L1 là tập gồm các mục có số lần xuất hiện (độ hỗ trợ) lớn hơn hoặc bằng 2. Trong các bước từ 2 đến 14 ta thu được tập ứng cử viên C2 là tập tất cả các tập có hai mục (2-itemset) và độ hỗ trợ tương ứng. Bước 13, ta thu được tập phổ biến L2 từ C2, L2 là tập các 2 itemset có độ hỗ trợ lớn hơn hoặc bằng 2. Lặp lại các bước từ 2 đến 14 ta thu được tập các ứng cử viên C3 gồm tập tất cả các tập có ba mục có độ hỗ trợ lớn hơn hoặc bằng 2. Tương tự, ta thu được C4 là tập có bốn mục L4 bằng rỗng. Như vậy, tập các tập mục phổ biến mà ví dụ trên ta thu được là: 1, 2, 3, 5, 1,3, 2,3, 2,5, 3,5, 2,3,5}. Thuật toán kết thúc. 47 2.6. Thuật toán SETM 2.6.1. Bài toán đặt ra Thuật toán SETM được đề xuất do mong muốn dùng SQL để tìm các tập mục phổ biến. 1. Đầu tiên, duyệt toàn bộ CSDL để tìm tất cả các tập mục phổ biến L1 và các mục phổ biến cùng với TID của nó L1' được xếp theo TID. 2. Tiếp theo chừng nào Lk-1!=  (k >= 2) 3. Tìm tập các ứng cử viên bằng cách quét toàn bộ CSDL, với mỗi giao dịch ta tìm tổ hợp chập k của các mục có trong giao dịch và xác định các mục cùng với TID trong tổ hợp này có thuộc L'k-1 ? Nếu không phải thì bỏ qua. Trái lại, ta bổ sung tổ hợp đó vào tập ứng cử viên đồng thời lưu một bản sao của tập mục ứng cử viên cùng với TID của nó. 4. Sắp xếp lại các ứng cử viên theo tập mục. 5. Xoá tất cả các ứng cử viên có độ hỗ trợ nhỏ hơn độ hỗ trợ do người sử dụng đề ra. Kết quả lưu vào Lk'. 6. Xếp lại Lk' theo TID. 7. Cuối cùng ta được tất cả các tập mục phổ biến thoả mãn, có độ hỗ trợ tối thiểu lớn hơn hoặc bằng độ hỗ trợ tối thiểu mà người sử dụng yêu cầu. 2.6.2. Thuật toán SETM Input: CSDL D, minsup Ouput: Tập các tập mục phổ biến. 1.L1 = Các mục phổ biến 2.L1' = Các mục phổ biến cùng các TID của nó được xếp theo TID 3.for (k=2; Lk-1  ; k ++) 4.C'k = ; 5. for (tất cả các giao dịch t  D) 6. Lt = l L'k-1 \I.TID = t.TID // Các tập có ( k-1) - itemset phổ biến có trong giao dịch t 7.for (tất cả các tập mục phổ bíên lt  Lt) 8. Ct = tăng lt thêm một mục có trong t; // Các ứng cử viên có trong t 9. C'k + =  \ c  C1 ; 10.  11.  48 12. sort C'k theo các tập mục 13. delete các mục c  C'k có c.count < minsup đưa vào L'k; 14. Lk = \ l  L'k; kết hợp với bước 13 15. sort L'k theo TID 16.  17.return L =  kLk'; Giống như AIS thuật toán SETM cũng sinh ra các ứng cử viên dựa trên các giao dịch đọc được từ CSDL. Vì thế, nó sinh ra và đếm mỗi tập mục ứng cử viên mà thuật toán AIS sinh ra. Tuy nhiên, để dùng phép nối (JOIN) chuẩn của SQL. SETM chia sự phát sinh ứng cử viên từ việc đếm. Nó lưu một bản sao của tập mục ứng cử viên cùng với TID của việc phát sinh giao dịch trong cấu trúc tuần tự (bước 9). Cuối mỗi bước, đếm độ hỗ trợ của các tập mục ứng cử viên được xác định bởi việc xếp (bước 12) và việc kết hợp lại cấu trúc tuần tự này (bước 13). SETM ghi nhớ các TID của việc phát sinh các giao dịch với các tập mục ứng cử viên. Để tránh việc thao tác trên tập con, nó dùng thông tin này để xác định các tập mục lớn chứa trong giao dịch được đọc (bước 6). L'k  C'k và thu được bởi việc xóa các ứng cử viên này mà không có độ hỗ trợ tối thiểu (bước 13). Giả sử rằng CSDL được xếp thứ tự TID, SETM có thể dễ dàng tìm các tập mục phổ biến được chứa trong một giao dịch trong bước tiếp theo bằng việc xếp L'k theo TID (bước 15). Thực tế, nó cần thăm hỏi mỗi thành viên của L'k chỉ một lần theo thứ tự TID và việc sinh ứng cử viên ở các bước 5 đến 11 có thể thực hiện nhờ phép toán Merge-join. Nhược điểm chính của thuật toán này là dựa vào số các tập ứng cử viên C'k. Khi với mỗi tập các mục ứng cử viên có một TID kết hợp với nó, nó yêu cầu nhiều không gian để lưu trữ số lượng lớn các TID. Hơn nữa, khi độ hỗ trợ của tập mục ứng cử viên được tính vào cuối mỗi bước, C'k không theo thứ tự. Vì thế, việc xếp lại các mục là cần thiết (bước 12). Sau đó, các tập mục ứng cử viên được cắt tỉa bằng việc loại bỏ các tập mục ứng cử viên không thoả mãn ràng buộc độ hỗ trợ. Một sắp xếp khác trên TID là cần thiết đối với tập kết qủa L'k (bước 15) trước khi nó có thể được sử dụng để phát sinh các ứng cử viên trong bước tiếp theo. Ví dụ minh hoạ thuật toán SETM Xét CSDL cho trong bảng sau. Giả sử với độ hỗ trợ tối thiểu là 2 giao dịch CSDL L1 L’1 TID Các mục Tập mục Độ hỗ trợ TID Tập mục 100 1, 3, 4 {1} 2 100 {1} 200 2, 3, 5 {2} 3 100 {3} 49 300 1, 2, 3, 5 {3} 3 200 {2} 400 2, 5 {5} 3 200 {3} 200 {5} 300 {1} 300 {2} 300 {3} 300 {5} 400 {2} 400 {5} C’2 L2 L’2 TID Tập mục Tập mục Độ hỗ trợ TID Tập mục 100 {1, 3} {1, 3} 2 100 {1, 3} 100 {1, 4} {2, 3} 2 200 {2, 3} 100 {3, 4} {2, 5} 3 200 {2, 5} 200 {2, 3} {3, 5} 2 200 {3, 5} 200 {2, 5} 300 {1, 3} 200 {3, 5} 300 {2,3} 300 {1, 2} 300 {2, 5} 300 {1, 3} 300 {3, 5} 300 {1, 5} 400 {2, 5} 300 {2, 3} 300 {2, 5} 300 {3, 5} 400 {2,5} L'3 L3 TID Tập mục Tập mục Độ hỗ trợ 50 200 {2, 3, 5} {2, 3, 5} 2 300 {2, 3, 5} C'4 L4 =  L'4 =  TID Tập mục 300 {1, 2, 3, 5} Bảng 2.8: Ví dụ thuật toán SETM Như vậy, tập các tập mục phổ biến mà ví dụ trên thu được là: L = 1, 2,3,5,1, 3,2, 3,2, 5,3, 5,2, 3, 5. Thuật toán kết thúc. 2.7. Thuật toán CHARM[9] 2.7.1. Tư tưởng thuật toán CHARM 2.7.1.1. Cơ sở lý thuyết Cho quan hệ nhị phân R I x X. Cho R I & R T, xét các ánh xạ: t: I  T, t(X) = {yT/xX, x R y}; i:TI, i(Y) = {xl/yY, x R y}. Một ánh xạ t(X) là tập tất cả các giao dịch chứa tập mục X, tương tự i(Y) là tập mục tất cả các giao dịch chứa tập mục Y. Định nghĩa một kết nối Galois giữa P(I) và P(T) tương ứng là các tập khả năng của l và T. Chúng ta biểu diễn cặp (X, t(X) là X x t(X) và cặp (i(X),Y) là i(Y) x Y kết nối Galois thoả mãn các thuộc tính sau (trong đó X, X1, X2  P(I) và Y,Y1, Y2  P(T):  X X2  t(X1) t(X2).  Y1 Y2  i(Y1) i(Y2).  X i(t(X)) và Y i(t(Y)). Cho s là một tập. Hàm c: P(S)P(S) là một toán tử đóng trên S nếu với  X,Y  S, c thoả mãn các thuộc tính sau:  Extention: X c(X)  Monotonicity: Nếu X  Y, thì c(X) c(Y)  Idempotency: c(c(X)) = c(X) 51  Một tập con X của S được gọi là đóng nếu c(X) =X Cho X Y và Y T. Cho Cit (X) biểu diễn ánh xạ hợp i0t(X) = i(t(X)) và Cit (Y)= i0i(Y) = t(i(Y)). Thì Cit :P(I) P(I) và Cti :P(T) P(T) là hai toán tử đóng trên các tập mục và các tập giao dịch tương ứng. Một số định nghĩa :  Định nghĩa tập mục đóng: X được gọi là tập mục đóng nếu X = Cit(X)  Định nghĩa tập mục đóng phổ biến: X được gọi là tập mục đóng phổ biến nếu X là tập mục đóng và support(X)  minsup.  Định nghĩa tập giao dịch đóng: Y là tập giao đóng nếu Y=Cit(Y) Các ánh xạ Cit và Cti là các toán tử đóng, thoả mãn 3 thuộc tính Extension, monotonicity và Idempotency. Cho f: P(I)  N là ánh xạ 1-1 từ các tập mục sang số nguyên. Với bất kỳ hai tập mục X1 và X2 nào, chúng ta nói X1  X2 f(X1)  f(X2). Hàm f xác định thứ tự toàn thể trên tập tất cả các tập mục. Ví dụ: nếu f biểu diễn theo thứ tự các từ điển, thì tập mục AC < AD. Khi với mẫu khác, nếu f sắp xếp các tập mục theo thứ tự tăng dần độ hỗ trợ của chúng, thì AD < AC nếu độ hỗ trợ của AD nhỏ hơn độ hỗ trợ của AC. Giả sử rằng chúng ta đang xử lý nhánh X1  t(X1) và chúng ta muốn kết nối với anh em của nó X2  t(X2). Điều này là X1  X2 (dưới dạng một thứ tự phù hợp f). Việc tính toán trong CHARM dựa trên các thuộc tính dưới đây: 1. Nếu t(X1) = t(X2), thì t(X1  X2) = t(X1)  t(X2) = t(X1) = t(X2). Vì thế chúng ta có sự xuất hiện của X1 bằng X1  X2 và xoá X2 được xem xét từ xa, vì bao đóng của X2 được đồng nhất với bao đóng của X1  X2. Mặt khác, chúng ta coi như X1  X2 là một tập mục hợp. 2. Nếu t(X1)  t(X2) thì t(X1  X2) = t(X1)  t(X2) = t(X1)  t(X2). Ở đây ta có thể thay mọi sự xuất hiện của X1 bằng X1  X2, vì nếu X1 xuất hiện trong bất kỳ giao dịch nào, thì X2 cũng xuất hiện. Nhưng khi t(X1)  t(X2), chúng ta không thể xóa X2. Nó phát sinh ra bao đóng khác. 3. Nếu t(X1)  t(X2) thì t(X1  X2) = t(X1)  t(X2) = t(X1)  t(X2). Trong trường hợp này, chúng ta thay thế mọi sự xuất hiện của X2 bằng X1  X2, vì bất chỗ nào X2 xuất hiện thì X1 cũng xuất hiện. Tuy nhiên, X1 là kết quả của bao đóng khác và nó phải được giữ lại. 52 4. Nếu t(X1)  t(X2) thì t(X1  X2) = t(X1)  t(X2)  t(X1)  t(X2). Trong trường hợp này, không được loại bỏ cả X1 và X2 dẫn đến các bao đóng khác nhau. 2.7.2.2. Bài toán đặt ra CHARM thực hiện trên cả không gian các tập phổ biến (itemset) và không gian các tập định danh (TIDset). CHARM không tìm tất cả các tập con có thể của tập mục mà thuật toán kết hợp tìm tập đóng hiệu quả hơn (bottom-up). Nếu CSDL cảu tập mục là lớn và tập mục phổ biến là dày thì CHARM duyệt cả không gian tập mục và tập định danh. Đồng thời sẽ bỏ qua nhiều mức để đi tìm tập phổ biến đóng thay cho việc tính toán nhiều tập con không đóng. Hơn nữa, CHARM sử dụng hai kỹ thuật cắt tỉa: 1. Tỉa các ứng cử viên nếu tập con của nó không phổ biến đồng thời tỉa các nhánh dựa trên tính chất không đóng (non-closure-property). 2. Bất kỳ tập không đóng nào cũng đều bị tỉa. CHARM không sử dụng cấu trúc dữ liệu cây băm (hash tree), phép toán cơ sở được sử dụng là hợp 2 tập mục và giao 2 tập định danh. Thuật toán bắt đầu bằng việc khởi tạo các nút để kiểm tra các mục đơn phổ biến và các tập giao dịch của chúng trong dòng 1. Tính toán chính được thực hiện trong CHARM-EXTEND, nó trả về các tập mục đóng phổ biến C. CHARM-EXTEND có trách nhiệm kiểm tra mỗi nhánh có khả năng. Nó rút ra mỗi cặp tập mục – tập giao dịch (itemset-tidset) trong tập nút hiện tại Node (Xi  t(Xi), dòng 3), và kết nối nó với các cặp khác mà đứng sau nó (Xi  t(Xi),dòng 5) theo thứ tự tuyệt đối f. Việc kết nối các cặp itemset-tidsset được tính toán trong. Thủ tục CHARM-PROPERTY kiểm tra tập kết quả với độ hỗ trợ yêu cầu và cũng áp dụng 4 thuộc tính được thảo luận ở trên. Lưu ý rằng thủ tục này có thể thay đổi tập nút hiện tại bằng việc xoá các cặp itemset-tidset mà đã được chứa trong các cặp đó. Nó cũng chèn các cặp phổ biến con mới được sinh ra trong tập các nút mới New. Nếu tập này khác rỗng chúng ta thực hiện lại quá trình theo chiều sâu (dòng 8). Sau đó, chúng ta chèn tập mục mở rộng có thể có X của Xi trong tập các tập mục đóng, vì nó không thể được thực hiện; ở giai đoạn này bất kỳ tập mục đóng đang chứa Xi, đã từng được sinh ra, sau đó chúng ta quay lại dòng 3 để xử lý nhánh tiếp theo (không được tỉa). Thủ tục CHARM-PROPERTY kiểm tra đơn giản nếu cặp mới là phổ biến. Sau khi nó kiểm tra mỗi cặp itemset-tidset với 4 thuộc tính cơ bản, việc mở rộng các tập mục hiện có, xoá một nhánh được gộp từ các nút hiện có, hoặc việc chèn các cặp mới trong tập nút cho bước tiếp theo (theo chiều sâu). 53 2.7.2. Thuật toán CHARM CHARM (R  I  T, minsup) 1.Nodes = {Ij  t(Ij): Ij  I  t(Ij)   minsup } 2.CHARM-EXTEND (Nodes, C) 3.For (mỗi Xi  t(Xj)  Nodes) 4. NewN =  & X = Xi 5. for (mỗi Xj  t(Xj)  Nodes với f(j) > f(i)) 6. X= X  Xj và Y= t(Xi)  t(Xj) 7. CHARM-PROPERTY( Nodes, NewN) 8. if (NewN   ) CHARM-EXTEND (NewN) 9. C=C  X;//nếu X chưa được gộp CHARM-PROPERTY( Nodes, NewN) 10. if ( || Y ||  minsup) 11. if(t(Xi) = t(Xj)) // Thuộc tính 1 12. Loại Xj ra khỏi Nodes 13. Thay thế tất cả các Xi bởi X 14. else if (t(Xi)  t(Xj)) // Thuộc tính 2 15. Thay thế tất cả các Xi bởi X 16. else (if t(Xi)  t(Xj)) // Thuộc tính 3 17. Xoá tất cả các Xj khỏi Nodes 18. Bổ sung X  Y vào NewN 19. else if (t(Xi)  t(Xj)) // Thuộc tính 4 20. Bổ sung X  Y vào NewN Ví dụ minh hoạ thuật toán CHARM Cho I ={A, C, D, T, W } và T = {1, 2, 3, 4, 5, 6} Giao dịch Các mục 1 {A, C, T, W} 2 {C, D, W } 3 {A, C,T, W } 4 {A, C, D, W } 5 {A, C, D, T, W } 6 {C, D, T } Bảng 2.9: Tập các giao dịch trong ví dụ thuật toán CHARM Từ bảng giao dịch trên, ta thu được tập mục phổ biến với độ hỗ trợ tối thiểu là 3 giao dịch: 54 Tập mục Hỗ trợ {C} 6 {{W}, {C, W }} 5 {{A}, {D}, {T}, {A,C},{A,W}, 4 {{A,T},{D,W},{T,W},{A,C,T},{A,T,W},{C,T,W},{C,D,W},{ A,C,T,W} 3 Bảng 2.10: Tập mục phổ biến trong ví dụ minh hoạ thuật toán CHARM a) Sắp xếp các tập mục theo thứ tự từ điển Chú ý: Để tiện cho mô tả chúng ta qui ước viết: ví dụ: 1345 tương ứng là {1,3,4,5}, ACD tương ứng với {A,C,D} Hình 2.11: Thuật toán CHARM sắp xếp theo thứ tự từ điển Ban đầu ta có 5 nhánh tương ứng với 5 mục và các tập giao dịch từ CSDL trên(minsup=3). Để phát sinh con của mục A(hoặc cặp A x{1,3,4,5}) chúng ta cần nối nó với tất cả các anh em đi sau nó. Khi ta nối 2 cặp X1 x t(X1) và X2 x t(X2). Cặp kết quả đưa ra là (X1 X2) x (t(X1)  t(X2)). Mặt khác, chúng ta cần thực hiện giao của các tập giao dịch tương ứng mỗi khi chúng ta nối hai hoặc nhiều hơn hai mục. Khi chúng ta thử mở rộng A với C, chúng ta thấy rằng thuộc tính hai là đúng. Nghĩa là, t(A) = {1,3,4,5} {1,2,3,4,5,6} =t(C). Vì thế, chúng ta có thể xoá A và thay bằng AC. Kết nối A với D kết quả là tập không phổ biến {A,C,D} bị cắt tỉa. Kết nối với T kết quả cặp{A,T,C} x {1,3,5} theo thuộc tính 4 không bị tỉa. Khi thử kết nối A D x 2456 CD x 2456 CT x 1356 CW x 12345 CTW x 135 A x 1345 AC x 1345 ACW x 1345 C x 123456 Tx 1356 W x 12345 ACD x 45 ACTx 135 ACTW x 135 CDT x 56 CDW x 245 {} 55 với W ta thấy rằng t(A)  t(W) theo thuộc tính 2 ta thay A bằng {A,W}. Do đó {A,C} thành {A,C,W} và {A,C,T} thành {A,C,T,W}. Tiếp theo ta bắt đầu xử lý nhánh C, ta kết nối C với D, ta thấy thuộc tính có 3 hiệu lực, nghĩa là: t(X)  t(D), tức là mỗi khi D xuất hiện thì C cũng xuất hiện. Vì thế, D có thể được loại bỏ và toàn bộ nhánh D bị tỉa; còn {C,D} thay bằng D. Cũng như vậy, ngữ cảnh tương tự xảy ra với T và W. Cả 2 nhánh bị tỉa và được tỉa thay thế bởi {C,T} và {C,W} là con của C.Tiếp tục duyệt theo chiều sâu,chúng ta xử lý tiếp với nút{C,D}.Nối{C,D} với{C,T} kết quả là tập mục không phổ biến {C,D,T} bị cắt tỉa. Nối {C,D} với {C,W} kết quả là {C,D,W} theo thuộc tính 4 không bị loại bỏ. Tương tự, nối {C,T} và {C,W} thành {C,T,W}.Lúc này các nhánh đã được xử lý. Cuối cùng, chúng ta xoá {C,T,W} x {1,3,5} vì nó được chứa trong{A,C,T,W} x {1,3,5}. Qua 10 bước xác định được tất cả 7 tập mục phổ biến đóng. b) Sắp xếp các tập mục theo độ hỗ trợ tăng dần Hình 2.12: Sắp xếp theo độ hỗ trợ tăng dần Nhận xét: Tính đúng đắn: Thuật toán CHARM tìm ra tất cả các tập mục phổ biến đóng. Thời gian tính toán: Thời gian tính toán của thuật toán CHARM là O(l*|C|) trong đó C là các tập mục phổ biến đóng; l là độ dài trung bình của tập định danh. Độ phức tạp: Số lần duyệt CSDL của CHARM là O(|C|/(*|I|)) trong đó: C là các tập mục phổ biến đóng; {I} là tập các mục và  là độ lớn phân vùng CSDL trong bộ nhớ. { } A x 1345 AW x 1345 ACW x 1345 T x 1356 CT x 1356 W x 12345 CW x 12345 C x 123456 AT x 135 ATW x 135 ACTW x 134 AD x 45 DT x 56 D x 2456 CD x 2456 DW x 245 CDW x 245 TW x 135 CTW x 135 56 2.8. Kết luận Chương này đã trình bày về lý thuyết luật và luật kết hợp, trình bày một số vấn đề cơ bản của việc khai phá dữ liệu dùng luật kết hợp. Trình bày một số thuật toán tiêu biểu khai phá luật kết hợp. Thuật toán kinh điển Apriori tìm tập mục phổ biến theo cách sinh các ứng cử, biến thể của thuật toán Apriori là thuật toán Apriori_Tid, và thuật toán AIS, SETS, CHARM. Độ phức tạp thuật toán tìm các tập mục phổ biến là khó, thời gian tìm các tập mục phổ biến là tuyến tính với kích thước của CSDL vì các CSDL thường là rất thừa và các thuật toán đã dùng một số kỹ thuật tỉa hiệu quả. 57 Chương 3 ỨNG DỤNG KHAI PHÁ LUẬT KẾT HỢP TRONG ĐÀO TẠO 3.1. Bài toán Hiện nay trường Đại học Dân lập Hải Phòng đã bắt đầu thực hiện chương trình đào tạo theo chế tín chỉ, nên đầu mỗi học kỳ sinh viên phải tiến hành đăng ký môn học. Để tạo điều kiện cho việc chọn đăng ký môn học cho mỗi học kỳ phòng Đào tạo sẽ phải lên danh sách các lớp học kèm theo thời khóa biểu. Bên cạnh đó để hỗ trợ thêm cho sinh viên có thể đăng ký môn học được tốt hơn thì các cán bộ phòng đào tạo và cán bộ tư vấn học tập phải tổ chức dữ liệu một cách khoa học rồi tiến hành trích rút thông tin dựa theo kết quả học tập của các môn học kỳ trước đó. Để có thể hỗ trợ sinh viên lựa chọn ngành nghề, lựa chọn môn học, hỗ trợ sau tốt nghiệp, đánh giá kết quả học tập của sinh viên phải dựa trên cơ sở hệ thống điểm mà sinh viên đã đạt được. Đây là cơ sở mang tính khoa học. Để có được những đánh giá mang tính thuyết phục, thì cần phải có phương pháp khai phá dữ liệu có hiệu quả, từ đó để đưa ra những kết luận có cơ sở khoa học, mang nhiều ý nghĩa thực tiễn. Muốn vậy chúng ta phải có dữ liệu tương đối đầy đủ. Trên cơ sở rút ra những luật kết hợp, tìm ra được các luật mạnh để có thể phân tích dựa trên dữ liệu điểm sinh viên. Hình 3.1: Trường Đại học Dân lập Hải phòng Trong phạm vi luận văn này, tác giả sử dụng các kỹ thuật khai phá dữ liệu đối với CSDL điểm của sinh viên trường Đại học Dân lập Hải phòng nhằm giúp cho sinh viên có thể lựa chọn tốt môn học, ngành nghề, giúp cho cán bộ đào tạo đánh giá được kết quả học tập của sinh viên, và hiệu quả đào tạo thông qua thuật toán Apriori đã trình bày ở phần trước. 58 3.2. Đặc tả dữ liệu Một đặc điểm mang tính thực tế là các item không đơn thuần chỉ được xét là “có” hay “không” trong khi đếm support mà mỗi item được kèm theo một trọng số mô tả mức quan trọng của item đó. Các item ta vẫn xem xét thường ở dạng Boolean. Chúng mang giá trị là “1” nếu item có mặt trong giao dịch và “0” nếu ngược lại. Các bài toán khai phá như trên người ta vẫn gọi là khai phá luật kết hợp kiểu Boolean (Mining Boolean Association Rules). Nhưng trong thực tế, các bảng số liệu thường xuất hiện các thuộc tính không đơn giản như vậy. Các thuộc tính có thể ở dạng số (quantitative) như điểm môn lập trình Java, điểm môn cơ sở dữ liệu, hoặc dạng phân loại (categorical) như các lớp, các ngành... Các bài toán khai phá luật kết hợp trên các thuộc tính như vậy gọi là khai phá luật kết hợp định lượng (Mining Quantitative Association Rules). Cũng như các bài toán khai phá luật kết hợp trước đây, mục tiêu của bài toán khai phá luật kết hợp định lượng cũng là kết xuất các luật kết hợp trên các ngưỡng support tối thiểu và các ngưỡng confidence tối thiểu. Với các thuộc tính định lượng thì cần phải có sự phân đoạn cho các thuộc tính này vì suy cho cùng thì khi tính support cũng cần phải kiểm tra lại nó tồn tại hay không tồn tại trong giao dịch. Nói cách khác là cần phải thực hiện ánh xạ các thuộc tính định lượng sang thuộc tính Boolean. Nếu các thuộc tính phân loại hoặc số lượng chỉ có vài giá trị riêng biệt thì có thể thực hiện ánh xạ này đơn giản như sau: Mỗi thuộc tính trong bảng dữ liệu có p giá trị riêng biệt sẽ được lập thành p thuộc tính logic mới. Mỗi thuộc tính logic này tương ứng với một cặp (attribute, value). Nó có giá trị “1” nếu value có mặt trong dữ liệu gốc và có giá trị “0” nếu ngược lại. Nếu số giá trị riêng biệt của một số thuộc tính khá lớn thì người ta thực hiện phân đoạn thuộc tính thành các khoảng và ánh xạ mỗi cặp (attribute, value) thành một thuộc tính. Sau khi ánh xạ, có thể thực hiện khai phá luật kết hợp trên cơ sở dữ liệu mới bằng thuật toán khai phá luật kết hợp kiểu logic. Tổng quát, ta có thể đưa ra một số phương pháp rời rạc hoá như sau: Trường hợp 1 : Nếu A là thuộc tính số rời rạc hoặc là thuộc tính hạng mục có miền giá trị hữu hạng dạng {V1, V2,..., Vk} và k đủ nhỏ (<100) thì ta biến đổi thuộc tính này thành k thuộc tính nhị phân A_V1, A_V2,..., A_Vk. Giá trị của bản ghi tại trường A_Vi = True (hoặc 1) Nếu giá trị của bản ghi đó tại thuộc tính A ban đầu bằng vi, Ngược lại Giá trị của A_Vi = False (hoặc 0). 59 Trường hợp 2 : Nếu A là thuộc tính số liên tục hoặc A là thuộc tính số rời rạc hay thuộc tính hạng mục có miền giá trị hữu hạng dạng {V1, V2,..., Vp} (p lớn) thì ta sẽ ánh xạ thành q thuộc tính nhị phân , ,..., <A : startq.. endq>. Giá trị của bản ghi tại trường bằng True (hoặc 1) nếu giá trị của bản ghi đó tại thuộc tính A ban đầu nằm trong khoảng [starti.. endi], ngược lại giá trị của = False (hoặc 0). Mã Sv Họ tên Lớp CSDL CTDL& GT Java …. C++ 08850 Lã Vũ Bình CT801 8 8 8 …. 7 08963 Trần Quang Lâm CT802 8 7 9 …. 7 08760 Bùi Thị Hạnh CT801 7 8 9 …. 7 08865 Trần Văn Sơn CT801 5 6 6 …. 4 07866 Nguyễn Thị Thuỳ CT701 5 7 7 … 8 07889 Trần Thị Lan CT702 9 8 9 … 8 08975 Trần Hồng Quang CT801 4 6 6 … 7 LT1011 Nguyễn Tuấn Anh LT101 6 5 7 … 7 ….. …. … … … … … … Bảng 3.2: Ví dụ CSDL điểm của sinh viên Ví dụ: Với bảng số liệu trên đây ta có thể phân chia như sau: Theo quy chế 25 của bộ giáo dục đào tạo mỗi sinh viên chỉ được phép thi tối đa hai lần cho một lần học của mỗi môn học, nếu sinh viên nào qua hai lần thi vẫn chưa đỗ thì phải học lại môn đó. Vậy ở đây nếu sinh viên nào phải thi lại thì sẽ có hai điểm của môn học đó. Vậy đối với các sinh viên này tác giả sẽ lấy điểm cao nhất trong hai lần thi. Thuộc tính điểm các môn là thuộc tính có nhiều giá trị, ta có thể phân thành các khoảng, 0..5, 5..7, 7..9, 9..10. Vậy theo như bảng trên thì mỗi điểm sẽ có 4 khoảng điểm: ở đó đặt 1 ứng với khoảng điểm (0..5), 2 ứng với khoảng [5..7), 3 ứng với khoảng [7..9), 4 ứng với khoảng [9..10]. Như vậy, với cách ánh xạ trên, từ CSDL gốc ban đầu, ta có CSDL dạng logic đối với môn CSDL sau đây, các môn khác tương tự cũng chia làm 4 khoảng: 60 CSDL Mã Sv Họ tên Lớp 1:(0..5) 2:[5..7) 3:[7..9) 4:[9..10] 08850 Lã Vũ Bình CT801 0 0 1 0 08963 Trần Quang Lâm CT802 0 0 1 0 08760 Bùi Thị Hạnh CT801 0 0 1 0 08865 Trần Văn Sơn CT801 0 1 0 0 07866 Nguyễn Thị Thuỳ CT701 0 1 0 0 07889 Trần Thị Lan CT702 0 0 0 1 08975 Trần Hồng Quang CT801 1 0 0 0 LT1011 Nguyễn Tuấn Anh LT101 0 1 0 0 ….. …. … … … … … Bảng 3.3: Dữ liệu đã chuyển đổi từ dạng số sang dạng logic Việc ánh xạ như trên có thể xảy ra vấn đề sau:  “minsup”: Nếu số lượng khoảng cho thuộc tính số lượng (hoặc số các giá trị riêng cho thuộc tính phân loại) là lớn thì support cho các khoảng có thể là nhỏ. Do đó, việc chia một thuộc tính ra quá nhiều khoảng có thể làm cho luật chứa nó không đạt được support tối thiểu.  “minconf”: Một số thông tin có thể bị mất do việc chia khoảng. Một số luật có thể có minconf chỉ khi một item trong chúng có giá trị đơn hoặc một khoảng rất nhỏ, do đó thông tin có thể bị mất. Sự mất mát thông tin càng tăng khi kích thước khoảng chia càng lớn. Như vậy, nếu kích thước khoảng là quá lớn (số khoảng nhỏ) thì có nguy cơ một số luật sẽ không có confidence tối thiểu, còn nếu kích thước các khoảng quá nhỏ (số khoảng lớn) thì một số luật lại có nguy cơ không có support tối thiểu. Để giải quyết hai vấn đề trên, người ta chú ý đến tất cả các vùng liên tục trên thuộc tính số lượng hoặc trên các khoảng đã phân đoạn. Vấn đề “minsup”sẽ được khắc phục bằng cách liên hợp các khoảng gần kề hoặc các giá trị gần kề. Vấn đề “minconf” sẽ được khắc phục bằng cách tăng số lượng khoảng mà không ảnh hưởng đến vấn đề “minsup”. 61 Người ta có thể thực hiện một phương pháp đơn giản để thực hiện việc chuyển các thuộc tính số lượng và phân loại về cùng một dạng với nhau. Với thuộc tính phân loại, các giá trị của nó sẽ được ánh xạ vào tập các số nguyên liên tiếp. Với các thuộc tính số lượng không cần khoảng chia (tức là có ít giá trị) thì các giá trị sẽ được ánh xạ vào tập các số nguyên liên tiếp theo thứ tự của các giá trị đó. Còn đối với các thuộc tính số lượng được phân khoảng, thì các khoảng sẽ được ánh xạ vào tập số nguyên liên tiếp, trong đó thứ tự các khoảng sẽ được bảo tồn. Các ánh xạ này sẽ làm cho mỗi bản ghi trong CSDL trở thành một tập các cặp (Attribute, Value). Bài toán khai phá luật kết hợp lúc này có thể thực hiện qua các bước sau: 1. Xác định số lượng mỗi phần chia cho mỗi thuộc tính số lượng. 2. Với các thuộc tính phân loại, ánh xạ các thuộc tính vào tập số nguyên liên tiếp. Với các thuộc tính số lượng không cần sự phân khoảng, ánh xạ các giá trị của chúng vào tập các số nguyên liên tiếp theo thứ tự giá trị thuộc tính. Với các thuộc tính số lượng đã được phân khoảng, ánh xạ các khoảng được chia vào tập các số nguyên liên tiếp và bảo tồn thứ tự các khoảng. Bằng cách này, thuật toán chỉ xem các giá trị hoặc các vùng giá trị như là các thuộc tính định lượng. 3. Tìm support cho mỗi giá trị của các thuộc tính phân loại lẫn thuộc tính số lượng, tiếp theo tìm tất cả các itemset mà support của nó lớn hơn support tối thiểu. 4. Sử dụng các tập tìm được để sinh ra các luật kết hợp. 5. Xác định luật đáng quan tâm và kết xuất chúng. Như vậy, khi xét trên CSDL điểm của sinh viên (giả sử với các môn học chuyên ngành CNTT), ta có thể thực hiện phân chia thuộc tính điểm trong bảng thành các khoảng và ký hiệu như sau: Mã mh Tên môn học 1:(0..5) 2:[5..7) 3:[7..9) 4:[9..10] ct1 An toàn bảo mật thông tin A1 A2 A3 A4 ct2 Anh văn chuyên ngành B1 B2 B3 B4 ct3 Bảo vệ đồ án tốt nghiệp_ Mon TN C1 C2 C3 C4 ct4 Cấu trúc dữ liệu và giải thuật D1 D2 D3 D4 ct5 Cấu trúc máy tính E1 E2 E3 E4 ct6 Chương trình dịch F1 F2 F3 F4 ct7 Cơ sở dữ liệu 1 G1 G2 G3 G4 62 ct8 Cơ sở dữ liệu 2 H1 H2 H3 H4 ct9 Công nghệ phần mềm I1 I2 I3 I4 ct10 Đồ hoạ máy tính J1 J2 J3 J4 ct11 Hệ điều hành K1 K2 K3 K4 ct12 Hệ quản trị CSDL Oracle N1 N2 N3 N4 ct13 Kỹ thuật Ghép nối máy tính M1 M2 M3 M4 ct14 Lập trình Visual Basic O1 O2 O3 O4 ct15 Lập trình ASP/PHP P1 P2 P3 P4 ct16 Lập trình C Q1 Q2 Q3 Q4 ct17 Lập trình C++ R1 R2 R3 R4 ct18 Lập trình hướng đối tượng S1 S2 S3 S4 ct19 Lập trình JAVA T1 T2 T3 T4 ct20 Lôgíc toán U1 U2 U3 U4 ct21 Lý thuyết đồ thị V1 V2 V3 V4 ct22 Mạng máy tính W1 W2 W3 W4 ct23 Mạng máy tính và truyền số liệu X1 X2 X3 X4 ct24 Mạng và hệ phân tán Y1 Y2 Y3 Y4 ct25 MATLAP và mô phỏng Z1 Z2 Z3 Z4 ct26 Otomat và ngôn ngữ hình thức Aa1 Aa2 Aa3 Aa4 ct27 Phân tích và thiết kế hệ thống Bb1 Bb2 Bb3 Bb4 ct28 Phương pháp tính Cc1 Cc2 Cc3 Cc4 ct29 Quản lý dự án CNTT Dd1 Dd2 Dd3 Dd4 ct30 Quản trị mạng Ee1 Ee2 Ee3 Ee4 ct31 Thương mại điện tử Ff1 Ff2 Ff3 Ff4 ct32 Tin học đại cương Gg1 Gg2 Gg3 Gg4 ct33 Trí tuệ nhân tạo Hh1 Hh2 Hh3 Hh4 ct34 Vi xử lý và lập trình Assembly Ii1 Ii2 Ii3 Ii4 ct35 Xử lý ảnh Jj1 Jj2 Jj3 Jj4 63 Bảng 3.4: Bảng ký hiệu tên các môn học Sơ đồ quan hệ để lưu trữ dữ liệu điểm của sinh viên như sau: Hình 3.5: Sơ đồ quan hệ CSDL điểm sinh viên 3.3. Chương trình thử nghiệm minh họa Đẻ thử nghiệm một số khía cạnh lí thuyết liên quan đến khai phá dữ liệu, luận văn thực hienẹ chương trình minh họa. Chương trình cài đặt trên ngôn ngữ C#, CSDL thiết kế trên SQL Server 2005, hệ điều hành WindowsXP, chip máy tính Pentium IV 1.7 GHz, RAM 512 MB, ổ cứng 80 GB còn trống gần 7 GB. Chương trình có một số giao diện chính sau: Hình 3.6: Giao diện chương trình chính 64 Hình 3.7: Phần kết nối CSDL Hinh 3.8: Form cập nhật điểm sinh viên Hình 3.9: Form cập nhật thêm sinh viên 65 Hình 3.10: Phần dữ liệu đã được mã hoá Hình 3.11: Phần tạo luật kết hợp dùng thuật toán Apriori 66 Hình 3.12: Phần mô phỏng thuật toán với dữ liệu nhập vào từ bàn phím 3.4. Kết luận Chương trình thực hiện tìm các tập phổ biến và luật kết hợp thông qua thuật toán Apriori. Từ các luật kết hợp thu được từ chương trình ta có thể tìm ra các luật mạnh phục vụ cho công tác đào tạo, hỗ trợ cho sinh viên lựa chọn môn học, ngành nghề. Để xác định độ Support của các tập ứng viên, thuật toán Apriori luôn luôn phải quét lại toàn bộ các giao dịch trong CSDL. Do vậy sẽ tiêu tốn rất nhiều thời gian khi số k-items tăng (số lần xét duyệt các giao dịch tăng). Hướng phát triển Tiếp tục hoàn thiện và mở rộng chương trình trong luận văn này để có thể áp dụng vào thực tế toàn diện hơn. Mở rộng khai phá luật kết hợp với dữ liệu đầu vào rộng hơn, không chỉ dừng lại ở điểm của sinh viên mà còn có thể là các yếu tố khác như: chuyên ngành về mạng máy tính thì sau khi ra trường có thể dễ xin việc hơn nên có nhiều sinh viên đăng ký học ngành này hơn. Xây dựng thêm phần tiền xử lý dữ liệu. Các tệp CSDL khác nhau như: Microsoft Access, Foxpro, Oracle… đều có thể chuyển về một dạng thống nhất để chương trình xử lý được. Nghiên cứu sâu các thuật toán khai phá dữ liệu, và áp dụng vào một số bài toán khai phá dữ liệu phù hợp với giai đoạn hiện nay: dự báo dân số, bệnh dịch, thời tiết, định hướng trong kinh doanh … 67 KẾT LUẬN Khai phá dữ liệu là một lĩnh vực vẫn còn khá mới mẻ, lý thú. Luận văn đã trình bày, một số vấn đề cơ bản nhất, các phương pháp cơ bản để khai phá dữ liệu, đặc biệt trình bày chi tiết, làm rõ vấn đề khai phá luật kết hợp. Phương pháp khai phá dữ liệu có thể là: phân lớp, hồi quy, cây quyết định, suy diễn, quy nạp, K- láng giềng gần, … các phương pháp trên có thể áp dụng trong dữ liệu thông thường và trên tập mờ. Bài toán khai phá luật kết hợp là bài toán khó. Luận văn đã trình bày thuật toán khai phá kinh điển Apriori và các thuật toán mới hiệu quả nhất (Apriori_Tid, Setm, Ais, Charm). Một cách tiếp cận khai phá luật kết hợp đảm bảo không dư thừa các luật và cho hiệu quả khai phá cao là dựa trên tập đóng. Thuật toán khai phá hiệu quả điển hình là thuật toán CHARM. Kết quả xây dựng chương trình thử nghiệm dựa trên thuật toán Apriori nhằm mô phỏng rõ hơn về khai phá dữ liệu bằng luật kết hợp. Chương trình ứng dụng vào bài toán dự báo kết quả học tập của sinh viên, hỗ trợ sinh viên lựa chọn môn học, lựa chọn ngành học, hỗ trợ cho cán bộ đào tạo đưa ra định hướng đào tạo trong các năm tiếp theo. 68 PHỤ LỤC Lớp Apriori public class Apriori { //Mang danh sach cac tap phan tu luu trong cac tap muc pho bien protected ItemsetArrayList itemsetsFrequentCollection; //Mang danh sach cac phan tu luu trong tap muc cac ung cu protected ItemsetArrayList itemsetsCandidateCollection; //Xay dung lop Apriori public Apriori() { this.itemsetsCandidateCollection = new ItemsetArrayList(); this.itemsetsFrequentCollection = new ItemsetArrayList(); } public void OnProgressMonitorEvent(ProgressMonitorEventArgs e) { if (ProgressMonitorEvent != null) { ProgressMonitorEvent(this, e); } } public event ProgressMonitorEventHandler ProgressMonitorEvent; protected DataRow[] FindItems(string find, DataTable data) { return data.Select(find); } protected int FindItems(string find, string data) { string[] splitstring = data.Split(new Char[] { ',' }); int length = splitstring.Length; int countFound = 0; string[] found = new string[length]; for (int counter = 0; counter < length; counter++) { found[counter] = splitstring[counter].Trim(); } foreach (string member in found) { if (member == find) { countFound++; } } return countFound; } //Mang danh sach cac tap muc protected int FindItems(ItemsetArrayList find, string data) 69 { string[] splitstring = data.Split(new Char[] { ',' }); int length = find.Count; string[] found = new string[splitstring.Length]; int minimumValue = 0; int[] search = new int[length]; for (int counter = 0; counter < splitstring.Length; counter++) { found[counter] = splitstring[counter].Trim(); } for (int count = 0; count < length; count++) { foreach (string member in found) { if (member == (string)find[count]) { search[count]++; } } } switch (length) { case 0: { minimumValue = 0; break; } case 1: { minimumValue = search[0]; break; } default: { for (int counter = 0; counter < search.Length; counter++) { if (counter == 0) { minimumValue = search[counter]; } else { if (search[counter] < minimumValue) { minimumValue = search[counter]; } } 70 } break; } } return minimumValue; } //Tinh Support cua 1 tap muc trong CSDL public int SupportCount(string find, Database Transactions_Data) { int count = 0; DataTable datatable = Transactions_Data.Transactions.Tables[0]; foreach (DataRow datarow in datatable.Rows) { count = count + FindItems(find, (datarow["Transactions"]).ToString()); } return count; } //Lay gia tri Support cua 1 tap muc public int SupportCount(ItemsetArrayList find, Database transactionsData) { int count = 0; int total = 0; DataTable dataTable =transactionsData.Transactions.Tables["TransactionTable"]; foreach (DataRow datarow in dataTable.Rows) { count = this.FindItems(find, (datarow["Transactions"]).ToString()); total = count + total; } return total; } //Tao tap cac tap muc tu CSDL cua cac giao [ReservedAttribute(false, "December 25, 2002")] public ItemsetCandidate CreateOneItemsets(Database dataBase) { DataTable dataTable = dataBase.Transactions.Tables["TransactionTable"]; ItemsetCandidate candidateItemset = new ItemsetCandidate(); ItemsetArrayList uniqueItems = new ItemsetArrayList(1); ; ItemsetArrayList candidateItems; ItemsetArrayList items; StringBuilder item = new StringBuilder(10); int itemSupportCount = 0; int counter = 1; string msg = "Creating One Itemsets"; ProgressMonitorEventArgs e = new ProgressMonitorEventArgs(1, 100, 80, "Apriori.CreateOneItemsets(Database)", msg); this.OnProgressMonitorEvent(e); foreach (DataRow dataRow in dataTable.Rows) 71 { item.Append(dataRow["Transactions"].ToString()); if (counter < (dataTable.Rows.Count)) { item.Append(", "); counter++; } } candidateItems = ItemsetArrayList.ConvertToItemsetArrayList(item.ToString(), new Char[] { ',' }); for (int count = 0; count < candidateItems.Count; count++) { item = new StringBuilder(10); item.Append(((string)candidateItems[count]).Trim()); if (!(item.ToString() == "")) { if (!uniqueItems.Contains(item.ToString())) { itemSupportCount = this.SupportCount(item.ToString(), dataBase); dataBase.AddItemset(item.ToString(), 1, itemSupportCount); items = new ItemsetArrayList(1); uniqueItems.Add(item.ToString()); items.Add(item.ToString()); items.Level = 1; items.SupportCount = itemSupportCount; items.TrimToSize(); candidateItemset.Items.Add(items); } } } candidateItemset.Items.TrimToSize(); candidateItemset.Level = 1; return candidateItemset; } //Lop Apriori_Gen public void AprioriGenerator(ItemsetCandidate Candidate_Itemset, Database TransactionsData, int minimum_support) { string start = "Generating Level " + Candidate_Itemset.Level + " Candidates : " + Candidate_Itemset.Items.Count + " Items"; ProgressMonitorEventArgs e = new ProgressMonitorEventArgs(1, 100, 25, "Apriori.AprioriGenerator()", start); this.OnProgressMonitorEvent(e); //Them 1 tap muc ung cu vien vao tap cac tap muc ung cu vien ItemsetCandidate candidateItemset = this.JoinCandidateItemsets(Candidate_Itemset, TransactionsData, minimum_support); if (candidateItemset.Items.Count > 0) { 72 this.AprioriGenerator(candidateItemset, TransactionsData, minimum_support); } string done = "Finished Generating Candidate Itemsets "; e = new ProgressMonitorEventArgs(1, 100, 70, "Apriori.AprioriGenerator()", done); this.OnProgressMonitorEvent(e); } //tap muc ung cu vien protected ItemsetCandidate GenerateFrequentItemsets(ItemsetCandidate candidateItemset, int minimum_support) { ItemsetCandidate itemsetFrequent = new ItemsetCandidate(); foreach (ItemsetArrayList itemsFrequent in candidateItemset.Items) { if (itemsFrequent.SupportCount >= minimum_support) { itemsetFrequent.Items.Add(itemsFrequent); } } itemsetFrequent.Items.Capacity = itemsetFrequent.Items.Count; return itemsetFrequent; } //Kiem tra neu 1 phan tap muc co 1 tap muc con pho bien protected bool HasInfrequentSubSet() { throw new Exception("This is a reserved attribute! Do not use it"); } public ItemsetArrayList ItemsetsFrequentCollection { get { return itemsetsFrequentCollection; } set { itemsetsFrequentCollection.Add(value); } } //Lua chon tap cac ung cu vien public ItemsetArrayList ItemsetsCandidateCollection { get { return itemsetsCandidateCollection; } set { 73 itemsetsCandidateCollection.Add(value); } } //Tao 1 tap muc bang 1 tap muc ung cu vien public ItemsetCandidate JoinCandidateItemsets(ItemsetCandidate candidate_itemset, Database transactionsData, int minimumSupport) { //neu so tap muc bang 0 if (candidate_itemset.Items.Count == 0) { throw new Exception("cannot join items : no items are present!"); } else { ItemsetArrayList copy_candidate_itemset = candidate_itemset.Items; ItemsetCandidate new_candidate_itemset = new ItemsetCandidate(); new_candidate_itemset.Level = candidate_itemset.Level + 1; //thanh phan cua 1 tap muc cua k phan tu duoc ket noi //neu (k-2) phan tu dau tien tham gia vao ket noi int count_common_items = (new_candidate_itemset.Level - 2); foreach (ItemsetArrayList itemset in candidate_itemset.Items) { int count_members = 0; foreach (ItemsetArrayList copy_itemset in copy_candidate_itemset) { bool join_items = true; for (count_members = 0; count_members < count_common_items; count_members++) { if (itemset[count_members] != copy_itemset[count_members]) { join_items = false; break; } } If (itemset[count_common_items].ToString().CompareTo(copy_itemset[count_common _items].ToString()) != -1) { join_items = false; } if (join_items == true) { ItemsetArrayList new_itemset = new ItemsetArrayList(1); for (count_members = 0; count_members <= count_common_items; count_members++) { if (itemset[count_members] == copy_itemset[count_members]) 74 { new_itemset.Add(itemset[count_members]); } else { new_itemset.Add(itemset[count_members]); new_itemset.Add(copy_itemset[count_members]); } } new_itemset.Capacity = new_itemset.Count; //lay ra support cho moi tap muc new_itemset.SupportCount = this.SupportCount(new_itemset, transactionsData); new_itemset.Level = new_candidate_itemset.Level; itemset.Capacity = itemset.Count; //Them tap muc vao bang cac tap muc transactionsData.AddItemset(new_itemset, ","); //Khong them cac tap muc neu co support < minsupp if (new_itemset.SupportCount >= minimumSupport) { new_candidate_itemset.Items.Add(new_itemset); } } } } new_candidate_itemset.Items.Capacity = new_candidate_itemset.Items.Count; return new_candidate_itemset; } } //Tao tap cac luat tu cac tap muc public void CreateItemsetRuleset(ItemsetArrayList parentRuleset, ItemsetArrayList leftRuleset, ItemsetArrayList rightRuleset, Database transactionsData) { //Tao va them 1 luat ket hop vao CSDL transactionsData.AddRuleset(parentRuleset, leftRuleset, rightRuleset); } public void CreateItemsetSubsets(int Level, ItemsetArrayList itemSubset, ItemsetArrayList parentItemset, Database transactionsData) { int length = 0; ItemsetArrayList childSubset = new ItemsetArrayList(1); ItemsetArrayList rulesItemset; if (itemSubset.Count > Level) { foreach (ItemsetArrayList item in itemSubset) { 75 ItemsetArrayList[] subsets = this.CreateItemsetSubsets(item); if (parentItemset == null) { parentItemset = item; } if (subsets != null) { length = subsets.Length; } else { break; } for (int count = 0; count < length; count++) { //them tap muc va tap con vao bangAdd the itemset and the subset to the subsets table transactionsData.AddSubset(item, subsets[count]); childSubset.Add(subsets[count]); //Tao 1 tap muc co support, conf va luat ket hop rulesItemset = (parentItemset - subsets[count]); this.CreateItemsetRuleset(parentItemset, subsets[count], rulesItemset, transactionsData); } } childSubset.TrimToSize(); this.CreateItemsetSubsets(0, childSubset, parentItemset, transactionsData); } } public ItemsetArrayList[] CreateItemsetSubsets(ItemsetArrayList itemSubset) { int length = itemSubset.Count; ItemsetArrayList[] subset = new ItemsetArrayList[length]; switch (length) { case 0: { subset = null; break; } case 1: { subset = null; break; } default: { subset[0] = new ItemsetArrayList(1); 76 for (int count = 0; count < (length - 1); count++) { subset[0].Add(itemSubset[count]); } subset[0].TrimToSize(); subset[1] = new ItemsetArrayList(1); for (int count = 1; count < (length); count++) { subset[1].Add(itemSubset[count]); } subset[1].TrimToSize(); for (int count = 1; count < (length - 1); count++) { int position = 0; subset[(count + 1)] = new ItemsetArrayList(1); subset[(count + 1)].Add(itemSubset[position]); for (position = 1; position < length; position++) { if (position != count) { subset[(count + 1)].Add(itemSubset[position]); } } subset[(count + 1)].TrimToSize(); } break; } } return subset; } } } 77 TÀI LIỆU THAM KHẢO Tiếng Việt [1]. Thái Nguyên (29 – 31 tháng 8 năm 2003), Một số vấn đề chọn lọc của công nghệ thông tin, Nhà xuất bản Khoa học Kỹ thuật. [2]. Nguyễn Công Cường, Nguyễn Doãn Phước (2001), Hệ mờ, mạng nơron và ứng dụng - NXB Khoa học Kỹ thuật. [3] Nguyễn Văn Vỵ (2006), Phân tích thiết kế hệ thống, NXB. Đại học Quốc gia Hà Nội. [4]. Đỗ Trung Tuấn (1999), Cơ sở dữ liệu, Nhà xuất bản Giáo dục. [5]. Nguyễn Đình Thúc (1998), Mạng nơron, Nhà xuất bản Giáo dục. Tiếng Anh [6]. John Wiley & Sons (2003) - Data Mining-Concepts Models Methods And Algorithms, Copyright © 2003 The Institute of Electrical and Electronics Engineers, Inc. [7]. Bao Ho Tu (1998), Introduction to Knowledge Discovery and Data mining, Institute of Information Technology National Center for Natural Science and Technology. [8]. Jean – Marc Adamo (2001), Data Mining for Association Rules and Sequential Patterns, Sequential and Parallel Algorithms, Springer – Verlag New York, Inc. [9]. Mohammet J. Zaki and Chin Jui Hasiao CHAM, An efficient Algorithm for Close Itemset Mining. [10]. Jean-Marc Adamo (2001), Data Mining for Association Rule and Sequential Pattens, With 54 Illustrations. ISBN0-95048-6. [11]. John Wiley & Son, Visual Data Mining: Techniques and Tools for Data Visualization and Mining, by Tom Soukup and Ian Davidson, ISBN: 0471149993. [12]. John Wiley & Sons (2003), Data Mining: Concepts, Models, Methods, and Algorithms, by Mehmed Kantardzic, ISBN:0471228524. [13]. W. H. Inmon, R. D. Hackthon, Using the Data Warehouse, A Wiley-QEA Publication. [14]. J.R. Quinlan (1986), Introduction of Decision Trees. Machine learning 1, Kluwer Academic Press,81-106. 78 Địa chỉ trang Web [15] [16] [17] [18] [19] es-4spp.pdf