Luận án TS. Nguyễn Bá Quảng: Rút gọn thuộc tính theo tiếp cận Filter-Wrapper

Luận án tiến sĩ toán học phát triển các thuật toán rút gọn thuộc tính hiệu quả cho bảng quyết định không đầy đủ theo tiếp cận filter-wrapper.

• 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ĩ
• Năm xuất bản: 2021
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
• DANH MỤC CÁC BẢNG
• DANH MỤC CÁC HÌNH VẼ
• MỞ ĐẦU
• 1. CHƯƠNG 1: TỔNG QUAN VỀ RÚT GỌN THUỘC TÍNH THEO TIẾP CẬN TẬP THÔ DUNG SAI
• 1.1. Hệ thông tin và mô hình tập thô truyền thống
• 1.1.1. Hệ thông tin
• 1.1.2. Mô hình tập thô truyền thống
• 1.2. Hệ thông tin không đầy đủ và mô hình tập thô dung sai
• 1.2.1. Hệ thông tin không đầy đủ
• 1.2.2. Mô hình tập thô dung sai
• 1.2.3. Bảng quyết định không đầy đủ
• 1.2.4. Ma trận dung sai
• 1.3. Tổng quan về rút gọn thuộc tính theo tiếp cận tập thô dung sai
• 1.3.1. Tổng quan về rút gọn thuộc tính
• 1.3.2. Tiếp cận filter, wrapper trong rút gọn thuộc tính
• 1.3.3. Rút gọn thuộc tính theo tiếp cận tập thô dung sai
• 1.4. 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
• 1.4.1. Rút gọn thuộc tính theo tiếp cận tập thô dung sai
• 1.4.2. Phương pháp gia tăng rút gọn thuộc tính trong bảng quyết định không đầy đủ theo tiếp cận tập thô dung sai
• 1.5. 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.1.1. Xây dựng độ đo khoảng cách giữa hai tập hợp
• 2.1.2. Xây dựng độ đo khoảng cách giữa hai tập thuộc tính
• 2.2. 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.2.1. 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.2.2. Đề 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.3. Thực nghiệm và đánh giá kết quả
• 2.4. 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.1.1. Công thức cập nhật khoảng cách khi bổ sung tập đối tượng
• 3.1.2. 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.1.3. Công thức cập nhật khoảng cách khi loại bỏ tập đối tượng
• 3.1.4. 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.1.5. Thực nghiệm và đánh giá các thuật toán
• 3.2. 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.2.1. Công thức cập nhật khoảng cách khi bổ sung tập thuộc tính
• 3.2.2. 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.2.3. Công thức cập nhật khoảng cách khi loại bỏ tập thuộc tính
• 3.2.4. 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.2.5. Thực nghiệm và đánh giá các thuật toán
• 3.3. 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. Hướng dẫn rút gọn thuộc tính cho bảng quyết định không đầy đủ

Rút gọn thuộc tính là một bước tiền xử lý dữ liệu quan trọng trong khai phá dữ liệu (Data mining) và học máy. Mục tiêu chính là loại bỏ các thuộc tính không liên quan hoặc dư thừa khỏi tập dữ liệu. Quá trình này giúp giảm độ phức tạp tính toán, tăng tốc độ của các thuật toán và cải thiện độ chính xác của mô hình dự đoán. Đặc biệt, trong bối cảnh dữ liệu lớn (Big Data), việc giảm chiều dữ liệu (dimensionality reduction) trở nên cấp thiết hơn bao giờ hết. Một trong những thách thức lớn nhất là xử lý bảng quyết định không đầy đủ, nơi một số đối tượng bị thiếu giá trị ở một vài thuộc tính. Các phương pháp truyền thống thường yêu cầu một bước xử lý giá trị thiếu (imputation) trước khi rút gọn, điều này có thể làm sai lệch thông tin gốc. Phương pháp rút gọn thuộc tính cho bảng quyết định không đầy đủ ra đời nhằm giải quyết trực tiếp vấn đề này. Bằng cách sử dụng các công cụ toán học mạnh mẽ như Lý thuyết tập thô (Rough set theory) và các mô hình mở rộng, các nhà nghiên cứu đã phát triển những cách tiếp cận hiệu quả để chọn lọc thuộc tính mà không cần điền giá trị thiếu. Hướng tiếp cận này không chỉ bảo toàn tính toàn vẹn của dữ liệu mà còn tìm ra được tập rút gọn (reduct) tối ưu, chứa ít thuộc tính nhất nhưng vẫn giữ được khả năng phân lớp của hệ thống. Luận án của Nguyễn Bá Quảng (2021) đã đi sâu vào việc phát triển các thuật toán mới, kết hợp phương pháp Filter và Wrapper, để nâng cao hiệu quả của quá trình này.

