The discovery of efficient and accurate descriptions for the macroscopic behavior of materials with complex microstructure is an outstanding challenge in mechanics of materials. A mechanistic, data-driven, two-scale approach is developed for predicting the behavior of general heterogeneous materials under irreversible processes such as inelastic deformation. The proposed approach includes two major innovations: (1) the use of a data compression algorithm, -means clustering, during the offline stage of the method to homogenize the local features of the material microstructure into a group of clusters; and (2) a new method called self-consistent clustering analysis used in the online stage that is valid for any local plasticity laws of each material phase without the need for additional calibration. A particularly important feature of the proposed approach is that the offline stage only uses the linear elastic properties of each material phase, making it efficient. This work is believed to open new avenues in parameter-free multi-scale modeling of complex materials, and perhaps in other fields that require homogenization of irreversible processes.