ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH
ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
BÀI THU HOẠCH MÔN
CÔNG NGHỆ TRI THỨC VÀ ỨNG DỤNG
ĐỀ TÀI
THUẬT TOÁN K-MEANS VÀ ỨNG DỤNG TRONG
BÀI TOÁN PHÂN ĐOẠN ẢNH
GVHD: GS TSKH. Hoàng Văn Kiếm
HVTH: Võ Tấn Lực
MSHV: CH1301098
TP. Hồ Chí Minh, ngày 10 tháng 10 năm 2014
TÓM LƯỢC
o
Trong thập kỷ qua, việc ứng dụng công nghệ tri thức - 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ự hành, 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 xin cảm ơn GS TSKH. Hoàng Văn Kiếm, người đã tận tình truyền đạt kiến
thức và có những định hướng giúp tôi hoàn thành môn học “Công Nghệ Tri Thức &
Ứng Dụng”.
Mặc dù đã rất cố gắng nhưng bài thu hoạch của tôi khó tránh khỏi thiếu sót,
mong Thầy góp ý nhận xét để bài thu hoạch được hoàn thiện hơn.
HVTH: CH1301098 – Võ Tấn Lực
MỤC LỤC
HVTH: CH1301098 – Võ Tấn Lực
Công nghệ Tri thức & Ứng dụng GS TSKH. Hoàng Văn Kiếm
Chương I. CƠ SỞ LÝ THUYẾT

không đầy đử, không chính xác.
Máy học giúp thiết kế hệ thống huấn luyện tự động (mạng nơrôn nhân tạo)
và giải mã mối liên hệ giữa các tri thức được lưu trữtrong mạng từ dữ liệu.Công
nghệ Máy học là một trong những phương pháp chính trong khai phá dữ liệu. Nó
được sử dụng trong tiến trình khám phá tri thức.
1.2. Tiến trình máy học và phân loại các thuật toán
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
HVTH: CH1301098 – Võ Tấn Lực Trang 5/17
Công nghệ Tri thức & Ứng dụng GS TSKH. Hoàng Văn Kiếm
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.

- Support Vector Machine – SVM.
- K Nearest Neighbours – KNN.
- Naïve Bayes – NB.
- Decision Tree – DT.
- Neural Network – Nnet.
- Centroid–base vector.
- Linear Least Square Fit – LLSF.
• Học Không giám sát (Unsupervised Learning).
Đâ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
HVTH: CH1301098 – Võ Tấn Lực Trang 7/17
Công nghệ Tri thức & Ứng dụng GS TSKH. Hoàng Văn Kiếm
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

tâm của cụm
μi,i=1, ,k
2. Gán các điểm dữ liệu
vào các cụm gần nhất
HVTH: CH1301098 – Võ Tấn Lực Trang 9/17
Công nghệ Tri thức & Ứng dụng GS TSKH. Hoàng Văn Kiếm
3. Thiết lập lại điểm
trung tâm của mỗi
cụm
4. Lập lại các bước 2-3
cho đến khi hội tụ
Ghi chú |c|= số phần tử trong c
Thuật toán k-means trên được chứng minh là hội tụ và có độ phức tạp tính
toán là:
Trong đó, n là số đối tượng dữ liệu, k là số cụm dữ liệu, d là số chiều, τ là số
vòng lặp, T
flop
là thời gian để thực hiện một phép tính cơ sở như phép tính nhân,
chia, Như vậy, do K-means phân tích phân cụm đơn giản nên có thể áp dụng đối
với tập dữ liệu lớn.Tuy nhiên, nhược điểm của K-means là chỉ áp dụng với dữ liệu
có thuộc tính số và khám phá ra các cụm có dạng hình cầu, k-means còn rất nhạy
cảm với nhiễu và các phần tử ngoại lai trong dữ liệu. Hơn nữa, chất lượng phân cụm
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.
HVTH: CH1301098 – Võ Tấn Lực Trang 10/17

HVTH: CH1301098 – Võ Tấn Lực Trang 12/17
Công nghệ Tri thức & Ứng dụng GS TSKH. Hoàng Văn Kiếm
• Điều kiện khởi tạo có ảnh hưởng lớn đến kết quả. Điều kiện khởi tạo
khác nhau có thể cho ra kết quả phân cụm khác nhau.
• Không xác định được mức độ ảnh hưởng của thuộc tính đến quá trình
tạo các cụm.
Chương III: ỨNG DỤNG THUẬT TOÁN K-MEANS TRONG PHÂN ĐOẠN
ẢNH
3.1. Giới thiệu về phân đoạn ảnh
Phân đoạn ảnh là một thao tác ở mức thấp trong toàn bộ quá trình xử lý ảnh.
Quá trình này thực hiện việc phân vùng ảnh thành các vùng rời rạc và đồng nhất với
nhau hay nói cách khác là xác định các biên của các vùng ảnh đó. Các vùng ảnh
đồng nhất này thông thường sẽ tương ứng với tòan bộ hay từng phần của các đối
tượng thật sự bên trong ảnh. Vì thế, trong hầu hết các ứng dụng của lĩnh vực xử lý
ảnh (image processing), thị giác máy tính, phân đoạn ảnh luôn đóng một vai trò cơ
bản và thường là bước tiền xử lý đầu tiên trong toàn bộ quá trình trước khi thực
hiện các thao tác khác ở mức cao hơn như nhận dạng đối tượng, biểu diễn đối
tượng, nén ảnh dựa trên đối tượng, hay truy vấn ảnh dựa vào nội dung …
Vào những thời gian đầu, các phương pháp phân vùng ảnh được đưa ra chủ
yếu làm việc trên các ảnh mức xám do các hạn chế về phương tiện thu thập và lưu
trữ. Ngày nay, cùng với sự phát triển về các phương tiện thu nhận và biểu diễn ảnh ,
các ảnh màu đã hầu như thay thế hoàn toàn các ảnh mức xám trong việc biểu diễn
và lưu trữ thông tin do các ưu thế vượt trội hơn hẳn so với ảnh mức xám. Do đó, các
kỹ thuật, thuật giải mới thực hiện việc phân vùng ảnh trên các loại ảnh màu liên tục
được phát triển để đáp ứng các nhu cầu mới. Các thuật giải, kỹ thuật này thường
đượ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ụ
HVTH: CH1301098 – Võ Tấn Lực Trang 13/17

Công nghệ Tri thức & Ứng dụng GS TSKH. Hoàng Văn Kiếm
Hầu hết những phương pháp được đề cập trong phần trên đều hoạt động dựa
trên các không gian đặc trưng của ảnh(thông thường là màu sắc). Do đó, các vùng
ảnh kết quả là đồng nhất tương ứng với các đặc trưng đã chọn cho từng không gian.
Tuy nhiên, không có gì đảm bảo rằng tất cả các vùng này thể hiển một sự cô đọng
(compactness) về nội dung xét theo ý nghĩa không gian ảnh (ý nghĩa các vùng theo
sự cảm nhận của hệ thần kinh con người). Mà đặc tính này là quan trọng thứ hai sau
đặc tính về sự thuần nhất của các vùng ảnh. Do các phương pháp gom cụm cũng
như xác định ngưỡng histogram đã nêu đều bỏ qua thông tin về vị trí của các pixel
trong ảnh.
Trong các báo cáo khoa học về phân vùng ảnh mức xám, có khá nhiều kỹ
thuật cố thực hiện việc thoả mãn cùng lúc cả hai tiêu chí về tính đồng nhất trong
không gian đặc trưng của ảnh và tính cô đọng về nội dung ảnh. Tuỳ theo các kỹ
thuật mà các thuật giải này áp dụng, chúng được phân thành các nhóm sau:
• Các thuật giải áp dụng kỹ thuật chia và trộn vùng.
• Các thuật giải áp dụng kỹ thuật tăng trưởng vùng.
• Các thuật giải áp dụng lý thuyết đồ thị.
• Các giải thuật áp dụng mạng neural.
• Các giải thuật dựa trên cạnh.
Các phương pháp dựa trên mô hình vật lý
Tất cả các giải thuật được xem xét qua, không ít thì nhiều ở mặt nào đó đều
có khả năng phát sinh việc phân vùng lỗi trong các trường hợp cụ thể nếu như các
đối tượng trong ảnh màu bị ảnh hưởng quá nhiều bởi các vùng sáng hoặc bóng mờ,
các hiện tượng này làm cho các màu đồng nhất trong ảnh thay đổi nhiều hoặc ít một
cách đột ngột. Và kết quả là các thuật giải này tạo ra các kết quả phân vùng quá
mức mong muốn so với sự cảm nhận các đối tượng trong ảnh bằng mắt thường. Để
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ý để

Công nghệ Tri thức & Ứng dụng GS TSKH. Hoàng Văn Kiếm
Hình 3.1.Giao diện chính của chương trình
Dữ liệu cần đưa vào là một tập tin hình ảnh và chọn số cụm cần được phân
chia. Kết quả sau khi xử lý sẽ được hiển thị trong phần result. Kết quả thực hiện với
số cụm lần lượt là 4, 2 và 12 như sau:
Hình 3.2. Thực hiện chương trình với số cụm bằng 4 (k = 4)
HVTH: CH1301098 – Võ Tấn Lực Trang 17/17
Công nghệ Tri thức & Ứng dụng GS TSKH. Hoàng Văn Kiếm
Hình 3.3.Thực hiện chương trình với số cụm bằng 2 (k=2)
Hình 3.4. Thực hiện chương trình với số cụm bằng 12 (k=12)
Kết luận của chương trình
HVTH: CH1301098 – Võ Tấn Lực Trang 18/17
Công nghệ Tri thức & Ứng dụng GS TSKH. Hoàng Văn Kiếm
• Phânđoạn ảnh được thực hiện bằng việc sử dụng thuật toánK-means trong
không gian màuRGB hoạt động rất tốt với tất cả các hình ảnh.
• Sự rõ nét trong hình ảnh đã phân đoạn bằng K-meanslà rấttốt.
• Sự rõ nét của hình ảnh cũng phụ thuộc vào số lượng các cụm (số k) được
sử dụng.
• Một bất lợi của thuật toán này là số lượng cụm là phải được xác định
trong mỗi lần lặp.
HVTH: CH1301098 – Võ Tấn Lực Trang 19/17
Công nghệ Tri thức & Ứng dụng GS TSKH. Hoàng Văn Kiếm
TÀI LIỆU THAM KHẢO
Tiếng Việt
[1] Bài giảng môn học “Công nghệ Tri thức & Ứng dụng” (2014)Giảng viên:
GSTSKHHoàng Văn Kiếm.
Tiếng Anh
[2]Siddheswar Ray and Rose H. Turi (2010), “Determination of Number of Clusters
in K-Means Clustering andApplication in Colour Image Segmentation”.
[3] Matteo Matteucci. “Tutorial on Clustering Algorithms,” Politecnico di Milano,