Data de-identification with minimal data distortion

1. A method, in a data processing system comprising at least one processor and at least one memory, the at least one memory comprising instructions executed by the at least one processor to cause the at least one processor to transform a dataset, the method comprising:

identifying discoverable patterns of a dataset and assigning a monetary value to each identified pattern;

determining privacy constraints to privatize the dataset, and pattern constraints to preserve a first set of the patterns and conceal a second set of the patterns;

generating a model based on the privacy constraints, the pattern constraints, and optimization criteria, wherein the model satisfies all of the privacy constraints and a subset of the pattern constraints that do not conflict with the privacy constraints, with minimal loss of data;

applying the model to the dataset to determine changes needed to the dataset to satisfy all of the privacy constraints and the subset of the pattern constraints, wherein the model fails to satisfy at least one of the pattern constraints;

modifying the dataset in accordance with the determined changes, wherein the optimization criteria minimize a distance between the dataset and the modified dataset and the determined changes satisfy the optimization criteria; and

determining discoverable patterns of the modified dataset from the subset of privacy constraints, and determining a monetary value of the modified dataset based on the monetary values of the discoverable patterns of the modified dataset.

2. The method of claim 1 , wherein the generating a model includes:

formulating a constraint satisfaction problem that includes the privacy constraints, the pattern constraints, and the optimization criteria configured to minimize information loss.

3. The method of claim 2 , wherein the generating a model further includes:

selectively replacing items in the dataset with variables of the constraint satisfaction problem, wherein each variable captures a presence or absence of a corresponding item in the modified dataset.

4. The method of claim 2 , wherein the generating a model further includes:

identifying a conflict in the model between the privacy constraints and the pattern constraints; and

omitting one or more of the pattern constraints from the constraint satisfaction problem until there is no conflict between the privacy constraints and remaining ones of the pattern constraints.

5. The method of claim 4 , wherein the pattern constraints include pattern preservation constraints to preserve the first set of patterns and pattern hiding constraints to conceal the second set of patterns, and wherein the omitting includes:

omitting one or more of the pattern preservation constraints prior to omitting one or more of the pattern hiding constraints.

6. The method of claim 4 , wherein the omitting includes:

selecting the one or more of the pattern constraints to omit from the constraint satisfaction problem based on the monetary values assigned to the corresponding patterns.

7. The method of claim 1 , wherein the assigning monetary values to the patterns includes:

characterizing the patterns with respect to interestingness; and

assigning the monetary values to the patterns based on the respective characterizations of interestingness.

8. The method of claim 1 , wherein the dataset includes medical data fields of patients, and wherein the patterns include patterns of the medical data fields, or personal financial data of a natural person.

9. A computer program product comprising one or more computer readable storage media collectively encoded with a computer program that includes instructions to cause a processor to:

identify discoverable patterns of a dataset and assign a monetary value to each identified pattern;

determine privacy constraints to privatize the dataset, and pattern constraints to preserve a first set of the patterns and conceal a second set of the patterns;

generate a model based on the privacy constraints, the pattern constraints, and optimization criteria, wherein the model satisfies all of the privacy constraints and a subset of the pattern constraints that do not conflict with the privacy constraints, with minimal loss of data;

apply the model to the dataset to determine changes needed to the dataset to satisfy all of the privacy constraints and the subset of the pattern constraints, wherein the model fails to satisfy at least one of the pattern constraints;

modify the dataset in accordance with the determined changes, wherein the optimization criteria minimize a distance between the dataset and the modified dataset and the determined changes satisfy the optimization criteria; and

determine discoverable patterns of the modified dataset from the subset of privacy constraints and determine a monetary value of the modified dataset based on the monetary values of the discoverable patterns of the modified dataset.

10. The computer program product of claim 9 , wherein the computer program further includes instructions to cause the processor to:

formulate a constraint satisfaction problem that includes the privacy constraints, the pattern constraints, and the optimization criteria configured to minimize information loss.

11. The computer program product of claim 10 , wherein the computer program further includes instructions to cause the processor to:

selectively replace items in the dataset with variables of the constraint satisfaction problem, wherein each variable captures a presence or absence of a corresponding item in the modified dataset.

12. The computer program product of claim 10 , wherein the computer program further includes instructions to cause the processor to:

identify a conflict in the model between the privacy constraints and the pattern constraints; and

omit one or more of the pattern constraints from the constraint satisfaction problem until there is no conflict between the privacy constraints and remaining ones of the pattern constraints.

13. The computer program product of claim 12 , wherein the pattern constraints include pattern preservation constraints to preserve the first set of patterns and pattern hiding constraints to conceal the second set of patterns, and wherein the computer program further includes instructions to cause the processor to:

omit one or more of the pattern preservation constraints prior to omitting one or more of the pattern hiding constraints.

14. The computer program product of claim 12 , wherein the computer program further includes instructions to cause the processor to:

select the one or more of the pattern constraints to omit from the constraint satisfaction problem based on the monetary values assigned to the corresponding patterns.

15. An apparatus, comprising, a processor and memory configured to:

identify discoverable patterns of a dataset and assign a monetary value to each identified pattern;

determine privacy constraints to privatize the dataset, and pattern constraints to preserve a first set of the patterns and conceal a second set of the patterns;

generate a model based on the privacy constraints, the pattern constraints, and optimization criteria, wherein the model satisfies all of the privacy constraints and a subset of the pattern constraints that do not conflict with the privacy constraints, with minimal loss of data;

apply the model to the dataset to determine changes needed to the dataset to satisfy all of the privacy constraints and the subset of the pattern constraints, wherein the model fails to satisfy at least one of the pattern constraints;

modify the dataset in accordance with the determined changes, wherein the optimization criteria minimize a distance between the dataset and the modified dataset and the determined changes satisfy the optimization criteria; and

determine discoverable patterns of the modified dataset from the subset of privacy constraints and determine a monetary value of the modified dataset based on the monetary values of the discoverable patterns of the modified dataset.

16. The apparatus of claim 15 , wherein the processor and memory are further configured to:

formulate a constraint satisfaction problem that includes the privacy constraints, the pattern constraints, and the optimization criteria configured to minimize information loss.

17. The apparatus of claim 16 , wherein the processor and memory are further configured to:

selectively replace items in the dataset with variables of the constraint satisfaction problem, wherein each variable captures a presence or absence of a corresponding item in the modified dataset.

18. The apparatus of claim 16 , wherein the processor and memory are further configured to:

identify a conflict in the model between the privacy constraints and the pattern constraints; and

omit one or more of the pattern constraints from the constraint satisfaction problem until there is no conflict between the privacy constraints and remaining ones of the pattern constraints.

19. The apparatus of claim 18 , wherein the pattern constraints include pattern preservation constraints to preserve the first set of patterns and pattern hiding constraints to conceal the second set of patterns, and wherein the processor and memory are further configured to:

omit one or more of the pattern preservation constraints prior to omitting one or more of the pattern hiding constraints.

20. The apparatus of claim 18 , wherein the processor and memory are further configured to:

select the one or more of the pattern constraints to omit from the constraint satisfaction problem based on the monetary values assigned to the corresponding patterns.