Nghiên cứu phương pháp ẩn các tập mục có độ hữu ích trung bình cao nhạy cảm trong cơ sở dữ liệu giao tác

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.93 MB, 79 trang )

HỌC VIỆN CƠNG NGHỆ BƯU CHÍNH VIỄN THƠNG

Tơ Phú Khương

NGHIÊN CỨU PHƯƠNG PHÁP ẨN CÁC TẬP MỤC
CĨ ĐỘ HỮU ÍCH TRUNG BÌNH CAO NHẠY CẢM
TRONG CƠ SỞ DỮ LIỆU GIAO TÁC

ĐỀ ÁN THẠC SĨ KỸ THUẬT
(Theo định hướng ứng dụng)

TP.HỒ CHÍ MINH – NĂM 2023

ii

HỌC VIỆN CƠNG NGHỆ BƯU CHÍNH VIỄN THƠNG

Tơ Phú Khương

NGHIÊN CỨU PHƯƠNG PHÁP ẨN CÁC TẬP MỤC
CĨ ĐỘ HỮU ÍCH TRUNG BÌNH CAO NHẠY CẢM
TRONG CƠ SỞ DỮ LIỆU GIAO TÁC

Chuyên ngành: Hệ thống thông tin
Mã số: 8.48.01.04
ĐỀ ÁN THẠC SĨ KỸ THUẬT
(Theo định hướng ứng dụng)
NGƯỜI HƯỚNG DẪN KHOA HỌC:
TS. NGUYỄN KHẮC CHIẾN

TP.HỒ CHÍ MINH - NĂM 2023

i

LỜI CAM ĐOAN
Tôi cam đoan đề án: “Nghiên cứu phương pháp ẩn các tập mục có độ hữu
ích trung bình cao nhạy cảm trong cơ sở dữ liệu giao tác” là cơng trình nghiên cứu
của chính tơi.
Các số liệu được sử dụng trong đề án là trung thực và chính xác.
Ngoài những nội dung nghiên cứu của đề án, các vấn đề được trình bày đều là
những tìm hiểu và nghiên cứu của tơi hoặc là được trích dẫn từ các nguồn tài liệu có
ghi tham khảo rõ ràng, hợp pháp.
Trong đề án, tơi có tham khảo một số tài liệu của một số tác giả được
liệt kê tại danh mục tài liệu tham khảo.

TP.HCM, Ngày 12 tháng 10 năm 2023

Học viên thực hiện đề án

Tô Phú Khương

ii

LỜI CẢM ƠN
Trong suốt quá trình học tập và nghiên cứu thực hiện đề án tốt nghiệp thạc sĩ,
ngoài nỗ lực của bản thân, tôi đã nhận được sự hướng dẫn nhiệt tình q báu của q
Thầy Cơ, cùng với sự động viên và ủng hộ của gia đình, bạn bè và đồng nghiệp. Với
lịng kính trọng và biết ơn sâu sắc, tôi xin gửi lời cảm ơn chân thành tới:

Thầy TS. Nguyễn Khắc Chiến, người thầy kính yêu đã hết lòng giúp đỡ,
hướng dẫn, động viên, tạo điều kiện cho tơi trong suốt q trình thực hiện và hồn
thành đề án tốt nghiệp thạc sĩ.
Ban Giám đốc, Phòng Đào tạo sau đại học và quý Thầy Cô đã tạo mọi điều
kiện thuận lợi giúp tơi hồn thành đề án.
Tơi xin chân thành cảm ơn gia đình, bạn bè, đồng nghiệp trong cơ quan đã
động viên. Hỗ trợ tôi trong lúc khó khăn để tơi có thể học tập và hồn thành đề án.
Mặc dù đã có nhiều cố gắng, nỗ lực, nhưng do thời gian và kinh nghiệm nghiên cứu
khoa học cịn hạn chế nên khơng thể tránh khỏi những thiếu sót. Tơi rất mong nhận
được sự góp ý của quý Thầy Cô cùng bạn bè đồng nghiệp để kiến thức của tơi ngày
một hồn thiện hơn.
Xin chân thành cảm ơn!
TP.HCM, Ngày 12 tháng 10 năm 2023

Học viên thực hiện đề án

Tô Phú Khương

iii

MỤC LỤC
LỜI CAM ĐOAN ....................................................................................................... i
LỜI CẢM ƠN ............................................................................................................ii
MỤC LỤC ................................................................................................................ iii
DANH MỤC CÁC THUẬT NGỮ, CHỮ VIẾT TẮT ............................................ v
DANH SÁCH BẢNG ..............................................................................................vii
DANH SÁCH HÌNH VẼ ....................................................................................... viii
MỞ ĐẦU .................................................................................................................... 1
1. Lý do chọn đề tài ..................................................................................................1

2. Tổng quan về vấn đề nghiên cứu .........................................................................2
3. Mục tiêu nghiên cứu của đề tài ............................................................................6
4. Đối tượng nghiên cứu ..........................................................................................6
5. Những nội dung chính yếu cần nghiên cứu .........................................................6
CHƯƠNG 1: MỘT SỐ VẤN ĐỀ LIÊN QUAN ĐẾN TẬP MỤC CÓ ĐỘ HỮU
ÍCH TRUNG BÌNH CAO ......................................................................................... 8
1.1. Các khái niệm liên quan đến khai thác tập mục có độ hữu ích trung bình cao 8
1.1.1. Khai phá tri thức và khai thác dữ liệu ......................................................8
1.1.1.1. Các bước chính của q trình khai phá dữ liệu ..................................8
1.1.1.2. Kiến trúc một hệ thống khai phá dữ liệu ..........................................10
1.1.1.3. Ứng dụng của khai phá dữ liệu ........................................................13
1.1.2. Khai phá tập mục độ hữu ích trung bình cao .........................................13
1.1.3. Ứng dụng khai thác tập mục độ hữu ích trung bình cao ........................16
1.1.4. Phương pháp khai phá tập mục hữu ích trung bình cao ........................16
1.2. Bài tốn ẩn tập mục có độ hữu ích trung bình cao .........................................19
1.3. Một số thuật toán khai phá tập mục độ hữu ích trung bình cao .....................22
1.4. Kết luận Chương 1 ..........................................................................................23
CHƯƠNG 2: PHƯƠNG PHÁP ẨN TẬP MỤC CÓ ĐỘ HỮU ÍCH TRUNG
BÌNH CAO NHẠY CẢM ....................................................................................... 24

iv

2.1. Phương pháp khai thác tập mục có độ hữu ích trung bình cao nhạy cảm ......24
2.2. Tác dụng phụ ..................................................................................................26
2.3. Phương pháp ẩn các tập mục có độ hữu ích trung bình cao nhạy cảm...........29
2.4. Ưu điểm và hạn chế của các phương pháp .....................................................38
2.5. Kết luận Chương 2 ..........................................................................................40
CHƯƠNG 3: ĐỀ XUẤT PHƯƠNG PHÁP HIỆU QUẢ ĐỂ ẨN TẬP MỤC CĨ
ĐỘ HỮU ÍCH TRUNG BÌNH CAO NHẠY CẢM .............................................. 41

3.1. Một số thông số dùng để đánh giá tính hiệu quả của phương pháp ẩn các tập
mục có độ hữu ích trung bình cao nhạy cảm. ........................................................41
3.1.1. Xác định giá trị hữu ích tối thiểu cần giảm hay xóa mục: .......................42
3.1.2. Xác định mục mục tiêu và hệ số :..........................................................42
3.2. Đề xuất phương pháp ẩn tập phổ biến có độ hữu ích trung bình cao nhạy cảm
hiệu quả. .................................................................................................................43
3.3. Kết luận Chương 3 ..........................................................................................50
CHƯƠNG 4: THỬ NGHIỆM VÀ ĐÁNH GIÁ ................................................... 51
4.1. Môi trường thực nghiệm và dữ liệu sử dụng ..................................................51
4.2. Kết quả thực nghiệm .......................................................................................51
a. Thời gian thực thi ..........................................................................................52
b. DSS (Tỷ lệ tương đồng về cấu trúc của CSDL sửa đổi D' so với CSDL gốc
D)

..................................................................................................................53

c. DUS (Tỷ lệ tương đồng về hữu ích giữa CSDL D' với CSDL D) ..................54
d. IUS (Tỷ lệ tương đồng về hữu ích trung bình của tập các HAUI trong CSDL
sửa đổi D' (HAUIs') so với tập các HAUI trong CSDL gốc D (HAUIs)). ........55
4.3. Kết luận Chương 4. .........................................................................................56
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ............................................................. 57
DANH MỤC TÀI LIỆU THAM KHẢO ............................................................... 58

v

DANH MỤC CÁC THUẬT NGỮ, CHỮ VIẾT TẮT
Viết tắt

Tiếng Anh

Tiếng Việt

Database

Cơ sở dữ liệu

DIF

Difference

Sự khác biệt

DSS

Database Structure
Similarity.

Tỷ lệ tương đồng về cấu trúc của CSDL
sửa đổi D' so với CSDL gốc D.

DUS

Database utility similarity

Tỷ lệ tương đồng về hữu ích giữa
CSDL D' với CSDL D

HAUI

High Average Utility
Itemset

Tập mục hữu ích trung bình cao

HAUIM

High Average Utility
Itemset Mining

Khai thác tập mục có độ hữu ích
trung bình cao

Hiding Failure

Tỷ lệ tập mục hữu ích trung bình
cao nhạy cảm khơng ẩn được

IUS

Itemsets Utility Similarity

Tỷ lệ tương đồng về hữu ích trung
bình của tập các HAUIs trong CSDL
sửa đổi D' so với tập các HAUIs trong
CSDL gốc D

KDD

Knowledge Discovery

in Databases

Phát hiện tri thức từ CSDL

Data Mining

Khai phá dữ liệu

Miss Cost

Tỷ lệ tập mục hữu ích trung bình
cao khơng nhạy cảm bị mất

CSDL

HF

KPDL
MC

Privacy Preserving
PPAUIM Average Utility Itemset
Mining
PPDM

Bảo vệ tính riêng tư trong khai phá
tập mục hữu ích trung bình cao

Privacy Preserving Data Khai phá dữ liệu bảo vệ quyền
Mining

riêng tư

vi

QTDB

Quantitative
Transaction Database

Cơ sở dữ liệu giao tác định lượng

SHAUI

Sensitive High Average
Utility Itemset

Tập mục hữu ích trung bình cao
nhạy cảm

vii

DANH SÁCH BẢNG
Bảng 1.1: Cơ sở dữ liệu giao tác (biểu diện dạng ngang) .................................... 14
Bảng 1.2: Cơ sở dữ liệu giao tác (biểu diễn dạng dọc) ........................................ 15
Bảng 1.3: Cơ sở dữ liệu giao tác (biểu diễn dạng ma trận).................................. 15
Bảng 1.4: CSDL giao tác D.................................................................................. 20
Bảng 1.5: Giá trị lợi nhuận của CSDL D ............................................................. 21
Bảng 1.6: Tập mục hữu ích trung bình cao HAUIs ............................................. 21

Bảng 2.1: Xác định tập ST chứa giao tác hỗ trợ S1 ............................................. 32
Bảng 2.2: CSDL giao tác D.................................................................................. 33
Bảng 2.3: Tập mục hữu ích trung bình cao .......................................................... 34
Bảng 2.4: Xác định tập ST chứa giao tác hỗ trợ S2 ............................................. 34
Bảng 2.5: CSDL giao tác D.................................................................................. 35
Bảng 2.6: Tập mục hữu ích trung bình cao .......................................................... 36
Bảng 2.7: Xác định tập ST chứa giao tác hỗ trợ S3 ............................................. 36
Bảng 2.8: CSDL giao tác D.................................................................................. 37
Bảng 2.9: Tập mục hữu ích trung bình cao .......................................................... 37
Bảng 3.1: T-table .................................................................................................. 45
Bảng 3.2: Xác định tập ST chứa giao tác hỗ trợ S1 ............................................. 46
Bảng 3.3: CSDL giao tác D.................................................................................. 47
Bảng 3.4: Tập mục hữu ích trung bình cao .......................................................... 47
Bảng 3.5: Xác định tập ST chứa giao tác hỗ trợ S2 ............................................. 48
Bảng 3.6: CSDL giao tác D.................................................................................. 49
Bảng 3.7: Tập mục hữu ích trung bình cao .......................................................... 49
Bảng 4.1: Cơ sở dữ liệu dùng cho thực nghiệm ................................................... 51

viii

DANH SÁCH HÌNH VẼ
Hình 1.1: Khai thác dữ liệu là một bước trong quá trình khám phá tri thức ................. 9
Hình 1.2: Kiến trúc hệ thống khai thác dữ liệu ........................................................... 11
Hình 2.1. Quy trình PPUM chung ............................................................................... 24
Hình 2.2. Mối quan hệ giữa các tập mục trước và sau quá trình PPDM..................... 26
Hình 2.3. Tập hợp các tập mục nhạy cảm mà quy trình PPDM khơng ẩn được ......... 27
Hình 2.4. Mising cost do quy trình làm sạch .............................................................. 27
Hình 2.5. Artificial cost phát sinh từ quy trình PPDM ............................................... 28
Hình 4.1: Kết quả so sánh thời gian thực thi của hai thuật tốn ................................. 52

Hình 4.2: DSS Tỷ lệ tương đồng về cấu trúc dữ liệu khi thực hiện ẩn ...................... 53
Hình 4.3: DUS Tỷ lệ tương đồng về giá trị hữu ích của CSDL khi thực hiện ẩn ...... 54
Hình 4.4: IUS Tỷ lệ tương đồng về giá trị hữu ích trung bình của tập SHAUIs giữa
CSDL gốc D và CSDL sửa đổi D' khi thực hiện ẩn .................................................... 55

1

MỞ ĐẦU
1.

Lý do chọn đề tài
Bài toán khai thác tập mục có độ hữu ích cao trong cơ sở dữ liệu (CSDL) giao

tác đã trở thành một vấn đề quan trọng trong những thập kỷ gần đây. Trong khai thác
tập mục có độ hữu ích cao truyền thống, độ hữu ích của một tập mục được định nghĩa
là tổng các hữu ích của các mục của nó, trong các giao tác mà nó xuất hiện. Một vấn
đề quan trọng với định nghĩa này là nó khơng tính đến độ dài của tập mục. Bởi vì độ
hữu ích của tập mục lớn thường lớn hơn độ hữu ích của tập mục nhỏ, thuật tốn khai
thác tập mục có độ hữu ích cao truyền thống có xu hướng thiên về việc tìm kiếm một
tập hợp các tập mục lớn. Vì vậy, định nghĩa này không phải là một phép đo hợp lý về
độ hữu ích. Để cung cấp một đánh giá tốt hơn về độ hữu ích của từng tập mục, bài
tốn khai thác tập mục độ hữu ích trung bình cao đã được đề xuất. Nó giới thiệu phép
đo độ hữu ích trung bình, xem xét cả độ dài của tập mục và độ hữu ích của chúng, và
do đó phù hợp hơn trong các tình huống thực tế.
Khai thác tập mục có độ hữu ích trung bình cao (HAUIM) bao gồm phân tích
cơ sở dữ liệu giao tác định lượng của khách hàng để xác định các tập mục độ hữu ích
trung bình cao, đó là tập hợp các mục có độ hữu ích trung bình cao (ví dụ: Lợi nhuận).
Nhiều thuật toán đã được thiết kế để nhận dạng cái mới, hữu ích và những mẫu bất
ngờ trong dữ liệu, có thể giúp hiểu dữ liệu, hỗ trợ ra quyết định và cung cấp thông tin

chi tiết về sở thích của người dùng. Tuy nhiên, một vấn đề chính là tri thức được phát
hiện bởi các kỹ thuật này cũng có thể tiết lộ thơng tin riêng tư, nhạy cảm hoặc thơng
tin chiến lược như thơng tin thẻ tín dụng, các mẫu mua hàng từ các cá nhân và số
nhận dạng cá nhân. Do đó, các cá nhân có thể phải đối mặt với các mối đe dọa về
quyền riêng tư và dữ liệu của họ có thể bị lạm dụng. Điều quan trọng nữa là bảo vệ
thông tin riêng tư và nhạy cảm của các doanh nghiệp mang lại cho họ lợi thế chiến
lược so với đối thủ cạnh tranh cũng như bảo vệ quyền riêng tư của nhân viên và khách
hàng của họ. Chẳng hạn, nếu một công ty công khai dữ liệu hoặc chia sẻ dữ liệu với
các cộng tác viên, thì có nguy cơ một số thơng tin nhạy cảm có thể bị trích xuất từ đó

2

bằng thuật toán khai phá dữ liệu. Để giải quyết mối lo ngại này, bài tốn ẩn các tập
mục có độ hữu ích trung bình cao được nghiên cứu, đó là sửa đổi cơ sở dữ liệu giao
tác để đảm bảo rằng các tập mục có độ hữu ích trung bình cao nhạy cảm khơng thể
bị phát hiện.
Tập mục hữu ích trung bình cao nhạy cảm là tập mục được sử dụng để hỗ trợ
ra quyết định. Thông tin này rất quan trọng đối với chủ sở hữu cơ sở dữ liệu. Nếu nó
bị phát hiện bởi các đối thủ cạnh tranh, hoạt động kinh doanh của chủ sở hữu cơ sở
dữ liệu có thể bị ảnh hưởng. Để đảm bảo rằng thơng tin này được bảo tồn, tập mục
hữu ích trung bình cao nhạy cảm phải được ẩn khỏi cơ sở dữ liệu trước khi được chia
sẻ ra bên ngồi.
Xuất phát từ những lý do trên, tơi chọn đề tài “Nghiên cứu phương pháp ẩn
các tập mục có độ hữu ích trung bình cao nhạy cảm trong cơ sở dữ liệu giao tác”
làm đề tài nghiên cứu cho đề án tốt nghiệp của mình.

2.

Tổng quan về vấn đề nghiên cứu

Các kỹ thuật khai phá dữ liệu trong đó có các kỹ thuật khai thác tập mục có độ

