Luận văn thạc sĩ nghiên cứu thuật toán filterwrapper tìm tập rút gọn của bảng quyết định không đầy đủ và ứng dụng phát hiện tàu thuyền từ ảnh vệ tinh

Luận văn thạc sĩ: Nghiên cứu thuật toán FilterWrapper, rút gọn bảng quyết định không đầy đủ. Ứng dụng phát hiện tàu thuyền từ ảnh vệ tinh.

• Tác giả: Phạm Quang Nam
• Người hướng dẫn: PGS. Nguyễn Long Giang
• Trường học: Học viện Khoa học và Công nghệ
• Chuyên ngành: Hệ thống thông tin
• Đề tài: Nghiên cứu thuật toán filter-wrapper tìm tập rút gọn của bảng quyết định không đầy đủ và ứng dụng phát hiện tàu thuyền từ ảnh vệ tinh
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2021
• Địa điểm: Hà Nội

Mục lục chi tiết

• DANH MỤC KÝ HIỆU VÀ CÁC CHỮ VIẾT TẮT
• DANH MỤC HÌNH VẼ VÀ ĐỒ THỊ
• MỞ ĐẦU
• Tính cấp thiết
• Mục tiêu nghiên cứu
• Đối tượng và phạm vi nghiên cứu
• Phương pháp nghiên cứu
• Nội dung nghiên cứu
• Ý nghĩa khoa học và thực tiễn
• Bố cục của luận văn
• 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.3. Bảng quyết định không đầy đủ
• 1.4. Ma trận dung sai
• 1.5. Tổng quan về rút gọn thuộc tính theo tiếp cận tập thô dung sai
• 1.5.1. Tổng quan về rút gọn thuộc tính
• 1.5.2. Tiếp cận filter, wrapper trong rút gọn thuộc tính
• 1.5.3. Rút gọn thuộc tính theo tiếp cận tập thô dung sai
• 1.6. 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 dung sai
• 1.6.1. Rút gọn thuộc tính theo tiếp cận tập thô dung sai
• 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.3. 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.4. 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.5. Thực nghiệm và đánh giá kết quả
• 2.6. Kết luận chương 2
• 3. CHƯƠNG 3: THỬ NGHIỆM RÚT GỌN THUỘC TÍNH VỚI BÀI TOÁN PHÂN LỚP ĐỐI TƯỢNG TRONG ẢNH VIỄN THÁM
• 3.1. Xây dựng mô hình giải quyết bài toán
• 3.2. Thực thi mô hình phân lớp gán nhãn cho ảnh viễn thám
• 3.2.1. Môi trường chạy thử nghiệm
• 3.2.2. Thực hiện chương trình
• 3.2.2.1. Tiền xử lý dữ liệu
• 3.2.2.2. Huấn luyện mô hình
• 3.2.2.3. Thực thi mô hình
• 4. CHƯƠNG 4: KẾT LUẬN
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Khám phá thuật toán rút gọn bảng quyết định trong kỷ nguyên số

Trong bối cảnh bùng nổ dữ liệu, việc xử lý các tập dữ liệu với số lượng thuộc tính khổng lồ đã trở thành một thách thức lớn. Các thuật toán khai phá dữ liệu và học máy thường gặp khó khăn về hiệu suất và độ phức tạp khi đối mặt với dữ liệu đa chiều. Để giải quyết vấn đề này, thuật toán rút gọn bảng quyết định đã ra đời như một công cụ thiết yếu trong giai đoạn tiền xử lý. Mục tiêu chính của kỹ thuật này là loại bỏ các thuộc tính dư thừa, không liên quan mà không làm mất mát thông tin quan trọng, từ đó gia tăng tốc độ tính toán, cải thiện chất lượng và tính dễ hiểu của kết quả. Đặc biệt, trong các bài toán thực tế, dữ liệu thường không hoàn chỉnh, dẫn đến sự xuất hiện của bảng quyết định không đầy đủ. Đây là một trở ngại lớn vì các phương pháp truyền thống thường yêu cầu dữ liệu đầy đủ. Luận văn của Phạm Quang Nam (2021) đã tập trung vào việc giải quyết bài toán này bằng cách áp dụng lý thuyết tập thô dung sai, một mở rộng của lý thuyết tập thô cổ điển do Pawlak đề xuất. Lý thuyết này cho phép xử lý trực tiếp các giá trị bị thiếu mà không cần các bước điền giá trị phức tạp, giữ nguyên bản chất của dữ liệu. Cách tiếp cận này sử dụng quan hệ dung sai thay vì quan hệ tương đương, cho phép xấp xỉ các tập hợp trong môi trường thông tin không chắc chắn và không đầy đủ. Sự kết hợp giữa lý thuyết nền tảng vững chắc và nhu cầu thực tiễn đã tạo ra động lực để nghiên cứu các phương pháp rút gọn thuộc tính hiệu quả hơn.

