Mining for Groups Using Clustering Algorithms

How do we express groups of similar data objects in a machine?

If we have a data set that contains many items that are similar, one way to represent groups of similar items is to apply clustering algorithms to the set. A clustering algorithm will use similarity metrics to evaluate how similar data objects are. Once these similarity scores are procured, they can be used to place the objects in groups. Groups, or clusters, of similar objects can then be visualized through scatter plots, dendrograms, or by other means.

Hierarchical Clustering

Hierarchical Diagram

The hierarchical clustering algorithm consists of two different flavors: agglomerative clustering and divisive clustering. Both of these techniques involve building some type of dendrogram or tree that reveals the relationships between the data objects in a data set (see the image above). Agglomerative clustering begins with each data object being its own cluster. The next step is to identify which clusters are the closest to others using a distance metric. The similar objects are then formed into bigger clusters of objects. Each iteration of this approach creates bigger and bigger clusters at each level until one giant cluster of all the objects remains. Each level of clusters can then be analyzed to determine the groups of similar data objects that formed. Divisive clustering is just the opposite of hierarchical in that it starts with one giant cluster containing all data objects, and then divides into smaller clusters after each iteration. It ends when each data object is its own cluster.

K-Means Clustering

K-Means Diagram

K-Means clustering is also an iterative clustering procedure, but it predefines the number of clusters that will be in your dataset. The algorithm begins by defining "centroids", which are points that will eventually migrate to the center of each cluster. The number of centroids chosen therefore determines the number of clusters in the dataset. The centroids are placed at random spots in the dataset. We then choose a distance metric to determine how far away each centroid is from each of the data objects. The distances of the objects that are closest to each of the centroids are then averaged, and the centroid is then moved to the center of the respective data objects. The process is then repeated by finding new distances from each of data objects to the centroids. The algorithm ends when the centroids no longer move within a certain threshold of distance. The closest data objects to each of the centroids are the resultant clusters. This process is similar to hierarchical in that it uses a distance metric to form clusters. It is different in that the number of clusters for k-means is predefined, where as hierarchical clustering creates levels of clusters.

Heirarchical Implementation

The following code is the python implementation of a hierarchical clustering algorithm. The algorithm takes in a similarity metric and uses it to find similar objects in a vector.

  # This function performs the hierarchical algorithm for clustering the sets of data
  def hcluster(rows,distance=pearson):

  # Each cluster is a row of data
  cluster=[bicluster(rows[i],id=i) for i in range(len(rows))]

  while len(cluster)>1:

    # loop through each cluster looking for the smallest distance between each
    for i in range(len(cluster)):
      for j in range(i+1,len(cluster)):
        # the 'distances' array holds the result of the distance metric calculation between each cluster
        if (cluster[i].id,cluster[j].id) not in distances: 

        # Find the closest pairs of clusters
        if dist greater than closest:

    # Calculate the average distance between the two clusters
    for i in range(len(cluster[0].vec))]

    # Create a new cluster from the two closest clusters using the average distance (merge_vector)

    # Set the cluster id to negative for clusters not contained in the original set
    del cluster[lowestpair[1]]
    del cluster[lowestpair[0]]

  return cluster[0]

K-Means Implementation

The following python code implements the K-Means clustering algorithm. It also has a similarity metric as an argument.

  # This function implements the K-Means clustering algorithm
  def kcluster(rows,distance=pearson,k=4):
  # For each point, find the minimum and maximum values
  ranges=[(min([row[i] for row in rows]),max([row[i] for row in rows])) 
  for i in range(len(rows[0]))]

  # Create and randomly place the centroids for a defined k
  for i in range(len(rows[0]))] for j in range(k)]
  for t in range(100):
    print 'Iteration %d' % t
    bestmatches=[[] for i in range(k)]
    # Determine the closest centroid to each row of data
    for j in range(len(rows)):
      for i in range(k):
        if d lessthan distance(clusters[bestmatch],row): bestmatch=i

    # End the loop when all rows have located the best centroids and the cycle produces the same result as last time
    if bestmatches==lastmatches: break
    # Relocate the centroid to the average distance of its matching rows
    for i in range(k):
      if len(bestmatches[i]) greaterthan 0:
        for rowid in bestmatches[i]:
          for m in range(len(rows[rowid])):
        for j in range(len(averages)):
  return bestmatches

NOTE: The python code was obtained from the book Collective Intelligence written by Toby Segaran. The images were pulled from Wikipedia.