A monotonic on-line linear algorithm for hierarchical agglomerative classification

A.B. Dragut, C.M. Nichitiu

Research output: Contribution to journalArticleAcademicpeer-review

1 Downloads (Pure)


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(nk) 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.
Original languageEnglish
Pages (from-to)111-141
JournalInformation Technology and Management
Issue number1-2
Publication statusPublished - 2004


Dive into the research topics of 'A monotonic on-line linear algorithm for hierarchical agglomerative classification'. Together they form a unique fingerprint.

Cite this