TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI 2
KHOA CÔNG NGHỆ THÔNG TIN
*************




PHAN THỊ NGỌC TRINH





THUẬT TOÁN ID3
VÀ CHƢƠNG TRÌNH MÔ PHỎNG
CHUẨN ĐOÁN BỆNH CÚM H1N1


KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
Chuyên ngành: Khoa học máy tính

HÀ NỘI, 2015





TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI 2
KHOA CÔNG NGHỆ THÔNG TIN
*************



PHAN THỊ NGỌC TRINH




THUẬT TOÁN ID3
VÀ CHƢƠNG TRÌNH MÔ PHỎNG
CHUẨN ĐOÁN BỆNH CÚM H1N1



KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
Chuyên ngành: Khoa học máy tính

Ngƣời hƣớng dẫn khoa học
PGS. TS. Bùi Thế Hồng






HÀ NỘI, 2015




LỜI CẢM ƠN
Trong suốt quá trình học tập và thực hiện đề tài khóa luận, em đã nhận
đƣợc sự giúp đỡ, tạo điều kiện của tập thể lãnh đạo, các thầy, cô giáo Trƣờng
Đại học Sƣ phạm Hà Nội 2 nói chung và các thầy, cô giáo Khoa Công nghệ
thông tin nói riêng. Em xin bày tỏ lòng cảm ơn chân thành về sự giúp đỡ đó.
Em xin bày tỏ lòng biết ơn sâu sắc tới PGS.TS. Bùi Thế Hồng, ngƣời
thầy đã trực tiếp hƣớng dẫn và chỉ bảo cho em hoàn thành khóa luận này.
Em xin gửi lời cảm ơn đến gia đình, các bạn học đã chia sẻ, động viên
khích lệ em về chuyên môn cũng nhƣ mọi mặt trong cuộc sống để em có thể
hoàn thành tốt khóa luận.
Do thời gian và kinh nghiệm nghiên cứu khoa học chƣa nhiều nên khóa
luận còn nhiều thiếu xót, rất mong nhận đƣợc sự đóng góp của các thầy, cô
giáo và các bạn để khóa luận đƣợc hoàn thiện hơn.












Hà Nội, ngày 10 tháng 05 năm 2015
Sinh viên
Phan Thị Ngọc Trinh




LỜI CAM ĐOAN
Tên em là: Phan Thị Ngọc Trinh
Sinh viên lớp: K37A - Tin học, khoa Công nghệ Thông tin, trƣờng Đại
học Sƣ phạm Hà Nội 2.
Em xin cam đoan:
1. Đề tài: “Thuật toán ID3 và chƣơng trình mô phỏng chuẩn đoán bệnh
cúm H1N1” là nghiên cứu của riêng em dƣới sự hƣớng dẫn của PGS. TS. Bùi
Thế Hồng.
2. Kết quả nghiên cứu của em không trùng với bất cứ một kết quả nào
của những tác giả khác.
3. Các kết quả nêu trong khóa luận là do nghiên cứu thực tiễn đảm bảo
tính chính xác và trung thực.
Nếu sai em xin hoàn toàn chịu trách nhiệm.









Hà Nội, ngày 10 tháng 05 năm 2015
Sinh viên thực hiện
(Ký và ghi rõ họ tên)
Phan Thị Ngọc Trinh




MỤC LỤC

MỞ ĐẦU 1
CHƢƠNG 1: CƠ SỞ LÝ THUYẾT 2
1.1. Quá trình phát hiện tri thức 3
1.2. Khai phá dữ liệu 5
1.2.1. Tính cp bách ca vic khai phá d liu 5
1.2.2. Mc tiêu ca khai phá d liu 5
1.2.3. Quá trình khai phá d liu 7
1.2.4. Các dng d liu có th khai phá 8
1.3. Ứng dụng của khai phá dữ liệu 9
1.3.1. Phân tích d liu tài chính (Financial Data Analysis) 9
1.3.2. Công nghip bán l (Retail Industry) 10
1.3.3. Công nghip vin thông (Telecommunication Industry) 10
1.3.4. Phân tích d liu sinh hc (Biological Data Analysis) 11
1.3.5. Phát hin xâm nhp bt hp pháp (Intrusion Detection) 11
1.4. Hàm Entropy 11
1.5. Hàm Gain 12
1.6. Một số phƣơng pháp khai phá dữ liệu 13
1.6.1. Cây quynh và lut 13
n và quy np 13

1.6.3. Lut kt hp 14
n 14
1.6.5. Mng neural 14
1.6.6. Gii thut di truyn 15
CHƢƠNG 2: KHAI PHÁ DỮ LIỆU SỬ DỤNG CÂY QUYẾT ĐỊNH 16
2.1. Giới thiệu 16
2.1.1. K thut khai phá s dng cây quynh 16
m 16




2.1.3. Cu trúc cây quynh 17
u kin dng ca cây quynh 18
2.2. Thuật toán 18
2.2.1. Thut toán CLS 18
2.2.2. Thut toán ID3 24
2.2.3. Thuật toán C4.5 34
2.3. Rút gọn cây quyết định 42
2.4. Rút gọn các luật từ cây quyết định 44
CHƢƠNG 3: XÂY DỰNG CHƢƠNG TRÌNH MÔ PHỎNG 46
3.1. Phát biểu bài toán 46
3.2. Giải quyết bài toán 47
3.2.1. Áp dng thut toán 47
3.2.2. Hàm xây dng cây quynh 47
3.2.3. Tính giá tr Gain cho các thuc tính 48
KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN 62
TÀI LIỆU THAM KHẢO 64



1

MỞ ĐẦU
1. Lý do chọn đề tài
Ngày nay, sự phát triển mạnh mẽ của Công nghệ thông tin đã làm cho
khả năng thu thập và lƣu trữ thông tin của các hệ thống thông tin tăng nhanh,
lƣợng dữ liệu mà chúng ta lƣu trữ trở nên quá nhiều, gây khó khăn cho việc
lấy ra đƣợc những thông tin hữu ích.
Do vậy, cần có những kỹ thuật và công cụ mới để tự động chuyển đổi
lƣợng dữ liệu khổng lồ kia thành các tri thức hữu ích. Với hàng loạt các công
trình nghiên cứu, giải pháp đƣợc thử nghiệm và ứng dụng thành công vào đời
sống đã chứng minh khai phá dữ liệu là lĩnh vực nghiên cứu có nền tảng lý
thuyết vững chắc. Đã có rất nhiều nghiên cứu về khai phá dữ liệu của các nhà
khoa học và cho tới hiện tại khai phá dữ liệu vẫn luôn là lĩnh lực đƣợc nhiều
ngƣời quan tâm.
Một trong những phƣơng pháp khai phá dữ liệu có hiệu quả, đƣợc ứng
dụng nhiều là phƣơng pháp cây quyết định. Vì khả năng ứng dụng thiết thực
vào đời sống xã hội của phƣơng pháp này rất cao nên em đã chọn đề tài
“Thuật toán ID3 và chƣơng trình mô phỏng chuẩn đoán bệnh cúm H1N1” để
làm đề tài khóa luận tốt nghiệp.
2. Mục đích nghiên cứu
- Hiểu đƣợc tổng quan về khai phá dữ liệu và phát hiện tri thức.
- Nghiên cứu các vấn đề cơ bản của thuật toán xây dựng cây quyết định
ID3, cài đặt và đánh giá thuật toán đó. Áp dụng mô hình cây quyết định ID3
để chuẩn đoán bệnh cúm H1N1.
3. Đối tƣợng và phạm vi nghiên cứu
Nghiên cứu về Khai phá dữ liệu, các thuật toán khai phá dữ liệu cơ bản
và xây dựng chƣơng trình minh họa thuật toán ID3 để chuẩn đoán bệnh cúm
H1N1.




2

4. Nhiệm vụ nghiên cứu
- Tìm hiểu về khai phá dữ liệu và các thuật toán phân lớp dữ liệu.
- Xây dựng chƣơng trình chuẩn đoán bệnh cúm H1N1 bằng thuật toán
ID3. Cài đặt thử nghiệm và đánh giá kết quả.
5. Giả thuyết khoa học
Tìm hiểu nghiên cứu một số thuật toán phân lớp dữ liệu giúp ra quyết
định dễ dàng hơn trong việc lựa chọn và có những quyết định đúng đắn.
Chƣơng trình đƣợc xây dựng dựa trên thuật toán ID3 không chỉ có ích
trong lĩnh vực y tế mô phỏng chuẩn đoán bệnh cúm H1N1 mà còn có thể áp
dụng hiệu quả đối với những dạng dữ liệu tƣơng tự thuộc nhiều lĩnh vực khác.
6. Phƣơng pháp nghiên cứu
a. Phương pháp nghiên cứu lý luận
Nghiên cứu qua việc đọc sách, báo, tài liệu web và các thông tin liên
quan nhằm xây dựng cơ sở lý thuyết và các biện pháp cần thiết để giải quyết
các vấn đề cần thiết của đề tài.
b. Phương pháp chuyên gia
Tham khảo ý kiến của các chuyên gia để có thể thiết kế chƣơng trình phù
hợp với yêu cầu thực tiễn. Nội dung xử lý nhanh đáp ứng nhu cầu ngày càng
cao của ngƣời sử dụng.
Phân tích và tổng hợp các tài liệu về khai phá dữ liệu sử dụng thuật toán
về Cây quyết định có thuật toán ID3, phân loại dữ liệu, mô hình dự báo.
c. Phương pháp thực nghiệm
Thông qua quan sát thực tế, yêu cầu của cơ sở, những lý luận đƣợc
nghiên cứu và kết quả đạt đƣợc qua những phƣơng pháp trên.
7. Cấu trúc khóa luận
Ngoài phần mở đầu, kết luận và hƣớng phát triển, tài liệu tham khảo,

khóa luận gồm các chƣơng sau:
- Chƣơng 1: Cơ sở lý thuyết
- Chƣơng 2: Khai phá dữ liệu sử dụng cây quyết định
- Chƣơng 3: Xây dựng chƣơng trình mô phỏng

3

CHƢƠNG 1: CƠ SỞ LÝ THUYẾT
1.1. Quá trình phát hiện tri thức
Khám phá tri thức là một lĩnh vực nghiên cứu mới mở ra một thời kỳ
trong việc tìm ra những thông tin hữu ích. Nhiệm vụ cơ bản của lĩnh vực này
là khám phá tri thức trong cơ sở dữ liệu. Khám phá dữ liệu trong cơ sở dữ liệu
không phải là một hệ thống phân tích tự động mà là một quá trình tƣơng tác
thƣờng xuyên giữa con ngƣời với cơ sở dữ liệu đƣợc sự trợ giúp của nhiều
phƣơng pháp và công cụ tin học.
Trong thời đại ngày nay, kinh tế xã hội phát triển đi liền với bùng nổ về
công nghệ thông tin và sự cạnh tranh trong nhiều lĩnh vực ngày càng cao. Yếu
tố quyết định thành công trong mọi lĩnh vực luôn gắn liền với việc nắm bắt,
thống kê và khai thác thông tin hiệu quả. Dữ liệu ngày càng lớn nên việc tìm
ra những thông tin tiềm ẩn trong chúng ngày càng khó khăn vì vậy phát hiện
tri thức là một quá trình quan trọng.













Hình 1.1. Quá trình phát hin tri thc


Hình thành và
Định nghĩa bài toán
Sử dụng các tri thức
phát hiện đƣợc
Phân tích và kiểm
định kết quả
Thu thập và
Tiền xử lý dữ liệu
Khai phá dữ liệu
Rút gọn tri thức

4

