# Directed Clustering of Multivariate Data Based on Linear or Quadratic Latent Variable Models
###### Abstract  
We consider situations in which the clustering of some multivariate data is desired, which establishes an ordering of the clusters with respect to an underlying latent variable. As our motivating example for a situation where such a technique is desirable, we consider scatterplots of traffic flow and speed, where a pattern of consecutive clusters can be thought to be linked by a latent variable, which is interpretable as traffic density. We focus on latent structures of linear or quadratic shapes, and present an estimation methodology based on expectation-maximization, which estimates both the latent subspace and the clusters along it. The directed clustering approach is summarized in two algorithms and applied to the traffic example outlined. Connections to related methodology, including principal curves, are briefly drawn. clustering; mixture model; latent variable model; dimension reduction; expectation-maximization algorithm; model selection; fundamental diagram +
Footnote †: journal:  
0000-0001-123-08  
the clusters in relation to each other based on their location within the data space. This is a possible drawback, especially in situations where the relative positioning of the cluster centers (and, hence, of the clusters) is meaningful as it can be considered as being driven by an external variable, which may or may not be observed. Specifically, in many situations, one may argue that the cluster centers are just particular realizations of a latent variable spanning the data space, with the observations essentially constituting multivariate 'noise' around these centers. Such scenarios are particularly prone to occur when the relationship between the variables in question is governed by some physical equation or property. An example of such a situation is the measurement of speed and flow on highways, sometimes referred to as the 'fundamental diagram', where the underlying latent variable can be thought to represent the traffic density. Although the next section is dedicated to detailing this particular application, the reader may wish to glance at Figure 1 at this point to gain some intuition. When clustering this data, the order of the clusters along the 'curved direction' taken by the data cloud is clearly meaningful: there is much more information in the data than would be captured by an unordered list of cluster centers. To define the terms more formally, assume the given data \(x_{i}\in\mathbb{R}^{m}\), \(i=1,\ldots,n\). We consider _clustering_ as an algorithmic process that takes the data \(\{x_{i}\}_{1\leq i\leq n}\) as input, and produces a set of cluster centers, say \(c_{1},\ldots,c_{K}\in\mathbb{R}^{m}\), with _cluster labels_\(1,2,\ldots,K\) as output, where observations \(x_{i}\) are then assigned according to a clustering rule \(\hat{k}(x_{i})\) with values in \(1,\ldots,K\). It is important to realize that, in conventional clustering, it is generally _not_ meaningful to establish an ordering relation on the cluster labels; that is, one cannot say that cluster 2 is 'larger' than cluster 1 in any meaningful way. The reason is that any such ordering would be based on the relative positioning of the centers \(c_{k}\) in the \(m\)-variate space, but these will not allow for obvious ordering unless \(m=1\). Since this paper is concerned with multivariate clustering, we are only interested in the case where \(m>1\). We define a _directed clustering_ algorithm as a clustering process in which the ordinal relationship of the resulting cluster labels is well-defined; that is, one can say that cluster \(k+1\) is larger (or smaller) than cluster \(k\) in a meaningful way. In order to include directional information in the clustering process, one needs to connect the clustering problem with the concept of a latent variable. The idea is to assume the existence of such a latent variable, which parameterizes a curve through \(m\)-variate space, passing through \(c_{1},c_{2},...,c_{K}\).