Cải tiến thuật toán phân cụm mờ dựa trên độ đo trọng số entropy và chỉ số Calinski-Harabasz

 TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ LẠT Tập 8, Số 2, 2018 13–23 
13 
CẢI TIẾN THUẬT TOÁN PHÂN CỤM MỜ DỰA TRÊN ĐỘ ĐO TRỌNG SỐ 
ENTROPY VÀ CHỈ SỐ CALINSKI-HARABASZ 
Nguyễn Như Đồnga*, Phan Thành Huấnb 
aPhòng Đào tạo, Trường Cao đẳng Kỹ nghệ II, TP. Hồ Chí Minh, Việt Nam 
bBộ môn Tin học, Trường Đại học Khoa học Xã hội và Nhân văn, Đại học Quốc gia TP. Hồ Chí Minh, 
TP. Hồ Chí Minh, Việt Nam 
*Tác giả liên hệ: Email: dongnhunguyen@gmail.com 
Lịch sử bài báo 
Nhận ngày 19 tháng 01 năm 2018 
Chỉnh sửa ngày 22 tháng 03 năm 2018 | Chấp nhận đăng ngày 14 tháng 04 năm 2018 
Tóm tắt 
Phân cụm là kỹ thuật quan trọng trong khai thác dữ liệu và được ứng dụng rộng rãi trong các lĩnh vực 
như nhận dạng mẫu, thị giác máy tính và điều khiển mờ. Trong bài viết này, chúng tôi trình bày thuật 
toán cải tiến phân cụm mờ dựa vào sự kết hợp thuật toán phân cụm mờ dựa trên độ đo trọng số Entropy 
và chỉ số Calinski-Harabasz. Ưu điểm của phương pháp này là không những phân chia cụm hiệu quả, có 
độ chính xác cao mà còn có khả năng đo lường cụm, đánh giá cụm nhằm tìm ra được số cụm tối ưu đủ 
đáp ứng cho các nhu cầu thực tiễn. Sau cùng, chúng tôi trình bày kết quả thực nghiệm trên dữ liệu thực, 
cho thấy thuật toán cải tiến phân cụm hiệu quả và chính xác hơn. 
Từ khóa: Chỉ số Calinski-Harabasz; Phân cụm mờ; Trọng số Entropy. 
Mã số định danh bài báo:  
Loại bài báo: Bài báo nghiên cứu gốc có bình duyệt 
Bản quyền © 2018 (Các) Tác giả. 
Cấp phép: Bài báo này được cấp phép theo CC BY-NC-ND 4.0 
TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ LẠT [ĐẶC SAN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG] 
14 
AN IMPROVED FUZZY K-MEANS CLUSTERING ALGORITHM BASED 
ON WEIGHT ENTROPY MEASUREMENT 
AND CALINSKI-HARABASZ INDEX 
Nguyen Nhu Donga*, Phan Thanh Huanb 
aTraining Department, Hochiminh Vocational College of Technology, Hochiminh City, Vietnam 
bThe Division of Information Technology, University of Social Sciences and Humanities, VNU Hochiminh, 
Hochiminh City, Vietnam 
*Corresponding author: Email: dongnhunguyen71@gmail.com 
Article history 
Received: January 19th, 2018 
Received in revised form: March 22nd, 2018 | Accepted: April 14th, 2018 
Abstract 
Clustering plays an important role in data mining and is applied widely in fields of pattern recognition, 
computer vision, and fuzzy control. In this paper, we proposed an improved clustering algorithm 
combined of both fuzzy k-means using weight Entropy and Calinski-harabasz index. The advantage of this 
method is that it does not only create efficient clustering but also has the ability to measure clusters and 
rate clusters to find the optimal number of clusters for practical needs. Finally, we presented 
experimental results on real-life datasets, which showed that the improved algorithm has the accuracy 
and efficiency of the existing algorithms. 
Keywords: Calinski-Harabasz Index; Fuzzy K-means; Weight entropy. 
Article identifier:  
Article type: (peer-reviewed) Full-length research article 
Copyright © 2018 The author(s). 
Licensing: This article is licensed under a CC BY-NC-ND 4.0 
 Nguyễn Như Đồng và Phan Thành Huấn 
15 
1. GIỚI THIỆU 
Mục đích chính của phân cụm dữ liệu nhằm khám phá cấu trúc của mẫu dữ liệu để phân chia 
thành các nhóm dữ liệu từ tập dữ liệu lớn. Từ đó, người dùng có thể phân tích và nghiên cứu theo 
từng cụm dữ liệu, nhằm khám phá và tìm kiếm các thông tin tiềm ẩn, hữu ích hỗ trợ cho việc ra 
quyết định. Phân cụm dữ liệu là quá trình phân chia một tập dữ liệu ban đầu thành các cụm dữ liệu 
sao cho các phần tử trong một cụm "tương tự" với nhau và các phần tử trong các cụm khác nhau sẽ 
"không tương tự" với nhau. Độ tương tự được tính dựa trên giá trị các thuộc tính mô tả đối tượng. 
Hình 1. Mô phỏng sự phân cụm dữ liệu 
Hiện nay, kỹ thuật phân cụm có rất nhiều hướng tiếp cận. Trong bài viết này, nhóm tác giả 
tập trung cải tiến kỹ thuật phân cụm theo hướng tiếp cận phân hoạch. Ý tưởng chính của kỹ thuật 
này là phân một tập dữ liệu có n phần tử cho trước thành k nhóm dữ liệu sao cho mỗi phần tử dữ 
liệu chỉ thuộc về một nhóm dữ liệu và mỗi nhóm dữ liệu có tối thiểu ít nhất một phần tử dữ liệu. 
Các thuật toán phân hoạch có độ phức tạp rất lớn khi xác định nghiệm tối ưu toàn cục cho vấn đề 
phân cụm dữ liệu, vì nó phải tìm kiếm tất cả các cách phân hoạch có thể được. Chính vì vậy, trên 
thực tế người ta thường đi tìm giải pháp tối ưu cục bộ cho vấn đề này bằng cách sử dụng một hàm 
tiêu chuẩn để đánh giá chất lượng của các cụm cũng như để hướng dẫn cho quá trình tìm kiếm phân 
hoạch dữ liệu. Với chiến lược này, thông thường người ta bắt đầu khởi tạo một phân hoạch ban đầu 
cho tập dữ liệu theo phép ngẫu nhiên hoặc theo heuristic và liên tục tinh chỉnh nó cho đến khi thu 
được một phân hoạch mong muốn, thoả mãn các điều kiện ràng buộc cho trước. Các thuật toán 
phân cụm phân hoạch cố gắng cải tiến tiêu chuẩn phân cụm bằng cách tính các giá trị đo độ tương 
tự giữa các đối tượng dữ liệu và sắp xếp các giá trị này, sau đó thuật toán lựa chọn một giá trị trong 
dãy sắp xếp sao cho hàm tiêu chuẩn đạt giá trị tối thiểu. Như vậy, ý tưởng chính của thuật toán phân 
cụm phân hoạch tối ưu cục bộ là sử dụng chiến lược ăn tham để tìm kiếm nghiệm. 
Trong phạm vi bài báo, nhóm tác giả trình bày cải tiến thuật toán phân cụm mờ kết hợp giữa 
phương pháp phân cụm mờ sử dụng trọng số Entropy do Jing, Ng, và Huang (2007) cũng như Li và 
Chen (2008, 2010) và kỹ thuật đánh giá cụm theo chỉ số Calinski-Harabasz. Phần 2 trình bày các 
khái niệm cơ bản về phân cụm rõ và phân cụm mờ. Phần 3 đề xuất mô hình phân cụm mờ dựa trên 
kết hợp giữa phân cụm mờ sử dụng trọng số Entropy và đánh giá cụm theo chỉ số Calinski-
Harabasz. Kết quả thực nghiệm được trình bày trong Phần 4 và kết luận ở Phần 5. 
2. CÁC VẤN ĐỀ LIÊN QUAN 
2.1. Phân cụm rõ: Thuật toán K-Means 
Cho một tập dữ liệu X={x1,x2,,xn}, với xi Rd, gồm n đối tượng dữ liệu d chiều. Phân tách 
tập dữ liệu thành k cụm: C1,C2,,Ck rời nhau thỏa mãn điều kiện sau: k..i,Ci 1   ;
TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ LẠT [ĐẶC SAN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG] 
16 
ji,CC ji    ; và 
1
k
i
i
C X
 U
. Trong đó: k là số cụm sẽ phân thành, cho trước, và nguyên dương; Ci 
là véc-tơ tâm cụm, dùng đề chỉ cụm thứ i. 
K-Means là thuật toán rất quan trọng và được sử dụng phổ biến trong kỹ thuật phân cụm. Ý 
tưởng chính của thuật toán K-Means là tìm cách phân nhóm các đối tượng đã cho vào k cụm (k là số 
các cụm được xác đinh trước, k nguyên dương) sao cho tổng bình phương khoảng cách giữa các đối 
tượng đến tâm nhóm là nhỏ nhất. Thuật toán có các bước như sau: 
 Đầu vào: Cơ sở dữ liệu gồm n đối tượng d chiều và hằng số k; 
 Đầu ra: Các cụm Ci (i=1..k) sao cho hàm tiêu chuẩn F đạt giá trị tối thiểu; 
 Bước 1: Chọn k đối tượng mj (j=1...k) là trọng tâm ban đầu của k cụm (ngẫu nhiên hoặc 
theo kinh nghiệm); 
 Bước 2: Đối với mỗi đối tượng Xi (1 ≤ i ≤ n), tính toán khoảng cách từ nó tới mỗi trọng 
tâm mj với j=1k. Sau đó tìm trọng tâm gần nhất đối với mỗi đối tượng; 
 Bước 3: Đối với mỗi j=1k, cập nhật trọng tâm cụm mj bằng cách tính trung bình cộng 
của các vector đối tượng dữ liệu; 
 Bước 4: Lặp các Bước 2 và Bước 3 cho đến khi các trọng tâm của cụm không thay đổi. 
Thuật toán K-Means được chứng minh là hội tụ và có độ phức tạp tính toán là:
)T)dkn(( flop   . Trong đó: n là số đối tượng dữ liệu; k là số cụm dữ liệu; d là số chiều; τ là 
số vòng lặp; và Tflop là thời gian để thực hiện một phép tính cơ sở như phép tính nhân, chia Như 
vậy, do K-Means phân tích phân cụm đơn giản nên có thể áp dụng đối với tập dữ liệu lớn. Tuy 
nhiên, nhược điểm của K-Means là chỉ áp dụng với dữ liệu có thuộc tính số và khám phá ra các cụm 
có dạng hình cầu, K-Means còn rất nhạy cảm với nhiễu và các phần tử ngoại lai trong dữ liệu. Hình 
2 mô phỏng về một số hình dạng cụm dữ liệu khám phá được bởi thuật toán K-Means. 
Hình 2. Mô phỏng kết quả phân cụm bằng thuật toán K-Means 
 Nguyễn Như Đồng và Phan Thành Huấn 
17 
Hơn nữa, chất lượng phân cụm của thuật toán K-Means phụ thuộc nhiều vào các tham số 
đầu vào như số cụm k và k trọng tâm khởi tạo ban đầu. Trong trường hợp các trọng tâm khởi tạo 
ban đầu quá lệch so với các trọng tâm cụm tự nhiên thì kết quả phân cụm của K-Means là rất thấp, 
nghĩa là các cụm dữ liệu được khám phá rất lệch so với các cụm trong thực tế. Trên thực tế, người 
ta chưa có một giải pháp tối ưu nào để chọn các tham số đầu vào. Giải pháp thường được sử dụng 
nhất là thử nghiệm với các giá trị đầu vào k khác nhau rồi sau đó chọn giải pháp tốt nhất. 
2.2. Phân cụm mờ: Thuật toán K-Means mờ 
Các thực thể trong thế giới thực hay các khái niệm trừu tượng thường là các đối tượng phức 
tạp. Các đối tượng này chứa một tập nhất định các thông tin về đối tượng và các hành vi của chính 
đối tượng đó. Thông tin về đối tượng được gọi là thuộc tính đối tượng và được xác định bởi giá trị 
cụ thể. Chúng ta có thể thấy rằng, tùy thuộc vào mục tiêu phân cụm mà tính chất quan trọng của 
mỗi thuộc tính là khác nhau. Do đó, chúng ta cần đánh giá tính quan trọng của từng thuộc tính trong 
đối tượng để thu được kết quả phân cụm tốt hơn. Cụ thể là cung cấp một giá trị trọng số ω trong độ 
đo F để thể hiện mức độ quan trọng của thuộc tính. Phương pháp này được gọi là phân cụm mờ, do 
Friguiand và Nasraoui (2004) cũng như Chan, Ching, Ng, và Huang (2004) đề xuất. Độ đo F được 
tính như công thức (1). 

k
l
n
j
m
i
lijililj )cx()C,W,T(F
1 1 1
2 (1) 
Trong đó: 
m
i
lililj
k
l
lj )kl(,,};,{),nj(,
11
11011011  ; n là số phần tử trong cụm; 
m là số thuộc tính của phần tử; k là số cụm; và cli là phần tử trung tâm của cụm (1 i n). 
Thuật toán K-Mean mờ được mô tả như sau: 
 Đầu vào: Cơ sở dữ liệu gồm n đối tượng và hằng số cụm k; 
 Đầu ra: Các cụm Ci (i=1k) sao cho hàm tiêu chuẩn F đạt giá trị tối thiểu; 
 Bước 1: Chọn k đối tượng mj (j=1k) là trọng tâm ban đầu của k cụm (ngẫu nhiên 
hoặc theo kinh nghiệm); Khởi tạo trọng số ωli = 1/m (1 i n; 1 l m); 
 Bước 2: Tính toán τ theo công thức (2); 
 
 
m
i
m
i
jizizijilili
m
i
m
i
jizizijilili
lj
)xc()xc(,
)xc()xc(,
1 1
22
1 1
22
0
1


 (2) 
 Bước 3: Tính hàm F theo công thức (3); 

k
l
n
j
m
i
lijililj )cx()C,W,T(F
1 1 1
2 (3) 
TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ LẠT [ĐẶC SAN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG] 
18 
 Bước 4: Cập nhật lại trọng tâm C theo công thức (4); 


n
j
lj
n
j
jilj
li
x
c
1
1


 (4) 
 Bước 5: Cập nhật lại ω theo công thức (5); 
)(
m
i
n
j
jtltlj
n
j
jililj
li
)xc(
)xc(
1
1
1
1
2
1
2






 (5) 
 Bước 6: Lặp lại các bước từ Bước 2 đến Bước 5 cho đến khi hàm F là nhỏ nhất. 
Dựa vào công thức tính ω như trên, ta nhận thấy trong một số trường hợp giá trị ω có thể 
không tính toán được khi mẫu số bằng 0. Để giải quyết vấn đề này nhóm tác giả Huang, Ng, Rong, 
và Li (2005) đề xuất thuật toán “An Entropy weighting K-Means algorithm (EWKM)” nhằm khắc 
phục hạn chế khi tính toán ω bằng cách xây dựng hàm F cải tiến như công thức (6). 
 
k
l
m
i
lili
n
j
m
i
lijililj log)cx()C,W,T(F
1 11 1
2   (6) 
Mặc dù phương pháp EWKM đã giải quyết được vấn đề mẫu số bằng 0 khi tính toán giá trị 
ω nhưng nó vẫn còn hạn chế đó là chưa tách được các lớp một cách rõ rệt. Điều này dẫn đến kết quả 
là phần tử giữa các cụm có thể nằm gần nhau gây nên sự chồng chéo và không chính xác. 
3. THUẬT TOÁN ĐỀ XUẤT 
3.1. Mô hình kết hợp 
Các thuật toán K-Means và K-Means mờ được khảo sát cho đến thời điểm này là một bước 
đột phá trong lĩnh vực phân cụm dữ liệu nhưng vẫn còn tồn tại một số khuyết điểm. Để khắc phục 
hạn chế của K-Means mờ, nhiều thuật toán cải tiến đã lần lượt ra đời và một trong những thuật toán 
cải tiến gần đây nhất được biết đến đó thuật toán phân cụm K-Means mờ sử dụng độ đo trọng số 
Entropy (Fuzzy K-Means algorithm for clustering using Entropy - FKMUE) của Li và Chen (2008, 
2010). Mục tiêu của thuật toán này là điều chỉnh hàm chí phí F trong công thức (6) bằng cách thêm 
vào một biến liên quan đến khoảng cách trung bình giữa các phần tử và khoảng cách trung bình 
giữa các cụm với nhau. Điều này không những giúp cho các mẫu trong cùng một cụm gom lại gần 
nhau mà còn hướng đến việc phân chia các cụm cách xa nhau nhất. 
Trong phần này sẽ trình bày cải tiến thuật toán phân cụm dựa vào sự kết hợp thuật toán K-
Means mờ sử dụng độ đo trọng số Entropy và phương pháp đánh giá cụm theo chỉ số Calinski-
Harabasz. Ưu điểm của phương pháp này không những phân chia cụm hiệu quả, có độ chính xác 
cao mà còn có khả năng đo lường cụm, đánh giá cụm nhằm tìm ra được số cụm tối ưu đủ đáp ứng 
cho các nhu cầu thực tiễn. Thuật toán cải tiến được chia thành hai giai đoạn như sau (Hình 3): 
 Nguyễn Như Đồng và Phan Thành Huấn 
19 
 Giai đoạn 1: Sử dụng thuật toán FKMUE để phân cụm tập dữ liệu đầu vào; 
 Giai đoạn 2: Sau khi phân hoạch dữ liệu thành từng cụm bằng thuật toán FKMUE, sử 
dụng độ đo Calinski-Harabasz để đánh giá tính hiệu quả ứng với số cụm vừa tìm được. 
Quá trình trên sẽ được lặp đi lặp lại cho các số cụm khác nhau và số cụm có giá trị SCH 
lớn nhất được chọn làm kết quả sau cùng. 
Hình 3. Mô hình kết hợp giữa phương pháp FKMUE và Calinski-Harabasz 
3.2. Thuật toán đề xuất 
Hầu hết các thuật toán phân cụm mờ cho đến thời điểm này thường mang tính chất ngẫu 
nhiên khi chọn tâm ban đầu cho các cụm. Vì vậy trong một số trường hợp có thể xảy ra hiện tượng 
tâm của các cụm được chọn nằm cạnh nhau hoặc có tính chất tương tự nhau. Điều này dẫn đến kết 
quả là chi phí lặp lại cho số lần phân chia cụm là rất lớn làm giảm hiệu năng của hệ thống. Để giải 
quyết vấn đề này, nhóm tác giả đã làm một số điều chỉnh cho việc chọn tâm cho k cụm ban đầu 
bằng cách tính toán khoảng cách sao cho tâm của cụm tiếp theo có khoảng cách xa nhất so với tâm 
của các cụm đã chọn trước đó. Ngoài ra, do dữ liệu trong thực tế thường không đồng nhất và hay bị 
TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ LẠT [ĐẶC SAN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG] 
20 
dư thừa nên thường dẫn đến việc phân cụm có độ chính xác không cao. Để loại bỏ những thuộc tính 
dư thừa, không tham gia vào quá trình phân cụm cũng như đảm bảo dữ liệu luôn được nhất quán, 
chúng tôi tiến hành chuẩn hóa dữ liệu về gốc tọa độ theo công thức (7) như sau: 
)mi(
xminxmax
xminx
x
t
ti
t
ti
t
ti
orginal
ji 
 1 (7) 
Thuật toán đề xuất có các bước như sau: 
 Đầu vào: Cơ sở dữ liệu gồm n đối tượng và các giá trị đầu vào m, l, maxValue = 0, k, γ, 
và số lần lặp tối đa s và trọng số ban đầu của các thuộc tính 
mli
1  ; 
 Đầu ra: Số cụm có giá trị SCH lớn nhất; 
 Bước 1: Chuẩn hóa thuộc tính của các mẫu về gốc tọa độ theo công thức (7); 
 Bước 2: Đưa tất cả các mẫu sau khi được chuẩn hóa vào tập H và gán tập C (chứa tâm 
của mỗi cụm); 
 Bước 3: Chọn ngẫu nhiên một mẫu bất kỳ trong H và đưa vào C, đồng thời loại bỏ mẫu 
này ra khỏi H. Mẫu này được xem là tâm của cụm đầu tiên; 
 Bước 4: Tìm một mẫu tiếp theo trong H đặt vào C sao cho khoảng cách từ mẫu này đến 
tất cả các mẫu trong C là xa nhất; 
 Bước 5: Nếu số tâm trong C bằng với k thì chuyển sang Bước 7, ngược lại quay sang 
Bước 4; 
 Bước 6: Tính giá trị T theo công thức (8) và giá trị F(T,W,C) theo công thức (9); 

m
i
i
n
j
ljlj )c,x(d
n
11
1
 (8) 
 


k
l
m
i
lili
k
l
m
i
ili
n
j
m
i
lijililj
log
)xc(
)cx(
)C,W,T(F
1 11
1
2
1 1
2

 
 (9) 
 Bước 7: Cập nhật C theo công thức (10) và W theo công thức (11); 

k
l
n
j
ljlj )c,x(d
n
m
1 1
 (10) 





 lt
m
i
lt
lt exp
exp
1
1 (11) 
 Nguyễn Như Đồng và Phan Thành Huấn 
21 
Trong đó 
 
n
j
jtltljm
i
ili
lt )xc(
)xc( 1
2
1
2
1
 
 Bước 8: Lặp lại Bước 6 và Bước 7 cho đến khi F không thể nhỏ hơn được nữa hoặc số 
lần lặp bằng s, khi đó chuyển sang Bước 10; 
 Bước 9: Đánh giá số cụm vừa tìm theo công thức (12) để được giá trị SCH; 
 

il Cx
lpip
r
p
k
l
T
ii
k
l
l
CH
xx
)xx)(xx(n
k
kn
S
11
1
1
 (12) 
 Bước 10: So sánh giá trị SCH với maxValue. Nếu SCH lớn hơn maxValue thì gán 
maxValue = SCH; 
 Bước 11: Tăng giá trị l = l +1. Nếu l ≤ k thì chuyển sang Bước 3. Ngược lại số cụm 
được chọn l là số cụm có giá trị SCH lớn nhất. 
Trong phần này, nhóm tác giả đã trình bày một phương pháp mới cho việc phân cụm bằng 
cách kết hợp thuật toán FKMUE và độ đo Calinski-Harabasz. So với các thuật toán K-Means mờ 
truyền thống tính chất mờ thường đi kèm với cả đối tượng vì vậy không phản ánh rõ mức độ quan 
trọng của thuộc tính khi xem xét gom cụm đối tượng. Trái lại thuật toán K-Means mờ với trọng số 
Entropy chú trọng đến tính chất mờ trên từng thuộc tính, cho phép người dùng điều chỉnh để tăng 
hệ số mờ với các thuộc tính quan trọng và giảm giá trị với các thuộc tính không cần thiết. Thêm vào 
đó sự điều chỉnh của hàm F để làm gia tăng khoảng cách giữa các cụm và thu hẹp giữa các mẫu 
trong cụm đã góp phần rất lớn vào mức độ chính xác, giúp cho các cụm rõ ràng và có nhiều ý nghĩa 
hơn. Cuối cùng tính hiệu quả của phương pháp còn được đo lường qua tiêu chuẩn đánh giá cụm 
bằng phương pháp Calinski-Harabasz, giúp cho kết quả phân cụm được chính xác, có ý nghĩa và tin 
cậy hơn. Với những ưu điểm vừa được trình bày ở trên, có thể thấy rằng phương pháp đề xuất của 
chúng tôi có đủ tính khả thi cho bài toán phân cụm dữ liệu, đáp ứng nhu cầu ứng dụng thực tiễn 
trong nhiều lĩnh vực khác nhau. 
4. THỰC NGHIỆM 
Trong phần này, nhóm tác giả sử dụng bộ dữ liệu Iris từ kho dữ liệu học máy của Đại học 
California (Lichman, 2013). Bộ dữ liệu được rút gọn gồm năm thuộc tính, trong đó bốn thuộc tính 
kiểu số bao gồm: Chiều dài đài hoa; Chiều rộng đài hoa; Chiều dài cánh hoa; và Chiều rộng cánh 
hoa. Một thuộc tính còn lại là tên của loài hoa Iris (Iris Setosa; Iris Versicolour; Iris Virginica). Tỷ 
lệ phân chia cho mỗi loài trong ba loài Iris là 33.3%. 
Bảng 1. Mô tả dữ liệu loài hoa Iris 
Đặc trưng Giá trị nhỏ nhất Giá trị lớn nhất Giá trị trung bình 
Chiều dài đài hoa 4.3 7.9 5.84 
Chiều rộng đài hoa 2.0 4.4 3.05 
Chiều dài cánh hoa 1.0 6.9 3.76 
Chiều rộng cánh hoa 0.1 2.5 1.20 
TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ LẠT [ĐẶC SAN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG] 
22 
Để đánh giá độ chính xác của thuật toán phân cụm, tỷ lệ lỗi được tính như công thức (13). 
Tỷ lệ lỗi càng nhỏ, thuật toán có độ chính xác càng cao, có tính phù hợp tốt. 
Tỷ lệ lỗi = (số mẫu gom cụm sai/ Tổng số mẫu kiểm tra) x 100% (13) 
Bảng 2. Tỷ lệ lỗi 
Trường hợp 
ω 
Số mẫu Số mẫu sai Tỷ lệ lỗi (%) 
Thuộc tính 1 Thuộc tính 2 Thuộc tính 3 Thuộc tính 4 
1 0.40 0.40 0.10 0.10 150 82 55.0 
2 0.10 0.10 0.40 0.40 150 5 3.0 
3 0.10 0.40 0.40 0.10 150 16 10.6 
4 0.40 0.10 0.10 0.40 150 12 8.0 
5 0.25 0.25 0.25 0.25 150 7 4.6 
Từ kết quả thống kê tỷ lệ lỗi trong Bảng 2 ta thấy quá trình phân cụm tốt nhất khi ω = {0.1, 
0.1, 0.4, 0.4} với tỷ lệ chính xác là 97% và quá trình phân cụm xấu nhất khi ω = {0.4, 0.4, 0.1, 0.1} 
với tỷ lệ chính xác là 45%. Điều này cho thấy trọng số của các thuộc tính đóng góp rất lớn vào tính 
chính xác của quá trình phân cụm. Ngoài ra với tỷ lệ phân cụm chính xác lên đến 97% nếu chọn các 
thuộc tính phù hợp cho chúng ta kết luận rằng phương pháp phân cụm mờ với trọng số Entropy cải 
tiến là phương pháp phân cụm chính xác, hiệu quả, mang lại hiệu quả khi áp dụng cho các bài toán 
ứng dụng thực tiễn. 
Một trong những khuyết điểm của các bài toán phân cụm đó là việc chọn số cụm đều dựa 
vào kinh nghiệm của người sử dụng. Nó không có cơ sở để đánh giá việc chọn số cụm nào là tối ưu. 
Có thể nói, phân cụm dữ liệu là một ví dụ của phương pháp học không giám sát, vì không đòi hỏi 
phải định nghĩa trước các mẫu dữ liệu huấn luyện. Vì thế có thể coi phân cụm dữ liệu là một cách 
học bằng quan sát (learning by observation). Trong phương pháp này ta không thể biết kết quả các 
cụm thu được sẽ thế nào khi bắt đầu quá trình. Vì vậy, thông thường cần có một chuyên gia để đánh 
giá các cụm thu được. Trong bài viết này, nhóm tác giả sử dụng phương pháp đánh giá theo độc đo 
Calinski-Harabasz. Kết quả đầu ra của quá trình phân cụm với trọng số Entropy cải tiến sẽ là đầu 
vào cho phương pháp đánh giá cụm Calinski-Harabasz. Quá trình trên sẽ được thực hiện với việc 
chọn nhiều số cụm khác nhau, sau đó kết quả đầu ra của mỗi lần phân cụm sẽ được đánh giá để 
chọn ra cụm tối ưu nhất như trong Bảng 3. Kết quả cho thấy với bộ dữ liệu Iris, số cụm k =3 là tối 
ưu nhất vì có tỷ lệ là 1.1438. 
Bảng 3. Kết quả đánh giá cụm theo phương pháp Calinski-Harabasz 
STT Số cụm Tỷ lệ đánh giá 
1 3 1.1438 
2 4 0.8229 
3 5 0.7417 
4 6 0.7221 
5 7 0.6879 
 Nguyễn Như Đồng và Phan Thành Huấn 
23 
5. KẾT LUẬN 
Trong bài viết này, nhóm tác giả đã trình bày cải tiến thuật toán phân cụm mờ bằng cách kết 
hợp phương pháp phân cụm K-Means mờ với độ đo trọng số Entropy và đánh giá cụm theo chỉ số 
Calinski-Harabasz. Các kết quả thực nghiệm cho thấy việc chọn hệ số phù hợp phương pháp phân 
cụm mới với trọng số Entropy là phương pháp hiệu quả có độ chính xác cao. Ngoài ra, để nâng cao 
độ tin cậy cho hệ thống phân cụm, chúng tôi đã sử dụng phương pháp đánh giá cụm theo chỉ số 
Calinski-Harabasz như là thước đo tính chính xác cho đầu ra khi chọn số cụm. Trong tương lai, 
nhóm tác giả cố gắng nghiên cứu thực nghiệm trên nhiều bộ dữ liệu khác nhau và đưa cải tiến trên 
vào ứng dụng thực tế. 
TÀI LIỆU THAM KHẢO 
Chan, Y., Ching, W., Ng, M. K., & Huang, J. Z. (2004). An optimization algorithm for clustering 
using weighted dissimilarity measures. Pattern Recognition, 37(5), 943-952. 
Friguiand, H., & Nasraoui, O. (2004). Unsupervised learning of prototypes and attribute weights. 
Pattern Recognition, 37(3), 567-581. 
Hoàng, X. H., & Nguyễn, T. X. H. (2006). Mở rộng thuật toán gom cụm K-means cho dữ liệu hỗn 
hợp. Tạp chí Tin học và Điều khiển học, 22(3), 267-274. 
Huang, J. Z., Ng, M. K., Rong, H., & Li, Z. (2005). Automated variable weighting in K-Means type 
clustering. IEEE Transactions on Pattern Analysis, 27(5), 657-668. 
Jing, L., Ng, M. K., & Huang, J. Z. (2007). An entropy weighting K-Means algorithm for subspace 
clustering of high dimensional sparse data. IEEE Transactions on Knowledge and Data 
Engineering, 19(8), 1026-1041. 
Li, T., & Chen, Y. (2008). An improved K-means algorithm for clustering using Entropy weighting 
measures. Paper presented at The 7th World Congress on Intelligent Control and 
Automation, China. 
Li, T., & Chen, Y. (2010). Fuzzy K-Means incremental clustering based on K-Center and vector 
quantization. Journal of Computer, 5(11), 1670-1677. 
Lichman, M. (2013). UCI machine learning repository. California, USA: University of California. 
Retrieved from