9026_04 – Khai phá dữ liệu bằng cây quyết định và ứng dụng

TRƢỜNG ĐẠI HỌC CÔNG NGHIỆP HÀ NỘI
KHOA CÔNG NGHỆ THÔNG TIN
————

BÁO CÁO THỰC TẬP
TỐT NGHIỆP
ĐỀ TÀI: KHAI PHÁ DỮ LIỆU BẰNG CÂY QUYẾT ĐỊNH VÀ
ỨNG DỤNG

Giảng viên hƣớng dẫn: Ths. Trần Hùng Cƣờng
Sinh viên thực hiện: Nguyễn Bá Nguyện
Lớp: Khoa học máy tính 3
Khóa: 4

Hà Nội, Tháng 3 năm 2013

LỜI MỞ ĐẦU
Trong thời đại ngày nay, 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 càng khó khăn hơn.
Khai 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 thông tin hữu ích. Nhiệm vụ cơ bản của lĩnh vực này là khai phá tri thức trong
cơ sở dữ liệu, khai 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.
Em xin bày tỏ sự biết ơn sâu sắc của mình tới Ths Trần Hùng Cƣờng ngƣời đã trực
tiếp hƣớng dẫn, chỉ bảo tận tình, cung cấp tài liệu và phƣơng pháp nghiên cứu khoa
học để em hoàn thành bản luận văn này. Em xin gửi lời cảm ơn tới các thầy cô giáo đã
dạy dỗ trong quá trình em theo học tại Trƣờng.
Trong suốt quá trình nghiên cứu, mặc dù đã hết sức cố gắng nhƣng chắc chắn bài
luận không tránh khỏi những thiếu sót, rất mong quý thầy cô góp ý để luận văn đƣợc
hoàn chỉnh hơn.
Em xin chân thành cảm ơn!

Ký tên
Nguyện
Nguyễn Bá Nguyện

TÓM TẮT NỘI DUNG
Nội dung luận văn em xin trình bày bao gồm ba chƣơng:
Chƣơng một: giới thiệu chung về công nghệ khai phá trí thức, các khái niệm cơ bản, ý
nghĩa và tầm quan trọng của việc khai phá tri thức.
Chƣơng hai: trình bày các phƣơng pháp khai phá dữ liệu bằng cây quyết định, khái
niệm cơ bản về cây quyết định, các thuật toán xây dựng cây quyết định: CLS, ID3,
C4.5, rút gọn các luật quyết định và đánh giá các thuật toán xây dựng cây quyết định.
Chƣơng ba: cài đặt chƣơng trình hỗ trợ ra quyết đinh bằng cây quyết đinh dựa trên
thuật toán C4.5.

MỤC LỤC

LỜI MỞ ĐẦU
………………………………………………………………………………………………..
2
TÓM TẮT NỘI DUNG …………………………………………………………………………………..
3
MỤC LỤC …………………………………………………………………………………………………….
4
DANH SÁCH HÌNH VẼ
…………………………………………………………………………………
6
PHẦN MỞ ĐẦU ……………………………………………………………………………………………
7
CHƢƠNG 1:
GIỚI THIỆU CHUNG VỀ KHAI PHÁ TRI THỨC
…………………….
8
1.1 Phát hiện tri thức và khai phá dữ liệu………………………………………………………………… 8
1.2 Quá trình phát hiện tri thức từ cơ sở dữ liệu ………………………………………………………. 8
1.2.1.
Hình thành và định nghĩa bài toán. ………………………………………………
9
1.2.2.
Thu thập và xử lý dữ liệu. ……………………………………………………………
9
1.2.3.
Khai thác dữ liệu và rút ra tri thức
……………………………………………..
10
1.2.4.
Phân tích và đánh giá tri thức ……………………………………………………
10
1.2.5.
Sử dụng tri thức phát hiện được …………………………………………………
10
1.3. Khai phá dữ liệu …………………………………………………………………………………………… 11
1.3.1.
Các quan niệm về khai phá dữ liệu.
…………………………………………….
11
1.3.2.
Quá trình khái phá dữ liệu.
………………………………………………………..
12
1.3.3.
Kiến trúc của hệ thống khai phá dữ liệu.
……………………………………..
14
1.4. Các kỹ thuật khai phá dữ liệu
…………………………………………………………………………. 15
1.4.1.
Phân lớp dữ liệu
……………………………………………………………………….
15
1.4.2.
Phân cụm dữ liệu ……………………………………………………………………..
16
1.4.3.
Cây quyết định …………………………………………………………………………
16
1.4.4.
Luật kết hợp
……………………………………………………………………………..
16
1.4.5.
Hồi quy ……………………………………………………………………………………
16
1.4.6.
Mạng Nơron …………………………………………………………………………….
16
1.4.7.
Giải thuật di truyền …………………………………………………………………..
17

