Cải tiến thuật toán K-Means và ứng dụng phân cụm dữ liệu tự động

Nguyễn Văn Huân và cs Tạp chí KHOA HỌC & CÔNG NGHỆ 61(12/2): 102 - 106 
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên  
102 
CẢI TIẾN THUẬT TOÁN K-MEANS VÀ ỨNG DỤNG 
PHÂN CỤM DỮ LIỆU TỰ ĐỘNG 
Nguyễn Văn Huân 1, Phạm Việt Bình1, Trương Mạnh Hà1, Vũ Xuân Nam1, Đoàn Mạnh Hồng2 
1 Khoa Công nghệ thông tin – Đại học Thái Nguyên, 
2 Trường Đại học Kinh tế và Quản trị Kinh doanh – Đại học Thái Nguyên 
TÓM TẮT 
Phân cụm dữ liệu tự động là một bài toán phức tạp và được nhiều nhà khoa học nghiên cứu, bước 
đầu họ đã đưa ra được một số thuật toán như: K-means, K-medoids,.. và đã đạt được những kết 
quả nhất định trong tìm kiếm, phân loại dữ liệu. Tuy nhiên, hầu hết những thuật toán này, khi phân 
cụm đều yêu cầu xác định số cụm cần thực thi đặc biệt là với thuật toán K-means hoặc yêu cầu 
mức độ khác biệt trong việc xác định các thành phần có tính chất giống nhau. Ngoài ra, các kỹ 
thuật này còn đòi hỏi phải chọn trước số điểm làm trọng tâm, với số điểm chọn ngẫu nhiên làm 
trọng tâm này sẽ cho các kết quả khác nhau. Do vậy, các kết quả có thể là không chính xác, với 
mức độ sai số có thể rất lớn. 
Bài báo đưa ra cải tiến thuật toán K-means trong phân cụm tài liệu web, thay vì chọn số điểm làm 
trọng tâm thì không chọn số điểm làm trọng tâm cho số cụm mà sẽ tăng số cụm từ 1 lên k cụm bằng 
cách đưa trung tâm cụm mới vào cụm có mức độ biến dạng Max và tính lại trọng tâm các cụm. 
Từ khoá: K-Means, phân cụm, Data mining, Web mining, K-Medoids. 
 GIỚI THIỆU 
Sự phát triển nhanh chóng của mạng Internet 
đã sinh ra một khối lượng khổng lồ các dữ 
liệu dạng siêu văn bản (dữ liệu Web). Các tài 
liệu siêu văn bản chứa đựng văn bản và 
thường nhúng các liên kết đến các tài nguyên 
khác phân bố trên Web. Ngày nay, Web bao 
gồm hàng tỷ tài liệu của hàng triệu tác giả 
được tạo ra và được phân tán qua hàng triệu 
máy tính được kết nối qua đường dây điện 
thoại, cáp quang, sóng radio v.v.. Web đã và 
đang được sử dụng phổ biến trong nhiều lĩnh 
vực như báo chí, phát thanh, truyền hình, hệ 
thống bưu điện, trường học, các tổ chức 
thương mại, chính phủ v.v.. Chính vì vậy lĩnh 
vực Web mining hay tìm kiếm tự động các 
thông tin phù hợp và có giá trị trên Web là 
một chủ đề quan trọng trong Data Mining và 
là vấn đề quan trọng của mỗi đơn vị, tổ chức 
có nhu cầu thu thập và tìm kiếm thông tin trên 
Internet. 
Hiện nay, các hệ thống tìm kiếm thông tin hay 
nói ngắn gọn là các máy tìm kiếm Web thông 
thường trả lại một danh sách các tài liệu được 
phân hạng mà người dùng sẽ phải tốn công 
 Tel: 0987 118 623, Email: nvhuan@ictu.edu.vn 
chọn lọc trong một danh sách rất dài để có 
được những tài liệu phù hợp. Ngoài ra các 
thông tin đó thường rất phong phú, đa dạng 
và liên quan đến nhiều đối tượng khác nhau. 
Điều này tạo nên sự nhập nhằng gây khó khăn 
cho người sự dụng trong việc lấy được các 
thông tin cần thiết. 
Có nhiều hướng tiếp cận khác nhau để giải 
quyết vấn đề này. Các hướng này thường chú 
ý giảm sự nhập nhằng bằng các phương pháp 
lọc hay thêm các tùy chọn để cắt bớt thông tin 
và hướng biểu diễn các thông tin trả về bởi 
các máy tìm kiếm thành từng cụm để cho 
người dùng có thể dễ dàng tìm được thông tin 
mà họ cần. Đã có nhiều thuật toán phân cụm 
tài liệu dựa trên phân cụm ngoại tuyến toàn 
bộ tập tài liệu. Tuy nhiên việc tập hợp tài liệu 
của các máy tìm kiếm là quá lớn và luôn thay 
đổi thì khó có thể phân cụm ngoại tuyến. Do 
đó, việc phân cụm phải được ứng dụng trên 
tập các tài liệu nhỏ hơn được trả về từ các 
truy vấn và thay vì trả về một danh sách rất 
dài các thông tin gây nhập nhằng cho người 
sử dụng cần có một phương pháp tổ chức lại 
các kết quả tìm kiếm một cách hợp lý. 
Hiện nay, đã có nhiều kỹ thuật, thuật toán về 
thu thập, phân cụm dữ liệu tự động [2, 5, 6, 
Nguyễn Văn Huân và cs Tạp chí KHOA HỌC & CÔNG NGHỆ 61(12/2): 102 - 106 
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên  
103 
11, 12], tuy nhiên hầu hết các kỹ thuật này khi 
phân cụm đều yêu cầu xác định số cụm cần 
thực thi đặc biệt là với thuật toán K-means 
hoặc yêu cầu mức độ khác biệt trong việc xác 
định các thành phần có tính chất giống nhau. 
Ngoài ra, các kỹ thuật này còn đòi hỏi phải 
chọn trước số điểm làm trọng tâm, với số 
điểm chọn ngẫu nhiên làm trọng tâm này sẽ 
cho các kết quả khác nhau. Do vậy, các kết 
quả trên có thể là không chính xác, với mức 
độ sai số có thể rất lớn. Để khắc phục nhược 
điểm trên, nhóm tác giả cải tiến thuật toán K-
means trong thu thập, phân cụm tài liệu Web 
và thay vì chọn số điểm làm trọng tâm, chúng 
ta không chọn số điểm làm trọng tâm cho số 
cụm mà sẽ tăng số cụm từ 1 lên k cụm bằng 
cách đưa trung tâm cụm mới vào cụm có mức 
độ biến dạng lớn nhất và tính lại trọng tâm 
các cụm. 
MỘT SỐ THUẬT TOÁN PHÂN CỤM 
DỮ LIỆU 
Thuật toán K-means 
Tư tưởng: Đầu tiên chọn ngẫu nhiên K mẫu, 
mỗi mẫu này coi như biểu diễn 1 cluster, lúc 
này trong mỗi cluster thì đối với mỗi mẫu đó 
cũng là tâm của cluster. Các mẫu còn lại được 
gán vào một nhóm nào đó trong K nhóm đã 
có sao cho tổng khoảng cách từ nhóm mẫu đó 
đến tâm của nhóm là min. Rồi, tính lại tâm 
cho các nhóm và lặp lại quá trình đó cho đến 
khi hàm tiêu chuẩn hội tụ. Hàm tiêu chuẩn 
hay được dùng nhất là hàm tiêu chuẩn sai-số 
vuông. Thuật toán này, có thể áp dụng được 
đối với cơ sở dữ liệu (CSDL) đa chiều, nhưng 
để dễ minh họa chúng tôi mô tả thuật toán 
trên dữ liệu hai chiều. 
Thuật toán k-means được mô tả như sau: 
Input: K, và dữ liệu về n mẫu của 1 CSDL. 
Output: Một tập gồm K cluster sao cho cực tiểu 
về tổng sai-số vuông. 
Các bước thuật toán: 
Bước 1: Chọn ngẫu nhiên K mẫu vào K cluster. 
Coi tâm của cluster chính là mẫu có trong cluster. 
Bước 2: Tìm tâm mới của cluster. 
Bước 3: Gán các mẫu vào từng cluster sao cho 
khoảng cách từ mẫu đó đến tâm của cluster đó là 
nhỏ nhất. 
Bước 4: Nếu các cluster không có sự thay đổi nào 
sau khi thực hiện bước 3 thì chuyển sang bước 5, 
ngược lại sang bước 2. 
Bước 5: Dừng thuật toán. 
Ví dụ: Trong không gian hai chiều, cho 12 
điểm (n = 12) cần phân 12 điểm này thành 
hai cluster (k=2). 
Đầu tiên, chọn hai điểm ngẫu nhiên vào hai 
cluster (chọn 2 điểm màu đỏ: (1,3); (9,4)) 
Coi điểm (1,3) là tâm của cluster 1 và điểm 
(9,4) là tâm của cluster 2. Tính toán khoảng 
cách từ các điểm khác đến hai điểm này và 
gán được các điểm còn lại này vào một trong 
hai cluster, những điểm có màu trắng vào 
cluster 1, những điểm có màu đen vào cluster 
2. Hiệu chỉnh lại tâm của hai cluster, điểm 
màu xám là tâm mới của hai cluster. Tính lại 
các khoảng cách các điểm đến tâm mới và 
gán lại các điểm này. Tiếp tục hiệu chỉnh lại 
tâm của hai cluster. Rồi, lặp lại cho đến khi 
không còn sự thay đổi nữa thì dừng. 
Hình 1. Minh họa thuật toán K-means 
Độ phức tạp của thuật toán này là O(tKn). 
Trong đó n là số mẫu trong CSDL, K là số 
cluster, t là số lần lặp. Thông thường t,k << n. 
Nên thuật toán này có hiệu quả tương đối với 
các CSDL lớn [Han 2001]. 
Nhận xét: Thuật toán K-means có ưu điểm là 
dễ dàng cài đặt, nhưng lại có nhược điểm là 
phải chỉ ra số lượng cluster và yêu cầu CSDL 
cần phân nhóm phải xác định được tâm. 
Thuật toán này không phù hợp với việc khai 
phá các dữ liệu gồm các cluster có hình dạng 
không lồi. Có thể đưa thêm nhiều cải tiến vào 
K-means để được thuật toán hiệu quả hơn, 
như thay đổi cách chọn các mẫu khởi đầu, 
cách tính tiêu chuẩn,... 
Thuật toán K-Medoid 
Nguyễn Văn Huân và cs Tạp chí KHOA HỌC & CÔNG NGHỆ 61(12/2): 102 - 106 
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên  
104 
Tư tưởng: Để tìm ra k cụm với n đối tượng 
thì k-medoids chọn ngẫu nhiên k đối tượng 
vào k cụm, coi mỗi đối tượng này là tâm của 
cụm. Phân bổ các đối tượng còn lại vào cụm 
mà sự khác nhau của nó với đối tượng tâm 
của cụm là gần nhất. Sau đó lặp lại quá trình: 
Thay đổi đối tượng tâm của mỗi cụm sao cho 
chất lượng của cụm được cải thiện. Chất 
lượng của cụm được lượng giá bởi một hàm 
đo sự khác nhau giữa một đối tượng và đối 
tượng tâm của cụm chứa nó. Quá trình lặp 
cho đến khi không còn sự thay đổi nào về lực 
lượng cũng như hình dạng của các cụm. 
Để chọn một đối tượng không là đối tượng 
tâm Orandom thay thế tốt cho một đối tượng tâm 
Oj thì mỗi đối tượng p xét theo 4 trường hợp 
sau đây: 
Trường hợp 1: p đang thuộc vào cụm có tâm 
là Oj (từ nay gọi là cụm Oj). Nếu Oj được thay 
thế bởi Orandom và p gần nhất với Oi (i j) thì p 
được gán lại vào Oi 
Trường hợp 2: p đang thuộc vào Oj. Nếu Oj 
được thay thế bởi Orandom và p gần nhất với 
Orandom thì p được gán lại vào Orandom. 
Trường hợp 3: p đang thuộc vào Oi (i j). Nếu 
Oj được thay thế bởi Orandom và p vẫn gần nhất 
với Oi thì không thay đổi gì cả. Tức là p vẫn 
thuộc Oi. 
Trường hợp 4: p đang thuộc vào Oi (i j). Nếu 
Oj được thay thế bởi Orandom và p gần nhất với 
Orandom thì p được gán lại vào Orandom. 
Hình 2. Các trường hợp đối với điểm p 
Thuật toán K-medoid được mô tả như sau: 
Input: Số nguyên k và CSDL gồm n đối tượng 
cần phân cụm. 
Output: Một tập gồm k cụm mà tổng giá trị của 
sự khác nhau của tất cả các đối tượng đến đối 
tượng tâm của nhóm chứa nó là nhỏ nhất. 
Thuật toán: 
Bước 1: Chọn k đối tượng bất kì vào k cụm. Coi 
mỗi đối tượng này là tâm của nhóm. 
Bước 2: Lặp 
Bước 3: Gán mỗi đối tượng còn lại vào một cụm 
mà nó gần với đối tượng tâm của cụm nhất. 
Bước 4: Chọn ngẫu nhiên một đối tượng không là 
đối tượng tâm, Orandom. 
Bước 5: Tính lại giá trị, S, đối với việc đổi Oj với 
Orandom. 
Bước 6: Nếu S<0 thì đổi Oj với Orandom để tạo ra 
một tập với đối tượngtâm mới. 
Bước 7: Đến khi không có sự thay đổi nào nữa thì 
dừng. 
Ví dụ: Trong không gian hai chiều cho n = 10 
điểm, cần chia thành k =2 cụm. Các bước 
thực hiện của thuật toán K-medoids được chỉ 
ra trong hình 3: 
Đầu tiên, chọn hai điểm bất kì vào hai cụm 
(điểm màu đen), rồi xét các điểm còn lại và 
đưa chúng vào một trong hai cụm với điểm 
tâm lần lượt là hai điểm đã chọn ban đầu. 
Tiếp theo, chọn một điểm bất kì khác điểm 
tâm (điểm màu xám). Tính giá của phép 
chuyển đổi điểm tâm từ điểm màu trắng -> 
điểm màu xám. Nếu giá này chất lượng hơn 
thì coi điểm xám là tâm của cụm mới và thực 
lặp lại quá trình đó cho đến khi không còn sự 
thay đổi nào. 
Nhận xét: Thuật toán K-medoids mạnh hơn 
thuật toán K-means trong các trường hợp dữ 
liệu có nhiễu vì K-medoids chịu ảnh hưởng ít 
hơn của nhiễu và các giá trị chênh lệnh so với 
giá trị trung bình. Tuy nhiên cả hai thuật toán 
này đều yêu cầu đưa vào số lượng cụm k. 
CẢI TIẾN THUẬT TOÁN K-MEANS 
TRONG PHÂN CỤM DỮ LIỆU TỰ ĐỘNG 
Bài toán thu thập, phân cụm dữ liệu tự động 
là một bài toán mang tính thời sự, vì trong 
thời đại công nghệ thông tin, với sự trợ giúp 
của máy tính thì việc áp dụng công nghệ 
thông tin vào thu thập dữ liệu tự động trên 
Internet, phân tích phục vụ cho việc phân cụm 
và từ đó hình thành các chủ đề thông tin với 
các dữ liệu thu thập tự động từ Internet. Trên 
cơ sở đó, chúng ta tiến hành phân tích dữ liệu 
Nguyễn Văn Huân và cs Tạp chí KHOA HỌC & CÔNG NGHỆ 61(12/2): 102 - 106 
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên  
105 
và đưa ra những dự báo trong tương lai với 
từng chủ đề khác nhau như: dự báo tốc độ 
tăng trưởng kinh tế, GDP, chỉ số chứng 
khoán, giá cả hàng hoá,...Điều này làm cơ sở 
cho chúng ta có thể đưa ra một chính sách 
phát triển kinh tế trong cả nước. Tuy nhiên, 
để có được những dữ liệu và phân cụm được 
những dữ liệu đó theo các chủ đề khác nhau 
thì chúng ta phải có các kỹ thuật. Như mục 2, 
nhóm tác giả đã giới thiệu thuật toán K-
Means, tuy nhiên thuật toán có những hạn chế 
nhất định. Do đó, nhóm tác giả cải tiến thuật 
toán này nhằm khắc phục những hạn chế của 
thuật toán K-means. 
Cải tiến thuật toán K-means: thay vì chọn số 
điểm (k) làm trọng tâm, chúng ta không chọn 
số điểm (k) làm trọng tâm cho số cụm mà sẽ 
tăng số cụm từ 1 lên k cụm bằng cách đưa 
trung tâm cụm mới vào cụm có mức độ biến 
dạng lớn nhất và tính lại trọng tâm các cụm. 
Với thuật toán K- means bắt đầu bằng cách 
chọn k cụm và chọn ngẫu nhiên k điểm làm 
trung tâm cụm, hoặc chọn phân hoạch ngẫu 
nhiên k cụm và tính trọng tâm của từng cụm 
này. Việc chọn ngẫu nhiên k điểm làm trung 
tâm cụm như đã nói ở trên có thể cho ra các 
kết quả khác nhau tùy vào chọn k điểm này. 
Thuật toán K-means cải tiến: 
Bước 1: Khởi tạo giá trị ban đầu cho K: K=1 
Bước 2: 
Bước 2.1: Kiểm tra điều kiện K 
Nếu K=1: chọn bất kỳ một điểm làm trung tâm 
của cụm. 
Nếu K>1: thêm trung tâm của cụm mới vào cụm 
có biến dạng max. 
Bước 2.2: Gán từng điểm vào cụm có trung tâm 
gần nhất với điểm đang xét và cập nhật lại trung 
tâm cụm 
Bươc 2.3: Nếu trung tâm cụm không thay đổi, 
chuyển sang bước 3. 
Ngược lại, quay trở lại bước 2.2 (bước 2). 
Bước 3: (Tăng số cụm) 
Nếu K≤ giá trị ấn định số cụm thì K:=K+1, quay trở 
lại bước 2.1 (bước 2). 
Ngược lại, thuật toán dừng. 
Với thuật toán K-means cải tiến: đưa ra sự 
khác biệt, đó là mức độ biến dạng của các 
cụm (dựa trên biến dạng để phân cụm).Mức 
độ biến dạng của các cụm được tính như sau: 
 I=S-N(d(w,x )) 
Trong đó: w: trung tâm của cụm, N: Số các thành 
phần trong cụm; S: Tổng bình phương khoảng 
cách giữa các thành phần trong cụm và trung tâm 
của không gian Euclidean; I: Mức độ biến dạng 
của cụm; d(w,x): là khoảng cách giữa trung tâm w 
của cụm và trung tâm của không gian Euclidean x. 
Nhận xét: 
+ Một cụm có mức độ biến dạng lớn thì trung 
tâm cụm đó có vị trí không thích hợp. 
+ Việc xác định các cụm cũng như xác định 
trung tâm của cụm, như vậy thuật toán chủ 
yếu tìm trung tâm cụm chính xác và xác định 
lại các thành phần trong cụm. 
Với thuật toán K-means cải tiến: 
+ Bước 2: như K-means nhưng khác là: 
không xác định trước k điểm mà tăng k lên 
dần từ 1. Và chọn cụm có mức độ biến dạng 
lớn để phân ra 2 cụm (khi đó 2 cụm này có 
mức độ biến dạng giảm, nhỏ hơn). 
+ Thuật toán cải tiến K-means có độ phức tạp 
là O(k
2 nt), như vậy so với thuật toán K-means 
có độ phức tạp O(tkn) thì: O(k
2 nt)>O(tkn), 
nhưng không bằng K-mendoids, do k<<n. 
Tuy nhiên ưu điểm của thuật toán là giảm sự 
phụ thuộc vào việc khởi tạo các cụm ban đầu 
nên ta sẽ không phải lặp lại thuật toán với 
việc chọn các cụm ban đầu khác nhau để tìm 
ra kết quả tối ưu như ở K-Means. 
THỬ NGHIỆM 
Để đánh giá thuật toán cải tiến K-means, 
nhóm tác giả sử dụng các dữ liệu lấy từ các 
trang Web với các nguồn chính sau: 
+ Các trang được lấy tự động từ các website 
trên internet, việc tìm kiếm được thực hiện 
bằng cách dùng Google, chương trình sẽ dựa 
vào URL để lấy tài liệu và lưu trữ lại phục vụ 
cho quá trình tìm kiếm sau này. 
+ Tìm kiếm có chọn lọc với các chủ đề tin về 
"Chứng khoán", khoảng 250 bài; Chủ đề tin 
về "Tỷ giá hối đoái", khoảng 100 bài; Chủ đề 
tin về "Giá vàng", khoảng 150 bài; Chủ đề tin 
về "Thời tiết", khoảng 50 bài. Các chủ đề đều 
có tần số xuất hiện nhiều.Trên cơ sở thuật toán 
K-means, thuật toán K-medoids, nhóm tác giả 
so sánh kết quả thực hiện phân cụm với các chủ 
đề tin trên. Kết quả bảng dưới. Với độ phức tạp 
của các thuật toán trên, nhóm tác giả thấy thời 
Nguyễn Văn Huân và cs Tạp chí KHOA HỌC & CÔNG NGHỆ 61(12/2): 102 - 106 
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên  
106 
gian thực hiện thuật toán phụ thuộc vào độ lớn 
cơ sở dữ liệu và số cụm cần phân cụm. 
Số tài 
liệu 
(CSDL) 
Số 
cụm 
Thời gian phân cụm 
trung bình (giây) 
K-
means 
K-medoids 
K-means 
cải tiến 
250 10 9,756 9,106 8,56 
250 15 12,375 11,525 10,972 
100 10 2,518 2,218 2,118 
100 15 3,719 3,119 3,219 
150 10 4,115 4,015 3,005 
150 15 5,723 5,110 5,123 
50 10 0,957 0,907 0,857 
50 15 1,13 1,11 1,00 
KẾT LUẬN 
Tìm kiếm và phân cụm tự động các thông tin 
phù hợp và có giá trị trên Web là một chủ đề 
quan trọng và là vấn đề quan trọng của mỗi 
đơn vị, tổ chức có nhu cầu thu thập và tìm 
kiếm thông tin trên Internet. Bài báo đã đưa ra 
cải tiến thuật toán K-means trong phân cụm 
tài liệu Web. Thay vì chọn số điểm làm trọng 
tâm thì không chọn số điểm làm trọng tâm 
cho số cụm mà sẽ tăng số cụm từ 1 lên k cụm 
bằng cách đưa trung tâm cụm mới vào cụm có 
mức độ biến dạng lớn nhất và tính lại trọng 
tâm các cụm. Nhóm tác giả đã cài đặt thử 
nghiệm trên các bộ cơ sở dữ liệu, cho kết quả 
bước đầu khá khả quan. 
TÀI LIỆU THAM KHẢO 
[1]. Athena Vakali, Web data clustering Current 
research status & trends, Aristotle 
University,Greece, 2004. 
[2]. Raghu Krishnapuram, Anupam Joshi, and Liyu 
Yi, A Fuzzy Relative of the K - Medoids Algorithm 
with Application toWeb Document and Snippet 
Clustering, 2001. 
[3]. Filippo Geraci, Marco Pellegrini, Paolo Pisati, and 
Fabrizio Sebastiani, A scalable algorithm for high-
quality clustering of Web Snippets, Italy, ACM, 2006. 
[4]. Hiroyuki Kawano, Applications of Web mining- 
from Web search engine to P2P filtering, IEEE, 2004. 
[5]. Raymond and Hendrik, Web Mining Research: A 
Survey, ACM, 2000 
[6]. Hua-Jun Zeng, Qi-Cai He, Zheng Chen, Wei-Ying 
Ma, Jinwen Ma, Learning to Cluster Web Search 
Results, ACM, 2004. 
[7]. Lizhen Liu, Junjie Chen, Hantao Song, The 
research of Web Mining, IEEE, 2002 
[8]. Maria Rigou, Spiros Sirmakessis, and Giannis 
Tzimas, A Method for Personalized Clustering in Data 
Intensive Web Applications, 2006. 
[9]. Oren Zamir and Oren Etzioni, Web document 
Clustering: A Feasibility Demonstration, University of 
Washington, USA, ACM, 1998. 
[10]. Periklis Andritsos, Data Clusting Techniques, 
University Toronto,2002. 
[11]. Yitong Wang, Masaru Kitsuregawa, Evaluating 
Contents-Link Coupled Web Page Clustering for Web 
Search Results, ACM, 2002. 
[12]. Zifeng Cui, Xu , Weifeng Zhang, Junling Xu, Web 
Documents Clustering with Interest Links, IEEE, 2005.
SUMMARY 
IMPROVE THE K-MEANS AGORITHM AND APPLY TO DATA AUTOMATIC 
CLUSTERING 
Nguyen Van Huan 
1 
, Pham Viet Binh
1
, Truong Manh Ha
1
, 
Vu Xuan Nam
1
, Doan Manh Hong
2 
1 Faculty of Information Technology - Thai Nguyen University, 
2 Economics and Business Administration - Thai Nguyen Univesity 
Data automatic clustering is a complicated problem and to many research scientists, first step they expose 
some of algorithms: K-means, K-medoids,.. and achieve the result in data search and data clustering. 
However, almost there algorithms, when clustering are required to determine the number of cluster 
performance, especially with K-means algorithm or required different levels in determining the nature and 
composition are similar. In addition, this technique also requires a pre-selected as focal points, with points 
chosen randomly as focus will be to different results. Therefore, the results can be inaccurate, with the level 
of error can be very large. This article offers improved K-means algorithm in web documents clustering, 
instead choose to focal points are not selected as focal points for the number of clusters that will increase the 
number of clusters from 1 to k clusters by introducing new cluster centers with the level of Max deformation 
and recalculating focal clusters. 
Keywords: K-Means, clustering, Data mining, Web mining, K-Medoids. 
 Tel: 0987 118 623, Email: nvhuan@ictu.edu.vn