Hafida Naim
email: hafida.naim@etu.univ-amu.fr

Mustapha Aznag
email: mustapha.aznag@univ-amu.fr

Mohamed Quafafou
email: mohamed.quafafou@univ-amu.fr

Nicolas Durand
email: nicolas.durand@univ-amu.fr

Semantic Divergence based Evaluation of Web Service Communities

Keywords: Community detection algorithms, Web services, Service communities, Topic models, Semantic divergence, Dependency network

The number of community detection algorithms is growing continuously adopting a topological based approach to discover optimal subgraphs or communities. In this paper, we propose a new method combining both topology and semantic to evaluate and rank community detection algorithms. To achieve this goal we consider a probabilistic topic based approach to define a new measure called semantic divergence of communities. Combining this measure with others related to prior knowledge, we compute a score for each algorithm to evaluate the effectiveness of its communities and propose a ranking method. We have evaluated our approach considering communities of real web services.

I. INTRODUCTION

Web services are increasingly being adopted to access data and applications through the Web. In order to ease the process of web services discovery, it is suggested to gather similar web services into groups known as communities or optimal subgraphs [START_REF] Maamar | Communities of Web Services -Concepts, Architecture, Operation, and Deployment[END_REF]. In this regard, the number of community detection algorithms is growing continuously adopting a topological based approach, as reported in [START_REF] Fortunato | Community detection in graphs[END_REF]. Unfortunately there is no generally accepted definition of community; each algorithm makes different assumptions that are consistent with the intuitive concept. Most assume that a graph or network contains a flat set of disjoint communities.

In the literature, several works have been proposed for comparing the resulted partitions in a supervised way [START_REF] Leskovec | Empirical comparison of algorithms for network community detection[END_REF]. In a social network, for instance, the communities could be groups of people with common interests. Many social networks emerge going far beyond the topological aspect and focus on the semantic dimension. In fact, nodes are not only black boxes but have a specific semantic. It became easy to construct a network on a specific topic where each node represents a user and contains all his tweets related to the topic at hand. In the context of web services, the notion of community is also very important. Classically, a community is a set of web services with similar functionalities grouped together independently of their location, of their maintenance and of their provider [START_REF] Cherifi | Community structure in interaction web service networks[END_REF]. A node of a network represents for example a web service which generally have a textual description. Recently, authors of [START_REF] Yu | On Service Community Learning: A Co-clustering Approach[END_REF] show that the discovery of web services communities facilitates the service discovery process.

An information network is usually represented by a graph with data entities corresponding to the nodes in the graph and edges indicating the relations among entities [START_REF] Liu | Community Detection Based on Structure and Content: A Content Propagation Perspective[END_REF]. In addition to the topological structure, nodes are usually represented with various types of information that describe their semantics. The task of identifying communities involves discovering groups with common properties, such as similarity among group members or densely connected structure. The main problem with the majority of community detection algorithms is that they completely ignore the semantics of nodes and consider just the topological nature of the communities [START_REF] Reihanian | Topic-oriented community detection of rating-based social networks[END_REF]. Community detection algorithms are usually informed only by the network structure. So, the produced communities are not sometimes homogeneous but nodes are divided into classes with a higher probability of connections between nodes of the same class than between nodes of different classes.

The work proposed in this paper aims to evaluate the quality and the semantic consistency of detected communities. More precisely, we propose a new method combining both topology and semantic to evaluate and rank community detection algorithms. Different phases of our method are defined as follows (see Section III for more details):

1) Community quality evaluation.

2) Community semantic divergence evaluation.

3) Community detection algorithms ranking.

To evaluate the quality of detected communities, we use the classical measures, i.e. purity and entropy [START_REF] Zhao | Empirical and theoretical comparisons of selected criterion functions for document clustering[END_REF]. These measures are widely used to evaluate the performance of supervised/unsupervised learning algorithms, particularly the clustering and community detection algorithms. To evaluate the semantic consistency of detected communities, we define a new measure called community semantic divergence based on the Kullback Leibler (KL) Divergence [START_REF] Steyvers | Probabilistic topic models[END_REF]. We use the probabilistic topic models, more precisely Correlated Topic Models [START_REF] Blei | A Correlated Topic model of Science[END_REF] to extract topics from web service descriptions. These extracted topics are then used to compute the semantic divergence for each detected community (see Section III-B). In our context, topic models are used as efficient dimension reduction techniques, which are able to capture semantic relationships between word-topic and topic-service interpreted in terms of probability distributions.

In our experiments, we consider a set of community detection algorithms, described in Section II-D, to evaluate empirically our approach.

The remainder of this paper is organized as follows: Section II introduces the basic concepts and problem formulation. It lists also a set of community detection algorithms selected to evaluate our approach. Section III presents the proposed method to evaluate and rank community detection algorithms. Section IV is devoted to the experimental evaluation. Finally, the conclusion and future work can be found in Section V.

II. PRELIMINARIES AND PROBLEM FORMULATION

A. Web services representation

Generally, every web service has a WSDL (Web Service Description Language) document that contains the description of the service. The WSDL is an XML-based language, designed according to standards specified by the W3C, that provides a model for describing web services. It describes one or more services as collections of network endpoints, or ports. It provides the specifications necessary to use the web service by describing the communication protocol, the message format required to communicate with the service, the operations that the client can invoke and the service location. To manage efficiently web service descriptions, we extract all features that describe a web service from the WSDL document.

Before representing web services as a TF-IDF (Text Frequency and Inverse Frequency) [START_REF] Salton | Automatic Text Processing: The Transformation, Analysis, and Retrieval of Information by Computer[END_REF] vectors, we need some preprocessing. The objective of this preprocessing is to identify the textual concepts of services, which describe the semantics of their functionalities. There are commonly several steps: Features extraction, Tokenization, Tag and stop words removal, Word stemming and Service Transaction Matrix construction (see [START_REF] Aznag | Correlated Topic Model for Web Services Ranking[END_REF] for more details). After identifying all the functional terms, we calculate the frequency of these terms for all web services. We use the Vector Space Model (VSM) technique to represent each web service as a vector of these terms. In fact, it converts service description to vector form in order to facilitate the computational analysis of data. In information retrieval, VSM is identified as the most widely used representation for documents and is a very useful method for analyzing service descriptions. The TF-IDF algorithm [START_REF] Salton | Automatic Text Processing: The Transformation, Analysis, and Retrieval of Information by Computer[END_REF] is used to represent a dataset of WSDL documents and convert it to VSM form. We use this technique, to represent a services descriptions in the form of Service Matrix. In the service matrix, each row represents a WSDL service description, each column represents a word from the whole text corpus (vocabulary) and each entry represents the TF-IDF weight of a word appearing in a WSDL document. TF-IDF gives a weight w ij to every term j in a service description i using the equation:

w ij = tf ij . log( n nj ).
Where tf ij is the frequency of term j in WSDL document i, n is the total number of WSDL documents in the dataset, and n j is the number of services that contain term j.

B. Web services graph

Before computing web service communities, we explain the structure of the web service space by modeling relationships between services. Let S = {s 1 , s 2 , ..., s n } be the web services space, we construct a semantic similarity graph, G = (V, E), which captures the semantic similarity between different web services. We compute the similarity between the two services using the proximity measure called Multidimentional Angle (also known as Cosine Similarity); a measure which uses the cosine of the angle between two vectors [START_REF] Platzer | Web service clustering using multidimentional angles as proximity measures[END_REF]. The semantic of the service s i is a vector d, which consists of the TF-IDF scores extracted from the Service Transaction Matrix. The multidimensional angle between a vector p containing the TF-IDF scores of the service s p and a vector q containing the TF-IDF scores of a service s q can be calculated using Equation 1:

Cos(p, q) = p.q p . q = t i=1 p i q i t i=1 p 2 i t i=1 q 2 i ( 1
)
where t is the number of terms representing each web service.

Consequently each vertex v i of our graph G represents the service s i and two vertices are s p , s q will be connected if and only if their similarity, i.e., cos(p, q), is larger than a given threshold. After the construction of the web services graph we apply several algorithms to detect communities of web services. Our goal is not to use the semantic of web services and to combine it with the structure of the graph to find homogeneous web services communities like [START_REF] Liu | Discovering Homogeneous Web Service Community in the User-Centric Web Environment[END_REF]. In fact, we apply several graph structure based detection community algorithms and we use the semantic of web services and their categories to evaluate the resulted communities and to rank the used algorithms.

C. Global semantic and topics extraction

In Information Retrieval, Probabilistic Topic Models were originally developed and utilized for topic extraction and document modeling. Topics (or latent factors) are a concept introduced by Probabilistic Topic Models [START_REF] Steyvers | Probabilistic topic models[END_REF]. These are a family of generative probabilistic models based on the assumption that documents are generated by a mixture of topics where topics are probability distributions on words. In [START_REF] Aznag | Correlated Topic Model for Web Services Ranking[END_REF], [START_REF] Aznag | Probabilistic Topic Models for Web Services Clustering and Discovery[END_REF], we investigated the use of three probabilistic topic models PLSA, LDA and CTM [START_REF] Blei | A Correlated Topic model of Science[END_REF] to extract latent factors from semantically enriched service descriptions. These latent factors provide a model which represents any web service's description by a vector of terms. The results obtained from comparing the three methods based on PLSA, LDA and CTM showed that the CTM model provides a scalable and interoperable solution for automated service discovery and ranking in large service repositories. The CTM model assumes that the concepts of each service arise from a mixture of topics, each of which is a distribution over the vocabulary. In our work, a topic t is associated with a group of textual concepts (i.e. words) and/or semantic concepts that can appear in service descriptions and can be expressed as a probability distribution over words [START_REF] Aznag | Leveraging Formal Concept Analysis with Topic Correlation for Service Clustering and Discovery[END_REF]. In this paper, we use the Correlated Topic Model (CTM) [START_REF] Blei | A Correlated Topic model of Science[END_REF] to extract latent factors from web service descriptions. These extracted latent factors are then used to compute the similarity between the services. In our context, topic models are used as efficient dimension reduction techniques, which are able to capture semantic relationships between word-topic and topic-service interpreted in terms of probability distributions.

CTM is a probabilistic topic model that enhances base LDA (Latent Dirichlet Allocation) [START_REF] Blei | Latent dirichlet allocation[END_REF] with modeling of correlations between topics.

D. Community detection Algorithms

In the literature, there are numerous algorithms that have been proposed for detecting communities by analyzing the structure of graphs focusing on specific graph properties and particular computing method [START_REF] Fortunato | Community detection in graphs[END_REF]. Such algorithms are generally tested on well known benchmark graphs [START_REF] Lancichinetti | Benchmark graphs for testing community detection algorithms[END_REF] and their results are summarized in different reviews [START_REF] Leskovec | Empirical comparison of algorithms for network community detection[END_REF]. However, there are crucial problems to tackle, related to communities, like the stability of communities' structures [START_REF] Gfeller | Finding instabilities in the com-munity structure of complex networks[END_REF], their dynamic and evolution, etc. Moreover, the analysis of most of community algorithms shows that the objective assessment of the algorithms quality is a complex task and until now, there is no satisfactory answer to the question of choosing the most appropriate algorithm in the context of a given network.

In this work, we therefore consider a set of algorithms, among those who have received the most attention from the scientific community, in order to evaluate empirically our approach.

• Louvain [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF] adopts an agglomerative hierarchical method, but it relies on a slightly different greedy optimization process, and includes an additional aggregation step to improve processing on large networks. • Multistep Greedy (MSG) [START_REF] Schuetz | Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement[END_REF] is a multistep extension of the classical greedy algorithm. It allows the simultaneous merging of several pairs of communities at each iteration. The essential idea is to prevent the premature condensation into few large communities. • greedy clique expansion (GCE) [START_REF] Lee | Detecting highly overlapping community structure by greedy clique expansion[END_REF] works by first detecting a set of seeds in a graph G, then expanding these seeds in series by greedily maximizing a local community fitness function, and then finally accepting only those communities that are not nearduplicates of communities that have already been accepted. • WalkTrap [START_REF] Pons | Computing communities in large networks using random walks[END_REF] uses a distance measure based on random walks and applies a hierarchical agglomerative clustering approach. It is based on the idea that a small random walk will stay inside the community from where it is originating because there are many links inside and few bridges leading outside. • Community Overlap Propagation Algorithm (COPRA) [START_REF] Mcdaid | Detecting highly overlapping communities with model-based overlapping seed expansion[END_REF] is proposed for the first time by Raghavan, Albert and Kumara in [START_REF] Raghavan | Near linear time algorithm to detect community structures in large-scale networks[END_REF]. COPRA relies on a label propagation strategy. The information takes the form of a label, and the propagation mechanism relies on a vote between neighbours. Initially, each node is labelled with a unique value. Then, an iterative process takes place, where each node takes the label which is the most spread in its neighbourhood (ties are broken randomly). This process goes on until convergence, i.e. each node has the majority label of its neighbours. Communities are then obtained by considering groups of nodes with the same label. By construction, one node has more neighbours in its community than in the others. This algorithm is faster than most other algorithms.

• CMN [START_REF] Clauset | Finding community structure in very large networks[END_REF]: this algorithm is for inferring community structure from network topology which works by greedily optimizing the modularity.

E. Problem formulation

Let us consider a web service network represented as a graph where each node has not only a black-box but has a specific information represented as textual data.

Definition II-E.1: A network is a graph G = (V, E), where V is a set of web services and E is a set of edges. The neighbor of a node v, denoted N v , is the set of nodes linked to it.

Definition II-E.2:

A community C on a network G is a subgraph G C = (V C , E C ) such that V C ⊂ V and E C ⊂ {link(x, y) : x ∈ V C ∧ y ∈ N x } such that a given predefined property P (C, G) is true.
The goal of community detection consists of the formalization of one or several properties P (C, G) and the development of a method to compute such constrained subgraph with a minimum complexity. Several algorithms have been proposed considering different P (C, G) which are generally related to both the structure of graph G and its properties like connex components, Cores, etc. It is also well known in information retrieval that the weight of a given document depends on the other documents which constitute the corpus. By analogy, we associate to a given node in the graph a semantic which is computed considering all other nodes in the graph. This latter semantic is called global semantic and consequently, a node will be generally represented by both a local and global semantics.

Definition II-E.3: The semantic of a vertex v is a pair l(v), g(v) where l and g are two functions returning respectively local and global semantic of v.

We will consider in the remainder part of this paper that the local semantic of a node is a vector of words and its global semantic is a mixture of topics. More precisely, we will consider that our nodes belong to predefined categories. they represent the real truth. Consequently, the main tasks are : (1) how to evaluate the compatibility of the computed communities, (2) how to evaluate semantic coherence of a community using topic modeling, and (3) how to evaluate community detection algorithms from the semantic viewpoint.

III. PROPOSED METHOD FOR COMMUNITY DETECTION ALGORITHMS RANKING

This section proposes a method for communities' evaluation by combining classical measures with a topic modeling on the network: topics shared with different nodes of a community. More specifically, we use the Entropy and Purity measures [START_REF] Zhao | Empirical and theoretical comparisons of selected criterion functions for document clustering[END_REF] to evaluate the quality of the detected communities and the Kullback Leibler (KL) Divergence [START_REF] Steyvers | Probabilistic topic models[END_REF] to measure the semantic divergence of these communities.

In the following, we will explain how we calculate the entropy, purity and semantic divergence measures in our context. Let us assume that we have q classes representing the partitioned web services (service domains), f communities which are produced by each algorithm approach and n is the total number of services.

A. Entropy and purity measures

The entropy measures how the various semantic classes are distributed within each community. Given a particular community C j of size n j , the entropy of this community is defined to be:

E(Cj) = - 1 log(q) q i=1 n i j nj log( n i j nj ) (2)
Where q is the number of domains in the dataset, and n i j is the number of services of the ith domain that were assigned to the jth community. The averaged entropy of the algorithm solution is defined to be the weighted sum of the individual community entropies (Equation 3). In general, smaller entropy values indicate better algorithm solutions.

Entropy = f j=1 nj n E(Cj) (3)
The purity measure evaluates the coherence of a community. It is the degree to which a community contains services from a single domain. The purity of C j is formally defined as:

P (Cj) = 1 nj maxi(n i j ) (4)
Where max i (n i j ) is the number of services that are from the dominant domain in community C j and n i j represents the number of services from community C j assigned to domain i.

The purity gives the fraction of the overall community size that the largest domain of services assigned to that community. Thus, the overall purity is the weighted sum of the individual community purities (Equation 5). In general, larger purity values indicate better algorithm solutions.

P urity = f i=1 ni n P (Ci) (5)
The entropy measure is more comprehensive than purity because rather than just considering the number of services in and not in the dominant domain, it considers the overall distribution of all the domains in a given community. Contrary to the purity measure, for an ideal algorithm with services from only a single domain, the entropy of the community will be 0.

B. Semantic divergence measure

Using the correlated topic model, we have associated to each node x a model θ x which is a probability distribution on the topic space. There are several metrics to compute the distance between the semantics of x and y. In this paper, we consider the divergence of Kullback Leibler (KL) [START_REF] Steyvers | Probabilistic topic models[END_REF] defined as follows:

KLD(θ x , θ y ) = T i=1 θ i x log 2 θ i x θ i y ( 6
)
Where θ i x = P (i | x) represents the proprability of the topic i given the node x. KLD is not symetric and KLD = 0 when θ i x = θ i y for all i. In our work, the semantic divergence for each edge in the network is measured by symmetric-KL divergence. Indeed, KL-divergence is a non symmetric measure between two probability distributions, while symmetric-KL divergence obtains the symmetry by adding two KL-divergences. For purpose of expediency, we will use the following symetric distance based on KLD:

SymmetricKL(θ x , θ y ) = 1 2 [KLD(θ x , θ y ) + KLD(θ y , θ x )] (7)

C. Community detection algorithms ranking

Based on the tree measures defined above, we inroduce a new method to evaluate and rank the community detection algorithms. In our context, each algorithm produces several communities which are ranked according to some criterion, i.e., purity/entropy and divergence semantic of a community. Once the web service communities are detected using the selected algorithms described in the Section II-D, we can rank these communities as follows:

1) Community quality evaluation: we rank the communities detected by each algorithm considering both the purity and the entropy measures. Each community is then characterized by the product P urity * (1 -Entropy) and the higher the product value, the better the quality of the community is. 2) Community semantic divergence evaluation: we compute the Community Semantic Divergence, i.e. denoted CSD, of each community, as the mean of the semantic divergence of their pairs (i.e. linked nodes) as defined in the equation 8. Then, we rank communities of each algorithm according to their semantic divergence. The lower Semantic Divergence Community value, the better the community is: it is semantically coherent.

CSD(C

i ) = 1 |E| (x,y)∈E SymmetricKL(θ x , θ y ) (8)
Where E is the set of edge (linked nodes) of the community C i . 3) Community detection algorithms ranking: each criteria, i.e. purity/entropy and semantic divergence, allow us to rank communities of each algorithm. Consequently, we consider that these two rankings are coherent: communities which are pure and with low entropy value are also semantically coherent. Hence, we define the score of a community detection algorithm as a distance between its two ranked lists. The distance between two ranked lists is measured using the Canberra distance [START_REF] Jurman | Canberra distance on ranked lists[END_REF]. Smaller canberra distance values indicate better algorithm solution. In fact, the Canberra distance is used to measure the disarray for ranking lists, where rank differences in the top of the lists should be penalized more than those at the end of the lists. Given two realvalued vectors l, m ∈ R n , their Canberra distance is defined as follows:

Ca(l, m) = N i=1 |l i -m i | |l i | + |m i | (9)
IV. EVALUATION

A. Web services collection

Our experiments are performed out based on real-world web services obtained from the WSDL service retrieval test collection called SAWSDL-TC3 1 . The WSDL corpus consists of 1051 semantically annotated WSDL 1.1 based Web services which cover 8 different application domains. Each web service belongs to one out of nine service domains named as: Communication, Education, Economy, Food, Geography, Medical, Travel and Military. Table I

TABLE I DOMAINS OF WEB SERVICES

In order to construct the web services graph and to apply the community detection algorithms, we start a pre-processing step of the WSDL corpus. The objective of this first step is to identify the functional terms of services, which describe the semantics of their functionalities. WSDL corpus processing consists of several steps: Features extraction, Tokenization:, Tag and stop words removal, Word stemming and Service Transaction Matrix construction.

B. Topic Extraction

