David Pastorelli
email: dpastorelli@yahoo.fr

P R Wisse

Mcreynolds

A Classification of Manuscripts Based on A New Quantitative Method. The Old Latin Witnesses of John's Gospel as Text Case

Keywords:

A new method for grouping manuscripts in clusters is presented with the calculation of distances between readings, then between witnesses. A classification algorithm ("Hierarchical Ascendant Clustering"), achieved through computer-aided processing, enables the construction of trees illustrating the textual taxonomy obtained. This method is applied to the Old Latin witnesses of the Gospel of John, and, in order to provide a study of a reasonable size, to a chapter as a whole (chapter 14). The result basically confirms the text-types identified by Bonatius Fischer, founder of the Vetus Latina Institute, while it invalidates the classification adopted by the current edition of the Vetus Latina of the Gospel of John.

INTRODUCTION

Statistics are useful for textual criticism of the New Testament 1 and computer-aided processing is now unavoidable. However, most of the quantitative studies made of the text of the New Testament are based on the number of agreements between manuscripts. For every variation-unit and for every pair of witnesses, one counts the agreements: 1 when they have the same reading, 0 otherwise. The processing of the data involves preparing a table of the agreements two by two in the form of a lower triangular matrix, to convert the results into percentages, then to proceed to their classification in lists where the percentages are sorted in decreasing order. The credit for this belongs to Ernest Colwell who created the impetus with the Multiple Readings Method in the late 50s 2 . Two developments ensued with construed is twofold. On the one hand, it is a question of characterizing quantitatively the relative weight of a variant. Unlike the binary counting of the agreements (1 or 0), the distance between readings allows it to be seen that the variations are not all equivalent. According to the kind of variation and the length of the variation-unit, the distance between two readings oscillates between 0 and 12. On the other hand, the calculation of the distance between manuscripts proves to be a robust tool: it avoids an excessive alienation of the atypical witnesses that present a large number of singular readings, and at the same time offers the necessary precision for a meaningful classification of witnesses. This method will be applied to the Old Latin witnesses of the Gospel of John (37 to date) and, for a study of a reasonable size, to a chapter as a wholewe have selected chapter 14. The text of these manuscripts is available on the website www.iohannes.com, as part of the edition of the Vetus Latina, under the direction of D.C. Parker 9 . 10 manuscripts are entirely lacunose for this chapter 10 . The four manuscripts that have at the most 10% of the text (Table 1: VL 40 to VL 46) are also excluded from the present study insofar as their low attestation does not yield reliable results 11 . The result is that 23 codices are used for classification: Palatinus (e, VL 2), Vercellensis (a, VL 3), Veronensis (b, VL 4), Bezae (d, VL 5), Colbertinus (c, VL 6), Sangermanensis primus (g 1 , VL 7), Corbeiensis (ff 2 , VL 8), Fossatensis (VL 9A), Brixianus (f, VL 10), Rehdigeranus (l, VL 11), Würzburg Univ. 67 (VL 11A), Monacensis (q, VL 13), Usserianus primus (r 1 , VL 14), Aureus (aur, VL 15), Sangallensis (n, VL 16), Sangallensis 48 (δ, VL 27), Sangermanensis secundus (g 2 , VL 29), Gatianus (gat, VL 30), palimpsest of a Gallican lectionary (VL 32), Carnotensis (VL 33), Book of Mulling (μ, VL 35), Sangallensis 60 (VL 47), Sangallensis 51 (VL 48). The text of the Vulgate (vg) is added, counting as one witness (edition of Stuttgart). As soon as a variation occurs within this set of witnesses, a variation-unit is constituted. Thus we obtain a relatively large amount of text, as shown in Annex 1. There, it can be seen that there are 136 variation-units for 529 words if we take the Vulgate as a point of reference, which are listed according to the 31 verses of John 14.

I. THE DISTANCE BETWEEN READINGS

A variation-unit can be subject to three kinds of variation: (1) presence / absence; (2) substitution; (3) displacement 12 . In an article of 1988, C.-B. Amphoux13 proposed a quantification of the difference between two readings for each kind of variation. We take this measurement system, slightly modified:

displacement: 1 point per displaced group (the words are the same); examples: cognovistis me / me cognovistis (L9c) = 1; parare vobis locum / locum parare vobis (L2d) = 1; substitution: 1 point if the substitution is made with a similar word or form, 2 points otherwise (most of the words of the variation-unit are the same except the replaced words); examples: dicit ei / dicit illi (L5a) = 1; quia / quoniam (L28a) = 1, but paracletum / advocatum (L16b) = 2; presence / absence: 2 points for a verb, a noun, an adjective or an adverb formed from an adjective, 1 point for the others (pronoun, conjunction, preposition, adverb, particle, etc.) (most of the words vary and the calculation is identical whether we count from the reading where the words are present, or from the reading where they are absent); examples: patrem / patrem meum (L16a) = 1; mihi dedit / mihi dedit Pater (L31e) = 2.

The identification of a displacement or a presence / absence is relatively easy. A substitution is noted when one word changes inside a phrase; however, when the substitution concerns several words, it must always be calculated word for word. Finally, two out of the three, or all three, kinds of variation can be combined. Examples: accipere saeculum non potest / hic mundus non potest accipere (L17a) = 4 in sum (displacement of accipere = 1; substitution saeculum / mundus = 2; presence / absence of hic = 1). All the distances between readings are given in Annex 1.

II. THE DISTANCE BETWEEN MANUSCRIPTS

From the distance between readings, it is possible to define a distance between two manuscripts. The safest definition from a mathematical point of view is that of the Euclidean distance. Considered within this perspective, the distance between two witnesses is equal to the square root of the sum of the squares of the distances between their readings taken two by two. By way of illustration, we may consider the first five variation-units in verse 1 and calculate the Euclidean distance between codex Palatinus (e, VL 2) and the Vulgate (vg):

Variation-units L1a L1b L1c L1d L1e Distances between the readings of VL 2 (e) and vg 0 1 3 2 0

The distance between VL 2 (e) and vg is then equal to:

√(0 2 + 1 2 + 3 2 + 2 2 + 0 2 ) = √14 = 3.7.
This definition is now applied to the 136 variation-units for the Vulgate. We give in Table 2 the distances between vg and the 23 Old Latin manuscripts under consideration for John 14. The distances are sorted in increasing order, i.e. from the manuscript closest to vg to the farthest. Codex Palatinus (e, VL 2) is the farthest from the Vulgate. In addition to that manuscript, we find that the Old Latin manuscripts known to be the most representative of the early, pre-Vulgate text are the farthest from vg: VL 3 (a), 14 (r 1 ), 5 (d), 13 (q), 6 (c), 8 (ff 2 ), and 4 (b). Conversely, the Old Latin manuscripts more influenced by the Vulgate (mixed texts) are: VL 33, 7 (g 1 ), 29 (g 2 ), 11A, and 47. On the other hand, the manuscripts VL 32 and 16 (n) should for the moment be put to one side because of their lacunae. Indeed, if the same list of distances is drawn up for VL 32, vg is the fifth witness and four other manuscripts are closer to VL 32; likewise, for VL 16 (n), vg is in 10th place. The distance between two manuscripts only makes sense within the context of all the 24 witnesses. Only in this network of interrelationships is a comparison possible. It is thus necessary to calculate the distances of all the witnesses two by two. For John 14, one obtains 276 values presented in a lower triangular matrix (Table 3, see end of article)14 . The majority of the quantitative studies would then show for each witness a column where the distances from the other manuscripts would be sorted in increasing order. The search for a classification on this model would prove difficult, if not impossible, because of the number of columns to be treated (23) and their identical length. In the face of this mass of data, a systematic method using the computer is preferable. The most appropriate statistical tool in our view is the clustering method.

III. CLASSIFICATION

After first presenting this method, we shall then go on to interpret the processing of the data of John 14.

The Clustering Method

The purpose of the clustering method is to distribute the individual elements of the sample in clusters where they are as similar as possible. At the same time, the clusters should be as dissimilar as possible. The construction of a hierarchical clustering entails, first, the formation of small clusters with very similar individual elements, then from these clusters to build others less and less homogeneous, until the sample is exhausted. This algorithm is called the "Hierarchical Ascendant Clustering" (HAC). It is based on the calculation of the distance between two distinct clusters. The rule for calculating this distance is called an "aggregation criterion". The aggregation criteria are as varied as the many possibilities of classification. Let us mention three of the most common:

-The minimum step or the criterion of the nearest neighbours (single linkage): the distance between two clusters is the smallest distance between elements of the two clusters.

-The maximum step or the criterion of the most remote neighbours (complete linkage): the distance between two clusters is the greatest distance between elements of the two clusters.

-The criterion of the average (average linkage): the distance between two clusters is the average of all the distances between elements of the two clusters.

The distance between clusters having been defined, the algorithm of the HAC then proceeds to the next stages. At the initial stage, each witness forms a cluster. Thus, there are 24 clusters. In the first stage, the table of distances between witnesses makes it possible to bring together the two closest witnesses, which will be aggregated into a new cluster. We then obtain 23 clusters. In the second stage, a new table of distances between the 23 clusters is established. The two closest clusters are gathered together and we obtain 22 clusters. The process is repeated until we obtain only one cluster. The result of the HAC is represented by a clustering tree or "dendrogram". This encompasses all stages of aggregation. The interpreter must therefore locate a natural break in the tree, enabling him or her to identify the number of homogeneous clusters and to give them a meaning. The tree schematizes distances between witnesses, or conversely a close relationship. In no way does it reflect any filiation and it looks nothing like a stemma codicum 15 .

For statistical processing, we used the free software R and chose as the criterion of aggregation of clusters the method of Ward, which is the standard method used for Euclidean data 16 . The manuscript VL 32 (the remains of a Gallican lectionary) had to be removed from the data because it disturbed the results, having only the text of the verses 13-19 of John 14. The resulting tree is given in Figure 1 (see end of article).

Interpretation of the Classification

The classification identifies two groups: in the lower part of the tree are the Old Latin manuscripts most representative of the pre-Vulgate text (12 witnesses), and in the upper part, the manuscripts whose text is more influenced by the Vulgate (11 witnesses). We suggest an interpretation of this classification into two groups, made in the light of the text-types masterfully synthesized by Bonatius Fischer 17 .

Group 1: the Old Latin manuscripts

It is generally agreed that the Old Latin manuscripts can be divided into two text-types. The African type is the text from around 230 and is represented primarily by codex Bobiensis (k, VL 1), then by Cyprian and e (VL 2). It gradually gives way to the European type of which b (VL 4), ff 2 (VL 8) and i (VL 17) are the leaders (the Italian text of the years 350-380). Unfortunately, k (likewise i) is lacunose for John. VL 3 (a) and 16 (n) represent a first form of the European type, close to Novatian. Also belonging to the European Old Latin manuscripts group whose African stratum is still present are codex Colbertinus (c, VL 6) and the problematic codex Bezae (d, VL 5), and codex Usserianus primus (r 1 , VL 14), which is the main representative of a subgroup of the Italian type (Gallo-Irish group).

These Old Latin manuscripts are found in the group of witnesses located in the lower part of the tree (Group 1). The only notable exception is the presence of codex Sangallensis 48 (δ, VL 27). In our study of the text of the Gospel of John in the Latin translation of Origen's Commentary on Matthew, we noticed that VL 27 formed in itself a cluster in the tree because of the large number of conflated readings 18 . The copyist seemingly has before his eyes two distinct texts, one of which preserves Old Latin readings. A classification of group 1 without this manuscript provides better results (Figure 2).

The algorithm provides a tree which enables us to follow the construction of each node with a graduated scale (Figure 1: 0-50; Figure 2: 0-35). In reading the tree, the interpreter has to determine where to make a break that enables a number of homogeneous clusters to be identified. The first clusters formed, and thus the more homogeneous ones, are in the group of manuscripts influenced by the Vulgate (Group 2). As regards the Old Latin manuscripts group (Group 1), we have four clusters in the following order of appearance: (1) VL 6 (c), 11 (l), 8 (ff 2 ), 16 (n), and 4 (b); (2) VL 10 (f), 13 (q), 14 (r 1 ), and 5 (d) ; (3) VL 3 (a) ; (4) VL 2 (e). Six comments may be made:

1. The first cluster formed clearly corresponds to the European type, of which codex Veronensis (b, VL 4) and Corbeiensis (ff 2 , VL 8) are the best representatives. Moreover, VL 6 (c) is known to be close to VL 8 (ff 2 )19 .

2. VL 14 (r 1 ), which is an excellent witness of the European text and belongs to the Gallo-Irish group, shares more than one reading with codex Monacensis (q, VL 13). The philologist will not fail to be surprised by the place of codex Rehdigeranus (l, VL 11). It is generally agreed that q and l form a subgroup of the European text type20 . However l, which contains only the verses 23-31 of John 14, opposes this view here.

3. Codex Brixianus (f, VL 10) contains a "mixed" text21 : as regards the gospel of John, it is classified with the Old Latin manuscripts, the Vulgate influence being secondary.

4. In the construction of the clustering tree, codex Bezae (d, VL 5) precedes VL 3 (a) and 2 (e). At the philological level, the text of d for the gospels of Luke and John is between e and a. It has an African stratum while under the influence of the European text22 . 5. Codex Vercellensis (a, VL 3), which represents the oldest form of the European text, usually in the company of fragments of St. Gallen, VL 16 (n), constitutes a cluster by itself.

Codex

Palatinus (e, VL 2) is the most difficult to classify following the formation of clusters. It is its African stratum that no doubt accounts for this fact.

Group 2: the Old Latin manuscripts more greatly influenced by the Vulgate (mixed text)

We find three clusters in the following order of appearance: (1) vg, VL 33, 7, 29, 11A, 47; (2) VL 48, 9A, 35, 30; (3) VL 15. Let us examine them. 1. VL 33, which contains only the gospel of John, here is the closest to the Vulgate text: account must be taken of the fact that it has an Old Latin text for chapters 1-6 and Vulgate for the rest. Codex Sangermanensis primus (g 1 , VL 7) also has without doubt an Old Latin stratum but, in this case, the influence of Vulgate is predominant. VL 29 contains a mixed text which derives from a regional group of Vulgate manuscripts, Celtic family DELQR. VL 47 has an Irish mixed text (Old Latin in Jn 1,29-3,26). Finally, VL 11A was recently included in the list of the Vetus Latina Institut and Hugh Houghton 23 has shown that the text of Jn 1,1-5,40 and 12,34-13,10 is Old Latin.

2. Manuscripts VL 35, 30 and 48 have in common that they display an Irish mixed text for John (Celtic family DELQR). VL 9A must be added to these witnesses. The recent study of Houghton [START_REF] Houghton | The St Petersburg Insular Gospels: Another Old Latin Witness[END_REF] prompted the inclusion of this manuscript in the list of Old Latin manuscripts. The author concludes from a survey of synonymous terms that this manuscript has an Old Latin sourcethe parallels with VL 2, 3, 13, 14 show the antiquity of the source textbut at the same time that there is no closeness to a particular manuscript. But according to our previous study [START_REF] Pastorelli | Commentaire sur Matthieu d[END_REF] , 9A forms a cluster with codex Aureus (aur, VL 15) which contains a mixed text with Vulgate readings and Old Latin readings of the European type. This cluster VL 9A-15 was formed immediately after the cluster VL 35, 30, 48. In the present case, the classification is similar: 9A is inserted into the Celtic family, just before the inclusion of aur, which forms a cluster apart.

Classification into Text-Types

The classification into two groups that has been achieved deserves to be compared with that proposed by Philip Burton [START_REF] Burton | The Old Latin Gospels. A Study of their Texts and Language (Oxford Early Christian Studies)[END_REF] , insofar as discrepancies with our conclusions are apparent. Burton identifies the existence of two European text-types (not one), the second containing the Vulgate and mixed texts; the two groups are a d q r 1 e and aur c f ff 2 l vg. His classification is based on a review of the translation of nine Greek terms. His main result is the non-existence of a European kernel formed by b and ff 2 . On the one hand, b would belong to the first group for John 1-9 and to the second for 10-21. On the other hand, ff 2 should be classified with a mixed text and the Vulgate. In our view, the sample used by Burton is too small, in terms of not only the number of variants but also the number of manuscripts. The sample of 136 variation-units of John 14 represents more than 520 words and involves 23 witnesses. The classification thereby obtained confirms the European kernel b-ff 2 in the Old Latin witnesses (Group 1) and also refutes any exclusion of manuscripts c, l and f from this group. Furthermore, it demonstrates conclusively the separation between the group of Old Latin manuscripts (Group 1) and the group influenced by the Vulgate (Group 2). 29 . In his review of the third instalment of the edition of Mark, Houghton draws a parallel between the two projects and condemns the text-type approach: "The alternative, adopted in the Vetus Latina edition of John, is to jettison text-types altogether and leave users to draw their own conclusions from an unmediated presentation of the manuscripts" 30 . Indeed, the editors of John, who will deliver their introduction at the end of their work, abandon text-types to adopt three groups: Group 1: VL 2 3 4 (in the first nine chapters) 5 13 14 20 22 24 and 47 (John 2) Group 2A: VL 6 8 11 11A 16 18 25 Let us examine the three groups of the Vetus Latina edition of John. Its Group 1 gathers our groups 1A, 1B, and 1C, except that VL 10 is missing. Group 2A corresponds to our group 1D. Group 2B brings together our groups 2A and 2B, except VL 11A is missing. Abandoning the writing of the history of the text no longer enables the distances existing between clusters VL 2 / VL 3 / VL 5, 10, 13, 14 (our groups 1A, 1B, and 1C) to be taken into account, nor the gap between the two subgroups of the Vulgate sphere (our groups 2A and 2B). The Clustering Method allows the construction of each node to be followed. So gradually as nodes are formed, the distances between manuscripts increase. Thus the Clustering Method shows that it is impossible that Group 1 of the Vetus Latina of John constitutes one single homogeneous cluster. Internal distances are too important and the existence of three clusters must be recognized, which are also the last to be formed in the tree (see Figure 2: Group 1A, 1B, 1C). Conversely, the first cluster formed, the one that is the most homogeneous (Group 1D), is the European kernel of which VL 4 (b) and 8 (ff 2 ) are the best representatives. In sum, our classification of Old Latin witnesses

CONCLUSION

Following this path, we can draw conclusions both on the method and on the results obtained. From a methodological point of view, the calculation of distances between readings, then between witnesses, is mainly characterized by stability and robustness of results. In terms of readings, the method allows us to take into account quantitatively the various kinds of variation on a scale ranging from 0 to 12, while the counting of the agreements standardizes the difference between readings (0 or 1). In terms of manuscripts, it makes a continuous reading of the text of John 14 possible. It thus avoids an arbitrary selection of variation-units that possibly would lead textual material to be overlooked that could be useful for the classification and especially to increase unduly a particular textual affinity. We have to apply a proportionality principle that results in a reliable classification of witnesses. The selection, for example, of the non-Vulgate readings of a manuscript alters the results; the same methodological error was made for Greek manuscripts of the New Testament when the percentages of agreements between two manuscripts were calculated by excluding the readings of the "Textus Receptus". In sum, attention must be paid to the network of interrelationships within which a comparison is alone possible. This is the goal of the method of "classification" ("Hierarchical Ascendant Clustering"), which analyzes hundreds of distances. In John 14, the clusters revealed by the algorithm show clearly that the text-types synthesized by Bonifatius Fischer are not to be doubted. On the contrary, textual taxonomy finds in the clustering method a solid foundation.

  Computazionale, 20-21). Istituti Editoriali e Poligrafici Internazionali (Pisa-Rome), 2004:305-341; Macé C., Baret P.V. Why Phylogenetic Methods Work: The Theory of Evolution and Textual Criticism. Macé C., Baret P.V., Bozzi A. (eds.) The Evolution of Texts: Confronting Stemmatological and Genetical Methods. Proceedings of the International Workshop Held in Louvain-la-Neuve on September 1-2, 2004 (Linguistica Computazionale, 24). Istituti Editoriali e Poligrafici Internazionali (Pisa-Rome), 2006:89-108; Macé C., De Vos I., Geuten K. Comparing Stemmatological and Phylogenetic Methods to Understand the Transmission History of the Florilegium Coislinianum. Bucossi A., Kihlman E. (eds.) Ars edendi. Lectures Series. Volume II (Acta Universitatis Stockholmiensis. Studia Latina Stockholmiensia, 58). Stockholm University Press (Stockholm), 2012:107-129; Andrews T.L., Macé C. Beyond the Tree of Texts: Building an Empirical Model of Scribal Variation Through Graph Analysis of Texts and Stemmata. Literary and Linguistic Computing. 2013;28:504-521. 17

  Fischer B. Das Neue Testament in lateinischer Sprache. Der gegenwärtige Stand seiner Erforschung und seine Bedeutung für die griechische Textgeschichte. Kurt A. (ed.) Die alten Übersetzungen des Neuen Testaments, die Kirchenväterzitate und Lektionare. Der gegenwärtige Stand ihrer Erforschung und ihre Bedeutung für die griechische Textgeschichte (Arbeiten zur neutestamentlichen Textforschung, 5). W. de Gruyter (Berlin-New York), 1972:30-39. See also Gryson R. Altlateinische Handschriften. Manuscrits vieux latins. Répertoire descriptif. Première partie: Mss 1-275 d'après un manuscrit inachevé de Hermann Josef Frede † (Vetus Latina. Die Reste der altlateinischen Bibel, 1/2A). Verlag Herder (Fribourg-en-Brisgau), 1999; Haelewyck J.-C. Les versions anciennes. Amphoux C.-B., Dorival G., Elliott J.K., Haelewyck J.-C., Pastorelli D., Reynard J. Manuel de critique textuelle du Nouveau Testament. Vol. 1: Introduction générale (Langues et cultures anciennes, 22). Éditions Safran (Bruxelles), 2014:87-88.

  P.H. Burton, H.A.G. Houghton, R.F. MacLachlan, and D.C. Parker are now editing the Vetus Latina of the Gospel of John, of which the first nine chapters have already been published 27 . The second Old Latin Gospel being published is that of Mark edited by Jean-Claude Haelewyck 28 . A comparison between the two projects is illuminating in this regard. The latter endeavours to reconstruct the texttypes along the lines proposed by B. Fischer: K, the ancient African text VL 1 [k]), C, the recent African text (VL 2 [e]), D, the European text (VL 3 [a] ; VL 16 [n+o]), I, the European text (VL 4 [b]; 8 [ff 2 ]; 17 [i]; 5 [d]; 13 [q]; 14 [r 1 ]; 6 [c]), V, the Vulgate text

