Computationally efficient methods of clustering ensemble construction for satellite image segmentation

Abstract

Combining multiple partitions into single ensemble clustering solution is a prominent way to improve accuracy and stability of clustering solutions. One of the major problems in constructing clustering ensembles is high computational complexity of the common methods. In this paper two computationally efficient methods of constructing ensembles of nonparametric clustering algorithms are introduced. They are based on the use of co-association matrix and subclusters. The results of experiments on synthetic and real datasets confirm their effectiveness and show the stability of the obtained solutions. The performance of the proposed methods allows to process large images including multispectral satellite data.

Keywords

• ensemble
• co-association matrix
• nonparametric clustering algorithm
• multispectral image segmentation

1. Introduction

Suppose that the set of classified objects consists of vectors in feature space Rd : X  {xi  (xi1,..., xid )  Rd , i  1, N} . Let a set of particular clustering results G  {G(1) ,, G(l) ,, G(L)} be obtained with use of some algorithm    ( ) depending on a vector of parameters  taken at random from certain set of parameters Θ ; here G(l) is the l th variant of partitioning on M (l) clusters.

Denote by H ( l ) the binary matrix of size N  N defined for the l th partition as follows:

0, if the objects xi and x j are assigned to the same cluster, Hi, j ( l )  

1, otherwise, where i, j  1,, N , i  j .

After constructing a set of particular clustering results, it is possible to determine the consensus co-association matrix 1 L H  Hi, j  , Hi, j   Hi, j (l ) ,

L l1 where i, j  1,, N . The quantity Hi, j equals the frequency of classifying xi and x j into separate clusters in the set of clusterings G . A value close to zero suggests that these objects have a large chance of falling into the same group. A value close to 1 indicates that the chance of being in the same cluster is negligible for the pair.

After calculating the consensus co-association matrix, hierarchical clustering algorithm UPGMA with unweighted average linkage rule is applied to find the collective clustering result [16]. This method has the advantage that it allows discovering hierarchical structure of clusters, what greatly simplifies the process of interpreting the results.

To study the properties of cluster ensemble construction method, we suggest the following probabilistic model.

Suppose that there exists a latent (directly unobservable) variable U that determines the belonging of each object to some of M  2 classes. Each class is characterized by certain conditional distribution p(x | U  r)  fr ( x) , r  1,, M . Consider a model of data generation. Let an object’s attributed class be determined in accordance with a priori probabilities Pr  P (U  r) ,

M r  1,, M , where  Pr  1 . Then according to distribution fr (x) the value of x is obtained. This procedure is repeated r1 independently for each object.

Let some clustering algorithm  be used to partition the dataset X into M subsets. Since the labeling of clusters do not matter, it is convenient to consider the equivalence relation, i.e. to indicate whether the algorithm assigns a pair of objects to the same class or not. For each pair of objects a and b , we define the value

0, if the objects are assigned to the same cluster, Ha,b ( )  

1, otherwise, where a, b  X , a  b .

Let us choose an arbitrary pair a and b of different objects.

Let PU  P (U (a)  U (b)) be the probability of assigning the objects to different classes. For example, for M  2 this probability equals

PU  1  P (U (a)  1 | a)P (U (b)  1 | b)  P(U (a)  2 | a)P(U (b)  2 | b)  1  2 fr (a) fr (b)Pr2 , r 1 p(a) p(b) 2 where p( )   fr ( )Pr ,   a, b .

r1 Denote by Per ( ) the probability of error for algorithm  in assigning a and b to different classes, where Per ( )   PU , if 1  PU , if

Ha,b ( )  0, Ha,b ( )  1.

One can easily notice that

Per ( )  (1 Ha,b ( ))PU  Ha,b ( )(1 PU )  PU  (1 2PU )Ha,b ( ) .

Algorithm  depends on the random vector of parameters   Θ :    () . To emphasize the dependence of the results on the parameter  , in what follows we shall denote

Ha,b ( ())  Ha,b () , Per ( ())  Per () .

Let a collection H (1 ),, H ( L ) be obtained by algorithm  running L times with randomly and independently selected parameters 1 ,, L . For definiteness, we may assume that L is odd. The function  0, if H(H (1),, H ( L ))   1, 1 L

 H ( l ) 

L l1 otherwise will be called a collective (ensemble) decision by majority voting for a pair of objects. Within the framework of the model described above, the following properties of the suggested collective decision are fulfilled [15].

Proposition 1. Mathematical expectation and variance of the value of error probability for algorithm  () are equal, respectively, to: Image Processing, Geoinformation Technology and Information Security / I.A. Pestunov et al.

E  Per ()  PU  (1  2PU )PH ,

Var Per ()  (1 2PU )2 PH (1 PH ) , where PH  P (H ()  1) .

Denote by Per (1,, L ) the random function which for fixed arguments takes a value equal to the probability of error in classifying a and b by the ensemble algorithm. Here we denote by 1 ,, L independent statistical copies of random vector  . Consider the behavior of error probability for collective decision.

Proposition 2. Mathematical expectation and variance of the value of error probability for collective decision are equal, respectively, to:

E1,,L Per (1,, L )  PU  (1 2PU )PH,L ,

Var1,,L Per (1,, L )  (1  2PU )2 PH,L (1  PH,L ) , where PH,L  P  L1 lL1 H (l )  12   lLL/21CLl PHl (1 PH )Ll , · denotes the integer part.

We use the following a priori information about cluster analysis algorithm. We assume that the expected probability of erroneous classification E  Per ()  1 / 2 . That is, it is believed that the algorithm  classifies with better quality than the algorithm of random equiprobable choice. It follows from Proposition 1 that one of two variants should be fulfilled: a) PH  1 / 2 and PU  1 / 2 ; b) PH  1 / 2 and PU  1 / 2 . Let us consider, for definiteness, the first case.

Proposition 3. If E  Per ()  1 / 2 , and at that PH  1 / 2 and PU  1 / 2 , then with increasing an ensemble size, the expected probability of erroneous classification decreases, tending to the limit of 1  PU , and the variance of the value of error probability tends to zero.

The last statement allows to conclude that under the fulfillment of quite natural requirements, the usage of the ensemblebased approach will improve the quality of clustering.

3. Computationally efficient methods of clustering ensemble construction

Constructing ensemble solution based on consensus co-association matrix requires formation and processing of the square matrix of size N  N ( N is the number of elements). This method is not applicable for satellite image segmentation due to its quadratic complexity. This problem can be overcome by processing groups of elements instead of single elements. The way of grouping and choosing representatives may depend on algorithm specific features. Two methods of data grouping in order to construct consensus co-association matrix are proposed below.

The first method allows combining results obtained by arbitrary clustering algorithm. Having L partitions, each data element xi can be associated with a label vector ci  (ci1,, ciL ) where cij is a label of cluster containing xi in j th partition. Data elements with the same label vectors are merged into subclusters, because corresponding elements of co-association matrix (the distance between such elements) is zero. Subclusters are labeled as related data elements and will act as data elements while constructing of consensus co-association matrix. The distance between subclusters labeled as ci and cj is defined as 1 L 1, if a is true;

Hi, j  L l1 I cil  clj  , where I (a)  0, otherwise.

In this case, the size of co-association matrix is equal to the number of subclusters, which can vary from the maximum number of clusters in partitions to their product.

The second method allows to construct an ensemble solution for nonparametric mode-seeking clustering algorithms. In this case, each cluster contains one or more local density maxima (modes). Data elements are first divided into subclusters corresponding to single modes. Modes are used as representatives of subclusters and will act as data elements while constructing consensus co-association matrix. All elements of the subcluster are labeled as corresponding mode. Consensus co-association matrix is formed on the set of representatives from the basic partition (the most detailed partition in the ensemble). The correspondence between different partitions is established by determining clusters containing the representatives from the basic partition (as points in the feature space). Therefore, the size of co-association matrix is much less than N and equal to the number of modes in base partition.

Fig. 1 illustrates the second method and shows two different partitions ( L  2 ) of the same data into clusters (highlighted by colors) that correspond to some density modes. First partition is considered basic and it contains three representatives (A, B, C). When establishing the correspondence between partitions, representatives A and B are assigned to one cluster in the second partition and representative C – to another. Thus, the distance between representatives A and B equals 1/2 (since they lie in different clusters in the basic partition) while the distances between pairs A, B and B, C are equal to 2/2.

The proposed methods were used to construct an ensemble of nonparametric clustering algorithms: MeanSC (based on Parzen density estimation), CCA and HCA (based on the histogram density estimation). Ensemble algorithms EMeanSC [17] and HECA [18] were designed using the first and the second ensemble construction method respectively. Basing on clustering algorithm CCA two ensemble algorithms were developed: CCAE (using first method) and ECCA [19] (using second method). The implementation of both proposed methods based on the same clustering algorithm allows to compare these methods.

4. Experimental results

Experimental results show that proposed clustering ensemble construction methods improve the quality and the stability of obtained results. Moreover, they significantly simplify algorithm parameters selection. Computational efficiency of the proposed methods allows processing large satellite images.

Experimental results on both synthetic and real datasets were obtained on Intel Core i7 3.2 GHz quad-core CPU.

Experiment 1. Two different two-dimensional synthetic datasets [20] were clustered. First dataset consists of 3 classes containing 1000 points each with uniformly distributed “bridge” (200 points) and uniformly distributed noise (1000 points). Fig. 2 shows initial data (Fig. 2a) and the result of EMeanSC ensemble clustering algorithm (Fig. 2b). Correct data decomposition with MeanSC clustering algorithm requires precise parameter setting while ensemble algorithm successfully detects 4 clusters and noise (black points in Fig. 2) even with bad interim results (Fig. 2e). Second synthetic dataset (“bananas”) was built in PRTools toolbox [21] with parameter   0.7 . It consists of 400 points and represents 2 linearly inseparable classes (Fig. 2c). Ensemble clustering result of EMeanSC algorithm is shown in Fig. 2d.

a b c

d e Fig. 2. Experiment 1: synthetic datasets (a,c) and clustering results obtained by ensemble EMeanSC algorithm (b,d) and MeanSC algorithm with different bandwidth parameter values (e).

Experiment 2. Two-dimensional synthetic dataset containing 5 classes [20] was clustered. Three classes represent normal distribution with mathematical expectation vectors 1  (188,100) ,  2  (75,100) , 3  (75,150) and covariance matrices  42 1    0 0  122 42  , 2   0 0   212

 , 3   122   0 0  82  respectively. Fourth class represents uniformly distribution along the ring with center at (188,100) and radiuses Rmin  20 and Rmax  25 . Fifth class represents uniform distribution along the circle with center at (188,100) and radius R  45 . Elements of the fifth class were further radially displaced by a random value having normal distribution with standard deviation   4 . Clusters containe 220, 600, 600, 400 and 500 points respectively (Fig. 3a). There we have a generated reference partition (Fig. 3a), so the accuracy of clustering is determined as the percentage of correctly classified elements. Each class from the reference partition is associated with a cluster (one or none) containing the largest number of elements from this class.

Image Processing, Geoinformation Technology and Information Security / I.A. Pestunov et al.

Fig. 3b represents results obtained by ECCA clustering algorithm ( L  8 ). The accuracy of clustering is 99.48%. Clustering algorithms from open source package ELKI [22] could not correctly separate all 5 classes. The best results (Fig. 3c and 3d) were obtained by density-based hierarchical algorithm OPTICS (79.7% for parameters epsilon  12 , minpts  8 and hierarchy cutoff level 4.9) and hierarchical nearest neighbor algorithm SLINK (72.72% for parameter threshold  5 ).

Experiment 3. The purpose of this experiment is to demonstrate an increasing stability of the ensemble clustering results with ensemble size ( L ) growth. The accuracy of clustering “bananas” dataset (see Fig. 2c) with respect to grid parameter m (bandwidth) for CCA(m,T ) algorithm and corresponding ensemble algorithms ECCA(m, L, T ) and CCAE(m, L,T ) with L  5 and L  10 is shown in Fig. 4. Parameter T was fixed at value 0.3. As it can be seen from the graph, the stability of the results increases with ensemble size growth.

a b

Experiment 4. Fig. 5 shows the result of WorldView-2 satellite image clustering (Burmistrovo, Novosibirsk region). Image size is 2048×2048 pixels; four spectral bands (1, 3, 5 and 8) were used. Image was processed by ECCA algorithm (with L  8 ) in 0.5 seconds. This experiment confirms the ability of the developed ensemble algorithm to effectively process multispectral satellite images.

Experiment 5. The purpose of this experiment is to demonstrate computational efficiency of the proposed ensemble construction methods and to compare them. Six images were used (Fig. 5a and 6) [23], including 3 satellite ones (WorldView-2 and Landsat-8, 4 bands selected). Table 1 shows the time of constructing clustering ensemble containing 8 elements with CCAE and ECCA algorithms. The time for 8 CCA runs (in parallel) performed before the ensemble construction is shown separately.

Image Processing, Geoinformation Technology and Information Security / I.A. Pestunov et al.

The results show that second ensemble constructing method based on the use of density-modes (ECCA algorithm) leads to much smaller size of consensus co-association matrix that substantially reduces processing time.

a b

5. Conclusion

Acknowledgements References

In this paper, two methods of constructing clustering ensemble based on co-association matrix are proposed and theoretically substantiated. Developed ensemble clustering algorithms are based on nonparametric density estimates and they don’t make hard assumptions on the density distribution function. Experimental results on both synthetic and real datasets confirm high quality of the obtained solutions and their stability. Unlike common ensemble construction methods, the proposed approaches can be directly applied to large satellite images (containing millions of pixels) and demonstrate high performance.

This work was partially supported by Presidium of the RAS (project 0316-2015-0006). [1] Gonzalez RC, Woods RE. Digital image processing. Moscow: Tekhnosphera, 2006; 812 p. (in Russian) [2] Dey V, Zhang Y, Zhong M. A review on image segmentation techniques with remote sensing perspective. Proceedings of ISPRS TC VII Symposium – 100

Years ISPRS. Vienna: ISPRS, 2010; XXXVIII(7A): 31–42. [3] Pestunov IA, Sinyavsky YuN. Clustering algorithms in problems of segmentation of satellite images. Bulletin KemSU 2012; 52(4/2): 110–125. (in

Russian). [4] Jain AK. Data clustering: 50 years beyond K-means. Pattern Recognition Letters 2010; 31(8): 651–666. [5] Krstinic D, Skelin AK, Slapnicar I. Fast two-step histogram-based image segmentation. Image Processing, IET 2011; 5(1): 63–72.

References