Create a Program to Implement Distance Calculation in Python Assignment Solution

import operator

import os

import pandas as pd

import time

import numpy as np

import matplotlib.pyplot as plt

import matplotlib.cm as cm

from collections import defaultdict

from sklearn.preprocessing import StandardScaler

from sklearn.decomposition import PCA

MAX_DISTANCE = 5000

MAX_DISTANCE_FROM_PROTOTYPE = 15

MAX_CLUSTER_DISTANCE = 25

header_names = ['duration', 'protocol_type', 'service', 'flag', 'src_bytes', 'dst_bytes', 'land', 'wrong_fragment', 'urgent', 'hot', 'num_failed_logins', 'logged_in', 'num_compromised', 'root_shell', 'su_attempted', 'num_root', 'num_file_creations', 'num_shells', 'num_access_files', 'num_outbound_cmds', 'is_host_login', 'is_guest_login', 'count', 'srv_count', 'serror_rate', 'srv_serror_rate', 'rerror_rate', 'srv_rerror_rate', 'same_srv_rate', 'diff_srv_rate', 'srv_diff_host_rate', 'dst_host_count', 'dst_host_srv_count', 'dst_host_same_srv_rate', 'dst_host_diff_srv_rate', 'dst_host_same_src_port_rate', 'dst_host_srv_diff_host_rate', 'dst_host_serror_rate', 'dst_host_srv_serror_rate', 'dst_host_rerror_rate', 'dst_host_srv_rerror_rate', 'attack_type', 'success_pred']

kdd_training_file = os.path.join("NSL-KDD", 'KDDTrain+_20Percent.txt')

category = defaultdict(list)

category['benign'].append('normal')

with open('NSL-KDD/training_attack_types.txt', 'r') as f:

for line in f.readlines():

attack, cat = line.strip().split(' ')

category[cat].append(attack)

attack_mapping = dict((v,k) for k in category for v in category[k])

print(repr(attack_mapping))

class ClusterNode(object):

def __init__(self, data_point,cluster_id=None, nearest_prototype_cluster_node=None):

# data point

self._data_point = data_point

self._assigned_cluster = None

# prototype node this node is associated with;

self._nearest_prototype_cluster_node = nearest_prototype_cluster_node

@staticmethod

def distance(node_a, node_b):

node_a_data_point = node_a.data_point

node_b_data_point = node_b.data_point

distance = np.linalg.norm(node_a_data_point - node_b_data_point)

# raise Exception("@todo: Implement a Euclidean distance function for kdd data set")

return distance

@staticmethod

def similarity(node_a, node_b):

return 1 / (1 + ClusterNode.distance(node_a, node_b))

@property

def assigned_cluster(self):

"""

Cluster that this node belongs to

:return:

"""

return self._assigned_cluster

@assigned_cluster.setter

def assigned_cluster(self, value):

self._assigned_cluster = value

@property

def cluster_id(self):

if self._assigned_cluster is None:

return None

return self._assigned_cluster.cluster_id

def print_stuff(self):

print(self.data_point)

@property

def is_prototype(self):

return self == self._nearest_prototype_cluster_node

@property

def data_point(self):

return self._data_point

@property

def nearest_prototype_cluster_node(self):

return self._nearest_prototype_cluster_node

@nearest_prototype_cluster_node.setter

def nearest_prototype_cluster_node(self, value):

self._nearest_prototype_cluster_node = value

class Cluster(object):

def __init__(self, cluster_node_list=[]):

self._cluster_id = id(self)

self._cluster_node_list = []

for cluster_node in cluster_node_list:

self.add_node_to_cluster(cluster_node)

def add_node_to_cluster(self, cluster_node):

# U pdate node's cluster assignment

cluster_node.assigned_cluster = self

# Add node to cluster's node list

self._cluster_node_list.append(cluster_node)

def merge_cluster(self, cluster_2_merge):

for cluster_2_merge_node in cluster_2_merge.cluster_nodes:

self.add_node_to_cluster(cluster_2_merge_node)

@property

def cluster_nodes(self):

for cluster_node in self._cluster_node_list:

yield cluster_node

@staticmethod

def complete_linkage_distance(cluster_a, cluster_b):

"""

Computes the complete linkage distance of two clusters

:param cluster_a:

:param cluster_b:

:return:

"""

# Note: Complete linkage computes the maximum distance of a pair of nodes from cluster a

# and cluster b

max_distance = 0

for cluster_a_node in cluster_a.cluster_nodes:

for cluster_b_node in cluster_b.cluster_nodes:

distance = ClusterNode.distance(cluster_a_node, cluster_b_node)

# If the distance between the current pair of notes is greater than max distance,

# the current distance is the new max distance

if distance > max_distance:

max_distance = distance

return max_distance

@property

def cluster_id(self):

return self._cluster_id

class ApproxAgglomerativeClusteringKDD(object):

def __init__(self, kdd_training_file_path):

self._data_set = None

self._kdd_training_file_path = kdd_training_file_path

self._cluster_node_list = []

self._cluster_list = []

self._is_data_set_loaded = False

self._train_x_continuous_std = None

self._train_Y = None

self._train_x_pca = None

self._pca = None

def plot_training_data(self):

# Check if data set already loaded

if not self._is_data_set_loaded:

self.load_dataset_from_file()

plt.figure()

colors = cm.rainbow(np.linspace(0, 1, len(category)))

for color, cat in zip(colors, category.keys()):

plt.scatter(self._train_x_pca[self._train_Y == cat, 0], self._train_x_pca[self._train_Y == cat, 1],

color=color, alpha=.8, lw=2, label=cat)

plt.legend(loc='right', shadow=False, scatterpoints=1)

plt.show()

def load_dataset_from_file(self):

if self._is_data_set_loaded:

return

train_df = pd.read_csv(self._kdd_training_file_path, names=header_names)

# Aggregates the attack types into categories

train_df['attack_category'] = train_df['attack_type'].map(lambda x: attack_mapping[x])

self.se = train_df['attack_category']

# Remove the attack type labels

train_x_raw = train_df.drop(['attack_type', 'attack_category'], axis=1)

# Remove the features from set that are not continuous

# raise Exception("Need to create a training data set with only continuous features")

symbolic=['attack_category','attack_type','protocol_type','service','flag','land','logged_in','root_shell','su_attempted','is_host_login','is_guest_login']

train_x_continuous = train_df.drop(symbolic,axis=1) # Training data set with only continuous features

# Standardize the data

standard_scaler = StandardScaler().fit(train_x_continuous)

self._train_x_continuous_std = standard_scaler.transform(train_x_continuous)

self._pca = PCA(n_components=2)

self._train_x_pca = self._pca.fit_transform(self._train_x_continuous_std)

self._cluster_node_list = [ClusterNode(data_point) for data_point in self._train_x_continuous_std]

self._is_data_set_loaded = True

def perform_clustering(self):

# Step 1: Determine the prototypes

prototype_list = self._get_prototypes()

# Step 2: Cluster Prototypes

self._cluster_list = self.cluster_nodes(prototype_list)

counter = 0

number_nodes = len(self._cluster_node_list)

# Step 3: Propagate Cluster assignments to nearest prototype

for cluster_node in self._cluster_node_list:

counter +=1

if cluster_node.is_prototype:

continue

# Get cluster assignment from nearest prototype

nearest_prototype_assigned_cluster = cluster_node.nearest_prototype_cluster_node.assigned_cluster

# Add cluster node to cluster

nearest_prototype_assigned_cluster.add_node_to_cluster(cluster_node)

if counter%10 ==0:

print("\n[ {}/{} ] Cluster node {} assigned to cluster {}".format(counter,number_nodes,

repr(cluster_node.data_point),

nearest_prototype_assigned_cluster.cluster_id))

def cluster_nodes(self, cluster_node_list):

# Note: Initially, every cluster node is its own cluster in agglomerative hierarchical clustering

cluster_list = [Cluster([cluster_node]) for cluster_node in cluster_node_list]

while True:

print("\n**** Current number of clusters: {}*****".format(len(cluster_list)))

# Step 1: Compute distances of the clusters

cluster_distance_dict = self._compute_cluster_distances(cluster_list)

# Step 2: Get the minimum cluster distances

(min_cluster_pair, min_cluster_distance_value) = self.get_min_cluster_distance(cluster_distance_dict)

print(

"Minimum Distance of {} is between current cluster {} and cluster {}".format(min_cluster_distance_value,

min_cluster_pair[

0].cluster_id,

min_cluster_pair[

1].cluster_id))

if min_cluster_distance_value >= MAX_CLUSTER_DISTANCE:

break

# Step 3: Merge the min pair clusters

min_cluster_a = min_cluster_pair[0]

min_cluster_b = min_cluster_pair[1]

min_cluster_a.merge_cluster(min_cluster_b)

print("Merging cluster {} into cluster {}; Distance: {}".format(min_cluster_b.cluster_id,

min_cluster_a.cluster_id,

min_cluster_distance_value))

cluster_list.remove(min_cluster_b)

return cluster_list

def _compute_cluster_distances(self, cluster_list):

cluster_distance_dict = dict()

for cluster_a in cluster_list:

cluster_distance_dict[cluster_a] = {}

for cluster_b in cluster_list:

distance = Cluster.complete_linkage_distance(cluster_a, cluster_b)

# print("Distance between current cluster {} and cluster {} is {}".format(cluster_a.cluster_id,

# cluster_b.cluster_id,

# distance))

cluster_distance_dict[cluster_a][cluster_b] = distance

return cluster_distance_dict

def plot_clusters(self):

num_clusters = len(self._cluster_list)

# Plotting

plt.figure()

colors = cm.rainbow(np.linspace(0, 1, num_clusters))

cluster_index = 0

for color, cluster in zip(colors, self._cluster_list):

X = []

Y = []

# for shape in self._train_x_pca:

# print(repr(shape))

for cluster_node in cluster.cluster_nodes:

# x = self._train_x_pca[cluster_node.data_point_index][0]

# y = self._train_x_pca[cluster_node.data_point_index][1]

transformed_data_point = self._pca.transform(cluster_node.data_point.reshape(1,-1))

X.append(transformed_data_point.item(0))

Y.append(transformed_data_point.item(1))

plt.scatter(X, Y, s=50, c=color, marker='o', label="cluster {}".format(cluster_index + 1))

plt.legend(loc='right', shadow=False, scatterpoints=1)

cluster_index += 1

plt.legend(scatterpoints=1)

plt.grid()

plt.show()

pass

def _get_prototypes(self):

prototype_set = set()

prototype_distance_map = dict()

# Initalize prototype distance map, where the key is the prototype and the

# value is that prototypes distance.

# Note: The distance will be initialized to MAX_DISTANCE, which is the maximum distance

prototype_distance_map = {key: value for (key, value) in

[(cluster_node, MAX_DISTANCE) for cluster_node in self._cluster_node_list]}

pass

(curr_max_distance_cluster_node, current_max_distance_value) = self.compute_max_distance_from_prototype(

prototype_distance_map)

while True:

print("\nCurrent max distance: {}".format(current_max_distance_value))

# All of the elements are less than 'MAX_DISTANCE_FROM_PROTOTYPE' away from a prototype

if current_max_distance_value < MAX_DISTANCE_FROM_PROTOTYPE:

break

for cluster_node in self._cluster_node_list:

if cluster_node == curr_max_distance_cluster_node or cluster_node in prototype_set:

continue

# if the current distance from a prototype is greater than that of the curr_max_distance_analysis_report,

# then we'll use the curr_max_distance_analysis_reports distance

dist_from_curr_max_dist_cluster_node = ClusterNode.distance(curr_max_distance_cluster_node,

cluster_node)

if prototype_distance_map[cluster_node] > dist_from_curr_max_dist_cluster_node:

prototype_distance_map[cluster_node] = dist_from_curr_max_dist_cluster_node

# update the clusters nodes nearest prototype

cluster_node.nearest_prototype_cluster_node = curr_max_distance_cluster_node

# The current prototype candidate is its own prototype

curr_max_distance_cluster_node.nearest_prototype_cluster_node = curr_max_distance_cluster_node

# Add the current_prototype candidate to the prototype list

prototype_set.add(curr_max_distance_cluster_node)

print("(Current total:{}) Added cluster node as prototype".format(len(prototype_set)))

# Since the candidate is a prototype, its distance to a prototype is 0 because it is a prototype

prototype_distance_map[curr_max_distance_cluster_node] = 0

# Find the next potential prototype candidate

(curr_max_distance_cluster_node, current_max_distance_value) = self.compute_max_distance_from_prototype(

prototype_distance_map)

return prototype_set

@staticmethod

def compute_max_distance_from_prototype(prototype_distance_map):

""" Returns (key, value) tuple where the value is the max value in dictionary

:param prototype_distance_map:

:return: (key, value) tuple where the value is the max value in dictionary

"""

max_distance = max(prototype_distance_map.items(), key=operator.itemgetter(1))

return max_distance

@staticmethod

def get_min_cluster_distance(cluster_distance_dict):

min_cluster_distance = None

min_cluster_pair = ()

for cluster_key_a in cluster_distance_dict:

for cluster_key_b in cluster_distance_dict[cluster_key_a]:

if cluster_key_a == cluster_key_b:

continue

cluster_distance = cluster_distance_dict[cluster_key_a][cluster_key_b]

if min_cluster_distance is None or min_cluster_distance > cluster_distance:

min_cluster_distance = cluster_distance

min_cluster_pair = (cluster_key_a, cluster_key_b)

return (min_cluster_pair, min_cluster_distance)

@property

def cluster_list(self):

return self._cluster_list

def test_harness():

approx_clustering_kdd = ApproxAgglomerativeClusteringKDD(kdd_training_file)

# Load the dataset

approx_clustering_kdd.load_dataset_from_file()

approx_clustering_kdd.plot_training_data()

start_time = time.time()

approx_clustering_kdd.perform_clustering()

elapsed_time = time.time() - start_time

approx_clustering_kdd.plot_clusters()

print("\nRuntime: {} seconds".format(elapsed_time))

#approx_clustering.plot()

pass

if __name__ == "__main__":

test_harness()