TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI
KHOA CÔNG NGHỆ THÔNG TIN
SINH VIÊN NGHIÊN CỨU KHOA HỌC
ĐỀ TÀI: KHAI PHÁ DỮ LIỆU BẰNG CÂY QUYẾT ĐỊNH
Giảng viên hướng dẫn: T.S Hồ Cẩm Hà
Sinh viên thực hiện : Nguyễn Thị Hạnh
Lớp : K54C- CNTT
Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học
HÀ NỘI -2008
LỜI CẢM ƠN
Trước tiên em xin được gửi lời cảm ơn chân thành tới các thầy cô giáo trong
khoa Công nghệ thông tin - Trường đại học sư phạm Hà Nội đã tần tình giúp đỡ và
giảng dạy cho chúng em trong những năm học vừa qua.
Đặc biệt, em xin gửi lời cảm ơn chân thành nhất tới cô giáo - T.S Hồ Cẩm Hà
cùng các thầy cô giáo trong tổ bộ môn Hệ thống thông tin đã tận tình hướng dẫn,
giúp đỡ em hoàn thành đề tài nghiên cứu khoa học này.
Trong thời gian vừa qua mặc dù em đã cố gắng rất nhiều để hoàn thành tốt đề
tài nghiên cứu khoa học của mình. Song chắc chắn kết quả nghiên cứu sẽ không
tránh khỏi những thiếu sót, vì vậy em kính mong nhận được sự chỉ bảo và góp ý của
quý thầy cô và các bạn.
Em xin chân thành cám ơn!
Ký tên
H
ạ
nh
Nguyễn Thị Hạnh
Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT
2
Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học
MỤC LỤC
LỜI MỞ ĐẦU ............................................................................................................. 5

Chương 2: Khai phá dữ liệu bằng cây quyết định .................................................. 15
Cây quyết định ..................................................................................................... 15
Định nghĩa cây quyết định ............................................................................... 15
Ưu điểm của cây quyết định ............................................................................ 16
Vấn đề xây dựng cây quyết định ..................................................................... 16
Rút ra các luật từ cây quyết định. .................................................................... 16
Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT
3
Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học
Các thuật toán khai phá dữ liệu bằng cây quyết định ......................................... 17
Thuật toán CLS ................................................................................................ 17
Thuật toán ID3 ................................................................................................. 18
Thuật toán C4.5 ............................................................................................... 20
Thuật toán SLIQ[5] .......................................................................................... 23
Cắt tỉa cây quyết định ...................................................................................... 26
Đánh giá và kết luận về các thuật toán xây dựng cây quyết định ................... 28
Chương 3: Xây dựng chương trình dêmo .............................................................. 30
Mô tả bài toán ...................................................................................................... 30
Thu thập và tiền xử lý dữ liệu .............................................................................. 30
Chương trình ....................................................................................................... 31
Chương 4. KẾT LUẬN ............................................................................................ 32
4.1 Đánh Giá ........................................................................................................ 32
4.1.1 Lý thuyết ................................................................................................. 32
4.1.2 Ứng dụng ................................................................................................ 32
4.2 Hướng Phát Triển .......................................................................................... 32
TÀI LIỆU THAM KHẢO ....................................................................................... 32
Tài liệu tiếng Việt ................................................................................................. 32
Tài liệu tiếng Anh ................................................................................................. 33
Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT
4

Khám phá tri thức và khai phá dữ liệu là gì?
Phát hiện tri thức (Knowledge Discovery ) trong các cơ sở dữ liệu là một qui
trình nhận biết các mẫu hoặc các mô hình trong dữ liệu với các tính năng: hợp thức,
mới, khả ích, và có thể hiểu được [4].
Còn khai thác dữ liệu (data mining) là một ngữ tương đối mới, nó ra đời vào
khoảng những năm cuối của của thập kỷ 1980. Có rất nhiều định nghĩa khác nhau về
khai phá dữ liệu. Giáo sư Tom Mitchell đã đưa ra định nghĩa của khai phá dữ liệu
như sau: “Khai phá dữ liệu là việc sử dụng dữ liệu lịch sử để khám phá những qui tắc
và cải thiện những quyết định trong tương lai.”. Với một cách tiếp cận ứng dụng hơn,
tiến sĩ Fayyad đã phát biểu: ”Khai phá dữ liệu thường được xem là việc khám phá tri
thức trong các cơ sở dữ liệu, là một quá trình trích xuất những thông tin ẩn, trước đây
chưa biết và có khả năng hữu ích, dưới dạng các quy luật, ràng buộc, qui tắc trong cơ
sở dữ liệu.”. Còn các nhà thống kê thì xem " khai phá dữ liệu như là một quá trình
phân tích được thiết kế thăm dò một lượng cực lớn các dữ liệu nhằm phát hiện ra các
mẫu thích hợp và/ hoặc các mối quan hệ mang tính hệ thống giữa các biến và sau đó
sẽ hợp thức hoá các kết quả tìm được bằng cách áp dụng các mẫu đã phát hiện được
cho tập con mới của dữ liệu".
Nói tóm lại: khai phá dữ liệu là một bước trong quy trình phát hiện tri thức
gồm có các thụât toán khai thác dữ liệu chuyên dùng dưới một số quy định về hiệu
quả tính toán chấp nhận được để tìm ra các mẫu hoặc các mô hình trong dữ liệu [4].
Quá trình phát hiện tri thức
Quá trình khám phá tri thức được tiến hành qua 5 bước sau [5]:
Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT
6
Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học
Hình 1.1. Quá trình khám phá tri thức
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, bước này
sẽ quyết định cho việc rút ra những tri thức hữu ích, đồ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 của ứng dụng và bản chất

trường hợp trong cơ sở dữ liệu.
Phân tích và kiểm định kết quả
Bước thứ tư 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ẽ được biến đổi sang
dạng phù hợp với lĩnh vực ứng dụng và dễ hiểu hơn cho người dùng.
Sử dụng các tri thức phát hiện được
Trong bước này, 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ôdun hỗ trợ việc đưa ra quyết định.
Các giai đoạn của quá trình khám phá 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 được sử dụng trong
giai đoạn trước có thể ảnh hưởng đến hiệu quả của các giải thuật được sử
dụng trong các giai đoạn tiếp theo. Các bước của quá trình khám phá 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ả các lần thực hiện.
Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT
8
Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học
Quá trình khai phá dữ liệu
Khai phá dữ liệu là hoạt động trọng tâm của quá trình khám phá tri thức . Thuật ngữ
khai phá dữ liệu còn được một số nhà khoa học gọi là phát hiện tri thức trong cơ sở dữ liệu (
knowledge discovery in database _KDD) ( theo Fayyad Smyth and Piatestky-Shapiro 1989).
Quá trình này gồm có 6 bước [1]:
Hình 1.2. Quá trình khai phá dữ liệu
Quá trình khai phá dữ liệu bắt đầu với kho dữ liệu thô và kết thúc với tri thức
được chiết xuất ra. Nội dung của quá trình như sau:
Gom dữ liệu (gatherin)
Tập hợp dữ liệu là bước đầu tiên trong khai phá dữ liệu. Bước này lấy
dữ liệu từ trong một cơ sở dữ liệu, một kho dữ liệu, thậm chí dữ liệu từ nhữ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.
Chức năng của khai phá dữ liệu
Khai phá dữ liệu có hai chức năng cơ bản đó là: chức năng dự đoán và chức
năng mô tả.
Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT
10
Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học
Các kỹ thuật khai phá dữ liệu
Trong thực tế có nhiều kỹ thuật khai phá dữ liệu khác nhau nhằm thực hiện hai
chức năng mô tả và dự đoán.
- Kỹ thuật khai phá dữ liệu mô tả: có nhiệm vụ mô tả các tính chất hoặc các
đặc tính chung của dữ liệu trong CSDL hiện có. Một số kỹ thuật khai phá
trong nhóm này là: phân cụm dữ liệu (Clustering), tổng hợp
(Summarisation), trực quan hoá (Visualization), phân tích sự phát triển và
độ lệch (Evolution and deviation analyst),….
- Kỹ thuật khai phá dữ liệu dự đoán: có nhiệm vụ đưa ra các dự đoán dựa
vào các suy diễn trên cơ sở dữ liệu hiện thời. Một số kỹ thuật khai phá
trong nhóm này là: phân lớp (Classification), hồi quy (Regression), cây quyết
định (Decision tree), thống kê (statictics), mạng nơron (neural network),
luật kết hợp,….
Một số kỹ thuật phổ biến thường được sử dụng để khai phá dữ liệu
hiện nay là :
Phân lớp dữ liệu:
Mục tiêu của phân lớp dữ liệu đó là dự đoán nhãn lớp cho các mẫu dữ
liệu. Quá trình gồm hai bước: xây dựng mô hình, sử dụng mô hình để phân lớp
dữ liệu( mỗi mẫu 1 lớp). Mô hình được sử dụng để dự đoán nhãn lớp khi mà độ
chính xác của mô hình chấp nhận được.
Phân cụm dữ liệu:

hiện ra được. Tuy nhiên phương pháp mạng nơ ron rất phức tạp và quá trình
tiến hành 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.
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
Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT
12
Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học
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ác dạng dữ liệu có thể khai phá được
- CSDL quan hệ
- CSDL đa chiều
- CSDL giao dịch
- CSDL quan hệ - đối tượng
- CSDL không gian và thời gian
- CSDL đa phương tiện.
Các lĩnh vực liên quan đến khai phá dữ liệu và ứng dụng của khai phá dữ liệu
Các lĩnh vực liên quan đến phát hiện tri thức và khai phá dữ liệu
Phát hiện tri thức và khai phá dữ liệu được ứng dụng trong nhiều ngành và
lĩnh vực khác nhau như: tài chính ngân hàng, thương mại, y tế, giáo dục, thống
kê, máy học, trí tuệ nhân tạo, csdl, thuật toán toán học, tính toán song song với
tốc độ cao, thu thập cơ sở tri thức cho hệ chuyên gia,…
Ứng dụng của khai phá dữ liệu
Khai phá dữ liệu được vận dụng để giải quyết các vấn đề thuộc nhiều lĩnh
vực khác nhau. Chẳng hạn như giải quyết các bài toán phức tạp trong các ngành
đòi hỏi kỹ thuật cao, như tìm kiếm mỏ dầu, từ ảnh viễn thám, cảnh báo hỏng
hóc trong các hệ thống sản xuất; Được ứng dụng cho việc quy hoạch và phát