Automatic subspace clustering of high dimensional data for data mining applications

Claim 3

The method according to claim 1, further comprising the step of identifying the minimal cover for each cluster of connected dense units.

Claim 4

The method according to claim 1, wherein the step of determining dense units in selected subspaces is based on a bottom-up cluster identification approach.

Claim 5

The method according to claim 1, wherein the step of determining dense units in selected subspaces includes the steps of: determining candidate one-dimensional dense units within the high-dimensional data; and determining dense units based on a density of each unit.

Claim 6

The method according to claim 4, further comprising the steps of: grouping together dense units that each lie in a same subspace; computing a fraction of the data space that is covered by each group of dense units; and reducing a number groups of dense units that cover a predetermined portion of the data space.

Claim 7

The method according to claim 5, wherein the step of determining groups of dense units that cover the predetermined portion of the data space includes the step of reducing a number of groups of dense units based on a minimal description length principle.

Claim 8

The method according to claim 5, wherein the step of determining groups of dense units that cover the predetermined portion of the data space includes the steps of: dividing the groups of dense units into a first set and a second set; determining a mean value for each of the first and second set; determining a deviation value from each mean for each selected subspace; forming a code length using the mean value for each set and the deviation value for each selected subspace; and reducing a number of groups of dense units that cover the predetermined portion of the data space based a minimized code length.

Claim 9

The method according to claim 5, wherein the step of determining each cluster of dense units that are connected to other dense units in the selected subspaces within the data space is based on a labyrinth-search schema.

Claim 10

The method according to claim 5, wherein the step of determining each cluster of dense units that are connected to other dense units in the selected subspaces within the data space includes the steps of: assigning a cluster identification to a selected unit, the selected unit being a member of a selected set of dense units, the cluster identification being associated with the selected unit; assigning the cluster identification to a left-neighbor unit of the selected unit in a first dimension; recursively assigning the cluster identification to a left-neighbor unit of each left-neighbor unit assigned the cluster identification in the first dimension; assigning the cluster identification to a right-neighbor unit of the selected unit in the first dimension; recursively assigning the cluster identification to a right-neighbor unit of each right-neighbor unit assigned the cluster identification in the first dimension; recursively assigning the cluster identification to all neighbor units of in each dimension of the data space using unit as a starting point; and repeating the steps of recursively assigning another cluster identification to all neighbor units of another selected unit in each dimension of the data space using the another selected unit as another starting point, the another selected unit being a member of the selected set of dense units and not having an assigned cluster identification.

Claim 11

The method according to claim 5, wherein the step of determining maximal regions covering each cluster of connected dense units includes the steps of: growing a maximal region that covers a selected unit, the selected unit being a member of a selected cluster; recursively growing another maximal region that covers another selected unit, the another selected unit being a member of the selected cluster and not being covered by a maximal region; and forming a set of regions that are a cover of the selected cluster.

Claim 12

The method according to claim 10, wherein each step of growing the maximal region is based on a greedy-growth algorithm.

Claim 13

The method according to claim 10, wherein each step of growing the maximal region is based on a sequential-scan algorithm.

Claim 14

The method according to claim 10, wherein the step of determining the minimal cover for each cluster of connected dense units is based on a minimum number of maximal regions required to cover the selected cluster.

Claim 15

The method according to claim 13, wherein the step of determining the minimal cover for each cluster of connected dense units is further based on a removal heuristic that removes a maximal region covering a fewest number of units, every unit contained in the smallest maximal region being contained in another maximal region.

Claim 16

The method according to claim 13, wherein the step of determining the minimal cover for each cluster of connected dense units is further based on an addition heuristic that forms a maximal region that covers a maximum number of uncovered units in the selected cluster.

Claim 17

A program storage device comprising: a storage area; and information stored in the storage area, the information being readable by a machine, and tangibly embodying a program of instructions executable by the machine for performing method steps for finding clusters of units in high-dimensional data of a database, the method steps comprising: determining dense units in selected subspaces within a data space of the high-dimensional data of the database; determining each cluster of dense units that are connected to other dense units in the selected subspaces within the data space; determining maximal regions covering each cluster of connected dense units; and determining a minimal cover for each cluster of connected dense units.

Claim 18

A program storage device comprising: a storage area; and information stored in the storage area, the information being readable by a machine, and tangibly embodying a program of instructions executable by the machine for performing method steps for finding clusters of units in high-dimensional data of a database, the method steps comprising: determining dense units in selected subspaces within a data space of the high-dimensional data of the database; determining each cluster of dense units that are connected to other dense units in the selected subspaces within the data space; determining maximal regions covering each cluster of connected dense units; and determining a minimal cover for each cluster of connected dense units.

Claim 19

The program storage device according to claim 16, wherein the method steps further comprise the step of identifying the minimal cover for each cluster of connected dense units.

Claim 20

The program storage device according to claim 16, wherein the step of determining dense units in selected subspaces is based on a bottom-up cluster identification approach.

Claim 21

The program storage device according to claim 16, wherein the step of determining dense units in selected subspaces includes the steps of: determining candidate one-dimensional dense units within the high-dimensional data; and determining dense units based on a density of each unit.

Claim 22

The program storage device according to claim 19, wherein the method steps further comprise the steps of: grouping together dense units that each lie in a same subspace; computing a fraction of the data space that is covered by each group of dense units; and reducing a number groups of dense units that cover a predetermined portion of the data space.

Claim 23

The program storage device according to claim 20, wherein the step of determining groups of dense units that cover the predetermined portion of the data space includes the step of reducing a number of groups of dense units based on a minimal description length principle.

Claim 24

The program storage according to claim 20, wherein the step of determining groups of dense units that cover the predetermined portion of the data space includes the steps of: dividing the groups of dense units into a first set and a second set; determining a mean value for each of the first and second set; determining a deviation value from each mean for each selected subspace; forming a code length using the mean value for each set and the deviation value for each selected subspace; and reducing a number of groups of dense units that cover the predetermined portion of the data space based a minimized code length.

Claim 25

The program storage device according to claim 20, wherein the step of determining each cluster of dense units that are connected to other dense units in the selected subspaces within the data space is based on a labyrinth-search schema.

Claim 26

The program storage device according to claim 20, wherein the step of determining each cluster of dense units that are connected to other dense units in the selected subspaces within the data space includes the steps of: assigning a cluster identification to a selected unit, the selected unit being a member of a selected set of dense units, the cluster identification being associated with the selected unit; assigning the cluster identification to a left-neighbor unit of the selected unit in a first dimension; recursively assigning the cluster identification to a left-neighbor unit of each left-neighbor unit assigned the cluster identification in the first dimension; assigning the cluster identification to a right-neighbor unit of the selected unit in the first dimension; recursively assigning the cluster identification to a right-neighbor unit of each right-neighbor unit assigned the cluster identification in the first dimension; recursively assigning the cluster identification to all neighbor units of in each dimension of the data space using unit as a starting point; and repeating the steps of recursively assigning another cluster identification to all neighbor units of another selected unit in each dimension of the data space using the another selected unit as another starting point, the another selected unit being a member of the selected set of dense units and not having an assigned cluster identification.

Claim 27

The program storage device according to claim 20, wherein the step of determining maximal regions covering each cluster of connected dense units includes the steps of: growing a maximal region that covers a selected unit, the selected unit being a member of a selected cluster; recursively growing another maximal region that covers another selected unit, the another selected unit being a member of the selected cluster and not being covered by a maximal region; and forming a set of regions that are a cover of the selected cluster.

Claim 28

The program storage device according to claim 25, wherein each step of growing the maximal region is based on a greedy-growth algorithm.

Claim 29

The program storage device according to claim 25, wherein each step of growing the maximal region is based on a sequential-scan algorithm.

Claim 30

The program storage device according to claim 25, wherein the step of determining the minimal cover for each cluster of connected dense units is based on a minimum number of maximal regions required to cover the selected cluster.

Claim 31

The program storage device according to claim 23, wherein the step of determining the minimal cover for each cluster of connected dense units is further based on a removal heuristic that removes a maximal region covering a fewest number of units, every unit contained in the smallest maximal region being contained in another maximal region.

Claim 32

The program storage device according to claim 28, wherein the step of determining the minimal cover for each cluster of connected dense units is further based on an addition heuristic that forms a maximal region that covers a maximum number of uncovered units in the selected cluster.

Claim 33

The program storage device according to claim 16, wherein the program storage device includes a magnetically recordable medium.

Claim 34

The program storage device according to claim 16, wherein the program storage device includes an optically recordable medium.