text: import numpy as np
  from load_dist_matrix import load_dist_matrix
  from timing_wrapper import timeit
  from scipy.cluster.hierarchy import dendrogram
  import matplotlib.pyplot as plt
  import copy
  
  class DivisiveClustering:
  	'''
  	Class which implements the DIANA (Divisive Analysis) algorithm and provides an interface for using the implementation.
  	'''
  	def __init__(self):
  		'''
  		Initializer for the DivisiveClustering class.
  		This function initializes some important class variables.
  		'''
  		self.clusters={}
  		self.dist_matrix=None
  		self.mapping=None
  		self.no_clusters=0
  		self.linkage_matrix=None
  		self.n=None
  		self.hierarchical_clusters={}
  		self.last_index=None
  
  	def initialize(self):
  		'''
  		Initializer for the DivisiveClustering class.
  
  		Parameters
  		----------
  		path : string
  		    path to file containinng transactions.
  		
  		Returns
  		----------
  		transactions : list
  			list containing all transactions. Each transaction is a list of
  			items present in that transaction.
  		items : list
  			list containing all the unique items.
  		'''
  		self.n=len(self.mapping)
  		self.last_index=2*self.n-2
  		self.i=0
  		self.clusters[self.last_index]=list(self.mapping.keys())
  		self.linkage_matrix=np.zeros([self.n-1, 4])
  
  	def splinter(self):
  		'''
  		This function finds the cluster with the largest diameter and finds the splinter element.
  
  		Returns
  		----------
  		splinter_element : int
  			the splinter element. This element will be removed from the cluster that is being split.
  		max_diameter_cluster : int
  			index of the cluster with the largest diameter. This is the cluster which will be split.
  		'''
  		cluster_diameters={k:(len(v)<1)*(-1)+(len(v)>1)*np.max(self.dist_matrix[np.ix_(v,v)]) for k,v in self.clusters.items()}
  		max_diameter_cluster=max(cluster_diameters, key=cluster_diameters.get)
  		avg_within_cluster_distances={pt:(np.sum(self.dist_matrix[np.ix_(self.clusters[max_diameter_cluster], [pt])])/(len(self.clusters[max_diameter_cluster])-1)) for pt in self.clusters[max_diameter_cluster]}
  		splinter_element=max(avg_within_cluster_distances, key=avg_within_cluster_distances.get)
  		self.no_clusters+=1
  		return splinter_element, max_diameter_cluster
  
  	def reassign(self, splinter_element, orig_cluster_key):
  		'''
  		Function which reassigns points between the original cluster and the splinter cluster.
  
  		Parameters
  		----------
  		splinter_element : int
  		    the splinter element.
  
  		orig_cluster_key : int
  		    the ID of the element to be split.
  
  		'''
  		# Create temp clusters
  		temp_new_cluster=[splinter_element]
  		self.clusters[orig_cluster_key].remove(splinter_element)
  		temp_orig_cluster=self.clusters[orig_cluster_key]
  
  		# Remove orig cluster from cluster dict
  		del self.clusters[orig_cluster_key]
  
  		# Calculate distances
  		within_cluster_dist={pt:np.mean(self.dist_matrix[np.ix_(temp_orig_cluster,[pt])]) for pt in temp_orig_cluster }
  		dist_to_splinter={pt:self.dist_matrix[pt, splinter_element]  for pt in temp_orig_cluster}
  		dist_diff={pt:(within_cluster_dist[pt] - dist_to_splinter[pt]) for pt in temp_orig_cluster} # if +ve, move to splinter
  		
  		# Reassign points
  		for pt in temp_orig_cluster:
  			if dist_diff[pt]>0 and len(temp_orig_cluster)>1:
  				temp_new_cluster.append(pt)
  				temp_orig_cluster.remove(pt)
  		
  		dist_bw_clusters=np.max(self.dist_matrix[np.ix_(temp_orig_cluster, temp_new_cluster)])
  		
  		# Add temp clusters to cluster dict
  		if len(temp_orig_cluster)==1:
  			self.clusters[temp_orig_cluster[0]]=temp_orig_cluster
  			orig_cluster_key=temp_orig_cluster[0]
  		else:
  			self.last_index-=1
  			self.clusters[self.last_index]=temp_orig_cluster
  			orig_cluster_key=self.last_index
  
  		if len(temp_new_cluster)==1:
  			self.clusters[temp_new_cluster[0]]=temp_new_cluster
  			new_cluster_key=temp_new_cluster[0]
  		else:
  			self.last_index-=1
  			self.clusters[self.last_index]=temp_new_cluster
  			new_cluster_key=self.last_index
  
  		# Append to hierarchical clusters
  		self.hierarchical_clusters['iter_'+str(self.no_clusters)]=copy.deepcopy(self.clusters)
  
  		# Make the linkage function
  		self.make_linkage_function(new_cluster_key, orig_cluster_key, dist_bw_clusters, len(temp_new_cluster)+len(temp_orig_cluster))
  
  	def make_linkage_function(self, cluster_1, cluster_2, dist, len_cluster_2):
  		'''
  		Function to create the linakge matrix 'Z' for the dendrogram.
  
  		Parameters
  		----------
  		cluster_1 : int
  		    the ID of the first cluster.
  		cluster_2 : string
  		    the ID of the first cluster.
  		dist : string
  		    distance between the newly formed clusters.
  		len_cluster_2 : string
  		    number of elements in the original cluster which was later split.
  		'''
  		self.linkage_matrix[self.n-self.no_clusters-1, 0]=cluster_2
  		self.linkage_matrix[self.n-self.no_clusters-1, 1]=cluster_1
  		self.linkage_matrix[self.n-self.no_clusters-1, 2]=dist
  		self.linkage_matrix[self.n-self.no_clusters-1, 3]=len_cluster_2
  
  	def termination(self):
  		'''
  		Function to check whether clustering has termianted.
  		Clustering has terminated when there's only one element in all of the clusters.
  
  		Returns
  		----------
  		terminated : int (0 or 1)
  			function returns 1 on termination. 0 otherwise.
  		'''
  		for k, v in self.clusters.items():
  			if len(v)>1:
  				return 0
  		return 1
  
  	def fit(self, dist_matrix, mapping):
  		'''
  		Function that fits the data on the HierarchicalCLustering model.
  
  		Parameters
  		----------
  		dist_matrix : numpy ndarray
  		    the distance matrix.
  		mapping : dict
  		    mapping of the cluster ids to original names from dataset.
  		'''
  		self.dist_matrix=dist_matrix
  		self.mapping=mapping
  		self.initialize()
  		while not self.termination():
  			splinter_element, orig_cluster_key=self.splinter()
  			self.reassign(splinter_element, orig_cluster_key)
  		print('Clustering done!')
  
  	def create_dendrogram(self):
  		'''
  		Function to create the dendrogram using the linakge matrix and save it to file.
  		'''
  		fig=plt.figure(figsize=(18, 8))
  		plt.title("Dendrogram - Divisive Clustering")
  		labels=['temp']*len(self.mapping)
  		for idx,label in self.mapping.items():
  			labels[idx]=label
  		labels=np.array(labels)
  		dendrogram(self.linkage_matrix, orientation='top', labels=labels)
  		fig.savefig('dendrogram_divisive.png')
  		plt.show()
  
  def read_data():
  	'''
  	Function that reads data from file.
  	
  	Returns
  	----------
  	data_dict : dict
  		dictionary containing the strings as values and cluster names as keys.
  	mapping : dict
  		mapping of the cluster ids to original names from dataset.
  	'''
  	dataDict={}
  	rawData=None
  	with open('data/data.txt', 'r') as f:
  		rawData=f.read()
  	dataSegments = rawData.split('>')
  	for segment in dataSegments:
  		try:
  			lines = segment.split('\n', 1)
  			dataDict[lines[0]] = lines[1].replace('\n', '')
  		except:
  			pass
  	mapping={ind:k for ind, k in enumerate(dataDict.keys())}
  	return dataDict, mapping
  
  if __name__=='__main__':
  	data, mapping=read_data()
  	dist_matrix=load_dist_matrix(data, mapping)
  	model=DivisiveClustering()
  	model.fit(dist_matrix, mapping)
  	model.create_dendrogram()