Documentation
¶
Overview ¶
Package cluster groups embedded repositories into candidate star lists.
Index ¶
- Constants
- func Describe(l Label) string
- func Place(sp *embed.Space, r *Result, todo []int, opt PlaceOptions) int
- type Label
- type Options
- type PlaceOptions
- type RefineOptions
- type Result
- func Agglomerate(sp *embed.Space, k int) *Result
- func AgglomerateContext(ctx context.Context, sp *embed.Space, k int) *Result
- func Consensus(sp *embed.Space, opt Options, runs int) *Result
- func ConsensusContext(ctx context.Context, sp *embed.Space, opt Options, runs int) *Result
- func DropUnnamed(docs []textproc.Doc, sp *embed.Space, r *Result, minCoverage float64) *Result
- func FromMembership(sp *embed.Space, assign []int, also [][]int, k int) *Result
- func MergeDuplicates(docs []textproc.Doc, sp *embed.Space, r *Result, minOverlap float64) *Result
- func Refine(sp *embed.Space, r *Result, opt RefineOptions) *Result
- func Run(sp *embed.Space, opt Options) *Result
- func RunContext(ctx context.Context, sp *embed.Space, opt Options) *Result
- func Soften(sp *embed.Space, r *Result, ratio float64, maxLists int) *Result
Constants ¶
const ( MaxListName = 32 MaxListDescription = 160 )
MaxListName and MaxListDescription mirror the limits the GitHub star list form enforces.
const DescriptionMarker = "Grouped by constellation."
DescriptionMarker closes every description this tool writes, so that a list it manages can be told from one made by hand. Reconciling deletes lists and empties them, and it must never touch a list somebody curated themselves.
It sits at the end rather than the front so the description reads as a description, with the attribution as a footnote.
Variables ¶
This section is empty.
Functions ¶
func Describe ¶
Describe writes a list description from what distinguishes the category.
It names the subject rather than listing members: a reader of "Repositories about Helm, charts and plugins" learns what belongs there, where a couple of example repositories only say what happens to be in it already — and go stale the moment anything is added.
func Place ¶ added in v0.2.0
Place files the given repositories into the clusters that already exist and reports how many it placed. Clusters are not moved, split or re-centred, and no repository outside todo is touched — which is the point: an incremental run must not reshuffle lists a person has already reviewed and applied.
A repository that fits nothing well enough is left unassigned rather than pushed into the nearest category, exactly as a full run would leave it.
Types ¶
type Label ¶
type Label struct {
Name string
TopTerms []string
TermScore []float64
// Lead is the raw term behind the first of TopTerms, before it was made
// readable. Anything that needs to ask how many members actually carry
// what the category is named after needs the term, not its rendering.
Lead string
}
Label is a proposed name for a cluster, together with the evidence behind it so a human can judge — and override — the machine's choice.
type Options ¶
type Options struct {
K int // 0 selects K automatically
MinK, MaxK int
Restarts int
MaxIter int
Seed int64
// SilhouetteSample caps how many repositories take part in the silhouette
// evaluation used to pick K; the full O(n^2) computation is wasteful on
// large star lists and the sampled estimate ranks K just as well.
SilhouetteSample int
}
Options control the k-means search.
type PlaceOptions ¶ added in v0.2.0
type PlaceOptions struct {
MinSimilarity float64
OutlierSigmas float64
// MultiLists and MultiRatio mirror Soften, applied to the newcomer alone.
MultiLists int
MultiRatio float64
}
PlaceOptions govern where a repository that has no category yet may go. They are the same two tests refinement applies, so that a repository arriving later is judged by the bar its neighbours had to clear.
type RefineOptions ¶
type RefineOptions struct {
// MinSize dissolves clusters with fewer members than this, redistributing
// them to their next-nearest cluster. A two-repo list is not a category.
MinSize int
// MaxLists keeps only the N largest clusters; the rest are dissolved.
MaxLists int
// SplitParts is the most pieces an incoherent category may be divided into
// before it is given up on. Zero dissolves it outright.
//
// A residual cluster is not always uniformly bad. It is often a real
// category with a tail of unrelated repositories swept in, so dissolving it
// whole throws away the good part along with the rest — one such cluster
// held a genuine terminal-tools group alongside a calculator and a code
// review checklist. Dividing it first keeps the part that holds together.
SplitParts int
// SplitMinSize is the smallest category worth trying to divide.
SplitMinSize int
// SplitMaxSize divides a category larger than this even when it is
// coherent enough to keep.
//
// A large category is not necessarily a bad one, but it is usually several
// good ones the tree never separated: a real account produced a single
// Kubernetes list of 366 repositories holding core tooling, operators,
// networking and cluster lifecycle together. Nothing about its coherence
// says so, which is why size has to be asked about separately. Zero leaves
// large categories alone.
SplitMaxSize int
// RescueNeighbours is how many nearest neighbours an uncategorized
// repository consults before joining a category. Zero disables it.
//
// It asks a different question from every other test here. The others ask
// whether a repository resembles a category's centre; this asks whether the
// repositories most like it agree on where they belong. A repository can
// fail the first and pass the second — a niche tool sitting at the edge of
// a broad category is far from its centre but surrounded by its members.
RescueNeighbours int
// RescueAgreement is the share of those neighbours that must name the same
// category before it is joined.
RescueAgreement float64
// MinCohesion dissolves a category whose members do not, on average,
// resemble it enough to be a category at all.
//
// This is the one test the per-member outlier check cannot make. That check
// asks whether a repository fits worse than its category's typical member,
// which is calibrated against the category itself — so a category that is
// uniformly incoherent has a low bar and rejects nobody. A bad cluster
// defends its own members.
//
// It matters because k-means has no way to say "this belongs nowhere".
// Every repository must join some centroid, so the leftovers collect into
// two or three enormous residual clusters which then get named after
// whatever small coherent group happens to be inside them. On a real
// account those held a fifth of all stars under names like "ESP32 Arduino"
// while containing neither.
MinCohesion float64
// MinSimilarity is an absolute floor on how well a repository must fit its
// category. It only catches the degenerate cases; what counts as a good
// cosine depends on the embedding, so it is deliberately permissive.
MinSimilarity float64
// OutlierSigmas is the useful test: a repository is left uncategorized when
// its fit falls this many robust deviations below its category's typical
// fit. Star lists always contain a long tail of one-off repositories that
// belong to no category, and forcing them into the nearest one is what
// makes automatic categorization feel wrong. A fixed threshold cannot find
// them — a pair of misfits that resemble each other drag their shared
// centroid towards themselves and so clear any absolute bar — while a
// deviation measured against the category's own spread adapts both to that
// and to the cosine scale the embedding produces.
// 0 disables the test.
OutlierSigmas float64
}
RefineOptions shape the raw k-means output into something worth turning into star lists.
type Result ¶
type Result struct {
// Assign maps a repository index to its cluster index, or -1 when the
// repository was left unassigned because no cluster fit it.
Assign []int
// Also holds any further clusters a repository belongs to. Star lists are
// many-to-many — a Rust command line tool belongs under both — so an
// algorithm that can express partial membership records it here. It is nil
// for the ones that assign each repository to exactly one cluster.
Also [][]int
// Centroids are dense, L2-normalized, one per cluster.
Centroids [][]float64
// K is the number of clusters, and Score the mean cosine similarity of
// each repository to its own centroid.
K int
Score float64
}
Result is one clustering of the corpus.
func Agglomerate ¶
Agglomerate builds clusters by repeatedly merging the two nearest, using Ward linkage.
The reason to prefer it here is that the clustering itself has no random element. That is not the same as the pipeline having none: the randomized SVD that produces the vectors is seeded, and a different --lsa-seed moves the answer more than any documented flag does. What this buys is that the ground stops shifting for a fixed seed. Every other method in this package starts from a guess and improves it, so the guess shows through: measured across seeds, barely half the categories kept their names and the ones that did exchanged a fifth of their members. That is not a defect of k-means so much as a fact about a corpus with no single preferred division — but a method that always returns the same answer at least makes the answer reproducible, and lets a change to the input be read as a change to the input rather than as a reshuffle.
Ward merges the pair that adds least to the total within-cluster variance, which is defined on squared Euclidean distance. The vectors are L2-normalized, so that is simply 2(1-cosine) and the geometry is the same one every other part of this package uses.
Cost is quadratic in both time and memory — around seventy megabytes for a few thousand repositories — which is affordable at this size and would not be at a hundred times it.
func AgglomerateContext ¶
AgglomerateContext is Agglomerate that stops when ctx is cancelled. The two heavy stages — building the pairwise distances and the chain of merges — are each quadratic, so a large corpus spends real time here; without a check a Ctrl-C during clustering does nothing until it finishes. On cancellation it returns whatever it has built, which the caller discards after seeing ctx.Err(); the point is to stop wasting CPU, not to produce a usable answer.
func Consensus ¶
Consensus clusters the agreement between several runs rather than trusting any one of them.
A single k-means run is a local optimum reached from a random start, and on this data the choice of start matters more than it looks: measured on a real account, only eighteen of twenty-nine categories survived a change of seed, and the categories that did keep their names exchanged a quarter of their members. A taxonomy that reshuffles itself when nothing about the input changed is not describing the input.
The method is cluster-based similarity partitioning. Each run is turned into an indicator vector — one dimension per cluster of that run, with a repository marking the cluster it joined — and the vectors are concatenated. The cosine between two repositories in that space is then exactly the fraction of runs that put them together, so clustering it groups repositories the runs agree about and leaves the contested ones to fall where they may. It costs nothing in memory beyond one entry per run per repository, which is what makes it affordable on a corpus this size; a full co-association matrix would be seventeen million entries.
func ConsensusContext ¶ added in v0.2.0
ConsensusContext is Consensus that stops when ctx is cancelled. It is --consensus times as long as a single run, so it is where an interrupt is most needed. On cancellation it hands back whatever the run in progress had built — never nil, see RunContext — rather than an agreement between partial runs, which would describe nothing; the caller discards it after seeing ctx.Err().
func DropUnnamed ¶
DropUnnamed dissolves categories that are not really about the thing they are named after.
A junk drawer is not detectable by coherence. A real account produced a category of 105 repositories called "Retries & Mob" — retry libraries, mob programming, KDE and Debian packaging together — at cohesion 0.49, squarely mid-table and comfortably above any floor worth setting. Vectors can be generically alike without being about anything, and the average distance to their own centre does not notice.
What does notice is asking how many members carry the term the category is named after. On that account every genuine category scored at least 25% and most above 68%; the junk drawer scored 2%. A name that describes two repositories out of a hundred is not a name, and a category that cannot be named is not a category.
Members are released rather than moved: they were swept together precisely because they fitted nothing, so reporting them as uncategorized is the honest outcome.
func FromMembership ¶ added in v0.2.0
FromMembership rebuilds a Result from memberships decided earlier — the categories of a plan written days ago, re-embedded in a fresh space — so that new repositories can be filed into them without re-deriving the categories themselves.
Centroids are derived from every member, including the secondary memberships, because a plan file does not distinguish them: it records the repositories in each category, not which category claimed them first.
func MergeDuplicates ¶
MergeDuplicates folds together categories that describe the same thing.
Cutting a dendrogram at a fixed height sometimes separates one category into two. A real account produced "Prometheus Exporter" and "Exporter & Metrics" side by side, both at cohesion 0.75, sharing most of their terms — two lists nobody would have made on purpose.
The test is the overlap between their describing terms, not the distance between their centroids. In a latent space every centroid points broadly the same way, so unrelated categories already look similar there and a test built on it collapses everything into a handful of lists; whereas the terms that distinguish a category from the others are, by construction, what makes it a different category. On that account the duplicated pair overlapped by 0.33 and the next closest pair by 0.20, which is a gap wide enough to sit a threshold in.
func Refine ¶
func Refine(sp *embed.Space, r *Result, opt RefineOptions) *Result
Refine mutates r in place and returns it, renumbering clusters so that the surviving ones are contiguous and ordered by descending size.
func RunContext ¶ added in v0.2.0
RunContext is Run that stops when ctx is cancelled.
The search is restarts times K candidates times Lloyd iterations, each of them a pass over every repository, so a large corpus spends minutes here; without a check a Ctrl-C during clustering did nothing until it finished. The context is looked at between K candidates, between restarts and once per Lloyd iteration — each of those is a full O(n·k·dim) pass, so the check costs nothing measurable.
On cancellation it returns what it has built so far, never nil: the best completed restart if there is one, otherwise the partial run it was in the middle of, which may still have every repository unassigned. The caller discards it after seeing ctx.Err(); the point is to stop wasting CPU, not to produce a usable answer. Returning nil instead would make every caller — Consensus, the refinement, the tests — guard against a case that only exists to be thrown away.
func Soften ¶
Soften adds secondary list memberships, so that a repository which belongs in more than one category is filed in more than one.
Star lists are many-to-many and a Rust command line tool genuinely belongs under both headings, but every clustering algorithm here returns a partition. This is the step that recovers what the partition threw away, and it is deliberately separate from the algorithms: it applies equally to all of them, and it runs after refinement so that it can only ever add a repository to a list that survived.
Membership is judged by how a repository's similarity to another centroid compares with the similarity to its own, rather than by an absolute number or by a mixture's posteriors. A ratio means the same thing whatever the backend and however many dimensions it produces; posteriors do not, since they saturate to zero and one as dimensions grow, and an absolute cosine threshold is differently strict for a tight category than a broad one.
ratio is how close a further category must come, as a fraction of the best fit; maxLists caps the total a single repository may join. A maxLists of one leaves the partition alone.
Source Files