Secure your code as it's written. Use Snyk Code to scan source code in minutes - no build needed - and fix issues immediately.
@param[in] node_head (node): Node from that searching is performed.
@param[in|out] best_nodes (list): List of founded nodes.
"""
if node_head.right is not None:
minimum = node_head.data[node_head.disc] - distance
if point[node_head.disc] >= minimum:
self.__recursive_nearest_nodes(point, distance, sqrt_distance, node_head.right, best_nodes)
if node_head.left is not None:
maximum = node_head.data[node_head.disc] + distance
if point[node_head.disc] < maximum:
self.__recursive_nearest_nodes(point, distance, sqrt_distance, node_head.left, best_nodes)
candidate_distance = euclidean_distance_square(point, node_head.data)
if candidate_distance <= sqrt_distance:
best_nodes.append( (candidate_distance, node_head) )
def __find_another_nearest_medoid(self, point_index, current_medoid_index):
"""!
@brief Finds the another nearest medoid for the specified point that is differ from the specified medoid.
@param[in] point_index: index of point in dataspace for that searching of medoid in current list of medoids is perfomed.
@param[in] current_medoid_index: index of medoid that shouldn't be considered as a nearest.
@return (uint) index of the another nearest medoid for the point.
"""
other_medoid_index = -1
other_distance_nearest = float('inf')
for index_medoid in self.__current:
if (index_medoid != current_medoid_index):
other_distance_candidate = euclidean_distance_square(self.__pointer_data[point_index], self.__pointer_data[current_medoid_index])
if other_distance_candidate < other_distance_nearest:
other_distance_nearest = other_distance_candidate
other_medoid_index = index_medoid
return other_medoid_index
@see __minimum_noiseless_description_length(clusters, centers)
"""
scores = [float('inf')] * len(clusters) # splitting criterion
dimension = len(self.__pointer_data[0])
# estimation of the noise variance in the data set
sigma_sqrt = 0.0
K = len(clusters)
N = 0.0
for index_cluster in range(0, len(clusters), 1):
for index_object in clusters[index_cluster]:
sigma_sqrt += euclidean_distance_square(self.__pointer_data[index_object], centers[index_cluster])
N += len(clusters[index_cluster])
if N - K > 0:
sigma_sqrt /= (N - K)
p = (K - 1) + dimension * K + 1
# in case of the same points, sigma_sqrt can be zero (issue: #407)
sigma_multiplier = 0.0
if sigma_sqrt <= 0.0:
sigma_multiplier = float('-inf')
else:
sigma_multiplier = dimension * 0.5 * log(sigma_sqrt)
# splitting criterion
for index_cluster in range(0, len(clusters), 1):
for point_index in range(0, len(self.__pointer_data)):
if point_index not in self.__current:
# get non-medoid point and its medoid
point_cluster_index = self.__belong[point_index]
point_medoid_index = self.__current[point_cluster_index]
# get other medoid that is nearest to the point (except current and candidate)
other_medoid_index = self.__find_another_nearest_medoid(point_index, current_medoid_index)
other_medoid_cluster_index = self.__belong[other_medoid_index]
# for optimization calculate all required distances
# from the point to current medoid
distance_current = euclidean_distance_square(self.__pointer_data[point_index], self.__pointer_data[current_medoid_index])
# from the point to candidate median
distance_candidate = euclidean_distance_square(self.__pointer_data[point_index], self.__pointer_data[candidate_medoid_index])
# from the point to nearest (own) medoid
distance_nearest = float('inf')
if ( (point_medoid_index != candidate_medoid_index) and (point_medoid_index != current_medoid_cluster_index) ):
distance_nearest = euclidean_distance_square(self.__pointer_data[point_index], self.__pointer_data[point_medoid_index])
# apply rules for cost calculation
if (point_cluster_index == current_medoid_cluster_index):
# case 1:
if (distance_candidate >= distance_nearest):
candidate_cost += distance_nearest - distance_current
# case 2:
else:
candidate_cost += distance_candidate - distance_current
def __calculate_nearest_distance(self, index_cluster1, index_cluster2):
"""!
@brief Finds two nearest objects in two specified clusters and returns distance between them.
@param[in] (uint) Index of the first cluster.
@param[in] (uint) Index of the second cluster.
@return The nearest euclidean distance between two clusters.
"""
candidate_minimum_distance = float('Inf')
for index_object1 in self.__clusters[index_cluster1]:
for index_object2 in self.__clusters[index_cluster2]:
distance = euclidean_distance_square(self.__pointer_data[index_object1], self.__pointer_data[index_object2])
if distance < candidate_minimum_distance:
candidate_minimum_distance = distance
return candidate_minimum_distance
# get other medoid that is nearest to the point (except current and candidate)
other_medoid_index = self.__find_another_nearest_medoid(point_index, current_medoid_index)
other_medoid_cluster_index = self.__belong[other_medoid_index]
# for optimization calculate all required distances
# from the point to current medoid
distance_current = euclidean_distance_square(self.__pointer_data[point_index], self.__pointer_data[current_medoid_index])
# from the point to candidate median
distance_candidate = euclidean_distance_square(self.__pointer_data[point_index], self.__pointer_data[candidate_medoid_index])
# from the point to nearest (own) medoid
distance_nearest = float('inf')
if ( (point_medoid_index != candidate_medoid_index) and (point_medoid_index != current_medoid_cluster_index) ):
distance_nearest = euclidean_distance_square(self.__pointer_data[point_index], self.__pointer_data[point_medoid_index])
# apply rules for cost calculation
if (point_cluster_index == current_medoid_cluster_index):
# case 1:
if (distance_candidate >= distance_nearest):
candidate_cost += distance_nearest - distance_current
# case 2:
else:
candidate_cost += distance_candidate - distance_current
elif (point_cluster_index == other_medoid_cluster_index):
# case 3 ('nearest medoid' is the representative object of that cluster and object is more similar to 'nearest' than to 'candidate'):
if (distance_candidate > distance_nearest):
pass;
if merged_cluster.points[1:] == merged_cluster.points[:-1]:
merged_cluster.mean = merged_cluster.points[0]
else:
for index in range(dimension):
merged_cluster.mean[index] = ( len(cluster1.points) * cluster1.mean[index] + len(cluster2.points) * cluster2.mean[index] ) / ( len(cluster1.points) + len(cluster2.points) );
temporary = list()
for index in range(self.__number_represent_points):
maximal_distance = 0
maximal_point = None
for point in merged_cluster.points:
minimal_distance = 0
if index == 0:
minimal_distance = euclidean_distance_square(point, merged_cluster.mean)
#minimal_distance = euclidean_distance_sqrt(point, merged_cluster.mean);
else:
minimal_distance = min([euclidean_distance_square(point, p) for p in temporary])
#minimal_distance = cluster_distance(cure_cluster(point), cure_cluster(temporary[0]));
if minimal_distance >= maximal_distance:
maximal_distance = minimal_distance
maximal_point = point
if maximal_point not in temporary:
temporary.append(maximal_point)
for point in temporary:
representative_point = [0] * dimension
for index in range(dimension):
representative_point[index] = point[index] + self.__compression * (merged_cluster.mean[index] - point[index])
def __cluster_distance(self, cluster1, cluster2):
"""!
@brief Calculate minimal distance between clusters using representative points.
@param[in] cluster1 (cure_cluster): The first cluster.
@param[in] cluster2 (cure_cluster): The second cluster.
@return (double) Euclidean distance between two clusters that is defined by minimum distance between representation points of two clusters.
"""
distance = float('inf')
for i in range(0, len(cluster1.rep)):
for k in range(0, len(cluster2.rep)):
dist = euclidean_distance_square(cluster1.rep[i], cluster2.rep[k]); # Fast mode
#dist = euclidean_distance(cluster1.rep[i], cluster2.rep[k]) # Slow mode
if dist < distance:
distance = dist
return distance
def _competition(self, x):
"""!
@brief Calculates neuron winner (distance, neuron index).
@param[in] x (list): Input pattern from the input data set, for example it can be coordinates of point.
@return (uint) Returns index of neuron that is winner.
"""
index = 0
minimum = euclidean_distance_square(self._weights[0], x)
for i in range(1, self._size, 1):
candidate = euclidean_distance_square(self._weights[i], x)
if candidate < minimum:
index = i
minimum = candidate
return index