Quá trình phát hiện tri thức bao gồm các bƣớc sau:
Bƣớc 1: Hình thành và định nghĩa bài toán
Đây là bƣớc tìm hiểu lĩnh vực ứng dụng và hình thành bài toán, quyết
định cần rút ra những dạng tri thức nhƣ thế nào, đồng thời lựa chọn các
phƣơng pháp khai phá dữ liệu thích hợp với mục đích ứng dụng và bản chất
của dữ liệu.
Bƣớc 2: Thu thập và tiền xử lý dữ liệu
Thu thập và tiền xử lý dữ liệu là thu thập và xử lý thô còn đƣợc gọi là
tiền xử lý dữ liệu nhằm loại bỏ nhiễu, xử lý việc thiếu dữ liệu, biến đổi dữ liệu
và rút gọn dữ liệu khi cần thiết. Bƣớc này thƣờng chiếm nhiều thời gian nhất
trong quá trình phát hiện tri thức.

Bƣớc 3: Khai phá dữ liệu và rút ra các tri thức
Đây là bƣớc khai phá dữ liệu hay nói cách khác là trích ra đƣợc các mẫu
và các mô hình ẩn dƣới các dữ liệu. Đây là bƣớc quan trọng nhất trong tiến
trình phát hiện tri thức.
Bƣớc 4: Phân tích và kiểm định kết quả
Bƣớc thứ 4 là hiểu các tri thức đã tìm đƣợc, đặc biệt là làm sáng tỏ các
mô tả và dự đoán. Trong bƣớc này, kết quả tìm đƣợc sẽ biến đổi sang dạng
phù hợp với các lĩnh vực ứng dụng và dễ hiểu hơn cho ngƣời dùng.
Bƣớc 5: Sử dụng các tri thức phát hiện đƣợc
Các tri thức khám phá đƣợc sẽ đƣợc củng cố, kết hợp lại thành một hệ
thống, đồng thời giải quyết các xung đột tiềm năng trong các tri thức đó. Các
mô hình rút ra đƣợc đƣa vào những hệ thống thông tin thực tế dƣới dạng các
môđun hỗ trợ việc đƣa ra quyết định.
Các giai đoạn của quá trình phát hiện tri thức có mối quan hệ chặt chẽ
với nhau trong bối cảnh chung của hệ thống. Các kỹ thuật sử dụng trong giai
đoạn trƣớc có thể ảnh hƣởng tới hiệu quả của các giải thuật đƣợc sử dụng
trong những giai đoạn tiếp theo. Các bƣớc của quá trình phát hiện tri thức có
thể đƣợc lặp đi lặp lại một số lần, kết quả thu đƣợc có thể đƣợc lấy trung bình
trên tất cả những lần thực hiện.

5

1.2. Khai phá dữ liệu
1.2.1. Tính cấp bách của việc khai phá dữ liệu
Công nghệ thông tin đƣợc ứng dụng nhiều trong các lĩnh vực của đời
sống, kinh tế xã hội và một trong những ứng dụng quan trọng là khai phá dữ
liệu. Tuy nhiên sự phát triển của Công nghệ thông tin cũng đồng nghĩa với
việc lƣợng dữ liệu cần đƣợc thu thập, tích lũy ngày càng tăng lên. Chúng ẩn
chứa những giá trị nào đó thƣờng đƣợc sử dụng và phân tích một lƣợng nhỏ
khi cần thiết số còn lại không biết phải làm gì nhƣng vẫn phải giữ lại vì lo

ngại lúc nào đó cần dùng đến.
Ngoài chức năng khai phá dữ liệu có tính chất tác nghiệp có thể nhìn
thấy ngay trƣớc mắt thì trong kinh doanh “tri thức” đƣợc rút ra từ những dữ
liệu đó giữ vai trò quan trọng hơn. Vì vậy các phƣơng pháp quản trị, khai thác
cơ sở dữ liệu truyền thống ngày càng không đáp ứng yêu cầu đặt ra. Để lấy
đƣợc những thông tin có tính “tri thức” trong khối dữ liệu khổng lồ này, yêu
cầu đặt ra là đi tìm những kỹ thuật có khả năng hợp nhất các dữ liệu từ các hệ
thống dữ kiệu khác nhau, chuyển đổi thành một tập hợp các cơ sở dữ liệu ổn
định, có chất lƣợng đƣợc sử dụng chỉ riêng cho một vài mục đích nào đó. Các
kỹ thuật đó đƣợc gọi chung là kỹ thuật tạo kho dữ liệu (Data Warehousing) và
môi trƣờng các dữ liệu đó đƣợc gọi là các kho dữ liệu.
Với áp lực cạnh tranh rất mạnh trƣớc một khối lƣợng lƣu trữ khổng lồ
nhƣ vậy, đƣa ra những quyết định đúng đắn kịp thời là điều không dễ dàng.
Vì vậy có thể sử dụng những kỹ thuật khai phá dữ liệu nhƣ: Kho dữ liệu sử
dụng để hỗ trợ cho phân tích trực tuyến, kỹ thuật học máy, phƣơng pháp
thống kê…Tuy nhiên mỗi kỹ thuật lại có các ƣu nhƣợc điểm riêng, một giải
pháp công nghệ mới đƣợc nghiên cứu đáp ứng cả nhu cầu trong khoa học lẫn
trong thực tiễn là công nghệ phát hiện tri thức và khai phá dữ liệu
(Knowledeg Discovery and Data Mining - KDD).
1.2.2. Mục tiêu của khai phá dữ liệu
Khai phá dữ liệu là trích rút và giải thích những thông tin hữu ích, chƣa
biết, tiềm ẩn trong khối dữ liệu lớn. Hơn nữa khai phá dữ liệu đƣợc dùng để

6

mô tả quá trình phát hiện ra tri thức trong cơ sở dữ liệu. Quá trình này kết
xuất ra các tri thức tiềm ẩn từ dữ liệu giúp cho việc dự báo kinh doanh, các
hoạt động sản xuất, … Khai phá dữ liệu làm giảm chi phí về thời gian so với
phƣơng pháp truyền thống trƣớc kia (Ví dụ nhƣ phƣơng pháp thống kê).
Sau đây là một số định nghĩa mang tính mô tả của nhiều tác giả về khai

