TweeProfiles4: a weighted multidimensional stream clustering algorithm

FACULDADE DE ENGENHARIA DA UNIVERSIDADE DO PORTO TweeProfiles4: a weighted multidimensional stream clustering algorithm Luís Miguel Azevedo Pereira Mestrado Integrado em Engenharia Informática e Computação Supervisor: Carlos Soares (PhD) July 30, 2015 TweeProfiles4: a weighted multidimensional stream clustering algorithm Luís Miguel Azevedo Pereira Mestrado Integrado em Engenharia Informática e Computação July 30, 2015 Abstract The emergence of social media made it possible for users to easily share their thoughts on different topics, which constitutes a rich source of information for many fields. Microblogging platforms experienced a large and steady growth over the last few years. Twitter is the most popular microblogging site, making it an interesting source of data for pattern extraction. One of the main challenges of analyzing social media data is its continuous nature, which makes it hard to use traditional data mining approaches. Therefore, mining stream data has also received a lot of attention recently. TweeProfiles is a data mining tool for analyzing and visualizing Twitter data over four dimensions: spatial (the location of the tweet), temporal (the timestamp of the tweet), content (the text of the tweet) and social (relationships graph). This is an ongoing project with many interesting challenges. For instance, it was recently improved by replacing the original clustering algorithm which could not handle the continuous flow of data with a streaming method. The goal of this dissertation is to continue the development of TweeProfiles. First, the stream clustering process is improved by proposing a new algorithm. The new algorithm is incremental and supports multi-dimensional streaming data. Moreover, it allows the user to dynamically change the relative importance of each dimension in the clustering. Additionally, a more thorough empirical evaluation is carried out using suitable measures to evaluate the extracted patterns. The proposed algorithm has been applied in the context of Twitter data and has been evaluated in both quantitative and qualitative terms. Its performance has also been measured and compared to the approach used in the previous version of the project. i ii Resumo O aparecimento das redes sociais abriu aos utilizadores a possibilidade de facilmente partilharem as suas ideias a respeito de diferentes temas, o que constitui uma fonte de informação enriquecedora para diversos campos. As plataformas de microblogging sofreram um grande crescimento e de forma constante nos últimos anos. O Twitter é o site de microblogging mais popular, tornandose uma fonte de dados interessante para extração de conhecimento. Um dos principais desafios na análise de dados provenientes de redes sociais é o seu fluxo, o que dificulta a aplicação de processos tradicionais de data mining. Neste sentido, a extração de conhecimento sobre fluxos de dados tem recebido um foco significativo recentemente. O TweeProfiles é a uma ferramenta de data mining para análise e visualização de dados do Twitter sobre quatro dimensões: espacial (a localização geográfica do tweet), temporal (a data de publicação do tweet), de conteúdo (o texto do tweet) e social (o grafo dos relacionamentos). Este é um projeto em desenvolvimento com muitos desafios interessantes. Uma das recentes melhorias inclui a substituição do algoritmo de clustering original, o qual não suportava o fluxo contínuo dos dados, por um método de streaming. O objetivo desta dissertação passa pela continuação do desenvolvimento do TweeProfiles. Em primeiro lugar, é proposto um novo algoritmo de clustering para fluxos de dados com o objetivo de melhorar o existente. O novo algoritmo é incremental e suporta fluxos de dados multidimensionais. Esta abordagem permite ao utilizador alterar dinamicamente a importância relativa de cada dimensão do processo de clustering. Adicionalmente, é feita uma avaliação empírica dos resultados mais completa através da identificação e implementação de medidas adequadas de avaliação dos padrões extraídos. O algoritmo proposto foi aplicado no contexto do Twitter e foi avaliado tanto em termos quantitativos como qualitativos. O desempenho do mesmo também foi medido e comparado com a abordagem utilizada na versão anterior do projeto. iii iv Acknowledgements I would like to thank Prof. Carlos Soares for his supervision in this project. His ideas and guidance enabled the accomplishment of the goals of this dissertation. I also thank Tiago Cunha and André Maia for their support and insights on the theme, which promoted a leaner integration and development process. I would like to thank my family, specially my parents, for all their support, motivation and for believing in my success during the development of this work. Finally, I thank my girlfriend, Inês de Sá, and my friends with a special remark for those from college. All of you made this journey a better experience and it would not have been the same without you. Luís Miguel Azevedo Pereira v LIST OF TABLES xii Abbreviations HMC Hybrid micro cluster MC Micro cluster PMC Potential micro cluster OMC Outlier micro cluster DBSCAN Density-Based Spatial Clustering of Applications with Noise OPTICS Ordering Points to Identify the Clustering Structure REST Representational state transfer API Application programming interface HTTP Hypertext Transfer Protocol NMI Normalized Mutual Information TFIDF Term frequency-inverse document frequency IDF Inverse document frequency xiii Chapter 1 Introduction Social networks are a source of ever growing data being used by many people to share firsthand information. As such, they are regarded as timely and cost-effective source of spatio-temporal information [Lee12]. These social media services not only influence how individuals communicate from a personal perspective, but also how companies define their marketing strategies. Twitter is one of the most popular social networking sites. It has not only gained worldwide popularity but has also been increasing its user activity with over 300 million monthly active users generating 500 million tweets per day [Twi15]. It is considered a microblogging platform for its short message broadcasting features, which allied to the proliferation of this service, makes it an interesting instrument for research studies. These include topic summarization [YZF12,SWCC13], event detection [BF10,BHP11,KBQ14] and sentiment analysis [Cor12,Lee12,BNG11,BL12,CTB+12]. Journalism is one of the most affected businesses, taking advantage of social networks to follow trending topics, information spreading and public opinion on several affairs. TweeProfiles [Cun13] is a data mining tool which allows the analysis and visualization of patterns extracted from Twitter data. The initial version used an offline clustering algorithm to identify patterns over four dimensions: spatial, temporal, social and content. However, it had the shortcoming of only supporting static data and, as such, it was unable to capture emerging trends from a data stream. It was further extended in TweeProfiles2 [Per14], Olhó-Passarinho [Mot14] and TweeProfiles3 [Mai15]. TweeProfiles2 improved the clustering process by introducing an algorithm capable of handling streaming data. Olhó-Passarinho extended the clustering process to consider images as part of the content a tweet, besides the text. TweeProfiles3 focused on improving the visualization of the results and on the integration with SocialBus [BOM+12], a platform for collecting and processing data from social networks for helping researchers build social network datasets. 1 Introduction 1.1 Motivation and Objectives In spite of the progress, some aspects of TweeProfiles can still be improved. As it evolves, it becomes necessary to evaluate the produced results. This is not only important for the ability to validate the clustering approaches, but also because it facilitates tuning the parameters required by the algorithms. Moreover, the user is currently unable to dynamically change the relative importance given to each dimension, since this parametrization is only allowed in the beginning of the process. This makes it difficult for the user to perform sensitivity analysis regarding the weighted combination of the dimensions. Whenever a different combination is required, the clustering algorithm must be restarted from the beginning of the stream, which is not practical. This dissertation aims to continue the development of TweeProfiles by improving several aspects. The first will be the proposal and implementation of a new algorithm for clustering multidimensional streaming data. This novel approach will allow the user to alter the relative weight of each dimension in the clustering process and have results in real-time. The second goal involves the identification and implementation of suitable measures for the evaluation of the resulting clusterings. An empirical methodology will be performed based on the extracted patterns obtained from the developed platform. The platform will be served input data as tweets acquired from a Twitter data collector. 1.2 Document Structure This document is organized as follows: Chapter 2summarizes the state of the art of the scientific fields related to this project, namely: stream clustering algorithms, distance measures, evaluation measures and research done using Twitter. Chapter 3describes the developed tool in terms of the architecture and explains the clustering and evaluation tasks. Chapter 4presents the experimental setup and analyzes the obtained results. Chapter 5concludes the achievements and discusses the work to be done. 2 Chapter 2 State of the art In this chapter, the state of the art in the domain of the project is reviewed. Section 2.1 details technical aspects of the clustering process with focus on the streaming paradigm and on the evaluation measures. In Section 2.2, an overview of the similarity functions is provided in the context of multidimensional clustering. Twitter is described in Section 2.3 and an overview of data mining research done on this microblogging platform is covered in section 2.3.3. The current state of TweeProfiles is described in sections 2.4 and 2.5 with focus on the relevant parts for this work. 2.1 Clustering Data mining is the process of discovering interesting patterns from massive amounts of data [HK06]. This knowledge discovery process comprises the following steps [HK06]: 1. Data cleaning 2. Data integration 3. Data selection 4. Data transformation 5. Data mining 6. Pattern evaluation 7. Knowledge presentation The first four steps are data preparation tasks which are responsible for making the data for being mined. This process is followed by the application of appropriate algorithms to the data so as to retrieve interesting patterns. These patterns are then assessed based on evaluation measures and, finally, a representation of the mined knowledge is constructed for visualization and decision support purposes. 3 State of the art Clustering is an unsupervised data mining task, whose goal is to group unlabeled data into meaningful groups [JMF99]. The data is partitioned by maximizing the similarity between objects in the same cluster, while minimizing the similarity between objects from distinct clusters. The assessment of the similarity is computed using distance functions, which are explained in more detail in section 2.2. Clustering methods can be classified into five categories [HK06]: partitioning, hierarchical, density-based, grid-based and model-based. In section 2.1.1, stream clustering algorithms are presented according to these categories. K-Means is one of the most common clustering algorithms, which fits in the partitioning category. This algorithm tries to find partitions such that the squared error between the points in a cluster and its center is minimized. This is known to be a NP-hard problem. Let us consider a dataset Xof d-dimensional data points Xi,Kclusters Ciwith centroids ci. The squared error is defined as: E= K ∑ i=1 ∑ x∈Ci dist(x,ci)2(2.1) The main steps of the algorithm are the following [Jai10]: 1. Arbitrarily select an initial partition with Kclusters. 2. Generate a new partition by assigning each object to its closest cluster center (most similar cluster) 3. Update the cluster centers Steps 1 and 2 are repeated until a predefined limit number of iterations is reached or until the partitioning does not change in two consecutive iterations. One drawback of the algorithm is the fact that is requires the user to establish the number of clusters K. The minimization of the squared error can only be applied for a fixed number of clusters since the error is inversely proportional to it. As the algorithm only converges to a local minima, it is very sensitive to the initialization performed, which is another disadvantage of this approach. DBSCAN [EKSX96] is a density-based algorithm. It needs to be supplied two parameters, which are the minimum number of points, minPts, and the radius, ε. The algorithm defines core points as those with a dense neighbourhood, which is considered as such when the number of points in the region is greater than minPts. These points are iteratively connected to their neighbours whenever the latter are in the core point’s ε-neighbourhood. The ε-neighbourhood depends on the εparameter, since a point is considered to be in the core point’s ε-neighbourhood if it is within the user-defined radius. DBSCAN is presented in algorithm 1. 4 State of the art Algorithm 1 DBSCAN 1: procedure DBSCAN(minPts :neighbourhood_threshold,D:dataset,ε:radius) 2: Mark all objects as unvisited 3: repeat 4: Randomly select an unvisited object x 5: Mark xas visited 6: if ε-neighborhood of xhas at least minPts objects then 7: Create a new cluster Cand add xto C 8: Let Nbe the set of objects in the ε-neighborhood of x 9: for each point x0in Ndo 10: if x0is unvisited then 11: Mark x0as visited 12: if ε-neighborhood of x0has at least minPts objects then 13: Add those points to N 14: end if 15: end if 16: if x0is not a member of any cluster then 17: add x0to C 18: end if 19: end for 20: else 21: Mark xas noise 22: end if 23: until all points are visited 24: end procedure 2.1.1 Stream Clustering In contrast with static data, continuously arriving data streams bring along some challenges given its continuous and dynamic behaviour. These include the volume of the data, its speed and evolution, the existence of noise and outliers and its eventual high-dimensionality, uncertainty and heterogeneous character. In order to address this challenges, stream clustering algorithms need to meet certain requirements. [Bar02] identifies the following requirements: •Compactness of representation: The clusters must be represented in a compact form, so that the memory resources are not exhausted by the increasing number of points processed. •Fast, incremental processing of new data points: Processing new points has to be an efficient task, which means that it cannot be based on comparisons with all the previously considered points. 5 State of the art •Clear and fast identification of outliers: Since noise has a great influence on the clusters, it is essential to have an efficient outlier handling mechanism. The evolution of the data points over time also plays an important role in stream clustering algorithms. In this sense, these algorithms can be classified according to the kind of window model followed. There are three which are commonly used [ZS02]: landmark window model, sliding window model and damped window model. Figure 2.1 [AWS14] presents an overview of these models. Figure 2.1: Window models in clustering data streams [AWS14] In the context of stream clustering, several algorithms have been proposed and some surveys have been conducted [Mah09,SFB+13,Agg13,WHT13]. In the following subsections, some of these algorithms are described. The major algorithms are explained in more detail and an overview of their derivations is provided. 2.1.1.1 Partitioning Clustering Partitioning clustering algorithms attempt to find mutually exclusive clusters of spherical shape. The grouping is achieved by using distance-based functions and a mean or medoid to represent clusters centers. This type of clustering methods are considered effective for small to mediumsized data sets [HK06]. STREAM [GMM+03] is one of the most popular partitioning algorithms for streaming data. It is a single-pass algorithm, which is based on the k-median problem. The main steps of the algorithm are as follows: 1. Divide the data stream into chunks of mdata points each. The value of mis defined according to memory restrictions. 2. A set of krepresentatives is picked from each chunk so that each data point is assigned to the nearest representative. The representatives are chosen with the goal of minimizing the sum of squared distances of the assigned data points. 6 State of the art 3. After each chunk is processed, the set of kmedians is stored along with their weights and the data points are discarded. The weight corresponds to the number of points assigned to the representative. These representatives are considered level-1 representatives. 4. When the number of representatives exceeds m, these are clustered by taking into account their weights. The representatives that result from this clustering process are considered level-2 representatives. 5. When all the original data points are processed or a clustering result is demanded, the remaining representatives of every level are clustered together. A divide and conquer algorithm is proposed in [GMMO00] and uses a similar approach also based on the k-median problem. The data is divided into chunks and their size is determined so that they can fit in memory. When the data stream is too large, the algorithm recursively calls itself on a smaller set of weighted centers. CluStream [AWC+03] is a stream clustering algorithm, whose process is divided into two components: online and offline. The former phase clusters data and summarizes it using microclusters, while the latter performs another clustering using the stored summary statistics. A pyramidal time frame is used for storing microclusters at snapshots in time at different levels of granularity depending upon the recency. A microcluster, for a group of points Xi1...Xin, with timestamps Ti1...Tin, is defined by the tuple (CF2x,CF1x,CF2t,CF1t,n), with [AWC+03]: •nis the number of data points maintained in the microcluster; •CF1x=∑n j=1Xijis the linear sum of the points; •CF2x=∑n j=1X2 ijis the squared sum of the points; •CF1t=∑n j=1Tijis the linear sum of the timestamps; •CF2t=∑n j=1T2 ijis the squared sum of the timestamps; The microclusters are maintained incrementally, since they have additive and subtractive properties. Besides, they can be merged by simply adding their respective features. In the online phase, when a new point arrives, it is either added to an existing cluster or to a new one. This decision depends on the maximum boundary defined for each cluster. If the point falls within the boundary of a cluster, it is merged to that cluster, otherwise it is put in its own cluster. Since the number of microclusters is to be kept constant, the creation of a new cluster requires one of the existing clusters to be removed or merged into another. This is decided according to certain criteria which takes into account the time recency. The offline phase applies a macroclustering process based on k-means, according to user-specified parameters. These are constituted by the time horizon and by the number of desired macroclusters. The macroclusters correspond to high-level clusters, which are computed using the summarized information of the microclusters obtained in the previous phase. SWClustering is proposed in [ZCQJ08] and uses a cluster feature vector similar to CluStream’s. In this vector, the timestamp of the most recent object is also included and a new data 7 State of the art which improves the quality of the clusters by extracting boundary points in the grids. This process occurs in the offline phase and the border points are assigned by taking into account the distances from the center of the grids. With the goal of improving the performance of the offline component, [WND+09] proposes an algorithm termed as MR-Stream. This algorithm keeps a tree-like structure for the space partitioning, which allows clustering at multiple resolutions. During the offline phase the clusters are generated by determining the reachable cells at a user-defined distance. DCU-Stream [YLZY12] improves D-Stream by adapting the latter for the context of uncertain data streams, where the data is incomplete or imprecise. This is achieved by considering an uncertain tense weight for each data point that is mapped into the grid. This is assigned by considering the arrival time of the data and also its existence probability. Also in the context of uncertain data, [TCT13] proposes Clu-US. It uses the existence probabilities of the data tuples in the calculation of the distance between adjacent grids, instead of being calculated through the traditional geometric centers. PDG-OCUStream [HCRG11] is another density grid-based approach for clustering uncertain data streams. This algorithm is based on a sliding window model and uses a threshold for the probability density in order to control the cluster quality. In the context of uncertain data streams and motivated by the fact that existing algorithms are sensitive to the user-specified threshold, UG-Stream is proposed in [HZ14]. UG-Stream defines a dynamic threshold, which is computed together with the probability variance of the grid in order to distinguish between dense and sparse grids. With a similar goal as SDStream, DENGRIS-Stream [AW12] is proposed as an improvement of D-Stream for clustering over sliding windows. This approach discards grids whose timestamps are older than the beginning of the window. In [BKC13], an algorithm termed as ExCC is proposed for clustering heterogeneous data. As D-Stream, it also has an online and an offline phase. The numerical data is mapped to the grid, while for the categorical data, granularities are defined based on the unique values in the domain. Unlike D-Stream, a window model is not used, since the pruning is performed by taking the speed of the data stream into account. In [TC09], an extension of D-Stream is proposed for clustering data streams taking into account the positional information of data in the grid. It uses the correlation between neighboring grids to merge them when this factor exceeds a certain threshold. Motivated by the fact that the sparsity of the grids is aggravated in the context of high-dimensional data, [RCH11] proposes PKS-Stream. This algorithm improves [TC09] and uses PKS-trees for keeping both the nonempty cells and their relations. The removal of the sparse grids occurs in the offline phase when the PKS-tree is adjusted. In [DCHR11], GDH-Stream is also proposed in the context of clustering high-dimensional data. It is based on subspace clustering, which means that the clustering algorithm is performed on a subset of the dimensions, therefore reducing the spatial complexity. The subspace is generated by ranking the dimensions according to their ability to separate projected clusters. This approach is improved by GDRH-Stream as proposed in [HMR12]. This algorithm considers the relative entropy of attributes in order to filter redundant features. They define a weighted attribute relativity measure, which is used to determine the subspace by computing it for the relevant attributes. 14 State of the art 2.1.1.4 Model-based Clustering Modelling techniques try to optimize the data fitness through probabilistic models. The parameters of the model are determined by ensuring a maximum fit of the underlying clusters. EM (Expectation Maximization) [DLR77] is a popular method to determine these parameters by clustering objects based on a membership probability. In the context of data streams, [DLN+09] proposes SWEM as an improvement of EM. 2.1.2 Consensus Clustering Consensus clustering addresses the problem of reconciling multiple clusters of the same dataset without having access to the underlying features of the data. Different clusters can be obtained by varying selections of attributes or by multiple runs of the same non-deterministic clustering algorithm. The objective is to find an agreement with the multiple clusterings, which highlights their commonalities. A survey of ensemble techniques for clustering has been conducted in [GSIM09] and more recently in [SSVS14] in the context of mixed data clustering. This is an interesting approach for this problem, considering that each dimension can be clustered independently and then merged to reach a final consensus clustering. This process contemplates several approaches [NC07]: Pairwise Similarity, Graph-based, Mutual Information, Mixture Model and Cluster Correspondence. Pairwise similarity measures similarity between data points based on their shared membership to the ensemble clusters. These measures are applied to a similarity-based algorithm in order to obtain the consensus clustering of the ensemble. Graph-based approaches adapt the ensemble of clusterings to a graph representation, while the consensus is obtained by the application onto a graph-based clustering algorithm. Mutual Information formulates an objective function to be maximized, which is based on the commonalities between the ensemble and the final consensus clustering. The Mixture Model approach is based on the generation of probabilistic models from a finite mixture of distributions. The final solution is obtained by solving the corresponding maximum likelihood problem. Cluster correspondence obtains the consensus clustering by optimization of a linear programming formulation combined with a voting procedure. Several proposals have been made to adapt traditional consensus clustering approaches for massive datasets and streaming data. [Eze13] scales an existing consensus clustering algorithm [TJ04], which relies on the Expected Maximization algorithm for mixture models. A strategy for distributing the EM algorithm is developed so as to be run on a cloud, which allows processing large amounts of data. This is done in the context of knowledge mining of large-scale medical data. In this work, multiple clusters are generated by projecting the data to random subspaces. [Hor07] proposes scalable algorithms for merging cluster ensembles of large data sets and data streams. Different clusters are obtained by clustering disjoint subsets of the data. A global consensus is obtained by partitioning the clusters into consensus chains or groups and computing the weighted mean of the corresponding centroids of each one. The problem is approached in a 15 State of the art graph formulation in which the centroids of each partition are represented as vertices of a graph and the dissimilarity between them as weighted edges. The goal is to partition the r-partite graph, where ris the number of partitions to combine, into ktarget clusters by grouping similar centroids together. Since the partitioning is an NP-hard problem, two heuristics are used: Bipartite Merger and Metis Merger. The first finds the global consensus clustering by partitioning the ensembles into kequally sized clusters (consensus chains) with one to one centroid mapping between two partitions . The second partitions the ensembles into kcentroid groups (consensus groups), but the group sizes are not guaranteed to be the same. [YC11] proposes a weighted consensus clustering algorithm in a two-stage process. Different representations are extracted from the full temporal dataset, generating partitions which are clustered independently. A weighted consensus function is applied to reconcile these partitions to candidate consensus partitions. The weighting scheme is based on the evaluation of the clusterings of this phase according to three evaluation measures. The resulting candidate consensus clusters are further reconciled by an agreement function to yield a final consensus cluster. In [ZZTG10] ensemble learning is applied for combining classifiers and clusters for mining data streams. The data stream is partitioned in chunks and a weighting scheme is applied on the ensemble according to the consistency between the base models and the up-to-date model. This is done in order to address the concept drifting problem. [DAR09] addresses the problem of reconciling multiple clusters from different subspaces by means of a weighting scheme. The weighted clusters are obtained by a locally adaptive algorithm, which are further combined by a consensus function. Two functions are introduced for the weighted clustering ensembles, which approach the problem as a graph partitioning resolution: Weighted Similarity Partition Algorithm and Weighted Bipartite Algorithm. The first algorithm constructs similarities between data points based on the membership probabilities to each weighted cluster. The data points and their respective similarities are then mapped to a graph and a k-way partitioning, where kis the final number of clusters, is computed by minimizing the edge weightcut. The second approach differs from the first in the sense that the problem is approached as a bipartite graph partitioning problem. In this case, the graph models both data points and clusters, which forms a bipartite graph, where the edges are weighted based on the cluster membership probabilities. 2.1.3 Clustering Evaluation Clustering evaluation assesses the clustering analysis and the quality of the results generated by the process. This task includes the assessment of clustering tendency, the determination of the number of clusters and measurement of the clustering quality [HK06]. Clustering tendency verifies whether a nonrandom structure exists in the data. This is done to guarantee that the clustering analysis is meaningful for a dataset, since methods for pattern extraction may return misleading clusters. Assessing the clustering tendency can be achieved by using statistical tests for spatial 16 State of the art randomness as the Hopkins Statistic, given as: H=∑n i=1yi ∑n i=1xi+∑n i=1yi (2.3) xi=minv∈D{dist(pi,v)}(2.4) yi=minv∈D,v6=qi{dist(pi,v)}(2.5) with pidata points uniformly sampled from the dataset. dist(pi,v)represents the distance between a data point and the neighbouring points. For a highly skewed dataset, the value of H is closer to 0. Determining the number of clusters is a difficult task, since it depends on the shape and scale of the distribution and also on the granularity demanded by the user. An estimate can be obtained from several methods. A rule of thumb is to set the number of clusters to pn/2 for a dataset of npoints. The elbow method takes into account the fact that the sum of within-cluster variance of each cluster is reduced with the increase of the number of clusters. Even though this increase allows for finer groupings, at some point the reduction on the variance is not significant and does not compensate the performance costs. The optimal number of clusters is, therefore, considered as the turning point. This point can be obtained by plotting the curve of the sum of withincluster variance against the number of clusters. Another known method for estimating the optimal number of clusters is cross-validation. It divides the dataset into mparts, using m1 parts to build a clustering model and the remaining to assess the quality of the previously obtained model. In order to measure the quality of the clustering several methods can be applied. These methods can be categorized as extrinsic, if a ground truth is available, or intrinsic otherwise. Extrinsic methods evaluate the resulting clusters with respect to the ground truth. Recent studies for this measures are found in [SZ08,WXC09]. Intrinsic methods measure the quality of the clusters by considering their separation. In [Mil81], thirty intrinsic measures are examined. Table 2.1 presents a list of evaluation measures according to their respective category, adapted from [KKJ+10,KKJ+11]. [Mil81] identifies a subset of the thirty internal measures examined by their correlation to the Rand statistic and Jaccard criterion. These six measures are Gamma, C Index, Point-Biserial, Tau, W/B statistics and G(+) index. [SZ08] examines seven external measures for clustering representations on data stream clustering: Purity, Cluster-based entropy, Class-based entropy, Homogeneity, Completeness, V-measure and Variation of Information. CMM (cluster mapping measure) is another evaluation measure, proposed in [KKJ+11] for the context of evolving data streams. Sixteen external measures are studied in [SZ08] for K-means clustering. This number is then narrowed down to thirteen by discarding some equivalent measures. These include the Purity, F-Measure, Mutual Information, Variation of Information, Rand statistic, Jaccard coefficient, Fowlkes and Mallows Index, Hubert’s statistics, Minkowski score, classification error and van Dongen crite17 State of the art Table 2.1: Clustering Evaluation Measures Internal Measures External Measures Gamma Rand statistic C Index Jaccard coefficient Point-Biserial Folkes and Mallow Index Log Likelihood Hubert Γstatistics Dunn’s Index Minkowski score Tau Purity Tau A van Dongen criterion Tau C V-measure Somer’s Gamma Completeness Ratio of Repetition Homogeneity Sum squared distances (SSQ) Variation of Information Adjusted Ratio of Clustering Mutual Information Fagan’s Index Class-based entropy Deviation Index Cluster-based entropy Z-Score Index Precision D Index Recall Silhouette Coefficient F-measure W/B Kappa G(+) Classification Error rion. In the context of density-based stream clustering the most common evaluation measures are [AWS14]: SSQ, Purity and Rand Index. 2.2 Distance Measures Clustering requires the computation of the similarities between objects and so different distance functions are used for this task, depending on the nature of the dimensions. The dissimilarity between two d-dimensional objects xAand xBis defined as dist(xA,xB). 2.2.1 Numerical Distance [HK06] refers the following as the most common for numeric data: Euclidean distance, Manhattan distance and the Minkowski distance. The Supremum (or Chebyshev) and the Mahalanobis distances are also mentioned. The Euclidean distance is measured as a straight line and the formula is given as: dist(xA,xB) = q(xA1−xB1)2+···+(xAd−xBd)2(2.6) If an importance is given to each dimension or attribute as a weight w, the Weighted Euclidean distance can be formulated as: dist(xA,xB) = qw1(xA1−xB1)2+···+wd(xAd−xBd)2(2.7) 18 State of the art The Manhattan distance is measured in blocks by summing the vertical and horizontal distances independently. It is defined as: dist(xA,xB) = |xA1−xB1|+···+|xAd−xBd|(2.8) The Minkowski distance generalizes both the Euclidean and the Manhattan distance and it is defined as: dist(xA,xB) = h q|xA1−xB1|h+···+|xAd−xBd|h,h≥1 (2.9) When h=1, the formula corresponds to Manhattan’s and when h=2, it corresponds to Euclidean’s. As for the Mahalanobis distance, it takes into account the correlations of the data and includes a covariance matrix S−1being defined as: dist(xA,xB) = q(xA−xB)S−1(xA−xB)T(2.10) The supremum distance generalizes the Minkowski distance for h=∞, giving the maximum difference in values between both objects. It is defined as: dist(xA,xB) = lim h→∞( d ∑ j=1|xAj−xBj|d)1 d=maxj|xAj−xBj|(2.11) For the specific case of geographical coordinates, the Haversine formula [MK10] can be used. It measures the great-circle distance between points and so the Earth’s shape is considered as a perfect sphere. The formula is given as: dist(xASp ,xBSp ) = 2Rsin−1 sin2xAlat −xBlat 2+cosxAlat cosxBlat sin2xAlng −xBlng 20.5! (2.12) where Ris the radius of the Earth and xAlat ,xAlng ,xBlat ,xBlng are the geographical coordinates (latitude,longitude) of both points respectively. The resulting distance is in the same unit as R. 2.2.2 Textual Distance For measuring the similarity between documents or textual data, [HK06] defines the cosine similarity and the Tanimono distance, which is a variation of the former. In order to compare two documents, they must first be represented as term-frequency vectors. The vector may correspond to the absolute frequency or it may be weighted as T FIDF [MRS08]. The idea of TFIDF is to overcome the fact that the absolute frequency considers all terms as equally important. This improvement is achieved by a weighting technique, which reduces the relevance of common terms. For a tweet t, let αbe its textual content and αia term in that content. 19 State of the art TFIDF defines the weight of a term as: TFIDF =TF(αi)·IDF(αi)(2.13) where TF(αi)is the term-frequency of the term and IDF the relevance of the term. IDF is given as: IDF(αi) = log(N d f (αi))(2.14) where Nis the size of the text collection and d f (αi)the frequency of the term in the documents. The IDF measure is high for rare terms and low for frequent terms. [SHK10] proposes an hybrid TFIDF in the context of microblogging summarization. This approach aims to overcome the sensitivity of TFIDF formula to the document length, which poses a problem when generating summaries from multiple documents. Considering a sentence S with nwords, the weight assigned to it is given as: W(S) = ∑n i=0TFIDF(αi) n f (S)(2.15) where n f is a normalization factor given by the equation: n f (S) = max(minimumThreshold,n)(2.16) Another weighting scheme named TFPDF is proposed in [BI02] with the goal of extracting hot terms which are discussed most often in channels. In this approach, an higher weight is given to a term when its frequency within a channel is also high. Besides, it grows exponentially with the increase of the ratio between the number of documents containing the term and the total number of documents. The formula of T FPDF is given as follows TFPDF = C ∑ c=1|Fc(αi)|expNc d fc(αi)(2.17) |Fc(αi)|=Fc(αi) q∑K k=1Fc(αk)2 (2.18) where Cis the number of channels, Kthe total number of terms in a channel, Fcthe frequency of a term in channel c,Ncthe number of documents in channel cand d fcthe frequency of the term in the documents. The formula for measuring the similarity using the cosine measure is given as: dist(xAC,xBC) = βA·βB kβAkkβBk(2.19) where βAand βBare two term-frequency vectors. kβAkand kβBkcorrespond to the Euclidean norm of the aforementioned vectors. The resulting value varies between 0 and 1. The first is 20 State of the art obtained when both vectors are orthogonal and do not match. A higher value means a greater match factor between the vectors. The Tanimono distance is a variant of this measure for the case of binary-valued attributes. In the referred scenario, the cosine similarity can be interpreted in terms of shared attributes. Its formula is given as: dist(xAC,xBC) = βA·βB βA·βA+βB·βB−βA·βB (2.20) In [RLW12], a variant of Jaccard’s similarity with Dice’s coefficient is used to compute similarity between documents: dist(xAC,xBC) = |βA∩βB| min(|βA|,|βB|)(2.21) [RKT11] proposes a variation of Cosine similarity and also of Jaccard similarity in the context of short text clustering. The equations of the variations are as follows, respectively: dist(xAC,xBC) = 1−∑D d=1βd A·βd B kβAk·kβBk(2.22) dist(xAC,xBC) = 1−|βA∩βB| |βA∪βB|(2.23) 2.2.3 Social Distance A social graph can be inferred from the relationship between users in Twitter. If we consider the users as vertices and the relationships as edges, the social distance is obtained from the distance between the vertices of the graph, which are mapped to tweets’ authors. [HK06] defines two distance measures for graphs: Geodesic Distance and SimRank. Geodesic distance is a simple measure defined as the number of edges which compose the shortest path between the vertices. A shortest path algorithm must be applied, such as Dijkstra’s [Dij59]. SimRank is a similarity measure based on random walk and structural context. It considers two vertices as being similar if they have similar neighbours. The concept of individual in-neighbourhood of a vertex is introduced, as given by the equation 2.24. I(v) = {u|(u,v)∈E}(2.24) for a directed graph G= (V,E), where Vis the set of vertices and Ethe set of edges, such that E⊆VxV. For two distinct vertices u,v∈V, the SimRank distance is given as: dist(u,v) = (0I(u) = 0∨I(v) = 0 C |I(u)||I(v)|∑x∈I(u)∑y∈I(y)s(x,y)I(u)6=0∧I(v)6=0(2.25) where Cis a constant between 0 and 1. The result is also between 0 and 1. In [ACF11], a social distance function named Network Similarity is introduced, which is based on the mutual friends graph and the friendship graph. The former graph, MFG(u,v)contains the 21 State of the art mutual friends of the users and their relationships, while the former, FG(u), contains all friends of a user and their relationships. The Network Similarity function is given as: dist(u,v) = log(|MFG(u,v)| log(2|FG(u)|)(2.26) where |G|denotes the number of edges of a graph G. [Dek06] introduces a social distance function based on link strength, which is weighted based on the periodicity of the communications. The values are assigned from a discrete scale, which varies between 0 (less than once per month) to 1 (communication every day). [SSB05] compares the performance of six network similarity measures in the context of recommender systems for social networks: L1Norm, Cosine similarity, Pointwise Mutual Information (positive correlations), Pointwise Mutual Information (positive and negative correlations), TFIDF and LogOdds. These measures are also used for the work in [ACF13], where a user similarity measure is proposed for online social networks by combining both network and profile similarity. Considering two sets of users Aand B, the L1Norm is given as: dist(A,B) = |A∩B| |A|·|B|(2.27) This measure evaluates to the overlap between the two groups of users, divided by the product of their sizes. It penalizes larger sets more severely than Cosine similarity. The Pointwise Mutual Information (positive correlations) is given as: dist(A,B) = |A∩B| |U|log|A∩B|·|U| |A|·|B|(2.28) where Urepresents the whole set of users. The Pointwise Mutual Information (positive and negative correlations) is given as: dist(A,B) = |A∩B| |U|log|A∩B|·|U| |A|·|B|+|A∩B| |U|log|A∩B|·|U| |A|·|B|(2.29) The Pointwise Mutual Information focuses on the correlations between the memberships on each set. Finally, LogOdds is given as: dist(A,B) = log|A∩B| |A∩B|(2.30) This measure evaluates how membership in one set predicts the membership or absence in another. 2.3 Twitter This section will discuss Twitter and also research that has been done on this subject. 22 State of the art 2.3.1 Description Twitter [Twi14b] is a microblogging service that allows users to publish short text messages, known as "tweets", with at most 140 characters. It is a social network in the sense that the messages are broadcast to the each author’s "followers". Therefore, a relationship is defined by the "follower" or "following" relationship, being that each user is allowed to choose who to follow. Table 2.2 presents the important concepts associated with a tweet, so as to promote a better understanding of the social interactions. Table 2.2: Twitter concepts Concept Description Retweet (RT) Share another user’s tweet Mention (@ + username) Identify a user in a tweet Reply (@ + username) Answer to a previous user’s tweet Hashtag (# + topic name) Association of a keyword to a tweet Localization User’s geo-coordinates when sending the tweet 2.3.2 SocialBus SocialBus [BOM+12], formerly known as TwitterEcho, is a research platform which supports the collection and processing of messages from social networks. It currently supports data extraction from Facebook1and Twitter, but it is designed to be easily extensible. The current architecture of SocialBus is presented in Figure 2.4. The Twitter Consumer retrieves tweets from Twitter using the Twitter Streaming API [Twi14a]. The tweets are sent to a message broker for translation of the data format. The server processes the tweets, extracts metadata, while also being responsible for indexing and tokenization. The processed messages are stored in MongoDB 2. After persisting the information, it is subjected to batch processing for mining different kinds of knowledge. 2.3.3 Research using Twitter The interest on Twitter for research purposes has been growing in the last few years. This section will focus on investigations that cluster Twitter data for several purposes, such as topic summarization, event detection and sentiment analysis. Despite being a rich source of information, the massive amount of tweets makes it difficult for users to plow through them for contents of interest. Twitter topic summarization attempts to solve this issue by summarizing tweets while representing them as short text pieces which cover the most relevant topics. [YZF12] proposes a framework for topic summarization in Twitter which summarizes topics by sub-topics. For this process, a clustering algorithm is used together with a graph-based ranking algorithm which takes into account both the social influence and the 1https://www.facebook.com 2http://www.mongodb.org/ 23 State of the art 30 Chapter 3 TweeProfiles4 This chapter describes the composition and the operations of the developed tool, TweeProfiles4. First, a description of the architecture is provided. Then, the data process and the clustering tasks are explained, followed by the description of the evaluation process. Finally, an overview of the visualization interface is given. 3.1 Introduction TweeProfiles4 was developed as an extension of TweeProfiles [Mai15], which not only allows clustering data streams in real-time, but also the application of a dynamic weighting scheme regarding each dimension. Furthermore, the previous version of the tool has been extended with the inclusion of a clustering evaluation process. The clustering is performed over three dimensions: spatial, temporal and content. The spatial dimension takes into account the geographical coordinates of the tweet. The temporal dimension, besides taking into account the hour and weekday of the tweet, also has an implicit influence on the whole clustering process, since a temporal decay is applied. The content dimension refers to the tweet’s text, which is limited to 140 characters. In order to allow the user to dynamically changes his preferences during the clustering process, a consensus clustering approach has been applied, which is explained in greater detail in this chapter. The evaluation process also involved the adaptation of the clustering algorithms. 3.2 System Architecture TweeProfiles4 is integrated with SocialBus, whose architecture is depicted in Figure 2.4. SocialBus collects the tweets from the Twitter Streaming API, processes them and persists them in MongoDB, which serves as the data source for the clustering algorithm. The high-level architecture of the whole platform is represented in Figure 3.1. 31 TweeProfiles4 The online clustering algorithm is responsible for incrementally processing the data by applying several pre-processing operations (see Section 3.3), mining the data and persisting the results in a relational database. These results are used by both the visualization module and the offline clustering algorithm. The former allows the analysis of the results and is described in detail in Section 3.7. The latter is triggered by user request, which includes his weighting preferences for each dimension. This final operation yields the final clustering results, which are also made accessible for the visualization module through persistent storage in a relational database. The clustering evaluation is also performed during the offline phase, after the computation of the final clusterings. Both the online and offline clustering algorithms are described in detail in Section 3.5. Figure 3.1: TweeProfiles4 system architecture 3.3 Data Processing The clustering algorithm receives a tweet data stream as input. Each tweet collected from the Twitter API is in the JSON format and contains over 30 fields, some of which contain nested objects. Not all the fields are relevant for the dimensions being studied, so the data is filtered and only the fields presented in Listing 3.1 are kept. The next pre-processing step involves extracting the hour of the day (0-23) and the day of the week (1-7, mapping to Sunday-Monday) from the date field. The final step is responsible for processing the text of the tweet as enumerated in the following subtasks: 1. Detect the language of the text; 2. Remove any URLs contained in the text; 32 TweeProfiles4 1{ 2"tweetid":359419233295269888, 3"username":"PipaOliveira_" 4"text":"Uns dormem e outros estudam...", 5"date":"2013-07-22T21:06:37.000Z", 6"lat":"-71.3553287", 7"lon":"-40.15760962" 8} Listing 3.1: Example of a tweet after filtering irrelevant fields 3. Remove all the punctuation from the text; 4. Tokenize the text; 3.4 Distance Functions The distance functions applied to the clustering algorithm were those which had been selected for the previous version of the platform. These are summarized in Table 3.1 (adapted from [Per14]), which also includes the value used for the min-max normalization. Table 3.1: Distance functions and normalization per dimension Formula Dimension Tweet fields Maximum Haversine spatial latitude, longitude 20.020 (km) Euclidean temporal hour, weekday √565 =23,77 Cosine Similarity content text 1 The normalization of the distance values is required since the order of magnitude varies depending on the formula applied. These similarity measures are used in the computation of both tweet-tweet and tweet-cluster distances. Defining the distance as a piecewise function allows one to perform a weighted combination of the similarities of each dimension. Considering a dimension Dand distD(xA,xB)as the distance between two entities xAand xB, which may be tweets or centroids, and wDas the relative weight, the weighted distance measure is given as: dist(xA,xB) = wC·distC(xA,xB)+ wT·distT(xA,xB)+wS·distS(xA,xB)(3.1) with wC+wT+wS=1 (3.2) The aforementioned weighting scheme is applied both in the macroclustering process performed by DBSCAN and in the evaluation of the final clusterings. 33 TweeProfiles4 3.5 Clustering We want to allow the user to dynamically change his preferences regarding the importance of each dimension during the clustering process. Clustering streaming data requires it to be constantly summarized, so it is not possible to obtain meaningful results by starting the clustering process with a set of parameters and then change them at later stages. In order to address this problem, the online clustering process must be agnostic to the weights of each dimension. Moreover, it must provide the necessary representations to be used when a final clustering request arrives, which includes the user’s preferences. Since no assumption can be made on the weights until a final clustering result is demanded, the developed solution relies on the construction of unidimensional microclusters during the online phase. Then, when a clustering request arrives with user-defined weights, weighted multidimensional clusters are constructed from the microclusters computed in the previous phase. Afterwards, the offline phase gives the final clustering from these multidimensional microclusters using DBSCAN. Table 3.2 summarizes the clustering process of each phase, both in the proposed solution and in TweeProfiles2 and TweeProfiles3. Table 3.2: Clustering process Unidimensional Clusters Multidimensional Clusters Online Phase (Micro) TweeProfiles4 TweeProfiles2/3 Offline Phase (Macro) TweeProfiles2/3 TweeProfiles4 Unlike static data clustering, where the data points can be kept in memory, in the streaming paradigm data is summarized and incrementally updated. So, it is not possible to reconstruct multidimensional clusters from unidimensional clusters with full accuracy, since data is inevitably lost. Therefore, the goal is to find a summarization and reconstruction process which gives the most approximate clustering to the one that would be obtained if the weights were being taken into account from the beginning of the online phase. We will explain the clustering mechanism in greater detail in Section 3.5.1, and the two variants developed for the construction of the muldimensional microclusters in Sections 3.5.2 and 3.5.3. 3.5.1 Clustering Mechanism The developed algorithm is divided in two phases: online and offline. The online phase is not only responsible for the incremental maintenance of microclusters, but also of a graph which represents the overlap between them. The offline phase is responsible for providing the final clusterings by taking into account the weighting of each dimension defined by the user, the previously obtained microclusters and their relation in terms of degree of overlapping. A diagram of the offline phase is presented in Figure 3.3. 34 TweeProfiles4 Figure 3.2: Online phase diagram For the online phase, we instantiate one unidimensional clusterer per dimension being studied. In the context of Twitter data, this means we have a spatial clusterer, a temporal clusterer and a content clusterer. Each of these clusterers corresponds to an independent instance of a microclustering algorithm extended from HybridDenStream (see Section 2.4.2). We consider them unidimensional, since each clusterer only extracts patterns taking into account their respective dimension. The similarity measures applied for each dimension are described in Section 3.4. The pseudo-code of our extension of HybridDenStream for the microclustering algorithm is presented in Algorithm 3. The extension of HybridDenStream also includes changes to the HybridMicroClusters, which had to be modified to keep a sample of the merged tweets, which is used later by the clustering evaluation process (see Section 3.6). We consider a point-to-cluster assignment A(X,MC), where Xis a d-dimensional data point and MC a microcluster, as the relation between a data point and the cluster on which the former was merged by the microclustering algorithm. During the online phase, every time a data point arrives from the stream, it is passed to each one of the clusterers, which will merge it into some microcluster. After merging, each clusterer communicates the corresponding assignment, A, to an OverlapManager agent. This agent is responsible for collecting the assignments of each clusterer and updating the OverlapGraph accordingly. The aforementioned graph is a undirected 35 TweeProfiles4 graph, where each vertex, V, is a microcluster and every edge E(V1,V2), which connects two vertices V1 and V2, is weighted according to the overlap between the connected microclusters. The edge weight measures the number of data points in common that each microcluster pair has merged. For every assignment pair A(X1,MCA),A(X2,MCB), where X1=X2, collected by the OverlapManager, the edge weight Ew(MCA,MCB)is incremented by 1 or set to 1 if no such edge exists on the OverlapGraph. The communication between each unidimensional clusterer and the OverlapManager is asynchronous and it was implemented with a producer-consumer pattern for performance reasons. The offline phase is triggered on demand by a request which includes the weighting preference of the user for each dimension. When a clustering request arrives, the microclusters obtained from each clusterer are collected and another graph is derived from the OverlapGraph. The new graph is obtained by removing the vertices of the OverlapGraph which correspond to outlier-micro-clusters and the edge weights are recalculated as follows: Ew(MCA,MCB) = 2∗Ew(MCA,MCB) MCAsize +MCBsize (3.3) Figure 3.3: Offline phase diagram The outlier-micro-clusters are only filtered from the OverlapGraph at this stage, since these may change to potential-micro-clusters over time and maintaining this consistency during the online phase would introduce a communication overhead, which would degrade the performance. At this point, the unidimensional microclusters and the final OverlapGraph are fed to another algorithm which is responsible for providing the multidimensional microclusters. Two algorithms were developed for this task, to which we refer as Solution A (see Section 3.5.2) and Solution B (see Section 3.5.3). 36 TweeProfiles4 Algorithm 3 HybridDenStream extension 1: procedure HYBRIDDENSTREAM EXTENSION(D,ε,β,µ,λ) 2: Tp=1 λlog(βµ βµ−1) 3: Get the next point Xat current time tfrom data stream D; 4: Try to merge Xinto its nearest p-micro-cluster cp; 5: if rp≤εthen 6: Merge Xinto cp; 7: Send assignment A(X,cp)to OverlapManager agent; 8: else 9: Try to merge Xinto its nearest o-micro-cluster co; 10: if ro≤εthen 11: Merge Xinto co; 12: Send assignment A(X,co)to OverlapManager agent; 13: if wo>βµ then 14: Remove cofrom outlier-buffer and create a new p-micro-cluster cpnby co; 15: end if 16: else 17: Create a new o-micro-cluster conby Xand insert into the outlier-buffer; 18: Send assignment A(X,con)to OverlapManager agent; 19: end if 20: end if 21: if (tmod Tp)=0then 22: for each p-micro-cluster cpdo 23: if wp<βµ then 24: Delete cp; 25: end if 26: end for 27: for each o-micro-cluster codo 28: ξ=2−λ(t−to+Tp)−1 2−λTp−1 29: if wo<ξthen 30: Delete co; 31: end if 32: end for 33: end if 34: if clustering request arrives then 35: Generate clusters; 36: end if 37: end procedure After the aforementioned algorithm produces the multidimensional microclusters, a final clustering step is applied to generate the macroclusters using DBSCAN. This macroclustering step has been adapted to use a weighted combination of the distance functions as explained in Section 3.4. 37 TweeProfiles4 3.5.2 Solution A In this solution, the OverlapGraph is applied a k-way partition algorithm [KK98], similar to the approach used in [Hor07], using the METIS [Kar15] package. This outputs arbitrarily-sized partitions, which represent groups of clusters with strong overlapping with each other. The clusters of each partition are then merged to form multidimensional clusters (one per partition). If multiple clusters of the same dimension are present on the same partition, their respective centroid is averaged. The execution of the partitioning algorithm requires the number of partitions to be fixed, which we set to the maximum number of unidimensional microclusters per dimension. 3.5.3 Solution B The first solution has the drawback that the number of partitions has to be defined a priori. Solution B relaxes this constraint and instead tries to group strong overlapping unidimensional microclusters without the referred parameter definition. For this we cluster the OverlapGraph using DBSCAN, where the microclusters are the vertices and the distances between each pair is defined by the weight of the edge which connects them. As in Solution A, the multidimensional clusters are formed by merging the clusters of each partition (one per partition), which the algorithm yields. Again, their respective centroid is averaged if the same partition happens to include multiple clusters of the same dimension. 3.6 Evaluation For the evaluation of the extracted patterns, internal measures were selected and implemented. This decision is supported by the fact that there is no ground truth for the distribution of the Twitter data, therefore external measures are not applicable. The clustering evaluation measures implemented are represented in Table 3.3, according to the objective function which provides the optimal value. Table 3.3: Evaluation measures and their optimal index value Maximize Minimize Silhouette Coefficient SSQ Dunn’s Index G(+) Tau Davies-Bouldin Index Gamma W/B Point-Biserial C Index In the following, we denote n= number of points, k= number of clusters, nk= number of points in cluster k, xi=ith point in cluster Ck, 38 TweeProfiles4 Ck= set of points belonging to cluster k, Nt= number of distinct pairs of points: Nt=n(n−1) 2,(3.4) Nw= number of distinct pairs of points belonging to the same cluster: Nw= k ∑ i=1 ni(ni−1) 2,(3.5) Nb= number of distinct pairs of points belonging to the different clusters: Nb=Nt−Nw,(3.6) Sw= sum of the intra-cluster distances: Sw= k ∑ c=1 ∑ i,j∈Cc i<j dist(xi,xj),(3.7) Sb= sum of the inter-cluster distances: Sb= k−1 ∑ c=1 k ∑ d=c+1 ∑ i∈Cc j∈Cd dist(xi,xj)(3.8) C Index [HL76] is calculated using equation 3.9: CIndex =Sw−Smin Smax −Smin ,Smin 6=Smax (3.9) where Smin is the sum of the Nwsmallest distances between all point pairs and Smax is the sum of the Nwlargest distances between all point pairs. Gamma [BH75] is calculated using equation 3.10: Gamma =s+−s− s++s−(3.10) where s+is the number of times an inter-cluster distance is strictly greater than an intra-cluster distance. s−is the number of times an inter-cluster distance is strictly less than an intra-cluster distance. The equality cases are not taken into account. Using the same notation as Gamma, G(+) [Mil81] is calculated using equation 3.11: G(+) = 2s− Nt(Nt−1)(3.11) 39 Results The reasons for the observed disparity are related to the filtering applied to only include data from Portuguese users or tweets which were written in Portuguese. Besides, the throughput of the data stream is dependent on the frequency of the posts and not limited by the system. There were also limitations regarding system failures and maintenance during some of the periods. The geographical distribution of the tweets present in the dataset can be observed in Figure 4.2, with Portugal, Spain and Brazil being the most representative countries. Figure 4.2: Test dataset spatial distribution Figure 4.3 presents the distribution of the test dataset according to the day of the week. It reveals Friday and Saturday as the most active days in terms of tweet posting, with Tuesday being the least active. Figure 4.3: Test dataset weekday distribution 46 Results Figure 4.3 presents the distribution of the test dataset according to the hour of posting of each tweet. There is less activity until noon, unlike the night hours where the frequency of posts achieves its peak. Figure 4.4: Test dataset hourly distribution We generated a data stream from the static dataset using Streamalizer [Per14], a simple tool to ease the testing of the stream clustering algorithm. It also allows the selection of custom time periods for the tweets’ retrieval. 4.2 Experimental Setup In order to assess the proposed algorithms, a series of tests has been conducted with different conditions. The main goal was to compare our solution with the one proposed and implemented in TweeProfiles2 [Per14]. First, we ran TweeProfiles2’s algorithm and both our solutions with a set of defined parameters, as shown in Table 4.1 (adapted from [Per14]), while varying the εparameters for both the microclustering algorithms and DBSCAN (table 4.2) and the weights of each dimension (table 4.3). For each execution, we gathered the resulting microcluster count and macrocluster count. After this process, we picked a set of three executions, one per solution, and compared their results from the perspective of each dimension being studied. Moreover, we have assessed the quality of the results with the application of the implemented evaluation measures. We have also compared the computational performance of our approach against the solution applied for TweeProfiles2. 47 Results Table 4.1: Clustering algorithms fixed parameters Name Abbrev Description Min Value Max Value Defined Value MinPoints mp Defines the minimum number of points to create a microcluster/macrocluster 1∞2 InitPoints ip Number of points for initialization 0∞50 µ µ Used in the p-microcluster/o-micro-cluster restriction 1∞1 Beta βUsed in the p-microcluster/o-micro-cluster restriction 0 1 0.2 Lambda λUsed in the time decay function; affects the decay rate of the stream 0 1 0.25 Processing speed s Defines the number of data points per time unit 1∞100 Table 4.2: Clustering algorithms variable parameters Name Abbrev Phase Description Min Value Max Value Step Value Epsilon eps Micro Defines the minimum radius of a microcluster 0.2 1 0.1 Epsilon eps Macro Defines the minimum radius of a ε-neighbourhood 0.2 1 0.1 Table 4.3: Weighting parameters Execution Spatial Temporal Content 1 0.33 0.33 0.33 2 0.5 0.5 0 3 0.5 0 0.5 4 0 0.5 0.5 4.3 Results 4.3.1 Clustering In this section we present the results of the performed executions as described in Section 4.2. 4.3.1.1 All Dimensions The following results were obtained using the weight parameters of Table 4.3 for Execution 1, which takes into account all dimensions. 48 Results Table 4.4 presents the microcluster and macrocluster count for the original solution and both developed solutions. Table 4.4: Clustering results for Execution 1 Solution Micro Macro Macro Outliers Original 265 17 239 Solution A 125 10 52 Solution B 208 9 126 Regarding the spatial dimension, we can observe the macroclusters obtained in Figures 4.5a, 4.5b and 4.5c. (a) Original (b) Solution A (c) Solution B Figure 4.5: Spatial view of the macroclusters for Execution 1 The temporal dimension is represented in Figures 4.6a,4.6b and 4.6c. The content dimension is represented in Figures 4.7a,4.7b and 4.7c. The dissimilarity in terms of the number of microclusters is noticeable, particularly between the original solution and solution A. However the difference is reduced for the macroclusterings. From a spatial perspective, we observe similar results with the exception of some macroclusters positioned closer to Africa in the developed solutions when compared to the original. Regarding the remaining dimensions, we find the results to be very similar. 49 Results (a) Original (b) Solution A (c) Solution B Figure 4.6: Temporal view of the macroclusters for Execution 1 50 Results (a) Original (b) Solution A (c) Solution B Figure 4.7: Content view of the macroclusters for Execution 1 51 Results 4.3.1.2 Spatial and Temporal Dimensions This subsection presents the results which were obtained using the weight parameters of Table 4.3 for Execution 2, which comprises the spatial and temporal dimensions. Table 4.5 presents the microcluster and macrocluster count for the original solution and both developed solutions. Table 4.5: Clustering results for Execution 2 Solution Micro Macro Macro Outliers Original 164 4 4 Solution A 139 4 46 Solution B 167 4 0 Regarding the spatial dimension, we can observe the macroclusters obtained in Figures 4.8a, 4.8b and 4.8c. (a) Original (b) Solution A (c) Solution B Figure 4.8: Spatial view of the macroclusters for Execution 2 The temporal dimension is represented in Figures 4.9a,4.9b and 4.9c. Finally, the content dimension is represented in Figures 4.10a,4.10b and 4.10c. Despite the variations in the number of microclusters of the solutions, the resulting macroclusters are the same in number and very similar in every perspective. The similarities between the developed solutions are the most noticeable. We can observe some differences between these solutions and the original, namely on the spatial view (Figure 4.8a), regarding the macrocluster further south, which is marked above Brazil on the original solution as opposed to a positioning 52 Results (a) Original (b) Solution A (c) Solution B Figure 4.9: Temporal view of the macroclusters for Execution 2 more to the east on the others (Figures 4.8b and 4.8c). This macrocluster also affects the content dimension, causing the differences observed between Figure 4.10a and Figures 4.10b and 4.10c. However, the variations in the aforementioned dimension are not very relevant, since it is not being weighted in this execution. 53 Results (a) Original (b) Solution A (c) Solution B Figure 4.10: Content view of the macroclusters for Execution 2 4.3.1.3 Spatial and Content Dimensions In this subsection we present the results which were obtained using the weight parameters of Table 4.3 for Execution 3, which comprises the spatial and content dimensions. Table 4.6 presents the microcluster and macrocluster count for the original solution and both developed solutions. Table 4.6: Clustering results for Execution 3 Solution Micro Macro Macro Outliers Original 106 3 27 Solution A 110 3 14 Solution B 139 2 20 The macroclustering results from the spatial perspective can be observed in Figures 4.11a, 4.11b and 4.11c. The temporal dimension is represented in Figures 4.12a,4.12b and 4.12c. The results from the content perspective are represented in Figures 4.13a,4.13b and 4.13c. Even though the number of microclusters varies for the solutions, the macroclusterings are very similar, specially between the original solution and solution A. For these solutions, we have 54 Results (a) Original (b) Solution A (c) Solution B Figure 4.11: Spatial view of the macroclusters for Execution 3 3 macroclusters as a result of this execution and one less for solution B, which is the macrocluster further north (Figures 4.11a,4.11b and 4.11c). From the temporal perspective, we have the same results on the three solutions. As for the content dimension, we do not observe any significant differences either, even though solution B considers fewer macroclusters. 55 Results We can also observe that including the content dimension results in macroclusters closer to Portugal (figures 4.17a,4.17c and 4.17d) which makes sense since the content of the tweets is similar. This is not only due to the language of the tweets itself, but also because of the topics being discussed, with the most trending keywords being: lisboa,porto,portugal,coimbra,aveiro, sintra,oeiras,centro,escola,parque,metro and universidade. Including the spatial dimension results in macroclusters more distant from each other (figures 4.17a,4.17b and 4.17c) in terms of the geolocation of the cluster center. Regarding the temporal dimension, it is more related with the spatial dimension than the content dimension. That is the reason why the second clustering (Fig. 4.17b) has fewer macroclusters than the last (Fig. 4.17d). (a) clustering 1 (b) clustering 2 (c) clustering 3 (d) clustering 4 Figure 4.17: Spatial view of the macroclusters 4.3.3 Performance We compared the performance of the developed solution during the online clustering process against the solution presented in TweeProfiles2. Only one of the proposed solutions was used for testing, since both share the same logic for the online phase. Table 4.11 shows the performance results measured in terms of CPU Time, User Time and Real Time, otherwise known as Wall Clock Time. These correspond to averaged results of ten 62 Results executions performed for both algorithms. For each execution, we defined a window of 30000 tweets, beginning at a random time point, which were fed to each algorithm as input data. The tests were performed on a PC with Intel Core 2.5GHz CPU and 8GB RAM, running on Windows 8.1. Table 4.11: Performance results Measure TweeProfiles2 TweeProfiles4 CPU Time 20.88s 101.984s User Time 20.75s 101.390s Real Time 21.60s 47.815s Since our solution is based on a consensus clustering approach, it is inherently more computationally expensive. The expected elapsed time of running the unidimensional clusterers would be about three times the original if implemented in a sequential fashion. However, since their computations are independent, they were implemented in parallel. From a fully parallelizable approach, we would expect the elapsed time to be the same as the original. Nonetheless, the considered phase also comprises the computations performed by the OverlapManager, which incurs added complexity. From table 4.11, we can see that our solution is nearly five times costlier than the original in terms of both CPU Time and User Time, but the ratio for the Real Time is only slightly above two. If implemented sequentially, we would not have this performance gain, since the Real Time would be close to the CPU Time, as we observe in the results retrieved from the original solution. It should be noted that the relative performance is very sensitive to the input data, since the number of microclusters being formed in one aproach may be much different from the other. For a certain input, the original solution might output 5 multidimensional microclusters, while our solution could yield 1 microcluster for the spatial dimension, 2 for the temporal dimension and 20 for the content dimension. In this case, the content clusterer would be the bottleneck, potentially 4 times costlier than the original solution alone. This is the reason why we chose to perform ten executions with randomized tweet windows. 63 Results 64 Chapter 5 Conclusions and Future Work In this chapter we present a summary of the project, a discussion of the decisions taken and the limitations regarding the clustering process and the visualization. We finish the chapter with some suggestions for future work. 5.1 Summary The goals of this dissertations were the proposal and development of a multidimensional clustering algorithm with support for a dynamic weighting scheme and the selection and implementation of a clustering evaluation process. To accomplish these goals, a consensus clustering approach has been applied, which uses an extended version of the HybridDenStream clustering algorithm [Per14]. Two variants of the approach have been implemented, which differ from one another in the process used to generate the multidimensional microclusters. The first solution relies on a graph partitioning algorithm [KK98], which requires the number of partitions to be defined. The second solution relaxes this constraint by obtaining the partitions using DBSCAN [EKSX96]. Regarding the clustering evaluation, several internal evaluation measures have been implemented and adapted to support the multidimensional context of Twitter data. This has been achieved with the introduction of weighted distance functions for the computation of intra-cluster and inter-cluster distances. The visualization tool has also undergone some changes. The first modification includes an interface to allow the user to dynamically alter his preferences. For this task, three sliders are provided (one for each dimension), which the user can drag independently to set the corresponding weight. The second modification comprises an interface to display the clustering evaluation results. These are presented in a time series chart, which is updated at frequent intervals and allows a dynamic selection of the evaluation measures to be displayed. 65 Conclusions and Future Work Several performance optimizations have also been performed including the filtering process from SocialBus [BOM+12], the data storage on the database, the clustering algorithm and the visualization tool. This dissertation has been an extension of the TweeProfiles tool and all the goals have been met. The focus was on the improvement of the clustering algorithm in order to add more flexibility for the user to change the weight of each dimension in the clustering process and obtain results onthe-fly. As the data mining project gained maturity, it also became necessary to provide metrics to support the user in the analysis of the quality of the results produced by the clustering algorithm. In this sense, the inclusion of clustering evaluation measures has been another differentiating factor compared to previous versions. 5.2 Discussion In the developed platform, there are some debatable aspects which are discussed below. •Weight Combinations: The number of weight combinations for the experimental setup was chosen arbitrarily. The main reason for not increasing this number was the time consumed for running the process on the full dataset for each algorithm. •Partitioning: For the graph partitioning algorithm applied in the first solution, we defined the number of partitions as the maximum number of microclusters on each dimension. This decision is purely arbitrary and its impact should be understood in more detail. •Evaluation: For the evaluation of the clustering, it was necessary to keep a sample of tweets for each microcluster and macrocluster. The size of each sample has been capped at a fixed number, which has been chosen taking into account the performance of the evaluation task. This limit is a trade-off between a more accurate evaluation and a more efficient one in terms of computation performance. •Database: A MySQL database was used to store the results of the mining and evaluation processes. This approach was chosen to facilitate the integration with the visualization tool and the adaptation of the clustering algorithm used in previous versions of the project. Even though the data is structured, the relational nature of this database system negatively affects the response time, given the current data access pattern. 5.3 Future Work There are still aspects that could benefit from improvements, namely: •Clustering Algorithm: The algorithm used for the unidimensional clustering was adapted from HybridDenStream [Per14], which is based on DenStream [CEQZ06]. Several proposals have been made as an improvement of the latter and it would be interesting to study their suitability in the context of Twitter data. 66 Conclusions and Future Work •Temporal Distance: For the temporal dimension, an Euclidean distance is used to measure the similarity between weekdays. As a consequence, Saturday is more similar to Sunday than to Friday, according to the used mapping. It would be interesting to study the impact of applying a distance measure which took into account the circular aspect of the days of the week. •Social Distance: The social dimension was not included in TweeProfiles4. This is a problem that has still not been solved in a satisfactory way in the TweeProfiles project. Regarding the social graph, one of the issues is that the Twitter Streaming API does not include enough information to build one consistently. Although this data could be obtained through the Twitter REST API, this endpoint imposes rate limiting restrictions, which makes the process infeasible. Besides, even if the information was fully accessible, it would not be feasible to maintain the social graph in memory, given its complexity. Normalization of the distances would also be an issue, since they are unbounded. The problem with formulating an alternative process for studying the social interactions is that it would have to overcome the aforementioned matters and also be meaningful to TweeProfiles. •Performance: Even though an effort was made to parallelize the clustering algorithm where possible, the workflow distribution might still be improved. For this, one could make use of an asynchronous message passing model, using a toolkit like Akka.1 •Database: For the storage of the clustering and evaluation results, a document-oriented database could improve the performance in terms of response time. This would reduce the detrimental effect of the large number of JOIN operations which are expensive in a relational database. MongoDB would be a good candidate, since it is already used for the data collection, therefore reducing the development stack. 1http://akka.io/ 67 Conclusions and Future Work 68 References [ABpKS99] Mihael Ankerst, Markus M. Breunig, Hans peter Kriegel, and Jörg Sander. Optics: Ordering points to identify the clustering structure. pages 49–60. ACM Press, 1999. [ACF11] Cuneyt Gurcan Akcora, Barbara Carminati, and Elena Ferrari. Network and profile based measures for user similarities on social networks. In Proceedings of the 2011 IEEE International Conference on Information Reuse and Integration, IRI 2011, pages 292–298, 2011. [ACF13] CuneytGurcan Akcora, Barbara Carminati, and Elena Ferrari. User similarities on social networks. Social Network Analysis and Mining, 3(3):475–495, 2013. [Agg09] Charu C. Aggarwal. On High Dimensional Projected Clustering of Uncertain Data Streams. In 2009 IEEE 25th International Conference on Data Engineering, pages 1152–1154. IEEE, 2009. [Agg13] CC Aggarwal. A Survey of Stream Clustering Algorithms. pages 229–252, 2013. [AHWY04] Charu C. Aggarwal, Jiawei Han, Jianyong Wang, and Philip S. Yu. A framework for projected clustering of high dimensional data streams. In Proceedings of the Thirtieth International Conference on Very Large Data Bases - Volume 30, VLDB ’04, pages 852–863. VLDB Endowment, 2004. [AMR+12] Marcel R. Ackermann, Marcus Märtens, Christoph Raupach, Kamil Swierkot, Christiane Lammersen, and Christian Sohler. Streamkm++: A clustering algorithm for data streams. Journal of Experimental Algorithmics, 17, 2012. [AW12] Amineh Amini and Teh Ying Wah. DENGRIS-Stream: A density-grid based clustering algorithm for evolving data streams over sliding window. In International Conference on Data Mining and Computer Engineering, pages 206–211, 2012. [AW13] Amineh Amini and Teh Ying Wah. LeaDen-Stream: A Leader Density-Based Clustering Algorithm over Evolving Data Stream. Journal of Computer and Communications, 01(05):26–31, 2013. [AWC+03] Charu C. Aggarwal, T. J. Watson, Resch Ctr, Jiawei Han, Jianyong Wang, and Philip S. Yu. A Framework for Clustering Evolving Data Streams. 2003. [AWS14] Amineh Amini, Teh Ying Wah, and Hadi Saboohi. On Density-Based Data Streams Clustering Algorithms: A Survey. Journal of Computer Science and Technology, 29(1):116–141, 2014. 69 REFERENCES [AWSY11] Amineh Amini, Teh Ying Wah, Mahmoud Reza Saybani, and Saeed Reza Aghabozorgi Sahaf Yazdi. A study of density-grid based clustering algorithms on data streams. In 2011 Eighth International Conference on Fuzzy Systems and Knowledge Discovery (FSKD), volume 3, pages 1652–1656. IEEE, 2011. [AY08] Charu C. Aggarwal and Philip S. Yu. A framework for clustering uncertain data streams. In Proceedings - International Conference on Data Engineering, pages 150–159, 2008. [Bar02] D Barbará. Requirements for clustering data streams. ACM SIGKDD Explorations Newsletter, 3(2):23–27, 2002. [BF10] Albert Bifet and Eibe Frank. Sentiment knowledge discovery in twitter streaming data. Discovery Science, 2010. [BGL10] Danah Boyd, Scott Golder, and Gilad Lotan. Tweet, tweet, retweet: Conversational aspects of retweeting on twitter. In Proceedings of the Annual Hawaii International Conference on System Sciences, 2010. [BH75] Frank B. Baker and Lawrence J. Hubert. Measuring the power of hierarchical cluster analysis. Journal of the American Statistical Association, 70(349):31–38, 1975. [BHKP10] Albert Bifet, Geoff Holmes, Richard Kirkby, and Bernhard Pfahringer. Moa: Massive online analysis. J. Mach. Learn. Res., 11:1601–1604, 2010. [BHP11] Albert Bifet, Geoffrey Holmes, and Bernhard Pfahringer. MOA-TweetReader: real-time analysis in twitter streaming data. Discovery Science, pages 46–60, 2011. [BI02] Khoo Khyou Bun and M. Ishizuka. Topic extraction from news archive using TF*PDF algorithm. In Proceedings of the Third International Conference on Web Information Systems Engineering, 2002., pages 73–82. IEEE Comput. Sci, 2002. [BKC13] Vasudha Bhatnagar, Sharanjit Kaur, and Sharma Chakravarthy. Clustering data streams using grid-based synopsis. Knowledge and Information Systems, pages 1–26, 2013. [BL12] Alexander Boettcher and Dongman Lee. EventRadar: A Real-Time Local Event Detection Scheme Using Twitter Stream. In 2012 IEEE International Conference on Green Computing and Communications, pages 358–367. IEEE, 2012. [BNG11] Hila Becker, M Naaman, and Luis Gravano. Beyond Trending Topics: Real-World Event Identification on Twitter. ICWSM, pages 438–441, 2011. [BNJ12] David M Blei, Andrew Y Ng, and Michael I Jordan. Latent Dirichlet Allocation. Journal of Machine Learning Research, 3:993–1022, 2012. [BOM+12] Matko Bošnjak, Eduardo Oliveira, José Martins, Eduarda Mendes Rodrigues, and Luís Sarmento. TwitterEcho - A Distributed Focused Crawler to Support Open Research with Twitter Data. Proceedings of the WWW 2012, the 21st International Conference Companion on World Wide Web, pages 1233–1239, 2012. 70 REFERENCES [Bru12] Axel Bruns. How Long Is a Tweet? Mapping Dynamic Conversation Networks on Twitter Using Gawk and Gephi. Information, Communication & Society, 15:1323– 1351, 2012. [CCFM97] Moses Charikar, Chandra Chekuri, Tomás Feder, and Rajeev Motwani. Incremental clustering and dynamic information retrieval. In Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing, STOC ’97, pages 626–635. ACM, 1997. [CCZ07] Jian-Long Chang, Feng Cao, and Ao-Ying Zhou. Clustering evolving data streams over sliding windows. Ruan Jian Xue Bao(Journal of Software), 18(4):905–918, 2007. [CEQZ06] Feng Cao, Martin Ester, W Qian, and A Zhou. Density-Based Clustering over an Evolving Data Stream with Noise. SDM, pages 326–337, 2006. [CLOW11] Chun Chen, Feng Li, Beng Chin Ooi, and Sai Wu. Ti: An efficient indexing mechanism for real-time search on tweets. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, SIGMOD ’11, pages 649–660. ACM, 2011. [Cor12] Mário Cordeiro. Twitter event detection: combining wavelet analysis and topic inference summarization. Proceedings of Doctoral Symposium on Informatics Engineering, 2012. [CT07] Yixin Chen and Li Tu. Density-based clustering for real-time stream data. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’07, pages 133–142. ACM, 2007. [CTB+12] Junghoon Chae, Dennis Thom, Harald Bosch, Yun Jang, Ross Maciejewski, David S. Ebert, and Thomas Ertl. Spatiotemporal social media analytics for abnormal event detection and examination using seasonal-trend decomposition. In 2012 IEEE Conference on Visual Analytics Science and Technology (VAST), pages 143–152. IEEE, 2012. [Cun13] Tiago Daniel Sá Cunha. Tweeprofiles: detection of spatio-temporal patterns on twitter. Master’s thesis, Faculty of Engineering, University of Porto, Portugal, 2013. [DAR09] Carlotta Domeniconi and Muna Al-Razgan. Weighted cluster ensembles. ACM Transactions on Knowledge Discovery from Data, 2(4):1–40, 2009. [DB79] David L. Davies and Donald W. Bouldin. A cluster separation measure. IEEE Trans. Pattern Anal. Mach. Intell., 1(2):224–227, 1979. [DCHR11] Wuzhou Dong, Jingyan Cui, Haitao He, and Jiadong Ren. Clustering over HighDimensional Data Streams Based on Grid Density and Effective Dimension. International Journal of Advancements in Computing Technology, 3(8):154–162, 2011. [Dek06] Anthony Dekker. Conceptual Distance in Social Network Analysis. Science And Technology, 6:1–34, 2006. [Dij59] E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1, 1959. 71 REFERENCES [ZGZ09] Chen Zhang, Ming Gao, and Aoying Zhou. Tracking High Quality Clusters over Uncertain Data Streams. In 2009 IEEE 25th International Conference on Data Engineering, pages 1641–1648. IEEE, 2009. [ZK04] Ying Zhao and George Karypis. Empirical and Theoretical Comparisons of Selected Criterion Functions for Document Clustering. Machine Learning, 55(3):311–331, 2004. [ZRL96] Tian Zhang, Raghu Ramakrishnan, and Miron Livny. BIRCH: An Efficient Data Clustering Method for Very Large Databases. In Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, pages 103–114, 1996. [ZS02] Yunyue Zhu and Dennis Shasha. Statstream: Statistical monitoring of thousands of data streams in real time. In Proceedings of the 28th international conference on Very Large Data Bases, pages 358–369. VLDB Endowment, 2002. [ZZTG10] Peng Zhang, Xingquan Zhu, Jianlong Tan, and Li Guo. Classifier and Cluster Ensembles for Mining Concept Drifting Data Streams. 2010 IEEE International Conference on Data Mining, pages 1175–1180, 2010. 78