Carlos Vicient
email: carlos.vicient@urv.cat

Antonio Moreno
email: antonio.moreno@urv.cat

A study on the influence of semantics on the analysis of micro-blog tags in the medical domain

Keywords: Semantic similarity, tags, co-occurrence, clustering, micro blogging

One current research topic in Knowledge Discovery is the analysis of the information provided by users in Web 2.0 social applications. In particular, some authors have devoted their attention to the analysis of micro-blogging messages in platforms like Twitter. A common shortcoming of most of the works in this field is their focus on a purely syntactical analysis. It can be argued that a proper semantic treatment of social tags should lead to more structured, meaningful and useful results that a mere syntactic-based approach. This work reports the analysis of a case study on medical tweets, in which the results of a semantic clustering process over a set of hashtags is shown to provide much better results than a clustering based on their syntactic co-occurrence.

Introduction

In the last years the World Wide Web has moved from a collection of static pages that were created by experts and read by users to a very dynamic environment in which users are not only consuming information but also providing it (the so-called Social Web or Web 2.0) [START_REF] O'reilly | What Is Web 2.0? Design Patterns and Business Models for the Next Generation of Software[END_REF]. Many researchers in Artificial Intelligence are already working in the next step (the Social Semantic Web or Web 3.0 [START_REF] Berners-Lee | The Semantic Web -A new form of Web content that is meaningful to computers will unleash a revolution of new possibilities[END_REF]), in which intelligent autonomous agents should be able to understand the semantics behind all this usergenerated data in order to solve automatically complex processes like open information extraction, information retrieval, question answering, automated reasoning, etc. [START_REF] Etzioni | Open information extraction from the web[END_REF][START_REF] Fensel | Semantic web application areas[END_REF][START_REF] Brill | Processing natural language without natural language processing[END_REF].

In the current Social Web users generate and distribute many different kinds of data in a wide variety of formats, from pure text to pictures, audios, videos, weblogs, etc. [START_REF] Holzinger | Interactive technology for enhancing distributed learning: a study on weblogs[END_REF]. In order to facilitate the access to these data, many Web 2.0 applications allow users to attach them some kind of keywords, usually called tags, which provide information on the main topics related to a certain item. In some limited cases these tags may belong to well-defined domain taxonomies or ontologies, providing an accurate indexing of the tagged elements. However, in most cases uses may freely add any textual keywords, giving rise to unstructured folksonomies. An important research problem is the design and development of tools that allow users to visualise, explore and interact with these enormous unstructured repositories of user-tagged data (HCI) and to discover and extract meaningful knowledge from them (KDD) [START_REF] Holzinger | On Knowledge Discovery and Interactive Intelligent Visualization of Biomedical Data -Challenges in Human-Computer Interaction & Biomedical Informatics[END_REF]. Current tools usually rely on information retrieval techniques to find relevant pieces of information about a certain topic on such a huge volume of generated data and also on clustering methods to sort and classify the relevant documents according to their similarity. In this regard, in the last years some researchers have proposed ontology-based text clustering [START_REF] Hotho | Wordnet improves Text Document Clustering[END_REF] or tag similarity [START_REF] Cattuto | Semantic Analysis of Tag Similarity Measures in Collaborative Tagging Systems[END_REF][START_REF] Cattuto | Semantic Grounding of Tag Relatedness in Social Bookmarking Systems[END_REF] methods. This classification process allows a posterior filtering process that keeps only those sets of documents that are more related to the user's interests, which may then finally be shown to the user applying advanced HCI visualization techniques. However, despite the great number of works in the field, it can be argued that there is still a lack of semantically-based classification and visualization mechanisms on Social Web data.

Some researchers are focusing on the analysis of the information provided by users in social networks. Micro-blogging services are one of the Web 2.0 kinds of applications that are attracting more attention. The most successful one is probably Twitter, that has around 200 million regular users that generate 500 million tweets per day [START_REF] Hold | Twitter in numbers[END_REF]. A tweet is a free text with a maximum length of 140 characters. Users may tag a tweet using the so-called hashtags, which are strings of characters that begin with the "#" symbol.

As will be commented in the next section, many researchers have focused on the analysis of hashtags in order to perform complex knowledge-based tasks on a corpus of tweets [START_REF] Abel | Semantic Enrichment of Twitter Posts for User Profile Construction on the Social Web[END_REF][START_REF] Weng | TwitterRank: finding topic-sensitive influential twitterers[END_REF]. However, most of the scientific contributions have focused almost exclusively on a purely syntactic analysis of the content of tweets, including their hashtags. For instance, some works have proposed to discover the main topics in a corpus of tweets by clustering them taking into account the syntactic co-occurrence of hashtags. In this paper we want to argue that a semantic analysis of hashtags, based on the use of well-known ontology-based semantic similarity measures, should lead to more meaningful and relevant results that a merely syntactic analysis. We have tested this research hypothesis by clustering a set of medical tweets using both syntactic cooccurrence and semantic similarity measures, obtaining a more appropriate classification of the tweets in the second case, as we expected.

The rest of the paper is structured as follows. The next section provides a brief background on related work on the analysis of tweets, showing the current predominance of syntactic methods. Section 3 describes a new mechanism that permits to make a semantic analysis of the hashtags contained in a set of tweets, by associating them to the concepts of an ontology and then employing ontology-based similarity measures to compute the relatedness between hashtags. In section 4 the case of study using a set of medical tweets is presented, explaining the analysed data set and the syntactic and semantic clustering techniques applied on them. The following section presents and comments the results of the study, and the last section closes the paper with some final comments and the presentation of future lines of work.

Related Work

There have been many works in which sets of tweets are analysed for different purposes (e.g. visualization of clusters of similar tweets [START_REF] Bhulai | Trend visualization in Twitter: what's hot and what's not? DATA ANALYTICS[END_REF][START_REF] Pöschko | Exploring Twitter Hashtags[END_REF], recommendation of hashtags [START_REF] Kywe | On recommending hashtags in twitter networks[END_REF], sentiment analysis [START_REF] Wang | Topic sentiment analysis in twitter: a graph-based hashtag sentiment classification approach[END_REF][START_REF] Petz | Opinion Mining on the Web 2.0 -Characteristics of User Generated Content and Their Impacts[END_REF], detection of events or common topics [START_REF] Doan | Enhancing Twitter Data Analysis with Simple Semantic Filtering: Example in Tracking Influenza-Like Illnesses[END_REF][START_REF] Russell | Semantic Analysis of Energy-Related Conversations in Social Media: A Twitter Case Study[END_REF], clustering of tweets [START_REF] Veltri | Microblogging and nanotweets: Nanotechnology on Twitter[END_REF][START_REF] Özdikiş | Semantic expansion of hashtags for enhanced event detection in Twitter[END_REF], etc.). However, in most cases it can be observed that the treatment of the tweet components (mainly the words contained in the body of the tweet and its hashtags) is purely syntactic. Kywe et al [START_REF] Kywe | On recommending hashtags in twitter networks[END_REF] aim to recommend hashtags that could be associated to a particular tweet, by considering those hashtags employed by similar users (those that use the same hashtags) or used in similar tweets (those that contain the same words). Doan et al. [START_REF] Doan | Enhancing Twitter Data Analysis with Simple Semantic Filtering: Example in Tracking Influenza-Like Illnesses[END_REF] analyse sets of tweets in order to track the evolution of influenza, and they propose to filter those tweets that contain certain pre-defined words as hashtags. Russell et al. [START_REF] Russell | Semantic Analysis of Energy-Related Conversations in Social Media: A Twitter Case Study[END_REF] analyse sets of tweets related to the Energy domain, and they define a notion of "semantic similarity" between tweets based on the co-occurrence of their terms. Bhulai et al. [START_REF] Bhulai | Trend visualization in Twitter: what's hot and what's not? DATA ANALYTICS[END_REF] also consider the co-occurrence of words within tweets to make clusters of tweets for visualization purposes. Teufl and Kraxberger [START_REF] Teufl | Extracting semantic knowledge from twitter[END_REF] represent a tweet with a set of terms (nouns, adjectives, verbs and hashtags) and use the co-occurrence between them to define a weighted graph that can be analysed to obtain the "semantic pattern" associated to each tweet. Mathiesen et al. [START_REF] Mathiesen | Modular networks of word correlations on Twitter[END_REF] build graphs of terms, where the edges are weighted by their co-occurrence, and study the communities present in these graphs. Veltri [START_REF] Veltri | Microblogging and nanotweets: Nanotechnology on Twitter[END_REF] also uses the co-occurrence between words to classify tweets related to the Nanotechnology domain. The lack of a semantic treatment of the content of the tweets is the main shortcoming of all these approaches. Some authors have focused on the analysis of the co-occurrences between the hashtags that appear on a set of tweets, but they also seem to take a purely syntactic point of view. Wang et al. [START_REF] Wang | Topic sentiment analysis in twitter: a graph-based hashtag sentiment classification approach[END_REF] define a sentiment analysis method based on different mechanisms of sentiment propagation in graphs that basically take into account the co-occurrence of hashtags. Ozdikis et al. [START_REF] Özdikiş | Semantic expansion of hashtags for enhanced event detection in Twitter[END_REF] cluster hashtags by considering the cooccurrence between the hashtags and the words that appear in the tweets. Pöschko [START_REF] Pöschko | Exploring Twitter Hashtags[END_REF] also considers the co-occurrence between hashtags to group together related tweets for visualization purposes. Again, all these approaches consider only the cooccurrence of the strings that define the tags, without trying to understand their meaning to make a more thorough and semantically coherent treatment.

