2.1 Authorship attribution methods

Authorship attribution is the determination of authorship of a document where there are documents known to be authored by each candidate. This type of analysis can be performed as a classification task in machine learning in which features are derived from input documents and these features are used to determine the distance between the documents. How these features are determined separates much of the work in authorship attribution to date, although there is some crossover in approaches.

Much work in Authorship Analysis uses either statically chosen features or dynamically chosen features (Layton, Watters and Dazeley Reference Layton, Watters and Dazeley2011b). Static features are identified by the investigator, and may be refined using feature selection techniques. Examples include the mean sentence length and frequency of special characters in the text (Zheng et al. Reference Zheng, Li, Chen and Huang2005). Dynamic features are selected from the documents themselves according to a predefined model. Examples include the bag-of-words (BOW model and LNGs (Kešelj et al. Reference Kešelj, Peng, Cercone and Thomas2003). The focus of this research is on automatable methods, and for this reason dynamic features are preferred over static features.

Once features have been determined, a method for calculating distance is needed. In many cases this can be standard distance metrics such as the Euclidean distance, which is usable when the feature values are arranged as a vector. The distance between documents can be used as part of a classification algorithm (Mohtasseb and Ahmed Reference Mohtasseb and Ahmed2009), or using a simple ‘nearest author by distance’ method (Kešelj et al. Reference Kešelj, Peng, Cercone and Thomas2003). Another method for determining distance is a locally based method, where a profile is generated for each author. Those profiles are then used to calculate the distance between the given author and a document of unknown authorship. This type of profile is often performed using dynamically chosen n-gram-based models. These models have an advantage of being automated, with only two input parameters, the size of the n-gram and the number of n-grams to use. These methods are described in the next section.

2.2 Local n-gram methods

The study of character n-grams for Authorship Analysis has a long history (Cavnar Reference Cavnar1994), which has led to improved accuracy over other feature-based models (Kešelj et al. Reference Kešelj, Peng, Cercone and Thomas2003; Layton et al. Reference Layton, Watters and Dazeley2011b). For a sequence S containing tokens {s ₁, s ₂, . . . s _N}, an n-gram is a subsequence {s_i, s _i+1, . . . s _i+(n−1)} and usually n ≪ N. For character level n-grams, the sequence is the characters of a document, with an n-gram being a subsequence of characters. For the previous sentence, the five first occurring character n-grams, when n = 3, are [For], [or ], [r c], [ ch] and [cha]. In some studies, formatting characters are removed, while in others they remain. This preprocessing can lead to improvements in some writing tasks, but the structural hints can provide authorship clues of use in classification tasks (Urvoy et al. Reference Urvoy, Chauveau, Filoche and Lavergne2008). The use of n-grams to detect authorship has been successful in many studies.

The LNG methods are a family of n-gram-based methods in which each author is profiled using a specific set of L n-grams that are considered specific to that author. In the Common n-grams (CNG) method, the L, the most frequently occurring n-grams in that author's known writings are used in the profile (Kešelj et al. Reference Kešelj, Peng, Cercone and Thomas2003). The distance between two profiles is then calculated using (1).

(1)\begin{eqnarray} K = \displaystyle\sum_{x \in X_{P_1} \cup X_{P_2}} \Biggl(\frac{2\cdot(P_1(x) - P_2(x))}{P_1(x) + P_2(x)}\Biggr)^2 \label{eq_keselj} \end{eqnarray}

In the same way an author can be profiled using the above technique, and so can be a single document of unknown authorship. The distance between an author and a document pair is then calculated in the same way. CNG can therefore be used as a classification algorithm by first profiling each author using documents in the training set. Each document in the testing set is then assigned to the author profile with the smallest distance (Kešelj et al. Reference Kešelj, Peng, Cercone and Thomas2003).

The Source Code Author Profiling (SCAP) method is a simplification of the CNG algorithm shown to perform better than, or competitively with, CNG (Frantzeskou et al. Reference Frantzeskou, Stamatatos, Gritzalis and Chaski2007). A profile is generated in the same way as CNG, except that the frequencies of the n-grams are not needed. The similarity s(P ₁, P ₂) between profiles P ₁ and P ₂ is simply the percentage of n-grams occurring in P ₁ that also occur in P ₂. The distance between profiles is then simply 1 − s(P ₁, P ₂). Documents of unknown authorship are assigned to the nearest author profile as with the CNG method.

The Recentred Local Profiles (RLP) method is another variation on this theme; however, instead of the L most frequently occurring n-grams, the L most distinctive n-grams are used (Layton et al. Reference Layton, Watters and Dazeley2011b). To calculate distinctiveness, the mean frequency of each n-gram from the entire corpus is subtracted from the frequency for the n-gram in a particular author's writings. As an example, if the n-gram [th] appears with frequency 0.05 in the entire corpus and with frequency 0.04 in a particular author's writings, then the recentred value is −0.01. Different n-grams are then sorted using their absolute value, with the L n-grams with the highest absolute value used to profile an author (or document). The distance between n-grams is then calculated using (2):

(2)\begin{eqnarray} s(P_1, P_2) = \displaystyle\sum_{x \in X_{P_1} \cup X_{P_2}}\frac{(P_1(x) - E(x))\cdot (P_2(x) - E(x))}{\|P_1(x) - E(x)\|\cdot \|P_2(x) - E(x)\|} \label{eq_rlp} \end{eqnarray}

Note that each of the above-mentioned methods is supervised when author profiles are used. Author profiles require at least some of the documents to have known authors, which are referred to as the training set. From this training set, author profiles can be created and then used to classify the documents of unknown authorship. Without known classes the methods can still be used to calculate the pairwise distance between documents, allowing their use in an unsupervised environment (Layton, Watters and Dazeley Reference Layton, Watters and Dazeley2011a).

2.3 Unsupervised authorship analysis

Unsupervised methods of clustering documents are not novel; however, methods in unsupervised Authorship Analysis are uncommon in the existing literature. The field of document clustering aims to cluster documents by finding topics inherent within the dataset (Steinbach, Karypis and Kumar Reference Steinbach, Karypis and Kumar2000). This is an unsupervised task which takes a word representation of the text, like the BOW model described earlier but with removed stop words and performed word stemming. It is also a form of exploratory analysis, where the topics are discovered through the analysis. UAA methods aim to produce clusters correlating to the authorship of the documents – not to discover but to model authorship. Methods for this are uncommon in the literature.

One existing method is Writeprints, a technique used for both classification and unsupervised visualisation (Li, Zheng and Chen Reference Li, Zheng and Chen2006). Writeprints uses the Karhunen–Loève (KL) transform from local profiles, related to the LNG methods described earlier. KL transforms are a supervised form of Principal Components Analysis (PCA), in which the vectors containing the most information about a dataset are extracted. This is useful for dimensionality reduction and allows the use of many features to create a Writeprint. Instead of n-gram models, a variety of features are used and the KL transform reduces this to two or three dimensions. This has proven useful for visualisation (Chen, Abbasi and Chen Reference Chen, Abbasi and Chen2010) and manual analysis of a set of documents (Abbasi and Chen Reference Abbasi and Chen2008). Writeprints have been shown to have high accuracy in many classification tasks; however, unsupervised applications to date have remained as a visualisation tool for manual analysis of a corpora.

Another related technique is that of anti-aliasing authors of posts on the web when the same person has posted online under two aliases. The method employed in this area uses the tf-idf algorithm on a model, and the Kullback–Leibler divergence as well as other features determine the similarity of two aliased documents (Novak, Raghavan and Tomkins Reference Novak, Raghavan and Tomkins2004). This method proved to be highly accurate in finding the expected match, when each of 100 authors' works from a single topic message board were split into two aliases. The technique even suggested actual aliases within the dataset which were previously unknown. These suggestions were investigated and evidence strongly indicates that the aliases are from the single author. This method of testing has some limitations: Clusters sizes are known and expected, allowing an algorithm to take the ‘best matching alias’, rather than trying to cluster documents into clusters of an unknown size. The technique was generalised to the clustering problem; however, the stopping criteria is still needed to be defined in order to obtain results, limiting its use in an automated system.

The research most similar to this is the work by Iqbal et al. (Reference Iqbal, Binsalleeh, Fung and Debbabi2010), who used cluster analysis in a corpus of unlabelled emails to guess authorship. This method used character, word, syntactic, structural and domain-specific features. A dataset was created from the values of each feature for each document and that dataset was used as input into any of the k-means algorithm, EM algorithm or bisecting k-means algorithm. Once this clustering was performed, the resulting clusters were then analysed using the Writeprints (Abbasi and Chen Reference Abbasi and Chen2008) technique, used earlier to discover patterns that lead to the creation of the cluster. The clustering algorithms chosen required an estimate of the number of clusters, which were chosen in these experiments as the number of authors in the dataset – the ‘correct’ value of k. This is not practical for a real world application, where the correct value is not (or cannot) be known a priori. The choice of a clustering algorithm that can be automated is an important one in this type of research as – without automation – insight into authorship cannot be inferred if the algorithm is heavily reliant on a known parametrisation. The next section investigates using clustering ensembles to eliminate parameters and allowing automation of the process.

2.4 Clustering ensembles

There exists a large number of clustering algorithms in the literature with various optimisations, generalisations and specialisations. Further to the number of clustering algorithms, there are also a large range of cluster ensembles that can be used to take the results of different clusterings and combine them to use the strengths of each algorithm. A full literature review of these algorithms is outside the scope of this research; readers are referred to Ghaemi et al. (Reference Ghaemi, Sulaiman, Ibrahim and Mustapha2009) and Xu and Wunsch II (Reference Xu and Wunsch2005) for surveys of this field. In order to be used in an automated methodology, a clustering algorithm must not need parameters to function. Further, as there are some parameters for any Authorship Analysis method, an ensemble methodology is needed to enable the ensembling of a wide variety of parameters. One methodology that has both of these attributes is called EAC.

Evidence Accumulation Clustering is a cluster ensembling algorithm which begins by using the k-means algorithm a large number of times on a dataset with a varying number of value for k (Fred and Jain Reference Fred and Jain2002). The resulting clusters are then used to form a co-association matrix C such that C_{i, j} is the percentage of iterations of the k-means algorithm which clustered instances i and j together. This is the ‘evidence accumulation’ of the algorithm; when items are clustered together more frequently, there is increased evidence that the items should be ultimately grouped together. This co-association matrix is then clustered using a hierarchical clustering algorithm to form a dendrogram Z that can then be ‘cut’ at a specific height to form the final labels. It has been shown that the cluster quality resulting from this method is significantly high (Duarte et al. Reference Duarte, Fred, Lourenço and Duarte2010).

The important factor in EAC is the remapping from the original distance space to a ‘co-association’ space. This technique has also been used in other ensembling methods with success (Parag and Elgammal Reference Parag and Elgammal2009). With the co-association matrix created, the standard EAC algorithm creates a dendrogram, which is then cut using the ‘cluster lifetime’ procedure to form a final flat clustering (Fred and Jain Reference Fred and Jain2002). This step can be replaced with any other clustering method. As an example, other research used a threshold cut-off to determine the final clusters after calculating the co-association matrix in the normal method (Gao, Zhu and Wang Reference Gao, Zhu and Wang2010). The choice of dendrogram cutting method is equivalent to the problem of choosing a method that determines flat clusters where the number of clusters is unknown. This is an unsolved problem in cluster analysis and therefore the choice of a dendrogram cutting method is possibly application-specific.

3.1 Initial clustering

In Step 1 of the algorithm, a set of documents of unknown authorship is clustered using the k-means method with the procedure outlined by Fred and Jain (Reference Fred and Jain2002). The list of each of the labels from each run of the k-means algorithm forms the output of this step.

Clustering is achieved by calculating the distance between the document profiles created from each document by using the Authorship Analysis distance method. To use each of the three LNG techniques (RLP, SCAP and CNG) in an unsupervised setting, document profiles are created for each document and compared as document profiles (Layton et al. Reference Layton, Watters and Dazeley2011a). These methods are chosen because LNG techniques have been shown to produce high quality results in authorship attribution studies.

In the original EAC work, 150 runs of the k-means algorithm with k values randomly chosen from 10 to 30 inclusive were used (Fred and Jain Reference Fred and Jain2002). Our methodology uses the same value for the number of runs. For the value of k, some of the problems have less than ten (and more have less than thirty). With these bounds, documents will not be properly clustered and would leave each document to its own cluster in every run of k-means. The original work does not propose a solution to this problem and instead we suggest to proportionally separate the dataset into smaller datasets. The minimum possible number of clusters to be used in such an instance would be two, with the upper bound required to be at least one higher than this. This provides the lower bound for the range: [2, 3]. Further to this, a cluster should generally have more than one instance. For this reason, |D|/2 should be an upper limit to the number of clusters when the size of the corpus is low, where |D| is the number of documents. The lower bound needs to be less than this and we propose clusters with approximately double the number of instances per cluster (|D|/4). These subjective decisions led to the adjusted bounds [lower, upper] created by using (3) and (4),

(3)\begin{eqnarray} \textit{lower} = maximum [minimum(|D|/4, 10), 2] \label{eq_lower} \end{eqnarray}

(4)\begin{eqnarray} \textit{upper} = maximum [minimum(|D|/2, 30), \textit{lower} + 1] \label{eq_upper} \end{eqnarray}

The labels from each run of the k-means algorithm are used as the input into the next step, creating the co-association matrix C.

3.2 Dendrogram creation

In Step 2 of the proposed methodology, the results from the k-means runs are used to form a co-association matrix C, which is then used to create a dendrogram Z using agglomerative average linkage. The co-association matrix C is formed in the same way as in the previous EAC literature (Fred and Jain Reference Fred and Jain2002). The value of C_{i, j} is the normalised frequency of the number of times documents i and j were clustered together in all k-means runs. This value is higher if the documents are often clustered together and lower if they are rarely clustered together.

The resulting co-association matrix C is then used to create a dendrogram Z, using agglomerative average linkage. To create this dendrogram, each document is first put into its own cluster. The two nearest clusters are then combined recursively, creating a dendrogram. The distance between two clusters is given as the mean distance between all pairs of documents, with one document from each of the clusters. The choice of average linkage over the single linkage used in the previous work was based on using the cophenetic correlation, which measures the correlation between a distance matrix and the distance within the resulting dendrogram (Sokal and Rohlf Reference Sokal and Rohlf1962). The tested linkage methods were average, complete and weighted. The cophenetic distance was the highest for the average linkage in every single experiment included in this research and was therefore used in this research.

3.3 Dendrogram cutting using IPS

With the dendrogram Z created in Step 2, the dendrogram is cut according to the IPS method described in algorithm 1 to form a definitive flat clustering of documents. The IPS method works by iteratively creating more clusters until the median silhouette coefficient is below zero, indicating overlap in the clusters. Overlap in clusters is a sign of having too many clusters for a dataset. When the silhouette coefficient is found to be less than zero, the labels corresponding to k−1 clusters (the clusters from the previous iteration) are given as the final clusters.

The silhouette coefficient is an unsupervised evaluation metric that measures the extent to which clusters are well-formed and well-separated (Rousseeuw Reference Rousseeuw1987). The silhouette coefficient for an instance p is calculated using the mean intra-cluster distance a_p and the mean inter-cluster distance b_p using (5):

(5)\begin{eqnarray} s_p = \frac{b_p - a_p}{{\max}(a_p, b_p)} \label{eq_sil} \end{eqnarray}

The silhouette coefficient ranges between −1, which indicates incorrect clustering, and 1, which indicate well-formed and well-separated clusters (Rousseeuw Reference Rousseeuw1987). Values above zero indicate that clusters are non-overlapping, while values below zero indicate overlapping clusters. The silhouette coefficient has the key benefit of scoring lower for solutions with too many or too few clusters when compared with the ‘natural’ number of clusters. For a set of points, the silhouette coefficient is defined as the mean value of silhouette coefficients of each point in the set. As with any application of the mean as an average (Huber and Ronchetti Reference Huber and Ronchetti1981), outliers can cause problems using the mean silhouette coefficient. To address this issue, the median of the silhouette coefficients of each point is used to calculate the silhouette coefficient of a set of points.

The silhouette coefficient can be arbitrarily maximised when each instance is within its own clusters. However, when increasing the number of clusters by splitting clusters, as the above procedure does, the silhouette tends to start with a high value before decreasing as the number of clusters increases. This occurs because the separation of clusters is less justified as more clusters are increased (if it were more justified then that particular separation would occur earlier). Often, this decrease will see the silhouette coefficient drop below zero, as cluster separations become almost arbitrary and overlapping clusters become prevalent. After a sufficiently high number of clusters are used, the value increases to its maximum value. When the IPS algorithm terminates, clustering of documents returns. These clusters form the output of the proposed methodology with the aim of having the outputted clusters correlate strongly to the true authorship of the documents given as input in Step 1.

3.4 Parameter selection and ensembling

The proposed methodology determines the individual parameter sets that perform better for the testing corpora. However, this may not correlate to a truly automated and unsupervised environment, where V-measure results are unable to be calculated to select parameters. To overcome this, a method that uses related corpora to choose parameters was proposed and tested using the given corpora. The leave-one-out approach was used, where for each authorship problem the best performing parameters (decided by calculating the V-measure, Section 4.2) for the corpora excluding the given problem were calculated. These parameters were then chosen to be ensembled and evaluated on the excluded problem.

The ensembling procedure used the EAC algorithm as given in the previous section; however, each parameter set was clustered using k-means clustering 150 times and then each of these clusters are combined to create a single co-association matrix C. This co-association matrix was then used to create a dendrogram, using the procedure described in Section 2.4. The final dendrogram was then used to form a final clustering using the IPS method described in Algorithm 1.

Algorithm 1

Iterating Positive Silhouette (IPS) method for cutting a dendrogram

4.1 Corpora

The corpora used for this research was derived from the AAAC corpus (Juola Reference Juola2004). The AAAC corpus is a corpora of documents taken from a variety of languages and contexts to provide a difficult set of problems for authorship studies. The problems used in this research were the problems in English only (problems A to H). These authorship problems are difficult, particularly problems A and F, which were considered difficult even by the creator of the data set (Juola Reference Juola2008). This suggests that finding authorship patterns in this corpus is unlikely to be due to chance.

Further to the English problems from the AAAC, an additional problem consisting of a collection of books from the website of Project Gutenberg (Project Gutenberg Organisation 2011) was added to the corpus and is described in Table 1. The books were cleaned to remove Project Gutenberg's header and footer on each of the text versions of each of these books, but were otherwise left untouched. An overview of the corpus is given in Table 2, which shows the variety of the corpora not only in the mean length of the documents but also the size of each corpus ranging from six to 178 documents.

Table 1.

Overview of the books corpus

Table 2.

Description of each problem in the testing corpus. Final column is the mean number of characters per document in the corpus

4.2 Evaluation metric

The V-measure score was used to evaluate the results of the experiments in this research. The V-measure is a supervised evaluation metric that evaluates how close a clustering solution is to the actual class values (Rosenberg and Hirschberg Reference Rosenberg and Hirschberg2007), and is related to the F-measure (Rijsbergen Reference Rijsbergen1979). The V-measure's main strength is that it allows for comparisons of scores when the number of clusters may vary (Rosenberg and Hirschberg Reference Rosenberg and Hirschberg2007). For class labels O and cluster labels K, the V-measure score is calculated using the homogeneity (h) and completeness (c) by (6) and (7), respectively. The homogeneity measures the extent to which clusters contain only instances from a single class, while the completeness measures the extent to which all instances of a single class are within a single cluster. Higher V-measure scores indicate a better correlation between the clustering solution and the actual class values. The score ranges from zero, indicating no correlation, to one, indicating an exact match. The V-measure for a given β value is then calculated using (8), where H is the entropy function,

(6)\begin{eqnarray} h = \begin{cases} 1 & \text{if} H(O, K) = 0 \\ 1 - \frac{H(C|K)}{H(O)} & \text{otherwise} \end{cases} \label{eq_homogeniety} \end{eqnarray}

(7)\begin{eqnarray} c = \begin{cases} 1 & \text{if} H(O, K) = 0 \\ 1 - \frac{H(K|O)}{H(K)} & \text{otherwise} \end{cases} \label{eq_completeness} \end{eqnarray}

(8)\begin{eqnarray} v = \frac{(1. + \beta)\cdot h \cdot c}{(\beta \cdot h) + c} \label{eq_vmeasure} \end{eqnarray}

$\frac{|K|}{|O|}$

4.3 Baseline authorship techniques

Baseline comparisons techniques were used to determine both upper and lower bounds for the results from the proposed methodology. The upper bound was calculated by taking class predictions from an effective classification algorithm. The lower bounds were calculated by using standard baseline techniques in the authorship attribution literature and using these to calculate the distance between documents. This distance is then used for clustering in the first step of the NUANCE methodology. The clusters resulting from creating the resulting dendrogram and using an optimal cutting algorithm are then evaluated as the baselines. Three methods for performing lower bound estimates were tested, using BOW, BOn and feature subset combinations.

The upper bound estimation was performed by taking class predictions by applying RLP (Layton et al. Reference Layton, Watters and Dazeley2011b) to the corpora. In this application, the RLP author profiles were trained on all training documents in each problem. For the books' problems, there were no predefined training documents, therefore the dataset was split randomly into 90% training and 10% testing. The author profiles were then used to predict the class value of all documents by determining the ‘nearest author’. These predicted class values were then used as pseudo-clusterings and evaluated using the V-measure score. In this baseline, the RLP method was trained using the actual class values, and then used to predict the authorship of all training and testing documents. This over-fitting was expected to lead to much higher results than those obtained using an unsupervised method, and therefore formed the upper bound baseline.

For the lower bound baselines, three techniques used for comparison in the literature were used: BOW, BOn and the feature subsets from Zheng et al. (Reference Zheng, Li, Chen and Huang2005). The distance between documents was calculated by the first two steps of the proposed methodology applying each distance metric. The dendrogram resulting from the second step of the proposed method was then split using a supervised procedure to simulate an ‘optimal cut’. The resulting clusters were then evaluated using the V-measure to provide baseline scores. All three baselines have been shown to perform moderately well for authorship attribution in the previous literature. BOW and BOn are often used as benchmark scores (Raghavan, Kovashka and Mooney Reference Raghavan, Kovashka and Mooney2010). The feature subset scores perform well in classification methods and have been used extensively for authorship attribution (Abbasi and Chen Reference Abbasi and Chen2005; Zheng et al. Reference Zheng, Li, Chen and Huang2005; Iqbal et al. Reference Iqbal, Binsalleeh, Fung and Debbabi2010).

For the feature subsets, we use the first four subsets from Zheng et al. (Reference Zheng, Li, Chen and Huang2005): character, word, syntactic and structural features. Only incrementing subset combinations were used in Zheng et al. (Reference Zheng, Li, Chen and Huang2005)Footnote ³; however, all combinations of these subsets are used and reported. Syntactic and structural features have performed well in the past for classification on the AAAC corpus (Layton et al. Reference Layton, Watters and Dazeley2011b) and are expected to provide a reasonable baseline.

In each of the baselines, a vector is created for each document with values for each feature. For the BOW, the values are the normalised frequency of each word in the top L most frequent words in the dataset. For the BOn, the values are the normalised frequency of each n-gram in the top L most frequent words in the dataset. For the feature subsets, the values are the normalised valueFootnote ⁴ for each feature. Distance between documents in all baseline techniques was calculated using each of the Euclidean, cosine and correlation metrics. This distance metric was then used in the first step of the proposed method to calculate the distance between documents. After running the k-means algorithm and creating a co-association matrix C, a dendrogram was formed and cut to create clusterings.

One potential area for bias in these lower bound results was that any chosen dendrogram cutting method may not be optimal for that type of model and may not represent the accuracy of the model. For this reason, a near-optimal dendrogram cut was used instead of the proposed IPS cutting. This ensures that there is no bias in the results from the method of cutting the dendrogram. The resulting dendrogram for each metric was cut to create each possible number of clusters (from k = 2 to k = ||D||, the number of documents). The V-measures for all of these cuts were then calculated using the true authors and the highest scoring cut was chosen. This cutting method was supervised, removing the potential for bias in the chosen dendrogram cutting algorithm. Choosing the cut THAT maximises the V-measure also provided a higher baseline score for experiments.

4.4 Monte carlo distribution estimation

The baseline methods described in the previous section provided an expected upper and lower bounds for the resulting V-measure score. The score resulting from NUANCE was reasonably expected to be within those bounds. Despite this, a method for estimating the overall strength of a score within those bounds was needed. To estimate this strength, the Monte Carlo simulation on V-measure scores was performed to estimate the distribution of V-measure scores on the given corpora. That distribution was then used to provide estimated p-values for the results obtained using the proposed methodology.

The tests reported in this paper were evaluated using the V-measure score, which is the supervised metric evaluating the level of correlation between clusters and classes (Section 4.2). While the V-measure score has been reliably shown to be effective for comparing methods in domains, there is no clear way to transfer results from one domain to another. The theoretical limits of the V-measure are 0 to 1 inclusive; however, results such as these in practice are rarely seen. For this reason, the Monte Carlo simulation was used to estimate the distribution of V-measure scores.

To simulate the distribution, a large number of pseudo-clusters were generated and the resulting V-measure score was used to estimate the distribution of possible V-measure scores. The pseudo-clusters were created by first taking the actual classes from each authorship problem and iterating through each class value. For each class value, noise was added with a probability of 50%. If noise was added, the value was changed to a random value up to |O|, the number of classes. This created randomness in the resulting labels while maintaining a similar number of clusters to the actual classes. The V-measure score was then calculated for this iteration and the procedure was repeated 100,000 times. The distribution of V-measure scores over all iterations was used as the distribution estimation. From this distribution estimate, the expected value (mean) was calculated along with probability values for estimating the likelihood that random clustering is as good as a given result. These are given as p-values in the results, although it should be noted that these are estimated values and not actual p-values for the given tests.

4.5 Testing parameters

The proposed methodology was tested using the three LNG methods described in Section 2.2: CNG, SCAP and RLP. For each of these methods, there were two parameters n and L which take varying parameters. The first was n, the size of the n-grams to extract, and the second was L, the number of n-grams to use to profile a document or author. Values for n tested were 2 to 5 inclusive, while values for L were 50, 100, 500, 1,000, 2,000, 3,000, 5,000, 7,500 and 10,000. Each combination of n and L values was tested by itself in our experiments, giving thirty-six combinations for each of the three methods (RLP, CNG and SCAP). These values were chosen from the literature on each of the three algorithms to give a wide range of values.

Further to individual parameter sets, an ensemble was performed using all parameter sets. The parameter selection used was the leave-one-out ensemble (Section 3.4). In the leave-one-out method all but one authorship problem in the corpus was used to select the highest scoring parameter sets, using the V-measure to evaluate. The top five parameter sets were chosen from each of the 108 parameter sets as described above. Those parameter sets were then ensembled, combined together to form the co-association matrix C in the first step of the proposed methodology. This ensemble aimed to combine the results from each parameter set, overcoming noise that may occur through the use of just a single parameter set. It was expected that the ensemble would achieve higher results than any individual parameter set by itself. More importantly, this provides an automated method for choosing parameters without the known class values for a given authorship problem. Using other corpora to choose parameter sets for a new corpus provides a means for automatic and unsupervised clustering of documents by authorship.