Luận văn Thạc sĩ Khoa học máy tính: Phương pháp trích rút các luật mờ phân lớp dựa trên đại số gia tử và ứng dụng

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

VŨ ĐỨC HẢI

PHƯƠNG PHÁP TRÍCH RÚT CÁC LUẬT MỜ

PHÂN LỚP DỰA TRÊN ĐẠI SỐ GIA TỬ

VÀ ỨNG DỤNG

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Thái Nguyên – 2015

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

VŨ ĐỨC HẢI

PHƯƠNG PHÁP TRÍCH RÚT CÁC LUẬT MỜ

PHÂN LỚP DỰA TRÊN ĐẠI SỐ GIA TỬ

VÀ ỨNG DỤNG

Chuyên ngành: Khoa học máy tính

Mã số: 60 48 0101

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

NGƯỜI HƯỚNG DẪN KHOA HỌC

TS. Dương Thăng Long

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Thái Nguyên – 2015

LỜI NÓI ĐẦU

Trong cuộc sống loài người, ngôn ngữ được hình thành một cách tự nhiên

để giải quyết nhu cầu trao đổi thông tin với nhau. Hơn thế, nó là công cụ để con

người mô tả các sự vật, hiện tượng trong thế giới thực và dựa trên đó để tư duy,

lập luận đưa ra những nhận định, phán quyết nhằm phục vụ cho cuộc sống xã

hội. Ngày nay khoa học và công nghệ đã có những phát triển vượt bậc, nhiều

máy móc thiết bị được tạo ra đã góp phần giải phóng sức lao động của con

người. Trong đó lĩnh vực công nghệ thông tin đã có những đóng góp vô cùng to

lớn cho sự phát triển kinh tế - xã hội nói chung và giúp giải phóng sức lao động

không chỉ là lao động chân tay mà còn cả lao động trí óc của con người nói

riêng. Công nghệ thông tin đã góp phần đưa khả năng tư duy, lập luận và sự

sáng tạo kiểu như bộ não người vào máy móc thiết bị để “thông minh hơn”. Để

thực hiện điều này, rất nhiều nhà khoa học đã và đang nghiên cứu cả về lý

thuyết lẫn ứng dụng, đưa ra các phương pháp, các quy trình nhằm kế thừa, mô

phỏng khả năng của con người vào các thiết bị máy móc. Trước hết, các nhà

khoa học đã phải hình thức hóa toán học các vấn đề ngôn ngữ và xử lý ngôn ngữ

mà con người vẫn làm. Người đi tiên phong trong lĩnh vực này là Lotfi A.

Zadeh, ông đã đề xuất khái niệm mờ từ những khái niệm mơ hồ, không rõ ràng.

Cho đến nay, hệ mờ phân lớp dạng luật (FRBCS) là mô hình được nhiều

tác giả quan tâm nghiên cứu và sử dụng trong khai phá dữ liệu, tìm kiếm tri thức

từ dữ liệu cho bài toán phân lớp. Thế mạnh của mô hình này là có thể cung cấp

được cho người dùng cuối những tri thức dạng luật dễ hiểu , dễ sử dụng đối với

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

con người như là những tri thức của họ . Vớ i viê ̣c sử du ̣ng tâ ̣p mờ và lôgic mờ các nghiên cứu đều tìm kiếm phương pháp xây dựng hệ mờ phân lớp dạng luật

nhằm đa ̣t hai mu ̣c tiêu chính : thứ nhất, hiê ̣u quả phân lớ p củ a hê ̣ càng cao càng tốt; thứ hai, tính phức tạp của hệ đồng thời càng nhỏ càng tốt.

Mô hình xây dựng hệ luật mờ phân lớp dựa trên đại số gia tử được đề xuất với

mục tiêu xây dựng hệ luật mờ để ứng dụng phân lớp cho các mẫu dữ liệu sao

cho hệ luật phải có hiệu quả phân lớp cao, càng đơn giản, dễ hiểu và tường minh

đối với người dùng càng tốt.

Tên đề tài được lựa chọn là “Phương pháp trích rút các luật mờ phân

lớp dựa trên đại số gia tử và ứng dụng”. Nội dung của luận văn được bố cục

thành các phần như sau:

Chương 1. Kiến thức cơ bản về hệ mờ và lập luận xấp xỉ.

Chương 2. Phương pháp trích rút luật mờ phân lớp dựa trên đại số gia tử.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Chương 3. Cài đặt thử nghiệm và đánh giá.

CHƢƠNG 1:

KIẾN THỨC CƠ BẢN VỀ HỆ MỜ VÀ LẬP LUẬN XẤP XỈ

1.1. Khái quát về lập luận xấp xỉ (lập luận mờ)

Từ năm 1965 Zadeh đưa ra lý thuyết tập mờ, logic mờ nhưng phải đến

những thập niên cuối của thế kỷ XX lý thuyết tập mờ, logic mờ mới được đặc

biệt quan tâm nghiên cứu và ứng dụng vào trong lý thuyết điều khiển, hệ thống

và trí tuệ nhân tạo. Tập mờ và logic mờ dựa trên các suy luận của con người về

các thông tin không đầy đủ để hiểu biết và điều khiển hệ thống. Điều khiển mờ

chính là mô phỏng cách xử lý thông tin và điều khiển của con người đối với các

đối tượng, do vậy điều khiển mờ đã giải quyết thành công rất nhiều vấn đề điều

khiển phức tạp trước đây chưa giải quyết được.

1.1.1. Định nghĩa tập mờ

Định nghĩa 1.1: [4] Cho tập vũ trụ U với các phần tử ký hiệu bởi x,

U={x}. Một tập mờ A trên U là tập được đặc trưng bở một hàm (x) mà nó liên

kết mỗi phần tử x U với một số thực trong đoạn [0,1]. Giá trị hàm (x) biểu

diễn mức độ thuộc của x trong A. (x) là một ánh xạ từU vào [0,1] và được gọi

là hàm thuộc của tập mờ A[1].

Hay A được gọi là tập mờ khi và chỉ khi:

A = {(x, (x) x U, (x): U [0,1]} (1)

Trong đó (x) được gọi là hàm thuộc của tập mờ A.

Giá trị hàm (x) càng gần tới 1 thì mức độ thuộc của x trong A càng cao.

Tập mờ là sự mở rộng của khái niệm tập hợp kinh điển. Khi A là tập hợp kinh

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

điển thì A có thể được biểu diễn như sau

A = {(x, (x) x U, (x): U {0,1}} (2)

Khi đó hàm thuộc (x) chỉ nhận hai giá trị 0 và 1.

1.1.2. Số mờ

Định nghĩa 1.2: [4] Tập mờ A trên đường thẳng số thực R là một số mờ,

nếu:

1.A chuẩn hóa, tức là có điểm x’ sao cho (x’) = 1.

2. Ứng với mỗi R, tập mức {x: (x) } là đoạn đóng trên R.

3. (x) là hàm liên tục.

Một số dạng số mờ thường được sử dụng là số mờ dạng tam giác, hình

thang và dạng hàm Gauss.

a. Số mờ dạng tam giác được xác định bởi 3 tham số. Khi đó hàm thuộc

1 

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

của sô mờ tam giác A(a, b, c) cho bởi:

b.Số mờ hình thang A(a, b, c, d) được sác định bởi 4 tham số và hàm

thuộc cho bởi:

c.Số mờ dạng hàm Gauss có hàm thuộc cho bởi:

1 

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Trong đó là số dương được chọn thích hợp.

Khái niệm về phân hoạch mờ (fuzzy partition) cũng là một trong khái

niệm quan trọng trong việc tiếp cận giải quyết bài toán phân lớp.

1.1.3. Định nghĩa phân hoạch mờ

Theo [4] Cho p điểm cố định m1

, , …, là các hàm thuộc tương đó tập gồm p tập mờ A1, A2,…, Ap(với

ứng) định nghĩa trên U được gọi là một phân hoạch mờ của U nếu các điều kiện

sau thỏa mãn, k=1,…,p:

1) (mk) = 1 (mk được gọi là một điểm trong nhân của Ak);

2) Nếu x [mk-1, mk+1], = 0 (trong đó m0 = m1 = a và mp+1 = mp =b);

(x) liên tục 3)

4) (x) đơn điệu tăng trên [mk-1, mk] và đơn điệu giảm trên [mk,mk+1];

5) U, , sao cho (x) > 0 (tất cả mọi điểm trong U đều thuộc một

lớp của phân hoạch này với độ thuộc nào đó khác 0)

1.1.4 Các phép tính trên tập mờ Zadeh

1.1.4.1 Các phép toán tập hợp:

Cho A, B là 2 tập mờ trên cùng tập nền U:

Phép giao (Intersection):

Phép giao của tập A và B là tập mờ C được định nghĩa như sau:

C = A B = {(x, (x))| x U, (x) = min{ (x), (x)}}

Ví dụ:

Cho U = {1, 2, 3, 4, 5} và hai tập mờ A, B như sau:

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

A = {(1,0), (2,1), (3,0.6), (4,0.3), (5,0.2)}

B = {(1,0), (2,0.5), (3,0.7), (4,0.2), (5,0.4)}

Khi đó : C = A B = {(1,0), (2,0.5), (3,0.6), (4,0.2), (5,0.2)}

Phép hợp (Union):

Hợp của hai tập mờ A và B là tập mờ C được định nghĩa như sau:

C = A B = {{(x, (x))| x U, (x) = max{ (x), (x)}}

Ví dụ:

Cho U = {1, 2, 3, 4, 5} và hai tập mờ A, B như sau:

A = {(1,0), (2,1), (3,0.6), (4,0.3), (5,0.2)}

B = {(1,0), (2,0.5), (3,0.7), (4,0.2), (5,0.4)}

Khi đó : C = A B = {(1,0), (2,1), (3,0.7), (4,0.3), (5,0.4)}

Phép bù (Complement):

Bù của hai tập mờ A được định nghĩa như sau:

AC = {(x, (x)) x U, (x) = 1 - (x)}

Lưu ý:

1/ A AC U

2/ A AC 0

3/ (AC)C = A

1.1.4.2 Phép phủ định:

Phủ định (negation) là một trong những phép toán logic cơ bản. Để suy

rộng chúng ta cần tới toán tử v(Not P) xác định giá trị chân lý của Not P đối với

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

mệnh đề P.

Định nghĩa: Hàm n: [0, 1]  [0, 1] không tăng thoả mãn các điều kiện

n(0) = 1, n(1) =0 gọi là hàm phủ định.

Hàm n là phép phủ định mạnh, nếu n giảm chặt và n(n(x)) = x với mỗi x

Ví dụ: n(x) = 1- x, n(x) = 1- x2

1.1.4.3 Phép hội:

Phép hội (vẫn quen gọi là phép AND – conjunction) là một trong những

phép toán cơ bản nhất. Nó cũng là cơ sở để định nghĩa phép giao của hai tập mờ.

Định nghĩa 1.3: [4] Hàm T: [0, 1] x[0, 1]  [0, 1] là một phép hội hay t –

chuẩn (chuẩn tam giác hay t- norm) nếu thoả mãn các điều kiện sau:

1) T(1, x) = x với mọi 0  x  1

2) T có tính giao hoán, tức là T(x, y) = T(y, x) với mọi 0  x, y  1

3) T không giảm theo nghĩa T(x, y)  T(u,v) với mọi x u, y  v

4) T có tính kết hợp : T(x, T(y, z)) = T(T(x, y), z) với mọi 0  x, y  1

Ví dụ về một số t – chuẩn

T(x, y) = min(x, y) ; T ( x, y ) = x.y ; T(x,y) = max(x+y -1, 0)

1.1.4.4 Phép tuyển:

Giống như phép hội, phép tuyển hay toán tử logic OR thông thường cần

thoả mãn các tính chất sau:

Định nghĩa 1.4: [4] Hàm S : [0, 1]x[0, 1]  [0, 1] gọi là phép tuyển hay

là t - đối chuẩn (t – conorm) nếu thoả mãn các tiên đề sau:

1) S(0, x) = x với mọi 0  x  1

2) S có tính giao hoán: S(x, y) = S(y, x) với mọi 0  x, y  1

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

3) S không giảm theo nghĩa s(x, y)  s(u, v) với x  u, y  v

4) S có tính kết hợp S(x, S(y,z)) = S(S(x, y), z) với mọi 0  x, y, z  1

Ví dụ: Một số phép tuyển:

S(x, y) = max(x, y) ; S (x, y) = x+ y – xy ; S(x, y) = min( x+ y -1 , 0), …..

1.1.4.5 Phép kéo theo:

Phép kéo theo là một hàm số I: [0,1]2  [0,1] thoả các điều kiện sau:

1) I(0,y)=1,  y  [0,1]

2) I(x,1)=1,  x  [0,1]

3) 0  x1, x2 1  I(x1,y)  I(x2,y),  y  [0,1]

4) 0  y1, y2 1  I(x,y1)  I(x,y2),  x  [0,1]

5) I(1,0)=0

Cho:T là t-chuẩn; S là t-đối chuẩn; n là phép phủ định mạnh

Phép kéo theo thứ nhất:

Hàm IS(x,y) xác định trên [0, 1]2 bằng biểu thức IS(x,y) =S(n(x),y)

Phép kéo theo thứ hai:

Cho T là t-chuẩn, xác định IT(x,y) =Sup{z | 0  z  1 và T(x,y) 

y},x,y [0,1]

Phép kéo theo thứ ba:

Cho (T, S, n) là bộ 3 De Morgan, T là t-chuẩn, S là t-đối chuẩn, n là phép

phủ định mạnh

Phép kéo theo thứ ba: Hàm ITS(x,y) xác định trên [0, 1]2 bằng biểu thức

ITS(x,y) =S(n(x),T(x,y))

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

1.1.5. Biến ngôn ngữ

Biến ngôn ngữ làm một loại biến mà giá trị của nó không phải là số mà là

từ hay mệnh đề dưới dạng ngôn ngữ tự nhiên. Biến ngôn ngữ được định nghĩa

như sau:

Định nghĩa 1.5 [1]: Biến ngôn ngữ được xác định bởi một bộ 5 thành

phần (X, T(X), U, R, M) trong đó:

X – là tên biến

T(X) – là tập các giá trị ngôn ngữ của biến X

– là không gian tham chiếu hay còn gọi là miền cơ sở của biến X U

– là một số quy tắc cú pháp sinh các giá trị ngôn ngữ trong T(X) R

M – là quy tắc gán ngữ nghĩa biểu thị bằng tập mờ trên U cho các từ

ngôn ngữ trong T(X)

