Здравствуйте. 
Есть набор размеченный данных (не очень большой размерности) (матрица лейблов 1 и 0) и есть предположение что в наборе данных есть несколько типов закономерностей. Точность классификации на тестовом наборе данных 85%, для решающей функции совсем грустно (65%). Хотелось построить такой классификатор который бы выдавал набор псевдоклассов: 0 остается а класс 1 разбивается на подклассы и нужно найти несколько очень хороших псевдоклассов а остальные выкинуть. Т.е. суть повышение качества за счет потери обучающих данных, которые можно считатать шумом. 
СТратегии решений
1. Класстеризовать и внутри каждого класстера классифицировать 
2. Класстеризовать и  класстеры с большим количеством лейблов 1 объявить разными классами.

Но что-то это слишком влоб и особо не работает. 

И не будет.

Используйте деревья решений (Деревья классификации, дендрограммы)
Они могут оказаться полезными или как само решение, или как указание где искать кластеры.