A common task in many domains with a temporal aspect involves identifying and tracking clusters over time. Often dynamic data will have a feature-based representation. In some cases, a direct mapping will exist for both objects and features over time. But in many scenarios, smaller subsets of objects or features alone will persist across successive time periods. To address this issue, we propose a dynamic spectral co-clustering method for simultaneously clustering objects and features over time, as represented by successive bipartite graphs. We evaluate the method on a benchmark text corpus and Web 2.0 bookmarking data.
In many domains, where the data has a temporal aspect, it will be useful to analyse the formation and evolution of patterns in the data over time. For instance, researchers may be interested in tracking evolving communities of social network users, such as clusters of frequently interacting authors in the blogosphere, or circles of users with shared interests on social media sites. In the case of online news sources, producing large volumes of articles on a daily basis, it will often be useful to chart the development of individual news stories over time.
For many of these problems it may be of interest to simultaneously identify
clusters of both data objects and features. This task, often referred to as
coclustering, has been formulated as the problem of partitioning a bipartite graph,
where the two types of nodes correspond to objects and features [
A popular recent approach to the problem of clustering dynamic data has
been to use an “offline” strategy, where the dynamic data is divided into
discrete time steps. Sets of step clusters are identified on the individual time steps
using a suitable clustering algorithm, and these step clusters are associated with
one another over successive time steps [
A number of additional considerations arise when tracking dynamic data represented in feature spaces. Notably, a set of objects or features will not always persist in the data across steps. In general, three different scenarios are possible: 1. Data objects alone persist across time steps. For instance, in bibliographic networks, papers are only published at a single point in time, whereas authors will generally be present in the network over an extended period of time. 2. Features alone persist across time. In a news collection, articles will appear once, whereas terms may continue to appear as topics extend over time. 3. Both objects and features persist across time. For example, in the case of Web 2.0 tagging portals, both the individual tags and the objects being tagged (e.g. bookmarks, images) will appear in multiple time steps. A simple example with just two clusters is shown in Figure 1.
Here we consider the problem of tracking nodes in multiple related dynamic bipartite graphs. In Section 3 we describe the main contribution of this paper – a dynamic spectral co-clustering algorithm for simultaneously grouping objects and features over time, in any of the above scenarios. This algorithm takes into account both information from the current time step, together with historic information from the previous step. In our evaluations in Section 4 we show that the proposed algorithm works both in the case where features alone persist over time, and when objects and features persist. These evaluations are performed on a labelled benchmark news corpus and Web 2.0 tagging data. 2 2.1
In certain problems it may be useful to perform co-clustering, where both
objects and features are assigned to groups simultaneously. One approach to the
co-clustering problem is to view it as the task of partitioning a weighted
bipartite graph. Dhillon [
The general problem of identifying clusters in dynamic data has been studied by
a number of authors. Early work on the unsupervised analysis of temporal data
focused on the problems of topic tracking and event detection in document
collections [
The application of dynamic clustering methods has been particularly
prevalent in the realm of social network analysis, where the goal is to identify
communities of users in dynamic networks. Palla et al. [
We represent a dynamic feature-based dataset as a set of l bipartite graphs {G1, . . . , Gl}. Each step graph Gt consists of two sets of nodes, representing the nt data objects, and mt features present in the data at time t. Edges exist only between nodes of different types, corresponding to non-zero feature values. We can conveniently represent each step graph using a feature-object matrix At of size mt × nt.
In the offline formulation of the dynamic co-clustering problem, the overall goal is to identify a set of dynamic clusters of objects and features, which appear in the data across one or more time steps. We refer to step clusters that are identified on individual step graphs, which represent specific observations of dynamic clusters at a given point in time. The formulation therefore has two key requirements: a suitable clustering algorithm to cluster individual time step graphs (ideally in a way that incorporates historic information), and an approach to track these clusters across time steps. While our primary focus here is on the former aspect, in Section 3.3 we also briefly discuss the latter aspect. 3.2
We now introduce a dynamic co-clustering algorithm that considers both historic
information from the previous time step, and the internal quality of the clustering
in the current time step. The algorithm consists of three phases: bipartite spectral
embedding, cluster initialisation, and a cluster assignment phase.
Spectral embedding. Following normalised cut optimisation via spectral
coclustering described in [
Zt =
D1−1/2Ukt
D2−1/2Vkt
(1)
Prior to clustering, the rows of Zt are subsequently re-normalised to have unit
length, as proposed for spectral partitioning in [
Cluster initialisation. At time t = 1, we have no historic information.
Therefore to seed the clustering process, we use a variant of orthogonal initialisation
as proposed by Ng et al. [
For each time step t > 1, we initialise using clusters from the previous time step. A simple approach is to map the clusters generated on the embedding for time t − 1 to Zt. However, as noted previously, not all features and objects will persist between time steps. To produce an initial clustering at time t, we identify the intersection of the sets of nodes present in the graphs Gt−1 and Gt. The clusters containing these are mapped to the embedding Zt, and we compute the resulting centroids. If less than kt centroids are produced, the remaining centroids are chosen from the rows of Zt using orthogonal selection as above. We can then predict memberships for each unassigned row zi of Zt, using a simple nearest centroid classifier to maximise the similarity: (2) (3) (4)
T max zi μc
C∈Ct where μc is the centroid of cluster Cc. This classification procedure yields a predicted clustering for rows in Zt (i.e. a co-clustering of all objects and features present at time t), which we denote Pt.
Cluster assignment. To recover a clustering from Zt, we apply a constrained
version of k-means clustering to the rows of the embedding, which takes into
account both the internal quality of the current partition, and agreement with the
predicted partition Pt. We distinguish the latter from the membership
preservation objective described in [
As a measure of current cluster quality, we use vector-centroid similarities
as in Eqn. 2. Historical quality is calculated based on the quantity pred(Pt, Ct),
which denotes the degree to which the predicted cluster assignments in Pt agree
with those in the current clustering Ct. To quantify this agreement, we use a
variant of pairwise prediction strength [
X where co(zi, zj ) = 1 if both rows were predicted to be coassigned in Pt, or c(zi, zj ) = 0 otherwise.
To combine both sources of information, the clustering objective then becomes a weighted combination of two objectives:
J (Ct) = (1 − α) · k X X c=1 zi∈Cc
T
zi μc
!
+ α · (pred(Pt, Ct))
This type of aggregation approach has been widely used for combining sources of
information, such as in dynamic clustering [
– Normalise the rows of Zt to unit length. 2. Initialisation and prediction – If t = 1, apply orthogonal initialisation to select a set of kt representative centroids from the representations of the objects in the embedded space. – For t > 1, recompute the kt−1 centroids based on last clustering but including only the embedding of the relevant set of objects/features in the current space. – If not all rows of the embedding have been assigned, apply nearest centroid classification to compute the predicted clustering Pt. 3. Compute clustering
– Apply constrained k-means to rows in Zt, initialised by centroids from Pt.
The parameter α ∈ [
Eqn. 4 can be viewed as the standard spherical k-means objective [
T max (1 − α) · zi μc + α · pred(zi, C)
C∈Ct where the quantity pred(zi, C) represents the degree to which the predicted assignment for the row zi in Pt agrees with the assignment of zi to cluster C. This is given by the proportion of rows in C that were co-assigned with zi in Pt: pred(zi, C) =
1 |C| (|C| − 1)
X
(zi,zj)∈C
Once the algorithm has converged to a local solution, Ct provides us with a k-way
partitioning of all nodes in the graph Gt (i.e. features and objects). An overview
of the complete co-clustering process is shown in Figure 2.
In the previous section we proposed an approach for co-clustering individual time
step graphs. The second aspect of the offline approach to dynamic clustering
involves identifying dynamic clusters composed from clusters associated across
time steps. We suggest that previous frameworks for tracking evolving dynamic
communities [
To evaluate the performance of the algorithm proposed in Section 3.2, we
required an annotated dataset with temporal information. For this purpose we
consider the bipartite document clustering problem, and use a subset of the
widely-used Reuters RCV1 corpus [
Our evaluations focused on the performance of the dynamic spectral
coclustering algorithm on each time step graph in the RCV1-5topic dataset, using a
range of values α ∈ [0.1, 0.5] for the balance parameter. As a baseline competitor,
we used multi-partition spectral co-clustering as proposed by Dhillon [
Figure 3 shows a comparison of agreement values for the three different time window sizes. Dynamic co-clustering leads to a higher level of agreement than 1 Datasets for this paper are available at http://mlg.ucd.ie/datasets/dynak.html standard spectral co-clustering for all three time window sizes. The effect becomes significantly more pronounced as α increases. This is to be expected, as increasing the parameter leads to a higher weighting for the historic information in Eqn. 4. For α ≥ 0.5, the resulting co-clusterings are often almost identical to the predicted co-clustering Pt, with the constrained k-means process converging to a solution after 2-5 iterations.
Clustering accuracy. To quantify algorithm accuracy, we calculated the NMI between clusterings and the relevant annotated document label information for 1.0 I) 0.8 M t(N 0.6 n e em 0.4 e r g A 0.2 0.0 1.0 I) 0.8 M t(N 0.6 n e em 0.4 e r g A 0.2 0.0 1.0 I) 0.8 M t(N 0.6 n e em 0.4 e r g A 0.2 Fig. 3. Comparison of agreement (in terms of NMI) between successive feature clusterings, generated by spectral co-clustering and dynamic co-clustering (α ∈ [0.1, 0.5]), on the RCV1-5topic dataset for monthly, fortnightly, and weekly time steps. each time step. Figure 4 illustrates a comparison of the accuracy achieved by traditional spectral co-clustering and dynamic co-clustering on the RCV1-5topic dataset for the three different time step sizes. We observed that, for monthly and fortnightly time steps, the accuracy achieved by dynamic co-clustering was not significantly higher. However, for the weekly case, there was a noticeable increase in accuracy. In the case of α = 0.5, dynamic co-clustering lead to higher accuracy on 21 out of 28 of the weekly graphs.
These results could appear surprising given the increases in temporal
smoothness demonstrated Figure 3. However, on closer inspection, it is apparent that
there is a strong concept drift effect in the data, as the composition of topics
0.70
I) 0.60
M
N
(
cy 0.50
a
r
u
c
cA 0.40
0.30
0.70
I)M 0.60
N
(
cy 0.50
a
r
u
ccA 0.40
Fig. 4. Comparison of accuracy (in terms of NMI) for document clusterings generated
by spectral co-clustering and dynamic co-clustering (α ∈ [0.1, 0.5]), on the RCV1-5topic
dataset for monthly, fortnightly, and weekly time steps.
changes over seven months. Therefore, for longer time periods, there is a greater
change in the clusters identified in successive time periods. In such cases we
expect historic information to be less useful. For the shorter weekly time windows,
where there is less scope for drift between steps, we expect the use of historic
information to improve accuracy. These results highlight the importance of
selecting an appropriate time step size for offline dynamic clustering.
For the second phase of our evaluation, we applied the proposed co-clustering
algorithm to a Web 2.0 data exploration problem. Unlike the RCV1 data, subsets
of both objects (bookmarks) and features (tags) persist over time. We use a
subset of the most recent data from a collection harvested by G¨orlitz et al. [
Figure 5 illustrates the agreement between both tag and bookmark clusterings identified by dynamic co-clustering for a balance parameter range α ∈ [0.1, 0.5]. As with the RCV1-topic data, an increase in the value of α leads to clusters that are considerably more similar to those produced in the previous step, yielding smoother transitions between both feature and object clusters across time. In the extreme case of α = 0.5, there is effectively no change between the predicted memberships and the final output of the co-clustering algorithm.
A number of authors (e.g. [
In this work, we have described a spectral co-clustering algorithm for simultaneously clustering both objects and features in dynamic feature-based data, represented as a sequence of bipartite graphs. The co-clustering algorithm incorporates both current and historic information into the clustering process. A key aspect of the approach is that it is applicable in domains where objects or features alone persist across time steps. In applications on both dynamic text and bookmark tagging data, the proposed approach was successful in identifying coherent clusters, while also ensuring a consistent transition between clusterings in successive time steps.
Acknowledgments. This work is supported by Science Foundation Ireland Grant No. 08/SRC/I140 (Clique: Graph & Network Analysis Cluster)