Method and apparatus for generating test data sets in accordance with user feedback

• US 7,085,981 B2
• Filed: 06/09/2003
• Issued: 08/01/2006
• Est. Priority Date: 06/09/2003
• Status: Expired due to Fees

• Current Assignee: LinkedIn Corporation (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Aggarwal, Charu C.
• Primary Examiner(s): Lamarre, Guy
• Assistant Examiner(s): Trimmings, John P.
• Application Number:
  US10/457,333
• Publication Number:
  US 20040250188A1
• Time in Patent Office: 1,149 Days
• Field of Search: None
• US Class Current: 714/738
• CPC Class Codes: G01R 31/318307 computer-aided, e.g. automatic test program generator [ATPG], program translations, test program debugging
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

Techniques for processing data sets and, more particularly, constructing a synthetic data set (test data set) from real data sets (input data sets) in accordance with user feedback. The technique mimics real data sets effectively to generate the corresponding synthetic ones. Multiple real data sets may be used to create a test data set which combines the characteristics of these multiple data sets. Users of the technique have the ability to modify the characteristics of the data sets to create a new data set which has features that a user may desire. For example, a user may change the shape or size of, or distort the different patterns in the data to create a new data set. A user may also choose to inject noise into the system.

Claims

1. A method of generating at least one test data set from at least one input data set, the test data set being capable of determining quality of results from a data mining technique performed in a computer, the method comprising the steps of:

obtaining the at least one input data set; and

constructing the at least one test data set from the at least one input data set based on characteristics associated with the at least one input data set and user input resulting in at least a changing of a shape of one or more clustered regions in data of the at least one input data set.

2. The method of claim 1, wherein the at least one input data set is from a data mining application.

3. The method of claim 1, wherein the user input comprises injection of noise in association with the at least one input data set.

4. The method of claim 1, wherein the user input results in a reduction of size of clustered regions in data of the at least one input data set.

5. The method of claim 1, wherein the user input results in an expansion of size of clustered regions in data of the at least one input data set.

6. The method of claim 1, wherein the input data set obtaining step comprises obtaining multiple input data sets such that the test data set is constructed by combining characteristics of the multiple input data sets.

7. The method of claim 6, wherein combining characteristics of the multiple input data sets comprises:

specifying a weight for each of the characteristics;

attributing the weight to the characteristics; and

summing weighted characteristics.

8. The method of claim 1, wherein the step of constructing the at least one test data set further comprises the steps of:

separating the at least one input data set into a number of grid squares;

estimating a function of density at a center of each grid square;

sampling the grid squares in proportion to their density; and

inserting a data point uniformly at random within each grid square.

9. The method of claim 8, wherein, in the step of sampling the grid squares in proportion to their density, the density is modified by adding noise whose parameters are determined by the user.

10. The method of claim 8, wherein, in the step of sampling the grid squares in proportion to their density, the density is modified by applying a distortion function whose definition and parameters are determined by the user.

11. The method of claim 10, wherein the distortion function changes the size and shape of clustered regions in the test data set.

12. Apparatus for generating at least one test data set from at least one input data set, the test data set being capable of determining quality of results from a data mining technique performed in a computer, the apparatus comprising:

a memory; and

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

(i) obtain at least one input data set; and

(ii) construct at least one test data set from the at least one input data set based on characteristics associated with the at least one input data set and user input resulting in at least a changing of a shape of one or more clustered regions in data of the at least one input data set.

13. The apparatus of claim 12, wherein the at least one input data set is from a data mining application.

14. The apparatus of claim 12, wherein the user input comprises injection of noise in association with the at least one input data set.

15. The apparatus of claim 12, wherein the user input results in a reduction of size of clustered regions in data of the at least one input data set.

16. The apparatus of claim 12, wherein the user input results in an expansion of size of clustered regions in data of the at least one input data set.

17. The apparatus of claim 12, wherein the input data set obtaining operation comprises obtaining multiple input data sets such that the test data set is constructed by combining characteristics of the multiple input data sets.

18. The apparatus of claim 17, wherein combining characteristics of the multiple input data sets comprises:

specifying a weight for each of the characteristics;

attributing the weight to the characteristics; and

summing weighted characteristics.

19. The apparatus of claim 12, wherein the constructing the at least one test data set operation further comprises:

separating the at least one input data set into a number of grid squares;

estimating a function of density at a center of each grid square;

sampling the grid squares in proportion to their density; and

inserting a data point uniformly at random within each grid square.

20. The apparatus of claim 19, wherein, in the sampling the grid squares in proportion to their density operation, the density is modified by adding noise whose parameters are determined by the user.

21. The apparatus of claim 19, wherein, in the sampling the grid squares in proportion to their density operation, the density is modified by applying a distortion function whose definition and parameters are determined by the user.

22. The apparatus of claim 21, wherein the distortion function changes the size and shape of clustered regions in the test data set.

23. An article of manufacture for generating at least one test data set from at least one input data set, the test data set being capable of determining quality of results from a data mining technique performed in a computer, the article of manufacture comprising a machine readable medium containing one or more programs which when executed implement the steps of:

obtaining the at least one input data set; and

constructing the at least one test data set from the at least one input data set based on characteristics associated with the at least one input data set and user input resulting in at least a changing of a shape of one or more clustered regions in data of the at least one input data set.