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.

Nội dung chính

Tổng quan nghiên cứu

Sự bùng nổ dữ liệu số trong kỷ nguyên trí tuệ nhân tạo khiến các hệ thống thông tin phải đối mặt với các bảng dữ liệu khổng lồ chứa từ hàng chục đến hàng nghìn thuộc tính. Trong thực tế thu thập dữ liệu, tỷ lệ khuyết thiếu giá trị thường dao động từ 5% đến hơn 30%, điển hình như hồ sơ bệnh án hoặc giao dịch tài chính. Việc loại bỏ bản ghi hay gán giá trị nhân tạo dễ gây sai lệch tri thức và làm suy giảm hiệu năng của các mô hình học máy.

Bài toán đặt ra cho nghiên cứu là tìm kiếm giải pháp 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 qua bước tiền xử lý điền giá trị thiếu. Mục tiêu cụ thể của luận văn là nghiên cứu, phát triển thuật toán lai kết hợp giữa bộ lọc và đóng gói mang tên IDS_FW_DAR, dựa trên nền tảng lý thuyết tập thô dung sai và độ đo khoảng cách mới. Mục tiêu này hướng tới việc tối thiểu hóa số lượng chiều dữ liệu và nâng cao độ chính xác phân lớp so với các giải thuật truyền thống.

Nghiên cứu được thực hiện trong giai đoạn từ năm 2019 đến năm 2021 tại Học viện Khoa học và Công nghệ thuộc Viện Hàn lâm Khoa học và Công nghệ Việt Nam. Luận văn thuộc chuyên ngành Hệ thống thông tin, mã số 8480104, dưới sự hướng dẫn khoa học của Phó Giáo sư, Tiến sĩ Nguyễn Long Giang. Phạm vi thực nghiệm bao gồm 10 bộ dữ liệu chuẩn quốc tế từ kho lưu trữ UCI và tập dữ liệu ảnh viễn thám thực tế từ vệ tinh VNREDSat-1 của Việt Nam cùng các nguồn ảnh vệ tinh Landsat 8 và Sentinel 2A.

Ý nghĩa khoa học và thực tiễn của đề tài được khẳng định qua việc cắt giảm hơn 50% số chiều dữ liệu dư thừa, đồng thời cải thiện độ chính xác phân lớp từ 2% đến 10% trên các bộ dữ liệu phức tạp. Kết quả nghiên cứu cung cấp một công cụ hiệu quả cho bài toán phát hiện tàu thuyền trên biển phục vụ an ninh quốc phòng và cứu hộ cứu nạn.

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

Khung lý thuyết áp dụng

Nghiên cứu xây dựng trên nền tảng lý thuyết tập thô truyền thống do Zdzisław Pawlak đề xuất năm 1982, vốn sử dụng quan hệ tương đương để xấp xỉ tập hợp. Để xử lý các bảng quyết định không đầy đủ chứa giá trị thiếu ký hiệu là dấu sao, luận văn mở rộng sang mô hình tập thô dung sai do Ewa Kryszkiewicz khởi xướng. Quan hệ dung sai thỏa mãn tính phản xạ và đối xứng nhưng không bắc cầu, từ đó tạo nên các lớp dung sai bao phủ không gian đối tượng.

Khung lý thuyết của luận văn tập trung vào 5 khái niệm cốt lõi:

1. Hệ thông tin không đầy đủ và bảng quyết định không đầy đủ chứa tập thuộc tính điều kiện và thuộc tính quyết định.
2. Lớp dung sai của đối tượng, đại diện cho tập hợp các phần tử không phân biệt được với đối tượng khảo sát.
3. Miền xấp xỉ dưới, xấp xỉ trên và miền dương của thuộc tính quyết định.
4. Ma trận dung sai biểu diễn mối quan hệ tương đồng giữa các cặp đối tượng dưới dạng nhị phân 0 và 1.
5. Độ đo khoảng cách mới giữa các phủ sinh bởi tập thuộc tính điều kiện và thuộc tính quyết định, thỏa mãn bất đẳng thức tam giác và tính phản đơn điệu.

Nghiên cứu kết hợp hai trường phái trích chọn đặc trưng: tiếp cận bộ lọc giúp sàng lọc nhanh các tập ứng viên rút gọn xấp xỉ thông qua độ quan trọng khoảng cách, và tiếp cận đóng gói sử dụng chính thuật toán phân lớp để đánh giá trực tiếp độ chính xác nhằm chọn ra tập đặc trưng tối ưu nhất.

Phương pháp nghiên cứu

