With the explosion of newly found proteins, it is necessary and urgent to develop automated computational methods for protein sub cellular location prediction. In particular, the problem of predictor construction for multi-location proteins is challenging. Considering the main limitations of the existing methods, we propose a hierarchical multi-label learning model FHML for both single-location proteins and multi-location proteins. In this model, feature space is firstly decomposed onto a set of nonnegative bases under the nonnegative data factorization framework. The nonnegative bases act as latent feature concepts and the corresponding coefficients on these bases are views as the new feature representation on the latent feature concepts. The similar decomposition is later performed in label space, and then the latent label concepts are extracted. Using these latent concepts as hyper edges, we construct dual fuzzy hyper graphs to exploit the intrinsic high-order relations embedded in both feature space and label space. Finally, the sub cellular location annotation information is propagated from the labeled proteins to the unlabeled proteins by performing dual fuzzy hyper graph Laplacian regularization. In this work, our proposed method is evaluated on eukaryotic protein benchmark dataset, and the experimental results have shown its effectiveness.