Nihil Obstat

Baseline Sentiment Analysis with WEKA

2013-06-11T13:21:00.001+02:00

Sentiment Analysis (and/or Opinion Mining) is one of the hottest topics in Natural Language Processing nowadays. The task, defined in a simplistic way, consists of determining the polarity of a text utterance according to the opinion or sentiment of the speaker or writer, as positive or negative. This task has multiple applications, including e.g. Customer Relationship Management or predicting political elections.

While initial results dating back to early 2000 seem very promising, it is not such a simple task. We face from the informal Twitter language to the fact that opinions can be faceted (for instance, I may like the software but not the hardware of a device), or opinion spam and fake reviews, along with traditional and complex problems in Natural Language Processing as irony, sarcasm or negation. For a good overview of the task, please check the survey paper on opinion mining and sentiment analysis by Bo Pang and Lillian Lee. A more practical overview is the Sentiment Tutorial with LingPîpe by Alias-i.

In general, there are two main approaches to this task:

Counting and/or weighting sentiment-related words that have been evaluated and tagged by experts, conforming a lexical collection like SentiWordNet.
Learning a text classifier on a previously labelled text collection, like e.g. the SFU Review Corpus.

The SentiWordNet home page offers a simple Java program that follows the first approach. I will follow the second one in order to show how to use an essential WEKA text mining class (weka.core.converters.TextDirectoryLoader), and to provide another example of the weka.filters.unsupervised.attribute.StringToWordVector class.

I will follow the process outlined in the previous post about Language Identification using WEKA.

Data Collection and Preprocessing

For this demonstration, I will make use of a relatively small but interesting dataset named the SFU Review Corpus. This corpus consists of 400 reviews in English extracted from the Epinions website in 2004 divided in 25 positive and 25 negative reviews for each of 8 product categories (Books, Cars, Computers, etc.). It also contains 400 reviews in Spanish extracted from Ciao.es divided in the same categories (except for the Cookware category in English, which --more or less-- maps to Lavadoras --Washing Machines-- in Spanish).

The original format of the collections is one directory per category of products, including 25 positive reviews including the word "yes" in the file name and 25 negative reviews including the word "no" in the file name. Unfortunately, this format does not allow to work directly with it in WEKA, but a couple of handy scripts transform it into a new format: two directories, one including the positive reviews (directory yes), and the other one including the negative reviews (directory no). I have kept the category in the name of the files (with patterns like bookyes1.txt) in order to allow others making a more detailed analysis per category.

Comparing the structure of the original and the new format of the text collections:

In order to construct an ARFF file from this structure, we can use the weka.core.converters.TextDirectoryLoader class, which is an evolution of a previously existing helper class named TextDirectoryToArff.java and available at WEKA Documentation at wikispaces. Using this class is as simple as issuing the next command:

$> java weka.core.converters.TextDirectoryLoader -dir SFU_Review_Corpus_WEKA > SFU_Review_Corpus.arff

You have to call this command at the parent directory of SFU_Review_Corpus_WEKA, and the parameter -dir sets up the input directory. This class expects to have a single directory containing a directory per class value (yes and no in our case), which in turn should contain a number of files pertaining to the corresponding classes. As the output of this command goes to the standard output, I have to redirect it to a file.

I have left the output of the execution of this command for both the English (SFU_Review_Corpus.arff) and the Spanish (SFU_Spanish_Review.arff) collections at the OpinionMining folder of my GitHub repository.

Data Analysis

Previous models in my blog posts have been based on a relatively simple representation of texts as sequences of words. However, a trivial analysis of the problem easily drives us to think that multi-word expressions (e.g. "very bad" vs. "bad", or "a must" vs. "I must") can lead to better predictors of user sentiment or opinion about an item. Because of this, we will compare word n-grams vs. single words (or unigrams). As an basic set up, I propose to compare word unigrams, 3-grams, and 1-to-3-grams. The latter representation will include uni- to 3-grams with the hope of getting the best of all of them.

Keeping in ming that capitalization may matter in this problem ("BAD" is worse than "bad"), and that we can use standard punctuation (for each of the languages) as texts are long comments (several paragraphs each), I derive the following calls to the weka.filters.unsupervised.attribute.StringToWordVector class:

$> java weka.filters.unsupervised.attribute.StringToWordVector -O -tokenizer "weka.core.tokenizers.NGramTokenizer -delimiters \"\\\\W\" -min 1 -max 1" -W 10000000 -i SFU_Review_Corpus.arff -o SFU_Review_Corpus.vector.uni.arff $> java weka.filters.unsupervised.attribute.StringToWordVector -O -tokenizer "weka.core.tokenizers.NGramTokenizer -delimiters \"\\\\W\" -min 3 -max 3" -W 10000000 -i SFU_Review_Corpus.arff -o SFU_Review_Corpus.vector.tri.arff $> java weka.filters.unsupervised.attribute.StringToWordVector -O -tokenizer "weka.core.tokenizers.NGramTokenizer -delimiters \"\\\\W\" -min 1 -max 3" -W 10000000 -i SFU_Review_Corpus.arff -o SFU_Review_Corpus.vector.unitri.arff

We follow the notation vector.uni to denote that the dataset is vectorized and that we are using word unigrams, and so on. The calls for the Spanish collection are similar to these ones.

The most important thing in these calls is that we are no longer using the weka.core.tokenizers.WordTokenizer class. Instead, we are using weka.core.tokenizers.NGramTokenizer, which uses the options -min and -max to set the minimum and maximum size of the n-grams. But the most important thing is that there is a major difference between both classes, regarding the usage of delimiters:

The weka.core.tokenizers.WordTokenizer class uses the deprecated Java class java.util.StringTokenizer , even in the latest versions of the WEKA package (as of the day of this writing). In StringTokenizer, the delimiters are the characters used as "spaces" to tokenize the input string: white space, punctuation marks, etc. So you have to explicitly define which will be the "spaces" in your text.
The weka.core.tokenizers.NGramTokenizer class uses the recommended Java String method String[] split(String regex) , in which the argument (and thus the delimiters string) is a Regular Expression (regex) in Java. The text is splitted into tokens separated by substrings that match the regex, so you can use all the power of regexes including e.g. special codes for characters. In this case I am using the code \W which denotes any non-word character, in order to get only alpha-numeric character sequences.

After splitting the text into word n-grams (or more properly, after representing the texts as term-weight vectors in our Vector Space Model), we may want to examine which n-grams are most predictive. As in the Language Identification post, we make use of the weka.filters.supervised.attribute.AttributeSelection class:

$> java weka.filters.supervised.attribute.AttributeSelection -c 1 -E weka.attributeSelection.InfoGainAttributeEval -S "weka.attributeSelection.Ranker -T 0.0" -i SFU_Review_Corpus.vector.uni.arff -o SFU_Review_Corpus.vector.uni.ig0.arff $> java weka.filters.supervised.attribute.AttributeSelection -c 1 -E weka.attributeSelection.InfoGainAttributeEval -S "weka.attributeSelection.Ranker -T 0.0" -i SFU_Review_Corpus.vector.tri.arff -o SFU_Review_Corpus.vector.tri.ig0.arff $> java weka.filters.supervised.attribute.AttributeSelection -c 1 -E weka.attributeSelection.InfoGainAttributeEval -S "weka.attributeSelection.Ranker -T 0.0" -i SFU_Review_Corpus.vector.unitri.arff -o SFU_Review_Corpus.vector.unitri.ig0.arff

After the selection of the most predictive n-grams, we get the following statistics in the test collections:

The percentages in rows 3-6-9 measure the agressivity of feature selection. Overall, both collections have comparable statistics (in the same order of magnitude). Original unigrams are quite similar, but bigrams and trigrams are less in Spanish (despite the fact that there are more isolated words -- unigrams). Selecting n-grams with Information Gain is a bit more aggressive in Spanish for unigrams and possible bigrams, but less in trigrams.

Adding bigrams and trigrams to the representation substantially increases the number of predictive features (from 4 to 5 times). However, only trigrams result in a little increment of features, so bigrams will play a role here. The number of features is quite handy, and allows us to make quick experiments.

According to my previous post on setting up experiments with WEKA text classifiers and how to chain filters and classifiers, you must note that these are not the final features if we configure a cross-validation experiment -- we have to chain the filters (StringToWordVector and AttributeSelection) and the classifier in order to perform a valid experiment, as the features for each folder should be different.

Experiments and Results

In order to simplify the example, and expecting to get good results, we will use the same algorithms we used in the Language Identification problem. These are: Naive Bayes (NB, weka.classifiers.bayes.NaiveBayes), PART (weka.classifiers.rules.PART), J48 (weka.classifiers.trees.J48), k-Nearest Neighbors (weka.classifiers.lazy.IBk) with k = 1,3,5, and Support Vector Machines (weka.classifiers.functions.SMO); all of them with the default options, except for kNN which uses 1, 3 and 5 neighbors. I am testing the three proposed representations (based on unigrams, trigrams and 1-3grams) by 10-fold cross-validation. An example experiment command line is the following one:

$> java weka.classifiers.meta.FilteredClassifier -F "weka.filters.MultiFilter -F \"weka.filters.unsupervised.attribute.StringToWordVector -O -tokenizer \\\"weka.core.tokenizers.NGramTokenizer -delimiters \\\\\\\"\\\\\\\W\\\\\\\" -min 1 -max 1\\\" -W 10000000\" -F \"weka.filters.supervised.attribute.AttributeSelection -E weka.attributeSelection.InfoGainAttributeEval -S \\\"weka.attributeSelection.Ranker -T 0.0\\\"\"" -W weka.classifiers.bayes.NaiveBayes -v -i -t SFU_Review_Corpus.arff > tests/uniNB.txt

You can change the size of n-grams with the -min and -max parameters. Also, you can change the learning algorithm with the most external -W option. I am storing the results in a tests folder, in files with the convention <rep><alg>.txt. The results of this test for the English language collection are the following ones:

Considering the class yes (positive sentiment) as the positive class, in each column we show the True Positives (hits on the yes class), False Positives (members of the no class mistakenly classified as yes), False Negatives (members of the yes class mistakenly classified as no) and True Negatives (hits on the no class); along with the macro-averaged F1 (standard average F1 over both classes) and the general accuracy.

Additionally, the results for the Spanish language collection are the following ones:

So these are the results. Let us start the analysis...

Results Analysis

We can perform an analysis regarding different aspects:

Which is the overall performance?
Which is the performance when comparing different languages?
Which are the best learning algorithms?
Which effect do have different text representations in the classifier performance?

All in all, and taking into account that class balance is 50% (thus a trivial acceptor or a trivial rejector, or a random classifier accuracy would be 50%), most of the classifiers beat this baseline but not by a wide margin, and even the best one among all algorithms, languages and representations (SVMs on English 1-to-3-grams) reaches only a modest 71% -- far from a satisfying 90% or over. Let me remind we are facing a relatively simple problem -- long, few texts, and a binary classification. Most approaches in the literature get much better results in similar setups.

Results are better for English than for Spanish, comparing one on one. I will check the representations used in Spanish, for instance listing the first 20 n-grams for each representation, in order to explain it:

Some of the n-grams (highlighted in italics) are just incorrect, because of the incorrect recognition of accents due to the inappropriate pattern I have used in the tokenization step. The tokenizer makes use of the string "\W" in order to recognize alphanumeric string -- which in Java do not include vowels with accents ("á", "é", "í", "ó", "ú") and other language-specific symbols (e.g. "ñ"). Most of the n-grams are just not opinionated words or n-grams; instead, they are either intensifiers (like e.g. "muy" -- "very") or just contingent (dependent on the training collection, e.g. "en el taller" -- "in the garage"; "tarjeta de memoria" -- "storage card"). Those clearly opinionated words are highlighted in boldface. Very few. So for this issue, we can conclude that the training collection is too small.

If we examine the performance of different classifiers, we can cluster them in three groups: top performers (SVMs, NB), medium performers (PART, J48) and losers for this problem (kNN). These groups are intuitive:

Both SVMs and NB have often demonstrated their high performance in sparse datasets, and in text classification problems in particular. They both build a linear classifier with weights (or probabilities) for each of the features. Linear classifiers perform well here given that the dataset is built on representations that clearly promote over-fitting the dataset, as we have seen that many of the most predictive n-grams are collection-dependent.
Both PART and J48 (C4.5) are based on reducing error by progressively partitioning the dataset according to tests on the most predictive features. But the predictive features we have for such a small collection are not very good, indeed.
All versions of kNN perform very bad, most likely because the dataset is sparse and relatively small.

However, we have to keep in mind that we have used the algorithms with their default configurations. For instance, kNN allows to use the cosine similarity instead of the Euclidean distance -- being the cosine similarity much better for text classification problems, as demonstrated many times during 50 years of research in Information Retrieval.

And regarding dataset representations, the behavior is not uniform -- we do not systematically get better results with one representation in comparison with the others. In general, 1-to-3-grams perform better than the other representations in English, while unigrams are best in Spanish, and trigrams is most often the worst representation for both languages. If we focus on top performing classifiers (NB and SVMs), this latter comment is always true. In consequence, trigrams have --to some extent-- demonstrated their power in English (as a complement to uni- and bigrams), but not in Spanish (but knowing that the representation is incorrect because of character encoding).

Concluding Remarks

So all in all, we have a baseline learning-based method for Sentiment Analysis in English (and probably in Spanish, after correcting the representation), which is -- not surprisingly -- based on 1-to-3-grams and Support Vector Machines. And it is a baseline because its performance is relatively poor (with an accuracy of 71%), and we have not taken full advantage of the configuration, text representation and other parameters yet.

After this long (again!) post, I propose the next steps -- some of them left for the reader as an exercise:

Build a Java class that classifies text files according their sentiment, for English at least, taking my previous post on Language Identification as an example -- left for the reader.
Test other algorithms, and in particular: play with SVM configuration, and add Boosting (using weka.classifiers.meta.AdaBoostM1) to Naive Bayes -- left for the realer.
Check differences of accuracy in terms of product type -- cars, movies, etc. -- left for the reader.
Improve the Spanish language representation using the appropriate regex in the tokenizer to cover Spanish letters and accents -- I will take this one myself.
Check the accuracy of the basic keyword-based algorithm available in the SentiWordNet page -- I will take this one as well.

