Learning to recognition without overfitting
Background: The problem of dealing with overfitting of recognition algorithms is one of the central problems in data mining. The algorithm that selects the most informative objects and features and generates a~signal at the point in which overfitting starts is described. At this signal, the learning process stops. Methods: To calculate the similarity between objects, the ternary relative measure called the function of rival similarity (FRiS) is used. Selecting informative features is made by the algorithm FRiS-Grad. Learning includes the consistent increase of number of reference objects ("stolps'') and the formation of clusters of objects closed to stolps in a fixed feature space. On each step of augmentation of number of stolps, the estimation of quality of the description of sample (or divisibility of classes) is calculated. Results: The hypothesis that the inflection point of the curve describing the separability of classes may signal about the beginning of overfitting is formulated and confirmed. On this basis, the algorithm FRiS-C-GRAD of learning without overfitting is developed. A method of decision-making that takes into account the weight of clusters is proposed. The results of testing of the algorithm on simulated problems are described. Concluding Remarks: Using FRiS-function has been useful in constructing decision rules, automatic classification (taxonomy), and selecting informative features and in obtaining quantitative estimation of compactness. In this paper, the utility of using this measure of similarity for addressing the protection of overfitting is illustrated.