Luận văn Thạc sĩ Công nghệ thông tin: Khai phá dữ liệu dựa trên bảng quyết định nhờ lý thuyết tập thô

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

Thêm vào BST

Báo xấu

29
lượt xem 5
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ìm hiểu về lý thuyết tập thô: hệ thông tin, bảng quyết định, các tập xấp xỉ, tập lõi và tập rút gọn. Tìm hiểu các phương pháp rút gọn thuộc tính, từ đó lựa chọn phương pháp rút gọn thuộc tính sử dụng Entropy Shannon trong bảng quyết định và phương pháp sinh luật quyết định trên tập rút gọn thu được.

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ĩ Công nghệ thông tin: Khai phá dữ liệu dựa trên bảng quyết định nhờ lý thuyết tập thô

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ HOÀNG THỊ KIM OANH KHAI PHÁ DỮ LIỆU DỰA TRÊN BẢNG QUYẾT ĐỊNH NHỜ LÝ THUYẾT TẬP THÔ LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Hà Nội - 2014
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ HOÀNG THỊ KIM OANH KHAI PHÁ DỮ LIỆU DỰA TRÊN BẢNG QUYẾT ĐỊNH NHỜ 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ố: 60480104 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƢỜI HƢỚNG DẪN KHOA HỌC: GS.TS. VŨ ĐỨC THI Hà Nội - 2014
1 LỜI CẢM ƠN Trước tiên, tôi xin gửi lời cảm ơn chân thành nhất tới GS.TS Vũ Đức Thi, Viện Công nghệ thông tin – Đại học Quốc gia Hà Nội đã tận tình hướng dẫn, định hướng, đóng góp những ý kiến quý báu cho tôi trong quá trình thực hiện luận văn. Tôi xin chân thành cảm ơn các Thầy, Cô giáo trong Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội đã tận tình giảng dạy và truyền thụ cho tôi những kiến thức quý báu trong suốt quá trình học tập tại trường. Đồng thời, tôi cũng xin cảm ơn gia đình, bạn bè, những người luôn khuyến khích và giúp đỡ tôi trong mọi hoàn cảnh khó khăn. Tôi xin cảm ơn cơ quan và các đồng nghiệp đã hết sức tạo điều kiện cho tôi trong suốt quá trình học tập và làm luận văn này. Hà Nội, ngày tháng 6 năm 2014 Học viên Hoàng Thị Kim Oanh
2 LỜI CAM ĐOAN Tôi xin cam đoan những kiến thức trình bày trong luận văn này là do tôi tìm hiểu, nghiên cứu và trình bày lại theo cách hiểu của tôi. Trong quá trình làm luận văn tôi có tham khảo các tài liệu có liên quan và đã ghi rõ nguồn tài liệu tham khảo đó. Phần lớn những kiến thức tôi trình bày trong luận văn này chưa được trình bày hoàn chỉnh trong bất cứ tài liệu nào. Hà Nội, ngày tháng 6 năm 2014 Học viên Hoàng Thị Kim Oanh
3 MỤC LỤC LỜI CẢM ƠN............................................................................................................................................................1 LỜI CAM ĐOAN.....................................................................................................................................................2 MỤC LỤC...................................................................................................................................................................3 DANH MỤC CÁC THUẬT NGỮ....................................................................................................................5 DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ...........................................................................6 DANH MỤC CÁC BẢNG ...................................................................................................................................7 DANH MỤC CÁC HÌNH VẼ.............................................................................................................................8 MỞ ĐẦU......................................................................................................................................................................9 Chƣơng 1. KHAI PHÁ DỮ LIỆU THEO TIẾP CẬN TẬP THÔ .................................................... 12 1.1. Hệ thông tin ........................................................................................................................... 12 1.2. Bảng quyết định .................................................................................................................... 13 1.3. Quan hệ không phân biệt được ............................................................................................ 14 1.4. Các tập xấp xỉ ........................................................................................................................ 16 1.5. Tập rút gọn và tập lõi ............................................................................................................ 18 1.6. Ma trận phân biệt và hàm phân biệt .................................................................................... 20 Chƣơng 2. PHƢƠNG PHÁP RÚT GỌN THUỘC TÍNH VÀ SINH LUẬT TRÊN BẢNG QUYẾT ĐỊNH........................................................................................................................................................ 21 2.1. Phương pháp rút gọn thuộc tính trên bảng quyết định ...................................................... 21 2.2. Phương pháp rút gọn thuộc tính dựa trên entropy Shannon ............................................. 25 2.2.1. Entropy Shannon trên bảng quyết định .................................................................. 25 2.2.2. Tập lõi của bảng quyết định dựa trên Entropy Shannon ........................................ 26 2.2.3. Tập rút gọn của bảng quyết định dựa trên Entropy Shannon .................................. 27 2.2.4. Độ quan trọng của thuộc tính dựa trên entropy Shannon ....................................... 27 2.2.5. Thuật toán tìm tập rút gọn của bảng quyết định sử dụng Entropy Shannon .......... 28 2.3. Sinh luật quyết định trên tập rút gọn của bảng quyết định................................................ 34 2.3.1. Luật quyết định ....................................................................................................... 34 2.3.2. Các độ đo đánh giá hiệu năng tập luật quyết định trên các tập rút gọn .................. 35 2.3.3. Thuật toán sinh luật quyết định dựa trên tập rút gọn của bảng quyết định............. 38 Chƣơng 3. THỬ NGHIỆM VÀ ĐÁNH GIÁ KẾT QUẢ...................................................................... 40 3.1. Bài toán .................................................................................................................................. 40 3.2. Một số kết quả thử nghiệm .................................................................................................. 40
4 3.2.1. Kết quả thử nghiệm thuật toán rút gọn thuộc tính sử dụng entropy Shannon ........ 40 3.2.2. Kết quả thử nghiệm thuật toán sinh luật quyết định dựa trên tập rút gọn .............. 42 3.3. Ứng dụng thuật toán rút gọn thuộc tính vào thực tế .......................................................... 44 3.4. Một số giao diện chương trình ............................................................................................. 45 3.4.1. Thực hiện thuật toán rút gọn thuộc tính CEBARKCC ........................................... 45 3.4.2. Thực hiện thuật toán sinh luật quyết định .............................................................. 45 KẾT LUẬN.............................................................................................................................................................. 48 TÀI LIỆU THAM KHẢO................................................................................................................................. 49
5 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 Hệ thông tin đầy đủ Complete Information System Bảng quyết định Decision Table Bảng quyết định đầy đủ Complete 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 Ma trận phân biệt Indiscernibility Matrix Hàm phân biệt Indiscernibility Function Luật quyết định Decision Rule
6 DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT Ký hiệu, từ viết tắt Diễn giải IS  U , A,V , f  Hệ thông tin, hệ thông tin đầy đủ DS  U , C  D,V , f  Bảng quyết định, bảng quyết định đầy đủ U Số đối tượng C Số thuộc tính điều kiện trong bảng quyết định A Số thuộc tính trong hệ thông tin u a Giá trị của đối tượng u tại thuộc tính a IND  B  Quan hệ B  không phân biệt  u B Lớp tương đương chứa u của quan hệ IND  B  U/B Phân hoạch của U sinh bởi tập thuộc tính B .  B (u ) Hàm quyết định suy rộng của đối tượng u đối với B . POS B  D  B  miền dương của D PRED  C  Họ tất cả các tập rút gọn Pawlak HRED  C  Họ tất cả các tập rút gọn Entropy Shannon PCORE  C  Tập lõi dựa trên miền dương HCORE  C  Tập lõi dựa trên entropy Shannon có điều kiện H  P Entropy Shannon của tập thuộc tính P H (Q | P) Entropy Shannon có điều kiện của Q khi đã biết P
7 DANH MỤC CÁC BẢNG Bảng 1.1. Ví dụ về hệ thông tin ............................................................................................... 13 Bảng 1.2. Ví dụ một bảng quyết định ...................................................................................... 14 Bảng 1.3. Bảng thông tin về bệnh cúm ................................................................................... 17 Bảng 2.1. Bảng quyết định minh họa Ví dụ 2.1 ....................................................................... 26 Bảng 2.2. Bảng quyết định minh họa Ví dụ 2.2 ....................................................................... 29 Bảng 2.3. Bảng quyết định về bệnh cúm ................................................................................. 36 Bảng 3.1. Kết quả thực hiện Thuật toán CEBARKCC ............................................................ 41 Bảng 3.2. Kết quả thực hiện Thuật toán CEBARKCC ............................................................ 42 Bảng 3.3. Tập rút gọn tốt nhất của bộ số liệu Soybean - small.data ....................................... 43 Bảng 3.4. Các luật phân lớp trên bảng quyết định rút gọn ....................................................... 43
8 DANH MỤC CÁC HÌNH VẼ Hình 1.1. Mô tả về tập xấp xỉ và miền .................................................................................... 16 Hình 3.1. Giao diện thực hiện thuật toán rút gọn thuộc tính ................................................... 45 Hình 3.2. Giao diện tìm tập rút gọn với bộ số liệu Soybean – small.data ............................... 46 Hình 3.3. Tập rút gọn thu được với bộ số liệu Soybean – small.data ...................................... 46
9 MỞ ĐẦU Ngày nay với sự bùng nổ của công nghệ thông tin và mạng Internet, lượng dữ liệu đang ngày càng tăng lên một cách nhanh chóng khiến chúng ta rơi vào tình trạng “ngập lụt thông tin". Chính vì vậy, các chuyên gia cho rằng, hiện nay chúng ta đang sống trong một xã hội “rất giàu về thông tin nhưng nghèo về tri thức”. Trước tình hình đó đòi hỏi phải phát triển các phương pháp khai phá, phát hiện ra những thông tin, tri thức có ích bị che giấu trong các “núi” dữ liệu phục vụ cho các nhà quản lý, các chuyên gia, từ đó thúc đầy khả năng sản xuất, kinh doanh của các tổ chức, doanh nghiệp. Do đó, khai phá dữ liệu (Data Mining) ra đời nhằm đáp ứng nhu cầu này. Lý thuyết tập thô do nhà logic học Balan Zdzislak Pawlak [17] đề xuất vào đầu những năm 80 được xem như là một cách tiếp cận mới để phát hiện tri thức và tạo thành một cơ sở vững chắc cho các ứng dụng khai phá dữ liệu. Nó rất hữu ích trong việc giải quyết các bài toán phân lớp dữ liệu, phát hiện luật, … chứa dữ liệu mơ hồ không chắc chắn. Các mối quan hệ trong mô hình này được biểu diễn qua quan hệ không phân biệt được, còn các dữ liệu được biểu diễn thông qua tập xấp xỉ trên và xấp xỉ dưới của nó. Dữ liệu trong lý thuyết tập thô được biểu diễn thông qua hệ thông tin hay bảng quyết định. Bảng quyết định là mô hình thường gặp trong thực tế, khi mà giá trị dữ liệu tại các thuộc tính điều kiện có thể cung cấp cho ta thông tin về giá trị của thuộc tính quyết định. Hiện nay các cơ sở dữ liệu (CSDL) cần khai phá thường có kích thước rất lớn, chẳng hạn như CSDL tin sinh học, CSDL đa phương tiện, … Các CSDL này thường chứa tới hàng ngàn thuộc tính, gây rất nhiều khó khăn trong việc khai phá, thậm chí còn làm cho nhiệm vụ khai phá trở nên bất khả thi. Vấn đề đặt ra là phải tìm cách rút gọn số thuộc tính mà không làm mất những thông tin cần thiết phục vụ nhiệm vụ khai phá. Rút gọn thuộc tính là ứng dụng quan trọng nhất trong lý thuyết tập thô. 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 để tìm ra các thuộc tính cốt yếu và cần thiết trong cơ sở dữ liệu. Với bảng quyết định, rút gọn thuộc tính là tìm tập con nhỏ nhất của tập thuộc tính điều kiện bảo toàn thông tin phân lớp của bảng quyết định.
10 Mười năm trở lại đây, nhiều nhóm nhà khoa học trên thế giới quan tâm nghiên cứu các phương pháp rút gọn thuộc tính trong bảng quyết định sử dụng lý thuyết tập thô. Các phương pháp chính là: phương pháp dựa trên miền dương, phương pháp sử dụng các phép toán trong đại số quan hệ, phương pháp sử dụng ma trận phân biệt, phương pháp sử dụng entropy thông tin, …. Tại Việt Nam, luận án tiến sĩ của tác giả Hoàng Thị Lan Giao [1] đã đề xuất các thuật toán heuristic tìm tập rút gọn và tìm tập rút gọn xấp xỉ của bảng quyết định nhất quán, bao gồm thuật toán sử dụng các phép toán trong đại số quan hệ và thuật toán sử dụng ma trận phân biệt. Luận án tiến sĩ của tác giả Nguyễn Đức Thuần [2] đề xuất thuật toán heuristic tìm tập rút gọn của bảng quyết định đầy đủ nhất quán dựa vào phủ tập thô. Luận án tiến sĩ của tác giả Nguyễn Long Giang [3] đã đề xuất thuật toán heuristic tìm tập rút gọn của bảng quyết định đầy đủ và không đầy đủ sử dụng metric. Với những lý do trên, tập thô đã chứng tỏ là một trong những lý thuyết rất hiệu quả trong lĩnh vực khai phá dữ liệu. Vì vậy tôi đã chọn đề tài “Khai phá dữ liệu dựa trên bảng quyết định nhờ lý thuyết tập thô”. Trong luận văn này, tôi nghiên cứu hai vấn đề chính sau:  Tìm hiểu về lý thuyết tập thô: hệ thông tin, bảng quyết định, các tập xấp xỉ, tập lõi và tập rút gọn.  Tìm hiểu các phương pháp rút gọn thuộc tính, từ đó lựa chọn phương pháp rút gọn thuộc tính sử dụng Entropy Shannon trong bảng quyết định và phương pháp sinh luật quyết định trên tập rút gọn thu được. Sau đó thử nghiệm thuật toán heuristic tìm tập rút gọn trên bảng quyết định sử dụng entropy Shannon có điều kiện có tính toán lõi trên các bộ số liệu mẫu từ kho dữ liệu UCI Đố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 trong quá trình khai phá dữ liệu. 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ề
11 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 Bố cục luận văn gồm 3 chương: Chương 1: Trình bày các khái niệm cơ bản của lý thuyết tập thô đượ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 phương pháp rút gọn thuộc tính đã công bố, từ đó lựa chọn phương pháp rút gọn thuộc tính dựa trên entropy Shannon. Thứ hai là nghiên cứu phương pháp sinh luật quyết định, các độ đo đánh giá hiệu năng tập luật quyết định, từ đó lựa chọn và đánh giá các phương pháp rút gọn thuộc tính. Chương 3: Thử nghiệm thuật toán heuristic tìm tập rút gọn trên bảng quyết định sử dụng entropy Shannon có điều kiện có tính toán lõi trên các bộ số liệu mẫu từ kho dữ liệu UCI và thuật toán sinh luật trên bảng quyết định.
12 Chƣơng 1. KHAI PHÁ DỮ LIỆU THEO TIẾP CẬN TẬP THÔ Lý thuyết tập thô (Rough Set Theory) do Zdzisaw Pawlak (1926-2006) đề xuất vào năm 1982 đã được ứng dụng ngày càng rộng rãi trong lĩnh vực khoa học máy tính. Lý thuyết tập thô được phát triển trên một nền tảng toán học vững chắc, cung cấp các công cụ hữu ích để giải quyết các bài toán phân tích dữ liệu, phát hiện luật, nhận dạng… Đặc biệt lý thuyết này thích hợp với các bài toán phân tích trên khối lượng dữ liệu lớn, chứa đựng thông tin mơ hồ, không chắc chắn. Khái niệm cơ bản của lý thuyết tập thô là xấp xỉ trên và xấp xỉ dưới của một tập. Tập con được tạo ra bởi xấp xỉ dưới bao gồm các đối tượng chắc chắn thuộc tập đó, còn xấp xỉ trên chứa tất cả các đối tượng có khả năng thuộc về tập đó. Mỗi tập con xác định thông qua xấp xỉ dưới và xấp xỉ trên được gọi là tập thô. 1.1. Hệ thông tin Trong hầu hết các hệ quản trị cơ sở dữ liệu thông thường, thông tin thường được biểu diễn dưới dạng các bảng dữ liệu, trong đó mỗi dòng biểu diễn thông tin ứng với một đối tượng, mỗi cột biểu diễn một thuộc tính có thể đo được của đối tượng. Từ đầu những năm 80, Z. Pawlak đã đưa ra một khái niệm mới là hệ thông tin dựa trên khái niệm bảng truyền thống. Có thể định nghĩa hệ thông tin một cách hình thức như sau. Định nghĩa 1.1. Hệ thông tin là một bộ IS  U , A,V , f  , trong đó: U là tập hữu hạn, khác rỗng các đối tượng (tập vũ trụ); 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 ; aA f là hàm thông tin, 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
13 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 viết u  B   v  B  nếu u  bi   v  bi  với mọi i  1,..., k . Ví dụ 1.1. Bảng 1.1 dưới đây biểu diễn về một hệ thông tin của 10 đối tượng với 5 thuộc tính Bảng 1.1. Ví dụ về hệ thông tin Ta có một hệ thông tin IS  U , A,V , f  . U   X1 , X 2 ,..., X10  , A = {To, Ly, Ho, Nv, Av} VTo  SX , G, K1, K 2 , VLy  G, K1, K 2 , VHo  K 2, TB , VNv  K 2, TB , VAv  G, K1, K 2 1.2. Bảng quyết định Để có thể biểu diễn một dữ liệu thực tế, trong đó có những thuộc tính quyết định, ta xét một trường hợp đặc biệt của hệ thông tin được gọi 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 tách biệt 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. Bảng quyết định, được ký hiệu là DS  U , C  D,V , f  với C  D   .
14 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 POS C 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. Ví dụ 1.2: Mô tả một bảng quyết định, với các thuộc tính điều kiện lấy ở Bảng 1.1 và thêm vào thuộc tính quyết định “Tc” Bảng 1.2. Ví dụ một bảng quyết định 1.3. Quan hệ không phân biệt đƣợc Một trong những đặc điểm cơ bản của lý thuyết tập thô là dùng để lưu giữ và xử lý các dữ liệu không phân biệt được. Trong một hệ thông tin theo định nghĩa 1.1 thì cũng có thể có những đối tượng không phân biệt được. Trước tiên ta nhắc lại định nghĩa quan hệ tương đương như sau: Định nghĩa 1.2 Một quan hệ hai ngôi (quan hệ nhị phân) R  U U trên U là một quan hệ tương đương khi nó thỏa mãn 3 tính chất: - Phản xạ: Mọi đối tượng đều quan hệ với chính nó - Đối xứng: Nếu xRy thì yRx - Bắc cầu: Nếu xRy và yRz thì xRz
15 Quan hệ tương đương R sẽ chia tập các đối tượng U thành các lớp tương đương. Lớp tương đương của phần tử x U , ký hiệu là [x]R, chứa tất cả các đối tượng y mà xRy. Xét hệ thông tin IS  U , A,V , f  , P  A , quan hệ không phân biệt được trên U theo P, ký hiệu là IND  P  , được định nghĩa như sau:   IND  P    u, v  U U a  P, u  a   v  a  . Khi đó 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 . Lớp tương đương trong phân hoạch U / P chứa đối tượng u ký hiệu là u P : u P  v U u, v   IND  P  . Định nghĩa 1.3. ([18]) Cho hệ thông tin IS  U , A,V , f  và P, Q  A . Ta nói: 1) Phân hoạch U / P và phân hoạch U / Q là như nhau (viết U / P  U / Q ), khi và chỉ khi u U , u P  u Q . 2) Phân hoạch U / P mịn hơn phân hoạch U / Q (viết U / P U / Q ) khi và chỉ khi u U , u P  u Q . Tính chất 1.1. ([18]) Xét hệ thông tin IS  U , A,V , f  và P, Q  A . 1) Nếu P  Q thì U / Q U / P , mỗi lớp của U / P là một lớp hoặc hợp của một số lớp thuộc U / Q . 2) Với mọi u U ta có u PQ  u P  u Q . Ví dụ 1.3. Xét hệ thông tin cho ở Bảng 1.1, phân hoạch của tập U sinh bởi quan hệ tương đương IND(P): - Với P={To} ta có IND(P)={{X1, X2, X7, X8}, {X5, X6, X9, X10}, {X3}, X4}}. Lúc này ta nói X1 và X2 là không phân biệt được.
16 1.4. Các tập xấp xỉ 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. Trong lý thuyết tập thô truyền thống, để biểu diễn tập đối tượng 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 phân hoạch 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ầ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, người 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 B-miền ngoài (NEGB(X)) của X chứa các đối tượng chắc chắn không thuộc 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ô. Hình 1.1. Mô tả về tập xấp xỉ và miền
17 Ví dụ 1.4. 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.3. Bảng 1.3. 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} = u1 , u2 , u3  , u4 , u5 , u6 , u7 , u8  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 đó: 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 .
18 1.5. 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 thuộc tính lõi và thuộc tính không cần thiết. Thuộc tính lõi là thuộc tính 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 không cần thiết là thuộc tính dư thừa mà việc loại bỏ thuộc tính này không ảnh hưởng đến việc phân lớp dữ liệu. Các thuộc tính không cần thiết được phân thành hai nhóm: Thuộc tính dư thừa thực sự và thuộc tính rút gọn. Thuộc tính dư thừa thực sự là những thuộc tính dư thừa mà việc loại bỏ tất cả các thuộc tính như vậy không ảnh hưởng đến việc phân lớp dữ liệu. Thuộc tính rút gọn, với một tổ hợp thuộc tính nào đó, nó là thuộc tính dư thừa và với một tổ hợp các thuộc tính khác nó có thể là thuộc tính lõi. Định nghĩa 1.3. ([17]) (Tập lõi dựa trên miền dương) Cho bảng quyết định DS  U , C  D,V , f  . Thuộc tính c  C được gọi là không cần thiết (dư thừa) 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. 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  . Lúc đó, thuộc tính cần thiết còn được gọi là thuộc tính lõi. Định nghĩa 1.4. ([17]) (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 , f  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   R. RPRED C  Định nghĩa 1.5. ([17]) 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 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 .