Xem mẫu
- Chưong 5
CÁC MẠNG HOẠT ĐỘNG THEO
NGUYÊN TÁC T ự TÓ CHỨC
Trong các phần trước chúng ta đã làm quen với các mô hình hoạt động theo
nguyên tắc “có hướng dẫn”, đó là các mô hình được xây dựng trên cơ sờ các bộ số
liệu gồm các cặp đầu vào - đầu ra tương ứng. Tuy nhiên thực tế ta cũng còn gặp các
vấn đề, trong đó ta chi có một bộ các số liệu mẫu không có đầu ra tương ứng (hay
còn gọi là các mẫu số liệu đơn). Một trong những nhiệm vụ chính khi đó là ta cần
phân tích các sự tương đồng giữa các số liệu, phân nhỏm hay khoanh vùng các số
liệu giống nhau,... Các nhiệm vụ đó được gọi là quá trình “tự tổ chức” hay “tự phân
nhóm” (self-organizing) bộ số liệu. Trong chương này, ta sẽ đề cập tới một trong
những cấu trúc mạng giải quyết bài toán này, đó là mạng Kohonen (hay còn gọi là
mạng SOM - S e lf - Organizing Map) do Kohonen đề xuất [Kohonen89].
5.1. MẠNG KOHONEN
Ý tường của việc phân nhóm và tự tổ chức xuất phát từ thực tế não bộ của chúng
ta là một hệ thống rất phức tạp. cấu trúc của não bộ không thống nhất, bao gồm nhiều
vùng khác nhau. Các nghiên cứu về y sinh hiện nay đã tạm chi ra rằng mỗi một vùng
cùa não bộ có cấu trúc khác nhau, số lượng nơ-rôn và cách két nối giữa chúng khác
nhau, đồng thời mỗi vùng lại chịu trách nhiệm khác nhau phục vụ cho con người. Ví dụ
như có những vùng chịu trách nhiệm về các xử lý hình ảnh, xử lý chuyển động, xử lý
âm thanh,... và những vùng này nhận tín hiệu truyền về từ các “cảm biến” khác nhau
của con người. Ta nói rằng mỗi một dạng tín hiệu đặc trưng của con người sẽ được
chuyển vào một vùng đặc trưng tương ứng bên trong não bộ. Do đó khi xây dựng mô
hình toán hợc của mạng Kohonen, ta có tín hiệu đầu vào thuộc về một không gian (mẫu
số liệu) cho trước. Khác với trường hợp mạng MLP, mạng Kohonen hoạt động theo
nguyên tắc “tự tổ chức”, có nghĩa là mạng chì hoạt động với véc-tơ đầu vào X , mà
không có các mẫu đầu ra d, tương ứng. Trong bài toán tự tổ chức, khi cho trước một
tập hợp các mẫu số liệu và số lượng trọng tâm M , ta cần tìm vị trí của M trọng tâm c ,.
105
- Các mẫu và các trọng tâm được biểu diễn dưới dạng véc-tơ có cùng sổ chiều. Đầu vào
có một bộ số liệu gồm p véc-tơ đa chiều:
*, = [*/i.*í2t—.* iv ]e rA^ ' = 1-► p
Ví dụ trên hình 5.1 là một bộ các điểm trẽn mặt phẳng hai chiều có xu hướng tập
trung thành ba nhóm.
Nhiệm vụ phân nhỏm các số liệu này thành M nhóm, mỗi nhóm được đặc tnmg
bởi một trọng tâm (center) Cj =ị c j ỉ , C j 1 , . . . , C j N '^ & R N\ j = 1 -> M . Ví dụ, phân chia
và nhóm các số liệu từ hình 5.1 thành ba nhóm ta có kết quả như hình 5.2.
Hình 5.2. Các số liệu được chia thành ba nhóm vùng
(đặc trưng bời các đường biên và các trọng tàm '*’)
106
- Với bài toán thuộc dạng “tự tổ chức” (self-organizing) thì ta chì có thông tin về
X, chứ không có các thông tin khác. Khi ta có các mẫu số liệu được biểu diễn dưới dạng
các véc-tơ thì mức độ “giống nhau” giữa các mẫu thường được xác định thông qua
khoảng cách giữa các vcc-tơ. Hai véc-tơ có khoảng cách nhỏ sẽ được đánh giá là
giống nhau hom trường hợp khoảng cách giữa chúng lớn. Các trọng tâm của các nhóm
được xác định trên nguyên tắc: “các véc-tơ có khoảng cách gần nhau sẽ được ưu tiên
ghép vào cùng một nhóm”. Thước đo khoảng cách giữa các véc-tơ chủ yếu là sử dụng
công thức ơ -clít:
x . c e R * : < / ( x , c ) = | | x - c | | = ^ > ] ( x (. - c , . ) 2 (5 .1 )
Tuy nhiên trong các công trình về mạng tự tổ chức, ta cũng có thể gặp các công
thức tính khoảng cách khác như [Deza09]:
1. Khoáng cách tích vô hướng:
í/(x,c) = 1- X c = 1—llxll •llcll -cos(x,c) (5.2)
2. Khoảng cách Manhattan:
N
(5.3)
i=l
3. Khoảng cách Chebyshev:
d ( \ , c) = max lx -c .l (5.4)
i= i- > N
4. Khoảng cách Minkowski:
'( « . o = ^ i k - c , r (5.5)
Trong trường hợp ta có M trọng tàm e,,( = 1 -> M và một véc-to X thì trong
quá trình hoạt động cạnh tranh, trọng tâm chiến thắng là trọng tâm có khoảng cách
ngắn nhất tới véc-tơ X đang xét.
Ilx - Cwm||=.min J x - C ,|| (5.6)
ĐỔ có dạng biểu diễn tương tự như các mạng nơ-rôn khác, ta thường sử dụng
mô hình như trên hình 5.3, trong đó các giá trị thành phần Cịj (i = ì,...,M ; j = l ,...,N )
của M trọng tâm c, được lưu dưới dạng giá trị của các trọng số ghép nổi giữa đầu vào
Xj và trọng tâm c ,. Mạng trên hình 5.3 có đầu ra của trọng tâm chiến thắng sẽ bằng 1,
các trọng tâm còn lại sẽ bàng 0.
107
- C1 y ^ W in n in g ^ .x )
*1 ---------------►
y2=Winning(c2,x)
X, ►3 ĩ > < / z c2
•
• •
• •
o
• yM=Wínning(cM.x)
XN ----------------- ►
Hình 5.3. Cấu trúc mạng Kohonen kinh điền
Đây là cấu trúc mạng truyền thẳng một lớp. Tất cà N đầu vào được nối với tất cả
M đầu ra thông qua trọng số Cịj . số lượng đầu vào bằng với số chiều của véc-tơ X,
trong khi số lượng đầu ra bằng với số lượng của nhóm mà dữ liệu được chia thành. Tọa
độ Cỳ thứ j của trọng tâm thứ i được coi là hệ sổ đặc trưng của kênh nổi đầu vào thứ j
(là X ) tới trọng tâm. Hệ số đặc trưng này trong các nghiên cứu về mạng nơ-rôn
thường được gọi là trọng số ghép nối (connection weight) hay đom giản là trọng số
(weight). Véc-tơ đầu vào X = [X|,JC2,...,JCA,] và trọng tâm c = [c|,c2,...,c Af] thường
được chuẩn hóa về độ dài 1 (tuy nhiên đây là yêu cầu không bắt buộc).
Để dễ dàng mô tả quá trình hoạt động của mạng, ngoài khái niệm khoảng cách
và khái niệm chiến thắng, ta còn dùng khái niệm “mức độ kích hoạt” (activation level)
của trọng tâm thứ j. Mức độ kích hoạt được xác định trên cơ sở một hàm nghịch biến
với khoảng cách giữa trọng tâm đang xét và véc-tơ đầu vào đang xét. Khoảng cách
càng nhỏ thì mức độ kích hoạt càng lớn. Như vậy trọng tâm chiến thắng là trọng tâm có
mức độ kích hoạt lớn nhất. Một số hàm kích hoạt thường được sử dụng là
[Zimmermann85, LinhOO]:
1. Hàm chuông:
activationc(x) = e (5.7)
2. Hàm Gauss mở rộng:
activationc(x) = (5.8)
3. Hàm tam giác:
0 khi ||x - cll > a
activationc (5.9)
khi ||x - c ||< a
108
- Mồi một trọng tâm sẽ xác định một vùng hoạt động của mình, đó là vùng tập
hợp các điểm trong không gian mà khoảng cách tới trọng tâm đó là bé nhất so với
khoảng cách tới các trọng tâm khác.
Ví dụ trên hình 5.4a với ba trọng tâm, ta thấy không gian được chia thành ba
vùng như trên hình 5.4b. Các phân chia này (còn được gọi là phân chia Voronoi do tác
giả Voronoi đề xuất lần đầu) có các đường biên giới là các đường trung trực giữa các
cặp điểm trọng tâm (nếu ta sử dụng công thức khoảng cách ơ-clít).
C1
°2 ¿3
- Ngoài việc định nghĩa các véc-tơ trọng tâm, Kohonen còn đưa ra đề xuất về
mạng lưới liên kết ảo giữa các trọng tâm này đề hình thành “lưới trọng tâm”. Theo đó,
mỗi mạng Kohonen sẽ có một hàm định nghĩa liên kết giữa các trọng tâm. Hai trọng
tâm có liên kết với nhau được gọi là “hàng xóm trực tiếp”, hay còn gọi là hàng xóm
bậc 1. Hai trọng tâm Cj và Cj không có liên kết trực tiếp nhưng nếu tồn tại một chuỗi các
trọng tâm trung gian c kj sao cho ci = c kữ,ckx,...,ckn= c j đồng thời ckJ và c*y+l là
hàng xóm bậc 1 với mọi j = 0 , . . . , n - \ thì c, và Cj được gọi là hàng xóm gián tiếp bậc n
(với n - 1 là số lượng trọng tâm trung gian nhỏ nhất nối giữa Cj và C j). Ta ký hiệu hàm
định nghĩa bậc liên kết hàng xóm giữa hai trọng tâm là G ( c,, c7).
Đe thuận tiện cho việc lập trinh mô phòng, ta thường sử dụng các mạng phân bố
theo lưới hai chiều với các cấu trúc hình chừ nhật, hình tam giác, hình lục giác,... như
trên hình sau:
Hình 5.6. Một số cấu trúc liên kết lưới giữa các trọng tâm trong mạng Kohonen
a) Lưới vuông; b) Lưới tam giác; c) Lưới lục giác.
Khi các trọng tâm được liên kết với nhau theo lưới và nếu một trọng tâm dịch
chuyền thì sẽ kéo theo các trọng tâm khác cũng dịch chuyển, nhưng mức độ dịch
chuyển sẽ tỷ lệ nghịch với bậc hàng xóm giữa mỗi trọng tâm với trọng tâm dịch
- chuyền chính. Các hàng xóm bậc 1 sẽ dịch chuyển nhiều nhất, các hàng xóm bậc cao
hơn sẽ dịch chuyển ít hơn.
í---------
- Đầu vào của các thuật toán học cho mạng Kohonen bao gồm một tập hợp p mẫu
sổ liệu X, e R iV với / = 1,2,...,/? và số lượng các véc-tơ trọng tâm cần xác định M.
Kết quà cùa quá trình học là vị trí của M trọng tâm c, € R ,v với / = 1,2,...,A /. Quá
trình học của mạng Kohonen cũng sẽ là một quá trình lặp.
a) Thuật toán WTA
Thuật toán trực tiếp đầu tiên là thuật toán WTA ( Winner Takes All) được thực
hiện theo trình tự các bước như sau:
Bước 1: Khởi động với chi số mẫu số liệu i = 1.
Bước 2: Tuần tự với các giá trị i = 1,2..... p , ta xử lý véc-tơ X,: xác định các
khoảng cách từ véc-tơ X, tới các nơ-rôn trọng tâm c ■, từ đó xác định nơ-rôn chiến
thắng N w là nơ-rôn có khoảng cách ngắn nhất tới véc-tơ X ,.
Bước 3: Cập nhật các trọng số (tọa độ) của nơ-rôn chiến thắng theo hướng dịch
chuyển về gần phía véc-tơ đầu vào X , .
Bước 4: Tăng i lên 1 vào quay lại bước 2.
Hình 5.8. Vị trí b ốn v é c - tơ đ ầ u và o Xi, Xỉ, X}, x4 và hai trọng tằm Ci, Cỉ. K hi x ét v ế c - t ơ x , thì
khoáng cách d u < d 12 nên trọng tâm Ci chiến thắng
Hình 5.9. Trọng tâm Ci được dịch chuyển về phía v é c -tơ Xí còn trọng tám Cỉ dứng yên
- Lặp lại trình tự này nhiều lần đưa mạng tới một trạng thái được sấp xếp, trong đó
mỗi nơ-rôn biểu diễn một nhóm dữ liệu riêng biệt. Mô tả minh họa một bước học cho
trường hợp bốn véc-tơ mẫu và hai trọng tâm được thể hiện trên hình 5.8 và hình 5.9.
Thuật toán này dược gọi là WTA do khi xừ lý một mẫu sổ liệu, chi duy nhất có
nơ-rôn chiến thắng được dịch chuyển về phía gần với số liệu đang xét còn toàn bộ các
nơ-rôn còn lại đứng yên.
Trong thuật toán trực tuyến chuẩn, chúng ta cập nhật trọng số của nơ-rôn chiến
thắng N w theo luật sau:
(5.10)
trong đó: t - chi số thời gian rời rạc; - véc-tơ trọng số của nơ-rôn chiến thắng
Nịỳ, rj(t) - giá trị của bước học tại thời điểm t.
Hệ số bước học rj(t) được chọn trong khoảng giá trị (0,1) (0 tưcmg ứng với
không dịch chuyển c^r+l) = , 1 - dịch chuyển hoàn toàn CN về p h ía x ,: = X,).
Đe quá trình học ổn định, ta sẽ sử dụng các hệ số học giảm dần theo thời gian. Quá
trinh học sẽ dừng lại khi đạt được số bước lặp chọn trước hoặc khi hệ số bước học quá
nhò rj(t) < £ , với £ là ngưỡng giá trị cho trước.
b) Thuật toán WTM (Winner Takes Most)
Thuật toán WTA có ưu điểm nổi bật là đorn giản, chi cần xử lý tuần tự từng số
liệu và từng trọng tâm. Nhược điểm chính của WTA là có thể xảy ra hiện tượng một số
nơ-rôn không bao giờ chiến thắng và sẽ không phải giờ được dịch chuyển vị trí trong
quá trình học. Dẻ khắc phục nhược điểm, ta có thẻ sử dụng thuật toán WTM, trong đó
ngoài nơ-rôn chiến thắng, các nơ-rôn "lân cận" với nơ-rôn chiến thắng cũng sẽ được
dịch chuyển về hướng các số liệu, nhưng với mức độ ít hon. Giải pháp này sẽ làm giảm
đáng kể khả năng một nơ-rôn không được dịch chuyển trong toàn bộ quá trình học.
Trọng số cùa các nơ-rôn trong thuật toán WTM:
c , ( f + 1 ) = c y (r) + rjj(t)G(Cj,cNw ) [ x ( 0 - c y( 0 ] (5.11)
Các công thức khác nhau trong việc lựa chọn hàm lân cận G(Cj,x(t)) dẫn tới
nhiều thuật toán học khác nhau. Một thuật học qơ bản là thuật toán Kohonen với hàm
Gaussian, trong đó:
113
- (5.12)
trong đó d 2(Cj,x) là khoảng cách Euclidean giữa véc-tơ trọng số cùa nơ-rôn thứj và
nơ-rôn thắng N w và ơ là hệ số vùng lân cận và sẽ giảm theo quá trình học.
c) Thuật toán Neural Gas
Theo công thức (5.12) thì các nơ-rôn ở xa có độ dịch chuyển vẫn bị tác động
mạnh bời khoảng cách từ nơ-rôn đó tới điểm mẫu đang xét. Đe giảm bớt sự ảnh ường
này ta có thể sử dụng một thuật toán mạnh khác được gọi là thuật toán khí nơ—ròn,
trong đó hàm lân cận được định nghĩa theo vị trí sắp xếp của khoảng cách giữa véc- tơ
đầu vào X và véc-tơ trọng số của nơ-rôn. Trong cách tiếp cận này, chúng ta sắp xếp
các nơ-rôn theo những khoảng cách này, tức là:
dị
- Thuật toán này có thể được tóm tất như sau:
1. Chọn một tập các nhóm khởi đầu C / , C 2 ....C M , tùy ý.
2. Đối với từng mẫu số liệu X ị , ta xác định trọng tâm c gần nhất để xếp X,
vào nhóm thứj đó.
X, GC,J neu X,- - c , = min x, -c,.
II 711 k = \ _ ; M II
3. Đối với từng nhóm thứ j = 1,2,..., A/ , tính toán các nguyên mẫu nhóm mới là
trung bình cộng của tất cả các véc-tơ trong nhóm j.
= - Z «I (5.17)
nj x,eC j
M
trong đó tĩj chỉ số lượng v éc-tơ x( được gán với nhóm thứ j ( = p ). Nếu còn có ít
i=1
nhất một trong số M trọng tâm có tọa độ được thay đổi đáng kể trong quá trình cập
nhât trên (tương đưamg với điều kiên max - c • > E với ngưỡng £ chon trước)
1 1II
thì quay trở lại bước 2 để tiếp tục điều chình các trọng tâm. Ngược lại thì dừng quá
trình học.
Hình 5.10. Trong bước tính toán trên, các véc tơ X ì và x2 thuộc về nhóm Ci, các v é c -tơ x 3
và X i thuộc vè nhóm Cĩ , do đó trong quá trình cập nhật, Ci sé dịch chuyển về phía
trung điểm của X» và Xz còn Cĩ sẽ dịch chuyển về phía trung điềm cùa x3 và X ạ
Trên hình 5.11 là ví dụ minh họa quá trình học mạng Kohonen theo thuật
toán K-mean cho mạng có cấu trúc lưới hình chữ nhật. Ta có thể nhận thấy sự biển
dạng của lưới chữ nhật đề các trọng tâm có thể được đặt vào các khu vực có số liệu
tập trung.
115
- (c) (d)
Hình 5.11. Kết quà học mạng Kohonen với 30 trọng tâm có liên kết mạng lưới chữ nhật
theo thuật toán K-means
(a) Sau 1 bước học; (b) Sau 3 bước học; (c) Sau 10 bước học; (d) Sau 100 bước học.
Tuy nhiên do việc tồn tại lưới liên kết dạng hình chữ nhật (một trọng tâm có bốn
trọng tâm lân cận) mà ta cũng có thể nhận thấy một số “mắt lưới” bị rơi vào vùng
không có số liệu. Nhược điểm này tiếp tục được quan sát thấy trên hình 5.12 cho mạng
cỏ cấu trúc lưới tam giác.
116
- (c) (d)
Hinh 5.12. Két quả học mạng Kohonen vói 30 trọng tâm có liên két mạng lưới tam giác
theo thuật toán K-means
(a) Sau 1 bước học; (b) Sau 3 bước học; (c) Sau 10 bước học; (d) Sau 100 bước học.
Để khắc phục được nhược điểm của cấu trúc mắt lưới, trong thuật toán C-mean
sau đây, ta sẽ bỏ quan hệ ràng buộc mắt lưới. Khi đó các trọng tâm có thể được
chuyển động tự do, lượng chuyển dịch chi phụ thuộc vào khoảng cách từ trọng tâm
tới các vcc-tơ mẫu số liệu chứ không phụ thuộc vào quan hệ tương đối giữa các
trọng tâm với nhau.
117
- b) Thuật toán C-mean
Trong thuật toán C-mean, các trọng tâm được xác định với sự hỗ trợ của một
đại lượng Uịj mới được gọi là giá trị phụ thuộc của véc-tơ X j vào trọng tâm c,-. Theo
thuật toán Kohoncn kinh điển thì mỗi một véc-tơ mẫu số liệu X / được phân chia thuộc
về một nhóm duy nhất mà cỏ trọng tâm c, gần nhất tới véc-tơ đó, khi đó thì giá trị phụ
thuộc của một véc-tơ X tới mỗi trọng tâm c, chi có the nhận một trong hai giá trị là 0
hoặc 1. Cụ thể:
jl nếu :||xy —C j II
u ij = / ( X7>c . ) = (5.18)
(o nếu ngược lại
Trong thuật toán C-mean, các tác giả đă làm “mềm” hóa yêu cầu trên trở thành
giá trị phụ thuộc của một véc-tơ X ■tới mỗi trọng tâm c, có thổ nhận các giá trị thực
trong đoạn [0,1] và tỷ lệ nghịch với khoảng cách giữa mẫu sổ liệu tới trọng tâm. Điều
này có nghĩa là một mẫu sổ liệu X j có thể thuộc về nhiều trọng tâm nhưng hệ số phụ
thuộc vẫn phải thỏa mãn hai điều kiện sau:
1. Tổng hệ số phụ thuộc của một mẫu tới tất cả các trọng tâm bằng 1:
M
Z Mý = 1 (5.19)
i=l
với tất cả các điểm dữ liệu j = 1,2,...,p.
2. Hệ số phụ thuộc tỷ lệ nghịch với khoảng cách: trọng tâm gần nhất sẽ tương
ứng với hệ số phụ thuộc cao nhất.
Từ tính chất 1 (công thức (5.19)) ta dễ dàng có:
M p p M
Ỹ ỉ . uu = z L Ĩ L uij = p (5.20)
i=l 7=1 7=1 i=l
Thuật toán học C-mean có hàm mục tiêu của quá trình học được định nghĩa như
sau [Dunn73, Bezdek81]:
(5.21)
- (5.22)
trong đó Ả là các nhân tử Lagrange cho các ràng buộc của phưcmg trình trên. Các
điều kiện cần thiết để tối thiểu hàm Lagrange như sau [Dunn73, Bezdek81]:
C; = (5.23)
và:
(5.24)
“ý ( \1/(«I-I)
Z M d
JL
k= \ dMj
trong đó dụ = c, - X j ị - khoảng cách giữa trọng tâm c, và véc-tơ dữ liệu Xj. Từ đó ta
có thuật toán phân nhóm C-mean có thể được phát biểu như sau:
1. Khởi tạo ngẫu nhiên các vị trí của các trọng tâm c, trong miền xác định cùa
các mẫu số liệu.
2. Xác định ma trận u từ công thức (5.24).
3. Tìm M trọng tâm c, sử dụng phương trình (5.23).
4. Tính toán hàm mục tiêu theo (5.21). Ncu giá trị của E nhỏ hơn một ngưỡng
cho trước hoặc các giá trị trọng tâm mới thay đồi nhỏ hơn mức ngưỡng cho trước sau
một vòng lặp thì sẽ dừng thuật toán, ngược lại ta sẽ quay lại bước 2 với các vị trị mới
cùa trọng tầm vừa xác định được.
Quá trình này được lặp lại nhiều lần sẽ dẫn tới một cực tiểu nào đó của /r, tuy
nhiên nó không nhất thiết là dạt tới giá trị cực tiểu toàn cục. Với các giá trị khởi tạo
ngẫu nhiên ban đầu khác nhau, ta có thể thu được các kết quả cuối cùng hoàn toàn khác
nhau. Vì vậy trong các công trình nghiên cứu, ta có thc gặp nhiều đề xuất về điều kiện
dừng hoặc một số tiêu chí bồ sung khác để đánh giá chất lượng của việc phân nhóm, để
tù đó có thẻ chọn được kết quả phù hợp.
Trên hình 5.13 là minh họa kết quà học của mạng Kohonen theo thuật toán
C-mean cho bộ số liệu mẫu phân bố giống như trong hai ví dụ từ các hình 5.11 và
5.12. Ta có thể nhận thấy do không còn ràng buộc lưới nên các trọng tâm đã được dịch
chuyển tự do và toàn bộ các trọng tâm đã nằm vào giữa các vùng sổ liệu, không còn
hiện tượng trọng tâm bị nằm ở vùng trống ờ giữa.
119
- (b)
*. . , / .--- >
J .•» •• • i ' 1•. •••>'
09
• . •' .ý •• ••• • • • '• t
08 ••• • • 08 • >•••*•• • ..
. * >• •
07
\* *v • 0. 7
• t \• Â\ '
oe
• . . • • • 06 #
. • . . •
• ••• ••• * • • • ••%•••+• ••
05 05
• . *
04 • • 04
•\ • • ;
> .
03 . 0. 3 * *
*• •
02
•• •í* 02 •• • #
••
• • ••• .• . • • . A .
. . . . . .. ... A r •' . - •_!_
.* • . ••V f~.• .• /• •
01 02 03 04 05 06 07 0 8 09 01 02 03 04 05 06 07 08 0
(c) (d)
Hình 5.13. Két quả học mạng Kohonen với 30 trọng tàm theo thuật toán C-means
a) Sau 1 bước học; b) Sau 3 bước học; c) Sau 5 bước học; d) Sau 10 bước học.
Khả năng tự động xác định vị trí các ừọng tâm của các vùng số liệu trong một
bộ sổ liệu cho trước cùa mạng Kohonen có thể được ứng dụng trong khá nhiều bài toán
khác nhau. Phần tiếp theo ta sẽ điểm qua một số ví dụ minh họa cho mạng Kohonen
với các trường hợp từ đơn giản cho đến phức tạp.
12 0
- 5.3. Vì DỤ ỨNG DỤNG MẠNG KOHONEN
(a)
Hình 5.14. Mẫu phân bố số liệu và ba trọng tâm tương ứng (a) cùng với ba vùng phân loại
và kết quả phân loại từng vùng (b)
Một trong những ứng dụng điển hình cùa mạng Kohonen là sử dụng trong nhận
dạng và phân loại đối tượng đầu vào. Mỗi một trọng tâm Cy đặc trung cho một nhóm
hay một tính chất nào đó. Ví dụ như trọng tâm Cị đặc trưng cho vùng các véc-tơ của
nhóm V thì khi véc-tơ đầu vào X gần với trọng tâm Cị nhất, ta sẽ kết luận X có tính
chat V và thuộc về nhóm này. Trên hình 5.14 là minh họa cho vấn đề này. Sau khi trên
cơ sở bộ mẫu số liệu hình 5.14a, ta tìm được ba trọng tâm C |, C2 và C3. Từ đó, dựa trên
nguyên tắc khoảng cách ngẩn nhất, miền xác định của các mẫu được chia thành ba khu
vực. Khi ta có một mẫu số liệu mới, ta xét mẫu đó thuộc vào miền nào và trọng tâm c,
tương ứng sẽ được coi là đặc trưng cho véc-tơ số liệu đang xét, đồng thời véc-tơ số
liệu đang xét sẽ được coi là có cùng đặc tính với các véc-tơ số liệu khác cũng nàm
trong vùng Cj.
5.3.1. Xác định mẫu cho số liệu hai chiều
Ta bắt đầu với một ví dụ đơn giản là các điểm phân bố trên không gian harchiều
theo một hàm nào đó. Trên hình 5.15 ta có 101 điểm đầu vào được phân bố dọc theo
hình sin với giá trị bước đều Ax = 0,1.
Sau khi có tập hợp điểm, ta tiến hành phân thành 30 nhóm. Kết quả của quá
trình học bằng thuật toán ngoại tuyến C-mean được trình bày trên hình 5.16, theo đó ta
thấy các trọng tâm (được biểu diễn bằng ‘ © ’) cũng được phân bố đều dọc theo các
khu vực chứa các véc-tơ đầu vào.
121
- 1
08
0.6
0.4
0.2
0
- 0.2
- 0.4
- 0.6
-08
-1
0 1 2 3 4 5 6 7 8 9 10
Hình 5.15. Mẩu 101 điểm số liệu 2-D phân bố theo hàm sin
1
08
06
04
0.2
0
-0 2
- 04
-0 6
- 08
-1
0 1 2 3 4 5 6 7 8 9 10
Hình 5.16. Kết quà phân nhóm và các trọng tâm ị'* ’) cho số liệu từ hình 5.15
Ta lấy ví dụ thứ hai với các số liệu của bài toán xoáy kinh điền (Spiral Problem)
trong đó các điểm số liệu đầu vào được phân bố dọc theo các đường xoáy trôn ốc.
12 2
- 25
2
15
1
05
0
-05
-1
■1.5 -
-2
-2 .5 -----------------*---------------- ‘---------------- >---------------- 1---------------- »---------------- 1---------------- ‘-----------------
-2 -1 5 -1 -0 5 0 05 1 15 2
Hình 5.17. Mầu số liệu chuẩn spiral
Với tập hợp điểm như trên hình 5.17, ta tiến hành phân thành 40 nhóm. Kết quả
cùa quá trình học bàng thuật toán ngoại tuyến C-mean được trình bày trên hình 5.18,
theo đó ta thấy các trọng tâm (được biểu diễn bằng ‘ © ’) cũng được phân bố đều dọc
theo các khu vực chứa các véc-tơ đầu vào.
2 .5 1----------------- 1---------------- 1---------------- 1---------------- 1---------------- 1---------------- 1---------------- 1----------------
2- • • *
.•
15 .
-2 -1 5 -1 -0 5 0 05 1 1.5 2
Hình 5.18. Kết quả phân nhóm và các trọng tâm ('*') cho số liệu từ hình 5.17
5.3.2. Xác định mẫu cho số liệu đa chiều
Mở rộng cho trường hợp các mẫu số liệu đa chiều, ta sẽ lấy ví dụ với trường hợp
ứng dụng mạng Kohonen trong xừ lý ảnh. Với một ảnh đầu vào cho trước, ta sẽ có một
ma trận điểm ảnh Aự = mã màu tại pixel (điểm ảnh) có tọa độ (ỉ',ý ).
123
- Đe tìm các vùng màu ảnh đặc trưng, ta chia nhỏ ảnh đầu vào thành các ảnh con
có cùng kích thước sRy.sC. Khi đó từ ảnh đầu vào kích thước tR XtC , ta sẽ thu được
íR tC
p = — ■—— ảnh con. Chia tâp hơp này thành M nhóm và xác đinh trong tâm của các
sR sC
nhỏm, ta sẽ tìm được các vùng ảnh con đặc trưng cùa ảnh đầu vào.
Trên hình 5.19 là một ví dụ cùa ảnh đầu vào với kích thước 600 X 800. Ành này
được cắt thành các ảnh con kích thước 20x20 . Ta có tập đầu vào 30 -40 = 1200 ảnh
con. Coi mỗi ảnh con này là một véc-tơ có 20 • 20 = 400 thành phần, ta triển khai thuật
toán học mạng Kohonen để tìm 40 trọng tâm cùa mạng.
Kết quả của quá trình học được thể hiện trên hình 5.20.
Hình 5.19. Ảnh đầu vào được sừdụng để kiểm tra mạng Kohonen
Hình 5.20. 40 ảnh con đặc trưng cho tập 1200 ảnh con của ảnh đầu vào
12 4
nguon tai.lieu . vn