A METHOD FOR IDENTIFYING CLUSTERS OF FLUORESCENCE-ACTIVATED CELL SORTING DATA POINTS
A method and/or system for analyzing data using population clustering through density based merging.
1 . A computer implemented method of identifying clusters of data items, wherein a data item is associated with one or more values using an information system comprising:
defining a plurality of lattice points in a data space able to contain some of said data items of interest, said lattice points spaced according to a lattice rule;
calculating weights for said lattice points using one or more of said data items according to a weighting rule;
determining a density at said lattice points relating a weight at a lattice point to weights at nearby lattice points using a density function;
creating, for a lattice point, a directional association with at least one other lattice point using an association rule;
following directional associations between lattice points to determine terminal states for one or more pointer paths;
assigning each data item to a lattice point according to an assignment rule; and
using terminal states of said pointer paths to determine a cluster for said data item.
2 . The method of claim 1 wherein said data items are groups of values each associated with an individual cell and said cluster is a cell subpopulation.
3 . The method of claim 1 wherein:
said data items each represent market participants in an economic market;
said values represent obtainable characteristic measures of a market participant; and
said clusters each represent a category of market participants.
4 . The method of claim 1 further wherein:
said one or more values are effectively continuous.
5 . The method of claim 1 wherein said identifying one or more clusters uses directional associations of a plurality of lattice points and a density estimated at each lattice point and does not use weights assigned to lattice points or original data values.
6 . An apparatus for creating groupings from data comprising:
means for assigning each piece of data from said set of data to a point on a lattice;
means for assigning weights to each lattice point based on the data near said lattice point;
means for determining for each of said lattice points if each of said lattice points should be associated with one of its surrounding lattice points and if so creating a pointer from the individual lattice point to the surrounding lattice point it is associated with; and
means for creating clusterings of the lattice points.
7 . A set of application program interfaces embodied on a computer-readable medium for execution on a computer in conjunction with an application program that determines clusters within a set of data, comprising:
a first interface that receives data;
a second interface that receives parameters; and
returns groupings of said data.
8 . A method of clustering data items, wherein a data item is associated with one or more semi-continuous values, using an information system comprising:
creating a reduction data item set, each reduction data item associated with one or more quantized values correlated with said one or more semi-continuous values;
assigning each data item to a reduction data item according to an assignment rule;
calculating weights for said reduction data items using one or more data items according to a weighting rule;
determining for a plurality of reduction data items if it should be associated with another reduction data item according to an association rule;
for at least one reduction data item, creating a directional association with at least one other reduction data item; and
identifying one or more clusters of said reduction data items using one or more directional associations and/or one or more of said weights.
9 . A method enabling analysis of large sets of data observation points, each point having multiple parameters comprising:
performing a first automated clustering of data points using a subset of said parameters using an information system, said first clustering providing one or more data clusters;
selecting a first selected cluster;
successively performing subsequent automated child clusterings on selected clusters, while option ally choosing different parameters allowing for said clustering.
10 . A method enabling analysis o(large sets of data observation points, each point having multiple parameters using an information system comprising:
displaying to a user results of an automated clustering of data points using a subset of said parameters, said first clustering indicating one or more data clusters;
registering an input from said user selecting a first selected cluster from which to generate children clusters;
providing an interface allowing a user to optionally choose different parameters allowing for said children clusters; and
displaying a hierarchy of clustering results.
11 . The method of claim 8 , wherein the step of calculating weights includes linear binning in accordance with the formula:
w
m
=
∑
i
=
1
n
∏
j
=
1
d
max
(
0
,
1
-
x
i
,
j
-
y
mj
/
Δ
j
)
12 . The method of claim 1 , wherein the step of determining a density includes computing an estimate of a density surface {circumflex over (f)}(y m ) wherein the Gaussian kernel is denoted by φ(b)=1/√{square root over (2)}πexp(−b 2 /2) and the estimated density y m is computed by the formula:
f
^
(
y
m
)
=
1
/
n
∑
l
1
=
-
Z
1
Z
1
…
∑
l
d
=
-
Z
d
Z
d
ω
m
-
1
∏
j
=
1
d
φ
(
l
j
Δ
j
/
h
j
)
/
h
j
,
where
l
=
(
l
1
,
…
,
l
d
)
,
Z
j
=
min
(
⌊
4
h
j
/
Δ
j
⌋
/
,
M
-
1
)
,
and
h
j
=
SD
(
{
x
i
,
j
,
i
=
1
,
…
,
n
}
)
n
-
1
/
(
d
+
4
)
)
where SD denotes standard deviation.
13 . The method of claim 12 , wherein the formula:
f
^
(
y
m
)
=
1
/
n
∑
l
1
=
-
Z
1
Z
1
…
∑
l
1
=
-
Z
1
Z
d
ω
m
-
1
∏
j
=
1
d
φ
(
l
j
Δ
j
/
h
j
)
/
h
j
,
where
l
=
(
l
1
,
…
,
l
d
)
,
Z
j
=
min
(
⌊
4
h
j
/
Δ
j
⌋
/
,
M
-
1
)
,
and
h
j
=
SD
(
{
x
i
,
j
,
i
=
1
,
…
,
n
}
)
n
-
1
/
(
d
+
4
)
)
,
is computed by the Fast Fourier Transform (FFT).
14 . The method of claim 1 , wherein the step of determining a density includes calculating an estimate of the standard deviation of the density estimate in accordance with the formula:
σ
^
m
2
=
1
n
(
n
-
1
)
∑
l
1
=
-
Z
1
Z
1
…
∑
l
d
=
-
Z
d
Z
d
w
m
-
1
∏
j
=
1
d
φ
2
(
l
j
Δ
j
/
h
j
)
/
h
j
2
-
1
n
-
1
f
^
(
y
m
)
2
and defining an index set S={m∈{1, . . . M} d : {circumflex over (f)}(y m )>4.3*√{square root over ({circumflex over (σ)} m 2 )}}.
15 . The method of claim 14 , wherein the step of creating a directional association includes establishing and removing pointers between neighboring lattice points by successively executing a series of evaluations for all lattice points y m , where m is an element of S, in turn:
considering all neighboring lattice points p 1 . . . , p nm which are defined as the set of all lattice points contained in a s-dimensional rectangular volume. Let p be an element of {p 1 , . . . , p nm } such that {circumflex over (f)}(p)=max k=1, . . . nm {circumflex over (f)}(p k ), splitting ties in an arbitrary manner; then a pointer is established from y m to p provided:
f
^
(
p
)
>
f
^
(
y
m
)
;
and
∂
∂
e
f
^
(
y
m
)
>
λ
m
,
where
e
=
(
p
-
y
m
)
/
p
-
y
m
,
·
denotes Euclidean norm, and
∂
∂
e
f
^
(
y
m
)
=
∑
?
d
e
∂
∂
y
f
^
(
y
m
)
,
?
indicates text missing or illegible when filed
which indicates a gradient of the density estimate,
∂
∂
y
m
a
f
^
(
y
m
)
=
1
/
n
∑
l
1
=
-
Z
1
Z
1
…
∑
l
d
=
-
Z
d
Z
d
w
m
-
1
-
l
α
Δ
a
h
α
2
∏
j
=
1
d
φ
(
l
j
Δ
j
/
h
j
)
/
h
j
λ
m
=
q
(
0.95
1
/
κ
)
∑
^
m
2
κ
=
#
S
Σ
mes
w
m
n
(
2
π
)
d
/
2
∏
j
=
1
d
h
j
Σ
m
∈
s
w
m
f
^
(
y
m
)
∑
^
m
2
=
1
n
-
1
(
∑
a
,
b
=
1
d
e
a
e
b
[
A
-
∂
∂
y
m
a
f
^
(
y
m
)
∂
∂
y
m
b
f
^
(
y
m
)
]
)
A
=
1
/
n
∑
l
1
=
-
Z
1
Z
1
…
∑
l
d
=
-
Z
1
Z
d
w
m
-
1
l
a
l
b
Δ
a
Δ
b
h
a
2
h
b
2
∏
ϕ
=
1
δ
φ
2
(
l
j
Δ
j
/
h
j
)
/
h
j
2
,
A being an estimate of
∂
∂
y
m
a
f
(
y
m
)
∂
∂
y
m
b
f
(
y
m
)
and q(x) denotes the 100*xth percentile of the standard normal distribution.
16 . The method of claim 15 , wherein from each lattice point y m , where m is not an element of S, a pointer is established that points to a state representing background noise.
17 . The method of claim 16 , wherein the step of following directional associations further includes the evaluation: for all lattice points y m , where m is an element of S, in turn: if a pointer originates at y m , then it will point to a different lattice point, which itself may have a pointer originating from it; following a succession of pointers until a lattice point y z is reached that either (a) does not have any pointer originating from it or (b) has a pointer originating from it that points to a state representing a cluster or background noise; in the event (a) removing all pointers visited in the succession and establishing new pointers originating from each lattice point to the background noise state, provided {circumflex over (f)}(y z )<q(0.95 1/κ )√{square root over ({right arrow over (σ)} z 2 )}, otherwise only the pointer originating from y z is removed and a new pointer is established that originates from y z (if any) is removed and a new pointer is establishes that originates from y z and points to a new cluster state, in the event (b) no pointers are removed or established.
18 . The method of claim 17 , wherein the step of following directional associations further includes the following steps:
Let {y m(1) , . . . y m(k) } be the set of all lattice points which have a pointer originating from them to a dummy state representing a cluster, enumerated such that {circumflex over (f)}(y m(1) )≧ . . . ≧{circumflex over (f)}(y m(k) ) and for i=1, . . . , k do:
Set A={m(i), and iterate the following loop until no more indices are added to A:
(Begin loop)
For each index a which is an element of A in turn, add all the indices p to A that satisfy:
Yp is a neighbor or ya as defined in claim 15 , and
No pointer originates from yp, and
{circumflex over ( f )}( y p )+{circumflex over (σ)} p ≧{circumflex over (f)} ( y m(i) )+{circumflex over (σ)} m(i)
(End loop)
Denote by B the set of indices of lattice points from which a pointer originates to a cluster state and that also have some y p , p being an element of as neighbor. If B is not empty, then do the following:
Define q by {circumflex over (f)}(y q )=max r∈B {circumflex over (f)}(y r ), breaking ties arbitrarily;
Establish a pointer from each y p , p an element of A\{m(i)} to y q ;
For each r which is an element of B, if r≠q, remove the pointer from y r to the state representing a cluster and establish a new pointer from y r to y q
19 . The method of claim 18 , wherein the steps recited in claim 18 are repeated until there are no more additions or deletions of pointers to cluster state.
20 . The method of claim 19 , wherein from each lattice point that does not have a pointer originating from it, a pointer is established pointing to the background noise state.