Clustering
5 problems from Rosalind — Bioinformatics Textbook Track. Press Run on any block to execute it in your browser.
BA8A — Implement FarthestFirstTraversal
solved Problem statement
Each new center is the point furthest from all chosen so far. Deterministic, unlike k-means, which is why it is used to seed clustering rather than to do it.
BA8B — Compute the Squared Error Distortion
solved Problem statement
Squared, so one badly placed point counts for far more than several slightly-off ones. This is the quantity k-means minimises.
BA8C — Implement the Lloyd Algorithm for k-Means Clustering
solved Problem statement
Assign, then move each center to the mean of what it was assigned, until nothing moves. Seeded with the first k points because Lloyd's converges differently from different seeds — which is what BA8A exists to address.
BA8D — Implement the Soft k-Means Clustering Algorithm
solved Problem statement
Where BA8C forces every point to pick one cluster, here a point midway between two centers pulls on both. Beta sets how decisive that sharing is: large beta reproduces Lloyd, small beta drags every center towards the overall mean.
BA8E — Implement Hierarchical Clustering
solved Problem statement
Needs no k. Produces a nested family of partitions rather than one — which is what a phylogenetic tree is. Average linkage is specified and it matters: single linkage chains elongated clusters, complete linkage insists on compactness.