A classical machine learning task seeks to induce a classifier to assign an example into one and only one class. In real-world domains, though, each example may at the same time belong to two or more classes, and there can be thousand of these classes, usually closely related to each other (e.g., hierarchically). Classifier induction then incurs high computational costs, and the results are often disappointing. Even the essential question of how to assess the performance of these classifiers has not been adequately answered. Addressing all of these issues, the talk will present new algorithms (based on k-NN and SVM), recommend adequate performance metrics, and illustrate their behaviors on experiments.