Apparatus and methods for anonymizing a data set

• US 9,202,081 B2
• Filed: 12/17/2012
• Issued: 12/01/2015
• Est. Priority Date: 12/17/2012
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Huang, Vincent, Svensson, Martin
• Primary Examiner(s): LE, THU NGUYET T
• Application Number:
  US13/716,910
• Publication Number:
  US 20140172854A1
• Time in Patent Office: 1,079 Days
• Field of Search: 707/757, 707/737
• US Class Current: 1/1
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/288 Entity relationship models
• CPC Class Codes: G06F 21/6245 Protecting personal data, e.g. for financial or medical purposes
• CPC Class Codes: G06F 21/6254 by anonymising data, e.g. decorrelating personal data from the owner's identification

Abstract

Methods and systems are disclosed for anonymizing a dataset that correlates a set of entities with respective attributes. The method may include: for each entity included in a set of entities, transforming two or more attribute values associated with the entity using received preference information, thereby creating for the entity a set of two or more transformed attribute values; clustering the entities included in the set of entities using said transformed attribute values to form at least a first entity cluster consisting of a first subset of the entities and a second entity cluster consisting of a second subset of the entities, wherein no entity included in the first entity cluster is included in the second entity cluster; anonymizing the first subset of entities; and anonymizing the second subset of entities.

Claims

1. A computerized method for anonymizing a dataset that associates each entity included in a set of entities with a set of two or more attribute values, wherein each said attribute value associated with the entity is associated with a different entity attribute, the method being performed by a computer system and comprising:

receiving preference information that comprises a set of attribute weights, wherein each attribute weight included in the set is associated with one of the entity attributes;

for each entity included in the set of entities, transforming said set of two or more attribute values associated with the entity using the preference information, thereby creating for the entity a set of two or more transformed attribute values, wherein the transforming the set of two or more attribute values comprises;

normalizing the set of two or more attribute values to produce normalized attribute values, and

after normalizing the set of two or more attribute values to produce normalized attribute values, calculating, for each of the normalized attribute values, a transformed attribute value using the normalized attribute value and the attribute weight associated with the entity attribute with which the normalized attribute value is associated;

clustering the entities included in the set of entities using said transfoinied attribute values to form at least a first entity cluster consisting of a first subset of the entities and a second entity cluster consisting of a second subset of the entities, wherein no entity included in the first entity cluster is included in the second entity cluster;

anonymizing the first subset of entities; and

anonymizing the second subset of entities.

2. The method of claim 1, wherein the step of calculating the transformed value comprises multiplying the weight with a value that is equal to the normalized value minus a first value and adding the result of the multiplication with the first value.

3. The method of claim 2, wherein the first value is the mean of a set of values.

4. The method of claim 1, wherein

the step of anonymizing the first subset of entities comprises creating a first new anonymous dataset that:

(1) associates a first common attribute value with each entity included the first subset, the first common attribute value being associated with a first entity attribute and (2) associates a second common attribute value with each entity included the first subset, the second common attribute value being associated with a second entity attribute that is different than the first entity attribute, and

the step of anonymizing the second subset of entities comprises creating a second new anonymous dataset that;

(1) associates a third common attribute value with each entity included the second subset, the third common attribute value being associated with the first entity attribute and (2) associates a fourth common attribute value with each entity included the second subset, the fourth common attribute value being associated with the second entity attribute.

5. The method of claim 4, further comprising publishing the first and second new anonymous datasets.

6. The method of claim 1, wherein the step of clustering the entities comprises:

creating an intermediate dataset using the transformed attribute values and processing the intermediate dataset to create an unsparse dataset that is less sparse than the intermediate dataset; and

identifying entity clusters using the unsparse dataset.

7. The computerized method of claim 1, wherein the transformed value for an i^th entity and j^th attribute (tv_ij) is calculated as tv_ij=mv_j+(nv_ij−

mv_j) x W_j, wherein mv _j is the mean value of a set of values for the j^th attribute, nv_ij is a normalized value for the i^th entity and j^th attribute, and W_j is a weight value for the j^th attribute.

8. The computerized method of claim 1, wherein clustering the entities comprises partitioning the entities in the set of entities into clusters each having entities with similar transformed attribute values.

9. The computerized method of claim 8, wherein clustering the entities comprises:

calculating a centroid of the transformed attribute values of the entities in the set of entities; and

partitioning the set of entities into two clusters that are symmetric to each other with respect to the centroid.

10. The computerized method of claim 1, wherein one of the entity attributes is user income and another one of the entity attributes is age.

11. A database anonymizing apparatus, comprising

a data processing system;

and

a data storage system, wherein

the data storage system stores a dataset that associates each entity included in a set of entities with a set of two or more attribute values, wherein each said attribute value associated with the entity is associated with a different entity attribute,

the data storage system comprises a computer readable medium storing computer readable program code (CRPC), and

the CRPC comprises;

instructions for, for each entity included in the set of entities, transforming said set of two or more attribute values associated with the entity using received preference information, thereby creating for the entity a set of two or more transformed attribute values, wherein the preference information comprises a set of attribute weights, wherein each attribute weight included in the set is associated with one of the entity attributes, and wherein the instructions for transforming the set of two or more attribute values include instructions for;

normalizing the set of two or more attribute values to produce normalized attribute values, and

after normalizing the set of two or more attribute values to produce normalized attribute values, calculating, for each of the normalized attribute values, a transformed attribute value using the normalized attribute value and the attribute weight associated with the entity attribute with which the normalized attribute value is associated;

instructions for clustering the entities included in the set of entities using said transformed attribute values to form at least a first entity cluster consisting of a first subset of the entities and a second entity cluster consisting of a second subset of the entities, wherein no entity included in the first entity cluster is included in the second entity cluster;

instructions for anonymizing the first subset of entities; and

instructions for anonymizing the second subset of entities.

12. The database anonymizing apparatus of claim 11, wherein the instructions for calculating the transformed value comprises instructions for multiplying the weight with a value that is equal to the normalized value minus a first value and instructions for adding the result of the multiplication with the first value.

13. The database anonymizing apparatus of claim 12, wherein the first value is the mean of a set of values.

14. The database anonymizing apparatus of claim 11, wherein

the instructions for anonymizing the first subset of entities comprises instructions for creating a first new anonymous dataset that:

(1) associates a first common attribute value with each entity included the first subset, the first common attribute value being associated with a first entity attribute and (2) associates a second common attribute value with each entity included the first subset, the second common attribute value being associated with a second entity attribute that is different than the first entity attribute, and

the instructions for anonymizing the second subset of entities comprises instructions for creating a second new anonymous dataset that;

(1) associates a third common attribute value with each entity included the second subset, the third common attribute value being associated with the first entity attribute and (2) associates a fourth common attribute value with each entity included the second subset, the fourth common attribute value being associated with the second entity attribute.

15. The database anonymizing apparatus of claim 14, wherein the CRPC further comprises instructions for publishing the first and second new anonymous datasets.

16. The database anonymizing apparatus of claim 11, wherein the instructions for clustering the entities comprises:

instructions for creating an intermediate dataset using the transformed attribute values and processing the intermediate dataset to create an unsparse dataset that is less sparse than the intermediate dataset; and

instructions for identifying entity clusters using the unsparse dataset.