Hierarchical Sparse Representation Clustering for High-Dimensional Data Streams

Let $\mathbf{D}=[{\mathbf{d}_{1}},{\mathbf{d}_{2}},...,{\mathbf{d}_{n}}]\in{\mathbf{R}^{d\times n}}$ be a dictionary consisting of $n$ vectors. Given a signal $x=\in{\mathbf{R}^{d}}$, its sparsest representation over the dictionary $\mathbf{D}$ can be approximately represented by a sparse linear combination of only a few columns of $\mathbf{D}$, i.e.,

where $\mathbf{z}$ represents a sparse coefficient, $\lambda>0$ is a tradeoff parameter, and ${\left\|\cdot\right\|_{0}}$ denotes the number of nonzero elements in a vector.

Since Problem (1) is nonconvex and nondeterministic polynomial-time (NP)-hard, it is often relaxed to the following ${l_{1}}$-norm minimization problem as a common surrogate for the sparse representation task, i.e.,

where ${\left\|\cdot\right\|_{1}}$ denotes the $l_{1}$-norm of a vector. The above optimization problem can be solved via various convex optimization methods, such as iterative thresholding algorithms [29, 24].

Inspired by the advances achieved with respect to ${l_{0}}$-norm and ${l_{1}}$-norm techniques, sparse representation has been widely used in various areas of machine learning and pattern recognition [30, 31]. For example, Aharon et al. [32] proposed a $K$-singular value decomposition (SVD) algorithm for designing overcomplete dictionaries for sparse representation purposes. The $K$-SVD algorithm can effectively seek the best representation of a given set as a dictionary under strict sparsity constraints. Hence, sparse representation has been proven to be an extremely successful technique for exploiting the intrinsic structures of high-dimensional data.

A data stream is a massive, potentially unbounded sequence of data objects which are continuously generated over time. Most existing data stream clustering algorithms can be broadly categorized into three main types: hierarchy-based clustering, density-based clustering and partitioning-based clustering.

Hierarchy-based clustering algorithms first use the data objects to construct a tree, in which each leaf represents a data object. These algorithms then group data objects into the corresponding clusters using agglomerative or divisive hierarchical decomposition. In the agglomerative approach, $n$ objects are merged into more general classes in a bottom-up fashion, whereas in divisive techniques, $n$ objects are divided into smaller clusters in a bottom-up fashion. BIRCH is a typical hierarchical clustering algorithm that constructs a height-balanced tree using the CF vector [16]. BIRCH adopts the CF vector to compute cluster measures such as the mean, radius, and diameter. Finally, the Euclidean distances between new objects and each centroid of the CF entries are calculated and compared against a threshold to determine whether the new object belongs to a new class. The BIRCH algorithm has $O(n)$ complexity and obtains good clustering results through only a single scan. However, it does not work well with data of arbitrary shape. The E-Stream algorithm is an evolution-based approach for data stream clustering that supports five evolutions of the data, namely appearance, disappearance, self-evolution, merging, and splitting [33, 34].

Density-based clustering algorithms define clusters as high-density areas of the features, which can be used to detect any arbitrary-shaped clusters. DenStream, an extended version of the DBSCAN algorithm, discovers clusters of arbitrary shape in an evolving data stream [18]. It introduces a core microcluster, a potential core microcluster, and an outlier microcluster using the CFs developed for BIRCH. The core microcluster is adopted to summarize the clusters with an arbitrary shape, while the potential core microcluster and outlier microcluster structures are used to pursue and distinguish potential clusters and outliers. DenStream involves numerous time vector calculations in the offline clustering phase, which leads to a high computational cost. The D-Stream algorithm automatically and dynamically adjusts the clusters without requiring user specification of the target time horizon or the number of clusters [11]. An online component maps each input data record into a grid, while an offline component computes the grid density and clusters the grids based on the density. However, D-Stream is incapable of processing very-high-dimensional data.

