i
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CNTT VÀ TRUYỀN THÔNG

Phan Thị Thu Nga

NGHIÊN CỨU PHƢƠNG PHÁP PHÂN CỤM NỬA GIẢM
SÁT VÀ ỨNG DỤNG

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

Thái Nguyên, tháng 9 năm 2015

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

/>

ii
LỜI CAM ĐOAN
Tôi xin cam đoan đề tài với tiêu đề Nghiên cứu phương pháp phân cụm
nửa giám sát và ứng dụng là công trình nghiên cứu đƣợc tôi thực hiện dƣới sự
hƣớng dẫn của giáo viên hƣớng dẫn khoa học.
Các kết quả nghiên cứu và kết quả thử nghiệm nêu trong luận văn là trung
thực và chƣa từng đƣợc công bố trong bất kỳ tài liệu nào khác. Trong phần kiến
thức chung, nghiên cứu giải thuật áp dụng và một số thực nghiệm kết quả tƣơng
ứng tôi có tham khảo ở một số tài liệu và đã có trích dẫn đúng và đầy đủ.

Học viên

Phan Thị Thu Nga


2.4.2 Thuật toán Seed Fuzzy C-means .................................................... 40
CHƢƠNG 3. ỨNG DỤNG THUẬT TOÁN PHÂN CỤM TRONG LĨNH VỰC
XỬ LÝ ẢNH ................................................................................................... 43
3.1 Giới thiệu tổng quan .............................................................................. 43

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

/>

iv
3.2 Phân vùng ảnh (Image segmentation) sử dụng Fuzzy C-Means .......... 43
3.2.1 Tóm lược về vấn đề xử lý ảnh số (Digital Image Processing) ....... 43
3.2.2 Lập trình và thử nghiệm ................................................................. 45
3.3 Phân cụm ảnh với thuật toán SSDBSCAN ........................................... 53
3.3.1 Dữ liệu ............................................................................................ 53
3.3.2 Kết quả ........................................................................................... 55
KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ...................................................... 58


Những kết quả đã đạt đƣợc ................................................................. 58



Hƣớng phát triển của đề tài ................................................................ 58

PHỤ LỤC ........................................................................................................ 60
TÀI LIỆU THAM KHẢO ............................................................................... 63

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


14
15

Hình 1.5

Bài toán phân cụm

17

Hình 1.6

Bài toán phân cụm nửa giám sát

17

Minh họa thuật toán K-Means: Sự phụ thuộc vào
Hình 2.1

trọng tâm tại bƣớc khởi tạo dẫn đến các kết quả khác

22

nhau sau mỗi lần chạy
Hình 2.2

Hình 2.3

Dữ liệu (với 9 cụm) mà K-Means không thể phát
hiện chính xác các cụm
Minh họa các bƣớc của thuật toán hierarchical

(b) các ràng buộc (constraint) must-link và cannotlink đƣợc biểu diễn tƣơng ứng bằng các đoạn thẳng nét

31

liền và nét đứt.
Hình 2.7
Bảng 2.1

Hình 2.8
Hình 2.9
Hình 3.1

Hình 3.2

Quá trình xây dựng cluster của SSDBSCAN

33

Các tập dữ liệu sử dụng (n: số phần tử cần clustering, m:
số thuộc tính, và k là số cluster)
Kết quả thực nghiệm của thuật toán ActSSDBSCAN và
SSDBSCAN
Kết quả thực nghiệm của thuật toán SECM
Tổng quan về hệ thống xử lý ảnh trên máy tính [5]
Ảnh gốc (a) và các vùng (màu sáng) đƣợc phân tách
bới thuật toán Fuzzy C-means

38

40


Dữ liệu lấy từ trang UCI

56

Hình 3.8

Kết quả với tập dữ liệu image210

57

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

/>

vii
Hình 3.9

Kết quả với tập dữ liệu image300

58

Hình 3.10

Kết quả với tập dữ liệu image420

58

Hình 3.11


Các ứng dụng tiêu biểu của trí tuệ nhân tạo vào đời sống xã hội bao gồm:
ngƣời máy, robot, xử lý ngôn ngữ tự nhiên, nhận dạng, phát hiện dị thƣờng,
an ninh quốc phòng, tin sinh học, khoa học vũ trụ và trái đất…
Trong khuôn khổ luận văn Thạc sỹ của mình, qua việc đƣợc trang bị
các môn học lý thuyết nhƣ thuật toán, xử lý ảnh, trí tuệ nhân tạo,… tôi đã lựa


2

chọn đề tài Nghiên cứu phương pháp phân cụm nửa giám sát và ứng dụng.
Chủ đề phân cụm dữ liệu là một nhánh nhỏ nằm trong lĩnh vực học máy
(machine learning) của trí tuệ nhân tạo nhằm nghiên cứu và ứng dụng bài
toán phân cụm trong thực tế. Hơn nữa phân cụm có giám sát là một hƣớng đi
tốt trong khoảng 10 năm trở lại đây và đã chứng minh tính ƣu việt của nó.
2. Đối tƣợng và phạm vi nghiên cứu
2.1. Đối tượng nghiên cứu
Vấn đề phân cụm dữ liệu (clustering), phân cụm nửa giám sát (semisupervised clustering).
2.2. Phạm vi nghiên cứu
- Lý thuyết: Nghiên cứu các thuật toán cơ bản về phân cụm dữ liệu và
phân cụm nửa giám sát.
- Thực nghiệm: Lập trình trên ngôn ngữ C# cho ứng dụng phân vùng
ảnh và phân cụm ảnh.
3. Phƣơng pháp nghiên cứu.
- Phƣơng pháp nghiên cứu khoa học và suy luận logic.
- Phƣơng pháp nghiên cứu mô tả, giải thích, giải pháp.
4. Ý nghĩa khoa học và thực tiễn của đề tài.
- Về khoa học
Nghiên cứu các thuật toán phân cụm và phân cụm nửa giám sát, đánh giá
ƣu, nhƣợc điểm và giải thích kết quả đạt đƣợc của từng phƣơng pháp


Học máy (machine learning) là một lĩnh vực của trí tuệ nhân tạo nghiên
cứu phát triển các phần mềm dùng cho máy tính hoặc hệ thống máy tính có
thể giải quyết các tình huống cụ thể hoặc nhận dạng ra các mẫu giống nhƣ con
ngƣời. Máy tính hoặc hệ thống máy tính ở đây hiểu rằng là bất kỳ hệ thống
nào mà có thể nạp và sử dụng phần mềm để thực hiện trên nó.
Trong lĩnh vực học máy hiện nay có ba phƣơng pháp học cơ bản bao
gồm: học có giám sát, học nửa giám sát và học không giám sát.
Ý tƣởng cơ bản của học có giám sát có thể hiểu nhƣ chúng ta cung cấp
một số mẫu (ví dụ dữ liệu, hình ảnh, đồ vật đã gán nhãn) cho hệ thống học và
sau đó thiết kế phát triển các hệ thống có thể suy diễn hay nhận biết mẫu mới
nằm trong phạm vi nó đã đƣợc học.
Học nửa giám sát khác với học có giám sát là các thuật toán dạng này chỉ
sử dụng một lƣợng nhỏ các mẫu (các dữ liệu đã gán nhãn) để học và suy luận
ra các dữ liệu chƣa gán nhãn.


5

Học không giám sát không dùng bất kỳ dữ liệu gán nhãn nào mà chỉ sử
dụng các dữ liệu không có nhãn để thực hiện yêu cầu nào đó chẳng hạn nhƣ
phân cụm các dữ liệu hay phát hiện các dị thƣờng trong dữ liệu hay ngoại suy.
Hình 1.1 minh họa các bài toán học máy tƣơng ứng.

(a) – Học có giám sát

( c)- Học nửa giám sát

(b) – Học nửa giám sát

(d)- Học không giám sát



7

- Máy tìm kiếm nhƣ Google, Yahoo, You tube: các hệ thống này sử dụng
các công cụ của học máy để phát triển hệ thống
- Chẩn đoán trong y tế: trợ giúp phân tích ảnh X - quang, các hệ chuyên
gia chẩn đoán tự động
- Tin sinh học: phân loại và dự đoán chuỗi gene, dự đoán tính chất của
thuốc mới
- Thiên văn học và trái đất
- Phát hiện gian lận tài chính, gian lận thẻ tín dụng
- Phân tích thị trƣờng chứng khoán (stock market analysis)
- Trò chơi: chơi cờ (Deep blue, IBM, 1998),
- Ngƣời máy (robot): 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 hệ thần kinh/bộ não của ngƣời máy
Trong nội dung của luận văn này, tôi chọn bài toán phân cụm (một dạng
của phƣơng pháp học không giám sát) để nghiên cứu và tìm hiểu cũng nhƣ
thử nghiệm các ứng dụng thực tế, phần tiếp theo sẽ trình bày các thuật ngữ,
các định nghĩa và khái niệm cơ bản, tiếp đó các thuật toán phân cụm sẽ trình
bày chi tiết ở chƣơng 2, phần thực nghiệm và đánh giá kết quả là nội dung của
chƣơng 3 sẽ tổng kết các kết quả đã làm đƣợc và hƣớng phát triển tiếp theo.
1.4 Khái niệm về bài toán phân cụm
Bài toán phân cụm (clustering) là một dạng của bài toán học không
giám sát (unsupervised learning) đƣợc phát biểu nhƣ sau: cho tập X gồm n
đối tƣợng x1, x2, …, xn trong không gian d chiều, hãy phân rã tập X ra thành k
(k ≤ n) cụm C1, C2,…, Ck (cluster) rời nhau (Ci

Cj =


hơn 200 đối tƣợng dữ liệu, tuy nhiên một cơ sở dữ liệu lớn có thể chứa hàng
triệu đối tƣợng. Phân cụm cho một mẫu của một tập dữ liệu lớn cho trƣớc có
thể dẫn tới các kết quả bị lệch. Ta có thể phát triển các giải thuật phân cụm có
khả năng mở rộng cao trong các cơ sở dữ liệu lớn nhƣ thế nào.
Khả năng giải quyết đối với dữ liệu có các thuộc tính hỗn hợp (số, kí
tự,…):
Nhiều giải thuật đƣợc thiết kế để phân cụm dữ liệu số dựa trên khoảng
cách. Tuy nhiên, nhiều ứng dụng có thể yêu cầu phân cụm các kiểu khác nhau
của dữ liệu nhƣ nhị phân, xác thực (tên) và dữ liệu có thứ tự hay sự pha trộn
các kiểu dữ liệu này.
Phát hiện ra các cụm với hình dạng tuỳ ý:
Nhiều giải thuật phân cụm định rõ các cụm dựa trên các phép đo khoảng
cách Euclidean và Manhattan. Các giải thuật dựa trên các phép đo khoảng
cách nhƣ thế này có khuynh hƣớng tìm các cụm hình cầu với kích thƣớc và
mật độ giống nhau. Tuy nhiên, một cụm có thể có hình dạng bất kỳ. Điều này
rất quan trọng để phát triển các giải thuật - các giải thuật này có thể phát hiện
ra các cụm có hình dạng tuỳ ý.
Các yêu cầu tối thiểu cho miền tri thức để xác định rõ các tham số đầu
vào:
Nhiều giải thuật phân cụm yêu cầu ngƣời dùng nhập vào các tham số
nào đó trong phép phân tích cụm (nhƣ số lƣợng các cụm đã đề nghị). Kết quả
phân cụm thƣờng rất nhạy cảm với các tham số đầu vào. Nhiều tham số khó
xác định, đặc biệt đối với các tập dữ liệu chứa các đối tƣợng số chiều cao.


10

Điều này không chỉ là gánh nặng cho các user mà còn làm cho chất lƣợng
phân cụm khó điều khiển.
Khả năng giải quyết dữ liệu nhiễu:

quả phân cụm ở khả năng diễn dịch, tính toàn diện và tiện lợi. Phân cụm có
thể cần đƣợc liên kết với các cách hiểu ngữ nghĩa cụ thể và các ứng dụng cụ
thể. Việc nghiên cứu mục đích của ứng dụng ảnh hƣởng nhƣ thế nào đến việc
lựa chọn các phƣơng pháp phân cụm là thực sự quan trọng.
1.6 Các chiến lƣợc trong phƣơng pháp phân cụm dữ liệu
1.6.1 Phương pháp phân cụm phân hoạch (Partitioning Methods)
Kỹ thuật này phân hoạch một tập hợp dữ liệu có n phần tử thành k
nhóm cho đến khi xác định số các cụm đƣợc thiết lập. Số các cụm đƣợc
thiết lập là các đặc trƣng đƣợc lựa chọn trƣớc. Phƣơng pháp này là tốt cho
việc tìm các cụm hình cầu trong không gian Euclidean.
1.6.2 Phương pháp phân cụm phân cấp (Hierarchical Methods)
Phƣơng pháp này xây dựng một phân cấp trên cơ sở các đối tƣợng dữ
liệu đang xem xét. Nghĩa là sắp xếp một tập dữ liệu đã cho thành một cấu
trúc có dạng hình cây, cây phân cấp này đƣợc xây dựng theo kỹ thuật đệ
quy.
Phân cụm phân hoạch và phân cụm phân cấp là hai phƣơng pháp
phân cụm dữ liệu cổ điển, hiện đã có rất nhiều thuật toán cải tiến dựa trên
hai phƣơng pháp này đã đƣợc áp dụng phổ biến trong khai phá dữ liệu.
Ý tƣởng của thuật toán phân cụm thứ bậc rất đơn giản, tại bƣớc khởi
động n điểm dữ liệu coi nhƣ n cụm, tại mỗi bƣớc hai cụm có hai điểm gần


12

nhau nhất sẽ đƣợc hòa lại thành một cụm [11]. Thuật toán sẽ dừng lại khi có
đủ số cụm cần thiết đƣợc yêu cầu bởi ngƣời sử dụng.
Hình minh họa việc tạo lập các cụm bằng phƣơng pháp phân cụm thứ
bậc.

1

cấp) hoặc cho đến khi các điều kiện kết thúc thỏa mãn. Nhƣ vậy, cách tiếp
cận này sử dụng chiến lƣợc ăn tham trong quá trình phân cụm.
- Phương pháp “trên xuống” (Top Down : Bắt đầu với trạng thái là tất
cả các đối tƣợng đƣợc xếp trong cùng một cụm. Mỗi vòng lặp thành công,
một cụm đƣợc tách thành các cụm nhỏ hơn theo giá trị của một phép đo độ
tƣơng tự nào đó cho đến khi mỗi đối tƣợng là một cụm, hoặc cho đến khi
điều kiện dừng thỏa mãn. Cách tiếp cận này sử dụng chiến lƣợc chia để trị
trong quá trình phân cụm.
1.6.3 Phương pháp phân cụm dựa trên mật độ (Density-Based
Methods)
Kỹ thuật này nhóm các đối tƣợng dữ liệu dựa trên hàm mật độ xác
định, mật độ là số các đối tƣợng lân cận của một đối tƣợng dữ liệu theo
một nghĩa nào đó. Trong cách tiếp cận này, khi một dữ liệu đã xác định thì
nó tiếp tục đƣợc phát triển thêm các đối tƣợng dữ liệu mới miễn là số các
đối tƣợng lân cận này phải lớn hơn một ngƣỡng đã đƣợc xác định trƣớc.
Phƣơng pháp phân cụm dựa trên mật độ của các đối tƣợng để xác định các
cụm dữ liệu có thể phát hiện ra các cụm dữ liệu với hình thù bất kỳ. Kỹ thuật
này có thể khắc phục đƣợc các phần tử ngoại lai hoặc giá trị nhiễu rất tốt,
tuy nhiên việc xác định các tham số mật độ của thuật toán là rất khó khăn,
trong khi các tham số này lại có tác động rất lớn đến kết quả phân cụm.
1.6.4 Phương pháp phân cụm dựa trên lưới (Grid-Based Methods)
Kỹ thuật phân cụm dựa trên lƣới thích hợp với dữ liệu nhiều chiều,
dựa trên cấu trúc dữ liệu lƣới để phân cụm, phƣơng pháp này chủ yếu
tập trung áp dụng cho lớp dữ liệu không gian. Mục tiêu của phƣơng pháp
này là lƣợng hóa dữ liệu thành các ô tạo thành cấu trúc dữ liệu lƣới. Sau đó,
các thao tác phân cụm chỉ cần làm việc với các đối tƣợng trong từng ô lƣới


14


- Phân đoạn ảnh nội soi thƣờng gặp một số thách thức nhƣ độ phân giải
thấp (256x256 pixels), ảnh thƣờng có các thành phần không có nghĩa (các
nhiễu do bong bóng nƣớc, thức ăn, …); các đặc trƣng vùng bệnh đa dạng,
biến đổi không theo quy luật, phân đoạn cho một loại ảnh bất bình thƣờng
(vùng chảy máu) (hình 1.4.a).
- Phân đoạn các đối tƣợng cần quan tâm trong ảnh thu từ thiết bị bay
không ngƣời lái (Unmanned Aerial Vehicle (UAV).
Kết quả phân đoạn này có thể hỗ trợ nhiều bài toán lớn tiếp theo nhƣ
giám sát an ninh trong môi trƣờng vừa và lớn, thống kê, xây dựng bản đồ
(hình 1.4.b).

Hình 1.4 Một số ví dụ về phân đoạn ảnh sử dụng clustering


16

Hình 1.5 Ứng dụng clustering trong việc phát hiện những vùng bị hỏng
trên trái cây
- Phân đoạn để nhận dạng các bề mặt là bình thƣờng hay bất thƣờng trên
bề mặt trái cây (hình 1.5).
Các ứng dụng của phân cụm còn phải kể đến nhƣ trong phân tích dữ
liệu trong chẩn đoán ung thƣ, trong xây dựng máy tìm kiếm (Google,
Yahoo,…) trong các hệ thống wireless sensor, trong dự đoán đặc tính của


17

thuốc dùng trong y học, trong nhận dạng và phân loại đối tƣợng, trong khai
phá dữ liệu (KDD).
1.8 Đánh giá kết quả của thuật toán phân cụm


nhằm tìm kiếm một phân hoạch thích hợp thỏa mãn các ràng buộc thông qua
việc sử dụng các thông tin bổ trợ.
Phương pháp dựa trên độ đo tương tự
Trong phƣơng pháp này, các thông tin bổ trợ ban đầu sẽ đƣợc dùng vào
việc huấn luyện một hàm khoảng cách (hàm độ đo). Sau đó thuật toán phân
cụm sẽ sử dụng hàm độ đo nay để phân cụm các dữ liệu.