1.1. Bảng quyết định không đầy đủ Thách thức trong thực tiễn

Một bảng quyết định không đầy đủ 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 bị thiếu (missing value), thường được ký hiệu là '*'. Ví dụ điển hình là trong lĩnh vực y tế, một bảng chẩn đoán bệnh có thể thiếu thông tin về một số triệu chứng của bệnh nhân do không thể thu thập đầy đủ. Tình trạng thiếu dữ liệu này gây ra nhiều khó khăn cho các thuật toán khai phá dữ liệu truyền thống, vốn yêu cầu dữ liệu phải hoàn chỉnh. Việc xử lý các giá trị thiếu bằng cách loại bỏ đối tượng hoặc điền giá trị trung bình có thể làm sai lệch thông tin và giảm độ chính xác của mô hình. Do đó, việc phát triển các thuật toán có khả năng làm việc trực tiếp trên dữ liệu không đầy đủ là một yêu cầu cấp thiết.

1.2. Lý thuyết tập thô dung sai Nền tảng toán học cốt lõi

Để giải quyết vấn đề dữ liệu thiếu, Kryszkiewicz [4] đã mở rộng lý thuyết tập thô truyền thống thành mô hình tập thô dung sai (tolerance rough set). Thay vì sử dụng quan hệ tương đương (equivalence relation) yêu cầu các đối tượng phải giống hệt nhau trên mọi thuộc tính để được nhóm lại, mô hình này sử dụng quan hệ dung sai (tolerance relation). Quan hệ này linh hoạt hơn, cho phép hai đối tượng được xem là tương tự ngay cả khi một trong hai có giá trị thuộc tính bị thiếu. Dựa trên quan hệ này, các khái niệm về xấp xỉ dưới và xấp xỉ trên được định nghĩa lại, tạo cơ sở toán học vững chắc để xây dựng các thuật toán rút gọn thuộc tính trực tiếp trên bảng quyết định không đầy đủ mà không cần tiền xử lý giá trị thiếu.

1.3. Tiếp cận Filter và Wrapper Hai chiến lược rút gọn thuộc tính

Trong rút gọn thuộc tính, có hai hướng tiếp cận chính là Filter (lọc) và Wrapper (đóng gói). Phương pháp Filter đánh giá và lựa chọn các tập con thuộc tính dựa trên các đặc tính nội tại của dữ liệu (như entropy, độ tương quan) mà không phụ thuộc vào thuật toán học máy sẽ được sử dụng sau này. Ưu điểm của nó là tốc độ tính toán nhanh. Ngược lại, phương pháp Wrapper sử dụng chính một thuật toán học máy để đánh giá chất lượng của từng tập con thuộc tính. Nó chọn ra tập con mang lại độ chính xác phân lớp cao nhất. Mặc dù cho kết quả tốt hơn, Wrapper lại tốn kém về mặt tính toán. Việc kết hợp ưu điểm của cả hai phương pháp là một hướng đi đầy hứa hẹn.

II. Vấn đề của phương pháp filter trong rút gọn thuộc tính dữ liệu

Các thuật toán rút gọn thuộc tính truyền thống dựa trên lý thuyết tập thô và tập thô dung sai phần lớn đều theo hướng tiếp cận Filter. Các phương pháp này xác định một tập thuộc tính rút gọn bằng cách tìm ra tập con nhỏ nhất có thể bảo toàn một độ đo thông tin nhất định, chẳng hạn như miền dương, entropy, hay ma trận phân biệt. Mặc dù các thuật toán này có ưu điểm là tốc độ xử lý nhanh và độc lập với mô hình phân lớp, chúng lại tồn tại những hạn chế cố hữu. Vấn đề lớn nhất là tập rút gọn thu được chưa chắc đã là tối ưu về mặt độ chính xác phân lớp. Việc chỉ tập trung vào việc bảo toàn một độ đo lý thuyết có thể dẫn đến việc lựa chọn một tập thuộc tính không phải là tốt nhất khi áp dụng vào một bộ phân lớp cụ thể (như SVM, C4.5, hay KNN). Điều này tạo ra một khoảng cách giữa mục tiêu lý thuyết (bảo toàn độ đo) và mục tiêu thực tiễn (tối đa hóa độ chính xác). Nghiên cứu của Phạm Quang Nam (2021) chỉ ra rằng, tập rút gọn từ các thuật toán filter thường chưa tối ưu về cả số lượng thuộc tính và độ chính xác. Việc đánh giá hiệu quả của mô hình chỉ được thực hiện sau khi đã tìm được tập rút gọn, dẫn đến một quy trình một chiều và thiếu sự phản hồi. Do đó, cần có một hướng tiếp cận mới có khả năng tích hợp việc đánh giá độ chính xác vào ngay trong quá trình lựa chọn thuộc tính.

2.1. Hạn chế của các thuật toán filter truyền thống

Các thuật toán filter heuristic, như POS-R [8] hay INF-R [20], hoạt động bằng cách xây dựng một độ đo và định nghĩa độ quan trọng của thuộc tính dựa trên độ đo đó. Sau đó, thuật toán sẽ chọn các thuộc tính có độ quan trọng cao nhất cho đến khi độ đo được bảo toàn. Tuy nhiên, "bảo toàn độ đo" không đồng nghĩa với "tối ưu độ chính xác". Một tập thuộc tính có thể giữ nguyên giá trị entropy của hệ thống nhưng lại không phải là tập tốt nhất cho một bộ phân lớp C4.5. Sự tách biệt giữa quá trình lựa chọn thuộc tính và quá trình huấn luyện mô hình là nhược điểm cốt lõi của phương pháp này, dẫn đến kết quả chưa thực sự tối ưu cho các bài toán học máy.

2.2. Sự đánh đổi giữa tốc độ và độ chính xác phân lớp

Lựa chọn phương pháp rút gọn thuộc tính luôn là một sự đánh đổi. Phương pháp Filter nhanh nhưng độ chính xác có thể không cao. Phương pháp Wrapper cho độ chính xác cao hơn nhưng lại rất chậm, đặc biệt với các tập dữ liệu lớn có hàng ngàn thuộc tính. Các thuật toán như NEW-R [31] dù hiệu quả hơn các thuật toán filter trước đó, vẫn không thoát khỏi hạn chế này. Vấn đề đặt ra là làm thế nào để cân bằng giữa hai yếu tố này: tìm ra một tập rút gọn có số lượng thuộc tính tối thiểu và độ chính xác phân lớp cao nhất, với một chi phí tính toán chấp nhận được. Đây chính là động lực để nghiên cứu các phương pháp lai ghép.

2.3. Nhu cầu tối ưu số lượng thuộc tính và hiệu năng mô hình

Giảm thiểu số lượng thuộc tính không chỉ giúp tăng tốc độ huấn luyện mô hình mà còn có ý nghĩa quan trọng trong việc cải thiện khả năng khái quát hóa. Một mô hình được xây dựng trên quá nhiều thuộc tính (đặc biệt là các thuộc tính nhiễu) có nguy cơ bị "overfitting" (quá khớp), tức là hoạt động tốt trên dữ liệu huấn luyện nhưng kém hiệu quả trên dữ liệu mới. Do đó, việc tìm ra một tập rút gọn nhỏ gọn nhưng giàu thông tin là cực kỳ quan trọng. Các thuật toán filter truyền thống đôi khi giữ lại nhiều thuộc tính hơn mức cần thiết, làm tăng độ phức tạp của mô hình mà không cải thiện đáng kể độ chính xác. Nhu cầu về một thuật toán thông minh hơn, có khả năng tối ưu đồng thời cả hai tiêu chí này là rất rõ ràng.

III. Phương pháp kết hợp Filter Wrapper Hướng đi đột phá hiệu quả