hữu ích trung bình cao đã đóng một vai trị quan trọng để phân tích CSDL giao tác.
Nhiều thuật tốn đã được thiết kế để rút trích ra tri thức mới, hữu ích và những mẫu
bất ngờ trong dữ liệu, có thể giúp người sử dụng hiểu dữ liệu, hỗ trợ ra quyết định và
cung cấp thông tin chi tiết về sở thích của người dùng.
Khai thác tập mục có độ hữu ích trung bình cao sử dụng độ hữu ích trung bình
để loại bỏ sự phụ thuộc của ràng buộc độ dài vào hữu ích tập mục. TPAU [1] là thuật
tốn khai thác HAUI đầu tiên, về bản chất là hai pha. TPAU xác định giới hạn trên
được gọi là giới hạn trên độ hữu ích trung bình (AUUB) để duy trì tính chất downward
closure. Nếu giá trị AUUB của một tập mục khơng thỏa ngưỡng độ hữu ích trung
bình tối thiểu, thì tập mục đó và tất cả các tập cha (supersets) của nó khơng thể là
HAUI. TPAU thực hiện tìm kiếm theo cấp độ địi hỏi thời gian chạy dài. Một giải
pháp khác, PBAU [5] phát triển một kỹ thuật dựa trên phép chiếu và cấu trúc lập chỉ
mục để tăng tốc q trình khai thác HAUI. Ngồi PBAU, Lan và cộng sự [4] đã trình

3

bày một giới hạn trên chặt chẽ hơn dựa trên khái niệm tiền tố để giảm số lượng tập
mục ứng viên. Tien Lu [12] đã đề xuất một thuật toán HAUI dựa trên cây sử dụng
cây HAUI và một cấu trúc mới cho các tập mục để tăng tốc độ tính tốn. HAUIgrowth [7] là một thuật tốn khai thác HAUI dựa trên cây khác để tránh quét cơ sở
dữ liệu nhiều lần. Ngoài ra, mỗi nút trong cây duy trì một mảng để giữ thơng tin về
độ hữu ích trung bình của các tập mục. Sau đó, thuật tốn HAUI-Miner [8] một pha
hiệu quả được trình bày kết hợp cấu trúc danh sách có tên là danh sách độ hữu ích
trung bình (AU) để khai thác HAUI. Nó áp dụng mơ hình AUUB để loại bỏ các ứng
viên yếu khỏi khơng gian tìm kiếm. EHAUPM [10] là một thuật toán khác để khai
thác HAUI, thuật toán này bổ sung hai giới hạn trên chặt chẽ hơn có tên là Tiện ích
giới hạn trên lỏng lẻo hơn (Looser Upper - Bound Utility - LUB) và Giới hạn trên
chặt chẽ hơn được sửa đổi (Revised Tighter Upper Bound - RTUB) để loại bỏ đáng

kể các tập mục ứng viên không tiềm năng. Ngồi ra, nó kết hợp một cấu trúc danh
sách mới được gọi là danh sách độ hữu ích trung bình được sửa đổi (MAU) và các
chiến lược cắt tỉa khác nhau để cải thiện hiệu suất. Trong khi đó, MHAI [21] đã đưa
ra một cấu trúc danh sách mới HAI-list và nhiều chiến lược cắt tỉa để thúc đẩy q
trình khai thác HAUI. Một số cơng trình nghiên cứu khác về vấn đề khai thác HAUI
đã được thảo luận trong [11], [15], [16], [19].
HAUIM có ứng dụng trong nhiều lĩnh vực. Chẳng hạn, HAUIM có thể được
sử dụng trong bối cảnh kinh doanh để tiếp thị chéo và phát triển các chiến lược quảng
bá mới để tăng doanh số bán các sản phẩm có lợi nhuận cao [17], để phân tích dữ liệu
phát trực tuyến (ví dụ: Phân tích luồng nhấp chuột vào web dựa trên thời gian dành
cho mỗi trang web), và để khám phá các mẫu gen quan trọng trong dữ liệu y tế [22].
Nhưng các HAUI được tìm thấy trong CSDL giao tác có thể tiết lộ thơng tin cá nhân
hoặc chiến lược, điều này có thể gây ra vấn đề. Ví dụ: Một cơng ty thương mại điện
tử có thể muốn chia sẻ dữ liệu về các giao tác khách hàng của mình với một công ty
khác dưới dạng CSDL giao tác để cộng tác nhưng có thể khơng muốn tiết lộ các mẫu
có lợi nhất (HAUI) xuất hiện trong dữ liệu để công ty kia không thể sử dụng thông
tin này để làm lợi thế cho mình. Đây là một mối quan tâm quan trọng vì dữ liệu do

4

các công ty thu thập về khách hàng đặc biệt khó thu thập và có giá trị đối với các
nhiệm vụ khác nhau như giới thiệu sản phẩm. Do đó, mong muốn có quyền kiểm sốt
những gì có thể tìm thấy trong dữ liệu bằng thuật tốn HAUIM. Ví dụ thứ hai là dữ
liệu được thu thập từ các công cụ tìm kiếm lớn về các truy vấn tìm kiếm. Một truy
vấn tìm kiếm có thể được biểu diễn dưới dạng một CSDL giao tác trong đó mỗi giao
tác là một tập hợp các từ khóa trong một truy vấn và trong đó độ hữu ích của các từ
khóa có thể là thước đo tầm quan trọng của các từ (ví dụ: Tần suất thuật ngữ). Vì dữ
liệu truy vấn tìm kiếm rất có giá trị đối với doanh nghiệp, nên việc ẩn các liên kết
quan trọng giữa các từ khóa trước khi cơng khai dữ liệu truy vấn tìm kiếm để giữ lợi

thế cạnh tranh cũng là điều hợp lý. Do đó, như được thúc đẩy bởi những ví dụ này,
việc chia sẻ một CSDL giao tác có thể dẫn đến các mối đe dọa về quyền riêng tư, bảo
mật hoặc tổn thất lợi nhuận. Do đó, rõ ràng cần phải ẩn các HAUI nhạy cảm để ngăn
người dùng trái phép phát hiện ra chúng.
Ẩn tập mục hữu ích trung bình cao nhạy cảm là cơng việc nhằm mục đích che
giấu các thơng tin riêng tư/nhạy cảm mà chủ sở hữu không muốn chúng bị khai thác
bởi các thuật toán HAUIM, để tránh các rủi ro gặp phải khi các thông tin này bị khai
thác và sử dụng vào các mục đích mà có thể gây ra các tác động xấu cho chủ sở hữu
CSDL hoặc các cá nhân có liên quan. Năm 2018, các tác giả trong [2] đề xuất phương
pháp và thuật toán ẩn tập mục hữu ích trung bình cao nhạy cảm có tên là HHAUSI.
Phương pháp tiếp cận của thuật toán này là sửa cơ sở dữ liệu gốc để giảm giá trị hữu
ích trung bình của tập mục nhạy cảm xuống thấp hơn ngưỡng hữu ích trung bình tối
thiểu. Thuật tốn HHAUSI sử dụng ba đơn vị đo lường để đánh giá hiệu ứng phụ của
thuật toán, gồm: HF (Tỷ lệ tập mục hữu ích trung bình cao nhạy cảm khơng ẩn được);
MC (Tỷ lệ tập mục hữu ích trung bình cao khơng nhạy cảm bị mất); DIF (Tỷ lệ sai
khác giữa CSDL gốc so với CSDL sửa đổi). Phương pháp chọn mục mục tiêu và giao
tác mục tiêu để sửa dữ liệu của thuật toán HHAUSI là tương tự như thuật toán HHUIF
[20] nên hiệu ứng phụ của thuật tốn vẫn cịn cao, bởi vì phương pháp lựa chọn mục
mục tiêu và giao tác mục tiêu để sửa của thuật toán HHUIF là dựa vào mục có độ hữu
ích cao nhất. Để giải quyết hạn chế của thuật tốn HHAUSI, cơng trình của Huỳnh

5

Triệu Vỹ và cộng sự [18] đã đề xuất thuật tốn có tên gọi là EHSHA-UI, thuật tốn
EHSHA-UI sử dụng các phương pháp chọn lựa mục mục tiêu và giao tác mục tiêu
khác nhau cho từng trường hợp mục mục tiêu được xóa và sửa để giảm hiệu ứng phụ.
Để giảm thiểu hiệu ứng phụ của quá trình sửa đổi dữ liệu gây ra, nhóm tác giả sử
dụng các phương pháp lựa chọn mục mục tiêu và giao tác mục tiêu khác nhau cho
trường hợp giảm giá trị hữu ích nội của mục mục tiêu và trường hợp xóa mục mục

tiêu. Mặc dù kết quả thực nghiệm của thuật toán EHSHA-UI mang lại một số hiệu
quả nhất định, tuy nhiên thời gian thực hiện của thuật toán EHSHA-UI cũng như các
hiệu ứng phụ vẫn được sinh ra đáng kể.
Trong công trình [6] nghiên cứu vấn đề ẩn các HAUI phổ biến (FHAUI) trong
một CSDL giao tác. Bài toán này bao gồm việc sửa đổi cơ sở dữ liệu để ẩn tất cả các
FHAUI đối với ngưỡng hỗ trợ và độ hữu ích tối thiểu nhất định, được ký hiệu là ms
và ms. Trong cơng trình này, FHAUI là tập mục có độ hữu ích trung bình cao có tần
số xuất hiện không nhỏ hơn ms. Lý do để xem xét khơng chỉ độ hữu ích trung bình
mà cả tần suất xuất hiện là do các ràng buộc về tần suất cũng được sử dụng theo cách
truyền thống trong khai thác mẫu để lọc ra các mẫu nhiễu (có thể xuất hiện tình cờ
hoặc khơng đáng kể do tần suất xuất hiện thấp của chúng). Ví dụ: Nếu một số hành
vi của khách hàng chỉ được quan sát một vài lần trong cơ sở dữ liệu giao tác của
khách hàng hoặc nếu một số từ khóa chỉ xuất hiện một vài lần trong các truy vấn tìm
kiếm, những mẫu đó có thể bị bỏ qua. Do đó, ẩn các mẫu bằng cách xem xét cả hai
yếu tố (độ hữu ích và tần số xuất hiện) hơn là chỉ xem xét một yếu tố. Bài báo này
giải quyết những vấn đề này bằng cách thiết kế một thuật toán hiệu quả cho FHAUIH
có tên là H-FHAUI. Thuật tốn sử dụng cách tiếp cận biên lấy ý tưởng từ cơng việc
trước đó về ẩn tập mục phổ biến [14] trong đó tính chất downward closure của phép
đo độ hỗ trợ được sử dụng để giảm khơng gian tìm kiếm. Tuy nhiên, việc mở rộng
cách tiếp cận biên này cho bài tốn FHAUIH khơng dễ dàng bởi vì hàm độ hữu ích
trung bình khơng thỏa mãn tính chất downward closure. Nghiên cứu này đề xuất một
đường biên dưới mở rộng, được áp dụng cho các giới hạn trên yếu trên au và được

6

tích hợp vào thuật tốn H-FHAUI được đề xuất để ẩn các FHAUI một cách hiệu quả
bằng cách chỉ ẩn một tập hợp con nhỏ các FHAUI.
Tuy nhiên, trong đề án này, tôi chỉ tập trung xem xét một yếu tố là độ hữu ích
trung bình cao dùng để ẩn các tập mục có độ hữu ích trung bình cao trong CSDL giao

tác. Phương pháp đề xuất trong đề án này sẽ tập trung so sánh, đánh giá với các thuật
tốn trong cơng trình năm 2018 [2] và năm 2021 [18]. Mục tiêu của đề án là đề xuất
được phương pháp ẩn các tập mục có độ hữu ích trung bình cao nhạy cảm trong CSDL
giao tác sao cho giảm thời gian thực hiện cũng như giảm thiểu các hiệu ứng phụ: Tạo
ra tập mục mới, ẩn nhầm các tập mục không nhạy cảm khác, giảm tối thiểu sự sai
khác giữa CSDL trước và sau khi sửa đổi,…

3.

Mục tiêu nghiên cứu của đề tài
Nghiên cứu các phương pháp ẩn tập mục có độ hữu ích trung bình cao nhạy

cảm hiện có dựa trên các cơng trình đã cơng bố gần đây. Từ đó chỉ ra những ưu điểm
và hạn chế của nó để đề xuất giải pháp hiệu quả hơn về mặt thời gian chạy cũng như
các phép đo về mặt hiệu ứng phụ tạo ra bởi quá trình ẩn.

4.

Đối tượng nghiên cứu
- Các kỹ thuật khai thác tập mục có độ hữu ích trung bình cao trong CSDL

giao tác.
- Các kỹ thuật ẩn các tập mục có độ hữu ích trung bình cao nhạy cảm trong
CSDL giao tác.

5.

Những nội dung chính yếu cần nghiên cứu
- Nghiên cứu và tìm hiểu những cơng trình đã cơng bố liên quan đến khai thác

tập mục có độ hữu ích trung bình cao (HAUI).
- Nghiên cứu và tìm hiểu những cơng trình liên quan bài tốn ẩn các tập mục
có độ hữu ích trung bình cao nhạy cảm trong cơ sở dữ liệu giao tác: Chỉ ra được
những ưu điểm và hạn chế của nó, từ đó đề xuất hướng nghiên cứu tiếp theo.

7

- Tìm hiểu các thơng số đánh giá tính hiệu quả của các phương pháp ẩn tập
mục có độ hữu ích trung bình cao nhạy cảm trong cơ sở dữ liệu giao tác.
- Tiến hành cài đặt phương pháp ẩn tập mục có độ hữu ích trung bình cao nhạy
cảm đề xuất để so sánh với các phương pháp cùng loại khác.
- Thực nghiệm trên các cơ sở dữ liệu giao tác được lấy trên trang web
/>- Môi trường thực nghiệm: Máy vi tính cài hệ điều hành Win 10 và ngơn ngữ
lập trình là Java, Python,…

8

CHƯƠNG 1: MỘT SỐ VẤN ĐỀ LIÊN QUAN ĐẾN
TẬP MỤC CĨ ĐỘ HỮU ÍCH TRUNG BÌNH CAO
1.1. Các khái niệm liên quan đến khai thác tập mục có độ hữu ích trung
bình cao
1.1.1. Khai phá tri thức và khai thác dữ liệu
Khai phá tri thức là việc rút trích tri thức một cách tự động và hiệu quả từ một
khối dữ liệu lớn. Tri thức đó thường ở dạng các mẫu có tính chất khơng tầm thường,
khơng tường minh chưa được biết đến và có tiềm năng mang lại lợi ích.
“Phát hiện tri thức trong CSDL là một quá trình khơng tầm thường nhận ra
những mẫu có giá trị, mới, hữu ích tiềm năng và hiểu được trong dữ liệu” [3].
Là lĩnh vực nghiên cứu và triển khai được phát triển nhanh chóng và rộng lớn,

lại được rất nhiều nhóm nghiên cứu tại nhiều địa điểm khác nhau trên thế giới đồng
thời quan tâm, nên tồn tại rất nhiều cách tiếp cận khác nhau đối với lĩnh vực KDD.
Vì lý do đó mà trong nhiều tài liệu, các nhà khoa học trên thế giới đã sử dụng nhiều
thuật ngữ khác nhau mà chúng được coi là mang cùng nghĩa với KDD như chiết lọc
tri thức (knowledge extraction), phát hiện thông tin (information discovery), thu
hoạch thông tin (information harvesting), khai quật dữ liệu (data archaeology) và xử
lý mẫu dữ liệu (data pattern processing).
Mơ hình q trình khai phá dữ liệu cũng được cải tiến, phù hợp với mục tiêu
kinh doanh và mục tiêu phát triển của từng tổ chức. Tồn tại một số mơ hình thiên
hướng cơng nghệ.

1.1.1.1. Các bước chính của quá trình khai phá dữ liệu
Nhiều người xem khai thác dữ liệu như là một từ đồng nghĩa với một thuật
ngữ phổ biến được sử dụng, khám phá tri thức từ dữ liệu, hoặc KDD, trong khi
những người khác xem khai thác dữ liệu chỉ đơn thuần là một bước cần thiết trong
quá trình khám phá tri thức. Quá trình khám phá tri thức được thể hiện trong Hình
1.1 là một chuỗi lặp đi lặp lại các bước sau:

9

Evaluation &
Presentation
Data Mining

Knowledge

Selection &
Transformation
Cleaning &

Integration
Data
warehouse

Data Base
Fla t file s

Bước 1: Trích
lọc dữ liệu

Bước 2: Tiền
xử lý dữ liệu

Bước 3: Chuyển
đổi dữ liệu

Bước 4: Khai
phá dữ liệu

Bước 5: Đánh giá và
biểu diễn tri thức

Hình 1.1: Khai thác dữ liệu là một bước trong quá trình khám phá tri thức

Làm sạch dữ liệu (để loại bỏ nhiễu và dữ liệu không phù hợp). Tích hợp dữ
liệu, nơi mà nhiều nguồn dữ liệu có thể được kết hợp (Một xu hướng phổ biến trong
ngành công nghiệp thông tin là để thực hiện làm sạch dữ liệu và tích hợp dữ liệu như
là một bước tiền xử lý, nơi mà các dữ liệu kết quả được lưu trữ trong một kho dữ
liệu). Chọn lựa dữ liệu, nơi dữ liệu có liên quan đến nhiệm vụ phân tích được lấy từ
cơ sở dữ liệu: 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.
Bước 1: Biến đổi dữ liệu, nơi mà dữ liệu được biến đổi và hợp nhất thành các
hình thức thích hợp cho khai thác bằng cách thực hiện tóm tắt hoặc tập hợp các hoạt
động (đôi khi chuyển đổi dữ liệu và hợp nhất được thực hiện trước khi quá trình lựa
chọn dữ liệu, đặc biệt là trong trường hợp các kho dữ liệu. Giảm dữ liệu cũng có thể
được thực hiện để có được một đại diện nhỏ hơn của dữ liệu gốc mà khơng bị mất
tồn vẹn của nó).

10