The main aim of this paper is to show, via an illustrative case of study in the medical domain, that clustering hashtags using a proper semantic similarity measure (supported by a domain ontology) provide a much more coherent result than the use of a purely syntactic co-occurrence metric.

Semantic Tag Similarity

As mentioned before, one of the main characteristics of social tagging is that users can freely annotate contents without any restriction in their choice of tags. Those tags usually lack any form of explicit organization and normalization, giving rise to un-structured folksonomies. This fact produces, as a consequence, several problems when using tags in retrieval tasks and in their classification. One of them is that different tags might have been used for the same concept (synonymy), which makes it difficult to find all items relevant for a certain concept. Another one is that the same tag can have different meanings in different contexts (polysemy). Just to name another one, a purely syntactic analysis of tags is unable to show whether two tags have some kind of relatedness (e.g. "Religious Building" is more general than "Cathedral", and "Cathedral" is more related to "Abbey" than to "Restaurant"). To overcome these problems, it is necessary to have methods that can find tags that are conceptually related. In other words, a semantic tag similarity measure is needed in order to compare two tags at the conceptual level (i.e. a metric to measure how similar is the meaning of two lexically different tags). Another characteristic of this kind of social tagging is the fact that tags may be acronyms, named entities, a composition of different terms or even invented words. This diversity presents a challenge in the discovery of the conceptual meaning of the tag. The linkage between the term and its meaning (a concept in a background knowledge structure, for instance a domain ontology) is what we call semantic annotation, and solving this issue is required to be able to define semantic similarity measures for tags. In this work WordNet [START_REF] Fellbaum | WordNet: An Electronic Lexical Database (Language, Speech, and Communication)[END_REF], a semantic lexicon for the English language that models and semantically interlinks more than 100,000 concepts referred to by means of English textual labels, is used as the reference background knowledge structure into which tags are mapped. WordNet is organised in synsets, which are useful to solve problems like synonymy. Moreover, it also introduces hierarchies of concepts which can be used to identify related concepts.

The rest of this section aims to propose a methodology to link tags with its meaning (with WordNet elements) and to calculate the semantic similarity between them. Notice that tags are not necessarily contained in WordNet. So, the basic idea is to find the mapping between tags and WordNet concepts and, after that, to apply well-known semantic measures to compare two different tags associated with WordNet concepts. Thus, the presented methodology is divided in two main parts: the semantic annotation and the calculation of the semantic similarity.

Semantic Annotation

The aim of this first stage is to analyse a tag and associate it, if possible, with a WordNet concept. In case the tag is composed of multiple words, the system generalises it by dropping sequentially the leftmost terms until a matching is found (e.g., if the tag is "Gothic Cathedral" and this expression is not found in WordNet, the system will look for "Cathedral"). Algorithm 1 shows the procedure applied to calculate the similarity between two tags. The input parameters are the two tags to be compared and the semantic measure to be used to compare two WordNet elements. The function getCandidates, explained later, returns a list of possible concept candidates to be matched with the tag within WordNet. This list only contains the tag itself if it matches directly with a WordNet concept. However, due to the nature of the hashtags commonly used in Twitter, there may be many cases in which hashtags are not found directly in WordNet and a more complex analysis is needed to find out the WordNet concept that should be associated to the hashtag (in fact, in some cases it may turn out to be impossible to find an appropriate matching between a hashtag and any concept). After that, if both candidate lists are not empty, the semantic similarity between the tags is computed by the calcu-lateSimilarity function, which is also described below.

Sem Sim (tag1, tag2, measure){ candTag1 := getCandidates(tag1) candTag2 := getCandidates(tag2) if (candTag1 || candTag2) == null return 0.0 return calculateSimilarity(candTag1, candTag2, measure) } Algorithm 1. Calculates the semantic similarity between tags "tag1" and "tag2", considering a given "measure" of semantic similarity between WordNet concepts In order to find possible semantic annotations for a given tag, the first step is to check whether it appears directly as a WordNet concept. If the tag is found, then the annotation is direct. However, as pointed out before, there are many different kinds of tags that do not appear in WordNet directly. To overcome this problem, the proposed methodology relies on Wikipedia as an external knowledge base. This procedure can be seen in the pseudo-code of Algorithm 2.

getCandidates(tag){

wTag := getWNConcept(tag) candidates <-wTag if wTag == null candidates := getWikipediaCandidates(tag) return candidates } Algorithm 2. Given a tag, returns a lists of possible WordNet concepts with which it could be annotated Wikipedia is a well-known free online encyclopaedia which contains more than 30 million articles that have been written collaboratively by volunteers all around the world. In all the knowledge-based tasks associated to the analysis of Natural Language it has been assumed in the last years that Wikipedia is the premier and more comprehensive repository of textual knowledge, due its enormous breadth and the quality of its collaborative-based contents [START_REF] Suchanek | YAGO: A Large Ontology from Wikipedia and WordNet[END_REF]. Its articles are not limited to the standard <concept, definition> structure of a dictionary, but they can describe just about anything one can imagine. Thus, Wikipedia entries have a much wider scope than WordNet concepts, permitting to find for example acronyms, named entities, different lexicalizations of the same concept, etc. Moreover, Wikipedia articles are loosely classified by means of a hierarchy of Wikipedia categories. Each of them defines the essential characteristics of a certain topic, allowing readers a mechanism to browse and quickly find sets of related pages.

In the semantic annotation mechanism, when a tag has not been found in WordNet, it is looked up on Wikipedia. If there is an entry for the tag, all the associated categories are retrieved. A category is treated as a phrase and it is proposed as an annotation candidate only if its head (the main noun of the description of the category, extracted by a natural language parser) matches with a WordNet concept. This process is shown in the high level description of the function getWikipediaCandidates in Algorithm 3. So, eventually, all the proposed candidates are WordNet concepts. A tag will not have any associated candidate concepts only if it is not found either in WordNet or in Wikipedia, or if the categories found in Wikipedia do not match with any concept in WordNet.

getWikipediaCandidates (tag){

wikiCandidates := null if existsWikiEntry(tag) auxCategories := getCategoriesFromWiki(tag) forall cat ∈ auxCategories mainNoun := getNN(cat) auxCat := getWNConcept(mainNoun) if auxCat != null wikiCandidates <-auxCat return wikiCandidates } Algorithm 3. Used to extract and process Wikipedia categories that will work as candidates to be annotated with WordNet concepts

Semantic Similarity

At this point there is a list of WordNet concepts (obtained directly or via Wikipedia categories) associated to each of the two tags to be compared. In order to establish the degree of semantic relatedness of the tags, the similarity between all the pairs of candidates (one from each tag) is calculated. This similarity is calculated with a function that computes the semantic similarity measure between WordNet concepts, which is given as parameter by the user. This function could be any of the well-known ontology-based similarity metrics described in the literature. The final similarity between the tags is the maximum of the similarities between the associated WordNet concepts.

If the tags are associated to a certain domain of knowledge (for instance, the medical domain considered in the next section), it may be argued that calculating the similarities between all the pairs of candidates and taking the maximum one solves, in an indirect way, the problem of disambiguating the correct sense of the tag. The idea is that, even if the terms that we are comparing are polysemic, each of them will have a "medical" sense, and these domain-related senses will be the ones with a higher similarity. This process is shown in the pseudo-code depicted in Algorithm 4.

calculateSimilarity(candidates1, candidates2, measure){ simMax := 0 forall cat1 ∈ candidates1 forall cat2 ∈ candidates2 sim := measure(cat1, cat2) if(sim >= sim_max) simMax := sim return simMax } Algorithm 4. Maximises the similarity between all the pairs of candidates of the given lists.

Case of Study: Data Set of Medical Tweets

The underlying research work concerns the study of the influence of the use of ontology-based semantic similarity measures on the analysis of a corpus of tweets. In this paper we present a preliminary study, conducted over a set of medical tweets on the cancer disease. As will be argued in the next section, the results of this study confirm the intuition on the improvement of the results with respect to the usual syntactic analysis. This section describes the obtainment and treatment of the data set, whereas the next section provides a more detailed analysis of the results of the comparative study between syntactic and semantic clustering of tags. The first step was the extraction of a dataset of medical tweets from the Symplur Website1 . This dataset is composed of approximately 5000 tweets that are strongly related with "cancer" (according to Symplur), dated from October 31st 2012 to January 11th 2013. After a first filtering pre-process, we obtained a set of 1086 different hashtags used in this dataset. The graph on Fig. 1 depicts a distribution of the number of hashtags per tweets, where the y-axis represents the total number of tweets that contain exactly the number of hashtags represented in the x-axis. Notice that there are 2530 tweets tagged only with one hashtag and just one tweet containing 12 distinct hashtags.

The first step of the analysis is the semantic annotation, in which hashtags are linked to WordNet concepts. 409 hashtags (37.6 %) are found directly in WordNet. When Wikipedia categories are used to support the annotation process, as described in the previous section, the system is able to annotate 815 hashtags (75.0%). Therefore, this indirect annotation route permits to double the number of annotated hashtags. However, it has to be noted that 25% of the hashtags cannot be annotated even with the help of Wikipedia. An area of future work is to make a more detailed analysis of the hashtags so that this percentage of unannotated tags can be lowered; moreover, another field of future work is the thorough analysis of the quality of the annotation, both in its direct and indirect routes.

