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.

Nội dung chính

Tổng quan luận án

Trong bối cảnh phát triển của cuộc cách mạng công nghiệp lần thứ tư, nhu cầu thu thập, lưu trữ và xử lý các tập dữ liệu có dung lượng lớn, cấu trúc phức tạp, chứa giá trị không đầy đủ và không chắc chắn ngày càng gia tăng. Trong quy trình khai phá dữ liệu, rút gọn thuộc tính ở giai đoạn tiền xử lý đóng vai trò loại bỏ các thuộc tính dư thừa nhằm giảm chiều dữ liệu và nâng cao chất lượng của các mô hình phân lớp. Lý thuyết tập thô do Pawlak đề xuất năm 1982 cung cấp công cụ hiệu quả cho các bảng quyết định đầy đủ. Đối với các bảng quyết định thiếu giá trị (bảng quyết định không đầy đủ - Incomplete Decision Table, ký hiệu IDS), việc tiền xử lý điền giá trị thiếu có thể gây sai lệch thông tin; do đó, mô hình tập thô dung sai của Kryszkiewicz đã được ứng dụng để xử lý trực tiếp thông qua quan hệ dung sai.

Mặt khác, trong các ứng dụng thực tế như hệ thống dữ liệu trực tuyến hay tin sinh học, dữ liệu thường xuyên biến động theo thời gian dưới các kịch bản: bổ sung hoặc loại bỏ đối tượng, bổ sung hoặc loại bỏ thuộc tính, và các đối tượng hoặc thuộc tính thay đổi giá trị. Việc tính toán lại tập rút gọn từ đầu trên toàn bộ bảng quyết định sau mỗi lần cập nhật đòi hỏi chi phí thời gian tính toán rất lớn. Các phương pháp gia tăng đã được đề xuất nhằm cập nhật tập rút gọn dựa trên việc tận dụng kết quả tính toán trước đó. Tuy nhiên, phần lớn các thuật toán gia tăng hiện hữu trên mô hình tập thô dung sai đều tiếp cận theo hướng lọc (filter) truyền thống, tức là việc đánh giá độ chính xác phân lớp được thực hiện độc lập sau khi đã tìm được tập rút gọn. Hạn chế của tiếp cận lọc là tiêu chuẩn đánh giá không phản ánh trực tiếp độ chính xác của mô hình học máy, dẫn đến tập rút gọn tìm được chưa tối ưu về số lượng thuộc tính và chất lượng phân lớp.

Luận án của tác giả Nguyễn Anh Tuấn tập trung giải quyết khoảng trống nghiên cứu trên thông qua hai mục tiêu chính:

1. Thứ nhất: Nghiên cứu tập đối tượng thay đổi:
   • Nghiên cứu các thuật toán gia tăng lọc - đóng gói tìm tập rút gọn trong trường hợp bổ sung, loại bỏ tập đối tượng.
   • Nghiên cứu, đề xuất 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 đủ thay đổi trong trường hợp tập đối tượng thay đổi giá trị. Đánh giá tính hiệu quả và so sánh hướng tiếp cận trực tiếp với hướng tiếp cận gián tiếp (thực hiện liên tiếp việc loại bỏ rồi bổ sung tập đối tượng).
2. Thứ hai: Nghiên cứu tập thuộc tính thay đổi:
   • Nghiên cứu, xây dựng thuật toán gia tăng lọc - đóng gói tìm tập rút gọn trong trường hợp bổ sung, loại bỏ tập thuộc tính.
   • Nghiên cứu, đề xuất 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 đủ thay đổi trong trường hợp tập thuộc tính thay đổi giá trị. Đánh giá tính hiệu quả và so sánh hướng tiếp cận trực tiếp với hướng tiếp cận gián tiếp (thực hiện liên tiếp việc loại bỏ rồi bổ sung tập thuộc tính).

Đối tượng nghiên cứu của luận án là các bảng quyết định không đầy đủ thay đổi trong các trường hợp: bổ sung, loại bỏ tập đối tượng, tập thuộc tính và tập đối tượng, tập thuộc tính thay đổi giá trị. Phạm vi nghiên cứu giới hạn ở các phương pháp rút gọn thuộc tính trên bảng quyết định không đầy đủ theo tiếp cận mô hình tập thô dung sai phục vụ bài toán phân lớp dữ liệu trong khai phá dữ liệu.

Tổng quan tài liệu và vị trí của luận án

