Tóm tắt Luận án Tiến sĩ Toán học: Nghiên cứu phát triển các phương pháp cập nhật bảng quyết định phủ động và xử lý mất cân bằng dữ liệu dựa trên tập thô mờ

Chia sẻ: _ _ | Ngày: | Loại File: DOCX | Số trang:29

Thêm vào BST

Báo xấu

4
lượt xem 1
download

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

Tóm tắt Luận án Tiến sĩ Toán học "Nghiên cứu phát triển các phương pháp cập nhật bảng quyết định phủ động và xử lý mất cân bằng dữ liệu dựa trên tập thô mờ" được nghiên cứu với mục tiêu: Nghiên cứu, đề xuất cập nhật các quyết định ba nhánh đối với hệ thông tin không đầy đủ; phương pháp cập nhật các tập xấp xỉ trong không gian xấp xỉ phủ động và phương pháp sử dụng tập thô mờ để cải thiện sự mất cân bằng của dữ liệu. Thực nghiệm, đánh giá các kỹ thuật đề xuất.

Chủ đề:

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

Lưu

Nội dung Text: Tóm tắt Luận án Tiến sĩ Toán học: Nghiên cứu phát triển các phương pháp cập nhật bảng quyết định phủ động và xử lý mất cân bằng dữ liệu dựa trên tập thô mờ

