Số hóa bởi Trung tâm Học liệu 1 ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CNTT VÀ TRUYỀN THÔNG
o0o

Họ và tên tác giả: Nguyễn Thị Thùy

MỘT SỐ KỸ THUẬT KHAI PHÁ LUẬT KẾT HỢP CÓ
BẢO ĐẢM TÍNH RIÊNG TƢ TRONG CÁC TẬP GIAO DỊCH
PHÂN TÁN NGANG

LUẬN VĂN THẠC SỸ KHOA HỌC


LUẬN VĂN THẠC SỸ KHOA HỌC NGƢỜI HƢỚNG DẪN KHOA HỌC
TS. TRẦN ĐỨC SỰ

Thái Nguyên - 2014

Số hóa bởi Trung tâm Học liệu 3

LỜI CAM ĐOAN

Những kết quả nghiên cứu được trình bày trong luận văn là hoàn toàn
trung thực, không vi phạm bất cứ điều gì trong luật sở hữu trí tuệ và pháp luật
Việt Nam. Nếu sai, tôi hoàn toàn chịu trách nhiệm trước pháp luật.

TÁC GIẢ LUẬN VĂN Nguyễn Thị Thùy

Số hóa bởi Trung tâm Học liệu
1.1.1. Khai phá dữ liệu 3
1.1.2. Tính riêng tư 3
1.1.3. Khai phá dữ liệu đảm bảo tính riêng tư 3
1.2. Khai phá luật kết hợp 4
1.2.1. Luật kết hợp 4
1.2.2. Khai phá luật kết hợp 6
1.3. Các phương pháp khai phá luật kết hợp có đảm bảo tính riêng tư. 6
1.3.1. Khai phá luật kết hợp có đảm bảo tính riêng tư với dữ liệu tập trung 7
1.3.2. Khai phá luật kết hợp có đảm bảo tính riêng tư với dữ liệu phân tán 8
1.3.2.1. Khai phá dữ liệu trong mô hình phân tán 8
1.3.2.2. Phân tán ngang 8
1.3.3. Ẩn các luật nhạy cảm trong khai phá luật kết hợp 11
1.4. Một số kỹ thuật khai phá luật kết hợp có đảm bảo tính riêng tư 11
1.4.1. Phương pháp biến đổi dữ liệu 11
1.4.2. Sử dụng thành viên thứ ba đáng tin cậy 11
1.4.3. Tính toán đa thành viên bảo mật 13
Chƣơng 2. MỘT SỐ PHƢƠNG PHÁP TÌM LUẬT KẾT HỢP 17
2.1. Bài toán tìm luật kết hợp. 17

Số hóa bởi Trung tâm Học liệu 6
2.1.1. Phát biểu bài toán. 17
2.1.2. Ví dụ 17
2.2. Thuật toán Apriori 18
2.2.1. Nguyên lí Apriori 19
2.2.2. Thuật toán Apriori 19
2.3. Thuật toán khai phá luật kết hợp phân tán 22
2.3.1. Thuật toán khai phá luật kết hợp phân tán nhanh(FDM) 22


Số hóa bởi Trung tâm Học liệu 8
DANH MỤC CÁC TỪ VIẾT TẮT

A.sup:
Ðộ hỗ trợ toàn cục của itemset A (tính theo số lần xuất hiện)
A.supi:
Ðộ hỗ trợ cục bộ của itemset A tại site i (tính theo số lần xuất
hiện)
conf:
Ðộ tin cậy (toàn cục) tối thiểu
CSDL:
Cơ sở dữ liệu
DB:
Cơ sở dữ liệu tập trung hay toàn cục
DBi:
Cơ sở dữ liệu cục bộ tại site i
FI:
Tập itemset phổ biến
FIi:
Tập itemset phổ biến cục bộ tại site i
KTDL:
Khai thác dữ liệu
MFI:
Tập itemset tối đại
MFIi:
Tập itemset tối đại cục bộ tại site i
Số hóa bởi Trung tâm Học liệu 10
DANH MỤC CÁC HÌNH VẼ