Lý thuyết tập thô được Pawlak đề xuất năm 1982 dựa trên quan hệ tương đương (quan hệ không phân biệt được IND) để phân hoạch không gian đối tượng trên hệ thông tin đầy đủ. Để xử lý hệ thông tin không đầy đủ chứa các giá trị thiếu (ký hiệu là *), Kryszkiewicz (1998, 1999) đã mở rộng quan hệ tương đương thành quan hệ dung sai (tolerance relation SIM), từ đó hình thành mô hình tập thô dung sai. Trên cơ sở mô hình này, nhiều phương pháp rút gọn thuộc tính cho bảng quyết định không đầy đủ cố định đã được phát triển dựa trên các tiêu chuẩn đo lường khác nhau:

• Nhóm thuật toán dựa trên miền dương do Qian, Liang (2006), Wang (2002), Yang (2007) nghiên cứu.
• Nhóm thuật toán dựa trên ma trận phân biệt và ma trận phân biệt mở rộng do Kryszkiewicz (1998), Xu (2007), Nguyen (2008) thực hiện.
• Nhóm thuật toán dựa trên tập xấp xỉ thô của Chen (2011), Dai (2012).
• Nhóm thuật toán dựa trên entropy thông tin và lượng thông tin của Guan (2005), Qian (2007), Sun (2014), Dai (2013).
• Nhóm thuật toán dựa trên độ đo khoảng cách của Chen (2010), Dai (2012).

Đối với các bảng quyết định thay đổi dữ liệu, nhiều thuật toán gia tăng đã được công bố:

• Trên bảng quyết định đầy đủ: Các nghiên cứu giải quyết kịch bản bổ sung/loại bỏ đối tượng sử dụng khoảng cách (Chen 2011), miền dương (Chen 2009, 2010), ma trận phân biệt (Lang 2009, Li 2007, 2017), hạt thông tin (Jing 2017), entropy thông tin (Shu 2013), hàm thành viên (Sajjad 2017). Trường hợp bổ sung/loại bỏ thuộc tính sử dụng entropy thông tin (Suh 2001), ma trận phân biệt (Wang 2008), tập thô mờ (Yang 2017). Trường hợp thay đổi giá trị đối tượng hoặc thuộc tính sử dụng ma trận phân biệt (Li 2018), hạt thông tin (Jing 2017, Li 2014), entropy thông tin (Shu 2014).
• Trên bảng quyết định không đầy đủ theo tiếp cận tập thô dung sai:
  • Trường hợp bổ sung và loại bỏ đối tượng: Yang và cộng sự (2012) sử dụng hàm quyết định suy rộng; Liu và cộng sự (2016) đề xuất ma trận độ chính xác và bao phủ; Wang và cộng sự (2019) sử dụng entropy trọng số; Shu và cộng sự (2015) đề xuất hai thuật toán IARM-I và IARM-E dựa trên miền dương; Zhang và cộng sự (2020) đề xuất hai thuật toán KGIRA-M và KGIRD-M dựa trên độ đo hạt tri thức.
  • Trường hợp bổ sung và loại bỏ thuộc tính: Shu và cộng sự (2014) đề xuất UARA và UARD cập nhật dựa trên miền dương; Chen và cộng sự (2019) đề xuất thuật toán IDRA dựa trên quan hệ phân biệt được.
  • Trường hợp đối tượng và thuộc tính thay đổi giá trị: Shu và cộng sự (2014) đề xuất thuật toán FSMV dựa trên việc cập nhật miền dương khi đối tượng thay đổi giá trị; Xie và cộng sự (2018) đề xuất thuật toán Object-R (khi đối tượng thay đổi giá trị) và Attribute-R (khi thuộc tính thay đổi giá trị) dựa trên độ đo không nhất quán.

Khoảng trống nghiên cứu được luận án chỉ ra bao gồm:

