An enhanced noise resilient K-associated graph classifier. Issue 21 (30th November 2015)

• Record Type: Journal Article
• Authors: Mohammadi, Mahdi; Raahemi, Bijan; Mehraban, Saeed Adel; Bigdeli, Elnaz; Akbari, Ahmad
• Is Part Of: Expert systems with applications. Volume 42:Issue 21(2015)
• Page Start: 8283
• Page End: 8293
• Publication Date: 2015-11-30
• Subjects: Graph-based classifier -- Noisy samples -- K-associated graph; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2015.06.044
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: We propose a non-parametric, noise resilient, graph-based classification algorithm. We employ relational data such as the degree of relevancy. We combine smaller components together to build larger ones. The algorithm is less noise sensitive than SVM and Decision Tree. The algorithm shows a superior performance in presence of different levels of noise. Abstract: In this paper, we propose a non-parametric, noise resilient, graph-based classification algorithm. By modifying the training phase of the k-associated optimal graph algorithm, and proposing a new labeling algorithm in the testing phase, we introduce a novel approach that is robust in the presence of different level of noise. In designing the proposed classification method, each class of dataset is represented by a set of sub-graphs (components), and a new extension of the k-associated optimal graph algorithm is introduced in the training phase to combine the smaller components. With this enhancement, we demonstrate that our algorithm distinguishes between noisy and non-noisy sub-graphs. Moreover, in the testing phase, we combine relational data, such as the degree of relevancy, with non-relational attributes, such as distance, for each sample in a graph to make the proposed algorithm less sensitive to noise. Gravity formula is the main concept behind the proposed test sample with various modifications to tailor it to the arbitrary shape and non-uniform sample scattering of the graph structure. We compare the proposed method with a graph-based classifier, as well as two other well-known classifiers, namely, Decision Tree and Multi-Class Support Vector Machine. Confirmed by the t -Test score, our proposed method shows a superior performance in the presence of different levels of noise on various datasets from the UCI repository. At a noise level of 5% or higher, the proposed algorithm performs, in average, 7% better than the graph-based classification algorithm. At a noise level of 20%, the proposed method performs, in average, 5% better than Decision Tree and multi-class SVM.