2 MỞ ĐẦU Tính cấp thiết của đề tài luận án Lý thuyết tập thô đóng vai trò quan trọng, là nền tảng trong tính toán hạt, trí tuệ nhân tạo, khai phá dữ liệu, khám phá tri thức, nhận dạng mẫu, hệ thống thông minh… Chính vì vậy lý thuyết tập thô đã nhận được sự quan tâm của đông đảo các nhà khoa học trong nước và thế giới. Trong các ứng dụng thực tế, dữ liệu trong một hệ thông tin thường thay đổi không ngừng, vì thế các kỹ thuật được đề xuất để khai thác các cơ sở dữ liệu động. Kỹ thuật này thường sử dụng các kết quả khai thác thu được từ cơ sở dữ liệu đầu tiên để làm điều kiện bảo trì và cập nhật lại các kiến thức trong cơ sở dữ liệu động mà không cần khai thác lại từ đầu. - Đã có nhiều phương pháp cập nhật các quyết định ba nhánh được đề xuất, tuy nhiên chúng chủ yếu được sử dụng trong hệ thông tin đầy đủ, còn đối với hệ thống không hoàn chỉnh thì chỉ áp dụng trong từng trường hợp đơn lẻ. - Các phương pháp cập nhật các tập xấp xỉ chủ yếu tiếp cận theo hướng chia tập biên thành các tập biên trên và các tập biên dưới, hoặc dựa vào sự thay đổi của các ma trận. - Việc sử dụng tập thô mờ để xử lý bài toán mất cân bằng dữ liệu theo hướng sử dụng các ngưỡng khác nhau cho các lớp đa số và thiểu số để chọn được nhiều đối tượng hơn từ các lớp
3 thiểu số. Tuy nhiên, việc chọn ngưỡng của phương pháp này vẫn thực hiện thủ công vì vậy chưa tối ưu. Xuất phát từ thực tiễn nêu trên, luận án chọn “Nghiên cứu phát triển các phương pháp cập nhật bảng quyết định phủ động và xử lý mất cân bằng dữ liệu dựa trên tập thô mờ” với mong muốn đề xuất phương pháp học tăng cường và cân bằng dữ liệu giúp tối ưu hóa thời gian và hiệu năng của mô hình. Mục tiêu nghiên cứu Nghiên cứu, đề xuất cập nhật các quyết định ba nhánh đối với hệ thông tin không đầy đủ; phương pháp cập nhật các tập xấp xỉ trong không gian xấp xỉ phủ động và phương pháp sử dụng tập thô mờ để cải thiện sự mất cân bằng của dữ liệu. Thực nghiệm, đánh giá các kỹ thuật đề xuất. Đối tượng và phạm vi nghiên cứu Đối tượng luận án nghiên cứu là các bảng quyết định đầy đủ và không đầy đủ với kích thước trung bình và kích thước lớn. Phạm vi nghiên cứu trọng tâm của luận án là bài toán cập nhật các tập xấp xỉ và các quyết định ba nhánh trong hệ thông tin không đầy đủ và bài toán ứng dụng tập thô vào tối ưu ngưỡng để giảm sự mất cân bằng của dữ liệu. Đánh giá các kỹ thuật đề xuất với các bộ số liệu lấy từ kho dữ liệu UCI. Nội dung nghiên cứu
4 Nghiên cứu, phân tích, đánh giá và đề xuất mới các phương pháp cập nhật các quyết định ba nhánh và các tập xấp xỉ trong bảng quyết định không đầy đủ động. Nghiên cứu, đề xuất phương pháp sử dụng tập thô mờ để làm giảm sự mất cân bằng dữ liệu. Phương pháp nghiên cứu: Kết hợp nghiên cứu lý thuyết và thực nghiệm. Ý nghĩa khoa học và thực tiễn Nghiên cứu chuyên sâu và có hệ thống về bài toán cập nhật gia tăng đối với bảng quyết định không đầy đủ động và bài toán giảm sự mất cân bằng dữ liệu sử dụng tập thô mờ. Bố cục của luận án Luận án gồm 04 chương cùng với các phần mở đầu, kết luận, danh mục các công trình khoa học đã được công bố của tác giả và danh mục tài liệu tham khảo.
5 CHƯƠNG 1 TỔNG QUAN VỀ TẬP THÔ VÀ CÁC MỞ RỘNG CỦA TẬP THÔ 1.1 Mô hình tập thô truyền thống 1.2 Tập thô dung sai 1.3 Tập thô mờ 1.4 Quyết định ba nhánh 1.5 Tập thô phủ 1.6 Những vấn đề luận án cần tập trung nghiên cứu giải quyết - Dựa trên sự thay đổi của xác suất có điều kiện, đề xuất phương pháp cập nhật các quyết định ba nhánh trong hệ thông tin không đầy đủ khi đồng thời thêm và xóa các đối tượng. Từ đó đưa ra công thức cập nhật các quyết định ba nhánh khi giá trị thuộc tính của một đối tượng thay đổi. - Xuất phát từ dạng thứ ba của hàm thành viên thô được giới thiệu bởi Yang và các cộng sự luận án đề xuất phương pháp cập nhật các tập xấp xỉ phân cấp trong không gian xấp xỉ phủ động. Ý tưởng chính của phương pháp này là khảo sát sự thay đổi của hàm thành viên thô dạng ba khi đồng thời thêm và xóa các đối tượng khỏi hệ thống, từ đó đưa ra công thức cập nhật các tập xấp xỉ phân cấp. - Cải tiến thuật toán trích chọn dữ liệu được nhóm tác giả Van Nguyen, D đề xuất để phù hợp hơn với các tập dữ liệu có độ mất cân bằng cao, đồng thời đề xuất thuật toán tối ưu hóa
6 các ngưỡng dùng trong thuật toán. 1.7 Kết luận chương 1 Chương 1 đã trình bày, tổng quan các khái niệm cơ bản về mô hình tập thô trong hệ thông tin đầy đủ, các mở rộng của tập thô và các quyết định ba nhánh. Các khái niệm được trình bày khái quát, ngắn gọn, và có ví dụ minh họa. Đây là công cụ nền tảng cho việc trình bày đề xuất các lý thuyết mở rộng nội dung ở các chương tiếp theo. CHƯƠNG 2 CẬP NHẬT QUYẾT ĐỊNH BA NHÁNH TRONG HỆ THÔNG TIN KHÔNG ĐẦY ĐỦ ĐỘNG Chương này trình bày đề xuất của luận án về cập nhật các quyết định ba nhánh khi hệ thông tin không đầy đủ biến động theo thời gian. Trước tiên luận án sẽ trình bày vắn tắt về các hướng nghiên cứu trên thế giới về cập nhật các quyết định ba nhánh trong hệ thông tin động và chỉ ra vấn đề cần cải tiến trong các phương pháp này. Tiếp theo, luận án trình bày đề xuất phương pháp cập nhật các quyết định ba nhánh trong hệ thông tin không đầy đủ. Phương pháp đề xuất được chứng minh tính đúng đắn bằng mô hình toán học và ví dụ minh họa. Các kết quả đã được công bố trong [CT1] và [CT4]. 2.1 Bài toán cập nhật tăng cường các quyết định ba nhánh Khi hệ thông tin thay đổi các đối tượng, các thuộc tính hoặc các giá trị thuộc tính,
7 kéo theo sự thay đổi của miền dương, miền biên và miền âm. Khi ba miền này thay đổi kéo theo sự thay đổi của các luật quyết định. Khi đó, cần phải tính toán lại các miền ba nhánh để cập nhật các luật quyết định. Vấn đề đặt ra là có thể dựa vào các miền ba nhánh có sẵn để cập nhât các miền mới nhằm giảm thời gian và công sức tính toán hay không. 2.2. Khảo sát xu hướng thay đổi của xác suất có điều kiện 2.2.1 Sự thay đổi của các xác suất có điều kiện khi tập đối tượng thay đổi Khi đồng thời thêm đối tượng và xóa đối tượng , các lớp dung sai và các lớp quyết định được cập nhật như sau: Mệnh đề 2.1. Xét hệ thông tin tại thời điểm, , khi đồng thời thêm đối tượng và xóa đối tượng thì Trong đó Với và . Trong đó Với và . Trong công thức trên, có một trường hợp là đối tượng được thêm vào không thuộc bất kỳ một lớp dung sai hay lớp quyết định sẵn có nào. Trong trường hợp đó, sẽ được coi là một lớp
8 mới, tương ứng. Định lý 2.1. Xét hệ thông tin ,và tại thời điểm và . Giả sử đồng thời thêm đối tượng và xóa đối tượng và các đối tượng này thỏa mãn một trong các điều kiện sau: Thì Định lý 2.2. Xét hệ thông tin ,và tại thời điểm và . Giả sử đồng thời thêm đối tượng và xóa đối tượng và các đối tượng này thỏa mãn một trong các điều kiện sau: Thì Định lý 2.3. Xét hệ thông tin ,và tại thời điểm và . Giả sử đồng thời thêm đối tượng và xóa đối tượng và các đối tượng này thỏa mãn một trong các điều kiện sau: Thì 2.2.2 Sự thay đổi của các xác suất có điều
9 kiện khi thay đổi các giá trị thuộc tính của các đối tượng 2.2.2.1 Giá trị thuộc tính điều kiện của một đối tượng thay đổi trên một thuộc tính Khi giá trị thuộc tính điều kiện của đối tượng thay đổi, các lớp dung sai được cập nhật như sau: Trong đó Với Tại thời điểm , nếu không thuộc bất kỳ một lớp dung sai định sẵn có nào thì coi là một lớp mới. Mệnh đề 2.2. Xét hệ thông tin trong đó là quan hệ dung sai trên . Giả sử tồn tại sao cho giá trị thuộc tính điều kiện của thay đổi trên thuộc tính từ thời điểm đến thời điểm , tức là, . Khi đó Nếu thì . Nếu Thì . Nếu Thì . 2.2.2.2 Giá trị thuộc tính quyết định của một đối tượng thay đổi trên một thuộc tính
10 Khi giá trị thuộc tính quyết định của đối tượng thay đổi, các lớp quyết định được cập nhật như sau: Trong đó: Với . Khi giá trị thuộc tính quyết định của đối tượng xk thay đổi, nếu giá trị thuộc tính quyết định mới này không thuộc về bất kỳ lớp quyết định hiện có nào, thì sẽ có dạng một lớp mới. Mệnh đề 2.3. Xét hệ thông tin trong đó là quan hệ dung sai trên . Giả sử giá trị thuộc tính quyết định của thay đổi trên thuộc tính từ thời điểm t đến thời điểm , tức là, . Khi đó Nếu Thì . Nếu Thì Nếu Thì . 2.2.2.3 Giá trị thuộc tính điều kiện và giá trị thuộc tính quyết định của một đối tượng cùng thay đổi Giả sử tại thời điểm , cả giá trị thuộc
11 tính điều kiện và giá trị thuộc tính quyết định của đối tượng thay đổi, các lớp dung sai và quyết định được cập nhật như sau: Trong đó Với . Trong đó Với Khi đối tượng đồng thời thay đổi giá trị thuộc tính điều kiện và giá trị thuộc tính quyết định, có một trường hợp mà giá trị thuộc tính mới của đối tượng không thuộc về bất kỳ lớp dung sai hoặc lớp quyết định hiện có nào. Trong trường hợp này, sẽ tạo thành một lớp mới, tương ứng. Mệnh đề 2.4. Xét hệ thông tin trong đó là quan hệ dung sai trên . Giả sử tồn tại và để và . Khi đó Nếu Thì . Nếu
12 Thì Nếu Thì . 2.3. Cập nhật quyết định ba nhánh dưới sự thay đổi của xác suất có điều kiện Mệnh đề 2.5. Giả sử rằng tại thời điểm , các xác suất có điều kiện giảm, tức là . Khi đó Trong đó . . Trong đó . . . Trong đó . . Mệnh đề 2.6. Giả sửa rằng tại thời điểm , các xác suất có điều kiện giảm, tức là . Khi đó Trong đó .
13 . . Trong đó . . . Trong đó . . . 2.4 Đề xuất phương pháp cập nhật các quyết định ba nhánh Xét hệ thông tin không đầy đủ , khi cần tính toán các miền ba nhánh cần thực hiện các bước sau : Bước 1: Dựa trên quan hệ dung sai, phân lớp các đối tượng, đồng thời phân hoạch các lớp quyết định. Bước 2: Đối với mỗi lớp quyết định, tính toán các xác suất có điều kiện với từng lớp dung sai. Bước 3: So sánh các xác suất với cặp ngưỡng cho trước để xác định miền dương, miền biên và miền âm. Giả sử tại thời điểm tập đối tượng thay đổi hoặc giá trị thuộc tính của đối tượng thay đổi. Khi đó, như đã trình bày ở phần 2.2 và 2.3, sự thay đổi thay này sẽ dẫn tới sự thay đổi của xác suất có điều kiện. Từ đó các miền ba nhánh cũng thay đổi theo. Để giảm thời gian và công sức tính toán, phương pháp cập nhật các quyết định ba nhánh được đề xuất như sau : Bước 1: Tại thời điểm cập nhật các lớp dung sai và các lớp quyết định dựa trên các lớp dung sai và lớp quyết định có sẵn tại thời
14 điểm . Chọn ra những lớp dung sai có sự thay đổi so với thời điểm . Bước 2: Chỉ tính toán lại các xác suất có điều kiện đối với các lớp đã được chọn ra ở bước 1. Bước 3: Dựa trên sự thay đổi xác suất này, cập nhật các miền ba nhánh. 2.5. Ví dụ minh họa 2.6. Kết luận chương 2 Xuất phát từ những hạn chế của phương pháp cập nhật quyết định ba nhánh, luận án đề xuất phương pháp cập nhật khi hệ thông tin thay đổi do đồng thời thêm và xóa các đối tượng khỏi tập đối tượng. Đồng thời Chương 2 cũng khảo sát sự thay đổi của các quyết định ba nhánh khi giá trị thuộc tính của đối tượng thay đổi theo thời gian. Phương pháp này được chứng minh tính đúng đắn bằng các mô hình toán học. Ngoài ra Chương 2 đã trình bày và phân tích một ví dụ minh họa để chỉ ra tính hiệu quả của phương pháp. CHƯƠNG 3 CẬP NHẬT TẬP XẤP XỈ TRONG KHÔNG GIAN XẤP XỈ PHỦ ĐỘNG Chương 3 trình bày các nghiên cứu của luận án về không gian xấp xỉ phủ động. Trước tiên luận án trình bày khảo sát về hàm thành viên thô và các tập xấp xỉ phân cấp trong không gian xấp xỉ phủ trong mục 3.1. Sau đó trình bày đề xuất của luận án về cập nhật bảng quyết
15 định phủ động. Cuối cùng luận án trình bày một ví dụ để minh họa cho phương pháp này. Các kết quả được công bố trong [CT2]. 3.1 Khảo sát về hàm thành viên thô và các tập xấp xỉ phân bậc trong không gian xấp xỉ phủ 3.1.1 Hàm thành viên thô 3.1.2. Các tập xấp xỉ phân bậc 3.1.3 Khảo sát các phương pháp cập nhật các tập xấp xỉ phân bậc 3.1.4. Nhận xét Ta nhận thấy rằng, đối với bảng quyết định không đầy đủ với thì là một phủ đặc trưng đặc biệt của Vì vậy hoàn toàn có thể xây dựng mô hình tập thô phân bậc dựa trên phủ này đối với các hệ thông tin có dữ liệu không đầy đủ. Do đó, có thể đề xuất một phương pháp cập nhật các tập xấp xỉ phân cấp dựa trên việc tính toán sự thay đổi của hàm thành viên thô dạng ba. Ngoài ra, đối với các tập xấp xỉ phân bậc trong hệ thông tin động, các phương pháp cập nhật chúng chủ yếu dựa trên ma trận ma trận đặc trưng, hoặc ma trận quan hệ tương đương. Lấy cảm hứng từ điều này, luận án đề xuất một phương pháp để cập nhật các tập xấp xỉ phân cấp dựa trên hàm thành viên thô dạng ba. Phương pháp này được công bố trong [CT2]. 3.2 Đề xuất phương pháp cập nhật tập xấp xỉ Xét bảng quyết định không đầy đủ với khi đó là một phủ đặc trưng đặc biệt của Tại thời điểm , khi tập đối tượng không
16 thay đổi, hệ thông tin được ký hiệu là . Khi đồng thời thêm đối tượng và xóa đối tượng vào tập , ta ký hiệu hệ thông tin tại thời điểm này là . 3.2.1 Xu hướng thay đổi của hàm thành viên thô dạng ba Để đơn giản ta ký hiệu dạng thứ ba của hàm thành viên thô tại thời điểm là và tại thời điểm là . Định lý 3.1. Xét hệ thông tin ,và tại thời điểm và . Giả sử đồng thời thêm đối tượng và xóa đối tượng và các đối tượng này thỏa mãn một trong các điều kiện sau: Nếu Thì Nếu Thì
17 Nếu Thì Định lý 3.2. Xét hệ thông tin ,và tại thời điểm và . Giả sử đồng thời thêm đối tượng và xóa đối tượng và các đối tượng này thỏa mãn một trong các điều kiện sau: Nếu Thì Nếu Thì
18 Nếu Thì 3.2.2 Cập nhật các tập xấp xỉ phân cấp Định lý 3.3. Giả sử tại thời điểm và dạng thứ ba của hàm thành viên thô không đổi, tức là, , thì Trong đó và . Trong đó và . Định lý 3.4. Giả sử tại thời điểm và dạng thứ ba của hàm thành viên thô tăng, tức là, , thì Nếu thì Trong đó và . Nếu thì Trong đó và . Định lý 3.5. Giả sử tại thời điểm và dạng
19 thứ ba của hàm thành viên thô giảm, tức là, , thì Nếu thì Trong đó và . Nếu thì Trong đó và . 3.2.3 Đề xuất phương pháp cập nhật các tập xấp xỉ Xét hệ thông tin không đầy đủ , khi cần tính toán các tập xấp xỉ phân cấp cần thực hiện các bước sau : Bước 1: Phân lớp dữ liệu dựa trên quan hệ dung sai. Bước 2: Tính hàm thành viên thô dạng ba của mỗi lớp. Bước 3: So sánh với ngưỡng để thu được các tập xấp xỉ phân cấp. Giả sử tại thời điểm tập đối tượng thay đổi khi đồng thời thêm và xóa các đối tượng. Để giảm thời gian và công sức tính toán, phương pháp cập nhật các tập xấp xỉ được đề xuất như sau : Bước 1: Tại thời điểm cập nhật các lớp dung sai dựa trên các lớp dung sai có sẵn tại thời điểm . Chọn ra những lớp dung sai có sự thay đổi so với thời điểm . Bước 2: Tính toán lại hàm thành viên thô dạng 3 đối với các lớp đã được chọn ra ở bước
20 1. Bước 3: Dựa trên sự thay đổi của hàm thành viên thô dạng 3, cập nhật các tập xấp xỉ. Khi sử dụng phương pháp này để cập nhật các tập xấp xỉ phân cấp các công việc ở cả 3 bước đều giảm đáng kể, cụ thể như sau: Bước 1: Không cần phân lớp lại dữ liệu, mà chỉ cần xét xem đối tượng thêm vào và đối tượng xóa đi thuộc lớp có sẵn nào. Bước 2: Chỉ tính các hàm thành viên thô dạng ba đối với các lớp liên quan đến đối tượng xóa đi và đối tượng thêm vào vừa khảo sát được ở bước 1. Bước 3: So sánh lại các hàm thành viên thô vừa tính ở bước 2 với ngưỡng để cập nhật các tập xấp xỉ phân cấp. 3.3 Ví dụ minh họa 3.4 Kết luận chương 3 Chương 3 đã trình bày phương pháp đánh giá sự thay đổi của hàm thành viên thô dạng ba khi tập đối tượng thay đổi do đồng thời thêm và xóa các đối tượng. Chương 3 cũng trình bày công thức cập nhật các tập xấp xỉ phân cấp dựa trên xu hướng thay đổi của hàm thành viên thô dạng ba. Đồng thời chứng minh tính đúng đắn của phương pháp bằng mô hình toán học và trình bày một ví dụ để minh họa cho việc xây dựng phương pháp đó. CHƯƠNG 4 PHƯƠNG PHÁP CÂN BẰNG DỮ LIỆU SỬ DỤNG TẬP THÔ MỜ Chương này trình bày các khảo sát về bài toán cân bằng dữ liệu từ đó đề xuất thuật toán trích chọn dữ liệu và tối ưu hóa ngưỡng bằng