Method and Apparatus for Variable Privacy Preservation in Data Mining

• US 20090319526A1
• Filed: 05/13/2008
• Published: 12/24/2009
• Est. Priority Date: 10/13/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Aggarwal, Charu C., Yu, Philip Shi-Lung
• Granted Patent: US 8,627,070 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 from the data records based on the privacy levels, wherein summary statistics are maintained for each condensed group; and

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

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;

(i) assign different privacy levels to the data records;

(ii) construct condensed groups from the data records based on the privacy levels, wherein summary statistics are maintained for each condensed group; and

(iii) 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 medium containing one or more programs which when executed implement the steps of:

assigning different privacy levels to the data records;

constructing condensed groups from the data records based on the privacy levels, wherein summary statistics are maintained for each condensed group; 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.