Fig. 1. Distribution of hashtags per tweet

A common way of analysing a set of tweets is to take their hashtags and partition them in a set of non-overlapping classes, so that all the hashtags in the same class (cluster) are supposed to be heavily related, whereas those belonging to different classes should be associated to different topics [START_REF] Pöschko | Exploring Twitter Hashtags[END_REF][START_REF] Wang | Topic sentiment analysis in twitter: a graph-based hashtag sentiment classification approach[END_REF][START_REF] Özdikiş | Semantic expansion of hashtags for enhanced event detection in Twitter[END_REF]. In this study we have compared two different ways of clustering the set of hashtags of the tweet corpus:  The first clustering process is purely syntactic. The measure of similarity between two hashtags used by the clustering algorithm is based on the number of tweets in which both hashtags co-occur. The more frequently two hashtags appear, the more related they are supposed to be.  The second clustering process is grounded on the use of a domain ontology that permits to measure the actual semantic similarity between two hashtags.

The pseudo-code of the algorithm used in this study is shown in Algorithm 5. The two input parameters of the algorithm are k (the number of classes to be generated in the clustering process) and the main topic of the extracted tweets (which in this study is "Cancer"). First, we obtain the set of tweets related to the input topic. After that, a filtering method is applied. In this step duplicates (e.g. re-tweets of the same tweet by different users) are removed, and word-breaking techniques are used in order to split hashtags composed by more than one word. The next step, described in the following subsections, is the construction of a similarity matrix between hashtags, which is used in the final step by a clustering algorithm to obtain the set of clusters of hashtags.

Hashtag_Clustering

Syntactic Clustering Based on Hashtag Co-Occurrences

In order to generate the symmetric similarity matrix used by the clustering process two steps are necessary. First, a hashtag co-occurrence matrix (as shown in Eq. 1) is constructed, where represents the total number of hashtags, is the number of cooccurrences between hashtag and hashtag within the dataset, and contains the times that the hashtag appears in the whole dataset. Notice that has the same value that , fact that implies that the order in which the hashtags appear in the set of tweets is not relevant.

⌈ ⌉ ∈ (1)
Afterwards, the matrix has to be normalised so that all its values are between 0 and 1, since the clustering method used in this study needs either a similarity or a dissimilarity matrix as input data. To do so, each element of the matrix is normalised (

∈ [ ] ∈ [ ] ( ))
where ( ) is the function shown in Eq. 2. This function assigns the value 1 to each element of the diagonal of the matrix (a hashtag is equal to itself). The co-occurrence between two different hashtags is normalised by dividing it by the minimum number of their individual appearances. The rationale of this approach is that two hashtags will be considered highly similar if, in most of the tweets in which one of them appears, the other hashtag also appears. For instance, if hashtag A appears in 100 tweets, hashtag B appears in 500 tweets, and they appear together in 80 tweets, their similarity will be very high (80/100=0.8), since B appears in 80% of the tweets containing A. Other more restrictive ways of normalising the matrix values, considering for instance the maximum or the average of the individual appearances, could have also been considered.

