Attribute-based Decision Graphs: A framework for multiclass data classification.
Graph-based algorithms have been successfully applied in machine learning and data mining tasks. A simple but, widely used, approach to build graphs from vector-based data is to consider each data instance as a vertex and connecting pairs of it using a similarity measure. Although this abstraction presents some advantages, such as arbitrary shape representation of the original data, it is still tied to some drawbacks, for example, it is dependent on the choice of a pre-defined distance metric and is biased by the local information among data instances. Aiming at exploring alternative ways to build graphs from data, this paper proposes an algorithm for constructing a new type of graph, called Attribute-based Decision Graph-AbDG. Given a vector-based data set, an AbDG is built by partitioning each data attribute range into disjoint intervals and representing each interval as a vertex. The edges are then established between vertices from different attributes according to a pre-defined pattern. Classification is performed through a matching process among the attribute values of the new instance and AbDG. Moreover, AbDG provides an inner mechanism to handle missing attribute values, which contributes for expanding its applicability. Results of classification tasks have shown that AbDG is a competitive approach when compared to well-known multiclass algorithms. The main contribution of the proposed framework is the combination of the advantages of attribute-based and graph-based techniques to perform robust pattern matching data classification, while permitting the analysis the input data considering only a subset of its attributes.
School of Technology, University of Campinas, R. Paschoal Marmo 1888, Jd. Nova Itália, Limeira, SP 13484-332, Brazil. Electronic address: bertini@ft.unicamp.br.
João Roberto
JR
Bertini
School of Technology, University of Campinas, R. Paschoal Marmo 1888, Jd. Nova Itália, Limeira, SP 13484-332, Brazil; FACCAMP, R. Guatemala 167, Campo Limpo Paulista, SP 13231-230, Brazil. Electronic address: carmo@dc.ufscar.br.
Maria do Carmo
MD
Nicoletti
Department of Computer Science and Mathematics, School of Philosophy, Science and Literature of Ribeirão Preto, University of São Paulo, Av. Bandeirantes 3900, Ribeirão Preto, SP 14040-901, Brazil. Electronic address: zhao@usp.br.
Liang
L
Zhao
D000465:Algorithms; D002965:Classification / Q000379:methods*; D057225:Data Mining / Q000379:methods*; D016208:Databases, Factual / Q000145:classification
Attribute-based Decision Graphs; Data-graph construction; Graph-based classification; Missing attribute values; Multiclass classification