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

• US 9,679,337 B2
• Filed: 08/27/2012
• Issued: 06/13/2017
• 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): Hill, Stanley K
• Assistant Examiner(s): Bharadwaj, Kalpana
• Application Number:
  US13/595,732
• Publication Number:
  US 20140052674A1
• Time in Patent Office: 1,751 Days
• 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 system that labels an unlabeled message of a social stream. The system including a memory device storing instructions to execute a training model, the training model being trained based on labeled messages, and partitioned into a plurality of class partitions, each of which comprise statistical information and a class label, and a Central Processing Unit (CPU) that computes a confidence for each of the class partitions based on information of an unlabeled message and the statistical information of a respective class partition, and that labels the unlabeled message according to respective confidences of the class partitions.

Claims

1. A system that labels an unlabeled message of a social stream, the system comprising:

a memory device storing instructions to execute a training model, the training model being trained based on labeled messages, and partitioned into a plurality of class partitions, each class partition based on a social context of the social stream based on one or more labels that reflect different topics being tracked for the social stream and each class partition having a model comprising statistical information for at least one class label, including statistical information of linkage information of a sending node and a receiving node;

the plurality of class partitions, maximized for classification accuracy with contextual partitions construed for different social contexts with different hash functions; and

a Central Processing Unit (CPU) that executes the training model, that receives unlabeled messages of social streams, that computes a confidence for each of the class partitions based on information of an unlabeled message and the statistical information of a respective class partition, and that labels the unlabeled message according to respective confidences of the class partitions.

2. The system according to claim 1, wherein if a certain confidence is computed for a class partition, then the CPU labels the unlabeled message with the label of the class partition having the certain confidence.

3. A system for social stream classification, the system comprising:

a terminal that receives 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;

a memory device storing instructions to execute a training model, the training model being trained based on the training instance, and storing a plurality of statistical information, which is updated over a period of time, the plurality of statistical information including;

statistical information of words in the plurality of message instances;

statistical information of linkage information of a sending node and a receiving node; and

statistical information of class partitions of the training model; and

a Central Processing Unit (CPU) that executes the training model, that receives unlabeled messages of social streams, that determines, for each message, linkage information of the sending node and the receiving node, and that classifies each test instance based on the training model, wherein the classification is maximized for classification accuracy with contextual partitions construed for different social contexts with different hash functions.

4. The system according to claim 3, wherein the plurality of statistics are partitioned into the class partitions based on information including the linkage information.

5. The system according to claim 3, wherein the class partitions each of which comprise local statistics that are stored separately from one another,

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

wherein the CPU classifies the test instance based on the local statistics.

6. The system according to claim 3, wherein the CPU partitions the plurality of message instances based on a plurality of class characteristic vectors including a class characteristic vector for each sending node and a class characteristic vector for each receiving node.

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

8. The system according to claim 6, wherein the CPU generates a class characteristic vector for each message instance of the plurality of message instances, 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 system according to claim 3, wherein the CPU assigns 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 system according to claim 3, wherein if a training instance is received, then the CPU updates the plurality of statistical information of a relevant partition of the training model based on information in the training instance.

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

12. The system according to claim 11, wherein the classifying performed by the CPU is further based on a frequency of an occurrence of words in the partition.

13. A system for social stream classification, which uses a training model including plurality of class partitions, the system comprising:

a terminal that receives a social stream including a plurality of instances, the plurality of instances including one or more of;

at least one training instance that is classified; and

at least one test instance that is not classified; and

a Central Processing Unit (CPU) that the at least one training instance to execute a training model, that receives each of the at least one test instance and determines, for each instance, linkage information of a sending node and a receiving node participating in the social stream and content information, that updates statistical information of the training model based on information that the CPU tracks, and that classifies each test instances based on the statistical information of the training model, wherein the classification is maximized for classification accuracy with contextual partitions construed for different social contexts with different hash functions.

14. The system according to claim 13, wherein if a training instance is received, then the training model is incrementally updated.

15. The system according to claim 13, wherein if a test instance is received, then the CPU performs a confidence calculation of the test instance for each class partition, and classifies the test instance based on the confidence calculations.

16. The system according to claim 13, wherein the CPU generates, for each instance, a plurality of vectors, and assigns the instance to a respective class partition based on the plurality of vectors, and

wherein the plurality of vectors include:

a class characteristic vector for each sending node;

a class characteristic vector for each receiving node; and

a random vector.

17. The system according to claim 16, wherein the CPU calculates an average of the class characteristic vector for each sending node and the class characteristic vector for each receiving node, and assigns the instance to the respective class partition based on a dot product of the average and the random vector.

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

19. The system according to claim 16, wherein the CPU generates a class characteristic vector for each instance, based on the class characteristic vector of each sending node of the instance and the class characteristic vector of each receiving node of the instance.

20. The system according to claim 13, wherein the CPU generates a plurality of vectors including a random vector, based on the plurality of instances, and partitions the training model into 2·

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

21. The system according to claim 20, wherein the CPU tracks m different topics in the social stream, and the training model further comprises 2·

r·

m local statistic models, each storing statistical information of the training model.

22. The system according to claim 13, wherein the CPU assigns each instance to one or more of the class partitions based on the linkage information having been determined for that instance.

23. The system according to claim 13, wherein the CPU computes an average confidence value, for each class partition of the training model, across words in a test instance, and classifies the test instance based on a class partition having a certain average confidence value.

24. A non-transitory, computer-readable storage medium that stores thereon a sequence of instructions to receive and classify a social stream that includes a plurality of message instances, the sequence of instructions comprising:

a module that, when executed by a processor in a computer system, determines, for each message instance, a relation of a sending node and a receiving node; and

a module that, when executed by the processor;

implements a model that is trained based on at least one message instance, each of which is classified;

stores statistical information about the plurality of message instances and the relation of the sending node and the receiving node participating in the social stream; and

classifies a message instance that is not classified, wherein the classification is maximized for classification accuracy with contextual partitions construed for different social contexts with different hash functions.

25. The non-transitory, computer-readable storage medium according to claim 24, wherein the model that is trained is partitioned into a plurality of partitions,

wherein the sequence of instructions further comprises a module that, when executed by the processor, computes an average confidence value across words in a message instance that is not classified, for each partition, and

wherein the model classifies the message instance that is not classified according to statistics of a partition that has a highest average confidence value of the class partitions, respectively.