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 CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
LÃNH LAN HƢƠNG

MẠNG KOHONEN VÀ ỨNG DỤNG TRONG
QUẢN LÝ TRỢ CẤP XÃ HỘI CỦA SINH VIÊN
TRƢỜNG CAO ĐẲNG SƢ PHẠM CAO BẰNG

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH


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
HƢỚNG DẪN KHOA HỌC: P G S . TS LÊ BÁ DŨNG
THÁI NGUYÊN - 2014

Số hóa bởi Trung tâm Học liệu http://www.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, tháng 7 năm 2014
Số hóa bởi Trung tâm Học liệu http://www.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 v
DANH MỤC CÁC BẢNG vi
DANH MỤC CÁC HÌNH vii
MỞ ĐẦU 1
CHƯƠNG 1: TỔNG QUAN VỀ MẠNG KOHONEN VÀ BÀI TOÁN
PHÂN CỤM 2
1.1. Giới thiệu chung về mạng Nơron 2
1.1.1 Lịch sử phát triển của mạng nơron 2
1.1.2. Mạng Nơron sinh học 3
1.1.3. Mạng Nơron nhân tạo 5
1.1.4 Ứng dụng 14
1.2. Mạng Kohonen và bài toán phân cụm 15
1.2.1 Giới thiệu về mạng nơron Kohonen 15
1.2.2 Bài toán phân cụm 16
1.3 Các phƣơng pháp phân cụm 18
CHƢƠNG 2: SOM VÀ KĨ THUẬT PHÂN CỤM DỮ LIỆU DỰA VÀO SOM 20
2.1. Thuật toán phân cụm dữ liệu 20
2.2. Một số thuật toán cơ bản trong phân cụm dữ liệu 21
2.2.1 Thuật toán phân cụm phân cấp 21
2.2.2 Thuật toán phân cụm phân hoạch (Thuật toán K-means) 22
2.2.3 Thuật toán phân cụm dựa trên mật độ (Thuật toán DBSCAN) 25

3.3. Thử nghiệm sử dụng mô hình mạng Kohonen để khảo sát, đánh
giá, thống kê tình hình trợ cấp xã hội của học sinh, sinh viên
trƣờng Cao đẳng Sƣ phạm Cao Bằng 51
3.3.1. Các chức năng của chƣơng trình 51
3.3.2. Giao diện chƣơng trình 51
3.3.3. Kết quả và phân tích kết quả sau khi huấn luyện mô hình mạng
Kohonen. Trực quan mạng U-Matrix 53
KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN 73
TÀI LIỆU THAM KHẢO 74

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

v
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 Clustering of Applications with
Noise): Phân cụm dữ liệu dựa trên không gian mật độ ứng với nhiễu

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

vii
DANH MỤC CÁC HÌNH
Hình 1.1. Cấu tạo mô hình nơron sinh học 4
Hình 1.2. Cấu trúc mô hình một nơron nhân tạo cơ bản 5
Hình 1.3. Đồ thị các dạng hàm chuyển 8
Hình 1.4. Mô hình mạng nơron 3 lớp 9
Hình 1.5. Cấu trúc huấn luyện mạng nơron 10
Hình 1.6. Học có giám sát 11
Hình 1.7. Học không có giám sát 11
Hình 1.8. Sơ đồ cấu trúc chung của quá trình học 13
Hình 2.1. Các thiết lập để xác định ranh giới các cụm ban đầu 22
Hình 2.2. Tính toán trọng tâm của các cụm mới 23
Hình 2.3. Hình dạng các cụm đƣợc khám phá bởi thuật toán DBSCAN 25
Hình 2.4. Cấu trúc mạng Kohonen 29
Hình 2.5. Phần tử nơron chiến thắng BMU 30
Hình 2.6. Các vùng lân cận 31
Hình 2.9: Hàm tỉ lệ học theo thời gian 36
Hình 3.1. Kết quả phân cụm theo các lớp trong trƣờng sử dụng phƣơng
pháp trực quan U-Matrix 54
Hình 3.2. Kết quả phân cụm các lớp sử dụng phƣơng pháp trực quan các
bản đồ thành phần 59
Hình 3.3 Kết quả phân cụm các nhóm sinh viên trong một lớp sử dụng
phƣơng pháp trực quan U-Matrix 66
Hình 3.4. Kết quả phân cụm sinh viên sử dụng phƣơng pháp trực quan
các bản đồ thành phần 69

