Synergistic neighborhood relationships with travel behavior: An analysis of travel in 30,000 US neighborhoods

<jats:p>A now substantial body of literature finds that land use and urban form have a statistically significant, albeit relatively modest, effect on travel behavior. Some scholars have suggested that various built-environment characteristics influence travel more in concert than when considered in isolation. Yet few previous studies have combined built-environment measures to create holistic descriptions of the overall character of neighborhoods, and fewer still have related these neighborhoods to residents’ travel decisions. To address this gap in the literature, we develop a typology of seven distinct neighborhood types by applying factor analysis and then cluster analysis to a set of 20 variables describing built-environment characteristics for most census tracts in the United States. We then include these neighborhood types in a set of multivariate regression models to estimate the effect of neighborhood type on the travel behavior of neighborhood residents, controlling for an array of personal and household characteristics. We find relatively little variation in the number of daily trips among neighborhood types, but there is substantial neighborhood variation in both person miles of travel and mode choice. Travel by residents of one particular neighborhood type is notably distinguished from all others by a very low number of miles traveled, little solo driving, and high transit use. However, this neighborhood type is found almost exclusively in just a few very large metropolitan areas, and its replicability is uncertain.</jats:p>

section_content: Let us denote by A the data matrix: each row is an observation O i corresponding to an individual and each column represents a variable observed for all the individuals. 

There are N observations and p variables. The size of matrix A is N × p. 

The data are assumed to be partitioned in K groups (or clusters). Let us denote by P the vector representing a partition of the data: it is an integer vector with values between 1 and K. The size of P is equal to the number N of observations. For each index i (1 ≤ i ≤ N ), the coordinate P i is equal to the number k (1 ≤ k ≤ K) of the cluster the observation O i belongs to. 

The cluster C k can be represented by a submatrix A {k} of matrix A made of the rows of A whose index i is such that P i = k. If n k denotes the cardinal of C k, the matrix A {k} has size n k × p and one has the relation k n k = N. Let us denote by I k the set of the indices of the observations belonging to the cluster C k :

The matrix A {k} can also be denoted formally as A {I k }. 

Let us denote by µ {k} the barycenter of the observations in the cluster C k and by µ the barycenter of all the observations. µ {k} and µ are row-vectors with length p: they are the means of the rows of the matrices A {k} and A respectively:

where x i designates the row of index i in A.
section_name: Internal clustering criteria 1.Algebraic background and notations

section_content: Each column vector V j (1 ≤ j ≤ p) of the matrix A can be interpreted as a sample of size N of the j-th observed variable. Let us center each of these vectors with respect to its mean by setting v j = V j -µ j. If X is the matrix formed by the centered vectors v j, the scatter matrix T is the matrix defined by

The general term of T is:

The matrix T is equal to N times the variance-covariance matrix of the family of column vectors (V 1,. . ., V p ). The general term of T can thus also be written as

In particular, the diagonal terms are N times the variances of the vectors V i :

One can also write:

where, by a slight abuse of notation, µ i and µ j are here identified with the vectors µ i 1 and µ j 1 respectively. The scatter matrix is a square symmetric matrix of size p × p. As it is of the form t X X, the quadratic form it represents is positive semi-definite. Indeed, if one takes any vector v in R p :

In particular, the eigenvalues and the determinant of the scatter matrix are also greater than or equal to 0. If N > p and if the matrix X has maximal rank p, the form is in fact positive definite. The total scattering TSS (total sum of squares) is the trace of the matrix T :

Geometric interpretation: let us denote by M 1,. . ., M N the points of the space R p representing all the observations: the coordinates of M i are the coefficients of the i-th row of the data matrix A. Similarly, let us denote by G the barycenter of these points: its coordinates are the coefficients of the vector µ. One can easily prove the following relations:

It means that the trace of T, in other words the total scattering TSS, is equal to the scattering (sum of the squared distances) of the points around the barycenter. The second equality shows that this quantity is also the sum of the distances between all the pairs of points, divided by N.
section_name: Total dispersion

section_content: There are similar definitions for the different clusters C k : each column vector V {k} j of the matrix A {k} represents a sample of size n k of the j-th observed variable. 

For each cluster C k, one defines the within-group scatter matrix (abbreviated as WG). If µ {k} designates the barycenter of the observations in cluster k and X {k} is the matrix formed by the centered vectors v {k} j = V {k} j -µ {k} j, the within-group scatter matrix is defined by the following relation:

and its general term is defined as:

In terms of variance and covariance, by analogy with the relations (4) and ( 5 ), the coefficients of the matrix W G {k} can also be written as:

The matrices W G {k} are square symmetric matrices of size p × p. Let us denote by W G their sum for all the clusters:

As was the case with the matrix T seen in section 1. 1. 1, the matrices W G {k} represent a positive semi-definite quadratic form Q k and, in particular, their eigenvalues and their determinant are greater than or equal to 0. 

The within-cluster dispersion, noted W GSS {k} or W GSS k, is the trace of the scatter matrix W G {k} :

The within-cluster dispersion is the sum of the squared distances between the observations M {k} i and the barycenter G {k} of the cluster. Finally the pooled within-cluster sum of squares WGSS is the sum of the withincluster dispersions for all the clusters:

The abovementioned geometric interpretation remains true at the level of each group: in each cluster C k, the sum of the squared distances from the points of the cluster to their barycenter is also the sum of the squared distances between all the pairs of points in the cluster, divided par n k. In other words:

Inverting the formula, one gets:
section_name: Within-group scatter

section_content: The between-group dispersion measures the dispersion of the clusters between each other. Precisely it is defined as the dispersion of the barycenters G {k} of each cluster with respect to the barycenter G of the whole set of data. 

Let us denote by B the matrix formed in rows by the vectors µ {k} -µ, each one being reproduced n k times (1 ≤ k ≤ K). The between-group scatter matrix is the matrix

The general term of this matrix is:

The between-group dispersion BGSS is the trace of this matrix:

Geometrically, this sum is the weighted sum of the squared distances between the G {k} and G, the weight being the number n k of elements in the cluster C k :

(23)
section_name: Between-group scatter

section_content: The observations (rows of the matrix A) can be represented by points in the space R p. Several quality indices defined in section 1. 2 consider the distances between these points. One is led to distinguish between pairs made of points belonging to the same cluster and pairs made of points belonging to different clusters. 

In the cluster C k, there are n k (n k -1)/2 pairs of distinct points (the order of the points does not matter). Let us denote by N W the total number of such pairs:

The total number of pairs of distinct points in the data set is

Since N = K k=1 n k, one can write :

Let us denote by N B the number of pairs constituted of points which do not belong to the same cluster, one has N T = N W + N B and consequently:

In the remainder, I B will denote the set of the N B pairs of between-cluster indices and I W the set of the N W pairs of within-cluster indices.
section_name: Pairs of points

section_content: The following sections provide the precise definitions of the various internal quality indices which have been proposed by various authors in order to determine an optimal clustering. They are sorted in alphabetical order. These indices, also called quality indices, are all denoted by the same letter C. Let us also denote by d the distance function between two points (usually the ordinary euclidean distance). 

Table 1 summarizes the existing indices, their name in the package clusterCrit for R, the bibliographic reference and the date of the article where they were originally defined.
section_name: Internal indices

section_content: The mean dispersion of a cluster is the mean of the squared distances of the points of the cluster with respect to their barycenter. The Ball-Hall index is the mean, through all the clusters, of their mean dispersion:

In the particular case where all the clusters have the same size N/K, this sum reduces to

log(BGSS/W GSS) Log_SS_Ratio [14] McClain-Rao McClain_Rao [17] PBM PBM [19] Point biserial Point_biserial [18] Ratkowsky-Lance Ratkowsky_Lance [21] Ray-Turi Ray_Turi [22] Scott-Symons Scott_Symons [24] SD SD_Scat [13] SD SD_Dis [13] S_Dbw S_Dbw [12] Silhouette Silhouette [20] Tr(W ) Trace_W [8] Tr(W -1 B) Trace_WiB [10] Wemmert-Gançarski Wemmert_Gancarski Xie-Beni Xie_Beni [25] Table 1 : Index names in the package clusterCrit for R and bibliographic references.
section_name: The Ball-Hall index

section_content: This index is the weighted sum of the logarithms of the traces of the variance-covariance matrix of each cluster. The index can be written like this:

The quantity Tr(W G {k} )/n k can be interpreted, after equation (15), as the mean of the squared distances between the points in cluster C k and their barycenter G {k}. If a cluster contains a single point, this trace is equal to 0 and the logarithm is undefined.
section_name: The Banfeld-Raftery index

