Foldwise Clustering for Cross-Validation

Why Clustering Must Be Foldwise

A cluster-derived predictor is not simply a property of a record. It is a property of the record relative to a fitted clustering rule: the training observations, any scaling parameters, the chosen number of clusters, and the fitted cluster centers jointly determine its assignment. In cross-validation, each training fold supplies a different set of observations on which to fit that rule.

For a fair assessment, a fold’s assessment records must be assigned using only the clustering rule learned from that fold’s training records. Clustering the full data set first, then cross-validating a prediction model that uses those full-data cluster assignments, allows assessment predictors to influence the representation used to evaluate the model. The outcome may not have been used, but the assessment data have still helped determine the features.

Definition: Foldwise clustering means fitting the clustering procedure separately on the predictor records in each cross-validation training fold, then assigning that fold’s assessment records using the clustering rule fitted on that fold. The cluster-derived predictor used to train the fold’s prediction model and the one used to represent its assessment records must come from the same fitted clustering rule.

Suppose a data set is divided into \(K\) folds. For fold \(k\), let \(T_k\) denote the training records and \(A_k\) the assessment records. The clustering fit for that fold is based on predictors in \(T_k\). If the procedure uses a scaling rule, that rule is also estimated from \(T_k\) and applied unchanged to \(A_k\). The assessment records do not determine centers, cluster boundaries, or scaling parameters.

\text{fit clustering on } T_k \quad\longrightarrow\quad \text{assign } T_k \text{ and } A_k \quad\longrightarrow\quad \text{fit and assess the prediction model for fold } k

For example, with \(k\)-means, the fitted rule consists of the centers and the distance-based assignment rule. A new record is assigned to the nearest fitted center under the same variables and scale used in fitting. It is not included in a new clustering fit with the training records. This is the operational meaning of assigning new records to existing clusters.

What Is Estimated Within a Fold?

A clustering procedure may involve choices or quantities estimated from the data. Every data-dependent part used to create a cluster feature must be determined from that fold’s training predictors. For \(k\)-means, these include the cluster centers. If predictors are standardized before clustering, the training-fold means and standard deviations used for that standardization must also be used to transform the assessment records. A fixed, prespecified choice such as \(k=3\) can be held constant across folds; a choice selected by examining the data must not be selected using the assessment fold.

For a \(k\)-means fit with \(k\) clusters and Euclidean distance, each training record is assigned to one of the fitted clusters. The fitted center for cluster \(j\) is the coordinate-wise mean of its assigned training records. The within-cluster sum of squares (WSS) is the sum of squared Euclidean distances from records to their assigned centers. WSS describes the fit of a clustering to the records used to fit it; it is not itself a cross-validated prediction metric.

\operatorname{WSS} = \sum_{j=1}^{k}\ \sum_{i\in C_j} \left\|x_i-\bar{x}_j\right\|^2

Here \(C_j\) is the set of training records assigned to cluster \(j\), \(x_i\) is a predictor vector, and \(\bar{x}_j\) is the mean vector for that cluster. A fold’s assessment records are not included in this WSS calculation. Their cluster assignments are produced afterward by applying the fitted rule.

Why the center is the mean: For one cluster with fixed membership and scalar observations \(x_1,\ldots,x_n\), the sum of squared distances to a proposed center \(c\) is \(Q(c)=\sum_{i=1}^{n}(x_i-c)^2\). Differentiating gives \(Q'(c)=-2\sum_{i=1}^{n}(x_i-c)\). Setting \(Q'(c)=0\) yields \(c=\sum_i x_i/n=\bar{x}\). Since \(Q''(c)=2n>0\), this is the minimizing center. The same coordinate-wise argument applies to a vector of predictors.

Worked Example: Fit Two Clusters and Assign Assessment Records

A fold’s training data contain six one-dimensional predictor values: \(0,2,4,6,8,10\). A two-cluster \(k\)-means fit has reached the partition \(C_1=\{0,2,4\}\) and \(C_2=\{6,8,10\}\). Find the centers and WSS, then assign assessment values \(3\) and \(9\). Also check the squared-distance total for initial centers \(3\) and \(7\), before updating them.

Method. Calculate each fitted center as the training mean in its cluster, sum squared distances to those fitted centers, and assign assessment values to the nearest fitted center.

Centers. For the first cluster, \(\bar{x}_1=(0+2+4)/3=6/3=2\). For the second, \(\bar{x}_2=(6+8+10)/3=24/3=8\).

WSS. The first cluster contributes \((0-2)^2+(2-2)^2+(4-2)^2=4+0+4=8\). The second contributes \((6-8)^2+(8-8)^2+(10-8)^2=4+0+4=8\). Therefore, the fitted partition has WSS \(8+8=16\).

Assessment assignments. For value \(3\), the distances to centers \(2\) and \(8\) are \(|3-2|=1\) and \(|3-8|=5\), so it is assigned to cluster 1. For value \(9\), the distances are \(|9-2|=7\) and \(|9-8|=1\), so it is assigned to cluster 2.

Check the initial-center calculation. With centers \(3\) and \(7\), the indicated assignments are \(0,2\) to center \(3\), and \(4,6,8,10\) to center \(7\). The squared-distance total is \((0-3)^2+(2-3)^2+(4-7)^2+(6-7)^2+(8-7)^2+(10-7)^2=9+1+9+1+1+9=30\), not \(22\). This is the total relative to those initial centers, not the WSS of the stated final partition. After updating to the stated partition’s means \(2\) and \(8\), its WSS is \(16\), as calculated above.

Check. Both assessment assignments use only the fitted centers \(2\) and \(8\); neither assessment value changes those centers. The common mistake is to report a squared-distance total for one set of centers as though it were the WSS for a different, updated fit.

Cluster Labels Are Fold-Specific

Cluster numbers are names, not measurements. A cluster called “1” in one fold has no guaranteed relationship to cluster “1” in another fold. Different training samples can produce different centers, and clustering software may number the same-looking groups in a different order. The meaning of a label is defined only by its fitted rule in that fold.

Within a fold, the training records and assessment records must use the same label mapping. If the training cluster near lower values is coded as label 1, then an assessment record assigned to that fitted cluster must also be coded as label 1 for that fold’s model. It would be incorrect to independently relabel assessment records or refit the clustering on them.

Across folds, however, the numeric labels should not be treated as a shared category without checking what they represent. In ordinary cross-validation, each fold’s prediction model is trained using that fold’s cluster coding, and that same fitted coding is used for its assessment records. The resulting assessment predictions can be collected and evaluated, even though the cluster labels themselves may not be comparable across folds. If a later analysis needs to describe a common cluster meaning across folds, that requires a deliberate comparison of centers or another alignment method; the label number alone does not establish equivalence.

Worked Example: Same Groups, Reversed Cluster Numbers

Two folds use a single predictor, annual service visits. In fold A, the fitted centers are 2 and 8 visits, with the lower center labeled 1 and the higher center labeled 2. In fold B, the fitted centers are 9 and 3 visits, with the first center labeled 1 and the second labeled 2. Assign an assessment record with 4 visits in each fold, and explain whether the two labels mean the same thing.

Fold A assignment. The distances from 4 to the labeled centers are \(|4-2|=2\) for label 1 and \(|4-8|=4\) for label 2. It is assigned label 1, representing the lower-visit cluster in fold A.

Fold B assignment. The distances are \(|4-9|=5\) for label 1 and \(|4-3|=1\) for label 2. It is assigned label 2, representing the lower-visit cluster in fold B.

Interpretation. Both assignments correspond to the lower-visit group under their respective fitted rules, but their numeric labels differ. Conversely, label 1 means the lower-visit group in fold A and the higher-visit group in fold B. Thus the label “1” cannot be interpreted as a common group across folds without considering the fold-specific centers.

Check. The record is assigned separately under each fold’s centers; its assignment in fold A does not alter its assignment in fold B. The common mistake is to assume that identically numbered clusters have identical meanings merely because both fits used the same value of \(k\).

Scaling and the Assessment Rule

Distances depend on measurement scales. If one predictor is measured in dollars in the thousands and another ranges from 0 to 1, Euclidean distance may be dominated by the dollar-valued variable. If the analysis specifies standardization, calculate the means and standard deviations from the training fold, standardize its records, and use those same quantities to standardize assessment records. Recomputing standardization statistics using assessment records changes the fitted representation and allows assessment information to affect the rule.

The assignment rule must match the fitting rule. For example, if clustering was fitted using standardized predictors and Euclidean distance, assessment records must also be standardized using the fold’s training means and standard deviations, then assigned by Euclidean distance to the fitted centers in standardized coordinates. Comparing raw assessment values with standardized centers is not a valid assignment.

Worked Example: Apply Training-Fold Scaling Before Assignment

A training fold has already been standardized using its own fitted transformation. In that standardized one-dimensional space, its two cluster centers are \(-1\) and \(1\). The training-fold raw mean and standard deviation are 10 and 2, respectively, and the assessment record has raw value 13. Standardization is \(z=(x-\text{mean})/\text{standard deviation}\). Assign the record correctly, and identify the error in comparing its raw value directly to the centers.

