Phương pháp rút gọn thuộc tính trong bảng quyết định không đầy đủ sử dụng mô hình tập thô dung sai

Khám phá luận án tiến sĩ về rút gọn thuộc tính trong bảng quyết định không đầy đủ với dữ liệu thay đổi theo mô hình tập thô dung sai.

• Tác giả: Nguyễn Anh Tuấn
• Trường học: Đại học Thái Nguyên - Trường Đại học Công nghệ Thông tin và Truyền thông
• Chuyên ngành: Khoa học máy tính
• Đề tài: Rút gọn thuộc tính trong bảng quyết định không đầy đủ với dữ liệu thay đổi: Tiếp cận mô hình tập thô dung sai
• Loại tài liệu: luận án tiến sĩ
• Năm xuất bản: 2022
• Địa điểm: Thái Nguyên

Mục lục chi tiết

• MỤC LỤC
• BẢNG CÁC KÝ HIỆU, TỪ VIẾT TẮT
• DANH MỤC CÁC BẢNG
• DANH MỤC HÌNH VẼ
• MỞ ĐẦU
• 1. TỔNG QUAN VỀ HỆ THÔNG TIN VÀ PHƯƠNG PHÁP RÚT GỌN THUỘC TÍNH THEO TIẾP CẬN TẬP THÔ DUNG SAI
• 1.1. Các khái niệm cơ bản về hệ thông tin
• 1.2. Hệ thông tin đầy đủ và mô hình tập thô truyền thống
• 1.3. Hệ thông tin không đầy đủ và mô hình tập thô dung sai
• 1.4. Phương pháp rút gọn thuộc tính theo tiếp cận tập thô dung sai
• 1.5. Phương pháp rút gọn thuộc tính theo tiếp cận lai ghép lọc - đóng gói
• 1.6. Bài toán phân lớp trong khai phá dữ liệu
• 1.7. Các nghiên cứu liên quan và các vấn đề còn tồn tại
• 1.7.1. Các nghiên cứu liên quan đến rút gọn thuộc tính trong bảng quyết định không đầy đủ
• 1.7.2. Các nghiên cứu liên quan đến rút gọn thuộc tính trong bảng quyết định thay đổi
• 1.7.3. Các vấn đề còn tồn tại và mục tiêu nghiên cứu của luận án
• 1.8. Bộ dữ liệu thực nghiệm
• 1.9. Kết luận chương 1
• 2. PHƯƠNG PHÁP RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ KHI TẬP ĐỐI TƯỢNG THAY ĐỔI
• 2.1. Phương pháp gia tăng tìm tập rút gọn của bảng quyết định không đầy đủ khi bổ sung, loại bỏ tập đối tượng
• 2.2. Thuật toán gia tăng lọc - đóng gói tìm tập rút gọn của bảng quyết định trong trường hợp bổ sung tập đối tượng
• 2.3. Thuật toán gia tăng lọc - đóng gói 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 đối tượng
• 2.4. Phương pháp gia tăng tìm tập rút gọn của bảng quyết định không đầy đủ khi tập đối tượng thay đổi giá trị
• 2.5. Công thức gia tăng tính khoảng cách khi tập đối tượng thay đổi giá trị
• 2.6. Thuật toán gia tăng lọc - đóng gói tìm tập rút gọn của bảng quyết định không đầy đủ khi tập đối tượng thay đổi giá trị
• 2.7. Thực nghiệm, đánh giá thuật toán FWIA_U_Obj
• 2.8. Đánh giá thuật toán FWIA_U_Obj so với việc thực hiện gián tiếp hai thuật toán IDS_IFW_DO và IDS_IFW_AO
• 2.9. Kết luận chương 2
• 3. PHƯƠNG PHÁP RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ KHI TẬP THUỘC TÍNH THAY ĐỔI
• 3.1. Phương pháp gia tăng tìm tập rút gọn của bảng quyết định không đầy đủ khi bổ sung tập thuộc tính
• 3.2. Công thức cập nhật khoảng cách khi bổ sung tập thuộc tính
• 3.3. Thuật toán gia tăng lọc - đóng gói tìm tập rút gọn của bảng quyết định không đầy đủ khi bổ sung tập thuộc tính
• 3.4. Thực nghiệm, đánh giá thuật toán FWIA_AA
• 3.5. Phương pháp gia tăng tìm tập rút gọn của bảng quyết định không đầy đủ khi loại bỏ tập thuộc tính
• 3.6. Công thức gia tăng cập nhật khoảng cách khi loại bỏ tập thuộc tính
• 3.7. Thuật toán gia tăng lọc - đóng gói tìm tập rút gọn của bảng quyết định không đầy đủ khi loại bỏ tập thuộc tính
• 3.8. Thực nghiệm, đánh giá thuật toán FWIA_DA
• 3.9. Phương pháp gia tăng tìm tập rút gọn của bảng quyết định không đầy đủ khi tập thuộc tính thay đổi giá trị
• 3.10. Công thức gia tăng tính khoảng cách khi tập thuộc tính thay đổi giá trị
• 3.11. Thuật toán gia tăng lọc - đóng gói tìm tập rút gọn của bảng quyết định không đầy đủ khi tập thuộc tính thay đổi giá trị
• 3.12. Thực nghiệm, đánh giá thuật toán FWIA_U_Attr
• 3.13. Thực nghiệm, đánh giá thuật toán FWIA_U_Attr so với việc thực hiện gián tiếp hai thuật toán FWIA_DA và FWIA_AA
• 3.14. Kết luận chương 3
• DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC CỦA LUẬN ÁN
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Rút gọn thuộc tính trong bảng quyết định không đầy đủ

