HỌC

VIỆN

CÔNG

NGHỆ

BƯU

CHÍNH

VIỄN

THÔNG


GIA

TỬ
Chuyên

ngành:

KHOA

HỌC

MÁY

TÍNH

Mã

số:

60.48.01


VIỆN

CÔNG

NGHỆ

BƯU

CHÍNH

VIỄN

THÔNG Người

hướng

dẫn

khoa

học
:

TS.Vào lúc: giờ ngày tháng năm

Có thể tìm hiểu luận văn tại:

- Thư viện của Học viện Công nghệ Bưu chính Viễn thông
1

I.

MỞ

ĐẦU
quá

trình

tự

động

tìm kiếm

thông tin hữu ích, các quan hệ phát hiện các tri thức. Để làm được điều đó các nhà

nghiên cứu đã đề xuất và nghiên cứu lĩnh vực này như phân lớp và nhận dạng mẫu,

hồi quy và dự báo, phân cụm… dựa trên tâp mờ.

Lý thuyết tập mờ được coi là nền tảng của lập luận xấp xỉ, nhưng lý thuyết tập

mờ vẫn chưa mô phỏng đầy đủ, hoàn chỉnh cấu trúc ngôn ngữ mà con người vẫn sử

dụng. Vì thế năm 1990 N.C.Ho & W.Wechler đã khởi xướng phương pháp tiếp cận

đại số dựa trên miền giá trị của biến ngôn ngữ.

Với ý nghĩa như vậy mục tiêu của luận văn đặt ra cụ thể như sau:

- Trình bày về tập mờ, logic mờ

- Trình bày thuật toán FCM



tập dữ liệu đầu vào, qua chương trình sẽ đánh giá tính hiệu năng của thuật toán, thấy

được tỉ lệ nhận dạng đúng khi phân loại bộ hoa Iris.

Chương

4
: Đánh giá kết quả và cài đặt tối ưu. Để có được tỉ lệ nhận dạng cao,

sử dụng giải thuật di truyền để tối ưu bộ số gia tử.
2
II.

NỘI

DUNGChương

1:

LOGIC

MỜ

VÀ

BÀI


hỗ

trợ

quyết

định…

Vậy

để

làm được

những

điều

đó

luận

văn

sẽ

đi

trình

1.1.1.

Lý

thuyết

tập

mờ

Lý thuyết tập mờ lần đầu tiên được Lotfi.A.Zadeh, một giáo sư thuộc trường

Đại học Caliornia, Berkley giới thiệu trong một công trình nghiên cứu vào năm 1965.

Lý thuyết tập mờ bao gồm logic mờ, số học mờ, quy hoạch toán học mờ, hình học

tôpô mờ, lý thuyết đồ

thị mờ, và phân tích dữ liệu mờ, mặc dù thuật ngữ logic mờ

thường được dùng chung cho tất cả.

Không

giống

như

tập


khả năng nhất định mà thôi.

Trọng tâm của lý thuyết tập mờ là việc đề xuất khái niệm tập mờ (fuzzy sets).

Về

mặt

toán

học,

một

tập

mờ

A

là

một

hàm

số

(gọi



tả định tính thuộc tính của đối tượng, chẳng hạn như cao, thấp, nóng, lạnh, sáng, tối

…

Một khái niệm cơ bản khác được đưa ra - biến ngôn ngữ (linguistic variables).

Biến

ngôn ngữ

là

biến

nhận

các giá

trị ngôn ngữ (linguistic

terms)

chẳng

hạn như
3
"già ", " trẻ " và "trung niên ", trong đó, mỗi giá trị ngôn ngữ

thực chất là một tập mờ


phủ

lên

nhau

(chẳng hạn, một người ở tuổi 50 có thể trực thuộc cả

tập mờ " trung niên ” lẫn tập

mờ " già ", với mức độ trực thuộc với mỗi tập là khác nhau).

1.1.2.

Logic

mờ

Trong logic rõ thì mệnh đề là một câu phát biểu đúng, sai. Trong logic mờ thì

mỗi mệnh đề mờ là một câu phát biểu không nhất thiết là đúng hoặc sai. Mệnh đề mờ

được gán cho một giá trị trong khoảng từ 0 đến 1 để chỉ mức độ đúng (độ thuộc) của

nó.

Các phép toán mệnh đề trong logic mờ được định nghĩa nhưsau:

-

toán

phân

cụm

mờBài toán phân cụm mờ được ứng dụng rất nhiều như trong việc nhận dạng mẫu

(vân tay, ảnh), xử lí ảnh, y học (phân loại bệnh lí, triệu chứng)…

Tuy nhiên với giải thuật thứ 2, tức là sử dụng logic mờ để phân cụm dữ liệu

mềm dẻo hơn rất nhiều (so với giải thuật K-means). Nó cho phép một đối tượng có

thể

thuộc

vào

một

hay

nhiều

phân

(x,y)

=

x

−

y

2



=1
(


v
i

=

1

x
k

∈G
i


mờ

Tập các đối tượng sẽ được phân vùng

X={x1,…,xN} ; (k=1,2,…,N)

Việc đánh giá quan hệ không đồng dạng trong 1 không gian cho trước thường sử

dụng

nhiều

đến

khái

niệm

metric,

metric

giữa

2

đối

tượng


mức

độ

không

đồng

dạng

D(X,Y)

chúng

ta

dùng

(được

mô

tả

dưới

đây)

được

-

Bước 2: sắp xếp các đối tượng sao cho gần tâm vùng nhất,

điều này có

nghĩa là:

x
k

∈

G
i
D
(
x
k

,

v
i

)

=

min


1

x
k

∈

G
i

,

5
- Bước 2 : Tối thiểu hàm J với G trong khi V được cố định

- Bước 3 : Tối thiểu J với V trong khi G được cố định

Bằng việc xây dựng ma trận U (NxC)
U

=

(
U
ki
)0






(



,




)


=1

=1

Nhược điểm lớn nhất của Fuzzy C- Means là việc xử lí gặp khó khăn khi tập

dữ

liệu

lớn,

tập


cụm. Để giải quyết vấn đề này, đã có nhiều phương pháp được đề xuất như phân cụm

dựa

trên

xác

suất

(Keller,

1993),

phân

cụm

nhiễu

mờ

(Dave, 1991),

thuật

toán

Є


SỬ

DỤNG

ĐẠI

SỐ

GIA

TỬTrong chương này luận văn sẽ trình bày:

-

Lý thuyết về đại số gia tử

-

Phân cụm mờ sử dụng lý thuyết đại số gia tử

2.1.

Lý

thuyết


dạng

phân

cụm.

Ví

dụ

như

giải

thuật

Gustafson-

Kessel (GK) xử lí tốt với những phân cụm dạng elip. Trong một số nghiên cứu, các

tác giả trong [12] đã chỉ ra khả năng của đại số gia tử với việc biểu diễn giá trị của

các biến ngôn ngữ dựa trên cấu trúc ngữ nghĩa của chúng. Việc ứng dụng đại số gia

tử trong thực hiện thông qua các bước:

-

Sử dụng cấu trúc đại số gia tử thay đổi ước lượng khoảng cách từ mẫu


(1) Mỗi gia tử hoặc là dương hoặc là âm đối với bất kỳ một gia tử nào khác, kể cả với

chính nó.
(2)

Nếu

hai

khái niệm u

và

v

là

độc

lập

nhau, nghĩa

là u∉H(v)

và

v∉H(u), thì

(∀x

nghịch

của

w

được

định

nghĩa

chính

là

w.

Phần

tử

đối

nghịch của x được ký hiệu là –x với chỉ số nếu cần thiết. Nhìn chung một phần tử có

thể có nhiều phần tử đối nghịch.

2.1.2



2.1.3

Tính

mờ

của

một

giá

trị

ngôn

ngữ

Cho

trước

một hàm định

lượng ngữ

nghĩa

f


Việc cải tiến giải thuật gồm những nội dung chính sau:


Sử dụng lí thuyết đại số gia tử cho việc sửa đổi khoảng cách từ mẫu tới

tâm cụm. Độ đo mờ của giá trị ngôn ngữ được dùng như trọng số tương ứng với mỗi

mẫu.


Một mẫu thuộc về một phân vùng được xác định khi mức độ thuộc của

nó đối với cụm đó có giá trị lớn hơn phần tử trung gian w của đại số gia tử. Theo đó

chỉ có những mẫu có giá trị độ thuộc vượt trên w mới được tham gia vào quá trình

tính toán lại tâm cụm sau này. Việc này sẽ làm hạn chế tầm ảnh hưởng của các phần

tử nhiễu.

Do vậy việc sử dụng đại số gia tử cho phép ta tạo lập các trọng số phù hợp với

mỗi mẫu dữ liệu dựa trên khoảng cách từ nó đến tâm vùng. Tâm cụm mới thu được

qua

phép

biểu


ngôn

ngữ

(LCC-linguistic cluster center). Việc xác định LCC được thực hiện qua 3 bước:

1.

Xác định giá trị k-level ngôn ngữ và độ đo mờ của chúng (Ở đây, một k-

level ngôn ngữ được xác định thông qua số lượng gia tử đi kèm theo phần tử sinh, lấy

ví dụ Very very True là một 3-level, tuy nhiên trong suốt đồ án này sẽ chỉ làm việc

liên quan tới 2-level linguistic tức là các giá trị ngôn ngữ có dạng Very True. Độ đo

mờ

của

chúng

được

tính

toán

dựa

kí

hiệu

là

d
max
Sau khi hoàn thành việc xây dựng tâm cụm ngôn ngữ, tiếp theo chúng ta cần

xác

định

giải

thuật

tính

toán

trọng

số

cho

mỗi



giá

trị

trung

gian

w,

độ

đo

mờ

của

các

biến

gia

tử

fm(hi).

Đầu ra: trọng số tương ứng cho khoảng cách tương ứng dij từ xi tới cj.

Như vậy với việc tìm hiểu đại số gia tử ở trên dễ thấy được ưu điểm của đại số

gia tử so với tiếp cận mờ theo hướng truyền thống. Nếu như phương pháp luận mờ

phụ thuộc vào yếu tố là hàm thuộc, mà xác định hàm thuộc với các bài toán lớn là rất

khó khăn dẫn đến nhiều sai số thì phương pháp lập luận mờ sử dụng đại số gia tử chỉ

cần tập trung đến độ đo tính mờ hay tối ưu được bộ số gia tử.

Có

rất

nhiều

các

nghiên

cứu

đã

so

sánh

và



Như vậy, luận văn đã trình bày các vấn đề về đại số gia tử và phân cụm mờ sử

dụng lý thuyết đại số gia tử.

Trong chương tiếp theo sẽ tiến hành phân tích thiết kế và cài đặt giải thuật để làm rõ

hơn bài toán đã nêu, cũng như đánh giá được hiệu năng của thuật toán.
10
Chương

3:

PHÂN

TÍCH

THIẾT

KẾ

VÀ

CÀI

ĐẶT

THỬ

NGHIỆM

toán

Dữ liệu mẫu IRIS đem phân cụm gồm 150 đối tượng hoa thuộc vào 3 lớp khác

nhau, là Iris-setosa, Iris-versicolor và Iris-verginica. Việc thực hiện cài đặt phân cụm

mờ trên tập dữ liệu mẫu đã phân lớp sẵn cho phép ta có cơ sở đánh giá sai số cũng

như hiệu quả của thuật toán về sau.

3.2.

Phân

tích

và

thiết

kế

chức

năng

Chương trình được tạo dựng với 3 lớp chính đó là:

-



3.3.

Mô

tả

chương

trình3.3.1

Giao

diện

chính File sau khi phân cụm: 3.4.

Kết

luận

chương


ưu

bộ

số

gia tử để

có

được phần

trăm nhận dạng mẫu cao hơn.
13
Chương

4:

ĐÁNH

GIÁ

KẾT

QUẢ,

CÀI

ĐẶT

Khác biệt quan trọng giữa tìm kiếm của

GA và

các phương pháp

tìm kiếm khác là

GA

duy trì

và

xử

lý

một

tập

các

lời

giải

(gọi


gian

tìm

kiếm.

Vì

thế

GA

mạnh

hơn

các

phương pháp tìm kiếm hiện có rất nhiều.

Phương pháp leo đồi dùng kỹ thuật lặp và áp dụng cho 1 điểm duy nhất (điểm

hiện hành trong không gian tìm kiếm). Trong mỗi bước lặp, một điểm mới được chọn

từ lân cận của điểm hiện hành (vì thế phương pháp leo đồi còn được gọi là phương

pháp tìm kiếm lân cận hay tìm kiếm cục bộ). Nếu điểm mới cho giá trị của hàm mục

tiêu tốt hơn thì điểm mới sẽ trở thành điểm hiện hành, nếu không một lân cận khác sẽ


bất

lợi

của

phương pháp leo đồi: Lời giản không còn phụ thuộc nhiều vào điểm khởi đầu nữa và

thường là gần với điểm tối ưu. Đạt được điều này là đưa vào xác suất nhận p. Xác

suất p là 1 hàm theo giá trị của hàm mục tiêu đối với điểm hiện hành và điểm mới và

1 tham số điều khiển bổ sung, tham số “nhiệt độ” T. Nói chung, nhiệt độ T càng thấp

thì cơ hội nhận điểm mới càng nhỏ. Khi thực hiện giải thuật, nhiệt độ T của hệ thống

sẽ được hạ thấp dần theo từng bước. Thuật giải dừng khi T nhỏ hơn một ngưỡng cho

trước, với ngưỡng này thì gần như không còn thay đổi nào được chấp nhận nữa.
14
Giải thuật di truyền được mô phỏng bởi các quá trình cơ bản:
4.1.1.

Lai

ghép4.1.2.


thuật

di

truyền

Việc cài đặt giải thuật di truyền được tiến hành thông qua 3 lớp

-

Chromosome: cho phép biểu diễn một nhiễm sắc thể (một cá thể) trong quần thể lời

giải của bài toán

-

GaAlgorithm:

lớp

này phục

vụ

việc

cài

đặt



Bộ

số

gia

tử

tối

ưu:

công tìm ra bộ số gia tử tối ưu. Tuy nhiên việc tối ưu hóa này

cũng mất khá nhiều

thời gian do việc phải thực thi số vòng lặp khá lớn.
16
KẾT

LUẬNLuận văn đạt được một số kết quả sau đây:

1. Trình bày về tập mờ cũng như về logic mờ. Đây là một lĩnh vực được áp dụng rất

nhiều trong khoa học công nghệ, từ đó có được một khung nhìn tổng quan nhất. Đặc

biệt đã tiếp cận đến bài toán phân cụm, phân tích được giải thuật này.

2.

Trình

bày về

lý

thuyết

đại


truyền. Đây là phần phát triển thêm của luận văn. Vì luận văn chọn phương án tối ưu

tham số đầu vào thì tỉ lệ nhận dạng mẫu đúng cao hơn rất nhiều khi chưa tối ưu bộ số

gia tử. Đề xuất hướng nghiên cứu tiếp theo:

1. Tối ưu được thuật toán khi chọn được bộ số gia tử.

2. Áp dụng giải thuật phân cụm để thực hiện trên các bài toán nhận dạng mẫu, phân

cụm ảnh…