Đề tài: Ứng dụng thuật toán phân cụm trong thiết kế luật hệ Anfis
MỤC LỤC
PHẦN 1. TỔNG QUAN VỀ PHÂN CỤM MỜ.............................................................4
1.1. Phân cụm dữ liệu...............................................................................................4
1.2. Phân cụm mờ.....................................................................................................4
PHẦN 2: THUẬT TOÁN PHÂN CỤM MỜ C-MEANS..............................................6
2.1. Giới thiệu chung................................................................................................6
2.2. Thuật toán FCM (Fuzzy C-means)....................................................................6
2.2.1. Hàm mục tiêu.................................................................................................6
2.2.2. Thuật toán FCM.............................................................................................9
PHẦN 3: MẠNG THÍCH NGHI DỰA TRÊN CƠ SỞ HỆ SUY DIỄN MỜ (ANFIS) 13
3.1.
3.2.
3.3.
3.4.
3.5.

Giới thiệu về Anfis - Adaptive Neuro-Fuzzy Interference System...................13
Fuzzy Inference System (FIS).........................................................................13
Mạng thích nghi (Adaptive network)...............................................................14
Kiến trúc của Anfis..........................................................................................14
Giới thiệu về công cụ Anfis trên Matlab..........................................................17

PHẦN 4: ỨNG DỤNG THUẬT TOÁN PHÂN CỤM TRONG THIẾT KẾ LUẬT HỆ
ANFIS.......................................................................................................................... 18
4.1. Giới thiệu về chương trình...............................................................................18
4.2. Giao diện chương trình....................................................................................18
4.3. Code chương trình...........................................................................................19
File anfisedit.m.........................................................................................................19
TÀI LIỆU THAM KHẢO............................................................................................21

PHẦN 1. TỔNG QUAN VỀ PHÂN CỤM MỜ
1.1.

Phân cụm dữ liệu

Phân cụm là một công cụ toán học dùng để phát hiện cấu trúc hoặc các mẫu nào
đó trong tập dữ liệu, theo đó có đối tượng bên trong cụm dữ liệu thể hiện bậc tương
đồng nhất định.
Nói cách khác, Phân cụm dữ liệu là quá trình nhóm một tập các đối tượng
tương tự nhau trong tập dữ liệu vào các cụm sao cho các đối tượng thuộc cùng một
cụm là tương đồng còn các đối tượng thuộc các cụm khác nhau sẽ không tương đồng.
Không giống như phân lớp dữ liệu, phân cụm dữ liệu 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, trong khi phân lớp dữ liệu là học bằng ví dụ… Ngoài ra phân
cụm dữ liệu còn có thể được sử dụng như một bước tiền xử lý cho các thuật toán khai
phá dữ liệu khác. Với tư cách là một chức năng khai phá dữ liệu, phân tích phân cụm
có thể được sử dụng như một công cụ độc lập chuẩn để quan sát đặc trưng của mỗi
cụm thu được bên trong sự phân bố của dữ liệu và tập trung vào một tập riêng biệt của
các cụm để giúp cho việc phân tích đạt kết quả.
Một vấn đề thường gặp trong phân cụm là hầu hết các dữ liệu cần cho phân
cụm đều chứa dữ liệu nhiễu do quá trình thu thập thiếu chính xác hoặc thiếu đầy đủ, vì
vậy cần phải xây dựng chiến lược cho bước tiền xử lý dữ liệu nhằm khắc phục hoặc
loại bỏ nhiễu trước khi chuyển sang giai đoạn phân tích cụm dữ liệu. Nhiễu ở đây
được hiểu là các đối tượng dữ liệu không chính xác, không tường minh hoặc là các đối
tượng dữ liệu khuyết thiếu thông tin về một số thuộc tính…
Một trong các kĩ thuật xử lí nhiễu phổ biến là việc thay thế giá trị các thuộc tính
của đối tượng nhiễu bằng giá trị thuộc tính tương ứng. Ngoài ra dò tìm phần tử ngoại
lai cũng là một trong những hướng nghiên cứu quan trọng trong phân cụm, chức năng
của nó là xác định một nhóm nhỏ các đối tượng dữ liệu khác thường so với các dữ liệu

