This paper considers the task of accelerating the text clustering by the island clustering method. Based on the consideration of the basic implementation of this method, the step of calculating the term correlation matrix is highlighted for further acceleration. This step has quadratic complexity from the number of terms since it considers each combination of them in pairs. In the framework of this study, it is proposed to use parallel computing and memoization as methods to accelerate the calculation of the term correlation matrix. The experiment was carried out using a specially developed deterministic algorithm for generating test data, which is also described. Based on the results of the data obtained analysis, it is shown that the use of the proposed methods accelerates the calculation of the matrix by 8-10 times on a virtual machine with 4 physical cores and 8 logical ones.
The clustering of natural language textual data is widely used both as one of the
variants of automatic systematization and as a proper analysis tool [
Thus, due to the constant increase in the volume of text corpora and complication
of their structure, formulation of new and improvement of existing methods of
automatic (unsupervised) clustering of text documents becomes an urgent task [
One of the existing effective methods of text clustering, which provides clarity to
the process of obtaining clusters for humans, is the method of island clustering [
The basis of this method is the implementation of a two-step procedure: the first
stage provides the clustering of terms (hereinafter, “term” is used in general
information retrieval meaning – any word/expression) that documents consist of; the
second stage – construction of document clusters, based on the clusters of terms
received in the first stage. Below is a more detailed list of steps of this method [
Stage I. Clustering of terms: 1. pre-processing of texts from the input collection of documents: removal of stop words, lemmatization, etc.; 2. selection from the texts the set of terms which they consist of; 3. if necessary, filtering the resulting set of terms (for example, in situations where the initial centroids of the clusters are known or the resulting set is too large); 4. construction of a graph of terms correlation; 5. pre-processing of the graph and obtaining its approximation (optional); 6. clustering of the obtained approximation of the graph;
7. splitting documents into clusters based on received term clusters.
One of the biggest cost steps is to build a graph of terms correlation. This procedure lays in calculation of the graph distances matrix (for this method of clustering the measure of terms correlation serves as a distance, so the names «distance matrix» and «correlation matrix» are identical for this research), which requires a pairwise consideration of all terms and leads to the quadratic complexity of the calculation process. Theoretically, the original clustering procedure for the obtained approximation of the graph is also quadratic (since it considers all edges of the obtained graph), but when applying the effective procedures of this very approximation, the complexity of this step is almost linear in practice.
Regardless of the mentioned above, as will be shown in Section 2 of this paper, none of the papers dealing with the island clustering method considers the acceleration of the term correlation matrix calculation. From this, we can conclude that the development of methods to accelerate the calculation of the term correlation matrix is a pressing issue, the successful solution of which will increase the speed of implementation of island clustering of texts as a whole.
Thus, the main objective of the research is to accelerate the calculation of the term correlation matrix in the method of island clustering of texts. The object of the study is the process of automatic clustering of natural language text data. The subject of the study is the methods of calculation acceleration and applying them in the context of the island text clustering method. According to the stated objective, the following tasks were set and solved: 1. research of existing methods to accelerate the calculations; 2. reasonable choice of methods to accelerate the calculations for their use in the method of island clustering of texts when calculating the term correlation matrix; 3. software implementation of the calculation of the term correlation matrix using the selected methods of accelerating the calculations; 4. analysis of the efficiency of the proposed means by the criterion of the speed of calculation.
The island clustering method was first described in [
[
However, in practice, more important is the dependence of performance on the volume of the text corpus, which is more natural to consider as the number of terms. Described related papers did not describe any techniques for improving this calculation. 3
The term correlation matrix is a symmetric matrix containing, as elements, the
correlation value between the corresponding pairs of terms [
pairs of terms. The correlation value between the terms and is determined as
follows. Let be the total number of terms in all documents, – be the number of
terms in the documents that meet the term , – the total number of term
occurrences in all documents, and – the number of term occurrences in documents
containing the term . Then the probability that in documents containing term ,
is found or more of terms , can be used as a basis for calculating the measure of
the correlation of terms and . This probability can be calculated by the formula of
the binomial distribution (1) [
As a result, we can build matrix
based on the obtained values and this matrix will look like . Such a matrix can be effectively stored in memory in the form of a vector with length
Thus, the basic algorithm for calculating the term correlation matrix
the following steps [
to with step 1 perform pp.2-4; with step 1 perform pp.3-4; This algorithm is a test of the statistical hypothesis of pairwise independence of the presence of terms in documents. The consequence of this is the fact that for randomly generated texts this algorithm will not find any significant relationship between the terms, and therefore, no clusters will be received at the output.
In practice, matrix also can be additionally filtered to remove insignificant
relations between terms (e.g. it can be done by use absolute threshold for term correlation
[
In the algorithm of the term correlation matrix calculation, it is obvious that each of the iterations is independent of the others. Thus, instead of sequentially executing iterations of cycles, their parallel execution is possible.
Let be the time of steps 3-4 of the algorithm (calculating the probabilities, finding the maximum and assigning it to the elements of the matrix). Then – the duration of the sequential implementation of the algorithm will be .
Let all the iterations be divided into parts of approximately equal size, which will
be processed by independent threads in parallel. Then – the minimum
duration of running a parallel algorithm implementation, which is
can theoretically be achieved. [
Thus, comparing and we can conclude that it is theoretically possible to achieve an acceleration of the matrix calculation by times (with a theoretical maximum in at ). However, the use of parallel implementation of the algorithm in practice requires additional data sharing and flow management costs, so that the practical acceleration will be less than . 4.2
Memoization is one of the methods of optimizing calculations, which consists of
storing the results of a function execution in a lookup table to prevent repeated
calculations [
In practice, memoization can only be applied to pure features that do not create side effects (such as file entries, database reads, etc.). Also, memoization cannot be applied if the calculation results have only a certain validity period, after which they must be re-calculated (in this case, more sophisticated techniques such as caching should be used).
The additional cost of memoization is only the need for additional memory to store the lookup table (its size depends on the set of valid values of the memoized function parameters).
In the case of calculating the term correlation matrix, memoization can be applied at the third point of the algorithm when calculating the parameters and from formula (1) of the calculation of . This will only require of additional memory, and if you use hash tables as lookup tables for memoization, the difficulty of getting the calculated result will be only . 5 5.1
To test the proposed methods of accelerating the calculation of the term correlation matrix, in the framework of this research an own algorithm for generating a textual data corpus was developed.
The developed algorithm has the following properties: 1. accepts only from the input parameters – the number of unique terms in the corpus texts; 2. is fully deterministic – the same result will be obtained for startups with the same input parameter value; 3. the generated corpus of texts contains pairs of terms with different degrees of correlation – fully correlated, partially, not at all correlated.
Due to the deterministic nature of this algorithm, it is possible to compare the obtained experimental data (the rate of calculation of the term correlation matrix) for the same matrix dimension with the use of different combinations of the proposed methods.
The developed algorithm for generating a textual data corpus (with a term correlation matrix of a given dimension) consists of the following steps: 1. based on the input value, calculate the number of texts in the corpus being generated, as well as the boundaries of the range of texts in which the next term will occur. Formulas (2) and (3) are used to calculate these two parameters; 2. for each from to : (a) obtain the row value of the next term by converting to hexadecimal; (b) calculate the indexes of the texts in which the next term will occur according to formula (4). In case if any index of the resulting set is negative or exceeds the index of the last text – this index is reduced to valid values; (c) calculate the number of occurrences of the term to the texts found in p.b: (i) the total number of occurrences of the term to the corpus is calculated by the formula (5); (ii) the number of occurrences of term to the central text of the range is ; (iii) the rest of the occurrences are distributed equally among the other texts of the range; (d) the term according to the number of occurrences calculated is added to the texts in the range. 5.2
The software based on C# and the .NET Core 2.2 platform has been developed for experimental studies of the proposed methods to accelerate the calculation of the term correlation matrix. The source code for the developed software is fully open and available at https://github.com/yakivyusin/IslandClusteringAcceleration.
The measurement of the performance of the calculation of the term correlation
matrix at different dimensions of the matrix and with different combinations of
acceleration methods used was performed using the BenchmarkDotNet library (v.0.11.5) [
The launch of the developed software was performed in Google Cloud Platform
virtual machine [
Testing the speed of calculating the term correlation matrix was performed for 8 dimensions: 49, 169, 245, 371, 441, 569, 659, and 785 terms. According to the developed algorithm for generating a textual data corpus, this set of dimensions provided the generation of corpora with sizes from 2 to 5 texts.
For each dimension of the test set, the term correlation matrix was calculated in twelve different ways: with sequential execution of cycles, with parallel execution of an external cycle, with parallel execution of both cycles, with memoization of calculation , with memoization of calculation , with memoization of calculation of both parameters.
The test results are shown in Table 1, in which the following notations are used to denote a matrix calculation variant: S – sequential execution of cycles; P – parallel execution of the external cycle only; P2 – parallel execution of both cycles; - – memoization of parameter calculation is absent (at the second position in the variant code corresponds to the parameter at the third position – parameter ); + – memoization of parameter calculation is present (at the second position in the variant code corresponds to the parameter , at the third position – parameter ). The present results have high accuracy with a low variance – the ratio of the standard deviation to mean is in the range from 0.01% to 6.7% (standard error is also within the range from 0.02% to 0.92%). All measurements (except one) where this ratio exceeds the mean value of the dataset are related to parallel implementations. This may be caused by the fact that parallel implementations are more sensitive to random changes in the workload of the operating system with multitasking, while sequential implementations just utilize one core and work on it. Also, the process of garbage collection might influence the variance of results without memoization, but on the experimental dataset this process is almost deterministic due to dataset volume.
The charts of the obtained results for matrices with dimensions of 659 and 785
terms are shown in Fig. 1 and Fig. 2 respectively. Interactive charts for all test data
are created using the Highcharts library [
From the obtained results, it can be concluded that the use of all the proposed methods to accelerate the calculation of the term correlation matrix, increases the performance by 8-10 times in total, provided there are 8 virtual cores (depending on the dimension of the matrix and the number of texts; shown in Fig. 3), compared to the «naive» implementation of calculations. As we can see, the main objective of the present paper is achieved –all proposed methods improve correlation matrix calculation performance in any given combination of used methods. The combination of all proposed methods (enabled parallelism and memoization of both calculation parameters) allows getting acceleration more than 8 times on machine with 4 physical cores / 8 virtual cores. Also, from the results obtained, the following dependencies can be emphasized: 1. clean use of parallelism leads to acceleration improvement more than 4 times. Such a result is because the test virtual machine has only 4 physical cores with 8 virtual cores; 2. memoization of parameter has a much greater effect on acceleration than memoization of parameter (average 2 times against average 1.05). We relate it to the fact that the calculation of is a more complex process and requires read collection of all corpus terms; 3. variants of parallelism implementation with one cycle and two almost do not differ from each other (P2 variant on average is faster on 4-6%). The internal features of .NET Core parallelism implementation might influence this result and also that even in case of used one parallel cycle the number of chunks exceeds free cores count. 6
In the present paper, we have described methods of acceleration of term correlation matrix calculation in the island text clustering method. Proposed methods are based on two techniques: parallel execution of iterations and memoization of interim results (coefficients in correlation calculation formula). According to experimental results, the performance of calculation has been improved more than 8 times on 8 virtual core machine within the range of different text corpora (test data was generated by a described algorithm which was developed especially for this paper). The obtained result exceeds a theoretical limit of parallel execution (which is equal to the number of cores) due to memoization using.
Future work on this subject may be in the following areas: 1. experimental testing on different machines (with different number of cores) to better determine the dependence between improvement ratio and the degree of parallelism; 2. porting an implementation to a programming language without a garbage collector to reduce the number of factors that affect the results.