Skip to content

A Python implementation of divisive and hierarchical clustering algorithms. The algorithms were tested on the Human Gene DNA Sequence dataset and dendrograms were plotted.

Notifications You must be signed in to change notification settings

shubhamjha97/hierarchical-clustering

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

13 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Agglomerative and Divisive Hierarchical Clustering

Course Assignment for CS F415- Data Mining @ BITS Pilani, Hyderabad Campus.

Done under the guidance of Dr. Aruna Malapati, Assistant Professor, BITS Pilani, Hyderabad Campus.

Table of contents

Table of contents generated with markdown-toc

Introduction

Hierarchical clustering is a method of cluster analysis which seeks to build a hierarchy of clusters. Strategies for hierarchical clustering generally fall into two types:

  1. Agglomerative: This is a "bottom up" approach: each observation starts in its own cluster, and pairs of clusters are merged as one moves up the hierarchy.

  2. Divisive: This is a "top down" approach: all observations start in one cluster, and splits are performed recursively as one moves down the hierarchy.

In general, the merges and splits are determined in a greedy manner. The results of hierarchical clustering are usually presented in a dendrogram.

The main purpose of this project is to get an in depth understanding of how the Divisive and Agglomerative hierarchical clustering algorithms work.

More on Hierarchical clustering

Data

We used the Human Gene DNA Sequence dataset, which can be found here. The dataset contains 311 gene sequences. The data can be found in the folder 'data'.

Instructions to run the scripts

Run the following command:

Divisive clustering
python divisive.py
Agglomerative clustering
python agglomerative.py

Equations used

Maximum or complete-linkage clustering -> Max(d(a,b))
Minimum or single-linkage clustering -> Min(d(a,b))
Mean or average linkage clustering -> sum of all d(a,b)/(|A|+|B|)
Diameter of a cluster -> Max(d(x,y))

where x, y are points in the same cluster and, a belongs to A, b belongs to B.

Pre-processing done

The file was read sequence by sequence and was saved in the form of a dictionary, where the key is the gene sequence's name and the value contains the entire gene string.

A mapping was created from the unique gene sequences in the dataset to integers so that each sequence corresponded to a unique integer.

The entire data was mapped to integers to reduce the storage and computational requirement.

Machine specs

Processor: i7-7500U

Ram: 16 GB DDR4

OS: Ubuntu 16.04 LTS

Results

CLustering was performed using the agglomerative and divisive methods and the following dendrograms were obtained-

Agglomerative

Agglomerative-Centroid Agglomerative-Max Agglomerative-Min

Divisive

Divisive

Group Members

Shubham Jha

Praneet Mehta

Abhinav Jain

About

A Python implementation of divisive and hierarchical clustering algorithms. The algorithms were tested on the Human Gene DNA Sequence dataset and dendrograms were plotted.

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages