Nghiên cứu một số phương pháp khai thác dữ liệu và ứng dụng

t là . 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. 1) Ý tưởng thuật giải Tạo các tập 1_itemset: từ các item trên cơ sở dữ liệu, tính độ hỗ trợ cho từng item đưa vào cơ sở dữ liệu đã mã hóa, loại đi các item có độ hỗ trợ nhỏ hơn minsup. Tạo các tập 2_itemset: tính độ hỗ trọ cho tập gồm 2 item dựa và tập C1_N loại đi các item có độ hỗ trợ nhỏ hơn minsup. …. Tạo các tập k_itemset: tính độ hỗ trợ cho tập gồm k item dựa vào tập Ck_1_N loại đi các item có độ hỗ trợ nhỏ hơn minsup. 2) Thuật giải Các khái niệm dùng trong thuật giải AprioriTid cũng tương tự như trong thuật giải Apriori, chỉ thêm tập Ck_N. Thuật giải này là cải tiến của thuật giải Apriori, ở chỗ: sau khi dùng cơ sở dữ liệu D đếm support cho các itemset 1 item tạo ra L1, thuật giải tạo thêm tập Ck_N, dựa vào tập Ck_N này, tính support cho các itemset từ 2 item trở lên tương ứng. Input: Cơ sở dữ liệu giao dịch D, ngưỡng minsup. Output: Các tập phổ biến. Procedure AprioriTid 1. Quét CSDL D để tìm các tập mục phổ biến 1_itemset, L1. 2. C1’ = CSDL D 3. for(k=2; Lk-1≠∅; k++){ 4. Ck=Apriori_Gen(Lk-1, minsup); //sinh ứng cử k-itemset 5. Ck’ = ∅ 6. for(mỗi một tác vụ t∈Ck-1) { 7. Ct = {c ∈ Ck | (c-c[k]) ∈ t.Set_of_ItemSets ^ (c-c[k-1] ∈ t.Set_of_ItemSets} //xác định tập ứng viên trong Ck chứa trong giao dịch với định danh t.Tid 8. for(mỗi một ứng cử c∈Ct) 9. c.count++; 10. if(Ct≠∅) then Ck+= }; //thêm item t vào bảng Ck’ 11. Lk={c∈Ck | c.count ≥ minsup} 12. return L = Uki 1= L1 3) Nhận xét Apriori tốt hơn Apriori_Tid [Agrawal 1994] khi tập cơ sở dữ liệu lớn, còn trong trường hợp khác khi tập Ck tương đối nhỏ thì Apriori_Tid thực hiện tốt hơn Apriori. Thuật giải FP_Growth Thuật giải FP_Growth sử dụng một cấu trúc dữ liệu gọi là FP_tree (Frequent Pattern tree). FP_tree là một thể hiện cô đọng các thông tin có liên quan đến thông tin thể hiện tính thường xuyên của các tập mục trong cơ sở dữ liệu. Mỗi nhánh của cây FP_tree thể hiện một tập mục phổ biến, và các nút dọc theo các nhánh được lưu trữ theo thứ tự giảm dần của tính phổ biến tương ứng với các mục, các mục ở lá của cây có tính phổ biến thấp nhất. Cây FP_tree có một bảng header kết hợp với nó. Bảng header lưu các mục cùng với số lần xuất hiện của nó trong cơ sở dữ liệu theo thứ tự giảm dần của tính phổ biến (mỗi mục chiếm một dòng của bảng). Mỗi mục của bảng chứa một nút đầu danh sách liên kết với tất cả các nút của cây FP_tree mà nút đó có tên trùng với tên của nó. Phương pháp FP_gowth chỉ cần duyệt cơ sở dữ liệu 2 lần để khai phá tất cả các tập mục phổ biến. Quét lần thứ nhất để xác định tần xuất của từng tập mục trong cơ sở dữ liệu. Quét lần thứ hai(lần cuối) để xây dựng cây FP_tree 1) Cấu trúc cây FP Cấu trúc của cây FP_tree: + Gốc cây được tạo với nhãn là null. + Các liên kết trên cây: Liên kết giữa nút có tên mục giống nhau. + Cấu trúc của một nút (trừ nút gốc) gồm các thành phần: - Tên mục - Bộ đếm (counter) - Liên kết (node link) đến nút tiếp theo trên cây có cùng tên mục 2) Xây dựng cây FP Quá trình xây dựng cây FP gồm 2 bước: Bước 1: Quét cơ sở dữ liệu lần thứ nhất, tìm tất cả các mục và tần xuất của nó. Sau đó chèn các mục có độ hỗ trợ lơn hơn hoặc bằng độ hỗ trợ tối thiểu cùng với tần xuất của nó vào bảng Header theo thứ tự giảm dần của tần xuất. Bước 2: Quét cơ sở dữ liệu lần thứ hai, mỗi một giao dịch được quét, loại bỏ mục có độ hỗ trợ nhỏ hơn minsup và sắp xếp lại các mục theo thứ tự giảm dần của tấn xuất. Nếu phần đầu của tập mục giao dịch này không trùng với bất cứ phần đầu của tập mục giao dịch đã xét thì tập hợp các mục đó được chèn vào cây như một nhánh của cây và bộ đếm của mỗi nút ban đầu là 1. Tạo liên kết từ bảng Header đến các mục tương ứng. Nếu tập mục của giao dịch đang xét, có phần đầu trùng với phần đầu của tập mục của một giao dịch nào đó, mà giao dịch này đã được tạo nhánh trên cây, thì phần đầu của tập mục của giao dịch đang xét sẽ được chia sẻ với phần đầu nhánh thể hiện giao dịch đã xét, với mỗi nút trên đoạn nhánh chia sẻ bộ đếm được tăng lên 1 đơn vị, phần còn lại với mỗi mục sẽ được tạo một nút và được nối liền với nhánh được chia sẻ ở phần đầu. Bộ đếm lưu trữ số giao dịch thể hiện bởi nhánh cây xuất phát từ nút gốc đến nút đó. Cây FP_tree chứa đựng tất cả các thông tin về tần xuất của các mục trong cơ sở dữ liệu, việc khai phá cơ sở dữ liệu lúc này trở về khai phá cây FP_tree Thuật giải Input: Cơ sở dữ liệu giao dịch D. Output: Cây FP_tree Procedure Insert_Tree(string[p], Tree có gốc T) 1) If T có nút con N mà N.itemname = p Then N.Count ++ 2) ELSE 3) Tạo nút mới N 4) N.itemname = p, N.Count = 1; 5) Liên kết bảng từ p đến N 6) If p khác rỗng Then 7) Insert_tree(N, p); P: là mục đầu tiên trong danh sách các tập mục P của giao dịch đang xét. 3) Phương pháp tìm tập phổ biến từ cây FP Từ cấu trúc cây FP, xét một số thuộc tính quan trọng: • HeadNodeLink: Nhờ thuộc tính này, khi xét các item phổ biến trong L1, ta có thể truy xuất đến vị trí đầu tiên của nút trong cây có tên giống với tên L1.item. • NodeLink: Nhờ thuộc tính này nên với bất kỳ item phổ biến i thuộc L1, ta có thể xác định được tất cả các tập phổ biến có chứa item I dựa vào các liên kết của nút i trong cây. Thuật giải tìm các tập phổ biến từ cây FP Input: Cây FP. Output: Tập các tập phổ biến. Procedure FrequentItem_FPTree(Tree T) 1) Duyệt L1 theo thứ tự các item có độ hỗ trợ từ thấp đến cao (duyệt ngược lại trong L1) 2) Với mỗi item i ∈L1 3) TimDuongDi (i, SoDD);// Có được MangDuongDi, SoDD 4) TimTapPhoBien (i, MangDuongDi, SoDD) Thủ tục TimDuongDi Mục đích: Tìm tất cả đường đi trong cây có chứa item I, Input: Item I, SoDD = 0 Output: MangDuongDi: là mảng các đường đi trong cây FP có chứa item i. SoDD: số đường đi trong cây có chứa item i. Procedure TimDuongDi (Item i, string MangDuongDi) 1) VT = i.HeadNodeLink; //Từ liên kết HeadNodeLink, xác định được ví trí đầu tiên //của nút có tên item giống i.Item 2) N = nút ở vị trí hiện hành; //Di chuyển đến nút ở vị trí VT trong cây 3) Link = 1 4) j = 1 5) Trong khi Link 0{ 6) Support = N.Support 7) DuongDi = Φ 8) N1 = N 9) Duyệt ngược cây FP từ vị trí VT { 10) If N1.TenNutCha != then 11) DuongDi = DuongDi + N1.TenNutCha 12) VT = Tim(N1.TenNutCha, VT); //Tìm ngược tự vị trí VT trong cây có tên item là //N1.TenNutCha, trả về vị trí tìm được 13) N1 = nút ở vị trí hiện hành) 14) Else 15) Thoát khỏi vòng lặp duyệt cây} 16) MangDuongDi(j) = DaoNguoc(DuongDi) 17) j = j+1 18) Link = N.NodeLink; //Tìm nút gần nhất trong cây có tên cùng tên với nút hiện hành 19) VT = Link 20) Di chuyển đến nút ở vị trí VT trong cây 21) N = nút ở vị trí hiện hành} 22) SoDD = j-1 Thủ tục TimTapPhoBien(Item i, string MangDuongDi, int soDD) Input: i: Item phổ biến một phần tử i. MangDuongDi: các đường đi trong cây chứa item i. SoDD: số đường đi trong cây chứa itm i. Output: Tập các tập phổ biến. Procedure TimTapPhoBien(Item i, string MangDuongDi, int soDD) 1) j = 1 2) t = 1 3) while j <= SoDD{ 4) Với mỗi kết hợp j phần tử trong MangDuongDi{ 5) PhanTuChung = TimPhanTuChung (i, soPTChung) 6) If Support(PhanTuChung) >= Minsup then 7) t = 1 8) do while t<= SoPTChung{ 9) Với mỗi kết hợp t phần tử k = {k1, k2, …k1} 10) Tạo ra tập phổ biến(k, i)}} 11) j = j+1} Thủ tục TimPhanTuChung Nhằm tìm phần tử chung giữa j phần tử trong kết hợp, nếu có item giống nhau thì PhanTuChung = PhanTuChung + Item, Support của PhanTuChung bằng tổng Support của các item trong kết hợp j phần tử này. Nhận xét: Ưu điểm của cây FP: tạo khả năng ứng dụng cho cơ sở dữ liệu lớn, giảm thời gian thực hiện thuật giải Apriori, do: • Cấu trúc dữ liệu đơn giản, đầy đủ. • Giảm số lần duyệt cơ sở dữ liệu. • Xây dựng và tính toán trên cây FP là cơ bản. Bài toán 2: Tìm tập luật. Khám phá các luật kết hợp theo ngưỡng MINCONF cho trước Ý tưởng: Ứng với một frequent itemset l, tìm những tập con khác rỗng của l. Ừng với một tậ con a, ta sẽ đưa ra luật dạng a → (1 - a) nếu tỉ số support (1)/support(a) ≥ minconf. Ta có nhận xét mọi tập con của a đều có độ hỗ trọ lớn hơn hoặc bằng độ hỗ trợ của a. Ví dụ: AB có support là 5, thì A là con của B phải có độ hỗ trợ ≥5. Ta có công thức tính độ tin cậy của một luật dạng a → (1 - a) là: Support(1)/support(a) ≥ minconf. Vì vậy nếu tập a con của l không đưa ra được luật thỏa minconf thì các tập con của a cũng không thể tạo ra một luật thỏa minconf được. 1) Thuật giải 1: Simple algorithm Chúng ta cải tiến thủ tục xử lý bằng cách sinh ra các tập con của mục lớn theo kiểu đệ qui ưu tiên độ sâu. Ví dụ: với tập mục ABCD, đầu tiên chúng ta xét tập con ABC, sau đó đến AB,... Tiếp đến, nếu tập con a của tập mục lớn l không sinh ra được luật thì không cần xét đến các tập con của nó nữa. Chẳng hạn: nếu luật ABC→ D không đủ độ tin cậy thì ta không cần xét đến luật AB→ CD. Điều này có thể chứng minh đơn giản như sau: • Nếu luật a →(l-a) không thoả mãn độ tin cậy, tức là: conf(a→l-a)) nhỏ hơn minconf, thế thì với bất kỳ tập con b nào của a ta có: • Vì b⊂ a nên supp(b)≥supp(a), do vậy: Conf(b→(l-b)) = )sup( )sup( )sup( )sup( a l b l ≤ =conf((a→(l-a))<minconf • Tức là độ tin cậy của luật b→(l-b) cũng nhỏ hơn minconf Thuật giải simple có thể mô tả như sau: ∀ frequent k_itemsets lk, k >= 2 do call GenRules(lk, lk) Thủ tục GenRules Mục đích: phát sinh tất cả các luật hợp lệ dạng a~ => (lk – a~), với a~ ⊂ am Procedure GenRules (lk: frequent k_itemset, am: frequent m_itemset ) 1) A = {(m-1)_itemsets am-1 | am-1 ⊂ am} 2) Forall am-1 ∈A do begin 3) conf = suppport(lk) / support(am-1) 4) if(conf ≥ minconf) then begin 5) output am-1 → (lk - am-1) //với confidence = conf và support = sup(lk) 6) if(m-1>1)then 7) call GenRules(lk, am-1) 8) end 9) end 2) Thuật giải 2: Fast algorithm Thuật giải 2 là cải tiến của thuật giải 1. Ở trên ta đã chỉ ra rằng nếu một luật không thoả mãn với tập cha a thì cũng không thoả mãn với tập con của nó. Ví dụ như trên đã xét: nếu ABC→D không đủ độ tin cậy thì luật AB→CD cũng không đủ độ tin cậy. Điều đó cũng có thể áp dụng theo hướng ngược lại như sau: nếu xảy ra luật với tập con thì cũng xảy ra luật với tập cha. Ví dụ: nếu luật AB→CD có đủ độ tin cậy thì luật ABC→D cũng đủ độ tin cậy. 1) forall frequent k_itemset Lk, k ≥ 2 2) H1 = {Tập vế phải của các luật có 1 item ở vế phải} 3) Call Ap_GenRule(Lk, H1) 4) end Procedure Ap_GenRule (Lk: Frequent k_itemset, Hm: tập vế phải của các luật có m item ở vế phải) if (m+1 < k) then Hm+1 = Apriori_Gen(Hm) với mọi hm+1 ∈ Hm+1 conf = support(Lk) / support(Lk – hm+1) if (conf >= minconf) Xuất ra luật (Lk – hm+1) → ( hm+1) với support là support(Lk), confidence là Conf else xóa hm+1 khỏi Hm+1 endif gọi hàm GenRule(Lk, H1) endif 3) Thuật giải 3: Từ ý tưởng tạo tập luật của phương pháp tạo luật cải tiến: nếu một luật chứa tập a ở vế phải thỏa ngưỡng minconf thì mọi luật chứa a~ ở vế phải cũng thỏa ngưỡng minconf với mọi a~ ⊂ a, ta rút ra nhận xét: nếu như phải tìm tất cả các luật kết hợp có thể có thì chri cần tìm những luật có 1 item ở vế phải là đủ. Tất cả các luật kết hợp có hơn 1 item ở vế phải đều có thể suy ra từ các luật có 1 item ở vế phải mà không cần xét đến cơ sở dữ liệu dùng để khai thác. Ký hiệu s là tập luật gồm tất cả những luật kết hợp có 1 item ở vế phải thỏa ngưỡng minsup và minconf cho trước. Thuật giải tìm tập luật đơn giản S 1. Tìm tất cả các tập frequent itemset thỏa minsup. 2. Đối với từng frequent itemset X: li1, li2, …lik kiểm tra tất cả các luật có vế phải có 1 thuộc tính r: X – lij → lij, j = 1 …k. Nếu thỏa minconf thì cho ra luật r. Tập luật đơn giản là tập các luật mà vế phải có 1 item. Tập luật này chứa đựng tất cả thông tin của tập các luật AR, nhưng có kích thước bé hơn tập AR. Việc khai thác dữ liệu tìm tập luật đơn giản (thay vì AR) là có ích vì các lý do sau: - Số lượng luật cần lưu lại giảm đáng kể, thường giảm từ 10% - 50% nên dễ quản lý. - Giảm đáng kể thời gian và tài nguyên tiêu tốn trong lúc tìm luật khi chỉ tìm luật đơn giản. - Mọi luật kết hợp đều có thể được suy dẫn từ tập luật đơn giản. Vì thế luật kết hợp sẽ được suy dẫn khi có nhu cầu. Nhờ vậy, người dùng chỉ tập trung vào các luật mà họ quan tâm chứ không phải chìm ngập trong tập tất cả các luật kết hợp. Loại luật thừa, tìm tập luật quan tâm 1) Phương pháp dùng quy luật loại bỏ luật thừa Có ba tập luật cần quan tâm. Tập luật kết hợp AR = {X => Y|, sup(X => Y) ≥ minsup và conf(X => Y) ≥ minconf} Đây là tất cả những luật có được do áp dụng thuật giải khia tìm luật kết hợp. Tập luật đặc trưng RR = { (X=>Y) ∈ AR| ¬∃ (X’ => Y’) ∈ AR, (X = X’) ∧ (X ∪Y ⊂ X’ ∪ Y’) ∨ (X X’ ⊃ X ∧ Y = X’ ∪Y’)}. Với luật mọi luật X => Y (được sinh ra từ itemset X ∪Y) đã có trong tập AR, tập luật RR gồm những luật trong tập AR loại bỏ các loại luật như sau: • Luật sinh ra itemset (X’ ∪Y’) chứa itemset (X ∪Y) và có cùng vế trái với luật X => Y. • Luật sinh ra từ (X’ ∪Y’) = (X ∪Y) và luật có vế trái là con của X. Tập luật gồm các luật vế trái nhỏ nhất, vế phải lớn nhất MMR = {r: (X => Y) ∈ AR | ¬∃ r’: (X’ => Y’) ∈ AR, r’ ≠ r và X’⊆ X và Y’ ⊇ Y } Với luật mọi luật X => Y ∈AR, tập MMR gồm những luật trong tập AR loại bỏ luật có tính chất sau: • Luật có vế trái là con của X và có vế phải chứa Y. Đói với ba tập luật kể trên, ta đã chứng minh được mối quan hệ sau: MMR ⊆ RR ⊆ AR Như vậy, tập MMR là tập con của tập luật kết hợp AR đã loại bỏ thành phần thừa. Quan niệm về khái niệm “thừa” được hàm chứa trong việc định nghĩa các tập luật. Thuật giải sau được dùng để tìm tâp luật MMR MMR = AR While (∃ r’: (X’ => Y’) ∈ AR, r’ ≠ r và X’⊆ X và Y’ ⊇ Y) MMR = MMR – rhhhh 2) Phương pháp lọc dùng mẫu đơn giản Lớp các luật IR (hoặc ngay cả các luật vô ích) có thể được mô tả bởi các mẫu (template). Mẫu là một sự tổng quát hóa một lớp các luật kết hợp Một mẫu có dạng như sau: A1,… Ak => Ak+1 Trong đó Ai có thể là tên thuộc tính hoặ là tên của lớp hoặc là một biểu thứ có dạng C+ hoặc C* với C là tên của một lớp. Ở đây, C+ và C* tương ứng với diễn tả “một hoặc nhiều” và “0 hoặc nhiều” thể hiện của lớp C. Luật: B1,… Bh => Bh+1 thỏa mẫu khi luật được xem là thể hiện của mẫu. Phương pháp này dùng cách biểu diễn luật trên sự phân loại mà người dùng định nghĩa dựa trên các thuộc tính của dữ liệu dùng để khai thác luật. Trong phương pháp này, người dùng tự nhập vào tiêu chuẩn của luật cần tìm thông qua mẫu thể hiện luật mà họ quan tâm. C. CÀI ĐẶT CHƯƠNG TRÌNH ỨNG DỤNG Chương trình tổ chức theo hướng đối tượng, được viết bằng ngôn ngữ C#. Cơ sở dữ liệu được tổ chức bằng MS SQL Server 2000. Chương trình cài đặt các thuật giải gom cụm dữ liệu và khai thác luật kết hợp, thực hiện trên bảng dữ liệu điểm của sinh viên khoa Toán tin trường Đại học Đà Lạt với mục đích: • Minh họa hoạt động của các thuật giải. • Tạo tập luật kết hợp làm cơ sở cho việc tư vấn sinh viên chọn chuyên ngành. 1. Tập dữ liệu khai thác: Ứng dụng khai thác trên tập dữ liệu chính: Ký hiệu Mô tả Số thuộc tính Số mẫu tin KhoaTin Điểm của sinh viên khoa Toán Tin Học (ĐHĐL) từ khóa K94 đến K26 20 855 Bảng 1. Tập dữ liệu thực nghiệm • Danh sách các môn học tương ứng với 20 thuộc tính trong cơ sở dữ liệu o Chọn 11 môn học trong các môn học cơ sở o Chọn 3 chuyên ngành, mỗi chuyên ngành chọn 3 môn học. Tên môn học Mã Môn học Chuyên ngành Kỹ Thuật Lập Trình TH201 Cơ Sở Toán Học TN201 Đại Số Đại Cương TN204 Kỹ Thuật Lập Trình Nâng Cao TH202 Phương Pháp Tính TN210 Kiến Trúc Máy Tính TH217 Cấu Trúc Dữ Liệu Và Thuật Toán TH203 Lập Trình Hướng Đối Tượng TH219 Thiết Kế Và Đánh Giá Thuật Toán TH206 Quy Hoạch Tuyến Tính TN213 Truyền Số Liệu TH213 Cơ Sở Dữ Liệu TH214 Hệ thống thông tin Phân Tích Thiết Kế Hệ Thống Thông Tin TH237 Hệ thống thông tin Cơ Sở Dữ Liệu Nâng Cao TH222 Hệ thống thông tin Ngôn Ngữ Lập Trình TH205 Công nghệ phần mềm Nhập Môn Trí Tuệ Nhân Tạo TH209 Công nghệ phần mềm Công Nghệ Phần Mềm TH212 Công nghệ phần mềm Mạng Máy Tính TH211 Mạng - Truyền thông Lập Trình Mạng TH234 Mạng - Truyền thông Thiết Kế Đánh Giá Hiệu Suất Mạng TH227 Mạng - Truyền thông Bảng 2: Bảng các môn học 2. Tổ chức chương trình Toàn bộ ứng dụng được xây dựng theo mô hình hướng đối tượng, chia làm 7 project nhỏ. ™ Project Common: • Configs: chứa các lớp cấu hình, các thông số mặc định như đường dẫn file, loại file, … • Constants: chứa tập các hằng số • Enums: chứa các kiểu tập hợp (enum)… cho toàn ứng dụng. ™ Project Framework: • Exceptions: chứa các lớp quản lý ngoại lệ như kết nối dữ liệu, chuyển đổi kiểu dữ liệu, ngoại lệ phát sinh từ các lớp khai thác dữ liệu, … • Data: chứa các lớp truy xuất dữ liệu từ tập tin XML và chuỗi hóa các đối tượng để lưu trữ vào các tập tin. • IOTools: Công cụ truy xuất dữ liệu từ các tập tin dạng text. • Utils: chứa lớp chuyển đổi qua lại giữa các kiểu dữ liệu cơ sở ™ Project DataEngine: • DMParameter: lớp mở rộng để tùy biến các tham số dùng khi truy xuất cơ sở dữ liệu. • DataProvider: lớp cung cấp các chức năng nhằm tối ưu và tiết kiệm thời gian xử lý việc truy xuất cơ sở dữ liệu. Đây là lớp trực tiếp tạo kết nối và thực thi các truy vấn đến cơ sở dữ liệu. ™ Project DataAccess: • Đây là project truy xuất cơ sở dữ liệu và khởi tạo các đối tượng phục vụ cho ứng dụng khai thác dữ liệu sau này. • BaseClasses: Chứa các lớp cơ sở, định nghĩa các đối tượng liên quan tương ứng với các bảng trong cơ sở dữ liệu. • Entities: Chứa các lớp kế thừa từ các lớp trong không gian tên BaseClasses để mở rộng khả năng thực thi code và quản lý hiệu quả. • DBDirect: Chứa các lớp sử dụng đối tượng DataProvider để trực tiếp truy xuất dữ liệu. Mỗi lớp có đầy đủ các chức năng thêm, xóa, cập nhật và truy vấn, tùy vào từng tình huống sử dụng cụ thể. ™ Project DataMiningCore: • Đây là project chứa tất cả các lớp cốt lõi phục vụ cho chương trình gom nhóm và khai thác luật kết hợp. • Interfaces: Chứa các interface như IDataBlock, ICopyable, ITreeNode… • Library: đây là thư viện chứa các lớp hỗ trợ cho các thuật toán gom nhóm và khai thác luật. Chẳng hạn: hàng đợi ưu tiên (PriorityQueue), lớp xử lý các phép toán trên ma trận (Matrix), lớp chứa tập dữ liệu cần khai thác (RecordSet)… • Supporter: Chứa các lớp phục vụ việc thống kê số liệu • Filters: Chứa các bộ lọc giá trị bị thiếu, chuẩn hóa dữ liệu. • Utils: Chứa các lớp chuyển đổi dữ liệu (TotalConverter) qua lại giữa các đối tượng trong Library và xử lý số thực, chuỗi, các phép toán trên mảng (LibTool), … • Clusterers: Chứa các lớp xử lý các thuật toán gom nhóm dữ liệu. • Associations: Chứa các lớp xử lý các thuật toán khai thác luật kết hợp. ™ Project WindowGUI: Đây là chương trình thực thi việc gom nhóm và khai thác luật kết hợp trên giao diện Windows Form. • AssociationRules: Chứa các form khai thác luật kết hợp • KDDTasks: Chứa các form đọc dữ liệu và gom nhóm. • Visualizers: Chứa các đồ thị biểu diễn kết quả gom nhóm và khai thác luật ™ Project ConsultantWeb: • Đây là ứng dụng tư vấn chọn ngành cho sinh viên và chọn khối thi cho các học sinh cuối cấp (các trường PTTH). • Home.aspx: Trang chủ, dùng để lấy thông tin từ người dùng • Register.aspx: Trang xác nhận thông tin từ người dùng • TestPieChart.aspx: Trang hiển thị kết quả tư vấn bằng biểu đồ. 3. Kết quả thử nghiệm: • Cấu hình máy tính sử dụng khi khai thác: o Hệ quản trị cơ sở dữ liệu MS SQL Server 2000 o Bộ nhớ trong (RAM): 3 GB o Bộ vi xử lý: Core 2 Duo 2.66 GHz o Hệ điều hành Windows XP Professional • Thực hiện trên bảng KhoaTin gồm 20 thuộc tính và 855 giao dịch 3.1 Kết quả thực thi gom nhóm: Tập dữ liệu Thuật giải Tham số 1 Tham số 2 Thời gian thực thi (giây) Số cluster KhoaTin Classic K-Means K = 5 # 1.263 5 Heuristic K-Means K = 5 # 1.173 5 DBSCAN MinPts = 5 Eps = 1.13846875719587 45.25 1 OPTICS MinPts = 10 Eps = 1.13259780053547 56.34 1 Bảng 3. Kết quả thực thi gom nhóm 3.2 Kết quả thực thi khai thác luật kết hợp Cơ sở dữ liệu Thuật toán tìm tập phổ biến Thuật toán sinh luật Thời gian tìm tập phổ biến (giây) Thời gian sinh luật (giây) Tổng thời gian (giây) KhoaTin (minsup = 50, minconf = 50) Apriori Simple 00:01:35 01:22:36 01:24:11 Fast 00:01:35 01:19:54 01:21:29 MMR 00:01:35 01:20:12 01:21:47 AprioriTid Simple 00:27:24 00:11:31 00:38:55 Fast 00:28:09 00:06:56 00:35:05 MMR 00:28:50 00:06:58 00:35:48 FP-Growth Simple 00:00:00 00:06:05 00:06:05 Fast 00:00:00 00:06:00 00:06:00 MMR 00:00:00 00:06:02 00:06:02 Bảng 4. Kết quả khai thác luật trước khi gom cụm 3.3 Các tập luật - Gom cụm bằng thực hiện thuật giải DBSCAN - Khai thác luật và rút gọn luật trên các cụm bằng thuật giải FP-Growth và MMR. - Kết quả tập luật trình bày luật dưới dạng P -> Q, với Q chứa các môn chuyên ngành, Q chứa các môn cơ sở. 1.Kết quả tập luật với vế phải chứa các môn chuyên ngành. MINSUPP = 0.10 MINCONF = 0.35 a. Công nghệ phần mềm: Luật Độ tin cậy TH201-Gioi --> TH205-Kha,TH217-TB 42.51% TH201-Gioi --> TH212-Gioi 46.86% TH201-Kha --> TH205-Gioi 40.66% TH201-Kha --> TH205-TB 41.08% TH201-Kha --> TH209-Gioi 35.68% TH201-Kha --> TH209-Kha 37.76% TH201-Kha --> TH212-Kha 43.98% TH201-Kha --> TH212-TB 37.34% TH201-TB --> TH202-TB,TH205-TB 39.63% TH201-TB --> TH202-TB,TH212-TB 47.37% TH201-TB --> TH205-TB,TH212-TB 40.25% TH201-TB --> TH209-Kha 45.82% TH201-TB,TH202-TB --> TH209-Kha 46.6% TH201-TB,TH202-TB --> TH212-TB,TH213-TB 42.72% TH202-Gioi --> TH209-Kha 39.37% TH202-Gioi --> TH212-TB 40.27% TH202-Kha --> TH205-Gioi 41.42% TH202-Kha --> TH209-Gioi 36.4% TH202-Kha --> TH212-Kha 49.79% TH202-TB --> TH201-TB,TH212-TB 41.24% TH202-TB --> TH205-TB,TH212-TB 37.2% TH202-TB --> TH209-Kha 45.01% TH202-TB --> TH209-TB 35.31% TH203-Gioi --> TH205-TB 44.91% TH203-Gioi --> TH209-Kha 43.52% TH203-Gioi --> TH212-TB 44.91% TH203-Kha --> TH209-Kha 42.36% TH203-Kha --> TH212-TB 38.86% TH203-TB --> TH205-TB 40.88% TH203-TB --> TH209-Kha 35.91% TH203-TB --> TH209-TB 35.36% ( . . . xem phụ lục) b. Hệ thống thông tin Luật Độ tin cậy TH201-Gioi --> TH214-TB 50.24% TH201-Gioi --> TH222-TB 55.07% TH201-Gioi --> TH237-TB 53.62% TH201-Kha --> TH214-TB 43.98% TH201-Kha --> TH222-Kha 37.34% TH201-Kha --> TH222-TB 44.81% TH201-Kha --> TH237-TB 58.09% TH201-TB --> TH202-TB,TH237-TB 37.04% TH201-TB --> TH214-TB 40.74% TH201-TB --> TH222-Kha 35.19% TH201-TB --> TH222-TB 45.06% TH201-TB,TH202-TB --> TH222-TB 44.66% TH202-Gioi --> TH222-Kha 41.63% TH202-Gioi --> TH222-TB 43.89% TH202-Gioi --> TH237-TB 49.32% TH202-Kha --> TH214-TB 51.46% TH202-Kha --> TH222-TB 53.14% TH202-Kha --> TH237-TB 61.09% TH202-TB --> TH214-TB 41.51% TH202-TB --> TH222-TB 48.79% TH202-TB --> TH237-TB 57.95% TH202-TB,TH203-TB --> TH237-TB 57.58% TH202-TB,TH213-TB --> TH214-TB 46.63% TH202-TB,TH213-TB --> TH222-TB 52.88% TH202-TB,TH217-TB --> TH222-TB,TN201-TB 51.15% TH203-Gioi --> TH214-Kha 40.28% TH203-Gioi --> TH222-TB 42.13% TH203-Gioi --> TH237-TB 62.5% TH203-Kha --> TH214-TB 38.26% TH203-Kha --> TH222-TB 49.57% ( . . . xem phụ lục) c. Mạng – Truyền thông Luật Độ tin cậy TH201-Gioi --> TH211-TB 46.08% TH201-Gioi --> TH227-TB 49.02% TH201-Kha --> TH211-TB 38.84% TH201-Kha --> TH227-TB 42.98% TH201-Kha --> TH234-TB 49.17% TH201-TB --> TH211-Kha 35.91% TH201-TB --> TH211-TB 35.6% TH201-TB --> TH227-TB 41.8% TH201-TB --> TH234-TB 43.03% TH201-TB,TH202-TB --> TH227-TB 42.72% TH202-Gioi --> TH211-Kha 40.45% TH202-Gioi --> TH227-TB 40.45% TH202-Gioi --> TH234-TB 41.36% TH202-Kha --> TH211-TB 41.18% TH202-Kha --> TH227-TB 47.9% TH202-Kha --> TH234-TB 47.48% TH202-TB --> TH211-TB 39.62% TH202-TB --> TH227-TB 43.94% TH202-TB --> TH234-TB 42.32% TH202-TB,TH213-TB --> TH211-TB 43.75% TH202-TB,TH213-TB --> TH227-TB 46.63% TH202-TB,TH213-TB --> TH234-TB 43.75% TH202-TB,TH217-TB --> TH234-TB 50% TH203-Gioi --> TH227-TB 48.39% TH203-Kha --> TH211-TB 38.77% TH203-Kha --> TH227-TB 44.49% TH203-Kha --> TH234-TB 41.85% TH203-TB --> TH211-TB 42.11% TH203-TB --> TH227-TB 43.77% TH203-TB --> TH234-TB 47.09% ( . . . xem phụ lục) 2. Minh họa khai thác luật để tư vấn: a. Dạng tư vấn về khả năng học một môn học chuyên ngành: • TH201-Gioi --> TH212-Gioi 46.86% Nếu Kỹ thuật lập trình giỏi thì khả năng môn Công nghệ phần mềm giỏi với độ tin cậy 46.86% • TH201-Kha --> TH205-Gioi 40.66% Nếu Kỹ thuật lập trình khá thì khả năng môn Ngôn ngữ lập trình giỏi với độ tin cậy 40.66% b. Tư vấn chọn ngành: Qui định học giỏi (Khá, trung bình) một chuyên ngành thì kết quả các môn chuyên ngành phải giỏi (Khá, trung bình) • Muốn học chuyên ngành Hệ thống thông tin loại Khá, các môn sau phải đạt : Môn học Học lực Kỹ Thuật Lập Trình Khá trở lên Kỹ Thuật Lập Trình Nâng Cao Giỏi Truyền Số Liệu Khá trở lên Kiến Trúc Máy Tính Khá trở lên Lập Trình Hướng Đối Tượng Khá trở lên Cơ Sở Toán Học Khá trở lên Đại Số Đại Cương Giỏi Phương Pháp Tính Khá trở lên Quy Hoạch Tuyến Tính Khá trở lên Cấu Trúc Dữ Liệu Và Thuật Toán Giỏi Thiết Kế Và Đánh Giá Thuật Toán Khá trở lên • Muốn học chuyên ngành Công nghệ phần mềm loại Giỏi, các môn sau phải đạt: Môn học Học lực Kỹ Thuật Lập Trình Khá trở lên Kỹ Thuật Lập Trình Nâng Cao Khá trở lên Truyền Số Liệu Giỏi Lập Trình Hướng Đối Tượng Giỏi Cơ Sở Toán Học Khá trở lên Đại Số Đại Cương Khá trở lên Phương Pháp Tính Trung bình trở lên Quy Hoạch Tuyến Tính Trung bình trở lên Tài liệu tham khảo [1] Michael J. A. Berry, Gordon S. Linoff (2004), “Data Mining Techniques”, Wiley Publishing, inc. [2] Jiawei Han, Michelin Kamber (2000), “ Data Mining: Conceps and Techiniques”, Morgan Kaufmann Publishers [3] David hand, Heikki Mannila, Padhraic Smyth (2001), “ Principle of Data Miming”, Massachusetts Institute technology [04] Lê Hoài Bắc, Võ Đình Bảy (2007), “Khai thác luật kết hợp không dư thừa”, Kỷ yếu hội thảo Quốc gia một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông lần thứ X, Nhà Xuất bản Khoa học và Kỹ thuật, Hà Nội. [5] Daniel T. Larose (2006), “ Data Mining Methods and Models ”, Wiley Publishing, inc. Phần 4: KẾT LUẬN VÀ KIẾN NGHỊ A. KẾT LUẬN Trong quá trình thực hiện nghiên cứu đề tài, chúng tôi đã có một số kết quả cụ thể sau đây: 1. Cải tiến thuật giải phân lớp của Daijin Kim (kết quả nghiên cứu khoa học đã được công bố) : Tiếp cận tập thô dung sai theo cách của Daijin Kim để giải quyết bài toán phân lớp dữ liệu. Phân lớp dữ liệu theo 2 giai đoạn: Giai đoạn 1 sử dụng công cụ tập xấp xỉ dưới để phân lớp dữ liệu. Giai đoạn 2 được tiến hành cho các mục dữ liệu không phân lớp được trong giai đoạn 1 bằng cách sử dụng công cụ tập xấp xỉ trên và hàm thành viên thô. Đề tài đưa ra một cải tiến cho thuật giải phân lớp theo 2 giai đoạn nêu trên. Từ nhận xét phải sử dụng tập xấp xỉ trên )(YAτ khi tiến hành phân lớp trong giai đoạn 2, tác giả đã chỉ ra một tập thực sự nhỏ hơn, đó là )(YAτ với )()()( YYY A A A τττ ⊆⊆ , đồng thời cho một ví dụ chứng tỏ )()( YY AA ττ ⊂ là bất đẳng thức nghiêm cách. 2. Đưa ra các thuật giải tìm tập luật rút gọn (kết quả nghiên cứu khoa học đã được công bố) : Các tác giả đưa ra các thuật giải tìm tập luật rút gọn và tập luật hệ quả được suy ra theo hai qui tắc đơn giản “hiểu được theo nghĩa lôgic” thông thường từ các tập phổ biến được xây dựng từ dàn đóng các thuộc tính. Cơ sở của các thuật giải này dựa trên việc phân lớp các tập con thuộc tính và lớp các luật kết hợp thành các lớp tương đương rời nhau có cùng độ hỗ trợ và độ tin cậy tương ứng theo các quan hệ tương đương. Điều này giúp hạn chế khá nhiều việc lưu trữ, tìm kiếm và tính lại các độ hỗ trợ và độ tin cậy thừa trong các thuật giải. Không gian các luật kết hợp sẽ được phân hoạch thành hai lớp rời nhau theo hai cách: tập luật gốc đóng và tập luật hệ quả không đóng; hoặc tập luật rút gọn và tập luật hệ quả hiểu được theo nghĩa lôgic. 3. Hệ thống một số thuật giải gom cụm dữ liệu và khai thác luật kết hợp (báo cáo kỹ thuật dạng tìm hiểu, tổng quan) Đối với lĩnh vực gom cụm dữ liệu, đã phân tích, mô tả và cài đặt minh họa các thuật giải K-Means, K-Means song song, DBSCAN. . . Đối với phương pháp khai thác luật kết hợp, đã phân tích, mô tả và cài đặt minh họa các thuật giải: Apriori, AprioriTid, FP-Growth, Simple, Fast, MMR . 4. Ứng dụng (dạng chương trình minh họa): - Tổ chức cơ sở dữ liệu thử nghiệm về sinh viên khoa Toán Tin trường Đại học Đà lạt bằng hệ quản trị cơ sở dữ liệu MS SQL Server 2000. - Cài đặt chương trình bằng ngôn ngữ C# trong môi trường .Net - Chương trình minh họa các thuật giải tương ứng với các bộ dữ liệu trên, đồng thời đưa ra tập các luật kết hợp làm cơ sở tư vấn cho sinh viên chọn chuyên ngành học. B. KIẾN NGHỊ Sử dụng các bài viết báo cáo kỹ thuật và các kết quả nghiên cứu mới trong đề tài làm giáo trình cho các học phần trong chuyên ngành Khoa học máy tính tại khoa Công nghệ thông tin, Đại học Đà Lạt, hoặc viết sách khảo cứu về lĩnh vực khai thác dữ liệu. TÀI LIỆU THAM KHẢO [01] Trần Tuấn Minh (2007), “Về một thuật giải phân lớp dữ liệu dựa vào tập thô dung sai”, Kỷ yếu Hội thảo quốc gia “Một số vấn đề về Công nghệ thông tin và truyền thông ” lần thứ IX, Trang 405 – 414, Nhà xuất bản Khoa học và Kỹ thuật, Hà Nội [02] Trương Chí Tín, Trần Ngọc Anh, Trần Tuấn Minh (2007), “Thuật toán khai thác luật kết hợp rút gọn từ dàn” , “Thông báo Khoa học” của trường Đại học Đà Lạt năm 2007, trang 193 – 206 [03] Lê Hoài Bắc, Võ Đình Bảy (2007), “Khai thác luật kết hợp không dư thừa”, Kỷ yếu hội thảo Quốc gia một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông lần thứ X, Nhà Xuất bản Khoa học và Kỹ thuật, Hà Nội [04] Jan Komorowski, Lech Polkowski, Andrzej Skowron, “Rough Sets : A Tutorial”. [05] G. Birkhoff (1948), Lattice theory, American Mathematical Society, New York [06] Michael J. A. Berry, Gordon S. Linoff (2004), “Data Mining Techniques”, Wiley Publishing, inc. [07] Jiawei Han, Michelin Kamber (2000), “ Data Mining: Conceps and Techiniques”, Morgan Kaufmann Publishers [08] David hand, Heikki Mannila, Padhraic Smyth (2001), “ Principle of Data Miming”, Massachusetts Institute technology [09] Daniel T. Larose (2006), “ Data Mining Methods and Models ”, Wiley Publishing, inc. [10] Hussein A Abbass, Ruhul A. Sarker, Charles S. Newton (2002), “Data Mining : A Heuristic Approach”, Idea Group Publishing. [11] Daijin Kim (2001), “Data Classification Based On Tolerant Rough Set”, Pattern Recognition, 34, 1613 -1624. [12] Jan Komorowski, Lech Polkowski, Andrzej Skowron, “Rough Sets : A Tutorial”. [13] L. Polkowski, A. Skowron, Knowledge system Group, “Learning Tolerance Relations by Boolean Descriptors: Automatic Feature Extraction from Data Tables”. [14] Matteo Magnani (2003), “Technical Report on Rough Set Theory for Knowledge Discovery in Databases” [15] R. Agrawal, R. Srikant (1994), “Fast algorithms for mining association rules”, Proceedings of the 20th Very Large Data Bases Conferenre Santiago, Chile, pages 478-499, June 1994. [16] H. T. Bao (1995),”An approach to concept formation based on formal concept analysis”, IEICE trans. Information and systems, vol. E78-D, No 5, May 1995. [17] R. Godin, R. Missaoul, Hassn Alaour (1995), “Incremental concept formation algorithms based on Galois lattices”, Magazine of computational Intelligence, pp 246-247 [18] N. Pasquier, Y. Bastide, R. Taouil and L. Lakhal (1999), “Efficient Mining of association rules using closed item set lattices”, Information systems, Vol. 24, No. 1, pp 25-46 [19] N. Pasquier, R. Taouil, Y. Bastide, G.Stumme and L. Lakhal (2005), “Generating a condensed representation for association rules”, J. of Intelligent Information Systems, Vol. 24, No. 1, pp 29-60 [20] Đ. Phúc (2002), Luận án tiến sĩ, ĐHQG TP HCM [21] R. Wille (182), “Restructuring lattice theory: An approach based on hierarchies of concepts”, in Ordered sets, I.Rival (Ed.), Reidel, pp. 445-470 [22] R. Wille (1992), Concept lattives and conceptual knowledge systems, Computers and . Mathematics with Applications, Vol. 23, pp. 493-515 [23] R. Wille (1989), “Lattice in data analysis: how to draw them with a computer”, in Algorithms and order, NATO ASI Series 147, Reidel, pp. 33- 58 [24] M. J. Zaki,S. Parthasarathy, M. Ogihara (1997), W. Li, “New algorithms for fast discovery of association rules”, Technical report 651, The University of Rochester, New York [25] PHỤ LỤC (Tập luật khai thác) a. Công nghệ phần mềm (132 luật): Luật Độ tin cậy TH201-Gioi --> TH205-Kha,TH217-TB 42.51% TH201-Gioi --> TH212-Gioi 46.86% TH201-Kha --> TH205-Gioi 40.66% TH201-Kha --> TH205-TB 41.08% TH201-Kha --> TH209-Gioi 35.68% TH201-Kha --> TH209-Kha 37.76% TH201-Kha --> TH212-Kha 43.98% TH201-Kha --> TH212-TB 37.34% TH201-TB --> TH202-TB,TH205-TB 39.63% TH201-TB --> TH202-TB,TH212-TB 47.37% TH201-TB --> TH205-TB,TH212-TB 40.25% TH201-TB --> TH209-Kha 45.82% TH201-TB,TH202-TB --> TH209-Kha 46.6% TH201-TB,TH202-TB --> TH212-TB,TH213-TB 42.72% TH202-Gioi --> TH209-Kha 39.37% TH202-Gioi --> TH212-TB 40.27% TH202-Kha --> TH205-Gioi 41.42% TH202-Kha --> TH209-Gioi 36.4% TH202-Kha --> TH212-Kha 49.79% TH202-TB --> TH201-TB,TH212-TB 41.24% TH202-TB --> TH205-TB,TH212-TB 37.2% TH202-TB --> TH209-Kha 45.01% TH202-TB --> TH209-TB 35.31% TH203-Gioi --> TH205-TB 44.91% TH203-Gioi --> TH209-Kha 43.52% TH203-Gioi --> TH212-TB 44.91% TH203-Kha --> TH209-Kha 42.36% TH203-Kha --> TH212-TB 38.86% TH203-TB --> TH205-TB 40.88% TH203-TB --> TH209-Kha 35.91% TH203-TB --> TH209-TB 35.36% TH203-TB --> TH212-TB 43.37% TH203-TB,TH206-TB --> TH205-TB 50.58% TH203-TB,TH217-TB --> TH209-TB 45.1% TH206-Gioi --> TH209-Kha 46.67% TH206-Gioi --> TH212-TB 41.43% TH206-Kha --> TH209-Kha 40.85% TH206-Kha --> TH212-TB 44.68% TH206-TB --> TH205-TB 49.74% TH206-TB --> TH209-Kha 35.68% TH206-TB --> TH212-TB 44.79% TH206-TB,TH213-TB --> TH205-TB 63.3% TH206-TB,TH213-TB --> TH205-TB,TH219-TB 46.28% TH206-TB,TH213-TB --> TH212-TB 50% TH206-TB,TH213-TB,TH219-TB --> TH205-TB 69.05% TH206-TB,TH219-TB --> TH205-TB 56.06% TH206-TB,TH219-TB --> TH205-TB,TH213-TB 43.94% TH206-TB,TH219-TB --> TH212-TB 44.95% TH206-TB,TN204-TB --> TH205-TB 47.54% TH206-TB,TN210-TB --> TH205-TB 53.62% TH206-TB,TN210-TB --> TH212-TB 49.28% TH206-TB,TN213-TB --> TH205-TB 52.88% TH213-Gioi --> TH205-Gioi 54.71% TH213-Gioi --> TH209-Kha 41.26% TH213-Kha --> TH205-TB 45.64% TH213-Kha --> TH209-Kha 44.81% TH213-Kha --> TH212-TB 51.45% TH213-TB --> TH205-TB 47.35% TH213-TB --> TH209-Kha 35.45% TH213-TB --> TH212-TB 46.3% TH213-TB,TH219-TB --> TH205-TB 50.44% TH213-TB,TH219-TB --> TH205-TB,TH206-TB 38.5% TH213-TB,TH219-TB --> TH212-TB 48.23% TH213-TB,TN210-TB --> TH205-TB 51.52% TH213-TB,TN210-TB --> TH212-TB 46.46% TH213-TB,TN213-TB --> TH205-TB 47.69% TH213-TB,TN213-TB --> TH212-TB 49.23% TH217-Gioi --> TH205-TB 42.73% TH217-Gioi --> TH209-Kha 45.91% TH217-Gioi --> TH212-TB 49.55% TH217-Kha --> TH205-TB 43.83% TH217-Kha --> TH209-Kha 51.91% TH217-Kha --> TH212-TB 47.23% TH217-TB --> TH205-Kha 37.28% TH217-TB --> TH205-TB 36.76% TH217-TB --> TH209-TB 42.16% TH217-TB --> TH212-TB 37.79% TH217-TB,TN201-TB --> TH209-TB 46.83% TH217-TB,TN201-TB --> TH212-TB 44.88% TH219-Gioi --> TH205-Gioi 38.25% TH219-Gioi --> TH209-Kha 38.65% TH219-Gioi --> TH212-TB 39.44% TH219-Kha --> TH205-TB 42.86% TH219-Kha --> TH209-Kha 43.67% TH219-Kha --> TH209-TB 35.92% TH219-Kha --> TH212-TB 49.8% TH219-TB --> TH205-TB 44.31% TH219-TB --> TH209-Kha 38.02% TH219-TB --> TH212-TB 44.01% TH219-TB,TN210-TB --> TH205-TB 50% TH219-TB,TN213-TB --> TH205-TB 45.19% TH219-TB,TN213-TB --> TH212-TB 45.19% TN201-Gioi --> TH205-TB 42.15% TN201-Gioi --> TH209-Kha 48.43% TN201-Gioi --> TH212-TB 55.16% TN201-Kha --> TH205-TB 42.74% TN201-Kha --> TH209-Gioi 36.75% TN201-Kha --> TH209-Kha 37.18% TN201-Kha --> TH212-Kha 49.15% TN201-TB --> TH205-TB 39.14% TN201-TB --> TH209-Kha 37.92% TN201-TB --> TH209-TB 39.45% TN201-TB --> TH212-TB 47.4% TN204-Gioi --> TH201-TB,TH212-TB 39.92% TN204-Gioi --> TH205-TB 41.09% TN204-Gioi --> TH209-Kha 51.94% TN204-Kha --> TH205-TB 39.02% TN204-Kha --> TH209-Gioi 35.61% TN204-Kha --> TH209-Kha 37.88% TN204-Kha --> TH212-TB 43.56% TN204-TB --> TH205-TB 41.14% TN204-TB --> TH212-Kha 38.29% TN210-Gioi --> TH205-TB 43.54% TN210-Gioi --> TH212-TB 46.89% TN210-Kha --> TH205-TB 36.61% TN210-Kha --> TH209-Kha 51.57% TN210-Kha --> TH212-TB 44.88% TN210-TB --> TH205-TB 42.18% TN210-TB --> TH209-Gioi 37.43% TN210-TB --> TH212-TB 42.18% TN210-TB,TN213-TB --> TH205-TB 45.77% TN210-TB,TN213-TB --> TH212-TB 43.78% TN213-Kha --> TH205-TB 41.13% TN213-Kha --> TH209-Kha 43.97% TN213-Kha --> TH209-TB 35.82% TN213-Kha --> TH212-TB 50% TN213-TB --> TH205-TB 42.77% TN213-TB --> TH209-Gioi 35.84% TN213-TB --> TH209-Kha 36.99% TN213-TB --> TH212-Kha 35.26% TN213-TB --> TH212-TB 41.91% b. Hệ thống thông tin (139 luật) Luật Độ tin cậy TH201-Gioi --> TH214-TB 50.24% TH201-Gioi --> TH222-TB 55.07% TH201-Gioi --> TH237-TB 53.62% TH201-Kha --> TH214-TB 43.98% TH201-Kha --> TH222-Kha 37.34% TH201-Kha --> TH222-TB 44.81% TH201-Kha --> TH237-TB 58.09% TH201-TB --> TH202-TB,TH237-TB 37.04% TH201-TB --> TH214-TB 40.74% TH201-TB --> TH222-Kha 35.19% TH201-TB --> TH222-TB 45.06% TH201-TB,TH202-TB --> TH222-TB 44.66% TH202-Gioi --> TH222-Kha 41.63% TH202-Gioi --> TH222-TB 43.89% TH202-Gioi --> TH237-TB 49.32% TH202-Kha --> TH214-TB 51.46% TH202-Kha --> TH222-TB 53.14% TH202-Kha --> TH237-TB 61.09% TH202-TB --> TH214-TB 41.51% TH202-TB --> TH222-TB 48.79% TH202-TB --> TH237-TB 57.95% TH202-TB,TH203-TB --> TH237-TB 57.58% TH202-TB,TH213-TB --> TH214-TB 46.63% TH202-TB,TH213-TB --> TH222-TB 52.88% TH202-TB,TH217-TB --> TH222-TB,TN201-TB 51.15% TH203-Gioi --> TH214-Kha 40.28% TH203-Gioi --> TH222-TB 42.13% TH203-Gioi --> TH237-TB 62.5% TH203-Kha --> TH214-TB 38.26% TH203-Kha --> TH222-TB 49.57% TH203-Kha --> TH237-TB 49.13% TH203-TB --> TH214-TB,TH217-TB 35.36% TH203-TB --> TH217-TB,TH222-TB 37.57% TH203-TB --> TH237-TB 56.08% TH206-Gioi --> TH214-Kha 43.27% TH206-Gioi --> TH222-TB 41.35% TH206-Gioi --> TH237-TB 51.92% TH206-Kha --> TH214-Kha 38.72% TH206-Kha --> TH222-TB 53.62% TH206-Kha --> TH237-TB 43.4% TH206-TB --> TH213-TB,TH237-TB 35.32% TH206-TB --> TH214-TB,TH217-TB 35.06% TH206-TB --> TH214-TB,TH237-TB 37.66% TH206-TB --> TH219-TB,TH237-TB 35.32% TH206-TB --> TH222-TB 49.61% TH206-TB --> TH237-TB,TN210-TB 39.22% TH206-TB --> TH237-TB,TN213-TB 35.32% TH206-TB,TH213-TB --> TH222-TB 52.91% TH206-TB,TH217-TB --> TH214-TB,TN204-TB 49.19% TH206-TB,TN210-TB --> TH222-TB 50.97% TH206-TB,TN213-TB --> TH222-TB 46.89% TH213-Gioi --> TH214-TB 42.6% TH213-Gioi --> TH222-Kha 42.6% TH213-Gioi --> TH222-TB 38.57% TH213-Gioi --> TH237-TB 58.3% TH213-Kha --> TH214-Kha 47.7% TH213-Kha --> TH214-TB 39.75% TH213-Kha --> TH222-TB 51.88% TH213-Kha --> TH237-TB 53.97% TH213-TB --> TH206-TB,TH237-TB 35.88% TH213-TB --> TH214-TB 45.91% TH213-TB --> TH222-TB 52.51% TH213-TB,TH219-TB --> TH214-TB 47.35% TH213-TB,TN210-TB --> TH214-TB 45.45% TH213-TB,TN210-TB --> TH222-TB 56.06% TH213-TB,TN213-TB --> TH214-TB 47.45% TH213-TB,TN213-TB --> TH222-TB 50% TH217-Gioi --> TH237-TB 55.25% TH217-Kha --> TH222-Kha 39.57% TH217-Kha --> TH237-TB 54.89% TH217-TB --> TH214-TB,TH222-TB 37.02% TH217-TB --> TH222-TB,TH237-TB 38.82% TH219-Gioi --> TH214-Kha 42.23% TH219-Gioi --> TH214-TB 36.25% TH219-Gioi --> TH222-Kha 39.04% TH219-Gioi --> TH222-TB 43.03% TH219-Gioi --> TH237-TB 52.99% TH219-Kha --> TH214-Kha 40.57% TH219-Kha --> TH214-TB 38.11% TH219-Kha --> TH222-TB 52.05% TH219-Kha --> TH237-TB 59.43% TH219-TB --> TH206-TB,TH237-TB 40.6% TH219-TB --> TH213-TB,TH222-TB 36.12% TH219-TB --> TH213-TB,TH237-TB 38.51% TH219-TB --> TH214-TB 51.34% TH219-TB --> TH237-TB,TN210-TB 35.52% TH219-TB,TN210-TB --> TH214-TB 47.89% TH219-TB,TN213-TB --> TH214-TB 49.52% TN201-Gioi --> TH222-TB 39.46% TN201-Gioi --> TH237-TB 57.4% TN201-Kha --> TH214-TB 40.6% TN201-Kha --> TH222-Kha 41.45% TN201-Kha --> TH222-TB 44.87% TN201-Kha --> TH237-TB 56.84% TN201-TB --> TH202-TB,TH222-TB 36% TN201-TB --> TH214-TB 47.08% TN201-TB --> TH217-TB,TH222-TB 41.23% TN201-TB --> TH217-TB,TH237-TB 37.23% TN204-Gioi --> TH214-Kha 37.11% TN204-Gioi --> TH222-Kha 37.11% TN204-Gioi --> TH222-TB 42.58% TN204-Gioi --> TH237-TB 53.91% TN204-Kha --> TH222-TB 43.18% TN204-Kha --> TH237-TB 52.27% TN204-TB --> TH206-TB,TH214-TB 39.43% TN204-TB --> TH206-TB,TH222-TB 35.65% TN204-TB --> TH206-TB,TH237-TB 40.06% TN204-TB --> TH214-TB,TH217-TB 41.96% TN204-TB --> TH214-TB,TH222-TB 38.8% TN204-TB --> TH214-TB,TH237-TB 37.85% TN204-TB --> TH217-TB,TH222-TB 40.06% TN204-TB --> TH217-TB,TH237-TB 39.12% TN204-TB --> TH222-TB,TH237-TB 38.49% TN210-Gioi --> TH214-Kha 51.66% TN210-Gioi --> TH222-TB 51.18% TN210-Gioi --> TH237-TB 54.98% TN210-Kha --> TH214-Kha 35.04% TN210-Kha --> TH214-TB 41.73% TN210-Kha --> TH222-Kha 42.91% TN210-Kha --> TH222-TB 43.7% TN210-Kha --> TH237-TB 50% TN210-TB --> TH206-TB,TH237-TB 42.54% TN210-TB --> TH213-TB,TH237-TB 36.62% TN210-TB --> TH214-TB 47.32% TN210-TB --> TH222-TB 48.73% TN210-TB,TN213-TB --> TH214-TB 46.77% TN210-TB,TN213-TB --> TH222-TB 45.27% TN213-Gioi --> TH222-TB 48.13% TN213-Gioi --> TH237-TB 58.88% TN213-Kha --> TH214-Kha 41.28% TN213-Kha --> TH214-TB 40.57% TN213-Kha --> TH222-Kha 35.59% TN213-Kha --> TH222-TB 50.18% TN213-Kha --> TH237-TB 56.58% TN213-TB --> TH206-TB,TH237-TB 39.19% TN213-TB --> TH214-TB 49.86% TN213-TB --> TH222-Kha 35.73% TN213-TB --> TH222-TB 46.69% TN213-TB --> TH237-TB,TN210-TB 35.73% c. Mạng – Truyền thông (150 luật) TH201-Gioi --> TH211-TB 46.08% TH201-Gioi --> TH227-TB 49.02% TH201-Kha --> TH211-TB 38.84% TH201-Kha --> TH227-TB 42.98% TH201-Kha --> TH234-TB 49.17% TH201-TB --> TH211-Kha 35.91% TH201-TB --> TH211-TB 35.6% TH201-TB --> TH227-TB 41.8% TH201-TB --> TH234-TB 43.03% TH201-TB,TH202-TB --> TH227-TB 42.72% TH202-Gioi --> TH211-Kha 40.45% TH202-Gioi --> TH227-TB 40.45% TH202-Gioi --> TH234-TB 41.36% TH202-Kha --> TH211-TB 41.18% TH202-Kha --> TH227-TB 47.9% TH202-Kha --> TH234-TB 47.48% TH202-TB --> TH211-TB 39.62% TH202-TB --> TH227-TB 43.94% TH202-TB --> TH234-TB 42.32% TH202-TB,TH213-TB --> TH211-TB 43.75% TH202-TB,TH213-TB --> TH227-TB 46.63% TH202-TB,TH213-TB --> TH234-TB 43.75% TH202-TB,TH217-TB --> TH234-TB 50% TH203-Gioi --> TH227-TB 48.39% TH203-Kha --> TH211-TB 38.77% TH203-Kha --> TH227-TB 44.49% TH203-Kha --> TH234-TB 41.85% TH203-TB --> TH211-TB 42.11% TH203-TB --> TH227-TB 43.77% TH203-TB --> TH234-TB 47.09% TH203-TB,TH206-TB --> TH234-TB 59.3% TH203-TB,TH217-TB --> TH211-TB 46.31% TH203-TB,TH217-TB --> TH227-TB 47.78% TH203-TB,TH217-TB --> TH234-TB 56.65% TH203-TB,TN213-TB --> TH234-TB 63.09% TH206-Kha --> TH211-Gioi 37.02% TH206-Kha --> TH227-Kha 47.23% TH206-Kha --> TH227-TB 39.15% TH206-TB --> TH211-Kha 36.72% TH206-TB --> TH211-TB 46.09% TH206-TB --> TH227-TB 49.48% TH206-TB --> TH234-TB 54.17% TH206-TB,TH213-TB --> TH211-TB 51.32% TH206-TB,TH213-TB --> TH227-TB 52.38% TH206-TB,TH213-TB --> TH234-TB 53.97% TH206-TB,TH217-TB --> TH211-TB 59.02% TH206-TB,TH217-TB --> TH227-TB 60.66% TH206-TB,TH217-TB --> TH234-TB 68.31% TH206-TB,TH219-TB --> TH211-TB 48.22% TH206-TB,TH219-TB --> TH227-TB 52.79% TH206-TB,TN201-TB --> TH234-TB 61.07% TH206-TB,TN204-TB --> TH211-TB 54.89% TH206-TB,TN210-TB --> TH211-TB 47.83% TH206-TB,TN210-TB --> TH227-Gioi 42.03% TH206-TB,TN210-TB --> TH227-TB 47.83% TH206-TB,TN210-TB --> TH234-TB 48.79% TH206-TB,TN213-TB --> TH211-TB 46.89% TH206-TB,TN213-TB --> TH227-TB 54.07% TH206-TB,TN213-TB --> TH234-TB 57.89% TH213-Gioi --> TH211-TB 42.27% TH213-Gioi --> TH227-TB 43.18% TH213-Gioi --> TH234-TB 45.45% TH213-Kha --> TH211-Kha 43.98% TH213-Kha --> TH227-Kha 46.47% TH213-Kha --> TH227-TB 39.83% TH213-Kha --> TH234-TB 39% TH213-TB --> TH211-TB 45.91% TH213-TB --> TH227-TB 48.81% TH213-TB --> TH234-TB 45.91% TH213-TB,TH217-TB --> TH211-TB 56.68% TH213-TB,TH217-TB --> TH227-TB 57.75% TH213-TB,TH217-TB --> TH234-TB 52.94% TH213-TB,TH219-TB --> TH211-TB 45.58% TH213-TB,TH219-TB --> TH227-TB 48.67% TH213-TB,TN204-TB --> TH211-TB 60.84% TH213-TB,TN210-TB --> TH211-TB 48.99% TH213-TB,TN210-TB --> TH227-TB 45.96% TH213-TB,TN213-TB --> TH211-TB 46.94% TH213-TB,TN213-TB --> TH227-TB 52.04% TH213-TB,TN213-TB --> TH234-TB 52.55% TH217-Gioi --> TH211-Kha 39.09% TH217-Kha --> TH227-TB 40.6% TH217-TB --> TH211-TB 49.48% TH217-TB --> TH227-Kha 36.08% TH217-TB --> TH227-TB 50.26% TH217-TB --> TH234-TB 52.58% TH217-TB,TH219-TB --> TH211-TB 56.79% TH217-TB,TH219-TB --> TH227-TB 59.88% TH217-TB,TN201-TB --> TH211-TB 44.88% TH217-TB,TN201-TB --> TH227-TB 45.37% TH217-TB,TN201-TB --> TH234-TB 49.76% TH217-TB,TN204-TB --> TH211-TB 54.36% TH217-TB,TN210-TB --> TH211-TB 58.23% TH217-TB,TN210-TB --> TH234-TB 56.33% TH217-TB,TN213-TB --> TH211-TB 58.54% TH217-TB,TN213-TB --> TH227-TB 62.8% TH217-TB,TN213-TB --> TH234-TB 65.85% TH219-Gioi --> TH211-Kha 36.4% TH219-Gioi --> TH211-TB 35.2% TH219-Gioi --> TH227-TB 43.6% TH219-Gioi --> TH234-TB 37.2% TH219-Kha --> TH227-Kha 43.67% TH219-Kha --> TH227-TB 40% TH219-Kha --> TH234-TB 39.59% TH219-TB --> TH211-Kha 35.74% TH219-TB --> TH211-TB 44.74% TH219-TB --> TH227-TB 49.25% TH219-TB --> TH234-TB,TN213-TB 35.44% TH219-TB,TN210-TB --> TH227-TB 47.37% TH219-TB,TN213-TB --> TH211-TB 45.19% TH219-TB,TN213-TB --> TH227-TB 51.92% TN201-Gioi --> TH227-TB 41.7% TN201-Kha --> TH211-TB 40.95% TN201-Kha --> TH227-TB 47.41% TN201-Kha --> TH234-TB 42.24% TN201-TB --> TH211-TB 40.18% TN201-TB --> TH227-Kha 36.81% TN201-TB --> TH227-TB 41.72% TN201-TB --> TH234-TB 47.85% TN204-Gioi --> TH227-Kha 39.22% TN204-Gioi --> TH234-Gioi 36.08% TN204-Gioi --> TH234-TB 35.69% TN204-Kha --> TH227-TB 39.02% TN204-Kha --> TH234-TB 38.26% TN204-TB --> TH206-TB,TH234-TB 35.96% TN204-TB --> TH211-Kha 35.96% TN204-TB --> TH211-TB 50.79% TN204-TB --> TH217-TB,TH227-TB 39.43% TN204-TB --> TH217-TB,TH234-TB 37.85% TN210-Gioi --> TH227-Kha 55.5% TN210-Kha --> TH211-Kha 39.13% TN210-Kha --> TH211-TB 39.53% TN210-Kha --> TH227-TB 47.04% TN210-Kha --> TH234-TB 46.64% TN210-TB --> TH211-TB 44.54% TN210-TB --> TH227-Gioi 36.69% TN210-TB --> TH227-TB 46.5% TN210-TB --> TH234-TB 45.1% TN210-TB,TN213-TB --> TH211-TB 44% TN210-TB,TN213-TB --> TH227-TB 48.5% TN210-TB,TN213-TB --> TH234-TB 50.5% TN213-Gioi --> TH211-TB 41.78% TN213-Gioi --> TH234-Kha 43.19% TN213-Kha --> TH227-Kha 42.2% TN213-Kha --> TH227-TB 44.68% TN213-Kha --> TH234-TB 36.52% TN213-TB --> TH211-Kha 35.84% TN213-TB --> TH211-TB 43.64% TN213-TB --> TH227-TB 51.16% TN213-TB --> TH234-TB 54.62%