Alex Mackay
email: amackay@uow.edu.au

Simon J Armitage

Elizabeth Niespolo

Warren Sharp

Mareike Stahlschmidt

Alexander F Blackwood

Kelsey Boyd

Brian M Chase

Susan E Lagle

Chester F Kaplan

Marika A Low

Naomi L Martisius

Patricia J Mcneill

Ian Moffat

Corey A O'driscoll

Rachel Rudd

Jayson Orton

Teresa E Steele

Environmental influences on human innovation and behavioural diversity in southern Africa 92-80 thousand years ago

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Archaeological evidence from the African Middle Stone Age (MSA, 400-40 ka) defines our understanding of human behavioural evolution in the critical window between the emergence of our species and our subsequent global spread. Yet evidence for cultural innovation-the appearance of novel items such as distinctive stone tools, engravings, ornaments, and implements made from organic materials-occurs unevenly through the MSA in both space and time. In southern Africa, evidence for innovation appears to concentrate in two successive cultural units referred to as the Still Bay and Howiesons Poort, dating approximately 77-59 ka [START_REF] Lombard | South African and Lesotho Stone Age sequence updated[END_REF][START_REF] Kandel | Increasing Behavioral Flexibility? An Integrative Macro-Scale Approach to Understanding the Middle Stone Age of Southern Africa[END_REF]. In the preceding periods of the MSA ('pre-Still Bay'), instances of cultural innovation tend to be temporally and geographically isolated [START_REF] Porraz | Experimentation as a driving force for innovation in the Pre-Still Bay from Southern Africa[END_REF]. In the subsequent MSA ('post-Howiesons Poort'), several innovations appear to be lost, including a tradition of producing engraved ostrich eggshell (OES) water flasks that previously extended across 600 km of diverse habitats from the southern Cape coast to the deserts of southern Namibia [START_REF] Texier | A Howiesons Poort tradition of engraving ostrich eggshell containers dated to 60,000 years ago at Diepkloof Rock Shelter, South Africa[END_REF][START_REF] Henshilwood | Klipdrift Shelter, southern Cape, South Africa: Preliminary Report on the Howiesons Poort layers[END_REF].

Explaining the complicated and apparently non-directional pattern of MSA cultural change is key to understanding controls on human behavioural evolution. Prominent explanations have included fluctuations in effective population size [START_REF] Powell | Late Pleistocene demography and the appearance of modern human behavior[END_REF], the advent of territorial defense associated with exploitation of dense and predictable resources [START_REF] Marean | The transition to foraging for dense and predictable resources and its impact on the evolution of modern humans[END_REF], and climatically driven phasing of cultural connectedness across the subcontinent [START_REF] Mackay | Coalescence and fragmentation in the late Pleistocene archaeology of southernmost Africa[END_REF]. A significant biogeographic skew in the available archaeological dataset, however, makes these explanations difficult to test. Southern Africa is an ecologically diverse region with complex climate dynamics, yet evidence for MSA cultural innovation derives disproportionately from the relatively humid southern Cape coastal fringe (Figure 1). The archaeology of the arid regions of the west coast and interior remains notably understudied [START_REF] Wilkins | Innovative Homo sapiens behaviours 105,000 years ago in a wetter Kalahari[END_REF][START_REF] Dewar | Preliminary results of excavations at Spitzkloof Rockshelter, Richtersveld, South Africa[END_REF]. This skew may act to exaggerate both the appearance of cultural homogeneity and the periodicity of innovation by excluding ecosystems that required different behavioural adaptations to enable occupation at different times. It also complicates our understanding of cultural transmission dynamics-of when and under what conditions behaviours were transferred across biogeographic boundaries-and thus of the interplay between population connectivity and the development and persistence of innovations.

Here we present new data from excavations at the site of Varsche Rivier 003 (VR003), located 44 km from the Atlantic coast in the Knersvlakte bioregion, southern Namaqualand (Figure 1). Falling within the modern Succulent Karoo Biome, the Knersvlakte currently receives ~175±30 mm of rainfall per year [START_REF] Cowling | Namaqualand: A Succulent Desert[END_REF][START_REF] Hijmans | Very high resolution interpolated climate surfaces for global land areas[END_REF], almost all during the austral winter, and is characterised by a limited groundcover of xeric-adapted succulent shrubs and endemic 'stone plants' [START_REF] Mucina | Succulent Karoo Biome. The vegetation of South Africa, Lesotho and Swaziland, Strelizia[END_REF]. While the MSA archaeology of the Succulent Karoo is largely unstudied, VR003 lies close to the modern limits of the Fynbos Biome. Characterised by evergreen shrubs and reeds, and closely related to winter rainfall regimes [START_REF] Rebelo | Fynbos Biome. The Vegetation of South Africa, Lesotho and Swaziland, Strelizia[END_REF], the Fynbos Biome's current distribution encompasses many of southern Africa's most prominent MSA sites [START_REF] Marean | Stone Age people in a changing South African Greater Cape Floristic Region. Fynbos: Ecology, Evolution, and Conservation of a Megadiverse Region[END_REF]. Edaphic controls mean the Succulent Karoo / Fynbos Biome boundary is unlikely to have shifted substantially through the late Pleistocene [START_REF] Mucina | Succulent Karoo Biome. The vegetation of South Africa, Lesotho and Swaziland, Strelizia[END_REF][START_REF] Carr | Mid to Late Quaternary Landscape and Environmental Dynamics in the Middle Stone Age of Southern South Africa[END_REF], though intensified winter rainfall may have supported periodic northward range expansion of some fynbos taxa [START_REF] Chase | Late Quaternary dynamics of southern Africa's winter rainfall zone[END_REF].

Still Bay and Howiesons Poort assemblages occur in the upper strata at VR003 [START_REF] Steele | Varsche Rivier 003: A Middle and Later Stone Age site with Still Bay and Howiesons Poort assemblages in southern Namaqualand, South Africa[END_REF]. Initial luminescence ages suggested that these occurrences were anomalously young; we redate the Howiesons Poort here to between 71.6-55.7 ka (SI Geochronology, Table S6), consistent with the majority of ages elsewhere, and supporting cultural linkages between VR003 and sites in the Fynbos during Marine Isotope Stage (MIS) 4. The character and cultural transmission dynamics of the MSA prior to the Still Bay in this region are, however, comparatively unknown. We thus focus on results from the deepest excavated layers at VR003, and their relationship to coeval MSA deposits elsewhere, to explore 1) evidence for innovative behaviours in this typically arid region, 2) the strength of cultural connectedness with sites to the south, and 3) relationships between innovation, cultural connectedness and environmental change.

Results

Site formation and chronology: VR003 is a north-facing rock shelter site in Neoproterozoic limestone of the Widouw Formation and located in the gorge wall of the Varsche River (Figure 1). Five excavation seasons since 2009 have focussed mainly on the upper slope deposits in front of the rock shelter (Main Area) and the accessible areas of the shelter itself (Shelter), linked by a narrow trench (Link Trench; Figure S1). The deep sounding in the Main Area excavation has attained a depth of 1.9 m below surface without encountering bedrock.

No subsurface Later Stone Age (LSA) material is preserved in the Main Area, and the entire deposit so far excavated can be assigned to the MSA. Still Bay and Howiesons Poort horizons occur in stratum I-04 near the top of the sequence (Figure S1) [START_REF] Steele | Varsche Rivier 003: A Middle and Later Stone Age site with Still Bay and Howiesons Poort assemblages in southern Namaqualand, South Africa[END_REF], underlain by extensive MSA (strata I-05 to I-09). Having previously described the material through to I-07 [START_REF] Steele | Varsche Rivier 003: A Middle and Later Stone Age site with Still Bay and Howiesons Poort assemblages in southern Namaqualand, South Africa[END_REF], we concentrate here on the deepest excavated pre-Still Bay deposits in the Main Area, comprising two archaeological horizons -I-08 and I-09 -referred to for the purposes of this paper as the Lower Deposits.

The sedimentary sequence in the Main Area is composed of slope deposits with fine grained colluvium and coarser grained debris flow (Figure 2; for more detail see SI Geoarchaeology, Figures S2-5). Deposition of non-archaeological clasts on the slope by debris flow and colluvial processes is indicated by a lack of sorting or orientation and the fine coating of some coarse grained materials, though the low incidence of soil aggregates (Figure 2, inset B) and the lack of rounded rocks from the plateau above the shelter suggests overall limited transport distances. The regular occurrence of microscopic lithic knapping debris, and the high incidence and broad size distribution of microscopic bones (Figure 2, inset A, B) are typical for occupation layers suggesting their initial deposition on the slope. The presence of gypsum in the deposits indicates an arid environment with high evaporation rates. Fabric analysis of elongated bone and stone objects (n=353) reveals a predominantly planar distribution, suggesting that archaeological materials in the Lower Deposits were discarded on the slope (Figure S6). Object dip does not deviate from the surface slope or the overlying strata, and orientation does not differ significantly from a uniform distribution (Rayleigh test, p = 0.0008). Similarly, the dip of the 12 identified lithic refit sets, mainly comprising sequential flake removals (n=9), generally follows the deposit slope (Figure S7). The Lower Deposits have been dated using single-grain luminescence (pIRIR) on feldspar, and by U-series dating on ostrich eggshell (OES) fragments (Figure 2). Potassium feldspar extracted from four sediment samples distributed from near the top of I-08 to the base of I-09 yielded stratigraphically consistent ages ranging from 80.8±4.6 ka (1σ, ±9.2 ka 2σ) to 89.9±5.0 ka (1σ, ±10.1 ka 2σ) (Table S7). U-series dating on three fragments of OES from lower I-08 and upper I-09 used a novel approach termed 230 Th/U burial dating [START_REF] Sharp | 230Th/U burial dating of ostrich eggshell[END_REF]. As OES fragments were not typically piece-plotted during excavations we used two samples from bucket aggregates that also yielded OES artefacts (VR003-9300, VR003-6612) (see below), and one well-preserved piece-plotted fragment (VR003-9085) (Figures S11-S15). OES fragment VR003-9300 yields a 230 Th/U burial age of 88.3 ±3.2 ka (2σ error). OES fragment VR003-9085 yields concordant sub-sample ages consistent with rapid U uptake, defining a mean age of 90.7 ±0.7 ka in good agreement with the age determined for VR003-9300.

VR003-6612 also yields concordant sub-sample ages, however, their mean age of 74.5 ±1.4 ka is significantly younger than ages obtained for the two other OES, though it is within error of the luminescence ages at 2σ. This may imply mixing either in the bucket aggregate from which the sample derived or via disturbance processes such as bioturbation (SI Geoarchaeology). A probability density function provides a combined age range for the Lower Deposits of 92-80 ka at 1σ (SI Geochronology).

