Adrien Revault D'allonnes

Marie-Jeanne Lesot
email: marie-jeanne.lesot@lip6.fr

Formalising Information Scoring in a Multivalued Logic Framework

Keywords: trust, information quality, many-valued logic, information scoring, trust building

This paper addresses the task of information scoring seen as measuring the degree of trust that can be invested in a piece of information. To this end, it proposes to model the trust building process as the sequential integration of relevant dimensions. It also proposes to formalise both the degree of trust and the process in an extended multivalued logic framework that distinguishes between an indifferent level and the actual impossibility to measure. To formalise the process, it proposes multivalued combination operators matching the desired behaviours.

Introduction

Amongst the diverse facets of information scoring, trust holds a central role. Qualifying the degree of trust that can be put in a piece of information can mean either evaluating its certainty -i.e. the reality of the fact it reports [START_REF]NATO: Annex to STANAG2022[END_REF][START_REF] Demolombe | Reasoning about trust: a formal logical framework[END_REF][START_REF] Lesot | Proposition of a semi-automatic possibilistic information scoring process[END_REF] or the extent to which the rater is convinced, based on the process by which he forms an opinion about a hitherto unknown piece of information [START_REF] Besombes | An extension of STANAG2022 for information scoring[END_REF][START_REF] Revault D'allonnes | An architecture for the evolution of trust: Definition and impact of the necessary dimensions of opinion making[END_REF].

Existing models differ in the dimensions they take into account to assess the degree of trust but also in the formal paradigms they use to represent it. Among the existing criteria, some examples are reliability, competence, sincerity, intention of the source, credibility, understood as confirmation by other sources, or plausibility, defined as likelihood with respect to a priori knowledge of the piece of information [START_REF]NATO: Annex to STANAG2022[END_REF][START_REF] Demolombe | Reasoning about trust: a formal logical framework[END_REF][START_REF] Lesot | Proposition of a semi-automatic possibilistic information scoring process[END_REF][START_REF] Besombes | An extension of STANAG2022 for information scoring[END_REF][START_REF] Revault D'allonnes | An architecture for the evolution of trust: Definition and impact of the necessary dimensions of opinion making[END_REF][START_REF] Pichon | Relevance and truthfulness in information correction and fusion[END_REF].

Information scoring as evaluation of trust has been formalised using both symbolic and numeric frameworks to evaluate each dimension and combine them using various aggregation operators to yield the final degree of trust. The original military model uses two discrete graded scales, respectively measuring source reliability and information credibility [START_REF]NATO: Annex to STANAG2022[END_REF]. The aggregation is simply a concatenation of the two resulting symbols. This leads to difficulty in comparisons, hindering the evaluation's legibility [START_REF] Capet | Information evaluation in the military domain: Doctrines, practices and shortcomings[END_REF]. Other models present the degree of trust as a single numerical value, a coefficient between 0 and 1, in either possibility [START_REF] Lesot | Proposition of a semi-automatic possibilistic information scoring process[END_REF] or evidence [START_REF] Pichon | Relevance and truthfulness in information correction and fusion[END_REF][START_REF] Cholvy | Information evaluation in fusion: a case study[END_REF][START_REF] Cholvy | Evaluation of information reported: a model in the theory of evidence[END_REF] theory frameworks. In the former, for instance, the dimensions are evaluated using possibility distributions, their aggregation relies on discounting, conjunctive and reinforcement operators [START_REF] Lesot | Proposition of a semi-automatic possibilistic information scoring process[END_REF].

This paper proposes to formalise information scoring in an extended multivalued logic framework: first off, as in the numerical approaches mentioned above, a unique degree is returned; second, as in the symbolic approach, it is defined on a discrete graded scale, which is further clarified with linguistic labels specifying the degrees' meaning, for all measured quantities [START_REF] Revault D'allonnes | An architecture for the evolution of trust: Definition and impact of the necessary dimensions of opinion making[END_REF]. Indeed, multivalued logic offers formal tools and concepts [START_REF] Akdag | A qualitative theory of uncertainty[END_REF] which allow these improvements of the model's legibility. The proposed extension of the multivalued framework arises in the introduction of an additional degree modelling the case where a dimension cannot be quantified, through lack of knowledge, thus distinguishing it from the case where the evaluation leads to a neutral, indifferent value.

Each dimension mentioned above is individually evaluated in this extended multivalued framework. The resulting level of trust is also measured in this framework by successive integration of the dimensions: this paper proposes to model the trust building process as the sequential projection of the activation along selected dimensions on the current level of trust. To achieve this, the required properties for information scoring process projection operators are discussed and corresponding functions are proposed.

The paper is organised as follows: Section 2 presents the trust building process as the sequential projection of dimensions on the level of trust. Section 3 presents the proposed extended multivalued logic framework that distinguishes between lack of knowledge and indifference. Sections 4 and 5 are dedicated to the two types of combination operators identified. The paper then concludes with some directions for future work.

A Model of the Trust Building Process

This section presents a general model of the process through which trust in a piece of information is constructed. The principle of this model lies in updating the trust value by the sequential projection of the dimensions which partake in its evaluation. In particular, this section focuses on the attributes which will be formalised in the following sections, such as the influence of dimension projection, leading to specifications for the projection operators, as well as the difference between unknown and neutral levels.

Trust Building as a Sequence of Projections

The model described in this paper dynamically measures trust as a score whose value shifts with the consecutive consideration of different dimensions. These factors are projected on the current score, resulting in an updated trust value: trust-building is modelled as the consecutive integration of answers to different questions. This principle is illustrated in Figure 1, discussed further below, where the shaded disks represent the current level of trust and the arrows four factors consecutively influencing its evolution. Obviously, the questions should not be redundant, nor should they be dependent. They should span different levels of specificity, from the most general, that is depending only on the context, not on the considered piece of information, to the particular, directly dependent on the informational content. This principle is put in use in [START_REF] Revault D'allonnes | An architecture for the evolution of trust: Definition and impact of the necessary dimensions of opinion making[END_REF], where the dimensions are selected so as to consecutively answer the following questions: 'Who is telling me?', which corresponds to source reliability; 'What does he know about the topic?', to source competence; 'How likely does it seem?', to information plausibility; 'Is anyone else reporting it?', to information credibility. The first two relate to the source where the other two depend on the informational content. Furthermore, the evaluation of the source's reliability, how trustworthy the source is, is constant, whatever the considered piece of information, where competence depends both on the source and the topic, so is more specific to the piece of information. Plausibility, taken here as compatibility with the rater's knowledge, is contextual and subjective in that it depends both on the piece of information and the rater. Credibility is completely contextual, since it is taken as a degree of confirmation of the considered piece of information. The four dimensions therefore span the divide from source to information, general to contextual and subjective to objective, ensuring they are neither redundant nor dependent.

Combining the Dimensions: Influence of the Projections

Once the dimensions participating in the evaluation are selected, one must look at how their intensities are combined and the order in which they are considered. In order to model the trust building process, we propose to order the dimensions from the most immutable to the least, that is from the most general to the most specific, both content and contextwise. The idea behind this ordering is that the evaluation of trust starts with global dimensions and is progressively corrected with respect to the specifics of the considered piece of information.

These consecutive corrections entail that most projections have an abating influence. For instance, the model presented in [START_REF] Revault D'allonnes | An architecture for the evolution of trust: Definition and impact of the necessary dimensions of opinion making[END_REF] and briefly summarised above suggests that the evaluation starts with source reliability, the most general dimension as its value stays the same regardless of the content. It is then adapted to the assertion by the projection of source competence, this adaptation resulting in either a lower updated value or, at most, leaving it unchanged: faced with a trustworthy source, the fact that he is a specialist on the topic should not increase one's trust. Rather, if he were to talk about something which he knew nothing about, would one's doubts begin to rise. Similar arguments also apply to information plausibility. For this reason, an abating operator is needed to project most dimensions onto trust.

However, a second type of operator is necessary to model credibility, as this particular dimension can have both an increasing and weakening influence on the trust level. Indeed, the final step in a trust building process is to try to cross-check the informational content, i.e. to find confirmation or invalidation. Credibility appears in most existing models [START_REF]NATO: Annex to STANAG2022[END_REF][START_REF] Lesot | Proposition of a semi-automatic possibilistic information scoring process[END_REF][START_REF] Revault D'allonnes | An architecture for the evolution of trust: Definition and impact of the necessary dimensions of opinion making[END_REF], usually, as the final projected dimension. This is in agreement with the specificity ordering proposed above, as cross-checking is both content and context dependent. Another argument for the credibility being the final step in the process is that its projection depends on the score of the confirmation which, thus, needs to have already been computed. Regarding credibility's influence, confirmations increase the trust level where invalidations weaken it, which explains the need for a specific cross-checking operator rather than the abating operator which, by definition, is one-way.

These two types of operators are illustrated in Figure 1, where the colour intensity of each arrow corresponds to the level to which each dimension is measured. The second and third sets of arrows, which all -except for the ones coming from the disks labelled 0, discussed in the following subsection -point downwards, are examples of abating operators. The final set of arrows, in both directions, is an example of the cross-checking operator.

Preserving the Expressiveness of Ignorance