1. Tất cả các thuật toán gia tăng đã công bố nêu trên cho bảng quyết định không đầy đủ (IARM-I, IARM-E, KGIRA-M, KGIRD-M, UARA, UARD, IDRA, FSMV, Object-R, Attribute-R) đều thực hiện theo tiếp cận lọc truyền thống. Các thuật toán này chọn tập rút gọn bảo toàn độ đo lý thuyết nhưng chưa gắn với độ chính xác của giải thuật học máy phân lớp.
2. Hướng tiếp cận lai ghép lọc - đóng gói (filter - wrapper) sử dụng độ đo khoảng cách đã bước đầu được xem xét trong một số công bố: bổ sung đối tượng (Đỗ Văn Nhơn, Nguyễn Anh Tuấn, 2016, 2017), bổ sung thuộc tính (Nguyễn Anh Tuấn, Đỗ Văn Nhơn, 2018). Tuy nhiên, trường hợp loại bỏ tập đối tượng chưa được tiến hành thực nghiệm so sánh; trường hợp bổ sung tập đối tượng mới chỉ so sánh với thuật toán từ năm 2015 (IARM-I) mà chưa so sánh với thuật toán công bố năm 2020 (KGIRA-M).
3. Trong trường hợp tập thuộc tính thay đổi, công thức tính khoảng cách trước đây chưa sử dụng phương pháp cập nhật gia tăng thuần nhất cho phần dữ liệu thay đổi; kịch bản loại bỏ thuộc tính chưa được giải quyết đầy đủ theo tiếp cận lọc - đóng gói.
4. Chưa có nghiên cứu nào phát triển thuật toán gia tăng theo hướng lai ghép lọc - đóng gói cho trường hợp đối tượng thay đổi giá trị và thuộc tính thay đổi giá trị trên bảng quyết định không đầy đủ; đồng thời chưa có thực nghiệm so sánh giữa phương pháp xử lý trực tiếp sự thay đổi giá trị với phương pháp xử lý gián tiếp (kết hợp hai thao tác loại bỏ và bổ sung liên tiếp).

Cơ sở lý thuyết và phương pháp nghiên cứu

Luận án xây dựng trên các nền tảng lý thuyết và khái niệm toán học hình thức:

• Hệ thông tin (Information System - IS): Được định nghĩa là bộ tứ $IS = (U, A, V, f)$, trong đó $U$ là tập hữu hạn các đối tượng, $A$ là tập hữu hạn các thuộc tính, $V = \bigcup_{a \in A} V_a$ là miền giá trị, và $f: U \times A \to V$ là hàm thông tin. Khi thuộc tính được phân tách thành tập thuộc tính điều kiện $C$ và thuộc tính quyết định $D$ ($C \cap D = \emptyset$), ta có bảng quyết định $DS = (U, C \cup D)$.
• Hệ thông tin không đầy đủ (IIS) và Bảng quyết định không đầy đủ (IDS): Khi tồn tại đối tượng $u \in U$ và thuộc tính $a \in A$ sao cho giá trị $a(u)$ bị thiếu (ký hiệu là *), hệ thống được gọi là không đầy đủ. Bảng quyết định không đầy đủ có dạng $IDS = (U, C \cup D)$ với thuộc tính quyết định $d \in D$ không chứa giá trị thiếu.
• Quan hệ dung sai (Tolerance Relation - SIM): Cho tập thuộc tính $P \subseteq C$, quan hệ dung sai $SIM(P)$ trên $U$ xác định bởi: $$(u, v) \in SIM(P) \Leftrightarrow \forall a \in P, a(u) = a(v) \lor a(u) = '' \lor a(v) = ''$$ Quan hệ dung sai có tính phản xạ và đối xứng nhưng không có tính bắc cầu. Lớp dung sai của $u$ trên $P$ là $S_P(u) = {v \in U \mid (u, v) \in SIM(P)}$. Tập các lớp dung sai tạo thành một phủ của $U$. Ma trận dung sai $M(P) = (p_{ij}){n \times n}$ có phần tử $p{ij} = 1$ nếu $u_j \in S_P(u_i)$ và $p_{ij} = 0$ nếu ngược lại.
• Khoảng cách giữa hai tập thuộc tính: Dựa trên ma trận dung sai $M(C) = (c_{ij}){n \times n}$ và $M(d) = (d{ij}){n \times n}$, khoảng cách giữa $C$ và $C \cup {d}$ được tính theo công thức: $$D(C, C \cup {d}) = \frac{1}{n^2} \sum{i=1}^n \sum_{j=1}^n (c_{ij} - c_{ij} \cdot d_{ij})$$ Độ quan trọng của thuộc tính $b \in C \setminus B$ đối với tập $B \subseteq C$ xác định bởi: $$SIG_B(b) = D(B, B \cup {d}) - D(B \cup {b}, B \cup {b} \cup {d})$$
• Khung phân tích lai ghép lọc - đóng gói (Filter - Wrapper):
  • Giai đoạn lọc (Filter): Sử dụng độ quan trọng của thuộc tính dựa trên độ đo khoảng cách để lần lượt chọn thuộc tính tối ưu theo giải thuật tìm kiếm tham lam (heuristic), sinh ra danh sách các tập con ứng viên của tập rút gọn.
  • Giai đoạn đóng gói (Wrapper): Chạy thuật toán phân lớp C4.5 kết hợp kỹ thuật đánh giá kiểm tra chéo 10-fold trên từng tập ứng viên, chọn tập con có độ chính xác phân lớp trung bình cao nhất làm tập rút gọn cuối cùng ($R_{best}$).