Để khắc phục những nhược điểm của phương pháp Filter truyền thống, hướng tiếp cận kết hợp Filter-Wrapper đã được đề xuất và nghiên cứu. Ý tưởng cốt lõi của phương pháp này là tận dụng tốc độ của giai đoạn Filter và độ chính xác của giai đoạn Wrapper. Thay vì chỉ tìm một tập rút gọn duy nhất, phương pháp này hoạt động theo hai giai đoạn rõ rệt. Giai đoạn đầu (Filter) sẽ nhanh chóng tạo ra một danh sách các "ứng viên" tiềm năng cho tập rút gọn dựa trên một độ đo hiệu quả. Giai đoạn sau (Wrapper) sẽ không cần duyệt qua tất cả 2^M tập con thuộc tính, mà chỉ cần đánh giá trên danh sách các ứng viên đã được sàng lọc, sau đó chọn ra ứng viên cho độ chính xác phân lớp cao nhất. Luận văn của Phạm Quang Nam (2021) đã tìm hiểu và áp dụng thành công phương pháp này cho bảng quyết định không đầy đủ dựa trên lý thuyết tập thô dung sai. Cụ thể, nghiên cứu đã xây dựng một độ đo khoảng cách mới để làm tiêu chuẩn cho giai đoạn Filter. Độ đo này giúp đánh giá mức độ tương đồng giữa các phân hoạch dữ liệu do các tập thuộc tính khác nhau tạo ra. Bằng cách này, thuật toán có thể xác định các thuộc tính quan trọng nhất một cách hiệu quả, tạo tiền đề cho giai đoạn Wrapper lựa chọn ra tập tối ưu cuối cùng, cân bằng được cả về kích thước và hiệu suất phân lớp.

3.1. Giai đoạn Filter Sàng lọc ứng viên tiềm năng

Trong giai đoạn đầu, thuật toán hoạt động tương tự một phương pháp Filter truyền thống. Nó xuất phát từ một tập rỗng và lần lượt bổ sung các thuộc tính có độ quan trọng lớn nhất. Độ quan trọng ở đây được định nghĩa dựa trên một độ đo khoảng cách mới, đo lường sự thay đổi trong khả năng phân lớp khi thêm một thuộc tính vào tập đang xét. Tuy nhiên, khác với phương pháp filter thông thường chỉ dừng lại khi tìm thấy một tập rút gọn, ở đây thuật toán sẽ lưu lại các tập thuộc tính trung gian ở mỗi bước lặp. Các tập này (ví dụ: {a1}, {a1, a3}, {a1, a3, a4},...) chính là những "ứng viên" sẽ được chuyển sang giai đoạn Wrapper để đánh giá.

3.2. Giai đoạn Wrapper Lựa chọn tập rút gọn tối ưu

Sau khi có được danh sách các tập thuộc tính ứng viên từ giai đoạn Filter, giai đoạn Wrapper bắt đầu. Tại đây, mỗi tập ứng viên sẽ được sử dụng để huấn luyện và kiểm thử một mô hình phân lớp cụ thể (ví dụ: C4.5). Độ chính xác của mô hình (thường được đánh giá bằng phương pháp kiểm tra chéo 10-fold) sẽ là tiêu chí để lựa chọn. Tập ứng viên nào mang lại độ chính xác phân lớp cao nhất sẽ được chọn làm tập rút gọn cuối cùng. Cách tiếp cận này đảm bảo rằng tập rút gọn được chọn không chỉ tốt về mặt lý thuyết mà còn tối ưu về mặt hiệu suất thực tế, giải quyết được bài toán cốt lõi mà phương pháp filter đơn thuần bỏ qua.

3.3. Xây dựng độ đo khoảng cách cho bảng quyết định không đầy đủ

Một đóng góp quan trọng của nghiên cứu là việc xây dựng một độ đo khoảng cách mới, ký hiệu là D(P, Q), để đo lường sự khác biệt giữa hai phủ (covering) được sinh ra bởi hai tập thuộc tính P và Q trên một bảng quyết định không đầy đủ. Độ đo này dựa trên sự khác biệt về kích thước giữa hợp và giao của các lớp dung sai tương ứng. Nó thỏa mãn các tính chất của một không gian metric, bao gồm cả bất đẳng thức tam giác. Đặc biệt, độ đo này có tính chất phản đơn điệu, nghĩa là khi tập thuộc tính B càng lớn, khoảng cách D(B, B ∪ {d}) càng nhỏ. Điều này có nghĩa là khả năng phân lớp của B càng cao. Tính chất này làm cho nó trở thành một tiêu chuẩn lý tưởng để định nghĩa độ quan trọng của thuộc tính trong giai đoạn Filter.

