The problem of clustering a large document collection is not only challenged by the number of documents and the number of dimensions, but it is also a ected by the number and sizes of the clusters. Traditional clustering methods fail to scale when they need to generate a large number of clusters. Furthermore, when the clusters size in the solution is heterogeneous, i.e. some of the clusters are large in size, the similarity measures tend to degrade. A ranking based clustering method is proposed to deal with these issues in the context of the Social Event Detection task. Ranking scores are used to select a small number of most relevant clusters in order to compare and place a document. Additionally, instead of conventional cluster centroids, cluster patches are proposed to represent clusters, that are hubs-like set of documents. Text, temporal, spatial and visual content information collected from the social event images is utilized in calculating similarity. Results show that these strategies allow us to have a balance between performance and accuracy of the clustering solution gained by the clustering method.
The Social Event Detection (SED) task at the 2014
MediaEval Benchmark for Multimedia Evaluation consists of two
subtasks: (1) Image clustering based on a given set of events;
and (2) retrieval of social events based on prede ned queries
[
Search engine technologies e.g., Sphinx, Lucene or Solr
have been successfully implemented to process large sized
document collections for information retrieval. Utilizing the
concept of ranking scores used in search engines, coupled
with using prior knowledge from the learning data, in
semisupervised clustering has shown to be an e ective and e
cient approach of clustering text data [
Semi-supervised clustering methods have shown to
produce a better result compared to their traditional
unsupervised counterpart [
The use of hubs has been explored and has shown its
efcacy in dealing with high dimensional data and clusters
with large sizes [
In this paper, we present a method based on cluster patches to calculate the distance between a document and the groups of documents inside a cluster (Figure 1). Instead of a single centroid, patches are proposed to represent a large highdimensional cluster in order to control the signi cance of similarity measurement.
All the features of the images were used in the clustering
process except of their URL. English stopwords and some
symbols (e.g. #,&,@) were ltered. Title, tag, username,
and description attributes were combined into a short
document. No external resources were used in the analysis.
The document length normalized tf-idf was used as the term
weighting scheme. The time information were transformed
into day interval between date taken and date upload.
Spatial information (i.e. latitude and longitude) were used by
utilizing a modi ed Harversine-formula. The modi cation is
done by changing the range of the measure to a unit value as
in cosine distance. Feature-based super-pixel segmentation
is used to extract compact color and texture representation
for small image patches [
A set of patches P are calculated in each iteration based on the ranking score from the document query. Instead of comparing a document with a cluster centroid, the document feature vector is compared with all the patches. The patches are calculated based on a certain size ( ) neighborhood of documents based on ranking scores within clusters. Optimal distance from the document and these patches is then used to decide the document assignment to a cluster. More detail of the approach is given in Algorithm 1.
input : Set of documents D, initial clusters
C = fc1; c2; : : : ; cK g, neighborhood size m, patches size , and cluster threshold . output: K0 disjoint partitions of D.
Index all documents D; for each di 2 Dtest do calculate a set of cluster patches P = f0 < jdrankj < i; i 2 I; d 2 cj g; for each p 2 P do calculate p = maxpfsim(di; p); p 2 P g; if sim(di; p ) > then
Assign document di to a cluster where p belongs; else
Form a new cluster c=di; end
Update cluster labels via the search engine end end Algorithm 1: Incremental ranking based social event images clustering algorithm.
The similarity measure between a document d and a patch p in a cluster c is given by utilizing textual, temporal, spatial and visual information within images: sim(d; p) = 1simcosine(d; p) + 2simtime(d; p)+ 3simspace(d; p) + 4simimage(d; p): (1) i is a weight parameter to combine the e ect of various types of attributes. These parameters can be ne tuned manually or calculated from the learning data by using variable importance measures from a decision tree model.
We submitted ve runs for the supervised clustering task
(Table 1). Runs one, three, four, and ve used the proposed
method on text only, text-time-space, all attributes, and
text-images set of attributes respectively. While run two is
using the method as described in [
The rst two runs indicate that the proposed method has comparable accuracy to general ranking method, but an improved cluster quality as shown by NMI. While the remaining runs shows that the usage of image, spatial, and time information is ine ective in this data for the purpose of clustering. The main reason behind this is the dependence of the proposed method on text ranking.
An adaptive weighting where weights of each attribute are dynamic among documents is a priority for future investigation to solve this issue. Future work will also explore on nding the optimal parameter and improve the scalability of the method in distributed data and distributed computing environment. 5.
We like to thank Dr Simon Denman from QUT Computational Intelligence and Signal Processing lab for providing us the image visual content encoding.