Phương pháp nghiên cứu kết hợp giữa nghiên cứu lý thuyết toán học (thiết lập các công thức cập nhật gia tăng ma trận dung sai, chứng minh tính bảo toàn quan hệ dung sai) và nghiên cứu thực nghiệm mô phỏng trên máy tính cá nhân (Intel Core i7-3770, 3.40 GHz, RAM hệ thống, hệ điều hành Windows 7, môi trường tính toán Matlab).

Nguồn dữ liệu thực nghiệm được lấy từ kho dữ liệu chuẩn của Đại học California tại Irvine (UCI Machine Learning Repository), gồm 06 bộ dữ liệu mẫu có các tỷ lệ missing khác nhau:

1. Audiology.data: 226 đối tượng, 69 thuộc tính điều kiện, 24 lớp quyết định.
2. Soybean-large.data: 307 đối tượng, 35 thuộc tính điều kiện, 2 lớp quyết định.
3. house-votes-84.data: 435 đối tượng, 16 thuộc tính điều kiện, 2 lớp quyết định.
4. Bridges2.data: 108 đối tượng, 11 thuộc tính điều kiện, 6 lớp quyết định.
5. Lymphography.data: 148 đối tượng, 18 thuộc tính điều kiện, 4 lớp quyết định.
6. Primary-tumor.data: 339 đối tượng, 17 thuộc tính điều kiện, 21 lớp quyết định.

Nội dung chính theo từng chương

Chương 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

Chương này trình bày các khái niệm nền tảng về hệ thông tin đầy đủ, hệ thông tin không đầy đủ, quan hệ tương đương, quan hệ dung sai, các tập xấp xỉ thô (xấp xỉ trên, xấp xỉ dưới, miền biên, miền dương). Tác giả làm rõ cấu trúc bài toán phân lớp dữ liệu có giám sát, tiến trình sinh luật quyết định và ba độ đo đánh giá hiệu năng tập luật của Qian Y. và cộng sự (2007) gồm: độ chắc chắn $\alpha(DS)$, độ nhất quán $\gamma(DS)$ và độ hỗ trợ $s(DS)$. Công thức độ chính xác phân lớp (Accuracy) được định nghĩa dựa trên tỷ lệ giữa số mẫu dự đoán đúng và tổng số mẫu thử nghiệm.

Nội dung chương phân tích chi tiết quy trình lựa chọn thuộc tính gồm bốn thành phần: thủ tục sinh tập con thuộc tính (generation), hàm tiêu chuẩn đánh giá (evaluation), tiêu chuẩn dừng (stopping criteria) và thủ tục kiểm tra kết quả (validation). Tác giả so sánh hai chiến lược tìm kiếm: tiếp cận từ dưới lên (bắt đầu từ tập rỗng/tập lõi và bổ sung thuộc tính) và tiếp cận từ trên xuống (bắt đầu từ toàn bộ tập thuộc tính và loại bỏ dần). Đồng thời, chương 1 đối chiếu ưu nhược điểm giữa phương pháp tiếp cận lọc (độc lập với giải thuật học nhưng kết quả phân lớp có thể không cao) và tiếp cận đóng gói (gắn với giải thuật phân lớp, độ chính xác cao nhưng chi phí tính toán lớn), từ đó xác lập tính hợp lý của phương pháp lai ghép lọc - đóng gói.

| STT | Tập dữ liệu | Số đối tượng (|O|) | Số thuộc tính điều kiện (|A|) | Số lớp quyết định (|k|) | | :--- | :--- | :---: | :---: | :---: | | 1 | Audiology.data | 226 | 69 | 24 | | 2 | Soybean-large.data | 307 | 35 | 2 | | 3 | house-votes-84.data | 435 | 16 | 2 | | 4 | Bridges2.data | 108 | 11 | 6 | | 5 | Lymphography.data | 148 | 18 | 4 | | 6 | Primary-tumor.data | 339 | 17 | 21 |

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

Chương này tập trung giải quyết bài toán rút gọn thuộc tính gia tăng khi tập đối tượng biến động:

1. Trường hợp bổ sung tập đối tượng: Giả sử bổ sung tập đối tượng $\Delta U = {u_{n+1}, u_{n+2}, \dots, u_{n+s}}$ vào $U$ ($s \ge 1$). Ma trận dung sai mới có kích thước $(n+s) \times (n+s)$. Công thức cập nhật khoảng cách gia tăng $D_{U \cup \Delta U}(C, C \cup {d})$ được xác định như sau: $$D_{U \cup \Delta U}(C, C \cup {d}) = \frac{n^2}{(n+s)^2} D_U(C, C \cup {d}) + \frac{2}{(n+s)^2} \sum_{i=n+1}^{n+s} \sum_{j=1}^i (c_{ij} - c_{ij} \cdot d_{ij})$$ Định lý chứng minh rằng nếu $S_R(u_{n+i}) \subseteq S_{{d}}(u_{n+i})$ với mọi $i = 1, \dots, s$ thì tập rút gọn $R$ không thay đổi. Thuật toán IDS_IFW_AO được mô tả gồm hai pha: pha lọc sử dụng công thức gia tăng tính $SIG_R(r)$ để chọn tập các ứng viên $T$, và pha đóng gói sử dụng bộ phân lớp C4.5 đánh giá kiểm tra chéo 10-fold để tìm $R_{best}$. Độ phức tạp của thuật toán là $O(|C|^2 \cdot (|U| + |\Delta U|)^2) + O(|C| \cdot f(n))$.

STT	Tập dữ liệu	Kịch bản dữ liệu	IDS_IFW_AO |R|	IDS_IFW_AO Acc (%)	IARM-I |R|	IARM-I Acc (%)	KGIRA-M |R|	KGIRA-M Acc (%)
1	Audiology.data	$O_{ori}$	5	76.16	13	71.24	10	73.45
		$O_{ori} \cup O_1$	5	77.20	14	70.15	11	74.50
		$O_{ori} \cup \dots \cup O_5$	6	78.32	15	71.68	11	75.22
2	Soybean-large	$O_{ori}$	4	88.54	11	82.17	8	85.35
		$O_{ori} \cup O_1$	4	89.21	12	81.56	8	86.10
		$O_{ori} \cup \dots \cup O_5$	5	90.12	13	82.74	9	87.30

Thực nghiệm cho thấy IDS_IFW_AO tìm được số lượng thuộc tính rút gọn ít hơn đáng kể so với hai thuật toán lọc IARM-I và KGIRA-M, đồng thời nâng cao độ chính xác phân lớp trung bình. Tuy nhiên, thời gian chạy của IDS_IFW_AO lớn hơn do phải huấn luyện phân lớp ở pha đóng gói (ví dụ ở bộ Audiology.data chạy toàn bộ, tổng thời gian của IDS_IFW_AO là 6.31 giây, cao hơn so với tiếp cận lọc).

2. Trường hợp loại bỏ tập đối tượng: Khi tập đối tượng $\Delta U = {u_k, \dots, u_{k+s-1}}$ bị loại bỏ ($0 < s < n$), công thức cập nhật khoảng cách gia tăng $D_{U \setminus \Delta U}(C, C \cup {d})$ được xây dựng. Tác giả chứng minh điều kiện: nếu $S_B(u_i) \subseteq S_{{d}}(u_i)$ với mọi $i = k, \dots, k+s-1$ thì tập rút gọn $B$ giữ nguyên. Thuật toán IDS_IFW_DO được thiết kế tương tự với độ phức tạp $O(|C|^2 \cdot (|U| - |\Delta U|)^2) + O(|C| \cdot f(n))$. Thực nghiệm so sánh với IARM-E và KGIRD-M chứng minh IDS_IFW_DO duy trì số thuộc tính rút gọn tối thiểu và độ chính xác phân lớp ổn định hơn.

3. Trường hợp tập đối tượng thay đổi giá trị: Tác giả xây dựng công thức cập nhật khoảng cách trực tiếp khi tập đối tượng thay đổi giá trị và thiết kế thuật toán FWIA_U_Obj. Thực nghiệm so sánh FWIA_U_Obj với hai thuật toán lọc FSMV (Shu, 2014) và Object-R (Xie, 2018). Đồng thời, tác giả so sánh việc thực hiện trực tiếp thuật toán FWIA_U_Obj với việc thực hiện gián tiếp hai thuật toán (IDS_IFW_DO để xóa các đối tượng cũ, sau đó chạy IDS_IFW_AO để nạp các đối tượng có giá trị mới). Kết quả chỉ ra rằng xử lý trực tiếp bằng FWIA_U_Obj có chi phí thời gian thấp hơn và tập thuộc tính rút gọn cô đọng hơn so với thực hiện gián tiếp qua hai bước.

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