IV. Hướng dẫn thuật toán IDS_FW_DAR tìm tập rút gọn tối ưu

Dựa trên phương pháp kết hợp Filter-Wrapper và độ đo khoảng cách mới, thuật toán IDS_FW_DAR (Filter-Wrapper Distance based Approximation Attribute Reduction in Incomplete Decision Tables) đã được nghiên cứu và phát triển. Đây là thuật toán trọng tâm trong luận văn của Phạm Quang Nam [19], được thiết kế để tìm tập rút gọn hiệu quả cho bảng quyết định không đầy đủ. Quy trình của thuật toán bao gồm hai giai đoạn chính. Giai đoạn Filter, được thực hiện bởi thuật toán con IDS_F_DAR, có nhiệm vụ tìm kiếm và tạo ra một chuỗi các tập thuộc tính ứng viên. Nó bắt đầu với tập rỗng, sau đó lặp lại việc tính toán độ quan trọng của các thuộc tính còn lại dựa trên sự thay đổi của độ đo khoảng cách. Thuộc tính có độ quan trọng lớn nhất sẽ được thêm vào tập đang xét. Mỗi tập được tạo ra trong quá trình này sẽ được lưu lại như một ứng viên. Giai đoạn Wrapper tiếp nhận chuỗi ứng viên này, sau đó sử dụng một bộ phân lớp (như C4.5) để đánh giá độ chính xác của từng ứng viên. Tập ứng viên nào cho kết quả phân lớp tốt nhất sẽ được công nhận là tập rút gọn cuối cùng. Về độ phức tạp, giai đoạn Filter có độ phức tạp là O(|C|^2 * |U|^2), trong khi giai đoạn Wrapper phụ thuộc vào bộ phân lớp được sử dụng. Mặc dù chi phí tính toán cao hơn so với các thuật toán filter đơn thuần, IDS_FW_DAR mang lại hiệu quả vượt trội về chất lượng của tập rút gọn.

4.1. Quy trình thực thi thuật toán IDS_F_DAR Filter

Thuật toán IDS_F_DAR là trái tim của giai đoạn Filter. Đầu vào là một bảng quyết định không đầy đủ. Đầu tiên, thuật toán tính toán các ma trận dung sai và các giá trị khoảng cách ban đầu. Sau đó, nó bước vào một vòng lặp: trong mỗi lần lặp, nó tính độ quan trọng SIG(b) cho mọi thuộc tính b chưa được chọn. Độ quan trọng này được định nghĩa là sự sụt giảm của giá trị khoảng cách khi thêm b vào tập hiện tại. Thuộc tính có độ quan trọng lớn nhất sẽ được chọn và thêm vào tập. Tập mới này được lưu lại như một ứng viên. Quá trình này tiếp tục cho đến khi việc thêm thuộc tính không còn cải thiện đáng kể khả năng phân lớp (tức là giá trị khoảng cách đạt đến ngưỡng của tập thuộc tính đầy đủ).

4.2. Tích hợp Wrapper để tối ưu độ chính xác phân lớp

Sau khi IDS_F_DAR kết thúc, chúng ta có một danh sách các tập ứng viên, ví dụ T = {{a3}, {a3, a4}, ...}. Giai đoạn Wrapper sẽ duyệt qua danh sách này. Với mỗi tập ứng viên Ti, một bộ phân lớp (ví dụ C4.5) sẽ được huấn luyện trên dữ liệu chỉ chứa các thuộc tính trong Ti. Độ chính xác của bộ phân lớp này được ghi nhận. Sau khi đánh giá tất cả các ứng viên, thuật toán sẽ so sánh các độ chính xác và chọn ra tập ứng viên T_best tương ứng với độ chính xác cao nhất. T_best chính là tập rút gọn cuối cùng mà thuật toán IDS_FW_DAR trả về. Quy trình này đảm bảo kết quả đầu ra được tối ưu hóa cho hiệu suất học máy thực tế.