CHƢƠNG 2:
CÁC PHƢƠNG PHÁP KHAI PHÁ DỮ LIỆU BẰNG CÂY
QUYẾT ĐỊNH ……………………………………………………………………………………………
18
2.1 Cây quyết định …………………………………………………………………………………………….. 18
2.1.1 Giới thiệu ………………………………………………………………………………..
18
2.1.2 Các kiểu cây quyết định
…………………………………………………………….
18
2.1.3 Ưu điểm của cây quyết định ………………………………………………………
19
2.1.4 Phân lớp dữ liệu bằng cây quyết định …………………………………………
19
2.1.5 Xây dựng cây quyết định.
…………………………………………………………..
21
2.1.6 Rút ra luật từ cây quyết định ……………………………………………………..
22
2.2 Các thuật toán xây dựng cây quyết định ………………………………………………………….. 22
2.2.1 Thuật toán CLS ………………………………………………………………………..
22
2.2.2 Thuật toán ID3
…………………………………………………………………………
23
2.2.3 Thuật toán C4.5 ………………………………………………………………………..
25
2.2.4 Cắt tỉa cây quyết định ………………………………………………………………..
31
2.2.5 Đánh giá và kết luận về các thuật toán xây dựng cây quyết định …….
33
CHƢƠNG 3:
CẶT ĐẶT CHƢƠNG TRÌNH KHAI PHÁ DỮ LIỆU SỬ DỤNG
CÂY QUYẾT ĐỊNH …………………………………………………………………………………….
36
3.1 Bài toán thực tế ……………………………………………………………………………………………. 36
3.2 Cài đặt thuật toán…………………………………………………………………………………………. 36
3.3 Hình ảnh demo …………………………………………………………………………………………….. 40
KẾT LUẬN
………………………………………………………………………………………………….
44
TÀI LIỆU THAM KHẢO ……………………………………………………………………………..
45

DANH SÁCH HÌNH VẼ
Hình 1. 1 Quá trình khai phá dữ liệu từ cơ sở dữ liệu …………………………………………
9
Hình 1. 2 Quá trình khai phá dữ liệu
……………………………………………………………….
12
Hình 1. 3 Kiến trúc của một hệ thống khai phá dữ liệu………………………………………
14
Hình 2. 1: Cây quyết định phân lớp mức lương ………………………………………………..
18
Hình 2. 2 Xây dựng mô hình …………………………………………………………………………..
20
Hình 2. 3 Sử dụng mô hình …………………………………………………………………………….
21
Hình 3. 1 Giao diện khi mở chương trình
…………………………………………………………
40
Hình 3. 2 Load dữ liệu và tạo cây quyết định
……………………………………………………
41
Hình 3. 3 Tiến hành cắt tỉa cây
……………………………………………………………………….
42
Hình 3. 4 Hình ảnh của cây quyết định ……………………………………………………………
42
Hình 3. 5 Rút ra luật từ cây quyết định ……………………………………………………………
43
Hình 3. 6 Phân tích dữ liệu mới
………………………………………………………………………
43
7