Partitioning-based clustering methods use traditional soft partitioning techniques such as $k$-median and $k$-means clustering to deal with data streams. CluStream is a two-phase clustering method that performs online micro-clustering and offline macro-clustering [17]. The first phase involves the acquisition of summary statistics from the data stream by extending the concept of the CF vector in the online micro-clustering. Each microcluster contains five components, three of which are the regular components of the CF vector. The second phase uses these statistics and other inputs to create clusters, where the $k$-means algorithm is embedded in the offline macro-clustering component. HPStream was developed as an extension to CluStream that performs projected clustering for high-dimensional streaming data. CluStream is not efficient when applied to high-dimensional data streams.

Let $\mathbf{X}=[{\mathbf{x}_{1}},{\mathbf{x}_{2}},...,{\mathbf{x}_{n}}]\in{\mathbf{R}^{d\times n}}$ be a set of data objects included in a landmark window. The rationale assumption behind clustering algorithms is that data objects within a cluster are more similar to each other than they are to objects belonging to a different cluster. Given a data object ${\mathbf{x}_{i}}$ ($1\leq i\leq n$), HSRC uses the following ${l_{1}}$-norm minimization problem for sparse representation:

where $\varepsilon$ represents a noise item. The above optimization problem can be solved in polynomial time via standard linear programming algorithms [29, 24]. Here $\mathbf{Z}$ can be constructed using the vectors of sparse coefficients, i.e., $\mathbf{Z}=[{\mathbf{z}_{1}},{\mathbf{z}_{2}},...,{\mathbf{z}_{n}}]$, and ${\mathbf{Z}^{*}}=\left|\mathbf{Z}\right|+\left|{{\mathbf{Z}^{T}}}\right|$. Each element $z_{ij}$ in ${\mathbf{Z}^{*}}$ can be used to measure the similarity between two data objects ${\mathbf{x}_{i}}$ and ${\mathbf{x}_{j}}$. If the data objects $\mathbf{x}_{i}$ and $\mathbf{x}_{j}$ are close in terms of the intrinsic geometries of their data distributions, their representations, $\mathbf{z}_{i}$ and $\mathbf{z}_{j}$, respectively, should also be close with respect to the same basis $\mathbf{X}$. Hence, sparse representation is utilized to evaluate the relationships among the data objects contained in high-dimensional data streams.

The solution to Problem (3) is individually obtained for each data object. This inevitably results in high computational costs. However, clustering high-dimensional data streams requires data objects to be continuously clustered within a limited period. To increase the efficiency of optimizing individual sparse representations, we use a sparse batch representation optimization problem as a good surrogate for Problem (3). Specifically, we formulate the following convex optimization problem to find a sparse representation $\mathbf{Z}$:

where $\mathbf{E}\in{\mathbf{R}^{d\times n}}$ is a noise item and $\lambda$ is a scalar constant.

We first convert Problem (4) to the following equivalent problem by introducing an auxiliary variable $\mathbf{J}$:

The augmented Lagrangian function of Problem (5) is

where ${\mathbf{Y}_{1}}$ and ${\mathbf{Y}_{2}}$ are Lagrange multipliers, and ${\mu_{1}}>0$ and ${\mu_{2}}>0$ are penalty parameters. The above optimization problem can be formulated as follows:

This formula can be effectively solved by the inexact augmented Lagrange multiplier (ALM) framework [35]. The variables $\mathbf{J}$, $\mathbf{Z}$ and $\mathbf{E}$ can be updated alternately at each step, whereas the other two variables are fixed. The updating schemes for the $(k+1)$ th iteration are as follows:

The first equation in Problem (8) is a convex problem that can be solved via the singular value thresholding (SVT) operator [36]. The solution of the third equation in Problem (8) is closely related to the value of the $l$-norm, which indicates a certain regularization strategy for characterizing various noises. For example, the ${l_{2,1}}$-norm encourages the columns of the matrix to be zero, where the last equation has a closed-form solution [37]. The complete procedure for solving Problem (5) is outlined in Algorithm 1.

