Luận văn Thạc sĩ Khoa học máy tính: Học nửa giám sát dựa trên đồ thị và ứng dụng

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

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

Mã số: 60 48 01 01

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

NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS.TS. ĐOÀN VĂN BAN

THÁI NGUYÊN - 2015

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

i

LỜI CẢM ƠN

Trong quá trình làm luận văn “Học nửa giám sát dựa trên đồ thị và ứng dụng”

tôi đã nhận đƣợc sự giúp đỡ tận tình của các cá nhân và tập thể.

Trƣớc hết, tôi xin bày tỏ lòng biết ơn sâu sắc đến thầy giáo PGS.TS Đoàn

Văn Ban, ngƣời đã tận tình hƣớng dẫn, chỉ bảo cho tôi trong suốt quá trình thực

hiện luận văn.

Xin cùng bày tỏ lòng biết ơn chân thành tới các thầy, cô giáo trong Viện Công

nghệ Thông tin cũng nhƣ các thầy, cô giáo trong Trƣờng Đại học Công nghệ Thông

tin & Truyền thông Thái Nguyên, đã đem lại cho tôi những kiến thức vô cùng có ích

trong những năm học tập tại trƣờng.

ngƣời đã luôn bên cạnh, động viên và khuyến khích tôi trong quá trình thực hiện đề

tài nghiên cứu của mình.

Tôi xin chân thành cảm ơn!

, ngày 10 tháng 4 năm 2015

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

LỜI CẢM ƠN ............................................................................................................. i

DANH MỤC HÌNH VẼ ..............................................................................................v

LỜI MỞ ĐẦU .............................................................................................................1

1.

............................................................................................................ 1

...................................................................................................... 2

.................................................................................. 2

............................................................................................... 2

............................................................................................... 3

6.

.......................................................................................................... 3

CHƢƠNG 1: TỔNG QUAN VỀ CÁC PHƢƠNG PHÁP HỌC MÁY ......................4

1.1. Giới thiệu về học máy ................................................................................................. 4

1.2. Các phƣơng pháp học máy .......................................................................................... 7

1.2.1. Học có giám sát .................................................................................................... 7

1.2.2. Học không giám sát .............................................................................................. 8

1.2.3. Học tăng cƣờng .................................................................................................. 11

1.2.4. Học nửa giám sát ................................................................................................ 12

1.3. Một số phƣơng pháp học nửa giám sát ..................................................................... 14

1.3.1. Phƣơng pháp tự huấn luyện ................................................................................ 14

1.3.2. Phƣơng pháp đồng huấn luyện ........................................................................... 15

1.3.3. Phƣơng pháp Máy véc tơ hỗ trợ truyền dẫn ....................................................... 18

1.3.4. Phƣơng pháp dựa trên đồ thị .............................................................................. 22

1.4. Kết luận ..................................................................................................................... 24

CHƢƠNG 2: PHƢƠNG PHÁP HỌC NỬA GIÁM SÁT DỰA TRÊN ĐỒ THỊ .....25

2.1. Giới thiệu .................................................................................................................. 25

2.2. Các loại đồ thị phổ biến có thể sử dụng trong học nửa giám sát .............................. 27

2.2.1. Đồ thị kết nối đầy đủ .......................................................................................... 27

2.2.2. Đồ thị rời rạc ...................................................................................................... 27

2.2.3. Đồ thị

-láng giềng gần nhất ............................................................................ 28

2.2.4. Đồ thị -láng giềng gần nhất ............................................................................. 28

2.2.5. Đồ thị trọng số exp ............................................................................................ 29

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

2.3. Các phƣơng pháp xác định khoảng cách giữa các điểm dữ liệu ............................... 29

2.3.1. Khoảng cách cục bộ, khoảng cách toàn cục và trọng số .................................... 29

2.3.2. Khoảng cách Hamming ...................................................................................... 30

2.3.3. Khoảng cách Manhattan cho các thuộc tính số học ........................................... 30

2.3.4. Các hàm khoảng cách cục bộ không đồng nhất ................................................. 31

2.3.5. Hàm khoảng cách tri thức chuyên gia ................................................................ 31

2.4. Thuật toán lan truyền nhãn trong đồ thị .................................................................... 32

2.4.1. Ký hiệu ............................................................................................................... 32

2.4.2. Nội dung thuật toán ............................................................................................ 33

2.4.3. Sự hội tụ của thuật toán ...................................................................................... 34

2.4.4. Phƣơng pháp xác định siêu tham số của đồ thị .................................................. 36

2.4.5. Độ phức tạp của thuật toán ................................................................................. 38

2.5. Thuật toán học nửa giám sát dựa trên đồ thị - Mincut .............................................. 38

2.6. Các trƣờng Gaussian ngẫu nhiên và các hàm điều hòa ............................................. 40

2.6.1. Các trƣờng Gaussian ngẫu nhiên........................................................................ 40

2.6.2. Đồ thị Laplacian ................................................................................................. 42

2.6.3. Các hàm điều hòa ............................................................................................... 43

2.7. Đánh giá .................................................................................................................... 44

2.8. Kết luận chƣơng ........................................................................................................ 44

CHƢƠNG 3: CÀI ĐẶT VÀ THỬ NGHIỆM THUẬT TOÁN ................................45

3.1. Mô tả bài toán ........................................................................................................... 45

3.2. Mô tả dữ liệu đầu vào ............................................................................................... 45

3.3. Trích chọn đặc trƣng ................................................................................................. 47

3.4. Cài đặt và thử nghiệm ............................................................................................... 50

Môi trƣờng cài đặt và thử nghiệm ................................................................................ 50

Các chức năng của chƣơng trình .................................................................................. 51

3.5. Kết quả thực nghiệm và đánh giá độ phức tạp .......................................................... 54

3.6. Kết luận ..................................................................................................................... 56

KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ................................................................57

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

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

DANH MỤC CÁC THUẬT NGỮ VÀ TỪ VIẾT TẮT

Thuật ngữ Viết tắt Ý nghĩa

Concept Concept Khái niệm

Self-training Self-training Tự huấn luyện

Co-training Co-training Đồng huấn luyện

Machine learning Machine learning Học máy

Supervised learning Supervised learning Học có giám sát

Unsupervised learning Unsupervised learning Học không giám sát

Reinforcement learning Reinforcement learning Học tăng cƣờng

Semi-supervised Semi-supervised learning Học nửa giám sát learning

Support vector machine Máy véc tơ hỗ trợ SVM

Transductive support Máy véc tơ hỗ trợ truyền TSVM vector machine dẫn

Labeled Propagation Labeled Propagation Lan truyền nhãn

Graph-based Graph-based Dựa trên đồ thị

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

DANH MỤC HÌNH VẼ

Hình 1.1: Phƣơng pháp phân cụm dữ liệu. ................................................................. 9

Hình 1.2: Khung nhìn dữ liệu giữa văn bản và liên kết ............................................ 17

Hình 1.3: Dữ liệu đƣợc học theo phƣơng pháp Co-training. .................................... 18

Hình 1.4: Phƣơng pháp Máy véc tơ hỗ trợ ................................................................ 19

Hình 1.5: Phƣơng pháp máy vecto hỗ trợ truyền dẫn ............................................... 22

Hình 1.6: Minh họa đồ thị đƣợc gán nhãn ................................................................ 23

Hình 2.1: Phƣơng pháp dựa trên đồ thị ..................................................................... 25

Hình 2.2: Đồ thị kết nối đầy đủ ................................................................................. 27

Hình 2.3: Đồ thị rời rạc ............................................................................................. 27

Hình 2.4: Đồ thị -láng giềng gần nhất ................................................................... 28

Hình 2.5: Đồ thị -láng giềng gần nhất ..................................................................... 28

Hình 2.6: Trọng số cạnh giữa hai đỉnh của đồ thị ..................................................... 29

Hình 2.7: Đồ thị với các trọng số cạnh ..................................................................... 32

Hình 3.1: Tệp dữ liệu tin nhắn mẫu .......................................................................... 45

Hình 3.2: Nội dung tin nhắn đƣợc chuyển thành dạng vector ................................. 46

Hình 3.3: Nội dung file dữ liệu dạng vector ............................................................ 47

Hình 3.4: Trích chọn đặc trƣng ............................................................................... 48

Hình 3.5: Trích chọn thuộc tính cho file đầu vào của chƣơng trình ........................ 49

Hình 3.6: Dữ liệu của chƣơng trình ......................................................................... 49

Hình 3.7: Dữ liệu của chƣơng trình mở bằng Notepad ............................................ 50

Hình 3.8: Giao diện chọn tệp dữ liệu ....................................................................... 51

Hình 3.9: Kết quả khi lựa chọn phƣơng pháp tự huấn luyện ................................... 52

Hình 3.10: Giao diện đồ thị lan truyền nhãn trƣớc khi thực hiện ............................ 53

Hình 3.11: Giao diện đồ thị lan truyền nhãn sau khi thực hiện ............................... 54

Hình 3.12: Kết quả đồ thị sau khi đƣợc gán nhãn ở dạng đồ thị.............................. 54

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

1

LỜI MỞ ĐẦU

1.

Học máy (Machine learning) là một ngành khoa học nghiên cứu các kĩ thuật,

các phƣơng pháp cho phép các máy tính có khả năng "học" giống nhƣ con ngƣời.

Hay nói một cách khác cụ thể hơn, học máy là một phƣơng pháp để tạo ra các

chƣơng trình máy tính bằng việc phân tích các tập dữ liệu, qua đó máy tính có khả

năng tích lũy đƣợc tri thức thông qua việc học đƣợc các khái niệm để có thể ra

quyết định trong các trƣờng hợp tƣơng tự.

Lĩnh vực học máy truyền thống thƣờng đƣợc chia thành bốn lĩnh vực con,

bao gồm: Học có giám sát (Supervised learning), Học không giám sát

(Unsupervised learning), Học nửa giám sát (Semi-Supervised learning) và Học tăng

cƣờng (Reinforcement learning).

Học nửa giám sát sử dụng cả dữ liệu đã gán nhãn và chƣa gán nhãn để huấn

luyện - điển hình là một lƣợng nhỏ dữ liệu có gán nhãn cùng với lƣợng lớn dữ liệu

chƣa gán nhãn. Học nửa giám sát đứng giữa học không giám sát (không có bất kì dữ

liệu có nhãn nào) và có giám sát (toàn bộ dữ liệu đều đƣợc gán nhãn). Để gán nhãn

dữ liệu cho một bài toán học máy thƣờng đòi hỏi một phân loại bằng tay các ví dụ

huấn luyện. Chi phí cho quy trình này khiến tập dữ liệu đƣợc gán nhãn hoàn toàn

trở nên không khả thi, trong khi dữ liệu không .

Trong tình huống đó, học nửa giám sát có giá trị thực tiễn lớn lao. Chính vì vậy, học

nửa giám sát là sự kết hợp một số lƣợng lớn các dữ liệu chƣa đƣợc gán nhãn cùng

với các dữ liệu đã đƣợc gán nhãn để xây dựng các bộ phân lớp tốt hơn.

Một số phƣơng pháp điển hình trong lĩnh vực này đƣợc kể đến nhƣ: Phƣơng

pháp EM với mô hình sinh hỗn hợp (EM with generative mixture models), phƣơng

pháp Tự huấn luyện (Self-training), phƣơng pháp Đồng huấn luyện (Co-training),

phƣơng pháp máy véc tơ hỗ trợ (Transductive support vector machines) và phƣơng

pháp Dựa trên đồ thị (Graph-based). Trong đó phƣơng pháp học nửa giám sát dựa

trên đồ thị (Graph-based) đang là hƣớng nghiên cứu mở và đem lại hiệu quả lớn.

Với những lý do trên, tác giả đã chọn đề tài “

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

” làm đề tài nghiên cứu luận văn tốt nghiệp thạc sĩ chuyên ngành

Khoa học máy tính.

Nghiên cứu tổng quan về học nửa giám sát và một số phƣơng pháp học nửa

giám sát.

Nghiên cứu phƣơng pháp học nửa giám sát dựa trên đồ thị

Cài đặt thử nghiệm thuật toán lan truyền nhãn trên đồ thị và thuật toán tự

huấn luyện.

Đối tượng nghiên cứu: Học nửa giám sát.

Phạm vi nghiên cứu:

- Nghiên cứu tổng quan về học có giám sát, học không giám sát và học nửa

giám sát.

- Các phƣơng pháp học nửa giám sát phổ biến.

- Phƣơng pháp học nửa giám sát dựa trên đồ thị (Graph-based) và một số

thuật toán.

- Cài đặt thử nghiệm thuật toán lan truyền nhãn trong phƣơng pháp học nửa

giám sát dựa trên đồ thị và thuật toán tự huấn luyện.

Các luận điểm chính mà luận văn đã thể hiện đƣợc:

Nghiên cứu tổng quan và đánh giá các phƣơng pháp học nửa giám sát, tập

trung vào phƣơng pháp học nửa giám sát dựa trên đồ thị.

Tập trung tìm hiểu một số thuật toán trong lĩnh vực học nửa giám sát nhƣ:

Phƣơng pháp EM với mô hình sinh hỗn hợp, phƣơng pháp Tự huấn luyện, phƣơng

pháp Đồng huấn luyện và phƣơng pháp máy véc tơ hỗ trợ. Đồng thời tập trung

nghiên cứu chi tiết phƣơng pháp dựa trên đồ thị.

Cài đặt phần mềm thử nghiệm mô phỏng thuật toán lan truyền nhãn và thuật

toán tự huấn luyện, đánh giá độ phức tạp của hai thuật toán này.

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

- Đọc tài liệu, phân tích, tổng hợp.

- Thống kê, phân tích dữ liệu.

- Thực nghiệm và đánh giá kết quả.

- Kết hợp nghiên cứu lý thuyết, tìm hiểu tình hình ứng dụng, đánh giá khả

năng ứng dụng và đề xuất giải pháp.

6.

Nội dung luận văn gồm 03 chƣơng:

Chƣơng 1: Tổng quan về các phƣơng pháp học máy

Chƣơng này trình bày tổng quan về các phƣơng pháp học máy gồm

phƣơng pháp Học có giám sát (Supervised learning), Học không giám sát

(Unsupervised learning), Học nửa giám sát (Semi-Supervised learning).

Chƣơng 2: Phƣơng pháp học nửa giám sát dựa trên đồ thị

Tập trung tìm hiểu một số thuật toán trong lĩnh vực học nửa giám sát nhƣ:

Phƣơng pháp EM với mô hình sinh hỗn hợp, phƣơng pháp Tự huấn

luyện, phƣơng pháp Đồng huấn luyện và phƣơng pháp máy véc tơ hỗ trợ.

Đồng thời tập trung nghiên cứu chi tiết phƣơng pháp dựa trên đồ thị.

Chƣơng 3: Cài đặt và thử nghiệm thuật toán

Cài đặt thử nghiệm thuật toán tự huấn luyện và lan truyền nhãn dựa trên

đồ thị .

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

CHƢƠNG 1:

TỔNG QUAN VỀ CÁC PHƢƠNG PHÁP HỌC MÁY

1.1. Giới thiệu về học máy

Học máy (Machine Learning) là một ngành khoa học nghiên cứu các thuật

toán cho phép máy tính có thể học đƣợc các khái niệm (concept)[7].

Phƣơng pháp quy nạp: Máy học/phân biệt các khái niệm dựa trên dữ liệu đã

Có hai loại phƣơng pháp học máy chính:

thu thập đƣợc trƣớc đó. Phƣơng pháp này cho phép tận dụng đƣợc nguồn dữ liệu rất

Phƣơng pháp suy diễn: Máy học/phân biệt các khái niệm dựa vào các luật.

nhiều và sẵn có.

Phƣơng pháp này cho phép tận dụng đƣợc các kiến thức chuyên ngành để hỗ trợ

máy tính.

Hiện nay, các thuật toán đều cố gắng tận dụng đƣợc ƣu điểm của hai phƣơng

pháp này.

Lý thuyết thống kê: các kết quả trong xác suất thống kê là tiền đề cho rất

Các ngành khoa học liên quan đến lĩnh vực học máy điển hình là:

nhiều phƣơng pháp học máy. Đặc biệt, lý thuyết thống kê cho phép ƣớc lƣợng sai số

Các phƣơng pháp tính: các thuật toán học máy thƣờng sử dụng các tính toán

của các phƣơng pháp học máy.

số thực/số nguyên trên dữ liệu rất lớn. Trong đó, các bài toán nhƣ: tối ƣu có/không

Khoa học máy tính: là cơ sở để thiết kế các thuật toán, đồng thời đánh giá

ràng buộc, giải phƣơng trình tuyến tính v.v… đƣợc sử dụng rất phổ biến.

Lĩnh vực học máy truyền thống thƣờng đƣợc chia thành bốn lĩnh vực con:

Học có giám sát: Máy tính đƣợc xem một số mẫu gồm đầu vào và đầu

thời gian chạy, bộ nhớ của các thuật toán học máy.

ra tƣơng ứng trƣớc. Sau khi học xong các mẫu này, máy tính quan sát một đầu vào

Học không giám sát: Máy tính chỉ đƣợc xem các mẫu không có đầu ra, sau

mới và cho ra kết quả.

đó máy tính phải tự tìm cách phân loại các mẫu này và các mẫu mới.

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Học nửa giám sát: Một dạng lai giữa hai nhóm giải thuật trên.

Học tăng cƣờng: Máy tính đƣa ra quyết định hành động và nhận kết quả phản

hồi từ môi trƣờng. Sau đó máy tính tìm cách chỉnh sửa cách ra quyết định hành

động của mình.

Học máy có ứng dụng rộng khắp trong các ngành khoa học/sản xuất, đặc biệt

Xử lý ngôn ngữ tự nhiên (Natural Language Processing): xử lý văn bản, giao

những ngành cần phân tích khối lƣợng dữ liệu khổng lồ. Một số ứng dụng thƣờng thấy:

Nhận dạng (Pattern Recognition): nhận dạng tiếng nói, chữ viết tay, vân tay,

tiếp ngƣời – máy, …

Tìm kiếm (Search Engine)

Chẩn đoán trong y tế: phân tích ảnh X-quang, các hệ chuyên gia chẩn đoán

thị giác máy (Computer Vision) …

Tin sinh học: phân loại chuỗi gene, quá trình hình thành gene/protein

Vật lý: phân tích ảnh thiên văn, tác động giữa các hạt …

Phát hiện gian lận tài chính (financial fraud): gian lận thẻ tỉn dụng

Phân tích thị trƣờng chứng khoán (stock market analysis)

Chơi trò chơi: tự động chơi cờ, hành động của các nhân vật ảo

Rôbốt: là tổng hợp của rất nhiều ngành khoa học, trong đó học máy tạo nên

tự động.

hệ thần kinh/bộ não của ngƣời máy.

Trong đó phải kể đến các ứng dụng quan trọng nhất của nó trong khai phá dữ

liệu. Khai phá dữ liệu (Data mining) là quá trình khám phá các tri thức mới và các

tri thức có ích ở dạng tiềm năng trong nguồn dữ liệu đã có. Khai phá dữ liệu là một

Xác định vấn đề và không gian dữ liệu để giải quyết vấn đề.

Chuẩn bị dữ liệu, bao gồm các quá trình làm sạch dữ liệu, tích hợp dữ liệu,

bƣớc của quá trình khai phá tri thức, bao gồm:

Khai phá dữ liệu: xác định nhiệm vụ khai phá dữ liệu và lựa chọn kĩ thuật

chọn dữ liệu, biến đổi dữ liệu.

khai phá dữ liệu. Kết quả cho ta một nguồn tri thức thô.

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Đánh giá: dựa trên một số tiêu chí tiến hành kiểm tra và lọc nguồn tri thức

Triển khai.

thu đƣợc.

Quá trình khai phá tri thức không chỉ là một quá trình tuần tự từ bƣớc đầu

tiên đến bƣớc cuối cùng mà là một quá trình lặp và có quay trở lại các bƣớc đã qua.

Về cơ bản, khai phá dữ liệu có thể ứng dụng cho bất kỳ kho thông tin nào

bao gồm: Các cơ sở dữ liệu quan hệ, kho dữ liệu, các cơ sở dữ liệu giao tác, các hệ

thống cơ sở dữ liệu tiên tiến, các tệp, ...

Phân lớp dữ liệu

Phân lớp dữ liệu là kĩ thuật dựa trên tập dữ liệu huấn luyện và những giá trị

trong một thuộc tính phân lớp (hay còn gọi là nhãn của lớp), sử dụng nó trong việc

phân lớp dữ liệu mới. Phân lớp cũng là tiên đoán loại lớp của nhãn. Bên cạnh kĩ

thuật phân lớp còn có một hình thức tƣơng tự gọi là kĩ thuật tiên đoán, kĩ thuật tiên

đoán khác với phân lớp ở chỗ phân lớp chỉ liên quan đến tiên đoán loại lớp của nhãn

còn kĩ thuật tiên đoán mô hình những hàm đánh giá liên tục[6].

Kĩ thuật phân lớp đƣợc tiến hành bao gồm 2 bƣớc: Xây dựng mô hình và sử

dụng mô hình.

Xây dựng mô hình: là mô tả một tập những lớp đƣợc định nghĩa trƣớc, trong

đó mỗi bộ hoặc mẫu đƣợc gán thuộc về một lớp đƣợc định nghĩa trƣớc nhƣ là đƣợc

xát định bởi thuộc tính nhãn lớp, tập hợp của những bộ đƣợc sử dụng trong việc sử

dụng mô hình đƣợc gọi là tập huấn luyện. Mô hình đƣợc biểu diễn là những luật

phân lớp, cây quyết định và những công thức toán học .

Sử dụng mô hình: việc sử dụng mô hình phục vụ cho mục đích phân lớp dữ

liệu trong tƣơng lai hoặc phân lớp cho những đối tƣợng chƣa biết đến. Trƣớc khi sử

dụng mô hình ngƣời ta thƣờng phải đánh giá tính chính xác của mô hình, trong đó

nhãn đƣợc biết của mẫu kiểm tra đƣợc so sánh với kết quả phân lớp của mô hình, độ

chính xác là phần trăm của tập hợp mẫu kiểm tra mà phân loại đúng bởi mô hình,

tập kiểm tra là độc lập với tập huấn luyện.

Phân lớp là một hình thức học có giám sát, tức là: tập dữ liệu huấn luyện

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

(quan sát, thẩm định ...) đi đôi với những nhãn chỉ định lớp quan sát, những

dữ liệu mới đƣợc phân lớp dựa trên tập huấn luyện này.

Trong phƣơng pháp học máy truyền thống, để phân lớp dữ liệu ta chỉ sử

dụng một tập dữ liệu đã đƣợc gán nhãn để huấn luyện. Tuy nhiên, để có đƣợc các

mẫu dữ liệu đã đƣợc gán nhãn thƣờng khó khăn, tốn kém thời gian và chi phí hay

nó đòi hỏi những nỗ lực của các chuyên gia. Trong khi đó, dữ liệu chƣa đƣợc gán

nhãn có thể sƣu tầm tƣơng đối dễ dàng, và có một số phƣơng pháp để sử dụng

chúng. Học nửa giám sát đề cập tới vấn đề này bằng cách sử dụng một số lƣợng lớn

các dữ liệu chƣa đƣợc gán nhãn cùng với các dữ liệu đã đƣợc gán nhãn để xây dựng

các bộ phân lớp tốt hơn. Do học nửa giám sát đòi hỏi nỗ lực của con ngƣời ít hơn và

đƣa ra độ chính xác cao, đó là sự quan tâm lớn cả về lý thuyết và thực hành.

Để hiểu bản chất của học nửa giám sát, ta sẽ xem xét các khái niệm về học

có giám sát, học không giám sát và học tăng cƣờng.

1.2. Các phƣơng pháp học máy

1.2.1. Học có giám sát

Học có giám sát là một kỹ thuật của ngành học máy nhằm mục đích xây

dựng một hàm f từ dữ tập dữ liệu huấn luyện (Training data). Dữ liệu huấn

luyện bao gồm các cặp đối tƣợng đầu vào và đầu ra mong muốn. Đầu ra của hàm f

có thể là một giá trị liên tục hoặc có thể là dự đoán một nhãn phân lớp cho một đối

tƣợng đầu vào[8].

Nhiệm vụ của chƣơng trình học có giám sát là dự đoán giá trị của hàm f cho

một đối tƣợng đầu vào hợp lệ bất kì, sau khi đã xét một số mẫu dữ liệu huấn luyện

(nghĩa là các cặp đầu vào và đầu ra tƣơng ứng). Để đạt đƣợc điều này, chƣơng trình

học phải tổng quát hóa từ các dữ liệu sẵn có để dự đoán đƣợc những tình huống

chƣa gặp phải theo một cách hợp lý.

Phƣơng pháp học có giám sát có thể đƣợc mô tả tóm tắt nhƣ sau:

Hệ thống học sẽ quan sát một tập dữ liệu huấn luyện đã đƣợc gán nhãn, bao

gồm các cặp (đặc tính, nhãn), đƣợc biểu diễn bởi {(x1, y1), (x2, y2), ..., (xn, yn)}.

Mục đích nhằm dự đoán nhãn y cho bất kỳ đầu vào mới với đặc tính x. Một nhiệm

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

vụ của học có giám sát đƣợc gọi là hồi quy khi y ∈ ℝ và phân lớp khi y có một tập

các giá trị rời rạc.

Để giải quyết bài toán học có giám sát, ta phải thực hiện các bước sau:

1. Xác định loại dữ liệu huấn luyện: Đầu tiên ta nên xác định xem loại dữ liệu

nào sẽ đƣợc sử dụng làm dữ liệu huấn luyện. Chúng có thể là dữ liệu liên tục hay dữ

liệu rời rạc, hoặc một dạng đặt biệt nào đó.

2. Xây dựng tập dữ liệu huấn luyện: Việc thu thập để tạo nên tập dữ liệu huấn

luyện là quan trọng vì nó sẽ phục vụ cho việc sử dụng hàm huấn luyện f. Dữ liệu

huấn luyện có thể thu thập đƣợc từ nhiều nguồn khác nhau: dữ liệu đầu vào, số liệu

đo đạc, tri thức hay kinh nghiệm của các chuyên gia lĩnh vực,…

3. Biễu diễn các đặc trƣng đầu vào: Sự chính xác của hàm chức năng phụ thuộc

lớn vào cách các đối tƣợng đầu vào đƣợc biểu diễn. Thông thƣờng, đối tƣợng đầu

vào đƣợc chuyển đổi thành một vec-tơ đặc trƣng, chứa một số các đặc trƣng nhằm

mô tả cho đối tƣợng đó. Số lƣợng các đặc trƣng không nên quá lớn nhƣng phải đủ

lớn để việc dự đoán đầu ra đƣợc chính xác.

4. Xác định cấu trúc của hàm chức năng cần tìm và giải thuật học tƣơng ứng.

Ví dụ, có thể lựa chọn việc sử dụng giải thuật K-láng giềng gần nhất hay giải thuật

cây quyết định,…

5. Hoàn thiện thiết kế. Ngƣời kĩ sƣ sẽ chạy giải thuật học từ tập huấn luyện thu

thập đƣợc. Các tham số của giải thuật học có thể đƣợc điều chỉnh bằng cách tối ƣu

hóa hiệu năng trên một tập con (gọi là tập kiểm chứng -validation set) của tập huấn

luyện, hay thông qua kiểm chứng chéo (cross-validation). Sau khi học và điều chỉnh

tham số, hiệu năng của giải thuật có thể đƣợc đo đạc trên một tập kiểm tra độc lập

với tập huấn luyện.

Các thuật toán sử dụng trong học có giám sát nhƣ: Cây quyết định (Decision Trees),

Máy véc tơ hỗ trợ (Support Vector Machine (SVM)), k-láng giềng gần nhất (k-

Nearest Neighbor), Cực đại Entropy (Maximum Entropy (MaxEnt)), Naive Bayes,...

1.2.2. Học không giám sát

Học không giám sát là một phƣơng pháp của ngành học máy nhằm tìm ra

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

một mô hình phù hợp với các quan sát. Nó khác với học có giám sát ở chỗ là đầu ra

đúng tƣơng ứng cho mỗi đầu vào là không biết trƣớc. Trong học không giám sát,

một tập dữ liệu đầu vào đƣợc thu thập. Học không giám sát thƣờng đối xử với các

đối tƣợng đầu vào nhƣ là một tập các biến ngẫu nhiên. Sau đó, một mô hình mật

độ kết hợp sẽ đƣợc xây dựng cho tập dữ liệu đó[8].

Học không giám sát có thể đƣợc dùng kết hợp với suy diễn Bayes (Bayesian

inference) để cho ra xác suất có điều kiện (nghĩa là học có giám sát) cho bất kì biến

ngẫu nhiên nào khi biết trƣớc các biến khác.

Học không giám sát cũng hữu ích cho việc nén dữ liệu: về cơ bản, mọi giải

thuật nén dữ liệu hoặc là dựa vào một phân bố xác suất trên một tập đầu vào một

cách tƣờng minh hoặc không tƣờng minh.

Phân cụm dữ liệu

Một ứng dụng khác của học không giám sát là phân cụm dữ liệu (data

clustering). Phân cụm đƣợc xem nhƣ vấn đề quan trọng nhất trong học không giám

sát, vì nhƣ các vấn đề khác của phân cụm dữ liệu, nó có liên quan tới việc tìm kiếm

một cấu trúc trong một tập các dữ liệu không có nhãn[3].

Một định nghĩa rộng hơn về phân cụm: “ phân cụm là quá trình tổ chức các

đối tƣợng dữ liệu vào trong các nhóm trong đó các đối tƣợng giống nhau theo một

cách nào đó”. Do đó, một cụm là một tập hợp các đối tƣợng mà giữa chúng có sự

giống nhau và khác với các đối tƣợng thuộc về các cụm khác.

Hình 1.1: Phƣơng pháp phân cụm dữ liệu.

Trong ví dụ trên, chúng ta có thẻ dễ dàng xác định đƣợc 4 cụm mà trong đó

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

dữ liệu đƣợc phân chia. Tiêu chí giống nhau ở đây là “khoảng cách”, hai hay nhiều

đối tƣợng thuộc về một cụm nếu chúng gần nhau hơn dựa theo khoảng cách đƣa ra.

Điều này gọi là phân cụm dựa trên khoảng cách.

Một dạng khác của phân cụm là Phân cụm khái niệm, hai hay nhiều đối

tƣợng thuộc về một cụm nếu ta định nghĩa một khái niệm phổ biến cho tất cả các

đối tƣợng. Tóm lại, các đối tƣợng đƣợc nhóm lại theo điều kiện mô tả chúng.

Mục đích của phân cụm dữ liệu

Mục đích của việc phân cụm dữ liệu là để xác định các nhóm trong một tập

các dữ liệu không có nhãn. Nhƣng làm thế nào để quyết định đƣợc điều gì tạo nên

việc phân cụm tốt. Có thể nói rằng, không có một tiêu chuẩn tuyệt đối nào là tốt

nhất, do đó ngƣời sử dụng phải đƣa ra các tiêu chuẩn này để các dữ liệu sau khi

đƣợc phân cụm sẽ phù hợp với yêu cầu của ngƣời sử dụng.

Các ứng dụng của Phân cụm dữ liệu

Các thuật toán phân cụm dữ liệu có thể áp dụng trong nhiều lĩnh vực, ví dụ nhƣ:

Tiếp thị: việc tìm ra các nhóm khách hàng có hành vi giống nhau sẽ đƣa ra

một CSDL lớn chứa thông tin khách hàng và thông tin mua sắm của họ.

Sinh học: phân loại động vật và thực vật dựa trên các đặc trƣng của chúng

Thƣ viện: đặt sách

www: phân lớp văn bản, phân cụm dữ liệu weblog để xác định các nhóm

ngƣời truy cập tƣơng tự nhau.

Các yêu cầu với thuật toán phân cụm:

Các yêu cầu chính mà một thuật toán phân cụm cần đáp ứng là:

Khả năng mở rộng

Đối xử với các loại thuộc tính khác nhau của đối tƣợng dữ liệu

Phát hiện ra các cụm với hình dạng có thể là bất kỳ.

Tối thiểu hóa yêu cầu cho miền tri thức để xác định các tham số đầu vào.

Khả năng xử lý các dữ liệu tạp và sự chênh lệch,...

Các thuật toán đƣợc sử dụng phổ biến nhất hiện nay: K-means, Fuzzy C-means,

Phân cụm có thứ bậc, Hỗn hợp Gaussian.

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

1.2.3. Học tăng cƣờng

Học tăng cƣờng là một lĩnh vực con của ngành học máy, nghiên cứu cách

thức để một Agent nên chọn thực hiện các hành động nào trong một “môi

trƣờng” để cực đại hóa số “phần thƣởng” nào đó. “Môi trƣờng” trong học tăng

cƣờng đƣợc biểu diễn dƣới dạng một quá trình trạng thái quyết định hữu hạn

Markov (Markov decision process – MDP)[8].

Cụ thể hơn, trong học tăng cƣờng, các Agent tƣơng tác với môi trƣờng của

nó bằng cách đƣa ra các hành động a1, a2, ... Những hành động này ảnh hƣởng tới

trạng thái của môi trƣờng do đó kết quả nhận đƣợc trong Agent lần lƣợt là số phần

thƣởng hoặc hình phạt r1, r2,... Mục đích của Agent là học một hành động trong một

cách nào đó để cực đại hóa thuộc tính phần thƣởng nó nhận đƣợc (hay cực tiểu hóa

rủi ro) trên vòng đời của nó.

Khác với học có giám sát, học tăng cƣờng không có các cặp dữ liệu vào hay

kết quả đúng, các hành động gần tối ƣu cũng không đƣợc đánh giá đúng sai một

cách tƣờng minh.

Mô hình học tăng cƣờng[9] bao gồm các thành phần sau:

- Tập các trạng thái môi trƣờng, ký hiệu là: S

- Tập các hành động, ký hiệu là: A

- Tập các phần thƣởng, ký hiệu: ℝ

Quá trình học nhƣ sau:

Tại mỗi thời điểm t, Agent có trạng thái môi trƣờng là st ∈ S và tập các hành

động có thể chọn A(st). Nó chọn một hành động a ∈ A(st) và nhận đƣợc từ môi

trƣờng một trạng thái mới st+1 và một phần thƣởng rt+1. Với việc học nhƣ vậy, agent

phải phát triển một hàm học π: S → A có tác dụng cực đại hóa số lƣợng phần

thƣởng thu đƣợc: R = r0 + r1 + .. + rn với các MDP có một trạng thái kết thúc, hoặc lƣợng R = Σtγtrt với các MDP không có trạng thái kết thúc (trong đó γ là một hệ số giảm " phần thƣởng trong tƣơng lai" nào đó, với giá trị trong khoảng từ 0 đến 1).

Học tăng cƣờng có liên quan mật thiết với lý thuyết quyết định và lý thuyết

điều khiển, do đó đƣợc áp dụng trong các bài toán nhƣ: điều khiển rô bốt, điều vận

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

thang máy, trò chơi cờ vua, ...

Một kỳ thủ cờ vua muốn đi một nƣớc cờ. Sự lựa chọn đƣợc đƣa ra sẽ dựa

Ví dụ về học tăng cường:

trên cả việc lập kế hoạch cho nƣớc cờ mình đi, dự đoán các nƣớc cờ tiếp theo của

Một con rô bốt di động quyết định có nên đi vào một căn phòng mới để tìm

đối thủ và xác định số nƣớc cờ của đối thủ sẽ đi một cách tức thì.

kiếm đƣờng về trạm sạc pin của nó. Nó đƣa ra quyết định dựa trên việc làm thế nào

để có thể tìm đƣợc trạm sạc pin trong quá khứ một cách nhanh chóng và dễ dàng.

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

1.2.4.1. Tổng quan về học nửa giám sát

Ban đầu, học nửa giám sát giả sử có hai lớp và mỗi lớp có một phân phối

Gaussian. Điều này giả sử rằng dữ liệu hoàn chỉnh xuất phát từ một mô hình hỗn

hợp. Với số lƣợng lớn các dữ liệu chƣa gán nhãn, các thành phần hỗn hợp có thể

đƣợc xác định với thuật toán EM (Expectation-Maximization). Thuật toán này chỉ

cần một mẫu dữ liệu đã gán nhãn trong số các thành phần để xác định đầy đủ mô

hình hỗn hợp. Mô hình này đã đƣợc áp dụng thành công để phân loại văn bản.

Một biến thể khác là phƣơng pháp tự huấn luyện (Self-traning): Một bộ phân

lớp ban đầu huấn luyện với các dữ liệu đã gán nhãn. Sau đó nó đƣợc sử dụng để

phân lớp các dữ liệu chƣa gán nhãn. Các điểm chƣa đƣợc gán nhãn cùng với các

nhãn đã đƣợc dự đoán sẽ đƣợc thêm vào tập huấn luyện. Bộ phân lớp sẽ huấn luyện

lại và quá trình này đƣợc lặp đi lặp lại. Lƣu ý rằng, bộ phân lớp sử dụng các dự

đoán của nó để dạy chính bản thân nó. Có một phiên bản khó của mô hình hỗn hợp

và thuật toán EM. Phƣơng thức đó cũng đƣợc gọi là “Tự dạy” hay bootstrapping.

Nó cho rằng lỗi phân lớp có thể tăng cƣờng cho nó.

Cả hai phƣơng pháp đã đƣợc sử dụng từ lâu nhƣng vẫn phổ biến vì khái niệm

và thuật toán của chúng đơn giản.

Phƣơng pháp Co-training làm giảm các lỗi của phƣơng pháp Self-training.

Phƣơng pháp này giả sử rằng các đặc tính của một mẫu dữ liệu có thể đƣợc chia

thành hai tập con. Mỗi tập con đặc tính đủ để huấn luyện một bộ phân lớp tốt, và tập

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

con thứ hai là điều kiện độc lập để đƣa ra phân lớp. Ban đầu, hai bộ phân lớp huấn

luyện với dữ liệu đã gán nhãn, mỗi bộ huấn luyện trên một tập con. Mỗi bộ phân

lớp sau đó lặp lại việc phân lớp với dữ liệu chƣa gán nhãn và dạy bộ phân lớp khác

với các dự đoán của nó.

Phƣơng pháp TSVM (Transductive Support Vector Machine) đƣợc biết đến

nhƣ việc mở rộng để chuẩn hóa SVM cho lĩnh vực học nửa giám sát. TSVM tìm

một cách gán nhãn cho tất cả các dữ liệu chƣa gán nhãn và sự phân chia đồng đều,

ví dụ nhƣ lề cực đại đạt đƣợc trên cả dữ liệu đã gán nhãn và dữ liệu chƣa gán nhãn.

Phƣơng pháp học nửa giám sát dựa trên đồ thị (Graph-based) hiện nay đã thu

hút số lƣợng lớn các nhà nghiên cứu. Các phƣơng pháp học nửa giám sát dựa trên

đồ thị bắt đầu với một đồ thị mà tại đó các đỉnh là các điểm dữ liệu đã đƣợc gán

nhãn và chƣa đƣợc gán nhãn, và các cạnh (có trọng số) phản ánh sự tƣơng tự của

các đỉnh. Giả sử, các đỉnh đƣợc kết nối với nhau bởi một cạnh có trọng số lớn thì có

khuynh hƣớng có cùng nhãn, các nhãn có thể lan truyền thông qua đồ thị. Các giải

thuật dựa trên đồ thị đƣợc thừa hƣởng từ lý thuyết quang phổ đồ thị[10].

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

Học nửa giám sát là một trong số các kỹ thuật học máy, sử dụng cả dữ liệu

đã đƣợc gán nhãn và dữ liệu chƣa đƣợc gán nhãn cho việc huấn luyện, điển hình là

một tập hợp nhỏ dữ liệu đƣợc gán nhãn kết hợp với một số lƣợng lớn các dữ liệu

chƣa gán nhãn. Học nửa giám sát nằm giữa học không giám sát và học có giám sát.

Nhiều nhà nghiên cứu về học máy đã tìm ra dữ liệu chƣa đƣợc gán nhãn trong khi

kết hợp với một lƣợng nhỏ dữ liệu đã đƣợc gán nhãn. Việc thu đƣợc dữ liệu gán

nhãn cho bài toán học thƣờng yêu cầu kỹ năng cao của con ngƣời để tự phân loại dữ

liệu huấn luyện. Các chi phí liên quan tới quá trình gán nhãn có thể làm cho một tập

dữ liệu gán nhãn không khả thi, trong khi mua lại dữ liệu không có nhãn chi phí

tƣơng thấp. Do đó, học nửa giám sát có thể mang lại giá trị thực tiễn lớn.

Với ý tƣởng nhƣ vậy, học nửa giám sát đƣợc áp dụng cho việc phân lớp dữ

liệu. Trong bài toán phân lớp dữ liệu nửa giám sát, các mẫu dữ liệu có đặc tính

tƣơng tự nhau thì sẽ đƣợc phân vào cùng một lớp. Ta có thể mô tả khái quát bài

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

toán phân lớp nhị phân nhƣ sau:

Rm • Cho tập dữ liệu: X = {x1..xℓ, xℓ+1..xn}

• Tập các nhãn: L = {0,1}

• Ban đầu, các dữ liệu đã đƣợc gán nhãn yi {0,1}, i=1,..,ℓ

• Với các dữ liệu từ xℓ+1..xn , các nhãn yi là chƣa biết.

Mục đích của bài toán là gán nhãn cho các dữ liệu chƣa có nhãn dựa trên tập

dữ liệu đã cho.

1.3. Một số phƣơng pháp học nửa giám sát

1.3.1. Phƣơng pháp tự huấn luyện

Tự huấn luyện (Self-training) là một phƣơng pháp phổ biến ra đời vào những

năm 1960 đến 1970, đƣợc sử dụng trong lĩnh vực học nửa giám sát. Trong phƣơng

pháp này, một bộ phân lớp ban đầu sẽ huấn luyện số lƣợng ít các dữ liệu đã gán

nhãn. Bộ phân lớp sau đó đƣợc sử dụng để phân lớp cho các dữ liệu chƣa gán nhãn.

Thông thƣờng các điểm chƣa gán nhãn cùng với các nhãn dự đoán của chúng sẽ

đƣợc thêm vào tập dữ liệu huấn luyện. Bộ phân lớp huấn luyện lại và quá trình này

đƣợc lặp lại. Lƣu ý rằng bộ phân lớp sử dụng dự đoán của nó để dạy cho chính nó.

Quá trình này cũng đƣợc gọi là self-teaching hay bootstrapping[9].

ℓ+1.

Thuật toán Self-training: Đầu vào : - Tập dữ liệu đã gán nhãn {(xi, yi)}ℓ i=1. - Tập dữ liệu chƣa gán nhãn {(xj)}ℓ+u j=

i=1 , và U={(xj)}ℓ+u

j=

ℓ+1.

Thuật toán :

1. Khởi tạo, đặt L={(xi, yi)}ℓ 2. Lặp:

3. Huấn luyện f từ tập L sử dụng một phƣơng pháp học có giám sát.

4. Dự đoán nhãn cho các phần tử x ∈ U.

5. Bỏ đi tập con S từ tập U chứa các dữ liệu vừa đƣợc gán nhãn, đồng

thời thêm vào tập L các mẫu dữ liệu này và nhãn của chúng (thêm {(x,

f(x))| xϵS} vào L).

Ƣu điểm:

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

- Là phƣơng pháp học nửa giám sát đơn giản nhất.

- Đƣợc xem nhƣ là phƣơng pháp “Bao trùm” (Wrapper), áp dụng cho các bộ

phân lớp sẵn có.

- Thƣờng đƣợc ứng dụng trong thực tế vào việc xử lý ngôn ngữ tự nhiên, phân

lớp văn bản,…

Độ phức tạp của thuật toán

Giả sử dữ liệu đầu vào bao gồm:

ℓ: số lƣợng dữ liệu đã gán nhãn.

u: số lƣợng dữ liệu chƣa gán nhãn (u ≫ ℓ).

n = ℓ + u : tổng số lƣợng dữ liệu.

Độ phức tạp của thuật toán tự huấn luyện dựa trên việc đánh giá quá trình lặp ở

bƣớc 2:

- Huấn luyện f từ tập L sử dụng một phƣơng pháp học có giám sát.

- Dự đoán nhãn cho các phần tử x ∈ U.

- Bỏ đi tập con S từ tập U chứa các dữ liệu vừa đƣợc gán nhãn, đồng thời thêm

vào tập L các mẫu dữ liệu này và nhãn của chúng (thêm {(x, f(x))| x S} vào L).

- Thuật toán thực hiện số vòng lặp nhiều nhất có thể là: u vòng lặp. Trong đó:

Vòng lặp thứ nhất có độ phức tạp: O (ℓ).

Vòng lặp thứ hai có độ phức tạp là: O (ℓ + 1).

..........................................................................

Vòng lặp thứ u có độ phức tạp là: O (ℓ+u−1).

Do đó thuật toán có độ phức tạp là:

O (ℓ) + O (ℓ +1) + ... + O (ℓ +u−1) = O(ℓ +u−1). (O (ℓ +u) − O (ℓ))/ 2.

= O(ℓ +u−1). O (u) / 2. ≈ O(n2).

1.3.2. Phƣơng pháp đồng huấn luyện

Đồng huấn luyện (Co-training) là một kỹ thuật học nửa giám sát yêu cầu hai

Khung nhìn dữ liệu (View). Nó giả sử rằng mỗi mẫu dữ liệu đƣợc mô tả bằng cách

sử dụng hai bộ đặc tính khác nhau, đƣợc cung cấp khác nhau, bổ sung thông tin về

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

mẫu dữ liệu đó. Lý tƣởng nhất, hai khung nhìn đƣợc xem là điều kiện độc lập (ví

dụ: hai bộ đặc tính của mỗi mẫu dữ liệu là điều kiện độc lập để đƣa ra phân lớp của

chúng) và mỗi khung nhìn là đủ (ví dụ: phân lớp của một mẫu dữ liệu có thể đƣợc

dự đoán chính xác từ mỗi khung nhìn độc lập). Co-training ban đầu học một bộ

phân lớp riêng cho mỗi khung nhìn, sử dụng bất kỳ mẫu dữ liệu đã gán nhãn nào.

Những dự đoán gần đúng nhất của mỗi bộ phân lớp trên các dữ liệu chƣa gán nhãn

sau đó đƣợc sử dụng lặp đi lặp lại để xây dựng thêm các dữ liệu đƣợc gán nhãn[9].

Phƣơng pháp

Giả sử các dữ liệu đƣa ra đã đƣợc gán nhãn nhƣ sau:

- Dữ liệu đã gán nhãn : (x1, y1),..., (xℓ, yℓ).

- Dữ liệu chƣa gán nhãn : xℓ+1, ..., xℓ+u .

- Hàm học f: x ⟼y.

Giả sử véc tơ đặc trƣng X có thể đƣợc chia thành hai Khung nhìn (View) nhƣ sau:

Huấn luyện hai bộ học cơ bản f(1): x(1) ⟼y và f(2): x(2) ⟼y

ℓ, yℓ)

Đầu tiên, học từ các dữ liệu đã gán nhãn:

1, y1),..., (x(1) 1, y1),..., (x(2)

ℓ, yℓ)

o f(1) học trên (x(1) o f(2) học trên (x(2)

Sau đó, sử dụng lặp lại các dữ liệu chƣa gán nhãn:

o f(1) phân lớp các điểm chƣa gán nhãn mà hầu hết chứa các điểm rỗng. o f(1) thêm điểm này vào tập các nhãn của f(2) f(2) lặp lại nhƣ f(1) tới khi dữ liệu đƣợc gán nhãn hết thì dừng.

 Ƣu điểm của phƣơng pháp Co-training

o Là một phƣơng pháp đơn giản, đƣợc áp dụng cho hầu hết các bộ phân lớp

hiện nay.

o Ít xảy ra lỗi hơn so với phƣơng pháp Self-training.

 Nhƣợc điểm của phƣơng pháp Co-training

o Các Khung nhìn đƣợc chia tách có thể tồn tại hoặc không tồn tại.

o Mô hình sử dụng cả hai Khung nhìn có thể sẽ tốt hơn.

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Ví dụ về phân lớp trang web với phƣơng pháp Co-training

Một ứng dụng của Co-training là sử dụng để phân lớp các trang web bằng

cách sử dụng các văn bản trên các trang nhƣ một Khung nhìn. Đơn giản chỉ cần đặt

văn bản trong một siêu liên kết trên một trang có thể đƣa ra thông tin về trang web

đó liên kết tới. Co-training có thể làm việc trên các văn bản chƣa gán nhãn mà chƣa

đƣợc phân lớp hay gắn thẻ, điển hình cho các văn bản xuất hiện trên các trang web

và email. Các đặc trƣng mô tả một trang web là các từ ngữ trên trang web đó và các

liên kết trỏ tới trang web đó. Mô hình Co-training sử dụng cả hai bộ phân lớp để xác

định rằng một trang web sẽ chứa dữ liệu liên quan đến các tiêu chí tìm kiếm. Văn

bản trên các trang web có thể đánh giá sự phù hợp của bộ phân lớp liên kết.

Bài toán đƣợc đƣa ra là: Có một tập các trang web, nhiệm vụ của chúng ta là

huấn luyện một chƣơng trình để tìm ra các trang web có cùng một đặc điểm nào đó

(phân lớp). Tuy nhiên, chi phí để có đƣợc các trang web đã đƣợc gán nhãn là lớn.

Vậy câu hỏi đặt ra là chúng ta chỉ có thể gán nhãn cho một vài trang web và sử dụng

dữ liệu chƣa đƣợc gán nhãn để phục vụ cho việc gán nhãn cho các trang tiếp theo.

Với bài toán này, phƣơng pháp Co-training có 2 bộ học sử dụng 2 Khung

nhìn của dữ liệu đã gán nhãn và chƣa gán nhãn.

Hai Khung nhìn của dữ liệu nhƣ sau: Phần văn bản (Page text) và Phần liên

kết (Link)

Hình 1.2: Khung nhìn dữ liệu giữa văn bản và liên kết

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Hình 1.3: Dữ liệu đƣợc học theo phƣơng pháp Co-training.

1.3.3. Phƣơng pháp Máy véc tơ hỗ trợ truyền dẫn

Để đề cập đến phƣơng pháp máy véc tơ hỗ trợ truyền dẫn (Transductive

Support Vector Machine-TSVM) trƣớc hết ta xem xét phƣơng pháp Máy véc tơ hỗ

trợ (Support Vector Machines -SVM). Phƣơng pháp SVM là một phƣơng pháp phân

lớp nhị phân, ra đời từ lý thuyết học thống kê, do Vapnik và Chervonenkis xây

dựng. Phƣơng pháp SVM có nhiều ứng dụng trong thực tế với các bài toán phân lớp

nhƣ: nhận dạng văn bản, nhận dạng chữ viết tay, phát hiện mặt ngƣời trong các ảnh

và ƣớc lƣợng hồi quy,...[8].

Trong phƣơng pháp SVM, một máy hỗ trợ vector xây dựng một siêu mặt

phẳng hay một tập các siêu mặt phẳng trong một không gian nhiều chiều. Bằng trực

giác, để phân lớp tốt nhất thì các siêu mặt phẳng nằm ở càng xa các điểm dữ liệu

của tất cả các lớp thì càng tốt, tức là lề (margin) càng lớn thì sai số tổng quát của

thuật toán phân lớp càng nhỏ.

Thuật toán đƣợc cho trƣớc một số điểm dữ liệu đã đƣợc gán nhãn thuộc một

trong hai lớp (giả sử là lớp −1 và lớp +1). Mục tiêu của thuật toán là xác định xem

một điểm dữ liệu mới sẽ thuộc về lớp nào. Mỗi điểm dữ liệu sẽ đƣợc biểu diễn dƣới

dạng một vector d chiều, và ta muốn biết liệu có thể chia tách hai lớp dữ liệu bằng

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

một siêu phẳng d – 1 chiều hay không?. Đây gọi là phân lớp tuyến tính. Có nhiều

siêu mặt phẳng có thể phân lớp đƣợc dữ liệu. Ở đây ta xét siêu mặt phẳng có lề cực

đại giữa hai lớp (Maximum margin).

Hình 1.4: Phƣơng pháp Máy véc tơ hỗ trợ

Giả sử, cho tập dữ liệu huấn luyện T gồm n phần tử có dạng sau:

T={(xi, yi) | xi ∈ ℝd , yi ∈ {−1, 1}} với i=1..n

Trong đó yi xác định lớp của điểm xi, yi nhận giá trị −1 hoặc +1. Mỗi xi là

một vectơ thực d chiều. Ta cần tìm siêu phẳng có lề cực đại chia tách các điểm

có yi=−1 và các điểm có yi=1.

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

w.x − b = 0. Trong đó dấu chấm ( ) kí hiệu của tích vô hƣớng và w là một vectơ

pháp tuyến của siêu phẳng.

Tham số xác định khoảng cách giữa gốc tọa độ và siêu phẳng theo

hƣớng vectơ pháp tuyến của w.

Nhiệm vụ của chúng ta là cần chọn w và b sao cho lề đạt cực đại, hay

khoảng cách giữa hai siêu mặt phẳng song song ở xa nhau nhất có thể trong khi vẫn

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

phân loại đƣợc dữ liệu. Hai siêu mặt phẳng đƣợc xác định bằng phƣơng trình sau:

w.x− b =1 và w.x− b =−1

Chú ý rằng nếu dữ liệu huấn luyện có thể đƣợc chia tách một cách tuyến tính,

thì ta có thể chọn hai siêu phẳng của lề sao cho không có điểm nào ở giữa chúng và

sau đó tăng khoảng cách giữa chúng đến tối đa có thể. Bằng hình học, ta tìm đƣợc

khoảng cách giữa hai siêu phẳng là . Vì vậy ta phải cực tiểu hóa giá trị ||w||. Để

đảm bảo không có điểm dữ liệu nào trong lề, ta thêm vào các điều kiện sau, với

mỗi i ta có:

w.xi –b >1 cho xi thuộc lớp thứ nhất (+1).

hoặc

w.xi –b <−1 cho xi thuộc lớp thứ hai (-1).

Có thể viết gọn lại nhƣ sau với mọi 1 ≤ i ≤ n, yi(w.xi −b) ≥1 (1)

Tóm lại, ta có bài toán tối ƣu hóa sau: Cực tiểu hóa ||W|| (theo w, b) với điều kiện

(với mọi i=1,..., n) yi(w.xi −b) ≥1.

Tuy nhiên bài toán tối ƣu này tƣơng đối khó giải vì hàm mục tiêu phụ thuộc vào

||w||, là một hàm có khai căn. Tuy nhiên có thể thay ||w|| bằng hàm mục tiêu 1/2||w||2 (hệ số 1/2 để tiện cho các biến đổi toán học sau này) mà không làm thay đổi

lời giải (lời giải của bài toán mới và bài toán ban đầu có cùng w và b). Đây là một

bài toán quy hoạch toàn phƣơng. Cụ thể:

Bằng cách thêm các nhân tử Lagrange α, bài toán trên trở thành

nghĩa là ta cần tìm một điểm nằm trên lề để thỏa mãn điều kiện trên. Khi đó, tất cả

các điểm không nằm trên lề, nghĩa là yi(w.xi −b) >1 đều không ảnh hƣởng đến giá

trị hàm mục tiêu vì ta có thể chọn αi =0.

Có thể giải bài toán này bằng các kĩ thuật thông thƣờng cho quy hoạch toàn

phƣơng. Theo điều kiện Karush–Kuhn–Tucker, lời giải có thể đƣợc viết dƣới dạng

tổ hợp tuyến tính của các vectơ huấn luyện.

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Chỉ có một vài αi nhận giá trị > 0. Các điểm xi tƣơng ứng là các vectơ hỗ trợ nằm

trên lề và thỏa mãn yi(w.xi −b) = 1 . Từ điều kiện này, ta nhận thấy

w.xi – b = 1/yi = yi ⟺w.xi −yi

từ đó ta suy ra đƣợc giá trị b. Trên thực tế, Cách tốt hơn để tính b là tính giá trị

trung bình từ tất cả NSV vectơ hỗ trợ:

Máy véc tơ hỗ trợ truyền dẫn

Phƣơng pháp TSVM tìm kiếm sự tách biệt lớn nhất giữa các dữ liệu đã gán

nhãn và chƣa gán nhãn thông qua quy chuẩn. Trong các nghiên cứu thực nghiệm,

nó thực hiện tốt với phân lớp văn bản, tuy nhiên có thể thực hiện tồi hơn phƣơng

pháp SVM trong một số ứng dụng khác.

TSVM đƣợc xem nhƣ sự mở rộng của phƣơng pháp SVM chuẩn (Vapnik,

1998) với dữ liệu chƣa gán nhãn. Trong phƣơng pháp SVM chuẩn, chỉ có dữ liệu đã

gán nhãn là đƣợc sử dụng, mục đích là tìm ra một lề cực đại. Trong TSVM dữ liệu

chƣa gán nhãn cũng đƣợc sử dụng. Mục đích là tìm ra nhãn cho các dữ liệu chƣa

gán nhãn, do đó một lề cực đại trên cả dữ liệu đã gán nhãn gốc và dữ liệu chƣa gán

nhãn (sẽ đƣợc gán nhãn về sau này). Đƣờng biên quyết định có lỗi tổng quát nhỏ

nhất giới hạn trên dữ liệu chƣa gán nhãn. Bằng trực giác, dữ liệu chƣa gán nhãn chỉ

ra ranh giới giữa các vùng dữ liệu dày đặc. Tuy nhiên, việc tìm ra chính xác giải

pháp TSVM là NP-Khó.

= {Xj} (trong đó j

Phƣơng pháp: Trong học nửa giám sát, một tập dữ liệu đã đƣợc gán nhãn (Xℓ, Yℓ) = {(Xi, Yi)} ( trong đó I = [1, nℓ] ), và một tập dữ liệu chƣa đƣợc gán nhãn X

= [nℓ+1, n]) và n = nℓ + n . Ở đây Xi = ( Xi1,..., Xip) là các vector đầu vào d-chiều

và Yi ∈ {−1, 1}, phân phối độc lập và giống nhau, theo một bảng phân phối không

biết trƣớc P(x, y) và X đƣợc phân phối theo P(x).

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Hình 1.5: Phƣơng pháp máy vecto hỗ trợ truyền dẫn

Trong hình trên, các dữ liệu chƣa gán nhãn giúp cho việc đặt đƣờng biên quyết định

trong vùng dữ liệu thƣa. Chỉ với dữ liệu đã gán nhãn, ranh giới lề cực đại đƣợc vẽ

bởi đƣờng nét đứt. Với các dữ liệu chƣa gán nhãn (chấm đen) ranh giới lề cực đại

đƣợc vẽ bởi đƣờng nét liền.

TSVM sử dụng một ý tƣởng là cực đại hóa khoảng cách giữa dữ liệu đã gán

nhãn và dữ liệu chƣa gán nhãn, đƣợc biểu diễn nhƣ sau:

Trong đó: f là một hàm quyết định trong ℱ-một lớp các hàm đƣợc đề xuất,

L(z)=(1−z)+ là hinge loss, và J(f) là nghịch đảo của lề (margin). Với trƣờng hợp tuyến tính: f(x)=wTx + b và J(f)=1/2||w||2 Với trƣờng hợp phi tuyến: f(x)=(K(x, x1),…, K(x, xn) )wT + b, J(f)=1/2wTKw Trong đó K là một hạt nhân đáp ứng điều kiện Mercer, để đảm bảo wTKw

với K= (K(xi, xj)), i, j=1..n trở thành một chuẩn đúng.

1.3.4. Phƣơng pháp dựa trên đồ thị

Phƣơng pháp Graph-based với các điểm dữ liệu đã gán nhãn và chƣa gán

nhãn đƣợc xem nhƣ các đỉnh của một đồ thị, mục đích của chúng ta là dựa vào các

dữ liệu đã gán nhãn, kết hợp với các thuật toán học nửa giám sát dựa trên đồ thị để

gán nhãn cho các dữ liệu chƣa có nhãn, thông thƣờng việc gán nhãn này dựa trên tƣ

tƣởng các đỉnh gần nhau hơn và đƣợc kết nối bởi cạnh có trọng số cao hơn thì sẽ có

nhãn tƣơng tự nhau.

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Hình 1.6: Minh họa đồ thị đƣợc gán nhãn

Tóm tắt ý tƣởng của phƣơng pháp dựa trên đồ thị:

- Xây dựng một đồ thị kết nối các điểm dữ liệu tƣơng tự nhau.

- Cho các nhãn ẩn đi hoặc quan sát các nhãn nhƣ các biến ngẫu nhiên trên đồ thị.

- Bằng trực quan, các điểm dữ liệu “tƣơng tự” nhau thì có nhãn giống nhau.

- Thông tin đƣợc lan truyền từ các điểm dữ liệu đã đƣợc gán nhãn tới các điểm

chƣa đƣợc gán nhãn.

Xây dựng đồ thị:

- Các đỉnh: là các dữ liệu nằm trong tập dữ liệu có nhãn và chƣa có nhãn L∪U. Trong bài toán phân lớp nhị phân, tập nhãn y ∈ {0, 1}n

- Các cạnh: đƣợc đƣa ra dƣới dạng ma trận trọng số đối xứng Wn×n.

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

- Hàm năng lƣợng: . Với các đỉnh có nhãn tƣơng tự

nhau thì hàm năng lƣợng đạt giá trị thấp và ngƣợc lại.

Ƣu điểm:

- Có nền tảng toán học rõ ràng

- Hiệu suất thuật toán cao nếu đồ thị phù hợp với các yêu cầu của thuật toán.

- Ma trận nghịch đảo của Laplace đƣợc xem là ma trận hạt nhân.

- Có thể mở rộng phƣơng pháp này cho các đồ thị có hƣớng.

Nhƣợc điểm:

- Hiệu suất của thuật toán là tồi nếu đồ thị là tồi.

- Dễ thay đổi nếu cấu trúc đồ thị và các trọng số cạnh khi có sự thay đổi các

đỉnh.

1.4. Kết luận

Trong chƣơng này, chúng ta đã nghiên cứu tổng quan về học có giám sát, học

không giám sát và học nửa giám sát. Đồng thời nghiên cứu một số phƣơng pháp học

nửa giám sát phổ biến hiện nay nhƣ: Self-training, Co-training, TSVM, Graph-

based. Mỗi phƣơng pháp có phạm vi ứng dụng khác nhau do đó để áp dụng chúng

vào các bài toán thực tế thì cần xác định yêu cầu bài toán để sử dụng một trong số

các phƣơng pháp trên cho hiệu quả, chẳng hạn nhƣ: nếu chúng ta muốn tạo ra các

cụm dữ liệu tốt thì phƣơng pháp EM với mô hình sinh hỗn hợp là sự lựa chọn tối

ƣu; Nếu các đặc trƣng của dữ liệu đƣợc chia thành hai khung nhìn thì phƣơng pháp

co-training là thích hợp; Nếu hai điểm dữ liệu với các tính năng giống nhau sẽ có

khuynh hƣớng thuộc cùng một lớp thì phƣơng pháp Graph-based đƣợc sử dụng;

Nếu chúng ta đã sử dụng phƣơng pháp SVM thì TSVM là một sự mở rộng của nó;

Còn nếu đã có bộ phân lớp có giám sát phức tạp và khó thay đổi thì nên sử dụng

phƣơng pháp Self-training.

Ở phần tiếp theo, chúng ta sẽ tập trung nghiên cứu phƣơng pháp dựa trên đồ thị

(Graph-based) và các thuật toán trong nó để phân lớp các đối tƣợng dữ liệu đƣợc

xây dựng trên một đồ thị.

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

CHƢƠNG 2:

PHƢƠNG PHÁP HỌC NỬA GIÁM SÁT DỰA TRÊN ĐỒ THỊ

2.1. Giới thiệu

Nhƣ chúng ta đã biết, dữ liệu đã gán nhãn là thiết yếu cho việc học có giám

sát, tuy nhiên chúng thƣờng ở dạng có sẵn với số lƣợng ít, trong khi đó dữ liệu chƣa

đƣợc gán nhãn thì rất phong phú. Việc sử dụng dữ liệu chƣa đƣợc gán nhãn kết hợp

với dữ liệu đã gán nhãn là vấn đề đang đƣợc quan tâm cả về lý thuyết và thực tế. Đã

có rất nhiều phƣơng pháp đƣợc đề xuất hiện nay, giữa chúng có mối quan hệ đầy

hứa hẹn tƣơng tự nhƣ phƣơng pháp K-Nearest Neighbor (kNN) trong học có giám

sát truyền thống. Những phƣơng pháp này giả sử rằng những điểm dữ liệu gần nhau

hơn thì có khuynh hƣớng có cùng nhãn. Chúng lan truyền các nhãn thông qua các

vùng dữ liệu dày đặc chƣa đƣợc gán nhãn.

Gần đây, phƣơng pháp học nửa giám sát dựa trên đồ thị đã thu hút sự quan

tâm rất lớn của các nhà nghiên cứu. Phƣơng pháp với một đồ thị mà tại đó các đỉnh

(vertex) là các điểm dữ liệu đã đƣợc gán nhãn và chƣa đƣợc gán nhãn, và các cạnh

phản ánh sự “tƣơng tự” của các đỉnh. Giả sử rằng các đỉnh đƣợc nối với nhau bởi

một cạnh có trọng số lớn thì có xu hƣớng có cùng nhãn và các nhãn có thể lan

truyền trong đồ thị. Phƣơng pháp dựa trên đồ thị (Graph-based) đƣợc thừa hƣởng

các đặc tính tốt đẹp từ lý thuyết quang phổ đồ thị[9].

Hình 2.1: Phƣơng pháp dựa trên đồ thị

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Trƣớc khi đi vào việc học trên đồ thị, đầu tiên ta cần tìm hiểu một số định

nghĩa liên quan trong đồ thị.

Cấu trúc của đồ thị

Các thuật toán trong phƣơng pháp học nửa giám sát dựa trên đồ thị hầu nhƣ

có tƣ tƣởng giống nhau và điều quan trọng là cần xây dựng đƣợc một đồ thị tốt, hơn

là việc sẽ sử dụng thuật toán nào giữa chúng.

Cho đồ thị G = (V, E) với n đỉnh, V: tập đỉnh, E: tập cạnh. Đồ thị G đƣợc thể

hiện bởi ma trận liền kề W trong đó wij > 0 nếu có cạnh nối giữa đỉnh i và đỉnh j và

wij = 0 trong các trƣờng hợp còn lại.

Đặt wij = 0 nếu đồ thị có chứa chu trình thì không tính cạnh đó. Với đồ thị có

. hƣớng, đỉnh i có tổng bậc đầu ra wi+ = và tổng bậc đầu vào w+i =

Tổng trọng số của đồ thị ký hiệu . Giả sử không có đỉnh nào

bị cô lập, do đó w+i > 0 và wi+ > 0. Trong trƣờng hợp đặc biệt của đồ thị không có

trọng số, ta có wij ∈ {0, 1}. Với đồ thị vô hƣớng, tổng bậc đầu vào và đầu ra tƣơng

ứng với di (= wi+ = w+i) đại diện cho cả hai để nhấn mạnh nhƣ một thuộc tính.

Trong thực tế, wij thƣờng có thể đƣợc giải thích một cách tự nhiên. Nó có thể

là số lƣợng các siêu liên kết từ một trang web tới các trang khác hay là một giá trị

nhị phân chỉ ra protein i tƣơng tác với protein j.

Tuy nhiên, khi các trọng số không sẵn có từ các dữ liệu, thƣờng có hai bƣớc

xử lý để xây dựng chúng. Bƣớc đầu tiên là sử dụng một hàm không âm và đối xứng

để định lƣợng các mối quan hệ giữa một cặp đỉnh. Ví dụ, nếu mỗi đỉnh đƣợc xét trong không gian Euclidean ℝd, một sự lựa chọn phổ biến là sử dụng hàm mật độ Gaussian a(i, j) = exp ( −||xi−xj||2 / 2σ2 ), trong đó xi ∈ ℝd thể hiện vị trí đỉnh i. Sau

đó, chúng ta cần xây dựng trọng số wij dựa trên mối quan hệ giữa các cặp a(i, j).

Phƣơng pháp tiếp cận ε-láng giềng đặt wij = a(i, j) nếu a(i, j) > ε và wij = 0 trong các

trƣờng hợp còn lại. Mặt khác, phƣơng pháp k-láng giềng gần nhất đặt wij = a(i, j)

nếu j là một trong số các láng giềng gần i nhất và wij = 0 trong các trƣờng hợp còn

lại. Từ đây, ta giả sử rằng đồ thị đƣợc xây dựng với các trọng số cạnh đƣợc đƣa ra

dựa trên phƣơng pháp xác định trọng số trong không gian Euclidian.

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

2.2. Các loại đồ thị phổ biến có thể sử dụng trong học nửa giám sát

Đôi khi các tập dữ liệu mà chúng ta có đƣợc lại bị giới hạn về miền tri thức,

đồng thời ta cần có một đồ thị để bắt đầu việc giải quyết vấn đề đó, do vậy, dƣới

đây là một số cách phổ biến dùng để xây dựng đồ thị phục vụ cho các thuật toán học

nửa giám sát[10].

2.2.1. Đồ thị kết nối đầy đủ

Hình 2.2: Đồ thị kết nối đầy đủ

Đồ thị kết nối đầy đủ là đồ thị với mỗi cặp đỉnh có một cạnh kết nối giữa

chúng. Đồ thị đƣợc đánh trọng số, các đỉnh “tƣơng tự” nhau thì có trọng số cạnh lớn

hơn giữa chúng. Ƣu điểm của đồ thị kết nối đầy đủ là trong việc học trọng số- với

một hàm trọng số khác nhau. Điều này dễ dàng đƣa ra các dẫn xuất của đồ thị, trọng

số tham số. Nhƣợc điểm của đồ thị kết nối đầy đủ là chi phí tính toán lớn do giữa

các đỉnh đều có cạnh nối.

2.2.2. Đồ thị rời rạc

Hình 2.3: Đồ thị rời rạc

Đồ thị rời rạc là đồ thị NN hay εNN mà mỗi đỉnh chỉ kết nối tới một vài

đỉnh khác. Đồ thị này đƣợc tính toán nhanh, tạo ra hiệu suất tính toán cao. Điều

đáng lo ngại ở đây là vì sự giả lập kết nối giữa các đỉnh không tƣơng tự nhau (có

khuynh hƣớng khác lớp) là bị bỏ đi. Với đồ thị rời rạc này, các cạnh có thể đƣợc

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

đánh trọng số hoặc không đánh trọng số. Một nhƣợc điểm của đồ thị rời rạc là khi ta

thay đổi trọng số học thì dẫn tới việc thay đổi các láng giềng của các đỉnh.

2.2.3. Đồ thị -láng giềng gần nhất

Hình 2.4: Đồ thị -láng giềng gần nhất

Đồ thị -láng giềng gần nhất là đồ thị trong đó đỉnh i và đỉnh j đƣợc kết nối

với nhau bởi một cạnh nếu đỉnh i nằm trong k láng giềng gần nhất của đỉnh j. là

một siêu tham số điều khiển mật độ của đồ thị. -NN có khả năng mở rộng bởi vì

bán kính láng giềng là khác nhau với các vùng dữ liệu có mật độ cao hay thấp. Số

nhỏ có thể là kết quả của đồ thị không liên thông. Tuy nhiên với phƣơng pháp lan

truyền nhãn thì đây không phải là vấn đề đáng ngại nếu mỗi thành phần kết nối có

một vài điểm dữ liệu đã đƣợc gán nhãn.

Nhƣợc điểm của phƣơng pháp -NN là không thể mở rộng và kết quả trong

đồ thị không đối xứng.

2.2.4. Đồ thị -láng giềng gần nhất

Hình 2.5: Đồ thị -láng giềng gần nhất

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Đồ thị ε-láng giềng gần nhất là đồ thị trong đó đỉnh i và đỉnh j đƣợc kết nối

bởi một cạnh nếu khoảng cách d(i, j) ≤ ε. Siêu tham số ε quyết định bán kính của

các láng giềng. Mặc dù ε mang giá trị liên tục, việc tìm kiếm giá trị tối ƣu là rời rạc với hầu hết giá trị độ dài các cạnh O(n2).

2.2.5. Đồ thị trọng số exp

Hình 2.6: Trọng số cạnh giữa hai đỉnh của đồ thị

wij = exp ( −d(i, j)2/α2 )

Hàm trọng số này rất hữu ích khi ta không có đủ miền tri thức. Tuy nhiên ta

quan sát thấy rằng đồ thị trọng số -NN với một số nhỏ có khuynh hƣớng thực

hiện tốt theo kinh nghiệm. Tất cả các phƣơng pháp xây dựng đồ thị đều có các siêu

tham số.

Đồ thị này đƣợc đƣa ra bởi ma trận trọng số Wn×n, Wij = 0 nếu giữa đỉnh i và j

không có cạnh nối. Ma trận trọng số W phải chứa các giá trị không âm và phải đối xứng.

2.3. Các phƣơng pháp xác định khoảng cách giữa các điểm dữ liệu

Ở phần trƣớc, chúng ta đã tìm hiểu các loại đồ thị có thể dùng để xây dựng

phục vụ quá trình học. Mỗi đồ thị đƣợc xây dựng nên bởi các điểm dữ liệu hay còn

gọi là các đối tƣợng dữ liệu, các đối tƣợng dữ liệu này lại đƣợc mô tả theo nhiều

chiều khác nhau nhƣ: miền rời rạc, miền liên tục,... Trong khi đó, phƣơng pháp học

nửa giám sát dựa trên đồ thị phụ thuộc vào khoảng cách giữa các điểm trên đồ thị.

Do đó, trƣớc khi đi vào các thuật toán học cụ thể, chúng ta cần phải lựa chọn hàm

xác định khoảng cách sẽ sử dụng. Sau đây chúng ta đi tìm hiểu một số hàm xác định

khoảng cách:

Giả sử mỗi đối tƣợng đƣợc mô tả bởi các thuộc tính có dạng nhƣ sau:

và q ký : {A1 = a1, A2 = a2, …, An = an}. Hàm khoảng cách giữa hai đối tƣợng

hiệu là: d( , q).

2.3.1. Khoảng cách cục bộ, khoảng cách toàn cục và trọng số

Một hàm khoảng cách toàn cục có thể đƣợc định nghĩa bởi sự kết hợp một

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

cách nào đó một số hàm khoảng cách cục bộ, distA, trên mỗi thuộc tính của nó.

Cách đơn giản nhất của sự kết hợp chúng là lấy tổng của chúng:

Tổng quát hơn, khoảng cách toàn cục có thể đƣợc định nghĩa nhƣ Tổng trọng

số của các khoảng cách cục bộ. Các trọng số wi cho phép các thuộc tính khác nhau

có tầm quan trọng khác nhau trong việc tính toán khoảng cách tổng thể. Các trọng

số đôi khi nằm giữa 0 và 1; trọng số bằng 0 sẽ chỉ ra một thuộc tính hoàn toàn

không liên quan.

Trọng số trung bình thƣờng là:

Các trọng số có thể đƣợc đƣa ra bởi các nhà thiết kế hệ thống. Ngoài ra còn

có các trọng số học từ một tập dữ liệu.

2.3.2. Khoảng cách Hamming

Hàm khoảng cách cục bộ đơn giản nhất đƣợc biết đến nhƣ một hàm nạp chồng

(overlap function), trả lại giá trị 0 nếu hai giá trị bằng nhau và 1 trong các trƣờng

hợp khác.

Nếu hàm khoảng cách toàn cục đƣợc định nghĩa nhƣ là tổng của các hàm khoảng

cách cục bộ thì chúng ta sẽ đếm số lƣợng các thuộc tính mà trên đó hai trƣờng hợp

không đồng nhất. Điều này gọi là khoảng cách Hamming. Tổng trọng số và trọng số

trung bình cũng có thể xảy ra.

2.3.3. Khoảng cách Manhattan cho các thuộc tính số học

Nếu một thuộc tính là thuộc tính số học thì hàm khoảng cách cục bộ có thể đƣợc

định nghĩa nhƣ độ chênh lệch tuyệt đối của các giá trị:

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Nếu khoảng cách toàn cục đƣợc tính bằng tổng của các khoảng cách cục bộ

này thì chúng ta đề cập tới khoảng cách Manhattan.

Tổng trọng số và trọng số trung bình cũng có thể xảy ra.

Một nhƣợc điểm của khoảng cách Manhattan đó là, nếu một trong số các

thuộc tính có miền giá trị tƣơng đối lớn thì nó có thể sẽ chế ngự các thuộc tính khác.

Vì vậy, khoảng cách cục bộ thƣờng đƣợc chuẩn hóa, do đó chúng nằm trong phạm

vi từ 0 đến 1. Có nhiều cách để chuẩn hóa. Để đơn giản, chúng ta chỉ xét một công

thức sau. Chúng ta chia miền giá trị chấp nhận đƣợc:

Trong đó, Amax là giá trị lớn nhất có thể của A và Amin là giá trị nhỏ nhất có thể của

A. Chúng ta gọi là khoảng cách đã đƣợc chuẩn hóa.

Một nhƣợc điểm nữa của ý tƣởng này là nó chỉ có thể đƣợc sử dụng trên các

thuộc tính số học.

2.3.4. Các hàm khoảng cách cục bộ không đồng nhất

Chúng ta có thể kết hợp khoảng cách tuyệt đối và độ trùng khớp để xử lý cả hai

thuộc tính số và thuộc tính ký hiệu (symbolic):

Khoảng cách toàn cục ở đây có thể đƣợc tính bằng tổng trọng số hoặc trọng số trung

bình của khoảng cách cục bộ.

2.3.5. Hàm khoảng cách tri thức chuyên gia

Các chuyên gia đôi khi có thể định nghĩa miền đặc biệt cho hàm khoảng cách cục

bộ, đặc biệt là cho các giá trị-ký hiệu của các thuộc tính.

Một ví dụ tuy không phải là phổ biến là khi có một số định nghĩa ở phần

trƣớc trên các giá trị của các thuộc tính ký hiệu. Ví dụ, bữa ăn cuối cùng một ngƣời

đã ăn có các giá trị là: không ăn gì, ăn nhanh và ăn đầy đủ. Những thứ này có thể

đƣợc nghĩ tới một thứ tự đã đƣợc sắp xếp trƣớc về số lƣợng thức ăn tiêu thụ: không

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

ăn gì < ăn nhanh < ăn đầy đủ.

Chúng ta có thể phân chia các giá trị số nguyên nhƣ sau: không ăn gì = 0; ăn

nhanh = 1; ăn đầy đủ = 2. Bây giờ chúng ta có thể sử dụng công thức sau:

Nhƣ vậy, chúng ta đã tìm hiểu một số hàm xác định khoảng cách giữa các

điểm dữ liệu với các miền thuộc tính khác nhau.

Sau đây chúng ta sẽ nghiên cứu thuật toán lan truyền nhãn trên đồ thị (Label

Propagation). Ý tƣởng của thuật toán là nhãn của các đỉnh sẽ đƣợc lan truyền tới các

đỉnh láng giềng dựa vào các đỉnh gần chúng. Trong quá trình này, ta cố định các

nhãn trên tập dữ liệu đã đƣợc gán nhãn. Do đó dữ liệu đã đƣợc gán nhãn sẽ đƣợc

xem nhƣ một tập nguồn và đƣa ra các nhãn thông qua dữ liệu chƣa đƣợc gán nhãn.

2.4. Thuật toán lan truyền nhãn trong đồ thị

2.4.1. Ký hiệu

Hình 2.7: Đồ thị với các trọng số cạnh

Cho đồ thị G = (V, E, W), trong đó:

- V: Tập các đỉnh, |V|=n.

- E: tập các cạnh

- W: Ma trận trọng số các cạnh tính theo công thức Euclid (Wn×n)

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

- n: Số lƣợng đỉnh trong G, n=nℓ+n .

 nℓ: số đỉnh đã đƣợc gán nhãn

 n : số đỉnh chƣa đƣợc gán nhãn

- C: tập các nhãn, thể hiện số lƣợng các nhãn, với |C|=m.

- P: Ma trận xác suất chuyển đổi nhãn, Pn×n

- Y: ma trận nhãn ban đầu Yℓ×C

- f: là ma trận fn×m, lƣu trữ thông tin của các nhãn của đỉnh đang huấn luyện.

Phƣơng pháp học nửa giám sát với đồ thị sẽ tính ma trận f từ các ma trận P, Y.

2.4.2. Nội dung thuật toán

Cho {(x1, y1)…(xℓ, yℓ)} là các dữ liệu đã gán nhãn, YL={y1, …yℓ} là các

nhãn của các lớp, y ={1..C} và {xℓ+1 … xℓ+u} là các dữ liệu chƣa đƣợc gán nhãn,

thƣờng ℓ≪u. Cho n=ℓ+u. Chúng ta thƣờng sử dụng L và U để thể hiện tƣơng ứng

với tập dữ liệu đã gán nhãn và tập dữ liệu chƣa gán nhãn. Giả sử rằng, số lƣợng các

lớp C là đã biết và tất cả các lớp đã đƣợc thể hiện trong dữ liệu đã gán nhãn. Chúng

ta sẽ nghiên cứu bài toán lan truyền cho việc tìm kiếm các nhãn cho tập U.

Bằng trực giác chúng ta muốn các điểm dữ liệu tƣơng tự nhau sẽ có cùng

nhãn. Ta tạo ra một đồ thị đầy đủ mà các đỉnh là tất cả các điểm dữ liệu, cả dữ liệu

đã gán nhãn và chƣa gán nhãn. Cạnh nối bất kỳ giữa đỉnh i và đỉnh j biểu thị cho sự

giống nhau của chúng. Giả sử đồ thị là đầy đủ với các trọng số sau đây, các trọng

số đƣợc điều khiển bởi tham số .

hoặc cụ thể hơn

Trong đó: dij là khoảng cách giữa điểm dữ liệu xi và xj.

Có thể lựa chọn cách tính giá trị khoảng cách khác nhau, tuy nhiên có lẽ là

phù hợp nếu x là các giá trị rời rạc. Trong phạm vi thuật toán này, chúng tôi lựa

chọn khoảng cách Euclid để xác định khoảng cách giữa các điểm dữ liệu và tùy theo

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

các giá trị siêu tham số cho mỗi chiều thuộc tính.

Tất cả các đỉnh có nhãn mềm có thể thay đổi nhãn trong quá trình thực hiện

việc lan truyền nhãn và đƣợc hiểu là phân phối nhãn.

Chúng ta cho nhãn của một đỉnh lan truyền tới tất cả các đỉnh khác thông qua

các cạnh giữa chúng. Cạnh có trọng số lớn hơn cho phép các nhãn đi qua dễ dàng

hơn. Ta định nghĩa một Ma trận xác suất chuyển đổi Pn×n.

Trong đó Pij là xác suất để nhảy từ đỉnh i tới j. Cũng định nghĩa một ma trận

nhãn YL ℓ×C mà dòng thứ i của chúng là một véctơ chỉ số cho yi, i ∈ L: Yic=δ(yi, c).

Chúng ta sẽ tính toán nhãn mềm f cho các đỉnh. f là ma trận n × C (f n×C), các hàng

có thể đƣợc thể hiện nhƣ sự phân bổ xác suất trên các nhãn. Việc khởi tạo giá trị

ban đầu cho f là không quan trọng. Sau đây chúng ta sẽ xem xét thuật toán:

Thuật toán:

Đầu vào: đồ thị vô hƣớng bao gồm các đỉnh đã gán nhãn và các đỉnh chƣa gán nhãn.

Đầu ra: đồ thị vô hƣớng với các đỉnh đã đƣợc gán nhãn.

Thuật toán lan truyền nhãn thực hiện theo các bƣớc sau:

Bƣớc 1. Lan truyền: f ← Pf

Bƣớc 2. Gán (giữ lại) các dữ liệu đã gán nhãn fL = YL (YL đã xây dựng ở

trên)

Bƣớc 3. Lặp lại từ bƣớc 1 cho tới khi f hội tụ.

Trong bƣớc 1, tất cả các đỉnh lan truyền các nhãn tới các láng giềng của

chúng. Bƣớc 2 là quan trọng: chúng ta muốn giữ lại các nhãn từ dữ liệu đã gán

nhãn. Vì vậy, thay vì cho việc làm các nhãn mờ đi, chúng ta giữ lại chúng ở ma trận

YL. Với sự hỗ trợ từ các đỉnh đã đƣợc gán nhãn, các lớp biên có thể đƣợc phân loại

thông qua các vùng có tỉ trọng cao và các vùng tỉ trọng thấp.

2.4.3. Sự hội tụ của thuật toán

Bây giờ ta thể hiện sự hội tụ của thuật toán tới một lời giải đơn giản.

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Cho f dƣới dạng sau: .

Vì fL đƣợc gán bằng YL nên chúng ta chỉ quan tâm đến fU. (fU chính là phần

ma trận của các phần tử chƣa đc gán nhãn). Mục đích của chúng ta cũng là xác định

ma trận fU này.

Chia ma trận P thành ma trận con đã gán nhãn và ma trận con chƣa gán nhãn,

có dạng:

Theo công thức ở trên, thuật toán có thể đƣợc mô tả nhƣ sau :

Dẫn đến

Trong đó, f0

U là giá trị khởi tạo ban đầu của fU. Chúng ta cần cho thấy

Vì P có các hàng bình thƣờng và PUU là ma trận con của P, dẫn đến:

Do đó

Do đó tổng các hàng của (PUU)n hội tụ về 0. Điều này có nghĩa rằng

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Do đó giá trị khởi tạo của f0

U là không quan trọng. Mà

fU=(I−PUU)−1 PULYL là cố định.

Do đó nó là điểm cố định duy nhất và là lời giải cho việc lặp lại thuật toán.

Điều này đƣa ra cho chúng ta một cách giải quyết bài toán lan truyền nhãn một cách

trực tiếp không cần lan truyền lặp lại.

Lƣu ý: lời giải này khả thi khi ma trận (1-PUU) có thể nghịch đảo đƣợc. Điều

kiện này sẽ đƣợc thỏa mãn khi mọi thành phần kết nối trong đồ thị có ít nhất một

điểm dữ liệu đƣợc gán nhãn.

2.4.4. Phƣơng pháp xác định siêu tham số của đồ thị

Các thuật toán học nửa giám sát đã đƣợc áp dụng thành công trong nhiều ứng

dụng với số lƣợng ít dữ liệu có nhãn bằng cách sử dụng các dữ liệu không có nhãn.

Một vấn đề quan trọng là các thuật toán học nửa giám sát dựa trên đồ thị phụ thuộc

vào chất lƣợng của đồ thị hay siêu tham số của nó[6].

Phƣơng pháp học nửa giám sát dựa trên đồ thị tạo ra một đồ thị mà các đỉnh

tƣợng trƣng cho dữ liệu có nhãn và chƣa có nhãn, trong khi các cạnh đƣợc thể hiện

sự giống nhau giữa các cặp điểm dữ liệu. Sự phân lớp ở đây đƣợc thực hiện bằng

cách sử dụng đồ thị và gán nhãn cho các dữ liệu chƣa có nhãn dựa vào việc các đỉnh

đƣợc kết nối bởi các cạnh có trọng số lớn hơn thì sẽ có nhãn giống nhau.

Các bộ phân lớp phụ thuộc đáng kể vào độ đo tƣơng tự của đồ thị, thƣờng

đƣợc thực hiện theo hai bƣớc. Bƣớc thứ nhất, các trọng số cạnh đƣợc xác định cục

bộ bằng cách sử dụng các hàm tính khoảng cách. Các hàm tính khoảng cách đóng

vai trò thành phần quan trọng trong học nửa giám sát dựa trên đồ thị để có đƣợc một

khoảng cách tốt nhất. Bƣớc thứ hai là bƣớc làm mịn, đƣợc áp dụng vào toàn bộ đồ

thị, điển hình là dựa trên sự lan truyền quang phổ của đồ thị Laplace.

Hiện nay, mới chỉ có một vài phƣơng pháp tiếp cận để giải quyết vấn đề học

trên đồ thị nhƣ: Học không tham số trên đồ thị Laplace, phƣơng pháp này giả sử

rằng trọng số và khoảng cách đƣợc đƣa ra trƣớc; Học có tham số trên đồ thị sử dụng

phƣơng pháp chứng minh cực đại hóa sử dụng suy luận xấp xỉ gradient. Việc sử

dụng chứng minh cực đại hóa và xấp xỉ Laplace để học các tham số đơn giản của

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

các hàm tƣơng tự vì chỉ học trên một đồ thị tốt, đề xuất xây dựng các đồ thị mạnh

hơn bằng cách áp dụng sự xáo trộn ngẫu nhiên và bỏ đi cạnh từ một tập các cạnh

trong cây bao trùm nhỏ nhất. Kết hợp đồ thị Laplace để học đồ thị. Học các băng

thông khác nhau với các chiều khác nhau bằng phƣơng pháp cực tiểu hóa Entropy

trên dữ liệu chƣa gán nhãn, giống nhƣ phƣơng pháp lề cực đại trong TSVM.

Trở lại với công thức tính ma trận W trong nội dung thuật toán Lan truyền

nhãn (Labeled Propagation), siêu tham số của đồ thị đƣợc ký kiệu là α. Ma trận

trọng số W đƣợc đƣa ra là cố định. Sau đây chúng ta nghiên cứu việc học các trọng

số từ cả dữ liệu gán nhãn và dữ liệu chƣa gán nhãn. Có một số phƣơng pháp dùng

để xác định siêu tham số nhƣ: Phƣơng pháp chứng minh cực đại trong các tiến trình

Gaussian (Evidence Maximization), Phƣơng pháp Cực tiểu hóa Entropy (Entropy

Minimization) và phƣơng pháp Cây khung nhỏ nhất (Minimum spanning tree). Sau

đây, chúng ta sử dụng phƣơng pháp Cây khung nhỏ nhất, để xác định siêu tham số

cho đồ thị.

Phƣơng pháp cây khung nhỏ nhất:

Nếu các cạnh của đồ thị đƣợc đánh trọng số exp với một siêu tham số , ta

có thể xác định giá trị tham số này theo thuật toán sau:

Ta xây dựng một cây khung nhỏ nhất trên tất cả các điểm dữ liệu với thuật

toán Kruskal[6].

Ban đầu không có đỉnh nào đƣợc nối với nhau. Trong suốt quá trình phát

triển cây, các cạnh lần lƣợt đƣợc xác định bởi trọng số từ ngắn đến dài.

Một cạnh đƣợc thêm vào cây nếu nó kết nối hai thành phần riêng biệt với

nhau.

Quá trình lặp lại cho tới khi toàn bộ đồ thị đƣợc kết nối.

Ta tìm ra cạnh đầu tiên của cây mà kết nối hai thành phần với nhãn khác nhau. Ta coi độ dài của cạnh này là d0 nhƣ là một giải thuật tối thiểu hóa khoảng

cách giữa các vùng lớp với nhau.

Sau đó ta đặt = d0/3 theo quy tắc 3α, do đó trọng số của cạnh này sẽ gần tới

0, với hy vọng rằng việc lan truyền cục bộ chủ yếu bên trong các lớp.

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

2.4.5. Độ phức tạp của thuật toán

Thuật toán lan truyền nhãn đƣợc thực hiện dựa trên quá trình tính toán các ma trận

và việc lặp lại để xác định sự hội tụ của thuật toán.

Đầu vào của thuật toán là một đồ thị, trong đó:

ℓ: số đỉnh đã gán nhãn.

u: số đỉnh chƣa gán nhãn (u ≫ ℓ).

n = ℓ + u : tổng số đỉnh của đồ thị.

Thuật toán thực hiện các quá trình tính toán với độ phức tạp của các thành phần nhƣ sau:

- Quá trình xác định các ma trận trọng số W, ma trận xác suất P, ma trận xác

suất chuyển nhãn PUU, ma trận xác suất PUL, ma trận nhãn YL, ma trận xác suất nhãn f, có độ phức tạp: O(n2). (*)

- Quá trình xác định siêu tham số α dựa trên thuật toán tìm cây khung nhỏ

nhất, có độ phức tạp: O (n2×log n). (**)

- Quá trình lặp để thực hiện việc lan truyền nhãn đƣợc thực hiện trong m

bƣớc lặp (m khá lớn), trong đó: việc xác định sự hội tụ của thuật toán dựa trên quá

trình tính toán các định thức ma trận, các phép toán nhân ma trận và tìm ma trận nghịch đảo, có độ phức tạp: O(n3).

Do đó, độ phức tạp của quá trình lặp là: O (m x n3).

(***) Từ (*), (**) và (***) suy ra độ phức tạp của thuật toán la truyền nhãn là: O (m x n3).

2.5. Thuật toán học nửa giám sát dựa trên đồ thị - Mincut

Thuật toán Mincut là một thuật toán dựa trên việc tìm kiếm một lát cắt nhỏ

nhất trên đồ thị, chúng sử dụng các cặp quan hệ giữa các điểm dữ liệu để học từ cả

dữ liệu đã gán nhãn và chƣa gán nhãn. Thuật toán sử dụng một độ đo tƣơng tự giữa

các điểm dữ liệu để xây dựng đồ thị và sau đó đƣa ra kết quả phân loại dữ liệu

tƣơng ứng với việc phân chia đồ thị bằng cách cực tiểu hóa số lƣợng các cặp dữ liệu

tƣơng tự nhau mà có nhãn khác nhau[4].

Bài toán cho trƣớc một tập dữ liệu đã gán nhãn và chƣa gán nhãn, chúng ta

xây dựng một đồ thị trên các mẫu dữ liệu này, do đó lát cắt nhỏ nhất trên đồ thị này

sẽ cho ta việc gán nhãn nhị phân tối ƣu trên các dữ liệu chƣa gán nhãn theo một

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

hàm tối ƣu nhất định.

Giống nhƣ hầu hết các phƣơng pháp tiếp cận khác dùng để kết hợp dữ liệu đã

gán nhãn và chƣa gán nhãn, ý tƣởng chính của thuật toán này là gán giá trị cho các

dữ liệu chƣa có nhãn để tối ƣu hóa một hàm mục tiêu có liên quan. Với phƣơng

pháp tiếp cận Mincut, loại hàm đƣợc tối ƣu đƣợc giới hạn để chỉ phụ thuộc vào mối

quan hệ giữa các cặp dữ liệu. Điều gì làm cho phƣơng pháp này thực sự đƣợc quan

tâm? Đó là các hàm chúng ta có thể xử lý, các lát cắt đồ thị đƣa ra một thuật toán có

thời gian đa thức để tìm ra sự tối ƣu hóa toàn cục.

Thuật toán Mincut

Giả sử, xét bài toán phân lớp nhị phân (dữ liệu đã gán nhãn đƣợc ký hiệu bởi

+, dữ liệu chƣa gán nhãn đƣợc ký hiệu bởi − ), L: là tập các dữ liệu đã gán nhãn, U:

là tập các dữ liệu chƣa gán nhãn, L+: tập các dữ liệu có nhãn dƣơng trong tập L, L−:

tập các dữ liệu có nhãn âm trong tập L.

Thuật toán nhƣ sau:

Bƣớc 1 . Xây dựng một đồ thị trọng số G=(V, E) trong đó V=L ∪ U ∪ { v+,

v−}, và E ⊆ V×V. Với mỗi cạnh e ∈ E có trọng số w(e). Gọi các đỉnh v+, v− là các

đỉnh phân lớp (Classication vertices) và tất cả các đỉnh khác gọi là các đỉnh mẫu

(Example vertices).

Bƣớc 2. Các đỉnh phân lớp có nhãn giống nhau đƣợc nối với nhau bởi các

cạnh có trọng số ∞. Ví dụ, w(v, v+)=∞ với tất cả các đỉnh v ∈ L+ và w(v, v−)=∞ với

tất cả các đỉnh v ∈ L−

Bƣớc 3. Các cạnh nối giữa Các Đỉnh mẫu đƣợc gán trọng số dựa trên mối

quan hệ giữa các mẫu dữ liệu đó, ví dụ nhƣ sự giống nhau hoặc khoảng cách giữa

chúng. Việc lựa chọn cụ thể các trọng số cạnh này sẽ đƣợc đề cập ở phần sau. Hàm

gán trọng số cho các cạnh đƣợc kết nối bởi Các đỉnh dữ liệu sẽ đƣợc gọi là Hàm gán

trọng số w.

Bƣớc 4. Bây giờ ta xác định một lát cắt nhỏ nhất (v+, v−) cho đồ thị; đó là, phải

tìm ra tổng trọng số nhỏ nhất của các cạnh mà nếu loại bỏ chúng đi thì sẽ làm mất kết

nối giữa các đỉnh v+ và v−. Điều này có thể tìm đƣợc bằng cách sử dụng thuật toán

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Luồng cực đại mà trong đó các đỉnh v+ là các đỉnh đầu, v− là các đỉnh đƣợc ẩn đi và

các trọng số cạnh đƣợc xem nhƣ capacities. Việc loại bỏ các cạnh theo lát cắt sẽ chia

đồ thị thành hai tập đỉnh đƣợc gọi là V+ và V−, với v+ ∈ V+ và v− ∈ V−. Nếu có nhiều

lát cắt, ta có thể đặt cho thuật toán chọn một tập đỉnh V+ là nhỏ nhất.

Bƣớc 5. Ta gán nhãn dƣơng (+) cho tất cả các mẫu dữ liệu chƣa có nhãn trong

tập V+ và gán nhãn âm (−) cho tất cả các mẫu dữ liệu chƣa có nhãn trong tập V−.

Trong thuật toán này, nếu các cạnh nối giữa các điểm dữ liệu có trọng số cao

tƣơng tự nhau thì hai điểm dữ liệu tƣơng tự nhau sẽ đƣợc đặt trong cùng một tập

đỉnh thu đƣợc từ lát cắt nhỏ nhất. Điều này phù hợp với giả thiết cơ bản của nhiều

thuật toán học (giống nhƣ láng giềng gần nhất) rằng các điểm dữ liệu tƣơng tự nhau

thì có khuynh hƣớng đƣợc phân lớp giống nhau.

Nhƣ vậy, thực tế đặt ra là chúng ta có thể đánh trọng số các cạnh nhƣ thế

nào? Nếu chúng ta có một khái niệm gọi là “khoảng cách” giữa các điểm dữ liệu thì

các mẫu dữ liệu này sẽ có nhãn giống nhau, sau đó hàm tính khoảng cách sẽ đặt các

cạnh nối các điểm dữ liệu gần nhau một trọng số cao và các cạnh có nối giữa các

điểm dữ liệu xa nhau (hoặc không có cạnh nối) một trọng số thấp. Nếu chúng ta

không khởi tạo ban đầu một hàm tính khoảng cách thì chúng ta có thể giữ các điểm

dữ liệu đã gán nhãn trong một số thuật toán học trợ giúp để học một hàm khoảng

cách. Ví dụ, chúng ta có thể sử dụng các dữ liệu đã gán nhãn để đánh trọng số cho

các thuộc tính dựa trên các thông tin có đƣợc. Ta cũng có thể đánh trọng số cho một

cạnh (x, y) với x ∈ U dựa trên y ∈ L hoặc không. Việc lựa chọn hàm đánh trọng số

cạnh có thể ảnh hƣởng đến chất lƣợng đầu ra của thuật toán.

2.6. Các trƣờng Gaussian ngẫu nhiên và các hàm điều hòa

2.6.1. Các trƣờng Gaussian ngẫu nhiên

Một cách tiếp cận khác của học nửa giám sát là đề xuất dựa trên mô hình

Gaussian ngẫu nhiên (GRF). Dữ liệu đã gán nhãn và chƣa gán nhãn đƣợc đƣa ra

nhƣ là các đỉnh trong một đồ thị có trọng số, với việc mã hóa trọng số các cạnh giữa

các mẫu dữ liệu giống nhau. Bài toán học sau đó đƣợc xây dựng trong các trƣờng

Gaussian ngẫu nhiên trên đồ thị này, tại đó ý nghĩa của các trƣờng đƣợc đặc trƣng

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

bởi các hàm điều hòa và hiệu quả thu đƣợc bằng cách sử dụng các phƣơng pháp ma

trận hay lan truyền tin cậy.

Không giống nhƣ các phƣơng pháp khác hiện nay, dựa trên hàm năng lƣợng

cực tiểu và các trƣờng ngẫu nhiên trong học máy, ta xem xét các trƣờng Gaussian

ngẫu nhiên trên không gian trạng thái liên tục thay vì các trƣờng ngẫu nhiên trên các

tập dữ liệu rời rạc. Đặc biệt, dạng phổ biến nhất của các trƣờng (field) có thể xảy ra

là duy nhất, đƣợc đặc trƣng bởi các hàm điều hòa và có thể tính toán dựa vào các

phƣơng pháp ma trận hay lan truyền. Ngƣợc lại, với các trƣờng ngẫu nhiên đa nhãn,

việc tính toán cấu hình năng lƣợng thấp nhất thƣờng là NP-khó và các thuật toán

xấp xỉ hay ƣớc lƣợng đƣợc sử dụng. Kết quả của thuật toán phân lớp với các trƣờng

Gaussian có thể đƣợc xem nhƣ một dạng của phƣơng pháp tiếp cận láng giềng gần

nhất, tại đó các mẫu dữ liệu láng giềng đã đƣợc gán nhãn bởi phƣơng pháp Bƣớc di

chuyển trên đồ thị.

Ta giả sử có ℓ điểm đã đƣợc gán nhãn (x1, y1),..., (xℓ, yℓ) và u điểm chƣa gán

nhãn xℓ+1, ..., xℓ+u; ℓ<

Cho n=ℓ+u là tổng số các điểm dữ liệu. Để bắt đầu, ta giả sử các nhãn mang

giá trị nhị phân: y ∈ {0, 1}. Xét một đồ thị liên thông G=(V, E) với tập các đỉnh V

tƣơng ứng với n điểm dữ liệu, với tập L các đỉnh ứng với các điểm dữ liệu đã gán

nhãn, với các nhãn y1,..., yℓ và tập U các đỉnh tƣơng ứng với các điểm dữ liệu chƣa

đƣợc gán nhãn. Nhiệm vụ của chúng ta là dự đoán các nhãn cho các điểm dữ liệu

trong tập U.

Ta giả sử một ma trận trọng số đối xứng Wn×n trên các cạnh của đồ thị đƣợc

đƣa ra. Ví dụ khi x ∈ ℝm thì ma trận trọng số đƣợc biểu diễn theo công thức sau:

Trong đó, xid là thành phần thứ d của mẫu dữ liệu xi biểu diễn nhƣ một véc tơ

và σ1, ..., σm là siêu tham số cho mỗi chiều.

xi ∈ ℝm

Chiến lƣợc của chúng ta đầu tiên là tính toán một hàm giá trị thực f: VR

trên đồ thị G với các thuộc tính nhất định và sau đó gán các nhãn dựa trên f. Chúng

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

ta hạn chế f để f(i) = fl(i) ≡ yi trên dữ liệu đã gán nhãn i=1, ..., ℓ. Bằng trực giác

chúng ta muốn các điểm dữ liệu chƣa gán nhãn gần nhau trong đồ thị sẽ có nhãn

tƣơng tự nhau. Điều này dẫn tới sự lựa chọn hàm bậc 2:

Rõ ràng, E đƣợc cực tiểu hóa bởi hàm không đổi. Nhƣng vì ta đã có một số

dữ liệu đã gán nhãn, chúng ta gán cho f một giá trị f(i) = yi, (i ∈ L trên tập dữ liệu đã

gán nhãn). Ta chỉ định một phân bổ xác suất tới hàm f bởi một trƣờng Gausian ngẫu

nhiên (GRF).

Trong đó β là một tham số “nghịch đảo” và Z là một hàm phân hoạch.

đƣợc chuẩn hóa trên các hàm ràng buộc với YL trên dữ liệu đã gán nhãn. Ta

đang quan tâm đến vấn đề suy luận p(fi|YL), i ∈ U hay nghĩa là

Sự phân bố p(f) giống các trƣờng Markov ngẫu nhiên với các trạng thái rời

rạc. Thực tế thì sự khác biệt duy nhất là trạng thái giá trị số thực. Tuy nhiên, điều

này làm cho vấn đề suy luận đơn giản hơn rất nhiều. Bởi vì hàm năng lƣợng bậc 2

p(f) và p(fU|YU) đều là phân phối Gaussian đa biến. Do đó p đƣợc gọi là GRF. Biên

p(fi|YL) là một biến đơn Gaussian và gần với giải pháp đƣa ra.

2.6.2. Đồ thị Laplacian

Bây giờ ta xem xét tổ hợp Laplat, ký hiệu: Δ

Cho D là ma trận đƣờng chéo bậc của các đỉnh, có Dii = ΣjWij là bậc của đỉnh i.

Laplat đƣợc định nghĩa nhƣ sau: Δ ≡ D – W.

Laplat là viết tắt cho hàm năng lƣợng:

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Hàm Gaussian ngẫu nhiên có thể đƣợc viết nhƣ sau:

2.6.3. Các hàm điều hòa

Không khó để chỉ ra rằng hàm năng lƣợng cực tiểu

là hàm điều hòa, cụ thể là Δf = 0 trên các điểm dữ liệu chƣa gán nhãn trong tập U,

và bằng Δf =YL trên các điểm dữ liệu đã gán nhãn L.

Ký hiệu hàm điều hòa là:

Thuộc tính điều hòa ở đây có nghĩa là giá trị của (i) tại mỗi điểm dữ liệu

chƣa gán nhãn i là giá trị trung bình của các láng giềng của nó trong đồ thị, ta có

công thức sau:

Do các nguyên lý cực đại của hàm điều hòa (Doyle & Snell, 1984), thỏa

mãn 0 ≤ (i)=0 hoặc (i) ≤1 với i ∈ U (lƣu ý: (i)=1 cho mỗi i ∈L).

Để tính toán giải pháp điều hòa, ta chia nhỏ ma trận W (tƣơng tự D, Δ, ...)

thành 4 khối cho L và U:

Giải pháp điều hòa Δh=0 với hL = YL đƣợc đƣa ra bởi

Mô tả cuối cùng giống với công thức fU = ( I−PUU)−1 PULYL, mà P=D/W là ma trận lan truyền trong đồ thị. Thuật toán lan truyền nhãn (labled propagation)

thực tế đã tính hàm điều hòa này.

Hàm điều hòa đã cực tiểu hóa năng lƣợng và do đó nó là một dạng của

Trƣờng Gaussian ngẫu nhiên.

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Hàm điều hòa có thể đƣợc thể hiện trong một vài cách nhìn khác nhau và

những cách nhìn khác nhau này cung cấp một tập hợp các lý luận bổ sung và kỹ

thuật phong phú cho lĩnh vực học nửa giám sát.

2.7. Đánh giá

Hầu hết các thuật toán học nửa giám sát dựa trên đồ thị đều dựa trên việc học

lan truyền, một nhƣợc điểm của phƣơng pháp này là chúng ta không thể dễ dàng mở

rộng thêm các điểm dữ liệu mới mà không thuộc tập L∪ U, hoặc nếu các điểm dữ

liệu mới đƣợc thêm vào đồ thị thì sẽ làm thay đổi cấu trúc của đồ thị, dẫn tới chi phí

tính toán bị tăng lên. Bên cạnh đó, một lý do nữa có ảnh hƣởng tới chi phí tính toán

đó là phụ thuộc vào loại đồ thị sẽ xây dựng, nếu sử dụng đồ thị kết nối đầy đủ thì ta

phải tính toán cho tất cả các cạnh nối giữa hai đỉnh bất kỳ.

2.8. Kết luận chƣơng

Trong chƣơng này, chúng ta đã tìm hiểu về phƣơng pháp học nửa giám sát

dựa trên đồ thị và một số thuật toán sử dụng để phục vụ quá trình học. Nghiên cứu

thuật toán lan truyền nhãn để học từ cả dữ liệu đã gán nhãn và chƣa gán nhãn, các

nhãn đƣợc lan truyền trong đồ thị thông qua hàm trọng số và các đỉnh lân cận đã

gán nhãn. Đây là thuật toán khá quan trọng với học máy trên đồ thị. Chúng ta cũng

nghiên cứu cách xác định các siêu tham số để phục vụ trong quá trình lan truyền

nhãn với thuật toán Cây khung nhỏ nhất. Vì các đồ thị là đầu vào của tất cả các

thuật toán nên chúng ta cần xây dựng đồ thị sao cho phù hợp nhất với yêu cầu của

bài toán.

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

CHƢƠNG 3:

CÀI ĐẶT VÀ THỬ NGHIỆM THUẬT TOÁN

3.1. Mô tả bài toán

Với mục tiêu gán nhãn cho các đỉnh trên đồ thị dựa trên cơ sở các đỉnh đã có

nhãn tiến hành xây dựng một chƣơng trình

ứng dụng nhằm mô phỏng quá trình thực hiện của thuật toán. Chƣơng trình ứng

dụng sẽ cài đặt hai thuật toán học nửa giám sát theo hai phƣơng pháp là phƣơng

pháp tự huấn luyện với sự kết hợp của các dữ liệu đã gán nhãn, chƣa gán nhãn và

phƣơng pháp dựa trên đồ thị để thực hiện việc phân loại các tin

nhắn rác có trong một tập các tin nhắn thông thƣờng.

3.2. Mô tả dữ liệu đầu vào

Dữ liệu đầu vào của chƣơng trình đƣợc lấy ngẫu nhiên với 50 tin nhắn trong

đó có 8 tin nhắn rác trong bộ dữ liệu thử nghiệm SMS Spam corpus (nguồn

http://www.dt.fee.unicamp.br/~tiago/smsspamcollection/).

Mỗi dòng dữ liệu sẽ chứa nội dung một tin nhắn dƣới dạng text. Kết thúc

mỗi dòng sẽ là dấu phân cách “phẩy”, sau dấu phẩy này tin nhắn sẽ đƣợc phân loại

thành ham-tin nhắn hợp lệ và spam-tin nhắn rác. Ví dụ về nội dung của bộ dữ liệu:

Hình 3.1: Tệp dữ liệu tin nhắn mẫu

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Trƣớc khi tiến hành phân lớp dữ liệu, cần phải xử lý để chuyển đổi dữ liệu về

định dạng phù hợp. Luận văn sử dụng phần mềm Weka (nguồn

http://www.cs.waikato.ac.nz/ml/weka/) để thực hiện các thao tác tiền xử lý dữ liệu.

Chi tiết các bƣớc xử lý nhƣ sau:

Bƣớc 1: Chuyển đổi dữ liệu dạng chuỗi về dạng vector: weka sẽ xây dựng bộ

từ điển về các từ khóa. Sau khi chuyển đổi, bộ dữ liệu dùng để chuyển đổi ở đây

bao gồm 148 bản ghi và 100 thuộc tính. Hình 3.2 chỉ rõ dữ liệu sau khi đã đƣợc

chuyển đổi.

Hình 3.2: Nội dung tin nhắn được chuyển thành dạng vector

Khi đó dữ liệu dạng vector đƣợc mô tả nhƣ trong hình sau. Các thuộc tính là

các từ trong nội dung tin nhắn, mỗi thuộc tính là 1 cột dữ liệu. Mỗi tin nhắn đƣợc

thể hiện trên một hàng với các số 0,1… thể hiện số lần xuất hiện thuộc tính (từ tiếng

anh) trong nội dung của tin nhắn nhƣ hình 3.3. Khi đó ta vẫn có thể chỉnh sửa đƣợc

nội dung file nếu cần.

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Hình 3.3: Nội dung file dữ liệu dạng vector

Bƣớc 2: Trích chọn đặc trƣng đƣợc trình bày chi tiết trong mục 3.3.

Bƣớc 3: Thực hiện gán số thứ tự cho các đỉnh với mỗi đỉnh là một SMS

đƣợc thể hiện trên một dòng dữ liệu và gán nhãn trƣớc cho một số đỉnh còn một số

đỉnh thì chƣa gán nhãn. Bằng cách thêm một số nhãn 1,0 (thể hiện là nhãn) hay -1

(chƣa gán nhãn) trƣớc phần dữ liệu của tin nhắn. Bƣớc này đƣợc thực hiện trong

chƣơng trình nhằm chuẩn hóa dữ liệu đầu vào cho phù hợp với dữ liệu đầu vào của

thuật toán.

3.3. Trích chọn đặc trƣng

Trích chọn đặc trƣng (Feature Selection, Feature Extraction) là nhiệm vụ rất

quan trọng giai đoạn tiền xử lý dữ liệu khi triển khai các mô hình khai phá dữ liệu

hoặc máy học. Một vấn đề gặp phải là các bộ dữ liệu dùng để xây dựng mô hình dữ

liệu thƣờng chứa nhiều thông tin không cần thiết (thậm chí gây nhiễu) cho việc xây

dựng mô hình. Chẳng hạn, một bộ dữ liệu gồm hàng trăm thuộc tính dùng để mô tả

về khách hàng của một doanh nghiệp đƣợc thu thập, tuy nhiên khi xây dựng một mô

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

hình nào đó chỉ cần khoảng 50 thuộc tính từ hàng trăm thuộc tính đó. Nếu ta sử

dụng tất cả các thuộc tính (hàng trăm) của khách hàng để xây dựng mô hình thì ta

cần nhiều CPU, nhiều bộ nhớ trong quá trình huấn luyện, thậm chí các thuộc tính

không cần thiết đó làm giảm độ chính xác của mô hình và gây khó khăn trong việc

phát hiện tri thức.

Có nhiều phƣơng pháp để trích chọn ra các thuộc tính tốt để huấn luyện mà

vẫn đảm bảo đƣợc yêu cầu, giúp quá trình thực thi huấn luyện nhanh hơn. Trong

trích chọn đặc trƣng văn bản, các phƣơng pháp có thể kể đến nhƣ Bag-of-words hay

Chỉ số Gain,… luận văn sử dụng phƣơng pháp trích chọn dựa trên bag-of-words với

kỹ thuật loại bỏ từ dừng “stop word” và lấy từ gốc “stemming”.

Sau khi các đặc trƣng phù hợp đƣợc chọn, bộ phân lớp đƣợc đào tạo với tập

dữ liệu huấn luyện. Quá trình huấn luyện thƣờng đƣợc lặp đi lặp lại nhiều lần để có

đƣợc một mô hình tốt nhất. Hiệu năng của mô hình phân loại sau đó đƣợc đánh giá

bởi tập dữ liệu kiểm tra đã chuẩn bị riêng.

Trong luận văn này Wake 3 đƣợc sử dụng để chọn ra các đặc trƣng tốt bằng

cách sử dụng tính năng Attribute Selection với tùy chọn Best First để lọc bỏ các tính

năng không thực sự quan trọng từ đó giảm số thuộc tính cần xét giúp chƣơng trình

thuật toán thực hiện đƣợc nhanh hơn mà vẫn đảm bảo một số tiêu chí dùng cho

phân lớp nhƣ hình sau.

Hình 3.4: Trích chọn đặc trưng

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Từ đó ta đƣợc file đầu vào cho bài toán tự huấn luyện và lan truyền nhãn với

30 thuộc tính cơ bản nhƣ hình 3.5. Dữ liệu đầu vào có thể xem và sửa nếu cần thiết

nhƣ hình 3.5 nhƣ sau:

Hình 3.5: Trích chọn thuộc tính cho file đầu vào của chương trình

Hình 3.6: Dữ liệu của chương trình

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Dữ liệu đầu vào của thuật toán là tập các bản ghi dữ liệu chƣa đƣợc phân lớp.

Với mỗi bản ghi dữ liệu sẽ chứa giá trị của các thuộc miền rời rạc.

Hình 3.7: Dữ liệu của chương trình mở bằng Notepad

Cấu trúc dữ liệu của tệp đầu vào có thể mô tả lại nhƣ sau:

Đầu tiên là các thông tin về Wake 3

Tiếp theo là n dòng thông tin các thuộc tính có dạng @ thuộc tính với n là số

thuộc tính.

Mỗi dòng tƣơng ứng với giá trị của một đối tƣợng trong luận văn thì mỗi

dòng thể hiện dữ liệu các thuộc tính của 1 sms.

Các giá trị của mỗi thuộc tính cách nhau bởi một dấu “,”

3.4. Cài đặt và thử nghiệm

Môi trƣờng cài đặt và thử nghiệm

Chƣơng trình thử nghiệm đƣợc viết bằng ngôn ngữ C#.Net trên bộ Visual

Studio 2010 sử dụng phiên bản .Net Framework 4.0. Dữ liệu của chƣơng trình đƣợc

lƣu trữ trong hệ quản trị cơ sở dữ liệu Sql Server 2008 R2.

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Các chức năng của chƣơng trình

Nhập dữ liệu:

Cho phép nhập dữ liệu từ tệp text có cấu trúc nhƣ trong mô tả ở mục 3.6.

Trƣớc khi nhập liệu, ngƣời dùng có thể chỉnh sửa trên phần mềm

Wake 3. Để nhập dữ liệu, ngƣời dùng nhấn vào nút “Chọn...”, sau đó tìm đến tệp dữ

liệu lƣu trữ trên máy tính có đuôi dạng *.arff hoặc *.text. Sau khi chọn tệp, dữ liệu

sẽ đƣợc lấy thông tin cần thiết về các thuộc tính và thực hiện lƣu vào cơ sở dữ liệu

và hiển thị lên ở tab “Chi tiết dữ liệu” để phục vụ cho việc thực hiện các thuật toán

tiếp theo đƣợc dễ dàng hơn.

Hình 3.8: Giao diện chọn tệp dữ liệu

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Tại giao diện này, cột wi chính là thuộc tính thứ i trong bộ thuộc tính đã

trích chọn ở bên trên. ngƣời dùng có thể thực hiện các thao tác lựa chọn vào

combobox “Chọn phƣơng pháp”. Chƣơng trình cho phép lựa chọn phƣơng pháp

tự huấn luyện và phƣơng pháp lan truyền nhãn. Sau khi lựa chọn, nhấn nút

“Thực hiện”.

Với phƣơng pháp tự huấn luyện, kết quả hiển thị nhƣ sau:

Hình 3.9: Kết quả khi lựa chọn phương pháp tự huấn luyện

Các tin nhắn thuộc lớp sms spam là 11 còn lại là ham.

Với phƣơng pháp lan truyền nhãn, giao diện sẽ hiển thị thông tin về ma trận

nhãn, ma trận xác suất nhãn, ma trận trọng số cạnh và ma trận xác suất.

Mỗi nút trên đồ thị là một SMS. Ngoài ra trên tab “Đồ thị lan truyền nhãn”,

sẽ hiển thị đồ thị các nhãn với mỗi đỉnh là 1 hình tròn, đỉnh màu đỏ ứng với trƣờng

hợp chƣa gán nhãn, đỉnh xanh lá ứng với nhãn 1 và đỉnh vàng ứng với nhãn 0 và

đƣờng nối giữa các đỉnh.

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Trong hình 3.10 ta có thể xem chi tiết các ma trận đƣợc tính toán trong quá

trình lan truyền nhãn nhƣ: ma trận trọng số cạnh W, ma trận xác suất chuyển đổi P,

ma trận nhãn YL, ma trận xác suất chuyển nhãn f

Hình 3.10: Giao diện đồ thị lan truyền nhãn trước khi thực hiện

Ở giao diện này trên các bảng “Nút i” thể hiện là SMS thứ i

Để thực hiện thuật toán lan truyền nhãn, ngƣời dùng nhấn vào nút “Thực

hiện” trên tab “Phƣơng pháp lan truyền nhãn”, chƣơng trình sẽ trả về kết quả là các

đỉnh đã đƣợc gán nhãn. Đồng thời sẽ hiển thị ma trận xác suất hội tụ và ma trận xác

xuất nhãn fu với của các 8 tin nhắn spam.

Sau khi hệ thống thực hiện xong việc lan truyền nhãn, ta có thể xem kết quả

dƣới dạng bảng ma trận xác suất nhạn hội tụ và ma trận xác suất nhãn fu cũng nhƣ

dƣới dạng đồ thị nhƣ hình 3.11. Màn hình sẽ hiển thị thông tin các đỉnh và nhãn của

chúng sau khi đƣợc lan truyền từ các đỉnh đã gán nhãn khác

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Hình 3.11: Giao diện đồ thị lan truyền nhãn sau khi thực hiện

Sau khi thực hiện thuật toán lan truyền nhãn, các đỉnh đều đƣợc gán nhãn

nên không còn các đỉnh màu đỏ (chƣa gán nhãn) nhƣ trên hình. Tại giao diện này,

ngƣời dùng có thể nhấn vào nút “Lƣu kết quả” để lƣu lại dữ liệu đã gán nhãn. Kết

quả sẽ xuất ra tệp text.

3.5. Kết quả thực nghiệm và đánh giá độ phức tạp

3.5.1 Kết quả thực nghiệm

Hình 3.12: Kết quả đồ thị sau khi được gán nhãn ở dạng đồ thị

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Kết quả thực nghiệm thuật toán thu đƣợc 11 tin nhắn đƣợc phân lớp tin nhắn rác

và 39 tin nhắn trong đó 3 tin nhắn phân lớp sai, tỷ lệ tin nhắn phân lớp đúng đạt 94%.

3.5.2 Đánh giá độ phức tạp thuật toán

 Với thuật toán tự huấn luyện

Dữ liệu đầu vào bao gồm:

ℓ: số lƣợng dữ liệu đã gán nhãn.

u: số lƣợng dữ liệu chƣa gán nhãn (u ≫ ℓ).

n = ℓ + u =50 : tổng số lƣợng dữ liệu.

Độ phức tạp của thuật toán tự huấn luyện dựa trên việc đánh giá quá trình lặp ở

bƣớc 2 (xem 1.3.1):

 Thuật toán thực hiện số vòng lặp nhiều nhất có thể là: u vòng lặp. Trong đó:

Vòng lặp thứ nhất có độ phức tạp: O (ℓ).

Vòng lặp thứ hai có độ phức tạp là: O (ℓ + 1).

..........................................................................

Vòng lặp thứ u có độ phức tạp là: O (ℓ+u−1).

Do đó thuật toán có độ phức tạp là:

O (ℓ) + O (ℓ +1) + ... + O (ℓ +u−1) = O(ℓ +u−1). (O (ℓ +u) − O (ℓ))/ 2.

= O(ℓ +u−1). O (u) / 2. ≈ O(n2) ≈ O(502).

 Với thuật toán lan truyền nhãn

Thuật toán lan truyền nhãn đƣợc thực hiện dựa trên quá trình tính toán các ma trận

và việc lặp lại để xác định sự hội tụ của thuật toán.

Đầu vào của thuật toán là một đồ thị, trong đó:

ℓ: số đỉnh đã gán nhãn.

u: số đỉnh chƣa gán nhãn (u ≫ ℓ).

n = ℓ + u =50: tổng số đỉnh của đồ thị.

Thuật toán thực hiện các quá trình tính toán với độ phức tạp của các thành phần nhƣ sau:

- Quá trình xác định các ma trận trọng số W, ma trận xác suất P, ma trận xác

suất chuyển nhãn PUU, ma trận xác suất PUL, ma trận nhãn YL, ma trận xác suất nhãn

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

f, có độ phức tạp: O(n2). (1)

- Quá trình xác định siêu tham số α dựa trên thuật toán tìm cây khung nhỏ

nhất, có độ phức tạp: O (n2×log n). (2)

- Quá trình lặp để thực hiện việc lan truyền nhãn đƣợc thực hiện trong m

bƣớc lặp (m khá lớn), trong đó: việc xác định sự hội tụ của thuật toán dựa trên quá

trình tính toán các định thức ma trận, các phép toán nhân ma trận và tìm ma trận nghịch đảo, có độ phức tạp: O(n3).

Do đó, độ phức tạp của quá trình lặp là: O (m×n3). (3)

 Từ (1), (2) và (3) suy ra độ phức tạp của thuật toán la truyền nhãn là: O (m×503).

3.6. Kết luận

Trong chƣơng này, tác giả đã cài đặt chƣơng trình thử nghiệm phƣơng pháp

tự huấn luyện và lan truyền nhãn dựa trên học nửa giám sát. Với thuật toán tự huấn

luyện, ứng dụng cho phép ngƣời dùng nhập dữ liệu đầu vào, gán nhãn thông qua

quá trình tự huấn luyện. Với thuật toán lan truyền nhãn trên đồ thị, chƣơng trình cho

phép theo dõi kết quả của quá trình tính toán thông qua các ma trận, đồng thời hiển

thị kết quả một cách trực quan lên giao diện. Chƣơng trình có thể dễ dàng phát triển

với nhiều thuộc tính hơn.

Trong chƣơng này, tác giả đã chƣơng trình thử nghiệm các thuật toán phân

lớp áp dụng vào bài toán phân loại tin nhắn rác. Với phƣơng pháp trích chọn đặc

trƣng nhƣ đã trình bày ở trên, giúp giảm rất nhiều thời gian thực hiện phân lớp của

các thuật toán. Đồng thời, luận văn cũng trình bày chi tiết các bƣớc tiền xử lý dữ

liệu cho phép khai thác trên các thuật toán phân lớp hiệu quả hơn

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN

 Kết luận

:

- Trình bày khái quát về học có giám sát, học không giám sát và học nửa

giám sát.

- Giới thiệu một số phƣơng pháp học nửa giám sát phổ biến nhƣ: Self-training,

Co-training, TSVM và đánh giá các ƣu và nhƣợc điểm của mỗi phƣơng pháp.

- Trình bày phƣơng pháp học nửa giám sát dựa trên đồ thị và một số thuật

toán nhƣ: Labeled Propagation, Mincut.

- Đã cài đặt chƣơng trình thử nghiệm thuật toán lan truyền nhãn trên đồ thị và

thuật toán tự huấn luyện.

 Hạn chế

Về chƣơng trình ứng dụng: do thời gian có hạn nên tôi chƣa có điều kiện xây

dựng một phần mềm ứng dụng hoàn chỉnh, áp dụng các thuật toán trên vào các lĩnh

vực trong đời sống.

 Hƣớng phát triển

Với việc nghiên cứu về học nửa giám sát và phƣơng pháp học nửa giám sát

dựa trên đồ thị, tôi sẽ tiếp tục nghiên cứu sâu hơn về hƣớng này và sẽ tìm hiểu

những phƣơng pháp, thuật toán học nửa giám sát khác để có thể áp dụng những lý

thuyết đã nghiên cứu đƣợc nhằm xây dựng các phần mềm áp dụng vào thực tiễn.

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

TÀI LIỆU THAM KHẢO

Tài liệu tiếng Việt

[1] TS Nguyễn Tân Ân (2011), Bài giảng mạng noron nhân tạo, Trƣờng Đại

học Sƣ phạm Hà Nội, Hà Nội.

[2] PGS. TS Đoàn Văn Ban, ThS Nguyễn Hiền Trinh (2009), Ngôn ngữ hình

thức và ôtômát, NXB Đại học Thái Nguyên.

[3] PGS. TS. Hà Quang Thụy (2011), Bài giảng nhập môn khai phá dữ liệu,

Trƣờng Đại học Công nghệ Đại học Quốc gia Hà Nội, Hà Nội.

Tài liệu tiếng Anh

[4] Avirm Blum, Shuchi Chawla (2001), Learning from labeled and Unlabeled

Data using Graph Mincuts, Computer Science Department, Carnegie

Mellon University, 5000 Forbes Avenue, Pittsburgh, PA15213USA.

[5] Amarnag Subramanya (2012), Partha Pratim Talukdar, A Tutorial on

Graph-based Semi-Supervised Learning Algorithms for NLP, South Korea.

[6] Matthias Seeger (2001), Learning with labeled and unlabeled data,

Technical Report, University of Edinburgh.

[7] Olivier Chapelle, Bernhard Sch¨olkopf, Alexander Zien (2006), Semi-

Supervised Learning.

[8] Partha Pratim Talukdar (July 16, 2010), Experiments in Graph-based Semi-

Supervised Learning Methods for Class-Instance Acquisition, Search Labs,

Microsoft Research Mountain View, CA 94043, Fernando Pereira Google,

Inc.Mountain View, CA 94043.

[9] Xiaojin Zhu (May 2005), Semi-Supervised Learning with Graphs.

[10] Zoubin Ghahramani (2012), Graph-based Semi-supervised Learning,

Department of Engineering University of Cambridge, UK, La Palma.

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn