Kondensacja zbioru odniesienia metodą punktów wzajemnie najdalszych jako system sterowania pomiędzy szybkością i jakością klasyfikacji

Abstract

Many pattern recognition systems can have limited time for classification, mainly in applications concerned the quality control in industry. One of the simplest classifiers, known as a nearest neighbor rule, can be used for approximation of any other kind of classifiers, for instance the more sophisticated $k$ nearest neighbor classifier. The $k$ nearest neighbor classifier ($k$-NN) offers very good classification quality and converges to the theoretically best possible classification rule called the Bays classifier. The classification speed depends linearly on the reference set size, so classification can be accelerated by the decreasing the size of the reference set. The easiest way to control a compromise between the speed of classification and its quality consists in division of the training set into some subsets. The gravity centers of these subsets form a condensed reference set for the nearest neighbor rule. Division of the original reference set, i.e. the whole training set, starts with one set, then this set is divided into two subsets, next one of this two subsets is divided and so on, until each subset will contain only one object, that is a point in the feature space.

W wielu systemach przetwarzania danych (obrazów) na klasyfikację mamy określony limit czasu. W takim przypadku wskazana jest możliwość sterowania pomiędzy szybkością klasyfikacji a jej jakością. Jednym z prostszych podejść jest podział zbioru uczącego na podzbiory i dokonanie ich kondensacji (w tym wypadku metodą znajdowania punktów wzajemnie najdalszych). Autorzy proponują dekompozycję uczenia na kilka cyklicznie powtarzających się podzadań, które można przerwać w dowolnym momencie, uzyskując najlepszą w danej chwili klasyfikację. Przeprowadzone eksperymenty dowodzą, że wskutek zaproponowanej dekompozycji zyskujemy możliwość sterowania czasem i jakością dokonywanych klasyfikacji.