Nguồn dữ liệu thực nghiệm gồm 10 bộ dữ liệu chuẩn từ kho UCI Machine Learning Repository với quy mô đa dạng: từ bộ Hepatitis có 155 đối tượng và 19 thuộc tính, Arrhythmia có 452 đối tượng và 279 thuộc tính, đến Advertisements có 3279 đối tượng và 1558 thuộc tính, cùng Mushroom với 8124 đối tượng và 22 thuộc tính. Nguồn dữ liệu ứng dụng thực tế sử dụng các phân cảnh ảnh vệ tinh quang học VNREDSat-1 thu nhận tại vùng biển Việt Nam.

Quy trình chọn mẫu và kiểm thử áp dụng phương pháp kiểm chứng chéo 10 phần ngẫu nhiên. Toàn bộ tập dữ liệu được phân chia thành 10 tập con cân bằng; trong mỗi vòng lặp, 9 phần được dùng để huấn luyện mô hình và 1 phần độc lập dùng để đánh giá độ chính xác, lặp lại 10 lần để lấy giá trị trung bình.

Lý do lựa chọn thuật toán cây quyết định C4.5 trong giai đoạn đóng gói là nhờ khả năng xử lý tốt dữ liệu dạng bảng, tốc độ huấn luyện nhanh và tính minh bạch của các luật quyết định sinh ra. Quy trình phân tích ảnh viễn thám kết hợp kỹ thuật cửa sổ trượt phân tách ảnh thành các khối 64x64 điểm ảnh, tạo ra không gian 4096 chiều đặc trưng mức xám để thuật toán IDS_FW_DAR thực hiện rút gọn. Toàn bộ hệ thống được lập trình trên nền tảng ngôn ngữ Python 3.9 kết hợp thư viện Scikit-learn, OpenCV và công cụ Matlab R2016a trong khung thời gian 24 tháng.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình thực nghiệm so sánh thuật toán lai IDS_FW_DAR với hai giải thuật lọc tiêu biểu là IDS_F_DAR và NEW-R dựa trên độ không nhất quán đã mang lại 4 phát hiện quan trọng:

Thứ nhất, thuật toán IDS_FW_DAR cho thấy khả năng tinh gọn số lượng thuộc tính vượt trội. Trên toàn bộ 10 bộ dữ liệu UCI, số thuộc tính trong tập rút gọn của IDS_FW_DAR luôn thấp hơn từ 25% đến 60% so với hai thuật toán lọc còn lại. Điển hình ở bộ dữ liệu Anneal gồm 38 thuộc tính gốc, thuật toán đã loại bỏ hơn 70% số chiều không cần thiết mà vẫn giữ được đặc trưng phân lớp cốt lõi.

Thứ hai, độ chính xác phân lớp được cải thiện rõ rệt trên 6 trên 10 bộ dữ liệu thử nghiệm bao gồm Audiology, Soybean-large, Congressional Voting Records, Arrhythmia, Anneal và Advertisements. Trên 4 bộ dữ liệu còn lại, độ chính xác đạt mức tương đương các thuật toán gốc.

Thứ ba, đối với các tập dữ liệu có số chiều cực lớn và độ chính xác phân lớp ban đầu thấp như Advertisements với 1558 thuộc tính, thuật toán lai đã giúp tăng độ chính xác phân lớp thêm khoảng 8% so với phương pháp lọc đơn thuần.

Thứ tư, trong bài toán ứng dụng thực tế phát hiện tàu thuyền từ ảnh vệ tinh VNREDSat-1, thuật toán đã giảm thành công không gian 4096 đặc trưng điểm ảnh của mỗi cửa sổ trượt xuống còn một tập hữu hạn các thuộc tính nhạy cảm, giúp phát hiện chính xác các mục tiêu tàu thuyền kích thước nhỏ trên nền biển nhiễu sóng.

Thảo luận kết quả

Nguyên nhân chính giúp thuật toán lai IDS_FW_DAR vượt trội hơn các giải thuật truyền thống như POS-R sử dụng miền dương hay INF-R sử dụng entropy thông tin nằm ở cơ chế tương tác hai giai đoạn. Các thuật toán lọc truyền thống chỉ tối ưu hóa dựa trên một độ đo toán học cố định mà không đánh giá phản hồi từ thuật toán học máy, dẫn đến việc giữ lại các thuộc tính tuy thỏa mãn độ đo nhưng lại gây nhiễu cho bộ phân lớp. Giai đoạn đóng gói của IDS_FW_DAR đã khắc phục triệt để nhược điểm này bằng cách sử dụng cây quyết định C4.5 để kiểm định độ chính xác thực tế của từng tập ứng viên xấp xỉ.