Archaeology: Phytoliths were analysed from nine samples distributed across stratigraphic units from I-09 to I-03 (SI Phytolith analysis, Tables S9 & S10, Figure S17). Abundance varies between samples, with highest concentrations in the Lower Deposits corresponding with high proportions of Poaceae (grasses) relative to Restionaceae and non-graminoid (woody and shrubby) vegetation compared to overlying strata (Table S10). The ratio of C4 (warm growing season) to C3 (cool growing season) to grass phytoliths is low (<20.8), consistent with the region's winter rainfall regime. However, higher proportions of warm growing season C4 grasses in the Lower Deposits (18.7±3.4) compared with the overlying strata (6.7±2.3) suggest a decrease in summer rain after ~80 ka. The decline in C4 grasses-and grasses in general-is concurrent with a two-fold increase in Restionaceae and woody phytolith percentages. Combined these results are consistent with the marked increase in wind strength and upwelling along the west coast that began in MIS 5a (Figure 3) and the weakening of tropical systems in the southern continental interior under decreasing orbital eccentricity [START_REF] Chase | Press) South African speleothems reveal influence of high-and lowlatitude forcing over the last 113[END_REF]. These factors would have limited the incursion of summer rainfall systems in the region, resulting in increased rainfall seasonality [START_REF] Chase | Influence of tropical easterlies in southern Africa's winter rainfall zone during the Holocene[END_REF]. As Restionaceae is strongly linked to winter rainfall in the Cape, this may be further evidence for an overall shift toward a more dominant winter rainfall regime (see SI Phytoliths).

The preserved vertebrate sample of the Lower Deposits is small (NISP=524; SI Vertebrates, Table S11, which includes scientific names for the taxa mentioned below) and dominated by tortoises (n=352), most of which are angulate tortoises that feed on grasses, annual herbs, and succulents in sandy, coastal habitats and succulent scrublands [START_REF] Manning | Namaqualand[END_REF].

Bovids of all sizes are present, although only eland and grysbok/steenbok could be identified to taxon. Eland can tolerate a wide variety of habitats, including those with limited surface water, by consuming browse and grass [START_REF] Skinner | The Mammals of the Southern African Subregion[END_REF]. Steenbok are browsers that are adapted to open areas with some tall grass, bushes or scrub for shelter; grysbok may have extended this far north, but generally prefer denser cover [START_REF] Skinner | The Mammals of the Southern African Subregion[END_REF][START_REF] Skead | Historical Mammal Incidence in the Cape Province[END_REF]. Cape zebra was a grazer that would have consumed grasses in open areas [START_REF] Churcher | Distribution and history of the Cape zebra (Equus capensis) in the Quaternary of Africa[END_REF]. Consistent with the phytoliths, the faunal communities imply a relatively open, arid to semi-arid environment, offering graze and browse in diverse habitats. These taxa are also found higher in the sequence, along with springbok, wildebeest/hartebeest, and blue antelope, indicating that grasses persisted in the region; small sample sizes limit detailed comparisons.

In addition to mammals and reptiles, the Lower Deposits preserve 26 shellfish fragments.

Limpets account for 77% of these, with granite limpets the dominant taxon, along with two black mussel fragments (SI Molluscs; Table S12, which includes scientific names). Other than a few isolated overlying examples, the majority of all marine shells at VR003 cluster in a band in the Lower Deposits (Figure 2). Given the luminescence and U-series results, relative sea level during the formation of the Lower Deposits would have been 25-40 m below present [START_REF] Spratt | A Late Pleistocene sea level stack[END_REF], though due to off-shore topography this would not have substantially increased VR003's distance to shore [START_REF] Wet | Bathymetry of the South African Continental Shelf[END_REF]. The molluscs were thus likely obtained at least 45-50 km from site. While limpets and mussels appear as an important food resource in other South African coastal MSA assemblages [START_REF] Jerardino | Shellfish gathering, marine paleoecology and modern human behavior: perspectives from cave PP13B, Pinnacle Point, South Africa[END_REF], they are rarely transported as food packages beyond 10 km [START_REF] Marean | Pinnacle Point Cave 13B (Western Cape Province, South Africa) in context: The Cape Floral kingdom, shellfish, and modern human origins[END_REF], raising questions about whether the VR003 individuals were transported as food or as empty shells. The shells from the Lower Deposits are fragmented, but no ochre residues nor anthropogenic modifications were observed on them.

OES is abundant at VR003, consisting mainly of unworked fragments, most of which appear to have been heated (SI Ostrich eggshell, Table S9). Surface preservation is typically poor, and engraved OES is limited to one piece with parallel striations from a Howiesons Poort context in the Link Trench (Figure S1). From approximately halfway through the Lower Deposits, however, we recovered 21 flaked OES fragments (Figures 2 &4; SI Ostrich eggshell, Table S14). All pieces show flaking in the form of precise percussive initiations that were truncated when the piece broke. Typically three or more initiations were used to form an arc consistent with a circular aperture of approximately 23.6 mm (±6.1 mm) that likely reflect circular perforations initially made on whole OES (Table S14). Such perforations are consistent in size, if not form, with laterally perforated ostrich eggshell flasks from the Holocene [START_REF] Kandel | Modification of ostrich eggs by carnivores and its bearing on the interpretation of archaeological and paleontological find[END_REF]. Pieces with only one or two initiations may reflect the early stages of this perforation process (SI Ostrich eggshell).

Main Area excavations have produced 27 772 flaked stone artefacts; 3062 of these were recovered from the Lower Deposits (SI Lithics) in addition to a small sample of pigments (SI Pigments). Distinctive artefact markers for the Still Bay and Howiesons Poort are limited to the upper strata, mainly I-04 (Figure S1). Quartz accounts for 60.0% of all artefacts from I-07 to I-03 (range: 54.2-65.4%), and silcrete for 10.9% (range: 7.2-16.1%) [START_REF] Steele | Varsche Rivier 003: A Middle and Later Stone Age site with Still Bay and Howiesons Poort assemblages in southern Namaqualand, South Africa[END_REF]. In the Lower Deposits the proportion of quartz (29.8%) halves while silcrete (41.6%) becomes the dominant raw material for the only time in the sequence (Table S16). This change is most evident in the distribution of silcrete cores (Figure 2) which account for 61.5% of cores in the Lower Deposits.

These silcrete cores are small (max dimension mean=43.7±10.2 mm), typologically diverse (Table S22), and exclusively produced small flakes and blades (scar length mean=17.4±6.9 mm). Cores with prepared platforms and no obvious management of the flaking surface are the most common identifiable type, though opportunistic and minimally worked cores account for about a quarter of the total. The average number of flake scars on silcrete cores is 3.1, suggesting generally short reduction chains. Blade removals are not numerous but are concentrated on some cores (Figure 5, Figure S24), and with an average scar length of 15.2 mm could be classified as bladelets. Blade production, however, generally seems to have been opportunistic (SI Lithics, Tables S17 &S18).

Heat shatter is unusually common in the Lower Deposits at VR003 (SI Lithics, Table S24, Figure S22), accounting for 24.2% of all silcrete artefacts (Tables S16); 62.3% of silcrete cores were made on such heat shattered fragments. Among those cores the mean scar count is only 2.3. Thus, the majority of silcrete cores in the Lower Deposits result from heat shattering of unworked pieces that were retrieved and used to produce a limited number of small flaking products prior to discard (Figure 5). Given the short reduction chains it is less likely that heat was used to improve the flaking characteristics of the rock than as an expedient means of creating small, angular core blanks.

Discussion

Geoarchaeological work combined with refit analysis suggests that strata I-08 and I-09 at VR003 are intact slope deposits, and two different geochronometric techniques produce largely concordant ages suggesting accumulation within the interval ~92-80 ka. Phytolith assemblages in these Lower Deposits indicate higher proportions of summer rain and limited fynbos taxa, giving way to an increasingly dominant winter rainfall regime across the MIS 5/4 transition. Corresponding with these environmental changes, the archaeological assemblages in the Lower Deposits are distinctive both from those overlying them, but also from documented MSA assemblages elsewhere in southern Africa.

Though it is not possible to confirm that the flaked OES pieces are fragments of flasks, no comparable flaked OES artefacts have been reported from other MSA assemblages with large samples of OES (e.g., [START_REF] Wilkins | Innovative Homo sapiens behaviours 105,000 years ago in a wetter Kalahari[END_REF][START_REF] Steele | The Middle and Later Stone Age faunal remains from Diepkloof Rock Shelter, Western Cape, South Africa[END_REF][START_REF] Klein | The Ysterfontein 1 Middle Stone Age site, South Africa, and early human exploitation of coastal resources[END_REF]). Potential OES flasks occur in the Howiesons Poort at Apollo 11 [START_REF] Vogelsang | New Excavations of Middle Stone Age Deposits at Apollo 11 Rockshelter, Namibia: Stratigraphy, Archaeology, Chronology and Past Environments[END_REF] and Diepkloof (4), but have not been reported from pre-Howiesons Poort contexts. The flask apertures at Diepkloof are also ground rather than flaked, consistent with LSA flasks. Thus, if the flaked OES from VR003 were flasks they were produced differently to other flasks from either MSA or LSA, and if they were not flasks then they reflect some other novel behaviour. In either case, use of OES as a raw material for artefact manufacture appears to be quite deep-rooted in the MSA.

Evidence for exploitation of edible shellfish species (e.g. limpets and mussels) occurs along the southern Cape coast as early as 164 ka [START_REF] Marean | Early human use of marine resources and pigment in South Africa during the Middle Pleistocene[END_REF]; however transport of such species over interior southern Namaqualand during MIS 5b. Long-distance transportation of a small sample of shellfish during the MSA has been noted from Apollo 11 and Pockenbank, which are ~140 km and ~120 km from the modern coast respectively [START_REF] Schmidt | New investigations at the Middle Stone Age site of Pockenbank Rockshelter, Namibia[END_REF][START_REF] Vogelsang | Middle Stone Age Fundstellen in Südwest-Namibia[END_REF]; they are both located in southern Namibia, suggesting that this behaviour may have been widespread through arid regions of southern Africa. Elsewhere limited transport of marine shell over ~15 km is found in the MSA at Diepkloof [START_REF] Steele | The Middle and Later Stone Age faunal remains from Diepkloof Rock Shelter, Western Cape, South Africa[END_REF] and at Sibudu Cave [START_REF] Plug | Aquatic animals and their associates from the Middle Stone Age levels at Sibudu[END_REF].

The major component of the Lower Deposits lithic technology is characterised by focussed procurement of silcrete, use of heat shatter to create core blanks, and short core-reduction chains producing small flakes and blades. Comparable technological systems have not been described in the MSA elsewhere (for reviews see 1, 38, 39, and SI Lithics), including at the six Fynbos Biome sites that lie within 100 km of VR003 (Figure 1; SI Lithics, Table S24).

