This paper proposes an improved optimization for the SECM evidential clustering algorithm. SECM benefits from the introduction of labelled objects to guide its output partition towards a desired solution. It also takes advantage of the belief functions theory to generate a credal partition that generalizes the concept of crisp and fuzzy partition. The counterpart of this gain of expressivity is the complexity which grows exponentially with the number of clusters. Thus, efficients methods should be used in order to optimize the objectif function. We propose in this article a heuristic that releases the classic constraint of positivity related to the mass functions coming from evidential methods. We show on several datasets the efficiency of our new optimization method in term of accuracy and speed.