In recent years, the protection of personal information has drawn much attention, requiring an advanced technology on de-identification to remove personal information from data. Among various personal information such as personal names, phone numbers, and so forth, this study focuses on location information. The conventional approaches to protect location information are to remove address expressions. However, there are complicated cases in which location information can be guessed with unexpected combinations of non-address words. For example, we can guess 'the most traditional city in Japan' is Kyoto. To our knowledge, such location-inferable expressions have not been dealt with. This study handles this phenomenon by using a location classifier. In addition, we assume two levels of location inferance; (1) inferable by machine and (2) inferable by human. To build the first-level inferance, we employed a collection of tweets with geo-tags. To build the second-level inferance, we created a new corpus with a flag for whether tweets are location-inferable by human or not. By using the two types of corpora, we classified texts into several categories such as a machine-inferable but human-non-inferable tweet, and so on. We also could obtain de-identified tweets by iterations of removing the highest weighted words for classifiers. We believe our novel concepts of de-identification are essential for various privacy protection.
• Security and privacy → Privacy protections; • Social and professional topics → Identity theft; Social engineering attacks; • Computing methodologies → Learning linear models; ©2018. Copyright for the individual papers remains with the authors. Copying permitted for private and academic purposes.
UISTDA ’18, March 11, 2018, Tokyo, Japan
In recent years, de-identification techniques to delete sensitive personal information have been studied actively because of the growing interest in privacy protection. In most automatic de-identification technologies, sensitive personal information is regarded as identical to proper expressions such as personal names, organization names, phone numbers, ID numbers, and addresses. Therefore, Named Entity Recognition (NER) techniques have been applied to deidentification. As described in this paper, this conventional approach is designated as NER-based de-identification.
Actually, NER-based de-identification has an important limitation: an address is identifiable from non-named entity expressions. Sometimes, the combination of general terms can be a strong clue for identifying a specific location. Consider the following sentence: ‘I’m excited to have dinner with my colleague on the riverbed!’ Because the riverbed is a famous spot in Kyoto and the location of riverbed in Kyoto is well-known, most Japanese people can guess that the person behind the tweet is located in Kyoto. This limitation of NER-based approaches becomes an important issue because many people unintentionally expose their location information to others. Sometimes the knowledge might be used illegally.
This study specifically examines automatic deidentification of messages in Twitter in terms of their location information. Our de-identification method has two novel features.
This study handles location-inferable expressions (not only proper expressions but also non-proper expressions).
This study assumes two levels of location inference:
(
Using the two viewpoints of inference, we were able to design several levels of de-identification: a level of a machine-inferable but human-non-inferable tweets, and so on. It is noteworthy that the proposed method is independent of any specific language.
The remainder of this paper is organized as follows. First, we construct a classifier to infer tweet locations using geotagged tweets in Twitter (Section 4). Next, we investigate
Home location Kong et al. [1] Yamaguchi et al. [4] (word-centric) Cha et al. [5] (location-centric) Efstathiades et al. [9]
Sadilek et al. [2] Flatow et al. [6] (word-centric) Kinsella et al. [7] Li et al. [8] (location-centric) Dredze et al. [10] Fang et al. [11]
Hua et al. [3] whether the classifier can infer tweet locations that are deidentified by humans (Section 5). Then, we tag the tweets with whether a human can infer the locations (what we call feasibility of location inference). We compare the diference between the classifier and human (Section 6). Finally, we present a de-identification method considering the combination of words (Section 7). 2
Many methods for location inference have been proposed to date. They are classifiable by two aspects: location types to be estimated and material types to be used for location estimation, as presented in Table 1.
As for location types, roughly three types of locations have been considered to date as shown in Table 1: user home locations, tweet locations, and described locations. Home location is a location where a user lives or spends much time, including the address of a user’s home or ofice. Tweet location is one from which a user has posted a tweet. A mentioned location is one that a user has described in a tweet. This paper represents an attempt to estimate tweet locations, which are our target of de-identification.
For location inference, three types of materials have been used as shown in Table 1: human network, tweet content, and tweet context. A human network is a relation between users in social networking services such as follower or followee in Twitter. Tweet content represents the content of a tweet message. Tweet context is information associated with a tweet such as a time stamp, geo-tag, or time zone. When inferring locations using tweet content, there are two major approaches distinguished by probabilistic models. One is called the word-centric model, calculating the probability p¹l |W º that a location l is labeled to a set of words W . The other is called a location-centric model. It calculates the probability p¹d|l º that each location’s label l outputs a tweet document d. In this paper, the word-centric model is applied to analyze tweet contents and to construct a classifier to estimate a tweet’s location.
The study by Flatow et al. [6] is similar to ours in that they attempted to infer tweet locations with the word-centric model and tweet content. However, the method cannot estimate locations that are identifiable by unexpected word combinations because a classifier is constructed using a word list that is appropriate to each area. By contrast, we propose a method to infer locations by considering word combinations.
In the medical field, de-identification of patient data has been studied actively. A conventional approach, Named Entity Recognition (NER) based de-identification, deletes proper expressions that are capable of specifying individuals such as proper nouns: phone numbers and addresses. However, NER-based de-identification is insuficient for deidentifying location information. Moreover, in the medical ifeld, a law exists to protect individuals’ medical records and other personal health information: Health Insurance Portability and Accountability Act (HIPAA) 1, which was approved in the U.S.A. in 1996. As for de-identification of social media contents including messages with location information, however, no criteria correspond to HIPAA. This paper therefore sets criteria for the de-identification of tweet locations by conducting experiments related to manual deidentification. 3
This section describes our dataset consisting of tweets with location information and area division.
Tweet data consist of 298,711 Japanese messages with geotags (hereinafter called ‘tweets’) posted within the central region of Kyoto City, Japan (latitude range = [34:93, 35:12] and longitude range = [135:67, 135:83]). This region includes popular landmarks, train stations, castles, shrines, temples, and so on, yielding a diverse mix of tweets. The tweets were collected about for a year between 2011/7/14 and 2012/7/31.
The tweet data are divided into training data and test data. Training data consisting of 179,227 tweets (60% of all data) are used to construct a classifier as described in Section 4. 1https://www.hhs.gov/hipaa/index.html The test data consist of 119,484 tweets (40% of all data) used to evaluate the classifier’s performance in Section 4. Some test data are used for experiments in Sections 5 and 6.
The region described in Section 3.1, the central region of Kyoto City, Japan, was divided into 200 (= 20 10) areas (a1 1; :::; a20 10 2 Akyoto ), as presented in Figure 1. Each area is 501 m 547 m. This division was useful to separate two consecutive stations (Hankyu Kawaramachi Station and Hankyu Karasuma Station) into two areas. Both areas are located near the Hankyu Kawaramachi Station, which is well known as the busiest downtown area in Kyoto. Therefore, this manner of division is reasonable.
Figure 1 presents the geographic distribution of 298,711 tweets for the selected areas. 39,078 tweets (13.1% of all tweets) were posted around the area a15 5, where Kyoto Station (Kyoto’s largest train station) is located. By contrast, only two tweets were posted in area a17 10, which is located southeast of Miterasennyuji Temple. 4
CONSTRUCTION OF LOCATION CLASSIFIER This section describes a method to construct a classifier that estimates a tweet location and which shows the classifier performance. Each text is split into words using a Japanese morphological analyzer, MeCab2. All uni-grams and bigrams are used as features for a bag-of-words representation. They are converted into vectors and are used for the training data. Each element of a vector was one or zero according to whether each feature appeared or not. Noises such as URLs (e.g. “https://XXX”), hashtags (e.g. “#hashtag”), or mentions to other users (e.g. “@username”) were removed from each text3. Correct answer labels are set to each area (200 classes in total) and are attached to each tweet based on its geo-tag. The classifier is constructed based on a linear model trained by logistic regression.
To evaluate the constructed classifier, the test data were classified into 200 classes. Results show that the accuracy for the test data was 47.2%. If the classifier always outputs the area a15 5 having the highest tweet density in the training data, then the accuracy for the test data is 11.6%. Also, 47.2% is modestly high in spite of its simple structure. 5
When using the classifier constructed in Section 4, it is necessary to define the state: ‘a tweet is de-identified.’ This section describes an experiment by which the state is defined.
To define the state that a tweet is de-identified, the manually annotated corpus was created. 500 tweets from the test data were de-identified manually. First, participants observe each tweet and infer its location as precisely as possible. The participants are allowed to use search engines, etc. Then, they delete the minimum number of morphemes in a tweet until they ascertain that the tweet’s location becomes ambiguous.
In this preliminary experiment, two annotators with
knowledge about Kyoto City independently annotated 500
tweets of the test data. The tweet below is an example of
the annotated tweets. Words to be deleted are crossed of.
In this example, the annotators considered that Tweet (
Then, a threshold determining whether a tweet is deidentified or not is defined using the annotated tweets. Given a de-identified tweet, the classifier calculates the 2http://taku910.github.io/mecab/ 3https://github.com/s/preprocessor probability of location inference when the tweet is assigned to the 200 areas, respectively. The maximum of the 200 probability values can be regarded as a reference to the tweet’s de-identification. Finally the average of the maximum values of the probability for all annotated tweets is used as the threshold. The tweets for which the probability is below the threshold were regarded as being de-identified.
The threshold value was set to 0.37 from the preliminary experiment’s result. Therefore, the tweets for which the probability was less than 0.37 were regarded as being deidentified.
However, for some tweets, the classifier outputs show high probability but the annotators were uncertain about their location, or vice versa. Because of such a discrepancy, probably one can make two types of inference for deidentification. One is to prevent inference of the location itself. The other is to prevent the assumption that a location can be inferred. In the next section, we examine another classifier to infer the feasibility of location inference. 6
FEASIBILITY OF LOCATION INFERENCE This section describes a preliminary experiment to construct a classifier that infers the feasibility of location inference and the actual construction.
To construct a classifier that infers the feasibility of location inference, a corpus annotated with the feasibility of location inference is generated. We first used 1,000 tweets selected randomly from the test data in Section 3.1. Then, binary classification tasks were conducted according to whether or not the locations can be inferred. To gather a large amount of experimental cooperation, the tasks were conducted through crowdsourcing. 100 participants answered each tweet as to whether or not the location can be inferred. The tweets for which 10% or more participants answered that they can be inferred were defined as tweets with feasibility of location inference. The others were treated as those without feasibility of location inference.
Results and Discussion 246 of 1,000 tweets showed the feasibility of location inference. Considering the two classification methods, whether the classifier in Section 4 can infer locations of tweets and whether tweets have feasibility of location inference, or not, the 1,000 tweets were classified into four classes. The results are presented in Table 2.
For some tweets, the classifier can infer their location, but
those without feasibility of location inference are presented
below.
(The wind is so strong (>_<). I am about to start my
lunch-hour business brightly and cheerfully as usual!)
p(^_^)q
(Good morning (^^). It is supposed to rain during the
day. The temperature will not reach 20◦C. Let’s be bright
and cheerful! I try to be busy and enjoy my day p(^_^)q.)
These tweets include fixed phrases for advertising stores,
e.g. the latter part of Tweet (
(
Tweet (
Construction of Classifier for Inferring Location Inference Feasibility A classifier was constructed with 1,000 tweets tagged using feasibility of location inference. Of the 1,000 tweets, 900 were training data. The other 100 were test data. As described in Section 4, each tweet was analyzed using MeCab. All uni-grams and bi-grams were used as features of Bagof-Words. Training was performed using logistic regression. Accuracy obtained using the test data was 86.0%. 7
From the result, de-identification of two kinds apparently exists. For that reason, it is necessary to use the system properly according to the purpose of de-identification. For example, the classifier in Section 4 de-identifies tweets for sales purposes. Because it is not necessary to de-identify such tweets, tweets can be de-identified using both the classifiers in Sections 4 and 6. Here we propose a method to de-identify tweets related to a combination of words.
Below is the algorithm of de-identification using the classiifer constructed in Section 4.
Step 0: Substitute 1 for m, the number of morphemes to be deleted.
Step 1: Delete m morpheme(s) from an original tweet sorд . When the number of the morphemes of sorд is n, the number of possible patterns is nCm . Group the nCm tweets into one group, S (= fs1; :::; snCm g).
Step 2: For each tweet si in S, find the maximum value of the probabilities the classifier outputs for its location (a1::200).
prob¹si;aj º maxprob¹si º = = p¹aj |si º max¹prob¹si;a1 º; :::; prob¹si;a200 ºº Step 3: Let the tweet with the least maxprob(si ) be snew , where the following holds.
snew = arg min maxprob¹si º si
UISTDA ’18, March 11, 2018, Tokyo, Japan
Return snew if maxprob¹snew º is below the threshold
(=0.37). Otherwise, increment m by 1 and back to Step
1 when m is less than n.
We present a part of the result of de-identification by the
proposed method. The tweets below are samples of the
deidentified tweets. Words to be deleted are crossed of.
(
With adequate training data, the method would work ideally, but a failure example exists as follows.
(12) (I never get tired of and never get enough of taking pictures in Kyoto Gyoen.) The algorithm should delete ‘ (Gyoen)’, but it actually deletes ‘ (Kyoto)’.
Furthermore, we investigated the relation between the size of the training data and the accuracy. Figure 3 shows that more training data are necessary. Some dificulty arises (a) Before: Original tweet and its location inference (b) After: De-identified tweet and its location inference with obtaining suficient amount of data because the way to make these data involves manual labeling.
A system for inference and de-identification of tweets can be built based on the proposed de-identification method. Figure 3 presents screenshots for the system. Inputting any tweet, this system infers its tweet location and de-identifies it according to a selected number of morphemes to be deleted. This process supports both machine and human inference. For both (a) raw and (b) de-identified tweets, the location inference results are presented on each map.
This paper proposed a novel de-identification method to anonymize tweet locations. Two kinds of tweet location inference were presented. One is inference of a location itself. The other is inference of the feasibility of location inference. These location inferences are based on the respective definitions of de-identification. The former tends to regard tweets from stores as identifiable because such tweets are posted from only one place many times. The latter tends to regard tweets in which common nouns are used as proper nouns, as identifiable. Therefore, in practical use, it would not be suficient to apply common concepts for de-identification of location. Our algorithm of de-identification based on the hypothesis that locations of tweets are inferable with combinations of words, partially brought expected results. Future tasks involve how to incorporate consideration of contexts. The analyses described in this paper investigated each tweet as a Bag-of-Words, and did not use information of relations of morphemes. This problem is expected to be resolved by consideration of the syntax structures of tweets. ACKNOWLEDGEMENTS This work is supported in part by Japan Agency for Medical Research and Development (16768699), Strategic Information and Communications R&D Promotion Programme (SCOPE), the Ministry of Internal Afairs and Communications of Japan.