trong cơ sở dữ liệu, tức là các đối tượng dữ liệu không tuân theo các hành vi hoặc mô
hình dữ liệu nhằm tránh sự ảnh hưởng của chúng tới quá trình và kết quả của phân
cụm.
1.1.1. Mục tiêu của thuật toán phân cụm
Mục tiêu của phân cụm là xác định được bản chất nhóm trong tập DL chưa có
nhãn. Nhưng để có thể quyết định được cái vì tạo thành một cụm tốt. Nó có thể được
chỉ ra rằng không có tiêu chuẩn tuyệt đối “tốt” mà có thể không phụ thuộc vào kq phân
cụm. Vì vậy, nó đòi hỏi người sử dụng phải cung cấp tiêu chuẩn này, theo cách mà kết
quả phân cụm sẽ đáp ứng yêu cầu.
Theo các nghiên cứu cho thấy thì hiện nay chưa có một phương pháp phân cụm
tổng quát nào có thể giải quyết trọn vẹn cho tất cả các dạng cấu trúc CDL. Hơn nữa,


các phương pháp phân cụm cần có cách thức biểu diễn cấu trúc của các CDL, với mỗi
cách thức biểu diễn khác nhau sẽ có tương ứng một thuật toán phân cụm phù họp. Vì
vậy phân cụm dữ liệu vẫn đang là một vấn đề khó và mở, vì phải giải quyết nhiều vấn
đề cơ bản một cách trọn vẹn và phù họp với nhiều dạng dữ liệu khác nhau, đặc biệt là
đối với dữ liệu hỗn hợp đang ngày càng tăng trong các hệ quản trị dữ liệu và đây cũng
là một trong những thách thức lớn trong lĩnh vực KPDL.
1.1.2. Thuật toán K-means
Thuật toán này dựa trên độ đo khoảng cách của các đối tượng dữ liệu trong
cụm. Trong thực tế, nó đo khoảng cách tới giá trị trung bình của các đối tượng dữ liệu
trong cụm. Nó được xem như là trung tâm của cụm. Như vậy, nó cần khởi tạo một tập
trung tâm các trung tâm cụm ban đầu, và thông qua đó nó lặp lại các bước gồm gán
mỗi đối tượng tới cụm mà trung tâm gần, và tính toán tại tung tâm của mỗi cụm trên
cơ sở gán mới cho các đối tượng. Quá trình lặp này dừng khi các trung tâm hội tụ.

Hình 1.1: Các thiết lập để xác định ranh giới các cụm ban đầu
Mục đích của thuật toán k-means là sinh k cụm dữ liệu {Ci, c2,..., ck} từ một tập
dữ liệu chứa n đối tượng trong không gian d chiều Xi = {Xii, xi2,..., xid}, i = 1 -i- n, sao

cho hàm tiêu chuẩn:

đạt giá trị tối thiểu,
trong đó: mi là trọng tâm của cụm Ci, D là khoảng cách giữa hai đối tượng.


Hình 1.2.Tính toán trọng tâm của các cụm mới
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 }*.=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

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
tâm mj

, tính toán khoảng cách của nó tới mỗi trọng

. 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
, 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,
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 đon 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. Hon nữa, chất lượng PCDL 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.
1.2.

Phân cụm mờ

Trong cuộc sống, chúng ta đã gặp rất nhiều ứng dụng của bài toán phân cụm.
Chẳng hạn như trong ngành bưu điện, hàng ngày bưu điện phải phân loại thư theo mã
nước, trong mã nước lại phân loại theo mã tỉnh/thành phố, sau đó khi thư về đến bưu

điện tỉnh thì bưu điện tỉnh lại phải phân loại thư theo quận/huyện để gửi đi, đến bưu
điện quận/huyện lại phân loại thư theo xã/phường để gửi thư. Đó chính là một ứng
dụng của bài toán phân cụm rõ.
Ta có thể định nghĩa bài toán phân cụm rõ như sau: Cho tập dữ liệu mẫu X, ta
kiểm tra các điểm dữ liệu xem nó giống với đặc điểm của nhóm nào nhất thì ta gán
điểm dữ liệu đó vào trong nhóm đó. Nhưng trong thực tế không phải lúc nào bài toán
phân cụm rõ cũng áp dụng được. Chẳng hạn, ta có phép phân loại sau: Những người đi
xe máy xịn thì thuộc nhóm người giàu, những người đi xe máy thường thuộc nhóm
người bình dân. Vậy người nghèo mà đi xe máy xịn thì chúng ta xếp người đó vào
nhóm nào? Vì vậy, chúng ta cần đưa vào khái niệm bài toán phân cụm mờ.
phương pháp phân cụm phân hoạch một tập dữ liệu ban đầu thành các cụm dữ
liệu có tính tự nhiên và mỗi đối tượng dữ liệu chỉ thuộc về một cụm dữ liệu, phương
pháp này chỉ phù hợp với việc khám phá ra các cụm có mật độ cao và rời nhau, với
đường biên giữa các cụm được xác định tốt. Tuy nhiên, trong thực tế, đường biên giữa
các cụm có thể mờ, các cụm có thể chồng lên nhau, nghĩa là một số các đối tượng dữ
liệu thuộc về nhiều các cụm khác nhau, do đó mô hình này không mô tả được dữ liệu
thực. Vì vậy người ta đã áp dụng lý thuyết về tập mờ trong PCDL để giải quyết cho
trường họp này. Cách thức kết họp này được gọi là Phân cụm mờ.
Phân cụm mờ là phương pháp phân cụm dữ liệu mà cho phép mỗi điểm dữ liệu
thuộc về hai hoặc nhiều cụm thông qua bậc thành viên. Ruspini (1969) giới thiệu khái
niệm phân hoạch mờ để mô tả cấu trúc cụm của tập dữ liệu và đề xuất một thuật toán
để tính toán tối ưu phân hoạch mờ. Dunn (1973) mở rộng phương pháp phân cụm và
đã phát triển thuật toán phân cụm mờ. Ý tưởng của thuật toán là xây đựng một phương
pháp phân cụm mờ dựa trên tối thiểu hóa hàm mục tiêu. Bezdek (1981) cải tiến và
tổng quát hóa hàm mục tiêu mờ bằng cách đưa ra trọng số mũ để xây dựng thuật toán
phân cụm mờ và được chứng minh độ hội tụ của các thuật toán là cực tiểu cục bộ.


PHẦN 2: THUẬT TOÁN PHÂN CỤM MỜ C-MEANS
1.3.


Giới thiệu chung

K-means là thuật toán PCDL rõ và C-means là thuật toán phân cụm mờ tương
ứng, hai thuật toán này cùng sử dụng chung một chiến lược phân cụm dữ liệu. Thuật
toán C-means mờ hay còn gọi tắt là thuật toán FCM (Fuzzy C-means) đã được áp dụng
thành công trong giải quyết một số lớn các bài toán PCDL như trong nhận dạng mẫu
(nhận dạng vân tay, ảnh), xử lý ảnh (phân tách các cụm ảnh màu, cụm màu), y học
(phân loại bệnh, phân loại triệu chứng), ...
Tuy nhiên, nhược điểm lớn nhất của thuật toán FCM là tập dữ liệu lớn, tập dữ
liệu nhiều chiều, nhạy cảm với các nhiễu và phần tử ngoại lai trong dữ liệu, nghĩa là
các trung tâm cụm có thể nằm xa so với trung tâm thực của cụm. Đã có nhiều các
phương pháp đề xuất để cải tiến cho nhược điểm trên của thuật toán FCM bao gồm:
Phân cụm dựa trên xác suất (keller, 1993), phân cụm nhiễu mờ (Dave, 1991), phân
cụm dựa trên toán tử LP Norm (Kerten, 1999) và thuật toán e- Insensitive Fuzzy Cmeans (eFCM) và thuật toán FCM cải tiến.
1.4.

Thuật toán FCM (Fuzzy C-means)

1.4.1. Hàm mục tiêu
Kỹ

thuật

này

phân

hoạch


một

tập

n-vectơ

đối

tượng

dữ

liệu

X  {x1 ,..., x n } � R thành c nhóm mờ dựa trên tính toán tối thiểu hàm mục tiêu để
s

đo chất lượng của phân hoạch và tìm trung tâm cụm trong mỗi nhóm, sao cho chi phí
hàm đo độ phi tương tự là nhỏ nhất.
Một phân hoạch mờ vectơ điểm dữ liệu X  {x1 ,..., x n } � R s là đặc trưng đầu
vào được biểu diễn bởi ma trận U   uik  sao cho điểm dữ liệu đã cho chỉ có thể
thuộc về một số nhóm với bậc được xác định bởi mức độ thuộc giữa [0, 1]. Như vậy,
ma trận U được sử dụng để mô tả cấu trúc cụm của X bằng cách giải thích u ik như bậc
thành viên xk với cụm i.
Cho u   u1 , u2 ,..., uc  là phân hoạch mờ C

U cxn

u11 K
�

�
 �M O
�
uc1 L
�

u1n �
M�
�
ucn �
�

Dunn định nghĩa hàm mục tiêu mờ như sau:
n

c

J m (U , V )  ��uik d 2 ( xk , vi )
k 1 i 1