The proposed sequential process relies on evaluations being made. However, there may be situations in which it is impossible to measure a particular dimension. It may, for instance, be impossible to evaluate an as yet unknown source's reliability, for lack of knowledge. Such a situation should not be confused with one in which a source is 'neither trustworthy nor untrustworthy', which conveys some knowledge on the matter. The latter is usually in the middleground of the evaluation scale. Distinguishing the two cases is necessary when projecting dimensions, as ignorance should not beget knowledge: if a dimension cannot be measured, its projection should not influence the outcome.

For this reason, a specific level is used in [START_REF]NATO: Annex to STANAG2022[END_REF], representing the impossibility to measure. Likewise, in the example shown in Figure 1, this partly accounts for the horizontal arrows: projection of an impossible to measure dimension does not change the score, regardless of its current value. In addition, the disks labelled 0 represent a situation where the level of trust is unknown, i.e. none of the previous dimensions have been measured. In the absence of knowledge, the first dimension which can be evaluated moves the score out of ignorance. Note that, if evaluation of trust was possible at any stage, it remains possible in all subsequent stages. Thus, no arrow points to a disk marked 0.

Extended Multivalued Logic Framework

The multivalued logic paradigm is based on a symbolic, discrete truth scale and offers a formal framework to manipulate and combine these degrees [START_REF] Akdag | A qualitative theory of uncertainty[END_REF]. It constitutes a candidate framework to model the trust building process described in the previous section, addressing the clarity and legibility concerns: the discrete scales used both for measuring the dimensions and the level of trust, such as that presented in Figure 1, can be mapped to multivalued logic degrees. Moreover, multivalued logic combination operators can help express trust as a projection of dimensions in a single degree. However, to fully express all aspects of the model, the multivalued logic paradigm needs to be able to distinguish between an indifferent and an unknown degree.

After having recalled the essential characteristics of multivalued logic, this section describes the proposed extension and discusses its properties.

Multivalued Logic

Multivalued logic models reasoning using the M truth degrees of a totally ordered set L M = {τ 0 , . . . , τ M -1 }, where τ α ≤ τ β ⇔ α ≤ β, coupled to an involutive negation satisfying De Morgan's laws. The ordering property guarantees all degrees in L M are comparable. They span, at a granularity varying with M , the different levels of veracity they represent from τ 0 , meaning 'false', to τ M -1 , for 'true'. The switch between the two appears around the middle value τ M -1 2 , usually forced into the chosen scale by choosing an odd M . Furthermore, all τ α 's come with a semantic label increasing their legibility.

On top of the expressiveness and legibility of the truth scale, multivalued logic offers tools to reason with truth degrees, through operators that generalise conjunction, disjunction or implication [START_REF] Akdag | A qualitative theory of uncertainty[END_REF]. It also has operators for symbolic arithmetic, beyond a purely logic interpretation [START_REF] Seridi | Approximate Reasoning for Processing Uncertainty[END_REF].

Introduction of an Ignorance Degree: τ ?

Discrete scales used for information scoring can be mapped to multivalued logic degrees. In accordance with what was discussed in the previous section and in Section 2.3, the indifferent value can be mapped to τ M -1 2 , leaving the question of representing the absence of knowledge.

We propose to extend the multivalued logic framework by introducing an additional degree, denoted τ ? , in order to distinguish between ignorance and indifference. We propose to define this degree by the following properties, where denotes any multivalued operator:

1. τ ? ∈ L M 2. ∀τ α ∈ L M , τ ? τ α = τ α τ ? = τ α 3. ¬τ ? = τ ? 4. τ ? τ ? = τ ?
The first property sets τ ? apart from other degrees, not submitting it to the same ordering constraints as τ α ∈ L M : an element whose truth cannot be evaluated cannot be compared to an element whose truth is known, no matter how true. Therefore, we propose to define τ ? as an exception to the total order rule and of a different nature than other degrees. The second property defines τ ? as a neutral element for all operators, in particular for both conjunctions and disjunctions, which implies it does not preserve the order on L M . The last two properties define the behaviour of τ ? when combined with itself.

It can be shown easily that τ ? preserves some essential properties of a De Morgan algebra, specifically the involution of negation and De Morgan's laws, but contradicts the axioms of identity, complement as well as the absorption law.

Characteristics of the Extended Multivalued Framework

We propose that truth be evaluated on L M extended with τ ? , which we write L e M = L M ∪ {τ ? }. This section shows how it offers an essential gain in expressiveness, illustrating it in the information scoring application.

As already stated, τ ? is not comparable to any degree, which may seem contradictory with the sought qualities of truth degrees. However, the localised loss of comparability in L e M is not an issue as τ ? never needs be compared to any degree, and, in fact, satisfies an expectation: a fact whose truth is given as τ ? is neither more, nor less true than any other. For this same reason, the introduction of τ ? places the comparison between a 'half true' fact and another back in its rightful place in L M 's semantic hierarchy.

When constructing or modifying a logic framework, one should take heed of the impact on the consistency of the resulting system, i.e. the impossibility to infer a contradiction. In the case of multivalued logics, this property is already relaxed since the laws of excluded middle and noncontradiction do not hold. Now adding τ ? does not introduce inconsistency: because τ ? is defined as a neutral element for all combination operators, any inconsistency proved after its inclusion will persist should it be removed.

Multivalued Abating Combination Operator

The previous section defined the extended formal framework L e M . This section and the next propose operators for manipulating degrees in L e M and, more specifically, operators exhibiting the properties detailed in Section 2 to model trust building. These operators are mappings L e M × L e M -→ L e M with current score and evaluation of the dimension for inputs and updated score for output.

This section focuses on the abating operator whose necessity is detailed in Section 2. A formal description of the required properties is given before a corresponding function is defined.

Formal Description of the Required Behaviour

The properties needed for an abating operator F :

L e M × L e M -→ L e M are: -∀τ α , τ β ∈ L M F (τ α , τ β ) ≤ τ α -∀τ α ∈ L e M F (τ ? , τ α ) = F (τ α , τ ? ) = τ α -∀τ α , τ β , τ γ ∈ L M if τ α ≤ τ β , then F (τ α , τ γ ) ≤ F (τ β , τ γ )
and F (τ γ , τ α ) ≤ F (τ γ , τ β ) The first property guarantees the abating behaviour, by imposing the updated value is at most equal to the current value τ α . The second property defines τ ? as a neutral element of F : when the current score is still unknown, the value of the projected dimension directly determines the updated score. Conversely, when the level of the dimension cannot be measured, the score is not updated. The final property ensures the operator is increasing in both its arguments. Indeed, the higher the current score, the higher the updated one, for any correction; reciprocally, for any given level of trust, the more the dimension is activated, the higher the updated score.

Proposed Operator

In order to satisfy the properties listed in the previous subsection, one could consider extending t-norms. Indeed, t-norms, in the regular multivalued case, satisfy the first and third properties, leaving only the special case of τ ? . However, t-norms have other properties, such as commutativity and associativity, which are superfluous in this particular context and would lead to unwanted constraints, limiting the expressiveness of the model. Furthermore, even if these properties were accepted, the different nature of the arguments, current score vs. dimension level, makes them inconsistent.

We, therefore, propose to define a new operator, illustrated in Figure 2, based on a set of parameters κ γ α ∈ L M that define transition thresholds between a current score τ α and its updated value τ γ :

F (τ α , τ β ) =    min{τ γ ∈ L M |τ β κ γ α } if τ α , τ β ∈ L M τ β if τ α = τ ? τ α if τ β = τ ?
The first line sets the conditions for the transition from τ α to τ γ . The other cases describe τ ? as a neutral element for both arguments. Note that consistency with the proposed model imposes constraints on the parameters κ γ α : to guarantee the function is increasing, they must be ordered, so that if τ γ ≤ τ δ , then κ γ α ≤ κ δ α . However, these ordering constraints on κ γ α are imposed for a given value of τ α but constraints of the form κ β α = κ γ α ⊕ κ β γ , where τ γ is an intermediate value between τ α and τ β and ⊕ a suitable sum operator [START_REF] Seridi | Approximate Reasoning for Processing Uncertainty[END_REF], are not required: going directly from τ α to τ β need not be equivalent to successive transitions from τ α to τ γ and from τ γ to τ β .

Multivalued Cross-checking Combination Operator

Two remarkable properties of credibility projection require a dedicated operator: first it can both weaken or increase the level of trust. Second, it involves an additional argument: besides the usual current score and dimension level, it depends on the current evaluation of the confirmation or invalidation. Indeed, an absolute confirmation should obviously increase the level of trust. However, if said corroboration has a low trust value, its influence should be less than that of a highly trusted confirmation.

Formal Description of the Required Behaviour

The cross-checking operator G is therefore a mapping, G : L e M × L e M × L e M -→ L e M , satisfying the following properties:

-G is increasing in all 3 arguments τ ? is a neutral element for all 3 arguments

-∀τ α , τ β , τ γ ∈ L M G(τ α , τ β , τ γ ) ≥ τ α if τ β ≥ τ M -1 2 G(τ α , τ β , τ γ ) ≤ τ α if τ β < τ M -1 2
The arguments for the monotonicity of operator G are similar to the ones explaining F 's, as given in Section 4.1. The third property outlines the change of behaviour between confirmations (where credibility is in the top half of the scale:

