Tài liệu Phát triển cấu trúc, thuật học của mạng noron tự tổ chức

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VN HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ Lê Anh Tú PHÁT TRIỂN CÁC CẤU TRÚC, THUẬT HỌC CỦA MẠNG NƠRON TỰ TỔ CHỨC Chuyên ngành: Cơ sở toán học cho tin học Mã số: 62 46 01 10 TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội - 2016 Công trình được hoàn thành tại: Học viện Khoa học và Công nghệ - Viện Hàn lâm Khoa học và Công nghệ Việt Nam Người hướng dẫn khoa học: PGS.TS. NGUYỄN QUANG HOAN Phản biện 1: ................................................................................................. ..................................................................................................................... Phản biện 2: ................................................................................................. ..................................................................................................................... Phản biện 3: ................................................................................................. ..................................................................................................................... Luận án được bảo vệ trước Hội đồng chấm luận án cấp Học viện họp tại: ......................................................................................................... ..................................................................................................................... Vào hồi giờ ngày tháng năm Có thể tìm hiểu luận án tại thư viện: ........................................................... 1 MỞ ĐẦU Mạng nơron bản đồ tự tổ chức (SOM - Self Organizing Map) được đề xuất bởi giáo sư Teuvo Kohonen vào năm 1980. Nó còn được biết đến với các tên gọi khác là: Bản đồ đặc trưng tự tổ chức (SOFM - Self Organizing Feature Map) hay mạng nơron tự tổ chức, hay đơn giản hơn là mạng nơron Kohonen. Điểm mạnh của SOM là khả năng khai thác các mối liên hệ có tính cấu trúc trong không gian dữ liệu thông qua một bản đồ đặc trưng, nên nó có thể được phát triển để giải quyết nhiều bài toán thực tiễn hiện nay. Tuy nhiên, bản thân mạng nơron SOM vẫn còn tồn tại nhiều nhược điểm dẫn tới những khó khăn và khả năng ứng dụng thực tiễn bị hạn chế. Do vậy, các nghiên cứu về cải tiến cấu trúc và thuật toán học của mạng nơron SOM đã được nhiều nhà nghiên cứu quan tâm. Các nghiên cứu cải tiến mạng nơron SOM được chia làm hai hướng chính, gồm: cải tiến cấu trúc và cải tiến thuật toán học của mạng. Các nghiên cứu về cải tiến cấu trúc của mạng có thể được chia làm hai nhóm: Nhóm thứ nhất gồm các cấu trúc cải tiến tăng trưởng theo chiều ngang. Các cấu trúc này có đặc điểm chung là ban đầu mạng có kích thước nhỏ, sau đó mở rộng trong quá trình huấn luyện tùy thuộc vào đặc tính của tập dữ liệu huấn luyện. Nhóm thứ hai gồm các cấu trúc cải tiến tăng trưởng theo chiều dọc, còn gọi là cấu trúc cây (với mỗi nút của cây là một nơron) hoặc cấu trúc cây phân tầng (với mỗi nút của cây là một mạng nơron SOM hoặc một biến thể của SOM). Các cấu trúc cây có thể cố định trước kích thước, nhưng cũng có thể tăng trưởng kích thước trong quá trình huấn luyện, do đó, còn được gọi là cấu trúc cây tăng trưởng. Các cấu trúc cây được đưa ra chủ yếu nhằm mục đích biểu diễn tính chất phân cấp của dữ liệu. Các cải tiến về thuật toán học của mạng có thể chia làm hai nhóm chính: các thuật toán học cải tiến sử dụng phương pháp học không giám sát và các thuật toán học cải tiến sử dụng phương pháp học giám sát hoặc bán giám sát. Nhóm thứ hai hình thành các biến thể với tên gọi chung là các mạng nơron SOM giám sát hoặc bán giám sát. Trên cơ sở nghiên cứu về mạng nơron SOM gốc và các biến thể của SOM về cấu trúc và phương pháp học, có một số vấn đề tồn tại cần tiếp tục nghiên cứu phát triển như sau: Thứ nhất, đề xuất các phương thức cải thiện chất lượng bản đồ đặc trưng khác so với các phương thức đã có trước đây; nghiên cứu cải thiện chất lượng biểu diễn dữ liệu của các mạng nơron SOM cải tiến. Đây là một hướng nghiên cứu mở do hiện nay các nghiên cứu cải thiện chất lượng các mạng nơron SOM cải tiến chưa có nhiều. Thứ hai, cả SOM gốc và hầu hết các biến thể của SOM chủ yếu được thiết kế cho mục tiêu biểu diễn dữ liệu (biểu diễn sự phân bố hoặc sự phân cấp của dữ liệu) nên khi ứng dụng SOM cho các mục đích khác cần nghiên cứu các phương án cải tiến phù hợp. Ví dụ, mạng nơron SOM chưa có phương án phân loại dữ liệu chính xác, do đó khả năng ứng dụng SOM để giải quyết các vấn đề của khai phá dữ liệu (ví dụ như phân lớp và phân cụm) còn hạn chế. Thứ ba: do sử dụng phương pháp học không giám sát nên quá trình học của SOM thiếu thông tin hướng dẫn để nâng cao hiệu quả ứng dụng trong một số bài toán thực tế, ví dụ như bài toán phân lớp dữ liệu. Các tồn tại trên là lý do lựa chọn và đưa ra các mục tiêu nghiên cứu của đề tài luận án. Mục tiêu nghiên cứu của đề tài luận án gồm: 1. Đề xuất một số giải pháp cải thiện chất lượng bản đồ đặc trưng mạng nơron SOM. 2. Cải tiến cấu trúc, thuật toán học mạng nơron SOM ứng dụng cho bài toán phân lớp, phân cụm dữ liệu. Các nội dung nghiên cứu này được thực nghiệm trong phạm vi dữ liệu dạng vector thuộc tính số thực; không áp dụng với các loại dữ liệu khác. Chương trình thực nghiệm được cài đặt bằng ngôn 2 ngữ lập trình C# và tiến hành thực nghiệm trên các tập dữ liệu đã được công bố sử dụng máy tính máy tính cá nhân (Chipset Core i5 - 1.7GHz, RAM 6GB). Nội dung của luận án bao gồm 4 chương. Chương đầu trình bày nghiên cứu tổng quan về nội dung của đề tài. Các chương còn lại trình bày các đóng góp của luận án. Nội dung của từng chương có thể tóm tắt như sau: Chương 1 trình bày nghiên cứu tổng quan về mạng nơron nhân tạo, mạng nơron SOM; tập trung phân tích các hạn chế và biện pháp khắc phục các hạn chế của SOM trên cơ sở nghiên cứu các biến thể được cải tiến từ SOM. Chương 2 trình bày các nghiên cứu liên quan đến vấn đề đánh giá và cải thiện chất lượng bản đồ đặc trưng của mạng nơron SOM từ đó đưa ra hai đề xuất, gồm: Thứ nhất, đưa ra tham số điều chỉnh của hàm lân cận đối xứng dạng mũ. Tham số điều chỉnh được xác định riêng cho mỗi tập dữ liệu, cho phép giảm đồng thời cả lỗi lượng tử và lỗi hình trạng của mạng. 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, cho phép 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. Nội dung của đề xuất gồm một định nghĩa, một định lý, một hệ quả và một thuật toán. Chương 3 trình bày các nghiên cứu liên quan đến cải tiến SOM giám sát hoặc bán giám sát nói chung và áp dụng cho bài toán phân lớp nói riêng, từ đó đề xuất một cấu trúc SOM phân tầng tăng trưởng và thuật toán học bán giám sát cho mục đích 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 (100% dữ liệu huấn luyện có gán nhãn) hoặc mô hình phân lớp bán giám sát. Chương 4 trình bày các nghiên cứu liên quan đến việc cải tiến SOM áp dụng cho bài toán phân cụm dữ liệu, từ đó đưa ra hai đề xuất cải tiến cấu trúc và thuật toán học SOM, gồm: Thứ nhất, cải tiến thuật toán học của SOM cho phép từng bước hình thành các cụm và hiệu chỉnh các nơron thuộc về mỗi cụm trong quá trình học của mạng. Thứ hai, đưa ra một cấu trúc SOM mở rộng hai lớp và thuật toán huấn luyện tương ứng cho mục đích phân cụm dữ liệu. Tiếp theo trình bày kết quả thực nghiệm của các phương thức đề xuất và so sánh kết quả với một số phương thức phân cụm khác. CHƯƠNG 1: TỔNG QUAN VỀ CÁC MÔ HÌNH MẠNG NƠRON TỰ TỔ CHỨC 1.1. Tổng quan về mạng nơron nhân tạo Mục này cung cấp các kiến thức tổng quan về mạng nơron nhân tạo gồm: khái niệm, các dạng kiến trúc căn bản, các phương pháp học, xu hướng phát triển các mạng nơron hiện nay. 1.2. Mạng nơron tự tổ chức b 1.2.1. Cấu trúc mạng nơron tự tổ chức Mạng nơron SOM có cấu trúc đơn lớp (Kohonen, 2001), gồm: các tín hiệu vào và lớp ra (được gọi là lớp Kohonen), trong đó, tất cả các đầu vào được kết nối đầy đủ với mọi nơron trên lớp ra Kohonen. a 1.2.2. Thuật toán học của mạng nơron tự tổ chức Thuật toán học của mạng nơron tự tổ chức hay thuật toán SOM (Kohonen, 2001), gồm 4 bước: Bước 1- Khởi tạo: Kích thước mạng (là kích thước lớp Kohonen), vector trọng số của các nơron: khởi tạo giá trị ngẫu nhiên, bán kính lân cận, tỉ lệ học khởi tạo. Hình 1. 1 Minh họa cấu trúc SOM với lớp Kohonen 2 chiều Bước 2- Cạnh tranh: Với mỗi mẫu đầu vào x(t)Rn tại lần huấn luyện thứ t, tìm nơron khớp nhất với mẫu x(t). Nơron c được gọi là nơron khớp nhất (BMU) nếu thỏa mãn công thức: 3  dist  x  t   wc  min x t   wi i  (1.1) Bước 3- Hợp tác: Cơ sở cho sự hợp tác giữa các nơron là phạm vi ảnh hưởng của BMU hay còn gọi là bán kính lân cận của BMU (ký hiệu Nc(t)). Nc(t) được xác định theo công thức:  t N c  t   N 0 exp      (1.2) trong đó: t là lân huấn luyện (hay lần học); N 0 là bán kính lân cận khởi tạo; Nc  t  là bán kính lân cận của BMU tại lần học thứ t;   T là hằng số thời gian, với T là tổng số lần học. log  N 0  Bước 4- Thích nghi: Điều chỉnh trọng số của BMU và các nơron trong bán kính lân cận của BMU theo công thức: wi  t  1  wi t   L t  hci t  v  wi t  (1.3) trong đó: - hci(t) là hàm nội suy theo khoảng cách (hay hàm lân cận), được xác định theo công thức:  r r 2  c i  hci  t   exp   2  2 N c  t   - (1.4) với rc và ri là vị trí tương ứng của nơron c và nơron i trong lớp Kohonen. L  t  là tỉ lệ học tại lần lặp thứ t, với 0  L  t   1 ). 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. t   L  t   L0  1   T  (1.5) trong đó: L0 là tỉ lệ học khởi tạo (01, 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  rc  ri   hci  t   exp   q Nc2 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ó: I  I1 , I 2 ,..., I s  (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: s E   x  centeri 2 (2.5) i 1 xI i trong đó, centeri là tâm cụm thứ i, xác định theo công thức: centeri  1 Ii x (2.6) xI i 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ó: Qi   d  x, wi  (2.7) xI i 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: d  x, wi   x  wi (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: QE  hay: QE  1 N 1 N s Q i i 1 s  i 1 xI i x  wi (2.9) (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 wi  centeri , 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à d  x, w j   d  x, wi  [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 x1  I i : d x1 , w j  d  x1 , wi  ; x2 là “phần tử khác biệt” của nơron i đối với nơron k, với   x2  I i : d  x2 , wk   d  x2 , wi  ; 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 d  x3 , wg   d  x3 , wi  . Đị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 Ii  I i \  x và I j  I j   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ử, QE(*j ) là lỗi lượng tử của mạng nếu Ii  I i \  x và I j  I j   x ; QE(*k ) 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 Ii  I i \  x và I k  I k   x . Ta có, QE(*j )  QE(*k ) khi và chỉ khi các khoảng cách d  x, w j   d  x, wk  [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 0.1890 0.1299 0.1129 0.0902 0.0810 0.1585 XOR 0.0318 0.0273 0.0427 0.0705 0.0925 0.0223 5.9702 5.0643 4.0276 2.2819 1.8472 2.9340 Aggregation 0.0549 0.0362 0.0294 0.0424 0.0678 0.0245 2.1839 1.9512 1.5194 0.9129 0.8206 1.1822 Flame 0.0700 0.0567 0.0407 0.0479 0.0833 0.0393 4.5859 4.0427 3.2618 1.9392 1.7401 2.4779 Pathbased 0.0561 0.0433 0.0373 0.0434 0.0794 0.0315 4.7595 4.1719 2.9239 2.2975 2.0085 3.4675 Spiral 0.0543 0.0404 0.0364 0.0413 0.0564 0.0284 5.2745 4.4829 3.5726 1.6236 1.5234 2.3559 Jain 0.0513 0.0395 0.0313 0.0443 0.0637 0.0269 4.4205 3.1508 2.5672 1.8323 1.7744 3.7595 Compound 0.0624 0.0349 0.0400 0.0630 0.0690 0.0299 2.2226 2.0212 1.8005 1.0730 0.9562 1.4606 R15 0.0722 0.0631 0.0368 0.0613 0.1162 0.0274 4.7676 4.1204 3.3943 2.0055 1.6793 2.4569 D31 0.0479 0.0352 0.0284 0.0332 0.0394 0.0207 0.7709 0.5353 0.4403 0.3773 0.3494 0.6430 Iris 0.0739 0.0689 0.0940 0.1196 0.1566 0.0548 2.7459 2.5736 2.2005 1.9150 1.7468 2.3755 Vowel 0.0537 0.0436 0.0448 0.0494 0.0497 0.0412 1.5841 1.4421 1.2468 0.9790 0.9156 1.0912 Zoo 0.0343 0.0254 0.0169 0.0162 0.0208 0.0104 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 0.1754 0.1587 0.1546 0.1518 0.1525 0.1513 XOR (q=1) 0.0534 0.0203 0.0225 0.0244 0.0238 0.0255 2.7895 3.0003 3.2722 3.6436 3.6100 3.8718 Aggregation (q=4) 0.0850 0.0300 0.0277 0.0273 0.0316 0.0282 1.1858 1.2105 1.2306 1.3158 1.4010 1.4209 Flame (q=4) 0.1438 0.0405 0.0284 0.0304 0.0331 0.0330 2.5458 2.4759 2.7586 2.8462 2.9400 2.9928 Pathbased (q=4) 0.1300 0.0313 0.0363 0.0351 0.0349 0.0304 3.5976 3.4319 3.4334 3.4603 3.4926 3.5797 Spiral (q=2) 0.0690 0.0290 0.0265 0.0290 0.0261 0.0264 2.3664 2.3519 2.7136 2.9018 3.1494 3.3035 Jain (q=4) 0.0896 0.0263 0.0270 0.0306 0.0402 0.0403 4.2063 3.7575 3.6224 3.4969 3.5082 3.4913 Compound (q=1) 0.0666 0.0291 0.0337 0.0340 0.0373 0.0398 1.3161 1.4406 1.5544 1.6498 1.6972 1.7376 R15 (q=4) 0.1055 0.0294 0.0367 0.0390 0.0454 0.0548 2.3832 2.4769 2.8137 2.9886 3.0686 3.1960 D31 (q=4) 0.0803 0.0199 0.0227 0.0238 0.0259 0.0284 0.7140 0.6382 0.6166 0.6002 0.5880 0.5849 Iris (q=1) 0.0665 0.0518 0.0555 0.0560 0.0572 0.0598 2.3938 2.3715 2.4186 2.4310 2.4529 2.4627 Vowel (q=2) 0.0635 0.0410 0.0416 0.0414 0.0429 0.0455 1.1817 1.0912 1.1780 1.1954 1.2015 1.2131 Zoo (q=4) 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 hci(t) với tham Hàm Hàm lân cận Tập dữ liệu hci(t) gốc số điều chỉnh “nổi bọt” bất đối xứng 0.1890 0.1585 0.2572 0.1808 XOR 0.0318 0.0223 0.2708 0.4635 5.9702 2.9340 7.3092 4.9466 Aggregation 0.0549 0.0245 0.1794 0.4476 2.1839 1.1822 2.6352 2.1916 Flame 0.0700 0.0393 0.1642 0.6828 4.5859 2.4779 5.524 5.3888 Pathbased 0.0561 0.0315 0.1981 0.2715 4.7595 3.4675 5.6515 4.3775 Spiral 0.0543 0.0284 0.1502 0.6306 5.2745 2.3559 6.3026 5.4962 Jain 0.0513 0.0269 0.2024 0.3172 4.4205 3.7595 5.5663 3.5529 Compound 0.0624 0.0299 0.2199 0.4349 2.2226 1.4606 2.5017 1.8911 R15 0.0722 0.0274 0.1384 0.6337 4.7676 2.4569 5.6095 5.958 D31 0.0479 0.0207 0.2054 0.3506 0.7709 0.6430 1.001 0.9284 Iris 0.0739 0.0548 0.2312 0.2610 2.7459 2.3755 3.1022 2.8808 Vowel 0.0537 0.0412 0.1872 0.3965 1.5841 1.0912 1.7182 1.7179 Zoo 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 55 1010 1515 Tập dữ liệu BatchBatchBatchSOM SOM SOM IMQS IMQS IMQS 0.1938 0.0716 0.1344 0.040 0.115 0.0293 XOR 0 0.0735 0 0.1270 0 0.1801 6.5617 1.8581 4.0004 1.1341 3.7515 0.9058 Aggregation 0 0.0774 0 0.0952 0.0114 0.2513 2.2242 0.8802 1.8174 0.4820 1.4581 0.3800 Flame 0 0.0292 0 0.2333 0.0083 0.3125 4.7585 1.6497 3.6075 0.8606 3.1839 0.5932 Pathbased 0.0133 0.1667 0.0067 0.24 0.0133 0.3067 12 Spiral Jain Compound R15 D31 Iris Vowel Zoo 4.9053 0 5.2967 0 4.4481 0 2.2694 0 5.1947 0 0.7622 0.0200 2.6522 0.003 1.6328 0 1.8792 0.1667 1.6913 0.0483 1.4561 0.0526 0.9755 0.0033 1.2570 0.1639 0.3926 0.1867 1.5399 0.1222 0.9977 0.099 3.6889 0 3.7646 0.0054 3.0018 0.0050 1.8055 0 3.3776 0 0.5526 0.0133 2.2776 0.0172 1.3044 0 0.8728 0.3397 1.0424 0.1609 0.8799 0.2030 0.8900 0.0183 0.7306 0.0816 0.2398 0.2400 1.1500 0.4212 0.7192 0.1188 3.2971 0.0032 3.1354 0.0107 2.5214 0.015 1.5845 0 2.9099 0.001 0.4995 0.0133 2.1422 0.0121 1.2268 0 0.6095 0.3429 0.7534 0.1796 0.694 0.1955 0.5435 0.0117 0.6021 0.2094 0.1793 0.3067 0.9997 0.4485 0.6645 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). - Ymap 2 y 2 1 2 1 1 3 1 1 3 2 Xmap -1 2 3 2 2 x Ymap Ymap -1 Xmap Xmap Hình 3. 1 Minh họa cấu trúc mạng GHSSOM. 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). 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, I child  I parent 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: nchild   | I   | child   ceil   n    | I parent |  parent     (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: qek    QE0 (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:  d  x t  , w T0 QE0  BMU  t  t 1  (3.3) T0 trong đó: x(t) là mẫu đầu vào tại lần huấn luyện thứ t; wBMU t  là trọng số của BMU đối với mẫu đầu   vào x(t); d x  t  , wBMU t  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. nchild  ceil  I parent  (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). Ymap  k   ymin (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) xmin  1 min  x , y I child  xw  k (3.6) 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 XOR Aggregation Flame Pathbased Spiral Jain Compound R15 D31 Iris Vowel Zoo 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% 99.10 99.76 99.83 99.90 99.98 100 95.69 97.08 98.87 99.11 99.37 99.49 89.58 95.83 96.25 97.50 98.75 99.17 68.0 82.67 89.67 92.67 94.33 95.67 49.38 55.13 65.03 72.41 84.25 91.04 96.52 98.67 99.46 99.47 99.73 100 79.71 87.72 89.73 91.98 93.74 95.24 88.33 93.33 96.50 97.33 97.67 98.67 89.68 92.61 94.13 94.55 94.67 95.42 90.0 92.0 92.67 94.67 95.33 96.0 31.81 51.52 61.92 80.61 84.95 90.61 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 (SOMPartitional). 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). r E    w  centeri 2 (4.1) i 1 wQi 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: d  wBMU , centerBMU    (4.2) trong đó: wBMU là trọng số của BMU; centerBMU là tâm của nhóm mà BMU thuộc về (là một trong r nhóm hoặc nhóm 0). centerBMU  1 QBMU  Ni QBMU wi (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; d  wBMU , centerBMU  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. Sc  1 N N  d  x , center  k 1 k 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: (4.2b)