13 Pattern Recognition and Reconstruction
585
about its location is available (beam profile, target position). On the other hand,
secondary decay vertices of short-lived decays are hard to find, as some of the
decay products may also be compatible with the primary vertex. Vertex finding
methods can be roughly divided in three main types: generic clustering algorithms,
topological methods, and iterated estimators. The latter can be considered as a
special divisive clustering method.
13.2.2.1 Clustering Methods
As mentioned above in the context of jet finding (see Sect. 13.1.3.6), clustering
methods are based on a distance matrix or a similarity matrix of the objects to be
classified. A cluster is then a group with small distances (large similarities) inside
the group and large distances (small similarities) to objects outside the group. The
distance measure reflects only the geometry of the tracks.
Various clustering methods have been evaluated in the context of vertex finding,
of both the hierarchical and the non-hierarchical type [117]. Hierarchical clustering
can be agglomerative or divisive. In agglomerative clustering each track starts out as
a single cluster. Clusters are merged iteratively on the basis of a distance measure.
The shortest distance in space between two tracks is peculiar insofar as it does
not satisfy the triangle inequality: if tracks a and b are close, and tracks b and c
are close, it does not follow that tracks a and c are close as well. The distance
between two clusters of tracks should therefore be defined as the maximum of the
individual pairwise distances, known as complete linkage in the clustering literature.
Alternatively, the distance between two clusters can be the distance between the
two vertices fitted from the clusters. Divisive clustering starts out with a single
cluster containing all tracks. Further division of this cluster can be based on repeated
vertex estimation with outlier identification (see Sect. 13.2.2.3). Examples of nonhierarchical clustering methods used in vertex finding are vector quantization, the
k-means algorithm and deterministic annealing [113].
13.2.2.2 Topological Methods
A very general topological vertex finder was proposed in [118]. It is related to
the Radon transform, which is a continuous version of the Hough transform used
for track finding (Sect. 13.1.2.1). The search for vertices is based on a function
V (v) which quantifies the probability of a vertex at location v. For each track a
Gaussian probability tube f i (v) is constructed. The function V (v) is defined taking
into account that the value of f i (v) must be significant for at least two tracks:
V (v) =
n
i=0
f i (v) −
n
i=0 f 2
i (v)
n
i=0 f i (v)
585
about its location is available (beam profile, target position). On the other hand,
secondary decay vertices of short-lived decays are hard to find, as some of the
decay products may also be compatible with the primary vertex. Vertex finding
methods can be roughly divided in three main types: generic clustering algorithms,
topological methods, and iterated estimators. The latter can be considered as a
special divisive clustering method.
13.2.2.1 Clustering Methods
As mentioned above in the context of jet finding (see Sect. 13.1.3.6), clustering
methods are based on a distance matrix or a similarity matrix of the objects to be
classified. A cluster is then a group with small distances (large similarities) inside
the group and large distances (small similarities) to objects outside the group. The
distance measure reflects only the geometry of the tracks.
Various clustering methods have been evaluated in the context of vertex finding,
of both the hierarchical and the non-hierarchical type [117]. Hierarchical clustering
can be agglomerative or divisive. In agglomerative clustering each track starts out as
a single cluster. Clusters are merged iteratively on the basis of a distance measure.
The shortest distance in space between two tracks is peculiar insofar as it does
not satisfy the triangle inequality: if tracks a and b are close, and tracks b and c
are close, it does not follow that tracks a and c are close as well. The distance
between two clusters of tracks should therefore be defined as the maximum of the
individual pairwise distances, known as complete linkage in the clustering literature.
Alternatively, the distance between two clusters can be the distance between the
two vertices fitted from the clusters. Divisive clustering starts out with a single
cluster containing all tracks. Further division of this cluster can be based on repeated
vertex estimation with outlier identification (see Sect. 13.2.2.3). Examples of nonhierarchical clustering methods used in vertex finding are vector quantization, the
k-means algorithm and deterministic annealing [113].
13.2.2.2 Topological Methods
A very general topological vertex finder was proposed in [118]. It is related to
the Radon transform, which is a continuous version of the Hough transform used
for track finding (Sect. 13.1.2.1). The search for vertices is based on a function
V (v) which quantifies the probability of a vertex at location v. For each track a
Gaussian probability tube f i (v) is constructed. The function V (v) is defined taking
into account that the value of f i (v) must be significant for at least two tracks:
V (v) =
n
i=0
f i (v) −
n
i=0 f 2
i (v)
n
i=0 f i (v)