Nonnegative matrix factorization has been widely used in co-clustering tasks which group data points and features simultaneously. In recent years, several proposed co-clustering algorithms have shown their superiorities over traditional one-side clustering, especially in text clustering and gene expression. Due to the NP-completeness of the co-clustering problems, most existing methods relaxed the orthogonality constraint as nonnegativity, which often deteriorates performance and robustness as a result. In this paper, penalized nonnegative matrix tri-factorization is proposed for co-clustering problems, where three penalty terms are introduced to guarantee the near orthogonality of the clustering indicator matrices. An iterative updating algorithm is proposed and its convergence is proved. Furthermore, the high-order nonnegative matrix tri-factorization technique is provided for symmetric co-clustering tasks and a corresponding algorithm with proved convergence is also developed. Finally, extensive experiments in six real-world datasets demonstrate that the proposed algorithms outperform the compared state-of-the-art co-clustering methods. (C) 2017 Elsevier Ltd. All rights reserved.