Tài liệu Tính toán mờ trong mạng kohonen và ứng dụng phân cụm dữ liệu

LỜI CẢM ƠN Sau một thời gian học tập, nghiên cứu và triển khai đề tài: “Tính toán mờ trong mạng Kohonen và ứng dụng phân cụm dữ liệu”, đến nay tôi đã hoàn thành đề tài nghiên cứu của mình. Tôi xin bày tỏ tấm lòng biết ơn sâu sắc nhất tới thầy giáo - Thạc sỹ Nguyễn Duy Hiếu người thầy đã trực tiếp hướng dẫn tôi trong suốt quá trình tôi thực hiện đề tài nghiên cứu khoa học này. Tôi cũng chân thành cảm ơn tới lãnh đạo Nhà trường, Ban chủ nhiệm Khoa cùng các thầy cô giáo đã giúp đỡ, tạo điều kiện để tôi có cơ hội nghiên cứu, học tập và hoàn thành đề tài nghiên cứu này. Do hạn chế về trình độ chuyên môn và thời gian thực hiện nên đề tài không tránh khỏi những thiếu sót, rất mong nhận được sự góp ý của thầy cô để tôi có thể hoàn thành tốt nhất đề tài nghiên cứu này. Tôi xin chân thành cảm ơn! Sơn la, tháng 5 năm 2014 Sinh viên Hoàng Khánh Linh 1 MỤC LỤC PHẦN MỞ ĐẦU ......................................................................................................7 1. Lý do chọn đề tài..............................................................................................7 2. Mục đích, nhiệm vụ nghiên cứu ......................................................................7 3. Đối tƣợng nghiên cứu ......................................................................................7 4. Phạm vi nghiên cứu .........................................................................................7 5. Phƣơng pháp nghiên cứu .................................................................................7 6. Cấu trúc của đề tài............................................................................................7 CHƢƠNG 1 TỔNG QUAN VỀ MÔ HÌNH MẠNG NƠ-RON .............................8 1.1. Mạng nơ-ron nhân tạo...................................................................................8 1.1.1. Mạng nơ-ron nhân tạo là gì?..................................................................8 1.1.2 Cấu trúc và mô hình của một nơ-ron nhân tạo .......................................8 1.1.3 Cấu tạo và phƣơng thức làm việc của mạng nơ-ron ............................10 1.1.4. Các kiểu mạng nơ-ron .........................................................................12 1.2.Các phƣơng pháp học ..................................................................................16 1.2.1. Khái Niệm ............................................................................................16 1.2.2. Học có giám sát....................................................................................16 1.2.3. Học không giám sát .............................................................................17 1.2.4. Học nửa giám sát .................................................................................18 1.2.5. Học tăng cƣờng ....................................................................................18 CHƢƠNG 2 LÝ THUYẾT TẬP MỜ....................................................................19 2.1. Tập mờ ........................................................................................................19 2.1.1. Khái niệm tập rõ ..................................................................................19 2.1.2. Khái niệm tập mờ ................................................................................19 2.2. Số mờ ..........................................................................................................21 2.2.1. Định nghĩa số mờ .................................................................................21 2.2.2. Số mờ đơn trị .......................................................................................21 2.2.3. Số mờ tam giác ....................................................................................21 2.2.4. Số mờ hình thang .................................................................................22 2 2.2.5. Số mờ hình chuông(Gauss) .................................................................22 2.3. Biến ngôn ngữ .............................................................................................22 2.4. Bộ giải mờ ...................................................................................................24 2.4.1. Phƣơng pháp lấy max ..........................................................................24 2.4.2. Phƣơng pháp lấy trọng tâm..................................................................24 2.4.3. Phƣơng pháp lấy trung bình tâm .........................................................24 CHƢƠNG 3 KỸ THUẬT SOM VÀ BÀI TOÁN PHÂN CỤM DỮ LIỆU .........25 3.1. Sơ lƣợc về SOM..........................................................................................25 3.2. Kiến trúc của SOM .....................................................................................25 3.3. Thuật toán phân cụm sử dụng SOM ...........................................................26 3.4. Ví dụ minh họa thuật toán ..........................................................................27 CHƢƠNG 4 ỨNG DỤNG MINH HỌA ..............................................................32 4.1. Mô tả dữ liệu ...............................................................................................32 4.2. Lựa chọn ngôn ngữ lập trình và hệ quản trị cơ sở dữ liệu .........................32 4.3. Cài đặt thuật toán ........................................................................................32 4.3.1. Cài đặt thuật toán .................................................................................32 4.3.2. Đánh giá ứng dụng...............................................................................36 KẾT LUẬN ............................................................................................................37 1. Kết luận ..........................................................................................................37 2. Hƣớng nghiên cứu phát triển đề tài ...............................................................37 TÀI LIỆU THAM KHẢO .....................................................................................38 3 DANH SÁCH HÌNH VẼ Hình 1. Mô hình nơ-ron nhân tạo ............................................................................8 Hình 2: Đồ thị các dạng hàm truyền ......................................................................10 Hình 3: Mạng nơ-ron ba lớp ..................................................................................11 Hình 4: Một số dạng mạng nơ-ron ........................................................................13 Hình 5 Cấu trúc của mạng Hopfield ......................................................................14 Hình 6: Cấu trúc của BAM ....................................................................................15 Hình 7: Đồ thị hàm thuộc µA(x) ..............................................................................20 Hinh 8: Số mờ tam giác .........................................................................................22 Hinh 9: Số mờ hình thang ......................................................................................22 Hình 10: Số mờ hình chuông .................................................................................22 Hình 11: Đồ thị biểu diễn mỗi quan hệ giữa nhiệt độ và độc thuộc .....................23 Hình 12: Kiến trúc của SOM .................................................................................26 Hình 13: Kiến trúc SOM đơn giản ........................................................................26 Hinh 14: Sơ đồ mạng Kohonen cho ví dụ trên ......................................................29 Hình 15: Giao diện chính của chƣơng trình ..........................................................33 Hình 16: Sau khi phân cụm hoàn tất......................................................................34 Hinh 17: Dữ liệu ban đầu .......................................................................................34 Hinh 18: Kết quả phân cụm - Cụm 1 .....................................................................35 Hình 19: Kết quả phân cụm - Cum 2 .....................................................................35 Hinh 20: Kết quả phân cụm - Cum 3 .....................................................................36 4 DANH MỤC BẢN BIỂU Bảng 1: Số mờ cho trƣờng buying.........................................................................28 Bảng 2: Số mờ cho trƣờng maint ...........................................................................28 Bảng 3: Số mờ cho trƣờng lug_boot .....................................................................28 Bảng 4: Số mờ cho trƣờng safety ..........................................................................28 Bảng 5: Dữ liệu đầu vào của ví dụ ........................................................................28 Bảng 6: Các trƣờng thông tin trong CSDL............................................................32 5 DANH MỤC TỪ VIẾT TẮT SOM Self Organizing Maps ANN Artificial Neural Network PE Processing Element MDP Markov Decision Process PCDL Phân cụm dữ liệu CSDL Cơ sở dữ liệu 6 PHẦN MỞ ĐẦU 1. Lý do chọn đề tài Phân cụm sử dụng mạng Kohonen (SOM: Self-Organizing Maps): Loại phân cụm này dựa trên khái niệm của các mạng nơ-ron. Mạng SOM có tầng nơ-ron vào và tầng nơ-ron ra. Mỗi nơ-ron của tầng vào tƣơng ứng với mỗi thuộc tính của bản ghi, mỗi một nơ-ron vào kết nối với tất cả các nơ-ron của tầng ra. Mỗi liên kết đƣợc gắn liền với một trọng số nhằm xác định vị trí của nơ-ron ra tƣơng ứng. Trong số này , SOM là một giải thuật đƣợc phát triển bởi Kohonen , nó có thể đƣợc áp dụng cho nhiều lớp bài toán khác nhau . Giải thuật SOM ban đầu đƣợc phát triể n cho mu ̣c đić h phân loa ̣i tiế ng nói , tuy nhiên SOM còn có thể áp du ̣ng đƣơ ̣c trong nhiề u liñ h vƣ̣c khác nhƣ điề u khiể n tƣ̣ đô ̣ng (Control Engineering), nhâ ̣n da ̣ng tiế ng nói (Kohonen, 1989), robotics (Ritter et al ., 1989), máy ảo (Oja, 1992), tố i ƣu tổ hơ ̣p (Fort, 1988), phân lớp (Kohonen, 1984), hóa - sinh trắ c ho ̣c (Biomedical Sciences and Chemistry), phân tić h tà i chiń h (Financial Analysis) và xử lý ngôn ngữ tự nhiên (Natural Language Processing). 2. Mục đích, nhiệm vụ nghiên cứu - Tìm hiểu mạng nơ-ron và kỹ thuật SOM. - Triển khai ứng dụng sử dụng kỹ thuật SOM vào phân cụm dữ liệu. 3. Đối tƣợng nghiên cứu - Mạng nơ-ron và kỹ thuật Self Organizing Map (SOM). 4. Phạm vi nghiên cứu - Nghiên cứu kỹ thuật SOM và sử dụng SOM để phân cụm dữ liệu. - Cài đặt chƣơng trình ứng dụng thử nghiệm. 5. Phƣơng pháp nghiên cứu - Nghiên cứu lý thuyết và xây dựng mô hình ứng dụng cho bài toán thực tế - Thu thập số liệu thực tế để thử nghiệm trên mô hình - Xây dựng chƣơng trình thử nghiệm 6. Cấu trúc của đề tài Đề tài gồm ba phần: - Phần 1: Phần mở đầu - Phần 2: Phần nội dung của đề tài gồm 4 chƣơng: Chƣơng 1: Tổng quan về mô hình mạng nơ-ron Chƣơng 2: Lý thuyết tập mờ Chƣơng 3: Kỹ thuật SOM và bài toán phân cụm dữ liệu Chƣơng 4: Chƣơng trình minh họa - Phần 3: Kết luận và hƣớng nghiên cứu phát triển đề tài 7 CHƢƠNG 1 TỔNG QUAN VỀ MÔ HÌNH MẠNG NƠ-RON 1.1. Mạng nơ-ron nhân tạo 1.1.1. Mạng nơ-ron nhân tạo là gì? Định nghĩa: Mạng nơ-ron nhân tạo (Artificial Neural Network - ANN) gọi tắt là mạng nơ-ron là một mô hình xử lý thông tin phỏng theo cách thức xử lý thông tin của các hệ nơ-ron sinh học. Nó đƣợc tạo lên từ một số lƣợng lớn các phần tử (gọi là phần tử xử lý hay nơ-ron) kết nối với nhau thông qua các liên kết (gọi là trọng số liên kết) làm việc nhƣ một thể thống nhất để giải quyết một vấn đề cụ thể nào đó. Một mạng nơ-ron nhân tạo đƣợc cấu hình cho một ứng dụng cụ thể (nhận dạng mẫu, phân loại dữ liệu...) thông qua một quá trình học từ tập các mẫu huấn luyện. Về bản chất học chính là quá trình hiệu chỉnh trọng số liên kết giữa các nơ-ron. 1.1.2 Cấu trúc và mô hình của một nơ-ron nhân tạo Mô hình toán học của mạng nơ-ron sinh học đƣợc đề xuất bởi McCulloch và Pitts, thƣờng đƣợc gọi là nơ-ron M-P, ngoài ra nó còn đƣợc gọi là phần tử xử lý và đƣợc ký hiệu là PE (Processing Element). Mô hình nơ-ron có m đầu vào x1, x2, ..., xm và một đầu ra yi nhƣ sau: Hình 1. Mô hình nơ-ron nhân tạo Giải thích các thành phần cơ bản: Tập các đầu vào: Là các tín hiệu vào của nơ-ron, các tín hiệu này thƣờng đƣợc đƣa vào dƣới dạng một vector m chiều. Tập các liên kết (các trọng số): Mỗi liên kết đƣợc thể hiện bởi một trọng số (thƣờng đƣợc gọi là trọng số liên kết). Trọng số liên kết giữa tín hiệu vào thứ j cho nơron i thƣờng đƣợc ký hiệu là wij. Thông thƣờng các trọng số này đƣợc khởi tạo ngẫu nhiên ở thời điểm khởi tạo mạng và đƣợc cập nhật liên tục trong quá trình học mạng. 8 Bộ tổng (Hàm tổng): Thƣờng dùng để tính tổng của tích các đầu vào với trọng số liên kết của nó. Ngƣỡng: Ngƣỡng này thƣờng đƣợc đƣa vào nhƣ một thành phần của hàm truyền. Hàm truyền: Hàm này dùng để giới hạn phạm vi đầu ra của mỗi nơ-ron. Nó nhận đầu vào là kết quả của hàm tổng và ngƣỡng đã cho. Thông thƣờng, phạm vi đầu ra của mỗi nơ-ron đƣợc giới hạn trong đoạn [0,1] hoặc [-1,1]. Các hàm truyền rất đa dạng, có thể là các hàm tuyến tính hoặc phi tuyến. Việc lựa chọn hàm truyền tùy thuộc vào từng bài toán và kinh nghiệm của ngƣời thiết kế mạng. Đầu ra: Là tín hiệu đầu ra của một nơ-ron, với mỗi nơ-ron sẽ có tối đa một đầu ra. Về mặt toán học, cấu trúc của một nơ-ron i đƣợc mô tả bằng cặp biểu thức sau: n yi  f (neti   i ) và neti   wij x j j 1 Trong đó: x1, x2, …xm là các tín hiệu đầu vào, còn wi1, wi2,…,wim là các trọng số kết nối của nơ-ron thứ i, neti là hàm tổng, f là hàm truyền, i là một ngƣỡng, yi là tín hiệu đầu ra của nơ-ron. Nhƣ vậy, tƣơng tự nhƣ nơ-ron sinh học, nơ-ron nhân tạo cũng nhận các tín hiệu đầu vào, xử lý (nhân các tín hiệu này với trọng số liên kết, tính tổng các tích thu đƣợc rồi gửi kết quả đến hàm truyền), và cho một tín hiệu đầu ra (là kết quả của hàm truyền). * Hàm truyền có thể có các dạng sau: Hàm bƣớc 1 y 0 khi x  0 (1.1) khi x  0 Hàm giới hạn chặt  1 khi x  0 y  sgn(x)    1 khi x  0 (1.2) Hàm bậc thang x 1 1 khi  y  sgn(x)   x khi 0  x  1 0 khi x0  (1.3) Hàm ngƣỡng đơn cực y 1 1  e  x với λ>0 (1.4) Hàm ngƣỡng hai cực 9 y 2  1 với λ>0 1  e  x (1.5) * Đồ thị các dạng hàm truyền đƣợc biểu diễn nhƣ sau: Hình 2: Đồ thị các dạng hàm truyền 1.1.3 Cấu tạo và phƣơng thức làm việc của mạng nơ-ron Dựa trên những phƣơng pháp xây dựng nơ-ron đã trình bày ở mục trên, ta có thể hình dung mạng nơ-ron nhƣ là một hệ truyền đạt và xử lý tín hiệu. Đặc tính truyền đạt của nơ-ron phần lớn là đặc tính truyền đạt tĩnh. Khi liên kết các đầu vào/ra của nhiều nơ-ron với nhau, ta thu đƣợc một mạng nơron, việc ghép nối các nơ-ron trong mạng với nhau có thể là theo một nguyên tắc bất kỳ. Vì mạng nơ-ron là một hệ truyền đạt và xử lý tín hiệu, nên có thể phân biệt các loại nơ-ron khác nhau, các nơ-ron có đầu vào nhận thông tin từ môi trƣờng bên ngoài khác với các nơ-ron có đầu vào đƣợc nối với các nơ-ron khác trong mạng, chúng đƣợc phân biệt với nhau qua vector hàm trọng số ở đầu vào w. Nguyên lý cấu tạo của mạng nơ-ron bao gồm nhiều lớp, mỗi lớp bao gồm nhiều nơ-ron có cùng chức năng trong mạng. Hình 3 là mô hình hoạt động của một mạng nơron 3 lớp với 8 phần tử nơ-ron. Mạng có ba đầu vào là x1, x2, x3 và hai đầu ra y1, y2. Các tín hiệu đầu vào đƣợc đƣa đến 3 nơ-ron đầu vào, 3 nơ-ron này làm thành lớp đầu vào của mạng. Các nơ-ron trong lớp này đƣợc gọi là nơ-ron đầu vào. Đầu ra của các 10 nơ-ron này đƣợc đƣa đến đầu vào của 3 nơ-ron tiếp theo, 3 nơ-ron này không trực tiếp tiếp xúc với môi trƣờng bên ngoài mà làm thành lớp ẩn, hay còn gọi là lớp trung gian. Các nơ-ron trong lớp này có tên là nơ-ron nội hay nơ-ron ẩn. Đầu ra của các nơ-ron này đƣợc đƣa đến 2 nơ-ron đƣa tín hiệu ra môi trƣờng bên ngoài. Các nơ-ron trong lớp đầu ra này đƣợc gọi là nơ-ron đầu ra. Hình 3: Mạng nơ-ron ba lớp Mạng nơ-ron đƣợc xây dựng nhƣ trên là mạng gồm 3 lớp mắc nối tiếp nhau đi từ đầu vào đến đầu ra. Trong mạng không tồn tại bất kỳ một mạch hồi tiếp nào. Một mạng nơ-ron có cấu trúc nhƣ vậy gọi là mạng một hƣớng hay mạng truyền thẳng một hƣớng (Feed forward network), và có cấu trúc mạng ghép nối hoàn toàn (vì bất cứ một nơ-ron nào trong mạng cũng đƣợc nối với một hoặc vài nơ-ron khác). Mạng nơ-ron bao gồm một hay nhiều lớp trung gian đƣợc gọi là mạng Multilayer Perceptrons (MLP-Network). Mạng nơ-ron khi mới đƣợc hình thành thì chƣa có tri thức, tri thức của mạng sẽ đƣợc hình thành dần dần sau một quá trình học. Mạng nơ-ron đƣợc học bằng cách đƣa vào những kích thích, và mạng hình thành những đáp ứng tƣơng ứng, những đáp ứng tƣơng ứng phù hợp với từng loại kích thích sẽ đƣợc lƣu trữ. Giai đoạn này đƣợc gọi là giai đoạn học của mạng. Khi đã hình thành tri thức mạng, mạng có thể giải quyết các vấn đề một cách đúng đắn. Đó có thể là vấn đề ứng dụng rất khác nhau, đƣợc giải quyết chủ yếu dựa trên sự tổ chức hợp nhất giữa các thông tin đầu vào của mạng và các đáp ứng đầu ra. Mạng nơ-ron có nhiệm vụ là hoàn chỉnh hoặc hiệu chỉnh các thông tin thu đƣợc không đầy đủ hoặc bị tác động của nhiễu, đƣợc ứng dụng trong lĩnh vực hoàn thiện mẫu, trong đó có một ứng dụng cụ thể là nhận dạng chữ viết. Nhiệm vụ tổng quát của một mạng nơ-ron là lƣu giữ động các thông tin. Dạng thông tin lƣu giữ này chính là quan hệ giữa các thông tin đầu vào và các đáp ứng đầu ra tƣơng ứng, để khi có một kích thích bất kỳ tác động vào mạng, mạng có khả năng suy diễn và đƣa ra một đáp ứng phù hợp. Đây chính là chức năng nhận dạng theo mẫu 11 của mạng nơ-ron. Để thực hiện chức năng này, mạng nơ-ron đóng vai trò nhƣ một bộ phận tổ chức các nhóm thông tin đầu vào, và tƣơng ứng với mỗi nhóm là một đáp ứng đầu ra phù hợp. Nhƣ vậy, một nhóm bao gồm một loại thông tin đầu vào và một đáp ứng đầu ra. Các nhóm có thể đƣợc hình thành trong quá trình học, và cũng có thể không hình thành trong quá trình học. 1.1.4. Các kiểu mạng nơ-ron 1.1.4.1. Mạng nơ-ron một lớp Mỗi một nơ-ron có thể phối hợp với các nơ-ron khác tạo thành một lớp các trọng số. Mạng một lớp truyền thẳng nhƣ hình 4a. Một lớp nơ-ron là một nhóm các nơ-ron mà chúng đều có cùng trọng số, nhận cùng một tín hiệu đầu vào đồng thời. Trong ma trận trọng số, các hàng là thể hiện nơ-ron, hàng thứ j có thể đặt nhãn nhƣ một vector wj của nơ-ron thứ j gồm m trọng số wji. Các trọng số trong cùng một cột thứ j (j=1,2,...,n) đồng thời cùng nhận một tín hiệu đầu vào xj. wj = [wj1, wj2, ..., wjm] Tại cùng một thời điểm, vector đầu vào x = [x1, x2,..., xn] có thể là một nguồn bên ngoài là cảm biến hoặc thiết bị đo lƣờng đƣa tới mạng. (a) Mạng truyền thẳng một lớp (b) Mạng hồi tiếp một lớp (c) Mạng truyền thẳng nhiều lớp 12 (d) Mạng nơ-ron hồi quy Hình 4: Một số dạng mạng nơ-ron 1.1.4.2. Mạng nơ-ron truyền thẳng nhiều lớp Mạng nơ-ron nhiều lớp (Hình 4c) có các lớp đƣợc phân chia thành 3 loại sau đây: Lớp vào là lớp nơ-ron đầu tiên nhận tín hiệu vào xi (i = 1, 2, ..., n). Mỗi tín hiệu xi đƣợc đƣa đến tất cả các nơ-ron của lớp đầu vào. Thông thƣờng, các nơ-ron đầu vào không làm biến đổi các tín hiệu vào xi, tức là chúng không có các trọng số hoặc không có các loại hàm chuyển đổi nào, chúng chỉ đóng vai trò phân phối các tín hiệu. Lớp ẩn là lớp nơ-ron sau lớp vào, chúng không trực tiếp liên hệ với thế giới bên ngoài nhƣ các lớp nơ-ron vào/ra. Lớp ra là lớp nơ-ron tạo ra các tín hiệu ra cuối cùng. 1.1.4.3 Mạng nơ-ron hồi tiếp Mạng nơ-ron hồi tiếp là mạng mà đầu ra của mỗi nơ-ron đƣợc quay trở lại nối với đầu vào của các nơ-ron cùng lớp đƣợc gọi là mạng Laeral nhƣ hình 4b. 1.1.4.4 Mạng nơ-ron hồi quy Mạng nơ-ron phản hồi có thể thực hiện đóng vòng đƣợc gọi là mạng nơ-ron hồi quy nhƣ hình 4d. Mạng nơ-ron hồi quy có trọng số liên kết đối xứng nhƣ mạng Hopfield, mạng luôn hội tụ về trạng thái ổn định (Hình 4b). Mạng BAM thuộc nhóm mạng nơ-ron hồi quy, gồm 2 lớp liên kết 2 chiều, không đƣợc gắn với tín hiệu vào/ra. Nghiên cứu mạng nơ-ron hồi quy mà có trọng số liên kết không đối xứng, thì sẽ gặp phải vấn đề phức tạp nhiều hơn so với mạng truyền thẳng và mạng hồi quy có trọng số liên kết đối xứng. 1.1.4.5 Mạng Hopfield Mạng Hopfield là mạng phản hồi một lớp, đƣợc chỉ ra trong hình 4b. Cấu trúc chi tiết của nó đƣợc thể hiện trong hình 5. Khi hoạt động với tín hiệu rời rạc, nó đƣợc gọi là mạng Hopfield rời rạc, và cấu trúc của nó cũng đƣợc gọi là mạng hồi quy. 13 Hình 5 Cấu trúc của mạng Hopfield Nhƣ mạng Hopfield đã vẽ ở trên, ta thấy nút có một đầu vào bên ngoài xj và một giá trị ngƣỡng  j (j = 1,2,...n). Một điều quan trọng cần nói ở đây là mỗi nút không có đƣờng phản hồi về chính nó. Nút đầu ra thứ j đƣợc nối tới mỗi đầu vào của nút khác qua trọng số wij, với i  j, (i = 1,2,...,n), hay nói cách khác wii = 0, (với i = 1,2,...,n). Một điều quan trọng nữa là trọng số của mạng Hopfield là đối xứng, tức là wij = wji, (với i,j = 1,2,...,n). Khi đó, luật cập nhật cho mỗi nút mạng là nhƣ sau:  n    (k ) (1.6) y  sgn   wij y j  xi   , i = 1,2,...,n  j 1   j i  Luật cập nhật trên đƣợc tính toán trong cách thức không đồng bộ. Điều này có ( k 1) i nghĩa là, với một thời gian cho trƣớc, chỉ có một nút mạng cập nhật đƣợc đầu ra của nó. Sự cập nhật tiếp theo trên một nút sẽ sử dụng chính những đầu ra đã đƣợc cập nhật. Nói cách khác, dƣới hình thức hoạt động không đồng bộ của mạng, mỗi đầu ra đƣợc cập nhật độc lập. Có sự khác biệt giữa luật cập nhật đồng bộ và luật cập nhật không đồng bộ. Với luật cập nhật không đồng bộ thì sẽ chỉ có một trạng thái cân bằng của hệ (với giá trị đầu đã đƣợc xác định trƣớc). Trong khi đó, với luật cập nhật đồng bộ thì có thể làm mạng hội tụ ở mỗi điểm cố định hoặc một vòng giới hạn. 1.1.4.6 Mạng BAM Mạng BAM bao gồm hai lớp và đƣợc xem nhƣ là trƣờng hợp mở rộng của mạng Hopfield. Ở đây ta chỉ xét mạng rời rạc, vì nó đơn giản và dễ hiểu. 14 Hình 6: Cấu trúc của BAM Khi mạng nơ-ron đƣợc tích cực với giá trị đầu vào của vector tại đầu vào của một lớp, mạng sẽ có hai mẫu trạng thái ổn định, với mỗi mẫu tại đầu ra của nó là một lớp. Tính động học của mạng thể hiện dƣới dạng tác động qua lại giữa hai lớp. Cụ thể hơn, giả sử một vector đầu vào x đƣợc cung cấp cho đầu vào của lớp nơ-ron y. Đầu vào đƣợc xử lý và truyền tới đầu ra của lớp y nhƣ sau: y’ = a(wx) ;   y i'  a  wij x j    ; với i = 1,2,...,n (1.7) Ở đó a(.) là hàm truyền, vector y’ bây giờ lại nuôi trở lại lớp nơ-ron X và tạo nên đầu ra nhƣ sau: x’ = a(wTy’);  n  x j  a  wij yi  ;  i 1  với j = 1,2,...,m (1.8) Sau đó x’ nuôi trở lại đầu vào của lớp y và tạo ra hàm y’’ theo phƣơng trình (1.7). Quá trình này cứ tiếp tục, bao gồm các bƣớc nhƣ sau: y(1) = a(wx(0)) x(2) = a(w(T)y(1)) y(3) = a(wx(2)) x(4) = a(w(T)y(3)) (truyền thẳng lần thứ nhất) (truyền ngƣợc lần thứ nhất) (truyền thẳng lần thứ hai) (truyền ngƣợc lần thứ hai)  y(k-1) = a(wx(k-2)) (k) (T) (k-1) x = a(w y ) (1.9) (truyền thẳng lần thứ k/2) (truyền ngƣợc lần thứ k/2) Chú ý rằng trạng thái cập nhật trong phƣơng trình (1.9) là đồng bộ theo phƣơng trình (1.7) và (1.8). Trạng thái cập nhật cũng có thể không đồng bộ theo phƣơng trình (1.7) và (1.8) với các nút i, j đƣợc chọn tự do. Ngƣời ta đã chỉ ra rằng, hệ thống ổn định cho cả hai chế độ đồng bộ và không đồng bộ. Tuy nhiên, chế độ đồng bộ sẽ làm cho hệ thống hội tụ nhanh hơn. 15 1.2.Các phƣơng pháp học 1.2.1. Khái Niệm Khái niệm: Học là quá trình thay đổi hành vi của các vật theo một cách nào đó làm cho chúng có thể thực hiện tốt hơn trong tƣơng lai. Một mạng nơ-ron đƣợc huấn luyện sao cho với một tập các vector đầu vào X, mạng có khả năng tạo ra tập các vector đầu ra mong muốn Y của nó. Tập X đƣợc sử dụng cho huấn luyện mạng đƣợc gọi là tập huấn luyện (training set). Các phần tử x thuộc X đƣợc gọi là các mẫu huấn luyện (training example). Quá trình huấn luyện bản chất là sự thay đổi các trọng số liên kết của mạng. Trong quá trình này, các trọng số của mạng sẽ hội tụ dần tới các giá trị sao cho với mỗi vector đầu vào x từ tập huấn luyện, mạng sẽ cho ra vector đầu ra y nhƣ mong muốn Các phƣơng pháp học phổ biến là học có giám sát (supervised learning), học không giám sát (unsupervised learning), học nửa giám sát và học tăng cƣờng (Reinforcement learning). 1.2.2. Học có giám sát Học có giám sát (supervised learning) là một kĩ thuật của ngành học máy để xây dựng một hàm từ dữ liệu huấn luyện. Dữ liệu huấn luyện bao gồm mỗi cặp đối tƣợng đầu vào (thƣờng dạng vec-tơ) và đầu ra mong muốn. Đầu ra của một hàm có thể là một giá trị liên tục (gọi là hồi quy), hay có thể là dự đoán một nhãn phân loại cho một đối tƣợng đầu vào (gọi là phân loại). Nhiệm vụ của chƣơng trình học có giám sát là dự đoán giá trị của hàm cho một đối tƣợng bất kì là đầu vào hợp lệ, sau khi đã xem xét một số ví dụ huấn luyện (nghĩa là các cặp đầu vào và đầu ra tƣơng ứng). Để đạt đƣợc điều này, chƣơng trình học phải tổng quát hóa từ các dữ liệu sẵn có để dự đoán đƣợc những tình huống chƣa gặp phải theo một cách "hợp lí". Học có giám sát có thể tạo ra 2 loại mô hình. Phổ biến nhất, học có giám sát tạo ra một mô hình toàn cục (global model) để ánh xạ đối tƣợng đầu vào đến đầu ra mong muốn. Tuy nhiên, trong một số trƣờng hợp, việc ánh xạ đƣợc thực hiện dƣới dạng một tập các mô hình cục bộ (nhƣ trong phƣơng pháp lập luận theo tình huống hay giải thuật láng giềng gần nhất). Để có thể giải quyết một bài toán nào đó của học có giám sát (ví dụ: học để nhận dạng chữ viết tay) ngƣời ta phải xem xét nhiều bƣớc khác nhau: 1. Xác định loại của các ví dụ huấn luyện. Trƣớc khi làm bất cứ điều gì, ngƣời kĩ sƣ nên quyết định loại dữ liệu nào sẽ đƣợc sử dụng làm ví dụ. Chẳng hạn, đó có thể là một kí tự viết tay đơn lẻ, toàn bộ một từ viết tay, hay toàn bộ một dòng chữ viết tay. 16 2. Thu thập tập huấn luyện. Tập huấn luyện cần đặc trƣng cho thực tế sử dụng của hàm chức năng. Vì thế, một tập các đối tƣợng đầu vào đƣợc thu thập và đầu ra tƣơng ứng đƣợc thu thập, hoặc từ các chuyên gia hoặc từ việc đo đạc tính toán. 3. Xác định việc biểu diễn các đặc trƣng đầu vào cho hàm chức năng cần tìm. Sự chính xác của hàm chức năng phụ thuộc lớn vào cách các đối tƣợng đầu vào đƣợc biểu diễn. Thông thƣờng, đối tƣợng đầu vào đƣợc chuyển đổi thành một vec-tơ đặc trƣng, chứa một số các đặc trƣng nhằm mô tả cho đối tƣợng đó. Số lƣợng các đặc trƣng không nên quá lớn, do sự bùng nổ tổ hợp (curse of dimensionality); nhƣng phải đủ lớn để dự đoán chính xác đầu ra. 4. Xác định cấu trúc của hàm chức năng cần tìm và giải thuật học tƣơng ứng. Ví dụ, ngƣời kĩ sƣ có thể lựa chọn việc sử dụng mạng nơ-ron nhân tạo hay cây quyết định. 5. Hoàn thiện thiết kế. Ngƣời kĩ sƣ sẽ chạy giải thuật học từ tập huấn luyện thu thập đƣợc. Các tham số của giải thuật học có thể đƣợc điều chỉnh bằng cách tối ƣu hóa hiệu năng trên một tập con (gọi là tập kiểm chứng -validation set) của tập huấn luyện, hay thông qua kiểm chứng chéo (cross-validation). Sau khi học và điều chỉnh tham số, hiệu năng của giải thuật có thể đƣợc đo đạc trên một tập kiểm tra độc lập với tập huấn luyện. 1.2.3. Học không giám sát Học không có giám sát (unsupervised learning) là một phƣơng pháp của ngành học máy nhằm tìm ra một mô hình mà phù hợp với các quan sát. Nó khác biệt với học có giám sát ở chỗ là đầu ra đúng tƣơng ứng cho mỗi đầu vào là không biết trƣớc. Trong học không có giám sát, một tập dữ liệu đầu vào đƣợc thu thập. Học không có giám sát thƣờng đối xử với các đối tƣợng đầu vào nhƣ là một tập các biến ngẫu nhiên. Sau đó, một mô hình mật độ kết hợp sẽ đƣợc xây dựng cho tập dữ liệu đó. Học không có giám sát có thể đƣợc dùng kết hợp với suy diễn Bayes để cho ra xác suất có điều kiện (nghĩa là học có giám sát) cho bất kì biến ngẫu nhiên nào khi biết trƣớc các biến khác. Học không có giám sát cũng hữu ích cho việc nén dữ liệu: về cơ bản, mọi giải thuật nén dữ liệu hoặc là dựa vào một phân bố xác suất trên một tập đầu vào một cách tƣờng minh hay không tƣờng minh. Một dạng khác của học không có giám sát là phân mảnh (data clustering), nó đôi khi không mang tính xác suất. Xem thêm phân tích khái niệm hình thức (formal concept analysis). 17 1.2.4. Học nửa giám sát Trong khoa học máy tính, học nửa giám sát là một lớp của kỹ thuật học máy, sử dụng cả dữ liệu đã gán nhãn và chƣa gán nhãn để huấn luyện - điển hình là một lƣợng nhỏ dữ liệu có gán nhãn cùng với lƣợng lớn dữ liệu chƣa gán nhãn. Học nửa giám sát đứng giữa học không giám sát (không có bất kì dữ liệu có nhãn nào) và có giám sát (toàn bộ dữ liệu đều đƣợc gán nhãn). Nhiều nhà nghiên cứu nhận thấy dữ liệu không gán nhãn, khi đƣợc sử dụng kết hợp với một chút dữ liệu có gán nhãn, có thể cải thiện đáng kể độ chính xác. Để gán nhãn dữ liệu cho một bài toán học máy thƣờng đòi hỏi một chuyên viên có kĩ năng để phân loại bằng tay các ví dụ huấn luyện. Chi phí cho quy trình này khiến tập dữ liệu đƣợc gán nhãn hoàn toàn trở nên không khả thi, trong khi dữ liệu không gán nhãn thƣờng tƣơng đối rẻ tiền. Trong tình huống đó, học nửa giám sát có giá trị thực tiễn lớn lao. Một ví dụ cho kỹ thuật học máy nửa giám sát là đồng huấn luyện (co-training), trong đó hay hay nhiều bộ học đƣợc huấn luyện cùng một tập ví dụ nhƣng mỗi bộ sử dụng một tập đặc trƣng khác nhau, lý tƣởng nhất là độc lập với nhau. Một cách tiếp cận khác là mô hình hoá phân phối xác suất đồng thời của các đặc trƣng và nhãn. Với dữ liệu chƣa gán nhãn, có thể coi nhãn là "dữ liệu còn thiếu". Các kỹ thuật xử lý dữ liệu còn thiếu nhƣ là lấy mẫu Gibbs và tối ƣu kỳ vọng có thể đƣợc sử dụng để ƣớc lƣợng tham số. 1.2.5. Học tăng cƣờng Học tăng cƣờng (reinforcement learning) nghiên cứu cách thức một agent trong một môi trƣờng nên chọn thực hiện các hành động nào để cực đại hóa một khoản thƣởng (reward) nào đó về lâu dài. Các thuật toán học tăng cƣờng cố gắng tìm một chiến lƣợc ánh xạ các trạng thái của thế giới tới các hành động mà agent nên chọn trong các trạng thái đó. Môi trƣờng thƣờng đƣợc biểu diễn dƣới dạng một quá trình quyết định Markov trạng thái hữu hạn (Markov decision process - MDP), và các thuật toán học tăng cƣờng cho ngữ cảnh này có liên quan nhiều đến các kỹ thuật quy hoạch động. Các xác suất chuyển trạng thái và các xác suất thu lợi trong MDP thƣờng là ngẫu nhiên nhƣng lại tĩnh trong quá trình của bài toán. Khác với học có giám sát, trong học tăng cƣờng không có các cặp dữ liệu vào/kết quả đúng, các hành động gần tối ƣu cũng không đƣợc đánh giá đúng sai một cách tƣờng minh. Hơn nữa, ở đây hoạt động trực tuyến (on-line performance) đƣợc quan tâm, trong đó có việc tìm kiếm một sụ cân bằng giữa khám phá (lãnh thổ chƣa lập bản đồ) và khai thác (tri thức hiện có). Trong học tăng cƣờng, sự đƣợc và mất giữa khám phá và khai thác đã đƣờng nghiên cứu chủ yếu qua bài toán multi-armed bandit. 18 Một cách hình thức, mô hình học tăng cƣờng bao gồm: S: tập các trạng thái của môi trƣờng ; A: tập các hành động; và : tập các khoản "thƣởng" với giá trị vô hƣớng. Tại mỗi thời điểm t, agent thấy đƣợc trạng thái của nó là st S và tập các hành động có thể A(st). Nó chọn một hành động a A(st) và nhận đƣợc từ môi trƣờng trạng thái mới st+1và một khoản thƣởng rt+1. Dựa trên các tƣơng tác này, agent học tăng cƣờng phải phát triển một chiến lƣợc π:S A có tác dụng cực đại hóa lƣợng R=r0+r1+...+rn với các MDP có một trạng thái kết thúc, hoặc lƣợng R=Σtγtrt với các MDP không có trạng thái kết thúc (trong đó γ là một hệ số giảm khoản "thƣởng trong tƣơng lai" nào đó, với giá trị trong khoảng 0.0 và 1.0). Do đó, học tăng cƣờng đặc biệt thích hợp cho các bài toán có sự đƣợc mất giữa các khoản thƣởng ngắn hạn và dài hạn. Học tăng cƣờng đã đƣợc áp dụng thành công cho nhiều bài toán, trong đó có điều khiển robot, điều vận thang máy, viễn thông, các trò chơi backgammon và cờ vua. CHƢƠNG 2 LÝ THUYẾT TẬP MỜ 2.1. Tập mờ 2.1.1. Khái niệm tập rõ Một tập vũ trụ A là một tập rõ có nghĩa là có thể liệt kê tất cả các phần tử của A, chẳng hạn A = {3, 5, 6, 9}. Trong trƣờng hợp không thể liệt kê ra hết đƣợc các phần tử của tập A, chúng ta có thể chỉ ra các tính chất chính xác mà các phần tử của tập A thoả mãn, chẳng hạn A = {x | x là số nguyên tố}. Một tập rõ có thể đƣợc xác định bởi hàm đặc trƣng, hay còn gọi là hàm thuộc (membership function) của nó. Hàm thuộc của tập rõ A, đƣợc ký hiệu là λA , đó là hàm 2 trị (1/0), nó nhận giá trị 1 trên các đối tƣợng x thuộc tập A và giá trị 0 trên các đối tƣợng x không thuộc A. Giữa phần tử bất kỳ và tập A chỉ tồn tại một trong hai quan hệ thuộc hoặc không thuộc. 2.1.2. Khái niệm tập mờ Xung quanh chúng ta, luôn tồn tại các khái niệm mờ, nó hiện hữu trong các bài toán ứng dụng, ngay cả trong suy nghĩ của mỗi chúng ta. Ví dụ xét về tuổi của con ngƣời chúng ta có các khái niệm trẻ, rất trẻ, hơi già,… Chúng ta cúng xét ví dụ sau: Ta xét tập hợp những ngƣời trẻ. Ta thấy rằng ngƣời dƣới 25 tuổi thì rõ ràng là trẻ và ngƣời trên 60 tuổi thì rõ ràng là không trẻ. Nhƣng những ngƣời có tuổi từ 26 đến 59 thì có thuộc tập hợp những ngƣời trẻ hay không? Nếu áp dụng khái niệm tập hợp cổ điển thì ta phải định ra một ranh giới rõ ràng và mang tính chất áp đặt chẳng hạn là 45 19 để xác định tập hợp những ngƣời trẻ. Nhƣng ta không thể chắc chắn ngƣời 45 tuổi là trẻ hay ngƣời 46 tuổi là không trẻ. Và trong thực tế thì có một ranh giới mờ để ngăn cách những ngƣời trẻ và những ngƣời không trẻ đó là những ngƣời trung niên. Nhƣ vậy, những ngƣời trung niên là những ngƣời có một “độ trẻ” nào đó. Nếu coi “độ trẻ” của ngƣời dƣới 25 tuổi là hoàn toàn đúng tức là có giá trị là 1 và coi “độ trẻ” của ngƣời trên 60 tuổi là hoàn toàn sai tức là có giá trị là 0, thì “độ trẻ” của ngƣời trung niên sẽ có giá trị p nào đó thoả 0 < p < 1. Nhƣ vậy, qua ví dụ trên ta thấy khái niện về tập hợp cổ điển không đáp ứng hết đƣợc các yêu cầu của thực tế và nó cần đƣợc mở rộng. L.A.Zadeh đã đề xuất hình thức hóa toán học của khái niệm mờ vào năm 1965, theo đó từ những khái niệm trừu tƣợng về ngữ nghĩa của thông tin mờ, không chắc chắn nhƣ trẻ-già, nhanh-chậm, cao-thấp,… tìm cách biểu diễn chúng bằng một khái niệm toán học, đƣợc gọi là tập mờ. Từ đó đến nay, lý thuyết tập mờ luôn đƣợc phát triển mạnh mẽ. Định nghĩa 2.1: Cho một tập vũ trụ U với các phần tử ký hiệu bởi x, U={x}. Một tập mờ A trên U là tập đƣợc đặc trƣng bởi một hàm µA(x) mà nó liên kết mỗi phần tử x∈U với một số thực trong đoạn [0,1]. Giá trị hàm µA(x) biểu diễn mức độ thuộc của x trong A. µA(x) là một ánh xạ từ U vào [0,1] và đƣợc gọi là hàm thuộc của tập mờ A. Giá trị hàm µA(x) càng gần tới 1 thì mức độ thuộc của x trong A càng cao, ngƣợc lại µA(x) càng gần tới 0 thì độ thuộc của x trong A càng thấp. Tập mờ là sự mở rộng của khái niệm tập hợp kinh điển(tập rõ). Thật vậy, khi A là một tập rõ, hàm thuộc µA(x) chỉ nhận 2 giá trị 1 hoặc 0, tƣơng ứng với x có nằm trong A hay không. Hình 7: Đồ thị hàm thuộc µA(x) * Một số khái niệm: Giả sử A, B,… là các tập mờ. Độ thuộc của phần tử x vào tập mờ A đƣợc ký hiệu là A(x). A(x) lấy giá trị trong đoạn [0, 1] với mọi x. Định nghĩa 2.2 (Tập mờ lồi): Cho tập mờ A của tập vũ trụ U. A là tập mờ lồi nếu 𝐴 𝜆𝑥 + 1 − 𝜆 𝑦 ≥ 𝑀𝑖𝑛 𝐴 𝑥 , 𝐴 𝑦 , ∀𝑥, 𝑦 ∈ 𝑈, 𝜆 ∈ 0,1 20