Toán học cho khoa học máy tính Ứng dụng logic mờ trong phân cụm dữ liệu
ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
BÀI THU HOẠCH MÔN
TOÁN HỌC CHO KHOA HỌC MÁY TÍNH
ĐỀ TÀI: ỨNG DỤNG LOGIC MỜ TRONG
PHÂN CỤM DỮ LIỆU
GVHD : PGS. TS. Nguyễn Văn Nhơn
SVTH : Bùi Lê Thuận
MSSV : CH1301062
Lớp : Cao học khóa 8
Tháng 01/2014
CH1301062 Trang 1
Toán học cho khoa học máy tính Ứng dụng logic mờ trong phân cụm dữ liệu
NHẬN XÉT CỦA GIẢNG VIÊN


cốt lõi trong khai thác dữ liệu.
Với sự ra đời và phát triển của lý thuyết tập mờ, ngành công nghệ thông tin đã
có cái nhìn gần với thực tiễn hơn, các công cụ của logic mờ cho phép xử lý những
thông tin không đầy đủ, không chính xác. Do đó, việc sử dụng logic mờ trong việc
phân vùng dữ liệu sẽ mềm dẻo, linh hoạt hơn rất nhiều. Nó cho phép một lượng dữ
liệu có thể thuộc vào một hoặc nhiều phân vùng khác nhau tùy vào mức độ hàm thuộc.
Như vậy có thể nói, sự ra đời của lý thuyết tập mờ đã mở ra một nhánh quan trọng
trong việc biểu diễn tri thức và ý nghĩ của con người.
Nội dung của bài thu hoạch này tập trung nghiên cứu tìm hiểu về logic mờ,
quan hệ mờ và thuật toán Fuzzy C-Means, thuật toán này sử dụng logic mờ để gom
cụm dữ liệu. Bên cạnh đó, thuật toán gom cụm rõ K-Means cũng sẽ được trình bày để
làm rõ sự khác nhau giữa phân cụm mờ và phân cụm rõ.
CH1301062 Trang 4
Toán học cho khoa học máy tính Ứng dụng logic mờ trong phân cụm dữ liệu
Em xin gửi lời cám ơn sâu sắc đến PGS. TS. Nguyễn Văn Nhơn đã tận tình
giảng dạy, truyền đạt kiến thức, giúp em hiểu hơn về ứng dụng của toán học trong
máy tính, đặc biệt là logic mờ. Đối với em, đây là kiến thức rất hay và bổ ích, tạo cho
em định hướng để thực hiện bài thu hoạch này. Tuy nhiên do thời gian nghiên cứu có
hạn nên bài thu hoạch này không thể tránh khỏi những thiếu sót nhất định, em rất
mong nhận được sự góp ý của Thầy để có thể hoàn thiện bài thu hoạch một cách tốt
nhất.
CH1301062 Trang 5
Toán học cho khoa học máy tính Ứng dụng logic mờ trong phân cụm dữ liệu
CHƯƠNG II : TẬP MỜ
2.1 Đặt vấn đề
Xét tập X là tập hợp các sinh viên của một trường đại học.
A là tập hợp các sinh viên của lớp CLASS. Như vậy với một sinh viên bất kỳ
của trường thì có thể khẳng định sinh viên đó có thuộc A hay không. Ta thấy mỗi tập
hợp có thể đặt tương ứng hàm một hàm đặc trưng:
Tuy nhiên trong cuộc sống người ta vẫn dùng những khái niệm mặc dù không

Cho X là tập hợp, A, B là hai tập mờ trong X và có các hàm thuộc lần luợt là
µA , µB. Hợp của hai tập mờ A và B trong X, ký hiệu A∪B, là một tập mờ có hàm
thuộc µ A∪B xác định như sau:
µA∪B (x) ) = max(µ A (x), µ B (x)) ∀x∈X
c. Tích đại số của hai tập mờ
Cho X là tập hợp, A, B là hai tập mờ trong X và có các hàm thuộc lần lượt là µ
A (x), µ B (x). Tích đại số của hai tập mờ A và B trong X, ký hiệu A.B là một tập mờ
có hàm thuộc được xác định như sau:
µA.B (x) = µA (x).µB (x) ∀x∈X
d. Tổng đại số của hai tập mờ
Cho X là tập hợp, A, B là hai tập mờ trong X và có các hàm thuộc lần lượt là
µA , µB. Tổng đại số của hai tập mờ A và B trong X, ký hiệu A+B là một tập mờ có
hàm thuộc được xác định như sau:
µ
A+B
(x) = µA (x) + µB(x) - µA(x).µB(x) ∀x∈X
e.Phần bù của một tập mờ
Cho A là tập mờ trong X có hàm thuộc µA . Phần bù A của A trong X là một
tập mờ có hàm thuộc xác định như sau:
µ
¬
A
= 1 - µA (x) ∀x∈X.
f. Tổng rời của hai tập mờ
CH1301062 Trang 7
Toán học cho khoa học máy tính Ứng dụng logic mờ trong phân cụm dữ liệu
Cho X là tập hợp, A và B là hai tập mờ trong X. Tổng rời của hai tập mờ A và
B trong X, ký hiệu A⊕B định nghĩa như sau:
A⊕B = (A∩B) ∪ (A∩B)
g. Phép trừ hai tập mờ

2
)), …, (x
n
, µA(x
n
))}.
Nếu X là một tập liên tục thì hàm thuộc của A thường được biểu diễn bằng đồ
thị. Người ta thường chọn các hàm thuộc có hình tam giác, hình bậc thang hay hình
chuông…
Ví dụ:
Cho X là tập các sinh viên một trường đại học, B là tập các sinh viên cao. Khi
đó hàm thuộc của B được xác định bởi hình vẽ sau
 Nếu µA(x) = 0 thì có thể nói x chắc chắn không thuộc B.
 Nếu µA(x) = 1 thì có thể nói x chắc chắn thuộc B.
CH1301062 Trang 9
Toán học cho khoa học máy tính Ứng dụng logic mờ trong phân cụm dữ liệu
CHƯƠNG III : QUAN HỆ MỜ
3.1 Khái niệm
Quan hệ mờ đóng vai trò quan trọng trong logic mờ và lập luận xấp xỉ. Khái
niệm quan hệ mờ là sự tổng quát hóa trực tiếp của khái niệm quan hệ (quan hệ rõ).
Giả sử U và V là hai tập hợp và một quan hệ R từ U đến V (quan hệ hai ngôi)
là một tập con của tích đề-các UV. Trong trường hợp U = V, ta nói R là quan hệ trên
U.
Khi U và V là các tập hữu hạn, chúng ta sẽ biểu diễn quan hệ R từ U đến V bởi
ma trận, trong đó các dòng được đánh dấu bởi các phần tử xU và các cột được đánh
dâu bởi các phần tử yV. Phần tử của ma trận nằm ở dòng x, cột y là R(x,y).
3.2 Định nghĩa
3.2.1 Quan hệ mờ trên tích đề-các
Cho X,Y là hai tập và x∈X, y∈Y. Ký hiệu (x,y) là cặp thứtựnằm trong tích
Đề-các XY. Tập mờR = {(x,y), µR(x,y)|(x,y) ∈XxY} được gọi là một quan hệ mờ

µ
R1.R2
(x,z) = max
y
(µ
R1
(x,y). µ
R2
(y,z)) ∀x∈X, ∀y∈Y, ∀z∈Z
Phép hợp thành max-trung bình
Giả sử R1 là quan hệ mờ trong X×Y, R2 là quan hệ mờ trong Y×Z. Phép hợp
thành max-trung bình của hai quan hệ mờ R1, R2 (R1avR2) là quan hệ mờ trong X×Z
thoả mãn:
µ
R1avR2
(x,z) = max
y
((µ
R1
(x,y)+µ
R2
(y,z))/2) ∀x∈X, ∀y∈Y, ∀z∈Z
 Phép hợp thành max-*.(max-* composition) (* là toán tử hai ngôi bất kỳ)
