Evolution of topics in a messaging system
Systems and methods for determining how topics evolve in a messaging system extract at least one N-gram from data content (e.g., caption of messages) in the messaging system and detect anomalous behavior in N-gram frequencies over time. The anomalous behavior is used to select candidate N-grams for a determination of whether a topic of a candidate N-gram is evolving or fading. The candidate N-grams are clustered into cluster groups that are used to train at least one time series forecasting model to predict N-gram frequencies in a future time window. A time series of the N-gram frequency is divided into old and recent partitions and pattern recognition is applied to the predicted N-gram frequencies to identify an evolving or fading topic when the difference between a frequency of each anomaly and an average rolling median for each partition is greater for the most recent partition.
1 . A computer-implemented method of automatically detecting evolving topics in a messaging system comprising a messaging application server and at least one messaging client and controlling presentation of content to the at least one messaging client based on the evolving topics, comprising:
extracting, by at least one computer processor of the messaging application server, N-grams from data content in the messaging system;
detecting, by the at least one computer processor, anomalous behavior in N-gram frequencies over time and using the anomalous behavior to select candidate N-grams exhibiting anomalous behavior for a determination of whether topics of candidate N-grams are evolving or fading;
clustering, by the at least one computer processor, the candidate N-grams by merging candidate N-grams into a topic;
training, by the at least one computer processor, at least one time series forecasting model using the clustered candidate N-grains to predict N-gram frequencies of the clustered candidate N-grams in a future time window;
applying, by the at least one computer processor, pattern recognition to the predicted N-gram frequencies of the clustered candidate N-grams to automatically identify an evolving or fading pattern in the topic; and
at least one of providing, by the at least one computer processor, content relating to the topic to the at least one messaging client when the topic is identified as evolving, providing, by the at least one computer processor, advertising relating to the topic to the at least one messaging client when the topic is identified as fading, or adjusting, by the at least one computer processor, a ranking algorithm for the topic when the topic is identified as evolving or fading.
2 . The method of claim 1 , wherein the data content in the messaging system comprises captions of messages sent in the messaging system.
3 . The method of claim 1 , further comprising receiving, by the at least one computer processor, at least one query table including a plurality of N-grams from an input data source of the messaging system, the plurality of N-grams including the N-grams from data content in the messaging system.
4 . The method of claim 1 , further comprising cleaning, by the at least one computer processor, the extracted N-grams to remove any personally identifiable information (PII) and to focus on words and sentences relevant to one or more topics.
5 . The method of claim 1 , wherein detecting anomalous behavior in the N-gram frequencies over time and using the anomalous behavior to select candidate N-grams comprises using anomaly detection software executed by the at least one computer processor to identify a normal range within boundaries of an N-gram frequency over time, to detect abnormal behaviors in the N-gram frequency at a timestamp, and to select the candidate N-grams as anomaly N-gram data points that exceed the boundaries at different timestamps.
6 . The method of claim 5 , further comprising selecting, by the at least one computer processor, a candidate N-gram based on a sum of a difference between each N-gram frequency outside the boundaries of the N-gram frequency over time and an average of a rolling median of a frequency of the selected candidate N-gram over time.
7 . The method of claim 6 , further comprising dividing, by the at least one computer processor, N-gram data for the candidate N-grams into two groups and isolating anomalies using binary trees or by applying isolation forest methodology to the N-gram data.
8 . The method of claim 5 , wherein detecting anomalous behavior in the N-gram frequencies over time and using the anomalous behavior to select candidate N-grams comprises detecting, by the at least one computer processor, at least one changepoint in the N-gram frequencies over time as an anomaly.
9 . The method of claim 5 , wherein selecting the candidate N-grams comprises processing, by the at least one computer processor, anomaly N-gram data points by:
for each N-gram and upper or lower boundary of the N-gram frequency over time, dividing a time series of the N-gram frequency into old and recent partitions and obtaining a list of anomalies within the old and recent partitions;
for each anomaly N-gram data point, calculating a difference between a frequency of each anomaly (d) and an average rolling median (p) for each partition (p) as follows:
diff
(
p
)
=
∑
p
in
D
partition
abs
(
frequency
(
d
)
-
μ
rolling
median
)
where
p
is
a
partition
∈
{
old
,
recent
}
and
D
is
all
data
points
in
a
partition
;
and
selecting the candidate N-grams as evolving or fading topics when diff(recent partition)>diff (old partition).
10 . The method of claim 1 , wherein clustering the candidate N-grams comprises merging, by the at least one computer processor, groups of candidate N-grams into the topic by using a Pointwise Mutual Information (PMI) algorithm to calculate a co-occurrence of two candidate N-grams appearing together over time.
11 . The method of claim 10 , further comprising using, by the at least one computer processor, an N×N PMI matrix output by the PMI algorithm, where N is a number of candidate N-grams, as input to one or more clustering algorithms to cluster the candidate N-grams.
12 . The method of claim 11 , further comprising identifying, by the at least one computer processor, a best N-gram cluster configuration in terms of a number of clusters based on a silhouette score for each N-gram cluster configuration.
13 . The method of claim 1 , wherein training the at least one time series forecasting model using the clustered candidate N-grams to predict N-gram frequencies of the clustered candidate N-grams in the future time window comprises training, by the at least one computer processor, at least two time series forecasting models for different cluster groups of candidate N-grams and selecting a time series forecasting model that produces less error to predict the N-gram frequencies of the clustered candidate N-grams in the future time window.
14 . The method of claim 1 , wherein applying pattern recognition to the predicted N-gram frequencies of the clustered candidate N-grams to identify the evolving or fading pattern of the topic comprises using, by the at least one computer processor, recent data points and predicted data points for et a candidate N-gram to discover patterns for evolving or fading topics and calculating, by the at least one computer processor, a linear slope of the candidate N-gram to identify whether a topic of the candidate N-gram is evolving or fading, where a positive slope of the candidate N-gram indicates that the topic of the candidate N-gram is evolving and a negative slope of the candidate N-gram indicates that the topic of the candidate N-gram is fading.
15 . A messaging system that determines topics to present to users, comprising:
at least one messaging client,
a messaging application server one or more computer processors and
one or more computer-readable media storing instructions that, when executed by the one or more computer processors, cause the messaging application server to automatically detect evolving topics and to control presentation of content to the at least one messaging client based on the evolving topics by performing operations comprising:
extracting N-grams from data content shared between the at least one messaging client and the messaging application server;
detecting anomalous behavior in N-gram frequencies over time and using the anomalous behavior to select candidate N-grams exhibiting anomalous behavior for a determination of whether topics of candidate N-grams are evolving or fading;
clustering the candidate N-grams by merging candidate N-grams into a topic;
training at least one time series forecasting model using the clustered candidate N-grams to predict N-gram frequencies of the clustered candidate N-grams in a future time window;
applying pattern recognition to the predicted N-gram frequencies of the clustered candidate N-grams to automatically identify an evolving or fading pattern in the topic; and
at least one of providing content relating to the topic to the at least one messaging client when the topic is identified as evolving, providing advertising relating to the topic to the at least one messaging client when the topic is identified as fading, or adjusting a ranking algorithm for the topic when the topic is identified as evolving or fading.
16 . The messaging system of claim 15 , further comprising anomaly detection software executed by the one or more computer processors to identify a normal range within boundaries of an N-gram frequency over time, to detect abnormal behaviors in the N-gram frequency at a timestamp, and to select the candidate N-grams as the detected anomalies that exceed the boundaries at different timestamps, where each candidate N-gram is based on a sum of a difference between each N-gram frequency outside the boundaries of the N-gram frequency over time and an average of a rolling median of a frequency of the selected candidate N-gram over time.
17 . The messaging system of claim 15 , further comprising instructions that, when executed by the one or more computer processors, cause the messaging application server to detect at least one changepoint in the N-gram frequencies over time as an anomaly and to process anomaly N-gram data points by:
for each N-gram and upper or lower boundary of the N-gram frequency over time, dividing a time series of the N-gram frequency into old and recent partitions and obtaining a list of anomalies within the old and recent partitions;
for each anomaly N-gram data point, calculating a difference between a frequency of each anomaly (d) and an average rolling median (p) for each partition (p) as follows:
diff
(
p
)
=
∑
p
in
D
partition
abs
(
frequency
(
d
)
-
μ
rolling
median
)
where
p
is
a
partition
∈
{
old
,
recent
}
and
D
is
all
data
points
in
a
partition
;
and
selecting the candidate N-grams as evolving or fading topics when diff(recent partition)>diff (old partition).
18 . The messaging system of claim 15 , further comprising instructions that, when executed by the one or more computer processors, cause the messaging application server to:
merge groups of candidate N-grams into the topic by using a Pointwise Mutual Information (PMI) algorithm to calculate a co-occurrence of two candidate N-grams appearing together over time;
use an N×N PMI matrix output by the PMI algorithm, where N is a number of candidate N-grams, as input to one or more clustering algorithms to cluster the N-grams;
identify a best N-gram cluster configuration in terms of a number of clusters based on a silhouette score for the N-gram cluster configuration;
train at least two time series forecasting models for different cluster groups of N-grams and selecting a time series forecasting model that produces less error to predict the N-gram frequencies of the clustered candidate N-grams in the future time window; and
use recent data points and predicted data points for a candidate N-gram to discover patterns for evolving or fading topics and calculate a linear slope of the candidate N-gram to identify whether a topic of the candidate N-gram is evolving or fading, where a positive slope of the candidate N-gram indicates that the topic of the candidate N-gram is evolving and a negative slope of the candidate N-gram indicates that the topic of the candidate N-gram is fading.
19 . A non-transitory computer-readable storage medium including instructions that, when processed by one or more computer processors, cause the one or more computer processors to implement a method of automatically detecting evolving topics in a messaging system and controlling presentation of content to users of the messaging system based on the evolving topics by performing operations comprising:
extracting N-grams from data content in a messaging system;
detecting anomalous behavior in N-gram frequencies over time and using the anomalous behavior to select candidate N-grams exhibiting anomalous behavior for a determination of whether topics of candidate N-grams are evolving or fading;
clustering the candidate N-grams by merging candidate N-grams into a topic;
training at least one time series forecasting model using the clustered candidate N-grams to predict N-gram frequencies of the clustered candidate N-grams in a future time window;
applying pattern recognition to the predicted N-gram frequencies of the clustered candidate N-grams to automatically identify an evolving or fading pattern in the topic; and
at least one of providing content relating to the topic to the users of the messaging system when the topic is identified as evolving, providing advertising relating to the topic to the users of the messaging system when the topic is identified as fading, or adjusting a ranking algorithm for the topic when the topic is identified as evolving or fading pattern in the topic.