So that is all for the moment. You can expect one or more posts from me on this hot topic. Finally, thanks for reading, and please feel free to leave a comment if you think I can improve this article, or you have questions or suggestions for further articles on these topics!

Compilation of Resources for Text-based Age Detection

2013-05-23T18:07:00.001+02:00

Text-based age detection consists of estimate the age of a user according to the kind of texts he/she writes. This task is atracting some attention in the latest years, as for instance it promises to add one of the most interesting demographic features required in ad targetting. There is even an online application, TweetGenie, which guesses the age of a Twitter user -- it works for Dutch and English.

Text-based age detection is a text classification task which has close relation with others like genre detection or authorship attribution, as it should be based on stylistic features (e.g. usage of capitalization, average word length, frequencies of prepositions, or even the usage of emoticons) instead of on content bearing words (mostly nouns and verbs) like e.g. in topical text categorization. However, this does not mean that a pure word-based learning would not be effective.

A particular feature of this task is that it can be approached as classification if ages are divided in ranges, or as regression if we try to approach the exact age of the user.

There is a currently ongoing scientific competition at this topic, namely the Author Profiling task at the 9th evaluation lab on uncovering plagiarism, authorship, and social software misuse (PAN 2013). With this competition adding up new text collections, we have the following resources for trying and testing our approaches to text-based age detection:

The PAN 2013 Training Corpus for Author Profiling Task, consisting of a big number of posts and chats from three age ranges in Spanish and English.
The Blog Authorship Corpus, referenced in PAN, consisting of a big number of blog posts from three age ranges in English.
The NPS Chat Corpus, consisting on a relatively small number of chats from five age ranges in English (download from the NLTK corpora page or pay to the LDC).

For your comfort, I summarize some statistics about the collections:

And some notes on the information available in each collection:

The following papers can be of interest in order to avoid repeating others work.

J. Schler, M. Koppel, S. Argamon and J. Pennebaker (2006). Effects of Age and Gender on Blogging , Proceedings of 2006 AAAI Spring Symposium on Computational Approaches for Analyzing Weblogs.
S. Argamon, M. Koppel, J. Pennebaker and J. Schler (2009), Automatically profiling the author of an anonymous text , Communications of the ACM 52 (2): 119-123.
M.Koppel, S. Argamon and A. Shimoni (2003), Automatically categorizing written texts by author gender , Literary and Linguistic Computing 17(4), November 2002, pp. 401-412.
Jenny K. Tam (2009). Detecting Age in Online Chat , Master Thesis, Naval Postgraduate School.
Jane Lin (2007). Automatic Author Profiling of Online Chat Logs , Master Thesis, Naval Postgraduate School.

Please feel free to send me a message or comment below if you find any other resource that I should add to this post. Thanks for reading.

Presentación: "Menores y móviles: Usos, riesgos y controles parentales"

2013-05-22T18:22:00.001+02:00

El día 19 de abril dí una charla en la Universidad Europea de Madrid, titulada "Menores y móviles: Usos, riesgos y controles parentales". Esta charla se corresponde con un trabajo de investigación que he realizado dentro del proyecto titulado "Protección de usuarios menores de edad de telefonía móvil inteligente", dirigido por Joaquin Pérez y financiado por la Universidad Europea de Madrid (P2012 UEM14).

El resumen de la charla está disponible en la página de la red MAVIR (MA2VICMR: Mejorando el Acceso, el Análisis y la Visibilidad de la Información y los Contenidos Multilingüe y Multimedia en Red para la Comunidad de Madrid), y la presentación utilizada durante la charla es la siguiente:

Si el tema te interesa, no dudes en hacer culaquier pregunta o sugerencia en los comentarios de este post.

Language Identification as Text Classification with WEKA

2013-05-20T21:28:00.001+02:00

Language Identification, consisting on guessing the natural language in which a text is written (or an utterance is spoken), is not one of the hardest problems in Natural Language Processing, and in consequence, I believe it is a good starting point for learning about the text analysis capabilities available in WEKA.

This is in fact one problem taken by others like in this tutorial on using LingPipe for Language Identification, or by Alejandro Nolla at his post on Detecting Text Language With Python and NLTK. Moreover you can find a wide number of language identification programs, APIs and demos in the Wikipedia article on Language Identification. We may even consider this function as a natural language commodity, as you can see how Google Translate does it on default in the next figure:

The most typical (and rather simple) approach to Language Identification is storing a list of the most frequent character 3-grams in each language and checking the target overlap with each of the lists. Alternatively, you can use stop words lists. Of course, the accuracy depends on how you compute the overlap, but even simple distances can make it rather effective.

However, I will not follow this approach here. Instead, I will show how to build an standard text classifier using WEKA in order to show the options (and how to apply) the StringToWordVector filter, which is the main tool for text analysis in WEKA.

The steps we have to follow are the next ones:

To collect data from different languages in order to build a basic dataset.
To prepare the data for learning, which involves transforming it by using the StringToWordVector filter.
To analyze the resulting dataset, and hopefully, to improve it by using attribute selection.
To test over an independent test collection, which will give us a robust estimation of the accuracy of the approaches on real examples.
To learn the most accurate model as obtained from the previous step, and to use it for our classification program.

So this will be a rather long post. Be prepared for it.

Collecting the data and Creating the Datasets

Following the LingPipe Language ID Tutorial, I collect the data from the Leipzig Corpora Home Page. In particular, I will address guessing among English (EN), French (FR) and Spanish (SP), so I have gone to the download page, completed the CAPTCHA to get the list of available corpora, and downloaded:

The 2005 English 10k corpus of news in text format.
The 2009 French 10k corpus of news in text format.
The 2001-2002 Spanish 10k corpus of news in text format -- which is no longer there as far as I can see.

For your comfort, I have put these corpora in my LangID GITHub demo page. The files have the following format:

1 I didn't know it was police housing," officers quoted Tsuchida as saying. 2 You would be a great client for Southern Indiana Homeownership's credit counseling but you are saying to yourself "Oh, we can pay that off." 3 He believes the 21st century will be the "century of biology" just as the 20th century was the century of IT.

So I have loaded them into an OpenOffice spreadsheet, and replaced the number columns by the corresponding tags for the different languages: EN, FR, and SP. Then I have escaped the " and ' characters, because they are string delimiters in WEKA Attribute-Relation File Format (ARFF). In order to build the datasets, I have split the data keeping the first 9K sentences of each language for training, and the remaining 1K for testing. As some learning algorithms may be sensitive to the instance order, I have mixed the instances in batches of 1K texts, so the first 1K sentences are in English, the next 1K sentences are in French, and so on. The training data has the following header:

@relation langid_train @attribute language_class {EN,FR,SP} @attribute text String @data EN,'I didn\'t know it was police housing,\" officers quoted Tsuchida as saying.' EN,'You would be a great client for Southern Indiana Homeownership\'s credit counseling but you are saying to yourself \"Oh, we can pay that off.\"' EN,'He believes the 21st century will be the \"century of biology\" just as the 20th century was the century of IT.' ../..

The ARFF files for training and testing are available at the GITHub repository for the demo as well. You can open the training file (langid.collection.train.arff) in the WEKA Explorer, and setting the class to be the first attribute, you should be getting something like the following figure:

So we have a training collection with 9K instances per class (language), and a test collection with 1K instances per class.

Data Transformation

As in previous posts about text classification with WEKA, we need to transform the text strings into term vector to enable learning. This is done by applying the StringToWordVector filter, that is the most remarkable text mining function in WEKA. In previous posts, I have applied this filter with default options, but it offers a wide range of possibilities that can be seen when opening it in the WEKA Explorer. If you click on the Filter button and browse the tree to "weka > filters > unsupervised > attribute > StringToWordVector", and then click on the filter name, you get the next window:

Those are a lot of options, aren't them? So let us focus on the minimum set of options in order to be productive with this example of Language Identification. Those are:

doNoOperateOnPerClassBasis - we set this option to True in order to make the filter collect word tokens over the classes as a whole. This should be the standard setting in nearly all text classification problems.
lowerCaseTokens - we set this option to True because we are interested on the words independently of using upper or lower case. In other problems, like e.g. when processing Social Networks text, keeping the capitalization may be critical for getting a good accuracy.
tokenizer - WEKA provides several tokenizers, intended to break the original texts into tokes according to a number of rules. The most simple tokenizer is the weka.core.tokenizers.WordTokenizer, which splits the string into tokens by using a list of separators that can be set by clicking on the tokenizer name. It is a nice idea to give a look at the texts we have before setting up the list of separating characters. In our case, we have several languages and the default punctuation symbols may not fit our problem -- we need to add opening question and exclamation marks, apart from other symbols from HTML format like &, and other symbols. So our delimiters string will be " \r\n\t.,;:\"\'()?!-¿¡+*&#$%\\/=<>[]_`@" (backslash is escaped).
wordsToKeep - we set this option to keep as much words as we can, to include the full vocabulary of the dataset. An appropriate value may be one million.

So we leave the rest of options on default. Most notably, we are not using sophisticated weighting schemas (like TF or TF.IDF), nor stop words or stemming. These options are very frequent in Information Retrieval systems like Apache Lucene/SOLR, and they often lead to nice accuracy improvements in search systems.

We need to have the same vocabulary both in the training and the testing datasets, so we can apply this filter in the command line by using the batch (-b) option:

$> java weka.filters.unsupervised.attribute.StringToWordVector -O -L -tokenizer "weka.core.tokenizers.WordTokenizer -delimiters \" \\r\\n\\t.,;:\\\"\\'()?!-¿¡+*&#$%\\\\/=<>[]_`@\"" -W 10000000 -b -i langid.collection.train.arff -o langid.collection.train.vector.arff -r langid.collection.test.arff -s langid.collection.test.vector.arff

The options -O, -L, -tokenizer and -W correspond to the options above. The delimiter string is escaped because it is included in the specification of the tokenizer. The resulting files are also in the GITHub repository for the LangID example, along with the script stwv.sh (String To Word Vector) which includes this command.

Data Analysis and Improvement

If we take a quick look to the terms or tokens we have got, e.g.:

@attribute archival numeric @attribute archivarlos numeric @attribute archivas numeric @attribute archives numeric @attribute archiving numeric @attribute archivo numeric @attribute archivos numeric

We can imagine that most of them will be useless for Language Identification. This motivates making a more precise analysis of the tokens by using some kind of quality metric, like Information Gain. In fact, I am applying the weka.filters.supervised.attribute.AttributeSelection filter as I did in my posts on selecting attributes by chaining filters and on command line functions for text mining. So I issue the following command:

$> java weka.filters.supervised.attribute.AttributeSelection -c 1 -E weka.attributeSelection.InfoGainAttributeEval -S "weka.attributeSelection.Ranker -T 0.0" -b -i langid.collection.train.vector.arff -o langid.collection.train.vector.ig0.arff -r langid.collection.test.vector.arff -s langid.collection.test.vector.ig0.arff

We apply the filter in batch mode as well, in order to get the same attributes both in the training and in the test collections. We also set up the first attribute as the class (with the option -c), and set the threshold for keeping attributes as 0.0 in the weka.attributeSelection.Ranker search method. This means that we will keep only those attributes with Information Gain score over 0, and they will be sorted according to their score as well. This command is included in the asig.sh (Attribute Selection by Information Gain) script of the GITHub repository for the LangID example, along with the data files.

From the original 65,429 word attributes we got in the previous step, we have kept only 16,840 (a 25.73% of the original ones). We can be more aggressive by setting the threshold to a bigger value (e.g. 0.2).

The first twenty attributes are the next ones:

As we can see, all of them are very frequent words (in each language) that would be present in the stop lists for them. In consequence, our "pure" data mining approach is quite close to the traditional one based on stop words.

It makes sense to learn a J48 tree to get an idea of the complexity of the term relations. The weka.classifiers.trees.J48 algorithm implements the Quinlan's popular C4.5 learner, and as it outputs a decision tree, it can give us valuable insights of the term relations, like e.g. which co-occurring terms are more predictive. If we train that classifier on our new training dataset with the following command:

$> java weka.classifiers.trees.J48 -t langid.collection.train.vector.ig0.arff -no-cv

However, we get a quite complex decision tree populated with 273 nodes and 137 leaves. All the tests in the tree have the following look: "word > 0" or "word <= 0". This means that the algorithm induces that only the occurrence of words is important, but not its weight. The root of the tree is obviously a test on "the", and the smallest side of the tree (its right hand side, with "the > 0") is the following one:

the > 0 | de <= 0: EN (5945.0/8.0) | de > 0 | | el <= 0 | | | and <= 0 | | | | for <= 0 | | | | | to <= 0: FR (24.0/3.0) | | | | | to > 0: EN (2.0) | | | | for > 0: EN (3.0) | | | and > 0: EN (7.0) | | el > 0: SP (3.0)

This means, for instance, that the word "the" is an excellent predictive feature, and if it occurs in a text and the word "de" (from French or Spanish) does not occur in the text, that text is most likely written in English (with an estimated likelihood of 99.86% on the training collection). The overall accuracy of J48 over the training collection is 98.3963%.

Training and then Evaluating on the Test Collection

Before start training and evaluating, we have to decide which algorithms are most appropriate for the problem. In my experience with text learning, it is wise to test at least the following ones:

The Naive Bayes probabilistic approach, quick and with good results in text learning on average problems. In WEKA, It is incarnated in the weka.classifiers.bayes.NaiveBayes class.
The rule learner PART, which induces a list of rules by learning partial decision trees. It is a symbolic algorithm that produces rules which can be very valuable as they are easy to understand. This algorithm is implemented by the weka.classifiers.rules.PART class.
Of course, the J48 algorithm because of its visualization capabilities.
The lazy learner k-Nearest Neighbors (kNN), which occasionally gives excellent results in text classification problems. The WEKA class that implements this algorithm is weka.classifiers.lazy.IBk.
The Support Vector Machines algorithm, which it is probably the most effective on text classification problems because of its ability to focus on the most relevant examples in order to separate the classes. It is a very good learning algorithm for sparse datasets, and it is implemented in WEKA via the weka.classifiers.functions.SMO class or by the library LibSVM. I choose the Sequential Minimum Optimization implementation (SMO) embedded in WEKA.

