Tài liệu Một số phương pháp rút gọn thuộc tính trong bảng quyết định.

  • Số trang: 78 |
  • Loại file: PDF |
  • Lượt xem: 142 |
  • Lượt tải: 0

Mô tả:

ðẠI HỌC THÁI NGUYÊN TRƯỜNG ðẠI HỌC CNTT VÀ TRUYỀN THÔNG HOÀNG THỊ NGỌC MAI MỘT SỐ PHƯƠNG PHÁP RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ðỊNH LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Thái Nguyên - Năm 2013 ðẠI HỌC THÁI NGUYÊN TRƯỜNG ðẠI HỌC CNTT VÀ TRUYỀN THÔNG HOÀNG THỊ NGỌC MAI MỘT SỐ PHƯƠNG PHÁP RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ðỊNH LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Chuyên ngành: Khoa học máy tính Mã số: 60.48.01 NGƯỜI HƯỚNG DẪN KHOA HỌC: GS.TS Vũ ðức Thi Thái Nguyên - Năm 2013 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn MỤC LỤC LỜI CẢM ƠN ......................................................................................................... I LỜI CAM ðOAN ................................................................................................... II DANH MỤC CÁC THUẬT NGỮ ........................................................................ III BẢNG CÁC KÝ HIỆU .........................................................................................IV DANH SÁCH BẢNG............................................................................................VI LỜI MỞ ðẦU ......................................................................................................... 1 Chương 1. KHÁI QUÁT VỀ TẬP THÔ VÀ RÚT GỌN THUỘC TÍNH ................. 5 1.1. Hệ thông tin .................................................................................................... 5 1.2. Tập thô ........................................................................................................... 7 1.3. Bảng quyết ñịnh.............................................................................................. 9 1.4. Tập rút gọn và lõi ........................................................................................... 9 1.5. Ma trận phân biệt và hàm phân biệt .............................................................. 10 1.6. Mối liên hệ giữa các tập rút gọn của các phương pháp rút gọn thuộc tính. .... 11 1.6.1. Entropy trong hệ thông tin và các tính chất. ............................................... 12 1.6.2. Tập rút gọn dựa trên entropy thông tin ....................................................... 14 1.6.3. Mối liên hệ của tập rút gọn dựa trên Shannon entropy ............................... 15 1.6.4. Mối liên hệ của tập rút gọn dựa trên ñộ khác biệt giữa các tri thức............. 19 1.7. Sự thay ñổi các ñộ ño ñánh giá hiệu năng bảng quyết ñịnh khi rút gọn thuộc tính. ..................................................................................................................... 22 1.7.1. Luật quyết ñịnh và các ñộ ño cổ ñiển ......................................................... 23 1.7.2. ðộ ño hiệu năng cải tiến của bảng quyết ñịnh ............................................ 24 1.7.3. ðề xuất ñộ ño hiệu năng mới của bảng quyết ñịnh ..................................... 25 1.7.4. Sự thay ñổi các ñộ ño khi thực hiện các phương pháp rút gọn thuộc tính ... 29 1.8. Kết luận Chương 1 ....................................................................................... 31 Chương 2. MỘT SỐ PHƯƠNG PHÁP RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ðỊNH. ..................................................................................................... 32 2.1. Mở ñầu ......................................................................................................... 32 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2.2. Thuật toán tìm tập rút gọn sử dụng Liang entropy......................................... 39 2.2.1. Tập rút gọn dựa trên Liang entropy với phân hoạch cải tiến..................... 40 2.2.2. Thuật toán tìm tập rút gọn sử dụng Liang entropy.................................... 43 2.3. Thuật toán tìm tập rút gọn sử dụng metric .................................................. 48 2.3.1. Khoảng cách Jaccard giữa hai tập hợp hữu hạn ........................................ 49 2.3.2. Metric trên hệ thông tin ........................................................................... 50 2.3.3. Tập rút gọn dựa trên metric ..................................................................... 51 2.3.4. Thuật toán tìm tập rút gọn sử dụng metric ............................................... 54 2.3.5. Thuật toán tìm tập rút gọn theo ngưỡng chắc chắn của bảng quyết ñịnh ........ 59 2.4. Kết luận Chương 2 ..................................................................................... 61 Chương 3: CHƯƠNG TRÌNH THỬ NGHIỆM ..................................................... 62 3.1. Bài toán ..................................................................................................... 62 3.2. Phương pháp .............................................................................................. 62 3.3. Xây dựng chương trình thử nghiệm ............................................................ 63 3.4. Kết quả thử nghiệm ................................................................................... 64 3.5. Kết luận chương 3 ..................................................................................... 65 KẾT LUẬN ........................................................................................................... 66 TÀI LIỆU THAM KHẢO ..................................................................................... 67 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn I LỜI CẢM ƠN Tôi xin chân thành cảm ơn ñến: - Trường ðại học Công nghệ thông tin và Truyền thông, ðại học Thái Nguyên - Viện Công nghệ Thông tin và các thầy cô giáo ñã trực tiếp giảng dạy, hướng dẫn tôi trong quá trình học tập và ñịnh hướng quan trọng trong việc hình thành ý tưởng nghiên cứu. Tôi xin chân thành cảm ơn Chi bộ, BGH, BCH Công ñoàn, Tổ Khoa học tự nhiên và cán bộ giáo viên, nhân viên Trường THPT Bình ðộ ñã ñộng viên, giúp ñỡ, tạo ñiều kiện thuận lợi cho tôi trong quá trình học tập và nghiên cứu. ðặc biệt, tôi xin bày tỏ lòng biết ơn sâu sắc ñến GS.TS Vũ ðức Thi, người thầy ñã trực tiếp hướng dẫn và giúp ñỡ tôi hoàn thành luận văn tốt nghiệp. Cuối cùng xin chân thành cảm ơn những người thân và gia ñình ñã luôn chia sẻ mọi khó khăn và là chỗ dựa vững chắc về vật chất, tinh thần ñể tôi hoàn thành chương trình khóa học cũng như trong suốt thời gian hoàn thành luận văn. Mặc dù ñã có nhiều cố gắng, nhưng do thời gian có hạn và bản thân còn những hạn chế nhất ñịnh nên luận văn không tránh khỏi thiếu sót. Mong nhận ñược các ý kiến phê bình, góp ý của Hội ñồng chấm luận văn, các thầy cô giáo và ñồng nghiệp ñể công trình nghiên cứu ñược hoàn chỉnh hơn. Thái Nguyên, tháng 01 năm 2013 Tác giả Hoàng Thị Ngọc Mai Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn II LỜI CAM ðOAN Tôi xin cam ñoan luận văn này là công trình do tôi tổng hợp và nghiên cứu. Trong luận văn có sử dụng một số tài liệu tham khảo như ñã nêu trong phần tài liệu tham khảo. Tác giả Luận văn Hoàng Thị Ngọc Mai Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn III DANH MỤC CÁC THUẬT NGỮ Tập thô Rough Set Hệ thông tin Information System Hệ thông tin ñầy ñủ Complete Information System Bảng quyết ñịnh Decision Table Bảng quyết ñịnh ñầy ñủ Comple Decision Table Bảng quyết ñịnh không nhất quán Inconsistent Decision Table Quan hệ không phân biệt ñược Indiscernibility Relation Rút gọn thuộc tính Attribute Reduction Tập rút gọn Reduct Tập lõi Core Shannon entropy Entropy Liang entropy Entropy mới của Jiye Liang trong [28] Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn IV BẢNG CÁC KÝ HIỆU IS = (U , A,V , f ) DS = (U , C ∪ D, V , f ) Hệ thông tin Cho bảng quyết ñịnh U Số ñối tượng C Số thuộc tính ñiều kiện trong bảng quyết ñịnh u (a) Giá trị ñối tượng của u của thuộc tính a [ u ]B Lớp tương ñương chứa u của quan hệ IND ( B ) SB ( u ) Lớp dung sai của ñối tượng u trên quan hệ SIM ( B ) U/B Phân hoạch U sinh bởi tập thuộc tính B BX B - xấp xỉ dưới của X BX B - xấp xỉ trên của X BN B ( X ) B - miền biên của X POS B ( D ) B - miền dương của D PRED ( C ) Tập tất cả các rút gọn dựa trên miền dương HRED ( C ) Tập tất cả các rút gọn dựa trên Shannon entropy SRED ( C ) Tập tất cả các rút gọn của phương pháp ma trận phân biệt ERED ( C ) Tập tất cả các rút gọn dựa trên Liang entropy NERED ( C ) Tập tất cả các rút gọn dựa trên Liang entropy với phân hoạch cải tiến. MRED ( C ) Tập tất cả các rút gọn dựa trên metric KRED ( C ) Tập tất cả các rút gọn dựa trên ñộ ño lượng tri thức khác nhau. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn V COREP ( C ) Tập lõi dựa trên miền dương COREH ( C ) Tập lõi dựa trên Shannon entropy CORES ( C ) Tập lõi của phương pháp ma trận phân biệt. COREE ( C ) Tập lõi dựa trên Liang entropy. COREM ( C ) Tập lõi dựa trên metric COREK ( C ) Tập lõi dựa trên ñộ ño lượng tri thức khác nhau. H ( P) Shannon entropy của tập thuộc tính P H (Q \ P ) Shannon entropy có ñiều kiện của Q khi ñã biết P E ( P) Liang entropy của tập thuộc tính P E (Q \ P ) Liang entropy có ñiều kiện của Q khi ñã biết P K ( P) Tri thức sinh bởi tập thuộc tính P d ( K ( P ) , K (Q)) Metric giữa hai tri thức K ( P ) và K ( Q ) trên hệ thông tin ñầy ñủ sử dụng khoảng cách Jaccard giữa hai tập hợp. DQP ( K ( P ) , K ( Q ) ) Lượng tri thức khác nhau giữa K ( P ) và K ( Q ) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn VI DANH SÁCH BẢNG Bảng 1.1. Bảng thông tin về bệnh cúm ........................................................... 6 Bảng 1.3. Bảng quyết ñịnh minh họa Ví dụ 1.3 ............................................ 18 Bảng 1.4. Bảng quyết ñịnh minh họa Ví dụ 1.4 ............................................ 46 Bảng 2.1. Bảng quyết ñịnh minh họa Ví dụ 2.1. ........................................... 46 Bảng 2.2. Bảng quyết ñịnh về bệnh cảm cúm ............................................... 53 Bảng 2.3. Bảng quyết ñịnh minh họa Ví dụ 2.5 ............................................ 57 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1 LỜI MỞ ðẦU 1. Tính cấp thiết của ñề tài Hiện nay, trên thế giới có rất nhiều thuật toán khai phá tri thức bằng cách phân lớp và rời rạc dữ liệu như: Sử dụng cây quyết ñịnh, phương pháp thống kê, các mạng nơ ron, thuật toán di truyền,...Trong một vài năm gần ñây, lý thuyết tâp thô ñược nhiều nhóm nghiên cứu hoạt ñộng trong lĩnh vực tin học nói chung và khai phá tri thức nói riêng nghiên cứu và áp dụng trong thực tế. Lý thuyết tập thô ñược xây dựng trên nền tảng toán học vững chắc giúp cung cấp những công cụ hữu ích ñể giải quyết những bài toán phân lớp dữ liệu và khai phá luật,...Lý thuyết tập thô do Zdzisaw Pawlak ñề xuất vào những năm ñầu thập niên tám mươi của thế kỉ hai mươi - ñược xem là công cụ hữu hiệu ñể giải quyết các bài toán phân lớp, phát hiện luật… chứa dữ liệu mơ hồ, không chắc chắn. Từ khi xuất hiện, lý thuyết tập thô ñã ñược sử dụng hiệu quả trong các bước của quá trình khai phá dữ liệu và khám phá tri thức, bao gồm rời rạc hóa dữ liệu, rút gọn thuộc tính, trích lọc các tri thức tiềm ẩn trong dữ liệu dưới dạng các mẫu, các luật quyết ñịnh. Trong lý thuyết tập thô, dữ liệu ñược biểu diễn thông qua một hệ thống thông tin IS = (U , A) với U là tập các ñối tượng và A là tập các thuộc tính. Mỗi tập thuộc tính B ⊆ A xác ñịnh một quan hệ tương ñương IND ( B ) trên U còn gọi là quan hệ không phân biệt ñược. Rút gọn thuộc tính là bài toán quan trọng nhất trong lý thuyết tập thô. Mục tiêu của bài toán rút gọn thuộc tính trong bảng quyết ñịnh là loại bỏ (tối ña) các thuộc tính dư thừa mà phần thuộc tính còn lại cũng chứa ñầy ñủ thông tin của bảng. Dựa vào tập thuộc tính rút gọn thu ñược, việc sinh luật và phân lớp Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2 ñạt hiệu quả cao nhất. ðối với một bảng quyết ñịnh có thể có nhiều tập rút gọn khác nhau. Tuy nhiên, trong thực tế thường không ñòi hỏi tìm tất cả các tập rút gọn mà chỉ cần tìm ñược một tập rút gọn “tốt nhất” theo một tiêu chuẩn ñánh giá nào ñó là ñủ. Vì vậy, phần lớn các phương pháp rút gọn thuộc tính ñều ñề xuất các thuật toán heuristic tìm tập rút gọn theo một tiêu chuẩn tối ưu ñặt ra. Trong mấy năm gần ñây chứng kiến sự phát triển mạnh mẽ và sôi ñộng của các nghiên cứu về rút gọn thuộc tính. Phần lớn các nghiên cứu này ñều tập trung vào ba phương pháp: phương pháp dựa trên miền dương; phương pháp sử dụng các ñộ ño không chắc chắn và phương pháp sử dụng ma trận phân biệt. Lĩnh vực nghiên cứu ñộ ño không chắc chắn của tri thức trong mấy năm gần ñây tập trung vào hai hướng tiếp cận chính là entropy thông tin và hạt tri thức. Một lớp ñặc biệt của các hệ thông tin ñóng vai trò quan trọng trong nhiều ứng dụng là bảng quyết ñịnh. Bảng quyết ñịnh DS là một hệ thống thông tin với tập thuộc tính A ñược chia thành hai tập con khác rỗng rời nhau C và D . Nói cách khác, DS = (U , C ∪ D ) với C ∩ D = ∅ . Bảng quyết ñịnh là nhất quán khi phụ thuộc hàm C → D là ñúng. ðối với bảng quyết ñịnh nhất quán, tập con các thuộc tính ñiều kiện R ⊆ C ñược gọi là một tập rút gọn của bảng quyết ñịnh nếu R là tập tối thiểu thỏa mãn phụ thuộc hàm R → D . Nếu xem bảng quyết ñịnh là quan hệ r trên tập thuộc tính C ∪ D và D chỉ chứa một thuộc tính duy nhất {d } thì khái niệm tập rút gọn trong bảng quyết ñịnh tương ñương với khái niệm tập tối thiểu của thuộc tính {d } trên quan hệ. Khi ñó, các bài toán liên quan ñến tập rút gọn trong bảng quyết ñịnh có thể giải quyết bằng các kết quả liên quan ñến tập tối thiểu của một thuộc tính trên quan hệ trong lý thuyết cơ sở dữ liệu quan hệ. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 3 Xuất phát từ những lý do trên, tôi chọn và nghiên cứu ñề tài luận văn: “Một số phương pháp rút gọn thuộc tính trong bảng quyết ñịnh”. 2. Mục tiêu của luận văn Mục tiêu của luận văn là tìm hiểu một số vấn ñề liên quan ñến phương pháp rút gọn thuộc tính trong hệ thông tin và xây dựng chương trình thử nghiệm một số thuật toán liên quan ñến tập rút gọn trong bảng quyết ñịnh. 3. Các ñóng góp của luận văn Luận văn ñã có hai ñóng góp chính sau: Thứ nhất là nghiên cứu mối liên hệ giữa các tập rút gọn của các phương pháp rút gọn thuộc tính, tìm hiểu các ñộ ño cải tiến ñánh giá hiệu năng bảng quyết ñịnh và nghiên cứu sự thay ñổi của các ñộ ño này khi thực hiện các phương pháp rút gọn thuộc tính. Thứ hai là xây dựng toán heuristic tìm tập rút gọn của bảng quyết ñịnh ñầy ñủ sử dụng Liang entropy và metric. 4. Bố cục luận văn Luận văn ñược viết trong ba chương, gồm 66 trang Chương một khái quát về tập thô và rút gọn thuộc tính. Chương hai trình bày kết quả nghiên cứu về ba vấn ñề. Thứ nhất nghiên cứu mối liên hệ giữa các tập rút gọn của các phương pháp rút gọn thuộc tính, bao gồm phương pháp dựa trên miền dương, phương pháp sử dụng các ñộ ño không chắc chắn (entropy thông tin, hạt tri thức) và phương pháp sử dụng ma trận phân biệt. Thứ hai là tìm hiểu các ñộ ño cải tiến ñánh gia hiệu năng của bảng quyết ñịnh và nghiên cứu sự thay ñổi của các ñộ ño này khi thực hiện các phương pháp rút gọn thuộc tính. Thứ ba là ñề xây dựng chương trình thử nghiệm thuật toán heuristic (Thuật toán 2.2, Thuật toán 2.4 và Thuật toán 2.5). Thuật toán 2.5 tìm tập rút gọn Pawlak sử dụng Liang entropy, Thuật toán 2.4 tìm tập rút gọn trong bảng quyết ñịnh sử dụng metric, Thuật toán 2.5 là Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 4 cải tiến của Thuật toán 2.4 tìm tập rút gọn theo tham số là ngưỡng chắc chắn của bảng quyết ñịnh. Các thuật toán trên ñều có ñộ phức tạp tính toán trong thời gian ña thức và hiệu quả hơn các thuật toán khác ñã công bố. Chương 3 Chương trình thử nghiệm xây dựng bảng quyết ñịnh dựa trên Thuật toán 2.4 tìm tập rút gọn sử dụng metric ñã trình bày trong Chương 2. Kết quả thử nghiệm của chương trình thực hiện trên công cụ mã nguồn mở NetBeans IDE 7.1.2 Cuối cùng, phần kết luận nêu những ñóng góp của luận văn, hướng phát triển và những vấn ñề quan tâm của tác giả. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 5 Chương 1. KHÁI QUÁT VỀ TẬP THÔ VÀ RÚT GỌN THUỘC TÍNH 1.1. Hệ thông tin Hệ thông tin là công cụ biểu diễn tri thức dưới dạng một bảng dữ liệu gồm P cột ứng với P thuộc tính và n hàng ứng với n ñối tượng. Một cách hình thức, nó ñược ñịnh nghĩa như sau: ðịnh nghĩa 1.1. Hệ thống thông tin là một bộ tứ IS = (U , A,V , f ) trong ñó U là tập hữu hạn, khác rỗng các ñối tượng; A là tập hữu hạn, khác rỗng các thuộc tính; V = ∏ Va với Va là tập giá trị của thuộc tính a ∈ A ; f là hàm thông tin, a∈ A với mọi a ∈ A và u ∈U hàm f cho giá trị f ( u, a ) ∈Va . Với mỗi u ∈U , a ∈ A , ta kí hiệu giá trị của ñối tượng u tại thuộc tính a là u ( a ) thay vì f ( u , a ) . Nếu B = {b1 , b2 ,..., bk } ⊆ A là một tập con các thuộc tính thì ta sẽ ký hiệu bộ các giá trị u ( bi ) bởi u ( B ) . Như vậy, nếu u và v là hai ñối tượng, thì ta sẽ viết u ( B ) = v ( B ) nếu u ( bi ) = v ( bi ) với mọi i = 1,..., k . Cho hệ thông tin IS = (U , A,V , f ) . Với mỗi tập con các thuộc tính p ⊆ A , tồn tại một quan hệ hai ngôi trên U , ký hiệu là IND ( P ) , xác ñịnh bởi IND ( P ) = {( u , v ) ∈U × U | ∀a ∈ P, f ( u , a ) = f ( v, a )} . IND ( P ) ñược gọi là quan hệ B - không phân biệt ñược. Dễ thấy rằng ñây là một quan hệ tương ñương trên U . Nếu ( v, u ) ∈ IND ( B ) thì hai ñối tượng u và v không phân biệt bởi các thuộc tính trong B . Ký hiệu phân hoạch của U sinh bởi quan hệ tương ñương IND ( P ) là U / IND ( P ) , viết tắt là U / P . Mỗi phần tử trong U / P là một lớp tương ñương hay một khối. Ký hiệu lớp tương ñương U / P chứa ñối tượng u là [u ]P , khi ñó, [u ]P = {v ∈U | ( u, v ) ∈ IND ( P )} . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 6 ðịnh nghĩa 1.2. [11, 12] Cho hệ thống thông tin IS = (U , A,V , f ) với P, Q ⊆ A . Ta nói: 1) U / P = U / Q khi và chỉ khi ∀u ∈ U , [u ]P = [u ]Q 2) U / P ≤ U / Q khi và chỉ khi ∀u ∈ U , [u ]P ⊆ [u ]Q ; 3) U / P < U / Q khi và chỉ khi ∀u ∈ U , [u ]P ⊆ [u ]Q và tồn tại v sao cho [ v ]P ⊆ [ v ]Q Tính chất 1.1. [11, 12] Xét hệ thống thông tin S = (U , A,V , f ) và P, Q ⊆ A . Nếu P ⊆ Q thì U / Q ≤ U / P . Tính chất 1.2. [11, 12] Xét hệ thông tin IS = (U, A, V, ƒ) và P, Q ⊆ A . Với mọi u ∈ U ta có [u ]P ∪Q = [u ]P ∩ [u ]Q . Ví dụ 1.1. Xét hệ thông tin IS = (U , A,V , f ) biểu diễn các triệu chứng cúm của bệnh nhân cho ở Bảng 1.1 với U = ( u1 , u2 , u3 , u4 , u5 , u6 , u7 , u8 ) , C = ( a1 , a2 , a3 ) với a1 (ðau ñầu), a2 (Thân nhiệt), a3 (Cảm cúm). ðau ñầu U Thân nhiệt Cảm cúm u1 Có Bình thường Không u2 Có Cao Có u3 Có Rất cao Có u4 Không Bình thường Không u5 Không Cao Không u6 Không Rất cao Có u7 Không Cao Có u8 Không Rất cao Không Bảng 1.1. Bảng thông tin về bệnh cúm Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 7 Ta có U / {a1} = {{u1 , u2 , u3} , {u4 , u5 , u6 , u7 , u8 }} , U / {a2 } = {{u1 , u4 } , {u2 , u5 , u7 } , {u3 , u6 , u8 }} , U / {a3 } = {{u1 , u4 , u5 , u8 } , {u2 , u3 , u6u7 }} , U / {a1 , a2 } = {{u1} , {u2 } , {u3 } , {u4 }{u5 , u7 } , {u6 , u8 }} Như vậy, các bệnh nhân u2 , u3 không phân biệt nhau về ñau ñầu ( a1 ) và cảm cúm ( a3 ) , nhưng phân biệt ñược về thân nhiệt ( a2 ) . 1.2. Tập thô Cho hệ thông tin IS = (U , A,V , f ) và tập ñối tượng X ⊆ U . Với một tập thuộc tính B ⊆ A cho trước, chúng ta có các lớp tương ñương của phân hoạch U / B , thế thì một tập ñối tượng X có thể biểu diễn thông qua các lớp tương ñương này như thế nào? Trong lý thuyết tập thô, ñể biểu diễn X thông qua các lớp tương ñương của U / B (còn gọi là biểu diễn X bằng tri thức sẵn có B ), người ta xấp xỉ X bởi hợp của một số hữu hạn các lớp tương ñương của U / B . Có hai cách xấp xỉ tập ñối tượng X thông qua thuộc tính B , ñược gọi là B -xấp xỉ dưới và B xấp xỉ trên của X , ký hiệu lần lượt là BX và BX ñược xác ñịnh như sau: BX = {u ∈ U | [u ]B ⊆ X } , BX = {u ∈ U | [u ]B ∩ X ≠ ∅} . Tập BX bao gồm tất cả các phần tử của U chắc chắn thuộc vào X , còn tập BX bao gồm các phần tử của U có khả năng ñược phân loại vào X dựa vào tập thuộc tính B . Từ hai tập xấp xỉ nêu trên, ta ñịnh nghĩa các tập BN B ( X ) = BX − BX : B - miền biên của X . U − BX : B -miền ngoài của X Dễ thấy B - miền biên của X là tập chứa các ñối tượng có thể thuộc X , còn miền B - miền ngoài của X chứa các ñối tượng chắc chắn không thuộc Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 8 X . Sử dụng các lớp của phân hoạch U / B , các xấp xỉ dưới và trên của X có thể viết lại. BX =U{Y ∈U / B | Y ⊆ X } . BX = U{Y ∈U / B | Y ∩ X = ∅} . Trong trường hợp BN B ( X ) = ∅ , X ñược gọi là tập rõ, ngược lại X ñược gọi là tập thô. Với B, D ⊆ A , ta gọi B - miền dương của D là tập ñược xác ñịnh như sau POS B ( D ) = U BX X ∈U / D Rõ ràng POS B ( D ) là tập tất cả ñối tượng u sao cho với mọi v ∈U mà ta u ( B) = v ( B) ñều có u ( D) = v ( D) . Nói cách khác, POS B ( D ) = {u ∈ U | [u ]B ⊆ [u ]D } . Ví dụ 1.2. Xét hệ thông tin IS = (U , A,V , f ) ở Ví dụ 1.1. Với B = {a1 , a2 } và X = {u2 , u3 , u6 , u7 } ta có U / B = {{u1} , {u2 } , {u3 } , {u4 } , {u5 , u7 } , {u6 , u8 }} . Do ñó, BX = {u2 , u3 } và BX = {u2 , u3 , u5 , u6 , u7 , u8 } . Như vậy, B -miền biên của X là tập hợp BN B ( X ) = {u5 , u6 , u7 , u8 } . Nếu ñặt D = {a3 } thì U / D = { X 1 = {u1 , u4 , u5 , u8 } , X 2 = {u2 , u3 , u6 , u7 }} . BX 1 = {u1 , u4 } , BX 2 = {u2 , u3 } . Do ñó, POSB ( D ) = U ( BX ) = {u1 , u2 , u3 , u4 } . X ∈U / D Với các khái niệm của tập xấp xỉ ñối với phân hoạch U / B , các tập thô ñược chia thành bốn loại như sau: 1) Tập X là B - xác ñịnh thô nếu BX ≠ ∅ và BX ≠ U 2) Tập X là B - không xác ñịnh trong nếu BX = ∅ và BX ≠ U 3) Tập X là B - không xác ñịnh ngoài nếu BX ≠ ∅ và BX = U 4) Tập X là B - không xác ñịnh hoàn toàn nếu BX ≠ ∅ và BX = U . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 9 1.3. Bảng quyết ñịnh Một lớp ñặc biệt của các hệ thống thông tin có vai trò quan trọng trong nhiều ứng dụng là bảng quyết ñịnh. Bảng quyết ñịnh là một dạng ñặc biệt của hệ thông tin, trong ñó tập các thuộc tính A bao gồm hai tập con rời nhau: tập các thuộc tính ñiều kiện C và tập các thuộc tính quyết ñịnh D . Như vậy, bảng quyết ñịnh là một hệ thống thông tin DS = (U , C ∪ D,V , f ) trong ñó C ∩ D = ∅ . Bảng quyết ñịnh DS ñược gọi là nhất quán khi và chỉ khi phụ thuộc hàm C → D nghiệm ñúng, nghĩa là với mọi u , v ∈ U , u (C ) = v(C ) kéo theo u ( D) = v( D) . Ngược lại, DS là không nhất quán. Dễ thấy bảng quyết ñịnh DS là nhất quán khi và chỉ khi POSC ( D) = U . Trong trường hợp bảng không nhất quán thì POSC ( D ) chính là tập con cực ñại của U sao cho phụ thuộc hàm C → D ñúng. 1.4. Tập rút gọn và lõi Trong bảng quyết ñịnh, các thuộc tính ñiều kiện ñược chia thành ba nhóm: thuộc tính lõi, thuộc tính cơ bản (hay thuộc tính rút gọn) và thuộc tính dư thừa (hay thuộc tính không cần thiết). - Thuộc tính lõi là thuộc tính cần thiết và cốt yếu, không thể thiếu trong việc phân lớp chính xác tập dữ liệu. - Thuộc tính dư thừa là những thuộc tính không cần thiết, nghĩa là có thể loại bỏ các thuộc tính như vậy mà không ảnh hưởng ñến việc phân lớp dữ liệu. - Thuộc tính cơ bản là thuộc tính nằm trong một tập rút gọn nào ñó. Ta sẽ ñưa ra các ñịnh nghĩa chính xác như sau: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 10 ðịnh nghĩa 1.3. Cho bảng quyết ñịnh DS = (U , C ∪ D,V , f ) , thuộc tính a ∈ C ñược gọi là cần thiết nếu POSC ( D ) ≠ POS(C −{a}) ( D) . Tập tất cả các thuộc tính cần thiết trong DS ñược gọi là tập lõi và kí hiệu là COREP (C ) . ðịnh nghĩa 1.4. Cho bảng quyết ñịnh DS = (U , C ∪ D,V , f ) . Nếu R ⊆ C thỏa mãn: 1) POS R ( D) = POSC ( D) 2) POS R ( D) ≠ POSC ( D ) với ∀R ' ⊂ R thì R là một rút gọn của C ' Tập rút gọn ñịnh nghĩa như trên gọi là một tập rút gọn dựa trên miền dương theo Pawlak. ðịnh nghĩa 1.4 cho thấy, R là tập rút gọn nếu nó là tập tối thiểu thỏa mãn POSR ( D) = POSC ( D) . Có thể tồn tại nhiều tập rút gọn của C . Ta kí hiệu PREDP ( C ) là tập tất cả các rút gọn theo Pawlak của C . Khi ñó, COREP (C ) = I R. R∈PRED ( C ) Từ ñịnh nghĩa về tập lõi và tập rút gọn, ta ñịnh nghĩa thuộc tính dư thừa và thuộc tính cơ bản trong bảng quyết ñịnh như sau: ðịnh nghĩa 1.5. Cho bảng quyết ñịnh DS = (U , C ∪ D, V , f ) và a ∈ C . Ta nói rằng a là thuộc tính cơ bản của C nếu tồn tại một rút gọn R ∈ PRED(C ) sao cho a∈R . ðịnh nghĩa 1.6. Cho bảng quyết ñịnh DS = (U , C ∪ D, V , f ) và a ∈ C . Ta nói rằng a là thuộc tính dư thừa của C nếu a ∈ C − U R. R∈PRED ( C ) 1.5. Ma trận phân biệt và hàm phân biệt Người ñầu tiên xây dựng phương pháp rút gọn thuộc tính trong bảng quyết ñịnh là Skowron. Ông ñã ñưa ra khái niệm ma trận phân biệt và hàm phân biệt, từ ñó ñưa ra phương pháp tìm tập rút gọn sử dụng hàm phân biệt. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
- Xem thêm -