The continuous growth of social networks and the active use of social media services result in massive amounts of user-generated data. Worldwide, more and more people report and distribute up-to-date information about almost any topic. At the same time, there is an increasing interest in information that can be gathered from this data. The popularity of new services and technologies that produce and consume data streams imposes new challenges on the analysis, namely, in terms of handling high volumes of noisy data in real-time. Since social media analysis is concerned with investigating current topics and actual events around the world, there is a pronounced need to detect topics in the data and to directly display their occurrence to analysts or other users. In this paper, we present an on-line clustering approach, which builds on traditional data mining methods to address the new requirements of data stream mining: (a) fast incremental processing of incoming stream objects, (b) compactness of data representation, and (c) efficient identi cation of changes in evolving clustering models.
The social network platform Twitter is a main producer of large volumes of data as a continuous stream. Over 140 million registered users and about 340 million short messages, called \tweets", per day make Twitter the undisputed market leader in social microblogging today. In its initial stages, Twitter was intended to be a service where people could update their status by posting short messages. Twitter prompted users to answer a simple question \What are you doing?" and thus the users reported their actual activities, feelings, and experiences of their everyday life. As Twitter gained signi cance and users started exchanging matters reaching beyond one's personal status, it was decided in November 2009 to change the question to a more general one \What's happening?"1. The intention of the new question is to engage users in reporting and publishing current news and events happening in the world. The consequence of this change is that Twitter has developed into a vast source of information that contains a mixture of all kinds of data.
Due to the diversity of the information provided, Twitter even plays an increasingly important role as a source for news agencies. In fact, news agencies use Twitter for two important functionalities in their daily activity. First, it is used as a publication and distribution platform for current news articles with a high throughput rate. For example, any reproduction of a tweet (\retweet") reaches an average of about 1,000 users [Kwa10]. Second, news agencies, such as BBC2, are constantly increasing the usage of Twitter as a reference in their daily news reports [Ton12].
A further characteristic of Twitter is its vibrant user community with a wide range of different personalities from all over the world. It has been shown that this whole spectrum can be sub-divided into a few categories of Twitter usage patterns, such as daily chatter, information and URL sharing, or news reporting [Jav07].
Further research undertaken has discovered that the majority of users publish messages focusing on their personal concerns and matters, whereas a smaller set of users publish for information sharing [Naa10]. This variety of content in the information ow leads to the primary task of detecting signi cant messages in the clutter of tweets. Because of the fast broadcasting manner of Twitter, important news spread rapidly through the social network. 2
Topic Detection Most traditional data mining methods such as Kmeans, DBSCAN, or OPTICS are not designed to be applied directly to data streams because of their in nite nature and the requirement for single pass evolutionary processing. In this paper we focus on a new stream mining method based on traditional data mining methods to address the new requirements of data stream mining: (a) fast incremental processing of incoming stream objects, (b) compactness of data representation, and (c) efficient identi cation of changes in evolving clustering models.
The proposed algorithmic idea relies on an extended concept of density-based clustering over an evolving data stream with noise (DenStream [Cao06]) with enhanced applicability for categorical data. We designed the on-line component of the extended DenStream algorithm to include the major ideas of the classical DenStream algorithm and added some new features and functionalities.
Similar to the ideas of the classical DenStream algorithm, a set of core and outlier micro-clusters is maintained incrementally with the role of outlier and core micro-clusters being often exchanged as a consequence of outdated micro-clusters fading into outliers and new micro-clusters being formed. To speed up processing, an outlier buffer is used to separate the processing of core micro-clusters and the outliers (micro-clusters attracting very few data objects for extensive time intervals). We also extended the general macro-clustering approach with a lightweight variant of the DBSCAN algorithm, which is applied on the micro-clusters as virtual points.
With a view toward achieving a both efficient and accurate estimate of the centroid of the clustering we propose a new approach that uses cluster feature vectors with sufficient summary statistics as components. We use POS tagging to extract a number of relevant features per cluster, the set of selected features consisting mainly of common and proper noun structures.In order to be able to detect new trends in a steadily evolving stream, an incoming data object is assigned to the nearest cluster based on the average of the closest similarity values to the cluster summaries attained by previous objects in the stream. Since the tweet objects can be very small in size, vector components consist of the inverse cluster frequency of a selected feature combined with the cluster frequency of that same feature. Effectively, the frequency of a selected feature in the cluster is offset by the frequency of that same feature across all documents in the cluster.We refer to these vectors as CF-ICF vectors.
The number of selected vector components to be monitored in a given cluster turns out to be exponential to the number of selected unique features, and therefore only a small subset which represents the frequent features needs to be kept. Infrequent features are removed from the vector representation by means of dimensionality reduction to speed up the processing. This also avoids excessive storage and, at the same time, simpli es and summarizes the incoming data, achieving a convergence effect that contributes to reaching a steady distribution of topics. Computation of similarity is done using the cosine similarity metric.
Micro-clusters are maintained incrementally. Effectively, the number of points and the linear sum of term frequencies of the micro-clusters are continuously updated.
We consider the problem of clustering a data stream in the damped window model, in which the weight of each stream object decreases exponentially with time t via an exponential fading function f (t) = 2 t, where is a constant called the decay factor and > 0. The fading function controls the importance of the historical data compared to the most recent data by taking into account the timestamp of the last update to the clustering. The higher the value of , the greater emphasis is placed on the more recent data.
The overall weight W of all stream objects is nearly constant, veri ed by applying a geometric series to it tn t!1 W = v ∑ t=0 ! 1 v 2 ; where v is the speed of the stream.
During the on-line part we distinguish between potential core-micro-clusters, if w and outlier micro-clusters, with w , where is the outlier threshold and the minimum overall weight for a core micro-cluster.
Effectively, for time interval t, if no points are merged into a micro-cluster the weight decreases M C = ( 2 tw; LS; tc); where LS is the linear sum of the term frequencies and tc is the creation timestamp of the micro-cluster.
If a data point p is merged the updated microcluster is de ned as
M C = ( w + 1; LS + 1; tc):
In order to be able to keep track of the evolution of interesting sub-topics as part of a major topic, we introduce the notion of sub-clusters that are incrementally maintained within core micro-clusters in a way similar to which micro-clusters are maintained. Specifically, incoming stream objects are reassigned to the closest sub-cluster by comparing them to vector representations of the sub-cluster summaries.
The sub-cluster summaries consist of the number of data points contained, the linear sums of a feature (LS), the linear sums of occurrences of a feature per window (LSW ) and the linear sums of co-occurrences per feature (LSC).
We distinguish between potential core-sub-clusters (p-sub-cluster ), if w and N min and outlier sub-clusters (o-sub-cluster ), if w , where N is the number of data objects in the sub-cluster, min the minimum number of objects required for a core subcluster, is the outlier threshold and the minimum overall weight for a core sub-cluster.
For time interval t, if no points are merged into a sub-cluster, the weight decreases
SC = ( 2
tw; LS; LSW; LSC; tc):
If a data point p is merged the updated sub-cluster is de ned as
SC = ( w + 1; LS + 1; LSW + 1; LSC + 1; tc): If an outlier micro-cluster has attracted sufficient data to be converted into a core micro-cluster, data objects that have been assigned to the latter are redistributed to underlying sub-clusters. This effectively means that an incoming stream object that has been assigned to a nearest micro-cluster is reassigned to its nearest sub-cluster, unless the closest similarity value is considerably lower than the values attained by previous stream objects. In order to be able to determine whether the closest similarity value is considerably below the one previously attained, the mean of the last three closest similarity values to the sub-cluster summaries is maintained. The similarity values are additively maintained, to increase efficiency. Algorithm 1 de nes the extended merging procedure, which is also visualized in Figure 3.
The potentially unbounded nature and uncertain arriving speed of data streams along with the requirement of single pass scanning imposes a limited space (memory) and a strict time constraint to the implementation of the data stream processing. Therefore, a checking strategy is performed every T p time steps, where T p is de ned as the minimal timespan for a cluster fading into an outlier. This ensures that outdated clusters that have either received few data or have had their weight reduced by the decay factor are pruned. Algorithm 1 Extended DenStream: Merging technique Require: ϵ1 0 1; ϵ2 0 1; 1 : Try to merge p into its nearest p-micro-cluster f g cp; if dp (the closest similarity value) < ϵ1 then Merge p into cp; 2 : Try to merge p into the nearest p-sub-cluster f g csp of p-micro-cluster cp; if dsp (the closest similarity value) < ϵ2 then
Merge p into csp; else f3g:Try to merge p into the nearest o-subcluster cso of p-micro-cluster cp; if dso (the closest similarity value) < ϵ2 then
Merge p into cso; else
Create a new o-sub-cluster containing p end if end if else f4g:Try to merge p into its nearest o-micro-cluster co; if do (the closest similarity value) < ϵ1 then Merge p into co; if w (the new weight of co) > then
Convert co into a p-micro-cluster and create a new o-sub-cluster with all stream objects of the converted o-micro-cluster; else
Create a new o-micro-cluster containing p end if end if end if Otherwise, they will take up a lot of memory space, and either the clustering result may contain outdated data with the immediate effect of lessening the evolving character of the data stream or clusters consisting of outliers will combine data that should not be in the same cluster into a same cluster in subsequently merging micro-clusters, thus decreasing clustering efciency.
The weight of outlier micro-clusters and outlier subclusters is compared against (t) = 2 (t tc+Tp) 1 2 1 ; where tc is the creation timestamp of the outlier microcluster and T p is the minimal timespan for a microcluster/sub-cluster fading into an outlier. Outlier subclusters that have been turned into core sub-clusters will have a lifespan at least as long as the core microcluster to which they belong.
The longer an outlier micro-cluster or outlier subcluster exists, the higher its expected weight lim tc!1 (tc) = 1
Based on this assumption, the cumulated maximal number of micro-clusters and sub-clusters in memory is W , where W is the overall weight of the data streams and acts as the ltering parameter. Therefore, the runtime complexity of the extended Denstream algorithm is O( W +x), where x is the length of the stream and W is the maximal cumulated number of core micro-clusters and core sub-clusters in memory. As a consequence of the pruning strategy and the dimensionality reduction, memory increases only logarithmically with stream length. The pruning technique used by our algorithm is shown in Figure 2, where N is the number of objects and min the minimum number of objects.
To handle the case where micro-clusters created independently might at some point during the clustering turn out to contain topics that are semantically related we implemented a modi ed lightweight variant of the DBSCAN algorithm that runs periodically (every N stream objects, with N typically set to 10,000) on the live set of micro-clusters as virtual points. The intuition behind this is based on the symmetric property of density-connectedness of the DBSCAN algorithm.
Apart from the immediate effect of semantic compaction of the topic distribution, the macro-clustering phase (see Figure 2) also effectively reduces the number of micro-clusters to be processed. While the core sub-clusters of the merged micro-clusters are added to the set of the existing core sub-clusters of the merging micro-cluster, the set of outlier sub-clusters effectively Figure 3: Extended DenStream: merging technique heaval in Ukraine, the Bitcoin exchange shutdowns due to alleged hacker theft, the clashes between rebels and the Syrian government forces in Syria and the Champions League results were most prominent in the topic distribution, containing more than 12,000 tweets. Since the major topics (mostly macro-clusters found by the DBSCAN algorithm) spanned over large time intervals yet contained a large diversity of sub-topics that were sufficiently different from each other, only the contained sub-topics were written to the result le to meet the interval requirement. For each sub-cluster, 15-minute intervals were output for which there was a signi cant difference in the n-gram signature between two successive windows of the respective sub-cluster (to avoid duplicates).
An example of a major topic with component subtopics are the events revolving around the Syrian conict in general, e.g., the major ambush involving rebels in Damascus, Germany monitoring jihadis in battlehardened Syria, the photos of the Yarmouk refugee camp in Syria, Syrian al Qaeda giving rival rebel group an ultimatum. This kind of approach might prove useful in helping journalists gain more insight into ongoing events and perhaps acquire a better understanding of the signi cance of more complex events by assessing their impact on a more global scale while at the same time allowing them to maintain the focus on the more detailed aspects of those events.
The official evaluation results of our method in the Data Challenge are included in Papadopoulos et al. [Pap14]. [Cao06]