Multi-modality classification for one-class classification in social networks

• US 8,386,574 B2
• Filed: 10/29/2009
• Issued: 02/26/2013
• Est. Priority Date: 10/29/2009
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Chidlovskii, Boris, Hovelynck, Matthijs
• Primary Examiner(s): BLAIR, DOUGLAS B
• Application Number:
  US12/608,143
• Publication Number:
  US 20110103682A1
• Time in Patent Office: 1,216 Days
• Field of Search: 709/206
• US Class Current: 709/206
• CPC Class Codes: G06F 18/2433 Single-class perspective, e.g. one-against-all classification; Novelty detection; Outlier detection
• CPC Class Codes: G06F 18/29 Graphical models, e.g. Bayesian networks
• CPC Class Codes: H04L 51/52 for supporting social networking services

Abstract

A classification apparatus, method, and computer program product for multi-modality classification are disclosed. For each of a plurality of modalities, the method includes extracting features from objects in a set of objects. The objects include electronic mail messages. A representation of each object for that modality is generated, based on its extracted features. At least one of the plurality of modalities is a social network modality in which social network features are extracted from a social network implicit in the set of electronic mail messages. A classifier system is trained based on class labels of a subset of the set of objects and on the representations generated for each of the modalities. With the trained classifier system, labels are predicted for unlabeled objects in the set of objects.

Claims

1. A classification method comprising:

receiving a set of objects, the objects comprising electronic mail messages, a subset of the objects having class labels;

extracting features associated with each of a first and a second modality, the second of the modalities being a social-network modality in which social network features are extracted from a social network implicit in the electronic mail messages, from objects in the set of objects and generating a representation of each object based on its extracted features;

training a classifier system based on the class labels of the subset of the set of objects and on the representations generated for each of the modalities; and

predicting labels for unlabeled objects in the set of objects using the trained classifier system.

2. The method of claim 1, wherein the classifier system is a one-class classifier system.

3. The method of claim 2, wherein the training of the classifier system comprises, for at least one of the first and second modalities, training a classifier, the training including, based on an initial set of positively labeled objects, generating an initial hypothesis which predicts negative labels for a subset of the unlabeled objects in the set and iteratively generating a new hypothesis in which a new boundary between representations of objects predicted as having negative labels and representations of objects predicted as having positive labels converges towards an original boundary between the representations of the initial positively labeled objects and the rest of the objects.

4. The method of claim 3, wherein the iteration is stopped prior to convergence between the new and original boundaries.

5. The method of claim 3, wherein for each modality, an iteration is selected which optimizes at least one performance criterion, and wherein predictions of the classifiers at those iterations are aggregated.

6. The method of claim 3, wherein at an iteration, the objects predicted as having negative labels and objects predicted as having positive labels are based on aggregated predictions from the classifiers.

7. The method of claim 1, wherein the extracting of social network features includes:

identifying a set of actors in the social network, based on the electronic messages;

assigning features to the actors in the social network, based on the electronic message traffic in the social network; and

propagating the actors'"'"' features to electronic messages between actors.

8. The method of claim 7, wherein the actors'"'"' features include features based on at least one of the amount of electronic message traffic between the actor and other actors, whether the actor serves as a hub in the network;

and the actor'"'"'s presence in one or more cliques.

9. The method of claim 7, wherein the assigning features to the actors in the social network includes computing a set of features from a graph of the social network in which actors are represented by nodes and connection lines between pairs of nodes represent electronic messages sent by a respective first actor to a respective second actor in the social network.

10. The method of claim 9, wherein the set of features include features selected from the group consisting of:

1) an activity score based on number of electronic messages sent by the actor;

2) a hub score for the actor based on a number of outgoing connection lines from the actor in the graph of the social network;

3) an authority score based on the number of incoming connection lines to the actor in the graph of the social network;

4) a mean centrality of the actor based on a total number of actors in the graph divided by the sum of all distances between the actor and each other actor in the graph;

5) a degree of centrality of the actor;

6) a neighborhood centrality of the actor based on a number of paths comprising at least two connected connection lines which pass through the actor;

