A Monotonic On-Line Linear Algorithm for Hierarchical Agglomerative Classification |
| |
Authors: | Andreea B. Dragut Codrin M. Nichitiu |
| |
Affiliation: | 1. Department of Operations Planning and Control, Faculty of Technological Management, Technical University of Eindhoven, Pav. F10, Den Dolech 2, P.O. Box 513, NL-5600 MB, Eindhoven, The Netherlands 2. EURISE, Faculté des Sciences et Techniques, Université Jean Monnet Saint étienne 23, rue du Dr. Paul Michelon, F-42034, St Etienne Cedex 2, France
|
| |
Abstract: | We start from an algorithm for on-line linear hierarchical classification for multidimensional data, using a centroid aggregation criterion. After evoking some real-life on-line settings where it can be used, we analyze it mathematically, in the framework of the Lance–Williams algorithms, proving that it does not have some useful properties: it is not monotonic, nor space-conserving. In order to use its on-line capabilities, we modify it and show that it becomes monotonic. While still not having the internal similarity-external dissimilarity property, the worst case classifications of the new algorithm are correctable with an additional small computational effort, on the overall taking O(n?k) time for n points and k classes. Experimental study confirm the theoretical improvements upon the initial algorithm. A theoretical and experimental comparison to other algorithms from the literature, shows that it is among the fastest and performs well. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|