Half-Heusler materials are strong candidates for thermoelectric applications due to their high weighted mobilities and power factors, which is known to be correlated to valley degeneracy in the electronic band structure. However, there are over 50 known semiconducting half-Heusler phases, and it is not clear how the chemical composition affects the electronic structure. While all the n-type electronic structures have their conduction band minimum at either the Γ- or X-point, there is more diversity in the p-type electronic structures, and the valence band maximum can be at either the Γ-, L-, or W-point. Here, we use high throughput computation and machine learning to compare the valence bands of known half-Heusler compounds and discover new chemical guidelines for promoting the highly degenerate W-point to the valence band maximum. We do this by constructing an "orbital phase diagram" to cluster the variety of electronic structures expressed by these phases into groups, based on the atomic orbitals that contribute most to their valence bands. Then, with the aid of machine learning, we develop new chemical rules that predict the location of the valence band maximum in each of the phases. These rules can be used to engineer band structures with band convergence and high valley degeneracy.