Multi-principal element alloys are an emerging class of materials that are attractive candidates for structural, electronic, and electrochemical applications. An exhaustive investigation of chemical space in such complex alloys is impossible. Computational techniques, such as cluster expansion methods, have proven to be valuable tools in discerning structure-property-composition relationships in multi-component alloys. However, the cluster expansion method remains difficult to deploy in alloy systems containing several chemical components. In conventional cluster expansions, the number of features scales polynomially with the number of alloying elements. The rapid increase in the number of features causes difficulties in parameterizing and evaluating conventional cluster expansions. Machine-learning tools are necessary to reduce chemical dimensionality and enable the deployment of existing computational methods to multi-principal element alloys. Here, we introduce the embedded cluster expansion (eCE) formalism that mitigates this rapid growth in the number of features through dimensionality reduction and machine learning. Chemical similarities between elements are simultaneously learned during training to reduce the number of site-basis functions. We will then describe how eCE models can be deployed to build accurate thermodynamic models of refractory alloys containing more than 9 elements. We show that the eCE model can successfully reproduce the formation energies computed by electronic structure calculations, requires a limited amount of data, and can robustly extrapolate ordering energies. The results of this study provide a systematic framework to coarse-grain electronic structure calculations and derive insights into the finite-temperature behavior of materials.