Hình 1.1. Quá trình khai phá luật kết hợp trên CSDL tập trung 7
Hình 1.2. Giao thức sử dụng Trusted-party 13
Hình 1.3. Mô hình tính toán SMC 14
Hình 2.1. CSDL giao dịch 18
Hình 2.2. Quá trình tìm tập phổ biến 18
Hình 3.1. SecureSum(): Tính tổng bảo mật các V
i
(0 ≤ i ≤ M-1) 34
Hình 3.2a. Giai đoạn 1 của ví dụ sử dụng SecureSum 35
Hình 3.2b. Giai đoạn 2 của ví dụ về sử dụng SecureSum 36
Hình 3.3. Một ví dụ minh họa CRDM 39
Hình 3.4.Giai đoạn 1, tìm itemset ứng viên chung 44
Hình 3.5. Giai đoạn 2, tính độ hỗ trợ toàn cục 46
Hình 3.6. Giao thức sử dụng Semi-trusted-mixer 47
Hình 3.7. Giai đoạn 1 ví dụ về thuật toán Two – MixerSum 52
Hình 3.8. Giai đoạn 2 ví dụ về thuật toán Two – MixerSum 53
Hình 3.9. Giao diện chính của chương trình 57
Hình 3.10. Tiến trình thử nghiệm của chương trình 58
Hình 3.11. Giao diện kết quả chương trình 58
Hình 3.12. Giao diện chương trình 62
Hình 3.13. Tiến trình thử nghiệm 63
Hình 3.14. Kết quả chương trình 63


Số hóa bởi Trung tâm Học liệu 2
tư với dữ liệu tập trung và trên các hệ thống phân tán, một số tiêu chí đánh
giá.
Chương 2: Một số phương pháp khai phá luật kết hợp.
Ở chương 2 chúng ta sẽ tìm hiểu về một số phương pháp tìm luật kết
hợp, khai phá luật kết hợp trong dữ liệu phân tán.
Chương 3: Một số thuật toán khai phá luật kết hợp có đảm bảo tính riêng tư
trong môi trường phân tán ngang.
Chương này sẽ tập chung nghiên cứu về một số thuật toán khai phá luật
kết hợp có đảm bảo tính riêng tư trong môi trường phân tán ngang. Trong đó
tập trung vào 2 thuật toán chính là: Phương pháp dựa trên tổng bảo mật chống
lại sự thông đồng và phương pháp tiếp cận theo hướng FI. Đồng thời trình bày
đề mô thuật toán Secure Sum và cải tiến thuật toán.

Số hóa bởi Trung tâm Học liệu 3
Chƣơng 1
TỔNG QUAN VỀ KHAI PHÁ LUẬT KẾT HỢP
CÓ ĐẢM BẢO TÍNH RIÊNG TƢ
1.1. Một số khái niệm cơ bản
1.1.1. Khai phá dữ liệu
Khai phá dữ liệu (KPDL) là các kỹ thuật để rút trích tri thức từ lượng
dữ liệu lớn và được xem là giai đoạn chính trong quá trình khám phá tri thức.
KPDL được ứng dụng trong nhiều lĩnh vực như tiếp thị, kinh doanh, khám

- Toàn bộ tập các mục I={i
1
,i
2
, i
k
} “tất cả các mặt hàng”. Một giao dịch
là một tập con của I: T I. Mỗi giao dịch T có một định danh T
ID.
- A là một tập mục A I và T là một giao dịch: Gọi T chứa A nếu
A T .
* Luật kết hợp.
- Gọi A → B là một “luật kết hợp” nếu A T, B T và A
B=
.
- Luật kết hợp A→B có độ hỗ trợ (support) s trong CSDL giao dịch D
nếu trong D có s% các giao dịch T chứa AB:chính là xác suất P(AB). Tập
mục A có P(A) ≥s>0 (với s cho trước) được gọi là tập phổ biến (frequent set).
Luật kết hợp A→B có độ tin cậy (confidence) c trong CSDL D nếu như trong
D có c% các giao dịch T chứa A thì cũng chứa B: chính là xác suất P(B│A).
- Support (A→B) = P(
B) :1
≥s(A→B)≥0
- confidence (A→B) = P(B│A)
:1
≥c(A→B)≥0
- Luật A→B được gọi là bảo đảm độ hỗ trợ s trong D nếu s(A→B)≥s.
Luật A → B được gọi là bảo đảm độ tin cậy c trong D nếu c(A→B)≥c.
Độ hỗ trợ (Support)


)(
)(
Xn
YXn
(2.3)
Trong đó: n(X) là số giao dịch chứa X
* Một số ví dụ về luật kết hợp.

Số hóa bởi Trung tâm Học liệu 6
Ví dụ 1.2.1 80% khách hàng mua tạp chí thể thao thì đều mua tạp chí
về về ô tô =>sự kết hợp giữa tạp chí thể thao với tạp chí về về ô tô . (80% là
độ tin cậy của luật)
Ví dụ 1.2.2 Ngân hàng muốn thu thập thông tin về lịch sử tín dụng của
khách hàng thấy có một luật: 75% khách hàng vay mua nhà và mua xe và có
thu nhập hàng tháng dưới 7 triệu thì không có khả năng thanh toán nợ => sự
kết hợp giữa vay mua nhà và mua xe, có thu nhập dưới 7 triệu với khả năng
thanh toán nợ.(75% là độ tin cậy của luật).
Ví dụ 1.2.3 20% trên tổng số khách hàng có tài khoản tiết kiệm có thu
nhập lớn hơn hoặc bằng 60 triệu một năm với độ tin cậy là 100%.
Thu nhập= 60.000.000_max →Tài khoản tiết kiệm= yes [20% ; 100%]
1.2.2. Khai phá luật kết hợp
Khai phá luật kết hợp: là tìm các mẫu phổ biến, sự kết hợp, sự tương
quan, hay các cấu trúc nhân quả giữa các tập đối tượng trong các cơ sở dữ liệu
giao tác được gọi là các luật kết hợp.
Các ứng dụng: Luật kết hợp có ứng dụng trong nhiều lĩnh vực khác
nhau của đời sống như: khoa học, hoạt động kinh doanh, tiếp thị, thương mại,
phân tích thị trường chứng khoán, tài chính và đầu tư,

hàng hoá vào mùa hè sắp tới để có phương pháp huy động vốn và đầu tư mặt
hàng cho phù hợp và hiệu quả. Họ sẽ cung cấp dữ liệu cho chuyên gia để
nghiên cứu, tuy nhiên họ lại không muốn để lộ các thông tin về bán hàng của
họ. Để làm được việc này họ đã biến đổi dữ liệu trước khi chuyển giao cho
việc nghiên cứu.
CSDL
Gốc
Biến đổi
Tri thức
CSDL
Đã biến đổi
KPDL

Số hóa bởi Trung tâm Học liệu 8
Ví dụ 1.3.2 Một ngân hàng thực hiện khai phá dữ liệu nghiên cứu về
khả năng thanh toán nợ của khách hàng dựa trên lịch sử tín dụng của khách
hàng trên CSDL của họ. Họ sẽ cung cấp dữ liệu cho chuyên gia để nghiên
cứu, tuy nhiên họ lại không muốn để lộ các thông tin của khách hàng. Để làm
được việc này họ đã biến đổi dữ liệu trước khi chuyển giao cho việc nghiên
cứu.
1.3.2. Khai phá luật kết hợp có đảm bảo tính riêng tư với dữ liệu phân tán
1.3.2.1. Khai phá dữ liệu trong mô hình phân tán
Giả thiết rằng tập dữ liệu được phân tán thành nhiều phần theo chiều
ngang hoặc theo chiều dọc trên một nhóm các tổ chức (thành viên), mỗi thành
viên sở hữu một tập dữ liệu riêng. Vấn đề đặt ra là làm thế nào để các tổ chức
có thể chia sẻ tập dữ liệu cho nhau nhằm khai phá ra các luật kết hợp trên tập
dữ liệu liên kết của các thành viên, trong khi vẫn bảo vệ được tính riêng tư

21/12/1992
Hà Nội
098998986x

…… Ví dụ 1.3.3 Ngân hàng Nhà nước thực hiện khai phá dữ liệu nghiên
cứu về khả năng thanh toán nợ của khách hàng dựa trên lịch sử tín dụng của
khách hàng trên CSDL của các ngân hàng thương mại. Nhưng các ngân hàng
này không muốn để lộ thông tin khách hàng cho các ngân hàng khác. Khi đó
yêu cầu đặt ra là phải thực hiện khai phá luật kết hợp ứng dụng trên CSDL
phân tán ngang đảm bảo tính riêng tư.

Số hóa bởi Trung tâm Học liệu 10
1.3.2.3. Phân tán dọc
Các site thu thập các đặc trưng khác nhau của cùng tập thực thể, ví dụ:
Bệnh viện thu thập các thông tin về bệnh nhân, các chứng bệnh. Nhà cung cấp
dịch vụ viễn thông cung cấp về thông tin khách hàng, thời gian gọi điện, thời
lượng gọi điện…
Tổng hợp 2 cơ sở dữ liệu này lại để nghiên cứu về một mối tương quan
giữa các bệnh có thể sinh ra do nguyên nhân sử dụng điện thoại di động
Bảng 1.2. Ví dụ về mô hình dữ liệu phân tán dọc
Dữ liệu toàn cục

không
………

Số hóa bởi Trung tâm Học liệu 11 1.3.3. Ẩn các luật nhạy cảm trong khai phá luật kết hợp
Trong quá trình khai phá dữ liệu có thể có những luật nhạy cảm không
muốn bị lộ ra, ví dụ: Trong ngân hàng có một số luật được tìm thấy nhưng lại
rất nhạy cảm, ngân hàng không muốn tiết lộ ra vì nếu tiết lộ ra sẽ làm ảnh
hưởng đến khách hàng, hoặc ảnh hưởng đến ngân hàng, giả dụ như khách
hàng sử dụng dịch vụ A và sử dụng dịch vụ B thì thường dẫn đến không có
khả năng thanh toán nợ…
Chính vì lí do đó nên trong bài toán khai phá luật kết hợp có đảm bảo
tính riêng tư chúng ta cần tính đến việc ẩn đi các luật nhạy cảm.
1.4. Một số kỹ thuật khai phá luật kết hợp có đảm bảo tính riêng tƣ
1.4.1. Phương pháp biến đổi dữ liệu
Tư tưởng của phương pháp biến đổi dữ liệu là trước khi đưa dữ liệu vào
khai phá thì dữ liệu sẽ được biến đổi, tuy nhiên việc biến đổi chỉ nhằm che
dấu những thông tin nhạy cảm mà không làm ảnh hưởng đến kết quả tính
toán. Một trong những phương pháp thường được sử dụng trong trường hợp
này là phương pháp cộng nhiễu.
1.4.2. Sử dụng thành viên thứ ba đáng tin cậy
Thành viên thứ 3 đáng tin cậy (Trusted-party) là một thành viên bên

giao thức với thành viên thứ ba đáng tin cậy, mỗi thành viên tham gia gửi yếu
tố đầu vào tới thành viên thứ ba đáng tin cậy này và chỉ nhận lại kết quả tính
toán. SMC giả lập thành viên thứ ba đáng tin cậy này dựa vào một giao thức
giữa các thành viên [7] như trong hình 1.3.

DB
1
DB
2
DB
n
TP
TP

TP

TP Số hóa bởi Trung tâm Học liệu 14

Hình 1.3. Mô hình tính toán SMC
Đã có nhiều giao thức SMC được đề xuất như: tính tổng an toàn, phép
giao an toàn, phép hợp an toàn, tích vô hướng an toàn. Ta có thể kết hợp các
giao thức con để tạo ra các giao thức an toàn mới, nếu thuật toán/giao thức
phụ thuộc vào một số giao thức con, việc thực hiện các giao thức con hiệu quả
sẽ cải thiện đáng kể hiệu quả tổng thể.