DEIM Forum 2016 C5-5

Clustering Tweets Containing Ambiguous Named Entities Based on the
Co-occurrence of Characteristic Terms
Maike ERDMANN, Gen HATTORI, Kazunori MATSUMOTO, and Yasuhiro TAKISHIMA††KDDI R&D Laboratories, Inc. 2-1-15 Ohara, Fujimino, Saitama, 356-8502 Japan
E-mail: †(ma-erdmann, gen, matsu, takisima) @kddilabs.jp
Abstract Social media platforms such as Twitter are an invaluable source of information. However, one of the problems
that arise when analyzing Twitter messages is the ambiguity of many named entities. Named entity disambiguation is usually
performed by comparing the text surrounding the occurrence of the ambiguous term to the text in a knowledge base such as
Wikipedia. However, texts published via social media are usually very short and written in an informal way, thus the overlap ofterms is too small for accurate entity matching. Apart from that, the usage of a term in social media can differ greatly from theentities represented in the knowledge base. Therefore, we propose an unsupervised and domain independent tweet clustering
method based on co-occurring terms in the tweets. Our method extracts characteristic keywords for a named entity from thetweets and adds terms proposed by Google Autocomplete. Then, it clusters all keywords according to the entity they represent
and assigns one of the keyword categories to each tweet. In an experiment with ambiguous company names, car names and TV
show titles, our proposed method achieved both a higher precision and a higher recall than two named entity disambiguation
methods matching named entities in the tweets to corresponding Wikipedia entities.
Keywords Keyword extraction, text clustering, social media analysis
propose an unsupervised tweet clustering method based on

1. Introduction
Socialmedia

platforms

such

as

Twitterareanco-occurring terms in the tweets. Our method extracts

invaluable source of information for understanding whatcharacteristic

people think about various topics such as prod ucts andambiguous named entity as well as terms proposed bycompanies, celebrities or news and events. Unfortunately,

Google Autocomplete, an API that provides a list of

many named entities are ambiguous. The company nameautocomplete suggestions for a search term. For the term

“Apple”, for instance, is also the name of a fruit. The term

“Apple”, for instance, terms such as “iPhone”, “iOS”, “pie”“Golf” can be the name of a car or the name of a sport.

or “cinnamon” can be extracted.

Therefore, it is necessary to distinguish the different

keywords

fromtweetscontaininganAfter that, the proposed method clusters all keywords
according to the entity they represent and assigns themeanings of a named entity.
Named entity disambiguation is usually performed b y

tweets to one of the keyword categories. Our method cancomparing the text surrounding the occurrence of thebe applied to any kind of named entity, such as product,

ambiguous term to the text in a knowledge base such ascompany, person or location names. We will describe an

Wikipedia. However, texts published via social media areexperiment that we have conducted to compare theusually very short and written in an informal way. Thisaccuracy of our proposed method to DBPedia Spotlight 1

leads to a small overlap of terms, making accurate entityand AIDA 2 , both popular tools for matching name dmatching difficult. Apart from that, the usage of a term inentities in texts to corresponding Wikipedia articles.

socialmedia

candiffergreatly

fromtheentities

represented in the knowledge base. For instance, there are

2. Related Work

45 Wikipedia articles related to the term “Apple”. Most of

A lot of research has been conducted on named entit ythose meanings, such as the “Apple River” or the annual

disambiguation (NED) [2]. Many recent approaches try tofootball match “Apple Cup”, are rarely discussed in social

match

media. On the other hand, meanings that are commonl yknowledge bases such as Wikipedia [3]. Two popular

discussed in social media are sometimes not listed in

implementations of such a s ystem are DBPedia Spotlight

Wikipedia, particularly the general meaning of a term. Lin[4] and AIDA [5]. However, most existing research aims at

et al. [1] report that when they tried to assign Wikipedia

named entity disambiguation of much longer texts thanambiguous

namedentitieswitharticles to entity mentions on the Internet, no suitable
article could be found for one third of the entities.
Instead of performing named entity disambiguation, we

1
2

http://spotlight.dbpedia.org
https://gate.d5.mpi -inf.mpg.de/webaida/

entitiesinconsists of three steps, visualized in Figu re 1, which wewill describe in the following subsections.

3.1. Keyword extraction
In the first step, characteristic keywords are extracted
from all tweets containing the ambiguous named entity.
Since the tweets are not disambiguated, the keywords ofdifferent meanings are mixed up (e.g. “iPhone” and“cinnamon” for “Apple” are not separated) and thus needFig.1. System Overview

to be clustered based on which meaning they represent.
Unfortunately, the meanings of the named entity arethose published on social media platforms.

usually not represented equally in the tweets. The majority

Named entity disambiguation has also been performedof tweets containing the term “Apple”, for instance, areon Twitter, which is much more challenging, since tweets

about the company Apple. Because of that, keywords ofare short and informal, making it difficult to categorize

minority meanings are underrepresented in the keyword

them

Severallists, making proper categorization difficult. If we decideapproaches have been proposed to disambiguate specificthroughword

overlap

calculation.

to extract more keywords to ensure each meaning is

types of named entities, such as company names [6][7][8],covered appropriately, we face the problem that theperson names [9] or TV show titles [10][11]. Depending

quality of the keywords will decrease drastically.

on the domain, various external resources such as

In order to solve that problem, we decided to collect

Wikipedia articles, compan y Web sites or electronic TV

keywords using two different methods, which we will

program guides are used for determining characteristic

introduce in the following, as well as a combination of

keywords.

both methods.

Habib van Keulen [12] proposed a general named entit y

The first method is a modified version of the tf -id f

disambiguation method for Twitter that uses the Yago

algorithm. At first, the top x keywords (e.g. top 10) are

knowledge base consisting of entries from Wikipedia,

extracted from all tweets using tf -idf and added to a

WordNet and GeoNames. In addition, they crawl Web

keyword repository. Then, all tweets c ontaining the top y

pages representing the entities by using the Google search

keywords with y ≤ x (e.g. top 1) are deleted from theengine. Then, they assign the named entities to both

corpus of collected tweets, before collecting the next set

Wikipedia articles and Web pages, but their experimentof top x keywords. The reason for deleting the tweets isindicates that using only Wikipedia articles achieves thethat one of the entities in the tweets is usually dominant

best results.

and keywords of this entity are overrepresented. Therefore,

Insteadofweproposeandeleting all tweets

independent

methodforemphasizes the tweets of minority entities and help ensure

clustering tweets according to the meaning of thethat all entities are represented by a sufficient number ofcontained named entity. The method uses information on

keywords. In the case of “Apple”, the top keyword

co-occurring terms and is therefore is suitable for any typeextracted from the collected tweets by tf -idf was “iPhone”.

of named entity. Besides, it does not depend on a manually

By removing allcompiled knowledge base, since those do not sufficiently

percentage of tweets about the fruit increases, making it

represent all meanings of an ambiguous term in social

more likely to extract keywords representing them inmedia.

subsequent keyword sets. The keyword collection process

unsupervised

performing
anddomainNED,

containing the top

tweetscontaining thaty keywords

term,

the

is repeated until enough keywords have been collected

3. Clustering

TweetsUsing

Co-occurring

Keywords(e.g. 100 keywords).
The second method collects keywords from Google

In this section, we will introduce an unsupervised

Autocomplete rather than analyzing the terms contained inmethod for clustering tweets of short and informal text

tweets. Google has published an API tha t provides a list ofsuch as Twitter messages, which does not depend on a

autocomplete suggestions for a term, consisting of words

manually created external knowledge base. Our methodthat frequently co-occur in search queries.

We selectedCompanies
Amazon, Apple,
Citizen, Coach,
Converse, Fox,
Jaguar, Sharp,
Subwa yTable 1. Test terms
Cars
TV shows
Civic, Escape,Arrow, Castle,
Explorer,
Empire, Nashville,
Focus, Golf,
Perception, Reign,Legacy, Pilot,
Revenge, Scandal,
Polo, Soul
Suits

Google Autocomplete keywords, because Web search
queries usually correspond to terms that appear in tweet
texts much more than entities in a knowledge base.
When combining both methods, the keywords extracted
by the modified tf-idf algorithm and the keywords
extracted from Google Autocomplete are simply merged.

experiment with 27 named entities in the categories
companies, cars and TV shows. For each category, we
selected 9 popular ambiguous named entities. The test
terms are listed in Table 1. For the company category, weused terms from the WePS -3 workshop [14]. For the car
category, we selected ambiguous terms from Web sites thatrank cars by popularity. For the TV show category, we
chose the most popular, currently running TV shows listed
on an online TV program guide. After compiling a list of
ambiguous terms for each category, we started to extract
tweets for them and selected the 9 terms for which thelargest number of tweets could be collected over a periodof three weeks. On average, about 1 million tweets werecollected per test term. Besides, we ensured that at least

3.2. Keyword clustering
In order to cluster the ke ywords based o n their meaning,

100,000 tweets were collected for each of the terms.

we estimate the semantic similarity of the keywords toeach other. For each pair of keywords k i and k j extracted
for an ambiguous term, the number of tweets containing
both k i and k j is calculated (co-occurrence score). The idea
behind this method is that similar keywords frequently
co-occur in tweets whereas different keywords co -occur
less frequently (e.g. “iPhone” and “iOS” co-occur much
more frequently than “cinnamon” and “iOS”). Aftercalculating the co-occurrence score of each keyword pair,the keywords are clustered based on these scores. In orderto do that, the ke ywords are represented as nodes of agraph and the co-occurrence as weighted edges connecting
two nodes, then the edge weight is set according to theco-occurrence score. A graph clustering algorithm such as
CNM

[13]

can

be

used

to

clusterthekeywords

automatically. Each cluster in the graph represents one
meaning of the named entity.

5.1. Keyword extraction and categorization
In the first part of the experiment, we extracted
keyword sets by four different methods and compared theresults.
Tf-idf
The keywords in this method are extracted using thestandard tf-idf algorithm.
Modified tf-idf
In this method, the tf-idf algorithm is modified
according to the algorithm des cribed in Section 3.1.
Google Autocomplete (GA)
Only the keywords collected through the Google
Autocomplete API are used.
Modified tf-idf + Google Autocomplete (GA)The keywords extracted by the modified tf -idf algorith m
are merged with the keywords collected from Google
Autocomplete.

4. Tweet clustering
After all keywords have been assigned to a category, thetweets containing those keywords are assigned to the
keyword categories. However, if a tweet contains multiple
keywords of different clusters, it cannot be clustered.
After all tweets containing characteristic keywords havebeen processed, it is possible to cluster tweet s that containno or conflicting ke ywords based on their similarity to thetweets that are already clustered. However, this last step is
not described in this paper.

For tf-idf and modified tf-idf, we extracted the 100 top
ranked keywords. The global document set for calculating
the inverse document frequency consisted of a large set of
randomly collected tweets. The Google Autocomplete AP I
suggests 10 keywords for each letter of the alphabet andeach number from 0 to 9. We onl y used the keywords foreach letter of the alphabet, resulting in 260 ke ywords. We
created a keyword co-occurrence graph according to themethod described in Section 3.2, but disregarded all
keywords that did not appear in the tweets or did not
co-occur with any other keywords. Then, we clustered all
keywords using the CNM algorithm [13] and deleted all

5. Experimental Results
In order to show that our proposed method works fordifferent kinds of named entities, we conducted an

categories to which fewer than 10 keywords had been
assigned.

Fig. 2. Tweet clustering example (Apple)
Table 2. Keyword clustering results
Companies Cars
TV shows
number of terms
999
correctly clusteredtf-idf
3
3
2
GA
3
3
2
modified tf-idf
6
4
4
modified tf-idf + GA 8
4
6cluster and the meaning of each cluster had to be clear forthe judge when seeing the top ranked ke ywords assigned
to the cluster. The clustering was considered to be
unsuccessful if either the cluster for an important entity
was missing or the entity represented by a cluster could
not be recognized from the keywords (e.g. man y unknownor mislabeled keywords). The major entities for each term

Figure 2 shows an example of a cluster structure which
was constructed for the term “Apple” and visualized with

were manually defined after manually analyzing 100
sample tweets per term prior to the experiment.

the Harel-Koren Fast Multiscale layout algorithm. The

As expected, standard tf-idf did not perform well, sincegraph is divided into one cluster representing the company

minority meanings were not represented in the keywords(dark blue nodes) and another cluster representing theforfruit (light blue nodes).

Autocomplete also did not perform well, facing the same

most

terms

used

in

the

experiment.

GoogleAs shown in the graph, not all keywords have been

problem as tf-idf. Slightly better results were achieved

assigned to the correct category. The ke ywords “watch”

with our modified version of tf-idf, since the methodand “siri” have accidentally been placed in the fruit

ensures more diverse keywords. The best clustering

category, even though they are company related. The

performance was achieved b y combining keywords from

keyword “adam's” should be placed in none of the two

modified tf-idf and Google Autocomplete. Comparing bothcategories. And for other keywords (e.g. “china” andkeyword sets, we realized that the keywords extracted by“march”), it is unclear whether the category assignment

Googlemakes sense without further examination of the tweets.

meaning than the ones extracted from modified tf -idf. For

However,

the term “Coach”, for instance, the keywords extractedthemajorityof

keywords

wasclusteredcorrectly.

Autocomplete

oftenemphasizedadifferent

from Google Autocomplete were mostly company related,

We clustered all 27 test terms shown in Table 1 andwhile the keywords extracted from tweets using m odified

