Đại học Quốc gia Thành phố Hồ Chí Minh
Trường Đại học Công nghệ thông tin
Khoa Mạng máy tính và truyền thông
o0o
Bài báo cáo môn:
KHAI PHÁ DỮ LIỆU VÀ
KHO DỮ LIỆU
Đề tài:
Thuật toán K-Means và ứng
dụng trong thực tế
GVHD : PGS.TS. Đỗ Phúc
Học viên : Bùi Anh Kiệt
MSHV : CH1101018
Tp. Hồ Chí Minh – Ngày 24 tháng 11 năm 2012
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
Lời mở đầu
Dữ liệu trong tự nhiên là một tài nguyên vô tận, nó tồn tại ở rất nhiều dạng, vật
chất, thông tin kể cả con người. Và trong thời đại của công nghệ thông tin, dữ liệu
của tự nhiên dần dần chuyển thành dạng thông tin và lưu trữ khắp nơi trên thế
giới số.
Khai thác dữ liệu là một ngành khoa học có nhiều ứng dụng trong thực tế, đặc
biệt là trong các ngành kinh tế học. Việc khai thác dữ liệu có hiệu quả hay không
phụ thuộc vào nhiều yếu tố. Hai trong số đó là thuật toán dùng để khai phá dữ
liệu và loại dữ liệu muốn khai phá. Trong điều kiện công nghệ thông tin phát triển
mạnh, dữ liệu tự nhiên đã hầu như chuyển thành dạng dữ liệu số và đó chính là
điều kiện để các thuật toán khai phá dữ liệu có cơ hội phát triển bùng nổ.
Trong các thuật toán về khai phá dữ liệu, thuật toán gom cụm dữ liệu được biết
đến nhiều vì khả năng áp dụng của nó trong việc phân tích và chọn lọc dữ liệu
cần thiết từ nguồn dữ liệu số. Và trong các thuật toán gom cụm, thuật toán K-
Means được xem như một thuật toán cơ bản, khởi đầu cho phương pháp khai phá
dữ liệu bằng cách gom cụm.

Học viên: Bùi Anh Kiệt – CH1101018 3
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
1 Thuật toán K-Means
1.1 Tổng quan
K-Means là thuật toán phân cụm dữ liệu, dùng để tiếp cận phân hoạch. Số
lượng cụm trong phân hoạch là một số cố định cho trước. Các cụm được hình
thành dựa vào khoảng cách các điểm trung tâm. Một điểm sẽ thuộc vào một cụm
nếu như khoảng cách từ điểm đó đến điểm trung tâm của cụm là nhỏ nhất trong số
các khoảng cách từ điểm đó đến các điểm trung tâm.
Vì vậy, cần khởi tạo một tập các điểm trung tâm ban đầu để làm nền tảng
.cho việc tính toán và phân lại cụm cho các điểm trong đồ thị. Quá trình xác định
cụm cho một điểm được thực lặp đi lặp lại nhiều lần, sau mỗi lần tính toán, các
điểm trung tâm sẽ thay đổi vị trí và các cụm của đồ thị cũng thay đổi theo. Quá
trình tính toán và xác định cụm cho các điểm dừng lại khi thành phần các cụm
tương đối ổn định (các điểm thuộc vào các cụm không thay đổi).
Trong phương pháp K-means, chọn một giá trị k và sau đó chọn ngẫu nhiên
k trung tâm của các đối tượng dữ liệu. Tính toán khoảng cách giữa đối tượng dữ
liệu trung bình mỗi cùm để tìm kiếm phần tử nào là tương tự và thêm vào cụm đó.
Từ khoảng cách này có thể tính toán trung bình mới của cụm và lặp lại quá trình
cho đến khi mỗi các đối tượng dữ liệu là một bộ phận của các cụm k.
Mục đích của thuật toán K-means là sinh k cụm dữ liệu {C1, C2,…, Ck} từ
một tập dữ liệu chứa n đối tượng trong không gian d chiều Xi = {xi1, xi2,…xid},
i = 1÷ n, sao cho hàm tiêu chuẩn :

đạt giá trị tối tiểu.
Trong đó: m
i
là trọng tâm của cụm Ci, D là khoảng cách giữa hai đối tượng.
Trọng tâm của cụm là một vector, trong đó giá trị của mỗi phần tử của nó là trung
cộng của các thành phần tương ứng của các đối tượng vector dữ liệu trong cụm

x
4
x
5
c
1
1 1 0 0 0
c
2
0 0 1 0 1
c
3
0 0 0 1 0
Học viên: Bùi Anh Kiệt – CH1101018 5
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
Trong ma trận phân hoạch trên, ta thấy ứng với mỗi cột chỉ có một dòng có
giá trị 1 điều đó thể hiện mỗi đối tượng trong một thời điểm chỉ thuộc về
một cụm.
Sau mỗi lượt gán cụm cho các đối tượng, ma trận phân hoạch lại được cập
nhật. Trong suốt quá trình cập nhật, một đối tượng vẫn chỉ thuộc một cụm
duy nhất.
(2) Vector trọng tâm
Vector trọng tâm chính là vị trí của điểm trung tâm của mỗi cụm. Vector
trọng tâm trong từng thời điểm là không giống nhau và nó phụ thuộc vào số
lượng các điểm nằm trong cụm đó.
Các tính vector trọng tâm được thể hiện như sau:
với:
và
Trong đó, m
ij

k: số cụm cần phân hoạch
- K-Means phù hợp với các cụm có dạng hình cầu.
- Có khả năng mở rộng và dể dàng sửa đổi với những dữ liệu mới.
- Bảo đảm hội tụ sau một số bước lặp hữu hạn.
- Số cụm luôn ổn định (k cụm cho trước).
- Luôn có ít nhất một điểm trong cụm.
- Các cụm được tách biệt rỏ rang không có hiện tượng một đối tượng xuất
hiện trong nhiều cụm dữ liệu.
2. Nhược điểm:
- Không đảm bảo đạt được tối ưu toàn cục và kết quả đầu ra phụ thuộc
vào nhiều vào việc chọn k điểm khởi đầu.
- Cần xác định trước số cụm.
Học viên: Bùi Anh Kiệt – CH1101018 7
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
- Khó xác định được thực sự số cụm có trong không gian dữ liệu. Do đó
có thể phải thử với các số k khác nhau.
- Khó phát hiện các loại cụm có hình dạng phức tạp và nhất là các dạng
cụm không lồi.
- Không thể xử lí nhiều mẫu cá biệt (nhiễu).
- Chỉ có thể áp dụng khi tính được trọng tâm.
1.4 Các biến thể của thuật toán K-Means
1.4.1 Thuật toán K-Medoid
Thuật toán K-Medoid tương tự thuật toán K-Means, mỗi cụm được đại diện bởi
một trong số các đối tượng của cụm. Thông thường thì điểm gần vector trọng tâm
sẽ được chọn làm điểm đại diện của cụm.
Thuật toán K-Medoid khắc phục được yếu điểm là loại được nhiễu trong thuật
toán K-Means. Nhưng bù lại, độ phức tạp của thuật toán lại rất lớn.
1.4.2 Thuật toán Fuzzy C-Means
Thuật toán Fuzzy C-Means có chiến lược phân cụm giống như K-Means. Nhưng
có một điểm khác biệt là K-Means phân cụm dữ liệu cứng (một đối tượng chỉ

- Mục tiêu của phân cụm là có được một chuỗi các cụm hyperellipsoidal bắt
đầu với các trung tâm cụm vị trí tại các vị trí mật độ tối đa trong không gian
mẫu, và các cụm phát triển về các trung tâm cho đến khi một thử nghiệm tốt
đẹp của x
2
cho phù hợp đã bị vi phạm. Một loạt các tính năng được thảo luận
và áp dụng cho cả hai màu xám và màu sắc hình ảnh.
Học viên: Bùi Anh Kiệt – CH1101018 9
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
- Kỹ thuật Clustering cũng đã được sử dụng thành công được cho nhiều phân
đoạn của hình ả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:
(1) Các thuật giải áp dụng kỹ thuật chia và trộn vùng.
(2) Các thuật giải áp dụng kỹ thuật tăng trưởng vùng.
(3) Các thuật giải áp dụng lý thuyết đồ thị.
(4) Các giải thuật áp dụng mạng neural.
(5) Các giải thuật dựa trên cạnh.
2.2 Nhận dạng
Có hai kỹ thuật nhận dạng chính trong thuật toán nhận dạng là nhận dạng đối
tượng và nhận dạng kí tự:
- Nhận dạng đối tượng là rút trích hình ảnh đối tượng trong trong một tập đối
tượng xuất hiện trong hình ảnh. Nhận dạng đối tượng được áp dụng nhiều
trong các ngành khoa học tiên tiến như y khoa, sinh hóa hay khoa học hình
sự… Trong y khoa, thuật toán nhận dạng đối tượng giúp ích cho việc xác
định các đối tượng lạ (vật thể lạ, khối u bứu…) trong hình ảnh chụp từ bên
trong cơ thể. Việc xác định các đối tượng lạ này thông qua việc so sánh đối
tượng của hai bức ảnh tương đương, dựa vào đó mà các chuyên viên y khoa

Hiện nay, bên cạnh nguồn dữ liệu có được từ việc thu thập thực tế thông qua khảo
sát thị trường thì nguồn dữ liệu từ internet đã và đang đóng vai trò cốt yếu trong
việc khai thác thị trường. Nguồn dữ liệu từ internet được xem là một trong những
nguồn dữ liệu chính và là nguồn dữ liệu vô tận mà rất nhiều tổ chức (có thể là cá
nhân) quan tâm và muốn khai thác. Ví dụ như: thông tin khách hàng, ý kiến khách
Học viên: Bùi Anh Kiệt – CH1101018 11
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
hàng về sản phẩm hay quan điểm khách hàng về những mặc hàng xuất hiện trong
tương lai.
Với sự phát triển mạnh mẽ của công nghệ thông tin hiện nay, internet đã và đang
trở thành cở sở dữ liệu vô tận. Nguồn dữ liệu này có ý nghĩa với rất nhiều tổ chức
và cá nhân đặc biệt là các tổ chức và cá nhân trong lĩnh vực kinh doanh. Do đó,
việc khai thác nguồn dữ liệu vô tận được lưu trữ trên internet đã và đang trở thành
một hướng đi mới trong việc khai thác thị trường. Một khi thành công trong việc
khai thác dữ liệu khách hàng từ internet, vấn đề tìm hiểu và khai thác thị trường sẽ
trở nên đơn giản và hiệu quả cao. Hiệu quả về chi phí là điểm nổi bật có thể nhìn
thấy được, bên cạnh đó hiệu quả về thời gian cũng là một điểm đáng ghi nhận.
Mọi thông tin khách hàng đã có sẵn, tuy nhiên làm thế nào để phân loại và đánh
giá nó chính xác đòi hỏi người làm công việc khai thác thị trường phải bỏ công
sức đầu tư để có một thuật toán phân tích và tổng hợp thật hiệu quả. Và với công
việc này, thuật toán gom cụm được sử dụng như phương pháp chính để khai hoàn
thành mục đích đặt ra.
Học viên: Bùi Anh Kiệt – CH1101018 12
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
3 Cài đặt thuật toán K-Means
3.1 Ý tưởng thuật toán K-Means
Thuật toán K-Means được hình thành bởi MacQueen từ 1967, là một trong những
thuật toán đơn giản nhất dùng để giải quyết vấn đề gom cụm. Quá trình xử lí dựa
trên số cụm của đối tượng được cho trước. Ý tưởng chính của thuật toán là dựa
vào số cụm cho trước, hình thành tương ứng số vector trọng tâm cho mỗi cụm. và

Bước 3:
(1) Gán điểm đang xét vào cụm mà khoảng cách từ điểm đang xét đó đến
vector trọng tâm của cụm là nhỏ nhất (cập nhật ma trận phân hoạch ở vị
trí cột là điểm đang xét).
(2) Thực hiện bước trên cho đối tượng tiếp theo.
Bước 4:
(1) Xét xem ma giá trị của ma trận phân hoạch có ổn định hay không. Nếu đã
ổn định (đạt điều kiện dừng) thì ngừng chương trình.
(2) Quay lại bước 2.
3.3 Hướng phát triển của thuật toán
Thuật toán K-Means là khởi nguồn của hệ thống các thuật toán gom cụm, vậy nên
song song với những điểm mạnh vẫn còn tồn tại nhiều hạn chế. Cũng vì lẽ đó nên
đã có rất nhiều thuật toán kế thừa K-Means và cải thiện những yếu điểm mà K-
Means mắc phải. Kết quả của quá trình cải thiện K-Means là đáng ghi nhận khi có
rất nhiều thuật toán ra đời như K-Medoid, Fuzzy C-Means hay PAM, CLARAR…
Tuy nhiên, đến thời điểm hiện tại vẫn chưa có thuật toán nào có thể đạt được hiệu
quả tuyệt đối.
Học viên: Bùi Anh Kiệt – CH1101018 14
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
Vì lẽ đó nên để hệ thống thuật toán gom cụm đạt hiệu quả cao chúng ta cần phải
hạn chế yếu điểm của thuật toán càng nhiều càng tốt (vì không thể loại bỏ những
yếu điểm tồn tại trong thuật toán).
Phương pháp dễ nhận thấy nhất trong thuật toán K-Means chính là việc hình thành
ma trận phân hoạch đầu tiên như thế nào để các cụm hình thành sau quá trình này
là tương đối ổn định. Vậy nên trong quá trình cải tiến K-Means, có rất nhiều học
giả đã chọn phương pháp này. Tuy nhiên, làm cách nào để có thể đạt được hiệu
quả tối ưu của quá trình hình thành ma trận phân hoạch ban đầu là việc làm vô
cùng phức tạp.
Bên cạnh vai trò quyết định của ma trận phân hoạch khởi đầu, một điểm cần chú ý
trong việc cải thiện tốc độ thuật toán là tinh lọc quá trình tính toán để xác định

rất nhiều lĩnh vực cuộc sống. Và hai mảng chính mà K-Means đóng vai trò chủ
đạo là phân đoạn ảnh và khai phá dữ liệu.
Tuy nhiên với những đặc điểm nổi trội trong việc gom cụm, K-Means sẽ còn được
ứng dụng nhiều hơn và đóng vai trò cốt yếu trong nhiều lĩnh vực khác của cuộc
sống.
Học viên: Bùi Anh Kiệt – CH1101018 16
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
Phụ lục
Giới thiệu về chương trình cài đặt cho thuật toán K-Means.
Hình 1. Giao diện chương trình cài đặt thuật toán K-Means
Chương trình demo cung cấp cho người sử dụng hai tuỳ chọn về hình thức đưa dữ
liệu ban đầu vào. Có thể lựa chọn thao tác bằng tay và chọn mở file đã có sẵn
(mặc định chương trình cung cấp là mở file có sẵn).
Nội dung của file có sẵn là số lượng cụm của đồ thị và vị trí của các đối tượng
trong đồ thị.
Học viên: Bùi Anh Kiệt – CH1101018 17
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
Hình 2. Nội dung file dữ liệu đầu vào
Học viên: Bùi Anh Kiệt – CH1101018 18
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
Hình 3. Giao diện người dùng cho việc chọn dữ liệu đầu vào có sẵn
Học viên: Bùi Anh Kiệt – CH1101018 19
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
Hình 3. Giao diện người dùng cho việc chọn thao tác dữ liệu đầu vào
Chương trình hổ trợ tại một thời điểm chỉ có một cách thức nhập liệu được cho
phép (hoặc chọn dữ liệu từ file sẵn có hoặc nhập giá trị mới).
Button “submit” dùng để đưa dữ liệu nhập vào khung “Object information”.
Học viên: Bùi Anh Kiệt – CH1101018 20
Khai phá dữ liệu & kho dữ liệu Thuật toán K-Means & ứng dụng thực tế
Hình 4. Submit dữ liệu hiển thị