w3resource

Python Math: Calculate clusters using Hierarchical Clustering method

Python Math: Exercise-75 with Solution

Write a Python program to calculate clusters using the Hierarchical Clustering method.

Sample Solution:

Python Code:

#https://gist.github.com/vineetrok/1391954

import math

def distance(a,b):
    x=float(a[0])-float(b[0])
    x=x*x
    y=float(a[1])-float(b[1])
    y=y*y
    dist=round(math.sqrt(x+y),2)
    return dist

def minimum(matrix):
    p=[0,0]
    mn=1000
    for i in range(0,len(matrix)):        
        for j in range(0,len(matrix[i])):            
            if (matrix[i][j]>0 and matrix[i][j]<mn):
                mn=matrix[i][j]
                p[0]=i
                p[1]=j
    return p 
            
def newpoint(pt):
    x=float(pt[0][0])+float(pt[1][0])
    x=x/2
    y=float(pt[0][1])+float(pt[1][1])
    y=y/2
    midpoint=[x,y]
    return midpoint

if __name__ == '__main__':    
    n=int(input("Input number of points.> "))
    points=list()
    outline='['
    i=0

    while(i<n):
        s=input("Input point (eg. 1,1)"+chr(65+i)+"> ")
        c=s.split(",")
        points.append(c)
        i=i+1

    names={}

    for i in range(0,len(points)):
        names[str(points[i])]=chr(65+i)
    l=0
    while(len(points)>1):
        l=l+1
        matrix=list()
        print('Distance matrix no. '+str(l)+': ')
        for i in range(0,len(points)):
            m=[]
            for j in range(0,len(points)):
                m.append(0)
            for j in range(0,len(points)):
                m[j]=distance(points[i],points[j])
            print(str(m))
            matrix.append(m)
        
        m=minimum(matrix)
        pts=list()
        p1=points[m[0]]
        pts.append(p1)
        points.remove(p1)
        p2=points[m[1]-1]
        pts.append(p2)
        points.remove(p2)   
        midpoint=newpoint(pts)
        points.append(midpoint)    
        c1=names.pop(str(p1))
        c2=names.pop(str(p2))
        names[str(midpoint)]="["+str(c1)+str(c2)+"]"    
        outline=names[str(midpoint)]
        
    print("Cluster is :",names[str(midpoint)])

Sample Output:

Input number of points.> 2                                          
Input point (eg. 1,1)A> 1,2                                         
Input point (eg. 1,1)B> 3,4                                         
Distance matrix no.1:                                               
[0.0, 2.83]                                                         
[2.83, 0.0]                                                         
Cluster is : [AB] 

Flowchart:

Flowchart: Calculate clusters using Hierarchical Clustering method

Python Code Editor:

Have another way to solve this solution? Contribute your code (and comments) through Disqus.

Previous: Write a Python program to select a random date in the current year.
Next: Write a Python program to implement Euclidean Algorithm to compute the greatest common divisor (gcd).

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Follow us on Facebook and Twitter for latest update.