Lately, multi-label classification (MLC) problems have drawn a lot of attention in a wide range of fields including medical, web, and entertainment. The scale and the diversity of MLC problems is much larger than single-label classification problems. Especially we have to face all possible combinations of labels. To solve MLC problems more efficiently, we focus on three kinds of locality hidden in a given MLC problem. In this paper, first we show how large degree of locality exists in nine datasets, then examine how closely they are related to labels, and last propose a method of reducing the problem size using one kind of locality.