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
TÓM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT
Hà Nội - 2017
Công trình được hoàn thành tại: Học viện Công nghệ Bưu chính
Viễn thông
Người hướng dẫn khoa học: GS. TS. Vũ Đức Thi
TS. Tân Hạnh
Phản biện:.....................................................................
.....................................................................................
Phản biện:.....................................................................
.....................................................................................
Phản biện:.....................................................................
.....................................................................................
Luận án sẽ được bảo vệ trước Hội đồng cấp Học viện Công
nghệ Bưu chính Viễn thông chấm luận án tiến sĩ họp tại..
.....................................................................................
vào hồi giờ ngày tháng năm
Có thể tìm hiểu luận án tại:
- Thư viện Quốc gia Việt Nam
- Thư viện Học viện Công nghệ Bưu chính Viễn thông
1
MỞ ĐẦU
Tính cấp thiết của luận án
Rút gọn thuộc tính và sinh luật quyết định 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 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.
Lý thuyết tập thô mờ (Fuzzy rough set) do Dubois, D., và
Prade, H., đề 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. Theo lý thuyết tập thô mờ, độ 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 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 và sinh luật quyế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. Luận án tập trung nghiên cứu
trọng tâm vào hai bài toán:
2
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ờ.
Đố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ờ.
Các kết quả đạt được của luận án
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 nhằm khắc phục một số hạn chế của những công bố trước
đây để tìm được một 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ờ. Thực nghiệm trên một
số bộ dữ liệu lấy từ kho dữ liệu UCI 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 công bố
trong 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
3
đươ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.
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. Chương 1
trình bày một số khái niệm cơ bản về lý thuyết tập thô và tổng quan
về bài toán rút gọn thuộc tính mà luận án tập trung nghiên cứu.
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ờ. 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 khoảng cách phân hoạch mờ. 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ờ.
CHƯƠNG 1. CÁC KIẾN THỨC CƠ SỞ
1.1. Một số khái niệm về tập thô
Hệ thông tin là một cặp
,
IS U A
trong đó
U
là tập hữu hạn
khác rỗng các đối tượng gọi là tập vũ trụ;
A
là tập hữu hạn khác
rỗng các thuộc tính.
Cho hệ thông tin
,
IS U A
và tập đối tượng
X U
. Với một
tập thuộc tính
P A
cho trước, xác định được các lớp tương đương
của phân hoạch
/
U P
. Có hai cách xấp xỉ tập đối tượng X thông
qua tập thuộc tính P, được gọi là P-xấp xỉ dưới và P-xấp xỉ trên của
X, ký hiệu lần lượt là
PX
và
PX
, được xác định như sau:
,
P
PX u U u X
P
PX u U u X
Tập
PX
bao gồm tất cả các phần tử của U chắc chắn thuộc
vào X, còn tập
PX
bao gồm các phần tử của U có khả năng thuộc
vào X dựa vào tập thuộc tính P.