Thái Nguyên, tháng 7 năm 2014
Ngƣời viết luận văn

Lãnh Lan Hƣơng

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

2
CHƢƠNG 1
TỔNG QUAN VỀ MẠNG KOHONEN VÀ BÀI TOÁN PHÂN CỤM

1.1. Giới thiệu chung về mạng Nơron
1.1.1 Lịch sử phát triển của mạng nơron
Khái niệm mạng nơron đƣợc bắt đầu vào cuối thế kỷ 19, đầu thế kỷ 20 do
có sự tham gia của ba ngành Vật lý học, Tâm lý học và Thần kinh học. Các
nhà khoa học nhƣ Hermann Von Hemholtz, Earnst Mach, Ivan Pavlov với
các công trình nghiên cứu đi sâu vào lý thuyết tổng quát mô tả hoạt động
của trí tuệ con ngƣời nhƣ: Học, nhìn, và lập luận, nhƣng không đƣa ra đƣợc mô
hình toán học cụ thể mô tả hoạt động của nơron.
Về lịch sử, quá trình nghiên cứu và phát triển mạng nơron nhân tạo có thể
chia thành bốn giai đoạn nhƣ sau:
- Giai đoạn một: Từ nghiên cứu của William (1890) về tâm lý học với
sự liên kết các nơron thần kinh. Năm 1943, nhà thần kinh học Warren
MeCulloch và nhà logic học Walter Pitts đã chỉ ra rằng: về nguyên tắc
mạng các nơron nhân tạo có thể đƣợc mô hình hoá nhƣ thiết bị ngƣỡng
(giới hạn) để thực hiện tính toán bất kỳ một hàm số học hay các phép tính
logic nào. Tiếp theo hai ông là Donald Hebb với giải thuật huấn luyện
mạng ra đời năm 1949.
- Giai đoạn hai: Vào khoảng những năm 1960, một số mô hình nơron
hoàn thiện hơn có tính ứng dụng thực tiễn đã đƣợc đƣa ra nhƣ: mô hình

1.1.2. Mạng Nơron sinh học
1.1.2.1. Cấu trúc một nơron sinh học
Theo các nghiên cứu sinh học về bộ não, hệ thống thần kinh của con
ngƣời bao gồm khoảng 100 tỷ tế bào thần kinh, thƣờng đƣợc gọi là nơron.
Mỗi tế bào thần kinh nơron bao gồm 03 thành phần:
- Thân nơron (gọi là Soma) với nhân bên trong là nơi tiếp nhận hay phát
ra các xung động thần kinh.
- Một hệ thống mạng các dây thần kinh vào (gọi là Dendrites) truyền tín
hiệu (dƣới dạng xung điện) tới nhân nơron để xử lý. Các dây thần kinh vào

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

4
tạo thành một lƣới dày đặc xung quanh thân nơron, chiếm diện tích khoảng
0,25mm
2
, bên trong thân các dữ liệu đó đƣợc tổng hợp lại.
- Đầu dây thần kinh (gọi là sợi trục Axon) phân nhánh dạng hình cây, có
thể dài từ 1cm đến hàng mét. Chúng nối với các dây thần kinh vào hoặc trực
tiếp với nhân tế bào của các nơron khác thông qua các khớp nối (gọi là
Synapse). Thông thƣờng mỗi nơron có thể có từ vài chục cho tới hàng trăm
ngàn khớp nối để nối với các nơron khác. Có hai loại khớp nối, khớp nối kích
thích (excitatory) sẽ cho tín hiệu qua nó để tới nơron còn khớp nối ức chế
(inhibitory) có tác dụng làm cản tín hiệu tới nơron. Ngƣời ta ƣớc tính mỗi
nơron trong bộ não của con ngƣời có khoảng 10
4
khớp nối (hình 1.1).