Ví dụ: Cho biến ngôn ngữ: Chiều cao

X = Chiều cao

T(X) = {Rất thấp, Thấp, Hơi Thấp, Bình thường, Hơi cao, Cao, Rất cao}

U = [50,215] – miền đánh giá chiều cao

R = Nếu chiều cao u là X thì Chiều cao có giá trị như sau:

Rất thấp với hàm thuộc (u)

Thấp với hàm thuộc (u)

Hơi thấp với hàm thuộc (u)

Bình thường với hàm thuộc (u)

Hơi cao với hàm thuộc (u)

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Rất cao với hàm thuộc (u)

Một số đặc trưng cơ bản của biến ngôn ngữ:

a)Tính phổ quát: các biến ngôn ngữ khác nhau về các giá trị nguyên thủy

nhưng ý nghĩa về mặt cấu trúc miền giá trị của chúng vẫn được giữ. Nói cách

khác, cấu trúc miền giá trị của hai biếnngôn ngữ cho trước tồn tại một “đẳng

cấu” sai khác nhau bởi giá trị sinh nguyên thủy

b) Tính độc lập ngữ cảnh của giả tử và liên từ như AND, OR…: ngữ nghĩa

của các gia tử và lien từ như AND, OR,… hoàn toàn độc lập với ngữ cảnh, khác

với giá trị nguyên thủy của các biến ngôn ngữ phụ thuộc vào ngữ cảnh. Do đó,

khi tìm kiếm các mô hình cho các gia tử và liên từ như AND, OR… chúng ta

không phải quan tâm đến giá trị nguyên thủy của biến ngôn ngữ đang xét.

Các đặc trưng này cho phép chúng ta sử dụng cùng một tập gia tử và xây

dựng một cấu trúc toán học duy nhất cho miền giá trị của các biến ngôn ngữ

khác nhau.

1.1.6. Suy luận xấp xỉ (suy luận mờ)

Suy luận xấp xỉ hay còn gọi là suy luận mờ, là quá trình suy ra những kết

luận dưới dạng các mệnh đề mờ trong điều kiện các quy tắc, các luật, các dữ liệu

đầu vào cho trước cũng không hoàn toàn xác định. Mỗi luật mờ được biểu diễn

bởi một biểu thức “if – then”, được phát biểu dưới dạng ngôn ngữ tự nhiên thể

hiện sự phụ thuộc nhân quả giữa các biến.

Ví dụ: If chuồn chuồn bay thấp then trời mưa

Trong suy luận mờ, đầu ra thường phụ thuộc vào nhiều yếu tố đầu vào.

Lúc đó ta có thể biểu diễn luật này dưới dạng luật mờ tổng hợp

Gọi x1, x2, …, xn là các biến đầu vào và y là biến đầu ra (thường là các

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

biến ngôn ngữ). Aki là các tập mờ ứng với các luật Rk trên không gian nền Ui có

hàm thuộc ký hiệu là Aki(xi) hoặc Aki(xi). Bk là tập mờ trên không gian nền V có

hàm thuộc Bk(y)= Bk(y).

IF (x1 is Ak1) (x2 is Ak2)  … (xi is Aki)  …  (xn is Akn) THEN y is Bk

Ví dụ:

IF (Ngoại ngữ giỏi)  (Tin học giỏi)  (Chuyên môn vững) THEN (Khả năng

trúng tuyển cao)

Giải bài toán lập luận xấp xỉ theo mô hình (1) là xây dựng một phương

pháp lập luận dựa trên các luật mờ để tính toán đầu ra từ các dữ liệu đầu vào

tương ứng, tức tìm kết quả B của Y khi biết giá trị A1, A2, ..., An tương ứng với

các biến X1, X2, …, Xn. Vì chúng ta đang ở trong môi trường thông tin mờ,

không chắc chắn, nên không có một phương pháp lập luận chính xác và duy

nhất. Mỗi phương pháp sẽ xuất phát từ một quan sát trực quan nào đó.

Theo phương pháp truyền thống, quy tắc modus ponens tổng quát hóa được

áp dụng cho hệ mờ dạng (1) cùng với việc sử dụng các phép toán lôgíc mờ đã

được nhiều tác giả đề cập chi tiết trong [1]. Ở đây chúng ta tóm tắt như sau:

Xét mỗi luật mờ trong (1) là một quan hệ mờ Ri trên miền tích Đề-các U=

U1U2 ... UnV với hàm thuộc được xác định bởi:

(3) Ri = I(Tn(Ai,1, ..., Ai,n), Bi)

trong đó Ai,j, Bi là các hàm thuộc tương ứng với Ai,j, Bi, Tn là phép t-normn-

ngôi và I là phép kéo theo. Kết nhập các luật mờ Ri (i = 1, ..., m) của hệ bằng

phép t-conorm với hàm thuộc R và áp dụng quy tắc suy diễn hợp thành ta có kết

quả:

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

(4)

ở đây  là phép t-norm,  là phép t-conorm và  là min hoặc prod.

Công thức (4) cho thấy phương pháp lập luận này với những cách chọn các

phép t-norm, t-conorm hay kéo theoI dẫn đến những kết quả tính toán tập mờ B

khác nhau. Điều này phù hợp với đặc trưng của lập luận xấp xỉ. Câu hỏi về cách

chọn các phép trên như thế nào để có một phương pháp lập luận tốt nói chung

không có câu trả lời khẳng định mà phụ thuộc vào từng tình huống ứng dụng cụ

thể và được kiểm chứng qua kết quả thực nghiệm.

Mặt khác, hệ luật mờ dạng Sugeno với phần kết luận của các luật là một

mệnh đề kinh điển chứa hằng cá thể sẽ trở thành một trường hợp riêng của dạng

(1) khi chọn đầu ra Bi có hàm thuộc ở dạng đơn tử. Tuy nhiên, luật mờ dạng

Sugeno với ưu điểm có thể thể hiện các hành vi cục bộ của hệ thống được ứng

dụng và không cần giải mờ sau khi lập luận. Đây là những lý do thúc đẩy những

nghiên cứu hơn nữa về các mô hình ứng dụng hệ luật mờ, đặc biệt trường hợp

luật mờ có kết luận chỉ chứa giá trị hằng cá thể sẽ được trình bày tiếp ở những

phần sau.

1.2.Một số vấn đề cơ bản trong Đại số gia tử

1.2.1. Đại số gia tử

Để mô phỏng các quá trình suy luận của con người, lý thuyết đại số gia tử

(ĐSGT) đã cố gắng nhúng tập ngôn ngữ vào một cấu trúc đại số thích hợp và

tìm cách xem chúng như là một đại số để tiên đề hoá sao cho cấu trúc thu được

mô phòng tốt ngữ nghĩa ngôn ngữ.

Giả sử X là một biến ngôn ngữ và miền giá trị của X là Dom(X). Một đại

số gia tử AX tương ứng của X là một bộ 4 thành phần AX = (Dom(X), G, H, ≤)

trong đó G là tập các phần tử sinh, H là tập các gia tử và quan hệ “≤” là quan hệ

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

cảm sinh ngữ nghĩa trên X. Giả thiết trong G có chứa các phần tử hằng 0, 1, W

với ý nghĩa là phần tử bé nhất, phần tử lớn nhất và phần tử trung hòa trong X. Ta

gọi mỗi giá trị ngôn ngữ x ∈ X là một hạng từ trong ĐSGT.

Trong đại số gia tử AX = (Dom(X), C, H, ≤) nếu Dom(X) và C là tập sắp

thứ tự tuyến tính thì AX được gọi là đại số gia tử tuyến tính.Khi được thêm hai

gia tử tới hạn là và với ngữ nghĩa là cận trên đúng và cận dưới đúng của tập

H(x) khi tác động lên x, thì ta được ĐSGT tuyến tính đầy đủ, ký hiệu AX = (X,

G, H, , , ≤).

Khi tác động gia tử h ∈H vào phần tử x ∈X, thì thu được phần tử ký hiệu

hx. Với mỗi x ∈X, ký hiệu H(x) là tập tất cả các hạng từ u ∈X sinh từ x bằng

cách áp dụng các gia tử trong H và viết u = hn…h1x, với hn, …, h1∈H.

Tập H gồm các gia tử dương H+ và gia tử âm H-. Các gia tử dương làm

tăng ngữ nghĩa của một hạng từ mà nó tác động, còn gia tử âm làm giảm ngữ nghĩa của hạng từ. Không mất tính tổng quát, ta luôn giả thiết rằng H- = {h-1< h- 2< ... < h-q} và H+ = {h1< h2< ... < hp}.

Để ý rằng biểu thức hn...h1u được gọi là một biểu diễn chính tắc của một

hạng từ x đối với u nếu x = hn...h1u và hi...h1u ≠ hi-1...h1u với i nguyên và i ≤ n.

Ta gọi độ dài của một hạng từ x là số gia tử trong biểu diễn chính tắc của nó đối

với phần tử sinh cộng thêm 1, ký hiệu l(x).

Ví dụ: Cho biến ngôn ngữ HOT, có G = {0,COLD, W, HOT, 1}, H- = {Possible

HOT, Little HOT

1.2.2. Tính chất của đại số gia tử tuyến tính

a. Tính thứ tự ngữ nghĩa của các hạng từ

Định lý 1.1: [1] Cho tập H- và H+ là các tập sắp thứ tự tuyến tính của

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

ĐSGT AX= (X, G, H, ≤). Khi đó ta có các khẳng định sau:

1. Với mỗi u∈X thì H(u) là tập sắp thứ tự tuyến tính.

2. Nếu X được sinh từ G bởi các gia tử và G là tập sắp thứ tự tuyến tính

thì X cũng là tập sắp thứ tự tuyến tính. Hơn nữa nếu u

nhau, tức là u∉H(v) và v∉H(u), thì H(u) ≤ H(v).

b. So sánh hai hạng từ trong miền ngôn ngữ

Định lý 1.2: [1] Cho x = hn…h1u và y = km…k1u là hai biểu diễn chính tắc

của x và y đối với u. Khi đó tồn tại chỉ số j ≤ min{n, m} + 1 sao cho hj' = kj' với

mọi j' < j (ở đây nếu j = min {n, m} + 1 thì hoặc hjlà toán tử đơn vị I, hj = I, j = n

+ 1 ≤ m hoặc dkj = I, j = m + 1 ≤ n) và

(1)x < y khi và chỉ khi hjxj< kjxj, trong đó xj = hj-1...h1u. (2)x = y khi và chỉ khi m = n và hjxj = kjxj. (3)x và y là không so sánh được với nhau khi và chỉ khi hjxjvà kjxjlà không

so sánh được với nhau.

1.2.3. Vấn đề định lƣợng ngữ nghĩa trong đại số gia tử

Hàm H(x) có thể được sử dụng như là một mô hình biểu thị tính mờ của x

và kích thước tập H(x) được xem như độ đo tính mờ của x, và được định nghĩa

như sau:

Định nghĩa 1.6: [1] AX = (X, G, H, , , ≤) là một ĐSGT tuyến tính đầy đủ.

Ánh xạ fm: X [0,1] được gọi là một độ đo tính mờ của các hạng từ trong X nếu:

(1)fm là đầy đủ, tức là fm(c-) + fm(c+) = 1 và = fm(u), ∀u∈X;

(2)fm(x) = 0, với các x thỏa H(x) = {x}. Đặc biệt, fm(0) = fm(W) = fm (1) = 0;

= , tỷ số này không phụ thuộc vào x và (3)∀x,y ∈ X, h ∈ H,

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

y, vì vậy nó được gọi là độ đo tính mờ của các gia tử và được ký hiệu bởi (h).

Trong định nghĩa trên, điều kiện (1) thể hiện tính đầy đủ của các phần tử

sinh và các gia tử cho việc biểu diễn ngữ nghĩa của miền thực đối với các biến.

Điều kiện (2) thể hiện tính rõ của các hạng từ và điều kiện (3) có thể thể được

chấp nhận vì chúng ta đã chấp nhận giả thiết rằng các gia tử độc lập với ngữ

cảnh, do vậy khi áp dụng một gia tử h lên các hạng từ thì hiệu quả tác động

tương đối làm thay đổi ngữ nghĩa của các hạng từ đó là như nhau.

Hình vẽ sau sẽ minh họa rõ hơn cho khái niệm độ đo tính mờ của biến

ngôn ngữ HOT

Hot

VeryHot

Poss Hot

More Hot

Little Hot

1 W

fm(LLHot)

fm(PVHot)

fm(VVHot)

fm(MLHot)

fm(LVHot)

fm(MHot)

fm(VLHot)

fm(PLHot)

fm(MVHot)

fm(LittleHot)

fm(VeryHot)

fm(PossHot)

fm(Hot)

Hình 1.1: Độ đo tính mờ của biến HOT

Một số tính chất của độ đo tính mờ của các hạng tử và gia tử được thể

hiện qua mệnh đề sau:

Mệnh đề 1.1: [1] Với độ đo tính mờ fm và đã được định nghĩa, ta có:

(1)fm(c-) + fm(c+) = 1 và = fm(x);

(2) , với > 0 và = 1;

(3) = 1, trong đó Xk là tập các hạng từ có độ dài đúng k;

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

(4)fm(hx) = .fm(x). và x X, fm( x) = fm( x) = 0;

(5)Cho fm(c-), fm(c+) và = , {- với ∀h∈H,khi đó với x = hn…h1

,+}, dễ dàng tính được độ do tính mờ của x như sau:

fm(x) = … )fm( )

Để thuận tiện cho việc tính toán và xử lý trong nhiều ứng dụng chúng ta

cần xác định giá trị định lượng của các hạng từ này. Việc định lượng hóa các

khái niệm mờ theo phương pháp tiếp cận của tập mờ được thực hiện qua các

phương pháp khử mờ. Đối với ĐSGT, giá trị định lượng của các hạng từ được

định nghĩa dựa trên cấu trúc thứ tự ngữ nghĩa của miền giá trị của các biến ngôn

ngữ, cụ thể là độ đo tính mờ của các hạng từ và gia tử.

Định nghĩa 1.7:[1] Cho AX = (X, G, H, , , ≤) là một ĐSGT tuyến tính

đầy đủ. Ánh xạ v: X→ [0,1] được gọi là một định lượng ngữ nghĩa của AX nếu:

(1)v là ánh xạ 1-1 từ tập X vào đoạn [0,1] và đảm bảo thứ tự trên X, tức là

x,y X, x

(2)v liên tục: x X, v( x) = infimumv(H(x)) và v( x) = supremumv(H(x))

