Parallel object-oriented data mining system

• US 6,675,164 B2
• Filed: 06/08/2001
• Issued: 01/06/2004
• Est. Priority Date: 06/08/2001
• Status: Expired due to Fees

• Current Assignee: Lawrence Livermore National Security LLC (Government of the United States of America)
• Original Assignee: Regents of the University of California (University of California)
• Inventors: Cantu-Paz, Erick, Kamath, Chandrika
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US09/877,685
• Publication Number:
  US 20020194159A1
• Time in Patent Office: 942 Days
• Field of Search: 707/6, 706/45
• 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 18/24323 Tree-organised classifiers
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A data mining system uncovers patterns, associations, anomalies and other statistically significant structures in data. Data files are read and displayed. Objects in the data files are identified. Relevant features for the objects are extracted. Patterns among the objects are recognized based upon the features. Data from the Faint Images of the Radio Sky at Twenty Centimeters (FIRST) sky survey was used to search for bent doubles. This test was conducted on data from the Very Large Array in New Mexico which seeks to locate a special type of quasar (radio-emitting stellar object) called bent doubles. The FIRST survey has generated more than 32,000 images of the sky to date. Each image is 7.1 megabytes, yielding more than 100 gigabytes of image data in the entire data set.

Claims

1. A data mining system, comprising:

a parallel reading and displaying module for reading and displaying data in different formats, said data containing data items with features;

a parallel object identifying module for identifying said data items;

a parallel feature extracting module for extracting at least one of said features for each of said data items;

a parallel pattern recognition algorithms module for pattern recognition;

a storage module to store at least one of said features for each of said data items as it is extracted, and

a parallel linking module for linking said parallel object identifying module, said parallel feature extracting module, said parallel pattern recognition algorithms module, and said storage module.

2. The data mining system of claim 1, including a parallel dimension reduction module for dimension reduction which reduces the number of said features for each of said data items.

3. The data mining system of claim 1, wherein said storage module is a database.

4. The data mining system of claim 1, including a parallel sampling module for sampling said data to reduce the number of said data items.

5. The data mining system of claim 1, including a parallel multiresolution analysis module for performing a reversible transformation of said data into a coarser resolution.

6. The data mining system of claim 1, including a parallel noise removing module for removing noise from said data.

7. The data mining system of claim 1, including a parallel data fusion module for data fusion.

8. A parallel object-oriented data mining system, comprising:

a parallel object-oriented reading and displaying module for reading and displaying data in different formats, said data containing data items with features;

a parallel object-oriented identifying module for identifying said data items;

a parallel object-oriented feature extracting module for extracting at least one of said features for each of said data items;

a parallel object-oriented pattern recognition algorithms module for pattern recognition;

a storage module to store at least one of said features for each of said data items as it is extracted, and

a parallel object-oriented linking module for linking said parallel object-oriented identifying module, said parallel object-oriented extracting module, said parallel object-oriented pattern recognition algorithms module, and said storage module.

9. The data mining system of claim 8, including a parallel object-oriented dimension reduction module for dimension reduction which reduces the number of said features for each of said data items.

10. The data mining system of claim 8, including a parallel object-oriented sampling module for sampling said data to reduce the number of said data items.

11. The data mining system of claim 8, including a parallel object-oriented multiresolution analysis module for performing a reversible transformation of said data into a coarser resolution.

12. The data mining system of claim 8, including a parallel object-oriented removing noise module for removing noise from said data.

13. The data mining system of claim 8, including a parallel object-oriented data fusion module for data fusion.

14. The data mining system of claim 13 including wherein said parallel object-oriented linking module for linking said parallel object-oriented identifying module, said parallel object-oriented extracting module, said parallel object-oriented pattern recognition algorithms module, and said storage module, also links said database and utilizes a scripting language.

15. The data mining system of claim 8 wherein said storage module is a database.

16. A parallel object-oriented data mining system, comprising:

parallel object-oriented reading and displaying means for reading and displaying data in different formats, said data containing data items with features;

parallel object-oriented sampling means for sampling said data to reduce the number of data items;

parallel object-oriented multiresolution analysis means for performing a reversible transformation of said data into a coarser resolution;

parallel object-oriented noise removing means for removing noise from said data;

parallel object-oriented data fusion means for data fusion;

parallel object-oriented object identifying means for identifying data items;

parallel object-oriented feature extracting means for extracting at least one of said features for each of the said data items;

parallel object-oriented dimension reduction means for dimension reduction which reduces the number of features for a data item;

parallel object-oriented pattern recognition algorithms means for pattern recognition; and

database means for storing features for each data item as it is extracted, wherein, the appropriate means are linked as necessary using a scripting language.

17. A data mining system for science, engineering, business and other applications, comprising:

a parallel object-oriented reading, writing, and displaying module for reading, writing, and displaying engineering, business and other data in different formats, said data containing data items from different sensors at different times under different conditions;

a parallel object-oriented sampling module for sampling said data and reducing the number of said data items;

a parallel object-oriented multiresolution analysis module for multiresolution analysis to perform a reversible transformation of said data into a coarser resolution using multi-resolution techniques;

a parallel object-oriented noise removal module for removing noise from said data;

a parallel object-oriented data fusion module for data fusion if said data is obtained from different sensors at different times under different conditions at different resolutions;

a parallel object-oriented object identifying module for identifying said data items in the fused, denoised, sampled, multi-resolution data;

a parallel object-oriented feature extracting module for extracting at least one of said features for each of said items from the said fused, denoised, sampled, multi-resolution data;

a parallel object-oriented dimension reduction module for dimension reduction which reduces the number of features for each of said data items;

a parallel object-oriented pattern recognition module using pattern recognition algorithms selected from the group consisting of decision trees, neural networks, k-nearest neighbor, k-means, or evolutionary algorithms; and

a database to store said at least one of said features for each of said data items as it is extracted, after the number of features have been reduced, and as the data set grows in size, enabling easy access to subsets of data;

wherein, all the appropriate modules are linked as necessary using a scripting language such as Python to provide a solution for data mining.

18. The data mining system of claim 17 wherein said parallel object-oriented multiresolution analysis module for multiresolution analysis to perform a reversible transformation of said data into a coarser resolution uses resolution techniques such as wavelets.

19. The data mining system of claim 17 wherein said parallel object-oriented noise removal module for removing noise from said data uses techniques selected from the group consisting of wavelet-based denoising, spatial filters or techniques based on partial differential equations.

20. The data mining system of claim 17 wherein said multi-resolution techniques are wavelets.

21. The data mining system of claim 17 wherein said denoising techniques are wavelet-based.

22. The data mining system of claim 17 wherein said denoising techniques are spatial filters.

23. The data mining system of claim 17 wherein said denoising techniques are techniques based on partial differential equations.

25. The method of data mining of claim 23 including the step of sampling said data and reducing the number of said data items.

26. The method of data mining of claim 23 including the step of conducting multiresolution analysis to perform a reversible transformation of said data into a coarser resolution.

27. The method of data mining of claim 23 including the step of removing noise from said data.

28. The method of data mining of claim 23 including the step of conducting data fusion of said data.

29. The method of data mining of claim 23 including the step of conducting dimension reduction which reduces the number of features for one or more of said data items.

30. The method of data mining of claim 23 including the steps of sampling said data and reducing the number of said data items, conducting multiresolution analysis to perform a reversible transformation of said data into a coarser resolution, removing noise from said data, conducting data fusion of said data, and conducting dimension reduction which reduces the number of features for one or more of said data items.

24. A method of data mining, comprising the steps of:

reading and displaying in parallel data files, said data files containing objects having at least one feature;

identifying in parallel said objects in said data files;

extracting in parallel said at least one feature for each of said objects; and

recognizing in parallel patterns among said objects based upon said features.

31. A method of data mining, comprising the steps of:

reading and displaying data files using a parallel object-oriented reading and displaying module, said data files containing objects having at least one feature;

identifying said objects in said data files using a parallel object-oriented object identifying module;

extracting at least one feature for each of said objects using a parallel object-oriented feature extracting module; and

recognizing patterns among said objects based on at least one feature using a parallel object-oriented pattern recognizing module.

32. A method of data mining, comprising the steps of:

reading, writing, and displaying a number of data files;

sampling said data files and reducing the number of said data files;

conducting multi-resolution analysis to perform a reversible transformation into a coarser resolution of said data files;

removing noise from said data files;

implementing data fusion of said data files;

identifying objects in said data files;

extracting at least one feature for each of said objects;

normalizing at least one feature of said objects;

reducing the dimension or number of at least one of said feature of said objects;

recognizing patterns among said objects using at least one of said feature;

displaying said data files and said objects and capturing feedback from scientists for validation;

storing at least one feature for each of said objects, after they have been extracted in said extracting step, reduced in number in said reducing step, used for pattern recognition in said recognizing patterns step, and displayed in said displaying step; and

linking said foregoing steps.

33. A method of data mining, comprising the steps of:

reading, writing, and displaying scientific, engineering, business and other data in different formats using a parallel object-oriented reading, writing, and displaying module, said data containing data items;

sampling said data and reducing the number of said data items using a parallel object-oriented sampling module;

conducting multiresolution analysis to perform a reversible transformation of said data into a coarser resolution using a parallel object-oriented multiresolution module;

removing noise from said data using a parallel object-oriented removing noise module;

conducting data fusion using a parallel object-oriented data fusion module;

when said data is obtained from different sensors at different times under different conditions at different resolutions;

identifying objects or data items in said data and extracting at least one feature for each of said data items using a parallel object-oriented identifying objects module;

conducting dimension reduction which reduces the number of said features for one or more of said data items using a parallel object-oriented conducting dimension reduction module;

implementing pattern recognition algorithms using a parallel object-oriented implementing pattern recognition algorithms module;

using a database to store at least one feature for each of said data items extracted after the number said features have been reduced, and as said data items grows in size, enabling easy access to subsets of said data; and

linking appropriate foregoing parallel object-oriented modules as necessary using a scripting language.