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

Từ những mối quan hệ giữa các khái niệm tập rút gọn của các tác giả và các mối quan hệ đã trình bày trên ta có nhận xét là 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 được biểu diễn bằng sơ đồ sau: Hình 1.1 Mối quan hệ giữa các tập rút gọn Sơ đồ trên cho thấy các tập rút gọn trong bảng không nhất quán được chia thành bốn nhóm: 1) Nhóm 1: Bao gồm tập rút gọn .PR 2) Nhóm 2: Bao gồm các tập rút gọn , , .R R MR 3) Nhóm 3: Bao gồm các tập rút gọn , , .DR IR TMR 4) Nhóm 4: Bao gồm tập rút gọn .R Mối liên hệ giữa các tập rút gọn trong các nhóm như sau:  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 2R thuộc Nhóm 2 và một tập rút gọn thuộc Nhóm 1 sao cho 1R .1 2 3R R R   PR MRRR ,,  TMID RRR ,, R   47  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 2R thuộc Nhóm 2 và một tập rút gọn thuộc Nhóm 1 sao cho 1R .1 2 4R R R  Như vậy, tập rút gọn của Nhóm 1 có số thuộc tính nhỏ nhất, sau đó đến Nhóm 2 và Nhóm 3, Nhóm 4. Dựa vào kết quả phân nhóm các tập rút gọn, các phương pháp rút gọn thuộc tính trong bảng quyết định không đầy đủ cũng được phân thành bốn nhóm tương ứng. Đế đánh giá tính hiệu quả của một phương pháp rút gọn thuộc tính, cộng đồng nghiên cứu về tập thô sử dụng hai tiêu chuẩn: 1) độ phức tạp về thời gian thực hiện thuật toán heuristic tìm một tập rút gọn tốt nhất và 2) chất lượng phân lớp của tập rút gọn. Các công bố về rút gọn thuộc tính đều tính toán độ phức tạp thời gian thuật toán tìm tập rút gọn. Do đó, hoàn toàn có thể so sánh được tính hiệu quả của các phương pháp về tiêu chuẩn thời gian. Vì vậy, luận án tập trung nghiên cứu việc đánh giá các phương pháp dựa trên tiêu chuẩn về độ hỗ trợ của tập luật. Việc đánh giá khả năng phân lớp của tập rút gọn dựa vào số lượng thuộc tính của tập rút gọn và khả năng phân lớp của từng thuộc tính. Về mặt định tính, tập rút gọn có số thuộc tính càng ít thì khả năng phân lớp càng cao. Tuy nhiên, điều này chưa hẳn đã chính xác vì khả năng phân lớp của từng thuộc tính khác nhau. Tóm lại, ta cần phải sử dụng độ đo mang tính định lượng để đánh giá khả năng phân lớp của tập rút gọn. Trong lý thuyết tập thô, các nhà nghiên cứu sử dụng ba độ đo để đánh giá tính đúng đắn và tính hiệu quả của một phương pháp rút gọn thuộc tính: độ chắc chắn (certainty measure), độ nhất quán (consistency measure) và độ hỗ trợ (support measure), cụ thể là: tập rút gọn của phương pháp rút gọn thuộc tính phải bảo toàn độ chính xác, độ 48 nhất quán của tập luật quyết định. Độ hỗ trợ sử dụng để đánh giá khả năng phân lớp của tập rút gọn. Độ hỗ trợ của tập luật quyết định dựa trên tập rút gọn càng cao thì khả năng phân lớp của tập rút gọn đó càng cao. 2.3. Đánh giá các phương pháp rút gọn thuộc tính Trong phần này, trước hết luận án sẽ tổng kết các kết quả nghiên cứu liên quan đến luật quyết định và các độ đo đánh giá hiệu năng tập luật trong bảng quyết định không đầy đủ. Tiếp theo, luận án sẽ phân tích nhược điểm các độ đo đánh giá hiệu năng tập luật của Yuhua Qian và các cộng sự trong công trình [33], trên cơ sở đó luận án đề 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 công trình [CT2]. (Danh mục các công trình của tác giả). 2.3.1. Luật quyết định và các độ đo đánh giá hiệu năng Cho bảng quyết định không đầy đủ với , giả   ,IDS U A d   1,..., nU u u sử và . Với ,      1/ { ,..., }A A nU SIM A S u S u   1 2/ { , ,..., }mU d Y Y Y    /A iS u U SIM A và , ký hiệu và lần lượt là các mô  /jY U d  A i jS u Y    A ides S u  jdes Y tả của lớp dung sai và lớp tương đương . Chú ý rằng nếu giá trị  A iS u jY thì bỏ giá trị này ra khỏi vì quy ước giá trị * bằng tất cả  ia u     A ides S u các giá trị khác. Một luật quyết định đơn có dạng     :ij A i jZ des S u des Y [33]. Giống như luật quyết định trong bảng quyết định đầy đủ, độ chắc chắn, độ hỗ trợ và độ bao phủ của luật quyết định đơn tương ứng là:ijZ      /ij A i j A iZ S u Y S u   49     /ij A i js Z S u Y U      /ij A i j jZ S u Y Y   Ví dụ 2.4. Xét bảng quyết định không đầy đủ mô tả về các   ,IDS U A d  tivi cho ở Bảng 2.4 với , với (Đơn  1 2 3 4 5 6, , , , ,U u u u u u u  4321 ,,, aaaaA  1a giá), (Màu sắc), (Tính năng), (Độ phân giải).2a 3a 4a Bảng 2.4. Bảng quyết định không đầy đủ về các tivi Tivi Đơn giá Màu sắc Tính năng Độ phân giải Chất lượng(d) u1 Cao Đen Đầy đủ Thấp Tốt u2 Thấp * Đầy đủ Thấp Tốt u3 * * Thiếu Thấp Xấu u4 Cao * Đầy đủ Cao Tốt u5 * * Đầy đủ Cao Tuyệt hảo u6 Thấp Nâu Đầy đủ * Tốt Ta có , với 1 2 3 4 5 6/ ( ) { ( ), ( ), ( ), ( ), ( ), ( )}A A A A A AU SIM A S u S u S u S u S u S u , , , , , 1 1( ) { }AS u u 2 2 6( ) { , }AS u u u 3 3( ) { }AS u u 4 4 5( ) { , }AS u u u 5 4 5 6( ) { , , }AS u u u u . với , , .6 2 5 6( ) { , , }AS u u u u    1 2 3/ , ,U d Y Y Y 1 1 2 4 6{ , , , }Y u u u u 2 3{ }Y u 3 5{ }Y u Các luật quyết định là: (a1, Cao)  (a2, Đen)  (a3, Đầy đủ)  (a4, Thấp)  (d, Tốt)11 :Z (a1, Thấp)  (a3, Đầy đủ)  (a4, Thấp)  (d, Tốt)21 :Z 50 (a3, Thiếu)  (a4, Thấp)  (d, Xấu)32 :Z (a1, Cao)  (a3, Đầy đủ)  (a4, Cao)  (d, Tốt)41 :Z (a1, Cao)  (a3, Đầy đủ)  (a4, Cao)  (d, Tuyệt hảo)43 :Z (a3, Đầy đủ)  (a4, Cao)  (d, Tốt)51 :Z (a3, Đầy đủ)  (a4, Cao)  (d, Tuyệt hảo)53 :Z (a1, Thấp)  (a2, Nâu)  (a3, Đầy đủ)  (d, Tốt)61 :Z (a1, Thấp)  (a2, Nâu)  (a3, Đầy đủ)  (d, Tuyệt hảo)63 :Z Các độ đo của các luật quyết định đơn là: ,     11 11 11 11: 1, 1 / 6, 1 / 4Z Z s Z Z    ,     21 21 21 21: 1, 1 / 3, 1 / 2Z Z s Z Z    ,     32 32 32 32: 1, 1 / 6, 1Z Z s Z Z    ,     41 41 41 41: 1 / 2, 1 / 6, 1 / 4Z Z s Z Z    ,     43 43 43 43: 1 / 2, 1 / 6, 1Z Z s Z Z    ,     51 51 51 51: 2 / 3, 1 / 3, 1 / 2Z Z s Z Z    ,     53 53 53 53: 1 / 3, 1 / 6, 1Z Z s Z Z    ,     61 61 61 61: 2 / 3, 1 / 3, 1 / 2Z Z s Z Z    .     63 63 63 63: 1 / 3, 1 / 6, 1Z Z s Z Z    Các độ đo này chỉ sử dụng để đánh giá các luật quyết định đơn, không phù hợp cho việc đánh giá tập luật quyết định. Giả sử    1 2/ , ,..., mF U d Y Y Y  51 là một phân lớp của U theo d, độ chính xác của phân lớp F theo A, ký hiệu là , được Pawlak [45] định nghĩa: A F       / / i i iY U d A iY U d AY F AY      Trong một số trường hợp, được dùng để đo độ chắc chắn của  A F bảng quyết định. Tuy nhiên, nhược điểm của độ đo này được minh họa trong ví dụ sau: Ví dụ 2.5. Xét bảng quyết định ở Ví dụ 2.4, ta có:      2 1 2 3 4 5 2 3 4 5 6/ ( ) { , , , , , , , , , , , , , }U SIM a u u u u u U U U U u u u u u              2 4 1 2 3 1 2 3 6 1 2 3 6 4 5 6 4 5 6 2 3 4 5 6/ ( , ) { , , , , , , , , , , , , , , , , , , , , , }U SIM a a u u u u u u u u u u u u u u u u u u u u u u         2 2/ 2/ 0/ 0 6 6 6 i i iY U d a iY U d a Y U d a Y          .          2 4 2 4/ , 2 4/ , 0/ 0 6 4 3, i i iY U d a a iY U d a a Y U d a a Y          Vì vậy, . Tuy nhiên, phủ sinh bởi mịn        2 2 4,/ /a a aU d U d   2 4,a a hơn phủ sinh bởi . Do đó, độ chắc chắn phân lớp nêu trên không phù hợp  2a để đánh giá độ chắc chắn của bảng quyết định, hay tập luật quyết định Trong bảng quyết định không đầy đủ, nghiên cứu đáng chú ý về độ đo đánh giá hiệu năng phải kể đến nhóm nghiên cứu của Yuhua Qian và các cộng sự [33], trong đó các tác giả đã đư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 (consistent block). Trước hết, luận án trình bày khái niệm khối đồng nhất cực đại trong công trình [52]. 52 Cho bảng quyết định không đầy đủ và một quan hệ   ,IDS U A d  dung sai xác định trên tập thuộc tính P. Khi đó,  SIM P là tập lớn nhất các đối tượng không có khả       PSIMvuUvuSP  ,| năng phân biệt được với u trên tập thuộc tính P. là lớp dung sai, còn  PS u gọi là hạt tri thức (knowledge granular). là đơn vị nhỏ nhất sử dụng để  PS u mô tả tri thức và lực lượng của là đơn vị tính toán cơ sở cho các  PS u phương pháp rút gọn thuộc tính [52]. Theo định nghĩa, các đối tượng trong lớp dung sai có quan hệ dung sai với đối tượng u, tuy nhiên các đối  PS u tượng trong có thể không quan hệ dung sai với nhau. Xét bảng quyết  PS u định trong Ví dụ 2.4, ta có , theo định nghĩa quan 5 4 5 6( ) { , , }AS u u u u 654 ,, uuu hệ dung sai với , tuy nhiên và không quan hệ dung sai với nhau. Do 5u 4u 6u đó, trong công trình [52], các tác giả nêu quan điểm rằng các lớp dung sai chưa phải là đơn vị nhỏ nhất để mô tả tri thức và đưa ra khái niệm  PS u khối đồng nhất cực đại (Maximal consistent block). Về bản chất, khối đồng nhất cực đại của đối tượng u là tập con của lớp dung sai , trong đó tất  PS u cả các đối tượng có quan hệ dung sai với nhau. Khối đồng nhất cực đại được định nghĩa như sau. Xét bảng quyết định không đầy đủ với và   ,IDS U A d  P A , ta nói rằng X là đồng nhất (consistent) trên tập thuộc tính P nếu với UX  mọi ta có (nghĩa là u và v quan hệ dung sai với nhau). Xvu , )(, PSIMvu  Nếu không tồn tại một tập con sao cho và X là đồng nhất trên UY  YX  tập thuộc tính P thì X được gọi là khối đồng nhất cực đại trên tập thuộc tính P. Ký hiệu là tập tất cả các khối đồng nhất cực đại trên tập thuộc tính P PMC và là khối đồng nhất cực đại chứa đối tượng u. Với bảng quyết định  uMCP đã cho ở Ví dụ 2.4, các khối đồng nhất cực đại là 53 , trong khi đó các lớp dung sai của các đối           65543621 ,,,,,,, uuuuuuuuMCA tượng là . Hiển nhiên,               652654543621 ,,,,,,,,,,,/ uuuuuuuuuuuuASIMU  các khối đồng nhất cực đại cũng tạo ra một phủ của U chứ không phải một phân hoạch của U, nghĩa là các khối cực đại có thể giao nhau. Trở lại với độ chắc chắn, độ nhất quán và độ hỗ trợ của tập luật trong công bố của Yuhua Qian và các cộng sự [33], các độ đo này được định nghĩa dựa trên các khối đồng nhất cực đại như sau: Cho bảng quyết định không đầy đủ với   ,IDS U A d   nuuU ,....,1 và tập luật với     jiijij YdesXdesZZRULE  :| . là họ các khối đồng nhất cực đại trên   mjnidUYMCX jAi ..1,..1,/,  AMC tập thuộc tính A. Độ chắc chắn của IDS được định nghĩa [33] .   1 1 1 1 iNm i j i ji i X Y IDS m N X       Độ nhất quán của IDS được định nghĩa [33]        1 1 1 41 1 iNm i j ij ij i ji IDS X Y Z Z m X              Độ hỗ trợ của IDS được định nghĩa [33]   1 1 jNn j k j j ki Y X Y IDS N U U      Từ các công thức trên ta thấy rằng độ chắc chắn, độ nhất quán, độ hỗ trợ được định nghĩa qua các khối đồng nhất cực đại. Trong khi đó, các phương pháp rút gọn thuộc tính trong các nhóm phương pháp được trình bày ở phần 1.1 đều sử dụng các độ đo được định nghĩa qua lực lượng của các lớp dung sai, ví dụ phương pháp sử dụng độ đo lượng thông tin (information quantity) 54 [16], độ đo lượng thông tin được định nghĩa qua lực lượng của lớp dung sai của đối tượng , . Do đó, Yuhua Qian và  iB uS Uui        n i iB uS U BI 1 2 11 các cộng sự [33] chưa đánh giá sự thay đổi giá trị độ chắc chắn, độ nhất quán, độ hỗ trợ trên các tập rút gọn của của các phương pháp rút gọn thuộc tính, do đó các độ đo này gặp khó khăn trong việc đánh giá tính hiệu quả (về khả năng phân lớp hay độ hỗ trợ của tập luật) của các phương pháp rút gọn thuộc tính. Hơn nữa, vì các độ đo này được tính qua các khối đồng nhất cực đại nên việc nghiên cứu sự thay đổi các độ đo này trên các tập rút gọn ta cần chuyển đổi các độ đo này sang đơn vị tính toán cơ sở là lực lượng các lớp dung sai. Hướng nghiên cứu này hoàn toàn có thể thực hiện được vì công trình [52] cho phép tính toán lớp dung sai dựa trên khối đồng nhất cực đại. Theo [52], nếu là tập tất cả các khối đồng nhất cực đại và khi và chỉ khi AMC AMCX  . Tuy nhiên, việc chuyển đổi các công thức độ chắc chắn, độ nhất  uAXu SX   quán, độ hỗ trợ trong [33] tính toán qua các lớp dung sai khá phức tạp vì bản thân các công thức độ chắc chắn, độ nhất quán, độ hỗ trợ cũng đã phức tạp và việc chuyển đổi sang lớp dung sai lại càng phức tạp. Do đó, luận án chuyển sang hướng nghiên cứu là định nghĩa lại độ chắc chắn, độ nhất quán, độ hỗ trợ qua các lớp dung sai. Việc định nghĩa các độ đo mới, độ chắc chắn, độ nhất quán, độ hỗ trợ, qua các lớp dung sai dựa trên ý tưởng mở rộng độ chắc chắn, độ nhất quán, độ hỗ trợ trên bảng quyết định đầy đủ trong luận án tiến sĩ [2]. 2.3.2. Đề xuất các độ đo mới đánh giá hiệu năng tập luật quyết định Trên cơ sở mở rộng các kết quả nghiên cứu trong luận án tiến sĩ [2], luận án đề xuất ba độ đo mới đánh giá hiệu năng tập luật quyết định: độ chắc chắn, độ nhất quán và độ hỗ trợ. Các độ đo này được tính bằng trung bình cộng của tất cả các luật quyết định đơn và được tính dựa trên lực lượng các lớp dung sai. Từ đó, luận án đánh giá sự thay đổi các độ đo đề xuất trên các tập rút gọn nhằm so sánh, đánh giá tính hiệu quả của các phương pháp rút gọn thuộc tính. 55 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 Dễ thấy rằng, đạt giá trị lớn nhất là 1 nếu với mọi  IDS   1ijZ  , nghĩa là IDS nhất quán, và đạt giá trị nhỏ nhất là nếu ijZ RULE  IDS 1 / n , nghĩa là và với mọi . Tương tự, đạt iN n m U  A iS u U iu U  IDS giá trị lớn nhất là 1 khi đạt giá trị lớn nhất là 1 và đạt giá trị  IDS  IDS nhỏ nhất là 0 khi đạt giá trị nhỏ nhất là . đạt giá trị lớn  IDS 1 / n  IDS nhất là 1 nếu với mọi . đạt giá trị nhỏ nhất là nếu  A iS u U iu U  IDS 1 / n với mọi . Mệnh đề 2.6 sau đây chứng minh một số tính    A i iS u u iu U chất quan trọng của các độ đo đánh giá hiệu năng. 56 Mệ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  , , . Nếu thì ,      / , /A i jS u U SIM A Y U d  1..i n 1..j m B A    'IDS IDS  ,    'IDS IDS     'IDS IDS  Chứng minh. 1) Giả sử , tương ứng là số luật quyết định sinh bởi lớp  iN A  iN B dung sai , . Theo [24], nếu thì với mọi  A iS u  B iS u B A    A i B iS u S u , suy ra . Từ đó ta có:iu U    i iN A N B = =          1 1 1 1 iN An A i j i ji A i S u Y IDS n N A S u          1 1 1 1 1 1n n i ii in N A n N B    = . Do đó .        1 1 1 1 iN Bn B i j i ji B i S u Y n N B S u     'IDS    'IDS IDS  Dấu đẳng thức khi và chỉ khi . Theo định    'IDS IDS     i iN A N B nghĩa hàm quyết định suy rộng ta có với mọi | ( ) | | ( ) | ( ) ( )A i B i A i B iu u u u       .iu U 2) Chứng minh tương tự như phần 1) ta có . Dấu đẳng    'IDS IDS  thức khi và chỉ khi với mọi .   'IDS IDS  ( ) ( )A i B iu u   iu U 3) Nếu thì với , suy ra B A    A i B iS u S u iu U với ,    A i j B i jS u Y S u Y   iu U  /jY U d    A i j B i jS u Y S u Y    . Dấu đẳng thức     1 1 1 1 1 1n m n mA i j B i j i j i j S u Y S u Y n n n n           'IDS IDS   khi và chỉ khi .   'IDS IDS     A i B iS u S u 57 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 Trước hết, luận án tổng kết lại kết quả phân nhóm các tập rút gọn được trình bày ở mục 2.2.6. Nhóm 1: Tập rút gọn miền dương .PR Nhóm 2: Bao gồm tập rút gọn dựa trên hàm quyết định suy rộng ( ), R tập rút gọn ấn định ( ), tập rút gọn dựa trên ma trận phân biệt ( ). Luận R MR án chọn tập rút gọn dựa trên hàm quyết định suy rộng làm đại diện.R Nhóm 3: Bao gồm tập rút gọn dựa trên lượng thông tin ( ), tập rút IR gọn dựa trên ma trận dung sai ( ), tập rút gọn dựa trên khoảng cách ( ), TMR DR luận án chọn tập rút gọn dựa trên khoảng cách làm đại diện.DR Nhóm 4: Tập rút gọn phân bố .R Trong mục này, chúng tôi nghiên cứu sự thay đổi của độ chắc chắn , độ nhất quán và độ hỗ trợ dựa trên bốn tập rút gọn  IDS  IDS  IDS của bốn nhóm phương pháp nêu trê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 ( ) thì PR , ,    'IDS IDS     'IDS IDS     'IDS IDS  58 Chứng minh a) Nếu IDS nhất quán và B là một tập rút gọn miền dương thì . Từ công thức tính dễ dàng suy ra | ( ) | | ( ) | 1A i B iu u       ,IDS IDS  , . Hơn nữa, theo Mệnh đề 2.6 ta có    ' 1IDS IDS      ' 1IDS IDS   .   'DS DS  Như vậy, tập rút gọn miền dương ( ) bảo toàn độ chắc chắn bằng 1, độ PR nhất quán bằng 1 và tăng độ hỗ trợ của tập luật đối với bảng quyết định không đầy đủ nhất quán. b) Nếu IDS không nhất quán: từ Mệnh đề 2.6 ta có ,    '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  Chứng minh Nếu là một tập rút gọn dựa trên hàm quyết định suy rộng thì B với mọi , theo điều kiện dấu đẳng thức của Mệnh đề 2.6 ta ( ) ( )A i B iu u   iu U có , . Cũng theo Mệnh đề 2.6 ta có    '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, bảo toàn độ nhất quán và tăng độ hỗ trợ của tập luật quyết định. 59 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  Chứng minh Nếu là một tập rút gọn dựa trên khoảng cách ( ) thì B DR , theo kết quả nghiên cứu mối liên            , ,E Ed K B K B d d K A K A d   hệ giữa các tập rút gọn đã trình bày ở trên ta có với mọi , ( ) ( )A i B iu u   iu U theo điều kiện dấu đẳng thức của Mệnh đề 2.6 ta có ,    'IDS IDS  . Cũng theo Mệnh đề 2.6 ta có .   'IDS IDS     'IDS IDS  Giống như tập rút gọn , tập rút gọn bảo toàn độ chắc chắn, bảo R DR toàn độ nhất quán và tăng độ hỗ trợ của tập luật quyết định. 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 ở trên, mỗi tập rút gọn đều tồn tại một tập rút gọn sao cho . Theo Mệnh đề DR R DR R  2.6, độ hỗ trợ của tập luật dựa trên tập rút gọn sẽ nhỏ hơn độ hỗ trợ của DR tập luật dựa trên tập rút gọn . Nghĩa là, chất lượng phân lớp của tập rút R gọn tốt hơn tập rút gọn .R DR 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  Chứng minh Nếu là một tập rút gọn phân bố ( ) thì với mọi , B R    R i A iu u  iu U theo kết quả nghiên cứu mối liên hệ giữa tập rút gọn phân bố và tập rút gọn 60 dựa trên hàm quyết định suy rộng trong [18] ta có với mọi ( ) ( )A i B iu u   , theo điều kiện dấu đẳng thức của Mệnh đề 2.6 ta có , iu U    'IDS IDS  . Cũng theo Mệnh đề 2.6 ta có .   'IDS IDS     'IDS IDS  Giống như tập rút gọn , tập rút gọn bảo toàn độ chắc chắn, bảo R R toàn độ nhất quán và tăng độ hỗ trợ của tập luật quyết định. 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 ở trên, mỗi tập rút gọn đều tồn tại một tập rút gọn sao cho . Theo Mệnh đề 2.6, R R R R  độ hỗ trợ của tập luật dựa trên tập rút gọn sẽ nhỏ hơn độ hỗ trợ của tập R luật dựa trên tập rút gọn . Nghĩa là, chất lượng phân lớp của tập rút gọn R tốt hơn tập rút gọn .R R 2.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 Từ kết quả nghiên cứu về lý thuyết của mục 2.3.3 ta có: - Tập rút gọn miền dương thuộc Nhóm 1 ( ) làm giảm độ chắc chắn PR , độ nhất quán ; tập rút gọn dựa trên hàm quyết định suy rộng  IDS  IDS thuộc Nhóm 2 ( ), tập rút gọn dựa trên khoảng cách ( ) thuộc Nhóm 3, tập R DR rút gọn phân bố ( ) thuộc Nhóm 4 bảo toàn độ chắc chắn , độ nhất R  IDS quán . IDS - Các tập rút gọn , , và đều tăng độ hỗ trợ .PR R DR R  IDS - Tập rút gọn có độ hỗ trợ cao hơn . Tập rút gọn có độ hỗ trợ PR R R cao hơn và (tập rút gọn có độ hỗ trợ càng cao thì số luật sinh ra càng DR R ít). 61 Trong mục này, luận án trình bày thử nghiệm các kết quả nghiên cứu lý thuyết nêu trên về sự thay đổi độ chắc chắn , độ nhất quán và  IDS  IDS độ hỗ trợ trên một số bộ số liệu từ kho dữ liệu UCI. IDS Để tiến hành thử nghiệm, luận án thực hiện các công việc sau: 1) Cài đặt các thuật toán sau bằng ngôn ngữ C# tìm một tập rút gọn của bảng quyết định. Với mỗi thuật toán, tính độ chắc chắn , độ  IDS nhất quán và độ hỗ trợ trên bảng quyết định với tập  IDS  IDS rút gọn thu được bằng công thức đề xuất trong mục 2.3.2.  Thuật toán POSBAR tìm một tập rút gọn [56].PR  Thuật toán GDBAR tìm một tập rút gọn [18].R  Thuật toán MBAR tìm một tập rút gọn [27].DR  Thuật toán DFBAR tìm một tập rút gọn [37].R 2) Trên máy tính PC với cấu hình Core i3 4150, 3 GB bộ nhớ RAM, sử dụng hệ điều hành Windows 7, chạy thử nghiệm hai thuật toán với 6 bộ số liệu lấy từ kho dữ liệu UCI [40]. 3) Dữ liệu thử nghiệm trên kho dữ liệu UCI như sau:  Bộ số liệu Hepatitis.data với thông số: Đặc điểm tập dữ liệu: Multivariate, Đặc điểm thuộc tính: Categorical, Integer và Real, Thiếu giá trị : Yes, Lĩnh vực : Life, Số đối tượng: 155, Số thuộc tính :19.  Bộ số liệu Lung-cancer.data với thông số: Đặc điểm tập dữ liệu: Multivariate, Đặc điểm thuộc tính: Integer, Thiếu giá trị : Yes, Lĩnh vực : Life, Số đối tượng: 32, Số thuộc tính :56. 62  Bộ số liệu Automobile.data với thông số: Đặc điểm tập dữ liệu: Multivariate, Đặc điểm thuộc tính: Categorical, Integer và Real, Thiếu giá trị : Yes, Lĩnh vực : N/A, Số đối tượng: 205, Số thuộc tính :26.  Bộ số liệu Anneal.data với thông số: Đặc điểm tập dữ liệu: Multivariate, Đặc điểm thuộc tính: Categorical, Integer và Real, Thiếu giá trị : Yes, Lĩnh vực : Physical, Số đối tượng: 798, Số thuộc tính :38.  Bộ số liệu Congressional Voting Records với thông số: Đặc điểm tập dữ liệu: Multivariate, Đặc điểm thuộc tính: Categorical, Thiếu giá trị : Yes, Lĩnh vực : Social, Số đối tượng: 435, Số thuộc tính :16.  Bộ số liệu Credit Approval với thông số: Đặc điểm tập dữ liệu: Multivariate, Đặc điểm thuộc tính: Categorical, Integer và Real, Thiếu giá trị : Yes, Lĩnh vực : Financial, Số đối tượng: 690, Số thuộc tính :15. 4) Với mỗi bộ số liệu, giả sử là số đối tượng, là số thuộc tính U C điều kiện, là số thuộc tính của tập rút gọn, ,  và  tương ứng là R độ chắc chắn, độ nhất quán và độ hỗ trợ của bảng quyết định. Kết quả thực hiện của hai thuật toán được mô tả ở Bảng 2.5 và Bảng 2.6 sau đây. 63 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 26 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.81