BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC LẠC HỒNG

ĐOÀN MINH HOÀNG
PHÁT TRIỂN THUẬT GIẢI TÌM KIẾM TƯƠNG
TỰ VỚI MÔ HÌNH MAPREDUCE

LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

Đồng Nai, Năm 2017


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC LẠC HỒNG

ĐOÀN MINH HOÀNG
PHÁT TRIỂN THUẬT GIẢI TÌM KIẾM TƯƠNG
TỰ VỚI MÔ HÌNH MAPREDUCE

LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
Chuyên ngành: Công Nghệ Thông Tin
Mã số : 60.48.02.01
NGƯỜI HƯỚNG DẪN KHOA HỌC
PGS. TS. ĐẶNG TRẦN KHÁNH

Đồng Nai, Năm 2017


LỜI CẢM ƠN
Tôi xin chân thành gửi lời cám ơn tới PGS.TS. Đặng Trần Khánh đã tận tình
hướng dẫn Tôi trong quá trình thực hiện luận văn này. Trong thời gian nghiên cứu và

làm việc với Thầy, Tôi đã nhận được nhiều đóng góp và ý kiến quý giá giúp Tôi học
hỏi và tiếp thu những kiến thức lý luận, phương pháp nghiên cứu và thực tiễn để có
thể áp dụng vào đề tài Luận văn.
Tôi xin chân thành cám ơn Khoa Sau Đại Học - Trường Đại Học Lạc Hồng đã
lập chương trình đào tạo Cao Học tại trường để Tôi có cơ hội học tập và nâng cao
kiến thức. Xin cám ơn quý Thầy/Cô đã giảng dạy và cung cấp cho Tôi những kiến
thức quý báu trong thời gian học tập tại Trường Đại Học Lạc Hồng, giúp tôi nắm
vững và học hỏi được những kiến thức chuyên ngành để áp dụng vào thực tiễn cuộc
sống và công việc sau này.
Cuối cùng, xin chân thành cám ơn ban lãnh đạo nhà trường, quý Thầy/Cô cùng
quí phụ huynh đã ủng hộ, giúp đỡ trong suốt quá trình thực hiện đề tài. Cám ơn các
thành viên trong gia đình, các bạn, và đặc biệt là người yêu của Tôi đã động viên tinh
thần, vật chất trong quá trình học tập của Tôi tại Trường Đại Học Lạc Hồng.
Biên hòa, ngày 10 tháng 06 năm 2017
Học viên

Đoàn Minh Hoàng


LỜI CAM ĐOAN
Tôi xin cam đoan tất cả các nội dung của Luận văn hoàn toàn được hình thành,
nghiên cứu và phát triển từ những quan điểm của chính cá nhân Tôi dưới sự hướng
dẫn khoa học của PGS.TS. Đặng Trần Khánh. Các số liệu và kết quả có được trong
Luận văn Thạc sĩ là hoàn toàn trung thực.
Biên hòa, ngày 10 tháng 06 năm 2017
Học viên

Đoàn Minh Hoàng



TRƯỜNG ĐẠI HỌC LẠC HỒNG
KHOA SAU ĐẠI HỌC
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

TÓM TẮT LUẬN VĂN
(Dùng cho học viên và người hướng dẫn)
Đề tài: Phát triển thuật giải tìm kiếm tương tự với mô hình MapReduce.
Ngành: Công nghệ thông tin

Mã số: 60.48.02.01

Học viên: Đoàn Minh Hoàng
Người hướng dẫn: PGS.TS. Đặng Trần Khánh
NỘI DUNG TÓM TẮT
1. Nội dung được giao và kết quả mong đợi của người hướng dẫn
Nghiên cứu và cải tiến tác vụ tìm kiếm tương tự với mô hình MapReduce.
2. Cách thức giải quyết vấn đề
 Đọc và hiểu một số bài báo, tạp chí, một số công trình đã công bố, một số sách
chuyên ngành liên quan:
o Tác vụ tìm kiếm tương tự: (Zezula et al., 2010)
o Kỹ thuật xử lý ngôn ngữ tự nhiên: (Rajaraman & Ullman, 2011)
o Mô hình hóa văn bản: (Rajaraman & Ullman, 2011)
o Mô hình MapReduce: (Dean & Ghemawat, 2008)
o Giải thuật tìm kiếm tương tự với mô hình MapReduce: (Elsayed et al.,
2008; Li et al., 2011; Phan et al., 2014)
 Đọc hướng dẫn sử dụng Hadoop framework để biết cách thức giao tiếp và triển
khai mô hình MapReduce với framework Hadoop dùng Python (Hadoop
Streaming).
 Nghiên cứu thuật giải từ bài báo “An Elastic Approximate Similarity Search
in Very Large Datasets with MapReduce” của các tác giả (Phan et al., 2014),

từ đó cải tiến thuật giải này.
 Tiến hành thí nghiệm và đánh giá thuật giải được đề xuất theo mô hình
MapReduce.
3. Đánh giá về mặt khoa học của kết quả


 Đề xuất phương pháp cải tiến với các phương pháp chính yếu được mô tả
như sau:
o Tối giản MapReduce-job
o Cải thiện mức độ đánh giá tương tự
o Đơn giản hóa quy trình tính toán
 Hiện thực mô hình MapReduce trên hệ thống máy ảo
 Chúng Tôi nhận thấy rằng phiên bản cải tiến đạt được hiệu suất cao hơn và
