Summary:
In Post #1 we covered how to search Twitter and get a useful on disk data representation of the search results. In Post #2 we covered the first level of deduplication using HashSets as the test of sameness. We extended sameness by doing some normalization of the tweets which included removing urls and retweets.
You can download the code with this tarball or get it from subversion with the command
svn co https://aliasi.devguard.com/svn/teaching/lingpipe4twitter
Despite the solutions above we still have annoyingly similar tweets that are not useful for my goals for this set of posts. In particular the near duplicates really foul up any attempts at cross validation where one part of the data is used as training and the other as test data. If there are duplicates then we are training on testing for some examples and results end up looking too good.
Tokenization and Jaccard Distance
The duplicate detection problem in Twitter is really about word overlap with a slight game of telephone quality to it. The elaborations of previous tweets tend to be leading or following comments with the core of the source tweet preserved. Not much rephrasing is going on so word overlap between tweets is the obvious place to go. That entails a few elaborations to our approach:
- Find words in the tweets: Tokenization
- Measure similarity of tweets without sensitivity to tweet length: Jaccard Distance
Tokenization
A very simple tokenizer can just break on what characters separate words as follows:
public class Tokenize1 {
//Approach #1, find token seperators
public static void main (String[] args) {
String tweet = "RT @mparent77772: Should Obama's 'internet kill switch' power be curbed? http://bbc.in/hcVGoz";
System.out.println("Tweet: " + tweet);
String[] tokens = tweet.split(" ");
for (String token : tokens) {
System.out.println("Token: " + token);
}
}
}
This code is in src/Tokenize1.java. It produces output:
<ant tokenize1
[java] Tweet: RT @mparent77772: Should Obama's 'internet kill switch' power be curbed? http://bbc.in/hcVGoz
[java] Token: RT
[java] Token: @mparent77772:
[java] Token: Should
[java] Token: Obama's
[java] Token: 'internet
Another approach would be to try an define what characters belong in a token and match that, but that is a little more complex to program because String does not have a simple method call to capture an array of regex matches–see the regex chapter in the LingPipe book for more discussion:
import java.util.regex.Pattern;
import java.util.regex.Matcher;
public class Tokenize2 {
//Approach 2, define what is a token
public static void main (String[] args) {
String tweet = "RT @mparent77772: Should Obama's 'internet kill switch' power be curbed? http://bbc.in/hcVGoz";
Pattern tokenPattern = Pattern.compile("\\w+"); //match one or more letter or digit chars
System.out.println("Tweet: " + tweet);
Matcher matcher
= tokenPattern.matcher(tweet);
while (matcher.find()) { //keep matching until no more matches
System.out.println("Token: " + matcher.group());//print what matched
}
}
}
This approach produces the following output:
<ant tokenize2
[java] Tweet: RT @mparent77772: Should Obama's 'internet kill switch' power be curbed? http://bbc.in/hcVGoz
[java] Token: RT
[java] Token: mparent77772
[java] Token: Should
[java] Token: Obama
[java] Token: s
[java] Token: internet
Note that the text that separate the tokens are very different. Between ‘RT’ and ‘mparent77772’ is the separator ‘ @’. Depending on the needs of the application it can be easier to define tokens by what they look like rather than what the spaces around them look like. Often it is both.
While these approaches might work for the case at hand we will introduce the LingPipe tokenizers instead. They offer much richer tokenization options ready to go–see chapter 8 of the LingPipe book draft for more details or look at the Java doc.
An equivalent tokenization in the LingPipe API is created as follows:
import com.aliasi.tokenizer.RegExTokenizerFactory;
import com.aliasi.tokenizer.TokenizerFactory;
import com.aliasi.tokenizer.Tokenizer;
import java.util.regex.Pattern;
import java.util.regex.Matcher;
public class Tokenize3 {
public static void main (String[] args) {
//approach #3, A LingPipe tokenizer
String tweet = "RT @mparent77772: Should Obama's 'internet kill switch' power be curbed? http://bbc.in/hcVGoz";
TokenizerFactory tokFactory
= new RegExTokenizerFactory("\\w+");//match one or more letter or digit chars
System.out.println("Tweet: " + tweet);
char[] chars = tweet.toCharArray();
Tokenizer tokenizer
= tokFactory.tokenizer(chars,0,chars.length);
String token;
System.out.println("White Space :'" + tokenizer.nextWhitespace() + "'");
while ((token = tokenizer.nextToken()) != null) {
System.out.println("Token: " + token);
System.out.println("White Space :'" + tokenizer.nextWhitespace()+"'");
}
}
}
Its output reports on both the white spaces as well as the tokens.
[java] Tweet: RT @mparent77772: Should Obama's 'internet kill switch' power be curbed? http://bbc.in/hcVGoz
[java] White Space :''
[java] Token: RT
[java] White Space :' @'
[java] Token: mparent77772
[java] White Space :': '
[java] Token: Should
We add the normalization features of post #2 by extending the ModifyTokenTokenizerFactory to filter retweets and urls. A good way to develop a tokenizer is to put in into its own class and create a stand-alone task that runs the tokenizer over example data. In ‘src/NormalizedTokenizerFactory.java’ there is a main method:
public static void main(String[] args) {
TokenizerFactory tokFactory = new NormalizedTokenizerFactory();
String text = "RT @mparent77772: Should Obama's 'internet kill switch' power be curbed? http://bbc.in/hcVGoz"
System.out.println("Tweet: " + text);
char[] chars = text.toCharArray(); //convert to charArray
Tokenizer tokenizer
= tokFactory.tokenizer(chars,0,chars.length);
String token;
System.out.println("White Space :'" + tokenizer.nextWhitespace() + "'");
while ((token = tokenizer.nextToken()) != null) {
System.out.println("Token: " + token);
System.out.println("White Space :'" + tokenizer.nextWhitespace()+"'");
}
}
Running the above with ant normalizedTokenizerFactorty produces nicely normalized output.
[java] Tweet: RT @mparent77772: Should Obama's 'internet kill switch' power be curbed? http://bbc.in/hcVGoz
[java] White Space :''
[java] Token: Should
[java] White Space :' '
[java] Token: Obama
[java] White Space :'''
[java] Token: s
[java] White Space :' ''
[java] Token: internet
How that tokenizer functions is left as an exercise for the reader. Time to take on Mr. Jaccard.
Jaccard Distance as a Measure of Similarity
Jaccard Distance is a good way to impress folks with a fancy sounding term that is really just percent word overlap in our usage. If you think it helps you can also call it by the term ‘coefficient de communauté’ but then you might have to reveal that it was popularized by a French botanist–kind of undermines its jargon impact score. From the Jaccard Javadoc the proximity of two character sequences:
proximity(cs1,cs2)
= size(termSet(cs1) INTERSECT termSet(cs2))
/ size(termSet(cs1) UNION termSet(cs2))
We get the term sets from the tokenizer, and proximity is the percentage of tokens shared by both character sequences. The code to compute this for all pairs of tweets in our search results is in src/ExploreJaccard.java and the relevant bit of code is:
JaccardDistance jaccardD = new JaccardDistance(tokFactory);
int filteredCount = 0;
List candidateTweets
= filterNormalizedDuplicates(texts,
tokFactory); //throw out easy cases
System.out.println("Normalized duplicate filter leaves " + candidateTweets.size() + " tweets");
row = new ArrayList();
for (int i = 0; i < candidateTweets.size(); ++i) {
String closestTweet = "default value";
double closestProximity = -1d;
String targetTweet = candidateTweets.get(i);
for (int j = 0; j < candidateTweets.size(); ++j ) {//cross product, ouchy, ow ow.
String comparisionTweet = candidateTweets.get(j);
double thisProximity
= jaccardD.proximity(targetTweet,comparisionTweet);
if (i != j) { // can't match self
if (closestProximity < thisProximity) {
closestTweet = comparisionTweet;
closestProximity = thisProximity;
}
}
}
The goal of the above wildly inefficient program is to explore what the closest tweet is as determined by token overlap. The filterNormalizedDeduplicates(tweets,tokFactory) filters out duplicates as discussed in #2. We can then decide on a threshold to throw out tweets with too much overlap. Running the program on the Obama.csv example:
ant exploreJaccard -Ddata=searches/Obama.csv -Doutfile=runs/Obama.jaccard.csv
and then viewing the output .csv file with a sort on column B we get (click to see larger image):
Note that we get some values of 1 even though there are differences in Tweet1 and Tweet2. In row 2 the normalization filters out the url leaving the only difference being the phrase “replacing trains by high speed buses” in Tweet1 has an additional “high speed” in “replacing high speed trains by high speed busses” in Tweet 2. Since Jaccard does not count the number of words in computing distance the additional phrase adds no words to the set of words since it already exists in the tweet.
Scrolling down reveals just how bad redundancy can be with tweets. At the 50% overlap point the tweets are still looking quite similar:
Vet, 77, Busted For Obama Death Threat | The Smoking Gun http://t.co/MrTUwxv via @
Vet, 77, Busted For Obama Death Threat http://tinyurl.com/25zyxgp #tcot #tlot #sgp
There are 14 unique tokens with 7 overlapping yielding 50% overlap. 36% of the Obama query tweets have an overlap of 50% or more with another tweet. Trying a different query, "the" finds less overlap between tweets. Only 3% of the tweets have another tweet with 50% overlap. The query "today" yields 14% of tweets overlap. The lesson here is that some queries yield more uniform tweets which impacts subsequent language processing. A more technical way of expressing this observation is that the entropy of the resulting search results varies depending on the query. The "obama" search result entropy is lower (less random) than results for "the" which is more random.
The ‘today’ query had usefully different tweets at the 50% overlap level:
Playing a show in Chicago, IL at 9:00 PM today at LE PASSAGE http://artistdata.com/a/32on
Playing a show in Cape Girardeau, MO at 9:00 PM today at The Venue http://artistdata.com/a/32ow
Despite sharing half the words they are clearly not retweets and contain different information. It might be quite difficult to automatically reject ‘obama’ near duplicates at 50% token overlap but retain the ‘today’ near duplicates with 50% overlap–I encourage people to suggest approaches in the comments.
Finally we add a class that will take a set of queries and filter them for near duplicates at a given Jaccard proximity in src/DedupeJaccard.java. The interesting bit is:
public static List filterTweetsJaccard(List texts,
TokenizerFactory tokFactory,
double cutoff) {
JaccardDistance jaccardD = new JaccardDistance(tokFactory);
List filteredTweets = new ArrayList();
for (int i = 0; i < texts.size(); ++i) {
String targetTweet = texts.get(i);
boolean addTweet = true;
//big research literature on making the below loop more efficient
for (int j = 0; j = cutoff) {
addTweet = false;
break; //one nod to efficency
}
}
if (addTweet) {
filteredTweets.add(targetTweet);
}
}
return filteredTweets;
}
Deduplication along these lines is a big deal for web search as well as cleaning up Twitter feeds. The painful bit is the comparison of each new tweet to all the tweets that have passed the filter before which does not scale well. Much work has gone into hashing schemes that test for a hash match based on a lexical fingerprint of the existing corpus of tweets as well as more sophisticated similarity metrics. A recent paper with a decent overview of past work is http://research.microsoft.com/pubs/130851/ANDD.pdf.
Running the code on the Obama search results removes half the tweets with a .5 cutoff.
<ant dedupeJaccard -Ddata=searches/Obama.csv -Doutfile=runs/ObamaJaccardFiltered.csv
Buildfile: build.xml
compile:
[javac] Compiling 1 source file to /home/breck/devguard/teaching/lingpipe4twitter/build/classes
jar:
[jar] Building jar: /home/breck/devguard/teaching/lingpipe4twitter/demo.jar
dedupeJaccard:
[java] Writing to: runs/ObamaJaccardFiltered.csv
[java] Filtered size: 752 originally 1500
Looking at the tweets another issue immediately presents itself:
Coupe du monde - Obama: "Mauvaise décision": Le président Barack Obama a… http://goo.gl/fb/j5OUm #Maroc #sport #foot
RT @Luminary212: LOL “@BreakingNews: Obama knocks FIFA's decision to award Qatar, not the U.S., the 2022 World Cup: 'Wrong decision'”
I want to meet President Obama.
RT @laaficion Barack Obama, presidente de EU, consideró que la FIFA se equivocó al darle a Qatar el Mundial de 2022 y no a su país// celos
All sorts of languages are in the data. It looks like there is French and Spanish mixed in with the English. Next post will be creation of a language identification classifiers that will return to the notion of entropy discussed above.
Wrapup
In the quest to clean up the search results I have introduced some key concepts in text processing that will resurface in various forms throughout the posts. Summarizing:
- Tokenization: Breaking strings into words/word separators is key to getting at the unit of meaning for word based processing. Oddly enough in the next post we won’t be using words for language id, but we will be still tokenizing.
- Normalization: By eliminating trivial differences we can make text look more uniform–but beware of this tendancy.
- Entropy: Some collections of data are more uniform than others.
- Similarity: There are measures like Jaccard Distance to estimate the similarity of text. We will see many more examples that implement topic assignment, sentiment and more.
- Evaluation: We have picked an operating point for near duplicate detection by examining data. While the evaluation metric remains quite loose, in the next post we will both create gold-standard (or truth) data and evaluation the performance of our language id system against it.
Breck
LingPipe Blog 