phá dữ liệu.
Định nghĩa của Ferruzza: “Khai phá dữ liệu là tập hợp các phƣơng pháp
đƣợc dùng trong tiến trình khám phá tri thức để chỉ ra sự khác bệt các mối
quan hệ và các mẫu chƣa biết bên trong dữ liệu”
Định nghĩa của Parsaye: “Khai phá dữ liệu là quá trình trợ giúp quyết
định, trong đó chúng ta tìm kiếm các mẫu thông tin chƣa biết và bất ngờ trong
cơ sở dữ liệu lớn”
Định nghĩa của Fayyad: “Khai phá tri thức là một quá trình không tầm
thƣờng nhận ra những mẫu dữ liệu có giá trị, mới, hữu ích, tiềm năng và có
thể hiểu đƣợc”.
Khai phá dữ liệu nhằm thực hiện các mục tiêu sau:
- Dự đoán: Sử dụng một vài biến để dự báo giá trị chƣa biết hoặc giá trị
tƣơng lai của các biến khác.
- Nhận dạng: Các mẫu dữ liệu có thể sử dụng để xác định sự tồn tại của
một mục, sự kiện hoặc một hoạt động.
- Phân lớp: Khai phá dữ liệu có thể phân vùng dữ liệu dựa vào việc phát
hiện ra mô tả của vài lớp đã đƣợc xác định và phân loại dữ liệu vào trong các
lớp đó.
- Tối ƣu hóa: Một trong những mục tiêu cuối cùng của khai phá dữ liệu
là có thể tối ƣu hóa việc sử dụng các nguồn tài nguyên hạn chế nhƣ thời gian,
không gian, tiền bạc hoặc nguyên vật liệu.





7

1.2.3. Quá trình khai phá dữ liệu
Khai phá dữ liệu là giai đoạn quan trọng nhất trong tiến trình khai phá tri

thức từ cơ sở dữ liệu, các tri thức này hỗ trợ trong việc ra quyết định trong
khoa học và kinh doanh.
Hình 1.2. Quá trình khai phá d liu
Quá trình khai phá dữ liệu đƣợc thực hiện qua 6 giai đoạn nhƣ Hình 1.2
- Giai đoạn 1: Gom dữ liệu (Gathering)
Tập hợp dữ liệu là bƣớc đầu tiên trong khai phá dữ liệu. Bƣớc này dữ
liệu đƣợc lấy từ trong một cơ sở dữ liệu, một kho dữ liệu và thậm chí là các
dữ liệu từ những nguồn cung ứng web.
- Giai đoạn 2: Trích lọc dữ liệu (Selection)
Dữ liệu đƣợc lựa chọn và phân chia theo một số tiêu chuẩn nào đó ví dụ
nhƣ ngƣời có tuổi đời từ 18 - 20 và có trình độ đại học.
- Giai đoạn 3: Làm sạch và tiền sử lý dữ liệu (Cleaning, Pre - processing
preparation)
Đây là một bƣớc rất quan trọng trong quá trình khai phá dữ liệu. Một số
lỗi thƣờng mắc phải khi gom dữ liệu là dữ liệu không đầy đủ hoặc không
thống nhất, thiếu chặt chẽ. Giai đoạn này nhằm xử lý các dạng dữ liệu không
chặt chẽ nói trên. Vì những dữ liệu này thƣờng đƣợc xem là thông tin thừa,
không có giá trị nên đây là một quá trình rất quan trọng. Nếu dữ liệu không

8

đƣợc “làm sạch - tiền xử lý - chuẩn bị trƣớc” thì sẽ gây nên những kết quả sai
lệch về sau.
- Giai đoạn 4: Chuyển đổi dữ liệu (Transformation)
Trong giai đoạn này dữ liệu có thể đƣợc tổ chức và sử dụng lại. Mục đích
của việc chuyển đổi dữ liệu là làm cho dữ liệu phù hợp hơn với mục đích khai
phá.
- Giai đoạn 5: Phát hiện và trích rút mẫu dữ liệu (Pattern extraction and
discovery)
Đây là bƣớc mang tính tƣ duy trong khai phá dữ liệu. Ở trong giai đoạn

này nhiều thuật toán khác nhau đã đƣợc sử dụng để trích ra các mẫu từ dữ liệu.
Thuật toán thƣờng dùng để trích mẫu dữ liệu là thuật toán phân loại dữ liệu,
kết hợp dữ liệu, thuật toán mô hình hoá dữ liệu tuần tự…
- Giai đoạn 6: Đánh giá kết quả mẫu (Evaluation of result )
Đây là giai đoạn cuối cùng trong quá trình khai phá dữ liệu, ở giai đoạn
này các mẫu dữ liệu đƣợc chiết xuất ra bởi phần mềm khai phá dữ liệu.
Không phải mẫu dữ liệu nào cũng hữu ích, đôi khi nó còn bị sai lệch. Vì vậy
cần phải đƣa ra những tiêu chuẩn đánh giá độ ƣu tiên cho các mẫu dữ liệu để
rút ra đƣợc những tri thức cần thiết.
Trên đây là 6 giai đoạn trong quá trình khai phá dữ liệu, trong đó giai
đoạn 5 là giai đoạn đƣợc quan tâm nhiều nhất hay còn gọi đó là Khai phá dữ
liệu. Các bƣớc trên có thể lặp đi lặp lại một số lần, kết quả thu đƣợc có thể
đƣợc lấy trung bình trên tất cả các lần thực hiện.
1.2.4. Các dạng dữ liệu có thể khai phá
Khai phá dữ liệu đƣợc ứng dụng rộng rãi nên có rất nhiều kiểu dữ liệu
khác nhau đƣợc chấp nhận để khai phá, sau đây là một số loại điển hình:
- Cơ sở dữ liệu quan hệ (Relational databases):
Các cơ sở dữ liệu tác nghiệp đƣợc tổ chức theo mô hình dữ liệu quan hệ.
Hầu hết các hệ quản trị cơ sở dữ liệu đều hỗ trợ dạng cơ sở dữ liệu này.
- Cơ sở dữ liệu đa chiều (Multimensional structures, Data warehouses,
Data mart):

9

Các kho dữ liệu đƣợc tập hợp, chọn lọc từ nhiều nguồn dữ liệu khác nhau.
Dạng dữ liệu này mang tính lịch sử và chủ yếu phục vụ cho quá trình phân
tích cũng nhƣ là khai phá tri thức nhằm hỗ trợ cho việc ra quyết định.
- Cơ sở dữ liệu dạng giao dịch (Transactional databases):
Là dạng cơ sở dữ liệu tác nghiệp nhƣng các bản ghi thƣờng là các giao
dịch. Dạng dự liệu này thƣờng phổ biến trong lĩnh vực thƣơng mại và ngân

hàng.
- Cơ sở dữ liệu quan hệ hƣớng đối tƣợng (Object - Relational Databases):
Cơ sở dữ liệu lai giữa hai mô hình quan hệ và hƣớng đối tƣợng.
- Dữ liệu không gian và thời gian (Spatial, Temporal and time - Series
data):
Dữ liệu có tích hợp thuộc tính về không gian hoặc thời gian.
- Cơ sở dữ liệu đa phƣơng diện (Multimedia databases):
Dữ liệu âm thanh (audio), hình ảnh (image), phim ảnh (video), Text &
WWW … Dạng dữ liệu này hiện đang rất phổ biến trên Internet do sự ứng
dụng rộng rãi của nó.
1.3. Ứng dụng của khai phá dữ liệu
Khai phá dữ liệu đã và đang đƣợc ứng dụng rộng rãi trong rất nhiều lĩnh
vực và hiện nay đã có rất nhiều công cụ thƣơng mại và phi thƣơng mại triển
khai các nhiệm vụ của khai phá dữ liệu. Sau đây là một số lĩnh vực mà Khai
phá dữ liệu đang đƣợc ứng dụng rộng rãi.
1.3.1. Phân tích dữ liệu tài chính (Financial Data Analysis)
Dữ liệu tài chính trong ngân hàng và trong ngành tài chính nói chung
thƣờng đáng tin cậy và có chất lƣợng cao, tạo điều kiện cho khai phá dữ liệu.
Dƣới đây là một số ứng dụng điển hình trong khai phá dữ liệu tài chính:
- Dự đoán khả năng vay và thanh toán của khách hàng, phân tích chính
sách tín dụng đối với khách hàng.
- Phân tích hành vi khách hàng (vay, gửi tiền).
- Phân loại và phân nhóm khách hàng mục tiêu cho tiếp thị tài chính.
- Phát hiện các hoạt động rửa tiền và tội phạm tài chính khác.

10

1.3.2. Công nghiệp bán lẻ (Retail Industry)
Khai phá dữ liệu có vai trò rất quan trọng trong ngành công nghiệp bán lẻ,
do dữ liệu thu thập từ lĩnh vực này rất lớn từ doanh số bán hàng, lịch sử mua

hàng của khách hàng, vận chuyển hàng hóa, tiêu thụ và dịch vụ. Điều tự nhiên
là khối lƣợng dữ liệu từ ngành công nghiệp này sẽ tiếp tục tăng lên nhanh
chóng và dễ dàng thu thập bởi tính sẵn có trên môi trƣờng Web. Ứng dụng
khai phá dữ liệu trong ngành công nghiệp bán lẻ nhằm xây dựng mô hình giúp
xác định xu hƣớng mua hàng của khách hàng, giúp doanh nghiệp cải thiện
chất lƣợng sản phẩm dịch vụ nhằm nâng cao sự hài lòng của khách hàng
và giữ chân khách hàng tốt.
Một số ứng dụng của khai phá dữ liệu trong ngành công nghiệp bán lẻ:
- Khai phá dữ liệu trên kho dữ liệu khách hàng.
- Phân tích đa chiều trên kho dữ liệu khách hàng về doanh số bán hàng,
khách hàng, sản phẩm, thời gian và khu vực.
- Phân tích hiệu quả của các chiến dịch bán hàng, Marketing.
- Quản trị mối quan hệ khách hàng (CRM).
- Giới thiệu và tƣ vấn sản phẩm phù hợp cho khách hàng.
1.3.3. Công nghiệp viễn thông (Telecommunication Industry)
Công nghiệp viễn thông là một trong những ngành công nghiệp mới
nổi, cung cấp nhiều dịch vụ nhƣ trên điện thoại di động, Internet, truyền hình
ảnh Do sự phát triển mạnh của công nghệ máy tính và mạng máy tính, viễn
thông đang phát triển với tốc độ rất lớn. Đây là lý do tại sao khai phá dữ
liệu trở nên rất quan trọng trong lĩnh vực này. Khai phá dữ liệu trong ngành
công nghiệp viễn thông giúp xác định các mô hình viễn thông, phát hiện các
hoạt động gian lận trong viễn thông, sử dụng tốt hơn nguồn tài nguyên và cải
thiện chất lƣợng dịch vụ viễn thông.
Một số ứng dụng của khai phá dữ liệu trong ngành công nghiệp viễn
thông:
- Phân tích dữ liệu đa chiều viễn thông.
- Xây dựng các mô hình phát hiện gian lận.

11


- Phát hiện bất thƣờng trong giao dịch viễn thông.
- Phân tích hành vi sử dụng dịch vụ viễn thông của khách hàng.
- Sử dụng các công cụ trực quan trong phân tích dữ liệu viễn thông.
1.3.4. Phân tích dữ liệu sinh học (Biological Data Analysis)
Khai phá dữ liệu sinh học là một phần rất quan trọng của lĩnh vực Tin -
Sinh học (Bioinformatics). Sau đây là một số ứng dụng của khai phá dữ liệu
ứng dụng trong sinh học:
- Lập chỉ mục, tìm kiếm tƣơng tự, bất thƣờng trong cơ sở dữ liệu Gen.
- Xây dựng mô hình khai phá các mạng di truyền và cấu trúc của
Gen, Protein.
- Xây dựng các công cụ trực quan trong phân tích dữ liệu di truyền.
1.3.5. Phát hiện xâm nhập bất hợp pháp (Intrusion Detection)
Xâm nhập bất hợp pháp là những hành động đe dọa tính toàn vẹn, bảo
mật và tính sẵn sàng của tài nguyên mạng. Trong thế giới của kết nối, bảo
mật đã trở thành vấn đề lớn đối với tồn tại của hệ thống. Với sự phát triển
của Internet và sự sẵn có của các công cụ, thủ thuật trợ giúp cho xâm nhập và
tấn công mạng, yêu cầu kiểm soát truy cập bất hợp pháp là yếu tố rất quan
trọng đảm bảo cho sự ổn định của hệ thống.
1.4. Hàm Entropy
Hàm Entropy dùng để xác định tính thuần nhất của một tập mẫu dữ liệu
bất kỳ. Khái niệm Entropy của một tập S đƣợc định nghĩa trong Lý thuyết
thông tin là số lƣợng mong đợi các bít cần thiết để mã hoá thông tin về lớp
của một thành viên rút ra một cách ngẫu nhiên từ tập hợp dữ liệu S. Trong
trƣờng hợp tối ƣu mã có độ dài ngắn nhất. Theo lý thuyết thông tin, mã có độ
dài tối ƣu là mã gán 

 bít cho thông điệp có xác xuất là p.
