System and method for data anonymization using hierarchical data clustering and perturbation

• US 9,135,320 B2
• Filed: 06/13/2013
• Issued: 09/15/2015
• Est. Priority Date: 06/13/2012
• Status: Active Grant

• Current Assignee: Electrifai LLC
• Original Assignee: Opera Solutions, LLC.
• Inventors: Goyal, Kanav, Pragya, Chayanika, Garg, Rahul
• Primary Examiner(s): Woo, Isaac M
• Application Number:
  US13/917,263
• Publication Number:
  US 20130339359A1
• Time in Patent Office: 824 Days
• Field of Search: 707600-899
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database

Abstract

A system and method for data anonymization using hierarchical data clustering and perturbation is provided. The system includes a computer system and an anonymization program executed by the computer system. The system converts the data of a high-dimensional dataset to a normalized vector space and applies clustering and perturbation techniques to anonymize the data. The conversion results in each record of the dataset being converted into a normalized vector that can be compared to other vectors. The vectors are divided into disjointed, small-sized clusters using hierarchical clustering processes. Multi-level clustering can be performed using suitable algorithms at different clustering levels. The records within each cluster are then perturbed such that the statistical properties of the clusters remain unchanged.

Claims

1. A system for data anonymization comprising:

a computer system for electronically receiving an original dataset and allowing a user to specify a relative importance of at least one attribute of the dataset; and

an anonymization program executed by the computer system for producing an anonymized dataset from the original dataset, the anonymization program executing;

a vector space mapping sub-process for converting each record of the original dataset to a normalized vector that can be compared to other vectors;

a hierarchical clustering sub-process for dividing the normalized vectors into disjointed k-sized groups of similar records based on a hierarchical clustering technique;

a perturbation sub-process for generating anonymized clusters from individual clusters generated by the hierarchical clustering sub-process; and

an original domain mapping sub-process to combine and remap anonymized clusters back to an original domain of the original dataset.

2. The system of claim 1, wherein the original dataset is a high-dimensional dataset containing record-level data.

3. The system of claim 1, wherein the vector space mapping sub-process executes a categorical to numeric conversion process.

4. The system of claim 1, wherein the vector space mapping sub-process assigns a relative weight to every field of the records.

5. The system of claim 4, wherein the vector space mapping sub-process normalizes the weighted records to produce the normalized vectors, which are compared with the original records to obtain mapping tables for each attribute.

6. The system of claim 1, wherein the vector space mapping sub-process produces a normalized vector mapped dataset.

7. The system of claim 1, wherein the hierarchical clustering sub-process divides the normalized vector mapped dataset into first-level clusters.

8. The system of claim 1, wherein the hierarchical clustering sub-process breaks down each first-level cluster into subsequent M-th level clusters based on attributes.

9. The system of claim 1, wherein the perturbation sub-process randomly assigns attribute values of one record to all records within each cluster.

10. The system of claim 1, wherein the perturbation sub-process shuffles the values of an attribute among the records in each cluster by a random permutation.

11. A method for data anonymization comprising:

electronically receiving an original dataset at a computer system;

allowing a user to specify a relative importance of at least one attribute of the dataset; and

executing by the computer system an anonymization program for producing an anonymized dataset from the original dataset, the anonymization program executing;

a vector space mapping sub-process for converting each record of the original dataset to a normalized vector that can be compared to other vectors;

a hierarchical clustering sub-process for dividing the normalized vectors into disjointed k-sized groups of similar records based on a hierarchical clustering technique;

a perturbation sub-process for generating anonymized clusters from individual clusters generated by the hierarchical clustering sub-process; and

an original domain mapping sub-process to combine and remap anonymized clusters back to an original domain of the original dataset.

12. The method of claim 11, wherein the original dataset is a high-dimensional dataset containing record-level data.

13. The method of claim 11, wherein the vector space mapping sub-process executes a categorical to numeric conversion process.

14. The method of claim 11, wherein the vector space mapping sub-process assigns a relative weight to every field of the records.

15. The method of claim 14, wherein the vector space mapping sub-process normalizes the weighted records to produce the normalized vectors, which are compared with the original records to obtain mapping tables for each attribute.

16. The method of claim 11, wherein the vector space mapping sub-process produces a normalized vector mapped dataset.

17. The method of claim 11, wherein the hierarchical clustering sub-process divides the normalized vector mapped dataset into first-level clusters.

18. The method of claim 11, wherein the hierarchical clustering sub-process breaks down each first-level cluster into subsequent M-th level clusters based on attributes.

19. The method of claim 11, wherein the perturbation sub-process randomly assigns attribute values of one record to all records within each cluster.

20. The method of claim 11, wherein the perturbation sub-process shuffles the values of an attribute among the records in each cluster by a random permutation.

21. A computer-readable medium having computer-readable instructions stored thereon which, when executed by a computer system, cause the computer system to perform the steps of:

electronically receiving an original dataset at a computer system;

allowing a user to specify a relative importance of at least one attribute of the dataset; and

executing by the computer system an anonymization program for producing an anonymized dataset from the original dataset, the anonymization program executing;

a vector space mapping sub-process for converting each record of the original dataset to a normalized vector that can be compared to other vectors;

a hierarchical clustering sub-process for dividing the normalized vectors into disjointed k-sized groups of similar records based on a hierarchical clustering technique;

a perturbation sub-process for generating anonymized clusters from individual clusters generated by the hierarchical clustering sub-process; and

an original domain mapping sub-process to combine and remap anonymized clusters back to an original domain of the original dataset.

22. The computer-readable medium of claim 21, wherein the original dataset is a high-dimensional dataset containing record-level data.

23. The computer-readable medium of claim 21, wherein the vector space mapping sub-process executes a categorical to numeric conversion process.

24. The computer-readable medium of claim 21, wherein the vector space mapping sub-process assigns a relative weight to every field of the records.

25. The computer-readable medium of claim 24, wherein the vector space mapping sub-process normalizes the weighted records to produce the normalized vectors, which are compared with the original records to obtain mapping tables for each attribute.

26. The computer-readable medium of claim 21, wherein the vector space mapping sub-process produces a normalized vector mapped dataset.

27. The computer-readable medium of claim 21, wherein the hierarchical clustering sub-process divides the normalized vector mapped dataset into first-level clusters.

28. The computer-readable medium of claim 21, wherein the hierarchical clustering sub-process breaks down each first-level cluster into subsequent M-th level clusters based on attributes.

29. The computer-readable medium of claim 21, wherein the perturbation sub-process randomly assigns attribute values of one record to all records within each cluster.

30. The computer-readable medium of claim 21, wherein the perturbation sub-process shuffles the values of an attribute among the records in each cluster by a random permutation.