PaperlayerView exact revision on arXiv

Source-linked AI summary

Expectation-Maximization Binary Clustering for Behavioural Annotation

Joan Garriga, John R. Palmer, Aitana Oltra, Frederic Bartumeus

arXiv:1503.04059v2q-bio.QM

TL;DR

Behavioural clustering can produce statistically sound groups that are difficult to interpret in behavioural terms. EMbC uses a binary high/low partition to support semantic interpretation, and empirical datasets suggest it works across varied tracking settings and species.

  • Problem

    Classical clustering can identify statistically sound groups that are difficult to interpret in behavioural terms.

    Source: §2.2.1 · p. 6

  • Method

    EMbC uses minimally supervised multivariate clustering that accounts for variable correlations and uncertainty, with a binary partition into high and low values.

    Source: §1 · p. 3, §2.2.1 · p. 6

  • Results

    Across empirical datasets, EMbC behaved reasonably well across tracking technologies, species, and ecological contexts.

    Source: §5 · p. 15

  • Takeaways & Limitations

    The method is general and robust enough for use across species and tracking methodologies, though final semantics depend on variables and species.

    Source: §5 · p. 16

    A steady likelihood decrease can signal a discrepancy between binary and optimal-likelihood partitions, suggesting the data may not suit binary partitioning.

    Source: §2.2.3 · p. 8

Abstract

from arXiv · show

We present a variant of the well sounded Expectation-Maximization Clustering algorithm that is constrained to generate partitions of the input space into high and low values. The motivation of splitting input variables into high and low values is to favour the semantic interpretation of the final clustering. The Expectation-Maximization binary Clustering is specially useful when a bimodal conditional distribution of the variables is expected or at least when a binary discretization of the input space is deemed meaningful. Furthermore, the algorithm deals with the reliability of the input data such that the larger their uncertainty the less their role in the final clustering. We show here its suitability for behavioural annotation of movement trajectories. However, it can be considered as a general purpose algorithm for the clustering or segmentation of multivariate data or temporal series.

Supporting Information

The Supporting Information lists materials on movement variables, EMbC procedures, synthetic trajectories, performance comparisons, and supplementary data.

Supporting Information

  • The supplement lists materials on movement variables, Caenorhabditis elegans movement analysis, data-reliability functions, and visualizations of annotated trajectories.Source: S1 Text · p. 2
  • It includes materials on EMbC likelihood dynamics, synthetic-trajectory generation, and performance measures and comparisons.Source: S1 Text · p. 2
  • The supplement identifies an S2 text on generating results with the EMbC R-package and an S3 data file containing datasets.Source: S1 Text · p. 2

1 Introduction

Movement research needs unsupervised methods to identify behavioural modes across large, varied trajectory datasets. The paper develops a minimally supervised clustering method intended to balance statistical significance with biological interpretability.

1 Introduction

  • Movement datasets vary in sampling rates and accuracy, making unsupervised identification of trajectory behavioural modes a key challenge.Source: §1 · p. 3
  • Identifying behaviourally meaningful movement modes can help connect movement patterns to biological processes and support more predictive movement models.Source: §1 · p. 3
  • Existing state-space models rely on strong distribution and transition assumptions and can require time-consuming, species-specific parameter estimation.Source: §1 · p. 3
  • Many current annotation procedures also require substantial computation or data-specific supervision, limiting use with massive datasets and comparative ecology.Source: §1 · p. 3
  • The proposed method uses minimally supervised multivariate clustering that accounts for feature correlations and uncertainty, assuming Gaussian mixtures over a binary partition.Source: §1 · p. 3
  • The paper compares EMbC with EMC and basic HMMs on synthetic data and with expert labels on empirical data to illustrate relative strengths and weaknesses, not rank methods.Source: §1 · p. 4

2 Models

The section introduces EMbC as a Gaussian-mixture clustering variant designed to yield interpretable high/low partitions while accounting for data reliability. It contrasts this with standard EMC and explains the delimiters, reliability weighting, and implementation choices that constrain the resulting clusters.

2.1 Expectation-Maximization Clustering

  • EMC alternates between estimating cluster-membership probabilities and updating Gaussian-mixture parameters, converging to a local likelihood maximum that depends on initialization.The standard setup specifies the number of clusters and a minimum variance for each variable.Source: §2.1 · pp. 4–5

2.2 EMbC Algorithm

  • EMbC adapts EMC to promote interpretable clustering and account for variable data reliability, using Gaussian mixtures within an EMC framework for movement annotation.Gaussian-mixture assumptions and their use for movement-mode classification predate this work.Source: §2 · p. 4, §2.2 · p. 5

2.2.1 Clustering semantics: the delimiters

  • Delimiters divide each variable into low and high values, yielding binary regions whose labels can map to behavioural modes, though the interpretation depends on variables and species.For velocity and turning, the example maps LL, LH, HL, and HH to resting, intensive search, travelling or relocation, and extensive search. The illustrated EMbC partition has clearer semantics than EMC's, but EMbC is not guaranteed to achieve higher likelihood and may trade likelihood for meaningful partitions.Source: §2.2.1 · p. 6

2.2.2 Data accuracy and reliability

  • Reliability coefficients give less accurate observations less weight when estimating Gaussian parameters, but the reliability function depends on the variable and source of error.Movement-variable uncertainty can arise from spatial errors and irregular sampling times.Source: §2.2.2 · p. 7

2.2.3 Implementation

  • During implementation, EMbC updates delimiters from adjacent-cluster likelihood weights, bounds Gaussian-mean calculations to delimiter-defined regions, and incorporates reliability weighting.Some points may belong to multiple regions, contributing to the means of each associated cluster.Source: §2.2.3 · pp. 7–8
  • EMbC's modified updates are not likelihood-maximization expressions, so likelihood can drop sporadically; sustained decreases may signal data unsuited to binary partitioning and trigger a warning and stop.The authors describe the drops as restarts from a new, less blind guess in the likelihood landscape.Source: §2.2.3 · p. 8
  • EMbC has at most 2^m clusters, may lose clusters during optimization, and is intended for roughly five or six meaningful input variables rather than automated feature selection.Its starting point uses uniform assignments and cluster priors, with initial delimiters selected by a maximum-entropy criterion; σ_min sets variable-specific analysis resolution.Source: §2.2.3 · pp. 8–9

3 Analysis

The analysis compares EMbC with related methods on synthetic trajectories and examines empirical movement tracks. It also studies temporal smoothing and robustness to data loss and data inaccuracy.

3 Analysis

  • Synthetic four-cluster trajectories compare EMbC with EMC and HMM across differing cluster overlap, sequence generation methods, and trajectory lengths.The comparisons illustrate relative strengths and weaknesses rather than rank the methods.Source: §3 · p. 9
  • Empirical tracks cover varied ecological contexts and high-resolution GPS, standard GPS, Argos, and video tracking.The examples mostly use local velocity and turn measures, with another movement-variable example also shown.Source: §3 · p. 9
  • Confusion matrices yield recall, precision, and F-measure, but empirical comparisons are not strict performance assessments when expert labels use information absent from the input features.Redistribution of EMbC annotations into expert labels can still inform understanding of the algorithm.Source: §3 · pp. 9–10

3.1 Smoothing of annotated trajectories

  • EMbC labels each location without temporal context; coarse-graining can use running-window averages or post-processing based on temporal correlations.The post-processing function checks isolated labels against neighboring likelihood weights using a user-set threshold, so it is kept separate from clustering.Source: §3.1 · p. 10

3.2 Robustness to data loss and data inaccuracy

  • To test data-loss robustness, the analysis randomly removes velocity/turn pairs while preserving the underlying behavioural distribution, then compares labels with the full dataset.Removing trajectory locations would change velocity and turn values because they depend on sampling intervals.Source: §3.2 · p. 10
  • To test sampling-heterogeneity inaccuracy, the analysis jitters points in proportion to their time gaps and compares labels with and without the reliability function.The authors state that greater uncertainty reduces a value's influence on the final clustering, and that the approach could also apply to geopositioning errors.Source: §3.2 · pp. 10–11

4 Results

The evaluation used synthetic trajectories and empirical animal-movement datasets spanning tracking technologies and sampling heterogeneity. Results covered clustering performance, behavioral interpretation, and robustness to data loss and inaccuracy.

4.1 Simulated trajectories

  • Performance exceeded 90% for n ≥200 and was around 80% for n ≤100, with EMbC performing better when clusters or datasets carried less information.Performance was sensitive to cluster mixture γ and dataset size n.Source: §4.1 · pp. 11–12
  • On Markov-chain trajectories, HMM led for well-mixed clusters while EMbC beat it for well-defined clusters at n ≥200; on mixture-prior data, EMbC and EMC were similar and HMM performed worse.HMM benefited when state sequences were well-defined by transition structure; mixture-prior trajectories instead favored the clustering procedures.Source: §4.1 · pp. 11–12
  • EMbC directly yields binary partitions with high stability and the lowest RMSE, whereas EMC and HMM are starting-condition-sensitive and do not guarantee binary output.For EMC and HMM, multiple runs with different starting seeds may be needed to check whether the output is binary.Source: §4.1 · p. 12

4.2 Empirical trajectories

  • Shearwater and Osprey data showed similar velocity/turn layouts across ecological contexts and sampling resolutions, but LL and HL proportions differed and HH interpretation varied.LL/HL proportions were 37%/13% for shearwater and 18%/30% for Osprey.Source: §4.2 · p. 12
  • For the shearwater, HH points suggested foraging and relocation submodes, but the likelihood payoff prevented the algorithm from reaching a proposed three-cluster classification.The Osprey's HH cluster was homogeneous and corresponded to long relocations within stopover areas.Source: §4.2 · p. 12
  • In the bat trajectory, smoothing left intermittent LL labels that may represent short transient behavior; expert labels aligned reasonably with EMbC, though roosting was poorly defined by velocity and turn.The authors leave decisions about retaining or smoothing such intermittent states to expert judgment.Source: §4.2 · p. 13
  • Population-level nematode clustering used straightness, velocity, and net displacement; its limited eight-cluster set favored generic behaviors, while individual cluster recovery revealed behavioral variability.The resulting semantics concerned looping or local-search intensity and the individual's tendency to move elsewhere.Source: §4.2 · p. 13

4.3 Robustness to data loss and data inaccuracy

  • Data-loss robustness increased with dataset size but depended on cluster-frequency representation, while reliability weighting especially improved inaccuracy robustness under heterogeneous or fixed sampling.Pre-assigned GPS schedules can bias behavior sampling and thereby condition both labeling and robustness to data loss.Source: §4.3 · pp. 13–14

5 Discussion

The discussion frames EMbC as a simple, interpretable binary clustering approach for movement annotation, useful under specific distributional and temporal assumptions. Its applicability spans variables, species, and tracking methods, while the authors caution that labels and temporal coherence depend on inputs and analytic choices.

Motivation

  • Trajectory segmentation is presented as essential to studying movement mechanisms and organisms’ interactions with their environment.The discussion connects segmentation to mechanistic ecological spatio-temporal analyses.Source: §5 · p. 14

Algorithm design

  • Delimiter-bounded means give clusters LL, HL, LH, or HH semantics, while unbounded covariances retain variable correlations and the binary scheme caps clusters at 2^m.This avoids an a priori choice of cluster count in the n-dimensional space.Source: §5 · p. 14

