# Max min distance algorithm Python Realization
# Data set form data=[[],[],...,[]]
# The form of clustering results result=[[[],[],...],[[],[],...],...]
# among [] For a pattern sample ,[[],[],...] Is a cluster
import math
def start_cluster(data, t):
zs = [data[0]] # Cluster center set , Select the first pattern sample as the first cluster center Z1
# The first 2 Step ： seek Z2, And calculate the threshold T
T = step2(data, t, zs)
# The first 3,4,5 Step , Find all the cluster centers
get_clusters(data, zs, T)
# Classify by nearest neighbor
result = classify(data, zs, T)
return result
# classification
def classify(data, zs, T):
result = [[] for i in range(len(zs))]
for aData in data:
min_distance = T
index = 0
for i in range(len(zs)):
temp_distance = get_distance(aData, zs[i])
if temp_distance < min_distance:
min_distance = temp_distance
index = i
result[index].append(aData)
return result
# Find all the cluster centers
def get_clusters(data, zs, T):
max_min_distance = 0
index = 0
for i in range(len(data)):
min_distance = []
for j in range(len(zs)):
distance = get_distance(data[i], zs[j])
min_distance.append(distance)
min_dis = min(dis for dis in min_distance)
if min_dis > max_min_distance:
max_min_distance = min_dis
index = i
if max_min_distance > T:
zs.append(data[index])
# iteration
get_clusters(data, zs, T)
# seek Z2, And calculate the threshold T
def step2(data, t, zs):
distance = 0
index = 0
for i in range(len(data)):
temp_distance = get_distance(data[i], zs[0])
if temp_distance > distance:
distance = temp_distance
index = i
# take Z2 Add to cluster center set
zs.append(data[index])
# Calculate threshold T
T = t * distance
return T
# Calculate the Euclidean distance between two pattern samples
def get_distance(data1, data2):
distance = 0
for i in range(len(data1)):
distance += pow((data1[i]-data2[i]), 2)
return math.sqrt(distance)
if __name__=='__main__':
data = [[0, 0], [3, 8], [1, 1], [2, 2], [5, 3], [4, 8], [6, 3], [5, 4], [6, 4], [7, 5]]
t = 0.5 # The scaling factor
result = start_cluster(data, t)
for i in range(len(result)):
print("---------- The first " + str(i+1) + " Clusters ----------")
print(result[i])