đánh giá mức độ tương tự tốt hơn phiên bản gốc.
4. Những vấn đề còn tồn tại so với nội dung được giao (nếu có)
 Giới hạn về phần cứng và thiết bị, các kết quả thí nghiệm mới chỉ được triển
khai trên các máy ảo với lượng dữ liệu giới hạn.
 Phương pháp cải tiến vẫn chưa tận dụng được lợi thế của việc đánh chỉ mục.
 Đánh giá mức độ tương tự về mặt ngữ nghĩa còn bị hạn chế.

NGƯỜI HƯỚNG DẪN

PGS.TS. ĐẶNG TRẦN KHÁNH

Ngày 10 tháng 06 năm 2017
HỌC VIÊN

ĐOÀN MINH HOÀNG



MỤC LỤC
Trang
Trang bìa phụ
Lời cám ơn
Lời cam đoan
Tóm tắt luận văn
Mục lục
Danh mục bảng
Danh mục hình
CHƯƠNG 1:

GIỚI THIỆU TỔNG QUAN ...........................................................1

1.1

Giới thiệu về đề tài ........................................................................................1

1.2

Mục tiêu của đề tài.........................................................................................2

1.3

Đối tượng và phạm vi nghiên cứu .................................................................3

1.3.1

Đối tượng nghiên cứu .............................................................................3

1.3.2


Phạm vi nghiên cứu ................................................................................3

1.4

Phương pháp nghiên cứu ...............................................................................3

1.4.1

Nội dung thực hiện .................................................................................3

1.4.2

Phương pháp thực hiện ...........................................................................3

1.5

Ý nghĩa của đề tài ..........................................................................................4

CHƯƠNG 2:

CƠ SỞ LÝ THUYẾT .......................................................................5

2.1

Tìm kiếm tương tự .........................................................................................5

2.2

Mô hình hóa đối tượng tài liệu ......................................................................7


2.3

Mô hình MapReduce .....................................................................................8

2.4

Hadoop Framework .......................................................................................9

2.5

Hadoop Streaming .......................................................................................11

2.6

Ngôn ngữ lập trình Python ..........................................................................14

CHƯƠNG 3:
3.1

PHƯƠNG PHÁP CẢI TIẾN ĐƯỢC ĐỀ XUẤT ..........................16

Các công trình nghiên cứu liên quan ...........................................................16


3.2

Phương pháp cải tiến ...................................................................................20

3.2.1


Tối giản MapReduce-job ......................................................................21

3.2.2

Cải thiện mức độ đánh giá tương tự .....................................................22

3.2.3

Đơn giản hóa quy trình tính toán ..........................................................24

3.3

Giải thuật đề xuất .........................................................................................24

3.4

Ví dụ minh họa ............................................................................................27

CHƯƠNG 4:

ĐÁNH GIÁ THỬ NGHIỆM .........................................................29

4.1

Thiết lập môi trường thử nghiệm.................................................................29

4.2

Tập dữ liệu ...................................................................................................30


4.3

Mô hình hóa đối tượng tài liệu ....................................................................32

4.4

Đánh giá phương pháp cải tiến ....................................................................32

4.4.1

Đo lường hiệu suất ................................................................................32

4.4.2

Đo lường khối lượng xử lý dữ liệu trung gian ......................................33

4.4.3

Đo lường mức độ đánh giá tương tự .....................................................34

4.4.4

Đo lường mức độ tác động lên hệ thống file ........................................36

4.4.5

Đo lường mức độ tác động lên hệ thống file phân tán của Hadoop .....38

4.4.6


Đo lường mức độ tác động lên Hadoop framework .............................41

CHƯƠNG 5:

TỔNG KẾT ....................................................................................45

5.1

Kết luận ........................................................................................................45

5.2

Những thiếu sót chính của luận văn ............................................................45

5.3

Hướng phát triển tiếp theo ...........................................................................46

Danh mục tài liệu tham khảo


DANH MỤC BẢNG
Bảng 2-1: Liệt kê các file chính cần cấu hình trong Hadoop framework .................10
Bảng 2-2: Thông số của Hadoop Streaming .............................................................12
Bảng 3-1: Tổ chức dữ liệu đầu vào và đầu ra cho hai tác vụ MAP và REDUCE ....22
Bảng 3-2: Giải thuật cho tác vụ Map ........................................................................25
Bảng 3-3: Giải thuật cho tác vụ Reduce ...................................................................26
Bảng 4-1: Mô tả thông số phần cứng và hệ điều hành ..............................................29
Bảng 4-2: Thông số cấu hình phần mềm ..................................................................29