Chương này giải quyết các biến động về tập thuộc tính điều kiện trong bảng quyết định không đầy đủ:

1. Trường hợp bổ sung tập thuộc tính: Khi bảng quyết định được bổ sung tập thuộc tính điều kiện $\Delta C$, ma trận dung sai được cập nhật dựa trên phép nhân từng phần tử của ma trận dung sai cũ và ma trận dung sai của tập thuộc tính bổ sung: $s_{ij} = p_{ij} \cdot q_{ij}$. Tác giả đề xuất công thức cập nhật khoảng cách gia tăng và xây dựng thuật toán lai ghép lọc - đóng gói FWIA_AA. Thực nghiệm trên các tập dữ liệu UCI chứng minh FWIA_AA cho kích thước tập rút gọn nhỏ hơn và độ chính xác phân lớp vượt trội so với hai thuật toán lọc UARA (Shu và cộng sự) và IDRA (Chen và cộng sự).
2. Trường hợp loại bỏ tập thuộc tính: Khi tập thuộc tính $\Delta C$ bị loại bỏ khỏi bảng quyết định, quan hệ dung sai của các thuộc tính còn lại được mở rộng. Luận án xây dựng công thức cập nhật khoảng cách gia tăng khi loại bỏ thuộc tính, thiết lập sơ đồ khối xử lý và thuật toán FWIA_DA. Kết quả thực nghiệm so sánh với thuật toán lọc UARD cho thấy FWIA_DA đạt độ chính xác phân lớp cao hơn và giảm thiểu thuộc tính dư thừa.
3. Trường hợp tập thuộc tính thay đổi giá trị: Tác giả xây dựng công thức gia tăng tính khoảng cách khi có sự thay đổi giá trị của tập thuộc tính, đề xuất thuật toán lai ghép lọc - đóng gói FWIA_U_Attr. Thực nghiệm đối sánh với thuật toán lọc Attribute-R (Xie và cộng sự) khẳng định tính ưu việt của mô hình lai ghép về độ chính xác phân lớp. Tiếp tục phân tích so sánh thực nghiệm giữa phương pháp tiếp cận trực tiếp FWIA_U_Attr với phương pháp gián tiếp (thực hiện tuần tự FWIA_DA để loại bỏ thuộc tính cũ rồi gọi FWIA_AA để bổ sung thuộc tính mới cập nhật) cho thấy thuật toán trực tiếp FWIA_U_Attr tiết kiệm thời gian tính toán và giảm thiểu số lượng thuộc tính trong tập rút gọn.

Kết quả và những đóng góp mới

Theo công bố của tác giả trong luận án, công trình đạt được ba kết quả đóng góp mới chính về mặt lý luận và thực tiễn:

1. Xây dựng công thức gia tăng cập nhật độ đo khoảng cách trong các trường hợp bổ sung và loại bỏ tập thuộc tính trên bảng quyết định không đầy đủ; trên cơ sở đó đề xuất và cài đặt thành công hai thuật toán gia tăng lai ghép lọc - đóng gói FWIA_AA (bổ sung thuộc tính) và FWIA_DA (loại bỏ thuộc tính).
2. Đề xuất công thức gia tăng cập nhật độ đo khoảng cách khi tập đối tượng thay đổi giá trị; trên cơ sở đó xây dựng thuật toán gia tăng lai ghép lọc - đóng gói FWIA_U_Obj tìm tập rút gọn của bảng quyết định không đầy đủ khi đối tượng thay đổi giá trị. Minh chứng thực nghiệm khẳng định tiếp cận trực tiếp hiệu quả hơn tiếp cận gián tiếp (thực hiện xóa rồi thêm đối tượng).
3. Đề xuất công thức gia tăng cập nhật độ đo khoảng cách khi tập thuộc tính thay đổi giá trị; trên cơ sở đó xây dựng thuật toán gia tăng lai ghép lọc - đóng gói FWIA_U_Attr tìm tập rút gọn của bảng quyết định không đầy đủ khi thuộc tính thay đổi giá trị. Minh chứng thực nghiệm xác nhận tính ưu việt của giải pháp trực tiếp so với giải pháp gián tiếp (thực hiện xóa rồi thêm thuộc tính).

Về mặt giải pháp đề xuất: Luận án khuyến nghị sử dụng kỹ thuật gia tăng lai ghép lọc - đóng gói dựa trên ma trận dung sai cho các bài toán phân lớp dữ liệu lớn có giá trị thiếu, thay vì chỉ sử dụng các thuật toán lọc đơn thuần nhằm đảm bảo chất lượng phân loại tối ưu.

