ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

Phạm Đình Phong

PHÁT TRIỂN MỘT SỐ PHƯƠNG PHÁP THIẾT KẾ
HỆ PHÂN LỚP TRÊN CƠ SỞ LÝ THUYẾT TẬP MỜ
VÀ ĐẠI SỐ GIA TỬ

Chuyên ngành: Khoa học máy tính
Mã số: 62 48 01 01

TÓM TẮT LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH

Hà Nội – 2017


Công trình được hoàn thành tại: Trường Đại học Công nghệ, Đại học
Quốc gia Hà Nội

Người hướng dẫn khoa học: GS. TS. Nguyễn Thanh Thủy
PGS. TSKH. Nguyễn Cát Hồ

Phản biện: TS. Nguyễn Công Điều
Viện Công nghệ thông tin, Viện Hàn lâm KH&CN VN
Phản biện: TS. Dương Thăng Long
Viện Đại học mở Hà Nội
Phản biện: PGS. TS. Nguyễn Đình Hóa
Viện Công nghệ thông tin, Đại học Quốc gia Hà Nội

Luận án sẽ được bảo vệ trước Hội đồng cấp Đại học Quốc gia chấm luận

tập mờ tam giác của chúng cho bài toán xây dựng tự động cơ sở luật cho FLRBC.
Trong ứng dụng lý thuyết tập mờ thường đòi hỏi lõi của tập mờ là một khoảng do ngữ
nghĩa của từ ngôn ngữ chứa một miền có giá trị phù hợp với ngữ nghĩa của từ nhất. Ngữ
nghĩa dựa trên tập mờ của các từ ngôn ngữ được xem là dạng hạt (granule) và có lõi
(core). Như vậy, ngữ nghĩa của mỗi từ ngôn ngữ đều có lõi và được gọi là lõi ngữ nghĩa
(semantics core). Trong xu thế nghiên cứu ĐSGT, một cơ sở hình thức toán học cần được
phát triển để sinh lõi khoảng của tập mờ biểu diễn ngữ nghĩa của từ ngôn ngữ. Luận án
nghiên cứu trường hợp cụ thể sinh lõi khoảng của tập mờ hình thang do lõi của hình thang
có dạng khoảng nên chúng có thể được sử dụng để biểu diễn lõi ngữ nghĩa được biểu thị
bằng tập mờ của các từ ngôn ngữ. Mặt khác, vấn đề tối ưu các tham số ngữ nghĩa, sinh luật
và tìm kiếm hệ luật tối ưu vẫn cần những nghiên cứu cải tiến.
Mục tiêu đặt ra của luận án: Thứ nhất là mở rộng ĐSGT để làm cơ sở hình thức toán
học cho việc sinh lõi của các tập mờ gán cho các từ ngôn ngữ, cụ thể là lõi của tập mờ
hình thang và ứng dụng giải bài toán thiết kế tự động cơ sở luật cho hệ phân lớp dựa trên
luật ngôn ngữ mờ. Thứ hai là nghiên cứu thiết kế hiệu quả hệ phân lớp dựa trên luật ngôn
ngữ mờ với ngữ nghĩa tính toán của từ ngôn ngữ được xác định dựa trên ĐSGT dựa trên
kỹ thuật tính toán mềm.
Với các mục tiêu đặt ra của luận án, các đóng góp của luận án là:


Đề xuất mở rộng lý thuyết đại số gia tử biểu diễn lõi ngữ nghĩa của các từ ngôn
ngữ nhằm cung cấp một cơ sở hình thức cho việc sinh tự động ngữ nghĩa tính toán
dựa trên tập mờ có lõi là một khoảng của khung nhận thức ngôn ngữ. Luận án
nghiên cứu trường hợp cụ thể là ngữ nghĩa dựa trên tập mờ hình thang.



Ứng dụng lõi ngữ nghĩa và ngữ nghĩa tính toán dựa trên tập mờ hình thang của
khung nhận thức ngôn ngữ giải bài toán thiết kế tối ưu FLRBC đảm bảo tính giải
1

1.1.4. Luật ngôn ngữ mờ và hệ luật ngôn ngữ mờ
Luật ngôn ngữ mờ hay luật mờ if-then, được gọi tắt là luật mờ, là một phát biểu có
điều kiện dưới dạng if A then B. Phần if của luật được gọi là giả thuyết hay tiền đề luật,
phần then của luật được gọi là phần kết luận.
1.1.5. Bài toán phân lớp dữ liệu
Bài toán phân lớp dữ liệu P được phát biểu như sau: cho một tập dữ liệu mẫu D = {(dp,
Cp), p = 1, …, m}, trong đó m là số mẫu dữ liệu, d p = [dp,1, dp,2, ..., d p,n] là dòng thứ p trong
m mẫu dữ liệu có n thuộc tính, C = {Cs | s = 1, …, M} là một tập gồm M nhãn lớp.
Quá trình xây dựng mô hình phân lớp thường được chia thành hai bước:
Bước 1. Huấn luyện: mô hình phân lớp được xây dựng dựa trên các tập dữ liệu mẫu đã
được gán nhãn, được gọi là các tập dữ liệu huấn luyện.

2


Bước 2. Thử nghiệm mô hình: sử dụng mô hình đã được xây dựng tại bước 1 để phân
lớp tập dữ liệu mới đã được gán nhãn được chọn ngẫu nhiên và độc lập với tập dữ liệu
huấn luyện.
1.2. HỆ DỰA TRÊN TRI THỨC LUẬT NGÔN NGỮ LUẬT MỜ
1.2.1. Cấu trúc của hệ dựa trên luật ngôn ngữ mờ
Hệ dựa trên luật ngôn ngữ mờ bao gồm hai thành phần chính: cơ sở tri thức và hệ suy
luận. Cơ sở tri thức bao gồm cơ sở dữ liệu và cơ sở luật. Cơ sở dữ liệu bao gồm tập các giá
trị ngôn ngữ được dùng trong biểu diễn cơ sở luật và các hàm thuộc biểu diễn ngữ nghĩa
của các giá trị ngôn ngữ. Cơ sở luật là tập hợp các tri thức liên quan đến các bài toán cần
giải quyết dưới dạng các luật mờ if-then.
1.2.2. Bài toán thiết kế hệ phân lớp dựa trên luật ngôn ngữ mờ
Hệ các luật mờ phân lớp bao gồm một tập luật mờ có trọng số dạng:
Luật Rq: if X1 is Aq,1 and ... and Xn is Aq,n then Cq with CFq, với q=1..N

(1.1)


=

∑

∈



∑
∑

∈

(



)

.

(1.3)

.

(1.4)

là độ tương thích hay độ đốt cháy của mẫu dữ liệu dp đối với điều kiện


- Các luật có thể được gán trọng số luật, công thức sau thường được sử dụng:
=

⟹

−

,

,

(1.9)

cq,2nd là độ tin cậy lớn nhất của các luật có cùng điều kiện Aq nhưng khác kết luận khác Cq.
= max

,

⟹

ℎ |ℎ = 1, … ,

;ℎ ≠

,

(1.12)

Hai phương pháp lập luận phân lớp cho một mẫu dữ liệu dp = [dp,1, dp,2, ..., dp,n]:
- Phương pháp lập luận là Single Winner Rule:

chúng; thiếu một cơ sở hình thức hóa toán học trong thiết kế tự động ngữ nghĩa tính toán
dựa trên tập mờ từ ngữ nghĩa vốn có của các từ ngôn ngữ, dẫn đến hệ phân lớp thu được
không là kết quả của sự tương tác giữa ngữ nghĩa của các từ ngôn ngữ với dữ liệu.
- Chưa có cơ chế hình thức đánh giá tính khái quát và tính cụ thể của các từ ngôn ngữ
và bài toán thiết kế các thể hạt (granularity) cho các phân hoạch mờ trên miền các thuộc
tính đảm bảo sự cân bằng giữa tính khái quát và tính cụ thể của các từ ngôn ngữ chưa được
đặt ra.
1.3. Đại số gia tử
1.3.1. Đại số gia tử của biến ngôn ngữ
Định nghĩa 1.4. [50] Giả sử X là một biến ngôn ngữ có miền giá trị là Dom(X). Một ĐSGT
AX tương ứng của X là một bộ 5 thành phần AX = (X, G, C, H, ≤), trong đó: (X, ≤) là cấu
trúc dựa trên quan hệ thứ tự, X là một tập giá trị ngôn ngữ của X với X  Dom(X) và ≤ là
quan hệ thứ tự được cảm sinh bởi ngữ nghĩa vốn có của các từ ngôn ngữ trên X; G = {c-,
c+} là tập các phần tử sinh có quan hệ ngữ nghĩa c- ≤ c+, trong đó c- và c+ tương ứng là
phần tử sinh nguyên thủy âm và dương; C = {0, W, 1} là tập các hằng thỏa quan hệ ngữ
nghĩa 0 ≤ c- ≤ W ≤ c+ ≤ 1, trong đó 0 và 1 tương ứng là phần tử nhỏ nhất và phần tử lớn
nhất trong cấu trúc (X, ≤), W là phần tử trung hòa; H là tập gia tử của biến ngôn ngữ X. □
Với mỗi x  X, ký hiệu H(x) là tập tất cả các giá trị ngôn ngữ u  X được cảm sinh từ
x bởi các gia tử trong H và được biểu diễn bởi chuỗi u = hn…h1x, với hn, …, h 1  H.
Trong trường hợp x  {c-, c+} thì chuỗi u = hn…h1c được gọi là một biểu diễn chính tắc
nếu h j+1…h1c ≠ hj…h1c với mọi j = 1, …, n - 1 và khi đó u có độ dài n + 1, được ký hiệu là
4


|u| hoặc l(u). Ký hiệu sau: Xk là tập tất cả các giá trị ngôn ngữ có độ dài đúng bằng k và X(k)
là tập tất cả các giá trị ngôn ngữ có độ dài nhỏ hơn hoặc bằng k.
Trong ĐSGT AX = (X, G, C, H, ≤) nếu X, G và H là tập sắp thứ tự tuyến tính thì AX
được gọi là ĐSGT tuyến tính. Một số tính chất của ĐSGT:
- Dấu của c+ là sign(c+) = +1, dấu của c- là sign(c-) = -1.
- Tập các gia tử dương là H+ = {hj: 1 ≤ j ≤ p} và có dấu sign(hj) = +1, tập các gia tử là

(FM1) fm là một độ đo đầy đủ trên X, nghĩa là fm(c) + fm(c+) = 1 và, u  X,
 fm(hu)  fm(u) ;

hH

5


(FM2) Nếu H(x) = x, thì fm(x) = 0. Đặc biệt ta có: fm(0) = fm(W) = fm(1) = 0;
(FM3) x, y  X, h  H, ta có fm(hx)/x = fm(hy)/y, nghĩa là tỷ số này không phụ
thuộc vào một phần tử cụ thể nào trong X mà chỉ phụ thuộc vào h được gọi là độ đo tính
mờ của gia tử h và được ký hiệu là (h). □
Công thức tính đệ quy độ đo tính mờ của x = hm...h1c với c  {c-, c+} như sau:
fm(x) = (hm)...(h1) fm(c), trong đó

  ( h)  1 .

(1.17)

hH

Mệnh đề 1.1. [52, 53] Độ đo tính mờ fm của các khái niệm và (h) của các gia tử thỏa:
1)

fm(hx) = (h)fm(x), x  X;

2) fm(c) + fm(c+) = 1;
p

3)

i

i 1

Định nghĩa 1.6. [52, 53] Ngữ nghĩa số của các từ ngôn ngữ hay ánh xạ định lượng ngữ
nghĩa của AX là ánh xạ bảo toàn thứ tự υ: X  [0,1] thỏa mãn các điều kiện sau:
SQM1) υ bảo toàn thứ tự trên X, tức là x < y  υ(x) < υ(y) và υ(0) = 0, υ(1) = 1;
SQM2) υ là song ánh và ảnh của X, υ(X), là trù mật trong đoạn [0, 1] ; □
Mệnh đề 1.2. [52, 53] Ánh xạ định lượng ngữ nghĩa υ được xác định quy nạp như sau:
1) υ(W) =  = fm(c), υ(c) =  - fm(c), υ(c+) =  +fm(c+);
j

