0 
+ 
o 
© 
UA 
T 
o 
N 
ul 
-— 
"oO 
© 
+ 
Nd’ 
© 
© 
~ 
| 
= 
œ 
unl 
I 
co 
~ 
| 
| — 
— 
— 
— 
Oo 
N 
— 
—— 
N 
-— 
at 
| 
à 
a 
ul 
© 
~ 
+ 
-— 
~ 
ul 
N 
— 
Ww 
N 
Oo 
a 
ul 
oO 
n 
-— 
© 
N 
~ 
  
ur. 
S | 
"o 
EA 
mily 
3 
P 
3 
iQ 
  
ng 
ee 
to 
of 
ot 
is 
al 
of 
ne 
he 
9) 
is 
be 
ry 
ly 
ce 
od 
ss 
  
  
BAND PRED VAL 
BLUE 1.075 
GREEN 1.134 
RED 1.057 
NEAR IR 1.192 
IR 1 1.172 
IR 2 1.055 
  
  
  
  
Figure 3: Predictiveness scores for the 
attributes in the 155-instance training set. 
  
N 
Typ(e,C) = 1/N* X Sim(e,b;) where beC and b,<>e 
i 
where e is the exemplar whose typicality score 
is being computed. The exemplar that gives a 
best score for the Typ function is known as the 
class prototype (Smith, 1981). The family 
resemblance statistic represents a global 
heuristic measure of classification goodness. 
Since similarity values closer to zero 
represent exemplars with greater similarity, an 
evaluation function that minimizes family 
resemblance scores would seem appropriate. 
Based on this idea, we define the evaluation 
rule used by SX-WEB: 
Given root node N, a list L of N's 
children representing the concept 
classes to be considered for instance 
classification, and a new instance I 
to be classified; 
Classify instance I with the concept 
class in L that results in the 
largest decrease in the average of 
the family resemblance scores of the 
children in L. 
In other words, compute the average family 
resemblance score of all of N's children. Then 
take the first child C, in L and compute the 
new family resemblance score as a result of 
instance I being added to this child. 
Now compute the new average family resemblance 
score resulting from this change to C, 
Subtract the new average family resemblance 
score from the old average. This is then the 
score for placing instance I into child C,. 
This computation is made for each child in L. 
Mathematically, since all that changes is the 
family resemblance score of the child now 
containing I and since the number of concept- 
level nodes remains constant, the actual 
computation is simply: 
FR(C) - FR(C+I) 
where C is the class in which I is being tested 
for incorporation and FR(C+I) is the family 
resemblance score of class C when I is 
included. 
2.4 Complexity analysis 
A cost analysis of SX-WEB's performance can be 
made for both the training and the clas- 
sification component of the learning process. 
During the training phase, SX-WEB builds its 
tree by creating links between the root-level, 
the concept-level and the instance-level nodes. 
The root-level and concept-level nodes store 
sums and sums of squares rather than actual 
mean and standard deviation values to 
accommodate the possibility of an incremental 
learning environment. 
After all of the training instances have been 
seen, the family resemblance score of the root- 
level and each concept-level node is computed. 
In a hierarchy containing R instance-level 
nodes, the family resemblance score of the 
root-level node can be computed by making R*(R- 
1)/2 similarity comparisons. If the R nodes are 
653 
evenly distributed among M  concept-level 
classes, then each concept-level class will 
contain approximately R/M  instance-level 
children. This being the case, to find the 
family resemblance score for one concept-level 
class will require R/M*(R/M-1)/2 similarity 
computations. Therefore, to find the family 
resemblance scores for all M concept-level 
classes will require R*(R-M)/(2*M) similarity 
calculations. 
The classification component cost analysis 
requires examining the total number of 
similarity computations necessary to classify 
a newly presented instance. To make instance 
classification as efficient as possible, each 
concept-level node stores a summation of 
instance similarity values rather than actual 
family resemblance scores. In this way, a new 
instance I being considered for classification 
into class C need only have its typicality 
score with the children of C computed. The 
typicality score for placing instance I into 
class C containing N children can be computed 
by making exactly N similarity computations. 
This typicality score can then be added to the 
present family resemblance summation value. 
From here the actual family resemblance score 
is computed by dividing the family resemblance 
summation by N*(N-*1)/2. Therefore, to classify 
P instances using a concept hierarchy 
containing R instance-level nodes requires 
exactly P*R similarity computations. 
When learning is incremental, each newly 
classified instance becomes an instance-level 
node within the concept hierarchy. In addition, 
the root-level node and the chosen concept- 
level node will have their statistics updated 
to reflect the incorporation of this new 
instance. An incremental learning environment 
is an advantage when concept class definitions 
need to be modified in order to reflect a 
changing learning environment. 
When SX-WEB is used as an incremental learning 
system, classification efficiency changes 
significantly. This is true because each 
instance that becomes part of the learning 
hierarchy has the effect of modifying the 
standard deviation values of the attributes 
found within the chosen concept class. This 
results in the similarity values of all 
instances within the chosen class to be 
affected. Because of this, the incorporation of 
each new instance requires the family 
resemblance score for the chosen concept-level 
class to be recomputed. Specifically, in a 
hierarchy containing R instances and M concept- 
level classes where each class contains 
approximately R/M children, to determine which 
concept class will contain a newly presented 
instance I requires R similarity computations. 
Then, to update the family resemblance score 
for the chosen concept-level class requires 
approximately = {R/M*[(R/M)+1]}/2 similarity 
computations. 
3. EXPERIMENTAL RESULTS 
This section gives the results obtained in 
testing SX-WEB using the derived Landsat TM 
data set previously described. The first three 
experiments test SX-WEB using all six spectral 
values. The remaining six experiments used 
predictiveness to test SX-WEB's classification 
accuracy when those spectral values least 
predictive of class membership were omitted 
from the classification process. 
3.1 Classification utilizing all six spectral 
values 
For the first experiment we used 155 of the 302 
instances for the training phase. This resulted 
in a hierarchy containing fifteen concept-level 
nodes with each node representing one of the 
fifteen land cover categories. Individual