ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
********

NGUYỄN THÀNH PHƯƠNG

CÁC THUẬT TOÁN KHAI PHÁ DỮ LIỆU ỨNG DỤNG TRONG
HỆ THỐNG PHÂN TÁN LỚN

KHÓA LUẬN CAO HỌC
NGÀNH KHOA HỌC MÁY TÍNH
Mã số: 60480101

TP. HỒ CHÍ MINH - 2015


ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
********

NGUYỄN THÀNH PHƯƠNG

CÁC THUẬT TOÁN KHAI PHÁ DỮ LIỆU ỨNG DỤNG TRONG
HỆ THỐNG PHÂN TÁN LỚN

KHÓA LUẬN CAO HỌC
NGÀNH KHOA HỌC MÁY TÍNH

Mã số: 60480101

NGƯỜI HƯỚNG DẪN KHOA HỌC

PGS.TS NGUYỄN PHI KHỨ

TP HỒ CHÍ MINH – NĂM 2015


LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi.
Các số liệu, kết quả thực nghiệm nêu trong khóa luận là trung thực và chưa từng
được ai công bố trong bất kỳ công trình nào khác.

Tác giả

Nguyễn Thành Phương


MỤC LỤC
CHƯƠNG 1: TỔNG QUAN ........................................................................................ 4
1.1 Mục tiêu và tính cần thiết của đề tài ................................................................. 4
1.2 Tổng quan tình hình nghiên cứu ....................................................................... 5
1.2.1
1.2.2
1.2.3
1.2.4
1.2.5
1.2.6
1.2.7

Tổng quan về khai phá dữ liệu ................................................................... 5
Các hướng tiếp cận và các kỹ thuật chính trong Khai phá dữ liệu............. 5
Các vấn đề trong khai phá dữ liệu .............................................................. 6

Tính khoa học và tính mới của đề tài ......................................................... 8
Mục tiêu, đối tượng và phạm vi nghiên cứu .............................................. 9
Nội dung, phương pháp dự định nghiên cứu............................................ 10
Phương pháp nghiên cứu .......................................................................... 11

CHƯƠNG 2: THUẬT TOÁN SONG SONG VỚI DỮ LIỆU LỚN ....................... 13
2.1 Thuật toán song song ...................................................................................... 13
2.1.1
2.1.2
2.1.3
2.1.4
2.2

Khái niệm ................................................................................................. 13
Tính cần thiết của xử lý song song........................................................... 13
Phân loại hệ thống tính toán song song .................................................... 14
Tiêu chí của thuật toán song song ............................................................ 15

Môi trường phân tán ....................................................................................... 15

CHƯƠNG 3: HIỆN THỰC CÁC THUẬT TOÁN SONG SONG ......................... 16
3.1 Dijkstra............................................................................................................ 16
3.1.1
3.1.2
3.1.3
3.1.4
3.2

K-means .......................................................................................................... 20


3.2.1
3.2.2
3.2.3
3.2.4
3.3

Giới thiệu ................................................................................................. 16
Thuật toán tuần tự .................................................................................... 16
Thuật toán song song ............................................................................... 19
Nhận xét ................................................................................................... 20
Giới thiệu ................................................................................................. 20
Thuật toán tuần tự .................................................................................... 21
Thuật toán song song ............................................................................... 21
Nhận xét ................................................................................................... 22

Apriori ............................................................................................................. 22

3.3.1
3.3.2
3.3.3
3.3.4
3.3.5

Giới thiệu ................................................................................................. 22
Thuật toán tuần tự .................................................................................... 24
Các nghiên cứu thuật toán song song liên quan ....................................... 25
Giải thuật song song đề xuất .................................................................... 27
Nhận xét ................................................................................................... 31

1



3.4

Tổng quan công nghệ, khả năng tích hợp, mở rộng ....................................... 32

CHƯƠNG 4: CHẠY THỬ VÀ ĐÁNH GIÁ CÁC THUẬT TOÁN ....................... 35
4.1 Dijkstra............................................................................................................ 35
4.2 K-means .......................................................................................................... 36
4.3 Apriori ............................................................................................................. 38
CHƯƠNG 5: KẾT LUẬN.......................................................................................... 41
5.1 Kết quả khóa luận ........................................................................................... 41
5.2 Hạn chế ........................................................................................................... 41

2


DANH MỤC HÌNH VẼ

Hình 3.1: Kết quả tính toán được trên đồ thị ................................................................ 17
Hình 3.2: Quá trình loại bỏ phần tử không phổ biến của giải thuật ODAM ................ 29
Hình 3.3: Cấu trúc lưu trữ dữ liệu thông thường (row-wise) ....................................... 30
Hình 3.4: Cấu trúc lưu trữ dữ liệu columnar storage.................................................... 31
Hình 3.5: Hệ thống phân tán chạy thử thuật toán Apriori ............................................ 32
Hình 3.6: Hệ thống phân tán chạy thử thuật toán K-means, Dijkstra .......................... 33
Hình 4.1: Thuật toán Dijkstra – thí nghiệm 1............................................................... 36
Hình 4.2: Thuật toán Dijkstra – thí nghiệm 2............................................................... 36
Hình 4.3: Thuật toán K-means – thí nghiệm 1 ............................................................. 37
Hình 4.4: Thuật toán K-means – thí nghiệm 2 ............................................................. 38
Hình 4.5: Thuật toán Apriori – Thí nghiệm 1 .............................................................. 39

Hình 4.6: Thuật toán Apriori – Thí nghiệm 2 .............................................................. 40

3


Chương 1: Tổng quan

