Systems and methods for subspace clustering

• US 20050278324A1
• Filed: 05/31/2004
• Published: 12/15/2005
• Est. Priority Date: 05/31/2004
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Yu, Philip S., Fan, Wei, Wang, Haixun
• Granted Patent: US 7,565,346 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures

Abstract

Unlike traditional clustering methods that focus on grouping objects with similar values on a set of dimensions, clustering by pattern similarity finds objects that exhibit a coherent pattern of rise and fall in subspaces. Pattern-based clustering extends the concept of traditional clustering and benefits a wide range of applications, including e-Commerce target marketing, bioinformatics (large scale scientific data analysis), and automatic computing (web usage analysis), etc. However, state-of-the-art pattern-based clustering methods (e.g., the pCluster algorithm) can only handle datasets of thousands of records, which makes them inappropriate for many real-life applications. Furthermore, besides the huge data volume, many data sets are also characterized by their sequentiality, for instance, customer purchase records and network event logs are usually modeled as data sequences. Hence, it becomes important to enable pattern-based clustering methods i) to handle large datasets, and ii) to discover pattern similarity embedded in data sequences. There is presented herein a novel method that offers this capability.

Claims

1. An apparatus for facilitating subspace clustering, said apparatus comprising:

an arrangement for accepting input data;

an arrangement for discerning pattern similarity in the input data; and

an arrangement for clustering the data on the basis of discerned pattern similarity;

said arrangement for discerning pattern similiarity comprising an arrangement for discerning pattern similiarity among both tabular data and sequential data contained in the input data.

2. The apparatus according to claim 1, wherein said arrangement for discerning pattern similarity is adapted to employ a distance function for determining a sequence-based distance between data objects.

3. The apparatus according to claim 2, wherein the distance function comprises the following:

given two data objects x and y, a subspace S, and a dimension k∈

S, the sequence-based distance between x and y is as follows;

${\mathrm{dist}}_{k,S}<br><br>\left(x,y\right)=\underset{i\in <br><br>S}{\max }<br><br><br><br>\left(x_i-y_i\right)-\left(x_k-y_k\right)<br><br>.$

4. The apparatus according to claim 1, wherein said discerning arrangement is adapted to:

define a pattern space; and

divide the pattern space into grids.

5. The apparatus according to claim 4, wherein said discerning arrangement is adapted to:

construct a tree structure which summarizes frequent patterns discerned among the input data; and

establish a grid of cells corresponding to the input data.

6. The apparatus according to claim 5, wherein the tree structure is adapted to detetermine at least one of:

the number of occurrences of a given pattern; and

the density of any cell in the grid of cells.

7. The apparatus according to claim 6, wherein said clustering arrangement is adapted to merge cells of at least a threshold density into clusters.

8. A method of facilitating subspace clustering, said method comprising the steps of:

accepting input data;

discerning pattern similarity in the input data; and

clustering the data on the basis of discerned pattern similarity;

said discerning step comprising discerning pattern similiarity among both tabular data and sequential data contained in the input data.

9. The method according to claim 8, wherein said step of discerning pattern similarity in the input data comprises employing a distance function for determining a sequence-based distance between data objects.

10. The method according to claim 9, wherein the distance function comprises the following:

given two data objects x and y, a subspace S, and a dimension k∈

S, the sequence-based distance between x and y is as follows;

${\mathrm{dist}}_{k,S}<br><br>\left(x,y\right)=\underset{i\in <br><br>\mathrm{??}}{\max }<br><br><br><br>\left(x_i-y_i\right)-\left(x_k-y_k\right)<br><br>.$

11. The method according to claim 8, wherein said discerning step comprises:

defining a pattern space; and

dividing the pattern space into grids.

12. The method according to claim 11, wherein said discerning step comprises:

constructing a tree structure which summarizes frequent patterns discerned among the input data; and

establishing a grid of cells corresponding to the input data.

13. The method according to claim 12, wherein said discerning step comprises determining at least one of:

the number of occurrences of a given pattern; and

the density of any cell in the grid of cells.

14. The method according to claim 13, wherein said clustering step comprises merging cells of at least a threshold density into clusters.

15. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for facilitating subspace clustering, said method comprising the steps of:

accepting input data;

discerning pattern similarity in the input data; and

clustering the data on the basis of discerned pattern similarity;

said discerning step comprising discerning pattern similiarity among both tabular data and sequential data contained in the input data.