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

--------------------------

NGUYỄN THỊ CHANH

CÁC PHƯƠNG PHÁP
KHAI PHÁ DỮ LIỆU SỬ DỤNG
CÂY QUYẾT ĐỊNH VÀ ỨNG DỤNG

KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
Chuyên ngành Tin học

H N

– 2014


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

--------------------------

NGUYỄN THỊ CHANH

CÁC PHƯƠNG PHÁP
KHAI PHÁ DỮ LIỆU SỬ DỤNG
CÂY QUYẾT ĐỊNH VÀ ỨNG DỤNG
KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
Chuyên ngành Tin học


Nguyễn Thị Chanh


LỜI CAM ĐOAN
Em xin cam đoan toàn bộ nội dung khóa luận này do em tự sưu tầm, tra
cứu thông tin trên mạng internet, trong một số sách tham khảo để sắp xếp,
hoàn thiện cho phù hợp với nội dung yêu cầu của đề tài.
Đến nay, nội dung khóa luận của em chưa từng được công bố hay xuất
bản dưới bất kỳ hình thức nào. Nếu sai em xin chịu hoàn toàn trách nhiệm.

Hà Nội, tháng 5 năm 2014
Kí tên

Nguyễn Thị Chanh


MỤC LỤC
MỞ ĐẦU ........................................................................................................ 1
CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU .......................... 4
1.1. Khám phá tri thức và khai phá dữ liệu ................................................. 4
1.2. Quá trình phát hiện tri thức .................................................................. 5
1.2.1. Các bước của quá trình phát hiện tri thức ...................................... 5
1.2.1.1. Xác định bài toán ..................................................................... 6
1.2.1.2. Thu thập và tiền xử lý dữ liệu .................................................. 6
1.2.1.3. Khai phá dữ liệu ....................................................................... 7
1.2.1.4. Phân tích và đánh giá tri thức .................................................. 7
1.2.1.5. Sử dụng tri thức phát hiện được............................................... 7
1.2.2. Nhiệm vụ của quá trình khám phá tri thức..................................... 8
1.2.3. Sự cần thiết của khám phá tri thức ............................................... 10

2.1.4. Rút ra luật từ cây quyết định ........................................................ 24
2.2. Các thuật toán khai phá dữ liệu bằng cây quyết định......................... 26
2.2.1. Thuật toán CLS ............................................................................ 26
2.2.2. Thuật toán ID3 ............................................................................. 27
2.2.2.1. Giới thiệu ............................................................................... 27
2.2.2.2. Thuật toán ID3 ....................................................................... 30
2.2.2.3. Tìm kiếm không gian giả thuyết trong ID3 ........................... 35
2.2.2.4. Đánh giá hiệu suất của cây quyết định .................................. 36
2.2.3. Thuật toán C45 ............................................................................. 37
2.2.3.1. Giới thiệu ............................................................................... 37
2.2.3.2. Thuật toán C4.5 xây dựng cây quyết định ............................. 37
2.2.3.3. Độ đo sử dụng để xác định điểm chia tốt nhất ...................... 40
2.2.3.4. Một số vấn đề về thuộc tính ................................................... 40
2.3. Cắt tỉa cây quyết định ......................................................................... 43
2.3.1. Tiền cắt tỉa (Prepruning) .............................................................. 43
2.3.2. Hậu cắt tỉa (Postpruning) ............................................................. 43
Chương 3: XÂY DỰNG ỨNG DỤNG ...................................................... 46


3.1. Bài toán ................................................................................................. 46
3.2. Thu thập và tiền xử lí dữ liệu ................................................................ 48
3.3. Thiết kế chương trình ............................................................................ 50
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ................................................ 53
TÀI LIỆU THAM KHẢO.......................................................................... 55


DANH SÁCH CÁC HÌNH
Hình 1. 1. Quá trình khai phá dữ liệu từ cơ sở dữ liệu..................................... 6
Hình 1. 2. Các nhiệm vụ của quá trình khám phá tri thức ............................... 9
Hình 1. 3. Quá trình khai phá dữ liệu ............................................................. 13

Các công cụ thu thập dữ liệu tự động và các công nghệ cơ sở dữ liệu được
phát triển dẫn đến vấn đề một lượng dữ liệu khổng lồ được lưu trữ trong cơ
sở dữ liệu và trong các kho thông tin của các tổ chức, cá nhân, …. Do đó
việc khám phá tri thức từ dữ liệu là một trong những vấn đề đã và đang nhận
được nhiều sự quan tâm của các nhà nghiên cứu.
Lĩnh vực khám phá tri thức và khai phá dữ liệu đã và đang được
nghiên cứu, ứng dụng trong nhiều lĩnh cực khác nhau trên thế giới. Ở Việt
Nam lĩnh vực này còn tương đối mới mẻ tuy nhiên cũng đang được nghiên
cứu và bắt đầu đưa vào một số ứng dụng thực tế. Vì vậy, vấn đề phát hiện tri
thức và khai phá dữ liệu đang thu hút được sự quan tâm của nhiều người. Với
1


mong muốn tiếp cận với lĩnh vực mới, bổ sung các kiến thức về khoa học kỹ
thuật hiện đại, cũng như tổng kết những kỹ thuật, kiến thức trong suốt quá
trình học tập tại trường, em đã chọn đề tài “Các phương pháp khai phá dữ
liệu sử dụng cây quyết định và ứng dụng” làm khóa luận tốt nghiệp.
2. Mục tiêu nghiên cứu
Mục tiêu của khóa luận là nghiên cứu các vấn đề cơ bản của khám phá
tri thức và khai phá dữ liệu, cây quyết định, các phương pháp khai phá dữ
liệu sử dụng cây quyết định, cài đặt và đánh giá các thuật toán khai phá dữ
liệu bằng cây quyết định.
3. Phạm vi nghiên cứu
Các phương pháp khai phá dữ liệu sử dụng cây quyết định.
4. Ý nghĩa khoa học và thực tiễn
Ý nghĩa khoa học: Các phương pháp khai phá dữ liệu sử dụng cây
quyết định được nghiên cứu giúp chúng ta hiểu hơn về khám phá tri thức,
khai phá dữ liệu, các thuật toán xây dựng cây quyết định.
Ý nghĩa thực tiễn: Chương trình thực nghiệm nếu thành công sẽ góp
phần hỗ trợ quá trình ra một quyết định áp dụng các thuật toán xây dựng cây


3


CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU
1.1.

Khám phá tri thức và khai phá dữ liệu
Trong vài thập kỉ gần đây, khả năng tạo sinh và lưu trữ dữ liệu của con

người đã tăng lên nhanh chóng. Lượng dữ liệu lớn được lưu trữ dẫn đến một
đòi hỏi cấp bách phải có những kĩ thuật mới, những công cụ tự động mới trợ
giúp con người một cách thông minh trong việc chuyển đổi một lượng lớn dữ
liệu thành thông tin hữu ích và tri thức. Vì vậy mà kĩ thuật khám phá tri thức
(Knowledge Discovery) đã ra đời và ngày càng phát triển để đáp ứng nhu
cầu của con người việc xử lý các kho dữ liệu lớn.
Vậy tri thức ở đây là gì? Thông thường chúng ta coi dữ liệu như một
dãy các bit, các số và các ký hiệu, hoặc các “đối tượng” được gửi cho một
chương trình dưới một định dạng nhất định nào đó. Chúng ta sử dụng các bit
để đo lường thông tin và xem nó như là dữ liệu đã được lọc bỏ dư thừa, được
rút gọn tới mức tối thiểu. Bit được dùng làm đơn vị đặc trưng cho dữ liệu.
Chúng ta có thể xem tri thức như là các thông tin tích hợp, bao gồm các sự
kiện và các mối quan hệ giữa chúng. Các mỗi quan hệ này có thể được hiểu,
được phát hiện ra, hoặc có thể được học. Nói cách khác, tri thức có thể coi là
dữ liệu có độ trừu tượng và tổ chức cao.
Hiện nay khám phá tri thức đang phát triển mạnh mẽ trong nhiều
ngành học thuật. Nó được kết hợp cùng với việc quản lý cơ sở dữ liệu, khoa
học thống kê, học máy, nghiên cứu quan hệ giữa các lĩnh vực nhằm rút ra các
tri thức có ích từ tập hợp dữ liệu.
Phát hiện tri thức (Knowledge Discovery) trong các cơ sở dữ liệu là



1. Xử lý dữ liệu bị mất/ thiếu: Các dạng dữ liệu bị thiếu sẽ được thay
thế bởi các giá trị thích hợp.
2. Khử sự trùng lặp: các đối tượng dữ liệu trùng lặp sẽ bị loại bỏ đi. Kỹ
thuật này không được sử dụng cho các tác vụ có quan tâm đến phân bố dữ
liệu.
3. Giảm nhiễu: nhiễu và các đối tượng tách rời khỏi phân bố chung sẽ bị
loại đi khỏi dữ liệu.
4. Chuẩn hoá: miền giá trị của dữ liệu sẽ được chuẩn hoá.
5. Rời rạc hoá: các dạng dữ liệu số sẽ được biến đổi ra các giá trị rời rạc.
6. Rút trích và xây dựng: đặc trưng mới từ các thuộc tính đã có.
7. Giảm chiều: các thuộc tính chứa ít thông tin sẽ được loại bỏ bớt.
1.2.1.3.

Khai phá dữ liệu

Đây là bước quan trọng nhất trong quá trình khám phá tri thức. Kết
quả của bước này là trích ra được các mẫu và/hoặc các mô hình ẩn dưới các
dữ liệu. Một mô hình có thể là một biểu diễn cấu trúc tổng thể một thành
phần của hệ thống hay cả hệ thống trong cơ sở dữ liệu, hay miêu tả cách dữ
liệu được nảy sinh. Còn một mẫu là một cấu trúc cục bộ có liên quan đến vài
biến và vài trường hợp trong cơ sở dữ liệu.
1.2.1.4.

Phân tích v đánh giá tri thức

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.

dữ liệu
mục tiêu

Kho dữ liệu
Lựa chọn kĩ
thuật và
mẫu dữ liệu

Bổ sung
giá trị
thiếu

Loại bỏ
dữ liệu
lỗi

Bình
thường
hóa giá trị

Chuyển
đổi giá
trị

Tạo ra
các thuộc
tính thu
được

Tìm các thuộc


Tinh
chỉnh
tri thức


1.2.3. Sự cần thiết của khám phá tri thức
Có rất nhiều lí do để giải thích sự cần thiết của khám phá tri thức –
khai phá dữ liệu điển hình là:
 Có rất nhiều tổ chức tập hợp quá nhiều dữ liệu, vậy họ phải làm gì
với chúng.
 Con người lưu trữ dữ liệu bởi vì họ cho rằng một số giá trị hữu ích
được mã hóa hoàn toàn trong dữ liệu.
 Trong kinh doanh, cần thu thập các thông tin về thị trường, về các
đối thủ và về khách hàng. Trong sản xuất, cần thu thập các dữ liệu
về thời điểm hiệu quả và tối ưu nhất phục vụ cho mục đích cải tiến
quy trình và giải quyết sự cố.
 Chỉ có một phần nhỏ của dữ liệu (khoảng 5 đến 10%) là luôn được
phân tích.
 Sự ra tăng của dữ liệu cẩn trở các phương pháp truyền thống.
 Giá trị dữ liệu là quá lớn đối với cách thức phân tích cổ điển.
Chúng ta có thể không bao giờ nhìn thấy chúng một cách trọn vẹn
hoặc không thể lưu trữ trong bộ nhớ.
 Dữ liệu cần tìm kiếm không tồn tại dưới dạng tường minh mà dưới
dạng phi cấu trúc, trong các quy luật tiềm ẩn.
 Sự phát triển của mạng máy tính đã ra tăng khả năng truy cập vào
dữ liệu.
 Người sử dụng cuối không phải là nhà thống kê đơn thuần họ cần
biết tri thức là cơ sở dữ liệu mà họ đang lưu trữ.
 Sự cần thiết phải nhanh chóng ra quyết định và phản ứng lại các cơ

11


Quan niệm 2:
Khai phá dữ liệu (Data Mining) chỉ là một bước quan trọng trong quá
trình phát hiên tri thức từ dữ liệu (KDD). Áp dụng các phương pháp “thông
minh” để trích chọn ra các mẫu dữ liệu (data pattern).
Khai phá dữ liệu được định nghĩa như một quá trình phát hiện mẫu
trong dữ liệu, quá trình này có thể là tự động hay bán tự động, song phần
nhiều là bán tự động. Các mẫu được phát hiện thường hữu ích theo định
nghĩa: các mẫu mang lại cho người sử dụng một lợi thế nào đó, thường là lợi
ích về kinh tế.
Khai phá dữ liệu được áp dụng trong các cơ sở dữ liệu quan hệ, giao
dịch, cơ sở dữ liệu không gian, cũng như các kho dữ liệu phi cấu trúc, mà
điển hình là World Wide Web.
Khám phá tri thức là quá 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 chất: Đúng đắn, mới, khả ích và có thể hiểu được.
Khai phá dữ liệu là một bước trong quá trình khám phá tri thức bao gồm các
thuật toán khai phá 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 và các mô hình trong dữ liệu.
Như vậy, mục đích của khám phá tri thức và khai phá dữ liệu là tìm ra
các mẫu hoặc mô hình đang tồn tại trong các cơ sở dữ liệu nhưng vẫn còn bị
khuất bởi số lượng dữ liệu khổng lồ.
1.3.2. Quá trình khai phá dữ liệu
Quá trình khám phá tri thức có thể chia thành 5 bước như sau:

12


Đánh giá,

Thành phần khai phá dữ liệu

Máy chủ cơ sở dữ liệu/kho dữ liệu

Làm sạch, tích hợp và chọn lựa dữ liệu

Cơ sở dữ liệu

Kho dữ liệu

World Wide
Wed

Các kiểu kho chứa
thông tin khác

Hình 1. 4. Kiến trúc điển hình của hệ thống khai phá dữ liệu
1.3.3.1. Cơ sở dữ liệu, kho dữ liệu, World Wide Web và các nguồn
chứa thông tin khác
Đây có thể là một hoặc một nhóm các cơ sở dữ liệu/kho dữ liệu hoặc
các nguồn chứa thông tin (information repositories).
Các kỹ thuật làm sạch dữ liệu và tích hợp dữ liệu có thể được thực
hiện trên các dữ liệu này.

14


1.3.3.2. Máy chủ cơ sở dữ liệu hoặc kho dữ liệu
Chịu trách nhiệm lấy về các dữ liệu phù hợp dựa trên yêu cầu khai phá
của người dùng.

Thực hiện khai phá thăm dò (Exploratory Data Mining) dựa trên các
kết quả khai phá trung gian.
Cho phép người dùng duyệt cơ sở dữ liệu, lược đồ kho dữ liệu và các
cấu trúc dữ liệu, đánh giá các mẫu được khai phá và biểu diễn trực quan mẫu
dưới các dạng thức khác nhau.
1.4.

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 cơ sở dữ liệu 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à:
16


1.4.1. 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 1lớp). Mô hình được sử dụng để dự đoán nhãn lớp khi