Assemblages at those nearby sites are generally dominated by locally available quartzite or hornfels with systematic use of silcrete only after 75 ka [START_REF] Schmidt | Why Was Silcrete Heat-Treated in the Middle Stone Age? An Early Transformative Technology in the Context of Raw Material Use at Mertenhof Rock Shelter, South Africa[END_REF][START_REF] Porraz | Technological successions in the Middle Stone Age sequence of Diepkloof Rock Shelter, Western Cape, South Africa[END_REF][START_REF] Schmid | The 'MSA 1' of Elands Bay Cave (South Africa) in the context of the southern African Early MSA technologies[END_REF][START_REF] Evans | Hollow Rock Shelter, a Middle Stone Age site in the Cederberg[END_REF][START_REF] Mackay | Pleistocene archaeology and chronology of Putslaagte 8 (PL8) rockshelter, Western Cape, South Africa[END_REF][START_REF] Saktura | Prep) The Middle Stone Age sequence at Klipfonteinrand 1 (KFR1)[END_REF]. The exception is in MSA-Lynn at Diepkloof, which exhibits an increase in heat-treated silcrete and dedicated bladelet production leading in to the Still Bay (3). Heat shatter is rare in that assemblage, however, and none of the documented reduction processes feature the systematic use of core blanks made from heat shatter. The presence of bifacial and unifacial points in MSA-Lynn also suggests continuity with the overlying Still Bay, something that did not occur at VR003.

Results from VR003 suggest that the southern Succulent Karoo fostered a different set of adaptations to those characteristic of more humid areas to the south, including the manufacture of OES artefacts (possibly flasks), long distance transportation of marine shell, and the primary use of heat treatment to create core blanks for production of small flakes and blades. This package corresponds to a specific set of environmental conditions, and terminates around 80 ka with an apparent strengthening of regional winter rainfall systems.

Though it lacks fossile directeur implements, the archaeological signature of the Lower Deposits is as distinctive in the VR003 MSA sequence as the Howiesons Poort or Still Bay.

The difference between these phases is not in their innovativeness per se, but in their differing geographic extent. While the Howiesons Poort and Still Bay extend across much of southern Africa, the Lower Deposit package at VR003 appears to be a localised and environmentally-contingent adaptation.

These observations carry four significant implications for models of human behavioural evolution. First, they support arguments that the productive environments of the southern Cape coastal plains were not the sole locus of human innovation in southern Africa [START_REF] Wilkins | Innovative Homo sapiens behaviours 105,000 years ago in a wetter Kalahari[END_REF]. Indeed, conversely, marginal environments likely required novel or at least distinct technological solutions to enable persistent survivorship [START_REF] Thompson | Ecological risk, demography and technological complexity in the Late Pleistocene of northern Malawi: implications for geographical patterning in the Middle Stone Age[END_REF]. Second, and following from the first, research emphasis on biogeographically limited regions of southern Africa has probably acted to exaggerate the extent of cultural similarities through the MSA (SI Lithics).

Third, cultural connectedness in southern Africa, if measurable by similarity in stone tool assemblages, was variable through the late Pleistocene. While VR003 is culturally in phase with sites across the Fynbos Biome at least after 71 ka, it was not between 92-80 ka. Fourth, arguments that widespread cultural interaction was a primary driver of innovation in southern Africa (e.g., [START_REF] Mackay | Coalescence and fragmentation in the late Pleistocene archaeology of southernmost Africa[END_REF]) are not supported. It is possible that strong cultural connections pertained across the arid and interior regions of the sub-continent during MIS 5, however available data are insufficient to substantiate this proposition. In any case, Still Bay and Howiesons Poort assemblages occur across these regions as well as more humid parts of southern Africa (2). More interesting is the apparent loss of innovations (production of OES artefacts, systematic use of heat shatter to create core blanks) at VR003 after 80 ka, preceding the spread of the Still Bay. In some cases at least, innovation was responsive to environmental conditions and neither driven by interaction nor inherently cumulative [START_REF] Vaesen | Is Human Culture Cumulative?[END_REF].

Though the suite of adaptations identified at VR003 is currently unique, the pattern of transient innovations is consistent with the broader evidence from the African MSA. This can be read in one of two ways. It could imply a pre-modern condition in which the capacity for innovation was latent but cultural behaviour itself was yet to become a major selective force [START_REF] Boyd | The cultural niche: why social learning is essential for human adaptation[END_REF]. Subsequent developments may reflect stabilisation of high-fidelity information transmission in the human niche [START_REF] Sterelny | From hominins to humans: how sapiens became behaviourally modern[END_REF][START_REF] Gärdenfors | The Archaeology of Teaching and the Evolution of Homo docens[END_REF], potentially supported by transformations in language efficacy [START_REF] Marwick | Pleistocene Exchange Networks as Evidence for the Evolution of Language[END_REF]. Alternatively, it may partly reflect the out-sized role played by durable materials in models of human behavioural evolution. Flask fragments are rare even in large LSA OES assemblages, and their identifying characteristics are-in contrast to the possible VR003 examples-quite subtle; ground surfaces representing fragments of apertures <15 mm [START_REF] Kandel | Modification of ostrich eggs by carnivores and its bearing on the interpretation of archaeological and paleontological find[END_REF]. In the small, fragmented OES assemblages from pre-Still Bay MSA contexts [START_REF] Wilkins | Innovative Homo sapiens behaviours 105,000 years ago in a wetter Kalahari[END_REF] and/or where surface preservation is poor (as at VR003) such artefacts would easily be masked. Thus, even if the flaked OES from the Lower Deposits are the remains of flasks, their disappearance does not necessarily reflect the loss of that capability but potentially its shift into a form that is less robust and visually obvious. Similarly, while the long-distance transportation of durable items is evident in the MSA by 200 ka [START_REF] Blegen | The earliest long-distance obsidian transport: Evidence from the ∼200 ka Middle Stone Age Sibilo School Road Site, Baringo, Kenya[END_REF]; evidence for longdistance transport of perishable items, as with the shellfish at VR003, first appears much later for reasons that we consider more probably taphonomic than behavioural. Such preservation problems currently confound all models of human behavioural evolution [START_REF] Sterelny | From hominins to humans: how sapiens became behaviourally modern[END_REF][START_REF] Mcbrearty | The revolution that wasn't: a new interpretation of the origin of modern human behavior[END_REF][START_REF] Klein | Archeology and the Evolution of Human Behavior[END_REF]. Ultimately the archaeology of human behavioural evolution reflects the intersection of four factors: capability to innovate [START_REF] Wynn | Archeological insights into hominin cognitive evolution[END_REF], motivation to innovate [START_REF] Thompson | Ecological risk, demography and technological complexity in the Late Pleistocene of northern Malawi: implications for geographical patterning in the Middle Stone Age[END_REF], stabilisation of innovations [START_REF] Derex | Cumulative Cultural Evolution within Evolving Population Structures[END_REF][START_REF] Sterelny | Adaptable individuals and innovative lineages[END_REF], and preservation of innovations [START_REF] Henshilwood | The Origin of Modern Human Behavior: Critique of the Models and their Test Implications[END_REF]. The record from VR003 speaks to the first two, highlighting the importance of obtaining data from diverse ecological regions.

Disentangling the last two remains a key challenge going forward.

Methods

Excavation. Excavations at VR003 proceeded within stratigraphic units. Only selected items were individually piece plotted during excavations in 2009/2011, with most items recovered in 11 L buckets aggregates. In 2014, 2015, and 2016, during which seasons the Lower Deposits were excavated, all artefacts >20 mm and bones >25 mm were piece plotted.

Elongate items were plotted with 2 points where possible to allow for fabric analysis.

Modified OES was plotted regardless of size in these seasons. All bucket aggregates were sieved on site through nested 3 mm and 1.5 mm mesh sieves.

Geoarchaeology. Geoarchaeological analysis included grain size, loss on ignition, magnetic susceptibility, and micromorphology as well as fabric and refit analyses. Detailed results are presented in SI Geoarchaeology. Thin section analysis was conducted with a petrographic microscopic with magnification of up to 200x using oblique incidental (OIL), plane (PPL) and cross polarized (XPL) light. Micromorphological description follows terminology in [START_REF]Interpretation of Micromorphological Features of Soils and Regoliths[END_REF][START_REF] Stoops | Guidelines for analysis and description of soil and regolith thin sections[END_REF] and a detailed analysis is presented in SI Micromorphology. Fabric analysis was undertaken using the methods and code provided in [START_REF] Mcpherron | Additional statistical and graphical methods for analyzing site formation processes using artifact orientations[END_REF].

Single-grain luminescence dating. Luminescence samples were obtained by hammering metal tubes into cleaned section faces. Samples were prepared under subdued red light at the Royal Holloway Luminescence Laboratory, yielding sand-sized quartz and potassium feldspar (K-feldspar) separates. All luminescence measurements were carried out using a Risø TL/OSL-DA-15 automated dating system, fitted with a dual-laser single-grain luminescence attachment. Quartz was measured using a standard single-aliquot regenerative-dose method whereas a post infrared, infrared stimulated luminescence procedure, intended to minimise the effect of "fading" (62) was used for K-feldspar. Individual grains were stimulated using either a focused 10 mW Nd:YVO 4 solid-state diode-pumped green (532 nm) laser for quartz or a 140 mW TTL modulated infra-red (IR, 830 nm) laser with a Schott RG 780 longpass filter mounted in the beamline for K-felspar. Simultaneous illumination of all grains on a disc was carried out using either blue (470 nm) or IR (870 nm) light emitting diodes (LEDs). Luminescence was detected using an Electron Tubes Ltd 9235QB15 photomultiplier tube shielded by Schott BG3 and BG39 filters. Irradiation was carried out using a 1.48 GBq 90 Sr/ 90 Y beta source calibrated relative to the National Physical Laboratory, Teddington 60 Co γ-source [START_REF] Armitage | The measured dependence of laboratory beta dose rates on sample grain size[END_REF]. Data analysis was carried out using functions within the numOSL and Luminescence R packages. K-feldspar ages were corrected for a measured fading rate (g-value normalised to 2 days) of 1.9±0.1 %/decade [START_REF] Huntley | Ubiquity of anomalous fading in K-feldspars and the measurement and correction for it in optical dating[END_REF].

U-series dating of ostrich eggshell. OES were analyzed in the Berkeley Geochronology Center's U-Daughter Lab. OES dating samples were screened using profiles of [U] and 232 Th/U obtained via laser ablation using a Photon Machines Analyte II excimer laser attached to a Thermo-Fisher NEPTUNE Plus inductively coupled mass spectrometer (ICP-MS). Selectively abraded subsamples of OES calcite from known positions in each OES fragment were analyzed in solution mode using the Thermo-Fisher NEPTUNE Plus ICP-MS. Laser ablation, solution analyses, data reduction, and calculation of 230 Th/U burial ages followed techniques similar to those described in [START_REF] Sharp | 230Th/U burial dating of ostrich eggshell[END_REF]. Activity ratios and ages were calculated using the half-lives from [START_REF] Jaffey | Precision measurement of half-lives and specific activities of 235 U and 238[END_REF][START_REF] Cheng | Improvements in 230 Th dating, 230 Th and 234 U half-life values, and U-Th isotopic measurements by multi-collector inductively coupled plasma mass spectrometry[END_REF][START_REF] Holden | Total half-lives for selected nuclides[END_REF]. Ages and uncertainties were calculated using [START_REF] Ludwig | Isoplot/Ex version 3.75: A Geochronological toolkit for Microsoft Excel[END_REF].

Phytolith analysis. Nine sediment samples were processed for phytoliths, covering strata from I-09 to I-03. Phytoliths were extracted from approximately 5 g of bulk fine fraction sediment. Samples were sieved through 125 µm mesh; 2 g of each <125 µm subsample was treated for carbonate digestion using 10% HCl, followed by clay deflocculation aided by NaPO3. 10% KOH solution was used for digestion of organic matter, before another round of deflocculation. Samples were neutralized, centrifuged and decanted between all steps.