τ β ≥ τ M -1 2
), for which G exhibits an increasing trend, and invalidations which have a weakening effect on the trust level.

Proposed Operator

Based on the properties required of the cross-checking operator, we propose the following function, illustrated in Figure 3:

G(τ α , τ β , τ γ ) =    τ α if τ β = τ ? Fi (τ α , g(τ β , τ γ )) if τ β < τ M -1 2 Fc (τ α , g(τ β , τ γ )) otherwise
As detailed below, G's increasing and weakening trends are described by functions Fc and Fi respectively.

In both cases, the range of influence is determined by a weighted credibility, defined as the aggregation of the degree of confirmation/invalidation, as measured by the credibility dimension τ β , and the trust level of the cross-checking

∀τ α , τ β ∈ L M g(τ α , τ β ) ≤ τ α if τ α ≥ τ M -1 2 g(τ α , τ β ) ≤ ¬τ α if τ α < τ M -1 2
Indeed, the trust level of a confirmation can only weaken the impact of the credibility projection, along the same lines as the abating operator. The case of invalidation is similar, except for the negation of the credibility, which only serves to allow a symmetric behaviour. The monotonicity of g must satisfy the following constraints, whose formal description is omitted for lack of space: g must be increasing (resp. decreasing) in its first argument for confirmations (resp. invalidations); g must be increasing in its second argument. Finally, τ ? must be an absorbing element for both arguments: if either cannot be evaluated, neither can the weighted credibility.

The Fi operator, which controls the abating influence of weighted invalidations, is similar to the general abating operator defined in Section 4, its only specificity being its monotonicity in its second argument. Indeed, Fi (τ α ,τ β ) increases whereas F (τ α , τ β ) decreases, when τ β grows. Consequently, constraints on κ γ α , and their comparisons with τ β , are reversed in Fi defined similarly to F :

Fi (τ α , τ β ) =    min{τ γ ∈ L M |τ β ≥ κ γ α } if τ α , τ β ∈ L M τ α if τ β = τ ? τ β if τ α = τ ?
An example of such an operator is represented in the bottom half of Figure 3. The Fc operator, which controls the emphasising influence of weighted confirmations, satisfies properties similar to that of F , except for the first one which becomes ∀τ α , τ β ∈ L M , Fc (τ α , τ β ) ≥ τ α , to express the emphasising influence. We thus propose to define:

Fc (τ α , τ β ) =    max{τ γ ∈ L M |τ β ≥ κ γ α } if τ α , τ β ∈ L M τ α if τ β = τ ? τ β if τ α = τ ?
An example of such an operator is represented in the top half of Figure 3. Note that the definitions of the Fi and Fc functions are independent, it is not required that κ γ α = κ α γ to allow for different sentivities to contradictory arguments.

Conclusion and Future Works

This paper proposes a sequential model for a trust building process, as the consecutive projection of dimensions on the current evaluation, as well as its formal and operational transposition in an extended multivalued logic framework. The latter offers a way to distinguish between indifference and ignorance, which is critical to adequately represent trust building. From the characterisation of the desired properties for the required projection operators, it defines special combination operators and gives the formal expression of suitable functions. Future works will include the implementation of the proposed model and the definition of an evaluation protocol to lead an experimental study of user response to the proposed model. On a more formal level, another perspective lies in the theoretical study of the logical reasoning properties offered by the proposed extended multivalued logic L e M , beyond the degree manipulation tools explored in this paper. Regarding information scoring, future works will aim at proposing tools allowing for the integration of the dynamics of trust building, like the influence on the evolution of trust of alternating confirmations and invalidations.

Fig. 1 .

 1 Fig. 1. Sequential projection of dimensions on trust

Fig. 2 .

 2 Fig. 2. An example of F (τα, τ β ) ignoring τ ? : the degrees of L5 represent possible values of the current score, the arrows labelled with κ γ α transitions from τα to τγ

Fig. 3 .

 3 Fig. 3. An example of G, τ β (τα, τγ), in L5


Marc Damez
email: marc.damez@lip6.fr

Marie-Jeanne Lesot
email: marie-jeanne.lesot@lip6.fr

Adrien Revault D'allonnes
email: adrien.revault-d'allonnes@lip6.fr

Dynamic Credit-Card Fraud Profiling

Keywords: Incremental Clustering, Data-Streams, Heterogeneous Data, Bank Fraud, Credit Card Security

HAL is

Introduction

Credit and debit cards have become ubiquitous modes of payment, which have brought with them the important issue, both for banks and card-holders, of card fraud [START_REF]Banque de France: Annual Report of the Observatory for Payment Card Security[END_REF]. The ensuing economic losses have motivated a vast field of study in the machine learning community [START_REF] Bolton | Statistical fraud detection: a review[END_REF][START_REF] Phua | A comprehensive survey of data miningbased fraud detection research[END_REF][START_REF] Laleh | A taxonomy of frauds and fraud detection techniques[END_REF], in particular concerned with electronic business, both for supervised -fraud detection-and unsupervised -fraud characterisation-learning tasks.

This paper considers the latter, i.e. the identification of ever changing groups of similar frauds. This problem is challenging in its twofold dynamic nature. First, fraudsters are inventive and continuously adapt to circumvent anti-fraud policies, elaborating new types of frauds. Second, the data are constantly incoming, building a never-ending stream. Finally, the very nature of the heterogeneous data, described by both numeric and categorical attributes, renders part of the classic methods unusable.

In this paper, we propose a methodology to process incoming streams presenting these characteristics and study the derived profiles and the dynamics of their contents. Contrary to most clustering tasks, the method proposed in this paper is less interested in summarising the data into abstract and possibly non-existent prototypes than it is in identifying precisely observable behaviours, those which are most likely to belong to an actual type of fraudster. The proposed method is tested on a real dataset representing one year of frauds

The paper is organised as follows: after outlining related work in Section 2, we present in Section 3 the methodology we propose. Section 4 analyses the profiles obtained using this methodology on a real dataset corresponding to a one year fraud-stream.

Related Work

Data representing credit-card frauds combine two characteristics that both require specific clustering algorithms, namely their data-stream and heterogeneous nature. This section outlines algorithms that have been proposed to deal with either data type.

Clustering Data-Streams

Data-Stream Characteristics: As opposed to classic data, data-streams are characterised by their production mode: the dataset is incrementally built, which means that not all data are available at once. They usually lead to very large datasets having restrictive characteristics which require specific algorithms to perform data-mining [START_REF] Aggarwal | Data Streams: Models and Algorithms[END_REF].

Indeed, data-streams first demand incremental algorithms that process data progressively, incorporating them as they come in to update the learnt model. Moreover, because of their production mode as well as memory constraints imposed by their quantity, data-streams usually require single-pass algorithms.

Another characteristic of data-streams is their dynamic feature: apart from the data arriving progressively, their underlying distribution generally evolves with time. This is in contradiction with the hypothesis of identically distributed data most classic data-mining algorithms rely on.

General Principles:

The main existing methods for clustering such datastreams belong to the framework of incremental clustering. First introduced to address the issue of very large datasets, these algorithms decompose the dataset into samples of manageable size. They consist in iteratively processing each sample individually and merging the corresponding partial results into the final partition. In the case of very large datasets, samples are automatically extracted, e.g. randomly drawn so as to fit in memory. In the case of data-streams, where samples are imposed by the time-line, and defined as the set of data becoming available in a given time interval, samples can be seen as data buffers.

Incremental clustering algorithms can be divided according to the way the partial results are merged, this fusion being either progressive or final. Progressive fusion means including, in the clustering step of a given sample, the results from the previous steps. Final fusion is performed at the end, when all samples have been processed. As detailed below, the same distinction can be applied to data-stream clustering algorithms.

Online Clustering: Online clustering algorithms are incremental approaches with progressive fusion: the previously seen data are summarised by extracted clusters, possibly weighted by their sizes, and this summary is processed together with the next sample.

This approach has been applied to most classic clustering algorithms, e.g. leading to incremental variants for k-means [START_REF] Farnstrom | Scalability for clustering algorithms revisited[END_REF], fuzzy c-means [START_REF] Hore | Single pass fuzzy c means[END_REF], fuzzy cmedoids [START_REF] Labroche | New incremental fuzzy c medoids clustering algorithms[END_REF] or dbscan [START_REF] Ester | Incremental clustering for mining in a data warehousing environment[END_REF]. Likewise stream [START_REF] O'callaghan | Streamingdata algorithms for high-quality clustering[END_REF], which is one of the first algorithms dedicated to data-streams, achieves the same kind of result with memory size limitations and theoretical guarantees on the result quality.

Two-level Approaches: The online approaches are said not to be able to fully adapt to the dynamics of the data, as they do not question previous cluster merges [START_REF] Aggarwal | A framework for clustering evolving data streams[END_REF]. Therefore, two-level approaches reject progressive fusion and postpone the fusion step until the final partition is required by the user. More precisely, they combine an online part, updating compact representations of the data seen so far, with an offline part, which extracts a final partition from this compact representation. The offline step does not take into account the temporal component: no comparison can be made between two consecutive demands of the user. The two steps are also respectively called micro and macro-clustering. Some approaches in this framework apply the same clustering algorithm to both steps, e.g. fuzzy c-means [START_REF] Hore | Online fuzzy c means[END_REF] or fuzzy c-medoids [START_REF] Labroche | New incremental fuzzy c medoids clustering algorithms[END_REF]. The centres or medoids obtained from each data buffer are in turn clustered.

Other methods perform a preclustering step of a different nature than the final one, e.g. incrementally updating quantities to compute cluster statistics such as cluster average or standard deviation. This approach is exemplified by birch [START_REF] Zhang | Birch: an efficient data clustering method for very large databases[END_REF], that incrementally builds a compact representation of the dataset, based on structured summaries that optimise memory usage along user-specified requirements. Clustream [START_REF] Aggarwal | A framework for clustering evolving data streams[END_REF] generalises the representation, taking into account the temporal dimension in the precluster description. These algorithms try to add a new data point to one of the preclusters. If this fails, then a new cluster is created to represent the data point. To maintain the memory size, either one of the previously identified clusters is deleted, e.g. based on a recentness criterion, or two clusters are merged, e.g. the two most similar.

This principle has also been applied to density-based clustering [START_REF] Cao | Density-based clustering over an evolving data stream with noise[END_REF]: it also combines online micro-cluster maintenance with offline generation of the final clusters with a variant of dbscan. Two types of clusters are distinguished: core and outlier-clusters, which can become core-clusters if they reach a size threshold. To prevent memory overload, the outlier-clusters are periodically pruned.

The proposed methodology described in the Section 3 is similar to this one, with two main differences, as detailed below: first it relies on partitioning and not density-based clustering. Second, it uses a different representation of the so-called outlier clusters.

Clustering Heterogeneous Data

Heterogeneous data are defined as data described by both numeric and categorical attributes. The presence of categorical attributes rule out the computation of average values and, therefore, the usage of all mean-centred clustering techniques, in particular the very commonly applied k-means and its variants.

Two main approaches can be distinguished: first, so-called relational methods which rely on the pairwise dissimilarity matrix (e.g. pairwise distances) and not on vector descriptions of the data. This type of approach includes hierarchical clustering methods, density-based methods [START_REF] Sander | Density-based clustering in spatial databases: the algorithm DBSCAN and its application[END_REF] as well as relational variants of classic algorithms [START_REF] Hathaway | Nerf c-means: non euclidean relational fuzzy clustering[END_REF][START_REF] Hathaway | On relational data versions of c-means algorithms[END_REF].

On the other hand, medoid-based methods [START_REF] Kaufman | Finding groups in data, an introduction to cluster analysis[END_REF][START_REF] Krishnapuram | Low complexity fuzzy relational clustering algorithms for web mining[END_REF] constitute variants of the mean-centered methods that do not define the cluster representative as the average of its members, but as its medoid, that is, the data point that minimises the, possibly weighted, distance to cluster members.

Linearised Fuzzy c-Medoids

The linearised fuzzy c-medoids algorithm [START_REF] Krishnapuram | Low complexity fuzzy relational clustering algorithms for web mining[END_REF], written l-fcmed hereafter, is a scalable medoid-based clustering algorithm: it can process data that are both in vast amounts and heterogeneous. Moreover, being a fuzzy variant, it offers properties of robustness and independence from random initialisation. We present it in greater detail here because the proposed method described in Section 3 depends on it.

The algorithm's inputs are D = {x i | i = 1, . . . , n} the dataset to be clustered, d the metric used to compare data, c the desired number of clusters, m the fuzzifier which sets the desired fuzziness and p the size of the neighbourhood in which medoid updates are looked for.

After initialisation of the cluster centres as c data in D the algorithm alternately updates memberships and cluster centres using the following equations:

u ir = c s=1 d(x i , v r ) d(x i , v s ) 2 m-1 -1 v r = argmin k∈Np(vr) n i=1 u m ri d(x k , x i ) (1)
where u ir denotes the membership degree of x i to cluster r, v r the cluster centres and N p (v r ) the neighbourhood of centre v r , which looks to update medoids in their vicinity, alleviating computational costs. The latter is defined as the p data maximising membership to cluster r. Both updates are iterated until medoid positions stabilise.

Proposed Methodology

This section describes the methodology we propose to dynamically cluster a heterogeneous stream, as sketched in Algorithm 1. It belongs to the family of two-level approaches, performing a micro-clustering step based on a partitioning approach. The micro-clusters, i.e. the cluster information which is updated for each new datum, are defined as cluster medoids. As in [START_REF] Zhang | Birch: an efficient data clustering method for very large databases[END_REF][START_REF] Aggarwal | A framework for clustering evolving data streams[END_REF][START_REF] Cao | Density-based clustering over an evolving data stream with noise[END_REF], we test whether a new data point fits an existing cluster. If the test succeeds, no update is performed; if it fails, instead of creating a new cluster immediately, we add the data point to a buffer B. Cluster creation then only takes place when the buffer reaches a size threshold and is the result of a partitioning algorithm applied to B.

We propose, for this, a variant of the linearised fuzzy c-medoids [START_REF] Krishnapuram | Low complexity fuzzy relational clustering algorithms for web mining[END_REF], adding a cluster selection step to increase cluster homogeneity. This step makes it possible to identify atypical data grouped in a set of as yet unassigned data, denoted U: similarly to [START_REF] Cao | Density-based clustering over an evolving data stream with noise[END_REF], we distinguish outliers from core-clusters. The main difference here is that the outliers are not clusters of their own but a single set.

The next subsections respectively describe in more detail the test for assigning a point to an existing cluster, called cluster augmentation criterion, and the cluster selection criterion, as well as the global architecture of the algorithm.

Cluster Augmentation Criterion

Cluster augmentation consists in testing whether an incoming point can be assigned to one of the already identified clusters, or whether it should be buffered as a candidate clusterable. This procedure has two immediate advantages. The first is to reduce, for a given volume of data, the number of times the buffer is filled and, thus, the identification of new clusters, making the global process run faster. The second advantage is that it avoids the discovery, at a later stage, of clusters too similar to those already identified: it, indeed, ensures that the next data considered for clustering are adequately separate from the previously selected clusters. It, therefore, suppresses the need for a posterior fusion step, where the results of the buffer clustering are merged to the previously obtained clusters. This, again, alleviates the computation costs of the global method.

We propose to consider that a data point can be assigned to an existing cluster only under the condition that it does not deteriorate its compactness: addition is not aimed at generalising a cluster, rather at processing new data quickly. Therefore, we impose that a point can be added to a cluster if and only if it falls within the mean distance to the medoid at the time the cluster was selected. This can be written formally as:

d(x, ν C ) ≤ 1 |C| y * ∈C d(y * , ν C ) (2)
where y * denotes any element in the cluster at its creation. This augmentation condition defines a local criterion that adapts to the compactness of each cluster.

In particular, for a cluster containing only exact replicas of a data point, the augmentation criterion will exclusively allow the addition of more replicas. Once again, this severe criterion is intended to help the identification of fraudster behaviours, more than it is meant to offer a summarisation of the observed data.

Cluster Selection Criterion: the l-fcmed-select Algorithm

Medoid selection is a substep that actually modifies the l-fcmed algorithm, leading to the variant we propose, called l-fcmed-select. One of its motivations comes

Algorithm 1 DS-l-fcmed-select

For each new data point x Process x if ∃C ∈ C such that x can be added to C according to Eq. 2 then

Update C:

C ← C ∪ {x} else Update B ← B ∪ {x} end if Process B if |B| = τB then Apply l-fcmed-select to B → (C , U ) Update C ← C ∪ C Update U ← U ∪ U end if
Process U if purging criterion on U is fulfilled then Apply DS-l-fcmed-select recursively to U, treated as a data-stream end if from the issue of determining the appropriate number of clusters, c: as all partitioning clustering algorithms, l-fcmed always produces c clusters, whether c is relevant for the considered data or not. In order to bypass this difficulty, we propose to ask for a 'reasonable' -probably overestimated-number of clusters, and then to select only some of the produced clusters.

The proposed selection condition is, again, a compactness criterion: we keep only the clusters of sufficient size that exhibit a very high homogeneity, evaluated as the radius of the cluster. The selection criterion can, thus, be formalised as:

|C| > τ C
and max

x∈C d(x, ν C ) ≤ ξ (3)
where τ C is the minimal acceptable size and ξ a compactness threshold. This algorithm does not return a data partition as some of the data, that assigned to discarded clusters, remain unattributed. More formally, l-fcmed-select outputs a set of clusters, C = {C 1 , ..., C c }, with c ≤ c, and a set of unassigned data U. The latter represents atypical cases, or as yet unexplained data, that do not deserve, for the time being, medoids of their own in the clustering solution.

Global Architecture and Parameters

The global architecture of the proposed methodology, called DS-l-fcmed-select, is given in Algorithm 1. The set of clusters C, the buffer B and the set of unassigned data U are initially assigned the empty set.

When a new data point then arrives, the algorithm tries to assign it to one of the existing clusters. If this substep fails, the point is added to the buffer B.

Once the buffer reaches a user-defined size threshold, τ B , meaning that too many points differ from the previously identified clusters, then l-fcmed-select is applied anew to the data in the buffer. Previously testing addability ensures that all obtained clusters are distinct enough from the already identified clusters.

The l-fcmed-select algorithm imposes handling the set U of unassigned data. The corresponding data are 'more atypical' than the ones in B, insofar as they have been submitted at least once to clustering, whereas buffered data have only been tested against existing clusters. However, it may be the case that atypical behaviours eventually become less isolated, warranting a cluster of their own. Therefore, when some purging condition on U is reached, the data it contains are considered once more for core-clustering. We apply DS-l-fcmed-select, processing it as a fictitious data-stream. The purging condition could be linked to the U's size, yet this induces the risk of running back to back purges, if U's size does not fall far enough below the threshold. To avoid this, we harness U's purge to the amount of processed data, with the idea that these regular purges still attest to the aging of the data. A purge, thus, starts every time τ U points of the data-stream have been processed and stops as soon as U's size stops decreasing.

Overall, the proposed method relies on three sets of parameters, that is the l-fcmed parameters: the number of clusters c, the fuzzifier m and the neighbourhood size for the medoid update p; the cluster selection criteria: the minimal acceptable cluster size τ C and diameter ξ; and the size thresholds: the size at which B is subjected to l-fcmed-select, τ B and the rate at which U is purged, τ U .

Experimental Results

Data and Experimental Setup

We applied the proposed methodology to a real fraud-stream covering almost one year (49 weeks) and containing close to a million fraudulent transactions. Each is described by its amount in Euros, a positive real number, as well as categorical attributes, namely the country where it took place and the merchant category code, a general categorisation of transacted products.

The distance d between two transactions t 1 and t 2 , represented as vectors of their features, is defined as d(t 1 , t 2 ) = 1/q q i=1 d i (t 1i , t 2i ), where d i is the distance for attribute A i . Two cases are distinguished:

d i is either d i = d cat , if A i is categorical, or d i = d num , if it is numeric.
Each is defined as follows:

d cat (x, y) = 1 if x = y 0 otherwise d num (x, y) = |x -y| max(x, y)
The distance for numeric attributes is thus defined as a relative gap: the assumption being that a difference of 2e in amount, say, should not have the same impact if the compared amounts are around 5e or if they are closer to 1 000e.

For the algorithm parameters, we use the following setup: l-fcmed is applied with c = 400, m = 2 and p = τ B /c = 12. Cluster selection is based on τ C = 10 and ξ = 0.15. Note that, due to the distance choice, this low value imposes that data assigned to a given cluster all have the same country and the same activity, variability is only (moderately) tolerated for the amount. The size threshold for the buffer is τ B = 5 000 and the set of unassigned data U is purged every time τ U = 50 000 transactions have been processed. The experiments were run using a parallel implementation of DS-l-fcmed-select on a multicore cluster.

Experimental Results

With these parameters, the proposed methodology finds a total of 6 476 clusters covering a wide range of sizes and time-spans. In the following, we first analyse the global results of the final step, then comment the dynamics of fraud profiles, both globally and at a more detailed level.

Final Global Analysis:

In order to study the obtained clusters when the whole data-stream has been processed, we focus on cluster sizes. Figure 1 shows the final sizes of the clusters in decreasing order.

It can be observed that, despite a very severe compactness criterion, the largest cluster groups 26 917 frauds, highlighting the redundancy of the data, in which there exists a largely dominant type of fraud. More generally, the 25% largest clusters cover 77.7% of all affected frauds. Conversely, the 25% smallest clusters only cover 3.6% of the assigned frauds. This shows that the fraud behaviours include a large number of rather rare fraud procedures, either due to atypical country, activity, amounts or a combination of the above.

Moreover, at the end of the process there remain 21.7% of the whole as unassigned frauds, i.e. too atypical to be clustered according to the criteria imposed on the clustering result.

Global Dynamic Analysis: We first analyse the dynamics of fraud profiles globally, examining the distribution of each profile time-span. These lengths are defined as the number of weeks between dates for the first and last frauds assigned to each cluster. We should point out that our analysis of the dynamics is more concerned with the evolution of the contents, the frauds, then it is with the displacement of the clusters, as is usually the case. Figure 2 shows the repartition of these durations, both in terms of the number of clusters, on the left, as well as the number of frauds they represent, on the right. Two types of clusters co-exist: a first category, representing 46.9% of all clusters, groups long-lasting profiles that nearly span over the whole year, with periods longer than 40 weeks. This comes along with a dominance in terms of data quantities, as they represent 81.6% of the assigned fraudulent transactions.

A second type of profiles can be described as 'flash profiles': these correspond to behaviours that are very precisely dated, disappearing within a single week or, possibly, up to two or three weeks. This category represents 9.1% of the clusters, and still appear to be significant in terms of number of frauds. More precisely, the average size of the 275 clusters observed only during a single week is 57, with sizes ranging from 10 to 3001.

Figure 3 provides another view on the dynamics of credit-card fraud profiles. The full line on top shows the evolution of the number of active clusters each week, where a cluster is called active at a given date if it is created or if at least one transaction is assigned to it at that date. The number of active clusters is globally increasing over the entire period, excepting the final period which is shorter than the other weeks and not augmented by new data. The ratio between new and existing clusters is clarified by the two additional dashed lines, where the one nearer the bottom shows cluster creation per week and the one closer to cluster activity traces the number of augmented clusters in the period. Cluster creations tend to slow down significantly after each peak and the range between consecutive maximum and minimum shrinks as time goes. This is explained by the fact that most relevant profiles are found and that new ones do not appear all the time. Cluster augmentation, for its part, explains most of the activity, as the closeness between plots shows, since the more clusters there are, the more likely a fraud will fit one. It should also be observed that the number of active clusters is always much lower than the total number of clusters.

Detailed Dynamic Analysis In order to offer a more detailed analysis, Figure 4 shows the size evolutions of the 40 largest clusters, where the ranking is based on the clusters' final sizes, as in Figure 1. Four main types are observed, relative to growth speed: the curves can be linear, corresponding to a constant speed, concave, as in a deceleration behaviour, convex, showing an acceleration, or, as already discussed, flash profiles. We discuss each in turn below.

The constant increase profiles, globally exemplified by ten of the eleven largest clusters, represent fraud behaviours that are observed all year with very little variations in terms of relative distribution, i.e. with an approximate constant number of additional representatives each week. These are the 'fraud basics' or classic behaviours fraudsters know they can rely on. It should be pointed out that the constant increase is correlated to the fact that these clusters are the largest ones.

The second profile type, characterised by concave curves, presents a deceleration or even an abrupt halt in exploitation. This type is illustrated by clusters 21, 25 or 27. It corresponds to obsolete types of frauds on their way out. It would be interesting to check with credit-card fraud experts whether these observations can be related to the introduction of specific anti-fraud policies.

The third type is complementary: it groups convex curves, more precisely a parabolic increase in size or even a sudden augmentation, like cluster 13. It would likewise be relevant to discuss these results with experts to see if these observations correlate with credit-card policy modifications.

Over the given temporal window, some clusters combine a sudden increase and progressive deceleration, as clusters 35 and 38 do. These hybrid profiles introduce some doubt as to whether clusters of the third type are going to slow down at some point.

The last type is the already discussed very short-lived clusters , e.g. cluster 23. It is interesting to note that some of these are indeed large enough to join the 40 largest clusters, in which most are represented over a much longer time-span.

Conclusion and Future Work

A methodology to process incoming streams of heterogeneous data and study the derived profiles and their dynamics is proposed in this paper, together with its application to a real data set of credit-card frauds. The analysis of the results shows the relevance of the approach, which makes it possible to establish distinct types of fraud profiles depending on their temporal evolution and to identify specific fraudster profiles. The proposed algorithm efficiently processes data streams of heterogeneous nature, in a parallel implementation. It is based on incremental micro-clustering performed by a variant of the l-fcmed algorithm, defined as its combination with a cluster selection step guaranteeing highly compact clusters. The processing decomposes the data into three subsets, namely clusters, data to-be-clustered in a buffer and atypical data, remaining unassigned. The purge of the unassigned data, and to a lesser extent the clustering of buffered data, make it possible to manage some data beside the current flow of the data stream. This is particularly helpful in the case of credit-card fraud profiling, where frauds can be declared a long time after the transaction has been recorded.

Ongoing work aims at combining these micro-clustering results with a macroclustering step, e.g. through a hierarchical method, to get a more synthetic view of the clusters, even if the detailed analysis also provides relevant and meaningful information. Future work includes comparisons with existing algorithms, as well as the discussion with experts in anti-fraud policies to obtain a semantic validation of the observed results. Another perspective is to take more information into account in fraud comparisons, in particular related to transaction sequences.

Fig. 1 .

 1 Fig. 1. Sizes of the clusters once all data has been processed, in descending order

Fig. 2 .

 2 Fig. 2. Time-span histograms: (left) number of clusters covering each number of weeks, (right) cumulative size of clusters covering each number of weeks

Fig. 3 .

 3 Fig. 3. Number of active (full line), augmented (top dashed) and new (bottom dashed) clusters per week

Fig. 4 .

 4 Fig. 4. Evolution of the size of the 40 largest clusters, where the cluster id equals its rank in terms of final size.

Acknowledgements This work was supported by the project eFraudBox funded by ANR -CSOSG 2009.


Marie-Jeanne Lesot

Adrien Revault D'allonnes

Credit-Card Fraud Profiling Using a Hybrid Incremental Clustering Methodology

Keywords: Incremental clustering, Hybrid Clustering, Bank Fraud, Credit Card Security

Introduction

With the generalisation of credit and debit cards as modes of payment, creditcard frauds in e-commerce and other mail-order or distant transactions have become a major issue for all banks and card-issuers. For instance, according to the 2011 annual Banque de France report [START_REF]Banque de France: Annual Report the Observatory for Payment Card Security[END_REF], whereas the overall 2010 fraud rate in France is as low as 0.074%, corresponding to an amount of e 368.9 million, the frauds in domestic card-not-present payments (i.e. made online, over the phone or by post) represent 0.26% of this type of transaction, about three and a half times more. These frauds represent 62% of all fraud cases in terms of value.

As a consequence, the analysis and automatic detection of fraudulent transactions has become a largely studied field in the machine learning community [START_REF] Bolton | Statistical fraud detection: a review[END_REF][START_REF] Phua | A comprehensive survey of data miningbased fraud detection research[END_REF][START_REF] Laleh | A taxonomy of frauds and fraud detection techniques[END_REF], in particular in the case of e-commerce. This task is both essential from an application point of view, as mentioned above, and scientifically highly challenging, because of its difficulty, part of which is due to the quantity of data that must be processed and the extreme class imbalance.

From a machine-learning standpoint two problems should be separated, namely fraud detection and fraud characterisation. The former aims at predicting whether or not a given transaction should be accepted, so as to decline tentative frauds as they take place. Its objective is, therefore, to differentiate fraudulent and genuine transactions and it is, thus, part of the supervised-learning framework. As such, it should be formulated as a discrimination task in a highly imbalanced two-class setting. This particular problem can use the card history to identify frauds as transactions that differ from the card-holder habits.

The second machine-learning problem, fraud characterisation, endeavours to identify distinct fraudster profiles which can then be conceived as operational procedures and used as investigative tools in the apprehension of fraudsters or to assist in fraud detection. The objective is, therefore, to identify, in a set of frauds, distinct subtypes of frauds exhibiting similar properties. It is part of the unsupervised-learning framework and is essentially a clustering task applied to the set of all fraudulent transactions. It should be noted that, in this case, card history is of no use, since fraudster profiles are independent from card-holder habits and, therefore, frauds need only be compared to other frauds and not to legitimate transactions.

In this paper, we consider the latter type of approach and propose a hybrid incremental clustering methodology to address this task. This method exhibits the following characteristics: first, it ensures a rich description of the identified fraudster profiles and allows a multi-level analysis, through the hierarchical structure of the extracted clusters it yields. Second, the method allows the processing of large datasets. Indeed, even if frauds represent a small minority of all transactions, they are still very numerous. This is the reason why we propose to combine a hierarchical clustering step, to organise the identified clusters in a dendrogram but with a very high computational cost, to a preliminary data-decomposition step, through an efficient partitioning step. For the partitioning step, we propose an incremental approach which processes the dataset in smaller subsets. Third, the method can deal with heterogeneous data, i.e. data whose features can be either categorical or numeric. Indeed, apart from the amount which is a number, transactions are, for instance, described by the country where they take place or the general category of transacted product. Finally, on a more general level, the method is robust, that is, it does not suffer from its random initialisation.

In the next section, we describe the methodology proposed to address this task. Section 3 then presents the experimental results obtained on real data.

Proposed Methodology

Clustering data that are both in vast amounts and of a hybrid nature imposes constraints on candidate algorithms. In this section, we outline the main approaches dealing with these issues and we describe in more detail the linearised Fuzzy c-Medoids [START_REF] Krishnapuram | Low complexity fuzzy relational clustering algorithms for web mining[END_REF] on which the proposed methodology relies. We then detail the proposed methodology.

Related Work

Clustering Large Data Sets Very large datasets, having become more and more common, have given rise to a large diversity of scalable clustering algorithms.

One way to tackle the problem is to make existing algorithms go faster with specific optimisations. For instance, acceleration of the k-means method and its variants can be achieved using improved initialisation methods to reduce the number of iterations [START_REF] Cheng | Fast fuzzy clustering[END_REF][START_REF] Altman | Efficient fuzzy clustering of multi-spectral images[END_REF]. For the Partitioning Around Medoids (pam [START_REF] Kaufman | Finding groups in data, an introduction to cluster analysis[END_REF]) approach, clarans [START_REF] Ng | Efficient and effective clustering methods for spatial data mining[END_REF] or the linearised fuzzy c-medoids algorithm [START_REF] Krishnapuram | Low complexity fuzzy relational clustering algorithms for web mining[END_REF], detailed below, alleviate computational costs by updating medoids in their vicinity.

Another approach, incremental clustering, iteratively applies a clustering algorithm on data subsamples which are processed individually. The samples are extracted from the dataset (e.g. randomly) or they can be imposed by a temporal constraint, when the data is available as time goes by. One variant proposes to build a single sample, guaranteeing its representativeness, so that the results of a single application of a clustering algorithm can be considered as meaningful for the entire dataset [START_REF] Hathaway | Extending fuzzy and probabilistic clustering to very large data sets[END_REF].

In the general case, however, each sample is clustered and these partial results are then merged into the final partition of the dataset [START_REF] Hore | A cluster ensemble framework for large data sets[END_REF]. This fusion can be performed progressively by including in the clustering step of a given sample the results from the previous steps: a sample is summarised by the extracted clusters and this summary is processed together with the next sample [START_REF] Farnstrom | Scalability for clustering algorithms revisited[END_REF][START_REF] Hore | Single pass fuzzy c means[END_REF][START_REF] Hore | Online fuzzy c means[END_REF]. The incremental variant of dbscan [START_REF] Ester | Incremental clustering for mining in a data warehousing environment[END_REF] proposes an efficient strategy to determine the region of space where the cluster structure identified in the previous samples should be updated and then locally applies the dbscan algorithm. Alternatively, the fusion can be performed at the end, when all samples have been processed, for instance by applying an additional clustering step to the centres obtained from each sample. Birch [START_REF] Zhang | Birch: an efficient data clustering method for very large databases[END_REF], for example, incrementally performs a preclustering step to build a compact representation of the dataset, based on structured summaries that optimise memory usage along user-specified requirements. The centres obtained after scanning the whole dataset then undergo a clustering process. Cure offers a compromise between hierarchical and partitioning clustering, by both using cluster representative points and applying cluster fusion [START_REF] Guha | CURE: an efficient clustering algorithm for large databases[END_REF]. Both approaches, progressive and closing fusions, can also be combined [START_REF] Bradley | Scaling clustering algorithms to large databases[END_REF].

Clustering Heterogeneous Data Hybrid data, data described by both numeric and categorical attributes, define another case where specific clustering algorithms are required. Such data rule out the usage of all mean-centred clustering techniques, in particular the very commonly applied k-means and its variants.

Two main approaches can be distinguished for this problem: so-called relational methods which rely on the pairwise dissimilarity matrix (e.g. based on the pairwise distances) and not on vector descriptions of the data. This type of approach includes, in particular, hierarchical clustering methods, density-based methods [START_REF] Sander | Density-based clustering in spatial databases: the algorithm DBSCAN and its application[END_REF] as well as relational variants of classic algorithms [START_REF] Hathaway | Nerf c-means: non euclidean relational fuzzy clustering[END_REF][START_REF] Hathaway | On relational data versions of c-means algorithms[END_REF].

On the other hand, medoid-based methods [START_REF] Kaufman | Finding groups in data, an introduction to cluster analysis[END_REF][START_REF] Krishnapuram | Low complexity fuzzy relational clustering algorithms for web mining[END_REF] constitute variants of the mean-centered methods that do not define the cluster representative as the average of its members, but as its medoid, that is, the data point that minimises the possibly weighted distance to cluster members.

Linearised Fuzzy c-Medoids The linearised fuzzy c-medoids algorithm, denoted l-fcmed in the following, combines several properties of the previously listed algorithms: it can process data that are both in vast amounts and of a hybrid nature [START_REF] Krishnapuram | Low complexity fuzzy relational clustering algorithms for web mining[END_REF]. Indeed, it belongs to both accelerated techniques and medoidbased methods. Moreover, being a fuzzy variant of such algorithms, it offers properties of robustness and independence from random initialisation. More formally, if x i , i = 1, . . . , n are the data points, c the desired number of clusters, v r , r = 1, . . . , c the cluster centres and u ir the membership degree of datum x i to cluster r, the algorithm alternatively updates the membership degrees and the cluster centres using the following equations:

u ir = c s=1 d(x i , v r ) d(x i , v s ) 2 m-1 -1 v r = argmin k∈N (vr) n i=1 u m ri d(x k , x i ) ( 1
)
where m is the so-called fuzzifier, d a suitable metric and N (v r ) the neighbourhood of centre v r . The latter is defined as the p data maximising membership to cluster r.

The membership degrees are, thus, updated as in the fuzzy c-means and the cluster centres as the data points that minimise the weighted distance to cluster members. To reduce the computational cost, l-fcmed searches for a suitable medoid update close to each current medoid, in N (v r ), instead of computing the minimum over the whole dataset. Both updates are iterated until medoid positions stabilise.

The l-fcmed parameters are c, the number of clusters, m, the fuzzifier, and p, the neighbourhood size. The algorithm also depends on the chosen metric d.

Global Architecture

To cluster fraudulent transactions, we propose a two-step methodology, illustrated in Figure 1, inspired from the existing approaches described above: before performing a hierarchical clustering, because of its high computational cost, we operate a segmentation using a partitioning algorithm. Because of its advantages, listed in the previous section, we choose to use the linearised fuzzy c-medoids, or rather we propose an incremental extension to further limit computational strains, which we describe in the following.

The second step then uses a hierarchical clustering method to generalise the obtained clusters. Its output dendrogram allows the data analyst to choose the desired level of compromise between homogeneity and generality.

Incremental Partitioning Step

Following the classic incremental methodology, instead of performing the partitioning clustering on the whole dataset, we operate l-fcmed iteratively on randomly selected samples of size n l . As detailed below, we propose to introduce two substeps to improve its efficiency in the considered global architecture: medoid selection and unaffected fraud allocation. Medoid selection The aim of the partitioning step is to purposefully build an over-segmentation to summarise the data while minimising the loss of information, as it is a preliminary step to the hierarchical clustering step. We thus force a compactness constraint on the over-segmented clusters, in order to keep only the most homogeneous, discarding the rest.

To select the clusters C r , r = 1, . . . , c, whose medoids are highly representative of their assigned data, we propose to keep those of sufficient size and exhibiting a very high homogeneity level. The latter is evaluated by a measure of the dispersion of members of C r that could, for instance, be relative to the cluster diameter, diam(C r ) = max xi,xj ∈Cr d(x i , x j ). The selection criterion can thus be formalised as:

size(C r ) = |C r | > τ and disp(C r ) ≤ ξ ( 2
)
where τ is the minimal acceptable size and ξ a user-set compactness threshold. All data in the discarded clusters is then put back into the general pool of transactions to be clustered. They thus become candidates for the random sample selection of following iterations of the partitioning step.

Unaffected Fraud Allocation Before iterating to the next sample, we scan the data that are yet to be clustered, so as to add unaffected frauds to the identified clusters. This cluster augmentation has a double advantage: first, it avoids the discovery in subsequent iterations of clusters similar to the selected ones, i.e. it avoids cluster duplication or redundancy. It therefore simplifies the posterior fusion step. Moreover, it further alleviates computational costs by reducing the size of the frauds to cluster in following iterations. This is done by selecting, from the pool of unclustered data, those frauds which can be allocated to the selected clusters without degrading their quality, that is, frauds which are sufficiently close to the medoid and are in the allowed dispersion. Formally an unaffected fraud x is assigned to cluster C r if:

d(x, v r ) < disp(C r ) (3)
This step can be seen as similar to the extension step performed by [START_REF] Hathaway | Extending fuzzy and probabilistic clustering to very large data sets[END_REF] but, in our case, it remains a tentative extension, that is, only performed under the condition that it does not deteriorate cluster dispersion.

Having built a compact and homogeneous partition of a subset of the data through over-segmentation, medoid selection and cluster augmentation, the process is repeated until no further cluster meets the required standards.

Hierarchical Step

Once all homogeneous clusters satisfying the constraints have been created, a hierarchical clustering with complete linkage is operated on the resulting medoids. Because we have heavily reduced the volume of data with our partitioning, this step is computationally acceptable. The resulting hierarchy offers a progressive agglomeration of clusters and allows for the selection of a suitable compromise between cluster density and number of clusters. The selection of this compromise is made by the visual examination of the hierarchy dendrogram.

Experimental Results

Data and Experimental Setup

We applied the proposed hybrid incremental clustering methodology to a dataset made of 958 828 fraudulent transactions. These correspond to transactions that were rejected by the actual card-holders who, in this way, label the data and identify the transactions to be considered as frauds.

Each fraud in the dataset is described as a combination of numeric and categorical features. The first type of attributes includes the amount of the transaction in euros, a positive real number. The second type includes the country where the transaction took place and the merchant category code of the product.

The distance d between two transactions t 1 and t 2 , represented as vectors of their features, is defined as the average of the distances on each attribute, i.e. d(t 1 , t 2 ) = 1/q q i=1 d i (t 1i , t 2i ), where d i is the distance for attribute A i . This is either

d i = d cat , if A i is categorical, or d i = d num if it is numeric.
Each is defined as follows:

d cat (x, y) = 1 if x = y 0 otherwise d num (x, y) = |x -y| max(x, y)
The distance for categorical attributes d cat is binary: it equals 0 if the two values to be compared are identical, and 1 in all other cases. The distance for numeric attributes is defined as a relative gap: the assumption behind this is that a difference of 2e in amount, for instance, should not have the same impact if the compared amounts are around 5e or if they are closer to 1 000e.

Regarding the parameters , we use the following setup: each sample contains n l = 50 000 randomly selected data. l-fcmed is initialised randomly and applied with the high value c = 4 000 because we want an over-segmentation. We use the common value m = 2 for the fuzzifier. The size of the neighbourhood around the medoids in which the following is selected is p = 50 000/4 000 .

Medoid selection, as presented in equation 2, depends on cluster size and dispersion. The minimal size required is set at τ = 10. Since it bears on all attributes, we write the dispersion metric disp(C) as the vector of its attributes' dispersions. For categorical attributes, the number of different values represents dispersion; for numeric attributes, dispersion is best represented by their standard-deviation normalised by their mean value. Formally supposing that for attribute A we write its value in x as A(x), and its average value in cluster C as A C = x∈C A(x)/|C|, we may write these dispersions as:

disp cat (C) = |{A(x)|x ∈ C}| disp num (C) = 1 |C| x∈C (A(x) -A C ) 2 A C (4)
In this way, disp(C) is the vector of all dispersions and ξ is also a vector giving local thresholds, which we set at ξ cat = 1, limiting the categorical attributes to a single value in the selected clusters, and ξ num = 0.01. The cut threshold, for the hierarchical clustering, is set to 0.5, based on a visual inspection of the dendrogram (see Figure 4) to achieve an acceptable compromise between the final number of clusters and their homogeneity.

Incremental Partitioning Step: Results

The evolution of the incremental partitioning step is illustrated on Figures 2 and3. Figure 2 shows the number of frauds assigned at each iteration, before the allocation of unaffected frauds. It should be observed that this number, starting at 18 373, represents 36.7% of the processed 50 000 points. This small proportion of selected data illustrates how the compactness constraint rejects a large amount of clusters and data. After this initial high value, the amount of selected fraudulent transactions decreases very rapidly. The curve presents an obvious asymptote around 500, i.e. around less than 1% of the considered 50 000 lines of data. This, in itself, is a satisfactory justification for stopping the partitioning step after the illustrated 50 iterations.

The left graph in Figure 3 shows the cumulative number of clusters selected at each iteration. At the first iteration, 394 clusters are selected as being quality clusters. By the end of the process 4 214 have been identified. The inflexion of the curve indicates that the number of newly discovered quality clusters decreases with the number of iterations, another explanation for stopping after fifty iterations of the partitioning step.

The right graph in Figure 3 shows the cumulative number of assigned data after reallocation at each iteration, i.e. the total number of transactions that have been assigned to any of the created clusters. 322 115 transactions are assigned at the very first iteration, which indicates a high redundancy in the considered data: many transactions are identical or very close one to another in the considered description space, and thus fulfil the strict homogeneity condition imposed on the assignment step. At each further iteration, the number of assigned transactions drastically decreases, the last iterations bringing very little gain. This curve, thus, also argues in favour of ending iterations of the partitioning.

As a result of these different choices, the incremental partitioning step produces, in the end, 4 214 clusters containing 642 054 frauds.

Hierarchical Step: Results

Figure 4 shows the dendrogram obtained after applying a hierarchical clustering to the medoids obtained in the partitioning step. The same distance is used for medoids as for transactions.

Visual inspection of the dendrogram prompts a cut above a cost of 0.5. Indeed, cutting the dendrogram at 0.5 yields 156 clusters, which represents a reasonable compromise between cluster homogeneity and number of clusters. The resulting clusters have a small diameter and their number, 156 as compared to the original 958 828 transactions, is a cognitively manageable amount of data to study for the human analyst.

Final Results

To take a closer look at the resulting clusters, we start off by studying the distribution of cluster sizes globally.

Figure 5 shows the cluster sizes in decreasing order and also shows a high disparity. In particular, the greatest cluster represents 23% of affected frauds on its own, whereas the second largest is only one third of the largest. More generally, the fifty largest clusters cover 92% of all affected frauds. In the following we successively comment the hundred and six smallest and the fifty largest clusters.

Analysis of the Smaller Clusters On average the smaller clusters, the ones after the first fifty, only contain 471 frauds, i.e. 7 of the affected frauds. It could, therefore, be argued that they contain too little information and that it not necessary to study them further. Indeed, the fraud profiles they are associated to may seem too anecdotal. However, some of these clusters, or groups of clusters, may still warrant the analyst's attention because of some striking characteristics.

