To ensure the structural integrity of large aerospace structures during operation, structural health monitoring is a major challenge. The monitoring can be performed by distributed strain measurements using strain gauges or fiber optical sensors. In this work, an advanced local residual classifier for strain-based damage detection and localization is introduced. The key principle is that a change in the relationship between a strain sensor and its neighbors indicates the presence of damage. After defining a sensor grid with sensor locations and their orientation, the relationship can be obtained from numerical simulations of the healthy structure. Here, local regression models are estimated between each master sensor and its neighboring sensors. Then, residuals of the predicted and measured strains are evaluated using a random forest classifier. The evaluation of the residuals has the advantage that the method is independent of the load level, as well as the fact that it is independent of certain environmental influences that are uniformly distributed over the entire structure. In addition to the numerical healthy strains, synthetically generated damage data are used for training the classifier. The synthetic data are obtained by statistical modifications of the healthy strains. This procedure avoids time-consuming and expensive damage simulations. The health monitoring approach is applied to a glass fiber reinforced polymer sandwich structure, imitating an aircraft spoiler, with a hole in the face layer considered as damage. The validation is performed by numerical finite element simulations as well as physical experiments under random loading conditions. The results demonstrate the high potential of the presented approach for strain-based structural health monitoring in composite sandwich structures.