Điều kiện (1) là bắt buộc tối thiểu đối với bất kỳ phương pháp định lượng

nào, điều kiện (2) đảm bảo tính trù mật của H(G) trong X. Trước hết ta cần phải

định nghĩa về dấu của các hạng từ.

Định nghĩa 1.8: [1] Một hàm dấu Sign: X {-1,0,1} là một ánh xạ được

định nghĩa đệ quy như sau:

(1)Sign(c-) = -1, Sign(c+) = 1;

(2)Sign(hc) = -Sign(c) nếu h âm đối với c; Sign(hc) = Sign(c) nếu h dương

đối với c

(3)Sign(h’hx) = -Sign(hx), nếu h’hx hx và h’ âm đối với h; Sign(h’hx) =

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Sign(hx) nếu h’hx hx và h’ dương đối với h.

(4)Sign(h’hx) = 0, nếu h’hx = hx

Mệnh đề 1.2: Với mọi gia tử h và phần tử x X nếu Sign(hx) = +1 thì

hx>x; nếu Sign(hx) = -1 thì hx

fm(x),

Định nghĩa 1.9:[1] Khoảng tính mờ của các hạng từ x∈X, ký hiệu

là một đoạn con của [0,1], ℑfm(x) ∈ tv([0,1]), nếu nó có độ dài bằng độ đo tính

mờ, |ℑfm(x)| = fm(x), và được xác định bằng qui nạp theo độ dài của x như sau:

(1) Với độ dài của x bằng 1 (l(x)=1), tức là x∈ {c-, c+}, khi đó |ℑfm(c-)| =

fm(c-), |ℑfm(c+)| = fm(c+) và ℑfm(c-) ≤ ℑfm(c+);

(2) Giả sử x có độ dài n (l(x) = n) và khoảng tính mờ ℑfm(x) đã được định

nghĩa với |ℑfm(x)| = fm(x). Khi đó tập các khoảng tính mờ {ℑfm(hjx): -q ≤ j ≤ p

và j ≠ 0} ⊂ Itv([0,1]) được xây dựng sao cho nó là một phân hoạch của ℑfm(x),

và thỏa mãn |ℑfm(hjx)| = fm(hjx) và có thứ tự tuyến tính tương ứng với thứ tự của

q+1x) > ... >ℑfm(hpx) và ngược lại:

v(Hot)

v(PHot)

v(VHot)

v(MHot)

v(LHot)

