Method for clustering data items through distance-merging and density-merging techniques

• US 8,473,215 B2
• Filed: 04/26/2004
• Issued: 06/25/2013
• Est. Priority Date: 04/25/2003
• Status: Active Grant

• Current Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford Management Co.)
• Original Assignee: Leland Stanford Junior University (Stanford University)
• Inventors: Walther, Guenther, Pan, Jinhui, Herzenberg, Leonore A., Moore, Wayne, Parks, David, Belitskaya-Levy, Ilana
• Primary Examiner(s): Whaley, Pablo S
• Application Number:
  US10/832,992
• Publication Number:
  US 20110029519A1
• Time in Patent Office: 3,347 Days
• Field of Search: None
• US Class Current: 702/19
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/24564 Applying rules; Deductive queries
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 16/55 Clustering; Classification
• CPC Class Codes: G06F 16/90 Details of database functions independent of the retrieved data types
• CPC Class Codes: G16B 25/10 Gene or protein expression profiling; Expression-ratio estimation or normalisation
• CPC Class Codes: G16B 5/00 ICT specially adapted for modelling or simulations in systems biology, e.g. gene-regulatory networks, protein interaction networks or metabolic networks

Abstract

A method and/or system for analyzing data using population clustering through density based merging.

Claims

1. A computer-implemented method for identifying clusters of observed data items in a data space comprising:

a) defining an N-dimensional normalized lattice comprising a plurality of lattice points used as data reduction points in a data space of said data items, wherein said lattice points have a regular placement and distance relationship to each other;

b) obtaining a set of n observed data items and parameter values from an information system, wherein the parameter values are associated with the observed data items;

c) reducing the observed data items to lattice points and lattice point weights by performing steps of;

identifying one or more data items within a predetermined distance of each lattice point, and calculating lattice point weights by applying a weighting rule that averages the parameter values associated with the observed data items within a predetermined distance of each lattice point;

d) determining paths between lattice points by performing steps of;

defining an estimated density surface for comparing lattice points within a predetermined distance, and creating directional associations between lattice points and at least one other lattice point within a predetermined distance by applying an association rule based on said estimated density surface;

e) determining a lattice point path by performing steps of;

sequentially connecting, based on said directional associations, a first lattice point and one or more subsequent lattice points within a predetermined distance until a terminal lattice point is reached, wherein said terminal lattice point is not connectable to any other lattice point based on said association rule;

f) assigning lattice points in the data space to clusters or background noise by performing steps of;

comparing the terminal lattice points of a said lattice point paths to a density threshold and defining the terminal lattice point as belonging to a new cluster, an existing cluster, or background noise;

labeling the lattice points in lattice point path as points belonging to said new cluster, existing cluster, or background points based on said comparing;

repeating said comparing and labeling steps until the remaining lattice points are labeled as belonging to a previously identified cluster or to background noise;

g) distance merging clusters of lattice points in the data space by performing steps of;

associating each cluster of lattice points with a root indicating the maximum terminal lattice point for that cluster;

determining distances between roots, and merging clusters associated with said roots if the distance between the roots is below a distance threshold;

h) density merging roots of clusters of lattice points in the data space by performing steps of;

examining the roots of clusters, determining paths along consecutive lattice points to other roots, and merging roots of clusters when the path of consecutive lattice points densities falls below a minimum density threshold;

repeating said density merging until no pairs of roots meet a density merging criteria;

i) assigning the observed data items to clusters of lattice points in the data space by performing steps of;

applying an assignment rule that assigns each observed data item to the closest lattice point within a predetermined distance; and

assigning each observed data item to the same cluster to which its associated lattice point is assigned; and

j) displaying the clusters of observed data items to a user graphical format, wherein steps a) through j) are performed on a suitably programmed computer.

2. The method of claim 1, wherein said set of n observed data items represents a set of one or more fluorescence levels obtained from a particular fluorescence channel of a fluorescence-activated cell sorter (FACS);

and wherein said clusters of observed data items each provide an indication of separable cell subpopulations analyzed by said cell sorter.

3. The method of claim 1, wherein said data space has N dimensions and each N corresponds to a number of values of interest associated with at least one of said data items;

and wherein said regular placement and distance relationship of lattice points is determined by a lattice rule that examines smallest and largest values of interest in each dimension and determines the lattice spacing.

4. The method of claim 3, wherein said lattice spacing is determined according to a spacing rule comprising taking the difference between smallest and largest values of interest in each dimension and defining a regular spacing of M units, where M represents a desired granularity.

5. The method of claim 1 wherein said association rule comprises:

determining density values of a plurality of lattice points by;

using a kernel density estimate of weights on a lattice point to determine a density estimate at each of said plurality of lattice points; and

at a lattice point, determining for a plurality of surrounding lattice points whether to make a directional association.

6. The method of claim 1 wherein said association rule comprises:

determining a density surface for said lattice points;

making a directional association if a slope of said density surface from a first lattice point to a second lattice point is significantly positive.

7. The method of claim 1, wherein said creating directional associations further comprises breaking spurious path terminations prior to said assigning lattice points in the data space to clusters or background noise.