1
2
3
4
5
6
7
8 """
9 This module contains a number of basic clustering algorithms. Clustering
10 describes the task of discovering groups of similar items with a large
11 collection. It is also describe as unsupervised machine learning, as the data
12 from which it learns is unannotated with class information, as is the case for
13 supervised learning. Annotated data is difficult and expensive to obtain in
14 the quantities required for the majority of supervised learning algorithms.
15 This problem, the knowledge acquisition bottleneck, is common to most natural
16 language processing tasks, thus fueling the need for quality unsupervised
17 approaches.
18
19 This module contains a k-means clusterer, E-M clusterer and a group average
20 agglomerative clusterer (GAAC). All these clusterers involve finding good
21 cluster groupings for a set of vectors in multi-dimensional space.
22
23 The K-means clusterer starts with k arbitrary chosen means then allocates each
24 vector to the cluster with the closest mean. It then recalculates the means of
25 each cluster as the centroid of the vectors in the cluster. This process
26 repeats until the cluster memberships stabilise. This is a hill-climbing
27 algorithm which may converge to a local maximum. Hence the clustering is
28 often repeated with random initial means and the most commonly occurring
29 output means are chosen.
30
31 The GAAC clusterer starts with each of the M{N} vectors as singleton clusters.
32 It then iteratively merges pairs of clusters which have the closest centroids.
33 This continues until there is only one cluster. The order of merges gives rise
34 to a dendrogram - a tree with the earlier merges lower than later merges. The
35 membership of a given number of clusters M{c}, M{1 <= c <= N}, can be found by
36 cutting the dendrogram at depth M{c}.
37
38 The Gaussian EM clusterer models the vectors as being produced by a mixture
39 of k Gaussian sources. The parameters of these sources (prior probability,
40 mean and covariance matrix) are then found to maximise the likelihood of the
41 given data. This is done with the expectation maximisation algorithm. It
42 starts with k arbitrarily chosen means, priors and covariance matrices. It
43 then calculates the membership probabilities for each vector in each of the
44 clusters - this is the 'E' step. The cluster parameters are then updated in
45 the 'M' step using the maximum likelihood estimate from the cluster membership
46 probabilities. This process continues until the likelihood of the data does
47 not significantly increase.
48
49 They all extend the ClusterI interface which defines common operations
50 available with each clusterer. These operations include.
51 - cluster: clusters a sequence of vectors
52 - classify: assign a vector to a cluster
53 - classification_probdist: give the probability distribution over cluster memberships
54
55 The current existing classifiers also extend cluster.VectorSpace, an
56 abstract class which allows for singular value decomposition (SVD) and vector
57 normalisation. SVD is used to reduce the dimensionality of the vector space in
58 such a manner as to preserve as much of the variation as possible, by
59 reparameterising the axes in order of variability and discarding all bar the
60 first d dimensions. Normalisation ensures that vectors fall in the unit
61 hypersphere.
62
63 Usage example (see also demo())::
64 from nltk import cluster
65 from nltk.cluster import euclidean_distance
66 from numpy import array
67
68 vectors = [array(f) for f in [[3, 3], [1, 2], [4, 2], [4, 0]]]
69
70 # initialise the clusterer (will also assign the vectors to clusters)
71 clusterer = cluster.KMeansClusterer(2, euclidean_distance)
72 clusterer.cluster(vectors, True)
73
74 # classify a new vector
75 print clusterer.classify(array([3, 3]))
76
77 Note that the vectors must use numpy array-like
78 objects. nltk_contrib.unimelb.tacohn.SparseArrays may be used for
79 efficiency when required.
80 """
81
82 from util import *
83 from kmeans import *
84 from gaac import *
85 from em import *
86
87 __all__ = ['KMeansClusterer', 'GAAClusterer', 'EMClusterer',
88 'VectorSpaceClusterer', 'Dendrogram']
89