ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
Trần Phƣơng Nhung
ÁP DỤNG PHƢƠNG PHÁP TRÍCH CHỌN THUỘC
TÍNH ĐẶC TRƢNG ĐỂ NÂNG CAO HIỆU QUẢ
PHÂN LỚP KHI KHAI PHÁ DỮ LIỆU LỚN
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
HÀ NỘI - 2009
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
Trần Phƣơng Nhung
ÁP DỤNG PHƢƠNG PHÁP TRÍCH CHỌN THUỘC
TÍNH ĐẶC TRƢNG ĐỂ NÂNG CAO HIỆU QUẢ
PHÂN LỚP KHI KHAI PHÁ DỮ LIỆU LỚN
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
Cán bộ hƣớng dẫn: TS. Nguyễn Hà Nam
HÀ NỘI - 2009
Lời cảm ơn
“Để hoàn thành khóa luận này, tôi xin gửi lời cảm ơn chân thành tới quý thầy cô
trong trường Đại học Công Nghệ - ĐHQGHN đã tận tình chỉ bảo tôi trong suốt bốn năm
học đại học. Tôi cũng xin cảm ơn sự hướng dẫn nhiệt tình của thầy Nguyễn Hà Nam,
cùng sự giúp đỡ của anh Đặng Tất Đạt – sinh viên cao học khoa Toán Tin trường Đại
học Tự Nhiên, ĐHQGHN.
Tôi cũng thầm biết ơn sự ủng hộ của gia đình, bạn bè – những người thân yêu luôn
luôn là chỗ dựa tinh thần vững chắc cho tôi.”
Hà Nội, tháng 05 năm 2009.
Sinh viên
Trần Phương Nhung
1
Tóm tắt khóa luận
Trong khóa luận này tôi áp dụng thuật toán di truyền (Genetic Algorithm) để bước
đầu cải tiến hiệu quả phân lớp của phương pháp minimax probability machine (MPM).
Phần đầu tôi xin giới thiệu tổng quan về khái niệm khai phá dữ liệu. Tiếp đó, tôi sẽ trình
bày về cơ sở lý thuyết của thuật toán di truyền và phương pháp phân lớp minimax
probability machine. Cuối cùng, tôi sẽ mô tả chi tiết về quá trình xây dựng hệ thống có
ứng dụng thuật toán di truyền trong phân lớp minimax probability machine để chuẩn đoán
bệnh ung thư. Mô hình phân lớp mới này sẽ được chạy thử trên một số cơ sở dữ liệu lớn
và đưa ra những số liệu thống kê để có thể thấy được hiệu quả của hệ thống so với
phương pháp phân lớp chỉ sử dụng minimax probability machine.
2
Mục lục
Giới thiệu ......................................................................................................................... 8
Chương 1: Giới thiệu về khai phá dữ liệu .................................................................... 10
1.1. Khai phá dữ liệu là gì? ...................................................................................... 10
1.2. Tại sao phải tiến hành khai phá dữ liệu? ........................................................... 10
1.3. Quá trình khai phá dữ liệu ................................................................................ 11
1.4. Kiến trúc điển hình của một hệ khai phá dữ liệu ............................................... 12
1.5. Các bài toán khai phá dữ liệu điển hình ............................................................ 13
1.6. Các lĩnh vực liên quan đến khai phá dữ liệu ..................................................... 15
1.7. Các ứng dụng điển hình của khai phá dữ liệu ................................................... 15
1.8. Các thách thức với khai phá dữ liệu .................................................................. 16
1.9. Kết luận ............................................................................................................ 16
Chương 2: Trích chọn thuộc tính phù hợp .................................................................. 17
2.1. Giới thiệu ......................................................................................................... 17
2.2. Mô hình trong bài toán trích chọn ..................................................................... 18
2.2.1. Các mô hình trong trích chọn .................................................................... 18
2.2.2. Đánh giá hai mô hình Filter và Wrapper ................................................... 19
2.2.2.1. Mô hình Filter .................................................................................... 19
2.2.2.2. Mô hình Wrapper ............................................................................... 19
2.3. Một số kỹ thuật xử lý........................................................................................ 20
2.3.1. Bộ sinh tập con (Feature Subset Generator) .............................................. 20
2.3.2. Bộ đánh giá tập con đặc trưng (Feature Subset Evaluator) ....................... 21
2.3.3. Thuật toán học điều khiển (Central machine learning algorithm) .............. 22
2.4. Kết luận ............................................................................................................ 22