Method and system for finding structures in multi-dimensional spaces using image-guided clustering

• US 7,406,200 B1
• Filed: 01/08/2008
• Issued: 07/29/2008
• Est. Priority Date: 01/08/2008
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Haas, Peter J., Lohman, Guy M., Lake, John M., Syeda-Mahmood, Tanveer
• Primary Examiner(s): Carter; Aaron W
• Application Number:
  US11/970,946
• Time in Patent Office: 203 Days
• Field of Search: 382224-228, 707 3- 6, 707/104.1
• US Class Current: 382/225
• CPC Class Codes: G06F 18/231 Hierarchical techniques, i.e. dividing or merging pattern sets so as to obtain a dendrogram
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A method is provided clustering data points in a multidimensional dataset in a multidimensional image space that comprises generating a multidimensional image from the multidimensional dataset; generating a pyramid of multidimensional images having varying resolution levels by successively performing a pyramidal sub-sampling of the multidimensional image; identifying data clusters at each resolution level of the pyramid by applying a set of perceptual grouping constraints; and determining levels of a clustering hierarchy by identifying each salient bend in a variation curve of a magnitude of identified data clusters as a function of pyramid resolution level.

Claims

1. A method for clustering data points in a multidimensional dataset in a multidimensional image space, the method comprising:

generating a multidimensional image from the multidimensional dataset;

generating a pyramid of multidimensional images having varying resolution levels by successively performing a pyramidal sub-sampling of the multidimensional image;

identifying data clusters at each resolution level of the pyramid by applying a set of perceptual grouping constraints; and

determining levels of a clustering hierarchy by identifying each salient bend in a variation curve of a magnitude of identified data clusters as a function of pyramid resolution level.

2. The method of claim 1, wherein the pyramidal sub-sampling performed comprises a logarithmic sampling strategy.

3. The method of claim 1, wherein identifying data clusters at each resolution level comprises identifying data clusters at a top resolution level of the pyramid by applying the set of perceptual grouping constraints, and identifying data clusters at each successively lower resolution level of the pyramid by extracting clusters identified at the previous resolution level and applying the set of perceptual grouping constraints.

4. The method of claim 1, wherein the set of perceptual grouping constraints comprises proximity, density, orientation similarity, and region contiguity.

5. The method of claim 1, wherein determining levels of the clustering hierarchy comprises identifying salient bends at points at which there is a zero crossing in a second derivative of the variation curve.