Về chi phí tính toán, tổng thời gian thực thi của thuật toán IDS_FW_DAR cao hơn các thuật toán lọc đơn thuần từ 1,5 đến 3 lần tùy thuộc vào quy mô dữ liệu. Điều này là hoàn toàn hợp lý vì giải thuật phải thực thi thêm các vòng lặp kiểm tra chéo của bộ phân lớp C4.5. Tuy nhiên, giai đoạn lọc ban đầu đã hoàn thành xuất sắc nhiệm vụ thu hẹp không gian tìm kiếm, giúp thời gian chạy của pha đóng gói chỉ chiếm khoảng 35% tổng thời lượng xử lý.

Các kết quả thực nghiệm có thể được trực quan hóa sinh động thông qua biểu đồ cột kép so sánh số lượng thuộc tính rút gọn và biểu đồ đường thể hiện tỷ lệ phần trăm độ chính xác phân lớp giữa ba thuật toán trên 10 bộ dữ liệu. Đồ thị thời gian thực thi cũng phản ánh rõ mối tương quan giữa số lượng mẫu, số chiều dữ liệu và tốc độ hội tụ của từng giải thuật.

Đề xuất và khuyến nghị

Dựa trên kết quả nghiên cứu lý thuyết và thử nghiệm ứng dụng, 4 đề xuất cụ thể được đưa ra nhằm chuyển giao công nghệ và nâng cao hiệu quả khai thác:

Thứ nhất, tích hợp mô hình phân lớp và rút gọn đặc trưng IDS_FW_DAR vào hệ thống phần mềm giám sát tàu thuyền tự động cho Trung tâm Vũ trụ Việt Nam và Cục Kiểm ngư. Mục tiêu là tự động hóa 100% quy trình rà quét ảnh viễn thám VNREDSat-1 và Sentinel 2A, cắt giảm khoảng 40% thời gian xử lý thủ công của chuyên viên giải đoán ảnh, hoàn thành triển khai thử nghiệm trong vòng 12 tháng tới.

Thứ hai, mở rộng ứng dụng giải thuật sang lĩnh vực y tế và ngân hàng nhằm xử lý các cơ sở dữ liệu bệnh án điện tử và hồ sơ tín dụng có tỷ lệ khuyết thiếu thông tin từ 15% đến 30%. Các bệnh viện tuyến trung ương và viện nghiên cứu y sinh có thể áp dụng thuật toán trong giai đoạn 2022-2024 để tăng tốc độ chẩn đoán bệnh lý phức tạp từ 15% đến 20%.

Thứ ba, nhóm nghiên cứu phát triển cần tối ưu hóa mã nguồn thuật toán thông qua kỹ thuật tính toán song song đa luồng và tăng tốc phần cứng trên nền tảng GPU. Giải pháp này hướng tới việc giảm ít nhất 50% thời gian tính toán của giai đoạn đóng gói đối với các tập dữ liệu có quy mô trên 10000 bản ghi, dự kiến thực hiện trong khung thời gian 6 đến 9 tháng.

Thứ tư, nâng cấp mô hình phân lớp bằng cách kết hợp thuật toán rút gọn tập thô dung sai với các kiến trúc mạng nơ-ron tích chập sâu. Nhóm tác giả tại các viện chuyên ngành Công nghệ thông tin nên tiến hành nghiên cứu này trong vòng 2 năm để nâng cao độ nhạy phát hiện phương tiện hàng hải trong điều kiện mây che phủ trên 20%.

Đối tượng nên tham khảo luận văn

Nội dung và kết quả của luận văn mang lại giá trị thiết thực cho 4 nhóm đối tượng chính:

Thứ nhất, các nhà khoa học dữ liệu và kỹ sư học máy đang tìm kiếm giải pháp tiền xử lý dữ liệu dạng bảng. Luận văn cung cấp phương pháp luận hoàn chỉnh để giải quyết triệt để bài toán giảm chiều dữ liệu bị khuyết thiếu giá trị mà không làm sai lệch phân phối thông tin ban đầu.

Thứ hai, các chuyên gia viễn thám và an ninh hàng hải phụ trách giám sát chủ quyền biển đảo. Tài liệu cung cấp quy trình công nghệ chi tiết từ tách kênh, khử nhiễu, phân tách cửa sổ trượt đến huấn luyện bộ phân lớp phát hiện mục tiêu kích thước nhỏ trên ảnh viễn thám VNREDSat-1.

Thứ ba, giảng viên, nghiên cứu sinh và học viên cao học ngành Khoa học máy tính và Hệ thống thông tin. Luận văn là tài liệu tham khảo giá trị về việc vận dụng lý thuyết tập thô mở rộng, xây dựng không gian khoảng cách toán học và thiết kế thuật toán tìm kiếm heuristic.