To extract topics from web service descriptions, we use the constructed service transaction matrix STM as training data for the CTM model (based on the Blei's implementation 2 , which is a C implementation of CTM using Variational EM for Parameter Estimation and Inference). The choice of the number of topics corresponding to the original dataset has an impact on the interpretability of the results. In CTM model, the number of topics must be decided before the training phase. There are several methods to choose the number of topics that lead to best general performance [START_REF] Steyvers | Probabilistic topic models[END_REF]. In computational linguistics, the measure of perplexity has been proposed to assess generalizability of text models. We computed the perplexity of a held-out test set to choose the optimal number of 1 http://www.semwebcentral.org/projects/sawsdl-tc 2 http://www.cs.princeton.edu/~blei/ctm-c/index.html topics. A lower perplexity score indicates better generalization performance. Assume we have M web services as a held out dataset D test and each web service s contains N d word tokens. More formally, the perplexity for a dataset D test is defined by: [START_REF] Aznag | Correlated Topic Model for Web Services Ranking[END_REF] Where p(w n |s d ) is the probability of having word w n given the d-th. service.

P erplexity = exp - M d=1 N d n=1 log p(w n |s d ) M d=1 N d
Figure 1 shows the perplexity of the held-out data for learned model by varying the number of topics (lower numbers are better). As observed from this figure, the better performance is obtained for K = 90 (where K is the number of topics). Thus, in our experiment, the CTM model was trained to generate 90 topics.

C. Web service communities detection

After the construction of the web services graph, we have applied the community detection algorithms listed in section II-D. In order to avoid the resulted communities, we have filtered them to avoid very small communities; i.e. communities that contain less than 2 nodes, see Table III.

Please remark that the algorithms CMN and COPRA detect few communities, respectively 2 and 3, and 50% of MSG detected communities are small, this number became 40% for WALKTRAP, and finally, only 1 community is small for the Louvain algorithm. According to the number of filtered communities, we divide the used algorithms into two categories: those finding only few filtered communities in contrast to all the other algorithms. Finally, we will consider only the filtered communities during the evaluation process.

D. Prior knowledge based community quality evaluation

Let us compute the purity and the entropy of all detected communities by each used algorithm. The results are given in Table II which may be summarized follows: (1) the communities detected by CMN, MSG and COPRA have similar entropy (very large communities), but CMN is better than MSG and COPRA if we consider the purity viewpoint, (2) The algorithm Louvain detects communities which are better than those computed by CGE and Walktrap. Consequently, we rank the communities detected by each algorithm considering both the purity and the entropy. As described in the section III-C, each community is then characterized by the product P urity * (1 -Entropy) and the higher the product value, the better the quality of the community is. For example, communities rank of those detected by CMN is C3, C1, C2, whereas those detected by Louvain algorithm are ranked as follows : C7, C3, C6, C5, C4, C2, C1, C8. The overall entropy and purity are calculated and drawn in the Figure 3.

E. Community semantic divergence evaluation

Now, let us consider the evaluation of detecting communities according to the semantic divergence of their linked nodes. In fact, we compute the semantic divergence of a community as the mean of those of their pairs, i.e., linked nodes. Figure 2 shows the results for the two kinds of considered algorithms giving more statistical details on the semantic divergence measures within a given community. In Figure 2 (Left), detected communities are enough large and are not semantically homogeneous except the very small one, for example the community 3 detected by the CMN algorithm that contains only 33 nodes. This situation is not the same for an algorithm which detects several communities. In fact, communities must be both enough large and semantically homogeneous. So, an algorithm may detect small and homogeneous communities or large and semantically divergent communities. The obtained values of Community Semantic Divergence measure of each detected II. The Louvain algorithm detects 3 small and 3 enough large communities, but others are larger and divergent. Note that the community C1 is larger, more dense and less divergent than C3. The other algorithms are balancing between enough large and small communities with different semantic divergence. Similarly to the criteria P urity * (1 -Entropy), we can also use the semantic divergence to rank communities detected by each system. How to score algorithms using these two ranking lists?

F. Score of algorithms

We have evaluated the community detection algorithms using two criteria. The first, is based on categories or domains of web services. The second one, focuses on the semantic coherence of a community considering probabilistic topic modelling. Each criterion allows us to rank the detected communities for each algorithm. Consequently, we consider that an algorithm is better if the two ranking of its detected communities are compatible: if a community is well classified by the criterion P urity * (1-Entropy) so, it will be also well ranked by the semantic divergence and vice versa. To achieve this goal we use the Canberra distance which is a measure of disarray for ranked lists [START_REF] Jurman | Canberra distance on ranked lists[END_REF]. Thus, the score of each algorithm is equal to the Canberra distance applied to its two resulted ranking. Of course, this method is useful when the number of detected communities is large because rank differences in top positions need to pay higher penalties than movements in the bottom part of the lists. The score for algorithms that detect more than 3 communities are 4.68 for Louvain, 3.43 for GCE and finally 1.81 for Walktrap. This latter is the best one because even if it does not detect the most homogeneous, but its communities are enough homogeneous and well classified according to the purity and the entropy.

V. CONCLUSION

In this paper, we have proposed a new method for community detection algorithms ranking by combining classical measures with a topic modeling. First, we have ranked the detected communities for each algorithm using purity, entropy and semantic divergence measures. A community is considered well ranked if it has a low entropy value and a high purity. In addition, according to the semantic divergence, the lower Semantic Divergence Community value, the better the community is: it is semantically coherent. Our approach allows us to evaluate the semantic homogeneity of the computed communities that are based only on topology. We can also evaluate the semantic coherence of a community using the semantic divergence measure proposed in this paper. We have tested our approach using several community detection algorithms and considering real world web services.

In future work, we will propose a semantic homogenietybased approach to detect semantic web service communities.

  Fig. 1. Perplexity values obtained for learned CTM model.

Fig. 3 .

 3 Fig. 3. Overall Purity and Entropy for all algorithms.

Fig. 2 .

 2 Fig. 2. Semantic divergence -(Left) algorithms detecting few communities (Right) algorithms detecting several communities

  lists the number of services from each domain.

	#	Domains	Number of services
	1	Communication	59
	2	Economy	354
	3	Education	264
	4	Food	41
	5	Geography	60
	6	Medical	72
	7	Travel	161
	8	Military	40
		Total	1051

  1. Perplexity values obtained for learned CTM model.

	#	Algorithm	#Communities	#Communities (Nodes>=2)
	1	CMN	3	3
	2	LOUVAIN	9	8
	3	MSG	6	3
	4	GCE	7	7
	5	COPRA	2	2
	6	WALTRAP	10	6
			TABLE III
	NUMBER OF COMMUNITIES GENERATED BY EACH ALGORITHM


Nicolas Durand
email: nicolas.durand@univ-amu.fr

Mohamed Quafafou
email: mohamed.quafafou@univ-amu.fr

Frequent Itemset Border Approximation by Dualization

Keywords: frequent itemsets, borders, hypergraph transversals, dualization, approximation

The approach F IBAD is introduced with the purpose of computing approximate borders of frequent itemsets by leveraging dualization and computation of approximate minimal transversals of hypergraphs. The distinctiveness of the F IBAD's theoretical foundations is the approximate dualization where a new function f is defined to compute the approximate negative border. From a methodological point of view, the function f is implemented by the method AM T HR that consists of a reduction of the hypergraph and a computation of its minimal transversals. For evaluation purposes, we study the sensibility of F IBAD to AM T HR by replacing this latter by two other algorithms that compute approximate minimal transversals. We also compare our approximate dualization-based method with an existing approach that computes directly, without dualization, the approximate borders. The experimental results show that our method outperforms the other methods as it produces borders that have the highest quality.

Introduction

The discovery of frequent itemsets was initiated by Agrawal et al. [START_REF] Agrawal | Mining Association Rules between Sets of Items in Large Database[END_REF]. This research field has quickly become an important task of data mining. The problem is to find the sets of items (i.e. attribute values) that appear together in at least a certain number of transactions (i.e. objects) recorded in a database. These sets of items are called frequent itemsets. In that regard, other types of itemsets have been proposed, for instance, closed itemsets [START_REF] Pasquier | Efficient Mining of Association Rules Using Closed Itemset Lattices[END_REF], free itemsets [START_REF] Boulicaut | Free-sets : a Condensed Representation of Boolean Data for the Approximation of Frequency Queries[END_REF] and emerging itemsets [START_REF] Dong | Efficient Mining of Emerging Patterns: Discovering Trends and Differences[END_REF]. Even more important, such itemsets play a key role in the generation of association rules [START_REF] Agrawal | Mining Association Rules between Sets of Items in Large Database[END_REF], supervised classification [START_REF] Ramamohanarao | Efficient Mining of Contrast Patterns and Their Applications to Classification[END_REF], clustering [START_REF] Durand | ECCLAT: a New Approach of Clusters Discovery in Categorical Data[END_REF] and are useful in a broad of range of application fields [START_REF] Han | Frequent pattern mining: current status and future directions[END_REF].

Two issues are important in the discovery of frequent itemsets: (1) the reduction of the search space due to combinatorial explosion and (2) the reduction of the number of generated itemsets to improve efficiency. In this paper, we consider only the second point, with a focus on the set of maximal frequent itemsets corresponding to a subset of frequent closed itemsets [START_REF] Pasquier | Efficient Mining of Association Rules Using Closed Itemset Lattices[END_REF]. The maximal frequent itemsets represent a reduced collection of frequent itemsets, but they are not considered as a condensed representation contrary to the frequent closed itemsets. Indeed, the regeneration of all the frequent itemsets is possible from the maximal frequent itemsets but the database must be read to compute the frequencies. The problem of mining maximal frequent itemsets is NP-hard [START_REF] Yang | The Complexity of Mining Maximal Frequent Itemsets and Maximal Frequent Patterns[END_REF]. The algorithms discovering these itemsets are, for instance, M axM iner [START_REF] Bayardo | Efficiently Mining Long Patterns From Databases[END_REF], P incer-Search [START_REF] Lin | Pincer-Search: A New Algorithm for Discovering the Maximum Frequent Sets[END_REF], M AF IA [START_REF] Burdick | MAFIA: A Maximal Frequent Itemset Algorithm for Transactional Databases[END_REF], GenM ax [START_REF] Gouda | GenMax: An Efficient Algorithm for Mining Maximal Frequent Itemsets[END_REF], Dualize&Advance [START_REF] Gunopulos | Discovering All Most Specific Sentences[END_REF], IBE [START_REF] Satoh | Enumerating Maximal Frequent Sets Using Irredundant Dualization[END_REF] and ABS [START_REF] Flouvat | ABS: Adaptive Borders Search of frequent itemsets[END_REF]. Maximal frequent itemsets are used a lot in recommendation systems where long itemsets describe trends. For example, a list of movies (i.e., a maximal itemset) that many people like can be used as recommendations for other users that share a large overlap of movies with this list.

The maximal frequent itemsets and the minimal infrequent itemsets correspond respectively to the positive border and the negative border of the set of frequent itemsets [START_REF] Mannila | Levelwise Search and Borders of Theories in Knowledge Discovery[END_REF]. These two borders are linked together by the computation of minimal hypergraph transversals (also called "minimal hitting sets") [START_REF] Mannila | Levelwise Search and Borders of Theories in Knowledge Discovery[END_REF][START_REF] De Marchi | Zigzag: a new algorithm for mining large inclusion dependencies in database[END_REF]. Thus, it is possible to switch to a border from the other one. This is called dualization. Algorithms like Dualize&Advance [START_REF] Gunopulos | Discovering All Most Specific Sentences[END_REF], IBE [START_REF] Satoh | Enumerating Maximal Frequent Sets Using Irredundant Dualization[END_REF] and ABS [START_REF] Flouvat | ABS: Adaptive Borders Search of frequent itemsets[END_REF] use dualization to discover maximal frequent itemsets. Indeed, Dualize&Advance computes the maximal frequent itemsets one by one, IBE is an improvement of the previous algorithm as it avoids the redundant frequency checks, and ABS starts computing the positive border and uses an adaptative strategy to decide when it is interesting to switch to the other border. Let us remark that the number of itemsets of the borders can be huge.

This paper extends our previous work in [START_REF] Durand | Approximation of Frequent Itemset Border by Computing Approximate Minimal Hypergraph Transversals[END_REF]. We propose the approach F IBAD1 with the purpose of computing approximate borders of frequent itemsets by leveraging dualization and computation of approximate minimal transversals of hypergraphs. The aim is to reduce the size of borders. The originality of the proposed approach comes from a new fonction we have defined to compute approximate negative borders. From a methodological point of view, the function is implemented by the method AM T HR2 that consists of a reduction of the hypergraph and a computation of its minimal transversals. Next, the approximate positive borders are computed from the approximate negative borders by an exact function. To the best of our knowledge, this is the first time that such approach is proposed leveraging dualization and border approximation. For evaluation purposes, we conduce experiments realized on different data sets, and evaluated the quality of the computed approximate borders by using the distance between the computed approximate borders and the exact ones. Morevover, we study the sensibility of F IBAD to AM T HR. For this, we replace AM T HR with two other methods that compute approximate minimal transversals. We also compare our dualization-based method with an existing approach which computes directly, without dualization, the approximate positive borders.

The rest of the paper is organized as follows. Section 2 defines notations and basic notions necessary for understanding the paper. Related works are discussed in Sect. [START_REF] Agrawal | Mining Association Rules between Sets of Items in Large Database[END_REF]. The proposed approach is detailed in Sect. [START_REF] Bailey | A Fast Algorithm for Computing Hypergraph Transversals and its Application in Mining Emerging Patterns[END_REF]. Section 5 presents our method that computes approximate minimal transversals. The experiments and the results are presented in Sect. [START_REF] Berge | Hypergraphs : Combinatorics of Finite Sets[END_REF]. We conclude and present some future work in Sect. 7.

Preliminaries

Let D = (T , I, R) be a data mining context, T a set of transactions, I a set of items (denoted by capital letters), and R ⊆ T × I is a binary relation between transactions and items. Each couple (t, i) ∈ R denotes the fact that the transaction t is related to the item i. A transactional database is a finite and nonempty multi-set of transactions. Table 1 provides an example of a transactional database consisting of 6 transactions (each one identified by its "Id") and 8 items (denoted A . . . H).

Id Items t1 A C E G t2 B C E G t3 A C E H t4 A D F H t5 B C F H t6 B C E F H
An itemset is a subset of I (note that we use a string notation for sets, e.g., AB for {A, B}). The complement of an itemset X (according to I) is noted X. A transaction t supports an itemset X iff ∀i ∈ X, (t, i) ∈ R. An itemset X is frequent if the number of transactions which support it, is greater than (or is equal to) a minimum threshold value, noted minsup. The set of all-frequent itemsets, noted S, is presented in Definition 1.

Definition 1 (Set of all-frequent itemsets).

Let D = (T , I, R) be a data mining context and minsup be the minimum threshold value. The set of all-frequent itemsets, noted S, is:

S = {X ⊆ I, |{t ∈ T , ∀i ∈ X (t, i) ∈ R}| ≥ minsup}.
The notion of frequent itemset border was introduced by Mannila & Toivonen in [START_REF] Mannila | Levelwise Search and Borders of Theories in Knowledge Discovery[END_REF] (see Definition 2). The borders can be visualized by using the itemset lattice, i.e., the partial order naturally defined on the powerset of I (see Fig. 1). The itemset lattice represents the complete search space. Bd

+ (S) = {X ∈ S | ∀Y ⊃ X, Y / ∈ S}. Bd -(S) = {X ∈ 2 I \ S | ∀Y ⊂ X, Y ∈ S}.
Example 1. Let us take the example of Before the presentation of the relationship between the positive border and the negative border of frequent itemsets, we need to introduce the notion of hypergraph (see Definition 3), the notion of simple hypergraph (see Definition 4) and the notion of minimal transversals of a hypergraph (see Definition 5) [START_REF] Berge | Hypergraphs : Combinatorics of Finite Sets[END_REF].

Definition 3 (Hypergraph and degree of a vertex).

A hypergraph H = (V , E) is composed of a set V of vertices and a set E of hyperedges [START_REF] Berge | Hypergraphs : Combinatorics of Finite Sets[END_REF]. Each hyperedge e ∈ E is a set of vertices included or equal to V . The degree of a vertex v in H, denoted deg H (v), is the number of hyperedges of H containing v. Definition 4 (Simple hypergraph and minimal hyperedges). Let H=(V , E) be a hypergraph. H is simple if for every pair e i , e j ∈ E, e j ⊆ e i ⇒ j = i. min(H) is the set of minimal hyperedges of H w.r.t. set inclusion, i.e., min(H) = {e i ∈ E|(∀e j ∈ E, i = j, e j ⊆ e i ) : e j = e i )}. The hypergraph min(H) is simple.

