Luận văn thạc sĩ về bảo vệ tính riêng tư và luật trong khai phá dữ liệu

Khám phá luận văn thạc sĩ về bảo vệ tính riêng tư và luật kết hợp trong khai phá dữ liệu, cung cấp kiến thức chuyên sâu và ứng dụng thực tiễn.

• Tác giả: Lê Thị Minh Châu
• Người hướng dẫn: PGS. Đặng Trần Khánh
• Trường học: Đại học Bách Khoa - Đại học Quốc gia TP. Hồ Chí Minh
• Chuyên ngành: Khoa học máy tính
• Đề tài: Bảo vệ tính riêng tư và luật kết hợp trong khai phá dữ liệu
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2011
• Địa điểm: TP. Hồ Chí Minh

Tóm tắt

I. Giới thiệu

Trong bối cảnh công nghệ thông tin phát triển mạnh mẽ, việc thu thập và lưu trữ dữ liệu trở nên dễ dàng hơn bao giờ hết. Tuy nhiên, điều này cũng đặt ra thách thức lớn về bảo vệ dữ liệu và tính riêng tư. Các hệ thống khai thác dữ liệu có thể dẫn đến việc lộ thông tin nhạy cảm của cá nhân và tổ chức. Do đó, việc phát triển các phương pháp bảo vệ tính riêng tư trong khai thác dữ liệu là rất cần thiết. Đề tài này sẽ tập trung vào việc nghiên cứu và phát triển các mô hình bảo vệ tính riêng tư, đồng thời duy trì giá trị khai thác của dữ liệu. Đặc biệt, kỹ thuật k-anonymity và ℓ-diversity sẽ được áp dụng để đảm bảo rằng thông tin nhạy cảm không bị lộ ra ngoài trong quá trình khai thác dữ liệu.

1.1 Phát biểu vấn đề

Sự phát triển của công nghệ đã tạo ra một lượng dữ liệu khổng lồ, nhưng cũng đồng thời làm gia tăng nguy cơ rò rỉ thông tin riêng tư. Các thông tin nhạy cảm như tình trạng sức khỏe, thông tin tài chính có thể bị lạm dụng nếu không được bảo vệ đúng cách. Do đó, cần có các giải pháp hiệu quả để bảo vệ tính riêng tư trong khai thác dữ liệu mà vẫn đảm bảo tính tiện ích của dữ liệu. Việc nghiên cứu và phát triển các phương pháp bảo vệ tính riêng tư không chỉ giúp bảo vệ quyền lợi cá nhân mà còn góp phần nâng cao độ tin cậy của các hệ thống khai thác dữ liệu.

II. Cơ sở lý thuyết

Để bảo vệ tính riêng tư trong khai thác dữ liệu, nhiều phương pháp đã được đề xuất. Một trong những phương pháp phổ biến là k-anonymity, cho phép dữ liệu được biến đổi sao cho mỗi cá thể trong tập dữ liệu không thể được xác định một cách dễ dàng. Phương pháp này giúp giảm thiểu khả năng tái xác định cá nhân từ dữ liệu. Bên cạnh đó, ℓ-diversity được phát triển để đảm bảo rằng các thông tin nhạy cảm trong dữ liệu không chỉ được bảo vệ mà còn duy trì tính đa dạng. Điều này có nghĩa là trong mỗi nhóm k-anonymity, phải có ít nhất ℓ giá trị khác nhau cho các thuộc tính nhạy cảm. Việc áp dụng các phương pháp này không chỉ giúp bảo vệ tính riêng tư mà còn duy trì giá trị khai thác của dữ liệu, từ đó tạo ra những tri thức có ích từ dữ liệu.

2.1 Bảo vệ tính riêng tư cho dữ liệu trước khi khai phá

Các phương pháp bảo vệ tính riêng tư trước khi khai phá dữ liệu bao gồm việc thêm nhiễu vào dữ liệu gốc, hoán đổi dữ liệu, và áp dụng các kỹ thuật nặc danh. Phương pháp ngẫu nhiên là một trong những kỹ thuật đơn giản và hiệu quả, giúp che giấu thông tin nhạy cảm bằng cách thêm nhiễu vào dữ liệu. Tuy nhiên, việc này cũng có thể làm giảm giá trị khai thác của dữ liệu. Do đó, cần có sự cân nhắc giữa việc bảo vệ tính riêng tư và duy trì tính tiện ích của dữ liệu. Việc áp dụng các kỹ thuật như Migrate Member có thể giúp duy trì chất lượng dữ liệu trong khi vẫn bảo vệ tính riêng tư.