Trong trƣờng hợp S là một tập mẫu rèn luyện thì mỗi thành viên của S là
một mẫu. Mỗi mẫu thuộc một lớp hay có một giá trị phân loại.
Trong trƣờng hợp đơn giản, giả sử các mẫu của S chỉ thuộc 2 lớp có giá

trị "Yes” (hoặc "Dƣơng", "+", "Yes", "High") và giá trị "No" (hoặc "Âm", "-",

12

"No", "Low"). Do tính đơn giản và phổ biến nên hai giá trị "Yes" và "No"
đƣợc thống nhất đƣa vào sử dụng.
Ký hiệu 

là tỷ lệ các mẫu có giá trị của thuộc tính quyết định là “Yes”
trong tập S. Khi đó:












 






Trƣờng hợp tổng quát, đối với tập con S có n phân lớp thì Entropy đƣợc

tính theo công thức sau:



















Trong đó 

là tỷ lệ các mẫu thuộc lớp I trên tập hợp S các mẫu kiểm tra.
1.5. Hàm Gain
Gain là đại lƣợng dùng để đo tính hiệu quả của một thuộc tính đƣợc lựa
chọn cho việc phân lớp. Đại lƣợng này đƣợc tính thông qua hai giá trị
Information và Entropy. Cho tập dữ liệu S gồm có n thuộc tính 

(i=1,2…n)
giá trị Information của thuộc tính 


ký hiệu là Information(

) đƣợc xác định
bởi công thức.





















Giá trị Gain của thuộc tính A trong tập S đƣợc ký hiệu là  và
đƣợc tính theo công thức sau:





 



 



 




















Trong đó, S là tập hợp ban đầu với các thuộc tính A. Các giá trị  tƣơng
ứng là các giá trị của thuộc tính A.


bằng tập hợp con của tập S mà có thuộc tính A mang giá trị .




là số phần tử của tập 

;



là số phần tử của tập S.
Chọn thuộc tính cho bƣớc tiếp theo trong thuật toán ID3:

13

Để chọn đƣợc thuộc tính cho bƣớc tiếp theo trong thuật toán ID3, cần
phải tính giá trị Gain của các thuộc tính. Thuộc tính nào có giá trị Gain lớn
nhất đƣợc xem là thuộc tính tốt nhất để lựa chọn cho việc triển khai cây.
1.6. Một số phƣơng pháp khai phá dữ liệu
1.6.1. Cây quyết định và luật
Cây quyết định là phƣơng pháp mô tả tri thức dạng đơn giản nhằm phân
các đối tƣợng dữ liệu thành một số lớp nhất định. Các nút của cây đƣợc gán
nhãn là tên các thuộc tính, các cạnh đƣợc gán các giá trị có thể của các thuộc
tính, các lá miêu tả các lớp khác nhau. Các đối tƣợng đƣợc phân lớp theo các
đƣờng đi trên cây, qua các cạnh tƣơng ứng với các giá trị của các thuộc tính

của đối tƣợng tới lá.
Các luật đƣợc tạo ra nhằm suy diễn cho một số mẫu dự liệu có ý nghĩa về
mặt thống kê. Các luật có dạng “Nếu P thì Q”, trong đó P là một mệnh đề
đúng với một phần dữ liệu trong cơ sở dữ liệu và Q là mệnh đề dự đoán.
Cây quyết định là phƣơng pháp dùng trong các bài toán phân loại dữ liệu
theo một tiêu chuẩn nào đó dựa trên mức độ khác nhau của thuộc tính. Cây
quyết định và luật có ƣu điểm là hình thức miêu tả đơn giản, mô hình suy diễn
khá dễ hiểu đối với ngƣời sử dụng. Tuy nhiên giới hạn của nó là miêu tả cây
và luật chỉ có thể biểu diễn đƣợc một số dạng chức năng và vì vậy giới hạn về
cả độ chính xác của mô hình.
1.6.2. Phương pháp suy diễn và quy nạp
Phƣơng pháp suy diễn: Rút ra thông tin là kết quả logic từ các thông tin
nằm trong cơ sở dữ liệu dựa trên các quan hệ trong dữ liệu. Phƣơng pháp suy
diễn dựa trên các sự kiện chính xác để suy ra các tri thức mới từ các thông tin
cũ. Mẫu chiết xuất đƣợc bằng cách sử dụng phƣơng pháp này thƣờng là các
luật suy diễn.
Phƣơng pháp quy nạp: Các thông tin đƣợc suy ra từ cơ sở dữ liệu bằng
cách nó tự tìm kiếm, tạo mẫu và sinh ra tri thức chứ không bắt đầu với các tri
thức đã biết trƣớc.


14

1.6.3. Luật kết hợp
Mục tiêu của phƣơng pháp này nhằm phát hiện ra các luật kết hợp giữa
các thành phần dữ liệu trong cơ sở dữ liệu. Mẫu đầu ra của thuật giải phát
hiện luật kết hợp giữa các thành phần dữ liệu trong cơ sở dữ liệu. Nhƣợc điểm
cơ bản của phƣơng pháp này là sự gia tăng nhanh chóng khối lƣợng tính toán
và các thông số. Tuy nhiên với sự phát triển nhanh chóng và mạnh mẽ của
phần cứng thì vấn đề này cũng đƣợc khắc phục.

