Tài liệu Nghiên cứu các tập rút gọn trong bảng quyết đinh l

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ LÊ THỊ HÂN NGHIÊN CỨU CÁC TẬP RÚT GỌN TRONG BẢNG QUYẾT ĐỊNH LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Hà Nội - Năm 2013 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ ---------- LÊ THỊ HÂN NGHIÊN CỨU CÁC TẬP RÚT GỌN TRONG BẢNG QUYẾT ĐỊNH 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Ĩ CÔNG NGHỆ THÔNG TIN NGƢỜI HƢỚNG DẪN KHOA HỌC: GS.TS. VŨ ĐỨC THI Hà Nội - Năm 2013 -1- MỤC LỤC MỤC LỤC .................................................................................................................. - 1 LỜI CẢM ƠN ............................................................................................................. - 3 LỜI CAM ĐOAN ....................................................................................................... - 4 BẢNG CÁC KÝ HIỆU, VIẾT TẮT .......................................................................... - 5 DANH SÁCH BẢNG................................................................................................. - 7 DANH SÁCH HÌNH VẼ............................................................................................ - 8 MỞ ĐẦU .................................................................................................................... - 9 Chƣơng 1. CÁC KHÁI NIỆM VỀ LÝ THUYẾT TẬP THÔ .................................. - 11 1.1. Hệ thông tin đầy đủ .................................................................................... - 11 1.2. Mô hình tập thô truyền thống ..................................................................... - 12 1.3. Bảng quyết định đầy đủ ............................................................................. - 14 1.4. Tập rút gọn và tập lõi ................................................................................. - 14 1.5. Ma trận phân biệt và hàm phân biệt ........................................................... - 16 1.6. Một số khái niệm cơ bản về cơ sở dữ liệu quan hệ ................................... - 17 1.6.1. Quan hệ .............................................................................................. - 17 1.6.2. Phụ thuộc hàm .................................................................................... - 17 1.6.3. Hệ tiên đề Armstrong ......................................................................... - 17 1.6.4. Sơ đồ quan hệ ..................................................................................... - 17 1.6.5. Khoá và phản khoá ............................................................................. - 18 1.6.6. Hệ bằng nhau và hệ bằng nhau cực đại .............................................. - 19 1.7. Một số thuật toán cơ bản ............................................................................ - 19 Chƣơng 2 : MỘT SỐ PHƢƠNG PHÁP TÌM MỘT TẬP RÚT GỌN VÀ TÌM CÁC TẬP RÚT GỌN TRONG BẢNG QUYẾT ĐỊNH ................................................... - 23 2.1. Thuật toán tìm tập rút gọn của bảng quyết định sử dụng metric ............... - 23 2.1.1. Khoảng cách Jaccard giữa hai tập hợp hữu hạn .................................. - 23 2.1.2. Một số tính chất của metric trên bảng quyết định ............................... - 25 2.2. Thuật toán tìm tập rút gọn theo tham số độ chắc chắn của tập luật........... - 33 2.3.huật toán tìm tập tất cả các thuộc tính rút gọn của bảng quyết định nhất quán .. - 34 2.3.1. Đặt vấn đề ........................................................................................... - 34 2.3.2. Thuật toán............................................................................................ - 35 2.4. Thuật toán tìm họ tất cả các tập rút gọn của bảng quyết định nhất quán .. - 38 2.5. Thuật toán xây dựng các phụ thuộc hàm từ bảng quyết định nhất quán ... - 40 - -2- 2.6. Thuật toán xây dựng bảng quyết định từ tập phụ thuộc hàm ................... - 41 Chƣơng 3: THỰC NGHIỆM THUẬT TOÁN TÌM MỘT TẬP RÚT GỌN............ - 45 3.1. Thử nghiệm các thuật toán heuristic tìm một tập rút gọn tốt nhất.............. - 45 3.1.1. Mô tả thuật toán CEBARKCC ............................................................. - 45 3.1.2. Thử nghiệm và đánh giá các thuật toán trên các bộ số liệu mẫu trong UCI. - 46 3.1.3. Thử nghiệm phƣơng pháp sinh luật quyết định trên các tập rút gọn ... - 48 3.2. Thử nghiệm thuật toán tìm tập rút gọn theo tham số độ chắc chắn ............ - 50 3.3. Thử nghiệm thuật toán tìm tất cả các thuộc tính rút gọn của bảng quyết định nhất quán ............................................................................................................... - 51 3.4. Một số bài toán ứng dụng .......................................................................... - 52 3.5. Một số giao diện chƣơng trình thử nghiệm ............................................... - 53 3.5.1. Giao diện chính của chƣơng trình ....................................................... - 53 3.5.2. Nạp các tệp dữ liệu mẫu lấy từ kho dữ liệu UCI ................................ - 53 3.5.3. Thực hiện thuật toán CEBARKCC ..................................................... - 54 3.5.4. Thực hiện thuật toán sử dụng khoảng cách ......................................... - 54 3.5.5. Thực hiện thuật toán sinh luật quyết định từ tập rút gọn .................... - 55 3.5.6. Thực hiện thuật toán tìm tập rút gọn xấp xỉ ........................................ - 56 3.5.7. Thực hiện thuật toán tìm tất cả thuộc tính rút gọn .............................. - 56 KẾT LUẬN .............................................................................................................. - 57 TÀI LIỆU THAM KHẢO ........................................................................................ - 58 - -3- LỜI CẢM ƠN Trong quá trình tìm hiểu nghiên cứu và hoàn thành luận văn, tác giả luận văn xin gửi lời cảm ơn chân thành nhất đến GS.TS Vũ Đức Thi Viện Công nghệ thông tin Viện Khoa học và Công nghệ Việt Nam Ngƣời thầy đáng kính đã tận tình hƣớng dẫn và giúp đỡ tác giả hoàn thành luận văn này. Tác giả cũng xin gửi lời cảm ơn đế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ác giả những kiến thức quý báu trong suốt quá trình học tập tại trƣờng. Tác giả cũng xin chân thành cảm ơn những ngƣời thân và gia đình cùng bạn bè đã luôn ủng hộ, cổ vũ và động viên về cả vật chất lẫn tinh thần trong suốt quá trình hoàn thành luận văn tốt nghiệp. Xin chân thành cảm ơn! Hà Nội, tháng 12 năm 2013 Lê Thị Hân -4- LỜI CAM ĐOAN Tôi xin cam đoan: bản luận văn tốt nghiệp này là công trình nghiên cứu thực sự của riêng cá nhân tác giả, đƣợc thực hiện trên cơ sở nghiên cứu lý thuyết và thực nghiệm thông qua các phần mềm có mã nguồn mở dƣới sự hƣớng dẫn của GS.TS khoa học Vũ Đức Thi. Các số liệu, kết quả là trung thực chƣa đƣợc công bố ở bất cứ công trình nghiên cứu nào. Dữ liệu thực nghiệm có nguồn gốc rõ ràng và không mang tính chất thƣơng mại. Học viên -5- BẢNG CÁC KÝ HIỆU, VIẾT TẮT Ký hiệu, từ viết tắt IS  U , A,V , f  Diễn giải 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 SB u  Lớp tƣơng đƣơng chứa u của quan hệ IND  B  U/B  B (u ) Phân hoạch của U sinh bởi tập thuộc tính B . Hàm quyết định suy rộng của đối tƣợng u đối với 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  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 FRED  C  MRED  C  Họ tất cả các tập rút gọn dựa trên các phép toán trong đại số quan hệ Họ tất cả các tập rút gọn dựa trên metric KRED  C  Họ tất cả các tập rút gọn dựa trên độ khác biệt của tri thức 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 SCORE  C  Tập lõi sử dụng ma trận phân biệt MCORE  C  Tập lõi dựa trên metric 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 K  P Trong hệ thông tin đầy đủ, ký hiệu K  P  là tri thức sinh Lớp dung sai của đối tƣợng u trên quan hệ SIM  B  bởi tập thuộc tính P. Trong hệ thông tin không đầy đủ, ký hiệu K  P  là phủ sinh bởi tập thuộc tính P. -6- Ký hiệu, từ viết tắt d J  K  P  , K Q   Diễn giải Khoảng cách giữa K  P  và K  Q  trong hệ thông tin đầy đủ dựa trên khoảng cách Jaccard giữa hai tập hợp. dE  K  P  , K Q  Khoảng cách giữa K  P  và K  Q  trong hệ thông tin không đầy đủ dựa trên entropy Liang mở rộng DQP  K  P  , K  Q   Độ khác biệt giữa K  P  và K  Q  SĐQH Sơ đồ quan hệ Phụ thuộc hàm PTH -7- DANH SÁCH BẢNG Bảng 1.1. Bảng thông tin về bệnh cúm ................................................................... - 13 Bảng 1.2. Bảng quyết định về bệnh cúm .................................................................. - 15 Bảng 2.1. Bảng quyết định về bệnh cảm cúm .......................................................... - 26 Bảng 2.2. Bảng quyết định minh họa Ví dụ 2.1 ....................................................... - 28 Bảng 2.3 Bảng quyết định ở Ví dụ 2.3 ..................................................................... - 37 Bảng 2.4 Bảng quyết định ở Ví dụ 2.4 ..................................................................... - 39 Bảng 2.5 Bảng quyết định đƣợc xây dựng từ Thuật toán 2.8................................... - 44 Bảng 3.1. Kết quả thực hiện Thuật toán CEBARKCC và Thuật toán MBAR ........ - 47 Bảng 3.2. Tập rút gọn của Thuật toán CEBARKCC và Thuật toán MBAR ............ - 47 Bảng 3.3. Kết quả thực hiện Thuật toán CEBARKCC và Thuật toán MBAR ....... - 48 trên các bộ số liệu lớn ............................................................................................... - 48 Bảng 3.4. Tập rút gọn tốt nhất của bộ số liệu Soybean-small ................................. - 49 Bảng 3.5. 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ô ............. - 50 Bảng 2.6. Sự thay đổi tập rút gọn theo ngƣỡng độ chắc chắn  ............................ - 51 Bảng 2.7. Kết quả thử nghiệm Thuật toán REATA ................................................. - 52 - -8- DANH SÁCH HÌNH VẼ Hình 3.1. Sự thay đổi tập rút gọn theo ngƣỡng độ chắc chắn  ........................................ - 51 - -9- MỞ ĐẦU Khai phá dữ liệu là một trong những vấn đề rất sôi động hiện nay và đƣợc ứng dụng rộng rãi. Có rất nhiều phƣơng pháp khai phá dữ liệu, một trong những phƣơng pháp đó là sử dụng lý thuyết tập thô - một trong những công cụ quan trọng trong khai phá dữ liệu. 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út gọn dữ liệu, trích lọc các tri thức tiềm ẩn trong dữ liệu dƣới dạng mẫu và các luật quyết định, bảng quyết định. Trong thực tế, dữ liệu trong bảng quyết định thƣờng đa dạng và không đầy đủ, thiếu chính xác mà lại dƣ thừa nên bài toán rút gọn thuộc tính đƣợc đặt ra nhằm mục tiêu tạo ra các thuộc tính cốt yếu và cần thiết trong cơ sở dữ liệu (bảng). Hay nói cách khác, Rút gọn 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 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 đạt hiệu quả cao nhất. Trong những 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 hƣớng nghiên cứu về rút gọn thuộc tính trong lý thuyết tập thô. Trong xu thế đó nhiều nhóm nhà khoa học trên thế giới đã nghiên cứu các phƣơng pháp rút gọn thuộc tính theo các phƣơng pháp khác nhau, đáng chú ý là phƣơng pháp dựa trên miền dƣơng, phƣơng pháp sử dụng lý thuyết thông tin, phƣơng pháp sử dụng ma trận phân biệt đƣợc, phƣơng pháp dựa trên tính toán hạt, phƣơng pháp dựa trên metric… Mỗi phƣơng pháp đều phù hợp với một lớp bài toán trong thực 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 hành 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, mỗi phƣơng pháp rút gọn thuộc tính đều đƣa ra một thuật toán heuristic tìm tập rút gọn. Các 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ó khối lƣợng dữ liệu lớn. Chính vì vậy, mà Tôi đã chọn đề tài: “Nghiên cứu các tập Rút gọn trong bảng quyết định” làm luận văn tốt nghiệp. Trong luận văn này, chúng tôi nghiên cứu các vấn đề chính sau: - Tìm hiểu một số lý thuyết về hệ thống thông tin, bảng quyết định, tập rút gọn. - Tìm hiểu một số lý thuyết về cơ sở dữ liệu. - 10 - - Tìm hiểu một số thuật toán tìm một tập rút gọn và tất cả các tập rút gọn trong bảng quyết định. - Cài đặt thử nghiệm một thuật toán tìm tập rút gọn trong bảng quyết định. Bố cục luận văn gồm: Mở đầu: Đặt vấn đề về ý nghĩa, tính cấp thiết của đề tài Chƣơng 1: Các khái niệm cơ bản về lý thuyết tập thô và lý thuyết cơ sở dữ liệu quan hệ. Trong chƣơng này, sẽ đi tìm hiểu về các khái niệm hệ thống thông tin, bảng quyết định, tập rút gọn... và đi tìm hiểu về một số khái niệm nhƣ: quan hệ, phụ thuộc hàm, tiên đề Armstrong, khoá, phản khoá... và một số thuật toán cơ bản trong cơ sở dữ liệu quan hệ đƣợc sử dụng để xây dựng các thuật toán rút gọn trong bảng quyết định. Đây là những phần lý thuyết cơ sở để triển khai, nghiên cứu trong các chƣơng tiếp theo. Chƣơng 2: Tìm hiểu về một số thuật toán tìm một tập rút gọn và thuật toán tìm tất cả các tập rút gọn trong bảng quyết định nhất quán. Trong chƣơng này, chúng tôi đƣa ra một số thuật toán trên bảng quyết định liên quan đến tập rút gọn: xác định một tập rút gọn và tất cả các tập rút gọn trong bảng quyết định nhất quán (dựa trên lý thuyết cơ sở dữ liệu quan hệ). Chƣơng 3: Triển khai cài đặt thử nghiệm một thuật toán tìm một tập rút gọn trong bảng quyết định nhất quán, từ đó rút ra một số ứng dụng và kết luận. Kết luận. Tài liệu tham khảo - 11 - Chƣơng 1. CÁC KHÁI NIỆM VỀ LÝ THUYẾT TẬP THÔ VÀ CƠ SỞ DỮ LIỆU QUAN HỆ Lý thuyết tập thô - do Zdzislaw Pawlak [12] đề 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. Công cụ này cho phép biểu diễn một mô hình toán học về tri thức, nhờ đó tri thức đƣợc định nghĩa một cách rõ ràng dƣới dạng toán học và có thể đƣợc phân tích và xử lý bằng các công cụ mạnh mẽ và hiệu quả của toán học. 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, trích lọc các tri thức tiềm ẩn trong dữ liệu và đánh giá kết quả thu đƣợc. Trong lý thuyết tập thô, dữ liệu đƣợc biểu diễn thông qua một hệ 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. Phƣơng pháp tiếp cận chính của lý thuyết tập thô là dựa trên quan hệ không phân biệt được để đƣa ra các tập xấp xỉ biểu diễn tập đối tƣợng cần quan sát. Khi đó, mọi tập đối tƣợng đều đƣợc xấp xỉ bởi hai tập rõ là xấp xỉ dƣới và xấp xỉ trên của nó. 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 đó. Nếu tập xấp xỉ dƣới bằng tập xấp xỉ trên thì tập đối tƣợng cần quan sát là tập rõ, ngƣợc lại là tập thô. Các tập xấp xỉ là cơ sở để đƣa ra các kết luận từ dữ liệu. Bảng quyết định là một hệ thông tin IS 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 , 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. Nói cách khác, DS  U , C  D  với C  D   . 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. Bảng quyết định là nhất quán khi phụ thuộc hàm C  D là đúng, trái lại là không nhất quán. 1.1. Hệ thông tin đầy đủ 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à 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, với mọi aA a  A và u U hàm f cho giá trị f  u, a  Va . - 12 - 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 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 . Nếu với mọi u U và a  A , u  a  đều chứa giá trị khác rỗng thì hệ thông tin đƣợc gọi là hệ thông tin đầy đủ. Trong luận văn này, hệ thông tin đầy đủ đƣợc gọi tắt là hệ thông tin và đƣợc ký hiệu là IS  U , A,V , f  . Xét 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, u  a   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  u, v   IND B  thì hai đối tƣợng u và v không phân biệt đƣợc bởi các thuộc tính trong B. 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  . Định nghĩa 1.2. [9] 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 [9] 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 . 1.2. Mô hình tập thô truyền thống 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ô truyền thống, để 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 - 13 - 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ó 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 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  Y U / B Y  X  , BX   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)    BX  X U / D 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} = u1 , u2 , u3  , u4 , u5 , u6 , u7 , u8  U / {Thân nhiệt} = U / {Cảm cúm} = u , u ,u , u , u ,u , u , u  u , u , u , u ,u , u , u , u  1 1 4 4 2 5 8 5 7 2 3 3 6 6 7 8 - 14 U / {Đau đầu, Cảm cúm} = u1 , u2 , u3  , u4 , u5 , u8  , u6 , u7  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 . 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)    BX   u , u , u , u  . 1 2 3 4 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 . 1.3. Bảng quyết định đầy đủ 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 đầy đủ là một dạng đặc biệt của hệ thông tin đầy đủ, 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. Trong luận văn này, bảng quyết định đầy đủ đƣợc gọi tắt là bảng quyết định và đƣợc ký hiệu là DS  U , C  D,V , f  với 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 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. 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 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 - 15 - 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à cốt yếu. Định nghĩa 1.3. [8] (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. [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 , 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. 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 . Đị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 thực sự của DS nếu a  C   RPRED C  R. 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ó - 16 - 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 tính cần thiết 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 thực sự 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}). 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ự [2] đề 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 , f  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 ui (c)  u j (c) mi j     if ui ( D)  u j ( D), if ui ( D)  u j ( D) . Định nghĩa 1.7. [2, 7] (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,V , f  , M   mi j nn là ma trận phân biệt của DS và tập thuộc tính R  C . 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 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 dựa trên ma trận phân biệt. Định nghĩa 1.8. [2, 7] (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,V , f  , M   mi j  là ma trận phân biệt của DS. Thuộc tính c  C nn đƣợc gọi là không cần thiết (dƣ thừa) trong DS dựa trên ma trận phân biệt nếu C  c  mi j   với mọi mi j   . 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 ma trận phân biệt và đƣợc ký hiệu là SCORE  C  . Theo [7], SCORE C    R . RSRED C  - 17 - 1.6. Một số khái niệm cơ bản về cơ sở dữ liệu quan hệ Mục này trình bày các khái niệm cơ bản nhất về mô hình dữ liệu quan hệ của E.F. Codd. Những khái niệm này bao gồm quan hệ, phụ thuộc hàm, hệ tiên đề Armstrong, sơ đồ quan hệ, khoá, phản khoá... Các khái niệm này có thể xem trong [3,4,5,13]. 1.6.1. Quan hệ Cho R  a1 ,..., an  là tập hữu hạn, khác rỗng các thuộc tính, mỗi thuộc tính ai có miền giá trị là D  ai  . Quan hệ r trên R là tập các bộ h1 ,..., hm  với h j : R   D  ai  ,1  j  m là một hàm sao cho h j  ai   D  ai  . ai R Về mặt trực quan, quan hệ r là một bảng, mỗi cột là một thuộc tính và mỗi dòng là một bộ. 1.6.2. Phụ thuộc hàm Cho R  a1 ,..., an  là tập hữu hạn, khác rỗng các thuộc tính, r  h1 ,..., hm  là một quan hệ trên tập thuộc tính R  a1 ,..., an  . Phụ thuộc hàm (PTH) trên R là một dãy ký tự có dạng A B với A, B  R. PTH A B thỏa mãn quan hệ r trên R nếu  hi , hj  r   a  A  hi  a   hj  a    b  B  hi  b  hj  b  . Đặt Fr   A, B  : A, B  R, A  B là họ đầy đủ các PTH thỏa mãn quan hệ r. Khi đó tất cả các PTH đúng trong r. 1.6.3. Hệ tiên đề Armstrong Giả sử R là tập các thuộc tính, ký hiệu P  R  là tập các tập con của R. Cho F  P  R   P  R  . Ta nói rằng F là một họ f trên R nếu với mọi A, B, C, D  R 1 2  3  4  A, A  F .  A, B   F ,  B, C   F   A, C   F .  A, B   F , A  C, D  B  C, D   F .  A, B   F , C, D   F   A  C, B  D   F . Rõ ràng là Fr là một họ f trên R. Nếu F là một họ f trên R thì có một quan hệ r trên R sao cho Fr = F. Ký hiệu F  là tập tất cả các PTH đƣợc dẫn xuất từ F bằng việc áp dụng các quy tắc 1   4  . 1.6.4. Sơ đồ quan hệ Sơ đồ quan hệ (SĐQH) s là một cặp  R, F  với R là tập thuộc tính và F là tập các phụ thuộc hàm trên R. Ký hiệu A  a : A  a   F   , A đƣợc gọi là bao đóng của A trên s. Dễ thấy A  B  F  khi và chỉ khi B  A . Tƣơng tự ký hiệu A  a : A  a  F  r  , - 18 Ar  đƣợc gọi là bao đóng của A trên quan hệ r. Nếu + s   R, F  là một sơ đồ quan hệ r trên R sao cho Fr =F , quan hệ r nhƣ vậy gọi là Armstrong của s. Trong trƣờng hợp này hiển nhiên các PTH của s đúng trong r. 1.6.5. Khoá và phản khoá Cho r là một quan hệ, s   R, F  là một SĐQH và A  R . Khi đó A là một khóa của r (tƣơng ứng của s) nếu A  R  A  R  F   . Ta gọi A là một khóa tối thiểu của r (tƣơng ứng của s) nếu: - A là một khóa của r (tƣơng ứng của s). - Bất kỳ một tập con thực sự của A không là khóa của r (tƣơng ứng của s). Ký hiệu K r và K s tƣơng ứng là tập tất cả các khóa tối thiểu của r và s. Cho s   R, F  là SĐQH trên R, a  R . Đặt K as   A  R : A  a,  B :  B  a  B  A . Khi đó, K as đƣợc gọi là họ các tập tối thiểu của thuộc tính a trên s. Tƣơng tự, cho r là một quan  hệ trên R  K ar  A  R : A  a ,  B :  B  a  B  A . Khi đó, K và r a aR . Đặt đƣợc gọi là họ các tập tối thiểu của thuộc tính a trên r. Gọi K  P  R  là một hệ Sperner trên R nếu với mọi A, B K kéo theo A  B . Dễ thấy K r , K s , K ar , K as là các hệ Sperner trên R. Với tập K là một hệ Sperner trên R, Giả sử K là một hệ Sperner trên R. Ta định nghĩa tập các phản khoá của K là K 1 nhƣ sau: K 1   A  R :  B  K    B  A và nếu  A  C    B  K  B  C  Dễ thấy K 1 cũng là một hệ Sperner trên R. Nhận xét: Nếu K là một hệ Sperner trên R đóng vai trò là tập các khóa tối thiểu của quan hệ r (hoặc SĐQH s) thì K 1 là họ tất cả các tập không phải khóa lớn nhất của r (hoặc của s), gọi là tập các phản khóa. Nếu K là một hệ Sperner trên R đóng vai trò là họ các tập tối thiểu của thuộc tính a trên r (hoặc trên s), hay K  K ar (hoặc K  K as ), thì K 1  K ar  (hoặc K 1  K as  ) là họ 1 1 tất cả các tập lớn nhất không phải là tập tối thiểu của thuộc tính a, đƣợc định nghĩa nhƣ sau [4] K    A  R : A  a  F K    A  R : A  a  F r a s a 1 1  r   , A  B  B  a  F  . , A  B  B  a  Fr , 