Nghiên cứu phương pháp lai ghép trong rút gọn thuộc tính theo tiếp cận tập thô mờ

Chuyên khảo phân tích Luận án một số phương pháp lai ghép trong rút gọn thuộc tính theo tiếp cận tập thô mờ, đánh giá các khía cạnh quan trọng, đề xuất hướng nghiên cứu tiếp theo.

• Trường học: Trường Đại Học
• Chuyên ngành: Khoa Học Máy Tính
• Đề tài: Phương Pháp Lai Ghép Hiệu Quả Trong Rút Gọn Thuộc Tính Với Tập Thô Mờ
• Loại tài liệu: luận án

Mục lục chi tiết

• MỤC LỤC
• Danh mục các thuật ngữ
• Bảng các ký hiệu, từ viết tắt
• Danh sách bảng
• Danh sách hình vẽ
• 1. MỞ ĐẦU
• 1.1. TỔNG QUAN VỀ RÚT GỌN THUỘC TÍNH THEO TIẾP CẬN TẬP THÔ MỜ
• 1.2. Một số khái niệm trong lý thuyết tập thô
• 1.3. Hệ thông tin và bảng quyết định
• 1.4. Quan hệ tương đương
• 1.5. Các tập xấp xỉ và tập thô
• 2. RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH SỬ DỤNG ĐỘ PHỤ THUỘC MỜ VÀ KHOẢNG CÁCH MỜ
• 2.1. Rút gọn thuộc tính sử dụng độ phụ thuộc mờ
• 2.2. Rút gọn thuộc tính sử dụng độ phụ thuộc theo tiếp cận filter
• 2.3. Rút gọn thuộc tính sử dụng độ phụ thuộc mờ theo tiếp cận filter
• 2.4. Rút gọn thuộc tính sử dụng độ phụ thuộc mờ theo tiếp cận filter-wrapper
• 2.5. Thực nghiệm các thuật toán
• 2.6. Rút gọn thuộc tính sử dụng khoảng cách mờ
• 2.6.1. Xây dựng khoảng cách mờ giữa hai tập mờ
• 2.6.2. Xây dựng khoảng cách mờ giữa hai phân hoạch mờ
• 2.6.3. Rút gọn thuộc tính sử dụng khoảng cách mờ theo tiếp cận filter
• 2.6.4. Rút gọn thuộc tính sử dụng khoảng cách mờ theo tiếp cận filter-wrapper
• 2.6.5. Thực nghiệm các thuật toán
• 2.7. Kết luận chương 2
• 3. RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH THAY ĐỔI SỬ DỤNG KHOẢNG CÁCH MỜ
• 3.1. Thuật toán gia tăng filter-wrapper tìm tập rút gọn xấp xỉ khi bổ sung tập đối tượng
• 3.2. Công thức gia tăng tính khoảng cách mờ khi bổ sung tập đối tượng
• 3.3. Thuật toán gia tăng filter-wrapper tìm tập rút gọn khi bổ sung tập đối tượng
• 3.4. Thực nghiệm thuật toán
• 3.5. Thuật toán filter-wrapper tìm tập rút gọn khi loại bỏ tập đối tượng
• 3.6. Công thức cập nhật khoảng cách mờ khi loại bỏ tập đối tượng
• 3.7. Thuật toán filter-wrapper tìm tập rút gọn khi loại bỏ tập đối tượng
• 3.8. Kết luận chương 3
• Danh mục các công trình của tác giả
• Tài liệu tham khảo

Tóm tắt

I. Tổng quan về rút gọn thuộc tính

Rút gọn thuộc tính là một vấn đề quan trọng trong khai phá dữ liệu, nhằm loại bỏ các thuộc tính dư thừa mà không làm mất thông tin cần thiết. Phương pháp lai ghép được áp dụng để tối ưu hóa quá trình này. Hai cách tiếp cận chính trong rút gọn thuộc tính là filter và wrapper. Cách tiếp cận filter thực hiện việc rút gọn độc lập với thuật toán khai phá dữ liệu, trong khi wrapper kết hợp việc lựa chọn thuộc tính với thuật toán khai phá. Lý thuyết tập thô mờ (Fuzzy Rough Set) là công cụ hữu ích trong việc giải quyết bài toán này, cho phép xấp xỉ các tập mờ dựa trên quan hệ tương đương mờ. Các nghiên cứu gần đây cho thấy rằng các phương pháp rút gọn thuộc tính theo tiếp cận tập thô mờ có độ chính xác cao hơn so với các phương pháp truyền thống.

1.1. Khái niệm về tập thô mờ

Lý thuyết tập thô mờ được phát triển từ lý thuyết tập thô truyền thống, cho phép xử lý các khái niệm không chắc chắn trong dữ liệu. Tập thô mờ sử dụng quan hệ tương đương mờ để xấp xỉ các tập mờ, từ đó giúp nâng cao độ chính xác của mô hình phân lớp. Các khái niệm như miền dương mờ và ma trận tương đương mờ là những yếu tố quan trọng trong việc xây dựng các thuật toán rút gọn thuộc tính. Việc áp dụng lý thuyết này trong thực tiễn đã chứng minh được tính hiệu quả trong việc cải thiện độ chính xác của các mô hình phân lớp.

1.2. Các phương pháp rút gọn thuộc tính

Các phương pháp rút gọn thuộc tính theo tiếp cận tập thô mờ bao gồm việc sử dụng độ phụ thuộc mờ và khoảng cách mờ. Những phương pháp này không chỉ giúp giảm thiểu số lượng thuộc tính mà còn nâng cao độ chính xác của mô hình phân lớp. Các nghiên cứu đã chỉ ra rằng việc áp dụng các thuật toán gia tăng filter-wrapper có thể cải thiện đáng kể hiệu suất của quá trình rút gọn thuộc tính. Điều này cho thấy sự cần thiết phải phát triển các thuật toán mới nhằm tối ưu hóa quy trình rút gọn thuộc tính trong các bảng quyết định lớn và thay đổi.

II. Phương pháp lai ghép trong rút gọn thuộc tính

Phương pháp lai ghép filter-wrapper được đề xuất nhằm tối ưu hóa quá trình rút gọn thuộc tính. Giai đoạn filter tìm kiếm các ứng viên cho tập rút gọn dựa trên độ đo, trong khi giai đoạn wrapper đánh giá độ chính xác phân lớp của các ứng viên. Việc kết hợp này giúp tìm ra tập rút gọn xấp xỉ có độ chính xác cao nhất. Các thuật toán gia tăng filter-wrapper cho phép xử lý các bảng quyết định lớn mà không cần tính toán lại toàn bộ bảng sau mỗi thay đổi. Điều này không chỉ tiết kiệm thời gian mà còn nâng cao hiệu quả của quá trình rút gọn thuộc tính.

2.1. Độ phụ thuộc mờ trong rút gọn thuộc tính

Độ phụ thuộc mờ là một trong những yếu tố quan trọng trong việc xác định mối quan hệ giữa các thuộc tính trong tập dữ liệu. Việc sử dụng độ phụ thuộc mờ giúp xác định các thuộc tính nào là cần thiết cho việc phân lớp, từ đó loại bỏ những thuộc tính không cần thiết. Các nghiên cứu đã chỉ ra rằng việc áp dụng độ phụ thuộc mờ trong các thuật toán rút gọn thuộc tính có thể cải thiện đáng kể độ chính xác của mô hình phân lớp, đồng thời giảm thiểu độ phức tạp của mô hình.

2.2. Khoảng cách mờ trong rút gọn thuộc tính

Khoảng cách mờ được sử dụng để đo lường sự khác biệt giữa các đối tượng trong tập dữ liệu. Việc xây dựng các công thức khoảng cách mờ cho phép xác định các thuộc tính có ảnh hưởng lớn đến kết quả phân lớp. Các thuật toán rút gọn thuộc tính sử dụng khoảng cách mờ đã cho thấy hiệu quả cao trong việc tối ưu hóa số lượng thuộc tính, đồng thời duy trì độ chính xác của mô hình phân lớp. Điều này cho thấy rằng khoảng cách mờ là một công cụ hữu ích trong việc phát triển các phương pháp rút gọn thuộc tính hiện đại.

III. Kết luận và hướng phát triển

Luận án đã trình bày các phương pháp rút gọn thuộc tính theo tiếp cận tập thô mờ và các thuật toán gia tăng filter-wrapper. Những đóng góp này không chỉ nâng cao độ chính xác của mô hình phân lớp mà còn giảm thiểu số lượng thuộc tính cần thiết. Hướng phát triển trong tương lai có thể tập trung vào việc cải thiện các thuật toán hiện tại, cũng như áp dụng các phương pháp mới trong các lĩnh vực khác nhau của khai phá dữ liệu. Việc nghiên cứu sâu hơn về các ứng dụng thực tiễn của các phương pháp này sẽ giúp mở rộng khả năng áp dụng trong các bài toán thực tế.

3.1. Đề xuất nghiên cứu tiếp theo

Các nghiên cứu tiếp theo có thể tập trung vào việc phát triển các thuật toán lai ghép mới, kết hợp giữa các phương pháp rút gọn thuộc tính khác nhau. Việc áp dụng các công nghệ mới như học sâu và trí tuệ nhân tạo vào quá trình rút gọn thuộc tính cũng là một hướng đi tiềm năng. Điều này không chỉ giúp cải thiện độ chính xác mà còn mở rộng khả năng xử lý dữ liệu lớn trong các ứng dụng thực tiễn.

Trích đoạn nội dung tài liệu

Chương 1 cũng trình bày các nghiên cứu liên quan đến rút gọn thuộc tính theo tiếp cận tập thô mờ, các nghiên cứu liên quan đến phương pháp gia tăng rút gọn thuộc tính theo tiếp cận tập thô mờ trong mấy năm gần đây. Trêm cơ sở đó, luận án phân tích các vấn đề còn tồn tại và nêu rõ các mục tiêu nghiên cứu cùng với tóm tắt các kết quả đạt được. Các đóng góp chính của luận án được trình bày trong chương 2, chương 3. Chương 2 trình bày hai kết quả nghiên cứu: thứ nhất là đề xuất thuật toán filter- wrapper tìm tập rút gọn sử dụng độ phụ thuộc mờ trong tập thô mờ; thứ hai là xây 6 dựng một độ đo khoảng cách mờ và đề xuất thuật toán filter-wrapper tìm tập rút gọn sử dụng khoảng cách mờ được xây dựng theo tiếp cận tập thô mờ.

Cả hai đề xuất đều nhằm mục tiêu giảm thiểu số thuộc tính của tập rút gọn, từ đó giảm thiểu độ phức tạp của mô hình so với các phương pháp filter trước đây. Chương 3 đề xuất hai thuật toán gia tăng filter-wrapper; thuật toán gia tăng filter-wrapper thứ nhất tìm tập rút gọn của bảng quyết định trong trường hợp bổ sung tập thuộc tính; thuật toán gia tăng filter-wrapper thứ hai tìm tập rút gọn của bảng quyết định trong trường hợp loại bỏ tập thuộc tính. Cả hai thuật toán đề xuất đều sử dụng độ đo khoảng cách mờ đề xuất ở chương 2 và đều có mục tiêu là giảm thiểu thời gian thực hiện so với thuật toán không gia tăng và giảm thiểu số thuộc tính tập rút gọn, từ đó giảm thiểu độ phức tạp của mô hình so với các thuật toán gia tăng khác đã công bố. Cuối cùng, phần kết luận nêu những đóng góp của luận án, hướng phát triển và những vấn đề quan tâm của tác giả.

