Recognition and manipulation of novel objects in human environments are a prerequisite for many tasks of robots. Since objects often occur in clutter, such robots should be capable of segmenting their environment into individual objects before attempting to learn the objects' properties. In this paper, we propose a probabilistic part-based approach to interactive segmentation of cluttered scenes containing multiple novel objects. Our experiments show that our probabilistic approach outperforms commonly employed heuristics. Furthermore, the probability distribution over segmentations enables principled selection of informative actions.