Microgrids (MGs) are decentralized systems that integrate distributed energy resources and may operate in grid-connected or islanded modes. Furthermore, MGs may feature several topologies or operative scenarios. These characteristics bring about major challenges in determining a proper protection coordination scheme. A new optimal coordination approach for directional over-current relays (OCRs) in MGs is proposed. In this case, a clustering of operational models is carried out by means of a K-means algorithm hybridized with the principal component analysis (PCA) technique. The number of clusters is limited by the number of setting groups of commercially available relays. The results carried out on a benchmark IEC microgrid evidence the applicability and effectiveness of the proposed approach.