Graphics Reference
In-Depth Information
8.4.1.2 Decremental
Reduced Nearest Neighbor (RNN) [ 76 ]—RNN starts with S = TR and removes
each instance from S if such a removal does not cause any other instances in TR
to be misclassified by the instances remaining in S . It will always generate a subset
of the results of CNN algorithm.
Shrink (Shrink) [ 89 ]—This algorithm starts with S = TR , and then removes any
instances that would still be classified correctly by the remaining subset. This is
similar to RNN, except that it only considers whether the removed instance would
be classified correctly, whereas RNN considers whether the classification of other
instances would be affected by the instance's removal.
Minimal Consistent Set (MCS) [ 36 ]—The purpose of this algorithm is to find a
Minimal consistent set of instances which will be able to classify all the training
instances in TR . It performs the following steps:
1. Define an initial consistent set to be the given training data set, since the given
set is by definition consistent with itself.
2. For a specific sample in the given training data set, determine the nearest sample
distance among all the samples from all classes other than its own in the consistent
set, i.e., identify and store the Nearest Unlike Neighbor (NUN) distance of the
sample from the consistent set.
3. For this same sample, identify all the neighboring samples from its own class in
the given data set which are closer than this NUN distance and cast an approval
vote to each of these samples in the given set by incrementing the correspond-
ing vote registers, while noting this voter's (sample) identity by updating the
corresponding voter lists.
4. Repeat Step 2 and 3 for all samples in the given training set, which results in a
list of the number of votes received by each sample in the given set along with
the records of the identity of its voters.
5. Create a potential candidate consistent set consisting of all samples in the given
set which are either (a) already present in the current consistent set or (b) whose
inclusion will not create an inconsistency; i.e., the sample should not be nearer to
any member of any other class other than that member's current NUN distance.
In the first iteration, the entire consistent set (i.e., the given set) remains as the
candidate consistent set as all samples satisfy condition (a)
6. Identify the most voted sample in this candidate consistent list and designate it
as a member of a newly selected consistent set and identify all of its contributing
voters.
7. Delete these voters from all the voter lists wherein they currently appear and
correspondingly decrement the appropriate vote counts.
8. Repeat Step 6 and Step 7 until all the voters have been accounted for by the
selected consistent set.
9. Now with this selected consistent set, the NUN distances of the input samples
are likely to be greater than before as some of the original NUN samples may
no longer be in the selected consistent set. Accordingly, repeat Step 2 using this
Search WWH ::




Custom Search