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

• US 7,302,420 B2
• Filed: 08/14/2003
• Issued: 11/27/2007
• 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
• Primary Examiner(s): Alam; Hosain
• Assistant Examiner(s): Raab; Christopher J
• Application Number:
  US10/641,935
• Publication Number:
  US 20050049991A1
• Time in Patent Office: 1,566 Days
• Field of Search: None
• US Class Current: 707/688
• 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 multidimensional static input data set for use in association with a data mining process, comprising the steps of:

generating data statistics from the at least one multidimensional static input data set in an iterative manner in accordance with one or more records from the at least one static input data set included in at least one condensed data group, and further comprising 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, generating first order statistics and second order statistics for the at least one condensed data group, 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;

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

storing the at least one output data set in a storage device for use by a user.

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 one or more correlations are inherent correlations between different dimensions of the multidimensional input data set.

5. 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.

6. Apparatus for generating at least one output data set from at least one multidimensional static 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 multidimensional static input data set in an iterative manner in accordance with one or more records from the at least one static input data set included in at least one condensed data group, and further comprising 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, generating first order statistics and second order statistics for the at least one condensed data group, 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;

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

(iii) store the at least one output data set in a storage device for use by a user.

7. The apparatus of claim 6, wherein the output data set is anonymized.

8. The apparatus of claim 6, wherein the data mining process is a privacy preserving data mining process.

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

10. The apparatus of claim 6, 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.

11. A method for making a computer implemented process to enable generation of at least one output data set from at least one multidimensional static input data set for use in association with a data mining process, the method comprising the steps of:

instantiating first computer instructions onto a computer readable medium, the first computer instructions configured to generate data statistics from the at least one multidimensional static input data set in an iterative manner in accordance with one or more records from the at least one static input data set included in at least one condensed data group;

instantiating second computer instructions onto a computer readable medium, the second computer instructions configured to generate the at least one output data set from the data statistics, wherein the output data set differs from the static input data set but maintains one or more correlations from within the static input data set, and further comprising the stens 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, generating first order statistics and second order statistics for the at least one condensed data group, 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; and

instantiating third computer instructions onto a computer readable medium, the third computer instructions configured to store the at least one output data set on a storage device for use by a user.

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

generating data statistics from the at least one multidimensional dynamic input data set in an iterative manner in accordance with one or more records from the at least one dynamic input data set included in at least one condensed data group, and further comprising 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,

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

storing the at least one output data set in a storage device for use by a user.

13. The method of claim 12, 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.

14. Apparatus for generating at least one output data set from at least one multidimensional dynamic 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 multidimensional dynamic input data set in an iterative manner in accordance with one or more records from the at least one dynamic input data set included in at least one condensed data group, and further comprising 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;

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

(iii) store the at least one output data set in a storage device for use by a user.

15. The apparatus of claim 14, 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.