Bezdek khái quát hóa hàm mục tiêu mờ bằng cách đưa ra trọng số mũ m > 1 là
bất kỳ số thực nào như sau:
J m (U , V ) 

n

c

��(u

k 1 i 1

ik

) m d 2 ( xk , vi ),1 �m ��(1)

Trong đó :

X   x1 , x2 ,..., xn  �R d là nửa dưới vector mẫu dữ liệu tập con thực d chiều trong
không gian vector R d .

m � 1, � là trọng số mũ hay còn gọi là tham số mờ.
vi �R d là trọng tâm của cụm thứ i
1/2

�d
2�
dik  d ( xk  vi )  xk  vi  �
(
x

v
)
�
� là khoảng cách theo thước đo Euclide
kj
ij
j

1

�
�
giữa mẫu dữ liệu xk với trọng tâm cụm thứ i , vi
uik � 0,1 là bậc hay độ thuộc của dữ liễu mẫu xk với cụm thứ i
dxc
V �
v ji �
�
�  v1 ,..., vc  �R là ma trận biểu diễn các giá trị tâm của cụm

Một trong các nhân tố chính ảnh hưởng tới quyết định phân cụm hợp lí các
điểm là vấn đề chọn phép đo độ phi tương tự. Thực vậy, tính toán bậc thành viên uik
phụ thuộc vào định nghĩa của phép đo khoảng cách dik mà là tích vô hướng trên RS
. Bình phương khoảng cách giữa vectơ mẫu xk và trung tâm vị trí của cụm thứ i được
định nghĩa như sau:

d ( xk , v1 )  xk  v1  ( xk  v1 )T A( xk  v1 )
d 2 ( xk , v1 )  xk  v1

2

 ( xk  v1 )T A( xk  v1 )

trong đó:
A là ma trận hữu hạn dương đối xứng (p x p) bất kỳ,
lệch của dữ liệu xk với v1 , d ( xk , v1 ) là tích vô hướng trên R s .
Bậc của thành viên thỏa mãn ràng buộc sau:

xk  v1


2

biểu diễn độ


�
� 0 �u �1,
ik
�
n
�
0  �uik  n
�
� k 1
� c
� �uik  1
� i 1

1 �i �c,1 �k �n
1 �i �c

(2)

1 �k �n

Để thuận tiện, coi mảng đối tượng dữ liệu {x1 ,....,x n } là các cột trong ma trận
sxc
x jk �
đối tượng dữ liệu X = �
�

�  x1 ,....,x n  �R . Ma trận phân hoạch U là một công

cụ tiện lợi để mô tả cấu trúc cụm trong dữ liệu {x1 ,....,x n } ; định nghĩa tập tất cả các
ma trận thực phân hoạch mờ không suy thoái cấp cxn cho phân hoạch n đối tượng
thành c cụm dữ liệu trong không gian

R sxc được viết gọn như sau:

c
c
�
�
M fcn  �
U �R cxn i, k : uik �[0,1];�u ik  1;0 ��u ik  1  n; �(3)
i=1
i=1
�
�

R cxn

là không gian của tất cả các ma trận thực cấp cxn. Thông thường người ta gọi

bài toán phân cụm mờ là bài toán tìm các độ thuộc uij nhằm tối thiểu hàm mục tiêu ở
trên J m (U , V ) với các điều kiện sau:
Định lí 1: 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:

I


1�k �n

k

 {i 1 �i �c,d ik  0} (4)

thì hàm mục tiêu J m (U ,V ) đạt giá trị tối thiểu:
n
c
�
�
min �J m (U , V )  ��(u ik ) m d 2 ( xk , v1 ) �
k=1 i=1
�
�

khi và chỉ khi:
�
1
,
�
2
m

1
�c �d �
�
� ik �
�
�

�
d �
uik  �j 1 � jk �
�
0,
��
�
��
�uik  1,
��
i�I k
�
�

Ik  ;
1 �i �c,1 �k �n

(5)

i �I k ,
i  Ik , Ik




n

vi 

�(u


) m xk

ik

k=1
n

�(u

ik

,

1 �i �c (6)

)m

k=1

2
Định lí đã được Bezdek chứng minh (nếu m �1, d ik  0,1 �i �c ) là đúng

đắn. Một phân hoạch tối ưu, nghĩa là hàm mục tiêu đạt giá trị tối thiểu, mà chủ yếu
dựa trên đó độ tương tự giữa xk và trung tâm cụm vi , điều này tương đương với
hai điều kiện (5) và (6) phải thỏa mãn. Với hàm mục tiêu và các ràng buộc để hàm
mục tiêu đạt giá trị tối thiểu trên đây.
1.4.2. Thuật toán FCM
Thuật toán FCM cung cấp một quá trình lặp qua lại giữa phương trình (5) và (6)
để tối ưu (xấp xỉ cực tiểu) hàm mục tiêu dựa trên đo đạc độ tương tự có trọng số giữa

