Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Federal State Autonomous Educational Institution for Higher Education National Research University Higher School of Economics

Faculty of Computer Science Educational Program

Applied Mathematics and Information Science

Bachelor's Thesis

Bot detection in social media

SumekenovAkhmad

Moscow, 2020

Contents

• Introduction
• Literature review
• Dataset
• Methods
• Experiments
• Conclusion
• References
• Appendix


Аннотация

Цель работы - классификация и обнаружение ботов в социальной сети ВКонтакте. Проводится сравнение существующих методов. Реализованы и протестированы алгоритмы классификации, использующие, в том числе, комментарии. Реализованный метод обладает высокой точностью.

The purpose of this work is to classify and detect bots in the social network Vkontakte. The existing methods are compared in this work. Classification algorithms that use comments among other things are implemented and tested. The implemented method has high accuracy.

Introduction

Literature review

There is a lot of literature on detecting bots on social networking sites, especially Twitter and Facebook. Many articles describe how to identify fake accounts created to influence public opinion, thus influencing public and political life in their respective countries. For example, foreign interference in the U.S. elections in 2016 and 2018 has been widely investigated.

The sphere of machine learning has also been touched upon in these studies. For example, the U.S. media holding company NBC, together with the Committee to Investigate Foreign Interference of the U.S. Congress, released a dataset on the Kaggle, which is machine learning competition platform, containing "tweets" created by supposedly fake accounts sponsored by the foreign government.

NBCwebsitescreenshot

The first work I would like to consider is [1] the article about Twitter account classification. This work dealt with three issues:

1. Is it possible to create an algorithm that would recognize such "fake accounts" accurately enough?

2. Is it possible to accurately generate such "fake accounts" to increase the sample for training subsequent algorithms?

3. The latter goal is to implement the "synthetic minority oversampling" technique, which is essentially an over-sampling option where smaller class samples are synthesized rather than taken from an existing dataset.

The dataset on which the authors of the article conduct experiments was taken from the work [2] and consists of a combination of different datasets composed of tweets from fake accounts and tweets from real accounts (also called “genuine tweets”). In this paper, the authors used two "levels" of classification: account-basedandtweet-based. The same classification levels will be used in our work with some changes. For example, in this paper, the account-based approach means a classification based on data in the profile description on Twitter. In our task, this approach will be unsuccessful, because most of accounts in VKontakte are “closed” and so it is impossible to view user profile metadata. Our approach will use user activity in a specific set of Vkontakte groups and ID of user as features in the account-based classification.

The authors used many different classification algorithms for the account-based approach and LSTM model for the tweet-based approach. The best classification algorithms have reached 99.81% accuracy for the account-based approach and 96.43% accuracy for the tweet-based approach.

Another work [3] is centered around an enhanced deep model. The authors of the article consider the dataset of tweets not as a set of texts, but as a time series consisting of these texts. Thus, they use this time series as features and build various deep neural networks as models that will be based on these features. The dataset on which the experiments were made was taken from [4]. The authors of the article make a time series from the usual set of texts in the following way: two additional features are also added to the features of plain text: timestamp of tweet and posting type. Then these concatenated features are directed to deep neural models as input. The best result among all models was the F1-Score of 87.32%. The score of the best model in this work is lower than in the previous because datasets and the way they are created are fundamentally different. In the first work, dataset is consisted of samples with all labels being manually confirmed. In the second work, authors used dataset composed of Twitter accounts provided by Twitter ban history, which has a policy of “precision first” algorithms, thus there is a subset of accounts which are bots but are not labelled as such.

Dataset

Methods

In our work we used several algorithms for text-based classification. The first set of algorithms are classical SVM, LogisticRegression, XGBoost and RandomForestClassifier on top of TF-IDF text vectorization algorithm.

Bag of Words (BOW) algorithm is used to represent text as a numerical vector for consequent use in machine learning algorithms. The vector represents the number of times a word was used in the text.

An example of BOW representation

TF-IDFisanadvancedversionofBOWalgorithm.The method of TF-IDF considers the importance of individual words in this comment considering the frequency of occurrence of this word in all comments:

TF-IDF algorithm is one of mainstream algorithms to give a weighing factor to words depending on their relative frequency. ItisoftenusedinvariousNLPfields such as text mining, text classification and document analysis. There are multiple variations of TF-IDF in practice, but we will use the one provided by sklearn Python package.

Sklearn TF-IDF has multiple hyperparameters. Setting all the others to default values, we change lowercasing to False and consider only words which have overall occurrence number of more than 3.

After vectorizing the text, these vectors can be used for machine learning classification models. There are two important factors worth considering when using TF-IDF vectors as word embeddings. First, TF-IDF vectorizer should be fitted on training dataset and test dataset should be transformed using the same vectorizer. Secondly, the resulting dataset is a sparse matrix which is stored and manipulated in a specific way to avoid memory and computational overconsumption. Dataset has the size of , where Nis the number of samples and D is the size of vocabulary yielded from training dataset.

