In this paper, we present our approach for the Social Event Detection task of Medieval 2013 [2]. The goal of the task was to group similar multimedia items into event clusters, based on their metadata (e.g. title, description, tags). Since the number of the event clusters in the test set was not known in advance, we formulated a non-parametric algorithm which resembles the Dirchlet process clustering. More speci cally, we developed a similarity-based version of the Chinese Restaurant Process (CRP) which exploits the similarities among the media items. Our approach achieved a F1 score of 0.2364.
The goal of the Social Event Detection task of Medieval 2013 was to discover event-related multimedia items and organize them in event-speci c clusters. For this purpose a large training set of about 312,000 photos was given along with their textual metadata like title , description, location and tags.
One of the biggest challenges that we faced had to do with the calculation of the number of event clusters in the test set, since this was not known in advance. To tackle this problem, we used the Chinese Restaurant Process (CRP), which is a formulation of the Dirichlet process. It has attracted its name from its analogy to a Chinese Restaurant where n customers are seated to an in nite number of tables based on the following algorithm: The rst customer sits at the rst table. All the subsequent customers either sit at one of the previously occupied K tables with probability n n1k+ , where nk is the number of customers already seated at table k, k = 1; 2; ::K or sit at a new table with probability n 1+ , where is a pre-de ned parameter. The connection between the CRP and our task is pretty straightforward. The photos in the dataset stand for the customers being seated and the tables are the event clusters that group similar multimedia items. The traditional CRP takes into account only the popularity of a table in order to decide whether to assign an item to a speci c table or not. In Section 3 we will present our modi ed version of the CRP, which we call similaritybased CRP as it exploits the similarity among the items in the dataset.
One of the most prominent algorithms in latent topic
discovery is the Latent Dirichlet Allocation (LDA) presented by
Blei et al. in [
In this section we present our algorithm for the Social Event Detection task. Our approach leans on the assumption that similar customers (photos) will tend to gather together and \sit at the same table" in the context of our modi ed Chinese Restaurant Process. Our analysis focused on the comparison of the available metadata of multimedia items which in our case were typical properties like title, description, tags and username, spatial properties like the longitude and latitude, and nally temporal attributes like the date that the media item was taken. The following subsections present in a stepwise manner the construction of our algorithm. We evaluated the importance of each attribute to the allocation of the media items in event clusters. More concretely, we operated on the training set and we measured the probability that two datapoints sharing the same value for a speci c attribute, will also belong also to the same event cluster.The results are depicted in Table 1. In order to measure the similarity of two photos in the test set, we used the computed probabilities as scores. More speci cally, the computation of the similarity between two datapoints i and j was performed using the following formula vij =
P a2attrs
proba Ma(i; j) , where attrs is the set of the metadata, proba the associated scores from Table 1 and Ma(i,j) is the matching function. For the majority of the attributes (Location, Username, Title, Tags) the M function is simply the indicator function 1 i,j share the same value for attribute a Ia(i; j) = 0 otherwise In the case of the \Date Taken" attribute we used an exponential decay weight function to model the temporal proximity of two photo items. More speci cally the similarity score was computed as Mij = exp( jdi hdjj ) , where di, dj are the timestamps of the two datapoints. The denominator in the exponent h is called the bandwidth and controls the rate of decay. We set this value to 1 hour, so that timestamps with time di erence less than one hour will receive high values (close to 1) , while larger deviations are penalized more heavily.
The second issue that we faced was the scaling of the algorithm in large datasets. Even for medium size datasets, like the one given for the task, it becomes impractical to measure the similarities among all pairs of datapoints. To tackle this problem, we introduced the concept of table pro les. A table pro le is simply the union of all the photo items that \sit" in that table, and it is equivalent to a super-photo item that encompasses all the characteristics of the photos belonging to the table. Using this trick, we reduced signi cantly the number of comparisons needed to allocate a new \customer" (media item) from n (the total number of customers at that point) to K (the number of occupied tables)
This subsection nally presents our modi ed CRP algorithm. When a new customer (photo) comes in we measure its similarity with each one of the K already occupied tables and then we make a stohastic decision: The newcomer will either sit in one of K tables with probability analogous to their similarity value, or she will pick a new table.In short, the algorithm works as follows : 1. The rst customer (photo) sits at the rst table (event cluster) and initializes the rst table pro le. 2. For each of the subsequent customers we compute their similarity value with each of the K table pro les. We denote these values as vk , k = 1,2..K 3. The customer sits at table k with probability Pi vvik+ or sits at a new table with probability Pi vi + the former case, the attributes of the media item are \merged" into the k-th table pro le, while in the latter case a new table pro le is initialized by the media item. . In The parameter controls the distribution of the customers on the tables. Higher values of signify higher dispersion and thus, a larger number of occupied tables, while lower values of give more compact allocations. Finally, to better measure the quality of our results, we computed the purity1 of the generated clusters as purity( ; C) = N1 P maxj(!k \ k cj) , where where = f!1; !2; : : : ; !K g is the set of the clusters generated by the algorithm and C = fc1; c2; : : : ; cJ g is the set of the actual clusters.
The results were very sensitive to the selection of . We
performed a line search in the region [