2) υ(hjx) = υ(x)+ Sign ( h j x )(  i 1 fm ( hi x )   ( h j x ) fm ( h j x )) , với 1  j  p,
j

và υ(hjx) = υ(x)+ Sign ( h j x )(  i  1 fm ( hi x )   ( h j x ) fm ( h j x )) , với q  j  1.
Hai công thức này có thể viết thành một công thức chung, với j  [-q^p] và j  0 là:
j

 ( h j x )   ( x )  Sign( h j x )(  i  sign ( j ) fm( hi x )   ( h j x ) fm( h j x )) , và
 ( h j x )  1 2 [1  Sign ( h j x ) Sign ( h p h j x )(    )]  { ,  } . □
1.3.3. Ý nghĩa ứng dụng của đại số gia tử
ĐSGT đã được ứng dụng thành công trong các lĩnh vực như điều khiển mờ, hồi quy
và dự báo, thiết kế FLRBC, ... Trong những ứng dụng như vậy, ngữ nghĩa của các từ ngôn
ngữ được sử dụng trong biểu diễn các luật ngôn ngữ mờ cần được biểu thị bằng tập mờ
phù hợp với ngữ nghĩa vốn có của chúng. Với độ đo tính mờ của |H| - 1 gia tử, độ đo tính
mờ của một phần tử sinh (fm(c-) hoặc fm(c+)) và một số nguyên dương k giới hạn độ dài tối
đa của các từ ngôn ngữ được gọi là các tham số ngữ nghĩa, ký hiệu là Л. Khi cho một bộ
giá trị cụ thể của các tham số ngữ nghĩa, các giá trị định lượng của các từ ngôn ngữ được
6

1

lõi

150

200

Hình 2.1. Mối quan hệ giữa từ “nhanh” và “rất nhanh” của biến ngôn ngữ TOCDO và
các giá trị của tập nền U được biểu diễn dưới dạng các tập mờ.
Mọi từ mang ngữ nghĩa không rõ ràng x của một biến ngôn ngữ với miền tham chiếu
số U biểu diễn mối quan hệ của x với các giá trị của U, tức là mọi giá trị số của U phù hợp
với x ở một độ chắc chắn nhất định. Mối quan hệ giữa từ “nhanh” và “rất nhanh” của biến
ngôn ngữ TOCDO và các giá trị của U có thể được biểu diễn dưới dạng các tập mờ như
7


trong Hình 2.1. Ký hiệu Core(x) là lõi ngữ nghĩa của của x thì Core(x) = {u: x(u) = 1} và
ngữ nghĩa của x là tập Sem(x) = {u: x(u)  (0, 1]}. Lõi ngữ nghĩa của hai từ ngôn ngữ bất
kỳ x, y  X và ngữ nghĩa tương ứng của chúng thỏa các điều kiện sau:
(C1) Core(x)  Sem(x);
(C2) Nếu x ≤ y thì Core(x) ≤ Core(y), Core(x) ≤ Sem(y) và Sem(x) ≤ Core(y).
Trong phương pháp hình thức hóa ĐSGT, lõi ngữ nghĩa của từ ngôn ngữ x cần được
sinh từ gia tử nên một gia tử nhân tạo h0 được bổ sung nhằm cảm sinh lõi ngữ nghĩa của x
là h0x. Việc mở rộng một ĐSGT tuyến tính AX được thực hiện như sau.
Định nghĩa 2.1. Mở rộng ngữ cảnh của một ĐSGT tuyến tính và tự do AX = (X, C, G, H,
) là ĐSGT mở rộng AX mr = (Xmr, C, G, Hmr, ), trong đó C cũng là tập các hằng tử của
AX mr, Hmr = HI  {h 0} = H+  H  {I, h 0}, ở đó H = {h-q, …, h-2, h-1}, h-q < ... < h-2 < h-1
và H+ = {h 1, h2 ,... , hp}, h1 < h 2 < ... < hp, nghĩa là HI = H  {I}, Xmr = X  {h0x | x  X}
và ≤ là quan hệ thứ tự mở rộng của X trên Xmr, nếu nó thỏa các tiên đề sau:

∪ {ℎ : ∈ ( ) } được sắp tuyến tính. □



( ) = 1 với ∀ > 0. Với k = 1, ta có (fm1). □

2.3. HỆ KHOẢNG TÍNH MỜ LIÊN KẾT VỚI ĐỘ ĐO TÍNH MỜ
Gọi PI([0, 1]) là tập tất cả các khoảng con của đoạn [0, 1]. Ta luôn luôn quy ước là các
khoảng đều đóng ở đầu mút trái và mở ở đầu mút phải, trừ khi đầu mút phải là giá trị 1. Ta
có khái niệm khoảng tính mờ  của các từ ngôn ngữ của Xmr, (x) với ∈ ( ) =
{ ∈
: | | ≤ } = ( ) ∪ {ℎ : ∈ ( ) }, dựa trên hệ tiên đề của độ đo tính mờ:
Định nghĩa 2.3. Cho một ĐSGT mở rộng AX mr = (Xmr, C, G, Hmr, ) của một ĐSGT tuyến
tính và tự do AX và độ đo tính mờ fm: Xmr  [0, 1] thỏa các tính chất trong Định nghĩa
2.2. Giả sử mỗi từ ngôn ngữ x  ( ) được liên kết với một khoảng trong PI([0, 1]). Các
khoảng này được gọi là các khoảng tính mờ mức k của các từ ngôn ngữ tương ứng của
AX mr và nó được xây dựng quy nạp theo k như sau:
1) Với k = 1, xây dựng các khoảng tính mờ 1(c-), 1(W), 1(c+) với |1(x)| = fm(x),
sao cho chúng có thứ tự tương đồng với thứ tự của các hạng từ c-, W, c+.

9


