10426_Nghiên cứu một số phương pháp phân lớp dữ liệu và ứng dụng trong phân lớp nấm

ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

INTHAVONG SOUKSAKHONE

NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP PHÂN LỚP
DỮ LIỆU VÀ ỨNG DỤNG TRONG PHÂN LỚP NẤM
(MUSHROOM) VỚI CÔNG CỤ WEKA

LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH

Thái Nguyên – 2020

ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

INTHAVONG SOUKSAKHONE

NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP PHÂN LỚP DỮ
LIỆU VÀ ỨNG DỤNG TRONG PHÂN LỚP NẤM
(MUSHROOM) VỚI CÔNG CỤ WEKA

LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH
Chuyên ngành: KHOA HỌC MÁY TÍNH
Mã số: 84 8 01 01

Người hướng dẫn khoa học: TS. Nguyễn Văn Núi

Thái Nguyên – 2020

I

LỜI CẢM ƠN

Trước tiên, tôi xin được gửi lời cảm ơn và lòng biết ơn sâu sắc nhất tới Thầy
giáo, TS. Nguyễn Văn Núi đã tận tình chỉ bảo, hướng dẫn, động viên và giúp đỡ tôi
trong suốt quá trình tôi thực hiện luận văn tốt nghiệp.

Tôi xin gửi lời cảm ơn tới các thầy cô Trường Đại Học Công nghệ Thông
Tin và Truyền Thông – Đại học Thái Nguyên, những người đã tận tình giúp đỡ,
hướng dẫn trong quá trình tôi học tập tại trường.

Cuối cùng, tôi muốn gửi lời cảm ơn tới gia đình và bạn bè, những người thân
yêu luôn bên cạnh, quan tâm, động viên tôi trong suốt quá trình học tập và thực hiện
luận văn tốt nghiệp này.

Tôi xin chân thành cảm ơn!
Thái Nguyên, tháng 11 năm 2020
Học viên

Inthavong Souksakhone

II

LỜI CAM ĐOAN

Tôi xin cam đoan kết quả đạt được trong Luận văn là sản phẩm của riêng cá
nhân tôi, không sao chép lại của người khác. Những điều được trình bày trong nội
dung Luận văn, hoặc là của cá nhân hoặc là được tổng hợp từ nhiều nguồn tài liệu.
Tất cả các tài liệu tham khảo đều có xuất xứ rõ ràng và được trích dẫn đúng quy
cách. Tôi xin hoàn toàn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy
định cho lời cam đoan của mình.

Thái Nguyên, tháng 11 năm 2020
Tác giả luận văn

Inthavong Souksakhone

III

MỤC LỤC

LỜI CẢM ƠN …………………………………………………………………………………………………………. I
LỜI CAM ĐOAN ……………………………………………………………………………………………………II
MỤC LỤC
…………………………………………………………………………………………………………….. III
DANH SÁNH BẢNG ……………………………………………………………………………………………. VI
DANH SÁNH HÌNH VẼ
………………………………………………………………………………………
VII
DANH SÁCH TỪ VIẾT TẮT ……………………………………………………………………………… IX
CHƯƠNG 1 TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ PHÁT HIỆN TRI THỨC …..
3
1.1 Giới thiệu tổng quan …………………………………………………………………………………………….
3
1.1.1 Khái niệm khai phá dữ liệu
……………………………………………………………………… 3
1.1.2 Nhiệm vụ của khai phá dữ liệu ………………………………………………………………… 4
1.1.3 Một số ứng dụng khai phá dữ liệu ……………………………………………………………. 4
1.1.4 Bước phát triển của việc tổ chức và khai thác các CSDL ……………………………. 5
1.1.5 Quá trình phát hiện tri thức
……………………………………………………………………… 6
1.1.6 Các bước của quá trình KPDL
…………………………………………………………………. 8
1.2. Một số kỹ thuật khai phá dữ liệu cơ bản
…………………………………………………………….
10
1.2.1 Khai phá dữ liệu dự đoán
………………………………………………………………………. 10
1.2.1.1 Phân lớp (Classification) …………………………………………………………………. 10
1.2.1.2 Hồi quy (Regression)………………………………………………………………………. 11
1.2.2 Khai phá dữ liệu mô tả
………………………………………………………………………….. 11
1.2.2.1 Phân cụm ………………………………………………………………………………………. 11
1.2.2.2 Khai phá luật kết hợp ……………………………………………………………………… 12
1.3 Một số so sánh giữa khai phá dữ liệu và các phương pháp cơ bản khác ………………
12
1.3.1 So sánh với phương pháp hệ chuyên gia (Expert Systems) ……………………….. 13
1.3.2 So sánh với phương pháp thống kê (Statistics) ………………………………………… 14
1.3.3 So sánh với phương pháp học máy (Machine Learning)
……………………………. 14
1.3.4 So sánh với phương pháp học sâu (Deep Learning)
………………………………….. 15
IV

