Fuzzy C-Means Cluster Analysis Based on Mutative Scale Chaos Optimization Algorithm for the Grouping of Discontinuity Sets

1 Introduction

Discontinuities with different geological origins are widely distributed in rock masses. Since discontinuities strongly influence the mechanical and hydraulic behavior of rock masses (Hammah and Curran 2000), careful collection and analysis of discontinuity data within a rock medium are of paramount importance for civil engineering and mining applications. One of the important challenges that engineers face in this respect is the identification and delineation of discontinuity sets with similar orientations.

The conventional method used for identifying discontinuity groups is contouring on stereographic plot projections of discontinuity poles. This process is very subjective because the clustering results depend heavily on the size of the reference circle. Different data analysts may arrive at very different conclusions depending on their backgrounds, experiences, and personal biases and inconsistencies. Differences in results could be even more pronounced in cases where the boundaries between clusters are unclear (Hammah and Curran 1998). Thus, this conventional method is not entirely satisfactory in some cases, and has led to the development of alternative techniques for the automatic identification of discontinuity sets (Jimenez-Rodriguez and Sitar 2006).

The first objective clustering algorithm was proposed by Shanley and Mahtab (1976). However, in this method, the proper radius of a small sphere must be assigned to determine the density point. Mahtab and Yegulalp (1982) proposed a clustering algorithm using a rejection scheme based on a randomness test derived from the Poisson distribution. Based on the assumption that the orientation of each discontinuity set can be modeled as a mixture of truncated bivariate normal distributions, Marcotte and Henry (2002) proposed a method for identifying discontinuity sets. However, in some cases, making a priori assumptions about the probabilistic structure of discontinuity properties may be a difficult task. Thus, clustering methods that use no a priori probabilistic information have also been developed. The distance measure between discontinuities is a key issue in identifying discontinuity sets (Jimenez-Rodriguez and Sitar 2006). Harrison (1992) first applied fuzzy objective functions to analyze discontinuity orientation data. Hammah and Curran (1998) proposed the fuzzy C-means (FCM) method for the automatic identification of discontinuity sets. Distance and validity measures were later proposed for the fuzzy cluster analysis of orientations (Hammah and Curran 1999, 2000). Sirat and Talbot (2001) proposed a method based on the use of artificial neural networks for classifying discontinuity sets. Utilizing multiple joint properties, Zhou and Maerz (2001, 2002) and Tokhmechi et al. (2011) proposed K-means clustering for grouping discontinuity sets. FCM and K-means belong to dynamic clustering algorithms, which commonly require an initial assignment of the number of target sets and cluster centers. Both algorithms are not guaranteed to achieve a global optimum; instead, a local optimum is obtained (Wong and Liu 2010; Hammah and Curran 1998). The clustering results are influenced by the initial cluster centers, and improper initial cluster centers can lead to incorrect clustering results. When the boundaries between clusters are unclear, proper initial cluster centers are difficult to chose, and the results are unreliable. A common approach for obtaining valid results is running the algorithm several times and observing the resulting partitions carefully. An improvement on this method is discussed in the present paper.

To avoid the difficulty in choosing proper initial cluster centers, Jimenez-Rodriguez and Sitar (2006) and Jimenez (2008) proposed a spectral clustering method for identifying discontinuity sets, in which an affinity matrix was constructed to evaluate the similarity between any two arbitrary discontinuities. Eigenvalues of the affinity matrix were used to construct the vector space R ^k associated with the projection points of discontinuities. The spectral clustering algorithm makes a transformation of the original discontinuity orientation data into a transformed space where the selection of proper initial cluster centers is natural. K-means clustering is conducted in the transformed space. Hence, sometimes, the spectral clustering is not guaranteed to achieve a global optimum.

Chaos is a kind of nonperiodic moving style. It has three important dynamic properties (Tavazoei and Haeri 2007), namely, quasi-stochastic, regularity, and ergodicity. Given these properties of chaos, the chaos optimization algorithm (COA) is a new searching method that often affords global optimization. The basic idea of the algorithm is to transform the problem variables from the solution space to chaos space and then perform a search to determine the solution by virtue of the randomicity, orderliness, and ergodicity of the chaos variable. COA has many advantages. This method is not sensitive to the initial value and can easily skip out of the locally minimum value. This method also has high searching efficiency. The advantages of chaos optimization can remedy the defect of FCM. In the current paper, an FCM method based on mutative scale COA is proposed for the automatic identification of discontinuity sets.

2 Clustering Algorithm

The FCM method separates a data set into C clusters by minimizing the fuzzy objective function (Bezdek 1981):

$$ J = \sum\limits_{j = 1}^{N} {\sum\limits_{i = 1}^{C} {\left( {u_{ij} } \right)^{m} } } d^{2} \left( {X_{j} ,V_{i} } \right)\;\left( {C \le N} \right) $$

(1)

where N is the total quantity of the observations, C is the number of cluster centers, X _j denotes the jth observation, and V _i denotes the ith cluster center of the data set. d(X _j , V _i ) is the distance between observation X _j and cluster center V _i , and u _ij is the fuzzy membership factor that defines the degree of belonging of the jth observation to the ith set. m is the degree of fuzzification and m = 2 is believed to be the best value for most applications.

The first procedure of FCM is initializing C cluster centers. All observations are assigned to each set according to their degree of membership to each cluster. The new cluster centers are then computed according to current cluster results, and the degree of membership is updated according to the new cluster centers. These iterative steps are Picard iterations [Hammah and Curran (1998) gave detailed iterative formulas] in the FCM. The FCM method of Hammah and Curran (1998) is not guaranteed to achieve a global optimum, because Picard iterations are used to minimize the objective function. In this paper, mutative scale COA is adopted instead of Picard iterations. Owing to the ergodicity property of chaos variables, the new algorithm often achieves a global optimum, and the result is not heavily influenced by the initial chaos variables.

Global optimization seeks the best set of parameters that maximizes or minimizes an objective function (Tavazoei and Haeri 2007). A nonlinear problem with constraints can be described as:

$$ \min f\left( {x_{1} ,x_{2} , \ldots x_{n} } \right)\;x_{i} \in \left[ {a_{i} ,b_{i} } \right]\;i = 1,2, \ldots ,n $$

(2)

where x _i denotes the ith variable of a total of n variables, and a _i and b _i are the lower and upper boundaries of the ith variable, respectively.

On the basis of the ergodicity property of chaos, chaos optimization can seek for the optimum solution of the objective function as described above. Chaos variables are generated by the logistic map (Zhang et al. 1999). This map is defined by the following function:

$$ \gamma^{{\left( {k + 1} \right)}} = \mu \gamma^{\left( k \right)} \left( {1 - \gamma^{\left( k \right)} } \right) $$

(3)

where μ is a control parameter and 0 ≤ μ ≤ 4. The value of μ determines whether γ stabilizes at a constant value, or oscillates between a limited sequence of values, or behaves chaotically in an unpredictable pattern. With μ set at 4, a very small change in the initial value of γ will cause a large difference in its long-term behavior, which is just the typical characteristic of chaos (Yang et al. 2007). In this paper, μ = 4.

By shrinking the intervals of the optimum solution, the mutative scale chaos optimization can reduce the solution runtime and improve accuracy. The algorithm is described as follows (Zhang et al. 1999):

• 1. k = 0, r = 0, f* = ∞ are set, where k is the symbol of chaos iterations, r is the symbol of mutative scale, and f* is the optimum value of the objective function.

• 2. The different values of chaos variables 0 < γ ^(k) _i  < 1 (i = 1, 2,…, n), are randomly initialized. a ^(r) _i  = a _i , b ^(r) _i  = b _i are also initialized.

• 3. The variables γ ^(k) _i (i = 1, 2,…, n) are mapped into the variance range of the optimization variables by the following equation:

  $$ x_{i}^{\left( k \right)} = a_{i}^{\left( r \right)} + \gamma_{i}^{\left( k \right)} \left( {b_{i}^{\left( r \right)} - a_{i}^{\left( r \right)} } \right)\left( {i = 1,2, \ldots ,n} \right) $$

  (4)

• 4. f, the value of the objective function, is calculated. If f < f*, then the value of f is assigned to f*, the value of γ ^(k) _i is assigned to γ _i *, and the value of x ^(k) _i is assigned to x _i * (let f* = f, γ _i * = γ ^(k) _i ,  and x _i * = x ^(k) _i ), where γ _i * is the current optimum chaos variable and x _i * is the current optimum variable.

