Luận án tiến sĩ Kỹ thuật: Nghiên cứu các phương pháp rút gọn thuộc tính và sinh luật quyết định theo tiếp cận tập thô mờ

Chia sẻ: Tỉ Thành | Ngày: | Loại File: PDF | Số trang:137

Thêm vào BST

Báo xấu

38
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục đích nghiên cứu của đề tài là đề xuất các phương pháp rút gọn thuộc tính trực tiếp trên bảng quyết định miền giá trị thực theo tiếp cận tập thô mờ. Đề xuất phương pháp rút gọn thuộc tính và sinh luật trong bảng quyết định mờ theo tiếp cận tập thô mờ. Phương pháp rút gọn thuộc tính sử dụng miền dương mờ được công bố trong công trình [CCN2], phương pháp sinh hệ luật mờ trên bảng quyết định mờ sử dụng khoảng cách Jaccard mờ được công bố trong [CCN5].

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án tiến sĩ Kỹ thuật: Nghiên cứu các phương pháp rút gọn thuộc tính và sinh luật quyết định theo tiếp cận tập thô mờ

BỘ THÔNG TIN VÀ TRUYỀN THÔNG HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG CAO CHÍNH NGHĨA NGHIÊN CỨU CÁC PHƯƠNG PHÁP RÚT GỌN THUỘC TÍNH VÀ SINH LUẬT QUYẾT ĐỊNH THEO TIẾP CẬN TẬP THÔ MỜ LUẬN ÁN TIẾN SĨ KỸ THUẬT HÀ NỘI - 2017
BỘ THÔNG TIN VÀ TRUYỀN THÔNG HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG CAO CHÍNH NGHĨA NGHIÊN CỨU CÁC PHƯƠNG PHÁP RÚT GỌN THUỘC TÍNH VÀ SINH LUẬT QUYẾT ĐỊNH THEO TIẾP CẬN TẬP THÔ MỜ CHUYÊN NGÀNH: HỆ THỐNG THÔNG TIN MÃ SỐ: 62.48.01.04 LUẬN ÁN TIẾN SĨ KỸ THUẬT NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. GS.TS. VŨ ĐỨC THI 2. TS. TÂN HẠNH HÀ NỘI - 2017
LỜI CẢM ƠN Luận án này được hoàn thành với sự nỗ lực không ngừng của tác giả và sự giúp đỡ hết mình từ các thầy giáo hướng dẫn, bạn bè và người thân. Đầu tiên, tác giả xin bày tỏ lời tri ân tới GS.TS Vũ Đức Thi và TS. Tân Hạnh, những thầy giáo đã tận tình hướng dẫn tác giả hoàn thành luận án này. Tác giả xin gửi lời cảm ơn tới các thầy, cô giáo và cán bộ của Học viện Công nghệ Bưu chính Viễn thông - Bộ Thông tin và Truyền thông, là cơ sở đào tạo đã luôn tạo điều kiện để NCS có thể hoàn thành luận án của mình. Tác giả xin gửi lời cảm ơn sâu sắc đến TS. Nguyễn Long Giang - một người thầy thầm lặng và các cán bộ Phòng Tin học quản lý, Viện Công nghệ Thông tin, Viện Khoa học và Công nghệ Việt Nam đã nhiệt tình giúp đỡ và tạo ra môi trường nghiên cứu tốt để tác giả hoàn thành công trình của mình; cảm ơn các thầy cô và các đồng nghiệp ở các nơi mà tác giả tham gia viết bài đã có những góp ý chính xác để tác giả có được những công bố như ngày hôm nay. Tác giả xin gửi lời cảm ơn tới Đảng ủy, Ban Giám đốc Học viện Cảnh sát Nhân dân, các đồng nghiệp Bộ môn Toán - Tin học nơi tác giả công tác đã ủng hộ để luận án được hoàn thành đúng thời hạn. Cuối cùng, tác giả xin gửi tới bạn bè, người thân lời cảm ơn chân thành nhất vì đã đồng hành cùng tác giả trong suốt thời gian qua. Con xin cảm ơn Cha, Mẹ và gia đình đã luôn là chỗ dựa vững chắc về tinh thần và vật chất, cũng là những người luôn mong mỏi cho con thành công; cảm ơn vợ và các em đã gánh vác công việc gia đình thay cho anh; xin lỗi các con vì phần nào đó đã chịu thiệt thòi trong thời gian bố học tập nghiên cứu, chính các con là nguồn động lực lớn lao giúp bố hoàn thành được công việc khó khăn này. Hà Nội, tháng 11 năm 2016 Cao Chính Nghĩa
LỜI CAM ĐOAN Các kết quả trình bày trong luận án là công trình nghiên cứu của tôi được hoàn thành dưới sự hướng dẫn của GS.TS. Vũ Đức Thi, TS. Tân Hạnh và TS. Nguyễn Long Giang. Những kết quả trình bày là mới và chưa từng được công bố ở các công trình của người khác. Tôi xin chịu trách nhiệm về những lời cam đoan của mình. Cao Chính Nghĩa
i MỤC LỤC MỤC LỤC ....................................................................................................................... i Danh mục các thuật ngữ................................................................................................ iii Bảng các ký hiệu, từ viết tắt .......................................................................................... iv Danh sách bảng ............................................................................................................ vii Danh sách hình vẽ ....................................................................................................... viii MỞ ĐẦU ....................................................................................................................... 1 CHƯƠNG 1. CÁC KIẾN THỨC CƠ SỞ ....................................................................... 9 1.1. Một số khái niệm về tập thô ............................................................................. 9 1.1.1. Hệ thông tin .............................................................................................. 9 1.1.2. Các tập xấp xỉ ......................................................................................... 10 1.1.3. Miền dương ............................................................................................ 11 1.1.4. Bảng quyết định...................................................................................... 11 1.2. Một số khái niệm về tập thô mờ xác định trên bảng quyết định miền giá trị thực ...................................................................................................................... 11 1.2.1. Bảng quyết định miền giá trị thực ........................................................... 12 1.2.2. Quan hệ tương đương mờ ....................................................................... 12 1.2.3. Ma trận tương đương mờ ........................................................................ 13 1.2.4. Phân hoạch mờ và lớp tương đương mờ .................................................. 14 1.2.5. Các tập xấp xỉ mờ ................................................................................... 17 1.2.6. Miền dương mờ ...................................................................................... 17 1.3. Một số khái niệm về tập thô mờ xác định trên bảng quyết định mờ ................ 18 1.3.1. Bảng quyết định mờ ................................................................................ 18 1.3.2. Phân hoạch mờ và lớp tương đương mờ .................................................. 20 1.3.3. Các tập xấp xỉ mờ ................................................................................... 21 1.3.4. Miền dương mờ ...................................................................................... 21 1.4. Rút gọn thuộc tính trong bảng quyết định....................................................... 23 1.4.1. Tổng quan về rút gọn thuộc tính ............................................................. 23 1.4.2. Tổng quan về rút gọn thuộc tính trong bảng quyết định theo tiếp cận tập thô ............................................................................................................... 26 1.4.3. Định hướng nghiên cứu của luận án ........................................................ 28 1.5. Kết luận chương 1.......................................................................................... 29
ii CHƯƠNG 2. RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH MIỀN GIÁ TRỊ THỰC SỬ DỤNG MIỀN DƯƠNG MỜ VÀ KHOẢNG CÁCH JACCARD MỜ .. 30 2.1. Đặt vấn đề ..................................................................................................... 30 2.2. Rút gọn thuộc tính sử dụng miền dương mờ ................................................... 31 2.2.1. Phương pháp rút gọn thuộc tính sử dụng miền dương mờ ....................... 32 2.2.2. Thử nghiệm và đánh giá kết quả ............................................................. 37 2.3. Rút gọn thuộc tính sử dụng khoảng cách Jaccard mờ ..................................... 44 2.3.1. Khoảng cách Jaccard mờ và các tính chất ............................................... 44 2.3.2. Phương pháp rút gọn thuộc tính sử dụng khoảng cách Jaccard mờ .......... 52 2.3.3. Thử nghiệm và đánh giá kết quả ............................................................. 56 2.4. Kết luận chương 2.......................................................................................... 61 CHƯƠNG 3. RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH MIỀN GIÁ TRỊ THỰC SỬ DỤNG KHOẢNG CÁCH PHÂN HOẠCH MỜ .................................. 63 3.1. Đặt vấn đề ..................................................................................................... 63 3.2. Khoảng cách phân hoạch mờ và các tính chất ................................................ 64 3.3. Phương pháp rút gọn thuộc tính sử dụng khoảng cách phân hoạch mờ ........... 70 3.4. Thử nghiệm và đánh giá kết quả .................................................................... 77 3.5. Kết luận chương 3.......................................................................................... 82 CHƯƠNG 4. RÚT GỌN THUỘC TÍNH VÀ SINH LUẬT TRÊN BẢNG QUYẾT ĐỊNH MỜ ................................................................................................................... 84 4.1. Đặt vấn đề ..................................................................................................... 84 4.2. Phương pháp rút gọn thuộc tính của bảng quyết định mờ ............................... 87 4.3. Phương pháp sinh luật quyết định của bảng quyết định mờ ............................ 91 4.3.1. Luật quyết định mờ ................................................................................. 92 4.3.2. Sinh luật quyết định từ bảng quyết định mờ ............................................ 93 4.3.3. Thử nghiệm và đánh giá kết quả ........................................................... 105 4.4. Kết luận chương 4........................................................................................ 110 KẾT LUẬN ............................................................................................................... 112 Danh mục các công trình của tác giả .......................................................................... 114 TÀI LIỆU THAM KHẢO .......................................................................................... 115
iii Danh mục các thuật ngữ Thuật ngữ tiếng Việt Thuật ngữ tiếng Anh Bảng quyết định Decision Table Bảng quyết định miền giá trị thực Numerical Decision Table Bảng quyết định mờ Fuzzy Decision Table Hệ thông tin Information System Khoảng cách mờ Fuzzy Distance Luật quyết định mờ Fuzzy Decision Rule Ma trận tương đương mờ Fuzzy Equivalent Relational Matrix Miền dương mờ Fuzzy Positive Region Quan hệ tương đương Equivalent Relation Quan hệ tương đương mờ Fuzzy Equivalent Relation Rút gọn thuộc tính Attribute Reduction Tập mờ Fuzzy Set Tập rút gọn Reduct Tập thô Rough Set Tập thô mờ Fuzzy Rough Set Xấp xỉ dưới Lower Approximation Xấp xỉ trên Upper Approximation Xấp xỉ dưới mờ Fuzzy Lower Approximation Xấp xỉ trên mờ Fuzzy Upper Approximation
iv Bảng các ký hiệu, từ viết tắt Ký hiệu, từ viết tắt Diễn giải IS  U ,A  Hệ thông tin D T  U , C  D  Bảng quyết định D DT  U , C    Bảng quyết định mờ U Số đối tượng C Số thuộc tính điều kiện trong bảng quyết định A Số thuộc tính u a  Giá trị của đối tượng u tại thuộc tính a IN D P  Quan hệ P không phân biệt  u P Lớp tương đương chứa u của quan hệ IND  P  Lớp tương đường mờ chứa u của quan hệ tương đương mờ ui R P P R U/P Phân hoạch của U sinh bởi tập thuộc tính P  P  Phân hoạch mờ theo tập thuộc tính P PX Pxấp xỉ dưới của X PX Pxấp xỉ trên của X PN P X  Pmiền biên của X POS P D  Pmiền dương của D S I G P b  Độ quan trọng của thuộc tính b với tập thuộc tính P  A ( u ) Hàm thuộc của đối tượng u với tập mờ A H  P  Entropy Shannon  E P   Entropy Liang
v P Khoảng cách phân hoạch mờ giữa hai phân hoạch mờ  R   P , R Q DNF       R Q   và  R Khoảng cách phân hoạch mờ giữa hai tập thuộc tính C và d NF C , C  D  CD D FJ (  ) A, B Khoảng cách Jaccard mờ giữa hai tập mờ A và B  Khoảng cách Jaccard mờ giữa hai tập thuộc tính C và d FJ C , C  D  CD Thuật toán rút gọn thuộc tính dựa trên miền dương mờ F_RSAR1 F_RSAR1 (Fuzzy Rough Set Based Attribute Reduction 1) Thuật toán rút gọn thuộc tính dựa trên miền dương mờ F_RSAR2 F_RSAR2 (Fuzzy Rough Set Based Attribute Reduction 2) Thuật toán rút gọn thuộc tính dựa trên khoảng cách Jaccard FJ_DBAR mờ (Fuzzy Jaccard Distance Based Attribute Reduction) Thuật toán sinh luật quyết định mờ dựa trên khoảng cách FJ_RBAR Jaccard mờ (Fuzzy Jaccard Rule Based Attribute Reduction) Thuật toán rút gọn thuộc tính dựa trên khoảng cách phân NF_DBAR hoạch mờ (New Fuzzy Distance Based Attribute Reduction) Thuật toán rút gọn thuộc tính dựa trên miền dương mờ FAR-VPFRS (Forward Attribute Reduction Based On Variable Precision Fuzzy-Rough Model) Thuật toán rút gọn thuộc tính dựa trên miền dương mờ cải FA-FPR tiến (Forward Approximation - Fuzzy Positive Region Reduction) Thuật toán rút gọn thuộc tính dựa trên Entropy cải tiến FA-FSCE (Forward Approximation - Fuzzy Conditional Entropy To Design A Heuristic Feature Selection Algorithm)
vi Thuật toán rút gọn thuộc tính dựa trên Entropy tăng thêm GRAF (Attribute Selection Based On Information Gain Ratio In Fuzzy Rough Set Theory) Thuật toán sinh luật quyết định mờ dựa trên xấp xỉ tiến MRBFA (Mine Rules Based On The Forward Approximation) Thuật toán sinh luật quyết định mờ dựa trên xấp xỉ lùi (Mine MRBBA Rules Based On The Backward Approximation)
vii Danh sách bảng Bảng 1.1. Bảng quyết định miền giá trị thực.................................................................... 12 Bảng 1.2. Bảng quyết định mờ chơi thể thao ................................................................... 18 Bảng 1.3. Bảng quyết định mờ của Ví dụ 1.3 .................................................................. 22 Bảng 2.1. Bảng quyết định miền giá trị thực của Ví dụ 2.1 .............................................. 34 Bảng 2.2. Bộ dữ liệu thử nghiệm ..................................................................................... 37 Bảng 2.3. Kết quả thực nghiệm của F_RSAR2, FAR-VPFRS ......................................... 40 Bảng 2.4. Tập rút gọn của F_RSAR2, FAR-VPFRS ........................................................ 42 Bảng 2.5. Độ chính xác phân lớp C4.5 của F_RSAR2, FAR-VPFRS .............................. 42 Bảng 2.6. Kết quả thực nghiệm của FJ_DBAR và GRAF ............................................... 57 Bảng 2.7. Tập rút gọn thu được bởi FJ_DBAR và GRAF ................................................ 59 Bảng 2.8. Độ chính xác phân lớp C4.5 của FJ_DBAR và GRAF ..................................... 59 Bảng 3.1. Mối liên hệ giữa khoảng cách phân hoạch mờ và entropy thông tin ................. 69 Bảng 3.2. Kết quả thực nghiệm của FA_FSCE, FA_FPR, NF_DBAR ............................. 78 Bảng 3.3. Tập rút gọn của FA_FSCE, FA_FPR, NF_DBAR .......................................... 80 Bảng 3.4. Độ chính xác phân lớp C4.5 của FA_FSCE, FA_FPR, NF_DBAR .................. 80 Bảng 4.1. Bảng quyết định mờ chơi thể thao biểu diễn lại Bảng 1.2 ................................ 89 Bảng 4.2. Bảng quyết định mờ chơi thể thao đã rút gọn thuộc tính .................................. 97 Bảng 4.3. Khoảng cách Jaccard mờ trực tiếp giữa các biến ngôn ngữ của Bảng 4.2 ......... 98 Bảng 4.4. Kết quả gán nhãn của Bảng 4.2 với (α=0.245; β=0.9) ................................... 100 Bảng 4.5. Kết quả gán nhãn của Bảng 4.2 với (α=0.245; β=0.8) ................................... 101 Bảng 4.6. Kết quả gán nhãn của Bảng 4.2 với (α=0.26) ................................................ 103 Bảng 4.7. Kết quả thực nghiệm của MRBFA, MRBBA và FJ_RBAR ........................... 108
viii Danh sách hình vẽ Hình 1.1. Quá trình lựa chọn thuộc tính .......................................................................... 25 Hình 1.2. Lựa chọn thuộc tính theo hướng tiếp cận lọc & đóng gói ................................. 26 Hình 1.3. Mô hình phương pháp heuristic rút gọn thuộc tính .......................................... 27 Hình 2.1. Thời gian thực hiện của F_RSAR2, FAR-VPFRS ............................................ 41 Hình 2.2. Độ chính xác phân lớp C4.5 của F_RSAR2, FAR-VPFRS .............................. 43 Hình 2.3. Thời gian thực hiện của FJ_DBAR và GRAF ................................................. 58 Hình 2.4. Độ chính xác phân lớp C4.5 của FJ_DBAR và GRAF ..................................... 61 Hình 3.1. Thời gian thực hiện của FA_FSCE, FA_FPR, NF_DBAR ............................... 79 Hình 3.2. Độ chính xác phân lớp C4.5 của FA_FSCE, FA_FPR và NF_DBAR ............. 81 Hình 4.1. Phân lớp dữ liệu theo các luật quyết định mờ ................................................... 86 Hình 4.2. Độ chính xác phân lớp của MRBFA, MRBBA và FJ_RBAR......................... 109 Hình 4.3. Độ phân tán dữ liệu của MRBFA, MRBBA và FJ_RBAR ............................. 109
1 MỞ ĐẦU Rút gọn thuộc tính và sinh luật quyết định (luật phân lớp) là hai bài toán quan trọng trong quá trình khám phá tri thức từ dữ liệu. Rút gọn thuộc tính thuộc giai đoạn tiền xử lý dữ liệu còn sinh luật quyết định thuộc giai đoạn khai phá dữ liệu. Rút gọn thuộc tính của 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, loại bỏ các thuộc tính dư thừa mà bảo toàn thông tin phân lớp của bảng quyết định, gọi là tập rút gọn (reduct). Kết quả rút gọn thuộc tính ảnh hưởng trực tiếp đến hiệu quả thực hiện các nhiệm vụ khai phá: Gia tăng tốc độ, cải thiện chất lượng, tính dễ hiểu của các kết quả thu được. Sinh luật quyết định là bước tiếp theo của rút gọn thuộc tính trong khai phá dữ liệu nhằm đánh giá chất lượng phân lớp của dữ liệu thông qua độ hỗ trợ của tập luật quyết định. Độ chính xác phân lớp được đánh giá thông qua tỷ lệ phân lớp đúng theo luật quyết định trên tổng số lớp của tập dữ liệu. Các kỹ thuật rút gọn thuộc tính được phân thành hai loại: Lựa chọn thuộc tính (Attribute selection) và biến đổi thuộc tính (Attribute transformation) [44]. Lựa chọn thuộc tính là chọn ra một tập con tốt nhất (theo một nghĩa nào đó) từ tập dữ liệu ban đầu. Biến đổi thuộc tính là thực hiện việc biến đổi các thuộc tính của tập dữ liệu ban đầu thành một tập dữ liệu với các thuộc tính mới có số lượng ít hơn sao cho bảo tồn được thông tin nhiều nhất. Các công trình nghiên cứu về rút gọn thuộc tính thường tập trung vào nghiên cứu các kỹ thuật lựa chọn thuộc tính. Lựa chọn thuộc tính là quá trình lựa chọn một tập con gồm P thuộc tính từ tập gồm A thuộc tính (PA) sao cho không gian thuộc tính được thu gọn lại một cách tối ưu theo một tiêu chuẩn nhất định. Hiện nay có hai cách tiếp cận chính đối với bài toán lựa chọn thuộc tính: Lọc (filter) và đóng gói (wrapper). Cách tiếp cận kiểu lọc thực hiện việc lựa chọn thuộc tính độc lập với thuật toán khai phá sử dụng sau này. Các thuộc tính được chọn chỉ dựa trên độ quan trọng của chúng trong việc mô tả dữ liệu. Ngược lại với cách tiếp cận lọc, lựa chọn thuộc tính kiểu đóng gói tiến hành việc lựa chọn bằng cách áp dụng ngay kỹ thuật khai phá cụ thể, độ chính xác của kết quả được lấy làm tiêu chuẩn để lựa chọn các tập con thuộc tính [44].
2 Lý thuyết tập thô (Rough set) do Pawlak đề xuất [66] là công cụ hiệu quả giải quyết bài toán rút gọn thuộc tính trong bảng quyết định và được cộng đồng nghiên cứu về tập thô thực hiện lâu nay. Trong lý thuyết tập thô, dữ liệu được biểu diễn thông qua một hệ thông tin IS  U , A  với U là tập các đối tượng và A là tập các thuộc tính. 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ệ không phân biệt được để đưa ra các tập xấp xỉ biểu diễn tập đối tượng cần quan sát. Bảng quyết định là một hệ thông tin IS với tập thuộc tính A được chia thành hai tập con 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. Nói cách khác, DT  U , C  D  với C  D   . Bảng quyết định là mô hình thường gặp trong thực tế, khi mà giá trị dữ liệu tại các thuộc tính điều kiện có thể cung cấp cho ta thông tin về giá trị của thuộc tính quyết định. Các phương pháp rút gọn thuộc tính theo tiếp cận lý thuyết tập thô đều thực hiện trên các bảng quyết định có miền giá trị rời rạc. Trong thực tế, miền giá trị thuộc tính của các bảng quyết định thường chứa giá trị thực. Ví dụ, thuộc tính trọng lượng cơ thể và huyết áp trong bảng dữ liệu bệnh nhân thường là các giá trị thực, liên tục. Để thực hiện các phương pháp rút gọn thuộc tính theo tiếp cận tập thô, miền giá trị thuộc tính thực, liên tục cần được rời rạc hóa. Tuy nhiên, các phương pháp rời rạc hóa không bảo toàn sự khác nhau ban đầu giữa các đối tượng trong dữ liệu gốc và do đó làm giảm độ chính xác phân lớp sau khi rút gọn thuộc tính. Để giải quyết bài toán rút gọn thuộc tính trực tiếp trên các bảng quyết định có miền giá trị thực, trong mấy năm gần đây các nhà nghiên cứu đề xuất hướng tiếp cận mới sử dụng lý thuyết tập thô mờ. Lý thuyết tập thô mờ (Fuzzy rough set) do Dubois, D., và Prade, H., [32], [33] đề xuất là sự kết hợp của lý thuyết tập thô và lý thuyết tập mờ nhằm xấp xỉ các tập mờ dựa trên một quan hệ tương đương mờ (fuzzy equivalent relation) được xác định trên miền giá trị thuộc tính. Lý thuyết tập thô truyền thống dựa trên quan hệ tương đương để xấp xỉ tập hợp, trong đó độ tương đương của hai đối tượng là 1 nếu chúng tương đương, ngược lại là 0 nếu chúng không tương đương. Lý thuyết tập thô
3 mờ sử dụng quan hệ tương đương mờ thay thế quan hệ tương đương, độ tương đương mờ của hai đối tượng là một giá trị nằm trong đoạn [0,1] cho thấy tính gần nhau, hay khả năng phân biệt giữa hai đối tượng. Do đó, quan hệ tương đương mờ bảo toàn sự khác nhau, hay độ tương đương, giữa các đối tượng và các phương pháp rút gọn thuộc tính theo tiếp cận tập thô mờ có tiềm năng trong việc bảo toàn độ chính xác phân lớp sau khi thực hiện các phương pháp rút gọn thuộc tính. Chủ đề nghiên cứu về rút gọn thuộc tính theo tiếp cận tập thô mờ đã thu hút sự quan tâm của các nhà nghiên cứu trong mấy năm gần đâ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ô mờ tập trung giải quyết hai bài toán chính: 1) Bài toán thứ nhất là rút gọn thuộc tính trực tiếp trên các bảng quyết định có miền giá trị thực (miền giá trị thuộc tính là các số thực) không qua bước rời rạc hoá dữ liệu [15], [18], [24], [26], [36], [38], [39], [63], [79], [80], [97]. Với bài toán này, đối tượng nghiên cứu là các bảng quyết định miền giá trị thực. Một quan hệ tương đương mờ được định nghĩa trên miền giá trị của thuộc tính. Quan hệ này cho phép xác định các ma trận tương đương mờ. Dựa trên ma trận quan hệ tương đương mờ, các toán tử của tập thô mờ được xây dựng như lớp tương đương mờ, tập xấp xỉ dưới mờ và xấp xỉ trên mờ, miền dương mờ... Lớp tương đương mờ là đơn vị cơ sở để xây dựng các độ đo hiệu quả giải quyết bài toán rút gọn thuộc tính. Các kết quả nghiên cứu theo hướng tiếp cận này tập trung vào ba nhóm chính: Nhóm các phương pháp sử dụng miền dương mờ [9], [38]- [40], [72], nhóm phương pháp sử dụng ma trận phân biệt mờ [15], [18], [26], [80], nhóm phương pháp sử dụng entropy thông tin mờ [24], [38]- [40], [88], [89]. Thực nghiệm trên một số bộ số liệu lấy từ kho dữ liệu UCI [99] cho thấy, các phương pháp rút gọn thuộc tính theo hướng tiếp cận này có độ chính xác phân lớp cao hơn các phương pháp rút gọn thuộc tính theo tiếp cận tập thô truyền thống. Tuy nhiên, chưa có nghiên cứu đầy đủ để so sánh, đánh giá các phương pháp đã có về độ chính xác phân lớp
4 và thời gian thực hiện. Do đó, việc tìm kiếm các phương pháp hiệu quả hơn các phương pháp đã công bố theo hướng tiếp cận này nhằm nâng cao độ chính xác phân lớp và thời gian thực hiện là vấn đề nghiên cứu thứ nhất của luận án. 2) Bài toán thứ hai là rút gọn thuộc tính và sinh luật trực tiếp trên bảng quyết định mờ, là bảng quyết định mà giá trị thuộc tính là các tập mờ [9], [44], [45], [47]-[51], [74], [88], [89]. Với bài toán này, đối tượng nghiên cứu là các bảng quyết định mờ (là các bảng quyết định sau khi được mờ hóa bằng các tập mờ). Các phân hoạch mờ được tính toán trên miền giá trị các thuộc tính. Trên cơ sở đó, các lớp tương đương mờ được xác định. Các lớp tương đương mờ là đơn vị tính toán cơ sở để tính toán các toán tử trong lý thuyết tập thô mờ như các tập xấp xỉ mờ, miền dương mờ và là đơn vị cơ sở để tính toán các độ đo sử dụng để giải quyết bài toán rút gọn thuộc tính. Sinh luật là bài toán tiếp theo của rút gọn thuộc tính nhằm sinh tập luật phân lớp dữ liệu. Các nghiên cứu liên quan đến việc giải quyết bài toán sinh luật quyết định trên bảng quyết định mờ phải kể đến các công trình [19], [21], [44], [51], [56], [74], [92]. Các công bố này sử dụng các độ đo khác nhau nhằm trích lọc hệ luật mờ như sử dụng miền dương mờ và một số độ đo khác. Việc tìm kiếm các độ đo nhằm nâng cao hiệu quả của phương pháp trích lọc hệ luật mờ về thời gian thực hiện và độ chính xác phân lớp là vấn đề nghiên cứu thứ hai của luận án. Kỹ thuật sử dụng khoảng cách đóng vai trò quan trọng trong khai phá dữ liệu. Trên thế giới, kỹ thuật này được nhiều người quan tâm nghiên cứu và áp dụng vào việc giải quyết các bài toán như phân lớp, phân cụm, lựa chọn đặc trưng,…Ở Việt Nam, luận án tiến sĩ của tác giả Nguyễn Long Giang là công trình nghiên cứu khá đầy đủ về một số phương pháp rút gọn thuộc tính của bảng quyết định theo tiếp cận lý thuyết tập thô, đặc biệt là phương pháp sử dụng khoảng cách [4]. Phương pháp rút gọn thuộc tính sử dụng khoảng cách theo tiếp cận tập thô được chứng minh là mang lại hiệu quả hơn so với các phương pháp khác [4]. Do đó, việc phát triển
5 các độ đo khoảng cách theo tiếp cận tập thô mờ (gọi là khoảng cách mờ) có tiềm năng trong việc giải quyết bài toán rút gọn thuộc tính và sinh luật theo tiếp cận tập thô mờ. Từ các phân tích nêu trên, nghiên cứu sinh đặt ra mục tiêu nghiên cứu như sau: 1) Với bài toán thứ nhất, nghiên cứu sinh tiếp tục nghiên cứu các phương pháp hiệu quả rút gọn thuộc tính trực tiếp trên các bảng quyết định có miền giá trị thực theo tiếp cận tập thô mờ. Tính hiệu quả dựa trên hai tiêu chí đánh giá: Nâng cao độ chính xác phân lớp và cải thiện hiệu năng (thời gian thực hiện) so với các phương pháp khác đã công bố. Việc tìm kiếm các phương pháp dựa trên các độ đo khoảng cách đã được sử dụng trong lý thuyết tập thô. 2) Với bài toán thứ hai, nghiên cứu sinh nghiên cứu các phương pháp hiệu quả rút gọn thuộc tính và sinh luật quyết định trên bảng quyết định mờ. Tính hiệu quả dựa trên hai tiêu chí đánh giá là độ chính xác phân lớp và thời gian thực hiện. Với mục tiêu đặt ra, luận án thu được các kết quả chính như sau: 1) Đề xuất các phương pháp rút gọn thuộc tính trực tiếp trên bảng quyết định miền giá trị thực theo tiếp cận tập thô mờ, bao gồm: - Phương pháp rút gọn thuộc tính sử dụng miền dương mờ nhằm cải tiến một số phương pháp dựa trên miền dương mờ đã công bố trước đó [38] để tìm tập rút gọn không dư thừa thuộc tính và bảo toàn miền dương mờ. Kết quả này công bố trong công trình [CCN1], [CCN2]. - Phương pháp rút gọn thuộc tính sử dụng khoảng cách Jaccard mờ và khoảng cách phân hoạch mờ. Khoảng cách Jaccard mờ được nghiên cứu sinh xây dựng dựa trên khoảng cách Jaccard giữa hai tập hợp hữu hạn [4] để đo khoảng cách giữa hai tập mờ. Khoảng cách phân hoạch mờ được xây dựng dựa trên khoảng cách mờ giữa hai tập mờ do nghiên cứu sinh
6 đề xuất. Thực nghiệm trên một số bộ dữ liệu lấy từ kho dữ liệu UCI [99] chứng minh hai phương pháp sử dụng khoảng cách mờ hiệu quả hơn các phương pháp đã công bố trên cả hai tiêu chí: Độ chính xác phân lớp và thời gian thực hiện trên một số bộ dữ liệu thực nghiệm. Các kết quả này góp phần hình thành nhóm phương pháp rút gọn thuộc tính sử dụng khoảng cách mờ theo tiếp cận tập thô mờ, được công bố trong các công trình [CCN3], [CCN4]. 2) Đề xuất phương pháp rút gọn thuộc tính và sinh luật trong bảng quyết định mờ theo tiếp cận tập thô mờ. Phương pháp rút gọn thuộc tính sử dụng miền dương mờ được công bố trong công trình [CCN2], phương pháp sinh hệ luật mờ trên bảng quyết định mờ sử dụng khoảng cách Jaccard mờ được công bố trong [CCN5]. Bằng lý thuyết và thực nghiệm chứng minh phương pháp đề xuất tương đương với các phương pháp khác trên tiêu chí độ chính xác phân lớp dữ liệu. Đối tượng nghiên cứu của luận án là các bảng quyết định có miền giá trị thực và bảng quyết định mờ. Phạm vi nghiên cứu của luận án tập trung trọng tâm vào hai bài toán: 1) Bài toán thứ nhất là rút gọn thuộc tính của bảng quyết định miền giá trị thực trong bước tiền xử lý số liệu. 2) Bài toán thứ hai là rút gọn thuộc tính và sinh luật quyết định của bảng quyết định mờ. Phương pháp nghiên cứu của luận án là nghiên cứu lý thuyết và nghiên cứu thực nghiệm. Về nghiên cứu lý thuyết: Các định lý, mệnh đề trong luận án được chứng minh chặt chẽ dựa vào các kiến thức cơ bản và các kết quả nghiên cứu đã công bố. Về nghiên cứu thực nghiệm: Luận án thực hiện cài đặt các thuật toán, chạy thử nghiệm thuật toán với các bộ số liệu lấy từ kho dữ liệu UCI [99], so sánh và đánh giá kết quả thực nghiệm so với kết quả nghiên cứu lý thuyết và các công bố khác để khẳng định được tính đúng đắn của kết quả nghiên cứu.
7 Bố cục của luận án gồm phần mở đầu và bốn chương nội dung, phần kết luận và danh mục các tài liệu tham khảo. Cụ thể như sau: Chương 1 trình bày một số khái niệm cơ bản gồm: Một số khái niệm về lý thuyết tập thô; một số khái niệm cơ bản về tập thô mờ xác định trên bảng quyết định miền giá trị thực; một số khái niệm về tập thô mờ xác định trên bảng quyết định mờ; tổng quan về bài toán rút gọn thuộc tính. Các kiến thức cơ sở này được sử dụng trong các chương sau, là các đóng góp chính của luận án. Chương 2 trình bày các kết quả nghiên cứu về các phương pháp rút gọn thuộc tính trong bảng quyết định miền giá trị thực sử dụng miền dương mờ và khoảng cách Jaccard mờ, bao gồm: 1) Đề xuất cải tiến một thuật toán rút gọn thuộc tính của bảng quyết định dựa trên miền dương mờ; đây là phương pháp tìm một tập rút gọn sử dụng quan hệ tương đương mờ theo tiếp cận tập thô mờ có độ phức tạp tính toán là hàm đa thức và bảo toàn miền dương mờ. Phương pháp đề xuất khắc phục được một số hạn chế về thời gian tính toán hàm mũ như công bố của nhóm tác giả trong [44] và bảo toàn miền dương mờ, tìm được một tập rút gọn với số thuộc tính là nhỏ nhất, loại bỏ được các thuộc tính dư thừa như trong công bố của nhóm tác giả trong [38]. 2) Xây dựng thuật toán rút gọn thuộc tính của bảng quyết định miền giá trị thực sử dụng khoảng cách Jaccard mờ. Khoảng cách Jaccard mờ được nghiên cứu sinh xây dựng dựa trên khoảng cách Jaccard giữa hai tập hợp hữu hạn [4] để đo khoảng cách giữa hai tập mờ. Kết quả so sánh đánh giá phương pháp đề xuất với các phương pháp khác dựa trên hai tiêu chuẩn: Độ chính xác phân lớp dữ liệu và thời gian thực hiện của phương pháp. Chương 3 trình bày kết quả nghiên cứu về phương pháp rút gọn thuộc tính trong bảng quyết định miền giá trị thực sử dụng độ đo khoảng cách phân hoạch mờ, bao gồm:
8 1) Đề xuất độ đo khoảng cách phân hoạch mờ dựa trên khoảng cách mờ giữa hai tập mờ. 2) Xây dựng thuật toán rút gọn thuộc tính của bảng quyết định miền giá trị thực sử dụng khoảng cách phân hoạch mờ. Kết quả so sánh đánh giá phương pháp đề xuất với các phương pháp khác dựa trên hai tiêu chuẩn: Độ chính xác phân lớp dữ liệu và thời gian thực hiện của phương pháp. Chương 4 trình bày phương pháp rút gọn thuộc tính và sinh luật quyết định của bảng quyết định mờ dựa trên tập thô mờ. Phương pháp rút gọn thuộc tính sử dụng miền dương mờ, phương pháp sinh luật sử dụng khoảng cách Jaccard mờ. Dựa trên lý thuyết và các thực nghiệm, chứng minh rằng phương pháp đề xuất là tương đương với các phương pháp khác dựa trên tiêu chí độ chính xác phân lớp dữ liệu và thời gian thực hiện; độ phức tạp tính toán của các phương pháp sinh luật quyết định trong trường hợp tổng quát là O( C D U ) với |C| là số biến ngôn ngữ của tất cả các thuộc tính điều kiện, |D| là số biến ngôn ngữ của tất cả các thuộc tính quyết định, |U| là số đối tượng của bảng dữ liệu. Cuối cùng, phần kết luận nêu những đóng góp của luận án, hướng phát triển tiếp theo và những vấn đề quan tâm của tác giả.