Method and system for data mining in high dimensional data spaces

• US 20040225638A1
• Filed: 02/26/2004
• Published: 11/11/2004
• Est. Priority Date: 05/08/2003
• Status: Active Grant

• Current Assignee: International Business Machines Corporation, Kaon Interactive, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Orechkina, Janna, Lingenfelder, Christoph, Geiselhart, Reinhold
• Granted Patent: US 7,567,972 B2
• Time in Patent Office: Days
• US Class Current: 707/1
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

The proposed computerized method and system is adapted for analyzing a multitude of items in a high dimensional (n-dimensional) data space D_n each described by n item features. The method uses a mining function f with at least one control parameter P_i controlling the target of the data mining function.

A first step is selecting a transformation function T for reducing dimensions of the n-dimensional space by means of space-filling curves mapping said n-dimensional space to a m-dimensional space (m<n).

A second step is determining a transformed control parameter P^T_i controlling the target of the data mining function in the m-dimensional space.

A third step is applying the selected transformation function T on the multitude D_n of items to create a transformed multitude D_m of items and is executing the mining function f controlled by the transformed control parameter P^T_i on the transformed multitude of items D_m.

Claims

1. A computerized data mining method for analyzing a multitude of items in an n-dimensional space D_n, each described by n item features, said method using a mining function f with at least one control parameter P_i controlling the target of the data mining function,

said method comprising a first step of selecting a transformation function T for reducing dimensions of said n-dimensional space by means of space-filling curves mapping said n-dimensional space to a m-dimensional space (m<

n);

said method comprising a second step of determining a transformed control parameter P^T_i controlling the target of the data mining function in said m-dimensional space;

said method comprising a third step of

applying said selected transformation function T on said multitude D_n of items to create a transformed multitude D_m of items; and

executing said mining function f controlled by said transformed control parameter P^T_i on said transformed multitude of items D_m.

2. The computerized data mining method according to claim 1,

wherein said transformed control parameter P^T_i is determined additionally based on one or more of the following:

the transformation function T;

the multitude of items D_n;

the number of dimensions n;

the number of dimensions m;

other control parameters P_j.

3. The computerized data mining method according to claim 1,

wherein said second step of determining said transformed control parameter P^T_i comprises the following sub-steps:

choosing a set of sample items of said n-dimensional space;

applying said selected transformation function f on said set of sample items to create a transformed set of sample items; and

determining said transformed control parameter P^T_i such that an acceptable target of the data mining function in said m-dimensional is achieved with respect to said transformed set of sample items.

4. The computerized data mining method according to claim 3,

wherein said set of sample items

is created by selecting items from said multitude of items D_n;

or

is created by creating artificial items within said n-dimensional space.

5. The computerized data mining method according to claim 1,

wherein, if in said second step no satisfactory transformed control parameter P^T_i could be determined, said method is iterated with said first step by selecting an alternative transformation function T_alt instead of said transformation function T.

6. The computerized data mining method according to claim 5,

wherein said alternative transformation function T_alt is being based on the same class of space-filling curves than said transformation function T, or

wherein said alternative transformation function T_alt is being based on another class of space-filling curves than said transformation function T.

7. The computerized data mining method according to claim 6,

wherein said class of space-filling curves is the class of Hilbert space-filling curves.

8. The computerized data mining method according to claim 1,

wherein in said second step empirical data of at least one comparable data mining problem is used for determining said transformed control parameter P^T_i.

9. The computerized data mining method according to claim 1,

wherein said mining function is solving a clustering problem and said control parameter P_i and transformed control parameter P^T_i is the minimal distance between clusters, or

wherein said mining function is solving a classification problem and said control parameter P_i and transformed control parameter P^T_i is the maximum depth of the classification decision tree.

10. The computerized data mining method according to claim 1,

wherein said method comprising a fourth step of presenting data mining results determined within said m-dimensional space in terms of said space n-dimensional.

11. The computerized data mining method according to claim 1,

wherein said m-dimensional space is reduced to one dimension (m=1) only.

12. A computer system comprising means adapted for carrying out the steps of the method according to claim 1.

13. A data processing program for execution in a data processing system comprising software code portions for performing a method according to claim 1, when said program is run on said data processing system.

14. A computer program product stored on a computer usable medium, comprising computer readable program means for causing a computer to perform a method according to claim 1 when said program is run on said computer.