In this way, 9 clusters, representing 1 745 transactions, are each composed of exact replicas of a single transaction, that is, identical amount, country and activity. Even if the largest of these clusters only has 535 frauds, their being identical marks them as potential parts of a particular modus operandi, which any analyst might wish to investigate further.

Another trigger which might tingle an analyst's curiosity is exhibited by cluster 147, which has a mean amount of 914e, an oddly high value compared to the average fraud value of about 112e. Moreover, all its transactions are linked to the same country and activity. This activity only appears in this cluster. For these reasons, even if cluster 147 only has 72 transactions, a closer study of these transactions seems appropriate to find other similarities, such as the identity of the seller or the dates on which they took place, for instance.

Analysis of the Larger Clusters

The fifty largest clusters represent the most notable fraudster profiles. Indeed, they are singularly homogeneous: just two of them, clusters 26 and 44, are not described by a single country and activity.

If we take a closer look at these two atypical clusters, we see that cluster 26 associates 4 546 frauds to three distinct merchant activities. Of these three activities, two are heavily outnumbered by the dominant one, the latter having 4 402 frauds, or 96.8% of the cluster, when the other two represent 80 and 64 transactions, that is, 1.8% and 1.4% respectively. Furthermore, these two minority activity types do not appear in any other cluster. The dominant activity does appear in five other clusters but with different countries, whereas cluster 26 only has one country. This cluster's homogeneity is also apparent in its amount distribution, since the range it covers is [10, 13.16].

The other mixed cluster, cluster 44, has 1 670 fraudulent transactions and two countries. Once again, one of the countries is dominated by the other, representing just 104 individuals or 6.2% of the cluster population, and is only present in this cluster. These compactness anomalies are, therefore, slight and explainable.

If we turn back to the general population of large clusters, the 96% with only one activity and one country, we see that compactness does not constrain size. Indeed, the largest of all clusters, with 147 831 frauds, equivalent to 23% of all affected frauds, belongs to this category. Regarding the amounts, this cluster spreads over the [START_REF]Banque de France: Annual Report the Observatory for Payment Card Security[END_REF]480] interval, a reasonable size compared to the global span of the data over [0, 10 276]. The left part of Figure 6 shows the histogram of its amounts and also shows how the distribution is concentrated on small values.

Another illustration of the first fifty clusters' quality, is given by cluster 12. This cluster, still defined over a single country and activity, has 8 828 frauds with amounts on the interval [0.99, 83.73]. The right part of Figure 6 offers a view on their dispersion. Looking at this distribution, we see that it could be subdivided into homogeneous subintervals, probably the ones given by the partitioning step, later joined by the hierarchical clustering. Cluster 12, thus, illustrates the use of this fusion step: instead of studying individually all 93 original clusters -the clusters fused during the hierarchical step to form cluster 12 -the analyst can focus on a generalised view, yet still be able to identify potentially interesting subgroups. The analyst may yet explore these subgroups by choosing to cut the dendrogram at a lower value. This inspection can be made locally by concentrating on the branch which actually contains the interesting clusters. This granularity refocusing ability, local or not, emanating from the cluster hierarchy, is an added benefit and justification for the proposed global architecture of the clustering method.

Conclusion

In this paper, we proposed a methodology for the identification of the characteristics of credit-card frauds, through the identification of distinct fraud profiles. It is based on the combination of an incremental variant of the fuzzy c-medoids with hierarchical clustering, and it is thus able to process very large heterogeneous data. We illustrated the relevance of the proposed approach on a real dataset describing next to one million online fraudulent transactions.

Ongoing work aims at enriching the interpretation of the obtained profiles, in particular by the construction of typical transactions representing each fraud profile, so as to ease their characterisation. To that aim, the use of fuzzy prototypes is considered, in order to underline the specificity of each profile as opposed to the others.

Fig. 1 .

 1 Fig. 1. Global architecture of the proposed methodology

Fig. 2 .

 2 Fig.2. Evolution of the incremental partitioning step: number of assigned transactions, at each iteration.

Fig. 3 .

 3 Fig.3. Evolution of the incremental partitioning step: (left) cumulative number of selected clusters, at each iteration, (right) cumulative number of assigned data after reassignment at each iteration.

Fig. 4 .

 4 Fig. 4. Dendrogram of the hierarchical clustering step applied to the medoids obtained in the partitioning step.

Fig. 5 .

 5 Fig. 5. Sizes of the final clusters.

Fig. 6 .

 6 Fig.6. Histogram of the amounts (left) for the largest cluster (population: 147 831; binwidth: 9.58e), (right) for 12 th largest cluster (population: 8 828; bin-width: 1.65e).

Acknowledgments

This work was supported by the project eFraudBox funded by ANR-CSOSG 2009. The authors also thank Nizar Malkiya for his help in implementing and testing the methodology.


Giuseppe Rastiello
email: g.rastiello@gmail.com

Cédric Giry

Fabrice Gatuingt

Rodrigue Desmorat

Milan Jirásek

Nonlocal damage with evolving internal length: the Eikonal nonlocal formulation

Integral non-local (INL) formulations [START_REF] Bažant | Nonlocal Integral Formulations of Plasticity and Damage: Survey of Progress[END_REF] are often used to regularize continuum damage models in the presence of strain softening laws. In numerical computations the introduction of an internal length allows for avoiding pathological mesh sensitivities. Some questions concerning the identification of the internal length, its possible evolution during damage process and the need for special treatments of non-locality operators near boundaries (e.g. edges, cracks) are however still open. A physical request is that material points separated by a crack or a highly damaged zone should not interact (despite what is done in standard non-local integral theories). This can be obtained by allowing non-local interactions to evolve depending on mechanical fields (e.g. damage [START_REF] Pijaudier-Cabot | Non-local damage model with evolving internal length[END_REF], stress [START_REF] Giry | Stress based nonlocal damage model[END_REF], etc.).

Different formulations where proposed in the literature for this purpose. In particular, based on the analogy between wave and information propagation within an elastic damaged medium, [START_REF] Desmorat | Nonlocal models with damage-dependent interactions motivated by internal time[END_REF] proposed to reformulate the classic non-local averaging procedure in terms of the ratio of the time needed for an elastic wave to propagate between two material points and the corresponding time in undamaged conditions. Using such an approach in two-and three-dimensional contexts may however reveal complex. In that case, no general analytical solutions for the wave propagation equation through the heterogeneous medium are available, and tedious and time-consuming numerical solution procedures are needed.

Based on the Wentzel-Kramers-Brillouin (WKB) approximation for high-frequency wave propagation in a damaged medium, the Eikonal non-local (ENL) formulation provides a novel interpretation of damage dependent non-local interactions both in isotropic and anisotropic contexts. From a mathematical point of view, interaction distances are computed as solution of a timeindependent Eikonal equation (a stationary case of the Hamilton-Jacobi equation) with a damage dependent isotropic/anisotropic Riemannian metric. From a differential geometry viewpoint, this leads to consider that damage induces a curvature of the Riemannian space in which interaction distances are computed. Geodesic interaction distances determined in the curved space are used to compute nonlocal variables driving damage evolution, thus preserving the general theoretical framework of INL theories. This allows modeling non-local interactions that gradually vanish in damaged zones, leading to a progressive transition from diffuse damage to fracture. From a numerical viewpoint, Fast Marching approaches [START_REF] Sethian | A fast marching level set method for monotonically advancing fronts[END_REF] are used to compute non-local interaction distances between material points. These distances define the kernel of weighting function considered in integral non-local regularization method.

In this work, the theoretical derivation of ENL formulation from wave propagation is discussed and illustrated first. Only the main equations of the theoretical background (fully developed in [START_REF] Desmorat | Nonlocal models with damage-dependent interactions motivated by internal time[END_REF]) are presented. As an illustration, the case of an isotropic damage model is considered for the elastodynamics equations and the WKB approximation, leading to the time-independent Eikonal equation from which interaction distances are computed.

The numerical properties of the ENL regularization technique are investigated then. A numerical formulation [START_REF] Rastiello | Strain localisation from a isotropic Eikonal nonlocal (ENL) damage formulation[END_REF] for modeling damage dependent non-local interactions within mechanical computations is obtained by coupling Fast-Marching [START_REF] Sethian | A fast marching level set method for monotonically advancing fronts[END_REF] algorithms -for computing interaction distances -and a standard Finite Element (FE) procedure -for solving the quasi-static equilibrium equations. While the method is illustrated with a simple isotropic damage model, the formulation proposed is however general, and can be adapted to more complex models. The extension to anisotropic contexts is also possible without major modifications. In this latter case, the only difference will concern the use of a Fast-Marching algorithm that now should be capable of dealing with anisotropic Riemannian metric fields.

Finally, several numerical results of quasi-static simulations involving the failure of quasi-brittle materials in isotropic/anisotropic media are presented.

Fig. 1 :

 1 Fig. 1: Geodesic distances field for a square plate and its influence on the Gaussian nonlocal weighting function centered on the point: a) undamaged; b) cracked medium