1.1. Khái niệm về hệ quyết định không đầy đủ và tầm quan trọng

Một hệ quyết định không đầy đủ (Incomplete decision system) là một hệ thống thông tin trong đó tồn tại ít nhất một đối tượng có giá trị thuộc tính không xác định, thường được ký hiệu là '*'. Ví dụ, trong hồ sơ y tế, một bệnh nhân có thể thiếu kết quả của một xét nghiệm cụ thể. Tình trạng này rất phổ biến trong các bài toán thực tế do hạn chế về chi phí, thời gian thu thập dữ liệu hoặc lỗi thiết bị. Tầm quan trọng của việc nghiên cứu các hệ thống này nằm ở chỗ chúng phản ánh đúng bản chất của dữ liệu trong thế giới thực. Việc loại bỏ các đối tượng có giá trị thiếu sẽ làm mất đi lượng thông tin quý giá. Do đó, cần có các phương pháp có khả năng làm việc trực tiếp trên dữ liệu khuyết thiếu. Việc rút gọn thuộc tính trên các hệ này giúp đơn giản hóa mô hình, làm nổi bật các thuộc tính quan trọng nhất (thuộc tính lõi - core attribute), và từ đó nâng cao hiệu quả của các mô hình phân lớp và dự đoán.

1.2. Vai trò của Lý thuyết tập thô trong khai phá dữ liệu

Lý thuyết tập thô (Rough set theory), do Zdzisław Pawlak đề xuất vào những năm 1980, là một công cụ toán học mạnh mẽ để xử lý sự không chắc chắn và mơ hồ trong dữ liệu. Nền tảng của lý thuyết này dựa trên quan hệ không phân biệt được (indiscernibility relation) để xấp xỉ các tập hợp. Trong khai phá dữ liệu, lý thuyết tập thô được ứng dụng rộng rãi trong bài toán rút gọn thuộc tính (attribute reduction). Nó cho phép xác định sự phụ thuộc giữa các thuộc tính và tìm ra một tập con thuộc tính tối thiểu mà vẫn duy trì được khả năng phân loại của toàn bộ tập thuộc tính ban đầu. Đặc biệt, mô hình tập thô dung sai (tolerance rough set) là một mở rộng quan trọng, được thiết kế để làm việc trực tiếp với hệ quyết định không đầy đủ bằng cách thay thế quan hệ tương đương bằng quan hệ dung sai, cho phép xử lý các missing values một cách tự nhiên.

II. Thách thức khi xử lý dữ liệu thiếu trong feature selection

Việc lựa chọn thuộc tính (feature selection) trong các bảng quyết định không đầy đủ đối mặt với nhiều thách thức đáng kể. Vấn đề cốt lõi là sự hiện diện của các giá trị bị thiếu (missing values), làm phá vỡ các giả định của nhiều thuật toán học máy và thống kê truyền thống. Các phương pháp cổ điển thường không thể tính toán các độ đo quan trọng như độ tương quan hay entropy thông tin một cách chính xác khi dữ liệu bị khuyết. Một giải pháp phổ biến là loại bỏ các bản ghi chứa giá trị thiếu, nhưng cách này có thể dẫn đến mất mát thông tin nghiêm trọng, đặc biệt khi dữ liệu thiếu phân bố rộng rãi. Một cách khác là điền giá trị thiếu (imputation) bằng các giá trị ước tính như trung bình, trung vị, hoặc giá trị phổ biến nhất. Tuy nhiên, việc này có thể đưa vào dữ liệu những thông tin sai lệch, ảnh hưởng đến chất lượng của tập rút gọn cuối cùng. Lý thuyết tập thô truyền thống dựa trên quan hệ tương đương cũng gặp khó khăn, vì hai đối tượng khó có thể được coi là 'không phân biệt được' nếu một trong hai có giá trị thiếu. Để vượt qua những rào cản này, các mô hình mở rộng như tập thô dung sai đã được phát triển. Các mô hình này cung cấp một khuôn khổ lý thuyết vững chắc để định nghĩa lại sự tương đồng giữa các đối tượng và tính toán mức độ phụ thuộc thuộc tính ngay cả khi có dữ liệu thiếu, mở đường cho các phương pháp rút gọn thuộc tính cho bảng quyết định không đầy đủ hiệu quả hơn.

2.1. Hạn chế của mô hình tập thô truyền thống với missing values

Mô hình tập thô truyền thống của Pawlak hoạt động dựa trên quan hệ tương đương (equivalence relation), yêu cầu các đối tượng phải có cùng giá trị trên một tập thuộc tính để được xếp vào cùng một lớp tương đương. Khi gặp missing values, quan hệ này trở nên không xác định. Nếu một đối tượng u có giá trị a(u) = 'cao' và đối tượng v có giá trị a(v) = '*', ta không thể kết luận chúng có tương đương hay không. Điều này làm cho việc xây dựng các tập xấp xỉ dưới và xấp xỉ trên trở nên bất khả thi. Do đó, mô hình tập thô cổ điển không thể áp dụng trực tiếp cho hệ quyết định không đầy đủ. Để khắc phục, Kryszkiewicz đã đề xuất mô hình tập thô dung sai, sử dụng quan hệ dung sai (tolerance relation) để nới lỏng điều kiện tương đương, cho phép so sánh các đối tượng ngay cả khi có giá trị thiếu.

2.2. Sự cần thiết của dimensionality reduction trong dữ liệu lớn

Trong kỷ nguyên dữ liệu lớn, các tập dữ liệu không chỉ lớn về số lượng mẫu mà còn về số lượng thuộc tính (chiều). Dữ liệu nhiều chiều thường chứa các thuộc tính dư thừa, nhiễu và không liên quan. Điều này dẫn đến hiện tượng 'lời nguyền của chiều' (curse of dimensionality), làm giảm hiệu suất của các thuật toán data mining, tăng chi phí lưu trữ và tính toán. Giảm chiều dữ liệu (Dimensionality reduction) là quá trình tất yếu để giải quyết vấn đề này. Nó giúp đơn giản hóa mô hình, cải thiện khả năng tổng quát hóa và tăng cường khả năng diễn giải kết quả. Trong bối cảnh các bảng quyết định không đầy đủ, việc giảm chiều càng trở nên phức tạp nhưng cũng càng quan trọng, vì nó giúp tập trung vào các thuộc tính cốt lõi, giảm thiểu tác động của nhiễu và dữ liệu thiếu.

III. Phương pháp Filter Cách tiếp cận phổ biến để tìm tập rút gọn

Phương pháp Filter là một trong hai cách tiếp cận chính trong bài toán rút gọn thuộc tính. Đặc điểm của phương pháp này là quá trình lựa chọn thuộc tính được thực hiện độc lập, trước khi áp dụng bất kỳ thuật toán học máy nào. Các thuộc tính được đánh giá và xếp hạng dựa trên các đặc tính nội tại của dữ liệu. Các tiêu chí đánh giá thường là các độ đo thống kê hoặc lý thuyết thông tin, chẳng hạn như mức độ phụ thuộc thuộc tính, entropy thông tin, hoặc miền dương trong Lý thuyết tập thô. Dựa trên điểm số này, một thuật toán heuristic sẽ được sử dụng để tìm ra một tập rút gọn tối ưu. Ví dụ, một thuật toán có thể bắt đầu với một tập rỗng và lần lượt thêm vào thuộc tính có độ quan trọng cao nhất cho đến khi đạt được một ngưỡng nhất định. Ưu điểm lớn của phương pháp Filter là tốc độ tính toán nhanh và khả năng mở rộng tốt với các tập dữ liệu lớn. Nó không phụ thuộc vào một mô hình phân lớp cụ thể nào, do đó tập rút gọn thu được có thể được sử dụng cho nhiều thuật toán khác nhau. Tuy nhiên, nhược điểm của nó là có thể bỏ qua các thuộc tính mà khi đứng riêng lẻ thì không quan trọng, nhưng khi kết hợp với các thuộc tính khác lại mang lại hiệu quả phân lớp cao. Đây là điểm mà phương pháp Wrapper tỏ ra vượt trội.

3.1. Nguyên lý hoạt động của thuật toán heuristic trong filter

Các thuật toán heuristic là trái tim của phương pháp Filter. Vì việc tìm kiếm toàn bộ không gian 2^M tập con thuộc tính (với M là tổng số thuộc tính) là bất khả thi về mặt tính toán, các thuật toán này sử dụng các chiến lược tìm kiếm gần đúng để nhanh chóng tìm ra một giải pháp tốt. Có hai hướng tiếp cận chính: từ dưới lên (bottom-up) và từ trên xuống (top-down). Hướng từ dưới lên bắt đầu với tập rỗng và ở mỗi bước, thêm vào thuộc tính mang lại sự cải thiện lớn nhất cho độ đo đánh giá (ví dụ: tăng mức độ phụ thuộc thuộc tính nhiều nhất). Hướng từ trên xuống bắt đầu với toàn bộ tập thuộc tính và ở mỗi bước, loại bỏ thuộc tính ít quan trọng nhất mà không làm giảm đáng kể giá trị của độ đo. Các thuật toán này dừng lại khi không thể cải thiện thêm hoặc đã đạt được số lượng thuộc tính mong muốn.

3.2. Đánh giá ưu và nhược điểm của các độ đo như entropy thông tin

Entropy thông tin là một độ đo phổ biến trong phương pháp Filter, được mở rộng để áp dụng cho hệ quyết định không đầy đủ. Nó đo lường mức độ bất định hoặc hỗn loạn của một tập dữ liệu. Một thuộc tính được coi là quan trọng nếu nó giúp giảm entropy của thuộc tính quyết định một cách đáng kể. Ưu điểm của entropy là nó có nền tảng lý thuyết vững chắc và có thể nắm bắt các mối quan hệ phi tuyến giữa các thuộc tính. Tuy nhiên, nhược điểm là nó có thể thiên vị các thuộc tính có nhiều giá trị khác nhau. Hơn nữa, giống như các độ đo Filter khác, nó đánh giá thuộc tính một cách độc lập với mô hình phân lớp cuối cùng, do đó tập rút gọn tìm được có thể không phải là tối ưu nhất về mặt độ chính xác phân lớp thực tế.

IV. Bí quyết kết hợp Filter Wrapper để tối ưu attribute reduction

Phương pháp kết hợp Filter-Wrapper là một hướng tiếp cận lai ghép, tận dụng ưu điểm của cả hai phương pháp để đạt được hiệu quả vượt trội trong rút gọn thuộc tính. Cách tiếp cận này thường được thực hiện theo hai giai đoạn. Giai đoạn đầu tiên sử dụng phương pháp Filter để nhanh chóng loại bỏ một lượng lớn các thuộc tính không liên quan và tạo ra một hoặc nhiều tập rút gọn ứng viên. Giai đoạn này giúp thu hẹp đáng kể không gian tìm kiếm, giảm bớt gánh nặng tính toán cho giai đoạn sau. Giai đoạn thứ hai, phương pháp Wrapper được áp dụng trên các tập thuộc tính ứng viên này. Cụ thể, mỗi tập ứng viên sẽ được sử dụng để huấn luyện một mô hình phân lớp cụ thể (ví dụ: K-NN, C4.5). Độ chính xác phân lớp của mô hình này sẽ được dùng làm tiêu chí cuối cùng để lựa chọn ra tập rút gọn tốt nhất. Hướng tiếp cận này giải quyết được nhược điểm cốt lõi của phương pháp Filter (không tối ưu cho độ chính xác) và phương pháp Wrapper (chi phí tính toán cao). Như được trình bày trong luận án của Nguyễn Bá Quảng, thuật toán IDS_FW_DAR là một ví dụ điển hình cho cách tiếp cận này trong môi trường bảng quyết định không đầy đủ, giúp giảm thiểu số lượng thuộc tính trong khi vẫn cải thiện hoặc bảo toàn độ chính xác phân lớp.

4.1. Giai đoạn Filter Sàng lọc ứng viên tập rút gọn reduct tiềm năng

Trong giai đoạn đầu của mô hình lai, phương pháp Filter đóng vai trò như một bộ lọc sơ bộ. Mục tiêu là nhanh chóng xác định một tập hợp các thuộc tính có tiềm năng cao nhất. Bằng cách sử dụng một độ đo hiệu quả, chẳng hạn như độ đo khoảng cách được đề xuất trong luận án, thuật toán sẽ xây dựng các tập rút gọn ứng viên. Các tập này là những tập thuộc tính tối thiểu có khả năng bảo toàn một lượng thông tin nhất định theo độ đo đã chọn. Thay vì chỉ tìm một tập rút gọn duy nhất, giai đoạn này có thể tạo ra nhiều ứng viên khác nhau. Quá trình này hiệu quả hơn nhiều so với việc áp dụng Wrapper trên toàn bộ không gian thuộc tính ban đầu, đặc biệt là với các bài toán giảm chiều dữ liệu có số lượng thuộc tính lớn.

4.2. Giai đoạn Wrapper Lựa chọn thuộc tính lõi core attribute tối ưu

Sau khi có được danh sách các tập ứng viên từ giai đoạn Filter, giai đoạn Wrapper bắt đầu. Mỗi tập ứng viên được coi như một giả thuyết về tập thuộc tính tốt nhất. Một thuật toán phân lớp được chọn trước (gọi là 'hộp đen') sẽ được huấn luyện và đánh giá trên từng tập ứng viên này, thường thông qua kỹ thuật kiểm định chéo (cross-validation) để đảm bảo kết quả đáng tin cậy. Tập rút gọn (reduct) nào mang lại độ chính xác phân lớp cao nhất sẽ được chọn làm kết quả cuối cùng. Quá trình này đảm bảo rằng tập thuộc tính được chọn không chỉ tốt về mặt lý thuyết thông tin (theo độ đo Filter) mà còn tối ưu về mặt hiệu suất thực tiễn với một mô hình cụ thể. Nó giúp xác định chính xác các thuộc tính lõi và các thuộc tính tương tác quan trọng mà phương pháp Filter đơn thuần có thể bỏ lỡ.

V. Ứng dụng thực tiễn của Rough set theory trong y tế tài chính

Các phương pháp rút gọn thuộc tính cho bảng quyết định không đầy đủ dựa trên Rough set theory có nhiều ứng dụng thực tiễn quan trọng, đặc biệt trong các lĩnh vực mà dữ liệu thường xuyên bị khuyết thiếu và phức tạp. Trong lĩnh vực y tế, các hệ thống hỗ trợ chẩn đoán bệnh thường phải làm việc với hồ sơ bệnh nhân không đầy đủ. Ví dụ, không phải bệnh nhân nào cũng thực hiện tất cả các xét nghiệm cần thiết. Áp dụng các thuật toán rút gọn thuộc tính giúp xác định các triệu chứng hoặc chỉ số xét nghiệm quan trọng nhất (thuộc tính lõi) để đưa ra chẩn đoán chính xác. Điều này không chỉ cải thiện độ chính xác mà còn có thể giảm chi phí y tế bằng cách loại bỏ các xét nghiệm không cần thiết. Trong lĩnh vực tài chính và ngân hàng, các mô hình đánh giá rủi ro tín dụng thường dựa trên hàng trăm biến số về khách hàng. Dữ liệu này thường bị thiếu do khách hàng không cung cấp đủ thông tin. Attribute reduction giúp xây dựng các mô hình xếp hạng tín dụng gọn nhẹ, hiệu quả và đáng tin cậy hơn. Các kết quả thực nghiệm được báo cáo trong nhiều công trình, bao gồm luận án của Nguyễn Bá Quảng (2021) trên các bộ dữ liệu từ kho lưu trữ UCI, đã chứng minh rằng các thuật toán như IDS_FW_DAR có thể giảm đáng kể số lượng thuộc tính mà vẫn 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.

5.1. Kết quả thực nghiệm trên bộ dữ liệu UCI và đánh giá hiệu quả

Để chứng minh tính hiệu quả, các thuật toán mới đề xuất thường được kiểm nghiệm trên các bộ dữ liệu chuẩn từ kho dữ liệu UCI Machine Learning Repository. Đây là một thực tiễn phổ biến trong cộng đồng data mining. Các bộ dữ liệu như 'Audiology', 'Soybean-large', hay 'Arrhythmia' thường chứa một tỷ lệ đáng kể các missing values. Trong các nghiên cứu, hiệu suất của thuật toán mới (ví dụ: một thuật toán filter-wrapper) sẽ được so sánh với các thuật toán filter kinh điển khác dựa trên hai tiêu chí chính: số lượng thuộc tính trong tập rút gọn cuối cùng và độ chính xác phân lớp đạt được. Kết quả thường cho thấy các phương pháp lai ghép không chỉ tạo ra các tập rút gọn nhỏ hơn mà còn đạt được độ chính xác cao hơn hoặc tương đương, minh chứng cho tính ưu việt của chúng.

5.2. Cải thiện độ chính xác phân lớp sau khi giảm chiều dữ liệu

