Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CNTT&TT
Điêu Thiện Chiến
MỘT SỐ KỸ THUẬT MÔ HÌNH HÓA VÀ ÁP DỤNG
CHO BÀI TOÁN DỰ BÁO KẾT QUẢ TUYỂN SINH ĐẠI HỌC
.
LUẬN VĂN THẠC SĨ: KHOA HỌC MÁY TÍNH
Người hướng dẫn: GS. TS Nguyễn Thanh Thủy
Thái Nguyên, tháng 01 năm 2014
2.1.3.2 Hàm xử lý 15
2.2 Học và lan truyền trong mạng 19
2.2.1 Học và tổng quát hóa 19
2.2.1.1 Học có giám sát 20
2.2.1.2 Học tăng cường 22
2.2.1.3 Học không giám sát 22
2.2.2 Lan truyền trong mạng: 24
Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
2.3 Hàm mục tiêu 24
2.4 Mạng nơ ron truyền thẳng 25
2.5 Khả năng thể hiện của mạng 27
2.6 Thiết kế cấu trúc mạng 28
2.6.1 Số lớp ẩn 28
2.6.2 Số nơron trong lớp ẩn 29
2.7 Thuật toán lan truyền ngược (Back-Propagation) 30
2.7.1 Mô tả thuật toán 31
2.7.2 Sử dụng thuật toán lan truyền ngược 32
2.7.2.1 Lựa chọn cấu trúc mạng 32
2.7.2.2 Quá trình hội tụ 33
2.7.2.3 Tổng quát hóa 33
2.7.3 Biến thể của thuật toán lan truyền ngược 34
2.7.3.1 Sử dụng tham số bước đà 34
2.7.3.2 Sử dụng hệ số học biến đổi 35
2.7.3.3 Sử dụng phương pháp Gradient kết hợp 36
2.7.4 Nhận xét: 40
Chương 3: Ứng dụng mạng Nơ ron truyền thẳng và thuật toán lan truyền
ngược vào bài toán “Dự báo kết quả tuyển sinh Đại học” 42
3.1 Tổng quan về bài toán dự báo 42
Group: nhóm
MLP: mạng nơron truyền thẳng nhiều lớp
Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
DANH MỤC CÁC BẢNG
3.1 Dữ liệu thu thập được 43
3.2 Dữ liệu đầu vò và đầu ra của mạng 48 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
DANH MỤC CÁC HÌNH 2.1 Cấu tạo của tế bào nơron sinh học 8
2.2 Mô hình nơron nhân tạo 8
2.3 Đơn vị xử lý 10
2.4 Hàm đồng nhất 12
2.5 Hàm bước nhị phân 12
2.6 Hàm sigmoid 13
2.7 Hàm sigmoid lưỡng cực 13
2.8 Sơ đồ học tham số có giám sát 17
2.9 Sơ đồ học tăng cường 17
2.10 Sơ đồ học không giám sát 18
2.11 Sơ đồ mạng nơron truyền thẳng nhiều lớp 20
2.12 Xác định tần số 33
NỘI DUNG
Chương 1: Các phương pháp mô hình hóa dữ liệu.
1.1 Phương pháp trực quan.[1]
1.1.1 Quan sát các hoạt động không theo chủ quan
Kỹ thuật khai phá dữ liệu trực quan cung cấp cho người khai phá khả
năng đầy đủ để quan sát các hoạt động mà không theo định kiến cá nhân nào
cả. Điều đó có nghĩa là ta không cần phải biết là cần phải tìm kiếm cái gì
trong thời gian sáp tới. Hơn thế, bạn có thể bắt dữ liệu chỉ ra cho bạn thấy cái
gì là quan trọng.
1.1.2 Trực quan và đòi hỏi của nhận thức
Có thể sự mở rộng lớn nhất trong việc sử dụng trực quan trong các
phương pháp khai phá dữ liệu là phương pháp trực quan cốt để làm nổi bật
khả năng nhận thức, kinh nghiệm của con người có thể làm tốt và một số công
việc khác lại làm rất tốt. Việc lựa chọn phương pháp nghiên cứu thường phải
có sự cân nhắc về kiểu xử lý thông tin mà người đó đòi hỏi trong suất quá
trình nghiên cứu.
1.1.3 Vẽ sơ đồ dữ liệu trên lược đồ trực quan
Khi đưa dữ liệu vào trong một môi trường trực quan, bạn phải quyết
định làm sao để trình bày dữ liệu theo một kiểu cách có ý nghĩa. Hoạt động
này tập trung vào sử dụng những thuộc tính của các phần tử dữ liệu đã được
định nghĩa trong mô hình để xác định làm sao thông tin sẽ được nhìn thấy và
cảm nhận. bạn có thể chọn những giải thuật xác định vị trí như gộp nhóm,
phân cụm, …
1.2 Phương pháp truyền thống
1.2.1 Phương pháp thống kê
Trong phương pháp này, ta sử dụng những thông tin được thống kê để
suy luận và miêu tả xa hơn trong phân tích dữ liệu.
Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
thành, được ước lượng và biến đổi như thế nào. Giải thuật cũng mô phỏng lại
yếu tố gen trong nhiễm sắc thể sinh học trên máy tính để có thể giải quyết
nhiều bài toán thực tế khác nhau.
Giải thuật di truyền dựa trên ba cơ chế cơ bản: Chọn lọc, tương giao chéo và
đột biến.[1]
1.3 Phương pháp khác
1.3.1 Phân nhóm và phân đoạn
Phương pháp phân nhóm và phân đoạn là những kỹ thuật phân chia dữ liệu
sao cho mỗi phần hoặc một nhóm giống nhau theo một tiêu chuẩn nào đó.
1.3.2 Phương pháp suy diễn và quy nạp
Một cơ sở dữ liệu là một kho thông tin những các thông tin quan trọng hơn
cũng có thể được suy diễn từ kho thông tin đó. Có hai kỹ thuật chính để thực
hiện việc này là suy diễn và quy nạp.
Phương pháp suy diễn: Nhằm rút ra những thông tin là kết quả logic của các
thông tin trong cơ sở dữ liệu, dựa trên các quan hệ trong dữ liệu.
Phương pháp quy nạp: Nhằm suy ra các thông tin được sinh ra từ cơ sở dữ
liệu.
1.3.3 Các phương pháp dựa trên mẫu
Sử dụng các mẫu miêu tả ừ cơ sơ dữ liệu để tạo nên mọt mô hình dự
đoán các mẫu mới dằng cách rút ra các thuộc tính tương tự như các mẫu đã
biết trong mo hình. Ở đây, nhiệm vụ chính là phải xác định được độ đo giống
nhau giữa các mẫu, sau đó mới rạo ra mẫu dự đoán.[1]
Chương 2: Mạng Nơron truyền thẳng và thuật toán lan truyền ngược
2.1 Tổng quan về mạng Nơron
2.1.1 Lịch sử phát triển
Khái niệm mạng nơ-ron được đề xuất nhằm mô tả hoạt động của nơron
trong bộ não con người. Ý tưởng này bắt đầu được nêu ra trong mô hình tính
toán mạng Perceptron. (Perceptron là một bộ phân loại tuyến tính dành cho
Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
• Tuy nhiên cả Rosenblatt và Widrow-Hoff đều cùng vấp phải một vấn
đề do Marvin Minsky và Seymour Papert phát hiện ra, đó là các mạng nhận
thức chỉ có khả năng giải quyết các bài toán khả phân tuyến tính. Họ cố gắng
cải tiến luật học và mạng để có thể vượt qua được hạn chế này nhưng họ đã
không thành công trong việc cải tiến luật học để có thể huấn luyện được các
mạng có cấu trúc phức tạp hơn.
• Do những kết quả của Minsky-Papert nên việc nghiên cứu vềmạng
nơron gần như bị đình lại trong suốt một thập kỷ do nguyên nhân là không có
được các máy tính đủ mạnh để có thể thực nghiệm.
• Mặc dù vậy, cũng có một vài phát kiến quan trọng vào những năm
70. Năm 1972, Teuvo Kohonen và James Anderson độc lập nhau phát triển
một loại mạng mới có thể hoạt động như một bộ nhớ. Stephen Grossberg
cũng rất tích cực trong việc khảo sát các mạng tự tổ chức (Self organizing
networks).
• Vào những năm 80, việc nghiên cứu mạng nơron phát triển rất mạnh
mẽ cùng với sự ra đời của PC. Có hai khái niệm mới liên quan đến sự hồi sinh
này, đó là:
1. Việc sử dụng các phương pháp thống kê để giải thích hoạt động của
một lớp các mạng hồi quy (recurrent networks) có thể được dùng như bộ nhớ
liên hợp (associative memory) trong công trình của nhà vật lý học Johh
Hopfield.
2. Sự ra đời của thuật toán lan truyền ngược (back-propagation) để
luyện các mạng nhiều lớp được một vài nhà nghiên cứu độc lập tìm ra như:
David Rumelhart, James McCelland, Đó cũng là câu trả lời cho Minsky-
Papert. [5]
Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
Hình 2.1 Cấu tạo của tế bào nơron sinh học
Với mục tiêu tạo ra một mô hình tính toán phỏng theo các làm việc của
nơron trong bộ não con người, vào năm 1943, các tác giả McCulloch và Pitts
đã đề xuất một mô hình toán cho một nơron như sau:
Hình 2.2 Mô hình nơron nhân tạo
Trong mô hình này, một nơron thứ i sẽ nhận các tín hiệu vào x
j
với các
trọng số tương ứng w
ij
, tổng các thông tin vào có trọng số là
m
j
jij
xw
1
Thông tin đầu ra ở thời điểm t+1 được tính từ các thông tin đầu vào như sau:
Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
itxwgtout
j
j
i
)()1(
(1.1)
vị phía trước hay một nguồn bên ngoài và sử dụng chúng để tính tín hiệu ra sẽ
được lan truyền sang các đơn vị khác.
Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ j
n
i
jijj
xwa
1
)(
jj
agz
Hình 2.3: Đơn vị xử lý (Processing unit)
x
i
: các đầu vào
w
ji
: các trọng số tương ứng với các đầu vào
j
: độ lệch (bias)
thực hiện nhiệm vụ này gọi là hàm kết hợp (combination function), được định
x
0
x
1
⁞
x
n
w
j0
w
j1
w
jn
∑
g(a
j
)
a
j
z
j
Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
nghĩa bởi một luật lan truyền cụ thể. Trong phần lớn các mạng nơron, chúng
ta giả sử rằng mỗi một đơn vị cung cấp một bộ cộng như là đầu vào cho đơn
vị mà nó có liên kết. Tổng đầu vào đơn vị j đơn giản chỉ là tổng trọng số của
các đầu ra riêng lẻ từ các đơn vị kết nối cộng thêm ngưỡng hay độ lệch (bias)
Phần lớn các nơron trong mạng nơron chuyển mạng đầu vào (net input) bằng
cách sử dụng một hàm vô hướng (scalar-to-scalar function) gọi là hàm kích
hoạt, kết quả của hàm này là một giá trị gọi là mức độ kích hoạt của đơn vị
(unit's activation). Loại trừ khả năng đơn vị đó thuộc lớp ra, giá trị kích hoạt
được đưa vào một hay nhiều đơn vị khác. Các hàm kích hoạt thường bị ép vào
một khoảng giá trị xác định, do đó thường được gọi là các hàm bẹp
(squashing). Các hàm kích hoạt hay được sử dụng là:
1) Hàm đồng nhất (Linear function, Identity function ) g( x) = x
Nếu coi các đầu vào là một đơn vị thì chúng sẽ sử dụng hàm này. Đôi khi một
hằng số được nhân với net-input để tạo ra một hàm đồng nhất.
Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
Hình 2.4: Hàm đồng nhất (Indentity function)
2) Hàm bước nhị phân (Binary step function, Hard limit function)
Hàm này cũng được biết đến với tên "Hàm ngưỡng" (Threshold function hay
Heaviside function). Đầu ra của hàm này được giới hạn vào một trong hai giá
trị:
1 nÕu x
()
0 nÕu x <
gx
0
-2
2
x
1
Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ Hình 2.6: Hàm Sigmoid
4) Hàm sigmoid lưỡng cực (Bipolar sigmoid function (tansig)
x
x
e
e
xg
1
1
)(
Hàm này có các thuộc tính tương tự hàm sigmoid. Nó làm việc tốt đối
với các ứng dụng có đầu ra yêu cầu trong khoảng [-1,1].
Hình 2.7: Hàm sigmoid lưỡng cực
Các hàm truyền của các đơn vị ẩn (hidden units) là cần thiết để biểu
x
1
g(x)
Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
hàm đồng nhất (identity function). Nếu giá trị mong muốn là dương nhưng
không biết cận trên thì nên sử dụng một hàm kích hoạt dạng mũ(exponential
output activation function). [4], [8]
2.2 Học và lan truyền trong mạng
2.2.1 Học và tổng quát hóa
Mạng nơron thực hiện hai chức năng quan trọng là học và tổng quát
hóa. Học là quá trình hiệu chỉnh các tham số và các trọng số liên kết trong
mạng để tối thiểu hóa sai số với vectơ đầu vào cho trước. Quá trình học dừng
khi mạng thỏa mãn một tiêu chuẩn dừng nào đó, chẳng hạn khi các trọng số
của mạng tạo ra lỗi đủ nhỏ giữa đầu ra mong đợi và kết quả đầu ra tính được
từ mạng.
Tổng quát hóa là quá trình đưa vào một vector đầu vào mới và sản sinh
ra quyết định dựa trên vector đầu ra tính được từ mạng.
Bài toán học có thể được mô tả như sau: Cho tập mẫu (X
i
, Y
i
) với X
i
và Y
i
là
hai vector không gian của một hoặc nhiều chiều, cần xác định bộ trọng số W
0
p
ii
i
E y O
p
với 1 ≤ p ≤ ∞
Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
Với bộ tham số này, có thể áp dụng một giải thuật tìm kiếm nào đó trên
không gian R
m
của tập trọng số. Nếu thu được kết quả tốt với một cực tiểu
toàn cục, ta sẽ có một bộ tham số tốt nhất cho mạng.
Học có cấu trúc:
Với học tham số ta giả định rằng mạng có một cấu trúc cố định. Việc
học cấu trúc của mạng truyền thẳng gắn với yêu cầu tìm ra số lớp của mạng L
và số nơron trên mỗi lớp ni. Tuy nhiên, với các mạng hồi quy còn phải xác
định thêm các tham số ngưỡng của các nơron trong mạng. Một cách tổng
quát là phải xác định bộ tham số P =(L, n1, n2, …, nl,
1 2 3
, ,
k
).
Các kỹ thuật học của mạng nơron chỉ ra cách chỉnh sửa các trọng số liên kết
mạng khi một mẫu học được đưa vào mạng. Sau đây sẽ trình bầy cụ thể về
các kỹ thuật học. [4]
Chức năng của một mạng nơron được quyết định bởi các nhân tố như:
hình trạng mạng (số lớp, số đơn vị trên mỗi lớp, và cách mà các lớp được liên
kết với nhau) và các trọng số của các liên kết bên trong mạng. Hình trạng của
♦ B2: Đưa một vector x trong tập mẫu huấn luyện X vào mạng
♦ B3: Tính vector đầu ra o của mạng
♦ B4: So sánh vector đầu ra mong muốn y (là kết quả được cho trong
tập huấn luyện) với vector đầu ra o do mạng tạo ra; nếu có thể thì đánh giá lỗi.
♦ B5: Hiệu chỉnh các trọng số liên kết theo một cách nào đó sao cho ở
lần tiếp theo khi đưa vector x vào mạng, vector đầu ra o sẽ giống với y hơn.
♦ B6: Nếu cần, lặp lại các bước từ 2 đến 5 cho tới khi mạng đạt tới
trạng thái hội tụ. Việc đánh giá lỗi có thể thực hiện theo nhiều cách, cách
dùng nhiều nhất là sử dụng lỗi tức thời: Err = (o - y), hoặc Err = |o - y|; lỗi
trung bình bình phương (MSE: mean-square error): Err = (o- y)
2
/2;
Có hai loại lỗi trong đánh giá một mạng nơron. Thứ nhất, gọi là lỗi rõ
ràng (apparent error), đánh giá khả năng xấp xỉ các mẫu huấn luyện của một
mạng đã được huấn luyện. Thứ hai, gọi là lỗi kiểm tra (test error), đánh giá
khả năng tổng quá hóa của một mạng đã được huấn luyện, tức khả năng phản
ứng với các vector đầu vào mới. Để đánh giá lỗi kiểm tra chúng ta phải biết
đầu ra mong muốn cho các mẫu kiểm tra.
Thuật toán tổng quát ở trên cho học có giám sát trong các mạng nơron có
nhiều cài đặt khác nhau, sự khác nhau chủ yếu là cách các trọng số liên kết
được thay đổi trong suốt thời gian học. Trong đó tiêu biểu nhất là thuật toán
lan truyền ngược. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ Hình 2.8: Sơ đồ học tham số có giám sát
2.2.1.2 Học tăng cường
Ta thấy trong kỹ thuật học có giám sát, các vecter đầu ra được biết một
Hình 2.10 Sơ đồ học không giám sát
Như vậy, giải thuật học là giải thuật xuất phát từ một tập mẫu, qua quá
trình huấn luyện để tìm ra bộ trọng số liên kết giữa các nơron, có thể mô tả
tổng quát như sau:
Đầu vào: Một tập mẫu gồm n phần tử mẫu
Đầu ra: Cấu trúc mạng và bộ trọng số các liên kết nơron.
Giải thuật:
1. Khởi tạo trọng số của mạng, đặt i = 1;
2. Đưa mẫu i vào lớp vào của mạng;
3. Sử dụng thuật toán lan truyền, nhận được giá trị nút ra.
Nếu giá trị đầu ra của mạng đạt yêu cầu hoặc thỏa mãn
tiêu chuẩn dừng thì kết thúc.
4. Sửa đổi trọng số bằng luật học của mạng;
5. Nếu i = n thì i =1, nếu không thì tăng i lên 1: i:=i+1
Quay lại bước 2.
Có nhiều tiêu chuẩn dừng quá trình học, chảng hạn:
- Chuẩn lỗi E nhỏ hơn một ngưỡng cho trước: E <
- Các trọng số của mạng không thay đổi nhiều sau khi hiệu chỉnh:
Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
ij ij
ww
new old
- Việc lặp bị bão hòa, tức là số lần lặp vượt một ngưỡng N cho trước.
2.2.2 Lan truyền trong mạng:
Mạng nơron lan truyền thông tin từ lớp vào đến lớp ra. Khi việc lan
E t y
NP
Copyright: Tài liệu đại học ©