# Pattern Recognition

**Research team:**

- Adam Jóźwik, Ph.D.,
- Szymon Grabowski, Ph.D.,
- Łukasz Sturgulewski, Ph.D.,
- Artur Sierszeń, Ph.D.,
- Marcin Raniszewski, Ph.D.

**Distance-based pattern recognition methods**** (Adam Jóźwik, Ph.D.)**

**Main results:**

- a method for class areas determination and its use for construction of classifiers,
- reference set reduction method for the nearest neighbor rule based on searching for mutually nearest samples,
- condensation of the reference sample set for the nearest neighbor rule based on finding mutually farthest samples.

**Application:**

- electron spectroscopy (cooperation with the Institute of Physical Chemistry Polish Academy of Science in Warsaw),
- biomedical data analysis, concerned mainly animal respiratory system (cooperation with the Institute of Experimental and Clinical Medicine).

**Selected publications:**

- Sokołowska B., Jóźwik A., Pokorski M., „A fuzzy-classifier system to distinguish respiratory pattern envolving after diaphragm paralysis in cat”, Japanese Journal of Physiology, vol. 53, pp. 301-307, 2003,
- Lesiak B. and Jóźwik A.: „Quantitative analysis of AuPd alloys from the shape of XPS spectra by the fuzzy rule”, Surface and Interface Analysis, vol. 36, pp. 793-797, 2004,
- Lesiak B., Zemek J., Houdkova J., Jiricek P. and Jóźwik A.: „XPS ans XAES of polyethylenes aided by line shape analysis: the effect of electron irradiation”, Polymer Degragation and Stability 94, pp. 1714-1721, Elsevier, 2009.

**Ensembles of nearest-neighbor classifiers (Szymon Grabowski, Ph.D.)**

**Main results:**

- fast deterministic nearest neighbor search algorithm in Manhattan metric, practical with low dimensionality of the feature space,
- exploring k nearest centroid neighbors (N-NCN) decision rule variants, based on the surrounding neighborhood concept; k-NSN (k Near Surrounding Neighbors, original idea), approximate variants of the k-NSN and ensemble classifiers of similar type,
- multi-stage (cascade) classifiers (e.g. Telescope Ensembles of Reduced Sets, TERS) with attractive classification accuracy--speed tradeoffs,
- ensembles of classifiers, e.g. voting k-NN (a simple idea; accuracy higher than of k-NN for the price of small slow-down) and related ones,
- reference set reduction variants and (in the case of the Hart and the Tomek reduction algorithms) efficient reduced set generation algorithms, in theory (worst case time) or in practice.

**Application:**

- pathomorphological microscopic image analysis.

**Selected publications:**

- Grabowski Sz., Jóźwik A., Chen C.H., "Nearest neighbor decision rule for pixel classification in remote sensing", monograph section „Frontiers of Remote Sensing Info Processing”, ed. S. Patt, World Scientific Publishing Co. Pte. Ltd., Singapur, July 2003,
- Grabowski Sz., "Telescope ensembles of reduced sets", III Conference „Komputerowe Systemy Rozpoznawania” (KOSYR 2003), Miłków k/Karpacza, May 2003, pp. 391–398,
- Grabowski Sz., "Reducing the Computational Demands for Nearest Centroid Neighborhood Classifiers", Proceedings of the 7th International Conference on Artificial Intelligence and Soft Computing (ICAISC 2004), Zakopane, June 2004, Springer-Verlag LNCS 3070, pp. 568–573.

**Algorithms for investigation of strict linear separability of two sets (Łukasz Sturgulewski, Ph.D.)**

**Main results:**

- algorithms for investigation and determining the strict linear separability and corrected strict linear separability, based on the existing recursive algorithm for investigation of weak linear separability, for two-class sets.

**Selected publications:**

- Sierszeń A., Sturgulewski Ł., "Kondensacja zbioru odniesienia metodą punktów wzajemnie najdalszych jako system sterowania pomiędzy szybkością i jakością klasyfikacji", Automatyka, AGH, Kraków, Vol. 10, No. 3, pp. 447–454, 2006,
- Sturgulewski Ł., "Algorithms for investigation of strict linear separability of two sets", Elektryka, Zeszyty Naukowe Politechniki Łódzkiej, Vol. 115, No. 1024, pp. 139–146, 2008.

**Methods of the reference set condensation and reduction for decision rules based on distance function
(Artur Sierszeń, Ph.D.)**

**Main results:**

- the condensation of the reference set with the method of finding mutually farthest pair of points,
- modified Chang’s algorithm,
- cascades and bubble reference set condensation algorithms.

**Selected publications:**

- Sierszeń A., "Reduction of reference set with the method of cutting hyperplanes", Journal Of Medical Informatics & Technologies, ISSN: 1642-6037, vol. 13, pp. 215-220, 2009,
- Sierszeń A., "Reduction of large reference sets with modified Chang's algorithm", Automatyka, ISSN: 1429-3447, pp. 1009-1020, 2009,
- Sierszeń A., "Bubble algorithm for the reduction of reference set", Journal Of Medical Informatics & Technologies, ISSN: 1642-6037, vol. 16, pp. 117-124, 2010.

**Methods of strong reduction and edition of a reference set for the nearest neighbour rule**

(Marcin Raniszewski, Ph.D.)

(Marcin Raniszewski, Ph.D.)

**Main results:**

- reference set reduction, edition and condensation algorithms for the nearest neighbour rule based on the representativeness measure.

**Selected publications:**

- Raniszewski M., "The Edited Nearest Neighbor Rule Based on the Reduced Reference Set and the Consistency Criterion", Biocybernetics and Biomedical Engineering, Vol. 30(1), pp. 31-40, 2010,
- Raniszewski M., "Prototype Extraction of a Single-Class Area for the Condensed 1-NN Rule", Computer Recognition Systems 4, Advances in Intelligent and Soft Computing, Vol. 95, Springer Berlin/Heidelberg, pp. 119-125, 2011.

**Approximate and probabilistic methods of fast nearest neighbor searching (Aleksander Cisłak, M.Sc., Szymon Grabowski, Ph.D.)**

**Abstract:**

Spatial data structures, for vector or metric spaces, are a well-known means to speed-up proximity queries. One of the common uses of the found neighbors of the query object is in classification methods, e.g., the famous k-nearest neighbors algorithm. Still, most experimental works focus on providing attractive tradeoffs between neighbor search times and the neighborhood quality, but they ignore the impact of such tradeoffs on the classification accuracy.

In this paper, we explore a few simple approximate and probabilistic variants of two popular spatial data structures, the k-d tree and the ball tree, with k-NN results on real data sets. The main difference between these two structures is the location of input data — in all nodes (k-d tree) or in the leaves (ball tree) — and for this reason they act as good representatives of other spatial structures. We show that in several cases significant speedups compared to the use of such structures in the exact k-NN classification are possible, with a moderate penalty in accuracy. We conclude that the usage of the k-d tree is a more promising approach.

**Publication:**

- Cisłak A., Grabowski Sz., "Experimental evaluation of selected tree structures for exact and approximate k-nearest neighbor classification", FedCSIS 2014, pp. 93-100.

Editors:

Marcin Raniszewski

Łukasz Sturgulewski

Artur Sierszeń

Last modification:

2015-10-29 14:22:34,
Marcin Raniszewski