Dimitris Milioris
email: dimitrios.milioris@alcatel-lucent.com

Philippe Jacquet
email: philippe.jacquet@alcatel-lucent.com

TOPIC DETECTION AND COMPRESSED CLASSIFICATION IN TWITTER

Keywords: Big Data, Text Classification, Joint Complexity, Combinatorics, Compressive Sensing, Kalman Filter

In this paper we introduce a novel information propagation method in Twitter, while maintaining a low computational complexity. It exploits the power of Compressive Sensing in conjunction with a Kalman filter to update the states of a dynamical system. The proposed method first employs Joint Complexity, which is defined as the cardinality of a set of all distinct factors of a given string represented by suffix trees, to perform topic detection. Then based on the inherent spatial sparsity of the data, we apply the theory of Compressive Sensing to perform sparsity-based topic classification by recovering an indicator vector, while reducing significantly the amount of information from tweets, possessing limited power, storage, and processing capabilities, to a central server. We exploit datasets in various languages collected by using the Twitter streaming API and achieve better classification accuracy when compared with state-of-the-art methods.

INTRODUCTION

Social Networks have undergone a dramatic growth in recent years and have changed the way we communicate with others, entertain and actually live. The communication between users has formed a new era with several research challenges, e.g. (a) real time search has to balance between quality, authority, relevance and timeliness of the content, (b) the relationship analysis between members of a social community can reveal the important teams which can be used for specific plans, (c) spam and advertisement detection to avoid the growth of irrelevant content. By extracting the relevant information from social networks in real time, we can address these challenges.

In this paper we use the theory of Joint Complexity (JC) to perform topic detection. The evaluation of the proposed method is based on the detection of real world topics like the categories of a mainstream news portal. We use large datasets, which are tweets from politics, economics, sport, technology and lifestyle. Then we classify new tweets into these cate-Dimitris Milioris would like to thank the "Alliance Doctoral Mobility Grant". The work presented in this paper has been partially carried out at Columbia University, NY and at Bell Labs, Murray Hill, NJ, USA.

gories with the power of Compressive Sensing (CS) by taking advantage of the inherent sparsity of the data, combined with a Kalman filter, as a refinement step for the update of the user's estimated class. The method is simple, context-free, with no grammar and no language assumptions, and does not use semantics. The sequence of text is decomposed in linear time into a memory efficient structure called Suffix Tree [START_REF] Tata | Practical Suffix Tree Construction[END_REF] (frequently used in DNA sequence analysis) and by overlapping two trees, in linear or sublinear average time, we obtain the JC defined as the cardinality of factors (subsequences) that are common in both trees. The method has been extensively tested for Markov sources of any order for a finite alphabet and gave good approximation for text generation and language discrimination, while being language-agnostic. Therefore there is no need to build any specific dictionary or stemming process.

The paper is organised as follows: Section 2 introduces the JC method, while Section 3 describes the classification via CS. Section 4 discusses the Kalman filter, while Section 5 evaluates the performance with real data obtained from Twitter. Finally, Section 6 summarises our main results and provides directions for future work.

JOINT COMPLEXITY

Several attempts have been made to capture mathematically the concept of complexity of a sequence, i.e., the number of distinct factors contained in a sequence. If X is a sequence and I(X) its set of factors, then |I(X)| is the complexity of the sequence. For example if X = "sunny then I(X) = {s, u, n, y, su, un, nn, ny, sun, unn, nny, sunn, unny, sunny, v} and |I(X)| = 15 (v denotes the empty string). The complexity of a string is called the I-complexity, and is connected with deep mathematical properties, including the rather elusive concept of randomness in a string [START_REF] Li | Introduction to Kolmogorov Complexity and its Application[END_REF], [START_REF] Hellseth | Some computable complexity measures for binary sequences[END_REF].

In general, a reference string is required to measure the information contained in a second string. In [START_REF] Jacquet | Common words between two random strings[END_REF] the concept of JC of two strings was introduced as the number of common distinct factors of two sequences, i.e. the JC of sequence X and Y is equal to J(X, Y ) = |I(X) ∩ I(Y )|. Our previous experiments [START_REF] Jacquet | Classification of Markov Sources Through Joint String Complexity: Theory and Experiments[END_REF] showed that the mentioned complexity estimate for memoryless sources converges very slowly. Furthermore, memoryless sources are not appropriate for mod-elling text generation. In a prior work, we extend JC estimate to Markov sources of any order on a finite alphabet. Markov models are more realistic and have a better approximation for text generation than memoryless sources [START_REF] Jacquet | Classification of Markov Sources Through Joint String Complexity: Theory and Experiments[END_REF], [START_REF] Milioris | Joint Sequence Complexity Analysis: Application to Social Networks Information Flow[END_REF]. We derived a second order asymptotics for JC of the following form

γ n κ √ α log n + β , (1)
for some β > 0, κ < 1 and γ, α > 0 which depend on the parameters of the two sources. This new estimate has a faster convergence, and is preferred for texts of order n ≈ 10 2 ; For some Markov sources our analysis indicates that JC oscillates with n. This is outlined by the introduction of a periodic function Q(log n) in the leading term of our asymptotics. This additional term even further improves the convergence for small values of n and therefore JC is an efficient method to capture the similarity degree of short texts, e.g. tweets.

Up to now, the main methods used for text classification are based on keywords detection and Machine Learning techniques, described extensively in [START_REF] Aiello | Sensing Trending Topics in Twitter[END_REF]. Using keywords in tweets will often fail because of the distorted usage of the words -which also need lists of keywords for every language to be built -or because of implicit references to previous texts or messages. Machine Learning techniques are generally heavy and complex and therefore are not good candidates for real time text classification, especially in the case of Twitter where we have natural language and thousands of tweets per second to process. Furthermore Machine Learning processes have to be manually initiated by tuning parameters, and it is one of the main drawbacks for that kind of application. Some other methods are using information extracted by visiting the specific URLs on the text, which makes them a heavy procedure, since one may have limited or no access to the information, e.g. because of access rights, or data size.

In this work, we construct the training databases (DBs) by using Twitter's Streaming API while filtering for specific keywords. For example, we build a class about politics by sending a request to Twitter API for tweets that contain the word "politics". Using these requests we build C classes on different topics. Assume that each class contains N tweets (eg. C = 5, i.e. Classes: politics, economics, sports, technology, lifestyle of N = 12, 000 tweets). We allocate a number of keywords to each class (e.g. the keywords used to populate the class). The tweets come in the basic .json format delivered by the Twitter API.

Then, assume that we have a dataset of S timeslots with s = 1 . . . S, and each timeslot is a 15 minutes request in Twitter API. For every tweet x i , where i = 1 . . . N , with N being the total number of tweets, in the s-th timeslot, i.e x s i , we build a Suffix Tree, ST (x s i ), as described in Section 2. Building an ST costs O(m log m) and takes O(m) space in memory, where m is the length of the tweet, in comparison of m 3 needed by algorithms based on semantic analysis.

Then we compute the JC metric, JC(x s i , x s j ) of the tweet

x s i with every other tweet x s j of the s-th timeslot, where j = 1 . . . N , and j = i (by convention we choose JC(x s i , x s i ) = 0). The JC between two tweets can be computed efficiently in O(m) operations (sublinear on average) by ST superposition. For the S timeslots we store the JC scores in the matrices S 1 , S 2 , . . . , S S of N × N dimensions.

We represent timeslots by fully-connected edge weighted graphs, where each tweet is a node in the graph and S n holds the weight of each edge [START_REF] Burnside | One Day in Twitter: Topic Detection Via Joint Complexity[END_REF]. Then, we calculate the score for each node by summing weights of all the edges that are connected to that node. The node that gives the highest score is the most representative and central tweet of the timeslot. Most of the timeslots have N = 12, 000 tweets, so matrices S 1 , S 2 , . . . , S S have approximately 144×10 6 entries for each timeslot. Since the score matrices are symmetric, only half of these entries could be used, i.e the upper/lower triangular, in order to reduce the complexity to N 2 2 . We then assign a new tweet to the class that maximises the JC metric inside that class. In order to limit the size of each reference class we delete the oldest tweets or the least significant ones (e.g. the ones which obtained the lowest JC score). This ensures the low cost and efficiency of the method.

COMPRESSIVE SENSING

Let us first describe the main theoretical concepts of CS [START_REF] Milioris | Low-dimensional signal-strength fingerprint-based positioning in wireless LANs[END_REF] as applied in the context of classification. Let x ∈ R N denote the signal of interest. Such signal can be represented as a linear combination of a set of basis {ψ i } N i=1 . By constructing a N × N basis matrix Ψ = [ψ 1 , ψ 2 , . . . , ψ N ], the signal x can be expressed as x = N i=1 s i ψ i = Ψs. In fact the signal is represented as x = Ψs + θ, with θ ∈ R N being the noise, where E(θ) = 0 and var(θ) = O(|Ψs|).

The efficiency of a CS method for signal approximation or reconstruction depends highly on the sparsity structure of the signal in a suitable transform domain associated with an appropriate sparsifying basis Ψ. The measurement model in the original space-domain is expressed as g = Φx , where g ∈ R M is the measurement vector and Φ ∈ R M ×N denotes the measurement matrix. The measurement model has the following equivalent transform-domain representation

g = ΦΨs + Φθ . (2)
In fact when the length of the sequence n → ∞ and

N → ∞, E(Ψs) = O(nN ), with var(θ) = O(nN ), std(θ) = O( |Φ|n) and E(Φθ) = 0. The second part of (2), Φθ is of relative order O( 1 √ nN )
, and is negligible compare to ΦΨs due to the law of large numbers.

Examples of measurement matrices Φ, which are incoherent with any fixed transform basis Ψ with high probability (universality property [START_REF] Donoho | Compressive sensing[END_REF]), are random matrices with independent and identically distributed (i.i.d.) Gaussian or Bernoulli entries.

In the framework of CS, the problem of classifying a tweet is reduced to a problem of recovering the one-sparse vector s. Of course in practice we do not expect an exact sparsity, thus, the estimated class corresponds simply to the largestamplitude component of s. According to [START_REF] Candés | Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[END_REF][START_REF] Donoho | Compressive sensing[END_REF], s can be recovered perfectly with high probability by solving the following optimization problem ŝ = arg min

s s 1 + τ g -(ΦΨs) 2 , ( 3
)
where τ is a regularization factor that controls the trade-off between the achieved sparsity and the reconstruction error.

Preprocessing phase

During the Preprocessing phase, we built our classes as described in Section 2 and for each class we extract the most representative tweet(s) (CTs) based on the Joint Complexity method. The vector Ψ i T consists of the highest JC scores of the i-th CT. The matrix Ψ T is used as the appropriate sparsifying dictionary for the training phase. Moreover, a measurement matrix Φ i T is associated with each transform matrix Ψ i T , while T denotes the preprocessing phase.

The matrix Ψ i T ∈ R Ni×C is used as the appropriate sparsifying dictionary for the i-th CT, since in the ideal case the vector of tweets at a given class j received from CT i should be closer to the corresponding vectors of its neighboring classes, and thus it could be expressed as a linear combination of a small subset of the columns of Ψ i T . Moreover, a measurement matrix Φ i T ∈ R Mi×Ni is associated with each transform matrix Ψ i T , where M i is the number of CS measurements. In the proposed algorithm, a standard Gaussian measurement matrix is employed, with its columns being normalized to unit 2 norm. A random matrix or a PCA matrix could be also used.

Run phase

A similar process is followed during the runtime phase. More specifically, we denote x c,R as the Joint Complexity score of the incoming tweet with the CT i classified at the current class c, where R denotes the runtime phase. The runtime CS measurement model is written as

g c = Φ R x c,R , (4)
where Φ i R ∈ R Mc,i×Nc,i denotes the corresponding measurement matrix during the runtime phase. In order to overcome the problem of the difference in dimensionality between the preprocessing and run phase, while maintaining the robustness of the reconstruction procedure, we select Φ i R to be a subset of Φ i T with an appropriate number of rows such as to maintain equal measurement ratios.

The measurement vector g c,i is formed for each CT i according to (4) and transmitted to the server, where the reconstruction takes place via the solution of (3), with the training matrix Ψ i T being used as the appropriate sparsifying dictionary. We emphasize at this point the significant conservation of the processing and bandwidth resources of the wireless device by computing only low-dimensional matrix-vector products to form g c,i (i = 1, . . . , P ) and then transmitting a highly reduced amount of data (M c,i N c,i ). Then, the CS reconstruction can be performed remotely (e.g., at a server) for each CT independently.

In this work, we are based on the assumption that the CSbased classification method involves the mobile device that collects the tweets from the Twitter API and a server that performs the core CS algorithm.

TRACKING VIA KALMAN FILTER

Focusing on the problem of classification, the user tweets periodically, and we check that information with the CTs at a specific time interval ∆t.

Then, the classification system estimates the user's class at time t, which is denoted by p * (t) = [x * (t)] T . Following a Kalman filtering approach [START_REF] Grewal | Kalman filtering: Theory and practice using MATLAB[END_REF], we assume that the process and observation noises are Gaussian, and also that the motion dynamics model is linear. The process and observation equations of a Kalman filter-based model are given by x(t) = Fx(t -1) + θ(t) and z(t) = Hx(t) + v(t), where x(t) = [x(t), v x (t)] T is the state vector, with x being the correct class in the space (user's tweets) and v x (t) the tweeting frequency, z(t) is the observation vector, while matrices F and H define the linear motion model. The process noise θ(t) ∼ N (0, S) and the observation noise v(t) ∼ N (0, U) are assumed to be independent zero-mean Gaussian vectors with covariance matrices S and U, respectively. The current class of the user is assumed to be the previous one plus the information provided by the JC metric, which is computed as the time interval ∆t multiplied by the current tweeting speed/frequency.

The steps to update the current estimate of the state vector x * (t), as well as its error covariance P(t), during the prediction and update phase are given by the following equations

x * -(t) = Fx * (t -1) (5)
P -(t) = FP(t -1)F T + S (6) K(t) = P -(t)H T (HP -(t)H T + U) -1 (7) x * (t) = x * -(t) + K(t)(z(t) -Hx * -(t)) (8)
P(t) = (I -K(t)H)P -(t) (9)
where the superscript "-" denotes the prediction at time t, and K(t) is the optimal Kalman gain at time t. The proposed Kalman system exploits not only the highly reduced set of compressed measurements, but also the previous user's class to restrict the classification set. The Kalman filter is applied on the CS-based classification, described briefly in Section 3, to improve the estimation accuracy of the mobile user's path. More specifically, let s * be the reconstructed position-indicator vector. Of course in practice s * will be not truly sparse, thus the current estimated position [x CS ], or equivalently, cell c CS , corresponds to the highestamplitude index of s * . Then, this estimate is given as an input to the Kalman filter by assuming that it corresponds to the previous time t -1, that is, x * (t -1) = [x CS , v x (t -1)] T , and the current position is updated using [START_REF] Jacquet | Classification of Markov Sources Through Joint String Complexity: Theory and Experiments[END_REF]. At this point, we would like to emphasize the computational efficiency of the proposed approach, since it is solely based on the use of the very low-dimensional set of compressed measurements given by ( 2), which are obtained via a simple matrix-vector multiplication with the original high-dimensional vector. Finally, Figure 1

EXPERIMENTAL RESULTS

The efficiency of the proposed classification method is evaluated on sets of tweets acquired from the Twitter API. The classification accuracy of the tested methods was measured with the standard Precision, Recall, and balanced F-score metrics, using a Ground Truth (GT) on more than 1, 041, 000 tweets [START_REF] Papadopoulos | Snow 2014 data challenge: Assessing the performance of news topic detection methods in social media[END_REF]. Then we kept track of which tweet was classified in which class in order to compare this with four classification methods along with many different optimisation techniques for the signal reconstruction mentioned in Section 3.

We selected the Document-Pivot (DP) method to compare with our method, since it outperformed the other state-of-theart techniques in a Twitter context as shown in [START_REF] Aiello | Sensing Trending Topics in Twitter[END_REF]. The most important difference of DP method is that instead of build-ing suffix trees, this time the method constructs a tf-idf bag of words), and then classifies each tweet of the Run phase by selecting the category containing the tweet closest to our test tweet. The notion of closest is because we used Locality Sensitive Hashing based on the Cosine Similarity in a vector space where each possible word is a dimension and its tf-idf score is the coordinate in that dimension. In such a space when the cosine between the two vectors is close to one, it means that the vectors are pointing in the roughly same direction, in other words the two tweets represented by the vectors should share a lot of words and thus should probably speak about or refer to the same subject. Fig. 2 compares the classification accuracy (increased by 27%) of the DP, DPurl and JC+CS, JCurl+CS method as a function of the number of measurements by using the 1 -norm minimization. Fig. 3 compares the reconstruction performance between several widely-used norm-based techniques and Bayesian CS algorithms. More specifically, the following methods are employed 1 : 1) 1 -norm minimization using the primal-dual interior point method (L1EQ-PD), 2) Orthogonal Matching Pursuit (OMP), 3) Stagewise Orthogonal Matching Pursuit (StOMP), 4) LASSO, 5) BCS, and 6) BCS-GSM [START_REF] Tzagkarakis | Bayesian compressed sensing imaging using a Gaussian scale mixture[END_REF][START_REF] Tzagkarakis | Multiple-Measurement Bayesian Compressive Sensing using GSM Priors for DOA Estimation[END_REF]. Fig. 3 shows that BCS and BCS-GSM outperform the introduced reconstruction techniques, while Fig. 4 shows that we a achieve better performance of 11% when using the Kalman filter.

CONCLUSIONS AND FUTURE WORK

In this paper, we performed topic detection based on Joint Complexity and low dimensional classification based on Compressive Sensing with the accuracy of a Kalman filter as a refinement step. The experimental evaluation revealed better performance, while maintaining a low computational complexity. As a future work, we intend to exploit the joint sparsity structure of the indicator vector among the several representative tweets, improving the reconstruction accuracy, while investigating the inherent encryption properties of CS for potential employment in classification on cloud services.

  presents the flowchart of the classification and tracking model based on Joint Complexity, Compressive Sensing and Kalman filter.

Fig. 1 .

 1 Fig. 1. Flowchart of the proposed topic detection and classification method.

Fig. 2 .

 2 Fig. 2. Classification accuracy measured by F-Score for the DP, DPurl and JC+CS, JCurl+CS method as a function of the number of measurements (%) by using the 1 -norm min.

Fig. 3 .

 3 Fig.3. Classification accuracy measured by F-Score as a function of the number of measurements (%) by using several reconstruction techniques, for the JCurl+CS method.

Fig. 4 .

 4 Fig.[START_REF] Jacquet | Common words between two random strings[END_REF]. Classification accuracy measured by F-Score as a function of the number of measurements (%) by using Kalman, for the JCurl+CS method.

For the implementation of methods 1)-5) the MATLAB codes can be found in: http://sparselab.stanford.edu/, http://www. acm.caltech.edu/l1magic, http://people.ee.duke.edu/ ˜lcarin/BCS.html