• 5. Chaos iterations are performed by the equation:

  $$ \gamma_{i}^{{\left( {k + 1} \right)}} = 4\gamma_{i}^{\left( k \right)} \left( {1 - \gamma_{i}^{\left( k \right)} } \right) $$

  (5)

• 6. Steps (3), (4), and (5) are repeated until f* remains almost unchanged.

• 7. Shrinking intervals on which the optimum solution is sought are achieved by the following equation:

  $$ a_{i}^{{\left( {r + 1} \right)}} = x_{i}^{*} - \lambda \left( {b_{i}^{\left( r \right)} - a_{i}^{\left( r \right)} } \right) $$

  (6)
  $$ b_{i}^{{\left( {r + 1} \right)}} = x_{i}^{*} + \lambda \left( {b_{i}^{\left( r \right)} - a_{i}^{\left( r \right)} } \right) $$

  (7)

  where λ $\in$ [0, 0.5]. The value of λ is 0.3 in the present paper. If a ^(r+1) _i  < a ^(r) _i ,  the value of a ^(r) _i is assigned to a ^(r+1) _i (let a ^(r+1) _i  = a ^(r) _i ); if b ^(r+1) _i  > b ^(r) _i ,  the value of b ^(r) _i is assigned to b ^(r+1) _i (let b ^(r+1) _i  = b ^(r) _i ). In addition, γ _i * should be recalculated by:

  $$ \gamma_{i}^{*} = \frac{{x_{i}^{*} - a_{i}^{{\left( {r + 1} \right)}} }}{{b_{i}^{{\left( {r + 1} \right)}} - a_{i}^{{\left( {r + 1} \right)}} }} $$

  (8)

• 8. The new chaos variables are calculated by the following equation:

  $$ \nu_{i}^{\left( k \right)} = \left( {1 - \eta } \right)\gamma_{i}^{*} + \eta \gamma_{i}^{\left( k \right)} $$

  (9)

  where η is a real number between 0 and 1. η = 0.2 in the present paper.

• 9. Using new chaos variables ν ^(k) _i ,  steps (3), (4), and (5) are repeated.

• 10. Steps (8) and (9) are repeated until f* remains almost unchanged.

• 11. The search region is continuously decreased. The value of η is decreased and steps (7), (8), (9), and (10) are repeated.

• 12. Step (11) is repeated until f* remains almost unchanged, after which the algorithm is stopped. The number of the repetitions usually is 4 or 5. x _i * is now the optimum solution and f* is the optimum value of the objective function.

In the present paper, the sine of the acute angle between discontinuity unit normal vectors is used as a measure of their distance. For the grouping of discontinuity sets, Eq. (1) is the objective function with constraints V _i  = (α _i , β _i ), α _i  $\in$ [0, 360], and β _i  $\in$ [0, 90], where α _i and β _i denote the dip direction and dip angle of the ith cluster center, respectively. For a cluster number of C, there are 2C variables in the objective function. First, the 2C chaos variables are initialized. The dip directions and dip angles of C cluster centers are then computed by mapping the 2C chaos variables into the range of dip directions and dip angles by Eq. (4). Next, the value of the fuzzy objective function is computed according to Eq. (1). Finally, new cluster centers and the new value of the objective function are computed using chaotic variables iterations until the optimum cluster centers are found. Figure 1 illustrates the overall process of this new algorithm for grouping discontinuity sets. The optimum solutions of the objective function are the cluster centers of discontinuity sets.

Fig. 1

Flowchart of the new algorithm for the grouping of discontinuity sets. γ ^(k) _αi and γ ^(k) _βi respectively denote the chaos variables of dip direction and dip angle. a ^(r) _αi and b ^(r) _αi respectively denote the lower and upper boundaries of the dip direction of the ith cluster center. a ^(r) _βi and b ^(r) _βi respectively denote the lower and upper boundaries of the dip angle of the ith cluster center

Determining the number of discontinuity sets in the cluster analysis of discontinuity data is very important. The cluster validity measure is a very effective approach for determining this value. In general, the number of discontinuity sets is less than eight. Therefore, several numbers of sets can be assigned, and the most appropriate number of sets can be ascertained using validity measures. A number of validity measures have been proposed by Hammah and Curran (2000). In this paper, the Xie-Beni and Fukuyama-Sugeno indices are adopted to measure cluster validity, because both indices are easy to compute and their physical meanings are clear.