Bảng 4-3: Mô tả các gói dữ liệu ................................................................................30
Bảng 4-4: Khối lượng dữ liệu trung gian được xuất ra từ tác vụ Map .....................34
Bảng 4-5: Khối lượng dữ liệu trung gian xử lý ở giai đoạn pha trộn .......................34
Bảng 4-6: Mô tả ý nghĩa tập tin tài liệu văn bản .......................................................35
Bảng 4-7: So sánh mức độ tương tự giữa PBG và PBCT .........................................36
Bảng 4-8: Mô tả thông số tác động lên hệ thống file ................................................37
Bảng 4-9: Kết quả thí nghiệm các thông số tác động lên hệ thống file với 1000 file
dữ liệu ........................................................................................................................37
Bảng 4-10: Kết quả thí nghiệm các thông số tác động lên hệ thống file với 3000 file
dữ liệu ........................................................................................................................37
Bảng 4-11: Kết quả thí nghiệm các thông số tác động lên hệ thống file với 5000 file
dữ liệu ........................................................................................................................38
Bảng 4-12: Mô tả thông số tác động lên hệ thống file phân tán của Hadoop ...........38
Bảng 4-13: Mô tả thông số tác động lên hệ thống file phân tán của Hadoop với 1000
file dữ liệu .................................................................................................................39
Bảng 4-14: Mô tả thông số tác động lên hệ thống file phân tán của Hadoop với 3000
file dữ liệu .................................................................................................................40
Bảng 4-15: Mô tả thông số tác động lên hệ thống file phân tán của Hadoop với 5000
file dữ liệu .................................................................................................................40
Bảng 4-16: Mô tả thông số tác động lên Hadoop framework ...................................41
Bảng 4-17: Mô tả thông số tác động lên Hadoop framework với 1000 file dữ liệu .42
Bảng 4-18: Mô tả thông số tác động lên Hadoop framework với 3000 file dữ liệu .43
Bảng 4-19: Mô tả thông số tác động lên Hadoop framework với 5000 file dữ liệu .44


DANH MỤC HÌNH
Hình 1-1: Minh họa bài toán tìm kiếm tương tự với mô hình MapReduce ................2
Hình 2-1: Hai ví dụ biến thể phổ biến của tìm kiếm tương tự; a) tìm kiếm tương tự
theo phạm vi r; b) tìm kiếm 3 đối tượng gần nhất với truy vấn q ...............................6
Hình 2-2: Tổng quan thực thi mô hình MapReduce (Dean & Ghemawat, 2008) ......9

Hình 2-3: Kiến trúc tổng quan của Hadoop với 4 mô đun chính ..............................10
Hình 2-4: Dòng chảy của Hadoop Streaming ...........................................................12
Hình 3-1: Tính toán mức độ tương tự với hai MapReduce job (Elsayed et al., 2008)
...................................................................................................................................16
Hình 3-2: Quá trình tạo từ điển tần số của từ với MapReduce (Li et al., 2011) .......17
Hình 3-3: Quá trình tạo véc tơ văn bản với MapReduce (Li et al., 2011) ................18
Hình 3-4: Quá trình tạo file ngược PLT với MapReduce (Li et al., 2011) ...............18
Hình 3-5: Quá trình tìm kiếm tương tự với MapReduce (Li et al., 2011) ................19
Hình 3-6: Công việc MapReduce-1 (Phan et al., 2014) ............................................19
Hình 3-7: Công việc MapReduce-2 (Phan et al., 2014) ............................................20
Hình 3-8: Mô hình tổng quan cho công việc MapReduce ........................................22
Hình 3-9: Một ví dụ minh họa...................................................................................28
Hình 4-1: Sự phân bố kích thước dữ liệu của gói dữ liệu 1000P1 ............................31
Hình 4-2: Sự phân bố kích thước dữ liệu của gói dữ liệu 2000P2 ............................31
Hình 4-3: Sự phân bố kích thước dữ liệu của gói dữ liệu 2000P3 ............................32
Hình 4-4: Tổng thời gian thực thi MapReduce job ...................................................33


1

CHƯƠNG 1:

GIỚI THIỆU TỔNG QUAN

1.1 Giới thiệu về đề tài
Tìm kiếm tương tự đóng vai trò quan trọng trong nhiều ứng dụng và lĩnh vực
khác nhau như tìm kiếm các đối tượng (gần) giống nhau, gom cụm dữ liệu, phân loại
dữ liệu. Ví dụ trong lĩnh vực gom cụm dữ liệu, tác vụ tìm kiếm tương tự được áp
dụng nhằm mục tiêu gom nhóm các đối tượng tương tự nhau vào một cụm hoặc tác
vụ tìm kiếm tương tự được áp dụng trong ứng dụng tìm kiếm những tập tài liệu văn

bản nào có mức độ tương tự với tập tài liệu văn bản được cho trước. Tuy nhiên, tác
vụ tìm kiếm tương tự thông thường tốn khá nhiều chi phí trong việc tìm kiếm và tính
toán mức độ tương tự giữa một cặp đối tượng được xem xét (Zezula et al., 2010).
Mặt khác, sự phát triển ngày càng nhanh chóng của khoa học và công nghệ làm
cho lượng dữ liệu được sinh ra, thu thập, và xử lý ngày càng nhiều. Điều này dẫn
đến hiện tượng bùng nổ dữ liệu (Letouzé, 2012). Khối lượng dữ liệu ngày càng lớn
làm cho các phương pháp xử lý truyền thống trở nên lạc hậu hoặc không phù hợp để
sử dụng. Trong bài toán tìm kiếm tương tự, dữ liệu lớn đồng nghĩa với việc số lượng
đối tượng cần tìm kiếm và tính toán mức độ tương tự giữa các cặp đối tượng trong
số chúng là lớn. Điều này dẫn đến chi phí cao khi thực thi tác vụ tìm kiếm tương tự
trên tập dữ liệu lớn.
Một trong những phương pháp tiên tiến trong việc xử lý khối lượng dữ liệu lớn
là mô hình xử lý song song trong môi trường phân tán gọi là MapReduce (Dean &
Ghemawat, 2008). Mô hình này tận dụng nhiều máy tính để xử lý các phân khúc dữ
liệu và sau đó sẽ gom gộp các kết quả trung gian để cho ra kết quả cuối cùng.
Đã có nhiều công trình nghiên cứu liên quan đến việc cải thiện hiệu suất của
tác vụ tìm kiếm tương tự với mô hình MapReduce. Tuy nhiên, một số công trình
nghiên cứu sử dụng các giả định làm giảm độ phức tạp của phương pháp đo lường,
trong khi giả định này trở nên không thực tế, hoặc các phương pháp được sử dụng
tốn kém nhiều về mặt chi phí (Phan et al., 2014). Chính vì vậy, đề tài này sẽ tiến
hành nghiên cứu để cải tiến một phương pháp tìm kiếm tương tự với mô hình
MapReduce.


