Simplifying lexicon creation in hybrid duplicate detection and inductive classifier systems

• US 8,713,014 B1
• Filed: 05/14/2010
• Issued: 04/29/2014
• Est. Priority Date: 02/11/2004
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Alspector, Joshua, Chowdhury, Abdur R., Kolcz, Aleksander
• Primary Examiner(s): Beausoliel, Jr., Robert
• Assistant Examiner(s): Khakhar, Nirav K
• Application Number:
  US12/780,500
• Time in Patent Office: 1,446 Days
• Field of Search: 707/736, 707/737, 707/739, 707/802, 707/803, 707/804
• US Class Current: 707/736
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation
• CPC Class Codes: H04L 51/212 using filtering or selective blocking

Abstract

A classification system includes a signature-based duplicate detector and an inductive classifier that share attribute information. To perform the duplicate detection and the classification, the duplicate detector and inductive classifier are first initialized by generating a lexicon of attributes for the duplicate detector and a classification model for the classifier. To develop a classification model, a training set of documents of known class are used by the classifier to determine the attributes of the documents that are most useful in classifying an unknown document. The model is developed from these attributes. Attribute information containing the attributes determined by the classifier is then passed to the duplicate detector and the duplicate detector uses the attribute information to generate the lexicon of attributes.

Claims

1. A method of classifying a document using a duplicate detector and an inductive classifier, the method comprising:

generating, at the duplicate detector, a lexicon of attributes based on attribute information received from the inductive classifier, wherein the duplicate detector is configured to determine whether two or more data items are near duplicates of each other;

receiving, at the duplicate detector, a set of documents of known classification;

calculating, at the duplicate detector, class signatures based on the set of documents of known classification and the lexicon of attributes;

receiving, at the duplicate detector, an unknown document;

generating, at the duplicate detector, a query signature based on the unknown document and the lexicon of attributes, the query signature being based at least in part on a correspondence between a unique attribute of the unknown document and the lexicon of attributes;

comparing, at the duplicate detector, the query signature to the class signatures to determine whether the query signature matches a class signature; and

determining, based on the query signature not matching a class signature, and using the inductive classifier, a classification from among a plurality of possible classifications for the unknown document, comprising;

determining a plurality of attributes that discriminate between the plurality of possible classifications;

comparing the determined plurality of attributes to the unknown document to generate a probabilistic classification for the unknown document;

determining that the probabilistic classification has probability exceeding a threshold; and

selecting the probabilistic classification.

2. The method of claim 1 further comprising applying, at the inductive classifier, a classification model to the unknown document to determine a classification for the unknown document.

3. The method of claim 1 wherein generating, at the duplicate detector, a lexicon of attributes based on the attribute information comprises selecting a specified number of the attributes with the highest mutual information scores.

4. The method of claim 1 further comprising generating, at the inductive classifier, attribute information based on a set of training documents of known classification.

5. The method of claim 4 wherein the attribute information comprises the attributes and mutual information scores.

6. The method of claim 5 wherein the attribute information comprises the portion of the attributes and the mutual information scores corresponding to the portion of the attributes.

7. The method of claim 4 wherein generating, at the inductive classifier, attribute information based on the set of training documents of known classification comprises:

receiving the training set of documents of known classification;

analyzing the set of training documents to determine attributes in the set of training documents; and

calculating mutual information scores for the attributes in the set of training documents.

8. The method of claim 4 wherein generating, at the inductive classifier, attribute information based on the set of training documents of known classification further comprises selecting a portion of the attributes based on mutual information scores.

9. The method of claim 4 wherein generating, at the inductive classifier, attribute information based on the set of training documents of known classification comprises:

selecting a specified number of the attributes with the highest mutual information scores; and

creating attribute clusters from the selected attributes.

10. The method of claim 9 wherein the attribute information comprises the attribute clusters.

11. The method of claim 1 wherein:

generating, at the duplicate detector, a lexicon of attributes based on the attribute information comprises;

generating a primary lexicon and a secondary lexicon based on the attribute information; and

generating, at the duplicate detector, a query signature based on the unknown document and the lexicon of attributes comprises;

determining unique attributes in the unknown document;

determining an intersection between the unique attributes in the unknown document and the primary lexicon;

determining whether the intersection exceeds a threshold;

when the intersection does not exceed the threshold, adding attributes from the secondary lexicon that intersect with the unique attributes in the unknown document to the intersection to create an augmented intersection that exceeds the threshold; and

calculating a signature for the document based on the augmented intersection.

12. The method of claim 11 wherein:

the attribute information comprises attributes in a set of training documents and mutual information scores for the attributes in the set of training documents, and

generating a primary lexicon and a secondary lexicon based on the attribute information comprises;

designating a specified number of the attributes in the set of training documents with the highest mutual information scores as the primary lexicon; and

designating at least a portion of the attributes other than the specified number of the attributes with the highest mutual information scores as the secondary lexicon.

13. The method of claim 1 wherein the set of documents of known classification comprises a set of spam e-mails such that receiving, at the duplicate detector, a set of documents of known classification comprises receiving, at the duplicate detector, a set of spam e-mails.

14. The method of claim 13 wherein calculating, at the duplicate detector, class signatures based on the set of documents of known classification and the lexicon of attributes comprises calculating spam signatures based on the spam e-mails and the lexicon of attributes.

15. The method of claim 14 further comprising indicating the unknown document is spam when the query signature matches a spam signature.

16. The method of claim 15 wherein calculating spam signatures based on the spam e-mails and the lexicon of attributes comprises:

selecting a spam e-mail from the set of spam e-mails;

determining unique attributes in the selected spam e-mail;

determining an intersection between the unique attributes in the selected spam e-mail and the lexicon; and

calculating a spam signature based on the intersection.

17. The method of claim 16 wherein the unknown document comprises an unknown e-mail such that receiving, at the duplicate detector, an unknown document comprises receiving, at the duplicate detector, an unknown e-mail.

18. The method of claim 1, wherein the class signatures are based at least in part on non-text attributes of the set of documents of known classification.

19. The method of claim 1, further comprising indicating the unknown document has a class of the document corresponding to the class signature that matches the query signature.

20. A computer-usable storage medium storing a computer program for classifying a document, the computer program comprising instructions for causing a computer to perform the following operations:

generate a lexicon of attributes based on attribute information, wherein the duplicate detector is configured to determine whether two or more data items are near duplicates of each other;

receive a set of documents of known classification;

calculate class signatures based on the set of documents of known classification and the lexicon of attributes;

receive an unknown document;

generate a query signature based on the unknown document and the lexicon of attributes, the query signature being based at least in part on a correspondence between a unique attribute of the unknown document and the lexicon of attributes;

compare the query signature to the class signatures to determine whether the query signature matches a class signature; and

determine, based on the query signature not matching a class signature, and using the inductive classifier, a classification from among a plurality of possible classifications for the unknown document, wherein the determination is performed using instructions for causing the computer to perform the following operations;

determine a plurality of attributes that discriminate between the plurality of possible classifications;

compare the determined plurality of attributes to the unknown document to generate a probabilistic classification for the unknown document;

determine that the probabilistic classification has probability exceeding a threshold; and

select the probabilistic classification.

21. The computer-usable storage medium 20, further comprising instructions for indicating the unknown document has a class of the document corresponding to the class signature that matches the query signature.

22. An apparatus for classifying a document, the apparatus comprising:

one or more processing devices and a computer-readable medium coupled to the one or more processing devices, the medium storing instructions which, when executed by the one or more processing devices, cause the one or more computers to perform operations comprising;

generating, at the duplicate detector, a lexicon of attributes based on attribute information received from the inductive classifier, wherein the duplicate detector is configured to determine whether two or more data items are near duplicates of each other;

receiving, at the duplicate detector, a set of documents of known classification;

calculating, at the duplicate detector, class signatures based on the set of documents of known classification and the lexicon of attributes;

receiving, at the duplicate detector, an unknown document;

generating, at the duplicate detector, a query signature based on the unknown document and the lexicon of attributes, the query signature being based at least in part on a correspondence between a unique attribute of the unknown document and the lexicon of attributes;

comparing, at the duplicate detector, the query signature to the class signatures to determine whether the query signature matches a class signature; and

determining, based on the query signature not matching a class signature, and using the inductive classifier, a classification from among a plurality of possible classifications for the unknown document, comprising;

determining a plurality of attributes that discriminate between the plurality of possible classifications;

comparing the determined plurality of attributes to the unknown document to generate a probabilistic classification for the unknown document;

determining that the probabilistic classification has probability exceeding a threshold; and

selecting the probabilistic classification.

23. The apparatus of claim 22, further comprising instructions which, when executed by the one or more processing devices, cause the one or more computers to indicate the unknown document has a class of the document corresponding to the class signature that matches the query signature.