Definition 5 (Transversal and minimal transversal).

Let H be a hypergraph and τ be a set of vertices (τ ⊆ V ). τ is a transversal of H if it intersects all the hyperedges of H. A transversal is also called a "hitting set". The set of all the transversals of 1 as a hypergraph H. The transactions are the hyperedges and the items are the vertices (see Fig. 2). Here, min(H) = {t 1 , t 2 , t 3 , t 4 , t 5 }. The set of vertices BC is not a transversal. ABC is a transversal but is not minimal (by removing B, it remains a transversal). AC and EF are minimal transversals. The set of all minimal transversals of H is {AB, AC, CD, CF, CH, EF, EH, GH, AF G, BDE}.

H is T r(H) = {τ ⊆ V | ∀e i ∈ E, τ ∩ e i = ∅}. A transversal τ of H is minimal if no proper subset is a transversal of H. The set of all minimal transversals of H is noted M inT r(H).
The computation of the negative border from the positive border and vice versa are presented in Property 1 [START_REF] Mannila | Levelwise Search and Borders of Theories in Knowledge Discovery[END_REF] and Property 2 [START_REF] De Marchi | Zigzag: a new algorithm for mining large inclusion dependencies in database[END_REF]. The term dualization refers to the use of the two previous properties to compute the negative border from the positive border, and vice versa.

Due to the exponential size of the search space, the size of the borders can be huge according to minsup. In this paper, we propose an approach to approximate the borders and to reduce their size. In this way, the exploitation of the itemsets of the borders will be easier. The next section presents the related works and positions our propositions.

3 Related Works

Approximation of the Frequent Itemset Border

The approximation of both positive and negative borders of frequent itemsets has been examined on the basis algorithmic dimension [START_REF] Boley | On Approximating Minimum Infrequent and Maximum Frequent Sets[END_REF]. At first, the computation of the approximate borders is performed directly from the data. In fact, it was shown that there is no algorithm of approximation to compute the positive border with a reasonable approximation factor. Furthermore, the computation of the negative border can be approximated by a greedy algorithm in polynomial time.

Numerous methods have been proposed to reduce the number of itemsets of the positive border. In [START_REF] Hasan | MUSK: Uniform Sampling of k Maximal Patterns[END_REF], the authors have proposed an algorithm to obtain k representative itemsets by uniformly sampling from the pool of all maximal frequent itemsets (i.e., the positive border). They have used a variant of Markov Chain Monte Carlo algorithm. The algorithm simulates a random walk over the frequent itemset partial order graph with a prescribed transition probability matrix, whose values are computed locally during the simulation. In [START_REF] Moens | Randomly Sampling Maximal Itemsets[END_REF], the authors have studied the problem of randomly sampling maximal itemsets without explicit enumeration of the complete itemset search space. They have employed a simple random walk that only allows additions of singletons to the current set untill a maximal itemset is found. An approximation measure, given as input of the algorithm, is used to guide the search for maximal frequent itemsets to different parts of the output space.

In [START_REF] Afrati | Approximating a Collection of Frequent Sets[END_REF], the approximation of a collection of frequent itemsets by the k best covering sets has been studied. The proposed algorithm input is the whole collection of the frequent itemsets or the positive border. The authors have explained the difficulties to use a greedy algorithm to obtain k covering sets belonging to the initial collection. In [START_REF] Zhu | Mining Colossal Frequent Patterns by Core Pattern Fusion[END_REF], the authors have proposed the notion of colossal frequent itemsets. Some small frequent itemsets (defined as core itemsets) are fused into colossal itemsets by taking leaps in the itemset search space. The fusion process is designed to give an approximation to the colossal frequent itemsets. The maximal number of colossal itemsets to discover is given as input. In [START_REF] Jin | Cartesian Contour: a Concise Representation for a Collection of Frequent Sets[END_REF], the authors have proposed a concise representation for a collection of frequent itemsets, called cartesian contour, based on the cartesian product. They have linked the computation of the cartesian contour into a generalized minimum biclique cover problem and they have designed an approximate algorithm with bound. This algorithm takes in input the set of all maximal frequent itemsets and produces a cover. Let us remark that, with this approach, there is no need to set the number of itemsets, contrary to the previous presented works.

Other approaches exist to reduce the number of itemsets but the link with maximal frequent itemsets is not direct. In [START_REF] Vreeken | Krimp: Mining Itemsets that Compress[END_REF], the authors have used the Minimum Description Length (MDL) principle: the best set of itemsets is that set that compresses the database best. A post-treatment step would be needed to obtain maximal itemsets.

Our approach computes an approximate border from a border given as input. In that respect, other algorithms presented in [START_REF] Afrati | Approximating a Collection of Frequent Sets[END_REF] and [START_REF] Jin | Cartesian Contour: a Concise Representation for a Collection of Frequent Sets[END_REF] have borders as input. Nevertheless, we do not try to find some covering sets, but our primary goal is to approximate the border that may contains itemsets, which are not necessarily belong to the initial collection. Our approach has the advantage to generate both the approximate positive border and the corresponding approximate negative border. We have an understanding mapping between the exact border and the approximate border. Consequently, we have the possibility to use several other strategies to approximate borders (see Sect. 4). Moreover, contrary to the most of the previous presented works, we do not need to fix the size of the searched borders.

Approximate Minimal Transversals

The computation of minimal transversals is a central point in hypergraph theory [START_REF] Berge | Hypergraphs : Combinatorics of Finite Sets[END_REF] and represents a NP-hard problem. The algorithms that address this need have been developed by different communities like graph theory [START_REF] Berge | Hypergraphs : Combinatorics of Finite Sets[END_REF][START_REF] Kavvadias | An Efficient Algorithm for the Transversal Hypergraph Generation[END_REF], logic [START_REF] Fredman | On the Complexity of Dualization of Monotone Disjunctive Normal Forms[END_REF][START_REF] Eiter | Hypergraph Transversal Computation and Related Problems in Logic and AI[END_REF] and data mining [START_REF] Dong | Mining Border Descriptions of Emerging Patterns from Dataset-Pairs[END_REF][START_REF] Bailey | A Fast Algorithm for Computing Hypergraph Transversals and its Application in Mining Emerging Patterns[END_REF][START_REF] Hébert | A data mining formalization to improve hypergraph transversal computation[END_REF]. Some works approximate the minimal transversals in order to obtain several ones or only one [START_REF] Ruchkys | A Parallel Approximation Hitting Set Algorithm for Gene Expression Analysis[END_REF]. Some works are based on an evolutionary computation [START_REF] Vinterbo | Minimal Approximate Hitting Sets and Rule Templates[END_REF] where the transversality and the minimality are transcribed both in a fitness function.

In [START_REF] Abreu | A Low-Cost Approximate Minimal Hitting Set Algorithm and its Application to Model-Based Diagnosis[END_REF], the Staccato algorithm computes low-cost approximate minimal transversals with a depth-first search strategy. It has been designed for model-based diagnosis. We have adapted Staccato in order to compute approximated minimal transversals in general and to use it in the experiments (see Sect. 6). The adaptation consists of defining the Staccato's cost function using properties of vertices belonging to the hypergraph (i.e., their degrees). This adaptation allows the definition of vertex's cost. The algorithm sorts the vertices according to their cost value in decreasing order. This vertex ranking is exploited to guide the search. At each selection step, only the first λ (%) vertices of the remaining hypergraph are used. For instance, the algorithm starts by selecting the vertex having the highest cost value. Then, it selects the vertex having the highest cost value in the hypergraph formed by the hyperedges not intersected yet. Etc. The more the λ value is high, the more the result is close to the set of all minimal transversals.

The algorithm presented in [START_REF] Rioult | Nonredundant Generalized Rules and Their Impact in Classification[END_REF], that we call δ-M T miner in reference to M T miner [START_REF] Hébert | A data mining formalization to improve hypergraph transversal computation[END_REF], produces minimal transversals which can miss at most δ hyperedges. It uses a breadth-first search strategy and several itemset discovery techniques (candidate generation, anti-monotone constraint, . . . ). The search space corresponds to the lattice of all subsets of items (i.e., the vertices). The transactions correspond to the hyperedges. The algorithm uses the notion of "anti-support", where the anti-support of an itemset is the number of transactions having no item in common with this itemset. If the anti-support of an itemset is equals to 0 then this itemset is a transversal. The minimality is achieved by using free itemsets [START_REF] Boulicaut | Free-sets : a Condensed Representation of Boolean Data for the Approximation of Frequency Queries[END_REF]. A δ-minimal transversal is a free itemset having an anti-support lower than or equals to δ. Let us note that δ-M T miner is especially efficient on dense hypergraphs (i.e., hypergraphs which strongly intersect).

Staccato and δ-M T miner present two approaches to compute approximate minimal transversals. Alternatively, we propose a method that performs a hypergraph reduction and then computes the minimal transversals of the reduced hypergraph. These transversals are considered as the approximate minimal transversals of the initial hypergraph. The number of missed hyperedges is free, contrary to δ-M T miner. Moreover, using our method, there are no parameters to set in advance.

Hypergraph Reduction

The classical approaches to reduce a hypergraph are edge and hyperedge coarsening [START_REF] Karypis | Multilevel Hypergraph Partitioning: Applications in VLSI Domain[END_REF]. In the edge coarsening approach, pairs of vertices that are present in the same hyperedges are selected to group the vertices. On the contrary, in the hyperedge coarsening approach, a set of independent hyperedges is selected and the vertices that belong to individual hyperedges are contracted together. The hyperedges are initially sorted, and they are visited according to the resulted order. Variants of these two approaches exist. For more information, we refer the reader to [START_REF] Karypis | Multilevel Hypergraph Partitioning: Applications in VLSI Domain[END_REF]. Recently, in [START_REF] Ducournau | A Reductive Approach to Hypergraph Clustering: An Application to Image Segmentation[END_REF], two algorithms of hypergraph reduction have been proposed. The first algorithm, called HR-IH, uses hyperedge intersections. Whereas, the second algorithm, called HR-M ST , uses minimum spanning tree. The hypergraph reduction is a step of the proposed hypergraph clustering method which is applied to image segmentation.

Our hypergraph reduction algorithm uses, as HR-IH, the hyperedge intersections. Nevertheless, only the step of computation of hyperedge intersections is in common. In fact, HR-IH computes a cover of the set of hyperedge intersections and our algorithm selects the most interesting intersections according to a heuristic for finding minimal transversals.

Proposed Approach of Border Approximation

The F IBAD approach is introduced with the purpose of computing approximate borders by dualization. Let f and g be the functions that allow to compute respectively the negative border from the positive border and vice versa:

f : 2 I → 2 I x → M inT r(x) g : 2 I → 2 I x → M inT r(x)
The following diagram allow us to visualize the dualizations between the positive and negative borders:

Bd + (S) f * * Bd -(S) g j j
The principle of F IBAD is to replace the function f by a function f which performs an approximate computation of the negative border. We define the following new function f that uses an approximate minimal transversals computation, noted M inT r:

f : 2 I → 2 I x → M inT r(x)
From the positive border, the function f computes an approximate negative border, noted Bd -(S) (see Definition 6).

Definition 6 (Approximate negative border). Let Bd + (S) be a positive border of frequent itemsets. The approximate negative border, noted Bd -(S), is defined as follows:

Bd -(S) = f (Bd + (S)) = M inT r(Bd + (S)).
The return to a positive border (via the function g) allows to obtain an approximate positive border, noted Bd + (S) (see Definition 7).

Definition 7 (Approximate positive border). Let Bd -(S) be an approximate negative border of frequent itemsets. The approximate positive border, noted Bd + (S), is defined as follows:

Bd + (S) = g( Bd -(S)) = M inT r( Bd -(S)).
From the positive border, the proposed approach produces the approximate negative border Bd -(S) and the corresponding approximate positive border Bd + (S). The following diagram presents all the dualization process:

Bd + (S) Bd + (S) f * * Bd -(S) g j j
Let us remark that we still have an exact dualization between the two approximated borders:

Bd + (S) f * * Bd -(S) g j j
In order to give a general overview of F IBAD, we introduce Algorithm 1 by noting that its main Steps 2 and 3 are treatments considered in the next section. Next, we illustrate F IBAD with Example 4. Example 4. Let us take the example of Table 1 with minsup=3, Bd + (S) = {A, BC, CE, CH, F H}, and let us compute the approximate borders with F IBAD.

Algorithm 1 General overview of FIBAD

Step 1:

H = Bd + (S) = {A, BC, CE, CH, F H} = {BCDEF GH, ADEF GH, ABDF GH, ABDEF G, ABCDEG}
Steps 2 and 3:

Bd -(S) = M inT r(H) = M inT r(H R ).
Let us assume that this computation provides the following result: Bd -(S) = {D, E, G, AF, AH, BF, BH}.

Step 4:

P = M inT r( Bd -(S)) = M inT r({D, E, G, AF, AH, BF, BH}) = {ABDEG, DEF GH}
Step 5: Bd + (S) = P = {ABDEG, DEF GH} = {CF H, ABC}. We can remark that A, B, C and BC are frequent itemsets and here ABC is considered as a frequent itemset. CF H is not frequent (its support is equal to 2) but it is almost frequent. These two itemsets can be interesting for applications like document recommendation. For instance, without our approach, F H is frequent and CF H is not frequent. The item C is potentially interesting. If the items are documents, with our approach, the item C can be recommended to a user.

In short, the distinctiveness of the F IBAD's theoretical foundations is the approximate dualization where the new approximate function f is defined to compute the approximate negative border from the exact positive one. From a methodological point of view, the approximate function is defined as a sequence of two subfunctions: (1) reduction of the hypergraph formed by the complements of the itemsets of the exact positive border (Step 2 of Algorithm 1) and ( 2) computation of the exact minimal transversals of the reduced hypergraph (Step 3 of Algorithm 1). Thus, the resulted transversals are the approximate minimal transversals of the initial hypergraph. They correspond to the approximate negative border as the input hypergraph is formed by the complements of the itemsets of the exact positive border. Afterwards, the approximate positive border is computed from the approximate negative border by an exact function g. In the remainder of this paper, the sequence of the two subfunctions is called AM T HR and is detailed in the next section.

It should be noted that the function f can be supported by any other functions that compute approximate minimal transversals. The use of each alternative functions, instead of AM T HR, leads to a new strategy for computing approximate borders using dualization. In this paper, the function g is unchanged and its experimental section is dedicated to the comparaison of our proposal with other alternative strategies.

Computation of Approximate Minimal Transversals