CHƯƠNG 1: TỔNG QUAN
1.1 Mục tiêu và tính cần thiết của đề tài
Ngày nay trong thời đại bùng nổ của Công Nghệ Thông Tin, các hoạt động của con
người càng ngày càng được tin học hóa. Càng nhiều hoạt động trong cuộc sống
hàng ngày của con người đang dần được chuyển sang một hình thức lưu trữ mới đó
là kĩ thuật số.
Với sự bùng nổ của khối lượng thông tin đó, khai phá dữ liệu là một lĩnh vực mang
lại hiệu quả thiết thực cho con người. Khai phá dữ liệu đã giúp người sử dụng thu
được những tri thức hữu ích từ những cơ sở dữ liệu hoặc các kho dữ liệu khổng lồ.
Cơ sở dữ liệu trong các đơn vị, tổ chức kinh doanh, quản lý khoa học chứa đựng
nhiều thông tin tiềm ẩn, phong phú và đa dạng, đòi hỏi phải có những phương pháp
nhanh, phù hợp chính xác, hiệu quả để lấy được những thông tin bổ ích.
Khai phá dữ liệu luôn là một đề tài nóng của lĩnh vực khoa học máy tính, đặc biệt
hơn do tính chất toàn cầu và rộng lớn của các hệ thống công nghệ thông tin trong
thế giới hiện đại, khi mà dữ liệu được lưu trữ một cách phân tán thì khai phá dữ liệu
càng gặp phải nhiều thách thức khó khăn cần giải quyết.
Do đó, đề tài này hướng đến vấn đề nghiên cứu các thuật toán quan trọng trong lĩnh
vực khai phá dữ liệu trên môi trường các hệ thống phân tán với lượng dữ liệu lớn.
Cụ thể hơn, đề tài sẽ hiện thực các thuật toán khai phá dữ liệu trong các môi trường
phân tán, đề xuất các cải tiến để tối ưu thuật toán này, xây dựng mô hình dữ liệu,
mô hình kĩ thuật theo các tiêu chuẩn của các tổ chức kĩ thuật trên thế giới để đảm
bảo bản hiện thực này có thể tiếp tục phát triển và tích hợp vào các sản phẩm thực
tế. Các thuật toán sẽ được hiện thực trong đề tài này: thuật toán phân cụm k-Means,

thuật toán khai thác luật kết hợp Apriori, thuật toán trong khai phá dữ liệu đồ thị tìm đường đi ngắn nhất Dijkstra.

4


Chương 1: Tổng quan

1.2 Tổng quan tình hình nghiên cứu
1.2.1 Tổng quan về khai phá dữ liệu
Khai phá dữ liệu là một bước của quá trình khai thác tri thức (Knowledge Discovery
Process), bao gồm các bước sau:
• Trích chọn dữ liệu (data selection): là bước trích chọn những tập dữ liệu cần được
khai phá từ các tập dữ liệu lớn (databases, data warehouses, data repositories) ban
đầu theo một số tiêu chí nhất định.
• Tiền xử lý dữ liệu (data preprocessing): là bước làm sạch dữ liệu (xử lý với dữ liệu
không đầy đủ, dữ liệu nhiễu, dữ liệu không nhất quán, .v.v.), rút gọn dữ liệu (sử
dụng hàm nhóm và tính tổng, các phương pháp nén dữ liệu, sử dụng histograms, lấy
mẫu, .v.v.), rời rạc hóa dữ liệu (rời rạc hóa dựa vào histograms, dựa vào entropy,
dựa vào phân khoảng, .v.v.). Sau bước này, dữ liệu sẽ nhất quán, đầy đủ, được rút
gọn, và được rời rạc hóa.
• Biến đổi dữ liệu (data transformation): đây là bước chuẩn hóa và làm mịn dữ liệu
để đưa dữ liệu về dạng thuận lợi nhất nhằm phục vụ cho các kỹ thuật khai phá ở
bước sau.
• Khai phá dữ liệu (data mining): đây là bước áp dụng những kỹ thuật khai phá
(phần nhiều là các kỹ thuật của machine learning) để khai phá, trích chọn được
những mẫu (patterns) thông tin, những mối liên hệ (relationships) đặc biệt trong dữ
liệu. Đây được xem là bước quan trọng và tốn nhiều thời gian nhất của toàn quá
trình KDD.
1.2.2 Các hướng tiếp cận và các kỹ thuật chính trong Khai phá dữ liệu
Các hướng tiếp cận của Khai phá dữ liệu có thể được phân chia theo chức năng hay

lớp các bài toán khác nhau. Sau đây là một số hướng tiếp cận chính:
 Phân lớp và dự đoán (classification & prediction): xếp một đối tượng vào
một trong những lớp đã biết trước. Phân lớp là bài toán thông dụng nhất
trong Khai phá dữ liệu. Với một tập các dữ liệu huấn luyện cho trước và sự
huấn luyện của con người, các giải thuật phân loại sẽ học ra bộ phân loại

5


Chương 1: Tổng quan

(classifier) dùng để phân các dữ liệu mới vào một trong những lớp (còn gọi
là loại) đã được xác định trước. Nhận dạng cũng là một bài toán thuộc kiểu
Phân lớp. Ví dụ: phân lớp vùng địa lý theo dữ liệu thời tiết. Hướng tiếp cận
này thường sử dụng một số kỹ thuật của machine learning như cây quyết
định (decision tree), mạng nơron nhân tạo (neural network), .v.v. Phân lớp
còn được gọi là học có giám sát (học có thầy – supervised learning).
 Luật kết hợp (association rules): Các giải thuật Tìm luật kết hợp tìm kiếm
các mối liên kết giữa các phần tử dữ liệu, ví dụ như nhóm các món hàng
thường được mua kèm với nhau trong siêu thị. Luật kết hợp được ứng dụng
nhiều trong lĩnh vực kinh doanh, y học, tin-sinh, tài chính & thị trường
chứng khoán, .v.v.
 Khai phá chuỗi theo thời gian (sequential/temporal patterns): tương tự như
khai phá luật kết hợp nhưng có thêm tính thứ tự và tính thời gian. Hướng tiếp
cận này được ứng dụng nhiều trong lĩnh vực tài chính và thị trường chứng
khoán vì nó có tính dự báo cao.
 Phân cụm (clustering/segmentation): xếp các đối tượng theo từng cụm (số
lượng cũng như tên của cụm chưa được biết trước. Phân cụm còn được gọi là
học không giám sát (học không có thầy – unsupervised learning).
 Mô tả khái niệm (concept description & summarization): thiên về mô tả, tổng

hợp và tóm tắt khái niệm. Ví dụ: tóm tắt văn bản.
1.2.3 Các vấn đề trong khai phá dữ liệu
a. Các dạng dữ liệu có thể khai phá
Do Khai phá dữ liệu được ứng dụng rộng rãi nên nó có thể làm việc với rất nhiều
kiểu dữ liệu khác nhau. Sau đây là một số kiểu dữ liệu điển hình.
 CSDL quan hệ (relational databases)
 CSDL đa chiều (multidimensional structures, data warehouses)
 CSDL dạng giao dịch (transactional databases)

6


Chương 1: Tổng quan

 CSDL quan hệ - hướng đối tượng (object-relational databases)
 Dữ liệu không gian và thời gian (spatial and temporal data)
 Dữ liệu chuỗi thời gian (time-series data)
 CSDL đa phương tiện (multimedia databases) như âm thanh (audio), hình
 Ảnh (image), phim ảnh (video), .v.v.
 Dữ liệu Text và Web (text database & www)
Khai phá dữ liệu tuy là một lĩnh vực mới nhưng thu hút được rất nhiều sự quan tâm
của các nhà nghiên cứu nhờ vào những ứng dụng thực tiễn của nó. Chúng ta có thể
liệt kê ra đây một số ứng dụng điển hình:
 Phân tích dữ liệu và hỗ trợ ra quyết định (data analysis & decision support).
Điều trị y học (medical treatment): mối liên hệ giữa triệu chứng, chẩn đoán
và phương pháp điều trị (chế độ dinh dưỡng, thuốc men, phẫu thuật …).
 Text mining & Web mining: phân lớp văn bản và các trang web, tóm tắt văn
bản, .v.v.
 Tin-sinh (bio-informatics): tìm kiếm, đối sánh các hệ gene và thông tin di
truyền, mối liên hệ giữa một số hệ gene và một số bệnh di truyền, .v.v.

 Tài chính và thị trường chứng khoán (finance & stock market): phân tích tình
hình tài chính và dự báo giá của các loại cổ phiếu trong thị trường chứng
khoán, .v.v.
Khai phá dữ liệu là một lĩnh vực mới, do đó đang còn rất nhiều vấn đề chưa được
nghiên cứu một cách trọn vẹn. Sau đây là một số hướng nghiên cứu đã và đang thu
hút được sự chú ý của các nhà tin học.
 OLAM (Online Analytical Mining) - Sự tích hợp giữa CSDL, kho dữ liệu và
Khai phá dữ liệu. Hiện nay một số hệ quản trị CSDL như Oracle, MS SQL
Server, DB2 đã tích hợp tính năng xây dựng kho dữ liệu và phân tích trực
tuyến (OLAP).
 Khám phá được nhiều dạng tri thức khác nhau từ nhiều kiểu dữ liệu.
7


Chương 1: Tổng quan

 Tính hiệu quả, tính chính xác, độ phức tạp tính toán, khả năng mở rộng và
tích hợp, xử lý nhiễu và dữ liệu không đầy đủ, tính hữu dụng (ý nghĩa) của tri
thức.
 Kết hợp Khai phá dữ liệu với tri thức cơ sở (background knowledge).
 Vấn đề song song hóa và phân tán quá trình Khai phá dữ liệu.
 Ngôn ngữ truy vấn trong Khai phá dữ liệu (Data Mining Query Language –
DMQL): cung cấp cho người sử dụng một ngôn ngữ hỏi thuật tiện tương tự
như SQL đối với CSDL quan hệ.
 Biểu diễn và trực quan hóa tri thức khai phá được sao cho gần gũi với người
sử dụng (human-readable expression). Tri thức có thể biểu diễn đa chiều, đa
tầng để người dùng sử dụng tri thức hiệu quả hơn.
1.2.4 Tính khoa học và tính mới của đề tài
Các nguồn cơ sở dữ liệu lớn và phân tán rộng khắp trên nhiều địa điểm khác nhau
đang ngày càng trở nên thông dụng trong nền công nghệ thông tin hiện đại. Các

nguồn cơ sở dữ liệu này ban đầu chứa một lượng dữ liệu không quá lớn, được lưu
theo kiến trúc tập trung, nhưng sau đó do yêu cầu phát triển của hệ thống, các dữ
liệu này ngày càng lớn và có thể phân tán rộng ra khắp nơi.
Công nghệ tính toán đã dẫn tới việc phân tán nguồn dữ liệu như là một tất yếu. Và
cùng với nó là sự phát triển của các thuật toán khai phá dữ liệu phân tán. Mặc dù đã
có một số thuật toán khai phá luật kết hợp trong cơ sở dữ liệu phân tán được đề
xuất, nhưng để đáp ứng được các nhu cầu ngày càng cao: thời gian xử lý nhanh, xử
lý trên các CSDL phân tán lớn … thì vẫn đòi hỏi phải có các thuật toán nhanh và
mạnh hơn. Và chính vì vậy hướng nghiên cứu khai phá luật kết hợp trong môi
trường phân tán vẫn là một hướng nghiên cứu thú vị và thực tế, kèm theo đó là rất
nhiều vấn đề khó khăn cần giải quyết.
Có năm cách tiếp cận cơ bản để thực hiện thuật toán trong một môi trường dữ liệu
phân tán, được GL Grossman et al. công bố trong công trình của ông, đó là:

8


Chương 1: Tổng quan

1. Chuyển đổi dữ liệu thành sao cho có thể lưu trữ thích hợp trong bộ nhớ máy tính:
Có bốn biến thể cơ bản của phương pháp này, cụ thể là lấy mẫu (namely sampling),
lựa chọn tính năng (feature selection), phân vùng (partition) và tổng hợp dữ liệu
(data summarization).
2. Giảm thời gian truy cập: Cách tiếp cận này sẽ cố gắng để làm giảm thời gian truy
cập dữ liệu trong bộ nhớ bằng cách sử dụng cấu trúc dữ liệu chuyên dụng để truy
cập dữ liệu trên đĩa như B + cây và sử dụng một số kỹ thuật như khối song song
đọc.
3. Sử dụng nhiều bộ xử lý: Có hai kỹ thuật cơ bản được sử dụng để tăng tốc độ
thuật toán: xử lý tác vụ song song (task parallelism) & xử lý dữ liệu song song (data
parallelism)

4. Tính toán sẵn: Nó bao gồm tính toán sẵn các bước phức tạp của thuật toán nếu có
thể
5. Giảm nhỏ dữ liệu: các kĩ thuật để làm giảm kích thước của dữ liệu nhưng vẫn
đảm bảo toàn vẹn các thông tin cần thiết cho thuật toán như: data smoothing, data
compression, data transformation.
Đề tài này hiện thực, tối ưu các thuật toán khai phá dữ liệu trong môi trường phân
tán bằng các kĩ thuật nêu trên.
1.2.5 Mục tiêu, đối tượng và phạm vi nghiên cứu
a. Mục tiêu
 Hiện thực các thuật toán khai phá dữ liệu trong các môi trường phân tán.
 Đề xuất các cải tiến để tối ưu thuật toán này.
 Xây dựng mô hình dữ liệu, mô hình kĩ thuật theo các tiêu chuẩn của các tổ
chức kĩ thuật trên thế giới để đảm bảo bản hiện thực này có thể tiếp tục phát
triển và tích hợp vào các sản phẩm thực tế.

9


Chương 1: Tổng quan

b. Đối tượng và phạm vi nghiên cứu
Đề tài này tập trung vào nội dung nghiên cứu các thuật toán khai phá dữ liệu có sẵn,
dùng các kĩ thuật mới để xây dựng các cấu trúc dữ liệu cải tiến để thuật toán có thể
chạy trong môi trường phân tán, cũng như đề xuất các giải pháp tối ưu cho các thuật
toán nếu có thể.
Các thuật toán đề tài tập trung là: thuật toán phân cụm k-Means, thuật toán khai thác
luật kết hợp Apriori, thuật toán trong khai phá dữ liệu đồ thị - tìm đường đi ngắn
nhất Dijkstra.
Các hệ thống phân tán sẽ được xây dựng theo đúng các chuẩn hiện đại về hệ thống
phân tán, các thuật toán và bản hiện thực sẽ được đánh giá, kiểm định, so sánh trên

các hệ thống này.
1.2.6 Nội dung, phương pháp dự định nghiên cứu
a. Nội dung thực hiện
Nội dung 1: Hiện thực thuật toán gom cụm K-means trong môi trường phân tán
 Hoàn thành, kiểm định và đề xuất các cách tối ưu thuật toán.
 Phiên bản hiện thực của thuật toán được viết bằng ngôn ngữ hiện đại, tuân
theo các tiêu chuẩn kĩ thuật lớn hiện có để có thể áp dụng vào thực tế và tích
hợp với các hệ thống phân tán lớn như Hadoop, Spark, Impala, SQL Cluster
...
 Chạy thử nghiệm, so sánh kết quả với các phiên bản thuật toán cũ, chưa cải
tiến, so sánh với các phiên bản hiện thực khác.
Nội dung 2: Hiện thực thuật toán khai thác luật kết hợp Apriori trong môi
trường phân tán
 Hoàn thành, kiểm định và đề xuất các cách tối ưu thuật toán.
 Phiên bản hiện thực của thuật toán được viết bằng ngôn ngữ hiện đại, tuân
theo các tiêu chuẩn kĩ thuật lớn hiện có để có thể áp dụng vào thực tế và tích

10


Chương 1: Tổng quan

hợp với các hệ thống phân tán lớn như Hadoop, Spark, Impala, SQL Cluster
...
 Chạy thử nghiệm, so sánh kết quả với các phiên bản thuật toán cũ, chưa cải
tiến, so sánh với các phiên bản hiện thực khác.
Nội dung 3: Hiện thực thuật toán tìm đường đi ngắn nhất Dijkstra trong môi
trường phân tán.
 Hoàn thành, kiểm định và đề xuất các cách tối ưu thuật toán.
 Hiện thực thuật toán chạy một cách đúng đắn.

 Phiên bản hiện thực của thuật toán được viết bằng ngôn ngữ hiện đại, tuân
theo các tiêu chuẩn kĩ thuật lớn hiện có để có thể áp dụng vào thực tế và tích
hợp với các hệ thống phân tán lớn như Hadoop, Spark, Impala, SQL Cluster
...
 Chạy thử nghiệm, so sánh kết quả với các phiên bản thuật toán cũ, chưa cải
tiến, so sánh với các phiên bản hiện thực khác.
1.2.7 Phương pháp nghiên cứu
Đi từ việc phân tích nhu cầu thực tiễn, tìm hiểu nghiên cứu các phương pháp và kỹ
thuật đã có, trên cơ sở đó tìm cách vận dụng, phối hợp và cải tiến sao cho phù hợp
với yêu cầu thực tế của ứng dụng mà đề tài đang hướng tới. Bên cạnh đó đưa ra
những đóng góp phát triển và đề xuất mới về mặt mô hình và kỹ thuật, tận dụng ưu
điểm của từng phương pháp, kỹ thuật trong các mô hình mới với khả năng biểu diễn
mô hình tốt hơn, cải tiến các thuật toán đơn giản và hiệu quả hơn. Một số phương
pháp nghiên cứu được thực hiện trong đề tài:
Phương pháp thu thập thông tin: thu thập các tài liệu, thông tin để làm tập mẫu
khi chạy kiểm thử các thuật toán của đề tài.
Phương pháp nghiên cứu tài liệu, phân tích và tổng hợp tài liệu: nghiên cứu các
tài liệu về các thuật toán khai phá dữ liệu trong môi trường phân tán. Từ đó đề xuất
mô hình, phương pháp, kỹ thuật thích hợp để áp dụng vào đề tài.

11


Chương 1: Tổng quan

Phương pháp chuyên gia:
 Tham vấn từ các chuyên gia trong trường và các diễn đàn thuật toán trên thế
giới, từ đó hoàn thiện các giải pháp đã đề xuất.
 Tổ chức seminar với các nhóm nghiên cứu khác để lấy ý kiến đóng góp cho
việc phát triển đề tài.

Phương pháp so sánh: so sánh kết quả đạt được với các công trình liên quan.

12


Chương 2: Thuật toán song song với dữ liệu lớn

CHƯƠNG 2: THUẬT TOÁN SONG SONG VỚI DỮ LIỆU
LỚN
2.1 Thuật toán song song
2.1.1 Khái niệm
Tính toán song song hay xử lý song song là quá trình xử lý thông tin trong đó nhiều
đơn vị dữ liệu được xử lý đồng thời bởi một hay nhiều bộ xử lý để giải quyết một
bài toán.
Nói cách khác: Xử lý song song là quá trình xử lý thông tin trong đó nhiều đơn vị
dữ liệu được xử lý đồng thời bởi nhiều bộ xử lý để giải quyết một bài toán.
2.1.2 Tính cần thiết của xử lý song song
 Yêu cầu của người sử dụng:
o Cần thực hiện một khối lượng lớn công việc
o Thời gian xử lý phải nhanh
 Yêu cầu thực tế:
o Trong thực tế không tồn tại máy tính có bộ nhớ vô hạn và khả năng
tính toán vô hạn.
o Trong thực tế có nhiều bài toán mà máy tính xử lý tuần tự (XLTT)
kiểu von Neumann không đáp ứng được.
o Sử dụng hệ thống nhiều BXL để thực hiện những tính toán nhanh hơn
những hệ đơn BXL.
o Giải quyết được những bài toán lớn hơn, phức tạp hơn
Nhiều lĩnh vực mới như đồ họa máy tính, trí tuệ nhận tạo, phân tích số, v.v. đòi hỏi
phải xử lý một khối lượng dữ liệu rất lớn, những vấn đề về xử lý ngôn ngữ tự nhiên,

nhận dạng, xử lý ảnh ba chiều (3-D), dự báo thời tiết v.v. đều đòi hỏi phải xử lý dữ
liệu với tốc độc rất cao, với khối lượng dữ liệu rất lớn. Hầu hết những bài toán này,
những máy tính xử lý tuần tự là không đáp ứng yêu cầu thực tế.do đó cần phải có
những hệ thống máy tính thật mạnh mới đáp ứng được những yêu cầu của thực tế.

13


Chương 2: Thuật toán song song với dữ liệu lớn

Mặc dù tốc độ xử lý của các Bộ xử lý tăng nhiều trong những năm qua, nhưng do
giới hạn về vật lý nên khả năng tính toán của chúng không thể tăng mãi được. Điều
này dẫn tới là muốn tăng được khả năng tính toán của các hệ thống máy tính thì
đích cuối cùng là phải khai thác được khả năng xử lý song song của chúng. Ngày
càng xuất hiện nhiều bài toán mà những hệ thống đơn một bộ xử lý không đáp ứng
được yêu cầu xử lý về thời gian, do đó đòi hỏi phải sử dụng những hệ thống đa bộ
xử lý và đòi hỏi phải xử lý song song.
2.1.3 Phân loại hệ thống tính toán song song
 SIMD (Single Instruction, Multiple Data): song song hóa về mặt dữ liệu.
(Single Instruction Stream, Multiple Data Stream - Đơn luồng lệnh, đa luồng
dữ liệu). Máy tính loại SIMD có một đơn vị điều khiển để điều khiển nhiều
đơn vị xử lý (nhiều hơn một đơn vị) thực hiện theo một luồng các câu lệnh.
CU phát sinh tín hiệu điều khiển tới tất cả các phần tử xử lý, những BXL này
cùng thực hiện một phép toán trên các mục dữ liệu khác nhau, nghĩa là mỗi
BXL có luồng dữ liệu riêng.
 MISD: Multiple Instruction, Single Data: chia sẻ bộ nhớ (Multiple
Instruction Stream, Single Data Stream – Đa luồng lệnh, đơn luồng dữ liệu).
Máy tính loại MISD là ngược lại với SIMD. Máy tính MISD có thể thực hiện
nhiều chương trình (nhiều lệnh) trên cùng một mục dữ liệu, nên còn được gọi
là MPSD (đa chương trình, đơn dữ liệu).

 MIMD: Multiple Instruction, Multiple Data: máy tính song song thực sự
(Multiple Instruction Stream, Multiple Data Stream - Đa luồng lệnh, đa
luồng dữ liệu). Máy tính loại MIMD còn gọi là đa BXL, trong đó mỗi BXL
có thể thực hiện những luồng lệnh (chương trình) khác nhau trên các luồng
dữ liệu riêng. Hầu hết các hệ thống MIMD đều có bộ nhớ riêng và cũng có
thể truy cập vào được bộ nhớ chung (global) khi cần, do vậy giảm thiểu được
thời gian trao đổi dữ liệu giữa các BXL trong hệ thống. Đây là kiến trúc phức
tạp nhất, nhưng nó là mô hình hỗ trợ xử lý song song cao nhất và đã có nhiều
máy tính được sản xuất theo kiến trúc này.

14


Chương 2: Thuật toán song song với dữ liệu lớn

2.1.4 Tiêu chí của thuật toán song song
Thách thức cũng như tiêu chí hoạt động của một thuật toán song song như sau:
 Giảm tối đa chi phí tương tác/ gửi thông điệp giữa các tiến trình
o Tăng giá trị tối đa của dữ liệu cục bộ
o Giảm dung lượng của dữ liệu trao đổi
o Giảm tần suất trao đổi thông diệp giữa các tiến trình
 Giảm thiểu chi phí đồng bộ và tương tác
 Chia tải hiệu quả giữa các tiến trình con
 Giảm thiểu tối đa sự tính toán trùng lặp giữa các tiến trình con
2.2 Môi trường phân tán
Xử lý dữ liệu trong hệ thống phân tán lớn đã trở thành một vấn đề cấp bách đối với
tất cả các công ty trên nền web, bất kể mọi lãnh vực. Dữ liệu ngày càng được thu
thập nhiều và dễ dàng thông qua các công cụ chuẩn, mã nguồn mở hiện đại, kèm
theo đó là chi phí lưu trữ dữ liệu ngày càng rẻ hơn. Vì thế việc phân tích và đánh
giá, rút trích ra các tri thức có ích từ nguồn dữ liệu trên đang trở nên quan trọng, và

được chú ý phát triển nhiều trong các tổ chức doanh nghiệp hiện đại.
Thời gian tương tác của các câu truy vấn trên các tập dữ liệu cực lớn đóng vai trò
quan trọng trong các tác vụ phân tích, rút trích tri thức như đã đề cập ở trên. Ngoài
ra khả năng chịu lỗi, độ tin cậy, khả năng phục hồi sau sự cố, khả năng mở rộng và
tích hợp tính toán giữa các hệ thống phân tán lớn cũng là một vấn đề quan trọng.
Để giải quyết bài toán trên, nhiều tổ chức khoa học, doanh nghiệp đã cùng nhau
nghiên cứu, hiện thực các thuật toán tối ưu cho môi trường phân tán, các nền tảng
chuẩn và mở cho các tác vụ tính toán trên mạng lưới phân tán lớn, trong đó nổi bật
nhất là nền tảng Hadoop của tổ chức Apache.

15


Chương 3: Hiện thực các thuật toán song song

CHƯƠNG 3: HIỆN THỰC CÁC THUẬT TOÁN SONG SONG
3.1 Dijkstra
3.1.1 Giới thiệu
Bài toán tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh là một trong số
những bài toán tối ưu trên đồ thị và được ứng dụng rộng rãi trong thực tế cũng như
các ứng dụng thú vị trong ngành toán học rời rạc. Bài toán được đề xuất và giải
quyết bởi nhà khoa học máy tính người Hà Lan Edsger Dijkstra và được gọi là thuật
toán Dijkstra. Thuật toán có độ phức tạp là O(n2), với độ phức tạp tính toán cao của
thuật toán này cũng như đòi hỏi về mặt thời gian, việc giải bài toán này với tính chất
tuần tự của giải thuật sẽ gặp phải những vấn đề về thời gian thực hiện chương trình,
tốc độ xử lý, khả năng lưu trữ của bộ nhớ, xử lý dữ liệu với quy mô lớn,… kích
thước của bài toán tăng lên và không gian tìm kiếm càng lớn, yêu cầu phải song
song hóa giải thuật để tăng tốc độ và hiệu quả của giải thuật
3.1.2 Thuật toán tuần tự
Đầu vào: Đồ thị liên thông G(V,E,w), w(i,j) > 0


(i,j) E, đỉnh nguồn a.

Đầu ra: Chiều dài đường đi ngắn nhất và đường đi ngắn nhất từ đỉnh a đến tất cả
các đỉnh trên đồ thị.
+ Phương pháp:
Bước 1. Gán L(a):=0. Với mọi đỉnh x ≠ a gán L(x) = ∞. Đặt T:=V.
Bước 2. Chọn v

T, v chưa xét sao cho L(v) có giá trị nhỏ nhất.

Đặt T:=T\{v}, đánh dấu đỉnh v đã xét.
Bước 3. Nếu T=

, kết thúc. L(z),

z V, z≠a là chiều dài đường đi ngắn nhất từ a

đến z. Từ z lần ngược theo đỉnh được ghi nhớ ta có đường đi ngắn nhất. (L(z) không
thay đổi, nếu L(z)= ∞ thì không tồn tại đường đi_(Not Path)). Ngược lại sang bước
4.

16


Chương 3: Hiện thực các thuật toán song song

Bước 4. Với mỗi x

T kề v gán L(x):= min{L(x), L(v)+w(v,x)}. Nếu L(x) thay đổi


thì ghi nhớ đỉnh v cạnh đỉnh x bằng mảng truoc[] (với truoc[] của đỉnh 1= 0) để sau
này xây dựng đường đi ngắn nhất. Quay về bước 2. Độ phức tạp của thuật toán
Dijkstra là O(n2) [3].
Ví dụ: Cho đồ thị được biểu diễn như sau, sau khi thuật toán thực hiện xong thì kết
quả được ghi nhớ lên các nhãn đỉnh tương ứng.

Hình 3.1: Kế t quả

tính toán đư ợ c trên đồ

thị

Mảng trước[]=0 1 1 2 3 3 6 4 8 11 7 11 (Mảng ghi nhớ trước[] dùng để tìm đường
đi, với trước[1]=0)
Mảng độ dài L = 0 7 5 13 15 15 17 18 38 39 24 29

17


Chương 3: Hiện thực các thuật toán song song

Vậy kết quả từ đỉnh 1 đến tất cả các đỉnh là:
Đến 2=7 (1 2)
Đến 3=5 (13)
Đến 4=13 (1→2→4)
Đến 5=15 (1→3→5)
Đến 6=15 (1→3→6)
Đến 7=17 (1→3→6→7)
Đến 8=18 (1→2→4→8)

Đến 9=38 (1→2→4→8)
Đến 10=39 (1→3→6→7→11→10)
Đến 11= 24 (1→3→6→7→11)
Đến 12=29 (1→3→6→7→11→12)
Mã giả

Tạo cluster cl[V]
Với một đỉnh nguồn nhất định - vertex s
While (có tồn tại trong tập đỉnh một đỉnh nằm ngoài cluster
cl[V])
{
FOR (tất cả các đỉnh nằm ngoài cluster)
Tính toán khoảng cách từ đỉnh này đến vertex S thông qua
cluster.
END
** O(V) **
Chọn đỉnh
cluster

có

khoảng

cách

** O(V) **
}

18


ngắn

nhất

và

thêm

nó

vào


Chương 3: Hiện thực các thuật toán song song

Với thuật toán tuần tự như trên, giải thuật có độ phức tạp là O(n2) khi n tăng lên quá
lớn (khoảng vài chục ngàn đỉnh) thì thời gian xử lý sẽ chậm đi đánh kể, điều này
không đáp ứng được những ứng dụng cho giải thuật Dijkstra đòi hỏi chạy với thời
gian nhanh hơn.
3.1.3 Thuật toán song song
Thuật toán đã giải quyết trên đồ thị với thời gian chạy khá lâu trên đồ thị có số đỉnh
lớn và dễ dàng tìm thấy nhiều ứng dụng trong các lĩnh vực khoa học kỹ thuật, y tế,
sinh vật và đặc biệt trong mạng giao thông vận tải. Tuy nhiên, có rất nhiều ứng
dụng cần xử lý nhanh trên đồ thị có số đỉnh lớn thì thuật toán tuần tự không đáp ứng
được. Vì vậy ta phải tìm cách giải quyết bài toán với số đỉnh lên đến hàng chục
ngàn đỉnh mà thời
Hiện nay, mô hình xử lý song song đã và đang phát triển mạnh mẽ giải quyết những
vấn đề bế tắc mà mô hình xử lý tuần tự gặp phải như: vấn đề thời gian thực hiện
chương trình, tốc độ xử lý, khả năng lưu trữ của bộ nhớ và xử lý dữ liệu với quy mô
lớn.

 Phương án đề xuất
o Mỗi bộ vi xử lý xác định đỉnh gần kề ngắn nhất từ đỉnh nguồn một
cách độc lập
o Song song hóa việc lựa chọn đỉnh gần nhất
o Chia sẻ kết quả sau khi tính toán giữa các đỉnh
o Mỗi bộ xử lý cùng tiến hành cập nhật danh sách đỉnh sau khi tính toán
Mã giả:
Tạo cluster cl[V]
Với một đỉnh nguồn nhất định - vertex s
[Mỗi bộ xử lý phụ trách xử lý một tập con v phần tử của p
đỉnh trong vòng lặp sau]
While (có tồn tại một đỉnh nằm ngoài cluster cl[V])
{

19


Chương 3: Hiện thực các thuật toán song song

FOR (tất cả các đỉnh trong tập con mà nằm ngoài cluster)
Tính toán khoảng cách từ đỉnh này đến vertex S
thông qua cluster.
Chọn đỉnh có khoảng cách ngắn nhất và thêm nó vào
cluster.
[Mỗi bộ xử lý tính toán song song và dùng kết quả
cục bộ, so sánh để tìm ra giá trị ngắn nhất]
END
}

3.1.4 Nhận xét

Thuật toán song song Dijkstra dựa trên mô hình SIMD (Single Instruction, Multiple
Data) tức là đơn luồng lệnh và đa dữ liệu, đây là mô hình khá dễ hiện thực nhưng
cũng mang lại hiệu quả khá cao, nếu so sánh thời gian thực thi đối với thuật toán
phiên bản tuần tự.
Tuy nhiên mô hình này không phải là mô hình song song hoàn thiện, có thể triển
khai dạng tính toán lưới. Cần biết rằng thuật toán Dijkstra bản chất dựa vào hàng
đợi tuần tự, vì vậy việc triển khai thuật toán song song một cách toàn diện (đa
nguồn lệnh, đa dữ liệu) gặp nhiều khó khăn.
3.2 K-means
3.2.1 Giới thiệu
Phân cụm là kỹ thuật rất quan trọng trong khai phá dữ liệu, nó thuộc lớp các
phương pháp Unsupervised Learning trong Machine Learning. Có rất nhiều định
nghĩa khác nhau về kỹ thuật này, nhưng về bản chất ta có thể hiểu phân cụm là các
qui trình tìm cách nhóm các đối tượng đã cho vào các cụm (clusters), sao cho các
đối tượng trong cùng 1 cụm tương tự (similar) nhau và các đối tượng khác cụm thì
không tương tự (Dissimilar) nhau.
Mục đích của phân cụm là tìm ra bản chất bên trong các nhóm của dữ liệu. Các
thuật toán phân cụm (Clustering Algorithms) đều sinh ra các cụm (clusters). Tuy
nhiên, không có tiêu chí nào là được xem là tốt nhất để đánh hiệu của của phân tích

20


Chương 3: Hiện thực các thuật toán song song

phân cụm, điều này phụ thuộc vào mục đích của phân cụm như: data reduction,
“natural clusters”, “useful” clusters, outlier detection
Kỹ thuật phân cụm có thể áp dụng trong rất nhiều lĩnh vực như:
 Marketing: Xác định các nhóm khách hàng (khách hàng tiềm năng, khách
hàng giá trị, phân loại và dự đoán hành vi khách hàng,…) sử dụng sản phẩm

hay dịch vụ của công ty để giúp công ty có chiến lược kinh doanh hiệu quả
hơn;
 Biology: Phận nhóm động vật và thực vật dựa vào các thuộc tính của chúng;
 Libraries: Theo dõi độc giả, sách, dự đoán nhu cầu của độc giả…;
 Insurance, Finance: Phân nhóm các đối tượng sử dụng bảo hiểm và các dịch
vụ tài chính, dự đoán xu hướng (trend) của khách hàng, phát hiện gian lận tài
chính (identifying frauds);
 WWW: Phân loại tài liệu (document classification); phân loại người dùng
web (clustering weblog);…
3.2.2 Thuật toán tuần tự
Thuật toán K-Means thực hiện qua các bước chính sau:
1. Chọn ngẫu nhiên K tâm (centroid) cho K cụm (cluster). Mỗi cụm được đại
diện bằng các tâm của cụm.
2. Tính khoảng cách giữa các đối tượng (objects) đến K tâm (thường dùng
khoảng cách Euclidean)
3. Nhóm các đối tượng vào nhóm gần nhất
4. Xác định lại tâm mới cho các nhóm
5. Thực hiện lại bước 2 cho đến khi không có sự thay đổi nhóm nào của các đối
tượng
3.2.3 Thuật toán song song
Nhận thấy trong 5 bước của thuật toán Kmeans tuần tự, ta có thể song song hóa 2
bước là bước 3 và bước 4.
Bước 3: Nhóm các đối tượng vào nhóm gần nhất

21


Chương 3: Hiện thực các thuật toán song song

Trong bước này, chúng ta lặp qua tất cả các điểm và kiểm tra tất cả các tâm để kiếm

tâm điểm gần nhất. Quá trình lặp qua tất cả các điểm này có thể song song hóa theo
mô hình SIMD bằng cách chia nhỏ tập hợp các điểm ra thành n mảnh và thực hiện
tính toán song song trên n mảnh này.
Bước 4: Xác định lại tâm mới cho các nhóm
Trong bước này, chúng ta lặp qua tất cả các nhóm và tính toán lại tâm mới. Ta có
thể áp dụng cách song song hóa như vừa nêu ở bước 3 cho bước 4 này, vì hai bước
này các hoạt động tính toán khá độc lập và có thể song song hóa dễ dàng.
3.2.4 Nhận xét
Thuật toán song song Kmeans dựa trên mô hình SIMD (Single Instruction, Multiple
Data) tức là đơn luồng lệnh và đa dữ liệu, đây là mô hình khá dễ hiện thực nhưng
cũng mang lại hiệu quả khá cao, nếu so sánh thời gian thực thi đối với thuật toán
phiên bản tuần tự.
Khóa luận lựa chọn cách thức song song hóa này vì đây là cách thức khá đơn giản
để tăng hiệu năng của thuật toán.
3.3 Apriori
3.3.1 Giới thiệu
Khai phá dữ liệu đã và đang được ứng dụng rộng rãi trong rất nhiều lĩnh vực. Đặc
biệt, trong những năm gần đây với số lượng dữ liệu đã vượt quá khả năng xử lý của
những hệ thống cơ sở dữ liệu truyền thống thì việc khai phá và xử lý dữ liệu lớn
một cách hiệu quả là một thách thức thực sự.
Trong khai phá dữ liệu thì khai phá tập phổ biến là một trong những nhiệm vụ quan
trọng có vai trò quyết định, nó đã và đang thu hút được rất nhiều sự chú ý của các
nhà khoa học. Nhiều thuật toán khai phá tập mục phổ biến đã được công bố với kết
quả rất thành công như thuật toán Apriori, FP-Growth, Eclat …, trong đó thuật toán
Apriori là một thuật toán nền tảng cho nhiều thuật toán khai phá luật kết hợp sau
này, và vẫn được coi là thuật toán phổ biến nhất để khai thác tập phổ biến.

22