Hạn chế và hướng nghiên cứu tiếp

Văn bản luận án đề cập một số điểm hạn chế và định hướng nghiên cứu tiếp nối:

• Hạn chế chính của các thuật toán đề xuất (IDS_IFW_AO, IDS_IFW_DO, FWIA_U_Obj, FWIA_AA, FWIA_DA, FWIA_U_Attr) nằm ở thời gian thực thi: do ở giai đoạn đóng gói (wrapper) phải gọi mô hình học máy C4.5 kết hợp kỹ thuật kiểm tra chéo 10-fold nhiều lần để đánh giá từng tập ứng viên, tổng thời gian tính toán của các thuật toán này cao hơn các thuật toán tiếp cận lọc thuần túy (IARM-I, KGIRA-M, UARA, Object-R, Attribute-R).
• Về phạm vi dữ liệu: Luận án mới chỉ dừng lại ở việc kiểm thử trên 06 bộ dữ liệu mẫu tĩnh được chia nhỏ từ kho dữ liệu UCI để giả lập quá trình biến động gia tăng; chưa kiểm thử trên các dòng dữ liệu (data stream) phân tán theo thời gian thực.
• Hướng nghiên cứu tiếp:
  • Nghiên cứu các giải pháp tối ưu hóa thời gian thực thi trong giai đoạn đóng gói, có thể kết hợp các kỹ thuật song song hóa tính toán ma trận dung sai.
  • Mở rộng phương pháp sang các mô hình tập thô mờ, tập thô trực giác hoặc tập thô bao phủ khi dữ liệu vừa không đầy đủ vừa chứa thuộc tính liên tục chưa qua tiền xử lý rời rạc hóa.
  • Thử nghiệm với các bộ phân lớp khác (như SVM, Random Forest) ngoài giải thuật C4.5.

Giá trị tham khảo

Luận án có giá trị tham khảo chuyên môn đối với các nhóm đối tượng:

• Nghiên cứu sinh, học viên cao học và giảng viên ngành Khoa học máy tính, Hệ thống thông tin, Trí tuệ nhân tạo: Bản luận án cung cấp hệ thống chứng minh toán học chặt chẽ về quan hệ dung sai, các công thức tính khoảng cách ma trận và phương pháp thiết kế thuật toán gia tăng lai ghép lọc - đóng gói.
• Kỹ sư dữ liệu và chuyên gia phân tích dữ liệu: Có thể ứng dụng trực tiếp mã giả và nguyên lý của các thuật toán FWIA_U_Obj, FWIA_AA, FWIA_DA, FWIA_U_Attr trong việc thiết kế mô-đun tiền xử lý dữ liệu tự động cho các hệ thống thông tin thường xuyên cập nhật bản ghi hoặc bổ sung trường thuộc tính mới.
• Phần đáng tham khảo nhất: Các định lý về điều kiện giữ nguyên tập rút gọn và các công thức cập nhật gia tăng ma trận khoảng cách ở Chương 2 và Chương 3, giúp giảm thiểu độ phức tạp tính toán từ việc tính lại toàn bộ xuống chỉ tính toán trên phần dữ liệu sai khác.

Câu hỏi thường gặp

1. Tại sao luận án sử dụng mô hình tập thô dung sai thay cho mô hình tập thô truyền thống của Pawlak? Trong bảng quyết định không đầy đủ, dữ liệu chứa các giá trị thiếu (ký hiệu là *). Mô hình tập thô truyền thống dựa trên quan hệ tương đương đòi hỏi tính bắc cầu, không thể áp dụng trực tiếp nếu không qua bước điền giá trị thiếu (imputation). Mô hình tập thô dung sai của Kryszkiewicz thay thế quan hệ tương đương bằng quan hệ dung sai (có tính phản xạ, đối xứng nhưng không bắc cầu), cho phép xử lý và khai phá tri thức trực tiếp trên dữ liệu khuyết thiếu mà không làm biến dạng thông tin gốc.

2. Điểm khác biệt cốt lõi giữa tiếp cận lọc thuần túy và tiếp cận lai ghép lọc - đóng gói trong luận án là gì? Tiếp cận lọc (filter) thuần túy đánh giá độ quan trọng của thuộc tính độc lập với thuật toán học máy (chỉ dựa vào các độ đo lý thuyết như miền dương, hạt tri thức, entropy) nên tốc độ nhanh nhưng tập rút gọn thu được có thể không đạt độ chính xác phân lớp tối ưu. Tiếp cận lai ghép lọc - đóng gói (filter - wrapper) kết hợp cả hai: giai đoạn lọc sử dụng độ đo khoảng cách dung sai để chọn ra danh sách các tập ứng viên tiềm năng, sau đó giai đoạn đóng gói gọi trực tiếp bộ phân lớp C4.5 để kiểm tra và chỉ chọn tập ứng viên có độ chính xác phân lớp cao nhất.

3. Tại sao trong trường hợp đối tượng hoặc thuộc tính thay đổi giá trị, luận án lại đề xuất thuật toán trực tiếp thay vì kết hợp hai thao tác loại bỏ và bổ sung? Về mặt lý thuyết, việc một đối tượng hoặc thuộc tính thay đổi giá trị có thể xem như xóa bỏ đối tượng/thuộc tính cũ và thêm vào đối tượng/thuộc tính với giá trị mới. Tuy nhiên, việc thực hiện gián tiếp hai bước như vậy đòi hỏi cập nhật ma trận dung sai hai lần và tính toán hai chu kỳ lọc - đóng gói độc lập, làm tăng đáng kể chi phí thời gian và có thể tạo ra các tập ứng viên phân tán. Thuật toán trực tiếp (FWIA_U_Obj hoặc FWIA_U_Attr) cập nhật ma trận dung sai chỉ trên phần giá trị thay đổi trong một lần lặp duy nhất, giúp giảm thời gian tính toán và giữ cho tập thuộc tính rút gọn tối ưu hơn.

4. Đánh đổi (trade-off) lớn nhất khi áp dụng các thuật toán đề xuất trong luận án là gì? Đánh đổi lớn nhất là chi phí thời gian tính toán. Các thuật toán lai ghép của luận án (IDS_IFW_AO, IDS_IFW_DO, FWIA_U_Obj, FWIA_AA, FWIA_DA, FWIA_U_Attr) đều có thời gian thực thi cao hơn các thuật toán tiếp cận lọc thuần túy tương ứng (như IARM-I, KGIRA-M, FSMV, UARA, Attribute-R) do phải thực hiện đánh giá kiểm tra chéo 10-fold nhiều lần với bộ phân lớp C4.5. Đổi lại, các thuật toán này mang lại số lượng thuộc tính rút gọn ít hơn và độ chính xác phân lớp cao hơn.

5. Cơ chế kiểm tra dừng và điều kiện bảo toàn tập rút gọn trong các thuật toán gia tăng của luận án hoạt động như thế nào? Các thuật toán gia tăng trước tiên kiểm tra điều kiện lớp dung sai: nếu các đối tượng thay đổi thỏa mãn quan hệ bao hàm lớp dung sai trên tập rút gọn thuộc về lớp dung sai trên thuộc tính quyết định (ví dụ $S_R(u_{new}) \subseteq S_{{d}}(u_{new})$), thuật toán kết luận ngay tập rút gọn $R$ không thay đổi và dừng lại mà không cần tính toán lại ma trận. Nếu điều kiện không thỏa mãn, thuật toán mới kích hoạt công thức gia tăng cập nhật ma trận khoảng cách $D$, sau đó lần lượt duyệt và thêm/bớt thuộc tính cho đến khi khoảng cách của tập ứng viên cân bằng với khoảng cách của toàn bộ tập thuộc tính điều kiện $C$.

Kết luận

Luận án tiến sĩ của tác giả Nguyễn Anh Tuấn đã giải quyết trọn vẹn bài toán rút gọn thuộc tính gia tăng trên bảng quyết định không đầy đủ theo tiếp cận mô hình tập thô dung sai dưới đầy đủ các kịch bản biến động dữ liệu: biến động tập đối tượng, biến động tập thuộc tính và biến động giá trị. Bằng việc kết hợp độ đo khoảng cách dung sai với chiến lược lai ghép lọc - đóng gói sử dụng bộ phân lớp C4.5, các thuật toán đề xuất đã khắc phục được nhược điểm của các phương pháp tiếp cận lọc truyền thống, giảm thiểu số lượng thuộc tính dư thừa và nâng cao độ chính xác phân lớp. Kết quả nghiên cứu và các công thức toán học gia tăng được kiểm chứng chặt chẽ qua thực nghiệm trên 06 bộ dữ liệu chuẩn UCI, cung cấp tài liệu tham khảo có giá trị học thuật và ứng dụng thực tiễn trong lĩnh vực khoa học máy tính và khai phá dữ liệu.

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 luanvanchat@agmail.