1.4 Tổng kết chương ………………………………………………………………………………………………..
18
CHƯƠNG 2 MỘT SỐ PHƯƠNG PHÁP VÀ KỸ THUẬT PHÂN LỚP DỮ
LIỆU …………………………………………………………………………………………………………….. 19
2.1 Tổng quan về phân lớp dữ liệu
……………………………………………………………………………
19
2.2 Phân lớp dữ liệu bằng cây quyết định …………………………………………………………………
22
2.2.1 Độ lợi thông tin
……………………………………………………………………………………. 26
2.2.2 Tỉ số độ lợi ………………………………………………………………………………………….. 29
2.2.3 Chỉ số Gini ………………………………………………………………………………………….. 30
2.2.4 Tỉa cây quyết định ……………………………………………………………………………….. 32
2.3 Phân lớp dữ liệu Bayesian ………………………………………………………………………………….
33
2.3.1 Định lý Bayes ……………………………………………………………………………………… 33
2.3.2 Phân lớp Naïve Bayes
…………………………………………………………………………… 34
2.4. Phân lớp dữ liệu sử dụng máy hỗ trợ vector (SVM) …………………………………………..
36
2.4.1 Phân lớp đa lớp với SVM ……………………………………………………………………… 40
2.5. Phân lớp dữ liệu với Random Forest (rừng ngẫu nhiên) …………………………………….
40
2.6 Một số phương pháp phân lớp dữ liệu khác ………………………………………………………..
44
2.6.1 Thuật toán phân lớp k-NN …………………………………………………………………….. 44
2.7 Đánh giá mô hình phân lớp dữ liệu …………………………………………………………………….
44
2.8 Tổng kết chương ………………………………………………………………………………………………..
46
CHƯƠNG 3 ỨNG DỤNG PHÂN LỚP DỮ LIỆU MUSHROOM VỚI CÔNG
CỤ WEKA VÀ MỘT SỐ THUẬT TOÁN CƠ BẢN
…………………………………………….
47
3.1 Giới thiệu bài toán phân lớp dữ liệu Mushroom
………………………………………………….
47
3.1.1 Giới thiệu về bài toán phân lớp dữ liệu Mushroom
…………………………………… 47
3.1.2. Thu thập, tiền xử lý và mã hóa dữ liệu
………………………………………………… 47
3.1.3. Mô tả sơ lược về dữ liệu
……………………………………………………………………. 51
3.2 Giới thiệu về công cụ Weka, cấu hình và ứng dụng phân lớp Mushroom …………..
52
3.2.1 Môi trường Explorer …………………………………………………………………………….. 53
V

3.2.2 Khuôn dạng của tập dữ liệu …………………………………………………………………… 54
3.2.3 Tiền xử lý dữ liệu
…………………………………………………………………………………. 54
3.2.4 Phân tích chức năng phân lớp (Classify) …………………………………………………. 54
3.2.5 Mô tả chức năng phân lớp (Classify)
………………………………………………………. 58
3.3 Áp dụng các phương pháp phân lớp trên tập dữ liệu Mushroom …………………………
60
3.3.1 Thực hiện phân lớp bằng thuật toán Naive Bayes …………………………………….. 61
3.3.2 Thực hiện phân lớp bằng thuật toán k-Nearest neighbor …………………………… 63
3.3.3 Thực hiện phân lớp bằng thuật toán Support Vector Machines ………………….. 66
3.4 Đánh giá mô hình phân lớp dữ liệu Mushroom …………………………………………………..
70
3.4.1 Đánh giá mô hình bằng phương pháp Hold-out ……………………………………….. 70
3.4.2 Đánh giá mô hình bằng phương pháp k-fold Cross validation
……………………. 71
3.5 Kết luận thực nghiệm phần lớp dữ liệu Mushroom
……………………………………………..
71
3.6 Tổng kết chương ………………………………………………………………………………………………..
72
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
……………………………………………………………..
73
TÀI LIỆU THAM KHẢO ……………………………………………………………………………………..
74

VI

DANH SÁNH BẢNG

Bảng 2.1: Bảng dữ liệu khách hàng …………………………………………………………………… 25
Bảng 2.3: Bảng biểu diễn ma trận nhầm lẫn ……………………………………………………….. 45

Bảng 3.1: Bảng tổng hợp dữ liệu thu thập ………………………………………………………….. 47
Bảng 3.2: Các tính năng dành cho các dữ liệu nấm ……………………………………………… 48
Bảng 3.3: Mô tả ý nghĩa các giá trị dữ liệu nấm ………………………………………………….. 50
Bảng 3.4: Hiệu năng của mô hình dự đoán, đánh giá bởi kiểm tra 70% …………………. 70
Bảng 3.5: Hiệu năng của mô hình dự đoán, đánh giá bởi kiểm tra chéo mặt
(fold=10 cross-validation)
………………………………………………………………………………… 71

VII

DANH SÁNH HÌNH VẼ

Hinh 1.1: Quá trình phát hiện tri thức ………………………………………………………………….. 6
Hinh 1.2: Quá trình khai phá dữ liêu (KPDL) ………………………………………………………. 9
Hinh 1.3: Phân cụm tập dữ liệu cho vay thành 3 cụm ………………………………………….. 12
Hinh 1.4: Một số lĩnh vực ứng dụng của trí tuệ nhân tạo ……………………………………… 13
Hinh 1.5: Học sau nhận dạng khuôn mặt hoặc biểu hiện cảm xúc trên khuân mặt …… 16

Hình 2.1: Quá trình phân lớp dữ liệu – (a) Bước xây dựng mô hình phân lớp …………. 21
Hình 2.2 : Quá trình phân lớp dữ liệu – (b1) Ước lượng độ chính xác của mô hình …. 22
Hình 2.3: Quá trình phân lớp dữ liệu – (b2) Phân lớp dữ liệu mới …………………………. 22
Hình 2.4:Phân lớp cho bài toán cho vay vốn của ngân hàng …………………………………. 23
Hình 2.5:Thuật toán xây dựng cây quyết định
…………………………………………………….. 24
Hình 2.6: Minh họa cây quyết định
……………………………………………………………………. 26
Hình 2.7: Thuộc tính tuổi có thông tin thu được cao nhất …………………………………….. 29
Hình 2.8 :Các điểm trong không gian D chiều ……………………………………………………. 36
Hình 2.9: Siêu phẳng phân lớp các điểm trong không gian …………………………………… 37
Hình 2.10: Đồ thị biểu diễn các điểm trong mặt phẳng R+ …………………………………… 37
Hình 2.11: Các điểm lựa chọn cho siêu phẳng ……………………………………………………. 38
Hình 2.12: Kiến trúc mô hình SVM
…………………………………………………………………… 38
Hình 2.13: Đồ thị biểu diễn siêu phẳng tìm được ………………………………………………… 39
Hình 2.14: Mô hình rừng ngẫu nhiên
…………………………………………………………………. 42
Hình 2.15: Mô hình chia tập dữ liệu Hold-out
…………………………………………………….. 45
Hình 2.16: Mô hình chia tập dữ liệu Cross validation ………………………………………….. 46