Also, when Naive Bayes or J48 are effective, I usually get from small to even big accuracy improvements by using boosting, implemented by the weka.classifiers.meta.AdaBoostM1 class in WEKA. Boosting takes as input a weak classifier, and build a classifier committee by iteratively training that weak learner on those dataset subsets on which the previous learners are not effective. In this case, I will not apply boosting because the weak learners get rather high levels of accuracy, and it is most likely that boosting will only achieve a marginal improvement (if any) at the cost of a much bigger training time.

I have written an script named test.sh to execute all these algorithms with default options at the GITHub repository for the LangID demo. The results obtained by the algorithms are included in the repository as well, and summarized in the next table:

The different versions of the lazy algorithm kNN tested here appear to be very weak. It is likely we can improve its performance by changing the way the distance among examples is computed (from the Euclidean distance to a more appropriate one for text, that would be the cosine similarity), but their performance is so low that they will not score better than the rest of the algorithms.

The top algorithms in this test are Naive Bayes and Support Vector Machines. There is a trade off between both algorithms: SVMs are more effective (in fact, they are very effective) but they employ quite a lot of time to be trained, while Naive Bayes is less effective but quicker to be trained. In terms of classification time, both algorithms are linear on the number of attributes.

Even we have used a big number of attributes, there are some examples with rather weak representations. For instance, let us check the following instances or texts:

{58 1,94 1,313 1,1663 1} {119 1,361 1,2644 1,16840 FR} {2 1,16840 SP}

The first and second examples have only 3 occurring words (the class value for the first text is EN in the sparse format it is used by WEKA in this example), and the third example has only one word ("el"). The two first examples attribute numbers (58 or over) mean that the attributes are not the most informative ones, while in the third example we find a very informative word. If we apply a more aggressive selection using Information Gain, we will be missing a lot of examples (with null representations) in this example, thus making them fall to the most likely class. As the classes have a balanced distribution, the language chosen in that case will be EN, which is the default value for the class attribute.

Learning the Best Classifier and Using it Programmatically

So after our experiments, we know the best classifier in our tests is SVMs. So it is time to learn it and store the classifier into a file for further programmatic use. For this purpose, I have written an script that trains the classifier and stores the model into a file, using the following command-line call:

$> java weka.classifiers.meta.FilteredClassifier -t langid.collection.train.arff -c first -no-cv -d smo.model.dat -v -F "weka.filters.MultiFilter -F \"weka.filters.unsupervised.attribute.StringToWordVector -O -L -tokenizer \\\"weka.core.tokenizers.WordTokenizer -delimiters \\\\\\\" \\\\\\\r\\\\\\\n\\\\\\\t.,;:\\\\\\\\\\\\\\\"'()?!-¿¡+*&#$%/=<>[]_`@\\\\\\\"\\\" -W 10000000\" -F \"weka.filters.supervised.attribute.AttributeSelection -E weka.attributeSelection.InfoGainAttributeEval -S \\\"weka.attributeSelection.Ranker -T 0.0\\\"\"" -W weka.classifiers.functions.SMO

This call is rather painful because of the nested, and nested, and nested, and nested quotes. So I have pretty-printed it in the script learn.sh script at the GitHub repository for the LangID example. For dealing with nested quotes, follow the advice in the Wikipedia article about nested quotation.

With this call, we have stored a model in the file smo.model.dat, which chains the StringToWordVector filter, the AttributeSelection filter, and an SMO classifier by using the weka.classifiers.meta.FilteredClassifier and the weka.filters.MultiFilter classes, as I have explained in the post on Command Line Functions for Text Mining in WEKA.

One good point of WEKA is that we can learn a model in the command line and use it in a program. I have modified the MyFilteredClassifier.java program I used in my post describing A Simple Text Classifier in Java with WEKA, and I have committed it at the GITHub repository with the name LanguageIdentifier.java. I have created three sample test files as well, test_en.txt, test_fr.txt and test_sp.txt. The operation of the program is the following one:

$> javac LanguageIdentifier.java $> java LanguageIdentifier Usage: java LanguageIdentifier <fileData> <fileModel> $> java LanguageIdentifier test_en.txt smo.model.dat ===== Loaded text data: test_en.txt ===== This is a sample test for the language identifier demo. ===== Loaded model: smo.model.dat ===== ===== Instance created with reference dataset ===== @relation 'Test relation' @attribute language_class {EN,FR,SP} @attribute text string @data ?,' This is a sample test for the language identifier demo.' ===== Classified instance ===== Class predicted: EN $> java LanguageIdentifier test_fr.txt smo.model.dat ===== Loaded text data: test_fr.txt ===== Ceci est un test de l'échantillon pour la démonstration de l'identificateur de langue. ===== Loaded model: smo.model.dat ===== ===== Instance created with reference dataset ===== @relation 'Test relation' @attribute language_class {EN,FR,SP} @attribute text string @data ?,' Ceci est un test de l'échantillon pour la démonstration de l'identificateur de langue.' ===== Classified instance ===== Class predicted: FR $> java LanguageIdentifier test_sp.txt smo.model.dat ===== Loaded text data: test_sp.txt ===== Esto es un texto de prueba para la demostración del identificador de idioma. ===== Loaded model: smo.model.dat ===== ===== Instance created with reference dataset ===== @relation 'Test relation' @attribute language_class {EN,FR,SP} @attribute text string @data ?,' Esto es un texto de prueba para la demostración del identificador de idioma.' ===== Classified instance ===== Class predicted: SP

So the program is correct on the three examples. Remember that you have to learn the model before using the program. As a side note, as the program only uses a FilteredClassifier object, you can change the script to accommodate a different algorithm. For instance, you can just change the text "weka.classifiers.functions.SMO" by "weka.classifiers.bayes.NaiveBayes" in the learn.sh script, and the program will be working the same way -- but with a different model.

Concluding Remarks

While being relatively simple, the Language Identification problem helps to identify the essential tasks we have to perform when building text classifiers with WEKA. It is a complete example in the sense that we have not only collected the dataset and learnt on it, but we have also dig a bit into the most suitable representation by playing with attribute selection and tentative classifier to visualize the data. It also demonstrates some basic configurations of the StringToWordVector filter, which is the most remarkable tool in WEKA for text mining.

If you have had the time to read all this post, and even tried the program: thank you! I hope it has been a valuable time investment. I am tempted to suggest you to modify the dataset to include more languages, as the problem I have addressed is relatively simple -- only three and quite different languages.

Finally, thanks for reading, and please feel free to leave a comment if you think I can improve this article, or you have questions or suggestions for further articles on this topics!

Mapping Vocabulary from Train to Test Datasets in WEKA Text Classifiers

2013-05-02T01:41:00.001+02:00

There are several ways of evaluating a (text) classifier: cross validation, splitting your dataset into train and test subsets, or even evaluating the classifier on the training set itself (not recommended). I will not discuss the merits of each method, instead I will focus on a train/test split evaluation.

When you start to work with your train and test text datasets, you have got two labelled text collections like e.g. those I make available at my GITHub project: smsspam.small.train.arff and smsspam.small.test.arff . In this case, we have two collections that are a 50% split of my original simple collection smsspam.small.arff , which in turn is a subset of the the original SMS Spam Collection. The files are formatted according to the WEKA ARFF:

@relation sms_test @attribute spamclass {spam,ham} @attribute text String @data ham,'Go until jurong point, crazy.. Available only in bugis n great world la e buffet... Cine there got amore wat...' spam,'Free entry in 2 a wkly comp to win FA Cup final tkts 21st May 2005. Text FA to 87121 to receive entry question(std txt rate)T&C\'s apply 08452810075over18\'s' ...

That is, one text instance per line, the first attribute being the nominal class spam/ham, and the second attribute being the text itself.

In text classification, you have to transform this original representation into a vector of terms/words/stems/etc. in order to allow the classifier to learn expressions like: "if the word "win" occurs in a text, then classify it as spam". In other words, you have to represent your texts as feature vectors, where the features are words and the values are e.g. binary weights, TF weights, or TF.IDF weights. In fact, WEKA provides the handy StringToWordVector filter for this purpose (Thanks, WEKA!).

However, it is most likely that the vocabulary used in your training set and in your test set is not identical. For instance, if you directly apply the StringToWordVector filter to the previous files, you get a bit different results, summarized in the following table:

Obviously, to enable learning you have to ensure that the representation of both datasets is the same. For instance, imagine that the root of the decision tree you have learnt on your training collection poses a test on an attribute that does not exist on your test collection, then what happens?

Fortunately, WEKA provides at least three ways of getting the same vocabulary in your train and test subcollections. Here are them:

Using a batch filter that takes both training and test collections at the same time, using the first for getting the attributes and representing the last using those attributes.
Using a FilteredClasifier (that I have discussed in previous posts), which feeds both the filter and the classifier into a single classifier that takes the original representation class/text as input for both the training and the test sets.
A more recent method, that is separately getting the representations and using an InputMappedClassifier that acts as a wrapper of an underlying classifier, and tries to match attributes from the training collection into the corresponding ones of the test subset.

The first method is quite simple, and it just makes use of the -b option of the WEKA filters. The corresponding command line calls are the next ones:

$> java weka.filters.unsupervised.attribute.StringToWordVector -b -i smsspam.small.train.arff -o smsspam.small.train.vector.arff -r smsspam.small.test.arff -s smsspam.small.test.vector.arff $> java weka.classifiers.lazy.IBk -t smsspam.small.train.vector.arff -T smsspam.small.test.vector.arff -i -c first ... === Confusion Matrix === a b <-- classified as 1 15 | a = spam 0 84 | b = ham

The second method, conveniently discussed in my previous post, can be applied with the following call:

$> java weka.classifiers.meta.FilteredClassifier -t smsspam.small.train.arff -T smsspam.small.test.arff -F weka.filters.unsupervised.attribute.StringToWordVector -W weka.classifiers.lazy.IBk -i -c first ... === Confusion Matrix === a b <-- classified as 1 15 | a = spam 0 84 | b = ham

As it is shown in the previous results, both methods achieve the same results. In this case, I have opted for using StringToWordVector without parameters (default tokenization, term weights, no stemming, etc.) with the relatively weak classifier IBk , which implements a k-Nearest-Neighbor learner that, instead of building a model from the training collection, it searches the closest training instance to the test instance (k is 1 on default) and assigns its class to the test instance.

However, the third method achieves different results, as the mapping involves some attributes from the training collection disappearing, and ignoring new attributes in the test collection. It is called the following way:

$> java weka.filters.unsupervised.attribute.StringToWordVector -i smsspam.small.train.arff -o smsspam.small.train.vector.arff $> java weka.filters.unsupervised.attribute.StringToWordVector -i smsspam.small.test.arff -o smsspam.small.test.vector.arff $> java weka.classifiers.misc.InputMappedClassifier -W weka.classifiers.lazy.IBk -t smsspam.small.train.vector.arff -T smsspam.small.test.vector.arff -i -c first Attribute mappings: Model attributes Incoming attributes ------------------------------ ---------------- (nominal) spamclass --> 1 (nominal) spamclass (numeric) #&gt --> 2 (numeric) #&gt (numeric) $1 --> - missing (no match) (numeric) &amp --> - missing (no match) (numeric) &lt --> 6 (numeric) &lt (numeric) *9 --> 7 (numeric) *9 (numeric) + --> - missing (no match) (numeric) - --> 8 (numeric) - ... === Confusion Matrix === a b <-- classified as 2 14 | a = spam 1 83 | b = ham

In fact, this time we get a bit more spam (2 over 14) with a false positive, although the general accuracy is exactly the same: 85%. You can see how some of the attributes are missing (they do not occur in the test dataset), like: "$1", "+", etc. This for sure affects the performance of the classifier, so beware.

With these options, my recommendation is using the first method, as it allows you to fully examine the representation of the datasets (term weight vectors) and it decouples filtering from training, what may be convenient in terms of efficiency.

Before ending this post, I have to thank Tiago Pasqualini Silva, Tiago Almeida and Igor Santos for our experiments with the SMS Spam Collection, and to Tiago Pasqualini in particular because he showed me the InputMappedClassifier.

And last but not least, thanks for reading, and please feel free to leave a comment if you think I can improve this article, or you have questions or suggestions for further articles on this topics!

URL Text Classification with WEKA, Part 1: Data Analysis

2013-04-26T00:46:00.001+02:00

I have recently came across a website named SquidBlackList.org, which features a number or URL lists for safe web browsing using the open source proxy Squid. In particular, it features a quite big porn domains list, so I wondered: Is it possible to make a text classification system with WEKA to detect porn domains using the text in the URLs?