1.1.3. Mạng Nơron nhân tạo
1.1.3.1. Cấu trúc và mô hình của một nơron nhân tạo
Năm 1943, Warren MuCulloch và Walter Pitts đã đề xuất mô hình nơron
nhân tạo đầu tiên thƣờng đƣợc gọi là nơron M-P, 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 nhân tạo cơ bản có n đầu vào x
1
, x
2
, , x
n
, và một đầu ra
y
i
nhƣ sau:
Hình 1.2. Cấu trúc mô hình một nơron nhân tạo cơ bản
.
.
.
W
i1

Hàm tổng
i
W
i2

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

6
Một nơron thực hiện nhiệm vụ: nhận tín hiệu từ các đơn 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. Trong đó:
- Tập các đầu vào, đƣợc ký hiệu là x
i
, 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 n chiều.
- Tập các liên kết (các trọng số) tƣơng ứng với các đầu vào, những trọng
số này tƣơng ứng với các Synapse trong nơron sinh học. 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à w
ij
. 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. Nếu w > 0 thì nơron đang
ở trạng thái kích thích, ngƣợc lại w < 0 thì nơron đang ở trạng thái kiềm chế.
- Độ lệch hay ngƣỡng, đƣợc ký hiệu là b, là tham số điều chỉnh vô hƣớng
của nơron. Thƣờng đƣợc đƣa vào nhƣ là một thành phần của hàm chuyển.
Ta thấy w và b đều là các tham số điều chỉnh vô hƣớng của nơron. Ý
tƣởng cơ bản của mạng nơron là điều chỉnh các tham số này để mạng đạt
đƣợc mục đích mong muốn.
- Hàm tổng, đƣợc ký hiệu là , thƣờng dùng để tính tổng của tích các đầu

*x
1
+ w
12
*x
2
+…+w
1n
*x+b (1.1)
Hay m = w*x+b (1.2)
Vậy véctơ đầu ra có giá trị: y
i
= f(w*x+b) (1.3)
Hàm chuyển hay còn gọi là hàm phi tuyến, chuyển đổi một tổ hợp tuyến
tính của tất cả các tín hiệu đầu vào thành tín hiệu đầu ra. Hàm chuyển này
đảm bảo tính chất phi tuyến cho tính toán mạng nơron. Nó đƣợc xem nhƣ là
một hàm giới hạn, nó giới hạn phạm vi biên độ cho phép của tín hiệu đầu ra
trong một khoảng giá trị hữu hạn.
Một số dạng hàm chuyển thƣờng đƣợc sử dụng:
Hàm bƣớc nhảy
00
01
)(
xkhi
xkhi
xf
(1.4)
Hàm giới hạn chặt (hay còn gọi là hàm bƣớc)
01
01

xf
với λ>0 (1.8)
* Đồ thị các dạng hàm chuyển đƣợc biểu diễn nhƣ sau: Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

8

Hình 1.3. Đồ thị các dạng hàm chuyển
1.1.3.2. Mô hình mạng Nơron nhân tạo
Mạng nơron gồm một số lƣợng lớn các đơn vị xử lý kết nối với nhau
hoạt động song song và cấu hình nên kiểu kiến trúc của hệ thống [1]. Do mô
phỏng cách thức hoạt động của nơron thần kinh, nên mạng nơron có khả năng
học, tái tạo, tổng quát hóa từ dữ liệu đã đƣợc huấn luyện.
Đơn vị tạo nên mạng nơron là các nút. Các nút này sẽ nằm ở các lớp
(Layer) khác nhau. Mỗi lớp có một nhiệm vụ riêng:
- Lớp vào (Input layer): nhận dữ liệu đầu vào, các nút thuộc lớp vào gọi
là nút vào.
- Lớp ra (Output layer): kết xuất dữ liệu, các nút thuộc lớp ra gọi là
nút ra.
- Lớp ẩn (Hidden layer): lớp này có thể có hoặc không, tùy loại mạng. Số
lƣợng lớp ẩn của một nơron cũng tùy theo ngƣời thiết kế mạng. Các nút thuộc
lớp ẩn gọi là nút ẩn. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

9



10
1.1.3.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. Cấu trúc huấn luyện mạng
đƣợc chỉ ra ở hình dƣới. Ở đây, hàm trọng số của mạng đƣợc điều chỉnh trên
cơ sở so sánh đầu ra với đích mong muốn (taget), cho tới khi đầu ra của mạng
phù hợp với đích. Những cặp vào/đích (input/taget) đƣợc dùng để giám sát
cho sự huấn luyện mạng. Hình 1.5. Cấu trúc huấn luyện mạng nơron
Để có đƣợc một số cặp vào/ra, ở đó mỗi giá trị vào đƣợc gửi đến mạng
và giá trị ra tƣơng ứng đƣợc thực hiện bằng mạng là sự xem xét và so sánh
với giá trị mong muốn. Bình thƣờng, nó sẽ tồn tại một sai số vì giá trị mong
muốn không hoàn toàn phù hợp với giá trị thực. Sau mỗi lần chạy, ta có tổng
bình phƣơng của tất cả các sai số. Sai số này đƣợc sử dụng để xác định các
hàm trọng số mới.
Sau mỗi lần chạy, hàm trọng số của mạng đƣợc sửa đổi với đặc tính tốt
hơn tƣơng ứng với đặc tính mong muốn. Từng cặp giá trị vào/ra phải đƣợc
kiểm tra và trọng số đƣợc điều chỉnh một vài lần. Sự thay đổi các hàm trọng
số của mạng sẽ đƣợc dừng lại, nếu tổng các bình phƣơng sai số nhỏ hơn một
giá trị đặt trƣớc, hoặc đã chạy đủ một số lần chạy xác định (trong trƣờng hợp
này, mạng có thể không thoả mãn yêu cầu đặt ra do sai lệch còn cao). Có hai
kiểu học:
- Học tham số: là các tham số về trọng số cập nhật kết nối giữa các nơron.
- Học cấu trúc: trọng tâm là sự biến đổi cấu trúc của các mạng nơron

cũng đƣợc cung cấp tới mạng. Hiệu giữa đầu ra thực y
(k)

và đầu ra mong muốn d
(k)
đƣợc đo trong máy phát tín hiệu lỗi. Máy này sẽ tạo
ra tín hiệu lỗi cho mạng để hiệu chỉnh các trọng số của mạng và với các hiệu
chỉnh này thì đầu ra thực sẽ tiến sát với đầu ra mong muốn. Hình 1.6. Học có giám sát Học không có giám sát

Hình 1.7. Học không có giám sát

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

12
Trong phần học không có giám sát, sẽ không có thầy hƣớng dẫn, tức là
không có tín hiệu d cung cấp tới mạch phản hồi. Điều này cho thấy, ta sẽ
không biết đầu ra đạt giá trị gì. Với loại này, thì các nơron tự xoay xở với các
dữ liệu mẫu mà nó có đƣợc, chứ không có “thầy” gợi ý cần luyện theo hƣớng

)( txr
(1.9)
là một số dƣơng và đƣợc gọi là hằng số học dùng để xác định tốc độ học, r
là tín hiệu học và phụ thuộc:
).,,(
iir
dxwfr
(1.10)

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

13

Hình 1.8. Sơ đồ cấu trúc chung của quá trình học
Từ hình (1.8) ta thấy, vector trọng số w
i
= [w
i1
, w
i2
, , w
im
]
T

điều khiển đối tƣợng có nhiều biến số.

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

14
1.1.4 Ứng dụng
Từ khi ra đời và phát triển, mạng nơron đã đƣợc ứng dụng trong nhiều
lĩnh vƣc khác nhau. Không thể liệt kê đƣợc hết ứng dụng của mạng nơron, tuy
nhiên ta có thể thấy một số ứng dụng điển hình nhƣ sau:
- Tài chính - ngân hàng: định giá bất động sản, cho vay, kiểm tra tài sản
cầm cố giá mức độ hợp tác, phân tích đƣờng tín dụng, chƣơng trình thƣơng
mại thông qua giấy tờ, cấp phát thẻ tín dụng, phân tích tài chính liên doanh,
dự báo tỉ giá tiền tệ,…
- Quân sự: định vị phát hiện vũ khí, dò tìm mục tiêu, nhận dạng ngƣời
nói, phân luồng rada.
- Y học: xử lý, chuẩn đoán hình ảnh trong y học, phân tích tín hiệu điện
tâm đồ,…
- Bảo hiểm: Đánh giá việc áp dụng các chính sách xã hội, tối ƣu hóa sản phẩm.
- Giao thông: các hệ thống dẫn đƣờng tự động trong ô tô, các bộ phận
hoạt động của xe,…
- Hàng không: phi công tự động, giả lập đƣờng bay, các hệ thống điều
khiển lái máy bay, bộ phận phát hiện lỗi,
- Giải trí: tạo các hiệu ứng đặc biệt, hoạt hình,
- Thiết bị điện tử: dự báo mã tuần tự, sơ đồ chip IC, điều khiển tiến trình,
phân tích nguyên nhân hỏng chip,
- Nhận dạng mẫu: phân loại tín hiệu của rada, nhận dạng và hiểu tiếng
nói, nhận dạng vân tay, kí tự, chữ viết,
- Xử lý tín hiệu: phân tích tín hiệu địa chấn và hình thái học.
- Xứ lý ảnh, nhìn máy: gồm trùng khớp ảnh, tiền xử lý ảnh, phân đoạn và
phân tích ảnh, nén ảnh,…

luật và các tƣơng quan, các giá trị nhập vào và dự đoán các kết quả tiếp theo.
Các nơron của mạng thông qua quá trình luyện cạnh tranh để nhận ra một
nhóm các đối tƣợng đầu vào tƣơng đƣơng nhau. Mục đích chính của việc
luyện trong mạng nơron Kohonen là nhận dạng một nhóm các vector đầu vào
cùng loại.

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

16
SOM là một công cụ thích hợp trong khai phá dữ liệu. Nó đƣợc ứng
dụng nhiều trong các bài toán nhƣ nhận dạng tiếng nói (Kohonen, 1989), máy
ảo (Oja, 1992), tối ƣu tổ hợp (Fort, 1988), phân lớp ảnh (Kohonen,
1984) Mạng Kohonen đƣợc thiết kế chủ yếu để giảm số chiều dữ liệu và trực
quan thông tin. Tuy nhiên có thể kết hợp Kohonen với các kỹ thuật xác định
cụm khác để phân cụm dữ liệu.
1.2.2 Bài toán phân cụm
1.2.2.1 Khái niệm
Phân cụm là quá trình nhóm một tập các đối tƣợng tƣơng tự nhau trong
tập dữ liệu vào các cụm sao cho các đối tƣợng thuộc cùng một cụm là tƣơng
đồng còn các đối tƣợng thuộc các cụm khác nhau sẽ không tƣơng đồng.
Phân cụm là một kỹ thuật trong khai phá dữ liệu nhằm tìm kiếm, phát
hiện các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn quan trọng trong tập dữ liệu
lớn từ đó cung cấp thông tin hữu ích cho việc ra quyết định.
Quá trình phân cụm là quá trình tìm ra các đối tƣợng trong cơ sở dữ liệu
một cách tự động. Phân cụm là một ví dụ của phƣơng pháp học không có
thầy. Không giống nhƣ phân lớp, phân cụm không đòi hỏi phải định nghĩa
trƣớc các mẫu dữ liệu huấn luyện. Vì thế, có thể coi phân cụm là một cách
học bằng quan sát.
Đã có rất nhiều thuật toán đƣợc phát triển cho bài toán phân cụm trong
cơ sở dữ liệu lớn và đƣợc áp dụng vào nhiều lĩnh vực nhƣ xử lý ảnh, nhận