Thứ tư, các kỹ sư phát triển phần mềm ứng dụng trong tài chính và y tế. Tài liệu hướng dẫn phương thức xây dựng giao diện người dùng bằng Python để tích hợp các mô hình trí tuệ nhân tạo vào quy trình nghiệp vụ thực tế.

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

Thuật toán IDS_FW_DAR xử lý dữ liệu khuyết thiếu như thế nào mà không cần điền giá trị? Thuật toán sử dụng mô hình tập thô dung sai để thiết lập quan hệ dung sai giữa các đối tượng. Khi một thuộc tính chứa giá trị thiếu ký hiệu là dấu sao, quan hệ dung sai mặc định đối tượng đó tương đồng với mọi đối tượng khác trên thuộc tính đó, cho phép tính toán ma trận dung sai trực tiếp mà không cần gán giá trị giả định.

Điểm khác biệt cốt lõi giữa tiếp cận lọc và tiếp cận lai lọc kết hợp đóng gói là gì? Phương pháp lọc chỉ lựa chọn thuộc tính dựa vào độ quan trọng đo bằng công thức toán học thuần túy nên có tốc độ nhanh nhưng độ chính xác chưa tối ưu. Phương pháp lai tận dụng bộ lọc để tìm các tập rút gọn ứng viên, sau đó dùng thuật toán học máy C4.5 trong pha đóng gói để chọn ra tập đặc trưng có độ chính xác phân lớp cao nhất.

Tại sao độ đo khoảng cách lại được chọn làm tiêu chuẩn đánh giá thuộc tính? Độ đo khoảng cách giữa hai phủ tập hợp có tính chất phản đơn điệu: khi bổ sung thuộc tính có ích, khoảng cách giữa phủ điều kiện và phủ quyết định sẽ thu hẹp lại. Thuộc tính nào làm giảm khoảng cách nhiều nhất sẽ có độ quan trọng lớn nhất, giúp thuật toán heuristic nhanh chóng hội tụ về tập rút gọn tối ưu.

Mô hình phân lớp cửa sổ trượt trên ảnh vệ tinh VNREDSat-1 hoạt động ra sao? Ảnh viễn thám sau khi lọc nhiễu được chia thành các ô lưới kích thước 64x64 điểm ảnh bằng kỹ thuật cửa sổ trượt. Mỗi ô lưới tạo thành một đối tượng dữ liệu với 4096 thuộc tính mức xám từ 0 đến 255. Thuật toán sẽ rút gọn không gian 4096 chiều này trước khi đưa vào mô hình phân lớp nhị phân để kết luận ô ảnh có tàu thuyền hay không.

Thuật toán này có thể áp dụng cho các định dạng dữ liệu khác ngoài ảnh viễn thám không? Thuật toán hoàn toàn tương thích với mọi loại dữ liệu dạng bảng có thuộc tính rời rạc hoặc liên tục đã qua bước rời rạc hóa. Thực nghiệm trên 10 bộ dữ liệu UCI trong các lĩnh vực y tế, sinh học, quảng cáo và bình chọn chính trị đã chứng minh tính tổng quát và khả năng thích ứng đa dạng của giải thuật.

Kết luận

Luận văn đã hoàn thành xuất sắc các mục tiêu nghiên cứu với những đóng góp khoa học và thực tiễn nổi bật:

• Xây dựng thành công độ đo khoảng cách mới trên bảng quyết định không đầy đủ thỏa mãn đầy đủ các tiên đề khoảng cách toán học.
• Đề xuất thuật toán lai IDS_FW_DAR kết hợp hài hòa ưu điểm tốc độ của bộ lọc và độ chính xác của bộ đóng gói.
• Chứng minh hiệu quả vượt trội của thuật toán trên 10 bộ dữ liệu chuẩn quốc tế UCI, giúp giảm mạnh số chiều dữ liệu và nâng cao độ chính xác phân lớp.
• Ứng dụng thành công giải thuật vào bài toán thực tiễn phát hiện tàu thuyền từ dữ liệu ảnh vệ tinh VNREDSat-1 thông qua phần mềm hoàn chỉnh.
• Mở ra hướng nghiên cứu kết hợp lý thuyết tập thô với học sâu trên dữ liệu lớn trong giai đoạn phát triển tiếp theo.

Các cơ quan quản lý, viện nghiên cứu và doanh nghiệp công nghệ có thể liên hệ tham khảo toàn văn công trình để nhận chuyển giao giải pháp và phối hợp triển khai thực tế.

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.