Just to note that SquidBlackList on porn (and most of the rest of the lists they provide is licensed under Creative Commons Attribution 3.0 Unported License: Blacklists (Squidblacklist.org) / CC BY 3.0

The Filtering Problem

Most web filtering systems work by using a manually classified list of URLs into a list of categories that are used to define filtering profiles (e.g. block porn but allow press). The URL lists or database must be manually maintained, and it has to be quite comprehensive regarding user browsing behaviour. As (aggregated) web browsing follows a Zipfian distribution (that is, relatively few URLs accumulate most of the traffic), you can provide a rather effective service by ensuring that your URL database covers the most popular URLs. URL-based filtering is rather efficient (if your database is well implemented), and it can easily cover around 95% of the web traffic (in terms of #requests, not in terms or #URLs).

However, covering the remaining 5% requires performing some kind of analysis. My target here is dynamically classifying that 5% of web requests (which may account for millions of URLs or even just domains) into two classes: notporn and porn. This way, we can cover the 100% of the traffic, and it is likely that we concentrate our classification mistakes (that may be possible at the URL database as well) only into that small 5% - so our filter can be 98% effective or more.

Why analyzing the URL text? For a matter of efficiency - you do not have to go to the Internet and get the actual Web content in order to analyze it, so all the processing is local to the proxy and you eventually avoid performing unnecessary Web requests at the proxy itself.

Collecting the Dataset

So we start with an 880k porn domains list, but although it is possible to learn only from positive examples, we may expect better effectiveness if we collect negative examples (not porn domains). A handy resource is the Top 1M Sites list by Alexa, a Web research company that provides this ranked list in a daily basis. Having 1M negative examples and 880k positive examples makes a good class balance and quite populated dataset -- nice for learning, specially when its instances are relatively short text sequences (e.g. google.com vs. porn.com).

First we have to make both lists comparable. The format of the Alexa list is <rank>,<domain>, while the format of the Squid black list is <dot><domain> (in order to match the Squid URL list format). A couple of cut and sed commands will do the trick.

Then we can just add the class and mix the lists.

Cleaning the Dataset, first step

But... Hey, Internet is for porn! -- we should expect that some of the URLs in the Alexa ranking are pornographic. In fact, a simple search demonstrate it:

$ grep porn alexa.csv | more pornhub.com youporn.com ... $ grep porn alexa.csv | wc -l 5719

We can just substract the porn list from the Alexa list with a handy grep:

grep -f porn.csv -v alexa.csv > alexaclean.csv

But it takes a loooooong time, so I prefer to sort Alexa list, transforming it to Linux format (as the original one has DOS format), and use comm:

$ sort alexa.csv > alexasorted.csv $ fromdos alexasorted.csv $ comm -23 alexasorted.csv porn.csv > alexaclean.csv $ wc -l alexaclean.csv 975088 alexaclean.csv

Good point, only 25k URLs are pornographic... Well, lets check:

$ grep porn alexaclean.csv | head 001porno.com 0dayporn.org 1000porno.net ...

So we still have some porn in there.

Cleaning the Dataset, second step

Cleaning Alexa list from porn is a bit more complex. How to find those popular porn sites, if they are not even in such a comprehensive list as the Squidblacklist one? Another resource comes to help, and it is the sex-related search engine PornMD. This engine has recently published a list of popular porn searches in the form of a dynamic infography named Global Internet Porn Habits:

So, if you collect a list of the top searches in five of the biggest speaking countries, you get:

Cleaning the list from duplicated words, adding "porn", "sex" and "xxx" (rule of thumb), and computing the number of domains they occur in the Alexa (cleaned) and the Squidblacklist lists, we get:

Looking at the list, a relatively safe proportion between the number of occurrences in Squid's versus Alexa's (clean) list is 9 -- this way, we keep most obvious words and remove the most ambiguous ones (although there are some borderline examples, as "asian"). We can see the effects:

$ grep "amateur\|anal\|asian\|creampie\|hentai\|lesbian\|mature\|milf\|squirt\|teen\|porn\|sex\|xxx" alexaclean.csv | wc -l 17389 $ grep "porn\|sex\|xxx" alexaclean.csv | wc -l 12342 $ grep -v "amateur\|anal\|asian\|creampie\|hentai\|lesbian\|mature\|milf\|squirt\|teen\|porn\|sex\|xxx" alexaclean.csv > alexacleanfinal.csv $ wc -l alexacleanfinal.csv 964735 alexacleanfinal.csv

You can see that just "porn", "sex" and "xxx" account for 70,97% of domains, so there is some domain knowledge in the process. I must note I may use another, much more extensive list of porn-related searches like the one featured PornMD Most Popular page.

Additional Analysis

To get a feeling of how the previous porn-related keywords are distributed across the original Alexa ranking, I have computed the number of lines (domains) they occur in 100k intervals, to get the following chart:

Where #query1 represents the number of occurrences of "porn\|sex\|xxx" and #query2 represents the full list of keywords. The growth is nearly linear with an average of 1234.2 URLs per interval in #query1, and 1738.9 URLs per interval in #query2. The curves are smooth, and there are more domains in the first intervals (e.g. 1482 hits in the first 100k Alexa URLs for #query1) than in the latest ones (e.g. 1077 hits in the last 100k Alexa URLs for #query1).

There are other dataset statistics that may provide better insights regarding the classification problem, or in other words, that may be more informative or predictive in terms of classification accuracy. For instance:

What is the length of an average domain name in each category?
How many points and/or dashes do domain have in average per category?
Which is the distribution of different TLDs (Top Level Domains) across both categories?

Can you imagine any other interesting statistics?

The Dataset

Once we have got the original Squidblacklist and the Alexa cleaned one (after substraction and removing the keyword hitting lines), we add some format to get a WEKA ARFF file. For instance, 0000free.com must be transformed into '0000free.com',safe. A bit of sed trickery does the job, and then we mix the lists with the following command:

$ paste -d '\n' alexacleanfinal.csv porn.csv > urllist.csv

The rationale behind mixing the lists is that some learning algorithms are dependent on the order of examples, and for those algorithms it is clever not to expose first all the examples of one class, the other class' ones. As the paste command adds new lines when one of the lists finish, we have to remove double CRs (\n\n) with another sed call, and we finally add the ARFF header to get a file starting the following way:

@relation URLs @attribute urltext String @attribute class {safe,porn} @data '0000free.com',safe '0000000000000000000sex.com',porn '0000.jp',safe '000000000gratisporno.ontheweb.nl',porn ...

I have left that file named urllist.arff in my GitHub folder for your convenience, so you can start playing with it. Beware, it is over 40Mb.

So that is all for the moment. Stay tuned for my next steps if you liked this post.

Thanks for reading, and please feel free to leave a comment if you think I can improve this article, or you have questions or suggestions for further articles on this topic!

A Simple Text Classifier in Java with WEKA

2013-04-08T09:31:00.001+02:00

In previous posts [1, 2, 3], I have shown how to make use of the WEKA classes FilteredClassifier and MultiFilter in order to properly build and evaluate a text classifier using WEKA. For this purpose, I have made use of the Explorer GUI provided by WEKA, and its command-line interface.

In my opinion, it is a good idea to get familiar with both the Explorer and the command-line interface if you want to get a feeling of the amazing power of this data mining library. However, where you can take full advantage its power is in your own Java programs. Now it is time to deal with it.

Following Salton, and Belkin and Croft, the process of text classification involves two main steps:

Representing your text database in order to enable learning, and to train a classifier on it.
Using the classifier to predict text labels of new, unseen documents.

The first step is a batch process, in the sense that you can do it periodically (as long as your labelled data set gets improved with time -- bigger sizes, new labels or categories, corrected predictions via user feedback). The second step is actually the moment in which you get advantage of the knowledge distilled by the learning process, and it is online in the sense that it is don by demand (when new documents arrive). This distinction is conceptual, I mean that modern text classifiers retrain on the added documents as soon as they get them, in order to keep or improve accuracy with time.

In consequence, what we need to demonstrate the text classification process is two programs: one to learn from the text dataset, and another to use the learnt model to classify new documents. Let us start showing a very simple text learner in Java, using WEKA. The class is named MyFilteredLearner.java , and its main() method demonstrates its usage, which involves:

Loading the text dataset.
Evaluating the classifier.
Training the classifier.
Storing the classifier.

The most interesting parts of the process are:

We read the dataset by simply using the method getData() of an ArffReader object that wraps a BufferedReader.
We programmatically create the classifier by combining a StringToWordVector filter (in order to represent the texts as feature vectors) and a NaiveBayes classifier (for learning), using the FilteredClassifier class discussed in previous posts.

The process of creating the classifier is demonstrated in the next code snippet:

trainData.setClassIndex(0); filter = new StringToWordVector(); filter.setAttributeIndices("last"); classifier = new FilteredClassifier(); classifier.setFilter(filter); classifier.setClassifier(new NaiveBayes());

So we set the class of the dataset as being the first attribute, then we create the filter and set the attribute to be transformed from text into a feature vector (the last one), and then we create the FilteredClassifier object and add the previous filter and a new NaiveBayes classifier to it. Given the attributes above, the dataset has to have the class as the first attribute, and the text as the second (and last) one, like in my typical example of the SMS spam subset example.

You can execute this class with the following commands to get the following output:

$>javac MyFilteredLearner.java $>java MyFilteredLearner smsspam.small.arff myClassifier.dat ===== Loaded dataset: smsspam.small.arff ===== Correctly Classified Instances 187 93.5 % Incorrectly Classified Instances 13 6.5 % Kappa statistic 0.7277 Mean absolute error 0.0721 Root mean squared error 0.2568 Relative absolute error 25.8792 % Root relative squared error 69.1763 % Coverage of cases (0.95 level) 94 % Mean rel. region size (0.95 level) 51.75 % Total Number of Instances 200 === Detailed Accuracy By Class === TP Rate FP Rate Precision Recall F-Measure MCC ROC Area PRC Area Class 0,636 0,006 0,955 0,636 0,764 0,748 0,943 0,858 spam 0,994 0,364 0,933 0,994 0,962 0,748 0,943 0,986 ham Weighted Avg. 0,935 0,305 0,936 0,935 0,930 0,748 0,943 0,965 ===== Evaluating on filtered (training) dataset done ===== ===== Training on filtered (training) dataset done ===== ===== Saved model: myClassifier.dat =====

The evaluation has been performed with default values except for the number of folds, that has been set to 4 as shown in the next code snippet:

Evaluation eval = new Evaluation(trainData); eval.crossValidateModel(classifier, trainData, 4, new Random(1)); System.out.println(eval.toSummaryString());

For the case you don want to evaluate the classifier on the training data, you can omit the call to the evaluate() method.

Now let us deal with the classification program, which is far more complex but only for the process of creating an instance. The class is named MyFilteredClassifier.java , and its main() method demonstrates its usage, which involves:

Reading the text to be classified from a file.
Reading the model or classifier from a file.
Creating the instance.
Classifying it.

Creating the instance is performed in the makeInstance() method, and its code is the following one:

// Create the attributes, class and text FastVector fvNominalVal = new FastVector(2); fvNominalVal.addElement("spam"); fvNominalVal.addElement("ham"); Attribute attribute1 = new Attribute("class", fvNominalVal); Attribute attribute2 = new Attribute("text",(FastVector) null); // Create list of instances with one element FastVector fvWekaAttributes = new FastVector(2); fvWekaAttributes.addElement(attribute1); fvWekaAttributes.addElement(attribute2); instances = new Instances("Test relation", fvWekaAttributes, 1); // Set class index instances.setClassIndex(0); // Create and add the instance DenseInstance instance = new DenseInstance(2); instance.setValue(attribute2, text); // instance.setValue((Attribute)fvWekaAttributes.elementAt(1), text); instances.add(instance);

The classifier learnt with MyFilteredLearner.java expects that an instance has two attributes: the first one is the class, it is a nominal one with values "spam" or "ham"; the second one is a String, which is the text to be classified. Instead of creating one instance, we create a whole new dataset which first instance is the one that we want to classify. This is required in order to let the classifier know the schema of the dataset, which is stored in the Instances object (and not in each instance).

So first we create the attributes by using the FastVector class provided by WEKA. The case of the nominal attribute ("class") is relatively simple, but the case of the String one is a bit more complex because it requires the second argument of the constructor to be null, but casted to FastVector. Then we create an Instances object by using a FastVector to store the two previous attributes, and set the class index to 0 (which means that the first attribute will be the class). As a note, the FastVector class is deprecated in the WEKA development version.

The latest step is to create an actual instance. I am using the WEKA development version in this code (as of the date of this post), so we have to use a DenseInstance object. However, if you make use of the stable version, then you can use Instance (link to the stable version doc), and must change this code to:

Instance instance = new Instance(2);

As a note, I have commented in the code a different way of setting the value of the second attribute. I must note that we do not set the value of the first attribute, as it is unknown.

The rest of the methods are (more or less) straightforward if you follow the documentation (weka - Programmatic Use, and weka - Use WEKA in your Java code). You get the class prediction on your text with the following lines:

double pred = classifier.classifyInstance(instances.instance(0)); System.out.println("Class predicted: " + instances.classAttribute().value((int) pred));

And if you feed this classifier with a file ( smstest.txt ) that stores the text "this is spam or not, who knows?", and the model learnt with MyFilteredLearner.java (that is stored in myClassifier.dat), then you get the following result:

$>javac MyFilteredClassifier.java $>java MyFilteredClassifier smstest.txt myClassifier.dat ===== Loaded text data: smstest.txt ===== this is spam or not, who knows? ===== Loaded model: myClassifier.dat ===== ===== Instance created with reference dataset ===== @relation 'Test relation' @attribute class {spam,ham} @attribute text string @data ?,' this is spam or not, who knows?' ===== Classified instance ===== Class predicted: ham

It is interesting to see that the class assigned to the instance before classifying it is "?", which means undefined or unknown.

For those interested on using the classifiers discussed in my previous posts (I mean including AttributeSelection , and using PART and SMO as classifiers), the only part of this code that you have to change is the learn() and evaluate() methods in MyFilteredLearner.java. Just play with it, and have fun.

Thanks for reading, and please feel free to leave a comment if you think I can improve this article, or you have questions or suggestions for futher articles on this topic!

Command Line Functions for Text Mining in WEKA

2013-04-01T18:21:00.000+02:00

In previous posts I have explained how to chain filters and classifiers in WEKA, in order to avoid incorrect results when evaluating text classifiers by using cross-fold validation, and how to integrate feature selection in the text classification process. For this purpose, I have used the FilteredClassifier and the MultiFilter in the Explorer GUI provided by WEKA. Now it is time to do so in the command line.

WEKA essentially provides three usage modes:

Using the Explorer, and other GUIs like the Experimenter, which allow to setup experiments and to examine the results graphically.
Using the command line functions, which allow to setup filters, classifiers and clusterers with plenty of configuration options.
Using the classes programmatically, that is, in your own programs in Java.

One major difference between modes 1 and 2 is that in the first mode, you spend some of the memory in the GUI, while in the second one, you do not. That can be a significant difference when you load big datasets. In both cases you can control the memory assigned to WEKA using Java command line options like -Xms, -Xms and so, but it may be interesting to save the memory used in the graphic elements in order to be able to deal with bigger datasets.

I will deal with the usage of WEKA in your programs in the future, in this post I focus on the command line. Before trying the following examples, please ensure weka.jar is added to your CLASSPATH. The first thing we must know is that WEKA filters and classifiers can be called in the command line, and that the call without arguments will show their configuration options. For instance, when you call a rule learner like PART (which I used in my previous posts), you get the following options:

$>java weka.classifiers.rules.PART Weka exception: No training file and no object input file given. General options: -h or -help Output help information. -synopsis or -info Output synopsis for classifier (use in conjunction with -h) -t <name of training file> Sets training file. -T <name of test file> Sets test file. If missing, a cross-validation will be performed on the training data. ... Options specific to weka.classifiers.rules.PART: -C <pruning confidence> Set confidence threshold for pruning. (default 0.25) ...

I omit the full list of options. Options are divided into two groups, those that are accepted by any classifier and those specific to the PART classifier. General options include three usage modes:

Evaluating the classifier on the training collection it self, possibly using cross validation, or on a test collection.
Training a classifier and storing the model in a file for further use.
Training a classifier and getting its output (classification of instances) on a test collection.

However, when calling a filter in the command line, the input file (the dataset) is read from the standard input, so you have to redirect the input from your file by using the appropriate operator (<), or to use the option -h to get the options of the filter.

In my previous post on chaining filters and classifiers, I performed an experiment running a PART classifier on an ARFF-formatted subset of the SMS Spam Collection, namely the smsspam.small.arff file. As every instance is of the form [spam|ham],"message text", we have to transform the text of the message into a term weight vector by using the StringToWordVector filter. You can combine the filter and the classifier evaluation into one command by using the FilteredClassifier class as in the following command:

$>java weka.classifiers.meta.FilteredClassifier -t smsspam.small.arff -c 1 -x 3 -v -o -F weka.filters.unsupervised.attribute.StringToWordVector -W weka.classifiers.rules.PART

To get the following output:

=== Stratified cross-validation === Correctly Classified Instances 173 86.5 % Incorrectly Classified Instances 27 13.5 % Kappa statistic 0.4181 Mean absolute error 0.1625 Root mean squared error 0.3523 Relative absolute error 58.2872 % Root relative squared error 94.9031 % Total Number of Instances 200 === Confusion Matrix === a b <-- classified as 13 20 | a = spam 7 160 | b = ham

Which is exactly the one I showed in my previous post. I have used the following general options:

-t smsspam.small.arff to specify the dataset to train (and on default, to evaluate on by using cross-validation).
-c 1 to specify the first attribute as the class.
-x 3 to specify that the number of folds to be used in the cross-validation evaluation is 3.
-v and -o to avoid outputting the classifiers and statistics on the training collection, respectively.

Plus the specific options of the FilteredClassifier -F to define the filter, and -W to define the classifier.

In my subsequent post on chaining filters, I proposed to make use of attribute selection to improve the representation of our learning problem. This can be done by issuing the following command:

$>java weka.classifiers.meta.FilteredClassifier -t smsspam.small.arff -c 1 -x 3 -v -o -F "weka.filters.MultiFilter -F weka.filters.unsupervised.attribute.StringToWordVector -F \"weka.filters.supervised.attribute.AttributeSelection -E weka.attributeSelection.InfoGainAttributeEval -S \\\"weka.attributeSelection.Ranker -T 0.0\\\"\"" -W weka.classifiers.rules.PART

To get the following output:

=== Stratified cross-validation === Correctly Classified Instances 167 83.5 % Incorrectly Classified Instances 33 16.5 % Kappa statistic 0.1959 Mean absolute error 0.1967 Root mean squared error 0.38 Relative absolute error 70.53 % Root relative squared error 102.3794 % Total Number of Instances 200 === Confusion Matrix === a b <-- classified as 6 27 | a = spam 6 161 | b = ham

Which in turn, it is the same I got in that post. If we replace PART by the SMO implementation of Support Vector Machines included in WEKA (by changing weka.classifiers.rules.PART to weka.classifiers.functions.SMO), we get the accuracy figure of 91%, as described in the post.

While most of the options are the same as in the previous command, two things deserve special attention in this one:

We chain the StringToWordVector and the AttributeSelection filters by using the MultiFilter described in the previous post. The order of calls is obviously relevant, as we first need to tokenize the messages into words, and then selecting the most informative words. Moreover, while we apply StringToWordVector with the default options, the AttributeSelection filter makes use of the InfoGainAttributeEval function as quality metric, and the Ranker class as the search method. The Ranker class is applied with the option -T 0.0 in order to specify that the filter has to rank the attributes (words or tokens) according to the quality metric, but to keep only which score is over the threshold defined by T, that is 0.0.
As the order of options is not relevant, it is required to link the options to the appropriate class by using the quotation mark symbol ("). Unfortunately, we have three nested expressions:
- The whole MultiFilter filter, enclosed by the isolated quotation marks (").
- The AttributeSelection filter, enclosed by the escaped quotation mark (\").
- The Ranker search method, enclosed by the double escaped quotation mark (\\\"). Here we escape the escape symbol itself (\) along with the quotation mark.
So many escaping symbols make it a bit dirty, but still functional.

Si I have shown how we can chain filters and classifiers, and apply several chained filters as well, in the command line. In next posts I will explain how to train, store and then evaluate a classifier by using the command line, and how to make use of WEKA filters and classifiers in your Java programs.

Thanks for reading, and please feel free to leave a comment if you think I can improve this article!

NOTE: You can find the collection I used in this post, along with other stuff related to WEKA and text mining in my Text Mining in WEKA page.

Text Mining in WEKA Revisited: Selecting Attributes by Chaining Filters

2013-02-11T10:50:00.001+01:00

Two weeks ago, I wrote a post on how to chain filters and classifiers in WEKA, in order to avoid misleading results when performing experiments with text collections. The issue was that, when using N Fold Cross Validation (CV) in your data, you should not apply the StringToWordVector (STWV) filter on the full data collection and then perform the CV evaluation on your data, because you would be using words that are present in your test subset (but not in your training subset) for each run. Moreover, the STWV filter can extract and use simple statistics to filter out the terms (e.g. minimum number of occurrences), but those statistics over the full collection are not valid because in each CV run you use only a subset of it.

Now I would like to deal with a more general setting in which you want to apply dimensionality reduction because, in general text classification tasks, the documents or examples are represented by hundreds (if not thousands) of tokens, what makes the classification problem very hard for many learners. In WEKA, this involves using the AttributeSelection filter along with the STWV one. Before thinking about dimensionality reduction, we must reflect a bit about it.

Dimensionality reduction is a typical step in many data mining problems, which involves transforming our data representation (the schema of our table, the list of current attributes) into a shorter, more compact, and hopefully, more predictive one. Basically, this can be done in two ways:

With feature reduction, which maps the original representation (list of attributes) onto a new and more compact one. The new attributes are synthetic, that is, they somehow combine the information from subsets of the original ones which share statistical properties. Typical feature reduction techniques include algebraic analysis methods like Principal Component Analysis (PCA) and Singular Value Decomposition (SVD). In text analysis, the most popular method is, by far, Latent Semantic Analysis, which involves obtaining the principal components or buckets into the term-to-document sparse matrix.
With feature selection, which just selects a subset of the original representation attributes, according to some Information Theory quality metric like Information Gain or X^2 (Chi-Square). This method can be far more simple and less time consuming than the previous one, as you only have to compute the value of the metric for each attribute, and rank the attributes. Then you simply decide a threshold in the metric (e.g. 0 for Information Gain) and keep the attributes with a value over it. Alternatively, you can choose a percentage of the number of original attributes (e.g. 1% and 10% are typical numbers in text classification), and just keep those top ranking ones. However, there are other more time consuming alternatives, like exploring the predictive power of subsets of attributes using search algorithms.

A major difference between both methods is that feature reduction leads to synthetic attributes, but feature selection just keeps some of the original ones. This may affect the ability of the data scientist to understand the results, as synthetic attributes can be statistically relevant but meaningless. Another difference is that feature reduction does not make use of the class information, while feature selection does. In consequence, the second method is very likely to lead to a more predictive subset of attributes than the original one. But beware, more theoretical predictive power does not always mean more effectiveness. I recommend to read the old (?) but always helpful paper by Yimming Yang & Jan Pedersen on the topic.

The WEKA package supports both methods, mainly with the weka.attributeSelection.PrincipalComponents (feature reduction) and weka.filters.supervised.attribute.AttributeSelection (feature selection) filters. But an important question is: Do you really need to make dimensionality reduction in text analysis? There are two clear arguments against it:

Some algorithms get no hurt with using all the features, even if they are really many and very sparse. For instance, Support Vector Machines excel in text classification problems exactly for that: they are able to deal with thousands of attributes, and they get better results when no reduction is performed. A typical text classification problem in which dimensionality reduction can be a big mistake is spam filtering.
If it is a matter of computing time, like e.g. in symbolic learners like decision trees (C4.5) or rules (Ripper), then there is no worry. Big Data techniques come to help, as you can configure cheap and big clusters over e.g. Hadoop to perform your computations!

But having the algorithms in my favourite data analysis package, and knowing that sometimes they lead to effectiveness improvements, why not using them?

Because of the reasons above, I will focus on feature selection. In consequence, I will deal with the AttributeSelection filter, leaving the PrincipalComponents one for another post. Let us start with the same text collection that I used in my previous post about chaining filters and classifiers in WEKA. It is an small subset of the SMS Spam Collection, made with the first 200 messages for brevity and simplicity.

Our goal is to perform a 3-fold CV experiment with any algorithm in WEKA. But, in order to do it correctly, we know we must chain the STWV filter with the classifier by using the FilteredClassifier learner in WEKA. However, we want to perform feature selection as well, and the FilteredClassifier allows us to chain a single filter and a single classifier. So, how to combine both the STWV and the AttributeSelection filters into a single one?

Let us start doing it manually. After loading the dataset into the WEKA Explorer, applying the STWV filter with the default settings, and setting the class attribute to the "spamclass" one, we get something like this:

Now we can either go to the "Select attributes" tab, or just stay in the "Preprocess" tab and choose the AttributeSelection filter. I opt for the second way, so you can browse the filters folder by clicking on the "Choose" button at the "Filters" area. After selecting the "weka > filters > supervised > attribute > AttributeSelection", you can see the selected filter in the "Filters" area, as shown in the next picture:

In order to set up the filter, we can click on the name of the filter. The "weka.gui.GenericObjectEditor" window we get is a generic window that allows to configure filters, classifiers, etc. according to a number of object-defined properties. In this case, it allows us to set up the AttributeSelection filter configuration options, which are:

The evaluator, which is the quality metric we use to evaluate the predictive properties of an attribute or a set of them. There you can choose among a wide number of them (which depends on your WEKA version), including specially Chi Square (ChiSquaredAttributeEval), Information Gain (InfoGainAttributeEval), and Gain Ratio (GainRatioAttributeEval).
The search algorithm, which is the way we will select the remaining group of attributes, and includes very clever but time consuming group search algorithms, and my favourite one, the Ranker (weka.attributeSelection.Ranker). This one just ranks the attributes according to the chosen quality metric, and keeps those meeting some criterion (like e.g. having a value over a predefined threshold).

In the next picture, you can see the AttributeSelection configuration window with the evaluator set up to Information Gain, and the search set up as Ranker, with the default options.

The Ranker evaluator has two main properties:

The numToSelect property, which defines the number of attributes to keep, an Integer number that is -1 (all) by default.
The threshold property, which defines the minimum value that an attribute has to get in the evaluator in order to be kept. The default value for this property is the minimum Long integer in Java.

In consequence, if we want to keep those attributes scoring over 0, we have just to write that number in the threshold area of the window we get when we click on the Ranker at the previous window:

By clicking OK on all the previous windows, we get a configuration of the AttributeSelection filter which involves keeping those attributes with Information Gain score over 0. If we apply that filter to our current collection, we get the following result:

As you can see, we get a ranked list of 82 attributes (plus the class one), in which the top scoring attribute is the token "to". This attribute occurs in 69 messages (value 1), but many of them are spam ones, so it is quite predictive for this particular class. We can see as well that we only keep a 5.93% of the original attributes (82 over 1382).

Now we can go to the "Classify" tab and select the rule learner PART ("weka > classifiers > rules > PART") to be evaluated on the training collection itself ("Test options" area, "Use training set option"), getting the next result:

We get an accuracy of 95.5%, much better than the results I reported in my previous post. Of course, these results cannot be compared because this quick experiment is a test on the training collection, not done with 3-fold CV and the FilteredClassifier. But if we want to run a CV experiment, how to do it as we have 2 filters instead of one, in our set up?

What we need now is to start with the original text collection in ARFF format (no STWV yet), and to use the MultiFilter that WEKA provides for these situations. We start then with the original collection, and go to the "Classify" tab. If we try to choose any classic learner (J48 for the C4.5 decision tree learner, SMO for Support Vector Machines, etc.), it will be impossible because we have just one attribute (the text of the SMS messages) along with the class, but we can use the weka.classifiers.meta.FilteredClassifier. After selecting it, we will see something similar to the next picture:

If we click on the name of the classifier at the "Classifier" area and we select weka.classifiers.rules.PART as the classifier (with default options), we get the next set up in the FilteredClassifier editor window:

Then we can choose the weka.filters.MultiFilter in the filter area, which starts with a dummy AllFilter. Time to set up our filter combining STWV and AttributeSelection. We click on the filter name area and we get a new filter edition window with an area to define the filters to be applied. If we click on it, we get a new window that allows to add, configure and delete filters. The selected filters will be applied in the order we add them, so we start deleting the AllFilter and adding a STWV filter with the default options, getting something similar to the next picture:

Filters are added by clicking on the "Choose" button to select them, and clicking on the "Add" button to add them to the list. We can now add the AttributeSelection filter with the Information Gain evaluator and the Ranker with threshold 0 search, by editing the filter when clicking on the "Edit" button with the AttributeSelection filter selected in the list. If you manually re-dimension the window, you can see a set up similar to this one:

The set up is nearly finished. We close this window by clicking on the "X" button, and click on the "OK" button at the MultiFilter and FilteredClassifier windows. In the "Classify" tab at the explorer, we select "Cross-validation" in the "Test options" area, entering 3 as the number of folds, and we select the class attribute as "spamclass". Having done this, we can just click on the "Start" button to get the next result:

So we get an accuracy of 83.5%, which is worse than the one we got without using feature selection (which was 86.5%). Oh oh, all this clever (?) set up to get a drop of 3 points in accuracy! :-(

But what happens if, instead of using a relatively weak learner on text problems like PART, we turn to Support Vector Machines? WEKA includes the weka.classifiers.functions.SMO classifier, which implements John Platt's sequential minimal optimization algorithm for training a support vector classifier. If we choose this classifier with default options, we get a quite different results:

Using only the STWV filter, we get an accuracy of 90.5% with 18 spam messages classified as legitimate ("ham"), and 1 false positive.
Using the MultiFilter with AttributeSelection in the same setup, we get an accuracy of 91% with 16 spam messages classified as ham, and 2 false positives.

So we get an improvement of accuracy on a more accurate learner, what is nice. However, the difference is just 0.5% (1 message in our 200 instances collection), so it is moderate. Moreover, we get one more false positive, what is bad for this particular problem. In spam filtering, it is much worse to make a false positive (sending a legitimate message to the spam folder) than the opposite, because the user has the risk to miss an important message. Check my paper on cost sensitive evaluation of spam filtering at ACM SAC 2002.

But all in all, I expect this post shows the merits of feature selection in text classification problems, and how to do it with my favourite library, WEKA. Thanks for reading, and please feel free to leave a comment if you think I can improve this article!

Text Mining in WEKA: Chaining Filters and Classifiers

2013-01-29T13:21:00.001+01:00

One of the most interesting features of WEKA is its flexibility for text classification. Over the years, I have had the chance to make a lot of experiments on text collections with WEKA, most of them in supervised tasks that are commonly mentioned as Text Categorization, that is, classifying text segments (documents, paragraphs, collocations) into a set of predefined classes. Examples of Text Categorization tasks include assigning topics labels to news items, classifying email messages into folders, or, more close to my research, classifying messages as spam or not (Bayesian spam filters) and web pages as inappropriate or not (e.g. pornographic content vs. educational resources).

WEKA support for Text Categorization is impressive. A prominent feature is that this package supports breaking text utterances into indexing terms (word stems, collocations) and assigning them a weight in term vectors, a required step in nearly every text classification task. This tokenization and indexing process is achieved by using a super-flexible filter named StringToWordVector. Lets me show an example of how it works.

I will start with a simple text collection, which is an small sample of the publicly available SMS Spam Collection. Some colleagues and me built this collection for experimenting with Bayesian SMS spam filters, and it contains 4,827 legitimate messages and 747 mobile spam messages, for a total of 5,574 short messages collected from several sources. I will make use of an small subset in order to better show my points in this post. The subset is made with the first 200 messages, and it is the following one right formatted in the suitable WEKA ARFF format:

@relation sms_test

@attribute spamclass {spam,ham}
@attribute text String

@data
ham,'Go until jurong point, crazy.. Available only in bugis n great world la e buffet... Cine there got amore wat...'
ham,'Ok lar... Joking wif u oni...'
spam,'Free entry in 2 a wkly comp to win FA Cup final tkts 21st May 2005. Text FA to 87121 to receive entry question(std txt rate)T&C\'s apply 08452810075over18\'s'
ham,'U dun say so early hor... U c already then say...'
ham,'Nah I don\'t think he goes to usf, he lives around here though'
spam,'FreeMsg Hey there darling it\'s been 3 week\'s now and no word back! I\'d like some fun you up for it still? Tb ok! XxX std chgs to send, £1.50 to rcv'
...
ham,'Hi its Kate how is your evening? I hope i can see you tomorrow for a bit but i have to bloody babyjontet! Txt back if u can. :) xxx'

In the first 200 messages of the collection, 33 of them are spam and 167 are legitimate ("ham"). This collection can be loaded in the WEKA Explorer, showing something similar to the following window:

The point is that messages are featured as string attributes, so you have to break them into words in order to allow learning algorithms to induce classifiers with rules like:

if ("urgent" in message) then class(message) == spam

Here is where the StringToWordVector filter comes to help. You can just select it by clicking the "Choose" button in the "Filter" area, and browsing the folders to "weka > filters > unsupervised > attribute" one. Once selected, you should be able to see something like this:

If you click on the name of the filter, you will get a lot of options, which I leave for another post. For the my goals in this one, you can just apply this filter with the default options to get an indexed collection of 200 messages and 1,382 indexing tokens (plus the class attribute), shown in the next picture:

If you want to see colors showing the distribution of attributes (tokens) according to the class, you can just select the "class" attribute as the class for the collection in the bottom-left area of the WEKA Explorer. So, you can see that the attribute "Available" occurs just in one message, which happens to be a legitimate (ham) one:

Now, we can make our experiments in the Classify tab. We can just select cross-validation using 3 folds (1), point to the appropriate attribute to be used as a class (which is the "spamclass" one) (2), and select a rule learner like PART in the classifier area (3). You can find that classifier at the "weka > classifiers > rules" folder when clicking on the "Choose" button at the "Classifier" area. This setup is shown in the next figure:

The selected evaluation method, cross-validation, instructs WEKA to divide the training collection into 3 sub-collections (folds), and perform three experiments. Each experiment is done by using two of the folds for training, and the remaining one for testing the learnt classifier. The sub-collections are sampled randomly, the way that each instance belong only to one of them, and the class distribution (50% in our example) is kept inside each fold.

So, if we click on the "Start" button, we will get the output of our experiment, featuring the classifier learnt over the full collection, and the values for the typical accuracy metrics averaged over the three experiments, along with the confusion matrix. The classifier learnt over the full collection is the following one:

PART decision list
------------------

or <= 0 AND
to <= 0 AND
2 <= 0: ham (119.0/3.0)

£1000 <= 0 AND
FREE <= 0 AND
call <= 0 AND
Reply <= 0 AND
i <= 0 AND
all <= 0 AND
final <= 0 AND
50 <= 0 AND
mobile <= 0 AND
ur <= 0 AND
text <= 0: ham (26.0/2.0)

i <= 0 AND
all <= 0: spam (30.0/3.0)

: ham (25.0/1.0)

Number of Rules : 4

This notation can be read as:

if (("or" not in message) and ("to" not in message) and ("2" not in message)) then class(message) == ham
...
otherwise class(message) == ham

And the confusion matrix is the next one:

=== Confusion Matrix ===

a b <-- classified as
17 16 | a = spam
12 155 | b = ham

Which means that the PART learner is able to get 17+155 correct classifications, and it makes 12+16 mistakes. It leads to an accuracy of 86%.

But we have done it wrong!

Do you remember the "Available" token, which occurs only on one of the messages? In which fold is it? When it is on a training fold, we are using it for training (making the learner trying to generalize from a token that does not occur in the test collection). And when it is on the test collection, the learner should not even know about it! Moreover, what happens with attributes that are highly predictive for the full collection (according to their statistics when computing e.g. the Information Gain metric)? They may have worse (or better) statistics when a subset of their occurrences is not seen, as they can be on the test collection!

The right way to perform a correct text classification experiment with cross validation in WEKA is feeding the indexing process into the classifier itself, that is, chaining the indexing filter (StringToWordVector) and the learner, the way that we index and train for every sub-set in the cross-validation run. Thus, you have to use the FilteredClassifier class provided by WEKA.

In fact, this is not that difficult. Let us go back to the original test collection, which features two attributes: the message (as a string) and the class. Then you can go to the Classify tab, and choose the FilteredClassifier learner, which is available at the "weka > classifiers > meta", and shown in the next picture:

Then you must choose the filter and the classifier you are going to apply to the collection, by clicking on the classifier name at the "Classifier" area. I choose StringToWordFilter and PART with their default options:

If we now run our experiment with 3-fold cross-validation and the filtered classifier we have just configured, we get different results:

=== Confusion Matrix ===

a b <-- classified as
13 20 | a = spam
7 160 | b = ham

For an accuracy of 86.5%, a bit better than the one obtained with the wrong setup. However, we catch 4 less spam messages, and the True Positive ratio goes down from 0.515 to 0.394. This setup is more realistic and it better mimics what will happen in the real world, in which we will find highly relevant but unseen events, and our statistics may change dramatically over time.

So now we can run our experiment safely, as no unseen events will be used in the classification. Moreover, if we apply any kind of Information Theory based filter like e.g. ranking the attributes according to their Information Gain value, the statistics will be correct, as they will be based on the training set for each cross-validation run.

Thanks for reading, and please feel free to leave a comment if you think I can improve this article!

A note on WEKA limitations and big data

2013-01-16T19:13:00.001+01:00

I love WEKA since it was first introduced to me by my friend Enrique Puertas back in 1999, when he used it for programming a Usenet News client with spam filtering capabilities based on Machine Learning (what we usually call a bayesian spam filter now). I got impressed by its flexibility and functionality, and the ease of experimenting with WEKA and using it in my Java programs. I quickly got familiar with it and I used it for making my very first experiments on spam filtering.

Over the years, WEKA has being updated, getting more algorithms and making some tasks easier for text miners. For instance, the StringToWordVector filter allows to get a Vector Space Model (or bag of words) representation of your problem texts, a task that I had to do manually (with my own programs or scripts) at the beginning. Another example: the Sparse ARFF format allows to get a compact representation of your word vectors, instead of getting thousands of attribute values per instance, most of them being "0" or "no". Moreover, WEKA has attracted so much attention that other platforms have integrated it (e.g. GATE) or provided covering environments that augment its functionality (e.g. RapidMiner).

However, our needs as researchers have evolved as well. One of the most important issues now is data size. While working with average computers in my early experiments was enough, given the size of standard collections (20 Newsgroups, Reuters-21578, LingSpam, etc. - all of the order of tens of thousand instances), now that is nearly impossible. Most of my experiments involve from hundreds of thousand to millions of instances. In those cases, WEKA can spend days for a single learn-and-test cycle, or it can simply run out of memory; and not with an average machine, even with a really big server!

So now, what?

Before dealing with this question, I must say that I have been a heavy user of the WEKA command line and the Explorer GUI . However, I have never considered or used the WEKA Experimenter GUI . I know from friends and diagonal readings that the Experimenter allows to distribute experiments over a number of machines. However, if I am going to distribute my experiments, why not using newer technologies (less ad-hoc, WEKA-dependent), just 100% compatible/standard/implemented with-in cloud providers? Why not getting advantage of elastic cloud capabilities (grow and pay as you need)?

Given said this, and keeping up with the latest news and trends in data and text mining, I see two options:

Going for R . This language/platform has grown incredibly in the latest years, and it has quickly became a standard language for data mining, present in many curricula, and much often considered an absolute requirement in data science job offers. There are nice books about it as well, like "R in a Nutshell", and other strategical books recommend/use it (like "The Elements of Statistical Learning"). R supports map reduce algorithms over Hadoop for distributed experiments with tons of data. And R interfaces with Java as well.
Choosing Mahout (plus Lucene/SOLR ). This platform is Java-based, tightly integrated with Hadoop, and it makes use of Lucene for text representation tasks -- Lucene could be considered a standard for deploying search engines now. There are good books on Mahout and Lucene/SOLR as well ("Mahout in Action", "Lucene in Action", "Apache SOLR Cookbook").

But still I do not feel any option is better than the other one. Both are challenging and appealing, and I have not taken a decision yet. And I am willing to hear your opinion, of course.

A list of datasets for opinion mining in Twitter

2013-01-10T19:14:00.000+01:00

In a recent thread at the SentimentAI group (list), a number of links to datasets for training / testing opinion mining / sentiment classifiers over Twitter have been contributed. I list them here for the case somebody considers this information useful:

Three datasets provided by Hassan Saif, including an annotated subset of the Stanford Twitter Sentiment Corpus, and two for the specific topics of the Health Care Reform and the Obama-McCain Debate.
The Stanford Twitter Corpus itself, provided by Alec Go and others at Sentiment140. You can download the ST Corpus directly (70Mb).
The Sanders Analytics Twitter Sentiment Corpus, provided by Niek Sanders.
The mejaj datasets, provided by Nibir Bora and others.
The SemEval-2013: Sentiment Analysis in Twitter evaluation campaign (or competition) dataset. Note the competition is still active, you can join it! Check the dates at the SemEval-2013 website.
The RepLab 2012 Profiling task dataset. The profiling task is a bit different from the standard sentiment classification task. For instance, factual tweets can imply bad reputation ("Lehmann Brothers goes bankrupt") and negative sentiment tweets can imply good reputation ("R.I.P. Michael Jackson. We'll miss you").

You can find the SentimentAI thread on Twitter datasets here.

Spam en LinkedIn al estilo "Robin Sage"

2013-01-08T16:55:00.000+01:00

Yo mismo, y algunos de mis contactos en LinkedIn, han recibido recientemente una solicitud de contacto por parte de una tal "Elena Domínguez" (enlace*). Se trata de un perfil un poco extraño, por cuanto está bastante poco detallado (experiencia profesional, formación, etc.), pero pertenece a varios grupos de ingenieros (se auto-califica como ingeniera), pero tiene cientos de contactos sumamente heterogéneos de temas TIC. Ésta es la imagen del perfil:

Si se acepta a esta "persona", en pocos días (u horas), se recibirá un correo invitando a unirse al grupo de LinkedIn "International Master's in Theoretical & Practical Application of Finite Element Method" (enlace*). Aunque el master promocionado mediante este grupo de LinkedIn parece razonablemente legítimo, tanto el perfil como el grupo parecen ser spam.

Una cosa que llama especialmente la atención es que su foto de perfil es bastante rara, como "demasiado aséptica", casi artificial. Una evidencia adicional de spam la obtenemos cuando realizamos una búsqueda por imágenes en Google, usando esta imagen como consulta. Primero obtenemos la URL de la imagen:

A continuación, buscamos la foto en Google Images, pulsando sobre el botón de la cámara e introduciendo la URL que hemos obtenido antes:

Y los resultados son los siguientes:

A partir de estos resultados, se puede deducir con bastante certeza que la foto es de "stock", es decir, de catálogo, y que aparece en varios catálogos como imagen de archivo de mujer de negocios con expresión neutra, realizada en estudio. Usar una foto como esta para nuestro perfil en una red como LinkedIn es posible, pero bastante poco probable.

Por tanto, considero esta fotografía como una evidencia fuerte que, unida al comportamiento del "usuario" (enviando el correo de invitación a un grupo tan focalizado en un producto educativo) como al número tan alto de contactos para un perfil tan poco detallado), me lleva a pensar que se trata de un perfil de spam, pero real en el sentido de que no es un experimento de ingeniería social como el realizado por Thomas Ryan con el perfil " Robin Sage ".

Como conclusión, pienso que hasta LinkedIn, que es una de las redes menos explotadas para el spam, se irá viendo invadida crecientemente por este fenómeno, cada vez con mayor nivel de personalización y sofisticación.

(*) No asocio el enlace al nombre del perfil o del grupo para no generar spam web.

Report on ERA Course: Fighting Child Pornography on the Internet

2012-12-04T15:16:00.004+01:00

I have had the pleasure of attending as a student to the European Academy of Law course on "Fighting Child Pornography on the Internet", at Madrid 29-30 November 2012. I was supported by the Spanish child protection NGO Protégeles, as I work with then whenever I can in order to push their mission.

It was a nice course, with a good coverage of topics, including legal aspects, and technical issues both from the view of prosecuting sex offenders and from Web filtering. Speakers were excellent and provided a lok of useful hints and links. I also crafted a backlog hashtag for the event in Twitter (#ERAChildPornCourse), but I am afraid that neither attendents nor speakers are very happy with Twitter (with scarce exceptions). I collected some comments during the event, organized in terms of the topic:

Legal issues

Media types that do not involve real children are child porn?
Internet and digital cameras have led to an explosion of child porn, now a home industry
There is a thousand years history on child porn (e.g. paintings) but cameras imply children are really abused to get it recorded
What does mean child porn possesion? What about cloud drives? And streaming?
Internet is world-wide, so who has the jurisdiction? Should anybody have it?
Eurojust helps coordination of child porn prosecution, examples of operations: "lost boy", "nanny", "dreamboard"
Lanzarote Convention says accesing a child porn site, if knowing it hosts that stuff, is illegal
Providing lists of links of web sites hosting child porn is illegal under Lanzarote Convention

Protection, prosecution, technical issues

For preparing cases against child porn, prosecutors check nature of material, offender involvement and number of images
The 10% of photographs ever taken, were taken during the latest year Note: all kind of pics
Groomers and child sex offenders play "the jailbait game" in vidro chat sites
Youngsters are extemely vulnerable to grooming: they nearly accept all frienship requests, have 3-4k+ contacts
Haebephilia is the sexual preference for individuals in early years of puberty (generally 11-14)
LEAs make use of a plethora of image analysis tools to process suspect pics; Microsoft PhotoDNA just one in the box
About 20% of child porn stuff is delivered through commercial platforms
Project HAVEN aims at stop child abuse by EU citizens in foreign countries (Asia, South America...)
Law Enforcement Agencies cooperate and share a Child Abuse International database
Law Enforcement Agencies (e.g. Europol) are getting more and more focused on victim identification
INHOPE has not authority to release block lists of child porn sites

An aditional fact is that after hearing Interpol and Europol, one gets proud of having such great professionals working against child porn.

All in all, it has been a great course and I am very happy of being able to attend to it.

Artículo en Novática: comprometiendo la seguridad de reCAPTCHA

2012-05-17T12:31:00.000+02:00

En el número 215 de Novática hemos publicado un artículo que versa sobre la utilización de diversas técnicas de normalización de imagen y el OCR Tesseract de Google para realizar ataques de reconocimiento de texto sobre dos versiones de reCAPTCHA. La referencia del artículo es:

Noemí Carranza, Ricardo Palma Durán, Gonzalo Álvarez Marañón, José María Gómez Hidalgo, 2012. Análisis de la seguridad del sistema reCAPTCHA. Revista Novática 215, enero-febrero 2012, pág. 43-48.

El resumen del artículo es el siguiente:

En los últimos tiempos se han popularizado extraordinariamente los sistemas CAPTCHA, que protegen servicios Web planteando al usuario una prueba destinada a verificar que se trata de un ser humano y no de un robot, o sistema automático para el envío de correo basura o difusión de malware. Estos sistemas están siempre expuestos a que spammers y hackers sean capaces de comprometer su seguridad, y abusar de los recursos subyacentes (cuentas de correo, blogs, etc.) para realizar sus actividades ilícitas. Por ello, es necesario comprobar periódicamente su seguridad usando herramientas como sistemas de reconocimiento óptico de caracteres (OCR), sistemas de análisis de imagen, y otras. En este artículo realizamos un análisis de la seguridad del sistema reCAPTCHA, que probablemente es el más usado en Internet actualmente. Para ello, utilizamos diversas técnicas de análisis de imagen orientadas
a corregir las deformaciones y distorsiones realizadas por el sistema en las imágenes que muestra al usuario, así como el eficaz sistema de OCR Tesseract. Se han analizado dos versiones del sistema reCAPTCHA y se ha comprobado que la seguridad del sistema probablemente ha aumentado en la segunda versión, más reciente, aunque es posible comprometer la seguridad del sistema si se cuenta con recursos suficientes en forma de una botnet de tamaño medio (unos 10.000 ordenadores).

In-progress competitions in Data and Text Mining

2012-05-07T06:44:00.000+02:00

The following competitions in Data and Text Mining are open to participation:

MediaEval 2012 - Multimedia Benchmark Evaluation - Several tasks including: Placing Task, Social Event Detection Task, Spoken Web Search Task, Tagging Task, Affect Task: Violent Scenes Detection, Visual Privacy Task.
Million Song Dataset Challenge: a large-scale, open evaluation of personalized music recommendation algorithms.
CLEF 2012: Several tasks related to Information Access Evaluation in Multilinguality, Multimodality, and Visual Analytics, including:
- CHiC : Cultural Heritage in CLEF, a pilot evaluation lab that aims at moving towards a systematic and large-scale evaluation of cultural heritage digital libraries and information access systems.
- CLEF-IP: IR in the patents domain, which provides a large collection of XML documents representing patents and patent images.
- ImageCLEF: Cross Language Image Retrieval, which evaluates the cross-language annotation and retrieval of images by focusing on the combination of textual and visual evidence.
- INEX : INitiative for the Evaluation of XML Retrieval
- PAN: Uncovering Plagiarism, Authorship, and Social Software Misuse. This includes the sexual predator identification task.
- QA4MRE: Question Answering for Machine Reading Evaluation, its goal is to evaluate Machine Reading abilities through Question Answering and Reading Comprehension Tests.
- RepLab: An Evaluation Campaign for Online Reputation Management Systems.
Simulated car racing championship: its goal is to design a controller for a racing car that will compete on a set of unknown tracks first alone (against the clock) and then against other drivers.
Europeana Hack4Europe! 2012: inviting developers and designers to try out their ideas for creative re-use of the Europeana content and build applications showcasing the social and business value of open cultural data.
Yahoo! News: ICML exploration and exploitation challenge on recommending Yahoo! news item using click logs.

CFP: RECSI 2012 : XII Spanish Meeting on Criptology and Information Security

2012-02-28T05:49:00.000+01:00

XII Spanish Meeting on Criptology and Information Security - RECSI 2012
Donostia-San Sebastian, Spain
September 4-7, 2012

The Information Society is a reality involving principal actors: Companies, Government, Scientific and Education Agents and Society as a whole. Scientific actors provide knowledge, that, with the support of the Government and a transformation to technology by Companies, must respond to the demand of the society in short, medium and long term. Computer Security is needed to ensure the correct use of Information Technology and Communication by Society.

The Spanish Meeting on Cryptology and Information Security (RECSI) is the Spanish reference scientific Conference in the field. Every two years the most important national researchers attend this event, and renowned foreign researchers are invited. In the meeting recent advances in security will be presented to the main agents of the Information Society, in order to provide a forum for exchanging ideas, increase knowledge and share experiences in the field of Security.

For this reason, Mondragon University is organizing the RECSI in order to bring together most of the research groups and the most important companies that work in: design of methods to protect the information (cryptography), analyze these methods to discover vulnerabilities (cryptanalysis), and create and analyze methods for the protection of computer systems and communication networks (Information Security).

In September 2012, its twelfth edition will take place in Donostia-San Sebastián. Previous editions were held in Palma de Mallorca (1991), Madrid (1992), Barcelona (1994), Valladolid (1996), Torremolinos (1998), Santa Cruz de Tenerife (2000), Oviedo (2002), Leganés (2004), Barcelona (2006), Salamanca (2008) and Tarragona (2010).

All papers about information security are relevant, and selected topics include:

Cryptography and cryptoanalysis
Authentication and digital signatures
Cryptography Applications
Privacy and Anonymity
Watermarking and steganography
Access Control
Intrusion detection and traps
Malware Analysis
Spam detection
Security in Social Networks
Security in Embedded Systems
Computer Forensics

Important Dates

Deadline for paper submission: April 2, 2012
Acceptance notification: May 1, 2012
Conference: September 4-7, 2012

PAN 2012 Author Identification - Sexual Predator task, references and resources

2012-02-10T06:46:00.000+01:00

The PAN Labs (Uncovering Plagiarism, Authorship, and Social Software Misuse) is a series of scientific competitions that have been performed during the recent years, focused on applying automated text analysis to the detection of plagiarism, authorship attribution, and related tasks. Unlike other, more traditional text classification tasks like Text Categorization, the problems are modeled using style attributes (instead of content words), like frequencies of particular syntactic tags, specific collocations, approximate string matching, etc. As in other scientific competitions, the organizers provide a labeled tratining set of texts in order to refine both the input/output format and the algorithms, and the participants are required to run their software on a test set with unknown labels.

The PAN 2012 Lab will be held in Rome in September in conjunction with the CLEF 2012 conference. It features three tasks, being one of them Author Identification. This task focuses on identifying sexual predators in chat logs, and on authorship verification. The training data will be released on Mar 16, 2012.

For those willing to participate in this competition, I provide a series of resources that may help them.

First, the Perverted Justice website, run by the Perverted Justice Foundation Inc., features a big number of English-language chat logs from real sexual predators talking to volunteers acting as female youngsters. These archives are public and legal according to USA Laws. There is no danger on using them for research purposes.

Secondly, here is a list of papers that may be of interest for those willing to prepare an algorithm or system to join the PAN 2012 author identification task on detecting sexual predators. Not all of them are related with sexual predators, but with other child security problems in the Internet like cyberbullying as well:

Myriam Munezero, Tuomo Kakkonen and Calkin Montero, "Towards automatic detection of antisocial behavior from texts", IJCNLP 2011 Proceedings of the Workshop on Sentiment Analysis where AI meets Psychology (SAAIP). http://www.ijcnlp2011.org/proceeding/workshop/WS8_SAAIP/SAAIP-2011.pdf

McGhee, India, Jennifer Bayzick, April Kontostathis, Lynne Edwards, Alexandra McBride, and Emma Jakubowski. (2011). Learning to Identify Internet Sexual Predation. International Journal on Electronic Commerce. Volume 15, Number 3. Spring 2011

Karthik Dinakar, Birago Jones, Catherine Havasi, Henry, Lieberman, Rosalind Picard, "TimeOut: Commonsense Reasoning for Detection, Prevention, and Mitigation of Cyberbullying" ACM Transactions on Interactive Intelligent Systems, 2011, http://web.media.mit.edu/~lieber/Publications/Bullying-TiiS.pdf

Tibor Bosse and Sven Stam, "A Normative Agent System to Prevent Cyberbullying", In IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent Agent Technology 2011, http://www.cs.vu.nl/~tbosse/papers/IAT11-cyberbullying.pdf

Jennifer Bayzick, April Kontostathis and Lynne Edwards, "Detecting the Presence of Cyberbullying Using Computer Software", Poster presentation at WebSci11, June 14-17, 2011, Koblenz Germany. http://www.websci11.org/fileadmin/websci/Posters/63_paper.pdf

Dinakar K., Reichart R.,Lieberman, H., "Modeling the detection of textual cyberbullying", International Conference on Weblog and Social Media - Social Mobile Web Workshop, Barcelona, Spain 2011. http://www.aaai.org/ocs/index.php/ICWSM/ICWSM11/paper/download/3841/4384

Michal Ptaszynski, Pawel Dybala, Tatsuaki Matsuba, Fumito Masui, Rafal Rzepka, Kenji Araki, and Yoshio Momouchi, "In the Service of Online Order: Tackling Cyber-Bullying with Machine Learning and Affect Analysis", International Journal of Computational Linguistics Research, Vol. 1 , Issue 3, pp. 135-154, 2010. http://arakilab.media.eng.hokudai.ac.jp/~ptaszynski/data/Ptaszynski_IJCLR2010-Cyberbullying_2011.02.23.pdf

Michal Ptaszynski, Pawel Dybala, Tatsuaki Matsuba, Fumito Masui, Rafal Rzepka and Kenji Araki, "Machine Learning and Affect Analysis Against Cyber-Bullying", In Proceedings of The Thirty Sixth Annual Convention of the Society for the Study of Artificial Intelligence and Simulation of Behaviour (AISB'10), 29th March - 1st April 2010, De Montfort University, Leicester, UK, pp. 7-16, 2010. http://arakilab.media.eng.hokudai.ac.jp/~ptaszynski/data/AISB2010_Cyberbullying_paper.pdf

Kontostathis, April, Lynne Edwards, and Amanda Leatherman. (2009). Text Mining and Cybercrime In Text Mining: Application and Theory. Michael W. Berry and Jacob Kogan, Eds., John Wiley & Sons, Ltd. 2009. Link to data used in paper

Kontostathis, April, Lynne Edwards, Jen Bayzick, India McGhee, Amanda Leatherman and Kristina Moore. (2009). Comparison of Rule-based to Human Analysis of Chat Logs. 1st International Workshop on Mining Social Media (MSM09). Seville, Spain. Nov 2009.

Kontostathis, April, Lynne Edwards, and Amanda Leatherman. (2009). ChatCoder: Toward the Tracking and Categorization of Internet Predators. In Proc. Text Mining Workshop 2009 held in conjunction with the Ninth SIAM International Conference on Data Mining (SDM 2009). Sparks, NV. May 2009.

D. Yin, Z. Xue, L. Hong, B. D. Davison, A. Kontostathis, and L. Edwards, "Detection of Harassment on Web 2.0", In CAW 2.0 '09: Proceedings of the 1st Content Analysis in Web 2.0 Workshop, Madrid, Spain, 2009. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.151.8839&rep=rep1&type=pdf

Datasets, databases and resources: MSH WSD, BioNOT, Gazetiki, DBpedia Spotlight, Google BigQuery, Common Crawl

2011-11-23T10:13:00.000+01:00

Some datasets and resources I have recently found (although they may be old):

MSH WSD: a data set for Word Sense Disambiguation WSD based on a method that can be used to automatically develop a WSD test collection using the Unified Medical Language System (UMLS) Metathesaurus and the manual MeSH indexing of MEDLINE.
BioNOT: a searchable database of negated biomedical sentences. The database consists of more than 32 million negated sentences at PubMed.
Gazetiki: a geographical database that contains 8323702 geographical names coming from Geonames and from different Web sources, with the latter representing over 1 million items, with the addition of a popularity score which was calculated based on the usage of a place name in a geotagged dataset.
DBpedia Spotlight: a tool for automatically annotating mentions of DBpedia resources in text, providing a solution for linking unstructured information sources to the Linked Open Data cloud through DBpedia. DBpedia Spotlight performs named entity extraction, including entity detection and Name Resolution.
Google BigQuery Service: a SQL-like tool for analyzing massive datasets, as a web service that enables you to do interactive analysis of massively large datasets-up to billions of rows.
Common Crawl: a freely accessible index of 5 billion web pages, their page rank, their link graphs and other metadata, hosted on Amazon EC2, was announced today by the Common Crawl Foundation.

Seminario MAVIR: Búsqueda de personas en la Web

2011-11-21T09:02:00.000+01:00

TÍTULO: Búsqueda de personas en la Web
PONENTE: Julio Gonzalo (NLP&IR-UNED)
FECHA Y HORA: miércoles 23 de noviembre de 2011, a las 12h00

ABSTRACT

Buscar información sobre personas es una actividad frecuente en la Red, que va desde encontrar un número de teléfono hasta analizar la reputación online de una persona a partir de miles de fuentes. Pero utilizar un nombre de persona como consulta tiene un problema crucial: la ambigüedad. Los buscadores convencionales devuelven una lista de resultados en la que, muy a menudo, se mezcla información sobre muchas personas que se llaman igual. Un buscador ideal agruparía los resultados que se refieren a cada persona, y extraería dinámicamente un perfil de cada persona a partir del contenido de las páginas encontradas.

Web People Search es el término acuñado para este reto, y una parte sustancial de la investigación en el tema se ha vertebrado en torno a las campañas de evaluación competitiva WePS. En esta charla resumiremos los progresos alcanzados hasta ahora, y utilizaremos WePS como un ejemplo del uso de campañas de evaluación como motor de la investigación en Tecnologías de la Lengua. Por el camino, nuestras reflexiones ayudarán a explicar porqué los espías se niegan a usar la medida F de Van Rijsbergen, y qué podrían usar a cambio.

BIO

Julio Gonzalo es coordinador del grupo de investigación NLP&IR de la UNED. Sus intereses de investigación se sitúan en la intersección entre el Procesamiento del Lenguaje Natural y la Recuperación de
Información e incluyen, en particular, la búsqueda de información multilingüe e interactiva, la organización de resultados de búsqueda, la búsqueda semántica, y las métricas y metodologías de evaluación en
estas áreas. Ha sido recientemente general co-chair del CLEF 2011, area chair de EACL 2012 y EMNLP 2010, y co-organizador de las campañas de evaluación WePS (2007, 2009 y 2010).

LUGAR DE CELEBRACIÓN

Sala de Grados
Escuela Politécnica Superior, UAM
c/ Francisco Tomás y Valiente, 11
Campus de Cantoblanco
28049 Madrid

+ INFO: http://www.mavir.net/talks/100-jgonzalo-nov2011

CFP: WWW 2012, Internet Monetization and Incentives Track

2011-10-27T10:45:00.001+02:00

Call for Papers: WWW 2012, Internet Monetization and Incentives Track

The Web has become as a major economic phenomenon, acting both as a conduit for traditional endeavourstransactions such as business-to-business and business-to-consumer commerce, and as an arena for a specific variety of other economic activities such as Web advertising, digital payment systems, and bandwidths provisioning. The WWW track on Internet Monetization is a forum for theoretical and applied research related to web-specific economic activities.

The track will be interdisciplinary in nature. Relevant topics include (but are not limited to) :

Computational advertising: sponsored search, content match, graphical ads delivery, targeting
Machine learning and data mining applied to auction theory and user modeling in the context of Internet monetization
Internet auctions, markets, and exchanges
Economics aspects of online reviews, reputations, and ratings
Monetizing digital media, user generated content, and the social web
User-experience design aspects of Web monetization mechanisms
Web analytics for e-commerce
Economics of information/digital goods
Advertising infrastructure: tools, platforms, networks, exchanges, automation, audience intelligence
Economic approaches to spam/fraud control
Social and crowdsourcing commerce
E-commerce issues in cloud computing and and Web apps
Mobile web advertising and locating-based e-commerce

Important dates

All submission deadlines are at 9:00pm PST.

November 1st, 2011 Abstracts for papers due
November 7th, 2011 Papers due
January 30th, 2012 Paper notifications out
February 28th, 2012 Camera ready papers due
April 16th, 2012 Conference begins

All submissions must be formatted according to the ACM SIG Proceedings Template.

Submission can be made at: https://www.easychair.org/account/signin.cgi?conf=www2012

Via SIGIRList.

ACM Author-Izer: it is for you, it is for the ACM

2011-10-19T22:44:00.001+02:00

A win-win, absoultely. The ACM has developed a new service, now live, named "Author-Izer". A relatively long explanation of the service is there, but I strongly recommend to take a look at the presentation; it will give you an idea of what you get, and how to get it. However, and in few words, you make the final version of your papers at ACM publications available for free to your readers, and in turn, you allow the ACM to get a more precise account of cites and downloads. A win-win, because you benefit from knowing (and posting) your (registered) cites and downloads, as well.

It would be redundant to explain the process here, but although it seems easy, it takes a while. And that is important, because you may want to get your papers made public for free instantly. But well, it does not work so quickly. Some hints of the process:

All right, you are told to create an ACM Digital Library Web user account. That is easy, just sign up. But the user name is automatically generated, so do not forget it or you will have to answer your secret question as you filled in the registration and read your email (delay!), or to re-create the account.
Then you are requested to make at least a change to your "author profile". But where is it? You can not find it in the ACM DL page, nor even being logged. That is because there is no link between you as a Web user and you as an author. So the quickest way to find the profile is to search for your name in the DL, and click on your author name at one of your papers. Then you edit it (suggestion, fill the form completely), and your changes stay pending until somebody at the DL authorizes them. Wait. It took a day on my case, but it can be hours if you ar in the same time frame as the ACM - it means, the US.
Once your changes are admitted, you can access your author profile page. This should be mine: ACM DL author profile for Jose Maria Gomez Hidalgo. If you are logged as a user, you will see a new export link at your pubs in the ACM journals/conferences: "ACM Author-Izer Service". You can export all of them with the same link at the begining of the page, but unless you have dozens and dozens, I do not recommend it. It is more easy going one by one.
When you click one of the Author-Izer links, you get a popup for filling some details, and you get the code to insert in your papers page. Beware, you cave to write the URL of the page that will be hosting your paper page, or it will not be working. In my case, I tried several times until I got it: http://www.esp.uem.es/jmgomez/papers/. Copy the code in your page, and that is it. It is done instantly.

So that is all. Now you can have a link to your camera-ready version, and the citation stats, in your page. Simple but with some delays. As a note, every time you make a change at your author profile, it is manually reviewed, so it may take time to get it live.

JRC-Names - A freely available, highly multilingual named entity resource

2011-10-13T10:24:00.001+02:00

JRC-Names is a highly multilingual named entity resource for person and organisation names ('entities'). It consists of large lists of names and their many spelling variants (up to hundreds for a single person), including across scripts (Latin, Greek, Arabic, Cyrillic, Japanese, Chinese, etc.). The named entity resource file with the list of spelling variants is accompanied by Java-implemented demonstrator software that (a) allows to produce - for any input name - a list of known spelling variants, and that (b) analyses UTF8-encoded text files to find known entity mentions, returning the name variant found, the preferred display name for that entity, the unique name identifier for that name, the position of the entity name in the text, and its length in characters.

To see examples, go to any of the over one million entity pages on EMM-NewsExplorer (e.g. that for Muammar Gaddafi at http://emm.newsexplorer.eu/NewsExplorer/entities/en/262.html) to see the list of spelling variants automatically collected for that entity.

JRC-Names is a /technical/ resource that can be used to find names even if they are spelled differently and to normalise name spellings in databases or other repositories. It is also a useful ingredient for IT systems that process text, e.g. for text mining, machine translation, social network generation, and other text mining applications involving named entities.

JRC-Names is a by-product of the analysis of about 100,000 news reports per day by the *Europe Media Monitor* (EMM) family of applications (freely accessible at http://emm.newsbrief.eu/overview.html). It was mostly compiled automatically, by analysing hundreds of millions of news articles since the year 2004 in up to twenty languages, identifying names of entities (mostly persons, but also organisations, event names, and more), and detecting which of these newly found names are variant spellings of each other. Most name variants in JRC-Names are thus spellings that were found in real-life text (including frequent spelling mistakes). Additionally, for a subset of the collection of entities, software automatically extracted spelling variants in many further languages (e.g. Chinese, Thai, Japanese, ...) from the cross-lingual links in Wikipedia. For highly frequent or otherwise important names, the named entity resource was additionally manually verified. As JRC-Names was mostly produced automatically, it will contain some errors.

At http://langtech.jrc.ec.europa.eu/, you find more information on the JRC's multilingual language technology activity, a download link for JRC-Names and a reference paper explaining the named entity resource, as well as a page pointing to other multilingual resources.

Via MAVIR and Elsnet lists.

VI Jornadas MAVIR: Tecnologías de Acceso a la Información: Estado actual y reto

2011-10-13T09:00:00.001+02:00

VI Jornadas MAVIR
Tecnologías de Acceso a la Información: Estado actual y retos
15 y 16 de noviembre de 2011
ETSI Informática, URJC

Registro gratuito: http://6jmavir.appspot.com
Información completa: http://www.mavir.net/events/96-jornadas-mavir-2011

PROGRAMA

martes 15/11/2011. Jornada Científica y Empresarial
Salón de Grados, Edificio Interdepartamental II, URJC

9h00: Recepción y entrega de documentación

9h30: Graph Distance Distribution for Social Network Mining
Paolo Boldi (Università degli Studi di Milano)

11h00: pausa café

11h30: Ceremonia de Apertura de las Jornadas y Entrega del Premio MAVIR
Raquel Martínez, Coordinadora Adjunta del Consorcio MAVIR
Abraham Duarte, Investigador Principal del grupo GAVAB-URJC

12h30: Exposición del Premio MAVIR 2011

13h00: pausa almuerzo

15h00: Understanding Text with Knowledge Bases and Random Walks
Eneko Agirre (Universidad del País Vasco/Euskal Herriko Unibertsitatea)

16h30: Mesa Redonda Empresas

17h30: fin del primer día

miércoles 15/11/2011. Jornada Académica
Salón de Grados, Edificio Interdepartamental II, URJC

9h30: Recepción y entrega de documentación

10h00: Presentación de las líneas de investigación actuales del Consorcio MAVIR
Ronda de presentaciones a cargo de investigadores de los grupos
CybermetricsLab-CSIC, HTL&IR-UAM, LABDA-UC3M, GSI-UEM, NLP&IR-UNED,
THALES-UPM y GAVAB-URJC.

13h30: clausura de las jornadas

PRESENTACIÓN

La Universidad Rey Juan Carlos acoge los próximos 15 y 16 de noviembre de 2011 la sexta edición de las Jornadas MAVIR. Este año, bajo el título "Tecnologías de Acceso a la Información: Estado actual y retos", reunimos charlas científicas a cargo de ponentes de prestigio internacional y presentaciones de empresas de base tecnológica que trabajan en las líneas de investigación prioritarias del consorcio. Entre los temas que se tratarán destacan el análisis de grafos para el análisis de las redes sociales, las técnicas de semántica computacional aplicadas a la comprensión de información textual y el estado actual de las tecnologías de acceso inteligente a la información.

Como en años anteriores, aprovechamos la celebración de las jornadas para entregar la quinta edición del Premio MAVIR al mejor Trabajo de Fin de Carrera o Tesis de Máster en las áreas de investigación del consorcio. El premio está patrocinado por las empresas Bitext, Corex, Daedalus e iSOCO y cuenta con una dotación en metálico de 1.600 €.

El Consorcio MAVIR es una red de investigación co-financiada por la Comunidad de Madrid y el Fondo Social Europeo bajo los programas de I+D en TIC MA2VICMR (2010-2013) y MAVIR (2006-2009). El núcleo del consorcio está formado por un equipo multidisciplinar de más de 50 ingenieros, científicos, lingüistas y documentalistas provenientes de grupos consolidados, 15 PYMEs de base tecnológica y empresas integradoras. Las actividades de I+D del consorcio se centran en el campo de las tecnologías lingüísticas aplicadas a los sistemas inteligentes de acceso y tratamiento de la información multimedia y multilingüe.

DESTINATARIOS

Empresas de base tecnológica relacionadas con las Tecnologías del Lenguaje Humano, los Sistemas Inteligentes de Acceso a la Información, los sistemas de Reconocimiento Automático del Habla, los buscadores y la Web, especialmente aquellas con interés en el acceso y gestión de contenidos multimedia y multilingües.
Empresas integradoras con intereses en Sistemas Inteligentes de Acceso a la Información.
Grupos de investigación y spin-offs con intereses en Transferencia de Tecnología en TIC.
Organismos públicos y privados para los cuales la presencia en la Web es un factor estratégico.
Investigadores y estudiantes interesados en áreas como el acceso a la información multimedia y multilingüe, el procesamiento del lenguaje natural, la creación de recursos lingüísticos, la extracción de información, los sistemas de búsqueda de respuestas, el reconocimiento del habla y la Web semántica.

LUGAR DE CELEBRACIÓN

Salón de Grados, Edificio Interdepartamental II
ETSI Informática, Universidad Rey Juan Carlos
c/ Tulipán, s/n
28933 Móstoles, Madrid

REGISTRO

La asistencia es abierta y gratuita. Dado lo limitado del aforo, es necesario registrarse y reservar plaza en el formulario de registro: http://registro.mavir.net

Comment in New Scientist feature on Crowsourced SMS Spam filter

2011-06-17T09:29:00.001+02:00

Jakob Aron from New Scientist interviewed me some time a go regarding the following paper:

Kuldeep Yadav, Ponnurangam Kumaraguru, Atul Goyal, Ashish Gupta, Vinayak Naik. SMSAssassin: Crowdsourcing Driven Mobile-based System for SMS Spam Filtering.
12th Workshop on Mobile Computing Systems and Applications (HotMobile 2011).

You can find my opinion at the feature: Crowdsourced software could stop SMS spam.