Finding structures in multi-dimensional spaces using image-guided clustering

• US 7,558,425 B1
• Filed: 06/20/2008
• Issued: 07/07/2009
• 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:
  US12/143,131
• Publication Number:
  US 20090175544A1
• Time in Patent Office: 382 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 data processing system is provided that comprises a processor, a random access memory for storing data and programs for execution by the processor, and computer readable instructions stored in the random access memory for execution by the processor to perform a method for clustering data points in a multidimensional dataset in a multidimensional image space. The method 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 data processing system comprising:

a processor;

a random access memory for storing data and programs for execution by the processor; and

computer readable instructions stored in the random access memory for execution by the processor to perform 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 data processing system of claim 1, wherein the pyramidal sub-sampling performed comprises a logarithmic sampling strategy.

3. The data processing system 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 data processing system of claim 1, wherein the set of perceptual grouping constraints comprises proximity, density, orientation similarity, and region contiguity.

5. The data processing system 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.