Luận văn Thạc sĩ Khoa học máy tính: 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

ĐẠ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

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

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

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

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

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

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

TT Từ viết tắt Dạng đầy đủ Chú thích

DM Data Mining Khai thác dữ liệu 1

SVM Supprot Vector Machin Máy hỗ trợ vector 2

KDD Knowlegde Discovery in 3

Phát hiện tri thức trong

Databases

CSDL

RF Random forest Rừng ngẫu nhiên 4

E Edible Ăn được hoặc không có độc 5

P Poisonous Có độc hoặc Không ăn được 6

PCA Principal Component Analysis Thuật toán phân tích thành 7

phần chính

K-NN K-Nearest neighbor K láng giềng gần nhất 8

ACC 9

Accuracy

Độ chính xác

10 ARFF Attribute Relation File Format

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).

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.

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,

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

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

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

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)

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.

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 đó.

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.

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.

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.

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.

Robotic

Vision

Speech

Natural Language

Artificial Neural Systems

Expert System

Understanding

Artificial Intelligence

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

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..

So với phương pháp học máy, khai phá dữ liệu có lợi thế hơn ở chỗ, khai phá

dữ liệu có thể sử dụng với các cơ sở dữ liệu thường động, không đầy đủ, bị nhiễu và

lớn hơn nhiều so với các tập dữ liệu học máy điển hình. Trong khi đó phương pháp

học máy chủ yếu được áp dụng trong các CSDL đầy đủ, ít biến động và tập dữ liệu

không quá lớn.

Thật vậy, trong học máy, thuật ngữ cơ sở dữ liệu chủ yếu đề cập tới một tập

các mẫu được lưu trong tệp. Các mẫu thường là các vectơ với độ dài cố định, thông

tin về đặc điểm, dãy các giá trị của chúng đôi khi cũng được lưu lại như trong từ

điển dữ liệu. Một giải thuật học sử dụng tập dữ liệu và các thông tin kèm theo tập

dữ liệu đó làm đầu vào và đầu ra biểu thị kết quả của việc học. Học máy có khả

năng áp dụng cho cơ sở dữ liệu, lúc này, học máy sẽ không phải là học trên tập các

mẫu nữa mà học trên tập các bản ghi của cơ sở dữ liệu. Tuy nhiên, trong thực tế, cơ

sở dữ liệu thường động, không đầy đủ và bị nhiễu, lớn hơn nhiều so với các tập dữ

liệu học máy điển hình. Các yếu tố này làm cho hầu hết các giải thuật học máy trở

nên không hiệu quả. Khai phá dữ liệu lúc này sẽ xử lý các vấn đề vốn đã điển hình

trong học máy và vượt quá khả năng của học máy, đó là sử dụng được các CSDL

chứa nhiều nhiễu, dữ liệu không đầy đủ hoặc biến đổi liên tục.

1.3.4 So sánh với phương pháp học sâu (Deep Learning)

Deep learning – Học sâu: là một chi của ngành máy học dựa trên một tập

hợp các thuật toán để cố gắng để mô hình dữ liệu trừu tượng hóa ở mức cao bằng

cách sử dụng nhiều lớp xử lý với cấu trúc phức tạp, hoặc bằng cách khác bao gồm

nhiều biến đổi phi tuyến.

Deep learning là một phần của một họ các phương pháp học máy rộng hơn

dựa trên đại diện học của dữ liệu. Một quan sát (ví dụ như, một hình ảnh) có thể

được biểu diễn bằng nhiều cách như một vector của các giá trị cường độ cho mỗi

điểm ảnh, hoặc một cách trừu tượng hơn như là một tập hợp các cạnh, các khu vực

hình dạng cụ thể, … Một vài đại diện làm khiến việc học các nhiệm vụ dễ dàng hơn

(ví dụ, nhận dạng khuôn mặt hoặc biểu hiện cảm xúc trên khuân mặt) từ các ví dụ.

Một trong những hứa hẹn của học sâu là thay thế các tính năng thủ công bằng các

thuật toán hiệu quả đối với học không có giám sát hoặc nửa giám sát và tính năng

phân cấp.

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

Các nghiên cứu trong lĩnh vực này cố gắng thực hiện các đại diện tốt hơn và

tạo ra các mô hình để tìm hiểu các đại diện này từ dữ liệu quy không dán nhãn mô

lớn. Một số đại diện được lấy cảm hứng bởi những tiến bộ trong khoa học thần kinh

và được dựa trên các giải thích của mô hình xử lý và truyền thông thông tin trong

một hệ thống thần kinh, chẳng hạn như mã hóa thần kinh để cố gắng để xác định

các mối quan hệ giữa các kích thích khác nhau và các phản ứng liên quan đến thần

kinh trong não.

Nhiều kiến trúc Deep learning khác nhau như mạng nơ-ron sâu, mã mạng

nơ-ron tích chập sâu, mạng niềm tin sâu và mạng nơron tái phát đã được áp dụng

cho các lĩnh vực như thị giác máy tính, tự động nhận dạng giọng nói, xử lý ngôn

ngữ tự nhiên, nhận dạng âm thanh ngôn ngữ và tin sinh học, chúng đã được chứng

minh là tạo ra các kết quả rất tốt đối với nhiều nhiệm vụ khác nhau.

Khái niệm chính trong thuật toán nghiêng sâu là tự động hóa việc khai thác

các biểu diễn (trừu tượng) từ dữ liệu. Thuật toán học tập sâu sử dụng một lượng lớn

dữ liệu không giám sát để tự động trích xuất biểu diễn phức tạp. Những thuật toán

này chủ yếu được thúc đẩy bởi lĩnh vực trí thông minh nhân tạo, có mục tiêu chung

là mô phỏng khả năng của con người để quan sát, phân tích, học hỏi và đưa ra quyết

định, đặc biệt cho các vấn đề cực kỳ phức tạp. Công việc liên quan đến những thách

thức phức tạp này là động lực chính đằng sau các thuật toán Deep Learning cố gắng

mô phỏng cách tiếp cận học tập phân cấp của bộ não con người.

Các mô hình dựa trên kiến trúc học tập nông như cây quyết định, máy hỗ trợ

vector và lý do dựa trên trường hợp có thể bị thiếu khi cố gắng trích xuất thông tin

hữu ích từ cấu trúc và mối quan hệ phức tạp trong kho dữ liệu đầu vào. Ngược lại,

kiến trúc

Deep Learning có khả năng khái quát hóa theo những cách phi địa phương và

toàn cầu, tạo ra các mô hình học tập và các mối quan hệ vượt ra ngoài hàng xóm

ngay lập tức trong dữ liệu. Học sâu là một bước quan trọng hướng tới trí thông minh

nhân tạo. Nó không chỉ cung cấp các biểu diễn dữ liệu phức tạp phù hợp với các

nhiệm vụ AI mà còn làm cho các máy tính độc lập với kiến thức của con người là

mục tiêu cuối cùng của AI. Nó trích xuất các biểu diễn trực tiếp từ dữ liệu không

giám sát mà không có sự can thiệp của con người.

Một khái niệm chính nằm sâu trong các phương thức Deep Learning là phân

phối các biểu diễn dữ liệu, trong đó một số lượng lớn các cấu hình có thể có của các

tính năng trừu tượng của dữ liệu đầu vào là khả thi, cho phép trình bày nhỏ gọn của

từng mẫu và dẫn đến tổng quát hơn. Số lượng cấu hình có thể có liên quan theo cấp

số nhân với số lượng các tính năng trừu tượng được trích xuất. Lưu ý rằng dữ liệu

quan sát được tạo ra thông qua tương tác của một số yếu tố đã biết / chưa biết, và do

đó khi một mẫu dữ liệu thu được thông qua một số cấu hình của các yếu tố đã học,

các mẫu dữ liệu bổ sung (không nhìn thấy) có thể được mô tả.

So với việc học dựa trên các khái quát hóa cục bộ, số lượng các mẫu có thể

thu được bằng cách sử dụng một biểu diễn phân bố nhanh chóng với số lượng các

yếu tố đã học. Các thuật toán học tập sâu dẫn đến các biểu diễn trừu tượng bởi vì

các biểu diễn trừu tượng hơn thường được xây dựng dựa trên các phép trừu tượng ít

hơn. Một lợi thế quan trọng của các biểu diễn trừu tượng hơn là chúng có thể bất

biến với các thay đổi cục bộ trong dữ liệu đầu vào.

Học các tính năng bất biến như vậy là một mục tiêu chính đang diễn ra trong

việc nhận dạng mẫu (ví dụ các tính năng học tập không thể biến đổi theo hướng

khuôn mặt trong một nhiệm vụ nhận diện khuôn mặt). Ngoài việc biểu diễn bất biến

như vậy cũng có thể tháo gỡ các yếu tố của biến thể trong dữ liệu. Dữ liệu thực

được sử dụng trong các nhiệm vụ liên quan đến AI chủ yếu phát sinh từ các tương

tác phức tạp của nhiều nguồn. Ví dụ: hình ảnh bao gồm các nguồn biến thể khác

nhau như ánh sáng, hình dạng đối tượng và vật liệu đối tượng. Các biểu diễn trừu

tượng được cung cấp bởi các thuật toán học tập sâu có thể tách các nguồn khác nhau

của các biến thể trong dữ liệu.

Thuật toán học sâu là kiến trúc sâu của các lớp liên tiếp. Mỗi lớp áp dụng

một phép biến đổi phi tuyến trên đầu vào của nó và cung cấp một biểu diễn trong

đầu ra của nó. Mục đích là để tìm hiểu một biểu diễn phức tạp và trừu tượng của dữ

liệu theo cách phân cấp bằng cách truyền dữ liệu qua nhiều lớp chuyển đổi. Dữ liệu

cảm giác (ví dụ: pixel trong một hình ảnh) được nạp vào lớp đầu tiên. Do đó, đầu ra

của mỗi lớp được cung cấp làm đầu vào cho lớp tiếp theo của nó.

1.4 Tổng kết chương

Chương này đã tổng hợp và trình bày một số kiến thức lý thuyết cơ bản về

khai phá dữ liệu và một số kỹ thuật khai phái dữ liệu cơ bản. Một số kỹ thuật khai

phá dữ liệu sử dụng phương pháp phân lớp, phân cụm cũng được giới thiệu và trình

bày trong chương này. Ngoài ra, những phân tích, so sánh giữa khai phá dữ liệu và

các phương pháp cơ bản khác cũng được nêu ra ở chương này.

CHƯƠNG 2

MỘT SỐ PHƯƠNG PHÁP VÀ KỸ THUẬT PHÂN LỚP DỮ LIỆU

2.1 Tổng quan về phân lớp dữ liệu

Phân lớp là một trong những mối quan tâm nhiều nhất của con người trong quá

trình làm việc với một tập hợp đối tượng. Điều này giúp con người có thể tiến hành

việc sắp xếp, tìm kiếm các đối tượng một cách thuật lợi. Khi biểu diễn đối tượng

vào các cơ sở dữ liễu, tính chất lớp vốn có của đối tượng trong thực tế thường đước

biểu diễn tương ứng bằng một thuộc tính “Lớp” riêng biệt. Chẳng hạn, trong hệ

thống thông tin quản lý tư liệu của thư viện, thuộc tính về loại tư liệu có miềm giá

trị là tập tên chuyên ngành của tư liệu, gồm các giá trị như “Tin học”, “Vật lý”, ...

Trước đây các công việc gán các giá trị của thuộc tính lớp thường được làm một

cách thủ công, Nhưng hiện nay, với sự bùng nổ của thông tin và các loại dữ liệu,

việc đánh giá, thuộc tính lớp một cách thủ công là rất khó khăn, có thế nói là không

thể. Do vậy các phương pháp phân lớp tự động là rất cần thiết và là một trong

những chủ đề chính trong khai phá dữ liệu.

Các cơ sở dữ liệu thường chứa rất nhiều các thông tin ẩn -các thông tin có thể

sử dụng phục vụ quá trình phân lớp. Các giải thuật phân lớp thường phân tích dữ

liệu nhằm tìm ra các mô hình mô tả các lớp dữ liệu, từ đó có thể quyết định được

một phần tử dữ liệu mới là thuộc vào lớp nào.

Việc tìm ra lớp của một phần tử dữ liệu mới trong nhiều trường hợp có ý nghĩa

rất quan trọng, nó hỗ trợ quá trình ra quyết định thông minh thậm chí là những

quyết định mang tính sống còn. Ví dụ, trong ngân hàng, một nhân viên cho vay vốn

rất muốn có một hệ thống có khả năng tự học từ các dữ liệu lịch sử để có thể quyết

