ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN TUẤN ANH

TỐI ƯU VIỆC LỰA CHỌN SỐ ĐẦU VÀO KHI ÁP
DỤNG MẠNG NƠRON NHÂN TẠO TRONG BÀI
TOÁN DỰ ĐOÁN ĐIỂM ĐÍCH CỦA MỘT CHUYẾN
TAXI

LUẬN VĂN THẠC SĨ KỸ THUẬT PHẦN MỀM

Hà Nội, 10/2018


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN TUẤN ANH

TỐI ƯU VIỆC LỰA CHỌN SỐ ĐẦU VÀO KHI ÁP
DỤNG MẠNG NƠRON NHÂN TẠO TRONG BÀI
TOÁN DỰ ĐOÁN ĐIỂM ĐÍCH CỦA MỘT CHUYẾN
TAXI
Ngành: Kỹ thuật Phần mềm
Chuyên ngành: Kỹ thuật Phần mềm
Mã số: 8480103.01

LUẬN VĂN THẠC SĨ KỸ THUẬT PHẦN MỀM

NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS PHẠM NGỌC HÙNG


ii
CHƯƠNG 4: MÔ HÌNH ĐỀ XUẤT VÀ THỰC NGHIỆM...............................26
4.1. Mô hình đề xuất........................................................................................26
4.2. Xây dựng thử nghiệm............................................................................... 30
4.3. Kịch bản thực nghiệm...............................................................................40
4.4. Kết quả thực nghiệm.................................................................................41
KẾT LUẬN.........................................................................................................47
TÀI LIỆU THAM KHẢO...................................................................................49
PHỤ LỤC............................................................................................................51


iii

LỜI CẢM ƠN
Trước tiên tôi xin dành lời cảm ơn chân thành và sâu sắc đến hai thầy giáo
PGS.TS Phạm Ngọc Hùng và TS. Trần Trọng Hiếu – những người đã hướng
dẫn, khuyến khích, chỉ bảo và tạo cho tôi những điều kiện tốt nhất từ khi bắt đầu
cho tới khi hoàn thành công việc của mình.
Tôi xin dành lời cảm ơn chân thành tới các thầy cô giáo khoa Công nghệ
thông tin, trường Đại học Công nghệ, Đại học Quốc Gia Hà Nội đã tận tình đào
tạo, cung cấp cho tôi những kiến thức vô cùng quý giá và đã tạo điều kiện tốt
nhất cho tôi trong suốt quá trình học tập, nghiên cứu tại trường.
Đồng thời tôi xin cảm ơn tất cả những người thân yêu trong gia đình tôi
cùng toàn thể bạn bè những người đã luôn giúp đỡ, động viên tôi những khi vấp
phải những khó khăn, bế tắc.
Cuối cùng, tôi xin chân thành cảm ơn các bạn trong lớp K22KTPM đã
giúp đỡ, tạo điều kiện thuận lợi cho tôi học tập và nghiên cứu chương trình thạc
sĩ tại Đại học Công nghệ, Đại học Quốc Gia Hà Nội.


Bảng 4.1 Sai lệch dự đoán của mô hình với từng giá trị k……………………..41
Bảng 4.2 Dãy giá trị k tối ưu tìm được…………………………………………43


vii

Danh sách mã nguồn
Mã nguồn 4.1 Gaussian process…..……………………………………………37
Mã nguồn 4.2 Hàm thu…………………………………………………………38


1

TÓM TẮT
Nền công nghiệp taxi đang thay đổi nhanh chóng. Các đối thủ mới cùng
những công nghệ mới đang thay đổi cách các doanh nghiệp taxi vận hành. Một
thay đổi lớn đang diễn ra là các công ty taxi chuyển từ hệ thống điều phối taxi
bằng bộ đàm sang hệ thống điều phối điện tử. Với hệ thống mới, mỗi taxi sẽ
được gắn một thiết bị GPS để xác định vị trí cũng như trao đổi thông tin liên lạc
với trung tâm. Hệ thống điều phối điện tử giúp cho việc xác định vị trí taxi đã đi
qua và hiện tại là dễ dàng nhưng không biết rõ địa điểm chiếc taxi đang đi tới vì
thông thường, lái xe sẽ không nhập điểm đến của hành trình. Đồng thời phương
thức thông báo về khách gọi xe mới cho các taxi cũng thay đổi, từ việc phát
thanh thông tin cho tất cả các xe bằng việc hệ thống sẽ tự động tìm một xe phù
hợp nhất để yêu cầu đón khách. Do đó nếu biết được gần đúng vị trí mà mỗi taxi
đang hướng tới thì hệ thống sẽ có thể tìm được chiếc taxi phù hợp nhất. Đặc biệt
trong khung giờ cao điểm, việc có một chuyến taxi sắp đến điểm trả khách mà
ngay gần vị trí trả khách này lại có một khách vừa yêu cầu xe là thường xuyên
xảy ra.
Hướng tiếp cận phổ biến trong việc dự đoán điểm đích của chuyến taxi là sử

nhất để yêu cầu đón khách. Do đó nếu biết được gần đúng vị trí mà mỗi taxi
đang hướng tới thì hệ thống sẽ có thể tìm được chiếc taxi phù hợp nhất [15].

1.2. Đặt vấn đề và đề xuất phương pháp
Một cuộc thi về dự đoán điểm đến của một hành trình taxi đã được tổ chức
vào năm 2015 với chiến thắng thuộc về đội MILA lab ở Canada bằng việc sử
dụng mạng nơron nhân tạo nhiều tầng truyền thẳng. Nhưng một vấn đề gặp phải
nằm ngay tại tầng đầu vào là số lượng các điểm GPS mà taxi đã đi qua là không
cố định, điều này thì không phù hợp với điều kiện kích thước tầng đầu vào của
mạng nơron nhiều tầng là phải cố định. Do đó các tác giả đã cố định số lượng
đầu vào bằng cách chỉ lấy k điểm đầu tiên và k điểm cuối cùng của chuyến đi.
Với mô hình chiến thắng trong cuộc thi, k có giá trị là năm. Tuy nhiên, trong bài
báo các tác giả chưa đề cập đến việc làm thế nào để xác định giá trị k tối ưu nhất
[1].
Trong đề tài này, tôi đề xuất phương pháp lựa chọn số đầu vào tối ưu trong
bài toán dự đoán điểm đến của một chuyến taxi khi cho trước tập các điểm ban
đầu. Đề tài hoàn toàn có thể áp dụng cho bài toán dự đoán số lượng đầu ra cố
định (fixed-length output) từ số lượng đầu vào thay đổi (variable-length input).


3

1.3. Tổng quan luận văn
Phần còn lại của luận văn được trình bày như sau.
Chương 1 giới thiệu về hoàn cảnh, đặt vấn đề, mô tả phương pháp đề xuất, và
cách nội dung trong luận văn được trình bày.
Chương 2 trình bày về kiến thức nền tảng về mạng nơron nhân tạo truyền
thẳng nhiều tầng.
Chương 3 trình bày về bài toán dự đoán điểm đích của chuyến taxi và
phương pháp đội MILA lab giải quyết vấn đề cũng như bài toán tìm số lượng


5
x1

Wk1

x2

Wk2

.
.

∑

.
.

xN

Hàm truyền
f(.)

Đầu ra
Hàm tổng

WkN

Đầu vào



6
5. Hàm truyền: là một hàm số dùng để tính đầu ra của nơron từ hàm tổng
và ngưỡng, ký hiệu là f.
6. Đầu ra: là tín hiệu đầu ra của nơron. Mỗi nơron chỉ có một tín hiệu đầu
ra. Với nơron thứ k đầu ra ký hiệu là yk.
Khái quát lại, nơron nhân tạo cho một đầu ra từ tập tín hiệu đầu vào.
Một số hàm truyền phổ biến là:
* Hàm đồng nhất
f(t) = αt
* Hàm bước nhảy

