natural language toolkit clusterers c 20012023 nltk project trevor cohn tacohncs mu oz au url https www nltk org for license information see license txt this module contains a number of basic clustering algorithms clustering describes the task of discovering groups of similar items with a large collection it is also describe as unsupervised machine learning as the data from which it learns is unannotated with class information as is the case for supervised learning annotated data is difficult and expensive to obtain in the quantities required for the majority of supervised learning algorithms this problem the knowledge acquisition bottleneck is common to most natural language processing tasks thus fueling the need for quality unsupervised approaches this module contains a kmeans clusterer em clusterer and a group average agglomerative clusterer gaac all these clusterers involve finding good cluster groupings for a set of vectors in multidimensional space the kmeans clusterer starts with k arbitrary chosen means then allocates each vector to the cluster with the closest mean it then recalculates the means of each cluster as the centroid of the vectors in the cluster this process repeats until the cluster memberships stabilise this is a hillclimbing algorithm which may converge to a local maximum hence the clustering is often repeated with random initial means and the most commonly occurring output means are chosen the gaac clusterer starts with each of the n vectors as singleton clusters it then iteratively merges pairs of clusters which have the closest centroids this continues until there is only one cluster the order of merges gives rise to a dendrogram a tree with the earlier merges lower than later merges the membership of a given number of clusters c 1 c n can be found by cutting the dendrogram at depth c the gaussian em clusterer models the vectors as being produced by a mixture of k gaussian sources the parameters of these sources prior probability mean and covariance matrix are then found to maximise the likelihood of the given data this is done with the expectation maximisation algorithm it starts with k arbitrarily chosen means priors and covariance matrices it then calculates the membership probabilities for each vector in each of the clusters this is the e step the cluster parameters are then updated in the m step using the maximum likelihood estimate from the cluster membership probabilities this process continues until the likelihood of the data does not significantly increase they all extend the clusteri interface which defines common operations available with each clusterer these operations include cluster clusters a sequence of vectors classify assign a vector to a cluster classificationprobdist give the probability distribution over cluster memberships the current existing classifiers also extend cluster vectorspace an abstract class which allows for singular value decomposition svd and vector normalisation svd is used to reduce the dimensionality of the vector space in such a manner as to preserve as much of the variation as possible by reparameterising the axes in order of variability and discarding all bar the first d dimensions normalisation ensures that vectors fall in the unit hypersphere usage example see also demo from nltk import cluster from nltk cluster import euclideandistance from numpy import array vectors arrayf for f in 3 3 1 2 4 2 4 0 initialise the clusterer will also assign the vectors to clusters clusterer cluster kmeansclusterer2 euclideandistance clusterer clustervectors true classify a new vector printclusterer classifyarray3 3 note that the vectors must use numpy arraylike objects nltkcontrib unimelb tacohn sparsearrays may be used for efficiency when required natural language toolkit clusterers c 2001 2023 nltk project trevor cohn tacohn cs mu oz au url https www nltk org for license information see license txt this module contains a number of basic clustering algorithms clustering describes the task of discovering groups of similar items with a large collection it is also describe as unsupervised machine learning as the data from which it learns is unannotated with class information as is the case for supervised learning annotated data is difficult and expensive to obtain in the quantities required for the majority of supervised learning algorithms this problem the knowledge acquisition bottleneck is common to most natural language processing tasks thus fueling the need for quality unsupervised approaches this module contains a k means clusterer e m clusterer and a group average agglomerative clusterer gaac all these clusterers involve finding good cluster groupings for a set of vectors in multi dimensional space the k means clusterer starts with k arbitrary chosen means then allocates each vector to the cluster with the closest mean it then recalculates the means of each cluster as the centroid of the vectors in the cluster this process repeats until the cluster memberships stabilise this is a hill climbing algorithm which may converge to a local maximum hence the clustering is often repeated with random initial means and the most commonly occurring output means are chosen the gaac clusterer starts with each of the n vectors as singleton clusters it then iteratively merges pairs of clusters which have the closest centroids this continues until there is only one cluster the order of merges gives rise to a dendrogram a tree with the earlier merges lower than later merges the membership of a given number of clusters c 1 c n can be found by cutting the dendrogram at depth c the gaussian em clusterer models the vectors as being produced by a mixture of k gaussian sources the parameters of these sources prior probability mean and covariance matrix are then found to maximise the likelihood of the given data this is done with the expectation maximisation algorithm it starts with k arbitrarily chosen means priors and covariance matrices it then calculates the membership probabilities for each vector in each of the clusters this is the e step the cluster parameters are then updated in the m step using the maximum likelihood estimate from the cluster membership probabilities this process continues until the likelihood of the data does not significantly increase they all extend the clusteri interface which defines common operations available with each clusterer these operations include cluster clusters a sequence of vectors classify assign a vector to a cluster classification_probdist give the probability distribution over cluster memberships the current existing classifiers also extend cluster vectorspace an abstract class which allows for singular value decomposition svd and vector normalisation svd is used to reduce the dimensionality of the vector space in such a manner as to preserve as much of the variation as possible by reparameterising the axes in order of variability and discarding all bar the first d dimensions normalisation ensures that vectors fall in the unit hypersphere usage example see also demo from nltk import cluster from nltk cluster import euclidean_distance from numpy import array vectors array f for f in 3 3 1 2 4 2 4 0 initialise the clusterer will also assign the vectors to clusters clusterer cluster kmeansclusterer 2 euclidean_distance clusterer cluster vectors true classify a new vector print clusterer classify array 3 3 note that the vectors must use numpy array like objects nltk_contrib unimelb tacohn sparsearrays may be used for efficiency when required
from nltk.cluster.em import EMClusterer
from nltk.cluster.gaac import GAAClusterer
from nltk.cluster.kmeans import KMeansClusterer
from nltk.cluster.util import (
    Dendrogram,
    VectorSpaceClusterer,
    cosine_distance,
    euclidean_distance,
)