We propose the method AM T HR to compute the approximate minimal hypergraph transversals (Steps 2 and 3 of Algorithm 1). This method is based on a new algorithm that reduces the initial hypergraph. Our goal is to compute the minimal transversals on the reduced hypergraph which is smaller than the initial one. The proposed algorithm of reduction is specially designed to compute minimal transversals. It exploits the fact that the hyperedges formed by the complements of the itemsets of the positive border, strongly intersect (i.e. the average degree of a vertex is high). For instance, in Example 4, this hypergraph is: {BCDEF GH, ADEF GH, ABDF GH, ABDEF G, ABCDEG}. The proposed method is composed of two steps: (1) Reduction of the hypergraph and (2) Computation of the (exact) minimal transversals of the reduced hypergraph. At the end, the minimal transversals obtained from the reduced hypergraph are declared as the approximate minimal transversals of the initial hypergraph.

Reduction of the Hypergraph

The reduction method is based on both the intersections of the hyperedges and the degree of each vertex. The representative graph [START_REF] Berge | Hypergraphs : Combinatorics of Finite Sets[END_REF] (also called "line-graph") of the hypergraph is thus generated. Let us recall that the representative graph of the hypergraph H is a graph whose vertices represent the hyperedges of H and two vertices are adjacent if and only if the corresponding hyperedges in H intersect. In our algorithm, we add values to the edges of the representative graph.

Algorithm 2 presents the reduction of a hypergraph H. This algorithm is composed of three steps: (1) Computation of the degree of each vertex in H (lines 1-3), ( 2 Select e max = (v maxi, v maxj) having the maximal weight value 14:

for all v ∈ V do 2: Compute degH(v) 3: end for 4: V ← {v i } i = 1, . . . , m; {each v i ∈ V represents ei ∈ E} 5: E ← {}; 6: for all v i ∩ v j = ∅ do 7: E ← E ∪ {(v i , v j )}; 8: w (v i ,v j ) ← v∈{ψ -1 (v i )∩ψ -1 (v j )} degH (
VR ← VR ∪ {ψ -1 (v maxi) ∩ ψ -1 (v maxj)}; 15: ER ← ER ∪ {{ψ -1 (v maxi) ∩ ψ -1 (v maxj)}}; 16:
Delete the edges e ∈ E where v maxi or v maxj is present 17: end while 18: return HR;

Valued Representative Graph Generation (lines 1-9). Let be H = (V, E) a hypergraph (|V | = n and |E| = m). The algorithm constructs a valued graph G=(V , E ) where V = {v i } (i = 1, . . . , m) and E = {e k } (k = 1, . . . , l). A vertex v i represents a hyperedge e i from H. Let be ψ : E → V the bijective function that associates a hyperedge e i to a vertex v i . A hyperedge between v i and v j shows that the intersection between the hyperedges ψ -1 (v i ) and ψ -1 (v j ) (e i and e j from H) is not empty. The weight of an edge is based on the degree of each vertex in the corresponding intersection.

To evaluate the weight of a generated edge, we use the degree of each vertex from the initial hypergraph. The idea is that a vertex very present has a good chance to be in a minimal transversal. This expresses a "degree" of transversality. If the degree of a vertex is equal to the number of hyperedges then this vertex is a minimal tranversal. Let us note that this heuristic is used by several algorithms that compute transversals [START_REF] Abreu | A Low-Cost Approximate Minimal Hitting Set Algorithm and its Application to Model-Based Diagnosis[END_REF][START_REF] Ruchkys | A Parallel Approximation Hitting Set Algorithm for Gene Expression Analysis[END_REF].

The weight of an edge e k = (v i , v j ), noted w e k , is the sum of the degree of the vertices present in the intersection which has led to create this edge (see [START_REF] Abreu | A Low-Cost Approximate Minimal Hitting Set Algorithm and its Application to Model-Based Diagnosis[END_REF]).

w e k = v∈{ψ -1 (v i )∩ψ -1 (v j )} deg H (v).
(

) 1
Generation of the Reduced Hypergraph (lines 10-17). After the creation of the valued representative graph, the algorithm performs a selection of edges with a greedy approach. It selects the edge having the higher weight value while there are edges left in the valued representative graph G. Each selected edge is transformed to a hyperedge of the reduced hypergraph. This hyperedge contains the vertices from H corresponding to the intersection of the two vertices of the edge.

We obtain, at the end, a set of hyperedges corresponding to the reduced hypergraph H R =(V R ,E R ). Let us remark that if several edges have the same weight, the first edge found is selected. The sum of the numbers of occurrences of A, C and E is equals to 12. This is the weight of the edge (v 1 , v 3 ) generated in G. The adjacency matrix of the generated valued graph is: The edge (v 5 , v 6 ) is selected because its weight is maximal (i.e., 15). The edges where v 5 or v 6 are present, are deleted. Thus, we have V R = {B, C, F, H} and E R = {{B, C, F, H}}). The adjacency matrix of the remaining valued graph is:

v 1 v 2 v 3 v 4 v 5 v 6              
v 1 v 2 v 3 v 4 v 5 v 6              
v 1 0 11 12 3 0 0 v 2 11 0 9 0 0 0 v 3 12 9 0 7 0 0 v 4 3 0 7 0 0 0 v 5 0 0 0 0 0 0 v 6 0 0 0 0 0 0 The next selected edge is (v 1 , v 3 ). After the deletion of the edges where v 1 or v 3 are present, there are no remaining edges and the algorithm ends. The reduced hypergraph is H R = (V R , E R ) where V R = {A, B, C, E, F, H} and E R = {{A, C, E}, {B, C, F, H}}). There are 6 vertices (instead of 8) and 2 hyperedges (instead of 6).

Remarks. Algorithm 2 can be implemented in time O(m 3 ) where m is the number of hyperedges of the initial hypergraph. Let us remark that the selection of the edge having the maximal weight value (line 13) can be changed to the selection the first edge of the list of all edges, if the algorithm performs a quicksort of this list according to the weight before line 12. In the worst case, there are

(m 2 -m) 2
hyperedges in the reduced hypergraph. Let us remark that we could also compute min(H R ) because there are no consequences on the next step, ie., the computation of minimal transversals (see Proposition 1).

Minimal Transversal Computation

The last step is the computation of the (exact) minimal transversals of the reduced hypergraph. These transversals correspond to the approximate minimal transversals of the initial hypergraph:

M inT r(H) = M inT r(H R ).
Example 6. Let us continue Example 5. The minimal transversals of H R are: {C, AB, AF , AH, BE, EF , EH}. We consider them as the approximate minimal transversals of H. Let us remark that the (exact) minimal transversals of H are: {AB, AC, CD, CF , CH, EF , EH, GH, AF G, BDE}. Let us note that an approximate minimal transversal is not necessarily a subset of an exact minimal transversal, for instance AH.

Experiments

As noted at the end of Sect. 4, the function f proposed in F IBAD can be supported by any other functions that compute approximate minimal transversals.

In these experiments, we evaluate our dualization-based method that computes approximate borders by using AM T HR. How much this latter is efficient, i.e., the quality of the computed borders? In answering this question, we compute the distance between the computed approximate borders and the exact ones. We also ask the following question: How much F IBAD is sensitive to AM T HR? To reply to this question, we replace AM T HR with other methods that compute approximate minimal transversals. In practice, we consider two alternative strategies based respectively on the δ-M T miner [START_REF] Rioult | Nonredundant Generalized Rules and Their Impact in Classification[END_REF] and Staccato [START_REF] Abreu | A Low-Cost Approximate Minimal Hitting Set Algorithm and its Application to Model-Based Diagnosis[END_REF] algorithms. Finally, we compare our dualization-based method with the CartesianContour algorithm [START_REF] Jin | Cartesian Contour: a Concise Representation for a Collection of Frequent Sets[END_REF] which computes directly, without dualization, the cover of Bd + (S) that corresponds to an approximate positive border. All the experiments have been performed on a Intel Xeon X5560 2.8 GHz with 16GB of memory. The implementations have been developed in JAVA.

Data and Protocol

Data. Four data sets have been used: Mushroom, Chess, Connect and Kosarak. They have been downloaded from the FIMI web site3 . Mushroom contains data on 23 species of gilled mushrooms. Chess contains some strategies for chess sets. Connect contains strategies for the game of connect-4. Kosarak contains anonymized click-stream data of a hungarian on-line news portal. These data sets (see Table 2) have been chosen to cover the different types of existing data sets according to two classifications: Gouda & Zaki [START_REF] Gouda | GenMax: An Efficient Algorithm for Mining Maximal Frequent Itemsets[END_REF] and Flouvat et al. [START_REF] Flouvat | A new classification of datasets for frequent itemsets[END_REF]. The classification proposed by Gouda & Zaki [START_REF] Gouda | GenMax: An Efficient Algorithm for Mining Maximal Frequent Itemsets[END_REF] (types 1, 2 , 3 et 4) is based on the density and on the distribution of the positive border according to the size of the itemsets and the value of the minimum support threshold. Let us note that a data set is dense when it produces long itemsets for high values of the minimum support threshold. The classification proposed by Flouvat et al. [START_REF] Flouvat | A new classification of datasets for frequent itemsets[END_REF] (types I, II et III) studies both the positive border and the negative border. Type I corresponds to data sets having long itemsets in the two borders and most of the itemsets in the two borders have approximately the same size. Type II corresponds to data sets having long itemsets in the positive border and the itemsets of the negative border are much smaller than those of the positive border. Type III is a special case of type I: the itemset size in the two Protocol. For each data set and for some minimum support threshold values, we adopt the following protocol:

1) Exact border computation:

The exact positive border Bd + (S) is the input of the evaluated methods.

Both the exact positive and negative borders, Bd + (S) and Bd -(S), will be used to evaluate the precision of the resulted approximate borders. The more an approximate border is close to the exact one, the more its precision is high. We compute Bd + (S) using the IBE algorithm [START_REF] Satoh | Enumerating Maximal Frequent Sets Using Irredundant Dualization[END_REF]. Afterwards, we compute Bd -(S) from Bd + (S) according to Property 1.

2) Approximate border computation:

Firstly, we compute Bd -(S) and Bd + (S) from Bd + (S) by dualization using AM T HR. Next, this computation is re-done twice by replacing AM T HR by the δ-M T miner algorithm [START_REF] Rioult | Nonredundant Generalized Rules and Their Impact in Classification[END_REF] and the Staccato algorithm [START_REF] Abreu | A Low-Cost Approximate Minimal Hitting Set Algorithm and its Application to Model-Based Diagnosis[END_REF], respectively.

