Luận án Nghiên cứu rút gọn tập thuộc tính trong hệ quyết định giá trị tập

uyển đổi từ 5 bộ số liệu trong kho dữ liệu [76]. Với mỗi bộ số liệu, giả sử là số đối tượng, là số thuộc tính điều kiện, là số thuộc tính của tập rút gọn, t là thời gian thực hiện thuật toán (đơn vị là giây s). Các thuộc tính điều kiện được đánh số thứ tự từ 1 đến . Hình 3.2. Minh họa các thuật toán tìm tập rút gọn Hình 3.3. Minh họa thuật toán sử dụng hàm phân biệt Trước hết, luận án mô tả thực nghiệm với bộ số liệu Iris.data. Sau khi chuyển đổi từ thiếu giá trị sang tập giá trị, luận án tiến hành nạp dữ liệu (Hình 3.2). Bộ số liệu Iris.data có 5 thuộc tính điều kiện và 150 đối tượng. Kết quả thực hiện thuật toán tìm một tập rút gọn tốt nhất sử dụng hàm phân biệt ngẫu nhiên (Thuật toán GMDSDT) được minh họa tại Hình 3.3. Tập rút gọn thu được gồm 2 thuộc tính, bao gồm {C1, C2}. Thời gian thực hiện thuật toán là 155 mili-giây. Tiếp theo, luận án tổng hợp kết quả thực nghiệm trên 5 bộ số liệu tập giá trị được chuyển đổi từ 5 bộ số liệu trong kho dữ liệu [76]. Kết quả thử nghiệm được mô tả bởi Bảng 3.4 và Bảng 3.5. Bảng 3.4. Kết quả thực hiện Thuật toán GMDSDT STT Bộ số liệu Thuật toán GMDSDT T 1 Hepatitis.data 155 19 3 0.735 2 Automobile.data 205 25 6 4.567 3 Anneal.data 798 38 7 41.256 4 Abalone.data 4177 8 3 214.114 5 Iris 150 5 2 0.155 Bảng 3.5. Tập rút gọn của Thuật toán GMDSDT STT Bộ số liệu Tập rút gọn của Thuật toán GMDSDT 1 Hepatitis.data {2, 15, 16} 2 Automobile.data {1, 2, 7, 14, 20, 21} 3 Anneal.data {3, 5, 8, 12, 33, 34, 35} 4 Abalone.data {2, 5, 6} 5 Iris {1, 2} 3.4. Thuật toán tìm tập xấp xỉ trong hệ thông tin giá trị tập 3.4.1. Đặt vấn đề Cho bảng quyết định . là quan hệ dung sai với Giả sử là các phần tử của tập X. Ký hiệu là lớp dung sai của x. Hàm bao nhau của trong được xác định: Chúng ta thấy rằng giá trị của hàm bao nhau có thể tính toán một cách hiệu quả khi sử dụng bảng phân biệt ngẫu nhiên. Cho tập đối tượng chúng ta ký hiệu là hàm đặc trưng của ta có nếu = { 0 nếu 1 khác Nhận xét 8 : Cho là bảng quyết định, giá trị của cột biểu diễn dưới dạng nhị phân 0 và 1. Với , bảng là bảng phân biệt ngẫu nhiên dựa trên , giả sử với là quan hệ dung sai. Hàm bao nhau của phân lớp có thể được tính qua bảng phân biệt ngẫu nhiên như sau: Đối tượng thuộc xấp xỉ dưới của X nếu: Và thuộc xấp xỉ trên của X nếu: Thuật toán tìm tập xấp xỉ dưới và xấp xỉ trên thực hiện như sau : ▪ Trước tiên với mỗi phân lớp ta tính được hàm bao nhau của các phần tử trong X. ▪ Tiếp theo với , xác định lớp có quan hệ không phân biệt được nếu nó thuộc vào xấp xỉ trên hoặc xấp xỉ dưới của X. 3.4.2. Thuật toán tìm tập xấp xỉ dưới và xấp xỉ trên VASDT Thuật toán 3.2. tìm tập xấp xỉ dưới và xấp xỉ trên - VASDT // Verifying upper and lower Approximation for Set valued Decision Tables (VASDT) Đầu vào: Hệ thông tin giá trị tập với Quan hệ dung sai . Đầu ra: Xấp xỉ trên của xấp xỉ dưới của Phương pháp: 1. Tạo bảng quyết định 2. Tạo bảng CTB; 3. Tạo bảng TCTB từ bảng CTB; 4. for iÎ{1, 2, ., nB} do 5. Tính hàm 6. 7. LowerAppr¬ {i} 8. else 9. if (vi > 0) then 10. 11. end if 12. end if 13. end for 3.4.3. Độ phức tạp của thuật toán VASDT  Giả sử là số đối tượng. Độ phức tạp để tạo bảng DS và bảng TCT là . Xét vòng lặp for độ phức tạp để tính hàm v là . Độ phức tạp thời gian để xấp xỉ trên và xấp xỉ dưới của từng vòng lặp là (bỏ qua d phân lớp quyết định). Vì vậy, độ phức tạp của Thuật toán 3.2 là . 3.4.4. Ví dụ minh họa thuật toán tìm tập xấp xỉ Ví dụ 3.4. Xét hệ thông tin giá trị tập cho ở Bảng 1.3 (bỏ đi thuộc tính quyết định d). Giả sử , , Tính xấp xỉ trên và xấp xỉ dưới của X theo Thuật toán VASDT Tạo bảng quyết định như sau: Bảng 3.6. Bảng quyết định giá trị tập gồm 4 cột thuộc tính điều kiện và cột U Audition(A) Spoken Language(S) Reading(R) Writing(W) 0 0 1 1 1 1 0 0 0 0 2) Tạo . Ta có: Tính phủ , từ bảng trên ta có: , , , , , 3) Thực hiện vòng lặp For với Với i =1, , do đó ; Với i =2, , do đó ; Với i =3, , do đó ; Với i =4, , do đó ; Với i =5, , do đó ; 4) Kết luận: Xấp xỉ trên của tập X đã cho là U. Xấp xỉ dưới của tập X đã cho là rỗng. 3.5. Kết luận Các kết quả nghiên cứu chính được trình bày trong chương 3 là: (1) Xây dựng hai cấu trúc dữ liệu mới là bảng ngẫu nhiên tổng quát hóa và các dàn giá trị thuộc tính trong hệ thông tin giá trị tập. Đây là công cụ hữu hiệu để xây dựng thuật toán tìm tập rút gọn trong bảng quyết định giá trị tập. (2) Đề xuất phương pháp mới rút gọn thuộc tính trong bảng quyết định giá trị tập đó là Thuật toán GMDSDT. Bằng lý thuyết và đánh giá độ phức tạp tính toán chứng minh Thuật toán GMDSDT tương đương với Thuật toán 2.7. của công trình [27]. (3) Đề xuất Thuật toán VASDT tìm tập xấp xỉ trên và tập xấp xỉ dưới trong hệ thông tin giá trị tập. Theo tiêu chuẩn đánh giá độ phức tạp tính toán, bằng lý thuyết chứng minh Thuật toán VASDT hiệu quả hơn Thuật toán tìm tập xấp xỉ của công trình [74]. Chương 4. RÚT GỌN THUỘC TÍNH TRONG HỆ QUYẾT ĐỊNH GIÁ TRỊ TẬP SỬ DỤNG HÀM PHÂN BIỆT THEO MA TRẬN PHÂN BIỆT MỞ RỘNG 4.1. Chọn mẫu đại diện cho bài toán tìm tập rút gọn 4.1.1. Đặt vấn đề Trên hệ thông tin giá trị tập, các công trình nghiên cứu [27, 62, 64] đã đề xuất giải pháp nén dữ liệu với mục đích thu nhỏ kích thước tập dữ liệu ban đầu nhằm giảm thiểu thời gian thực hiện các thuật toán tìm tập rút gọn. Dựa trên ý tưởng thu nhỏ kích thước tập dữ liệu ban đầu, trong phần này luận án đề xuất phương pháp lựa chọn tập đối tượng đại diện từ tập đối tượng ban đầu cho bài toán tìm tập rút gọn của hệ thông tin giá trị tập và bảng quyết định giá trị tập. Và chứng minh tập rút gọn trên tập đối tượng ban đầu và tập rút gọn trên tập đối tượng đại diện là như nhau qua một song ánh trên cả hệ thông tin và bảng quyết định giá trị tập, từ đó khẳng định tính đúng đắn của phương pháp. Vì kích thước tập đối tượng đại diện nhỏ hơn kích thước tập đối tượng ban đầu nên thời gian thực hiện các thuật toán tìm tập rút gọn trên tập đối tượng đại diện giảm thiểu đáng kể. Kích thước tập đối tượng đại diện được chọn lớn hay nhỏ phụ thuộc vào đặc thù mỗi hệ thông tin trong bài toán thực tế. Phát triển các thuật toán tìm tập rút gọn trong hệ thông tin và thuật toán tìm tập xấp xỉ gia tăng của Junbo Zhang và cộng sự [74] và Yao Y.Y [69], luận án dựa vào trên ý tưởng các thuật toán của hai công trình trên đã mở rộng và xây dựng các thuật toán mới về tìm tập rút gọn trong bảng quyết định giá trị tập (cả trong trường hợp bổ sung và loại bỏ tập thuộc tính điều kiện) với công cụ xây dựng các thuật toán là hàm phân biệt mở rộng và ma trận phân biệt mở rộng. Các kết quả trong chương này đã được tác giả công bố trong công trình số 2 và công trình số 3, phần ‘’Danh mục các công trình của tác giả’’ 4.1.2. Chọn tập đối tượng đại diện trong hệ thông tin giá trị tập cho bài toán tìm tập rút gọn 4.1.2.1. Cơ sở lý thuyết Mệnh đề 4.1. Nếu là một đối tượng đại diện được chọn trên sao cho với thì ta cũng có trên với . Chứng minh: Trên , giả sử , khi đó với mọi ta đều có . Từ suy ra . Xét đối tượng bất kỳ , vì nên với mọi , do đó không chứa u với mọi , nghĩa là trên , không chứa với là đối tượng đại diện của lớp tương đương chứa y trên (i). Mặt khác, từ giả thiết , với thì với mọi , hay chứa u với mọi . Với đối tượng y được xét ở trên rõ ràng , giả sử với khi đó và chứa u với mọi , nghĩa là trên , chứa với là đối tượng đại diện của lớp tương đương chứa y, điều này mâu thuẫn với (i). Do đó với mọi Với giả thiết thì trên , với là tập các đối tượng đại diện của các đối tượng thuộc X. Với giả thiết và kết quả chứng minh , với mọi thì trên , với và là đối tượng đại diện của . Do đó ta kết luận trên , , (đpcm) Định nghĩa 4.1. (Rút gọn thuộc tính trong hệ thông tin giá trị tập) Tương tự trong hệ thông tin không đầy đủ [25], với hệ thông tin giá trị tập , tập thuộc tính được gọi là tập rút gọn của IS nếu và điều này tương đương với với mọi và tồn tại sao cho . Từ kết quả của Mệnh đề 4.1 chứng minh rằng tập rút gọn của hệ thông tin giá trị tập ban đầu và tập rút gọn của hệ thông tin giá trị tập đại diện là như nhau. Chứng minh: Giả sử là tập rút gọn của hệ thông tin giá trị tập ban đầu , khi đó với mọi và tồn tại sao cho . a) Từ với mọitrêndễ dàng suy ra với mọi trên . b) Không mất tính tổng quát, giả sử và tồn tại sao cho trên . Nếu u là đối tượng đại diện được chọn thì và trên , theo Mệnh đề 4.1 thì trên (i). Nếu u không phải đối tượng đại diện thì trên , giả sử là đối tượng đại diện của lớp tương đương chứa u và , khi đó . Do nên từ ta cũng suy ra . Từ ta có với mọi theo cách xây dựng phân hoạch ta có với mọi do đó . Từ , bằng cách tương tự ta suy ra . Theo giả thiết, nên ta thu được trên theo Mệnh đề 4.1 thì ta cũng có trên (ii). Như vậy, cả hai trường hợp (i) và (ii) ta đều có trên , từ đó kết luận tồn tại sao cho . Từ a) và b) theo định nghĩa ta có là một tập rút gọn của hệ thông tin giá trị tập đại diện . 4.1.2.2. Thuật toán chọn đối tượng đại diện trên hệ thông tin giá trị tập Xét hệ thông tin giá trị tập , trước hết cần phân hoạch tập đối tượng U ban đầu trên tập thuộc tính thành các lớp tương đương. Hai đối tượng thuộc cùng một lớp tương đương nếu với mọi . Với mỗi lớp tương đương, ta chọn ra một đối tượng đại diện cho lớp tương đương đó, không mất tính chất tổng quát, chọn đối tượng đầu tiên làm đại diện. Khi đó, tập các đối tượng được chọn là tập đại diện. Thuật toán chọn tập đối tượng đại diện của hệ thông tin giá trị tập được mô tả như sau: Thuật toán 4.1. Chọn tập đối tượng đại diện của hệ thông tin giá trị tập. Đầu vào: Hệ thông tin giá trị tập ban đầu với , Đầu ra: Hệ thông tin giá trị tập đại diện , với là một mẫu đại diện. Phương pháp: Bước 1: Đặt ; Bước 2: Với mỗi , tính phân hoạch với . Bước 3: Tính phân hoạch với . Giả sử và với . Bước 4: Với mọi , , đặt ; Bước 5: Return ; Độ phức tạp thuật toán: Giả sử là số thuộc tính điều kiện, là số đối tượng. Xét Bước 2, với mỗi , độ phức tạp để tính là , độ phức tạp để tính phân hoạch là . Do đó, độ phức tạp của Bước 2 là . Độ phức tạp của Bước 3 khi bước 2 đã được tính là . Độ phức tạp của bước 4 là . Do đó, độ phức tạp của Thuật toán là . 4.1.2.3. Ví dụ minh họa Ví dụ 4.1. Xét hệ thông tin giá trị tập cho từ Bảng 4.1 bằng cách loại bỏ cột thuộc tính quyết định d, với và . Bảng 4.1. Bảng quyết định giá trị tập U d {0} {0} {1, 2} {1, 2} 0 {0, 1, 2} {0, 1, 2} {1, 2} {0, 1, 2} 1 {1, 2} {0, 1} {1, 2} {1, 2} 0 {0, 1} {0, 2} {1, 2} {1} 1 {1, 2} {1, 2} {1, 2} {1} 0 {1} {1, 2} {0, 1} {0, 1} 1 {0} {0} {1, 2} {1, 2} 0 {1} {1, 2} {0, 1} {0, 1} 1 Ta có: , , . Do đó . Tính toán tương tự, ta có: , Từ đó ta có Tập mẫu đại diện được chọn là và hệ thông tin giá trị tập mẫu được chọn ở Bảng 4.2. Bảng 4.2. Hệ thông tin giá trị tập đại diện từ Bảng 4.1 Up {0} {0} {1, 2} {1, 2} {0, 1, 2} {0, 1, 2} {1, 2} {0, 1, 2} {1, 2} {0, 1} {1, 2} {1, 2} {1, 2} {1, 2} {1, 2} {1} 4.1.3. Chọn tập đối tượng đại diện trong bảng quyết định giá trị tập cho bài toán tìm tập rút gọn 4.1.3.1. Cơ sở lý thuyết Định nghĩa 4.2. (hàm quyết định suy rộng) Cho bảng quyết định giá trị tập Với được 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 C. Nếu với mọi thì DS là nhất quán, trái lại DS là không nhất quán. Nếu thì từ ta dễ dàng suy ra với mọi Cho bảng quyết định giá trị tập ban đầu và bảng quyết định giá trị tập đại diện , cần chứng minh mệnh đề sau: Mệnh đề 4.2. Nếu là một đối tượng đại diện được chọn trên sao cho với thì ta cũng có trên với . Chứng minh. Trên , từ giả thiết suy ra , giả sử Khi đó, tồn tại sao cho , suy ra 1) Nếu y là đối tượng đại diện, nghĩa là khi đó trên , và , do đó ta kết luận . 2) Nếu y không phải là đối tượng đại diện, giả sử là đối tượng đại diện của lớp tương đương chứa y, theo cách xây dựng tập đối tượng đại diện ta có , mà nên trên ta có (i). Hơn nữa, trên ta có , mà nên . Như vậy, trên ta có (ii). Từ (i) và (ii) suy ra . Như vậy, cả hai trường hợp 1) và 2) ta đều có trên (đpcm). Định nghĩa 4.3. (Rút gọn thuộc tính trong bảng quyết định giá trị tập) Tương tự bảng quyết định không đầy đủ [25], với bảng quyết định giá trị tập , tập thuộc tính được gọi là tập rút gọn của DS nếu với mọi và tồn tại sao cho . Chứng minh rằng tập rút gọn của bảng quyết định giá trị tập ban đầu và tập rút gọn của bảng quyết định giá trị tập đại diện là như nhau. Chứng minh: Giả sử là tập rút gọn của bảng quyết định giá trị tập ban đầu , khi đó với mọi và tồn tại sao cho . 1) Từ với mọi trên dễ dàng suy ra với mọi trên . 2) Không mất tính tổng quát, giả sử và tồn tại trên sao cho . Nếu u là đối tượng đại diện được chọn thì và trên , theo Mệnh đề 4.2 thì trên (i). Nếu u không phải đối tượng đại diện thì trên , giả sử là đối tượng đại diện của lớp tương đương chứa u và , khi đó . Do nên từ ta cũng suy ra . Từ ta có do đó Từ , bằng cách tương tự ta suy ra . Theo giả thiết, nên ta thu được trên , theo Mệnh đề 4.2 thì ta cũng có trên (ii). Như vậy, cả hai trường hợp (i) và (ii) ta đều có trên , từ đó kết luận tồn tại sao cho. Từ 1) và 2) theo định nghĩa ta có là một tập rút gọn của bảng quyết định giá trị tập đại diện . 4.1.3.2. Thuật toán chọn đối tượng đại diện trên bảng quyết định giá trị tập Xét bảng quyết định giá trị tập , tính được phân hoạch . Với mỗi lớp tương đương , ta tính phân hoạch . Với mỗi lớp tương đương , cần chọn ra một đối tượng đại diện cho lớp tương đương đó, không mất tính chất tổng quát, ta chọn đối tượng đầu tiên làm đại diện. Khi đó, tập đối tượng được chọn là tập các đối tượng đại diện. Thuật toán chọn tập đối tượng đại diện của bảng quyết định giá trị tập được mô tả như sau: Thuật toán 4.2. Chọn tập đối tượng đại diện của bảng quyết định giá trị tập. Đầu vào: Bảng quyết định giá trị tập ban đầu với , . Đầu ra: Bảng quyết định giá trị tập đại diện với là một tập đối tượng đại diện. Phương pháp: Bước 1: Đặt ; Bước 2: Với mỗi , tính phân hoạch với . Bước 3: Tính phân hoạch với . Giả sử ; Bước 4: Với mỗi , thực hiện lặp các bước 4.1 và 4.2 như sau: Bước 4.1. Tính phân hoạch với Giả sử và với . Bước 4.2. Với mỗi , , đặt ; Bước 5: Return ; Độ phức tạp thuật toán: Tương tự như thuật toán 4.1, độ phức tạp của Thuật toán 4.2 là . 4.1.3.3. Ví dụ minh họa Ví dụ 4.2. Xét bảng quyết định giá trị tập cho ở Bảng 4.1 với và . Từ Ví dụ 4.1 ta tính được . Tính , vậy được chọn và . Tính , vậy được chọn và . Tính , vậy được chọn và . Tính , vậy và được chọn, . Như vậy, tập mẫu đại diện được chọn là và bảng quyết định giá trị tập mẫu được chọn cho ở Bảng 4.3. Bảng 4.3. Bảng quyết định giá trị tập đại diện từ Bảng 4.1 Up d {0} {0} {1, 2} {1, 2} 0 {0, 1, 2} {0, 1, 2} {1, 2} {0, 1, 2} 1 {1, 2} {0, 1} {1, 2} {1, 2} 0 {1, 2} {1, 2} {1, 2} {1} 0 {1} {1, 2} {0, 1} {0, 1} 1 4.2. Rút gọn thuộc tính trong bảng quyết định giá trị tập sử dụng hàm phân biệt mở rộng Rút gọn thuộc tính trong bảng quyết định là quá trình lựa chọn tập con nhỏ nhất của tập thuộc tính điều kiện mà bảo toàn thông tin phân lớp của bảng quyết định. Trong lý thuyết tập thông truyền thống, Skowron và Rauszer [52] đã đưa ra khái niệm ma trận phân biệt và hàm phân biệt để tìm tập rút gọn. Dựa trên cách tiếp cận này, luận án đưa ra khái niệm ma trận phân biệt mở rộng và hàm phân biệt mở rộng để tìm tập rút gọn của bảng quyết định giá trị tập. 4.2.1. Cơ sở lý thuyết Định nghĩa 4.4. Cho bảng quyết định giá trị tập . Nếu thỏa mãn: (1) với mọi (2) Với mọi , tồn tại sao cho thì R được gọi là một tập rút gọn của DS dựa trên hàm quyết định suy rộng. Ví dụ 4.3. Xét bảng quyết định giá trị tập cho ở Bảng 4.1 với và và cột thuộc tính d. Với đối tượng ta có Do đó . Tương tự, ta tìm các quan hệ dung sai với đối tượng như sau: Do đó . Các quan hệ dung sai với đối tượng Các quan hệ dung sai với đối tượng Các quan hệ dung sai với đối tượng Các quan hệ dung sai với đối tượng Vậy ta có: , . Hơn nữa, , , . Do đó, DS không nhất quán. Định nghĩa 4.5. Cho bảng quyết định giá trị tập với và . Ma trận phân biệt mở rộng của trên tập thuộc chính , ký hiệu , là ma trận vuông cấp n, mỗi phần tử có giá trị 0 hoặc 1, được định nghĩa như sau: nếu (2) nếu . Chú ý: Nếu thì quy ước và không phải là ma trận đối xứng vì vẫn có thể với ; . Ví dụ 4.4. Với bảng quyết định giá trị tập cho ở Ví dụ 4.1 (Bảng 4.1), ma trận phân biệt mở rộng của trên tập thuộc tính C như sau: Mệnh đề 4.3. Cho bảng quyết định giá trị tập với Nếu thì . Ví dụ 4.5. Tiếp tục Ví dụ 4.4, giả sử với , khi đó ta tính được như sau: Với đối tượng ta có Do đó . Suy ra Tương tự, ta có: Do đó . Suy ra Suy ra Suy ra Suy ra Suy ra Vậy Ma trận được biểu diễn như sau Rõ ràng, . Định nghĩa 4.6. Cho bảng quyết định giá trị tậpvà là ma trận phân biệt mở rộng của trên tập thuộc tính . Khi đó, hàm phân biệt mở rộng của trên , ký hiệu là , được định nghĩa như sau: với . Ví dụ 4.6. Tiếp tục Ví dụ 4.4, với ma trận phân biệt , hàm phân biệt là: Từ Định nghĩa 4.6 và Mệnh đề 4.3 ta có mệnh đề sau: Mệnh đề 4.4. Cho bảng quyết định giá trị tập với . Nếu thì . Mệnh đề 4.5. Cho bảng quyết định giá trị tập và , tương ứng là ma trận phân biệt mở rộng và hàm phân biệt mở rộng của trên tập thuộc tính C. Khi đó, khi và chỉ khi với . Chứng minh: i) Giả sử tồn tại sao cho . Vì nên tồn tại sao cho . Từ ta có , (1). Từ , (2). Từ giả thiết ta có , kết hợp với (1) và (2) ta có , điều này mâu thuẫn với điều kiện . Vì vậy, nếu thì . ii) Ngược lại, giả sử . Theo Mệnh đề 4.3 từ ta có , kết hợp với suy ra , khi đó tồn tại và sao cho (3) và (4). Từ (4) suy ra . Từ (3) suy ra . Do đó, , điều này mâu thuẫn với điều kiện . Vì vậy nếu với thì . Từ i) và ii) ta có điều phải chứng minh. Phần tiếp theo, luận án trình bày phương pháp rút gọn thuộc tính trong bảng quyết định giá trị tập sử dụng hàm phân biệt mở rộng. Giống như các phương pháp rút gọn thuộc tính trong lý thuyết tập thô truyền thống, phương pháp này bao gồm các bước: định nghĩa tập rút gọn, định nghĩa độ quan trọng của thuộc tính và xây dựng thuật toán heuristic tìm một tập rút gọn tốt nhất dựa trên độ quan trọng của thuộc tính. Định nghĩa 4.6 cho thấy, hàm phân biệt mở rộng đặc trưng cho khả năng phân lớp của tập thuộc tính vào các lớp quyết định sinh bởi thuộc tính , do đó luận án sử dụng hàm phân biệt mở rộng làm tiêu chuẩn lựa chọn thuộc tính trong thuật toán heuristic tìm tập rút gọn, gọi là độ quan trọng của thuộc tính. Định nghĩa 4.7. (Tập rút gọn dựa vào hàm phân biệt mở rộng) Cho bảng quyết định giá trị tập . Nếu thỏa mãn: (1) (2) , thì R được gọi là một tập rút gọn của DS dựa trên hàm phân biệt mở rộng. Mệnh đề 4.5 chứng minh rằng tập rút gọn sử dụng hàm phân biệt mở rộng tương đương với tập rút gọn sử dựa trên hàm quyết định mở rộng. Định nghĩa 4.8. (Độ quan trọng thuộc tính khi thêm tập thuộc tính điều kiện) Cho bảng quyết định giá trị tập , và . Độ quan trọng của thuộc tính đối với tập thuộc tính được định nghĩa bởi: . Định nghĩa 4.9. (Độ quan trọng thuộc tính khi xóa tập thuộc tính điều kiện) Cho bảng quyết định giá trị tập , và . Độ quan trọng của thuộc tính trong tập thuộc tính được định nghĩa bởi: Từ Mệnh đề 4.4 ta có và . Do đó, và được tính bởi lượng thay đổi hàm phân biệt mở rộng khi thêm thuộc tính a vào A hoặc loại bỏ a khỏi A và , càng lớn thì lượng thay đổi này càng lớn, hay thuộc tính a càng quan trọng và ngược lại. 4.2.2. Thuật toán tìm tập rút gọn trong bảng quyết định giá trị tập sử dụng hàm phân biệt mở rộng Tiếp theo, luận án đề xuất thuật toán heuristic tìm một tập rút gọn tốt nhất theo tiêu chuẩn đánh giá độ quan trọng của thuộc tính. Ý tưởng của thuật toán là xuất phát từ tập thuộc tính rỗng , lần lượt bổ sung vào tập R các thuộc tính có độ quan trọng lớn nhất cho đến khi tìm được tập rút gọn. Thuật toán đề xuất sử dụng chiến lược Thêm - Xóa [69]. Thuật toán 4.3. Thuật toán heuristic tìm tập rút gọn dùng hàm phân biệt mở rộng RGDSDT (heuristic algorithm to find a Reduct based on Generalized Discernibility function in Set-valued Decision Table). Đầu vào: Bảng quyết định giá trị tập . Đầu ra: Một tập rút gọn . Phương pháp: ; // Thêm dần vào R các thuộc tính có độ quan trọng lớn nhất; While do Begin For each tính ; Chọn sao cho ; ; End; //Loại bỏ các thuộc tính dư thừa trong R nếu có; For each If then Return ; 4.2.3. Đánh giá độ phức tạp của thuật toán RGDSDT Giả sử là số thuộc tính điều kiện và là số đối tượng. Ta thấy độ phức tạp để tính là , do đó độ phức tạp tính là . Xét vòng lặp While từ dòng lệnh 2 đến dòng lệnh 7, độ phức tạp để tính tất cả các là . Độ phức tạp thời gian để chọn thuộc tính có độ quan trọng lớn nhất là . Do đó, độ phức tạp của vòng lặp While là . Tương tự, độ phức tạp của vòng lặp For là . Vì vậy, độ phức tạp của Thuật toán 4.3 là . Chứng minh tính đúng đắn của Thuật toán RGDSDT Với bước thêm dần vào R các thuộc tính có độ quan trọng lớn nhất, tập thuộc tính R thu được từ câu lệnh từ 2 đến 7 thỏa mãn điều kiện bảo toàn khoảng cách Với bước loại bỏ các thuộc tính dư thừa, câu lệnh từ 8 đến 10 đảm bảo tập R là tối thiểu, nghĩa là Theo Định nghĩa 4.7, R là tập rút gọn dựa trên hàm phân biệt mở rộng. 4.2.4. Ví dụ minh họa thuật toán RGDSDT Ví dụ 4.7. Xét bảng quyết định giá trị tập cho ở Ví dụ 4.1 (Bảng 4.1). Áp dụng Thuật toán 4.3 tìm tập rút gọn ta có: Đặt và tính: ● Ma trận và Từ kết quả tính được ở Ví dụ 4.3 ta có Như vậy ta có: Chọn thuộc tính có độ quan trọng lớn nhất và . Từ Ví dụ 4.3 ta có , do đó . Chuyển vòng lặp thứ 2 và tính: Ma trận và Từ kết quả tính được ở Ví dụ 4.3 ta có: Chọn thuộc tính có độ quan trọng lớn nhất, và Ta thấy , chuyển đến vòng lặp For thực hiện kiểm tra tập R thu được. Theo tính toán ở trên, và Do đó thuật toán kết thúc và là một rút gọn “tốt nhất” của C. 4.3. Rút gọn thuộc tính trong bảng quyết định giá trị tập khi bổ sung và loại bỏ thuộc tính Trong phần này, luận án trình bày sự thay đổi của ma trận phân biệt mở rộng và hàm phân biệt mở rộng trong bảng quyết định giá trị tập với hai trường hợp: bổ sung tập thuộc tính và loại bỏ tập thuộc tính. Trên cơ sở đó, xây dựng thuật toán tìm tập rút gọn tương ứng với hai trường hợp này. 4.3.1. Cơ sở lý thuyết Mệnh đề 4.6. Cho bảng quyết định giá trị tập với , và . Giả sử và tương ứng là ma trận phân biệt mở rộng của trên tập thuộc tính và . Khi đó, các phần tử của được tính dựa vào các phần tử của như sau: (1) nếu hoặc (2) nếu và Ví dụ 4.8. Xét bảng quyết định giá trị tập cho ở Bảng 4.1 bằng cách bổ sung tập thuộc tính như Bảng 4.4 dưới đây: Bảng 4.4. Bảng quyết định giá trị tập khi bổ sung U d {1} { 1} {1} {0} {0} {0} 1 {0} {0, 1} {1} {0} {1} {1} 1 {0, 1} {0, 1} {0} {1} {0} {0} 0 {1} {0, 1} {1} {1} {0,1} {0} 1 {0, 1} {0, 1} {1} {1} {0} {1} 2 {0} {1} {1} {0, 1} {0} {0} 1 Đặt , . Từ Ví dụ 4.4, ma trận phân biệt mở rộng của trên là: Tính hàm phân biệt mở rộng của ma trận trong đó Ta có: Với đối tượng ta có Do đó . Ta có Do đó Ta có Do đó Ta có Tương tự, ta có: Vậy Ta xây dựng theo Mệnh đề 4.6. Xét đối tượng ta có , Do đó . Theo Mệnh đề 4.6, do nên , nên . Xét đối tượng ta có Do đó . Theo Mệnh đề 4.6, do nên nên Xét đối tượng ta có Do đó Theo Mệnh đề 4.6, do nên nên Xét đối tượng ta có Do đó Theo Mệnh đề 4.6, do nên nên Xét đối tượng ta có Do đó Theo Mệnh đề 4.6, do nên nên Xét đối tượng ta có , . Do đó. Theo Mệnh đề 4.6, , do nên , nên . Ta thu được: Bằng cách tính trực tiếp theo Định nghĩa 4.5, ta cũng thu được kết quả tương tự. Đó là: Ma trận trong đó Dựa vào kết quả hàm phân biệt mở rộng ở phân trên ta xây dựng và tính như sau Mệnh đề 4.7. Cho bảng quyết định giá trị tập với và . Giả sử và tương ứng là ma trận phân biệt mở rộng của trên tập thuộc tính và . Khi đó, các phần tử của được tính dựa vào các phần tử của như sau: (1) nếu và (2) nếu hoặc Ví dụ 4.9. Xét bảng quyết định giá trị tập trong Ví dụ 4.8, đặt , . Từ Ví dụ 4.8 ta có: Tính hàm phân biệt mở rộng của ma trận trong đó ma trận với và ma trận với Dựa vào kết quả tính phân lớp dung sai của Ví dụ 4.3 và Ví dụ 4.8 ta có: . Vậy Ta xây dựng theo Mệnh đề 4.7. Xét đối tượng ta có . Theo Mệnh đề 4.7, , do nên , nên Xét đối tượng ta có . Theo Mệnh đề 4.7, , do nên , nên Xét đối tượng ta có . Theo Mệnh đề 4.7, , do nên , nên Xét đối tượng ta có . Theo Mệnh đề 4.7, , do nên , nên Xét đối tượng ta có . Theo Mệnh đề 4.7, , do nên , nên Xét đối tượng ta có . Theo Mệnh đề 4.7, , do nên , nên . Ta thu được: Bằng cách tính trực tiếp theo Định nghĩa 4.5, ta cũng thu được kết quả tương tự. 4.3.2. Một số thuật toán gia tăng tìm tập rút gọn thuộc tính RSDTAAS và RSDTDAS Thuật toán 4.4. Thuật toán gia tăng tìm tập rút gọn của bảng quyết định giá trị tập khi bổ sung tập thuộc tính: RSDTAAS (extended algorithm to find a Reduct in Set-valued Decision Table when Adding Attribute Set) Đầu vào: Bảng quyết định giá trị tập , Một tập rút gọn tốt nhất của tập thuộc tính C và tập thuộc tính với . Đầu ra: Một tập rút gọn tốt nhất của tập thuộc tính . Phương pháp: ; Tính theo Mệnh đề 4.6; Tính ; While do Begin For each tính với tính theo Mệnh đề 4.6; Chọn sao cho ; ; End; For each If then Return ; Thuật toán 4.5. Thuật toán tìm tập rút gọn của bảng quyết định giá trị tập khi loại bỏ tập thuộc tính: RSDTDAS (extended algorithm to find a Reduct in Set-valued Decision Table when Deleting an Attribute Set) Đầu vào: Bảng quyết định giá trị tập , Một tập rút gọn tốt nhất của tập thuộc tính C và tập thuộc tính với . Đầu ra: Một tập rút gọn tốt nhất của tập thuộc tính . Phương pháp: ; Tính theo Mệnh đề 4.7; Tính ; While do Begin For each tính với tính theo Mệnh đề 4.7; Chọn sao cho ; End; For each If then Return ; 4.3.3. Đánh giá độ phức tạp của các thuật toán RSDTAAS và RSDTDAS w Đánh giá độ phức tạp của thuật toán RSDTAAS Giả sử là số thuộc tính của và là số đối tượng. Theo công thức tính gia tăng ma trận phân biệt mở rộng tại Mệnh đề 4.6, độ phức tạp để tính khi biết là . Do đó, độ phức tạp để tính khi biết cũng là . Xét vòng lặp While từ dòng lệnh 3 đến dòng lệnh 7, độ phức tạp để tính tất cả các là . Độ phức tạp thời gian để chọn thuộc tính có độ quan trọng lớn nhất là . Do đó, độ phức tạp của vòng lặp While là . Tương tự, độ phức tạp của vòng lặp For là . Vì vậy, độ phức tạp của Thuật toán RSDTAAS là . Nếu tìm tập rút gọn của tập thuộc tính bằng Thuật toán RGDSDT thì độ phức tạp sẽ là . Do đó, Thuật toán RSDTAAS tìm tập rút gọn theo phương pháp gia tăng giảm thiểu đáng kể thời gian thực hiện. w Đánh giá độ phức tạp của thuật toán RSDTDAS Tương tự như Thuật toán RSDTAAS, độ phức tạp của Thuật toán RSDTDAS là với là lực lượng của . 4.3.4. Ví dụ minh họa thuật toán RSDTAAS và RSDTDAS Ví dụ 4.11. Từ Ví dụ 4.7 ta có là một rút gọn “tốt nhất” của bảng quyết định giá trị tập cho ở Ví dụ 4.3. Xét bảng quyết định giá trị tập cho ở Ví dụ 4.8 (Bảng 4.4) với , áp dụng Thuật toán RSDTAAS tìm một tập rút gọn tốt nhất khi bổ sung tập thuộc tính , ta có: Đặt , từ Ví dụ 4.8 tính được , Tính ma trận , , như sau: Vậy ta có: . Tính ma trận như sau: Vậy ta có: . Tính ma trận như sau: Vậy ta có: . Chọn thuộc tính có độ quan trọng lớn nhất và . Từ ta có . Chuyển vòng lặp For thực hiện kiểm tra tập R thu được. Tính , do đó Tính , do đó Theo tính toán trên, , do đó Do đó thuật toán kết thúc và là một rút gọn “tốt nhất” của C. Ví dụ 4.12. Xét bảng quyết định giá trị tập cho ở Ví dụ 4.8 (Bảng 4.4) với là một tập rút gọn tốt nhất tìm được ở Ví dụ 4.11. Áp dụng Thuật toán RSDTDAS tìm một tập rút gọn tốt nhất khi loại bỏ tập thuộc tính , ta có: Đặt , từ Ví dụ 4.9 ta có . Từ Ví dụ 4.10 ta có , do đó . Chuyển vòng lặp For thực hiện kiểm tra tập R thu được. Tính , do đó . Tính , do đó . Do đó thuật toán kết thúc và là một rút gọn “tốt nhất” của . 4.4. Thực nghiệm thuật toán RGDSDT Trong phần này, luận án trình bày kết quả thực nghiệm Thuật toán RGDSDT tìm một tập rút gọn tốt nhất của bảng quyết định giá trị tập sử dụng hàm phân biệt mở rộng do tác giả đề xuất. Việc thực nghiệm được tiến hành trên 5 bộ dữ liệu tập giá trị được chuyển đổi từ 5 bộ dữ liệu lấy từ kho dữ liệu [76]. Trên cơ sở đó, luận án so sánh kết quả thực hiện Thuật toán GMDSDT và Thuật toán RGDSDT đều tìm tập rút gọn thuộc tính của hai phương pháp được luận án đề xuất đã trình bày chi tiết trong Chương 3 và Chương 4. 4.4.1. Cài đặt thuật toán RGDSDT Trước hết, tiến hành cài đặt Thuật toán RGDSDT bằng ngôn ngữ C#, môi trường cài đặt là bộ công cụ Microsoft Visual Studio 2010, với bảng quyết định giá trị tập . 4.4.2. Thi hành thực nghiệm thuật toán RGDSDT Môi trường thực nghiệm là máy tính PC với cấu hình Pentium dual core 2.13 GHz CPU, 1GB bộ nhớ RAM, sử dụng hệ điều hành Windows XP Professional. Việc thực nghiệm Thuật toán RGDSDT được thực hiện trên 5 bộ số liệu tập giá trị được chuyển đổi từ 5 bộ số liệu trong kho dữ liệu [76]. Với mỗi bộ số liệu, giả sử là số đối tượng, là số thuộc tính điều kiện, là số thuộc tính của tập rút gọn, T là thời gian thực hiện thuật toán (đơn vị là giây s). Các thuộc tính điều kiện được đánh số thứ tự từ 1 đến . Bảng 4.5 và Bảng 4.6 sau đây mô tả kết quả thực hiện Thuật toán RGDSDT tìm một tập rút gọn tốt nhất sử dụng hàm phân biệt mở rộng. Luận án cũng ghi lại kết quả thực hiện Thuật toán GMDSDT trên 5 bộ số liệu được chọn để thực hiện so sánh thời gian thực hiện và kết quả thực hiện của hai thuật toán. STT Bộ số liệu Thuật toán RGDSDT Thuật toán GMDSDT T T 1 Hepatitis.data 155 19 3 0.531 3 0.735 2 Automobile.data 205 25 6 4.364 6 4.567 3 Anneal.data 798 38 7 27.588 7 41.256 4 Abalone.data 4177 8 3 127.245 3 214.114 5 Iris 150 4 2 0.127 2 0.155 Bảng 4.5. Kết quả thực hiện Thuật toán RGDSDT và Thuật toán GMDSDT STT Bộ số liệu Tập rút gọn của Thuật toán RGDSDT Tập rút gọn của Thuật toán GMDSDT 1 Hepatitis.data {2, 15, 16} {2, 15, 16} 2 Automobile.data {1, 2, 7, 14, 20, 21} {1, 2, 7, 14, 20, 21} 3 Anneal.data {3, 5, 8, 12, 33, 34, 35} {3, 5, 8, 12, 33, 34, 35} 4 Abalone.data {2, 5, 6} {2, 5, 6} 5 Iris {1,2} {1,2} Bảng 4.6. Tập rút gọn của Thuật toán RGDSDT và Thuật toán GMDSDT Từ kết quả thực nghiệm, luận án có nhận xét sau: - Trên 5 bộ số liệu được chọn, tập rút gọn thu được của Thuật toán RGDSDT và Thuật toán GMDSDT là như nhau. Điều này cũng phù hợp với kết quả nghiên cứu lý thuyết là tập rút gọn thu được từ Thuật toán RGDSDT và tập rút gọn thu được từ Thuật toán GMDSDT hoàn toàn giống nhau. - Thời gian thực hiện Thuật toán RGDSDT nhỏ hơn thời gian thực hiện Thuật toán GMDSDT. Với bộ số liệu càng lớn, thời gian thực hiện Thuật toán RGDSDT càng nhỏ hơn nhiều. 4.5. Kết luận chương 4 Chương 4 đã trình bày phương pháp xây dựng hàm phân biệt mở rộng, ma trận phân biệt mở rộng trên bảng quyết định giá trị tập. Hai cấu trúc dữ liệu mới này là công cụ để xây dựng thuật toán tìm tập rút gọn trên bảng quyết định giá trị tập. Đồng thời luận án chứng minh việc tìm tập rút gọn trên bảng quyết định giá trị tập đại diện và bảng quyết định giá trị tập ban đầu là như nhau. Sử dụng hàm phân biệt mở rộng, chương 4 đã trình bày một phương pháp mới tìm rút gọn thuộc tính trong bảng quyết định giá trị tập. Bằng lý thuyết và thực nghiệm, chương 4 đã đề xuất năm thuật toán trên bảng quyết định giá trị tập. 1) Thuật toán 4.1 chọn mẫu đại diện trên hệ thông tin giá trị tập với độ phức tạp thời gian là hàm mũ. 2) Thuật toán 4.2 chọn mẫu đại diện trên bảng quyết định giá trị tập. Đây là thuật toán thực sự có ý nghĩa trong bước tiền xử lý dữ liệu trước khi thực hiện các nhiệm vụ khai phá dữ liệu tiếp theo. 3) Thuật toán RGDSDT tìm một tập rút gọn sử dụng hàm phân biệt mở rộng trong bảng quyết định giá trị tập. 4) Thuật toán RSDTAAS tìm một tập rút gọn sử dụng hàm phân biệt mở rộng trong bảng quyết định giá trị tập khi bổ sung tập thuộc tính. 5) Thuật toán RSDTDAS tìm một tập rút gọn sử dụng hàm phân biệt mở rộng trong bảng quyết định giá trị tập khi loại bỏ tập thuộc tính. Chương 4 cũng tiến hành thử nghiệm thuật toán RGDSDT và so sánh kết quả tìm tập rút gọn hai thuật toán RGDSDT và thuật toán GMDSDT qua thực nghiệm cho cùng một kết quả. KẾT LUẬN VÀ KIẾN NGHỊ I. Những kết quả chính của luận án 1. Định hướng theo kỹ thuật bảng ngẫu nhiên (contingency table) [56], luận án đề xuất hai cấu trúc dữ liệu mới là bảng ngẫu nhiên tổng quát hóa (generalized contingency table) và các dàn giá trị thuộc tính (lattices of attribute values) trong hệ thông tin giá trị tập. Các cấu trúc dữ liệu mới này cho phép phát triển kỹ thuật bảng ngẫu nhiên để đề xuất thuật toán tương ứng tìm tập rút gọn trên bảng quyết định giá trị tập. Kết quả là, luận án đề xuất một thuật toán rút gọn thuộc tính trong bảng quyết định giá trị tập mới là Thuật toán GMDSVDT (Generalized Maximal Discernibility heuristic for Set valued Decision Tables, Thuật toán 3.1). Thuật toán GMDSVDT được tác giả công bố trong công trình số 1, phần “Danh mục các công trình của tác giả”. 2. Hơn nữa, luận án chứng tỏ rằng hai cấu trúc dữ liệu bảng ngẫu nhiên tổng quát hóa và các dàn giá trị thuộc tính cũng là công cụ hữu hiệu đề nghị thuật toán tìm các tập xấp xỉ thô trong hệ thông tin giá trị tập. Luận án đề xuất thuật toán VASDT (Verifying upper and lower Approximation for Set valued Decision Tables, Thuật toán 3.2.) tìm tập xấp xỉ trong hệ thông tin giá trị tập. Ngoài việc áp dụng hai cấu trúc dữ liệu nói trên, Thuật toán VASDT còn khai thác ý nghĩa của các khái niệm hàm phân biệt và độ đo bao hàm trong hệ thông tin giá trị tập. Bằng lý thuyết, luận án chứng minh Thuật toán VASDT do luận án đề xuất hiệu quả hơn Thuật toán tìm tập xấp xỉ trong công trình [74] dựa trên độ phức tạp tính toán. Thuật toán VASDT được tác giả công bố trong công trình số 1. 3. Dựa trên ý tưởng thu nhỏ kích thước tập dữ liệu ban đầu của công trình [27], kết quả là, luận án đề xuất Thuật toán chọn tập đối tượng đại diện (Select a representative object set, Thuật toán 4.1 và Thuật toán 4.2) trong hệ thông tin và trong bảng quyết định giá trị tập từ tập đối tượng ban đầu cho bài toán tìm tập rút gọn. Và chứng minh tập rút gọn trên tập đối tượng ban đầu và tập rút gọn trên tập đối tượng đại diện là như nhau qua một song ánh trên cả hệ thông tin và bảng quyết định giá trị tập, từ đó khẳng định tính đúng đắn của phương pháp. Các thuật toán chọn tập đối tượng đại diện có ý nghĩa quan trọng trong bước tiền xử lý số liệu của bảng quyết định trước khi thực hiện các nhiệm vụ khai phá dữ liệu. Các kết quả được tác giả công bố trong công trình số 2. 4. Trong lý thuyết tập thông truyền thống, Skowron và Rauszer [52] đã đưa ra khái niệm ma trận phân biệt và hàm phân biệt để tìm tập rút gọn. Dựa trên cách tiếp cận này, luận án đề xuất hai cấu trúc dữ liệu mới là hàm phân biệt mở rộng và ma trận phân biệt mở rộng trong bảng quyết định giá trị tập. Hai cấu trúc dữ liệu mới này là công cụ để xây dựng thuật toán tìm tập rút gọn trên bảng quyết định giá trị tập. Kết quả là, luận án đề xuất ba thuật toán tìm tập rút gọn thuộc tính trong bảng quyết định giá trị tập mới là Thuật toán RGDSDT tìm tập rút gọn thuộc tính trong bảng quyết định giá trị tập, Thuật toán RSDTAAS và Thuật toán RSDTDAS lần lượt tìm tập rút gọn thuộc tính khi bổ sung và loại bỏ tập thuộc tính trong bảng quyết định giá trị tập, đồng thời luận án đánh giá độ phức tạp của từng thuật toán. Các kết quả được tác giả công bố trong công trình số 3. II. Hướng phát triển của luận án 1. Trên bảng quyết định giá trị tập, tiếp tục nghiên cứu rút gọn thuộc tính trong trường hợp khi bổ sung tập đối tượng. 2. Tiếp tục nghiên cứu các hàm phân biệt khác trên hệ thông tin giá trị tập. Trên cơ sở đó, đề xuất các phương pháp mới hiệu quả hơn các phương pháp đã có. DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ Sinh Hoa Nguyen and Thi Thu Hien Phung (2013). Efficient Algorithms for Attribute Reduction on Set-valued Decision Systems, The 14th International Conference of Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing (RSFDGrC 2013), Halifax, NS, Canada, October 11-14, 2013, Lecture Notes of Computer Science, SpingerLink, Volume 8170 (2013), pp 87-98. Thi Thu Hien Phung (2013). Generalized Discernibility Function based Attribute Reduction in Set-valued Decision Systems, The Third World Congress on Information and Communication Technologies (WICT 2013), published by IEEE, pp. 225-230. Thi Thu Hien Phung (2013). On Selection of Representative Object Set for Attribute Reduction in Set-valued Information Systems, The Third World Congress on Information and Communication Technologies (WICT 2013), published by IEEE, pp. 269-274. Phùng Thị Thu Hiền, Lê Quang Hào, Nguyễn Bá Tường (2011). Những vấn đề của trích chọn đặc trưng trong hệ tin, Tạp chí nghiên cứu Khoa học kỹ thuật và công nghệ quân sự (2011), tr. 60 - 63. Phùng Thị Thu Hiền, Lê Quang Hào, Nguyễn Quang Khanh, Nguyễn Bá Tường (2010). Định nghĩa tập thô theo hàm thuộc thô, Tạp chí nghiên cứu Khoa học kỹ thuật và công nghệ quân sự (2010), tr. 50 - 54. TÀI LIỆU THAM KHẢO Tài liệu tiếng Việt Nguyễn Long Giang (2012). Nghiên cứu một số phương pháp khai phá dữ liệu theo tiếp cận lý thuyết tập thô, Luận án Tiến sĩ, Viện Công Nghệ Thông Tin. Hoàng Thị Lan Giao (2007). Khía cạnh đại số và lôgic phát hiện luật theo tiếp cận tập thô, Luận án Tiến sĩ, Viện Công Nghệ Thông Tin. Phùng Thị Thu Hiền, Lê Quang Hào, Nguyễn Quang Khanh, Nguyễn Bá Tường (2010). Định nghĩa tập thô theo hàm thuộc thô, Tạp chí nghiên cứu Khoa học kỹ thuật và công nghệ quân sự (2010), tr. 50 - 54. Phùng Thị Thu Hiền, Lê Quang Hào, Nguyễn Bá Tường (2011). Những vấn đề của trích chọn đặc trưng trong hệ tin, Tạp chí nghiên cứu Khoa học kỹ thuật và công nghệ quân sự (2011), tr. 60 - 63. Nguyễn Đức Thuần (2010). Phủ tập thô và độ đo đánh giá hiệu năng tập luật quyết định, Luận án Tiến sĩ, Viện Công Nghệ Thông Tin. Tài liệu tiếng Anh [6] Beaubouef T., Petry F.E. and Arora G. (1998). Information-theoretic measures of uncertainty for rough sets and rough relational databases, Information Sciences, 109, pp. 535-563. [7] Jerzy W. Grzymala-Busse (2011). Mining Incomplete Data - A Rough Set Approach, RSKT 2011, pp. 1-7. [8] Chen Z. C, Shi P., Liu P. G., Pei Z. (2013). Criteria Reduction of Set-Valued Ordered Decision System Based on Approximation Quanlity, International Journal of Innovative Computing, Information and Control, Vol 9, N 6, 2013, pp. 2393-2404. [9] D.G. Chen, S.Y. Zhao, L. Zhang, Y.P. Yang, X. Zhang (2012). Sample pair selection for attribute reduction with rough set, IEEE Transaction on Knowledge and Data Engineering, 24(1), pp. 2080-2093. [10] Ivo Düntsch, Wendy MacCaull, Ewa Orlowska (2000). Structures with Many-Valued Information and Their Relational Proof Theory. ISMVL 2000, pp. 293-304. [11] I. Duntsch, G. Gediga, and E. Orlowska (2001). Relational attribute systems. International Journal of Human-Computer Studies, 55(3):293–309. [12] Qinrong Feng and Rui Li (2013). Discernibility Matrix Based Attribute Reduction in Intuitionistic Fuzzy Decision Systems, RSFDGrC 2013, Halifax, NS, Canada, October 11-14, 2013, Lecture Notes of Computer Science, Volume 8170 (2013), pp. 147-156. [13] Ge H., Li L.S and Yang C.J. (2009). Improvement to Quick Attribution Reduction Algorithm, Journal of Computers, Vol.30, No.2, pp. 308-312. [14] Long Giang Nguyen and Hung Son Nguyen (2013). Metric Based Attribute Reduction in Incomplete Decision Tables, RSFDGrC 2013, Halifax, NS, Canada, October 11-14, 2013, Lecture Notes of Computer Science, Volume 8170 (2013), pp. 99-110. [15] Y. Y. Guan, H. K. Wang (2006). Set-valued information systems, Information Sciences 176(17), pp. 2507-2525. [16] Thi Thu Hien Phung (2013). Generalized Discernibility Function based Attribute Reduction in Set-valued Decision Systems, The Third World Congress on Information and Communication Technologies (WICT 2013), published by IEEE, pp. 225-230. [17] Thi Thu Hien Phung (2013). On Selection of Representative Object Set for Attribute Reduction in Set-valued Information Systems, The Third World Congress on Information and Communication Technologies (WICT 2013), published by IEEE , pp. 269-274. [18] Sinh Hoa Nguyen and Thi Thu Hien Phung (2013). Efficient Algorithms for Attribute Reduction on Set-valued Decision Systems, The 14th International Conference of Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing (RSFDGrC 2013), Halifax, NS, Canada, October 11-14, 2013, Lecture Notes of Computer Science, SpingerLink, Volume 8170 (2013), pp 87-98. [19] Nguyen Sinh Hoa, Nguyen H.Son (1996). Some Efficient Algorithms for Rough Set Methods, The sixth International Conference on Information Processing Management of Uncertainty in Knowledge - Based Systems, pp. 1451-1456 [20] Hu X.H. and Cercone N. (1995). Learning in relational databases, pp. a rough set approach, International Journal of computational intelligence, pp. 323-338. [21] Hu X.H., Lin T.Y. and Han J.C. (2004). A new rough sets model based on database systems, Fundamenta Informaticae, 59(1), pp. 135-152 . [22] Richard Jensen (2005). Combining rough and fuzzy sets for feature selection, PhD Thesis, University of Edinburgh. [23] B. Kolman, R.C. Busby, S.C. Ross (2003). Discrete Mathematical Structures ( fifth ed.), Prentice-Hall, Inc., 2003 [24] Jan Komorowski, Zdzislaw Pawlak, Lech Polkowski and Andrzej Skowron (1999). Rough Sets: A Tutorial. Rough Fuzzy Hybridization – A New Trend in Decision Making (S.K. Pal, A. Skowron; Eds,), pp. 3-98, Springer [25] M. Kryszkiewicz (1998). Rough set approach to incomplete information systems, Information Sciences 112, pp. 39-49. [26] Kryszkiewicz, M. (1999). Rule in complete information systems, Information Science, (113), pp. 271 - 292. [27] Lang G. M., Li Q. G. (2012). Data compression of dynamic set-valued information systems, CoRR abs/1209.6509. [28] Li X.H. and Shi K.Q. (2006). A knowledge granulation-based algorithm for attribute reduction under incomplete information systems, Computer Science, Vol. 33, pp. 169-171. [29] Jiye Liang (2011). Uncertainty and feature selection in rough set theory, Proceedings of the 6th international conference on Rough sets and knowledge technology (RSKT'11), pp. 8-15. [30] G. Liu (2006). The axiomatization of the rough set upper approximation operations, Fundamenta Informaticae 69 (3):331–342 [31] Liu Y., Xiong R. and Chu J. (2009). Quick Attribute Reduction Algorithm with Hash, Chinese Journal of Computers, Vol.32, No.8, pp. 1493-1499. [32] Dale E. Nelson (2001). High Range Resolution Radar Target Classification, pp. A Rough Set Approach, PhD Thesis, Ohio University. [33] Senan Norhalina (2013). Feature selection for traditional Malay musical instrument sound classification using rough set, PhD Thesis, Universiti Tun Hussein Onn Malaysia. [34] Neil S. Mac Parthalain (2009). Rough Set Extensions for Feature Selection, PhD Thesis, Aberystwyth University. [35] Zdzislaw Pawlak (1981). Information System Theoretical Foudation, Information Systems, 6 (3):205-218. [36] Zdzislaw Pawlak (1982). Rough sets, International Journal of Computer and Information Sciences, 11 (5), pp. 341-356. [37] Zdzislaw Pawlak (1985) Rough sets and fuzzy sets, Fuzzy sets and systems, 17, pp. 99-102. [38] Z. Pawlak (1991). Rough Sets: Theoretical Aspects of Reasoning about Data, System Theory, Kluwer Academic Publishers, Dordrecht, 1991. [39] Pawlak Z. (1998). Rough set theory and its applications in data analysis, Cybernetics and systems 29, pp. 661-688. [40] Zdzisław Pawlak (2002). Rough set theory and its applications, Journal of Telecommunications and Information Technology (3/2002), pp. 7-10. [41] Z. Pawlak (2002). Rough sets and intelligent data analysis, Information Science, 147, pp. 1-12. [42] Zdzislaw Pawlak, Andrzej Skowron (2007). Rudiments of rough sets, Information Sciences 177 (1), pp. 3-27. [43] Zdzislaw Pawlak, Andrzej Skowron (2007). Rough sets: some extensions, Information Sciences 177 (1), pp. 28-40. [44] Y. Qian, C. Dang, J. Liang, D. Tang (2009). Set-valued ordered information systems, Information Sciences 179 (16), pp. 2809–2832. [45] Y. H. Qian Y. H., Liang J. Y. (2010). On Dominance Relations in Disjunctive Set-Valued Ordered Information Systems, International Journal of Information Technology & Decision Making, Vol. 9, No. 1, pp. 9–33. [46] Yuhua Qian, Jiye Liang, Witold Pedrycz, Chuangyin Dang (2010). Positive approximation: An accelerator for attribute reduction in rough set theory, Artificial Intelligence 174 (2010), pp. 597–618. [47] J. Qian, D. Q. Miao, Z. H. Zhang, W. Li (2011). Hybrid approaches to attribute reduction based on indiscernibility and discernibility relation. Int. J. Approx. Reasoning 52(2), pp. 212-230. [48] Sanchita Mal-Sarkar (2009). Uncertainty Management of Intelligent Feature Selection in Wireless Sensor Networks, PhD Thesis, Cleveland State University. [49] Shifei D., Hao D. (2010). Research and Development of Attribute Reduction Algorithm Based on Rough Set, IEEE CCDC2010, pp. 648-653. [50] Andrzej Skowron and Cecylia Rauszer (1992). The discernibility matrices and functions in information systems. Theory and Decision Library, Volume 11, pp 331-362 . [51] Skowron, A., Stepaniuk, J. (1996). Tolerance approximation spaces. Fundamenta Informaticae 27, pp. 245-253. [52] Skowron, A., Rauszer, C.: The discernibility matrices and function in infornation systems. In:Slowinski (ed.) Intelligent Decision Support, vol. 11, pp. 331–362. Springer, Netherlands (1992). [53] Andrzej Skowron, Jaroslaw Stepaniuk, Roman W. Swiniarski (2012). Modeling rough granular computing based on approximation spaces. Inf. Sci. 184(1), pp. 20-43. [54] Andrzej Skowron, Andrzej Jankowski, and Roman Swiniarski (2013). 30 Years of Rough Sets and Future Perspectives, RSFDGrC 2013, Halifax, NS, Canada, October 11-14, 2013, Lecture Notes of Computer Science, Volume 8170 (2013), pp. 1–10. [55] Hung Son Nguyen (2006). Approximate Boolean Reasoning: Foundations and Applications in Data Mining, Transactions on Rough Sets (J.F. Peters and A. Skowron (Eds.), V, LNCS 4100, pp. 334–506. [56] W. Swieboda, H. S. Nguyen (2012). Rough Set Methods for Large and Spare Data in EAV Format. 2012 IEEE RIVF International Conference on Computing and Communication Technologies, Research, Innovation, and Vision for the Future (RIVF), pp. 1-6 [57] Roman W. Swiniarski, Andrzej Skowron (2003). Rough set methods in feature selection and recognition. Pattern Recognition Letters 24(6), pp. 833-849. [58] Marcin Szczuka (2011). The use of Rough Set methods in KDD (A tutorial), RSFDGrC-2011. [59] Wang G.Y. (2003). Rough reduction in algebra view and information view, International Journal of Intelligent System 18, pp. 679-688. [60] Wang G.Y., Yu H., Yang D.C. and Wu Z.F. (2001). Knowledge Reduction Based on Rough Set and Information Entropy, The World Multi-conference on Systemics, Cybernetics and Informatics, Orlando, Florida, pp. 555-560. [61] Wang G.Y., Yu H. and Yang D.C. (2002). Decision table reduction based on conditional information entropy, Journal of Computers, Vol. 25 No. 7, pp. 759-766. [62] Wang C. Z., Wua C. X., Chenb D. G., Duc W. J. (2008). Some properties of relation information systems under homomorphisms, Applied Mathematics Letters 21, pp. 940–945. [63] Wang X.B., Zheng X.F. and Xu Z.Y (2008). Comparative Research of Attribute Reductions based on the System Entropy and on the Database System, International Symposium on Computation Intelligence and Design, pp. 150-153. [64] Wang C. Z., Chen D. G., Wuc C., Hu Q. H. (2011). Data compression with homomorphism in covering information systems, International Journal of Approximate Reasoning 52, pp. 519–525. [65] Feng Wang, Jiye Liang, Chuangyin Dang (2013). Attribute reduction for dynamic data sets. Appl. Soft Comput. 13(1), pp. 676-689. [66] Feng Wang, Jiye Liang, Yuhua Qian (2013). Attribute reduction: A dimension incremental strategy, Knowl.-Based Syst. 39, pp. 95-108. [67] Wei Wei, Jiye Liang, Yuhua Qian, Feng Wang, and Chuangyin Dang (2010). Comparative study of decision performance of decision tables induced by attribute reductions, International Journal of General Systems, 39 (8), pp. 813-838. [68] Xu Z.Y., Yang B.R. and Song W. (2006). Complete attribute reduction algorithm based on Simplified discernibility matrix, Computer Engineering and Applications, Vol. 42, No. 26, pp.167-169. [69] Yao Y.Y., Zhao Y., Wang J. (2006). On reduct construction algorithms, Proceedings of International Conference on Rough Sets and Knowledge Technology, pp. 297-304. [70] Yiyu Yao, Yan Zhao (2008). Attribute reduction in decision-theoretic rough set models, Inf. Sci. 178(17), pp. 3356-3373. [71] Ye D.Y. and Chen Z.J. (2002). A new discernibility matrix and computation of a core, Acta Electronica Sinica, Vol. 30, No. 7, pp. 1086-1088. [72] Zadeh L.A. (1965). Fuzzy sets, Information and Control, 8, pp. 338-353, Academic Press, New York. [73] W. Zhang, J. Mi (2004). Incomplete information system and its optimal selections, Computers & Mathematics with Applications 48 (5–6), pp. 691–698. [74] Junbo Zhang, Tianrui Li, Da Ruan, Dun Liu (2012). Rough sets based matrix approaches with dynamic attribute variation in set-valued information systems, International Journal of Approximate Reasoning, Volume 53, Issue 4, pp. 620-635. [75] Zhao M., Luo K. and Qin Z. (2008). Algorithm for attribute reduction based on granular computing, Computer Engineering and Applications, Vol. 44, No. 30, pp. 157-159. [76] The UCI machine learning repository, [77] Li J.H. (2004), “An Absolute Information Quantity-based Algorithm for Reduction of Knowledge in Information Systems”, Computer Engineering and Applications, 39 (28), pp. 52-53. [78] Miao D.Q. and Hu G.R. (1999), “A heuristic algorithm for knowledge reduction”, Computer Research and Development, Vol. 36, No. 6, pp. 681-684.