định được một đơn vay vốn mới của khách hàng thuộc lớp “an toàn” hay “mạo

hiểm”, trên cơ sở đó sẽ có các quyết định phù hợp. Mô hình phân lớp dự báo thời

tiết có thể cho biết thời tiết ngày mai là mưa, hay nắng dựa vào những thông số về

độ ẩm, sức gió, nhiệt độ, … của ngày hôm nay và các ngày trước đó.

Hay là một bác sỹ sẽ rất muốn có một hệ thống phân tích dữ liệu điều trị lịch

sử để dự đoán xem một bệnh nhân mới với những triệu chứng thu được sẽ thuộc

bệnh nào, trên cơ sở đó sẽ có các phác đồ điều trị tương ứng... Trong những năm

qua, phân lớp dữ liệu đã thu hút sự quan tâm các nhà nghiên cứu trong nhiều lĩnh

vực khác nhau như học máy (machine learning), hệ chuyên gia (expert system),

thống kê (statistics)... Công nghệ này cũng ứng dụng trong nhiều lĩnh vực khác

nhau như: thương mại, nhà băng, maketing, nghiên cứu thị trường, bảo hiểm, y tế,

giáo dục... Phần lớn các thuật toán ra đời trước đều sử dụng cơ chế dữ liệu cư trú

trong bộ nhớ (memory resident), thường thao tác với lượng dữ liệu nhỏ. Một số

thuật toán ra đời sau này đã sử dụng kỹ thuật cư trú trên đĩa cải thiện đáng kể khả

năng mở rộng của thuật toán với những tập dữ liệu lớn lên tới hàng tỉ bản ghi.

Bản chất của bài toán phân lớp là dự đoán các nhãn (hay lớp) của các phần tử

dữ liệu đầu vào và các nhãn (hay lớp) này là các giá trị rời rạc. Thông thường, các

giải thuật phân lớp thường hoạt động thông qua hai bước như sau:

• Bước thứ nhất (learning step)

Quá trình học nhằm xây dựng một mô hình mô tả một tập các lớp dữ liệu hay

các khái niệm định trước. Đầu vào của quá trình này là một tập dữ liệu có cấu trúc

được mô tả bằng các thuộc tính và được tạo ra từ tập các bộ giá trị của các thuộc

tính đó. Mỗi bộ giá trị được gọi chung là một phần tử dữ liệu (data tuple), có thể là

các mẫu (sample), ví dụ (example), đối tượng (object), bản ghi (record) hay trường

hợp (case). Khoá luận sử dụng các thuật ngữ này với nghĩa tương đương. Trong tập

dữ liệu này, mỗi phần tử dữ liệu được giả sử thuộc về một lớp định trước, lớp ở đây

là giá trị của một thuộc tính được chọn làm thuộc tính gán nhãn lớp hay thuộc tính

phân lớp (class label attribute). Đầu ra của bước này thường là các quy tắc phân lớp

dưới dạng luật dạng if-then, cây quyết định, công thức logic, hay mạng nơron.

Quá trình này được mô tả như trong hình 2.1.

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

• Bước thứ hai (classification step)

Bước thứ hai dùng mô hình đã xây dựng ở bước trước để phân lớp dữ liệu

mới. Trước tiên độ chính xác mang tính chất dự đoán của mô hình phân lớp vừa tạo

ra được ước lượng. Holdout là một kỹ thuật đơn giản để ước lượng độ chính xác

đó. Kỹ thuật này sử dụng một tập dữ liệu kiểm tra với các mẫu đã được gán nhãn

lớp. Các mẫu này được chọn ngẫu nhiên và độc lập với các mẫu trong tập dữ liệu

đào tạo. Độ chính xác của mô hình trên tập dữ liệu kiểm tra đã đưa là tỉ lệ phần

trăm các các mẫu trong tập dữ liệu kiểm tra được mô hình phân lớp đúng (so với

thực tế). Nếu độ chính xác của mô hình được ước lượng dựa trên tập dữ liệu đào tạo

thì kết quả thu được là rất khả quan vì mô hình luôn có xu hướng “quá vừa” dữ liệu.

Quá vừa dữ liệu là hiện tượng kết quả phân lớp trùng khít với dữ liệu thực tế vì quá

trình xây dựng mô hình phân lớp từ tập dữ liệu đào tạo có thể đã kết hợp những đặc

điểm riêng biệt của tập dữ liệu đó. Do vậy cần sử dụng một tập dữ liệu kiểm tra độc

lập với tập dữ liệu đào tạo. Nếu độ chính xác của mô hình là chấp nhận được, thì

mô hình được sử dụng để phân lớp những dữ liệu tương lai, hoặc những dữ liệu mà

giá trị của thuộc tính phân lớp là chưa biết.

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

Hình 2.3: Quá trình phân lớp dữ liệu - (b2) Phân lớp dữ liệu mới

Trong mô hình phân lớp, thuật toán phân lớp giữ vai trò trung tâm, quyết

định tới sự thành công của mô hình phân lớp. Do vậy chìa khóa của vấn đề phân lớp

dữ liệu là tìm ra được một thuật toán phân lớp nhanh, hiệu quả, có độ chính xác cao

và có khả năng mở rộng được. Trong đó khả năng mở rộng được của thuật toán

được đặc biệt trú trọng và phát triển. Có thể liệt kê ra đây các kỹ thuật phân lớp đã

được sử dụng trong những năm qua.

2.2 Phân lớp dữ liệu bằng cây quyết định

J. Ros Quinlan là người phát triển giải thuật cây quyết định có tên là ID3

(viết tắt từ cụm từ “Iterative Dechotomiser”), sau đó cũng chính tác giả này đề xuất

giải thuật phân lớp C4.5 (một hậu duệ của thuật toán ID3). Giải thuật C4.5 này đã

được dùng làm chuẩn (benchmark) để các thuật toán mới so sánh. Cũng trong

khoảng thời gian này thì một nhóm các nhà thống kê gồm L. Breiman, J. Friedman,

R. Olshen và C. Stone đã xuất bản cuốn sách “Classfication and Regression Tree

(CART)” mô tả phương pháp tạo cây quyết định nhị phân. Giải thuật ID3 và CART

đã trở thành các hòn đá tảng và nó mở đầu cho hàng loạt các giải thuật dựa trên học

quy nạp cây quyết định (decision tree induction). Giải thuật học dựa trên cây quyết

định hoạt động trên tập dữ liệu được biểu diễn bằng cách giá trị rời rạc, trong

trường hợp dữ liệu được biểu diễn bằng các thuộc tính có giá trị liên tục thì cần thực

hiện bước rời rạc hóa. Các giải thuật ID3, CART và C4.5 đều áp dụng cách tiếp cận

ăn tham (greedy) (một thuật toán không quay lui (non-backtracking)) để xây dựng

cây theo hướng từ trên xuống. Tập dữ liệu huấn luyện sẽ được chia thành các tập

nhỏ hơn trong quá trình xây dựng cây theo cơ chế chia để trị (devide-and-conquer).

Giải thuật ID3 học

Dữ liệu huấn luyện

Dười đây mô tả thuật toán xây dựng cây cơ bản chung của các giải thuật này.

Đữ liệu kiểm thử

Tập luật phân lớp

Đánh giá

Dữ liệp mới

Nhãn lớp

Đánh giá

Hình 2.4:Phân lớp cho bài toán cho vay vốn của ngân hàng

Thuật toán xây dựng cây quyết định

Đầu vào: Tập D chứa dữ liệu huấn luyện

attribute_list chứa danh sách các thuộc tính ứng cử

Đầu ra: Cây quyết định

Generate_decision_tree (D, attribute_list)

1. Tạo một nút gốc N cho cây quyết định

2. If toàn bộ dữ liệu trong D đều thuộc lớp C, return nút N là nút lá có nhãn C

3. If attribute_list là rỗng, return nút N với nhãn là lớp xuất hiện nhiều nhất

trong D

4. splitting_attribute = attribute_selection_method (D, attribute_list) tìm thuộc

tính phân chia tốt nhất

5. Gán cho nút N nhãn là splitting_attribute

6. attribute_list attribute_list \ {splitting_attribute}

(loại bỏ thuộc tính splitting_attribute khỏi attribute_list)

7. For each giá trị j của thuộc tính splitting_attribute

7.1. Gọi 𝐷𝑗 là tập chứa các phần tử dữ liệu mà thuộc tính splitting_attribute có giá

trị j

7.2. If 𝐷𝑗 là rỗng thì thêm một nút lá 𝑁𝑗 cho nút N có nhãn là nhãn phổ biến nhất

xuất hiện trong D

7.3. Else gắn cây trả về bởi Generate_decision_tree

(𝐷𝑗, attribute_list) vào nút N

8. return N

Hình 2.5:Thuật toán xây dựng cây quyết định

Trong đó, attribute_list là tập các thuộc tính mô tả tập dữ liệu huấn luyện D;

attribute_selection_method là hàm lựa chọn thuộc tính tốt nhất để phân chia dữ liệu,

bản chất nó là giải thuật dựa trên kinh nghiệm (heuristic) để tìm ra thuộc tính nào có

khả năng phân biết được ccs phần tử dữ liệu trong tập D vào các lớp nhất. Nó dựa

trên một độ đo nào đó chẳng hạn độ lời thông tin (information gain), hay độ đo chỉ

số gini (Gini index) để tìm ra thuộc tính tốt nhất.

Giải thuật bắt đầu bằng thao tác tạo ra một nút N mô tả tập dữ liệu D (bước 1).

Nếu toàn bộ dữ liệu trong D cùng có chung một nhãn lớp thì N sẽ là một nút lá có

nhãn là nhãn chung của các phần tử dữ liệu, và thuật toán dừng. Nếu không thì nó

sẽ gọi hàm attribute_selection_method () để tìm ra thuộc tính tốt nhất dùng để phân

chia tập dữ liệu D thành các phần 𝐷𝑗, và nút N sẽ được gán nhãn là thuộc tính tìm

được. Giải thuật đệ quy với các tập con dữ liệu 𝐷𝑗. Hình 2.4. minh họa cây quyết

định được tạo ra bởi giải thuật trên tập dữ liệu bán hàng (trong bảng 2.1) để tìm ra

những loại khách hàng nào có khả năng máy tính (buys_computer) (yes là có mua

và no là không mua). Độ phức tạp của thuật toán là trong đó là

số thuộc tính mô tả tập dữ liệu là số lượng các phần tử trong

Bảng 2.1: Bảng dữ liệu khách hàng

ID Tuổi Thu nhập

1 Sinh viên Đánh giá tin dụng fair no Mua máy tính no youth high

2 youth high no excellent no

3 middleaged high no fair yes

4 senior medium no fair yes

5 senior low yes fair yes

6 senior low yes excellent no

7 middleaged low yes excellent yes

8 youth medium no fair no

9 youth low yes fair yes

10 senior midium yes fair yes

11 youth midium yes excellent yes

12 middleaged midium no excellent yes

13 middleaged high yes fair yes

14 senior midium no excellent no

Trong trường hợp giá trị của một thuộc tính nòa đó không phải là giá trị rời

rạc (chẳng hạn như thuộc tính tuổi), khi đó một phương pháp rời rạc hóa đã được áp

dụng (xem bảng 2.1.). Cụ thể nó đã được chia thành 3 loại tuổi rời rạc: trẻ (youth),

trung niên (middle_age) và già (senior).

Điểm mấu chốt trong giải thuật xây dựng cây quyết định ở trên là hàm lựa

chọn thuộc tính tốt nhất để phân chia dữ liệu. Phần tiếp theo sẽ trình bày một số độ

age?

senior

youth

Middle_age

credit_rating?

student?

yes

excellent

fair

yes

đo dùng để đánh giá “chất lương” của các thuộc tính.

Hình 2.6: Minh họa cây quyết định

Trong cây quyết định:

• Nút gốc: là node trên cùng của cây

• Node trong: biểu diễn một kiểm tra trên một thuộc tính đơn (hình chữ nhật)

• Nhánh: biểu diễn các kết quả của kiểm tra trên node trong (mũi tên)

• Node lá: biểu diễn lớp hay sự phân phối lớp (hình tròn)

Để phân lớp mẫu dữ liệu chưa biết, giá trị các thuộc tính của mẫu được đưa

vào kiểm tra trên cây quyết định. Mỗi mẫu tương ứng có một đường đi từ gốc đến lá

và lá biểu diễn dự đoán giá trị phân lớp mẫu đó.

2.2.1 Độ lợi thông tin

Độ lợi thông tin (information gain) là độ đo đước sử dụng trong giải thuật ID3.

Đầu tiên là công thức đo lượng thông tin kỳ vọng để phân lớp một phần tử trong tập

dữ liệu D đước đo bằng công thức sau:

(2.1)

Trong đó pi là xác suất một phần tử dữ liệu trong D thuộc vào lớp Ci và nó

được ước lượng bằng công thức , với là tập các phần tử dữ liệu trong D

thuộc vào lớp Ci ; m là số lượng các lớp trong D. Hàm logarit cơ số 2 được sử dụng

là do công thức trên đo lượng thông tin theo đơn vị bit (theo lý thuyết thông tin của

C. Shannon). Hàm info(D) còn được gọi là entropy của D.

Bây giờ giả sử ta phân chia dữ liệu trong D theo thuộc A nào đó, và giả sử

thuộc tính này có v giá trị (rời rạc) khác nhau là {a1, a2, ..., av} Thuộc tính này chia

tập dữ liệu D thành v tập con {D1, D2, ..., Dv} trong đó Dj là tập phần tử dữ liệu có

giá trị của thuộc tính A là ai. Tập con này sẽ tương ứng với một nhánh cây được

phát triển từ nút N trong giải thuật tạo cây quyết định. Trường hợp lý tưởng thì ta

muốn tập con này sẽ có khả năng phân lớp chính xác các phần tử trong nó, hay nói

một cách khác ta muốn tập con này càng đồng nhất (pure) càng tốt, đồng nhất ở đây

có thể hiểu là các phần tử trong trong tập con này đều cùng thuộc về một lớp. Tuy

nhiên trong thực tế thì các tập này thường không đồng nhất (impure) vì nó chứa các

phần tử dữ liệu thuộc về cac lớp khác nhau, do đó chúng ta cần thêm thông tin để

phân lớp chính xác tập con này. Lượng thông tin này được đo bởi:

(2.2)

Trong đó được dùng làm trọng số của tập con DJ. Giá trị của infoA(D) là

lượng thông tin kỳ vọng để phân lớp một phần tử dữ liệu trong D dựa trên việc chia

dữ liệu bằng thuộc tính A. Giá trị này càng nhỏ thì độ đồng nhất của các tập con

càng cao. Cuối cúng hàm đo độ lợi thông tin được tính bằng công thực:

(2.3)

Giá trị Gain(A) cho chúng ta biết ta được lợi bao nhiều nếu chia dữ liệu theo

thuộc tính A. Giá trị này càng lớn thì càng tốt, do đó thuộc tính nào có giá trị Gian

() lớn nhất sẽ được chọn để phân nhánh trong quá trình xây dựng cây quyết định.

Để minh họa cho độ đo này ta tính toán một thuộc tính trên tập dữ liệu ở bảng

2.1. Trong bảng này trường cuối cùng là nhãn của dữ liệu (Mua máy tính), nó có 2

giá trị, do đó số lớp ở đây là 2. Có 9 phần tử dữ liệu có nhãn là yes và 5 phần tử dữ

liệu có nhãn là no, do đó theo công thức (1.2) ta có:

Tiếp đến theo công thức (2.2) ta tính giá trị của hàm cho thuộc tính tuổi

(age):

Tiếp đến theo công thức (2.3) ta có độ lời thông tin theo thuộc tính tuổi sẽ là:

Tường tự ta có thể tính được giá trị độ lợi thông tin cho các thuộc tính thu

nhập (income), sinnh viên (student) và đành giá tín dụng (credit_rating)

Gain(income)= 0.092 bits, Gain (student)= 0.151 bits và Gain (credit rating) = 0.048

bits. Từ kết quả này, chúng ta thấy thuộc tính tuổi sẽ được chọn để phan chia dữ

liệu. Lặp lại quá trình xây dựng cây tương ứng với các tập con dữ liệu (đã bỏ đi

thuộc tính tuổi) ta sẽ thu được cây quyết định như hình (2.6)

Hình 2.7: Thuộc tính tuổi có thông tin thu được cao nhất

2.2.2 Tỉ số độ lợi

Độ đo độ lợi thông tin hoạt động không tốt trong trường hợp một thuộc tính

có nhiều giá trị. Vì dụ, thuộc tính mã sản phẩm (product_ID), hay mã giao dịch sẽ

có rất nhiều giá trị. Đặc biệt nữa, khi chia dữ liệu theo thuộc tính này thì mỗi một

tập con dữ liệu sẽ chỉ có tương ứng một bản ghi, do đó các tập con này là hoàn toàn

đồng nhất. Hay nói một cách khác, lượng thông tin cần để phân lớp tập dữ liệu D

dưa trên cách phân chia dữ liệu trên thuộc tính này InfoProduct_ID(D)= 0. Và giá trị độ

lợi thông tin sẽ đạt giá tri tối đa:

Gian (Product_ID) = Info(D)- InfoProduct_ID(D)=Info(D)

Nhưng rõ ràng việc phân lớp dựa trên thuộc tính này là vô nghĩa.

Do đó, trong giải thuật C4.5 (hậu duệ của giải thuật ID3) tác giả đã đề xuất

sử dụng một độ đo mới gọi là tỉ số độ lợi (gain ratio) để cố tránh nhược điểm trên.

Hàm này sử dụng một phương pháp chuẩn hóa độ lợi thông tin bằng cách sử dụng

giá trị phân chia thông tin (split information) được định nghĩa tương tự như hàm

Info(D) như sau:

(2.4)

Giá trị này biểu diễn thông tin tiềm năng được sinh ra thông qua việc chia tập

dữ liệu huấn luyện D thành v tập con tương ứng với các giá trị của thuộc tính A.

Chú ý rằng với mỗi giá trị của thuộc tính j, nó tính toán số lượng các phần tử có giá

trị thuộc tính A là j trên tổng số lượng các phần tử của D. Đây là điểm khác so với

độ lợi thông tin, do đó công thức tính tỉ số đọ lợi sẽ là:

(2.5)

Trong đó, hàm SplitInfoA (D) được viết ngắn gọn thành SplitInfo(A). Dựa

trên độ đo này, các thuộc tính có giá trị tỉ số độ lợi cao sẽ được chọn làm thuộc tính

phân chia dữ liệu. Có một chú ý rằng, nếu hàm SplitInfo(A)=0 thì công thức trên

không dùng được, do đó có thêm rằng bược để tránh trường hợp này. Cụ thể giá trị

độ lợi thông tin của thuộc tính được chọn phải đủ lớn, ít nhất là lớn hơn giá trị trung

bình độ lợi thông tin của tất cả các thuộc tính.

Trở lại bảng dữ liệu (2.1), ta tính tỉ số độ lợi cho thuộc tính thu nhập

(Income). Đầu tiên ta sử dụng công thức (2.4) để tính SplitInfoincome(D)

Do đó

2.2.3 Chỉ số Gini

Đây là độ đo được sử dụng trong giải thuật CART, chỉ số Gini đo độ không

đồng nhất của một tập dữ liệu D bằng công thức:

(2.6)

Trong đó, pi có ý nghĩa giống như công thức (2.1); m là số lượng lớp trong

D. Chỉ số Gini quan tâm đến trường hợp ta sẽ sử dụng một thuộc tính và chia dữ

liệu thành 2 nửa. Để đơn giản, ta xét trường hợp thuộc tính A có v giá trị khác nhau

{a1, a2, ..., av} xuất hiện trong D. Để xác định cách phân chia tốt nhất ta xét toán bộ

các tập con của D phân chia theo của giá trị A. Do đó nếu A có v giá tri khác nhau

thì ta sẽ có 2v tập con của D .Vì dụ thuộc tính thu nhập (income) có 3 giá trị {low,

medium, high} thì các tập con có thể sẽ là {low, medium, high}, {low, medium},

{medium, high}, {low, high}, {low}, {medium}, {high}, và tập rỗng {}. Chúng ta

không xét 2 tập con {low, medium, high} và {} vì nó không chia dữ liệu ra 2 tập, do

đó ta có tổng số 2v -2 cách để chia tập dữ liệu D thành 2 tập con dựa trên dựa trên

thuộc tính A. Khi chia tập dữ liệu D thành 2 nửa D1 và D2 chúng ta xem xét độ

không đồng nhất (impurity) của dữ liệu trong 2 nửa này:

(2.7)

Trong trường hợp thuộc tính A có giá trị liên tục thì chúng ta phải xác định các

điểm (giá trị) split_point đẻ chia tập dữ liệu D thành 2 tập con. Các điểm split_point

có thể lấy là giá trị trung bình giữa 2 giá trị gần nhau nhất của thuộc tính A. Khi xác

định được chia dữ liệu split_point ta có thể chia dữ liệu D thành 2 tập dữ liệu con là

và D1 và D2 sao cho:

trong đó vA là giá trị của thuộc tính A. Khi đó ta định nghĩa độ giảm của độ bất đồng

nhất của dữ liệu khi chia dữ liệu thành 2 tập con theo thuộc tính A:

(2.8)

Trong đó cách phân chia nào mà tạo ra 2 tập con có giá trị lớn nhất

(hay GiniA(D) nhỏ nhất) sẽ được chọn. tuy nhiên trong trường hợp này khác với các

độ đo trước, ta cần kết hợp cách phân chia hay giá trị điểm phân chia (split point)

với thuộc tính để dúng làm đều kiện nhánh cây quyết định.

Quy lại cơ sở dữ liệu khách hàng ở bảng (2.1), ta có 9 phần tử dữ liệu thuộc

vào lớp Cyes và 5 phần tử dữ liệu thuộc tính vào lớp Cno do đó chỉ số Gini(D) đô độ

bất đồng nhất trong D là:

Tiếp theo ta xét thuộc tính thu nhập (income), bắt đầu bằng cách phân chia

{low, medium} và {high}. Với cách phân chia này thì ta có tập D1 chứa 10 phần tử

dữ liệu có thuộc tính income có giá trị nằm trong tập {low, medium} và tập D2 chứa

4 phần tử có giá trị income= high. Khi đó chỉ số Gini sẽ được tính toán là:

Tương tự, giá trị Gini cho cách chia {medium, high} và {low} là 0.3; giá trị

Gini cho cách chia {low, high} và {medium} là 0,315. Do đó cách chia {medium,

high} và {low} sẽ được chọn làm điều kiện để phân nhánh cây quyết định vì nó cho

ta giá trị Gini nhỏ nhất. Với thuộc tính tuổi (age) thì cách phân chia {youth, senior}

và {middle_age} cho giá trị tốt nhất là 0.375. Với thuộc tính student và

credit_rating đều là giá trị nhị phân nên chúng ta chỉ có một cách chia duy nhất, giá

trị Gini của 2 thuộc tính này lần lượt là 0.367 và 0.429. Qua kết quả này ta thấy

thuộc tính income cho giá trị Gini nhỏ nhất do đó nó sẽ được chọn để làm điều kiện

phân nhánh cây quyết định, khác với 2 độ đo ở trên chọn thuộc tính tuổi làm điều

kiện phân nhánh đầu tiên. Một điều chú ý là vời độ đo này thì ta không chỉ quan tâm

đến thuộc tính dùng để phân chia tập dữ liệu mà còn quan tâm đến cách chia dữ liệu

theo thuộc tính đó.

2.2.4 Tỉa cây quyết định

Sau khi cây được xây dựng, nó có thể chứa nhiều nhánh phản ánh sự bất

thường trong dư liệu huấn luyện: có thể là các trường hợp ngoại lệ, dữ liệu lỗi hay

là dữ liệu nhiều. Hiện tương trên cũng gây ra hệ quả là xảy ra hiện tượng cây thu

được quá phù hợp dữ liệu (overfitting). Để giải quyết vấn đề này phương pháp tỉa

cây (tree pruning) được đề xuất. Phương pháp tỉa cây vầ bản chất là loại bỏ các

nhánh ít tin cây nhất, do đó ta không những thu được cây có khả năng phân lớp tốt

hơn mà còn làm cho cây cô đọng hơn và tốc đọ xử lý sẽ nhánh hơn. Phương pháp

tỉa cây được chia thành 2 loại: tỉa trước (prepruning) cây và tỉa sau (postpruning).

Trong phương pháp tỉa cây trước, cây sẽ được tỉa ngay trong giai đoạn xây dựng

cây, nó sẽ tương ứng với các điều kiện để dừng phát triển một nhánh nào đó. Còn

phương pháp tỉa cây sau lại xử lý cây sau khi nó đã được xây dựng hoàn chính.

2.3 Phân lớp dữ liệu Bayesian

Bộ phân lớp Bayesian là một giải thuật thuộc lớp giải thuật phân lớp thống kê,

nó có thể dữ đoán xác suất của một phần tử dữ liệu thuộc vào một lớp là bao nhiều.

Phân lớp Bayesian dựa trên định lý Bayes (định lý được đặt theo then tác giả của nó

là Thomas Bayes). Một classifier đơn giản của Bayesian đó là Naive Bayes, so với

việc thực thi của classifier cây quyết định và mạng nơron, classifier Bayesian đưa ra

độ chính xác cao và nhanh khi áp dụng vào các cơ sở dữ liệu lớn.

Mục 2.3.1 nói lại các khái niệm xác suất cơ bản và định lý Bayes. Sau đó ta sẽ

xem phân lớp Naïve Bayes trong 2.3.2

2.3.1 Định lý Bayes

Gọi X là một chứng cứ (evidience) (trong bài toán phân lớp thì X sẽ là một

phần tử đữ liệu), Y là một giả thiết nào để cho X thuộc về một lớp một lớp C nào đó.

Trong bài toán phân lớp chúng ta muốn xác định giá trị P (Y |X) là xác suất để giả

thiết Y là đúng với chứng cứ X thuộc vào lớp C với điều khiện ta biết các thông tin

mô tả X. P (Y |X) là một xác suất hậu nghiệm (posterior probability hay posteriori

probability) của Y với điều kiện X.

Giả sử tập dữ liệu khách hàng của chúng ta được mô tả bởi các thuộc tính

tuổi và thu nhập, và một khách hàng X có tuổi là 35 và thu nhập là $40.000. Giả sử

Y là giả thiết khách hàng đó sẽ mua máy tính, thì P (Y /X) phảm ánh xác suất người

dùng X sẽ mua máy tính, thì P (Y |X) phản ánh xác suất người dùng X sẽ mua máy

tính với điều kiện ta biết tuổi và thu nhập của người đó.

Ngược lại P(Y) là xác suất tiền nghiệm (prior probability hay priori

probability) của Y. Trong ví dụ trên, nó là xác suất một khách hàng sẽ mua máy tính

mà không cần biết các thông tin về tuổi hay thu nhập của họ. Hay nói cách khác,

xác suất này không phụ thuộc vào X. Tương tự P (X |Y) là xác suất của X với điều

kiện Y, nó là một xác hậu nghiệm. Vì dụ, nó là xác suất người dùng X (có tuổi là 35

và thu thập là $40.000) sẽ mua máy tính với điều kiện ta đã biết là người dùng đó sẽ

mua máy tính. Cuối cùng P(X) là xác suất tiền nghiệm cảu X. Trong ví dụ trên, nó

sẽ là xác suất một người trong tập dữ liệu sẽ xó tuổi 34 và thu nhập $40.000. Các

xác suất này sẽ được tính dựa vào định lý Bayes như sau:

(2.9)

Với:

: Xác suất của sử kiện X xảy ra, Không quan tâm đến Y

: Xác suất của sử kiện Y xảy ra, Không quan tâm đến X

: Xác suất (có điều kiện) của sự kiện X xảy ra, nếu biết rằng sự kiện

Y xảy ra

: Xác suất hậu nghiệm của Y nếu biết X

Thuật toán bayes dựa trên định lý Bayes áp dụng cho các bài toán giả định

điều kiện độc lập. Nghĩa là giả định đặc trưng của một lớp xảy ra không ảnh hưởng

hay phụ thuộc vào đặc trưng của lớp khác

2.3.2 Phân lớp Naïve Bayes

Bộ phân lớp Naïve Bayes hay là bộ phân lớp Bayes đơn giản (simple Bayes

classifier) hoạt động như sau:

1) Gọi D là tâp dữ liệu huấn luyện, trong đó mỗi phần tử dữ liệu X được biểu

diễn bằng một vector chứa n giá trị thuộc tính A1, A2, ..., An, X= {x1, x2, ..., xn}.

2) Giả sử có m lớp C1, C2, ..., Cm; Cho một phần tử dữ liệu X, bộ phân lớp sẽ

gán nhãn cho X là lớp có xác suất hậu nghiệm lớn nhất. Cụ thể, bộ phân lớp Bayes

sẽ dự đoán X thuộc vào lớp Ci nếu và chỉ nếu:

với (2.10)

Ci: Phân lớp i, với i= {1, 2 …, m}

Giá trị này sẽ được tình dựa vào định lý Bayes:

(2.11)

3) Để tìm giá trị xác suất lớn nhất, ta nhận thấy trong công thức (2.10) thì giá trị

P(X) là giống nhau với mọi lớp nên ta không cần tìm. Do đó ta chỉ cần tìm giá trị

lớn nhất của P(X|Ci) x P(Ci). chú ý rằng P(Ci) được ước lượng bằng công thức

, trong đó Di là tập các phần tử dữ liệu thuộc vào lớp Ci. nếu xác suất

tiền nghiệm P(Ci) cũng không xác định được thì ta coi chúng bằng nhau P(C1) =

P(C2) = ...=P(Cm), khi đó ta chỉ cần tìm giá trị P(X|Ci) lớn nhất.

4) Khi số lượng các thuộc tính mô tả dữ liệu là lớn thì chi phí tính toán P(X|Ci)

là rất lớn, do đó để làm giảm độ phức tạp, giải thuật Naïve Bayes giả thiết các thuộc

tính là độc lập nhau hay không có sự phụ thuộc nào giữa các thuộc tính. Khi đó ta

có thể tính:

(2.12)

Khi đó xác suất xảy ra của một điều kiện x mới là

(2.13)

Trong đó:

P(Ci): được tính dựa trên tần suất xuất hiện tài liệu trong tập huấn luyện.

P(xk|Ci): được tính từ những tập thuộc tính đã được tính trong quá trình huấn

luyện

Bước tính thuật toán Bayes:

Bước 1: Huấn luyện tập dữ liệu:

Tính xác suất P(Ci)

Tính xác suất P(xk|Ci)

Bước 2: Lớp của giá trị mới được gắn cho lớp có xác suất lớn nhật

theo công thức:

2.4. Phân lớp dữ liệu sử dụng máy hỗ trợ vector (SVM)

Support vector machine là một khái niệm trong thống kê và khoa học máy

tính cho một tập hợp các phương pháp học có giám sát liên quan đến nhau để phân

loại và phân tích hồi quy.

Nguyên lý cơ bản của SVM là tìm một siêu phẳng phân hoạch tối ưu cho

phép chia các điểm trong không gian nhiều chiều thành 2 lớp nằm ở 2 phía chưa

siêu phẳng.

SVM dạng chuẩn nhận dữ liệu vào và phân loại chúng vào hai lớp khác

nhau. Do đó SVM là một thuật toán phân loại nhị phân.

Hình 2.8 :Các điểm trong không gian D chiều

Cho trước n điểm trong không gian D chiều (mỗi điểm thuộc vào một lớp kí

hiệu là +1 hoặc -1), mục đích của giải thuật SVM là tìm một siêu phẳng phân hoạch

tối ưu cho phép chia các điểm này thành hai phần sao cho các điểm cùng một lớp

nằm về một phía với siêu phẳng này.

(2.14)

Mỗi siêu phẳng đều có thể được viết dưới dạng một tập hợp các điểm x thỏa

mãn:

(2.15)

Công thức trên là tích vô hướng với vector pháp tuyến của siêu phẳng (w) và

b đóng vai trò là tham số.

Ta cần chọn w và b để cực đại hóa lề, hay khoảng cách giữa hai siêu mặt

song song ở xa nhau nhất có thể trong khi vẫn phân chia được dữ liệu

Các siêu mặt ấy được xác định bằng:

(2.16)

(2.17)

Hình 2.9: Siêu phẳng phân lớp các điểm trong không gian

Ví dụ: Giả sử ta có một tập được gán nhãn (+1): {(3,1), (3, -1), (6, 1), (6, -1)} Và

tập các điểm được gán nhãn âm (-1): {(1, 0), (0, 1), (0, -1), (-1, 0)} trong mặt phẳng

R+

Hình 2.10: Đồ thị biểu diễn các điểm trong mặt phẳng R+

Ta sử dụng SVM để phân biệt hai lớp (+1 và -1). Bởi vì dữ liệu được chia

tách một cách tuyến tính, nên chúng ta sử dụng một hàm tuyến tính để phân tách 2

lớp. Theo quan sát, ta chọn ra ba vector hỗ trợ để thực thi các phép toán nhằm tìm ra

mặt phẳng phân tách tối ưu nhất:

{s1 = (1,0), s2 = (3,1), s3 = (3, -1)}

Hình 2.11: Các điểm lựa chọn cho siêu phẳng

Các vector hỗ trợ được tăng cường bằng cách thêm 1. Tức là s1 = (1,0), thì

nósẽ được chuyển đổi thành s = (1, 0, 1). Theo kiến trúc SVM, Nhiệm vụ là tìm ra

những giá trị αi.

(2.18)

(2.19)

(2.20)

Hình 2.12: Kiến trúc mô hình SVM

Do sử dụng SVM tuyến tính nên hàm Φ () - dùng để chuyển đổi vector

từ không gia dữ liệu đầu vào sang không gian đặc trưng – sẽ bằngΦ = () I. Biểu thức

trên được viết lại như sau:

(2.21)

(2.22)

(2.23)

Rút gọn biểu thức thông qua tính tích vô hướng của các vector:

(2.24)

(2.25)

(2.26)

Giải hệ phương trình trên có: α1 = -3.5, α2 = 0.75, α3 = 0.75. Tiếp đến tính

trọng số ω thông qua công thức:

Siêu phẳng phân chia hai lớp đó là: y = wx + b với w = (1, 0) và b = -2

Hình 2.13: Đồ thị biểu diễn siêu phẳng tìm được

2.4.1 Phân lớp đa lớp với SVM

Thuật toán SVM trình bày ở trên chỉ hoạt động với dữ liệu có 2 lớp, trong

thực tế số lượng lớp của dữ liệu có thể rất lớn. Rất may là cũng có giải pháp để mở

rộng SVM cho bài toán có nhiều lớp.

Bài toán phân lớp câu hỏi yêu cầu một bộ phân lớp đa lớp do đó cần cải tiến

SVM cơ bản (phân lớp nhị phân) thành bộ phân lớp đa lớp.

Một trong những phương pháp cải tiến đó là sử dụng thuật toán 1-against-all

[Hau02, Milgram06]. Ý tưởng cơ bản là chuyển bài toán phân lớp nhiều lớp thành

nhiều bài toán phân lớp nhị phân như sau:

• Giả sử tập dữ liệu mẫu (x1, y1), ..., (xm, ym) với xi là một vector n chiều và

là nhãn lớp được gán cho vector xi (có m nhãn lớp khác nhau)

• Biến đổi tập Y ban đầu thành m tập có hai lớp con

• Áp dụng SVM phân lớp nhị phân cơ bản với m tâp Zi để xây dựng siêu

phẳng cho phân lớp này. Như vậy ta sẽ có m bộ phân lớp nhị phân.

Bộ phân lớp với sự kết hợp của m bộ phân lớp trên được gọi là bộ phân lớp

đa lớp mở rộng với SVM

2.5. Phân lớp dữ liệu với Random Forest (rừng ngẫu nhiên)

Tiếp cận Random Forest (rừng ngẫu nhiên) do (Breiman, 2001) đưa ra là một

trong những phương pháp tập hợp mô hình thành công nhất. Giải thuật random

forest tạo ra một tập hợp các cây quyết định (Breiman et al., 1984), (Quinlan, 1993)

không cắt nhánh, mỗi cây được xây dựng trên tập mẫu bootstrap (lấy mẫu có hoàn

lại từ tập học), tại mỗi nút phân hoạch tốt nhất được thực hiện từ việc chọn ngẫu

nhiên một tập con các thuộc tính. Lỗi tổng quát của rừng phụ thuộc vào độ chính

xác của từng cây thành viên trong rừng và sự phụ thuộc lẫn nhau giữa các cây thành

viên. Giải thuật random forest xây dựng cây không cắt nhánh nhằm giữ cho thành

phần lỗi bias thấp (thành phần lỗi bias là thành phần lỗi của giải thuật học, nó độc

lập với tập dữ liệu học) và dùng tính ngẫu nhiên để điều khiển tính tương quan thấp

giữa các cây trong rừng. Tiếp cận random forest cho độ chính xác cao khi so sánh

với các thuật toán học có giám sát hiện nay, chịu đựng nhiễu tốt. Như trình bày

trong (Breiman, 2001), random forest học nhanh, chịu đựng nhiễu tốt và không bị

tình trạng học vẹt. Giải thuật random forest sinh ra mô hình có độ chính xác cao đáp

ứng được yêu cầu thực tiễn cho vấn đề phân loại, hồi quy.

Rừng ngẫu nhiên (được mô tả trong hình 2.14) tạo ra một tập hợp các cây

quyết định không cắt nhánh, mỗi cây được xây dựng trên tập mẫu bootstrap (lấy

mẫu ngẫu nhiên có hoàn lại), tại mỗi nút phân hoạch tốt nhất được thực hiện từ việc

chọn ngẫu nhiên một tập con các thuộc tính.

Lỗi tổng quát của rừng phụ thuộc vào độ chính xác của từng cây thành viên

trong rừng và sự phụ thuộc lẫn nhau giữa các cây thành viên. Giải thuật rừng ngẫu

nhiên cho độ chính xác cao khi so sánh với các thuật toán học có giám sát hiện nay,

chịu đựng nhiều tốt

Với bài toán phân lớp: cho một tập dữ liệu huấn luyện

với , trong đó: gọi là lớp, giả sử có C nhãn lớp là vector M chiều,

. Ý tưởng chính của mô hình RF là lựa chọn ngẫu nhiên 2 lần

(ngẫu nhiện mẫu và ngẫu nhiện thuộc tính) trong suốt quá trình xây dựng cây gồm

có 3 pha như sau:

Pha 1: Từ dữ liệu ban đầu D, sử dụng kỹ thuật boostrap (lấy mẫu ngẫu nhiên

có hoàn lại) để tạo ra t tập dữ liệu con S = {𝑆1, 𝑆2..., 𝑆t }.

Pha 2: Trên mỗi tập dữ liệu Sj, xây dựng một cây quyết định ℎ𝑗. Mô hình

. Thay vì sử dụng tất cả các biến là biến ứng Rừng ngẫu nhiên là mô hình

cử để lựa chọn điểm chia tốt nhất, tại mỗi nút RF chọn ngẫu nhiên một không gian

tập con M’ thuộc tính từ M thuộc tính ban đầu (M’<

định trong mô hình RF là cây quyết định không cắt nhánh.

Pha 3: RF dự đoán nhãn lớp của phần tử mới đến bằng chiến lược bình chọn

số đông của các cây quyết định.

Ưu điểm của RF là xây dựng cây không thực hiện việc cắt nhánh từ các tập

dữ liệu con khác nhau, do đó thu được những cây với lỗi bias thấp. Bên cạnh đó,

mối tương quan giữa các cây quyết định cũng được giảm xuống nhờ việc xây dựng

các không gian con thuộc tính một cách ngẫu nhiên. Sự chính xác của RF phụ thuộc

vào chất lượng dự đoán của các cây quyết định và mức độ tương quan giữa các cây

trong rừng.

Trong quá trình xây dựng các cây quyết định, RF phát triển các nút con từ

một nút cha dựa trên việc đánh giá chỉ số Gini của một không gian con M’ các

thuộc tính được chọn ngẫu nhiên từ không gian thuộc tính ban đầu. Thuộc tính được

chọn để tách nút t là thuộc tính có điểm cắt làm cực tiểu độ hỗn tạp của các tập mẫu

sau khi chia. Công thức tính chỉ số Gini cho nút t như sau:

(2.27)

trong đó là tần suất hiện của lớp

Trong nút t

Hình 2.14: Mô hình rừng ngẫu nhiên

Gọi s là một giá trị của thuộc tính 𝑋j. Giả sử tách nút t thành 2 nút con: nút

trái 𝑡L và nút phải 𝑡R tại s. Tùy thuộc vào 𝑋j ≤ s hoặc 𝑋j> s ta có 2 nút con:

𝑡L = {𝑋j ∈ 𝑡, 𝑋j ≤ 𝑠} 𝑣à 𝑡R = {𝑋j ∈ 𝑡, 𝑋j > 𝑠}

Khi đó, tổng độ đo chỉ số Gini của 2 nút 𝑡L và 𝑡R sau khi dùng thuộc tính 𝑋j

tách nút t tại s là:

(2.28)

Để đạt được điểm chia tốt, tại mỗi nút RF sẽ tìm tất cả các giá trị phân biệt

của tất cả n’ thuộc tính để tìm ra điểm phân tách nút t (điểm s có độ đo Gini (s, t)

nhỏ nhất). Thuộc tính chứa điểm phân tách nút t được gọi là thuộc tính tách nút t.

Gọi 𝐼𝑆k (𝑋j), 𝐼𝑆x lần lượt là độ đo sự quan trọng của thuộc tính 𝑋j trong một

cây quyết định Tk (k=1÷m) và trong một rừng ngẫu nhiên. Công thức tính 𝐼𝑆x (𝑋j)

và 𝐼𝑆xj như sau:

(2.29)

(2.30)

Chuẩn hóa min - max để chuyển độ đo sự quan trọng thuộc tính về đoạn [0,1],

theo công thức (2.31):

(2.31)

Kết quả dự đoán của mô hình rừng ngẫu nhiên là kết hợp kết quả của một số

lượng lớn những cây quyết định có mối tương quan thấp (do RF lấy ngẫu nhiên mẫu

và xây 33 dựng các không gian con thuộc tính cũng ngẫu nhiên) nên RF đạt được cả

độ lệch thấp và phương sai thấp. Trong thực tế RF đã trở thành một công cụ tin cậy

cho phân tích dữ liệu chiều cao. Tuy nhiên, tiếp cận cài đặt ban đầu, RF chỉ cho kết

quả tốt trên các dữ liệu có số chiều vừa phải và giảm đáng kể hiệu năng khi xử lý dữ

liệu có số rất chiều cao cỡ hàng nghìn thuộc tính, nhiều nhiễu, dung lượng mẫu ít

(bài toán phân tích dữ liệu gene là một trường hợp cụ thể). Sự chính xác của RF phụ

thuộc vào chất lượng dự đoán của các cây quyết định và mức độ tương quan giữa

các cây quyết định. Chính vì vậy, đã có nhiều đề xuất cho việc cải tiến mô hình

Rừng ngẫu nhiên. Dưới đây sẽ trình bày tóm tắt một số phương pháp cải tiến mô

hình Rừng ngẫu nhiên.

2.6 Một số phương pháp phân lớp dữ liệu khác

2.6.1 Thuật toán phân lớp k-NN

Classifier k-Nearest Neighbors dựa trên việc học bằng sự giống nhau. Các

mẫu huấn luyện được mô tả bởi các thuộc tính số n - chiều. Mỗi mẫu đại diện cho

một điểm trong một không gian n - chiều. Vì vậy tất cả các mẫu huấn luyện được

lưu trữ trong không gian mẫu n - chiều. Khi có một mẫu chưa biết cho trước thì

classifier k-Nearest Neighbors sẽ tìm kiếm trong không gian mẫu k mẫu huấn luyện

gần mẫu chưa biết đó nhất. k mẫu huấn luyện này là k "k-Nearest Neighbors " của

mẫu chưa biết. "Độ gần" được định nghĩa dưới dạng khoảng cách Euclidean, tại đó

khoảng cách Euclidean giữa hai điểm X1 = (𝑥11, 𝑥12, ..., 𝑥1n) và X2 = (𝑥21, 𝑥22, ..., 𝑥2n)

là:

(2.32)

Mẫu chưa biết được phân vào lớp phổ biến nhất trong số k láng giềng gần nhất

của nó. Khi k = 1 thì mẫu chưa biết được ấn định lớp của mẫu huấn luyện gần nhất

với nó trong không gian mẫu.

Classifier k-Nearest Neighbors dựa trên khoảng cách, từ đó chúng lưu trữ tất

cả các mẫu huấn luyện. Các kỹ thuật đánh chỉ số hiệu quả được dùng khi số lượng

các mẫu huấn luyện là rất lớn. Không giống như cây quyết định quy nạp và lan

truyền ngược, classifier k-Nearest Neighbors ấn định các trọng số bằng nhau cho

từng thuộc tính. Điều này có thể là nguyên nhân gây nhập nhằng khi có nhiều thuộc

tính không thích hợp trong dữ liệu. Classifier k-Nearest Neighbors cũng được dùng

để dự đoán, tức là trả lại một dự đoán giá trị thực cho một mẫu chưa biết cho trước.

Lúc này, classifier trả lại giá trị trung bình của các nhãn giá trị thực kết hợp với k-

láng giềng gần nhất của mẫu chưa biết đó

2.7 Đánh giá mô hình phân lớp dữ liệu

Trong thực tế, ta cần áp dụng nhiều thuật toán Machine learning để chọn ra

được mô hình phù hợp nhất cho bài toán của mình. Vấn đề đặt ra, làm thế nào để

đánh giá và chọn ra các mô hình. Ngoài thuật toán học máy, sự thực thi của mô hình

có thể phụ thuộc vào các yếu tố khác như sự phân bố của các lớp, chi phí phân loại

sai, kích thước của tập huấn luyện và tập thử nghiệm, độ đo thực thi. Trong bài viết

này, ta sẽ đánh giá thực thi: tập trung vào khả năng dự đoán của mô hình hơn là tốc

độ phân loại hay xây dựng mô hình, khả năng có giãn.

• Confusion matrix

Bảng 2.2: Bảng biểu diễn ma trận nhầm lẫn

Predicted Class

Yes No

Actual Class Yes a b

No c d

Đầu tiên, ta hãy làm quen với confusion matrix (ma trận nhầm lẫn).

Quan sát confusion matrix, ta có các thông tin sau:

− a:TP (true positive) – mẫu mang nhãn dương được phân lớp đúng vào

lớp dương.

− b:FN (false negative) – mẫu mang nhãn dương bị phân lớp sai vào lớp

âm.

− c:FP (false positive) – mẫu mang nhãn âm bị phân lớp sai vào lớp

dương.

− d:TN (true negative) – mẫu mang nhãn âm được phân lớp đúng vào

lớp âm.

• Phương pháp Hold-out

Hình 2.15: Mô hình chia tập dữ liệu Hold-out

Phương pháp Hold-out phân chia tập dữ liệu thành 2 tập độc lập. Ví dụ, tập

huấn luyện (training set) 2/3, tập thử nghiệm (testing set) 1/3 hay 70% và 30%

Phương pháp này thích hợp cho các tập dữ liệu nhỏ. Tuy nhiên, các mẫu có

thể không đại diện cho toàn bộ dữ liệu (thiếu lớp trong tập thử nghiệm).

Ta có thể cải tiến bằng cách dùng phương pháp lấy mẫu sao cho mỗi lớp

được phân bố đều trong cả 2 tập dữ liệu huấn luyện và thử nghiệm. Hay lấy mẫu

ngẫu nhiên: thực hiện holdout k lần và độ chính xác acc(M) = trung bình cộng k giá

trị chính xác.

• Phương pháp Cross validation

Hình 2.16: Mô hình chia tập dữ liệu 5-fold Cross validation

Hay còn gọi là k-fold Cross validation. Phương pháp này phân chia dữ liệu

thành k tập con có cùng kích thước. Tại mỗi vòng lặp sử dụng một tập con là tập

thử nghiệm và các tập con còn lại là tập huấn luyện. Giá trị k thường là = 10. Ta có

thể dùng một trong hai cách:

− Leave-one-out: k=số mẫu trong dữ liệu (dành cho tập dữ liệu nhỏ)

− Stratified cross-validation: dùng phương pháp lấy mẫu để các lớp trong từng

tập con phân bố như trên toàn bộ dữ liệu.

2.8 Tổng kết chương

Chương này trình bày về chi tiết về một số phương pháp và kỹ thuật phân

lớp dữ liệu. Các phương pháp phân lớp sử dụng cây quyết định (Decision Tree),

Naive Bayes, Random Forest (rừng ngẫu nhiên), máy hỗ trợ vector (SVM) và một

số phương pháp phân lớp dữ liệu khác cũng được trình bày chi tiết trong chương

này. Bên cạnh đó, chương này cũng trình bày về 2 phương pháp phổ biến trong việc

đánh giá hiệu năng phân lớp/dự đoán của mô hình như: Hold-out, Cross-validation.

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

3.1 Giới thiệu bài toán phân lớp dữ liệu Mushroom

3.1.1 Giới thiệu về bài toán phân lớp dữ liệu Mushroom

Nấm (Mushroom) có lợi ích cao trong cơ thể con người. Tuy nhiên, không

phải tất cả các loại nấm đều ăn được. Trong khi một số có đặc tính y tế để chữa ung

thư, một số loại nấm khác có thể chứa vi-rút mang bệnh truyền nhiễm.

Trong bài viết luân văn này được thiết lập để nghiên cứu phân lớp các đặc

điểm của nấm hành vi như hình dạng, bề mặt và màu sắc của nắp, mang và thân,

cũng như mùi, dân số và môi trường sống của nấm. Thuật toán phân tích thành phần

chính “ The Principal Component Analysis” (PCA) được sử dụng để chọn các tính

năng tốt nhất cho phân loại thử nghiệm bằng thuật toán Cây quyết định “Decision

Tree”, Naïve Bayes, k-Nearest neighbor, SMV. Phân loại chính xác, hệ số đo và

thời gian thực hiện để phân loại mô hình trên bộ dữ liệu Nấm tiêu chuẩn đã được

đo. Hành vi tính năng mùi “odro” và màu sắc “color” được chọn là tính năng được

xếp hạng cao nhất góp phần phân loại độ chính xác cao.

3.1.2. Thu thập, tiền xử lý và mã hóa dữ liệu

Dữ liệu thực nghiệm Mushroom được thu thập lấy từ Kho lưu trữ học máy

của UCI thu thập https://archive.ics.uci.edu/ml/datasets/mushroom. Chi tiết của bộ dữ

liệu đã thu thập này được cung cấp bởi Bảng 3.1 và bảng 3.2.

Bảng 3.1: Bảng tổng hợp dữ liệu thu thập

Multivariate 8124 Area: Life

22 1987-04-27 Number of Instances: Catessification Number of Attributes:

Data Set Characteristics: Attribute Characteristics: Associated: 493131 Classification Missing Values: Date Denated: Yes Number of Web Hits:

Bảng 3.2: Các tính năng dành cho các dữ liệu nấm

TT Đặc trưng Kiểu dữ liệu Giá trị danh nhĩa

1 cap-shape Nominal bell=b, conical=c, convex=x, flat=f,

knobbed=k, sunken=s

2 cap-surface Nominal fibrous=f, grooves=g, scaly=y, smooth=s

3 cap-color Nominal brown=n, buff=b, cinnamon=c, gray=g,

green=r, pink=p, purple=u, red=e, white=w,

yellow=y

4 bruises? Nominal bruises=t, no=f

5 odor Nominal almond=a, anise=l, creosote=c, fishy=y,

foul=f, musty=m, none=n, pungent=p,

spicy=s

6 gill- Nominal attached=a, descending=d, free=f, notched=n

attachment

7 gill-spacing Nominal close=c, crowded=w, distant=d

8 gill-size Nominal broad=b, narrow=n

9 gill-color Nominal black=k, brown=n, buff=b, chocolate=h,

gray=g, green=r, orange=o, pink=p, purple=u,

red=e, white=w, yellow=y

10 stalk-shape Nominal enlarging=e, tapering=t

11 stalk-root Nominal bulbous=b, club=c, cup=u, equal=e,

rhizomorphs=z, rooted=r, missing=?

12 stalk-surface- Nominal fibrous=f, scaly=y, silky=k, smooth=s

above-ring

13 stalk-surface- Nominal fibrous=f, scaly=y, silky=k, smooth=s

below-ring

14 stalk-color- Nominal brown=n, buff=b, cinnamon=c, gray=g,

above-ring orange=o, pink=p, red=e, white=w, yellow=y

15 stalk-color- Nominal brown=n, buff=b, cinnamon=c, gray=g,

below-ring orange=o, pink=p, red=e, white=w, yellow=y

16 veil-type Nominal partial=p, universal=u

17 veil-color Nominal brown=n, orange=o, white=w, yellow=y

18 ring-number Nominal none=n, one=o, two=t

19 ring-type Nominal cobwebby=c, evanescent=e, flaring=f,

large=l, none=n, pendant=p, sheathing=s,

zone=z

20 spore-print- Nominal black=k, brown=n, buff=b, chocolate=h,

color green=r, orange=o, purple=u, white=w,

yellow=y

21 population Nominal abundant=a, clustered=c, numerous=n,

scattered=s, several=v, solitary=y

22 habitat Nominal grasses=g, leaves=l, meadows=m, paths=p,

urban=u, waste=w, woods=d

23 class Nominal Edible=e, poisonous=p

Đây là bảng tập dữ liệu mô tả các đặc tính vật lý của nấm, cùng với nhãn

phân loại có độc hoặc ăn được (thuộc tính class đầu tiên: p (poisonous) – có độc, e

(edible) – ăn được).

Hình 3.1: Sơ đồ Phương pháp phân lớp nấm (Mushroom).

Bảng 3.3: Mô tả ý nghĩa các giá trị dữ liệu nấm

TT Mô tả ý nghĩa

1 Hình dạng: tràng hoa, hình nón nhô cao, mọc từng dãy trồi lên trủng xuống

2 Bề mặt tai nấm: có thớ, đường khuyết, có lớp vỏ nhẳn bao quanh

3 Màu tai nấm: nâu, vàng sẫm, nâu vàng, xám, xanh lá cây, hồng, đỏ tím, đỏ,

trắng, vàng

4 Vết thâm: có vết thâm, không có

5 Mùi: mùi hạnh nhân, hương cây hồi, creosote, mùi tanh, hôi, mốc, không mùi,

vị cây, có gia vị

6 Là tia dính kèm: dính kèm, hướng xuống tự do, hay đánh dấu theo hình chữ V

7 Khoảng cách giữa các lá tím: dày đặc, chật ních, rải rác

8 Kích thước lá tím: rộng, hẹp

9 Màu sắc lá tia: đen, nâu, vàng sẫm, màu socola, xám, xanh lá cây, cam, hồng,

tím, dỏ, trắng, vàng

10 Hình dạng thân nấm: to lớn, thon dài

11 Loại rễ: hình cũ, chum, hình chén, hay hình dang như nhau, dạng sợi nấm, ăn

sâu vào đất không nhìn thấy

12 Vòng thân trên nấm: có thớ, xếp như vảy cá, mềm mịn trơn nhẳn

13 Vòng thân dưới: có thớ xếp như vảy cá mềm mịn trơn nhẳn

14 Màu vòng thân trên: nâu, vàng sẩm, nâu vàng, xám, cam, hồng, đỏ, trắng,

vàng

15 Màu vòng thân dưới: nâu, vàng sẩm, nâu vàng, xám, cam, hồng, đỏ, trắng,

vàng

16 Loại có mũ: phần, phổ biến

17 Màu của mũ: màu nâu, màu cam, màu trắng, màu vàng

18 Số vòng nấm: không, một, hai

19 Loại vòng nấm: hình mạng nhện, không hiện rỏ, hay hiện rỏ, lớn, không lớn,

hình tua, bao bên ngoài, theo từng vùng

20 Màu mầm: có các màu đen, nâu, da bò, chocolate, xanh la cây, cam, tím,

trắng, vàng

21 Số lượng nấm: phong phú, mọc từng đám, nhiều, lác đác, vài, cô độc

22 Môi trường sống: nấm có thẻ sống ở nơi có cỏ, lá, đồng cỏ, nơi gần đường

mòn, thành thị, nơi có chất bẩn hoặc trong rừng

23 Loại nấm; ăn được, không ăn được

3.1.3. Mô tả sơ lược về dữ liệu

Để nạp dữ liệu mushroom và Weka, ta cần thêm thông tin các thuộc tính nằm

trong file mô tả vào tập dữ liệu, sau đó chuyển đuôi mở rộng thành *.csv

(mushroom.csv).

• Số lượng mẫu: 8124.

• Số lượng thuộc tính: 23.

• Kiểu của mỗi thuộc tính: nomial.

Hình 3.2 : Load Mushroom data

3.2 Giới thiệu về công cụ Weka, cấu hình và ứng dụng phân lớp Mushroom

WEKA (Waikato Environment for Knowledge Analysis) là một phần mềm

khai thác dữ liệu, thuộc dự án của đại học Waikato New Zealand, phần mềm viết

bằng Java, phục vụ lĩnh vực học máy và khai phá dữ liệu.

Chúng ta có thể tải về từ địa chỉ: https://www.cs.waikato.ac.nz/ml/weka/

Hình 3.3: Giao diên ban đầu Phần mềm WEKA

Các tính năng chính:

− Một tập các công cụ tiền xử lý dữ liệu, các giải thuật học máy, khai phá dữ

liệu, và các phương pháp thí nghiệm đánh giá

− Giao diện đồ họa (gồm cả tính năng hiển thị hóa dữ liệu)

− Môi trường cho phép so sánh các giải thuật học máy và khai phá dữ liệu

Các môi trường chình:

− Simple CLI

Giao diện đơn giản kiểu dòng lệnh (như MS-DOS)

− Explorer (trong luân văn chúng ta sẽ chủ yếu sử dụng môi trường này!)

Môi trường cho phép sử dụng tất cả các khả năng của WEKA để khám phá

dữ liệu

− Experimenter

Môi trường cho phép tiến hành các thí nghiệm và thực hiện các kiểm tra

thống kê (statistical tests) giữa các mô hình học máy

− KnowledgeFlow

Môi trường cho phép bạn tương tác đồ họa kiểu kéo/thả để thiết kế các bước

(các thành phần) của một thí nghiệm

3.2.1 Môi trường Explorer

Hình 3.4: Giao diên của WEKA Explorer

− Preprocess: Để chọn và thay đổi (xử lý) dữ liệu làm việc

− Classify: Để huấn luyện và kiểm tra các mô hình học máy (phân loại, hoặc

hồi q y uy/dự đoán)

− Cluster: Để học các nhóm từ dữ liệu (phân cụm)

− Associate: Để khám phá các luật kết hợp từ dữ liệu

− Select attributes: Để xác định và lựa chọn các thuộc tính liên quan (quan

trọng) nhất của dữ liệu

− Visualize: Để xem (hiển thị) biểu đồ tương tác 2 chiều đối với dữ liệu

3.2.2 Khuôn dạng của tập dữ liệu

− WEKA chỉ làm việc với các tập tin văn bản (text) có khuôn dạng ARFF

(Attribute-Relation File Format)

− Ví dụ của một tập dữ liệu

Hình 3.5: Biểu diễn tập dữ liệu weather trong tập tin văn bản(text)

3.2.3 Tiền xử lý dữ liệu

− Dữ liệu có thể được nhập vào (imported) từ một tập tin có khuôn dạng:

ARFF, CSV

− Dữ liệu cũng có thể được đọc vào từ một địa chỉ URL, hoặc từ một cơ sở dữ

liệu thông qua JDBC

− Các công cụ tiền xử lý dữ liệu của WEKA được gọi là filters

• Rời rạc hóa (Discretization)

• Lấy mẫu (Re-sampling)

• Lựa chọn thuộc tính (Attribute selection)

• Chuyển đổi (Transforming) và kết hợp (Combining) các thuộc tính

• …

3.2.4 Phân tích chức năng phân lớp (Classify)

Các bước thực hiện:

Đọc dữ liệu vào chương trình Weka

• Bước 1: Tại tab Preprocess, chọn tập dữ liệu và thực hiện tiền xử lý dữ liệu

Chọn tab Classify để phân lớp

Hình 3.6: Biểu diễn đọc dữ liệu vào chương trình Weka

Hình 3.7: Biểu diễn chọn tab Classify để phân lớp

Chọn thuật toán và điều chính tham số (nếu có)

• Bước 2: Chọn thuật toán phân lớp và xác định tham số

Hình 3.8: Biểu diễn chọn thuật toán phân lớp và xác định tham số

• Bước 3: Chọn kiểu test, và tập dữ liệu test nếu cần

Chọn kiểu test

Hình 3.9: Biểu diễn chọn kiểu test

Sau khi chúng ta chọn tập dữ liệu, thuât toán phân và xác định tham

số, chọn kiểu test, và tập dữ liệu test nếu cần chúng ta chạy thuật toán phân

Chạy thuật toán phân lớp

lớp.

Hình 3.10: Chạy thuật toán phân lớp

Bảng lưu thông tin

• Bước 4: Tiến hành phân lớp dữ liệu

Hình 3.11: Bảng lưu thông tin

Bảng kết quả

Nhật ki hệ thống

• Bước 5: Ghi nhận kết quả

Hình 3.12: Bảng kết quả sau chạy thuật toán phân lớp

3.2.5 Mô tả chức năng phân lớp (Classify)

Phân tích kết quả: Trong hình 3.7 trên là màn hình kết quả biểu diễn cho

chúng ta xem xét kết quả sau khi chạy:

• Running Information: là thông tin về mô hình học, tên quan hệ, số mẫu,

Thuật toán sử dụng

tên quan hệ

số mẫu

thuộc tính

kiểu test

thuộc tính và kiểu test

Hình 3.13: Giải thích Running Information

• Classifier model (full training set): cho biết mô hình phân lớp được xây dựng

Thuật toán Bayes

Kết quả sau khi chạy thuật toán Naïve bayes của các thuộc tính

Thời gian xây dựng mô hình

dựa trên cả tập huấn luyện

Hình 3.14: Giải thích Classifier model (full training set)

• Tổng kết: Số liệu thống kế cho biết độ chính xác của bộ phân lớp, theo một

Đánh giá tập dữ liệu

Mẫu phân lớp đúng

Mẫu phân lớp sai

Tối đa lỗi

kiểu test cụ thể

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

• Độ chính xác chi tiết cho từng phân lớp

Hình 3.16: Xem độ chính xác chi tiết cho từng phân lớp

• Confusion matrix: cho biết bao nhiêu mẫu được gán vào từng lớp. Các phần

tử của ma trận thể hiện số mẫu test có lớp thật sự là dòng và lớp dự doạn là

cột

Hình 3.17: Confusion matrix của bộ phân lớp dữ liêu Mushroom

3.3 Áp dụng các phương pháp phân lớp trên tập dữ liệu Mushroom

Trong luân văn này, ta sẽ áp dụng các phương pháp phân lớp (classification)

lên tập dữ liệu Mushroom. Đây là tập dữ liệu mô tả các đặc tính vật lý của nấm,

cùng với nhãn phân loại có độc hoặc ăn được. Các thuật toán được sử dụng gồm:

Naive Bayes, Nearest neighbor, Support Vector Machines, Decision tree (J48).

Để dễ tiếp cận, các phương pháp được thực hiện với Weka. Mô hình phân

lớp dự đoán đề xuất trong đề tài này được hiển thị chi tiết qua hình dưới đây:

Hình 3.18: Sơ đồ tổng thể Mô hình phân lớp dự đoán nấm (mushroom)

3.3.1 Thực hiện phân lớp bằng thuật toán Naive Bayes

Kịch bản 1: thực nghiệm huấn luyện trong chế độ phân lớp Percentage split

để xác định tỉ lệ phân chia, trong thực nghiệm này tôi xác định tỉ lệ là 70%, có nghĩa

là chia 70% tâp huấn luyện (tập train), 30% tập kiểm tra (tập test). Để đạt hiệu quả

phân lớp như sau:

1) Nhấp vào nút “Choose” Lựa chọn và chọn Tập tin “NaiveBayes” trực tuyến

trong nhóm “Bay Bayes”.

2) Nhấp vào tên của thuật toán để xem lại cấu hình thuật toán.

Hình 3.19: Cấu hình Weka cho thuật toán Naive Bayes

Theo mặc định, một phân phối Gaussian được giả sử cho từng thuộc tính số.

Các phân phối này có thể thay đổi thuật toán để sử dụng công cụ ước tính Kernel

với đối số sử dụng Kernel Estimator có thể phù hợp hơn với phân phối thực tế của

các thuộc tính trong tập dữ liệu của bạn. Tuy nhiên, các thông số này có thể tự động

chuyển đổi các thuộc tính số thành thuộc tính danh nghĩa với tham số sử dụng

Supervised Discretization.

3) Nhấn vào “Ok” đây để đóng cấu hình thuật toán.

4) Ta chọn thuộc tính phân lớp là “class”, chọn các Classifer tương ứng, sau đó

bấm Start để tiến hành xây dựng mô hình và đánh giá độ chính xác. Sau chạy

thuật toán trên bộ dữ liệu Ionosphere. Có thể thấy rằng với cấu hình mặc

định, thuật toán cây quyết định đạt được độ chính xác 95.4042%.

Hình 3.20: Kết quả phân lớp Weka cho thuật toán Naive Bayes với số 70% Split

Nhận xét:

- Thời gian xây dừng mô hình là 0.01 giây

- Tỷ lệ phân lớp đúng là 95.4042% (2325 mẫu)

- Tỷ lệ phân lớp sai là 4.5958% (112 mẫu)

- Mức độ chính của bộ phân lớp đối với mỗi lớp e (nấm ăn được) và lớp p

(nấm không ăn được) là:

- Ma trận Confusion thể hiện các mẫu nấm ăn được (e) phân đúng là 1242,

phân sai là 101. Các mẫu không ăn được (p) phân đúng là 1083, phân sai là

Kịch bản 2: thực nghiệm huấn luyện trong chế độ phân Cross-validation.

Tập dữ liệu sẽ được chia đều k tập (folds) có kích thước xấp xỉ nhau, và bộ phân

loại học được sẽ được dánh giá bởi phướng pháp cross-validation. Trong thực

nghiệm này tôi xác định chọn fold=10, để đạt hiệu quả phân lớp như sau:

Sau chạy thuật toán trên bộ dữ liệu Ionosphere. Có thể thấy rằng với cấu hình

mặc định, thuật toán cây quyết định đạt được độ chính xác 95.8272%.

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 (fold=10 cross-validation)

3.3.2 Thực hiện phân lớp bằng thuật toán k-Nearest neighbor

Thuật toán hỗ trợ cả phân lớp và hồi quy. Nó cũng được gọi là kNN cho

ngắn gọn. Nó hoạt động bằng cách lưu trữ toàn bộ tập dữ liệu huấn luyện và truy

vấn nó để xác định vị trí của các mẫu đào tạo tương tự nhất khi đưa ra dự đoán. Như

vậy, không có mô hình nào ngoài tập dữ liệu huấn luyện thô và phép tính duy nhất

được thực hiện là truy vấn bộdữ liệu huấn luyện khi yêu cầu dự đoán.

Chọn thuật toán k-Nearest Neighbors:

1) Nhấp vào nút “Choose” và chọn “IBk” trong nhóm “Lazy”.

2) Nhấp vào tên của thuật toán để xem lại cấu hình thuật toán.

Hình 3.22: Cấu hình Weka cho thuật toán k-NN

Theo hình 3.21 cấu hình Weka cho thuật toán k-Neares Neighbors chúng ta

được xác định giá trị tham số K (số láng giềng gần nhất) K=1 và dùng khoảng

cách Euclidean để tính khoảng cách giữa các trường hợp, điều này tốt cho dữ liệu số

có cùng tỷ lệ. Khoảng cách Manhattan là tốt để sử dụng nếu thuộc tính của bạn khác

nhau về các biện pháp hoặc loại.

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

3) Sau đó nhấn vào “Ok” đây để đóng cấu hình thuật toán.

4) Ta chọn thuộc tính phân lớp là “class”, chọn các Classifer tương ứng,

sau đó bấm Start để tiến hành xây dựng mô hình và đánh giá độ chính

xác. Sau chạy thuật toán trên bộ dữ liệu Ionosphere. Có thể thấy rằng với cấu

hình mặc định, thuật toán cây quyết định đạt được độ chính xác 100%.

Hình 3.24: Kết quả phân lớp Weka cho thuật toán k-NN với số 70% Split

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

(fold=10 cross-validation)

3.3.3 Thực hiện phân lớp bằng thuật toán Support Vector Machines

1) Nhấp vào nút “Choose” và chọn “SMO” trong nhóm “Function”

2) Nhấp vào tên của thuật toán để xem lại cấu hình thuật toán

Hình 3.26: Cấu hình Weka cho thuật toán SVM

Theo hình (3.26) tham số C, được gọi là tham số độ phức tạp trong Weka

kiểm soát mức độ linh hoạt của quy trình vẽ đường phân tách các lớp có thể. Giá trị

0 cho phép không vi phạm ký quỹ, trong khi mặc định là 1.

Một tham số chính trong SVM là loại Kernel sẽ sử dụng. Hạt nhân đơn giản

nhất là hạt nhân tuyến tính phân tách dữ liệu bằng một đường thẳng hoặc siêu

phẳng. Mặc định trong Weka là một hạt nhân đa thức sẽ phân tách các lớp bằng

cách sử dụng một đường cong hoặc uốn lượn, đa thức càng cao, càng lung lay (giá

trị số mũ).

Một hạt nhân phổ biến và mạnh mẽ là Kernel RBF hoặc Radial Basis

Function Kernel có khả năng học các đa giác khép kín và các hình dạng phức tạp để

phân tách các lớp.

Đó là một ý tưởng tốt để thử một bộ các giá trị hạt nhân và C (độ phức tạp)

khác nhau về vấn đề của bạn và xem cái gì hoạt động tốt nhất.

3) Sau đó nhấn vào “Ok” đây để đóng cấu hình thuật toán.

4) Ta chọn thuộc tính phân lớp là “class”, chọn các Classifer tương ứng, sau đó

bấm Start để tiến hành xây dựng mô hình và đánh giá độ chính xác. Sau chạy

thuật toán trên bộ dữ liệu Ionosphere. Có thể thấy rằng với cấu hình mặc

định, thuật toán cây quyết định đạt được độ chính xác 100%.

Hình 3.27: Kết quả phân lớp Weka cho thuật toán SVM với số 70% Split

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 (fold=10 cross-validation)

3.3.4 Thực hiện phân lớp bằng thuật toán Decision tree (J48)

1) Nhấp vào nút “Choose” và chọn “J48” trong nhóm “Trees”.

2) Nhấp vào tên của thuật toán để xem lại cấu hình thuật toán.

Hình 3.29: Cấu hình Weka cho thuật toán J48

5) Sau đó nhấn vào “Ok” đây để đóng cấu hình thuật toán.

6) Ta chọn thuộc tính phân lớp là “class”, chọn các Classifer tương ứng, sau đó

bấm Start để tiến hành xây dựng mô hình và đánh giá độ chính xác. Sau chạy

thuật toán trên bộ dữ liệu Ionosphere. Có thể thấy rằng với cấu hình mặc

định, thuật toán cây quyết định đạt được độ chính xác 100%.

Hình 3.30: Kết quả phân lớp Weka cho thuật toán J48 decision với số 70% Split

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 (fold=10 cross-validation) Riêng thuật toán J48, ta có thể sử dụng chức năng Visualize Tree để

xem hình ảnh cây quyết định.

Hình 3.32: Mô hình cây quyết định hiển thị bởi Hold-out J48

Hình 3.33: cây quyết định Visualization

3.4. Đánh giá mô hình phân lớp dữ liệu Mushroom

3.4.1 Đánh giá mô hình bằng phương pháp Hold-out

Chúng ta sẽ chia dữ liệu thành 2 phần: 70% để xây dựng mô hình phân lớp

(tập train), 30% để kiểm tra (tập test).

Bảng 3.4: Hiệu năng của mô hình dự đoán, đánh giá bởi kiểm tra 70%

Classifier

Precision Recall F-measure

ACC

Time Confusion matrix

Naïve Bayes

0,990

0,915

0,951

95.4042%

0.01

KNN (k=1)

100%

0.03

SVM

100%

1.35

J48

100%

0.05

3.4.2 Đánh giá mô hình bằng phương pháp k-fold Cross validation

Ta chọn k=10, nghĩa là chia tập dữ liệu thành 10 phần, 1 phần dùng làm tập

kiểm tra (test set), 9 phần dùng để huấn luyện (train set).

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)

Classifier

Precision Recall F-measure

ACC

Time Confusion matrix

Naïve Bayes

0,991

0,922

0,955

95.8272%

0.02

KNN (k=1)

100%

0.02

100%

0.98

SVM

100%

0.03

J48

3.5. Kết luận thực nghiệm phần lớp dữ liệu Mushroom

Qua kết quả phân lớp trên, ta thấy ngoài mô hình Naive Bayes, các mô hình

còn lại đều cho kết quả phân lớp rất tốt (100% phân lớp chính xác). Điều này cho

thấy, các mô hình phân lớp ở trên khá phù hợp cho bài toán phân lớp, dự đoán nấm.

Từ kết quả của một số mô hình phân lớp ở trên, đặc biệt là mô hình phân lớp

dựa vào cây quyết định, ta có thể biết được một loại nấm có độc hay không nhờ vào

đặc điểm mùi và màu sắc của nó.

Về đặc điểm mùi, nấm nào ăn được thường có mùi hạnh nhân và mùi hoa

hồi, nấm độc thường có mùi hôi, tanh, và cay.

Còn đặc điểm màu sắc, chỉ có nấm màu xanh lá cây là không ăn được hoặc

nấm có độc, các loài nấm có màu loè loẹt như cam, vàng, tím đều là nấm ăn được.

Thật thú vị, thông qua một số thuật toán phân lớp (ví dụ: cây quyết định), ta

có thể phân biệt được đâu là nấm độc, đâu là nấm ăn được chỉ thông qua một số đặc

điểm nhận diện qua mùi và màu sắc.

3.6 Tổng kết chương

Chương 3 trình bày các vấn đề chính về bài toán phân lớp/dự đoán tính chất

(ăn được/có độc) của nấm thông qua việc áp dụng một số phương pháp/kỹ thuật

phân lớp dữ liệu. Đặc biệt, chương trình đã xây dựng trình bày mô hình tổng thể bài

toán phân lớp dự đoán nấm trên cơ sở áp dụng các thuật toán phân lớp và phần mềm

hỗ trợ trực quan Weka. Kết quả thực nghiệm của bài toán được trình bày khá chi tiết

trên cơ sở áp dụng phần mềm Weka và các phương pháp phổ biến như: Naive

Bayes, Nearest neighbor, Support Vector Machines, Decision tree (J48).

KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN

Kết quả đạt được:

Sau một thời gian làm việc, nghiên cứu dưới sự hướng dẫn tận tình của thầy

giáo TS. Nguyễn Văn Núi, tôi đã đạt được các kết quả sau đây:

1. Tổng hợp được tương đối đầy đủ và chính xác khái niệm và kiến thức liên

quan đến khai phá dữ liệu và phát hiện tri thức, các thuật toán phân lớp dữ liệu và

ứng dụng về việc dự doán.

2. Giới thiệu và trình bày công cụ phần mềm Weka (Waikato Environment

for Knowledge Analysis) là một bộ phần mềm học máy được Đại học Waikato,

New Zealand phát triển bằng Java., ứng dụng trong phân lớp dữ liệu.

3. Tìm hiểu các bài toán phân lớp dữ liệu áp dụng cho phân lớp và dự đoán

nấm Mushroom.

4. Cài đặt, cấu hình phần mềm Weka và tiến hành phân lớp dữ liệu thực hiện

trong phân lớp dữ liệu Mushroom.

5. Tóm tắt và đề xuất một số tính chất tiêu biểu của nấm có thể trở thành

thông tin, căn cứ chính, qua đó giúp phân biệt dự đoán một loại nấm bất kỳ là có

độc hoặc ăn được thông qua một số mô hình phân lớp nhất định (ví dụ: cây quyết

định).

Hướng phát triển của luận văn:

Trong thời gian tới, tôi sẽ tiếp tục nghiên cứu sâu hơn về các vấn đề của phân

lớp dữ liệu, đặc biệt sẽ nghiên cứu tìm hiểu sâu hơn việc ứng dụng phần mềm Weka

để tiến hành phân tích dữ liệu ứng dụng trong các lĩnh vực cụ thể như phân lớp, dự

đoán Mushroom.

Tiến hành nghiên cứu thêm các thuật toán phân lớp dữ liệu, tối ưu hóa các

thuật toán phân lớp dữ liệu, từ đó đề xuất mô hình phân lớp, dự đoán vị Mushroom

với độ chính xác cao hơn nữa.

TÀI LIỆU THAM KHẢO

Tiếng Việt

[1]. Đỗ Phúc (2017), Giáo trình khai phá dữ liệu, NXB ĐHQG TPHCM

[2]. Nguyễn Hà Nam, Nguyễn Trí Thành, Hà Quang Thụy (2013), Giáo trình

khai phá dữ liệu, NXB Đại học Quốc gia Hà Nội.

[3]. Hà Quang Thụy (Chủ biên), Phan Xuân Hiếu – Đoàn Sơn – Nguyễn Trí

Thành, Nguyễn Thu Trang – Nguyễn Cẩm Tú (2009), Giáo trình khai

phá dữ liệu, NXB .Giáo dục Việt Nam

[4]. Website: https://ndhcuong.wordpress.com/hoc-phan/khai-pha-du-lieu/

[5]. Website:https://ongxuanhong.wordpress.com/2015/08/25/ap-dung-cac-

phuong -phap- phan-lop-classification-tren-tap-du-lieu-mushroom/

[6]. Joydeep Ghosh (2003), Scalable Clustering, Chapter 10, pp. 247-278,

Formal version appears in: The Hand book of Data Mining, Nong Ye (Ed)

[7]. Anil K. Jain and Richard C. Dubes (1988), Algorithms for clustering data,

Prentice Hall, Inc., USA.

[8]. Ho Tu Bao (1998), Introduction to knowledge discovery and data mining.

[9]. Jiawei Hanand Micheline Kambel (2000), Data Mining: Concepts and

Techniques, Morgan Kaufmann Publishers.

[10]. J.Ross Quinlan (1993), C4.5: Programsfor Machine Learning, Morgan

Kaufmann Publishers.

[11]. Robert Nisbet, John Elder, Gary Miner, Handbook of Statistical Analysis and

Data Mining Applications, Elsevier Inc, 2009

[12]. Mehmed Kantardzic; Data mininng concepts, models, methods, and algorithms;

John Wiley & Són, 2003

[13]. Usama Fayyad, Gregory Piatesky-Shapiro, and Padhraic Smyth; From data

mining to knowledge discovery in databases

[14]. Concepts-and-Techniques-3rd-Edition-Morgan-Kaufmann-(2011)

[15]. WEKA Manual for Version 3-8-0 Remco R. Bouckaert, Eibe Frank, Mark Hall,

Richard Kirkby, Peter Reutemann, Alex Seewald, David Scuse, April 14, 2016

[16]. Website: https://archive.ics.uci.edu/ml/datasets/mushroom

Tiếng anh

Luận văn Thạc sĩ Khoa học máy tính: 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

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

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

LỜI CẢM ƠN

LỜI CAM ĐOAN

MỤC LỤC

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

DANH SÁNH BẢNG

DANH SÁNH HÌNH VẼ

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

Phát hiện tri thức trong

CSDL

Accuracy

Độ chính xác

CHƯƠNG 1

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

• Giả sử tập dữ liệu mẫu (x1, y1), ..., (xm, ym) với xi là một vector n chiều và

• Biến đổi tập Y ban đầu thành m tập có hai lớp con

• Áp dụng SVM phân lớp nhị phân cơ bản với m tâp Zi để xây dựng siêu

• Phương pháp Hold-out

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

• Bước 3: Chọn kiểu test, và tập dữ liệu test nếu cần

3) Sau đó nhấn vào “Ok” đây để đóng cấu hình thuật toán.

4) Ta chọn thuộc tính phân lớp là “class”, chọn các Classifer tương ứng,

sau đó bấm Start để tiến hành xây dựng mô hình và đánh giá độ chính

xác. Sau chạy thuật toán trên bộ dữ liệu Ionosphere. Có thể thấy rằng với cấu

xem hình ảnh cây quyết định.

Classifier

Precision Recall F-measure

ACC

Time Confusion matrix

3.4.2 Đánh giá mô hình bằng phương pháp k-fold Cross validation

Classifier

Precision Recall F-measure

ACC

Time Confusion matrix

KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN

TÀI LIỆU THAM KHẢO

Có thể bạn quan tâm

Luận văn Thạc sĩ: Quản lý hoạt động phát triển nhận thức cho trẻ mẫu giáo ở các trường mầm non, huyện Hoàng Su Phì, tỉnh Hà Giang

Luận văn Thạc sĩ tóm tắt: Pháp luật về điều kiện đầu tư kinh doanh trong lĩnh vực giáo dục, đào tạo ở Việt Nam

Luận văn Thạc sĩ: Sự nghiệp nghiên cứu phê bình văn học của Hoài Thanh

Luận văn Thạc sĩ: Tiểu thuyết của Đỗ Phấn từ góc nhìn sinh thái

Luận văn Thạc sĩ: Giải pháp ứng phó với nhập cư ở Liên minh Châu Âu

Luận văn Thạc sĩ: Diễn ngôn về giới nữ trong văn xuôi nữ Việt Nam đương đại (khảo sát sáng tác của Dạ Ngân, Y Ban, Lý Lan, Nguyễn Thị Thu Huệ)

Luận văn Thạc sĩ: Xây dựng mức phát thải tham chiếu rừng khu vực huyện Bảo Lâm tỉnh Lâm Đồng

Luận văn Thạc sĩ: Đặc điểm nhân vật chính trong ba tác phẩm của Franz Kafka: Lâu đài, Vụ án, Hóa thân

Kháo luận tốt nghiệp: Vận dụng lí thuyết học tập trải nghiệm vào dạy học Thống kê - Xác suất ở lớp Hai

Luận văn Thạc sĩ: Xây dựng hệ thống điều khiển và thu nhận dữ liệu cho Robot dịch vụ

Luận văn Thạc sĩ: Thế giới nhân vật trong truyện ngắn Lê Minh Khuê sau năm 1975

Luận văn Thạc sĩ: Tác động của cấu trúc vốn đến hiệu quả hoạt động của các ngân hàng thương mại cổ phần niêm yết trên thị trường chứng khoán Việt Nam

Luận văn Thạc sĩ: Kiểm soát rủi ro tín dụng bán lẻ tại Ngân hàng Thương mại Cổ phần Đầu tư và Phát triển Việt Nam chi nhánh Thủ Thiêm

Luận văn Thạc sĩ: Các yếu tố ảnh hưởng đến hiệu quả kinh doanh của ngân hàng thương mại cổ phần niêm yết trên thị trường chứng khoán Việt Nam

Luận văn Thạc sĩ: Các nhân tố ảnh hưởng đến hành vi sử dụng dịch vụ ngân hàng điện tử tại Ngân hàng Thương mại Cổ phần Ngoại thương Việt Nam – Chi nhánh Thủ Đức

Luận văn Thạc sĩ: Các yếu tố tác đồng đến nợ xấu tại Ngân hàng Nông nghiệp và Phát triển Nông thôn - Chi nhánh Tiền Giang

Luận văn Thạc sĩ: Yếu tố ảnh hưởng đến quyết định sử dụng dịch vụ thanh toán không dùng tiền mặt tại Ngân hàng TMCP Công thương Việt Nam (Vietinbank)

Luận văn Thạc sĩ tóm tắt: Pháp luật về du lịch biển, thực tiễn tại tỉnh Bình Định

Luận văn Thạc sĩ: Ảnh hưởng của các yếu tố thương hiệu với vai trò trung gian của Marketing truyền miệng đến quyết định chọn việc làm của nhân viên GenZ tại chuỗi nhà hàng gà rán Popeyes khu vực Thành Phố Hồ Chí Minh

Luận văn Thạc sĩ: Ảnh hưởng của Marketing mix đến ý định học cao học của sinh viên khối ngành kinh tế thuộc Trường Đại học Công nghệ Thành phố Hồ Chí Minh

Tài liêu mới

Luận án Tiến sĩ: Nghiên cứu xây dựng thuật toán thích nghi và học tăng cường cấu trúc Actor - Critic điều khiển bám quỹ đạo cho robot di động đa hướng mecanum

Luận án Tiến sĩ: Cơ cấu bệnh tim mạch và chất lượng cuộc sống của người cao tuổi mắc suy tim, rung nhĩ điều trị tại Bệnh viện Thống Nhất, thành phố Hồ Chí Minh

Tóm tắt Luận án Tiến sĩ: Nghiên cứu hiện tượng nứt dăm đê sông vùng đồng bằng sông Hồng và dự báo khả năng bị nứt của một số đoạn đê

Tóm tắt Luận án Tiến sĩ: Nghiên cứu xây dựng giải pháp đảm bảo an toàn thông tin cho quá trình học liên kết dựa trên mật mã

Tóm tắt Luận án Tiến sĩ: Phát triển năng lực đánh giá công nghệ cho học sinh trong dạy học môn Công nghệ 11 ở trường trung học phổ thông

Tóm tắt Luận án Tiến sĩ: Nghiên cứu phân loại chi cầu diệp – Bulbophyllum Thouars (Orchidaceae) ở vùng Tây Nguyên bằng phương pháp hình thái và phân tử

Tóm tắt Luận án Tiến sĩ: Nghiên cứu đặc điểm phân bố và dinh dưỡng của các loài lưỡng cư ở Vườn Quốc gia Bến En và Khu bảo tồn thiên nhiên Pù Luông, tỉnh Thanh Hóa

Luận án Tiến sĩ: Tổng hợp luật dẫn và điều khiển cho một lớp tên lửa đối hải trên cơ sở ứng dụng mạng nơ ron và hệ mờ

Luận án Tiến sĩ: Nghiên cứu tổng hợp hệ điều khiển góc Pitch tua bin gió trong điều kiện có nhiễu tác động

Luận án Tiến sĩ: Nghiên cứu hóa học lipid của hai loài san hô thủy tức Millepora dichotoma và Millepora platyphylla ở Việt Nam

Luận án Tiến sĩ: Nghiên cứu kiểm soát phân phối công suất kéo trên cầu chủ động của ô tô con bằng ABS