4.3. Đánh giá kết quả thực nghiệm và so sánh hiệu quả

Để chứng minh tính hiệu quả, thuật toán IDS_FW_DAR đã được thử nghiệm trên 10 bộ dữ liệu từ kho UCI [36] và so sánh với hai thuật toán filter khác là NEW-R [31] và IDS_F_DAR. Kết quả cho thấy IDS_FW_DAR giảm thiểu đáng kể số lượng thuộc tính trong tập rút gọn so với hai thuật toán còn lại. Ví dụ, trên bộ dữ liệu Audiology, IDS_FW_DAR chỉ giữ lại 13 thuộc tính so với 45 của NEW-R. Về độ chính xác, IDS_FW_DAR duy trì hoặc cải thiện hiệu suất phân lớp trên hầu hết các bộ dữ liệu. Mặc dù thời gian thực thi của nó lâu hơn do phải chạy các bộ phân lớp, nhưng sự đánh đổi này là hợp lý đối với các bài toán yêu cầu mô hình có độ phức tạp thấp và độ chính xác cao, đặc biệt là dữ liệu y sinh hoặc tài chính.

V. Bí quyết ứng dụng ảnh vệ tinh để phát hiện tàu thuyền hiệu quả

Một trong những ứng dụng thực tiễn nổi bật của thuật toán rút gọn bảng quyết định là trong lĩnh vực viễn thám, cụ thể là bài toán phát hiện tàu thuyền từ ảnh vệ tinh. Ảnh vệ tinh có độ phân giải cao (từ VNREDSat-1, Landsat 8) chứa một lượng thông tin khổng lồ. Tuy nhiên, các đối tượng như tàu thuyền thường chỉ chiếm một phần rất nhỏ trong ảnh, gây khó khăn cho việc nhận dạng tự động. Việc phân tích thủ công (giải đoán bằng mắt) tốn nhiều thời gian và không hiệu quả. Mô hình được đề xuất trong luận văn đã giải quyết bài toán này bằng cách biến mỗi ảnh thành một tập dữ liệu lớn. Đầu tiên, ảnh được tiền xử lý và chia thành các cửa sổ nhỏ hơn (ví dụ: 64x64 pixel). Mỗi cửa sổ được xem là một đối tượng, và giá trị mức xám của từng pixel trong cửa sổ được coi là một thuộc tính. Điều này dẫn đến một bảng quyết định với hàng nghìn thuộc tính (4096 thuộc tính cho cửa sổ 64x64). Áp dụng trực tiếp các thuật toán học máy trên dữ liệu đa chiều như vậy là không khả thi. Đây là lúc thuật toán IDS_FW_DAR phát huy vai trò. Nó giúp rút gọn 4096 thuộc tính xuống một con số nhỏ hơn nhiều, chỉ giữ lại những pixel (thuộc tính) quan trọng nhất để phân biệt giữa cửa sổ có tàu và không có tàu, giúp mô hình phân lớp hoạt động nhanh và chính xác hơn.

5.1. Mô hình phân lớp đối tượng từ ảnh viễn thám độ phân giải cao

Mô hình giải quyết bài toán phát hiện tàu thuyền được chia thành hai giai đoạn. Giai đoạn 1 là xây dựng mô hình phân lớp. Ảnh viễn thám được xử lý, chia nhỏ bằng kỹ thuật "cửa sổ trượt", và gán nhãn thủ công (1 cho có tàu, 0 cho không có tàu). Các thuộc tính (pixel) được trích xuất, sau đó thuật toán IDS_FW_DAR được áp dụng để tìm ra tập thuộc tính rút gọn. Cuối cùng, một bộ phân lớp (SVM, KNN, ...) được huấn luyện trên tập dữ liệu đã rút gọn này. Giai đoạn 2 là thực thi mô hình. Một ảnh vệ tinh mới sẽ được xử lý tương tự, các thuộc tính rút gọn được trích xuất và đưa vào bộ phân lớp đã huấn luyện để gán nhãn cho từng cửa sổ. Nếu bất kỳ cửa sổ nào được gán nhãn 1, toàn bộ ảnh sẽ được đánh dấu là "có tàu thuyền".

5.2. Tiền xử lý và trích chọn thuộc tính từ dữ liệu ảnh vệ tinh

Chất lượng của mô hình phụ thuộc rất nhiều vào bước tiền xử lý. Dữ liệu ảnh vệ tinh thô cần được xử lý để loại bỏ nhiễu và tách kênh ảnh phù hợp (ví dụ, kênh nhạy cảm với mặt nước). Sau đó, kỹ thuật cửa sổ trượt sẽ quét qua toàn bộ ảnh, tạo ra hàng ngàn cửa sổ con. Mỗi cửa sổ này trở thành một hàng trong bảng dữ liệu. Mỗi pixel trong cửa sổ trở thành một cột (thuộc tính). Ví dụ, một cửa sổ kích thước 80x80 pixel sẽ tạo ra 6400 thuộc tính. Giá trị của mỗi thuộc tính là cường độ sáng của pixel đó (từ 0-255). Quá trình này biến bài toán xử lý ảnh thành một bài toán khai phá dữ liệu trên một bảng quyết định có số chiều rất cao, nơi mà việc rút gọn thuộc tính là bước bắt buộc.

5.3. Kết quả thực tiễn Rút gọn đặc trưng và phân loại tàu thuyền

Việc áp dụng thuật toán rút gọn bảng quyết định đã mang lại kết quả tích cực. Thay vì phải xử lý hàng nghìn thuộc tính cho mỗi cửa sổ ảnh, mô hình chỉ cần làm việc với một tập con nhỏ hơn nhiều. Điều này không chỉ giảm đáng kể thời gian huấn luyện và dự đoán mà còn giúp mô hình tập trung vào những đặc trưng thực sự quan trọng, tránh được nhiễu từ các pixel không liên quan (như các pixel của mặt nước hoặc mây). Kết quả là một hệ thống tự động có khả năng phân lớp ảnh vệ tinh với độ chính xác cao, hỗ trợ hiệu quả cho các nhiệm vụ an ninh quốc phòng, giám sát hàng hải và cứu hộ cứu nạn. Đây là một minh chứng rõ ràng về giá trị thực tiễn của các nghiên cứu lý thuyết trong lĩnh vực học máy.

VI. Tương lai của thuật toán rút gọn bảng quyết định và học máy

Nghiên cứu về thuật toán rút gọn bảng quyết định, đặc biệt là phương pháp kết hợp Filter-Wrapper như IDS_FW_DAR, đã mở ra nhiều hướng đi mới cho lĩnh vực học máy và khai phá dữ liệu. Thành công trong việc xử lý bảng quyết định không đầy đủ và ứng dụng trong phân tích ảnh vệ tinh cho thấy tiềm năng to lớn của các kỹ thuật này. Ưu điểm vượt trội của phương pháp lai ghép là khả năng cân bằng giữa hiệu suất tính toán và độ chính xác của mô hình, giải quyết được bài toán đánh đổi kinh điển trong lựa chọn thuộc tính. Tuy nhiên, vẫn còn những thách thức cần được giải quyết. Thời gian tính toán của giai đoạn Wrapper vẫn là một rào cản đối với các bộ dữ liệu siêu lớn (big data). Trong tương lai, các nghiên cứu có thể tập trung vào việc tối ưu hóa giai đoạn này, ví dụ như sử dụng các kỹ thuật tìm kiếm thông minh hơn hoặc tính toán song song. Hơn nữa, việc mở rộng các thuật toán này để xử lý các loại dữ liệu phức tạp hơn như dữ liệu chuỗi thời gian, dữ liệu đồ thị, hay dữ liệu không đồng nhất cũng là một hướng phát triển đầy hứa hẹn. Tiềm năng ứng dụng của chúng không chỉ giới hạn trong viễn thám mà còn có thể mở rộng sang các lĩnh vực quan trọng khác như chẩn đoán y tế, phân tích tài chính, và an ninh mạng.

6.1. Tóm tắt ưu điểm vượt trội của phương pháp Filter Wrapper

