BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ TP. HCM

------------------------

MAI THẾ PHÚC

BẢO VỆ TÍNH RIÊNG TƢ TRONG KHAI THÁC
LUẬT KẾT HỢP TỪ CƠ SỞ DỮ LIỆU ĐƢỢC
THUÊ NGOÀI
LUẬN VĂN THẠC SĨ
Chuyên ngành: Công Nghệ Thông Tin
Mã ngành: 60480201

TP. HỒ CHÍ MINH, tháng 06 năm 2016


CÔNG TRÌNH ĐƢỢC HOÀN THÀNH TẠI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ TP. HCM

Cán bộ hƣớng dẫn khoa học:
PGS.TS. Võ Đình Bảy

Luận văn Thạc sĩ đƣợc bảo vệ tại Trƣờng Đại học Công nghệ TP. HCM ngày 10
tháng 09 năm 2016.
Thành phần Hội đồng đánh giá Luận văn Thạc sĩ gồm:
Họ và Tên

TT

Chức danh Hội đồng

Xác nhận của Chủ tịch Hội đồng đánh giá Luận văn sau khi Luận văn đã sửa
chữa (nếu có).
Chủ tịch Hội đồng đánh giá LV

PGS. TS Quản Thành Thơ


TRƢỜNG ĐH CÔNG NGHỆ TP. HCM

CỘNG HÕA XÃ HỘI CHỦ NGHĨA VIỆT NAM

PHÒNG QLKH – ĐTSĐH

Độc lập – Tự do – Hạnh phúc
TP. HCM, ngày 30 tháng 06 năm 2016

NHIỆM VỤ LUẬN VĂN THẠC SĨ
Họ tên học viên: MAI THẾ PHÖC

Giới tính: Nam

Ngày, tháng, năm sinh: 10/02/1979

Nơi sinh: Thanh Hoá

Chuyên ngành: Công nghệ thông tin

MSHV: 1441860051

I- Tên đề tài:

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ả
nêu trong Luận vă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ôi xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện Luận văn này
cũng nhƣ các trích dẫn hay tài liệu học thuật tham khảo đã đƣợc cảm ơn đến tác giả và
các thông tin trích dẫn trong Luận văn đã đƣợc chỉ rõ nguồn gốc.
Học viên thực hiện Luận văn

Mai Thế Phúc


ii

LỜI CÁM ƠN

Trƣớc hết, cho tôi đƣợc gửi lời cảm ơn đến sự hƣớng dẫn và giúp đỡ tận tình
của PGS.TS Võ Đình Bảy.
Xin cảm ơn các Thầy/Cô, Khoa CNTT Đại Học Công Nghệ TP. HCM đã
giúp đỡ và cung cấp cho tôi những kiến thức quý giá trong suốt thời gian học tập
và nghiên cứu thực hiện luận văn.
Tôi cũng xin gởi lời cảm ơn đến gia đình, bạn bè và những ngƣời thân đã
luôn quan tâm và giúp đỡ tôi trong suốt thời gian học tập và nghiên cứu hoàn thành
luận văn này.
Luận văn không thể tránh khỏi những sai sót, rất mong nhận đƣợc ý kiến
đóng góp của mọi ngƣời cho luận văn đƣợc hoàn thiện hơn.
Tôi xin chân thành cảm ơn.
TP. Hồ Chí Minh, ngày 30 tháng 06 năm 2016

Mai Thế Phúc


service provider (server). However, both the items and the association rules of the
outsourced database are considered private property of the corporation (data owner). To
protect corporate privacy, the data owner transforms its data and ships it to the server,
sends mining queries to the server, and recovers the true patterns from the extracted
patterns received from the server.
Research in this thesis focuses on the study of algorithms of encryption and
decryption a data model outside ownership, for example, a supermarket, providing data to a
mining company service of data to get the association rules from that supermarket. With the
request to preserve the privacy of the data, ie will not disclose sales data as well as
information obtained from the analysis of this data mining
.


v

MỤC LỤC
LỜI CAM ĐOAN ..................................................................................................... i
TÓM TẮT

........................................................................................................... iii

PHẦN MỞ ĐẦU .......................................................................................................1
MỤC TIÊU CỦA ĐỀ TÀI: .......................................................................................1
NỘI DUNG NGHIÊN CỨU: ....................................................................................2
PHƢƠNG PHÁP NGHIÊN CỨU ............................................................................2
CHƢƠNG 1 :TỔNG QUAN VỀ KHAI THÁC DỮ LIỆU .....................................4
1.1

GIỚI THIỆU ĐỀ TÀI ....................................................................................4



THAY GIÁ TRỊ DỮ LIỆU THẬT BẰNG GIÁ TRỊ KHÔNG XÁC ĐỊNH 25

2.3

ẨN TẬP MỤC NHẠY CẢM .......................................................................29

2.4 THUẬT TOÁN ẨN TẬP MỤC NHẠY CẢM ...............................................................31
CHƢƠNG 3 KỸ THUẬT MÃ HÓA VÀ GIẢI MÃ DỮ LIỆU .............................36


vi

3.1

3.2

CÁC NGHIÊN CỨU LIÊN QUAN ..............................................................36
3.1.1

Đặt vấn đề ..........................................................................................36

3.1.2

Một số nghiên cứu liên quan ..............................................................38

MÃ HÓA VÀ GIẢI MÃ DỮ LIỆU THUÊ NGOÀI .....................................40
3.2.1

Dữ liệu khai thác ................................................................................40

ĐÁNH GIÁ ..................................................................................................62

CHƢƠNG 5 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ........................................64
5.1

ƢU ĐIỂM .....................................................................................................64

5.2

HẠN CHẾ ....................................................................................................65

5.3

HƢỚNG PHÁT TRIỂN ...............................................................................65

TÀI LIỆU THAM KHẢO ..................................................................................... 66


vii

DANH MỤC CÁC TỪ VIẾT TẮT

Từ viết tắt
CSDL
DB

Ý nghĩa
Cơ sở dữ liệu
Cơ sở dữ liệu (DataBase)



PPDM

Khai thác dữ liệu đảm bảo tính riêng tƣ (Privacy Preserving Data
Mining)

PPDP

Công bố dữ liệu bảo mật tính riêng tƣ (Prevacy Preserving Data
Publishing)

PPPP

Công bố mô hình bảo mật tính riêng tƣ (Prevacy Preserving Patern
Publishing)


viii

DANH MỤC CÁC BẢNG

Bảng 1.1 Cơ sở dữ liệu giao dịch ....................................................................................... 7
Bảng 1.2 CSDL y tế .......................................................................................................... 15
Bảng 2.1 Bảng so sánh bốn thuật toán 1a, 1b, 2a, 2b ..................................................... 25
Bảng 2.2 CSDL giao tác gốc D ........................................................................................ 29
Bảng 2.3 CSDL giao tác mô tả quá trình ẩn AB ............................................................. 30
Bảng 2.4 Sửa giá trị của E trong các bộ chứa ADE ........................................................ 33
Bảng 2.5 Sửa giá trị của E trong các bộ chứa ABE ........................................................ 34
Bảng 3.1 CSDL giao dịch, độ hỗ trợ các mặt hàng ......................................................... 40
Bảng 3.2 TDB và độ hỗ trợ ............................................................................................. 47

ngoài (Outsourced) cũng đƣợc phát triển nhƣ một dịch vụ hình mẫu, cho phép các tổ chức
có nguồn lực hạn chế tính toán hoặc khai thác dữ liệu có thể thuê bên ngoài khai thác dữ
liệu của họ [4][17][13]. Ví dụ, các dữ liệu hoạt động giao dịch từ những cửa hàng khác
nhau của Safeway, một chuỗi cửa hàng hoạt động tại Mỹ và Canada, có thể đƣợc chuyển
đến một bên thứ ba cung cấp dịch vụ khai thác cho Safeway. Việc quản lý Safeway không
cần phải sử dụng một đội ngũ các chuyên gia khai thác dữ liệu. Bên cạnh đó, họ có thể cắt
giảm yêu cầu quản lý dữ liệu cục bộ, vì theo định kỳ dữ liệu đƣợc chuyển đến các nhà
cung cấp dịch vụ và những ngƣời có trách nhiệm duy trì sẽ tiến hành khai thác nó để đáp
ứng các yêu cầu từ các nhà phân tích kinh doanh của Safeway. Trong ví dụ này, Safeway
là một chủ sở hữu dữ liệu, là một khách hàng (client) và cung cấp dịch vụ đƣợc gọi là nhà
cung cấp dịch vụ (server). Một trong những vấn đề chính của mô hình này là các server có
quyền truy cập vào dữ liệu có giá trị của client và có thể tìm hiểu các thông tin từ nó bằng
cách nhìn vào các giao dịch, server có thể tìm hiểu các dữ liệu nhạy cảm mà bên client
không muốn công khai (đơn vị hợp tác, lƣợt khách,...).
Để thực hiện việc chia sẻ dữ liệu cho đối tác khai thác, đồng thời bảo vệ đƣợc tính
riêng tƣ trong cơ sở dữ liệu, đề tài này nghiên cứu về việc khai thác luật kết hợp trong
khuôn khổ bảo vệ tính riêng tư từ dữ liệu giao dịch được thuê ngoài
Mục tiêu của đề tài:
Từ những đòi hỏi ngày càng gắt gao của môi trƣờng kinh doanh, yêu cầu doanh
nghiệp phải năng động chia sẻ thông tin của mình cho nhiều đối tƣợng khác nhau. Chẳng
hạn công ty thuê bên ngoài khai thác dữ liệu để định hƣớng chiến lƣợc kinh doanh của
mình..., vì vậy mà việc bảo vệ thông tin là rất quan trọng của công ty, Hầu hết các doanh


2

nghiệp ngày nay đều sử dụng các hệ quản trị cơ sở dữ liệu [2] để lƣu trữ tập trung tất cả
các thông tin quý giá của mình. Hiển nhiên hệ thống sẽ là tiêu điểm tấn công của những
kẻ xấu. Ở mức độ nhẹ, các cuộc tấn công sẽ làm hệ thống CSDL bị hỏng hóc, hoạt động
không ổn định, mất mát dữ liệu làm cho các giao dịch hàng ngày của doanh nghiệp bị


-

Tìm tài liệu bởi các từ khoá ―Privatecy-Preserving‖ , ―Mining‖+ ―Association
rules‖ + ―Outsoured‖

-

Nghiên cứu tổng quan về cơ sở dữ liệu giao dịch.

-

Nghiên cứu mô hình mã hóa và giải mã Encription/Decription


3

-

Xây dựng chƣơng trình và đánh giá kết quả đạt đƣợc.

Bố cục luận văn
Luận văn đƣợc tổ chức thành năm chƣơng:
Chƣơng 1: Trình bày tổng quan về khai thác dữ liệu và bảo toàn tính riêng tƣ.
Chƣơng 2: Trình bày lý thuyết và các thuật toán bảo toàn tính riêng tƣ.
Chƣơng 3: Trình bày lý thuyết, thuật toán và các ví dụ minh họa thuật toán mã hóa
và giải mã dữ liệu sử dụng cho dữ liệu ngoài.
Chƣơng 4: Kết quả chƣơng trình thực nghiệm.
Chƣơng 5: Kết luận và hƣớng phát triển


5

Tuy nhiên, việc khai thác này khó có thể tiến hành ở một đơn vị hay một tổ chức khi yêu
cầu chia sẻ dữ liệu xuất hiện giữa nhiều bên hay khi nhu cầu khai thác dữ liệu thuê cho
nhà cung cấp dịch vụ của bên thứ ba. Ví dụ, dữ liệu về hoạt động giao dịch của các gian
hàng khác nhau trong một chuỗi siêu thị có thể đƣợc gửi đến cho bên thứ ba cung cấp
dịch vụ khai thác dữ liệu. Việc quản lý siêu thị không cần đến một đội ngũ các chuyên
gia khai thác dữ liệu nội bộ. Bên cạnh đó, họ có thể cắt giảm các yêu cầu về quản lý dữ
liệu nội bộ bởi vì các dữ liệu sẽ đƣợc định kỳ chuyển đến cho ngƣời cung cấp dịch vụ là
ngƣời phụ trách việc duy trì các dịch vụ này và tiến hành khai thác nhằm đáp ứng yêu cầu
từ các nhà phân tích kinh doanh của chuỗi siêu thị. Dự kiến rằng mô hình ―dịch vụ khai
thác và quản lý dữ liệu‖ sẽ phát triển với sự ra đời và phổ biến của điện toán đám mây.
Trong ví dụ trên chuỗi siêu thị, khách hàng là chủ sở hữu dữ liệu và nhà cung cấp
dịch vụ đƣợc gọi là máy chủ. Một trong những vấn đề chính của mô hình này là máy chủ
có quyền truy cập vào các dữ liệu có giá trị của chủ sở hữu và có thể biết hoặc tiết lộ
thông tin nhạy cảm của họ, hoặc khi nhìn vào các giao dịch, máy chủ (hoặc một kẻ xâm
nhập có quyền truy cập vào máy chủ) có thể biết sản phẩm (mặt hàng) nào đã đƣợc mua
cùng nhau, và đến lƣợt mình, các mô hình khai thác mô tả hành vi của khách hàng trong
siêu thị. Trong trƣờng hợp này, các giao dịch mua bán và mô hình đƣợc khai thác và tất
cả các thông tin có thể lấy từ dữ liệu đều là tài sản của siêu thị và phải đƣợc giữ an toàn
khỏi máy chủ và bất cứ kẻ xâm nhập nào khác. Thực sự là các thông tin lấy từ dữ liệu có
thể đƣợc các siêu thị sử dụng trong các quyết định tiếp thị quan trọng nhằm cải thiện dịch
vụ của họ.
Vấn đề về bảo toàn thông tin cho các bên tham gia khai thác hay bên cung cấp dữ
liệu cho dịch vụ khai thác là một vấn đề rất quan trọng và là đề tài nghiên cứu chính của
luận văn này.


6




Dữ liệu giao dịch: Cho I = {i1, i2, …, in} là tập tất cả các mục dữ
liệu (mặt hàng). T = {t1, t2, …, tm} là tập tất cả các giao dịch trong
CSDL giao dịch D. CSDL đƣợc cho là quan hệ hai ngôi   I  T. Nếu
mục iI xảy ra trong giao dịch tT thì ta viết là (i, t) , kí hiệu i 
t.


7



Tập phổ biến (kí hiệu FI): XI đƣợc gọi là phổ biến nếu (X) minSupp (với
minSupp là giá trị do ngƣời dùng chỉ định).



Luật kết hợp: Một luật kết hợp có dạng AB, với A  I, B  I và A  B =
Ø. Luật AB ngầm chứa trong D với độ đo Supp s, trong đó s là tỷ lệ các
giao dịch trong D chứa A  B, đƣợc diễn tả bằng xác suất P(A B). Luật
AB có độ đo Conf c trong tập D, thì c là tỷ lệ giữa các giao dịch trong D
chứa A thì chứa luôn B, đƣợc diễn tả bằng xác suất P(B/A).

Để minh họa cho các khái niệm trên, ta lấy ví dụ CSDL với các giao dịch sau.
Bảng 1.1. Cơ sở dữ liệu giao dịch



Mã giao dịch


Hạng mục (item): mặt hàng A = apple, B = bread, C = cereal, D = donuts, E =
eggs.



Tập các hạng mục (itemset): danh sách các hạng mục trong giỏ hàng nhƣ
{A, B, C, D, E}.



Giao dịch (Transaction): tập các hạng mục đƣợc mua trong một giỏ hàng,
lƣu kèm với mã giao dịch (TID).


8



Tập k-hạng mục (k-itemset): Ví dụ danh sách sản phẩm đơn (1-itemset)
nhƣ {A, B, C}, danh sách cặp sản phẩm đi kèm (2-itemset) nhƣ {{A,B},{A,C}},
danh sách 3 sản phẩm đi kèm (3-itemset) nhƣ {{A,B, C},{B, C, E}}.



Độ hỗ trợ: đƣợc kí hiệu (X), hay Supp(X) đƣợc tính bằng công thức:
Supp(X)=Count(X)/|D| , trong đó: X I




RaKesh Agrawal, Ramakrishnan Srikant đƣa ra vào năm 1994, là nền tảng cho việc phát
triển những thuật toán sau này. Thuật toán sinh tập mục ứng cử từ những tập mục phổ
biến ở bƣớc trƣớc, sử dụng kĩ thuật ―tỉa‖ để bỏ đi tập mục ứng cử không thỏa mãn
ngƣỡng hỗ trợ cho trƣớc.

Thuật toán Apriori
Input: Tập các giao dịch D, ngưỡng hỗ trợ minSupp
Output: Tập F

bao gồm các tập mục phổ biến trên D

Method:
L1 = find_frequent_1-itemset(D);
for (k = 2; Lk-1 ≠ ; k++)
{Ck = Apriori_gen(Lk-1);// sinh tập mục ứng cử mới Ck;
For each giao tác t ∈ D
{//Quét D để đếm
Ct = subset(Ck, t);// các ứng viên chứa trong t;
For each Cứng viên

ci ∈ C t

ci.count ++ ;
}
Lk = {ci ∈ Ck|ci.count ≥ minSupp}
}
Return L=

k


Trong các giai đoạn thứ k sau đó (k >1), mỗi giai đoạn gồm có 2 pha:


11

Pha thứ 1: Các (k-1)-itemset phổ biến trong tập Lk-1 tìm đƣợc trong giai đoạn
thứ k-1 đƣợc dùng để sinh ra các tập mục ứng cử Ck bằng cách thực hiện hàm
apriori_gen().
Pha thứ 2: CSDL D sẽ đƣợc quét để tính độ hỗ trợ cho mỗi tập mục ứng cử trong
Ck. Các tập mục ứng cử trong Ck mà đƣợc chứa trong giao dịch t có thể đƣợc xác định
một cách hiệu quả bằng việc sử dụng cây băm.
Hàm apriori_gen() thực hiện hai bƣớc:
Bƣớc 1- Kết nối: Để tìm Lk, một tập ứng viên các tập k item đƣợc sinh bởi việc
kết Lk-1 với chính nó. Tập các ứng viên này đƣợc đặt là Ck. Gọi l1 và l2 là các tập item
trong Lk-1. Ký hiệu li[j] chỉ tới item thứ j trong li (chẳng hạn, l1[k–2] chỉ tới item
cuối thứ 2 trong l1). Với quy ƣớc, Apriori giả sử các item trong một giao tác hay tập item
đã đƣợc sắp xếp theo thứ tự từ điển. Đối với tập (k–1) item, li nghĩa là các item đƣợc
sắp xếp thành li[1]
6

1

A, C, B, E

2

C, D, E

3

A, C, B, E

D

4

4

A, C, D, E

B

4

5

A, C, D, B, E


AC

4

AD

2

AB

3

AB

3

Quét DB

AE

4

AE

4

Loại bỏ Item

CD


2

BE

3

DE

3

BE

3

Danh mục

Độ phổ biến

Danh mục

Độ phổ biến

ACB

3

ACB

3


3

Danh mục

Độ phổ biến

ACBE

3

DỪNG

C2

L3
Quét DB

L2

C3

Danh mục Độ phổ biến L4

C4

ACBE

C5={}

3