ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN

BÁO CÁO
TÌM HIỂU CLUSTERING
Lớp : CAO HỌC KHÓA 6
GVHD : PGS-TS Đỗ Phúc
Sinh Viên : Phạm Quang Diệu
MSSV : CH1101077
Tp Hồ Chí Minh, tháng 11 năm 2012
Tìm hiểu Clustering - Khai Phá Dữ Liệu Và Kho Dữ Liệu
Trang
GIỚI THIỆU
Phép phân tích nhóm chia dữ liệu thành những nhóm (group, cluster) có
nghóa, hữu ích, hay cả hai. Nếu mục đích là những nhóm có nghóa, thì những nhóm
nên giữ được cấu trúc tự nhiên của dữ liệu. Tuy nhiên, trong một số trường hợp,
phép phân tích nhóm chỉ là điểm khởi đầu hữu ích cho một mục đích khác, như sự
tổng kết dữ liệu. Dù trong nghiên cứu hay ứng dụng, thì phép phân tích nhóm đã
đóng một vai trò quan trọng trong rất nhiều lónh vực: tâm lý học và những ngành
khoa học xã hội khác, sinh học, khoa học thống kê, sự nhận dạng, phục hồi thông
tin, máy học, và data mining.
Có nhiều ứng dụng của phép phân tích nhóm đối với những vấn đề thực tiễn.
Chúng tôi cung cấp một vài ví dụ đặc trưng, tùy theo mục đích nghiên cứu hay ứng
dụng.
NGHIÊN CỨU
Những lớp, hay những nhóm đối tượng trừu tượng có nghóa mà chia sẻ những
đặc điểm chung, đóng một vai trò quan trọng trong việc làm thế nào con người
phân tích và mô tả thế giới. Quả thực, con người khéo léo trong việc phân chia các
đối tượng vào các nhóm (clustering) và gán những đối tượng riêng biệt vào những
nhóm này (classification). Ví dụ, những đứa bé nhanh chóng dán nhãn cho những
vật trong một tấm ảnh như những tòa nhà, xe cộ, con người, động vật, cây cối,

thể dùng để nhận dạng những mẫu trong sự phân bố không gian hay thời gian
của một bệnh.
• Kinh doanh
Việc kinh doanh đòi hỏi những lượng lớn thông tin trên những khách hàng
hiện tại và tiềm năng. Phép xếp nhóm có thể được dùng để phân đoạn những
khách hàng vào những nhóm cho những hoạt động phân tích và tiếp thò.
ỨNG DỤNG
Phép phân tích nhóm cung cấp sự trừu tượng hóa từ những đối tượng dữ liệu
riêng lẻ thành những nhóm đối tượng. Ngoài ra, một số kỹ thuật xếp nhóm mô tả
đặc điểm mỗi nhóm dưới dạng nguyên mẫu nhóm; nghóa là, dùng một đối tượng
dữ liệu làm đại diện cho những đối tượng khác trong nhóm. Những nguyên mẫu
nhóm này có thể được dùng như cơ sở cho một số kỹ thuật phân tích hay xử lý dữ
liệu. Do đó, trong lónh vực ứng dụng, phép phân tích nhóm nghiên cứu những kỹ
thuật để tìm những nguyên mẫu nhóm tiêu biểu nhất.
• Sự tổng hợp
Nhiều kỹ thuật phân tích dữ liệu, như PCA, có độ phức tạp thời gian hay
không gian là O(m
2
) hay cao hơn (với m là số đối tượng), và do đó, không áp
dụng được cho những tập hợp dữ liệu lớn. Tuy nhiên, thay vì dùng thuật toán
cho toàn bộ tập hợp dữ liệu, ta có thể áp dụng đối với một tập hợp dữ liệu
được giảm chỉ chứa những nguyên mẫu nhóm. Phụ thuộc vào kiểu phân tích,
số nguyên mẫu, và độ chính xác mà nguyên mẫu đại diện cho dữ liệu, mà
kết quả có thể so sánh được với trường hợp áp dụng cho tất cả dữ liệu.
• Nén
SVTH: Phạm Quang Diệu – MSSV: CH1101077
Tìm hiểu Clustering - Khai Phá Dữ Liệu Và Kho Dữ Liệu
Trang
Những nguyên mẫu nhóm cũng có thể được dùng cho nén dữ liệu. Cụ thể là,
một bảng chứa những nguyên mẫu cho mỗi nhóm được tạo ra; nghóa là, mỗi

tích nhóm, giải thích mối liên quan của nó với những kỹ thuật nhóm dữ liệu khác.
Sau đó chúng ta xem xét hai vấn đề quan trọng: (1) những cách khác nhau để xếp
một tập hợp các đối tượng vào một tập hợp các nhóm, và (2) những loại nhóm.
1.1 THẾ NÀO LÀ PHÉP PHÂN TÍCH NHÓM?
Phép phân tích nhóm gom nhóm những đối tượng dữ liệu chỉ dựa trên thông
tin được tìm thấy trong dữ liệu mà mô tả những đối tượng đó hay và những mối
quan hệ của chúng. Mục đích là những đối tượng bên trong một nhóm tương tự
(hay liên quan) với nhau và chúng khác nhau (hay không liên quan) với những đối
tượng trong những nhóm khác. Nếu sự tương tự trong một nhóm càng lớn và sự
khác nhau giữa các nhóm càng nhiều, thì phép xếp nhóm càng tốt hơn hay dễ phân
biệt hơn.
Trong nhiều ứng dụng, khái niệm một nhóm không được đònh nghóa rõ ràng.
Để hiểu rõ hơn sự khó khăn khi quyết đònh cái gì tạo thành một nhóm, xem hình
8.1, biểu diễn hai mươi điểm và ba cách phân nhóm khác nhau. Những kí hiệu chỉ
rõ thành phần của mỗi nhóm. Hình 8.1(b) và 8.1(d) lần lượt chia dữ liệu thành hai
và sáu phần. Không thể không có lý khi cho rằng các điểm tạo thành bốn nhóm,
như trong hình 8.1(c). Hình này biểu diễn đònh nghóa một nhóm là không chính xác
và đònh nghóa tốt nhất phụ thuộc vào trạng thái nguyên thủy của dữ liệu và những
kết quả mong muốn.
SVTH: Phạm Quang Diệu – MSSV: CH1101077
Tìm hiểu Clustering - Khai Phá Dữ Liệu Và Kho Dữ Liệu
Trang
Phép phân tích nhóm liên quan đến những kỹ thuật khác được dùng để chia
những đối tượng dữ liệu vào các nhóm. Ví dụ, phép xếp nhóm có thể được xem
như một dạng của phép phân loại trong đó nó tạo ra sự đánh nhãn các đối tượng.
Tuy nhiên, nó nhận được các nhãn này chỉ từ dữ liệu. Ngược lại, phép phân loại là
một supervised classification; nghóa là, những đối tượng mới chưa được đánh
nhãn được gán một nhãn sử dụng một mô hình có được từ những đối tượng đã được
đánh nhãn. Vì lý do này, phép xếp nhóm thường được xem như unsupervised
classification.

phép xếp nhóm hierarchical có thể xem như một chuỗi các phép xếp nhóm
SVTH: Phạm Quang Diệu – MSSV: CH1101077
Tìm hiểu Clustering - Khai Phá Dữ Liệu Và Kho Dữ Liệu
Trang
partitional; nghóa là, khi cắt ra mỗi cấp của cây thứ bậc thì ta có một phép xếp
nhóm partitional.
Exclusive với Overlapping với Fuzzy
Những phép xếp nhóm trong hình 8.1 đều là exclusive, khi chúng gán mỗi
đối tượng vào một nhóm. Có nhiều trường hợp trong đó một điểm có thể được đặt
trong nhiều hơn một nhóm, và những trường hợp này là non-exclusive. Thông
thường, một phép xếp nhóm overlapping hay non-exclusive được dùng để phản
ánh sự kiện rằng một đối tượng có thể đồng thời thuộc về hơn một nhóm (class).
Ví dụ, một người ở trường đại học có thể là sinh viên được tuyển và một nhân viên
của trường. Một phép xếp nhóm non-exclusive cũng thường được dùng, ví dụ, khi
một đối tượng ở giữa nhiều hơn hai nhóm và có thể được gán đến bất kỳ nhóm
nào. Tưởng tượng một điểm nằm giữa hai nhóm trong hình 8.1. Thay vì gán tùy ý
đối tượng vào một nhóm nào đó, thì nó được đặt vào tất cả những nhóm như thế.
Trong một phép xếp nhóm fuzzy, mỗi đối tượng thuộc về một nhóm với một
trọng số giữa 0 (hoàn toàn không thuộc) và 1 (hoàn toàn thuộc). Nói cách khác,
những nhóm như những tập hợp fuzzy. (Trong toán học, một tập hợp fuzzy là tập
hợp trong đó một đối tượng thuộc bất cứ tập nào với trọng số giữa 0 và 1. Trong
phép xếp nhóm fuzzy, chúng ta thường đưa ra ràng buộc bổ sung mà tổng các
trọng số của mỗi đối tượng phải bằng 1). Tương tự, những kỹ thuật xếp nhóm theo
thống kê tính toán xác suất mà mỗi điểm thuộc về mỗi nhóm, và mỗi xác suất này
cũng phải có tổng là 1. Fuzzy clustering thích hợp nhất để tránh việc gán tùy ý một
đối tượng vào chỉ một nhóm khi nó có thể gần với nhiều nhóm. Trong thực tế,
fuzzy clustering thường được chuyển đổi thành exclusive clustering bằng cách gán
mỗi đối tượng vào nhóm trong đó trọng số hay xác suất của nó là cao nhất.
Complete với Partial
Complete clustering gán mỗi đối tượng vào một nhóm, trái lại partial

khác. Đối với dữ liệu có những thuộc tính liên tục, nguyên mẫu của một nhóm
thường là trung tâm, nghóa là, trung bình (mean) của tất cả các điểm trong nhóm.
Với nhiều kiểu dữ liệu, nguyên mẫu có thể xem như điểm trung tâm nhất, và trong
những trường hợp như thế, chúng ta thường xem những nhóm prototype-based như
center-based. Thường những nhóm như vậy có hình cầu. Hình 8.2(b) cho một ví
dụ nhóm center-based.
Graph-Based
Nếu dữ liệu được biểu diễn đồ thò, với các nút là các đối tượng và các cung
biểu diễn liên kết giữa các đối tượng, thì một nhóm được đònh nghóa là một thành
phần liên thông (connected component); nghóa là, một nhóm đối tượng được liên
kết với nhau, nhưng không có liên kết đến những đối tượng ngoài nhóm. Một ví dụ
quan trọng của graph-based cluster là contiguity-based cluster (cluster dựa trên sự
kề nhau), trong đó hai đối tượng chỉ được liên kết nếu chúng cách nhau một
khoảng được chỉ rõ. Điều này có nghóa là mỗi đối tượng trong contiguity-based
cluster gần với đối tượng khác trong nhóm hơn bất kỳ điểm nào trong nhóm khác.
Hình 8.2(c) cho một ví dụ với những điểm hai chiều. Đònh nghóa nhóm này hữu ích
khi các nhóm không theo quy luật hay quấn vào nhau (intertwined), nhưng có thể
gặp vấn đề khi xuất hiện nhiễu như minh họa bởi hai nhóm hình cầu trong hình
8.2(c), một cầu nhỏ của các điểm có thể kết hợp hai điểm phân biệt.
Density-Based
Một nhóm là 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ơn. Hình 8.2(d) biểu diễn các nhóm density-based với dữ liệu được tạo
thành bằng cách thêm nhiễu vào dữ liệu của hình 8.2(c). Hai nhóm tròn không
SVTH: Phạm Quang Diệu – MSSV: CH1101077
Tìm hiểu Clustering - Khai Phá Dữ Liệu Và Kho Dữ Liệu
Trang
được kết hợp như trong hình 8.2(c), vì cầu giữa chúng biến mất trong nhiễu. Cũng
vậy, đường cong trong hình 8.2(c) cũng biến mất trong nhiễu và không tạo thành
nhóm trong hình 8.2(d). Đònh nghóa nhóm density-based thường được dùng khi các
nhóm không theo quy luật, và khi xuất hiện nhiễu và giá trò ngoại lệ. Ngược lại,

chiều.
SVTH: Phạm Quang Diệu – MSSV: CH1101077
Tìm hiểu Clustering - Khai Phá Dữ Liệu Và Kho Dữ Liệu
Trang
PHẦN 2
NHỮNG THUẬT TOÁN
2.1 K-MEANS
Hai kỹ thuật quan trọng nhất là K-means và K-medoid. K-means đònh nghóa
một nguyên mẫu là một trọng tâm (centroid), thường là trung tâm của một nhóm
điểm, và được ứng dụng cho những đối tượng trong một không gian n chiều liên
tục. K-medoid đònh nghóa một nguyên mẫu là một medoid, là điểm đại diện nhất
cho một nhóm điểm, và có thể áp dụng cho một phạm vi dữ liệu rộng vì nó chỉ đòi
hỏi một phép đo lân cận cho một cặp đối tượng. Trong khi centroid không bao giờ
tương ứng với một điểm dữ liệu thật sự, thì một medoid phải là một điểm dữ liệu
thật sự. Trong phần này, chúng ta chỉ tập trung đến K-means, một trong những
phương pháp cũ nhất và được dùng rộng rãi nhất.
2.1.1 THUẬT TOÁN K-MEANS CƠ BẢN
Phép xếp nhóm K-means đơn giản, và chúng ta bắt đầu mô tả thuật toán cơ
bản. Đầu tiên ta chọn K trọng tâm, với K là tham số cho bởi người dùng, gọi là số
nhóm. Sau đó mỗi điểm được gán với một trọng tâm gần nhất, và mỗi tập điểm
được gán với một trọng tâm là một nhóm. Ta lặp lại việc gán và cập nhật các bước
cho đến khi không còn điểm nào thay đổi nhóm.
K-means được mô tả trong thuật toán 8.1. Thuật toán được minh họa cụ thể
trong hình 8.3. Trong những hình này, mỗi hình nhỏ biểu diễn (1) những trọng tâm
lúc đầu và (2) phép gán các điểm đến các trọng tâm đó. Những trọng tâm được
biểu diễn bởi dấu “+”; tất cả các điểm thuộc cùng một nhóm có cùng kí hiệu như
nhau.

Thuật toán 8.1 Thuật toán K-means cơ bản.
1: Chọn K điểm như những trọng tâm đầu tiên.

những điểm dữ liệu trong không gian Euclid. Tuy nhiên, có thể có nhiều phép đo
độ lân cận thích hợp cho một nhóm dữ liệu được cho. Ví dụ, khoảng cách
Manhattan (L
1
) có thể dùng cho dữ liệu Euclid, trong khi phép đo Jaccard thường
được dùng cho những tài liệu.
Thông thường, những phép đo lân cận dùng cho K-means thường đơn giản vì
thuật toán tính toán lặp đi lặp lại sự lân cận của mỗi điểm với mỗi trọng tâm. Tuy
nhiên, trong một số trường hợp, nhưng khi dữ liệu nằm trong không gian Euclid ít
chiều, có thể tránh được việc tính toán nhiều sự lân cận, do đó tăng đáng kể tốc độ
của thuật toán K-means. Bisecting K-means (được mô tả trong phần 8.2.3) là một
SVTH: Phạm Quang Diệu – MSSV: CH1101077
Tìm hiểu Clustering - Khai Phá Dữ Liệu Và Kho Dữ Liệu
Trang
cách tiếp cận khác làm tăng tốc độ của K-means bằng cách giảm số lượng tính
toán lân cận.
Bảng 8.1. Bảng ký hiệu
Ký hiệu Mô tả
x
C
i
c
i
c
m
i
m
K
Một đối tượng.
Nhóm thứ i.

i Cx
i
i
xcdistSSE
1
2
),(
(8.1)
với dist là khoảng cách Euclid chuẩn (L
2
) giữa hai đối tượng trong không gian
Euclid.
SVTH: Phạm Quang Diệu – MSSV: CH1101077
Tìm hiểu Clustering - Khai Phá Dữ Liệu Và Kho Dữ Liệu
Trang
Theo những giả thuyết này, có thể nói rằng (xem phần 8.2.6) trọng tâm tối
thiểu hóa SSE của nhóm là trung bình. Dùng kí hiệu trong bảng 8.1, trọng tâm
(trung bình) của nhóm thứ i được đònh nghóa bởi phương trình 8.2.
∑
∈
=
i
Cx
i
i
x
m
c
1
(8.2)

Có một số lựa chọn cho hàm lân cận, trọng tâm, và hàm mục tiêu có thể
dùng trong thuật toán K-means cơ bản. Bảng 8.2 biểu diễn một số lựa chọn có thể,
bao gồm hai cái mà chúng ta vừa mới thảo luận. Lưu ý rằng khoảng cách
Manhattan (L
1
) và mục tiêu tối thiểu hóa tổng các khoảng cách, trọng tâm thích
hợp là trung vò các điểm trong một nhóm.
Bảng 8.2. K-means: Những lựa chọn thông thường cho hàm lân cận, trọng
tâm, và hàm mục tiêu
Hàm lân cận Trọng tâm Hàm mục tiêu
SVTH: Phạm Quang Diệu – MSSV: CH1101077
Tìm hiểu Clustering - Khai Phá Dữ Liệu Và Kho Dữ Liệu
Trang
Manhattan (L1) Trung vò Tối thiểu hóa tổng khoảng cách L
1
của một đối
tượng đến trọng tâm của nhóm nó.
Euclid bình phương Trung bình Tối thiểu hóa tổng khoảng cách L
2
bình phương
của một đối tượng đến trọng tâm của nhóm nó.
Cosine Trung bình Tối đa hóa tổng sự đồng dạng cosine của một
đối tượng đến trọng tâm của nhóm nó.
Sự phân kỳ Bregman Trung bình Tối thiểu hóa tổng sự phân kỳ Bregman của
một đối tượng đến trọng tâm của nhóm nó.
Sự phân kỳ Bregman thật ra là một lớp phép đo lân cận bao gồm khoảng
cách Euclid bình phương,
2
2
L

biểu diễn bởi dấu gạch chéo).
Ví dụ: Những giới hạn của sự khởi tạo ngẫu nhiên
Một kỹ thuật được dùng thông thường để giải quyết vấn đề chọn những trọng
tâm ban đầu là thực hiện nhiều lần chạy, mỗi lần với một bộ khác nhau các trọng
tâm ban đầu được chọn ngẫu nhiên, và sau đó chọn ra tập hợp các nhóm với SSE
nhỏ nhất. Cách này có thể không thực hiện tốt, tùy thuộc vào tập dữ liệu và số
nhóm được tìm kiếm. Chúng ta biểu diễn điều này dùng bộ dữ liệu mẫu cho trong
hình 8.6(a). Dữ liệu bao gồm hai cặp nhóm, với các nhóm trong mỗi cặp (cặp trên-
dưới) gần nhau hơn các nhóm trong cặp khác. Hình 8.6(b-d) chỉ ra rằng nếu ta bắt
đầu với hai trọng tâm ban đầu đối với mỗi cặp nhóm, thì thậm chí khi tất cả trọng
tâm ở trong một nhóm duy nhất, những trọng tâm sẽ được phân phối lại để tìm
được các nhóm đúng. Tuy nhiên, hình 8.7 chỉ ra rằng nếu một cặp nhóm chỉ có một
trọng tâm ban đầu và cặp khác có ba, thì hai trong các nhóm đúng sẽ được kết hợp
và một nhóm đúng sẽ được chia ra.
SVTH: Phạm Quang Diệu – MSSV: CH1101077
Tìm hiểu Clustering - Khai Phá Dữ Liệu Và Kho Dữ Liệu
Trang
Lưu ý rằng một phép gom nhóm tối ưu sẽ đạt được cho đến khi hai trọng tâm
ban đầu rơi vào trong một cặp nhóm, vì các trọng tâm sẽ được phân phối lại đến
mỗi nhóm.
Vì những vấn đề với việc dùng những trọng tâm ban đầu được chọn ngẫu
nhiên, mà những lần chạy lặp lại có thể không vượt qua. Một cách tiếp cận hiệu
quả là lấy một mẫu các điểm và gom nhóm chúng dùng kỹ thuật gom nhóm
hierarchical. K nhóm rút ra từ phép gom nhóm hierarchical, và những trọng tâm
của những nhóm đó được dùng như những trọng tâm ban đầu. Cách này thường
hoạt động tốt, nhưng thực hiện được chỉ nếu (1) bộ mẫu tương đối nhỏ, ví dụ, vài
trăm đến vài ngàn, và (2) K tương đối nhỏ so với kích thước mẫu.
SVTH: Phạm Quang Diệu – MSSV: CH1101077
Tìm hiểu Clustering - Khai Phá Dữ Liệu Và Kho Dữ Liệu
Trang

nhóm. Chi tiết của thuật toán bisecting K-means như sau:
Thuật toán 8.2 Thuật toán bisecting K-means.
1: Khởi tạo danh sách các nhóm để chứa nhóm bao gồm tất cả các điểm.
2: repeat
3: Loại bỏ một nhóm từ danh sách các nhóm.
4: {Thực hiện nhiều lần chia đôi “thử" nhóm được chọn.}
5: for i = 1 to number of trials do
6: Chia đôi nhóm được chọn bằng phương pháp K-means cơ
bản.
7: end for
8: Chọn ra hai nhóm từ việc chia đôi với SSE tổng cộng nhỏ nhất.
9: Thêm hai nhóm này vào danh sách các nhóm
10: until Danh sách nhóm chứa K nhóm.
Có nhiều cách khác nhau trong việc chọn ra nhóm nào để chia. Ta có thể
chọn nhóm lớn nhất ở mỗi bước, chọn nhóm với SSE lớn nhất, hay dùng một tiêu
chuẩn dựa trên cả kích thước và SSE. Những lựa chọn khác nhau sẽ cho ra những
nhóm khác nhau.
Ví du: Bisecing K-means và sự khởi tạo
Để minh họa rằng bisecting K-means ít bò ảnh hưởng bởi vấn đề khởi tạo
hơn, ta biểu diễn trong hình 8.8, bisecting K-means tìm ra bốn nhóm như thế nào
trong bộ dữ liệu ban đầu biểu diễn trong hình 8.6(a). Ở bước lặp 1, hai cặp nhóm
SVTH: Phạm Quang Diệu – MSSV: CH1101077
Tìm hiểu Clustering - Khai Phá Dữ Liệu Và Kho Dữ Liệu
Trang
được tìm thấy; ở bước lặp 2, cặp nhóm bên phải được chia ra; và ở bước 3, cặp
nhóm bên trái được chia ra. Bisecting K-means ít gặp vấn đề hơn với việc khởi tạo
bởi vì nó thực hiện nhiều lần chia đôi thử và dùng lần thử có SSE nhỏ nhất, và bởi
vì chỉ có hai trọng tâm ở mỗi bước.
Cuối cùng, bằng cách ghi lại chuỗi các phép gom nhóm có được K-means
chia đôi các nhóm, ta cũng có thể dùng bisecting K-means để tạo ra hierarchical

means không phù hợp cho tất cả các loại dữ liệu. Tuy nhiên, K-means không thể
xử lý các nhóm không là hình cầu hay các nhóm có kích thước và độ dày đặc khác
nhau, mặc dù nó có thể tìm thấy các nhóm con nếu như đủ nhiều các nhóm được
chỉ rõ. K-means cũng có gặp vấn đề khi gom nhóm dữ liệu chứa những giá trò
ngoại lệ. Tìm và loại bỏ các giá trò ngoại lệ có thể giúp đáng kể trong các trường
hợp như vậy. Cuối cùng, K-means bò giới hạn đối với dữ liệu có trung tâm (center,
SVTH: Phạm Quang Diệu – MSSV: CH1101077
Tìm hiểu Clustering - Khai Phá Dữ Liệu Và Kho Dữ Liệu
Trang
centroid). Một kỹ thuật liên quan, K-medoid clustering, không có hạn chế này,
nhưng tốn kém hơn.
2.1.5 K-MEANS NHƯ MỘT VẤN ĐỀ TỐI ƯU HÓA
Ở đây, ta sẽ nghiên cứu sâu vào phương pháp toán đằng sau phương pháp K-
means. Phần này, có thể được bỏ qua mà không mất tính liên tục, đòi hỏi kiến
thức giải tích thông qua những đạo hàm riêng.
Như đã đề cập từ trước, cho một hàm mục tiêu là “tối thiểu hóa SSE”, phép
gom nhóm có thể coi như vấn đề tối ưu hóa. Một cách để giải quyết vấn đề này –
tìm một điều kiện tối ưu toàn cục – là đánh số tất cả các cách khả thi để chia các
điểm vào các nhóm và sau đó chọn ra tập các nhóm mà thỏa mãn hàm mục tiêu
nhất, ví dụ, tối thiểu hóa SSE tổng. Dó nhiên, cách vét cạn này là bất khả thi về
mặt tính toán và do đó, một cách tiếp cận thực tế hơn rất cần thiết, cho dù cách
tiếp cận đó tìm ra những giải pháp không đảm bảo tối ưu. Một kỹ thuật, được biết
như gradient descent, dựa trên việc chọn một giải pháp ban đầu và sau đó lặp lại
hai bước sau: tính toán sự thay đổi đến giải pháp mà tối ưu hóa hàm mục tiêu nhất
và sau đó cập nhật giải pháp.
Ta giả sử rằng dữ liệu là một chiều, nghóa là, dist(x, y) = |x – y|. Điều này
thực chất không làm thay đổi bất cứ thứ gì, nhưng làm đơn giản hóa đáng kể khái
niệm.
Đạo hàm của K-means như một thuật toán cực tiểu hóa SSE
Trong phần này, ta biểu diễn làm thế nào trung tâm trong thuật toán K-

0).(2)()(
1
2
1
2
=−=−
∂
∂
=−
∂
∂
=
∂
∂
∑∑∑∑∑
∈= ∈= ∈
kii
Cx
k
K
i Cx
i
k
K
i Cx
i
kk
xcxc
c
xc

tối thiểu hóa. Ta đang tìm cách cực tiểu hóa tổng các sai số tuyệt đối L
1
(SAE)
theo phương trình dưới đây, với
1
L
dist
là khoảng cách L
1
. Để đơn giản ý tưởng, ta
sử dụng dữ liệu một chiều, nghóa là,
xcdist
iL
−=
1
.
∑∑
= ∈
=
K
i Cx
iL
i
xcdistSAE
1
),(
1
(8.5)
Ta có thể giải quyết cho trung tâm thứ k là c
k

xc
c
xc
c
xc
c
SSE
c
00 =−⇒=−
∂
∂
∑∑
∈∈
kk
Cx
k
Cx
k
k
cxsignxc
c
Nếu ta giải quyết cho c
k
, ta tìm
}{
kk
Cxmedianc ∈=
, trung vò của các điểm
trong nhóm.
SVTH: Phạm Quang Diệu – MSSV: CH1101077