Rút gọn thuộc tính là một bài toán quan trọng trong tiền xử lý dữ liệu, đặc biệt trong bối cảnh dữ liệu không đầy đủ. Mục tiêu chính là tìm tập con các thuộc tính, gọi là tập rút gọn, để nâng cao hiệu quả của các mô hình khai phá dữ liệu. Bảng quyết định không đầy đủ thường thiếu giá trị trên miền giá trị của các thuộc tính, gây khó khăn trong việc phân tích. Mô hình tập thô dung sai được đề xuất để giải quyết vấn đề này bằng cách mở rộng quan hệ tương đương trong lý thuyết tập thô truyền thống. Các thuật toán rút gọn thuộc tính dựa trên mô hình này đã được phát triển, tập trung vào việc bảo toàn thông tin và giảm thiểu số lượng thuộc tính.

1.1. Phương pháp rút gọn thuộc tính theo tiếp cận tập thô dung sai

Phương pháp rút gọn thuộc tính theo tiếp cận tập thô dung sai sử dụng các độ đo như khoảng cách, entropy, và ma trận phân biệt để xác định tập rút gọn. Các thuật toán này thường bao gồm hai giai đoạn: lọc và đóng gói. Giai đoạn lọc tìm các ứng viên của tập rút gọn, trong khi giai đoạn đóng gói tối ưu hóa tập rút gọn để đạt độ chính xác phân lớp cao nhất. Các thuật toán như FWIA_U_Obj và FWIA_AA đã được đề xuất để xử lý các trường hợp bổ sung hoặc loại bỏ đối tượng và thuộc tính.

1.2. Các nghiên cứu liên quan và vấn đề tồn tại

Các nghiên cứu trước đây về rút gọn thuộc tính trong bảng quyết định không đầy đủ đã đề xuất nhiều thuật toán dựa trên miền dương, ma trận phân biệt, và entropy. Tuy nhiên, các thuật toán này thường gặp khó khăn khi xử lý dữ liệu thay đổi liên tục. Các vấn đề tồn tại bao gồm chi phí tính toán cao và khả năng mở rộng kém trên các bảng quyết định lớn. Các thuật toán gia tăng đã được đề xuất để giải quyết các vấn đề này, nhưng vẫn cần cải tiến để nâng cao hiệu quả và độ chính xác.

II. Xử lý dữ liệu thay đổi trong bảng quyết định không đầy đủ

Dữ liệu thay đổi là một thách thức lớn trong việc rút gọn thuộc tính, đặc biệt khi bảng quyết định không đầy đủ được cập nhật liên tục. Các thay đổi có thể bao gồm bổ sung hoặc loại bỏ đối tượng, thuộc tính, hoặc thay đổi giá trị của chúng. Các thuật toán gia tăng đã được phát triển để xử lý các thay đổi này mà không cần tính toán lại toàn bộ bảng quyết định. Mô hình tập thô dung sai cung cấp một cách tiếp cận hiệu quả để cập nhật tập rút gọn trong các trường hợp này.

2.1. Phương pháp gia tăng xử lý thay đổi đối tượng

