90 minutes · 100 marks · 7 questions. Original self-study practice, not an official examination specification or weighting forecast. Answer every part; show essential calculations and proofs. Exact values are preferred; if a decimal answer is requested, state the rounding used. Consistent paired eigenvector/singular-vector sign changes are acceptable. Follow each question’s normalization, domain and tie rules; never assume an inverse exists. Use a Casio fx-50FH II for this practice; one double-sided A4 reference sheet may be used. These are practice conditions, not a new claim about official examination rules.
Mark allocations are self-assessment guidance. Give equivalent correct methods equal credit. Retain method marks after an isolated arithmetic error when subsequent reasoning remains valid. Read the question paper first; the answers below explain conditions and checks, not just final numbers.
| Q | 1 | 2 | 3 | 4 | 5 | 6 | 7 | Total |
|---|---|---|---|---|---|---|---|---|
| Marks | 20 | 14 | 15 | 9 | 9 | 15 | 18 | 100 |
Q1. Weighted polynomial regression and uniqueness (20)
(a) [4]
Each observation contributes a row containing the intercept, linear and quadratic terms. Because W is symmetric, the residual norm contains W². Expand the quadratic and differentiate. The positive-semidefinite Hessian makes the stationarity equation globally sufficient; positive definiteness would additionally give uniqueness.
Identify the objects first. The unknown is not a separate fitted value for each observation: it is the three coefficients shared by all four observations. Thus c is a three-dimensional column vector, whereas y and the residual are four-dimensional. M has four rows, one per observation, and three columns, one per basis function. Its first column is all ones and supplies the intercept. W is a 4×4 diagonal matrix; WM is 4×3. Consequently the normal-equation matrix is 3×3 and its right-hand side is a three-dimensional column vector.
Why are the weights squared? The question multiplies residual i by wᵢ before squaring it. A weight of 2 therefore multiplies its squared contribution by 4. When expanding the objective, the two cross terms are transposes of one another and are scalars, so they combine into the term with coefficient −2. The first term contains no c and has derivative zero. The symmetric quadratic term differentiates to twice its matrix times c. Setting the gradient to zero derives the equation for this specific objective rather than importing a formula with a different weighting convention.
When is an inverse justified? Positive semidefiniteness establishes convexity, not uniqueness. Positive definiteness or full column rank must be established before writing a unique coefficient vector using an inverse. Part (c) supplies that argument. “It is least squares, so it is invertible” is not a proof.
Marking： M and W 2; weighted quadratic1; derivative/equation1.
(b) [7]
Symmetric inputs and weights make odd weighted moments zero. Compute the right-hand side from the responses, then solve the decoupled slope and the two-variable system. Substitute all four inputs before calculating the weighted, not ordinary, residual sum. The final orthogonality check uses MᵀW²r; unweighted residual orthogonality is not required.
How are the matrix entries built from the data? The columns of M contain 1, x and x². Multiply the relevant two columns, multiply by the squared weights, and sum to obtain a Gram-matrix entry. The top-left entry is 1+4+4+1=10; the bottom-left is 4+4+4+4=16; the bottom-right is 16+4+4+16=40. Odd powers cancel because both the positions and their weights are symmetric, not merely because the inputs look symmetric.
The right-hand side also contains y, so its odd-power component need not vanish. Its components are 2+4+12+4=22, −4−4+12+8=12, and 8+4+12+16=40. Solve the middle equation for the linear coefficient first, then solve the two equations for the intercept and quadratic coefficient. This exploits the zero entries without discarding any equation. The latter system has nonzero determinant 144 and therefore a unique solution.
Substitution and verification. At x=−2 the fitted value is 5/3−3/2+4/3=3/2, giving residual 2−3/2=1/2. Compute the remaining residuals in the same observation order. Each weighted squared residual contributes exactly 1/4, producing total 1. For the weighted inner product with the linear column, the four terms are −1, 1, 1, −1 and sum to zero; the intercept and quadratic columns also give zero. This checks optimality. It does not require every residual to vanish, nor does it say the ordinary unweighted RSS equals 1.
Marking： Numerical matrix/right side2; three coefficients3; residual1; weighted minimum1.
(c) [5]
The quadratic form is a sum of nonnegative weighted squared polynomial values. If three weights are positive, zero quadratic form would make a polynomial of degree at most two vanish at three distinct points. Such a polynomial is identically zero, hence its coefficient vector is zero and the matrix is positive definite. Conversely, with at most two positive weights, WM has at most two nonzero rows and cannot have three independent columns. A nonzero null vector makes the Gram matrix singular. A zero-weight observation adds no identifying constraint.
Why turn a matrix question into a polynomial question? Computing the determinant for general weights is cumbersome. The Gram matrix is a transpose-times-itself matrix, so it is natural to ask whether its quadratic form can vanish for a nonzero vector. Regard the three entries of v as coefficients of a polynomial of degree at most two. Then Mv lists that polynomial's values at the observed inputs.
The crucial sufficiency step. A sum of nonnegative squares is zero only when every positive-weight contribution is zero; cancellation is impossible. Distinct inputs give three distinct roots. A nonzero polynomial of degree at most two has at most two distinct roots, including the cases where its actual degree is one or zero. Thus the polynomial is identically zero and all three coefficients vanish. This is exactly the condition for positive definiteness.
Necessity is a rank argument, not just equation counting. At most two nonzero rows imply rank at most two, whereas WM has three columns. Rank–nullity therefore supplies a nonzero v with WMv=0. The Gram matrix also maps this v to zero and is singular. The stated assumptions of nonnegative weights and distinct inputs matter: repeated observations at one input do not supply new distinct roots. Whenever a minimizer exists, moving its coefficients along this null direction leaves the objective unchanged, ruling out uniqueness.
Marking： Quadratic form1; three-root sufficiency2; rank necessity2.
(d) [4]
Each fold has n−1 distinct positively weighted observations. Four original observations leave the three needed for uniqueness. With only three original observations, each fold retains two inputs u,v. Adding any multiple of their vanishing quadratic to an interpolating polynomial leaves both fitted values unchanged, giving infinitely many coefficient vectors. With even fewer observations rank also fails.
Separate the two sample counts. The full data contain n observations, but leave-one-out cross-validation trains n models, each on only n−1 observations. The held-out response cannot be borrowed to identify a fold's coefficients. The requirement is uniqueness in every fold, not merely uniqueness after fitting all observations. Apply the three-distinct-positive-weight-input condition to each training subset.
Why are three observations in total insufficient? For the two retained inputs u and v, start with a line interpolating them and call it f₀. The polynomial (x−u)(x−v) vanishes at both retained inputs. Adding any multiple of it leaves both training predictions and the training loss unchanged, although different t values change the coefficients. A third independent constraint is missing. Hence n=4 is sufficient and minimal under the stated assumptions. Four records alone would not guarantee this if inputs repeated or some weights were zero.
Marking： Answer1; sufficiency1; two-retained-point nonuniqueness2.
Q2. Regularization, training scores and validation (14)
(a) [6]
Expand and differentiate; the positive second derivative gives the unique minimizer. R² evaluates unpenalized RSS, whereas the optimizer trades RSS against a penalty on the intercept itself. The mean predictor has smaller RSS but much larger total objective. Thus the OLS baseline argument for minimizing RSS alone does not apply.
Identify the actual objective. Both observations share the constant prediction a, so their unpenalized loss is (2−a)²+(4−a)². The question adds 2a². Expanding the residual terms gives 2a²−12a+20; only after adding the penalty do we obtain 4a²−12a+20. The positive second derivative shows that the stationary point is the unique global minimum, rather than a maximum or merely a candidate.
Why can the score be negative when optimization is correct? The numerator used in R² is unpenalized RSS, without the additional 2a². At prediction 3/2, the squared errors are 1/4 and 25/4, giving RSS 13/2. TSS is measured about the observed mean 3, not about the fitted constant 3/2. Since RSS exceeds TSS, R² is negative: on these observations, prediction error alone is worse than always predicting the mean.
The optimizer compares a different quantity. At 3/2 the penalty is 9/2 and the total objective is 11; at 3 the penalty is 18 and the total is 20. The penalty reduction outweighs the increase in prediction error. Choosing 3/2 is therefore correct for this objective. Being a training-set score does not alone guarantee nonnegative R²: whether the intercept is penalized matters.
Marking： Minimizer/minimality2; RSS1; TSS1; R²1; different objective1.
(b) [4]
Use the feasible mean predictor with zero slopes. Its penalty vanishes, so its entire objective equals TSS. Global optimality and nonnegativity of the penalty bound the fitted RSS. Divide by positive TSS. No full-rank assumption or unpenalized normal-equation orthogonality is needed. The same comparison applies to any nonnegative slope penalty that vanishes at zero slopes.
Why need we not solve for the coefficients? We only need to bound the fitted RSS against one particular baseline, not determine every optimal parameter. Let X be n×p, b a p-dimensional slope vector and a a scalar. Setting b=0 removes every feature contribution. Setting a to the training-response mean then gives the constant predictor whose RSS is TSS.
Read the inequality chain one step at a time. RSS is nonnegative because it is a sum of squares. A nonnegative penalty means RSS is no larger than RSS plus penalty. Global optimality makes the entire fitted objective no larger than the objective at any feasible comparison point. Finally that comparison point has zero penalty, so its objective equals TSS. The unpenalized intercept is essential to the last step; penalizing it can break the argument as in (a). Divide by positive TSS to bound RSS/TSS between zero and one, then subtract from one.
If TSS=0, all responses are identical and the usual R² ratio has a zero denominator; this proof does not assign it a value of zero or one. The argument concerns the data used for optimization, not a separate test set with different errors and mean. Uniqueness of coefficients and a bound on the score are different issues, so full column rank of X is unnecessary.
Marking： Comparison point1; objective=TSS1; inequality chain1; positive TSS and bound1.
(c) [4]
First, scaling statistics and PCA directions learned from all observations expose test-feature information even without labels. Second, repeated test-based selection turns the test set into validation and biases the reported best score. Reserve a final test set first, respecting time/group dependence if present. Within each training CV fold, fit scaling, PCA and ridge only on that fold’s training subset, apply the frozen transformations to its validation subset, and aggregate errors to choose penalty and PCA dimension. Lock choices, refit the entire pipeline on development data, then evaluate the untouched test set once. Doing PCA once on all development data before CV still leaks within folds.
Recognize what counts as fitting. Training is not just the final ridge call. Estimating means, standard deviations and PCA directions also learns parameters from data. Not using labels does not mean no test information was used. A test set is meant to represent unseen data and must not participate in choosing its representation.
Write the corrected process in chronological order: (1) isolate the final test set, respecting temporal or group structure where appropriate; (2) create training and validation folds inside the development data; (3) estimate scaling parameters and fit PCA and ridge on each training fold only, transform its validation fold using those fixed parameters, and aggregate validation errors to choose the penalty and dimension; (4) lock the choices, refit the complete pipeline on all development data, and evaluate once on the final test set. A validation fold must not estimate its own separate means or PCA directions either, because that would also put it in a different coordinate system from the trained model.
Identify both errors separately. Correct preprocessing does not excuse repeatedly selecting parameters using test scores. Avoiding test-score tuning does not excuse fitting PCA on all observations beforehand. Once a test set has been used for selection, its best selected score cannot be described as an independent final test result. Credit requires locating the information leakage and explaining fold-specific refitting, not merely saying “use cross-validation”.
Marking： Preprocessing leak1; test tuning1; fold-local pipeline1; refit and final test1.
Q3. Negative dominant eigenvalue and one completion step (15)
(a) [4]
Multiplication gives the raw vector and its length. The eigenvalue of largest absolute value is−3 and the initial vector has nonzero projection onto its eigendirection. Even iterations approach the positive first axis, odd ones the negative first axis; the oriented vectors do not converge to a single vector, but their lines do. Dividing by a positive length does not force the estimated eigenvalue to be positive.
Follow the algorithm without skipping the norm. B is 2×2 and each iterate has two components. Multiply first, then compute the Euclidean norm: its square is (9+1)/2=5. Dividing by √5 produces the denominator √10 in the new vector. Its squared length is (9+1)/10=1, so the Rayleigh quotient's denominator is already one. The positive normalization length is not a signed eigenvalue estimate.
Why does the minus sign persist? Every multiplication by B multiplies the first component by −3 and the second by 1. Normalization changes overall length but not the component ratio, yielding the displayed expression at step t. The first component dominates in magnitude while alternating in sign. Power iteration requires a nonzero initial component in the dominant-absolute-eigenvalue direction, which holds here. Starting with only the second component would not find −3.
The Rayleigh quotient weights the eigenvalues by squared components, so reversing the whole vector does not change it. The first squared weight tends to one and the quotient tends to −3. Distinguish convergence of an oriented vector, convergence of its unoriented line, and convergence of the quotient; answering one does not answer the others.
Marking： Normalized vector1; quotient1; limit1; sign/direction distinction1.
(b) [6]
Diagonalize the Gram matrix to get squared singular values. Choose right eigenvectors, then compute left vectors by multiplying and dividing by the matching singular values. The second eigenvalue of the symmetric original matrix is negative, so its left singular vector is the negative of the right one. Symmetry alone does not justify U=V when singular values must be nonnegative. Verify both orthogonality and the reconstructed product.
Why start with a Gram matrix? Singular values are nonnegative by definition, whereas the original matrix can have negative eigenvalues. Right singular vectors are unit eigenvectors of the transpose-times-original Gram matrix; singular values are the nonnegative square roots of its eigenvalues. Thus 9 and 1 produce singular values 3 and 1, not diagonal entries 9 and 1 in Σ. Here U, Σ and V are all 2×2, and column order must match singular-value order.
Left vectors cannot be chosen independently. Once v₁ and v₂ have been selected, multiply them by the original matrix and divide by 3 and 1 respectively to obtain their paired left vectors. The original matrix reverses the second direction, so the second left vector needs a minus sign. Forcing U=V with nonnegative Σ would lose that reversal. Both members of a corresponding pair may be negated together, since the signs cancel in their outer product; changing just one changes the reconstruction.
Finally add the rank-one terms separately: the first is 3/2 times the all-ones matrix, and the second is −1/2 times the alternating-sign matrix. Their sum has diagonal entries 1 and off-diagonal entries 2. Orthogonality checks unit column lengths and zero cross inner products; reconstruction checks that directions, signs and ordering are correctly paired.
Marking： Gram and spectrum2; singular values1; V1; paired U1; verification1.
(c) [5]
Soft-thresholding retains one singular component with value2. Restoration changes the lower-left entry back to the observed2 while retaining the estimated missing upper-right entry1. The low-rank estimate and the observation-consistent iterate serve different purposes. Restoring entries is not rank preserving and need not maintain symmetry. Do not replace both off-diagonal entries simply because the initialization was symmetric.
Separate the two operations. Soft thresholding acts on singular values, not by subtracting one from every matrix entry. The positive-part expression means subtract one and then take the maximum with zero. Thus 3 becomes 2 and 1 becomes 0. Only the first singular-vector pair contributes, giving Y with all four entries equal to one. Its single nonzero singular value gives rank one.
Only then restore the observations, consulting the observed-entry mask rather than matrix symmetry. The lower-left observed entry must be restored to 2; the missing upper-right entry retains its estimate 1 from Y. The diagonal observations are already 1. Consequently X⁽¹⁾ is not symmetric. Its determinant is 1−2=−1, which makes this 2×2 matrix full rank.
There is no contradiction. Y is the low-rank shrinkage estimate, whereas X⁽¹⁾ is the next iteration's input with observed entries enforced. Restoring hard constraints may destroy low rank. The question asks for just this update: do not report Y as the restored matrix or conclude that the algorithm has failed because one restored iterate has full rank.
Marking： Thresholded values1; Y1; restored matrix1; both ranks1; distinct roles1.
Q4. Classical multidimensional scaling (9)
(a) [5]
For centered coordinates, squared distances expand into two squared norms minus twice an inner product. Multiplying by H annihilates the norm-only row and column terms because H1=0, while HG H=G. Compute squared-distance row means and the grand mean to avoid two full matrix products. The zero row sums check centering. Squaring after averaging would be a different operation.
What does double centering remove? Let each row of Z be a centered point coordinate. Then G=ZZᵀ is the 3×3 inner-product matrix, and g contains its three diagonal entries, the squared point lengths. Squared distance expands as the squared length of point i plus that of point j minus twice their inner product. The first two terms depend only on a row or a column, so they become outer products involving the all-ones vector.
H is the 3×3 centering matrix I−11ᵀ/3. It annihilates the all-ones vector, so multiplication on both sides removes those two outer products. Centered coordinates also satisfy HZ=Z, hence HGH=G. Only −2G remains. This explains why distances must first be squared entry by entry: neither centering unsquared distances nor taking the matrix product D·D gives the required input.
Calculate representative entries. The first row 0, 1, 9 has mean 10/3; the other row means are 5/3 and 13/3. All nine entries sum to 28, so the grand mean is 28/9, not 28/3. For G₁₁, the bracket is 0−10/3−10/3+28/9=−32/9; multiplying by −1/2 gives 16/9. For G₁₂ it is 1−10/3−5/3+28/9=−8/9, giving 4/9. Compute other entries identically, then check symmetry and zero row sums.
Marking： Distance expansion/centering2; squared-distance matrix1; G2.
(b) [4]
Recognize the rank-one outer product. Its only positive eigenvalue is the vector’s squared norm; the other two are zero. Scale a unit eigenvector by the square root of that eigenvalue, not by the eigenvalue itself. The resulting coordinates sum to zero and reproduce all distances. Centering fixes translation, but simultaneous sign reversal gives an indistinguishable reflection. Without centering any common translation would also be allowed.
Avoid a cubic characteristic polynomial. The rows of G are proportional, suggesting an outer product of one column vector with itself. Once z is found, Gz=z(zᵀz) shows that z is an eigenvector with eigenvalue equal to its squared length. Every vector perpendicular to z is mapped to zero, giving the other two zero eigenvalues. Three objects need only one dimension here because of the rank, not because their number prescribes a dimension.
Why multiply by a square root? A unit eigenvector specifies direction and unit length. Coordinates αq₁ have Gram matrix α²q₁q₁ᵀ. To match eigenvalue λ₁, we need α²=λ₁ and hence a square-root scaling. Multiplication by λ₁ itself would square the wrong scale. Finally, checking the zero coordinate sum is not enough: computing all absolute pairwise differences as 1, 3 and 2 verifies the actual distance reconstruction.
Negating all coordinates is a one-dimensional reflection and preserves every absolute difference, so it is equally valid. Negating just one coordinate generally is not. Centering removes translation freedom but does not remove reflection freedom.
Marking： Spectrum1; eigenvector/outer product1; coordinates1; reflection and centering1.
Q5. LDA with specified covariance normalization (9)
(a) [4]
Center each observation using its own class mean for within-class covariance. The first class varies only horizontally; the second only vertically. Divide their summed outer products by the prescribed4, not by n−1 or separate class sample denominators. For between-class covariance center the class means about the overall mean and average their outer products.
Decide which mean to subtract. Each observation is a two-dimensional column vector and each covariance matrix is 2×2. Within-class variation measures dispersion around the class's own center. Subtracting the overall mean would mix class separation into that quantity. Class-one deviations are (−1,0) and (1,0), whose outer products each contribute 1 to the upper-left entry. Class-two deviations are (0,−2) and (0,2), each contributing 4 to the lower-right. Thus their unnormalized scatter totals are 2 and 8.
The question requires summing both class scatters and dividing by all four observations, giving diagonal entries 1/2 and 2. This is a specified definition, not an invitation to substitute an unbiased covariance estimator. For the between-class quantity, the objects being centered are the two class means. Their deviations from the overall mean are negatives of one another and have identical outer products; averaging leaves that same matrix. Its off-diagonal entry is (3/2)×1=3/2, not zero.
Checks: equal class sizes make the overall mean the simple average of the two class means, and both covariance matrices must be symmetric positive semidefinite. Overall and within-class centering are not interchangeable. Changing denominators is not immaterial, because the next part's generalized eigenvalue depends on them.
Marking： Means1; within-class centering/covariance2; between-class covariance1.
(b) [3]
The within-class matrix is positive definite, so inverse covariance weighting is valid. With two equal-sized classes, between-class covariance is one-quarter of the mean-difference outer product. The generalized eigenproblem has eigenvalues5 and0; normalize its maximizing vector and enforce the sign convention. The direction is not simply the normalized mean difference because the first feature has lower within-class variation. Omitting the quarter factor leaves the direction unchanged but incorrectly multiplies the eigenvalue by four.
Why apply inverse within-class covariance to the direction? LDA compares projected between-class variation with projected within-class variation. The mean difference d describes separation of the centers but ignores how dispersed each coordinate is within a class. Within-class variances are 1/2 and 2. The inverse covariance multiplies these coordinates by 2 and 1/2, emphasizing the lower-noise direction and turning (3,2) into (6,1), rather than merely normalizing (3,2).
Positive definiteness makes the denominator positive in every nonzero direction and permits inversion. The between-class matrix has rank one, leaving one zero eigenvalue. The product matrix has trace 9/2+1/2=5 and determinant zero, giving eigenvalues 5 and 0. This establishes that the displayed direction is maximal, not just an arbitrary eigenvector. The inverse-within-times-between matrix need not itself be symmetric; that appearance does not invalidate its role.
Dividing (6,1) by √37 gives unit length and a positive first component as required. Independently checking numerator 100/37 and denominator 20/37 produces ratio 5. Scaling the direction does not change this ratio, but omitting the factor 1/4 from between-class covariance multiplies it by four.
Marking： Invertibility/direction1; normalization/sign1; maximum eigenvalue1.
(c) [2]
Take the dot product with each raw observation. The average equals the projection of the overall mean, providing a check. Centered projections would subtract that common value; their class separation is unchanged but they are not the coordinates requested here.
Read the projection as a concrete calculation. The scalar uᵀx is obtained by multiplying the first original coordinate by 6 and the second by 1, adding, then dividing by √37. The original points are (−1,0), (1,0), (3,0), (3,4), so their numerators are −6, 6, 18, 22. Do not subtract another mean or normalize the projected observations again.
Linearity says that averaging projections equals projecting the average. The four numerators average to 10, agreeing with 6×(3/2)+1=10. Incorrectly projecting centered observations would subtract 10 from each numerator, giving −16, −4, 8, 12. Relative distances would survive, but these would not be the requested original-data projections. This check catches an answer whose separation looks right but whose overall location is wrong.
Marking： Each projection0.5.
Q6. Hierarchical clustering: linkage matters (15)
(a) [4]
List all six original distances first. Single linkage takes the minimum cross-cluster distance. After merging A,B, recompute distances to C and D; the smaller link from B to C causes C to join next. Finally D joins at its distance to C. This chain-like absorption does not require C to be close to every point in the existing cluster. No merge-changing tie occurs.
From point distances to cluster distances. On the real line use absolute coordinate differences, not squared distances. Initially every point is a singleton; the smallest of the six pair distances is 2, so the first merge is unambiguous. After merging A and B, however, the objects are three clusters. Do not mechanically pick the next unused number from the original point-pair table.
Single linkage uses the shortest cross-cluster distance for each pair of current clusters. For AB versus C compare AC and BC, obtaining 3. For AB versus D compare AD and BD, obtaining 13/2. C versus D remains 7/2. Comparing these three candidates selects 3 and forms ABC. Finally compare the distances from A, B and C to D; the minimum comes from C and is 7/2.
A merge height records the current linkage distance, not the diameter of the resulting cluster. ABC has diameter 5 but forms at height 3. In a dendrogram join A and B at 2, attach C at 3, and attach D at 7/2. Increasing heights and a final single cluster provide useful process checks.
Marking： Initial distances/first merge1; updated distances/second merge2; final merge1.
(b) [7]
The first merge is still A,B because singleton linkage definitions agree. Afterward average all cross-cluster pairs rather than selecting the closest pair. C,D now form the second cluster, since their distance is below the AB-to-C average. The final average uses all four pairs between two size-two clusters. Both the tree shape and merge heights differ from single linkage; averaging centroids would be a different definition.
The same first merge does not imply the same later merges. Singleton clusters have only one cross-cluster pair, so both a minimum and an average equal the original point distance. After AB forms, its two distances to C average to 4, and its two distances to D average to 15/2. Now the C–D distance 7/2 is smaller than 4. Thus form CD rather than copying the single-linkage decision to attach C to AB.
Between AB and CD, the cross-cluster pairs are AC, AD, BC and BD: exactly 2×2=4 pairs. Internal distances AB and CD do not belong in the numerator. Nor is the denominator two merely because there are two clusters. The four distances sum to 23, giving mean 23/4. It lies between their smallest value 3 and largest value 17/2, as any average must.
Describe the tree shape too. Single linkage creates a three-point cluster at the second step; average linkage creates two two-point clusters before joining them. Average linkage means averaging every cross-cluster point distance. Centroid distance is not a general substitute, even if it happens to agree in some separated one-dimensional configurations.
Marking： First merge1; three updated distances3; second merge1; four-pair average/final height2.
(c) [4]
Split the double sum into pairs from S and pairs from T. Each old average must be multiplied by its pair count before the counts are combined; the common |U| cancels. Equal cluster sizes guarantee the ordinary mean for arbitrary old distance values. Unequal sizes can happen to work if the old distances coincide, but this is not a general rule. The numerical example shows the discrepancy.
Why weight by cluster sizes? The old distance dₐᵥ(S,U) is already an average, not a total. To combine it with another average, first recover the totals: multiply by |S||U| for the pairs between S and U, and by |T||U| for those between T and U. Add those totals and divide by the new pair count (|S|+|T|)|U|. Cancelling the common factor |U| yields weights |S| and |T|.
Here S and T are disjoint nonempty old clusters and U is another nonempty cluster, ensuring nonzero denominators and no double counting. An unweighted average gives equal weight to the two old clusters. The definition instead gives equal weight to every cross-cluster point pair; a larger cluster supplies more pairs and should contribute more.
With old means 4 and 10 and twice as many pairs in the first group, the combined mean is closer to 4: it is 6 rather than midpoint 7. Equal cluster sizes guarantee that simple averaging works for arbitrary old distances. Equal old distances can also make it work accidentally, but do not justify ignoring sizes in general.
Marking： Split sums1; pair counts1; formula1; guarantee versus coincidence1.
Q7. DBSCAN: a shared border point is not a core bridge (18)
(a) [6]
List closed neighborhoods before applying the threshold of at least four points. E has only three neighbors and is not core, but lies next to core points D and F, so is border rather than noise. J is neither core nor within radius1 of any core, so is noise. Omitting the point itself would change the stipulated convention.
Fix three easily confused definitions. A neighborhood contains points at distance at most one, including the point itself and any point exactly at the boundary. Core status requires at least four neighborhood points, not four additional points besides itself. A noncore point adjacent to a core point is border; only otherwise is it noise. Determine all core points before classifying the remainder rather than immediately calling every point with fewer than four neighbors noise.
For example, D is at −0.9. Its distances to A, B and C are 0.9, 0.8 and 0.7; it also contains itself and E at distance 0.9, giving five points. F is already 1.8 away and excluded. E at zero contains only itself plus D and F at distance 0.9, giving three points. It fails the core threshold, but D and F are core, making E a shared border point. J's nearest other point I is still 2.2 away, so J has only itself and is adjacent to no core point: it is noise.
A, B, C and G, H, I each have exactly four neighborhood points and meet the threshold. Do not read “at least four” as “more than four”. Explicit neighborhood lists are more reliable than visual impressions of density; both counts and classifications matter for marking.
Marking： All counts3; eight core points, E border and J noise3.
(b) [4]
Starting from A, the left core component expands through D and includes E. Since E is not core, it cannot continue to F. When F is processed, the right core component forms a second cluster; E keeps its first assignment. Processing the right component first could change E’s assignment, but would not merge the two core components. Distinguish order-dependent border membership from core connectivity.
Simulate the visit order rather than connecting every adjacent point. A is processed first and is core, so its neighborhood enters the first cluster. B, C and D are also core and may contribute their neighborhoods. D brings in E, but E has only three neighbors, so propagation stops there. A point can be visited in the expansion queue without acquiring a core point's right to expand the cluster.
F is then an unassigned core point and starts a second cluster with G, H and I. Although F also sees E, the stipulated first-assignment rule keeps E in the first cluster. J has no core neighbor and remains noise. The final cluster sizes are five and four, plus one noise point: all ten points are covered without duplicate assignment.
Reversing the visit order could assign E to the right-hand cluster, but the four left core points and four right core points would still form two separate core components. Order affects the shared border label here; it does not authorize merging the two clusters through E.
Marking： Left core component1; right core component1; E assigned left1; J noise1.
(c) [4]
No. D and F are core, so both D–E and E–F are allowed graph edges. Their path bridges the two dense components, although its interior point E is not core. Undirected transitive connectivity ignores that distinction. Standard expansion may reach E from D but may not launch an expansion from E to F. To represent the core structure faithfully, connect core points only, find their components, then attach border points using the stated order; border points do not merge components.
First verify that the counterexample satisfies the proposed rule. That rule requires at least one endpoint of each edge to be core. D–E has core endpoint D; E–F has core endpoint F; both lengths are at most one. Both are therefore legal undirected edges. Although E is noncore, graph connectivity still permits a path from D through E to F, joining the two core regions into one component.
Standard DBSCAN instead imposes a condition on the point initiating each next expansion. Core D may add E, but noncore E may not initiate a further expansion to F. Replacing this conditional propagation with transitive undirected connectivity discards the crucial restriction. The distances are not wrong; the graph encodes a different relation from the algorithm.
Thus “not equivalent” alone is insufficient. Exhibit the two legal edges and the merged nine-point component, then identify noncore interior point E as the reason standard expansion stops. A faithful construction finds connected components in the core-only subgraph first and attaches neighboring border points according to the specified order. Border points must not serve as bridges that merge components.
Marking： Reject equivalence1; two legal graph edges1; merged component1; noncore cannot expand1.
(d) [4]
Sort distances including the initial zero. Ties in the fourth/fifth positions do not change the smallest radius enclosing at least four points. E needs a wider neighborhood to reach sufficient local density, raising the edge from ordinary length0.9 to weight1.6. Such sparse connections occur later in the density hierarchy. This is one ingredient of HDBSCAN, not a completed final cluster selection.
Core distance and core status are related but different questions. At fixed radius one, E is noncore. It still has a core distance: the radius needed to contain at least four points. Include the self-distance zero in sorting and select the fourth entry, rather than skipping zero and then taking the fourth. For D the first three entries come from itself, C and B; the fourth comes from A or E, giving 0.9. For E the first three come from itself, D and F; the fourth comes from C or G, giving 1.6.
A tie between the fourth and fifth entries simply means that both points enter at the same radius; no tie-breaking choice is needed. The definition asks for at least four points, not exactly four. Mutual reachability takes the maximum of both endpoint core distances and the original point distance. It therefore respects the density scales at both endpoints, with E's value 1.6 dominating here.
The raw D–E edge has length only 0.9 and looks short, but its increase to 1.6 reflects the sparse endpoint. In a hierarchy formed by increasing the distance threshold, this connection appears only at a larger threshold. Calculating one mutual-reachability edge does not compute the full minimum spanning tree, condensed hierarchy or stability-based cluster selection, so it does not determine the final HDBSCAN clustering.
Marking： Each core distance1; mutual reachability1; density/raised-weight explanation1.