ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG ------------------ CHỬ THỊ QUỲNH HOA NGHIÊN CỨU MỐI QUAN HỆ GIỮA PHỤ THUỘC HÀM VÀ BẢNG QUYẾT ĐỊNH TRONG CHẨN ĐOÁN BỆNH LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên - 2015 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn LỜI CẢM ƠN Em xin chân thành bày tỏ lòng biết ơn sâu sắc đến TS. Lê Văn Phùng, người thầy đã hết lòng giúp đỡ và tạo điều kiện tốt nhất để em hoàn thành luận văn này. Em xin chân thành cảm ơn toàn thể các Thầy, cô công tác tại Viện CNTT và Trường Đại học Công Nghệ Thông Tin và Truyền Thông - Đại Học Thái Nguyên đã luôn tận tình chỉ bảo, giúp đỡ, tạo điều kiện và truyền đạt kiến thức cho em trong suốt quá trình học tập và thực hiện luận văn. Xin chân thành cảm ơn Ban Giám Hiệu Trường THPT Định Hóa, gia đình, bạn bè và đồng nghiệp đã không ngừng quan tâm, động viên, giúp đỡ và tạo mọi điều kiện tốt nhất cho tôi trong suốt thời gian học tập và thực hiện luận văn. Mặc dù đã cố gắng rất nhiều, 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. Em rất mong nhận được các ý kiến phê bình, góp ý của Hội đồng bảo vệ luận văn, các thầy cô giáo và đồng nghiệp để luận văn được hoàn chỉnh hơn. Thái Nguyên, ngày 09 tháng 05 năm 2015 Học viên Chử Thị Quỳnh Hoa Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn LỜI CAM ĐOAN Tôi xin cam đoan luận văn này là sản phẩm do tôi tổng hợp và nghiên cứu. Trong luận văn có sử dụng một số định nghĩa, bổ đề, hệ quả, thuật toán lấy từ nguồn tài liệu có trích dẫn tên tài liệu và tên tác giả rõ ràng như đã nêu trong phần tài liệu tham khảo. Tôi xin chịu trách nhiệm về sản phẩm nghiên cứu của mình. Học viên Chử Thị Quỳnh Hoa Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn i MỤC LỤC Lời cam đoan MỤC LỤC ..................................................................................................... i Danh mục các thuật ngữ ................................................................................ iv Danh mục các ký hiệu, các từ viết tắt ........................................................... v Danh sách bảng ............................................................................................. vii Danh sách hình vẽ ......................................................................................... viii MỞ ĐẦU ....................................................................................................... 1 Chƣơng 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ BÀI TOÁN CHẨN ĐOÁN BỆNH ................................................................................... 3 1.1. Các khái niệm cơ bản về hệ thông tin và tập thô .............................. 3 1.1.1. Hệ thông tin .................................................................................. 3 1.1.2. Tập thô.......................................................................................... 5 1.1.3. Bảng quyết định .......................................................................... 8 1.1.4. Cơ sở dữ liệu quan hệ .................................................................. 10 1.1.5. Tập rút gọn và lõi ........................................................................ 12 1.1.6. Luật quyết định ........................................................................... 14 1.2. Khai phá dữ liệu ................................................................................... 15 1.2.1. Khai phá dữ liệu và phát hiện tri thức ......................................... 15 1.2.2. Các chức năng khai phá dữ liệu .................................................. 17 1.2.3. Các hệ thống khai phá dữ liệu và kiến trúc tổng quát của chúng.. 18 1.2.4. Các loại dữ liệu có thể khai phá được .......................................... 22 1.2.5. Khai phá dữ liệu theo hướng tiếp cận tập thô .............................. 22 1.3. Bài toán chẩn đoán bệnh ...................................................................... 23 1.3.1. Vai trò của phương pháp chẩn đoán lâm sàng trong y học ......... 23 1.3.2. Giá trị thực tiễn của việc xác định quan hệ giữa phụ thuộc hàm và bảng quyết định trong chẩn đoán bệnh ................................................. 24 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn ii 1.4. Kết luận chƣơng 1 ................................................................................ 26 Chƣơng 2. MỐI QUAN HỆ GIỮA PHỤ THUỘC HÀM VÀ BẢNG QUYẾT ĐỊNH THEO HƢỚNG TIẾP CẬN TẬP THÔ ......................... 27 2.1. Xác định các phụ thuộc hàm từ bảng quyết định ............................. 27 2.1.1. Thuộc tính rút gọn và các thuật toán tìm chúng ......................... 27 2.1.2. Thuật toán tìm họ tất cả các tập rút gọn trong bảng quyết định .. 36 2.1.3. Tập lõi trong bảng quyết định ..................................................... 38 2.1.4. Thuật toán xác định các phụ thuộc hàm từ bảng quyết định .. .... 42 2.2. Xây dựng bảng quyết định từ tập phụ thuộc hàm ............................ 44 2.2.1. Sự phụ thuộc giữa các thuộc tính trong bảng quyết định ........... 44 2.2.2. Một số thuật toán cơ bản liên quan đến phụ thuộc hàm ............. 45 2.2.3. Thuật toán xây dựng bảng quyết định từ tập phụ thuộc hàm ... .. 50 2.3. Kết luận chƣơng 2 ................................................................................. 54 Chƣơng 3. CHƢƠNG TRÌNH THỬ NGHIỆM ....................................... 55 3.1. Bài toán chẩn đoán bệnh cúm .............................................................. 55 3.1.1. Yêu cầu nghiệp vụ ....................................................................... 55 3.1.2. Yêu cầu công nghệ ...................................................................... 57 3.2. Thiết kế chƣơng trình .......................................................................... 57 3.2.1. Thiết kế cơ sở dữ liệu .................................................................. 57 3.2.2. Thiết kế xử lý .............................................................................. 59 3.2.3. Thiết kế các mô-đun và lược đồ chương trình ............................ 60 3.3. Cài đặt và thực hiện chƣơng trình ..................................................... 63 3.3.1. Các chức năng chương trình ....................................................... 63 3.3.2. Hệ thống dữ liệu đầu vào ............................................................ 64 3.3.3. Hệ thống giao diện ...................................................................... 65 3.3.4. Kết quả thử nghiệm chương trình và đánh giá ............................ 67 3.4. Kết luận chƣơng 3 ................................................................................. 71 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn iii KẾT LUẬN .................................................................................................... 72 Tài liệu tham khảo ......................................................................................... 73 PHỤ LỤC ...................................................................................................... 75 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn iv 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 Quan hệ dung sai Tolerance 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 Quan hệ Relation Sơ đồ quan hệ Relation Schema Phụ thuộc hàm Functional Dependency Khóa, phản khóa Key, Antikey Tập tối thiểu của thuộc tính a Minimal set of the attribute a Họ các tập tối thiểu của thuộc tính Family of all minimal sets of attribute a a Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn v Danh mục các ký hiệu, các từ viết tắt Ký hiệu, từ viết tắt Diễn giải S  U , A Hệ thông tin T  U , C  D  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 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 . 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 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 dựa trên ma trận phân biệt ECORE  C  Tập lõi dựa trên entropy Liang có điều kiện MCORE  C  Tập lõi dựa trên metric Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn vi CSDL Cơ sở dữ liệu SĐQH Sơ đồ quan hệ PTH Phụ thuộc hàm Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn vii Danh sách bảng Bảng 1.1. Bảng dữ liệu về bệnh cúm ............................................................4 Bảng 1.2. Bảng thông tin về bệnh cúm .........................................................7 Bảng 1.3. Bảng quyết định ...........................................................................9 Bảng 1.4. Bảng quyết định về bệnh cúm ......................................................14 Bảng 2.1. Bảng quyết định ở Ví dụ 2.1 ........................................................30 Bảng 2.2. Bảng quyết định về bệnh cúm ở Ví dụ 2.2 ...................................32 Bảng 2.3. Bảng rút gọn thứ nhất của hệ thống bệnh cúm R1 .......................33 Bảng 2.4. Bảng rút gọn thứ hai của hệ thống bệnh cúm R2 .........................33 Bảng 2.5. Bảng quyết định ở Ví dụ 2.3 ........................................................37 Bảng 2.6. Bảng quyết định minh họa Ví dụ 2.4 ............................................41 Bảng 2.7. Bảng quyết định được xây dựng từ Thuật toán 2.16 ....................54 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn viii Danh sách hình vẽ Hình 1.1. Quá trình phát hiện tri thức ..........................................................16 Hình 1.2. Kiến trúc của một hệ thống khai phá dữ liệu điển hình ............... 20 Hình 2.1. Sơ đồ thuật toán xây dựng các phụ thuộc hàm từ bảng quyết định ........................................................................................................................ 43 Hình 2.2. Sơ đồ thuật toán xây dựng bảng quyết định từ tập phụ thuộc hàm ........................................................................................................................ 51 Hình 3.1. Màn hình giao diện chương trình ................................................. 65 Hình 3.2. Màn hình xây dựng bảng quyết định ............................................ 65 Hình 3.3. Màn hình xây dựng bảng thuộc tính rút gọn ................................ 66 Hình 3.4. Màn hình xây dựng các phụ thuộc hàm và luật quyết định từ bảng quyết định ...................................................................................................... 67 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 1 MỞ ĐẦU Lý thuyết tập thô (Rough Set Theory) do Zdzislaw 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 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. Mục đích chính của phân tích dữ liệu dựa trên lý thuyết tập thô nhằm đưa ra các xấp xỉ để biểu diễn các đối tượng không thể được phân lớp một cách chắc chắn bằng tri thức có sẵn. Theo quan điểm của lý thuyết tập thô, mọi tập thô đều liên kết vớ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 đó. Các tập xấp xỉ là cơ sở để rút ra các kết luận (tri thức) từ cơ sở dữ liệu. Trong lý thuyết tập thô, mô hình biểu diễn dữ liệu được trình bày thông qua hệ thông tin hay bảng quyết định. Bảng quyết định là một hệ thông tin có dạng T = (U,A), với U là tập các đối tượng và A là tập các thuộc tính, trong đó tập thuộc tính A được chia thành hai tập thuộc tính con khác rỗng rời nhau là C và D, C được gọi là tập thuộc tính điều kiện và D là tập thuộc tính quyết định. Tức là T = (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. Với bảng quyết định nhất quán T = (U,C  D) , tập thuộc tính R  C được gọi là một tập rút gọn của tập thuộc tính điều kiện C nếu R là tập tối Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 2 thiểu thỏa mãn phụ thuộc hàm R  D . Giả sử D chỉ chứa một thuộc tính duy nhất d  , nếu xem bảng quyết định T là quan hệ r trên tập thuộc tính C  d  thì khái niệm tập rút gọn 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 đó, một số bài toán trong bảng quyết định liên quan đến tập rút gọn có thể được giải quyết bằng một số kết quả liên quan đến tập tối thiểu của một thuộc tính trong lý thuyết cơ sở dữ liệu quan hệ; bao gồm bài toán tìm tập tất cả các thuộc tính rút gọn, bài toán trích lọc các phụ thuộc hàm từ bảng quyết định, bài toán xây dựng bảng quyết định thỏa mãn tập phụ thuộc hàm cho trước. Do tính hấp dẫn và tính thời sự của khai phá dữ liệu, đặc biệt là mối quan hệ giữa phụ thuộc hàm và bảng quyết định để từ bảng quyết định trích lọc các phụ thuộc hàm và xây dựng bảng quyết định thỏa mãn tập phụ thuộc hàm cho trước nên tôi lựa chọn đề tài “Nghiên cứu mối quan hệ giữa phụ thuộc hàm và bảng quyết định trong chẩn đoán bệnh” là luận văn cao học của mình. Trong đó vận dụng kiến thức nghiên cứu này vào chẩn đoán bệnh lâm sàng trong lĩnh vực y học. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 3 Chƣơng 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ BÀI TOÁN CHẨN ĐOÁN BỆNH 1.1. Các khái niệm cơ bản về hệ thông tin và tập thô 1.1.1. Hệ thông tin Một tập dữ liệu có thể biểu diễn dưới dạng một bảng, trên đó mỗi hà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 mỗi đối tượng (do các chuyên gia hay người sử dụng cung cấp). Bảng này được gọi là một hệ thông tin. 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 (Information System) là một cặp S = (U, A). Trong đó: U là một tập hữu hạn khác rỗng các đối tượng gọi là tập vũ trụ hay là tập phổ dụng. A là một tập hữu hạn khác rỗng các thuộc tính. Với mỗi u  U và a  A , ta ký hiệu u(a) là giá trị của đối tượng u tại thuộc tính a. Nếu gọi Ia là tập tất cả các giá trị của thuộc tính a, thì u(a)  Ia với mọi u  U. Bây giờ, nếu B=b1,b2 ,...,bk   A , 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 sẽ viết u(B) = v(B) nếu u(bi)= v(bi), với mọi i = 1, 2, ..., k. [6] Định nghĩa 1.2. Quan hệ không phân biệt đƣợc Xét hệ thông tin S = (U, A), với mỗi tập thuộc tính B  A tạo ra một quan hệ hai ngôi trên U, ký hiệu IND(B) IND(B) = u,v   U  U | u  a   v  a  , a  B IND(B) được gọi là quan hệ B_không phân biệt được. Dễ kiểm chứng đây là một quan hệ tương đương trên U. Nếu (u, v)  IND( B) thì hai đối Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 4 tượng u và v giống nhau (không phân biệt được) nếu chỉ xem xét giá trị tại các thuộc tính trong B. Quan hệ tương đương IND(B) xác định một phân hoạch trên U, ký hiệu U/IND(B) hay U/B, tức là U/IND(B) = U/B =  u B | u  U . Với mọi đối tượng u  U, lớp tương đương của u trong quan hệ IND(B) được ký hiệu bởi [u]B. Khi đó [u]B = {vU|(u,v) IND(B)}. [6] Ví dụ 1.1. Xét hệ thông tin cho ở bảng 1.1 U Đau đầu Đau cơ Thân nhiệt Cúm u1 Không Có Bình thường Không u2 Có Không Cao Không u3 Không Có Cao Có u4 Có Không Cao Có u5 Không Có Rất cao Có u6 Có Có Rất cao Có Bảng 1.1. Bảng dữ liệu về bệnh cúm Trong đó: U = {u1, u2, u3, u4, u5, u6} A = {Đau đầu, Đau cơ, Thân nhiệt, Cúm} Trong bảng, các bệnh nhân u2, u4 và u6 không phân biệt được đối với thuộc tính Đau đầu; bệnh nhân u5 và u6 không phân biệt được đối với thuộc tính Đau cơ, Cúm và bệnh nhân u2, u4 không phân biệt được đối với thuộc tính Đau đầu, Đau cơ và Thân nhiệt. Do đó: IND({Đau đầu}) = {{u1, u3, u5},{u2, u4, u6}} IND({Đau cơ}) = {{u1, u3, u5, u6},{u2, u4}} IND({Thân nhiệt}) = {{u2, u3, u4},{u5, u6}, {u1}} IND({Cúm}) = {{u3, u4, u5, u6},{ u1, u2}} IND({Đau đầu, Đau cơ}) = {{u1, u3, u5},{u2, u4}, { u6}} Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 5 Xét hệ thông tin S = (U, A), một quan hệ bộ phận xác định trên họ U/B | B  A được định nghĩa: U/P U/Q nếu và chỉ nếu Pi  U / P, Q j  U / Q : Pi  Q j . Khi đó ta nói Q là thô hơn P hay P là mịn hơn Q. 1.1.2. Tập thô Cho hệ thông tin S  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 . 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 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 ứng với quan hệ R 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, POSB ( X )  BX : B-vùng dương của X NEGB  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: Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 6 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,  POS B ( D)  u U u B  u D .  Trên cơ sở đó có thể tính B-xấp xỉ dưới và B-xấp xỉ trên của X nhờ thuật toán sau: Thuật toán 1.1. [2] Xác định xấp xỉ dƣới, xấp xỉ trên Đầu vào: Hệ thông tin S = (U, A), tập thuộc tính B  A , tập đối tượng X U . Đầu ra: Tập các đối tượng BX và BX Phƣơng pháp: 1. Xác định các lớp tương đương X1B , X 2B ,......, X mB của IND(B) 2. Khởi tạo BX : ; và BX : ; 3. Với mọi giá trị của j  1,...., m begin Nếu X Bj  X thì BX : BX  X Bj Nếu X Bj  X   thì BX : BX  X Bj end. Thuật toán 1.1 có độ phức tạp là O(k|U|log|U|), trong đó |B|  |A| = k. [2] Ví dụ 1.2. Xét hệ thông tin biểu diễn các triệu chứng cúm của bệnh nhân Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 7 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 Cao Có u7 Không Rất cao Không u8 Không Rất cao Có Bảng 1.2. Bảng thông tin về bệnh cúm Ta có: U / {Đau đầu} = u1, u2 , u3,u4 , u5 , u6 , u7 , u8 U / {Thân nhiệt} = u1, u4 ,u2 , u5 , u6,u3 , u7 , u8 U / {Cảm cúm} = u1, u4 , u5 , u7 ,u2 , u3 , u6 , u8 U / {Đau đầu, Cảm cúm} = 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 đượ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 , u6, u7 , u8 . Đặt X  {u u (Cảm cúm) = Có} = u2 , u3 , u6 , u8 . 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 , u7 ; X 2  u2 , u3 , u6 , u8, BX1  u1, u4  ; BX 2  u2 , u3 , POS B ( D)   BX   u1, u2 , u3 , u4 . X U / D Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 8 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] 1.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 (còn được gọi là hệ quyết định: decision system) là một dạng đặc biệt của hệ thông tin T đầy đủ, trong đó tập các thuộc tính A bao gồm hai tập con khác rỗng 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. Tức là, T  U , C  D  với C  D   . Trong trường hợp không sợ bị nhầm lẫn người ta còn ký hiệu T  U , 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 T được gọi là nhất quán (consistent) 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 T là không nhất quán (inconsistent) hay mâu thuẫn. Dễ thấy bảng quyết định T 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. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 9 Ví dụ 1.3. Hệ thông tin S = (U, A) biểu diễn cơ sở tri thức về bệnh cúm được thể hiện trong bảng 1.3 là một bảng quyết định T  U , C  D  Trong đó: U  x1, x2 , x3 , x4 , x5 , x6  A = {Đau đầu, Đau cơ, Thân nhiệt, Cúm} Tập thuộc tính điều kiện C = {Đau đầu, Đau cơ, Thân nhiệt} Tập thuộc tính quyết định D = {Cúm} U Đau đầu Đau cơ Thân nhiệt Cúm x1 Không Có Cao Có x2 Có Không Cao Có x3 Có Có Rất cao Có x4 Không Có Bình thường Không x5 Có Không Cao Không x6 Không Có Rất cao Có Bảng 1.3. Bảng quyết định Cho một bảng quyết định T  U , C  D  , giả sử U / C   X1, X 2 ,..., X m và U / D  Y1,Y2 ,...,Yn  . Một lớp X i U / C được gọi là nhất quán nếu u(d )  v(d ), u, v  X i , d  D, lúc này cũng có thể viết u( D)  v( D)  X i ( D); một lớp Yi U / D được gọi là nhất quán ngược nếu u(a)  v(a), u, v Yi , a  C. Một bảng quyết định T  U , C  D  là nhất quán nếu mọi lớp X i U / C là nhất quán, ngược lại T được gọi là không nhất quán. Dễ thấy nếu U / C U / D thì T  U , C  D  là nhất quán. Tương tự, nếu U / D U / C, thì T là nhất quán ngược. [6] Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn