ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC BÁCH KHOA

HUỲNH VĂN QUỐC PHƯƠNG

BẢO VỆ TÍNH RIÊNG TƯ TRONG KHAI PHÁ
DỮ LIỆU
Chuyên ngành: Khoa học Máy tính

LUẬN VĂN THẠC SĨ

TP. HỒ CHÍ MINH, tháng 04 năm 2010


CƠNG TRÌNH ĐƯỢC HỒN THÀNH TẠI
TRƯỜNG ĐẠI HỌC BÁCH KHOA
ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH

Cán bộ hướng dẫn khoa học :

TS. Đặng Trần Khánh
TS. Võ Thị Ngọc Châu

Cán bộ chấm nhận xét 1 : ................................................................................

Cán bộ chấm nhận xét 2 : ................................................................................

Luận văn thạc sĩ được bảo vệ tại

HỘI ĐỒNG CHẤM BẢO VỆ LUẬN VĂN THẠC SĨ
TRƯỜNG ĐẠI HỌC BÁCH KHOA, ngày . . . . tháng . . . . năm 2010.

TRƯỜNG ĐẠI HỌC BÁCH KHOA
KHOA KHOA HỌC MÁY TÍNH

CỘNG HỒ XÃ HỘI CHỦ NGHĨA VIỆT NAM
Độc Lập - Tự Do - Hạnh Phúc
Tp. HCM, ngày . . . . . tháng . . . . . năm 2010

NHIỆM VỤ LUẬN VĂN THẠC SĨ
Họ và tên học viên:

Huỳnh Văn Quốc Phương . . . . . . . . Phái:

Nam . . . . . . . .

Ngày, tháng, năm sinh: 15-01-1983. . . . . . . . . . . . . . . . . . . . Nơi sinh: Phú Yên . . . . . .
Chuyên ngành:

Khoa học Máy tính . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

MSHV:

00708206. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1- TÊN ĐỀ TÀI: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
BẢO VỆ TÍNH RIÊNG TƯ TRONG KHAI PHÁ DỮ LIỆU. . . . . . . . . . . . . .
2- NHIỆM VỤ LUẬN VĂN: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.......................................................................
.......................................................................

.......................................................................
.......................................................................
.......................................................................
3- NGÀY GIAO NHIỆM VỤ : . . . . . . . . . . . . . . . . . . . . .

4- NGÀY HOÀN THÀNH NHIỆM VỤ : . . . . . . . . . . . . . . . . . . . . .
5- HỌ VÀ TÊN CÁN BỘ HƯỚNG DẪN: TS. Đặng Trần Khánh. . . . . . . . . . . . .
TS. Võ Thị Ngọc Châu . . . . . . . . . . . .
Nội dung và đề cương Luận văn thạc sĩ đã được Hội Đồng Chun Ngành thơng qua.
CÁN BỘ HƯỚNG DẪN
CHỦ NHIỆM BỘ MƠN
KHOA QL CHUYÊN NGÀNH
(Họ tên và chữ ký)
QUẢN LÝ CHUYÊN NGÀNH
(Họ tên và chữ ký)
(Họ tên và chữ ký)


LỜI CAM ĐOAN

Tôi cam đoan rằng, ngoại trừ các kết quả tham khảo từ các cơng trình khác như
đã ghi rõ trong luận văn, các cơng việc trình bày trong luận văn này là do chính tơi
thực hiện và chưa có phần nội dung nào của luận văn này được nộp để lấy một
bằng cấp ở trường này hoặc trường khác.

Ngày 08 tháng 04 năm 2010

Huỳnh Văn Quốc Phương

ii



LỜI CẢM ƠN

Tôi xin gởi lời cảm ơn chân thành và sâu sắc nhất đến TS. Đặng Trần Khánh và
TS. Võ Thị Ngọc Châu. Cám ơn thầy và cô đã tận tình hướng dẫn, định hướng tơi từ
cách đặt vấn đề, phương pháp nghiên cứu khoa học, đến những công việc cụ thể trong
luận văn này.
Tôi cũng xin cảm ơn gia đình đã động viên và tạo mọi điều kiện tốt nhất để tơi có
thể tiếp tục theo đuổi việc học tập nghiên cứu. Tôi trân trọng dành tặng thành quả của
luận văn này cho Cha Mẹ. Nhờ công lao dưỡng dục của Người mà chúng con mới có
được thành quả như ngày hôm nay. Con xin hứa sẽ tiếp tục cố gắng phấn đấu để vươn
cao hơn nữa.

Huỳnh Văn Quốc Phương

iii


TĨM TẮT ĐỀ TÀI
Bảo vệ tính riêng tư trong khai phá dữ liệu (PPDM – Privacy Preserving Data
Mining) là một lĩnh vực còn khá mới mẻ, nhất là ở Việt Nam hiện nay. Đây là một
lĩnh vực phát sinh trực tiếp từ lĩnh vực phát hiện tri thức và khai phá dữ liệu (KDD Knowledge Discovery and Data Mining) vì trong q trình khai thác dữ liệu, nguy cơ
những thơng tin nhạy cảm có thể bị phơi bày, lạm dụng ảnh hưởng không tốt đến các
cá nhân, tổ chức liên quan.
PPDM đã phát triển với nhiều phương pháp, mơ hình khác nhau như: k-nặc danh
(k-anonymity), nhiễu hóa, hốn đổi … để bảo vệ tính riêng tư của dữ liệu trong khi cố
gắng duy trì tối đa có thể giá trị khai thác của nó. Hiện tại chưa có một kỹ thuật, giải
thuật nào duy trì giá trị khai thác theo một kỹ thật khai phá dữ liệu cụ thể nào đó mà
chỉ cố gắng duy trì sự khác biệt ít nhất giữa dữ liệu gốc và dữ liệu đã thay đổi rất

chung chung.
Trong phần này, đề tài đề ra hướng tiếp cận mới là: thực hiện q trình che dấu
tính riêng tư cá thể trong dữ liệu đồng thời duy trì giá trị khai thác dữ liệu lớn nhất có
thể theo một kỹ thuật khai phá dữ liệu cụ thể nào đó.
Đề tài sẽ cụ thể hóa hướng tiếp cận mới mà đề tài đề xuất ra bằng cách đề xuất
kỹ thuật Migrate Member để đạt mơ hình k-nặc danh và giải thuật M3AR cho kỹ thuật
này để chống lại khả năng tái xác định cá thể đồng thời phải duy trì tối đa có thể các
luật kết hợp của dữ liệu gốc.

iv