Phytoliths were extracted by heavy liquid flotation, using a solution of sodium polytungstate (2.3 g/cm 3 ). Assemblages were pipetted onto coverslips, dried, and mounted to microscope slides using Entellan medium for identification and counting. Phytolith abundance was counted up to 300, with concentration per gram of sediment later estimated using the proportion of sample analysed and initial 2 g weight.

Faunal analysis. All faunal (vertebrate, mollusc, and eggshell) remains were examined, including those that were individually plotted (>25 mm) as well as those recovered from the 3 mm screens. The screened materials were rinsed with water before sorting. Specimens were identified using comparative material housed in the Department of Archaeology at the University of Cape Town and the Department of Anthropology and the Museum of Wildlife and Fish Biology at the University of California, Davis, and published manuals. Specimens of any size that could be identified to element and taxon were recorded in the MNISQL database program written by Richard G. Klein (Stanford University). All identified specimens were examined for surface modifications and preservation. Molluscs and eggshells were counted, weighed, and examined for surface modifications. Discoloration consistent with heating was also noted [START_REF] Collins | An often overlooked resource: Ostrich ( Struthio spp.) eggshell in the archaeological record[END_REF]. Lithic analysis. Basic methods of stone artefacts classification and analysis are described in [START_REF] Steele | Varsche Rivier 003: A Middle and Later Stone Age site with Still Bay and Howiesons Poort assemblages in southern Namaqualand, South Africa[END_REF]. Additional data were acquired as follows. Core scars counts applied a scaled minimum scar size cut-off at 20% of core maximum dimension, and also a fixed value (15 mm) presented separately in SI. Heat treatment was identified visually using methods described in [START_REF] Schmidt | How reliable is the visual identification of heat treatment on silcrete? A quantitative verification with a new method[END_REF]. Silcrete is common and physically diverse around VR003 (71), complicating development of reference collections. For this reason we rely principally on visually-obvious heat-induced non-conchoidal fractures (HINC) [START_REF] Schmidt | A previously undescribed organic residue sheds light on heat treatment in the Middle Stone Age[END_REF] to identify the presence of thermal effects.

Figure 1 .

 1 Figure 1. (A) Aridity map of southern Africa, with the Varsche Rivier 003 (VR003; white dot) and relevant MSA sites referred to in the text (yellow dots) indicated. Aridity index data from (73) with definitions according to (74). Red box shows location of inset map (B). (B) VR003 in relation to modern biome-bioregion boundaries from (75) and Fynbos Biome sites immediately south: DRS=Diepkloof, EBC=Elands Bay Cave, HRS=Hollow Rock Shelter, KFR=Klipfonteinrand 1, MRS=Mertenhof, PL8=Putslaagte 8. (C) Site photo of VR003 and the Varsche Rivier 003 valley, looking west. (D) Excavation plan at conclusion of most recent season in 2016. The original deep sounding is highlighted in red.

Figure 2 .

 2 Figure 2. East section of deep sounding with key artefact type and location of geochronology samples. Per convention, luminescence ages are presented here at 1 sigma uncertainty, U-Th ages at 2 sigma. For artefacts, aggregate contexts refers to silcrete cores recovered during the initial seasons (2009, 2011) during which individual artefacts were typically not plotted. These cores were recovered from bucket aggregates and include up to two cores in some cases. Inset bottom left: Microphotographs showing the typical components and structure of I-08. (A). Bone (B) fragments range in size from gravel to sand.Another typical anthropogenic component at the site is ostrich eggshell (OES). Note also the coarse crystalline limestone (Li), and calcite crystals (C) and fine coating of these coarse grains. (B) Microscopic silcrete (Si) knapping debris and rounded soil aggregates (Agg) from the plateau above the site in a calcareous matrix.

Figure 3 .

 3 Figure 3. Comparison of primary factors determining long-term regional climate dynamics with VR003 phytolith data for 1) C4:C3 grass ratios and 2) the percentage of Restionaceae and woody taxa, a classification reflecting the abundance of fynbos vegetation (Cordova et al., 2013; Esteban et al., 2017). Data for orbital parameters is from Laskar et al. (2004) and the SE Atlantic wind strength composite is as calculated by Chase et al. (2019) using the data of Farmer et al. (2005), Little et al. (1997), Pichevin et al. (2005) and Stuut et al. (2002).The phytolith data are depicted as uncertainty spaces defined by the multiplication of probability density functions derived from 1) stratigraphic unit ages and errors for the Lower Deposits and Howiesons Poort layers and 2) aggregated phytolith data and the associated standard deviation of sample values from these units (see SI for more detail).

Figure 4 .

 4 Figure 4. Flaked OES fragments from the Lower Deposits. Artefacts 9220 and 7693 have simple perforations like those made by hyenas (76), but 9340, 7974, and 9300 show apparent elaborations of similar perforations through more extensive flaking. The artefacts in the central column may thus represent production stages leading to more finely 'finished' pieces in the left two columns. The 'hypothetical fit' in the top right is an indicative photo montage of VR003 samples 6147, 7833, 8415, 8348, and 6307. These pieces do not actually refit. Artefact AA8438 (bottom right) is from the Ethnographic Collection at Iziko Museums, and was recovered from Ysterfontein Village by G.E. Loedalf in June 1968 and donated to the museum in December 1968.

Figure 5 .

 5 Figure 5. A selection of silcrete cores from the Lower Deposits (see also Figure S24). White arrows indicate location of HINC surfaces; yellow arrows indicate location of flaking initiations. All artefacts shown except 2815 were made on heat shatter. 1421: Minimal core on heat shatter. Inset (a) shows the contact between the smooth post-heat removal and the scalar features on the older shatter surface. 1462: Simple prepared platform core on heat shatter. 1520: Minimal core on heat shatter. 3450: Single platform core with small laminar removals on heat shatter. 5391: Prepared core on heat shatter with one laminar removal. 7379: Multiplatform core on heat shatter. 2815: Unheated single platform core with small laminar removals.

Acknowledgments

Funding: US National Science Foundation: High-Risk Anthropology (TES); US National Science Foundation: Archaeology (TES); US National Science Foundation: Archaeometry; the Leakey Foundation (TES); the University of California, Davis (TES); Australian Research Council (AM); Australian National University (AM); Max Planck Society (MCS); the University of Wollongong (AM); and the Research Council of Norway Centers of Excellence project number 262618 (SJA). Assistance: Fieldwork was conducted under Heritage Western Cape Permit X120417JL07; P. and L. Visser (2008-2011) and I. Zaaiman (2014-present) kindly provided access to the Varsche Rivier 260 Farm. Colleagues at the University of Cape Town, Department of Archaeology, Iziko: South African Museum, and ACO Associates all provided valuable support, as did R.G. Klein, T. Weaver, A. Welz, and our student volunteers and workers. Manuscript preparation: We are grateful to four anonymous reviewers and the handling editor Dr Luiśeach Nic Eoin for their considerable efforts if improving this paper.

Data availability statement

All data used in the present study are available from the corresponding author on reasonable request.

Data Availability Statement

The spatial, lithic, faunal and pigment data used in this paper are included in a supplementary file. Phytolith data are provided in tables in the Supplementary Information.

The VR003 collections are curated at University of Cape Town and Iziko Museums Cape Town, and can be accessed by arrangement with TES and AM.

Competing Interests Statement

The authors have no competing interests as defined by Nature Portfolio, or other interests that might be perceived to influence the results and/or discussion reported in this paper.


Nassim Belmecheri
email: belmecheri.nassim@edu.univ-oran1.dz

Noureddine Aribi
email: aribi.noureddine@gmail.com

Nadjib Lazaar
email: nadjib.lazaar@lirmm.fr

Yahia Lebbah
email: ylebbah@gmail.com

Samir Loudni
email: samir.loudni@imt-atlantique.fr

BOOSTING THE LEARNING FOR RANKING PATTERNS

Keywords: Interactive Data Mining, Machine Learning, Active Learning, Multicriteria decision making, Analytic Hierarchy Process

Discovering relevant patterns for a particular user remains a challenging tasks in data mining. Several approaches have been proposed to learn user-specific pattern ranking functions. These approaches generalize well, but at the expense of the running time. On the other hand, several measures are often used to evaluate the interestingness of patterns, with the hope to reveal a ranking that is as close as possible to the user-specific ranking. In this paper, we formulate the problem of learning pattern ranking functions as a multicriteria decision making problem. Our approach aggregates different interestingness measures into a single weighted linear ranking function, using an interactive learning procedure that operates in either passive or active modes. A fast learning step is used for eliciting the weights of all the measures by mean of pairwise comparisons. This approach is based on Analytic Hierarchy Process (AHP), and a set of user-ranked patterns to build a preference matrix, which compares the importance of measures according to the user-specific interestingness. A sensitivity based heuristic is proposed for the active learning mode, in order to insure high quality results with few user ranking queries. Experiments conducted on well-known datasets show that our approach significantly reduces the running time and returns precise pattern ranking, while being robust to user-error compared with state-of-the-art approaches.

Introduction

Data mining is the study of how to extract relevant information from data and exploit it as useful knowledge. One of its most important subfields, pattern mining, involves searching and enumerating interesting patterns in data. In the last decade, the pattern mining community has witnessed a sharp shift from efficiency-based approaches to methods that can extract more meaningful patterns. Unfortunately, obtaining interesting results with traditional pattern mining methods can be a tough and time-consuming task. The two main issues are that: 1) humongous amounts of patterns are found, of which many are redundant, and 2) preferences and background knowledge of the domain expert are not taken into account. The importance of taking user preferences and knowledge into account was first emphasized by Tuzhilin [START_REF] Silberschatz | On subjective measures of interestingness in knowledge discovery[END_REF]. The main idea is to model the user's preferences using objective interestingness measures. Here, the interestingness of a pattern is computed from the data only. However, as stated in [START_REF] De | An information theoretic framework for data mining[END_REF], using objective quality measures are of limited practical use, since interestingness depends on the specific user and task at hand. In recent years, pattern mining has been challenged by an increasing focus on user-centered, interactive, and anytime pattern mining [START_REF] Dzyuba | Interactive discovery of interesting subgroup sets[END_REF][START_REF] Boley | One click mining: interactive local pattern discovery through implicit preference and performance learning[END_REF][START_REF] Dzyuba | Learning what matters -sampling interesting patterns[END_REF]. This new paradigm stresses that users should be presented quickly with patterns likely to be interesting to them, and typically affect later iterations of the interactive mining process by giving feedback. An important aspect of this framework is the ability to learn user-specific pattern ranking functions from feedback. This idea was first investigated in [START_REF] Xin | Discovering interesting patterns through user's interactive feedback[END_REF] and recently extended by Boley et al. [START_REF] Boley | One click mining: interactive local pattern discovery through implicit preference and performance learning[END_REF] and Dzyuba et al. [START_REF] Dzyuba | Interactive discovery of interesting subgroup sets[END_REF][START_REF] Dzyuba | Learning what matters -sampling interesting patterns[END_REF] in the context of interactive pattern mining. These approaches exploit standard machine learning techniques to learn weighted vectors according to some selected features on patterns (i.e. items, transactions, length . . .).

