Methods and apparatus for privacy preserving data mining using statistical condensing approach

• US 20050049991A1
• Filed: 08/14/2003
• Published: 03/03/2005
• Est. Priority Date: 08/14/2003
• 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 7,302,420 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: Y10S 707/957 Multidimensional
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

Methods and apparatus for generating at least one output data set from at least one input data set for use in association with a data mining process are provided. First, data statistics are constructed from the at least one input data set. Then, an output data set is generated from the data statistics. The output data set differs from the input data set but maintains one or more correlations from within the input data set. The correlations may be the inherent correlations between different dimensions of a multidimensional input data set. A significant amount of information from the input data set may be hidden so that the privacy level of the data mining process may be increased.

Claims

1. A method of generating at least one output data set from at least one input data set for use in association with a data mining process, comprising the steps of:

generating data statistics from the at least one input data set; and

generating the at least one output data set from the data statistics, wherein the output data set differs from the input data set but maintains one or more correlations from within the input data set.

2. The method of claim 1, wherein the output data set is anonymized.

3. The method of claim 1, wherein the data mining process is a privacy preserving data mining process.

4. The method of claim 1, wherein the input data set is multidimensional.

5. The method of claim 4, wherein the one or more correlations are inherent correlations between different dimensions of the multidimensional input data set.

6. The method of claim 1, wherein the input data set is a static data set.

7. The method of claim 6, wherein the step of generating data statistics comprises the steps of:

forming at least one condensed data group having a specific number of records from the static data set closest to a given record of the static data set; and

generating first order statistics and second order statistics for the at least one condensed data group.

8. The method of claim 7, wherein the step of generating data statistics is an iterative process comprising the steps of:

deleting records from the static data set that are included in the at least one condensed data group;

determining if records remain in the static data set; and

forming additional condensed data groups if records remain in the static data set.

9. The method of claim 1, wherein the input data set is a dynamic data set.

10. The method of claim 9, wherein the step of generating data statistics comprises the steps of:

receiving a record from the dynamic data set;

finding a closest condensed data group to add the record to or creating a condensed group having the record if the record is the first received from the dynamic data set;

generating first order statistics and second order statistics for the closest condensed data group;

determining if the number of records in the closest condensed data group is larger than an indistinguishability factor; and

splitting the closest condensed data group into two groups and updating the first order statistics and second order statistics if the number of records in the closest condensed data group is larger than the indistinguishability factor.

11. The method of claim 10, wherein the step of generating data statistics is an iterative process comprising the steps of:

determining whether records remain in the dynamic data set; and

receiving a next record from the dynamic data set if records remain in the dynamic data set.

12. The method of claim 1, wherein the step of generating the at least one output data set comprises the steps of:

determining eigenvectors and eigenvalues of the data statistics; and

generating anonymized data in the output data set from the data statistics using the eigenvectors and eigenvalues.

13. Apparatus for generating at least one output data set from at least one input data set for use in association with a data mining process, the apparatus comprising:

a memory; and

at least one processor coupled to the memory operative to;

(i) generate data statistics from the at least one input data set; and

(ii) generate the at least one output data set from the data statistics, wherein the output data set differs from the input data set but maintains one or more correlations from within the input data set.

14. The apparatus of claim 13, wherein the output data set is anonymized.

15. The apparatus of claim 13, wherein the data mining process is a privacy preserving data mining process.

16. The apparatus of claim 13, wherein the input data set is multidimensional.

17. The apparatus of claim 16, wherein the one or more correlations are inherent correlations between different dimensions of the multidimensional input data set.

18. The apparatus of claim 13, wherein the input data set is a static data set.

19. The apparatus of claim 18, wherein the operation of generating data statistics comprises the steps of:

forming at least one condensed data group having a specific number of records from the static data set closest to a given record of the static data set; and

generating first order statistics and second order statistics for the at least one condensed data group.

20. The apparatus of claim 19, wherein the operation of generating data statistics is an iterative process comprising the steps of:

deleting records from the static data set that are included in the at least one condensed data group;

determining if records remain in the static data set; and

forming additional condensed data groups if records remain in the static data set.

21. The apparatus of claim 13, wherein the input data set is a dynamic data set.

22. The apparatus of claim 21, wherein the operation of generating data statistics comprises the steps of:

receiving a record from the dynamic data set;

finding a closest condensed data group to add the record to or creating a condensed group having the record if the record is the first received from the dynamic data set;

generating first order statistics and second order statistics for the closest condensed data group;

determining if the number of records in the closest condensed data group is larger than an indistinguishability factor; and

splitting the closest condensed data group into two groups and updating the first order statistics and second order statistics if the number of records in the closest condensed data group is larger than the indistinguishability factor.

23. The apparatus of claim 22, wherein the operation of generating data statistics is an iterative process comprising the steps of:

determining whether records remain in the dynamic data set; and

receiving a next record from the dynamic data set if records remain in the dynamic data set.

24. The apparatus of claim 13, wherein the operation of generating the at least one output data set comprises the steps of:

determining eigenvectors and eigenvalues of the data statistics; and

generating anonymized data in the output data set from the data statistics using the eigenvectors and eigenvalues.

25. An article of manufacture for generating at least one output data set from at least one input data set for use in association with a data mining process, comprising a machine readable medium containing one or more programs which when executed implement the steps of:

generating data statistics from the at least one input data set; and

generating the at least one output data set from the data statistics, wherein the output data set differs from the input data set but maintains one or more correlations from within the input data set.