Các thuật toán gia tăng như FWIA_U_Obj được đề xuất để xử lý các thay đổi trong tập đối tượng. Các thuật toán này sử dụng các công thức gia tăng để cập nhật khoảng cách và tìm tập rút gọn mới. Kết quả thực nghiệm cho thấy các thuật toán này giảm thiểu thời gian tính toán và duy trì độ chính xác phân lớp cao. So sánh với các thuật toán truyền thống, các thuật toán gia tăng cho thấy hiệu quả vượt trội trong việc xử lý dữ liệu thay đổi.

2.2. Phương pháp gia tăng xử lý thay đổi thuộc tính

Trong trường hợp thay đổi thuộc tính, các thuật toán như FWIA_AA và FWIA_DA được đề xuất để xử lý việc bổ sung hoặc loại bỏ thuộc tính. Các thuật toán này sử dụng các công thức gia tăng để cập nhật khoảng cách và tìm tập rút gọn mới. Kết quả thực nghiệm cho thấy các thuật toán này giảm thiểu số lượng thuộc tính trong tập rút gọn và nâng cao độ chính xác phân lớp. So sánh với các thuật toán truyền thống, các thuật toán gia tăng cho thấy hiệu quả vượt trội trong việc xử lý dữ liệu thay đổi.

III. Ứng dụng và đánh giá thực nghiệm

Các thuật toán đề xuất đã được thực nghiệm trên các bộ dữ liệu từ kho UCI để đánh giá hiệu quả. Kết quả cho thấy các thuật toán gia tăng theo tiếp cận lọc - đóng gói giảm thiểu số lượng thuộc tính trong tập rút gọn và nâng cao độ chính xác phân lớp. So sánh với các thuật toán truyền thống, các thuật toán gia tăng cho thấy hiệu quả vượt trội trong việc xử lý dữ liệu thay đổi. Các kết quả này khẳng định giá trị thực tiễn của các nghiên cứu trong việc áp dụng vào các bài toán thực tế.

3.1. Đánh giá hiệu quả của các thuật toán gia tăng

Các thuật toán gia tăng như FWIA_U_Obj và FWIA_AA được đánh giá dựa trên số lượng thuộc tính trong tập rút gọn và độ chính xác phân lớp. Kết quả thực nghiệm cho thấy các thuật toán này giảm thiểu số lượng thuộc tính và nâng cao độ chính xác phân lớp so với các thuật toán truyền thống. Các thuật toán này cũng cho thấy khả năng xử lý dữ liệu thay đổi một cách hiệu quả.

3.2. So sánh với các thuật toán truyền thống

So sánh với các thuật toán truyền thống như IDS_IFW_DO và IDS_IFW_AO, các thuật toán gia tăng cho thấy hiệu quả vượt trội trong việc xử lý dữ liệu thay đổi. Các thuật toán gia tăng giảm thiểu thời gian tính toán và duy trì độ chính xác phân lớp cao. Kết quả này khẳng định giá trị thực tiễn của các nghiên cứu trong việc áp dụng vào các bài toán thực tế.

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

chương 1 phân tích các vấn đề còn tồn tại của các nghiên cứu trước đây, từ đó đưa ra các mục tiêu nghiên cứu của luận án. Các khái niệm cơ bản về hệ thông tin 1. Hệ thông tin đầy đủ và mô hình tập thô truyền thống 1.1- Hệ thông tin đầy đủ 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 p cột tương ứng với p thuộc tính và n hàng tương ứng với n đối tượng. Hệ thông tin được định nghĩa như sau: Hệ thông tin là một bộ tứ IS  U , A,V , f  , trong đó: (1) U là tập hữu hạn, khác rỗng các đối tượng; (2) A là tập hữu hạn, khác rỗng các thuộc tính; (3) V  Va với Va là tập giá trị của thuộc tính a  A ; aA (4) f : U  A Va là hàm thông tin, a  A, u U , f u, a  Va.

Với mọi u U , a  A , ta ký hiệu giá trị thuộc tính a tại đối tượng u là a u  thay vì f u, a . Xét hệ thông tin IS  U , A,V , f  , 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  , được xác định như sau: 8   IND  P    u, v  U  U a  P, a  u   a  v  (1.1) Khi đó 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 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 , f  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 có các lớp tương đương của phân hoạch U / B , thế thì một tập đối tượng X có thể biểu diễn thông qua các lớp tương đương này như thế nào? Trong lý thuyết tập thô, để biểu diễn X thông qua các lớp tương đương của U / 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. Với tập X cho trước, tập xấp xỉ dưới BX và xấp xỉ trên BX luôn đi cùng nhau và được sử dụng để xấp xỉ tập hợp trong các bài toán cụ thể. 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.

