Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
———————————— TRẦN ANH TUẤN
PHƯƠNG PHÁP HỌC NỬA GIÁM SÁT VÀ ỨNG DỤNG
Chuyên nghành: Khoa học máy tính
Mã số : 60.48.01
1.2.4. Quá trình rời rạc hóa dữ liệu 7
1.2.5. Tập mẫu 7
1.2.6. Quá trình tìm kiếm trong không gian giả thuyết 7
1.3. Học có giám sát 8
1.3.1. Khái niệm 8
1.3.2. Cách giải một bài toán học có giám sát 9
1.3.3. Cực tiểu hóa rủi ro kinh nghiệm 10
1.4. Học không có giám sát 11
1.4.1. Khái niệm 11
1.4.2. Phân cụm dữ liệu 12
1.5. Học tăng cƣờng 14
1.6. Học nửa giám sát 16
1.6.1. Khái niệm 16
- ii -
1.6.2. Bài toán học nửa giám sát 19
1.7. Tổng kết chƣơng 1 21
CHƢƠNG 2: MỘT SỐ THUẬT TOÁN HỌC NỬA GIÁM SÁT VÀ BÀI
TOÁN PHÂN CỤM DỮ LIỆU 22
2.1. Một số thuật toán học nửa giám sát 22
2.1.1. Mô hình sinh và thuật toán kỳ vọng cực đại 22
2.1.1.1. Giới thiệu mô hình sinh 22
2.1.1.2. Mô hình sinh trong học nửa giám sát 22
2.1.1.3. Thuật toán kỳ vọng cực đại 24
2.1.2. Thuật toán tự huấn luyện 25
2.1.2.1 Giới thiệu thuật toán tự huấn luyện 25
2.1.2.2. Nội dung thuật toán 26
2.1.3. Thuật toán đồng huấn luyện 27
2.1.3.1. Giới thiệu thuật toán đồng huấn luyện 27
2.1.3.2. Nội dung thuật toán 28
- iv -
DANH MỤC CÁC TỪ VIẾT TẮT
SVM
Support Vector Machine
S3VM
Semi – superviesd Suport vector machines
EM
Expectation-Maximization
MaxEnt
Maximum Entropy
TSVM
Transductive Support Vector Machine
RSS
Residual Sum of Squares
học tìm hiểu trƣớc, giờ ngƣời học chỉ việc tái tạo lại. Và để tái tạo lại, ngƣời học
không có cách gì khác đó là phải huy động nội lực của bản thân (động cơ, ý chí,
…), càng phát huy cao bao nhiêu thì việc tái tạo lại càng diễn ra tốt bấy nhiêu.
Do đó hoạt động học làm thay đổi chính ngƣời học. Ai học thì ngƣời đó phát
triển, không ai học thay thế đƣợc, ngƣời học cần phải có trách nhiệm với chính
bản thân mình, vì mình trong quá trình học. Mặc dù hoạt động học có thể cũng
có thể làm thay đổi khách thể. Nhƣng nhƣ thế không phải là mục đích tự thân
của hoạt động học mà chính là phƣơng tiện để đạt đƣợc mục đích làm thay đổi
chính chủ thể của hoạt động.
Hoạt động học là hoạt động tiếp thu những tri thức lý luận, khoa học.
Nghĩa là việc học không chỉ dừng lại ở việc nắm bắt những khái niệm đời
thƣờng mà học phải tiến đến những tri thức khoa học, những tri thức có tính
chọn lựa cao, đã đƣợc khái quát hoá, hệ thống hoá.
Hoạt động học tập không chỉ hƣớng vào việc tiếp thu những tri thức, kĩ
năng, kĩ xảo mà còn hƣớng vào việc tiếp thu cả những tri thức của chính bản
thân hoạt động học. Hoạt động học muốn đạt kết quả cao, ngƣời học phải biết
cách học, phƣơng pháp học, nghĩa là phải có những tri thức về chính bản thân
hoạt động học.
Vậy, việc làm thế nào để máy tính có khả năng học tập, tƣ duy và có khả
năng học tập giống con ngƣời là một lĩnh vực nghiên cứu rất đƣợc chú ý trong
thời đại hiện nay. Dựa trên khuynh hƣớng đó và sự hƣớng dẫn của PGS, TS
- 2 -
Đoàn Văn Ban, tôi mạnh dạn nhận đề tài: ”PHƢƠNG PHÁP HỌC NỬA
GIÁM SÁT VÀ ỨNG DỤNG” để tìm hiểu và ứng dụng vào thực tế.
2. Đối tƣợng và phạm vi nghiên cứu
Đối tƣợng nghiên cứu:
- Đề tài nghiên cứu về những vấn đề chung trong học máy, một số thuật
toán trong khai phá dữ liệu và ứng dụng thuật toán học nửa giám sát trong phân
cụm văn bản.
- 4 -
CHƢƠNG 1: PHƢƠNG PHÁP HỌC MÁY
1.1. Khái niệm học máy
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ự [11].
Qua đó ta thấy học máy có liên quan rất mật thiết với thống kê, vì cả hai
lĩnh vực đều nghiên cứu việc phân tích dữ liệu, nhƣng học máy khác với thống
kê ở chỗ, học máy tập trung vào sự phức tạp của các giải thuật trong việc thực
thi tính toán. Nhiều bài toán suy luận đƣợc xếp vào loại bài toán NP-khó, vì thế
một phần của học máy là nghiên cứu sự phát triển các giải thuật suy luận xấp xỉ
mà có thể xử lí đƣợc.
Phân loại: Có hai loại phƣơng pháp học máy chính:
- 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
đã 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 nhiều và sẵn có.
- 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. 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.
- 5 -
Các ngành khoa học liên quan:
- 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
Ký hiệu là X, mỗi phần tử thuộc X có thể đƣợc gọi là các dữ liệu, các
thể hiện, các đối tƣợng hay các ví dụ.
Mỗi phần tử S X đƣợc biểu diễn bởi một tập gồm n
thuộc tính S = (s
1
, s
2
, …, s
n
).
Một đối tƣợng S cũng có thể đƣợc biểu diễn kết hợp với lớp liên thuộc
của nó hay nói cách khác có thể đƣợc biểu diễn dƣới dạng nhãn: z = (s, c).
1.2.2. Bản chất của dữ liệu
Bản chất của các dữ liệu có thể là các giá trị số trong tập số thực, các giá
trị rời rạc, các giá trị nhị phân, dãy các phần tử trong một bảng chữ cái
(alphabet),
Không gian biểu diễn của dữ liệu có thể biểu diễn dƣới dạng thuần nhất
(cùng kiểu) hoặc dƣới dạng trộn (không cùng kiểu).
1.2.3. Tiền xử lý dữ liệu
Là quá trình xử lý dữ liệu đầu vào nhằm mục đích làm giảm số chiều của
dữ liệu đầu vào, giảm số chiều của vấn đề, xử lý nhiễu,
Ta thực hiện nhƣ sau:
Loại bỏ các thuộc tính không phù hợp hoặc ít phù hợp với quá trình học.
Sử dụng các phép biến đổi tuyến tính hoặc không tuyến tính trên các
thuộc tính ban đầu, nhằm giảm số chiều của không gian đầu vào.
Dùng các chuyên gia hoặc sử dụng trực quan để phát hiện các bất
thƣờng, các lỗi mô tả thuộc tính hoặc nhãn, nhằm xử lý nhiễu.
- 7 -
1.2.4. Quá trình rời rạc hóa dữ liệu
Hình 1.1: Mô hình học có giám sát
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 {(x
1
, y
1
), (x
2
, y
2
), , (x
n
, y
n
)}. 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 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.
Dữ liệu đƣợc gán nhãn: Là dữ liệu bao gồm các cặp gồm đối tƣợng đầu
vào và đầu ra mong muốn. Đầu ra của một hàm có thể là một giá trị liên tục gọi
là hồi quy, hoặc có thể là dự đoán một nhãn phân loại cho một đối tƣợng đầu
vào gọi là phân loại.
- 9 -
tƣơng ứng. Ví dụ: Ta có thể dụng mạng nơ-ron nhân tạo, cây quyết định,
Bước 5: Hoàn thiện thiết kế.
Tiến hành chạy giải thuật học với tập dữ liệu huấn luyện thu thập đƣợc.
Ta có thể điều chỉnh các tham số của giải thuật học bằng cách tối ƣu hóa hiệu
năng trên một tập con của tập huấn luyện, hay thông qua kiểm chứng chéo. Sau
đó ta tiến hành đo đạc hiệu năng của giải thuật trên một tập dữ liệu 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.3.3. Cực tiểu hóa rủi ro kinh nghiệm
Mô hình toàn cục của việc học có giám sát có mục tiêu nhằm tìm ra một
hàm g, khi cho sẵn một tập hợp các điểm có dạng (x, g(x)).
Giả thiết rằng ta đã biết đặc điểm của hàm g đối với một tập điểm, và tập
điểm này đƣợc lấy mẫu độc lập và có cùng phân bố theo một xác suất phân bố p
chƣa biết từ một tập lớn hơn hoặc có thể vô hạn. Ta cũng giả thiết tồn tại một
hàm tổn thất theo tác vụ L có dạng: L: Y × Y → R+.
Trong đó miền xác định của Y trùng với miền xác định của g và L ánh xạ
tới các số thực không âm.
Giá trị L(z, y) là giá trị tổn thất sinh ra khi đoán giá trị của g tại một điểm
z cho trƣớc khi mà giá trị thực của nó là y.
- 11 -
Ta định nghĩa hàm rủi ro f: Là giá trị kỳ vọng của hàm tổn thất, có công
thức là:
)())(),(()(
iii
xpxgxfLfR
1
)(
Đối với rủi ro kinh nghiện ta có nguyên tắc cực tiểu hóa rủi ro kinh
nghiệm bằng cách chọn hàm f* để rủi ro kinh nghiệm là nhỏ nhất.
1.4. Học không có giám sát
1.4.1. Khái niệm
Học không có giám sát là một phƣơng pháp học máy mà dữ liệu huấn
luyện là dữ liệu hoàn toàn chƣa đƣợc gán nhãn, nhằm tìm ra một mô hình phù
hợp với các quan sát [1].
Học không có giám sát 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à chƣa biết trƣớc.
Trong học không có giám sát, một tập dữ liệu đầu vào thƣờng đƣợc thu
thập một cách ngẫu nhiên, và sau đó một mô hình mật độ kết hợp sẽ đƣợc xây
dựng cho tập dữ liệu đó.
- 12 -
Ta có thể kết hợp học không có giám sát với suy diễn Bayes để tạo ra xác
suất có điều kiện cho bất kỳ biến ngẫu nhiên nào khi biết trƣớc các biến khác.
Hay nói cách khác khi đó ta đã chuyển từ việc học không có giám sát sang học
có giám sát.
Mọi giải thuật nén dữ liệu, về cơ bản 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 hay không tƣờng minh. Do đó
trong công nghệ nén dữ liệu học không có giám sát đƣợc ứng dụng một cách rất
hữu dụng.
* Mô hình toán học
- Cho X = (x
1
, x
2
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
- 14 -
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.
1.5. 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).
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 a
môi trƣờng một trạng thái mới s
t+1
và một phần thƣởng r
t+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=r
0
+r
1
+ +r
n
với các MDP có một trạng thái kết
thúc, hoặc lƣợng R=Σ
t
γ
t
r
t
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 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 để
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à
- 18 -
tập 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.
đƣợ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.
Dƣới đây là hình vẽ thể hiện việc dữ liệu chƣa đƣợc gán nhãn sử dụng
trong học nửa giám sát.
Copyright: Tài liệu đại học ©