Information Technology Reference
In-Depth Information
classify the represented instances. However, IBL algorithms do little in
representation phase in that they do not store explicit generalizations, yet
there is more calculation on similarities among cases in the classification
phase when a new instance is encountered.
The performance of IBL algorithms are generally be assessed in terms of
the following respects:
(1) Generalization capability: the ability to determine which concepts can be
describable and the learning power of the algorithms. IBL algorithms can
PAC-learn any concept whose boundary is a union of a finite set of closed
hyper-curves of finite size.
(2) Classification accuracy.
(3) Learning rate.
(4) Incorporation costs: the overhead involved in updating the concept
descriptions of a training instance, including classification costs.
(5) Storage requirement: the size of the concept descriptions which for IBL
algorithms, is defined as the number of saved instances used for
classification decisions.
5.10.2
Algorithm IB1
The key idea of the IB1 algorithm is quite simple: Given an instance, it
assumes that the instance is in the same category as its nearest neighbor. Yet,
it is must be acknowledged that IB1 will fails in the cases that the given
attributes are logically inadequate for the description of the target concept.
Algorithm 5.1:
IB1 algorithm
1.
CD
∅
//CD=Concept description
2.
For each
x
∈
Training Set do
3.
for each
y
∈
CD do
4. sim[
y
]
similarity(
x,y
).
5.
y
max
some
y
∈
CD with maximal sim[
y
]
6.
if class(
x
)=class (
y
max)
7.
then classification
correct
8.
else classification
incorrect
9.
CD
CD
G
{
x
}
