Measures of classification complexity based on neighborhood model

Abstract: It is useful to measure classification complexity for understanding classification tasks, selecting feature subsets and learning algorithms. In this work, we review some current measures of classification complexity and propose two new coefficients: neighborhood dependency (ND) and neighborhood decision error (NDEM). ND reflects the ratio of boundary samples over the whole sample set; while NDEM is the decision error rate based on neighborhood local information of samples. We introduce neighborhood rough set model to define and compute decision boundary, furthermore compute NDEM. As one hopes to find the feature subspace where the classification task is with the least complexity, we construct a feature selection algorithm based on the proposed measures and sequentially forward selection. Experimental results show that NDEM correlates best with classification error rate from well-known classifiers compared to current measures and ND. Accordingly, NDEM can select the minimal feature subset with comparative classification performance. Key words: classification complexity; neighborhood; rough set; decision error; dependency; feature selection 1