Luận án Một số phương pháp lai ghép trong rút gọn thuộc tính theo tiếp cận tập thô mờ - Nguyễn Văn Thiện

CR u u u u  ,    2 4 5 5, , 1CR u u u u  ,    2 4 5 6, , 0CR u u u u  . Từ đó, hàm thuộc của các đối tượng đối với miền dương mờ    CR POS d là:                1 3 6 2 4 51 1 1, , , ,sup , 1C CRCPOS d R u u u R u u uu u u    ,     2 1RCPOS d u  ,     3 1RCPOS d u  ,     4 1RCPOS d u  ,     5 1RCPOS d u  ,     6 1RCPOS d u  . Từ đó:    1 CR d  Áp dụng các bước của Thuật toán F_FRSAR ta có    1 0.167 cR d  ,    2 0 cR d  ,    3 0.167 cR d  ,    4 0.5 cR d  ,    5 0.467 cR d  ,    6 0.467 cR d  . Chọn thuộc tính 4c có độ quan trọng lớn nhất và  4P c . Thực hiện vòng lặp While. Xét các thuộc tính 1c ta có: 44               ,4 4 1 4 1 1 0.5 0.5c c c cR R RSIG c d d      . Tương tự    4 2 0.5cRSIG c  ,     4 3 0cRSIG c  ,    4 5 0.5cRSIG c  ,    4 6 0.5cRSIG c  . Không mất tính tổng quát, chọn thuộc tính 1c có độ quan trọng lớn nhất và  1 4,P c c . Khi đó ta có         ,1 4 1 c c CR R d d   , do đó thuật toán dừng và  1 4,P c c là một tập rút gọn của bảng quyết định DS. 2.2.3. Rút gọn thuộc tính sử dụng độ phụ thuộc mờ theo tiếp cận filter- wrapper Xét bảng quyết định  ,DS U C D  với  1 2, ,..., mC a a a và R là quan hệ tương đương mờ xác định trên miền giá trị thuộc tính. Đặt   CR D  . Theo thuật toán F_FRSAR, giả sử các thuộc tính 1 2 , ,...i ia a được thêm vào tập rỗng theo giá trị lớn nhất của độ quan trọng thuộc tính cho đến khi tồn tại  1,2,...t m sao cho     , ,..., 1 2 a a ai i it R D  . Kết thúc thuật toán filter F_FRSAR, ta thu được tập rút gọn   1 2 , ,..., ti i i B a a a và độ chính xác phân lớp trên tập dữ liệu được tính trên B. Mặt khác, theo định nghĩa miền dương mờ trong lý thuyết tập thô mờ và [76, 77, 78, 79] ta có             , ,..., 1 1 2 1 ... a a a a ai i i i it R R R D D D       . Với ngưỡng   cho trước, đặt   1 ,..., kk i i B a a thỏa mãn   BkR D  và     1 B ak ik R D     . Khi đó, kB được gọi là tập rút gọn xấp xỉ ngưỡng  . Nếu kB và  1 ,...,k tk i iB a a được sử dụng để xây dựng bộ phân lớp, công bố [91] cho thấy, độ chính xác phân lớp trên   1 ,..., k tk i i B a a   chưa chắc đã tốt hơn trên kB . Giả sử kB có độ chính xác phân lớp tốt hơn   1 ,..., k tk i i B a a   . Khi đó, nếu chọn kB là kết quả của thuật toán thì kB có độ chính xác phân lớp cao hơn, có số lượng thuộc tính ít hơn nên khả năng khái quát hóa và hiệu năng thực hiện các thuật toán phân lớp sẽ cao hơn. Điều đó dẫn đến hướng tiếp cận lai ghép tìm tập rút gọn xấp xỉ, là sự kết hợp giữa filter (lọc) và wrapper (gói). Phương pháp filter tìm ra các tập rút gọn xấp xỉ, phương pháp 45 wrapper kiểm tra độ chính xác phân lớp của các tập rút gọn xấp xỉ để chọn tập rút gọn có độ chính xác cao nhất. Với hướng tiếp cận này, độ chính xác phân lớp trên tập rút gọn tìm được cao hơn so với các phương pháp lọc truyền thống. Tuy nhiên, thời gian thực hiện sẽ lớn hơn vì phải thực hiện các bộ phân lớp. Thuật toán filter-wrapper tìm tập rút gọn xấp xỉ sử dụng độ phụ thuộc mờ được mô tả như sau: Thuật toán FW_FRSAR (Filter-Wrapper Fuzzy Rough Set based Attribute Reduction): Thuật toán filter-wrapper tìm tập rút gọn xấp xỉ sử dụng độ phụ thuộc mờ. Đầu vào: Bảng quyết định  ,DS U C D  với  1 2, ,..., nC a a a , quan hệ tương đương mờ R xác định trên miền giá trị thuộc tính điều kiện. Đầu ra: Tập rút gọn xấp xỉ xS có độ chính xác phân lớp tốt nhất. // Khởi tạo 1. :B  ;   0D   ; :S  ; 2. Tính độ phụ thuộc mờ   CR D ; // Giai đoạn filter, tìm các ứng viên cho tập rút gọn // Thêm dần vào P các thuộc tính có độ quan trọng lớn nhất 3. While     B CR R D D  do 4. Begin 5. Với mỗi a C B  tính         B a BB R R SIG a D D     6. Chọn ma C B  sao cho     B m B a C B SIG a Max SIG a    ; 7.  mB B a  ; ;S S B  8. End; // Giai đoạn Wrapper,tìm tập rút gọn có độ chính xác phân lớp cao nhất 9. Đặt t S //t là số phần tử của S, S chứa các chuỗi thuộc tính được chọn tại mỗi bước lặp của vòng lặp While, nghĩa là 46        1 1 2 1 2 , , ,..., , ,..., ti i i i i i S a a a a a a ; 10. Đặt       1 1 2 1 21 2 , , ,..., , ,..., ti i i t i i i S a S a a S a a a   11. For j = 1 to t 12. Begin 13. Tính độ chính xác phân lớp trên jS bằng một bộ phân lớp sử dụng phương pháp 10-fold; 14. End 15. x joS S với joS có độ chính xác phân lớp lớn nhất. Return xS ; Tiếp theo, chúng tôi đánh giá độ phức tạp thời gian của thuật toán filter- wrapper FW_FRSAR, gọi tắt là độ phức tạp. Giả sử  D d và ký hiệu ,C U tương ứng là số thuộc tính điều kiện và số đối tượng của DS. Theo mục 2.2.2, độ phức tạp của thuật toán filter F_FRSAR là  2 2*O C U , do đó độ phức tạp của giai đoạn filter (từ câu lệnh 3 đến 8) là  2 2*O C U . Độ phức tạp của giai đoạn wrapper (từ câu lệnh số 9 đến số 15) phụ thuộc vào độ phức tạp của bộ phân lớp được sử dụng. Giả sử độ phức tạp của bộ phân lớp là  O T , khi đó độ phức tạp của giai đoạn wrapper là  *O C T . Vì vậy, độ phức tạp của thuật toán FW_FRSAR là    2 2* *O C U O C T 2.2.4. Thực nghiệm các thuật toán 2.2.4.1. Bộ dữ liệu thử nghiệm và môi trường thử nghiệm Chúng tôi chọn 8 bộ dữ liệu mẫu từ lấy từ kho dữ liệu UCI [103] cho ở Bảng 2.2 để tiến hành thử nghiệm. Môi trường thử nghiệm là máy tính PC với cấu hình Intel(R) Core(TM) i7-3770CPU @3.40 GHz, sử dụng hệ điều hành Windows 7, 32 bit. Công cụ lập trình thực hiện các thuật toán là ngôn ngữ C# và công cụ phân tích dữ liệu R. 47 Bảng 2.2. Bộ dữ liệu thử nghiệm thuật toán F_FRSAR, FW_FRSAR STT Bộ dữ liệu Mô tả Số đối tượng Số thuộc tính điều kiện Số lớp quyết định Tất cả Thuộc tính định danh (nominal) Thuộc tính thực (Real- valued) 1 Ecoli Protein Localization Sites 336 7 0 7 8 2 Ionosphere Johns Hopkins University Ionosphere database 351 34 0 34 2 3 WDBC Wisconsin diagnostic breast cancer 569 30 0 30 2 4 Wpbc Wisconsin Prognostic Breast Cancer 198 33 0 33 2 5 Wine Wine recognition data 178 13 0 13 3 6 Glass Glass Identification Database 214 9 0 9 7 7 Magic04 MAGIC gamma telescope data 2004 19020 10 0 10 2 8 Page- blocks Blocks Classification 5473 10 0 10 5 2.2.4.2. Đánh giá độ chính xác phân lớp của thuật toán F_FRSAR với các thuật toán khác theo tiếp cận tập thô mờ và thuật toán RSAR theo tiếp cận tập thô truyền thống 1) Đánh giá độ chính xác phân lớp của thuật toán F_FRSAR theo tiếp cận tập thô mờ với thuật toán RSAR theo tiếp cận tập thô truyền thống Trước hết, chúng tôi tiến hành thử nghiệm nhằm đánh giá độ chính xác phân lớp của thuật toán F_FRSAR với thuật toán RSAR theo tiếp cận tập thô truyền thống. Với thuật toán filter theo tiếp cận tập thô mờ F_FRSAR, chúng tôi dùng 48 quan hệ tương đương mờ R trên miền giá trị của thuộc tính kc C như sau [54, 68, 76]           1 4* , 0.25 ( , ) max( ) min( ) max( ) min( ) 0, k k i k j k i k j c i j k k k k c u c u c u c u R u u c c c c otherwise             Với    max , mink kc c tương ứng là giá trị lớn nhất và giá trị nhỏ nhất của miền giá trị thuộc tính kc . Trên thuộc tính quyết định  d chúng tôi sử dụng quan hệ tương đương  dR . Phân hoạch      / d dU R x x U  với      ( , ) 1ddx y U R x y   là một lớp tương đương. Khi đó, lớp tương đương  dx được xem là lớp đương đương mờ, ký hiệu là   d x , với hàm thuộc     1 d x y  nếu   d y x và     0 d x y  nếu   d y x . Để tiến hành thử nghiệm, chúng tôi thực hiện các công việc sau: - Cài đặt, thực hiện thuật toán rời rạc hóa dữ liệu equal-width [64] và thuật toán RSAR để tìm tập rút gọn theo tiếp cận tập thô. - Cài đặt, thực hiện thuật toán F_FRSAR để tìm tập rút gọn trực tiếp từ bảng quyết định ban đầu theo tiếp cận tập thô mờ. - Chúng tôi sử dụng bộ phân lớp SVM và C4.5 trong công cụ R để tính độ chính xác phân lớp trên tập rút gọn thu được bởi hai thuật toán . Chúng tôi sử dụng phương pháp kiểm tra chéo 10-fold, nghĩa là bộ dữ liệu được chia thành 10 phần xấp xỉ bằng nhau, lấy ngẫu nhiên 1 phần làm bộ dữ liệu kiểm tra, 9 phần còn lại làm dữ liệu huấn luyện. Quá trình được lặp lại 10 lần. Bảng 2.3 là kết quả thử nghiệm trên 8 bộ số liệu được chọn với U là số đối tượng, C là số thuộc tính điều kiện, R là số thuộc tính của tập rút gọn. 49 Bảng 2.3. Độ chính xác phân lớp của F_FRSAR và RSAR ST T Bộ số liệu U C Rút gọn thuộc tính theo tiếp cận tập thô (RSAR) Rút gọn thuộc tính theo tiếp cận tập thô mờ (F_FRSAR) R Độ chính xác phân lớp SVM Độ chính xác phân lớp C4.5 R Độ chính xác phân lớp SVM Độ chính xác phân lớp C4.5 1 Ecoli 336 7 5 0.851 0.819 7 0.865 0.855 2 Ionospher e 351 34 10 0.814 0.802 15 0.937 0.915 3 Wdbc 569 30 8 0.795 0.784 19 0.980 0.975 4 Wpbc 198 33 7 0.718 0.704 19 0.825 0.818 5 Wine 178 13 4 0.814 0.802 10 0.955 0.920 6 Glass 214 9 5 0.815 0.795 7 0.891 0.882 7 Magic04 1902 0 10 4 0.745 0.715 6 0.782 0.765 8 Page- blocks 5473 10 5 0.758 0.725 7 0.865 0.855 Hình 2.1. Độ chính xác phân lớp của F_FRSAR và RSAR 50 Từ Bảng 2.3 và Hình 2.1 ta thấy, trên tất cả các tập dữ liệu, tập rút gọn của F_FRSAR nhiều thuộc tính hơn RSAR. Độ chính xác phân lớp trên tập rút gọn của F_FRSAR cao hơn độ chính xác phân lớp trên tập rút gọn của RSAR. 2) Đánh giá độ chính xác phân lớp của thuật toán F_FRSAR với các thuật toán khác theo tiếp cận tập thô mờ Tiếp theo, chúng tôi tiến hành thử nghiệm để đánh giá thuật toán filter đề xuất F_FRSAR với thuật toán filter tìm tập rút gọn theo tiếp cận tập thô mờ sử dụng lượng thông tin tăng thêm (information gain) mờ dựa trên entropy Shannon mờ, gọi là thuật toán GAIN_RATIO_AS_FRS trong công trình [45]. Sở dĩ chọn thuật toán GAIN_RATIO_AS_FRS để so sánh với thuật toán đề xuất vì thuật toán GAIN_RATIO_AS_FRS được chứng minh là hiệu quả hơn các thuật toán sử dụng ma trận phân biệt mờ (công trình số 1, phần danh mục các công trình của tác giả). Để tiến hành thử nghiệm, chúng tôi cài đặt thuật toán GAIN_RATIO_AS_FRS trong [45] sử dụng cùng quan hệ tương đương mờ với thuật toán F_FRSAR. Chúng tôi cũng sử dụng phương pháp 10-fold như mô tả ở trên (mục 2.2.4.2) để đánh giá độ chính xác phân lớp với bộ phân lớp SVM và C4.5 trong công cụ R, vì bộ phân lớp SVM và C4.5 cũng được chọn trong thử nghiệm của công bố số [45]. Kết quả thực hiện hai thuật toán được mô tả ở Bảng 2.4 như sau: Bảng 2.4. Độ chính xác phân lớp của GAIN_RATIO_AS_FRS và F_FRSAR STT Bộ số liệu U C Thuật toán GAIN_RATIO_AS_FRS [45] Thuật toán F_FRSAR R Độ chính xác phân lớp SVM Độ chính xác phân lớp C4.5 R Độ chính xác phân lớp SVM Độ chính xác phân lớp C4.5 1 Ecoli 336 7 6 0.814 0.802 7 0.865 0.855 2 Ionos phere 351 34 13 0.916 0.904 15 0.937 0.915 3 Wdbc 569 30 17 0.925 0.917 19 0.980 0.975 4 Wpbc 198 33 17 0.815 0.804 19 0.825 0.818 5 Wine 178 13 9 0.910 0.902 10 0.955 0.920 51 6 Glass 214 9 7 0.891 0.882 7 0.891 0.882 7 Magic 04 1902 0 10 6 0.782 0.765 6 0.782 0.765 8 Page- blocks 5473 10 6 0.852 0.848 7 0.865 0.855 Hình 2.2. Độ chính xác phân lớp của GAIN_RATIO_AS_FRS và F_FRSAR Từ Bảng 2.4 và Hình 2.2 ta thấy, trên cùng một quan hệ tương đương mờ được sử dụng, độ chính xác phân lớp sau khi thực hiện thuật toán đề xuất F_FRSAR cao hơn độ chính xác phân lớp sau khi thực hiện thuật toán GAIN_RATIO_AS_FRS trong [45]. Tập rút gọn của thuật toán đề xuất F_FRSAR bảo toàn miền dương mờ và nhiều thuộc tính hơn so với thuật toán GAIN_RATIO_AS_FRS trong [45]. 2.2.4.3. Đánh giá độ chính xác phân lớp của thuật toán filter-wrapper FW_FRSAR với thuật toán filter F_FRSAR và các thuật toán filter khác theo tiếp cận tập thô mờ Trong mục này, chúng tôi tiến hành thử nghiệm đánh giá thuật toán filter- wrapper FW_FRSAR với thuật toán filter F_FRSAR và thuật toán filter GAIN_RATIO_AS_FRS trong [45]. Việc đánh giá dựa trên hai tiêu chuẩn: độ chính xác phân lớp và thời gian thực hiện của các thuật toán. Cả 3 thuật toán đề sử dụng quan hệ tương đương mờ ở mục 2.2.4.2. Chúng tôi cũng sử dụng phương pháp 10-fold như mô tả ở mục 2.2.4.2 để đánh giá độ chính xác phân lớp với bộ phân lớp C4.5 trong công cụ R. 52 1) So sánh độ chính xác phân lớp của FW_FRSAR, F_FRSAR và GAIN_RATIO_AS_FRS Kết quả so sánh độ chính xác phân lớp của 3 thuật toán được mô tả ở Bảng 2.5. Trong đó, U là số đối tượng, C là số thuộc tính điều kiện, R là số thuộc tính của tập rút gọn. Bảng 2.5. Độ chính xác phân lớp FW_FRSAR, F_FRSAR, GAIN_RATIO_AS_FRS STT Tập dữ liệu Tập dữ liệu ban đầu Thuật toán FW_FRSAR Thuật toán F_FRSAR Thuật toán GAIN_RATIO _AS_FRS [45] U C R Độ chính xác phân lớp C4.5 R Độ chính xác phân lớp C4.5 R Độ chính xác phân lớp C4.5 1 Ecoli 336 7 5 0.901 7 0.855 6 0.802 2 Ionosphere 351 34 8 0.946 15 0.915 13 0.904 3 Wdbc 569 30 6 0.975 19 0.975 17 0.917 4 Wpbc 198 33 12 0.867 19 0.818 17 0.804 5 Wine 178 13 5 0.920 10 0.920 9 0.902 6 Glass 214 9 4 0.924 7 0.882 7 0.882 7 Magic04 19020 10 4 0.886 6 0.765 6 0.765 8 Page- blocks 5473 10 5 0.906 7 0.855 6 0.848 Kết quả ở Bảng 2.5 cho thấy, số thuộc tính tập rút gọn của thuật toán filter- wrapper FW_FRSAR nhỏ hơn nhiều, đặc biệt là đối với các bộ dữ liệu Wdbc, Ionosphere. Hơn nữa, độ chính xác của FW_FRSAR cao hơn F_ FRSAR và GAIN_RATIO_AS_FR, độ chính xác FW_FRSAR bằng F_FRSAR trên 2 bộ dữ liệu Wdbc và Wine. Nguyên nhân là giai đoạn wrapper, thuật toán FW_FRSAR tính độ chính xác phân lớp trên tất cả các ứng cử viên tập rút gọn sinh bởi F_FRSAR và tìm ứng cử viên có độ chính xác phân lớp tốt nhất. Như vậy, thuật toán đề xuất filter-wrapper FW_FRSAR đáp ứng mục tiêu đặt ra là giảm thiểu số thuộc tính tập rút gọn, từ đó giảm thiểu độ phức tạp của mô hình mà vẫn cố gắng bảo toàn độ chính xác phân lớp (độ chính xác phân lớp còn cao hơn các phương pháp filter). 53 2) So sánh thời gian thực hiện của FW_FRSAR, F_FRSAR và GAIN_RATIO_AS_FRS Kết quả so sánh thời gian thực hiện của 3 thuật toán được mô tả ở Bảng 2.6. Thời gian tính bằng giây (s), trong đó thời gian thực hiện thuật toán filter-wrapper FW_FRSAR được tách thành hai giai đoạn: thời gian thực hiện thủ tục filter và wrapper. Bảng 2.6. Thời gian thực hiện FW_FRSAR, F_FRSAR, GAIN_RATIO_AS_FRS STT Bộ dữ liệu U C Thuật toán FW_FRSAR Thuật toán F_FRSAR Thuật toán GAIN_RATIO _AS_FRS [45] Thủ tục Filer Thủ tục Wrapper Tổng cộng 1 Ecoli 336 7 2.38 1.24 3.62 2.86 2.95 2 Ionosphere 351 34 12.64 6.92 19.56 14.87 15.04 3 Wdbc 569 30 22.15 8.74 30.89 24.12 26.08 4 Wpbc 198 33 8.56 6.28 14.84 9.12 9.88 5 Wine 178 13 0.58 1.22 1.80 0.62 0.74 6 Glass 214 9 0.82 0.66 1.48 0.88 1.02 7 Magic04 19020 10 894.26 124.49 1018.75 914.86 948.16 8 Page- blocks 5473 10 98.64 22.16 120.80 112.76 126.28 Kết quả ở Bảng 2.6 cho thấy, thời gian thực hiện thuật toán FW_FRSAR cao hơn hai thuật toán filter F_FRSAR và GAIN_RATIO_AS_FRS vì phải thực hiện các bộ phân lớp trong giai đoạn wrapper. Chú ý rằng thời gian thực hiện thủ tục filter trong thuật toán FW_FRSAR nhỏ hơn F_FRSAR và GAIN_RATIO_AS_FRS vì thủ tục filter không phải kiểm tra lại tập rút gọn tìm được. Với 2 thuật toán filter, thời gian thực hiện thuật toán đề xuất F_FRSAR nhỏ hơn một chút so với thuật toán GAIN_RATIO_AS_FRS vì không phải tính toán các công thức entropy Shannon. 2.3. Rút gọn thuộc tính sử dụng khoảng cách mờ Trong mấy năm gần đây, nhóm nghiên cứu của Nguyễn Long Giang và cộng sự đã sử dụng các độ đo khoảng cách để giải quyết bài toán rút gọn thuộc tính trong bảng quyết định theo tiếp cận tập thô truyền thống [9, 24, 57, 65] và bảng quyết 54 định không đầy đủ theo tiếp cận tập thô dung sai [9, 10, 12, 25, 58]. Theo tiếp cận tập thô mờ, nhóm nghiên cứu đã mở rộng các độ đo khoảng cách đã đề xuất thành các độ đo khoảng cách mờ và đã có một số kết quả trong việc sử dụng độ đo khoảng cách mờ để giải quyết bài toán rút gọn thuộc tính trên bảng quyết định có miền giá trị số. Trong công trình [8], nhóm tác giả xây dựng độ đo khoảng cách Jaccard mờ giữa hai tập thuộc tính dựa trên khoảng cách Jaccard giữa hai tập hợp hữu hạn và chứng minh một số tính chất của nó. Trong công trình [3], các tác giả đã sử dụng khoảng cách Jaccard mờ trong [8] để giải quyết bài toán rút gọn thuộc tính trực tiếp trên bảng quyết định gốc có miền giá trị số. Trong công trình [18], các tác giả xây dựng độ đo khoảng cách phân hoạch mờ và sử dụng khoảng cách phân hoạch mờ giải quyết bài toán rút gọn thuộc tính trên bảng quyết định có miền giá trị số. Tiếp tục hướng nghiên cứu này, với mục tiêu tìm kiếm các độ đo khoảng cách hiệu quả (có công thức tính toán đơn giản) giải quyết bài toán rút gọn thuộc tính, giảm thiểu thời gian thực hiện, trong phần này chúng tôi xây dựng độ đo khoảng cách mờ mới (sau đây gọi là khoảng cách mờ) dựa trên độ đo khoảng cách phân hoạch trong công trình [48]. Sử dụng khoảng cách mờ được xây dựng, chúng tôi đề xuất phương pháp filter-wrapper rút gọn thuộc tính trong bảng quyết định nhằm nâng cao độ chính xác phân lớp và giảm thiểu số lượng thuộc tính tập rút gọn. 2.3.1. Xây dựng khoảng cách mờ giữa hai tập mờ Cho bảng quyết định  ,DS U C D  với  1 2, ,..., nU x x x , ,P Q C và     i iPK P x x U  ,     i iQK Q x x U  là hai phân hoạch trên P và Q. Trong công trình [48], Liang và các cộng sự đã chứng minh          1 1 , U i iP Q i x x D K P K Q U U          với            i i i i i iP Q P Q P Qx x x x x x     là khoảng cách phân hoạch giữa  K P và  K Q . Dựa trên khoảng cách phân hoạch, trong mục này chúng tôi xây dựng một độ đo khoảng cách giữa hai tập mờ, gọi là khoảng cách mờ. 55 Định nghĩa 2.3. [63] Cho U là tập hữu hạn, khác rỗng các đối tượng. Một độ đo khoảng cách trên U là một ánh xạ  : 0,d U U   thỏa mãn các điều kiện sau với mọi , ,x y z U  1P  , 0d x y  ,  , 0d x y  khi và chỉ khi x y .  2P    , ,d x y d y x .  3P      , , ,d x y d y z d x z  . Điều kiện  3P được gọi là tiên đề bất đẳng thức tam giác. Bổ đề 2.1. Cho ba số thực a, b, m với a b . Khi đó ta có    min , min ,a b a m b m   Mệnh đề 2.1. Cho ba tập mờ , ,A B C trên cùng tập đối tượng U. Khi đó ta có các mệnh đề sau: 1) Nếu A B thì B B C A A C     . 2) Nếu A B thì C C A C C B     . 3) A A B C C A C C B        Chứng minh. 1) Vì A B , với mọi ix U ta có    i iB Ax x  . Áp dụng Bổ đề 2.1 ta có:              min , min ,i i i i i iB B C CA Ax x x x x x                       1 1 1 1 min , min , U U U U i i i i i iB B C CA A i i i i x x x x x x                B A B C A C B B C A A C            2) Vì A B , với mọi ix U ta có    i iB Ax x           min , min ,i i i iB C A Cx x x x                  min , min ,i i i i i iC C C B CAx x x x x x                       1 1 1 1 min , min , U U U U i i i i i iC C C B CA i i i i x x x x x x                 C C A C C B      . 56 3) Từ A C A  , áp dụng tính chất 1) ta có A A B A C A C B       (1) Mặt khác, từ A B B  , áp dụng tính chất 2) ta có C C A B C C B      (2) Từ (1) và (2) ta có: A A B C C A A C A C B C C A             C A B C C C B       . Mệnh đề 2.2. Cho hai tập mờ ,A B trên tập đối tượng U. Khi đó  ,d A B A B A B    là một khoảng cách mờ giữa A và B . Chứng minh. Rõ ràng A B A B   nên  , 0d A B  . Hơn nữa,    , ,d A B d B A . Để  ,d A B là độ đo khoảng cách, ta cần chứng minh bất đẳng thức tam giác. Không mất tính chất tổng quát ta chứng minh      , , ,d A B d A C d B C  . Áp dụng tính chất 3) của Mệnh đề 2.1 ta có: A A B C C A C C B        (1) A A C B B A B B C        (2) Cộng (1) với (2), vế với vế ta được:    2 2 2A B A B A C A C B C B C           (3) Mặt khác, với hai số thực bất kỳ a, b ta luôn có    max , min ,a b a b a b   . Từ đó ta có với mọi ix U ,              max , min ,i i i i i iB B BA A Ax x x x x x        , nghĩa là A B A B A B     . Do đó, từ (3) thu được:    A B A B A C A C B C B C           Hay      , , ,d A B d A C d B C  . Từ đó,  ,d A B là một khoảng cách giữa hai tập mờ A và B , gọi là khoảng cách mờ. Dựa trên khoảng cách mờ này, mục tiếp theo chúng tôi xây dựng khoảng cách phân hoạch mờ. 57 2.3.2. Xây dựng khoảng cách mờ giữa hai phân hoạch mờ Mệnh đề 2.3. Cho bảng quyết định  ,DS U C D  với  1 2, ,..., nU x x x và  PR ,  QR là hai phân hoạch mờ sinh bởi hai quan hệ tương đương mờ PR , QR trên ,P Q C . Khi đó:              2 1 1 , n P Q i i i iP Q P Q i D R R x x x x n        là một khoảng cách mờ giữa  PR và  QR , gọi là khoảng cách phân hoạch mờ. Chứng minh. Rõ ràng     , 0P QD R R   và          , ,P Q Q PD R R D R R    . Ta cần chứng minh bất đẳng thức tam giác. Không mất tính chất tổng quát, với mọi      , ,P Q SR R R   ta chứng minh               , , ,P Q P S Q SD R R D R R D R R       . Từ Mệnh đề 2.2, với mọi ix U ta có:               , , ,i i i i i iP Q P S Q Sd x x d x x d x x  . Từ đó:          , ,P Q P SD R R D R R                     2 2 1 1 1 1n n i i i i i i i iP Q P Q P S P S i i x x x x x x x x n n                              2 2 2 1 1 1 1 1 1 , , , , n n n Q Si i i i i iP Q P S Q S i i i d x x d x x d x x D R R n n n            Dễ thấy rằng,     ,P QD R R  đạt giá trị nhỏ nhất là 0 khi và chỉ khi    P QR R  và     ,P QD R R  đạt giá trị lớn nhất là 1 khi và chỉ khi    PR   và    QR   (hoặc    PR   và    QR   Do đó,     0 , 1P QD R R   . 58 Mệnh đề 2.4. Cho  PR  là một phân hoạch mờ trên , khi đó ta có:          , , 1P PD R D R       Chứng minh. Giả sử         1 2, ,...,P nP P PR x x x  . Khi đó       2 1 1 , n P i P i D R x n       ,        2 1 1 , n P i P i D R n x n       . Từ đó ta có          , , 1P PD R D R       . Mệnh đề 2.5. Cho bảng quyết định  ,DS U C D  với  1 2, ,..., nU x x x và R là quan hệ tương đương mờ xác định trên miền giá trị tập thuộc tính điều kiện, khi đó khoảng cách mờ giữa hai tập thuộc tính C và C D được xác định như sau:            2 1 1 , n C C D i i iC C D i D R R x x x n        Chứng minh. Từ Mệnh đề 2.3 ta có:              2 1 1 , n C C D i i i iC C D C C D i D R R x x x x n                             2 2 1 1 1 1n n i i i i i i i iC C D C D C C D i i x x x x x x x x n n           Dễ thấy rằng      10 , 1C C DD R R n      .     , 0C C DD R R    khi    CR D  và      1, 1C C DD R R n      khi    CR   và    i iDx x với 1 i n  . Mệnh đề 2.6. Cho bảng quyết định  ,DS U C D  với  1 2, ,..., nU x x x , B C và R là quan hệ tương đương mờ xác định trên miền giá trị tập thuộc tính điều kiện. Khi đó          , ,B B D C C DD R R D R R     Chứng minh: Từ B C , theo [93] ta có    C BR R  , nghĩa là    i iC Bx x với 1 i n  , suy ra    i iC Bx x với 1 i n  . Xét đối tượng ix U ta có: 59                    1 1 min , i i iC C D n n i i i j j jx x xC C D j j x x x x x x                             1 1 min , i i iB B D n n i i i j j jx x xB B D j j x x x x x x          (1) Với  j i Dx x ta có     1i D jx x  , do đó            0i i i i i iC C D B B Dx x x x x x      (2) Với  j i Dx x ta có     0i D jx x  , do đó          i i i i iC C D C Bx x x x x          i i iB B Dx x x  . Từ (1), (2) ta có: