I. GIỚI THIỆU
Thuật toán K-means clustering do
MacQueen giới thiệu trong tài liệu “J. Some Methods for Classification and
Analysis of Multivariate Observations” năm 1967.
K-means Clustering là một
thuật toán dùng trong các bài toán phân loại/nhóm n đối tượng thành k nhóm dựa
trên đặc tính/thuộc tính của đối tượng (k £n nguyên, dương).
Về nguyên lý, có n đối
tượng, mỗi đối tượng có m thuộc tính, ta phân chia được các đối tượng thành k
nhóm dựa trên các thuộc tính của đối tượng bằng việc áp dụng thuật toán này.
Coi mỗi thuộc tính của đối tượng (đối
tượng có m thuộc tính) như một toạ độ của không gian m chiều và biểu diễn đối
tượng như một điểm của không gian m chiều.
ai =( xi1, xi2,
... xim) (
1)
ai (i=1..n) - đối tượng thứ i
xij (i=1..n, j=1..m) - thuộc tính thứ j của
đối tượng i
Phương thức phân loại/nhóm dữ liệu thực hiện dựa
trên khoảng cách Euclidean nhỏ nhất giữa đối tượng đến phần tử trung tâm của các nhóm.
Phần
tử trung tâm của nhóm được xác định bằng giá trị trung bình các phần tử trong
nhóm.
2.
Khoảng cách Euclidean.
ai=(xi1,
xi2,... xim) i=1..n - đối tượng thứ i cần phân phân loại
cj=(xj1, xj2,... xjm)
j=1..k - phần tử trung tâm nhóm j
Khoảng cách Euclidean từ đối tượng ai đến
phần tử trung tâm nhóm j cj được tính toán dựa trên công thức:
dji - khoảng cách Euclidean từ ai đến
cj
xis - thuộc tính thứ s của đối tượng ai
xjs - thuộc tính thứ s của phần tử trung
tâm cj
3.
Phần tử trung tâm.
k phần tử trung tâm (k
nhóm) ban đầu được chọn ngẫu nhiên, sau mỗi lần nhóm các đối tượng vào các
nhóm, phần tử trung tâm được tính toán lại.
Clusteri = {a1, a2 .... at} – Nhóm thứ
i
i=1..k, k số cluster
j= 1..m, m số thuộc tính
t - số phần tử hiện có của nhóm thứ i
xsj - thuộc tính thứ j của phần tử s s=1..t
cij - toạ độ thứ j của phần tử trung tâm nhóm i;
( 3)
II. GIỚI THIỆU VỀ THUẬT TOÁN K-MEANS.
Sơ
đồ thuật toán:
Hình
3: Sơ đồ thuật toán K-means clustering
Thuật toán k-means bao gồm các bước cơ
bản sau :
Input: Số cụm k và các trọng
tâm cụm {mj}kj=1.
Output: Các cụm C[i] (1 ≤ i ≤
k) và hàm tiêu chuẩn E đạt giá trị tối thiểu.
Begin
Bước 1:
Khởi tạo
Chọn
k trọng tâm {mj}kj=1 ban đầu trong không gian Rd (d là số chiều của
dữ liệu). Việc lựa chọn này có thể là ngẫu nhiên hoặc theo kinh nghiệm.
Bước 2: Tính toán khoảng cách
Đối với mỗi điểm Xi (1 ≤ i ≤ n), tính
toán khoảng cách của nó tới mỗi trọng
tâm mj (1 ≤ j ≤
k). Sau đó tìm trọng tâm gần nhất đối với mỗi điểm.
Bước 3: Cập nhật lại
trọng tâm
Đối với mỗi 1 ≤ j ≤ k, cập nhật trọng tâm cụm mj bằng cách xác định
trung bình cộng các vectơ đối tượng dữ
liệu.
Điều kiện dừng:
Lặp lại các bước 2 và 3 cho đến khi các trọng tâm của cụm không thay
đổi.
End.
Thuật toán k-means trên
được chứng minh là hội tụ và có độ phức tạp tính toán là:
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, 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ơn nữa, chất lượng phân cụm dữ liêuk 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 mà 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ế 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.
III.
CHƯƠNG TRÌNH DEMO.
Chương
trình gồm các Hàm chính:
·
kMeanCluster– Thể hiện một đối tượng
·
dist – Đối tượng trung tâm
Sub kMeanCluster(Data() As Variant,
numCluster As Integer)
Dim
i As Integer
Dim
j As Integer
Dim
X As Single
Dim
Y As Single
Dim
min As Single
Dim
cluster As Integer
Dim
d As Single
Dim sumXY()
Dim
isStillMoving As Boolean
isStillMoving
= True
If
totalData <= numCluster Then
Data(0, totalData) = totalData '
cluster No = total data
Centroid(1, totalData) = Data(1,
totalData) ' X
Centroid(2, totalData) = Data(2,
totalData) ' Y
Else 'calculate minimum distance to
assign the new data
min = 10 ^ 10 'big number
X = Data(1, totalData)
Y = Data(2, totalData)
For i = 1 To numCluster
d = dist(X, Y, Centroid(1, i),
Centroid(2, i))
If d < min Then
min = d
cluster = i
End If
Next i
Data(0, totalData) = cluster
Do While isStillMoving
' this loop will surely
convergent calculate new centroids
ReDim sumXY(1 To 3, 1 To numCluster) '1=X,2=Y,3=count number of data
For i = 1 To totalData
sumXY(1, Data(0, i)) = Data(1, i) +
sumXY(1, Data(0, i))
sumXY(2, Data(0, i)) = Data(2, i) +
sumXY(2, Data(0, i))
sumXY(3, Data(0, i)) = 1 + sumXY(3,
Data(0, i))
Next i
For i = 1 To numCluster
Centroid(1, i) = sumXY(1, i) /
sumXY(3, i)
Centroid(2, i) = sumXY(2, i) /
sumXY(3, i)
Next i
'assign all data to the new centroids
isStillMoving = False
For i = 1 To totalData
min = 10 ^ 10 'big number
X = Data(1, i)
Y = Data(2, i)
For j = 1 To numCluster
d = dist(X, Y, Centroid(1, j),
Centroid(2, j))
If d < min Then
min = d
cluster = j
End If
Next j
If Data(0, i) <> cluster Then
Data(0, i) = cluster
isStillMoving = True
End If
Next i
Loop
End
If
End Sub
Function dist(X1 As Single, Y1 As Single, X2 As
Single, Y2 As Single) As Single
' calculate Euclidean distance
dist = Sqr((Y2 - Y1) ^ 2 + (X2 - X1) ^ 2)
End Function
Private
Function min2(num1, num2)
' return minimum value between two numbers
If num1 < num2 Then
min2 = num1
Else
min2 = num2
End If
End Function
>> DOWNLOAD CODE TẠI ĐÂY
KẾ QUẢ CHƯƠNG TRÌNH
Dữ liệu vào
Data(1, 1) = 1
Data(2, 1) = 1
Data(1, 2) = 5
Data(2, 2) = 2
Data(1, 3) = 8
Data(2, 3) = 5
Data(1, 4) = 7
Data(2, 4) = 3
Data(1, 5) = 5
Data(2, 5) = 1
Kết quả chạy
với k= 3
Kết quả chạy
với k= 2
Giống
như các thuật toán khác, k- mean cũng có một số hạn chế nhất định:
-
Việc khởi tạo phần tử trung tâm của nhóm
ban đầu ảnh hưởng đến sự phân chia đối tượng vào nhóm trong trường hợp dữ liệu
không lớn.
-
Số nhóm k luôn phải được xác định trước.
-
Không xác định được rõ ràng vùng của
nhóm, cùng 1 đối tượng, nó có thể được đưa vào nhóm này hoặc nhóm khác khi dung
lượng dữ liệu thay đổi.
-
Điều kiện khởi tạo có ảnh hưởng lớn đến
kết quả. Điều kiện khởi tạo khác nhau có thể cho ra kết quả phân vùng nhóm khác
nhau.
-
Không xác định được mức độ ảnh hưởng của
thuộc tính đến quá trình tạo nhóm.
Như vậy, với dữ liệu nhỏ, thuật toán có thể có những
hạn chế. Để khắc phục những hạn chế này, nên sử dụng thuật toán kmean trong trường
hợp dữ liệu lớn.
Về vấn đề hạn chế phân nhóm, có thể dùng phương pháp
xác định trung tuyến thay vì xác định mean.
Một
quan niệm cho rằng k-means không thể dùng cho dữ liệu có kiểu là định lượng.
Điều này không đúng, k-means có thể được dùng giải quyết các bài toán dữ liệu
đa biến, thậm chí cho các bài toán có nhiều dạng dữ liệu. Chìa khoá cho việc
giải bài toán này của k-means là sử dụng ma trận khoảng cách.
TÀI LIỆU THAM
KHẢO
1.
Bài
giảng của thầy Nguyễn Bá Tường
2.
k-means
clustering http://en.wikipedia.org/wiki/K-means_clustering
3.
How
the K-Mean Clustering algorithm works? http://people.revoledu.com/kardi/tutorial/kMean/Algorithm.htm
4.
Kiri
Wagstaff, Claire Cardie; Constrained k-means clustering with Background
Knowledge http://www.cse.msu.edu/~cse802/notes/ConstrainedKmeans.pdf
[TxT]