Mở đầu Rút gọn thuộc tính (attribute reduction) hay còn được gọi lựa chọn đặc trưng (fea- ture selection) là một trong những bước tiền xử lý dữ liệu quan trọng trong các lĩnh vực nhận dạng (pattern recognition), học máy (machine learning) và khai thác dữ liệu (data mining). Đối với các tập dữ liệu dành cho các bài toán học không giám sát (un- supervised - learning), rút gọn thuộc tính nhằm lựa chọn một tập con của tập thuộc tính ban đầu bảo toàn thông tin của tập thuộc tính gốc. Đối với các tập dữ liệu cho các bài toán học có giám sát (supervised - learning), rút gọn thuộc tính nhằm chọn ra một tập con của tập thuộc tính ban đầu bảo toàn khả năng phân lớp hay dự báo so với tập thuộc tính gốc [53]. Có ba mô hình tiếp cận chính để xây dựng các thuật toán rút gọn thuộc tính gồm có mô hình filter, wrapper và embed thuộc tính.
Trong đó tiếp cận Filter là tiếp cận được sử dụng rộng rãi nhất. Cách tiếp cận Wrapper thường được gắn với một mô hình phân lớp cụ thể để đánh giá tập thuộc tính rút gọn ứng viên tốt nhất về khả năng phân lớp. Tuy nhiên với C thuộc tính ta cần đánh giá tới 2C tập con thuộc tính, do đó cách tiếp cận này có chi phí tính toán rất lớn. Gần đây, một số mô hình lai ghép filter và wrapper, trong đó kỹ thuật wrapper được cải tiến để đánh giá trên các reduct ứng viên có số lượng nhỏ.
Với cách tiếp cận embed, việc đánh giá thuộc tính hay tập thuộc tính thường được gắn trực tiếp vào một mô hình cụ thể, ví dụ mô hình cây quyết định thì luật thu được từ mô hình này thường ngắn gọn hơn so với luật quyết định của bảng dữ liệu huấn luyện. Tuy nhiên tập thuộc tính rút gọn thu được theo cách tiếp cận Wrapper hay Embed chỉ phù hợp với một mô hình học máy cụ thể, nếu sử dụng reduct đó sang mô hình học máy khác có thể sẽ 9 không hiệu quả. Do đó, cho đến nay tiếp cận Filter vẫn được các nhà khoa học lựa chọn nhiều hơn cả do mục tiêu đánh giá tập thuộc tính rút gọn được khái quát theo tiêu chí bảo toàn thông tin của reduct so với tập dữ liệu gốc. Để xây dựng các thuật toán rút gọn thuộc tính, mô hình chung cho các thuật toán gồm có hai thành phần chính như sau: - Tiêu chuẩn chọn lọc thuộc tính: bao gồm các phương pháp đánh giá độ quan trọng của thuộc tính như dựa trên độ đo được định nghĩa hay cấu trúc tôpô được định nghĩa.
- Phương pháp tìm kiếm: chủ yếu dựa vào tiếp cận Heuristic như tìm kiếm thuộc tính quan trọng dựa trên tập thuộc tính ban đầu, dựa trên tập thuộc tính lõi hay xuất phát từ tập rỗng. Các thuộc tính điều kiện trong bảng quyết định có thể được chia làm 03 nhóm có tính chất như sau: - Tính độc lập (Independent): Bao gồm các thuộc tính điều kiện không tương quan với các thuộc tính điều kiện khác nhưng tương quan với thuộc tính quyết định. - Tính dư thừa (Redundant): Bao gồm các thuộc tính điều kiện có tương quan với các thuộc tính điều kiện khác nhưng không tương quan với thuộc tính quyết định. - Tính không phù hợp: Bao gồm các thuộc tính điều kiện không tương quan với các thuộc tính điều kiện khác mà cũng không tương quan với thuộc tính quyết định.
Bên cạnh phương pháp rút gọn thuộc tính truyền thống đã được phát triển hơn ba thập kỉ vừa qua, trong những năm gần đây nhiều nhà nghiên cứu đề xuất cách tiếp cận rút gọn thuộc tính theo tiếp cận tôpô đại số, cách tiếp cận này nhận được nhiều sự quan tâm của cộng động các nhà nghiên cứu lý thuyết về RS, tôpôlogy và tôpô đại số do một số công trình công bố đã chỉ ra sự tương quan khá gần gũi giữa mô hình RS cổ điển và không gian tôpô, đặc biệt về ý bài toán rút gọn thuộc tính có liên quan đến khái niệm bất biến của không gian tôpô dưới góc nhìn của đại số trừu tượng. Các khái niệm cơ bản 1. Hệ thông tin và mô hình RS truyền thống 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 A cột ứng với A thuộc tính và U hàng ứng với U đối tượng. Một cách hình thức, hệ thông tin được định nghĩa như sau.
Hệ thông tin là một bộ tứ IS = (U, A,V, f ) trong đó 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, V = Va với Va là tập giá trị của thuộc tính a ∈ A và f : U × A → Va là hàm S a∈A thông tin, ∀a ∈ A, u ∈ U ta có f (u, a) ∈ Va. 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 DT 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à DT = (U,C, D, f ) với C ∩ D = 0.
/ Xét bảng quyết định DT = (U,C, D, f ) với giả thiết ∀u ∈ U, ∀d ∈ D đầy đủ giá trị, nếu tồn tại u ∈ U và c ∈ C sao cho c (u) thiếu giá trị thì DT được gọi là bảng quyết định không đầy đủ, trái lại DT được gọi là bảng quyết định đầy đủ. Xét bảng quyết định DT = (U,C, D, f ). Khi đó, quan hệ của các đối tượng trong U trên tập thuộc tính B ⊆ C ký hiệu bới ID (B), được định nghĩa bởi: ID (B) = {(u, v) ∈ U |∀a ∈ B, a (u) = a (v)} (1.1) Rõ ràng ID (B) 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 ID (B) xác định một phân hoạch trên U, ký hiệu là U/ID (B) hay U/B. Ký hiệu lớp tương đương trong phân hoạch U/P chứa đối tượng u là [u]B , khi đó [u]B = {v ∈ U |(u, v) ∈ ID (B)}. Cho bảng quyết định DT = (U,C, D, f ) và P, Q ⊆ C. Khi đó: 1) Phân hoạch U/P và phân hoạch U/Q được gọi là như nhau hay U/P = U/Q, khi và chỉ khi ∀u ∈ U, [u]P = [u]Q.
2) Phân hoạch U/P được gọi là mịn hơn phân hoạch U/P hay U/P ≺ U/Q khi và chỉ khi ∀u ∈ U, [u]P ⊆ [u]Q Định nghĩa 1. Trong mô hình RS cổ điển truyền thống, để biểu diễn tập X ⊆ U trên cơ sở tri thức của tập thuộc tính B theo khái niệm RS, Pawlack sử dụng hai phép toán dựa trên các lớp tương đương của U/B. Các phép toán này được gọi là B-xấp xỉ dưới và B-xấp xỉ trên của X trên U/B, ký hiệu lần lượt là B(X) và B(X).3) Khi đó, B(X) là tập các phần tử trong U chắc chắn thuộc X (xác định thuộc), còn B(X) là tập các phần tử của U có thể thuộc X dựa trên tập thuộc tính B. Trên cơ sở đó, các tập không xác định và tập xác định không thuộc được định nghĩa như sau: BNB (X) = B(X) − B(X) (1.5) Trong đó: BNB (X) được gọi là miền biên của X theo B là tập các đối tượng có thể thuộc hoặc không thuộc (không xác định) trong X, còn U − B(X) là miền ngoài của X là tập các đối tượng chắc chắn không thuộc (không xác định) trong X.
Trong trường hợp BNB (X) = 0/ thì X được gọi là tập xác định, ngược lại X được gọi là RS (Rough Set - RS). Cho bảng quyết định DS = 12 (U,C, D, f ), với X,Y ⊆ U và A ⊆ C. RS mờ trực cảm Định nghĩa 1. Cho U là tập hữu hạn khác rỗng các đối tượng, tập mờ A xác định trên U có dạng: A = {⟨x, µA ⟩ |x ∈ U}.
Trong đó µA (x) được gọi là độ thành viên của phần tử x trong A. Cho A, B ⊆ F (U) với F (U) là họ các tập mờ trên U. Khi đó: 1) A = B nếu A (x) = B (x) , ∀x ∈ U 2) A ⊆ B nếu A (x) ≤ B (x) , ∀x ∈ U 3) (A ∪ B) (x) = max {A (x) , B (x)} , ∀x ∈ U 4) (A ∩ B) (x) = min {A (x) , B (x)} , ∀x ∈ U 5) Ā (x) = 1 − A (x) , ∀x ∈ U Để phát triển các phép toán trong môi trường dữ liệu mờ, các toán tử logic rõ cũng được mở rộng cho môi trường dữ liệu mờ.1 mô tả chi tiết một số toán tử chuẩn T-norm và đối chuẩn T-conorm tương ứng cho phép toán hợp và giao.2 mô 13 √ tả các chi tiết các toán tử kéo theo I-norm và I-conorm.1: Các toán tử T-chuẩn và T-đối chuẩn T-norm T-conorm Tm (a, b) = min{a, b} Sm (a, b) = max{a, b} Tp (a, b) = ab S p (a, b) = a + b − ab TL (a, b) = max{a + b − 1, 0} SL (a, b) = min{a + b, 1} Tcos (a, b) = max {ab − xy, 0} Scos (a, b) = min {a + b − ab + pq, 1} Bảng 1.2: Các toán tử kéo theo chuẩn và đối chuấn I-norm ( I-conorm ( 1, a ≤ b 0, a ≥ b θm (a, b) = σm (a, b) = b, a > b b, a < b ( ( 1, a=0 1, a = 0; θ p (a, b) = b σ p (a, b) = b−a min 1, a , otherwise max 0, 1−a , otherwise. θL (a, b) = min{b ( − a + 1, 1} σL (a, b) = min{0, ( b − a} 1, a≤b 0, a>b θcos (a, b) = σcos (a, b) = ab + xy, a > b a + b − ab − pq, a ≤ b Dựa trên nền tập mờ, để biểu diễn sự tương quan của các đối tượng trong cùng một tập được trơn hơn, phản ánh rõ nét độ tương tự giữa các đối tượng.
Đặc biệt là quan hệ giữa các đối tượng thuộc R. Khi đó, quan hệ tương đương của mô hình RS truyền thống được mở rộng trên nền tập mờ bằng quan hệ tương đương mờ theo định nghĩa sau đây: Định nghĩa 1. Xét R là quan hệ tương đương trên U không rỗng.