title: Linear time relational prototype based learning.
abstract: Prototype based learning offers an intuitive interface to inspect large quantities of electronic data in supervised or unsupervised settings. Recently, many techniques have been extended to data described by general dissimilarities rather than Euclidean vectors, so-called relational data settings. Unlike the Euclidean counterparts, the techniques have quadratic time complexity due to the underlying quadratic dissimilarity matrix. Thus, they are infeasible already for medium sized data sets. The contribution of this article is twofold: On the one hand we propose a novel supervised prototype based classification technique for dissimilarity data based on popular learning vector quantization (LVQ), on the other hand we transfer a linear time approximation technique, the Nyström approximation, to this algorithm and an unsupervised counterpart, the relational generative topographic mapping (GTM). This way, linear time and space methods result. We evaluate the techniques on three examples from the biomedical domain.
authors.affiliation: Department of Technology, University of Bielefeld, Universitätsstrasse 21-23, 33615 Bielefeld, Germany. agisbrec@techfak.uni-bielefeld.de
authors.forename: Andrej
authors.initials: A
authors.lastname: Gisbrecht
authors.forename: Bassam
authors.initials: B
authors.lastname: Mokbel
authors.forename: Frank-Michael
authors.initials: FM
authors.lastname: Schleif
authors.forename: Xibin
authors.initials: X
authors.lastname: Zhu
authors.forename: Barbara
authors.initials: B
authors.lastname: Hammer
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D002875:Chromosomes / Q000235:genetics; D016000:Cluster Analysis; D019295:Computational Biology; D003627:Data Interpretation, Statistical; D030541:Databases, Genetic; D006801:Humans; D016014:Linear Models; D015233:Models, Statistical; D016011:Normal Distribution; D012984:Software; D060388:Support Vector Machine; D013997:Time Factors; D014733:Vibrio / Q000235:genetics