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.　©　2017　Elsevier　Ltd