TỔNG QUAN VỀ RÚT GỌN THUỘC TÍNH THEO TIẾP CẬN TẬP THÔ MỜ 1. Một số khái niệm trong lý thuyết tập thô Lý thuyết tập thô truyền thống do Z.Pawlak [101] đề xuất là công cụ toán học hiệu quả để biểu diễn và xử lý các khái niệm không chắc chắn. Phương pháp tiếp cận chính của lý thuyết tập thô là dựa trên quan hệ tương đương (hay quan hệ không phân biệt được) để xấp xỉ tập hợp. Khi đó, mọi tập đối tượng đều được xấp xỉ bởi hai tập rõ là xấp xỉ dưới và xấp xỉ trên của nó.

Mỗi tập xấp xỉ được hợp thành bởi một hoặc nhiều lớp tương đương, là cơ sở để xây dựng các thuật toán rút gọn thuộc tính và khai phá tri thức từ dữ liệu. Trong phần này, luận án trình bày một số khái niệm cơ bản trong lý thuyết tập thô truyền thống của Z.Pawlak [101], là cơ sở nền tảng cho lý thuyết tập thô mờ được trình bày ở phần 1. Hệ thông tin và bảng quyết định Hệ thông tin là công cụ biểu diễn tri thức dưới dạng một bảng dữ liệu gồm n cột ứng với n thuộc tính và m hàng ứng với m đối tượng. Một cách hình thức, hệ thông tin là một cặp IS  U , A trong đó U là tập hữu hạn, khác rỗng các đối tượng, gọi là tập vũ trụ; A là tập hữu hạn, khác rỗng các thuộc 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 DS  U , C  D  là một dạng đặc biệt của hệ thông tin, trong đó tập các thuộc tính A bao gồm hai tập con tách biệt nhau: Tập các thuộc tính điều kiện C và tập các thuộc tính quyết định D với C  D  . Quan hệ tương đương Xét hệ thông tin IS  U , A , mỗi tập con thuộc tính P  A xác định một quan hệ hai ngôi trên U, ký hiệu là IND  P  , xác định bởi   IND  P    u, v  U U a  P, a u   a  v  .1) 8 Với a  u  là giá trị thuộc tính a tại đối tượng u. IND  P  gọi là quan hệ P-không phân biệt được trên U.

Dễ thấy rằng IND P  là một quan hệ tương đương trên U. Nếu  u, v   IND P  thì hai đối tượng u và v không phân biệt được bởi các thuộc tính trong P. Quan hệ tương đương IND  P  xác định một phân hoạch trên U, ký hiệu là U / IND  P  hay U / P , trong đó mỗi thành phần trong phân hoạch U / P là một lớp tương đương. Ký hiệu lớp tương đương trong phân hoạch U / P chứa đối tượng u là u P , khi đó u P  v U u, v   IND  P .

Ký hiệu phân hoạch sinh bởi thuộc tính a  P là U / a , khi đó ta có: U / P  a  P : U / a với A  B  X Y :X  A ,Y  B ,X Y    1. Các tập xấp xỉ và tập thô Cho hệ thông tin IS  U , A và tập đối tượng X  U. Với một tập thuộc tính P  A cho trước, ta thu được các lớp tương đương sinh bởi phân hoạch U / P. 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 / P , 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 / P.

Có hai cách xấp xỉ tập đối tượng X thông qua tập thuộc tính P, được gọi là P- xấp xỉ dưới và P-xấp xỉ trên của X, ký hiệu lần lượt là PX và PX , được xác định như sau:    PX  u U u P  X , PX  u U u P  X    (1.2) Tập PX 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 PX bao gồm các phần tử của U có khả năng thuộc vào X dựa vào tập thuộc tính P. Từ hai tập xấp xỉ nêu trên, ta định nghĩa P-miền biên của X là tập PN P  X   PX  PX và P-miền ngoài của X là tập U  PX. Dễ thấy, P-miền biên của X là tập chứa các đối tượng có thể thuộc X, còn P-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 / P , các xấp xỉ dưới và trên của X có thể viết lại 9 PX  Y U / P Y  X  , PX  Y U / P Y  X   (1.3) Trong trường hợp PN P  X    thì X được gọi là tập rõ, ngược lại X được gọi là tập thô.

Xét hệ thông tin IS  U , A với P, Q  A , ta gọi tập POS P (Q)   PX  X U / Q là P-miền dương của Q. Dễ thấy POSP (Q) là tập các đối tượng trong U được phân lớp đúng vào các lớp của U / Q sử dụng tập thuộc tính P. Rõ ràng, POSP (Q) là tập tất cả các đối tượng u sao cho với mọi v U mà u  P   v  P  ta đều có u  Q   v  Q . Nói  một cách hình thức, POS P (Q)  u U u P  u Q.

Một số khái niệm trong lý thuyết tập thô mờ Lý thuyết tập thô truyền thống của Pawlak [101] sử dụng quan hệ tương đương để xấp xỉ tập hợp. Trong khi đó, lý thuyết tập thô mờ (Fuzzy Rough Set) do D. Dubois và các cộng sự [22, 23] đề xuất sử dụng quan hệ tương đương mờ để xấp xỉ tập mờ. Giống như lý thuyết tập thô truyền thống, lý thuyết tập thô mờ được xem là công cụ hiệu quả giải quyết bài toán rút gọn thuộc tính và trích lọc luật trên bảng quyết định.

Cho đến nay, các nghiên cứu liên quan đến rút gọn thuộc tính theo tiếp cận tập thô mờ tập trung vào hai hướng chính: thứ nhất là rút gọn thuộc tính trên các bảng quyết định mờ (bảng quyết định với giá trị thuộc tính là các tập mờ); thứ hai là rút gọn thuộc tính trực tiếp trên bảng quyết định gốc (bảng quyết định không qua bước rời rạc hóa dữ liệu) nhằm nâng cao độ chính xác của mô hình phân lớp. Luận án nghiên cứu hướng thứ hai, do đó trong phần này luận án trình bày một số khái niệm cơ bản về mô hình tập thô mờ trên bảng quyết định. Các khái niệm này được sử dụng trong các chương sau của luận án. Quan hệ tương đương mờ Định nghĩa 1.

[32, 71] Cho bảng quyết định DS  U , C  D  , một quan hệ R xác định trên miền giá trị thuộc tính được gọi là quan hệ tương đương mờ nếu thỏa mãn các điều kiện sau với mọi x, y, z U 10 1) Tính phản xạ (reflexive): R  x, x   1 ; 2) Tính đối xứng (symetric): R  x, y   R  y, x  ; 3)Tính bắc cầu max-min (max-min transitive): R  x, z   min R  x, y  , R  y, z  ; với R  x, y  là giá trị quan hệ giữa hai đối tương x và y. [72] Cho bảng quyết định DS  U , C  D  và quan hệ tương đương mờ R. Ký hiệu R P , R Q tương ứng là quan hệ R xác định trên tập thuộc tính P, Q. Khi đó, với mọi x, y U ta có: 1) R P  RQ  R P  x, y   RQ  x, y    2) R PQ  R P  RQ  R  x, y   max R P  x, y  , RQ  x, y  3) R PQ  R  R  R  x, y   min R  x, y  , R  x, y  P Q P Q 4) R P  RQ  R P  x, y   RQ  x, y  1.

Ma trận tương đương mờ Ma trận tương đương mờ là công cụ biểu diễn giá trị quan hệ tương đương mờ giữa các đối tượng của bảng quyết định và được định nghĩa như sau: Định nghĩa 1. Cho bảng quyết định DS  U , C  D  với U  x1 , x2 ,., xn  và R P là quan hệ tương đương mờ xác định trên tập thuộc tính P  C .