Experiments and results

In all experiments the stopping criterion for FCM was a maximal squared difference in membership values of two successive U matrices of $\epsilon = 0.001$ (i.e. $max_{ik}\{(u^{new}_{ik} - u^{old}_{ik})^{2}\} < .001$). The stopping criterion for HCM was an iteration for which no data object changed classes. The initial V's for FCM and HCM are created randomly within the feature space. For each feature the initial values are randomly chosen to be in the range (determined from the data set) of the feature.

We will examine the results of the FCM experiments first because, for the studied domains we found less extrema, presentation of the results is easier. For all FCM trials m=2.

In doing experiments, we are primarily interested in domains that have multiple local extrema for a given clustering algorithm. For FCM, the Iris and MS domains have only 1 extrema that we can find. The single feature data set was found to have 11 extrema. Only 3 of the extrema occur more than 10% of the time. However, the averages of the extrema makes this domain an interesting test for genetic guided clustering.

Table 1 lists number of trials, the average J₂ values and the standard deviations found by FCM for each of the domains. Table 2 shows the extrema found by FCM for each of the small data sets.

 

Data set # of 2c|Average Values std. dev. Lowest J₂

$$\;\,\;\, \;\,\;\,$$ runs iter.

single feature 2000 26 0.926 0.099 0.731

Iris 5000 19 60.576 60.576

multiple sclerosis 3000 20 65766.453 65766.453

 

2|c|Iris 2|c|MS 2|c|single feature

Extrema Value Count Value Count Value Count

1 60.576 5000 65766.453 3000 0.731 355

2 0.893 889

3 0.949 10

4 1.016 1

5 1.050 720

6 1.068 3

7 1.069 5

8 1.104 3

9 1.488 12

10 1.535 1

11 1.689 1

Although GGA is applied to R_m in (7), we will discuss GGA outputs in terms of J_m values as computed by (4) in order to facilitate clear comparisons with FCM. Table 3 shows the GGA results in terms of J₂ values, number of generations, population size and mutation rate. All results are averages over 50 trials. Our GGA approach always finds the best known local extrema for these domains given a large enough population, enough generations and a mutation rate high enough to enable the necessary search. This stands in contrast with two previous approaches, which both required subsequent iteration of FCM on the best GA result to find the best FCM partition (equivalent J_m values) [1,4].

In the single feature domain, as the mutation rate is lowered the GA finds the second lowest extrema (.893), for example, 5 times as shown in Table 3. Experiments have shown that low mutation rates work well (less than 5%) with less than (1%) being acceptable for the data sets with few extrema. For these small data sets, the GGA relatively quickly finds the same best extrema that FCM does in most cases. There is occasionally some slight roundoff error for the MS domain. So, for FCM a GA can skip local extrema and will terminate at a best FCM extrema in almost all cases.

   

Data set Pop. size Gens. Mut. Rate 2c|Average Values Lowest J₂

J₂ st. dv. value found

single feat. 30 500 0.046 0.731 .731

single feat. 30 500 0.030 0.747 0.049 .731

single feat. 20 500 0.046 0.734 0.023 .731

Iris 30 300 .008 60.58 60.58

multiple scl. 30 300 .007 65766.469 0.014 65766.453

multiple scl. 30 300 .009 65766.484 0.028 65766.453