section_content: Let us consider the distances between the pairs of points inside each cluster. The numbers N W and N T have been defined in section 1. 1. 4. One computes the following three quantities:

• S W is the sum of the N W distances between all the pairs of points inside each cluster ;

• S min is the sum of the N W smallest distances between all the pairs of points in the entire data set. There are N T such pairs (see section 1. 1. 4): one takes the sum of the N W smallest values ;

• S max is the sum of the N W largest distances between all the pairs of points in the entire data set. There are N T such pairs: one takes the sum of the N W largest values. 

The C index is defined like this:

If one considers the N T distances between pairs of points as a sequence of values sorted in increasing order, the C index uses the N W smallest values and the N W largest values in order to compute the sums S min and S max : the sum S involves the N W distances in this sequence which correspond to pairs present in some cluster (that is to say pairs whose two points are in a same cluster). No more than 3N W distances are effectively retained in the calculation of this index.
section_name: The C index

section_content: Using the notations of equations ( 16 ) and ( 23 ), the Calinski-Harabasz index is defined like this:
section_name: The Calinski-Harabasz index

section_content: Let us denote by δ k the mean distance of the points belonging to cluster C k to their barycenter G {k} :

Let us also denote by

One computes, for each cluster k, the maximum M k of the quotients

The Davies-Bouldin index is the mean value, among all the clusters, of the quantities M k :
section_name: The Davies-Bouldin index

section_content: The Det_Ratio index is defined like this:

T designates the total scatter matrix defined in section 1. 1. 1. This is the sum of matrices BG and W G defined in equations ( 14 ) and (20).
section_name: The Det_Ratio index

section_content: Let us denote by d min the minimal distance between points of different clusters and d max the largest within-cluster distance. 

The distance between clusters C k and C k ′ is measured by the distance between their closest points:

and d min is the smallest of these distances d kk ′ :

For each cluster C k, let us denote by D k the largest distance separating two distinct points in the cluster (sometimes called the diameter of the cluster):

Then d max is the largest of these distances D k :

The Dunn index is defined as the quotient of d min and d max :
section_name: The Dunn index

section_content: The Gamma index of Baker-Hubert is an adaptation, in the context of clustering, of the index Γ of correlation between two vectors of data A and B with the same size. Generally, for two indices i and j such that a i < a j, one says that the two vectors are concordant if b i < b j, in other words, if the values classify in the same order in both vectors. One calculates the number s + of concordant pairs {i, j} and the number s - of discordant pairs. Note that the inequalities are strict, meaning that ties are dropped. 

In this context, the Γ index is classically defined like this (see [11] ):

Its value is between -1 and 1. 

In the context of a partition, the first vector A is chosen to be the set of distances d ij between pairs of points {M i, M j } (with i < j). The second vector B is a binary vector: in this vector, the coordinate corresponding to a pair {M i, M j } has value 0 if the two points lie in the same cluster and 1 otherwise. These two vectors have length

The number s + represents the number of times a distance between two points which belong to the same cluster (that is to say a pair for which the value of vector B is 0) is strictly smaller than the distance between two points not belonging to the same cluster (that is to say a pair for which the value of vector B is 1). The number s -represents the number of times the opposite situation occurs, that is to say that a distance between two points lying in the same cluster (value 0 in B) is strictly greater than a distance between two points not belonging to the same cluster (value 1 in B). The cases where there is equality (ties or ex-aequos) are not taken into account. As defined in section 1. 1. 4, there are N B between-cluster distances and, for each of them, one compares with the N W within-cluster distances: one finally performs N B × N W comparisons. 

One can write the numbers s + and s -in the following form:

Their difference is:

1. 2. 9 The GDI index

The GDI indices are generalisations of the Dunn index seen in section 1. 2. 7 (GDI is the abbreviation of Generalized Dunn's Indices). They use different quantities in order to evaluate the between-clusters and within-groups distances. 

Let us denote by the letter δ a measure of the between-cluster distance and by ∆ a measure of the within-cluster distance (which is also called the diameter of the cluster). The GDI index, relatively to these distances, is defined like this:

Six different definitions of δ (denoted as δ 1 through δ 6 ) and three definitions of ∆ (denoted as ∆ 1 through ∆ 3 ) have been suggested. This leads to 18 different indices denoted as C uv : here u is an integer designating the between-clusters distance (1 ≤ u ≤ 6) and v an integer designating the within-groups distance (1 ≤ v ≤ 3). 

The definitions of the within-cluster distances ∆ are:

Here d is the euclidean distance. The facteur 2 in the definition of ∆ 3 allows us to interpret the value as a diameter rather than a radius. The definitions of the between-cluster distances δ are:

The first four distances (δ 1 to δ 4 ) occur in ascendant clustering algorithms and are called single linkage, complete linkage, average linkage, centroid linkage respectively. The measure δ 5 is the weighted mean (with weights n k and n k ′ ) of the mean distances between the points in clusters C k and C k ′ and their respective barycenter. The measure δ 6 is the Hausdorff distance D H.
section_name: The Baker-Hubert Gamma index

section_content: Using the same notations as for the Baker-Hubert Γ index seen in section 1. 2. 8, the G+ index is defined like this:

This is the proportion of discordant pairs among all the pairs of distinct points.
section_name: The G_plus index

section_content: The Ksq_DetW index (also denoted as k 2 |W |) is defined like this:

where W G is defined as in equation ( 14 ).
section_name: The Ksq_DetW index

section_content: The Log_Det_Ratio index is defined like this:

where T is the scatter matrix defined in section 1. 1. 1 and W G is defined by equation (14). This is a logarithmic variant of the Det_Ratio index seen in section.
section_name: The Log_Det_Ratio index

section_content: The Log_SS_Ratio index is defined like this:

where BGSS and W GSS are defined by equations ( 23 ) and ( 16 ) respectively: they are the traces of the BG and W G matrices respectively.
section_name: The Log_SS_Ratio index

section_content: As for the C index seen in section 1. 2. 3, let us denote by S W the sum of the withincluster distances:

Recall that the total number of distances between pairs of points belonging to a same cluster is N W. Let us denote by S B the sum of the between-cluster distances:

The total number of distances between pairs of points which do not belong to the same cluster is

The McClain-Rao index is defined as the quotient between the mean within-cluster and between-cluster distances:
section_name: The McClain-Rao index

section_content: The PBM index (acronym constituted of the initals of the names of its authors, Pakhira, Bandyopadhyay and Maulik) is calculated using the distances between the points and their barycenters and the distances between the barycenters themselves. 

Let us denote by D B the largest distance between two cluster barycenters:

On the other hand, let us denote by E W the sum of the distances of the points of each cluster to their barycenter and E T the sum of the distances of all the points to the barycenter G of the entire data set:

The PBM index is defined like this:

E T is a constant which does not depend on the partition, nor on the number of clusters.
section_name: The PBM index

section_content: Generally speaking, in statistics, the point-biserial coefficient is a correlation measure between a continuous variable A and a binary variable B (i-e a variable whose values are 0 or 1). A and B are sets with the same length n. 

The values of A are dispatched into two groups A 0 and A 1 depending on the corresponding value in B being 0 or 1. 

Let us denote by M A0 and M A1 the means in A 0 and A 1, and n A0 and n A1 the number of elements in each group. The point-biserial correlation coefficient is defined as the quantity:

where s n is the standard deviation of A. 

In the context of a comparison between different clusterings, the term s n may be omitted because it does not depend on the partitions but only on the set of data. 

As in the case of the Γ index seen in section 1. 2. 8, one adapts this definition by choosing A to be the set of the N T distances between pairs of points M i and M j. The corresponding value in B is 1 if the two points lie in the same cluster and 0 otherwise:

M A1 is the mean of all the within-cluster distances and M A0 is the mean of all the between-cluster distances. 

Using the notations introduced in section 1. 2. 14, the definition of the point-biserial index is :

1. 2. 17 The Ratkowsky-Lance index

One computes the mean R of the quotients between BGSS and TSS for each dimension of the data, that is to say for each column of the matrix A. 

Let us denote

Then

BGSS j is in fact the j-th diagonal term of the matrix BG defined by equation (20). The Ratkowsky_Lance index (c/ √ K) is defined like this:
section_name: The Point-Biserial index

section_content: The Ray-Turi index is defined as a quotient:

• the numerator is the mean of the squared distances of all the points with respect to the barycenter of the cluster they belong to:

• the denominator is the minimum of the squared distances ∆ kk ′ between all the cluster barycenters:

So the Ray-Turi index can be written like this:
section_name: The Ray-Turi index

section_content: This index is the weighted sum of the logarithms of the determinants of the variancecovariance matrix of each cluster. 

It can be written like this:

The determinants of the matrices W G {k} are greater than or equal to 0 because these matrices are positive semi-definite. If one of them is equal to 0, the index is undefined.
section_name: The Scott-Symons index

section_content: One defines two quantities S and D called respectively the average scattering for clusters and the total separation between clusters. 

The average scattering for the clusters, noted S, is defined as follows. Let us consider the vector of variances for each variable in the data set. It is a vector V of size p defined by:

Similarly, one defines variance vectors V {k} for each cluster C k :

The quantity S is the mean of the norms of the vectors V {k} divided by the norm of vector V:

On the other hand, the total separation between clusters, noted D, is defined as follows. Let us denote by D max and D min respectively the largest and the smallest distance between the barycenters of the clusters:

Let us denote

The SD index is finally defined like this:

where α is a weight equal to the value of D obtained for the partition with the greatest number of clusters. In order to compare several partitions of the data, one must first calculate the value of D corresponding to the greatest number of clusters in order to find the value of the coefficient α and then calculate the other indices based on this coefficient.
section_name: The SD index

section_content: This index relies on the notion of density of points belonging to two clusters. One first defines a limit value σ equal to the square root of the sum of the norms of the variance vectors V {k} (introduced in section 1. 2. 20) divided by the number of clusters:

The density γ kk ′ for a given point, relative to two clusters C k and C k ′, is equal to the number of points in these two clusters whose distance to this point is less than σ. Geometrically, this amounts to considering the ball with radius σ centered at the given point and counting the number of points of C k ∪ C k ′ located in this ball. 

For each pair of clusters, let us evaluate the densities for the barycenters G {k} and G {k ′ } of the clusters and for their midpoint H kk ′. One forms the quotient R kk ′ between the density at the midpoint and the largest density at the two barycenters:

On the other hand, one defines a between-cluster density G as the mean of the quotients R kk ′ :

The S-Dbw index is defined as the sum of the mean dispersion in the clusters S (defined in section 1. 2. 20) and of the between-cluster density G:
section_name: The S_Dbw index

section_content: Let us consider, for each point M i, its mean distance to each cluster. One defines the within-cluster mean distance a(i) as the mean distance of point M i to the other points of the cluster it belongs to: if M i ∈ C k, we thus have

On the other hand, let us evaluate the mean distance d(M i, C k ′ ) of M i to the points of each of the other clusters C k ′ :

Let us also denote by b(i) the smallest of these mean distances:

The value k ′ which realizes this minimum indicates the best choice for reaffecting, if necessary, the point M i to another cluster than the one it currently belongs to. 

For each point M i, one then forms the quotient

which is called the silhouette width of the point. It is a quantity between -1 and 1: a value near 1 indicates that the point M i is affected to the right cluster whereas a value near -1 indicates that the point should be affected to another cluster. The mean of the silhouette widths for a given cluster C k is called the cluster mean silhouette and is denoted as s k :

Finally, the global silhouette index is the mean of the mean silhouettes through all the clusters:
section_name: The Silhouette index

section_content: Using the same notations as for the Gamma index in section 1. 2. 8, the τ index of Kendall between two vectors of data of length N T is classically defined in statistics as the quantity:

The numbers s + and s -do not count ties, so if a between-cluster distance and a within-cluster distance are equal, they do not enter in the numerator. In order to take ties into account, one modifies the denominator and defines the corrected index τ c like this:

with

where t i is the number of values in the i-th group of ties for the vector A and u j is the number of values in the j-th group of ties for the vector B. Here the vector B is constituted only of values 0 and 1 (corresponding to the between-cluster and withincluster pairs respectively) and we thus have:

An easy calculation shows that ν 0 -

If one makes the reasonable hypothesis that the vector A contains few identical values, one can estimate that ν 2 is negligible with respect to ν 0. This justifies the following definition of the Tau index of clustering:

(101)
section_name: The Tau index

section_content: The Trace_W index is defined like this:

where W G and W GSS are defined by equations ( 14 ) and ( 16 ) respectively.
section_name: The Trace_W index

section_content: The Trace_WiB (or Trace_W -1 B) index is defined like this:

where W G and BG are defined by equations ( 14 ) and ( 20 ) respectively.
section_name: The Trace_WiB index

section_content: The Wemmert-Gançarski index is built using quotients of distances between the points and the barycenters of all the clusters. For a point M belonging to cluster C k, one forms the quotient R(M ) between the distance of this point to the barycenter of the cluster it belongs to and the smallest distance of this point to the barycenters of all the other clusters:

One then takes the mean of these quotients in each cluster. If this mean is greater than 1, it is ignored, otherwise one takes its complement to 1. Precisely, let us define:

The Wemmert-Gançarski index is defined as the weighted mean, for all the clusters, of the quantities J k like this:

This expression can be rewritten as follows:
section_name: The Wemmert-Gançarski index

section_content: The Xie-Beni index is an index of fuzzy clustering, but it is also applicable to crisp clustering. 

It is defined as the quotient between the mean quadratic error and the minimum of the minimal squared distances between the points in the clusters. 

The mean quadratic error, in the case of a crisp clustering, is simply the quantity 1 N W GSS, in other words the mean of the squared distances of all the points with respect to the barycenter of the cluster they belong to. 

Using the same notation as in section 1. 2. 9, one has

and the Xie-Beni index can be written like this:
section_name: The Xie-Beni index

section_content: In order to find the best partition of the data, one usually executes a clustering algorithm with different values of the expected number of clusters K: let us say that K m ≤ K ≤ K M. The clustering algorithm which is applied could be an ascending hierarchical clustering (AHC) or the k-means algorithm or any other technique. One then computes a quality index Q K for each value of K and selects the partition which led to the "best" value for Q K. This section explains what is considered the "best" value for the different quality indices. 

Table 2 summarizes, for each index, which rule must be applied in order to determine the best index value. For instance, in the case of the Calinski-Harabasz index, if the quality index has been computed for different partitions of the data, the best partition is the one corresponding to the greatest value of the index. The decision rules called max and min in table 2 mean that one should select respectively the greatest or the smallest index value.
section_name: Choice of the best partition

section_content: The decision rule called max diff means that the best value for K is the one corresponding to the greatest difference between two successive slopes. On a diagram representing the index values against the number of selected clusters, this corresponds to an elbow. More precisely, let us denote V i = Q i+1 -Q i the slope between to successive points of the diagram. Then K is defined by:

This is better explained on the following graphic. The figure on the right displays the values of the Hall_Ball index corresponding to different clusterings of the data represented by the figure on the left. The index has been computed with tentative partitions made of 2 to 7 clusters. The figure exhibits an elbow for the four-clusters partition and indeed the data clearly belong to four distinct groups. The external indices of comparison are indices designed to measure the similitude between two partitions. They take into account only the distribution of the points in the different clusters and do not allow to measure the quality of this distribution.
section_name: Index

section_content: All the suggested indices rely on a confusion matrix representing the count of pairs of points depending on whether they are considered as belonging to the same cluster or not according to partition P 1 or to partition P 2. There are thus four possibilities:

• the two points belong to the same cluster, according to both P 1 and P 2

• the two points belong to the same cluster according to P 1 but not to P 2

• the two points belong to the same cluster acording to P 2 but not to P 1

• the two points do not belong to the same cluster, according to both P 1 and P 2. 

Let us denote by yy, yn, ny, nn (y means yes, and n means no) the number of points belonging to these four categories respectively. N T being the total number of pairs of points, one has:
section_name: Notation

section_content: If partition P 1 is used as a reference, one defines the precision coefficient as the proportion of points rightly grouped together in P 2, that is to say which are also grouped together according to the reference partition P 1. Among the yy + ny points grouped together according to P 2, yy are rightly grouped. One thus has:

Similarly, one defines the recall coefficient as the proportion of points grouped together in P 1 which are also grouped together in partition P 2. This is the proportion of points which are supposed to be grouped together according to the reference partition P 1 and which are effectively marked as such by partition P 2. Among the yy+yn points grouped together in P 1, yy are also grouped together in P 2. One thus has:

In terms of conditional probabilities, one can write

where the events gp 1 and gp 2 mean that two points are grouped together in P 1 and in P 2 respectively. The F-measure is the harmonic mean of the precision and recall coefficients:

There is also a weighted version of this measure, called the F α -measure, defined like this:
section_name: Precision and recall coefficients

section_content: Let us associate to each partition P a (a = 1, 2) the binary random variable X a defined on the set of indices i and j such that i < j as follows: its value is 1 if the points M i and M j are classified in the same cluster than in partition P a and 0 otherwise. The variable X a works as an indicator variable. 

There are N T pairs of points and one is interested only in the indices i and j such that i < j. Let us consider the mean and the standard deviation of X a :

The following formulas establish a link between these random variables and the concordant and discordant count variables:

From this we get:
section_name: Indicator variables

section_content: The following sections give the definition of several (more or less) widely used external indices.
section_name: External indices definition

section_content: The Czekanowski-Dice index (aka the Ochiai index) is defined like this:

This index is the harmonic mean of the precision and recall coefficients, that is to say it is identical to the F-measure defined in section 2. 2:
section_name: The Czekanowski-Dice index

section_content: The Folkes-Mallows index is defined like this:

This index is the geometric mean of the precision and recall coefficients:
section_name: The Folkes-Mallows index

section_content: The index of Hubert Γ is the correlation coefficient of the indicator variables introduced in section 2. 3. It is defined like this:

Comparing with equation ( 136 ), the index of Hubert Γ appears as a standardized variant (centered and reduced) of the Russel-Rao index defined in section 2. 4. 10. Its value is between -1 and 1. 

Using the relations of section 2. 3, one may write the Γ index as follows:
section_name: The Hubert Γ index

section_content: The Jaccard index is defined like this:
section_name: The Jaccard index

section_content: The Kulczynski index is defined like this:

This index is the arithmetic mean of the precision and recall coefficients:
section_name: The Kulczynski index

section_content: The McNemar index is defined like this:

Under the null hypothesis H 0 that the discordances between the partitions P 1 and P 2 are random, the index C follows approximatively a normal distribution. It is an adaptation of the non-parametric test of McNemar for the comparison of frequencies between two paired samples: the statistic of McNemar's test (called the χ 2 distance) is the square of the index

(yn -ny) 2 yn + ny and follows, under the null hypothesis of marginal homogeneity of the contingency table, a χ 2 distribution with 1 degree of freedom.
section_name: The McNemar index

section_content: The Phi index is a classical measure of the correlation between two dichotomic variables. It is defined like this: C = yy × nn -yn × ny (yy + yn) (yy + ny) (yn + nn) (ny + nn) (132)
section_name: The Phi index

section_content: The Rand index is defined like this:

2. 4. 9 The Rogers-Tanimoto index

The Rogers-Tanimoto index is defined like this:
section_name: The Rand index

section_content: The Russel-Rao index measures the proportion of concordances between the two partitions. It is defined like this:

Using the notations introduced in section 2. 3, this index can be written:
section_name: The Russel-Rao index

section_content: There are two versions of the Sokal-Sneath index. They are defined respectively like this:

C 1 = yy yy + 2(yn + ny)

3 Usage of the clusterCrit package

The clusterCrit package for R provides an implementation of all the indices described in the preceding sections. The core of the package is written in Fortran and is optimized in order to avoid duplicate calculations. It can be installed from the R console with the following instruction:
section_name: The Sokal-Sneath indices

section_content: Once it is installed, it can be loaded in an R session with the following instruction: load(clusterCrit)
section_name: install.packages(clusterCrit)

section_content: The clusterCrit package defines several functions which let you compute internal quality indices or external comparison indices. The partitions are specified as an integer vector giving the index of the cluster each observation belongs to. The possible values are integers between 1 and K, where K is the number of clusters. 

The intCriteria function calculates one or several internal quality indices. Its syntax is:

The traj argument is the matrix of observations (aka as trajectories). The part argument is the partition vector. The crit argument is a list containing the names of the indices to compute. One can use the keyword "all" in order to compute all the available indices. See the getCriteriaNames function to see the names of the currently available indices. All the names are case insensitive and can be abbreviated as long as the abbreviation remains unambiguous. 

The extCriteria function calculates one or several external indices (including the precision and recall coefficients). Its syntax is:

The part1 and part2 arguments are the partition vectors. The meaning of the crit argument is the same as for the intCriteria function. 

Given a vector of several clustering quality index values computed with a given criterion, the function bestCriterion returns the index of the one which must be considered as the best in the sense of the specified criterion. Its syntax is:
section_name: Available commands

section_content: The x argument is a numeric vector of quality index values. The crit argument is the name of the criterion: it is case insensitive and can be abbreviated. 

Typically, a set of data is clusterized several times (using different algorithms or specifying a different number of clusters) and a clustering index is calculated each time: the bestCriterion function tells which value is considered the best. For instance, if one uses the Calinski_Harabasz index, the best value is the largest one. 

The concordance function calculates the concordance matrix between two partitions of the same data. Its syntax is: concordance(part1, part2)

The arguments are the partition vectors. The function returns a 2 × 2 matrix of the form: yy yn ny nn

These are the number of pairs classified as belonging or not belonging to the same cluster with respect to both partitions. Since there are N (N -1)/2 pairs of distinct points, one has:

The getCriteriaNames function is a convenience function which returns the names of the currently implemented indices. Its syntax is:

where the argument isInternal is a logical value: if TRUE it returns the names of the internal indices, otherwise it returns the names of the external ones.
section_name: bestCriterion(x, crit)

section_content: First load the package:
section_name: Examples of use

section_content: Let us create some artificial data: > x <-rbind(matrix(rnorm(100, mean = 0, sd = 0. 5), ncol = 2), + matrix(rnorm(100, mean = 1, sd = 0. 5), ncol = 2), + matrix(rnorm(100, mean = 2, sd = 0. 5), ncol = 2))

Now perform the kmeans algorithm in order to get a partition with 3 clusters (the kmeans function is provided by R in the stats package and is available by default):

Let us get the names of the internal indices:
section_name: > library(clusterCrit)

section_content: [1] "Ball_Hall" "Banfeld_Raftery" "C_index" [4] "Calinski_Harabasz" "Davies_Bouldin" "Det_Ratio" [7] "Dunn" "Gamma" "G_plus" [10] "GDI11" "GDI12" "GDI13" [13] "GDI21" "GDI22" "GDI23" [16] "GDI31" "GDI32" "GDI33" [19] "GDI41" "GDI42" "GDI43" [22] "GDI51" "GDI52" "GDI53" [25] "Ksq_DetW" "Log_Det_Ratio" "Log_SS_Ratio" [28] "McClain_Rao" "PBM" "Point_Biserial" [31] "Ray_Turi" "Ratkowsky_Lance" "Scott_Symons" [34] "SD_Scat" "SD_Dis" "S_Dbw" [37] "Silhouette" "Tau" "Trace_W" [40] "Trace_WiB" "Wemmert_Gancarski" "Xie_Beni"

Let us compute all the internal indices and display one of them:

> intIdx <-intCriteria(x,cl$cluster,"all") > length(intIdx)

[1] 42
section_name: > getCriteriaNames(TRUE)

section_content: [1] 67. 44501

It is possible to compute only a few indices:

> intCriteria(x,cl$cluster,c("C_index","Calinski_Harabasz","Dunn"))

$c_index [1] 0. 06240864 $calinski_harabasz [1] 255. 5711

$dunn [1] 0. 03600579

The names are case insensitive and can be abbreviated:

> intCriteria(x,cl$cluster,c("det","cal","dav"))

$det_ratio
section_name: > intIdx[["trace_w"]]

section_content: [1] "Czekanowski_Dice" "Folkes_Mallows" "Hubert" "Jaccard" [5] "Kulczynski" "McNemar" "Phi" "Precision" [9] "Rand" "Recall" "Rogers_Tanimoto" "Russel_Rao" [13] "Sokal_Sneath1" "Sokal_Sneath2"

Let us compute all the external indices and retrieve one of them:

> extIdx <-extCriteria(part1,part2,"all") > length(extIdx)

[1] 14
section_name: > getCriteriaNames(FALSE)

section_content: [1] 0. 140622

Let us compute only some of them:

> extCriteria(part1,part2,c("Rand","Folkes"))

$rand [1] 0. 5920358 $folkes_mallows [1] 0. 2539172

The names are case insensitive and can be abbreviated:

> extCriteria(part1,part2,c("ra","fo"))

$rand [1] 0. 5920358 $folkes_mallows [1] 0. 2539172
section_name: > extIdx[["jaccard"]]

section_content: The clusterCrit package is written in Fortran which makes the calculations quite fast. Nevertheless some indices are more demanding and require more computations than the others. The following timings have been evaluated using the rbenchmark package: the various indices have been computed separately 100 times on a set of 400 points partitionned in four groups. The results are not interesting per se but rather to compare the amount of computations required by the different indices. 

The following table summarizes the timings for the internal indices (they are expressed in seconds for 100 replications, so they must all be divided by 100):
section_name: Benchmark