xk và trung tâm cụm vi , sau mỗi vòng lặp, thuật toán tính toán và cập nhật các phần tử
ujk trong ma trận phân hoạch U. Phép lặp sẽ dừng khi maxx ij 
trong đó



u ij( k 1)  uij( k ) �

,

là chuẩn kết thúc giữa 0 và 1, trong khi k là các bước lặp. Thủ tục này hội

tụ tới cực tiểu cục bộ hay điểm yên ngựa của J m (u , V ) .Thuật toán FCM tính toán ma
trận phân hoạch U và kích thước của các cụm để thu được các mô hình mờ từ ma trận
này. Các bước thực hiện của thuật toán FCM như sau:
Input : Số cụm c và tham số mũ m cho hàm mục tiêu J;
Output: c cụm dữ liệu sao cho hàm mục tiêu trong (1) đạt giá trị cực tiểu;
Begin
1. Nhập tham số cụm c (1
V  [vij ], V (0) �R sxc , j  0;
2. Repeat
2.1. j:=j+1;
2.2. Tính ma trận phân hoạch mờ U ( j ) theo công thức (5);
( j)
(j)
(j)
(j)
2.3. Cập nhật các trung tâm cụm V  [v1 , v 2 ,....,v c ] dựa vào công thức

(6) và

U ( j)

(j+1)
U ( j)
3. Until ( U

F

) �

4. Trình diễn các cụm kết quả;
End.


Trong đó, *

U

2
F

F

là tiêu chuẩn Frobenious được định nghĩa như sau:

 Tr (UU T )  ��
u 2 và tham số
i

k ik



được cho trước .

Nhận xét:
Việc chọn các tham số cụm rất ảnh hưởng đến kết quả phân cụm, tham số này
thường được chọn theo phương pháp ngẫu nhiên hoặc theo Heuristic.
Đối với m � 1 thì thuật toán FCM trở thành thuật toán rõ
Đối với m � � thì thuật toán FCM trở thành thuật toán phân cụm mờ với

1
uik  . Chưa có luật nào nhằm chọn lựa tham số m đảm bảo cho phân cụm hiệu quả,
c
thông thường chọn m=2.
Ta có thể tiến hành đánh giá việc lựa chọn số tâm cụm tối ưu:
c
n
�
2
2 �
1 n
min �P(c)  ��uikm ( x k  v i  v i  x ) �Trong đó: x  � x
(c )
n k 1 k
i 1 k 1
�

Để dễ hiểu có thể xét ví dụ sau: Cho một tập các đối tượng dữ liệu một chiều được

biểu thị như sau:

Hình 2.1: Mô phỏng về tập dữ liệu đơn chiều
Bằng quan sát dễ nhận thấy có hai cụm trong tập dữ liệu trên đặt tên tương ứng
là "A" và "B". Với thuật toán k-means thì hàm tính độ phụ thuộc giữa đối tượng dữ
liệu và trọng tâm cụm của nó được thể hiện như trong đồ thị Hình 2.2 dưới đây:

Hình 2.2: Hàm thuộc với trọng tâm của cụm A trong k-means
Dựa vào hình rút ra nhận xét rằng, các đối tượng trong cụm A có giá trị hàm
thuộc với trọng tâm của cụm A là bằng 1 và bằng 0 với trọng tâm cụm B. Điều này


ngược lại với các đối tượng ở trong cụm B. Thế nhưng, đối với thuật toán FCM thì
hàm thuộc của các đối tượng dữ liệu với các trung tâm cụm dữ liệu được minh họa
như trong đồ thị Hình 2.3 dưới đây:

Hình 2.3: Hàm thuộc với trọng tâm của cụm A trong FCM
Dựa vào hình có thể nhận xét rằng, các đối tượng dữ liệu có giá trị hàm thuộc
với các trọng tâm của cụm A nằm trong khoảng [0, l], hàm thuộc lúc này là một đường
cong trơn. Điểm có mũi tên chỉ đến có nhiều khả năng thuộc về lớp B hơn là lớp A do
giá trị hàm thuộc của nó vào lớp A là nhỏ (=0.2). Có thể biểu diễn các giá trị hàm
thuộc trên bằng ma trận cho cả hai trường hợp như sau:

U nxc

1
�
�
0
�

 �
1
�
...
�
�
0
�

0�
0.8
�
�
�
1�
0.3
�
U nxc  �
0�
0.6
�
�
.....
�
�
�
1�
0.9
�
�

0.2 �
0.7 �
�
0.4 �
�
�
0.1�
�

Số dòng và số cột phụ thuộc vào số các đối tượng dữ liệu n và số các cụm k.
Một số ví dụ mô phỏng về kết quả các cụm khám phá được của thuật toán phân cụm
mờ FCM như Hình 2.4 dưới đây:

Hình 2.4: Các cụm khám phá được bởi thuật toán FCM
Độ phức tạp của thuật toán FCM tương đương với độ phức tạp của thuật toán kmeans trong trường hợp số đối tượng của tập dữ liệu cần phân cụm là rất lớn.


Thuật toán phân cụm mờ FCM là một mở rộng của thuật toán k-means nhằm để
khám phá ra các cụm chồng lên nhau, tuy nhiên, FCM vẫn chứa đựng các nhược điểm
của thuật toán k-means trong việc xử lí đối với các phần tử ngoại lai và nhiễu trong dữ
liệu.
Tóm lại, phân cụm mờ là một sự mở rộng của phân cụm dữ liệu bằng cách
thêm vào yếu tố quan hệ giữa các phần tử và các cụm dữ liệu thông qua các trọng số
trong ma trận U. Bằng cách này, có thể khám phá ra các cụm dữ liệu phức tạp theo
cách mềm dẻo từ một tập dữ liệu đã cho. Thuật toán phân cụm mờ là một cách thức
mở rộng cho các thuật toán phân cụm rõ nhằm khám phá ra các cụm dữ liệu chồng lên
nhau trên các tập dữ liệu có kích thước lớn, nhiều chiều và nhiều nhiễu...

PHẦN 3: MẠNG THÍCH NGHI DỰA TRÊN CƠ SỞ HỆ SUY DIỄN MỜ
(ANFIS)
2.1.

Giới thiệu về Anfis - Adaptive Neuro-Fuzzy Interference System

ANFIS-Adaptive Neuro-Fuzzy Interference System là sự kết hợp của hai
phương pháp tính toán của mạng nơ ron nhân tạo (ANN) và logic mờ (Jang 1993).
Logic mờ có khả năng thay đổi các khía cạnh định tính của kiến thức con người và
hiểu biết sâu sắc vào quá trình phân tích định lượng chính xác. Tuy nhiên, nó không có
một phương pháp xác định có thể được sử dụng như là một hướng dẫn trong quá trình
chuyển đổi và suy nghĩ của con người vào hệ thống suy luận mờ cơ sở (FIS) và phải
mất khá nhiều thời gian để điều chỉnh các chức năng thành viên (MFs) (Jang 1993).
Không giống như ANN, nó có khả năng cao hơn trong quá trình học tập để thích nghi
với môi trường của nó. Do đó, ANN có thể được sử dụng để tự động điều chỉnh MFs
và giảm tỷ lệ sai sót trong việc xác định các luật trong logic mờ.
Sử dụng tập dữ liệu vào/ra có sẵn, hàm anfis xây dựng nên hệ thống suy diễn mờ
(FIS- Fuzzy Inference System), các thông số hàm liên thuộc của nó được điều chỉnh
nhờ sử dụng các thuật toán huấn luyện của mạng nơron như thuật toán lan truyền
ngược (BP) hoặc kết hợp lan truyền với phương pháp bình phương cực tiểu. Điều đó
cho phép hệ mờ của ta "học" từ tập dữ liệu chúng được mô hình.
2.2.

Hệ thống suy diễn mờ (FIS)

Một FIS - Fuzzy Inference System được xây dựng trên ba thành phần chính, đó
là đầu vào, đầu ra và các luật cơ bản, trong đó bao gồm việc lựa chọn các luật logic mờ
"If-Then;" như một chức năng của thành viên tập mờ; và lý luận các kỹ thuật suy luận
mờ từ các luật cơ bản để có được đầu ra.
Hình 3.1 cho thấy cấu trúc chi tiết của FIS. FIS sẽ làm việc khi đầu vào có chứa

giá trị thực tế được chuyển đổi sang các giá trị mờ bằng cách sử dụng quá trình
fuzzifile thông qua chức năng thành viên của nó, trong đó giá trị mờ có khoảng từ 0
đến 1.
Các luật cơ bản và cơ sở dữ liệu được gọi là cơ sở tri thức, nơi cả hai yếu tố
chính trong quá trình ra quyết định. Thông thường, cơ sở dữ liệu chứa các thông tin
như thông tin về tham số bộ mờ với một hàm đã được xác định cho mỗi biến ngôn ngữ
hiện tại. Sự phát triển của cơ sở dữ liệu thường bao gồm việc xác định dữ liệu toàn
cầu, xác định số lượng các giá trị ngôn ngữ được sử dụng cho mỗi biến ngôn ngữ,
cũng như thiết lập một chức năng thành viên


Hình 3.1 Cấu trúc của FIS
Dựa trên các luật, nó chứa các toán tử logic mờ và một câu lệnh có điều kiện "IfThen." Các luật cơ bản có thể được xây dựng từ thế hệ con người hoặc tự động, nơi mà
các luật tìm kiếm sử dụng dữ liệu đầu vào-đầu ra theo số lượng.
Có một số loại FIS như Takagi-Sugeno, Mamdani, và Tsukamoto (Cheng và cộng
sự, 2005). Một mô hình FIS của mô hình Takagi-Sugeno đã được sử dụng rộng rãi
trong việc áp dụng phương pháp ANFIS..
2.3.

Mạng thích nghi (Adaptive network)

Mạng Adaptive là một ví dụ về mạng nơ-ron thích nghi với nhiều lớp (xem hình
3.2). Trong quá trình học, các mạng này thường sử dụng thuật toán học có giám sát.
Ngoài ra, mạng thích nghi có đặc điểm kiến trúc bao gồm một số nút thích nghi được
kết nối trực tiếp mà không có bất kỳ giá trị trọng lượng giữa chúng.
Mỗi nút trong mạng này có các chức năng và nhiệm vụ khác nhau, và kết quả đầu
ra phụ thuộc vào các tín hiệu và các thông số đến có trong nút. Một luật học đã được
sử dụng có thể ảnh hưởng đến các tham số trong nút và nó có thể làm giảm sự xuất
hiện của các lỗi ở đầu ra của mạng thích nghi (Jang 1993).
Trong việc tìm hiểu mạng lưới thích nghi cơ bản, nó thường sử dụng gradient

xuôi hoặc ngược lại và luật dây chuyền. Tất cả các thuật toán học này đã được đề xuất
bởi Werbos năm 1970 (Jang 1993). Cho đến nay, gradient xuống hoặc truyền lại vẫn
được sử dụng như là một thuật toán học trong một mạng thích nghi. Mặc dù vậy, vẫn
còn những điểm yếu trong thuật toán tăng tốc và có thể làm giảm khả năng và tính
chính xác của các mạng thích nghi trong việc ra quyết định. Tốc độ hội tụ chậm và có
xu hướng luôn luôn bị mắc kẹt trong minimimax cục bộ là những vấn đề chính trong
thuật toán tăng tốc.

Hình 3.2 Adaptive network


2.4.

Kiến trúc của Anfis

Kiến trúc ANFIS là một mạng lưới thích nghi sử dụng học có giám sát trên thuật
toán học, có một chức năng tương tự như mô hình hệ thống suy luận mờ TakagiSugeno. Hình 3.3 a, b cho thấy cơ chế lý luận mờ cho mô hình Takagi-Sugeno và kiến
trúc ANFIS. Để đơn giản, giả sử rằng có hai đầu vào x và y, và một đầu ra f. Hai luật
đã được sử dụng trong phương pháp "If-Then" cho mô hình Takagi-Sugeno, như sau:

trong đó A1, A2 và B1, B2 là các chức năng thành viên của mỗi đầu vào x và y (một
phần của mặt bằng), trong khi p1, q1, r1 và p2, q2, r2 là các tham số tuyến tính trong phần
- Sau đó (một phần hậu quả) của Takagi -Sueno fuzzy suy luận mô hình.
Đề cập đến hình 3.3, kiến trúc ANFIS có 5 lớp. Các lớp thứ nhất và thứ tư chứa
một nút thích nghi, trong khi các lớp khác chứa một nút cố định. Mô tả ngắn gọn về
mỗi lớp như sau:
Lớp 1: Mỗi nút trong lớp này thích nghi với một tham số chức năng. Đầu ra từ
mỗi nút là một mức độ giá trị thành viên được đưa ra bởi đầu vào của các chức năng
thành viên. Ví dụ, chức năng thành viên có thể là một chức năng thành viên Gaussian
(tương đương 2.2), một chức năng thành viên tổng quát chuông (Eq. 2.3), hoặc một

loại chức năng thành viên là mức độ các chức năng thành viên cho các tập mờ Ai và
Bi, tương ứng , và {ai, bi, ci} là các tham số của một hàm thành viên có thể thay đổi
hình dạng của hàm thành viên. Các tham số trong lớp này thường được gọi là các tham
số tiền đề

Hình 3.3 a. Mô hình Sugeno


Hình 3.3b. Kiến trúc của ANFIS (Suparta và Alhasa 2013)

Lớp 2: Mỗi nút trong lớp này được định dạng hoặc không tương thích, và nút
tròn được gắn nhãn là P. Nút đầu ra là kết quả của việc nhân tín hiệu đi vào nút và
được chuyển đến nút tiếp theo. Mỗi nút trong lớp này đại diện cho sức mạnh vòng tròn
cho mỗi luật. Trong lớp thứ hai, toán tử T-norm với hiệu suất chung, chẳng hạn như
AND, được áp dụng để có được đầu ra

Trong đó wi là đầu ra đại diện cho sức mạnh vòng tròn của mỗi luật.
Lớp 3: Mỗi nút trong lớp này được định dạng hoặc không tương thích và nút tròn
được dán nhãn là N. Mỗi nút là một phép tính tỷ số giữa cường độ của các luật thứ i và
sức mạnh của vòng tròn của tất cả các luật. Kết quả này được gọi là cường độ vòng
chuẩn

Lớp 4: Mỗi nút trong lớp này là một nút thích nghi với đầu ra, với một hàm nút
được xác định là


Trong đó wi là sức mạnh vòng chuẩn hóa từ lớp trước (lớp thứ ba) và là một tham số
trong nút. Các tham số trong lớp này được gọi là các tham số kết quả.
Lớp 5: Nút duy nhất trong lớp này là một nút cố định hoặc nonadaptive tính tổng
sản lượng là tổng của tất cả các tín hiệu đến từ nút trước đó. Trong lớp này, một nút

tròn được dán nhãn là

Thuật toán BP tính trọng số từ đầu ra cuối sau đó từ cuối về đầu, có đầu ra rồi so sánh
và update trọng số. Lúc đầu các luật có vai trò bình đẳng như nhau, sau quá trình học
thì các trọng số sẽ khác nhaucác luật sẽ có vai trò khác nhau.
Quá trình học là quá trình điều chỉnh trọng số
2.5.

Giới thiệu về công cụ Anfis trên Matlab

Hình 3.4. Giao diện của ANFIS


PHẦN 4: ỨNG DỤNG THUẬT TOÁN PHÂN CỤM TRONG THIẾT KẾ LUẬT
HỆ ANFIS
3.1.

Giới thiệu về chương trình

Chương trình sẽ sử dụng giao diện ANFIS GUI của MATLAB và thêm chức
năng chạy thuật toán FCM vào phần Generate Fis.
Chức năng FCM sẽ cho phép chọn các thuộc tính như số cụm, số mũ…
Dữ liệu được load lên sau đó chọn FCM, gõ các thông số. Kết quả đưa ra màn
hình là biểu đồ với các mẫu dữ liệu được chia ra theo số cụm được chọn và tâm của
cụm.
3.2.

Giao diện chương trình

3.3.

Code chương trình

File anfisedit.m
case 'FCM'
if isempty(trnData)
msgbox('Load training data in order to generate ANFIS');
return
end
param=inputdlg({'Number clusters:','Exponent:','Max.
Iterations:','Min. Improvement:'},'FCM Settings', 1, {'3', '2',
'100', '0.00001'}, 'on');
if ~isempty(param)
numCluster = str2double(param{1});
exponent = str2double(param{2});
maxIteration = str2double(param{3});


minImpr = str2double(param{4});
opts = [exponent;maxIteration;minImpr;1];
fuzzyWatchOn;
fismat=genfis3(trnData(:,1:length(fis.input)),
trnData(:,length(fis.input)+1), ‘sugeno', numCluster, opts);
fismat.name=fis.name;
[center,U,obj_fcn] = fcm([trnData(:,1:length(fis.input)), ...
trnData(:,length(fis.input)+1)], numCluster, opts);
maxU = max(U);
plot(trnData(:,1),trnData(:,2),'o');
hold on;

for i=1:numCluster
index = find(U(i,:)== maxU);
color = rand(1,3);
line(trnData(index,1),trnData(index,2),'linestyle','none',
'marker','*','color',color);
plot(center(i,1),center(i,2),'x','MarkerSize',15,'LineWidth
',3, 'Color',color)
end
fuzzyWatchOff
end