PHẦN MỞ ĐẦU
Trong nhiều năm qua, cùng với sự phát triển của công nghệ thông tin và ứng dụng
của công nghệ thông tin trong nhiều lĩnh vực của đời sống xã hội, thì lƣợng dữ liệu
đƣợc các cơ quan thu thập và lƣu trữ ngày một nhiều lên. Ngƣời ta lƣu trữ
những dữ liệu này vì cho rằng nó ẩn chứa những giá trị nhất định nào đó. Tuy nhiên
theo thống kê thì chỉ có một lƣợng nhỏ của những dữ liệu này (khoảng từ 5% đến 10%)
là luôn đƣợc phân tích, số còn lại họ không biết sẽ phải làm gì và có thể làm gì với
những dữ liệu này, nhƣng họ vẫn tiếp tục thu thập và lƣu trữ vì hy vọng
những dữ liệu này sẽ cung cấp cho họ những thông tin quý giá một cách
nhanh chóng để đƣa ra những quyết định kịp thời vào một lúc nào đó. Chính vì vậy,
các phƣơng pháp quản trị và khai thác cơ sở dữ liệu truyền thống ngày càng không đáp
ứng đƣợc thực tế đã làm phát triển một khuynh hƣớng kỹ thuật mới đó là Kỹ thuật phát
hiện tri thức và khai phá dữ liệu (KDD – Knowledge Discovery and Data
Mining). Kỹ thuật phát hiện tri thức và khai phá dữ liệu đã và đang đƣợc nghiên cứu,
ứng dụng trong nhiều lĩnh vực khác nhau trên thế giới, tại Việt Nam kỹ thuật 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, hiện nay ở nƣớc ta 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à nhiều công ty phát triển
ứng dụng công nghệ thông tin. Trong phạm vi đề tài nghiên cứu khoa học này của em,
em sẽ trình bày những nội dung sau:
Chƣơng 1: Giới thiệu những kiến thức tổng quan về khám phá tri thức và khai phá
dữ liệu.
Chƣơng 2: Nghiên cứu kỹ thuật khai phá dữ liệu bằng cây quyết định.
Chƣơng 3: Xây dựng ứng dụng demo cho kỹ thuật khai phá dữ liệu bằng cây quyết
định.

8

CHƢƠNG 1: GIỚI THIỆU CHUNG VỀ KHAI PHÁ TRI THỨC
1.1 Phát hiện tri thức và khai phá dữ liệu
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.
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.
1.2 Quá trình phát hiện tri thức từ cơ sở dữ liệu
Quá trình phát hiện tri thức có thể chia thành các bƣớc nhƣ sau:

9

1.2.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, 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 của dữ liệu.
1.2.2. Thu thập và xử lý dữ liệu.
Trong bƣớc này dữ liệu đƣợc thu thập ở dạng thô (nguồn dữ liệu thu thập có thể
là từ các kho dữ liệu hay nguồn thông tin internet). Trong giai đoạn này dữ liệu cũng
đƣợc tiền xử lý để biến đổi và cải thiện chất lƣợng dữ liệu cho phù hợp với phƣơng
pháp khai phá dữ liệu đƣợc chọn lựa trong bƣớc trên.
Bƣớc này thƣờng chiếm nhiều thời gian nhất trong quá trình khám phá tri thức.
Các giải thuật tiền xử lý dữ liệu bao gồm :
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.
Hình thành và
định nghĩa bài toán
Thu thập và tiền
xử lý dữ liệu
KHAI PHÁ DỮ LIỆU
(Triết xuất tri thức)
Phân tích và
đánh giá tri thức
Sử dụng tri thức
phát hiện đƣợc
Hình 1. 1 Quá trình khai phá dữ liệu từ cơ sở dữ liệu
10

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.3. Khai thác dữ liệu và rút ra tri thức
Đây là bƣớc quan trọng nhất trong tiến 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.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.
1.2.5. Sử dụng 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á trithứ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.

11

1.3. Khai phá dữ liệu
1.3.1. Các quan niệm về khai phá dữ liệu.
Khai phá dữ liệu là tập hợp các thuật toán nhằm chiết xuất những thông tin có
ích từ kho dữ liệu khổng lồ.
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 giống nhƣ quá trình tìm ra và mô tả mẫu dữ liệu. Dữ liệu nhƣ
là một tập hợp các vật hay sự kiện, còn đầu ra của quá trình khai phá dữ liệu thƣờng
nhƣ là những dự báo của các vật hay các sự kiện mới.
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ồ. Nhiệm vụ của khai phá dữ liệu.

12

1.3.2. Quá trình khái phá dữ liệu.

Hình 1. 2 Quá trình khai phá dữ liệu
1.3.2.1. 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 nguồn
cung ứng web.
1.3.2.2. Trích lọc dữ liệu (selection)
Ở giai đoạn này dữ liệu đƣợc lựa chọn và phân chia theo một số tiêu chuẩn
nào đó.
1.3.2.3. Làm sạch và tiền xử lý dữ liệu (cleansing prepocessing)
Giai đoạn thứ ba này là giai đoạn hay bị sao lãng, nhƣng thực tế nó 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
trong 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ẽ. Vì vậy dữ liệu thƣờng chứa các giá trị vô nghĩa và không có khả năng kết nối
dữ liệu. Ví dụ Sinh viên có tuổi=200. Giai đoạn thứ ba này nhằm xử lý các dữ
liệu nhƣ trên(dữ liệu vô nghĩa, dữ liệu không có khả năng kết nối). Những dữ liệu
dạng này thƣờng đƣợc xem là thông tin dƣ thừa, không có giá trị. Bởi vậy đây là
13

một quá trình rất quan trọng. Nếu dữ liệu không đƣợ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 nghiêm trọng về sau.
1.3.2.4. Chuyển đổi dữ liệu (tranformation)
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á dữ liệu.
1.3.2.5. Phát hiện và trích mẫu dữ liệu (pattern extraction and discovery)
Đây là bƣớc 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ự.
1.3.2.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.
14

1.3.3. Kiến trúc của hệ thống khai phá dữ liệu.

 Database, data warehouse, World Wide Web, và information repositories
– Thành phần này là các nguồn dữ liệu/thông tin sẽ đƣợc khai phá.
– Trong những tình huống cụ thể, thành phần này là nguồn nhập (input)
của các kỹ thuật tích hợp và làm sạch dữ liệu.
 Database hay data warehouse server
– Thành phần chịu trách nhiệm chuẩn bị dữ liệu thích hợp cho các yêu cầu
khai phá dữ liệu.
 Knowledge base
– Thành phần chứa tri thức miền, đƣợc dùng để hƣớng dẫn quá trình tìm
kiếm, đánh giá các mẫu kết quả đƣợc tìm thấy.
– Tri thức miền có thể là các phân cấp khái niệm, niềm tin của ngƣời sử
dụng, các ràng buộc hay các ngƣỡng giá trị, siêu dữ liệu, …
 Data mining engine
User Interface
Pattern Evaluation
Data mining Enggine
Database or Data
Warehouse Server
Knowledge
Base
Database

Data
Warehouse
Other Infor
Repositories
World Wide
Web
Data cleaning, integration and selection
Hình 1. 3 Kiến trúc của một hệ thống khai phá dữ liệu
15

– Thành phần chứa các khối chức năng thực hiện các tác vụ khai phá dữ
liệu.
 User interface
– Thành phần hỗ trợ sự tƣơng tác giữa ngƣời sử dụng và hệ thống khai phá
dữ liệu.
 Ngƣời sử dụng có thể chỉ định câu truy vấn hay tác vụ khai phá dữ
liệu.
 Ngƣời sử dụng có thể đƣợc cung cấp thông tin hỗ trợ việc tìm
kiếm, thực hiện khai phá dữ liệu sâu hơn thông qua các kết quả
khai phá trung gian.
 Ngƣời sử dụng cũng có thể xem các lƣợc đồ cơ sở dữ liệu/kho dữ
liệu, các cấu trúc dữ liệu; đánh giá các mẫu khai phá đƣợc; trực
quan hóa các mẫu này ở các dạng 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 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à :
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ữ
16

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.
1.4.2. Phân cụm dữ liệu
Mục tiêu của phân cụm dữ liệu là nhóm các đối tƣợng tƣơng tự nhau trong
tập dữ liệu vào các cum, sao cho các đối tƣợng thuộc cùng một lớp là tƣơng đồng.
1.4.3. 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.
1.4.4. Luật kết hợp
Chẳng hạn nhƣ có luật: âm nhac, thể thao => thiếu nhi, nghĩa là những ngƣời
mua sách âm nhạc và thể thao thì cũng mua sách thiếu nhi. Lúc đó ta sẽ quan tâm
đến số lƣợng trƣờng hợp khách hàng thỏa mãn luật này trong cơ sở dữ liệu hay độ
hỗ trợ (Support) cho luật này. Độ hỗ trợ cho luật chính là phần trăm số bản ghi có
cả sách âm nhạc, thể thao và thiếu nhi hay tất cả những ngƣời thích cả ba loại
sách nói trên. Tuy nhiên, giá trị độ hỗ trợ là không đủ, có thể có trƣờng hợp ta có
một nhóm tƣơng đối những ngƣời đọc cả ba loại trên nhƣng lại có một nhóm với
lực lƣợng lớn hơn những ngƣời thích sách thể thao, âm nhạc mà không thích sách
thiếu nhi. Trong trƣờng hợp này tính kết hợp rất yếu mặc dù độ hỗ trợ tƣơng đối
cao, nhƣ vậy chúng ta cần thêm một độ đo thứ hai đó là độ tin cậy (confidence).
Độ tin cậy chính là phần trăm các bản ghi có sách thiếu nhi trong số các bản ghi
có sách âm nhạc và thể thao.
1.4.5. Hồi quy
Phƣơng pháp hồi quy tƣơng tự nhƣ là phân lớp dữ liệu. Nhƣng khác ở chỗ nó
dùng để dự đoán các giá trị liên tục còn phân lớp dữ liệu dùng để dự đoán các giá
trị rời rạc.
1.4.6. Mạng Nơron
17

Đây là một trong những kỹ thuật khai phá dữ liệu đƣợc ứng dụng phổ biến
hiện nay. Kỹ thuật này 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 nơron 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á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 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.
1.4.7. Giải thuật di truyền
Là quá trình mô phỏng theo tiến hoá của 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 hoá
trong sinh học.
Việc xây dựng các thuật toán di truyền mô phỏng sinh học nhằm tìm ra các
giải pháp tốt nhất bao gồm các bƣớc sau:
1. Tạo ra cơ chế mã di truyền dƣới dạng các xâu của một bảng mã ký tự
hạn chế.
2. Thiết lập môi trƣờng nhân tạo trên máy tính có các giải pháp có thể
tham gia “đấu tranh sinh tồn” với nhau để xác định độ đo thành công hay
thất bại, hay còn gọi là “hàm thích nghi”.
3. Phát triển các “phép lai ghép” để các giải pháp kết hợp với nhau. Khi
đó các xâu mã di truyền của giải pháp cha và mẹ bị cắt đi và xếp lại,
trong quá trình sinh sản nhƣ vậy các kiểu đột biến có thể đƣợc áp dụng.
4. Cung cấp một quần thể các giải pháp ban đầu tƣơng đối đa dạng và để
máy tính thực hiện “cuộc chơi tiến hóa” bằng cách loại bỏ các giải pháp
từ mỗi cá thể và thay thế chúng bằng các con cháu hoặc các đột biến của
các giải pháp tốt. Thuật toán sẽ kết thúc khi một họ các giải pháp thành
công đƣợc sinh ra.
18

CHƢƠNG 2: CÁC PHƢƠNG PHÁP KHAI PHÁ DỮ LIỆU BẰNG CÂY
QUYẾT ĐỊNH
2.1 Cây quyết định
2.1.1 Giới thiệu
Trong lĩnh vực học máy, cây quyết định là một kiểu mô hình dự báo
(predictive model), nghĩa là một ánh xạ từ các quan sát về một sự vật/hiện tƣợng
tới các kết luận về giá trị mục tiêu của sự vật/hiện tƣợng. Mỗi nút trong (internal
node) tƣơng ứng với một biến; đƣờng nối giữa nó với nút con của nó thể hiện giá
trị cụ thể cho biến đó. Mỗi nút lá đại diện cho giá trị dự đoán của biến mục tiêu,
cho trƣớc các giá trị dự đoán của các biến đƣợc biểu diễn bởi đƣờng đi từ nút gốc
tới nút lá đó. Kỹ thuật học máy dùng trong cây quyết định đƣợc gọi là học bằng
cây quyết định, hay chỉ gọi với cái tên ngắn gọn là cây quyết định.
Ví dụ: Cây quyết định phân lớp mức lƣơng

2.1.2 Các kiểu cây quyết định
Cây quyết định còn có hai loại:
– Cây hồi quy (Regression tree): ƣớc lƣợng các hàm giá có giá trị là số thực
thay vì đƣợc sử dụng cho các nhiệm vụ phân loại. (Ví dụ: ƣớc tính giá một
ngôi nhà hoặc khoảng thời gian một bệnh nhân nằm viện.)
Age?
≤ 35
salary
> 35
salary
≤ 40
>40
bad
good
≤50
>50
bad
good
Hình 2. 1: Cây quyết định phân lớp mức lương
19

– Cây phân loại (Classification tree): nếu y là một biến phân loại nhƣ: giới tính
(nam hay nữ), kết quả của một trận đấu (thắng hay thua).
2.1.3 Ưu điểm của cây quyết định
So với các phƣơng pháp khai phá dữ liệu khác, cây quyết định là phƣơng
pháp có một số ƣu điểm:
– Cây quyết định dễ hiểu. Ngƣời ta có thể hiểu mô hình cây quyết định sau khi
đƣợc giải thích ngắn.
– Việc chuẩn bị dữ liệu cho một cây quyết định là cơ bản hoặc không cần thiết.
Các kỹ thuật khác thƣờng đòi hỏi chuẩn hóa dữ liệu, cần tạo các biến phụ
(dummy variable) và 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. 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 nơ-ron chỉ có thể dùng cho các biến có giá trị bằng
số.
– Cây quyết định là một mô hình hộp trắng. Mạng nơ-ron là một ví dụ về mô
hình hộp đen, do lời giải thích cho kết quả quá phức tạp để có thể hiểu đƣợc.
Có thể thẩm định một mô hình bằng các kiểm tra thống kê. Điều này làm cho
ta có thể tin tƣởng vào mô hình.
2.1.4 Phân lớp dữ liệu bằng cây quyết định
Phân lớp dựa trên cây quyết định rất thích hợp cho việc khai phá dữ liệu vì cây
quyết định có cấu trúc đơn giản, dễ hiểu và có thể đƣợc xây dựng khá nhanh, từ
cây quyết định có thể dễ dàng rút ra các luật.
Quy nạp cây quyết định là một quá trình học tập của cây quyết định từ các
nhãn lớp của bộ dữ liệu huấn luyện (training tuple). Một cây quyết định là một biểu
đồ dòng dữ liệu nhƣ cấu trúc cây, mỗi nút trong (không phải lá) tƣợng trƣng cho
một thuộc tính kiểm tra, mỗi nhánh đại diện cho kết quả của việc kiểm tra, và mỗi
nút lá (hay nút giới hạn) giữ một lớp nhãn. Nút đầu tiên trên cây là nút gốc.
20

Quá trình phân lớp dữ liệu thông qua 2 bƣớc cơ bản nhƣ sau:
 Bƣớc 1: Xây dựng mô hình từ tập huấn luyện
Mỗi bộ/mẫu dữ liệu đƣợc phân vào một lớp đƣợc xác định trƣớc.

Lớp của một bộ/mẫu dữ liệu đƣợc xác định bởi thuộc tính gán nhãn lớp.

Tập các bộ/mẫu dữ liệu huấn luyện – tập huấn luyện – đƣợc dùng để xây

dựng mô hình.
Mô hình đƣợc biểu diễn bởi các luật phân lớp, các cây quyết định hoặc các

công thức toán học.

Hình 2. 2 Xây dựng mô hình
 Bƣớc 2: Sử dụng mô hình, kiểm tra tính đúng đắn của mô hình và dùng nó để
phân lớp dữ liệu mới.
Phân lớp cho những đối tƣợng mới hoặc chƣa đƣợc phân lớp.

Đánh giá độ chính xác của mô hình:

21

Lớp biết trƣớc của một mẫu/bộ dữ liệu đem kiểm tra đƣợc so sánh với

kết quả thu đƣợc từ mô hình.
Tỉ lệ chính xác bằng phần trăm các mẫu/bộ dữ liệu đƣợc phân lớp

đúng bởi mô hình trong số các lần kiểm tra.

Hình 2. 3 Sử dụng mô hình
Việc tạo cây quyết định bao gồm 2 giai đoạn: Tạo cây và tỉa cây.
Để tạo cây ở thời điểm bắt đầu tất cả những ví dụ huấn luyện là ở gốc sau đó
phân chia ví dụ huấn luyện theo cách đệ qui dựa trên thuộc tính đƣợc chọn.
Việc tỉa cây là xác định và xóa những nhánh mà có phần tử hỗn tạp hoặc
những phần tử không thể phân vào một lớp nào đó
2.1.5 Xây dựng cây quyết định.
Có nhiều thuật toán khác nhau để xây dựng cây quyết định nhƣ: CLS, ID3,
C4.5, SLIQ, SPRINT, EC4.5, C5.0…Nhƣng nói chung quá trình xây dựng cây
quyết định đều đƣợc chia ra làm 3 giai đoạn cơ bản:
a. Xây dựng cây: Thực hiện chia một cách đệ quy tập mẫu dữ liệu huấn luyện
cho đến khi các mẫu ở mỗi nút lá thuộc cùng một lớp
b. Cắt tỉa cây: Là việc làm dùng để tối ƣu hoá cây. Cắt tỉa cây chính là việc trộn
một cây con vào trong một nút lá.
22

c. Đánh giá cây: Dùng để đánh giá độ chính xác của cây kết quả. Tiêu chí đánh
giá là tổng số mẫu đƣợc phân lớp chính xác trên tổng số mẫu đƣa vào.

2.1.6 Rút ra luật từ cây quyết định
Có thể chuyển đổi qua lại giữa mô hình cây quyết định và mô hình dạng
luật (IF …THEN…). Hai mô hình này là tƣơng đƣơng nhau.
Ví dụ từ cây 2.1 ta có thể rút ra đƣợc các luật sau.
IF (Age <= 35) AND (salary<=40) THEN class = bad IF (Age<=35) AND (salary>40) THEN class = good
IF (Age>35) AND (salary <=50 ) THEN class = bad IF (Age > 35) AND(salary>50) THEN class = good

2.2 Các thuật toán xây dựng cây quyết định
2.2.1 Thuật toán CLS
Thuật toán này đƣợc Hovland và Hint giới thiệu trong Concept learning
System (CLS) vào 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. Nó gồm
các bƣớc sau:
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.
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á.
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á.
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ì:
23

+ Chọn một thuộc tính X trong tập thuộc tính của tập mẫu dữ
liệu, X có các giá trị v1,v2, …vn.
+ Chia tập mẫu trong T thành các tập con T1, T2,….,Tn. chia theo
giá trị của X.
+ Tạo n nút con Ti (i=1,2…n) với nút cha là nút T.
+ Tạo các nhánh nối từ nút T đến các nút Ti (i=1,2…n) là các
thuộc tính của X.
5. Thực hiện lặp cho các nút con Ti(i =1,2..n) và quay lại bƣớc 2.

Ta nhận thấy trong bƣớc 4 của thuật toán, thuộc tính đƣợc chọn để triển
khai cây là tuỳ ý. Do vậy cùng với một tập mẫu dữ liệu huấn luyện nếu áp dụng
thuật toán CLS với thứ tự chọn thuộc tính triển khai cây khác nhau, sẽ cho ra các
cây có hình dạng khác nhau. Việc lựa chọn thuộc tính sẽ ảnh hƣởng tới độ rộng,
độ sâu, độ phức tạp của cây. Vì vậy một câu hỏi đặt ra là thứ tự thuộc tính nào
đƣợc chọn để triển khai cây sẽ là tốt nhất. Vấn đề này sẽ đƣợc giải quyết trong
thuật toán ID3 dƣới đây.
2.2.2 Thuật toán ID3
Thuật toán ID3 đƣợc phát biểu bởi Quinlan (trƣờng đại học Syney, Australia)
và đƣợc công bố vào cuối thập niên 70 của thế kỷ 20. Sau đó, thuật toán ID3
đƣợc giới thiệu và trình bày trong mục Induction on decision trees, machine
learning năm 1986. ID3 đƣợc xem nhƣ là một cải tiến của CLS với khả năng lựa
chọn thuộc tính tốt nhất để tiếp tục triển khai cây tại mỗi bƣớc. ID3 xây dựng cây
quyết định từ trên- xuống (top -down).
Nhiệm vụ của giải thuật ID3 là học cây quyết định từ một tập các ví dụ huấn
luyện (training example) hay còn gọi là dữ liệu huấn luyện (training data). Hay
nói khác hơn, giải thuật có:
 Đầu vào: Một tập hợp các ví dụ. Mỗi ví dụ bao gồm các thuộc tính mô
tả một tình huống, hay một đối tƣợng nào đó, và một giá trị phân loại
của nó.
24

 Đầu ra: Cây quyết định có khả năng phân loại đúng đắn các ví dụ trong
tập dữ liệu huấn luyện, và hy vọng là phân loại đúng cho cả các ví dụ
chƣa gặp trong tƣơng lai.
ID3 xây dựng cây quyết định (cây QĐ) theo cách từ trên xuống. Lƣu ý rằng
đối với bất kỳ thuộc tính nào, chúng ta cũng có thể phân vùng tập hợp các ví dụ
rèn luyện thành những tập con tách rời, mà ở đó mọi ví dụ trong một phân vùng
(partition) có một giá trị chung cho thuộc tính đó. ID3 chọn một thuộc tính để
kiểm tra tại nút hiện tại của cây và dùng trắc nghiệm này để phân vùng tập hợp
các ví dụ; thuật toán khi đó xây dựng theo cách đệ quy một cây con cho từng
phân vùng. Việc này tiếp tục cho đến khi mọi thành viên của phân vùng đều nằm
trong cùng một lớp; lớp đó trở thành nút lá của cây.
Các thuộc tính phân loại:
Entropy: dùng để đo tính thuần nhất của một tập dữ liệu. Entropy của một tập S
đƣợc tính theo công thức

+
–
2
2
Entropy(S)= – P log (
)
P log (
)
P
P



(2.1)

Trong trƣờng hợp các mẫu dữ liệu có hai thuộc tính phân lớp “yes” (+), “no”
(-). Ký hiệu p+ là để chỉ tỷ lệ các mẫu có giá trị của thuộc tính quyết định là
“yes”, và kí hiệu p- là tỷ lệ các mẫu có giá trị của thuộc tính quyết định là “no”
trong tập S.
Trƣờng hợp tổng quát, đối với tập con S có n phân lớp thì ta có công thức sau:

n
i
2
i=1
Entropy(S)=
(- P log ( ))
i
P

(2.2)
Trong đó Pi 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.
Các trƣờng hợp đặc biệt:
– Nếu tất cả các mẫu thành viên trong tập S đều thuộc cùng một lớp thì
Entropy(S) =0
– Nếu trong tập S có số mẫu phân bổ đều nhau vào các lớp thì Entropy(S) =1
– Các trƣờng hợp còn lại 0< Entropy(S)<1 25 Information Gain (viết tắt là 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 Ai(i=1,2…n) giá trị Information của thuộc tính Ai ký hiệu là Information(Ai) đƣợc xác định bởi công thức . (2.3) Giá trị Gain của thuộc tính A trong tập S ký hiệu là Gain(S,A) và đƣợc tính theo công thức sau: (2.4) Trong đó :  S là tập hợp ban đầu với thuộc tính A. Các giá trị của v tƣơng ứng là các giá trị của thuộc tính A.  Sv bằng tập hợp con của tập S mà có thuộc tính A mang giá trị v.  |Sv| là số phần tử của tập Sv.  |S| là số phần tử của tập S. Trong quá trình xây dựng cây quyết định theo thuật toán ID3 tại mỗi bƣớc triển khai cây, thuộc tính đƣợc chọn để triển khai là thuộc tính có giá trị Gain lớn nhất. Với việc tính toán giá trị Gain để lựa chọn thuộc tính tối ƣu cho việc triển khai cây, thuật toán ID3 đƣợc xem là một cải tiến của thuật toán CLS. Tuy nhiên thuật toán ID3 không có khả năng xử lý đối với những dữ liệu có chứa thuộc tính số - thuộc tính liên tục (numeric attribute) và khó khăn trong việc xử lý các dữ liệu thiếu (missing data)và dữ liệu nhiễu (noisy data). Vấn đề này sẽ đƣợc giải quyết trong thuật toán C4.5 sau đây. 2.2.3 Thuật toán C4.5 Information(𝐴𝑖) = − 𝑙𝑜𝑔2(𝑃 𝑖) = 𝐸𝑛𝑡𝑟𝑜𝑝𝑦(𝑆) 𝑛 𝑖=1 ) Entropy(S S S Entropy(S) ) Gain(S, V Value(A) V V     A