29

  Ibid.:24-111. 30 Journal of Theological Studies. 2015;66:396. Houghton H.A.G. Patristic Evidence in the New Edition of the Vetus Latina Iohannes. Vinzent M., Mellerin L., Houghton H.A.G. (eds.) Studia Patristica. Vol. LIV. Papers presented at the Sixteenth International Conference on Patristic Studies held in Oxford 2011. Volume 2: Biblical Quotations in Patristic Texts. Peeters (Leuven-Paris-Walpole), 2013:71: "The variety of readings preserved in the manuscripts meant that it was not necessary to use the patristic citations as the basis for text-types. In fact, no hypothetical text-types are reconstructed in the edition: the schema instead gives the text of the manuscripts in three broad groups at the top of the page". 31 Burton P.H., Houghton H.A.G., MacLachlan R.F., Parker D.C. (eds.) Iohannem. Fascicle 1, 2011:11, also excluded is Sangallensis 48 (δ, VL 27). http://jdmdh.episciences.org ISSN 2416-5999, an open-access journal essentially confirms the text-types previously generated for the gospels, especially those of Mark. Patristic quotations are then used to locate in time and space these different text-types.

Table 1 :

 1 Old Latin Witnesses lacunose in John 14

	Manuscript	Number of lacunae in 136 variation-units Percentage of preserved variation-units
	VL 40	127	6.6%
	VL 10A	124	8.8%
	VL 39	123	9.6%
	VL 46	122	10.3%
	VL 32	114	16.2%
	VL 16 (n)	105	22.8%
	VL 11 (l)	93	31.6%

9

Burton P.H., Houghton H.A.G., MacLachlan R.F., Parker D.C. (eds.) Vetus Latina. Die Reste der altlateinischen Bibel. Vol. 19: Evangelium secundum Iohannem. Fascicle 1: Jo 1,1-4,48. Fascicle 2: Jo 4,49-9,41. Herder (Fribourg), 2011-2013.

10

VL 18 (π), 20 (p), 22 (j), 22A, 23, 24 (ρ), 25 (ν), 28 (r 2 ), 34 et 49.

11

In the same way, the conclusions on manuscripts VL 16 (n, 22.8% of preserved variation-units [= Jn 14,23-30]), 32 (16.2% [= vv. 13-19]), and, to a lesser degree, 11 (l, 31.6% [= vv. 23-31]) need some qualification.

Table 2 :

 2 Distances between vg and the Old Latin Witnesses in John 14

	vg	Distances
	VL 33	2.65
	VL 32	3.32
	VL 7 (g 1 )	3.74
	VL 29 (g 2 )	4.90
	VL 11A	5.92
	VL 47	5.92
	VL 16 (n)	6.16
	VL 9A	7.14
	VL 48	8.19
	VL 35 (μ)	8.25
	VL 11 (l)	8.66
	VL 30 (gat)	9.22

  and 4 (from John 10 onwards) Group 2B: vg VL 7 9A 10 15 28 29 30 32 33 35 47 48.Considering the manuscripts used for John 14 31 , our classification results in a total of six clusters, four for the Old Latin manuscripts (Group 1) and two for manuscripts more influenced by the Vulgate (Group 2):

	Group 1A: VL 2
	Group 1B: VL 3
	Group 1C: VL 5 10 13 14
	Group 1D: VL 4 6 8 11 16
	Group 2A: VL 9A 30 35 48 (15)
	Group 2B: vg VL 7 11A 29 33 47.

Table 3 :

 3 Distances between Manuscripts in the 136 Variation-Units of John 14

	Distan ces	vg	VL 2(e )	VL 3(a )	VL 4(b )	VL 5(d )	VL 6(c )	VL 7(g 1 )	VL 8(ff 2 )	VL 9A	VL 10( f)	VL 11( l)	VL 11 A	VL 13( q)	VL 14( r1)	VL 15(a ur)	VL 16( n)	VL 27( δ)	VL 29( g 2 )	VL 30(g at)	V L 32	V L 33	VL 35( μ)	V L 47
	VL2(e	26.
	)	50
	VL3(a	24.	31.
	)	43	13
	VL4(b	17.	31.	23.
	)	41	02	26
	VL5(d	19.	27.	26.	25.
	)	70	18	53	77
	VL6(c	17.	30.	20.	15.	23.
	)	80	68	74	46	58
	VL7(g	3.7	26.	24.	17.	19.	18.
	1 )	4	94	43	58	80	00
	VL8(ff	17.	29.	23.	16.	24.	13.	17.
	2 )	58	80	28	43	90	27	80
	VL9A	7.1 4	26. 21	24. 58	16. 73	19. 47	17. 26	7.6 2	17. 41
	VL10(	12.	27.	23.	18.	20.	19.	12.	18.	12.
	f)	21	48	62	89	64	42	61	87	45
	VL11(	8.6	16.	14.	8.8	14.	8.4	8.4	8.8	9.2	10.
	l)	6	94	76	3	56	3	9	9	7	05
	VL11	5.9	26.	24.	18.	20.	18.	6.7	18.	8.1	12.	8.6
	A	2	40	15	06	71	28	1	25	9	65	0
	VL13( q)	17. 80	26. 42	23. 07	22. 38	20. 59	22. 65	17. 72	22. 10.	18.	20.	13.1	9.0	15.	9.9
													39	52	42	9	0	20	0
	VL32	3.3 2	12. 04	7.8 7	10. 34	4.3 6	8.6 6	3.1 6	8.8 3	3.3 2	5.2 9	0.0 0	4.5 8	7.6 8	7.2 8	3.74	0.0 0	3.7 4	4.0 0	3.74
	VL33	2.6 5	26. 36	24. 23	17. 44	19. 44	17. 58	4.1 2	17. 32	6.6 3	11. 83	8.4 3	5.4 8	17. 26	20. 07	10.2 0	5.8 3	12. 12	4.5 8	9.06	3. 32

Figure 1. Classification of 23 Latin Witnesses in John 14 Figure 2. Classification of 11 Old Latin Witnesses in John 14 Annex 1: Variation-Units and Distances between Readings in John 14

On the question of the various quantitative methods for the textual classification or taxonomy, see the fundamental article, published in 1975, by Duplacy J. Classification des états d'un texte, mathématiques et informatique: repères historiques et recherches méthodologiques. Id. Études de critique textuelle du Nouveau Testament (Bibliotheca Ephemeridum Theologicarum Lovaniensium, 78). Leuven University Press (Louvain), 1987:193-257.

Colwell E.C. Method in Locating a Newly-Discovered Manuscript. Id. Studies in Methodology in Textual Criticism of the New Testament (New Testament Tools and Studies, 9). E.J. Brill (Leiden), 1969:26-44; Id.,Tune E.W. Method in Establishing Quantitative Relationships Between Text-Types of New Testament Manuscripts. Ibid. 56-62.

http://jdmdh.episciences.org

Thus Fee G.D. On the Types, Classification, and Presentation of Textual Variation. Epp E.J., Fee G.D. Studies in the Theory and Method of New Testament Textual Criticism (Studies and Documents, 45). W.B. Eerdmans (Grand Rapids), 1993:63: "The kinds of variation narrow to three: (1) add/omit ... (2) substitution ... and (3) word order ... any two or all three of these may occur in combination in any set of variants".

Amphoux C.-B. Un indice de variation pour le classement des états d'un texte. Revue d'Histoire des Textes. 1988;18:282.

Journal of Data Mining and Digital Humanities http://jdmdh.episciences.org

The upper triangle is left empty in so far as it would be identical by symmetry to the diagonal.

For recent discussions about stemmatology, see the contributions collected in the two following volumes: van Reenen P., van Mulken M. (eds.) Studies in Stemmatology. J. Benjamins (Amsterdam-Philadelphia), 1996; van

Pastorelli D. Commentaire sur Matthieu d'Origène. 2015:64.

The closest manuscript to VL 6 (c) is 8 (ff 2 ) at a distance of 13.27, followed by 4 (b) at a distance of 15.46.

Gryson R. Altlateinische Handschriften, 1999:34.

A "mixed" text is a text that either simultaneously contains Old Latin and Vulgate readings in variable proportions or alternates between Old Latin sections and Vulgate sections.

Auwers J.-M. Le texte latin des Évangiles dans le Codex de Bèze. Parker D.C., Amphoux C.-B. (eds.) Codex Bezae. Studies from the Lunel Colloquium June 1994 (New Testament Tools and Studies, 22). E.J. Brill (Leyde-New York-Cologne), 1996:196-209.


X E Pantazi
email: renepantazi@gmail.com

D Moshou

A A Tamouridou

S Kasderidis

Leaf Disease Recognition in Vine Plants based on Local Binary Patterns and One Class Support Vector Machines

Keywords: image processing, novelty detector, classifier conflict, texture descriptors

The current application concerns a new approach for disease recognition of vine leaves based on Local Binary Patterns (LBPs). The LBP approach was applied on color digital pictures with a natural complex background that contained infected leaves. The pictures were captured with a smartphone camera from vine plants. A 32-bin histogram was calculated by the LBP characteristic features that resulted from a Hue plane. Moreover, four One Class Support Vector Machines (OCSVMs) were trained with a training set of 8 pictures from each disease including healthy, Powdery Mildew and Black Rot and Downy Mildew. The trained OCSVMs were tested with 100 infected vine leaf pictures corresponding to each disease which were capable of generalizing correctly, when presented with vine leave which was infected by the same disease. The recognition percentage reached 97%, 95% and 93% for each disease respectively while healthy plants were recognized with an accuracy rate of 100%.

Introduction

Plant recognition is regarded as a puzzling computer vision problem which requires dealing with irregular shapes and textures. Interest in methods for visual classification of plants has grown recently [START_REF] Belhumeur | Searching the world's herbaria: 16, A system for visual identi_cation of plant species[END_REF] as devices equipped with cameras became ubiquitous, making intelligent field guides, education tools and automation in forestry and agriculture practical. Belhumeur et al [START_REF] Belhumeur | Searching the world's herbaria: 16, A system for visual identi_cation of plant species[END_REF] presented how using such a system in the field enables a botanist to quickly search vast collections of plant species -a process that was time consuming and laborious can now be implemented in seconds. Recognition of leaves is usually applied on broad leaves and needles are treated separately. Several techniques have been introduced for leaf description, utilizing shape features and colour features. The leaf recognition approach which was presented by Fiel and Sablatnig [START_REF] Fiel | Automated identication of tree species from images of the bark, leaves and needles[END_REF] was based on a Bag of Words model with SIFT descriptors and reached 93.6% accuracy on a leaf dataset of 5 Austrian tree species. Kumar et al. [START_REF] Kumar | A computer vision system for automatic plant species identication[END_REF] proposed Leafsnap, which is a computer vision system capable of identifying plant species, They introduced a pre-filter on input images, numerous speed-ups and additional post-processing within the segmentation algorithm, the use of a simpler and more efficient recognition algorithm based on curvature instead of Inner Distance Shape Context (IDSC); an image dataset with more images, and an interactive system that can be used by non-expert users. The final product was an electronic field guide, available as a free mobile app for iOS devices. Even though the app runs on iPad and iPhone devices, the images of the leaves have to be processed on a server. This requires an internet connection to achieve recognition, so it is problematic for use in natural areas without access to internet or a limited bandwidth connection. Another severe limitation concerns the need to obtain photos of the leaves with a white background. The contribution of the current paper concerns an effective combination of pre-processing stages and One Class Classifiers applied on complex natural scenes with aim to discover early stages of infections in field grown crops enabling faster and more effective prevention of crop epidemics that threaten food supply and quality. The presented approach consists of training one classifier per disease and presenting the feature vector to a committee of one class classifiers which decide autonomously by having been trained only on target data. In the event that there is a multiple activations of one class classifiers the resultant conflict is overcome by an original conflict resolution method that utilizes the proximity of the nearest support vector to make an accurate decision which reached 97% for testing with unforeseen examples. The mentioned technique can generalize in multiple crops for three diseases while it has been trained only with vine leaves.

Materials and Methods

Image Segmentation

The segmentation operation needed to extract the leaf that has the symptoms was implemented by making use of the GrabCut algorithm. The basic steps for implementing the GrabCut algorithm in the leaf segmentation [START_REF] Rother | GrabCut: Interactive foreground extraction using iterated graph cuts[END_REF] are presented as follows:

The initial information provided about the foreground and the backgrounds are given by the user is a rectangular selection around the object of interest. Pixels that reside outside this selection are considered as known background and other pixels inside are marked as unknown. From this data we wish to create a model which can be used to decide if the unknown pixels are foreground or background. In the GrabCut algorithm this is achieved by creating K components of multivariate Gaussian Mixture Models (GMM) corresponding to the two regions. K components are created from the known background and K components correspond to the region that could belong to the foreground, giving a total of 2*K components. The GMM components have the same dimensions as the color space and they are defined based on the color statistics from each cluster. In order to obtain a good segmentation we need to add components with low variance because this makes cluster separation easier.

The Local Binary Patterns (LBPs)

The local binary pattern is a simple but very effective texture operator which tags the pixels of an image by thresholding the region of each pixel and considers the outcome as a binary number. The LBP scheme can be seen as a fusing approach to the traditionally deviating statistical and structural representations of texture analysis. Perhaps the most significant property of the LBP operator in actual applications is its invariance beside monotonic gray level deviations caused, e.g., by illumination differences.

Another likewise important is its computational effortlessness, which makes it possible to analyze images in puzzling real-time situations. The original local binary pattern operator, presented by Li, J., et al. [START_REF] Li | One step beyond histograms: Image representation usingMarkov stationary features[END_REF] and Llado, et al. [START_REF] Llado | A textural approach for mass false positive reduction in mammography[END_REF] was founded on the conjecture that texture has locally two balancing aspects, a pattern and its strength.

The operator works in a 3 × 3 locality, using the center value as a threshold. An LBP code is created my multiplying the thresholded values with loads given by the corresponding pixels, and summing up the outcome. As the neighborhood comprises of 8 pixels, a total of 28 = 256 dissimilar labels can be obtained dependent on the relative gray values of the epicenter and the pixels in the locality. The contrast measure (C) is acquired by subtracting the average of the gray levels under the center pixel after that of the gray levels above (or equal to) the center pixel. If the eight thresholded neighbors of the middle pixel have an identical value (0 or 1), the value of contrast is set to zero. The distributions of LBP codes are used as features in grouping or segmentation. The local binary pattern (LBP) operator is an image operator which converts an image into a group or image of integer labels relating to small-scale appearance of the image. These labels or their statistics, and one of the most commonly used is the histogram, are then applied for further image analysis. The most frequently used versions of the operator are aimed for monochrome still images nevertheless it has been extended likewise for color (multi channel) images and also for videos and volumetric data. An example of an H-plane image and corresponding LBP image are shown in Figures 3 and4.

The creation of the LBP histogram

The segmented image acquired from the GrabCut algorithm is utilized to create different monochrome descriptions as the LBP algorithms operates in single channels. Three diverse options were tried, the gray level, Hue channel and saturation channel.

One Class Support Vector Machines (OCSVMs)

To support One Class SVM Classification a suitable description of the configuration of SVM as a model to designate target data was presented by Tax and Duin [START_REF] Tax | Support vector data description[END_REF] in the form of Support Vector Data Description (SVDD). The objective of SVDD is to learn a decision function in order to predict if an example is actually a target or an outlier. SVDD is created based on the supposition that targets are bounded by a close boundary in the feature space. The OCSVM creates a model from performing adjustment by normal data according to the SVDD description. At the following stage, orders test data based on the deviance from normal training data as being either normal or outlier [START_REF] Sachs | One-class support-vector machines for the classification of bioacoustic time series[END_REF].

2.4.1

One-Class Support-Vector-Learning for Multi Class Problems

The described one-class approach can be applicable to multiclass problems in the following way. It is anticipated that data samples from k different classes are given.

Let Ω = {1, . . . , k} denotes the set of classes. For each distinct class t ∈ Ω a one-class classifier f t is created. Specifically, k centres and corresponding radii R t are considered. To determine the class relationship of a new undetected pattern z all decision functions are calculated in parallel leading to class memberships. In the classification stage of an undetected input pattern z three probable resulting circumstances have to be distinguished:

1. If just one classifier shows its bond for the new pattern, the resultant class label is the class membership of this classifier. 2. If more classifiers raise a claim for this pattern, a conflict situation has arrived. 3. On the other hand it is possible that no classifier matches, so in this case we can characterize this outcome as an outlier situation.

The problematic with such uncertain (2 and 3) classification assignments can be disentangled in two ways: Discarding the classification of the novel pattern or finding the matching class label through an outlier-/conflict processing approach. In the subsequent section we will present a strategy to crack such problems [START_REF] Sachs | One-class support-vector machines for the classification of bioacoustic time series[END_REF].

Nearest-Support-Vector Strategy

The class label of a novel pattern z is assessed by comparing the remoteness to the support vectors of the involved classifiers. The classifier that has the nearest support vector defines the class membership of z assuming that are the support vectors, and i t is the amount of support vectors of classifier t.

 

 

 ( ) argmin || ||

l i l C f z x z    ( 2 )
The decision function is then demarcated by where the minimum will be taken over all the support vectors of classes after the candidate set [START_REF] Schölkopf | Estimating the support of a high-dimensional distribution[END_REF].

Results and Discussion

Application of LBP in disease recognition of infected vine leaves

Initially, smartphone photo is obtained from infected plants. The standard requirement is that a leaf demonstrating symptoms of powdery mildew is situated in the center of the image. To obtain only the leaf area and subtract the background, a segmentation operation is performed. Then, the HSV image is obtained and the Hue plane is shown in Fig. 5. The corresponding LBP image obtained from the Hue plane of Fig. 5 is shown in Fig. 6. Then the LBP image is used in order to calculate the histogram with 32 bins. The global LBP histogram equation is given as follows:

, ( ) ( ( , ) )

x y image

H i I f x y i     (3)
where i=1,…32, I represents the indicator function used for thresholding and f(x,y) represents the LBP label. The histograms have been used as input in One Class Classifiers in the form of One Class SVMs in order to recognize specific leaf samples as a target class and treat healthy samples and other samples from different diseases as outliers. The Kernel function that has been used was RBF. The default width of the tube was e=0.1. Eight samples were enough for building powdery mildew model in vines that can recognize this disease. A similar procedure was followed for healthy leaves of vines, by building an one Class SVM model that could recognize only healthy leaves. Cross testing of each One Class SVM with leaves from the other category showed perfect classification for the calibration sets and additional samples that were picked randomly from the internet and smartphone. In the current work OpenCV Computer Vision Library Version 2.4.11 has been used for image processing and classifier development.

The One Class SVM that has been trained on vines to recognize powdery mildew is called 'powderyHSV' and it has been stored in XML format. It has been tested in various infected vine leaves successfully. Here, it is tested on vine leaves.. Initially, the powderyHSV One Class SVM recognizes the disease successfully (Fig. 7). However, in order to test the selectivity of the model, a second model has been utilized, that is called 'blackrotHSV' and recognizes black rot (Fig. 8). As it is shown below (Fig. 7), both models are activated from the observed symptoms as belonging to the sphere of confidence of one Class SVM of each model. Conflict resolution takes place by calculating the distances from the support vectors of the test image feature vector (Hue histogram) (Fig. 7). The result of the conflict resolution is that the actual model, it is identified to be powderyHSV, which is correct (Fig. 7). One hundred samples from each class were used (actual infection from powdery mildew, black rot and downy mildew).Without applying nearest vector based conflict resolution, it was impossible to achieve correct classification in 50% of the cases. Through conflict resolution, 100% percentage was reached in classifying both infected and healthy state. The numbers reached 97% for powdery mildew identification, compared to support vector machine model for black rot and downy mildew. The recognition percentage reached 95% and 93% for black rot and downy mildew respectively. In all disease cases, the test samples came from vine leaves that were not included to the training set. Support Vector Machine training was accomplished, as mentioned above, with 7 samples that all came from vine cultivations' leaves. This fact alone indicates the high generalization capability of the model, demonstrated and validated through the efficient performance on different vine leaf images that were gathered under varying conditions. The most significant advantage of this method does not only regard the application of One Class Classifiers, but also the highly effective way of discerning between infected leaves and image background. This property derives from the application of the Gaussian mixtures based segmentation method, remarkably effective for isolating image areas of sharp variation in color.

The effectiveness of the presented application is a result of the sharp color variation that occurs at infected leaves, in comparison with healthy ones, thus an immediate differentiation is possible. In cases with a complex background, GrabCut algorithm can be trained to recognize a certain foreground not corresponding to the central area of the image. This ability was not required for use in this application, but can be optionally activated according to the criterion of right choice of each infected leaf in examination.

Conclusions

In the current paper an effective combination of pre-processing stages and One Class Classifiers applied on complex natural scenes is presented. The main aim of the presented research was to discover early stages of infections in vine leaves in order to enable faster and more effective prevention of vine epidemics that threaten food supply and quality. Four One Class Support Vector Machines (OCSVMs) were trained with a training set of 8 pictures from each disease including healthy, Powdery Mildew and Black Rot and Downy Mildew. The trained OCSVMs were tested with 100 infected vine leaf pictures corresponding to each disease. The recognition percentage reached 97%, 95% and 93% for each disease respectively while healthy plants were recognized with an accuracy rate of 100%.

Fig. 1 .Fig. 2 .

 12 Fig. 1. The original image of a vine leaf that has been fed to the model of pow-deryHSV Fig. 2. Segmentation of vine leaf by using the GrabCut algorithm on the original image.

Fig. 3 .

 3 Fig. 3. H-plane of the vine leaf after the background of the initial image has been removed.

Fig. 4 .

 4 Fig. 4. The corresponding LBP image of the vine leaf.

  The most performing was the Hue channel LBP histogram as the results showed in the recognition of diseased plants against healthy plants. The image of the Hue channel is shown in Fig.4. By applying the LBP transformation on the Hue image the textural features corresponding to contrast and hue change are exploited by labelling neighboring pictures according to the LBP algorithm explained above. The LBP image obtained from this process can be shown in Fig.5. The histogram of the LBP image is constructed according to the frequency of the occurrence of similar values between 0 and 255, a low length histogram containing 32 bins, has been used to partition the range of 255, so as to more rough features instead of local high resolution features which might demonstrate high variability.

Fig. 5 .

 5 Fig. 5. The segmented image has been used to obtain the HSV planes. Here, the Hue plane is shown.

Fig. 6 .

 6 Fig. 6. The corresponding LBP image of the vine leaf.

Fig. 7 .

 7 Fig. 7. Conflict resolution takes place and the image is labelled correctly as infected with powdery mildew.

Fig. 8 .

 8 Fig. 8. Vine leaf image without conflict resolution is classified correctly as Black Rot infected.

Acknowledgements

The presented study has been funded by PPP-FI /FRACTALS project.


Everton Alvares Cherman
email: echerman@icmc.usp.br

Grigorios Tsoumakas

Maria-Carolina C Monard
email: mcmonard@icmc.usp.br

Active Learning Algorithms for Multi-label Data

Keywords: Supervised learning, multi-label learning, active learning, pool-based strategies

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Different approaches to enhance supervised learning have been proposed over the years. As supervised learning algorithms build classifiers based on labeled training examples, several of these approaches aim to reduce the amount of time and effort needed to obtain labeled data for training. Active learning is one of these approaches [START_REF] Settles | Active learning literature survey[END_REF]. The key idea of active learning is to minimize labeling costs by allowing the learner to query for the labels of the most informative unlabeled data instances. These queries are posed to an oracle, e.g. a human annotator, which understands the nature of the problem. This way, an active learner can substantially reduce the number of labeled data required to construct the classifier.

Active learning has been developed substantially to support single-label learning, where each object (instance) in the dataset is associated with only one class label. However, this is not the case in multi-label learning, where each object is associated with a subset of labels. Due to the large number of real-world problems which fall into this category, and the interesting challenges that it poses, multi-label learning has attracted great interest in the last decade [START_REF] Tsoumakas | Introduction to the special issue on learning from multi-label data[END_REF].

We here focus on the pool-based active learning scenario [START_REF] Settles | Active learning literature survey[END_REF], where a pool of unlabeled data is available to the learning algorithm. The first contribution of this paper is the presentation of the key issues that have to be considered when applying active learning on (multi-label) data, as well as the particular decisions of existing algorithms in the literature with respect to these issues (Section 2). We implemented existing algorithms in a common framework within the Mulan library [START_REF] Tsoumakas | Mulan: A java library for multi-label learning[END_REF] and empirically investigated their performance on two multi-label data sets with different properties and under two different application settings (transductive, inductive). The second contribution of this paper is the presentation of these experimental results, where novel and interesting conclusions are drawn with respect to the factors that affect the performance of the different algorithms (Section 3).

Active Learning from Multi-label Data

There are a number of issues that need to be considered when attempting to apply active learning on multi-label data. In the following sections we focus on the most important ones.

Manual annotation approaches and effort

Similarly to a single-label active learning system, a multi-label active learning system can request the annotation of one or more objects. If the request is for just one object, then the annotator will observe (look at, read, hear, watch) the object in an attempt to understand it and characterize it as relevant or not to each of the labels. In practice, requests are made for a batch of objects. For example, ground truth acquisition for the ImageCLEF 2011 photo annotation and concept-based retrieval tasks was achieved via crowd-sourcing in batches of 10 and 24 images [START_REF] Nowak | The clef 2011 photo annotation and conceptbased retrieval tasks[END_REF]. In such cases, there are two ways that an annotator can accomplish the task:

1. object-wise, where for each object the annotator determines the relevancy to each label; and 2. label-wise, where for each label the annotator determines relevancy to each object3 .

Consider a request for the annotation of n objects with q labels. Let c o be the average cost of understanding an object, c l be the average cost of understanding a label and c lo be the average cost of deciding whether an object should be annotated with a particular label or not. If we set aside the cognitive and psychological aspects of the annotation process, such as our short-term memory capacity, then a rough estimation of the total cost of object-wise annotation is:

n[c o + q(c l + c lo )] = nc o + nqc l + nqc lo
Similarly, a rough estimation of the total cost of label-wise annotation is:

q[c l + n(c o + c lo )] = qc l + nqc o + nqc lo
Assuming that the cost of label-wise annotation is smaller than that of objectwise annotation, we have:

qc l + nqc o + nqc lo < nc o + nqc l + nqc lo qc l + nqc o < nc o + nqc l n(q -1)c o < q(n -1)c l c o < q(n-1)
n(q-1) c l ≈ qn nq c l = c l This means that choosing the annotation approach, largely depends on the object and label understanding costs. If object (label) understanding is larger, then the object (label) wise approach should be followed.

As Figure 1 illustrates, object understanding is less costly than label understanding only for images, which humans understand in milliseconds. Documents, audio and video require far more time to understand than typical label concepts.

Costs of understanding

Label cost = object/label wise boundary

Fig. 1. The cost of understanding a label in different types of data.

Full and partial annotation requests

In a classical supervised learning task, the active learning system requests the value of the target variable for one or more objects. What can the learning system request in multi-label learning?

Normally it should request the values of all binary target variables (labels) for one or more objects. Then a (batch) incremental multi-label learning algorithm can update the current model based on the new examples. A different approach is taken in [START_REF] Qi | Two-Dimensional Multilabel Active Learning with an Efficient Online Adaptation Model for Image Classification[END_REF], where the system requests the values for only a subset of the labels and subsequently infers the values of the remaining labels based on label correlations.

Sticking to the values of just a subset of the labels would require an algorithm that is incremental in terms of partial training examples. Binary relevance (BR) is perhaps the sole algorithm fulfilling this requirement, but it is a standard and often strong baseline. Therefore, the development of active learning strategies that request partial labeling of objects could be a worthwhile endeavor. However, there is an implication on annotation effort that has to be considered. If the system requests the labeling of the same object at two different annotation requests, then the cost of understanding this object would be incurred twice. As discussed in Section 2.1, this is inefficient for most data types.

Evaluation of unlabelled instances

The key aspect in a single-label active learning algorithm is the way it evaluates the informativeness of unlabelled instances. In multi-label data, the evaluation function (query) of active learning algorithms comprises two important parts:

1. a scoring function to evaluate object-label pairs; and 2. an aggregating function to aggregate these scores.

Algorithm 1 shows the general procedure for a batch-size = t, i.e., t examples are annotated in each round. The evaluation function query calculates the evidence value of each example E i ⊂ D u and returns the t most informative instances, according to the evidence value used. In each round, these t examples will be labeled by the oracle and included in the set D l of labeled examples.

input : D l : labeled pool; Du: unlabeled pool; Ei: multi-label example;

L: set of labels; Yi: subset of labels associated to Ei; t: batch size; R: number of rounds; F : multi-label learner; Oracle: the annotator;

for r = 1, 2, .., R do H ← F (D l ) {Ei} t i=1 ← query(H, L, Du, t) {Yi} t i=1 ← Oracle({Ei} t i=1 ) D l ← D l ∪ {(Ei, Yi)} t i=1 Du ← Du -{Ei} t i=1 end
Algorithm 1: Multi-label active learning procedure for the object-wise annotation approach.

Algorithm 2 shows the query function of a multi-label active learning procedure. The scoring function considers object-label pairs (E i , y j ) and evaluates the participation (e i,j ) of label y j in object E i . It returns an evidence value e i,j for all instances E i ⊂ D u and for each label y j ∈ L = {y 1 , y 2 , ..., y q }. The aggregating function considers the q evidence values e i,1 , e i,2 , ..., e i,q of each instance E i given by the scoring function, and combines these values into a unique evidence value e i .

input : Du: unlabeled pool; L: set of labels; H: multi-label classifier output: The t instances with higher evidences for Ei ∈ Du do for yj ∈ L do ei,j ← scoring(Du, H, Ei, yj) end ei ← aggregating(ei,1, ei,2, ..., ei,q) end query ← best(e1, e2, ...., t, Du) Algorithm 2: The query function

The following three families of measures have been proposed in the related work for evaluating object-label pairs (scoring):

1. Confidence-based score [START_REF] Brinker | On active learning in multi-label classification[END_REF][START_REF] Esuli | Active learning strategies for multi-label text classification[END_REF][START_REF] Singh | Score Normalization and Aggregation for Active Learning in Multi-label Classification[END_REF]. The distance of the confidence of the prediction from the average value is used. The nature of this value depends on the bias of learner. It could be a margin-based value (distance from the hyper-plane), a probability-based value (distance from 0.5) or other. The value returned by this approach represents how far an example is from the boundary decision threshold between positive and negatives examples. We are interested in examples that minimize this score. 2. Ranking-based score [START_REF] Singh | Score Normalization and Aggregation for Active Learning in Multi-label Classification[END_REF]. This strategy works like a normalization approach for the values obtained from the confidence-based strategy. The confidences given by the classifier are used to rank the unlabeled examples for each label. We are interested in examples that maximize this score. 3. Disagreement-based score [START_REF] Hung | Multi-label active learning with auxiliary learner[END_REF][START_REF] Yang | Effective multi-label active learning for text classification[END_REF]. Unlike the other approaches, this strategy uses two base classifiers and measures the difference between their predictions. We are interested in maximizing this score. The intuitive idea is to query the examples that most disagree in their classifications and could be most informative. Three ways to combine the confidence values output by the two base classifiers have been proposed: i. MMR uses a major classifier which outputs confidence values and an auxiliary classifier that outputs decisions (positive/negative). The auxiliary classifier is used to determine how conflicting the predictions are. ii. HLR considers a more strict disagreement using the decisions output by both classifiers to decide if there is disagreement or agreement between each label prediction of an example. iii. SHLR tries to make a balance between MMR and HLR through a function that defines the influence of each approach in the final score.

After having obtained the object-label scores, there are two main aggregation strategies for combining the object-label scores to an overall object score:

1. AVG averages the object-label scores across all labels. Thus, given the q object-label scores e i,j of object E i , the overall object-label score of object E i is given by:

e i = aggregating avg ({e i,j } q j=1 ) = q j=1 e i,j q
2. MIN/MAX, on the other hand, considers the optimal (minimum or maximum) of the object-label scores, given by:

e i = aggregating min/max ({e i,j } q j=1 ) = min/max({e i,j } q j=1 )
Note that for HLR, only the average aggregation strategy makes sense, as taking the maximum would lead to a value of 1 for almost all unlabeled instances and would not help in discriminating among them.

Experimental protocol

Besides the multi-label active learning strategies themselves, the way that they are evaluated is another important issue to consider. Some aspects to be considered are the size of the initial labeled pool, the batch's size, the set of examples used as testing, the sampling strategy and also the evaluation approach. Next, these aspects are described with reference to related work.

Regarding the initial labeled pool, different papers built it in different ways. In [START_REF] Singh | Score Normalization and Aggregation for Active Learning in Multi-label Classification[END_REF], the examples are chosen to have at least one example positive and one negative for each label. In [START_REF] Yang | Effective multi-label active learning for text classification[END_REF], 100 to 500 examples were selected randomly to compose the initial labeled pool. In [START_REF] Esuli | Active learning strategies for multi-label text classification[END_REF], the first 100 chronologically examples were selected. In [START_REF] Brinker | On active learning in multi-label classification[END_REF], the author choose randomly 10 examples to compose the initial labeled pool.

The batch size defines how many examples are queried in each round of active learning. In [START_REF] Singh | Score Normalization and Aggregation for Active Learning in Multi-label Classification[END_REF][START_REF] Brinker | On active learning in multi-label classification[END_REF], only one example was queried per round. In [START_REF] Esuli | Active learning strategies for multi-label text classification[END_REF] 50 examples were chosen in each round, while in [START_REF] Yang | Effective multi-label active learning for text classification[END_REF] experiments with both 50 and 20 examples were performed.

There are basically two different ways to define the test set. The first one is to consider a totally separated test set. This was followed in [START_REF] Esuli | Active learning strategies for multi-label text classification[END_REF] and though not explicitly mentioned, it seems to have also been followed in [START_REF] Brinker | On active learning in multi-label classification[END_REF]. The second way is to use the remaining examples in the unlabeled pool for testing. This approach was used in [START_REF] Singh | Score Normalization and Aggregation for Active Learning in Multi-label Classification[END_REF][START_REF] Yang | Effective multi-label active learning for text classification[END_REF].

It is worth noting that the quality of the model assessed using this second approach holds for examples in the unlabeled pool, and does not necessarily hold for new unlabeled data. Although there is a lack of discussion about this topic in the active learning literature, the decision of which evaluation approach to use depends on the application's nature. Most learning applications are interested in building a general model from a training set of examples to predict future new examples, e.g., this kind of application uses inductive inference algorithms to make its predictions. An experimental protocol using a separate test set is the correct evaluation approach for the performance assessment for the inductive inference setting. The remaining evaluation approach is biased by the active learner and hence the evaluation on these remaining examples will not be representative of the actual distribution of new unseen examples, which is the case for inductive inference.

However, there are active learning applications that want to predict labels of an a priori known specific set of examples. For example, in a real world personal image annotation scenario, the user would like to annotate some images of his/her collection and after few rounds of active learning, the system would annotate the remaining image in the collection [START_REF] Singh | Score Normalization and Aggregation for Active Learning in Multi-label Classification[END_REF]. For such an application, the learning assessment should use the remaining examples in the query pool.

The learning curve is the most common evaluation approach used to assess active learning techniques. A learning curve plots the evaluation measure considered as a function of the number of new instance queries that are labeled and added to D l . Thus, given the learning curves of two active learning algorithms, the algorithm which dominates the other for more or all the points along the learning curve is better than the other. Besides the learning curve, [7, 10, 2] also used the value of the evaluation measure in the end of some specific number of rounds to assess the active learning techniques.

Experiments

The active learning algorithms described in Section 2.3, as well as the active learning evaluation framework, were implemented using Mulan4 [START_REF] Tsoumakas | Mulan: A java library for multi-label learning[END_REF], a Java package for multi-label learning based on Weka5 . Our implementation is publicly available to the community at http://www.labic.icmc.usp.br/pub/mcmonard/ Implementations/Multilabel/active-learning.zip.

Setup

The experiments were performed using the datasets Scene and Yeast, two classic multi-label datasets, which can be found in the Mulan website 6 . Scene dataset addresses the problem of semantic image categorization. Each instance in this dataset is an image associated with some of the six available semantic classes (beach, sunset, fall foliage, eld, mountain, and urban). Yeast is a biological dataset for gene function classification. Each instance is a yeast gene described by the concatenation of micro-array expression data and phylogenetic prole associated with one or more different functional classes.

Table 1 describes the datasets, where CL (cardinality) and DL (density) are defined as 6), few different multi-labels (15) and low cardinality (1.074). On the other hand, Yeast dataset has 14 labels, 198 different multi-labels, and a reasonably high cardinality (4.237). This means that instances in the Yeast dataset have more complex label space than the instances in the Scene dataset. Thus, learning from the Yeast dataset would be more difficult than learning from the Scene dataset.

CL(D) = 1 |D| |D| i=1 |Y i | and DL(D) = 1 |D| |D| i=1 |Yi| q , respectively.
Information related to label frequency is also important to characterize multilabel datasets. To this end, Table 1 also shows summary statistics related to labels frequency, where (Min) Minimum, (1Q) 1 st Quartile, (Med) Median, (3Q) 3 rd Quartile and (Max) Maximum. Recall that 1Q, Med and 3Q divide the sorted labels frequency into four equal parts, each one with 25% of the data. Note that Yeast dataset in unbalanced.

Figure 2 shows a graphic distribution of the datasets label frequency using the Violin plot representation, which adds the information available from local density estimates to the basic summary statistics inherent in box plots. Note that the Violin plot may be viewed as boxplots whose boxes have been curved to reflect the estimated distribution of values over the observed data range. Moreover, observe that the boxplot is the black box in the middle, the white dot is the median and the black vertical lines are the whiskers, which indicate variability outside the upper and lower quartiles. As mentioned in Section 2.3, the active learning algorithms implemented in this work are combinations of functions to evaluate object-label pairs and to aggregate these scores. The functions to evaluate the object-label pairs, i.e., the scoring function, are: Confidence-based (CONF), Ranking-based (RANK), HLR Disagreement-based (HLR), MMR Disagreement-based (MMR), SHLR Disagreement-based (SHLR). The functions to aggregate the outputted scores, i.e., the aggregating function, are: average (AVG) and maximum or minimum (MAX/MIN), depending on the score function.

In this work, the initial labeled pool of examples was built by randomly choosing examples until having N ini × q positive single labels, i.e.. until

N ini × q ≥ |D l | i=1 Y i ,
where N ini is user-defined. This strategy allows for fairer comparison across the datasets. N ini = 5, 10, 20 was used in order to evaluate the influence of different sizes of the initial labeled pool. The general procedure -Algorithm 1 -was executed with a batch size t = 1, i.e., one example is annotated in each run. The Binary Relevance approach was used as the multi-label classifier, using stochastic gradient descent with hinge loss as the base classifier. For the disagreement-based approaches, we used the sequential minimal optimization algorithm with a linear kernel. Both learners, are implemented in the Weka framework, and are named SGD and SMO respectively.

Results and Discussion

We report results in terms of the micro F 1 measure, and in particular its average over 1500 iterations of active selection of one example in each iteration. This is proportional to the area under the corresponding learning curve of the different algorithms. Figure 3 presents the results. Bold typeface is used to highlight the relative best performance of the different scoring functions and aggregation strategies for each particular experimental setting (dataset and protocol pair). All results were obtained using 10-folds cross-validation. The full experimental results are available online as supplementary material 7 .

Scene

Yeast Remaining Separated Remaining Separated AVG MAX AVG MAX AVG MAX AVG MAX Confidence 0,6478 0,6274 0,5867 0,5918 0,6100 0,5556 0,5557 0,5415 Rank 0,6377 0,6376 0,6024 0,6029 0,5790 0,5907 0,5670 0,5689 MMR 0,6979 0,6562 0,6038 0,5961 0,5878 0,5586 0,5622 0,5534 HLR 0,6885 0,5999 0,6248 0,5705 SHLR 0,6815 0,6617 0,5960 0,5970 0,5900 0,5571 0,5609 0,5583 Random 0,5928 0,5916 0,5589 0,5602 The first question we want to answer is how does the size of the initial pool of training examples affect the performance of the methods? Here we noticed the same strange general pattern across both data sets and application settings and across all algorithms: Having 5 and 20 examples per label leads to similar performance, which is slightly better compared to having 10 examples per label. In the rest of the experiments we removed this factor by considering the average results of the three different sizes of the initial pool.

The next question we want to answer is which aggregation strategy works best for each scoring function and under what conditions? For the confidence-based score function, in the separated protocol min is best aggregation strategy in both yeast and scene, while for the remaining protocol, avg works best in both yeast and scene. Taking the min of the confidence-based score stresses more the labels for which the classifier is most uncertain (e.g. rare labels that it has not seen yet), while avg treats all labels equally. We hypothesize that in the remaining protocol instances with rare (difficult to be predict) labels are removed from the test set and hence stressing the performance in such labels is meaningless. In contrast, in the separate protocol, rare labels in the test set remain rare and important. Figure 4 shows the learning curves of min and avg in scene for the remaining protocol. It confirms our hypothesis, as in the initial steps, avg does not perform as well as min, but as more and more rare labels are being removed from the test set, it eventually does better. This is an important conclusion for researchers developing methods for a particular protocol, or practitioners applying methods in a particular protocol setting. For the rank-based score function, in the scene data set, max and avg work equally well for both the remaining/separate protocols, while in the yeast database max gives slightly better results. The rank-based score function normalizes the absolute values of uncertainty across the labels and hence makes itself all labels equal in this sense. This alleviates the issue we discussed above. We hypothesize that the aforementioned difference between yeast and scene is due to the corresponding differences in label frequencies, as shown in Figure 2. The max aggregation pays more attention to labels where the relative uncertainty with respect to other labels is higher, and this pays-off better, in accordance with the theory of active learning. In scene, as there are fewer labels with similar distributions, it makes no difference in focusing on all labels or only on the most uncertain one.

In terms of the disagreement-based score functions, in MMR avg works better than max for both data sets and protocols, while for SHLR, avg works better than max in the remaining setting, while they perform similarly in the separate setting. Here, we would expect similar results with confidence-based scoring and indeed we see that avg does better than max in the remaining setting. However, in contrast with confidence-based scoring, here avg dominates also in the separate protocol. It seems that while uncertainty is maximized in the case of rare labels, the same does not happen for the disagreement between the two classifiers. We hypothesize that this occurs because with limited training data for rare labels both classifiers' output is similarly uncertain. We also argue that the disagreement of classifiers per label, again in itself, brings all labels to the same measurement level (normalization). This also explains the good results of the average strategy.

The next question we want to answer is which scoring function works best and under what conditions? Comparing the different scoring functions with each other, we notice that the disagreement-based functions do best overall, with MMR giving the best results in scene and HLR the best results in yeast for both protocols. HLR is the most robust method, delivering near-top results also in scene. Recall that HLR takes into account crisp decisions instead of confidences. This shows that looking at actual confidence values can be misleading, particularly in the presence of rare labels and imbalanced distributions across the labels. In scene, where labels are similar in frequency, MMR did best, hence in these -rare in practice -cases, we expect actual confidences to offer benefits.

Further interesting results are obtained by comparing random selection of unlabeled instances (passive learning) with the active learning approaches. In particular, we notice that large gains are achieved in the transductive setting, while active learning methods are struggling to beat passive learning in the separated setting. This shows that in the remaining setting, the benefits of active learning are coming mostly from the removal of difficult instances from the test set rather than from the incorporation of useful instances to the training set, an interesting conclusion for active learning in general (non multi-label) that to the best of our knowledge has not been previously discussed in the literature.

Summary and Future Work

Although active learning in single-label learning has been investigated over several decades, this is not the case for multi-label learning. This work discussed key issues in pool-based (multi-label) active learning based on existing algorithms in the literature, which were implemented in a common framework and experimen-tally evaluated in two multi-label data sets with different properties and under two different application settings (transductive, inductive).

Results show that taking the average across all labels of disagreement-based scoring functions perform best, and that in particular the MMR function works better in the absence of imbalance among the labels, while HLR works better in the presence of such imbalance. Moreover, the transductive setting was found to be easier for active learning due to the removal of difficult examples.

In the future, we plan to expand our empirical study with more data sets, in order to assess the generality of our conclusions.

Fig. 2 .

 2 Fig. 2. Violin plots of label frequencies distribution.

Fig. 3 .

 3 Fig. 3. Experimental results.

4 .

 4 Average vs minimum in scene for the confidence-based score function.

Table 1 .

 1 Datasets description and label frequency statistics These two datasets have different properties. Although both datasets have similar number of examples, Scene dataset has low number of labels (

	Dataset domain #ex #feat q CL DL #dist Min 1Q Med 3Q Max
	Scene	image 2407 294 6 1.074 0.179 15	364 404 429 432 533
	Yeast biology 2417 103 14 4.237 0.303 198	34 324 659 953 1816

Object-wise and label-wise annotation have been called global and local labeling respectively in[START_REF] Esuli | Active learning strategies for multi-label text classification[END_REF]

http://mulan.sourceforge.net

http://www.cs.waikato.ac.nz/ml/weka

http://mulan.sourceforge.net/datasets.html

http://www.labic.icmc.usp.br/pub/mcmonard/ExperimentalResults/ AIAI2016-ALLRESULTS.xls

Acknowledgment

This research was supported by the São Paulo Research Foundation (FAPESP), grants 2010/15992-0 and 2011/21723-5, and Brazilian National Council for Scientific and Technological Development (CNPq), grant 644963.


J Sánchez-González

J Pérez-Romero

R Agustí

O Sallent
email: sallent@tsc.upc.edu

On Learning Mobility Patterns in Cellular Networks

Keywords: Clustering, Cellular Networks, Mobility patterns. 1

This paper considers the use of clustering techniques to learn the mobility patterns existing in a cellular network. These patterns are materialized in a database of prototype trajectories obtained after having observed multiple trajectories of mobile users. Both K-means and Self-Organizing Maps (SOM) techniques are assessed. Different applicability areas in the context of Self-Organizing Networks (SON) for 5G are discussed and, in particular, a methodology is proposed for predicting the trajectory of a mobile user.

Introduction

The new generation of mobile and wireless systems, known as 5th Generation (5G), intends to provide solutions to the continuously increasing demand for mobile broadband services associated with the massive penetration of wireless equipment while at the same time supporting new use cases associated to customers of new market segments and vertical industries (e.g., e-health, automotive, energy). As a result, the vision of the future 5G Radio Access Network (RAN) corresponds to a highly heterogeneous network with unprecedented requirements in terms of capacity, latency or data rates, as identified in different fora [START_REF]METIS 2020 project[END_REF] [START_REF] Hattachi | NGMN 5G White Paper[END_REF]. To cope with this heterogeneity and complexity, the RAN planning and optimization processes can benefit at a large extent from exploiting cognitive capabilities that embrace knowledge and intelligence.

In this direction, legacy systems already started the automation in the planning and optimization processes through Self-Organizing Network (SON) functionalities [START_REF] Ramiro | Self-Organizing Networks. Self-planning, self-optimization selfhealing for GSM, UMTS and LTE[END_REF]. In 5G, considering also the advent of big data technologies [START_REF] Liu | On Big Data Analytics for Greener and Softer RAN[END_REF], it is envisioned that SON can be further evolved towards a more proactive approach able to exploit the huge amount of data available by a Mobile Network Operator (MNO) and to incorporate additional dimensions coming from the characterization of end-user experience and end-user behavior [START_REF] Imran | Challenges in 5G: How to Empower SON with Big Data for Enabling 5G[END_REF]. Then, SON can be enhanced through Artificial Intelligence (AI)-based tools, able to smartly process input data from the environment and come up with knowledge that can be formalized in terms of models and/or structured metrics that represent the network behavior. This will allow gaining in-depth and detailed knowledge about the whole 5G ecosystem, understanding hidden patterns, data structures and relationships, and using them for a more efficient network management [START_REF] Pérez-Romero | Artificial Intelligence-based 5G Network Capacity Planning and Operation[END_REF]. AI-based SON involves three main stages [START_REF] Pérez-Romero | Artificial Intelligence-based 5G Network Capacity Planning and Operation[END_REF]: (i) the acquisition and preprocessing of input data exploiting the wide variety of available data sources; (ii) the knowledge discovery that smartly processes the input data to come up with exploitable knowledge models that represent the network/user behavior; and (iii) the knowledge exploitation stage that applies the obtained models to drive the decisionmaking of the SON functions. This paper focuses on the knowledge discovery stage and, in particular, on automatically learning the mobility patterns of the mobile users, trying to identify if the traffic across the cells in a scenario follows specific patterns that can be characterized in terms of prototype trajectories followed by many users.

Different works of the literature have addressed the analysis of trajectories in different contexts such as hurricane trajectories, animal movements, public transportation, etc. Various tools have been considered, such as Self-Organizing Maps (SOM) together with visual analysis [7], density-based clustering [8][9] or Principal Component Analysis [START_REF] Masciari | A Complete Framework for Clustering Trajectories[END_REF]. In wireless networks, [START_REF] Lee | Data Stashing: Energy-efficient Information Delivery to Mobile Sinks through Trajectory Prediction[END_REF] proposed a trajectory prediction strategy to deal with routing in mesh sensor networks. It is based on clustering similar trajectories followed by wireless nodes and using them for making predictions of other nodes. However, the concept of trajectory in [START_REF] Lee | Data Stashing: Energy-efficient Information Delivery to Mobile Sinks through Trajectory Prediction[END_REF] is defined by the set of nodes that a mobile node would associate with to send or receive data along a path, but not by the geographical locations. Instead, in our work we intend to derive a deeper knowledge about trajectories based on analyzing the geographical coordinates. In turn, [START_REF] Sas | Classifying Users based on their Mobility Behavior in LTE networks[END_REF] and [START_REF] Sas | A SON function for Steering Users in Multi-Layer LTE Networks based on their mobility behavior[END_REF] address the problem of classifying the trajectory followed by a mobile terminal based on a set of reference trajectories in order to optimize the handover process in LTE. However, while [START_REF] Sas | Classifying Users based on their Mobility Behavior in LTE networks[END_REF] and [START_REF] Sas | A SON function for Steering Users in Multi-Layer LTE Networks based on their mobility behavior[END_REF] use a simple method for building the set of reference trajectories, based on monitoring certain users with a given probability and adding their trajectories to the set, in our approach we propose the use of clustering techniques, which are more powerful for identifying the most representative trajectories.

In this context, the approach proposed in this paper considers the use of clustering techniques, namely K-means and SOM, to learn the mobility patterns existing in a cellular network. These patterns are materialized in a database of prototype trajectories obtained after having observed multiple trajectories of mobile users. Different applicability areas for these patterns in the context of 5G-SON are discussed and, in particular, a methodology is proposed for predicting the trajectory of a mobile user.

The rest of the paper is organized as follows. Section 2 describes the proposed methodology based on clustering tools for learning mobility patterns. Section 3 discusses the applicability areas and describes the approach for identifying the trajectory of a mobile user. Proposed approach is evaluated in Section 4, while Section 5 summarizes the concluding remarks.

Mobility pattern knowledge discovery

Current cellular networks like 4G already include the capability that the User Equipments (UEs) provide geolocation information, including both geographical coordinates and altitude, as part of the radio measurement reporting processes [14]. Location information can be obtained from UEs in connected mode, who periodically transmit measurement reports to the network. Furthermore, thanks to the use of Minimization of Drive Tests (MDT) feature [START_REF] Hapsari | Minimization of Drive Tests Solution in 3GPP[END_REF], UEs in idle mode can log measurements and transmit them later on when the UE enters in connected mode. These capabilities enable MNOs to collect large amounts of data that include valuable knowledge about the spatio-temporal traffic distribution across the cells. This paper proposes a methodology to analyze this data and identify the existing mobility patterns of the UEs.

The approach for learning mobility patterns is graphically illustrated in Fig. 1. It operates on a long-term basis after having observed a large amount of connected and idle mode UEs in different time periods of a certain geographical area and analyzes the collected location information from these UEs to identify the existence of prototype trajectories. As shown in Fig. 1 the first step is the pre-processing, which analyzes consecutive reports for each UE and extracts the geolocation information in order to build a trajectory for this UE. A trajectory is defined here as the concatenation of N coordinates at consecutive time instants t 1 ,...,t N . Then, assuming for simplicity twodimensional (2D) coordinates (x,y), the trajectory for the j-th UE is given by the vector of dimension B=2N denoted as r j =[x j (t 1 ),y j (t 1 ),…, x j (t N ),y j (t N )]. The result of the pre-processing task will be a total of J trajectories r j , j=1,...,J. The second step is the clustering, which processes the set of J trajectories by grouping them in K clusters in a way that trajectories of the same cluster are similar among them and different from the trajectories of the rest of the clusters. Two alternative clustering techniques are considered in this work:  K-means: This strategy belongs to the family of partitioning methods. It groups the J input trajectories in K clusters by trying to maximize that the similarity between trajectories of the same cluster and to minimize the similarity between trajectories of different clusters, using the Euclidean distance as a metric of similarity. The process can be summarized as follows (see [START_REF] Han | Data Mining Concepts and Techniques[END_REF] for further details): (a) The algorithm starts by selecting randomly K out of the J input trajectories. Each of these K trajectories represents an initial cluster. For each cluster k, the algorithm computes the centroid s k . At this initial stage, where each cluster contains only one trajectory, the centroid s k equals the selected trajectory for the k-th cluster. (b) Each of the remaining J-K trajectories is assigned to the cluster to which it is the most similar, based on Euclidean distance between the trajectory and the centroid of each cluster |r j -s k |. Once all the J trajectories have been clustered, the new values of the centroids s k are recomputed. In particular, the i-th component of s k is the average of the i-th components of all the trajectories belonging to the k-th cluster. (c) Using the new values of the centroids s k , each of the J trajectories r j is reassigned to the cluster with lowest distance |r j -s k |. The new centroids are recomputed and this step is iteratively repeated until convergence (i.e. until there are no changes in the obtained clusters after two consecutive iterations). (d) At the end of the process, each cluster k=1,...,K will contain a number of input trajectories N k and its centroid s k will be the so-called prototype trajectory that is taken as a representative of all the trajectories belonging to this cluster.  Self-Organizing Map (SOM): This clustering strategy relies on a neural network model with a total of K neurons and where each neuron is characterized by a Bdimensional weight vector s k . The process can be summarized as follows (see [START_REF] Kohonen | Essentials of the Self-Organizing Map[END_REF] for details): (a) The weight vectors s k are initialized. This can be done randomly or through the linear initialization method described in [START_REF] Kohonen | Essentials of the Self-Organizing Map[END_REF]. (b) An iterative unsupervised learning process is used to update the values of the weight vectors s k of the different neurons according to the Kohonen's algorithm [START_REF] Kohonen | Essentials of the Self-Organizing Map[END_REF] based on the input trajectories r j . In essence, at iteration t the algorithm identifies, for each trajectory r j the winning neuron as the one with the lowest Euclidean distance |r j -s k |. Then, the algorithm updates the weight vector of this winning neuron k as s k (t+1)=s k (t)+(t)(r j -s k (t)) where (t) is a scalar-valued adaptation gain that decreases with successive iterations. A similar update is performed for the weight vectors of the rest of neurons k'k but in this case the adaptation gain (t) is multiplied by a neighborhood function that decreases with the distance between neurons k' and k. The process is repeated for a certain number of iterations. (c) At the end of the process, all the input trajectories that have neuron k as winning neuron form the k-th cluster. The number of trajectories in the k-th cluster is N k , and the prototype trajectory of this cluster is the weight vector s k .

As shown in Fig. 1, the prototype trajectories obtained as a result of the clustering will be stored in the database. In addition, two statistical indicators are also included for each cluster to assess how representative this cluster is:

 Percentage of hits (A k =N k /J): It is the percentage of input trajectories that belong to the cluster k. The prototype trajectories of clusters with a high value of A k will be more frequent and representative of the scenario.  Average squared Euclidean distance of the trajectories in k-th cluster (E k ): It is a metric that captures the degree of similarity between trajectories of the same cluster with respect to the prototype trajectory s k of the cluster. A high value of E k reflects a higher dispersion in the cluster, meaning that the prototype trajectory is less representative of the clustered trajectories. It is defined as:

2 Cluster k k j E     j k r s ( 1 )

Exploitation of mobility patterns

It is envisaged that the identification of prototype trajectories as explained in previous section can have applicability for different 5G-SON functions.

For example, prototype trajectories can be used in the context of self-planning to decide appropriate cell locations and antenna settings. For example, if there is a well identified representative trajectory, a sector of a cell site can be pointed in the direction of this trajectory. Typically, this can be the case of a cell site providing coverage over a main street. Despite one could argue that a radio engineer could easily identify such a situation and take such a common sense decision, the interest of the proposed use case remains in the fact that SON involves automatization. That is, self-planning and self-configuration means the capability for the system to automatically identify the trajectories and propose the adequate values for the parameters of a new cell.

Similarly, the learnt mobility patterns can also have applicability in the selfoptimization of several functions such as handover, load balancing or admission control. For example, by identifying the trajectory of a UE or group of UEs in relation to a known prototype trajectory it is possible to anticipate the cell that the UEs are heading to and configure these functions so as to avoid call droppings and overload situations. In the following, we focus on proposing a methodology to predict the future positions of a certain UE based on analyzing the actual locations reported by the UE in relation to the learnt prototype trajectories.

Mobility prediction

The proposed approach is illustrated in Fig. 2 and is executed on an individual UE basis. The criterion to decide which specific UEs are analyzed is out of the scope of this paper and it will depend on the specific self-optimization function under consideration. For example, the optimization of load balancing may predict the trajectory of UEs that demand a high bit rate in order to anticipate the arrival of these UEs to a cell and take the appropriate actions to ensure there are sufficient resources for these UEs in the cell. Similarly, it is also possible to predict the trajectory of high priority UEs to ensure that they will not experience problems in handovers, etc.

The process of Fig. 2 starts from the measurement reports provided by the UE whose trajectory is being predicted. First, pre-processing stage is carried out to extract the geolocation information and build the trajectory u that is currently being observed for this UE. The trajectory u is a vector of dimension C=2M composed by the concatenation of M pairs of coordinates followed by the UE at consecutive time instants u=[x(t 1 ),y(t 1 ),…, x(t M ),y(t M )]. Without loss of generality, let us consider that the dimension of u is lower than the number of elements of the prototype trajectories s k (i.e. CB). This reflects that, in case that the UE was following a prototype trajectory, the actual location of the UE is somewhere within the prototype trajectory.

The mobility prediction process of Fig. 2 intends to determine the likelihood that the UE is following one of the learnt prototype trajectories. This is done by assessing the similarity between the trajectory u followed by the UE and the prototype trajectories s k according to the Euclidean distance. Given that CB, all the possible portions of C consecutive elements of the vectors s k (k=1,…,K) need to be considered when assessing this similarity. The α-th portion of s k is then defined as the vector [s k (1+α),…, s k (C+α)] with α=0,…,B-C, where s k (i) denotes the i-th component of s k .

Then, the squared Euclidean distance between the α-th portion of s k and trajectory u is computed as:

, ∑ with α=0,…,B-C (2)
Then, the similarity between u and s k is computed as the minimum Euclidean distance between u and the possible portions of the prototype trajectory s k , that is:

  , min k u k m d    (3)
A low value of m k indicates that the trajectory u is very similar to some portion of vector s k . Then, the likelihood L k that the UE is following the prototype trajectory s k is defined here as:

⁄ ∑ ⁄ ( 4 )
A high value of L k reflects that the UE is following a trajectory very similar to a portion of s k . Therefore, s k provides information about the positions that the UE may likely follow in the future.

Results

This section provides some results to illustrate the performance of the proposed approach. The considered scenario is shown in Fig. 3 and represents an urban area in the intersection between two main streets. The mobility of multiple UEs has been considered including a wide variety of situations as shown Fig 3a . For example, some UEs move straight along a street, others move straight and turn right, left or move back.

For each kind of trajectory, 100 realizations have been generated by considering UE trajectories that are not perfectly straight but they have lateral movements simulating e.g. cars changing the lane in the road. It is assumed that the distance between two consecutive positions of the trajectory is a random value (simulating that the user speed may be variable). Moreover, 100 realizations of users that move a short distance and stop at a particular position (represented by black arrows in Fig. 3a) have been also generated. Finally, a group of 100 static users (represented by black dots in Fig 3a) have also been placed randomly in each of the four corners of the scenario.

Cl

The reless netrajectories present applicability in different areas, such as self-planning and self-optimization. In this respect, the paper has proposed a strategy for predicting the mobility of specific users based on the obtained prototype trajectories. Results reflect that both K-means and SOM techniques are able to properly identify the different trajectories existing in the considered scenario.

Fig. 1 .

 1 Fig. 1. -Procedure for learning mobility patterns

Fig. 2 .

 2 Fig. 2. -Exploitation of learnt patterns for predicting the trajectory of a UE

Fig. 3 .

 3 Fig. 3. (

Fig. 5

 5 Fig. 5. (

Fig. 6

 6 Fig. 6. E

Acknowledgements. This work has been supported by the EU funded H2020 5G-PPP project SESAME under the grant agreement no 671596 and by the Spanish Research Council and FEDER funds under RAMSES grant (ref. TEC2013-41698-R).