tập {h-qx, h-q+1x, ..., hpx}, tức là nếu h-qx > h-q+1x > ... > hpx thì ℑfm(h-qx) >fm(h-

ℑ2(PHot)

ℑ2(VHot)

ℑ2(MHot)

ℑ2(LHot)

ℑ3(LVHot) ℑ3(MVHot)

ℑ3(MMHot )

ℑ3(MLHot) ℑ3(LLHot) ℑ3(PPHot) ℑ3(VPHot) ℑ3(MPHot)

ℑ3(VMHot) ℑ3(PVHot) ℑ3(VVHot)

ℑ3(VLHot) ℑ3(PLHot) ℑ3(LPHot) ℑ3(MPHot) ℑ3(LMHot)

Hình 1.2: Khoảng tính mờ của các hạng từ của biến HOT

Mệnh đề 1.3: [1] Cho A X = (X, G, H, ∑, Φ, ≤) là một ĐSGT tuyến tính đầy đủ:

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

(1) Nếu Sign(hpx′) = 1, thì ta có ℑ(h-qx′) ≤ ℑ(h-q+1x′) ≤ ... ≤ ℑ(h-1x′) ≤

ℑ(h1x′) ≤ ℑ(h2x′) ≤ ... ≤ ℑ(hpx′), và nếu Sign(hpx′) = -1, thì ta có ℑ(hpx′) ≤

ℑ(hp-1x′) ≤ ... ≤ ℑ(h1x′) ≤ ℑ(h-1x′) ≤ ℑ(h-2x′) ≤ ... ≤ ℑ(h-qx′);

(2) Tập Ik = {ℑ(x): x ∈ Xk} là một tựa phân hoạch của đoạn [0,1];

(3) Cho một số m, tập {ℑ(y): y = km... k1x, ∀km,... , k1∈ H} là một tựa

phân hoạch của khoảng tính mờ ℑ(x);

(4) Tập Ik = {ℑ(x): x ∈ Xk} “mịn” hơn tập Ik-1 = {ℑ(x): x ∈ Xk-1}, tức là

bất kỳ một khoảng tính mờ trong Ik chắc chắn được chứa bên trong một khoảng

của Ik-1;

(5) Với x < y và l(x) = l(y), thì ℑ(x) ≤ ℑ(y) và ℑ(x) ≠ ℑ(y).

Theo Định nghĩa 1.7 và 1.8, có một mối liên hệ giữa ánh xạ định lượng

ngữnghĩa và khoảng tính mờ của của hạng từ trong một ĐSGT, được thể hiện bằng

địnhlý sau :

Định lý 1.3: [1] Cho A X = (X, G, H, ∑, Φ, ≤) là một ĐSGT tuyến tính đầy

đủ và hàm υ được định nghĩa trong Định nghĩa 1.7. Khi đó υ là một ánh xạ định

lượng ngữ nghĩa và tập các giá trị của υ đối với H(x), viết là υ(H(x)), trù mật

trong đoạn [υ(Φx), υ(∑x)], ∀x ∈ X. Hơn nữa, υ(Φx) = infimum υ(H(x)), υ(∑x)

= supremum υ(H(x)) và fm(x) = υ(∑x) - υ(Φx), và như vậy fm(x) = d(υ(H(x))),

trong đó d(A) là đường kính của A ⊆ [0,1]. Kết quả, υ(H(G)) trù mật trong đoạn

[0,1].

Định lý này cũng khẳng định rằng ĐSGT AX cùng với hàm định lượng

ngữ nghĩa υ có thể ứng dụng trong mọi quá trình thực.

Từ những kết quả trên cho thấy giá trị định lượng ngữ nghĩa υ(x) của

một hạng từ x cũng như khoảng tính mờ ℑ(x), ∀x ∈ X, phụ thuộc đầy đủ vào các tham số mờ gia tử fm(c-), fm(c+), µ(h) ∀h ∈ H.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

1.3. Bài toán phân lớp và phƣơng pháp giải quyết dựa trên hệ mờ dạng luật

1.3.1. Bài toán phân lớp

Trong các bài toán về lĩnh vực khai phá dữ liệu thì bài toán phân lớp là

một trong những bài toán đặc trưng được nhiều tác giả nghiên cứu, với các

phương pháp khác nhau để đạt được hiệu quả phân lớp cao nhất. Trong đó có

phương pháp dựa trên hệ mờ dạng luật (fuzzy rule-base classification systems -

FRBCS), ngoài việc đạt được hiệu quả phân lớp cao phương pháp này còn được

nghiên cứu để đáp ứng cho người dùng một mô hình phân lớp dễ hiểu trực quan,

được người dùng sử dụng như là các tri thức của mình để áp dụng trong thực tế.

Bài toán phân lớp mờ có thể được phát biểu như sau: cho một tập các dữ

liệu mẫu D = {(P, C)}, trong đó P = {pi = (di,1,…,di,n)| i=1,…,N} là tập dữ liệu,

C = {C1,…,Cm} là tập các nhãn của các lớp, pi ∈ U là dữ liệu thứ i với U = U1 ×

... × Un là tích Đề-các của các miền của n thuộc tính X1, ..., Xn tương ứng, m là

số lớp và N là số mẫu dữ liệu, để ý rằng P ⊂ U. Mỗi dữ liệu pi∈ P thuộc một lớp

ci∈ C tương ứng tạo thành từng cặp (pi, ci) ∈ D. Giải bài toán bằng FRBCS

chính là xây dựng một hệ các luật mờ, ký hiệu S, để phân lớp đóng vai trò như

một ánh xạ từ tập dữ liệu vào tập nhãn:

S: U C (1.1)

Như vậy, hệ S phải đạt được các mục tiêu như hiệu quả quả phân lớp cao,

tức là sai số phân lớp cho các dữ liệu ít nhất có thể, số lượng các luật nhỏ cũng

như số điều kiện tham gia trong vế trái mỗi luật ít. Mục tiêu về hiệu quả phân

lớp nhằm đáp ứng tính đúng đắn của của hệ đối với tập dữ liệu mẫu được cho

của bài toán, các luật mờ trong S phải đơn giản và dễ hiểu đối với người dùng.

Khi đó mục tiêu xây dựng hệ luật sao cho:

(1.2) fp(S) → max, fn(S) và fa(S) → min.

trong đó: - fp(S) – hàm đánh giá hiệu quả phân lớp

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

- fn(S) – là số luật

- fa(S) – là độ dài (số điều kiện tham gia)

Tuy nhiên, ta thấy rằng ba mục tiêu xây dựng hệ luật trên không thể đạt

được đồng thời. Khi số luật giảm thì lượng tri thức về bài toán giảm khi đó nguy

cơ phân lớp sai tăng, khi có quá nhiều luật lại gây nhiễu loạn thông tin trong quá

trình phân lớp. Số điều kiện của mỗi luật ảnh hưởng đến tính phổ quát của luật,

cụ thể nếu số điều kiện ít sẽ làm tăng tính phổ quát và ngược lại. Tính phổ quát

dễ làm tăng khả năng dự đoán của luật nhưng nguy cơ gây sai số lớn, khi tính cá

thể tăng làm giảm khả năng dự đoán nhưng lại tăng tính đúng đắn của luật. Vì

vậy, các phương pháp giải quyết bài toán đều phải thỏa hiệp giữa các mục tiêu

để đạt được kết quả cuối cùng.

Dưới dạng tổng quát của hệ mờ dạng luật có n đầu vào thì đầu ra của nó

cũng là một tập mờ, khi đó chúng ta cần giải mờ để xác định nhãn phân lớp cho

mẫu dữ liệu tương ứng. Để đơn giản hơn thì ta sử dụng các luật mờ có phần kết

luận của mỗi luật là một giá trị hằng tương ứng với nhãn của một lớp có dạng

như sau:

(1.3) If x1 is Aq1 and …and xn is Aqn then Class Cq with CFq

trong đó Aqj là giá trị ngôn ngữ của các biến ngôn ngữ tương ứng với các thuộc

tính, Cq là nhãn phân lớp và CFq là trọng số của mỗi luật, q= 1,…, M với M là số

luật, j=1…n. Thông thường CFq [0,1].

Đối với những dữ liệu mẫu của bài toán cho dưới dạng số, tức là U Rn

thì việc xây dựng một hệ luật mờ S gồm hai bước:

Bước 1: Phân hoạch mờ trên miền của các thuộc tính bằng tập các giá trị

ngôn ngữ của các biến ngôn ngữ - Dom(x), mỗi giá trị ngôn ngữ được gán một

hàm thuộc tương ứng.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Bước 2: Xác định các luật mờ từ các phân hoạch ở trên tạo thành hệ S.

Bước 1 thường dựa trên các tập mờ tương ứng với các giá trị ngôn ngữ

trên miền của các thuộc tính. Chúng ta có thể sử dụng phương pháp phân hoạch

dạng lưới (grid-partition) hoặc phân hoạch theo sự phân bố dữ liệu (scatter-

partition).

Ví dụ: Cho bài toán phân lớp với tập mẫu có thuộc tính x1, x2 và hai lớp

{C1, C2} biểu thị bằng chấm tròn và vuông (hình..):

Hình 1.3: Lưới phân hoạch mờ trên miền của hai thuộc tính

Lưới phân hoạch này chia không gian tích Đề-các của các miền của thuộc

tính tạo thành không gian các siêu hộp, ký hiệu Hs, các luật mờ sẽ được hình

thành từ các tổ hợp của các giá trị ngôn ngữ trong không gian phân hoạch tương

ứng với mỗi siêu hộp mà tại đó có hỗ trợ bởi các mẫu dữ liệu.

Trực quan từ ví dụ trong hình 1.3, các hệ luật có thể được chọn như sau:

- Hệ S1 gồm 7 luật mờ sau:

If x1 is Small and x2 is Small then Class C1,

If x1 is Small and x2 is Large then Class C1,

If x1 is Large and x2 is Medium then Class C1,

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

If x1 is Large and x2 is Small then Class C2,

If x1 is Medium and x2 is Small then Class C2,

If x1 is Medium and x2 is Medium then Class C2,

If x1 is Medium and x2 is Large then Class C2.

- Hệ S2 gồm 4 luật mờ sau:

If x1 is Small then Class C1,

If x1 is Large and x2 is Medium then Class C1,

If x1 is Medium then Class C2,

If x1 is Large and x2 is Small then Class C2.

1.3.2. Mô hình hệ mờ dạng luật giải bài toán phân lớp

Luật mờ dạng (1.3) có thể được viết gọn lại như sau:

(1.4) Aq Cq with CFq

Trong đó Aq = (Aq,1,…,Aq,n)

Luật mờ (1.4) được đánh giá qua độ tin cậy c(Aq Cq) kí hiệu cq và độ hỗ

trợ s(Aq Cq) kí hiệu sqbằng các công thức:

(1.5)

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

(1.6)

Để tính mức đốt cháy của mẫu dữ liệu pi đối với điều kiện Aq của luật mờ,

ta áp dụng t-norm dạng tích:

(1.7) (pi) = (di,1). (di,2). … . (di,n).

Để đánh giá trọng số của luật dạng (1.4), một số tác giả đã đề xuất

phương pháp đánh giá trọng số luật như sau:

(1.8) CF1(Aq Cq) = cq’

(1.9) CF2(Aq Cq) = cq – cq,Ave,

(1.10) CF3(Aq Cq) = cq – cq,2nd,

(1.11) CF4(Aq Cq) = cq – cq,Sum

trong đó :

cq,Ave là độ tin cậy trung bình của các luật có cùng điều kiện Aq nhưng kết

luận khác Cq:

(1.12)

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 kết

luận là lớp khác với Cq:

(1.13) cq,2nd = max{c(Aq Cq) | h = 1, …, m; Ch Cq }

cq,Sum là tổng các độ tin cậy của các luật có cùng điều kiện Aq nhưng kết

luận là lớp khác với Cq:

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

(1.14)

Một số kết quả thực nghiệm của một số tác giả cho thấy rằng việc đánh

giá trọng số luật theo CF3 cho kết quả tốt hơn so với đánh giá trọng số luật theo CF1,CF2 và CF4

Với hệ luật mờ S dạng (1.4) ta có thường sử dụng phương pháp chọn luật

có mức đốt cháy lớp nhất đối với dữ liệu để đưa vào và phân lớp tương ứng với

kết luận của luật đó (SWR – single winner rule):

(1.15)

trong đó w là chỉ số tương ứng trọng số luật được chọn, w {1,2,3,4}, hoặc có

thể áp dụng với trọng số đồng nhất bằng 1 cho mọi luật, kí hiệu CF0 = 1.

Trong không gian các siêu hộp Hs của phương pháp sinh luật dựa trên lưới

phân hoạch mờ của các miền thuộc tính, mỗi (Aq,1, …, Aq,n) Hs sẽ dùng để xây

dựng một luật mờ bằng cách đặt điều kiện của luật tương ứng với siêu hộp đó

Aq= (Aq,1, …, Aq,n), phần kết luận được chọn là nhãn phân lớp sao cho luật đạt

độ tin cậy lớn nhất:

(1.16)

Phương pháp sinh luật này sẽ đảm bảo các công thức đánh giá trọng số

của luật theo CF1, CF3 luôn dương.

Ký hiệu S0 là tập tất cả các luật mờ được sinh ra từ không gian Hs, kích

thước tập S0 có khả năng rất lớn, có thể |S0| = |Hs|. Do vậy, mỗi luật trong S0 sẽ

được đánh giá tiêu chuẩn lựa chọn (hay tiêu chuẩn sẵn sàng), kí hiệu là SR:

(1.17) SR1(Aq Cq) = cq’

(1.18) SR2(Aq Cq) = sq,

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

(1.19) SR3(Aq Cq) = cq.sq

Một phương pháp khác được sử dụng là thiết kết các thuật toán tìm kiếm

hệ luật tối ưu dựa trên giải thuật di truyền (GA). Trong đó các luật mờ được mã

hóa bằng các cá thể trong GA bời một trong 2 phương pháp là Michigan hoặc

Pittsburgh mã hóa tập các luật mờ thành một cá thể.

1.4 Kết luận

Chương này đã trình bày một số khái niệm cơ bản về lập luận mờ: khái

niệm về tập mờ, số mờ, khái niệm về biến ngôn ngữ và các phép toán trên tập

mờ. Bên cạnh đó Chương 1 còn trình bày các khái niệm về ĐSGT, các tính chất

của ĐSGT, vấn đề định lượng ngữ nghĩa trong ĐSGT, các khái niệm về khoảng

mờ của các giá trị ngôn ngữ.

Trong chương này còn trình bày về bài toán phân lớp và các phương pháp

tiếp cận giải bài toán của một số tác giả. Từ đó ta thấy các phương pháp này còn

gặp trở ngại vì số luật sinh ra có thể rất lớn đòi hỏi khối lượng tính toán lớn,

hoặc các hàm thuộc của các giá trị ngôn ngữ có thể gần như đồng nhất với nhau

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

khi sử dụng biện pháp điều chỉnh tham số.

CHƢƠNG 2: PHƢƠNG PHÁP TRÍCH RÚT LUẬT MỜ PHÂN LỚP DỰA TRÊN ĐẠI SỐ GIA TỬ

2.1. Phƣơng pháp sinh các từ ngôn ngữ trong Đại số gia tử

2.1.1.Phƣơng pháp sinh tập giá trị ngôn ngữ trong đại số gia tử

Trong [1] đã chứng minh miền ngôn ngữ X = Dom(X) của một biến ngôn

ngữ X có thể được tiên đề hóa và được gọi là đại số gia tử và được ký hiệu là

AX = (X, G, H, ) trong đó G là tập các phần tử sinh, H là tập các gia tử (hedge)

còn “” là quan hệ cảm sinh ngữ nghĩa trên X. Giả thiết trong G có chứa các

phần tử hằng 0, 1, W với ý nghĩa là phần tử bé nhất, phần tử lớn nhất và phần tử

trung hòa (neutral) trong X. Ta gọi mỗi giá trị ngôn ngữ xX là một hạng từ

(term) trong ĐSGT.

Nếu tập X và H là các tập sắp thứ tự tuyến tính, khi đó AX = (X, G, H, )

là ĐSGT tuyến tính. Hơn nữa, nếu được trang bị thêm hai gia tử tới hạn là  và

 với ngữ nghĩa là cận trên đúng và cận dưới đúng của tập H(x) khi tác động lên

x, thì ta được ĐSGT truyến tính đầy đủ, ký hiệu AX = (X, G, H, , , ). Vì

trong luận án chỉ quan tâm đến ĐSGT tuyến tính, kể từ đây nói ĐSGT cũng có

nghĩa là ĐSGT tuyến tính.

Khi tác động gia tử hH vào phần tử xX, thì thu được phần tử ký hiệu

hx. Với mỗi xX, ký hiệu H(x) là tập tất cả các hạng từ uX sinh từ x bằng cách

áp dụng các gia tử trong H và viết u = hn…h1x, với hn, …, h1H.

Tập H gồm các gia tử dương H+ và gia tử âm H-. Các gia tử dương làm

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

tăng ngữ nghĩa của một hạng từ mà nó tác động, còn gia tử âm làm giảm ngữ nghĩa của hạng từ. Không mất tính tổng quát, ta luôn giả thiết rằng H- = {h-1

Để ý rằng biểu thức hn...h1u được gọi là một biểu diễn chính tắc của một

hạng từ x đối với u nếu x = hn...h1u và hi...h1uhi-1...h1u với i nguyên và in. Ta

gọi độ dài của một hạng từ x là số gia tử trong biểu diễn chính tắc của nó đối với

phần tử sinh cộng thêm 1, ký hiệu l(x).

Ví dụ:Cho biến ngôn ngữ BIG, có G = {0, SMALL, W, BIG, 1}, H- = { Possible

VeryBIG, LittleBIG

2.1.2. Sinh hệ khoảng tính mờ

Như chúng ta đã ký hiệu Xk là tập các hạng từ độ dài k trong ĐSGT, Ik =

{ (x) : x Xk} là tập các khoảng tính mờ của các hạng từ trong Xk và là một

phân hoạch của [0,1]. Ta gọi Ik là hệ phân hoạch khoảng tính mờ mức k (hay độ

sâu k). Nếu đặt xk,0 là hạng từ bé nhất trong tập Xk, thì (xk,0) = 0. Theo [1]

Định lý 1.3 và Định nghĩa 1.8, chúng ta có (xk,0) = [(xk,0), (xk,0)] và (x)

= ((x), (x)] cho xXk, xxk,0, trong đó quy ước khoảng tính mờ luôn

đóng ở điểm mút phải. Hơn nữa, nếu ký hiệu k là độ dài lớn nhất của các

khoảng tính mờ trong Ik và  là độ đo tính mờ lớn nhất của các gia tử trong H, thì theo [1] ta có k+1kk1. Do < 1 nên ta luôn tìm được khoảng tính mờ

của x cho dù khoảng cần tìm bé đến mức nào.

Điều này cho phép xây dựng các thuật toán xác định các khoảng tính mờ

của mọi hạng từ trong ĐSGT. Theo [1] xX, {(hx): hH} là một phân

hoạch của khoảng tính mờ (x) và được tính toán bằng thuật toán sau.

Thuật toán 2.1:[1] Tính phân hoạch các khoảng tính mờ độ sâu k+1 của

khoảng tính mờ độ sâu k (k(x)).

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Inputs: xXk, k(x) và (h) h H = {h-q, h-q+1, ..., h-1, h1, h2, ..., hp}

Outputs: {(hx): hH} tập phân hoạch các khoảng tính mờ độ sâu k+1

của k(x) và tương ứng là tập {hx: hH}

Actions:

(Step1) Đặt tập chỉ số J,

J = nếu Sign(hpx)=1, ngược lại

Không xét chỉ số 0, ký hiệu jiJ với i=1,..., p+q.

(Step2) Tính khoảng tính mờ xuất phát,

(hj1x) = (lmp(k(x)), lmp(k(x)+(hj1).|k(x)|],

nếu k(x) là khoảng tính mờ đóng trái thì k(hj1x) cũng đóng trái.

(Step3) Đặt Ik+1(x) = {k+1(hj1x)}.

(Step4) Lặp theo i = 2,..., p+q, để tính khoảng tính mờ tiếp theo

k+1(hjix) = (rmp(k+1(hji-1x)), rmp(k+1(hji-1x) + (hji).|k(x)|].

Return: Tập phân hoạch {k+1(hx) : hH} và tập {hx: hH}.

End.□

Trong đó rmp và lmp là điểm mút phải và điểm mút trái của khoảng tính

mờ. Kết quả tập phân hoạch {k+1(hx) : hH} gồm các khoảng tính mờ độ sâu

k+1 có thứ tự tương ứng với thứ tự ngữ nghĩa các hạng từ sinh bằng cách tác

động các gia tử lên x. Bước 3 của thuật toán 2.1 trên lặp trên các gia tử trong H

theo thứ tự tương ứng với thứ tự ngữ nghĩa của các hạng từ sinh {hx : hH}

(xác định bởi bước 1). Điểm mút trái của khoảng tính mờ tiếp theo chính là điểm

mút phải của khoảng tính mờ trước đó, khoảng tính mờ xuất phát tương ứng với

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

hạng từ có ngữ nghĩa bé nhất được tính trong bước 2.

Dựa trên hệ khoảng tính mờ, miền của mỗi thuộc tính Xj được phân hoạch

bởi một tập hạng từ mức kj, tức Xkj = {... xkjxkjxkj ... } trong ĐSGT AXj.

Mỗi hạng từ xXkj được thiết kế hàm định lượng ngữ nghĩa dựa trên nguyên tắc

càng gần tâm ((xkj) - upsilon) giá trị hàm càng lớn và bằng 1 tại tâm, hàm sẽ

giảm dần về hai phía và không vượt khỏi tâm của hai hạng từ láng giềng (xkj)

và (xkj). Điều này nhằm đảm bảo tính thứ tự ngữ nghĩa của các hạng từ trong

ĐSGT. Có thế thiết kế hàm dạng tam giác hay dạng hình chuông. Tuy nhiên

thực tế để mềm dẻo và dễ dàng trong khi áp dụng, luận văn xây dựng hàm dạng

tam giác (Hình 2.1) với hai tham số L, R để xác định giá trị hàm tại hai điểm

đầu mút của khoảng tính mờ tương ứng (L, R> 0), công thức tính như sau:

, (2.1)

trong đó L và R là hai tham số xác định giá trị hàm x(v) tại điểm mút trái v =

x(v)

R

L

(x)

(x)

(x)

(x)

(x)

(x)

lmp((x)) và điểm mút phải v = rmp((x)) của khoảng tính mờ (x).

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Hình 2.1: Hàm định lượng dạng tam giác của các hạng từ

2.2. Phƣơng pháp định lƣợng ngữ nghĩa trong Đại số gia tử

2.2.1. Định lượng ánh xạ ngữ nghĩa SQM

Trong phần này chúng ta xem xét ba vấn đề cơ bản đó là độ đo tính mờ

của các giá trị ngôn ngữ (hạng từ), phương pháp định lượng ngữ nghĩa và

khoảng tính mờ của các khái niệm mờ.

Tính mờ của các giá trị ngôn ngữ xuất phát từ thực tế rằng một giá trị ngôn

ngữ mang ý nghĩa mô tả cho nhiều sự vật và hiện tượng trong thế giới thực, với

lý do tập hữu hạn các giá trị ngôn ngữ không đủ để phản ánh thế giới vô hạn các

sự vật hiện tượng. Như vậy khái niệm tính mờ và độ đo tính mờ của một giá trị

ngôn ngữ được hình thành và nó là một khái niệm rất khó xác định, đặc biệt

trong lý thuyết tập mờ. Tuy nhiên, trong ĐSGT các tác giả đã cho thấy độ đo

tính mờ được xác định một cách hợp lý: “tính mờ của một hạng từ x được hiểu

như là ngữ nghĩa của nó vẫn có thể được thay đổi khi tác động vào nó bằng các

gia tử”. Do đó, tập các hạng từ sinh từ x bằng các gia tử sẽ thể hiện cho tính mờ

của x và do đó, H(x) có thể sử dụng như là một mô hình biểu thị tính mờ của x

và kích thước tập H(x) được xem như độ đo tính mờ của x. Ta có định nghĩa sau

về độ đo tính mờ.

Định nghĩa 2.2:[1] Cho AX = (X, G, H, , , ) là một ĐSGT tuyến tính

đầy đủ. Ánh xạ fm : X [0,1] được gọi là một đo tính mờ của các hạng từ trong

X nếu:

(1) fm là đầy đủ, tức là fm(c-) + fm(c+) =1 và hHfm(hu) = fm(u), uX;

(2) fm(x) = 0, với các x thỏa H(x) = {x}. Đặc biệt, fm(0) = fm(W) = fm(1) = 0;

(3) x,y X, h H, , tỷ số này không phụ thuộc vào x và y, vì

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

vậy nó được gọi là độ đo tính mờ của các gia tử và được ký hiệu bởi (h).

Trong đó, điều kiện (1) thể hiện tính đầy đủ của các phần tử sinh và các gia

tử cho việc biểu diễn ngữ nghĩa của miền thực đối với các biến. (2) thể hiện tính

rõ của các hạng từ và (3) có thể được chấp nhận vì chúng ta đã chấp nhận giả

thiết rằng các gia tử là độc lập với ngữ cảnh và, do vậy, khi áp dụng một gia tử h

lên các hạng từ thì hiệu quả tác động tương đối làm thay đổi ngữ nghĩa của các

hạng từ đó là như nhau.

Thông thường, ngữ nghĩa của các hạng từ thuần túy mang tính định tính.

Tuy nhiên, trong nhiều ứng dụng, chúng ta cần giá trị định lượng của các hạng

từ này cho việc tính toán và xử lý. Theo tiếp cận của tập mờ, việc định lượng

hóa các khái niệm mờ được thực hiện qua các phương pháp khử mờ

(defuzzification). Đối với ĐSGT, giá trị định lượng của các hạng từ được định

nghĩa dựa trên cấu trúc thứ tự ngữ nghĩa của miền giá trị của các biến ngôn ngữ,

cụ thể là độ đo tính mờ của các hạng từ và gia tử. Tuy có nhiều phương pháp xác

định giá trị định lượng của các hạng từ dựa trên các tham số này nhưng phải

thỏa mãn một số ràng buộc nhất định và được thể hiện trong định nghĩa sau.

Định nghĩa 2.3:[1] Cho AX = (X, G, H, , , ) là một ĐSGT tuyến tính

đầy đủ. Ánh xạ  : X [0,1] được gọi là một hàm định lượng ngữ nghĩa (SQM)

của AX nếu:

(1)  là ánh xạ 1-1 từ tập X vào đoạn [0,1] và đảm bảo thứ tự trên X, tức là

x,yX, x

(2)  liên tục: xX, (x) = infimum (H(x)) và (x) =

supremum(H(x)).

Điều kiện (1) là bắt buộc tối thiểu đối với bất kỳ phương pháp định lượng

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

nào, còn điều kiện (2) đảm bảo tính trù mật của H(G) trong X. Dựa trên những

ràng buộc này, các tác giả đã xây dựng một phương pháp định lượng ngữ nghĩa

của các hạng từ trong ĐSGT.

2.2.2. Xây dựng hàm định lượng ngữ nghĩa cho các giá trị ngôn ngữ

Đối với việc áp dụng ĐSGT trong hệ luật mờ phân lớp, ngoài việc thiết kế

các giá trị ngôn ngữ và ngữ nghĩa của chúng cho từng bài toán dựa trên việc tìm

kiếm tố i ưu các tham số mờ ngữ nghĩa , nhằm đảm bảo các mu ̣c tiêu củ a hê ̣ luâ ̣t , các giá trị ngôn ngữ biểu diễn khái niệm mờ sẽ được thiết kế hàm định lượng

t kế da ̣ng

ngữ nghĩa mà nó biểu diễn . Rõ ràng, vớ i tâ ̣p mờ chú ng ta có các thiế tam giác, dạng hình chuông, hình thang,… và ở đây mỗi trườ ng hơ ̣p thiết kế cho giá trị ngôn ngữ sẽ cho kết quả ảnh hưởng đến hiệu quả của hệ luâ ̣t phân lớ p. Sử dụng hệ khoảng tương tự của giá trị ngôn ngữ để t hiết kế dựa trên nguyên tắc

tâm (giá trị định lượng - SQM) của hai giá trị ngôn ngữ liền kề trong thứ tự ngữ

nghĩa làm giới hạn thiết kế của hàm định lượng ngữ nghĩa cho giá trị ngôn ngữ

đó và càng gần về tâm củ a nó t hì giá trị hàm càng lớn , đa ̣t đỉnh bằng 1 tại tâm của chính nó. Hình vẽ 2.2 minh ho ̣a cho thiết kế này ở mứ c phân hoa ̣ch kj. Công thứ c tính cho da ̣ng hàm đi ̣nh lươ ̣ng theo thiết kế này:

, (10)

trong đó  là giá trị định lượng (SQM) hay tâm củ a giá tri ̣ ngôn ngữ.

X(kj)

0

1

(xj,i-1)

(xj,i+1)

T(xj,i+1)

T(xj,i-1)

T(1)

T(0)

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

(xj,i) T(xj,i) Hình 2.2: Thiết kế hà m đi ̣nh lượng dựa trên hê ̣ khoảng tính mờ

Trong thiết kế trên , mỗi giá tri ̣ ngôn ngữ đều thỏa mãn tiêu chuẩn hàm đi ̣nh lươ ̣ng ngữ nghĩa đa ̣t đỉnh ta ̣i tâm củ a nó và đảm bảo tính chất phân hoa ̣ch mờ cho mỗi mứ c phân hoa ̣ch k j. Tuy nhiên, đối vớ i các giá tri ̣ ngôn ngữ mứ c thấp như c- hay c+ có hàm định lượng với độ phổ quát nhỏ tương tự với các giá

trị ngôn ngữ m ức cao, trong khi tính mờ củ a chú ng la ̣i lớ n hơn các giá tri ̣ ngôn ngữ mứ c cao . Điều này chưa thâ ̣t phù hơ ̣p vớ i tính mờ củ a chú ng . Hình vẽ 2.3 minh ho ̣a cho ha ̣n chế này củ a giá tri ̣ ngôn ngữ c+ vớ i mứ c phân hoa ̣ch kj = 3.

Hình 2.3: So sá nh giữa thiết kế dựa trên hê ̣ khoảng tương tự và khoảng tính mờ

Mô ̣t cải tiến đó là áp du ̣ng mứ c khoảng tính mờ củ a chính bản thân các

giá trị ngôn ngữ. Mỗi giá tri ̣ ngôn ngữ ta ̣i hê ̣ khoảng tính mờ mứ c k chú ng ta lấy tâm củ a hai giá tri ̣ ngôn ngữ liên kề trong thứ tự ngữ nghĩa làm giớ i ha ̣n củ a thiết kế hàm đi ̣nh lươ ̣ng ngữ nghĩa cho giá tri ̣ ngôn ngữ đó . Vớ i hai giá tri ̣ 0, 1 trong đa ̣i số gia tử mang ngữ nghĩa bé nhất và lớ n nhất , chúng ta thiết kế hàm đi ̣nh lươ ̣ng củ a chú ng theo từ ng mứ c . Tại mỗi mức khoảng tính mờ k (1,2,3…) chúng ta đặt mức giới hạn của thiết kế hàm định lượng là tâm của giá trị ngôn

ngữ liền kề vớ i nó . Hình vẽ 2.4 a, b, c minh ho ̣a trườ ng hơ ̣p thiết kế này vớ i mứ c

phân hoa ̣ch kj = 3.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

(c)

(b)

(a)

Hình 2.4: Thiết kế hà m đi ̣nh lượng tam giá c dựa trên khoảng tính mờ ở các mức 1,2,3

Như vâ ̣y, mỗi tâ ̣p giá tri ̣ ngôn ngữ ở mô ̣t mứ c k trong phân hoa ̣ch k j (1  k

 kj) có các hàm định lượng ngữ nghĩa tương ứng là một phân hoạch mờ trên

miền đi ̣nh lươ ̣ng . Rõ ràng, thiết kế này đảm bảo tính thứ tự ngữ nghĩa củ a các giá trị ngôn ngữ trong ĐSGT.

Trong thiết kế này , mỗi luâ ̣t sinh bở i thuâ ̣t toán IFRG trên nếu có chứ a

mô ̣t trong hai giá tri ̣ 0, 1 thì thay luật đó bằng cách nhân nó lên k j lần tương ứ ng vớ i mứ c các mứ c khoảng tính mờ 0k hay 1k (k=1,2,…,kj). Chẳng ha ̣n vớ i k j =3,

nếu luâ ̣t sinh có da ̣ng (0, DC, Vc-, VLc+)  class1 thì thay nó bằng 3 luâ ̣t sau

(01, DC, Vc-, VLc+)  class1,1, (02, DC, Vc-, VLc+)  class1,2, (03, DC, Vc-,

VLc+)  class1,3. Các lớp trong vế phải mỗi luật class 1,i (i=1,2,3) đươ ̣c xác

đi ̣nh theo.

Ngoài ra, chúng ta có thể áp dụng hàm định lượng ngữ nghĩa dạng hình

chuông (thay đổi từ công thức (10)) với đỉnh cũng tại tâm của giá trị ngôn ngữ

(giá trị định lượng (.)) và chân là đỉnh của hai giá trị ngôn ngữ liền kề (hình

vẽ).

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

kj = 1 (a)

kj = 2 (b)

kj = 3 (c)

2.3. Xây dựng hệ mờ dạng luật phân lớp dựa trên Đại số gia tử

Áp dụng lược đồ đã trình bày ở trên để xây dựng một hệ luật mờ phân lớp,

ta gọi hệ này là hệ luật khởi đầu. Trong phần này, dựa trên lưới phân hoạch hệ

các khoảng tính mờ Ik, chúng ta sẽ thiết kế thuật toán sinh hệ luật mờ như sau.

Thuật toán 2.2:[1] Sinh các luật mờ từ tập dữ liệu mẫu dựa trên hệ phân

hoạch các khoảng tính mờ (Initial Fuzzy Rules Generation - IFRG1).

Inputs:

- Tập dữ liệu mẫu D = { (pi; ci) | i=1, ..., N }, pi = (di,1, ..., di,n) P, ciC

= {C1, ..., Cm}, n là số thuộc tính, m là số lớp, N là số mẫu dữ liệu;

- Bộ các tham số mờ gia tử của ĐSGT cho mỗi thuộc tính PARj = {

fmj(c-), fmj(c+), j(h) hH }, j = 1, ..., n;

- Mức phân hoạch kj các khoảng tính mờ trên miền của các thuộc tính;

Outputs: Tập các luật mờ S0 = {R1, ..., RM}

Actions:

(Step1) Khởi tạo tập luật S0 = ,

(Step2) Tính phân hoạch các khoảng tính mờ trên miền các thuộc tính Xj

theo tham số mờ gia tử PARj và mức phân hoạch kj,

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Ikj = {kj(xkj,1), kj(xkj,2), ... }, Xkj = {xkj,1, xkj,2, ... }, j = 1, 2, ..., n.

(Step3) Lặp trên mỗi mẫu dữ liệu (pi; ci) D, thực hiện:

(Step3.a) Xác định giá trị ngôn ngữ có khoảng tính mờ chứa di,jpi,

{ Ai,j = xkj,i* | xkj,i*Xkj và di,jkj(xkj,i*), j = 1, 2, ..., n }

(Step3.b) Tạo một truyển vế trái gồm n giá trị ngôn ngữ trên

Aq = (Ai,1, Ai,2, ..., Ai,n),

(Step3.c) Sinh luật mới theo Aq và thêm vào tập luật S0,

S0 = S0{AqCq},

. trong đó

Return: Tập S0.

End.□

Ví dụ: sinh luật dựa trên hệ khoảng tính mờ

Cho bài toán phân lớp với tập mẫu có thuộc tính x1, x2 và hai lớp {C1, C2},

bao gồm 10 mẫu dữ liệu được cho trong bảng sau:

X1 X2 Class

0.2 0.29 C1

0.37 0.18 C1

0.25 0.87 C1

0.78 0.65 C1

0.81 0.23 C2

0.56 0.62 C2

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

0.57 0.83 C2

0.24 0.43 C2

0.37 0.64 C2

0.82 0.31 C2

Ta ký hiệu đại số gia tử cho thuộc tính x1, x2 đều có cấu trúc như sau: c- = short, c+ = long, H = {L, V}. Các tham số mờ gia tử đều cho giống nhau: fmj(c-) = fmj(c+) = 0.5, µj(L) = µj(V) = 0.5 và mức phân hoạch kj = 2 đối với cả hai thuộc

tính x1, x2. Tính toán hệ phân hoạch các khoảng tính mờ trên miền của hai thuộc

tính x1 và x2 chúng ta có lưới phân hoạch trong Hình 2.5.

Hình 2.5: Sơ đồ phân hoạch trên miền thuộc tính x1, x2

Sử dụng thuật toán sinh luật IFRG1 theo các bước sau:

Bước 1: Xác định đầu vào của bài toán

- Gồm 2 thuộc tính x1, x2

- Gồm 2 lớp C1, C2

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

- Gồm 10 mẫu dữ liệu

- Các tham số mờ gia tử: : fmj(c-) = fmj(c+) = 0.5, µj(L) = µj(V)

= 0.5 và mức phân hoạch kj = 2 đối với cả hai thuộc tính x1, x2.

Bước 2: Tính hệ khoảng tính mờ

+ Thuộc tính x1 với mức phân hoạch kj = 2

Hệ khoảng tính mờ của thuộc tính CT:

ℑCT(Vc-) =[0, 0.25)

ℑCT(Lc-) =[0.25, 0.5)

ℑCT(Lc+) =[0.5, 0.75)

ℑCT(Vc+) =[0.75, 1]

Hàm định lượng ngữ nghĩa của thuộc tính x1:

Giá trị tâm của các hạng từ

(VSmall) = 0.125

(LSmall) = 0.375

(LLarge) = 0.625

0.2

0.6

0.8

0.4

ℑx1(Vc+)

ℑx1(Vc-)

ℑx1(Lc-)

ℑx1(Lc+)

+ Thuộc tính x2 với mức phân hoạch kj = 2

(VLarge) = 0.875

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Hệ khoảng tính mờ của thuộc tính x2:

ℑCT(Vc-) =[0, 0.25)

ℑCT(Lc-) =[0.25, 0.5)

ℑCT(Lc+) =[0.5, 0.75)

ℑCT(Vc+) =[0.75, 1]

Hàm định lượng ngữ nghĩa của thuộc tính x2:

Giá trị tâm của các hạng từ

(Vc-) = 0.125

(Lc-) = 0.375

(Lc+) = 0.625

0.2

0.6

0.8

0.4

(Vc+) = 0.875

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

ℑx2(Vc+) ℑx2(Vc-) ℑx2(Lc-) ℑx2(Lc+)

+Bước 3: Sinh luật

Sinh tuyển vế trái:

L1: Ifx1 is V.short and x2 is L.short

L2: Ifx1 is L.short and x2 is V.short

L3: Ifx1 is V.short and x2 is V.long

L4: Ifx1 is V.long and x2 is L.long

L5: Ifx1 is V.long and x2 is V.short

L6: Ifx1 is L.long and x2 is L.long

L7: Ifx1 is L.long and x2 is V.long

L8: Ifx1 is L.long and x2 is L.short

L9: Ifx1 is L.short and x2 is V.long

Tính độ tin cậy của các tuyển luật:

+ Với L1: Ifx1 is V.short and x2 is L.short

X1 X2 Class Mức kích hoạt vế trái Tổng mức đốt cháy theo lớp

0.2 0.29 C1 0.21

0.37 0.18 C1 0.0196 0.4796 0.25 0.87 C1 0.25

0.78 0.65 C1 0

0.81 0.23 C2 0

0.56 0.62 C2 0 0.1924 0.57 0.83 C2 0

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

0.43 0.24 C2 0

0 0.64 0.37 C2

0.1924 0.31 0.82 C2

Tổng 0.672

Độ tin cậy c và độ hỗ trợ s của tuyển vế trái L1 với kết luận là lớp C1:

c = 0.71369, s = 0.04796

Độ tin cậy c và độ hỗ trợ s của tuyển vế trái L1 với kết luận là lớp C2:

c = 0.28631, s = 0.01924

Kết luận: Vậy kết luận vế phải của luật 1 là C1

Ifx1 is V.short and x2 is L.shortthen Class C1

Tương tự với các tuyển vế trái từ L2  L9.

Khi đó thuật toán sinh luật IFRG1cho ra được 9 luật, bao gồm:

R1 Ifx1 is V.short and x2 is L.shortthen Class C1

(c = 1, s = 0.0256)

R2 Ifx1 is L.short and x2 is V.shortthen Class C1

(c = 0.6784, s = 0.0819)

R3 Ifx1 is V.short and x2 is V.longthen Class C1

(c = 0.6034, s = 0.0658)

R4 Ifx1 is V.long and x2 is L.longthen Class C1

(c = 0.7955, s = 0.0597)

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

R5 Ifx1 is V.long and x2 is V.shortthen Class C2

(c = 1, s = 0.0724)

R6 Ifx1 is L.long and x2 is L.long then Class C2

(c = 1, s = 0.0461)

R7 Ifx1 is L.long and x2 is V.longthen Class C2

(c = 1, s = 0.0646)

R8 Ifx1 is L.long and x2 is L.shortthen Class C2

(c = 1, s = 0.0845)

R9 Ifx1 is L.short and x2 is V.longthen Class C2

(c = 1, s = 0.0409)

Kết quả phân lớp đạt 80%, tỉ lệ phân lớp sai là 2/10 mẫu dữ liệu.

2.4. Kết luận Chƣơng 2

Trong chương này đề cập đến các nội dung như phương pháp sinh các từ

ngôn ngữ trong ĐSGT, hàm định lượng ngữ nghĩa và tiếp cận, xây dựng thuật

toán sinh các luật mờ từ tập dữ liệu mẫu dựa trên hệ phân hoạch các khoảng tính

mờ IFRG1. Với mục tiêu xây dựng hệ luật đơn giản, dễ hiểu và đạt hiệu quả cao

cho bài toán phân lớp, từ đó tiến hành thử nghiệm như trong ví dụ nêu trên và

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

cho kết quả khả quan.

CHƢƠNG 3: CÀI ĐẶT THỬ NGHIỆM VÀ ĐÁNH GIÁ

Xây dựng hệ luật mờ phân lớp dựa trên ĐSGT với mục đích để ứng dụng

phân lớp cho các mẫu dữ liệu sao cho hệ luật có hiệu quả phân lớp cao, đơn

giản, dễ hiểu và tường minh. Trong chương này, sẽ thực hiện một số ví dụ để

minh họa cho phương pháp đã nêu Chương 2. Các bài toán với tập dữ liệu mẫu

được xây dựng bởi nhiều nhà khoa học và công bố công khai tại [7] của Đại học

California - Irvine. Các bài toán ở đây chủ yếu về lĩnh vực khai phá dữ liệu như

phân lớp, phân cụm.

Đối với các phương pháp không tất định, tức các lần chạy sẽ cho ra những

kết quả khác nhau do các yếu tố ngẫu nhiên tham gia vào quá trình thực hiện

phương pháp, do đó người ta thường thử nghiệm bằng phương pháp k-cross-

validation. Trong đó, chia ngẫu nhiên tập dữ liệu mẫu của bài toán thành k phần

bằng nhau, sử dụng một phần để thẩm định (test) mô hình còn lại (k-1) phần để

sinh hệ luật (Train). Phương pháp thử nghiệm này nhằm khắc phục nhược điểm

của các mô hình, đó là hiện tượng quá khớp, tức là mô hình sẽ làm việc tốt đối

với tập dữ liệu mẫu dùng để xây dựng trong khi cho kết quả rất tồi đối với các

mẫu dữ liệu mới. Phương pháp thử nghiệm này sẽ được lặp lại k lần, mỗi lần lấy

ra lần lượt một phần trong số k phần để kiểm tra.

Ngoài ra, phương pháp thử nghiệm lấy một mẫu dữ liệu ra để kiểm tra,

còn lại các mẫu dùng để xây dựng mô hình, ký hiệu LV1. Phương pháp này sẽ

được lặp lại theo lần lượt mỗi mẫu được lấy ra để kiểm tra, như vậy số lần lặp để

thử nghiệm đúng bằng số mẫu. Tuy nhiên phương pháp LV1 sẽ phải lặp lại rất

nhiều lần nếu tập dữ liệu mẫu có kích thước lớn, do đó chúng ta sẽ không áp

dụng cho những bài toán có tập dữ liệu mẫu lớn.

Một số thử nghiệm mô hình đối với 2 bài toán:

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

(1) Bài toán phân loại vị trí protein bằng vi khuẩn Ecoli.

(2) Bài toán phân lớp đánh giá trợ giảng.

3.1. Bài toán phân loại vị trí protein bằng vi khuẩn Ecoli

Ứng dụng được xây dựng bằng ngôn ngữ java, bao gồm các bước thực hiện

thuật toán sinh hệ luật mờ: Đọc tệp dữ liệu  thay đổi tham số mờ gia tử đầu vào

cho các thuộc tính  Sinh hệ luật mờ  kiểm tra tỉ lệ phân lớp của hệ luật.

Bài toán phân loại vị trí protein bằng cách sử dụng một số chỉ số của tế

bào ở vi khuẩn Ecoli được tạo bởi Kenta Nakai tại Viện Sinh học phân tử và tế

bào, thuộc đại học Osaka, Nhật Bản. Bài toán gồm 7 thuộc tính bao gồm:

(1) MCG:McGeoch's method for signal sequence recognition. (Phương

pháp McGeoch để nhận biết chuỗi tín hiệu)

(2) GVH: Von Heijne's method for signal sequence recognition.

(Phương pháp von Heijne để nhận biết chuỗi tín hiệu)

(3) LIP: Von Heijne's Signal Peptidase II consensus sequence score. Binary attribute.(Chỉ số chuỗi đồng thuận tín hiệu Peptidase II của von Heijne. Thuộc tính nhị phân)

(4) CHG: Presence of charge on N-terminus of predicted lipoproteins. Binary attribute. (Thể hiện của chất tải trên phần cuối N của lipoproteins được dự đoán. Thuộc tính nhị phân)

(5) AAC: Score of discriminant analysis of the amino acid content of outer membrane and periplasmic proteins.(Chỉ số phân tích biệt thức của hàm lượng amino acid màng ngoài và periplasmic proteins)

(6) ALM1: Score of the ALOM membrane spanning region prediction program. (Chỉ số của chương trình dự đoán vùng mở rộng màng ALOM)

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

(7) ALM2: score of ALOM program after excluding putative cleavable signal regions from the sequence.(Chỉ số của chương trình ALOM sau khi đã loại bỏ các vùng tín hiệu giả định chia tách được từ dãy)

Tập dữ liệu bao gồm 336 mẫu dữ liệu và được phân thành 8 lớp là: cp, im, imS, imL, imU, om, omL, pp. Tỉ lệ số mẫu trong mỗi lớp tương ứng như sau: 143/cp, 77/im, 52/pp, 35/imU, 20/om, 5/omL, 2/imL, 2/imS.

TT Tên lớp Số lƣợng mẫu dữ liệu

1 cp (cytoplasm) 143

2 im (màng trong, không có chuỗi tín hiệu) 77

3 pp (perisplasm) 52

4 imU (màng trong, chuỗi tín hiệu không rõ) 35

5 om (màng ngoài) 20

6 omL (lipoprotein màng ngoài) 5

7 imL (lipoprotein màng trong) 2

8 imS (màng trong, chuỗi tín hiệu rõ) 2

Trong Hình 3.1 thể hiện sự phân bố dữ liệu của tập mẫu giữa các lớp theo

từng cặp thuộc tính, hình (a) cặp thuộc tính MCG và GVH, hình (b) cặp thuộc

tính AAC và ALM1.

(a) (b)

Hình 3.1: Sơ đồ phân bố dữ liệu giữa các lớp của bài toán Ecoli

Áp dụng thuật toán sinh luật bằng sử dụng khoảng tính mờ IFRG1, với

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

phương pháp sang luật là c.s (confidence x support), phương pháp lập luận là

chọn một luật thắng, số luật sàng theo lớp là 20. Các giá trị của tham số ngữ

nghĩa cho ở Bảng 3.2.

fmj(c-) fmj(c+) µj(L) µj(V) kj Thuộc tính

MCG 0.65 0.35 0.616 0.384 2

GVH 0.588 0.412 0.102 0.898 2

LIP 0.553 0.447 0.375 0.625 1

CHG 0.163 0.837 0.616 0.384 2

AAC 0.45 0.55 0.293 0.707 2

ALM1 0.732 0.268 0.21 0.79 2

ALM2 0.585 0.415 0.351 0.649 1

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Bảng 3.2: Bảng tham số mờ gia tử cho bài toán Ecoli

Kết quả chạy chương trình cho kết quả hệ luật được sinh ra bao gồm 85

luật như Hình 3.3; tỉ lệ lỗi phân lớp là 77/336, tỉ lệ phân lớp đúng là 77.08%,

như Hình 3.4.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Hình 3.3: Kết quả chạy chương trình, cho kết quả hệ luật được sinh ra 85 hệ luật và được mô tả lại như Bảng 3.5.

Hình 3.4: Phân lớp dữ liệu mẫu, tỉ lệ lỗi phân lớp là 77/336, tỉ lệ phân lớp đúng là 77.08%.

Bảng danh sách hệ luật theo thuật toán IFRG1 của bài toán Ecoli:

R1

R2

R3

R4

R5

R6

if MCG is L.low and GVH is V.low and LIP is high and CHG is V.high and AAC is L.high and ALM1 is V.low and ALM2 is low then cp (c= 0.9771, s= 0.0275) if MCG is L.low and GVH is V.low and LIP is high and CHG is V.high and AAC is V.low and ALM1 is V.low and ALM2 is low then cp (c= 0.9914, s= 0.0109) if MCG is V.low and GVH is V.low and LIP is high and CHG is V.high and AAC is L.high and ALM1 is V.low and ALM2 is low then cp (c= 1, s= 0.0098) if MCG is L.low and GVH is V.low and LIP is high and CHG is V.high and AAC is V.high and ALM1 is V.low and ALM2 is low then cp (c= 1, s= 0.0077) if MCG is L.low and GVH is V.low and LIP is high and CHG is V.high and AAC is L.low and ALM1 is V.low and ALM2 is low then cp (c= 1, s= 0.006) if MCG is L.low and GVH is L.low and LIP is high and CHG is V.high and AAC is L.high and ALM1 is V.low and ALM2 is low then cp (c= 0.9911, s= 0.0026)

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

R7

R8

R9

R10

R11

R12

R13

R14

R15

R16

R17

R18

R19

R20

R21

if MCG is V.low and GVH is V.low and LIP is high and CHG is V.high and AAC is V.high and ALM1 is V.low and ALM2 is low then cp (c= 0.8085, s= 0.0027) if MCG is V.low and GVH is V.low and LIP is high and CHG is V.high and AAC is L.low and ALM1 is V.low and ALM2 is low then cp (c= 1, s= 0.0017) if MCG is L.high and GVH is L.high and LIP is high and CHG is V.high and AAC is L.low and ALM1 is V.low and ALM2 is low then cp (c= 1, s= 0.0017) if MCG is V.low and GVH is L.low and LIP is high and CHG is V.high and AAC is L.high and ALM1 is V.low and ALM2 is low then cp (c= 1, s= 0.0015) if MCG is L.high and GVH is V.low and LIP is high and CHG is V.high and AAC is L.low and ALM1 is V.low and ALM2 is low then cp (c= 0.7397, s= 0.0011) if MCG is L.low and GVH is L.high and LIP is high and CHG is V.high and AAC is V.high and ALM1 is V.low and ALM2 is low then cp (c= 1, s= 0.0006) if MCG is L.low and GVH is L.low and LIP is high and CHG is V.high and AAC is V.high and ALM1 is V.low and ALM2 is low then cp (c= 0.6053, s= 0.0006) if MCG is L.low and GVH is L.low and LIP is high and CHG is V.high and AAC is L.low and ALM1 is V.low and ALM2 is low then cp (c= 1, s= 0.0003) if MCG is V.low and GVH is V.low and LIP is high and CHG is V.high and AAC is L.low and ALM1 is V.low and ALM2 is 0 then cp (c= 1, s= 0.0002) if MCG is L.low and GVH is L.high and LIP is high and CHG is V.high and AAC is L.high and ALM1 is V.low and ALM2 is low then cp (c= 0.7746, s= 0.0003) if MCG is L.low and GVH is L.low and LIP is high and CHG is V.high and AAC is V.low and ALM1 is V.low and ALM2 is low then cp (c= 1, s= 0.0002) if MCG is V.low and GVH is L.low and LIP is high and CHG is V.high and AAC is V.low and ALM1 is V.low and ALM2 is low then cp (c= 1, s= 0.0002) if MCG is L.low and GVH is V.high and LIP is high and CHG is V.high and AAC is V.low and ALM1 is V.low and ALM2 is low then cp (c= 1, s= 0.0001) if MCG is L.high and GVH is L.low and LIP is high and CHG is V.high and AAC is L.high and ALM1 is V.low and ALM2 is low then cp (c= 0.9317, s= 0.0001) if MCG is V.low and GVH is V.high and LIP is high and CHG is V.high and AAC is V.high and ALM1 is L.low and ALM2 is

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

R22

R23

R24

R25

R26

R27

R28

R29

R30

R31

R32

R33

R34

R35

low then im (c= 1, s= 0.0021) if MCG is L.high and GVH is V.high and LIP is high and CHG is V.high and AAC is L.high and ALM1 is V.high and ALM2 is high then im (c= 1, s= 0.0005) if MCG is L.low and GVH is V.low and LIP is high and CHG is V.high and AAC is L.high and ALM1 is V.low and ALM2 is high then im (c= 1, s= 0.0009) if MCG is L.high and GVH is V.high and LIP is high and CHG is V.high and AAC is L.high and ALM1 is V.high and ALM2 is low then im (c= 1, s= 0.0005) if MCG is V.low and GVH is V.high and LIP is high and CHG is V.high and AAC is L.low and ALM1 is V.high and ALM2 is high then im (c= 1, s= 0.0026) if MCG is L.low and GVH is L.low and LIP is high and CHG is V.high and AAC is V.high and ALM1 is V.high and ALM2 is low then im (c= 1, s= 0.0005) if MCG is L.low and GVH is V.low and LIP is high and CHG is V.high and AAC is V.low and ALM1 is V.high and ALM2 is low then im (c= 1, s= 0.0009) if MCG is V.low and GVH is V.low and LIP is high and CHG is V.high and AAC is V.high and ALM1 is L.high and ALM2 is low then im (c= 1, s= 0.0004) if MCG is L.high and GVH is V.high and LIP is high and CHG is V.high and AAC is V.high and ALM1 is L.high and ALM2 is low then im (c= 1, s= 0.0013) if MCG is L.high and GVH is V.low and LIP is high and CHG is V.high and AAC is V.high and ALM1 is V.low and ALM2 is low then im (c= 0.7108, s= 0.0006) if MCG is V.low and GVH is V.low and LIP is high and CHG is V.high and AAC is V.high and ALM1 is L.low and ALM2 is low then im (c= 1, s= 0.0007) if MCG is V.high and GVH is L.high and LIP is high and CHG is V.high and AAC is L.high and ALM1 is L.high and ALM2 is low then im (c= 1, s= 0.0004) if MCG is V.low and GVH is V.high and LIP is high and CHG is V.high and AAC is L.high and ALM1 is V.high and ALM2 is low then im (c= 1, s= 0.0028) if MCG is L.low and GVH is V.low and LIP is high and CHG is V.high and AAC is V.high and ALM1 is L.high and ALM2 is low then im (c= 0.9303, s= 0.0004) if MCG is L.low and GVH is V.high and LIP is high and CHG is V.high and AAC is L.low and ALM1 is V.high and ALM2 is low then im (c= 1, s= 0.0005)

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

R36

R37

R38

R39

R40

R41

R42

R43

R44

R45

R46

R47

R48

R49

R50

if MCG is L.low and GVH is L.low and LIP is high and CHG is V.high and AAC is V.low and ALM1 is V.high and ALM2 is high then im (c= 1, s= 0.0003) if MCG is L.low and GVH is V.high and LIP is high and CHG is V.high and AAC is L.high and ALM1 is V.high and ALM2 is high then im (c= 1, s= 0.0009) if MCG is V.high and GVH is V.low and LIP is high and CHG is V.high and AAC is V.high and ALM1 is L.high and ALM2 is low then im (c= 1, s= 0.0003) if MCG is L.low and GVH is V.low and LIP is high and CHG is V.high and AAC is V.high and ALM1 is V.high and ALM2 is high then im (c= 1, s= 0.0005) if MCG is L.high and GVH is V.low and LIP is high and CHG is V.high and AAC is V.high and ALM1 is V.high and ALM2 is high then im (c= 1, s= 0.0003) if MCG is V.high and GVH is L.high and LIP is high and CHG is V.high and AAC is L.high and ALM1 is V.low and ALM2 is low then imS (c= 1, s= 0) if MCG is L.high and GVH is L.high and LIP is 0 and CHG is V.low and AAC is V.low and ALM1 is V.low and ALM2 is low then imL (c= 1, s= 0.0003) if MCG is V.low and GVH is V.low and LIP is 0 and CHG is V.high and AAC is L.high and ALM1 is V.high and ALM2 is low then imL (c= 1, s= 0.0001) if MCG is L.high and GVH is V.low and LIP is high and CHG is V.high and AAC is L.high and ALM1 is V.high and ALM2 is low then imU (c= 1, s= 0.0011) if MCG is L.high and GVH is V.low and LIP is high and CHG is V.high and AAC is V.high and ALM1 is L.high and ALM2 is low then imU (c= 1, s= 0.0001) if MCG is V.high and GVH is L.high and LIP is high and CHG is V.high and AAC is V.high and ALM1 is V.high and ALM2 is low then imU (c= 1, s= 0.0017) if MCG is L.high and GVH is V.low and LIP is high and CHG is V.high and AAC is V.low and ALM1 is L.low and ALM2 is low then imU (c= 1, s= 0.0002) if MCG is L.low and GVH is V.high and LIP is 0 and CHG is V.high and AAC is V.high and ALM1 is L.high and ALM2 is low then imU (c= 1, s= 0.0001) if MCG is V.low and GVH is L.high and LIP is high and CHG is V.high and AAC is V.low and ALM1 is V.high and ALM2 is high then imU (c= 1, s= 0.0003) if MCG is V.high and GVH is L.low and LIP is high and CHG is V.high and AAC is V.high and ALM1 is V.high and ALM2 is

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

R51

R52

R53

R54

R55

R56

R57

R58

R59

R60

R61

R62

R63

R64

low then imU (c= 1, s= 0.0004) if MCG is V.high and GVH is L.high and LIP is high and CHG is V.high and AAC is V.low and ALM1 is L.low and ALM2 is low then imU (c= 1, s= 0.0001) if MCG is L.high and GVH is V.low and LIP is high and CHG is V.high and AAC is L.high and ALM1 is L.high and ALM2 is low then imU (c= 1, s= 0.0001) if MCG is V.high and GVH is V.low and LIP is high and CHG is V.high and AAC is V.high and ALM1 is V.high and ALM2 is low then imU (c= 1, s= 0.0016) if MCG is L.high and GVH is V.high and LIP is high and CHG is V.high and AAC is V.low and ALM1 is L.high and ALM2 is low then imU (c= 1, s= 0) if MCG is V.high and GVH is V.low and LIP is high and CHG is V.high and AAC is L.high and ALM1 is L.high and ALM2 is low then imU (c= 0.6529, s= 0.0005) if MCG is L.high and GVH is L.low and LIP is high and CHG is V.high and AAC is V.high and ALM1 is L.high and ALM2 is low then imU (c= 1, s= 0.0001) if MCG is V.high and GVH is V.low and LIP is high and CHG is V.high and AAC is L.high and ALM1 is L.low and ALM2 is low then imU (c= 1, s= 0) if MCG is V.high and GVH is V.low and LIP is high and CHG is V.high and AAC is L.high and ALM1 is V.high and ALM2 is low then imU (c= 1, s= 0.0005) if MCG is L.high and GVH is V.low and LIP is high and CHG is V.high and AAC is V.high and ALM1 is L.low and ALM2 is low then imU (c= 0.7651, s= 0.0005) if MCG is L.high and GVH is L.high and LIP is high and CHG is V.high and AAC is L.high and ALM1 is V.high and ALM2 is low then imU (c= 1, s= 0) if MCG is V.high and GVH is L.high and LIP is high and CHG is V.high and AAC is V.high and ALM1 is V.high and ALM2 is high then imU (c= 1, s= 0.0001) if MCG is L.high and GVH is V.low and LIP is high and CHG is V.high and AAC is V.high and ALM1 is V.high and ALM2 is low then imU (c= 0.8418, s= 0.0003) if MCG is V.high and GVH is V.high and LIP is high and CHG is V.high and AAC is V.high and ALM1 is V.low and ALM2 is low then om (c= 1, s= 0.0004) if MCG is L.low and GVH is V.high and LIP is high and CHG is V.high and AAC is V.high and ALM1 is V.low and ALM2 is low then om (c= 0.9541, s= 0.0017)

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

R65

R66

R67

R68

R69

R70

R71

R72

R73

R74

R75

R76

R77

R78

R79

if MCG is L.high and GVH is L.low and LIP is high and CHG is V.high and AAC is V.high and ALM1 is V.low and ALM2 is low then om (c= 0.8664, s= 0.0013) if MCG is L.high and GVH is V.high and LIP is high and CHG is V.high and AAC is V.high and ALM1 is L.low and ALM2 is low then om (c= 0.8851, s= 0.0014) if MCG is V.low and GVH is V.high and LIP is 0 and CHG is V.high and AAC is V.high and ALM1 is L.low and ALM2 is low then om (c= 1, s= 0.0027) if MCG is L.high and GVH is V.high and LIP is high and CHG is V.high and AAC is V.high and ALM1 is V.low and ALM2 is low then om (c= 0.907, s= 0.0126) if MCG is L.high and GVH is L.low and LIP is 0 and CHG is V.high and AAC is V.high and ALM1 is L.low and ALM2 is low then omL (c= 1, s= 0.0001) if MCG is L.high and GVH is L.high and LIP is 0 and CHG is V.high and AAC is V.high and ALM1 is L.low and ALM2 is low then omL (c= 1, s= 0.0021) if MCG is L.high and GVH is V.high and LIP is 0 and CHG is V.high and AAC is L.low and ALM1 is V.low and ALM2 is low then omL (c= 1, s= 0) if MCG is L.high and GVH is V.low and LIP is 0 and CHG is V.high and AAC is L.high and ALM1 is L.low and ALM2 is low then omL (c= 1, s= 0.0001) if MCG is L.high and GVH is V.high and LIP is high and CHG is V.high and AAC is L.low and ALM1 is L.low and ALM2 is low then pp (c= 1, s= 0.0002) if MCG is V.low and GVH is V.high and LIP is high and CHG is V.high and AAC is L.high and ALM1 is V.high and ALM2 is high then pp (c= 1, s= 0) if MCG is L.low and GVH is V.high and LIP is high and CHG is V.high and AAC is L.high and ALM1 is V.low and ALM2 is low then pp (c= 0.8445, s= 0.0006) if MCG is L.high and GVH is V.high and LIP is high and CHG is V.high and AAC is L.high and ALM1 is V.low and ALM2 is low then pp (c= 0.8568, s= 0.0131) if MCG is L.high and GVH is V.low and LIP is high and CHG is V.high and AAC is L.high and ALM1 is V.low and ALM2 is low then pp (c= 0.6677, s= 0.0033) if MCG is L.high and GVH is V.high and LIP is high and CHG is V.high and AAC is L.high and ALM1 is L.low and ALM2 is low then pp (c= 1, s= 0) if MCG is L.high and GVH is V.high and LIP is high and CHG is V.high and AAC is V.low and ALM1 is L.low and ALM2 is low

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

R80

R81

R82

R83

R84

R85

then pp (c= 1, s= 0.0001) if MCG is V.low and GVH is V.high and LIP is high and CHG is V.high and AAC is L.high and ALM1 is V.low and ALM2 is low then pp (c= 1, s= 0.0007) if MCG is V.low and GVH is V.high and LIP is high and CHG is V.high and AAC is V.high and ALM1 is V.low and ALM2 is low then pp (c= 1, s= 0.0002) if MCG is L.high and GVH is V.low and LIP is high and CHG is V.high and AAC is L.high and ALM1 is L.low and ALM2 is low then pp (c= 0.9538, s= 0.001) if MCG is L.high and GVH is L.low and LIP is high and CHG is V.high and AAC is V.low and ALM1 is L.low and ALM2 is low then pp (c= 1, s= 0.0001) if MCG is L.high and GVH is V.high and LIP is high and CHG is V.high and AAC is L.low and ALM1 is V.low and ALM2 is low then pp (c= 1, s= 0.0062) if MCG is L.high and GVH is V.high and LIP is high and CHG is V.high and AAC is V.low and ALM1 is V.low and ALM2 is low then pp (c= 0.916, s= 0.0098)

Bảng 3.5: Danh sách hệ luật theo thuật toán IFRG1 của bài toán Ecoli

Nếu không sử dụng phương pháp sàng luật thì hệ luật sinh ra gồm 119

luật, như Hình 3.6; với tỉ lệ lỗi phân lớp là 35/336, tỉ lệ phân lớp đúng là

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

89.58%, như Hình 3.7.

Hình 3.6: Không sử dụng phương pháp sàng luật, thì số luật sinh ra 119 hệ luật.

Hình 3.7: Tỉ lệ lỗi phân lớp là 35/336, tỉ lệ phân lớp đúng là 89.58%

Sử dụng phương pháp sàng luật làm giảm tỉ lệ phân lớp là do sự phân bố

chồng chéo giữa các mẫu dữ liệu, do vậy khi sinh luật thì cơ hội mỗi siêu hộp

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

chứa nhiều mẫu dữ liệu ở khác lớp nhau rất cao, luật sinh ra không có tính

phân biệt lớn giữa các lớp hay luật mờ có tính phổ quát cao, bên cạnh đó tỉ lệ

giữa các mẫu dữ liệu theo lớp không được cân bằng cũng làm ảnh hưởng đến tỉ

lệ phân lớp.

So sánh kết quả phân lớp của phương pháp IFRG1 với phương pháp

phân lớp Bayes được nêu trong [8] trên cùng mẫu dữ liệu mẫu vào Phân loại vị

trí protein bằng khuẩn Ecoli. Kết quả cho thấy phương pháp IFRG1 có độ tin

cậy cao, như bảng 3.8.

Dữ liệu mẫu Phân loại vị trí protein bằng khuẩn Ecoli Phƣơng pháp IFRG1 Phƣơng pháp phân lớp Bayes

Sử dụng phương pháp sàng luật:

- 85 luật. - Phân lớp đúng đạt 77.08%

Tỷ lệ phân lớp đúng đạt 81%

Không sử dụng phương pháp sàng luật: - 119 luật. - Phân lớp đúng đạt 89.58%

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Bảng 3.8: Kết quả phân lớp giữa phương pháp IFRG1 với phương pháp Bayes

3.2. Bài toán phân lớp đánh giá trợ giảng (TAE)

Ứng dụng được xây dựng bằng ngôn ngữ Java, bao gồm các bước thực

hiện thuật toán sinh hệ luật mờ: Đọc tệp dữ liệu  thay đổi tham số đầu vào cho

các thuộc tính  Sinh hệ luật mờ  kiểm tra tỉ lệ phân lớp của hệ luật.

Bài toán này được đưa ra bởi Wei-Yin Loh tại Khoa thống kê của Đại học

Wisconsin-Madison. Các dữ liệu này là các đánh giá về hoạt động giảng dạy

trong 3 học kỳ chính và 2 học kỳ hè của 151 trợ lý giảng dạy (TA).

Dữ liệu có 5 thuộc tính là:

(1) NES:Whether of not the TA is a native English speaker(TA là người

nói tiếng Anh bản địa hay không. 1: Nói tiếng Anh, 2: Không nói

tiếng Anh (nhị phân))

(2) CI: Course instructor(Người hướng dẫn khóa học, dạng phân nhóm,

25 nhóm)

(3) C: Course(Khóa học, dạng phân nhóm, 26 nhóm)

(4) SOR: Summer or regular semester(Học kỳ hè hoặc học kỳ chính, 1:

học kỳ hè, 2: học kỳ chính (nhị phân))

(5) CS: Class size(quy mô lớp học, dạng số)

Tập dữ liệu mẫu bao gồm 151 mẫu được chia thành 3 lớp: (“thấp”, “trung

bình” và “cao” - "Low", "Medium", and "High"). Với tỉ lệ mẫu trên các lớp là:

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

52/High, 50/Medium và 49/Low.

Hình 3.9: Sơ đồ phân bố dữ liệu của bài toán đánh giá trợ giảng (TAE)

Áp dụng thuật toán sinh luật bằng sử dụng khoảng tính mờ IFRG1, với

phương pháp sang luật là c.s(confidence x support), phương pháp lập luận là

chọn một luật thắng, số luật sàng theo lớp là 20. Các giá trị của tham số ngữ

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

nghĩa cho ở Bảng 3.9.

Thuộc tính µj(L) µj(V) kj

NES CI C SOR CS fmj(c-) 0.818 0.401 0.21 0.7 0.291 0.355 0.179 0.492 0.412 0.452 0.645 0.821 0.508 0.588 0.548 fmj(c+) 0.182 0.599 0.79 0.3 0.709 3 2 2 2 3

Bảng 3.9: Bảng tham số mờ gia tử cho bài toán đánh giá trợ giảng

Kết quả chạy chương trình cho kết quả hệ luật được sinh ra bao gồm 60

hệ luật, như Hình 3.10 và Bảng 3.12; tỉ lệ lỗi phân lớp là 37/151, tỉ lệ phân lớp

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

đúng là 75.5% như Hình 3.11.

Hình 3.10: Kết quả chạy chương trình, cho kết quả hệ luật được sinh ra 60 hệ luật và được mô tả lại như Bảng 3.12.

Hình 3.11: Kết quả chạy phân lớp dữ liệu, tỉ lệ lỗi phân lớp là 37/151,

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

tỉ lệ phân lớp đúng là 75.5%

Bảng Danh sách hệ luật của bài toán đánh giá trợ giảng (TAE):

if NES is VV.large and CI is V.small and C is V.small and SOR is V.large and CS is LL.large then Low (c= 1, s= 0.01797)

R1

if NES is VV.large and CI is V.small and C is V.small and SOR is V.large and CS is LV.large then Low (c= 1, s= 0.01215)

R2

if NES is VV.large and CI is V.large and C is L.small and SOR is V.large and CS is VL.small then Low (c= 1, s= 0.01183)

R3

if NES is VV.large and CI is V.small and C is L.large and SOR is V.large and CS is VL.large then Low (c= 0.84712, s= 0.01349)

R4

if NES is VV.large and CI is V.large and C is V.small and SOR is V.large and CS is VV.small then Low (c= 1, s= 0.00662)

R5

if NES is VV.large and CI is V.large and C is V.small and SOR is V.large and CS is VV.large then Low (c= 1, s= 0.00565)

R6

if NES is VV.large and CI is V.small and C is V.small and SOR is V.large and CS is VL.large then Low (c= 0.79007, s= 0.0071)

R7

if NES is VV.large and CI is V.large and C is V.small and SOR is V.large and CS is VL.small then Low (c= 1, s= 0.0053)

R8

if NES is VV.large and CI is V.large and C is V.large and SOR is V.large and CS is LL.small then Low (c= 1, s= 0.00515)

R9

if NES is VV.large and CI is V.large and C is V.small and SOR is V.large and CS is VL.large then Low (c= 0.64882, s= 0.0074)

R10

if NES is VV.large and CI is V.large and C is V.small and SOR is V.large and CS is LL.small then Low (c= 1, s= 0.00308)

R11

if NES is VV.large and CI is L.small and C is V.small and SOR is V.large and CS is VL.small then Low (c= 1, s= 0.00278)

R12

if NES is VV.large and CI is L.large and C is V.small and SOR is V.large and CS is VL.large then Low (c= 0.56358, s= 0.00351)

R13

if NES is VV.large and CI is V.large and C is L.small and SOR is V.large and CS is LV.small then Low (c= 1, s= 0.00126)

R14

if NES is VV.small and CI is V.large and C is V.small and SOR is V.large and CS is LL.large then Low (c= 0.5, s= 0.00237)

R15

if NES is VV.small and CI is V.large and C is L.large and SOR is V.large and CS is LV.large then Low (c= 1, s= 0.00092)

R16

if NES is VV.large and CI is L.large and C is V.small and SOR is V.large and CS is LV.large then Low (c= 1, s= 0.00075)

R17

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

if NES is VV.large and CI is L.small and C is V.small and SOR is V.large and CS is LV.small then Low (c= 1, s= 0.00062)

R18

if NES is VV.large and CI is L.large and C is L.large and SOR is V.large and CS is LL.large then Low (c= 1, s= 0.00025)

R19

if NES is VV.small and CI is L.large and C is V.small and SOR is V.small and CS is LV.small then Low (c= 1, s= 0.00005)

R20

if NES is VV.large and CI is V.small and C is L.large and SOR is V.large and CS is LV.small then Medium (c= 1, s= 0.00952)

R21

if NES is VV.large and CI is V.large and C is V.small and SOR is V.large and CS is LV.small then Medium (c= 0.65368, s= 0.0079)

R22

if NES is VV.large and CI is V.large and C is L.large and SOR is V.large and CS is LL.large then Medium (c= 0.57289, s= 0.00706)

R23

if NES is VV.small and CI is V.large and C is L.large and SOR is V.large and CS is VL.large then Medium (c= 0.9896, s= 0.00384)

R24

if NES is VV.small and CI is V.large and C is V.small and SOR is V.large and CS is LL.small then Medium (c= 1, s= 0.0032)

R25

if NES is VV.large and CI is V.large and C is L.large and SOR is V.large and CS is LL.small then Medium (c= 1, s= 0.00257)

R26

if NES is VV.large and CI is V.large and C is L.large and SOR is V.large and CS is VL.large then Medium (c= 1, s= 0.00243)

R27

if NES is VV.large and CI is V.large and C is V.small and SOR is V.large and CS is LV.large then Medium (c= 0.44176, s= 0.00549)

R28

if NES is VV.large and CI is V.small and C is V.large and SOR is V.large and CS is LV.large then Medium (c= 1, s= 0.00194)

R29

if NES is VV.large and CI is L.large and C is V.small and SOR is V.large and CS is VL.small then Medium (c= 1, s= 0.00152)

R30

if NES is VV.large and CI is V.small and C is L.large and SOR is V.large and CS is VL.small then Medium (c= 1, s= 0.00138)

R31

if NES is VV.large and CI is L.large and C is V.small and SOR is V.small and CS is LV.small then Medium (c= 0.63909, s= 0.0021)

R32

if NES is VV.large and CI is L.small and C is V.large and SOR is V.large and CS is VL.small then Medium (c= 1, s= 0.00114)

R33

if NES is VV.small and CI is V.large and C is V.large and SOR is V.large and CS is LV.large then Medium (c= 1, s= 0.00111)

R34

if NES is VV.large and CI is L.small and C is V.small and SOR is V.large and CS is LL.small then Medium (c= 1, s= 0.00098)

R35

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

if NES is VV.small and CI is V.small and C is V.large and SOR is V.large and CS is LL.large then Medium (c= 1, s= 0.00087)

R36

if NES is VV.large and CI is V.large and C is L.large and SOR is V.large and CS is VL.small then Medium (c= 1, s= 0.00079)

R37

if NES is VV.large and CI is L.large and C is L.large and SOR is V.large and CS is VL.large then Medium (c= 1, s= 0.00067)

R38

if NES is VV.large and CI is V.small and C is L.large and SOR is V.small and CS is VL.large then Medium (c= 1, s= 0.00029)

R39

if NES is VV.large and CI is L.small and C is L.small and SOR is V.large and CS is VV.small then Medium (c= 0.62306, s= 0.0004)

R40

if NES is VV.large and CI is V.large and C is V.large and SOR is V.large and CS is VL.large then High (c= 0.87528, s= 0.013)

R41

if NES is VV.large and CI is V.large and C is V.small and SOR is V.small and CS is VL.small then High (c= 0.83415, s= 0.00907)

R42

if NES is VV.small and CI is V.large and C is V.small and SOR is V.large and CS is LV.large then High (c= 1, s= 0.00676)

R43

if NES is VV.small and CI is V.large and C is V.small and SOR is V.small and CS is VL.small then High (c= 0.81819, s= 0.00812)

R44

if NES is VV.large and CI is V.large and C is V.large and SOR is V.large and CS is VL.small then High (c= 0.84994, s= 0.00646)

R45

if NES is VV.large and CI is V.small and C is L.large and SOR is V.large and CS is VV.large then High (c= 1, s= 0.00507)

R46

if NES is VV.large and CI is L.small and C is L.small and SOR is V.large and CS is VL.small then High (c= 1, s= 0.00379)

R47

if NES is VV.large and CI is V.small and C is L.large and SOR is V.small and CS is VL.small then High (c= 1, s= 0.00341)

R48

if NES is VV.large and CI is V.large and C is V.large and SOR is V.large and CS is LV.small then High (c= 1, s= 0.00335)

R49

if NES is VV.small and CI is V.large and C is V.small and SOR is V.small and CS is VV.large then High (c= 1, s= 0.00301)

R50

if NES is VV.small and CI is V.large and C is V.small and SOR is V.large and CS is VV.large then High (c= 1, s= 0.00301)

R51

if NES is VV.large and CI is L.small and C is V.small and SOR is V.large and CS is VL.large then High (c= 1, s= 0.00278)

R52

if NES is VV.small and CI is V.large and C is V.small and SOR is V.small and CS is VL.large then High (c= 1, s= 0.00204)

R53

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

if NES is VV.small and CI is V.small and C is V.small and SOR is V.large and CS is LL.large then High (c= 1, s= 0.00194)

R54

if NES is VV.small and CI is V.small and C is V.small and SOR is V.large and CS is VL.large then High (c= 1, s= 0.00146)

R55

if NES is VV.large and CI is L.small and C is V.large and SOR is V.large and CS is LV.small then High (c= 1, s= 0.00141)

R56

if NES is VV.small and CI is V.large and C is V.large and SOR is V.large and CS is VL.small then High (c= 1, s= 0.0013)

R57

if NES is VV.large and CI is L.small and C is V.small and SOR is V.large and CS is LL.large then High (c= 1, s= 0.00107)

R58

if NES is VV.large and CI is L.small and C is L.small and SOR is V.large and CS is VL.large then High (c= 1, s= 0.00089)

R59

Bảng 3.12: Danh sách hệ luật của bài toán đánh giá trợ giảng (TAE)

Nếu không sử dụng phương pháp sàng luật thì hệ luật sinh ra gồm 67 luật,

như Hình 3.13; với tỉ lệ lỗi phân lớp 29/151, tỉ lệ phân lớp đúng là 80.8%, như

Hình 3.14.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Hình 3.13

Hình 3.14

3.3. Kết luận Chƣơng 3

Chương 3 đã cài đặt chạy thuật toán sinh luật với 2 bài toán cụ thể, mỗi

bài toán có các đặc điểm về thuộc tính, các mẫu dữ liệu và sự phân bố các mẫu

dữ liệu khác nhau. Tùy theo mức phân bố dữ liệu và phương pháp sàng luật

theo mỗi lớp khác nhau mà hệ luật sinh ra nhiều hay ít, tỉ lệ phân lớp đúng cao

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

hay thấp.

KẾT LUẬN CHUNG

Trong quá trình học tập, tìm hiểu, nghiên cứu thực hiện luận văn, với sự

hướng dẫn, giúp đỡ của Thầy giáo TS. Dương Thăng Long. Luận văn đã thực

hiện đáp ứng được yêu cầu và có được 2 kết quả chính:

1. Nghiên cứu, tìm hiểu tài liệu để trình bày được một số vấn đề như: tiếp

cận bài toán phân lớp và phương pháp thực hiện dựa trên hệ mờ dạng luật.

Phương pháp sinh các từ ngôn ngữ và phương pháp định lượng ngữ nghĩa trọng

ĐSGT, xây dựng thuật toán sinh các luật mờ từ tập dữ liệu mẫu dựa trên hệ phân

hoạch các khoảng tính mờ (Initial Fuzzy Rules Generation - IFRG1).

2. Trên cơ sở thuật toán được đề xuất, thực hiện xây dựng phần mềm ứng

dụng mô phỏng cho 2 bài toán phân lớp có mẫu dữ liệu đặc trưng được cung cấp

bởi cơ sở dữ liệu của trường Đại học California - Irvin, được nhiều tác giả dùng

để thử nghiệm cho các mô hình phân lớp. Kết quả chạy chương trình sinh các hệ

luật và tỷ lệ phân lớp đúng đạt xấp xỉ 80% trở lên; kết quả thử nghiệm cho thấy

tính hiệu quả của phương pháp .Trong quá trình thực hiện phần mềm, bản thân

cũng đã được bổ sung thêm kiến thức, kỹ năng lập trình trên nền tảng ngôn ngữ

Java.

Hướng phát triển: Trên cơ sở của mô hình ứng dụng trong bài toán phân

lớp, tiếp tục thử nghiệm trên nhiều mẫu dữ liệu khác, để ứng dụng cho một số

bài toán khác trong lĩnh vực khai phá dữ liệu như khai phá luật kết hợp, phân

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

cụm dữ liệu,...

TÀI LIỆU THAM KHẢO

Tiếng Việt

[1] Dương Thăng Long (2010), Phương pháp xây dựng hệ mờ dạng luật với ngữ nghĩa dựa trên đại số gia tử và ứng dụng trong bài toán phân lớp, Luận án tiến sĩ toán học, Viện Công nghệ Thông tin.

[2] Dương Thăng Long, Trương Tiến Tùng, Trần Tiến Dũng (2013), A HA based Fuzzy Association Rule Extracting Method for Classification on High-Dimensional Datasets, Kỷ yếu hội nghị quốc gia lần thứ VI về nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR).

[3] Nguyễn Cát Hồ, Dương Thăng Long, Trần Thái Sơn (2009), “Tiếp cận đại số gia tử cho phân lớp mờ”, Tạp chí tin học và điều khiển học, Tập 25(1), tr 53-68.

[4] Nguyễn Ngọc Hoan (2008), Tiếp cận mờ và tiếp cận đại số gia tử trong điều khiển hệ quạt gió – cánh nhôm, Luận văn thạc sĩ khoa học máy tính, Trường ĐH Công nghệ thông tin và truyền thông Thái Nguyên.

[5] Nguyễn Cát Hồ (2008), Cơ sở dữ liệu mờ với ngữ nghĩa đại số gia tử, Bài

giảng Trường thu – hệ mờ và ứng dụng, Viện Toán học Việt Nam.

Tiếng Anh

[6] A. Fernández, F. Herrera (2012), “Linguistic Fuzzy Rules in Data Mining: Follow-Up Mamdani Fuzzy Modeling Principle”, STUDFUZZ, vol. 221, pp 103-122.

Website

[7]

The Machine Learning Repository of University of California - Irvinehttp://archive.ics.uci.edu/ml/datasets.html?format=&task=cla&att= &area=&numAtt =&numIns=&type=&sort=nameUp&view=table

http://archive.ics.uci.edu/ml/datasets/Ecoli [8]

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

http://archive.ics.uci.edu/ml/datasets/Teaching+Assistant+Evaluation [9]

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn