Tóm tắt Luận án Rút gọn thuộc tính trong bảng quyết định không đầy đủ theo tiếp cận tập thô dung sai

ion) trên U. Ta có, .    a PSIM P SIM a  1.3. Bảng quyết định không đầy đủ Bảng quyết định là một hệ thông tin DS với tập thuộc tính A được chia thành hai tập khác rỗng rời nhau C và D , lần lượt được gọi là tập thuộc tính điều kiện và tập thuộc tính quyết định. Tức là với  ,DS U C D  .C D  Xét bảng quyết định với giả thiết , đầy  ,DS U C D  ,u U d D     d u đủ giá trị, nếu tồn tại và sao cho thiếu giá trị thì DS được u U c C  c u gọi là bảng quyết định không đầy đủ, trái lại DS được gọi là bảng quyết định đầy đủ. Ta biểu diễn bảng quyết định không đầy đủ là với  ,IDS U C D  . Không mất tính chất tổng quát, giả thiết D chỉ gồm một thuộc , '* ' dd D V   tính quyết định duy nhất .  d 1.4. Tập rút gọn và tập lõi Định nghĩa 1.2 Cho hệ thông tin không đầy đủ . Ta nói rằng  ,IIS U A thuộc tính là không cần thiết (dispensable) trong A nếu a A ; ngược lại, a được gọi là cần thiết (indispensable)     / /U SIM A U SIM A a  trong A. Tập tất cả các thuộc tính cần thiết trong A được gọi là tập lõi của A. Khi đó, thuộc tính cần thiết chính là thuộc tính lõi. Định nghĩa 1.3 Cho hệ thông tin không đầy đủ . Tập thuộc tính  ,IIS U A là một tập rút gọn của A nếu và với mọi , R A    / /U SIM R U SIM A r R .    / /U SIM R r U SIM A  Hiển nhiên, A có nhiều tập rút gọn. Khi đó, tập lõi của A là giao của tất cả các tập rút gọn của A. 5Kết luận chương 1 Chương 1 đã trình bày một số khái niệm cơ bản trong mô hình tập thô dung sai do Kryszkiewicz đề xuất và một số khái niệm cơ bản về tập rút gọn và tập lõi trong hệ thông tin không đầy đủ và bảng quyết định không đầy đủ. Các khái niệm này được sử dụng trong chương 2 và chương 3 của luận án. Chương 2. PHÂN NHÓM VÀ ĐÁNH GIÁ CÁC PHƯƠNG PHÁP RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ 2.1. Mở đầu Chương này trình bày các kết quả nghiên cứu sau đây: 1) Phân nhóm các phương pháp rút gọn thuộc tính trong bảng quyết định không đầy đủ dựa vào nghiên cứu mối liên hệ giữa các khái niệm tập rút gọn. 2) Đánh giá các phương pháp rút gọn thuộc tính dựa vào nghiên cứu sự thay đổi các độ đo đánh giá hiệu năng tập luật quyết định trên các khái niệm tập rút gọn. 2.2. Phân nhóm các phương pháp rút gọn thuộc tính Tiêu chí phân nhóm là: các phương pháp có tập rút gọn như nhau được phân thành một nhóm. Các kết quả trong phần này đã được tác giả công bố trong tài liệu [1]. 2.2.1. Các khái niệm tập rút gọn trong bảng quyết định không đầy đủ Kryszkiewicz M và các cộng sự đã đư ra khái niệm tập rút gọn của IDS dựa trên hàm quyết định suy rộng ( ), Zuqiang Meng và các cộng sự R đưa ra khái niệm về tập rút gọn dựa trên miền dương ( ), Huang B và các PR cộng sự đưa ra khái niệm về tập rút gọn dựa trên lượng thông tin (information quantity)( ). Tác giả trước đã đưa ra khái niệm về tập rút IR gọn dựa trên metric( ), Huasheng ZOU và cộng sự đưa ra khái niệm tập DR rút gọn dựa trên ma trận phân biệt( ). Công trình trước tác giả đưa ra MR khái niệm tập rút gọn dựa trên ma trận dung sai( ), ngoài ra, trong các TMR công trình khác, các tác giả đưa ra khái niệm tập rút gọn phân bố (distribution reduct)( ), tập rút gọn ấn định (assignment reduct)( ).R R Kết quả nghiên cứu về mối liên hệ giữa các khái niệm tập rút gọn như sau: 61) Nếu bảng quyết định nhất quán, các tác giả đã chỉ ra , , , PR R R R là như nhau về định nghĩa độ đo. 2) Nếu bảng quyết định không nhất quán, Renpu Li và cộng sự đã chứng minh và là như nhau về định nghĩa độ đo. Huasheng ZOU và R R cộng sự đã chứng minh và như nhau về định nghĩa độ đo.R MR 2.2.2. Mối liên hệ giữa các khái niệm tập rút gọn , , DR IR TMR Mệnh đề 2.1. Cho bảng quyết định không đầy đủ và .   ,IDS U A d  R A Khi đó khi và chỉ khi            , ,E Ed K R K R d d K A K A d   .     I R d I A d Mệnh đề 2.2. Cho bảng quyết định không đầy đủ , và   ,IDS U A d  R A là ma trận dung sai của IDS. Khi đó i j n nTM m     khi và chỉ khi với mọi            , ,E Ed K R K R d d K A K A d   i jR m  .i jm   2.2.3. Mối liên hệ giữa và R PR Mệnh đề 2.3. Cho bảng quyết định không đầy đủ và .   ,IDS U A d  R A Nếu với mọi thì .   R Au u   u U      R APOS d POS d 2.2.4. Mối liên hệ giữa và DR R Mệnh đề 2.4. Cho bảng quyết định không đầy đủ và .   ,IDS U A d  R A Nếu thì .           , ,E Ed K R K R d d K A K A d      , R Au U u u     2.2.5. Mối liên hệ giữa và R R Mệnh đề 2.5. Cho bảng quyết định không đầy đủ và .   ,IDS U A d  R A Nếu thì .   , R Au U u u       , R Au U u u     2.2.6. Phân nhóm các phương pháp rút gọn thuộc tính Nếu bảng quyết định nhất quán, các tập rút gọn , , , , , , PR R R MR DR IR , là như nhau.TMR R Nếu bảng quyết định không nhất quán, mối liên hệ giữa các tập rút gọn trong các nhóm như sau:  PR MRRR ,,  TMID RRR ,, R   7 Nếu là một tập rút gọn thuộc Nhóm 3 thì tồn tại một tập rút gọn 3R thuộc Nhóm 2 và một tập rút gọn thuộc Nhóm 1 sao cho 2R 1R .1 2 3R R R   Nếu là một tập rút gọn thuộc Nhóm 4 thì tồn tại một tập rút gọn 4R thuộc Nhóm 2 và một tập rút gọn thuộc Nhóm 1 sao cho 2R 1R .1 2 4R R R  2.3. Đánh giá các phương pháp rút gọn thuộc tính Chúng tôi đề xuất các độ đo mới và nghiên cứu sự thay đổi giá trị các độ đo đề xuất trên các tập rút gọn nhằm đánh giá các phương pháp rút gọn thuộc tính. Các kết quả trong phần này đã được tác giả công bố trong tài liệu [2]. 2.3.1. Luật quyết định và các độ đo đánh giá hiệu năng Yuhua Qian và các cộng sự, đã đưa ra độ chắc chắn, độ nhất quán và độ hỗ trợ của tập luật trong bảng quyết định không đầy đủ dựa trên khái niệm khối đồng nhất cực đại. Điểm hạn chế lớn nhất của công trình này là các tác giả chưa đánh giá được sự thay đổi giá trị của các độ đo này trên các tập rút gọn. 2.3.2. Đề xuất các độ đo mới đánh giá hiệu năng tập luật quyết định Cho bảng quyết định không đầy đủ với và   ,IDS U A d   1,..., nU u u tập luật với .      :ij ij A i jRULE Z Z des S u des Y       / , / , 1.. , 1..A i jS u U SIM A Y U d i n j m    Độ chắc chắn của IDS được định nghĩa .    1 1 1 1 iNn A i j i ji A i S u Y IDS n N S u       Độ nhất quán của IDS được định nghĩa     1 1 1 1 1 1 1 iNn A i j i ji A i S u Y IDS n N nS u        Độ hỗ trợ của IDS được định nghĩa     1 1 1 n m A i j i j S u Y IDS n n      Ký hiệu là số luật quyết định (số lớp quyết định) sinh bởi lớp dung iN sai . A iS u 8Mệnh đề 2.6. Cho hai bảng quyết định không đầy đủ ,   ,IDS U A d  và với ,   ' ,IDS U B d       :ij ij A i jRULE Z Z des S u des Y       / , /A i jS u U SIM A Y U d  , . Nếu thì , , 1..i n 1..j m B A    'IDS IDS     'IDS IDS     'IDS IDS  2.3.3. Nghiên cứu sự thay đổi giá trị các độ đo đề xuất trên các tập rút gọn Mệnh đề 2.7. Cho hai bảng quyết định không đầy đủ và   ,IDS U A d  .   ' ,IDS U B d  a) Nếu IDS nhất quán và B là một tập rút gọn miền dương ( ) thì PR , ,    ' 1IDS IDS      ' 1IDS IDS      'IDS IDS  b) Nếu IDS không nhất quán và B là một tập rút gọn miền dương ( ) PR thì , ,    'IDS IDS     'IDS IDS     'IDS IDS  Như vậy, tập rút gọn miền dương ( ) làm giảm độ chắc chắn, giảm PR độ nhất quán và tăng độ hỗ trợ của tập luật đối với bảng quyết định không đầy đủ không nhất quán. Mệnh đề 2.8. Cho hai bảng quyết định không đầy đủ và   ,IDS U A d  . Nếu B là một tập rút gọn dựa trên hàm quyết định suy   ' ,IDS U B d  rộng ( ) thìR , ,    'IDS IDS     'IDS IDS     'IDS IDS  Như vậy, tập rút gọn dựa trên hàm quyết định suy rộng ( ) bảo toàn R độ chắc chắn, độ nhất quán và tăng độ hỗ trợ của tập luật quyết định. Mệnh đề 2.9. Cho hai bảng quyết định không đầy đủ và   ,IDS U A d  . Nếu B là một tập rút gọn dựa trên khoảng cách ( ) thì   ' ,IDS U B d  DR , ,    'IDS IDS     'IDS IDS     'IDS IDS  Mệnh đề 2.10. Cho hai bảng quyết định không đầy đủ và   ,IDS U A d  . Nếu B là một tập rút gọn phân bố ( ) thì   ' ,IDS U B d  R , ,    'IDS IDS     'IDS IDS     'IDS IDS  92.3.4. Thử nghiệm sự thay đổi giá trị các độ đo đề xuất trên các tập rút gọn Bảng 2.5. Kết quả thử nghiệm sự thay đổi các độ đo đánh giá hiệu năng 1 Thuật toán POSBAR Thuật toán GDBAR STT Bộ số liệu U C R    R    1 Hepatitis.data 155 19 3 0.909 0.819 0.598 3 0.909 0.819 0.504 2 Lung-cancer.data 32 56 4 1 1 0.814 4 1 1 0.814 3 Automobile.data 205 25 4 0.825 0.702 0.708 6 0.915 0.781 0.624 4 Anneal.data 798 38 6 0.804 0.713 0.586 7 0.852 0.755 0.503 5 Congressional Voting Records 435 16 15 1 1 0.616 15 1 1 0.616 6 Credit Approval 690 15 3 0.716 0.708 0.786 5 0.884 0.802 0.615 Bảng 2.6. Kết quả thử nghiệm sự thay đổi các độ đo đánh giá hiệu năng 2 Thuật toán MBAR Thuật toán DFBAR STT Bộ số liệu U C R    R    1 Hepatitis.data 155 19 4 0.909 0.819 0.415 5 0.909 0.819 0.402 2 Lung-cancer.data 32 56 4 1 1 0.814 4 1 1 0.814 3 Automobile.data 205 25 8 0.915 0.781 0.518 8 0.915 0.781 0.518 4 Anneal.data 798 38 9 0.852 0.755 0.426 10 0.852 0.755 0.406 5 Congressional Voting Records 435 16 15 1 1 0.616 15 1 1 0.616 6 Credit Approval 690 15 7 0.884 0.802 0.487 6 0.884 0.802 0.512 Hình 2.1 sau đây biểu diễn sự thay đổi của độ hỗ trợ  trên 6 bộ số liệu được chọn đối với các thuật toán: Thuật toán POSBAR, Thuật toán GDBAR, Thuật toán MBAR, Thuật toán DFBAR. 10 Hình 2.1. Sự thay đổi độ hỗ trợ  trên các tập rút gọn 2.3.5. Lựa chọn, đánh giá các phương pháp rút gọn thuộc tính 1) Lựa chọn nhóm phương pháp phù hợp 1) Tập rút gọn , tập rút gọn , tập rút gọn và tập rút gọn đều PR R DR R bảo toàn độ chắc chắn của tập luật đối với bảng quyết định không đầy đủ nhất quán. 2) Tập rút gọn làm giảm độ chắc chắc của tập luật đối với bảng PR quyết định không đầy đủ không nhất quán 3) Tập rút gọn , tập rút gọn và tập rút gọn đều bảo toàn độ R DR R chắc chắn của tập luật đối với bảng quyết định không đầy đủ không nhất quán. 2) Đánh giá các phương pháp Với bảng quyết định không đầy đủ nhất quán, các tập rút gọn tốt nhất của bốn nhóm phương pháp là như nhau nên chúng có chất lượng phân lớp như nhau. Với bảng quyết định không nhất quán, chúng tôi đánh giá ba nhóm phương pháp phù hợp (Nhóm 2, Nhóm 3, Nhóm 4) dựa trên tiêu chuẩn chất lượng phân lớp tập rút gọn của nhóm phương pháp. Giả sử là một tập rút gọn tốt nhất của các phương pháp thuộc esDB tR Nhóm 3 ( tìm được bởi thuật toán heuristic sử dụng khoảng cách, esDB tR lượng thông tin hay ma trận dung sai). Theo kết quả nghiên cứu về mỗi liên hệ giữa các tập rút gọn đã trình bày, tồn tại một tập rút gọn dựa trên hàm quyết định suy rộng sao cho ( tối thiểu hơn ). R esDB tR R  R esDB tR 11 Giả sử là một tập rút gọn tốt nhất của các phương pháp thuộc esB tR Nhóm 2 ( tìm được bởi thuật toán heuristic sử dụng hàm quyết định esB tR suy rộng, tập rút gọn ấn định hay ma trận phân biệt). Ta có hai trường hợp. - Nếu chính là ( ) thì , nghĩa là tối thiểu esB tR R esB tR R  es esB t DB tR R  esB tR hơn . Theo Mệnh đề 2.6, độ hỗ trợ của tập luật dựa trên cao hơn esDB tR esB tR độ hỗ trợ của tập luật dựa trên , hay có chất lượng phân lớp tốt esDB tR esB tR hơn .esDB tR - Nếu khác thì có chất lượng phân lớp tốt hơn do esB tR R esB tR R esB tR có chất lượng phân lớp tốt nhất. Mặt khác, do nên tốt hơn esDB tR R  R esDB tR về chất lượng phân lớp. Do đó, tốt hơn về chất lượng phân lớp.esB tR esDB tR Do đó, trong cả hai trường hợp có chất lượng phân lớp tốt hơn esB tR . Từ đó kết luận các phương pháp thuộc Nhóm 2 hiệu quả hơn các esDB tR phương pháp thuộc Nhóm 3 theo tiêu chuẩn đánh giá chất lượng phân lớp của tập rút gọn. Tương tự như trên ta có các phương pháp thuộc Nhóm 2 hiệu quả hơn các phương pháp thuộc Nhóm 4 theo tiêu chuẩn đánh giá chất lượng phân lớp của tập rút gọn. Các phương pháp thuộc Nhóm 3 không so sánh được với các phương pháp thuộc Nhóm 4 do tập rút gọn và tập rút gọn không có mối quan DR R hệ. 2.4. Kết luận chương 2 Chương 2 luận án đã thực hiện các nội dung nghiên cứu sau: (1) Phân nhóm các phương pháp rút gọn thuộc tính trong bảng quyết định không đầy đủ không nhất quán dựa vào kết quả nghiên cứu mối liên hệ giữa các khái niệm tập rút gọn, mối liên hệ giữa các tập rút gọn của các nhóm phương pháp. Dựa trên tập rút gọn, các phương pháp được phân thành bốn nhóm: Nhóm 1 (Tập rút gọn miền dương ), Nhóm 2 (tập rút PR gọn dựa trên hàm quyết định suy rộng , tập rút gọn ấn định , tập rút R R gọn dựa trên ma trận phân biệt ), Nhóm 3 (tập rút gọn dựa trên lượng MR thông tin , tập rút gọn dựa trên ma trận dung sai , tập rút gọn dựa trên IR TMR 12 khoảng cách ), Nhóm 4 (Tập rút gọn phân bố ). Kết quả này được DR R công bố trong công trình [1]. (2) Đề xuất các độ đo mới đánh giá hiệu năng tập luật quyết định (độ chắc chắn, độ nhất quán, độ hỗ trợ). Nghiên cứu sự thay đổi giá trị các độ đo đề xuất trên các tập rút gọn của bốn nhóm phương pháp. Trên cơ sở đó, lựa chọn và đánh giá các phương pháp rút gọn thuộc tính dựa trên tiêu chuẩn chất lượng phân lớp của tập rút gọn. Kết quả này được công bố trong công trình [2]. Chương 3. ĐỀ XUẤT CÁC PHƯƠNG PHÁP RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ 3.1. Mở đầu Trong chương này, trước hết chúng tôi giải quyết bài toán rút gọn dữ liệu bằng đề xuất phương pháp chọn tập đối tượng đại diện. Sau đó, chúng tôi đề xuất phương pháp sử dụng lượng thông tin mở rộng và phương pháp sử dụng hàm quan hệ. Chúng tôi chứng minh rằng cả 2 phương pháp này đều thuộc Nhóm 2 (theo phân nhóm phương pháp đã trình bày ở Chương 2). 3.2. Chọn tập đối tượng đại diện cho bài toán rút gọn thuộc tính 3.2.1. Chọn tập đối tượng đại diện cho hệ thông tin không đầy đủ Thuật toán 3.1. Chọn tập đối tượng đại diện của hệ thông tin không đầy đủ. Đầu vào: Hệ thông tin không đầy đủ với ,  ,IIS U A  1,..., nU u u  maaA ,...,1 Đầu ra: Hệ thông tin không đầy đủ đại diện với . AUIIS PP , UU P  Bước 1: Đặt ;PU Bước 2: Với mỗi , tính với miAai ..1,       / ii aU a u u U  .           i ii a aau v U S u S v   Bước 3: Tính với .   UuuAU A  //           im amiaaA uuuu 1...1   Giả sử và với . kXXAU ,...,/ 1  1 ,..., li i iX u u 1..i k Bước 4: Với mọi , , đặt ;,/ AUX i  1..i k  1:P P iU U u  Bước 5: Return ; AUIIS PP , 13 3.2.2. Chọn tập đối tượng đại diện cho bảng quyết định không đầy đủ Thuật toán 3.2. Chọn tập đối tượng đại diện của bảng quyết định không đầy đủ. Đầu vào: Bảng quyết định không đầy đủ với   ,IDS U A d  ,  1,..., nU u u  maaA ,...,1 Đầu ra: Bảng quyết định không đầy đủ đại diện với   ,p pIDS U A d  .PU U Bước 1: Đặt ;PU   Bước 2: Với mỗi , tính với miAai ..1,       / ii aU a u u U  .           i ii a aau v U S u S v   Bước 3: Tính với   UuuAU A  //           im amiaaA uuuu 1...1   Giả sử ; kXXAU ,...,/ 1 Bước 4: Với mỗi , , thực hiện lặp các bước 4.1 và 4.2 ,/ AUX i  1..i k như sau: Bước 4.1. Tính với . Giả sử      /i idX d u u X         idu v X d u d v   và với .   1/ ,...,i lX d Y Y  1 ,..., oj j jY u u 1..j l Bước 4.2. Với mỗi , , đặt ; /j iY X d 1..j l  1:P P jU U u  Bước 5: Return ;  ,p pIDS U A d  3.3. Phương pháp rút gọn thuộc tính sử dụng lượng thông tin mở rộng 3.3.1. Độ đo lượng thông tin mở rộng Cho hệ thông tin đầy đủ , với , giả sử  AUIS ,  nuuU ,...,1 là phân hoạch sinh bởi tập thuộc tính . Khi đó, lượng  kPPPU ,...,/ 1 AP  thông tin mở rộng của P trên tập đối tượng U, ký hiệu là , được tính  UPEI , bằng tổng khoảng cách Jaccard trung bình giữa tập U và như sau: iP (3.1)   1 1 1 1 1, 1 1 1 k k i i i ii U P P EI P U k U P k U k                  3.3.2. Xây dựng lượng thông tin mở rộng có điều kiện Cho bảng quyết định không đầy đủ và với   dAUIDS  ,  nuuU ,...,1 ta có là một phủ của U. Khi đó, ta xây AP      niUuuSPSIMU iip ..1,/  14 dựng lượng thông tin mở rộng có điều kiện (conditional extended information quantity) của tập thuộc tính P đối với thuộc tính , ký hiệu  d là , là trung bình cộng các lượng thông tin mở rộng thành phần   CEI P d của thuộc tính trên các tập đối tượng , . Giả sử  d  ip uS     , P iEI d S u với là số lớp tương đương của phân hoạch .      1, 1P i P i EI d S u k   ipk    duS ip / Khi đó ta có: (3.2)        1 1 1 1 1 1 1 1, 1 1 n n n P i i i i i iP P CEI P d EI d S u n n k n k             Cho bảng quyết định không đầy đủ và , với   dAUIDS  ,  nuuU ,...,1 ta có là một phủ của U. ta xây dựng AP      niUuuSPSIMU iip ..1,/  lượng thông tin mở rộng có điều kiện của tập thuộc tính P và thuộc tính quyết định , ký hiệu là , là trung bình cộng các lượng thông  d   CEI P d tin mở rộng thành phần của thuộc tính trên các tập đối tượng ,  d  ip uS Giả sử với là số lớp tương đương của     , P iEI d S u      1, 1P i P i EI d S u k   ipk phân hoạch . Khi đó ta có:   duS ip / (3.2)        1 1 1 1 1 1 1 1, 1 1 n n n P i i i i i iP P CEI P d EI d S u n n k n k             3.3.3. Rút gọn thuộc tính sử dụng lượng thông tin mở rộng có điều kiện Định nghĩa 3.1. Cho bảng quyết định không đầy đủ và tập   dAUIDS  , thuộc tính . Nếu R A 1)      CEI R d CEI A d 2)         ,r R CEI R r d CEI A d    thì R là một tập rút gọn của A dựa trên lượng thông tin mở rộng có điều kiện. 15 Định nghĩa 3.2. Cho bảng quyết định không đầy đủ ,   dAUIDS  , AB  và . Độ quan trọng của thuộc tính b đối với tập thuộc tính B được BAb  định nghĩa bởi:         BSIG b CEI B d CEI B b d   Thuật toán 3.3 (Thuật toán EIQBAR). Thuật toán heuristic tìm một tập rút gọn sử dụng lượng thông tin mở rộng có điều kiện. Đầu vào: Bảng quyết định không đầy đủ   dAUIDS  , Đầu ra: Một tập rút gọn .R 1. ;R 2. Tính lượng thông tin mở rộng có điều kiện và ;  CEI R d   CEI A d // Thêm vào R các thuộc tính có độ quan trọng lớn nhất 3. While do     CEI R d CEI A d 4. Begin 5. For tính ;RAa          RSIG a CEI R d CEI R a d   6. Chọn sao cho ; RAam      aSIGMaxaSIG RRAamR  7. ; maRR  8. Tính ;  CEI R d 9. End; //Loại bỏ các thuộc tính dư thừa trong R nếu có 10. For each doRa 11. Begin 12. Tính ;   CEI R a d 13. If then ;      CEI R a d CEI R d   aRR  14. End; 15. Return ;R Xét vòng lặp While từ dòng lệnh 3 đến 9, để tính ta cần phải  aSIGR tính phải tính vì đã được tính ở bước trước, nghĩa    CEI R a d   CEI R d là cần phải tính và phân hoạch . Theo Zhang và các   iaR uS      duS iaR / cộng sự [9], độ phức tạp để tính với mọi khi đã được   iaR uS  Uui   iR uS tính là , độ phức tạp để tính phân hoạch với mọi là  2UO     duS iaR / Uui  16 . Do đó, độ phức tạp thời gian để tính tất cả các ở dòng lệnh  2UO  aSIGR số 5 là:        2 2 2 21 ... 1 * * / 2 *A A U A A U O A U       với là số thuộc tính điều kiện và là số đối tượng. Độ phức tạp thời A U gian để chọn thuộc tính có độ quan trọng lớn nhất ở dòng lệnh số 6 là: . Do đó, độ phức tạp thời gian của vòng      22/1*1...1 AOAAAA  lặp While là . Tương tự, độ phức tạp của vòng lặp For từ dòng  22 UAO lệnh số 10 đến 14 là . Vì vậy, độ phức tạp thời gian của Thuật  22 UAO toán EIQBAR là . 22 UAO 3.3.4. Thử nghiệm và đánh giá kết quả Chúng tôi chọn thuật toán MBAR tìm tập rút gọn của bảng quyết định không đầy đủ sử dụng metric để so sánh với thuật toán sử dụng lượng thông tin mở rộng đề xuất (Thuật toán EIQBAR) về thời gian thực hiện và kết quả thực hiện. Bảng 3.4. Kết quả thực hiện thuật toán MBAR và Thuật toán EIQBAR Thuật toán MBAR Thuật toán EIQBARSTT Bộ số liệu U C R t R t 1 Hepatitis.data 155 19 4 1.296 3 1.29 2 Lung-cancer.data 32 56 4 0.171 4 0.17 3 Automobile.data 205 25 8 1.687 6 1.68 4 Anneal.data 798 38 9 179 7 178 5 Congressional Voting Records 435 16 15 16.7 15 16.73 6 Credit Approval 690 15 7 15.7 5 15.68 17 Bảng 3.5. Tập rút gọn của thuật toán MBAR và Thuật toán EIQBAR STT Tập dữ liệu Tập rút gọn của Thuật toán MBAR Tập rút gọn của Thuật toán EIQBAR 1 Hepatitis.data {1, 2, 4, 17} {1, 2, 17} 2 Lung-cancer.data {3, 4, 9, 43} {3, 4, 9, 43} 3 Automobile.data {1, 8, 9, 13, 14, 20, 21, 24} {1, 4, 13, 14, 20, 21} 4 Anneal.data {1, 3, 4, 5, 8, 9, 33, 34, 35} {1, 3, 4, 5, 8, 9, 34} 5 Congressional Voting Records {1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16} {1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16} 6 Credit Approval {1, 2, 3, 4, 5, 6, 8} {1, 3, 4, 5, 8} Kết quả thực hiện của hai thuật toán về tập rút gọn và tính toán giá trị các độ chắc chắn , độ nhất quán , độ hỗ trợ  được mô tả ở Bảng 3.6 sau đây: Bảng 3.6. Kết quả tính toán độ chắc chắn, độ nhất quán và độ hỗ trợ trên các tập rút gọn Thuật toán EIQBAR Thuật toán MBARS T T Bộ số liệu U C R    R    1 Hepatitis.data 155 19 3 0.909 0.819 0.504 4 0.909 0.819 0.415 2 Lung-cancer.data 32 56 4 1 1 0.814 4 1 1 0.814 3 Automobile.data 205 25 6 0.915 0.781 0.624 8 0.915 0.781 0.518 4 Anneal.data 798 38 7 0.852 0.755 0.503 9 0.852 0.755 0.426 5 Congressional Voting Records 435 16 15 1 1 0.616 15 1 1 0.616 6 Credit Approval 690 15 5 0.884 0.802 0.615 7 0.884 0.802 0.487 18 Hình 3.1 biễu diễn sự thay đổi độ hỗ trợ  trên hai tập rút gọn của hai thuật toán EIQBAR và MBAR. 0.000 0.100 0.200 0.300 0.400 0.500 0.600 0.700 0.800 0.900 He pat itis .da ta Lu ng- can cer .da ta Au tom obi le.d ata An nea l.da ta C. Vo tin g R eco rds Cre dit Ap pro val Thuật toán EIQBAR Thuật toán MBAR Hình 3.1. Sự thay đổi độ hỗ trợ  trên hai tập rút gọn của thuật toán EIQBAR, MBAR. 1) Kết quả thử nghiệm từ Bảng 3.4 và Bảng 3.5 cho thấy:  Trên các bộ số liệu Lung-cancer.data, Congressional Voting Records, tập rút gọn thu được bởi Thuật toán EIQBAR và Thuật toán MBAR là như nhau. Tuy nhiên, với các bộ số liệu còn lại, tập rút gọn thu được bởi Thuật toán EIQBAR tối thiểu hơn tập rút gọn thu được bởi Thuật toán MBAR. Điều này cũng phù hợp với kết quả nghiên cứu về lý thuyết.  Thời gian thực hiện Thuật toán EIQBAR và Thuật toán MBAR về cơ bản là tương đương nhau. 2) Kết quả thử nghiệm từ Bảng 3.6 và Hình 3.1 cho thấy:  Độ chắc chắn , độ nhất quán  của hai tập rút gọn thu được bởi hai thuật toán EIQBAR và MBAR trên 6 bộ dữ liệu thử nghiệm là bằng nhau. 19  Độ hỗ trợ của tập rút gọn thu được bởi Thuật toán EIQBAR cao hơn độ hỗ trợ của tập rút gọn thu được bởi Thuật toán MBAR. Phần tiếp theo, chúng tôi trình bày phương pháp rút gọn thuộc tính sử dụng hàm quan hệ được xây dựng trên ma trận quan hệ. Phương pháp đề xuất này cũng thuộc Nhóm 2. 3.4. Phương pháp rút gọn thuộc tính sử dụng hàm quan hệ Trong phần này chúng tôi xây dựng thuật toán heuristic tìm một tập rút gọn tốt nhất sử dụng hàm quan hệ. Các kết quả trong phần này đã được tác giả công bố trong công bố [4]. 3.4.1. Ma trận quan hệ và hàm quan hệ Định nghĩa 3.3. Cho bảng quyết định không đầy đủ với   ,IDS U A d  và . Ma trận quan hệ của trên tập thuộc chính , ký hiệu R A U n IDS R , là ma trận vuông cấp n, mỗi phần tử có giá trị 0 hoặc 1, được   nxn R ijR mM  định nghĩa như sau: (1) nếu 1Rijm    iRj uud  (2) nếu .0Rijm    iRj uud  Định nghĩa 3.4. Cho hai ma trận và . Hai quan hệ và   mxn R ijxX   mxnRijyY  " " được định nghĩa như sau:" " (1) khi và chỉ khi , , X Y RijRij yx  1,2,...,i m 1,2,...,j n (2) khi và chỉ khi , , X Y RijRij yx  1,2,...,i m 1,2,...,j n Định nghĩa 3.5. Cho hệ quyết định không đầy đủ , với   ,IDS U A d  R A và là ma trận quan hệ của trên tập thuộc tính . Khi đó,   nxn R ijR mM  IDS R hàm quan hệ của trên , ký hiệu là , được định nghĩa như sau:IDS R  RDIS với .      n i n j R ijmRDIS 1 1 1 ,1i n j n    20 3.4.2. Rút gọn thuộc tính sử dụng hàm quan hệ Định nghĩa 3.6. Cho bảng quyết định không đầy đủ . Nếu   ,IDS U A d  thỏa mãn: R A (1)   )(ADISRDIS  (2) , ' R R   )(' ADISRDIS  thì R được gọi là một tập rút gọn của dựa trên hàm quan hệ.IDS Ta thấy rằng tập rút gọn sử dụng hàm quan hệ tương đương với tập rút gọn sử dựa trên hàm quyết định suy rộng. Do đó, phương pháp rút gọn thuộc tính sử dụng hàm quan hệ thuộc Nhó