1.6.4. Phân nhóm và phân đoạn
Kỹ thuật phân nhóm và phân đoạn là những kỹ thuật phân chia dữ liệu
sao cho mỗi phần hoặc mỗi nhóm giống nhau theo một tiêu chuẩn nào đó.
Mối quan hệ thành viên của các nhóm có thể dựa trên mức độ giống nhau của
các thành viên và từ đó xây dựng nên các luật ràng buộc giữa các thành viên
trong nhóm. Một số kỹ thuật phân nhóm khác là xây dựng nên các hàm đánh
giá các thuộc tính của các thành phần nhƣ là hàm của các tham số của các
thành phần. Kỹ thuật này đƣợc gọi là kỹ thuật phân hoạch tối ƣu.
Mẫu đầu ra của quá trình khai phá dữ liệu sử dụng kỹ thuật này là các tập
mẫu chứa dữ liệu có chung những tính chất nào đó đƣợc phân tách từ cơ sở
dữ liệu. Khi các mẫu đƣợc thiết lập, chúng có thể sử dụng để tái tạo các tập
dữ liệu dễ hiểu hơn, đồng thời cũng cung cấp các nhóm dữ liệu cho các hoạt
động cũng nhƣ công việc phân tích. Đối với cơ sở dữ liệu lớn, việc lấy ra các
nhóm này là rất quan trọng.
1.6.5. Mạng neural
Mạng neural là một phƣơng pháp khai phá dữ liệu phát triển dựa trên
một nền tảng toán học vững vàng, khả năng huấn luyện trong kỹ thuật này
dựa trên mô hình thần kinh trung ƣơng của con ngƣời.
Kết quả mà mạng neural học đƣợc có khả năng tạo ra các mô hình dự
báo, dự đoán với độ chính xác và độ tin cậy cao. Nó có khả năng phát hiện ra
các xu hƣớng phức tạp mà kỹ thuật thông thƣờng khác khó có thể phát hiện ra
đƣợc. Tuy nhiên phƣơng pháp mạng neural rất phức tạp và quá trình tiến hành

15

nó gặp rất nhiều khó khăn đòi hỏi mất nhiều thời gian, nhiều dữ liệu, nhiều
lần kiểm tra thử nghiệm.
1.6.6. Giải thuật di truyền
Là quá trình mô phỏng tiến hóa trong tự nhiên. Ý tƣởng chính của giải
thuật là dựa vào quy luật di truyền trong biến đổi, chọn lọc tự nhiên và tiến

hóa trong sinh học.
Giải thuật di truyền là một giải thuật tối ƣu hóa, nó đƣợc sử dụng rất rộng
rãi trong việc tối ƣu hóa các kỹ thuật khai phá dữ liệu trong đó có kỹ thuật
mạng neural. Sự liên hệ của nó với các giải thuật khai phá dữ liệu là ở chỗ tối
ƣu hóa là cần thiết để xác định các giá trị tham số nào tạo ra các luật tốt nhất.



















16

CHƢƠNG 2: KHAI PHÁ DỮ LIỆU SỬ DỤNG
CÂY QUYẾT ĐỊNH
2.1. Giới thiệu
2.1.1. Kỹ thuật khai phá sử dụng cây quyết định

Kỹ thuật cây quyết định là một công cụ mạnh và hiệu quả trong việc
phân lớp và dự báo. Các đối tƣợng dữ liệu đƣợc phân thành các lớp. Các giá
trị của đối tƣợng dữ liệu chƣa biết sẽ đƣợc dự đoán, dự báo. Tri thức đƣợc rút
ra trong kỹ thuật này thƣờng đƣợc mô tả dƣới dạng tƣờng minh, đơn giản,
trực quan, dễ hiểu đối với ngƣời sử dụng.
Cây quyết định là một mô tả tri thức dạng đơn giản nhằm phân các đối
tƣợng dữ liệu thành một số lớp nhất định. Các nút của cây đƣợc gán nhãn là
tên các thuộc tính, các cạnh đƣợc gán các giá trị có thể của các thuộc tính, các
lá mô tả các lớp khác nhau. Các đối tƣợng đƣợc phân lớp theo các đƣờng đi
trên cây, qua các cạnh tƣơng ứng với các giá trị của thuộc tính của đối tƣợng
tới lá.
2.1.2. Ưu điểm
So với các phƣơng pháp khai phá dữ liệu khác, cây quyết định có một số
ƣu điểm sau:
- Cây quyết định tƣơng đối dễ hiểu. Mô hình cây quyết định có thể hiểu
đƣợc dễ dàng chỉ cần sau khi đƣợc giải thích ngắn gọn.
- Việc chuẩn bị dữ liệu cho một cây quyết định là cơ bản, đôi khi không
cần thiết phải xử lý dữ liệu trƣớc khi tiến hành khai phá. Trong khi đó các kỹ
thuật khác thƣờng đòi hỏi phải có các thao tác xử lý dữ liệu phức tạp hơn nhƣ
chuẩn hóa dữ liệu, tạo ra các biến phụ hay loại bỏ các giá trị rỗng.
- Cây quyết định có thể xử lý cả dữ liệu có giá trị bằng số, và dữ liệu có
giá trị là tên thể loại dạng phân loại rời rạc. Các kỹ thuật khác thƣờng chuyên
để phân tích các bộ dữ liệu chỉ gồm một loại biến. Chẳng hạn, các luật quan
hệ chỉ có thể dùng cho các biến tên, trong khi mạng neural chỉ có thể dùng
cho các biến có giá trị bằng số.

17

- Cây quyết định là một mô hình hộp trắng. Nếu có thể quan sát một tình
huống cho trƣớc trong một mô hình, thì có thể dễ dàng giải thích điều kiện đó

bằng logic Boolean.
- Có thể thẩm định một mô hình cây quyết định bằng các kiểm tra thống
kê. Điều này làm cho kết quả của mô hình tăng thêm độ tin tƣởng.
- Cây quyết định có thể xử lý một lƣợng rất lớn dữ liệu và đƣa ra các kết
quả phân tích trong thời gian ngắn. Chính vì vậy nó giúp cho các nhà chiến
lƣợc đƣa ra các quyết định kịp thời nhanh chóng dựa vào việc phân tích cây
quyết định.
Quá trình xây dựng cây quyết định là quá trình phát hiện ra các luật phân
chia tập dữ liệu đã cho thành các lớp đã đƣợc định nghĩa trƣớc. Trong thực tế
tập các cây quyết định có thể có đối với bài toán này rất lớn và rất khó có thể
duyệt hết một cách tƣờng tận.
2.1.3. Cấu trúc cây quyết định
Cây quynh là mt c
- Mỗi đỉnh trong (đỉnh có thể khai triển đƣợc) biểu thị cho một phép thử
đối với một thuộc tính.
- Mỗi nhánh biểu thị cho một kết quả của phép thử.
- Các đỉnh lá (các đỉnh không khai triển đƣợc) biểu thị các lớp hoặc phân
bổ lớp.
- Đỉnh trên cùng trong một cây đƣợc gọi là gốc.
Vic sinh cây quyc chia n:
- Giai đoạn 1: Xây dựng cây.
+ Tại thời điểm ban đầu, tất cả các case dữ liệu học đều nằm tại gốc.
+ Các case dữ liệu đƣợc phân chia đệ quy trên cơ sở các thuộc tính đƣợc
chọn.
- Giai đoạn 2: Rút gọn cây: Phát hiện và bỏ đi các nhánh chứa các điểm
dị thƣờng và nhiễu trong dữ liệu.



18


2.1.4. Điều kiện dừng của cây quyết định
- Tất cả các mẫu rơi vào cùng một nút thuộc về cùng một lớp (nút lá).
- Không còn thuộc tính nào có thể dùng để phân chia mẫu.
- Không còn lại mẫu nào tại nút.
2.2. Thuật toán
2.2.1. Thuật toán CLS
Xây dựng cây quyết định lần đầu tiên đƣợc Hoveland và Hunt giới thiệu
trong Concept Learning System - CLS vào cuối những năm 50 của thế kỷ 20.
Sau đó gọi tắt là thuật toán CLS. Thuật toán CLS đƣợc thiết kế theo chiến
lƣợc chia để trị từ trên xuống và gồm những bƣớc sau:
Bƣớc 1: Tạo một nút T, nút này gồm tất cả các mẫu của tập huấn luyện.
Bƣớc 2: Nếu tất cả các mẫu trong T có thuộc tính quyết định mang giá trị
"yes" (hay thuộc cùng một lớp), thì gán nhãn cho nút T là "yes" và dừng lại. T
lúc này là nút lá.
Bƣớc 3: Nếu tất cả các mẫu trong T có thuộc tính quyết định mang giá trị
“no” (hay thuộc cùng một lớp), thì gán nhãn cho nút T là “no” và dừng lại. T
lúc này là nút lá.
Bƣớc 4: Trƣờng hợp ngƣợc lại các mẫu của tập huấn luyện thuộc cả hai
lớp "yes" và "no" thì:
1. Chọn một thuộc tính X có các giá trị 

,

, … 

.
2. Chia tập mẫu trong T thành các tập con 

, 


, …

. Dựa theo các giá
trị của X.
3. Tạo n nút con 

(i = 1, 2,…,n) với nút cha là nút T.
4. Tạo các nhánh nối từ nút T đến các nút 

().
Bƣớc 5: Thực hiện lặp cho các nút con 

 và quay trở lại
bƣớc 2.




19

Ví dụ 1: Cho tập huấn luyện thể hiện trong bảng dữ liệu sau, xây dựng
cây quyết định đi chơi tennis.
Bng 2.1. Tp d liu hun luyn quy
Ngày
Quang cảnh
Nhiệt độ
Độ ẩm
Gió
Chơi Tennis

D1
Nắng
Nóng
Cao
Nhẹ
Không
D2
Nắng
Nóng
Cao
Mạnh
Không
D3
Âm u
Nóng
Cao
Nhẹ
Có
D4
Mƣa
Ấm áp
Cao
Nhẹ
Có
D5
Mƣa
Mát
TB
Nhẹ
Có

D6
Mƣa
Mát
TB
Mạnh
Không
D7
Âm u
Mát
TB
Mạnh
Có
D8
Nắng
Ấm áp
Cao
Nhẹ
Không
D9
Nắng
Mát
TB
Nhẹ
Có
D10
Mƣa
Ấm áp
TB
Nhẹ
Có

D11
Nắng
Ấm áp
TB
Mạnh
Có
D12
Âm u
Ấm áp
Cao
Mạnh
Có
D13
Âm u
Nóng
TB
Nhẹ
Có
D14
Mƣa
Ấm áp
Cao
Mạnh
Không
Bảng dữ liệu trên là một tập hợp các mẫu mô tả về việc quyết định chơi
Tennis. Trong bảng thuộc tính Ngày dùng để định danh (chỉ số). Các thuộc
tính Quang cảnh, Nhiệt độ, Độ ẩm, Gió là các thuộc tính ứng viên đƣợc dùng
để xét, còn thuộc tính Chơi Tennis là thuộc tính quyết định đƣợc dùng để
phân lớp các mẫu dữ liệu. Khi đó cây quyết định xây dựng theo thuật toán
CLS đối với tập dữ liệu trong bảng 2.1 đƣợc xây dựng nhƣ sau:

- Chọn thuộc tính  cây thu đƣợc có
dạng nhƣ sau:







Hình 2.1. Khai trin cây theo thuc tính quang cnh
(Cần mở rộng)
[D1, D2, D3, D4, D5, D6, D7, D8, D9, D10, D11, D12, D13, D14]
[D3, D7, D12, D13]
Có
Mƣa
Âm u
Nắng
Quang cảnh
[D1, D2, D8, D9, D11]
[D4, D5, D6, D10, D14]
(Cần mở rộng)