Trần Mạnh Tuấn và Đtg
Tạp chí KHOA HỌC & CÔNG NGHỆ
90(02): 87 - 92
KẾT HỢP GIẢI THUẬT DI TRUYỀN VỚI PHÂN CỤM LOẠI TRỪ TRONG TỐI
ƢU HÓA THAM SỐ ĐIỀU KHIỂN
Trần Mạnh Tuấn1*, Nguyễn Thị Linh1, Vũ Đình Minh2
Trường ĐH CNTT&TT, 2Trường CĐ Công nghiệp Thái Nguyên – ĐHTN
TÓM TẮT
Dữ liệu trong các thiết bị điều khiển thƣờng bị nhiễu bởi nhiều loại dữ liệu khác nhau. Việc hiệu
chỉnh, tinh chỉnh và kiểm tra dữ liệu dùng trong các hệ thống điều khiển là cần thiết. Nghiên cứu
này đề xuất phƣơng pháp phân cụm loại trừ và giải thuật di truyền trong trích lọc dữ liệu từ một
tập dữ liệu ban đầu. Thực hiện phân cụm để loại bỏ phần dƣ thừa, hình thành các luật làm tri thức
đầu vào cho hệ điều khiển. Giải thuật di truyền là công cụ tìm kiếm, xác định các giá trị tối ƣu cho
tập tham số điều khiển.
Từ khóa: Giải thuật di truyền, phân cụm loại trừ, trích lọc dữ liệu, hệ điều khiển, tham số
điều khiển.
MỞ ĐẦU*
Mặc dù khả năng thực hiện của mô hình phụ
thuộc rất nhiều vào chính bản thân mô hình,
nhƣng có một thực tế rằng dữ liệu đóng một
vai trò rất quan trọng trong xây dựng các mô
hình chất lƣợng. Điều này càng đặc thù hơn
cho một mô hình định hƣớng dữ liệu. Dữ liệu
nhiễu sẽ cho kết quả trong một mô hình xây
dựng không phù hợp. Khi đó, các mô hình
điều khiển cần dữ liệu đƣợc chuẩn hóa. Nhƣ
vậy, kết quả thu đƣợc từ mô hình điều khiển
sử dụng dữ liệu chuẩn sẽ đƣa ra dự đoán tốt
và đáng tin cậy. Trong các yêu cầu đặt ra cho
quá trình phân cụm thì yêu cầu về độ chính
xác luôn đƣợc đặt ra hàng đầu, ngoài ra sự kết
hợp các thuật toán phân cụm và giải thuật di
truyền còn đòi hỏi thỏa mãn đƣợc tính tối ƣu
của các luật đƣợc sử dụng. Vì vậy một cách
tiếp cận khác mà bài báo nêu ra đó là sử dụng
phân cụm kết hợp với giải thuật di truyền để
chuẩn hóa dữ liệu cho điểu khiển.
Bài báo đƣợc tổ chức nhƣ sau: Phần 2 trình
bày về hệ thống suy luận mờ, phƣơng pháp
phân cụm và giới thiệu một số thuật toán phân
cụm. Phần 3 trình bày về sử dụng giải thuật di
truyền để tối ƣu hóa các luật đƣợc hình thành
sau quá trình phân cụm. Cuối cùng, phần 4
đƣa ra kết quả cài đặt thực nghiệm
chƣơng trình.
*
Tel: 098 3 668 841; Email: tmtuan@ictu.edu.vn
MỘT SỐ VẤN ĐỀ CƠ SỞ
Hệ thống suy luận mờ
Giả sử với tập dữ liệu có p đầu vào và q đầu
ra trong hệ luật mờ. Theo Mamdani[2] luật
thứ i trong hệ gồm k luật đƣợc viết:
i
i
Ri: If x1 is A1 and x2 is A2 and .. and xp is
i
i
A p then y1 is C1 and y2 is C 2i and...and yq is
C qi
Trong đó:
x j là các biến vào
A ij là giá trị ngữ nghĩa của biến đầu vào
yj là các biến ra
C ij là giá trị ngữ nghĩa của biến đầu ra
Khi K = 7, hàm thuộc với các giá trị ngữ
nghĩa của hệ thống với 2 biến vào và một biến
ra đƣợc miêu tả trên hình 2-1 và hình 2-2:
Hình 2-1: Các giá trị ngữ nghĩa của biến đầu vào
Các giá trị ngữ nghĩa của biến đầu ra trên
hình 2-2:
Hình 2-2: Các giá trị ngữ nghĩa của biến đầu ra
87
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
Trần Mạnh Tuấn và Đtg
Tạp chí KHOA HỌC & CÔNG NGHỆ
Với hệ hai đầu vào và một đầu ra gồm 7 giá
trị ngôn ngữ, thì sẽ có 72 = 49 luật cho xây
dựng hệ suy diễn mờ. Bảng hệ thống luật mờ
cho xây dựng hệ suy diễn mờ có thể thấy trên
bảng 2-1:
90(02): 87 - 92
K
Ekmeans x X xi h
địa phƣơng.
Thuật toán K-Means đƣợc thực hiện qua các
bƣớc sau:
(1). Khởi
tạo các cụm: các tâm ban đầu
K
h( 0) h1 đƣợc chọn ngẫu nhiên
(2). Lặp cho tới khi hội tụ
Gán cụm: Gán mỗi đối tƣợng dữ liệu x vào
A2
A3
A4
A5
A6 A7
A1
C7
C7
C7
C7
C7
C7
C7
A2
C7
C6
C6
C6
C6
C6
C6
A3
C7
C6
C5
C5
C5
C5
C5
cụm h* (tức là tập
A4
C7
C6
C5
C4
C4
C4
C4
argmin x h(t )
A5
C7
C6
C5
C4
C3
C3
C3
A6
C7
C6
C5
C4
C3
C2
C2
A7
C7
C6
C5
C4
C3
C2
C1
Phƣơng pháp phân cụm
Các thuật toán phân cụm thƣờng đƣợc biết tới
nhƣ một cách tổ chức và phân loại dữ liệu
hợp lý. Kết quả của phân cụm là một sự phân
chia dữ liệu thành các nhóm tƣơng đồng. Sự
phân chia không gian nhận đƣợc từ quá trình
phân chia dữ liệu. Mỗi luật tƣơng ứng với
một cụm trong đó các tập mờ không đƣợc
chia sẻ bởi tập các luật mà với số chiều cho
trƣớc, mỗi tập mờ đƣợc gắn với một luật duy
nhất. Các tập mờ kết quả thƣờng rất khó để
biểu diễn một cách rõ ràng.
* Một số thuật toán phân cụm cứng
+ Thuật toán K-Means [2]
K-Means lặp lại nhiều lần quá trình bố trí lại
vị trí của đối tƣợng dữ liệu để phân hoạch một
tập dữ liệu thành K cụm và cực tiểu địa
phƣơng giá trị bình phƣơng trung bình
khoảng cách giữa các đối tƣợng tới tâm cụm
của nó. Cụ thể hơn, với tập dữ liệu
X xi i 1 , xi d thuật toán K-Means
N
tạo ra K phân hoạch X h h 1 của X sao cho
K
nếu
h h1
K
mục tiêu sau:
đại diện cho K tâm thì hàm
đạt cực tiểu
i
h 1
A1
Bảng 2-1. Hệ thống luật mờ cho xây dựng hệ suy
diễn mờ
2
X
( t 1) K
)
h*
h 1
với h* =
2
Ƣớc lƣợng tâm:
h(t 1)
1
X h(t 1)
xX h( t 1)
x
t = t+1
+ Thuật toán K-Medoids
Thuật toán K-Medoids có khả năng khắc phục
đƣợc nhiễu bằng cách chọn đối tƣợng ở gần
tâm cụm nhất làm đại diện cho cụm đó
(medoid). Thuật toán K-Medoids đƣợc thực
hiện qua các bƣớc sau:
(1). Chọn K đối tƣợng bất kỳ trong N đối
tƣợng ban đầu làm các medoid ban đầu
(2). Lặp cho tới khi hội tụ
- Gán mỗi đối tƣợng còn lại vào cụm có
medoid gần nhất với nó
- Thay thế medoid hiện tại bằng một đối
tƣợng không phải là medoid sao cho chất
lƣợng phân cụm đƣợc cải thiện (Chất lƣợng
đƣợc đánh giá sử dụng hàm chi phí, hàm tính
độ phi tƣơng tự giữa một đối tƣợng và
medoid của cụm chứa đối tƣợng đó).
K-Medoids tỏ ra hiệu quả hơn K-Means trong
trƣờng hợp dữ liệu có nhiễu hoặc đối tƣợng
ngoại lai (Outlier). Nhƣng so với K-Means thì
K-Medoids có độ phức tạp tính toán lớn hơn.
Cả hai thuật toán trên để có nhƣợc điểm
chung là số lƣợng cụm K đƣợc cung cấp bởi
ngƣời dùng.
88
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
Trần Mạnh Tuấn và Đtg
Tạp chí KHOA HỌC & CÔNG NGHỆ
* Thuật toán phân cụm mờ C – Means
(FCM) [5]
FCM đƣợc giới thiệu bởi Dunn vào năm
1973. Bezdek đã chứng minh các tính chất
của nó và đề xuất tiêu chuẩn hợp lệ phân cụm
đầu tiên. Mỗi n cặp dữ liệu thuộc về một
trong c nhóm với một hệ số thành viên, u ik
thể hiện mức độ thuộc của mẫu dữ liệu k
trong cụm i. Cho Dik2 là khoảng cách giữa
cặp dữ liệu k và cụm i, về cơ bản đƣợc xác
định theo chuẩn Euclide và tổng quát hơn là:
Dik2 xk vi
xk vi Axk vi
2
T
A
Trong đó x k cặp dữ liệu thứ k đƣợc dùng cho
việc phân cụm, A là một ma trận đối xứng,
xác định dƣơng và v i là một nguyên mẫu của
cụm. Cho U là ma trận hệ số u ik và V ma
trận tọa độ trung tâm. Thuật toán sinh ra U và
V làm cực tiểu hàm tổn thất sau:
n
c
J FCM
u
k 1
Với
i 1
Dik2
ràng
c
u
i 1
m
ik
ik
buộc
(1)
xác
suất:
1; k 1,..., n. và m 1 là mũ mờ.
Sự tối ƣu hàm trên đƣợc thực hiện bằng một
thủ tục tối ƣu lặp. Đầu tiên, các hệ số u ik
đƣợc khởi tạo ngẫu nhiên, sau đó, tại mỗi
bƣớc, hai thao tác sau đƣợc thực hiện thành
công:
(1). Tính toán các trung tâm cụm mờ v i , giả
sử các bậc u ik là các hằng số, dùng phƣơng
n
trình sau: v
i
u
k 1
n
m
ik
u
k 1
xk
m
ik
(2). Tính toán mức độ thuộc u ik , giả sử các
trung tâm v i là các vector hằng, dùng phƣơng
trình:
1
uik
Dik
j 1 D jk
c
2
m1
90(02): 87 - 92
Các thao tác trên đƣợc lặp lại cho đến khi hội
tụ, nghĩa là các tọa độ trung tâm là ổn định
đối với sai số đã cho.
Thuật toán phân cụm FCM thích hợp với các
cụm với hình dạng và kích thƣớc có thể so
sánh đƣợc (là hình cầu khi dùng ma trận đơn
vị) hoặc khi các cụm đƣợc phân chia rõ ràng.
Nguyên mẫu cụm là các điểm dữ liệu đƣợc
chọn làm trung tâm cụm.
Input : Số cụm k và tham số mũ m cho hàm
tiêu chuẩn J
OutPut: c cụm dữ liệu sao cho hàm mục tiêu
(1) đạt giá trị tối thiểu.
Begin
(1). Nhập giá trị cho hai tham số k (1
>pm2,pm3 để giảm số luật hiện diện
trong mỗi cá thể nhằm tìm ra cá thể tốt, từ đó
nhận đƣợc số tối thiểu các luật mà vẫn phân
lớp đúng mẫu học.
Phép lai ghép
Là một phép toán quan trọng trong GA để
tìm kiếm các tính chất hữu ích của cha mẹ.
Mỗi cặp cá thể Sh, Sk đƣợc thực hiện lai ghép
đều với xác suất pc nhƣ sau:
- Chọn các cặp bit si1, i = 1, 2,…, L với xác
suất 0.5, nếu bit si1 đƣợc chọn thì các cặp bit
tiếp theo cũng đƣợc chọn (chọn đủ một luật).
- Trao đổi các cặp bit đã chọn giữa 2 cá thể
h
S , Sk.
- Hai cá thể con cháu mới do lai tạo sẽ
đƣợc thay thế cho hai cá thể cha mẹ trong
thế hệ kế tiếp.
90
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
Trần Mạnh Tuấn và Đtg
Tạp chí KHOA HỌC & CÔNG NGHỆ
Phép chọn lọc
Là quá trình cá thể đƣợc chọn dựa vào giá trị
thích nghi của nó đối với mục tiêu cần đạt
đƣợc bằng cách tạo một vòng quay đƣợc phân
chia thành nhiều phần, mỗi phần thể hiện giá
trị thích nghi của mỗi cá thể. Khi vòng quay
quay, có một viên bi với giá trị ngẫu nhiên
nhỏ hơn tổng các giá trị thích nghi di chuyển
theo hƣớng ngƣợc lại. Khi vòng quay ngừng,
viên bi dừng trên phần chia nào thì cá thể đó
đƣợc chọn. Thuật toán đƣợc mô tả nhƣ sau:
- Tính tổng: SUM (ai (t ))
L
i 1
- Chọn một giá trị để so sánh: Sel
[0;SUM]
- Khởi tạo i = 1;
- Kiểm tra:
While (Sel > ( a i (t )) )
{ Sel = Sel - ( a i (t )) ;
i = i+1;
}
select()=i; /* phần tử thứ i đƣợc chọn
Chiến lƣợc phần tử ƣu tú: Luôn luôn chọn cá
thể có giá trị thích nghi cao nhất trong thế hệ
P(t) để đƣa trực tiếp vào thế hệ kế tiếp P(t+1)
khi thực hiện phép toán chọn lọc nếu nó chƣa
đƣợc chọn để đảm bảo các thế hệ kế tiếp
không đánh mất truyền thống thích nghi tốt
nhất và nhờ đó cải thiện sự tiến hóa một cách
liên tục.
Hiệu chỉnh độ tin cậy trong thuật giải GA
Để tăng khả năng phân cụm đúng 100% các
mẫu học với chỉ một số ít luật, cần phải thay
đổi độ tin cậy của mỗi luật thông qua sự
thƣởng, phạt từng luật bằng cách đƣa thêm
một thủ tục hiệu chỉnh độ tin cậy vào quá
trình thực hiện giải thuật di truyền. Với một
mẫu dữ liệu học Xp và với số lần lặp xác
định, độ tin cậy đƣợc tăng hay giảm phụ
thuộc vào việc Xp đƣợc phân cụm đúng hay
sai. Thủ tục nhƣ sau:
Với mỗi mẫu dữ liệu học X p , p = 1, …, P
thực hiện:
- Xếp lớp cho Xp:
90(02): 87 - 92
• Tính độ tƣơng thích của mẫu Xp đối với
từng cụm ci:
k = max{uj1(xp1) uj2(xp2)
…ujN(xpN)CFi|RjS,CFj=ci}
• Nếu i≠j mà Ci = Cj thì Xp không xếp
cụm đƣợc
Nếu ko = max{k ,k = 1, …, K } thì
xếp mẫu Xp vào cụm Cko
- Dùng công thức sau để xác định luật Ri chịu
trách nhiệm phân lớp mẫu Xp
i1 (xp1) i2(xp2) …iN(xpN). CFi = max{j1
(xp1) j2(xp2) …jN(xpN). CFj; RjS }
Trong đó: ij(xpj): là hàm thành viên tập mờ
Aij, i = 1, 2, …, n; j= 1, 2, …N.
Nếu luật Ri xếp đúng lớp cho Xp thì tăng độ
tin cậy của nó theo công thức:
CFi = CFi + 1. (1- CFi)
Nếu luật Ri xếp sai lớp cho Xp thì giảm độ tin
cậy của nó theo công thức:
CFi = CFi - 2.CFi
Với: 1 và 2 là các hằng số trong khoảng
(0;1).
Đánh giá:
Ƣu điểm: Làm tăng khả năng tìm ra cá thể có
các luật phân lớp đúng 100% mẫu học.
Nhƣợc điểm: Cá thể tốt nhất trong thế hệ
trƣớc qua phép chọn phần tử ƣu tú có thể
không còn là cá thể tốt nhất ở thế hệ sau do
độ tin cậy các luật của nó đã bị điều chỉnh.
KẾT QUẢ THỰC NGHIỆM
Với dữ liệu đầu vào là một bảng dữ liệu
(bảng 2-1):
Hình 4-1: Dữ liệu nhập ban đầu
91
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn