K-Means　users　usually　have　to　decide　on　the　number　of　clusters　and　the　initial　state　by　themselves.　Evolutionary　K-Means　(EKM),　a　hybrid　algorithm　of　K-Means　and　genetic　algorithm,　solves　the　problem　by　choosing　the　two　parameters　automatically　through　partition　evolution;　however,　the　final　partition　obtained　often　doesn’t　meet　users’　expectations.　As　a　solution　to　this　problem,　we　suggest　using　background　knowledge　for　enhancing　clustering　quality　and　propose　a　semi-supervised　approach　that　incorporates　instance　level　constraints　into　the　objective　function　of　EKM.　Firstly,　we　define　Constrained　Silhouette　Index　(CS)　for　data　instances,　which　decreases　the　silhouette　index　of　the　instance　having　violated　constraints.　Then,　we　present　two　weighted　approaches　to　extend　the　influence　of　constraints　beyond　the　level　of　instance　for　evaluating　the　quality　of　a　cluster　or　a　partition.　To　evaluate　the　performance　of　CS　in　guiding　EKM　algorithms,　we　combine　the　two　types　of　CS　with　F-EAC　algorithm,　and　get　two　constrained　EKM　algorithms,　which　are　named　as　CEAC1　and　CEAC2,　respectively.　Experimental　results　on　two　artificial　datasets　and　eight　UCI　datasets　suggest　a　few　constraints　are　often　powerful　enough　to　improve　the　accuracy　of　labelling　instances　and　choosing　K,　and　more　constraints　may　improve　the　performance　even　more.　©　2014,　Springer-Verlag　Berlin　Heidelberg.