In this paper, we reformulate the Evidential C-Means (ECM) problem for clustering complex row-data. We propose a new algorithm, Soft-ECM, which coherently positions the centers of imprecise clusters based on a semi-metric. Our experiments show that Soft-ECM obtains results comparable to conventional fuzzy clustering approaches on data in a euclidean space, and we demonstrate its benefits when combining fuzzy clustering with semi-metrics on time series data or categorical relational data.