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




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 đề

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




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




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



Transductive support

TSVM

vector machine

Học nửa giám sát
Máy véc tơ hỗ trợ
Máy véc tơ hỗ trợ truyền
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




DANH MỤC HÌNH VẼ





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

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




- Đọ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ợ.

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
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
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.
Khoa học máy tính: là cơ sở để thiết kế các thuật toán, đồng thời đánh giá
thời gian chạy, bộ nhớ của các thuật toán học máy.
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
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
mới và cho ra kết quả.
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á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




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
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:
Xử lý ngôn ngữ tự nhiên (Natural Language Processing): xử lý văn bản, giao
tiếp ngƣời – máy, …
Nhận dạng (Pattern Recognition): nhận dạng tiếng nói, chữ viết tay, vân tay,
thị giác máy (Computer Vision) …
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
tự động.

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




(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ử



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 (kNearest 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




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




thang máy, trò chơi cờ vua, ...
Ví dụ về học tăng cường:
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
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
đối thủ và xác định số nƣớc cờ của đối thủ sẽ đi một cách tức thì.
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
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

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


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].
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)}ℓ+uj= ℓ+1.
Thuật toán :
1. Khởi tạo, đặt L={(xi, yi)}ℓi=1 , và U={(xj)}ℓ+uj= ℓ+1.
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




-

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


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




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
Đầu tiên, học từ các dữ liệu đã gán nhãn:

(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




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