Original link:tecdat.cn/?p=6689 

Original source:Tuo End number according to the tribe public number

In this paper, 188 countries are aggregated based on these 19 socioeconomic indicators using monte-Carlo K-means clustering algorithm implemented by Python. Clustering can help reduce the amount of work required to identify attractive investment opportunities by grouping similar countries together and generalizing them.

Before discussing clustering countries and drawing conclusions about the results, this paper introduces distance measurement, clustering quality measurement, clustering algorithm, k-means clustering algorithm in detail.

Cluster theory – Measurement of similarity and distance

Clustering is the process of dividing a set of heterogeneous (different) objects into subsets of homogeneous (similar) objects. The core of cluster analysis is that given any two objects, you can quantify the similarities or dissimilarities between those objects. Distance measures similarity in continuous search space.

Below I write a similarity measure for continuous search space. For each I include formulas (given two vectors, and q) and Python code. All of the Python code used to write this article is available.

class Similarity:
 

    def __init__(self, minimum):
        self.e = minimum
        self.vector_operators = VectorOperations()

    def manhattan_distance(self, p_vec, q_vec):
        """
        This method implements the manhattan distance metric
        :param p_vec: vector one
        :param q_vec: vector two
        :return: the manhattan distance between vector one and two
        """
        return max(np.sum(np.fabs(p_vec - q_vec)), self.e)

    def square_euclidean_distance(self, p_vec, q_vec):
        """
        This method implements the squared euclidean distance metric
        :param p_vec: vector one
        :param q_vec: vector two
        :return: the squared euclidean distance between vector one and two
        """
        diff = p_vec - q_vec
        return max(np.sum(diff ** 2), self.e)
Copy the code

Clustering theory – clustering algorithm class

Clustering theory – K-means clustering algorithm

K-means clustering algorithm is a partition clustering algorithm based on centroid, which uses mean shift heuristic algorithm. The K-means clustering algorithm consists of three steps (initialization, allocation and update). These steps are repeated until the clustering has converged or the number of iterations has exceeded, that is, the computational budget has been exhausted.

Initialize the

Initializes a random set of centroids in the search space. These centroids must be in the same order of magnitude as the clustered data pattern. In other words, it makes no sense to initialize random vectors with values between 0 and 1 if the values in the data schema are between 0 and 100.

Note: Make sure to normalize data across each attribute,Rather thanEach pattern

distribution

Once the center of mass has been randomly initialized in space, we iterate over each pattern in the dataset and assign it to the nearest center of mass. Try to do this step in parallel, especially if there are a large number of schemas in the data set.

update

Once patterns are assigned to their centers of mass, the mean-shift heuristic is applied. This heuristic replaces each value in each center of mass and replaces the average of that value with the pattern assigned to that center of mass. This moves the center of mass towards the higher-dimensional mean of its pattern. The problem with the mean-shift heuristic is that it is sensitive to outliers. To overcome this problem, k-Medoids clustering algorithm can be used, and standardized data can be used to suppress the influence of outliers,

The iteration

Repeat these three steps for multiple iterations until the clustering has converged on the solution. A nice GIF shows something like this,

Clustering theory – the measurement of clustering quality

Assuming you have a certain degree of similarity and clustering of data, you still need an objective function to measure the quality of that clustering. Most cluster quality metrics attempt to optimize a cluster based on inter-cluster and intra-cluster distances. Simply put, these metrics try to ensure that patterns in the same cluster are closely related and that patterns in different clusters are far apart.

Quantization error

Quantization error measures the rounding error introduced by quantization, which maps a set of input values to a finite, smaller set. This is basically what we do by clustering patterns into k clusters.

Note: The image also assumes that we use the Manhattan distance.

In the above description of the quantization error, we calculate the sum of the square absolute distances between each mode and its assigned center of mass.

Davis-bourdin index

The Davis-Erding criterion is based on the distance ratios within and between clusters of a particular cluster.

Note: The image assumes that we use the Manhattan distance.

In the diagram above of the Davies-Bouldin index, we have three clusters of three patterns.

Silhouette index

The silhouette index is one of the most popular ways to measure the quality of a particular cluster. It measures how similar each pattern is to the patterns in its own cluster and compares it to the patterns in other clusters.

