Phát Triển Phương Pháp Rút Gọn Thuộc Tính Trong Bảng Quyết Định Không Đầy Đủ Sử Dụng FilterWrapper

Luận án phát triển phương pháp rút gọn thuộc tính trong bảng quyết định không đầy đủ, áp dụng tiếp cận filterwrapper để tối ưu hóa hiệu quả xử lý dữ liệu.

• Tác giả: Nguyễn Bá Quảng
• Người hướng dẫn: PGS. TS Nguyễn Long Giang
• Trường học: Viện Khoa học và Công nghệ Quân sự
• Chuyên ngành: Cơ sở toán học cho tin học
• Đề tài: Phát Triển Một Số Phương Pháp Rút Gọn Thuộc Tính Trong Bảng Quyết Định Không Đầy Đủ Theo Tiếp Cận Filter-Wrapper
• Loại tài liệu: luận án tiến sĩ toán học
• Năm xuất bản: 2021
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: TỔNG QUAN
• 1.1. Khái niệm cơ bản
• 1.2. Phương pháp nghiên cứu
• 1.3. Kết luận chương 1
• 2. CHƯƠNG 2: THUẬT TOÁN FILTER-WRAPPER TÌM TẬP RÚT GỌN CỦA BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ
• 2.1. Xây dựng độ đo khoảng cách trong bảng quyết định không đầy đủ
• 2.2. Xây dựng độ đo khoảng cách giữa hai tập hợp
• 2.3. Xây dựng độ đo khoảng cách giữa hai tập thuộc tính
• 2.4. Rút gọn thuộc tính trong bảng quyết định không đầy đủ sử dụng khoảng cách
• 2.5. Xây dựng thuật toán filter tìm tập rút gọn của bảng quyết định không đầy đủ
• 2.6. Đề xuất thuật toán filter-wrapper tìm tập rút gọn của bảng quyết định không đầy đủ
• 2.7. Thực nghiệm và đánh giá kết quả
• 2.8. Kết luận chương 2
• 3. CHƯƠNG 3: CÁC THUẬT TOÁN GIA TĂNG FILTER-WRAPPER TÌM TẬP RÚT GỌN CỦA BẢNG QUYẾT ĐỊNH THAY ĐỔI
• 3.1. Thuật toán gia tăng filter-wrapper tìm tập rút gọn khi bổ sung, loại bỏ tập đối tượng
• 3.2. Công thức cập nhật khoảng cách 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. Công thức cập nhật khoảng cách khi loại bỏ tập đối tượng
• 3.5. Thuật toán gia tăng filter-wrapper cập nhật tập rút gọn khi loại bỏ tập đối tượng
• 3.6. Thực nghiệm và đánh giá các thuật toán
• 3.7. Thuật toán gia tăng filter-wrapper tìm tập rút gọn khi bổ sung, loại bỏ tập thuộc tính
• 3.8. Công thức cập nhật khoảng cách khi bổ sung tập thuộc tính
• 3.9. Thuật toán gia tăng filter-wrapper tìm tập rút gọn khi bổ sung tập thuộc tính
• 3.10. Công thức cập nhật khoảng cách khi loại bỏ tập thuộc tính
• 3.11. Thuật toán gia tăng filter-wrapper cập nhật tập rút gọn khi loại bỏ tập thuộc tính
• 3.12. Thực nghiệm và đánh giá các thuật toán
• 3.13. Kết luận chương 3
• DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC ĐÃ CÔNG BỐ
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Phát triển phương pháp rút gọn thuộc tính

Luận án tập trung vào phát triển phương pháp rút gọn thuộc tính trong bảng quyết định không đầy đủ theo tiếp cận FilterWrapper. Các phương pháp này nhằm loại bỏ các thuộc tính dư thừa, giảm độ phức tạp của mô hình và cải thiện độ chính xác phân lớp. Rút gọn thuộc tính là bước tiền xử lý quan trọng trong khai phá dữ liệu, đặc biệt khi xử lý các bảng quyết định lớn và phức tạp.

1.1. Bảng quyết định không đầy đủ

Bảng quyết định không đầy đủ là bảng dữ liệu chứa các giá trị thiếu trên miền giá trị thuộc tính. Điều này gây khó khăn trong việc áp dụng các phương pháp truyền thống. Luận án sử dụng mô hình tập thô dung sai để giải quyết vấn đề này. Mô hình này mở rộng quan hệ tương đương trong lý thuyết tập thô truyền thống thành quan hệ dung sai, cho phép xử lý trực tiếp các bảng quyết định không đầy đủ mà không cần tiền xử lý giá trị thiếu.

1.2. Tiếp cận FilterWrapper

Tiếp cận FilterWrapper kết hợp hai phương pháp: filter và wrapper. Giai đoạn filter sử dụng độ đo để lựa chọn các thuộc tính quan trọng, trong khi giai đoạn wrapper đánh giá độ chính xác phân lớp của các tập thuộc tính được chọn. Phương pháp này giúp tối ưu hóa số lượng thuộc tính và cải thiện độ chính xác của mô hình phân lớp.

II. Thuật toán FilterWrapper tìm tập rút gọn

Luận án đề xuất thuật toán FilterWrapper để tìm tập rút gọn trong bảng quyết định không đầy đủ. Thuật toán này sử dụng độ đo khoảng cách để xác định mức độ quan trọng của các thuộc tính. Kết quả thử nghiệm cho thấy, thuật toán giảm thiểu đáng kể số lượng thuộc tính trong tập rút gọn mà vẫn duy trì hoặc cải thiện độ chính xác phân lớp.

2.1. Xây dựng độ đo khoảng cách

Độ đo khoảng cách được xây dựng để đánh giá sự khác biệt giữa các tập hợp thuộc tính trong bảng quyết định không đầy đủ. Độ đo này giúp xác định các thuộc tính có ảnh hưởng lớn đến kết quả phân lớp, từ đó loại bỏ các thuộc tính dư thừa.

2.2. Thực nghiệm và đánh giá

Các thử nghiệm được thực hiện trên các bộ dữ liệu từ kho UCI. Kết quả cho thấy, thuật toán FilterWrapper giảm thiểu số lượng thuộc tính trong tập rút gọn và cải thiện độ chính xác phân lớp so với các phương pháp truyền thống. Điều này chứng minh tính hiệu quả của phương pháp đề xuất.

III. Thuật toán gia tăng FilterWrapper

Luận án cũng đề xuất các thuật toán gia tăng FilterWrapper để xử lý các bảng quyết định thay đổi. Các thuật toán này chỉ cập nhật tập rút gọn trên phần dữ liệu thay đổi, giảm thiểu thời gian tính toán và tăng hiệu quả xử lý.

3.1. Bổ sung và loại bỏ tập đối tượng

Khi bổ sung hoặc loại bỏ tập đối tượng, thuật toán gia tăng chỉ cập nhật lại tập rút gọn trên phần dữ liệu thay đổi. Điều này giúp giảm thiểu thời gian tính toán so với việc tính toán lại toàn bộ tập rút gọn.

3.2. Bổ sung và loại bỏ tập thuộc tính

Tương tự, khi bổ sung hoặc loại bỏ tập thuộc tính, thuật toán gia tăng chỉ cập nhật lại tập rút gọn trên phần dữ liệu thay đổi. Phương pháp này đặc biệt hiệu quả khi xử lý các bảng quyết định lớn và thường xuyên thay đổi.

IV. Ý nghĩa khoa học và thực tiễn

Luận án có ý nghĩa khoa học và thực tiễn lớn. Về mặt khoa học, các thuật toán đề xuất mở rộng lý thuyết tập thô dung sai và tiếp cận FilterWrapper. Về mặt thực tiễn, các phương pháp này giúp giảm thiểu độ phức tạp của mô hình và cải thiện độ chính xác phân lớp, đặc biệt trong bối cảnh dữ liệu lớn và thường xuyên thay đổi.

4.1. Ứng dụng trong khai phá dữ liệu

Các phương pháp đề xuất có thể áp dụng trong các bài toán khai phá dữ liệu, đặc biệt là các bài toán phân lớp và dự đoán. Chúng giúp tăng hiệu quả xử lý và giảm chi phí tính toán.

4.2. Hướng phát triển trong tương lai

Luận án mở ra hướng nghiên cứu mới trong việc kết hợp các phương pháp FilterWrapper với các mô hình khác như tập thô mờ hoặc học sâu, nhằm tiếp tục cải thiện hiệu quả của các thuật toán rút gọn thuộc tính.

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ô dung sai, 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ô dung sai trong mấy năm gần đây. Trên 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 kết quả nghiên cứu về xây dựng độ đo khoảng cách mới.

Sử dụng độ đo khoảng cách mới, chương 2 đề xuất thuật toán IDS_F_DAR tìm tập rút gọn theo tiếp cận filter và thuật toán IDS_FW_DAR tìm tập rút gọn 9 theo tiếp cận kết hợp filter-wrapper. Các thuật toán trên thực hiện trên bảng quyết định không đầy đủ cố định. Chương 3 xây dựng các công thức gia tăng tính độ đo khoảng cách và đề xuất bốn thuật toán gia tăng filter-wrapper tìm tập rút gọn trong bảng quyết định thay đổi, cụ thể là: 1) Thuật toán IDS_IFW_AO tìm tập rút gọn trong trường hợp bổ sung tập đối tượng; 2) Thuật toán IDS_IFW_DO tìm tập rút gọn trong trường hợp loại bỏ tập đối tượng; 3) Thuật toán IDS_IFW_AA tìm tập rút gọn trong trường hợp bổ sung tập thuộc tính; 4) Thuật toán IDS_IFW_DA tìm tập rút gọn trong trường hợp loại bỏ tập thuộc tính. 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Ô DUNG SAI 1. Hệ thông tin và mô hình tập thô truyền thống Lý thuyết tập thô truyền thống do Z.Pawlak [113] đề 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 [113], là cơ sở nền tảng cho mô hình tập thô dung sai được trình bày ở phần 1. Hệ thông tin 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; A là tập hữu hạn, khác rỗng các thuộc tính.

Mỗi thuộc tính a  A xác định một ánh xạ: a : U  Va với Va là tập giá trị của thuộc tính a A. Xét hệ thông tin IS  U , A. Mỗi tập con các 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 . IND  P  là quan hệ P-không phân biệt được.

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 11 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. 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 .

Mô hình tập thô truyền thống 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 B  A cho trước, chúng ta biểu diễn X thông qua các lớp tương đương của U / B (còn gọi là biểu diễn X bằng tri thức có sẵn B), người ta xấp xỉ X bởi hợp của một số hữu hạn các lớp tương đương của U / B. Có hai cách xấp xỉ tập đối tượng X thông qua tập thuộc tính B , được gọi là B-xấp xỉ dưới và B- xấp xỉ trên của X, ký hiệu là lượt là BX và BX , được xác định như sau:    BX  u U u B  X , BX  u U u B  X   . Tập BX bao gồm tất cả các phần tử của U chắc chắn thuộc vào X, còn tập BX bao gồm các phần tử của U có thể thuộc vào X dựa trên tập thuộc tính B. Từ hai tập xấp xỉ nêu trên, ta định nghĩa các tập BN B  X   BX  BX : B-miền biên của X , U  BX : B-miền ngoài của X.