Hình 3.1: Sơ đồ Phương pháp phân lớp nấm (Mushroom).
…………………………………… 49
Hình 3.2 : Load Mushroom data ……………………………………………………………………….. 51
Hình 3.3: Giao diên ban đầu Phần mềm WEKA …………………………………………………. 52
Hình 3.4: Giao diên của WEKA Explorer ………………………………………………………….. 53
Hình 3.5: Biểu diễn tập dữ liệu weather trong tập tin văn bản(text)
……………………….. 54
Hình 3.6: Biểu diễn đọc dữ liệu vào chương trình Weka ……………………………………… 55
VIII

Hình 3.7: Biểu diễn chọn tab Classify để phân lớp………………………………………………. 55
Hình 3.8: Biểu diễn chọn thuật toán phân lớp và xác định tham số ……………………….. 56
Hình 3.9: Biểu diễn chọn kiểu test …………………………………………………………………….. 56
Hình 3.10: Chạy thuật toán phân lớp …………………………………………………………………. 57
Hình 3.11: Bảng lưu thông tin
…………………………………………………………………………… 57
Hình 3.12: Bảng kết quả sau chạy thuật toán phân lớp
…………………………………………. 58
Hình 3.13: Giải thích Running Information
………………………………………………………… 58
Hình 3.14: Giải thích Classifier model (full training set) ……………………………………… 59
Hình 3.15: Giải thích xem xét tổng kết số liệu thống kế tập dữ liệu ………………………. 59
Hình 3.16: Xem độ chính xác chi tiết cho từng phân lớp ……………………………………… 59
Hình 3.17: Confusion matrix của bộ phân lớp dữ liêu Mushroom …………………………. 60
Hình 3.18: Sơ đồ tổng thể Mô hình phân lớp dự đoán nấm (mushroom)
………………… 60
Hình 3.19: Cấu hình Weka cho thuật toán Naive Bayes
……………………………………….. 61
Hình 3.20: Kết quả phân lớp Weka cho thuật toán Naive Bayes với số 70% Split
…… 62
Hình 3.21: Kết quả phân lớp Weka cho thuật toán Naive Bayes kiểm tra chéo 10
mặt
………………………………………………………………………………………………………………… 63
Hình 3.22: Cấu hình Weka cho thuật toán k-NN
…………………………………………………. 64
Hình 3.23: Cấu hình Weka cho thuật toán tìm kiếm trong thuật toán k-NN ……………. 64
Hình 3.24: Kết quả phân lớp Weka cho thuật toán k-NN với số 70% Split …………….. 65
Hình 3.25: Kết quả phân lớp Weka cho thuật toán k-NN kiểm tra chéo 10 mặt ………. 65
Hình 3.26: Cấu hình Weka cho thuật toán SVM …………………………………………………. 66
Hình 3.27: Kết quả phân lớp Weka cho thuật toán SVM với số 70% Split
……………… 67
Hình 3.28: Kết quả phân lớp Weka cho thuật toán SVM kiểm tra chéo 10 mặt ………. 67
Hình 3.29: Cấu hình Weka cho thuật toán J48 ……………………………………………………. 68
Hình 3.30: Kết quả phân lớp Weka cho thuật toán J48 decision với số 70% Split …… 68
Hình 3.31: Kết quả phân lớp Weka cho thuật toán J48 kiểm tra chéo 10 mặt………….. 69
Hình 3.32: Mô hình cây quyết định hiển thị bởi Hold-out J48 ………………………………. 69
Hình 3.33: cây quyết định Visualization
…………………………………………………………….. 70

IX

DANH SÁCH TỪ VIẾT TẮT

TT
Từ viết tắt
Dạng đầy đủ
Chú thích
1
DM
Data Mining
Khai thác dữ liệu
2
SVM
Supprot Vector Machin
Máy hỗ trợ vector
3
KDD
Knowlegde Discovery in
Databases
Phát hiện tri thức trong
CSDL
4
RF
Random forest
Rừng ngẫu nhiên
5
E
Edible
Ăn được hoặc không có độc
6
P
Poisonous
Có độc hoặc Không ăn được
7
PCA
Principal Component Analysis Thuật toán phân tích thành
phần chính
8
K-NN
K-Nearest neighbor
K láng giềng gần nhất
9
ACC
Accuracy
Độ chính xác
10
ARFF
Attribute Relation File Format

1

MỞ ĐẦU
Ly do chọn đề tài
Sự bùng nổ và phát triển của ngành công nghệ thông tin trong cách mạng 4.0
và việc ứng dụng công nghệ thông tin ở hầu hết các lĩnh vực trong nhiều năm qua
cũng đồng nghĩa với lượng dữ liệu đã được thu thập và lưu trữ ngày càng lớn. Các
hệ quản trị cơ sở dữ liệu truyền thống cũng chỉ khai thác được một lượng thông tin
nhỏ không còn đáp ứng đầy đủ những yêu cầu, những thách thức mới. Do vậy một
khuynh hướng mới được ra đời đó là kỹ thuật phát hiện tri thức trong cơ sở dữ liệu.
Xin giới thiệu một cách tổng quan về phát hiện tri thức và khai phá dữ liệu cùng
một số kỹ thuật cơ bản để trong khai phá dữ liệu để phát hiện tri thức và một số ứng
dụng trong thực tế nhằm hỗ trợ cho tiến trình ra quyết định.
Kỹ thuật phát hiện tri thức và khai phá dữ liệu đã đang được nghiên cứu, ứng
dụng trong nhiều lĩnh vực khác nhau ở các nước trên thế giới, kỹ thuật này tương
đối còn mới mẻ tuy nhiên cũng đang được nghiên cứu và dần đưa vào ứng dụng.
Bước quan trọng nhất của quá trình này là Khai phá dữ liệu (Data Mining – DM),
giúp người sử dụng thu được những tri thức hữu ích từ những CSDL hoặc các
nguồn dữ liệu khổng lồ khác. Rất nhiều doanh nghiệp và tổ chức trên thế giới đã
ứng dụng kĩ thuật khai phá dữ liệu vào hoạt động sản xuất kinh doanh của mình và
đã thu được những lợi ích to lớn.
Khai phá dữ liệu và khám phá tri thức (Data mining and Knowledge
discovery) là một lĩnh vực quan trọng của ngành Công nghệ thông tin với mục tiêu
là tìm kiếm các tri thức có ích, cần thiết, tiềm ẩn và chưa được biết trước trong cơ
sở dữ liệu lớn. Đây là lĩnh vực đã và đang thu hút đông đảo các nhà khoa học trên
thế giới và trong nước tham gia nghiên cứu. Phân lớp (classification) là một trong
những bài toán cơ bản trong khai phá dữ liệu với mục tiêu là phân loại các đối
tượng vào các lớp cho trước. Nhưng để làm được điều đó, sự phát triển của các mô
hình toán học và các giải thuật hiệu quả là chìa khoá quan trọng. Vì vậy, trong luận
văn này, tác giả sẽ đề cập tới kỹ thuật thường dùng trong khai phá dữ liệu, đó là
Phân lớp (Classification).
2

Sau phần mở đầu, kết luận và tài liệu tham khảo nội dung chính của luận văn
được trình bày chi tiết chia thành 3 chương như sau:
Chương 1. Tổng quan về khai phá dữ liệu và phát hiện tri thức
Phần này giới thiệu một cánh tổng quát về quá trình phát hiện tri thức nói
chung và khai phá dữ liệu nói riêng. Đặc biệt nhấn mạnh về một kỹ thuật chính
được nghiên cứu trong luận văn đó là Kỹ thuật phân lớp.
Chương 2. Một số phương pháp và kỹ thuật phân lớp dữ liệu
Trong phần này, sẽ giới thiệu tập trung vào kỹ thuật phân lớp được một số
cách chi tiết. Có nhiều kiểu phân lớp như phân lớp bằng cây quyết định (Decision
Tree), phân lớp dữ liệu Bayesian, phân lớp dữ liệu với Random Forest (rừng ngẫu
nhiên), Phân lớp dữ liệu sử dụng máy hỗ trợ vector (SVM) và một số phương pháp
phân lớp dữ liệu khác. Ngoài ra còn đánh giá mô hình của phương pháp phân lớp dữ
liệu.
Chương 3. Ứng dụng phân lớp dữ liệu Mushroom với công cụ Weka và một số
thuật toán cơ bản.
Phần này giới thiệu bài toán phân lớp dữ liệu Mushroom, giới thiệu về phân
lớp dữ liệu sử dụng công cụ Weka, áp dụng các phương pháp phân lớp trên tập dữ
liệu Mushroom. Sau đó phân chia tập dữ liệu để đánh giá mô hình theo hai phương
pháp Hold-out và K-fold cross validation để kết luận phân lớp dữ liệu Mushroom
cho kết quả phân lớp tốt nhất.

3

CHƯƠNG 1
TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ PHÁT HIỆN TRI THỨC

1.1 Giới thiệu tổng quan
Trong thời đại ngày nay, với sự phát triển vượt bật của công nghệ thông tin,
các hệ thống thông tin có thể lưu trữ một khối lượng lớn dữ liệu về hoạt động hàng
ngày của chúng. Không có một lĩnh vực nào lại không cần đến sự hỗ trợ của công
nghệ thông tin và sự thành công của các lĩnh vực đó phụ thuộc rất nhiều vào việc
nắm bắt thông tin một cách nhạy bén, nhanh chóng và hữu ích. Với nhu cầu như thế
nếu chỉ sử dụng thao tác thủ công truyền thống thì độ chính xác không cao và mất
rất nhiều thời gian. Từ khối dữ liệu này, các kỹ thuật trong Khai Phá Dữ Liệu
(KPDL) và Máy Học (MH) có thể dùng để trích xuất những thông tin hữu ích mà
chúng ta chưa biết. Các tri thức vừa học được có thể vận dụng để cải thiện hiệu quả
hoạt động của hệ thống thông tin ban đầu. Do vậy việc khai phá tri thức từ dữ liệu
trong các tập tài liệu lớn chứa đựng thông tin phục vụ nhu cầu nắm bắt thông tin có
vai trò hết sức to lớn. Từ đó, các kĩ thuật khai phá dữ liệu đã trở thành một lĩnh vực
thời sự của nền CNTT thế giới hiện nay.
Khai phá dữ liệu (Data Mining) là một lĩnh vực mới xuất hiện, nhằm tự động
khai thác những thông tin, những tri thức có tính tiềm ẩn, hữu ích từ những CSDL
lớn cho các đơn vị, tổ chức, doanh nghiệp,… từ đó làm thúc đẩy khả năng sản xuất,
kinh doanh, cạnh tranh cho các đơn vị, tổ chức này. Các kết quả khoa học cùng
những ứng dụng thành công trong khám phá tri thức, cho thấy, khai phá dữ liệu là
một lĩnh vực phát triển bền vững, mang lại nhiều lợi ích và có nhiều triển vọng,
đồng thời có ưu thế hơn hẳn so với các công cụ phân tích dữ liệu truyền thống. Hiện
nay, khai phá dữ liệu đã ứng dụng ngày càng rộng rãi trong các lĩnh vực như:
Thương mại, tài chính, điều trị y học, viễn thông, tin – sinh…
1.1.1 Khái niệm khai phá dữ liệu

Khai phá dữ liệu (data mining) là quá trình trích xuất, khai thác các mẫu
trong các bộ dữ liệu lớn liên quan đến các phương pháp tại giao điểm của máy học,
4

thống kê và các hệ thống cơ sở dữ liệu và sử dụng những dữ liệu có giá trị tiềm ẩn
từ bên trong lượng lớn dữ liệu được lưu trữ trong các cơ sở dữ liệu (CSDL), kho dữ
liệu, trung tâm dữ liệu lớn hơn là Big Data dựa trên kĩ thuật như mạng nơ ron, lí
thuyết tập thô, tập mờ, biểu diễn tri thức. Khai phá dữ liệu là một công đoạn trong
hoạt động “làm sạch” dữ liệu giúp cho dữ liệu được truyền dẫn một cách nhanh
nhất. Mục tiêu tổng thể của quá trình khai thác dữ liệu là trích xuất thông tin từ một
bộ dữ liệu và chuyển nó thành một cấu trúc dễ hiểu để sử dụng tiếp. Ngoài bước
phân tích thô, nó còn liên quan tới cơ sở dữ liệu và các khía cạnh quản lý dữ liệu,
xử lý dữ liệu trước, suy xét mô hình và suy luận thống kê, các thước đo thú vị, các
cân nhắc phức tạp, xuất kết quả về các cấu trúc được phát hiện, hiện hình hóa và
cập nhật trực tuyến. Khai thác dữ liệu là bước phân tích của quá trình “khám phá
kiến thức trong cơ sở dữ liệu” hoặc KDD.
Định nghĩa: Khai phá dữ liệu là một quá trình tìm kiếm, phát hiện các tri
thức mới, tiềm ẩn, hữu dụng trong CSDL lớn.
Khai phá tri thức trong CSDL (Knowledge Discovery in Databases – KDD)
là mục tiêu chính của khai phá dữ liệu, do vậy hai khái niệm khai phá dữ liệu và
KDD được các nhà khoa học trên hai lĩnh vực xem là tương đương với nhau. Thế
nhưng, nếu phân chia một cách chi tiết thì khai phá dữ liệu là một bước chính trong
quá trình KDD.
1.1.2 Nhiệm vụ của khai phá dữ liệu
Những nhiệm vụ cơ bản nhất của KPDL là:
• Phân cụm, phân loại, phân nhóm, phân lớp.
• Khai phá luật kết hợp.
• Lập mô hình dự báo.
• Phân tích đối tượng ngoài cuộc.
• Phân tích sự tiến hóa.
1.1.3 Một số ứng dụng khai phá dữ liệu
Mặc dù còn rất nhiều vấn đề mà KPDL cần phải tiếp tục nghiên cứu để giải
quyết nhưng tiềm năng của nó đã được khẳng định bằng sự ra đời của rất nhiều ứng
5

dụng. các ứng dụng của KPDL trong khoa học cũng được phát triển. các công ty
phần mềm lớn trên thế giới cũng rất quan tâm và chú trọng tới việc nghiên cứu và
phát triển kỹ thuật khai phá dữ liệu: oracle tích hợp các công cụ khai phá dữ liệu
vào bộ oracle 9i, IBM đã đi tiên phong trong việc phát triển các ứng dụng khai phá
dữ liệu với các ứng dụng như Intelligence miner, …Ta có thể đưa ra một số ứng
dụng trong các lĩnh vực như:
• Thương mại: Phân tích dữ liệu bán hàng và thi trường, phân tích đầu tư,
quyết định cho vay, phát hiện gian lận.
• Thông tin sản xuất: Điều khiển và lập kế hoạch, hệ thống quản lý, phân tích
kết quả thử nghiệm.
• Thông tin khoa học: dự báo thời tiết, CSDL sinh học: Ngân hàng gen, khoa
học địa lý: dự báo động đất.
• Trong y tế, marketing, ngân hàng, viễn thông, du lịch, internet.
1.1.4 Bước phát triển của việc tổ chức và khai thác các CSDL
Cùng với việc tăng không ngừng khối lượng dữ liệu, các hệ thống thông tin
cũng được chuyên môn hóa, phân hoạch theo các lĩnh vực ứng dụng như sản xuất,
tài chính, buôn bán thị trường v.v. Như vậy, bên cạnh chức năng khai thác dữ liệu
có tính chất tác nghiệp, sự thành công trong kinh doanh không còn là năng suất
của các hệ thống thông tin nữa mà là tính linh hoạt và sẵn sàng đáp lại những yêu
cầu trong thực tế, CSDL cần đem lại những “tri thức” hơn là chính những dữ liệu
đó. các quyết định cần phải có càng nhanh càng tốt và phải chính xác dựa trên
những dữ liệu sẵn có. lúc này các mô hình CSDL truyền thống và ngôn ngữ SQL đã
cho thấy không có khả năng thực hiện công việc này.
Để lấy được tri thức trong khối dữ liệu khổng lồ này, người ta đã đ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 giao dịch 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, chỉ
được sử dụng 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ó được gọi
là các kho dữ liệu (data warehouse). Với những thách thức như vậy, các nhà nghiên
6

cứu đã đưa ra một phương pháp mới trên kho dữ liệu đáp ứng cả nhu cầu trong khoa
học cũng như trong hoạt động thực tiễn. Đó chính là công nghệ phát hiện tri thức từ
cơ sở dữ liệu
1.1.5 Quá trình phát hiện tri thức

Một vấn đề rất quan trọng để dẫn đến thành công là việc biết sử dụng thông
tin một cách có hiệu quả. Điều đó có nghĩa là từ các dữ liệu sẵn có phải tìm ra
những thông tin tiềm ẩn có giá trị mà trước đó chưa được phát hiện, phải tìm ra
những xu hướng phát triển và những yếu tố tác động lên chúng. Thực hiện công
việc đó chính là thực hiện quá trình phát hiện tri thức trong cơ sở dữ liệu
(Knowledge Discovery in Database – KDD) mà trong đó kỹ thuật này cho phép ta
lấy được các tri thức chính là pha khai phá dữ liệu (KPDL).
Quá trình phát hiện tri thức tiến hành qua 6 giai đoạn như Hình 1.1

Hinh 1.1: Quá trình phát hiện tri thức
Quá trình khám phá tri thức từ CSDL là một quá trình có sử dụng nhiều
phương pháp và công cụ tin học nhưng vẫn là một quá trình mà trong đó con người
là trung tâm. Do đó, nó không phải là một hệ thống phân tích tự động mà là một hệ
thống bao gồm nhiều hoạt động tương tác thường xuyên giữa con người và CSDL,
tất nhiên là với sự hỗ trợ của các công cụ tin học. Người sử dụng hệ thống ở đây
7

phải là người có kiến thức cơ bản về lĩnh vực cần phát hiện tri thức để có thể chọn
được đúng các tập con dữ liệu, các lớp mẫu phù hợp và đạt tiêu chuẩn quan tâm so
với mục đích. Tri thức mà ta nói ở đây là các tri thức rút ra từ các CSDL, thường để
phục vụ cho việc giải quyết một loạt nhiệm vụ nhất định trong một lĩnh vực nhất
định. Do đó, quá trình phát hiện tri thức cũng mang tính chất hướng nhiệm vụ,
không phải là phát hiện mọi tri thức bất kỳ mà là phát hiện tri thức nhằm giải quyết
tốt nhiệm vụ đề ra.
Trong hình 1.1 quá trình phát hiện tri thức bắt đầu của quá trình là kho dữ
liệu thô và kết thúc với tri thức được chiết xuất ra. Về lý thuyết thì có vẻ rất đơn
giản nhưng thực sự đây là một quá trình rất khó khăn gặp phải rất nhiều vướng mắc
như: quản lý các tập dữ liệu, phải lặp đi lặp lại toàn bộ quá trình, v.v…
1.1.5.1 Gom dữ liệu (Gathering)
Tập hợp dữ liệu là bước đầu tiên trong quá trình khai phá dữ liệu. Đây là
bước được khai thác trong một cơ sở dữ liệu, một kho dữ liệu và thậm chí các dữ
liệu từ các nguồn ứng dụng Web.
1.1.5.2 Lựa chọn dữ liệu (Selection)
Ở giai đoạn này dữ liệu được lựa chọn hoặc phân chia theo một số tiêu chuẩn
nào đó phục vụ mục đích khai thác, ví dụ chọn tất cả những người có tuổi đời từ 25
– 35 và có trình độ đại học.
1.1.5.3 Làm sạch, tiền xử lý và chuẩn bị dữ liệu (Cleaning, Pre-processing and
Preparation)
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à tính không đủ chặt chẽ, logíc. 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ụ: điểm = -1. Giai
đoạn này sẽ tiến hành xử lý những dạng dữ liệu không chặt chẽ nói trên. Những dữ
liệu dạng này được xem như thông tin dư thừa, không có giá trị. Bởi vậy, đây là một
quá trình rất quan trọng vì dữ liệu này nế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.
1.1.5.4 Chuyển đổi dữ liệu (Transformation)
8

Tiếp theo là giai đoạn chuyển đổi dữ liệu, dữ liệu đưa ra có thể sử dụng và
điều khiển được bởi việc tổ chức lại nó, tức là dữ liệu sẽ được chuyển đổi về dạng
phù hợp cho việc khai phá bằng cách thực hiện các thao tác nhóm hoặc tập hợp.
1.1.5.5 Khai phá dữ liệu (Data mining)
Đây là bước mang tính tư duy trong khai phá dữ liệu. Ở 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 là nguyên tắc phân lớp, nguyên tắc kết, v.v…
1.1.5.6 Đánh giá các luật và biểu diễn tri thức (Evaluation of Result)

Đây là giai đoạn cuối 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, không phải bất cứ mẫu dữ liệu nào cũng đều hữu ích,
đôi khi nó còn bị sai lệch. Vì vậy, cần phải ưu tiên những tiêu chuẩn đánh giá để
chiết xuất ra các tri thức (Knowlege) cần thiết. Đánh giá sự hữu ích của các mẫu
biểu diễn tri thức dựa trên một số phép đó. Sau đó sử dụng các kỹ thuật trình diễn
và trực quan hoá dữ liệu để biểu diễn tri thức khai phá được cho người sử dụng.
Từ quá trình khám phá tri thức trên chúng ta thấy được sự khác biệt giữa
khám phá tri thức và khai phá dữ liệu. Trong khi khám phá tri thức là nói đến quá
trình tổng thể phát hiện tri thức hữu ích từ dữ liệu. Còn KPDL chỉ là một bước trong
quá trình khám phá tri thức, các công việc chủ yếu là xác định được bài toán khai
phá, tiến hành lựa chọn phương pháp KPDL phù hợp với dữ liệu có được và tách ra
các tri thức cần thiết.
1.1.6 Các bước của quá trình KPDL
Các giải thuật KPDL thường được mô tả như những chương trình hoạt động
trực tiếp trên tệp dữ liệu. Với các phương pháp học máy và thống kê trước đây,
thường thì bước đầu tiên là các giải thuật nạp toàn bộ tệp dữ liệu vào trong bộ nhớ.
Khi chuyển sang các ứng dụng công nghiệp liên quan đến việc khai phá các kho dữ
liệu lớn, mô hình này không thể đáp ứng được. Không chỉ bởi vì nó không thể nạp
hết dữ liệu vào trong bộ nhớ mà còn vì khó có thể chiết xuất dữ liệu ra các tệp đơn
giản để phân tích được.

9

Hinh 1.2: Quá trình khai phá dữ liêu (KPDL)
Quá trình xử lý KPDL bắt đầu bằng cách xác định chính xác vấn đề cần giải
quyết. Sau đó sẽ xác định các dữ liệu liên quan dùng để xây dựng giải pháp. Bước
tiếp theo là thu thập các dữ liệu có liên quan và xử lý chúng thành dạng sao cho giải
thuật KPDL có thể hiểu được. Về lý thuyết thì có vẻ rất đơn giản nhưng khi thực
hiện thì đây thực sự là một quá trình rất khó khăn, gặp phải rất nhiều vướng mắc
như: các dữ liệu phải được sao ra nhiều bản (nếu được chiết xuất vào các tệp), quản
lý tập các tệp dữ liệu, phải lặp đi lặp lại nhiều lần toàn bộ quá trình (nếu mô hình dữ
liệu thay đổi), …
Bước tiếp theo là chọn thuật toán KPDL thích hợp và thực hiện việc KPDL để
tìm được các mẫu (pattern) có ý nghĩa dưới dạng biểu diễn tương ứng với các ý
nghĩa đó (thường được biểu diễn dưới dạng các luật xếp loại, cây quyết định, luật
sản xuất, biểu thức hồi quy, …).
Đặc điểm của mẫu phải là mới (ít nhất là đối với hệ thống đó). Độ mới có thể
đuợc đo tương ứng với độ thay đổi trong dữ liệu (bằng cách so sánh các giá trị hiện
tại với các giá trị trước đó hoặc các giá trị mong muốn), hoặc bằng tri thức (mối liên
hệ giữa phương pháp tìm mới và phương pháp cũ như thế nào). Thường thì độ mới
của mẫu được đánh giá bằng một hàm logic hoặc một hàm đo độ mới, độ bất ngờ
của mẫu. Ngoài ra, mẫu còn phải có khả năng sử dụng tiềm tàng. các mẫu này sau
khi được xử lý và diễn giải phải dẫn đến những hành động có ích nào đó được đánh
giá bằng một hàm lợi ích. mẫu khai thác được phải có giá trị đối với các dữ liệu mới
với độ chính xác nào đó.
10

Kỹ thuật KPDL thực chất là phương pháp không hoàn toàn mới. Nó là sự kế
thừa, kết hợp và mở rộng của các kỹ thuật cơ bản đã được nghiên cứu từ trước như
máy học, nhận dạng, thống kê (hồi quy, xếp loại, phân cụm), các mô hình đồ thị,
các mạng Bayes, trí tuệ nhân tạo, thu thập tri thức hệ chuyên gia, v.v… Tuy nhiên,
với sự kết hợp tài tình của KPDL, kỹ thuật này có ưu thế hơn hẳn các phương pháp
trước đó, đem lại nhiều triển vọng trong việc ứng dụng phát triển nghiên cứu khoa
học.
1.2 Một số kỹ thuật khai phá dữ liệu cơ bản
1.2.1 Khai phá dữ liệu dự đoán
Nhiệm vụ của KPDL dự đoán là đư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. Bao gồm các kỹ thuật: Phân lớp (Classification); Hồi qui
(Regres-sion…).
1.2.1.1 Phân lớp (Classification)

Mục tiêu của phương pháp 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 phân loại dữ liệu thường gồm hai bước: xây dựng mô hình và sử
dụng mô hình để phân lơp dữ liệu.
▪ Bước 1: Xây dựng mô hình dựa trên việc phân tích các mẫu dữ liệu cho
trước. Mỗi mẫu thuộc về một lớp, được xác định bởi một thuộc tính gọi là thuộc
tính lớp. Các mẫu dữ liệu này còn được gọi là tập dữ liệu huấn luyện. Các nhãn lớp
của tập dữ liệu huấn luyện đều phải được xác định trước khi xây dựng mô hình, vì
vậy phương pháp này còn được gọi là học có giám sát.
▪ Bước 2: Sử dụng mô hình để phân loại dữ liệu. Trước hết chúng ta phải
tính độ chính xác của mô hình. Nếu độ chính xác là chấp nhận được, mô hình sẽ
được sử dụng để dự đoán nhãn lớp cho các mẫu dữ liệu khác trong tương lai. Hay
nói cách khác, phân lớp là học một hàm ánh xạ một mục dữ liệu vào một trong số
các lớp cho trước. Hay nói các khác, phân loại là học một hàm ánh xạ một mục dữ
liệu vào trong số các lớp cho trước.
11

1.2.1.2 Hồi quy (Regression)
Phương pháp hồi quy khác với phương pháp phân loại dữ liệu ở chỗ, hồi qui
dùng để dự đoán về các giá trị liên tục còn phân loại dữ liệu chỉ dùng để dự đoán về
các giá trị rời rạc. Hồi quy là học một hàm ánh xạ một mục dữ liệu vào một biến dự
báo giá trị thực. Các ứng dụng hồi quy có nhiều, ví dụ như đánh giá xác xuất một
bệnh nhân sẽ chết dựa trên tập kết quả xét nghiệm chẩn đoán, dự báo nhu cầu của
người tiêu dùng đối với một sản phẩn mới dựa trên hoạt động quảng cáo tiêu dùng.
1.2.2 Khai phá dữ liệu mô tả
Kỹ thuật này có nhiệm vụ mô tả về các tính chất hoặc các đặc tính chung của
dữ liệu trong CSDL hiện có. Bao gồm các kỹ thuật: Phân cụm (clustering); Khai
phá luật kết hợp (association rules) …
1.2.2.1 Phân cụm
Mục tiêu chính của phương pháp 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 cụm sao cho các đối tượng thuộc cùng một
cụm là tương đồng còn các đối tượng thuộc các cụm khác nhau sẽ không tương
đồng. Phân cụm dữ liệu là một ví dụ của phương pháp học không giám sát. Không
giống như phân lớp dữ liệu, phân cụm dữ liệu không đòi hỏi phải định nghĩa trước
các mẫu dữ liệu huấn luyện. Vì thế, có thể coi phân cụm dữ liệu là một cách học
bằng quan sát (learning by 8 observation), trong khi phân lớp dữ liệu là học bằng ví
dụ (learning by example). Trong phương pháp này bạn sẽ không thể biết kết quả các
cụm thu được sẽ như thế nào khi bắt đầu quá trình. Vì vậy, thông thường cần có một
chuyên gia về lĩnh vực đó để đánh giá các cụm thu được. Phân cụm dữ liệu được sử
dụng nhiều trong các ứng dụng về phân đoạn thị trường, phân đoạn khách hàng,
nhận dạng mẫu, phân lớp trang Web… Ngoài ra phân cụm dữ liệu còn có thể được
sử dụng như một bước tiền xử lí cho các thuật toán khai phá dữ liệu khác.
Hình 1.3. cho thấy sự phân cụm tập dữ liệu cho vay vào trong 3 cụm: Lưu ý
rằng các cụm chồng lên nhau cho phép các điểm dữ liệu thuộc về nhiều hơn một
cụm.

12

Hinh 1.3: Phân cụm tập dữ liệu cho vay thành 3 cụm
1.2.2.2 Khai phá luật kết hợp
Mục tiêu của phương pháp này là phát hiện và đưa ra các mối liên hệ giữa
các giá trị dữ liệu trong cơ sở dữ liệu. Mẫu đầu ra của giải thuật KPDL là luật kết
hợp tìm được. Khai phá luật kết hợp được thực hiện qua 2 bước:
• Bước 1: tìm tất cả các tập mục phổ biến, một tập mục phổ biến được xác định qua
tính độ hỗ trợ và thỏa mãn độ hỗ trợ cực tiểu.
• Bước 2: sinh ra các luật kết hợp mạnh từ tập mục phổ biến, các luật phải thỏa mãn
độ hỗ trợ cực tiểu và độ tin cậy cực tiểu.
Phương pháp này được sử dụng rất hiệu quả trong các lĩnh vực như
marketing có chủ đích, phân tích quyết định, quản lí kinh doanh, …
1.3 Một số so sánh giữa khai phá dữ liệu và các phương pháp cơ bản khác
Khai phá dữ liệu là một lĩnh vực liên quan tới rất nhiều ngành học khác như: hệ
CSDL, thống kê,… Hơn nữa, tuỳ vào cách tiếp cận được sử dụng, khai phá dữ liệu
còn có thể áp dụng một số kĩ thuật như mạng nơ ron, lý thuyết tập thô hoặc tập mờ,
biểu diễn tri thức… Như vậy, có thể hiểu rằng khai phá dữ liệu thực ra là dựa trên
các phương pháp cơ bản đã biết. Tuy nhiên, sự khác biệt của khai phá dữ liệu so với
các phương pháp đó là gì? Tại sao khai phá dữ liệu lại có ưu thế hơn hẳn các
phương pháp cũ? Ta sẽ lần lượt xem xét và giải quyết các câu hỏi này.
13

1.3.1 So sánh với phương pháp hệ chuyên gia (Expert Systems)
Theo E. Feigenbaum: “Hệ chuyên gia (Expert System) là một chương trình máy
tính thông minh sử dụng tri thức (knowledge) và các thủ tục suy luận (inference
procedures) để giải những bài toán tương đối khó khăn đòi hỏi những chuyên gia
mới giải được”.
Hệ chuyên gia là một hệ thống tin học có thể mô phỏng (emulates) năng lực
quyết đoán (decision) và hành động (making abilily) của một chuyên gia (con
người). Hệ chuyên gia là một trong những lĩnh vực ứng dụng của trí tuệ nhân tạo
(Artificial Intelligence) như hình dưới đây.

Hinh 1.4: Một số lĩnh vực ứng dụng của trí tuệ nhân tạo

Hệ chuyên gia sử dụng các tri thức của những chuyên gia để giải quyết các
vấn đề (bài toán) khác nhau thuộc mọi lĩnh vực. Tri thức (knowledge) trong hệ
chuyên gia phản ánh sự tinh thông được tích tụ từ sách vở, tạp chí, từ các chuyên
gia hay các nhà bác học. Các thuật ngữ hệ chuyên gia, hệ thống dựa trên tri thức
(knowledge-based system) hay hệ chuyên gia dựa trên tri thức (knowledge-based
expert system) thường có cùng nghĩa.
Các kỹ thuật thu thập giúp cho việc lấy tri thức từ các chuyên gia con người.
Mỗi phương pháp hệ chuyên gia là một cách suy diễn các luật từ các ví dụ và giải
Robotic
Vision
Natural
Language
Understanding
Expert System
Artificial
Neural
Systems
Speech
Artificial Intelligence

14

pháp đối với bài toán chuyên gia đưa ra. Phương pháp hệ chuyên gia khác với khai
phá dữ liệu ở chỗ các ví dụ của chuyên gia thường ở mức chất lượng cao hơn nhiều
so với các dữ liệu trong CSDL, và chúng thường chỉ bao hàm được các trường quan
trọng. Hơn nữa các chuyên gia sẽ xác nhận giá trị và tính hữu ích của các mẫu phát
hiện được.
1.3.2 So sánh với phương pháp thống kê (Statistics)
Mặc dù các phương pháp thống kê cung cấp một nền tảng lý thuyết vững chắc
cho các bài toán phân tích dữ liệu nhưng chỉ có tiếp cận thống kê thuần tuý thôi
chưa đủ bởi:
● Các phương pháp thống kê không phù hợp với các kiểu dữ liệu có cấu trúc
trong rất nhiều các cơ sở dữ liệu
● Thống kê hoàn toàn tính toán trên dữ liệu, nó không sử dụng tri thức sẵn có
về lĩnh vực quan tâm
● Các kết quả của phân tích thống kê có thể rất nhiều và khó có thể làm rõ được
● Các phương pháp thống kê cần có sự hướng dẫn của người dùng để xác định
phân tích dữ liệu như thế nào và ở đâu.
Phương pháp thống kê là một trong những nền tảng lí thuyết của khai phá dữ
liệu. Sự khác nhau cơ bản giữa khai phá dữ liệu và thống kê ở chỗ khai phá dữ liệu
là một phương tiện được dùng bởi người sử dụng đầu cuối chứ không phải là các
nhà thống kê. Khai phá dữ liệu đã khắc phục được các yếu điểm trên của thống kê,
tự động quá trình thống kê một cách hiệu quả vì thế giảm bớt công việc của người
dùng đầu cuối, tạo ra một công cụ dễ sử dụng hơn.
1.3.3 So sánh với phương pháp học máy (Machine Learning)
Trong vài năm trở lại đấy lĩnh vực trí tuệ nhân tạo nói chung và học máy nói
riêng phát triển cực kỳ mạnh vì khả năng ứng dụng của nó. Học máy là một lĩnh
vực của trí tuệ nhân tạo liên quan đến việc nghiên cứu và xây dựng các kĩ thuật cho
phép các hệ thống “học” tự động từ dữ liệu để giải quyết những vấn đề cụ thể. Ngày
nay học máy được ứng dụng rộng rãi trên nhiều lĩnh vực và đem lại thành công lớn.
Một số lĩnh vực áp dụng học máy thành công như: Xử lý ngôn ngữ tự nhiên, Hệ
thống gợi ý, Xử lý dữ liệu lớn, lĩnh vực robot, xe tự lái.v.v..