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

Chia sẻ: Phi Ngoc Man | Ngày: | Loại File: DOC | Số trang:27

Thêm vào BST

Báo xấu

110
lượt xem 24
download

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

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...

Chủ đề:

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

Lưu

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

ĐỀ 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
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
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 b iệ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 n hấ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 b iê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
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. Đau đầu Nhiệt độ Bệnh Đaucơ Bị bệnh cúm nhân (Muscle- (Flu) (Headache) (Temperature) (Patient) pain) p1 không có cao có p2 có không cao có rất cao p3 có có có bình thường p4 không có không p5 có không cao không rất cao p6 không có 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
Trong bảng 1 các bệnh nhân p 2, 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 h ai 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
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 Va là tập tất cả các g iá 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 b iệ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 BN B ( 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
4) B ( X  Y )  B ( X )  B (Y ) , 5) X  Y  B ( X )  B (Y ) và 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 ngoài, d) B ( X )   và B  ( X )  U thì X là B-không định nghĩa được hoàn toà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 h ay không khi sử dụng B. - Nếu X là B-không định nghĩa được bên ngoà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 hoàn toà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 h ay không khi sử dụng B. 7 Sinh viên: Trịnh Văn Dương – Lớp KHMT4K5
Các tập thô cũng có thể được tính chất hóa bằng hệ số sau đây: | B ( X ) | B ( X )  | 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 n iệ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, p 2, 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ó n ghĩa rằng khái niệm “b ị bệnh cúm” không đ ịnh nghĩa được hoàn toà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, p 2, p3, p5, p 6} . 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 toà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 THUỘ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
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 ( X )  {x  U :  X ( x)  0} , B B BN B ( 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)  X ( x )  0 iff x   B* ( X ) , B B c) 0   X ( x)  1 iff x  BN B ( 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) , g) Mọi xU,  X Y ( x)  max (  X ( x), YB ( x)) B B h) Mọi xU,  X Y ( x)  min (  X ( x), YB ( x)) . B B 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
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 n gượ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
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ê toá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 hoàn toà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 hoàn toà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 hoàn toà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 ho àn toà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
Đị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 hoàn toà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 b iể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 n iệ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 đoá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 hoàn toà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ì | POSC ( D) | ,  (C , D)  |U | 12 Sinh viên: Trịnh Văn Dương – Lớp KHMT4K5
C ( X ) Trong đó POS C ( D)   X U / I ( D ) Biểu thức POS C(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 hoàn toà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 n iệ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 toàn phân hoạch. Có n ghĩ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 to àn bộ tập các 13 Sinh viên: Trịnh Văn Dương – Lớp KHMT4K5
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 h ai 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
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 hoàn toà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 toá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 CORED(C). Trong trường hợp n ày chúng ta cũng có: CORED (C )   Red D (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
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 Nhiệt độ Đau Bị bệnh đầu cúm p1 không cao có p2 có cao có rất cao p3 có có p4 không không bình thường p5 có cao không rất cao p6 không 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ó rất cao p3 có có bình thường p4 có không p5 không cao không rất cao p6 có có Bảng 3 16 Sinh viên: Trịnh Văn Dương – Lớp KHMT4K5
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 đoá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 ) . Ta cũng có tính chất: CORED (C )   RedD (C ) , trong đó Red D (C ) là họ tất x x x 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: Đau đầu Nhiệt độ Bị bệnh cúm Bệnh nhân p1 không cao có 17 Sinh viên: Trịnh Văn Dương – Lớp KHMT4K5
p2 có cao có rất cao p3 có  p4 không b ình  thường p5 có cao không rất cao p6 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ó rất cao p3 có  b ình thường p4 không  p5 không cao không rất cao p6 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
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ử cij 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
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 toà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 b iế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: 2 { ( x, y) : ( x, y) U &  ( x, y )  } . f ( B)  ( x , y )U 2 20 Sinh viên: Trịnh Văn Dương – Lớp KHMT4K5