2) Với k > 1 và xC, xây dựng các khoảng tính mờ k(x) sao cho (i) nếu |x| < k - 1 thì
|k(x)| = |k-1(x)|, (ii) nếu |x| = k - 1 thì |k(x)| = (h0)fm(x), (iii) nếu |x| = k thì |k(x)| =
fm(x), (iv) thứ tự của các khoảng tính mờ tương đồng với thứ tự của các hạng từ x, tức là,
với x, y  {hx: h  Hmr}, nếu x ≤ y thì k(x) ≤ k(y). □
Thuật toán 2.1. Thuật toán xây dựng hệ khoảng tính mờ.
Đầu vào: Các độ đo tính mờ fm(c-), fm(W), (h) với h  Hmr và số k >= 1 xác định độ dài tối đa
của các từ ngôn ngữ. Lưu ý: fm(c+) = 1 - fm(c-) - fm(W).
Đầu ra:  là tập các khoảng với nhãn là các từ ngôn ngữ trong ( ) .
Begin
Khởi tạo j = 1 và tập  bằng rỗng.


thỏa |x| = j < k, ta có k(x) = I(h0x) và |k(x)| = (h0)fm(x). Với x

thỏa |x| = j  k – 2, ta có k(x) = k-1(x).
(3) Tập tất cả các khoảng tính mờ mức k, FI(k) = {k(x), x 

( ) },

có các tính chất:

a- Đối với hạng từ hằng W, ta có k(W) = 1(W);
b- Với mỗi x  H({c,c+}) thỏa |x| = k – 1, tập các khoảng tính mờ {k(hx): h  Hmr}
là một phân hoạch nhị phân của khoảng tính mờ k-1(x) mức k – 1 của x.
10


c- Các khoảng tính mờ trong FI(k) có thứ tự tương đồng với thứ tự của các hạng từ của
chúng và lập thành một phân hoạch nhị phân của đoạn [0,1]. □
2.4. ÁNH XẠ ĐỊNH LƯỢNG NGỮ NGHĨA KHOẢNG
Định nghĩa 2.4. Cho AXmr là ĐSGT mở rộng của AX tuyến tính và tự do, ánh xạ f : Xmr 
PI([0, 1]) được gọi là ánh xạ định lượng ngữ nghĩa khoảng của AXmr nếu nó thỏa các điều
kiện sau:
(IQ1) f bảo toàn thứ tự trên Xmr, tức là nếu x  y thì f(x)  f(y), với x, y  Xmr;
(IQ2) f(Xmr) là tập trù mật trong [0, 1]. □
Định lý 2.5. Cho độ đo tính mờ fm của ĐSGT AXmr và  là tập tất cả các khoảng tính mờ
của các từ ngôn ngữ của AXmr được xác định bởi fm. Khi đó ánh xạ f: Xmr    PI[0, 1]
được định nghĩa như sau là ánh xạ định lượng ngữ nghĩa khoảng:
f(x) = |x|+1(h0x)  PI[0, 1], với x, y  Xmr

(2.5)


( )

(ℎ ) − ( ) × (ℎ )}.
11

1+

ℎ

× (ℎ ) +


2.6. ỨNG DỤNG LÕI NGỮ NGHĨA VÀ NGỮ NGHĨA HÌNH THANG TRONG
THIẾT KẾ HỆ PHÂN LỚP DỰA TRÊN LUẬT NGÔN NGỮ MỜ
Luận án áp dụng phương pháp hai giai đoạn thiết kế FLRBC với ngữ nghĩa tính toán
của các từ được xác định bởi ĐSGT AXmr và AXmrtp, điểm khác biệt so với ĐSGT AX:
1) Thứ nhất, trong bước thiết kế các từ ngôn ngữ cho các thuộc tính của tập dữ liệu
huấn luyện, mỗi thuộc tính được liên kết với một ĐSGT AXmr hoặc AXmrtp thay vì AX. Tập
các từ mức k trong Xk đã bao gồm đầy đủ các hạng từ ngôn ngữ có độ dài nhỏ hơn hoặc
bằng k và tạo thành một phân hoạch trên miền giá trị định lượng chuẩn hóa [0, 1].
2) Thứ hai, ngữ nghĩa tính toán dựa trên tập mờ tam giác của các từ ngôn ngữ trong
biểu diễn cơ sở luật của FLRBC được thay bằng tập mờ hình thang.
2.6.1. Thiết kế ngữ nghĩa tính toán dựa trên tập mờ của các từ ngôn ngữ
Phương pháp luận cho việc thiết kế các từ ngôn ngữ với ngữ nghĩa dựa trên tập mờ có
độ dài tối đa của từ là kj cho bài toán phân lớp dựa trên luật mờ như sau:
+ Mỗi thuộc tính thứ j của tập dữ liệu huấn luyện được liên kết với một ĐSGT AXmrj
hoặc AXmrtpj, cảm sinh tập các từ ,( ) có thứ tự theo ngữ nghĩa định tính của chúng.
+ Ký hiệu
thể, ta có

,

)≤⋯≤ (

,

,

). Giả sử

đặt a = R(f(xj,i-1)), b = L(f(xj,i)), c = R(f(xj,i)), d = L(f(xj,i+1)), ta có công thức tính giá trị hàm
( ) của từ xj,i theo (2.7), trong đó v là một điểm dữ liệu.
thuộc của tập mờ hình thang
,

,

( ) =

⎧
⎪
⎨
⎪
⎩

0vớihoặc < hoặc >
với ≤ <
1với ≤ ≤
với < ≤


tham số ngữ nghĩa Л, NR0 số luật khởi đầu, K giới hạn độ dài của các từ ngôn ngữ, λ giới
hạn độ dài tối đa của luật.
Output: Tập luật khởi đầu S0.
Begin
Bước 1: Xây dựng tập các hạng từ, tập khoảng tính mờ, tập ánh xạ định lượng khoảng
và các tập mờ hình thang của các từ đối với mọi thuộc tính của tập dữ liệu huấn luyện.
Bước 2: Sinh tập luật ứng viên từ tập dữ liệu huấn luyện.
Tập các khoảng tính mờ ℑ (

, ( ))

chứa thành phần dữ liệu dl,j xác định một khối hộp

Hl chứa mẫu dữ liệu dl. Khối hộp Hl cùng với lớp kết luận Cl của p l xác định luật mờ cơ sở
độ dài n có dạng sau:
IF X1 is x1,i(1) AND … AND Xn is xn,i(n) THEN Cl

(Rb)

Phần kết luận của luật là lớp Cq được chọn từ các nhãn lớp có độ tin cậy của luật là lớn
nhất. Từ các luật cơ sở có độ dài n, các luật ứng viên có độ dài nhỏ hơn n được xây dựng
bằng cách bỏ đi một số điều kiện tiền đề Al,j của luật cơ sở.
Bước 3. Chọn lọc tập luật khởi đầu S0 từ tập luật ứng viên sử dụng tiêu chuẩn sàng.
Sắp xếp các luật giảm dần trong mỗi nhóm theo tiêu chuẩn sàng và chọn ra NB0 luật
trong mỗi nhóm từ trên xuống dưới. Trả lại tập luật khởi đầu S0.
End.
13


Sau Bước 3 ta thu được hệ luật khởi đầu S0 có NR0 = NB0 * M luật. Các luật được gán

kế hệ phân lớp dựa trên luật ngôn ngữ mờ
2.6.4.1. Dữ liệu và phương pháp thực nghiệm
Các thực nghiệm được tiến hành đối với 23 tập dữ liệu mẫu UCI được cộng đồng
nghiên cứu thừa nhận bao gồm: Appendicitis, Australian, Bands, Bupa, Cleveland,
Dermatology, Glass, Haberman, Hayes-roth, Heart, Hepatitis, Ionosphere, Iris,
Mammographic, Newthyroid, Pima, Saheart, Sonar, Tae, Vehicle, Wdbc, Wine, Wisconsin.
Phương pháp kiểm tra chéo 10 nhóm (10-fold cross-validation) được sử dụng và được lặp
lại 3 lần đối với một tập dữ liệu được thử nghiệm. Kết quả cuối cùng của các lần thử
nghiệm sau khi lựa chọn được hệ luật tối ưu được tính trung bình đối với số luật #R, độ
phức tạp của hệ luật #C, tỷ lệ phân lớp đúng trên tập huấn luyện Ptr và trên tập kiểm tra
Pte. Độ phức tạp của hệ luật được tính theo công thức #C = #R × Avg, trong đó Avg là độ
dài trung bình của hệ luật.

14


Số thế hệ khi tối ưu các tham số ngữ nghĩa MOPSO_SPO là 250, tìm kiếm hệ luật tối
ưu MOPSO_RBO là 1000. Số cá thể mỗi thế hệ là 600.
Các ràng buộc đối với các tham số ngữ nghĩa như sau: số gia tử âm và gia tử dương
đều được lấy là 1. Giới hạn độ dài của các từ ngôn ngữ 0 < kj ≤ 3. Giá trị của các độ đo
tính mờ: Với ĐSGT AXmr: 0,2 ≤
( ), (Lj) ≤ 0,7; 0,0001 ≤ fm(Wj) ≤ 0,2;
+
= 1; 0,0001 ≤ (h0,j) ≤ 0,5. Với ĐSGT AXmrtp: 0,00001 ≤ fm(0), fm(1)
( )+
( ), (Lj) ≤ 0,7; 0,0001 ≤ fm(Wj) ≤ 0,2;
+

+
≤ 0,01; 0,15 ≤


#C

Ptr

App
Aus
Ban
Bup
Cle
Der
Gla
Hab
Hay
Hea
Hep
Ion
Iri
Mam
New
Pim
Sah
Son
Tae
Veh
Wdb
Win
Wis

16,77

77,60
89,40
89,19
93,68
94,69
98,25
85,49
96,76
78,69
75,51
87,59
68,97
70,74
97,08
99,60
97,78

88,15
87,15
73,46
72,38
62,39
94,40
72,24
77,40
84,17
84,57
89,28
91,56
97,33

216,19
23,08
42,09
59,81

91,30
87,72
76,28
77,54
69,86
96,88
80,26
77,67
89,98
88,07
94,44
94,67
98,35
85,31
96,30
78,53
74,55
86,84
68,36
71,64
97,16
100,0
97,20

88,09

10,20
122,27
122,72
26,16
90,33
26,29
92,25
45,18
60,89
86,75
79,76
261,00
242,79
37,35
35,82
74,36

92,28
88,06
76,17
78,13
72,44
98,03
80,45
76,91
90,11
89,63
95,83
95,35
98,40

Ptr

Pte

87,55
8,84 91,86 87,91 20,89 93,47 87,30
86,38
4,00 85,51 85,51 62,43 89,18 85,65
72,80
57,18 71,36 68,73 104,09 71,18 65,80
68,09 112,59 69,50 63,99 210,91 78,59 67,19
62,19 1132,14 73,11 55,11 1020,66 77,21 58,80
96,07 220,36 99,07 94,12 185,28 99,28 94,48
72,09 408,83 78,65 60,48 534,88 83,68 71,28
75,76
90,55 79,46 71,89 21,13 76,82 71,88
84,17 140,03 90,88 78,03 158,52 90,99 78,88
84,44 109,45 90,19 83,46 164,61 91,87 82,84
88,44
35,34 96,10 90,44 20,29 97,88 88,53
90,22 141,33 95,64 88,62 86,75 96,25 90,79
96,00
27,40 99,11 95,11 18,54 98,30 97,33
84,20 102,46 83,07 81,04 106,74 83,90 80,49
94,42
49,40 96,19 91,78 56,47 98,02 94,60
76,18
95,01 77,80 74,92 57,20 79,06 77,05
69,33
76,24 76,70 71,14 110,84 77,73 70,13

