K-Mean Clustering Algorithm And its intresting usecases

The K-means clustering is a method of vector quantization, originally from signal processing, that aims to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean, serving as a prototype of the cluster.

Before proceeding let’s get clear with the two cases that probably occur in the data mining :

Supervised Learning (SL): It is a concept when the ML model is trained using a set of inputs (predictors) and desired outputs (target).

Unsupervised Learning (UL): It is used when the target(output) is not known and the objective is to infer patterns or trends in the data that can inform a decision.

Let us study more regarding K-Means , the same with it’s various other use cases.

K-mean is a clustering to solve the unsupervised problems of Machine Learning where that does not contain any output.

How K-means algorithm works

Let’s say we have a data set that looks like the following figure when plotted out,

What K-means clustering? actually, it will create clusters. Let us take an example of this, This looks perfectly fits within three groups. Machines can’t see that, as those points are actual data points.

k-Means clustering is all about putting the training points into clusters. But the purpose of it follows the same idea. We want to know which data points belong together without having any labels for any of them.

We start the algorithm by placing k different averages (means) whose values are either initialized randomly. For explanation-related purposes.

Now, the algorithm goes through the data points one by one, measuring the distance between each point and the three centroids(triangle/A, B, and C). The algorithm then groups the data point with the closest distance).

For instance, data pointed one will belong to group A in the green color, merely because it’s closer in distance to centroid A

Once done with associating each data point with its closest centroids, we re-calculate the values of the centroids. The new value of a centroid is the sum of all the points belonging to that centroid divided by the number of points in the group as below.

We keep on doing the above until no centroid changes its value. This means that each centroid has centered itself in the middle of its cluster, which is surrounded by its own circular decision boundary.

Mathematics behind K-Mean Clustering algorithm :

Assuming we have input data points x1,x2,x3,…,xn and value of K (the number of clusters needed). We follow the below procedure:

1. Pick K points as the initial centroids from the dataset, either randomly or the first K.
2. Find the Euclidean distance of each point in the dataset with the identified K points (cluster centroids).
3. Assign each data point to the closest centroid using the distance found in the previous step.
4. Find the new centroid by taking the average of the points in each cluster group.
5. Repeat 2 to 4 for a fixed number of iteration or till the centroids don’t change.

Euclidean Distance between two points in space: If p = (p1, p2) and q = (q1, q2) then the distance is given by

Advantages of K-Means Clustering :

K-Means offer many advantages while doing unsupervised data mining. The various advantages it may offer the user are

1. Easy to implement and apply.
2. Generalization of clusters for different shapes and sizes.
3. Produce better and tighter clusters as compared to the clustering techniques.

4. It can handle more large data linearly.

5. Offers an effective way to initialize.

6. Fastest Algorithm for clustering data.

7. Successful usage in the domains of market segmentation, computation vision, fraud detection, etc.

Disadvantages of K-means

1. It is sensitive to outliers.
2. Choosing the k values manually is a tough job.
3. As the number of dimensions increases its scalability decreases.

Some of K-Mean Use-Cases

Use Cases in the Security Domain

1. Identifying crime localities

With data related to crimes available in specific localities in a city, the category of crime, the area of the crime, and the association between the two can give quality insight into crime-prone areas within a city or a locality.

2. Cyber-profiling criminals

Cyber profiling is the process of collecting data from individuals and groups to identify significant correlations. The idea of cyber profiling is derived from criminal profiles, which provide information on the investigation division to classify the types of criminals who were at the crime scene.

3. Call record detail analysis

This information provides greater insights about the customer’s needs when used with customer demographics. We can cluster customer activities for 24 hours by using the unsupervised k-means clustering algorithm. It is used to understand segments of customers concerning their usage by hours.

4.Anomaly detection

Anomaly detection refers to methods that provide warnings of unusual behaviors that may compromise communication networks' security and performance. Anomalous behaviors can be identified by comparing the distance between real data and cluster centroids. Identifying network anomalies is essential for communication networks of enterprises or institutions. The goal is to provide an early warning about an unusual behavior that can affect the security and the performance of a network.

5. Rideshare Data Analysis

The publicly available uber ride information dataset provides a large amount of valuable data around traffic, transit time, peak pickup localities, and more. Analyzing this data is useful not just in the context of uber but also in providing insight into urban traffic patterns and helping us plan for the cities of the future.

6. Document Classification

Cluster documents in multiple categories based on tags, topics, and the content of the document. This is a very standard classification problem and k-means is a highly suitable algorithm for this purpose. The initial processing of the documents is needed to represent each document as a vector and uses term frequency to identify commonly used terms that help classify the document. the document vectors are then clustered to help identify similarities in document groups.

7. Delivery Store Optimization

Optimize the process of good delivery using truck drones by using a combination of k-means to find the optimal number of launch locations and a genetic algorithm to solve the truck route as a traveling salesman problem.

8. Crime Analysis

Crime analysis is a law enforcement function that involves systematic analysis for identifying and analyzing patterns and trends in crime and disorder. Crime analysis also plays a role in devising solutions to crime problems and formulating crime prevention strategies. Analysis of crime is essential for providing safety and security to the civilian population. K means clustering technique is used to extract useful information from the high volume crime dataset and to interpret the data which assist police in identify and analyze crime patterns to reduce further occurrences of similar incidence and provide information to reduce the crime.

Use-Cases in CDR analysis

CDR is the record gathering by the telecom providers.CDR stands for the Call Detail Record. This information contains all the information regarding the call details, SMS details, internet service used by the customers.

Most telecom corporations use CDR data for impostor detection by clustering the user profiles, reducing customer churn by usage activity, and targeting profitable customers by using RFM analysis.

The data once gathered by the API system is retrieved by the data analysts. The data is preprocessed by applying various optimization, error detection techniques, and EDA. Exploratory Data Analysis is the method of analyzing the data visually. It involves outlier detection, exception detection, missing values detection.

K-Means algorithm is used to create clusters that may resemble certain similarities in the records. K-means are applied among “total activity and activity hours” to find the usage pattern regarding the activity hours.

The Elbow method is used to find an optimal number of clusters to the K-means algorithm.

It tells the pattern the data is following in the given time duration. It is used to understand the segment of customers concerning their usage by hours. For example, a customer segment with high activity may generate more revenue. Customer segments with high activity in the night hours might be fraudulent ones.

By practicing this clustering tool, you can discover the clusters making more traffic to the telecom network in the measure of total activity. Similarly, you can obtain more information like square grid and country code information to understand the square grid likely creating more revenue and more traffic to the telecom network and targeting high customers based on their geo-location.