Electronic document classification using composite hyperspace distances

• US 8,051,139 B1
• Filed: 04/27/2011
• Issued: 11/01/2011
• Est. Priority Date: 09/28/2006
• Status: Active Grant

• Current Assignee: Bitdefender IPR Management Limited (Bitdefender LLC)
• Original Assignee: Bitdefender IPR Management Limited (Bitdefender LLC)
• Inventors: Musat, Claudiu C. N.
• Primary Examiner(s): Follansbee; John
• Assistant Examiner(s): Mejia; Anthony
• Application Number:
  US13/095,350
• Time in Patent Office: 188 Days
• Field of Search: 709/206
• US Class Current: 709/206
• CPC Class Codes: G06Q 10/107 Computer-aided management of electronic mailing [e-mailing]

Abstract

In some embodiments, a layout-based electronic communication classification (e.g. spam filtering) method includes generating a layout vector characterizing a layout of a message, assigning the message to a selected cluster according to a hyperspace distance between the layout vector and a central vector of the selected cluster, and classifying the message (e.g. labeling as spam or non-spam) according to the selected cluster. The layout vector is a message representation characterizing a set of relative positions of metaword substructures of the message, as well as metaword substructure counts. Examples of metaword substructures include MIME parts and text lines. For example, a layout vector may have a first component having scalar axes defined by numerical layout feature counts (e.g. numbers of lines, blank lines, links, email addresses), and a second vector component including a line-structure list and a formatting part (e.g. MIME part) list.

Claims

1. A non-transitory computer-readable medium encoding instructions which, when executed by a computer system, cause the computer system to:

parse an electronic text document to generate a document vector for the electronic text document, wherein the document vector includes a feature count component and a feature position component, wherein the feature count component includes a plurality of feature count indicators for the electronic text document, wherein the feature position component includes a data structure selected from a group consisting of an ordered list and a tree of document substructure indicators, each document substructure indicator denoting a type of substructure in the electronic text document, and wherein a position of said each document substructure indicator in the data structure characterizes a position of a corresponding substructure in the electronic text document;

determine a plurality of composite hyperspace distances between the document vector and a plurality of reference vectors, each composite hyperspace distance being defined between the document vector and a reference vector of the plurality of reference vectors, wherein each composite hyperspace distance is a function of a Euclidean-space distance dependent on the feature count component of the document vector and of an edit distance dependent on the feature position component of the document vector; and

classify the electronic text document according to at least one of the plurality of composite hyperspace distances.

2. The computer-readable medium of claim 1, wherein the Euclidean-space distance is a Euclidean distance or a Manhattan distance.

3. The computer-readable medium of claim 1, wherein said each composite hyperspace distance is equal to a sum of the Euclidean-space distance and the edit distance.

4. The computer-readable medium of claim 1, wherein the plurality of feature count indicators comprises at least one indicator selected from a group consisting of a size of the electronic text document, a number of new lines, a number of blank lines, a number of links, and a number of email addresses in the electronic text document.

5. The computer-readable medium of claim 4, wherein each document substructure indicator in the data structure denotes a type of text line in the electronic text document.

6. The computer-readable medium of claim 1, wherein each reference vector represents a cluster of electronic text documents.

7. The computer-readable medium of claim 1, wherein the electronic text document is an electronic mail message.

8. The computer-readable medium of claim 7, wherein classifying the electronic text document comprises determining whether the electronic text document is spam or non-spam.

9. A method comprising employing a computer system to:

parse an electronic text document to generate a document vector for the electronic text document, wherein the document vector includes a feature count component and a feature position component, wherein the feature count component includes a plurality of feature count indicators for the electronic text document, wherein the feature position component includes a data structure selected from a group consisting of an ordered list and a tree of document substructure indicators, each document substructure indicator denoting a type of substructure in the electronic text document, and wherein a position of said each document substructure indicator in the data structure characterizes a position of a corresponding substructure in the electronic text document;

determine a plurality of composite hyperspace distances between the document vector and a plurality of reference vectors, each composite hyperspace distance being defined between the document vector and a reference vector of the plurality of reference vectors, wherein each composite hyperspace distance is a function of a Euclidean-space distance dependent on the feature count component of the document vector and of an edit distance dependent on the feature position component of the document vector; and

classify the electronic text document according to at least one of the plurality of composite hyperspace distances.

10. A non-transitory computer-readable medium encoding instructions which, when executed by a computer system, cause the computer system to:

generate an electronic communication feature count indicator comprising a plurality of feature counts for the electronic communication;

generate a text line structure indicator characterizing a line structure of the electronic communication, the text line structure indicator comprising a data structure selected from a group consisting of an ordered list and a tree of text line type indicators, a position of each text line type indicator in the data structure being indicative of a position of a corresponding text line type in the electronic communication;

determine a composite hyperspace distance between a vector representing the electronic communication and a predetermined vector, the hyperspace distance being a function of a Euclidean-space distance dependent on the feature count indicator, and of an edit distance dependent the text line structure indicator; and

classify the electronic communication according to the composite hyperspace distance.

11. A method comprising employing a computer system to:

generate an electronic communication feature count indicator comprising a plurality of feature counts for the electronic communication;

generate a text line structure indicator characterizing a line structure of the electronic communication, the text line structure indicator comprising a data structure selected from a group consisting of an ordered list and a tree of text line type indicators, a position of each text line type indicator in the data structure being indicative of a position of a corresponding text line type in the electronic communication;

determine a composite hyperspace distance between a vector representing the electronic communication and a predetermined vector, the hyperspace distance being a function of a Euclidean-space distance dependent on the feature count indicator, and of an edit distance dependent the text line structure indicator; and

classify the electronic communication according to the composite hyperspace distance.

12. The method of claim 11, wherein the Euclidean-space distance is a Euclidean distance or a Manhattan distance.

13. The method of claim 11, wherein the composite hyperspace distance is equal to a sum of the Euclidean-space distance and the edit distance.

14. The method of claim 11, wherein the feature count indicator comprises at least one indicator selected from a group consisting of a size of the electronic communication, a number of new lines, a number of blank lines, a number of links, and a number of email addresses in the electronic communication.

15. The method of claim 11, wherein each document substructure indicator in the data structure denotes a type of text line in the electronic text document.

16. The method of claim 11, wherein each reference vector represents a cluster of electronic text documents.

17. The method of claim 11, wherein the electronic text document is an electronic mail message.

18. The method of claim 11, wherein classifying the electronic communication comprises determining whether the electronic communication is spam or non-spam.