ĐẠI HỌC HUẾ
TRƢỜNG ĐẠI HỌC KHOA HỌC
LÊ VĂN TƢỜNG LÂN
PHÂN LỚP DỮ LIỆU BẰNG CÂY QUYẾT ĐỊNH MỜ
DỰA TRÊN ĐẠI SỐ GIA TỬ
CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH
MÃ SỐ: 62.48.01.01
TÓM TẮT
LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH
Ngƣời hƣớng dẫn khoa học
1. PGS.TS. Nguyễn Mậu Hân
2. TS. Nguyễn Công Hào
HUẾ – NĂM 2018
1
MỞ ĐẦU
1. Lý do chọn đề tài
Trong thực tế, các khái niệm mờ luôn tồn tại nên với việc quan
niệm các đối tượng được sử dụng phải luôn rõ ràng ở trong logic cổ
điển sẽ không không đủ miêu tả các vấn đề của thế giới thực. Năm
1965, L. A. Zadeh đã đề xuất hình thức hóa toán học của khái niệm
mờ, từ đó lý thuyết tập mờ được hình thành và ngày càng thu hút sự
nghiên cứu của nhiều tác giả. Năm 1990, N.C. Ho & W. Wechsler đã
khởi xướng phương pháp tiếp cận đại số đến cấu trúc tự nhiên của
miền giá trị của các biến ngôn ngữ. Theo cách tiếp cận này, mỗi giá
trị ngôn ngữ của một biến ngôn ngữ nằm trong một cấu trúc đại số
gọi là đại số gia tử (ĐSGT). Trên cơ sở đó, đã có nhiều nghiên cứu
của nhiều tác giả trong các lĩnh vực: điều khiển mờ và lập luận mờ,
cơ sở dữ liệu mờ, phân lớp mờ,… và đã cho chúng ta nhiều kết quả
rất khả quan, có khả năng ứng dụng tốt.
Hiện nay, khai phá dữ liệu là bài toán cần ưu tiên cần giải quyết
mà phân lớp dữ liệu là một quá trình quan trọng của khai phá dữ liệu.
Đó là quá trình chia các đối tượng dữ liệu thành các lớp dựa trên các
nét đặc trưng của tập dữ liệu. Các phương pháp thường được sử dụng
trong quá trình học phân lớp như: thống kê, mạng nơron, cây quyết
định,… trong đó cây quyết định là một giải pháp hữu hữu hiệu. Đã
có nhiều nghiên cứu để xây dựng nó mà nổi bật là các thuật toán học
quy nạp như CART, ID3, C4.5, SLIQ, SPRINT, LDT, LID3,... Tuy
vậy, các cách tiếp cận cho việc học phân lớp bằng cây quyết định
hiện nay vẫn còn nhiều vấn đề cần giải quyết:
- Xây dựng cây quyết định dựa trên khái niệm Entropi thông tin
theo các phương pháp truyền thống như ID3, C4,5, CART, SLIQ,
SPRINT,…cho các thuật toán có độ phứt tạp thấp nhưng khả năng
dự đoán chưa cao, có thể dẫn đến tình trạng quá khớp trên cây kết
quả. Thêm vào đó, các phương pháp này không thể sử dụng để huấn
luyện và dự đoán trên các tập mẫu có chứa giá trị mờ, mà việc lưu
trữ dữ liệu mờ hiện nay là tất yếu trên các kho dữ liệu nghiệp vụ.
- Một hướng tiếp cận là thông qua lý thuyết tập mờ để tính lợi
ích thông tin của các thuộc tính mờ cho quá trình phân lớp. Cách này
đã giải quyết được các giá trị mờ trong tập huấn luyện thông qua việc
xác định các hàm thuộc, từ đó các bộ giá trị này có thể tham gia vào
quá trình huấn luyện nên đã giải quyết được hạn chế là bỏ qua các
2
giá trị dữ liệu mờ của cách tiếp cận phân lớp rõ. Tuy vậy, hiện vẫn
còn gặp phải những hạn chế xuất phát từ bản thân nội tại của lý
thuyết tập mờ: hàm thuộc của chúng không sánh được với nhau, xuất
hiện sai số lớn tại quá trình xấp xỉ, phụ thuộc vào sự chủ quan, giá trị
ngôn ngữ còn thiếu một cơ sở đại số làm nền tảng.
- Theo cách tiếp cận xây dựng cây quyết định ngôn ngữ, nhiều
tác giả đã xây dựng cách thức xác định cho các giá trị ngôn ngữ trên
tập dữ liệu mờ và xây dựng cây bằng phương pháp LID3. Việc xây
dựng các nhãn ngôn ngữ cho các giá trị mờ dựa vào xác suất của các
nhãn liên kết trong khi vẫn giữ được các giá trị rõ đã biết, hướng tiếp
cận này đã làm giảm sai số đáng kể cho quá trình huấn luyện. Tuy
vậy, hướng tiếp cận này sẽ phát sinh cây đa phân do có sự phân chia
lớn theo chiều ngang tại các nút ngôn ngữ.
- Phương pháp định lượng ngữ nghĩa theo điểm dựa trên ĐSGT,
nhằm thuần nhất dữ liệu về các giá trị số hay giá trị ngôn ngữ. Bài
toán xây dựng cây quyết định mờ lúc này có thể sử dụng các thuật
toán học theo cách tiếp cận cây quyết định rõ trong một ĐSGT đã
xây dựng. Tuy vậy, hướng tiếp cận này vẫn còn một số vấn đề như:
vẫn xuất hiện sai số lớn khi thuần nhất theo điểm mờ, khó đưa ra dự
đoán khi có sự đan xen ở điểm phân chia mờ của cây kết quả, phụ
thuộc vào miền trị [
min,
max] từ miền giá trị rõ của thuộc tính mờ.
Tất cả các thuật toán học phân lớp bằng cây quyết định hiện có
đều phụ thuộc lớn vào việc chọn tập mẫu của người huấn luyện.
Trong các kho dữ liệu nghiệp vụ, nhiều thông tin phục vụ tốt cho
việc dự đoán nhưng nhiều thông tin khác chỉ có ý nghĩa lưu trữ thông
thường, phục vụ cho việc diễn giải thông tin. Chúng làm phức tạp
mẫu nên tăng chi phí cho quá trình huấn luyện, quan trọng hơn là
chúng gây nhiễu nên cây được xây dựng không có hiệu quả cao.
Xuất phát từ việc tìm hiểu, nghiên cứu các đặc điểm và các thách
thức về các vấn đề của phân lớp dữ liệu bằng cây quyết định, đề tài:
“Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử” là
vấn đề lớn cần giải quyết.
2. Đối tƣợng và phạm vi nghiên cứu
Luận án tập trung nghiên cứu mô hình cho quá trình học từ tập
mẫu huấn luyện, nghiên cứu phương pháp xử lý giá trị ngôn ngữ và
xây dựng các thuật toán học phân lớp bằng cây quyết định mờ đạt
hiệu quả trong dự đoán và đơn giản đối với người dùng.
3
3. Phƣơng pháp nghiên cứu
Luận án sử dụng phương pháp tổng hợp, hệ thống hóa và
phương pháp thực nghiệm khoa học.
4. Mục tiêu và nội dung của luận án
Sau khi nghiên cứu và phân tích các vấn đề về phân lớp dữ liệu
bằng cây quyết định của các nghiên cứu trong và ngoài nước, luận án
đưa ra mục tiêu nghiên cứu chính như sau:
- Xây dựng mô hình học phân lớp dữ liệu bằng cây quyết định
mờ và phương pháp trích chọn đặc trưng để chọn tập mẫu huấn luyện
cho quá trình học phân lớp. Đề xuất phương pháp xử lý giá trị ngôn
ngữ của các thuộc tính chưa thuần nhất dựa vào ĐSGT.
- Đề xuất các thuật toán học bằng cây quyết định mờ nhằm đạt
hiệu quả trong dự đoán và đơn giản đối với người dùng.
Để đáp ứng cho các mục tiêu nghiên cứu trên, luận án tập trung
nghiên cứu các nội dung chính sau:
- Nghiên cứu các thuật toán học cây truyền thống CART, ID3,
C4.5, C5.0, SLIQ, SPRINT trên mỗi tập mẫu huấn luyện để tìm một
phương pháp học phù hợp.
- Nghiên cứu xây dựng mô hình học phân lớp dữ liệu cây quyết,
xây dựng phương pháp trích chọn đặc trưng để chọn tập mẫu huấn
luyện cho việc học cây quyết định từ các kho dữ liệu nghiệp vụ.
- Nghiên cứu để đề xuất phương pháp xử lý giá trị ngôn ngữ của
các thuộc tính chưa thuần nhất trên tập mẫu dựa vào của ĐSGT.
- Đề xuất các thuật toán học phân lớp bằng cây quyết định mờ
đạt hiệu quả trong dự đoán và đơn giản đối với người dùng.
5. Ý nghĩa khoa học và thực tiễn
Ý nghĩa khoa học
Những đóng góp chính của luận án về khoa học:
- Xây dựng mô hình học phân lớp dữ liệu bằng cây quyết định
mờ từ tập mẫu huấn luyện. Đề xuất phương pháp trích chọn đặc
trưng để chọn tập mẫu huấn luyện cho việc học phân lớp bằng cây
quyết định từ các kho dữ liệu, nhằm hạn chế sự phụ thuộc ý kiến của
chuyên gia trong quá trình chọn tập mẫu huấn luyện.
- Đề xuất phương pháp xử lý giá trị ngôn ngữ của các thuộc tính
chưa thuần nhất trên tập mẫu huấn luyện dựa vào bản chất của
ĐSGT.
- Luận án đã xây dựng các hàm mục tiêu của bài toán phân lớp
bằng cây quyết định, sử dụng tính có thứ tự của các giá trị ngôn ngữ
4
trong ĐSGT. Đưa ra các khái niệm đối sánh khoảng mờ, khoảng mờ
lớn nhất để từ đó đề xuất các thuật toán học cây quyết định mờ
MixC4.5, FMixC4.5, HAC4.5 và HAC4.5* cho bài toán phân lớp,
nhằm góp phần cải thiện, nâng cao độ chính xác trong quá trình học
phân lớp dữ liệu bằng cây quyết định cho bài toán phân lớp dữ liệu .
Ý nghĩa thực tiễn
- Góp phần chứng tỏ khả năng ứng dụng phong phú của ĐSGT
trong biểu diễn và xử lý thông tin mờ, không chắc chắn.
- Luận án đã góp phần vào việc giải quyết vấn đề định lượng
cho các giá trị ngôn ngữ mà không phụ thuộc cố định vào miền trị
Min-Max của các giá trị kinh điển của thuộc tính mờ trong tập mẫu.
- Dựa trên các khái niệm về khoảng mờ và khoảng mờ lớn nhất,
luận án đã đề xuất các thuật toán cho quá trình học cây, nhằm tăng
khả năng dự đoán cho bài toán phân lớp dữ liệu bằng cây quyết định.
Làm phong phú thêm các phương pháp học cho bài toán phân lớp nói
chung và phân lớp bằng cây quyết định nói riêng.
- Luận án có thể được sử dụng làm tài liệu tham khảo cho các
sinh viên đại học, học viên cao học ngành Công nghệ thông tin
nghiên cứu về học phân lớp bằng cây quyết định.
6. Bố cục của luận án
Ngoài phần mở đầu, kết luận và tài liệu tham khảo, luận án được
chia làm 3 chương nội dung. Chương 1: Cơ sở lý thuyết về đại số gia
tử và tổng quan phân lớp dữ liệu bằng cây quyết định. Tập trung
phân tích và đánh giá các công trình nghiên cứu đã công bố gần đây,
chỉ ra các vấn đề còn tồn tại để xác định mục tiêu và nội dung cần
giải quyết. Chương 2: Phân lớp dữ liệu bằng cây quyết định mờ theo
phương pháp đối sánh điểm mờ dựa trên đại số gia tử. Tập trung
phân tích sự ảnh hưởng của tập mẫu huấn luyện đối với hiệu quả của
cây thu được. Trình bày phương pháp nhằm trích chọn được tập mẫu
đặc trưng cho quá trình huấn luyện. Phân tích, đưa ra các khái niệm
về tập mẫu không thuần nhất, giá trị ngoại lai và xây dựng thuật toán
để có thể thuần nhất cho các thuộc tính này. Đề xuất các thuật toán
MixC4.5 và FMixC4.5 phục vụ quá trình học cây quyết định trên tập
mẫu không thuần nhất. Chương 3: Phương pháp huấn luyện cây
quyết định mờ cho bài toán phân lớp dữ liệu dựa trên đối sánh
khoảng mờ. Chương này của luận án tập trung nghiên cứu quá trình
học cây quyết định mờ nhằm đạt hai mục tiêu là fh(S) → max và fn(S)
→ min. Trên cơ sở nghiên cứu mối tương quan của các khoảng mờ,