( ) { ( ) (2)
In Fig. 1 it was shown that more than half of the analysed tweets only contain 1 hashtag, and only around 18% of them have 4 or more hashtags. Therefore, the number of co-occurrences between hashtags is relatively small; moreover, the pairs of cooccurrent hashtags are likely to appear in different tweets. Therefore, there are many cells in the co-occurrence matrix with a 0 value (near to 86%), for all those pairs of hashtags that do not appear together in any of the input tweets (i.e. only about 14% of pairs of hashtags co-occur). With this co-occurrence based similarity measure, these pairs of hashtags are considered to be totally dissimilar.

Clustering Based on Semantic Similarities

In this section the aim is the same than in the previous section, the construction of a normalised similarity matrix between hashtags. However, in this case we want to define an ontology-based semantic similarity matrix. Let (Eq. 3) be the mentioned matrix, where represents the total number of hashtags and is the semantic similarity between hashtag and hashtag , calculated with the function (Algorithm 1), so that

∈ [ ] ∈ [ ] ( ). ⌈ ⌉ ∈ [ ] (3)
In the experiment reported in this section Wu and Palmer's similarity measure [START_REF] Wu | Verbs semantics and lexical selection[END_REF] has been used to estimate the semantic alikeness between words by mapping them to WordNet concepts and computing the number of semantic links separating them. This measure gives a value between 0 and 1, so it does not require any further normalisation. As a result, terms are classified according to their semantic similarity.

It is worth noting that the matrix does not have as many null values as the normalised matrix. The reason is that relies on direct co-occurrences among hashtags, and most of them do not tend to co-occur at all, whereas is constructed with the results of the function, which is applied to WordNet elements. Thus, two very different hashtags will probably have a very low semantic similarity, but not a null one.

Analysis of the Results

The final part of the study consists in clustering the set of 815 annotated hashtags in two different ways, considering the and normalised similarity matrixes, and comparing the results. The intuition is that the semantic clustering should be more meaningful and better structured than the one based on syntactic co-occurrence. In this case, the parameter k has been fixed to 99 clusters (to obtain clusters with an average low number of elements, around 8, which can be easily managed and analysed) and the resultant clusters have been compared as follows:

1. Centroids are key components in many data analysis algorithms such as clustering.

They basically represent a central value that minimises the distance to all the objects in the cluster. The centroid of each cluster has been calculated with the ontology-based semantically-grounded methodology presented in Martínez et al [START_REF] Martínez | Semantically-grounded construction of centroids for datasets with textual attributes[END_REF]. In this approach, first a set of centroid candidates is constructed, taking into account all the concepts associated to the input cluster of hashtags according to the background knowledge (i.e. WordNet). In a second step, the final centroid of each cluster is calculated as the concept candidate that minimises the average semantic distance to all concepts in the set. 2. In order to determine the internal compactness of each cluster (how similar they elements are) we have computed in this study the average distance to the centroid of all the elements of the cluster which are linked to WordNet concepts. Notice that, in order to calculate this distance, any well-known ontology-based semantic similarity measure like path length, Wu-Palmer, etc. [START_REF] Wu | Verbs semantics and lexical selection[END_REF][START_REF] Rada | Development and application of a metric on semantic nets[END_REF] could have been used, since all these linked elements are in the semantic level defined by the WordNet taxonomy. Budanitsky et al [START_REF] Budanitsky | Evaluating WordNet-based Measures of Lexical Semantic Relatedness[END_REF] reported a list of those measures and evaluated their performance. In this study, as mentioned before, we have used the Wu-Palmer semantic similarity measure [START_REF] Wu | Verbs semantics and lexical selection[END_REF]. This measure is a path length-based measure that has the advantage of being independent of corpus statistics, uninfluenced by sparse data and easy to implement. 3. The average distance of all the elements of each cluster with respect to its centroid is calculated for both approaches (co-occurrence and semantic) and the results are compared. The lower the distance, the better the cluster (i.e. the inter-homogeneity of the cluster is stronger for lower distances). Table 1 shows the results after applying the hierarchical clustering "hclust"2 algorithm provided by the R library separately on the and matrixes. Columns represent the percentage of elements of the clusters that have a direct match with WordNet concepts (e.g. the first column indicates the percentage of clusters for which at least 10% of their elements have been identified as WordNet concepts). Rows correspond to the minimum number of elements of the cluster which have been directly linked to WordNet concepts (for instance, the last row refers to those clusters that have more than 3 elements which have been identified as WordNet concepts). The combination of a row and a column restricts the possible size of a cluster. If there are N elements in a cluster which have been found in WordNet, and the minimum required percentage of cluster elements in WordNet is P (given as a number between 0 and 100), the number of elements of the cluster must be between N and 100*N/P.

If the table results are analysed, it can be observed that in all cases the percentage of clusters that meet the requisites specified above is much bigger for the semantic analysis and, moreover, their average distances are always smaller, which means that the clusters are more compact (i.e. the inter-group homogeneity is stronger). On the other hand, the fact that the percentage of clusters obtained from C n drops quickly to very low levels (2-3%) when the minimum number of WordNet matchings is increased is due to the fact that the majority of the clusters obtained from this syntactic co-occurrence matrix are very small (from 1 to 3 elements). On the contrary, the size of the clusters obtained from the semantic similarity matrix S n is much more homogeneous, and 23-26% of the clusters still have more than 3 elements identified as WordNet concepts. Thus, the clusters obtained in this case are much more semantically meaningful and useful than those obtained in the first case, in which there is basically a very big cluster accompanied by a large number of very small and irrelevant clusters. This fact is also shown in Fig. 2 which depicts the distribution of elements per cluster in a logarithmic scale. This study has analysed two different ways of clustering the set of hashtags that appear in a given corpus of medical tweets. A classification is based on the syntactic cooccurrence of the hashtags, whereas the other one focuses on the semantic similarity between the WordNet concepts associated to the hashtags (either directly or with the support of Wikipedia categories). The results of the case study reported in this paper seem to support the initial intuition that the common syntactic-based analysis of social tags should be replaced by more complex semantically-based treatments that provide a better structure to the knowledge extracted from Web 2.0 social applications. There are several lines of work that can be pursued in the future. It is possible to think of more complex ways in which hashtags (especially those composed of multiple words) may be linked to WordNet concepts. The content of a tweet could be used to disambiguate the sense of the hashtag that it contains, if the hashtag corresponds to a WordNet synset with several senses (now this disambiguation is made in a more

Distribution of elements per cluster

Sn Cn implicit way, with the pairwise comparison of all the candidate concepts associated to the two hashtags to be compared). Concerning the similarity matrix based on cooccurrences, it could be possible to normalise it using other functions rather than the minimum (recall Eq. 2). It would also be interesting to explore similarity measures based on second-order co-occurrences (two hashtags A and B could not appear together very often in a set of tweets, but they could separately co-occur quite often with another hashtag C).

Algorithm 5 .

 5 (k, topic){ TW  getTweets(topic) TW  filterTweets(TW) Mtw  generateSimilarityMatrix(TW) Ctw  hierarchicalClustering(k, Mtw) } Algorithm used to perform the clustering of hashtags

Fig. 2 .

 2 Fig. 2. Distribution of the elements per cluster in a logarithmic scale

Table 1 .

 1 Average distances of clusters

			% cluste r e le me nts found in WordNe t
		10%	25%	33,3%		50%
		C n	Sn	Cn	Sn	Cn	Sn	Cn	Sn
	match > 1	% avg 0,25 7,1%	52,5% 0,20	7,1% 0,25	51,5% 0,20	7,1% 0,25	49,5% 0,19	7,1% 0,25	39,4% 0,18
	match > 2	% avg 0,31 3,0%	35,4% 0,21	3,0% 0,31	35,4% 0,21	3,0% 0,31	33,3% 0,21	3,0% 0,31	27,3% 0,21
	match > 3	% avg 0,37 2,0%	26,3% 0,23	2,0% 0,37	26,3% 0,23	2,0% 0,37	25,3% 0,23	2,0% 0,37	23,2% 0,23

www.symplur.com. Last access: May

th , 2013.

http://stat.ethz.ch/R-manual/R-patched/library/stats/html/hclust.html. Last access: May 24 th , 2013.

Acknowledgments

This work was partially supported by the Universitat Rovira i Virgili (pre-doctoral grant of C. Vicient, 2010BRDI-06-06) and the Spanish Government through the project DAMASK-Data Mining Algorithms with Semantic Knowledge (TIN2009-11005).


Jens Bauer
email: jbauer@cs.uni-kl.de

Achim Ebert

Oliver Kreylos

Bernd Hamann

Marking Menus for Eyes-free Interaction Using Smart Phones and Tablets

Keywords: input devices, collaborative interaction, multimodal interaction, 3D Interaction

Large displays are helpful tools for knowledge discovery applications. The increased screen real estate allows for more data to be shown at once. In some cases using virtual reality visualizations helps in creating more useful visualizations. In such settings, traditional input devices are not well-suited. They also do not scale well to multiple users, effectively limiting collaborative knowledge discovery scenarios. Smart phones and tablet computers are becoming increasingly ubiquitous and powerful, even having multi-core CPUs and dedicated Graphic Processing Units (GPUs). Given their built-in sensors they can serve as replacements for currently-used input devices, and provide novel functionality not achieved with traditional devices. Furthermore, their ubiquity ensures that they scale well to multi-user environments, where users can use their own devices. We present an application-independent way to integrate smart phones and tablets into knowledge discovery applications as input devices with additional functionality. This approach is based on Marking Menus, but extends the basic idea by employing the special capabilities of current consumer-level smart phones and tablets.

Introduction

Smart phones and tablet computers are becoming increasingly popular and powerful. Current consumer-level devices feature multi-core CPUs and dedicated GPUs. They contain multi-touch screens, GPS receivers, compasses, and accelerometers, and offer connectivity via WiFi, bluetooth, and 3G technologies. Given those capabilities, smart phones and tablets are attractive alternatives to "traditional" input devices. Smart phones and tablets offer several benefits, due to their ubiquity and added functionality compared to typical input devices.

As these devices are multi-functional and wide-spread, most users of knowledge discovery applications already own at least one, which precludes the need to buy often expensive single-purpose input devices. The same holds for multi-user environments, where each user can use his/her own device to control the system. Due to the devices' portability, they could potentially be used as (limited) "mobile memory" to transfer data between environments or as a kind of token to identify users.

Non-trivial applications typically provide the user with a moderate to large number of functions, which need to be mapped to the set of available input devices. Normally, each function is mapped to one device button, or gesture, or user interface (UI) button displayed. Problems arise when the number of required functions exceeds the number of input device buttons or gestures, or when the number of displayed UI buttons clutters the display. The touch-capable screens of current mobile devices, on the other hand, provide enough screen real estate to offer a large number of buttons and mapped functions -significantly more than practical for traditional input devices. However, the naïve approach of using mobile devices disrupts users' workflows, as they have to shift their attention back and forth between the devices' small screens and the main display environment.

We propose to utilize Marking Menus [START_REF] Kurtenbach | The limits of expert performance using hierarchic marking menus[END_REF], a radial menu structure, as a central element of a novel interaction method employing the multi-touch screen of mobile devices. The touch screen is used to show (hierarchical) radial menus as they pop up. This enables eyes-free interaction for experienced users who do not need the visual feedback from the mobile device, and leads to increased efficiency for those users, while at the same time keeping the menu structures visible should they be needed. This selection method is extended by the usage of tracking sensors, accelerometers, multi-touch and/or in-menu slider controls to provide a larger variety of interaction possibilities, which are explained in detail later in this paper.

The advantages of this design over existing interaction methods are:

-Eyes-free interaction makes complex user interaction possible without interrupting the workflow. -Auditory or haptic feedback is given to support eyes-free interaction even more. -The general approach allows application of the design to a wide array of new and existing applications. -The ubiquity of smart phones and tablets and their usability for other tasks make this approach very cost-effective. -As the system uses its own mobile screen it can replace large parts of the application's graphical user interface (GUI) up to the complete GUI in some cases.

-Support for multiple users and the system scales well to the number of users.

We present the design and implementation of our prototype. A formal user study is beyond the scope of this paper, but is planned as part of our future work. Studies by Kurtenbach et al. [START_REF] Kurtenbach | User learning and performance with marking menus[END_REF] are applicable to this interaction method and show its general usability.

Remote Interaction Using Mobile Phones

The use of mobile or smart phones as input device has been an active area of research. Ballagas et al. [START_REF] Ballagas | Sweep and Point and Shoot: Phonecambased Interactions for Large Public Displays[END_REF] presented two interaction techniques for cameraequipped phones. One uses the phone as a replacement for an optical mouse, with the physical x-y-translation of the phone mapped to a traditional cursor on the screen. At the time, the method incurred a latency of about 200 ms, too much for a practical applications; even today, high latency seems to be an issue for such approaches. This approach also does not increase the number of functions that can be mapped to a device. The second technique in the same paper is a pure selection method, where the phone detects at which object on the screen it is pointed by tracking markers displayed on the screen. These markers only appear for brief moments while the phone's camera is active to reduce display clutter. Both approaches only employ camera phones as direct mouse replacements, missing the opportunity to further improve the available interaction.

Extending that work, Jeon et al. [START_REF] Jeon | Interaction techniques in large display environments using hand-held devices[END_REF] proposed interaction techniques to replace the computer mouse with mobile phones. The movement of the phone in the air is mapped either to a cursor, or directly to an interactive object. Three approaches of calculating the relative movement of the phone are described: motion-flow, marker tracking with the marker on an selectable object, and marker tracking with a free-floating marker. While this is more refined than Ballagas' et al.'s approach, it still suffers from the same basic limitations.

A specialized approach is presented by Madhavapeddy et al. [START_REF] Madhavapeddy | Using Camera-Phones to Enhance Human-Computer Interaction[END_REF]. A cameraequipped phone is used to control a flight booking application, where the starting and destination airports are selected by pointing at them with the phone, again using on-screen tracking markers. A similar approach was used by Thelen et al. [START_REF] Thelen | A 3D Human Brain Atlas[END_REF] to interact with a 3D representation of the human brain. Here, 2D markers are rendered as part of a 3D model of the human brain, and scanning one of those markers with a smart phone displays additional information associated with that marker. Both are examples of usable designs, but have the drawback of being very specific to a certain kind of task, i. e., selection from a small number of preset targets.

Marking Menus

Kurtenbach et al. [START_REF] Kurtenbach | The limits of expert performance using hierarchic marking menus[END_REF][START_REF] Kurtenbach | User learning and performance with marking menus[END_REF] proposed and evaluated Marking Menus as an improved version of radial menus. The main difference between Marking Menus and transitional radial menus is the absence of a completely bounded target area for each menu item in the former. Radial menus simply arrange their items in a circular pattern around a center point in one or more "rings." An item is selected when the selection cursor is within the bounds of the item, and selection is usually affirmed by a button press on the input device (or any other available confirmation gesture). If the selected menu item has subitems, this causes a new radial menu to pop up at or near the current cursor position. Marking Menus only have a single ring of items, and their respective target areas expand infinitely outwards from the center of the menu in a wedge-like shape. Holding the cursor still in the selection area of an item with sub-items pops up another Marking Menu showing the sub-items, and a confirmation event (button press, or, in the original example, lifting the pen from the display surface) selects the current item. The main benefit of this menu layout and selection mechanism is eyes-free item selection, which was at the time proposed to address the high latency of pen-based direct interaction displays on then-current workstations. Using Marking Menus, users could either put the pen down on the screen, wait for the menu to appear, and select items and sub-items by drawing a stroke from the center into the (wedge-shaped) selection areas, while experienced users could just draw the chain of strokes used to reach a certain item without even waiting for the menu to pop up. (Kurtenbach called this "Expert Mode".) Since the selection areas are theoretically infinitely large, user accuracy is very high and Marking Menus are very easy to use. These assertions are backed up by Fitts' Law [START_REF] Fitts | The information capacity of the human motor system in controlling the amplitude of movement[END_REF] and Steering Law [START_REF] Accot | Beyond Fitts' law: models for trajectory-based HCI tasks[END_REF]. While the original high-latency problem Marking Menus were designed to address no longer matters, their effectiveness still does, and Marking Menus have been incorporated into many modern applications.

Pook et al. [START_REF] Pook | Control Menus : Execution and Control in a Single Interactor[END_REF] proposed Control Menus, a general improvement that also applies to Marking Menus: instead of using menus only for selections, the continued motion of an input device after an item has been selected is used to change a continuous value associated with that item. They use an example of a "zoom" menu item, where any continued input device motion after selecting that item directly alters the current zoom level. This method could also be applied to to related continuous values by using both display axes simultaneously.

Perlin's QuikWrite [START_REF] Perlin | Quikwriting: continuous stylus-based text entry[END_REF] is a stroke-based text entry method. It lays out the available character set along the edge of a rectangle (usually covering the entire screen), and divides them into eight zones (N, NE, E, etc.). A character is selected by first moving the input device from the rectangle's center into a zone, then optionally into a second zone, and finally back to the center. For example, the top-left (NW) character of the top-right (NE) zone is selected by first moving into the NE zone, then into the NW zone, and then back to the center. QuikWrite allows to enter entire phrases of text with a single, continuous stroke of the input device.

Other touch text input methods include Cirrin [START_REF] Mankoff | Cirrin: a word-level unistroke keyboard for pen input[END_REF] and T-Cube [START_REF] Venolia | T-Cube: a fast, self-disclosing pen-based alphabet[END_REF]. The former selects characters by touching them with a stylus and allows multiple selections with one single stroke, while the latter is a radial menu where the characters are arranged in multiple circles, so the direction and the length of a stroke together are responsible for character selection. Among these methods, only Quikwriting can seamlessly be used in a Marking Menu. Holzinger et al. [START_REF] Holzinger | An answer to who needs a stylus? on handwriting recognition on mobile devices[END_REF] propose to use a stylus to aid handwriting on touch surfaces. This could also be integrated into a Marking Menu.

Guimbretière and Winograd [START_REF] Guimbretiere | FlowMenu: Combining Command, Text, and Data Entry[END_REF] presented FlowMenus, a menu system designed for pens on large touch-sensitive displays. FlowMenus work like normal Marking Menus for the first selection step, but selection in submenus of any level is based on curved stroke gestures back to the submenu's center: sloped clockwise, sloped counter-clockwise, and straight, supporting only three items per submenu. The advantage of this method is that the pen always returns to the original selected position, and therefore allows direct interaction with an on-screen element at that position after an item has been selected. However, in Expert Mode, it can be difficult to return precisely to the menu center, and small deviations may add up to a point where users might accidentally select a wrong menu item. FlowMenus also allow text input directly chained into the menu using QuikWrite, and value selection similar to Control Menus. But since submenu selection strokes need to curve back to the submenu's center, values now need to be selected based on the length of the curved stroke, which is less intuitive. This also shows a subtle menu design limitation of FlowMenus: menu items for direct object interaction and for text input need to be on the center of the menu structure and thus on an even level of the submenu hierarchy, while value-selection items need to be on an odd level for the same reason.

More new menu designs based on Marking Menus emerged recently. Bailly and Lecolinet [START_REF] Bailly | Flower menus: a new type of marking menu with large menu breadth, within groups and efficient expert mode memorization[END_REF] allowed curved strokes for menu item selection, resulting in socalled "Flower Menus." Depending on the initial stroke direction, the curvature and the curve direction, i. e., clockwise or counter-clockwise, different items can be selected. While this allows a higher density of menu items per submenu level, the total time needed to draw the curved strokes is notably higher than drawing just straight lines. Using a similar, but unrelated, design to Marking Menus, Wavelet Menus [START_REF] Francone | Wavelet Menus: A Stacking Metaphor for Adapting Marking Menus to Mobile Devices[END_REF][START_REF] Francone | Wavelet menus on handheld devices: stacking metaphor for novice mode and eyes-free selection for expert mode[END_REF] are also controlled by straight strokes. The menu is radial and the menu grows in radius whenever a submenu is opened and placed on. New submenus are positioned innermost. The main difference to Marking Menus is that the user has to release the touch after each level of the submenu hierarchy and start each new stroke in the center of the screen.

A first attempt to improve Marking Menus with multi-touch was presented by Lepinski and Grossman [START_REF] Lepinski | The design and evaluation of multitouch marking menus[END_REF]. Their design uses chording gestures to invoke up to 31 different menus, based on which fingers of a hand are touching the screen. However, due to technical limitations, this approach requires the user to put down all five fingers first, and then lift a subset of fingers afterwards to invoke a menu. This is awkward, causes unnecessary delay, leads to selection mistakes if users lift fingers faster than the system can detect their gestures, and prohibits other simultaneous uses of multi-touch. In the near future these technical limitations might no longer apply to large touch sensitive surfaces, but consumer level smart phones and tablets will probably lack the feature of tracking non-touching fingers for still quite some time. [START_REF] Kin | Two-handed marking menus for multitouch devices[END_REF] studied user experience with two-handed Marking Menus. They proposed either to split the menus into parts for each hand, and let the user select items either simultaneously or sequentially, potentially increasing efficiency. Their method requires clutching with the fingers to select items deeper in the menu hierarchy as one stroke has to be completed by lifting the finger from the surface in order to access the next level of menu items, and does not allow multi-finger gestures.

Kin and Hartmann

Heidrich et al. [START_REF] Heidrich | Device-free interaction in smart domestic environments[END_REF] used an approach similar to Marking Menus to control a Smart Home. The gestures are performed on a table monitored by a Kinect and the menu is projected on the table. While the basic approach is the same as described in this paper, Heidrichet al.'s method does not allow multi-touch or value selection.

Design

Smart phones and tablets are not only usable as input devices, but also have output capabilities. When designing a user interface, one has to decide whether, and how, to use those capabilities. A device's screen, typically the primary output channel, can be used in a variety of roles: as a primary screen for a focus-andcontext displays [START_REF] Baudisch | Focus plus context screens: combining display technology with visualization techniques[END_REF]; as a full additional screen, as in Air Display3 ; to clone the environment's main display, as in remote access applications such as Remote Desktop Protocol (RDP) or Virtual Network Computing (VNC); or even not at all, as in mouse control applications such as Remote Mouse4 . One reason not to use a device's screen is that having to shift focus between multiple unrelated screens might interrupt a user's workflow.

Our approach uses touch screens for interaction feedback via radial menus similar to Marking Menus, described in Section 2.2. Kurtenbach 2.2 categorizes the usage modes of Marking Menus as Novice Mode (waiting for menus to pop up) and Expert Mode (completing interaction before or while a menu pops up). In the remainder of this paper, we refer to Expert Mode as eyes-free mode, to emphasize the fact that it does not require shifting attention away from an environment's main display.

Menu Design

A radial menu is presented to the user when they touch the screen (see Fig. 1). Its design is similar to the original Marking Menu. The menu is centered around the initial finger position, and menu items are selected as the finger enters their selection area. If the selected item has sub-items, a submenu pops up on selection (see Fig. 2). Unlike regular radial menus, the submenus have an additional wedgeshaped dead zone, i. e., a zone where no selection is made, along the line from the center of the current submenu through the center of its parent menu. This dead zone improves usability in eyes-free mode: when not looking at the screen while interacting, users run the risk of making shorter or longer finger movements than intended. To account for that, submenus initially move with the user's finger until the movement changes direction. This ensures that stroke length does not influence item selection. The wedge-shaped dead zone has the additional benefit of allowing to undo selections, as users can backtrack their strokes through multiple levels of the submenu hierarchy, including canceling menu invocation entirely. This is an extension of the original Marking Menu method. To support eyes-free interaction, the phone can provide auditory or haptic feedback whenever the user tracks back one submenu level.

To avoid unintentional selections caused by touch screen jitter, another circular dead zone has to be defined in the center of the menu. This dead zone should be as small as possible, as it defines the minimal length of a stroke to be recognized. The dead zone additionally improves selection accuracy, as the length of a stroke determines the accuracy of measuring that stroke's angle. Due to the rather coarse resolution of current-generation touch screens, a very short stroke may only be a few pixels long, resulting in inaccuracy when detecting the angle of that stroke. Thus, the size of the central dead zone is a device-and user-dependent configuration parameter.

To reduce display clutter in deep submenu hierarchies, where submenus are drawn on top of their respective parents, only the currently active submenu is drawn fully opaque, while parent submenus are drawn with increasing levels of transparency, i. e., the root menu is most transparent. Drawing the entire menu hierarchy in this way helps users to see their current position in the menu hierarchy and the direction of the most recent stroke, should they lose their place during eyes-free interaction. It also provides valuable feedback for the multitouch interaction described in Section 3.3. Fig. 2. The menu with a submenu opened up after the user moved their finger to the left. The submenu is on top of the half-transparent parent menu. Note the dead zone through in sub-menu to improve usability in eyes-free mode and to allow backtracking of selections.

Value Control

Our menu design also supports value selection similarly to Control Menus, as described in Section 2.2. Menu items with associated values are indicated by arrows (see Fig. 3). But instead of only allowing simple slider-like control over one or two dimensions, our design allows two modes of operation. In absolute mode it works like a regular slider control, reporting the absolute position of the touch(es) to the application. In relative mode, the actual location of the touch(es) are irrelevant. Instead only the changes in position are reported to the application. Absolute mode is useful for any fixed range of continues values, i. e., whenever a traditional slider control is useful. Relative mode is for situations where the absolute value of a variable is of less interest than the actual change to it. A common example for this is the position of an object. The user is normally more interested in moving the object a certain amount of units, instead of setting it to an absolute value. This relieves the application of keeping track of an absolute value (i. e., the position of the slider) that is of little interest.

For many visualization applications 1D or even 2D positioning is not enough. Employing the well-known multi-touch gestures of pinch and rotate, four degreesof-freedom (DOF) can be controlled at once (x-Direction, y-Direction, Pinch and Rotation). This allows for simultaneous two-DOF-Movement, Zoom and one-DOF-Rotation, for example, to allow the user to drill down into a part of the visualized data without having to apply a new menu selection. Alternatively multiple quantifications can be made at the same time, with each finger touching the screen functioning as a separate one-DOF slider control, theoretically allowing for a 10-DOF control. The practical limit depends on actual touchscreen size, the size of the user's fingers and the user's dexterity. Most people should be able to use four sliders simultaneously without serious problems. The control provided might be too coarse or too fine. Therefore the control itself can be scaled using the pinch gesture with a second finger (one-DOF or two-DOF controls) or a third finger (three-DOF and four-DOF). The scaling is visualized by scaling the control on the touchscreen accordingly.

Multi-touch Capabilitiy

In our method, multi-touch is not only used for value control, but also for normal menu navigation. As shown in Fig. 4, putting down another finger on the touch screen while a menu item with sub-items is selected causes the submenu for that item to detach from its parent menu, to move to the new finger's position, and subsequently to be controlled by the new finger. The parent menu sticks to the original finger, and move with it, but is otherwise be locked as long as a detached submenu is active. If, on the other hand, the currently active menu item is a value selection item, then the new finger will invoke multi-DOF value selection as described in Section 3.2. If the currently selected item is a regular menu item, then each additional finger will cause a selection event for that menu item, enabling rapid multiple selection of the same menu item by repeated tapping with an additional finger.

Detachable submenus are useful when stroke navigation through a deep menu hierarchy reaches the edge of the touch screen at any point. In that case, the user can place a second finger on the opposite side of the touch screen, and continue with menu selection normally. To prevent awkward positions, the initial finger can be released once the second finger starts interacting with the menu hierarchy. If, however, the first finger is kept held down, then only the detached part of the menu structure, and not the entire hierarchy, is dismissed after a successful selection. This enables a shortcut for multiple subsequent selections that have the same prefix in the menu hierarchy. For example, if the user wants to execute left, up, left followed by left, up, right, it will be possible to stroke left, up first, then perform left using a second finger, causing the menu at the first two parts of the stroke to be still open after the selection. With either the original or an additional touch the right stroke can be performed. A similar example is depicted in Fig. 5. Such shortcuts becomes more useful with deeper menu hierarchies. Very experienced "power users" can push the paradigm by using more than two fingers, detaching multiple submenus at the same time. With properly designed deep menu hierarchies, such expert shortcuts, while having a relatively steep learning curve, can lead to highly efficient interaction sequences.

The methods described up to this point support selection, quantification, an approximation of positioning and orientation via sequences of quantification, path via sequences of approximated position and orientation, and text when combined with QuikWrite or a comparable approach. True 3D interaction, however, requires at least 6 degrees of freedom, and single-or multi-touch gestures are not an intuitive replacement. While it is possible to chain two individual three-DOF interactions together to achieve six-DOF, this is difficult to handle for the user. Also it is only possible for two-handed interactions, and users should be able to choose one-handed vs. two-handed usage freely for themselves. Another way is to employ the smartphones build-in accelerometers to deliver the current orientation of the phone as additional information for each menu. As orientation provides three DOF (pitch, yaw and roll), seven DOF can be achieved through the combination of multi-touch quantification and orientation. Since 4 of these 7 DOFs concern rotation, a more practical limit is six DOF though. The quantification control already described can transmit the current orientation of the device as an additional 3 quantifications. This can be combined into free six-DOF-movement, for example, by letting the position of the user's touches control the x and y position, pinching of the fingers controls the z position (or zoom) and the device rotation can be transferred to the object being moved.

To support clutching (i.e., repeated swipes on the screen to control the same value) and to offer quick access to the last used function, the last invoked action can be part of the menu or can be activated by the use of multiple touches. For example a menu can be designed in a way that a single touch with a swipe to the left and then up lets the user control the position of some object. If the user is not satisfied with the object's position afterwards, a simple touch with two fingers will allow one to refine the positioning without having to swipe left and up again.

Hardware Requirements

Our design can be implemented on most current consumer-level smart phones and tablets. More specifically, target devices need to support multi-touch, need to have at least accelerometers for six-DOF interactions, and WiFi for communication. Other factors such as screen size or weight influence usability, but are not technically limiting.

Implementation

Unlike most other approaches, our proposed interaction method is neither specifically tailored towards, nor implemented in, a single application. It is designed as a toolset for application or interaction designers wanting to include smart phone or tablet-based interactions in their applications. It can be included into a program as a library or plug-in. In our test implementation it has been added to the Vrui toolkit5 [START_REF] Kreylos | Environment-Independent VR Development[END_REF] as a third party plug-in for and it can easily be included in any Vrui-based VR application.

Mobile Device

The prototype device-side application was developed in Objective-C for an Apple iPhone 4S and an iPad 2 (See [START_REF] Holzinger | Making apps useable on multiple different mobile platforms: On interoperability for business application development on smartphones[END_REF] for potential problems when porting this to other platforms).

The device-side application implements the client component of the distributed architecture. On startup, it connects to an application-side server, found either via Service Discovery, or a manually entered host name. Upon connection, the client receives the application's menu structure and builds the menu's visual representation. If the application side requests orientation measurements, the client sends streaming orientation data at the maximal rate of 30 Hz to minimze lag. User interface events such as selection or quantification are reported asynchronously as they happen.

Extension Possibilities

The communication protocol is extensible and can be tailored toward a specific application should the need arise. Extensions are simple to implement on both sides and can make use of the already implemented features.

Conclusions

We have presented our eyes-free interaction method using consumer level smart phones and tablets. This method can be used effectively with applications for knowledge discovery and employs multi-touch and the phones sensors to allow full 3D interaction. Being eyes-free users can interact without interrupting their workflow to look at the input device. With its simple consistent design it can replace traditional menus and even whole dialog boxes. Our method is application-independent and can be used in other environments (e.g., Desktop) as well. Applications do not have to be altered to make use of this approach, but the prototype can be customized to include application-specific behavior.

A possible extension is device-based authentication. Devices can send public keys to the server on connection. Instead of a passphrase, the menu can be used to enter a combination of strokes serving as a password (similar to YAGP [START_REF] Gao | YAGP: Yet Another Graphical Password Strategy[END_REF]). To prevent password sniffing, the communication can be encrypted using Transport Layer Security (TLS). The whole concept is also transferable to other application domains. When a multi-touch trackpad is available (as with most Macintosh computers) the menu can be controlled the same way. Unfortunately, the use of sensors to control rotation is then no longer possible.

The paradigm of our design is usable for a number of other application areas as well, such as desktop computers, tv sets, etc.

We plan do devise and perform a user study for our system, considering multiple applications and users from various disciplinary backgrounds (i.e., users applying out system to their domain-specific problems).

Fig. 1 .

 1 Fig.1. The general design of the menu, in this example for four menu items, all with a descriptive name and an icon.

Fig. 3 .

 3 Fig. 3. An arrow shows up when the selected submenu supports direct value selection, just like a regular slider.

Fig. 4 .

 4 Fig. 4. Multi-Touch enabled navigation allows the user to detach a submenu and control it with another finger while the original menu still sticks to the old touch.

Fig. 5 .

 5 Fig. 5. Using detached menus as shortcut: The index finger touches the surface and is swept up (1). The middle finger swipes down causing the submenu to detach and toggle the auto-rotate function (2). The middle finger touches the surface another time, swiping up to activate the transparency settings (3).

http://www.avatron.com

http://www.remotemouse.net/

http://idav.ucdavis.edu/ okreylos/ResDev/Vrui


Chandan Kumar
email: chandan.kumar@uni-oldenburg.de

Wilko Heuten
email: wilko.heuten@offis.de

Susanne Boll
email: susanne.boll@uni-oldenburg.de

Visualization Support for Multi-Criteria Decision Making in Geographic Information Retrieval

Keywords: Local Search, Geographic Information Retrieval, Geovisualization, User Interfaces, User-Centered Design, Heatmaps, Grids, Voronoi diagram

The goal of geographic information retrieval (GIR) is to provide information about geo-entities to end-users and assist their spatial decision making. In the current means of GIR interfaces, users could easily visualize the geo-entities of interest on a map interface via sequential querying or browsing of individual categories. However, there are several decision making scenarios when the user needs to explore and investigate the geospatial database with multiple criteria of interests, which is not well supported by the sequential querying or browsing functionality of current GIR interfaces. There is a need for more sophisticated visual interfaces to enable end-users in discovering knowledge hidden in multidimensional geospatial databases. In this paper we discuss some of the HCI issues in realizing such multi-criteria decision making scenario based on the user requirement analysis. To tackle the human centered aspects we propose different heatmap based interfaces to support multi-criteria visualizations in GIR, i.e., to facilitate the knowledge based exploration of geospatial databases with less information overload.

Introduction

Geo-related information is one of the basic needs of citizens to understand the local infrastructure and to satisfy their spatial information requirements [START_REF] Ahlers | Location-based Web search[END_REF]. Spatial databases of georeferenced entities, documents and Web pages are a huge information source for geographic locations and entities. A GIR system supports end-users to search into these spatial databases [START_REF] Kumar | Relevance and ranking in geographic information retrieval[END_REF], its goal is to process the information request of end-users and provide the results to satisfy their spatial information need. The current GIR interfaces are able to serve comparably simple requests, e.g., a search for "Restaurant in New York " in Google Maps 3 will return all restaurants in the downtown New York. However, in the current information age, the spatial information need of an end-user is often much more complex than such simple, aforementioned queries.

In several scenarios of spatial decision making users look for multiple criteria of interest simultaneously, which is not very convenient with the sequential querying and categorization approach of current GIR interfaces, e.g., somebody who has to move to a new city and is looking for a new living place. In this example the user will most likely come up with a variety of different criteria of geo-entities that he/she would like to visualize it together, e.g., availability of shopping facilities, medical facilities, and a good connection to public transport. Existing GIR systems fail to satisfy such complex information needs of end-users, even though the associated geospatial databases contain all these multi-dimensional information. The need is to support geographic retrieval with appropriate visualization methods that could assist users to explore the geospatial databases more effectively to discover the hidden spatial knowledge.

In this paper we argue the need of visualization methods for GIR to assist the complex decision making task of end-users. We conducted a user study to understand the requirements of end-users for GIR decision support systems, where we presented some spatial decision making scenarios such as moving to a new region or city. The insights of our study motivated us to design different interfaces which can support users in visualizing multiple criteria on the map with less information overload. We primarily focus on the heatmap visualizations (which have been simple yet effective phenomena in visualization research [START_REF] Maceachren | Animated maps of aggregate data: Conceptual and practical[END_REF][START_REF] Fisher | Hotmap: Looking at geographic attention[END_REF] for the information representation with less overload), and proposed various GIR interfaces using aggregated computations of geo-entities with grid-based and voronoi divisions. The proposed interfaces operate with the effective visualizations to enhance the capability of geospatial database in providing useful knowledge about spatial regions, and assist end-users decision making task.

The rest of paper is organized as follows: First, we give an overview of the multi-criteria local search problem and discuss the related applications and research approaches in Section 2. Then in Section 3 we describe our user study which was conducted to characterize multi-criteria search over various scenarios of exploring urban regions. We propose our heatmap based visual interface for multi-criteria local search in Section 4. In this section we describe how grid-based and voronoi-divisions were employed to present the aggregated spatial information. Finally, Section 5 concludes the paper by discussing the contribution of the paper and directions for future work.

Background and Related Work

Geographic information retrieval or local search provides the information about geo-entities to end-users [START_REF] Ahlers | Location-based Web search[END_REF][START_REF] Kumar | Relevance and ranking in geographic information retrieval[END_REF]. These geo-entities usually belong to a criteria/category or set of categories (shopping, education, sport, etc.). Several locationbased services and yellowpages follow the categorical structure for the overview of geo-entities. In the current geo applications, users could view the geo-entities which belong to a particular category on the map, but realization of multiple categories is usually not supported. So end-users are expected to accomplish decision making task through sequential querying/browsing of categories which could be extremely complex and time consuming task. There are a few commercial applications 4,5 which provide the end-user interface of few selected categories for a very specific task like hotel or apartment search. In comparison we focus on the generic local search for end-users, and to support their decision making through visualization of multiple categories on a map interface.

In the research community, multi-criteria spatial problems have been approached from the computation perspective [START_REF] Makropoulos | Spatial ordered weighted averaging: incorporating spatially variable attitude towards risk in spatial multi-criteria decision-making[END_REF][START_REF] Rinner | Personalized multi-criteria decision strategies in location-based decision support[END_REF] which is focused on distance and density estimation of locations with respect to different criteria. In comparison, we focus on visualization methods, i.e., how end-users perceive and analyze multiple criteria on local search interface for spatial decision making. Some geovisualization approaches [START_REF] Dykes | Exploring Geovisualization. International Cartographic Association Series[END_REF][START_REF] Greene | GIS-based multiple-criteria decision analysis[END_REF] explore the problem of multi-criteria analysis, but they usually target specific domains like healthcare and support the decision analysis of a focused group of experts. Rinner and Heppleston [START_REF] Rinner | The spatial dimensions of multi-criteria evaluation -case study of a home buyer's spatial decision support system[END_REF] proposed geospatial multi-criteria evaluation for home buyers where decision criteria were based on: location, proximity, and direction. Even though their task has been guided by a similar scenario of spatial decision making like discussed in our work, the study was conducted for a focused group of real-estate agents and the contribution was more on the computation issues rather than the HCI and visualization aspects. In general geospatial decision making has been one of the main challenges and application of visual analytics [START_REF] Keim | Mastering The Information Age -Solving Problems with Visual Analytics[END_REF]. For geo-related content visual analytics is prominently being used. There have been many visual analytical models and tools developed to support critical business decision making processes, but assisting lay users in their decision making is still a major research challenge.

In this paper we focus on the analysis of GIR visual interfaces with endusers. The research problem of user-centered analysis have been well investigated in visualization and human-computer interaction research [START_REF] Moere | Evaluating the effect of style in information visualizations[END_REF][START_REF] Lam | Empirical studies in information visualization: Seven scenarios[END_REF][START_REF] Maguire | Methods to support human-centred design[END_REF], also in the spatial context of geovisualization [START_REF] Lloyd | Evaluating human-centered approaches for geovisualization[END_REF][START_REF] Nivala | User-centred design and development of a mobile map service[END_REF]. Even though we follow the general guidelines from the aforementioned work, we particularly focus on the usability and end-user satisfaction of a heatmap based visualizations. It is common to use heatmaps, grid structure, and voronoi divisions, in many visualization approaches, but their impacts on the GIR interfaces to support user's multi-criteria decision making have not been explored before.

In this work we particularly augment the interfaces of our existing GIR system whose goal is to provide the access of geo-entities through spatial Web pages. Figure 1 shows the end-user interface of system which is very similar to the current local search services, i.e., markers on the map to show the geo-entities, and an associated ordered list of results. The associated geospatial database consist a huge collection of georeferenced Web pages through a focused Web crawler [START_REF] Ahlers | Adaptive Geospatially Focused Crawling[END_REF]. Identification and verification of the addresses are done against the street Fig. 1. A screenshot of our early GIR interface name database, which we fetched from OpenStreetMap6 for the major cities of Germany. The system is primarily focused on relevance algorithms and computational ranking solutions [START_REF] Kumar | Relevance and ranking in geographic information retrieval[END_REF][START_REF] Ahlers | Retrieving Address-based Locations from the Web[END_REF] to process user requests and listing result documents in a ranked order.

User requirement analysis in complex spatial decision scenarios

The role of end-user is of prime importance in the successful design of Web interfaces, so the usability and HCI aspects need to be considered [START_REF] Holzinger | Usability engineering methods for software developers[END_REF][START_REF] Maguire | Methods to support human-centred design[END_REF]. We follow the generic guidelines of user-centered design process to understand the context of use and to gather requirements. We conducted a semi-structured interview, where we asked people about experiences with existing systems, gathered insights, desires and ideas for improvements regarding GIR decision making tasks.

Ten users participated in our study. The participants were aged between 33 (mean) and 5.6 (standard deviation). We asked the participants to think about how it feels to move to a different city. We thereby hoped that the participants can provide us with more thoughtful, inspiring information. Initially, we asked each participant to name the important criteria and aspects if they would like to move to a different city, or to open up a business in a city, or to compare different cities. Then we asked each participant on how an ideal user interface for these scenarios could look like. Thereby, also non-stationary devices could be considered. Participants were allowed to draw sketches with pen and paper. We then asked them to reflect on how they use existing tools, like Google Maps, the GIR interface (Figure 1), for these scenarios and if they fulfill their needs. Ultimately, we confronted the participants with an early functional prototype of our GIR interface for multi-criteria search (Figure 2) and asked them to share their thoughts by thinking aloud. The prototype is the easy adaption of the existing GIR interface to overcome the limitation of sequential querying and browsing. It supports multi-criteria selection through the colored association of markers on map. Each marker (circle) represents a geo-entity and follows the color scheme of its respected category.

We obtained the general perception that the user's requirements could be very diverse and dynamic. All study participants had their very own criteria in mind when discussing about the scenario, some criteria were contradictory, e.g., one participant wants to live as close as possible to work, while another participant wants to live as far away from work as possible to have a clear separation. Most of the participants stated that existing tools and services are not sufficient to fulfill these tasks in a simple and easy way. The current means of interfaces support only the sequential querying and searching of geo-entites, so the exploration with respect to multiple criteria of interests becomes an uneasy task. Few participants mentioned that they could achieve the task via several sequential queries. Moreover, they supported our point of view that this decision making process is very complex and the way to merge information in mind is demanding. Simplification in the information presentation, categorical and aggregated overview, easy and adaptive interaction were the main wishes of the users, we discuss these observations more specifically in the following.

Simplification of Information presentation: Most of the users wished for easy and simple visualizations while being asked about their need in realizing an ideal geospatial decision support system. Participants were concerned from the overload of information from existing interfaces and the complexity of representation. The geospatial databases contain multivariate and complex attributes so the need is to summarize this huge information via easy visualizations. In order to support simple visualization, advance interaction methods could be useful to provide exploration capabilities to end user, i.e., to reduce the information loss.

Visualization at category level is important: We noticed that users tend to visualize the geo attribute at low granularity. While being asked to list the important geo attributes for relocation, users mention the geo-relevance parameters with a categorical overview, e.g. shopping, sports, education etc. The usual geo-data available to search systems are at the high granularity with real physical addresses of local entities. So the need is to represent the geovisualization of spatial database with low level category based details to simplify the initial visualization for end users.

Aggregation of information and knowledge-based support:

In the scenarios such as geovisualization, integration of geo-spatial knowledge, learning of geo-spatially related entities in the search and visualization is required. There is a greater need of visual analysis tools to represent and reason with human knowledge and formalize the intersection between interaction and knowledge construction. From the user study we got the impression that the user is very willing to support these knowledge-based interfaces. In many of the drawn sketches we identified principles to assist such interfaces. Most prominently, the users wanted to set their general priorities and interests on some scales. These could serve as a starting point for building up more detailed knowledge-based interfaces. As open challenge we see how the user's set preferences and intelligent interface support work together, in particular since the user's interests might change over time or for each session.

Adaptive interaction techniques: Interfaces of spatial data usually demands interaction patterns like zooming, panning, rotating or selecting. The challenge is to provide users the scope to utilize these techniques to navigate the map and, thus, the geographic search results. The user should be able to mark areas, move to other areas, and manipulates the retrieved attributes till he/she reaches a deep understanding of the data and potentially gathers new knowledge. From the user study we got strong support that interaction techniques beyond traditional WIMP (windows, icons, menus, pointer) interfaces should be considered. We learned that the context is often completely different between users. It might be even different in various situations of the same user. E.g., the user's individual interaction flow might be different to the flow when the interests of a whole family are considered. These different profiles are very hard to infer from a technical Fig. 3. Grid-based heatmap visualization for spatial exploration point of view. However, the participants appreciated the different user profiles of the shown prototype (Figure 2). Thus, this is a significant challenge that needs to be addressed.

Visualizations to support multi-criteria decision making in GIR

Based on the gathered insights we are able to make some fundamental design decisions. We know that people will approach a spatial decision making task, like in the relocation scenario, with a map-based tool. Consequently, we decide that the main part of the user interface should be a map. This map should exactly behave like traditional map-based systems to match the user expectations regarding common interactions like zooming or panning. The user interface should use a simple language, should be easy to understand, should be clearly structured and further should avoid information overload. A trade-off was deemed optimal for the criteria selection process. The users should be allowed to adapt the criteria to their very individual needs. The user preferred criteria gathered in the requirement analysis guided our formulation of the list of category. Our primary goal is to provide an appropriate visualization of the spatial data for GIR users. In visualization research, there have been many advance multivariate, high dimensional visualizations for analysts and decision makers which could be hard to interpret by lay users. Here we imply the heatmap based information presentation phenomena in the GIR interface, which is easily understandable and less prone to information overload. Heatmap visualization has been applied in various domains to represent spatial distributions and relevance [START_REF] Fisher | Hotmap: Looking at geographic attention[END_REF].

Grid-based heatmap visualization for spatial exploration

For the aggregational view of geo-entities we discretize the map area using a grid raster [START_REF] Maceachren | Animated maps of aggregate data: Conceptual and practical[END_REF], since we didn't intend to restrict user exploration to be constrained by administrative boundaries. We adapted the heatmap visualization for the distribution of categories across user-defined grid-based division of maps. Each grid cell conveys the categorical information. The color of each grid cell represents the category of largest allocation of geo-entities in the cell area. Figure 3 shows the grid-based visualization for two user selected cities with respect to 6 selected categories of interest. We can perceive that the visualization gives a good overview and assessment on the distribution of geo located facilities across the region and cities, e.g., to identify the regions with better shopping facilities in the city. Relevance based aggregation : Sometimes users need to rank the regions with respect to their criteria of interest, e.g., to find the best place to live or to open a business. We therefore employed a basic multi-criteria aggregation [START_REF] Rinner | The spatial dimensions of multi-criteria evaluation -case study of a home buyer's spatial decision support system[END_REF] to provide a spatially-related aggregated view on entity distribution with regard to multiple categories. Figure 4 shows the aggregated ranked version of the grid-based visualization. Here each grid cell represents the overall relevance with respect to user selected categories. The relevance score is computed based on the quantity and balanced distribution of geo-entities which belongs to the criteria of interests. The relevance of each grid cell G is based upon user selected category allocation (C 1 , C 2 , .., C n ), where each category C i has an importance based on the geo-entities which belong to category i. The relevance of a particular cell G is computed with the combined distribution of categories selected by user. We used a color scheme of six different green tones which differed in their transparency. While light colors represented low relevance, dark colors were used in order to indicate high relevance. The color scheme was chosen with the support of ColorBrewer7 ; an online color scheme recommendation tool based on the work of Brewer and Harrower [START_REF] Harrower | .org: An online tool for selecting color schemes for maps[END_REF].

For the end-user interaction with grid and categories, we show the relevance of a grid with respect to selected categories using a pie chart (Figure 5). The pie charts provide the detailed information on categorical distribution of grid cells when the users click on a particular grid cell with mouse cursor.

Voronoi-based heatmap visualization for user-constrained spatial exploration

The aforementioned grid-based visualization divides the spatial regions in automated fix sized spaces, i.e. the end-user does not have the possibility of specifying personal location preferences as input. The user study also indicated the need of users in preselecting the desired locations and then compares them with respect to their criteria of interest. Figure 6 shows our transformation of heatmap visualization to a voronoi-based division to fulfill such requirement. Voronoi diagram [START_REF] Aurenhammer | Voronoi diagrams: a survey of a fundamental geometric data structure[END_REF] is a way of dividing space into a number of regions. A set of points (seeds) is specified beforehand and for each seed there will be a corresponding region consisting of all points closer to that seed than to any other. The regions are called voronoi cells. The color of each voronoi cell represents the category of largest allocation of geo-entities in the cell area. Similar to the aggregated view of relevance in grid-based visualization, Figure 7 shows the ranked voronoi-based divisions. Here the relevance of a particular voronoi cell is computed not only based on the distribution of geo-entities; it's additionally the accumulation of root distance of the geo-entities from the selected home location. Figure 8 shows the distribution of geo-entities across the selected locations of city Leipzig with respect to categories: shopping, education and medical facilities. We could see that most relevant region (voronoi cell with the darkest green shade) has the better distribution of geo-entities and the corresponding home location is closely connected to the geo-entities of interest.

Conclusion and Future Work

Exploration of multiple criteria for location-based decision making is a common scenario of our daily life, but the current means of local search interface does not offer adequate support for such task. This was also evident from our study when the participant reported on the incapability of Google maps and given GIR interface to accomplish the task of exploring city with multiple criteria. In this paper we argue the need of interactive visual interfaces for a geographic information retrieval system, so the end-user can easily explore and interact with the spatial database. We presented an extension of current interfaces (with multiple placing of markers) to perform multi-criteria search. But the huge amount of markers presented in the marker condition carry the information overload and put high mental demand to perform the task of exploration and comparison of spatial regions. We proposed the use of heatmap visualization through grid and voronoi-based conditions to facilitate the knowledge based exploration of geospatial databases with less information overload. The proposed visualizations has been used in many of visualization research prototypes, but the acceptability of such heatmap based visualization has not been studied in the context of geographic information retrieval for lay users.

Most of the users who participated in the preliminary study were constantly involved in the design and assessment of the interfaces described in this work, still the comparative study of proposed interfaces is essential. In future we plan the extensive qualitative and quantitative evaluation of these interfaces, to conclude the acceptability of these visualizations with regard to user-centered aspects such as exploration ability, information overload and cognitive demand. The methodology discussed by Longo et al. [START_REF] Longo | The importance of human mental workload in web design[END_REF][START_REF] Longo | A novel methodology for evaluating user interfaces in health care[END_REF] would be a guideline to evaluate the proposed interfaces, and to judge the human mental workload in web-design imposed by different interfaces. We would also like to investigate more advanced interaction methods to enhance the usability of proposed visualizations.

Fig. 2 .

 2 Fig. 2. Marker-based interface for multi-criteria exploration

Fig. 4 .Fig. 5 .

 45 Fig. 4. Ranked grid-based visualization

Fig. 6 .

 6 Fig. 6. Voronoi-based heatmap visualization

Fig. 7 .

 7 Fig. 7. Aggregated voronoi-based visualization.

Fig. 8 .

 8 Fig. 8. Aggregated voronoi-based visualization with distribution of geo-entities

http://www.maps.google.com

http://www.hipmunk.com/hotels/

http://www.walksore.com/apartments/

http://www.openstreetmap.org/

ColorBrewer: http://www.colorbrewer.org

http://www.visualanalytics.de

Acknowledgments

The authors are grateful to the DFG SPP priority program 8 which funds the project UrbanExplorer.