dataesr/scientific-paragraphs-categorization huggingface dataset:
However, this test cannot conclude that a dataset is representative of a population, only that it is not homogeneous. Besides, the χ 2 value has no intuitive meaning, and the p-value is notoriously prone to cause interpretation error while the maximal error δ is easier to interpret. For these reasons, we will use the δrepresentativity when debiasing datasets. We propose here two algorithms to limit the bias of an initial dataset B, while minimizing the number of modifications. Algorithm 1 constructs a dataset of the same size as B. This can lead to suboptimal solutions because the size of the optimal solution and B may differ. Algorithm 2 allows the size of the generated dataset to vary. Besides, we prove that this algorithm is optimal in the number of modifications to B. These two algorithms take as input an initial base dataset B, a target dataset T which we would like B to resemble, a source labeled dataset S from which we will draw applications, and a positive ratio of tolerated difference δ.
A. Constant-Size Debiasing Algorithm Algorithm 1 produces a dataset G whose size is the same as its input B. Intuitively, this algorithm consists in adding elements from the source S to the most underrepresented classes of B and to remove elements from B for the most overrepresented class. Each time an element is added, another element is removed in order to keep a constant size. With the constraint of constant size, the debiasing may be impossible for one of two reasons: either no element can be added to an underrepresented class (because the source does not contain elements of this class); or it is not possible to obtain for some class k a proportion that lies in [ p T,k -δ; p T,k + δ] because δ is too small.
Algorithm 1 Constant Size Debiasing Algorithm. Input: B, T, S, δ Output: 15 return G Algorithm 1 is optimal in terms of number of modifications. 6 If a class is underrepresented in B, we need to add elements to increase its proportion and make it correctly represented. If a k elements are added to this class while the size of D remains constant (i. e. |D| = |B|), the proportion of class k in D is p B,k + a k |B|. A class is not underrepresented if its proportion is greater than p T,k -δ, so we are looking for the smallest a k such that p B,k Generated dataset G 1 S ← S; G ← B 2 while max k∈K | p G,k -p T,k | > δ do 3 k h ← arg max k∈K ( p G,k -p T,k ) most overrepresented class 4 k l ← arg min k∈K ( p G,k -p T,k ) most underrepresented class 5 if |S'(k l )| = 0 then 6 K S = {k ∈ K | |S'(k)| > 0} 7 if p G,k l ≥ p T,k l -δ and K S = ∅ then 8 k l ← arg min k∈K S p G,k -p T,k + a k |B| ≥ p T,k -δ, hence a k ≥ |B|( p T,k -δ -p B,k ).
B. Optimal Debiasing Algorithm Algorithm 1 can lead to suboptimal solutions. Algorithm 2 produces a dataset G without size constraint which is representative of T, with minimal modifications to B. This algorithm calls Algorithm 1 multiple times with different dataset sizes and maintains two variables: G best is the best dataset found so far, i. e. , the one that minimizes the number of modifications to B; and d min is this distance between G best and B. The algorithm starts with G best = "I mpossible and d min = ∞ (line 1). First, it calls Algorithm 1 (line 2) with the initial dataset B. If this succeeds, d min is updated with the appropriate number of additions and deletions, and G best becomes the result of Algorithm 1. Then, in lines 6 to 11, it tries to remove applications from the most overrepresented classes from B.
Algorithm 2 Optimal debiasing Algorithm Input: B, T, S, δ Output: Generated dataset Its worst-case temporal complexity is O ( 1 δ + |B|) 2 |K|. While Algorithm 2 computes the closest dataset to the original one, it may happen that the solution found contains only a few applications from the original dataset. This is an indication that the original dataset was very biased. 1 d min ← ∞; G best ← "Impossible" 2 if Algo1(B, T, S, δ) = "Impossible" then 3 d min ← 2 max( k n + B (k), k n - B (k)) If B has been debiased towards a target dataset T randomly drawn from a population P, with a tolerated difference of δ debiasing , we can estimate its error with the population P by taking into account the error δ sampling and confidence interval C used to derive the size of T with Eq. (  2 ): with confidence level C, the error between the debiased dataset and P is less than δ sampling + δ debiasing.
VIII. EXPERIMENTS In this last section, we are interested in producing datasets for experiments concerning Android malware detection or classification. 7 As identified in Section II-B three types of experimental scenarios can occur. The first scenario (market profiling) requires only unlabeled representative data sets that can be drawn randomly without requiring debiasing (Section V). The two other cases, Algorithm evaluation and Machine learning, require labeled datasets with different proportions of malware/goodware samples. Therefore, we propose in Section VIII-A to debias datasets containing only malware or only goodware and mix them, in Section VIII-B, to obtain mixed datasets directly usable for machine learning algorithms.
A. Debiasing Datasets The following details the use of our algorithm to produce representative datasets and in particular the choice of the base, reference and source datasets. Through these objectives, we discuss three main questions: • Is it always possible to debias a strongly biased dataset such as Drebin or VirusShare? • How many modifications (del/add) are required? • Is a debiased malware dataset stable over time? 1) Debiasing 100% Goodware Datasets: We have randomly drawn a New AndrooZoo Extract (NAZE-18-G) and filtered it by relying on Virus Total to keep only goodware with a date no greater than 2018. This dataset should be close to a representative dataset of the Android app population in 2020. Indeed, by taking as reference dataset AZ20 30k and as source dataset AZ19 100k G, we successfully build a representative goodware dataset when δ reaches 0.
001, as shown in Table  II. Indeed, for δ = 0. 04 the dataset is already homogeneous: no addition/deletion is required, but the p-value is 0. Then, we decrease δ until the p-value becomes close to 1. For δ = 0. 001, 19. 53% of the resulting dataset are new applications and more than 50% of applications have been removed from the original one. Remark that these values of δ are far lower than the maximum δ observed in Table  I. 2) Debiasing 100% Malware Datasets: We were first interested in investigating whether it is possible to debias a small and old dataset (Drebin) on the one hand and a more recent and larger dataset on the other hand (malware from VirusShare between 2015 and 2018). We want the produced datasets to resemble the population of AndroZoo, extracted in 2020. The debiasing results show us that Drebin is strongly biased as we need to add from 1.
8% to 12. 7% of new samples, because a lot of classes of the population are underrepresented or missing in Drebin. Even with these modifications, the resulting dataset is not homogeneous to the population. On the contrary, VirusShare can be debiased with few additions (less than 2. 9%) but requires removing more than 90% of the dataset. In that case, the resulting dataset obtains a p-value of 1. We conclude that the VirusShare dataset already contains enough material to be representative of AndroZoo for certain classes but that a lot of these classes are overrepresented. 3) Discussion: As seen in the results, Algorithm 2 can generate a new dataset statistically indistinguishable from the target dataset with a margin of error δ. However, the algorithm may fail (cf. grey cells in Table  II ) when some classes are underrepresented in the source, as discussed in Section VII-A.
This limitation can be overcome by providing a large and diverse enough source dataset. On the other hand, when the algorithm succeeds, the generated datasets' size tends to be much smaller than the base dataset. This is due to a lot of overrepresented classes, from which the algorithm removes elements at line 9. This is especially the case for historical malware datasets. The number of classes to consider may also limit the debiasing: intuitively, more characteristics would help to resemble the target dataset better, but it spreads the elements into more classes and makes it more difficult to find elements for certain classes.
B. Building Mixed Datasets for Machine Learning We finally produced two mixed datasets (goodware/malware) usable for training and testing machine learning algorithms. These datasets are built on top of the debiased malware datasets previously discussed. The goodware are taken from NAZE Debiased 18-G dataset. These two datasets are: • DR-AG Deb (standing for Drebin+AndroZoo Goodware), that mixes the debiased version of Drebin with δ = 0. 01 and the goodware. • VS-AG Deb (standing for VirusShare+AndroZoo Goodware), that mixes the debiased version of VS Debiased 15-18 when δ = 0. 1 and the goodware. Because the goal is to use mixed datasets for machine learning algorithms, we have to follow additional recommendations from Pendlebury et al. [7]. We build our mixed sets by extracting random samples from goodware and malware and by following the recommendations C1 (APK of the training set should be older than the ones of the test set) and C3 (realistic malware-to-goodware ratio i.
e. 5% or 10%). In Table  III  we call "Pivot year" the year that delimitates the train and test sets. Note also that a consequence of C1 is that applications in the training and test sets are disjoint (which correspond to an added C4*: Train ∩ Test = ∅). For C2 (temporal window consistency) we do not enforce the constraint as we already balanced the classes on the year when performing the debiasing algorithms. Nevertheless, we can enforce them if needed, at the cost of reducing the output size of the training/tests sets. For example, the set VS-AG-C2 Deb has fewer samples than VS-AG Deb. In the rest of the paper we only use the set that does not enforce C2 to decrease the quantity of results to discuss. We recomputed the average δ of these mixed datasets: it is still quite low (worst case of 0.
0012 for VS-AG Deb ). The p-value falls to zero for some sets because applying the constraints of Pendlebury et al. drives the datasets away from the population. Nevertheless, we believe that respecting the time consistency for machine learning algorithms is of higher importance. Finally, for evaluating these datasets when used for machine learning purposes, Table III includes additional datasets: • ACT14 and ACT17: a mixed version of AndroCT  [46]  with pivot year 2014 and 2017 respectively. • AZL14 and AZL17: a mixed version of random samples extracted from AZ20 30k for which we took the goodware/malware label of AndroZoo as an oracle. All these datasets will be used to compare the efficiency of machine learning algorithms when using our debiased datasets. In particular, AZL14 and AZL17 are the biggest extract of the population.
C. Classifying With Machine Learning We evaluate the performance of various machine learning classifiers depending on their training datasets to assess the contribution of debiased datasets. The datasets used in this experiments are those computed in the previous section, cf. Table  III. The machine learning classifiers rely on a total of 262 characteristics. The first 12 characteristics are those used to debiased the datasets that are not related to security. Additionally, we included the characteristics related to security computed from two sources: • Droidlysis that computes 214 Booleans about the use of some APIs or behaviors (loading a DEX file, using cryptography, etc. ); • FalDroid  [47]  that computes 48 characteristics representing score values related to graph-based features (with parameters = 0.
8, θ = 0. 1  [47] ). As FalDroid is intended to classify families, we configured the software with only two families (goodware/malware) and we extracted features related to control flow graph that manipulates sensitive APIs. We base this evaluation on the area under the receiver operating characteristic curve (AUC), a classical metric in machine learning. This metric can be interpreted as the probability that a classifier considers a randomly chosen goodware to be more probably benign than a randomly chosen malware. A perfect classifier has an AUC of 1 (every goodware is ranked higher than all malware), meaning that there exists a threshold to separate exactly goodware and malware. A random classifier has an AUC of 0. 5. Besides, this metric does not depend on some threshold selection. We evaluate various machine learning techniques: k-nearest neighbors  [48]  (neighborhood-based technique), decision trees  [49] , random forest  [50]  (bagging ensemble technique with decision trees), Gaussian naive Bayes  [51]  (statistical model), and AdaBoost  [52]  (boosting ensemble models with decision trees).
We used the scikit-learn  [53]  implementation with default parameters. Since the decision trees, random forest and AdaBoost learning algorithms are stochastic, we took the average AUC over 25 seeds. Average and max AUC are presented in Tables IV (pivot year of 2017) and V (pivot year of 2014) where each line corresponds to a different training set and each column to a different test set. The mean AUC over the various classifiers helps to estimate the global quality of a training dataset for machine learning. The max AUC reflects what performances could be obtained with the best classifiers. The datasets go by pair: there is one training set and one test set (cf. Table  III ). In Table  IV , we can see that generally learning on one training set yields the best results on the associated test set (i.
e. , the diagonal is in bold). The unique exception is that learning on AZL17 yields better results than learning on ACT17 when testing with ACT17. In fact, we can see that the AZL17 training set allows learning the best classifiers on ACT17 (max AUC: 0. 77) and AZL17 (max AUC: 0. 84), probably because it is a real randomly sampled dataset, and therefore it is less prone to bias. However, this training set was built using VirusTotal as an oracle, so it is, in general, not available for training. Moreover, the most interesting results are the comparison of the performances of VS-AG and VS-AG Deb on ACT17 and AZL17 test sets. We see that the debiased dataset always performs better than the original one. Another important result is that it is notably better to train on the debiased dataset VS-AG Deb than on ACT17 (AndroCT  [46] ), which is the most recent dataset we have.
Finally, the debiased test dataset VS-AG Deb is more difficult to predict than the test set VS-AG. It is a sign that the bias in the test set of VS-AG makes it easier for a model to correctly classify it, probably because some difficult cases are absent. Finally, we can remark that the DR-AG training set yields poor results on all test sets, which is an expected result, as no applications in this dataset after 2015. We tried to confirm this result with an additional experiment with the pivot year of 2014, in Table  V. In this experiment, we evaluate if the debiased version of Drebin can obtain good results, even if it is old and quite small. The row in Table V concerning DR-AG Deb shows that this dataset is far from being effective compared to ACT14. This is due to its size and the failing of debiasing when δ reaches 0.
D. Discussion This section discusses the validity of the datasets through time. We also compare these results with related works  [32] ,  [54] ,  [55]  that have studied this question and the relation with Android history. First, Cai et al. [54]  focus on the evolution of usage of the system's API over time, using a dedicated analysis framework  [32]. They conclude three main points: the decrease of usage of callbacks for methods of the app activities' lifecycle, a stable and small usage of inter-component communication, and a stable distribution of source/sink categories of callbacks. Second, Cai et al. [55]  characterize this evolution for goodware and malware applications. Newer malware tend to access system APIs more often through third-party libraries than older malware. The use of activities and services has increased over time, while the use of ICC components has decreased.
The diversity of callback categories has also increased. Our experiments confirm this evolution at a higher level. We study the evolution of representativeness of our debiased dataset over the years. More precisely, we debiased several extracts of VirusShare 2015, 2016, 2017 and 2018, and checked whether these debiased datasets stay representative of an evolving population over time. The target datasets are extracts of applications from AndroZoo 2019 (AZ19 100k ) filtered on the corresponding period of time (T = AZ19 100k i , with i = 15,  16, 17, 18). The source datasets are known datasets of malware such as Drebin and AMD, available at date i. When the p-value confirms that the dataset is not statistically different, we tested the produced debiased version V S Debiased i with the next years' population, i.
IX. CONCLUSION In this article, we presented the different types of Android datasets used by researchers to evaluate their experiments. We argued that these datasets have problems with their construction depending on the type of experiment. For surveys on bigger datasets, we proposed the use of a margin of error to obtain a lower bound on the size of the sample to be drawn. We also proposed a methodology based on the χ 2 test to evaluate the homogeneity of a dataset with respect to a given population for a finite set of characteristics. When starting from a dataset that does not resemble the population, we introduced a debiasing algorithm to push this biased dataset towards the population's characteristics. The choice of characteristics for which the dataset is debiased is of high importance.
We propose here to debias datasets for a finite set of computable characteristics unrelated to the characteristic under study in order to keep only the relevant differences with the population. Finally, using this algorithm, we proposed directly usable datasets for the evaluation of machine learning algorithms. We evaluated these debiased datasets using machine learning algorithms and we show that they outperform biased ones and in particular one recent dataset of the literature. Additionally, our debiased dataset, VS-AG Deb , would be usable for further works as a difficult test set for classification experiments. Future works concern the study of the influence of the considered characteristics over the performances of detection algorithms. In particular, limiting the study to a small number of characteristics when debiasing, prevents combinations from exploding.
At each iteration of the algorithm, there is at least one class k such that | T p G,k | > δ that is modified in G: one element is added if k is underrepresented and one element is removed if k is overrepresented in G. So k | T p G,k | is reduced by at least 1 |B| in the updated value of G. With enough iterations, k | T p G,k | will so low that every class will be correctly represented. At that point, the algorithm halts. Besides, a representative dataset always exists. This is necessary to prove the termination and the complexity of Algorithm 2. Theorem 3: Let T be a dataset, δ > 0 and n > 0 such as n ≥ 1 δ. There exists a dataset D of size n such as D is δ-representative of T. Proof: To prove the existence of such dataset of size n, we construct it. More precisely, we associate to each class k a number of element b k such as this class is δ-representative Proof: Assume such dataset D exists.
Consider the case where S is empty and T p G,k l ≥ -δ. Once again, we will prove by contradiction that this case is impossible when D exists. The fact that T p G,k l ≥ -δ implies that T p G,k h ≥ δ, otherwise the "While" condition would not have been true. Denote m the number of completed iterations so far. We now prove that the "If" condition on line 13 cannot be true in Algorithm 1 when D exists. For algorithm 1 to return an error on line 14, the condition max k∈K | T p G,k | > δ must be true. Let us assume (without loss of generality) that there exists k such as T p G,k > δ (the case T p G,k < -δ is similar). Consider now the value of k h. Since k h ← arg max k∈K T p G,k , we can conclude that T p G,k h ≥ T p G,k > δ. Denote n = |B| and G the dataset obtained from G by removing one element from k h and adding one element to k l.
Therefore b 1 -b 2 + 1 ≤ b 3 -b 4 and T p G ,k l = p G,k l + 1 n -p D,k l ≤ δ. This proves that the "If" condition is never true if D exists. Finally, if D exists, then Algorithm 1 returns a dataset. This dataset is representative because the "While" condition is true for the last iteration. When the algorithm outputs a dataset, it is representative and its size is the same as B. If such dataset does not exist, the algorithm cannot output one. Since the algorithm always halts, it must return "Impossible. " We denote d.
C. Datasets Used in the Literature Table VI evaluates the dataset usages of 28 articles on Android malware detection using machine learning techniques. Column "Paper" gives the name of the tool or the authors' names. Next, column "Goodware source" contains the datasets used in the experiment. Sometimes, several sets are used in a paper: we note these subsets D i and we give their size in other columns accordingly. Next, columns "GS year" and "Nb Goodware" are the year range and number of goodware according to the article, if available. The next three colmuns give the same information for the used malware. Next, columns "Training set" and "Test set" correspond to the number of applications used in the respective sets. The notation "(M/G)" reports the Malware/Goodware for each experiment. The use of "k-fold cross validation" will be specified in these columns.
We denote m D,k (respectively m D r ,k ) the number of samples in D (respectively in D r ) of class k ∈ K and p P,k (respectively p D,k and p D r ,k ) the proportion of class k in P (respectively in D, in D r ). If the null hypothesis holds true, then the three proportions p P,k , p D,k and p D r ,k of class k ∈ K should be close. The proportion p P,k can thus be estimated by m Dr ,k +m D,k |D r |+|D| and the expected number of occurrences of class k in D can be estimated by E D,k,D r = |D| × m Dr ,k +m D,k |D r |+|D| and in D r by E D r ,k,D = |D r | × m Dr ,k +m D,k |D r |+|D|. The χ 2 value of two datasets D and D r is defined as:.
best ← Algo1(B, T, S, δ) h ← arg max k∈K ( p G,kp T,k ) ← | |B| -|G| | + 2 max( k n + G (k), k n - G (k))11 if d < d min and Algo1(G, T, S, δ) = "Impossible" then 12 d min ← d; G best ← Algo1(G, T, S, δ) 13 G ← B 14 for i from 1 to d min -1 do Search larger datasets 15k l ← arg min k∈K ( p G,kp B,k ) 16 if |S(k l )| = 0 S = {k ∈ K | |S(k)| > 0} 18 if p G,k l ≥ p T,k -δ and K S = ∅ then 19 k l ← arg min k∈K S p G,kp ← one element of S(k l ) chosen at random ← | |B| -|G| | + 2 max( k n + G (k), k n - G (k))24 if d < d min and Algo1(G, T, S, δ) = "Impossible" then 25 d min ← d; G best ← Algo1(G, T, S, δ) 26 return G best Theorem 1: Let B, S, T be three datasets and δ > 0. If there exists at least one δ-representative dataset of T that is composed of elements of B and S, then Algorithm 2 produces such a dataset G such that the number of additions and deletions from the initial dataset B is minimal.
k a k < n and k (a k + 1) ≥ n. So there exist b k such as for all class k either b k = a k or b k = a k + 1 and that verify k b k = n. Denote the dataset D such as p D,k = b k n. The size of D is k b k = n and D is δ-representative of T since b k n ∈ [p T,kδ; p T,k + δ] for every class k. It proves the existence of such a dataset. Theorem 4: If there exists a dataset D consisting of elements of B and S (i. e. , D ⊆ B ∪ S) such as D is representative of T and |D| = |B|, then Algorithm 1 returns a representative dataset. If no such dataset exists, the algorithm returns "Impossible. ".