It should be noted that in our paper TF-IDF vectors are only used in non-neural network models, and neural network models use pre-trained embeddings of considerably smaller size. They are described in neural networks models section.

Support Vector Machine.

SVM is usually used as a non-probabilistic binary classifier or multiple labels classifier with one-vs-all or one-vs-one nature. SVMs take a set of points with labels in space and finds a hyperplane of dimension n-1 subject that minimizes certain loss. In separable case it tries to find hyperplane with maximum minimal distance from any point in space. In our case, the space of will be a space of commentaries after TF-IDF transformation. Advantages include simplicity of training and inference process and interpretability of results. As for disadvantages, the rise in dimension dramatically increases the time of training process. Secondly, because of the underlying nature of algorithm, it has a limited capacity out of linear domain. Mathematically, SVM classifier solves the following problem:

Where are weights, are features and are targets. C is a regularization parameter.

Example of dividing hyperplane on randomly created dataset

Logistic Regression.

Logistic regression is in its nature a probabilistic classifier which decides the class of a sample by taking a threshold over logistic function:

Logistic regression is by far one of the most popular machine learning algorithms for classification. Not only it can be constructed on top of the original features, it is often used as classification algorithm over features from more complex model such as neural networks and various boosting models (XGBoost, CatBoost). Logistic regression downsides are assumption of linearity between features and the target and also it can be overfitted in high-dimensional spaces.

Example of 3 class logistic regression on Iris data.

Random Forest Classifier.

Random Forest algorithm is an ensemble method based on decision forests. While decision trees lack the stability and tend to overfit aggressively random forests provide the way to tackle these problems. Random Forest algorithm consists of fitting multiple trees on random subsets of training data and then produce mean or otherwise weighted result. It is different from usual bagging technique because each tree is fitted on random subsets of features, what is sometimes called “feature bagging”. It is often used in scientific articles because of its relative simplicity and interpretability.

XGBoost Classifier. social network vkontakte bot

XGBoost Classifier is a parallel tree boosting algorithm which is optimized to run in distributed and efficient way. XGBoost Classifier is often used on tabular datasets but is also used as classification method on top of neural networks last layer features. Gradient boosting is a powerful algorithm, being used in a lot of top solutions on Kaggle competition platform. Simply put, it is an ensemble method, in which decision trees called weak learners are fitted on errors from ensemble of previous weak learners.On the other side, XGBoost Classifier needs tuning of many hyperparameters, which is a disadvantage compared to previous algorithms.

Text-level classification

After TF-IDF vectorizing, the proposed set of algorithms suggests the following actions:

· To balance the dataset, theunder sampling is performed: the size of the dataset is reduced to about 30.000.

· Then all 4 algorithms (SVM, LogisticRegression, RandomForestClassifier, XGBoost) are trained and tested with 5-fold cross-validation.

The second set of algorithms includes deep neural networks trained on pre-trained BERT-embeddings. These pre-trained Russian word embeddings were taken from DeepPavlov project.

· The first neural network includes a pre-trained embedding layer, several layers of LSTM (Long Short-Term Memory) and a fully connected layer at the end. With the help of the tool for working with graphs and their visualization it was possible to build a neural network visualization:

· The second neural network includes a pre-trained embedding layer, several convolution layers (Convolutional Layer) with MaxPool layer and a fully connected layer at the end.

Classification with user activity and metadata

It should be noted that the size of the dataset is significantly reduced when classified based on user activity, because there are much more unique comments than unique users. Moreover, due to under sampling, the size of our dataset is reduced to 1268. The vector of attributes in our models is the number of comments in each group of our set, i.e. the size of the vector is 43. The only metadata we have access to is user ID.We tried 4 algorithms - RandomForestClassifier, SVM, LogisticRegression and XGBoost.

Classification with combined features

After separate experiments we combine features in a sophisticated way to improve model quality with respect to both models based on user activity and metadata and models based on text features.

Experiments

Classificationwithtextfeatures. Non-neuralnetworkalgorithms

At first, we divided all comments into train and test datasets. We have trained the TF-IDF algorithm on a train dataset and conducted training with each classification algorithm with cross-validation on 5 folds.

As you can see, the two best algorithms for this task are LinearSVC and LogisticRegression. Their similar accuraciesare explained by the fundamentally linear nature of these classifiers.Having chosen the algorithm of logistic regression, we checked additional metrics on the test sample, such as precision, recall and F1-score:

As a result, we see that the model has not been overfitted, reaching 77% accuracy on the test sample.

Classification with text features. Neural Networks

For training neural network models, we took two simple architectures.

