Tóm tắt Luận án Phát triển các cấu trúc, thuật học của mạng nơron tự tổ chức

là tỉ lệ học tại lần lặp thứ t, với  0 1L t  ).  L t có thể là một hàm tuyến tính, hàm mũ... Công thức (1.5) là một ví dụ của hàm xác định tỉ lệ học.   0 1 t L t L T        (1.5) trong đó: L0 là tỉ lệ học khởi tạo (0<L01); L(t) là tỉ lệ học của mạng tại lần học thứ t; T là tổng số lần học của mạng. Do sự ảnh hưởng của các mẫu vào đối với từng nơron cụ thể khác nhau, nên tỉ lệ học của mỗi nơron có thể khác nhau. Việc cập nhật trọng số nơron có thể dựa vào tỉ lệ học riêng biệt của từng nơron.          w 1 w wi i i ci it t L t h t x t      (1.6) trong đó,  iL t là tỉ lệ học tại lần học thứ t của nơron thứ i, được xác định theo công thức:         1 1 i i ci i L t L t h t L t    (1.7) Sau khi khởi tạo (Bước 1), quá trình huấn luyện mạng sẽ lặp lại nhiều lần các bước 2, 3 và 4 cho đến khi thỏa mãn một trong các điều kiện dừng: đạt được số lần huấn luyện nhất định (T lần) hoặc mạng đạt được trạng thái cân bằng. 1.2.3. Đánh giá chất lượng bản đồ đặc trưng của mạng nơron tự tổ chức Hai độ đo thường được sử dụng để đánh giá chất lượng bản đồ đặc trưng của SOM, gồm: Lỗi lượng tử (QE- Quantization Error) và Lỗi hình trạng (TE- Topographic Error). 4 a) Lỗi lượng tử: Lỗi lượng tử là độ đo đánh giá chất lượng học của mạng thông qua độ khác biệt trung bình của các mẫu đầu vào so với các nơron chiến thắng (BMU) tương ứng của nó. Nó thể hiện độ chính xác của dữ liệu đại diện, do đó giá trị này càng nhỏ thì càng tốt (Kohonen, 2001).     1 1 T c t QE x t w t T    (1.8) b) Lỗi hình trạng: Lỗi hình trạng là độ đo đánh giá độ bảo toàn quan hệ lân cận của dữ liệu (topology preservation) (Kiviluoto, 1996), (Mwasiagi, 2007). Nó được xác định bằng tỉ số của số lần nơron khớp nhất (BMU1) không liền kề với nơron khớp thứ hai (BMU2) trên tổng số lần huấn luyện, do đó giá trị này càng nhỏ thì càng tốt.    1 1 T t TE d x t T    (1.9) trong đó:  x t là mẫu đầu vào của mạng tại lần huấn luyện thứ t;    1d x t  nếu BMU1 và BMU2 của  x t không liền kề, ngược lại    0d x t  ; T là tổng số lần huấn luyện. 1.3. Hạn chế của mạng nơron tự tổ chức và các biện pháp khắc phục Một số hạn chế của SOM đã được các nhà nghiên cứu chỉ ra trong các biến thể của SOM như: phải xác định trước hình trạng và kích thước bản đồ; bản đồ đặc trưng thiếu tính trực quan; thiếu cơ chế xác định ranh giới giữa các vùng dữ liệu trên bản đồ đặc trưng; việc tìm BMU mất nhiều thời gian; thứ tự của các mẫu vào ảnh hưởng tới xu hướng biến đổi của bản đồ; không có thông tin chỉ dẫn trong quá trình huấn luyện... 1.4. Kết quả nghiên cứu trong và ngoài nước về cải tiến cấu trúc, phương pháp học của mạng nơron tự tổ chức 1.4.1. Kết quả nghiên cứu trong nước Cho đến nay nghiên cứu sinh chưa tìm thấy kết quả nghiên cứu nào về cải tiến cấu trúc hoặc quá trình học của mạng nơron tự tổ chức. Hầu hết các nghiên cứu liên quan chỉ giới hạn trong phạm vi ứng dụng mạng nơron tự tổ chức trong các bài toán ứng dụng thực tiễn. Các công trình đã công bố chủ yếu là các luận văn thạc sĩ. 1.4.2. Kết quả nghiên cứu ngoài nước Có nhiều nghiên cứu được công bố ngoài nước về cải tiến cấu trúc và phương pháp học của mạng nơron tự tổ chức (gọi chung là các biến thể). Về mặt cấu trúc, các biến thể của mạng nơron tự tổ chức có thể được chia thành 2 nhóm: các biến thể không sử dụng cấu trúc cây và các biến thể sử dụng cấu trúc cây. Về mặt phương pháp học, bên cạnh các biến thể sử dụng phương pháp học không giám sát truyền thống, một số biến thể đã sử dụng phương pháp học giám sát hoặc bán giám sát. Gần đây nhiều nhà nghiên cứu tiếp tục đưa ra các biến thể về phương pháp học của SOM, cụ thể: các biến thể SOM có giám sát có thể kể đến như (Papadimitriou, 2001), (Thammano, 2007), (Lawawirojwong, 2013), (Groof, 2014), (Gil, 2015); các biến thể SOM bán giám sát: (Li, 2013), (Allahyar, 2015), (Abaei, 2015). 1.5. Đặc điểm chung của các phương thức cải tiến mạng nơron tự tổ chức Các biến thể của SOM thường sử dụng một số phương thức cải tiến như: bộ đếm BMU; bộ đếm “tuổi”; lỗi lượng tử vượt ngưỡng; mở rộng mạng từ nơron ở biên; “đóng băng” nơron ở trung tâm; tăng trưởng, phân tầng và thêm thông tin hướng dẫn trong quá trình học. 5 1.6. Kết luận chương 1 Chương này đã trình bày các kiến thức nghiên cứu tổng quan về: Mạng nơron nhân tạo và xu thế phát triển mạng nơron nhân tạo cho đến hiện nay; Mạng nơron tự tổ chức và các biến thể của nó. Phân tích các hạn chế của mạng nơron tự tổ chức và biện pháp khắc phục; Tổng hợp đặc điểm chung của các phương thức cải tiến mạng nơron tự tổ chức. CHƯƠNG 2: HAI PHƯƠNG THỨC CẢI THIỆN CHẤT LƯỢNG BẢN ĐỒ ĐẶC TRƯNG CỦA MẠNG NƠRON TỰ TỔ CHỨC 2.1. Tổng quan về cải thiện chất lượng bản đồ đặc trưng của mạng nơron tự tổ chức Phương thức truyền thống để cải thiện chất lượng bản đồ đặc trưng của SOM là “thử sai” nhiều lần với các tham số khác nhau của mạng. Ngoài ra, hướng nghiên cứu cải tiến thuật toán học của SOM để cải thiện chất lượng bản đồ đặc trưng cũng được các nhà nghiên cứu quan tâm. Điển hình là các nghiên cứu của (Germen, 2002), (Germen, 2005), (Neme, 2008), (Lopez-Rubio, 2013), (Neme, 2014), (Kamimura, 2014). Tuy nhiên, chưa có giải pháp nào có thể giảm đồng thời cả QE và TE mà luôn đúng cho mọi tập dữ liệu. 2.2. Điều chỉnh tham số của hàm lân cận để cải thiện chất lượng bản đồ đặc trưng 2.2.1. Một số dạng hàm lân cận của mạng nơron tự tổ chức Ngoài hàm lân cận Gaussion được sử dụng phổ biến, một số loại hàm lân cận khác cũng được đề cập như: Hàm “nổi bọt - bubble” (Kohonen, 2001); hàm lân cận bất đối xứng (Aoki, 2007) và (Ota, 2011); quy tắc cập nhật trọng số “ngư dân - fisherman” (Lee, 2002). Tuy nhiên, theo các tác giả thì hàm lân cận Gaussian vẫn cho kết quả tốt nhất, do vậy nó vẫn được sử dụng phổ biến đối với SOM và các biến thể của SOM. 2.2.2. Adding adjust parameter for Gaussian neighborhood function Công thức (1.4) có thể được viết lại ở dạng tổng quát như sau:     exp p c i ci p c r r h t q N t          (2.1) trong đó: q và p là hai tham số điều chỉnh, với q0 và p0. Nhận thấy, giá trị của hci(t) phụ thuộc vào khoảng cách từ vị trí (ri) của nơron đang xét (nơron i) tới vị trí (rc) của nơron chiến thắng (BMU hay nơron c) và các tham số q, p. Nếu nơron đang xét là BMU, tức là 0c ir r  thì   1cih t  ; Nếu nơron đang xét nằm ở vị trí xa nhất trong bán kính lân cận Nc(t), tức là  c i cr r N t  thì giá trị hàm lân cận phụ thuộc vào tham số q, với:    expcih t q  (2.2) Hình 2.2 minh họa hàm lân cận  cih t trong trường hợp bán kính lân cận   10cN t  , với các tham số p=2 và q=0.5, 1, 2, 4, 8, 12. a) Tham số q Về nguyên tắc, khi các nơron láng giềng trong bán kính lân cận của BMU bị điều chỉnh theo mẫu đầu vào ở lần học hiện tại càng lớn thì sự khác biệt của chúng với các mẫu đầu vào khác ở những lần học sau càng cao. Đây là nguyên nhân dẫn tới lỗi lượng tử QE tăng. Do vậy, muốn giảm QE ta phải giảm mức độ và phạm vi tác động của mẫu vào, tức là việc tăng tham số q sẽ làm giảm lỗi lượng tử QE. 6 Tuy nhiên, nếu q quá lớn thì khả năng học của mạng bị hạn chế, tức là hình trạng mạng có thể ít thay đổi và phần nào phụ thuộc vào việc khởi tạo trọng số của nơron. Mặt khác, bán kính lân cận Nc(t) có thể vô hình chung bị co lại, do hàm   0cih t  đối với các nơron ở vị trí xa trong bán kính lân cận (tức là các nơron ở vị trí xa trong bán kính lân cận không được điều chỉnh hoặc điều chỉnh không đáng kể theo mẫu đầu vào). Vì vậy, để đảm bảo tất cả các nơron trong bán kính lân cận Nc(t) được tác động bởi mẫu đầu vào thì tham số q không được phép quá lớn. Ví dụ, trường hợp q=8 và 12, hàm   0cih t  khi khoảng cách c ir r tiến dần tới Nc(t). Trong trường hợp q0, hàm mũ Gaussian có kết quả tương tự hàm “nổi bọt” Bubble, tức là hci(t)1 với mọi nơron trong bán kính lân cận Nc(t). Kết quả là, nếu bán kính lân cận Nc(t) càng lớn thì bản đồ đặc trưng càng có xu hướng biến đổi cục bộ theo mẫu đầu vào thứ t. Điều này làm giảm khả năng nhớ của mạng đối với những lần học trước. Như vậy, lỗi hình trạng TE có thể phụ thuộc vào việc khởi tạo trọng số nơron nếu q quá lớn, hoặc phụ thuộc thứ tự các mẫu đầu vào nếu q quá nhỏ. Chú ý rằng trọng số khởi tạo của nơron và thứ tự các mẫu đầu vào được xác định ngẫu nhiên. Do vậy, khả năng học hình trạng của mạng tốt nhất khi tham số q không quá nhỏ hoặc quá lớn. b) Tham số p Khi cố định tham số q, nếu tăng tham số p thì hàm hci(t) tăng dần tới 1 đối với các nơron gần phía với BMU, tức là số lượng láng giềng quanh BMU được điều chỉnh với mức độ tương tự như BMU sẽ mở rộng. Điều này làm tăng lỗi lượng tử QE. Nếu tham số p quá lớn thì bản đồ đặc trưng có xu hướng biến đổi cục bộ theo mẫu đầu vào của lần huấn luyện gần nhất (tương tự như trường hợp tham số q quá nhỏ). Tuy nhiên, lỗi hình trạng TE có thể thay đổi không đáng kể, do việc xác định TE chỉ xét trong phạm vi BMU và các nơron láng giềng liền kề của nó. Hình 2. 1 Minh họa hàm hci(t) khi thay đổi giá trị q. hci(t) c ir r Hình 2. 2 Minh họa hàm hci(t) khi thay đổi giá trị p. hci(t) c ir r 7 Hình 2.2 biểu diễn hàm hci(t) gốc (với q=0.5 và p=2) và hàm hci(t) điều chỉnh với tham số q=4 và p=1, 2, 3, 4, 5, 6 trong trường hợp bán kính lân cận   10cN t  . Riêng trường hợp p=1 đồ thị hci(t) tương tự như trường hợp q=8, 12 ở Hình 2.2, tức là lỗi lượng tử QE nhỏ nhất so với các trường hợp p>1, nhưng lỗi hình trạng TE có thể không tin cậy do nó phụ thuộc vào việc khởi trọng số của nơron. Do đó, việc điều chỉnh tham số p có tác động không đáng kể tới việc cải thiện chất lượng bản đồ đặc trưng của mạng nơron tự tổ chức. Nhận xét: Tham số q có ý nghĩa tích cực trong việc cải thiện chất lượng bản đồ đặc trưng của mạng nơron tự tổ chức. Tham số q càng lớn thì QE càng nhỏ, tuy nhiên q đạt giá trị phù hợp nhất khi TE nhỏ nhất. Do vậy, nghiên cứu sinh đề xuất cải tiến hàm lân cận với một tham số điều chỉnh như sau:     2 2 exp c i ci c r r h t q N t          (2.3) 2.3. Thuật toán điều chỉnh trọng số nơron để giảm lỗi lượng tử 2.3.1. Đặt vấn đề Giả sử I là tập dữ liệu huấn luyện, sau huấn luyện ta có:  1 2, ,..., sI I I I (2.4) trong đó: Ii là tập mẫu được đại diện bởi nơron thứ i, với i=1..s; s=ab là tổng số nơron; ab là kích thước lớp Kohonen. Như vậy, mỗi tập con Ii thực chất là một cụm dữ liệu trong trong tập dữ liệu đầu vào, vì thế theo k-means thì các cụm dữ liệu là tốt nhất nếu hàm mục tiêu E tối thiểu: 2 1 i s i i x I E x center     (2.5) trong đó, centeri là tâm cụm thứ i, xác định theo công thức: 1 i i x Ii center x I    (2.6) với, |.| là số phần tử của một tập hợp. Ta thấy, để tối thiểu hóa hàm mực tiêu E phải điều chỉnh các phần tử trong mỗi tập Ii và tâm cụm centeri. Gọi Qi là giá trị lỗi của nơron thứ i, được xác định là tổng khoảng cách của các mẫu dữ liệu thuộc cụm Ii đối với vector trọng số wi, ta có:  , i i i x I Q d x w   (2.7) trong đó: wi là trọng số của nơron i; d(x,wi) là khoảng cách giữa vector x và vector wi, với:  , i id x w x w  (2.8) Về nguyên tắc, số lần huấn luyện mạng càng lớn thì chất lượng bản đồ đặc trưng sẽ càng được cải thiện. Tuy nhiên, tỉ lệ học của mạng là một hàm giảm dần theo thời gian huấn luyện, nên tỉ lệ học L(t)0 nếu tổng số lần huấn luyện T. Tức là, việc tăng số lần huấn luyện mạng quá lớn chỉ làm tăng tổng thời gian tính toán, còn hiệu quả cải thiện chất lượng bản đồ đặc trưng là không cao. 8 Nếu giả thiết rằng L(t)0 (giả thiết này đúng khi T hoặc khi quá trình huấn luyện đã kết thúc), ta có công thức (1.8) tương đương với: 1 1 s i i QE Q N    (2.9) hay: 1 1 i s i i x I QE x w N     (2.10) trong đó: N là tổng số mẫu dữ liệu. Nhận thấy, công thức (2.10) có sự tương đồng với công thức (2.5). Do vậy, để giảm QE thì wi nên được xem xét giống như centeri. Điều này có nghĩa rằng, thay vì cố gắng tăng số lần huấn luyện mạng lên quá lớn để giảm QE ta nên điều chỉnh wi theo tâm cụm centeri. Việc điều chỉnh này chỉ cần thực hiện khi quá trình huấn luyện của mạng đã kết thúc. Ta có bổ đề sau: Bổ đề. Một bản đồ tự tổ chức có lỗi lượng tử nhỏ nhất khi và chỉ khi i iw center , trong đó: wi là vector trọng số của nơron thứ i; centeri là tâm cụm của tập Ii, với i=1..s. Tập Ii bao gồm các mẫu dữ liệu được đại diện bởi nơron thứ i khi quá trình huấn luyện đã kết thúc [6A]. Việc điều chỉnh wi trùng với centeri làm tăng độ chính xác của dữ liệu đại diện, nhưng cũng dẫn tới hệ quả là có một số mẫu dữ liệu cần phải chuyển đổi nơron đại diện cho nó, do nó khớp hơn với một nơron khác (so với nơron mà nó đang thuộc về). Các mẫu dữ liệu cần thay đổi nơron đại diện được gọi là các “phần tử khác biệt” theo định nghĩa dưới đây: Định nghĩa. Một mẫu dữ liệu x được gọi là “phần tử khác biệt” của nơron i đối với nơron j (với j  i) khi và chỉ khi xIi và    , ,j id x w d x w [6A]. Hình 2.4 minh họa x1 là “phần tử khác biệt” của nơron i đối với nơron j, với    1 1 1: , ,i j ix I d x w d x w  ; x2 là “phần tử khác biệt” của nơron i đối với nơron k, với    2 2 2: , ,i k ix I d x w d x w  ; x3Ii nhưng không là “phần tử khác biệt” của nơron i đối với nơron g vì không thỏa mãn điều kiện    3 3, ,g id x w d x w . Định lý. Cho Ii và Ij là hai tập dữ liệu được đại diện tương ứng bởi hai nơron i và nơron j; mẫu dữ liệu x là “phần tử khác biệt” của nơron i đối với nơron j (với xIi, ij); QE là lỗi lượng tử của mạng. Ta có, QE giảm khi và chỉ khi  \i iI I x và  j jI I x  [6A]. Hệ quả. Cho Ii, Ij và Ik là các tập dữ liệu được đại diện tương ứng bởi các nơron i, j và k; mẫu dữ liệu x là “phần tử khác biệt” của nơron i đối với đồng thời cả hai nơron j và k (với xIi, i≠j, i≠k, j≠k). Giả sử, * ( )jQE là lỗi lượng tử của mạng nếu  \i iI I x và  j jI I x  ; * ( )kQE là lỗi lượng tử của mạng Hình 2. 3 Minh họa “phần tử khác biệt” của nơron i. 9 nếu  \i iI I x và  k kI I x  . Ta có, * * ( ) ( )j kQE QE khi và chỉ khi các khoảng cách    , ,j kd x w d x w [6A]. 2.3.2. Thuật toán điều chỉnh trọng số nơron Batch-IMQS Lặp lại hai bước sau cho tới khi thỏa mãn điều kiện dừng: lỗi lượng tử sau khi lặp giảm so với lỗi lượng tử trước khi lặp nhỏ hơn ngưỡng . - Bước 1: Xác định các tập con Ii của I={I1, I2,.., Is}, với i=1..s - Bước 2: Tính các vector tâm cụm centeri, và gán wi = centeri, với i=1..s. Thuật toán có thể giảm lỗi lượng tử của mọi bản đồ mà không quan tâm đến các tham số cấu hình mạng, cũng như không gia tăng thêm các tham số khác. Tuy nhiên, hạn chế của nó là TE tăng tỉ lệ nghịch với QE. 2.4. Các tập dữ liệu sử dụng cho thực nghiệm Sử dụng 12 tập dữ liệu đã được công bố, bao gồm: XOR, Aggregation, Flame, Pathbased, Spiral, Jain, Compound, R15, D31, Iris, Vowel và Zoo. 2.5. Thực nghiệm hàm lân cận đối xứng dạng mũ với tham số điều chỉnh Trường hợp 1: Tham số p cố định, tham số q thay đổi Bảng 2.1 thống kê kết quả thực nghiệm với tham số p=2 và thay đổi giá trị tham số q=0.5, 2, 4, 8, 12. Bảng 2. 1 Kết quả thực nghiệm khi cố định tham số p=2, thay đổi tham số q q 0.5 1 2 4 8 12 XOR 0.1890 0.1585 0.1299 0.1129 0.0902 0.0810 0.0318 0.0223 0.0273 0.0427 0.0705 0.0925 Aggregation 5.9702 5.0643 4.0276 2.9340 2.2819 1.8472 0.0549 0.0362 0.0294 0.0245 0.0424 0.0678 Flame 2.1839 1.9512 1.5194 1.1822 0.9129 0.8206 0.0700 0.0567 0.0407 0.0393 0.0479 0.0833 Pathbased 4.5859 4.0427 3.2618 2.4779 1.9392 1.7401 0.0561 0.0433 0.0373 0.0315 0.0434 0.0794 Spiral 4.7595 4.1719 3.4675 2.9239 2.2975 2.0085 0.0543 0.0404 0.0284 0.0364 0.0413 0.0564 Jain 5.2745 4.4829 3.5726 2.3559 1.6236 1.5234 0.0513 0.0395 0.0313 0.0269 0.0443 0.0637 Compound 4.4205 3.7595 3.1508 2.5672 1.8323 1.7744 0.0624 0.0299 0.0349 0.0400 0.0630 0.0690 R15 2.2226 2.0212 1.8005 1.4606 1.0730 0.9562 0.0722 0.0631 0.0368 0.0274 0.0613 0.1162 D31 4.7676 4.1204 3.3943 2.4569 2.0055 1.6793 0.0479 0.0352 0.0284 0.0207 0.0332 0.0394 Iris 0.7709 0.6430 0.5353 0.4403 0.3773 0.3494 0.0739 0.0548 0.0689 0.0940 0.1196 0.1566 Vowel 2.7459 2.5736 2.3755 2.2005 1.9150 1.7468 0.0537 0.0436 0.0412 0.0448 0.0494 0.0497 Zoo 1.5841 1.4421 1.2468 1.0912 0.9790 0.9156 0.0343 0.0254 0.0169 0.0104 0.0162 0.0208 10 Ghi chú: Các kết quả trong bảng là giá trị trung bình của 10 lần thực nghiệm. Kết quả của mỗi tập dữ liệu trình bày trong hai dòng: dòng thứ nhất biểu diễn độ đo QE và dòng thứ hai biểu diễn độ đo TE. Dữ liệu in đậm là kết quả tốt nhất, trong đó: TE là nhỏ nhất, còn QE nhỏ hơn so với trường hợp sử dụng hàm lân cận gốc (q=0.5). Trường hợp 2: Tham số q cố định, tham số p thay đổi Bảng 2.2 là kết quả thực nghiệm khi cố định tham số q tương ứng với giá trị độ đo đạt được tốt nhất trong Bảng 2.1 và thay đổi giá trị của tham số p=1, 2, 3, 4, 5, 6. Khi p=1, cả QE và TE tăng cao. Khi p2, TE có xu hướng ổn định hoặc tăng nhẹ khi p tăng. Điều này cho thấy tham số p có ý nghĩa không đáng kể trong việc cải thiện chất lượng hình trạng khi đã xác định được tham số q phù hợp; QE có xu hướng tăng với đa số các tập dữ liệu khi tăng p (trừ các tập dữ liệu XOR, Compound và Iris, QE có xu hướng giảm, nhưng TE lại có xu hướng tăng). Điều này cho thấy, p=2 là tốt nhất trong số các giá trị thử nghiệm của p. Bảng 2. 2 Kết quả thực nghiệm khi thay đổi tham số p, cố định tham số q p 1 2 3 4 5 6 XOR (q=1) 0.1754 0.1587 0.1546 0.1518 0.1525 0.1513 0.0534 0.0203 0.0225 0.0244 0.0238 0.0255 Aggregation (q=4) 2.7895 3.0003 3.2722 3.6436 3.6100 3.8718 0.0850 0.0300 0.0277 0.0273 0.0316 0.0282 Flame (q=4) 1.1858 1.2105 1.2306 1.3158 1.4010 1.4209 0.1438 0.0405 0.0284 0.0304 0.0331 0.0330 Pathbased (q=4) 2.5458 2.4759 2.7586 2.8462 2.9400 2.9928 0.1300 0.0313 0.0363 0.0351 0.0349 0.0304 Spiral (q=2) 3.5976 3.4319 3.4334 3.4603 3.4926 3.5797 0.0690 0.0290 0.0265 0.0290 0.0261 0.0264 Jain (q=4) 2.3664 2.3519 2.7136 2.9018 3.1494 3.3035 0.0896 0.0263 0.0270 0.0306 0.0402 0.0403 Compound (q=1) 4.2063 3.7575 3.6224 3.4969 3.5082 3.4913 0.0666 0.0291 0.0337 0.0340 0.0373 0.0398 R15 (q=4) 1.3161 1.4406 1.5544 1.6498 1.6972 1.7376 0.1055 0.0294 0.0367 0.0390 0.0454 0.0548 D31 (q=4) 2.3832 2.4769 2.8137 2.9886 3.0686 3.1960 0.0803 0.0199 0.0227 0.0238 0.0259 0.0284 Iris (q=1) 0.7140 0.6382 0.6166 0.6002 0.5880 0.5849 0.0665 0.0518 0.0555 0.0560 0.0572 0.0598 Vowel (q=2) 2.3938 2.3715 2.4186 2.4310 2.4529 2.4627 0.0635 0.0410 0.0416 0.0414 0.0429 0.0455 Zoo (q=4) 1.1817 1.0912 1.1780 1.1954 1.2015 1.2131 0.0366 0.0104 0.0182 0.0188 0.0176 0.0180 Ghi chú: Các kết quả trong bảng là giá trị trung bình của 10 lần thực nghiệm. Kết quả của mỗi tập dữ liệu trình bày trong hai dòng: dòng thứ nhất biểu diễn độ đo QE và dòng thứ hai biểu diễn độ đo TE. Kết luận: Với tham số p=2 (giá trị mặc định), việc điều chỉnh tham số q có ảnh hưởng đáng kể tới chất lượng của bản đồ. Nếu q càng lớn thì lỗi lượng tử càng nhỏ, tuy nhiên q phù nhất khi giá trị khi lỗi hình trạng đạt giá trị nhỏ nhất. Ngược lại, nếu đã xác định được giá trị phù hợp nhất của tham số q, thì tham số p có ảnh hưởng không đáng kể tới việc cải thiện chất lượng bản đồ. 11 Bảng 2.3 so sánh các độ đo QE, TE đạt được khi sử dụng hàm lân cận với tham số điều chỉnh (p=2 và q xác định riêng cho mỗi tập dữ liệu như Bảng 2.2) và một số dạng hàm lân cận khác Bảng 2. 3 So sánh độ đo QE, TE của một số dạng hàm lân cận Tập dữ liệu hci(t) gốc hci(t) với tham số điều chỉnh Hàm “nổi bọt” Hàm lân cận bất đối xứng XOR 0.1890 0.1585 0.2572 0.1808 0.0318 0.0223 0.2708 0.4635 Aggregation 5.9702 2.9340 7.3092 4.9466 0.0549 0.0245 0.1794 0.4476 Flame 2.1839 1.1822 2.6352 2.1916 0.0700 0.0393 0.1642 0.6828 Pathbased 4.5859 2.4779 5.524 5.3888 0.0561 0.0315 0.1981 0.2715 Spiral 4.7595 3.4675 5.6515 4.3775 0.0543 0.0284 0.1502 0.6306 Jain 5.2745 2.3559 6.3026 5.4962 0.0513 0.0269 0.2024 0.3172 Compound 4.4205 3.7595 5.5663 3.5529 0.0624 0.0299 0.2199 0.4349 R15 2.2226 1.4606 2.5017 1.8911 0.0722 0.0274 0.1384 0.6337 D31 4.7676 2.4569 5.6095 5.958 0.0479 0.0207 0.2054 0.3506 Iris 0.7709 0.6430 1.001 0.9284 0.0739 0.0548 0.2312 0.2610 Vowel 2.7459 2.3755 3.1022 2.8808 0.0537 0.0412 0.1872 0.3965 Zoo 1.5841 1.0912 1.7182 1.7179 0.0343 0.0104 0.2182 0.2210 Ghi chú: Các kết quả trong bảng là giá trị trung bình của 10 lần thực nghiệm. Kết quả của mỗi tập dữ liệu trình bày trong hai dòng: dòng thứ nhất biểu diễn độ đo QE và dòng thứ hai biểu diễn độ đo TE. 2.6. Thực nghiệm thuật toán Batch-IMQS Bảng 2.4 cho thấy Batch-IMQS có thể cải thiện đáng kể QE của một bản đồ đặc trưng bất kỳ mà không quan tâm đến các tham số cấu hình mạng, cũng như không gia tăng thêm các tham số khác. Tuy nhiên, lỗi TE tăng tỉ lệ nghịch với QE Bảng 2. 4 Kết quả thực nghiệm thuật toán Batch-IMQS Tập dữ liệu 55 1010 1515 SOM Batch- IMQS SOM Batch- IMQS SOM Batch- IMQS XOR 0.1938 0.0716 0.1344 0.040 0.115 0.0293 0 0.0735 0 0.1270 0 0.1801 Aggregation 6.5617 1.8581 4.0004 1.1341 3.7515 0.9058 0 0.0774 0 0.0952 0.0114 0.2513 Flame 2.2242 0.8802 1.8174 0.4820 1.4581 0.3800 0 0.0292 0 0.2333 0.0083 0.3125 Pathbased 4.7585 1.6497 3.6075 0.8606 3.1839 0.5932 0.0133 0.1667 0.0067 0.24 0.0133 0.3067 12 Spiral 4.9053 1.8792 3.6889 0.8728 3.2971 0.6095 0 0.1667 0 0.3397 0.0032 0.3429 Jain 5.2967 1.6913 3.7646 1.0424 3.1354 0.7534 0 0.0483 0.0054 0.1609 0.0107 0.1796 Compound 4.4481 1.4561 3.0018 0.8799 2.5214 0.694 0 0.0526 0.0050 0.2030 0.015 0.1955 R15 2.2694 0.9755 1.8055 0.8900 1.5845 0.5435 0 0.0033 0 0.0183 0 0.0117 D31 5.1947 1.2570 3.3776 0.7306 2.9099 0.6021 0 0.1639 0 0.0816 0.001 0.2094 Iris 0.7622 0.3926 0.5526 0.2398 0.4995 0.1793 0.0200 0.1867 0.0133 0.2400 0.0133 0.3067 Vowel 2.6522 1.5399 2.2776 1.1500 2.1422 0.9997 0.003 0.1222 0.0172 0.4212 0.0121 0.4485 Zoo 1.6328 0.9977 1.3044 0.7192 1.2268 0.6645 0 0.099 0 0.1188 0 0.2574 Ghi chú: Các giá trị đạt được có sai số 0.02 trong các lần thực nghiệm khác nhau. Kết quả của mỗi tập dữ liệu trình bày trong hai dòng. Dòng thứ nhất biểu diễn độ đo QE và dòng thứ hai biểu diễn độ đo TE. 2.7. Kết luận chương 2 Chương này đã trình bày hai đề xuất để cải thiện chất lượng bản đồ đặc trưng của mạng nơron tự tổ chức. Đề xuất thứ nhất, bổ sung tham số điều chỉnh cho hàm lân cận đối xứng Gaussian. Kết quả có thể giảm được đồng thời cả lỗi lượng tử và lỗi hình trạng của mạng. Tuy nhiên, giá trị của tham số điều chỉnh phải xác định riêng đối với mỗi tập dữ liệu cụ thể. Đề xuất thứ hai, đưa ra thuật toán điều chỉnh trọng số nơron để giảm lỗi lượng tử của mạng. Thuật toán có thể giảm lỗi lượng tử của mạng mà không quan tâm đến các tham số cấu hình, cũng như không gia tăng thêm các tham số khác. Tuy nhiên, nhược điểm là lỗi hình trạng tăng tỉ lệ nghịch với lỗi lượng tử. CHƯƠNG 3: MỘT MẠNG NƠRON TỰ TỔ CHỨC CÓ CẤU TRÚC PHÂN TẦNG TĂNG TRƯỞNG VÀ THUẬT TOÁN HỌC BÁN GIÁM SÁT CHO BÀI TOÁN PHÂN LỚP DỮ LIỆU 3.1. Tổng quan về các mạng nơron tự tổ chức cải tiến học giám sát, bán giám sát cho phân lớp dữ liệu 3.2. Phát biểu bài toán phân lớp dữ liệu 3.3. Một cấu trúc phân tầng tăng trưởng và thuật toán học bán giám sát của mạng nơron tự tổ chức cho bài toán phân lớp dữ liệu Mạng nơron tự tổ chức phân tầng tăng trưởng học bán giám sát cho bài toán phân lớp dữ liệu, được gọi là GHSSOM (Growing Hierarchical Semi-Supervised SOM) [4A], [5A], [8A]. Cấu trúc của GHSSOM được lai ghép từ cấu trúc của GHSOM (Growing Hierarchical SOM) (Rauber, 2002), HTS (Hierarchical Tree Structure) [2A] và cấu trúc giả giám sát CPN (Zupan, 1997). 13 3.3.1. Các cấu trúc nền tảng để xây dựng mạng nơron tự tổ chức phân tầng tăng trưởng học bán giám sát cho phân lớp dữ liệu 3.3.2. Cấu trúc mạng nơron tự tổ chức phân tầng tăng trưởng học bán giám sát cho phân lớp dữ liệu Mỗi nút của GHSSOM là một mạng SOM mở rộng, gồm có hai lớp tương tự như mạng CPN. Lớp thứ nhất gọi là Xmap (hay lớp Kohonen). Xmap là bản đồ tự tổ chức biểu diễn đặc trưng của các mẫu đầu vào và được huấn luyện bằng thuật toán SOM gốc. Lớp thứ hai gọi là Ymap. Ymap là bản đồ phân bố đầu ra (nhãn) của dữ liệu. Ymap có kích thước bằng Xmap. Tuy nhiên, các đơn vị trên Ymap không được cập nhật đồng thời cùng Xmap giống như mạng CPN, mà được cập nhật sau khi Xmap đã được huấn luyện xong. Việc cập nhật nhãn cho Ymap được thực hiện theo hai bước: Bước 1. Cập nhật nhãn: duyệt tất cả các mẫu dữ liệu đã được gán nhãn (x, y) thuộc tập dữ liệu huấn luyện, với x là mẫu đầu vào và y là giá trị nhãn (đầu ra tương ứng của x), với y>0. Quy ước y=0 cho biết mẫu đầu vào x chưa được gán nhãn (trong trường hợp học bán giám sát, tập dữ liệu huấn luyện có thể tồn tại các mẫu dữ liệu chưa có nhãn). - Xác định nơron chiến thắng (BMU) của x trên Xmap. Giả sử nơron thứ i của Xmap được xác định là nơron chiến thắng. - Kết nạp mẫu dữ liệu (x, y) vào tập dữ liệu được đại diện bởi nơron thứ i. - Cập nhật nhãn y cho Ymap theo nguyên tắc: Nếu nơron thứ i chưa được gán nhãn thì nó sẽ được gán nhãn là y (với y>0). Ngược lại, nếu nơron thứ i đã được gán nhãn, nhưng giá trị nhãn của nó khác y thì gán cho nơron i một nhãn đặc biệt e=-1 (e là nhãn lỗi dùng để đánh dấu vị trí nơron phân lớp sai và nhãn lỗi không có trong tập dữ liệu). Bước 2. Lan truyền nhãn: với mỗi đơn vị thứ i thuộc Ymap chưa xác định nhãn (giá trị nhãn bằng 0), thực hiện: - Tìm trên Xmap một nơron thứ j có vị trí tương ứng trên Ymap đã gán nhãn (là nhãn có trong tập dữ liệu hoặc nhãn lỗi e) thỏa mãn: ij và trọng số của nơron thứ i khớp nhất với trọng số của nơron thứ j. - Gán nhãn của nơron thứ i bằng nhãn của nơron thứ j: Ymap[i]= Ymap[j]. - Gán tập dữ liệu được đại diện bởi nơron thứ i bằng tập dữ liệu được đại diện bởi nơron thứ j. Cách thức cập nhật nhãn của Ymap như trên cho phép GHSSOM giải quyết bài toán phân lớp mà tập dữ liệu huấn luyện đầy đủ nhãn (phân lớp truyền thống) hoặc chỉ có một số lượng nhất định mẫu dữ liệu có nhãn (phân lớp bán giám sát). Khi bắt đầu, GHSSOM được khởi tạo với một nút gốc duy nhất có kích thước ab. Xmap của nút gốc được huấn luyện bởi tất cả các mẫu dữ liệu của tập huấn luyện (ký hiệu là I). Sau khi xác định nhãn cho Ymap của nút gốc thì mỗi nơron thứ i của Xmap sẽ đại diện cho một tập con dữ liệu Ii  I, (với i=1..s, s=ab). Hình 3. 1 Minh họa cấu trúc mạng GHSSOM. 1 1 1 2 1 - 1 2 2 2 2 2 3 2 3 -1 3 y x Xmap Ymap -1 Xmap Ymap Xmap Ymap 14 Nguyên tắc tăng trưởng của GHSSOM: Giả sử m là một nút của GHSSOM; k là một nơron thuộc nút m có giá trị nhãn là e; subnet là nút con tăng trưởng từ nơron k; Iparent là tập dữ liệu huấn luyện nút m, child parentI I là tập dữ liệu huấn luyện nút con subnet (tập dữ liệu được đại diện bởi nơron k). Xét theo hai trường hợp sau: Trường hợp 1: nếu |Ichild|  |Iparent| thì phát sinh nút con subnet liên kết với nơron k. Kích thước nút con subnet xác định theo công thức: ar ar | | | | child child p ent p ent I n ceil n I              (3.1) trong đó: nchild là kích thước nút con; nparent là kích thước nút cha;  là tham số điều chỉnh mức độ giảm kích thước nút con so với nút cha; ceil(): là hàm làm tròn lên; |.| số phần tử trong một tập hợp. Trường hợp 2: nếu |Ichild|=|Iparent| thì điều chỉnh lại nút đang xét m. Xét điều kiện sau: 0kqe QE  (3.2) trong đó:  là tham số xác định ngưỡng tăng trưởng, có vai trò quan trọng, đảm bảo cho mạng không rơi vào trạng thái “quá khớp” với dữ liệu huấn luyện (overfitting1), với 0< <1; qek là lỗi lượng tử của nơron k; QE0 là lỗi lượng tử của nút gốc, được xác định theo công thức:      0 1 0 0 , T BMU t t d x t w QE T   (3.3) trong đó: x(t) là mẫu đầu vào tại lần huấn luyện thứ t;  BMU tw là trọng số của BMU đối với mẫu đầu vào x(t);     , BMU td x t w là khoảng cách của mẫu đầu vào x(t) so với BMU của nó; T0 là tổng số lần huấn luyện của nút gốc; Nếu điều kiện (3.2) là đúng thì khởi tạo và huấn luyện lại nút m, với kích thước xác định theo công thức (3.4), tập dữ liệu huấn luyện là Iparent. Chú ý rằng, trọng số của mỗi nơron được khởi tạo bằng một mẫu dữ liệu thuộc tập Iparent.  child parentn ceil I (3.4) Ngược lại, nếu điều kiện (3.2) là sai thì sửa lại giá trị nhãn của nơron k theo nguyên tắc nhãn khớp nhất đại diện, đồng thời loại bỏ các nơron còn lại (trừ nơron k) ra khỏi nút m. Giá trị nhãn của nơron k xác định theo (3.5).   minYmap k y (3.5) trong đó: ymin là nhãn tương ứng của mẫu đầu vào xmin, với xmin được xác định theo công thức (3.6)    min , min child k x y I x x w    (3.6) 1 Một hàm mục tiêu hay một giả thiết học được h, sẽ được gọi là overfitting (quá khớp dữ liệu) với một tập dữ liệu huấn luyện nếu tồn tại một hàm mục tiêu khác là h’ sao cho: h’ kém phù hợp hơn, đạt độ chính xác kém hơn so với h trên tập dữ liệu huấn luyện, nhưng h’ lại đạt độ chính xác cao hơn h đối với toàn bộ tập dữ liệu (bao gồm cả tập dữ liệu liệu huấn luyện và tập dữ liệu kiểm tra) 15 3.3.3. Thuật toán huấn luyện của mạng nơron tự tổ chức phân tầng tăng trưởng học bán giám sát cho phân lớp dữ liệu Thuật toán GHSSOM tại mỗi nút vừa có vài trò huấn luyện, vừa có vai trò tăng trưởng để hình thành cấu trúc cây phân tầng [8A]. Quá trình huấn luyện cụ thể tại mỗi nút được chia thành hai giai đoạn như sau: Giai đoạn 1: Hình thành bản đồ đặc trưng - Huấn luyện lớp Xmap bằng thuật toán SOM gốc. Kết quả là các nơron của Xmap biểu diễn các đặc trưng của tập dữ liệu huấn luyện. Giai đoạn 2: Gán nhãn và tăng trưởng (xác định các nơron phân lớp sai và tăng trưởng nút mới) - Cập nhật nhãn và xác định các tập con dữ liệu Ii được đại diện bởi mỗi nơron thứ i thuộc Xmap - Lan truyền nhãn cho các đơn vị thuộc Ymap chưa được gán nhãn. - Tăng trưởng: thực hiện theo nguyên tắc tăng trưởng (mục 3.3.2). - Lặp lại Giai đoạn 1 đối với các nút mới tăng trưởng hoặc nút được khởi tạo lại. 3.4. Thực nghiệm mạng nơron tự tổ chức phân tầng tăng trưởng học bán giám sát cho phân lớp dữ liệu Bảng 3. 1 Kết quả phân lớp của GHSSOM với hàm lân cận với tham số điều chỉnh q Tập dữ liệu Tỉ lệ mẫu dữ liệu có nhãn/tổng dữ liệu huấn luyện 10% 20% 30% 50% 70% 100% XOR 99.10 99.76 99.83 99.90 99.98 100 Aggregation 95.69 97.08 98.87 99.11 99.37 99.49 Flame 89.58 95.83 96.25 97.50 98.75 99.17 Pathbased 68.0 82.67 89.67 92.67 94.33 95.67 Spiral 49.38 55.13 65.03 72.41 84.25 91.04 Jain 96.52 98.67 99.46 99.47 99.73 100 Compound 79.71 87.72 89.73 91.98 93.74 95.24 R15 88.33 93.33 96.50 97.33 97.67 98.67 D31 89.68 92.61 94.13 94.55 94.67 95.42 Iris 90.0 92.0 92.67 94.67 95.33 96.0 Vowel 31.81 51.52 61.92 80.61 84.95 90.61 Zoo 76.14 81.14 84.33 87.24 93.05 94.14 Ghi chú: Các kết quả trong bảng là giá trị trung bình của 10 lần thực nghiệm. 16 (1) So sánh GHSSOM với các phương thức phân lớp bán giám sát SSGSOM và CS2GS (Allahyar, 2015) a) Kết quả phân lớp Two Moons của GHSSOMv1 và GHSSOMv2 b) Kết quả phân lớp Two Moons của SSGSOM và một số phương thức Hình 3. 2 So sánh GHSSOM với SSGSOM, CS2GS và một số phương thức khác Ghi chú: GHSSOMv1 là phiên bản thuật toán GHSSOM sử dụng hàm lân cận gốc, GHSSOMv2 là phiên bản thuật toán GHSSOM sử dụng hàm lân cận với tham số điều chỉnh q. Nhận xét: GHSSOMv1 và GHSSOMv2 phân lớp chính xác hơn SSGSOM, CS2GS và các phương thức CCS, RCS, DCS, HSS khi tỉ lệ dữ liệu có nhãn/tổng dữ liệu huấn luyện nhỏ. (2) So sánh GHSSOM với SVM, GMM, BSOM và KNN (Guo, 2013) Bảng 3.2 so sánh kết quả phân lớp tập dữ liệu Iris trong trường hợp 100% mẫu huấn luyện được gán nhãn (Guo, 2013). Bảng 3. 2 Kết quả phân lớp Iris của GHSSOM và một số phương thức Tập dữ liệu SVM GMM BSOM KNN (n=8) GHSSOMv1 GHSSOMv2 Iris 95.90 95.50 96.30 95.90 94.67 96.0 (3) So sánh GHSSOM với một số phương thức phân lớp cài đặt trong WEKA Hình 3.3 là các biểu đồ so sánh kết quả phân lớp bán giám sát của GHSSOM với LibSVM khi thay đổi số lượng mẫu dữ liệu huấn luyện có nhãn. Nhận thấy GHSSOM phân lớp tốt hơn trong trường hợp tập dữ liệu phân bố rõ ràng, sự tương đồng giữa các phần tử trong cùng một lớp cao. Nguyên nhân là vì GHSSOM sử dụng nguyên tắc học cạnh tranh, nên nó gom các mẫu dữ liệu có sự tương đồng cao vào cùng một lớp. Khi tỉ lệ mẫu dữ liệu huấn luyện có nhãn càng nhỏ thì kết quả phân lớp của GHSSOM càng tốt hơn so với LibSVM. 17 Hình 3. 3 So sánh kết quả phân lớp bán giám sát của GHSSOM và LibSVM 18 3.5. Kết luận chương 3 Chương này đề xuất một cấu trúc phân tầng tăng trưởng và một thuật toán học bán giám sát của SOM cho mục đích phân lớp dữ liệu. Mô hình đề xuất có thể thực hiện cả hai nhiệm vụ phân lớp bán giám sát và phân lớp truyền thống, với có kết quả phân lớp bán giám sát tốt hơn so với phân lớp truyền thống và tốt hơn so với một số phương thức phân lớp khác. CHƯƠNG 4: MỞ RỘNG CẤU TRÚC, THUẬT TOÁN HỌC CỦA MẠNG NƠRON TỰ TỔ CHỨC CHO BÀI TOÁN PHÂN CỤM DỮ LIỆU 4.1. Tổng quan về sử dụng mạng nơron tự tổ chức cho phân cụm dữ liệu 4.2. Phát biểu bài toán phân cụm dữ liệu 4.3. Cải tiến thuật toán học mạng nơron tự tổ chức cho phân cụm dữ liệu Thuật toán mạng nơron tự tổ chức cải tiến cho phân cụm dữ liệu được gọi là SOM-P (SOM- Partitional). 4.3.1. Ý tưởng của thuật toán cải tiến Trước tiên, thuật toán thiết lập r nhóm tạm thời (r là tổng số nhóm cần đạt được), sau đó liên tục kết nạp hoặc loại bỏ phần tử của các nhóm này để đạt giá trị hàm mục tiêu (4.1) nhỏ hơn sau mỗi lần học của mạng (theo k-means). 2 1 i r i i w Q E w center     (4.1) trong đó: r là tổng số nhóm; Qi là tập các nơron của nhóm thứ i; w là trọng số của một nơron thuộc tập Qi; centeri tâm nhóm thứ i. Giả thiết ban đầu tất cả các nơron thuộc về một nhóm, gọi là nhóm 0. Nhóm 0 không thuộc tổng số r nhóm cần hình thành. Gọi Nq.nhom là nhóm của nơron Nq, ta có Nq.nhom=0 với q=1..ab, trong đó ab là kích thước lớp Kohonen. Với mỗi mẫu đầu vào v tại lần huấn luyện thứ t, phân nhóm các nơron trong bán kính lân cận của BMU theo các nguyên tắc sau: - Nguyên tắc phân ly: Xét điều kiện xác định nhóm cho BMU như sau:  ,BMU BMUd w center  (4.2) trong đó: BMUw là trọng số của BMU; BMUcenter là tâm của nhóm mà BMU thuộc về (là một trong r nhóm hoặc nhóm 0). 1 i BMU BMU i N QBMU center w Q    (4.2a) với: QBMU là nhóm chứa BMU; wi là trọng số của nơron thứ i trong nhóm QBMU;  ,BMU BMUd w center là khoảng cách từ BMU đến tâm của nhóm chứa nó;  =Sc là ngưỡng phân ly, với: 0<≤1 là tham số xác định ngưỡng phân ly; Sc là khoảng cách trọng tâm (Centroid Distance) của tập dữ liệu.   1 1 , N c k k S d x center N    (4.2b) với: N là tổng số mẫu dữ liệu; xk là mẫu dữ liệu thứ k; center là tâm của tập dữ liệu. Nếu điều kiện (4.2) thỏa mãn, xảy ra hai trường hợp: 19 Trường hợp 1: Nếu số lượng nhóm hiện tại nhỏ hơn r (r là số nhóm tối đa) thì thêm một nhóm mới và gán BMU vào nhóm này (BMU.nhom = chỉ số nhóm mới) Trường hợp 2: Nếu số lượng nhóm hiện tại bằng r thì gán BMU vào nhóm khớp nhất với nó nếu có thể. Nhóm thứ k (với k≤r) được xác định là nhóm khớp nhất với BMU nếu thỏa mãn các điều kiện sau:     , min ,BMU k BMU i i d w center d w center với i=1..r (4.3)    , ,BMU k BMU BMUd w center d w center (4.4) trong đó: centeri, centerk là tâm nhóm của các nhóm thứ i, k. - Nguyên tắc tranh chấp: Giả sử q BMUN Q và Nq.group  BMU.group thì kết nạp Nq vào nhóm chứa BMU (Nq.group = BMU.group) nếu điều kiện dưới đây thỏa mãn:    , ,q BMU q qd w center d w center (4.5) trong đó: wq là trọng số của nơron Nq. 4.3.2. Thuật toán học cải tiến SOM-P cho phân cụm dữ liệu SOM-P gồm 5 bước, trong đó: bốn bước đầu tiên giống thuật toán SOM gốc, chỉ bổ sung Bước 5 xác định nhóm cho BMU và các nơron trong bán kính lân cận của BMU [9A]. Bước 1: Khởi tạo mạng. Lặp: Bước 2: Cạnh tranh (đưa một kích thích vào mạng và xác định BMU). Bước 3: Hợp tác (xác định bán kính lân cận của BMU). Bước 4: Thích nghi (cập nhật trọng số cho BMU và các nơron trong bán kính lân cận của BMU). Bước 5: Xác định nhóm của BMU và các nơron trong bán kính lân cận của BMU (theo các nguyên tắc phân ly và tranh chấp). Cho đến khi thỏa mãn điều kiện dừng: đạt được số lần huấn luyện nhất định hoặc mạng đạt trạng thái cân bằng. 4.4. Mở rộng cấu trúc mạng nơron tự tổ chức cho phân cụm dữ liệu 4.4.1. Cấu trúc mạng nơron tự tổ chức mở rộng hai lớp Mạng nơron tự tổ chức có cấu trúc mở rộng gồm hai lớp, được gọi là SOM-2 (Hình 4.1). Lớp thứ nhất là SOM hai chiều để biểu diễn bản đồ đặc trưng của tập dữ liệu; lớp thứ hai là SOM một chiều để phân nhóm các nơron của lớp thứ nhất. 4.4.2. Thuật toán huấn luyện mạng nơron tự tổ chức mở rộng hai lớp Tại lần huấn luyện thứ t, một mẫu vào x=(x1, x2,..., xn) được gửi tới mạng. Quá trình học của mạng thực hiện lần lượt trên các lớp như sau: Lớp 1 (lớp Kohonen): Các nơron được cập nhật theo thuật toán SOM gốc. Mỗi nơron tại lớp 1 sau khi được cập nhật sẽ kích hoạt một nơron thuộc lớp 2 và tiếp tục cập nhật mẫu dữ liệu vào cho lớp 2. Hình 4.1. Minh họa cấu trúc mạng SOM-2 20 Lớp 2: Các nơron được cập nhật theo nguyên tắc học cạnh tranh tương tự như thuật toán SOM gốc. Với mỗi nơron thứ i nằm trong bán kính lân cận của BMU1 thuộc lớp 1, thực hiện: + Xác định nơron chiến thắng tại lớp 2 (BMU2): là nơron thứ  2 c (với 1 ≤  2 c ≤ r) thỏa mãn công thức sau:         1 2 1 2is mini c i j j d t w w w w    (4.6) trong đó:  1 iw là trọng số của nơron thứ i thuộc lớp 1 nằm trong bán kính lân cận của BMU1;  2 jw là trọng số của nơron thứ j thuộc lớp 2, với j=1..r. + Gán nơron thứ i thuộc lớp 1 bằng nhóm của BMU2: Labeli=  2 c + Tăng giá trị bộ đếm phân nhóm  2 ic counter lên một đơn vị. + Xác định bán kính lân cận tại lớp 2 theo công thức sau:    0 2exp t R t R         (4.7) trong đó: R(t) là bán kính lân cận của lớp 2 tại lần huấn luyện thứ t; R0 là bán kính lân cận khởi tạo của lớp 2 (khởi tạo bằng kích thước mạng);     2 0log T R   là hằng số thời gian, với T là tổng số lần học của mạng. + Cập nhật trọng số của các nơron thuộc lớp 2 nằm trong bán kính lân cận R(t) của BMU2 (bao gồm cả BMU2) theo mẫu đầu vào:                      2 2 2 2 w 1 w wj j ij i ci jc j t t p t L t h t h t v t       (4.8) trong đó:    2w j t là trọng số của nơron thứ j thuộc lớp 2 nằm trong bán kính R(t) của BMU2;  iL t là tỉ lệ học tại lần lặp thứ t của nơron thứ i thuộc lớp 1 (1.7);    2 c j h t là hàm lân cận xác định cho nơron thứ j thuộc lớp 2 trong bán kính lân cận BMU2, xác định theo công thức sau:         2 2 2 2 4 || || exp jc c j r r h t R t         (4.9)  ijp t là xác suất nơron thứ i của lớp 1 thuộc vào nhóm Cj (với j=1..r) tại lần huấn luyện thứ t.  ijp t được xác định theo công thức (4.10).       1 ij ij r ik k counter t p t counter t    (4.10) Công thức (4.8) cho thấy tham số tỉ lệ học của đơn vị thứ j trên lớp 2 được tính dựa vào các thành phần: xác xuất, tỉ lệ học và hàm lân cận của nơron trên lớp 1 kích hoạt đơn vị j, tức là:          2j ij i ciL t p t L t h t (4.11) trong đó: i là nơron trên lớp 1 kích hoạt nơron j trên lớp 2. 21 4.5. Thực nghiệm thuật toán học cải tiến và mạng tự tổ chức mở rộng hai lớp Bảng 4.1 trình bày kết quả phân loại của SOM-P và SOM-2 trên các tập dữ liệu thực nghiệm. Bảng 4. 1 Kết quả thực nghiệm phân cụm của SOM-P và SOM-2 Tập dữ liệu Tổng số mẫu SOM-P SOM-2 Số mẫu bị phân loại sai Tỉ lệ phân loại sai (%) Số mẫu bị phân loại sai Tỉ lệ phân loại sai (%) XOR 4125 2045 49.58 2042 49.50 Aggregation 788 180 22.84 157 19.92 Flame 240 43 17.92 39 16.25 Pathbased 300 82 27.33 90 29.67 Spiral 312 205 65.71 195 62.50 Jain 373 90 24.13 65 17.43 Compound 399 125 31.33 181 45.36 R15 600 176 29.33 183 30.50 Iris 150 17 11.33 11 7.33 Vowel 990 854 86.26 879 88.79 Zoo 101 25 24.75 20 19.80 Ghi chú: Các kết quả trong bảng là giá trị trung bình của 10 lần thực nghiệm. Kết quả phân loại của SOM-P và SOM-2 có sự tương đồng nhau, trong đó phân loại tốt hơn đối với 5 tập dữ liệu Aggregation, Flame, Jain, Iris và Zoo. Đây là các tập có sự phân bố cụm và hình dạng cụm rõ ràng, dữ liệu của các cụm tập trung, ít bị xen lẫn và không có sự bao nhau giữa các cụm. (1) So sánh SOM-P, SOM-2 với thuật toán GWCA và một số phương thức khác (Wang, 2009) khi phân loại tập dữ liệu Iris và Zoo Bảng 4. 2 So sánh SOM-P, SOM-2 với GWCA và một số phương thức khác Tên phương thức Tỉ lệ phân loại đúng (%) Ghi chú Iris Zoo SC 91 64 CSPA 86 56 HPGA 69 58 NMFC 89 62 WC 89 70 EGWCA 92 72 Sử dụng hàm Euclidean eGWCA 90 75 Sử dụng hàm Exponential SOM-P 88.67 75.25 SOM-2 92.67 80.20 (2) So sánh SOM-P, SOM-2 với GSOM, KGSOM (Senanayake, 2015) khi phân loại tập Zoo Bảng 4. 3 So sánh SOM-P, SOM-2 với GSOM và KGSOM Tên phương thức Độ chính xác (Precision) Khả năng nhớ (Recall) GSOM 0.8894 0.4250 KGSOM 0.9182 0.7036 SOM-P 0.7884 0.6933 SOM-2 0.8987 0.7536 Ghi chú: Các độ đo Precision và Recall đạt được của SOM-P và SOM-2 là trung bình của 10 lần thực nghiệm. Xét một cách tương đối thì SOM-2 phân loại tập Zoo tốt hơn so với các phương thức còn lại do tổng các độ đo Precision và Recall lớn nhất. 22 (3) So sánh SOM-P, SOM-2 với một số phương thức (Leela, 2014) khi phân loại tập dữ liệu Iris Bảng 4. 4 So sánh SOM-P, SOM-2 với một số phương thức khác Tên phương thức Số cụm đạt được Tỉ lệ phân loại đúng (%) K-means 4 82 Improved Y-means 2 85 FC means 5 81 Mountain 3 77.4 Subtractive 4 75 SOM-P 3 88.67 SOM-2 3 92.67 (4) So sánh SOM-P, SOM-2 với một số phương thức phân cụm trong WEKA Bảng 4. 5 So sánh tỉ lệ phân loại sai của SOM-P, SOM-2 với một số phương thức Tập dữ liệu Hierarchical Cluster LVQ MTree EM Simple Kmeans Xmeans SOM- P SOM- 2 XOR NOT 40.15 47.15 49.70 49.70 49.70 49.58 49.50 Aggregation 17.51 33.38 35.66 7.49 21.70 20.18 22.84 19.92 Flame 35.42 29.58 18.75 34.17 15.83 15.42 17.92 16.25 Pathbased 63.00 40.67 47.67 29.67 25.67 25.67 27.33 29.67 Spiral 0 64.74 64.42 64.74 65.71 65.38 65.71 62.50 Jain 25.74 19.84 19.57 8.85 11.80 11.80 24.13 17.43 Compound 23.81 48.37 50.38 19.30 19.80 32.08 31.33 45.36 R15 27.67 12.67 44.00 9.83 9.33 19.67 29.33 30.50 Iris 34.00 56.00 44.00 9.33 11.33 12.00 11.33 7.33 Vowel 88.48 85.86 73.54 78.29 79.19 82.02 86.26 88.79 Zoo 12.87 19.80 49.51 20.79 18.81 13.86 24.75 19.80 Ghi chú: “NOT” là không có kết quả do máy tính sử dụng cho thực nghiệm không đủ bộ nhớ để thực hiện phương thức phân cụm “Hierarchical Cluster”. So với một số phương thức phân cụm cũng sử dụng phương pháp phân cụm phân hoạch được công bố gần đây và đặc biệt là một số phương thức phân cụm được cải tiến từ SOM, thì SOM-P và SOM-2 phân cụm tốt hơn. Tuy nhiên, so với một số phương thức phân cụm truyền thống thì kết quả chưa có sự nổi bật. Có hai nguyên nhân chính: Một là, SOM-P và SOM-2 phải thực hiện hai lần phép ánh xạ dữ liệu để phân cụm. Lần một là ánh xạ các mẫu dữ liệu tới các nơron đại diện cho chúng. Lần hai là gom các nơron có trọng số tương đồng nhau vào cùng một cụm. Hai lần ánh xạ này có thể tạo ra sai số cao hơn so với các thuật toán phân cụm trực tiếp. Đây là hạn chế chung của tất cả các phương thức phân cụm được phát triển từ SOM. Hai là, việc phân nhóm nơron sử dụng phương pháp phân cụm phân hoạch là chưa phù hợp vì thực tế các cụm dữ liệu phân bố trên bản đồ đặc trưng có thể không phải dạng hình cầu. 4.6. Kết luận chương 4 Chương này đã trình bày hai phương thức cải tiến mạng nơron tự tổ chức cho phân cụm dữ liệu. Thứ nhất, cải tiến thuật toán học của SOM cho mục đích phân cụm dữ liệu. Thứ hai, mở rộng cấu trúc SOM cho mục đích phân cụm dữ liệu. Cả hai phương thức đề xuất được phát triển dựa trên phương pháp phân cụm phân hoạch. Do đó, các phương thức này phù hợp để áp dụng đối với các tập dữ liệu có các cụm hình cầu, kích thước và khoảng cách giữa các cụm đều nhau. 23 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN CỦA ĐỀ TÀI LUẬN ÁN 1. Kết luận Với mục tiêu nghiên cứu cải tiến cấu trúc, thuật toán học của mạng nơron tự tổ chức, luận án đã thực hiện các nội dung nghiên cứu: Nghiên cứu tổng quan về mạng nơron tự tổ chức và các biến thể của mạng nơron tự tổ chức, phân tích các hạn chế và giải pháp đã được các nhà nghiên cứu sử dụng để khắc phục những hạn chế này. Ngoài ra, tổng hợp các đặc điểm chung được áp dụng để phát triển các biến thể của mạng nơron tự tổ chức. Các nghiên cứu này là cơ sở để phát triển các hướng nghiên cứu của luận án. Các nội dung nghiên cứu chuyên sâu của luận án tập trung theo hai mục tiêu chính sau: Thứ nhất, cải tiến thuật toán học nhằm cải thiện chất lượng bản đồ đặc trưng của mạng nơron tự tổ chức. Thứ hai, cải tiến cấu trúc và thuật toán học của mạng nơron tự tổ chức ứng dụng cho bài toán phân lớp và phân cụm dữ liệu. Các kết quả cụ thể gồm: (1) Bổ sung tham số điều chỉnh cho hàm lân cận dạng mũ để đạt được bản đồ đặc trưng có chất lượng tốt hơn với hai độ đo lỗi lượng tử và lỗi hình trạng đều giảm. Tức là cải thiện được cả hai tiêu chí chất lượng học và tính bảo tồn quan hệ lân cận của dữ liệu. (2) Đưa ra thuật toán điều chỉnh trọng số nơron để giảm lỗi lượng tử. Mục tiêu là nâng cao chất lượng học của mạng hay cải thiện tính chính xác của dữ liệu đại diện. Tuy nhiên, hạn chế của thuật toán là lỗi hình trạng tăng tỉ lệ nghịch với lỗi lượng tử. (3) Đưa ra một cấu trúc phân tầng tăng trưởng và thuật toán học bán giám sát của mạng nơron tự tổ chức cho bài toán phân lớp dữ liệu. Mô hình đề xuất có thể hoạt động như một mô hình phân lớp truyền thống hoặc phân lớp bán giám sát. So với nhiều mô hình phân lớp khác, mô hình đề xuất phân lớp chính xác hơn, đặc biệt trong các trường hợp số lượng mẫu dữ liệu huấn luyện có nhãn nhỏ. (4) Cải tiến mạng nơron tự tổ chức cho bài toán phân cụm dữ liệu. Bao gồm hai đề xuất: Một là, cải tiến thuật toán học của mạng áp dụng cho bài toán phân cụm dữ liệu. Hai là, đưa ra một cấu trúc mạng hai lớp và thuật toán học của cấu trúc đề xuất áp dụng cho bài toán phân cụm dữ liệu. Các phương thức này phân cụm chính xác hơn so với một số phương thức phân cụm khác sử dụng phương pháp phân hoạch và một số phương thức phân cụm được phát triển từ SOM. (5) Cài đặt thực nghiệm các cấu trúc và thuật toán cải tiến sử dụng 12 tập dữ liệu giả định và thực tế đã được công bố. 2. Hướng phát triển của đề tài luận án Các nội dung nghiên cứu của luận án có thể tiếp tục hoàn thiện và phát triển. Một số hướng phát triển cụ thể của luận án như sau: - Tiếp tục nghiên cứu các phương thức để cải thiện chất lượng bản đồ đặc trưng của mạng, nhằm đảm bảo giảm đồng thời cả hai độ đo lỗi lượng tử và lỗi hình trạng. Ngoài ra, có thể nghiên cứu mở rộng thuật toán học của các biến thể mạng nơron tự tổ chức để cải thiện chất lượng bản đồ đặc trưng của các biến thể này. - Cải tiến kỹ thuật lan truyền nhãn của mạng nơron tự tổ chức phân tầng tăng trưởng học bán giám sát GHSSOM nhằm cải thiện độ chính xác phân lớp. - Nghiên cứu kỹ thuật phân nhóm nơron của SOM dựa trên tính chất về khoảng cách giữa các nơron thay vì sử dụng tư tưởng của phương pháp phân cụm phân hoạch để cải thiện độ chính xác phân cụm của các giải pháp đã đề xuất. 24 CÁC CÔNG TRÌNH KHOA HỌC CỦA NGHIÊN CỨU SINH 1A. Lê Anh Tú, Phạm Việt Bình, Lê Sơn Thái (2013), Một giải pháp trực quan mạng nơron SOM ứng dụng phân cụm dữ liệu, Fair 06/2013-Huế, 270-276. 2A. Le Anh Tu, Nguyen Quang Hoan, Le Son Thai (2013), Clustering Hierarchical Data Using SOM Neural Network, ICCASA 2012, LNICST of Springer 109, 282–289. 3A. Lê Anh Tú, Lê Sơn Thái, Nguyễn Quang Hoan (2014), Một số giải pháp cải tiến nhằm tăng tốc độ thuật toán mạng nơron SOM, Tạp chí KH&CN-ĐHTN, 116(2), 79-84. 4A. Le Anh Tu, Nguyen Quang Hoan, Le Son Thai (2014), Hierarchy Supervised SOM Neural Network Applied for Classification Problem, Journal of Computer Science and Cybernetics, 24(3), 278-290. 5A. Lê Anh Tú, Phạm Việt Bình, Đỗ Năng Toàn, Lê Sơn Thái (2014), Ứng dụng mạng nơron SOM trong việc xác định trạng thái nhắm, mở của mắt người, Kỷ yếu Hội thảo Fair 6/2014 - Thái Nguyên, 729-735. 6A. Le Anh Tu (2015), Improving the Quality of Self-Organizing Map by Different Elements Competitive Strategy, Journal of Computer Science and Cybernetics, 31(3), 215-229. 7A. Le Anh Tu, Nguyen Quang Hoan, Vu Duc Thai (2016), Improving Feature Map Quality of SOM Based on Adjusting the Neighborhood Function, International Journal of Computer Science and Information Security (ESCI index), 14(9), 746-757. 8A. Le Anh Tu, Nguyen Quang Hoan, Vu Duc Thai (2016), A Growing Hierarchical Semi- Supervised SOM for Classification Problem, International Journal of Computer Science and Information Security (ESCI index), 14(9), 671-679. 9A. Lê Anh Tú, Vũ Đức Thái, Ngô Phương Thùy (2016), Cải tiến mạng nơron tự tổ chức cho mục đích phân cụm dữ liệu, Hội nghị toàn quốc lần thứ 8 về Cơ Điện tử - VCM-2016, Cần Thơ 11/2016.