ABSTRACT
Privacy Preserving Data Mining (PPDM) is rather a new field, specially in
Vietnam. This field arose directly from the area of Knowledge Discovery and Data
Mining as during data mining sensitive information may be exposed and imposed,
that will impact on related individuals and organizations.
PPDM has developed with various methods, models such as: k-anonymity,
perturpation, data swapping… to preserve the privacy of data while trying to maitain
as much as possible its utility. However, up to now, there is not any technique,
algorithm to maintain utility for a specific data mining technique; current techniques,
algorithms only try to maintain the least difference between orgirinal and modified
data that is over general.
This thesis proposes a new approach: performing individual privacy preserving in
data and at the same time, maintaing data utility as much as possible according to a
specific data mining technique.
This thesis will concretize the above proposed approach by offering the Migrate
Member technique to optain k-anonymity model and M3AR algorithm for this
technique to resist the possibility of reidentifying individuals and maintain as much as
possible the association rules of original data.


v


Mục lục

MỤC LỤC
Trang
DANH MỤC BẢNG ........................................................................................................ viii
DANH MỤC HÌNH ............................................................................................................ix
CHƯƠNG 1: GIỚI THIỆU.................................................................................................1
1.1 Phát biểu vấn đề.........................................................................................................1
1.2 Tên đề tài....................................................................................................................5
1.3 Phạm vi đề tài ............................................................................................................5
1.4 Mục tiêu đề tài ...........................................................................................................6
1.5 Phương pháp thực hiện .............................................................................................6
CHƯƠNG 2: TỔNG QUAN CÁC PHƯƠNG PHÁP BẢO VỆ TÍNH RIÊNG TƯ
TRONG KHAI PHÁ DỮ LIỆU ..........................................................................................7
2.1 Phương pháp ngẫu nhiên..........................................................................................7
2.1.1 Nhiễu hóa dựa trên cộng nhiễu..........................................................................7
2.1.2 Nhiễu hóa dựa trên nhân nhiễu .........................................................................8
2.1.3 Hốn đổi dữ liệu .................................................................................................8
2.2 Phương pháp nặc danh dựa trên nhóm ....................................................................9
2.2.1 k-Nặc danh .......................................................................................................10
2.2.2 l-Đa dạng ..........................................................................................................10
2.2.3 t-Gần nhau .......................................................................................................11
2.3 Bảo vệ tính riêng tư trong khai phá dữ liệu phân tán ...........................................14
2.4 Bảo vệ tính riêng tư của kết quả ứng dụng............................................................16
2.4.1 Che dấu luật kết hợp.........................................................................................16
2.4.2 Thu giảm tính hiệu quả bộ phân lớp ................................................................17

2.4.3 Điều khiển suy diễn và kiểm soát truy vấn......................................................17
CHƯƠNG 3: PHƯƠNG PHÁP K-NẶC DANH...............................................................19
3.1 Tổng quan phương pháp k-nặc danh.....................................................................19
3.1.1 Kỹ thuật tổng quát hóa .....................................................................................20
3.1.2 Kỹ thuật loại bỏ.................................................................................................23
3.2 Một số giải thuật cho k-nặc danh ...........................................................................23
3.2.1 Giải thuật của Samarati....................................................................................24
3.2.2 Giải thuật của Bayardo và Agrawal .................................................................26
3.2.3 Giải thuật của LeFevre, DeWitt and Ramakrishnan.......................................29
3.3 Các cách tiếp cận đảm bảo k-nặc danh trong khai phá dữ liệu .............................31
3.3.1 Nặc danh – và – Khai phá.................................................................................31
3.3.2 Khai phá – và – Nặc danh.................................................................................33
CHƯƠNG 4: PHƯƠNG PHÁP HOÁN ĐỔI DỮ LIỆU ..................................................39
4.1 Giới thiệu..................................................................................................................39
4.2 Giải pháp mơ hình hóa hốn đổi dữ liệu như một bài tốn quyết định.................40
4.2.1 Đặc tả cấu hình hốn đổi ..................................................................................40
4.2.2 Khơng gian cấu hình hốn đổi..........................................................................41
4.2.3 Độ đo rủi ro .......................................................................................................42
4.2.4 Độ đo tiện ích.....................................................................................................43

vi


Mục lục
4.2.5 Lựa chọn cấu hình hốn đổi từ độ đo rủi ro và độ đo tiện ích ........................44
4.2.6 Một số giải thuật ...............................................................................................46
4.3 Giải pháp hoán đổi xấp xỉ dựa trên xếp loại ...........................................................48
4.3.1 Giải thuật...........................................................................................................48
4.3.2 Một số tăng cường cho giải thuật hoán đổi xấp xỉ dựa trên xếp loại ..............49
4.4 Những ưu và nhược điểm của kỹ thuật hoán đổi dữ liệu .......................................51

4.4.1 Ưu điểm .............................................................................................................51
4.4.2 Nhược điểm .......................................................................................................51
CHƯƠNG 5: PHƯƠNG PHÁP NHIỄU HÓA DỰA TRÊN CỘNG NHIỄU..................52
5.1 Giới thiệu..................................................................................................................52
5.2 Độ đo tính riêng tư và độ đo mất mát thơng tin .....................................................52
5.2.1 Độ đo tính riêng tư............................................................................................52
5.2.2 Độ đo mất mát thông tin ...................................................................................54
5.3 Tái cấu trúc dữ liệu gốc ...........................................................................................55
5.3.1 Tái cấu trúc dựa trên phân phối nhiễu ............................................................55
5.3.2 Tái cấu trúc dựa trên phân phối đơn biến .......................................................55
5.3.3 Phương pháp của Agrawal và Srikant .............................................................57
5.3.4 Phương pháp cực đại hóa mong đợi.................................................................58
CHƯƠNG 6: HƯỚNG TIẾP CẬN ĐỀ TÀI VÀ GIẢI PHÁP .........................................60
6.1 Hướng tiếp cận đề tài...............................................................................................60
6.2 Giải pháp..................................................................................................................62
6.2.1 Định dạng dữ liệu..............................................................................................62
6.2.2 Vấn đề cần giải quyết........................................................................................63
6.2.3 Phân tích sự phù hợp của các kỹ thuật trong phương pháp k-nặc danh cho
vấn đề của đề tài ........................................................................................................65
6.2.4 Kỹ thuật Di trú Thành viên ..............................................................................69
6.2.5 Tác động của phép di trú thành viên lên luật kết hợp.....................................75
6.2.6 Đánh giá chất lượng dữ liệu biến đổi D’ so với dữ liệu gốc D .........................83
6.2.7 Chính sách và giải thuật M3AR .......................................................................85
6.2.8 Ước lượng độ phức tạp của giải thuật..............................................................92
6.2.9 Ảnh hưởng của min_sup và min_conf lên giải thuật........................................95
CHƯƠNG 7: CHƯƠNG TRÌNH HIỆN THỰC VÀ KIỂM THỬ...................................97
7.1 Chương trình hiện thực...........................................................................................97
7.1.1 “DMX Script” tab .............................................................................................97
7.1.2 “Dataset Mining” tab........................................................................................98
7.1.3 “Dataset” Tab....................................................................................................99

7.1.4 “Anonymity” tab.............................................................................................100
7.2 Kiểm thử ................................................................................................................102
CHƯƠNG 8: TỔNG KẾT...............................................................................................109
8.1 Tổng kết những công việc đã làm..........................................................................109
8.2 Những đóng góp của luận văn...............................................................................110
8.3 Hướng phát triển đề tài .........................................................................................111
TÀI LIỆU THAM KHẢO...............................................................................................113
PHỤ LỤC A: CÔNG CỤ KHAI PHÁ DỮ LIỆU ...........................................................117
PHỤ LỤC B: DMX SCRIPT DÙNG TRONG KIỂM THỬ..........................................134

vii


Danh mục bảng

DANH MỤC BẢNG
Bảng 2.1: Thông tin bệnh nhân............................................................................................11
Bảng 2.2: Thông tin bệnh nhân đã bị nặc danh (3-anonymity) .............................................11
Bảng 2.3: Thông tin tiền lương - bệnh .................................................................................12
Bảng 2.4: Thông tin tiền lương - bệnh đã 3-diversity ...........................................................13
Bảng3.1: Một ví dụ đơn giản về bảng riêng tư .....................................................................19
Bảng 3.2: Tổng qt hóa bảng 3.1 dựa trên thuộc tính Sex...................................................21
Bảng 3.3: Tổng qt hóa bảng 3.2 dựa trên thuộc tính Marital status ...................................22
Bảng 3.4: Tổng quát hóa bảng 3.3 dựa trên thuộc tính Marital status ...................................22
Bảng 3.5: Tổng qt hóa bảng 3.4 dựa trên thuộc tính Hour ................................................22
Bảng 3.6: Tổng qt hóa bảng 3.5 dựa trên thuộc tính Hour ................................................22
Bảng 3.7: Phân loại các kỹ thuật k-nặc danh.......................................................................23
Bảng 3.8: Ví dụ đơn giản về bảng riêng tư...........................................................................25
Bảng 3.9: Tổng quát bảng 3.8 dựa trên <M0,S1>..................................................................25
Bảng 3.10: Tổng quát bảng 3.8 dựa trên <M1,S0>................................................................26

Bảng 3.11: Ví dụ đơn giản về bảng riêng tư.........................................................................30
Bảng 3.12: Ví dụ đơn giản về bảng riêng tư.........................................................................34
Bảng 3.13: Các itemset và độ hỗ trợ tương ứng của bảng 3.12 .............................................35
Bảng 6.1: Dữ liệu sinh viên tổng hợp...................................................................................64
Bảng 6.2: Nhóm các bộ giá trị dựa trên các thuộc tính QI từ bảng 6.1..................................64
Bảng 6.3: Dữ liệu điểm sinh viên tổng hợp ..........................................................................70
Bảng 6.4: 3-nặc danh hóa của bảng 6.3................................................................................71
Bảng 6.5 Trình tự di chuyển thành viên giữa các nhóm và độ rủi ro tương ứng ....................73
Bảng 6.6 Thiên vị giảm nhóm khơng an tồn trong ước lượng độ rủi ro...............................74
Bảng 6.7 Bảng dữ liệu ngẫu nhiên .......................................................................................79
Bảng 6.8 Tập các luật kết hợp sinh ra từ bảng 6.7 ................................................................80
Bảng 6.9 Bảng thơng tin các nhóm từ bảng 6.7....................................................................80
Bảng 6.10 Liệt kê các trường hợp tăng giảm số nhóm của các danh sách. ............................94
Bảng 6.11 Số lần SelectedG xem xét chuyển đổi với các nhóm khác qua mỗi lần lặp ..........95
Bảng A.1 Mining_Services Schema Rowset ......................................................................125
Bảng A.2 Service_Parameters Schema Rowset..................................................................126
Bảng A.3 Mining_Models Schema Rowset........................................................................126
Bảng A.4 Mining_Columns schema Rowset ......................................................................127
Bảng A.5 Mining_Model_Content Schema Rowset ...........................................................128
Bảng A.6 Mining_Functions Schema Rowset ....................................................................128
Bảng A.7 Model_PMML Schema Rowset .........................................................................129
Bảng A.8 Mining Structure Schema Rowset ......................................................................131

viii


Danh mục hình

DANH MỤC HÌNH
Hình 1.1 Nhóm các kỹ thuật tác động lên dữ liệu gốc D ........................................................2

Hình 1.2 Nhóm các kỹ thuật tác động lên kết quả khai thác dữ liệu D....................................3
Hình 2.1: Dữ liệu phân tán theo chiều ngang .......................................................................15
Hình 2.2: Dữ liệu phân tán theo chiều dọc ...........................................................................15
Hình 3.1: Phân cấp tổng qt hóa thuộc tính Marital_status.................................................21
Hình 3.2: Phân cấp tổng qt hóa thuộc tính Sex .................................................................21
Hình 3.3: Phân cấp tổng qt hóa thuộc tính Hour ...............................................................21
Hình 3.4: Phân cấp tổng qt hóa trên tập thuộc tính marital_status và sex ..........................25
Hình 3.5: Các chỉ số tương ứng các giá trị của tập thuộc tính marital_status và sex..............27
Hình 3.6: Cây liệt kê tập con của tập I = {1, 2, 3}................................................................28
Hình 3.7: Các bước phân chia bảng 3.11 thỏa mãn 10-anonymity........................................30
Hình 3.8: Cây quyết định dựa trên bảng 3.12.......................................................................36
Hình 3.9: Loại bỏ kênh suy diễn từ hình 3.8 ........................................................................37
Hình 3.10: Loại bỏ kênh suy diễn từ hình 3.8 .....................................................................38
Hình 4.1: Risk–Utility Frontiers ..........................................................................................46
Hình 5.1: Độ đo mất mát thơng tin của phân phối ước lượng ...............................................54
Hình 6.1 Hướng tiếp cận mới ..............................................................................................62
Hình 6.2: Định dạng dữ liệu cho k-nặc danh ........................................................................63
Hình 6.3 Mơ tả các thuộc tính thành phần trong phép biến đổi thành viên m........................81
Hình 6.4 Minh họa sự khác biệt tập luật kết hợp của dữ liệu D và D’...................................84
Hình 6.5 Sơ đồ flowchart của giải thuật ...............................................................................85
Hình 6.6 Cấu trúc dữ liệu cơ bản của giải thuật....................................................................88
Hình 6.7 Giải thuật M3AR ..................................................................................................91
Hình 6.8 Hàm Disperse .......................................................................................................92
Hình 7.1 Tab “DMX Script” của giao diện chương trình......................................................98
Hình 7.2 Tab “Dataset Mining” của giao diện chương trình.................................................99
Hình 7.3 Tab “Dataset” của giao diện chương trình ...........................................................100
Hình 7.4 Tab “Anonymity” của giao diện chương trình .....................................................101
Hình 7.5 Giao diện hiện thực giải thuật KACA..................................................................101
Hình 7.6 Giao diện hiện thực giải thuật Bottom-Up ...........................................................102
Hình 7.7 Giao diện hiện thực giải thuật OKA ....................................................................102

Hình 7.8 Phân phối của thuộc tính “age” trong dữ liệu Adult .............................................103
Hình 7.9 Phân phối của thuộc tính “marital” trong dữ liệu Adult .......................................103
Hình 7.10 Phân phối của thuộc tính “gender” trong dữ liệu Adult ......................................104
Hình 7.11 Phân phối của thuộc tính “race” trong dữ liệu Adult ..........................................104
Hình 7.12 Phân phối của thuộc tính “edu” trong dữ liệu Adult...........................................104
Hình 7.13 Phân phối của thuộc tính “h_p_w” trong dữ liệu Adult......................................105
Hình 7.14 Phân phối của thuộc tính “income” trong dữ liệu Adult .....................................105
Hình 7.15 Phân phối của thuộc tính “workclass” trong dữ liệu Adult .................................105
Hình 7.16 Biểu đồ kết quả thực nghiệm trên dữ liệu Adult.................................................107
Hình 7.17 Số liệu thực nghiệm trên dữ liệu Adult ..............................................................108
Hình A.1 Mơ tả Prediction Join .........................................................................................124
Hình A.2 Nội dung mơ hình của luật kết hợp.....................................................................133

ix


Chương 1: Giới thiệu

CHƯƠNG 1: GIỚI THIỆU
1.1 Phát biểu vấn đề
Ngày nay, những tiến bộ trong kỹ thuật phần cứng đã làm tăng khả năng xử lý
cũng như khả năng lưu trữ vô cùng lớn dữ liệu cá nhân của khách hàng và các cá thể
khác nhau. Dữ liệu này có thể được tích lũy qua nhiều năm thậm chí là hàng chục
năm, kết quả là các khối dữ liệu khổng lồ được tạo ra và được lưu trữ bởi các tổ chức
khác nhau.
Từ đây, người ta có nhu cầu phân tích các khối dữ liệu khổng lồ này để có thể
trích rút ra những thơng tin, tri thức có ích cho hoạt động của mỗi tổ chức. Với nhu
cầu này, một khuynh hướng kỹ thuật mới ra đời, đó là kỹ thuật phát hiện tri thức và
khai phá dữ liệu (KDD - Knowledge Discovery and Data Mining) với nhiều phương
pháp và giải thuật hiệu quả khác nhau.

Tuy nhiên trong quá trình khai thác, dữ liệu cá nhân cũng như thơng tin nhạy cảm
có thể bị phơi bày, lạm dụng cho những mục đích khác nhau. Như một tất yếu, nhu
cầu mới được đặt ra là làm sao có thể cho phép khai thác dữ liệu nhưng không cho
phép hoặc hạn chế khả năng xác định dữ liệu riêng tư của một cá thể nào đó cũng như
che dấu, hạn chế các thông tin, qui luật nhạy cảm khỏi các giải thuật khai phá dữ liệu.
Đáp ứng nhu cầu này, một số các kỹ thuật đã được đề xuất để bảo vệ tính riêng tư
khỏi các giải thuật khai phá dữ liệu, được gọi chung là các kỹ thuật bảo vệ tính riêng
tư trong khai phá dữ liệu (PPDM - Privacy-Preversing Data Mining).
Một cách chung nhất, các kỹ thuật PPDM cố gắng thay đổi (modifying) hay
chuyển đổi (transforming) dữ liệu gốc theo một cách nào đó để có thể đảm bảo được
tính riêng tư trong khi vẫn cho phép khai thác tri thức ẩn chứa bên trong dữ liệu (xem
hình 1.1). Hơn nữa, một số kỹ thuật có cách tiếp cận khác là lược bỏ đi một số kết quả
khai thác được bởi các giải thuật khai phá dữ liệu trước khi kết quả này được đưa ra
cho người sử dụng (xem hình 1.2). Sự khác biệt giữa 2 nhóm kỹ thuật này là đối với

Trang 1


Chương 1: Giới thiệu

nhóm các kỹ thuật đầu thì người nhận sẽ nhận toàn bộ dữ liệu đã thay đổi D’ từ dữ
liệu gốc D và có một cơng cụ khai phá dữ liệu riêng để khai thác trên dữ liệu D’ này.
Cịn đối với nhóm các kỹ thuật thứ hai, người nhận sẽ không được nhận dữ liệu D’ mà
chỉ được nhận kết quả khai thác trên dữ liệu gốc D.

Hình 1.1 Nhóm các kỹ thuật tác động lên dữ liệu gốc D

Trang 2



Chương 1: Giới thiệu

Hình 1.2 Nhóm các kỹ thuật tác động lên kết quả khai thác dữ liệu D
Nếu như trong các lĩnh vực bảo mật thông tin thông thường, chúng ta cố gắng hạn
chế ở một mức độ nào đó hoặc khơng cho phép truy xuất dữ liệu gốc D đối với từng
cá nhân cụ thể; thì ở PPDM vấn đề này chúng ta khơng cịn quan tâm và xem như đã
được đảm bảo, dữ liệu D sẽ được biến đổi thành D’ theo một kỹ thuật thích hợp, sau
đó D’ sẽ được đưa cho các thành phần khác (tổ chức, cơ quan, công ty, cá nhân) khai
phá tri thức bên trong dữ liệu, hiển nhiên là các thành phần khác này có tồn quyền
truy xuất lên D’ và D’ phải thõa mãn các điều kiện sau:
-

D’ khác với D và phải đảm bảo được tính riêng tư.

-

Các tri thức bên trong dữ liệu D’ không được khác biệt quá một ngưỡng
cho trước so với tri thức trong dữ liệu D.

Khi dữ liệu gốc bị thay đổi thì thơng tin trích rút từ dữ liệu này sẽ bị mất mát và
khơng cịn đầy đủ so với dữ liệu gốc. Như vậy tính hữu ích, giá trị khai thác của dữ
liệu đã bị giảm sút, tuy nhiên lúc này tính riêng tư và thông tin nhạy cảm của dữ liệu
lại được bảo vệ tốt hơn so với dữ liệu ban đầu. Nếu chúng ta quá thiên về việc bảo vệ
tính riêng tư của dữ liệu thì dữ liệu sẽ mất đi nhiều tính tin cậy và giá trị khai thác của
nó. Ngược lại nếu chúng ta quá coi trọng giá trị khai thác của dữ liệu thì dữ liệu có
Trang 3


Chương 1: Giới thiệu


nguy cơ bị lạm dụng, dẫn đến tính riêng tư bị xâm phạm. Do đó việc cân bằng giữa 2
đại lượng này sao cho hợp lý trong một trường hợp cụ thể nào đó (đối tượng khai thác
dữ liệu) cũng là một vấn đề khá quan trọng trong lĩnh vực này. Mục tiêu của PrivacyPreversing Data Mining là phải đạt được trạng thái win-win-win của: Tri thức của dữ
liệu có thể được trích rút để sử dụng, tính riêng tư của các cá thể được bảo vệ, và vật
chứa dữ liệu (data holder) được bảo vệ chống lại sự lạm dụng hay phơi bày dữ liệu
[16, chương 1, tr 3].
Ví dụ cơ sở dữ liệu y khoa của một bệnh viện được tích lũy qua nhiều năm với
các thông tin về: tên bệnh nhân, số chứng minh nhân dân, giới tính, địa chỉ, số điện
thoại, nghề nghiệp, số giờ làm việc một tuần, tuổi ... và cuối cùng là chứng bệnh mà
bệnh nhân mắc phải. Cơ sở dữ liệu này ngày một nhiều lên và có khả năng ẩn chứa
trong nó nhiều tri thức hữu ích cho việc phịng chống và chuẩn đốn bệnh. Vì vậy
người ta mong muốn khai thác dữ liệu để trích rút được các tri thức này, ví dụ như:
những người làm nghề A với số giờ làm việc vượt một ngưỡng N thì thường mắc một
chứng bệnh nào đó, hay biết được phân phối của một chứng bệnh B nào đó theo tuổi
chẳng hạn, từ đó biết được chứng bệnh B này có tùy thuộc nhiều tuổi hay khơng và
thường tập trung ở độ tuổi nào... Tuy nhiên trong quá trình khai phá, tính riêng tư của
dữ liệu có nguy cơ bị xâm phạm là điều rất có thể xảy ra, ví dụ như: khả năng xác
định chính xác một người hay thu hẹp vùng xác định người mắc chứng bệnh nghiêm
trọng nào đó. Vì thế mà người ta mong muốn thực hiện một kỹ thuật bảo vệ tính riêng
tư phù hợp tác động lên dữ liệu trước khi đưa đi khai thác; mục đích là làm sao cho
những tri thức bên trong dữ liệu có thể bị mất đi nhưng khơng vượt quá giới hạn cho
phép trong khi vẫn bảo vệ được tính riêng tư của các bệnh nhân.
Ngồi cơ sở dữ liệu y khoa ở trên còn nhiều dữ liệu khác như: dữ liệu sinh viên
(môn học, điểm số, giảng viên phụ trách ...), dữ liệu điện lực (loại sự cố, nguyên nhân,
khu vực ...), dữ liệu hình sự (nghề nghiệp, tuổi, loại tội, nguyên nhân gây án ...) ...
Các dữ liệu ví dụ này chỉ là một số rất ít trong số các dữ liệu tồn tại trong thời đại
bùng nổ số liệu và thông tin như ngày nay. Nếu dữ liệu càng lớn, càng đa dạng thì tri

Trang 4



Chương 1: Giới thiệu

thức trích rút được càng nhiều, càng phong phú và ích lợi mang lại càng to lớn, nhưng
mặt trái là nguy cơ bị lạm dụng, phơi bày của dữ liệu theo đó cũng càng lớn và tác hại
mang lại là khơng thể lường trước được. Vì vậy khơng q khi nói rằng PPDM là một
lĩnh vực rất quan trọng và không thể thiếu được; đối với thời đại thông tin như ngày
nay, PPDM thật sự trở nên cấp thiết hơn bao giờ hết.
Nhìn chung, Privacy-Preversing Data Mining (PPDM) là một lĩnh vực còn khá
mới mẻ ở Việt Nam và đang thu hút nhiều sự quan tâm của các cộng đồng liên quan
trên thế giới vì tính đặc biệt nhạy cảm của nó. Nhiều kỹ thuật PPDM khác nhau được
công bố thông qua các bài báo khoa học được đăng tải bởi các tổ chức có uy tín như:
IEEE, ACM ...Trong các cơng bố của mình, hầu hết các tác giả đều đưa ra một kỹ
thuật hay một giải thuật cụ thể để bảo vệ tính riêng tư đồng thời duy trì tri thức bên
trong dữ liệu đối với một giải thuật khai phá dữ liệu cụ thể. Đề tài này cũng khơng
phải là một ngoại lệ, vì vậy hướng nghiên cứu, công việc và mục tiêu thực hiện cũng
như các tác giả đi trước, với mong ước đóng góp một phần cơng sức của mình vào
lĩnh vực đầy nhạy cảm, cấp thiết và quan trọng này.

1.2 Tên đề tài
Bảo vệ tính riêng tư trong khai phá dữ liệu (PPDM - Privacy-Preserving Data
Mining)

1.3 Phạm vi đề tài
Lĩnh vực PPDM có rất nhiều kỹ thuật, giải thuật thuộc nhiều mơ hình, phương
pháp khác nhau như: k-nặc danh, nhiễu hóa, hốn đổi, mã hóa … Tuy nhiên đề tài sẽ
tập trung vào việc nghiên cứu và đề xuất ra một kỹ thuật, giải thuật thuộc mơ hình knặc danh.
Đề tài không quan tâm đến kết quả khai phá (tập luật kết hợp) trên dữ liệu gốc D
có giá trị như thế nào vì đây là cơng việc của lĩnh vực phát hiện tri thức và khai phá
dữ liệu (KDD - Knowledge Discovery and Data Mining). Đề tài chỉ quan tâm đến kết

quả khai phá (tập luật kết hợp) trên dữ liệu thay đổi D’ khác như thế nào đối với kết
quả khai phá trên dữ liệu gốc D.

Trang 5


Chương 1: Giới thiệu

1.4 Mục tiêu đề tài
1. Đề xuất và phát triển một kỹ thuật, giải thuật để đạt mơ hình k-nặc danh (kanonymity) nhằm hạn chế khả năng tái xác định cá thể, qua đó bảo vệ tính riêng
tư của các cá nhân, tổ chức liên quan đến dữ liệu trong khi duy trì tối đa có thể
các luật kết hợp ẩn chứa trong dữ liệu.
2. Xây dựng hoàn chỉnh một ứng dụng prototype sử dụng kỹ thuật, giải thuật đã
đề xuất.
3. Tập luật khai phá được trên dữ liệu đã thay đổi D’ không được khác biệt quá
lớn đối với tập luật khai phá được trên dữ liệu gốc D.
4. Thời gian chạy của giải thuật không quá lâu để có thể chấp nhận được.
5. Thử nghiệm, phân tích và đánh giá giải thuật đã đề xuất lên dữ liệu Adult
[35] và dữ liệu ngẫu nhiên để thấy được ưu điểm và nhược điểm.

1.5 Phương pháp thực hiện
Để đạt được mục tiêu đề tài, các bước sau cần được thực hiện theo trình tự:
-

Nghiên cứu các phương pháp, mơ hình, kỹ thuật và giải thuật bảo vệ tính
riêng tư trong khai phá dữ liệu (PPDM) khác nhau đã công bố.

-

Từ việc nghiên cứu các kỹ thuật, giải thuật đã có, đề nghị một kỹ thuật, giải

thuật khả thi cho đề tài.

-

Hiện thực ứng dụng prototype theo kỹ thuật, giải thuật đã đề nghị.

-

Tìm hiểu cơng cụ khai phá dữ liệu trong SQL-Server 2005.

-

Chuẩn bị dữ liệu Adult [35] và dữ liệu ngẫu nhiên để kiểm thử.

-

Tiến hành kiểm thử, phân tích và đánh giá ưu nhược điểm của kỹ thuật.

-

Đưa ra phương hướng cải tiến kỹ thuật đề nghị trong tương lai nhằm khắc
phục các nhược điểm, hạn chế của kỹ thuật nếu có.

Trang 6


Chương 2: Tổng quan các phương pháp bảo vệ tính riêng tư trong khai phá dữ liệu

CHƯƠNG 2: TỔNG QUAN CÁC PHƯƠNG PHÁP BẢO VỆ
TÍNH RIÊNG TƯ TRONG KHAI PHÁ DỮ LIỆU

Chương này sẽ trình bày một cách tổng quan dựa trên sự phân loại các kỹ thuật
bảo vệ tính riêng tư trong khai phá dữ liệu theo [16, Chương2] (Privacy-Preversing
Data Mining).

2.1 Phương pháp ngẫu nhiên
Phương pháp ngẫu nhiên (Randomization Method) thực hiện biến đổi dữ liệu gốc
thông qua một số phép toán như: cộng, nhân hay hoán đổi dữ liệu ở các dòng trong
bảng dữ liệu trước khi được khai thác bởi các giải thuật khai phá dữ liệu.
Nói chung, phương pháp này có thuận lợi là đơn giản và có thể dễ dàng hiện thực
ở thời điểm thu thập dữ liệu (data collection time) bởi vì nhiễu được thêm vào một
dịng dữ liệu thì độc lập với những dịng dữ liệu khác. Tuy nhiên, phương pháp này
cũng có điểm yếu là không quan tâm đến khả năng các dịng dữ liệu được biết phổ
biến mà có thể là nguy cơ tái xác định một cá thể nào đó [16, Chương2, tr14].
Phương pháp này được phân thành một số kỹ thuật như sau:
2.1.1 Nhiễu hóa dựa trên cộng nhiễu
Kỹ thuật nhiễu hóa dựa trên cộng nhiễu (Additional Perturbation) được áp
dụng cho dữ liệu số liên tục, là kỹ thuật phổ biến nhất trong phương pháp ngẫu nhiên.
Gọi X là một thuộc tính nào đó cần được bảo vệ của dữ liệu gốc với các giá trị dữ liệu
{x1, x2, ...xn}. Sau đó dữ liệu gốc này sẽ bị làm nhiễu bằng một biến ngẫu nhiên Y
(hàm mật độ của Y được biết công khai) với các giá trị dữ liệu {y1, y2, ...yn} (gọi là
giá trị nhiễu) bằng phép toán cộng Z = X + Y. Nghĩa là: zi = xi + yi, zi gọi là dữ liệu bị
nhiễu. Giả định là X và Y độc lập.

Trang 7


Chương 2: Tổng quan các phương pháp bảo vệ tính riêng tư trong khai phá dữ liệu
Dữ liệu bị nhiễu {z1, z2, ..., zn} sau đó được đưa cho các thành phần khai phá
dữ liệu (miner). Như vậy các miner biết được dữ liệu bị nhiễu và phân phối của giá trị
nhiễu fY(y) của biến ngẫu nhiên Y. Mục đích của các miner là ước lượng càng chính

xác càng tốt phân phối fX(x) của biến ngẫu nhiên X (dữ liệu gốc).
2.1.2 Nhiễu hóa dựa trên nhân nhiễu
Kỹ thuật nhiễu hóa dựa trên nhân nhiễu (Multiplicative Perturbation) cũng
giống như kỹ thuật nhiễu hóa dựa trên cộng nhiễu là áp dụng cho dữ liệu số liên tục
và cũng bao gồm biến ngẫu nhiên Y với phân phối được biết công khai dùng làm giá
trị gây nhiễu cho dữ liệu, biến gây nhiễu cũng độc lập với dữ liệu gốc. Tuy nhiên cách
thức gây nhiễu ở kỹ thuật này sẽ thực hiện dựa trên phép tốn nhân thay vì phép tốn
cộng như ở kỹ thuật Additional Perturbation. Nghĩa là Z = X*Y, sau đó các zi được
đưa đi khai thác [11].
2.1.3 Hốn đổi dữ liệu
Ý tưởng của kỹ thuật hoán đổi dữ liệu (Data Swapping) là lựa chọn các cặp
dòng dữ liệu trong bảng dữ liệu gốc và thực hiện việc hoán đổi giá trị của 2 dòng dữ
liệu trong mỗi cặp trên một số các thuộc tính đã chọn từ trước. Việc chọn các cặp
dòng dữ liệu này là ngẫu nhiên và có thể có hoặc khơng thêm ràng buộc để đảm bảo
khơng sinh ra những dịng dữ liệu q bất thường. Kỹ thuật này có thể thực hiện trên
những thuộc tính phân loại (category) và cả những thuộc tính số liên tục (continuous).
Kỹ thuật này có một ưu điểm là các tổng lề (marginal totals) của tập dữ liệu
đã bị hoán đổi được đảm bảo giống như dữ liệu gốc. Vì vậy, các tính tốn mang tính
tổng kết có thể được thực thi một cách chính xác mà khơng vi phạm đến tính riêng tư
của dữ liệu. Vì kỹ thuật này không tuân theo nguyên lý cơ bản của phương pháp
Randomization (Cho phép giá trị của các dòng dữ liệu được xáo trộn một cách độc lập
với những dòng dữ liệu khác) nên kỹ thuật này có thể được sử dụng kết hợp với
những kỹ thuật khác như k-nặc danh, miễn là qui trình hốn đổi được thiết kế để đảm
bảo tính riêng tư của một mơ hình nào đó.

Trang 8


Chương 2: Tổng quan các phương pháp bảo vệ tính riêng tư trong khai phá dữ liệu


2.2 Phương pháp nặc danh dựa trên nhóm
Các kỹ thuật trong phương pháp nặc danh dựa trên nhóm (Group Based
Anonymization) nhằm hạn chế điểm yếu của phương pháp ngẫu nhiên (Từ các dòng
dữ liệu được biết phổ biến mà có thể là nguy cơ tái xác định một cá thể nào đó [16,
Chương 2, tr20]). Cách tiếp cận tổng quát của các kỹ thuật trong phương pháp này là
dữ liệu phải được nặc danh hóa trước khi được đưa đi khai thác; nghĩa là biến đổi dữ
liệu theo một cách nào đó (thay thế bằng những giá trị tổng quát hơn, hay giá trị
không xác định unknown) kết quả là có nhiều dịng dữ liệu giống nhau xét trên một
tập thuộc tính cho trước.
Các thuộc tính được phân làm 3 loại [22]:
-

Các thuộc tính xác định cụ thể cá thể (clearly identify individuals) như: số
chứng minh nhân dân, tên, địa chỉ.

-

Các thuộc tính mà khi kết hợp lại với nhau có thể xác định được cụ thể cá
thể nào đó mà được gọi là quasi-identifiers như: Ngày sinh, giới tính.

-

Các thuộc tính nhạy cảm như: Bệnh, tiền lương, tiểu sử phạm tội.

Hầu hết các kỹ thuật đều phải loại bỏ đi tất cả các thuộc tính cho phép xác
định cụ thể cá thể trước khi đưa vào q trình nặc danh hóa. Tuy nhiên nguy cơ bị
phơi bày thông tin vẫn luôn tồn tại, do đó mục tiêu thường là giới hạn rủi ro phơi bày
đến một mức nào đó trong khi tối đa có thể lợi ích khai thác.
Các rủi ro phơi bày được phân thành 2 loại sau [22]:
-


Phơi bày định danh (identity disclosure) là trường hợp khi một cá thể nào
đó bị liên kết đến một dịng dữ liệu nào đó trong bảng dữ liệu được đưa đi
khai thác.

-

Phơi bày thuộc tính (attribute disclosure) là những thơng tin mới của một
cá thể nào đó bị bộc lộ.

Trang 9


Chương 2: Tổng quan các phương pháp bảo vệ tính riêng tư trong khai phá dữ liệu
Vì khi một cá thể được xác định thì những thơng tin nhạy cảm cũng bị bộc lộ
theo nên có thể nói sự phơi bày định danh thường kéo theo phơi bày thuộc tính. Tuy
nhiên, sự phơi bày thuộc tính thì khơng chắc kéo theo phơi bày định danh.
Phương pháp này bao gồm một số kỹ thuật tiêu biểu sau:
2.2.1 k-Nặc danh
Là kỹ thuật biến đổi dữ liệu gốc sao cho dữ liệu được đưa đi khai thác phải
thỏa mãn điều kiện: bất kỳ sự kết hợp nào của các thuộc tính riêng tư của một cá thể
đều có ít nhất k cá thể khác có cùng giá trị cho sự kết hợp các thuộc tính riêng tư
tương ứng trong dữ liệu đưa ra [16, Chương 5, tr107].
Một cách dễ hình dung, cho một bảng T(A1, A2, A3, …, An) là một bảng có n
thuộc tính Ai (i=1…n). Bất sự kết hợp các thuộc tính Ai của một dịng dữ liệu nào đó
đều có ít nhất k dịng khác có cùng giá trị tương ứng với sự kết hợp thuộc tính đó.
Nhóm ít nhất k dòng này còn được gọi là lớp tương đương (equivalence class).
2.2.2 l-Đa dạng
Trong khi k-nặc danh chỉ chống lại khả năng phơi bày định danh, nó khơng
bảo vệ đầy đủ để chống lại sự phơi bày thuộc tính thì l-đa dạng (l-diversity) được đề

xuất để chống lại sự phơi bày thuộc tính nhằm loại bỏ thiếu sót này của k-nặc danh
[22].
Định nghĩa l-Đa dạng: Một lớp tương đương được gọi là có l-đa dạng nếu có
ít nhất l giá trị “thể hiện tốt” cho thuộc tính nhạy cảm. Một bảng được gọi là l-đa dạng
nếu mọi lớp tương đương của bảng đều thỏa mãn l-đa dạng.
Ví dụ:
No ZIP Code Age Disease
1

47677

29

Heart Disease

2

47602

22

Heart Disease

3

47678

27

Heart Disease


Trang 10


Chương 2: Tổng quan các phương pháp bảo vệ tính riêng tư trong khai phá dữ liệu
4

47905

43

Flu

5

47909

52

Heart Disease

6

47906

47

Cancer

7


47605

30

Heart Disease

8

47673

36

Cancer

9

47607

32

Cancer

Bảng 2.1: Thông tin bệnh nhân
No ZIP Code Age Disease
1

476**

2*


Heart Disease

2

476**

2*

Heart Disease

3

476**

2*

Heart Disease

4

4790*

≥ 40 Flu

5

4790*

≥ 40 Heart Disease


6

4790*

≥ 40 Cancer

7

476**

3*

Heart Disease

8

476**

3*

Cancer

9

476**

3*

Cancer


Bảng 2.2: Thông tin bệnh nhân đã bị nặc danh (3-anonymity)
Giả sử Malice biết Alice sống ở ZIP 47678 và tuổi là 27. Từ bảng 2 Malice có
thể đốn Alice mắc bệnh tim, đây là tấn công kiểu “đồng nhất” (homogeneity attack).
Giả sử Malice biết Bob sống ở ZIP 47656 và tuổi là 32, hơn nữa Malice biết
Bob không thể mắc chứng tim mạch, vì vậy Malice suy ra Bob chỉ có thể bị ung thư.
Đây là kiểu tấn công “hiểu biết lai lịch” (background knowledge attack).
2.2.3 t-Gần nhau
l-đa dạng là một bước mạnh hơn trong bảo vệ tính riêng tư so với k-nặc danh,
tuy nhiên l-đa dạng trong một số trường hợp vẫn chứa đựng nguy cơ bị xâm phạm

Trang 11


Chương 2: Tổng quan các phương pháp bảo vệ tính riêng tư trong khai phá dữ liệu
tính riêng tư [22]. Dưới đây sẽ trình bày một số trường hợp mà l-đa dạng mắc phải
một số thiếu sót:
l-đa dạng có thể khó và khơng cần thiết để đạt được
Ví dụ: Giả sử dữ liệu nguồn chỉ có một thuộc tính nhạy cảm là kết quả kiểm
tra các cá thể có bị nhiễm một virus nào đó. Thuộc tính này có 2 giá trị là positive and
negative. Dữ liệu có 100000 dịng, trong đó 99% là negative và 1% là positive. Rõ
ràng positive có mức độ nhạy cảm hơn rất nhiều so với negative. Vì vậy, đối với một
lớp tương đương mà tồn các dịng với giá trị của thuộc tính nhạy cảm là negative thì
khơng cần thiết phải 2-diversity.
l-đa đạng có thể không đủ mạnh để ngăn chặn phơi bày thuộc tính trong
một số trường hợp
Ví dụ: Cũng với ví dụ ở trên, giả sử có một lớp tương đương mà số dịng có
giá trị negative bằng với số dịng có giá trị positive ở thuộc tính nhạy cảm. Như vậy
bất kỳ một người nào tương ứng với một dòng trong lớp tương đương này sẽ có 50%
là positive, cao hơn nhiều so với 1% positive toàn cục. Đây gọi là tấn cơng Skewness.

Ví dụ:
No ZIP Code Age Salary Disease
1

47677

29

3K

gastric ulcer

2

47602

22

4K

gastritis

3

47678

27

5K


Stomach cancer

4

47905

43

6K

gastritis

5

47909

52

11K

flu

6

47906

47

8K


bronchitis

7

47605

30

7K

bronchitis

8

47673

36

9K

pneumonia

9

47607

32

10K


stomach cancer

Bảng 2.3: Thông tin tiền lương - bệnh

Trang 12


Chương 2: Tổng quan các phương pháp bảo vệ tính riêng tư trong khai phá dữ liệu
No ZIP Code Age Salary Disease
1

476**

2*

3K

gastric ulcer

2

476**

2*

4K

gastritis

3


476**

2*

5K

Stomach cancer

4

4790*

≥ 40 6K

gastritis

5

4790*

≥ 40 11K

flu

6

4790*

≥ 40 8K


bronchitis

7

476**

3*

7K

bronchitis

8

476**

3*

9K

pneumonia

9

476**

3*

10K


Stomach cancer

Bảng 2.4: Thông tin tiền lương - bệnh đã 3-diversity
Bảng có 2 thuộc tính nhạy cảm là tiền lương và bệnh, giả sử thơng tin của
một cá thể nào đó tương ứng với một trong 3 dòng đầu tiên trong bảng 1.4, vì vậy sẽ
biết được thơng tin là lương của người này tương đối thấp và mắc một chứng bệnh có
liên quan đến dạ dày. Đây là kiểu tấn công tương tự (Similarity).
Định nghĩa t-Gần nhau: Một lớp tương đương được gọi là thõa t-gần nhau
(t-closeness) nếu độ sai biệt giữa phân phối của một thuộc tính nhạy cảm trong lớp
tương đương này với phân phối của cùng thuộc tính nhạy cảm trong tồn bộ bảng
khơng vượt q một ngưỡng t cho trước. Một bảng được gọi là thõa t-gần nhau nếu
mọi lớp tương đương của nó thỏa mãn t-gần nhau.
Độ sai biệt giữa 2 phân phối này có thể được đo theo một vài cách:
Gọi P = {p1, p2, ..., pm} là phân phối của một thuộc tính nhạy cảm nào đó
trong một lớp tương đương, và Q= {q1, q2, ..., qm} là phân phối của cùng thuộc tính
nhạy cảm trong tồn bộ bảng. Độ sai biệt là D(P, Q)
m

D ( P, Q ) = ∑
i =1

1
pi − q i
2

(2.1)

Trang 13



Chương 2: Tổng quan các phương pháp bảo vệ tính riêng tư trong khai phá dữ liệu
m

D ( P, Q) = ∑ pi log
i =1

pi
qi

(2.2)

2.3 Bảo vệ tính riêng tư trong khai phá dữ liệu phân tán
Trong thực tế, nhiều trường hợp dữ liệu không tập trung mà được phân tán
giữa các tổ chức, công ty khác nhau. Nếu từng thành phần (tổ chức, công ty) này chỉ
khai thác dữ liệu của họ thì kết quả có được khơng trọn vẹn cũng như giá trị tri thức
khơng cao. Vì vậy các thành phần này có xu hướng kết hợp dữ liệu riêng của họ lại
với mong muốn đạt được kết quả khai thác có giá trị và đầy đủ hơn mà không muốn
phơi bày dữ liệu gốc của họ cho những thành phần cịn lại. Do đó các phương pháp
bảo vệ tính riêng tư trong khai phá dữ liệu phân tán (Distributed Privacy preserving
Data mining) ra đời.
Mục đích chính trong hầu hết các phương pháp phân tán để bảo vệ tính riêng
tư trong khai phá dữ liệu là cho phép tính tốn các thống kê tổng hợp hữu ích trên
tồn bộ tập dữ liệu mà khơng xâm phạm đến tính riêng tư của các tập dữ liệu của các
thành phần tham gia khác nhau (một tổ chức, một công ty). Dữ liệu thường được phân
tán theo 2 cách: phân tán theo chiều ngang (horizontally partitioned) và phân tán theo
chiều dọc (vertically partitioned).
Trong phân tán theo chiều ngang các dòng dữ liệu được sở hữu bởi các thành
phần tham gia, tuy nhiên các dịng dữ liệu này có cùng tập thuộc tính hay trùng lắp
thuộc tính cao.


Trang 14