Method and computer program product for producing a record clustering with estimated clustering accuracy metrics with confidence intervals

1. A method of producing a record clustering with estimated accuracy metrics with confidence intervals, the method using:

(i) a collection of input records,

(ii) a model that is applied to a collection of records to produce a proposed cluster membership for each record in the collection,

(iii) a collection of record changes, wherein each record change is an add, update or delete and wherein updates and deletes reference records in the collection of input records,

(iv) a collection of test records, wherein each test record is a member of the collection of input records, and

(vi) a collection of verified records, wherein each verified record has a verified cluster membership and wherein each verified record is a member of the collection of input records,

the method comprising:

(a) incorporating, using software code in a processor, the record changes in the collection of record changes into:

(i) the collection of input records, thereby producing revised input records, and

(ii) the collection of verified records, thereby producing first revised verified records, and

(iii) the collection of test records, thereby producing first revised test records;

(b) creating, using the software code in the processor, a proposed cluster membership for each of the input records in the revised input records using the model, thereby producing proposed clusters;

(c) selecting a sample of the input records from the revised input records to add to the first revised test records, using the first revised verified records, thereby producing second revised test records;

(d) displaying to a user, on a user interface display, the following records:

(i) the test records in the second revised test records that are in need of verification,

(ii) the records in the proposed clusters whose proposed cluster membership is a related cluster, and

(iii) the records in the first revised verified records whose verified cluster membership is a related cluster;

(e) the user indicating, via the user interface display, for one or more of the records displayed in the user interface display, whether the records are members of a cluster;

(f) creating, based on the user indications in step (e), using the software code in the processor, second revised verified records and current clusters, the current clusters being the record clustering; and

(g) computing, using the software code in a processor, estimated accuracy metrics for the record clustering with confidence intervals from the second revised test records, using the proposed clusters, and the second revised verified records.

2. The method of claim 1 wherein the sample of the input records is selected by stratified sampling.

3. The method of claim 2 wherein the strata used in stratified sampling are defined by record creation time.

4. The method of claim 2 wherein a new stratum to be used in the stratified sampling is created when the number of records added since the most recent stratum end timestamp is over a threshold of the total record count before the most recent stratum end timestamp.

5. The method of claim 1 wherein the estimated clustering metrics are record-based precision and recall.

6. The method of claim 1 wherein the size of the sample of the input records is determined by a verification budget.

7. The method of claim 1 wherein test records in need of verification includes test records where the most frequent verified record cannot be determined.

8. A computer program product for producing a record clustering with estimated accuracy metrics with confidence intervals, the computer program product using:

(i) a collection of input records,

(ii) a model that is applied to a collection of records to produce a proposed cluster membership for each record in the collection,

(iii) a collection of record changes, wherein each record change is an add, update or delete and wherein updates and deletes reference records in the collection of input records,

(iv) a collection of test records, wherein each test record is a member of the collection of input records, and

(vi) a collection of verified records, wherein each verified record has a verified cluster membership and wherein each verified record is a member of the collection of input records,

the computer program product comprising a non-transitory computer-readable storage medium tangibly embodying non-transitory computer-executable program instructions thereon that, when executed, causes a computing device to:

(a) incorporate the record changes in the collection of record changes into:

(i) the collection of input records, thereby producing revised input records, and

(ii) the collection of verified records, thereby producing first revised verified records, and

(iii) the collection of test records, thereby producing first revised test records;

(b) create a proposed cluster membership for each of the input records in the revised input records using the model, thereby producing proposed clusters;

(c) selecting a sample of the input records from the revised input records to add to the first revised test records, using the first revised verified records, thereby producing second revised test records;

(d) display to a user, on a user interface display, the following records:

(i) the test records in the second revised test records that are in need of verification,

(ii) the records in the proposed clusters whose proposed cluster membership is a related cluster, and

(iii) the records in the first revised verified records whose verified cluster membership is a related cluster;

(e) receive user indications, via the user interface display, for one or more of the records displayed in the user interface display, regarding whether the records are members of a cluster;

(f) create, based on the user indications in step (e), second revised verified records and current clusters, the current clusters being the record clustering; and

(g) compute estimated accuracy metrics for the record clustering with confidence intervals from the second revised test records, using the proposed clusters, and the second revised verified records.

9. The computer program product of claim 8 wherein the sample of the input records is selected by stratified sampling.

10. The computer program product of claim 9 wherein the strata used in stratified sampling are defined by record creation time.

11. The computer program product of claim 9 wherein a new stratum to be used in the stratified sampling is created when the number of records added since the most recent stratum end timestamp is over a threshold of the total record count before the most recent stratum end timestamp.

12. The computer program product of claim 8 wherein the estimated clustering metrics are record-based precision and recall.

13. The computer program product of claim 8 wherein the size of the sample: of the input records is determined by a verification budget.

14. The computer program product of claim 8 wherein test records in need of verification includes test records where the most frequent verified record cannot be determined.