2
Hình 1-1 minh họa bài toán tìm kiếm tương tự với mô hình MapReduce. Đối
tượng tìm kiếm trong đề tài này là các đối tượng tài liệu văn bản. Nhìn chung, khi
được cung cấp câu truy vấn, tác vụ tìm kiếm tương tự sẽ được thực hiện dựa trên
thuật giải tìm kiếm theo mô hình MapReduce chạy trên nền tảng framework Hadoop.
Dữ liệu đầu ra sẽ là các tài liệu văn bản tương tự với câu truy vấn được cung cấp ở

dữ liệu đầu vào.

Hình 1-1: Minh họa bài toán tìm kiếm tương tự với mô hình MapReduce
1.2 Mục tiêu của đề tài
Phát triển thuật giải tìm kiếm tương tự với mô hình MapReduce. Việc cải tiến
mức độ hiệu quả của tác vụ tìm kiếm tương tự có thể tiếp cận ở mức thuật giải hoặc
ở mức framework như được minh họa ở Hình 1-1. Tuy nhiên, đề tài sẽ tập trung
nghiên cứu và cải tiến thuật giải theo mô hình MapReduce ở mức thuật giải vì các lý
do chính sau:
- Không cần can thiệp vào Hadoop framework. Từ đó thuật giải sẽ độc lập với
nền tảng thực thi thuật giải. Như vậy, các thay đổi về cấu trúc và vận hành của
framework sẽ không ảnh hưởng đến thuật giải chạy trực tiếp trên đó.
- Sự cải tiến mức độ hiệu quả của tác vụ tìm kiếm tương tự từ thuật giải có thể
nhận được sự hỗ trợ đồng hành khi có sự cải tiến về hiệu suất thực thi giải thuật từ
framework được sử dụng.


3
1.3 Đối tượng và phạm vi nghiên cứu
1.3.1 Đối tượng nghiên cứu
Tác vụ tìm kiếm tương tự dữ liệu văn bản với mô hình MapReduce trên nền
tảng Hadoop Framework với ngôn ngữ lập trình Python.
1.3.2 Phạm vi nghiên cứu
Tìm hiểu các công trình liên quan về tác vụ tìm kiếm tương tự dữ liệu văn bản
trên mô hình MapReduce.
Phân tích và cải tiến thuật giải tìm kiếm tương tự trên mô hình MapReduce từ
công trình nghiên cứu của (Phan et al., 2014).
1.4 Phương pháp nghiên cứu
1.4.1 Nội dung thực hiện
- Tìm hiểu tác vụ tìm kiếm tương tự.

- Tìm hiểu kỹ thuật xử lý ngôn ngữ tự nhiên, mô hình hóa văn bản trong
tác vụ tìm kiếm tương tự.
- Tìm hiểu mô hình MapReduce.
- Tìm hiểu framework Hadoop trong việc triển khai thực thi mô hình
MapReduce.
- Tìm hiểu ngôn ngữ lập trình Python và cách thức giao tiếp với Hadoop.
- Nghiên cứu và đề xuất cải tiến thuật giải tìm kiếm tương tự với mô
hình MapReduce.
- Tiến hành thí nghiệm và đánh giá thuật giải được đề xuất.
1.4.2 Phương pháp thực hiện
- Đọc và hiểu một số bài báo, tạp chí, một số công trình đã công bố, một
số sách chuyên ngành liên quan:


Tác vụ tìm kiếm tương tự: (Zezula et al., 2010)



Kỹ thuật xử lý ngôn ngữ tự nhiên: (Rajaraman & Ullman, 2011)



Mô hình hóa văn bản: (Rajaraman & Ullman, 2011)



Mô hình MapReduce: (Dean & Ghemawat, 2008)


4



Giải thuật tìm kiếm tương tự với mô hình MapReduce: (Elsayed

et al., 2008; Li et al., 2011; Phan et al., 2014)
- Đọc hướng dẫn sử dụng Hadoop framework để biết cách thức giao
tiếp và triển khai mô hình MapReduce với framework Hadoop dùng Python (Hadoop
Streaming).
- Nghiên cứu thuật giải từ bài báo “An Elastic Approximate Similarity
Search in Very Large Datasets with MapReduce” của các tác giả (Phan et al., 2014),
từ đó cải tiến thuật giải này.
- Tiến hành thí nghiệm và đánh giá thuật giải được đề xuất theo mô hình
MapReduce.
1.5 Ý nghĩa của đề tài
Kết quả về lý thuyết: thuật giải tìm kiếm tương tự với mô hình MapReduce được
cải tiến. Thông qua đó, người thực hiện đề tài có kiến thức về các lý thuyết và kỹ
thuật cũng như phương pháp liên quan. Cụ thể một số điểm chính như:
- Hiểu và nắm bắt vai trò của tác vụ tìm kiếm tương tự
- Mô hình và cách thức hoạt động của MapReduce
- Nắm bắt các kỹ thuật cơ bản trong việc xử lý ngôn ngữ tự nhiên và các đối
tượng tài liệu văn bản
- Cách thức giao tiếp và triển khai mô hình MapReduce với framework
Hadoop dùng Python.
- Các kiến thức về lý thuyết sẽ được vận dụng trong quá trình phân tích và hiện
thực hóa thuật giải được đề xuất.
Kết quả về sản phẩm: Thí nghiệm đánh giá tương ứng cho thuật giải được đề
xuất.


5


CHƯƠNG 2:

CƠ SỞ LÝ THUYẾT

2.1 Tìm kiếm tương tự
Tìm kiếm tương tự là bài toán tìm kiếm các đối tượng tương tự nhau. Tác vụ
tìm kiếm tương tự là sự kết hợp giữa hai từ khóa “tìm kiếm” và “tương tự”. Trong
đó, “tìm kiếm” là tác vụ cơ bản trong khoa học máy tính mà mục tiêu của nó là tìm
kiếm câu trả lời cho các truy vấn được cung cấp. Ngày nay, hầu hết các đối tượng đều
được số hóa và lưu trữ trong máy tính. Do đó, tác vụ tìm kiếm trở nên phổ biến và
được sử dụng rộng rãi. Khi hai khái niệm “tìm kiếm” và “tương tự” được kết hợp với
nhau, chúng tạo nên tác vụ tìm kiếm tương tự. Ví dụ như các bộ máy tìm kiếm của
Google, Yahoo, hoặc Bing minh họa cho tác vụ tìm kiếm tương tự dựa trên từ khóa
truy vấn của người dùng. Mặt khác, tác vụ tìm kiếm tương tự cũng được áp dụng rộng
rãi trong nhiều ngành, nhiều lĩnh vực, ví dụ như gom cụm dữ liệu, phân lớp dữ liệu,
khai phá dữ liệu, hệ thống hỗ trợ ra quyết định.
Định nghĩa không gian khoảng cách (không gian “metric”) được giới thiệu trong
công trình nghiên cứu (Zezula et al., 2010). Không gian này là một tập hợp các khái
niệm khoảng cách giữa các phần tử của một tập hợp. Gọi d là hàm đo lường khoảng
cách, đặc trưng của một không gian khoảng cách bao gồm bốn điều kiện chính sau:
- Điều kiện không âm: ∀𝑥, 𝑦, 𝑑 (𝑥, 𝑦) ≥ 0
- Điều kiện trùng nhau: ∀𝑥, 𝑦, 𝑥 = 𝑦 ⇔ 𝑑 (𝑥, 𝑦) = 0
- Điều kiện đối xứng: ∀𝑥, 𝑦, 𝑑 (𝑥, 𝑦) = 𝑑(𝑦, 𝑥)
- Điều kiện bất đẳng thức tam giác: ∀𝑥, 𝑦, 𝑧, 𝑑 (𝑥, 𝑧) ≤ 𝑑 (𝑥, 𝑦) + 𝑑(𝑦, 𝑧)
Có nhiều biến thể của tác vụ tìm kiếm tương tự, trong đó hai biến thể phổ biến
nhất là tìm kiếm tương tự theo phạm vi (range search) và tìm kiếm tương tự k láng
giềng gần nhất (k-nearest neighbor search). Hai biến thể này được mô tả như sau:
- Tìm kiếm tương tự theo phạm vi (range search): cho trước một đối tượng truy
vấn q và giá trị phạm vi r, tác vụ tìm kiếm tương tự sẽ tìm tất cả các đối tượng dữ liệu

o trong không gian tìm kiếm sao cho d(o, q) ≤ r.
- Tìm kiếm tương tự k láng giềng gần nhất (k-nearest neighbor search): cho
trước một đối tượng truy vấn q và giá trị thông số k, tác vụ tìm kiếm tương tự sẽ tìm
tất cả các đối tượng dữ liệu o trong không gian tìm kiếm sao cho lượng số của tập o


6
là k và d(o, q) ≤ d(x, q), với x là các đối tượng còn lại trong không gian tìm kiếm
mà không nằm trong tập o.

Hình 2-1: Hai ví dụ biến thể phổ biến của tìm kiếm tương tự; a) tìm kiếm tương tự
theo phạm vi r; b) tìm kiếm 3 đối tượng gần nhất với truy vấn q
Hình 2-1 minh họa hai biến thể phổ biến của tác vụ tìm kiếm tương tự. Trong
đó, Hình 2-1a trả về đối tượng o3, o4, o5 trong phạm vi bán kính r từ đối tượng truy
vấn q. Mặt khác, Hình 2-1b trả về 3 đối tượng gần nhất với truy vấn q là o3, o4, o5.
Để đo lường giá trị khoảng cách, có nhiều phương pháp đo lường được đề xuất.
Trong đó, khoảng cách Euclidean là được biết đến nhiều nhất. Cho hai điểm p và q
trong không gian Euclidean hai chiều, sao cho p(p1, p2) và q(q1, q2), khoảng cách d(p,
q) được tính bằng công thức (2-1) như sau:
𝑑 (𝑝, 𝑞) =

(𝑞 − 𝑝 ) + (𝑞 − 𝑝 )

(2-1)

Để tổng quát hóa không gian véc tơ n chiều bậc 𝜌, tác giả Minkowski
(Minkowski, 1953) đưa ra một công thức (2-2) tổng quát như sau:
𝑑 𝐷 ,𝐷

=


∑

𝐷 [𝑖 ] − 𝐷 [𝑖 ]

(2-2)

Trong đó, 𝜌 là bậc của không gian khoảng cách. Nếu 𝜌 = 2 thì ta có không gian
Euclidean như công thức (2-1). Trong trường hợp hai đối tượng dữ liệu là chuỗi nhị

phân, tác giả Hamming đề xuất khoảng cách Hamming (Hamming, 1950) được tính
bằng công thức (2-3) như sau:
𝑑 (𝑝, 𝑞) = ∑ 𝑝[𝑖] 𝑋𝑂𝑅 𝑞 [𝑖]

(2-3)


7
Trong trường hợp hai đối tượng là chuỗi, tác giả Levenshtein đề xuất khoảng
cách Levenshtein (Levenshtein, 1965). Theo đó, khoảng cách giữa hai chuỗi s và t là
số bước ít nhất để biến đổi chuỗi s thành chuỗi t thông qua ba phép biến đổi sau:
- Xóa một ký tự
- Thêm một ký tự
- Thay một ký tự này bằng một ký tự khác
Trong trường hợp hai đối tượng là véc tơ n chiều, khoảng cách Cosine (Singhal,
2001) của hai véc tơ là 𝑐𝑜𝑠(), với  là hệ số góc giữa hai véc tơ. Khoảng cách này
được đề xuất theo công thức (2-4) như sau:
∑

𝑐𝑜𝑠() =

∑

[ ]× [ ]

( [ ]) × ∑

(2-4)
( [ ])

Trong trường hợp hai đối tượng là hai tập hợp, tác giả Jaccard đề xuất hệ số
tương quan Jaccard (Jaccard, 1912). Hệ số này giữa hai tập hợp A và B được tính
theo công thức (2-5) như sau:
‖ ∩ ‖

𝑑 (𝐴, 𝐵) = 1 − ‖

∪ ‖

(2-5)

2.2 Mô hình hóa đối tượng tài liệu
Thông thường, các đối tượng tài liệu sẽ được mô hình hóa dưới dạng các véc tơ
nhiều chiều. Ví dụ đối tượng tài liệu Di chứa đoạn văn bản “today is not a bad day,
is it?” sẽ được mô hình hóa thành véc tơ Di 8 chiều Di(today, is, not, a, bad, day, is,
it), trong đó mỗi chiều là một từ vựng tương ứng trong đoạn văn bản.
Mặt khác, đối tượng tài liệu có thể được biểu diễn dưới dạng tập hợp. Ví dụ tài
liệu Di chứa đoạn văn bản “today is not a bad day, is it?” sẽ được mô hình hóa thành
tập hợp Di = {today, is, not, a, bad, day, it}. Trong trường hợp này, số phần tử của
tập hợp Di là 7.
Một cách khác dùng để mô hình hóa đối tượng tài liệu là dùng cụm từ liên tiếp

nhau theo khái niệm k-shingle (Rajaraman & Ullman, 2011), tức là k chuỗi con bất
kỳ được tìm thấy trong tài liệu. Ví dụ tài liệu Di chứa đoạn văn bản “today is not a
bad day, is it?” sẽ được mô hình hóa thành tập hợp 2-shingle Di = {todayis, isnot,
nota, abad, badday, dayis, isit}. Trong trường hợp này, số phần tử của tập hợp Di là
7.


8
2.3 Mô hình MapReduce
Hai tác giả Dean và Ghemawat đề xuất ra mô hình MapReduce để hỗ trợ các
tác vụ chuyên biệt trong môi trường phân bố mà không cần phải quan tâm nền tảng
song song hóa bên dưới (Dean & Ghemawat, 2008). Ý tưởng cơ bản của mô hình
MapReduce xuất phát từ chiến lược “chia để trị”, tức là một bài toán lớn cần giải
quyết sẽ được chia nhỏ thành các bài toán con, và mỗi bài toán con này sẽ được xử
lý trên nhiều máy tính khác nhau.
Để sử dụng mô hình này, người sử dụng chỉ cần định nghĩa tác vụ Map và
Reduce trong một công việc MapReduce (MapReduce job). Mô hình MapReduce sẽ
được triển khai trên một hệ thống máy cụm (cluster) bao gồm nhiều máy tính khác
nhau. Trong đó có một máy sẽ đảm nhận vai trò là máy chủ “master”, những máy còn
lại sẽ đóng vai trò là máy trạm “worker”. Máy chủ sẽ phân chia các tác vụ Map và
Reduce cho các máy trạm rảnh rỗi trong hệ thống máy cụm.
Tổng quan thực thi mô hình MapReduce được minh họa ở Hình 2-2. Các bước
thực hiện chính được mô tả như sau:
- Bước 1: Người dùng đặc tả hai tác vụ Map và Reduce trong User Program.
- Bước 2: Máy chủ “Master” chịu trách nhiệm trong việc gán tác vụ Map và
Reduce cho các worker.
- Bước 3: Các máy trạm thực hiện tác vụ Map sẽ đọc dữ liệu đầu vào.
- Bước 4: Sau khi thực hiện xong tác vụ Map, các dữ liệu trung gian sẽ được
ghi vào bộ nhớ cục bộ tương ứng ở mỗi máy trạm.
- Bước 5: Các máy trạm thực hiện tác vụ Reduce sẽ lấy dữ liệu trung gian và

thực thi hàm chức năng Reduce.
- Bước 6: Kết quả tổ hợp từ tác vụ Reduce sẽ được ghi lại vào hệ thống lưu trữ
phân bố.
Mô hình MapReduce tổ chức dữ liệu dưới dạng các cặp key-value. Ngoài ra,
Hadoop1 là framework hiện thực mô hình MapReduce được sử dụng rộng rãi.

1




9

Hình 2-2: Tổng quan thực thi mô hình MapReduce (Dean & Ghemawat, 2008)
2.4 Hadoop Framework
Hadoop là một framework mã nguồn mở được viết bằng Java để hiện thực hóa
mô hình MapReduce. Hadoop cho phép xử lý dữ liệu trong môi trường song song và
phân tán trên các cụm máy tính.
Hadoop framework được cấu tạo bởi 4 mô đun chính sau:
- Hadoop Common: chứa các thư viện và các tiện ích cần thiết cho các mô đun
khác, bao gồm cả các mã lệnh để khởi động Hadoop.
- Hadoop YARN: quản lý tiến trình và tài nguyên của các cụm máy tính.
- Hadoop Distributed File System (HDFS): hệ thống file phân tán cho dữ liệu
lưu trữ trên cụm máy tính.
- Hadoop MapReduce: xử lý dữ liệu theo mô hình MapReduce.


10

Hình 2-3: Kiến trúc tổng quan của Hadoop với 4 mô đun chính

Để cài đặt Hadoop framework, các máy tính phải được cài đặt máy ảo JAVA.
Sau khi cài đặt phiên bản Hadoop framework, các cấu hình chính cần thiết được liệt
kê như được minh họa ở Bảng 2-1.
Bảng 2-1: Liệt kê các file chính cần cấu hình trong Hadoop framework
STT

Tên File

Mô tả

1

hdfs-site.xml

Cấu hình đường dẫn cho lưu trữ dữ liệu
trong hệ thống file phân tán Hadoop.


11
2

core-site.xml

Cấu hình định dạng tài nguyên thống
nhất (URI) và địa chỉ IP của máy tính.

3

yarn-site.xml


Cấu hình các thông số cho mô đun
YARN.

4

hadoop-env.sh

Cấu hình đường dẫn máy ảo JAVA.

5

slaves

Cấu hình các địa chỉ IP máy tính trong
cụm máy tính

6

mapred-site.xml

Cấu hình các thông số liên quan đến
công việc MapReduce

Ngoài ra, hệ thống cần được cấu hình SSH để các máy tính trong cụm kết nối
và giao tiếp với nhau một cách tự động không cần yêu cầu xác thực cho mỗi lần kết
nối.
2.5 Hadoop Streaming
Hadoop Streaming2 là API tổng quát cho phép người lập trình hiện thực tác vụ
Map và Reduce bằng bất kỳ ngôn ngữ nào và giao tiếp với Hadoop framework. Các
máy tính thực thi tác vụ Map và Reduce sẽ nhận dữ liệu từ đầu vào chuẩn (stdin) và

xuất dữ liệu ra đầu xuất chuẩn (stdout), với dữ liệu được định dạng theo cặp khóa-giá
trị (key-value). Như vậy, đầu vào và đầu ra luôn được biểu diễn dưới dạng text, và
một khoảng cách tab được dùng để ngăn cách khóa và giá trị, ví dụ như:
key1 \t value1 \n
key2 \t value2 \n
key3 \t value3 \n
…
keyN \t valueN \n
Một quy trình Streaming được minh họa ở Hình 2-4. Đầu vào của tác vụ Map
và tác vụ Reduce từ stdin, trong khi đầu ra của tác vụ Map và tác vụ Reduce là ở

2

/>

12
stdout. Mỗi máy tính được gán thực thi tác vụ Map gọi là mapper, trong khi mỗi máy
tính được gán thực thi tác vụ Reduce, gọi là reducer.

Hình 2-4: Dòng chảy của Hadoop Streaming
Các thông số cho Hadoop Streaming được mô tả ở Bảng 2-2. Tùy vào nhu cầu
sử dụng mà các thông số này sẽ được cung cấp các giá trị tương ứng.
Bảng 2-2: Thông số của Hadoop Streaming
STT
1
2

Thông Số

Bắt Buộc?


Mô Tả

-input directoryname Có

Chỗ lưu trữ dữ liệu đầu vào cho

or filename

mapper

-output

Có

Chỗ lưu trữ dữ liệu đầu ra cho reducer

directoryname
3

-mapper executable Có

Hàm thực thi tác vụ Map

or JavaClassName
4

-reducer executable Có

Hàm thực thi tác vụ Reduce


or JavaClassName
5

-file filename

Không

Làm cho sự thực thi của mapper,
reducer, or combiner sẵn sàng cục bộ
trên các máy tính trong cụm


13
STT
6

Thông Số
-inputformat

Bắt Buộc?
Không

JavaClassName

Mô Tả
Class được chỉ định để trả về cặp khóagiá trị của class Text. Nếu như không
được chỉ định, TextInputFormat sẽ
được sử dụng mặc định.


7

-outputformat

Không

JavaClassName

Class được chỉ định để nhận cặp khóagiá trị của class Text. Nếu như không
được chỉ định, TextOutputformat sẽ
được sử dụng mặc định.

8

-partitioner

Không

JavaClassName
9

10

-combiner

nào mà một khóa được gửi đến.
Không

Hàm thực thi Combiner executable


streamingCommand

cho các cặp khóa-giá trị trung gian từ

or JavaClassName

tác vụ Map.

-cmdenv

Không

name=value
11

Class được dùng để xác định reducer

-inputreader

Truyền biến môi trường cho các lệnh
streaming.

Không

Xác định lớp đọc dữ liệu thay vì lớp
định dạng dữ liệu đầu vào.

12

-verbose


Không

Verbose output

13

-lazyOutput

Không

Tạo ra đầu ra một cách “lười biếng”.
Tức là nếu định dạng đầu ra dựa trên
FileOutputFormat, file output sẽ được
tạo ra chỉ khi có lần gọi đầu tiên đến
Context.write.

14

-numReduceTasks

Không

Chỉ định số lượng reducers

15

-mapdebug

Không


Kịch bản để gọi khi tác vụ Map thực
thi không thành công

16

-reducedebug

Không

Kịch bản để gọi khi tác vụ Reduce thực
thi không thành công


14
Với Hadoop Streaming, người lập trình không nhất thiết phải viết chương trình
Java tích hợp vào Hadoop. Thay vào đó, người lập trình có thể đặc tả hàm Map và
Reduce dưới dạng các script và chỉ định đường dẫn đến các script này tương ứng với
các thông số của Hadoop Streaming. Trong luận văn, chúng tôi sử dụng ngôn ngữ lập
trình Python để đặc tả script cho tác vụ Map và Reduce. Hai tác vụ này sẽ tương tác
với Hadoop thông qua các API của Hadoop Streaming.
2.6 Ngôn ngữ lập trình Python
Python3 là ngôn ngữ lập trình thông dịch ra đời vào năm 1990. Ngôn ngữ này
được đánh giá là có hình thức sáng sủa và rõ ràng, thuận lợi cho người mới bắt đầu
lập trình. Triết lý của Python được trình bày trong tài liệu (Tim, 2004), trong đó các
lợi điểm khi sử dụng Python được tóm tắt lại như sau:
- Python được thiết kế dễ học, dễ đọc, bố cục trực quan, và dễ hiểu.
- Python sử dụng hệ thống kiểu dữ liệu tự động xác định kiểu. Tức là Python
không kiểm tra kiểu dữ liệu tại thời điểm dịch, mà chỉ kiểm tra tại thời điểm thực thi.
- Python cho phép chia các chương trình thành các mô đun, và các mô đun này

có thể được tái sử dụng lại cho các chương trình khác.
- Python cho phép người lập trình sử dụng nhiều phương pháp lập trình khác
nhau như hướng đối tượng, cấu trúc, chức năng.
- Python có thể được mở rộng như mở rộng chức năng của trình thông dịch,
liên kết các chương trình của Python với các thư viện ở dạng nhị phân, liên kết trình
thông dịch của Python với các ứng dụng viết bằng C.
- Python sử dụng trình thông dịch nên giúp tiết kiệm thời gian phát triển ứng
dụng
- Python có thể được viết từ những ngôn ngữ khác như CPython cho ngôn ngữ
C, Jython cho ngôn ngữ Java, và IronPython cho môi trường .NET.
- Python là một ngôn ngữ lập trình đơn giản nhưng hiệu quả.
- Python là một ngôn ngữ lập trình cấp cao đáp ứng phần lớn yêu cầu của lập
trình viên.

3

/>

15
Với những ưu điểm như vậy, Python trở thành một ngôn ngữ kịch bản tương tác
với Hadoop framework thông qua API Hadoop Streaming. Một ví dụ giao tiếp với
Hadoop thông qua Python được minh họa như sau:
$ $HADOOP_HOME/bin/hadoop jar contrib/streaming/hadoop-streaming-1.2.1.jar \
-input input_dirs \
-output output_dir \
-mapper -reducer
Trong ví dụ trên, các hàm cho tác vụ Map và Reduce là những Python scripts
đọc dữ liệu đầu vào từ stdin và xuất dữ liệu ra stdout. Hadoop Streaming sẽ tạo ra

một MapReduce job cho cụm máy tính đang chạy tương ứng, thực thi MapReduce
job, và giám sát tiến trình của các công việc này cho đến khi nó kết thúc.
Đối với Python script cho tác vụ Map, mỗi máy tính được gán thực thi tác vụ
này, gọi là mapper, đều kích hoạt Python script tương ứng. Khi tác vụ Map được thực
thi, dữ liệu đầu vào được phân tách thành các dòng và chuyển đến cho stdin. Tiếp
đến, các mappers này sẽ xử lý quy trình nghiệp vụ như được lập trình trong file Python
script. Kết quả đầu ra của tác vụ Map sẽ được đẩy ra cho stdout.
Một cách tương tự đối với Python script cho tác vụ Reduce, mỗi máy tính được
gán thực thi tác vụ này, gọi là reducer, đều kích hoạt Python script tương ứng. Khi
tác vụ Reduce được thực thi, dữ liệu đầu vào được phân tách thành các dòng và
chuyển đến cho stdin. Tiếp đến, các reducers này sẽ xử lý quy trình nghiệp vụ như
được lập trình trong file Python script. Kết quả đầu ra của tác vụ Reduce sẽ được đẩy
ra cho stdout.