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

Luận án tiến sĩ nghiên cứu rút gọn thuộc tính trong bảng quyết định không đầy đủ có dữ liệu thay đổi theo tiếp cận mô hình tập, phát triển phương pháp mới, đánh giá hiệu quả ứng

• Tác giả: Nguyễn Anh Tuấn
• Trường học: Trường Đại học Công nghệ Thông tin và Truyền thông - Đại học Thái Nguyên
• 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 đủ có dữ liệu thay đổi theo 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
• 0.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
• 0.1.1. Các khái niệm cơ bản về hệ thông tin
• 0.1.2. Hệ thông tin đầy đủ và mô hình tập thô truyền thống
• 0.1.3. Hệ thông tin không đầy đủ và mô hình tập thô dung sai
• 0.1.4. Phương pháp rút gọn thuộc tính theo tiếp cận tập thô dung sai
• 0.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
• 0.1.6. Bài toán phân lớp trong khai phá dữ liệu
• 0.1.7. Các nghiên cứu liên quan và các vấn đề còn tồn tại
• 0.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 đủ
• 0.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
• 0.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
• 0.1.8. Bộ dữ liệu thực nghiệm
• 0.1.9. Kết luận chương 1
• 1. CHƯƠNG 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
• 2. CHƯƠNG 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. Tổng quan về 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 trong những bước quan trọng trong quá trình khai thác dữ liệu. Đặc biệt, trong bối cảnh dữ liệu không đầy đủ, việc rút gọn thuộc tính trở nên cần thiết hơn bao giờ hết. Mục tiêu chính của việc này là tìm ra tập con của thuộc tính sao cho vẫn bảo toàn được thông tin cần thiết. Các phương pháp rút gọn thuộc tính đã được nghiên cứu và phát triển để giải quyết vấn đề này, đặc biệt là trong các bảng quyết định không đầy đủ.

1.1. Khái niệm về bảng quyết định không đầy đủ

Bảng quyết định không đầy đủ là bảng mà trong đó một số giá trị thuộc tính bị thiếu. Điều này gây khó khăn trong việc phân tích và khai thác dữ liệu. Việc hiểu rõ về bảng quyết định không đầy đủ là bước đầu tiên để áp dụng các phương pháp rút gọn thuộc tính hiệu quả.

1.2. Tầm quan trọng của việc rút gọn thuộc tính

Rút gọn thuộc tính giúp giảm thiểu độ phức tạp của mô hình, từ đó nâng cao hiệu quả phân lớp. Việc loại bỏ các thuộc tính dư thừa không chỉ tiết kiệm thời gian tính toán mà còn cải thiện độ chính xác của các mô hình khai thác dữ liệu.

II. Thách thức trong việc rút gọn thuộc tính với dữ liệu thay đổi

Dữ liệu thay đổi thường xuyên là một thách thức lớn trong việc rút gọn thuộc tính. Khi dữ liệu được cập nhật, các thuộc tính có thể thay đổi, dẫn đến việc cần phải tính toán lại tập rút gọn. Điều này không chỉ tốn thời gian mà còn có thể làm giảm độ chính xác của mô hình.

2.1. Các loại thay đổi trong dữ liệu

Dữ liệu có thể thay đổi theo nhiều cách, bao gồm bổ sung hoặc loại bỏ đối tượng và thuộc tính. Mỗi loại thay đổi này đều yêu cầu các phương pháp rút gọn thuộc tính khác nhau để đảm bảo tính chính xác và hiệu quả.

2.2. Tác động của thay đổi dữ liệu đến mô hình

Khi dữ liệu thay đổi, các mô hình phân lớp có thể bị ảnh hưởng nghiêm trọng. Việc không cập nhật kịp thời các thuộc tính có thể dẫn đến việc mô hình không còn chính xác, do đó cần có các phương pháp gia tăng để xử lý vấn đề này.

III. 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 đã được chứng minh là hiệu quả trong việc xử lý bảng quyết định không đầy đủ. Phương pháp này sử dụng các khái niệm từ lý thuyết tập thô để xác định các thuộc tính cần thiết và loại bỏ các thuộc tính dư thừa.

3.1. Nguyên lý của phương pháp tập thô dung sai

Nguyên lý của phương pháp này dựa trên việc xác định các quan hệ dung sai giữa các thuộc tính. Điều này cho phép xác định được các thuộc tính không cần thiết mà vẫn bảo toàn được thông tin quan trọng.

3.2. Ứng dụng của phương pháp trong thực tiễn

Phương pháp này đã được áp dụng thành công trong nhiều lĩnh vực, từ y tế đến tài chính, giúp cải thiện độ chính xác của các mô hình phân lớp và giảm thiểu thời gian tính toán.

IV. Kết quả nghiên cứu và ứng dụng thực tiễn

Nghiên cứu đã chỉ ra rằng việc áp dụng các phương pháp rút gọn thuộc tính theo tiếp cận tập thô dung sai có thể cải thiện đáng kể hiệu quả của các mô hình phân lớp. Các kết quả thực nghiệm cho thấy độ chính xác của mô hình tăng lên khi sử dụng các tập rút gọn được xác định chính xác.

4.1. Kết quả thực nghiệm với dữ liệu không đầy đủ

Các thử nghiệm cho thấy rằng các thuật toán rút gọn thuộc tính có thể giảm thiểu số lượng thuộc tính mà vẫn duy trì độ chính xác cao trong phân lớp. Điều này chứng tỏ tính khả thi của phương pháp trong thực tế.

4.2. Ứng dụng trong các lĩnh vực khác nhau

Phương pháp rút gọn thuộc tính đã được áp dụng trong nhiều lĩnh vực như y tế, tài chính và marketing, giúp cải thiện hiệu quả phân tích dữ liệu và ra quyết định.

V. Kết luận và triển vọng tương lai của nghiên cứu

Nghiên cứu 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 mở ra nhiều hướng đi mới cho các nghiên cứu tiếp theo. Việc phát triển các thuật toán gia tăng hiệu quả hơn sẽ là một trong những mục tiêu chính trong tương lai.

5.1. Hướng 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 cải thiện các thuật toán hiện tại, nhằm giảm thiểu thời gian tính toán và nâng cao độ chính xác của mô hình.

5.2. Tác động của công nghệ mới

Sự phát triển của công nghệ mới như trí tuệ nhân tạo và học máy có thể tạo ra những cơ hội mới trong việc rút gọn thuộc tính, mở rộng khả năng ứng dụng của các phương pháp này trong thực tiễn.

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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.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 LUAN VAN CHAT LUONG download : add [e-mail] 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.

10 LUAN VAN CHAT LUONG download : add [e-mail] Định nghĩa 1.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. 11 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.

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. 12 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.