A Combination of a symbolic and a natural classifier applied to
remote sensing images
Case of study: Penang Island
3.2 The Algorithm
The Cobweb algorithm maintains a hierarchy of classes, and updates some classes in this hierarchy any time it gets a new pixel. The first pixel makes a new class by itself, and the second may lead to a new class (if it is different from the first), both of them becoming subclasses of a newly generated root-class. This is enough to bootstrap the process. The next pixels will be driven through the growing hierarchy, starting at the root and following the most adequate path down the tree. Full details of the algorithm are give in [4]. This section provides only the most important assumptions behind Cobweb.
When driving an incoming pixel through the hierarchy, Cobweb tries to adapt the classes to account for the new data. This updating process is twofold. First, several statistics (such as the estimated mean and standard deviation) are compared and stored in each class to provide some descriptive information. Second, the local structure of the hierarchy (i.e. one class along with its sub-classes) is tentatively modified, and the changes are made permanent if they lead to the increase of a heuristic (described below). Those structure modification operators include the creation of a new class covering only the incoming pixel (in which case the algorithm stops, and goes on considering the next pixel), the merging of two sub-classes (by insertion of an intermediate class), or the splitting of one the sub-classes (by promoting this class sub-classes as new direct descendants ) . In each case a new partition is generated at the current level, and this new partition is evaluated. The best possible modification is applied before the algorithm recourses to a deeper level, to continue the incorporation of the pixel. The process stops when reaching a terminal node (a node with no sub-class).
As any clustering algorithm, Cobweb tries to group pixels that are similar, while separating dissimilar ones. This is performed while generating variations of the current partition. Each generated partition is evaluated in terms of the precision of the classes involved. If II (C ) measures the denseness of class C, Cobweb uses the following heuristic to distinguish between candidate partions:
In this formula, C is the main class, which is split into {C1 ,……, Ck} is the proportion of pixels of C affected to Ck. In turn, II (Ck) can be defined as:
Where sik is the estimated standard deviation on spectral values of the ith band for pixels converted by Ck.
This formula can be seen as an average of the gain in precision implied by splitting C into {C1,…., Ck}. By computing the value of this heuristic for each potential partition, Cobweb can select the one with the best score and apply the corresponding update. It thus continually updates the class hierarchy to reflect the data, and keeps a completes range of general to specific classes.
4. A neural classifier
4.1 Principles
Our second clustering method is based on competitive learning as proposed by Rumelhart and Zipser. By training, this unsupervised method allows the neural network to find homogeneous clusters in the input population by self-organization. The network is supposed to discover statistically salient features in the pattern input set.
After learning, each input vector is assigned to one cluster. In a cluster, vectors are similar to each other. Homogeneity of the clusters depends on this similarity between vectors in one class.
The neural network produces one resulting images where pixels are gathered together into classes. This map is considered as a thematic map but without labeled classes. In order to assign a label to each class, expert's knowledge is required.
4.2 Competitive algorithm
The proposed model contains two layers n-m-which are fully interconnected via randomly initialized weights. The input layer contains n neutrons corresponding to the number of components of the input vector. These components corresponds to spectral values of one pixel (x,y) in each image. Each vector is successively presented to the input layer [see figure 1].
Figure 1: Self-Organizing Neural Net
After propagation of information through the network via connections, the winning output neuron is selected by a 'Winner-takes-all' rule. The following rule describing the minimal distances between the input vector x and the weights of connection which feed into unit i wi. The winner k is the output neuron which possesses the minimal distance:
||.|| denotes the Euclidian norm. Moreover, with this method, there is no need for normalization of the weights and the input data.
The adaptation rule modified weights according to a variation vector:
where the variation vector corresponds to a difference vector:
The parameters a such as 0
£ a <<1, is called the learning rate. The modification of weights can be instantaneous i.e. weights are modified at each time t by the presentation of a new example, or global i.e. after the presentation of all the set of examples. In this case the variation is computed at each time t and the update is done at the end of each presentation of pattern set. Advantages of this latest method are that the order of pixel presentation has no importance and convergence of the network is quicker. [3] [1].
After several presentation of the pattern input set, the network becomes stabilized. Pixels are definitively affected to one specific class and the total square error E which is computed after each presentation of the input set, becomes minimal.
k denotes the unit winning with input xp.