In [START_REF] Dzyuba | Interactive discovery of interesting subgroup sets[END_REF], a linear ranking function is learned using RankingSVM. In [START_REF] Boley | One click mining: interactive local pattern discovery through implicit preference and performance learning[END_REF][START_REF] Dzyuba | Learning what matters -sampling interesting patterns[END_REF], the authors propose to use Stochastic Coordinate Descent (SCD) [START_REF] Shalev | Stochastic methods for l 1 -regularized loss minimization[END_REF] to learn a logistic function. While these methods allow to exploit user feedback to learn ranking functions, they also result in a more computationally expensive learning task, particularly when the number of pairs of patterns and measures used for ranking increases. However, a vital ingredient of this framework is the ability to quickly present a set of patterns to the user and focus on what should be of interest using some interestingness measures.

In this paper, we tackle the problem of learning pattern ranking functions as a multicriteria decision making problem. We use a weighted linear function to aggregate all the individual measures into a global ranking function. A fast and scalable learning algorithm is used to maintain the right expected weights of measures. The proposed approach exploits the Analytical Hierarchy Process (AHP) [START_REF] Thomas | What is the analytic hierarchy process? In Mathematical models for decision support[END_REF], and a set of user-ranked patterns to learn the measures' weighting vector, that maximizes the correlation between the (unknown) user's ranking function and the learned AHP-based ranking function.

This approach was firstly introduced in our earlier work [START_REF] Belmecheri | Une méthode d'apprentissage par optimisation multicritère pour le rangement de motifs en fouille de données[END_REF], where we show initial results of the passive version of the algorithm. More precisely, our new contributions compared with the previous version are as follows:

• A detailed presentation of the whole approach with running examples.

• A new generic version of the learning algorithm to learn both in active and passive modes.

• Proposition of a sensitivity based heuristic for selecting patterns when learning in the active mode.

• Implementing three different user simulations.

• Validation of the whole approach with its various settings (i.e., passive and active modes, user simulations, etc.) on large and new datasets. • Showing the robustness of the approach in an interactive learning process, considering user mistakes and user changing its ranking criterion.

To assess the interest of our approach, we consider the association rules mining problem as a case study. Experiments conducted on a wide range datasets show that our approach significantly reduces the running time, while ensuring accurate pattern ranking compared to the state-of-the-art approaches.

The rest of the paper is organized as follows: Section 2 introduces the related work. Section 3 presents some necessary preliminaries. Section 4 formulates the tackled problem and describes our approach. Section 5 illustrates our approach on a running example. Empirical results are reported and discussed in Section 6. Section 7 concludes the paper.

Related work

Recent approaches for iterative/user-centric pattern mining are based on learning ranking functions throughout user pairwise pattern rankings. This problem is known as object ranking. Several methods have been developed for the object ranking task [START_REF] Kamishima | A survey and empirical comparison of object ranking methods[END_REF]. A common solving technique involves minimizing pairwise loss, e.g., the number of discordant pairs. In [START_REF] Xin | Discovering interesting patterns through user's interactive feedback[END_REF], the authors propose a log-linear model for itemsets to learn the user's prior knowledge from her feedback. They use RankingSVM formulations [START_REF] Cao | Adapting ranking SVM to document retrieval[END_REF] to learn a ranking function. For more complex patterns (e.g., sequential patterns), a belief model is proposed, which exploits belief probabilities assigned to transactions. Later, Dzyuba et al. [START_REF] Dzyuba | Interactive discovery of interesting subgroup sets[END_REF] extend the approach based on RankingSVM for active preference learning for ranking patterns. According to [START_REF] Bottou | Support vector machine solvers[END_REF], the worst-case time complexity to solve the SVM problem varies between k 2 and k 3 on the number of samples k; whereas our approach is linear on k (see section 4.4). In [START_REF] Boley | One click mining: interactive local pattern discovery through implicit preference and performance learning[END_REF], the same approach is adopted to learn a logistic function using Stochastic Coordinate Descent (SCD) [START_REF] Shalev | Stochastic methods for l 1 -regularized loss minimization[END_REF]. The same technique is also used in [START_REF] Dzyuba | Learning what matters -sampling interesting patterns[END_REF], but the learned function is exploited for patterns sampling. In [START_REF] Mansurul | Priime: A generic framework for interactive personalized interesting pattern discovery[END_REF], regression techniques are adopted to learn ranking functions.

Our approach is different and tackles the problem of learning pattern ranking functions as a multicriteria decision making problem using AHP. Moreover, our method remains fast when the number of patterns used for ranking increases. 3 Background

Pattern mining and interestingness measures

Data can be abstracted as a triplet (O, A, L) in which O is a set of objects, A is a set of attributes and L is the language used to express objects on attributes. This framework is inspired from inductive databases concepts [START_REF] De | A perspective on inductive databases[END_REF][START_REF] Imielinski | A database perspective on knowledge discovery[END_REF]. Following the language L, for instance, we can get classical datasets: (1) when L is a binary relation between attributes and objects (i.e., L ⊆ O × A), we get the classical itemset mining framework; (2) when L expresses each object as a sequence of attributes, we get a sequential dataset; (3) when L expresses each object as a graph where nodes and vertices are labeled, we get a dataset of graphs. Data mining tasks aim at discovering interesting regularities, namely patterns, between objects in large-scale datasets.

Measuring the interestingness of discovered patterns w.r.t. the user-specific preferences is an active field in Data Mining.

Nine concepts have been introduced to determine whether a pattern is interesting or not: Conciseness, Generality, Reliability, Peculiarity, Diversity, Novelty, Surprisingness, Utility and Applicability [START_REF] Geng | Interestingness measures for data mining: A survey[END_REF]. Some concepts are correlated like Surprisingness and Applicability concepts, are conflicting like Generality and Pecularity, or independent like Novelty and Utility. The user has in mind some of these concepts to say that she prefers a pattern than another. A wide range of measures, and aggregation of these measures, have been proposed to satisfy the user preferences.

Analytical Hierarchy Process (AHP)

AHP is a well-known multicriteria decision-making method developed by Saaty [START_REF] Thomas | What is the analytic hierarchy process? In Mathematical models for decision support[END_REF]. It is based on structuring and synthesizing the decision problem into a problem hierarchy, and eliciting criteria weights from the decision maker through a series of pairwise comparisons, as opposed to utilizing numerical values directly. After constructing a hierarchy of the decision problem, the importance weights of criteria can be calculated according to the following three main steps:

1. A user is asked to compare the criteria of a given level in a pairwise manner to estimate their relative importance in relation to criteria at the preceding level. The pairwise comparisons are collected into a pairwise comparison matrix, A = (a ij ) m×m , with a ij expressing the relative importance of criterion i to criterion j: the i th criterion is better than the j th criterion if a ij > 1. The preference matrix A is filled s.t. a ij = 1/a ji and a ii = 1.

For simplicity and easiness, AHP uses 9 degrees of preference, where a ij = 1 indicates an indifference and a ij = 9 an absolute preference.

2. Once the pairwise comparison matrix at a given level is built, the weight vector w = (w 1 , . . . , w m ) T can be computed using several mathematical techniques proposed in the literature. For example, the eigen vector method (EVM) or distance-based minimization methods, such as Least Squares Method, Logarithmic Least Squares Method, Weighted Least Squares Method, Logarithmic Least Absolute Values Method and Singular Value Decomposition [START_REF] Saaty | Comparison of eigenvalue, logarithmic least squares and least squares methods in estimating ratios[END_REF][START_REF] Gass | Singular value decomposition in ahp[END_REF][START_REF] Takeda | Estimating criterion weights using eigenvectors: A comparative study[END_REF][START_REF] Blankmeyer | Approaches to consistency adjustment[END_REF][START_REF] Brunelli | Introduction to the analytic hierarchy process[END_REF]. The most used one is the Eigen Vector Method. The EVM method computes the weight vector w by solving the characteristic equation:

A • w = λ max • w w T 1 = 1 (1)
where A is the pairwise comparison matrix, λ max is the highest eigen value of A, and 1 = (1, . . . , 1) T . The constraint m i=1 w i = 1 is added to aid the solving process and avoid the infinitely many solutions. Note that, if A is positive then the highest eigenvalue is real (i.e. λ max ∈ R) [START_REF] Brunelli | Introduction to the analytic hierarchy process[END_REF]. Interestingly, Saaty [START_REF] Thomas | A scaling method for priorities in hierarchical structures[END_REF] mentioned that the perfect1 normalized eigenvector w satisfied the following relation:

a ij = w i w j , ∀i, j = 1 . . . m. (2)
In this case λ max = m, otherwise λ max > m. The relation given by equation (2) explains why some researchers prefer the distance-based methods to directly consider to minimize the distance between (a ij ) m×m and (w i /w j ) m×m . However, the resulting problem is non-linear and difficult to solve. This is why we prefer, in this paper, to use the EVM method instead of distance-based methods.

Obviously, the hierarchy may contain more levels of criteria, especially when the number of criteria exceeds nine. One key idea to handle this particular case consists to establish a hierarchy structure based on existing criteria dependencies.

It is important to generate an optimized decision problem hierarchy, to reduce the number of pairwise decisions. For more details, we refer the reader to [START_REF] Brunelli | Introduction to the analytic hierarchy process[END_REF]. Note that, in this paper, we will not cover this point.

Example 1 Consider a multicriteria decision problem with three criteria, for which we build a pairwise comparison matrix A(a ij ) 3×3 that compares the relative importance of criteria according to the achievement of an overall goal. This matrix is given by:

A =   1 1 2 1 4 2 1 1 2 4 2 1  
To find the criteria weight vector, one could use the EVM method, which consists to solve the equation: Aw = λ max w.

The solution is given by the vector w = (w 1 , w 2 , w 3 ) = ( 1 7 , 2 7 , 4 7 ) whose components are the weights of criteria.

AHP-based learning approach for ranking patterns

Our objectif is to learn a ranking function aggregating a set of interestingness measures while approximating the user-specific preferences.

Problem statement: learning pattern rankings

We show in this section that learning a ranking function from some interestingness measures w.r.t. user-specific preferences can be translated into a multicriteria problem. In our context, the criteria are interestingness measures. The task is to learn a function for ranking patterns from a sample of ordered patterns. Following previous research [START_REF] Dzyuba | Interactive learning of pattern rankings[END_REF], we use ordered feedback, where a user is asked to provide a total order over a (small) number of patterns according to her subjective interestingness on them.

Let be a binary preference relation between patterns. A ranking function based on , denoted by r (.), accepts as input a subset of patterns P ⊆ L and returns as output a permutation S = P r1 , P r2 , . . . , P rn of P, s.t. |P| = |S| and ∀i < j, P ri P rj .

The user ranking function to learn is denoted by r u , which is based on the user preference relation u . Given a set of interestingness measures M = {M 1 , . . . M m } and the corresponding ranking functions r M 1 , . . . , r Mm . We denote by rank Mi (P j ) the rank of P j ∈ P w.r.t. the interestingness measure M i . Here, (P k Mi P l ) means that M i (P k ) ≥ M i (P l ).

