Groups That Are Not Blobs

Last timeHow Many Groups Are There

Grouping by how crowded a neighbourhood is finds groups of any shape, leaves points unassigned rather than forcing them somewhere, and needs no number of groups chosen in advance.

A different definition of a group

The previous method defined a group as the points nearest to a centre. That is

why it could only find round blobs: the definition has a centre in it.

Here is another definition with no centre in it. A group is a crowded region

of the space, together with every crowded region joined onto it.

Make that precise with two numbers. A radius, and a count. A point is crowded

if at least the count many points lie within the radius of it. Two crowded

points that lie within the radius of each other belong to the same group. And

a point that is not crowded but lies within the radius of a crowded point is

attached to that group as an edge member.

FIG 1The crowding test for one point

: the radius, the only setting that really matters
: the count of neighbours needed, including the point itself
: the distance from the second lesson, still a decision

Everything in the method follows from this one test applied to every point. There is no number of groups in it, no centre, and no assumption about shape: a group is however far the crowding extends, which may be a round blob, a long thread, a ring, or a shape with holes in it.

Notice what is absent. Nobody said how many groups there are. The number of

groups is whatever the crowding produces, which is the right way round: the

number is an output rather than an input.

FIG 2Growing one group outwards from a crowded point

python

def grow(points, start, radius, count, label, labels):
    queue = [start]
    while queue:
        i = queue.pop()
        near = [j for j in range(len(points)) if dist(points[i], points[j]) <= radius]
        if len(near) < count: continue        # an edge member, joined but not extended from
        for j in near:
            if labels[j] is None:
                labels[j] = label
                queue.append(j)               # crowded neighbours carry the group onwards
print("a group is however far the crowding reaches, with no shape assumed anywhere")

The whole method is this routine started at each unlabelled crowded point in turn, with a new label each time. The line that does the real work is the skipped extension: an edge member joins the group but does not pass it on, which is what stops two groups that nearly touch from being joined by a single point sitting between them.

The two rings, revisited

The previous lesson ended with a small ring of points inside a large one,

which centres cannot separate because both rings have the same centre.

Crowding separates them immediately and without being told anything. Each ring

is a crowded region. The gap between them is empty, so no point of one ring

lies within the radius of a point of the other, and the two never join. The

shapes do not matter at all, only where the points are dense and where they

are not.

The lesson stops here

4 more paragraphs to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents

Groups That Are Not Blobs

A different definition of a group

The two rings, revisited

4 more paragraphs to go

This is the reading half

Read alongside