manually evaluated the categories for each term. T he

tf-idf carried the meaning of the term in the sports domain.

numbers of terms for which ke yword clustering was

For that reason, Google Autocomplete keywords are useful

successful are shown in Table 2. In order to consider theto complement underrepresented keyword meanings. Only

keyword clustering of a term to be successful, each major

for the car domain, the keywords for less than half of theentity of the term had to be represented in a separate

test terms could be clustered successfully. This is because

wasTable 3. Tweet clustering results
Companies

categories
precisionreca llf-mea surecategories
precisionreca llf-mea surecategories
precisionreca llf-mea sure

AIDA

DBPedia
Spotlight

m.tf-idf
+GA

4.25
65.33
11.75
0.20
28.78
61.08
50.94
0.56
2.56
68.69
54.64
0.61

Cars

TV
shows

Ave rage

0.67
100.0
0.89
0.02
30.67
50.18
31.09
0.38
3.33
51.77
53.10
0.52

1.67
90.86
8.67
0.16
30.11
53.24
25.80
0.35
2.78
61.59
53.89
0.57

2.19
85.40
7.10
0.13
29.85
54.83
35.94
0.43
2.89
60.68
53.87
0.57

achieved

by AIDA.

Apparently,

thealgorithm

classifies only entities where the classification confidence
is high.
Our proposed method achieved an average recall of
53.87% with the simple keyword matching approach. In
the next step, we are planning cluster the remaining tweets
based on the text similarity to the already clustered tweets
in order to further increase the recall. For DBPe dia
Spotlight, the average recall was significantly lower with
35.94% and the recall of AIDA was extremely low withonl y 7.1%. Besides, the number of tweets clustered withthe general meaning of the terms (e.g. “Escape”, “Focus”,

DBPedia Spotlight and AIDA greatly varied with the“Pilot”) is so dominant that car related keywords weredifferent categories. While relatively many tweets wererarely extracted.

clustered for the company domain, the recall for cars andTV shows was very low. The main reason was that terms inthose categories are often general terms, which are not

5.2. Tweet clustering
After having determined the keyword categories, we

covered in Wikipedia. For instance, no Wikipedia article

assigned all tweets to the category of the keywords they

exists for the general meaning of the company namecontain. We disregarded the tweets that did not contain“Sharp”.

any keywords or that contained keywords in multiple
categories.

Toevaluateourproposedmethod,we

We also realized that for some terms, the tweet
clustering process

performed well even though thecompared our results to the annotation results of DB Pedia

keyword clustering was not successful. In those cases, theSpotlight and AIDA. For each of the 27 test terms, we

unknown or mislabeled keywords apparently di d not haverandomly selected 1,000 tweets and manually evaluateda significant impact on the tweet classification result.

theHowever, if we cannot understand the entities from theassigned

categories.

The

results

of

the

tweet

keywords, we have to manually evaluate some of thecategorization process are shown in Table 3.
AIDA and DBPedia Spotlight clustered the tweets int otweets to identify the entity represented by a cluster.

more fine grained categories than our method. For
instance, tweets related to the company “Apple” were

6. Conclusion and Future Wor k

assigned to entities such as “Apple iPhone 4S”, “AppleIn this paper, we proposed an unsupervised method foriPad”, “Apple MacBook Pro” or “Apple Inc.”. However,clustering Twitter messages according to the meaning of aassuming that these subcategories can l ikely be grouped

named entity they contain based on onl y co-occurring

automatically b y analyzing the Wikipedia link structure,terms. Our method extracts characteristic keywords from

we manually merged them in our experiment.

tweets containing an ambiguous na med entity and Google
methodAutocomplete, clusters the keywords according to the(modified tf-idf + GA) was 60.68%, whereas DBPedia

entity the y represent and then assigns keyword categories

Spotlight achieved only an average precisio n of 54.83%.

to the tweets. Our method can be applied to any kind of

For both methods, the precision varied significantly

named entity, such as product names, company names

depending on the test terms. For the proposed method, it

person names or location names.

Theaverageprecisionoftheproposeddecreased drastically when important keywords were

We have conducted an experiment with 27 ambiguous

assigned to the wrong category. In case of the term

terms in the categories companies, cars and TV shows, in“Apple”, for instance, the keyword “watch” was assigned

order to compare the accuracy of our proposed method toto the fruit category, resulting in all tweets about the

DBPedia Spotlight and AIDA, two popular tools for“Apple watch” being mislabeled. For DBPedia Spotlight,

matching named

the precision decreased when characteristic keywords

Wikipedia articles. Our proposed method achieved awere missing in the tweets and thus unspecific terms