HSRC uses the learned affinity matrix to identify clusters as groups of microclusters through a spectral clustering algorithm, such as NCuts [7]. For simplicity, we assume that $n$ data objects in a landmark window are segmented into $m$ microclusters, i.e., $\mathbf{X}=[{\mathbf{X}_{1}},{\mathbf{X}_{2}},...,{\mathbf{X}_{m}}]$, according to Algorithm 2. For example, the $i$th microcluster contains $n_{i}$ data objects, i.e., ${\mathbf{X}_{i}}=[{\mathbf{X}_{i1}},{\mathbf{X}_{i2}},...,{\mathbf{X}_{i{n_{i}}}}]$. Each microcluster consists of a set of neighboring objects, where each data object within the microcluster can be linearly represented by other objects in the cluster. The microclusters are identified in a single pass of the landmark window, and their summary statistics are stored offline.

We define SRVs to measure the importance levels of the data objects included in clusters. The lower the SRV value of a data object is, the more significant it is during the sparse representation process. Without loss of generality, the sparse coefficients of a data object $\mathbf{x}$ are represented by a vector $\mathbf{z}$, and $\mathbf{e}$ denotes a corresponding noise item in the sparse representation of the object. Given a solution $\mathbf{Z}$ for the data objects $\mathbf{X}$ obtained by Algorithm 1, the representative data objects can be adaptively selected from the candidates by sorting their SRVs. The sizes of the representative data objects are aligned with those of the data objects contained in the landmark window. The dictionary samples in an adaptive dictionary selection scheme consist of two parts, including the data objects contained in the current landmark window and the representative data objects chosen from the previous landmark window.

In practice, outliers often arise due to various factors, such as data collection, storage, or transmission errors. Outliers are data objects that deviate from a sparse representation-based model. To identify outliers throughout high-dimensional data streams, we set a threshold $\sigma\in\left({0,1}\right)$. A data object is estimated according to the threshold $\sigma$. For example, we consider a data object an outlier if it satisfies the following condition:

HSRC is able to adaptively identify outliers in high-dimensional data streams. Algorithm 2 summarizes the complete microclustering algorithm of HSRC.

As microclusters are rough, they need to be merged into macroclusters. Considering the $i$th microcluster, we first choose a candidate from another microcluster as the merged target. Utilizing only the sparse coefficients associated with the $j$th microcluster ${\mathbf{X}_{j}}$, the sparse representation of the $l$th data object ${\mathbf{x}_{l}}$ contained in the $i$ th microcluster can be written as follows:

where $i,j\in[1,m]$, $l\in[1,n_{i}]$ and $i\neq j$. The item $\mathbf{z}_{j}\in{\mathbf{R}^{n_{j}}}$ is a sparse coefficient vector whose entries are those associated with $\mathbf{X}_{j}$. The residual item ${\mathbf{e}_{l}}$ can be used to measure the similarity between ${\mathbf{x}_{l}}$ and ${\mathbf{X}_{j}}$. We adopt the residual item to define the SSD concept, which is used to measure the similarity between two microclusters in the microcluster merging operation.

We further calculate the SSDs of cluster $i$ with the other clusters. Finally, we can obtain a candidate based on these residual items by choosing the lowest error. We need to further check the merging condition to determine whether cluster $i$ and cluster $j$ should be merged. We assume that we obtain a new cluster ${\mathbf{X}_{i+j}}$ after clusters $i$ and $j$ are merged. According to graph theory, the merging condition is that the similarity degree of the merged cluster ${\mathbf{X}_{i+j}}$ must be greater than that of cluster ${\mathbf{X}_{i+j}}$ associated with any other clusters ${\mathbf{X}_{p}}$; i.e., the following two conditions must hold:

where $p\neq i$ and $p\neq j$. If the above conditions hold, two microclusters are merged into a relatively large cluster. The final merging operation is stopped if any two microclusters cannot be further merged. For simplicity, we define a new matrix $\mathbf{S}$ with a size of $m\times m$ to preserve the merged sign for each pair of $m$ microclusters. For instance, ${S_{ij}}$ denotes that cluster $i$ can be merged into cluster $j$. Algorithm 3 below summarizes the complete microclusters merging procedure.

Although sparse representation attempts to automatically choose data objects belonging to the same class in data streams, the coefficients of sparse representation are not completely concentrated on a particular microcluster and instead are likely to be widely spread across a few microclusters. Hence, the microclusters can be considered rough clusters. A data object has a sparse representation whose nonzero entries are concentrated mostly in one microcluster. The distribution of the estimated sparse coefficients contains important clustering information about the relationships among the data objects. Under these circumstances, fine-tuning is a strategy in which a few data objects are selected from a microcluster and then dropped into another microcluster under certain conditions. This strategy incrementally improves the clustering performance achieved for data objects.

From a sparse representation perspective, fine-tuning considers each data object in a microcluster with respect to another microcluster as follows:

where $\mathbf{x}_{l}$ denotes the $l$th data object in the $i$th microcluster, and ${\mathbf{X}_{j}}$ is the $j$th microcluster. We assume that $s$ macroclusters are obtained via Algorithm 3. The error set of $\mathbf{x}_{l}$ is represented as $errorSet=[error_{1},{error_{2}},...,{error_{s}}]$, and the clustering index of the minimum value included in the error set is $j$.

If $i\neq j$, $\mathbf{x}_{l}$ is selected from the $i$th microcluster and dropped into the $j$th microcluster. For example, a data object is picked up from its original cluster and dropped into a new microcluster if it has a smaller residual with respect to another microcluster.

Finally, it is critical to choose candidates from among the data objects that will be purified in their clusters. We consider these data objects, which indicate the spread of the sparse coefficients over most classes. In particular, we adopt the SRV as a criterion to help choose potential outliers in each cluster. Algorithm 4 below summarizes the complete macrocluster fine-tuning procedure.

We assume that $\mathbf{X}$ in a sliding-window has $n$ data objects that belong to $s$ classes, where the size of $\mathbf{X}$ is $d\times n$. Algorithm 5 summarizes the complete data stream clustering algorithm of HSRC. We use an inexact ALM framework in Algorithm 1 [35]. The inexact ALM framework has been extensively studied and generally converges well. Algorithm 1 performs well in practical applications. The computational complexity of the first step of Algorithm 1 is $O({n^{2}})$ because it requires the sparse representation of an $n\times n$ matrix to be computed in an SVT operator. The overall computational complexity of Algorithm 1 is $O(t{n^{2}})$ if the ${l_{2,1}}$-norm is adopted in the last equation of Problem (8), where $t$ is the number of iterations. When $n>d$, the computational complexity of Algorithm 2 can be considered $O({n^{3}})$ in spectral clustering. The computational complexities of Algorithm 3 and Algorithm 4 are $O({k^{2}}{n^{2}})$ and $O({s^{2}}{n^{2}})$ respectively, where $k$ and $s$ are the numbers of microclusters and macroclusters, respectively. The complexity of HSRC is $O({t{n^{2}}+{n^{3}}+{k^{2}}{n^{2}}+{s^{2}}{n^{2}}})$. Therefore, the final overall complexity of HSRC is $O({n^{3}})$ if $t\ll n$, $k\ll n$ and $s\ll n$.

Four benchmark datasets are used in the evaluation [42, 43]. The data objects are randomly shuffled to alleviate any potential effects caused by the sorted streaming order. The drift interval of the Keystroke dataset is 200. The drift intervals of the other datasets are unknown. The Keystroke dataset is composed of 10 feature variables. The Network Intrusion dataset was collected from seven weeks of network traffic simulated in a military network environment. The Network Intrusion requests are divided into two classes: normal and malicious. All the text attributes of Network Intrusion are manually converted into enumerated values and represented by digits. The Forest Cover dataset consists of 54 cartographic variables. The last variables of the datasets represent the ground-truth labels of the corresponding data objects. The Columbia University Image Library (COIL)-100 dataset contains 7200 images of data objects belonging to 100 categories. The statistics of the datasets are summarized in Table I.

The HSRC algorithm is evaluated based on its clustering quality and temporal efficiency. Clustering quality is assessed via clustering purity and the $F$-measure [44]. All the parameters of the competing algorithms are manually tuned to obtain their optimal results. In Algorithms 1-4, HSRC involves three parameters: $\lambda$, $m$ and $\sigma$. Empirically speaking, parameter $\lambda$ should be relatively large if the input data streams are slightly contaminated by noise, and vice versa. Parameter $m$ controls the number of microclusters and is typically set as a multiple of the maximum number of classes contained in the data streams. For our experiments, we use a modified parameter ${m^{\prime}}$ instead of $m$, which ranges from 1 to 2. Microcluster merging is not performed if the maximum number of classes is less than or equal to 2 when ${m^{\prime}}=1$. Parameter $\sigma$ is disregarded in cases where no outliers are detected. Additionally, HSRC disables the fine-tuning operation by setting $w=0$. Further details concerning the parameters are provided in the experiments.

We evaluate the proposed algorithm on the streaming datasets. The four groups of HSRC parameters used for this experiment are (1) $\lambda=100$, $m^{\prime}=1$, $w=0$, (2) $\lambda=0.1$, $m^{\prime}=1$, $w=1$, (3) $\lambda=12$, $m^{\prime}=1$, $w=0$ and (4) $\lambda=20$, $m^{\prime}=1$, $w=1$ . Compared with the other algorithms, the HSRC algorithm almost consistently obtains the best results in terms of clustering purity and the $F$-measure in the experiments. This confirms that our proposed method is very effective for high-dimensional data stream clustering cases with varying numbers of clusters. For example, HSRC achieves a high clustering purity level of 89.49% on the Keystroke dataset and improves the clustering purity by at least 9.43% over those of the other algorithms. We observe the same advantages in our proposed method, which contains more data object features. For example, HSRC achieves high clustering purities of 96.48%, 74.58% and 67.74% for the remaining three datasets. Table II shows that it still significantly outperforms the other four algorithms in terms of the $F$-measure. These clustering results confirm that the relationships calculated from the sparse representations significantly improve the attained clustering performance, especially when the data objects derived from the data streams contain more features. In addition, density-based algorithms can identify clusters with arbitrary shapes in data streams and often perform well when the input data objects have only a few attributes. However, the clustering performance of these algorithms decreases as the number of data object attributes gradually increases.

We evaluate the online performance of the proposed HSRC method on the first 50 windows of two representative datasets, i.e., the Network Intrusion and Forest Cover. Fig. 1 illustrates the online performance attained by the proposed HSRC method on these datasets. We can observe that HSRC almost achieves relatively stable clustering purity and $F$-measures on both datasets. For example, Fig. 1a shows that the online clustering purity and $F$-measure values exceed 90% for most of the landmark windows. Similarly, Fig. 1b indicates that both metrics yielded by HSRC are above 25%. These experimental results demonstrate the excellent stability of the online performance exhibited by the proposed HSRC method.

The time costs of all the competing algorithms are presented in Table III. The density-based algorithms generally have lower computational costs than the other methods do. For example, CluStreamKM has a lower computational cost than the other algorithms do. However, HSRC has relatively reasonable computational costs in the experiments. This is because HSRC spends most of its time computing the affinity matrix using sparse representation.

Compared with $k$-means-based data stream clustering methods such as CluStreamKM and StreamKM++, HSRC employs a spectral clustering technique that also incorporates $k$-means to create microclusters. CluStreamKM and StreamKM++ compute the centroid of each CF vector via the original data objects. In contrast, HSRC uses an $l_{1}$-norm technique to construct an affinity matrix, which encodes the membership attributed of the high-dimensional data objects contained in the input data streams. HSRC captures the intrinsic structures of high-dimensional data objects. The experimental results show that HSRC significantly enhances the clustering purity and $F$-measure values achieved for high-dimensional data streams.

We evaluate the robustness of these algorithms on a more challenging set of high-dimensional data streams. Four artificial pixel noise levels (5%, 10%, 15%, and 20%) are integrated into two datasets: (1) Network Intrusion and (2) Forest Cover. The locations of the corrupted data object attributes are chosen randomly, and the value of each selected location is replaced by a random number within the range $\left[{0,1}\right]$.

Table IV shows the average clustering results produced for the four different noise levels. As expected, the performance of the algorithms slowly decreases as the percentage of noise increases. HSRC achieves consistently better clustering results than those of the other methods. For example, our method achieves average clustering purities of $95.04\%$, $94.95\%$, $94.4\%$ and $94.44\%$ on the Network Intrusion dataset. Regarding the $F$-measure, HSRC significantly outperforms the competing methods across the different noise levels, which indicates that the numbers of macroclusters are much closer to the ground-truth numbers of clusters contained in the landmark windows. However, the clustering performance of the other competing algorithms dramatically decreases as the percentage of noise slowly increases. We also observe that HSRC still retains the same advantages on the Forest Cover dataset. For example, the clustering purity and $F$-measure of HSRC are $74.69\%$ and $43.61\%$, respectively under a noise percentage of 5%. HSRC consistently achieves better clustering performance than that of the competing approaches under the other three noise percentages (10%, 15%, and 20% ). On the one hand, this highlights the benefit of estimating the relationships among data objects via sparse representation. On the other hand, this finding demonstrates that the ${l_{2,1}}$-norm effectively characterizes the noise term in Problem (4). These experimental results demonstrate the robustness of the proposed HSRC method under noisy circumstances.

The proposed outlier detection mechanism is evaluated on the Forest Cover dataset. We select the first 20 landmark windows, and each window contains 1,000 data objects. In each trial, two successive landmark windows are employed, and the experiment is repeated 10 times. Half of the data objects contained within these windows are segmented into clusters, whereas the remaining data objects are treated as potential outliers for testing purposes. The effectiveness of the outlier detection mechanism is then verified via the SRV from Eq. (9). For comparison, we employ the 1-NN method, which is a general outlier detection technique that calculates the Euclidean distance between a test data object and its nearest neighbor within a landmark window. The outlier detection errors are classified into two categories: valid data objects misidentified as outliers and actual outliers incorrectly classified as valid data. The average outlier error rate for HSRC is 4.21%, whereas it is 6.64% for 1-NN across the 10 trials. Compared with 1-NN, HSRC reduces the average outlier error rate by 2.43%.

In Algorithms 1-4, HSRC has two main parameters: $\lambda$ and $m$. We examine the sensitivity of different combinations of parameters $\lambda$ and $m$. In particular, we set parameter $w=1$ for the Network Fusion and Forest Cover datasets. Empirically, parameter $\lambda$ is closely related to the noise level prior of the data stream. Hence, we usually set relatively large values for parameter $\lambda$ in HSRC if the given data stream is slightly contaminated by noise. In addition, parameter $m$ represents the number of microclusters. For convenience, parameter $m^{\prime}$ represents a multiple of the maximum number of classes contained in a data stream. Parameter $m^{\prime}$ ranges from 1 to 2 in the experiments.

Figs. 2 and 3 show the clustering performance achieved on the Network Fusion and Forest Cover datasets, respectively, in terms of the clustering purity and $F$-measure values produced with different combinations of parameters $\lambda$ and $m^{\prime}$. Specifically, Fig. 2 indicates that HSRC performs well across a large range of $\lambda$ values when $m^{\prime}=1$. However, the $F$-measure declines significantly as $m^{\prime}$ increases from 1 to 2. This is because the number of clusters rapidly decreases as the number of macroclusters gradually increases during the experiments. Similar cases can also be observed in Fig. 3. For example, the $F$-measure dramatically decreases when $m^{\prime}$ gradually increases from 1 to 2 in Fig. 3. Therefore, relatively large ranges of $\lambda$ yield satisfactory clustering results when $m^{\prime}=1$.