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 – nghiên cứu sinh 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
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 MPM.


Mục lục
Chương 1: Giới thiệu về khai phá dữ liệu ...................................................................... 10


4.1. Giới thiệu ............................................................................................................... 36
4.2. Nội dung................................................................................................................. 36
4.3. Ưu ñiểm và nhược ñiểm của minimax probability machine ................................. 37
4.4. Các phiên bản cải tiến của thuật toán minimax probability machine .................... 38
4.4.1. Minimum error minimax probability machine (MEMPM) .............................. 38
4.4.2. Biased minimax probability machine (BMPM) ................................................ 39
Chương 5: Phương pháp ñề nghị .................................................................................... 41
Danh sách các hình


Danh sách các bảng


Bảng các từ viết tắt
Genetic Algorithm GA
Minimax Probability Machine MPM


Giới thiệu
Những năm gần ñây, các hệ thống cơ sở dữ liệu ñã ñem lại những lợi ích vô cùng to
lớn cho con người. Song hành cùng sự phát triển nhanh chóng của công nghệ thông tin và
những ứng dụng của nó trong ñời sống, kinh tế và xã hội, lượng dữ liệu thu thập ngày
càng nhiều theo thời gian, dẫn ñến việc xuất hiện ngày càng nhiều các hệ thống cơ sở dữ
liệu có kích thước lớn. Trong xã hội hiện ñại, thông tin ñược coi như sức mạnh và là yếu
tố quyết ñịnh thành công trong mọi lĩnh vực, do ñó việc tìm ra thông tin hữu ích trong
khối dữ liệu khổng lồ ñược xem như mục tiêu hàng ñầu của mọi tổ chức và cá nhân.

Chương 6: Kết luận. Chương này là phần tổng kết khóa luận, ñồng thời nêu ra những
mặt còn hạn chế trong phương pháp ñề nghị và những công việc trong tương lai nhằm cải
tiến hiệu quả của phương pháp này.


Chương 1: Giới thiệu về khai phá dữ liệu
1.1. Khai phá dữ liệu là gì?
Có khá nhiều ñịnh nghĩa về khai phá dữ liệu (Data mining), nhưng ñịnh nghĩa ñơn
giản nhất thì khai phá dữ liệu là việc trích rút thông tin hay tri thức mới và có ích từ
nguồn dữ liệu khổng lồ.
Ngoài ra, khai phá dữ liệu còn có thể hiểu là trích rút các thông tin có ích từ những dữ
liệu không tường minh, hoặc trích rút lấy những thông tin không biết trước và tiềm tàng
trong dữ liệu. Cũng có thể hiểu, khai phá dữ liệu là việc phân tích khảo sát một cách tỉ mỉ
số lượng lớn dữ liệu bằng các phương pháp tự ñộng hoặc bán tự ñộng nhằm tìm ra các
mẫu có ích.
Có thể nhận xét rằng, khái niệm khai phá dữ liệu là khá rộng lớn, nhưng không phải
tất cả mọi công việc liên quan ñến dữ liệu ñều ñược coi là khai phá dữ liệu, chẳng hạn
như những việc xử lý truy vấn ñơn giản như tra cứu một số ñiện thoại, hay thống kê ra
những học sinh giỏi của một lớp, thì không thể coi ñó là khai phá dữ liệu. Nhưng những
công việc như gom nhóm các tài liệu trả về từ máy tìm kiếm theo từng ngữ cảnh thì lại
ñược xem là khai phá dữ liệu.
1.2. Tại sao phải tiến hành khai phá dữ liệu?
Trong những năm gần ñây, khai phá dữ liệu trở thành một lĩnh vực nghiên cứu rộng
rãi trong ngành công nghiệp thông tin, nguyên nhân chủ yếu là do khối lượng khổng lồ
của dữ liệu mà con người tạo ra, ñi kèm với nó là sự cần thiết biến ñổi những dữ liệu ñó
thành tri thức. Thông tin và tri thức có thể ñược áp dụng vào nhiều lĩnh vực từ phân tích
thị trường tài chính, phát hiện giả mạo, cho ñến ñiều khiển sản xuất và nghiên cứu khoa
học.

