..
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
MAI XUÂN ĐẠT
NGHIÊN CỨU MẠNG NƠRON VÀ ỨNG DỤNG
TRONG KHẢO SÁT, ĐÁNH GIÁ, THỐNG KÊ KẾT QUẢ
HỌC TẬP TẠI TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP
QUẢNG NINH
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
Thái Nguyên - 2013
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
MAI XUÂN ĐẠT
NGHIÊN CỨU MẠNG NƠRON VÀ ỨNG DỤNG
TRONG KHẢO SÁT, ĐÁNH GIÁ, THỐNG KÊ KẾT QUẢ
HỌC TẬP TẠI TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP
QUẢNG NINH
Chuyên ngành: KHOA HỌC MÁY TÍNH
Mã số: 60 48 01
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Ngƣời hƣớng dẫn khoa học: PGS.TS NGÔ QUỐC TẠO
Thái Nguyên – 2013
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
i
LỜI CAM ĐOAN
Tôi xin cam đoan luận văn là công trình nghiên cứu của riêng cá nhân tôi,
không sao chép của ai do tôi tự nghiên cứu, đọc, dịch tài liệu, tổng hợp và thực hiện.
Nội dung lý thuyết trong trong luận văn tôi có sử dụng một số tài liệu tham khảo nhƣ
đã trình bày trong phần tài liệu tham khảo. Các số liệu, chƣơng trình phần mềm và
những kết quả trong luận văn là trung thực và chƣa đƣợc công bố trong bất kỳ một
công trình nào khác.
Thái Nguyên, ngày 09 tháng 10 năm 2013
Học viên thực hiện
Mai Xuân Đạt
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
ii
LỜI CẢM ƠN
Lời đầu tiên, em xin gửi lời biết ơn sâu sắc đến PGS.TS Ngô Quốc Tạo ngƣời
đã tận tình hƣớng dẫn, chỉ bảo, giúp đỡ em trong suốt quá trình làm luận văn.
Em cũng xin gửi lời cảm ơn đến các thầy cô giáo trƣờng Đại học Công nghệ
thông tin và Truyền thông - Đại học Thái Nguyên, các thầy cô Viện Công nghệ thông
tin đã truyền đạt những kiến thức và giúp đỡ em trong suốt quá trình học của mình.
Tôi cũng xin gửi lời cảm ơn tới các đồng nghiệp, gia đình và bạn bè những
ngƣời đã ủng hộ, động viên tạo mọi điều kiện giúp đỡ để tôi có thể hoàn thành tốt
luận văn.
Tôi cũng xin gửi lời cảm ơn tới Ban giám hiệu Trƣờng Đại học Công nghiệp
Quảng Ninh đã tạo kiện thuận lợi cho tôi tham gia khóa học và trong suốt quá trình
hoàn thành luận văn.
Một lần nữa, xin chân thành cảm ơn.
Thái Nguyên, ngày 09 tháng 10 năm 2013
Học viên
Mai Xuân Đạt
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
iii
MỤC LỤC
LỜI CAM ĐOAN ............................................................................................................. i
LỜI CẢM ƠN ................................................................................................................. ii
MỤC LỤC ..................................................................................................................... iii
DANH MỤC CÁC KÍ HIỆU, CHỮ CÁI VIẾT TẮT ........................................................ vi
DANH MỤC CÁC BẢNG ............................................................................................. vii
DANH MỤC CÁC HÌNH ............................................................................................. viii
MỞ ĐẦU ...................................................................................................................... 1
Chƣơng 1: GIỚI THIỆU VỀ MẠNG NƠRON ........................................................ 3
1.1. Giới thiệu về mạng nơron nhân tạo .................................................................... 3
1.1.1. Cấu trúc và mô hình mạng nơron ................................................................ 3
1.1.2. Cấu tạo và phƣơng thức làm việc của mạng nơron ..................................... 6
1.1.3. Các luật học ................................................................................................. 8
1.2. Kết luận chƣơng 1 ............................................................................................ 11
Chƣơng 2: MẠNG SOM VÀ MỘT SỐ PHƢƠNG PHÁP PHÂN CỤM ............. 13
2.1. Thuật toán phân cụm dữ liệu ............................................................................ 13
2.2. Một số thuật toán cơ bản trong phân cụm dữ liệu ............................................ 14
2.2.1. Thuật toán phân cụm phân cấp .................................................................. 14
2.2.2. Thuật toán phân cụm phân hoạch (Thuật toán K-means) .......................... 15
2.2.3. Thuật toán phân cụm dựa trên mật độ (Thuật toán DBSCAN) ................. 17
2.2.4. Thuật toán phân cụm dựa trên lƣới (Thuật toán STING) .......................... 19
2.2.5. Các thuật toán phân cụm dựa trên mô hình (Thuật toán EM) ................... 20
2.3. Thuật toán phân cụm bằng mạng Kohonen ...................................................... 21
2.3.1. Mạng Kohonen là gì?................................................................................. 21
2.3.2. Cấu trúc mô hình mạng Kohonen .............................................................. 21
2.3.3. Thuật toán phân cụm bằng mạng Kohonen ............................................... 22
2.4. Một số vấn đề phân cụm bằng mạng Kohonen ................................................ 25
2.4.1. Khởi tạo mạng Kohonen (SOM) ............................................................... 25
2.4.2. Huấn luyện mạng Kohonen ....................................................................... 25
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
iv
2.4.3. Tỉ lệ học ..................................................................................................... 26
2.4.4. Cập nhật lại trọng số .................................................................................. 27
2.4.5. Xác định nơron chiến thắng ....................................................................... 28
2.5. Kohonen (SOM) sử dụng trong phân cụm dữ liệu ........................................... 29
2.5.1. SOM phân cụm với bản đồ một chiều ....................................................... 29
2.5.2. SOM phân cụm với bản đồ hai chiều ....................................................... 29
2.5.3. Xác định ranh giới các cụm ....................................................................... 30
2.5.4. Trực quan mạng ........................................................................................ 31
2.5.5. Số lƣợng nhóm khi phân cụm .................................................................... 32
2.6. Kết luận chƣơng 2 ............................................................................................ 33
Chƣơng 3: ỨNG DỤNG MÔ HÌNH SOM TRONG BÀI TOÁN KHẢO SÁT,
ĐÁNH GIÁ, THỐNG KÊ KẾT QUẢ HỌC TẬP CỦA SINH VIÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHIỆP QUẢNG NINH ....................................... 34
3.1. Phát biểu bài toán ............................................................................................. 34
3.2. Khảo sát, đánh giá, thống kê quá trình học tập của sinh viên trƣờng đại học
Công nghiệp Quảng Ninh................................................................................. 34
3.2.1. Thu thập dữ liệu ......................................................................................... 34
3.3. Thực nghiệm sử dụng mô hình SOM để khảo sát, đánh giá, thống kê kết
quả học tập của sinh viên trƣờng đại học Công nghiệp Quảng Ninh ............ 43
3.3.1. Các chức năng của chƣơng trình ............................................................... 43
3.3.2. Phân tích dữ liệu ........................................................................................ 43
3.3.3. Giao diện chƣơng trình .............................................................................. 51
3.3.4. Kết quả và phân tích kết quả sau khi huấn luyện mô hình mạng kohonen. ......... 53
3.4. Kết luận chƣơng 3 ........................................................................................... 63
KẾT LUẬN ................................................................................................................ 64
TÀI LIỆU THAM KHẢO ........................................................................................ 64
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
v
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
vi
DANH MỤC CÁC KÍ HIỆU, CHỮ CÁI VIẾT TẮT
HSSV:
Học sinh, sinh viên
CSDL:
Cơ sở dữ liệu
KPDL:
Khai phá dữ liệu
PCDL :
Phân cụm dữ liệu
SOM(Self Organizing Maps):
Mạng nơron tự tổ chức
PE (Processing element):
Phần tử xử lý
BMU(Best - Matching unit):
Đơn vị phù hợp nhất
U-matrix (unified distance matrix):
Ma trận thống nhất khoảng cách
EM (Expectation maximization):
Thuật toán tối đa hóa
STING (STatistical INformation Grid ): Thuật toán thống kê thông tin lƣới
DBSCAN (Density Based Spatial) :
Phân cụm dữ liệu dựa trên không
Clustering (of Applications with Noise): Gian mật độ ứng với nhiễu
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
vii
DANH MỤC CÁC BẢNG
Bảng 3.1 Bảng xếp loại điểm ..................................................................................... 40
Bảng 3.2. Dữ liệu thống kê phân cụm, môn học ......................................................... 45
Bảng 3.3. Dữ liệu thống kê phân cụm, môn học ......................................................... 46
Bảng 3.4 Dữ liệu thống kê phân cụm của sinh viên theo điểm thi ............................. 48
Bảng 3.5 Dữ liệu thống kê phân cụm của sinh viên theo điểm thi ............................. 49
Bảng 3.6. Kết quả các cụm môn sau khi huấn luyện mạng Kohonen......................... 54
Bảng 3.7. Kết quả các cụm Sinh viên sau khi huấn luyện mạng Kohonen ................ 62
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
viii
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
ix
DANH MỤC CÁC HÌNH
Hình 1.1: Một nơron sinh học ....................................................................................... 3
Hình 1.2: Sự liên kết các nơron..................................................................................... 4
Hình 1.3: Mô hình một nơron nhân tạo......................................................................... 5
Hình 1.4: Đồ thị các dạng hàm truyền .......................................................................... 6
Hình 1.5: Mạng nơron ba lớp ........................................................................................ 7
Hình 1.6: Một số dạng mạng nơron .............................................................................. 8
Hình 1.7: Cấu trúc huấn luyện mạng nơron .................................................................. 9
Hình 1.8: Học có giám sát ............................................................................................ 9
Hình 1.9: Học không có giám sát ................................................................................ 10
Hình 1.10: Sơ đồ cấu trúc chung của quá trình học .................................................... 11
Hình 2.1. Các thiết lập để xác định ranh giới các cụm ban đầu .................................. 15
Hình 2.2. Tính toán trọng tâm của các cụm mới ......................................................... 16
Hình 2.4. Một dạng mạng nơron Kohonen ................................................................. 22
Hình 2.5. Phần tử nơron chiến thắng BMU ................................................................ 22
Hình 2.6. Các vùng lân cận ......................................................................................... 23
Hình 2.7: Hàm tỉ lệ học theo thời gian ........................................................................ 27
Hình 3.1 Kết quả chạy chƣơng trình huấn luyện SOM............................................... 52
Hình 3.2. Kết quả phân cụm môn học, mô đun sử dụng phƣơng pháp trực quan
U-Matrix .................................................................................................... 53
Hình 3.3 Kết quả phân cụm điểm sử dung phƣơng pháp trực quan các biểu đồ
thành phần .................................................................................................. 57
Hình 3.4 Kết quả phân cụm sinh viên theo môn học, mô đun sử dụng phƣơng
pháp trực quan U-Matrix ........................................................................... 61
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
1
MỞ ĐẦU
Trong cuộc sống hàng ngày con ngƣời chúng ta tiếp nhận rất nhiều thông tin.
Với khối lƣợng thông tin khổng lồ đòi hỏi con ngƣời phải phân tích chúng và phân
chia chúng thành các dạng thông tin khác nhau. Cùng với sự phát triển của công
nghệ thông tin các phƣơng pháp, thuật toán phân cụm dữ liệu ra đời giúp cho con
ngƣời có khả năng phân chia các loại thông tin khác nhau để phục vụ cho công việc
và trong cuộc sống hàng ngày.
Mạng nơron SOM đƣợc giáo sƣ Teuvo Kohonen của trƣờng đại học Helsinki
Phần Lan phát triển vào những năm 80 của thế kỷ 20[7]. Đây là mạng truyền thẳng
sử dụng thuật học cạnh tranh, không giám sát có khả năng phân cụm dữ liệu với
một lƣợng lớn dữ liệu đầu vào.
Thông tin giáo dục đào tạo của các trƣờng hiện nay hầu hết đƣợc lƣu trữ trong
máy tính và chúng ta cần phải tìm ra những thông tin hữu ích từ cơ sở dữ liệu đó để
có các biện pháp phù hợp, cần thiết cho việc cải cách, nâng cao chất lƣợng giáo dục
đào tạo thông qua việc khảo, đánh giá, thống kê, báo cáo.
Chính vì lý do đó tôi chọn đề tài: "Nghiên cứu mạng Nơron và Ứng dụng
trong Khảo sát, đánh giá, thống kê kết quả học tập tại Trường Đại học Công
nghiệp Quảng Ninh". Luận văn tập trung vào tìm hiểu mạng SOM và sử dụng
SOM trong phân cụm dữ liệu.
Phƣơng pháp nghiên cứu chính là tìm hiểu các tài liệu bài báo viết về mạng
SOM và huấn luyện mạng SOM phân cụm điểm các môn học và phân cụm sinh
viên của Trƣờng Đại học Công nghiệp Quảng Ninh từ đó đƣa ra những nhận xét,
đánh giá, tƣ vấn cho phòng đào tạo và học sinh đăng kí học theo từng môn, từng kỳ
học phù hợp với mình .
Nội dung luận văn gồm có 3 chƣơng:
Chƣơng I: Giới thiệu về mạng nơron sinh học bao gồm cấu trúc của mạng
nơron sinh học và nguyên lý hoạt động của nơron sinh học. Về nơron nhân tạo giới
thiệu cấu trúc của một nơron nhân tạo, mô hình của mạng nơron nhân tạo.
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
2
Chƣơng II: Giới thiệu về một số phƣơng pháp phân cụm và một số thuật
toán phân cụm phổ biến, ƣu nhƣợc điểm của từng thuật toán phân cụm. Trong
chƣơng này trình bày về mạng SOM: giới thiệu về mạng SOM, cấu trúc của SOM,
các phƣơng pháp khởi tạo, huấn luyện SOM, tỉ lệ học, các hàm lân cận, phƣơng
pháp xác định nơron chiến thắng và sử dụng SOM trong phân cụm dữ liệu.
Chƣơng III: Trình bày về sử dụng công cụm SOM phân cụm điểm từng môn
học và từng sinh viên để đƣa ra những nhận xét, đánh giá về các môn học từ cơ sở
dữ liệu đó để có các biện pháp phù hợp, nâng cao chất lƣợng giáo dục đào tạo.
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
3
Chƣơng 1
GIỚI THIỆU VỀ MẠNG NƠRON
1.1. Giới thiệu về mạng nơron nhân tạo
1.1.1. Cấu trúc và mô hình mạng nơron
1.1.1.1. Mô hình một nơron sinh học
Phần tử xử lý cơ bản của một mạng nơron sinh học là một nơron, phần tử
này có thể chia làm bốn thành phần cơ bản nhƣ sau:
- Dendrites: Là phần nhận tín hiệu đầu vào.
- Soma: Là hạt nhân.
- Axon: Là phần dẫn ra tín hiệu xử lý.
- Synapses: Là đƣờng tín hiệu điện hóa giao tiếp giữa các nơron.
Một cách tổng quát, một nơron sinh học nhận đầu vào từ các nguồn khác
nhau, kết hợp chúng tại với nhau, thực thi tổ hợp phi tuyến chúng để cho ra kết quả
cuối cùng ở đầu ra. Hình 1.1 chỉ ra mối quan hệ giữa bốn thành phần của một nơron
sinh học.
Hình 1.1: Một nơron sinh học
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
4
Một nơron sinh học chỉ có một số chức năng cơ bản nhƣ vậy nên khả năng
xử lý thông tin của nó là rất yếu. Để có đƣợc khả năng xử lý thông tin hoàn hảo nhƣ
bộ não con ngƣời thì các nơron phải kết hợp và trao đổi thông tin với nhau.
Sơ đồ liên kết và trao đổi thông tin giữa hai nơron nhƣ hình sau:
Hình 1.2: Sự liên kết các nơron
1.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 nhân tạo đƣợc đề xuất bởi McCulloch và
Pitts 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:
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
5
Hình 1.3: Mô hình một 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.
- 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 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 truyền 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].
- Đầ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à net i
wij x j
j 1
Trong đó: x1, x2, …xm là các tín hiệu đầu vào; 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
y
Số hóa bởi Trung tâm Học liệu
1 khi x 0
0 khi x 0
(1.1)
http://lrc.tnu.edu.vn
6
- Hàm giới hạn chặt
y
sgn( x)
- Hàm bậc thang
y
sgn( x)
1 khi x 0
1 khi x 0
(1.2)
1 khi
x 1
x khi 0 x 1
(1.3)
0 khi
x 0
- Hàm ngƣỡng đơn cực
1
- Hàm ngƣỡng hai cực 1 e
y
với λ > 0
(1.4)
x
2
với λ > 0
1
1 e x
Đồ thị các dạng hàm truyền đƣợc biểu diễn nhƣ sau:
y
(1.5)
Hình 1.4: Đồ thị các dạng hàm truyền
1.1.2. Cấu tạo và phương thức làm việc của mạng nơron
Mạng nơron 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 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.
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
7
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 1.5 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. Các tín hiệu đầu vào đƣợc đƣa đến 3 nơron
đầu vào x1, x2, x3; 3 nơron này làm thành lớp đầu vào của mạng. Đầu ra của các
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. Đầ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 y1, y2.
Hình 1.5: Mạng nơron ba lớp
Mạng nơron có cấu trúc nhƣ trên 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.
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. Khi đã hình thành tri thức, mạng
có thể giải quyết các vấn đề một cách đúng đắn.
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 của mạng nơron.
Số hóa bởi Trung tâm Học liệu
http://lrc.tnu.edu.vn
8
(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
(d) Mạng nơron hồi quy
Hình 1.6: Một số dạng mạng nơron
Hình 1.6 là một số liên kết đặc thù của mạng nơron. Nơron đƣợc vẽ là các
vòng tròn xem nhƣ một tế bào thần kinh, chúng có các mối liên hệ đến các nơron
khác nhờ các trọng số liên kết, tập hợp các trọng số liên kết này sẽ lập thành các ma
trận trọng số tƣơng ứng.
1.1.3. Các luật học
Thông thƣờng, mạng nơron đƣợc điều chỉnh hoặc đƣợc huấn luyện để hƣớng
các đầu vào riêng biệt đến đích ở đầu ra.
Dữ
liệu
vào
ANN
Số hóa bởi Trung tâm Học liệu
Đích
Trọng số wi
So sánh
Điều chỉnh
http://lrc.tnu.edu.vn
- Xem thêm -