Phương pháp học nửa giám sát và ứng dụng

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

ĐẠI HỌC THÁI NGUYÊN

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

————————————

TRẦN ANH TUẤN

PHƯƠNG PHÁP HỌC NỬA GIÁM SÁT VÀ ỨNG DỤNG

Chuyên nghành: Khoa học máy tính

Mã số : 60.48.01

LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

Người hướng dẫn khoa học: PGS.TS ĐOÀN VĂN BAN

Thái nguyên – Năm 2014

- i -

MỤC LỤC

MỤC LỤC..............................................................................................................i

DANH MỤC CÁC TỪ VIẾT TẮT .....................................................................iv

DANH MỤC CÁC HÌNH..................................................................................... v

MỞ ĐẦU............................................................................................................... 1

CHƢƠNG 1: PHƢƠNG PHÁP HỌC MÁY ....................................................... 4

1.1. Khái niệm học máy .................................................................................... 4

1.2. Một số khái niệm cơ bản trong học máy.................................................... 6

1.2.1. Không gian biểu diễn của dữ liệu ....................................................... 6

1.2.2. Bản chất của dữ liệu............................................................................ 6

1.2.3. Tiền xử lý dữ liệu................................................................................ 6

1.2.4. Quá trình rời rạc hóa dữ liệu ............................................................... 7

1.2.5. Tập mẫu............................................................................................... 7

1.2.6. Quá trình tìm kiếm trong không gian giả thuyết................................. 7

1.3. Học có giám sát.......................................................................................... 8

1.3.1. Khái niệm............................................................................................ 8

1.3.2. Cách giải một bài toán học có giám sát .............................................. 9

1.3.3. Cực tiểu hóa rủi ro kinh nghiệm ....................................................... 10

1.4. Học không có giám sát............................................................................. 11

1.4.1. Khái niệm.......................................................................................... 11

1.4.2. Phân cụm dữ liệu............................................................................... 12

1.5. Học tăng cƣờng ........................................................................................ 14

1.6. Học nửa giám sát...................................................................................... 16

1.6.1. Khái niệm.......................................................................................... 16

- ii -

1.6.2. Bài toán học nửa giám sát ................................................................. 19

1.7. Tổng kết chƣơng 1 ................................................................................... 21

CHƢƠNG 2: MỘT SỐ THUẬT TOÁN HỌC NỬA GIÁM SÁT VÀ BÀI

TOÁN PHÂN CỤM DỮ LIỆU........................................................................... 22

2.1. Một số thuật toán học nửa giám sát ......................................................... 22

2.1.1. Mô hình sinh và thuật toán kỳ vọng cực đại..................................... 22

2.1.1.1. Giới thiệu mô hình sinh.............................................................. 22

2.1.1.2. Mô hình sinh trong học nửa giám sát......................................... 22

2.1.1.3. Thuật toán kỳ vọng cực đại........................................................ 24

2.1.2. Thuật toán tự huấn luyện................................................................... 25

2.1.2.1 Giới thiệu thuật toán tự huấn luyện............................................. 25

2.1.2.2. Nội dung thuật toán.................................................................... 26

2.1.3. Thuật toán đồng huấn luyện.............................................................. 27

2.1.3.1. Giới thiệu thuật toán đồng huấn luyện....................................... 27

2.1.3.2. Nội dung thuật toán.................................................................... 28

2.1.4. Thuật toán máy véc tơ hỗ trợ (S3VM).............................................. 29

2.4.1.1. Thuật toán SVM......................................................................... 29

2.1.4.2. Giới thiệu thuật toán S3VM....................................................... 34

2.1.4.3. Nội dung thuật toán S3VM........................................................ 34

2.2. Phân cụm dữ liệu...................................................................................... 36

2.2.1. Khái quát quá trình phân cụm dữ liệu............................................... 36

2.2.2. Bài toán phân cụm dữ liệu ................................................................ 36

2.2.3. Các yêu cầu của phân cụm dữ liệu.................................................... 39

2.2.4. Các kỹ thuật phân cụm...................................................................... 41

- iii -

2.2.5. Một số thuật toán phân cụm dữ liệu nửa giám sát ............................ 46

2.2.5.1. Thuật toán COP-Kmeans........................................................... 46

2.2.5.2. Phân cụm nửa giám sát trên tập dữ liệu đƣợc gán nhãn ............ 47

2.2.5.3. Thuật toán K-Means phân cấp ................................................... 49

2.3. Tổng kết chƣơng 2 ................................................................................... 50

CHƢƠNG 3: ỨNG DỤNG HỌC NỬA GIÁM SÁT VÀO BÀI TOÁN PHÂN

CỤM VĂN BẢN................................................................................................. 51

3.1. Phân tích bài toán ..................................................................................... 51

3.2 Hƣớng giải quyết của bài toán .................................................................. 53

3.3. Giải pháp, công nghệ sử dụng.................................................................. 57

3.4. Cài đặt chƣơng trình thử nghiệm ............................................................. 58

3.4.1. Nội dung chƣơng trình ...................................................................... 58

3.4.2. Kết quả thực nghiệm......................................................................... 63

3.4.3. Thực hiện phân cụm thử nghiệm ...................................................... 64

3.5. Kết luận chƣơng 3 .................................................................................... 67

KẾT LUẬN......................................................................................................... 68

TÀI LIỆU THAM KHẢO................................................................................... 70

- iv -

DANH MỤC CÁC TỪ VIẾT TẮT

SVM Support Vector Machine

S3VM Semi – superviesd Suport vector machines

EM Expectation-Maximization

MaxEnt Maximum Entropy

TSVM Transductive Support Vector Machine

RSS Residual Sum of Squares

- v -

DANH MỤC CÁC HÌNH

Hình 1.1: Mô hình học có giám sát....................................................................... 8

Hình 1.2: Minh họa phân cụm dữ liệu. ............................................................... 13

Hình 1.3: Sơ đồ quá trình thực hiện của học nửa giám sát ................................. 17

Hình 1.4: Mô hình học nửa giám sát .................................................................. 19

Hình 1.5: Dữ liệu chƣa gán nhãn sử dụng trong quá trình học nửa giám sát ..... 20

Hình 1.6: Mô hình hóa các tập dữ liệu trong học nửa giám sát.......................... 21

Hình 2.1 Dữ liệu có nhãn .................................................................................... 23

Hình 2.2 Dữ liệu có nhãn và chƣa có nhãn ......................................................... 23

Hình 2.3. Quá trình tự huấn luyện....................................................................... 26

Hình 2.4 Phân lớp SVM.................................................................................... 29

Hình 2.5: Phân cụm các vector truy vấn ............................................................. 37

Hình 2.6: Hình thành cụm cha ............................................................................ 38

Hình 2.7: Các chiến lƣợc phân cụm phân cấp ................................................... 42

Hình 2.8: Thuật toán K-Means phân cấp ............................................................ 50

Hình 3.1. Thuật toán phân cụm văn bản ............................................................. 57

Hình 3.2: Giao diện chính chƣơng trình ............................................................. 63

Hình 3.3: Thử nghiệm nhập văn bản để phân cụm............................................. 65

Hình 3.4: Thử nghiệm chèn văn bản vào danh sách chờ phân cụm ................... 66

Hình 3.5: Kết quả phân cụm thử nghiệm............................................................ 66

- 1 -

MỞ ĐẦU

1. Đặt vấn đề

Hoạt động học tập là hoạt động chuyên hƣớng vào sự tái tạo lại tri thức ở

ngƣời học. Sự tái tạo ở đây hiểu theo nghĩa là phát hiện lại. Sự thuận lợi cho

ngƣời học ở đây đó là con đƣờng đi mà để phát hiện lại đã đƣợc các nhà khoa

học tìm hiểu trƣớc, giờ ngƣời học chỉ việc tái tạo lại. Và để tái tạo lại, ngƣời học

không có cách gì khác đó là phải huy động nội lực của bản thân (động cơ, ý chí,

…), càng phát huy cao bao nhiêu thì việc tái tạo lại càng diễn ra tốt bấy nhiêu.

Do đó hoạt động học làm thay đổi chính ngƣời học. Ai học thì ngƣời đó phát

triển, không ai học thay thế đƣợc, ngƣời học cần phải có trách nhiệm với chính

bản thân mình, vì mình trong quá trình học. Mặc dù hoạt động học có thể cũng

có thể làm thay đổi khách thể. Nhƣng nhƣ thế không phải là mục đích tự thân

của hoạt động học mà chính là phƣơng tiện để đạt đƣợc mục đích làm thay đổi

chính chủ thể của hoạt động.

Hoạt động học là hoạt động tiếp thu những tri thức lý luận, khoa học.

Nghĩa là việc học không chỉ dừng lại ở việc nắm bắt những khái niệm đời

thƣờng mà học phải tiến đến những tri thức khoa học, những tri thức có tính

chọn lựa cao, đã đƣợc khái quát hoá, hệ thống hoá.

Hoạt động học tập không chỉ hƣớng vào việc tiếp thu những tri thức, kĩ

năng, kĩ xảo mà còn hƣớng vào việc tiếp thu cả những tri thức của chính bản

thân hoạt động học. Hoạt động học muốn đạt kết quả cao, ngƣời học phải biết

cách học, phƣơng pháp học, nghĩa là phải có những tri thức về chính bản thân

hoạt động học.

Vậy, việc làm thế nào để máy tính có khả năng học tập, tƣ duy và có khả

năng học tập giống con ngƣời là một lĩnh vực nghiên cứu rất đƣợc chú ý trong

thời đại hiện nay. Dựa trên khuynh hƣớng đó và sự hƣớng dẫn của PGS, TS