Nhìn vào hai lĩnh vực sinh ra nhiều dữ liệu nhất ñó là thương mại và khoa học. Trong

hợp cho quá trình khai phá.
(5) Khai phá dữ liệu (Data Mining): Sử dụng những phương pháp thông minh ñể khai
thác dữ liệu nhằm thu ñược các mẫu mong muốn.
(6) ðánh giá kết quả (Pattern Evaluation): Sử dụng các ñộ ño ñể ñánh giá kết quả thu
ñược.
(7) Biểu diễn tri thức (Knowledge Presentation): Sử dụng các công cụ biểu diễn trực
quan ñể biểu diễn những tri thức khai phá ñược cho người dùng. Tri thức
ðánh giá &
Trình diễn
Lựa chọn &
Chuyển dạng
Dữ liệu
Kho dữ
liệu
Khai phá
dữ liệu
Dữ liệu
chuyển
dạng
Mẫu
Làm sạch &
Tích hợp

Hình 1.1. Quá trình phát hiện tri thức trong cơ sở dữ liệu.
Quá trình này có thể ñược lặp lại nhiều lần một hay nhiều giai ñoạn dựa trên phản hồi
từ kết quả của các giai ñoạn sau.
1.4. Kiến trúc ñiển hình của một hệ khai phá dữ liệu

Kho dữ
liệu
World
Wide
Kiểu kho
chứa thông tin
Cơ sở tri
thức
Làm sạch, tích hợp và chọn lựa dữ

• Quan hệ kết hợp (Dependency relationship)
Một trong những vấn ñề của phát hiện mối quan hệ là làm rõ ràng và nguyên nhân.
Bài toán tìm luật kết hợp là một ñại diện ñiển hình, thực hiện việc phát hiện ra mối
quan hệ giữa các thuộc tính (các biến), có dạng ở phụ thuộc hàm trong cơ sở dữ liệu
quan hệ.
• Phân lớp (Classification)
Phân lớp còn ñược gọi là học máy có giám sát (supervised learning). Với một tập
các dữ liệu huấn luyện cho trước và sự huấn luyện của con người, các giải thuật phân
loại sẽ học ra bộ phân loại (classifier) dùng ñể phân dữ liệu mới vào trong những lớp
(còn gọi là loại) ñã ñược ñịnh trước. Một số phương pháp ñiển hình là cây quyết ñịnh,
luật phân lớp, mạng neuron.
• Phân cụm (Clustering)
Phân cụm còn ñược gọi là học máy không giám sát (unsupervised learning), thực
hiện việc nhóm dữ liệu thành các lớp mới ñể có thể phát hiện các mẫu phân bố. Phân
cụm chỉ là bái toán mô tả hướng tới việc nhận biết một tập hữu hạn các loại hoặc các
cụm ñể mô tả dữ liệu. Các loại (cụm) có thể rời nhau và toàn phần (tạo nên phân
hoạch) hoặc chồng chéo lên nhau.
• Phân ñoạn (Segmentation)
Về bản chất phân ñoạn là tổ hợp của phân cụm và phân lớp, trong ñó phân cụm
ñược tiến hành trước và sau ñó là phân lớp.

Trực quan hóa


Các kỹ thuật truyền thống không còn thích hợp với các loại dữ liệu bị lỗi, bị nhiễu hay
dữ liệu nhiều chiều và các hệ dữ liệu tự nhiên phân tán hay hỗn tạp. Do ñó khi kết hợp
với nhau, hình thành lĩnh vực mới, ñó là khai phá dữ liệu.
1.7. Các ứng dụng ñiển hình của khai phá dữ liệu
Ứng dụng của khai phá dữ liệu ñược chia thành hai lớp chính bao gồm các ứng dụng
phân tích – hỗ trợ ra quyết ñịnh và lớp các lĩnh vực ứng dụng khác.
• Lớp các ứng dụng trong phân tích dữ liệu và hỗ trợ ra quyết ñịnh bao gồm các ứng
dụng trong:
- Thông tin thương mại: Phân tích dữ liệu Marketing, khách hàng; Phân tích ñầu
tư; Phê duyệt cho vay vốn hay phát hiện gian lận.
- Thông tin kỹ thuật: ðiều khiển và lập trình lịch; Quản trị mạng.
- Bảo hiểm y tế.
- Viễn thông.
- Thể thao
• Lớp các lĩnh vực ứng dụng ñiển hình khác ñược kể ñến là khai phá văn bản, khai
phá Web, khai phá dữ liệu sinh học và khai phá dữ liệu dòng.
1.8. Các thách thức với khai phá dữ liệu
• Cơ sở dữ liệu lớn.
• Số chiều lớn.
• Thay ñổi dữ liệu và tri thức có thể làm cho các mẫu ñã phát hiện không còn phù
hợp.
• Dữ liệu bị thiếu hoặc bị nhiễu.