Transform using training-fold quantities. The assessment value becomes \(z=(13-10)/2=3/2=1.5\). The value 13 is not compared directly to centers expressed in standardized units.

Compare distances in the fitted space. Its distance to center \(-1\) is \(|1.5-(-1)|=2.5\). Its distance to center \(1\) is \(|1.5-1|=0.5\). Therefore, it is assigned to the cluster centered at \(1\).

Check. The standardized value \(1.5\) is closer to \(1\) than to \(-1\), so the assignment is consistent. Comparing raw 13 to \(-1\) and \(1\) would mix units and produce no meaningful nearest-center decision. Re-estimating the mean or standard deviation from the assessment record would also violate the fold-specific rule.

Practical Foldwise Workflow

A reliable implementation treats clustering as part of the fold-specific feature-building process. For each fold, keep a record of the exact variables, any transformations, the fitted clustering object, and how cluster labels are encoded for the prediction model. In R, the conceptual sequence is to subset the training and assessment rows, fit any required preprocessing on training predictors, call a clustering method such as kmeans() on the processed training predictors, and use the returned centers to assign assessment predictors. The cluster feature is then supplied to the prediction model fitted for that fold.

Separate the fold.
Identify its training records and assessment records before estimating any data-dependent clustering quantities.

Fit the fold’s representation.
Estimate any required scaling from training predictors, then fit the clustering procedure on those training predictors only.

Create both sets of features.
Use the fitted clustering rule to assign training records and assessment records. Preserve the fold’s own cluster coding for both.

Fit and assess the prediction model.
Train the model using the fold’s training outcomes and training-derived features; predict assessment outcomes using assessment features made by that same fold’s rule.

Repeat independently.
Refit preprocessing and clustering for each new training fold rather than carrying centers or labels over from another fold or the full data set.

A fixed random seed or multiple initializations can help make \(k\)-means fits reproducible or less dependent on a poor starting point, but neither changes the foldwise principle. Any selection based on fit quality should be conducted using the training data available within the fold, not by choosing the result that best represents its assessment records.

Common Exam Traps

Cluster first, split later. This lets assessment predictors influence centers or boundaries. Split first, then fit clustering on each training fold.
Refit to include assessment records. Assessment records are assigned to existing fold-specific clusters; they are not added to the fitting data for that fold.
Use full-data scaling. If scaling is part of the fitted feature process, estimate its parameters from the fold’s training predictors only.
Assume label 1 has a stable meaning. Labels are arbitrary within a fit and may be permuted across fits. Interpret a label with its fold-specific centers, not by number alone.
Pool labels before considering folds. Fold-specific numeric cluster codes are not automatically one common categorical variable. Each fold’s model must receive consistent coding between its own training and assessment records.
Use an incorrect distance scale or WSS. Calculate assignment distances and WSS in the same predictor space used to fit the clusters, and distinguish distances to initial centers from WSS at updated fitted centers.

Key takeaway: Cross-validation evaluates a complete prediction process, including how cluster features are created. Fit clustering and any associated preprocessing on each training fold, assign its assessment records with that fold’s fitted rule, and treat cluster numbers as fold-specific labels.

Check Your Understanding

For each problem, state the fold-specific action or calculate the requested quantity. Check that the assessment records never determine the clustering fit.

A training fold has one-dimensional values \(1,3,5,9\), partitioned as \(\{1,3,5\}\) and \(\{9\}\). Find the cluster centers and WSS. (Answer: centers \(3\) and \(9\); WSS \(8+0=8\).)
A fitted fold has centers 4 and 12. An assessment record has value 10. Assign it by nearest-center distance and show both distances. (Answer: distances 6 and 2; assign to the center at 12.)
Training-fold raw predictors have mean 20 and standard deviation 4. The standardized cluster centers are \(-1\) and \(1\), and an assessment value is 24. Transform it and assign it. (Answer: standardized value \(1\); distance 2 to \(-1\), distance 0 to \(1\); assign to the center at \(1\).)
Two folds have centers \((2,8)\) and \((9,3)\), respectively, with centers listed in label order 1 then 2. Which label represents the lower-center cluster in each fold, and can label 1 be treated as the same group across folds? (Answer: fold one label 1; fold two label 2; no, the numeric labels have reversed meanings.)
A team fits clusters on all records, then splits the resulting cluster labels into cross-validation folds. Identify the problem and give the corrected sequence. (Answer: assessment predictors influenced the clustering representation; split first, then fit clustering separately on each training fold and assign that fold’s assessment records with its fitted rule.)

What You'll Learn