2.1 Sexual predator identification at PAN 2012

PAN (Plagiarism Analysis, Authorship Identification, and Near-Duplicate Detection – http://pan.webis.de/) is a lab on uncovering plagiarism, authorship, and social software misuse, organized as part of CLEF (Conference and Labs of the Evaluation Forum – http://clef2012.clef-initiative.eu/). In 2012, PAN proposed a distinct subtask under the Author Identification topic, focused on Sexual Predator Identification in chat conversations (Inches and Crestani Reference Inches and Crestani2012).

For this task, the organizers collected and provided two collections of chats: one for training (which also contained the list of expected sexual predators) and another one used for evaluating the submitted solutions. The conversations dataset consists of an XML file with all the chat discussions, each one having a set of messages representing the utterances of the various participants to each chat. All messages contain the following information: the ID of the user, the timestamp, and the actual text.

In order to build the whole collection (both for training and evaluation), the organizers collated chats from different online sources:

• • Perverted Justice website Footnote ¹ where one can find conversations between convicted sexual predators and volunteers posing as underage teenagers;

• • Omegle repository Footnote ² which contains anonymous online conversation between consenting adults who use abusive language or even engage in cybersex;

• • IRC channels ^{Footnote 3,Footnote 4} which includes logs of IRC discussions on various topics.

The workshop organizers made available about thirty per cent of this collection as a training set, consisting of 66,927 conversations which contained over 90,000 unique users. They also provided the list of the 142 sexual predators which could be found within these conversations. The other seventy per cent of the corpus was used to assess the submitted solutions. For the test dataset, only the conversations were provided and each submitted solution provided a list of the sexual predators identified in these discussions.

In order to measure the performance of the submitted solutions, standard metrics for text classification (Manning et al. Reference Manning, Raghavan and Schütze2008) were used: precision (P), recall (R), and F-score. However, the F-score with precision and recall being equally weighted – called the F1 measure – is not always the best performance indicator. The same is true for sexual predator detection, as it is more important for the system to have a very high confidence that the identified participants really are sexual offenders than to aim to detect all the sexual predators. Therefore, for assessing the performance of the submitted solutions, the organizers proposed to favor precision over recall, thus using an F-score with the weight set to 0.5:

(1) $$\begin{equation} F=\frac{(\beta ^{2}+1)PR}{\beta ^{2}P+R} \ , \text{where} \ \beta =0.5 \end{equation}$$

Although it is important to retrieve as many suspects as possible (recall), the motivation behind the emphasis on precision is to optimize the time of the police officers who will receive the output of the program and will have to review the list of possible suspects.

Sixteen submissions were made within this competition at PAN 2012 and the best solution achieved a F _0.5-score of 0.9346, developed by Villatoro-Tello et al. (Reference Villatoro-Tello, Juá rez-Gonzá lez, Escalante, Montes-y Gómez and Pineda2012). Table 1 contains the results of the top ten solutions which were submitted for this competition.

Table 1.

Top ten results for the sexual predator competition at PAN 2012

We should take into consideration that the rather high scores obtained on the PAN sexual predator dataset might be explained by the fact that all predator conversations have been extracted from the same source, which contains the chat logs of predators which have been identified and prosecuted as sexual offenders. There might be other chat conversations between predators and their victims which are more complex or where the predator has a more complex behavior which have not been added to the Perverted Justice website, mainly because the offenders have not been convicted. As the work presented in this paper uses the PAN predator dataset, the same considerations apply to our results as well.

2.2 Previous results in sexual predators identification

The winning solution at PAN 2012 was developed by Villatoro-Tello et al. (Reference Villatoro-Tello, Juá rez-Gonzá lez, Escalante, Montes-y Gómez and Pineda2012), who proposed a two-step approach for identifying the sexual predators. Thus, they employed two different classifiers, one used to detect suspicious conversations (Suspicious Conversations Identification – SCI classification) and the second one for predator disclosure (Victim From Predator – VFP classification). Before training the classifiers, they filtered the chats by removing conversations with only one participant, conversations with less than six messages per user and conversations with long sequences of unrecognized characters. For representation, they used a BoW model to determine the features for both classifiers. The actual features were computed using term frequency-inverse document frequency weighting. For the first classifier, the feature vector represented all the text within a conversation, while for the second classifier it consisted of all the messages for each user. They used Multi-Layer Perceptrons with ten neurons on the hidden layer for both classifiers.

Later, the same authors proposed a different approach which makes use of a three-stage chain classifier (Escalante et al. Reference Escalante, Erro, Villesanor, Villatoro-Tello and Montes-y Gómez2013). Each model of this chain classifier is trained for a different stage related to how a sexual predator approaches the victim: gaining access, deceptive relationship, and sexual affair/proposal. Each stage was represented by an equally length fragment extracted from the conversation. However, this solution obtained a lower performance than the approach proposed during the competition.

Peersman et al. (Reference Peersman, Vaassen, Van Asch and Daelemans2012) used a similar approach with two classification models: one for separating posts by predators from posts by other participants, and another one for excluding the users without any suspicious behavior, both trained using Support Vector Machines (SVMs). They also incorporated a filtering module to increase the precision of the first classifier. They relied on the probability outputs of the SVM classifier and averaged the outputs of the ten most suspicious posts of each user in order to determine whether an user is suspicious or not. Then the outputs of both classifiers were combined using a linear combination.

Parapar et al. (Reference Parapar, Losada and Barreiro2012) developed a classifier that distinguishes predators from non-predators by concatenating all the messages that a specific person wrote in all conversations from the corpus, resulting in a document per user. They removed words with more than twenty characters and the ones that appear in less than ten documents. After that, the remaining words were weighted using a frequency-inverse document frequency scheme. They also considered word bigrams and trigrams during their experiments to find their role in the overall performance. Moreover, they incorporated Linguistic Inquiry and Word Count (Pennebaker et al. Reference Pennebaker, Francis and Booth2001) features that estimate the degree to which people use different categories of words, and also chat-based features (the number of subjects contacted by a given user, the percentage of conversations initiated by a given user, etc.). Then they trained a SVM classifier using all these features.

Morris and Hirst (Reference Morris and Hirst2012) used both lexical features and some BF in their solution. For lexical features, they computed a vector of messages for each user along with the response of the interlocutors concatenated by the special prefix/tag OTHER_. They also transformed some of the other lexical features into special tags such as SMILEY_, MALE_name, FEMALE_name, NUM for numbers, and PHONE_number for telephone numbers. They considered several BF metrics such as initiative of a user, attentiveness, and conversation dominance. Using these features, they trained a SVM classifier for this task. However, after that, they applied a filter consisting of another SVM with the task of distinguishing predators from victims.

Other approaches include the ones of Eriksson and Karlgren (Reference Eriksson and Karlgren2012) which have used a Maximum-Entropy classifier with the profile of each user and Popescu and Grozea (Reference Popescu and Grozea2012) who combined k-Nearest Neighbors and Random Forest based on string kernels with character 5-gram presence bits. Kontostathis et al. (Reference Kontostathis, Garron, Reynolds, West and Edwards2012) developed ChatCoder 2.0 which uses a document per user approach. They used features such as the number of pronouns in a line, number of personal nouns, number of relationship nouns, or number of communicative desensitization words (such as ‘kiss’, ‘bra’, ‘horny’, ‘sex’) to train a C4.5 decision tree classifier.

Besides the PAN 2012 sexual predator identification competition, there have also been several other approaches worth mentioning. Bogdanova et al. (Reference Bogdanova, Rosso and Solorio2012b) propose a classifier that uses features based primarily on sentiments, such as emotional markers (joy, sadness, anger, surprise, disgust, or fear words) and on the offender’s psychological profile. They observed that predators are not willing to step aside from the sex-related conversation, concluding that predators have a somehow fixated discourse or predominant topic. They suggest to use lexical chains in order to model and identify this feature in the conversations (Bogdanova et al. Reference Bogdanova, Rosso and Solorio2012a). Considering these features, they employed a Naive Bayes classifier trained on chat logs from the Perverted Justice site, cybsersex chat logs and the NPS chat corpus Footnote ⁵ and report an accuracy of ninety-four per cent for distinguishing Perverted Justice conversations from cybersex chat logs and ninety-two per cent in separating Perverted Justice from NPS chats.

Vartapetiance and Gillam (Reference Vartapetiance and Gillam2012) used an approach based on deception detection. They developed a set of features which best characterize the predators based on different cues/topics discovered by manually inspecting a part of the corpus: address (asking the children about the address of the house or of some place to meet), parents (asking the children about the presence or absence of their parents while chatting, making sure the chat logs will be later deleted, and the children will not discuss with their parents), age of the predator, and the intentions of the predator. Their main algorithm analyzes each chat and detects lexical patters for each of the aforementioned topics. In a subsequent research, the authors improved their categories by including a wider list of word patterns and by filtering conversations that were discussing computer topics (Vartapetiance and Gillam Reference Vartapetiance and Gillam2014). Moreover, they investigated the use of machine learning algorithms (decision trees, Naive Bayes, and SVM) for selecting the best attributes. The main conclusion is that SVMs proved the best solution for these features and the results obtained using a SVM would place them on the fourth place in the PAN competition.

Our solution has been inspired by the various approaches developed for sexual predator detection. Similar to Villatoro-Tello et al. (Reference Villatoro-Tello, Juá rez-Gonzá lez, Escalante, Montes-y Gómez and Pineda2012), we employ a two-stage classification strategy in order to solve the two main problems of detecting a sexual predator: identifying suspicious discussions and separating predator from victim in these conversations. However, we go beyond their solution by integrating behavioral features that prove very powerful in differentiating predators from victims, in a similar way to Vartapetiance and Gillam (Reference Vartapetiance and Gillam2012) or Morris and Hirst (Reference Morris and Hirst2012). Our BF aim to detect more complex issues about the phrase structure of predators (such as textual complexity differences) or about the intentional elements expressed in the dialogue (e.g. invitations, guiding the discussion, questions). Moreover, we have treated the problem of the imbalanced dataset more thorough than any previous work. All these improvements allowed us to obtain the best result known so far in online sexual predator identification.

2.3 Learning from imbalanced datasets

He and Garcia (Reference He and Garcia2009) present in a comprehensive study the state-of-the-art methods for dealing with imbalanced datasets for learning algorithms. They motivate their review by the increasing volume of datasets with under-represented classes, which prove to be a challenge for the existing methods used for supervised learning. The study provides three main methods to deal with imbalanced datasets:

• • Sampling Methods;

• • Cost-Sensitive Methods;

• • Kernel-Based Methods and Active Learning Methods.

According to He and Garcia (Reference He and Garcia2009), sampling methods for handling imbalanced datasets can be divided into several categories. In the proposed solution, a cost-sensitive solution has been employed to handle the imbalance in the sexual predator dataset. However, several sampling methods have also been tested, including random undersampling and oversampling, informed undersampling using BalanceCascade (Liu et al. Reference Liu, Wu and Zhou2009), and CBO – a clustering-based method using k-means (Jo and Japkowicz Reference Jo and Japkowicz2004).

Cost-sensitive methods are based on a cost matrix which defines the penalty of misclassifying an instance. The purpose of the cost matrix, C(i, j), is to help finding a hypothesis that minimizes the overall cost on the training data set (Bayes conditional risk):

(2) $$\begin{equation} R(i|x)={\scriptstyle {\textstyle \sum _{j}}}P(j|x)C(i,j) \end{equation}$$

P(j|x) is the probability of each class j for an instance x, while C(i, j) is the cost or penalty for predicting that an instance belongs to class i when it actually belongs to class j. Several specific cost-sensitive methods have been developed for the most important classifiers: for AdaBoost (Sun et al. Reference Sun, Kamel, Wong and Wang2007), for decision trees (Maloof Reference Maloof2003), for neural networks (Kukar et al. Reference Kukar and Kononenko1998), etc. Moreover, Domingos (1999) proposed MetaCost, a general method that allows any classifier to be cost-sensitive by wrapping a cost-minimizing procedure around the classifier.

2.4 Corpus description and brief analysis

As already mentioned in the general description of the PAN 2012 sexual predator identification competition, the training collection has approximately 67,000 chats with more than 90,000 users. Among these conversations, only around 2,000 have a sexual predator within the list of participants. Moreover, about sixty-eight per cent of the chats are between two users and the rest are multi-party discussions. After a brief analysis of the subset of the corpus containing only the chats between two users, an initial observation was that many conversations had very few lines as can be seen in Figure 1. These very brief conversations can mislead the training of the classifiers, since no meaningful information can be extracted from them even by employing manual human inspection. As a result of this preliminary investigation, we decided to use for training a subset of the corpus consisting of conversations with exactly two users and more than twenty messages.

Fig. 1.

Histogram for the number of messages in conversations between two users.

Table 2 contains additional details about the outcome of this filtering phase: The resulted corpus has a little over 8,000 conversations out of which about ten per cent of the chats contain a predator. We considered that this is a simple method for removing some of the outliers in the train dataset without losing useful information when training the classifiers. It is also important to notice that no sexual predator has been lost in this filtering phase as all predators have also been involved in at least one longer conversation that has not been removed. An interesting side-effect of this phase is that the filtered corpus is still imbalanced; however, the ratio of chats with predators versus chats without predatory content has increased several times.

Table 2.

Size of the corpus after filtering

Since the corpus was created by merging chats from different websites and IRC channels, the conversations cover a diversity of topics. For the interested reader, Appendix A contains selected representative logs for each of the four types of conversations present in the analyzed dataset: one chat from the Perverted Justice website, one from the Omeagle repository containing a cybersex sex between consenting adults, and two conversations from an IRC channel – one covering general topics and one on a more technical topic.

Two distinct representations of the analyzed corpus were used. The first representation helps to classify at the conversation level and is helpful for determining whether a conversation contains a potential predator. In this case, each feature vector represents an entire chat conversation. The second one, which is used to determine whether a user is a predator, classifies at the participant level and each feature vector represents an unique participant. The training corpus used for the conversation-level representation is the one containing only chats with only two users and more than twenty messages. However, the corpus used for participant-level representation contains, for each user, the list of all utterances that were authored by him in all conversations, regardless of the number of participants and messages. Table 3 presents the size of the training corpus and the distribution of the classes for each type of representation. From the data in this table, one can easily see that solving the problem of predator identification at the participant level is more difficult due to the highly imbalanced dataset. This is the main reason for employing a two-stage classification strategy.

Table 3.

Distribution of classes for each type of chat representation

3.2 Proposed solution

3.2.1 Features for sexual predator detection

Since we considered two distinct representations of the chats (conversation level and participant level), we developed a different set of features for each representation. The features used for both representations can be divided into two categories: ‘lexical’ features that are extracted from the raw text using the BoW model, and ‘behavioral’ features that are engineered to reflect how a user acts in the chat by taking into consideration the task at hand.

To build the set of lexical features, we first applied a pre-processing step for the whole corpus. This included tokenization, stop-words removal, and also discarding long words with over twenty letters. For the remaining words, a BoW model was built and, after preliminary experiments, we have opted for binary features instead of frequency-inverse document frequency. Then the most discriminative features were selected by employing MI feature selection. Table 4 shows the top fifteen most relevant lexical features for detecting sexual predators within the training corpus, ordered descending by MI score. Using this procedure, the vocabulary size has been reduced considerably both for the conversation-level representation and for the participant-level one, as can be seen in Table 5. The experiments for determining the optimum number of features selected using MI are described in the next section.

Table 4.

Top fifteen most relevant lexical features for detecting sexual predator ordered descending using MI

Table 5.

Vocabulary size before and after feature selection

As for the behavioral/interactional attributes, we started from the premise that there is a need for higher level linguistic features that are able to capture discourse, semantic, and pragmatic elements which can easily separate predatory discussions from non-predatory ones, as well as predators from victims. Part of the BF described next were introduced after manual inspection of the conversations, being also inspired from research in textual complexity and the analysis of chat logs in educational settings.

Although some of these features are empirical or defined according to the task at hand (e.g. underage or above age existence, usage of slang), many are in accordance with research in the behavior of online predators when attracting their victims using chat conversations (Malesky Reference Malesky2007; Whittle et al. Reference Whittle, Hamilton-Giachritsis, Beech and Collings2013) such as usage of sexual expressions, initiating conversations, trying to be a mentor which may manifest in linguistic differences which may be measured using a readability index or other textual complexity measures. Our choice of behavioral/interactional features is based on current research in the behavior of sexual predators in online conversations and from an empirical analysis of the PAN chat corpus. However, other interactional features might have been used such as dialog acts (Core and Allen Reference Core and Allen1997) detected in the chat utterances or even sequences of relevant dialog acts.

Next, we present the full list of behavior and interactional features used for both levels of representation.

• • Question ratio: Percentage of questions asked from the total number of messages. This number was computed heuristically by counting question marks, patters such as ‘is it’ where the verbs appear before nouns/pronouns, and lines containing one of the Five Ws and H followed by an auxiliary verb and the ‘you’ pronoun.

• • Underage expressions ratio: Percentage of expressions that may reflect that the user is underage from the total number of messages. We counted expressions such as ‘don’t know’, ‘didn’t do’, ‘never did’, etc.

• • Above age existence: Existence of a message containing the answer to an ASL Footnote ⁶ request and the answer should be a number above 18.

• • Underage existence: As above, but the age should be between 10 and 17.

• • WordNet Footnote ⁷ words ratio: Percentage of the words that are present in WordNet from the total number of words. In this case, WordNet is used as a dictionary to separate the formal vocabulary from slang and other informal vocabulary.

• • Slang words ratio: Percentage of slang words from the total number of words. For this, a list of the most common English slang words has been crawled from the Online Slang Dictionary Footnote ⁸ .

• • Sexual words ratio: Percentage of words with sexual connotation from the total number of words. The list of words with sexual connotation was also obtained from the Online Slang Dictionary.

• • Non-words ratio: Percentage of words that do not exist in either WordNet or the Online Slang Dictionary. The motivation behind this feature is to count the ratio of misspelled words.

• • Negations ratio: Percentage of messages that contain a negation from the total number of messages. This feature was added because, in many cases, the victim usually refuses the predator’s requests.

• • Flesch Reading Ease Score (FRES): Score computed by the formula for the FRES test used to assess the readability of a text (Flesch Reference Flesch1948):

  $FRES=206.835-1.015\left(\frac{total_{-}words}{total_{-}sentences}\right)-84.6\left(\frac{total{}_{-}syllables}{total_{-}words}\right)$

These BF can be used for both types of chat representations. However, for the participant-level representation, the features reflecting the existence of a message containing the age of the participant will be modified to consider all conversations in which an user takes part, so they will become the following:

• • Above age ratio: Percentage of conversations that contain the answer at an ASL request from the total number of conversations in which the user takes part. The age in this answer is a number above 18.

• • Underage ratio: As above, but the age is between 10 and 17.

Moreover, for the participant-level representation, two new features have been introduced that have no added value for the conversation-level representation:

• • Initiation ratio: Percentage of conversations that the user had initiated from the total number of conversations that he/she took part in.

• • Average response time: The average time that the user responds to the messages sent by the other participants.

This set of behavioral attributes is lacking features that could describe the actual interaction between that user and the other participants in the chat. To tackle this issue, for both representations, we enhanced the feature set by adding the following new features. For the conversation-level representation, we divided each conversation into two documents (since each conversation had only two users after the intial filtering of the corpus), each one containing the messages of a single user. For these two new documents, we computed the BF vector and the new features were calculated as the difference between the feature values of the user who initiated the conversation and the feature values of the other participant. This allowed us to capture information whether the initiator of the chat conversation had a different behavior within the discussion than his/her interlocutor.

For the participant-level representation, this mechanism needed to be slightly changed as each user might have participated in more than a single conversation. Thus, for each participant we extracted all partners that interacted with him/her in the entire corpus and we computed, for each BF, the average value of all his/her partners. These mean scores were the new features quantifying the difference in interaction between a user and all his/her interlocutors.

Table 6 shows the final feature vector size for each representation. We chose 1,000 lexical features for the conversation-level representation and fifty lexical features for the participant-level corpus. As described in the next section, these values were selected as they offered the best results after performing cross-validation on the training set. More details about the performed experiments, along with their results, are presented in the following section.

Table 6.

Final feature vector size

Table 7 shows the BF sorted by their relevance, whereas Table 8 presents the top fifteen most relevant features for detecting a sexual predator. As can be observed from these tables, for the conversation-level representation, the BF are not as powerful as the lexical ones, and the interaction behavioral features (IBF) are actually poor. However, for the participant-level representation, the situation is completely different: Among the most relevant attributes are the behavioral ones, especially the features which reflect the interaction between the user and his/her partners.

Table 7.

Behavioral features sorted by their relevance using MI. Features prefixed with DIF represent the difference between the feature values of the participants, while the ones starting with PRTN are computed for the chat interlocutor/partner

Table 8.

Top fifteen most relevant features for detecting a sexual predator using MI

A possible explanation for this result is that separating conversations that might be predatory, have some sexual content, or contain other messages that resemble predatory conversations is a simpler task than separating the actual predator users from other participants in chats between two consenting adults. Thus, lexical features are very discriminative for this task, while behavioral and interactional features are more relevant for separating predator users from suspicious conversations from non-predators.

3.2.2 Chained classification

For an improved detection of sexual predators, the problem was split into two different tasks and a chain of two classifiers was employed to solve them. The first task consisted of identifying suspicious conversations and for this task the classifier was trained on the conversation-level representation and corpus. As mentioned at the beginning of this section, in order to handle the imbalanced dataset, we used a MetaCost classifier with the cost matrix represented in Table 9. From this matrix, one can easily notice that we penalized false negatives seven times more than false positives. This way we are increasing the recall for this task at the cost of a slightly lower precision, thus ensuring that most of the suspicious conversations containing a predator are handled to the second classification step. As will be discussed in the next section, the classifier wrapped inside the MetaCost function is a SVM trained using SMO.

Table 9.

Cost matrix for the suspicious conversation classifier

In fact, the main role of the first classifier is to filter out as many non-predator users as possible by removing all conversations with non-predatory content. This filtering performed by the suspicious conversation identifier (SCI) is thus useful to reduce the data imbalance for the second classifier trained for predator detection. In Table 10 is highlighted the effect of this filtering stage on the dataset used for training the predator identification classifier. Without SCI, the participant-level corpus has over 90,000 users out of which only 142 are predators, while with SCI the dataset will contain only 381 users and a balanced distribution of the two classes. As a conclusion, the second classifier is trained on the participant-level corpus from which the users that did not participate in any suspicious conversations (as identified by the SCI) were removed, thus leading to a much smaller dataset.

Table 10.

Distribution of classes for the second classifier with/without SCI

The chain classifier acts on two different types of data. In the first stage, SCI works on conversations to filter out as many chats which are considered safe. These filtered out chats do not resemble discussions containing predators in the training set. The second stage acts on all the users from the chats which are considered suspicious to discriminate between actual predators and safe users. Although not tested in the current work, it is highly possible that the SCI phase actually acts as a filter for chats which contain a specific vocabulary, probably including sexual references and invitations to meetings. This is also demonstrated by the fact that lexical features work very well for this task as shown in this section and the subsequent one.

The best solution for the second classifier proved to be a Random Forest classifier wrapped again in a MetaCost procedure with the cost matrix from Table 11. The forest grows ten decision trees by selecting at each node the best values among seven randomly chosen attributes. More details are provided in the next section.

Table 11.

Cost matrix for the second classifier used for predator detection