Bước 2: Khai thác dữ liệu (một quá trình cần thiết mà các phương pháp thông
minh được áp dụng để trích xuất các mẫu dữ liệu): Đây được xem là bước quan trọng
nhất trong q trình KDD. Nó áp dụng một số kỹ thuật KPDL (chủ yếu là từ học máy
và các lĩnh vực khác) để 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.
Bước 3: Đánh giá mẫu (để xác định các mơ hình thực sự thú vị đại diện cho
kiến thức dựa trên các biện pháp): Thành phần này thường sử dụng các độ đo và
tương tác với thành phần KPDL để tập trung tìm kiếm các mẫu. Nó có thể sử dụng
các ngưỡng để lọc ra các mẫu phát hiện được. Ngoài ra, thành phần đánh giá mẫu có
thể được tích hợp với thành phần KPDL, phụ thuộc vào các phương pháp KPDL được
sử dụng.
Bước 4: Biểu diễn tri thức (nơi trực quan và kỹ thuật biểu diễn tri thức được
sử dụng để trình bày kiến thức khai thác cho người sử dụng): Những mẫu thông tin
và mối liên hệ trong dữ liệu đã được khai phá ở bước trên được chuyển dạng và biểu
diễn ở một dạng gần gũi với người sử dụng như đồ thị, cây, bảng biểu, luật,... Đồng
thời bước này cũng đánh giá những tri thức khám phá được những tiêu chí nhất định.
Từ bước 1 đến 4 là các hình thức khác nhau của tiền xử lý dữ liệu, nơi dữ
liệu được chuẩn bị cho khai thác. Các bước khai thác dữ liệu có thể tương tác với

người sử dụng hoặc một cơ sở tri thức. Các mẫu thú vị được trình bày cho người sử
dụng và có thể được lưu trữ như kiến thức mới trong cơ sở tri thức.

1.1.1.2. Kiến trúc một hệ thống khai phá dữ liệu
Kiến trúc của hệ thống KPDL có thể có các thành phần chính sau:

11

Giao diện người dùng
(User int erface)

Đánh gi á mẫu
(Pattern Evaluation)
Cơ sở tri thức
(Knowledge Base)

Bộ máy khai thác dữ liệu
(Data Mining Engine)

CSDL/Kho DL
(Database/Data Warehous e Server)

Tiền xử lý dữ liệu
(Data Cleaning, Integration, Selection)

CSDL

Kho DL

WWW

...

Hình 1.2: Kiến trúc hệ thống khai thác dữ liệu

Trong kiến trúc này, các nguồn dữ liệu cho các hệ thống KPDL bao gồm
hoặc CSDL, hoặc kho dữ liệu, hoặc WWW, hoặc kho chứa dữ liệu kiểu bất kỳ khác,
hoặc tổ hợp các kiểu đã liệt kê nói trên. Cơ sở tri thức, bao gồm các tri thức hiện có
về miền ứng dụng, được sử dụng trong thành phần KPDL để làm tăng tính hiệu quả
của thành phần này. Một số tham số của thuật toán KPDL tương ứng sẽ được tinh
chỉnh theo tri thức miền sẵn có từ cơ sở tri thức trong hệ thống.
Cơ sở tri thức còn được sử dụng trong việc đánh giá các mẫu đã khai phá được
xem chúng có thực sự hấp dẫn hay khơng, trong đó có đối chứng với các tri thức đã
có trong cơ sở tri thức. Nếu mẫu khai phá được thực sự hấp dẫn thì được bổ sung vào
cơ sở tri thức để phục vụ cho hoạt động tiếp theo của hệ thống. Như vậy, nguồn tri
thức bổ sung vào cơ sở tri thức ở đây không chỉ từ lập luận logic để có tri thức mới,
mà còn cho con người hiểu biết thêm về thế giới khách quan để bổ sung vào tri thức
được phát hiện một cách tự động từ nguồn dữ liệu. KPDL là một bước chính trong
q trình phát hiện tri thức từ số lượng lớn dữ liệu đã lưu trữ trong CSDL, kho dữ

12

liệu hoặc các nơi lưu trữ khác. Kết quả của bước này là những mẫu đáng quan tâm
được đưa đến cho người dùng hoặc lưu giữ như là tri thức mới trong cơ sở tri thức.
+ CSDL, kho dữ liệu, WWW, kho chứa dữ liệu khác: Đây là một hoặc một
tập CSDL, kho dữ liệu, World Wide Web, hoặc kho chứa dữ liệu kiểu bất kỳ khác,
hoặc tổ hợp các kiểu đã liệt kê nói trên. Các kỹ thuật làm sạch dữ liệu và tích hợp dữ
liệu có thể được thực hiện trên dữ liệu.

+ Server CSDL/Kho dữ liệu: Có trách nhiệm lấy dữ liệu liên quan dựa trên
yêu cầu của người KPDL.
+ Cơ sở tri thức: Đây là miền tri thức được sử dụng để hướng dẫn việc tìm
kiếm hoặc đánh giá sự thú vị của các mẫu quan tâm. Tri thức này có thể bao gồm các
mức phân cấp khái niệm, được sử dụng để tổ chức các thuộc tính hoặc giá trị thuộc
tính thành các cấp trừu tượng. Tri thức như độ tin cậy của người sử dụng, có thể được
sử dụng để đánh giá độ thú vị của mẫu. Các ví dụ khác của miền tri thức là các ràng
buộc thú vị bổ sung hoặc ngưỡng, và siêu dữ liệu (mô tả dữ liệu từ nhiều nguồn không
đồng nhất).
+ Bộ máy khai phá dữ liệu: Đây là thành phần cần thiết đối với hệ thống
KPDL, bao gồm một tập các chức năng như mô tả, phân tích tính kết hợp và tính
tương quan, phân lớp, dự báo, phân tích cụm, phân tích ngoại lai, và phân tích sự tiến
hóa.
+ Đánh giá mẫu: Thành phần này thường sử dụng các độ đo và tương tác với
thành phần KPDL để tập trung tìm kiếm các mẫu thú vị. Nó có thể sử dụng các
ngưỡng để lọc ra các mẫu phát hiện được. Ngoài ra, thành phần đánh giá mẫu có thể
được tích hợp với thành phần KPDL, phụ thuộc vào các phương pháp KPDL được sử
dụng.
+ Giao diện người dùng: Thành phần này là thành phần giao tiếp giữa người
sử dụng và hệ thống KPDL; cho phép người dùng tương tác với hệ thống bằng cách
xác định một truy vấn hoặc một nhiệm vụ KPDL, cung cấp thông tin để giúp tập trung
tìm kiếm, thăm dị và KPDL dựa trên kết quả KPDL trung gian. Ngoài ra, thành phần
này cho phép người dùng tìm các lược đồ CSDL, kho dữ liệu hoặc các cấu trúc dữ

13

liệu, đánh giá các mẫu khai phá được, và trực quan hoá các mẫu trong các dạng khác
nhau.

1.1.1.3. Ứng dụng của khai phá dữ liệu
Mặc dù KPDL là một xu hướng nghiên cứu tương đối mới, nhưng thu hút
nhiều nhà nghiên cứu bởi vì các ứng dụng thực tế của nó trong nhiều lĩnh vực. Sau
đây là một số ứng dụng tiêu biểu:
+ Phân tích dữ liệu và hỗ trợ ra quyết định: Ứng dụng này là phổ biến trong
thương mại, tài chính và thị trường chứng khốn,…
+ Y tế: Tìm kiếm sự liên quan tiềm năng giữa các triệu chứng, chẩn đoán, và
phương pháp điều trị,…
+ Khai phá text và web: Tóm tắt tài liệu, khơi phục văn bản và tìm kiếm văn
bản, phân lớp văn bản và siêu văn bản,…
+ Tin sinh học: Tìm kiếm và so sánh thơng tin di truyền điển hình hoặc đặc
biệt như bộ gen và DNA, các mối quan hệ ngầm giữa một số gen và một số bệnh di
truyền,….
+ Tài chính và thị trường chứng khốn: Kiểm tra dữ liệu để trích xuất thơng
tin dự đốn cho giá của các loại cổ phiếu,…
+ Những ứng dụng khác: Viễn thông, bảo hiểm y tế, thiên văn học, chống
khủng bố, thể thao,…

1.1.2. Khai phá tập mục độ hữu ích trung bình cao
Khai thác tập mục độ hữu ích cao (HUIM) đã trở thành một vấn đề quan trọng
trong những thập kỷ gần đây. Trong khai thác tập mục độ hữu ích cao truyền thống,
độ hữu ích của một tập mục được định nghĩa là tổng các hữu ích của các mục của nó,
trong các giao tác mà nó xuất hiện. Một vấn đề quan trọng với định nghĩa này là nó
khơng tính đến độ dài của tập mục. Bởi vì độ hữu ích của tập mục lớn thường lớn hơn
độ hữu ích của tập mục nhỏ, thuật toán khai thác tập mục độ hữu ích cao truyền thống
có xu hướng thiên về việc tìm kiếm một tập hợp các tập mục lớn. Vì vậy, định nghĩa
này không phải là một phép đo hợp lý về độ hữu ích. Để cung cấp một đánh giá tốt
hơn về độ hữu ích của từng tập mục, nhiệm vụ khai thác tập mục độ hữu ích trung

14

bình cao (HAUIM) đã được đề xuất. Nó giới thiệu thước đo độ hữu ích trung bình,
xem xét cả độ dài của tập mục và độ hữu ích của chúng, và do đó phù hợp hơn trong
các tình huống thực tế. Một số thuật toán đã được thiết kế cho nhiệm vụ này. Nhìn
chung, chúng có thể được phân loại thành các phương pháp tiếp cận theo cấp độ hoặc
theo mơ hình phát triển. Tuy nhiên, cả hai đều u cầu khối lượng tính tốn để tìm ra
các tập mục có độ hữu ích trung bình cao (HAUI) thực tế [12].
Ví dụ về CSDL giao tác: Cho tập các mục I={i1, i2,..., in}. Một giao tác T là
một tập con của I, T  I, CSDL giao tác là tập các giao tác D ={T1, T2,..., Tm}. Mỗi
giao tác được gán một định danh TID. CSDL này thường được sử dụng trong kinh
doanh thương mại hoặc các hệ thống ngân hàng. CSDL giao tác thường được biểu
diễn ở dạng ngang, dạng dọc và bảng ma trận.
Biểu diễn giao tác dạng ngang: Là trình bày giao tác dưới dạng một danh
sách, mỗi giao tác có một mã định danh riêng (TID), mỗi giao tác chứa một danh sách
các mục.
Bảng 1.1: Cơ sở dữ liệu giao tác (biểu diện dạng ngang)

TID

Mục

T1

a, b, c, f

T2

d, e, f, g

T3

a, b, d, e, f

T4

a, b, c, e

T5

d, e, f

T6

b, c, f, h

T7

d, e, f, g, h

T8

b, d, h

T9

b, d, f

T10

b, d, f

Biểu diễn giao tác dạng dọc: Là trình bày danh sách các mục dữ liệu, mỗi
mục dữ liệu chứa tất cả các mã định danh giao tác.

15

Bảng 1.2: Cơ sở dữ liệu giao tác (biểu diễn dạng dọc)

Mục

TID

a

T1, T3, T4

b

T1, T3, T4, T6, T8, T9, T10

c

T1, T4, T6

d

T2, T3, T5, T7, T8, T9, T10

e

T2, T3, T4, T5, T7

f

T1, T2, T3, T5, T6 , T7, T9, T10

g

T2, T7

h

T6, T7, T8

Biểu diễn dạng ma trận: Cho CSDL D = {T1, T2, …, Tn} trên tập các mục I
= {I1, I2, …, In} được biểu diễn bởi ma trận nhị phân M = (kpq)mxn
𝑘𝑝𝑞 = {

1 𝑘ℎ𝑖 𝑖𝑞 ∈ 𝑇𝑞
0 𝑘ℎ𝑖 𝑖𝑞 ∉ 𝑇𝑞

Với cơ sở dữ liệu từ Bảng 1.1 ta có ma trận giao tác như sau:
Bảng 1.3: Cơ sở dữ liệu giao tác (biểu diễn dạng ma trận)

TID

a