7) a closeness centrality which is based on the inverse of a maximum distance between the actor and any other actor;

8) a stress centrality based on a sum of the number of number of paths comprising at least two connected connection lines which pass through the actor;

9) a clustering coefficient based feature which characterizes a ratio of the connectedness in the direct neighborhood of the node;

10) a number of cliques that an actor is in, each clique comprising at least a preselected number of actors;

11) a raw clique score based on a number of cliques the actor is in and the clique sizes; and

12) a weighted clique score based on a number of cliques the actor in and a measure of activity of all actors of each clique.

11. The method of claim 7, wherein the propagating includes generating a feature set for each electronic mail message based on feature sets of the sender and at least one recipient of the electronic mail message and optionally also a number of recipients.

12. The method of claim 7, wherein the identifying of the set of actors in the social network includes resolving references to senders and recipients in the electronic messages.

13. The method of claim 1, wherein the first of the modalities is a text-based modality.

14. The method of claim 13, wherein the extracted features comprise a bag-of-terms, each of the terms corresponding to a word or cluster of words present in the dataset.

15. A classification apparatus comprising:

memory which stores instructions for performing a method comprising;

for each of first and second modalities;

extracting features from objects in a set of objects, the objects comprising electronic mail messages, and

generating a representation of each object based on its extracted features;

the first of the modalities being a text-based modality, the second of the modalities being a social-network modality in which social network features are extracted from a social network implicit in the electronic mail messages;

training a classifier system based on class labels of a subset of the set of objects and on the representations generated for each of the modalities; and

with the trained classifier system, predicting labels for unlabeled objects in the set of objects; and

a processor, in communication with the memory for executing the instructions.

16. A non-transitory computer program product encoding instructions, which when executed by a computer, perform a method comprising:

receiving a set of objects, the objects comprising electronic mail messages, a subset of the objects having class labels;

extracting features associated with each of a first and a second modality, the second of the modalities being a social-network modality in which social network features are extracted from a social network implicit in the electronic mail messages, from objects in the set of objects and generating a representation of each object based on its extracted features;

training a classifier system based on the class labels of the subset of the set of objects and on the representations generated for each of the modalities; and

predicting labels for unlabeled objects in the set of objects using the trained classifier system.

17. A classification apparatus comprising:

an input for receiving a set of objects, the objects comprising electronic mail messages, a subset of the objects having class labels;

a first feature extractor which extracts text-based features from objects in the set of objects;

a second feature extractor which extracts social network-based features from the objects in the set of objects;

a classifier system, which predicts labels for unlabeled objects in the set of objects based on the class labels of the subset of objects having class labels and the extracted text-based and social network-based features; and

a processor which executes the classifier system.

18. A classification method comprising:

receiving a set of objects, the objects comprising electronic mail messages, an initial subset of the objects being positively labeled with respect to a class;

extracting features associated with each of a first and a second modality from objects in the set of objects and generating a representation of each object based on its extracted features;

training a one-class classifier system based on class labels of the subset of the set of objects and on the representations generated for each of the first and second modalities, the training including, for each of the modalities;

based on the initial set of objects that are positively labeled with respect to the class, generating an initial hypothesis which predicts negative labels for a subset of unlabeled objects in the set of objects, and

iteratively generating a new hypothesis in which a new boundary between representations of objects predicted as having negative labels and representations of objects predicted as having positive labels converges towards an original boundary between the representations of the initial positively labeled objects and the rest of the objects in the set; and

predicting labels for unlabeled objects in the set of objects using the trained classifier system.

19. The method of claim 18, wherein the iteration is stopped prior to convergence between the new and original boundaries.

20. The method of claim 19, wherein for each modality, an iteration is selected which optimizes at least one performance criterion, and wherein predictions for each of the modalities at those iterations are aggregated.

21. The method of claim 19, wherein at each of a plurality of iterations, the objects predicted as having negative labels and objects predicted as having positive labels are based on aggregated predictions of each of the first and second modalities.

22. The method of claim 18, wherein the first of the modalities is a text-based modality and the second of the modalities is a social network-based modality.