The modern period of development of society is characterized by a significant impact on its information technology in all spheres of life. Marketing is no exception. Among the great competition, it is so difficult to interest a potential buyer with your product. The solution to this problem is data clustering. The aim of the work is to investigate two popular clustering algorithms DBSCAN K-means, to analyze the dataset of customer data. The experiments confirmed the efficiency of the proposed methods for data clustering. It has been investigated that K-means for analyzing customer data. After all, the data are non-spherical in shape and have different densities, contain noise. However, the DBSCAN algorithm is excellent with such data.
2021 Copyright for this paper by its authors.
of two clustering algorithms (DBSCAN and K-tools) for data set analysis. Researchers wrote about
them in their work [
Consider in more detail the operation of the DBSCAN algorithm, which is based on determining
the density between clusters. His job is to separate high and low density clusters [
In the works of researchers [
To perform the DBSCAN algorithm, you need to use two parameters that allow you to quickly
group objects by characteristics into clusters [
1. Euclidean distance, which shows the distance between two points, it is denoted by EPS. This parameter determines the distance between adjacent points.
2. The second parameter is to form a dense cluster. It is determined by the minimum number of points.
Knowing these two parameters and how to determine them, you can divide the data points into certain categories:
The first category includes the main point, which takes the minimum number of points wit hin the
epsilon (MinPts) [
Consider the algorithm of K-means. To implement it, you need to have the values of entry points and the value of K, where K is the number of required clusters. To analyze this method you need to follow a certain algorithm: 1. In the first step, you need to select the points K, which will act as the initial centroids. 2. The next step is to group relative to the centroid to create a cluster K. To do this, determine the
Euclidean distance to each point relative to the centroid within the cluster.
If we have point р ( р1 , р2 ) і q (q1, q2 ) , then the Euclidean distance between the points d ( р, q) will be determined by the formula 1.
dist ( p, q) 2 (q1 p1 ) 2 (q2 p2 ) 2 (1)
According to formula 2, the Euclidean distance is assigned to the points closest to the centroid. Where ci centroids of every class, а х point from set (Formula 2).
3. Find next centroid, moving the centroid to the center of its cluster (Formula 3).
min dist (ci , x) ci 1 si xisi xi , (2) (3) where si ‒ the set of all points assigned to i‒th cluster.
First you need to examine the selected dataset «Mall_Customer» (Table 1). The selected dataset contains data on customer age, gender, annual income, and average spending.
Using data, we tried to group the data and understand. Let's start the research with the DBSCAN algorithm.
As we know algorithm DBSCAN basically requires two parameters to search for clusters: 1. Еps; 2. MinPoints.
Our clustering depends on the values of these points.
The first step, to form a cluster requires a minimum number of points, which is denoted by
MinPoints [
The Figure 1 shows the Euclidean distance between points, where the y ‒ axis shows the distance between n ‒ points, and the x ‒ axis shows the points sorted by distance. The principle of eps selection is to select the point after which distance starts to increase. All points that will be located on the right side will be the noise. The number of noise will depend on the choice of eps. Therefore, according to Figure 2 eps = 0.7.
We found parameters that we need for this algorithm: 1. Еps ‒ 0,7. 2. MinPoints – 4.
It should be noted that these parameters directly affect the result. The number of noise will depend on the choice of eps.
The DBSCAN algorithm begins its work by selecting one observation. Then counts the number of neighbors at a distance of eps (0.7). If the number of neighbors more than MinPoints (4), we classify our point as the basis and use it to expand the cluster. Let's look at the Figure 2, we can see that on a distance eps from the selected point are 6 points. So, we can say that the main point can form a cluster.
Each neighbor, which we have not considered before, we write in the cluster, and then use it as a point for further expansion of the cluster. Well, we begin to expand our cluster, consider the next neighbor and its neighbors (neighbors of the 2nd degree) and repeat the same algorithm. To expand the cluster, we consider the number of second ‒ degree neighbors. If their number exceeds MinPoints, then the extension point becomes the main point that will determine the next extension. Looking at the figure we can see that at a distance eps from our point is 4. So, we can assume that our point belongs to our cluster (Figure 3).
We continue our algorithm further. Choose the next point. We can see that there is one point left at the eps' distance, and we need at least 4 points to form a cluster, so our point should not be up to any class, and we classify as noise (Figure 4).
And so we will continue until we visit will all the points. When we do not have enough neighbors and main points to expand, we have completed the classification of the cluster (Figure 5). And we get the first formed cluster.
Then we select a new point and start the process again. We continue until we form all clusters. At the Figure 6 we can see how the DBSCAN algorithm divided our data into clusters.
Now let's look at the operation of the K-means algorithm.
To implement the K-means algorithm you need to find the following values: 1. Number of cluster K. 2. K – centroids.
In algorithm K-means of big importance is the correct choice of the value of the parameter k ‒ if the number of clusters is not known in advance.
In this case, it is usually considered k n , where n ‒ sample size. However, for a large n, this choice of the parameter will lead to a very large number of clusters, which will lead to incorrect clustering. Therefore, we will apply Elbow method. It implies multiple cyclic executions of the algorithm with an increase in the number of selected clusters, as well as subsequent deposition on the graph of the clustering score (Figure 7).
We need to choose the point after which the schedule stops falling sharply.
In our case, it will be point 5. That is for our clustering we will use 5 clusters. The next step is to select K ‒ centroid (Centroid is a point that is the center of the class).
Well, randomly we choose 5 centers (Figure 8).
We choose a point and look for the Euclidean distance from the selected point on the set of centroids (Figure 9).
Next, we assign a given point to the cluster to which it is closest. The same we do for all points. When we have passed all the points, we look at the location of our centroids and move them to the cluster of points. as a result, we obtain the location of new centroids. This process needs to be reused until we know a constant value for the centers, and the last cluster will be considered as the last solution of the cluster (Figure 10).
Our centers around which clusters are formed are highlighted in pink on the Figure 10.
Comparing the work of algorithms, we can see that the given dataset is best handled by the algorithm K-means. We can that algorithm divided data on 5 clusters.
Let's try to compare the work of our algorithms by applying to different data (Table 3).
We have a data set in the form of two crescents. We can see in the Table 3, that only the DBSCAN algorithm shown us the correct clusterization. Algorithms divided our data into 2 clusters, but only
DBSCAN divided the data correctly. The K-means algorithm divided our data set according to the location of the centroid. And as we know that our centroids are shifted toward the largest cluster, we can conclude that the K-means algorithm works poorly when the data is not spherical (Table 4).
We have the following data set. The DBSCAN and K – means algorithms identified 2 clusters (Table 4). However, again, only DBSCAN coped with the task correctly. First of all, K-means works badly with non-spherical data. And also the algorithm divides the data into approximately identical clusters (Table 5).
Well, let's consider the following example. In general, we can say that each of the algorithms has done the task correctly (Table 5). However, the DBSCAN algorithm coped with the task better. To form a dense cluster, you need to determine the minimum number of points. For this purpose the point was entered in a certain group. If the point does not belong to any cluster, it is defined as noise. Accordingly, our algorithm divided our data into 3 clusters on the allocated emissions.
Let's compare the dependence of the running time of algorithms on the amount of data (Table 6).
We can see in the Table 6 that a large amount of data for K-means is not a problem, because the data processing time is not high. After all, even when we increased the amount of data 11 times, the operating time of the algorithm did not increase very sharply, the time difference is only 0.15 seconds.
The DBSCAN algorithm also quick classify data (Table 7). It handles a data set that contains 11,000 observations in just 0.12 seconds.
We can see that the fastest is the DBSCAN algorithm, in second place is the K-means algorithm (Figure 11).