System, method and computer program product for classification of social streams

• US 9,165,328 B2
• Filed: 08/17/2012
• Issued: 10/20/2015
• Est. Priority Date: 08/17/2012
• Status: Active Grant

• Current Assignee: AirBNB Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Aggarwal, Charu C.
• Primary Examiner(s): Gaffin, Jeffrey A
• Assistant Examiner(s): Bharadwaj, Kalpana
• Application Number:
  US13/588,891
• Publication Number:
  US 20140052673A1
• Time in Patent Office: 1,159 Days
• Field of Search: 706/12
• US Class Current: 1/1
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06Q 50/01 Social networking

Abstract

A method of labeling an unlabeled message of a social stream. The method including training a training model based on labeled messages, partitioning the training model into a plurality of class partitions, each comprising statistical information and a class label, computing a confidence for each of the class partitions based on information of an unlabeled message and the statistical information of a respective class partition, as executed by a processor in a computer system, and labeling the unlabeled message of the social stream according to respective confidences of the class partitions.

Claims

1. A method of labeling an unlabeled message of a social stream, the method comprising:

training a training model of a social stream based on labeled messages, as executed by a processor on a computer;

partitioning the training model into a plurality of class partitions, each partition based on a social context of the social stream and each partition having a model comprising statistical information for at least one class label;

receiving an unlabeled message of the social stream;

computing a confidence for each of the class partitions based on information of the unlabeled message and the statistical information of respective class partitions; and

labeling the received unlabeled message of the social stream according to respective confidences of the class partitions.

2. The method according to claim 1, wherein the unlabeled message is labeled with a label of a class partition which has at least a certain confidence.

3. A method of social stream classification, the method comprising:

receiving a social stream including a plurality of message instances, the plurality of message instances including at least one of;

a test instance that is not classified; and

a training instance that is classified;

determining, for each message instance, linkage information of a sending node and a receiving node;

training a training model based on each training instance;

storing a plurality of statistical information including;

statistical information of words in the plurality of messages;

statistical information of the linkage information; and

statistical information of class partitions of the training model;

updating the plurality of statistical information over a period of time; and

classifying, as executed by a processor on a computer, each test instance based on the plurality of statistical information.

4. The method according to claim 3, further comprising partitioning the plurality of statistics based on the linkage information.

5. The method according to claim 3, wherein the class partitions each comprise local statistics,

wherein the plurality of statistical information comprises an aggregate of the local statistics of the class partitions, and

wherein the local statistics are stored separately from one another and are used for classifying the test instance.

6. The method according to claim 3, further comprising:

generating a plurality of class characteristic vectors including;

a class characteristic vector for each sending node; and

a class characteristic vector for each receiving node; and

partitioning the plurality of message instances based on the plurality of class characteristic vectors.

7. The method according to claim 6, wherein each class characteristic vector of the plurality of class characteristic vectors is generated based on a number of message instances belonging to each partition having been generated by each node.

8. The method according to claim 6, further comprising generating a class characteristic vector for a each message instance of the plurality of message instances,

wherein the class characteristic vector for each message instance is generated based on the class characteristic vector of each of its sending nodes and the class characteristic vector of each of its receiving nodes.

9. The method according to claim 3, further comprising assigning each message instance of the plurality of message instances to one or more partitions of the training model, based on the linkage information of each respective message instance.

10. The method according to claim 3, wherein if the training instance is received, then the plurality of statistical information of a relevant partition of the training model is updated based on information in the training instance.

11. The method according to claim 3, wherein if the test instance is received, then the test instance is assigned to a partition of the training model and classified based on statistical information stored in the partition where the test instance has been assigned.

12. The method according to claim 11, wherein the classifying of the test instance is further based on a frequency of an occurrence of words in the partition.

13. A method of social stream classification using a training model including plurality of class partitions, the method comprising:

receiving a social stream including a plurality of instances, the plurality of instances including at least one of;

a training instance that is classified; and

a test instance that is not classified;

determining, for each instance, linkage information and content information;

tracking relevance information, the relevance information including;

a number of times that words of the content information are relevant to one or more class partitions of the training model; and

a number of times that nodes, which are determined from the linkage information, belong to the relevant one or more class partitions of the training model;

updating statistical information of the training model based on the tracking; and

classifying, as executed by a processor in a computer system, each test instances based on the statistical information of the training model.

14. The method according to claim 13, wherein if a training instance is received, then the training model is incrementally updated, based on the classifying of that training instance.

15. The method according to claim 13, wherein if a test instance is received, then a confidence calculation of the test instance is performed for each class partition of the training model and the test instance is classified based on the confidence calculations.

16. The method according to claim 13, further comprising:

generating, for each instance, a plurality of vectors including;

a class characteristic vector for each sending node;

a class characteristic vector for each receiving node; and

a random vector; and

assigning the instance to a respective class partition based on the plurality of vectors.

17. The method according to claim 16, further comprising:

calculating an average of the class characteristic vector for each sending node and the class characteristic vector for each receiving node; and

assigning the instance to the respective class partition based on a dot product of the average and the random vector.

18. The method according to claim 16, wherein each class characteristic vector is generated based on a number of instances having been sent by each node and belonging to each of the class partitions.

19. The method according to claim 16, further comprising generating a class characteristic vector for each instance,

wherein the class characteristic vector for each instance is generated based on the class characteristic vector of each of its sending nodes and the class characteristic vector of each of its receiving nodes.

20. The method according to claim 13, further comprising:

generating a plurality of vectors including a random vector, based on the plurality of instances; and

partitioning the training model into 2·

r class partitions, where r is a number of random vectors of the plurality of vectors.

21. The method according to claim 20, further comprising tracking m different topics in the social stream, wherein the training model comprises 2·

r·

m local statistic models, which use the statistical information to classify the test instances.

22. The method according to claim 13, further comprising assigning each instance to one or more of the class partitions based on the linkage information having been determined for that instance.

23. The method according to claim 13, further comprising:

partitioning the training model into a plurality of class partitions;

computing an average confidence, for each class partition, across words in a test instance; and

classifying the test instance based on a class partition having a highest average confidence across the words in the test instance.

24. A computer program product for social stream classification, the computer program product comprising a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising:

computer readable program code configured to receive a social stream including a plurality of message instances, the plurality of message instances including one or more of;

a test instance that is not classified; and

a training instance that is classified;

computer readable program code configured to determine, for each message of the plurality of messages instances, linkage information of a sending node and a receiving node based on a respective message;

computer readable program code configured to train a training model based on the training instance;

computer readable program code configured to store a plurality of statistical information including;

statistical information of words in the plurality of messages;

statistical information of the linkage information; and

statistical information of a plurality of class labels of the training model;

computer readable program code configured to update the plurality of statistical information over a period of time; and

computer readable program code configured to classify the test instance based on the plurality of statistics.

25. The computer program product according to claim 24, wherein the computer readable program code further comprises:

computer readable program code configured to partition the training model into a plurality of class partitions; and

computer readable program code configured to compute an average confidence across words in a test instance, for each class partition, and

wherein the test instance is classified according to statistics of a class partition that has a highest average confidence of the class partitions.