HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
---------------------------------------
TRẦN THỊ LỊCH
KHAI PHÁ LUẬT KẾT HỢP VỚI DỮ LIỆU
PHÂN TÁN DỰA TRÊN MÔ HÌNH MAPREDUCE
LUẬN VĂN THẠC SĨ KỸ THUẬT
HÀ NỘI – 2014
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
---------------------------------------
KHAI PHÁ LUẬT KẾT HỢP VỚI DỮ LIỆU PHÂN TÁN
DỰA TRÊN MÔ HÌNH MAPREDUCE
Chuyên ngành: Khoa học máy tính
Mã số
: 60.48.01.01
LUẬN VĂN THẠC SĨ KỸ THUẬT
NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS.TS TRẦN ĐÌNH QUẾ
HÀ NỘI - 2014
1
MỞ ĐẦU
1. Lý do chọn đề tài
Khai phá dữ liệu (Data Mining ) là một lĩnh vực
khoa học liên ngành mới xuất hiện gần đây nhằm đáp ứng
nhu cầu phát hiê ̣n ra những tri thức có ích , phục vụ cho
công viê ̣c của con người. Các kết quả nghiên cứu cùng với
những ứng dụng thành công trong khai phá dữ liệu, khám
phá tri thức cho thấy khai phá dữ liệu là một lĩnh vực khoa
học tiềm năng, mang lại nhiều lợi ích, đồng thời có ưu thế
hơn hẳn so với các công cụ phân tích dữ liệu truyền thống.
Trong lĩnh vực khai phá dữ liệu , mục đích của luật
kết hợp (Association Rule - AR) là tìm ra các mối kết hợp
(Association) hay tương quan (Correlation) giữa các đối
tượng trong khối lượng lớn dữ liệu. Ứng dụng của luật kết
hợp rất phổ biến trong nhiều lĩnh vực, nhất là trong kinh
doanh như phân tić h hành vi khách hàng , dự đoán nhu cầ u
của khách hàng...
Mô hin
̀ h MapReduce là một mô hình lập trình
giúp các ứng dụng có thể xử lý nhanh một lượng lớn dữ
liê ̣u trên các máy phân tán hoa ̣t đô ̣ng song son g, đô ̣c lâ ̣p
với nhau từ đó giúp rút ngắ n thời gian xử lý toàn bô ̣ dữ
liê ̣u. MapReduce có thể chạy trên các phần cứng thông
thường (commodity hardware), không đòi hỏi các server
chạy MapReduce phải là các máy tính có khả năng tính
2
toán, lưu trữ và truy xuất mạnh mẽ. Do vậy, chi phí triển
khai MapReduce sẽ rẻ hơn.
MapReduce làm đơn giản hoá các giải thuật tính
toán phân tán. Với MapReduce, bạn chỉ cần cung cấp hai
hàm Map và Reduce cùng với một số thành phần xử lý dữ
liệu đầu vào. Do vậy, các nhà phát triển ứng dụng phân
tán có thể tập trung nhiều hơn cho phần logic của ứng
dụng, bỏ qua các chi tiết phức tạp của việc phân tán xử lý.
Sự ra đời của MapReduce đã mở ra cho các doanh
nghiệp cơ hội xử lý các nguồn dữ liệu đồ sộ với chi phí
thấp và thời gian nhanh hơn. Với việc áp dụng
MapReduce, Amazon có thể xử lý được các file log phát
sinh trong quá trình bán hàng trên mạng, phục vụ cho việc
dự đoán xu hướng mua hàng của khách hàng, các sản
phẩm đang được mua nhiều… Facebook có thể xử lý được
khối lượng hơn 10 tỷ hình ảnh mà họ đang lưu trữ để rút
trích các thông tin về kích thước hình ảnh, phát hiện các
hình ảnh xấu.
Vì những lý do trên mà tôi chọn đề tài “ Khai phá
luật kế t hợp với dữ liê ̣u phân tán dựa trên mô hình
MapReduce” làm đề tài luận văn của mình.
2. Mục đích nghiên cứu
Tìm hiểu kỹ thuật , thuâ ̣t toán khai phá luâ ̣t kế t hơ ̣p
trong khai phá dữ liê ̣u.
3
Nghiên cứu mô ̣t mô hình lâ ̣p trình MapReduce
trong viê ̣c ứng du ̣ng vào các bài toán xử lý mô ̣t lươ ̣ng
lớn dữ liê ̣u . Sử du ̣ng H adoop, mô ̣t thể hiê ̣n của
MapReduce, cho viê ̣c phân tić h dữ liê ̣u.
Áp du ̣ng cấ u trúc, tham chiế u các đă ̣c trưng của mô
hình MapReduce vào bài toán phân tić h xu hướng
khách hàng nhằm rút ra những luật kết hợp.
3. Đối tƣợng và phạm vi nghiên cứu
Nghiên cứu khái niệm, vai trò, ứng dụng và các kỹ
thuật khai phá dữ liệu.
Tìm hiểu, nghiên cứu khai phá dữ liê ̣u với luâ ̣t kế t
hơ ̣p và mô ̣t số thuâ ̣t toán .
Tìm hiểu , nghiên cứu mô hình lâ ̣p trình
MapReduce, Hadoop.
4. Phƣơng pháp nghiên cứu
Nghiên cứu, tìm hiểu lý thuyết về các kỹ thuật khai
phá dữ liệu.
Tìm hiểu và cài đặt mô hình lập trình MapReduce
trên nề n Hadoop . Sử du ̣ng ngôn ngữ lâ ̣p trin
̀ h Java
tích hợp Framework Hadoop trên môi trư
Eclipse.
ờng
Nguồ n dữ liê ̣u sẽ sử du ̣ng để thử nghiê ̣m là dữ liê ̣u
mua bán lẻ của khách hàng đã đươ ̣c lưu trữ ta ̣i siêu
thị.
4
5. Kết cấu luận văn
Chƣơng 1: TỔNG QUAN KHAI PHÁ DƢ̃ LIỆU
Giới thiê ̣u tổ ng quan về quá trình khai phá dữ liê ̣u,
các phương pháp khai phá dữ liệu , nhiê ̣m vu ̣ chính , quy
trình khai phá dữ liệu.
Chƣơng 2: KHAI PHÁ LUẬT KẾT HỢP
Trình bày tổng quan về khai phá luật kết hợp và
giới thiê ̣u mô ̣t số thuâ ̣t toán khai phá luâ ̣t kế t hơ ̣p.
Chƣơng 3: TỔNG QUAN MÔ HÌ NH LẬP TRÌ NH
MAPREDUCE
Trình bày tổng quan mô hình lập trình MapReduce ,
các thành phần , cấ u trúc của mô hiǹ h này . Làm quen với
môi trường phân tán Hadoop trên mô hình đó .
Chƣơng 4: ỨNG DỤNG LUẬT KẾT HỢP TRONG
MÔ HÌ NH MAPREDUCE
Tóm tắt lại kết quả đạt được , ưu điể m , nhươ ̣c điể m của
thuâ ̣t toán và phương hướng phát triể n tiế p theo.
5
CHƢƠNG 1 TỔNG QUAN KHAI PHÁ DỮ LIỆU
1.1 Khai phá dƣ̃ liêụ là gi?̀
1.2 Quy trin
̀ h khai phá dƣ̃ liêụ
1. Làm sạch dữ liệu
2. Tích hợp dữ liệu
3. Trích chọn dữ liệu
4. Chuyển đổi dữ liệu
5. Khai phá dữ liệu
6. Ước lượng mẫu
7. Biểu diễn tri thức
1.3 Các phƣơng pháp khai phá dữ liệu
1.3.1 Phát hiện các luật kết hợp
1.3.2 Phân cụm
1.3.3 Phân lớp
1.3.4 Hồi quy
1.3.5 Mô hình phụ thuộc
1.3.6 Phát hiện sự thay đổi và độ lệch
1.4 Các dạng cơ sở dữ liệu có thể khai phá
CSDL quan hệ (relational databases)
CSDL dạng giao dịch (transactional databases)
CSDL mở rộng
6
1.5 Phân loại các hệ khai phá dữ liệu
Phân loại dựa trên kiểu dữ liệu được khai phá
Phân loại dựa trên dạng tri thức được khám phá
Phân loại dựa trên kỹ thuật được áp dụng
Phân loại dựa trên lĩnh vực được áp dụng
1.6 Nhƣ̃ng thách thƣ́c khai phá dƣ̃ liêụ
1.7 Các ứng dụng trong khai phá dữ liệu
1.8 Kế t luâ ̣n
Trong chương một, luận văn đã trình bày một cách tổng
quan nhất về KPDL - cụ thể là định nghĩa về KPDL và
những mục đích, ứng dụng, động cơ thúc đẩy các nhà tin
học chú trọng vào lĩnh vực nghiên cứu này.
7
CHƢƠNG 2: KHAI PHÁ LUẬT KẾT HỢP
2.1 Giới thiêụ
2.1.1 Các khái niệm cơ bản
Định nghĩa 2.1: Độ hỗ trợ (support) của luật kết hợp X
Y là :
Support =
Định nghĩa 2.2: Độ tin cậy (Confidence) của luật kết hợp
X Y là : Đơn vị tính %.
Confidence =
Các luật thỏa mãn có support và confidence thỏa
mãn (lớn hơn hoặc bằng)
cả Minimum support và
Minimum confidence gọi là các luật mạnh (Strong Rule)
Một itemsets mà tần suất xuất hiện của nó >=
min_sup goi là frequent itemsets.
2.1.2 Khai phá luật kế t hợp
2.1.2.1 Phát biểu bài toán:
- Cho một tập mục I = {I1, I2,..., Im}
- Một cơ sở dữ liệu giao dịch D (n giao dịch)
- Độ hỗ trợ tối thiểu minsup và độ tin cậy tối thiểu mincof.
8
Tìm tập các luật kết hợp R: X
Y sao cho
support(X Y) >= minsup và confidence(X Y) >=
mincof.
2.1.2.2 Giải quyết bài toán
Tìm tất cả các tập mục thỏa mãn độ hỗ trợ tối thiểu
minsup cho trước, hay tập mục phổ biến.
Tìm tất cả những luật kết hợp từ những tập mục
phổ biến thỏa độ tin cậy tối thiểu mincof cho trước.
2.1.2.3 Phân loại luật kết hợp
Luật kết hợp nhị phân
Luật kết hợp mờ
Luật kết hợp nhiều mức
2.2 Mô ̣t số thuâ ̣t toán khai phá luâ ̣t kế t hơ ̣p
2.2.1 Thuật toán khai phá luật kế t hợp tuầ n tự
2.2.2 Thuật toán khai phá luật kết hợp song song
2.2.3 Thuật toán khai phá luật kế t hợp phân tán
2.3 Ứng dụng của luật kết hợp
9
2.4 Kế t luâ ̣n
Trong chương này chúng ta tìm hiểu được một số vấn đề
sau:
Các hiểu biết, khái niệm về luật kết hợp, một số
thuật toán dùng trong khai phá luật kết hợp, làm
quen thuật toán Apriori.
Phân biệt thế nào là độ hỗ trợ, độ tin cậy, Frequent
items, ItemSet và đặc biệt là cách tìm ra một
frequent items như thế nào?
Thuật toán Apriori được dùng để phát hiện các luật
kết hợp dạng khẳng định nhị phân chứ không thể
phát hiện các luật kết hợp ở dạng phủ định.
10
CHƢƠNG 3: TỔNG QUAN MÔ HÌ NH LẬP TRÌ NH
MAPREDUCE
3.1 Giới thiêụ mô hin
̀ h tính toán MapReduce
3.1.1 Nguyên nhân và lich
̣ sử ra đời
Khi khối lượng dữ liệu của một hệ thống gia tăng
tới một mức độ nhất định (khoảng hàng ngàn Terabyte
chẳng hạn), thì việc hệ thống sẽ phải đối mặt với thách
thức làm sao để lưu trữ và phân tích dữ liệu.
Sự bùng nổ về dữ liệu đã đặt ra các cơ hội, cơ hội
chiếm lĩnh một nguồn thông tin khổng lồ, làm sao để lưu
trữ và phân tích nguồn dữ liệu đó nếu chúng ta có đủ khả
năng phân tích và xử lý nguồn dữ liệu đó, biến những dữ
liệu thô thành những thông tin hữu ích với một mức chi
phí hợp lý.
3.1.2 MapReduce là gì ?
“MapReduce là mô hình lập trình và thực thi song
song các xử lý và phát sinh các tập dữ liệu lớn”.
Hình 3.1 Mô hình MapReduce của Google.
11
12
MapReduce sử dụng hai thao tác chính cho việc thực thi
công việc ban đầu từ người dùng là hàm map và hàm
reduce
Hàm map có input là một cặp (k1, v1) và output là
một danh sách các cặp (k2, v2).
map(k1, v1) -> list(k2, v2)
Sau giai đoạn này thì chúng ta có một tập hợp rất
nhiều cặp (key, value) thuộc kiểu (k2, v2) gọi là các cặp
(key, value) trung gian. MR cũng sẽ nhóm các cặp này
theo từng key, như vậy các cặp (key, value) trung gian có
cùng k2 sẽ nằm cùng một nhóm trung gian.
Một cách hình thức, hàm này có thể mô tả như sau
reduce(k2, list (v2))->list(v3)
Trong đó k2 là key chung của nhóm trung gian, list(v2) là
tập các values trong nhóm, và list(v3)là một danh sách
các giá trị trả về của reduce thuộc kiểu dữ liệu v3. Do
reduce được áp dụng vào nhiều nhóm trung gian độc lập
nhau, chúng lại một lần nữa có thể được chạy song song
với nhau.
3.1.3 Ưu điểm của MapReduce
3.1.4 Nguyên tắ c hoa ̣t động của MapReduce
13
Đọc dữ liệu đầu vào
Thực hiện xử lý các phần dữ liệu vào (xử lý từng
phần một ) (Thực hiện hàm Map)
Trộn và sắp xếp các kết quả thu được từ các máy
tính làm sao để được kết quả tiện lợi nhất so với
mục đích của quá trình.
Tổng hợp các kết quả trung gian thu được từ các
máy tính phân tán (Thực hiện hàm reduce)
Hình 3.2 Sơ đồ hoạt động của quá trình Mapreduce
Đưa ra kết quả cuối cùng
14
3.2 Giới thiêụ nề n tảng tính toán phân tán Hadoop
trên mô hin
̀ h MapReduce
3.2.1 Hadoop là gì?
1) Hadoop là một framework cho phép phát triển các ứng
dụng phân tán.
2) Hadoop cung cấp một phương tiện lưu trữ dữ liệu phân
tán trên nhiều node.
3.2.2 Lịch sử Hadoop.
3.2.3 Các thành phần của Hadoop.
3.2.4 Ứng dụng của Hadoop
3.3 Hadoop Distributed File System (HDFS)
3.3.1 Giới thiê ̣u
3.4 Kế t luâ ̣n
Một số ván đề đã tìm hiểu trong chương này:
MapReduce là mô hình lập trình và thực thi song
song các xử lý và phát sinh các tập dữ liệu lớn.
MapReduce là một mô hình được áp dụng trên một
hệ thống các máy tính được kết nối với nhau và cài
đặt chương trình MapReduce và thường kèm theo
nó là một hệ thống chia sẻ file phân tán (HDFS).
15
CHƢƠNG 4: ỨNG DỤNG LUẬT KẾT HỢP TRONG
MÔ HÌ NH MAPREDUCE
4.1 Giới thiệu bài toán
Maket Basket Analysis (MBA) là một trong những
phương pháp khai phá dữ liệu để phân tích dựa trên một
tập dữ liệu với nhau. Ý tưởng chính của thuật toán là đi
tìm sự kết hợp của các cặp mặt hàng trong cửa hàng…
Trong chương này chúng ta sẽ thực nghiệm mô
hình lập trình MapReduce với bài toán Maket Basket
Analysis .
4.1.1 Thuật toán khai phá luật kết hợp Apriori tuần tự
Bài toán khai phá luật kết hợp được chia thành hai bài
toán nhỏ:
Bài toán 1: Tìm tất cả các tập mục thỏa mãn độ hỗ trợ
tối thiểu minsup cho trước hay tập mục phổ biến.
Bài toán 2: Tìm tất cả những luật kết hợp từ những
tập mục phổ biến thỏa độ tin cậy tối thiểu mincof cho
trước.
Thuật toán như sau:
16
//(1) Map transaction t in data
source to all Map nodes;
C1 = {size 1 frequent items};
// (2) min_support = num/total
items;
L1 = {size 1 frequent items
min_support};
for (k = 1; Lk !=∅; k++) do begin
// (3) sắp xếp và loại bỏ các items
trùng nhau từ Lk
Ck+1 = Lk join_sort Lk;
for each transaction t in data
source
with Ck+1 do
//
Đếm số lần xuất hiện Ck+1
trong t
// (5) Tìm Lk+1 với Ck+1 thỏa mãn
min_support
Lk+1 = {size k+1 frequent items
min_support};
end
end
return ∪k Lk;
Hình 4.1 Thuật toán Apriori tuần tự
4.1.2 Thuật toán khai phá luật kết hợp Apriori trên
MapReduce
Giai đoạn Mapper:
17
Step 1: Đọc mỗi giao dịch của dữ liệu
đầu vào và tạo ra một tập các Item
(, ,…, ) where < Vn>:(vn1,
vn2,.. vnm)
Step 2: Sắp xếp tất cả các tập và
tạo ra một tập các dữ liệu đã được sắp
xếp là :
(, , …, ) trong đó < Un>:
(un1, un2,.. unm)
Step 3: Vòng lặp While < Un> có phần tử
tiếp theo;
//Chú ý:mỗi danh sách Un được xử lý
riêng rẽ.
3.1: Vòng lặp For mỗi Item từ un1 tới
unm của < Un> with NUM_OF_PAIRS
3.a: sinh ra một tập dữ liệu :
(yn1, yn2,.. ynl);
Ynl: (unx uny) là danh sách của các cặp
(un1, un2,.. unm) where unx uny
3.b: Làm tăng sự xuất hiện của ynl;
//Chú ý: (key, value) = (ynl, số lần
xuất hiện)
3.2: Kết thúc vòng lặp For
Step 4: Kết thúc vòng lặp While
Tập dữ liệu được tạo ra là đầu vào của
giai đoạn Reducer:
(key, ) = (ynl, )
Hình 4.2 MBA Algorithm for Mapper
18
Giai đoạn Reducer
1 Đọc(ynl,)
data từ nhiều node.
2.
Add the values for ynl to
have
(ynl, total number of occurrences)
Hình 4.3. MBA Algorithm for Reducer
4.1.3 So sánh thuật toán apriori trên MapReduce và
thuật toán Apriori tuần tự.
Độ phức tạp của thuật toán Apriori tuần tự là
O(k
t
n)) với k: kích cỡ của frequent items, t: số giao
dịch, n: số Items của giao dịch với t>>k, n>>k.
Độ phức tạp của thuật toán Apriori-Map/Reduce là
O(k
t
n/p) với k: kích thước của frequent items, t: số
transactions, n: số items của transactions, p: số nodes
Map và Reduce giả sử rằng kích thước các Node là như
nhau. Với điều kiện t >> k, n >> k.
Lý thuyết này đã chỉ ra rằng độ phức tạp của thuật toán
Apriori sử dụng Map/Reduce ít hơn p lần so với thuật toán
Apriori tuần tự.
- Xem thêm -