Example of Single Pass Clustering Technique

Suppose that we have the following set of documents and terms, and that
we are interested in clustering the terms using the single pass method
(note that the same method can beused to cluster the documents, but in
that case, we would be using the document vectors (rows) rather than the
term vector (columns).

	T1	T2	T3	T4	T5
Doc1	1	2	0	0	1
Doc2	3	1	2	3	0
Doc3	3	0	0	0	1
Doc4	2	1	0	3	0
Doc5	2	2	1	5	1

Start with T1 in a cluster by itself, say C1. At this point, C1 contains
only one item, T1, so the centroid of C1 is simply the vector for T1:

C1 = <1, 3, 3, 2, 2>.

Now compare (i.e., measure similarities) of the next item (T2) to centroids
of all existing clusters. At this point we have only one cluster, C1 (we
will use dot product for simplicity):

SIM(T2, C1) = 1*2 + 1*3 + 0*3 + 1*2 + 2*2 = 11

Now we need a pre-specified similarity threshold. Let's say that our
threshold is 10. This means that if the similarity of T2 to the cluster
centroid is >= 10, then we add T2 to the cluster, otherwise we use T2 to
start a new cluster.

In this case. SIM(T2, C1) = 11 > 10. Therefore we add T2 to cluster C1.
We now need to compute the new centroid for C1 (which now contains T1 and
T2). The centroid (which is the average vector for T1 and T2 is:

C1 = <3/2, 4/2, 3/2, 3/2, 4/2>

Now, we move to the next item, T3. Again, there is only one cluster, C1,
so we only need to compare T3 with C1 centroid. The dot product of T3 and
the above centroid is:

SIM(T3, C1) = 0 + 8/2 + 0 + 0 + 4/2 = 6

This time, T3 does not pass the threshold test (the similarity is less
than 10). Therefore, we use T3 to start a new cluster, C2. Now we have two
clusters

C1 = {T1, T2}
C2 = {T3}

We move to the next unclustered item, T4. Since we now have two clusters,
we need to compute the MAX similarity of T4 to the 2 cluster centroids
(note that the centroid of cluster C2 right now is just the vector for T3):

SIM(T4, C1) = <0, 3, 0, 3, 5> . <3/2, 4/2, 3/2, 3/2, 4/2>
            = 0 + 12/2 + 0 + 9/2 + 20/2 = 20.5

SIM(T4, C2) = <0, 3, 0, 3, 5> . <0, 2, 0, 0, 1>
            = 0 + 6 + 0 + 0 + 5 = 11

Note that both similarity scores pass the threshold (10), however, we pick
the MAX, and therefore, T4 will be added to cluster C1. Now we have the
following:

C1 = {T1, T2, T4}
C2 = {T3}

The centroid for C2 is still just the vector for T3:

C2 = <0, 2, 0, 0, 1>

and the new centroid for C1 is now:

C1 = <3/3, 7/3, 3/3, 6/3, 9/3>

The only item left unclustered is T5. We compute its similarity to the
centroids of existing clusters:

SIM(T5, C1) = <1, 0, 1, 0, 1> . <3/3, 7/3, 3/3, 6/3, 9/3>
            = 3/3 + 0 + 3/3 + 0 + 9/3 = 5

SIM(T5, C2) = <1, 0, 1, 0, 1> . <0, 2, 0, 0, 1>
            = 0 + 0 + 0 + 0 +1 = 1

Neither of these similarity values pass the threshold. Therefore, T5 will
have to go into a new cluster C3. There are no more unclustered items, so
we are done (after making a single pass through the items). The final
clusters are:

C1 = {T1, T2, T4}
C2 = {T3}
C3 = {T5}

Note: Obviously, the results for this method are highly dependent on the
similarity threshold that is used. You should use your judgment in setting
this threshold so that you are left with a reasonable number of clusters.