Patent ID: 7870136

Claim:
A method for clustering data using pairwise constraints, comprising: receiving a set of data for clustering, the set of data includes a plurality of data units; identifying soft pairwise constraints, wherein the soft pairwise constraints include, for each pair of data units in the set of data, a soft must-link constraint indicating that the respective pair of data units are in a same cluster and having a confidence level indicating a probability of the soft must-link constraint; and a soft cannot-link constraint indicating that the respective pair of data units are not in the same cluster and having a confidence level indicating a probability of the soft cannot-link constraint; and clustering the plurality of data units in the set of data into a plurality of data partitions based at least on a chunklet modeling technique that employs the soft pairwise constraints, wherein the chunklet technique includes sampling the soft must-link and cannot-link constraints associated with each respective pair of data units in the set of data according to their associated confidence levels.