In　evidential　clustering,　cluster-membership　uncertainty　is　represented　by　Dempster　Shafer　mass　functions.　The　EVCLUS　algorithm　is　an　evidential　clustering　procedure　for　dissimilarity　data,　based　on　the　assumption　that　similar　objects　should　be　assigned　mass　functions　with　low　degree　of　conflict.　CEVCLUS　is　a　version　of　EVCLUS　allowing　one　to　use　prior　information　on　cluster　membership,　in　the　form　of　pairwise　must-link　and　cannot-link　constraints.　The　original　CEVCLUS　algorithm　was　shown　to　have　very　good　performances,　but　it　was　quite　slow　and　limited　to　small　datasets.　In　this　paper,　we　introduce　a　much　faster　and　efficient　version　of　CEVCLUS,　called　k-CEVCLUS,　which　is　both　several　orders　of　magnitude　faster　than　EVCLUS　and　has　storage　and　computational　complexity　linear　in　the　number　of　objects,　making　it　applicable　to　large　datasets　(around　104　objects).　We　also　propose　a　new　constraint　expansion　strategy,　yielding　drastic　improvements　in　clustering　results　when　only　a　few　constraints　are　given.　(C)　2017　Elsevier　B.V.　All　rights　reserved.