Unit 4 exercises

First allocation. The squared distances to \(\mu_1\) and \(\mu_2\) are 0 and 1 for (0, 0), 1 and 0 for (1, 0), 1 and 2 for (0, 1), 50 and 41 for (5, 5), 61 and 50 for (6, 5), and 61 and 52 for (5, 6). Cluster 1 is {(0, 0), (0, 1)} and cluster 2 is {(1, 0), (5, 5), (6, 5), (5, 6)}, with \(J = 0 + 0 + 1 + 41 + 50 + 52 = 144\).

First update. \(\mu_1 = (0, 0.5)\) and \(\mu_2 = (17/4, 16/4) = (4.25, 4)\). The six squared distances to the new centers are 0.25, 0.25, 26.5625, 1.5625, 4.0625 and 4.5625, so the objective falls to \(J = 37.25\).

Second allocation. The record (1, 0) is now at squared distance \(1 + 0.25 = 1.25\) from \(\mu_1\) and \(10.5625 + 16 = 26.5625\) from \(\mu_2\), so it moves to cluster 1; the others stay. The three lower records contribute 0.25, 1.25 and 0.25, and the three upper records \(0.5625 + 1 = 1.5625\), \(3.0625 + 1 = 4.0625\) and \(0.5625 + 4 = 4.5625\), for a total of \(J = 11.9375\).

Second update. \(\mu_1 = (1/3, 1/3)\) and \(\mu_2 = (16/3, 16/3)\). Each cluster contributes \(4/3\), so \(J = 8/3 \approx 2.667\).

Third allocation. No record changes cluster, so the algorithm stops. The sequence of objective values, 144, 37.25, 11.9375 and 2.667, never increases, as it must, since each step minimizes \(J\) over either the allocation or the centers with the other held fixed.

Within its cluster, (1, 0) is at distance 1 from (0, 0) and \(\sqrt{2} \approx 1.414\) from (0, 1), so \(a = (1 + 1.414)/2 \approx 1.207\). To the other cluster, its distances are \(\sqrt{16 + 25} \approx 6.403\) to (5, 5), \(\sqrt{25 + 25} \approx 7.071\) to (6, 5) and \(\sqrt{16 + 36} \approx 7.211\) to (5, 6), so \(b \approx 6.895\). Then \(s = (6.895 - 1.207)/6.895 \approx 0.825\). The record is far closer to its own cluster than to the other one, so it is well placed. On the synthetic flow data of Lab 4, where the best mean silhouette is 0.38, clusters overlap far more than in this toy example.

First allocation. The table below gives the distance from each host to the initial centers and the cluster that the host joins.

Host C differs from \(\mu_1\) by 2 in the first feature and 3 in the second, and from \(\mu_2\) by 2 and 3 as well. Both squared distances are \(2^2 + 3^2 = 13\), so both distances equal \(\sqrt{13} \approx 3.606\), and the tie rule puts C in cluster 1. Cluster 1 is {A, B, C} and cluster 2 is {D, E, F, G}. Distances and squared distances rank the centers in the same order, so either gives this allocation, and \(J\) adds the squares. The squared distances of A to G to their own centers are 0, 1.25, 13, 0, 6.25, 2.5 and 8.5, which sum to \(J = 31.5\).

First update. The coordinates of A, B and C sum to 5.5 and 7, so their mean is \(\mu_1 = (11/6, 7/3)\), about (1.833, 2.333). The coordinates of D, E, F and G sum to 16.5 and 22, so \(\mu_2 = (4.125, 5.5)\). With the clusters held fixed, the objective falls to \(577/48 \approx 12.021\).

Second allocation. The second table gives the distances to the updated centers.

Host C is now closer to \(\mu_2\), at 1.875 against 2.034, so it moves to cluster 2, and no other host changes cluster. Cluster 1 is {A, B} and cluster 2 is {C, D, E, F, G}. Only the term of C in \(J\) changes, from \(149/36 \approx 4.139\) to \(225/64 \approx 3.516\), and the objective falls to \(6565/576 \approx 11.398\).

Second update. The mean of A and B is \(\mu_1 = (1.25, 1.5)\). The coordinates of the other five hosts sum to 19.5 and 26, so \(\mu_2 = (3.9, 5.2)\). The objective falls to \(69/8 = 8.625\), with 0.625 from cluster 1 and 8 from cluster 2.

Third allocation. The third table gives the distances to these centers.

Every host is closest to the center of its own cluster, so the allocation does not change, \(J\) stays at 8.625, and the algorithm stops after its third allocation step. The final clusters are {A, B}, with center (1.25, 1.5), and {C, D, E, F, G}, with center (3.9, 5.2). In the order of the steps, \(J\) takes the values 31.5, 12.021, 11.398, 8.625 and 8.625. It decreases at every step until the last allocation, which changes nothing. The tie rule affected only the path. Had C joined cluster 2 in the first allocation, the first update would already have produced the final centers, and the second allocation would have stopped the algorithm.

Checking with scikit-learn. With an explicit init and n_init=1, KMeans runs Lloyd's algorithm once from exactly these centers. The code below prints its result.

import numpy as np
from sklearn.cluster import KMeans

X = np.array([[1, 1], [1.5, 2], [3, 4], [5, 7],
              [3.5, 5], [4.5, 5.5], [3.5, 4.5]])
init = np.array([[1, 1], [5, 7]])
km = KMeans(n_clusters=2, init=init, n_init=1).fit(X)
print(km.labels_)           # [0 0 1 1 1 1 1]
print(km.cluster_centers_)  # [[1.25 1.5 ]
                            #  [3.9  5.2 ]]
print(km.inertia_)          # 8.625
print(km.n_iter_)           # 3

first = KMeans(n_clusters=2, init=init, n_init=1, max_iter=1).fit(X)
print(first.cluster_centers_)  # [[1.83333333 2.33333333]
                               #  [4.125      5.5       ]]
print(first.labels_)           # [0 0 1 1 1 1 1]
print(first.inertia_)          # 11.397569444444445

Scikit-learn numbers clusters from 0. With an explicit init, cluster \(j\) is the one that started from row \(j\) of init, so labels 0 and 1 correspond to clusters 1 and 2 above, and the labels, the centers and the inertia, which is \(J\), agree with the hand calculation. The attribute n_iter_ is 3, one iteration for each allocation step. With k-means++ or random starts the numbering is arbitrary and can change from one run to the next, so compare two clusterings by their members rather than by their labels.

The second fit, with max_iter=1, performs one allocation and one update. Because it has not converged, scikit-learn then runs one more allocation with the updated centers so that labels_ matches cluster_centers_, which is why first.labels_ is already [0 0 1 1 1 1 1] and first.inertia_ is \(6565/576 \approx 11.398\). The first allocation is therefore visible only in the centers. They are the means of {A, B, C} and {D, E, F, G}, the first update above, so its first allocation also placed C with the first center; had C gone to the second center, these centers would already be (1.25, 1.5) and (3.9, 5.2). This matches the implementation, whose allocation loop picks, among equally near centers, the one with the lowest number. Distances are computed in floating point, so on other data a tie that is exact on paper can be resolved either way by rounding.

1. \((3 - \lambda)^2 - 1 = 0\) gives \(\lambda_1 = 4\) with eigenvector \((1, 1)/\sqrt{2}\) and \(\lambda_2 = 2\) with eigenvector \((1, -1)/\sqrt{2}\). The first component explains \(4/(4 + 2) \approx 66.7\%\).

2. One component explains 66.7%, below 90%, so the 90% rule keeps both components. One component already reaches 60%, so the 60% rule keeps one.

3. For a centered record \((u, v)\), the reconstruction error is the squared score on the dropped component, \(((u - v)/\sqrt{2})^2\). For (2, 0) it is \((2/\sqrt{2})^2 = 2\). For (1, 1) it is 0, because the record lies on the first axis.

4. Multiplying the first feature by 10 multiplies its variance by 100 and its covariance with the second feature by 10, so the new covariance matrix is \(S' = \begin{pmatrix} 300 & 10 \\ 10 & 3 \end{pmatrix}\). Its eigenvalues are about 300.34 and 2.66, and the first component, which now explains about 99.1% of the variance, points almost exactly along the first feature (its loading on the second feature is about 0.034). The analysis is now dominated by a choice of units, which is why features are standardized, after a log transform for heavy-tailed counts, before PCA.

1. Adding 0.5772 to \(\ln 63 \approx 4.1431\) gives \(H(63) \approx 4.7203\). Then \(2H(63) \approx 9.4406\) and \(2 \times 63/64 \approx 1.9688\), and \(c(64)\) is their difference, about 7.472.

2. \(2^{-3/7.472} \approx 0.757\) and \(2^{-9/7.472} \approx 0.434\). The first record is isolated quickly and scores well above 0.5; the second needs more splits than an average record and looks normal.

3. No. The scores returned by score_samples are identical in the two fits; contamination only moves the threshold offset_, so the second setting flags more records, about 5% instead of 1% of the training data. It catches more attacks and also raises more false alerts, and every ranking metric, such as AP or precision at k, is unchanged. Lab 4 shows the same effect with the default contamination="auto" and with contamination=0.10. The scores are identical, and the number of test alerts changes from 995 to 1,205. The comparison that matters is precision and recall at the number of alerts the team can investigate.

1. \(P@120 = 45/120 = 0.375\) and recall \(= 45/60 = 0.75\).

2. There are only 60 attacks, so at most 60 of the 120 alerts can be attacks, and \(P@120 \le 60/120 = 0.5\). A random ranking has expected precision equal to the base rate, \(60/12{,}000 = 0.005\). The detector reaches three quarters of the maximum possible precision and is 75 times better than random.

3. Not directly. With 300 attacks the cap \(\min(1, 300/120)\) is 1 instead of \(60/120 = 0.5\), so the same detector could reach a higher precision at 120 on the second period without ranking any better, simply because attacks are more numerous there. Compare detectors on the same period, or report precision together with the number of attacks (or the maximum achievable precision) and recall at the budget.

For LOF, the recall of denial of service among the top 100 falls from 0.74 with clean training data to 0.04 with contaminated data. The training period contains denial-of-service records from days 2 and 6. When they are part of the training data, a test denial-of-service record finds them among its 20 nearest neighbors, its local density is similar to theirs, and its LOF is close to 1. For the isolation forest the recall of this family is 0.42 in the clean setting and 0.84 in the contaminated one. Each tree sees only 256 random training records, so a few hundred training attacks are rarely numerous enough in a subsample to shield similar test records. In this data their presence even raised the recall of denial of service.

One proposal is to increase n_neighbors well above the size of the attack groups in the training data, so that each neighborhood is dominated by normal records. Another is to fit LOF on a random subsample of the training data, in the spirit of the isolation forest. The test below reuses the lab's variables and takes a minute or two on a laptop CPU.

for k in (20, 100, 300):
    lof = LocalOutlierFactor(n_neighbors=k, novelty=True)
    lof.fit(Z[settings["contaminated"]])
    s = -lof.score_samples(Z_test)
    print(k, round(average_precision_score(y_test, s), 3))

Whatever the printed values, this loop scores the test period, so it shows whether a larger neighborhood reduces the damage done by contamination but cannot be used to pick n_neighbors; keeping the value with the highest test AP would tune it on the test data. To choose a value, compare the candidates on a validation period held out from the end of the training period, and score the test period once with the chosen value (Lesson 2.2).

A reasonable design has five parts. For the data, use flow features with log transforms and standardization fitted on a training window of a few weeks, and remove exact duplicates first. Since nobody has labeled the traffic, the training data is contaminated; prefer a detector that tolerated contamination in an offline test (in Lab 4, the isolation forest), or invest a few analyst days in reviewing a sample of the training window and removing obvious attacks, which turns outlier detection into approximate novelty detection.

For the threshold, rank each day's records by score and alert on the top 40, or carry over the 40th-highest score of the previous day as the threshold. Do not set contamination to a guessed attack rate.

Known benign behavior needs explicit treatment. Backups and the scanner are rare and unusual, so they will fill the top of the list (Lab 4 shows this for backups and for the misconfigured service). Handle them with knowledge, not with a different algorithm. Maintain an allow-list of the backup hosts and time windows and of the scanner's address and schedule, and score those records separately or not at all. Revisit the list when the schedule changes, and alert if the scanner's address appears outside its window, since an attacker may try to hide behind it.

For evaluation, record the analyst verdict for every alert, which gives precision at 40 each day at no extra cost. Estimate recall by reviewing a small random sample of unflagged records periodically, and inject or replay known attack traffic (red-team exercises) to measure per-family detection. Report precision at the budget and per-family recall, not only AP.

For maintenance, retrain on a rolling window that excludes alerts confirmed as attacks and anything not yet reviewed near the threshold, so that undetected attacks are not learned as normal, and monitor the score distribution for drift.