9 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 BNB  X     BX  X  BX 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). Với B  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   u D B  1.

Bảng quyết định và tập rút gọn 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 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à thuộc tính quyết định, nghĩa là DS  U, C  D với C  D  . Trong bảng quyết định, các thuộc tính điều kiện được phân thành thuộc tính lõi và thuộc tính không cần thiết. Thuộc tính lõi là thuộc tính cốt yếu, là thuộc tính có trong tất cả các tập rút gọn của bảng quyết định và dùng để xây dựng tập rút gọn, mà tập rút gọn liên quan đến phân lớp.

Thuộc tính không cần thiết là thuộc tính dư thừa mà việc loại bỏ thuộc tính này không ảnh hưởng đến việc phân lớp dữ liệu. Các thuộc tính không cần thiết được phân thành hai nhóm: Thuộc tính dư thừa thực sự và thuộc tính rút gọn. Thuộc tính dư thừa thực sự là những thuộc tính dư thừa mà việc loại bỏ tất cả các thuộc tính như vậy không ảnh hưởng đến việc phân lớp dữ liệu. Thuộc tính rút gọn, với một tổ hợp thuộc tính nào đó, nó là thuộc tính dư thừa và với một tổ hợp các thuộc tính khác nó có thể là thuộc tính lõi.1 [62] (Độ quan trọng của thuộc tính dựa trên miền dương) Cho bảng quyết định DS  U , C  D , P C, aP, độ quan trọng của thuộc tính a được xác định: sig  a, P   POS P  D   POS P {a}  D  (1.2) Nếu sig  a, P  0 thì thuộc tính a được gọi là thuộc tính cần thiết.

Nếu sig  a, P  0 thì thuộc tính a được gọi là thuộc tính không cần thiết (dư thừa).2 [62] (Tập rút gọn dựa trên miền dương) Cho bảng quyết định DS  U , C  D. Tập R  C thỏa mãn các điều kiện: 1) POSR (D)  POSC (D) 2) r  R, POSRr (D)  POSC (D) hoặc R '  R, POSR' (D)  POSR (D) thì R là một tập rút gọn của C dựa trên miền dương. Trong định nghĩa này, điều kiện 1) là điều kiện tập rút gọn R bảo toàn độ chắc chắn của các luật phân lớp như tập thuộc tính gốc C; điều kiện 2) đảm bảo để trong tập rút gọn R không chứa thuộc tính nào dư thừa. Tập rút gọn định nghĩa như trên còn được gọi là tập rút gọn Pawlak.

Trong một bảng quyết định có thể có nhiều tập rút gọn, ký hiệu PRED C là họ tất cả các tập rút gọn Pawlak của C. Tập tất cả các thuộc tính cần thiết trong DS được gọi là tập lõi dựa trên miền dương và được ký hiệu là PCORE C  , khi đó: PCORE  C   R RPRED  C  Định nghĩa 1.3 [62] (Thuộc tính rút gọn dựa trên miền dương) Cho bảng quyết định DS  U , C  D , với a C ta nói rằng a là thuộc tính rút gọn của DS nếu tồn tại một tập rút gọn R  PRED C  sao cho a  R. Hệ thông tin không đầy đủ và mô hình tập thô dung sai Nhằm giải quyết bài toán rút gọn thuộc tính trên các hệ quyết định không đầy đủ, Marzena Kryszkiewicz[38] đã 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 và xây dựng mô hình tập thô mở rộng dựa trên quan hệ dung sai gọi là mô hình tập thô dung sai. Hệ thông tin không đầy đủ Cho hệ thông tin IS  U , A,V , f  , nếu tồn tại u U và a  A sao cho a u  thiếu giá trị thì IS được gọi là hệ thông tin không đầy đủ.

Ta biểu diễn giá trị thiếu là ‘*’ và hệ thông tin không đầy đủ là IIS  U , A,V , f . Xét hệ thông tin không đầy đủ IIS  U , A,V , f  với tập thuộc tính 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   '* '  (1.3) 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). Quan hệ SIM  P  được gọi là quan hệ dung sai (tolerance relation) trên U. Theo [38], SIM  P   aP SIM a.

Đặt tập S P  u   v U u , v   SIM  P  khi đó SP u  được gọi là một lớp dung sai. SP u  là tập lớn nhất các đối tượng không có khả năng phân biệt với u trên tập thuộc tính P (tức là v U không có khả năng phân biệt với u, hay u và v có quan hệ dung sai với nhau). 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 .