3) Direct computation of approximate positive border:

We compute the cover of Bd + (S) using the CartesianContour algorithm [START_REF] Jin | Cartesian Contour: a Concise Representation for a Collection of Frequent Sets[END_REF]. This cover corresponds to an approximate positive border. 4) Evaluation of the quality of the computed borders.

In this experiments, we use the Border-Dif f algorithm [START_REF] Dong | Mining Border Descriptions of Emerging Patterns from Dataset-Pairs[END_REF] to compute exact minimal transversals when it is needed. Alternatively, we can replace this algorithm by any other one which computes exact minimal transversals without however any change of the resulted borders.

For δ-M T miner (see Sect. 3), the best results have been obtained with δ set to 1, so we have selected this value. Let us recall that for Staccato (see Sect. 3), the more λ is high, the more Staccato is close to the exact solution. Nevertheless, the more λ is high, the more the execution time is high. Thus, we have chosen the highest values of λ before being impracticable: λ=0.8 for Mushroom, λ=0.65 for Chess, λ=0.7 for Connect, and λ=0.95 for Kosarak. CartesianContour (developed in C++) has been downloaded from the web page of one of the authors 4 . There is no need to set the number of itemsets of the computed borders, and the exact positive border is given as input (see Sect. 3). Some statistics are computed: the number of itemsets of the computed border, the average size of the itemsets of the computed border, and the distance between the set of the itemsets of the computed border and the set of itemsets of the exact border.

To evaluate the distance between two borders, we have used the distance of Karonski & Palka [START_REF] Karonski | One standard Marczewski-Steinhaus outdistances between hypergraphs[END_REF] based on the Hausdorff distance. The cosine distance (see ( 2)) has been chosen to compute the distance between two elements (i.e., two itemsets). The distance D between two set of itemsets X and Y is defined in [START_REF] Agrawal | Mining Association Rules between Sets of Items in Large Database[END_REF].

d(X, Y ) = 1 - |X ∩ Y | |X| × |Y | . (2) D(X , Y) = 1 2 {h(X , Y), h(Y, X )} where h(X , Y) = max X∈X {min Y ∈Y d(X, Y )}. ( 3
)
Example 7. Let us consider Example 4 (see Sect. 4). The distance between Bd -(S) and Bd -(S) is equal to 0.395 ( 1 2 (0.29 + 0.5)). The distance between Bd + (S) and Bd + (S) is equal to 0.385 ( 12 (0.18 + 0.59)). Let us recall that our main goal is to produce approximate borders smaller than exact borders, while having the lowest values of the distance to the exact borders.

Results and Discussion

Hypergraph Reduction. Table 3 presents We can observe that the generated hypergraphs H strongly intersect, i.e., the average degree of a vertex is close to the number of hyperedges. These results confirm the observation made at the beginning of Sect. 5.

The number of vertices is almost the same in the initial hypergraph and the reduced hypergraph. The number of hyperedges of the reduced hypergraph is much lower than the number of hyperedges of the initial hypergraph. For instance, on Chess with minsup equals to 50%, there are 3,351 hyperedges instead of 11,463. The "space savings" (i.e., 1

-|E R |
|E| ) is equal to 70.7%. In average, over all the data sets, the space savings is equal to 63%.

We can also see that, in general, the number of minimal transversals of the reduced hypergraph is lower than the number of minimal transversals of the initial The hypergraph reduction is efficient in view of the space saving. Let us recall, that the hyperedges of the reduced hypergraph are selected using a heuristic which favors the search of approximate minimal transversals (see Sect. 5). Thus, our algorithm reduces the hypergraph while keeping the most important parts to find approximate minimal transversals.

Approximate Negative Borders. Figures 3,4, 5 and 6 present, for each data sets, (a) the number of itemsets of the computed negative borders, (b) the distance between the computed negative borders and the exact negative borders, (c) the average size of an itemset of the computed negative borders, and (d) the execution time, according to the minsup value.

We can observe that the cardinality of Bd -(S) is lower than the cardinality of Bd -(S) for each data sets. The itemsets of Bd -(S) are shorter than the itemsets of Bd -(S). On Mushroom and Kosarak, the cardinality of Bd -(S) produced by AM T HR is very close to the cardinality of Bd -(S). The generated itemsets with AM T HR are a little shorter than the itemsets of the exact borders. For 1-M T miner, the cardinality of Bd -(S) is the smallest on Mushroom and Kosarak. Staccato has generated the shortest itemsets on Mushroom but they are numerous. The itemsets produced by 1-M T miner and Staccato are very short on Kosarak. On Chess and Connect, AM T HR and 1-M T miner have produced a similar number of itemsets. These itemsets have a very close average size. We can remark that Staccato has produced a very small number of itemsets, and the average size of the itemsets is very small, on Chess and Connect.

Regarding the distance (between Bd -(S) and Bd -(S)), AM T HR is not the best but it is close to the best algorithm for each data sets. Staccato has obtained the closest borders on Mushroom and Kosarak. This can be explained by the fact that λ has been set to high values for these data sets. This was not possible for Chess and Connect (dense data sets) and this explains why Staccato has the worst results on these data sets. 1-M T miner has produced the closest borders on Chess and Connect. These data sets are dense and they have many long itemsets in the positive borders (see Sect. 6.1). Let us remember that δ-M T miner produces δ-minimal transversals: minimal transversals which can miss at most δ hyperedges (see Sect. 3). δ-M T miner does not control where are the missed hyperedges. On dense data sets, this is not a problem because the possibilities to miss a hyperedge are few many. Let us also note that δ-M T miner is particularly fast on dense data sets.

Concerning the execution time to compute the approximate negative borders, Staccato is the slowest and 1-M T miner is the fastest. AM T HR is relatively fast on Mushroom and Kosarak but not on Chess and Connect.

We can conclude that Staccato and 1-M T miner are the best to compute Bd -(S) respectively on sparse and dense data sets. Nevertheless, AM T HR is close to the best algorithm for each data sets. We can also note that AM T HR is not sensitive to the type of data sets, contrary to the other algorithms. Only the execution time varies (it is higher on dense data sets). The number of itemsets of Bd + (S) with AM T HR is the lowest on Mushroom. On the other data sets, Staccato has generated the lowest number of itemsets. 1-M T miner have produced more itemsets than AM T HR, except for Kosarak. The itemsets of Bd + (S) are longer than the itemsets of Bd + (S). They are the longest with Staccato or AM T HR on each data sets.

Approximate Positive Borders.

AM T HR has obtained the closest Bd + (S) to Bd + (S) on all the data sets. On Connect, 1-M T miner has also obtained good results. On Kosarak, Staccato and 1-M T miner have produced bad results. This can be explained by the small number of itemsets of Bd -(S) and these itemsets are too short. The transition to Bd + (S) produces too few itemsets and these itemsets are too long. The other bad results can be explained by the same remark.

The itemsets of Bd + (S) are longer than the itemsets of Bd + (S) and AM T HR has obtained low distance values. We can say that the approximate positive borders generated by AM T HR contain some itemsets with new items, while being close to the itemsets of the exact positive border. These new items could be interesting for some applications like document recommendation.

Regarding the execution time, on Mushroom, Chess and Connect, 1-M T miner is the slowest and Staccato is the fastest. On Kosarak, 1-M T miner is the fastest and Staccato is the slowest. The execution time of AM T HR is not the best but still correct.

We can conclude that AM T HR is the best to compute Bd + (S). The distances are the lowest, the number is reduced, and the execution time is correct. We explain these results by the characteristics of Bd -(S) produced by AM T HR. We have previously seen that the cardinality of Bd -(S) is a little lower than the cardinality of Bd -(S), and the itemsets of Bd -(S) are a little shorter than the itemsets of Bd -(S). The transition to Bd + (S) produces some itemsets longer than the itemsets of Bd + (S) while being close to Bd + (S). The other algorithms have not done that. Global results. Table 4 presents the average distance, the average number of itemsets, and the average execution time over all the computed borders of all the data sets. The results obtained by the computation of the exact borders by dualization using Border-Dif f , are presented at the last line of the table. We can observe that AM T HR has obtained the lowest average distance, and an average number of itemsets smaller than the average number of itemsets of the exact borders. The average execution time is correct. We can conclude that AM T HR is the best of the used methods in overall. Moreover, we have observed that AM T HR is robust according to the different types of data sets, contrary to 1-M T miner which fails on sparse data sets and Staccato which does not produce good results on dense data sets. Let us remark that we have used Border-Dif f to compute the exact minimal transversals of the reduced hypergraph (Step 3 of Algorithm 1). We have also used it for the computation of the approximate positive border (Step 4 of Algorithm 1). This is possible to use another more efficient algorithm, for instance one of the two algorithms presented in [START_REF] Murakami | Efficient Algorithms for Dualizing Large-Scale Hypergraphs[END_REF], in order to decrease the execution time.

FIBAD vs. CartesianContour. CartesianContour has not been able to compute the approximate positive borders on Chess (minsup < 70%), Connect (minsup < 75%) and Kosarak (minsup < 1%). 17 of the 31 positive borders have been computed. Thus, the values presented in Table 5 have been computed only on these borders. This is why CartesianContour is not present in the previous results and discussion. We observe that the average distances are very close. Nevertheless, the average number of itemsets of the approximate positive borders is the lowest with F IBAD (for information, there are 728.7 itemsets in average in the 17 exact positive borders). We also see that F IBAD is faster than CartesianContour. We can conclude that F IBAD is better than CartesianContour to generate

Conclusion

This paper deals with the problem of approximate borders computed by dualization. At the same time, this is a challenging theoretical problem which may play a valuable role in a wide range of applications. To achieve this goal, we introduced here the F IBAD approach leveraging dualization and computation of approximate minimal transversals of hypergraphs. Its originality comes from a new function we have defined to compute approximate negative borders. For this purpose, we start by reducing the initial hypergraph and, then, we compute its exact minimal transversals. This processing is implemented by the function AM T HR and used by F IBAD as an approximate dualization. To evaluate our approximate dualization method, we replaced AM T HR with other methods that compute approximate minimal transversals. In particular, we considered two alternative methods based on the T miner and Staccato algorithms, respectively. We also compared our method with CartesianContour that computes directly, without dualization, the approximate borders. The experimental results have showed that our method outperforms the other methods as it produces borders which have the highest quality. It produces an approximate positive border smaller than the exact positive border, while keeping a low distance with the exact border. Through these experiments, we have observed that our approach is robust according to the different types of data sets. We can note that for sparse data sets, it is particularly efficient. This point is very interesting for future applications on the Web where most of the constructed data sets are sparse and very large (for instance, data from a web server log file). We have also seen that the proposed approach is able to find potentially interesting items for some applications like document recommendation, for instance. In the future, we will develop a recommendation system using the approximate positive borders generated by F IBAD. In that way, we will able to evaluate the quality of the generated borders in an applicative context.