precision of 60.68% and a recall of 53.87%, whereas

extracted from the tweets were matched with terms in

DBPedia Spotlight achieved only a precision of 54.83%

unrelated Wikipedia articles. The best accuracy of 85.4%

and a recall of 35.94%. AIDA achieved a precision ofentities

in

texts

to

corresponding

85.4%, but the tradeoff is a recall of only 7.1%.
In the future, we will increase the recall of our proposed
method by clustering the currently unassigned tweets
based on their similarity to the already clustered tweets.
This can be achieved using, for instance, a machinelearning algorithm trained on characteristic keywords
extracted from the already clustered tweets. Apart from
that, we will further refine our keyword extraction andkeyword clustering algorithms to improve the accuracy ofour proposed method, and conduct a more comprehensive
experiment.

References[1] T. Lin, Mausam and O. Etzioni, “Entity Linking at
Web Scale”, In Proceedings of the Joint Workshop on
Automatic Knowledge Base Construction andWeb-scale Knowledge Extraction, pp. 84-88, 2012.
[2] D.Nadeau and S. Sekine, “A survey of named entity
recognition
andclassification”,
Lingvisticae
Investigationes, 30, 1, pp. 3-26, 2007.
[3] J. Hoart, M. A. Yosef, I. Bordino, H. Fürstenau, M.
Pinkal, M. Spaniol, B. Taneva, S. Thater, and G.
Weikum, “Robust disambiguation of named entities
in text”, In Proceedings of the Conference on
Empirical Methods in Natural Language Processin g(EMNLP), pp. 782-792, 2011.
[4] P.Mendes, N. and Jakob, Max and García-Silva,
Andrés and Bizer, Christian, “DBpedia Spotlight :Shedding Light on the Web of Documents”, In
Proceedings of the International Conference on
Semantic S ystems (I-Semantics), pp. 1-8, 2011.
[5] Mohamed Amir Yosef and Johannes Hoffart andIlaria Bordino and Marc Spaniol and Gerhard
Weikum, “AIDA: An Online Tool for Accurate
Disambiguation of Named Entities in Text andTables”, In Proceedings of the International
Conference on Very Large Databases (VLDB), pp.
1450-1453, 2011.
[6] F. Perez-Tellez and D. Pinto and J. Cardiff and P.
Rosso,“Onthe
DifficultyofClusterin g
Microblogging Texts
forOnlineReputation
Management”, In Proceedings of the ACL-HLTWorkshoponComputational
Approaches
toSubjectivity and Sentiment Anal ysis (WASSA), pp.
146-152, 2011.
[7] S. Zhang, J. Wu, D. Zheng, Y. Meng, Y. Xia, and H.
Yu, “Two stages based organization
namedisambiguity”, In Proceedings of the International
Conference on Computational Linguistics andIntelligent Text Processing (CICLing), pp. 249-257,
2012.
[8] Zhang, Shu, Jianwei Wu, Dequan Zheng, Yao Meng,and Hao Yu, “An Adaptive Method for Organization
Name Disambiguation with Feature Reinforcing”, In
Proceedings of the Pacific Asia Conference on
Language, Information and Computation (PACLIC),
pp. 237-245, 2012.
[9] S. R. Yerva, Z. Miklós, and K. Aberer.
“Quality-aware similarity assessment for entit ymatching in web data”, Information S ystems, 37(4) :pp. 336-351, 2012.

[10] O. Dan, J. Feng, and B. D. Davison, “A
Bootstrapping Approach to Identifying Relevant
Tweets for Social TV”, In Proceedings of theInternational AAAI Conference on Weblogs andSocial Media (ICWSM), pp. 462-465, 2011.
[11] B. Renger and J. Feng and O. Dan and H. Chang and
L. Barbosa, “VoiSTV: Voice-Enabled Social TV”, In
Proceedings of the International World Wide Web
Conference (WWW), pp. 253-256, 2011.
[12] M. Habib and M. van Keulen, “A generic open worldnamed entity disambiguation approach for tweet”, In
Proceedings of the International Conference on
Knowledge Discovery and Information Retrieval(KDIR), pp. 267-276, 2013.
[13] M. E. J. Newman and M. Girvan, “Finding
community structure in very large networks”,
Physical Review E, 70(6), 2004.
[14] E. Amigó, J. Artiles, J. Gonzalo, D. Spina, B. Liu,and A. Corujo, “Weps-3 evaluation campaign :Overview of the online reputation management task” ,In Proceedings of the Web People Search Evaluation
Workshop (WePS), pp. 1-13, 2010.