Consensus clustering is to find a high quality and robust partition that is in agreement with multiple existing base clusterings. However, its computational cost is often very expensive and the quality of the final clustering is easily affected by uncertain consensus relations between clusters. In order to solve these problems, we develop a new k -type algorithm, called k -relations-based consensus clustering with double entropy-norm regularizers (KRCC-DE). In this algorithm, we build an optimization model to learn a consensus-relation matrix between final and base clusters and employ double entropy-norm regularizers to control the distribution of these consensus relations, which can reduce the impact of the uncertain consensus relations. The proposed algorithm uses an iterative strategy with strict updating formulas to get the optimal solution. Since its computation complexity is linear with the number of objects, base clusters, or final clusters, it can take low computational costs to effectively solve the consensus clustering problem. In experimental analysis, we compared the proposed algorithm with other k -type-based and global-search consensus clustering algorithms on benchmark datasets. The experimental results illustrate that the proposed algorithm can balance the quality of the final clustering and its computational cost well.