Tổng quan luận án

Trong khai phá dữ liệu (KPDL) từ cơ sở dữ liệu (CSDL) giao tác, kỹ thuật khai phá tập mục thường xuyên và luật kết hợp truyền thống chỉ dựa trên tần suất xuất hiện đồng thời của các mục mà không phân biệt vai trò hay giá trị kinh tế của từng mục. Khai phá hữu ích cao (High Utility Itemset Mining - HUIM) được đề xuất nhằm giải quyết hạn chế này bằng cách tích hợp đồng thời hữu ích nội (số lượng mua trong từng giao tác) và hữu ích ngoại (lợi nhuận hoặc giá trị của từng mặt hàng). Khi nhu cầu chia sẻ dữ liệu kinh doanh và hợp tác thương mại gia tăng, CSDL giao tác có nguy cơ làm lộ các tri thức chiến lược hoặc bí mật kinh doanh. Bài toán bảo vệ tính riêng tư trong khai phá hữu ích cao (Privacy Preserving Utility Mining - PPUM) đặt ra yêu cầu sửa đổi CSDL gốc thành CSDL sửa đổi sao cho các mẫu hữu ích cao nhạy cảm không thể bị khai thác, đồng thời hạn chế tối đa các hiệu ứng phụ làm suy giảm chất lượng dữ liệu.

Khoảng trống nghiên cứu được luận án chỉ ra bao gồm:

  1. Các thuật toán che giấu tập mục hữu ích cao nhạy cảm theo tiếp cận heuristic hiện tại áp dụng chiến lược lựa chọn mục mục tiêu giống nhau cho cả hai thao tác sửa giá trị hữu ích nội và xóa mục khỏi giao tác, dẫn đến việc mất nhiều mẫu hữu ích cao không nhạy cảm.
  2. Các thuật toán ẩn tập mục hữu ích cao và phổ biến nhạy cảm trước đây chưa phân tách chiến lược xử lý độc lập giữa việc giảm độ hỗ trợ và giảm giá trị hữu ích.
  3. Chưa có các công trình công bố về mô hình và thuật toán che giấu tập mục hữu ích trung bình cao nhạy cảm cũng như ẩn luật kết hợp hữu ích cao nhạy cảm.
  4. Việc ứng dụng công cụ toán học như lý thuyết giàn vào bài toán che giấu thông tin nhạy cảm trong khai phá hữu ích cao còn hạn chế do đặc tính không thỏa mãn tính chất bao đóng giảm dần của tập hữu ích cao.

Mục tiêu nghiên cứu của luận án được xác định gồm hai mục tiêu chính:

  • Mục tiêu 1: Nghiên cứu và đề xuất các thuật toán ẩn tập mục hữu ích cao nhạy cảm, tập mục hữu ích cao và phổ biến nhạy cảm, tập mục hữu ích trung bình cao nhạy cảm và luật kết hợp hữu ích cao nhạy cảm dựa trên kỹ thuật heuristic.
  • Mục tiêu 2: Nghiên cứu và áp dụng lý thuyết Giàn để giảm hiệu ứng phụ trong quá trình che giấu thông tin nhạy cảm trong khai phá hữu ích cao.

Đối tượng và phạm vi nghiên cứu:

  • Đối tượng nghiên cứu: CSDL giao tác; các thuật toán ẩn tập mục hữu ích cao nhạy cảm (SHUIs), ẩn tập mục hữu ích cao và phổ biến nhạy cảm (SHUFIs), ẩn tập mục hữu ích trung bình cao nhạy cảm (SHAUIs), ẩn luật kết hợp hữu ích cao nhạy cảm (HRs); cơ sở toán học giàn giao của tập hợp.
  • Phạm vi nghiên cứu: Tập trung vào kỹ thuật che giấu mẫu nhạy cảm (sensitive patterns) từ CSDL giao tác tĩnh thông qua phương pháp heuristic làm xáo trộn dữ liệu (data distortion) và cấu trúc giàn giao có ràng buộc; thực nghiệm đánh giá trên các CSDL mẫu chuẩn và ngẫu nhiên.

Tổng quan tài liệu và vị trí của luận án

Luận án tổng quan các hướng nghiên cứu nền tảng trong khai phá hữu ích cao và bảo vệ tính riêng tư trong KPDL:

Về khai phá tập mục phổ biến có trọng số và khai phá hữu ích cao:

  • Khai phá tập mục phổ biến có trọng số: Cai và cộng sự (1998) đề xuất độ hỗ trợ trọng số và thuật toán MINWAL dựa trên Apriori; Yun U. và cộng sự đề xuất thuật toán WFIM sử dụng cấu trúc FP-Tree.
  • Khai phá tập mục hữu ích cao (HUIM): Hong Yao và cộng sự (2004, 2006) đặt nền móng lý thuyết với ràng buộc hữu ích và các thuật toán Uming, UmingH; Liu Y. và cộng sự (2005) đề xuất thuật toán TwoPhase sử dụng độ đo Transaction-Weighted-Utilization (TWU); Erwin và cộng sự (2007) đề xuất thuật toán CTU-Mine dựa trên CTU-tree; Liu và cộng sự (2012) giới thiệu thuật toán HUI-Miner với cấu trúc utility-list; Tseng và cộng sự (2010, 2013) phát triển UP-Growth, UP-Growth+ dựa trên cây UP-Tree và mô hình khai phá tập hữu ích cao đóng (CHUIs) cùng thuật toán DAHU; Chu và cộng sự (2009) đề xuất HUINIV-Mine xử lý hữu ích âm; Philippe Fournier-Viger (2014) đề xuất FHN dựa trên FHM và kỹ thuật tỉa EUCP.
  • Các mô hình mở rộng: Pillai và cộng sự đề xuất thuật toán HURI, V. Goyal và cộng sự đề xuất UP-Rare-Growth trong khai phá tập mục hữu ích cao hiếm (HURIM); Fournier-Viger và cộng sự mở rộng thuật toán EFIM, Uday Kiran và cộng sự đề xuất HU-FIMi trong khai phá tập mục hữu ích cao và phổ biến (HUFIM); Hong Tzung-Pei và cộng sự (2009), Lin và cộng sự đề xuất HAUIMiner trong khai phá tập mục hữu ích trung bình cao (HAUIM); Jayakrushna Sahoo và cộng sự (2015), Thang Mai và cộng sự (2017) nghiên cứu khai phá luật kết hợp hữu ích cao.

Về che giấu thông tin nhạy cảm trong khai phá dữ liệu và khai phá hữu ích cao:

  • Các hướng tiếp cận che giấu mẫu nhạy cảm: Heuristic (làm xáo trộn dữ liệu, khóa dữ liệu), bảo vệ biên (border-based), chính xác (exact-based).
  • Che giấu tập mục hữu ích cao nhạy cảm (SHUIs): Jieh-Shan Yeh và cộng sự (2010) mở đầu với hai thuật toán HHUIF và MSICF; Lin và cộng sự (2014, 2015) đề xuất thuật toán dựa trên giải thuật di truyền GA-based (chèn giao tác giả) và PPUMGAT (xóa giao tác); Lin và cộng sự (2016) đề xuất MSU-MAU và MSU-MIU; Xuan Liu và cộng sự (2020) đề xuất SMAU, SMIU và SMSE.
  • Che giấu tập mục hữu ích cao và phổ biến nhạy cảm (SHUFIs): Rajalaxmi và cộng sự (2012) đề xuất MSMU và MCRSU; Lin và cộng sự đề xuất HUFI.
  • Ứng dụng lý thuyết giàn: Wille (1982), Godin (1995), Keyun Hu (2000), JiYe Liang và cộng sự (2009), B. Vo (2012), Thang Mai và cộng sự (2017); Hai Quoc Le và cộng sự (2014, 2016) áp dụng giàn để ẩn luật kết hợp nhạy cảm trong khai phá tập phổ biến.

Vị trí của luận án: Luận án kế thừa các mô hình khai phá hữu ích cao và kỹ thuật heuristic xáo trộn dữ liệu, khắc phục các điểm hạn chế về chiến lược chọn mục mục tiêu của các thuật toán tiền nhiệm, đề xuất các mô hình mới chưa từng được công bố (SHAUIs, HRs), đồng thời phát triển cấu trúc giàn giao có ràng buộc nhằm tối ưu hóa việc chọn mục sửa đổi trong bài toán SHUFIs.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết và các định nghĩa toán học

Cho tập các mục $I = {x_1, x_2, \dots, x_m}$, mỗi mục $x \in I$ có giá trị hữu ích ngoại $p(x)$. CSDL giao tác $D = {T_1, T_2, \dots, T_n}$, mỗi giao tác $T_c$ gắn với định danh $Tid$ và mỗi mục $x \in T_c$ có hữu ích nội $q(x, T_c)$.

  • Hữu ích của mục $x$ trong giao tác $T_c$: $u(x, T_c) = q(x, T_c) \times p(x)$.
  • Hữu ích của tập mục $X \subseteq I$ trong giao tác $T_c$: $u(X, T_c) = \sum_{x \in X} u(x, T_c)$.
  • Hữu ích của tập mục $X$ trong CSDL $D$: $u(X) = \sum_{X \subseteq T_c \wedge T_c \in D} u(X, T_c)$.
  • Hữu ích của giao tác $T_c$: $TU(T_c) = \sum_{x \in T_c} u(x, T_c)$. Tổng hữu ích CSDL: $DU(D) = \sum_{T_c \in D} TU(T_c)$.
  • Tập mục hữu ích cao (HUIs): $HUIs = {X \mid X \subseteq I, u(X) \ge \varepsilon}$, với $\varepsilon$ là ngưỡng hữu ích tối thiểu.
  • Tập mục hữu ích cao và phổ biến (HUFIs): $HUFIs = {X \mid u(X) \ge \varepsilon \wedge support(X) \ge \delta}$, với $\delta$ là ngưỡng hỗ trợ tối thiểu và $support(X) = |{T_c \mid X \subseteq T_c, T_c \in D}| / |D|$.
  • Tập mục hữu ích trung bình cao (HAUIs): $au(X, T_c) = u(X, T_c) / |X|$; $au(X) = \sum_{X \subseteq T_c \wedge T_c \in D} au(X, T_c)$; $HAUIs = {X \mid au(X) \ge \mu}$, với $\mu$ là ngưỡng hữu ích trung bình tối thiểu.
  • Luật kết hợp hữu ích cao (HRs): Luật $R: X \to Y$ với $X, Y \subseteq I, X \cap Y = \emptyset$. Giá trị hữu ích cục bộ $luv(X, XY) = \sum_{XY \subseteq T_c \wedge T_c \in D} \sum_{x \in X} u(x, T_c)$; độ tin cậy hữu ích $uconf(R) = luv(X, XY) / u(X)$; $HRs = {R: X \to Y \mid uconf(R) \ge \mu}$.

Các đơn vị đo lường đánh giá hiệu ứng phụ

Ký hiệu Tên đơn vị đo Công thức xác định Ý nghĩa đánh giá
HF Hiding Failure $HF = \frac{|SHUPs'|}{|SHUPs|}$ Tỷ lệ mẫu nhạy cảm không ẩn được sau khi sửa đổi CSDL.
MC Miss Cost $MC = \frac{|non\text{-}SHUPs \setminus non\text{-}SHUPs'|}{|non\text{-}SHUPs|}$ Tỷ lệ mẫu hữu ích cao không nhạy cảm bị mất do sửa đổi CSDL.
AC Artificial Cost $AC = \frac{|non\text{-}SHUPs' \setminus non\text{-}SHUPs|}{|non\text{-}SHUPs|}$ Tỷ lệ mẫu giả mạo xuất hiện trong CSDL sửa đổi.
DSS Database Structure Similarity $DSS = \frac{\sum_{k=1}^m \min(freq(tp_k^D), freq(tp_k^{D'}))}{\sum_{k=1}^m \max(freq(tp_k^D), freq(tp_k^{D'}))}$ Mức độ tương đồng về tần suất các mẫu giao tác giữa CSDL gốc và sửa đổi.
DUS Database Utility Similarity $DUS = \frac{DU(D')}{DU(D)}$ Mức độ tương đồng về tổng giá trị hữu ích của CSDL sau khi sửa đổi.
IUS Itemsets Utility Similarity $IUS = \frac{\sum_{X \in HUIs'} u'(X)}{\sum_{X \in HUIs} u(X)}$ Mức độ tương đồng về tổng giá trị hữu ích của các tập mục hữu ích cao.

Phương pháp nghiên cứu và nguồn dữ liệu thực nghiệm

Luận án sử dụng phương pháp nghiên cứu kết hợp giữa xây dựng mô hình toán học giải tích, thiết kế giải thuật và kiểm nghiệm thực nghiệm định lượng trên máy tính. Các thuật toán được cài đặt và kiểm thử trên 6 bộ CSDL giao tác chuẩn và ngẫu nhiên với các đặc trưng cấu trúc khác nhau.

Tên CSDL Tổng số giao tác (|D|) Tổng số mục (|I|) Chiều dài trung bình (AVG-length) Chiều dài tối đa (Max-length) Nguồn gốc dữ liệu
T1000_200_40 1.000 200 7,23 40 Sinh ngẫu nhiên bằng chương trình Java
Foodmart 4.141 1.559 4,4 14 Thư viện mã nguồn mở SPMF
Retail 88.162 16.470 10,3 76 Thư viện mã nguồn mở SPMF
Mushroom 8.124 119 23,0 23 Thư viện mã nguồn mở SPMF
Chess 3.196 75 37,0 37 Thư viện mã nguồn mở SPMF
Chainstore 1.112.949 46.086 7,23 170 Thư viện mã nguồn mở SPMF

Nội dung chính theo từng chương

Chương 1: Tổng quan về khai phá hữu ích cao và che giấu thông tin nhạy cảm trong khai phá hữu ích cao từ cơ sở dữ liệu giao tác

Chương 1 hệ thống hóa cơ sở lý thuyết về khai phá hữu ích cao và bài toán bảo vệ tính riêng tư trong khai phá dữ liệu:

  • Trình bày chi tiết các khái niệm nền tảng: cấu trúc CSDL giao tác có trọng số, giá trị hữu ích nội, hữu ích ngoại, hữu ích giao tác và các mô hình mở rộng gồm khai phá tập mục hữu ích cao và phổ biến (HUFIM), khai phá tập mục hữu ích trung bình cao (HAUIM) và khai phá luật kết hợp hữu ích cao.
  • Phân loại bài toán che giấu thông tin nhạy cảm thành hai nhánh: che giấu dữ liệu nhạy cảm (áp dụng ngẫu nhiên hóa, nặc danh hóa nhóm $k$-anonymity, $l$-diversity, $t$-closeness) và che giấu mẫu nhạy cảm (heuristic, border-based, exact-based). Trọng tâm nghiên cứu của luận án thuộc nhánh che giấu mẫu nhạy cảm trong khai phá hữu ích cao bằng kỹ thuật heuristic.
  • Định nghĩa chi tiết hệ thống 6 chỉ số đánh giá chất lượng CSDL sửa đổi ($HF, MC, AC, DSS, DUS, IUS$) làm thước đo thực nghiệm cho toàn bộ luận án.
  • Tổng quan ứng dụng lý thuyết giàn trong KPDL, phân tích khả năng mở rộng của giàn khái niệm và giàn tập phổ biến đóng sang lĩnh vực khai phá hữu ích cao.
  • Trình bày đặc tả chi tiết 6 CSDL thực nghiệm sử dụng trong các chương tiếp theo.

Chương 2: Che giấu thông tin nhạy cảm trong khai phá hữu ích cao dựa trên kỹ thuật heuristic

Chương 2 tập trung đề xuất quy trình 3 bước và 4 thuật toán/mô hình che giấu thông tin nhạy cảm dựa trên kỹ thuật heuristic:

Quy trình 3 bước che giấu mẫu nhạy cảm:

  1. Bước 1: Khai phá tập mẫu hữu ích cao từ CSDL gốc và xác định tập mẫu nhạy cảm cần che giấu dựa trên ngưỡng thiết lập.
  2. Bước 2: Lặp quá trình sửa đổi dữ liệu gốc (giảm giá trị hữu ích nội hoặc xóa mục) để làm cho các mẫu nhạy cảm không còn thỏa mãn ngưỡng tối thiểu.
  3. Bước 3: Đánh giá chất lượng CSDL sửa đổi thông qua việc khai phá lại và tính toán các chỉ số hiệu ứng phụ.

Thuật toán ẩn tập mục hữu ích cao nhạy cảm đề xuất (EHSHUI):

  • Phát biểu bài toán và xác định lượng hữu ích tối thiểu cần giảm để ẩn tập mục nhạy cảm $S$: $du = u(S) - \varepsilon + 1$.
  • Chiến lược sắp xếp thứ tự ẩn: Tính độ phổ biến $f_{SHUIs}(S) = |{X \mid S \subset X, X \in SHUIs}|$ và sắp xếp giảm dần để ưu tiên ẩn tập mục xuất hiện nhiều nhất trong các tập nhạy cảm khác.
  • Lựa chọn giao tác mục tiêu ($T_{vic}$): Thuật toán findVictimTransaction chọn giao tác $T \in D_S$ có giá trị $u(S, T)$ lớn nhất.
  • Lựa chọn mục mục tiêu ($x_{vic}$): Thuật toán findVictimItem chọn mục trong $S$ sao cho khi sửa đổi sẽ làm mất ít tập mục không nhạy cảm (non-SHUIs) nhất.
  • Quy tắc sửa đổi dữ liệu dựa trên hai định lý:
    • Định lý 2.1: Nếu $u(x_{vic}, T_{vic}) > du$, chỉ cần giảm giá trị hữu ích nội của $x_{vic}$ một lượng $dec = \lceil du / p(x_{vic}) \rceil$, khi đó $q(x_{vic}, T_{vic}) = q(x_{vic}, T_{vic}) - dec$ và $du = 0$.
    • Định lý 2.2: Nếu $u(x_{vic}, T_{vic}) \le du$, xóa mục $x_{vic}$ khỏi $T_{vic}$, giá trị hữu ích của $S$ giảm $u(S, T_{vic})$ và cập nhật $du = du - u(S, T_{vic})$.

Thuật toán ẩn tập mục hữu ích cao và phổ biến nhạy cảm đề xuất (ATMTU):

  • Tách biệt chiến lược chọn mục mục tiêu cho hai trường hợp: giảm độ hỗ trợ (xóa mục để giảm số giao tác hỗ trợ) và giảm giá trị hữu ích (sửa giá trị hữu ích nội).
  • Giảm thiểu hiện tượng mất mẫu không nhạy cảm so với các thuật toán MSMU, MCRSU và HUFI.

Mô hình và thuật toán ẩn tập mục hữu ích trung bình cao nhạy cảm (EHSHA-UI):

  • Xây dựng bài toán và công thức tính độ giảm hữu ích trung bình $dau = au(S) - \mu + \epsilon$.
  • Đề xuất thuật toán tìm giao tác và mục mục tiêu tối ưu, chứng minh hiệu quả giảm MC và nâng cao DSS, DUS, IUS so với thuật toán đối sánh HHAUSI.

Mô hình và thuật toán ẩn luật kết hợp hữu ích cao nhạy cảm:

  • Phát biểu bài toán che giấu luật $R: X \to Y$ có $uconf(R) \ge \mu$.
  • Cơ chế sửa đổi: Giảm giá trị hữu ích cục bộ $luv(X, XY)$ hoặc tăng giá trị hữu ích $u(X)$ trong các giao tác liên quan để đưa $uconf(R) < \mu$.

Chương 3: Che giấu thông tin nhạy cảm trong khai phá hữu ích cao dựa trên lý thuyết Giàn

Chương 3 giải quyết bài toán tối ưu hóa lựa chọn mục mục tiêu trong che giấu tập mục hữu ích cao và phổ biến nhạy cảm (SHUFIs) bằng công cụ toán học giàn giao:

  • Cơ sở lý thuyết giàn: Trình bày quan hệ hai ngôi, giàn sắp thứ tự, giàn đại số, giàn của tập hợp và giàn giao của tập phổ biến.
  • Xây dựng Giàn giao có ràng buộc của tập các tập mục hữu ích cao và phổ biến ($L_\cap^H$): Cấu trúc giàn biểu diễn thứ tự bao hàm giữa các tập mục thuộc $HUFIs$.
  • Thuật toán HSUFIBL (Hiding Sensitive Utility and Frequent Based on Lattice):
    • Tận dụng cấu trúc liên kết nút cha - con trong $L_\cap^H$ để tính toán chính xác mức độ ảnh hưởng của việc sửa đổi một mục lên toàn bộ không gian các tập mục không nhạy cảm.
    • Lựa chọn mục mục tiêu có số lượng nút bị tác động tiêu cực trong giàn là nhỏ nhất.
  • Kết quả thực nghiệm: Đánh giá so sánh thuật toán HSUFIBL với các thuật toán đối sánh trên các tham số: kích thước tập nhạy cảm, ngưỡng hỗ trợ $\delta$ và ngưỡng hữu ích $\varepsilon$. Kết quả chỉ ra HSUFIBL luôn đạt $HF = 0$, đồng thời các chỉ số $MC$ thấp hơn, các chỉ số $DSS, DUS, IUS$ cao hơn và thời gian thực thi duy trì ổn định.

Kết quả và những đóng góp mới

Luận án đạt được các kết quả và đóng góp khoa học chính sau đây:

  1. Đóng góp về mô hình lý thuyết:
  • Đề xuất mô hình toán học và thuật toán che giấu tập mục hữu ích trung bình cao nhạy cảm (SHAUIs) từ CSDL giao tác.
  • Đề xuất mô hình toán học và thuật toán che giấu luật kết hợp hữu ích cao nhạy cảm (HRs) từ CSDL giao tác.
  • Xây dựng cấu trúc Giàn giao có ràng buộc của tập các tập mục hữu ích cao và phổ biến ($L_\cap^H$), mở rộng phạm vi ứng dụng của lý thuyết giàn trong lĩnh vực PPUM.
  1. Đóng góp về thuật toán và kỹ thuật xử lý:
  • Thuật toán EHSHUI: Cải tiến phương pháp ẩn tập mục hữu ích cao nhạy cảm nhờ phân định rõ hai trường hợp sửa hữu ích nội ($dec = \lceil du / p(x_{vic}) \rceil$) và xóa mục, kết hợp chiến lược sắp xếp độ phổ biến $f_{SHUIs}(S)$ giúp giảm thiểu hiệu ứng phụ $MC$.
  • Thuật toán ATMTU: Cải tiến việc ẩn tập mục hữu ích cao và phổ biến nhạy cảm bằng cách phân tách độc lập cơ chế chọn mục cho hai điều kiện hỗ trợ và hữu ích.
  • Thuật toán HSUFIBL: Ứng dụng cấu trúc giàn giao $L_\cap^H$ để tối ưu hóa việc chọn mục mục tiêu, duy trì tỷ lệ ẩn thành công $HF = 0$ và nâng cao độ tương đồng dữ liệu.

  1. Các công trình khoa học đã công bố: Kết quả nghiên cứu của luận án được công bố trong 9 công trình khoa học, bao gồm 1 bài báo trên tạp chí thuộc danh mục ISI (Q3) - Intelligent Data Analysis (2020), 1 bài báo trên tạp chí thuộc danh mục Scopus (Q2) - Cybernetics and Information Technologies (2022), 2 bài báo trong kỷ yếu hội thảo quốc tế (Springer INISCOM 2018, IEEE MAPR 2018), và 5 bài báo trong kỷ yếu các hội nghị quốc gia chuyên ngành (FAIR 10, FAIR 13, FAIR 14, FAIR 15, ICT 2018).

  2. Kiến nghị và giải pháp đề xuất:

  • Khuyến nghị các cơ quan, doanh nghiệp áp dụng thuật toán EHSHUI và HSUFIBL vào quy trình tiền xử lý, khử định danh dữ liệu giao tác trước khi thực hiện chia sẻ dữ liệu kinh doanh cho đối tác bên ngoài.

Hạn chế và hướng nghiên cứu tiếp

Hạn chế của luận án:

  • Các mô hình và thuật toán đề xuất trong luận án được thiết kế và kiểm thử trên CSDL giao tác tĩnh, chưa mở rộng cho các dạng CSDL phân tán hoặc luồng dữ liệu biến đổi liên tục (data streams).
  • Cấu trúc lý thuyết giàn mới chỉ được áp dụng cho trường hợp tập mục hữu ích cao kết hợp điều kiện phổ biến (HUFIs) do tính chất không đơn điệu (non-monotonicity) của hàm hữu ích trong bài toán HUIM tổng quát.

Hướng nghiên cứu tiếp theo:

  • Nghiên cứu phát triển các kỹ thuật che giấu thông tin nhạy cảm cho CSDL gia tăng (incremental databases) và luồng dữ liệu giao tác thời gian thực.
  • Tìm kiếm các cấu trúc đại số và mô hình toán học mới nhằm áp dụng kỹ thuật cấu trúc cho bài toán khai phá hữu ích cao tổng quát không kèm ràng buộc hỗ trợ.
  • Tối ưu hóa hiệu năng tính toán của các thuật toán trên môi trường dữ liệu lớn (Big Data).

Giá trị tham khảo

Luận án là tài liệu tham khảo chuyên khảo trong lĩnh vực Khoa học máy tính và Hệ thống thông tin:

  • Đối với nghiên cứu sinh và học viên cao học: Luận án cung cấp hệ thống định nghĩa toán học chuẩn xác, mã giả giải thuật chi tiết của các thuật toán PPUM (EHSHUI, ATMTU, EHSHA-UI, HSUFIBL), và phương pháp luận áp dụng lý thuyết giàn trong KPDL.
  • Đối với giảng viên và nhà nghiên cứu: Cung cấp tài liệu tổng quan toàn diện về các cấu trúc dữ liệu (utility-list, UP-Tree) và các độ đo đánh giá hiệu ứng phụ dữ liệu ($HF, MC, AC, DSS, DUS, IUS$).
  • Đối với chuyên viên phân tích dữ liệu và kỹ sư phần mềm: Cung cấp giải pháp kỹ thuật cụ thể để làm sạch và bảo mật CSDL giao tác thương mại trước khi chia sẻ ra môi trường bên ngoài.

Câu hỏi thường gặp

Câu hỏi 1: Tại sao khai phá tập mục hữu ích cao (HUIM) lại phức tạp hơn khai phá tập mục phổ biến truyền thống (FIM)? Trả lời: Trong FIM, độ hỗ trợ thỏa mãn tính chất bao đóng giảm dần (Apriori property: mọi tập con của một tập phổ biến đều là tập phổ biến). Ngược lại, trong HUIM, giá trị hữu ích không thỏa mãn tính chất này (một tập mục là hữu ích cao thì tập con của nó có thể không là hữu ích cao, và ngược lại tập con không hữu ích cao nhưng tập cha có thể là hữu ích cao). Do đó, không thể áp dụng trực tiếp tính chất Apriori để tỉa không gian tìm kiếm, đòi hỏi phải phát triển các cấu trúc chặn trên như TWU hoặc utility-list.

Câu hỏi 2: Trong thuật toán EHSHUI, lượng giá trị hữu ích nội tối thiểu cần giảm ($dec$) của mục mục tiêu được tính như thế nào? Trả lời: Theo Định lý 2.1, khi mục mục tiêu $x_{vic}$ tại giao tác $T_{vic}$ có $u(x_{vic}, T_{vic}) > du$ (với $du = u(S) - \varepsilon + 1$), giá trị hữu ích nội tối thiểu cần giảm được xác định chính xác theo công thức $dec = \lceil du / p(x_{vic}) \rceil$, trong đó $p(x_{vic})$ là giá trị hữu ích ngoại của mục $x_{vic}$.

Câu hỏi 3: Chỉ số Miss Cost (MC) và Artificial Cost (AC) phản ánh điều gì trong đánh giá thuật toán PPUM? Trả lời: Chỉ số MC phản ánh tỷ lệ các mẫu hữu ích cao không nhạy cảm có trong CSDL gốc nhưng bị mất đi (không khai thác được) từ CSDL sửa đổi. Chỉ số AC phản ánh tỷ lệ các mẫu vốn không phải là mẫu hữu ích cao trong CSDL gốc nhưng lại trở thành mẫu hữu ích cao trong CSDL sửa đổi do quá trình sửa dữ liệu gây ra. Mục tiêu của các thuật toán là cực tiểu hóa cả hai chỉ số này.

Câu hỏi 4: Cấu trúc Giàn giao có ràng buộc ($L_\cap^H$) giúp ích gì trong việc che giấu tập mục hữu ích cao và phổ biến nhạy cảm ở Chương 3? Trả lời: Cấu trúc $L_\cap^H$ tổ chức các tập mục thuộc $HUFIs$ theo thứ tự bao hàm khái niệm, cho phép thuật toán HSUFIBL định lượng chính xác mức độ ảnh hưởng lan truyền của việc xóa/sửa một mục lên toàn bộ các tập mục không nhạy cảm trong giàn, từ đó chọn ra mục mục tiêu gây ra ít tác động phụ tiêu cực nhất.

Câu hỏi 5: Thuật toán EHSHUI giải quyết hạn chế của các thuật toán MSICF và MSU-MAU như thế nào? Trả lời: Các thuật toán MSICF và MSU-MAU áp dụng quy tắc chọn mục mục tiêu đồng nhất cho cả thao tác xóa và sửa hữu ích nội, đồng thời có thể tiếp tục sửa dữ liệu ngay cả khi mẫu đã được ẩn hoặc khi $u(S) = \varepsilon$. EHSHUI khắc phục bằng cách phân định rõ hai trường hợp sửa đổi (Định lý 2.1 và Định lý 2.2), tính toán chính xác lượng giảm tối thiểu $dec$, và thiết lập $du = 0$ ngay khi mẫu được ẩn thành công.

Kết luận

Luận án đã giải quyết bài toán bảo vệ tính riêng tư trong khai phá hữu ích cao từ CSDL giao tác thông qua việc phát triển 4 thuật toán heuristic cải tiến (EHSHUI, ATMTU, EHSHA-UI và ẩn luật kết hợp hữu ích cao nhạy cảm) và 1 thuật toán tối ưu hóa dựa trên cấu trúc giàn giao có ràng buộc (HSUFIBL). Các thuật toán đề xuất đạt tỷ lệ che giấu thành công tuyệt đối ($HF = 0$), đồng thời giảm thiểu tỷ lệ mất mẫu không nhạy cảm ($MC$) và bảo toàn tối đa độ tương đồng cấu trúc cũng như giá trị hữu ích của CSDL ($DSS, DUS, IUS$). Kết quả nghiên cứu đã mở rộng lý thuyết PPUM cho các mô hình hữu ích trung bình cao và luật kết hợp hữu ích cao, đóng góp 9 công trình khoa học trên các tạp chí ISI, Scopus và kỷ yếu hội nghị chuyên ngành uy tín.