ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Nguyễn Văn Dương
KANTS: HỆ KIẾN NHÂN TẠO CHO PHÂN LỚP
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Nguyễn Văn Dương
KANTS: Hệ kiến nhân tạo cho phân lớp
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
Cán bộ hướng dẫn:
Đồng hướng dẫn:
PGS.TS Hoàng Xuân Huấn
ThS. Đỗ Đức Đông
HÀ NỘI – 2010
LỜI CẢM ƠN
Tôi muốn bày tỏ sự cảm ơn sâu sắc của mình tới thầy Hoàng Xuân Huấn, thuộc bộ
môn Khoa học máy tính, khoa Công nghệ thông tin, trường Đại học Công nghệ,
ĐHQGHN. Trong thời gian thực hiện khóa luận, thầy đã nhiệt tình hướng dẫn và giúp đỡ
tôi rất nhiều. Ngoài thời gian tìm hiểu và cung cấp tài liệu, thầy cũng chỉ ra những vướng
mắc trong qua trình làm, giúp đỡ tôi khắc phục để đạt hiệu quả cao hơn. Ngoài ra tôi còn
muốn gửi lời cảm ơn tới thầy đồng hướng dẫn Đỗ Đức Đông, thầy cũng đã nhiệt tình giúp
đỡ tôi trong việc tìm hiểu giải quyết những khúc mắc sai lầm khi làm khóa luận này.
Tôi cũng muốn bày tỏ sự cảm ơn của mình tới các các thầy, các cô trong bộ môn,
cũng như các thầy, các cô trong khoa, trường đã hết sức tạo điều kiện tốt và giúp đỡ cho
tôi hoàn thành khóa luận của mình.
TÓM TẮT NỘI DUNG
Mặc dù đã được nghiên cứu từ rất lâu, nhưng đến nay bài phân lớp mẫu vẫn còn có
rất ít công cụ toán học để giải quyết và hiệu quả chưa cao. Mạng Neural nhân tạo là một
phương pháp hay để giải quyết bài toán phân lớp mẫu. Năm 1987, Kohonen giới thiệu
phương pháp bản đồ tự tổ chức là một loại mạng neural đơn giản và hiệu quả để giải
quyết bài toán phân cụm và phân lớp. Năm 1991, Dorigo giới thiệu phương pháp hệ kiến
để giải quyết các bài toán tối ưu tổ hợp rất hiệu quả. Từ đó, các mô hình giải quyết các bài
toán phức tạp mà tư tưởng dựa trên sự mô phỏng hành vì loài kiến đã đạt được nhiều
bước tiến đáng kể. Điển hình là hệ kiến của Chialvo và Millonas.
Nội dung chính của khóa luận là trình bày khảo cứu về thuật toán KANT (một sự
kết hợp) để giải quyết bài toán phân lớp sau đó ứng dụng cơ sở lý thuyết trên để xây dựng
chương trình kiểm tra độ chính xác của thuật toán so với k láng giềng gần nhất và cải tiến
một phần thuật toán bằng học tập hợp (Ensembler learning) để thu được kết quả tốt hơn.
Danh mục các hình
Hình 1: Minh họa một Neuron thần kinh sinh học
…………………………………………………….
5
Hình 2: Đồ thị hàm ngưỡng ………………………………………………………………………………….
7
Hình 3: Đồ thị hàm tuyến tính
……………………………………………………………………………….
7
Hình 4: Đồ thị hàm sigmoid
………………………………………………………………………………….
7
Hình 5: Đồ thị hàm tanh……………………………………………………………………………………….
8
Hình 6: Đồ thị hàm Gauss
…………………………………………………………………………………….
8
Hình 7: Kiến trúc mạng neural truyền tới
………………………………………………………………..
9
Hình 8: Mẫu dữ liệu ví dụ cho KNN …………………………………………………………………….
12
Hình 9: Trực quan hóa các mẫu trên mặt phẳng ……………………………………………………..
13
Hình 10: Bỏ phiếu các mẫu dữ liệu trong KNN………………………………………………………
14
Hình 11: Mô hình mạng SOM……………………………………………………………………………..
18
Hình 12: Các mạng SOM thể hiện phân bố các dữ liệu tập IRIS ……………………………….
19
Hình 13: Dạng ngẫu nhiên ban đầu của SOM ………………………………………………………..
21
Hình 14: Tráng thái lưới SOM sau một số bước huấn luyện
……………………………………..
22
Hình 15: Thí nghiệm cho thấy sự phân cụm các ấu trùng của kiến …………………………….
26
Hình 16: Mã giả thuật toán KA NTS
…………………………………………………………………….
29
Hình 17: Mã giả hàm quyết định bước đi tiếp theo
………………………………………………….
30
Hình 18: Công thức xác suất di chuyển
…………………………………………………………………
30
Hình 19: Lân cận khả dĩ
……………………………………………………………………………………..
31
Hình 20: Sự phân cụm của kiến theo tham sô
…………………………………………………………
38
Hình 21: Mô hình trực quan giải thích học tập hợp …………………………………………………
42
Hình 22: Mô hình nguyên lý học tập hợp ………………………………………………………………
43
Hình 23: Ensembler learning với hỗ trợ mô hình chuyên gia
…………………………………….
44
BẢNG TỪ VIẾT TẮT
SOM ( Self-organizing map)
Bản đồ tự tổ chức
KNN (K nearest neibours)
K láng giềng gần nhất
AS (Ant System)
Phương pháp hệ kiến
ANN (Artificail Neural Network)
Mạng neural nhân tạo
BMU (Best matching unit)
Phần tử gần đúng nhất
MỤC LỤC
MỞ ĐẦU ………………………………………………………………………………………………………….
1
CHƯƠNG 1: BÀI TOÁN PHÂN LỚP VÀ MỘT SỐ PHƯƠNG PHÁP TIẾP CẬN
…
3
1.1 PHÁT BIỂU BÀI TOÁN PHÂN LỚP ……………………………………………………………
3
1.1.1 Mẫu (pattern/sample) …………………………………………………………………………….
3
1.1.2 Nhận dạng mẫu là gì? …………………………………………………………………………….
3
1.1.3 Các bài toán nhận dạng mẫu thường gặp …………………………………………………..
4
1.2 MẠNG NEURAL NHÂN TẠO
…………………………………………………………………….
4
1.2.1 Mạng Neural sinh học ……………………………………………………………………………
5
1.2.2 Mạng Neural nhân tạo ……………………………………………………………………………
6
1.3 PPHƯƠNG PHÁP K LÁNG GIỀNG GẦN NHẤT ………………………………………..
10
1.3.1 Thuật toán k láng giềng gần nhất là gì?……………………………………………………
10
1.3.2 Thuật toán KNN
………………………………………………………………………………….
11
CHƯƠNG 2: BẢN ĐỒ TỰ TỔ CHỨC
………………………………………………………………
15
2.1 Giới thiệu…………………………………………………………………………………………………
15
2.2 Thuật toán
………………………………………………………………………………………………..
16
2.3 Phân tích
………………………………………………………………………………………………….
22
CHƯƠNG 3: KANTS – HỆ KIẾN NHÂN TẠO CHO PHÂN LỚP ……………………..
24
3.1 Giới thiệu…………………………………………………………………………………………………
24
3.2 Các khái niệm mở đầu ……………………………………………………………………………….
25
3.2.1 Mô hình nhận thức bầy đàn và hệ kiến nhân tạo ……………………………………….
25
3.2.2 Nhắc lại SOM – bản đồ tự tổ chức
………………………………………………………….
27
3.2.3 Ant System
…………………………………………………………………………………………
27
3.3 Mô hình kiến tự tổ chức
……………………………………………………………………………..
29
CHƯƠNG 4: KẾT QUẢ VÀ THỰC NGHIỆM ………………………………………………….
34
4.1 Xây dựng chương trình kiểm thử …………………………………………………………………
34
4.2 Chuẩn bị dữ liệu kiểm tra
……………………………………………………………………………
35
4.3 Sự phụ thuộc chất lượng thuật toán vào các tham số ……………………………………….
36
4.3.1 β-δ – Độ ngẫu nhiên theo mùi………………………………………………………………..
37
4.3.2 Tham số k trong thuật toán k láng giềng gần nhất
……………………………………..
39
4.3.3 Kích thước lưới …………………………………………………………………………………..
39
4.3.4 Bán kính lân cận
………………………………………………………………………………….
40
4.3.5 Tham số q0
…………………………………………………………………………………………
40
4.3.6 Tham số bán kính trọng tâm cr ………………………………………………………………
40
4.3.7 Tham số bay hơi
………………………………………………………………………………….
41
4.3.8 Số lần lặp tối thiểu và cách xác định điều kiện dừng của thuật toán ……………..
41
4.4 Mở rộng của KANTS ………………………………………………………………………………..
41
4.4.1 Giới thiệu Ensembler learning ……………………………………………………………….
41
4.4.2 Áp dụng ensembler learning vào bài toán phân lớp với KANTS
………………….
44
CHƯƠNG 5: KẾT LUẬN ………………………………………………………………………………..
46
1
MỞ ĐẦU
Sự phát trển mạnh mẽ của công nghệ cao nói chung và khoa học máy tính nói riêng
ngày càng thu hút nhiều nhà khoa học và công nghệ quan tâm nghiên cứu bài toán nhận
dạng mẫu. Thoạt tiên, bài toán nhận dạng mẫu xuất phát từ nhu cầu tạo nên các thành
phần máy có khả năng quan sát môi trường. Cùng với sự phát triển của các ứng dụng
công nghệ thông tin, đặc biệt trong lĩnh vực học máy, người ta phải đi sâu phát triển các
hệ nhận dạng mẫu có khả năng tìm các mẫu mới trong các cơ sở dữ liệu lớn hay còn gọi
là khám phá tri thức từ dữ liệu.
Phân lớp mẫu là bài toán thường gặp nhất trong nhận dạng mẫu và phân thành hai
loại có giám sát và không có giám sát. Trong bài toán phân lớp có giám sát, dựa trên một
tập dữ liệu đã được gán nhãn, người ta xây dựng một bộ phân lớp để gán nhãn cho các dữ
liệu chưa biết. Còn trong bài toán không giám sát, người ta phân một tập dữ liệu chưa
được gán nhãn thành các các tập con sao cho các đối tượng dữ liệu trong mỗi tập con thì
có đặc tính giống nhau hơn so với đối tượng ở các tập con khác.
Trong các bài toán nhận dạng mẫu, bài toán phân lớp có giám sát là bài toán được
ứng dụng rộng rãi nhất. Việc xây dựng bộ phân lớp trong bài toán này được thực hiện bởi
các thuật toán học máy (học có giám sát). Với học có giám sát truyền thống, con người
thường phải bỏ ra rất nhiều công sức để gán nhãn cho tập dữ liệu đào tạo nếu muốn có
một bộ học tốt.
Phương pháp đơn giản và thông dụng hiện nay để giải bài toán phân lớp là k láng
giềng gần nhất. Gần đây, phương pháp KANTS mô phỏng hành vi loài kiến kết hợp với
bản đồ tự tổ chức (SOM) của Kohonen. Nội dung của khóa luận này là trình bày khái quát
về phương pháp phân lớp KANTS, trên cơ sở đó xây dựng chương trình thử nghiệm thuật
toán bằng C++ đánh giá hiệu quả với các k khác nhau. Ngoài ra, chúng tôi xây dựng bộ
phân lớp mới nhờ phương pháp học tập hợp của các bộ học với k khác nhau đã có. Kết
quả thực nghiệm cho thấy, chất lượng bộ học mới được cải tiến đáng kể so với từng bộ
học thành phần
Trong các phương pháp kinh điển để giải bài toán phân lớp có giám sát, mô hình
mạng neural nhân tạo và phương pháp k-láng giềng gần nhất đã chứng tỏ được tính hiệu
2
quả. Xong, hiệu suất và độ chính xác của các phương pháp/mô hình này chưa cao như kì
vọng. Khóa luận này xin được trình bày thuật toán KANTS: một sự kết hợp giữa bản đồ
tự tổ chức (một loại mạng neural nhân tạo) của Kohonen và phương pháp hệ kiến của
Chialvo và Milonas.
Bố cục của khóa luận gồm các phần sau:
Chương 1: Giới thiệu về bài toán phân lớp và hai phương pháp kinh điển để giải bài
toán này là: mạng neural nhân tạo và phương pháp k-láng giềng gần nhất
Chương 2: Giới thiệu về bản đồ tự tổ chức của Kohonen bao gồm kiến trúc và luật
học
Chương 3: Phương pháp hệ kiến và thuật toán KANTS
Chương 4: Kết quả thực nghiệm và sự mở rộng của KANTS.
Chương 5: Kết luận
3
CHƯƠNG 1:
BÀI TOÁN PHÂN LỚP VÀ MỘT SỐ PHƯƠNG PHÁP TIẾP CẬN
Chương này trình bày về khái niệm bài toán phân lớp trong học máy và hai phương pháp
kinh điển để giải bài toán này hiện nay: mạng neural và k-láng giềng gần nhất.
1.1.
PHÁT BIỂU BÀI TOÁN PHÂN LỚP
1.1.1. Mẫu (pattern/sample):
Có thể phân làm hai hoại: mẫu trừu tượng và mẫu cụ thể. Các ý tưởng, lập luận và
khái niệm… là những ví dụ về mẫu trừu tượng, nhận dạng các mẫu như vậy thuộc về lĩnh
vực nhận dạng khái niệm.
Các mẫu cụ thể bao gồm các đối tượng có tính không gian, thời gian và hình ảnh,
hoặc các đối tượng vật lý, chữ ký, chữ viết, ký hiệu, ảnh, đoạn sóng âm thanh, điện não
đồ hoặc điện tâm đồ, hàm số…là những ví dụ về mẫu cụ thể.
1.1.2. Nhận dạng mẫu là gì?
Không có một định nghĩa thống nhất nào về nhận dạng mẫu (Pattern recognition
viết tắt là PR) nhưng điều này cũng không gây ra tranh cãi gì trong giới nghiên cứu. Sau
đây là một số định nghĩa theo ngữ cảnh nghiên cứu:
– Duda et al: Nhận dạng mẫu là việc quy những đối tượng vật lí hay sự kiện vào một loại
(nhóm) nào đó đã xác định từ trước.
– Jürgen Schürmann: Nhận dạng mẫu là việc gán nhãn w cho một quan sát x.
– Selim Aksoy: Nhận dạng mẫu là việc nghiên cứu cách làm cho một máy có thể thực
hiện:
+ Quan sát môi trường.
+ Học cách phân biệt được các mẫu cần quan tâm.
+ Đưa ra các quyết định đúng đắn về loại (nhóm) của các mẫu.
4
Như vậy thay cho việc tìm định nghĩa chính xác cho khái niệm nhận dạng mẫu ta
sẽ liệt kê các bài toán chính trong lĩnh vực này.
1.1.3. Các bài toán nhận dạng mẫu thường gặp
Các bài toán nhận dạng mẫu thường gặp có thể quy về các dạng sau.
Phân lớp có giám sát hay phân loại (categorize): Dựa trên một tập con (tập đào
tạo) đã biết nhãn, đưa ra một cách gán nhãn cho các đối tượng mới để phân tập
các đối tượng thành các lớp. Ví dụ: nhận dạng chữ viết tay nhờ các chữ đã biết,
nhận dạng loài hoa nhờ các thông tin về độ dài, độ rộng, màu sắc.
Phân lớp không giám sát hay phân cụm (cluster): Chia tập đối tượng thành nhóm
sao cho các đối tượng trong mỗi nhóm tương đối giống nhau còn các đối tượng
khác nhóm thì khác nhau.
Phân tích hồi quy (regression) hay nhận dạng hàm: Xác định một biến (hàm) qua
tập các biến khác.
Nhận thực (Identify): Xác định đối tượng trong tập đã cho có là đối tượng đang
quan tâm hay không. Chẳng hạn như nhận thực vân tay, nhận thực mặt người…
Mô tả: Mô tả các đối tượng dưới hình thức dễ phân tích. Chẳng hạn mô tả điện
tâm đồ dưới dạng biểu đồ đặc trưng hoặc xâu mã.
Khóa luận này sẽ đề cập đến bài toán đầu tiên: Phân lớp có giám sát hay phân loại
(categorize). Để hiểu rõ hơn yêu cầu của bài, xem ví dụ ở phần 1.3 phương pháp k láng
giềng gần nhất.
1.2.
MẠNG NEURAL NHÂN TẠO
Bộ não con người chứa đựng những bí mật mà đến bây giờ khoa học vẫn chưa giải
đáp được, chính nhờ có bộ não hoàn chỉnh mà con người đã trở thành động vật bậc cao
thống trị muôn loài. Đã từ lâu con người đã nghiên cứu cấu trúc đặc biệt của bộ não từ đó
ứng dụng để giải quyết những bài toán khoa học kỹ thuật. Người ta đã phát hiện ra rằng
bộ não con người là mạng lưới chằng chịt các Neural liên kết với nhau, đây là cơ sở hình
thành nên cấu trúc của mạng Neural nhân tạo.
5
Về bản chất toán học thì mạng Neural nhân tạo như là một mặt trong không gian đa
chiều để xấp xỉ một hàm chưa biết nào đấy. Nhưng mạng Neural nhân tạo lại giống mạng
Neural sinh học ở chỗ đó là khá năng có thể huấn luyện(học), đây là đặc điểm quan trọng
nhất của mạng Neural nhân tạo. Chính vì đặc điểm này mà mạng Neural nhân tạo có khả
năng thực hiện tốt các công việc sau khi đã được huấn luyện, và đến khi môi trường thay
đổi ta lại có thể huấn luyện lại mạng Neural nhân tạo để nó thích nghi với điều kiện mới.
1.2.1. Mạng Neural sinh học
Mạng Neural sinh học là một mạng lưới (plexus) các Neuron có kết nối hoặc có liên
quan về mặt chức năng trực thuộc hệ thần kinh ngoại biên (peripheral nervous system)
hay hệ thần kinh trung ương (central nervous system).
Hình 1: Minh họa một Neuron thần kinh sinh học
Trên đây là hình ảnh của một tế bào thần kinh(Neural thần kinh), ta chú ý thấy rằng một
tế bào thần kinh có ba phần quan trọng:
-Phần đầu cũng có nhiều xúc tu (Dendrite) là nơi tiếp xúc với các với các điểm kết
nối(Axon Terminal) của các tế bào thần kinh khác
-Nhân của tế bào thần kinh (Nucleus) là nơi tiếp nhận các tín hiệu điện truyền từ xúc tu.
Sau khi tổng hợp và xử lý các tín hiệu nhận được nó truyền tín hiệu kết quả qua trục cảm
ứng (Axon) đến các điểm kết nối (Axon Terminal) ở đuôi.
6
-Phần đuôi có nhiều điểm kết nối (Axon Terminal) để kết nối với các tế bào thần kinh
khác.
Khi tín hiệu vào ở xúc tu kích hoạt nhân nhân Neuron có tín hiệu ra ở trục cảm ứng
thì Neuron được gọi là cháy. Mặc dù W. Mculloch và W.Pitts (1940) đề xuất mô hình
mạng neural nhân tạo khá sớm nhưng định đề Heb (1949) mới là nền tảng lý luận cho
mạng neural nhân tạo.
Định đề Heb: Khi một neuron(thần kinh) A ở gần neuron B, kích hoạt thường xuyên hoặc
lặp lại việc làm cháy nó thì phát triển một quá trình sinh hoá ở các neuron làm tăng tác
động này.
1.2.2. Mạng Neural nhân tạo
Mạng Neural nhân tạo được thiết kế để mô hình một số tính chất của mạng Neural
sinh học, tuy nhiên, khác với các mô hình nhận thức, phần lớn các ứng dụng lại có bản
chất kỹ thuật. Mạng Neural nhân tạo (ANN) là máy mô phỏng cách bộ não hoạt động
thực hiên các nhiệm vụ của nó. Một mạng Neural là bộ xử lý song song phân tán lớn nó
giống bộ não người về 2 mặt:
-Tri thức được nắm bắt bởi Neural thông qua quá trình học.
-Độ lớn của trọng số kết nối Neural đóng vai trò khớp nối cất giữ thông tin.
a) Cấu tạo một Neuron trong mạng Neural nhân tạo
Cấu tạo một Neural nhân tạo
Một neuron bao gồm các liên kết nhận tín hiệu vào bằng số có các trọng số kết nối
wi tương ứng với tín hiệu xi, hàm F gọi là hàm kích hoạt để tạo tín hiệu ra dựa trên giá trị
F
∑
x1
x2
xn
w1
w2
w3
w0
Y
7
hàm tổng có trọng số của các giá trị đầu vào, Y là giá trị đầu ra của Neural. Ta có thể biểu
diễn một Neural nhân tạo theo công thức toán học như sau:
0
1
w
n
i
i
i
Y
F
x w
Tùy vào thực tế bài toán hàm F là một hàm cụ thể nào đấy, trong quá trình huấn
luyện(học) thì các tham số wi được xác định. Trên thực thế F thường được chọn trong
những hàm sau:
1) Hàm ngưỡng
1;
0
( )
( )
1;
0
x
F x
x
x
Hình 2: Đồ thị hàm ngưỡng
2) Hàm tuyến tính
( )
F x
ax
Hình 3: Đồ thị hàm tuyến tính
3) Hàm sigmoid
1
( )
1
x
F x
e
Hình 4: Đồ thị hàm sigmoid
-1.5
-1
-0.5
0
0.5
1
1.5
-6
-4
-2
0
2
4
6
-4
-3
-2
-1
0
1
2
3
4
-6
-4
-2
0
2
4
6
0
0.5
1
-6
-4
-2
0
2
4
6
8
4) Hàm tanh
1
( )
1
x
x
e
F x
e
Hình 5: Đồ thị hàm tanh
5) Hàm bán kính
(Gauss)
2
( )
x
F x
e
Hình 6: Đồ thị hàm Gauss
Trên thực tế thì các họ hàm sigmoid thường dùng cho mạng Neural truyền thẳng nhiều
tầng MLP vì các hàm này dễ tính đạo hàm:
‘( )
( )(1
( ))
f
x
f x
f x
, trong khi đó mạng
Neural RBF lại dùng hàm kích hoạt là hàm bán kính.
b) Kiến trúc của mạng Neural nhân tạo
-1
-0.5
0
0.5
1
-6
-4
-2
0
2
4
6
0
0.5
1
-6
-4
-2
0
2
4
6
9
Kiến trúc của mạng Neural nhân tạo
lấy tư tưởng chính của mạng Neural sinh
học đó là sự kết nối của các Neural. Tuy
nhiên, mạng Neural nhân tạo có kiến trúc
đơn giản hơn nhiều, về cả số lượng
Neuron và cả kiến trúc mạng, trong khi ở
mạng Neural tự nhiên một Neuron có thể
kết nối với một Neuron khác bất kỳ ở
trong mạng thì ở mạng Neural nhân tạo
các Neuron được kết nối sao cho nó có
thể dễ dàng được biểu diễn bởi một mô
hình toán học nào đấy. Ví dụ trong mạng
Neural truyền tới các Neuron được phân
thành nhiều lớp, các Neuron ở lớp trước
chỉ được kết nối với các Neuron ở lớp
sau.
Hình 7: Kiến trúc mạng neural truyền tới
c) Quá trình học
Như đã nói ở trên mạng Neural nhân tạo có khả năng huấn luyện được(học), quá
trình huấn luyện là quá trình mà mạng Neural nhân tạo tự thay đổi mình dưới sự kích
thích của môi trường(bộ dữ liệu huấn luyện) để phù hợp với điều kiện của môi trường.
Quá trình huấn luyện chỉ có thể được thực hiện khi mạng Neural nhân tạo đã xây dựng
được kiến trúc cụ thể, và hàm kích hoạt F đã được xác định. Về bản chất quá trình học là
quá trình xác định các tham số wi của các Neuron trong mạng Neural. Có ba kiểu học
chính, mỗi kiểu mẫu tương ứng với một nhiệm vụ học trừu tượng. Đó là học có giám sát,
học không có giám sát và học tăng cường. Dưới đây xin nêu ra phương pháp học có giám
sát, các phương pháp khác xem thêm phần phụ lục.
Học có giám sát
Trong học có giám sát, ta được cho trước một tập ví dụ gồm các cặp
( ,
,
1.. ),
,
i
i
x y i
n x
X y
Y
và mục tiêu là tìm một hàm
:
f
X
Y
(trong lớp các hàm
INPUT
OUTPUT
HIDDEN
10
được phép) khớp với các ví dụ. Trên thực tế người ta thường tìm hàm f sao cho tổng bình
phương sai số đạt giá trị nhỏ nhất trên tập ví dụ:
2
1
(
)
n
i
i
i
E
f x
y
Chương 2 xin được trình bày về bản đồ tự tổ chức (còn gọi là bản đồ Kohonen) – một loại
mạng neural dùng để phân cụm.
1.3.
PHƯƠNG PHÁP K LÁNG GIỀNG GẦN NHẤT
1.3.1 Thuật toán k láng giềng gần nhất là gì?
Phương pháp k láng giềng gần nhất ( K nearest neibours – KNN) là một trong những
phương pháp phân loại đơn giản và cơ bản nhất, là lựa chọn đầu tiên mà ta nghĩ đến khi
cần học phân lớp mà không biết rõ về phân bố của dữ liệu.
K láng giềng gần nhất là một thuật toán học có giám sát với kết quả của một truy
vấn được phân loại chủ yếu dựa trên nhãn của các lân cận cạnh nó. Chức năng của thuật
toán này là để phân lớp một đối tượng dựa trên các thuộc tính và các mẫu huấn luyện. Bộ
phân loại không sử dụng một mô hình nào để phân loại mà chỉ dựa trên bộ nhớ. Cho một
đối tượng O cần cần lớp, trước hết tìm k số các đối tượng (hay các điểm huấn luyện) gần
nhất với đối tượng này. Sự “gần” ở đây được hiểu là gần về khoảng cách Ơclit của các
vector dữ liệu (vector thể hiện đặc trưng số đã được chuẩn hóa).
Sự phân lớp được thực hiện theo quy tắc sau: mỗi đối tượng trong k các đối tượng
được tìm thấy ở trên mang một nhãn lớp (vì là học có giám sát) và sẽ được “bỏ phiếu”. Lá
phiếu này chính là nhãn lớp của chúng. Đếm số “phiếu” được bỏ, ta sẽ tìm được nhãn
được bỏ phiếu nhiều nhất, nhãn lớp của O sau đó sẽ được gán nhãn này. Đây là cách gán
nhãn dựa trên xác suất và sự gần về mặt dữ liệu. Việc chọn đặc trưng số để biểu diễn đặc
điểm của dữ liệu dưới dạng vector dữ liệu có ảnh hưởng lớn đến chất lượng của thuật toán
phân lớp. Các đặc trưng được chọn phải tạo ra sự phân bố đủ tốt để giảm thiểu tối đa
nhiễu, việc chọn đặc trưng cũng phụ thuộc nhiều vào đặc điểm của từng bài toán.
Để hiểu rõ hơn KNN, ta hãy xét ví dụ sau:
Ví dụ:
11
Ta có các dữ liệu là những câu hỏi khảo sát ý kiến một số người và trắc nghiệm khách
quan với hai thuộc tính: độ bền axit và độ dẻo dai, để phân loại xem một loại giấy nào đó
là tốt hay không:
X1 = độ bền axit
(giây)
X1 = độ dẻo dai
(kq/m2
Phân lớp
7
7
Kém
7
4
Kém
3
4
Tốt
1
4
Tốt
Từ đây, khi các nhà máy sản xuất giấy, nếu họ thu được 1 mẫu giấy có X1 = 3 và X2
= 7, sẽ rất khó để xác định chất lượng giấy nếu phải tiến hành điều tra lấy ý kiến người
tiêu dùng. Nhưng KNN là một phương pháp đủ tốt để xác định chất lượng mà không cần
khảo sát tốn kém mà chỉ dựa vào một số kết quả khảo sát tin cậy đã tiến hành.
1.3.2 Thuật toán KNN
Ta có thể biểu diễn mỗi đối tượng huấn luyện và các đối tượng cần phần lớp bằng 1
vector n nhiều. Khi đó mỗi vector lại có thể đặt trọng không gian n chiều.
Thuật toán KNN rất đơn giản. Nó làm việc dựa trên khoảng cách nhỏ nhất từ điểm cần
phân lớp tới các dữ liệu huấn luyện để xác định k lân cận gần nhất. Sau khi tìm được k lân
cận này, ta thực hiện bỏ phiếu để tìm ra nhãn lớp được bỏ nhiều nhất làm kết quả.
Dữ liệu cho thuật toán KNN gồm nhiều thuộc tính đa chiều Xi để phân các đối tượng vào
các nhãn trong tập Y. Các dữ liệu của KNN là những vector thể hiện đặc trưng số của đối
tượng.
12
Hình 8: Mẫu dữ liệu ví dụ cho KNN
Dòng cuối cùng là đối tượng với X1 = 6 và X2 = 5 là đối tượng mà ta cần biết nó thuộc
phân lớp + hay lớp –
Ta coi 2 thuộc tính X1 và X2 của các mẫu như là những tọa độ trên không gian 2 chiều,
khi đó có thể trực quan các mẫu như sau:
13
Hình 9: Trực quan hóa các mẫu trên mặt phẳng
Giả sử ta ta chọn tham số trong thuật toán này là K = 8 (tức là 8 lân cận gần nhất).
Sau đó ta tính toán khoảng cách giữa điểm cần tính q và tất cả các mẫu huấn luyện. Ta sẽ
sử dụng khoảng cách Ơ clit để tính khoảng cách giữa các mẫu với các đại lượng Xi. Giả
sử điểm cần phân lớp q có tọa độ (x1q, x2q) và tọa độ của các mẫu huấn luyện là (x1t, x2t).
Bình phương khoảng cách Ơ clit giữa d2 tp = (x1t – x1p)2 + (x2t – x2p)2 vậy dtp = sqrt((x1t –
x1p)2 + (x2t – x2p)2). Trường hợp có nhiều hơn 2 thuộc tính cách tính cũng tương tự như
công thức Ơ clit cho vector n chiều:
Bước tiếp theo là tìm k lân cận gần nhất, với mỗi mẫu đào tạo t cho một khoảng
cách là dt, ta chọn k mẫu có khoảng cách dt nhỏ nhất. Nói cách khác, ta sắp xếp các
khoảng cách của q với tất cả các mẫu đào tạo, sắp xếp theo thứ tự tăng dần vào chọn k
điểm cho k khoảng cách nhỏ nhất đầu tiên.
14
Hình 10: Bỏ phiếu các mẫu dữ liệu trong KNN
Trong bảng trên, nhãn + được bỏ phiếu 3 lần còn nhãn – được bỏ phiếu 5 lần, ta lấy nhãn
được bỏ nhiều hơn, do đó q được gán nhãn là –.
Ưu điểm:
+) Phân lớp tốt với các dữ liệu đào tạo có nhiễu (đặc biệt nếu sử dụng nghịch đảo bình
phương của khoảng cách trọng số.
+) Hiệu quả với dữ liệu đào tạo lớn.
Nhược điểm:
+) Cần phải xác định giá trị của tham số K (số láng giềng gần nhất)
+) Học dựa khoảng cách không nói rõ nó sử dụng loại khoảng cách nào và với những
thuộc tính nào thì cho kết quả tốt nhất. Và sử dụng tất cả các thuộc tính hay chỉ một số
thuộc tính mà thôi.
+) Chi phí tính toán là khá cao vì chúng ta cần phải tính khoảng các của từng mẫu đến tất
cả các mẫu huấn luyện.
15
CHƯƠNG 2: BẢN ĐỒ TỰ TỔ CHỨC
Chương này trình bày về bản đồ tự tổ chức (Self-organizing map – SOM). Bản đồ tự tổ
chức là cơ sở để thực hiện KANTS.
2.1.
Giới thiệu:
Một bản đồ tự tổ chức (self-organizing map – hay self-organizing feature map
(SOFM) là một loại mạng neural nhân tạo được huấn luyện sử dụng học không giám sát
để sinh ra một không gian có số chiều nhỏ hơn (thông thường là hai chiều), biểu diễn rời
rạc của không gian đầu và của các dữ liệu huấn luyện, được gọi là một bản đồ. Bản dồ tự
tổ chức khác với những mạng neural nhân tạo khác theo nghĩa là chúng sử dụng một hàm
lân cận để bảo toàn tính quan hệ hình học của không gian đầu vào.
SOM rất có lợi trong việc trực quan hóa cách nhìn của cách dữ liệu nhiều chiều,
giống như việc chia các dữ liệu nhiều chiều thành các mức (hoặc các cụm). Mô hình này
lần đầu tiên được miêu tả như một mạng neural nhân tạo bởi một giáo sư người Phần Lan
là Teuvo Kohonen, và đôi khi còn được gọi là bản đồ Kohonen[19].
Giống như hầu hết các mạng neural nhân tạo, các SOM hoạt động ở hai chế độ huấn
luyện (training) và ánh xạ (mapping) hay thực hiện phân lớp. Quá trình huấn luyện sẽ xây
dựng bản đồ sử dụng các mẫu dữ liệu đầu vào. Đó là một quá trình cạnh tranh, cũng được
gọi là lượng tử vector. Việc ánh xạ tự động phân lớp một vector đầu vào mới.
Một bản đồ tự tổ chức chứa các thành phần gọi là các đỉnh (node) hay neural. Kết
hợp với mỗi đỉnh là một vector trọng số có số chiều bằng số chiều với các vector dữ liệu
vào và một vị trí trong không gian bản đồ. Thông thường, các đỉnh được sắp xếp dạng
lưới tứ giác hoặc lục giác. Bản đồ tự tổ chức sẽ mô phỏng một ánh xạ từ một không gian
dữ liệu đầu vào với số chiều lớn thành một không gian có số chiều nhỏ hơn (thông thường
để cho trực quan, người ta thường để 2 chiều để dữ liệu phân bố trên một mặt phẳng).
Thủ tục đặt mỗi vector từ không gian dữ liệu đầu vào vào bản đồ là việc tìm ra đỉnh
với vector trọng số gần nhất với vector được lấy từ không gian dữ liệu và gán các tọa độ
trong bản đồ của đỉnh này bằng vector của đầu vào của ta.
Thông thường cấu trúc của loại mạng này giống với các mạng truyền thẳng – ta sẽ
thấy rằng trong một mạng SOM, chỉ có một tầng vào mà một tầng ra.
16
Những mở rộng quan trọng bao gồm việc sử dụng các lưới có hình xuyến (lục giác
hoặc tứ giác), trong loại lưới này các cung đối diện được kết nối sử dụng số các đỉnh lớn
hơn. Điều này chỉ ra rằng, với các bản đồ tự tổ chức với số các đỉnh nhỏ làm việc theo
cách giống như K-means, các bản đồ tự tổ chức lớn hơn sắp xếp lại dữ liệu theo các đặc
tính hình học của dữ liệu vào.
Thông thường, trong SOM người ta sử dụng ma trận U. Các giá trị của ma trận U là
khoảng cách giữa một đỉnh và các lân cận gần nó nhất. Ví dụ, trong các lưới tứ giác, ta sẽ
chọn được 4 hoặc 8 đỉnh gần nhất tùy theo cách định nghĩa hoặc trong các lưới lục giác là
6 đỉnh.
Những bản đồ tự tổ chức lớn hơn thể hiện các thuộc tính rất rõ nét. Trong những bản
đồ chứa tới hàng nghìn đỉnh, ta có thể thực hiện các phép phân cụm trên chính bản đồ.
2.2.
Thuật toán:
Mục đích của việc học trong bản đồ tự tổ chức là dẫn đến việc tạo ra sự phân chia
thành các phần khác nhau của các neural trong mạng để thỏa mãn giống như các mẫu vào.
Đây là một phần thúc đẩy bởi cách trực quan, thính giác hay các giác quan thông tin khác
được điều khiển bởi các phần khác nhau, tách biệt nhau của vỏ não người.
Các trọng số của các vector được khởi tạo là những giá trị ngẫu nhiên nhỏ hay các
mẫu tương tự nhau từ không gian con…
Mạng sau đó phải được huấn luyện bởi một số lớn các vector mẫu vào, gần nhau
nhất có thể … Những mẫu này thường được thực hiện nhiều lần tương tự mỗi lần lặp.
Việc huấn luyện sử dụng học cạnh tranh. Khi một mẫu huấn luyện được đưa vào
mạng, nó tính khoảng cách Ơclit (Euclidean distance) cho tất cả các vector trọng số.
Neural với vector trọng số giống với vector trọng số của mẫu vào nhất được gọi là best
matching unit (BMU). Các trọng số của BMU và các neural gần với nó trong lưới SOM
được kéo gần về phía vector đầu vào. Biên độ của thay đổi sẽ giảm theo thời gian và theo
khoảng cách với BMU. Công thức cập nhật cho một neural với vector trọng số Wv(t) là:
Wv(t + 1) = Wv(t) + Θ (v, t) α(t)(D(t) – Wv(t))
17
Với α(t) là một hệ số học giảm đơn điệu và D(t) là vector đầu vào. Hàm lân cận Θ
(v, t) phụ thuộc và khoảng cách giữa BMU và neural v. Ở dạng đơn giản nhất nó là một
cho tất cả các neural đủ gần với BMU và 0 với các neural khác, nhưng thông thường ta
hay chọn một hàm gaussian. Bất kể với dạng của hàm này, hàm lân cận giảm theo thời
gian. Tại thời điểm đầu khi lân cận là rộng, bản đồ tự tổ chức sẽ cập nhật tổng thể toàn
mạng, tức là coi như toàn bộ mạng thuộc vào lân cận, sau đó bán kính lân cận giảm dần.
Khi lân cận co lại chỉ còn một đôi neural, các trọng số được hội tụ về ước lượng địa
phương.
Quá trình này được lặp đi lặp lại cho mỗi vector đầu vào với một số (thường là lớn)
cho kì λ. Mạng kết thúc việc kết hợp các đỉnh ra với các nhóm hoặc mẫu trong tập dữ liệu
vào. Nếu những mẫu này được gán nhãn, các nhãn có thể được gắn để kết hợp với các
đỉnh trong mạng lưới đã được huấn luyện này.
Trong quá trình ánh xạ, sẽ có một neural duy nhất gọi là neural thắng: neural có
vector trọng số nằm gần nhất với vector đầu vào. Để xác định được vector này chỉ cần
đơn giản tính khoảng cách Ơclit của vector đầu vào và các vector trọng số của các neural,
neural nào cho khoảng cách Ơclit nhỏ nhất là neural thắng.
Việc biểu diễn dữ liệu đầu vào thành các vector được được nhấn mạnh trong khóa
luận này, ta cũng chú ý rằng mọi đối tượng đều có thể biểu diễn số hóa rời rạc và có một
khoảng cách thích hợp để xác định được kết hợp khi cần thực hiện huấn luyện có thể
được sử dụng để tạo bản đồ tự tổ chức. bao gồm: các ma trận, các hàm liên tục hoặc thậm
chí các bản đồ tự tổ chức khác.