Một trong những lợi ích lớn nhất của việc giảm chiều dữ liệu một cách thông minh là cải thiện độ chính xác của mô hình phân lớp. Việc loại bỏ các thuộc tính nhiễu và không liên quan giúp mô hình tập trung vào các tín hiệu thực sự quan trọng trong dữ liệu, tránh được hiện tượng học vẹt (overfitting). Khi mô hình ít phức tạp hơn, nó có khả năng tổng quát hóa tốt hơn trên các dữ liệu mới chưa từng thấy. Các phương pháp dựa trên Lý thuyết tập thô và đặc biệt là cách tiếp cận filter-wrapper, đã chứng tỏ khả năng tìm ra các tập thuộc tính không chỉ nhỏ gọn mà còn có sức mạnh phân biệt cao, trực tiếp dẫn đến việc nâng cao hiệu suất của các hệ thống học máy trong thực tế.

VI. Tương lai của data mining với các phương pháp rút gọn cải tiến

Tương lai của ngành khai phá dữ liệu (Data mining) gắn liền với việc phát triển các phương pháp xử lý dữ liệu ngày càng thông minh và hiệu quả hơn. Trong đó, các phương pháp rút gọn thuộc tính cho bảng quyết định không đầy đủ sẽ tiếp tục đóng vai trò trung tâm. Một hướng nghiên cứu đầy hứa hẹn là phát triển các thuật toán gia tăng (incremental algorithms). Các thuật toán này có khả năng cập nhật tập rút gọn một cách hiệu quả khi có dữ liệu mới được thêm vào hoặc loại bỏ khỏi hệ thống, thay vì phải chạy lại toàn bộ quá trình từ đầu. Điều này đặc biệt quan trọng trong các ứng dụng thời gian thực và xử lý luồng dữ liệu (data stream). Luận án của Nguyễn Bá Quảng cũng đã đề cập đến việc phát triển các thuật toán gia tăng filter-wrapper, cho thấy đây là một định hướng nghiên cứu cấp thiết. Một hướng khác là tích hợp các kỹ thuật học sâu (deep learning) vào quá trình feature selection để tự động học các biểu diễn đặc trưng cấp cao từ dữ liệu thô, kể cả khi dữ liệu không đầy đủ. Hơn nữa, việc nghiên cứu các độ đo mới, có khả năng nắm bắt các mối quan hệ phức tạp hơn giữa các thuộc tính, cũng sẽ góp phần tạo ra các thế hệ thuật toán attribute reduction mạnh mẽ hơn, đáp ứng yêu cầu của các bài toán ngày càng phức tạp trong tương lai.

6.1. Tổng kết những đóng góp chính của phương pháp filter wrapper

Phương pháp kết hợp filter-wrapper đã mang lại một bước tiến quan trọng cho lĩnh vực rút gọn thuộc tính. Đóng góp chính của nó là tạo ra một sự cân bằng tối ưu giữa hiệu quả tính toán và độ chính xác của mô hình. Bằng cách sử dụng Filter để giảm không gian tìm kiếm và Wrapper để tinh chỉnh lựa chọn cuối cùng, phương pháp này đã giải quyết được những hạn chế cố hữu của từng cách tiếp cận riêng lẻ. Nó cho phép tìm ra các tập rút gọn nhỏ gọn hơn và có khả năng phân lớp tốt hơn, đặc biệt hiệu quả khi áp dụng cho các hệ quyết định không đầy đủ dựa trên nền tảng Rough set theory. Các thuật toán như IDS_FW_DAR là minh chứng cụ thể cho sự thành công của hướng đi này.

6.2. Hướng nghiên cứu gia tăng cho hệ quyết định không đầy đủ động

Các hệ thống dữ liệu trong thực tế thường mang tính động, nghĩa là dữ liệu liên tục thay đổi theo thời gian. Các đối tượng hoặc thuộc tính mới có thể được thêm vào, hoặc các giá trị có thể được cập nhật. Các thuật toán rút gọn thuộc tính truyền thống, vốn được thiết kế cho dữ liệu tĩnh, sẽ trở nên kém hiệu quả vì phải tính toán lại từ đầu sau mỗi lần thay đổi. Do đó, hướng nghiên cứu về các thuật toán gia tăng cho hệ quyết định không đầy đủ là cực kỳ quan trọng. Mục tiêu là phát triển các phương pháp có thể cập nhật tập rút gọn một cách nhanh chóng bằng cách chỉ tính toán trên phần dữ liệu thay đổi. Điều này giúp tiết kiệm đáng kể thời gian và tài nguyên tính toán, làm cho các kỹ thuật data mining trở nên khả thi trong các môi trường dữ liệu động và quy mô lớ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ô 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   .