We are provided with a dataset of elements with specific characteristics and values for these elements (for example, a vector). The challenge is to classify these elements into groups. For this we will use the kMeans algorithm; unsupervised learning algorithm.
overview
(It helps if you think of objects as points in ndimensional space). The algorithm will divide the elements into k similarity groups. To calculate this similarity, we will use Euclidean distance as a measurement.
The algorithm works as follows:
The above “points” are called averages because they contain the average of the items classified in it. We have many options to initialize these tools. An intuitive method is to initialize means of random elements in the dataset. Another method is to initialize the means at random values between the boundaries of the dataset (if for the object the elements have values in [0.3], we initialize the means with values in [0.3]).
Above algorithm in pseudocode:
Initialize k means with random values For a given number of iterations: Iterate through items: Find the mean closest to the item Assign item to mean Update mean
Read data
We receive input as a text file (“data.txt”). Each line represents an element and contains numeric values (one for each function), separated by commas. You can find sample data here.
We will read data from the file, storing it as a list. Each list item is a different list containing item values for objects. We do this with the following function:

Initialize Means
We want to initialize the values of each mean in a range of element feature values. To do this, we need to find the minimum and maximum values for each function. We accomplish this with the following function:

Variables are lists containing the minimum and maximum values of the elements, respectively … We initialize the values of each mean randomly between the corresponding minimum and maximum in these two lists:

Euclidean Distance
We will use Euclidean Distance as a measure of similarity for our dataset (note: depending on your subjects, you may use a different measure of similarity).

Update Tool
To update the average, we need to find the average for its function for all elements in the average / cluster. We can do this by adding all the values and then dividing them by the number of elements, or we can use a more elegant solution. We will calculate a new average without having to readd all values by doing the following:
m = (m * (n1) + x) / n
where — the member average, the number of members in the cluster, and the member value for the added member. We do the above for each function to get a new average.

Classify items
Now we need to write a function to classify an item into a group / cluster. For a given element, we will find its similarity to each average and classify the element by the closest one.

Find funds
To actually find funds, we will iterate over all the items, classify them by the closest cluster, and update the cluster average. We will repeat the process for some fixed number of iterations. If between two iterations no element changes the classification, we stop the process, since the algorithm found the optimal solution.
The function below takes as input (the number of desired clusters), the elements and the number of maximum iterations and returns averages and clusters. The classification of the element is stored in an array, and the number of elements in the cluster is — c.

Find Clusters
Finally, we want to find clusters given the means. We will loop through all the elements and classify each element by the closest cluster.

Other popular similarity measures are:
1. Cosine distance: defines the cosine of the angle between point vectors of two points in ndimensional space
2. Manhattan Distance: computes the sum of the absolute differences between the coordinates of the two data points.
3. Minkowski distance: it is also known as generalized distance metric. Can be used for both ordinal and quantitative variables.
You can find all the code on my GitHub plus an example dataset and plotting function … Thanks for reading.
This article contributed by Anthony Maronikolakis . If you are as Python.Engineering and would like to contribute, you can also write an article using contribute.python.engineering or by posting the article [email protected] … See my article appearing on the Python.Engineering homepage and help other geeks.
Please post comments if you find anything wrong or if you would like to share more information on the topic discussed above.