Understanding structural transformation and phase transition accompanying reactions in a solid as a catalyst or oxygen carrier is important to the design and optimization of many catalytic or chemical looping reaction processes. Herein, we combined density functional theory calculation with the stochastic surface walking global optimization approach to track the structural transformation accompanying the reduction of CuO upon releasing oxygen. We then used machine learning (ML) methods to correlate the structural properties of CuOx with varying x. By decomposing a reduction step into oxygen detachment and structural reconstruction, we identified two types of pathways: (1) uniform reduction with minimal structural changes; (2) segregated reduction with significant reconstruction. The results of ML analysis showed that the most important feature is the radial distribution functions of Cu-O at a percentage of oxygen vacancy [C(OV)] < 50% and Cu-Cu at C(OV) > 50% for CuOx formation. These features reflect the underlying physicochemical origin, i.e., Cu-O breaking and Cu-Cu formation in the respective stage of reduction. Phase diagram analysis indicates that CuO will be reduced to Cu2O under a typical oxygen uncoupling condition. This work demonstrates the complexity of solid structural transformation and the potential of ML methods in studying solid state materials involved in many chemical processes.