f(t) = { 1

ℎ

≥
0 ℎ



nhiều tầng là một trong những mạng nơron thông dụng nhất.


7

2.2. Mạng nơron truyền thẳng nhiều tầng
Mạng nơron truyền thẳng nhiều tầng (multi layer perceptron - MLP) là mạng
có n tầng (n >= 2). Trong đó tầng nhận tín hiệu vào của mạng gọi là tầng vào
(input layer). Tầng vào chỉ làm chức năng nhận tín hiệu mà không thực hiện việc
chuyển đổi thông tin nên không được tính vào số lượng tầng của mạng. Tín hiệu
ra của mạng được đưa ra từ tầng ra (output layer). Các tầng ở giữa tầng vào và
tầng ra gọi là các tầng ẩn (có n–1 tầng ẩn). Các nơron ở một tầng nhất định đều
liên kết đến tất cả các nơron ở tầng tiếp theo. Với mạng nơron truyền thẳng
(feedforward network) không có nút nào mà đầu ra của nó là đầu vào của một
nút khác trên cùng tầng với nó hoặc tầng trước.
Tầng vào

Tầng ẩn 1
Tầng ẩn n-1

Tầng ra

x1

y1
...

x2

...



8
Kiến trúc của một mạng nơron truyền thẳng nhiều tầng tổng quát có thể mô
tả như sau:
+ Đầu vào là một các tập vector (x1, x2, … xp) p chiều, đầu ra là một tập
các vector (y1, y2, … yq) q chiều.
+ Mỗi nơron thuộc tầng sau sẽ liên kết với tất cả các nơron thuộc tầng ngay
trước nó. Như vậy đầu ra của nơron tầng trước sẽ là đầu vào của nơron thuộc
tầng liền sau.
Mạng nơron truyền thẳng nhiều tầng sẽ hoạt động như sau: tại tầng đầu vào
các nơron nhận tín hiệu vào xử lý, thực hiện việc tính tổng trọng số rồi gửi tới
hàm truyền, kết quả của hàm truyền sẽ được gửi tới các nơron thuộc tầng ẩn đầu
tiên. Nơi đây các nơron tiếp nhận các kết quả này như là tín hiệu đầu vào và xử
lý rồi gửi kết quả đến tầng ẩn thứ 2. Quá trình cứ tiếp tục như thế cho đến khi
các nơron ở tầng ra cho ra kết quả.
Về ứng dụng của mạng nơron truyền thẳng nhiều tầng, vài kết quả đã được
chứng minh cụ thể như sau:
+ Mọi hàm toán học bất kỳ đều có thể được biểu diễn xấp xỉ bằng một
mạng nơron truyền thẳng ba tầng trong đó các nơron ở tầng ra đều sử dụng hàm
truyền tuyến tính và tất cả các nơron ở tầng ẩn đều dùng hàm truyền sigmoid.
+ Tất cả các hàm toán học liên tục đều có thể được biểu diễn xấp xỉ bởi
một mạng nơron truyền thẳng hai tầng trong đó các nơron ở tầng ra đều sử dụng
hàm truyền tuyến tính với sai số nhỏ tùy ý và tất cả các nơron ở tầng ẩn đều
dùng hàm truyền sigmoid.
+ Bất kỳ một hàm toán học Boolean nào cũng có thể được mô tả bởi một
mạng nơron truyền thẳng hai tầng trong đó hàm truyền sigmoid được sử dụng
cho tất cả các nơron.
Mạng nơron truyền thẳng nhiều tầng đã được sử dụng nhiều trong bài toán dự
báo và cho kết quả khả quan. Điều này sẽ giúp hướng tiếp cận này phổ biến hơn

(reinforcement learning).
+ Học có giám sát: là quá trình học giống việc ta dạy cho trẻ, luôn luôn có
một người “thầy giáo”, muốn dạy cho trẻ chữ “a”, ta đưa chữ “a” ra và nói với
trẻ rằng đây là chữ “a”. Và thực hiện tương tự với tất cả các chữ cái khác. Cuối
cùng để kiểm tra việc học, ta sẽ đưa ra một chữ cái bất kỳ và hỏi đây là chữ gì.
Do đó với học có giám sát, số tầng cần phân loại đã được biết trước. Nhiệm vụ


10
của việc huấn luyện là phải xác định được một cách thức phân tầng sao cho với
mỗi vector đầu vào sẽ được phân loại chính xác vào tầng của nó.
+ Học không giám sát: là quá trình học mà không có bất kỳ một người giám
sát nào. Trong bài toán mà luật học không giám sát được áp dụng, với tập dữ
liệu huấn luyện D thì nhiệm vụ của thuật toán học là phải phân chia tập dữ liệu
D thành các nhóm con, mỗi nhóm chứa các giá trị đầu vào có đặc trưng giống
nhau. Do đó với học không giám sát, số tầng phân loại chưa được biết và tùy
theo yêu cầu về độ giống nhau giữa các mẫu mà ta có các tầng phân loại tương
ứng.
+ Học tăng cường: còn được gọi là học thưởng phạt vì phương pháp này hoạt
động như sau: với mỗi giá trị đầu vào, thực hiện đánh giá vector đầu ra mà mạng
tính được với kết quả mong muốn, nếu được xem là “tốt” thì mạng sẽ được
thưởng (chính là việc tăng các trọng số liên kết), ngược lại nếu “xấu” mạng sẽ bị
phạt (tức là giảm các trọng số liên kết). Vì vậy học tăng cường là học theo nhà
phê bình còn học giám sát là học theo thầy giáo.


11

CHƯƠNG 3: BÀI TOÁN TÌM SỐ ĐẦU VÀO TỐI ƯU
KHI DỰ ĐOÁN ĐIỂM ĐÍCH CỦA

snapshots của mạng lưới taxi tại 5 thời gian khác nhau. Tập dữ liệu đánh giá này
thực ra được chia thành 2 tập nhỏ có kích thước bằng nhau: tập dữ liệu mở và
tập dữ liệu kín. Tập dữ liệu mở sẽ được sử dụng trong suốt cuộc thi để so sánh
các mô hình dự đoán của các đội thi, trong khi tập dữ liệu kín sẽ chỉ được sử
dụng vào lúc kết thúc cuộc thi để đánh giá các đội lần cuối.

3.2. Phương pháp của MILA lab
3.2.1 Giới thiệu chung
MILA lab là đội thi mà có thành phần chính là từ MILA lab thuộc trường
đại học Montreal, Canada. Hướng tiếp cận của đội MIA có ưu điểm là các công
việc phải làm bằng tay là ít hơn so với các đội thi khác. Nó gần như là hoàn toàn
tự động và đương nhiên là dựa trên mạng nơron nhân tạo truyền thẳng nhiều
tầng. Chính mô hình dự trên mạng nơron này đã giúp cho MILA lab chiến thắng
tại cuộc thi. Nhưng ngoài ra MILA lab cũng thực hiện nghiên cứu và thử một số
kiến trúc thay thế khác, tuy nhiên nó không thực hiện tốt lắm với bài toán này.
Do cuộc thi yêu cầu dự đoán điểm đích của một chuyến taxi dựa trên một
số lượng điểm đầu (prefix) của cuộc hành trình, mà tập dữ liệu cho trước lại bao
gồm tập đầy đủ các điểm của chuyến taxi, nên MILAB phải thực hiện tạo ra tập
điểm đầu. Tập dữ liệu huấn luyện có trên 1.7 triệu hành trình hoàn thiện, các
hành trình này cho ra 83.480.696 điểm có thể là điểm đầu. MILA lab cần lấy các
điểm đầu sao cho phân phối của nó là gần nhất có thể với tập dữ liệu đánh giá để
đảm bảo đưa ra kết quả dự đoán chính xác nhất. Tập dữ liệu đánh giá được lấy
từ năm thời điểm khác nhau của mạng lưới các taxi, vì vậy xác suất mà một
điểm bất kỳ trong tập dữ liệu huấn luyện sẽ nằm trong tập đánh giá là như nhau.
Do đó MILA lab sẽ cho tất cả các điểm trong tất cả các hành trình vào tập huấn
luyện làm điểm đầu, như vậy phân phối (distribution) điểm đầu trong tập MILA
lab sinh ra để huấn luyện sẽ giống với tập dữ liệu đánh giá [1].
Khi sử dụng mạng nơron nhân tạo truyền thẳng nhiều tầng (MLP) thì tầng
dữ liệu vào là các điểm đầu và thông tin meta của chuyến taxi, tầng ra sẽ dự
đoán đích điến (là một tọa độ gồm kinh độ và vĩ độ) của hành trình này. Trong


Số giá trị có thể

Kích thước nhúng

ID khách hàng

57106

10

ID taxi

448

10

ID điểm đón

64

10

Một phần tư giờ trong này

96

10

Ngày thứ mấy trong tuần


pi =

15

exp( )

∑ =1 exp( )

trong đó (ej)j là giá trị đầu ra của tầng trước.
Các cụm ci được sinh ra bằng thuật toán mean-shift trên tất cả các hành
trình có trong tập huấn luyện, và cuối cùng cho ra tập C chứa 3392 cụm. Tổng
quát lại mô hình mạng nơron nhân tạo truyền thẳng nhiều tầng sử dụng trong
cuộc thi của MILA lab được mô tả ở hình sau [1]:

dự đoán điểm đích
ŷ= ∑ =1

centroid

Cụm (ci)1≤i≤c

(pi)i
softmax
(ei)i

Tầng ẩn

Thông tin sẽ được nhúng



−

)

2

Nhưng mô hình của MILA lab lại không cho kết quả tốt khi huấn luyện trực
tiếp với khoảng cách Haversine này, do đó họ đã sử dụng một công thức tính
khoảng cách equirectanglular đơn giản hơn, mà hoàn toàn phù hợp với quy mô
của thành phố Porto như sau [1]:
deqrec(x,y) = R√(

−) cos(

−

))2 + (

− )2

2

MILA lab còn sử dụng giải thuật gradient descent ngẫu nhiên (stochastic
gradient descent – SGD), với momentum 0.9, tỷ lệ học là 0.01 và một mẻ
(batch) có kích thước 200 để tối thiểu độ sai lệch của khoảng cách
equirectanglular với khoảng cách thật.
3.2.5 Nhược điểm
Với bài toán dự đoán điểm đích của một chuyến taxi, MILA lab đã đưa ra mô
hình sử dụng mạng nơron nhân tạo nhiều tầng truyền thẳng để giải quyết vấn đề.