This paper proposes a new cloud classification method, named bag of micro-structures (BoMS), for whole-sky imagers. BoMS treats an all-sky image as a collection of micro-structures mapped from image patches, rather than a collection of pixels. BoMS identifies five different sky conditions: cirriform, cumuliform, stratiform, clear sky, and mixed cloudiness (often appearing in all-sky images but seldom addressed in the literature). The performance of BoMS overperforms those of traditional methods.