• Quan hệ giữa các trường phức tạp.
• Giao tiếp với người sử dụng và kết hợp với các tri thức ñã có.
• Tích hợp với các hệ thống khác …
1.9. Kết luận

Stopping
Criterion
YES
NO
Goodness of Subset
Subset
Original
Set

tập con tiềm năng là 2
n
. Vì một tập con tối ưu các ñiểm ñặc trưng không phải là duy nhất
nên số lượng các tập con có thể thỏa mãn là rất lớn, do ñó quá trình tìm kiếm trong trích
chọn ñặc trưng sẽ tốn nhiều thời gian và công sức. Mỗi tập con ñược sinh ra cần phải
ñược ñánh giá và so sánh với những tập con tốt nhất ñã ñược tìm thấy trước. Nếu tập con
tìm thấy sau là tốt hơn thì nó sẽ ñược thay thế cho tập con tốt nhất trước ñây. Nếu không
có một ñiều kiện dừng hợp lý thì quá trình tìm kiếm các tập con tốt nhất sẽ ñược xem như
là vô hạn. Một quá trình trích chọn ñặc trưng có thể dừng khi thỏa mãn một trong những
ñiều kiện ñánh giá sau: (a) chọn ñủ số lượng ñã ñược xác ñịnh trước của tập ñặc trưng,
(b) thỏa mãn số lần ñã ñược xác ñịnh trước của quá trình lặp lại. (c) ở một khía cạnh
(ñiều kiện) nào ñó tập con mới ñược ñánh giá là không tốt hơn tập con trước, (d) tập con
ñược bộ ñánh giá cho là tốt nhất.
2.2. Mô hình trong bài toán trích chọn
2.2.1. Các mô hình trong trích chọn
Trích chọn ñặc trưng thật sự là lý tưởng trong lựa chọn tập con ñặc trưng tối ưu từ
một tập ứng cử ñể mô tả khái niệm mục tiêu trong hệ thống học. ðộ tốt của một tập con
ñặc trưng có thể ñược ñánh giá qua nhiều cách khác nhau, nhờ ñó mà có nhiều mô hình
khác nhau ñược ñưa ra trong phương pháp trích chọn. ðiển hình là hai mô hình: Filter và
Wrapper.


2.2.2. ðánh giá hai mô hình Filter và Wrapper
2.2.2.1. Filter
• Ưu ñiểm:
- Không có xử lý học máy trong quá trình lựa chọn các ñặc trưng.
- Dễ dàng nhận diện và thời gian tiêu thụ ít hơn mô hình Wrapper.
• Nhược ñiểm:
- Hiệu suất sản sinh các tập con ñặc trưng là không ñảm bảo vì nó thường ñánh
giá một tập con ñặc trưng chỉ dựa trên ñặc trưng nhỏ thiên về nguyên lý mà
không tính tới ñộ chính xác của kết quả học máy.
- Kết quả thu ñược bị giảm sút về ñộ chính xác học ở những giai ñoạn sau vì các
hàm ñánh giá hiện thời ñược sử dụng thường thiên về giá trị ở một vài phạm vi,
do ñó sẽ không ñánh giá một cách khách quan tầm quan trọng của các ñặc
trưng.
2.2.2.2. Mô hình Wrapper
• Ưu ñiểm:
- ðảm bảo hiệu suất của kết quả học hơn mô hình Filter.
• Nhược ñiểm:
- Ít ñược sử dụng hơn môt hình Filter trên thực tế vì:
 Tiến trình học tốn kém về thời gian ñến mức thời gian thực hiện ñưa ra bởi
một thuật toán sử dụng mô hình Wrapper là không chấp nhận ñược.
 Với một hệ thống kích thước cực lớn, mô hình này không thực tế do phạm
vi của nó buộc phải thu nhỏ lại trước khi thuật toán học máy ñược áp dụng.

 Kết quả ñánh giá của mô hình phụ thuộc nhiều vào thuật toán học máy ñiều
khiển.
2.3. Một số kỹ thuật xử lý
2.3.1. Bộ sinh tập con (Feature Subset Generator)
Tùy từng chiến lược cụ thể, bộ sinh tập con sẽ tạo ra những tập con ñặc trưng từ một
tập ñầu vào tương ứng. ðầu ra của bộ sinh sẽ xác ñịnh thuật toán trích chọn ñặc trưng của
việc tìm ñường và tìm kiếm phạm vi trong một không gian ñặc trưng tương ứng. Nói

hoặc các ñiều kiện thực thi ñưa ra ñã ñược triệt tiêu hết.
- Lựa chọn hai hướng (Bi – direction Selection): các tập con ñặc trưng ñược
khởi tạo trước hết là rỗng, ñầy, hoặc sản sinh ngẫu nhiên một tập con ñặc
trưng, sau ñó liên tục hoặc là gán tính năng tốt nhất hiện thời cho tập con ñó
hoặc là triệt tiêu tính năng kém nhất từ các tập con ñó. ðể từ ñó ñưa ra
những giá trị ñịnh hướng tốt nhất ở mỗi lần lặp lại ñó. Quá trình tiếp tục
cho tới khi tất cả ñiều kiện ñược ñưa ra từ trước ñã ñược tiếp nhận hết.
Bộ phận khởi tạo kinh nghiệm giảm thiểu phạm vi tìm kiếm ña thức số mũ, do ñó
giảm thời gian thực hiện thuật toán phức tạp trong phương pháp trích chọn. Tuy nhiên,
thuật toán chỉ ñưa ra một lượng nhỏ kết quả tối ưu, khi thực hiện tìm ñường và tìm kiếm
phạm vi của bộ phận khởi tạo, kết quả này ñược ñảm bảo thông qua những thuật toán này.
2.3.2. Bộ ñánh giá tập con ñặc trưng (Feature Subset Evaluator)
Hiệu suất của một tập con ñặc trưng ñược ñánh giá dựa trên cơ sở nào ñó mà bộ ñánh
giá ñạt ñược. Bộ ñánh giá của những mô hình thuật toán khác nhau là khác nhau. Bộ ñánh
giá của mô hình Filter thường là các hàm ñánh giá, trong khi của mô hình Wrapper là ñộ
học chính xác ñạt ñược bởi quá trình thực thi thuật toán học máy ñiều khiển trên hệ thống
học.
• Hàm ñánh giá

Những hàm ñánh giá ñiển hình dùng ñể ño ñạc và phân biệt khả năng phân lớp của
những ñặc ñiểm khác nhau trên các mẫu. Thực tế, các hàm ñánh giá khác nhau
thường ñược dùng hiện nay như: xấp xỉ chất lượng (Approximation Quality), ñộ
quan trọng của thuộc tính (Feature Importance), trọng số của thuộc tính (Feature
Weight) …
• Học chính xác
Trong mô hình Wrapper, ñể ước lượng ñộ học máy chính xác, trước hết, các mẫu
của hệ thống học phải ñược chia ngẫu nhiên làm hai hệ thống con, chẳng hạn như:
hệ thống huấn luyện và hệ thống kiểm tra, trong ñó, cấu trúc của hai hệ thống con
có cùng ñặc ñiểm và ñược tạo ra bởi bộ sinh; sau ñó thuật toán học máy ñiều khiển
sẽ thực hiện trên hệ thống con huấn luyện (training) và tiếp thu ñộ học chính xác