The first neural network consists of the following basic layers: Embedding layer, LSTM layer and full-connected layer at the end. The second neural network also consists of an embedding layer at the beginning and a full-connected layer at the end, but the "core" has been replaced from the LSTM layer to a series of convolutionalones which are followed by MaxPool layer.

To improve the quality of the classification, we took pre-trained embeddings from the open project DeepPavlov, namely Conversational RuBERT, because it is assumed that online comments are closer to the "free" style of the Russian language than to the official one, as on Russian Wikipedia. It should be noted that these embeddings were used in both architectures.

So, havingbeen trained on both architectures, we got the following results of modelperformances on the test sample:

As we can see, the recurrent model got the result higher than the convolutional and classical models. This can be explained by the fact that text is a sequence, and therefore the recurrent model is better suited for this type of problems.

Classification with user activity

We conducted experiments using 4 algorithms of classification on user activity features without any pre-processing. We trained these models with cross-validation on 5 folds. The results are shown below:

Note that the highest accuracy is yielded fromRandomForest model, which is explained by the nature of features: the trees analyze the number of comments and decide on the type of profile. AftertrainingRandomForest on a training dataset, let us look at the resulting metrics of this model on the test sample:

We see that the model based on the profile activity has the same accuracy as the neural networks model trained on text features.

Classification with user activity and their ID

Besides user activity, we can use metadata of user account. Unfortunately, in VK social network there is a considerable part of accounts which are closed from view (also called “private” accounts). These accounts metadata consist only of account ID. To our advantage, IDs have valuable latent information about accounts date of registration.It is known that in VK social network, ID of user is a strictly increasing variable with respect to the time. While we cannot get explicit date of registration, it gives us an information about whether one account is registered before or after another. Therefore, this meta-feature is supposed to be of huge value to bot detection algorithm.

We suppose the following method to use this feature:

1. Fit bucketizer on training data IDs, then transform both training and test data IDs.

2. Concatenate new features with account activity vectors.

3. Train 4 classification algorithms used previously on concatenated features using 5-fold cross-validation. Each time bucketizer is refitted on corresponding folds.

Results are given below:

As it is seen from table, accuracies are significantly higher than before. Training RandomForest classifier on the whole training dataset, we are getting the following metrics on test dataset:

Combining account-level features and text features

Next logical step is to combine account-level and text features to create a more accurate classifier for commentaries. A sample from dataset is now constructed by concatenating TF-IDF embedding of commentary text and account-level features of user who left the commentary. The peculiarity of situation is that account label (bot or real) automatically yields the commentary label (bot or real) and vice versa. Thus, if we split dataset randomly without any additional consideration, we may have the same account commentaries both in training and test datasets which contradicts the principle of train-test split. Because these commentaries have the same label a priori it is suggested to use a more complicated way of train-test split, which is presented below in the diagram.

The main idea is:

1. Split account IDs into training and test sets

2. Then train dataset consists of commentaries left by users with IDs from training set IDs and test dataset is constructed the same way.

The best model in this case, as in previous ones, is RandomForest classifier. Other metrics for this model are provided below:

Notably, model has high precision for class 1 and high recall for class 0. It means that samples which are labeled 1 by model (in other words, model decides that commentary is bot-originated) are almost certainly bot-originated but model does not discriminate other bot-originated commentaries.

As RandomForest classifier can yield probabilities, we are able to change decision threshold. By lowering decision threshold, we can make model to have a higher accuracy in the expense of precision for the class 1.First model has its advantage in the case when there is “precision-first” policy. As mentioned before, such policy is used in Twitter when banning suspicious accounts. The second model is more relevant when accuracy is the main metric. It has the following metrics:

Conclusion

In the course of the work, the task of classifying comments at the text and user levels was considered. Methods which were used in related researches were studied and applied in this work. Various methods of text vectorization were used. As a result of the work, several models of comment classification were obtained:

1. Text level classification model with TF-IDF embeddings and non-neural network models

2. Text level classification model with BERT embeddings and neural network architecture: RNN-based and CNN-based

3. Account level classification with non-neural network models. Features include activity of account and its ID

4. Model based on concatenated features. These features combine text-level and account-level features.

During this work, the dataset of VK commentaries was created from scratch and can be used for continued research on this topic.

As for future research, the next steps include treating commentaries of each user as time series and including timestamps and time differences between commentaries of the same user as new features. Also, in this work we have not included commentary attributes such as attached photos, attached links and whether commentary was original commentary or a reply to someone else. Another area of research is the “likes” attribute. “Likes” attribute provides an information about IDs of users who “liked” the commentary. There is a strong hypothesis that these attributes may significantly improve model performance.

References

Appendix

1. Part of code in github : https://github.com/ahmados/RussianBotDetection

2. External source with bot IDs:https://gosvon.ru/

Размещено на Allbest.ru