A critical step in the process of reusing existing WSDLspecified components is the discovery of potentially relevant Web Services. Traditional category based Web Service retrieval usually can achieve good recall but worse precision because some semantically relevant Web Services are not actually relevant as they cannot provide suitable interfaces. In this paper, we present an interactive Web Services retrieval mechanism to refine the coarse retrieval results set in category based retrieval. In the refinement, the signature matching of Web Services that concerning the structure of operation specifications is investigated from a multi-instances view. In detail, each Web Service is represented as a bag in multiple instance learning, while each operation in this Web Service is regarded as an instance. This representation lies in that a user regards a service as useful if at least one operation provided by this Web Service is useful. Experimental results show that our approach can improve the retrieval performance significantly: It can gain 83% precision in average after two rounds of user relevance feedback.