Giả sử R 1 là quan hệ mờ trong X×Y, R 2 là quan hệ mờ trong Y×Z. Phép
hợp thành max-* của hai quan hệ mờ R1 , R2 (R1 * R2 ) là một quan hệ mờ trong
X×Z thoả mãn:
µ
R1*R2
(x,z) = max(µ
R1

CHƯƠNG IV : GOM NHÓM DỮ LIỆU
4.1 Gom nhóm là gì?
Gom nhóm là quá trình nhóm các đối tượng thànhnhững nhóm/cụm/lớp có ý
nghĩa. Các đối tượng trong cùng một nhóm có nhiều tính chất chung và có những tính
chất khác với các đối tượng ở nhóm khác.
Đây là quá trình xử lý một tập các đối tượng vào trong các lớp các đối tượng
giống nhau được gọi là phân cụm. Một cụm là một tập hợp các đối tượng dữ liệu
giống nhau trong phạm vi cùng một cụm và không giống nhau với các đối tượng trong
các cụm khác. Số các cụm dữ liệu được phân ở đây có thể được xác định trước theo
kinh nghiệm hoặc có thể được tự động xác định của phương pháp gom nhóm.
Cho CSDL D={t
1
,t
2
,…,t
n
} và số nguyên k, gom nhóm là bài toán xác định ánh
xạ f: Dg{1,…,k}sao cho mỗi t
i
được gán vào một nhóm (lớp) K
j
,1 ≤ j ≤ k.
Cách biểu diễn các nhóm/cụm
 Phân chia bằng các đường ranh giới
 Các khối cầu
 Theo xác suất
 Sơ đồ hình cây, …
Không giống bài toán phân lớp, các nhóm/cụm/lớp không được biết trước.
Gom cụm là một bước quan trọng trong “khai phá dữ liệu”, gồm 6 bước
a. Gom cụm dữ liệu.

 Các tiêu chuẩn gom nhóm
- Phương pháp gom nhóm tốt là phương pháp sẽ tạo các nhóm có chất lượng :
 Sự giống nhau giữa đối tượng trong cùng một nhóm cao.
 Giữa các nhóm thì sự giống nhau thấp.
- Chất lượng của kết quả gom nhóm dựa trên 2 yếu tố :
 Độ đo sự giống nhau dùng trong phương pháp gom nhóm và
 Sự thi hành nó
- Một số độ đo chất lượng :
 Bình phương sai (Sum of Squared Error -SSE)
 Entropy
CH1301062 Trang 13
Toán học cho khoa học máy tính Ứng dụng logic mờ trong phân cụm dữ liệu
 Độ đo khoảng cách
Độ đo khoảng cách thường dùng để xác định sự khác nhau hay giống nhau giữa
hai đối tượng .
+ Khoảng cách Minkowski :
d(i,j) =
với i =(x
i1
, x
i2
, …, x
ip
) và j = (x
j1
, x
j2
, …, x
jp
) : hai đốitượng p-chiều và q là số

Phân cụm dựa theo lưới
Sử dụng lưới các ô cùng cỡ: tuy nhiên cụm là các “ô” phân cấp
Tạo phân cấp ô lưới theo một số tiêu chí: số lượng đối tượng trong ô
Thuật toán: STING, CLIQUE, WaweCluster…
Phân cụm dựa theo mô hình
Giải thiết: Tồn tại một số mô hình dữ liệu cho phân cụm
Xác định mô hình tốt nhất phù hợp với dữ liệu
Thuật toán: MCLUST…
Phân cụm mờ
Giả thiết: không có phân cụm “cứng” cho dữ liệu và đối tượng có thể thuộc
một số cụm
Sử dụng hàm mờ từ các đối tượng tới các cụm
Thuật toán: FCM (Fuzzy CMEANS),…
CH1301062 Trang 15
Toán học cho khoa học máy tính Ứng dụng logic mờ trong phân cụm dữ liệu
CHƯƠNG V : THUẬT TOÁN K-MEANS
5.1 Tổng quan
Đây là một giải thuật gom nhóm đơn giản không tham số. Ý tưởng chính của
giải thuật này đơn giản chỉ là xem mỗi mẫu dữ liệu là một điểm trên không gian N
chiếu, trong đó các điểm gần nhau sẽ được gom vào thành một nhóm.
Ban đầu giải thuật sẽ sinh ngẫu nhiên K điểm và xem như đó là trọng tâm của
K nhóm tương ứng. Sau đó các điểm sẽ được lần lượt phân vào các nhóm có trọng
tâm gần nó nhất. Cuối cùng, các trọng tâm nhóm sẽ được tính lại dựa trên các điểm dữ
liệu thuộc nhóm đó. Quá trình trên sẽ được lặp lại liên tục cho đến khi phạm vi dao
động của các trọng tâm nhỏ hơn một ngưỡng nào đó (hội tụ).
Ở đây, tiêu chuẩn gần nhất sẽ được xác định dựa theo một tiêu chuẩn độ đo
khoảng cách nào đó như Euclide, Minkowsky. Ngưỡng hội tụ sẽ được thiết lập dựa
trên bản chất của dữ liệu.
Nhìn chung, đây là một thuật giải dễ cài đặt, dễ hiểu có khả năng ứng dụng
trong thực tế nhưng cũng có nhiều hạn chế. Đầu tiên, thuật giải này có hạn chế ở chỗ

 Ưu điểm
 Đơn giản, dễ sử dụng
 Hiệu quả về thời gian: tuyến tính O(tkn), t số lần lặp, k số cụm, n là số
phần tử
 Một thuật toán phân cụm phổ biến nhất
 Thường cho tối ưu cục bộ. Tối ưu toàn cục rất khó tìm
 Nhược điểm
 Phải “tính trung bình được”: dữ liệu phân lớp thì dựa theo tần số
 Cần cho trước k : số cụm
 Nhạy cảm với ngoại lệ (cách xa so với đại đa số dữ liệu còn lại): ngoại
lệ thực tế, ngoại lệ do quan sát sai (làm sạch dữ liệu)
 Nhạy cảm với mẫu ban đầu: cần phương pháp chọn mẫu thô tốt
 Không thích hợp với các tập dữ liệu không siêu-ellip hoặc siêu cầu (các
thành phần con không ellip/cầu hóa)
5.4 Bài toán minh họa
Cho bảng dữ liệu (đã chuẩn hóa) như sau
.
Customer Age Income No. cards
Lâm 0.35 0.03 0.67
Hưng 0.05 0.12 0.33
Mai 0.19 0.06 0.00
Lan 0.58 0.41 0.33
Thủy 0.00 0.00 0.67
Tuấn 0.33 0.15 0.33
Minh 1.00 1.00 0.00
Vân 0.81 0.65 0.33
Thiện 0.91 0.82 0.00
Ngọc 0.12 0.06 1.00
Ta sẽ sử dụng thuật toán K-means (k=2) để gom nhóm
Bước 1. Chọn Thiện và Ngọc làm trung tâm của nhóm/cụm A và B.

Ngọc 1.28 0.50
Với các trung tâm nhóm mới này, thành phần của các nhóm không thay đổi.
Thuật toán dừng tại đây.
Sau khi sử dụng thuật toán K-mean ta thu được 2 nhóm A và B như sau:
A: Lan, Minh, Vân, Thiện.
B: Lâm, Hưng, Mai, Thủy, Tuấn, Ngọc
CH1301062 Trang 18
Toán học cho khoa học máy tính Ứng dụng logic mờ trong phân cụm dữ liệu
CHƯƠNG VI : THUẬT TOÁN FUZZY CMEANS (FCM)
6.1 Giới thiệu
Thuật toán phân cụm dữ liệu mờ FCM giống như k-means đều sử dụng chung
một chiến lược phân cụm dữ liệu. FCM phân chia tập dữ liệu ban đầu thành c cụm
mờ, trong đó mỗi đối tượng dữ liệu thuộc về các cụm được xác định bởi một hệ số là
độ phụ thuộc u
ik
[0,1] (k là chỉ số của cụm và i biểu thị số thứ tự của đối tượng dữ liệu
trong tập dữ liệu ban đầu), hệ số u
ik
này để chỉ quan hệ giữa các đối tượng với cụm dữ
liệu trong quá trình tính toán, hay còn gọi là mức độ phụ thuộc của đối tượng dữ liệu
thứ I vào trung tâm của cụm thứ k.
6.2 Hàm mục tiêu
Trong phân cụm mờ, tổng tất cả các phân hoạch mờ có c cụm dữ liệu của tập
dữ liệu có N đối tượng trong không gian D chiều được xác định như sau:
Trong đó: RcN là không gian của tất cả các ma trận thực cấp c*N, uik là các
phần tử của ma trận U.
Hàm mục tiêu của thuật toán FCM được định nghĩa như sau:
∑∑
= =
=

= |x
k
– v
i
|
A
(3)
Trong đó: A là ma trận hữu hạn dương.
Họ các hàm mục tiêu xác định trong công thức (2) với tham số mũ m [1,∞).
Sau đây là các điều kiện cần thiết nhằm tối thiểu hàm mục tiêu J
m
(U,V).
Ta có định lý
Nếu m và c là các tham số cố định, và Ik là một tập được định nghĩa như sau:
Thì hàm mục tiêu J
m
(U,V) đạt giá trị tối thiểu khi và chỉ khi:
CH1301062 Trang 19
Toán học cho khoa học máy tính Ứng dụng logic mờ trong phân cụm dữ liệu
Và
Để có một phân hoạch tối ưu thì hàm mục tiêu đạt giá trị tối thiểu, hay hai công
thức trên phải được thỏa mãn.
6.3 Thuật toán FCM
Đầu vào: Số cụm c và tham số mũ m cho hàm tiêu chuẩn J
Kết quả trả về: c cụm dữ liệu sao cho hàm tiêu chuẩn trong (2) đạt giá trị tối
thiểu.
B1: Nhập giá trị cho hai tham số c (1<c<N), m (1,∞) và khởi tạo ma trận mẫu
V
(0)
R

y học, …
Nhược điểm
Nhạy cảm với các nhiễu và phần tử ngoại lai jtrong dữ liệu, nghĩa là các trung
tâm cụm có thể nằm xa xo với trung tâm thực của cụm. Do đó các cụm dữ liệu được
khám phá có thể rất lệnh so với các cụm trong thực tế. Việc khử nhiễu và phần tử
ngoại lại là một vấn đề cần phải được giải quyết.
6.5 Bài toán minh họa
Cho tập điểm:
X
1
={1,3} = {x
11,
, x
12
}
X
2
={1.5,3.2} = {x
21,
, x
22
}
X
3
={1.3,2.8} = {x
31,
, x
32
}
CH1301062 Trang 21

ij
x
v
1
1
)(
)(
µ
µ
a. Với cụm 1(c=1)
0.3
3
8.32.33
26.1
3
3.15.11
3
0111
*0*1*1*1
****
12
321
11
4321
2
4
2
3
2
2

xxxx
v
jjj
jjjj
jjjj
j
µµµµ
µµµµ
b. Với cụm 2(c=2)
Vector v
1
cho cụm 1
}1,3{
1,3
1000
2
2221
2222
4
2
=
==
+++
=
v
vv
x
v
j
j

=−+−=
=−+−=
=−+−=
=−+−=
=−+−=
=−+−=
=−+−=
d
d
d
d
d
d
d
d
Với độ đo khoảng cách, cập nhật U
00
0
65.2
1
993.0
47.2
20.0
1
968.0
66.2
31.0
1
991.0
82.2

12
1
22
1
2
21
2
11
1
2
1
1
11
1
1
)(
)(
)1(
1313
1212
111111
==











=
=














+=












+=
















+








=
=









+








=















−
=
+
∑
∑
ICho
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
PT
d
d
c
j
j

ma trận phân hoạch mới
Với cụm 1(c=1)
Vector v
1
cho cụm 1
)3,26.1(
0.3
94.2
816.8
94.2
8.2*)993.0(2.3*)986.0(3*)991.0(
26.1
94.2
17.3
94.2
3.1*)993.0(5.1*)986.0(1*)991.0(
)0()993.0()986.0()991.0(
*)0(*)993.0(*)986.0(*)991.0(
1
222
11
222
11
2222
4
2
3
2
2
2

2
222
22
2222
21
2222
4
2
3
2
2
2
1
2
2
=
=
++
=
=
+++
=
+++
+++
=
V
v
v
xxxx
v