Method and apparatus for privacy preserving data mining by restricting attribute choice

• US 7,475,085 B2
• Filed: 04/04/2006
• Issued: 01/06/2009
• Est. Priority Date: 04/04/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Aggarwal, Charu C., Halim, Nagui
• Primary Examiner(s): NGUYEN, CAM LINH T
• Application Number:
  US11/397,297
• Publication Number:
  US 20070233711A1
• Time in Patent Office: 1,008 Days
• Field of Search: 707/1, 707/2, 707/9, 707100-103 R
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: G06F 21/6254 by anonymising data, e.g. decorrelating personal data from the owner's identification
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99939 Privileged access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

Improved techniques for privacy preserving data mining of multidimensional data records are disclosed. For example, a technique for generating at least one output data set from at least one input data set for use in association with a data mining process comprises the following steps/operations. At least one relevant attribute of the at least one input data set is selected through determination of at least one relevance coefficient. The at least one output data set is generated from the at least one input data set, wherein the at least one output data set comprises the at least one relevant attribute of the at least one input data set, as determined by use of the at least one relevance coefficient.

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, the input data set comprising at least one entry including each of a plurality of attributes, comprising the steps of:

determining at least one relevance coefficient for at least a subset of the plurality of attributes;

selecting at least one relevant attribute of the at least one input data set based at least in part on the at least one relevance coefficient; and

generating the at least one output data set from the at least one input data set;

wherein the at least one output data set comprises at least one entry not including at least one of the plurality of attributes; and

wherein the at least one entry of the output data set has the at least one relevant attribute of the at least one input data set;

wherein the at least one relevance coefficient is computed using a quantitative measure of an effect on the data mining process of a deletion of at least the given attribute from each entry of the input data set.

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

3. The method of claim 2, wherein the anonymization generates synthetic pseudo-data.

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

5. The method of claim 1, wherein the at least one input data set is multidimensional.

6. The method of claim 1, wherein a global feature analysis is used for computing the at least one relevance coefficient.

7. The method of claim 1, wherein a local feature analysis is used for computing the at least one relevance coefficient.

8. The method of claim 1, wherein the at least one relevance coefficient is used in at least one distance function during a condensation process.

9. The method of claim 8, wherein the at least one distance function is more strongly weighted by the at least one relevant attribute.

10. The method of claim 1, wherein the at least one relevant attribute is pre-selected for privacy preservation purposes.

11. 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 input data set comprising at least one entry including each of a plurality of attributes, the apparatus comprising:

a memory; and

at least one processor coupled to the memory and operative to;

(i) determine at least one relevance coefficient for at least a subset of the plurality of attributes;

(ii) select at least one relevant attribute of the at least one input data set based at least in part on the at least one relevance coefficient; and

(iii) generate the at least one output data set from the at least one input data set;

wherein the at least one output data set comprises at least one entry not including at least one of the plurality of attributes; and

wherein the at least one entry of the output data set includes the at least one relevant attribute of the at least one input data set;

wherein the at least one relevance coefficient is computed using a quantitative measure of an effect on the data mining process of a deletion of at least the given attribute from each entry of the input data set.

12. The apparatus of claim 11, wherein the output data set is anonymized.

13. The apparatus of claim 12, wherein the anonymization generates synthetic pseudo-data.

14. The apparatus of claim 11, wherein the data mining process is a privacy preserving data mining process.

15. The apparatus of claim 11, wherein the at least one input data set is multidimensional.

16. The apparatus of claim 11, wherein a global feature analysis is used for computing the at least one relevance coefficient.

17. The apparatus of claim 11, wherein a local feature analysis is used for computing the at least one relevance coefficient.

18. The apparatus of claim 11, wherein the at least one relevance coefficient is used in at least one distance function during a condensation process.

19. The apparatus of claim 18, wherein the at least one distance function is more strongly weighted by the at least one relevant attribute.

20. The apparatus of claim 11, wherein the the at least one relevant attribute is pre-selected for privacy preservation purposes.

21. 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, the input data set comprising at least one entry including each of a plurality of attributes, comprising a machine readable medium containing one or more programs which when executed implement the steps of:

determining at least one relevance coefficient for at least a subset of the plurality of attributes;

selecting at least one relevant attribute of the at least one input data set based at least in part on the at least one relevance coefficient; and

generating the at least one output data set from the at least one input data set;

wherein the at least one output data set comprises at least one entry not including at least one of the plurality of attributes; and

wherein the at least one entry of the output data set includes the at least one relevant attribute of the at least one input data set;

wherein the at least one relevance coefficient is computed using a quantitative measure of an effect on the data mining process of a deletion of at least the given attribute from each entry of the input data set.