so với phương pháp lập luận weighted vote tương ứng.
2.6.4.4. So sánh các phương pháp thiết kế hệ phân lớp theo tiếp cận ĐSGT
Ký hiệu phương pháp thiết kế FLRBC với ngữ nghĩa tính toán của từ được xác định
dựa trên ĐSGT AX, ĐSGT AXmr và ĐSGT AXmrtp tương ứng là FRBC_AX, FRBC_AXmr và
FRBC_AXmrtp. Theo các kết quả thực nghiệm trong Bảng 2.8, hệ phân lớp FRBC_AXmrtp
cho kết quả phân lớp trên tập kiểm tra cao hơn so với hệ phân lớp FRBC_AX đối với 19
tập dữ liệu và cao hơn so với hệ phân lớp FRBC_AXmr đối với 15 tập dữ liệu trong số 23
tập dữ liệu mẫu được thực nghiệm. Với các kết quả kiểm định thống kê WSR, ta có thể
khẳng định rằng, việc ứng dụng ĐSGT AXmrtp trong thiết kế FLRBC cho hiệu suất phân
lớp tốt hơn so với việc ứng dụng ĐSGT AXmr và ĐSGT AX, ĐSGT AXmr cho hiệu suất
phân lớp tốt hơn ĐSGT AX.
2.6.4.5. So sánh với một số phương pháp theo tiếp cận lý thuyết tập mờ
Các kết quả thực nghiệm của hai hệ phân lớp FRBC_AXmr và FRBC_AXmrtp được so
sánh với một số các kết quả theo tiếp cận lý thuyết tập mờ được công bố gần đây của R.
Alcalá, 2011 và M. Antonelli, 2014.
Trong R. Alcalá, 2011, đã đề xuất kỹ thuật lựa chọn phân hoạch đơn thể hạt từ các
phân hoạch đa thể hạt. Theo kết quả thực nghiệm, có hai kỹ thuật cho kết quả tốt hơn cả là
All Granularities và Product/1-ALL TUN. Các kết quả thực nghiệm, so sánh tương ứng
được thể hiện trong Bảng 2.8. Cả hai hệ phân lớp FRBC_AXmr và FRBC_AXmrtp đều cho
hiệu suất phân lớp trung bình trên tập kiểm tra đối với 23 tập dữ liệu thử nghiệm cao hơn
so nhưng có độ phức tạp của hệ phân lớp thấp hơn so với hai hệ phân lớp All
Granularities và Product/1-ALL TUN. Theo kết quả kiểm định giả thuyết thống kê
WSR, ta có thể khẳng định rằng cả hai hệ phân lớp FRBC_AXmr và FRBC_AXmrtp đều tốt
hơn so với các phương pháp được đề xuất trong R. Alcalá, 2011 về hiệu suất phân lớp
nhưng không tăng độ phức tạp của hệ phân lớp.
Hai hệ phân lớp được đề xuất trong luận án được so sánh với các kết quả được đề xuất
của M. Antonelli, 2014 có tên là PAES-RCS, một tiếp cận khai thác tiến hóa đa mục tiêu
để học đồng thời cơ sở luật và các tham số của các hàm thuộc của FLRBC. Các kết quả
thực nghiệm và so sánh giữa hệ phân lớp PAES-RCS và các hệ phân lớp FRBC_AXmrtp và
FRBC_AXmr được thể hiện trong Bảng 2.13. Hai hệ phân lớp FRBC_AXmrtp và

Hay
Hea
Hep
Ion
Iri
Mam
New
Pim
Sah
Son
Tae
Veh
Wdb
Win
Wis

16,77
46,50
58,20
181,19
468,13
182,84
474,29
10,80
114,66
123,29
25,53
88,03
30,37
73,84

96,78
98,49
96,95

16,91
41,85
78,19
170,70
640,19
189,46
488,38
20,00
139,42
120,69
25,75
83,71
34,59
82,08
30,93
50,33
58,41
53,91
163,61
216,19
23,08
42,09
59,81

TB


90,98 670,63 90,40 372,68
96,67
69,84 95,33
31,95
84,46 132,54 83,37
16,83
95,03
97,75 95,35 100,82
76,66 270,64 74,66 127,50
70,27 525,21 70,92
50,88
77,29 524,60 77,00 309,96
59,46 323,14 60,81
43,00
68,12 555,77 64,89 2125,97
95,96 183,70 95,14 356,12
80,00
98,52 170,94 93,98
96,51 328,02 96,46 521,10
355,23 80,66

281,49

Pte

C4.5
#C

Pte


96,60
60,00 93,82
96,35
462,00 95,60
80,34

6497,82 79,57

Số có chữ đậm thể hiện kết quả tốt nhất trong các phương pháp (trên cùng dòng).

2.6.4.6. So sánh đánh giá với một số tiếp cận khác
Các kết quả được đề xuất trong luận án được so sánh với kết quả của hai phương pháp
thiết kế hệ phân lớp không dựa vào cơ chế tiến hóa là FURIA (Fuzzy Unordered Rules
Induction Algorithm) và C4.5. FURIA là một mở rộng của giải thuật RIPPER với tập luật
không cần thiết phải được sắp xếp. Hệ phân lớp C4.5 là hệ phân lớp dựa trên cây quyết
định khai thác khái niệm entropy thông tin. Các kết quả thực nghiệm và so sánh hai hệ
phân lớp FRBC_AXmrtp và FRBC_AXmr so với hai hệ phân lớp FURIA và C4.5 được thể
hiện trong Bảng 2.13. Cụ thể, hai hệ phân lớp FRBC_AXmrtp và FRBC_AXmr lần lượt có
17 và 18 tập dữ liệu, trong số 23 tập dữ liệu được thực nghiệm, có độ chính xác trên tập
kiểm tra cao hơn so với hệ phân lớp FURIA. Cả hai hệ phân lớp FRBC_AXmrtp và
FRBC_AXmr đều có độ chính xác trên tập kiểm tra cao hơn so với hệ phân lớp C4.5 đối
với 20 trong số 23 tập dữ liệu được thực nghiệm. Các kết quả kiểm định giả thuyết thống
17


kê, ta có thể kết luận rằng cả hai hệ phân lớp FRBC_AXmr và FRBC_AXmrtp thực sự tốt
hơn FURIA và C4.5 cả về hiệu suất phân lớp lẫn độ phức tạp của hệ phân lớp.
2.6.5. Biểu diễn ngữ nghĩa tính toán dựa trên tập mờ hình thang đảm bảo tính giải
nghĩa được của khung nhận thức ngôn ngữ
Đảm bảo tính giải nghĩa được của khung nhận thức ngôn ngữ (LFoC) là đảm bảo ngữ

xác trên tập kiểm tra cao hơn so với hệ phân lớp với cấu trúc đa thể hạt cũ đối với 18 tập
dữ liệu mẫu trong số 23 tập dữ liệu được thử nghiệm. So sánh dựa trên kết quả trung bình
của độ chính xác trên tập kiểm tra đối với 23 tập dữ liệu, hệ phân lớp FRBC_AXmrtp_k0 có
độ chính xác trung bình là 82,94%, cao hơn so với hệ phân lớp FRBC_AXmrtp có độ chính
xác trung bình là 82,67%, trong khi có độ phức tạp trung bình cao hơn không nhiều
(122,61 so với 114,78). Các kết quả kiểm định giả thuyết thống kê WSR cho ta kết luận,
18


