Method and apparatus for variable privacy preservation in data mining

• US 8,627,070 B2
• Filed: 05/13/2008
• Issued: 01/07/2014
• Est. Priority Date: 10/13/2005
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Aggarwal, Charu C., Yu, Philip Shi-Lung
• Primary Examiner(s): Abrishamkar, Kaveh
• Application Number:
  US12/119,766
• Publication Number:
  US 20090319526A1
• Time in Patent Office: 2,065 Days
• Field of Search: None
• US Class Current: 713/166
• CPC Class Codes: G06F 21/604 Tools and structures for managing or administering access control systems
• 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

Improved privacy preservation techniques are disclosed for use in accordance with data mining. By way of example, a technique for preserving privacy of data records for use in a data mining application comprises the following steps/operations. Different privacy levels are assigned to the data records. Condensed groups are constructed from the data records based on the privacy levels, wherein summary statistics are maintained for each condensed group. Pseudo-data is generated from the summary statistics, wherein the pseudo-data is available for use in the data mining application. Principles of the invention are capable of handling both static and dynamic data sets.

Claims

1. A method for preserving privacy of data records for use in a data mining application, comprising the steps of:

assigning different privacy levels to the data records;

constructing condensed groups of data records from the data records based on the privacy levels, wherein a data record having a first privacy level is condensed with a data record having a second privacy level different than the first privacy level;

maintaining summary statistics for each condensed group of data records, wherein the summary statistics for a given condensed group of data records includes information regarding a sum of privacy levels of data records in the given condensed group of data records; and

generating pseudo-data from the summary statistics, wherein the pseudo-data is available for use in the data mining application,

wherein the assigning, constructing, maintaining and generating steps are performed by a data processing system.

2. The method of claim 1, wherein maintaining summary statistics further comprises:

an iterative step of segmentation wherein data records with the same privacy level are included in one group;

an iterative step of cannibalization wherein data records from one group are redistributed to other groups; and

a step of attrition wherein data records from one group are reassigned to a closer group.

3. The method of claim 1, wherein data records of a given privacy level are processed in increasing order of privacy.

4. The method of claim 1, wherein data records of a given privacy level are processed in decreasing order of privacy.

5. The method of claim 2, wherein the cannibalization step redistributes records of a given privacy level to groups with higher privacy levels.

6. The method of claim 5, wherein the cannibalization step is performed when the reassignment of all data records within the group results in a lower squared error.

7. The method of claim 2, wherein the attrition step reassigns excess records from a given group to other groups.

8. The method of claim 1, wherein the data records are static.

9. The method of claim 1, wherein the data records are dynamic.

10. Apparatus for preserving privacy of data records for use in a data mining application, comprising:

a memory; and

a processor coupled to the memory and operative to;

assign different privacy levels to the data records;

construct condensed groups of data records from the data records based on the privacy levels, wherein a data record having a first privacy level is condensed with a data record having a second privacy level different than the first privacy level;

maintain summary statistics for each condensed group of data records, wherein the summary statistics for a given condensed group of data records includes information regarding a sum of privacy levels of data records in the given condensed group of data records; and

generate pseudo-data from the summary statistics, wherein the pseudo-data is available for use in the data mining application.

11. The apparatus of claim 10, wherein maintaining summary statistics further comprises:

an iterative operation of segmentation wherein data records with the same privacy level are included in one group;

an iterative operation of cannibalization wherein data records from one group are redistributed to other groups; and

an operation of attrition wherein data records from one group are reassigned to a closer group.

12. The apparatus of claim 10, wherein data records of a given privacy level are processed in increasing order of privacy.

13. The apparatus of claim 10, wherein data records of a given privacy level are processed in decreasing order of privacy.

14. The apparatus of claim 11, wherein the cannibalization operation redistributes records of a given privacy level to groups with higher privacy levels.

15. The apparatus of claim 14, wherein the cannibalization operation is performed when the reassignment of all data records within the group results in a lower squared error.

16. The apparatus of claim 11, wherein the attrition operation reassigns excess records from a given group to other groups.

17. The apparatus of claim 10, wherein the data records are static.

18. The apparatus of claim 10, wherein the data records are dynamic.

19. An article of manufacture for use in preserving privacy of data records for use in a data mining application, the article comprising a machine readable storage device containing one or more programs which when executed implement the steps of:

assigning different privacy levels to the data records;

constructing condensed groups of data records from the data records based on the privacy levels, wherein a data record having a first privacy level is condensed with a data record having a second privacy level different than the first privacy level;

maintaining summary statistics for each condensed group of data records, wherein the summary statistics for a given condensed group of data records includes information regarding a sum of privacy levels of data records in the given condensed group of data records; and

generating pseudo-data from the summary statistics, wherein the pseudo-data is available for use in the data mining application.

20. The article of claim 19, wherein maintaining summary statistics further comprises:

an iterative step of segmentation wherein data records with the same privacy level are included in one group;

an iterative step of cannibalization wherein data records from one group are redistributed to other groups; and

a step of attrition wherein data records from one group are reassigned to a closer group.