ĐẠ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
TS. TRẦN TRỌNG HIẾU
Hà Nội, 10/2018
i
Mục lục
LỜI CẢM ƠN ...................................................................................................... iii
LỜI CAM ĐOAN................................................................................................. iv
Danh sách hình ảnh ............................................................................................... v
Danh sách bảng biểu ............................................................................................ vi
Danh sách mã nguồn ........................................................................................... vii
TÓM TẮT ............................................................................................................. 1
CHƢƠNG 1: MỞ ĐẦU ........................................................................................ 2
1.1. Hoàn cảnh ................................................................................................... 2
1.2. Đặt vấn đề và đề xuất phƣơng pháp ........................................................... 2
1.3. Tổng quan luận văn..................................................................................... 3
CHƢƠNG 2: MẠNG NƠRON NHÂN TẠO TRUYỀN THẲNG NHIỀU TẦNG
............................................................................................................................... 4
2.1. Mạng nơron nhân tạo .................................................................................. 4
2.2. Mạng nơron truyền thẳng nhiều tầng.......................................................... 7
2.3. Các phƣơng pháp học phổ biến .................................................................. 9
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 CHUYẾN TAXI ............................................................................. 11
3.1. Bài toán dự đoán điểm đích của taxi ........................................................ 11
3.2. Phƣơng pháp của MILA lab ..................................................................... 12
3.3. Bài toán tìm số lƣợng đầu vào tối ƣu........................................................ 18
3.4. Các phƣơng pháp giải quyết hiện nay ...................................................... 20
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.
iv
LỜI CAM ĐOAN
Tôi xin cam đoan rằng luận văn thạc sĩ công nghệ thông tin “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” là công trình nghiên cứu của riêng tôi, không
sao chép lại của ngƣời khác. Trong toàn bộ nội dung của luận văn, những điều
đã đƣợc trình bày hoặc là của chính cá nhân tôi hoặc là đƣợc tổng hợp từ nhiều
nguồn tài liệu. Tất cả các nguồn tài liệu tham khảo đều có xuất xứ rõ ràng và
hợp pháp.
Tôi xin hoàn toàn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy
định cho lời cam đoan này.
Hà Nội, ngày …. tháng … năm …..
v
Danh sách hình ảnh
Hình 2.1 Mô hình toán học của một nơron ........................................................... 5
Hình 2.2 Mạng nơron truyền thẳng nhiều tầng………………………………….7
Hình 3.1 Kiến trúc của mạng nơron MILA lab………………………………...15
Hình 4.1 Mô hình sử dụng tối ƣu Bayes đề xuất……………………………….27
Hình 4.2 Cách thức triển khai thử nghiệm……………………………………..31
vi
Danh sách bảng biểu
Bảng 3.1. Thông tin meta chi tiết………………………………………………14
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ử
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 nhà nghiên cứu thƣờng chọn
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. Tuy nhiên, chƣa có nghiên cứu nào đề cập đến việc làm thế nào
để xác định giá trị k tối ƣu nhất.
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 tìm siêu tham số tối ƣu
(hyperparameter) khi có yếu tố số lƣợng đầu vào thay đổi.
Keywords: fixed-length output, variable-length sequence, taxi destination
prediction, multi-layer perceptron, hyperparameter optimization
2
CHƢƠNG 1: MỞ ĐẦU
1.1. Hoàn cảnh
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. Sự
thay đổi này mang lại nhiều thuận lợi nhƣng nó cũng gây nên nhiều vấn đề. 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
broadcast 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 [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
đầu vào tối ƣu cho mạng nơron nhân tạo nhiều tầng truyền thẳng để cải tiến mô
hình của đội MILA lab..
Chƣơng 4 trình bày mô hình đề xuất, xây dựng thử nghiệm và kết quả thực
nghiệm của phƣơng pháp.
Phần kết luận đƣa ra kết quả của luận văn và cũng nhƣ triển vọng và hƣớng
nghiên cứu trong tƣơng lai.
4
CHƢƠNG 2: MẠNG NƠRON NHÂN TẠO TRUYỀN
THẲNG NHIỀU TẦNG
2.1. Mạng nơron nhân tạo
Mạng nơron nhân tạo (artificial neural network) là một mô hình tính toán xử
lý thông tin bằng cách mô phỏng theo cách thức hoạt động của hệ nơron sinh
học trong bộ não con ngƣời [2].
Mạng gồm một nhóm các phần tử (nơron nhân tạo) kết nối với nhau thông
qua các liên kết (liên kết đƣợc đánh trọng số). Nó làm việc nhƣ một thể thống
nhất bằng cách truyền thông tin theo các kết nối và tính giá trị mới tại các nơron.
Một mạng nơron nhân tạo sẽ đƣợc cấu hình để giải quyết một vấn đề cụ thể nào
đó nhƣ nhận dạng mẫu, phân loại dữ liệu, dự đoán,... Nó hoạt động thông qua
một quá trình học từ tập các mẫu huấn luyện. Việc học về bản chất chính là quá
trình đƣa dữ liệu vào mạng nơron và thực hiện hiệu chỉnh trọng số liên kết giữa
các nơron thông qua kết quả có trƣớc trong mẫu.
Mạng nơron nhân tạo đƣợc coi là một công cụ mạnh để giải quyết các bài
toán có tính phi tuyến, phức tạp và đặc biệt trong các trƣờng hợp mà mối quan
hệ giữa các quá trình không dễ thiết lập một cách tƣờng minh.
Mô hình toán học tiêu biểu cho một nơron nhân tạo đƣợc minh họa nhƣ hình
2.1 sau:
5
Wk1
x1
Hàm truyền
Wk2
x2
.
.
.
.
xN
WkN
Đầu vào
∑
f(.)
yk
Đầu ra
Hàm tổng
bk
Trọng số liên kết
Ngƣỡng
Hình 2.1 Mô hình toán học của một nơron
Cấu trúc của một nơron k đƣợc mô tả toán học bằng cặp biểu thức sau:
=
∑
và
yk = f(uk – bk)
Trong đó, cụ thể các thành phần của một nơron gồm:
1. Tập đầu vào: là các tín hiệu (dữ liệu) vào của nơron, thƣờng đƣợc đƣa
dƣới dạng một vector N chiều (x1, x2, … xN).
2. Tập liên kết: là các liên kết từ tín hiệu đến nơron. Mỗi liên kết sẽ đƣợc
đánh trọng số, ví dụ nhƣ nơron thứ k sẽ có trọng số wk1 ở liên kết 1. Do đó với
mỗi nơron ta cũng có một vector trọng số liên kết N chiều (wk1,wk2, … wkN). Các
trọng số này thông thƣờng sẽ đƣợc tạo ngẫu nhiên ở thời điểm tạo mạng, sau đó
qua quá trình học sẽ đƣợc hiệu chỉnh dần.
3. Hàm tổng: là tổng của tích các đầu vào với trọng số liên kết của nó, kí
hiệu cho hàm tổng của nơron thứ k là uk.
4. Ngƣỡng: là một thành phần của hàm truyền, ký hiệu cho ngƣỡng của
nơron thứ k là bk.
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) = {
* Hàm dấu
f(t) = {
* Hàm sigmoid
f(t) =
* Hàm sigmoid lƣỡng cực
f(t) =
=
Có nhiều loại mạng nơron khác nhau trong đó mạng nơron truyền thẳng
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
.
.
.
...
.
.
.
...
.
.
.
y2
.
.
.
yq
xp
Hình 0.2 Mạng nơron truyền thẳng nhiều tầng
Nếu mạng nơron truyền thẳng chỉ có tầng nơron đầu vào và tầng nơron đầu
ra thì đƣợc gọi là mạng nơron truyền thẳng 1 tầng.
Mạng nơron có phản hồi (feedback network) là mạng mà đầu ra của một
nơron có thể trở thành đầu vào của nơron trên cùng một tầng hoặc của tầng
trƣớc đó. Mạng nơron có phản hồi có chu trình khép khín gọi là mạng nơron hồi
quy.
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
trong thời gian tới cho bài toán dự báo.
9
2.3. Các phƣơng pháp học phổ biến
Trong cuộc sống tự nhiên, học đƣợc định nghĩa là quá trình tiếp thu cái mới
hoặc bổ sung, trau dồi các kiến thức, kỹ năng, kinh nghiệm, giá trị, nhận thức
hoặc sở thích và có thể liên quan đến việc tổng hợp các loại thông tin khác nhau.
Khả năng học hỏi là sở hữu của loài ngƣời, một số động vật. Việc học sẽ giúp
vật học tiến bộ theo thời gian.
Mạng nơron cũng đƣợc học thông qua các luật học. Luật học là một thủ tục
dùng để xác định việc cập nhật trọng số liên kết và ngƣỡng của mạng nơron.
Luật học còn đƣợc gọi là thuật toán huấn luyện mạng. Quá trình học còn gọi là
quá trình huấn luyện. Một mạng nơron đƣợc huấn luyện sao cho với một tập các
vector đầu vào X, mạng sẽ cho ra tập các vector đầu ra Y mong muốn. Tập X
dùng để làm đầu vào huấn luyện cho mạng nên đƣợc gọi là tập huấn luyện
(training set). Các phần tử x thuộc X đƣợc gọi là các mẫu huấn luyện (training
example). Nhƣ đã đƣợc đề cập ở phần đầu, việc học bản chất là việc cập nhật
liên tục các trọng số liên kết trong mạng nơron. Trong quá trình này, các trọng
số của mạng sẽ hội tụ dần tới các giá trị sao cho với mỗi đầu vào, mạng sẽ cho
đầu ra nhƣ ý muốn.
Với mỗi mạng nơron nhân tạo có hai vấn đề cần học đó là học tham số
(parameter learning) và học cấu trúc (structure learning). Học tham số là việc
điều chỉnh trọng số của các liên kết giữa các nơron trong mạng, còn học cấu trúc
là việc thay đổi cấu trúc của mạng bao gồm thay đổi số lớp nơron, số nơron của
mỗi lớp và cách liên kết giữa chúng. Hai vấn đề này có thể đƣợc thực hiện đồng
thời hoặc tách biệt.
Luật học của mạng nơron có thể chia làm 3 loại: học có giám sát (supervised
learning), học không có giám sát (unsupervised learning), học tăng cƣờng
(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
CHUYẾN TAXI
3.1. Bài toán dự đoán điểm đích của taxi
Bài toán tìm đích đến của một chuyến taxi đang gây đƣợc sự chú ý của cộng
đồng nghiên cứu trong thời gian gần đây. Vì vậy vào năm 2015 tại hội nghị
ECML/PKDD đã tổ chức một cuộc thi dự đoán đích đến của một chuyến taxi
nhƣ là một cuộc thi của Kaggle [15]. Dữ liệu đầu vào của bài toán là những
điểm bắt đầu trong hành trình của một chuyến taxi (thƣờng gọi là prefixes) và
những thông tin meta của chuyến taxi đó. Từ đó ngƣời tham gia cuộc thi phải
tìm ra điểm đích của cuộc hành trình đó (gồm kinh độ và vĩ độ). Ý nghĩa của
việc giải bài toán trên là sẽ giúp công ty taxi phân chia số lƣợng taxi tại mỗi
điểm đón, khu vực đón một cách tối ƣu nhất.
Ngƣời tham gia cuộc thi sẽ phải xây dựng một mô hình dự đoán dựa trên tập
dữ liệu gồm tất cả các chuyến đi của 442 taxi hoạt động tại thành phố Porto thủ
đô của Bồ Đào Nha trong suốt một năm hoàn chỉnh (từ ngày 01/07/2013 đến
ngày 30/06/2014) [15]. Tập dữ liệu huấn luyện trên có hơn 1.7 triệu chuyến đi
hoàn chỉnh [1]. Mỗi chuyến đi sẽ bao gồm các thông tin sau:
+ Một chuỗi các vị trí (gồm kinh độ và vĩ độ) đƣợc đo bằng GPS mỗi 15
giây. Vị trí cuối cùng chính là đích đến của hành trình. Do độ dài của mỗi
chuyến taxi là khác nhau nên số lƣợng vị trí trong mỗi chuyến đi cũng sẽ khác
nhau.
+ Thông tin meta tƣơng ứng với mỗi chuyến đi gồm:
1. Nếu khách hàng gọi taxi bằng điện thoại thì chúng ta sẽ có ID của khách
hàng. Nếu khách hàng bắt taxi tại điểm đón thì chúng ta sẽ có ID của điểm đón.
Ngƣợc lại chúng ta sẽ không có thông tin gì cả.
2. ID của taxi.
3. Thời gian bắt đầu của chuyến đi dƣới định dạng của hệ điều hành unix.
- Xem thêm -