Reliability

  • Greater input uncertainty reduces a data point’s leverage; this work models sampling-interval uncertainty, while device measurement error is omitted for simplicity.The multivariate method can accommodate other movement or behavioural variables and their error sources.Source: §5 · p. 15

Use and comparison

  • EMbC is particularly useful when input features are somewhat bimodal, binary partitions are informative, and temporal dynamics cannot be assumed to follow a Markov chain.The authors report similar performance to EMC without multiple restarts or initial parametrization.Source: §5 · p. 15

Empirical scope

  • Across empirical datasets, EMbC behaves reasonably across species, ecological contexts, and tracking technologies, and pooled trajectories can define average modes for visualization on individuals.Different scatter-plot layouts can reflect input distributions, mixture priors, and behaviours along trajectories.Source: §5 · p. 15

Interpretation

  • Behavioural match depends more on how much the input variables convey about behaviours than on the behaviours’ relative proportions or durations.Velocity and turn are used here, but other adequately correlated behavioural or physiological variables are possible; semantics remain variable- and species-specific.Source: §5 · pp. 15–16

Scale and limitations

  • EMbC is proposed for fine-scale segmentation because coarse-scale labels may appear discontinuous or seem meaningless to experts; optional smoothing can incorporate label weights and temporal dependencies.Coarse-graining and population-level analysis can affect estimated state numbers and durations, so interpretation depends on expert criteria and study goals.Source: §5 · p. 16

Implementation

  • The released EMbC R package includes clustering statistics, plots, smoothing, and trajectory visualization functions, and is compatible with the Move R package.Source: §5 · p. 16

Tables

Table 2 lists empirical datasets; the accompanying text specifies how dataset size and sampling intervals are reported.

Tables

  • Table 2 covers empirical datasets, with fixes denoting total locations and τ̂ denoting the mean interval between fixes in seconds.Source: Tables · p. 22, Table 2 · p. 22

Figures

The figures illustrate EMbC’s delimiter-based cluster semantics and computations, its robustness-test procedures, and performance and behavioural-annotation examples across synthetic and empirical trajectories.

Figure 1

  • For the same trajectory and initialization, Figure 1 contrasts EMC’s hard-to-interpret clusters with EMbC’s delimiter-bounded centroids and clearer L/H semantics.Cluster assignments can still differ from binary regions because points are assigned by weights.Source: Figure 1 · p. 24

Figures 2–3

  • Figure 2 pairs adjacent-cluster mean lines with likelihood-difference contours; each delimiter crosses its mean line at the point of minimum likelihood difference.Figure 3 shows overlapping and non-overlapping delimiters, with some points contributing to multiple cluster means.Source: Figures · pp. 25–26, Figure 2 · p. 25, Figure 3 · p. 26

Figure 4

  • Figure 4 contrasts data-loss subsampling with uncertainty-based jittering, showing missing observations versus perturbed values.The example uses kdl = 0.2 for data loss and kdi = 0.05 for jittering.Source: Figure 4 · p. 27

Figure 5

  • Figure 5 compares EMbC, EMC, and HMM across synthetic trajectory sizes and sampling schemes using F-measure.Its panels distinguish Markov-chain-based sampling from prior-based sampling.Source: Figure 5 · p. 28, Figures · p. 28

Figure 6

  • Figure 6 presents a simulated trajectory (N = 400, γ = 0.05), with reference and output labels, their differences, velocity/turn delimiters, frequency distributions, and a confusion matrix with performance measures.Source: Figure 6 · p. 29

Figures 7–10

  • Figures 7–10 visualize annotated animal trajectories and behavioural profiles across shearwater, osprey, bat, and nematode examples.The nematode figure pools six trajectories for population-level clustering and displays the results on individual trajectories.Source: Figure 7 · p. 30, Figure 8 · p. 31, Figure 9 · p. 32

Figure 11

  • Figure 11 reports average F-measure over 10 runs across data-loss and jittering ranges.Source: Figure 11 · p. 34
Loading 1503.04059v2…