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
x0
(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
- Xem thêm -