natural language toolkit group average agglomerative clusterer c 20012023 nltk project trevor cohn tacohncs mu oz au url https www nltk org for license information see license txt the group average agglomerative 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 this clusterer uses the cosine similarity metric only which allows for efficient speedup in the clustering process stores the merge order variables describing the initial situation construct the similarity matrix update similarities for merging i and j remove j merge the clusters update the index map to reflect the indexes if we had removed j the new cluster i merged from i and j adopts the average of i and j s similarity to each other cluster weighted by the number of points in the clusters i and j update for xi update for ixj update for ijx return the dendrogram representing the current clustering rtype dendrogram noninteractive demonstration of the clusterers with simple 2d data use a set of tokens with 2d indices test the gaac clusterer with 4 clusters show the dendrogram classify a new vector natural language toolkit group average agglomerative clusterer c 2001 2023 nltk project trevor cohn tacohn cs mu oz au url https www nltk org for license information see license txt the group average agglomerative 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 this clusterer uses the cosine similarity metric only which allows for efficient speed up in the clustering process stores the merge order variables describing the initial situation construct the similarity matrix update similarities for merging i and j remove j merge the clusters update the index map to reflect the indexes if we had removed j the new cluster i merged from i and j adopts the average of i and j s similarity to each other cluster weighted by the number of points in the clusters i and j update for x i update for i x j update for i j x return the dendrogram representing the current clustering rtype dendrogram non interactive demonstration of the clusterers with simple 2 d data use a set of tokens with 2d indices test the gaac clusterer with 4 clusters show the dendrogram classify a new vector
try:
    import numpy
except ImportError:
    pass

from nltk.cluster.util import Dendrogram, VectorSpaceClusterer, cosine_distance


class GAAClusterer(VectorSpaceClusterer):
    

    def __init__(self, num_clusters=1, normalise=True, svd_dimensions=None):
        VectorSpaceClusterer.__init__(self, normalise, svd_dimensions)
        self._num_clusters = num_clusters
        self._dendrogram = None
        self._groups_values = None

    def cluster(self, vectors, assign_clusters=False, trace=False):
        
        self._dendrogram = Dendrogram(
            [numpy.array(vector, numpy.float64) for vector in vectors]
        )
        return VectorSpaceClusterer.cluster(self, vectors, assign_clusters, trace)

    def cluster_vectorspace(self, vectors, trace=False):
        
        N = len(vectors)
        cluster_len = [1] * N
        cluster_count = N
        index_map = numpy.arange(N)

        
        dims = (N, N)
        dist = numpy.ones(dims, dtype=float) * numpy.inf
        for i in range(N):
            for j in range(i + 1, N):
                dist[i, j] = cosine_distance(vectors[i], vectors[j])

        while cluster_count > max(self._num_clusters, 1):
            i, j = numpy.unravel_index(dist.argmin(), dims)
            if trace:
                print("merging %d and %d" % (i, j))

            
            self._merge_similarities(dist, cluster_len, i, j)

            
            dist[:, j] = numpy.inf
            dist[j, :] = numpy.inf

            
            cluster_len[i] = cluster_len[i] + cluster_len[j]
            self._dendrogram.merge(index_map[i], index_map[j])
            cluster_count -= 1

            
            
            index_map[j + 1 :] -= 1
            index_map[j] = N

        self.update_clusters(self._num_clusters)

    def _merge_similarities(self, dist, cluster_len, i, j):
        
        
        
        i_weight = cluster_len[i]
        j_weight = cluster_len[j]
        weight_sum = i_weight + j_weight

        
        dist[:i, i] = dist[:i, i] * i_weight + dist[:i, j] * j_weight
        dist[:i, i] /= weight_sum
        
        dist[i, i + 1 : j] = (
            dist[i, i + 1 : j] * i_weight + dist[i + 1 : j, j] * j_weight
        )
        
        dist[i, j + 1 :] = dist[i, j + 1 :] * i_weight + dist[j, j + 1 :] * j_weight
        dist[i, i + 1 :] /= weight_sum

    def update_clusters(self, num_clusters):
        clusters = self._dendrogram.groups(num_clusters)
        self._centroids = []
        for cluster in clusters:
            assert len(cluster) > 0
            if self._should_normalise:
                centroid = self._normalise(cluster[0])
            else:
                centroid = numpy.array(cluster[0])
            for vector in cluster[1:]:
                if self._should_normalise:
                    centroid += self._normalise(vector)
                else:
                    centroid += vector
            centroid /= len(cluster)
            self._centroids.append(centroid)
        self._num_clusters = len(self._centroids)

    def classify_vectorspace(self, vector):
        best = None
        for i in range(self._num_clusters):
            centroid = self._centroids[i]
            dist = cosine_distance(vector, centroid)
            if not best or dist < best[0]:
                best = (dist, i)
        return best[1]

    def dendrogram(self):
        
        return self._dendrogram

    def num_clusters(self):
        return self._num_clusters

    def __repr__(self):
        return "<GroupAverageAgglomerative Clusterer n=%d>" % self._num_clusters


def demo():
    

    from nltk.cluster import GAAClusterer

    
    vectors = [numpy.array(f) for f in [[3, 3], [1, 2], [4, 2], [4, 0], [2, 3], [3, 1]]]

    
    clusterer = GAAClusterer(4)
    clusters = clusterer.cluster(vectors, True)

    print("Clusterer:", clusterer)
    print("Clustered:", vectors)
    print("As:", clusters)
    print()

    
    clusterer.dendrogram().show()

    
    vector = numpy.array([3, 3])
    print("classify(%s):" % vector, end=" ")
    print(clusterer.classify(vector))
    print()


if __name__ == "__main__":
    demo()