Fig. 1 .

 1 Fig. 1. Lattice of all subsets of items of I

  The following Proposition 1 results from the definition of the minimal transversals of a hypergraph. Considering a hypergraph H, the minimal transversals of H are the same as the minimal transversals of the set of minimal hyperedges of H[START_REF] Kavvadias | An Efficient Algorithm for the Transversal Hypergraph Generation[END_REF].Proposition 1. Let H=(V , E) be a hypergraph. Then, M inT r(H) is a simple hypergraph and M inT r(H) = M inT r(min(H)).

Fig. 2 .

 2 Fig.2. The hypergraph from the example of Table1

Property 1 (Example 3 .

 13 Negative border and minimal transversals) Bd -(S) = M inT r(Bd + (S)) where Bd + (S) is the hypergraph formed by the items of I (i.e. the vertices) and the complements of the itemsets of the positive border of S (i.e. the hyperedges). Property 2 (Positive border and minimal transversals) Bd + (S) = M inT r(Bd -(S)) where Bd -(S) is the hypergraph formed by the items of I (i.e. the vertices) and the itemsets of the negative border of S (i.e. the hyperedges). Let us compute Bd -(S) from Bd + (S) with our running example. Bd -(S) = M inT r(Bd + (S)) = M inT r({A, BC, CE, CH, F H}) = M inT r({BCDEF GH, ADEF GH, ABDF GH, ABDEF G, ABCDEG}) = {D, G, AB, AC, AE, AF, AH, BE, BF, BH, CF, EF, EH}. Let us compute Bd + (S) from Bd -(S). Bd + (S) = M inT r(Bd -(S)) = M inT r({D, G, AB, AC, AE, AF, AH, BE, BF, BH, CF, EF, EH}) = {BCDEF GH, ADEF GH, ABDF GH, ABDEF G, ABCDEG} = {A, BC, CE, CH, F H}.

  Require: a positive border of frequent itemsets, Bd + (S) Ensure: the approximate negative and positive borders, Bd -(S) and Bd + (S) {Steps 1, 2 and 3: Dualization using function f } 1: H=Bd + (S); {Computation of the hypergraph from Bd + (S)} 2: HR=HR(H); {Reduction of the hypergraph H} 3: Bd -(S)= M inT r(H)=M inT r(HR) {Computation of the approximate negative border ; The approximate minimal transversals of H are the exact minimal transversals of HR} {Step 4 and 5: Dualization using function g} 4: P =M inT r( Bd -(S)); {Computation of the exact minimal transversals of Bd -(S)} 5: Bd + (S)=P ; {Computation of the approximate positive border} 6: return Bd -(S) and Bd + (S);

  ) Generation of the valued representative graph of H (lines 4-9), and (3) Generation of the reduced hypergraph from the valued representative graph (lines 10-17). Algorithm 2 HR (Hypergraph Reduction) Require: a hypergraph H=(V , E) where |V |=n and |E|=m Ensure: the reduced hypergraph HR 1:

v); 9 : end for 10 :

 910 VR ← {}; 11: ER ← {}; 12: while E = ∅ do 13:

Example 5 .

 5 Let us consider the example of Table1 asa hypergraph H (6 hyperedges, 8 vertices). The transactions are the hyperedges e k and the items are the vertices v i . First, the degree of each vertex is evaluated: occur[A] = 3, occur[B] = 3, occur[C] = 5, occur[D] = 1, occur[E] = 4, occur[F ] = 3, occur[G] = 2 and occur[H] = 4. Then, the intersections between the hyperedges are computed. For instance, ψ -1 (v 1 ) ∩ ψ -1 (v 3 ) = e 1 ∩ e 3 = {A, C, E}.

  borders is very close for very low minimal support values. Type III captures the notion of sparseness. Type I and Type II correspond to dense data sets. Chess and Connect are dense data sets. Kosarak is a sparse data set. Let us remark that Mushroom is special: Flouvat et al. classify it in Type II (as Connect) but Gouda & Zaki classify it in an other type, Type 4. Mushroom is between dense data sets and sparse data sets.

  the hypergraphs and the transversals computed by F IBAD. Let us recall that for an experiment (a data set and a minsup value) the computed hypergraph, noted H = (V , E), correspond to the complement of the itemsets of the positive border (V ⊆ I and E = Bd + (S)). The reduced hypergraph of H, noted H R , is computed with Algorithm 2 (H R = HR(H)). For each data sets and minsup values, we have the number of hyperedges of H (|E|), the number of vertices of H (|V |), the average degree of a vertex (deg H (v)), the number of minimal transversals of H (|M inT r(H)|), the number of hyperedges of min(H R ) (|E R |), the number of vertices of min(H R ) (|V R |) and the number of minimal tranversals of H R (|M inT r(H R |). In order to better show the impact of the reduction, we consider here min(H R ) instead of H R . The computation of min(H R ) has no consequences on the computation of minimal transversals (see Proposition 1).

  Figures 7,[START_REF] Boulicaut | Free-sets : a Condensed Representation of Boolean Data for the Approximation of Frequency Queries[END_REF], 9 and 10 present, for each data sets, (a) the number of itemsets of the computed positive borders, (b) the distance between the computed positive borders and the exact positive borders, (c) the average size of an itemset of the computed positive borders, and (d) the execution time, according to the minsup value.

Fig. 3 .

 3 Fig. 3. Negative borders computed on Mushroom

Fig. 4 .

 4 Fig. 4. Negative borders computed on Chess

Fig. 5 .

 5 Fig. 5. Negative borders computed on Connect

Fig. 6 .

 6 Fig. 6. Negative borders computed on Kosarak

Fig. 7 .Fig. 8 .Fig. 9 .Fig. 10 .

 78910 Fig. 7. Positive borders computed on Mushroom

Table 1 .

 1 Example of transactional database.

Table

Table

Table 2 .

 2 Data sets used in the experiments.

	Data set	|T |	|I| Avg. |ti| Gouda & Zaki Flouvat et al.
	Mushroom 8,124	119	23.0	type 4	type II
	Chess	3,196	75	37.0	type 1	type I
	Connect 67,557	129	43.0	type 2	type II
	Kosarak 990,002 41,270	8.1	type 3	type III

Table 3 .

 3 Computed hypergraphs and transversals. This is not always true. For instance, on Mushroom with minsup equals to 10%, there are 3,103 minimal transversals for H and 3,125 for H R . Let us take an example to illustrate this point. The minimal transversals of the hypergraph {ABC, ABD, ABE, ABF, ABG} are {A, B, CDEF G}. There are 3 minimal transversals. Now, let us consider the hypergraph {AC, ABD, BG}, there are 4 minimal transversals ({AB, AG, BC, CDG}).

				Initial hypergraph		Reduced hypergraph
	Data set Minsup	|E|	|V | degH(v) |M inT r|	|ER|	|VR| |M inT r|
		(%)			(avg.)	(H) (min(HR)) (min(HR))	(HR)
	Mushroom	25	105	115	100.1	652	47	115	581
		20	158	115	150.4	1,012	63	115	879
		15	321	115	303.8	1,816	118	115	1,478
		10	558	118	525.1	3,103	235	118	3,125
		5 1,452	118 1,347.3	9,034	580	118	8,801
		3 2,627	118 2,414.1 16,361	1,075	118 15,674
		2 3,761	118 3,422.6 23,208	1,600	118 21,571
	Chess	80	226	66	200.1	398	73	66	284
		75	489	74	437.3	742	155	73	446
		70	898	74	796.1	1,318	273	73	794
		65 1,779	74 1,568.7	2,644	594	73	1,713
		60 3,374	74 2,949.3	4,793	1,017	74	2,809
		55 6,261	74 5,429.4	8,435	1,955	73	4,943
		50 11,463	74 9,875.5 15,224	3,351	74	8,864
	Connect	80	676	127	611.8	975	203	127	594
		75	961	127	861.6	1,317	292	127	797
		70 1,220	127 1,083.2	1,672	374	127	989
		65 1,588	127 1,400.1	2,196	467	127	1,289
		60 2,104	127 1,849.3	2,937	657	127	1,758
		55 2,836	127 2,481.1	3,859	827	127	2,145
		50 3,748	127 3,259.2	5,041	1,072	127	2,871
		45 4,720	127 4,079.1	6,364	1,448	127	3,747
		40 6,213	127 5,342.9	8,358	1,887	127	4,735
	Kosarak	5	8	218	7.9	240	4	218	234
		4	13	218	12.8	268	5	218	244
		3	17	294	16.8	380	7	294	365
		2	30	490	29.8	780	15	490	759
		1	88	987	87.7	2,298	41	987	2,241
		0.5	305 2,952	304.6 14,791	146	2,952 14,524
		0.4	468 2,952	467.4 25,082	228	2,952 24,938
		0.3	814 3,804	813.2 51,770	394	3,804 51,567
	hypergraph.

Table 4 .

 4 Global results obtained on all the computed approximate borders.

	Method	Avg. distance Avg. number of itemsets Avg. time (sec.)
	AM T HR	0.323	3342.6	15.05
	1-M T miner	0.384	2191.1	1.53
	Staccato	0.452	1989.4	41.63
	Border-Dif f	-	4492.1	28.88

  Table 5 presents the average distance, the average number of itemsets, and the average execution time over several approximate positive borders computed by F IBAD and CartesianContour. Indeed,

		16000			1-MTminer
		14000				Staccato AMTHR
		12000			Border-Diff
	#itemsets	6000 8000 10000
		4000
		2000
		0
		50	55	60	65	70	75	80
					minsup

Table 5 .

 5 F IBAD vs. CartesianContour.

	Approach	Avg. distance Avg. number of itemsets Avg. time (sec.)
	F IBAD	0.289	286.6	9.67
	CartesianContour	0.283	606.2	49.31

Frequent Itemset Border Approximation by Dualization

Approximate Minimal Transversals by Hypergraph Reduction

Frequent Itemset Mining Implementations, http://fimi.ua.ac.be/data/

http://www.cs.kent.edu/∼lliu/sourceCode.html