Luận văn Một số phương pháp rút gọn thuộc tính trong bảng quyết định

ề 1.9. [13] (Cực trị cho α ) Cho bảng quyết ñịnh ( ),DS U C D= ∪ và ( ) ( ){ }| : , / , / , 1.. , 1..ij ij i j i jRULE Z Z des X des Y X U C Y U D i m j n= → ∈ ∈ = = . Khi ñó ta có • Với mọi ijZ RULE∈ , nếu ( ) 1ijZµ = thì ( )DSα ñạt giá trị lớn nhất là 1. • Nếu 1m = và n U= thì ( )DSα ñạt giá trị nhỏ nhất là 1 U Mệnh ñề 1.10. Cho bảng quyết ñịnh ( ),DS U C D= ∪ và ( )' ,DS U B D= ∪ . Nếu B C⊆ thì ( ) ( )'DS DSα α≤ . Chứng minh Giả sử { }1 2/ , ,..., nU D D D D= . Từ giả thiết B C⊆ ta có / /U C U B≤ , nghĩa là mỗi khối /U B sẽ là tập hợp của một số khối thuộc /U C . Không mất tính chất tổng quát, chỉ cần chứng minh mệnh ñề trong trường hợp các khối của /U B trùng với các khối của /U C , ngoại trừ chỉ một khối của /U B là hợp của hai khối trong /U C , nghĩa là { }1 2/ , ,..., mU C X X X= và { }1 2 1 1 1 1/ , ,..., , ,..., , ,..., ,u u v v m u vU B X X X X X X X X X− + − += ∪ . Thật vậy ta có: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 26 ( ) ( ) 2 2 2 ' 1, , 1 1 1 m n n n i j u j v j i i u i v j j ji u v X D X D X D DS DS U X U X U X α α = ≠ ≠ = = = ∩ ∩ ∩ − = + +∑ ∑ ∑ ∑ ( )2 2 1, , 1 1 m n n i j u v j i i u i v j ji u v X D X X D U X U X X = ≠ ≠ = = ∩ ∪ ∩ − − ∪ ∑ ∑ ∑ ( ) ( ) 22 2 1 1 1 n n n u j v ju j v j j j ju v u v X D X DX D X D U X U X U X X = = = ∩ + ∩∩ ∩ = + − + ∑ ∑ ∑ ( )22 2 1 1 n u j v ju j v j j u v u v X D X DX D X D U X X X X =  ∩ + ∩∩ ∩  = + −  +    ∑ ( ) ( ) ( ) ( ) 2 2 2 1 1 n u v u j v j u j v u v v j u u v j u v u v X X X D X D X D X X X X D X X X U X X X X =  ∩ + ∩ − ∩ + − ∩ +  =  +    ∑ ( ) 2 22 2 1 21 n u j v u j v j u v v j u j u v u v X D X X D X D X X X D X U X X X X =  ∩ − ∩ ∩ + ∩  =  +   ∑ ( ) ( ) 2 1 1 0 n u j v v j u j u v u v X D X X D X U X X X X = ∩ − ∩ = ≥ + ∑ Do ñó ( ) ( )'DS DSα α≤ . Dấu ñẳng thức ( ) ( )'DS DSα α= xảy ra khi và chỉ khi 0 u j v ju j v v j u u j v v j u u v X D X D X D X X D X X D X X D X X X ∩ ∩ ∩ − ∩ = ⇔ ∩ = ∩ ⇔ = Từ ñó kết luận dấu ñẳng thức ( ) ( )'DS DSα α= xảy ra khi và chỉ khi với mọi , / ,u v u vX X U C X X∈ ≠ , nếu w /u vX X Y U B∪ ⊆ ∈ thì u j v j u v X D X D X X ∩ ∩ = với mọi 1, 2,...,j n= . Từ ñiều kiện dấu ñẳng thức của Mệnh ñề 1.6 ta suy ra ( ) ( )'DS DSα α= khi và chỉ khi ( ) ( )| |H D B H D C= . ðịnh nghĩa 1.19. Cho bảng quyết ñịnh ( , , , )DS U C D V f= ∪ và ( ) ( ){ }| : , / , / , 1.. , 1..ij ij i j i jRULE Z Z des X des Y X U C Y U D i m j n= → ∈ ∈ = = , ñộ nhất quán cải tiến gβ của DS ñược ñịnh nghĩa: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 27 ( ) 2 1 1 1 1 1 m n i j i j i X Yng DS n U X n β = = ∩ = − − − ∑∑ . Mệnh ñề 1.11. (Cực trị cho gα ) Cho bảng quyết ñịnh ( ),DS U C D= ∪ và ( ) ( ){ }| : , / , / , 1.. , 1..ij ij i j i jRULE Z Z des X des Y X U C Y U D i m j n= → ∈ ∈ = = . Khi ñó ta có • Với mọi ijZ RULE∈ , nếu ( ) 1ijZµ = thì ( )g DSβ ñạt giá trị lớn nhất là 1. • Nếu 1m = và n U= thì ( )g DSβ ñạt giá trị nhỏ nhất là 0 Chứng minh Theo ðịnh nghĩa 1.19 ta có ( ) ( ) 1 1 1 ng DS DS n n β α= − − − . Do ñó, ( )g DSβ ñạt giá trị lớn nhất là ( ) 1 1 1 1 ng DS n n β = − = − − khi ( )DSα ñạt giá trị lớn nhất là 1. ( )g DSβ ñạt giá trị nhỏ nhất là ( ) 1 1* 0 1 1 ng DS n n n β = − = − − khi ( )DSα ñạt giá trị nhỏ nhất là 1 n . Mệnh ñề 1.12. Cho hai bảng quyết ñịnh ( ),DS U C D= ∪ và ( )' ,DS U B D= ∪ . Nếu B C⊆ thì ( ) ( )'g DS g DSβ β≤ . Chứng minh Từ B C⊆ , theo Mệnh ñề 1.15 ta có ( ) ( ) ( ) ( ) ( ) ( )' ' '1 11 1 1 1 n nDS DS DS DS g DS g DS n n n n α α α α β β≤ ⇔ − ≤ − ⇔ ≤ − − − − Dấu ñẳng thức ( ) ( )'g DS g DSβ β= xảy ra khi và chỉ khi ( ) ( )'DS DSα α= , nghĩa là với mọi , / ,u v u vX X U C X X∈ ≠ , nếu w /u vX X Y U B∪ ⊆ ∈ thì u j v j u v X D X D X X ∩ ∩ = với mọi 1, 2,...,j n= . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 28 Từ ñiều kiện dấu ñẳng thức của Mệnh ñề 1.15 ta suy ra ( ) ( )'g DS g DSβ β= khi và chỉ khi ( ) ( )| |H D B H D C= . Nhận xét 1.2. - Theo tác giả Nguyễn ðức Thuần [1], ñộ nhất quán của hai bảng quyết ñịnh bằng nhau khi và chỉ khi 0c u j v jX D X D∩ ∩ = (Bổ ñề 3.1) và xảy ra khi cả hai bảng quyết ñịnh nhất quán (Bổ ñề 3.2). Tuy nhiên, với các bảng quyết ñịnh không nhất quán, không ñánh giá ñược ñiều kiện bằng nhau của ñộ ño này. Từ Mệnh ñề 1.12, ñiều kiện bằng nhau của ñộ nhất quán nghiên cứu thỏa mãn với cả bảng nhất quán và không nhất quán. Hơn nữa, ñiều kiện tìm hiểu ở trên chặt hơn ñiều kiện của Nguyễn ðức Thuần. - Mệnh ñề 1.12 cho thấy ñộ nhất quán tỷ lệ thuận với ñộ chắc chắn của bảng quyết ñịnh. Do ñó khắc phục ñược nhược ñiểm ñộ nhất quán Yuhua Qian và các cộng sự [13]. Mệnh ñề 1.13. Cho hai bảng quyết ñịnh ( ),DS U C D= ∪ và ( )' ,DS U B D= ∪ . Nếu B C⊆ thì ( ) ( )'DS DSγ γ≥ . Chứng minh Theo giả thiết B C⊆ ta có / /U C U Bp , nghĩa là mỗi khối /U B sẽ là hợp của một số khối thuộc /U C . Không mất tính chất tổng quát, chỉ cần chứng minh mệnh ñề trong trường hợp các khối của /U B trùng với các khối của /U C , ngoại trừ chỉ một khối của /U B là hợp của hai khối trong /U C , nghĩa là { }1 2/ , ,..., mU C X X X= và { }1 2 1 1 1 1/ , ,..., , ,..., , ,..., ,u u v v m u vU B X X X X X X X X X− + − += ∪ . Thật vậy, ta có ( ) ( ) ( ) 2 2 ' 2 2 1, , 1 1 m n n i j u v j i i u i v j j X D X X D DS DS U U γ γ = ≠ ≠ = = ∩ ∪ ∩ − = +∑ ∑ ∑ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 29 2 2 2 2 2 2 1, , 1 1 1 m n n n i j u j v j i i u i v j j j X D X D X D U U U= ≠ ≠ = = = ∩ ∩ ∩ − − −∑ ∑ ∑ ∑ ( )2 2 2 2 2 2 1 1 1 n n n u j v j u j v j j j j X D X D X D X D U U U= = = ∩ + ∩ ∩ ∩ = − −∑ ∑ ∑ ( ) ( )'2 1 2 0 n u j v j j X D X D DS DS U γ γ = ∩ ∩ = ≥ ⇔ ≥∑ . ðiều kiện bằng nhau ( ) ( )'DS DSγ γ= xảy ra khi và chỉ khi / /U D U Cp và / /U D U Bp , nghĩa là DS và 'DS là các bảng quyết ñịnh nhất quán ngược. 1.7.4. Sự thay ñổi các ñộ ño khi thực hiện các phương pháp rút gọn thuộc tính Mệnh ñề 1.14. Cho hai bảng quyết ñịnh ( ),DS U C D= ∪ và ( )' ,DS U B D= ∪ . Nếu B là rút gọn của C dựa trên miền dương thì ( ) ( ) ( ) ( ) ( ) ( )' ' ', ,DS DS g DS g DS DS DSα α β β γ γ≤ ≤ ≥ . Chứng minh 1) ( ) ( )'DS DSα α≤ Suy ra từ Mệnh ñề 1.10. 2) ( ) ( )'g DS g DSβ β≤ Suy ra từ Mệnh ñề 1.12. 3) ( ) ( )'DS DSγ γ≥ Suy ra từ Mệnh ñề 1.13. Từ Mệnh ñề 1.14 ta rút ra kết luận phương pháp rút gọn thuộc tính dựa trên miền dương làm giảm ñộ chắc chắn, ñộ nhất quán và tăng ñộ hỗ trợ của bảng quyết ñịnh. Hơn nữa, phương pháp này bảo toàn ñộ chắc chắn của các luật sinh bởi các ñối tượng thuộc miền dương (các luật chắc chắn) và giảm ñộ chắc chắn của các luật sinh bởi các ñối tượng ngoài miền dương (các luật không chắc chắn). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 30 Mệnh ñề 1.15. Cho hai bảng quyết ñịnh ( ),DS U C D= ∪ và ( )' ,DS U B D= ∪ . Nếu B là rút gọn của C dựa trên Shannon entropy thì ( ) ( ) ( ) ( ) ( ) ( )' ' ', ,DS DS g DS g DS DS DSα α β β γ γ= = ≥ . Chứng minh Nếu B là một rút gọn của C dựa trên Shannon entropy thì ( ) ( )| |H D B H D C= , theo ñiều kiện bằng nhau của Mệnh ñề 1.10 và Mệnh ñề 1.12 ta có ( ) ( )'DS DSα α= , ( ) ( )'g DS g DSβ β= . Mặt khác, theo Mệnh ñề 1.13 ta có ( ) ( )'DS DSγ γ≥ . Từ Mệnh ñề 1.15 ta rút ra kết luận phương pháp rút gọn thuộc tính sử dụng ñộ ño Shannon entropy không thay ñổi ñộ chắc chắn, ñộ nhất quán và tăng ñộ hỗ trợ của bảng quyết ñịnh. Nghĩa là bảo toàn ñộ chắc chắn và tăng ñộ hỗ trợ của tất cả các luật của bảng quyết ñịnh. Mệnh ñề 1.16. Cho hai bảng quyết ñịnh ( ),DS U C D= ∪ và ( )' ,DS U B D= ∪ . Nếu B là rút gọn của C dựa trên Liang Entropy thì ( ) ( ) ( ) ( ) ( ) ( )' ' ', ,DS DS g DS g DS DS DSα α β β γ γ= = ≥ . Chứng minh Nếu B là một rút gọn của C dựa trên Liang entropy thì theo Mệnh ñề 1.2 ta có, với mọi , /u vX X U B∈ , nếu /u v kX X Y U C∪ ⊆ ∈ thì uX , vX ñều thuộc một khối /jD U D∈ , từ ñó suy ra 1 u j v j u v X D X D X X ∩ ∩ = = . Từ Mệnh ñề 1.1 ta suy ra ( ) ( )| |H D B H D C= , theo ñiều kiện bằng nhau của các Mệnh ñề 1.10 và Mệnh ñề 1.12 ta có ( ) ( ) ( ) ( )' ',DS DS g DS g DSα α β β= = . Mặt khác, theo Mệnh ñề 1.13 ta có ( ) ( )'DS DSγ γ≥ . Do ñó, ñộ chắc chắn và ñộ nhất quán của bảng quyết ñịnh khi thực hiện phương pháp rút gọn thuộc tính sử dụng Shannon entropy và Liang entropy Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 31 (hoặc ñộ ño lượng tri thức khác nhau, sử dụng ma trận phân biệt) là như nhau. Tuy nhiên, số lượng thuộc tính của tập rút gọn dựa trên Liang entropy nhiều hơn số thuộc tính của tập rút gọn dựa trên Shannon entropy nên ñộ hỗ trợ của phương pháp sử dụng Shannon entropy lớn hơn. Nhận xét 1.3 - Với các bài toán chỉ ñòi hỏi phân lớp chính xác tập dữ liệu (bảo toàn các luật chắc chắn sinh bởi các ñối tượng thuộc miền dương) thì sử dụng phương pháp rút gọn thuộc tính dựa trên miền dương. - Với các bài toán ñòi hỏi bảo toàn ñộ chắc chắn của tất cả các luật, phương pháp rút gọn thuộc tính sử dụng Shannon entropy rõ ràng hiệu quả hơn phương pháp sử dụng Liang entropy vì tập rút gọn thu ñược tối thiểu hơn, do ñó tập luật thu ñược có ñộ hỗ trợ cao hơn. Tuy nhiên, trong công thức tính toán Shannon entropy có sử dụng biểu thức logarit nên ñộ phức tạp tính toán cao hơn Liang entropy. Trong nỗ lực nghiên cứu ñể tìm ñộ ño mới thay thế Shannon entropy nhằm giảm thiểu ñộ phức tạp tính toán, trong phần 2.3 của luận văn, tôi tìm hiểu phương pháp rút gọn sử dụng metric. 1.8. Kết luận Chương 1 Chương 1 nêu khái quát về tập thô và trình bày kết quả nghiên cứu về mối quan hệ giữa các tập rút gọn của các phương pháp rút gọn thuộc tính, tìm hiểu các ñộ ño ñánh giá hiệu năng bảng quyết ñịnh và nghiên cứu sự thay ñổi các ñộ ño này khi thực hiện các phương pháp rút gọn thuộc tính. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 32 Chương 2. MỘT SỐ PHƯƠNG PHÁP RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ðỊNH. 2.1. Mở ñầu Rút gọn thuộc tính là ứng dụng quan trọng nhất trong lý thuyết tập thô, ñã và ñang thu hút sự chú ý quan tâm của nhiều nhà nghiên cứu. Trong thực tế, dữ liệu thường ña dạng, 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ìm ra các thuộc tính cốt yếu và cần thiết trong cơ sở dữ liệu. Nói cách khác, rút gọn thuộc tính là quá trình loại bỏ (tối ña) các thuộc tính dư thừa mà phần thuộc tính còn lại vẫn chứa ñầy ñủ thông tin của dữ liệu; 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. ðối với một bảng quyết ñịnh có thể có nhiều tập rút gọn khác nhau. ðộ phức tạp của thuật toán tìm tất cả các tập rút gọn là hàm mũ của số thuộc tính ñiều kiện. Tuy nhiên, trong thực tế 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, phần lớn các kết quả nghiên cứu về rút gọn thuộc tính ñều ñề xuất các thuật toán heuristic rút gọn thuộc tính theo một tiêu chuẩn tối ưu ñặt ra. Các thuật toán này ñều có ñộ phức tạp tính toán thời gian ña thức, do ñó có thể áp dụng ñối với các bài toán có khối lượng dữ liệu lớn. Cho bảng quyết ñịnh ( , , , )DS U C D V f= ∪ , nếu R là một tập rút gọn của tập thuộc tính ñiều kiện C thì theo ñịnh nghĩa của Pawlak, R chứa mọi thuộc tính lõi, hay nói cách khác tập tính lõi nằm trrong tất cả các tập rút gọn của bảng quyết ñịnh. Do ñó, các thuật toán tìm tập rút gọn theo tiếp cận heuristic thường ñược phân thành hai nhóm: các thuật toán tính toán lõi và các thuật toán không tính toán lõi. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 33 Ý tưởng chung cho các thuật toán tính toán lõi là xuất phát từ tập lõi, bổ sung dần dần các thuộc tính vào tập lõi cho ñến khi thỏa mãn ñiều kiện của một tập rút gọn. Vấn ñề ñặt ra là chọn thuộc tính nào ñể ñưa vào tập lõi, ñiều này dẫn ñến việc cần có tiêu chuẩn nào ñó ñể ñánh giá các thuộc tính ñảm bảo chọn ñược các thuộc tính có “chất lượng” ñưa vào tập lõi. Từ ñó xuất hiện khái niệm ñộ quan trọng của thuộc tính, ñộ ño này sử dụng làm tiêu chuẩn lựa chọn thuộc tính trong các thuật toán heuristic. Giả sử ( )CORE C là tập lõi và R là một tập rút gọn của bảng quyết ñịnh DS , khi ñó các thuật toán heuristic tính toán lõi ñược thực hiện theo sơ ñồ khối hình: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 34 Hình 2.1: Sơ ñồ khối của thuật toán tìm tập rút gọn tính toán lõi Kiểm tra R có phải là tập rút gọn hay chưa? Bắt ñầu Tìm tập nhân CORE(C) R := CORE(C) Chọn thuộc tính a C R∈ − có ñộ quan trọng lớn nhất { }:R R a= ∪ Kiểm tra R có phải là tập rút gọn hay chưa? Loại bỏ các thuộc tính dư thừa trong R nếu có Return (R) Có Không Có Không Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 35 Mỗi phương pháp rút gọn thuộc tính ñều ñưa ra ñịnh nghĩa một ñộ ño và xây dựng tập rút gọn dựa trên ñộ ño này. Tập thuộc tính R ñược gọi là một tập rút gọn của thuộc tính ñiều kiện C nếu ñộ ño trên R cũng bằng ñộ ño trên C . ðộ quan tọng của thuộc tính a C∈ là sự thay ñổi của ñộ ño khi loại thuộc tính a ra khỏi C . Các ñộ ño ñáng chú ý là entropy thông tin, hạt tri thức, metric sẽ ñược trình bày trong chương này. Các thuật toán heuristic không tính toán lõi xây dựng theo hai cách tiếp cận khác nhau. Cách tiếp cận thứ nhất là bottom-up, tức là xuất phát từ tập rỗng và bổ sung dần dần các thuộc tính theo thứ tự giảm dần của ñộ quan trọng cho ñến khi thu ñược tập rút gọn, nghĩa là các thuộc tính có ñộ quan trọng lớn nhất sẽ ñược xem xét bổ sung vào trước. Cách tiếp cận thứ hai là top-down, nghĩa là xuất phát từ tập thuộc tính C ban ñầu, loại bỏ dần dần các thuộc tính theo thứ tự tăng dần của ñộ quan trọng, nghĩa là các thuộc tính có ñộ quan trọng nhỏ nhất sẽ ñược xem xét ñể loại bỏ trước. Cả hai cách tiếp cận này ñều ñòi hỏi phải sắp xếp danh sách các thuộc tính ban ñầu theo thứ tự giảm dần hoặc tăng dần của ñộ quan trọng. Trong mấy 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 nghiên cứu về rút gọn thuộc tính. 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 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 entropy thông tin, phương pháp sử dụng ma trận phân biệt, pương pháp sử dụng các ñộ ño trong tính toán hạt Mỗi phương pháp phù hợp với một bài toán trong thực tế. Rút gọn thuộc tính dựa trên miền dương Từ khái niệm tập rút gọn dựa trên miền dương của Pawlak, có rất nhều tác giả ñề xuất và cải tiến các thuật toán tìm tập rút gọn dựa trên miền dương. Ye. D ñã xây dựng thuật toán phân hoạch /U C với ñộ phức tạp ( )2O C U và Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 36 thuật toán tìm tập rút gọn với ñộ phức tạp ( )2 2O