›
›

Đề tài Ứng dụng tập thô trong lập luận từ dữ liệu

doc 27 trang phuongnguyen 3260
Download
Bạn đang xem 20 trang mẫu của tài liệu "Đề tài Ứng dụng tập thô trong lập luận từ dữ liệu", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • docde_tai_ung_dung_tap_tho_trong_lap_luan_tu_du_lieu.doc

Nội dung text: Đề tài Ứng dụng tập thô trong lập luận từ dữ liệu

  1. ĐỀ TÀI ỨNG DỤNG TẬP THƠ TRONG LẬP LUẬN TỪ DỮ LIỆU 1 Sinh viên: Trịnh Văn Dương – Lớp KHMT4K5
  2. 1. MỞ ĐẦU 3 1. MỞ ĐẦU 3 2. VÍ DỤ 4 3. TẬP THƠ VÀ CÁC XẤP XỈ 5 4. CÁC TẬP THƠ VÀ HÀM THUỘC 8 5. CÁC BẢNG QUYẾT ĐỊNH VÀ THUẬT GIẢI QUYẾT ĐỊNH 10 6. SỰ PHỤ THUỘC VÀO CÁC THUỘC TÍNH 11 7. THU GỌN CÁC THUỘC TÍNH 13 8. CÁC HÀM VÀ MA TRẬN PHÂN BIỆT 19 9. ĐỘ QUAN TRỌNG CỦA CÁC THUỘC TÍNH VÀ CÁC THU GỌN XẤP XỈ 23 10. KẾT LUẬN 26 2 Sinh viên: Trịnh Văn Dương – Lớp KHMT4K5
  3. 1. Mở Đầu Các tập thơ được xây dựng trên lý thuyết tập hợp. Ta thường sử dụng thêm một số thơng tin về các phần tử của một tập tổng thể. Các phần tử cĩ cùng thơng tin là khơng phân biệt được và tạo thành một khối cĩ thể được xem như là các hạt cơ bản của tri thức về tập tổng thể đĩ. Chẳng hạn, các bệnh nhân mắc phải một căn bệnh nào đĩ cĩ cùng các triệu chứng là khơng phân biệt được và cĩ thể được biểu diễn như một hạt (khối bệnh) trong tri thức y học. Những hạt này được gọi là các tập phần tử cơ bản và cĩ thể xem như là những phần tử xây dựng nên các khối tri thức. Phù hợp với tính chất hạt của tri thức, các tập thơ cũng được mơ tả bằng các tri thức cĩ được. Do đĩ, với mỗi tập hợp khi khơng phân biệt được các phần tử một cách chính xác thì ta gắn nĩ với hai tập hợp rõ được gọi là xấp xỉ trên và xấp xỉ dưới. Theo trực giác, xấp xỉ dưới của một tập chứa tất cả các phần tử chắc chắn thuộc vào tập đĩ, cịn xấp xỉ trên được tạo thành từ tất cả các phần tử cĩ thể thuộc vào tập này. Phần khác biệt giữa xấp xỉ trên và xấp xỉ dưới gọi là vùng biên. Vùng biên chứa tất cả các phần tử khơng được phân lớp một cách duy nhất thuộc vào một tập hợp hoặc phần bù của nĩ khi sử dụng các tri thức cĩ được. Do đĩ, mỗi tập thơ khác với tập thơng thường là nĩ cĩ vùng biên thường khác rỗng. Bộ lý thuyết tập thơ được xác định xấp xỉ. Thơng báo, mà bộ thường được xác định bởi các hàm thành viên. Bộ thơ cĩ thể được xác định bằng cách sử dụng, thay vì xấp xỉ, thành viên chức năng, tuy nhiên hàm thành viên khơng phải là một khái niệm nguyên thủy trong cách tiếp cận này, và cả hai định nghĩa là khơng tương đương. Trong bài báo này chúng tơi định nghĩa các khái niệm cơ bản của lý thuyết tập thơ dưới dạng dữ liệu. Các khái niệm này sẽ được áp dụng để thực hiện lập luận từ dữ liệu. Các tập trong lý thuyết tập thơ được định nghĩa bằng các xấp xỉ dựa trên hàm thuộc. 3 Sinh viên: Trịnh Văn Dương – Lớp KHMT4K5
  4. 2. VÍ DỤ Trước tiên, chúng tơi trình bày một ví dụ đơn giản để mơ tả phương pháp một cách trực quan. Dữ liệu được biểu diễn bằng một bảng, các cột là các thuộc tính, các hàng là các đối tượng cịn mỗi ơ trong bảng là giá trị của thuộc tính của đối tượng tương ứng. Ví dụ trong một bảng cĩ thơng tin về các bệnh nhân nhiễm phải một căn bệnh nào đĩ, các đối tượng là các bệnh nhân, các thuộc tính cĩ thể là: huyết áp, nhiệt độ cơ thể Những bảng như vậy được gọi là các hệ thơng tin hoặc các bảng thơng tin. Dưới đây là một ví dụ về một bảng thơng tin Giả sử chúng ta cĩ dữ liệu về 6 bệnh nhân như trong bảng 1 dưới đây. Bệnh Đau đầu Đaucơ Nhiệt độ Bị bệnh cúm nhân (Headache) (Muscle- (Temperature) (Flu) (Patient) pain) p1 khơng cĩ cao cĩ p2 cĩ khơng cao cĩ p3 cĩ cĩ rất cao cĩ p4 khơng cĩ bình thường khơng p5 cĩ khơng cao khơng p6 khơng cĩ rất cao cĩ Bảng 1 Các cột của bảng được gán nhãn bởi các thuộc tính là các triệu chứng và các hàng là các đối tượng (các bệnh nhân). Do đĩ, các ơ của bảng là giá trị của các thuộc tính của các đối tượng. Mỗi hàng của bảng cĩ thể được xem như thơng tin về một bệnh nhân nào đĩ. Ví dụ bệnh nhân p2 được biểu diễn trong bảng bởi tập giá trị-thuộc tính như sau: (Đau đầu, cĩ), (Đau cơ, khơng), (Nhiệt độ, cao), (Bị bệnh cúm, cĩ). 4 Sinh viên: Trịnh Văn Dương – Lớp KHMT4K5
  5. Trong bảng 1 các bệnh nhân p2, p3, và p5 là khơng phân biệt được với thuộc tính đau đầu, các bệnh nhân p3 và p6 là khơng phân biệt được với thuộc tính đau cơ và bị bệnh cúm,và các bệnh nhân p2 và p5 là khơng phân biệt được với các thuộc tính đau đầu, đau cơ và nhiệt độ. Do đĩ, thuộc tính đau đầu sinh ra hai tập cơ bản {p2, p3, p5} và {p1, p4, p6}, trong khi các thuộc tính đau đầu và đau cơ tạo thành các tập cơ bản sau: {p1, p4, p6}, {p2, p5} và {p3}. Tương tự chúng ta cĩ thể định nghĩa các tập cơ bản sinh bởi một tập con các thuộc tính. Bệnh nhân p2 bị bệnh cúm, trong khi bệnh nhân p5 thì khơng. Họ là khơng phân biệt được với thuộc tính đau đầu, đau cơ và nhiệt độ. Do đĩ, bị bệnh cúm khơng thể biểu diễn được theo các thuộc tính đau đầu, đau cơ và nhiệt độ. Vì vậy p2 và p5 là các trường hợp biên, chúng khơng thể được phân lớp một cách đúng đắn theo quan sát bằng các tri thức cĩ được. Các bệnh nhân cịn lại p1, p3 và p6 cĩ các triệu chứng cho phép chúng ta cĩ thể phân lớp một cách chính xác khi bị bệnh cúm. Các bệnh nhân p2 và p5 khơng được coi là cùng bị cúm và p4 chắc chắn khơng bị cúm. Do đĩ xấp xỉ dưới của tập các bệnh nhân bị cúm là tập {p1, p3, p6} và xấp xỉ trên của tập này là {p1, p2, p3, p5, p6}, trong đĩ trường hợp biên là các bệnh nhân p2 và p5. Tương tự p4 khơng bị cúm và p2, p5 khơng thể được coi như bị cúm. Do đĩ, xấp xỉ dưới của khái niệm khơng bị cúm là {p4} và xấp xỉ trên là tập {p2, p4, p5}, vùng biên của nĩ là tập {p2, p5} giống như trong trường hợp trước. 3. Tập thơ và các xấp xỉ Như đã đề cập trong phần mở đầu, cơ sở của lý thuyết tập thơ là quan hệ “khơng phân biệt được” được sinh ra từ thơng tin về các đối tượng. Quan hệ khơng phân biệt được, được sử dụng để biểu diễn tình trạng thiếu tri thức khi ta khơng thể phân biệt được một số đối tượng. Điều đĩ cĩ nghĩa là khơng thể xử lý các đối tượng một cách đơn lẻ nhưng cĩ thể nghiên cứu cụm các đối tượng theo quan hệ khơng phân biệt được. 5 Sinh viên: Trịnh Văn Dương – Lớp KHMT4K5
  6. Giả sử cĩ hai tập rỗng U và A, trong đĩ U là tập tổng thể và A là tập các thuộc tính. Với mỗi thuộc tính a A, ký hiệu V a là tập tất cả các giá trị cĩ thể của a và gọi là miền của a. Định nghĩa 1: Mỗi tập con B  A xác định một quan hệ khơng phân biệt được I(B) trên U, được định nghĩa như sau: Mọi x, y U, x I(B)y mọi a B, a(x)=a(y), trong đĩ a(x) biểu diễn giá trị tại thuộc tính a của phần tử x. Hiển nhiên, I(B) là một quan hệ tương đương. Lớp tương đương của I(B) chứa x được kí hiệu bởi B(x). Họ tất cả các lớp tương đương của I(B) là một phân hoạch của tập U xác định bởi B được ký hiệu là U/I(B), hoặc là U/B. Nếu (x,y) I/B thì ta nĩi rằng x và y là B-khơng phân biệt được. Các lớp tương đương của quan hệ I(B) được nghiên cứu như các tập B-phần tử. Trong phương pháp tập thơ các tập phần tử là các khối cơ bản các khái niệm của các tri thức thực tế. Quan hệ tương đương trên được sử dụng để định nghĩa các xấp xỉ như sau: B X x U : B x  X , B X x U : B x  X  Nghĩa là, ta gắn với mỗi tập con X của tập tổng thể U hai tập B *(X) và B*(X) và gọi chúng là B-xấp xỉ dưới và B-xấp xỉ trên của X. Tập hợp BNB (X ) B (X ) B (X ) được gọi là B-vùng biên của X. Nếu vùng biên của X là tập rỗng thì tập X là tập rõ theo B. Ngược lại nếu BNB(X) =  thì tập X là tập thơ theo B. Một số tính chất của các xấp xỉ: 1)B (X )  X  B (X ) , 2)B () B () ; B (U ) B (U ) U , 3)B (X Y B (X )  B (Y) , 6 Sinh viên: Trịnh Văn Dương – Lớp KHMT4K5
  7. 4)B (X Y ) B (X )  B (Y ) , 5) X  Y B (X ) và B (Y ) B (X ) , B (Y ) 6)B (X Y )  B (X )  B (Y ) , 7)B (X Y )  B (X )  B (Y ) , 8)B ( X ) B (X ) , 9)B ( X ) B (X ) , 10)B (B (X )) B (B (X )) B (X ) , 11) B (B (X )) B (B (X )) B (X ) trong đĩ: -X ký hiệu thay cho U\X và là phần bù của X Ta phân chia 4 lớp tập thơ cơ bản sau đây: a) B (X )  và B (X ) U thì X là B-định nghĩa được thơ b) B (X )  và B (X ) U thì X là B-khơng định nghĩa được bên trong, c) B (X )  và B (X ) U thì X là B-định nghĩa được bên ngồi, d) B (X )  và B (X ) U thì X là B-khơng định nghĩa được hồn tồn Ý nghĩa trực quan của các lớp này như sau: - Nếu X là B-định nghĩa được thơ, cĩ nghĩa rằng cĩ thể xác định một số phần tử của U hoặc là thuộc vào X hoặc là thuộc vào –X khi sử dụng B. - Nếu X là B-khơng định nghĩa được bên trong, cĩ nghĩa rằng cĩ thể quyết định được một số phần tử của U thuộc vào –X nhưng khơng thể quyết định một phần tử nào đĩ của U cĩ thuộc vào X hay khơng khi sử dụng B. - Nếu X là B-khơng định nghĩa được bên ngồi, cĩ nghĩa là cĩ thể quyết định được một số phần tử của U thuộc vào X nhưng khơng thể quyết định được bất kỳ một phần tử nào của U cĩ thuộc vào –X hay khơng khi sử dụng B. - Nếu X là B-khơng định nghĩa được hồn tồn thì ta khơng thể quyết định được với mỗi phần tử của U cĩ thuộc vào X hoặc –X hay khơng khi sử dụng B. 7 Sinh viên: Trịnh Văn Dương – Lớp KHMT4K5
  8. Các tập thơ cũng cĩ thể được tính chất hĩa bằng hệ số sau đây: | B (X ) | (X ) B | B (X ) | Hệ số này được gọi là độ chính xác của xấp xỉ. Hiển nhiên, 0 B (X ) 1 . Nếu B (X ) 1 thì X là tập rõ theo B cịn nếu B (X ) 1 thì X là tập thơ theo B (X khơng rõ ràng theo B). Chúng ta mơ tả các định nghĩa ở trên bằng các ví dụ từ bảng 1 với khái niệm “bị bệnh cúm”, tập X={p1, p2,p3,p6} và tập các thuộc tính B = {đau đầu, đau cơ, nhiệt độ}. Khái niệm “bị bệnh cúm” là B-định nghĩa được thơ, vì B (X ) {p1, p3, p6}  và B (X ) {p1, p2, p3, p5, p6} U . Với trường hợp này, chúng ta nhận được B (“bị bệnh cúm”) =3/5. Cĩ nghĩa là khái niệm “bị bệnh cúm” chỉ được mơ tả bộ phận từ các triệu chứng: đau đầu, đau cơ và nhiệt độ. Chỉ xét một triệu chứng B= {đau đầu} chúng ta cĩ B (X )  , và B (X ) U , cĩ nghĩa rằng khái niệm “bị bệnh cúm” khơng định nghĩa được hồn tồn theo thuộc tính đau đầu. Tuy nhiên, khi lấy thuộc tính B = {nhiệt độ} chúng ta cĩ B (X ) {p3, p6} và B (X ) {p1, p2, p3, p5, p6} . Do đĩ, khái niệm “bị bệnh cúm” định nghĩa được một cách thơ. Trong trường hợp này ta nhận được B(X)= 2/5. Điều này cĩ nghĩa là triệu chứng nhiệt độ ít ảnh hưởng với bị bệnh cúm hơn tồn bộ các triệu chứng và bệnh nhân p1 khơng thể được phân lớp là bị cúm trong trường hợp này. 4. Các tập thơ và hàm thức Các tập thơ cĩ thể được định nghĩa bằng cách sử dụng một hàm thuộc thơ được xác định như sau: | X  B(x) |  B (x) . X | B(x) | 8 Sinh viên: Trịnh Văn Dương – Lớp KHMT4K5
  9. B Hiển nhiên:  X (x) [0,1] Giá trị của hàm thuộc X(x) là xác suất cĩ điều kiện và cĩ thể được hiểu như độ chắc chắn để x thuộc vào X. Hàm thuộc thơ cĩ thể được sử dụng để định nghĩa các xấp xỉ và vùng biên của một tập hợp như sau: B B (X ) {x U :  X (x) 1} , B B (X ) {x U :  X (x) 0} , B BNB (X ) {x U : 0  X (x) 1} Hàm thuộc thơ cĩ những tính chất sau đây: B a)  X (x) 1 iff x B* (X ) , B * b)  X (x) 0 iff x B (X ) , B c) 0  X (x) 1 iff x BNB (X ) , B d) Nếu I(B) {(x, x) : x U} , thì  X (x) là hàm đặc trưng của X, B B e) Nếu xI(B)y, thì  X (x) =  X (y) theo I(B), B B f) Mọi x U,,U X (x) 1  X (x) B B B g) Mọi x U,  X Y (x) max ( X (x),Y (x)) B B B h) Mọi x U,  X Y (x) min ( X (x),Y (x)) . Các tính chất trên cho thấy rõ ràng sự khác biệt giữa thành viên mờ và thơ. Trong các biểu thức g) và h) cho thấy các thành viên thơ chính thức cĩ thể được coi như là một sự tổng quát của các thành viên mờ. Chúng ta hãy nhớ lại rằng “ thơ thành viên”, trái ngược với “thành viên mờ” , cĩ tính chất xác suất. Nĩ cĩ thể được dễ dàng nhìn thấy rằng cĩ tồn tại một kết nối chặt chẽ giữa sự mơ hồ và khơng chắc chắn. Như chúng tơi đã đề cập ở trên khơng rõ ràng cĩ liên quan đến bộ( khái niệm), trong khi khơng chắc chắn liên quan đến các yếu tố của bộ. Cách tiếp cận tập thơ cho thấy kết nối rõ ràng giữa hai khái niệm này. 9 Sinh viên: Trịnh Văn Dương – Lớp KHMT4K5
  10. 5. CÁC BẢNG QUYẾT ĐỊNH VÀ THUẬT GIẢI QUYẾT ĐỊNH Trong một bảng thơng tin, ta phân biệt hai lớp các thuộc tính: các thuộc tính điều kiện và các thuộc tính quyết định. Ví dụ trong bảng 1 các thuộc tính: đau đầu, đau cơ và nhiệt độ cĩ thể được xem như các thuộc tính điều kiện, cịn thuộc tính bị cúm là thuộc tính quyết định. Mỗi hàng của một bảng quyết định xác định một luật quyết định, nĩ xác định các quyết định cĩ thể xảy ra khi các điều kiện được thỏa mãn. Ví dụ trong bảng 1 điệu kiện (đau đầu, khơng), (đau cơ, cĩ), (nhiệt độ, cao) xác định duy nhất quyết định (bị bệnh cúm,cĩ). Các đối tượng trong một bảng quyết định được sử dụng như là các nhãn của các luật quyết định. Các luật 2) và 5) trong bảng 1 cĩ cùng các điều kiện nhưng khác nhau ở các quyết định. Những luật như vậy được gọi là mâu thuẫn cịn trong trường hợp ngược lại thì các luật được gọi là nhất quán. Đơi khi các luật quyết định nhất quán cịn được gọi là các luật chắc chắn. Tỷ lệ các luật nhất quán trên tất cả các luật trong một bảng quyết định cĩ thể được xem như là hệ số nhất quán của bảng quyết định, và được ký hiệu bởi (C, D), trong đĩ C là các thuộc tính điều kiện và D là các thuộc tính quyết định. Do đĩ, nếu (C, D) =1 thì bảng quyết định là nhất quán và nếu (C, D) 1 thì bảng quyết định là khơng nhất quán. Ví dụ với bảng 1 chúng ta cĩ (C, D) = 4/6. Các luật quyết định thường được biểu diễn bằng các phép kéo theo theo dạng các luật “if then ”. Ví dụ luật 1) trong bảng 1 cĩ thể được biểu diễn như sau: If (Đau đầu, khơng) và (Đau cơ, cĩ) và (Nhiệt độ, cao) then (Bị bệnh cúm, cĩ). Một tập các luật quyết định được gọi là một thuật giải quyết định. Do đĩ, với mỗi bảng quyết định ta cĩ thể gắn với một thuật giải quyết định chứa tất cả các luật quyết định xuất hiện trong bảng quyết định đĩ. 10 Sinh viên: Trịnh Văn Dương – Lớp KHMT4K5
  11. Chúng ta cần phải phân biệt sự khác biệt giữa các bảng quyết định và các thuật giải quyết định. Một bảng quyết định là các dữ liệu trong khi một thuật giải quyết định là một tập các luật kéo theo, chẳng hạn các biểu thức logic. Để xử lý dữ liệu chúng ta sử dụng một số phương pháp thống kê tốn học. Nhưng để phân tích các luật kéo theo chúng ta cần phải sử dụng tới các cơng cụ logic. Do đĩ, hai phương pháp này là khơng tương đương. Tuy nhiên, để đơn giản chúng ta sẽ sử dụng các luật quyết định theo phép kéo theo chứ khơng đi sâu hơn về biểu diễn tự nhiên như đã thực hiện trong trí tuệ nhân tạo. 6. SỰ PHỤ THUỘC VÀO CÁC THUỘC TÍNH Một vấn đề quan trọng khác trong phân tích dữ liệu là khám phá sự phụ thuộc giữa các thuộc tính. Một cách trực giác, một tập các thuộc tính D phụ thuộc hồn tồn vào một tập các thuộc tính C, ký hiệu: C D, nếu tất cả các giá trị của các thuộc tính từ D được xác định một cách duy nhất bằng các giá trị của các thuộc tính của C. Nĩi cách khác, D phụ thuộc hồn tồn vào C nếu tồn tại một phụ thuộc hàm giữa các giá trị của D và C. Ví dụ trong bảng 1 khơng cĩ một sự phụ thuộc hồn tồn nào. Nhưng nếu giá trị của thuộc tính nhiệt độ của bệnh nhân p5 là “bình thường” thay cho “cao” thì cĩ một phụ thuộc hồn tồn {nhiệt độ} {bị bệnh cúm}, vì với mỗi giá trị của thuộc tính nhiệt độ cĩ một giá trị tương ứng duy nhất của thuộc tính bị bệnh cúm. Chúng ta mở rộng khái niệm tính độc lập các thuộc tính và gọi là tính độc lập bộ phận của các thuộc tính. Trong bảng 1 thuộc tính nhiệt độ xác định chỉ một số giá trị của thuộc tính bị bệnh cúm. Do đĩ (Nhiệt độ, rất cao) cĩ nghĩa là (Bị bệnh cúm, cĩ). Tương đương (Nhiệt độ, bình thường) cĩ nghĩa (bị bệnh cúm, khơng). Nhưng (nhiệt độ, cao) khơng phải lúc nào cũng cĩ nghĩa (bị bệnh cúm, cĩ). Do đĩ tính phụ thuộc bộ phận cĩ nghĩa là chỉ một số giá trị của D được xác định bởi các giá trị của C. Tính phụ thuộc tổng quát cĩ thể được định nghĩa như sau. 11 Sinh viên: Trịnh Văn Dương – Lớp KHMT4K5
  12. Định nghĩa 2: Giả sử D và C là các tập con của tập các thuộc tính A. D được gọi là phụ thuộc vào C với mức k, trong đĩ k = (C, D) và ký hiệu C kD. Nếu k =1 ta nĩi rằng D phụ thuộc hồn tồn vào C cịn nếu k < 1 thì D phụ thuộc bộ phận vào C (với mức k). Hệ số k biểu diễn tỷ lệ của tất cả các phần tử của tập tổng thể cĩ thể được phân lớp chính xác thành các khối của các phân hoạch U/D khi sử dụng các thuộc tính C. Do đĩ khái niệm tính độc lập của các thuộc tính được liên hệ với khái niệm tính nhất quán của bảng dữ liệu. Chẳng hạn với quan hệ {đau đầu, đau cơ, nhiệt độ} {bị bệnh cúm} ta nhận được k=4/6, vì bốn trong sáu bệnh nhân cĩ thể được phân lớp thành tập bị bệnh cúm khi sử dụng các thuộc tính đau đầu, đau cơ và nhiệt độ. Khi quan tâm tới việc đánh giá độ chính xác của các chuẩn đốn chỉ sử dụng một thuộc tính nhiệt độ thì mức phụ thuộc của {nhiệt độ} {bị bệnh cúm} là k =3/6, vì trong trường hợp này chỉ ba bệnh nhân p3, p4 và p6 trong sáu bệnh nhân cĩ thể được phân vào một lớp bị bệnh cúm. Đối lập với trường hợp trước bệnh nhân p4 khơng thể được phân lớp là bị bệnh cúm hay khơng. Do đĩ, thuộc tính đơn lẻ nhiệt độ thực hiện phân lớp tồi hơn tập tất cả các thuộc tính đau đầu, đau cơ và nhiệt độ. Một nhận xét thú vị là khơng phải đau đầu cũng khơng phải đau cơ cĩ thể được sử dụng để nhận ra bị bệnh cúm, vì cả hai phụ thuộc {Đau đầu} {Bị bệnh cúm} và {Đau cơ} {Bị bệnh cúm} đều cĩ k = 0. Cĩ thể dễ dàng thấy rằng nếu D phụ thuộc hồn tồn vào C thì I(C)  I(D). Cĩ nghĩa rằng phân hoạch sinh bởi C là mịn hơn phân hoạch sinh bởi D. Nếu D-phụ thuộc với mức k, 0 k 1 theo C, thì | POS (D) |  (C, D) C , |U | 12 Sinh viên: Trịnh Văn Dương – Lớp KHMT4K5
  13. Trong đĩ POSC (D) C (X ) X U / I (D) Biểu thức POSC(D), được gọi là một vùng chắc chắn của phân hoạch U/D với C. Đĩ là tập tất cả các phần tử của U cĩ thể được phân lớp duy nhất vào các khối của phân hoạch U/D bằng cách sử dụng các thuộc tính C. Tập thuộc tính D là phụ thuộc hồn tồn (bộ phận) vào tập các thuộc tính C nếu tất cả (một số) các phần tử của tập tổng thể U cĩ thể được phân lớp duy nhất vào các khối của phân hoạch U/D khi sử dụng các thuộc tính trong C. 7. THU GỌN CÁC THUỘC TÍNH Ta thường gặp câu hỏi: Cĩ thể xĩa bớt một số dữ liệu từ bảng dữ liệu mà vẫn giữ được các tính chất cơ bản của nĩ hay khơng? Hay nĩi một cách khác, liệu trong bảng cĩ chứa một số dữ liệu khơng cần thiết hay khơng? Dễ thấy rằng, nếu ta xĩa trong bảng 1 hoặc là thuộc tính đau đầu hoặc đau cơ thì sẽ nhận được tập dữ liệu là tương đương với tập ban đầu theo định nghĩa các xấp xỉ và các phụ thuộc. Dĩ đĩ, trong trường hợp này độ chính xác của các xấp xỉ và mức độ phụ thuộc giống như trong bảng trước đĩ nhưng với tập các thuộc tính nhỏ hơn. Để diễn đạt những ý tưởng trên rõ ràng hơn chúng tơi sử dụng một số khái niệm bổ trợ. Định nghĩa 3: Gỉa sử B  A và a B 1. a được gọi là cĩ thể bỏ được trong B nếu I(B)=I(B – {a}; ngược lại a là khơng thể bỏ được trong B. 2. Tập B là độc lập nếu tất cả các thuộc tính của nĩ là khơng thể bỏ được. 3. Tập con B' của B là một thu gọn của B nếu B' nếu là độc lập và I(B') = I(B). Do đĩ một thu gọn là một tập các thuộc tính bảo tồn phân hoạch. Cĩ nghĩa rằng một phân hoạch là một tập con nhỏ nhất các thuộc tính cĩ khả năng phân lớp các phần tử trong tập tổng thể giống như khi sử dụng tồn bộ tập các 13 Sinh viên: Trịnh Văn Dương – Lớp KHMT4K5
  14. thuộc tính. Nĩi cách khác, các thuộc tính khơng thuộc vào một thu gọn là các thuộc tính dư thừa khi phân lớp các phần tử của tập tổng thể. Các thu gọn cĩ một số tính chất quan trọng. Dưới đây chúng tơi trình bày hai tính chất trong số đĩ. Trước hết chúng ta định nghĩa khái niệm về hạt nhân của các thuộc tính. Với B  A Hạt nhân của B là tập của tất cả các thuộc tính khơng thể bỏ được của B. Mối liên hệ giữa khái niệm hạt nhân và các thu gọn như sau: CORE x (B) Red x (B) , trong đĩ Red(B) là một thu gọn của B: Vì hạt nhân là giao của tất cả các thu gọn nên nĩ là tập con trong mỗi thu gọn, hay mỗi phần tử của hạt nhân thuộc vào các thu gọn. Do đĩ, hạt nhân là tập con quan trọng nhất của các thuộc tính, khơng một phần tử nào của nĩ cĩ thể bỏ đi mà khơng ảnh hưởng tới phân lớp tập tổng thể. Trong một bảng thơng tin ta cĩ thể loại bỏ một số thuộc tính của bảng theo một phương pháp nào đĩ mà vẫn cĩ thể phân biệt được các đối tượng trong bảng như khi cĩ tất cả các thuộc tính ban đầu. Để thực hiện điều này chúng ta cĩ thể áp dụng một thủ tục tương tự như khi loại bỏ các thuộc tính khơng cần thết được định nghĩa như sau: 1) Ta nĩi rằng giá trị của thuộc tính a B là cĩ thể bỏ được với x nếu [x]I(B) = [x]I(B –{A}) , ngược lại thì giá trị của thuộc tính a là khơng thể bỏ được vơi x. 2) Nếu mọi thuộc tính a B, giá trị của a là khơng thể bỏ được với x thì B sẽ được gọi là trực giao với x. 3) Tập con B'  B là một giá trị thu gọn của B theo x, nếu và chỉ nếu B' là trực giao với x và [x]I(B) = [x]I(B’) Tập tất cả các giá trị khơng thể bỏ được của các thuộc tính trong B theo x sẽ được gọi là hạt nhân của B theo x, và được ký hiệu là COREx(B). 14 Sinh viên: Trịnh Văn Dương – Lớp KHMT4K5
  15. Trong trường hợp này chúng ta cũng cĩ: CORE x (B) Red x (B) Trong đĩ Redx(B) là họ tất cả các thu gọn của B theo x. Giả sử cĩ một phụ thuộc C D. Cĩ thể tập D khơng phụ thuộc hồn tồn vào C mà chỉ phụ thuộc vào tập con C' của C. Do vậy, chúng ta cần phải tìm tập con này. Để giải quyết bài tốn này chúng ta sử dụng khái niệm thu gọn liên quan được định nghĩa như sau: Định nghĩa 4: Gỉa sử C,D  A. 1. Tập C'  C là một D-thu gọn của C nếu C' là một tập con nhỏ nhất của C thỏa mãn:  (C, D)  (C , D) . 2. Thuộc tính a C là D-cĩ thể bỏ được trong C, nếu POSC(D) = POS(C {a})(D), ngược lại thì thuộc tính a là D-khơng thể bỏ được trong C. 3. Nếu tất cả các thuộc tính a C là D-khơng thể bỏ được trong C, thì C được gọi là D-khơng thể bỏ được. 4. Tập con C'  C là một D-rút gọn của C, nếu và chỉ nếu C' là D-độc lập và POSC(D) = POSC'(D). Tập tất cả các thuộc tính D-khơng thể bỏ được trong C được gọi là D-hạt nhân của C, và được ký hiệu bởi CORE D(C). Trong trường hợp này chúng ta cũng cĩ: CORED (C) RedD (C) trong đĩ RedD(C) là họ tất cả các D-rút gọn của C. Ví dụ trong bảng 1 cĩ hai thu gọn liên quan với bị bệnh cúm là {đau đầu, nhiệt độ} và {đau cơ, nhiệt độ} của tập các thuộc tính điều kiện {đau đầu, đau 15 Sinh viên: Trịnh Văn Dương – Lớp KHMT4K5
  16. cơ, nhiệt độ}. Cĩ nghĩa rằng hoặc là thuộc tính đau đầu hoặc đau cơ cĩ thể bỏ khỏi bảng và thay cho sử dụng bảng 1 chúng ta sử dụng bảng 2 dưới đây. Bệnh nhân Đau Nhiệt độ Bị bệnh đầu cúm p1 khơng cao cĩ p2 cĩ cao cĩ p3 cĩ rất cao cĩ p4 khơng bình khơng thường p5 cĩ cao khơng p6 khơng rất cao cĩ Bảng 2 Hoặc bảng 3 Bệnh nhân Đau cơ Nhiệt độ Bị bệnh cúm p1 cĩ cao cĩ p2 khơng cao cĩ p3 cĩ rất cao cĩ p4 cĩ bình thường khơng p5 khơng cao khơng p6 cĩ rất cao cĩ Bảng 3 16 Sinh viên: Trịnh Văn Dương – Lớp KHMT4K5
  17. Với bảng 1 hạt nhân liên quan với tập {đau đầu, đau cơ, nhiệt độ} là nhiệt độ. Điều này khẳng định lại nhận định trước đây chúng tơi đã chỉ ra rằng nhiệt độ chỉ là triệu chứng chẩn đốn bộ phận về các bệnh nhân. Chúng tơi sử dụng khái niệm giá trị thu gọn và giá trị hạt nhân. Giả sử cĩ một phụ thuộc C D trong đĩ C là D-thu gọn của C. Ta sẽ tìm hiểu một cách chính xác các giá trị của các thuộc tính trong D phụ thuộc như thế nào tới các giá trị của các thuộc tính trong C. Ta nĩi rằng giá trị của thuộc tính a B là D-cĩ thể bỏ được đối với x U, nếu: [x]I(C)  [x]I(D) [x]I(C {a})  [x]I(D); cịn nếu ngược lại thì giá trị của thuộc tính a là D-khơng thể bỏ được của x. Nếu với mỗi thuộc tính a C, giá trị của a là D-khơng thể bỏ được đối với x, thì C được gọi D-độc lập với x. Tập con C’  C là một D-thu gọn của C với x nếu và chỉ nếu C’ là D-độc lập với x và: [x]I(C)  [x]I(D) [x]I(C')  [x]I(D). Tập tất cả các giá trị D-khơng thể bỏ được của x của các thuộc tính trong x C được gọi là D-hạt nhân của C với x và được ký hiệu là CORED (C) . x x x Ta cũng cĩ tính chất: CORED (C) RedD (C) , trong đĩ RedD (C) là họ tất cả các D-thu gọn C với x. Sử dụng khái niệm của một giá trị thu gọn, bảng 2 và bảng 3 cĩ thể được đơn giản hĩa như sau: Bệnh Đau đầu Nhiệt độ Bị bệnh cúm nhân p1 khơng cao cĩ 17 Sinh viên: Trịnh Văn Dương – Lớp KHMT4K5
  18. p2 cĩ cao cĩ p3 rất cao cĩ p4 bình khơng thường p5 cĩ cao khơng p6 rất cao cĩ Bảng 4 Bệnh nhân Đau cơ Nhiệt độ Bị bệnh cúm p1 cĩ cao cĩ p2 khơng cao cĩ p3 rất cao cĩ p4 bình thường khơng p5 khơng cao khơng p6 rất cao cĩ Bảng 5 Ta cũng cĩ thể biểu diễn các kết quả nhận được dưới dạng thuật giải quyết định. Với bảng 4 ta nhận được: if (Đau đầu, khơng) and (Nhiệt độ, cao) then (Bị bệnh cúm, cĩ), if (Đau đầu, cĩ) and (Nhiệt độ, cao) then (Bị bệnh cúm, cĩ), if (Nhiệt độ, rất cao) then (Bị bệnh cúm, cĩ), if (Nhiệt độ, bình thường) then (Bị bệnh cúm, khơng), if (Đau đầu, cĩ) and (Nhiệt độ, cao) then (Bị bệnh cúm, khơng), 18 Sinh viên: Trịnh Văn Dương – Lớp KHMT4K5
  19. if (Nhiệt độ, rất cao) then (Bị bệnh cúm, cĩ) , Và với bảng 5 ta nhận được: if (Đau cơ, cĩ) and (Nhiệt độ, cao) then (Bị bệnh cúm, cĩ) , if (Đau cơ, khơng) and (Nhiệt độ, cao) then (Bị bệnh cúm, cĩ), if (Nhiệt độ, rất cao) then (Bị bệnh cúm, cĩ), if (Nhiệt độ, bình thường) then (Bị bệnh cúm, khơng), if (Đau cơ, khơng) and (Nhiệt độ, cao) then (Bị bệnh cúm, khơng), if (Nhiệt độ, rất cao) then (Bị bệnh cúm, cĩ). Dưới đây là một số tính chất quan trọng của thu gọn: a)B' B B', trong đĩ B' là một thu gọn của B. b) Nếu B C, thì B C', với mỗi C'  C, c) Nếu B C, thì B {a}, với mỗi a C. d) Nếu B' là một thu gọn của B thì hoặc {a} {b} hoặc {b} {a} với mỗi a,b B', tất cả các thuộc tính trong một thu gọn độc lập từng đơi một. 8. CÁC HÀM VÀ MA TRẬN PHÂN BIỆT Để tính các thu gọn và hạt nhân một cách dễ dàng chúng ta sử dụng ma trận phân biệt được định nghĩa trong [4] như sau: Ma trận phân biệt của B  A ký hiệu M(B) là một ma trận vuơng cấp n trong đĩ : (cij ) {a B : (xi ) a(x j )} với i, j 1,2,,n . Khi đĩ các phần tử c ij là tập tất cả các thuộc tính phân biệt của các đối tượng xi và xj. Ma trận phân biệt M(B) gắn mỗi cặp đối tượng x và y với một tập con các thuộc tính  (x, y)  B , cĩ các tính chất sau đây: 19 Sinh viên: Trịnh Văn Dương – Lớp KHMT4K5
  20. 1)  (x, x) = , 2)  (x, y) =  (y, x), 3)  (x, z)   (x, y)   (y, z). Những tính chất này giống với những tính chất của nửa khoảng cách, do đĩ ma trận phân biệt cĩ thể được xem như một ma trận nửa khoảng cách. Với mọi x, y, z U ta cĩ : 4) | (x, x)| = 0, 5) | (x, y)| = | (y, x)|, 6) | (x, z)| | (x, y)| + | (y, z)|. Dễ dàng thấy rằng hạt nhân là tập tất cả các phần tử của ma trận phân biệt M(B): CORE)B) {a B : cij {a}, mọi i, j} Ta cĩ B  B là một thu gọn của B, nếu B' là tập con nhỏ nhất của B thỏa mãn: B  c  với bất kỳ một phần tử c(c ) trong M(B). Nĩi cách khác thu gọn là tập con nhỏ nhất các thuộc tính phân biệt được tất cả các đối tượng bằng tập tồn bộ các thuộc tính. Mỗi ma trận phân biệt M(B) xác định duy nhất một hàm phân biệt f(B) được định nghĩa như sau: Gán cho mỗi thuộc tính a B mỗi biến logic a, và đặt  (x, y) là tổng thể logic của tất cả các biến logic gắn với tập thuộc tính (x, y) . Hàm phân biệt được định nghĩa bằng cơng thức: f (B) { (x, y) : (x, y) U 2 &  (x, y) } . (x, y) U 2 20 Sinh viên: Trịnh Văn Dương – Lớp KHMT4K5
  21. Tính chất sau đây thiết lập mối quan hệ giữa hàm f(B) và tập tất cả các thu gọn của B. Định lý 5: Tập tất cả các phần tử trong dạng chuẩn tắc nhỏ nhất của hàm f(B) chính là tập tất cả các thu gọn của B. Chứng minh: Thật vậy,với mỗi phần tử trong dạng chuẩn tắc nhỏ nhất của hàm f(B sẽ là tập các phần tử khơng thể bỏ được trong B, do đĩ nĩ là một thu gọn của B và ngược lại. Để tính giá trị hạt nhân và giá trị thu gọn của x chúng ta cĩ thể sử dụng ma trận phân biệt như định nghĩa trước đây và hàm phân biệt được sửa đổi như sau: f x (B) { (x, y) : y U và  (x, y) } . y U Các thu gọn và hạt nhân cũng được tính bằng cách sử dụng ma trận phân biệt với một thay đổi như sau: cij {a C : a(xi ) a(x j ) &,w(xi , x j )} Trong đĩ w(xi , x j  xi POSC (D) & x j POSC (D) hoặc xi POSC (D) & x j POSC (D) hoặc xi , x j POSC (D) & (x j , x j ) I(D) Với i, j 1,2,,n . Nếu phân hoạch được định nghĩa bằng D là định nghĩa được bằng C thì điều kiện w(xi , x j ) trong định nghĩa trên cĩ thể được biến đổi thành(xi , x j ) I(D) . Do đĩ phần tử c ij là tập tất cả các thuộc tính phân biệt các đối tượng x i và xj khơng thuộc vào cùng một lớp tương đương của quan hệ I(D). D-hạt nhân là tập tất cả các phần tử đơn của ma trận phân biệt MD(C). CORED (C) {a C : cij (a), voi i, j}. 21 Sinh viên: Trịnh Văn Dương – Lớp KHMT4K5
  22. Tập C  C là D-thu gọn của C, nếu C' C là tập con nhỏ nhất của C thỏa mãn C  c  Với bất kỳ thực thể khác rỗng c(c ) trong M D (C) Do đĩ D-thu gọn là tập con nhỏ nhất các thuộc tính phân biệt tất cả các lớp tương đương của quan hệ I(D). Mỗi ma trận phân biệt M D(C) xác định duy nhất một hàm phân biệt f D(C) được định nghĩa như trước đây. Chúng ta cũng cĩ tính chất sau đây: Định lý 6: Tập tất cả các phần tử trong dạng phân biệt chuẩn tắc của hàm f D(C) chính là tập tất cả các D-thu gọn của C. Chứng minh: Thật vậy với mỗi phần tử trong dạng chuẩn tắc phân biệt của hàm fD(C) cĩ tương ứng một ma trận phân biệt M D(C). Nĩ bao gồm tập con nhỏ nhất các thuộc tính phân biệt tất cả các lớp tương đương của quan hệ I(D), do đĩ nĩ là D-thu gọn của C. Để tính gá trị các thu gọn và giá trị hạt nhân cho các thu gọn liên quan, đầu tiên chúng tối sử dụng ma trận phân biệt MD(C) và hàm phân biệt sẽ cĩ dạng: x f D (C) { (x, y) : y U và  (x, y) } y U Chúng tơi minh họa các định nghĩa trên bằng cách tính các thu gọn liên quan với tập các thuộc tính {Nhức đầu, đau cơ,nhiệt độ} với bị cúm (Bị bệnh cúm) Ma trận phân biệt tương ứng được cho trong bảng 6 dưới đây: 1 2 3 4 5 6 1 2 3 22 Sinh viên: Trịnh Văn Dương – Lớp KHMT4K5
  23. 4 T H, M, T 5 H, M M, T 6 T H, M, T Bảng 6 Trong bảng H, M, T tương ứng là ký hiệu Đau đầu, Đau cơ và Nhiệt độ. Hàm phân biệt cho bảng trên là: T (H M )(H M T )(M T ) , Trong đĩ ký hiệu + là tổng logic cịn phép nhân logic khơng cần ký hiệu trong cơng thức. Sử dụng các luật của đại số logic chúng ta cĩ biểu thức sau: TH + TM Điều này chỉ ra rằng cĩ hai thu gọn TH và TM trong bảng dữ liệu và T là hạt nhân. 9. ĐỘ QUAN TRỌNG CỦA CÁC THUỘC TÍNH VÀ CÁC THU GỌN XẤP XỈ Như đã trình bày trong phần thu gọn thuộc tính, các thuộc tính cĩ “mức độ quan trọng” khơng như nhau. Một số trong chúng cĩ thể bị loại bỏ khỏi một bảng thơng tin mà khơng gây mất thơng tin cĩ trong bảng. Ý tưởng thu gọn các thuộc tính cĩ thể được tổng quát hĩa bằng cách giới thiệu khái niệm độ quan trọng của các thuộc tính. Nĩ cho phép chúng ta đánh giá các thuộc tính khơng chỉ bằng cặp giá trị cĩ thể bỏ được - khơng thể bỏ được, mà bằng cách gán cho mỗi thuộc tính một giá trị thực đoạn [0,1] để biểu diễn mức độ quan trọng của một thuộc tính trong bảng thơng tin này. 23 Sinh viên: Trịnh Văn Dương – Lớp KHMT4K5
  24. Độ quan trọng của một thuộc tính cĩ thể được đánh giá bằng cách đo mức độ ảnh hưởng của việc bỏ đi một thuộc tính từ một bảng thơng tin. Chúng ta bắt đầu với các bảng quyết định. Gọi C là tập các thuộc tính quyết định, D là tập các thuộc tính điều kiện và a là một thuộc tính điều kiện a C. Giá trị (C, D) biểu diễn độ nhất quán của bảng quyết định, hay cịn gọi là độ phụ thuộc giữa các thuộc tính C và D. Giá trị này cũng thể hiện độ chính xác của xấp xỉ U/D bởi C. Ta cĩ thể đặt câu hỏi: Hệ số (C, D) thay đổi như thế nào khi bỏ đi thuộc tính a? Hay sự khác nhau giữa (C, D) và (C - {a}, D) là gì ? Chúng ta cĩ thể tổng quát hĩa sự khác biệt và định nghĩa độ quan trọng của thuộc tính a như sau: ( (C, D)  (C {a}, D))  (C {a}, D)  (a) 1 , (C,D)  (C, D)  (C, D) và ký hiệu ngắn gọn là (a) , khi C và D đã biết. Ta cĩ 0  (a) 1 . Mức độ quan trọng của thuộc tính a càng cao thì số  (a) càng lớn. Ví dụ với các thuộc tính điều kiện trong bảng 1 chúng ta cĩ các kết quả sau:  (Đau đầu) = 0,  (Đau cơ) = 0,  (Nhiệt độ) = 0.75. Vì độ quan trọng của thuộc tính Nhiệt độ hoặc Đau cơ là 0 nên việc bỏ đi một trong số các thuộc tính từ các thuộc tính điều kiện khơng ảnh hưởng tới tập các luật nhất quán. Do đĩ thuộc tính Nhiệt độ là thuộc tính quan trọng nhất bảng. Điều đĩ cĩ nghĩa rằng bằng cách bỏ đi thuộc tính Nhiệt độ, 75% của các luật quyết định nhất quán sẽ biến mất khỏi bảng, nên tình trạng thiếu thuộc tính ảnh hưởng cơ bản tới “khả năng quyết định” của bảng quyết định. 24 Sinh viên: Trịnh Văn Dương – Lớp KHMT4K5
  25. Với một thu gọn của các thuộc tính điều kiện, chẳng hạn {Đau đầu, Nhiệt độ}, chúng ta nhận được:  (Đau đầu) = 0.25,  (Nhiệt độ) = 1.00. Trong trường hợp này việc bỏ đi thuộc tính Đau đầu từ thu gọn, chẳng hạn sử dụng chỉ thuộc tính Nhiệt độ thì 25% các luật quyết định nhất quán sẽ bị mất. Cịn nếu bỏ thuộc tính Nhiệt độ mà chỉ sử dụng thuộc tính Đau đầu thì 100% các luật quyết định nhất quán sẽ bị mất. Điều đĩ cĩ nghĩa rằng trong trường hợp này việc ra các quyết định là khơng thực hiện được. Nếu sử dụng chỉ thuộc tính Nhiệt độ thì một số quyết định cĩ thể thực hiện. Do đĩ, hệ số  (a) được hiểu như một lỗi xuất hiện khi thuộc tính a bị bỏ đi. Hệ số độ quan trọng cĩ thể mở rộng cho tập các thuộc tính như sau: ( (C, D)  (C B, D))  (C B, D)  (B) 1 (C,D)  (C, D)  (C, D) và ký hiệu  (B), nếu C và D đã biết, trong đĩ B là một tập con của C. Nếu B là một thu gọn của C, thì  (B) = 1, do đĩ việc bỏ đi bất kỳ thu gọn nào từ một tập của các luật quyết định cho phép tạo ra các quyết định chắc chắn. Một tập con B nào đĩ của C được gọi là một thu gọn xấp xỉ của C, và số: ( (C, D)  (B, D))  (B, D)  (B) 1 (C,D)  (C, D)  (C, D) ký hiệu (B), được gọi là lỗi của các xấp xỉ thu gọn. Nếu biểu diễn độ chính xác tập các thuộc tính B xấp xỉ tập các thuộc tính điều kiện C. Ta cĩ  (B) = 1  (B) và  (B) = 1  (C B). Với tập con B nào đĩ của C,chúng ta cĩ  (B)  (C). Nếu B là thu gọn của C, thì  (B) = 0. 25 Sinh viên: Trịnh Văn Dương – Lớp KHMT4K5
  26. Ví dụ một trong các thuộc tính Đau đầu và Nhiệt độ cĩ thể được coi như một thu gọn xấp xỉ của {Đau đầu, Nhiệt độ} và :  (Đau đầu) = 1,  (Nhiệt độ) = 0.25. Nhưng với tồn bộ tập các thuộc tính điều kiện {Đau đầu, Đau cơ, Nhiệt độ} chúng ta cũng cĩ thu gọn xấp xỉ sau đây:  (Đau đầu, Đau cơ) = 0.75. Tập con nhỏ nhất B của các thuộc tính điều kiện C thỏa mãn  (C, D)  (B, D) , hoặc (C,D) (B) 0 là một thu gọn. Ý tưởng của một thu gọn xấp xỉ cĩ thể rất hữu dụng trong trường hợp số các thuộc tính điều kiện ít lại được ưu tiên hơn theo độ chính xác của phân lớp. 10. KẾT LUẬN Như vậy từ một bảng dữ liệu chúng ta cĩ thể tính tốn độ quan trọng của các thuộc tính và tìm được các thu gọn xấp xỉ cũng như tìm được các thuộc tính khơng bỏ được sử dụng lý thuyết tập thơ. Điều này cho phép chúng ta dễ dàng hơn trong việc lập luận với dữ liệu vì số lượng các thuộc tính hay phạm vi của bài tốn đã được thu hẹp lại. Lý thuyết tập thơ cĩ rất nhiều ứng dụng trong phân tích dữ liệu y học, tài chính, nhận dạng giọng nĩi, xử lý ảnh và một số lĩnh vực khác. Phương pháp được trình bày trong bài báo là đơn giản hơn so với nhiều ứng dụng trong thực tế và đã được mở rộng theo nhiều hướng khác nhau. Những thảo luận chi tiết về những vấn đề trên cĩ thể thấy trong các tài liệu [5,6]. Ở đây chúng tơi chỉ đưa ra những ý tưởng cơ bản để lập luận với các hạt dữ liệu khi sử dụng lý thuyết các tập thơ. 26 Sinh viên: Trịnh Văn Dương – Lớp KHMT4K5
  27. TÀI LIỆU THAM KHẢO [1] Z. Pawlak: Rough sets, International Journal of Computer and Information Sciences, 11, 341-356, 1982 [2] Z. Pawlak: Rough Sets Theoretical Aspects of Reasoning about Data, Kluwer Academic Publishers, Boston, London, Dordrecht, 1991 [3] Z. Pawlak, A. Skowron: Rough membership functions, in: R. R Yaeger, M. Fedrizzi and J. Kacprzyk (eds.), Advances in the Dempster Shafer Theory of Evidence, John Wiley & Sons, Inc., New York, Chichester, Brisbane, Toronto, Singapore, 1994, 251-271 [4] A. Skowron, C. Rauszer: The discernibility matrices and functions in information systems, in: R. Słowiński (ed.), Intelligent Decision Support. Handbook of Applications and Advances of the Rough Set Theory, Kluwer Academic Publishers, Dordrecht, 1992, 311-362 [5] A. Skowron et al: Rough set perspective on data and konwedge, Handbook of Data Mining and Knoledge Discovery (W. Klưsgen, J. Żytkow eds.), Oxford University Press, 2002, 134-149 [6] L. Polkowski: Rough Sets Mathematical Foundations, Advances in Soft Computing, Physica-Verlag, Springer-Verlag Company, 2002, 1-534 27 Sinh viên: Trịnh Văn Dương – Lớp KHMT4K5