In this paper, we propose a novel data mining technique for the efficient damage detection within the large-scale complex mechanical structures. Every mechanical structure is defined by the set of finite elements that are called structure elements. Large-scale complex structures may have extremely large number of structure elements, and predicting the failure in every single element using the original set of natural frequencies as features is exceptionally time-consuming task. Traditional data mining techniques simply predict failure in each structure element individually using global prediction models that are built considering all data records. In order to reduce the time complexity of these models, we propose a localized clustering-regression based approach that consists of two phases: (1) building a local cluster around a data record of interest and (2) predicting an intensity of damage only in those structure elements that correspond to data records from the built cluster. For each test data record, we first build a cluster of data records from training data around it. Then, for each data record that belongs to discovered cluster, we identify corresponding structure elements and we build a localized regression model for each of these structure elements. These regression models for specific structure elements are constructed using only a specific set of relevant natural frequencies and merely those data records that correspond to the failure of that structure element. Experiments performed on the problem of damage prediction in a large electric transmission tower frame indicate that the proposed localized clustering-regression based approach is significantly more accurate and more computationally efficient than our previous hierarchical clustering approach, as well as global prediction models.