VIETNAM NATIONAL UNIVERSITY HO CHI MINH CITY HO CHI MINH CITY UNIVERSITY OF TECHNOLOGY NHAM LAP HANH PRIVACY PRESERVING IN SHARING DATA Major: : COMPUTER SCIENCE Code: : 8480101 MASTER’S THESIS HO CHI MINH CITY, July 2023 THIS THESIS IS COMPLETED AT HO CHI MINH CITY UNIVERSITY OF TECHNOLOGY – VNU-HCM Supervisor : Dr. TRUONG TUAN ANH Examiner 1: Assoc. NGUYEN TUAN DANG Examiner 2: Assoc. NGUYEN VAN VU This master’s thesis is defended at HCM City University of Technology, VNU - HCM City on July 11, 2023.
Master’s Thesis Committee: 1. LE HONG TRANG 2. PHAN TRONG NHAN 3. NGUYEN TUAN DANG 4.
NGUYEN VAN VU 5. TRUONG TUAN ANH Approval of the Chairman of Master’s Thesis Committee and Dean of Faculty of Computer Science and Engineering after the thesis being corrected (If any). CHAIRMAN OF THESIS HEAD OF FACULTY OF COMMITTEE COMPUTER SCIENCE AND ENGINEERING Assoc. LE HONG TRANG ⅰ VIETNAM NATIONAL UNIVERSITY - HO CHI MINH CITY SOCIALIST REPUBLIC OF VIETNAM HO CHI MINH CITY UNIVERSITY OF TECHNOLOGY Independence – Freedom - Happiness THE TASK SHEET OF MASTER’S THESIS Full name: NHAM LAP HANH Student ID: 1991020 Date of birth: November 23, 1991 Place of birth: HCM City Major: Computer Science Major ID: 8480101 I.
THESIS TITLE: PRIVACY PRESERVING IN SHARING DATA / BẢO VỆ QUYỀN RIÊNG TƯ TRONG DỮ LIỆU CHIA SẺ II. TASKS AND CONTENTS: - Researched data anonymization. - Researched and analyzed the strengths and weaknesses of existing data anonymization solutions. - Based on this, proposed an improved algorithm for data anonymization.
- Implemented and evaluated the improved algorithm. THESIS START DAY: February 01, 2023 IV. THESIS COMPLETION DAY: May 31, 2023 V. TRUONG TUAN ANH Ho Chi Minh City, June 09, 2023 SUPERVISOR CHAIR OF PROGRAM COMMITTEE Dr.
TRUONG TUAN ANH DEAN OF FACULTY OF COMPUTER SCIENCE AND ENGINEERING ⅱ ACKNOWLEDGEMENTS I am deeply grateful to Dr. Truong Tuan Anh for his wholehearted help and guidance during my thesis work. He provided me with valuable insights and feedback, and his support was essential to the completion of my thesis. I would also like to thank Assoc.
Nguyen Tuan Dang and Assoc. Nguyen Van Vu for their useful comments on how to complete my thesis before defending it. Their advice was invaluable, and I am very grateful for their help. Besides, on behalf of all students, I would like to express my gratitude to the teachers of Ho Chi Minh City University of Technology, especially those in the Faculty of Computer Science and Engineering.
Your enthusiastic guidance and support have been invaluable to us, both during our time at the university and in our later career paths. Finally, I would like to thank my family and friends for their help, support, and encouragement throughout this process. They were always there for me, and I could not have done it without them. ⅲ ABSTRACT Currently, the amount of data generated is growing exponentially every year.
This data is collected and used to discover valuable information using data mining techniques. However, this data can contain sensitive information, so it is important to analyze it in a way that protects privacy. Many privacy protection models have been proposed to apply this situation, but k-anonymity is the most widely used because it is practical and easy to implement. Many researchers are also working on ways to protect data privacy while maximizing the data utility.
However, these methods are so general and do not focus on a specific data mining technique. This thesis proposes an algorithm that protects data privacy while maximizing its usefulness for a specific data mining technique. ⅳ TÓM TẮT LUẬN VĂN Hiện nay, lượng dữ liệu được tạo ra đang tăng theo cấp số nhân hàng năm. Dữ liệu này được thu thập và sử dụng để khám phá thông tin giá trị bằng cách sử dụng kỹ thuật khai thác dữ liệu.
Tuy nhiên, dữ liệu này có thể chứa các thông tin nhạy cảm, vì vậy cần phải phân tích nó theo cách bảo vệ quyền riêng tư. Nhiều mô hình bảo vệ quyền riêng tư đã được đề xuất để áp dụng tình huống này, nhưng k-anonymity là được sử dụng rộng rãi nhất vì nó thực tế và dễ thực hiện trong đa số các trường hợp. Nhiều nhà nghiên cứu cũng đang nghiên cứu cách bảo vệ quyền riêng tư của dữ liệu đồng thời tối đa hóa tính hữu ích của dữ liệu. Tuy nhiên, các phương pháp này rất chung chung và không tập trung vào một kỹ thuật khai thác dữ liệu cụ thể.
Luận án này đề xuất một thuật toán bảo vệ quyền riêng tư của dữ liệu đồng thời tối đa hóa tính hữu ích của nó cho một kỹ thuật khai thác dữ liệu cụ thể. ⅴ THE COMMITMENT OF THE THESIS’ AUTHOR: I hereby declare that this is my own research work. The data and results presented in the thesis are honest and have never been published in any previous works. Student NHAM LAP HANH ⅵ Table of contents THE TASK SHEET OF MASTER’S THESIS.
ⅳ THE COMMITMENT OF THE THESIS’ AUTHOR:. Objectives of the topic. Privacy Preserving Data Mining. One-Pass K-Means Algorithm.
K-Anonymity Algorithm Based On Improved Clustering. A clustering-based anonymization approach for privacy-preserving in the healthcare cloud. NonHomogenous Anonymization Approach Using Association Rule Mining For Preserving Privacy. 21 CHAPTER 3: THE PROPOSED ALGORITHM.
The impact of member migration on association rules. The proposed algorithm. TRUONG TUAN ANH STUDENT: NHAM LAP HANH ⅶ Table of Figures Figure 1.1: Overview of Privacy-Preserving Data Publishing. Illustrate the process of Anonymize and mine.1: An example of domain and value generalization hierarchies.2: An example of generating Association Rule using Apriori algorithm.3: An example of attacks on k-anonymity.4: A classification tree example for a category attribute.5: Core process of the Mondrian algorithm.6: The Block Diagram Of Nonhomogenous Anonymization Approach.7: The M3AR algorithm pseudocode.8: Disperse function of M3AR algorithm.1: Results on metric Lost Rules Percentage.2: Results on metric New Rules Percentage.3: Results on metric Different Rules Percentage.4: Results on metric Average Group Size.5: Results on metric Running Time.
TRUONG TUAN ANH STUDENT: NHAM LAP HANH ⅷ Table of Tables Table 2. k-anonymity, types of attribute in dataset .2: Microdata table of criminal records.3: A 3-anonymous version of Table 2.4 : Example of Association Rule Mining.5: Example of 3-anonymity on tuples member migration technique.1: The metrics function description. TRUONG TUAN ANH STUDENT: NHAM LAP HANH 1 CHAPTER 1: INTRODUCTION 1. General introduction Currently, the volume of data generated increases exponentially every year.
This data has brought many benefits to many organizations, such as storing, sharing, and exploiting data using data mining techniques. Through data mining, some valuable information can be discovered from that shared data. Massive data generated from various sources can be processed and analyzed to support decision-making. Among this data, more and more personal information is contained within, it leads to serious privacy concerns.
Therefore, analyzing privacy-preserving data becomes very important. Besides, governments have published data privacy rules, such as HIPAA (Health Insurance Portability and Accountability Act) in the US and the Data Protection Regulation GDPR in Europe in order to control the use and sharing of data to protect user privacy. Any organization that is found to be disclosing user information will be subject to severe fines.1: Overview of Privacy-Preserving Data Publishing. [1] As a result, Privacy Protected Data Publishing (PPDP) [19] has become an area of interest to researchers and practitioners.
A typical scenario of PPDP is depicted in Figure 1.1, showing the different stages of data processing. One key assumption of the PPDP model is that attackers can be found among data recipients SUPERVISOR: Dr. TRUONG TUAN ANH STUDENT: NHAM LAP HANH 2 who intend to discover sensitive information about individuals. Therefore, the goal of PPDP techniques is to modify data by making it less specific in a way that protects the privacy of individuals; while aiming to maintain the usefulness of anonymous data.
The essence of PPDP is to create datasets that have good utility for various tasks since, typically, all potential use scenarios for the data are unknown at the time of publication. For example, under open data initiatives, it is not possible to identify all data recipients. Therefore, any data controller involved in sharing personal data should apply privacy protection mechanisms. Research problem Many PP models have been proposed to adopt this situation.
These models have been developed to consider different attack scenarios against data. For example, assuming an attacker has the basic knowledge to varying degrees could lead to information disclosure. Examples of well-known patterns are k-anonymity [2], l-diversity [3], t-closeness [4] and differential privacy [17]. Among these models, k-anonymity is focused on and used widely by researchers and organizations because this model is realistic and can be easily achieved in most cases.
Furthermore, although it has been shown that k-anonymity is vulnerable to specific attacks, it allows for general-purpose data to be published with reasonable utility. This is in contrast to more robust models (e., differential privacy) which might hamper data quality in order to preserve a stricter guarantee of privacy [18]. These characteristics may make k-anonymity attractive to practitioners, who can adopt it within their organization for an anonymity strategy with a formal guarantee of privacy. However, in reality, the mining process is executed by the difference of organization or individual through a technique called data mining technique (association rules mining for example).
Privacy-Preserving Data Mining (PPDM) [23] methodologies is a branch of PPDM, it is designed to guarantee a certain level of privacy, while maximizing the utility of the data, such that data mining can still be performed on the transformed data efficiently. TRUONG TUAN ANH STUDENT: NHAM LAP HANH 3 Some benefits of the information technologies are only possible through the collection and analysis of (sometimes sensitive) data. However, transforming the data may also reduce its utility, resulting in inaccurate or even infeasible extraction of knowledge through data mining. Privacy-Preserving Data Mining (PPDM) methodologies are designed to guarantee a certain level of privacy, while maximizing the utility of the data, such that data mining can still be performed on the transformed data efficiently.
Illustrate the process of Anonymize and mine A simple example of data sharing is shown in Figure 1.2: data owner of dataset D containing sensitive data, approximate data, and identifiers. Some other data miners require data for their purposes (to analyze and mine the data using association rules techniques to extract valuable information). To protect the privacy of users with sensitive data, data owners must use PP algorithms (e. anonymize k) to anonymize the original data from dataset D to dataset D' for sharing with this data mining tool.
The data miner will then use a mining technique (e. association rules) to mine dataset D' to get valuable information. As a result, the key objective here is data anonymization but still retain all association rules in dataset D (especially those with high support and high confidence) maintained in dataset D' after anonymization, so data mining on dataset D' will give the same result as on D. TRUONG TUAN ANH STUDENT: NHAM LAP HANH 4 1.
Objectives of the topic As mentioned, many studies have been conducted on anonymizing data before releasing it to third parties. Maximizing the utility of data and minimizing privacy risk are two opposing goals. As a result, the goal of this thesis is to investigate the state of algorithms that preserve data privacy while ensuring good data mining results. Finally, this thesis will propose an efficient algorithm for achieving k-anonymity that outperforms current state-of-the-art algorithms.
Additionally, the proposed algorithm preserves significant association rules in k-anonymity data so that the data mining process based on association rule mining can preserve valuable information as in the original data. Research significances In recent years, there has been a growing trend of data collection and information extraction. This has led to an increased risk of sensitive information being leaked.