def silhouette_index(self, index): # store the total distance to each cluster silhouette_totals = [] # store the number of patterns in each cluster silhouette_counts = [] # initialize the variables for i in range(self.solution.num_clusters): Silhouette_totals. Append (0.0) silhouette_counts. Append (0.0) s = Similarity(self.e) for I in range(len(self.solution.patterns)): # for every pattern other than the one we are calculating now if i ! = index: # get the distance between pattern[index] and that pattern distance = s.fractional_distance(self.solution.patterns[i], self.solution.patterns[index]) # add that distance to the silhouette totals for the correct cluster silhouette_totals[self.solution.solution[i]] += distance # update the number of patterns in that cluster silhouette_counts[self.solution.solution[i]] += 1 # setup variable to find the cluster (not equal to the Pattern [index]'s cluster) with the Smallest_Silhouette = Silhouette = Cliette_Totals [0] / Max (1.0, silhouette_counts[0]) for i in range(len(silhouette_totals)): # calculate the average distance of each pattern in that cluster from pattern[index] silhouette = silhouette_totals[i] / Max (1.0, silhouette_counts[i]) # if the average distance is lower and it isn't pattern[index] cluster update the value if silhouette < smallest_silhouette and i ! = self.solution.solution[index]: smallest_silhouette = silhouette # calculate the internal cluster distances for pattern[index] index_cluster = Silhouette = Self. Silhouette = Silhouette + silhouette_totals[index_cluster] / Max (1.0, silhouettes) silhouette_counts[index_cluster]) # return the ratio between the smallest distance from pattern[index] to another cluster's patterns and # the patterns belong to the same cluster as pattern[index] return (smallest_silhouette - index_silhouette) / max(smallest_silhouette, index_silhouette)Copy the code

The high contour value means that avdeev matches well with its own cluster and badly with its neighbors. One should aim to maximize each pattern in the data set.

Note: The image also assumes that we use the Manhattan distance.

After using these metrics over the past few months, I’ve come to the conclusion that none of them are perfect,

1. Quantization error – This measure has minimal computational complexity, but the measure is biased toward large clusters because clusters become smaller (more compact) as you add more centroids, and in extreme cases you may assign one pattern centroid to each cluster. In this case, the quantization error is minimized. Using this metric, The Good, The results are The most reliable.
2. Davis – Bourding – as you increase the value of the k k the distance between each centroid will naturally decrease on average. Because this term is in the denominator, so for larger values, finally divide by smaller numeric k k. The result is a metric bias toward solutions with a smaller number of clusters.
3. Silhouette Index – The computational complexity of this indicator is insane. Suppose you calculated from each model avdeev avdeev I life to each other in the distance, to calculate which cluster is the most close to, and you do this for each model, you need to calculate | Z | | | * Z – 1 | | | | * avdeev avdeev – 1. In this case, that’s 35,156 calculations. If you remember perfectly, the number of calculations per pass is halved.

These biases are well documented in the following analysis of different indicators; Despite the fact that they should measure the same thing, they are almost entirely negatively correlated.

PYTHON code – Clustering

Before you can evaluate the adaptability of a given cluster, you need the actual clustering pattern. The Clustering class contains methods for assigning patterns to the nearest center of mass.

PYTHON code – Object functions

The ClusteringQuality class measures the quality of a cluster for a given input pattern.

Clustering theory – Monte Carlo method in clustering

Clustering results – visualization and centroid analysis

The final results presented below represent the simulated k’s found in the range of the best clustering k’s ={6, 7, 8} k’s ={6, 7, 8} over 1000 independent per of each value. Euclidean distance and quantization error are distance and quality measures used in Monte Carlo k-means clustering. The data set used to produce the results is a standardized point-in-time data set from 2014, which includes 19 socio-economic indicators identified as positively correlated with real GDP growth.

Cluster subdivision and centroid analysis

Each label below breaks down the cluster into the countries it belongs to and compares the center of mass to the central center of mass of each of the 19 socioeconomic indicators we aggregate.

Countries in this group in 2014

Clustering results – Conclusions and further research