phương pháp thiết kế đa thể hạt với mức k = 1 được tách thành hai mức 0 và 1 có ngữ
nghĩa dựa trên tập mờ hình thang của các từ ngôn ngữ thỏa Ràng buộc thứ ba và đảm bảo
tính giải nghĩa được của khung ngôn nhận thức ngôn ngữ và cho độ chính xác phân lớp
cao hơn so với phương pháp thiết kế đa thể hạt không tách mức k = 1.
2.7. KẾT LUẬN CHƯƠNG 2
Chương này trình bày các nghiên cứu phát triển mở rộng lý thuyết ĐSGT biểu diễn lõi
ngữ nghĩa và ngữ nghĩa tính toán dựa trên tập mờ hình thang và ứng dụng trong thiết kế tự
động FLRBC cũng như trình bày các thực nghiệm, đánh giá và so sánh.
CHƯƠNG 3
THIẾT KẾ HIỆU QUẢ HỆ PHÂN LỚP DỰA TRÊN LUẬT NGÔN NGỮ MỜ
SỬ DỤNG KỸ THUẬT TÍNH TOÁN MỀM
Chương này trình bày các thiết kế hiệu quả hệ phân lớp dựa trên luật ngôn ngữ mờ trên
cơ sở đại số gia tử dựa trên kỹ thuật tính toán mềm.
3.1. THIẾT KẾ HIỆU QUẢ HỆ PHÂN LỚP DỰA TRÊN LUẬT NGÔN NGỮ MỜ
SỬ DỤNG CÁC THUẬT TOÁN TỐI ƯU
3.1.1. Đánh giá tính hiệu quả của thuật toán MOPSO so với thuật toán GSA
3.1.1.1. Giải thuật tối ưu bầy đàn đa mục tiêu
- Chia sẻ thích nghi (fitness sharing): Khi một cá thể i đang chia sẻ các nguồn tài
nguyên thì sự thích nghi fi của nó bị giảm bớt tỷ lệ với số cá thể xung quanh nó.
- Tiêu chuẩn tính trội (dominance criterion): Một phương án u được gọi là trội hơn
phương án v nếu phương án u không tồi hơn phương án v đối với tất cả các mục tiêu và

19


trong đó, ω là hệ số inertia, c1 và c2 là các hệ số tăng tốc, veli là giá trị tốc độ liền trước đó, r1
và r2 là các giá trị ngẫu nhiên giữa 0 và 1, pbesti là vị trí tốt nhất được tìm thấy bởi particle,
Лh là particle được đi theo và popi là vị trí hiện tại của particle trong không gian biến.
Bước 3: Vị trí mới của các particlei được tính như sau: pop i = pop i + veli
(3.7)
Bước 4: Các vị trí mới của bầy được đánh giá.
Bước 5: Bộ nhớ lưu trữ Лopt được cập nhật theo tiêu chuẩn tính trội và chia sẻ thích nghi.
Bước 6: Bộ nhớ của từng particle được cập nhật sử dụng tiêu chuẩn tính trội.
Bước 7: Chấm dứt và trả về Лopt nếu đạt số thế hệ Gmax, ngược lại thì trở về Bước 2.

End.
3.1.1.2. Ứng dụng thuật toán MOPSO tối ưu các tham số ngữ nghĩa và tìm kiếm hệ luật
tối ưu
Tối ưu các tham số ngữ nghĩa sử dụng giải thuật MOPSO là MOPSO_SPO.
Thuật toán 3.2. MOPSO_SPO //[CT2] Tối ưu các tham số ngữ nghĩa
Đầu vào: tập dữ liệu mẫu D = {(dp, Cp) | p = 1, …, m}; Các ràng buộc của các tham số tính mờ;
Các tham số: NR0, Npop, Gmax, K, λ; //Npop là kích thước bầy, Gmax là số thế hệ
Đầu ra: Tập các tham số ngữ nghĩa tối ưu Лopt;

Begin
Cụ thể hóa Giải thuật 3.1 với vị trí của mỗi cá thể là một bộ tham số ngữ nghĩa cần tối ưu;
Trả lại tập các giá trị tốt nhất của tập các bộ tham số ngữ nghĩa (gần) tối ưu Лopt;

End.
3.1.1.3. Thực nghiệm so sánh thuật toán MOPSO so với thuật toán GSA
Theo các kết quả thực nghiệm, việc sử dụng giải thuật tối ưu MOPSO trong thiết kế
FLRBC với ngữ nghĩa dựa trên ĐSGT AX cho độ chính xác trên tập kiểm tra cao hơn so

Giải thuật tối ưu đa mục tiêu lai MOPSO-SA
Thuật toán 3.4. MOPSO-SA //[CT6] giải thuật tối ưu bầy đàn mô phỏng tôi luyện
Đầu vào: các tham số: Gmax, Tmax, α, Npop, D.
Đầu ra: Tập các phương án tối ưu Лopt là kết quả của quá trình huấn luyện.

Begin
Bước 1: Khởi tạo t = 0, và sinh ngẫu nhiên n particle của thế hệ ban đầu. Nhiệt độ ban đầu T0
= Tmax, tỷ suất làm lạnh α, số thế hệ Gmax. Các giá trị của các hàm mục tiêu của mỗi particle
đánh giá. Giá trị chia sẻ thích nghi của từng each particle được tính theo công thức (3.4).
Bước 2: Với mỗi i trong bầy đàn.
Bước 2.1: Tính tốc độ của velit 1 của particle i theo công thức (3.6).
Bước 2.2: Tính vị trí mới popit 1 của particle i theo công thức (3.7).
Bước 2.3: Đánh giá các giá trị mục tiêu của particle thứ i.
Bước 2.4: Kiểm tra tiêu chuẩn tính trội giữa vị trí mới popit 1 của particle i và vị trí cũ của nó
tại thế hệ trước đó popit . Nếu vị trí pop it 1 trội hơn vị trí pop it , nghĩa là vị trí mới tốt hơn, thì
vị trí pop it 1 được chấp nhận là vị trí mới của particle i. Ngược lại, tính giá trị RMSR:
RMSR =

1
D

D
t 1
i, j

 ( fitness

 fitnessit, j ) 2

(3.8)

3.1.2.3. Thực nghiệm so sánh giải thuật MOPSO-SA so với giải thuật MOPSO
Theo các kết quả thực nghiệm đối với 23 tập dữ liệu, hệ phân lớp MOPSO-SAAX có
độ chính xác trên tập kiểm tra cao hơn so với hệ phân lớp MOPSOAX đối với 16 trong số
23 tập dữ liệu được thực nghiệm và có độ chính xác bằng nhau đối với 3 tập dữ liệu. Hệ
phân lớp MOPSO-SAAXmrtp có độ chính xác trên tập kiểm tra cao hơn so với hệ phân lớp
MOPSOAXmrtp đối với 17 tập dữ liệu trong số 23 tập dữ liệu được thực nghiệm và có độ
chính xác bằng nhau đối với 1 tập dữ liệu. Qua các kết quả kiểm định WSR, ta có thể kết
luận rằng, việc sử dụng giải thuật tối ưu MOPSO-SA trong thiết kế FLRBC với ngữ nghĩa
dựa trên ĐSGT AX cho độ chính xác phân lớp tốt hơn so với việc sử dụng giải thuật
MOPSO (82,48% so với 81,92%) nhưng không làm tăng độ phức tạp của hệ phân lớp.
Việc sử dụng giải thuật tối ưu MOPSO-SA trong thiết kế FLRBC với ngữ nghĩa dựa trên
ĐSGT AXmrtp không những cho độ chính xác phân lớp tốt hơn (82,94% so với 82,67%) mà
còn cho độ phức tạp trung bình thấp hơn (107,52 so với 114,78) so với việc sử dụng giải
thuật tối ưu MOPSO.
3.2. NÂNG CAO HIỆU QUẢ SINH LUẬT MỜ VỚI NGỮ NGHĨA DỰA TRÊN ĐẠI
SỐ GIA TỬ BẰNG KỸ THUẬT LỰA CHỌN ĐẶC TRƯNG
Với mục tiêu làm giảm số chiều của các tập dữ liệu có số chiều lớn trước khi thực hiện
sinh luật sử dụng ĐSGT, luận án đề xuất ứng dụng kỹ thuật lựa chọn đặc trưng với trọng
số động do Sun X. đề xuất năm 2013 như một bước tiền xử lý bổ sung cho phương pháp
hai bước thiết kế FLRBC trên cơ sở ĐSGT.
3.2.1. Một số khái niệm cơ bản về lý thuyết thông tin
3.2.2. Kỹ thuật lựa chọn đặc trưng sử dụng trọng số động
( ; )

Công thức phân tích tính hợp lý: ( , ) = 2 ×

( )

( )



)

≥ ( ;
;

( ;
( )

(

)

)

)
)

(3.17)
(3.18)
(3.19)

Tỷ lệ phụ thuộc lẫn nhau giữa fi và fj biểu thị tỷ lệ tăng hoặc giảm của tính hợp lý giữa
fi và nhãn lớp bởi có sự tham gia của thuộc tính mới được định nghĩa như sau:
(, )=

( , ),
( , ),

;

= ∪ { }; F = F \ {fj};
For từng thuộc tính ứng viên ∈ do
Tính tỷ lệ phụ thuộc lẫn nhau CR(i, j); ( ) = ( ) × (1 + ( , ));
End; k = k + 1;

End.
Độ phức tạp của giải thuật DWFS là ( × ) như đã được chứng minh bởi Sun X.,
trong đó, n là số thuộc tính gốc và số thuộc tính được lựa chọn.
3.2.3. Ứng dụng giải thuật DWFS trong thiết kế FLRBC trên cơ sở ĐSGT
Phương pháp hai giai đoạn thiết kế FLRBC theo tiếp cận ĐSGT được bổ sung thêm
một giai đoạn tiền xử lý áp dụng giải thuật DWFS. Bước tiền xử lý như sau: Với mỗi tập
dữ liệu cụ thể, các thuộc tính có giá trị liên tục được phân hoạch thành các cụm bằng việc
áp dụng kỹ thuật phân cụm mờ c-means với hàm chỉ số hợp lệ cụm (cluster validity index
function) PBMF để rời rạc hóa dữ liệu và sau đó áp dụng giải thuật DWFS để lựa chọn
một tập con các thuộc tính có tính phân biệt nhất.
3.2.4. Kết quả thực nghiệm và thảo luận
Sau khi áp dụng kỹ thuật lựa chọn đặc trưng, thời gian sinh luật giảm rất nhiều. Chẳng
hạn, thời gian sinh tập luật khởi đầu từ tập dữ liệu Dermatology gốc trong trường hợp độ
dài luật tối đa là 3 hết 07:41:03 hay 27.663 giây, lớn hơn 5.532 lần so với sau khi áp dụng
kỹ thuật lựa chọn đặc trưng lựa chọn ra 7 thuộc tính.
Kết quả thực nghiệm về độ chính xác phân lớp của FLRBC trên cơ sở ĐSGT AX và
ĐSGT AXmrtp đối với tập dữ liệu gốc và các tập dữ liệu đã áp dụng kỹ thuật lựa chọn đặc
trưng trên kết quả trung bình đối với 8 tập dữ liệu được thử nghiệm, độ chính xác và độ
phức tạp trung bình của các hệ phân lớp không có nhiều khác biệt. Các kết quả kiểm định
giả thuyết thống kê cho ta kết luận, việc áp dụng phương pháp lựa chọn đặc trưng như một
bước tiền xử lý trong phương pháp thiết kế FLRBC trên cơ sở ĐSGT không làm giảm chất
lượng của hệ phân lớp. Để giảm thời gian sinh luật từ các tập dữ liệu có số chiều lớn, kỹ
thuật lựa chọn đặc trưng nên được áp dụng như một kỹ thuật tiền xử lý dữ liệu.
3.3. Kết luận chương 3
Chương này trình bày giải pháp nâng cao chất lượng của FLRBC được thiết kế trên cơ