-The article presents a new approach to the problem of searching for cluster centers, based on minimizing differentiable estimates of the average value, insensitive to outliers. It is at the level of the initial mathematical formulation of the problem to lay the stability of the solution with respect to outliers in the data. The search for cluster centers is carried out using the Mahalanobis distance. The proposed algorithm is based on an iterative reweighting scheme. At each step, the problem of searching for cluster centers based on an algorithm with weights of examples is solved. The weights of the examples correspond to the values of the partial derivatives of a function that estimates the average value and is insensitive to outliers. The weights obtained in this way suppress the effect of emissions.
mean estimate, iteratively reweighted algorithm
The classical method for searching for centers and covariance matrices of clusters can be based on solving the following minimization problem: 1 1∗, … , ∗ = arg min 1,…, =1,…, min ( ; , ) (1) matrices, where 1, … , are cluster centers, 1, … , are covariance ( ; , ) = ln| | + ( − )′ −1( − ) is the square of the Mahalanobis distance with the covariance matrix between the points and .
This statement of the problem is based on the assumption that the points of the -th cluster obey a multidimensional normal distribution with a density an arbitrary point refers to the cluster with the number 1 √| | ( ; , ) ∝ −2( − )′ −1( − ), ( ) = arg max ( ; , ).
=1,…,
The problem (1) is reduced to solving systems of
equations
Copyright © 2020 for this paper by its authors.
(2)
(
The following iterative procedure underlies the extended
, +1 =
1
1
| , |
| , |
∑
∈ ,
∈ ,
∑ ( − , )′( − , ),
where
where , are indices of points falling into the -th cluster at
the -th step. Initial values of cluster centers 1,0, … , ,0 and
covariance matrices 1,0, … , ,0 are set before the iteration
procedure (
A significant distortion of the results of the algorithm may appear if the empirical distribution { ( 1), … , ( )}, ( ) = ( ; 1, … , ; 1, … , ) = min ( ; , ) =1,…, contains oitliers.
II. THE CLASSIC METHOD OF OVERCOMING THE EFFECTS OF
OUTLIERS The classical method for solving the problem emissions is based on the replacement of the function ( ; , ) with
( ; , ) = ln| | + (( − )′ −1( − )), where ( ) is a function to suppress the effects of outliers. It corresponds to the probability distribution of points with density
1 √| | ( ; , ) ∝
−21 (( − )′ −1( − )) The optimization task has the form: 1∗, … , ∗ = arg min 1,…, 1 ∑ ( ), =1 (4) where ( ) = ( ; 1, … , ; 1, … , ) = min ( ; , ) The function is introduced in order to achieve a relative decrease in the large values of the square of the Mahalanobis function. An example is the function ( ) = (√ ), where is the Huber function: ( ) = { 1 2 2, − 1 2
if ≤ 2, if < .
Along with the Huber function, you can also use the function ( ) = √ 2 + 2 − , which, unlike it, has a continuous 2nd-order derivative.
The problem (4) can be reduced to solving a system of equations: { = = 1 1 = ∑ ∑ ( − )′( − ), (5) matrices 1, … , . be found in [5], [6]. where = ( ( )), ( ) = ′( ).
For the solution to be unique, it is necessary that ′( ) be non-decreasing. But it follows from this that it is enough to make outliers of the order +1 1 -th part of the set of points in order to break the robustness of such a method [4].
Nevertheless, if the matrices 1, … , are given, then the problem of finding the centers 1, … , is robust. The loss of robustness is precisely connected with the evaluation of the A fairly comprehensive overview of other methods can
In this paper, we propose a new approach based on replacing the arithmetic mean in (1) with a robust differentiable mean estimate of { 1, … , }, which will be insensitive to outliers. Such a replacement will allow, at the level of the mathematical formulation of the problem, to lay the foundation for the stability of the solution of the problem. This is precisely the novelty of the proposed approach. Since the empirical distribution of the squares of the distances of the Mahalanobis from the points to the center of the nearest cluster may contain outliers, so the arithmetic mean value turns out to be distorted. As a consequence of this, the positions of the centers of the clusters may be displaced. The use of an outliers-insensitive average estimate can avoid distortion.
The differentiability of the estimate of the average value, insensitive to outliers, allows the use of gradient minimization algorithms to search for cluster centers. 1∗, … , ∗ and 1∗, … , ∗ , minimizing the functional Thus, in terms of outliers, it is proposed to search for centers 1∗, … , ∗ and the matrices 1∗, … , ∗ are the solutions = = 1 1 ∑ ( − )′( − ), = 1, … ,
The vector of sample weights for = ∗ and = ∗ can also be used as an estimate of the significance of points. points with the lowest values of the weights.
Since 1 + ⋯ +
= 1, the outliers will correspond to the
Stability with respect to outliers is achieved due to the fact that the weights of the points corresponding to outliers are significantly less than the weights of the points that are not outliers. It is also important that the point weight decreases as the absolute value of the difference between ‾ = ∇ { 1, … , }and increases. Such properties are a natural consequence of the robustness of mean estimates.
=1 { 1, … , }= arg min ∑ ( − ), where is twice differentiable strictly convex function with a minimum at zero. The -mean defined in this way has partial derivatives: where ‾ = { 1, … , }.
For example, if you take the function ( ) = √ 2 + 2 − , then for sufficiently small values > 0, you can get an approximate and smoothed version of the median. Choosing a sufficiently small value of , we can ensure that the value /
is negligible for those values that are far from the average value ‾ .
Smoothed variant of -quantile can be built based on the function
( ), (1 − ) ( ), ( ) = { ( (0+)+ (1 − ) (0+)), if = 0 (7) where ( ) is a function for smoothed variant of median.
The second method is based on the use of a censored arithmetic mean, in which the threshold value is estimated using a smoothed version of the -quantile: if > 0 if < 0, 1 , if < ‾ , if ≥ ‾ ,
≥ 0 and where is equal to the number of ≥ ‾ . In both cases
The third method takes a different approach to censoring values. Let’s define a truncated version of a quadratic function: 1 + ⋯ + 2 = { 2, if | | > .
With its help we define ̃ = { 1, … , }=
=arg min {
∑ | − |≤ ‾ ( − )2 +
∑ | − |> ‾ ‾2}, where ‾2 = { 1, … , }, = ( − )2. calculating ̃ :
From the definition we get a recurrence relation for +1 =
∑ | − |≤ ‾ , (
+ 1 + ) , ∑ | − |> ‾ , , , number of values : | − | > ‾ , . where ‾ , if | − ̃ | ≤ ‾ if | − ̃ | > ‾ , and ‾2 = { 1, … , }, = ( of values : | − ̃ | > ‾ . Note that
− ̃ )2, is the number =1 ̃ = ∑ , ∑ = 1.
=1 rewrited as follow { where 1 1 =
∑ ( − )′( − ), = 1, … , ,
To search 1∗, … , ∗ and 1∗, … , ∗ we apply an iterative scheme that corresponds to the analog of the Jacobi method for solving the system of nonlinear equations (6).
The initial positions of the centers are selected in some way, for example: = ∑ .
2) Step 1 is repeated until < (maximum number of iterations) or the sequence { ( ,1, … , , ; ,1, … , , )} will not concentrate around its condensation point.
The sets of point indices 1, … , corresponding to the partition into clusters are found before solving systems of equations. An additional condition | | = 1 is usually added to prevent singularity of the covariance matrices. Scale factor = | | can then be estimated using the -estimator [9].
+1 = (1 − ℎ) + ℎ ( ), where 0 ≤ ℎ ≤ 1. The second equation has a similar form: = ( ).
= ( ). +1 = (1 − ℎ) + ℎ ( ).
In this situation the system of equations (6) should be
Consider the relatively simple and classic IRIS dataset (3 classes, 4 attributes, 150 items). Here we use data in projection on 1st and 2nd principial components. As a rule, it is used for classification tasks. Here we will try to identify classes using clustering, using the Mahalanobis distance instead of Euclidean. Figure 1 shows the results of clustering using the robust algorithm proposed here and the classical algorithm. The result of clustering using the robust algorithm (both using and , = 0.001, = 0.96) differs from the given classification only at 3 points out of 150. The result of clustering using the classical algorithm differs from the given classification in no less than 6 points out of 150. For comparison, the classic kmeans with Euclidean distance differs from the given classification at 17 points out of 150. This simple example shows that the application of the proposed robust approach to clustering based on a realistic set of features can allow us to construct a partition that differs slightly from a given classification.
Consider another classic WINE dataset (3 classes, 13 attributes, 178 items). As a rule, it is also used for classification tasks. Here we will also try to identify classes using clustering, using the Mahalanobis distance instead of Euclidean. The result of clustering using the robust algorithm (both using and , = 0.001, = 0.97) differs from the given classification only at 3–4 points out of 178. The result of clustering using the classical algorithm differs from the given classification in no less than 6–7 points out of 178. This simple example shows that the application of the proposed robust approach to clustering based on a realistic set of features can allow us to construct a partition that differs slightly from a given classification.
Cosider datasets S1–S4 for clustering from . They contain 5000 points, 15 clusters. In Fig. 2–5 presents the results of clustering for sets S1–S4, respectively. On each figure, on the left side there is the result of the robust algorithm, and on the right side there is the classical one. During the training, a robust mean estimate was used with , = 0.001, = 0.96 − 0.97, ℎ = 0.95. It is easy to see that the robust algorithm allows one to find more adequate positions of the centers of clusters and the shape of the variance matrices.
In this paper, we considered a new variant of the k-means algorithm, in which the Mahalanobis distance was used instead of the Euclidean distance. The proposed new approach to constructing a robust version of k-means algorithm with the Mahalanobis distance bases on minimizing robust differentiable estimates of the mean. Its fundamental resistance ability to strong distortions in data was shown compared with the classical k-means algorithm. This is due to the fact that the robust average estimates used in the work limit the influence on the search for the position of the centers of clusters of points that are located at relatively large distances from them. The differentiability of the estimate of the average value, insensitive to outliers, allows the use of gradient minimization algorithms to search for cluster centers. Differentiability made it possible to construct an algorithm based on the iterative reweighting method, so that at each step the centers of the clusters are searched within the framework of the classical k-means with sample weights. Taking into account the shape of the covariance matrix significantly enhance the result. It should also be noted that the result of the robust algorithm is not completely stable. However, with a suitable choice of parameters and ℎ, it can be achieved that in most starts of the training procedure, an adequate result can be obtained.