ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH
ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
THUẬT TOÁN K-MEANS VÀ ỨNG
DỤNG TRONG
BÀI TOÁN PHÂN ĐOẠN ẢNH
Giảng viên hướng dẫn: PGS TS. Vũ Thanh Nguyên
Học viên thực hiện: Trần Quốc Bảo
MSHV: CH1301004
TP Hồ Chí Minh, tháng 03/2014
TÓM LƯỢC
o
Trong thập kỷ qua, việc ứng dụng máy học vào khoa học kỹ thuật đã giúp cho
chúng ta có thể tạo ra được những chiếc xe tự lái, nhận dạng giọng nói thực tế, tìm
kiếm web có hiệu quả, và sự hiểu ngày càng sâu sắc hơn về bộ gen của con
người,v.v Ngày nay máy học phổ biến đến nỗi chúng ta có thể sử dụng nó hàng
chục lần một ngày mà không hề hay biết biết.
Trong giới hạn của đồ án này chúng ta sẽ khảo sát qua các khái niệm cơ bản
về máy học, thuật toán K-means và ứng dụng của thuật toán K-means trong phân
đoạn ảnh.
Tôi chân thành tỏ lòng biết ơn PGS. TS. Vũ Thanh Nguyên, Trưởng khoa
Khoa Công nghệ Phần mềm, Trường Đại học Công nghệ Thông tin, người đã cung
cấp cho tôi các kiến thức cơ bản ban đầu để có thể tìm hiểu sâu thêm trong lĩnh vực
máy học.
MỤC LỤC
Trang4
Chương I. CƠ SỞ LÝ THUYẾT
1.1. Máy học là gì
Rất khó để có thể định nghĩa một cách chính xác về máy học. Một trong
những định nghĩa rộng nhất về thuật ngữ máy học là: “một cụm từ dùng để chỉ khả
năng một chương trình máy tính để tăng tính thực thi dựa trên những kinh nghiêm
đã trải qua” hoặc “là để chỉ khả năng một chương trình có thể phát sinh ra một cấu

1.2.1. Tiến trình máy học
Một tiến trình máy học bao gồm 2 giai đoạn:
• Giai đoạn học: hệ thống phân tích dữ liệu và nhận ra sự mối quan hệ
(có thể là phi tuyến hoặc tuyến tính) giữa các đối tượng dữ liệu. Kết
quả của việc học có thể là: nhóm các đối tượng vào trong các lớp, tạo
ra các luật, tiên đoán lớp cho các đối tượng mới.
• Giai đoạn thử nghiệm: Mối quan hệ (các luật, lớp ) được tạo ra
phải được kiểm nghiệm lại bằng một số hàm tính toán thực thi trên
một phần của tập dữ liệu huấn luyện hoặc trên một tập dữ liệu lớn.
1.2.2. Phân loại các thuật toán
Trang6
Các thuật toán máy học được chia làm 3 loại: học giám sát, học không giám
sát và học nửa giám sát.
• Học có giám sát (Supervised Learning).
Đây là cách học từ những mẫu dữ liệu mà ở đó các kỹ thuật máy học
giúp hệ thống xây dựng cách xác định những lớp dữ liệu. Hệ thống phải tìm một sự
mô tả cho từng lớp (đặc tính của mẫu dữ liệu).Người ta có thể sử dụng các luật phân
loại hình thành trong quá trình học và phân lớp để có thể sử dụng dự báo các lớp dữ
liệu sau này.
Thuật toán học có giám sát gồm tập dữ liệu huấn luyện M cặp:
S = {(xi, cj)| i=1,…,M; j=1,…,C}
Các cặp huấn luyện này được gọi là mẫu, vớixi là vector n-chiều còn gọi
là vector đặc trưng,cj là lớp thứ j đã biết trước.
Thuật toán máy học giám sát tìm kiếm không gian của những giả thuyết
có thể, gọi là H. Đối với một hay nhiều giả thuyết, mà ước lượng tốt nhất hàm
không được biết chính xác f : x  c.Đối với công việc phân lớp có thể xem giả
thuyết như một tiêu chí phân lớp.
Thuật toán máy học tìm ra những giả thuyết bằng cách khám phá ra
những đặc trưng chung của những ví dụ mẫu thể hiện cho mỗi lớp.Kết quả nhận
được thường ở dạng luật (Nếu thì).

Đây là việc học từ quan sát và khám phá. Hệ thống khai thác dữ liệu
được ứng dụng với những đối tượng nhưng không có lớp được định nghĩa trước, mà
để nó phải tự hệ thống quan sát những mẫu và nhận ra mẫu. Hệ thống này dẫn đến
Trang8
một tập lớp, mỗi lớp có một tập mẫu được khám phá trong tập dữ liệu.Học không
giám sát còn gọi là học từ quan sát và khám phá.
Trong trường hợp chỉ có ít, hay gần như không có tri thức về dữ liệu đầu
vào, khi đó một hệ thống học không giám sát sẽ khám phá ra những phân lớp của
dữ liệu, bằng cách tìm ra những thuộc tính, đặc trưng chung của những mẫu hình
thành nên tập dữ liệu.Một thuật toán máy học giám sát luôn có thể biến đổi thành
một thuật toán máy học không giám sát (Langley 1996).Đối với một bài toán mà
những mẫu dữ liệu được mô tả bởi n đặc trưng, người ta có thể chạy thuật toán học
giám sát n-lần, mỗi lần với một đặc trưng khác nhau đóng vai trò thuộc tính lớp, mà
chúng ta đang tiên đoán.Kết quả sẽ là n tiêu chí phân lớp (n bộ phân lớp), với hy
vọng là ít nhất một trong n bộ phân lớp đó là đúng.
Một số thuật toán học không giám sát:
- Thuật toán K-means
- Mô hình mạng Neural
- Hệ thống ART(adaptive resonance theory)
• Học nửa giám sát.
Học nửa giám sát là các thuật toán học tích hợp từ học giám sát và học
không giám sát. Việc học nửa giám sát tận dụng những ưu điểm của việc học giám
sát và học không giám sát và loại bỏ những khuyết điểm thường gặp trên hai kiểu
học này.
Một số thuật toán học nửa giám sát.
- EM - Expectation Maximization.
- TSVM - Transductive Support Vector Machine.
- Self-training.
- Co-training.
Trang9

dữ liêuk của thuật toán k-means phụ thuộc nhiều vào các tham số đầu vào như: số
cụm k và k trọng tâm khởi tạo ban đầu. Trong trường hợp các trọng tâm khởi tạo
ban đầu mà quá lệch so với các trọng tâm cụm tự nhiên thì kết quả phân cụm của k-
means là rất thấp, nghĩa là các cụm dữ liệu được khám phá rất lệch so với các cụm
trong thực tế. Trên thực tế chưa có một giải pháp tối ưu nào để chọn các tham số
đầu vào, giải pháp thường được sử dụng nhất là thử nghiệm với các giá trị đầu vào k
khác nhau rồi sau đó chọn giải pháp tốt nhất.
2.3. Ví dụ minh họa
Trong phần này chúng ta sẽ xem qua các bước thực hiện của thuật toán K-
means bằng đồ họa
Trang11
Hình 2.1.Giá trị gốc ban đầu Hình 2.2. Khởi tạo các cụm ban đầu
Hình 2.3. Gán các điểm dữ liệu vào các
cụm
Hình 2.4 Tính toán lại vị trí các điểm
trung tâm của cụm
Trang12
Hình 2.5 Gán các điểm dữ liệu vào
trong các cụm
Hình 2.6 Thuật toán dừng lại vì không có
điểm thay đổi
Thuật toán kết thúc vì không có sự thay đổi của các đối tượng trong từng cụm
2.4. Ưu và khuyết điềm của thuật toán
Ưu điểm:
• Với số lượng biến lớn thì thuật toán K-means có thể tính toán nhanh
hơn so với các thuật toán phân nhóm phân cấp khác (nếu K là nhỏ).
• K-means có thể gom các cụm chặt chẽ hơn so với phân cụmtheo cấp
bậc, đặc biệt là nếu các cụm hình cầu.
Khuyết điểm: Giống như các thuật toán khác, k- means cũng có một số
khuyết điềmnhất định:

được phát triển dựa trên nền tảng các thuật giải phân vùng ảnh mức xám đã có sẵn.
Các hướng tiếp cận phân đoạn ảnh
Phân đoạn ảnh là chia ảnh thành các vùng không trùng lắp. Mỗi vùng gồm
một nhóm pixel liên thông và đồng nhất theo một tiêu chí nào đó. Tiêu chí này phụ
thuộc vào mục tiêu của quá trình phân đoạn. Ví dụ như đồng nhất về màu sắc, mức
xám, kết cấu, độ sâu của các layer… Sau khi phân đoạn mỗi pixel chỉ thuộc về một
vùng duy nhất. Để đánh giá chất lượng của quá trình phân đoạn là rất khó. Vì vậy
trước khi phân đoạn ảnh cần xác định rõ mục tiêu của quá trình phân đoạn là gì. Xét
Trang14
một cách tổng quát, ta có thể chia các hướng tiếp cận phân đoạn ảnh thành ba nhóm
chính như sau:
• Các kỹ thuật phân đoạn ảnh dựa trên không gian đặc trưng.
• Các kỹ thuật dựa trên không gian ảnh.
• Các kỹ thuật dựa trên các mô hình vật lý.
Các phương pháp dựa trên không gian đặc trưng
Nếu chúng ta giả định màu sắc bề mặt của các đối tượng trong ảnh là một
thuộc tính bất biến và các màu sắc đó được ánh xạ vào một không gian màu nào đó,
vậy thì chúng ta sẽ có một cái nhìn đối với mỗi đối tượng trong ảnh như là một cụm
(cluster) các điểm trong không gian màu đó. Mức độ phân tán của các điểm trong
trong một cụm được xác định chủ yếu bởi sự khác biệt về màu sắc. Một cách khác,
thay vì ánh xạ các pixel trong ảnh vào một không gian màu cụ thể, ta xây dựng một
histogram dựa trên các đặc trưng màu dạng ad-hoc cho ảnh đó (ví dụ như Hue), và
thông thường, các đối tượng trong ảnh sẽ xuất hiện như các giá trị đỉnh trong
histogram đó. Do đó, việc phân vùng các đối tượng trong ảnh tương ứng với việc
xác định các cụm – đối với cách biểu diễn thứ nhất – hoặc xác định các vùng cực trị
của histogram – đối với cách biểu diễn thứ hai.
Các phương pháp tiếp cận này chỉ làm việc trên một không gian màu xác
định chẳng hạn phương pháp của Park áp dụng trên không gian màu RGB, còn
phương pháp của Weeks và Hague thì áp dụng trên không gian màu HIS. Dựa trên
không gian đặc trưng, ta có các phương pháp phân đoạn: phương pháp phân nhóm

giải quyết vấn đề này, các giải thuật phân vùng ảnh áp dụng các mô hình tương tác
vật lý giữa bề mặt các đối tượng với ánh sáng đã được đề xuất. Các công cụ toán
học mà các phương pháp này sử dụng thì không khác mấy so với các phương pháp
đã trình bày ở trên, điểm khác biệt chính là việc áp dụng các mô hình vật lý để
minh hoạ các thuộc tính phản chiếu ánh sáng trên bề mặt màu sắc của các đối
tượng.
Cột mốc quan trọng trong lĩnh vực phân vùng ảnh màu dựa trên mô hình vật
lý được Shafer đặt ra. Ông giới thiệu mô hình phản xạ lưỡng sắc cho các vật chất
điện môi không đồng nhất. Dựa trên mô hình này, Klinker đã đặt ra một giải thuật
đặt ra một số giả thiết quang học liên quan đến màu sắc, bóng sáng, bóng mờ của
các đối tượng và cố gắng làm phù hợp chúng với hình dạng của các cụm. Hạn chế
chính của giải thuật này là nó chỉ làm việc trên các vật chất điện môi không đồng
nhất. Hai ông cùng tên Tsang đã áp dụng mô hình phản xạ lưỡng sắc trong không
gian HSV để xác định các đường biên trong ảnh màu.
Healey đề xuất một mô hình phản xạ đơn sắccho các vật chất kim loại. Các
phương pháp đề cập trong phần này chỉ áp dụng cho hai loại vật chất là kim loại và
điện môi không đồng nhất. Một thuật toán tổng quát và phức tạp hơn cũng được
Maxwell và Shafer đề xuất.
3.2. Phát biểu ứng dụng
Thuật toán K-means phân cụm thường được sử dụng trong thị giác máy tính
là một hình thức phân đoạn ảnh thuộc nhóm phương pháp dựa trên không gian đặc
trưng. Các kết quả của các phân đoạn thường được sử dụng để hỗ trợ phát hiện các
đường biên biên và xác định đối tượng. Ứng dụng mẫu sau đây thực hiện phân đoạn
ảnh bằng cách sử dụng các tiêu chuẩn bình phương khoảng cách Euclide trênkhông
gian màu RGB. Các phương thức xác định khoảng cách tốt hơn để phân đoạn ảnh sẽ
không được thể hiện trong ví dụ này.
Trang17
Trong chương trình này có sử dụng framework Accord.NET phiên bản
2.1.2. Đây là một bộ framework chuyên dùng trong lĩnh vực thị giác máy tính, trí
tuê nhân tạo – xử lý ảnh, mạng neural, các thuật toán di truyền, máy học,

[5] “K-means clustering”www.onmyphd.com