B-miền biên của X là tập chứa các đối tượng có thể thuộc hoặc không thuộc X, còn B-miền ngoài của X chứa các đối tượng chắc chắn không thuộc X. Sử dụng các lớp của phân hoạch U/B, các xấp xỉ dưới và trên của X có thể viết lại BX  Y U / B Y  X  , BX  Y U / B Y  X  . Trong trường hợp BN B  X    thì X được gọi là tập chính xác (exact set), ngược lại X được gọi là tập thô (rough set). 12 Xét hệ thông tin IS  U , A  với B, D  A , ta gọi B-miền dương của D là tập được xác định như sau POS B ( D)   BX  X U / D Rõ ràng POSB ( D) là tập tất cả các đối tượng u sao cho với mọi v U mà u  B  v  B ta đều có u  D  v  D.

Nói cách khác,  POS B ( D)  u U u B  u D. Hệ thông tin không đầy đủ và mô hình tập thô dung sai Phần này trình bày một số khái niệm cơ bản về mô hình tập thô dung sai trên hệ thông tin không đầy đủ do Kryszkiewicz [67] đề xuất 1. Hệ thông tin không đầy đủ Xét hệ thông tin IS  U , A , nếu tồn tại u U và a  A sao cho a  u  chứa giá trị thiếu (missing value) thì IS được gọi là hệ thông tin không đầy đủ, trái lại IS được gọi là hệ thông tin đầy đủ. Ta biểu diễn giá trị thiếu được ký hiệu là ‘*’ và hệ thông tin không đầy đủ là IIS  U , A .

Mô hình tập thô dung sai Xét hệ thông tin không đầy đủ IIS  U , A  , với tập thuộc tính P, P  A ta định nghĩa một quan hệ nhị phân trên U như sau:   SIM  P    u, v  U U a  P, a  u   a  v   a u   '*'  a  v   '*'. Quan hệ SIM  P  không phải là quan hệ tương đương vì chúng có tính phản xạ, đối xứng nhưng không có tính bắc cầu. Do đó, SIM  P  là một quan hệ dung sai (tolerance relation), hay quan hệ tương tự (similarity relation) trên U. Dễ thấy rằng SIM  P   aP SIM a.

13 Gọi S P  u  là tập v U  u, v   SIM  P . S P  u  là tập lớn nhất các đối tượng không có khả năng phân biệt được với u trên tập thuộc tính P dựa trên quan hệ dung sai, còn gọi là một lớp dung sai hay một hạt thông tin. Ký hiệu tập tất cả các lớp dung sai sinh bởi quan hệ SIM(P) trên U là U / SIM  P  , khi đó các lớp dung sai trong U / SIM  P  không phải là một phân hoạch của U mà hình thành một phủ của U vì chúng có thể giao nhau và uU SP u   U. Cho tập đối tượng X , dựa trên quan hệ dung sai các tập P-xấp xỉ dưới và P-xấp xỉ trên của X trong hệ thông tin không đầy đủ, ký hiệu lần lượt là PX và PX , được xác định như sau    PX  u U S P  u   X  u  X S P  u   X   PX  u U S P  u   X     S u  u U  P Với các tập xấp xỉ nêu trên, ta gọi P-miền biên của X là tập BN P  X   PX  PX , và P-miền ngoài của X là tập U  PX.

Trong trường hợp BN P  X    thì X được gọi là tập chính xác (exact set), ngược lại X được gọi là tập thô dung sai (tolerance rough set). Với P, D  A , ta gọi P-miền dương của D là tập được xác định như sau POS P ( D )   PX  X U / D Rõ ràng POSP ( D) là tập tất cả các đối tượng u sao cho với mọi v  S P  u  ta đều có u  D   v  D . Nói cách khác, POSP ( D)  u U SP  u   u D . Như vậy, mô hình tập thô dung sai là mô hình tập thô mở rộng dựa trên quan hệ dung sai trên các hệ thông tin không đầy đủ với các tập xấp xỉ dưới, xấp xỉ trên được định nghĩa dựa trên quan hệ dung sai.

Bảng quyết định không đầy đủ 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 là một hệ thông tin DS với tập thuộc tính A được chia thành hai tập khác rỗng rời nhau C và D , lần lượt được gọi là tập thuộc tính điều kiện và tập thuộc tính quyết định. Tức là DS  U , C  D  với C  D   .