Non-negative Matrix Tri-Factorization Based on Anchor Graph for Clustering

The graph-based clustering approach is a classical method, which transforms the clustering problem to graph cut. The graph-based approach has two key steps:(1) construction of graph; (2) proposing of graph. For lager-scale data set with data size <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex>, the approach needs to construct and propose <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n^{2}$</tex> matrices, which is inefficient and ineffective. To this end, an important technique is find anchor bipartite graphs instead of graphs. In this paper, we propose a non-negative matrix tri-factorization based on anchor graph, where the first layer matrix factorization is employed to search anchors, and the second layer factorization is used to generate the data representations. At the same time, an adaptive graph construction technique is employed to construct bipartite graph, and the data representations are required to conform to the bipartite. Under this unified framework, we can simultaneously learn appropriate anchors, bipartite graph and data representations. We use an alternate iteration algorithm to solve this optimization. The effectiveness of the algorithm is verified by experiments on six benchmark datasets.