3 Example Analysis

3.1 Analysis of Artificial Data

To investigate the applicability of this algorithm, the cluster method was applied to an artificial data set. Four clusters of discontinuities of different numbers and different orientations were generated using bivariate normal distributions (Chen et al. 1995; Zanbak 1977; Marcotte and Henry 2002). The parameters of the bivariate normal distributions and the number of each discontinuity cluster are listed in Table 1. FCM has an inherent difficulty in choosing the proper initial cluster centers when the boundaries between clusters are unclear. To show our improvement over the FCM method of Hammah and Curran, the discontinuity data were generated with overlapping orientations (Fig. 2).

Table 1 Parameters of the bivariate normal distributions of clusters

Fig. 2

Pole of the artificial discontinuity data

In the analysis of the artificial data, the number of discontinuity sets is known. The boundaries between clusters in the artificial data are unclear. Using the FCM method, different choices of initial cluster centers can lead to different partitions of the same data. Table 2 and Fig. 3 show the flaw of FCM. In Fig. 3a, it is shown that the FCM method fails to identify discontinuity sets when improper initial cluster centers are chosen. As listed in Table 2, for this case, the assignment error rate is 63 %. Figure 3b shows that FCM can only achieve a local optimum. Discontinuity normals that trend west are clearly a part of Set 4, but they were wrongly assigned to Set 2. This obvious error can be seen from Fig. 3b.

Table 2 Clustering results of the fuzzy C-means (FCM) method

Fig. 3

Comparison of the clustering results of the fuzzy C-means (FCM) method with different initial cluster centers. a Clustering results No. 1. b Clustering results of No. 2

The Shanley and Mahtab method is the first published clustering method based on an objective function and is often still used today. Thus, this method was chosen as a benchmark. The spectral clustering algorithm transforms the original discontinuity orientation data into a different space so that the selection of proper initial cluster centers is natural (Jimenez-Rodriguez and Sitar 2006). This method was also chosen as a benchmark. The clustering results of these two methods are listed in Table 3. Figure 4 shows the clustering results obtained by these methods.

Table 3 Clustering results obtained with the Shanley and Mahtab method and the spectral clustering algorithm

Fig. 4

Clustering results of the Shanley and Mahtab method and the spectral clustering method with artificial data. a Clustering results of the Shanley and Mahtab method. b Clustering results of the spectral clustering method

The performance of the Shanley and Mahtab method is unsatisfactory. As indicated in Table 3, the assignment error rate of the Shanley and Mahtab method is 21 %. Figure 4a shows that two groups (Set 2 and Set 3 in Fig. 2) are merged into one group by the Shanley and Mahtab method, and the discontinuities trending to the west are separated from Set 4. For this case, the assignment error rate of the spectral clustering method is much lower, being only 10 %. Clustering results by this method are very similar to the groups statistically defined in advance, although the average directions of each computed discontinuity set differ slightly from those statistically defined in advance. However, the spectral clustering algorithm is shown to perform well.

The new algorithm in the present paper uses mutative scale chaos optimization, which often provides global optimal results, instead of the Picard iterations in FCM. Owing to the ergodicity property of chaos variables, the initial chaos variables do not heavily influence the final result. Thus, the new algorithm does not need to choose the proper initial cluster centers. The clustering results of the new algorithm with different initial cluster centers are presented in Table 4 and Fig. 5 shows the poles of the re-grouped discontinuity sets.

Table 4 Clustering results obtained with the new algorithm

Fig. 5

Comparison of the clustering results of the new algorithm with different initial cluster centers. a Clustering results of No. 1. b Clustering results of No. 2

Table 4 indicates that, although the initial cluster centers are different, the mean orientations of the re-grouped discontinuity sets from the new algorithm are all very similar to the data sets defined in advance. Figure 5 shows that the poles of the re-grouped discontinuity sets are almost the same in cases with different initial cluster centers. Comparing Table 2 with Table 4, the value of the object function obtained by the new algorithm is found to be less than the value obtained by the FCM method. As a method of global optimization, the new algorithm provides better clustering results than FCM. For this case, the assignment error rate of the new algorithm is only 3.5 %, which is less than the 15.5 % of the FCM, the 21 % of the Shanley and Mahtab method, and the 10 % of the spectral clustering algorithm. The clustering results of the new algorithm are in agreement with the data sets defined in advance, which verifies the good performance of the proposed new algorithm.

3.2 Analysis of the Jimenez-Rodriguez and Sitar (2006) Data

In this section, we further validate our method with the data of discontinuity orientations taken from Jimenez-Rodriguez and Sitar (2006). The set consists of near-vertical discontinuities and near-horizontal discontinuities. Considering two discontinuity sets, in Fig. 6, we show a comparison among clustering results computed with the new method, the FCM method, the Shanley and Mahtab method, and the spectral clustering algorithm. The clustering results obtained with the method proposed in the present paper are almost the same as those obtained with the FCM method. This is because the boundary between two sets is obvious, and choosing the proper initial cluster centers of these two clear sets is not difficult. As Jimenez-Rodriguez and Sitar (2006) stated, several quasi-vertical discontinuities are assigned to the joint set of quasi-horizontal discontinuities. The reason for this is that the discontinuities trending approximately N300E are nearer to the cluster center with low dip angles than those with steep dip angles. As shown in Fig. 6c and d, the spectral clustering algorithm and the Shanley and Mahtab method provide the same results for this case. The distance between two adjacent poles in the same set is small, whereas the distance between the two sets is great. Thus, the spectral clustering algorithm and the Shanley and Mahtab method both separate discontinuities belonging to two sets as a human would identify.

Fig. 6

Comparison of the clustering results of the new clustering method and those of three other methods with two discontinuity sets. a FCM. b The new clustering method. c Spectral clustering algorithm. d Shanley and Mahtab method

Considering three discontinuity sets, Fig. 7 shows a comparison among clustering results obtained with the four methods. In Fig. 7a, the FCM method provides unreliable clustering results that are clearly different from those obtained with other methods. The reason for the failure to obtain general agreement among the methods is that the boundary between Set 2 and Set 3 is unclear. The FCM method only achieves a local optimum. However, the new method proposed in the present paper provides correct clustering results that are exactly the same as those obtained with the Shanley and Mahtab method and with the spectral clustering algorithm. The average dip direction of Set 2 is 225°, and is perpendicular to the average dip direction of Set 3, which is 313°. Set 2 and Set 3 should not be merged into one set, although they are all near-vertical discontinuities. The Xie-Beni index with three sets is 0.08, which is less than the Xie-Beni index with two sets, which is 0.18. In addition, the Fukuyama-Sugeno index with three sets is −144, which also is less than the Fukuyama-Sugeno index with two sets, which is −51.5. The validity measure indicates that the most appropriate number of sets should be three. Considering three sets, the new method is shown to perform well.

Fig. 7

Comparison of the clustering results of the new clustering method and those of three other methods with three discontinuity sets. a FCM. b The new clustering method. c Spectral clustering algorithm. d Shanley and Mahtab method

4 Conclusions

The fuzzy C-means (FCM) algorithm for grouping discontinuity sets suffers from the inherent difficulty in choosing proper initial cluster centers. When initial cluster centers are not properly selected, global optimal results cannot be obtained. To solve this issue, an FCM cluster method, based on a mutative scale chaos optimization algorithm (COA), is proposed for the automated identification of discontinuity sets in this paper. Global optimal clustering results are obtained by COA owing to the ergodicity property of chaos. The clear advantage of this new method is that there is no need to choose proper initial cluster centers.

For an example case with artificial data, the new clustering method provided results that were almost equal to the discontinuity sets statistically defined in advance. The new algorithm performed very well. Compared with the cluster results by the FCM method of Hammah and Curran, a clear improvement is demonstrated. Compared with the cluster results obtained by the spectral clustering algorithm and the Shanley and Mahtab method, the assignment error of the proposed method is the lowest, and the average directions of each set obtained by the proposed method are the closest to the average directions defined in advance. The proposed method was then applied to analyze the Jimenez-Rodriguez and Sitar (2006) discontinuity data. The clustering results obtained by the proposed method were compared with those of the Shanley and Mahtab method, the spectral clustering algorithm, and the FCM method of Hammah and Curran. The optimum number of sets was identified to be three. Considering three discontinuity sets, the proposed method, the spectral clustering algorithm, and the Shanley and Mahtab method provided the same clustering results. The new method was shown to be an improvement over the FCM method and to perform as well as the Shanley and Mahtab method and the spectral clustering algorithm.