Abstract: To address the issue of concept drift, on the basis of considering the dependency between labels, a novel ensemble classifier was introduced based on random labelsets for multi-label data streams. First, it divided the label set into several subsets based on RAkEL algorithm. Then a classifier on each subset was built using probabilistic classifier chain. Moreover, the adaptive windowing algorithm as a change detector was used to deal with concept drift. The experimental results on both synthetic and real-world data streams showed that our method achieves better performance than the previous methods, especially in datasets with concept drifts.