Luận văn Thạc sĩ Hệ thống thông tin: Nghiên cứu các tập rút gọn và luật trong bảng quyết định theo tiếp cận lý thuyết tập thô

Chia sẻ: Tomjerry001 | Ngày: | Loại File: PDF | Số trang:54

Thêm vào BST

Báo xấu

21
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục tiêu nghiên cứu của đề tài là Tổng hợp các phương pháp rút gọn thuộc tính và trích lọc luật trong bảng quyết định theo tiếp cận lý thuyết tập thô trong tài liệu; Xây dựng và thử nghiệm phương pháp rút gọn thuộc tính sử dụng độ đo khoảng cách.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Hệ thống thông tin: Nghiên cứu các tập rút gọn và luật trong bảng quyết định theo tiếp cận lý thuyết tập thô

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ HỒNG HẠNH NGHIÊN CỨU CÁC TẬP RÚT GỌN VÀ LUẬT TRONG BẢNG QUYẾT ĐỊNH THEO TIẾP CẬN LÝ THUYẾT TẬP THÔ LUẬN VĂN THẠC SĨ HỆ THỐNG THÔNG TIN Hà Nội - 2015
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ HỒNG HẠNH NGHIÊN CỨU CÁC TẬP RÚT GỌN VÀ LUẬT TRONG BẢNG QUYẾT ĐỊNH THEO TIẾP CẬN LÝ THUYẾT TẬP THÔ Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60.48.05 LUẬN VĂN THẠC SĨ HỆ THỐNG THÔNG TIN Người hướng dẫn: TS. Nguyễn Long Giang Hà Nội - 2015
1 MỤC LỤC MỤC LỤC............................................................................................................................................................. 1 Danh mục các thuật ngữ...................................................................................................................................... 3 Danh sách bảng ..................................................................................................................................................... 4 MỞ ĐẦU ............................................................................................................................................................... 5 Chương 1. TỔNG QUAN VỀ LÝ THUYẾT TẬP THÔ........................................................................ 8 1.1. Hệ thông tin ..................................................................................................................... 8 1.2. Mô hình tập thô ............................................................................................................... 9 1.3. Bảng quyết định ............................................................................................................ 11 1.4. Tập rút gọn và tập lõi .................................................................................................... 12 1.5. Ma trận phân biệt và hàm phân biệt ............................................................................ 14 Chương 2. RÚT GỌN THUỘC TÍNH VÀ TRÍCH LỌC LUẬT TRONG BẢNG QUYẾT ĐỊNH THEO TIẾP CẬN TẬP THÔ .................................................................... 15 2.1. Rút gọn thuộc tính và trích lọc luật trong bảng quyết định ....................................... 15 2.1.1. Tổng kết, phân nhóm các phương pháp rút gọn thuộc tính .............................15 2.1.2. Luật quyết định và các độ đo đánh giá hiệu năng ............................................20 2.1.3. Lựa chọn, so sánh, đánh giá các phương pháp rút gọn thuộc tính ...................23 2.2. Xây dựng phương pháp rút gọn thuộc tính trong bảng quyết định sử dụng khoảng cách 25 2.2.1. Độ đo khoảng cách ..........................................................................................26 2.2.2. Xây dựng khoảng cách giữa hai tri thức và các tính chất ................................27 2.2.3. Phương pháp rút gọn thuộc tính sử dụng khoảng cách ....................................31 2.2.4. Phân nhóm phương pháp rút gọn thuộc tính sử dụng khoảng cách .................36 Chương 3. THỬ NGHIỆM VÀ ĐÁNH GIÁ KẾT QUẢ .................................................. 38 3.1. Bài toán .......................................................................................................................... 38 3.2. Phân tích, lựa chọn công cụ ......................................................................................... 38 3.2.1. Thuật toán tìm tập rút gọn sử dụng entropy Liang ..........................................39 3.2.2. Lựa chọn công cụ và cài đặt ............................................................................40 3.3. Một số kết quả thử nghiệm........................................................................................... 40 3.3.1. Kết quả thử nghiệm thuật toán tìm tập rút gọn sử dụng khoảng cách .............40
2 3.3.2. Kết quả thử nghiệm về trích lọc luật theo tiếp cận tập thô ..............................42 KẾT LUẬN.........................................................................................................................................................46 Tài liệu tham khảo ..............................................................................................................................................47 Phụ lục ...................................................................................................................................................................49
3 Danh mục các thuật ngữ Thuật ngữ tiếng Việt Thuật ngữ tiếng Anh Tập thô Rough Set Hệ thông tin Information System Bảng quyết định Decision Table Quan hệ không phân biệt được Indiscernibility Relation Xấp xỉ dưới Lower Approximation Xấp xỉ trên Upper Approximation Rút gọn thuộc tính Attribute Reduction Tập rút gọn Reduct Tập lõi Core Luật quyết định Decision Rule Khoảng cách Distance
4 Danh sách bảng Bảng 1.1. Bảng thông tin về bệnh cúm ............................................................................... 10 Bảng 1.2. Bảng quyết định về bệnh cúm ............................................................................. 13 Bảng 2.1. Các phương pháp rút gọn thuộc tính trong tài liệu [1] ...................................... 16 Bảng 2.2. Bảng quyết định về các xe hơi ............................................................................ 20 Bảng 2.1. Bảng quyết định minh họa thuật toán tìm tập rút gọn........................................... 34 Bảng 3.1. Kết quả thực hiện Thuật toán ELBAR và Thuật toán DBAR .............................. 40 Bảng 3.2. Tập rút gọn của Thuật toán ELBAR và Thuật toán DBAR ................................. 41 Bảng 3.3. Kết quả thực hiện Thuật toán ELBAK và Thuật toán DBAK .............................. 42 trên các bộ số liệu lớn .......................................................................................................... 42 Bảng 3.7. Tập rút gọn tốt nhất của bộ số liệu Soybean-small ........................................... 44 Bảng 3.8. Các luật phân lớp trên bảng quyết định rút gọn sử dụng tập thô ....................... 44
5 MỞ ĐẦU Lý thuyết tập thô - do Zdzislaw Pawlak [7] đề 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 không đầy đủ, 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 tiền xử lý số liệu, khai phá dữ liệu và đánh giá kết quả thu được. Rút gọn thuộc tính và trích lọc luật quyết định (luật phân lớp) là hai ứng dụng chính của lý thuyết tập thô trong khai phá dữ liệu. Rút gọn thuộc tính thuộc giai đoạn tiền xử lý dữ liệu còn trích lọc luật thuộc giai đoạn khai phá dữ liệu. Mục tiêu của rút gọn thuộc tính là loại bỏ các thuộc tính dư thừa nhằm tìm tập con nhỏ nhất của tập thuộc tính điều kiện (tập rút gọn) mà bảo toàn thông tin phân lớp của bảng quyết định. Dựa trên tập rút gọn thu được, việc sinh luật và phân lớp đạt hiệu quả cao nhất. Trong hai thập kỷ trở lại đây, chủ đề nghiên cứu về rút gọn thuộc tính trong bảng quyết định theo tiếp cận lý thuyết tập thô đã thu hút đông đảo cộng đồng nghiên cứu về tập thô tham gia [1]. Có rất nhiều phương pháp rút gọn thuộc tính khác nhau đã được đề xuất sử dụng các độ đo khác nhau. Các phương pháp điển hình được tổng kết trong tài liệu [1] là: phương pháp dựa trên miền dương, phương pháp dựa trên ma trận phân biệt, các phương pháp sử dụng độ đo entropy trong lý thuyết thông tin, các phương pháp sử dụng độ đo trong tính toán hạt, các phương pháp sử dụng độ đo khoảng cách… Với mong muốn tổng hợp các kết quả nghiên cứu về các phương pháp rút gọn thuộc tính trong bảng quyết định theo tiếp cận tập thô, trên cơ sở đó xây dựng phương pháp sử dụng một độ đo mới (độ đo khoảng cách), luận văn đặt ra hai mục tiêu chính sau đây:
6 1) Tổng hợp các phương pháp rút gọn thuộc tính và trích lọc luật trong bảng quyết định theo tiếp cận lý thuyết tập thô trong tài liệu [1, 2], bao gồm: - Phân nhóm các phương pháp rút gọn thuộc tính và mối liên hệ giữa các phương pháp dựa vào định nghĩa tập rút gọn. - Trích lọc luật trong bảng quyết định, bao gồm: luật quyết định và các độ đo đánh giá hiệu năng, sự thay đổi các độ đo đánh giá hiệu năng trên các tập rút gọn và đánh giá các phương pháp dựa trên tiêu chuẩn chất lượng phân lớp (độ hỗ trợ) của tập luật. 2) Xây dựng và thử nghiệm phương pháp rút gọn thuộc tính sử dụng độ đo khoảng cách, bao gồm: đề xuất độ đo khoảng cách và xây dựng công thức tính khoảng cách giữa hai tập thuộc tính; định nghĩa tập rút gọn và độ quan trọng của thuộc tính dựa trên khoảng cách; 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 khoảng cách; phân nhóm và đánh giá phương pháp sử dụng khoảng cách với các phương pháp đã có và thử nghiệm phương pháp trên các bộ số liệu mẫu từ kho dữ liệu UCI [12]. Đối tượng nghiên cứu của luận văn là các bảng quyết định với kích thước trung bình và kích thước lớn. Phạm vi nghiên cứu của luận văn tập trung vào bài toán rút gọn thuộc tính ở bước tiền xử lý số liệu và trích lọc luật ở bước khai phá dữ liệu trong quá trình khai phá dữ liệu và khám phá tri thức. Phương pháp nghiên cứu của luận văn là nghiên cứu lý thuyết và nghiên cứu thực nghiệm. Về nghiên cứu lý thuyết: các mệnh đề được chứng minh chặt chẽ dựa vào các kiến thức cơ bản và các kết quả nghiên cứu đã công bố. Về nghiên cứu thực nghiệm: luận văn thực hiện cài đặt các thuật toán, chạy thử nghiệm thuật toán với các bộ số liệu lấy từ kho dữ liệu UCI [12], so sánh và đánh giá kết quả thực nghiệm so với kết quả nghiên cứu lý thuyết, từ đó kết luận tính đúng đắn của kết quả nghiên cứu.
7 Bố cục của luận văn gồm phần mở đầu và ba chương nội dung, phần kết luận và danh mục các tài liệu tham khảo. Chương 1 trình bày các khái niệm cơ bản về lý thuyết tập thô của Pawlak [8] được sử dụng trong chương 2 và chương 3. Chương 2 trình bày hai nội dung chính, thứ nhất là tổng kết các công bố về các phương pháp rút gọn thuộc tính và trích lọc luật, bao gồm phân nhóm các phương pháp rút gọn thuộc tính, luật quyết định và các độ đo đánh giá hiệu năng, sự thay đổi các độ đo đánh giá hiệu năng trên các tập rút gọn của các phương pháp, đánh giá các phương pháp dựa vào chất lượng phân lớp (độ hỗ trợ) của tập luật. Thứ hai là xây dựng phương pháp rút gọn thuộc tính sử dụng khoảng cách, bao gồm xây dựng độ đo khoảng cách, định nghĩa tập rút gọn và độ quan trọng của thuộc tính dựa trên khoảng cách, 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 khoảng cách; phân nhóm và đánh giá phương pháp sử dụng khoảng cách với các phương pháp đã có. Chương 3 trình bày kết quả thử nghiệm và đánh giá phương pháp sử dụng khoảng cách trên các bộ số liệu mẫu từ kho dữ liệu UCI [12] nhằm sáng tỏ các kết quả nghiên cứu về lý thuyết. 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 tiếp theo.
8 Chương 1. TỔNG QUAN VỀ LÝ THUYẾT TẬP THÔ Chương này trình bày các khái niệm cơ bản về lý thuyết tập thô do Pawlak [8] đề xuất. Các khái niệm cơ bản này là kiến thức nền tảng để sử dụng cho các chương sau của luận văn. 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, hệ thông tin được định nghĩa như sau. Định nghĩa 1.1. Hệ thông tin là IS  U , A 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ới mọi u U , a  A , ta ký hiệu giá trị thuộc tính a tại đối tượng u là a  u  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 ký hiệu bộ các giá trị bi  u  bởi B  u  . Như vậy, nếu u và v là hai đối tượng, thì ta viết B  u   B  v  nếu bi  u   bi  v  với mọi i  1,..., k . Xét hệ thông tin IS  U , A . Mỗi tập con các thuộc tính P  A xác định 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, a u   a  v  . IND  P  là quan hệ P-không phân biệt được. Dễ thấy rằng IND P  là một quan hệ tương đương trên U. Nếu  u, v   IND P  thì hai đối tượng u và v không phân biệt được bởi các thuộc tính trong P. Quan hệ tương đương IND  P  xác định một phân hoạch trên U, ký hiệu là U / IND  P  hay U / P . Ký hiệu lớp tương đương trong phân hoạch  U / P chứa đối tượng u là u P , khi đó u P  v U  u, v   IND  P  . 
9 1.2. Mô hình tập thô Cho hệ thông tin IS  U , A 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 có sẵn 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 tập 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à 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ó thể thuộc vào X dựa trên 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. B-miền biên của X là tập chứa các đối tượng có thể thuộc hoặc không thuộc X, còn B-miền ngoài của X chứa các đối tượng chắc chắn không thuộc 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    thì X được gọi là tập chính xác (exact set), ngược lại X được gọi là tập thô (rough set). 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
10 Rõ ràng POSB ( D) là tập tất cả các đối tượng u sao cho với mọi v U mà u  B   v  B  ta đều có u  D   v  D  . Nói cách khác, POSB ( D)  u U u B  u D .   Ví dụ 1.1. Xét hệ thông tin biểu diễn các triệu chứng cúm của bệnh nhân cho ở Bảng 1.1. Bảng 1.1. Bảng thông tin về bệnh cúm U Đau đầ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 Ta có: U / {Đau đầu} = u , u , u ,u , u , u , u , u  1 2 3 4 5 6 7 8 U / {Thân nhiệt} = u , u ,u , u , u ,u , u , u  1 4 2 5 7 3 6 8 U / {Cảm cúm} = u , u , u , u ,u , u , u , u  1 4 5 8 2 3 6 7 U / {Đau đầu, Cảm cúm} = u ,u , u ,u , u , u ,u , u  1 2 3 4 5 8 6 7 Như vậy, các bệnh nhân u2 , u3 không phân biệt được về đau đầu và cảm cúm, nhưng phân biệt được về thân nhiệt. Các lớp không phân biệt được bởi B = {Đau đầu, Thân nhiệt} là: u1 , u2 , u3  , u4  , u5 , u7 , u6 , u8  . Đặt X  {u u (Cảm cúm) = Có} = u2 , u3 , u6 , u7  . Khi đó:
11 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 = {Cảm cúm} thì U / D   X1  u1, u4 , u5 , u8 ; X 2  u2 , u3 , u6 , u7  , BX1  u1 , u4  ; BX 2  u2 , u3  , POS B ( D)  U  BX   u , u , u , u  . X U / D 1 2 3 4 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 lớp cơ bản: 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 . 1.3. Bảng quyết định Một lớp đặc biệt của các hệ 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 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à DS  U , C  D  với C D  . Bảng quyết định DS được gọi là nhất quán nếu D phụ thuộc hàm vào C, tức là với mọi u, v U , C  u   C  v  kéo theo D  u   D  v  . Ngược lại thì gọi là không nhất quán hay mâu thuẫn. Theo định nghĩa miền dương, bảng quyết định 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.
12 1.4. Tập rút gọn và tập lõi Trong bảng quyết định, các thuộc tính điều kiện được phân thành ba nhóm: thuộc tính lõi (core attribute), thuộc tính rút gọn (reductive attribute) và thuộc tính dư thừa (redundant attribute). Thuộc tính lõi là thuộc tính 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 lõi xuất hiện trong tất cả các tập rút gọn của bảng quyết định. Thuộc tính dư thừa là những thuộc tính mà việc loại bỏ chúng không ảnh hưởng đến việc phân lớp tập dữ liệu, thuộc tính dư thừa không xuất hiện trong bất kỳ tập rút gọn nào của bảng quyết định. Thuộc tính rút gọn là thuộc tính xuất hiện trong một tập rút gọn nào đó của bảng quyết định. Chúng ta sẽ đưa ra các định nghĩa chính xác trong phần tiếp theo. Định nghĩa 1.2. [8] (Tập lõi dựa trên miền dương) Cho bảng quyết định DS  U , C  D  . Thuộc tính c  C được gọi là không cần thiết (dispensable) trong DS dựa trên miền dương nếu POSC  D   POS(C c)  D  ; Ngược lại, c được gọi là cần thiết (indispensable). 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 dựa trên miền dương và được ký hiệu là PCORE  C  . Khi đó, thuộc tính cần thiết chính là thuộc tính lõi. Theo Định nghĩa 1.2, thuộc tính không cần thiết là thuộc tính dư thừa hoặc thuộc tính rút gọn. Định nghĩa 1.3. [8] (Tập rút gọn dựa trên miền dương) Cho bảng quyết định DS  U ,C D  và tập thuộc tính R  C . Nếu 1) POSR ( D)  POSC ( D) 2) r  R, POSRr ( D)  POSC ( D) thì R là một tập rút gọn của C dựa trên miền dương. Tập rút gọn định nghĩa như trên còn gọi là tập rút gọn Pawlak. Ký hiệu PRED  C  là họ tất cả các tập rút gọn Pawlak của C. Khi đó PCORE  C   I R. RPRED C 
13 Định nghĩa 1.4. Cho bảng quyết định DS  U , C  D  và a  C . Ta nói rằng a là thuộc tính rút gọn của DS nếu tồn tại một tập rút gọn R  PRED C  sao cho a  R . Định nghĩa 1.5. Cho bảng quyết định DS  U , C  D  và a  C . Ta nói rằng a là thuộc tính dư thừa của DS nếu a  C  U R. RPRED C  Ví dụ 1.2. Xét bảng quyết định về bệnh cúm cho ở Bảng 1.2. Bảng 1.2. Bảng quyết định về bệnh cúm U Mệt mỏi Đau đầu Đau cơ Thân nhiệt Cảm cúm u1 Có Có Có Bình thường Không u2 Có Có Có Cao Có u3 Có Có Có Rất cao Có u4 Có Không Có Bình thường Không u5 Có Không Không Cao Không u6 Có Không Có Rất cao Có Bảng này có hai tập rút gọn là R1 = {Đau cơ, Thân nhiệt} và R2 = {Đau đầu, Thân nhiệt}. Như vậy tập lõi là PCORE(C) = {Thân nhiệt} và Thân nhiệt là thuộc lõi duy nhất. Các thuộc tính không cần thiết bao gồm:  Thuộc tính Mệt mỏi là thuộc tính dư thừa vì không tham gia vào rút gọn nào  Hai thuộc tính Đau đầu và Đau cơ là hai thuộc tính rút gọn vì đều có mặt trong một tập rút gọn. Hai thuộc tính này đều không cần thiết theo nghĩa là, từ bảng dữ liệu, có thể loại bỏ một trong hai thuộc tính này mà vẫn chuẩn đoán đúng bệnh. Tức là POS{Đau cơ, Thân nhiệt}({Cảm cúm}) = POSC({Cảm cúm}) POS{Đau đầu, Thân nhiệt}({Cảm cúm}) = POSC({Cảm cúm}).
14 1.5. Ma trận phân biệt và hàm phân biệt Ma trận phân biệt do Andrzej Skowron và các cộng sự [3] đề xuất là công cụ sử dụng để tìm tập rút của bảng quyết định. Xét bảng quyết định DS  U , C  D  với U  u1 , u2 ,..., un  . Ma trận phân biệt của DS , ký hiệu M   mi j nn , là một ma trận đối xứng mà mỗi phần tử của nó là một tập hợp các thuộc tính được xác định như sau    c  C c(ui )  c(u j ) mi j    if D(ui )  D(u j ),   if D(ui )  D(u j ) . Định nghĩa 1.6. [3] (Tập rút gọn dựa trên ma trận phân biệt) Cho bảng quyết định DS  U , C  D  , M   mi j  là ma trận phân biệt của DS và tập thuộc tính R  C . nn Nếu 1) R  mi j   với mọi mi j   2) Với mọi r  R , R  r không thỏa mãn 1) thì R được gọi là một tập rút gọn của C thu được bởi phương pháp sử dụng ma trận phân biệt, gọi tắt là tập rút gọn dựa trên ma trận phân biệt. Ký hiệu SRED C  là họ tất cả các tập rút gọn của C dựa trên ma trận phân biệt. Định nghĩa 1.7. [3] (Tập lõi dựa trên ma trận phân biệt) Cho bảng quyết định DS  U , C  D  , M   mi j  là ma trận phân biệt của DS. Thuộc tính c  C được nn gọi là không cần thiết (dispensable) trong DS dựa trên ma trận phân biệt nếu C  c  m ij   với mọi mi j   . Ngược lại, c được gọi là cần thiết (indispensable). 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 dựa trên ma trận phân biệt và được ký hiệu là SCORE  C  . Theo [3], SCORE  C   I R. RSRED C 
15 Chương 2. RÚT GỌN THUỘC TÍNH VÀ TRÍCH LỌC LUẬT TRONG BẢNG QUYẾT ĐỊNH THEO TIẾP CẬN TẬP THÔ Chương này trình bày hai nội dung chính như sau: 1) Tổng hợp các kết quả nghiên cứu về các phương pháp rút gọn thuộc tính và trích lọc luật trong bảng quyết định trong tài liệu [1, 2], bao gồm: tổng hợp và phân nhóm các phương pháp rút gọn thuộc tính dựa vào tập rút gọn; tổng hợp các kết quả nghiên cứu về luật quyết định và các độ đo đánh giá hiệu năng; tổng hợp các kết quả nghiên cứu về so sánh, đánh giá các phương pháp rút gọn thuộc tính. 2) Xây dựng phương pháp rút gọn thuộc tính sử dụng độ đo khoảng cách, bao gồm: xây dựng độ đo khoảng cách; định nghĩa tập rút gọn và độ quan trọng của thuộc tính dựa trên khoảng cách; xây dựng thuật toán heuristic tìm tập rút gọn sử dụng khoảng cách; phân nhóm, đánh giá phương pháp khoảng cách với các phương pháp khác công bố. 2.1. Rút gọn thuộc tính và trích lọc luật trong bảng quyết định 2.1.1. Tổng kết, phân nhóm các phương pháp rút gọn thuộc tính Mục tiêu của rút gọn thuộc tính trong bảng quyết định theo tiếp cận tập thô là sử dụng công cụ tập thô để tìm tập con nhỏ nhất của tập thuộc tính điều kiện mà bảo toàn thông tin phân lớp của bảng quyết định. Dựa vào tập rút gọn thu được, việc sinh luật và phân lớp đạt hiệu quả cao nhất. Với một bảng quyết định cho trước, độ phức tạp thời gian của thuật toán tìm tất cả các tập rút gọn là hàm mũ đối với số thuộc tính điều kiện. Tuy nhiên, trong các bài toán thực tế 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á đặt ra. Do đó, các phương pháp rút gọn thuộc tính sử dụng cận tập thô đều thực hiện theo hướng tiếp cận heuristic. Các phương pháp này đều có các điểm chung như sau: - Đưa ra khái niệm tập rút gọn của phương pháp dựa trên một độ đo được chọn. Các phương pháp khác nhau có độ đo khác nhau, điển hình là các độ đo trong
16 tính toán hạt (granunal computing), độ đo entropy, độ đo khoảng cách, sử dụng ma trận… - Đưa ra khái niệm độ quan trọng của thuộc tính đặc trưng cho chất lượng phân lớp của thuộc tính dựa trên độ đo được chọn. - Xây dựng một thuật toán heuristic tìm một tập rút gọn tốt nhất theo tiêu chuẩn đánh giá độ quan trọng của thuộc tính (chất lượng phân lớp của thuộc tính). Thuật toán này giảm thiểu đáng kể khối lượng tính toán, nhờ đó có thể áp dụng đối với các bài toán có dữ liệu lớn. Các thuật toán heuristic này thường được xây dựng theo hai hướng tiếp cận khác nhau: hướng tiếp cận từ dưới lên (bottom-up) và hướng tiếp cận từ trên xuống (top-down). Ý tưởng chung của hướng tiếp cận từ dưới lên (bottom-up) là xuất phát từ tập tập lõi, bổ sung dần dần các thuộc tính có độ quan trọng lớn nhất vào tập lõi cho đến khi thu được tập rút gọn. Ý tưởng chung của hướng tiếp cận từ trên xuống (top-down) xuất phát từ tập thuộc tính điều kiện ban đầu, loại bỏ dần các thuộc tính có độ quan trọng nhỏ nhất cho đến khi thu được tập rút gọn. Cả hai hướng tiếp cận này đều đòi hỏi phải sắp xếp danh sách các thuộc tính theo thứ tự giảm dần hoặc tăng dần của độ quan trọng tại mỗi bước lặp. 1) Các phương pháp rút gọn thuộc tính trong bảng quyết định Theo tiếp cận tập thô, cho đến nay đã có rất nhiều phương pháp rút gọn thuộc tính dựa trên các độ đo khác nhau được công bố. Trong tài liệu [1, 2], tác giả đã tổng kết khá đầy đủ các phương pháp rút gọn thuộc tính trong bảng quyết định và các tập rút gọn tương ứng. Bảng 2.1. Các phương pháp rút gọn thuộc tính trong tài liệu [1, 2] STT Phương pháp Tập rút gọn Ký hiệu tập rút gọn 1 Phương pháp sử dụng miền Tập rút gọn dựa trên RP dương. miền dương 2 Phương pháp sử dụng entropy Tập rút gọn dựa trên RH
17 Shannon entropy Shannon 3 Phương pháp sử dụng metric Tập rút gọn dựa trên RM metric 4 Phương pháp sử dụng các Tập rút gọn dựa trên RF phép toán trong đại số quan hệ đại số quan hệ 5 Phương pháp sử dụng ma trận Tập rút gọn dựa trên RS phân biệt. ma trận phân biệt 6 Phương pháp sử dụng entropy Tập rút gọn dựa trên RE Liang entropy Liang 7 Phương pháp sử dụng độ đo Tập rút gọn dựa trên RK khác biệt của tri thức độ khác biệt của tri thức. 2) Phân nhóm các phương pháp rút gọn thuộc tính Như đã trình bày ở trên, mỗi phương pháp rút gọn thuộc tính đều đưa ra định nghĩa về tập rút gọn và xây dựng thuật toán heuristic tìm tập rút gọn. Do đó, có thể nói rằng tập rút gọn là kết quả của phương pháp rút gọn thuộc tính. Vì vậy, việc phân nhóm các phương pháp rút gọn thuộc tính cũng dựa vào định nghĩa tập rút gọn và được thực hiện theo nguyên tắc: các phương pháp có tập rút gọn như nhau được phân thành một nhóm. Trong tài liệu [1, 2], các tác giả đã tổng kết và nghiên cứu mối liên hệ giữa các định nghĩa tập rút gọn và kết quả phân nhóm các phương pháp rút gọn thuộc tính như sau: 1) Nếu bảng quyết định nhất quán, các định nghĩa tập rút gọn RP , RH , RM , RF , RS , RE , RK là tương đương nhau. 2) Nếu bảng quyết định không nhất quán: - Tập rút gọn dựa trên entropy Shannon ( RH ), tập rút gọn dựa trên metric ( RM ), tập rút gọn dựa trên đại số quan hệ ( RF ) tương đương nhau.
18 - Tập rút gọn dựa trên ma trận phân biệt ( RS ), tập rút gọn dựa trên entropy Liang ( RE ), tập rút gọn dựa trên độ khác biệt của tri thức ( RK ) tương đương nhau. Mối quan hệ giữa các định nghĩa tập rút gọn được mô tả như sau: - Tập rút gọn dựa trên miền dương ( RP ) là tập con của tập rút gọn dựa trên entropy Shannon ( RH ), nghĩa là: nếu RH là một tập rút gọn dựa trên entropy Shannon thì tồn tại RP  RH với RP là một tập rút gọn dựa trên miền dương. - Tập rút gọn dựa trên entropy Liang ( RE ) là tập con của tập rút gọn dựa trên entropy Shannon ( RH ), nghĩa là: nếu RE là một tập rút gọn dựa trên entropy Liang thì tồn tại RH  RE với RH là một tập rút gọn dựa trên entropy Shannon. Mối liên hệ giữa các tập rút gọn của bảng quyết định không nhất quán được biểu diễn bằng sơ đồ sau:   RH  RM  RF RS  RE  RK RP Hình 2.1. Mối liên hệ giữa các định nghĩa tập rút gọn Từ sơ đồ về mối liên hệ giữa các tập rút gọn, các tác giả trong [1, 2] đã thực hiện phân nhóm các tập rút gọn và chỉ ra mối liên quan hệ giữa các tập rút gọn của các nhóm. Cụ thể: Các tập rút gọn trong bảng quyết định không nhất quán được chia thành bốn nhóm: Nhóm 1: Bao gồm tập rút gọn RP . Nhóm 2: Bao gồm các tập rút gọn RH , RM , RF Nhóm 3: Bao gồm các tập rút gọn RS , RE , RK Mối liên hệ giữa các tập rút gọn trong các nhóm như sau: