BÀI TOÁN PHÂN CỤM
Giải thuật và các ứng dụng
11/27/2014
Trường Đại học Bách khoa Hà nội
Viện Công nghệ thông tin và Truyền thông


CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM
Độc lập – Tự do – Hạnh phúc

BẢN XÁC NHẬN CHỈNH SỬA LUẬN VĂN THẠC SĨ
Họ và tên tác giả luận văn: Nguyễn Hoàng Anh
Đề tài luận văn: Bài toán phân cụm: giải thuật và các ứng dụng
Chuyên ngành: Công nghệ thông tin
Mã số SV: CB120053

Tác giả, Người hướng dẫn khoa học và Hội đồng chấm luận văn xác nhận tác giả
đã sửa chữa, bổ sung luận văn theo biên bản họp Hội đồng ngày
….........................………… với các nội dung sau:
……………………………………………………………………………………
………………..………………………………………………………………………
……………………………..…………………………………………………………
……………………………..…………………………………………………………
Ngày 29 tháng 1 năm 2015
Giáo viên hướng dẫn

Tác giả luận văn

CHỦ TỊCH HỘI ĐỒNG

PHIẾU GIAO NHIỆM VỤ LUẬN VĂN CAO HỌC
1. Thông tin giao đề tài luận văn và cán bộ hướng dẫn:
Họ và tên học viên: Nguyễn Hoàng Anh

MSHV: CB120053

Tên đề tài: Bài toán phân cụm: giải thuật và các ứng dụng
Mã đề tài: 2012BCNTT1-KT13

Hệ: Thạc sĩ kỹ thuật

Chuyên ngành: Công nghệ thông tin

Lớp: CNTT-1

Khóa: 2012B
Cán bộ hướng dẫn: TS. Phạm Quang Dũng
Đơn vị: Viện Công nghệ thông tin và Truyền thông, Trường Đại học Bách Khoa Hà
Nội
Thời gian làm LVCH: Từ ngày 13/5 /2013 đến 27/11 /2014

2. Mục đích nội dung của LVCH
 Tìm hiểu tổng quan các thuật toán phân cụm và các ứng dụng.
 Bài toán phân cụm cân bằng và ứng dụng.
 Cài đặt và thử nghiệm giải thuật phân cụm cân bằng.

3. Các nhiệm vụ cụ thể của LVCH







Tìm hiểu tổng quan về phân cụm và các ứng dụng trong thực tế
Tìm hiểu các thuật toán phân cụm cổ điển và các ưu nhược điểm của chúng
Nghiên cứu chi tiết thuật toán phân cụm cân bằng
Cài đặt thử nghiệm thuật toán phân cụm cân bằng trên dữ liệu nguồn
OpenStreetMap là các trạm ATM trên địa bàn Hà Nội.
Đánh giá và kết luận

Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B

Page 3


4. Lời cam đoan của học viên:
Tôi - Nguyễn Hoàng Anh - cam kết LVCH là công sức đóng góp của bản thân tôi dưới
sự hướng dẫn của TS Phạm Quang Dũng.
Các kết quả nêu trong LVCH là trung thực, không phải là sao chép toàn văn của bất kỳ
công trình nào khác.

Hà Nội, ngày 25 tháng 12 năm 2014
Tác giả LVCH

Nguyễn Hoàng Anh
5. Xác nhận của cán bộ hướng dẫn về mức độ hoàn thành của LVCH và cho phép bảo
vệ:

Hà Nội, ngày 25 tháng 12 năm 2014
Cán bộ hướng dẫn


Tiến sĩ Phạm Quang Dũng

Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B

Page 4


TÓM TẮT NỘI DUNG LUẬN VĂN CAO HỌC
PHẦN I : CƠ SỞ LÍ THUYẾT
 CHƯƠNG I : Giới thiệu chung
Giới thiệu tổng quan về phân cụm, bao gồm các định nghĩa cơ bản tới các ứng
dụng của phân cụm trong thực tế. Chương này cũng nêu lên những khó khăn trong việc
phân cụm, chi tiết về các kiểu cụm và cuối cùng là giới thiệu các kĩ thuật phân cụm phổ
biến nhất.
 CHƯƠNG II : Thuật toán phân cụm cổ điển
Tìm hiểu thuật toán phân cụm cổ điển K-means, K-medoid nhưng chỉ tập trung
chi tiết vào thuật toán K-means, thuật toán phân cụm phổ biến nhất. Sau đó các vấn đề
bổ sung, nâng cao khi thực hiện phân cụm theo thuật toán K-means cũng sẽ được đề cập
và cuối cùng là các ưu nhược điểm của thuật toán.
PHẦN II : PHÂN CỤM CÂN BẰNG
 CHƯƠNG III : Bài toán phân cụm cân bằng
Chương này giới thiệu cụ thể về bài toán phân cụm cân bằng, các nhu cầu thực tế
của phân cụm nhưng cần thêm điều kiện ràng buộc cân bằng số điểm bằng nhau trong
mỗi cụm. Chương cũng trình bày một cách tóm tắt về tiến trình thực hiện phân cụm dữ
liệu theo yêu cầu mở rộng này.
 CHƯƠNG IV : Thuật toán phân cụm cân bằng
Chương này nghiên cứu một cách chi tiết về thuật toán phân cụm cân bằng. Ba
bước được trình này vắn tắt ở chương trước đó là : lấy mẫu, phân cụm tập mẫu và phân
phối, lọc sẽ được mô tả cụ thể và trình bày dưới dạng giả ngôn ngữ. Phần trọng tâm của

thuật toán là bước phân phối và lọc. Sau cùng một bước hậu xử lí giúp cải thiện hàm
mục tiêu sẽ được đề xuất.
 CHƯƠNG V : Cài đặt thử nghiệm
Mô tả các bước cài đặt thuật toán dựa vào bộ dữ liệu nguồn OpenStreetMap, là
các điểm ATM có trên địa bàn Hà Nội. Các kết quả so sánh giữa việc phân cụm theo
thuật toán cổ điển K-means và phân cụm theo thuật toán phân cụm cân bằng, sự ổn định
Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B

Page 5


hơn của các cụm khi áp dụng bước hậu xử lí sau khi áp dụng thuật toán phân cụm cân
bằng cũng sẽ được trình bày cụ thể.
TỔNG KẾT ĐÁNH GIÁ
TÀI LIỆU THAM KHẢO

Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B

Page 6


Mục lục
PHIẾU GIAO NHIỆM VỤ LUẬN VĂN CAO HỌC.............................................................. 3
TÓM TẮT NỘI DUNG LUẬN VĂN CAO HỌC.................................................................... 5
LỜI NÓI ĐẦU .......................................................................................................................... 10
PHẦN I : CƠ SỞ LÍ THUYẾT ............................................................................................... 11
Chương I : Giới thiệu chung ................................................................................................... 11
I.1. Tổng quan về phân cụm .................................................................................................... 11
Định nghĩa.......................................................................................................................... 11
Ứng dụng ............................................................................................................................ 11

I.2. Chi tiết về phân cụm.......................................................................................................... 12
I.2.1 Khó khăn trong việc phân cụm .................................................................................. 12
I.2.2 Các kiểu phân cụm ...................................................................................................... 13
Phân cấp và phân vùng ...................................................................................................... 13
Duy nhất, xếp chồng và mờ ................................................................................................ 14
Toàn bộ và bộ phận ............................................................................................................ 14
I.2.3 Các kiểu cụm ................................................................................................................ 14
Well-separated ................................................................................................................... 15
Prototyped-Based ............................................................................................................... 15
Graph-Based ...................................................................................................................... 15
Density-Based .................................................................................................................... 15
Shared-Property ................................................................................................................. 16
I.2.4 Các kĩ thuật phân cụm ................................................................................................ 17
Kĩ thuật K-means............................................................................................................... 17
Kĩ thuật phân cấp xếp đống .............................................................................................. 17
Kĩ thuật DBSCAN ............................................................................................................. 17
Chương II : Thuật toán phân cụm cổ điển ............................................................................ 18
II.1. K-means, K-mendoid ....................................................................................................... 18
II.1.1 Cơ bản về thuật toán K-means ................................................................................. 18
Giải thuật 1. K-means cơ bản ........................................................................................... 18
Gán điểm vào trọng tâm gần nhất .................................................................................... 20
Trọng tâm và các hàm mục tiêu ....................................................................................... 20
Dữ liệu trong tọa độ Ơ-clit ................................................................................................ 21
Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B

Page 7


Dữ liệu văn bản ................................................................................................................. 21
Trường hợp tổng quát ....................................................................................................... 22

Lựa chọn các điểm trọng tâm ban đầu ............................................................................ 22
Ví dụ 1 (Các điểm trọng tâm khởi tạo tồi). [2] .................................................................. 22
Ví dụ 2 (Giới hạn của sự khởi tạo ngẫu nhiên) [2] ............................................................ 23
Độ phức tạp tính toán ....................................................................................................... 26
II.1.2 K-mean : Các vấn đề bổ sung ................................................................................... 26
Điều khiển các cụm rỗng .................................................................................................. 26
Nằm ngoài ......................................................................................................................... 27
Giảm SSE ở bước hậu xử lí .............................................................................................. 27
Cập nhật tăng các điểm trọng tâm ................................................................................... 28
II.1.3 Bisecting K-mean ....................................................................................................... 28
Giải thuật 2. Bisecting K-mean ........................................................................................ 28
Ví dụ 3 ( Bisecting K-mean và khởi tạo). .......................................................................... 29
II.1.4 K-mean và những kiểu cụm khác nhau ................................................................... 30
II.1.5 Điểm mạnh và điểm yếu ............................................................................................ 32
PHẦN 2 : PHÂN CỤM CÂN BẰNG ...................................................................................... 34
Chương III : Bài toán phân cụm cân bằng ............................................................................ 34
Tóm tắt ....................................................................................................................................... 34
Giới thiệu bài toán................................................................................................................ 34
Chương IV : Thuật toán phân cụm cân bằng ....................................................................... 38
Tóm tắt ....................................................................................................................................... 38
IV.1 Lấy mẫu ............................................................................................................................ 40
IV.2 Phân cụm tập mẫu ........................................................................................................... 40
IV.2.1 K-means Ơ clit .......................................................................................................... 41
IV.2.2 K-means hình cầu ..................................................................................................... 41
IV.3 Phân phối và lọc ............................................................................................................... 42
IV.3.1 Thuật toán phân phối ............................................................................................... 43
IV.3.2 Thuật toán lọc ........................................................................................................... 44
Gán từng điểm .................................................................................................................... 45
Gán cụm điểm .................................................................................................................... 45
IV.4 Đề xuất bước hậu xử lí .................................................................................................... 46

Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B

Page 8


Chương V : Cài đặt thử nghiệm ............................................................................................. 48
V.1 Môi trường phát triển và thiết kế ứng dụng ................................................................... 48
Môi trường cài đặt ............................................................................................................. 48
Dữ liệu bản đồ từ OpenStreetMap ..................................................................................... 48
Thiết kế dữ liệu cho một điểm ............................................................................................ 49
Xử lí nguồn dữ liệu bản đồ................................................................................................. 49
Hiển thị các cụm dữ liệu lên Google Map ......................................................................... 50
V.2 Kết quả thử nghiệm .......................................................................................................... 51
V.2.1 Thuật toán K-means .................................................................................................. 51
Chia 3 cụm theo K-means .................................................................................................. 52
Chia 4 cụm theo K-means .................................................................................................. 53
V.2.2 Thuật toán phân cụm cân bằng ................................................................................ 53
Chia 3 cụm theo phân cụm cân bằng ................................................................................. 54
Chia 4 cụm theo phân cụm cân bằng ................................................................................. 55
V.2.3 Độ ổn định sau bước hậu xử lí .................................................................................. 57
TỔNG KẾT ĐÁNH GIÁ ......................................................................................................... 58
1. Đánh giá kết quả ............................................................................................................ 58
2. Kết luận .......................................................................................................................... 59
TÀI LIỆU THAM KHẢO ....................................................................................................... 60

Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B

Page 9



LỜI NÓI ĐẦU

Sau một thời gian tìm hiểu và nghiên cứu rất nhiều các thuật toán phân cụm, em
nhận thấy thuật toán phân cụm cân bằng là một thuật toán mang tư tưởng mới mẻ về
ràng buộc số điểm nằm trong mỗi cụm là bằng nhau, thuật toán có tính ứng dụng cao
trong đời sống hiện nay. Cụ thể như một công ty muốn phân công cho nhân viên của
mình đi lấy dữ liệu khách hàng từ các trạm thông tin, khi đó bài toán đặt ra không chỉ là
chia các trạm thành nhiều cụm mà số trạm trong một cụm cũng phải đều nhau. Mặc dù
chưa phải tuyệt đối mĩ mãn như lí thuyết nhưng các kết quả chạy ứng dụng cài đặt thuật
toán đã thu được một số thành công nhất định. Ngoài nỗ lực bản thân, em còn cần tới
rất nhiều sự trợ giúp của nhiều người để có thể hoàn thành được luận văn cao học như
ngày hôm nay.
Trước hết, em xin gửi lời cảm ơn chân thành và sâu sắc tới TS Phạm Quang Dũng
- Bộ môn Khoa học máy tính, Viện Công nghệ thông tin và Truyền thông, trường Đại
học Bách Khoa Hà Nội đã hết lòng giúp đỡ, định hướng và hướng dẫn tận tình để giúp
em vượt qua từng giai đoạn khó khăn trong quá trình làm luận văn cao học.
Em cũng xin được gửi lời cảm ơn tới các thầy cô giáo trong trường Đại học Bách
Khoa Hà Nội nói chung và các thầy cô trong Viện Công nghệ thông tin và Truyền
thông nói riêng đã tận tình giảng dạy, truyền đạt cho em những kiến thức và kinh
nghiệm quý báu trong thời gian học tập chương trình Thạc sĩ kỹ thuật tại trường Đại
học Bách Khoa Hà Nội.
Cuối cùng em xin gửi lời cảm ơn tới gia đình đã luôn ở bên động viên và trợ giúp,
nhất là luôn luôn tin tưởng vào cá nhân em, để em có thể hoàn thành được bản luận văn
cao học của mình.

Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B

Page 10



PHẦN I : CƠ SỞ LÍ THUYẾT
Chương I : Giới thiệu chung

I.1. Tổng quan về phân cụm
Định nghĩa
Phân cụm chia dữ liệu thành các nhóm (clusters) ý nghĩa hoặc hữu dụng. Mục
đích là những đối tượng trong một nhóm sẽ tương đồng nhau và khác với các đối tượng
trong nhóm khác. Sự tương đồng trong một nhóm càng lớn thì sự khác nhau giữa các
nhóm càng lớn, như vậy là việc phân cụm tốt hơn, độc nhất hơn.
Cụm (Cluster) là một nhóm các đối tượng có chung một số đặc điểm, đóng vai trò quan
trọng trong cách con người phân tích và mô tả thế giới. Thực ra, con người có kĩ năng
phân chia các đối tượng thành các cụm và gán các đối tượng đặc biệt vào các cụm này.
Ví dụ, một đứa trẻ có thể nhanh chóng nhận diện được đâu là tòa nhà, xe cộ, con người,
vật nuôi, cây cối trong một bức tranh. Trong bối cảnh tìm hiểu dữ liệu, clusters là
những lớp tiềm năng và phân tích cụm là kĩ thuật tự động tìm các lớp.
Ứng dụng
Kỹ thuật phân cụm có thể áp dụng trong rất nhiều lĩnh vực như :
Marketing [2]: xác định các nhóm khách hàng (khách hàng tiềm năng, khách hàng giá
trị, phân loại và dự đoán hành vi khách hàng,…) sử dụng sản phẩm hay dịch vụ của
công ty để giúp công ty có chiến lược kinh doanh hiệu quả hơn;
Thư viện [2]: theo dõi độc giả, sách, dự đoán nhu cầu của độc giả
Sinh học [2]: các nhà sinh học đã tốn nhiều năm để phân loại ra tất cả các thể sống :
ngành, lớp, loại, gia đình, loài. Do đó không ngạc nhiên khi từ trước đây họ đã làm việc
với phân tích cụm để tìm ra thuật toán tự động tìm cấu trúc phân loại. Ngày nay, các

Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B

Page 11



nhà sinh học áp dụng phân cụm để phân tích số lượng lớn thông tin di truyền ví dụ để
tìm nhóm các gens có cùng chức năng.
Bảo hiểm, tài chính [2]: Phân nhóm các đối tượng sử dụng bảo hiểm và các dịch vụ tài
chính, dự đoán xu hướng (trend) của khách hàng, phát hiện gian lận tài chính
(identifying frauds)
Truy xuất thông tin [2]: WWW bao gồm hàng tỉ các trang web, kết quả trả về theo một
truy vấn máy tìm kiếm có thể trả lại hàng ngàn trang. Phân cụm có thể dùng để nhóm
những kết quả này lại thành số ít các cụm, mỗi cái chứa một đặc tính cụ thể của truy
vấn. Ví dụ, truy vấn :”movie” có thể được nhóm lại theo catalog là : reviews, trailers,
stars … mỗi catalog (cụm) có thể chia nhỏ hơn thành các catalog con ( sub-cluster), tạo
ra một cấu trúc phân cấp để hỗ trợ người dùng tìm kiếm kết quả.
Chương này giới thiệu về phân tích cụm. Chúng ta bắt đầu xem nhiều cách tiếp cận để
chia các đối tượng thành tập các cụm và những kiểu khác nhau. Sau đó ta mô tả 3 kĩ
thuật phân cụm cụ thể đại diện cho số lượng lớn thuật toán và minh họa cho một vài
khái niệm : K-means, phân cụm phân cấp xếp đống và DBSCAN..
I.2. Chi tiết về phân cụm
Ở phần này sẽ cho chúng ta thấy định nghĩa rõ hơn về phân cụm, minh họa vì sao nó
là khó khăn và giải thích mối quan hệ của nó với những kĩ thuật khác. Ta sẽ khám phá
hai chủ đề quan trọng :
 Những cách khác nhau để nhóm một tập các đối tượng thành một tập các cụm
 Các kiểu cụm.

I.2.1 Khó khăn trong việc phân cụm
Trong rất nhiều ứng dụng, khái niệm của một cụm không được định nghĩa tốt.
Để hiểu rõ hơn về sự khó khăn của việc quyết định những gì tạo thành một cụm, xem
hình 1: 20 điểm và 3 cách khác nhau để chia chúng thành các cụm:
Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B

Page 12



Hình 1 [2]. Các cách phân cụm khác nhau với cùng một tập điểm
Hình dạng của khối đánh dấu các thành viên của cụm. Hình 1(b) và 1(d) chia dữ
liệu thành 2 và 6 phần. Tuy nhiên, sự phân chia rõ ràng hai khối lớn thành 3 khối nhỏ
có thể đơn giản dựa theo trực giác con người và cũng chẳng có lí do gì để không chia
theo như hình 1(c). Hình trên chứng minh rằng định nghĩa về một cụm là không chính
xác và định nghĩa tốt nhất phụ thuộc vào bản chất của dữ liệu và kết quả mà ta mong
muốn.
Phân tích cụm liên quan tới các kĩ thuật chia các đối tượng dữ liệu thành các
nhóm. Ví dụ, phân cụm có thể được xem như một phân loại trong đó nó tạo một nhãn
cho các đối tượng.

I.2.2 Các kiểu phân cụm
Trong phần này chúng ta sẽ phân biệt các loại phân cụm [2]:
-

Phân cấp (hierarchical - nested) với phân vùng (partitional - unnested)

-

Duy nhất (exclusive) với chồng (overlapping) với mờ (fuzzy)

-

Toàn bộ (complete) với bộ phận (partial)

Phân cấp và phân vùng
Điểm khác biệt giữa những kiểu phân cụm được thảo luận nhiều nhất đó là : khi
nào tập các cụm là lồng nhau (hierarchical – nested) hay không lồng nhau (partition Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B


Page 13


unnested). Một partition đơn giản là một sự phân chia tập các đối tượng dữ liệu thành
các tập con không chồng nhau (mỗi đối tượng dữ liệu chính xác nằm trong một tập
con). Hình 1 b-d là phân cụm dạng partition.
Nếu chúng ta cho phép cụm có những cụm con, khi đó ta có kiểu phân cấp
Hierarchical : một tập các cụm lồng nhau được tổ chức theo dạng cây. Mỗi nút là một
cụm (trừ nút lá) là hợp của các con của nó ( subcluter) và gốc của cây chính là cụm tổng
chứa toàn bộ các đối tượng. ví dụ hình 1 a có hai cụm con như 1 b và trong mỗi cụm
con của hình 1 b lại chia ra ba cụm con nữa như hình 1 d. Khi xét theo trật tự đó chúng
ta hình thành lên một cây phân cấp Hierarchical chứa : 1,2,4,6 cụm. Cuối cùng, lưu ý
một cây phân cấp có thể được xem như một chuỗi các phân vùng Partition và một phân
vùng có thể được tách ra bằng cách lấy bất kì đoạn nào trong chuỗi phân vùng của cây
phân cấp Hierarchical đó.

Duy nhất, xếp chồng và mờ
Hình 1 là tất cả là duy nhất: mỗi đối tượng được gắn với duy nhất 1 cụm. Nếu
đối tượng có thể đồng thời gắn với nhiều hơn một cụm ta có dạng xếp chồng
(overlapping hay non-exclusive). Ví dụ : một người ở trường đại học có thể vừa là sinh
viên tham gia học vừa là nhân viên thuộc trường đó. Đối với phân cụm kiểu mờ (fuzzy)
thì mọi đối tượng đều có một tỉ lệ nào đó thuộc về mọi cụm - tỉ lệ trọng số thành viên từ
0 tới 1. Như vậy các cụm được xem xét như các tập mờ.

Toàn bộ và bộ phận
Ở phân cụm kiểu toàn bộ thì mọi đối tượng được gắn vào một cụm, còn bộ phận
thì không.

I.2.3 Các kiểu cụm
Mục đích chính của phân cụm là tìm ra các nhóm đối tượng có ích. Để mô phỏng

Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B

Page 14


sự khác nhau giữa những kiểu của cụm [2], chúng ta dùng các điểm hai chiều như hình
2
Well-separated
Tập các đối tượng mà trong đó mỗi đối tượng gần với những đối tượng trong
cùng cụm hơn các đối tượng nằm khác cụm.

Prototyped-Based
Tập các đối tượng trong đó mỗi đối tượng gần với prototype định nghĩa ra cụm
chứa nó hơn với protype của cụm khác. Ví dụ center-based cụm

Graph-Based
Nếu dữ liệu được biểu diễn dưới dạng đồ thị bao gồm các nút là các đối tượng và
đường nối thì cụm sẽ được hiểu là các bộ phận được kết nối với nhau. Ví dụ : Cụm kề
(contiguity-based clusters) trong đó hai đối tượng chỉ được nối với nhau khi chúng nằm
trong phạm vi khoảng cách quy định của mỗi đối tượng. Có nghĩa là mỗi đối tượng nằm
trong một Contiguity-based cluster sẽ gần với các đối tượng trong cùng cụm hơn bất cứ
điểm nào ở cụm khác. Hình 2 (c) chỉ ra một ví dụ của dạng cụm kề này đối với các
điểm hai chiều.

Density-Based
Một vùng dày đặc các đối tượng được bao quanh bởi một vùng ít dày đặc.

Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B

Page 15



Hình 2 [2]. Các kiểu cụm khác nhau
Shared-Property
Tập các đối tượng mà có chung một vài đặc tính. Cách định nghĩa này bao hàm
toàn bộ các định nghĩa về một cụm mà ta đã đề cập, ví dụ : các đối tượng trong một
cụm hướng tâm có chung thuộc tính là chúng gần nhất với điểm trung tâm. Tuy nhiên,
cách tiếp cận của Shared property cụm bao gồm những kiểu mới của cụm. Xem các
cụm ở hình 2 (e) ta thấy : một cụm vùng tam giác kế cận với một vùng chữ nhật, và có
hai vòng tròn quấn vào nhau, và cần một thuật toán rất chi tiết để nhận diện ra các vùng
cụm này tuy nhiên rất phức tạp ( sang phạm trù nhận diện mẫu) nên chúng ta sẽ chỉ xem
xét những kiểu cụm đơn giản hơn trong luận văn này.

Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B

Page 16


I.2.4 Các kĩ thuật phân cụm
Trong chương này, chúng ta dùng ba kĩ thuật đơn giản nhưng quan trọng sau để
giới thiệu về các khái niệm trong phân tích cụm [2]
Kĩ thuật K-means.
Đây là một kiểu kĩ thuật prototype-based, partitional : cố gắng tìm kiếm một số
xác định người dùng của các cụm (K) – được biểu diễn bởi trọng tâm
Kĩ thuật phân cấp xếp đống
Hướng tiếp cận này liên quan tới một tuyển tập các kĩ thuật phân cụm, nó sinh ra
một phân cụm phân cấp bằng cách bắt đầu với việc xem mỗi điểm là một cụm đơn nhất
và sau đó lặp lại việc gộp hai cụm gần nhất làm một cho tới khi còn lại một cụm bao
quát.
Kĩ thuật DBSCAN

Đây là một thuật toán phân cụm dựa trên mật độ (density-based), nó tạo ra một
phân vùng phân cụm trong đó số lượng các cụm được xác định tự động bởi thuật toán.
Các điểm ở vùng mật độ thưa sẽ được xem là nhiễu và bị bỏ qua, do đó, DBSCAN
không sinh ra một phân cụm hoàn thiện.

Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B

Page 17


Chương II : Thuật toán phân cụm cổ điển

II.1. K-means, K-mendoid
Các kĩ thuật phân cụm dựa trên prototype tạo ra một phân vùng một cấp cho các
đối tượng dữ liệu. Có một số kĩ thuật như vậy nhưng nổi tiếng nhất là K-means và Kmedoid [2]. K-means định nghĩa một prototype về trọng tâm, thường là khoảng giữa
của một nhóm các điểm và thường áp dụng cho các đối tượng ở khoảng n chiều. Kmedoid định nghĩa một prototype về một medoid, đó là điểm tượng trưng đại diện nhất
cho một nhóm các điểm, và có thể áp dụng cho một phạm vi rộng dữ liệu vì nó chỉ cần
một sự đo đạc xấp xỉ cho một cặp đối tượng. Trong khi một trọng tâm thường không
bao giờ tương ứng với một điểm, còn với medoid, sẽ là một điểm. Trong phần này
chúng ta sẽ chỉ tập trung duy nhất vào K-means, thuật toán lâu đời nhất và được sử
dụng rộng rãi nhất.
II.1.1 Cơ bản về thuật toán K-means
Kĩ thuật phân cụm K-means rất đơn giản [2], chúng ta sẽ bắt đầu với một mô tả
cơ bản về thuật toán. Đầu tiên ta chọn trọng tâm khởi tạo K, trong đó K là một tham số
người dùng, số lượng cụm mong muốn. Sau đó mỗi điểm sẽ được gán với trọng tâm gần
nhất, và mỗi tập hợp các điểm được gắn với một trọng tâm sẽ được xem là một cụm.
Trọng tâm của mỗi cụm sau đó được cập nhật lại dựa trên những điểm trong cụm. Ta
lặp lại các bước gán và cập nhật tới khi không có điểm nào thay đổi cụm hay một cách
tương đương : cho tới khi các trọng tâm không còn thay đổi.
K-means được mô tả bởi giải thuật 1 [2]. Sự hoạt động của K-means được minh họa chi

tiết trong hình 3, chỉ rõ cách, từ 3 điểm trọng tâm, những cụm cuối cùng được tìm thấy
qua 4 bước : gán-cập nhật. Trọng tâm được đánh dấu là “+”, các điểm thuộc cùng cụm
được đánh dấu cùng hình dạng
Giải thuật 1. K-means cơ bản
Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B

Page 18


1. Chọn K điểm các trọng tâm khởi tạo
2. Repeat
Hình thành K cụm bằng cách gán mỗi điểm với trọng tâm gần nhất
Tính toán lại trọng tâm của mỗi cụm
Until các trọng tâm không đổi
Bước đầu tiên, hình 3 a, các điểm được gán với các trọng tâm khởi tạo ( các trọng tâm
này đều thuộc nhóm điểm lớn hơn như hình), sau khi các điểm được gắn với một trọng
tâm, ta thực hiện cập nhật lại trọng tâm. Ở bước thứ hai, các điểm được gắn với các
trọng tâm mới và các trọng tâm mới này lại được cập nhật tiếp. Trong bước thứ 2,3,4
như hình 3 (b), (c), (d) tương ứng, ta thấy hai trọng tâm dịch chuyển dần về phía hai
nhóm nhỏ hơn ở phía dưới của hình vẽ, và khi nào không còn thay đổi thì các trọng tâm
này là kết quả chúng ta cần.

Hình 3 [2]. Thuật toán K-means chia bộ dữ liệu làm 3 cụm
Với các kiểu và chức năng kết hợp của các điểm trọng tâm, K-means luôn luôn quy tụ
về một cách giải quyết. Ví dụ, K-means đạt tới trạng thái mà không có điểm nào dịch
chuyển từ cụm này sang cụm kia và do đó, điểm trọng tâm không thay đổi. Tuy nhiên
dòng thứ 5 trong giải thuật 1 thường được thay thế bằng một điều kiện khác dễ hơn, như
: lặp tới khi chỉ 1% các điểm thay đổi cụm.

Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B


Page 19


Chúng ta sẽ xem xét mỗi bước trong giải thuật K-means kĩ hơn và phân tích phạm vi và
độ phức tạp tính toán.
Gán điểm vào trọng tâm gần nhất
Để gán một điểm vào trọng tâm gần nhất, chúng ta cần một thước đo xấp xỉ để
định lượng khái niệm gần nhất. Khoảng cách Ơ-clit (L2) thường được sử dụng cho các
điểm trong tọa độ Ơ-clit. Ngoài ra còn có khoảng cách Manhattan cũng được dùng cho
các điểm dữ liệu Ơ-clit…
Bảng kí hiệu 1
Kí hiệu

Mô tả
Một đối tượng
Cụm thứ ith
Trọng tâm của cụm
Trọng tâm của tất cả các điểm
Số lượng đối tượng trong cụm thứ ith
Số lượng đối tượng trong bộ dữ liệu

K

Số lượng cụm

Trong tọa độ Ơ-clit, ta có thể tránh việc tính toán nhiều lần tương tự nhau bằng cách sử
dụng giải thuật chia đôi K-means, và cách tiếp cận này giúp tăng tốc độ tính toán cho
giải thuật 3.
Trọng tâm và các hàm mục tiêu

Bước thứ 4 của giải thuật K-means được phát biểu là : “Tính toán lại trọng tâm
của mỗi cụm”, mục tiêu của phân cụm thường được biểu diễn bởi một hàm mục tiêu,
phụ thuộc vào sự gần nhau giữa các điểm và các điểm với trọng tâm. Khi chúng ta xác
định được một thước đo xấp xỉ và một hàm mục tiêu, thì trọng tâm có thể được tìm thấy
bằng phương pháp toán học.
Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B

Page 20


Dữ liệu trong tọa độ Ơ-clit
Xét tập dữ liệu có thước đo xấp xỉ là khoảng cách Ơ-clit, còn hàm mục tiêu của
chúng ta : dùng SSE (Sum of the squared error) _ sự phân tán, hay nói cách khác : ta
tính toán lỗi của mỗi điểm. Ví dụ : khoảng cách Ơ-clit tới trọng tâm gần nhất, và sau đó
tính tổng bình phương lỗi.

(1)
Dist : là khoảng cách Ơ-clit giữa hai đối tượng trong hệ tọa độ Ơ-clit.
Trọng tâm nào khiến SSE nhỏ nhất là cái chúng ta cần. Trọng tâm của cụm thứ i được
định nghĩa bởi biểu thức :

(2)
Để mô phỏng, trọng tâm của một cụm có 3 điểm hai chiều (1,1) (2,3) (6,2) là
((1+2+6)/3, (1+3+2)/3) = (3,2). Bước 3 và 4 của thuật toán K-means cố gắng làm tối
giản SSE. Bước 3 định hình các cụm bằng cách gán các điểm với trọng tâm gần nhất,
cách này làm tối giản SSE với một tập các trọng tâm cho trước. Bước 4 tính toán lại các
trọng tâm để tối giản hơn nữa SSE.
Dữ liệu văn bản
Để minh chứng cho việc K-means không bị giới hạn ở dữ liệu trong không gian
Ơ-clit, ta sẽ xem xét trường hợp của document data và độ đo cosin. Giả sử document

data được biểu diễn dưới dạng ma trận tài liệu, mục tiêu của ta là làm lớn nhất sự tương
đồng của các tài liệu trong một cụm đối với trọng tâm – số lượng này còn được gọi là
độ liên kết của cụm (cohesion)

(3)
Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B

Page 21


Trường hợp tổng quát
Có một vài lựa chọn cho hàm không gian, trọng tâm và hàm mục tiêu trong giải
thuật K-means cơ bản [2].

Hàm không gian

Trọng tâm

Hàm mục tiêu

Mahattan

Điểm giữa

Tối giản tổng các L1 (khoảng cách một điểm tới
tâm)

Bình phương Ơ- Điểm giữa

Tối giản tổng các bình phương L2 (khoảng cách


clit

một điểm tới tâm)
Điểm giữa

Cosin

Tối đa tổng của cosin sự đồng dạng của một điểm
tới tâm

Phân kỳ Bregman

Điểm giữa

Tối giản tổng phân kỳ Bregman của một điểm tới
tâm

Lựa chọn các điểm trọng tâm ban đầu
Nếu sử dụng lựa chọn ngẫu nhiên, thuật toán K-means sẽ cho ra các tổng SSE
khác nhau. Ta mô phỏng với tập các điểm hai chiều như hình 3 với 3 cụm cho trước.
Hình 4 (a) chỉ ra một phương án phân cụm mà làm tối giản SSE cho toàn bộ 3 cụm,
trong khi đó hình 4 (b) chỉ ra phương án chỉ tối ưu ở mức cục bộ.
Lựa chọn đúng điểm trọng tâm ban đầu rất quan trọng. Thường thì người ta hay chọn
ngẫu nhiên và kéo theo là các cụm có chất lượng kém.
Ví dụ 1 (Các điểm trọng tâm khởi tạo tồi). [2]
Lựa chọn một cách ngẫu nhiên điểm trọng tâm ban đầu có thể là tồi ví dụ như
với cùng một tập các điểm như hình 3 ( hoặc 4). Hình 3 và 5 chỉ ra các cụm được tạo
thành từ hai cách lựa chọn điểm trọng tâm ban đầu khác nhau. Trong hình 3, cho dù tất
cả các điểm trọng tâm khởi tạo đều nằm trong một nhóm, thì SSE vẫn được tìm thấy.

Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B

Page 22


Trong hình 5, cho dù các trọng tâm khởi tạo dường như được phân bố tốt hơn, chúng ta
lại thu được các cụm với tổng bình phương lỗi nhiều hơn (SSE).

Hình 5 [2]. Các điểm khởi tạo tồi với K-means
Ví dụ 2 (Giới hạn của sự khởi tạo ngẫu nhiên) [2]
Một kĩ thuật hay được dùng cho vấn đề lựa chọn điểm trọng tâm ban đầu là thực
hiện nhiều lần chạy, mỗi lần chọn ngẫu nhiên các điểm trọng tâm khác nhau và cuối
cùng chọn phương án tạo ra các cụm có SSE nhỏ nhất. Phương pháp này đơn giản
nhưng có thể không tốt lắm, nó phụ thuộc vào tập dữ liệu và số lượng các cụm cần tìm.
Ta sẽ chứng minh điều này bằng cách sử dụng tập dữ liệu như hình 6 (a).

Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B

Page 23


Hình 6 [2]. Hai cặp điểm khởi tạo nằm trong hai cặp cụm
Tập dữ liệu chứa hai cặp cụm (hai nhóm trên và dưới tạo thành một cặp), hai
cụm trong cùng một cặp gần nhau hơn so với hai cụm ở cặp còn lại. Hình 6 (b-d) chỉ ra
nếu chúng ta chọn 2 điểm trọng tâm ban đầu ở mỗi cặp, thì sau đó, cho dù cả hai trọng
tâm nằm trong một cụm thì cuối cùng chúng cũng được phân bố lại và ta tìm thấy các
cụm cần thiết. Tuy nhiên, hình 7 chỉ ra rằng nếu một cặp cụm ban đầu chỉ có một điểm
trọng tâm và cặp cụm còn lại có 3 điểm trọng tâm thì cuối cùng ta thu được: hai cụm
ban đầu kết hợp lại và có một cụm ban đầu bị chia ra.


Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B

Page 24


Hình 7 [2]. Hai cặp cụm có nhiều điểm hơn hoặc ít hơn so với cụm khởi tạo ban đầu
Chú ý, phân cụm đạt được trạng thái tối ưu ngay khi hai điểm trọng tâm ban đầu
rơi vào bất cứ đâu trong một cặp cụm, khi đó, các điểm trọng tâm sẽ tự phân phối lại,
mỗi điểm sẽ gắn vào một cụm. Không may, khi số lượng cụm lớn, nó sẽ phát triển theo
hướng tối thiểu một cặp cụm sẽ chỉ có một điểm trọng tâm. Trong trường hợp này, vì
hai cặp cụm cách xa nhau hơn khoảng cách giữa những cụm ở ngay trong nó, thuật toán
K-mean sẽ không phân phối lại trọng tâm giữa các cặp cụm, do đó, chỉ có một điểm
trọng tâm tìm thấy.
Do vấn đề với việc chọn ngẫu nhiên điểm trọng tâm khởi tạo ban đầu, mà việc
lặp lại việc chạy thử nhiều lần không có kết quả tốt thì các kĩ thuật khác sẽ được áp
dụng cho giai đoạn khởi tạo này. Một cách hiệu quả là lấy một mẫu điểm và phân chia
chúng sử dụng kĩ thuật chia phân cấp. K cụm sẽ được trích từ việc chia phân cấp, và
Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B

Page 25