We propose to state the problem as a learning problem, where we have to find the weights w i of a linear aggregation function over the measures from a set of ranked patterns that maximizes the correlation of the aggregation with the user ranking function r u :

f (P ) = i=1..m w i . M i (P ) (3)
Our main idea is to exploit the user feedback to perform pairwise comparisons between measures in order to estimate their relative importance on the basis of individual scores of measures. The results of these pairwise comparisons are then collected into a pairwise comparison matrix used by AHP to compute the weights w i .

Comparing a single measure to a user ranking:

Let S = P 1 , . . . , P n be a user ranking. Let M = {M 1 , . . . , M m } be some interestingness pattern measures.

To evaluate the overall ranking accuracy of a given measure compared to a user ranking, we use the Kendall's W concordance coefficient [START_REF] Kendall | The problem of m rankings[END_REF]. Given a measure M i and a user ranking S, we denote by K i (S) ∈ [0, 1], the Kendall's W between the ranking using M i and the user ranking S, where the value 1 (resp., value 0) represents a perfect concordance (resp., no concordance):

K i (S) = 3α (|S| 3 -|S|) , α = |S| =1 (R -R) 2 , (4)
where R = rank M i (P ) + rank u (P ) with P ∈ S, and R = 1

|S| |S| =1 R .
Comparing two measures according to a user ranking:

Let M i and M j two measures to be compared according to a given user ranking S. Computing the gap ∆ i,j (S) = K i (S) -K j (S) enables to know how much M i is closer to the user ranking S than M j : if ∆ i,j (S) ≥ 0, then M i is closer, else the converse. If a set of user rankings S = {S 1 , . . . , S n } is considered, comparing two measures M i and M j on S comes to estimating the closest measure to S by averaging the gaps on all the user rankings of S:

∆ i,j = 1 n S k ∈S ∆ i,j (S k ).

Learning weights process

Function 1 implements the learning process that computes a weight vector w (a weight for each measure) by exploiting the pairwise comparisons of measures. It takes as inputs a vector of pairs comparisons ∆ and the corresponding index l, a user ranking S and a set of measures M. The learning step is done at line 2 where for each pair of measures, we compute the gap w.r.t the user ranking S. learnWeights is an incremental function that can take into account the previous l user rankings by updating ∆. At line 5,the AHP matrix is built by scaling the ∆ i,j comparisons to the permitted values (between 1/9 and 9). Once done, the criteria weight vector w is returned in line 12 by solving the minimization problem described in line 11, using the usual eigen vector method (EVM) [START_REF] Brunelli | Introduction to the analytic hierarchy process[END_REF].

Function 1 learnWeights( ∆, l , S, M) In :Set of measures M = {M 1 , .
. . , M m }; user ranking S = P 1 , . . . , P n ; In Out : pairs comparisons and index parameter ∆, l ; Out :Weight vector w;

A[i, j] ← 1, ∀i, j ∈ {1, . . . , m}; foreach M i , M j ∈ M : i < j do ∆ i,j ← l l+1 ∆ i,j + 1 l+1 (K i (S) -K j (S)); end foreach ∆ i,j ∈ ∆ do if ∆ i,j < 0 then scale ∆ i,j to (-9.. -1); A[j, i] ← |∆ i,j |; A[i, j] ← 1/|∆ i,j | ; else scale ∆ i,j to (1..9); A[i, j] ← ∆ i,j ; A[j, i] ← 1/∆ i,j ; end w ← solve A • w = λ max • w subject to m j=1 w j = 1, w j > 0, ∀j = 1 . . . m. return w;
Once the weight vector w is learned, we can compute the score of a given pattern P i using the following weighted aggregation function:

g w (P i ) = Mi∈M w i scale(M i (P )) (5)
where the scale function is used to adjust interestingness values of the different measures to a [0, 1] scale.

AHPRank algorithm

Function 1 implements the key concept of our approach. It enables to learn a weight vector w from a given user ranking S. Moreover, function 1 can easily be used in an iterative process and for a passive/active perspective using the incremental computation of ∆ in line 3. We propose AHPRank (algorithm 2) based on learnWeights function to learn a weighted aggregation function in a passive mode as well as in an active one. Algorithm 1 takes as input a set of measures M, a set of user-ranked patterns S and a triplet of parameter P, θ, T corresponding respectively to a collection of patterns and two integers to use in the active mode. AHPRank starts by initializing the vector of pairs comparisons to zero in line 1. If AHPRank is fed with a non empty S, then it acts in a passive mode by iterating and calling learnWeights on the given user-ranked patterns S (lines 3-6). Otherwise, the active mode is triggered by submitting T queries to the user (lines 7-15). Here, the user is asked to rank a subset of patterns proposed by a query generator. Our query generator is based on a heuristic that exploits the performance of the overall approach on the already learned rankings. More precisely, the active learning mode is performed through the following main iterative steps:

1. As a first step, a subset of patterns is randomly sampled from the global set of patterns P: At line 10, SamplePatterns returns a sample P of θ patterns. 2. Select a pair of patterns using BasedHeuristic function. The proposed heuristic aims to select a pair of patterns of good quality to speed up the convergence of the learning process (function 3 detailed in section 4.3.1). 3. Interacting with the user to get her preferences w.r.t to the patterns ranking query feedback (line 12). 4. Preference-based learning of the user ranking function (line 13), by calling learnWeights function.

It is important to stress that it is very usual that P is of huge size making step 2 very costly. Step 1 enables us to avoid this complexity by sampling a reasonable subset of patterns. Moreover, it also introduces a kind of diversity on the patterns proposed to the user through step 2.

To be effective, our learning method must decide when to stop e.g. maximal number of iterations, albeit being open to any custom stopping criterion. We take into account the case where the user can stop at any time she feels satisfied, and we simulate the user's stopping point using a fixed number T of learning iterations.

foreach ∆ i,j ∈ ∆ do ∆ i,j ← 0; if S = ∅ then foreach S k ∈ S do w t ← LearnWeights( ∆, k , S k , M) ; //

A Pattern Selection Heuristic for AHPRank

Learning in active manner is not an easy task, since it is crucial that each learning step improves the learned function. Selecting the right patterns to present to the user is what allows the algorithm to improve the learning process step by step. However generating the right set of patterns is NP-hard [START_REF] Ailon | An active learning algorithm for ranking from pairwise preferences with an almost optimal query complexity[END_REF]. We propose a heuristic (Function 3) based on sensitivity analysis for AHP models [START_REF] Erkut | On Sensitivity Analysis in the Analytic Hierarchy Process[END_REF]. The rationale behind our heuristic is to select a single pair of patterns that are close in terms of overall score predicted by the learned function, relative to the sum of the measures gaps:

σ(P i , P j ) = g w (P i ) -g w (P j ) m l=1 (M l (P i ) -M l (P j )) ; i, j ∈ 1 . . . k. (6)
Intuitively, a successful aggregation should have the following property: if two patterns are close in the overall predicted score, they should be close also in their measures values. Thus, the algorithm will be enforced into learning the correct preferences of the patterns when having the lowest σ value, since the selected pair is surely close in terms of g w values and very distant on the measures values.

Example 2 Given four interestingness measures M = {M 1 , M 2 , M 3 , M 4 } and two patterns {P 1 , P 2 }. Suppose that the measure values for both patterns are as follows: P 1 = 0.1, 0.2, 0.3, 0.7 , P 2 = 0.7, 0.3, 0.2, 0.1 and that the current learned weight vector is w = 0.25, 0.25, 0.25, 0.25 . At this stage, g w (P 1 ) = 0.26 and g w (P 2 ) = 0.26. Here P 1 and P 2 are equivalent w.r.t. the current state of g w . However, the values of the four measures are different for the two patterns. This pair of patterns is an interesting candidate (σ(P 1 , P 2 ) = 0), where eliciting a preference on such a pair will make the learning closer to the user ranking. proof Let S = {S 1 , . . . , S n } be a set of n user rankings, k the size of the largest ranking S t and m a bounded number of measures in M. Once the pairwise comparison matrix A is built, we could compute the preference vector of weights w using several mathematical techniques. We have used the eigen-vector based method (i.e., EVM) [START_REF] Brunelli | Introduction to the analytic hierarchy process[END_REF], for which the worst case time complexity is about O(m 3 ) [START_REF] Victor | The complexity of the matrix eigenproblem[END_REF]. The EVM approach is of constant time complexity O(1) since that m is constant. Complexity of computing the matrix at line 3 of the learnWeights function is O(m n k) since that Kendall's W is in O(k) (see Definition (4)). The complexity of lines 2, 5 and 11 in learnWeights are respectively O(n m 2 + m n k), O(m 2 ) and O(m 3 ). Notice that in AHP, it is demonstrated in [START_REF] Thomas | Why the magic number seven plus or minus two[END_REF] that the number of criteria is recommended to be no more than seven ±2. That is, with m ≤ 9, we get an asymptotic quadratic complexity of O(n k) when AHPRank is in passive mode. In other terms, the approach costs O(k) for each ranking in the given S. Now, when AHPRank is in active mode where queries are pair of patterns (k = 2), the complexity is linear on the number of queries submitted to the user O(n).

It is important to stress that in practice, we have in general a set S reduced to a large element in the passive learning mode ( n = 1 and a large k), and to a set of n queries of pair of patterns (a large n and a k = 2) in the active mode. This makes AHPRank running in a linear time (linear on k in passive and on n in active) in most of the cases. This low complexity makes AHPRank a fast approach to learn a user ranking function, which is supported by the experimental evaluation in section 6.

Running Example

To illustrate our approach, we consider an initial set of patterns P = {P 1 , . . . , P 10 }, five interestingness measures M = {M 1 , . . . , M 5 } and a user-ranking r u . Columns of Table 1 show the user ranking for P, the rankings given by M i on P and the AHPRank results. It is important to stress that no measure perfectly matches the user ranking.

The data in Table 1 is used by our algorithm to build the AHP Matrix and to learn a weight vector w over M. For the sake of simplicity, let us call AHPRank in the passive mode with S = {S a = P 3 , P 1 , P 5 , P 2 , P 4 }. Here, the user prefers P 3 u P 1 u P 5 u P 2 u P 4 . AHPRank learns weights by calling learnWeights on S a and by computing the correlation between the user rankings of S a and the ones of the measures M i . The matrix provided in Equation [START_REF] Shalev | Stochastic methods for l 1 -regularized loss minimization[END_REF] values of each measure pairs. We recall that for |S| > 1, ∆ i,j is an averaged value of ∆ i,j (S k ) where S k ∈ S. Since we only have S a , ∆ 1,2 = ∆ 1,2 (S a ). Here, ∆ 1,2 (S a ) represents the gap between the two measure rankings M 1 and M 2 w.r.t the user ranking S a . For having ∆ 1,2 (S a ), we need to compute Kendall's W K 1 (S a ) (resp., K 2 (S a )) between the ranking of M 1 (resp. M 2 ) compared to the user ranking S a : ∆ 1,2 (S a ) = (K 1 (S a ) -K 2 (S a )) = (0.25 -0.25) = 0. After scaling the values of ∆ to (-9.. -1) if negatives, and to (1..9) otherwise. We can see in Equation ( 7) that, for instance, measure M 5 is better than M 4 with a degree of 6. The same intensity is observed between M 5 and M 3 . We can also observe that M 3 and M 4 are indifferent.

∆ =      (M 1) (M 2) (M 3) (M 4) (M 5) (M 1) 0 0.42 0.42 -0.43 (M 2)
0.20 0.28 -0.25

(M 3)
-0.08 -0.55

(M 4)
-0.60

(M 5)      Scaling -→      (M 1) (M 2) (M 3) (M 4) (M 5) (M 1) 1 4 4 -4 (M 2) 2 3 -3 (M 3) 1 -6 (M 4)
-6

(M 5)      (7)
Afterwards, AHPRank computes the AHP matrix A through learnWeights function and the scaled ∆ matrix (i.e., the average correlation gap) as an input:

A =      (M 1) (M 2) (M 3) (M 4) (M 5) (M 1) 1 1 4 4 1/4 (M 2) 1 1 2 3 1/3 (M 3) 1/4 1/2 1 1 1/6 (M 4) 1/4 1/3 1 1 1/6 (M 5) 4 3 6 6 1      (8)
At the end, AHPRank computes the weighting vector w by solving the minimization problem. Thus, we find the learned weight vector w = (w M1 , w M2 , w M3 , w M4 , w M5 ) = (0.24, 0.24, 0.065, 0.065, 0.39). This vector reflects the importance of each measure with respect to the achievement of the goal (user ranking function g w ).

Now, we can use the AHP interestingness measure g w of formula 5 to rank all the patterns P provided in Table 1. The overall ranking accuracy of AHPRank on such example is of 91% where it is able to rank accurately the 5 first patterns, the seventh and the tenth ones.

Experiments

In this section, we experimentally evaluate our fast learning framework AHPRank for ranking patterns. First, we present our case study on association rules mining and different oracles simulating user-specific rankings. Then, we present the studied research questions, the experimental protocol and the obtained results.

Mining associations rules (ARs)

We evaluate our generic approach on a concrete pattern mining task, the association rule mining, one of the most important and well studied task in data mining, first introduced in [START_REF] Rakesh Agrawal | Mining association rules between sets of items in large databases[END_REF].

An association rule is an implication of the form X → Y , where X and Y are itemsets such that X ∩ Y = ∅ and Y = ∅. X represents the body of the rule and Y represents its head. The frequency of an itemset X in a dataset, denoted by f req(X), is the number of transaction of the dataset containing X. The frequency of a rule X → Y is the frequency of

the itemset X ∪ Y , that is, f req(X → Y ) = f req(X ∪ Y ).
Several interestingness measures of ARs have been introduced like support, confidence, interest factor, correlation and entropy. Tan et al. [START_REF] Tan | Selecting the right objective measure for association analysis[END_REF] made an interesting study on the usefulness of the existing measures related to the application type. In particular, they identified seven independent groups (see Table 2) of consistent measures having similar properties.

Groups

User feedback emulators

It is difficult to evaluate an interactive approach since users are scarce, for this reason we emulate the user feedback using three different objective target ranking functions:

• RAND-EMU: The user-specific ranking is equivalent to a random weighted aggregation function. For that, we generate for each measure M i a random weight w i ∈ [0, 1] such that i∈1..m w i = 1.

• LEX-EMU: The user-specific ranking follows a lexicographic order on the measures. That is, given a lexicographic order lex on M:

lex(M) = l 1 , . . . , l m , s.t., i∈1..m l i = M
Here, given two patterns (P 1 , P 2 ), P 1 is prefered to P 2 iff (l i (P 1 ) > l i (P 2 )) or (l i (P 1 ) = l i (P 2 ) ∧ l i+1 (P 1 ) > l i+1 (P 2 )) (for i = 1 to m -1).

• CHI-EMU: χ 2 as a statistical measure is a good candidate to emulate the user feedback [START_REF] Ringuest | A chi-square statistic for validating simulation-generated responses[END_REF]. χ 2 is a rather complex function to approximate with non-trivial correlations, it is also a quality measure suggested in [START_REF] Dzyuba | Learning what matters -sampling interesting patterns[END_REF].

Here, we use χ 2 as the target user-specific ranking function over ARs. Given some association rule X → Y , the χ 2 value is as follows:

χ 2 (X → Y ) = (f req(X → Y ) -f req(X)f req(Y ) N ) 2 f req(X)f req(Y ) N . ( 9
)
with N the number of transactions of the dataset.

Research questions

Our evaluation aims to answer the following four research questions:

• RQ1: Given a sample of ranked patterns, is it possible to infer the user-specific preferences over all the patterns? If yes, how much of data are required as input? How long does the learning process last?

• RQ2: How does the proposed new learning based on AHP compare with the baseline one using SVM when they are used to automatically learn user-specific ranking function? • RQ3: How effective is AHPRank from an active learning perspective? Is the sensitivity heuristic a wise choice to use in query selection?

Dataset

• RQ4: How effective is AHPRank from an interactive data mining perspective?

6.4 Experimental protocol

Implementation settings

We have implemented in Java our AHPRank approach with its two modes: the passive mode denoted by AHPRank.0 and the active mode denoted by AHPRank.1. The code is publicly available at github.com/lirmm/AHPRank. We compared our approach to the state of the art, the SVM based approach RankingSVM [START_REF] Dzyuba | Learning what matters -sampling interesting patterns[END_REF]. We denote by RankingSVM.0 the passive version and by RankingSVM.1 the active one following [START_REF] Dzyuba | Interactive discovery of interesting subgroup sets[END_REF]. All experiments were conducted on an Intel core i7, 2.4Ghz with 16Gb of RAM using an overall timeout of one hour.

Metrics

We consider three metrics to evaluate the performance of our approach:

(i) the Spearman's rank correlation coefficient ρ (sum of squared differences between learned rank L and target rank T pattern ranks over n patterns) in order to evaluate the overall ranking accuracy:

ρ = 1 - 6 i∈1..n (rank L (P i ) -rank T (P i )) 2 n(n 2 -1) , (10)
(ii) the Recall metric R@k in order to evaluate the effectiveness of our approach in identifying the top k most interesting patterns:

R@k = |{rank L (P i ) ≤ k : i ∈ 1..n ∧ rank T (P i ) ≤ k}| k (11)
(iii) CPU time needed to finish the whole learning process and the waiting time between two queries for the active mode (in seconds).

Benchmark Datasets

We selected several real-sized datasets from the FIMI repository. 2 These datasets have various characteristics representing different application domains. Table 3 reports for each dataset the number of transactions |T |, the number of items |I|, its application domain, and the number of valid rules (#Rules) corresponding to the initial rules minded using a standard association rules algorithm and without any knowledge about the user. The datasets are presented by increasing order of #Rules.

Passive learning results

In this section, we address the two first research questions (RQ1 and RQ2). To that end, we perform a 5-folds crossvalidation on #Rules for each dataset. In each fold, we randomly select 20% of #Rules to form the training data and use the remaining 80% ARs for evaluation (testing data). We have chosen this way of using k-folds cross-validation in order to see how effective are the approaches in learning from relatively small training sets. 4: Correlation results with user ranking for using the emulators.

A) Analysing the different user feedback emulators. Table 4 reports the rank correlation ρ between the user-specific ranking functions (RAND-EMU, LEX-EMU and CHI-EMU) and the seven interestingness measures. We also report VBM, the Virtual Best Measure, which returns the best rank correlation ρ provided by one of the seven measures. We observe from table 4 that given a measure, the results are chaotic. For instance, Lambda measure is highly correlated to CHI-EMU on T40 dataset (ρ = 98%) but it is weakly correlated on Connect (ρ = 29%) dataset. The same observation can be made with RAND-EMU and LEX-EMU functions. However, the theoretical construction of VBM is of a high accuracy (mean of 91%), which brings us to believe that a weighted aggregation of the selected measures can lead to a good trade-off. B) Comparing AHPRank.0 with RankingSVM.0. Table 5 is dedicated to the k-folds cross-validation results of RankingSVM.0 and AHPRank.0 using averaged rank correlation ρ, recall values (R@10% and R@1%) and CPU time in seconds averaged over the folds. Under a time contrast of one hour, RankingSVM.0 is able to deal with a training set not exceeding 100K rules, and thus we are able to compare it with our approach only on Hepatitis. In terms of ranking accuracy, we observe that RankingSVM.0 outperforms AHPRank.0 for all user feedback emulators. However, AHPRank.0 remains competitive with an acceptable accuracy. Same observations can be made in terms of recall at the 10% and 1% top of the ranking (R@10% and R@1%). AHPRank.0 is able to reach a high correlation with the user ranking functions on most of the datasets. However, we can also observe a weak correlation with CHI-EMU on Connect, where a high correlation is observed on that dataset with RAND-EMU and LEX-EMU. This stems from the fact that RAND-EMU and LEX-EMU are linear functions expressed with the given 7 interestingness measures, which explains the high accuracy. However, CHI-EMU is a complex function and the statistics extracted from Connect on the 7 measures are not sufficient to learn such a function. However, the high accuracy of RankingSVM.0 is at the expense of the running time. For a training set of 100K rules, RankingSVM.0 needs more than 15 minutes to learn. Exceeding 100K rules, RankingSVM.0 needs more than one hour, where AHPRank.0 is able to deal with 7.5M of rules in a time not exceeding 4 minutes.

In what follows, the observations and the conclusions drawn from CHI-EMU remain true for RAND-EMU and LEX-EMU. For the sake of simplicity, we only report the results on the complex function CHI-EMU. In terms of Spearman correlation ρ, figure 1 shows a discrepancy of 5% between the two approaches when the training data is not exceeding 1K. However, the gap becomes particularly important (exceeding 10%) and in favor of AHPRank.0 when the training data contains 10K and 100K rules. In terms of recall at 10% and 1%, RankingSVM.0 outperforms AHPRank.0 with a gap of 23% and 15% at R@10% and R@1% when the training data contains only 10 rules. The gap get tighter when the training data is increasing in size at R@10% (less than 5%) and remains more or less the same for R@1%. In terms of CPU time, figure 2 shows that RankingSVM.0 needs less than a second to deal with a training data not exceeding 100 rules, more than one minute for 1K rules, 13min for 10K rules, and more than 26min for 100K rules.

RAND-EMU