Phương pháp Filter-Wrapper kết hợp những gì tốt nhất của hai thế giới. Nó sử dụng tốc độ của Filter để nhanh chóng sàng lọc và tạo ra một tập hợp các ứng viên thuộc tính có chất lượng cao. Sau đó, nó sử dụng sự chính xác của Wrapper để kiểm định và chọn ra ứng viên tối ưu nhất dựa trên hiệu suất thực tế của mô hình học máy. Kết quả là một tập rút gọn vừa nhỏ gọn (giảm độ phức tạp mô hình) vừa mạnh mẽ (tăng độ chính xác phân lớp). Đây là một giải pháp toàn diện hơn nhiều so với việc chỉ sử dụng một trong hai phương pháp một cách riêng lẻ, đặc biệt hiệu quả cho các bảng quyết định không đầy đủ.

6.2. Hạn chế và các bài toán cần giải quyết trong tương lai

Mặc dù hiệu quả, thuật toán IDS_FW_DAR vẫn có hạn chế về thời gian thực thi. Giai đoạn Wrapper yêu cầu huấn luyện nhiều mô hình phân lớp, điều này có thể trở nên tốn kém khi số lượng ứng viên lớn hoặc mô hình phân lớp phức tạp. Một hướng nghiên cứu trong tương lai là phát triển các chiến lược để giảm số lượng ứng viên cần đánh giá mà không làm giảm chất lượng. Ngoài ra, việc xác định các độ đo (như độ đo khoảng cách) phù hợp cho các loại dữ liệu khác nhau ngoài dữ liệu dạng bảng cũng là một thách thức mở, cần được tiếp tục nghiên cứu để mở rộng phạm vi ứng dụng của phương pháp.

6.3. Tiềm năng ứng dụng trong lĩnh vực y tế và tài chính

Ngoài viễn thám, thuật toán rút gọn bảng quyết định có tiềm năng ứng dụng rất lớn trong các lĩnh vực khác. Trong y tế, dữ liệu bệnh án thường có hàng trăm thuộc tính (kết quả xét nghiệm, triệu chứng) và thường xuyên bị thiếu thông tin. Việc áp dụng các thuật toán này có thể giúp xác định các chỉ số sinh học quan trọng nhất để chẩn đoán bệnh sớm. Trong tài chính, chúng có thể được sử dụng để phân tích rủi ro tín dụng, xác định các yếu tố chính ảnh hưởng đến khả năng vỡ nợ của khách hàng từ dữ liệu giao dịch khổng lồ, giúp các tổ chức đưa ra quyết định chính xác và kịp thời hơ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 trong mấy năm gần đây. Nội dung chính của luận văn được trình bày trong chương 2. Chương 2 trình bày kết quả tìm hiểu về xây dựng độ đo khoảng cách mới và thuật toán filter-wrapper IDS_FW_DAR tìm tập rút gọn của bảng quyết định không đầy đủ. Chương 3 áp dụng thuật toán filter-wrapper IDS_FW_DAR vào bài toán phát hiện tàu thuyền từ ảnh vệ tinh.

Cuối cùng, phần kết luận nêu những nội dung đã tìm hiểu của luận văn, hướng phát triển tiếp theo. 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 [3] đề 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 vă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 [3], 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 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). 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 POS B ( 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, POSB ( D) = u U u   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 [4] đề xuất.

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). 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 SP ( u )  X = u  X SP (u )  X   PX = u U SP ( u )  X   =  S (u ) u U P 7 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 POS P ( 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, POS P ( D ) = u  U S P ( 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 DS là một hệ thông tin 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 = .

Xét bảng quyết định DS = (U , C  D ) , nếu tồn tại u U và c  C sao cho c ( u ) thiếu giá trị thì DS được gọi là bảng quyết định không đầy đủ, trái lại DS được gọi là bảng quyết định đầy đủ. Ta biểu diễn bảng quyết định không đầy đủ là IDS = (U , C  D ) với d  D, '*'  Vd. Không mất tính chất tổng quát, giả thiết D chỉ gồm một thuộc tính quyết định duy nhất d . Cho bảng quyết định không đầy đủ IDS = (U , C  d ).

Với P  C , u U ,  P (u ) = d ( v ) v  S P (u ) gọi là hàm quyết định suy rộng của đối tượng u trên tập thuộc tính P. Nếu |  C (u ) |= 1 với mọi u U thì IDS là nhất quán, trái lại IDS là không nhất quán.