HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
KHOA ĐÀO TẠO QUỐC TẾ & SAU ĐẠI HỌC
oo0oo
TIỂU LUẬN:
Khai phá dữ liệu thời gian sử dụng thuật toán di truyền và mạng nơron –
nghiên cứu dựa trên các dự báo tình hình ô nhiễm không khí
Môn học: Công cụ toán học nâng cao
Giáo viên: Nguyễn Văn Thỏa
Học viên: Nhóm 3

Hà nội, ngày 30/12/2011
Tiểu Luận: Công Cụ Toán Học Nâng Cao
CN2011_TDLMMT_NHOM3
1
Nhóm 3: danh sách các học viên
Nguyễn Thị Lan Anh
Đỗ Thị Liên
Mai Anh Chung
Nguyễn Văn Thắng
Nguyễn Văn Thanh
Nguyễn Thanh Thức
Tiểu Luận: Công Cụ Toán Học Nâng Cao
CN2011_TDLMMT_NHOM3
2
Mục lục
PHẦN 1: DỊCH NỘI DUNG BÀI BÁO
Tổng quan:
Công nghệ trí thông minh nhân tạo được biết đến như mạng nơron và thuật toán di truyền có thể dễ
dàng giải quyết những vấn đề kết hợp không gian và thời gian phi tuyến mang tính phức tạp cao. Chính
vì vậy bài báo này kết hợp các kĩ thuật của giải thuật di truyền và mạng nơron để xây dựng công cụ tiên
đoán thời gian mới cho “hệ thống thông tin địa lý” (GIS – Geographic Information System). Những

2000; Gahegan,2000; Openshaw and OpenShaw,1997).
Vì những nhà địa lý mong chờ giải quyết những vấn đề không gian và thời gian phức tạp và linh
động nên GIS đã bắt đầu tích hợp khoa học thông tin trong khai phá dữ liệu và khám phá tri thức
(Boots, 2000; Fischer,1997; Leung and Legung,1993; Marible,2000). Điều đó chính là lý do để sử
dụng máy tính xử lý với những vấn đề địa lý.
Mục tiêu dầu tiên của nghiên cứu này là chuẩn hóa sự tương tác giữa con người và môi trường của
họ, đồng thời để xây dựng tích hợp framework phân tích không gian và thời gian, làm lên sức mạnh
của GIS và khoa học thông tin.
Anselin(2000) đã tuyên bố có 3 yêu cầu cần thiết để thiết kế tốt 1 hệ thống thông tin tích hợp GIS,
bao gồm :
(1) Cung cấp một định dạng dữ liệu mà có thể chuyển đổi theo các kiểu GIS khác nhau.
(2) Thiết kế các thành phần có thể sử dụng lại trong môi trường lập trình windows.
(3) Có giao diện nền tảng trực quan.
Mục tiêu thứ hai trong nghiên cứu phát triển “gói phân tích thông tin không gian và thời gian thông
minh nhân tạo” – ASIA (Artificial intelligent Spatial and temporal Information Analyst), bao gồm việc
Tiểu Luận: Công Cụ Toán Học Nâng Cao
CN2011_TDLMMT_NHOM3
4
thiết kế một định dạng dữ liệu mới để chuyển đổi với các kiểu GIS khác nhau, sử dụng chương trình
C++ để xây dựng môđun đối tượng thông minh nhân tạo truy cập mở, và sử dụng phần mềm ArcView
GIS để trực quan hóa. Gói này tích hợp công nghệ thông minh nhân tạo và dữ liệu không gian và thời
gian theo cách phổ biến được sử dụng trong môi trường phần mềm GIS.
Mục tiêu thứ ba của nghiên cứu này là giải quyết với dự báo xu hướng thời gian của ô nhiễm
không khí như là một minh họa để chứng minh tính hợp lý và hữu ích của framework phân tích không
gian và thời gian và của hệ thống thông minh nhân tạo tích hợp.
2. Phân tích kiến trúc khái niệm không gian và thời gian GIS
Nghiên cứu này xây dựng kiến trúc không gian và thời gian GIS nhằm tích hợp GIS, trí thông
minh nhân tạo và công nghệ khai phá dữ liệu. Kiến trúc ở mức khái niệm này bao gồm các giai đoạn
phân tích không gian, thời gian và tích hợp nền tảng thông tin và quá trình hoạt động, được mô tả bằng
hình sau :

đồ GIS. Điều này cho phép các thuật toán di truyền để lựa chọn các mô tả và biến đổi nó sang định
dạng dữ liệu mới GIS2. Cuối cùng, chọn các mô hình kết nối tri thức mạng Nơron để khai phá
những dữ liệu tri thức ma trận trọng số.
3.1. Dữ liệu trình diễn GIS và hệ thống mô tả không gian
Theo các nguồn dữ liệu GIS về không gian hoặc trình tự thời gian, ASIA có thể sử dụng các menu để
thực hiện chuẩn bị dữ liệu hệ thống, bao gồm cả tính năng khái quát hóa từ đa giác hoặc hình đa
cạnh, mô tả lưới, tạo lại mẫu lưới, cắt gọn lưới bằng việc sử dụng chủ đề đa giác, các dạng lưới, cấu
trúc lưới (chuyển đổi dạng lưới sang dạng lattice), tăng cường tương phản lưới tuyến tính, tính phương
sai lưới, và phân chia bảng ngẫu nhiên. Và hệ thống đặc tả không gian tạo ra các vector số liệu thống
kê đơn giản, tính năng chỉ mục quay vòng các bất biến địa lý, chỉ số xu hướng bề mặt Evans, và các
chỉ số biến đổi Furiê nhanh các tần số bề mặt. Xem hình 2.
Tiểu Luận: Công Cụ Toán Học Nâng Cao
CN2011_TDLMMT_NHOM3
7
Hình 2: hệ thống mô tả không gian và chuẩn bị dữ liệu ASIA
3.2. Chuẩn bị định dạng chuyển đổi GIS2
Các định dạng dữ liệu GIS2 là một cấu trúc dữ liệu cơ bản trong hệ thống ASIA và kết nối giữa các
mô hình AI phân tích không gian và thời gian. Nó bao gồm định dạng dữ liệu ASCII thuần tuý, như
là một định dạng tập tin trung chuyển, có thể dễ dàng giao tiếp với các phần mềm GIS dung lượng
lớn hơn. Tập tin dữ liệu đầu tiên là file ghi lại các thuộc tính mà trong dòng đầu tiên ghi các biến và
số thứ tự bản ghi của đối tượng; từ dòng thứ hai lần lượt ghi các giá trị của tất cả các ô GRID. Xem
bảng 1 dưới đây.
Bảng 1: Tệp lưu trữ thuộc tính GIS2.
19 1 739596
3313 54.6524 97.776 -0.219237 3.60014 -0.00351583 -0.0219008 … 0
3296 63.3855 65.9391 -0.534405 1.21776 -0.0102157 -0.00895094 … 0
…
Tiểu Luận: Công Cụ Toán Học Nâng Cao
CN2011_TDLMMT_NHOM3
8

Hình 3: 2 bước trong việc chuyển đổi khuôn dạng dữ liệu GIS2 tại ASIA

3.3. Mô hình phân tích không gian mạng Nơtron có giám sát và không giám sát.
Trong việc “Gọi lại từ bộ nhớ” – là thành phần của mô hình phân tích mạng nơron ASIA, người sử
dụng đầu tiên cần quyết định hoặc huấn luyện một phần tử mới hoặc nạp vào một ma trận trọng số
đã được huấn luyện. Nếu người dùng lựa chọn để huấn luyện một ma trận trọng số mới, thì cần
phải sau đó quyết định chu kỳ cần huấn luyện trong BPN (mạng lan truyền phía sau) hoặc phải
thêm việc ánh xạ đến các thông tin trong mô hình SOM (bản đồ tự tổ chức).
Trong việc ánh xạ thông tin trong mô hình SOM “3” có nghĩa là kiểu số 9 là 3*3. Sau khi lựa chọn
“mẫu huấn luyện đầu vào” từ file nguồn GIS2, ta có thể bấm “Train”, và bảng nghiên cứu kết quả
huấn luyện sẽ tương ứng với “các đường cong chỉ thị của các thông tin đã học”.
Trái ngược với việc đó, nếu người dùng chọn để nạp một ma trận trọng số, điều đó có nghĩa là hệ
thống đã được huấn luyện từ trước và có thể gọi lại bởi những file đã được xác định. Tên file mặc
định trong mạng lan truyền ngược (BPN) là “neurowgt.dat”, và trong bản đồ tự tổ chức (SOM) đó
là “somwgt.dat” và “sommap.dat”.
Thứ 3 là: người dùng nên xác định việc xác thực hoặc giả lập file GIS2 nhằm mục đích để đặt ma
trận trọng số của các kiến thức đã có về không gian và thời gian trong việc sử dụng trong đoạn “kết
quả học được”. Khi gặp phải khuôn dạng bảng thời gian, chuẩn ASIA có thể vẽ nên một đường đồ
thị thời gian đơn giản hoặc một bản đồ phân tán theo trục XY hoặc khi gặp với khuôn dạng chủ đề
Tiểu Luận: Công Cụ Toán Học Nâng Cao
CN2011_TDLMMT_NHOM3
10
lưới GRID về không gian, chuẩn ASIA có thể tạo ra kết quả một chủ đề mới dạng lưới GRID. Ta
xem hình 4.
Hình 4: Mô hình phân tích giám sát và không giám sát mạng thần kinh
3.4. Mô hình phân tích không gian tối ưu thuật toán di truyền
Các thuật toán di truyền có thể được phân biệt với mô tả thích hợp bởi tập phong phú dữ liệu số mà
biểu diễn dưới dạng chuỗi các bit 0,1. Giải thuật di truyền tối ưu ASIA tích hợp mô hình phân tích sự
hội tụ mạng nơ ron để đánh giá tính đúng đắn của mỗi thế hệ với những chức năng phát triển tối ưu.
Giải thuật ASIA này đưa ra các phương pháp đánh giá đúng đắn, đảm bảo hiệu suất và tính hợp lý của

gian GIS mức khái niệm.
Bước phân tích
thời gian và không
gian
Nền tảng
thông tin
tích hợp
Bước nghiên cứu hệ thống
Chuẩn bị dữ liệu
(khai thác cơ sở dữ
liệu, thao tác, và
quản lý)
Chuẩn bị
dữ liệu
Bước 1: Tìm kiếm và thu thập dữ liệu về chất
gây ô nhiễm không khí.
Bước 2: Đưa ra dự báo các nhân tố chất gây ô
nhiễm không khí (SO2, CO, O3, PM10, NO2) và
thời gian (từ 1-3 giờ).
Hệ thống
mô tả dữ
liệu không
gian
Bước 3: lọc và xử lý nhiễu dữ liệu nếu cần thiết.
Khai thác dữ liệu
và khám phá tri
thức
Bước 4: chuyển đổi tất cả các biến, mục tiêu sang
định dạng tập tin GIS2 (thời điểm các chất gây ô
nhiễm được tổng kết trước 24 giờ, sự thay đổi về

Bước 9: Sử dụng phương sai để kiểm tra sự học
của mạng nơ ron và kiểm tra kết quả.
Cơ bản kiến
thức áp dụng
Bước 10: Sử dụng ma trận trọng lượng mạng nơ
ron để thiết lập mô hình dự báo chất gây ô nhiễm
không khí
4.2 Kết quả nghiên cứu
4.2.1 Lọc nhiễu dữ liệu và điều chỉnh dữ liệu trễ
Trong nghiên cứu khai thác dữ liệu và khám phá tri thức, chúng tôi luôn luôn phải đối mặt với
rất nhiều dữ liệu số ban đầu mà không có bất kỳ hiệu chuẩn hoặc kiểm tra.
Ví dụ, độ dày của các chất ô nhiễm không khí là quan trọng đối với các yếu tố vật lý trong chuyển động
của bầu khí quyển. Giả sử có một cơn bão hoặc một sự việc nào đó ảnh hưởng tới trạm, nó sẽ khiến
việc ghi âm rất thấp. Rõ ràng, việc loại bỏ các dữ liệu này quan trọng , nhưng có những hạn chế của
chính mô hình đó.
Trường hợp nghiên cứu các dữ liệu đột xuất sẽ đi lên hay đi xuống mạnh trong một số giai đoạn
đặc biệt vì sự bất ổn của công cụ tự động ghi âm. Ví dụ, dự báo SO2 kể từ ngày 3 / 31 và 7 / 27, các dữ
liệu quan sát được không ổn định ở giờ cao điểm vào cuối ngày. Và nghiêm trọng hơn sẽ ảnh hưởng
đến độ chính xác dự báo. Trong trường hợp này các hệ thống chuẩn bị dữ liệu tự động xóa bỏ các dữ
liệu không có giá trị và sử dụng các bản ghi liền kề, lọc dữ liệu sai. Xem Hình 6.
Tiểu Luận: Công Cụ Toán Học Nâng Cao
CN2011_TDLMMT_NHOM3
14
Hình 6: SO2 gây nhiễu dữ liệu
Bên cạnh nhiễu dữ liệu, nghiên cứu dự báo thời gian cũng có hiện tượng trễ thời gian. Điều này
là bởi vì các cơ sở dữ liệu không có dữ liệu liên quan trước khi các dữ liệu thời gian tiếp theo xuất hiện.
Hiện tượng thời gian trễ này có thể được cải thiện bằng cách tìm kiếm các chu kỳ thời gian trong cơ sở
dữ liệu. Trường hợp nghiên cứu này đã sử dụng sự tổng hợp từ 24 giờ trước đó như các biến đầu vào
của mạng nơ ron. Điều này rõ ràng làm giảm trễ dự báo từ 0,67 tới 0,88 (trong ví dụ của chất gây ô
nhiễm SO2). Xem Hình 7.

Tiểu Luận: Công Cụ Toán Học Nâng Cao
CN2011_TDLMMT_NHOM3
16
4.2.3. Kết quả dự báo mạng Nơron
4.2.3.1 Kết quả dự báo từ 1 đến 3 giờ
Nghiên cứu này sử dụng các chỉ số tương quan để kiểm tra các kết quả dự báo từ các mạnh
Nơron. Hai nhóm dữ liệu được quan sát và xác minh. Chúng tôi sử dụng dữ liệu quan sát để đưa vào
mạng Nơron và thu được một ma trận trọng số. Và chúng tôi sử dụng ma trận trọng số này trong việc
xác minh dữ liệu để so sánh giữa các giá trị ước lượng và giá trị thực.
Bảng 6 mô tả giá trị ước lượng dự báo trong khoảng từ 1 đến 3 giờ. Đối với các chất ô nhiễm thì
chỉ số tương quan dự báo trung bình giai đoạn 1-giờ là 0.94; 2-giờ là 0.77 và 3-giờ là 0.67. Trong một
giờ dự báo O3 mặc dù là thấp nhất cũng gần 0.9, PM10 là cao nhất với gần 0.97. Mô hình phi tuyến
tính có thể phải đối mặt với một sự đảo ngược, sự xoáy hay sự trùng lắp thời gian và nó sẽ làm thay đổi
các đường cong của mình. Tuy nhiên, nó chỉ thích hợp để phân tích và dự báo trong thời gian ngắn bởi
một đặc tính khó kiểm soát là phản hồi hành động lâu dài. Bởi vì chất lượng giống nhau của các dự báo
chắc chắn là được thực hiện trong khoảng thời gian ngắn và không được đảm bảo trong khoảng thời
gian dài. Mặc dù các trường hợp dự báo nghiên cứu đã có một độ chính xác cao trong dự báo ô nhiễm
không khí trong 1-giờ nhưng lại không thể dự báo cùng một độ chính xác trong khoảng thời gian dài
hơn. Rõ ràng, mô hình phi tuyến là phù hợp hơn cho các dự báo thời gian ngắn và khi thời gian càng
tăng thì độ chính xác càng giảm đi.
Bảng 6: Kết quả dự báo nhờ mạng Nơron thời gian từ 1 đến 3 giờ.
4.2.3.2. Kết quả dự báo 1-giờ hàng ngày
Đối với dự báo 1-giờ hàng ngày, mạng Nơron dự báo chỉ số tương quan, hầu hết tất cả các chất
ô nhiễm trong tất cả các ngày đều trên 0.9. Mỗi tháng, sau ngày thứ 26, dữ liệu được xác minh và do đó
có tổng cộng là 63 ngày. Đối với SO2, 50.8% của những ngày đã được trên 0.9 và 88.9% là trên 0.8.
Tiểu Luận: Công Cụ Toán Học Nâng Cao
CN2011_TDLMMT_NHOM3
17
Đối với CO thì 68.3% ngày đã được trên 0.9 và những ngày khác thì trên 0.8. Với O3, 47.6% của ngày
đã được trên 0.9 và 90.5% đã được trên 0.8. Đối với PM10, 60.3% của ngày đã được trên 0.9 và 92.1%

Boots, B. (2000) “Using GIS to Promote Spatial Analysis”, Journal of Geographical
Systems, 2:17-21
Fischer, M. M. (1997) “Computational Neural Networks: A New Paradigm for Spatial
Analysis”, Environment and Planning A, 29:1873-1891
Frank, A. U. (2000) “Geographic Information Science: New methods and technology”,
Journal of Geographical Systems, 2:99-105
Gahegan, M. (2000) “On the Application of Inductive Machine Learning Tools to
Geographical Analysis”, Geographical Analysis, 32(1): 113-139
Leung, Y., Leung, K.S. (1993) “An Intelligent Expert System Shell for Knowledge-based
GIS: 1. The Tools”, International Journal of Geographical Information Systems, 7(3):
189-199
Marble, D. F. (2000) “Some thoughts on the integration of spatial analysis and geographic
Information Systems”, Journal of Geographical Systems, 2:31-35
Muller, B., Reinhardt, J. and Strickland, M. T. (1995) Neural Networks: An Introduction
Physics of Neural Networks Series, Berlin: Spring
Openshaw, S., Openshaw, C. (1997) Artificial intelligence in Geography, John Wiley and
Sons LTD
Scott, A. (1990) “An Introduction to Genetic Algorithms”, AI Expert, 4(3): 49-53
PHẦN 2: PHÂN TÍCH ĐÁNH GIÁ
1. Phân tích bài toán
Trong bài viết trên tác giả đã giới thiệu sự kết hợp giữa giải thuật di truyền và mạng nơron để
xây dựng công cụ đoán thời gian mới cho “hệ thống thông tin địa lý” (GIS – Geographic Information
System). Do đó mục đích là hoàn thiện những lỗ hổng của chức năng khai phá dữ liệu.
Tiểu Luận: Công Cụ Toán Học Nâng Cao
CN2011_TDLMMT_NHOM3
19
Mục tiêu đầu tiên của nghiên cứu này là chuẩn hóa sự tương tác giữa con người và môi trường
của họ, đồng thời để xây dựng tích hợp framework phân tích không gian và thời gian, làm lên sức
mạnh của GIS và khoa học thông tin.
Mục tiêu thứ hai trong nghiên cứu phát triển “gói phân tích thông tin không gian và thời gian

Quá trình sinh sản và chọn lọc (phép tái sinh và phép chọn)
Phép tái sinh: là quá trình các cá thể được sao chép dựa trên độ thích nghi của nó. Độ thích nghi là một
hàm được gán các giá trị thực cho các cá thể trong quần thể của nó. Phép tái sinh có thể mô phỏng như
sau: Tính độ thích nghi của từng cá thể trong quần thể, lập bảng cộng dồn các giá trị thích nghi đó (theo
thứ tự gán cho từng cá thể) ta được tổng độ thích nghi. Giả sử quần thể có n cá thể. Gọi độ thích nghi
của cá thể thứ i là Fi, tổng dồn thứ i là Ft.Tổng độ thích nghi là Fm
- Tạo số ngẫu nhiên F có giá trị trong đoạn từ 0 đến Fm
- Chọn cá thể k đầu tiên thỏa mãn F ≥ Ft đưa vào quần thể của thế hệ mới.
Phép chọn: là quá trình loại bỏ các cá thể xấu và để lại những cá thể tốt. Phép chọn được mô tả như
sau: Sắp xếp quần thể theo thứ tự độ thích nghi giảm dần, loại bỏ các cá thể cuối dãy, chỉ để lại n cá thể
tốt nhất.
4. Ví dụ xây dựng cấu trúc dữ liệu thích hợp cho input và output của bài toán
Input: các biến môi trường tự nhiên, các thông số về không khí ( bầu khí quyển , độ dày không khí),
môi trường, các chất tự nhiên có trong nước, đất, không khí như: Sulfur dioxide, carbon monoxide,
Tiểu Luận: Công Cụ Toán Học Nâng Cao
CN2011_TDLMMT_NHOM3
21
ozone, nitrogen dioxide, hydrocarbon, non-methane hydrocarbon, nhiệt độ không khí, điểm sương,
nhiệt độ bề mặt mặt đất, áp suất khí quyển, tia cực tím xuyên tâm và mê-tan.
Output: dự đoán được chỉ số gây ô nhiễm, tỉ lệ tiếng ồn.
Quá trình thực hiện:
- Khởi tạo: thu thập dữ liệu môi trường
- Mã hóa các biến: Quyết định mục tiêu dự báo chất gây ô nhiễm không khí
- Chọn lọc: Để lọc tiếng ồn và xử lý dữ liệu với các dữ liệu nâng cao nếu cần thiết.
- Lai tạo: Để chuyển đổi tất cả các biến và các mục tiêu để GIS2 định dạng tập tin (các
chất ô nhiễm vào thời điểm thích hợp, tích lũy trước 24 giờ, sự thay đổi về thời gian dự
báo, và tỷ lệ thay đổi).
- Đột biến: Điều chỉnh các thông số của các thuật toán di truyền (đào tạo mạng lưới thần
kinh = 1400 chu kỳ, phát triển = 140 thế hệ, khả năng trao đổi = 0,25, và xác suất đột
biến = 0,04)