Cluster expansions are commonly employed as surrogate models to link the electronic structure of an alloy to its finite-temperature properties. Using cluster expansions to model materials with several alloying elements is challenging due to a rapid increase in the number of fitting parameters and training set size. We introduce the embedded cluster expansion (eCE) formalism that enables the parameterization of accurate on-lattice surrogate models for alloys containing several chemical species. The eCE model simultaneously learns a low dimensional embedding of site basis functions along with the weights of an energy model. A prototypical senary alloy comprised of elements in groups 5 and 6 of the periodic table is used to demonstrate that eCE models can accurately reproduce ordering energetics of complex alloys without a significant increase in model complexity. Further, eCE models can leverage similarities between chemical elements to efficiently extrapolate into compositional spaces that are not explicitly included in the training dataset. The eCE formalism presented in this study unlocks the possibility of employing cluster expansion models to study multicomponent alloys containing several alloying elements.