III. Các công trình liên quan

Nhiều nghiên cứu đã chỉ ra rằng việc áp dụng các phương pháp như k-anonymity và ℓ-diversity có thể giúp bảo vệ tính riêng tư trong khai thác dữ liệu. Các nghiên cứu này đã phát triển nhiều thuật toán khác nhau để cải thiện hiệu quả của các phương pháp này. Ví dụ, một số nghiên cứu đã chỉ ra rằng việc kết hợp Migrate Member với k-anonymity không chỉ bảo vệ tính riêng tư mà còn duy trì chất lượng dữ liệu cho các thuật toán khai thác dữ liệu cụ thể như khai thác luật kết hợp. Điều này cho thấy rằng việc nghiên cứu và phát triển các phương pháp bảo vệ tính riêng tư là một lĩnh vực quan trọng và cần thiết trong bối cảnh hiện nay.

3.1 Phương pháp k anonymity

Phương pháp k-anonymity đã được áp dụng rộng rãi trong nhiều lĩnh vực để bảo vệ tính riêng tư. Kỹ thuật này yêu cầu rằng mỗi cá thể trong tập dữ liệu phải không thể được phân biệt với ít nhất k-1 cá thể khác. Điều này giúp giảm thiểu khả năng tái xác định cá nhân từ dữ liệu. Tuy nhiên, phương pháp này cũng có những hạn chế, chẳng hạn như không đảm bảo rằng các thông tin nhạy cảm trong dữ liệu không bị lộ. Do đó, việc phát triển các phương pháp bổ sung như ℓ-diversity là cần thiết để đảm bảo rằng các thông tin nhạy cảm vẫn được bảo vệ trong quá trình khai thác dữ liệu.

Trích đoạn nội dung tài liệu

Chương 1: Giới thiệu 1.4 Mục tiêu đề tài 1. Đề xuất mô hình và phát triển một giải thuật biến đổi dữ liệu để đạt mô hình l-diversity nhằm hạn chế khả năng xác định thông tin riêng tư của các cá nhân, tổ chức đồng thời tận dụng được những ưu điểm của mô hình k-anonymity để hạn chế biến đổi dữ liệu nhằm duy trì tối đa có thể các luật kết hợp ẩn chứa trong dữ liệu. Xây dựng một ứng dụng minh họa sử dụng giải thuật đã đề xuất. Tập luật khai phá được từ dữ liệu đã được áp dụng kỹ thuật, giải thuật đã đề xuất 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.

Thời gian chạy của giải thuật không quá lâu để có thể chấp nhận được. Thử nghiệm, đo đạc, phân tích và đánh giá ưu điểm, nhược điểm giải thuật đã đề xuất lên tập dữ liệu thực tế. Trang 10 Chương 2: Cơ sở lý thuyết CHƯƠNG 2: CƠ SỞ LÝ THUYẾT 2.1 Bảo vệ tính riêng tư cho dữ liệu trước khi khai phá 2.1 Phương pháp ngẫu nhiên (Randomization) Phương pháp ngẫu nhiên bảo vệ tính riêng tư của dữ liệu bằng cách thêm nhiễu (noise) vào dữ liệu gốc để che giấu các thông tin nhạy cảm của các cá thể (các dòng dữ liệu). Nhiễu được thêm vào theo một cách phân bố nào đó và phải đủ mạnh để các thông tin nhạy cảm đã được che giấu không thể được lấy lại (recover) được.

Phương pháp này có ưu điểm là đơn giản và có thể hiện thực ở thời điểm thu thập dữ liệu bởi vì nhiễu được thêm vào một dòng 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ó một số nhược điểm: xử lý tất cả các dòng dữ liệu như nhau không quan tâm đến mật độ phân bố của các dòng dữ liệu nên các phần tử biên (outliers) dễ bị tấn công hơn các phần tử trong vùng có mật độ phân bố dày đặc; 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 đó [6, chương 2, trang 20]. Nhiễu hóa dựa trên cộng nhiễu (Additional Perturbation) Là kỹ thuật phổ biến nhất trong phương pháp ngẫu nhiên, áp dụng cho dữ liệu số liên tục (continous). Gọi X là một thuộc tính cần được bảo vệ của dữ liệu gốc X = {x … x }.

Với mỗi dòng dữ liệu x ϵ X, ta thêm thành phần nhiễu được rút trích từ hàm phân phối xác suất f (y), hàm này được biết công khai. Tập các thành phần nhiễu Y = {y … y }. Trang 11 Chương 2: Cơ sở lý thuyết Tập các dòng dữ liệu đã bị làm nhiễu là Z = {z … z } nghĩa là z = x + y sẽ được đưa cho các thành phần khai phá dữ liệu. Giả định rằng giá trị nhiễu thêm vào đủ lớn để các giá trị của dòng dữ liệu gốc không thể dễ dàng được suy ra từ dữ liệu đã bị làm nhiễu.

Do đó, các dòng dữ liệu gốc không thể được lấy lại được nhưng sự phân phối của các dòng dữ liệu gốc có thể được lấy lại được. Nhiễu hóa dựa trên nhân nhiễu (Multiplicative Pertubation) Áp dụng trên dữ liệu số liên tục (continuos). Thực hiện biến đổi dữ liệu giống như kỹ thuật nhiễu hóa dựa trên cộng nhiễu bao gồm dữ liệu gốc X, biến ngẫu nhiên Y với hàm phân phối được biết công khai nhưng dùng phép toán nhân để thêm giá trị nhiễu vào dữ liệu gốc nghĩa là Z = X*Y. Hoán đổi dữ liệu (data swapping) Áp dụng trên những thuộc tính phân loại (category) và thuộc tính số liên tục (continuous).

Kỹ thuật này 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 các dòng dữ liệu quá bất thường. Ưu điểm của kỹ thuật này là tổng lề bên dưới (lower marginal totals) của dữ liệu được bảo vệ và không bị nhiễu. Do đó các hàm tính toán mang tính tổng kết có thể 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.

Kỹ thuật này không tuân theo các nguyên lý cơ bản của phương pháp ngẫu nhiên (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) nên kỹ thuật này có thể được sử dụng kết hợp với các kỹ thuật khác như k-anonymity miễn là quy Trang 12 Chương 2: Cơ sở lý thuyết trình hoán đổi được thiết kế để bảo vệ tính riêng tư cho mô hình đó [6, chương 2, trang 19].2 Phương pháp nặc danh dựa trên nhóm Điểm yếu của phương pháp ngẫu nhiên 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 đó [6, chương 2, trang 20]. Các kỹ thuật trong phương pháp nặc danh dựa trên nhóm nhằm hạn chế điểm yếu này. Các thuộc tính được chia thành các loại: - Key identifier: là những thuộc tính xác định cụ thể cá thể như tên, số bảo hiểm xã hội. - Quasi-identifier (QI): các thuộc tính khi kết hợp với nhau sẽ xác định cụ thể cá thể như tuổi tác, zip-code, giới tính.

- Sensitive: là những thuộc tính nhạy cảm như: bệnh, tiền lương, tiểu sử phạm tội. Trong nhiều ứng dụng, để bảo mật dữ liệu các thuộc tính xác định cụ thể cá thể (identifier) như tên, số bảo hiểm xã hội thường được loại bỏ. Tuy nhiên, các thuộc tính thuộc loại quasi-identifier (pseudo-identifier) có thể được dùng để xác định chính xác các cá thể. Ví dụ các thuộc tính như tuổi, mã vùng (zip-code), sex có sẵn trong một tập dữ liệu có thể được kết hợp để xác định các cá thể tương ứng hoặc thu hẹp phạm vi tìm kiếm các cá thể.

Do đó việc loại bỏ trên không đủ để bảo vệ dữ liệu trước nguy cơ phơi bày thông tin. Các phơi bày được chia làm hai loại [20]: - 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 13 Chương 2: Cơ sở lý thuyết a.

Nhóm ít nhất k dòng này còn được gọi là lớp tương đương (equivalence class). Có 2 kỹ thuật được dùng để biến đổi một bảng đạt được k-anonymity:  Tổng quát hóa (Generalization): thay thế các giá trị của một thuộc tính bằng một giá trị tổng quát hơn. Việc tổng quát hóa dựa trên một phân cấp tổng quát hóa miền trị và một phân cấp tổng quát hóa giá trị tương ứng. Phân cấp tổng quát hóa miền trị có thứ tự toàn phần và phân cấp tổng quát hóa giá trị tương ứng là một cây, trong đó mối quan hệ cha/con diễn tả mối quan hệ tổng quát hóa/chuyên biệt hóa.

Kỹ thuật này được chia làm 2 loại:  Mức cell: thay thế giá trị một vài cell nào đó bằng một giá trị tổng quát hơn. Mức cell có thuận lợi là tránh được sự thay thế tất cả các giá trị của một thuộc tính nhưng có một bất lợi là tạo ra sự không đồng nhất các giá trị cho một thuộc tính nào đó.  Mức thuộc tính: thay thế giá trị của cột thuộc tính bằng giá trị tổng quát hơn. Mức thuộc tính thì có được sự đồng nhất tuy nhiên lại làm thay đổi nhiều trên dữ liệu gốc, mất mát nhiều thông tin.

 Kỹ thuật loại bỏ (Suppression): loại bỏ các thông tin nhạy cảm. Cách thức loại bỏ có thể được áp dụng ở các mức cell đơn (cell này sẽ nhận giá trị null hoặc unknown), toàn bộ một dòng hoặc toàn bộ một cột, cho phép giảm mức độ tổng quát hóa mà được dùng để đạt được k-anonymity. Rõ ràng các phương pháp như vậy giảm nguy cơ xác định cá thể nhưng cũng làm giảm độ chính xác của các ứng dụng khai phá trên tập dữ liệu đã bị biến đổi. Trang 14 Chương 2: Cơ sở lý thuyết Suppression Generalization Tuple Attribute Cell None AG_T AG_AS ≡ AG ≡ Attribute AG_CS S AG AG_AS CG_T S CG_AS CG_CS ≡ Cell CG≡ CG_CS Not Not CG applica applicable ble None TS AS CS Bảng 2.1: Phân loại các kỹ thuật k-anonymity [6, chương 5, trang 110] Một ví dụ về biến đổi dữ liệu để đạt k-anonymity Marital status Sex Hours #tuples (Hyp.

values) divorced M 35 2 (0Y,2N) divorced M 40 17 (16Y,1N) divorced F 35 2 (0Y,2N) married M 35 10 (8Y, 2N) married F 50 9 (2Y,7N) single M 40 26 (6Y, 20N) Bảng 2.2: Ví dụ đơn giản về bảng riêng tư [6, chương 5, trang 108] Giả sử Marital Status, Sex và Hour là các thuộc tính quasi-identifier.2 gộp chung các hàng có giá trị giống nhau ở tất cả các thuộc tính này. Cột #tuples cho biết số các hàng giống nhau.values cho biết số người bị chứng cao huyết áp và số người không bị. Cụ thể, hàng thứ nhất cho biết: có 2 người đã ly hôn, giới tính là nam, số giờ làm việc trong tuần là 35 thì không có người nào bị bệnh cao huyết áp. Mức độ nặc danh của bảng là k = 2.

Ta có phân cấp tổng quát hóa cho các thuộc tính như sau [6, chương 5, trang 108]: Trang 15 Chương C 2 Cơ sở lý thuyếtt 2: Hình 2.11: Thuộc tínnh Marital__status Hìn nh 2.2: Thuuộc tính Seex Hìnnh 2.3: Thuuộc tính Hoour Từ sơ c này, giiả sử ta tổnng quát hóaa mức thuộộc tính cho thuộc tínhh ơ đồ phân cấp Seex (từ S0  S1) ta đư ược bảng có c mức nặcc danh k = 4. Marital status Sexx Hoours #tuplles (Hyp. values) divorced Anyy_sex 35 4 (0Y,4N N) divorced Anyy_sex 40 17 (16Y,1 1N) married Anyy_sex 35 10 (8Y, 2N) 2 married Anyy_sex 50 9 (2Y,7N N) Single Anyy_sex 40 26 (6Y, 20N) 2 Bảng 2.3: Tổng quáát hóa bảngg 2.2 dựa trrên thuộc tính t Sex Trang 16 6 Chương 2: Cơ sở lý thuyết Tiếp tục áp dụng tổng quát hóa mức thuộc tính lên thuộc tính Marital status (Từ M0  M1), ta được bảng với k = 9 như sau: Marital status Sex Hours #tuples (Hyp. values) Been_married Any_sex 35 14 (8Y,6N) Been_married Any_sex 40 17 (16Y,1N) Been_married Any_sex 50 9 (2Y,7N) Never_married Any_sex 40 26 (6Y, 20N) Bảng 2.4: Tổng quát hóa bảng 2.3 dựa trên thuộc tính Marital status Tiếp tục áp dụng tổng quát hóa mức thuộc tính lên thuộc tính Marital status (Từ M1  M2), ta được bảng với k = 9, mức độ nặc danh không tăng lên.