RankingSVM.0 AHPRank.0 ρ R@10% R@1% t(s) ρ R@10% R@1% t(
For comparison, AHPRank.0 is able to deal with a training data of a size ranged between 100 and 100K in a time ranged between 0.03 and 24.86 seconds for an overall ranking accuracy close to the one reported by RankingSVM.

Active learning results

In this section, we attempt to answer the two research questions (RQ2 and RQ3) where we compare the active learning versions of RankingSVM and AHPRank. For that end, we consider a simple process, where we ask the user some ranking queries on pairs of patterns (e.g. do you prefer P i to P j ?).

A) Evaluating the effectiveness of our sensitivity-based heuristic. Our first experiment aims to evaluate the usefulness of our Sensitivity-Based Generator (SBG) (see section 4.3). For that, we compare SBG to a Random Generator (RG), where the latter selects randomly a pair of patterns from #Rules to submit to the both learners RankingSVM.1 and AHPRank.1. For our experiment and with a human-in-the-loop, we set the number of queries (i.e., number of iterations T of algorithm 2) to a reasonable number not exceeding 20 queries. We repeat 10 times the experiment and take the average result in order to avoid the bad-luck effect with RG and the sampling step of our SBG. After few tests, we set the size of the sample X picked at line 10 of algorithm 2 to θ = 10 3 . A sample size that provide a good trade-off between time selection and the accuracy of the selected pair.

Figure 3 reports a comparison between RankingSVM.1 and AHPRank.1 in a scatter plot of 20 iterations. We report the Spearman correlation ρ and the recall at 10% and 1% of each iteration. We observe from the scatter plot that the use of SBG outperforms RG either with our approach or with RankingSVM.1.

In order to support our observation on the use of SBG, we carried out a statistical test using the Wilcoxon Signed-Rank Test, Here, the one-tailed alternative hypothesis is used with the following null hypothesis (RG is more efficient than SBG): H 0 : The accuracy using RG ≥ The accuracy using SBG. That is, the alternative hypothesis H 1 states that our SBG outperforms RG. With this statistical test, we are able to conclude that the use of SBG is more efficient than RG (H 1 accepted). Table 6 reports the p-value, the z-score and the confidence interval (CI) of each test. According to the p-value column, and except the case of (RankingSVM.1,R@10%), we have strong evidence to reject the null hypothesis. The confidence interval column shows clearly that the use of SBG is better than RG. Consequently, we will use in what follows the SBG heuristic in RankingSVM.1 and AHPRank.1.

B) Comparing

AHPRank.1 with RankingSVM.1. Table 7 shows a comparison between RankingSVM.1 and AHPRank.1 on the 5 datasets. We report ρ, R@10% and R@1% within stopping criterion T at 10, 50 and 100 queries. We also report the averaged latency time between two queries Time for RankingSVM.1, knowing that Time never exceeds the latency bound of 0.1 seconds. The findings are the same for RAND-EMU, LEX-EMU and CHI-EMU functions.

The main observation that we can draw from table 7 is that AHPRank.1 outperforms RankingSVM.1. Let us take a close look at Hepatitis results. For this dataset, AHPRank.1 is able to rank 500K patterns with an accuracy of 78% using only 10 queries (73% observed with RankingSVM.1). The accuracy increases to 95% when learning on 50 queries for AHPRank.1 and 94% for RankingSVM.1. AHPRank.1 reaches 98% of accuracy with 100 queries while RankingSVM.1 remains stable at 94%. In terms of recall values, AHPRank.1 is able to discover the most relevant patterns on the first 50K and 5K patterns (out of 500K) with an accuracy of, respectively, 78% and 66% over 10 queries (61% and 44% for RankingSVM.1). Let us now take a close look at Retail dataset. We observe that AHPRank.1 reaches a high accuracy over 10 queries and such accuracy remains stable over the following 90 queries. The RankingSVM.1 results are less impressive on Retail and particularly on the recall metric. But the main difference is on the waiting time Time , where RankingSVM.1 can keep the user waiting more than 10 seconds between two queries. Same observation can be made on the other datasets where RankingSVM.1 can be hampered by overall waiting time even with queries of size 2, where AHPRank.1 shows an instantaneous behavior (less than 0.1 seconds between two queries). This represents a limitation in the use of RankingSVM.1 especially when the learning is integrated to an interactive data mining process, where a reasonable latency time for a human user is around few seconds [START_REF] Lallemand | Enhancing user experience during waiting time in hci: Contributions of cognitive psychology[END_REF].

Interactive learning results

In this section, we address the last research questions RQ4. In addition to the active learning results, which are part of the interactive perspective with a human-in-the-loop, we conduct two more experiments by focusing on the hazard characteristics linked to the presence of a human in the learning process.

Our first experiment aims to evaluate the robustness of our approach in front of a human likely to make mistakes. To simulate such situations involving incorrect user feedback, we pick randomly (with a percentage ratio Err) a set of queries and we swap the user preference. That is, a user that prefers a pattern P i to P j will make a mistake by preferring P j to P i with a probability Err.

Figure 4 reports a comparison between RankingSVM.1 and AHPRank.1 under mistakes present with a probability Err varying from 0% to 40%. The reported results are averaged on 10 runs and on the whole set of datasets on learning CHI-EMU and by submitting 20 queries to the user. We observe that AHPRank.1 is quite stable and robust even with 40% of mistakes (8 mistakes out of 20). The overall correlation between the learned function and the user one ρ is at 77% without mistakes and becomes 70% under Err= 40%. However, RankingSVM.1 is stable till Err= 20% and then, the accuracy is highly impacted where ρ decreases from 71% to 54%. In terms of recall, we observe a decline not exceeding 2% at R@10% and 8% at R@1% under AHPRank.1. Using RankingSVM.1, the decline is exceeding 10% at R@10% and R@1%. In terms of CPU time and between two queries, we observe a waiting time ranged between 6 and 12 seconds under RankingSVM.1, where under our approach is never over 0.02 seconds.

Our second experiment aims to evaluate the robustness of our approach in front of an undecided user that starts with a set of preferences A in mind to finish with preferences B. Here, the initial user preferences A are biased along the presented patterns till being the user more comfortable with preferences B. To simulate such situations where the user target function is changing during the learning process, we conduct an experiment where we start with LEX-EMU as a target to learn and after x queries, we swap to RAND-EMU where the learning process takes (20 -x) more queries (we coined it LEX2RAND target). Note that we choose a swap from LEX-EMU to RAND-EMU because of the two functions are linear. For a total number of 20 queries, we compare RankingSVM.1 and AHPRank.1 on LEX2RAND(x) target (x ∈ {0, 5, 10}). Note that with x = 0, LEX2RAND(0) is equivalent to RAND-EMU. results of 10 runs on all datasets over 20 queries. The main observation that we can draw is that AHPRank.1 is stable in front of a changing linear function to learn even with a changeable mind in the middle of the learning (10 out of 20 queries). However, a target alteration during the learning process can drastically impacts the accuracy of RankingSVM.1 (decline of 44% in terms of ρ). In terms of CPU time, our approach is 50 times faster than RankingSVM.1. To sum up, our main finding is that AHPRank represents a good trade-off between ranking accuracy and running time.

AHPRank is able to reach a good overall ranking accuracy within a time being linear on the size of the training data and thus, not exceeding few seconds, which makes it suitable for industrial exploitation.

Conclusion

We presented a generic and efficient framework for learning pattern ranking functions using a multicriteria decision making method based on AHP. The proposed AHPRank algorithm can be applied in both passive and active learning modes. It requires the user to rank subsets of patterns according to her preferences. Our approach exploits the learned weights to aggregate all the measures into a single ranking function, using a weighted linear formulation. The resulting aggregation function was experimentally and statistically proven to be as close as possible to the user ranking. We applied this framework to the case study of Association Rules Mining, for which experiments showed that AHPRank algorithm is able to learn the ranking function efficiently compared with the results of state-of-the-art learning approaches.

2

 2

Algorithm 2

 2 AHPRank(M, S, P, θ, T ) In :Set of measures M = {M 1 , . . . , M m }; Passive mode (S = ∅): Set of user-ranked patterns S = {S 1 , . . . , S n }; Active mode (S = ∅): Collection of patterns P; Sample size θ ; Number of iterations T ;

4. 4

 4 Complexity Analysis Proposition 1 (Time complexity) Given a bounded number of interestingness measures, Algorithm 2 runs in O(n k) in passive learning and in O(n) in active learning.

Figure 1 :

 1 Figure 1: Learning accuracy comparison between RankingSVM.0 and AHPRank.0 learning CHI-EMU on different training data size.

Figure 2 :

 2 Figure 2: CPU time comparison between RankingSVM.0 and AHPRank.0 learning using CHI-EMU emulator on different training data sizes averaged overall datasets.

Figure 5 Figure 4 :

 54 Figure 4: Learning under mistakes (20 queries).

Figure 5 :

 5 Figure 5: Learning under swaps (20 queries)

  // sort P according to g w P air ← ∅; σ min ← +∞; for i ∈ 1..|P | : P i , P i+1 ∈ P do

	score ← σ(P i , P i+1 );
	if score < σ min then
	σ min ← score;
	P air ← {P i , P i+1 };
	end
	end
	return P air;

Function 3 BasedHeuristic(P, w, M) In :Collection of patterns P; Weight vector w; Set of measures M; P ← Sort(P, w) ;

Table 1 :

 1 shows the ∆ user S M 1 -rank M 2 -rank M 3 -rank M 4 -rank M 5 -rank g Running example with 10 patterns and 5 measures.

	w -rank

Table 2 :

 2 Independent Subjective Measure GroupsFor our evaluation, we pick one measure per group to have 7 measures representing an independent set of measures (see measures in bold in table2).

		Measures
	1	Yules Q, Yules Y, Odds Ratio
	2	Cosine, Jaccard
	3	Laplace, Support
	4	φcoefficient, CollectiveStrength, piatetskyShapiro's
	5	Goodman Kruskal's, Gini Index
	6	Interest factor,added value, Klosgen K
	7	certainty factor, Mutual Information, Cohen's κ

Table 3 :

 3 Dataset Characteristics.

		|T |	|I|	Density(%)	Type of Data	#Rules
	Hepatitis	137	68	50.00	Disease	0.5 M
	Connect	67,557	129	33.33	Game steps	1 M
	Mushroom	8,124	119	18.75	Species of mushrooms	1.5 M
	T40	100,000	1,000	4.20	Synthetic dataset	2 M
	Retail	88,162	16,470	0.06	Retail market basket data	2,5 M
					T40:T40I10D100K

Table 5 :

 5 5-folds cross-validation results (passive learning).

	s)

Table 6 :

 6 Wilcoxon Signed-Rank Test (RG vs SBG).

		1
		0.9
		0.8
	Random Generator	0.5 0.6 0.7
		0.4
		0.3
				RankingSVM.1:	ρ	R @10	R @1
				AHPRank.1:		ρ	R @10	R @1
		0.2
		0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9	1
				Sensitivity-Based Generator
		Figure 3: Random vs Sensitivity-Based Patterns Generator.
	Approaches	Metrics		p-value		z-score	CI
		ρ				.00226		-2.8373	99%
	RankingSVM.1	R@10%			.12302		-1.1573	70%
		R@1%				.06301		-1.5306	90%
		ρ				.00034		-3.3973	99.9%
	AHPRank.1	R@10%			.00205		-2.8746	99%
		R@1%				.00139		-2.9866	99%

Table 7 :

 7 Qualitative evaluation of RankingSVM.1 vs AHPRank.1.

	10 Queries

When the components of A are exactly obtained as ratio between weights.

fimi.uantwerpen.be/data/


Pascal Andre

Gilles Ardourel

Christian Attiogbé

Protocoles d'utilisation de composants : spécification et analyse en Kmelia