Bruno Donassolo
email: bruno.donassolo@orange.com

Ilhem Fajjari
email: ilhem.fajjari@orange.com

Arnaud Legrand
email: arnaud.legrand@imag.fr

Panayotis Mertikopoulos
email: panayotis.mertikopoulos@imag.fr

Fog Based Framework for IoT Service Provisioning

Keywords: Fog Computing, IoT, application placement, service provisioning 1 Statista

To this day, the Internet of Things (IoT) continues its explosive growth. Nevertheless, with the exceptional evolution of traffic demand, existing infrastructures are struggling to resist. In this context, Fog computing is shaping the future of IoT applications. It offers nearby computational, networking and storage resources to respond to the stringent requirements of these applications. However, despite its several advantages, Fog computing raises new challenges which slow its adoption down. Hence, there is a lack of practical solutions to enable the exploitation of this novel concept. To deal with this shortcoming, we propose FITOR, an orchestration system for IoT applications in the Fog environment. This solution builds a realistic Fog environment while offering efficient orchestration mechanisms. In order to optimize the provisioning of Fog-Enabled IoT applications, FITOR relies on O-FSP, an optimized fog service provisioning strategy which aims to minimize the provisioning cost of IoT applications, while meeting their requirements. Based on extensive experiments, the results obtained show that O-FSP optimizes the placement of IoT applications and outperforms the related strategies in terms of i) provisioning cost ii) resource usage and iii) acceptance rate.

I. INTRODUCTION

The Internet of Things (IoT) is an emerging concept that promises to revolutionize our daily lives and the way we interact with our surrounding. It refers to the interconnection of heterogeneous end devices, especially everyday life objects, that are addressable and controllable via Internet. The number of such devices is expected to reach 75 billion(s) by 2025, 1 an explosion in size which will be inevitably the catalyst for the transformation of Cloud infrastructures. Being established too far away, traditional data centers struggle to meet stringent bandwidth and latency requirements of IoT systems. This is why the deployment of a new generation of infrastructure is crucial to deal with the huge amount of data transmitted by sensors and connected devices.

In this context, Fog Computing [START_REF] Bonomi | Fog computing and its role in the internet of things[END_REF] is shaping the future of IoT solutions. To deal with the prolific growth of the generated traffic, the Cloud infrastructure is expanded to handle the processing in the surrounds of end devices. This augmented architecture provides nearby resources, performing analytics tasks and data storage. The so-called Fog nodes can be whether physical or virtualized. They are deployed between end devices and centralized services hosted by the Cloud. Note that a subset of Fog nodes are more specialized, dedicated and hence can be placed even closer to the end devices than the more powerful Fog nodes. They are called Mist nodes [START_REF] Iorga | Fog computing conceptual model[END_REF]. In doing so, a decentralized processing will be supported while taking advantage of the Cloud utilities and virtualization technology. It is straightforward to see that, the establishment of such a decentralized processing will ensure enhanced network performance, lower operational costs, alleviated network congestion and improved survivability.

However, such a design raises new challenges in terms of resource management and application orchestration. In this context, the orchestration is a keystone of Fog PaaS (Platform as a Service): It corresponds to designing, creating, and delivering one or more service components that, put together, offer an end-to-end service. Nevertheless, the heterogeneity, the dynamic nature and the large-scale deployment of the Fog environment make existing orchestration solutions, such as Kubernetes 2 and Docker Swarm 3 , even mature, ill-adapted.

Recently, several researches [START_REF] Wang | Enorm: A framework for edge node resource management[END_REF] [4] [START_REF] Wen | Fog orchestration for internet of things services[END_REF] have proposed conceptual Fog frameworks for IoT service orchestration. However, most of them do not address the problematic in a practical and concrete manner. In this paper, we propose a Fog computing based framework, referred to as FITOR: Fog-IoT ORchestrator which integrates end devices and Fog nodes in the Cloud ecosystem to create a Fog environment. FITOR provides various functionalities, which deal with the provisioning of IoT applications in a Fog infrastructure while meeting non-functional requirements in terms of network performances (e.g., latency, throughput) and IT resources (e.g., CPU, memory).

The contribution of this paper is twofold: first, we design and implement FITOR, an orchestration framework for the automation of the deployment, the scalability management, and migration of micro-service based IoT applications. Second, we propose a provisioning solution for IoT applications that optimizes the placement and the composition of IoT components, while dealing with the heterogeneity of the underlying Fog infrastructure.

In order to optimize the placement of micro-service based IoT components and their composition, we formulate the problem as an Integer Linear Problem. Since this problem is computationally intractable, the optimal solution could only be generated in small-sized instances of IoT applications and Fog infrastructures. We, therefore, propose an Optimized Fog Service Provisioning strategy named O-FSP which adopts a divide and conquer approach. Its main objective is to minimize the cost of Fog-enabled IoT applications' provisioning while responding to their requirements in terms of resources and network performance. To do so, O-FSP exploits the gathered information about the current state of the sensors, actuators, Fog nodes, and the condition of IT and network resources to select the best placement of micro-services on Fog resources.

The performance of O-FSP is validated by robust experiments within the proposed FITOR platform and compared with several classical approaches: Uniform, Best-Fit and Min-latency. The results obtained highlight the strength of our strategy in terms of i) acceptance rate of IoT applications, ii) provisioning cost, and iii) CPU usage.

The remainder of this paper is organized as follows.

In Section II, we will summarize the related work dealing with this problematic. In Section III we describe FITOR, a Fog based framework for IoT applications orchestration. In Section IV, we will formulate the IoT service provisioning problem. Then, our proposal O-FSP will be described in Section V. Performance evaluation based on experimentation will be detailed in Section VI.

II. RELATED WORK

Several Fog architectures have been put forward in the literature. In this respect, in [START_REF] Wang | Enorm: A framework for edge node resource management[END_REF], the authors propose a prototype framework for Fog computing, named Enorm. The latter centralizes the management of applications and edge nodes in the Cloud, while offloading the workload to the edge nodes closer to the end user. In addition, an auto-scaling mechanism is implemented to scale up/down the resources based on the network latency and the tasks' execution time. In [START_REF] De Brito | A service orchestration architecture for fogenabled infrastructures[END_REF], Inspired by ETSI NFV MANO reference architecture, the authors develop a service orchestration system for Fog computing. The architecture relies on two main components: i) a Fog Orchestration Agent (FOA) which runs in the Fog node and locally manages the services, and ii) a Fog orchestrator (FO) which makes use of a centralized view to manage the services and Fog nodes. In [START_REF] Yangui | A platform as-a-service for hybrid cloud/fog environments[END_REF], a set of extensions to the Cloud Foundry architecture are proposed to cope with the Fog environment. These extensions include new modules to: i) develop applications, ii) deploy the components either in the Cloud or Fog using containers, and iii) manage the application during its execution. [START_REF] Tomovic | Software-defined fog network architecture for iot[END_REF] proposes an SDN-based orchestration solution for Fog environments. To do so, the environment is split into several Fog regions managed by an SDN controller. The latter is responsible for keeping an updated view of the Fog nodes, collecting information about their capabilities (CPU, RAM, network, etc.), and orchestrating IoT applications while taking into consideration the business policies defined by applications. [START_REF] Saurez | Incremental deployment and migration of geodistributed situation awareness applications in the fog[END_REF] proposes a Foglet programming infrastructure for Fog environments. Foglet provides a programming interface to be used by developers and a runtime system to manage the application execution.

Although the Fog computing concept has been relatively well investigated, the provisioning of IoT applications in the Fog environment remains an open issue. This is due to the distributed nature of Fog nodes and the uncertainty induced by multiple factors, such as end device volatility, peak resource demands and utilization gaps. It is worth noting that service provisioning in Cloud computing is mature [START_REF] Fajjari | Cloud networking: An overview of virtual network embedding strategies[END_REF] [10] and may offer interesting insights. However, there are key differences between Cloud services and Fog services that prevent the use of these methods in Fog context. Indeed, the type and size of Cloud resources are very different from Fog resources. In this respect, Cloud resources are usually homogeneous and centralized in data centers, while their counterparts in Fog computing are heterogeneous and distributed in a large area. In addition, Cloud applications are less challenging than IoT services running in the Fog. The latter are generally latencysensitive. They require location-awareness, mobility support and a distributed coordination between geo-distributed end devices.

To the best of our knowledge, very few works have been carried out to specifically deal with the Fog service provisioning problem. In [START_REF] Skarlat | Towards qos-aware fog service placement[END_REF], the authors put forward the concept of Fog colonies to address the Fog service placement problem (FSPP), while taking into account Quality of Service constraints. In [START_REF] Yousefpour | Qos-aware dynamic fog service provisioning[END_REF], two heuristics are proposed to efficiently deal with the FSPP while reducing the cost. In [START_REF] Skarlat | Optimized iot service placement in the fog[END_REF], the authors formulate an optimization problem to deal with the placement of IoT applications over Fog resources, while considering the heterogeneity of the resources and applications. Then, a greedy first fit heuristic and a genetic algorithm are proposed to solve the proposed optimization problem. In [START_REF] Xia | Combining hardware nodes and software components ordering-based heuristics for optimizing the placement of distributed iot applications in the fog[END_REF], the authors formulate the FSPP problem with an objective function that aims to minimize applications' average response time. The problem is addressed using two placement algorithms and two combinable heuristics to accelerate the placement decision making process.

A key underlying limitation of the aforementioned Fog service provisioning solutions [START_REF] Skarlat | Towards qos-aware fog service placement[END_REF]- [START_REF] Xia | Combining hardware nodes and software components ordering-based heuristics for optimizing the placement of distributed iot applications in the fog[END_REF], which serve as the main motivation of our work, is that none of them have been implemented nor do they tackle the issue of orchestrating heterogeneous Fog resources in a practical and concrete manner. Our work aims at complementing this, by offering a general centralized framework for holistic Fog resource orchestration.

Our solution provides high level abstractions of the interactions between software components and end devices, which enable flexible deployment of management approaches. To gauge the efficiency of our FITOR architecture, we design and implement an efficient provisioning approach which exploits the gathered statistics, to optimize the allocation of IoT application components while considering their requirements.

III. FOG-IOT ORCHESTRATOR ARCHITECTURE

Fig. 1 provides an overview of the FITOR architecture. Our proposed solution is device-aware, and hence, handles the heterogeneity of the Fog environment. Application components can be easily deployed on end devices and Fog nodes. It is worth noting that FITOR works across two main layers: 1) Fog layer: can be subdivided into two sublayers: i) High Fog layer composed of distributed Fog nodes providing nearby computational and storage resources and ii) Lightweight Fog Layer (Mist) encompassing more specialized, dedicated nodes that provide low computational resources. The so-called Mist nodes are placed closer to the end devices, and 2) End devices: includes the sensors, which collect information about the environment, and the actuators which have an effect on it.

In our context, an IoT application deployed in a Fog environment is composed of a set of micro-services which are containerized and running on the nodes of the infrastructure. We adopt an actor-based model to develop our IoT applications, where each micro-service is modelled as a set of actors and communicates, with other micro-services, through flows. An actor is characterized by a private internal state and a set of communication ports through which tokens are transmitted.

FITOR supports various orchestration mechanisms to deal with the stringent requirements of such applications. The global architecture for the proposed orchestration framework is depicted in Fig. 1 showing its components and their roles:

1) The Service Descriptor: This component aims to describe the IoT application, its building components and its requirements. Indeed, the developer needs to describe the actors, their requirements in terms of both location and computational effort, and how data should circulate between them. It is worth noting that, in order to ensure a guaranteed QoS, network related requirements could be specified during the description of links between the actors. Specifically, CPU/RAM affinity and capacity can be specified for the actors, while latency and bandwidth can be defined for the links.

2) The Service Deployer: Once the description is submitted, this component handles the mapping between the application components (i.e., actors, communications) and the nodes hosting the latter. Its main objective consists in optimizing the placement of actors and their links while considering their location, computational and network requirements.

3) The Service Manager: A running application is exposed to the uncertainty of the Fog environment. In addition, its components may change in response to the variation of data sources or internal transformation. To deal with this dynamicity, the applications containers are continually monitored in order to be managed while considering, in real-time, the environment evolution. To do so, scale out/in actions can be triggered to allocate or de-allocate resources. Besides, migration actions could be triggered when necessary.

4) The Infrastructure Monitor: This is responsible for sketching out the telemetry information by extracting several resource metrics from the Fog nodes and links. To do so, it makes use of various probes to get real-time information about both physical resources and their running containers. In our context, we consider two main categories of metrics to observe: i) Host-related metrics, concerning all information about the host and container in which the application is running. This includes: CPU, RAM, disk, etc. ii) Network related metrics, corresponding to the end-to-end latency and bandwidth, which are crucial and thus, mandatory to be collected during the application execution. It is straightforward to see that two views of resources are provided: i) reserved resources, which concerns the allocated capacities in terms of compute, storage and RAM, ii) the real resource capacities consumed by containers.

5) The Fog Node: This can be hosted by a server, a network equipment, or even an end device. High Fog nodes are capable of running containerized (e.g., docker) micro-services while Mist nodes are used as a bare-metal equipment. The so-called runtimes are responsible for the execution of actors. They may handle, for example, the actor scheduling and the data transport message parsing. It is worth noting that one runtime may concurrently run multiple actor instances belonging to different applications. A runtime is characterized by a set of capabilities (e.g., access to a camera, access to a disk, etc.) and performances metrics (e.g., CPU, memory) which are monitored by a set of tools. These tools collect, aggregate, process and export information about all components in the Fog node, including the physical host, running containers and network bandwidth and latency.

IV. PROBLEM STATEMENT A. Infrastructure and Application Models

We model our Fog infrastructure P as an undirected graph denoted by G P = (V P , E P ), where V P and E P are respectively the sets of physical equipment and their connected links. Note that V P = (F P ∪ S P ), where F P corresponds to the set of Fog nodes, while S P encompasses the sensors and actuators in the end device layer.

Each physical node v ∈ V P is characterized by its i) residual processing power W (v), ii) residual memory M (v), and iii) kind K(v) and iv) geographic location G(v). 4 We consider two types of resources: edge sensor/actuator (end device) and Mist/Fog node. Likewise, each physical link l ∈ E P is characterized by its bandwidth capacity B(l) and its latency L(l).

Similarly, a Fog-Enabled IoT application A consists of multiple interconnected components (i.e., micro-services). It is modelled as a directed acyclic graph (DAG) G A = (V A , E A ), where V A and E A are respectively the sets of services and their logical links. Within the IoT application A, each service a ∈ V A is associated with the required processing power W (a) and memory M (a), its kind K(a), and geographic location G(a). We also define T rate (a) and T size (a) as the number of tokens per second sent by service a and its token size, respectively. We recall that the kind specifies the requirement of a service to be executed on a specific category of resource. Finally, each link e ∈ E A is characterized by a data rate B(e), in terms of bandwidth, and L(e), in terms of latency.

B. Problem formulation

In this section, we formulate the provisioning problem of a Fog-enabled IoT application A, modelled by the graph G A , in the Fog infrastructure P, denoted by the graph G P . First, we take into consideration the fact that all the physical nodes and link capacities (i.e. processing, memory and bandwidth) in P are limited. In fact, P is able to host a limited number of A while responding to the requested QoS. Consequently, an optimized G A provisioning in G P is crucial in order to maximize the acceptance rate while minimizing the cost of resources.

In what follows, we will use the following notation:

• α av is a binary variable indicating whether the service, a ∈ V A , is assigned to the physical node, v ∈ V P , or not. • N vx denotes the set of admissible physical paths from v to x, (v, x) ∈ V 2 P . Note that k 2 denotes the family of all ordered pairs of elements within set We recall that T rate is the number of tokens sent per second by a s (e) and T size is the size of each token.

k (i.e. k = {(v, x) ∈ V 2 P : v = x}). • N
The provisioning of services is constrained so that for each IoT application A, a service must be hosted in one physical node. Formally,

v∈V P α av = 1, ∀a ∈ V A (IV.1)
A service a ∈ V A can be hosted in the physical node v ∈ V P , if i) the available residual resources (i.e. W (v) and M (v)) are at least equal to those required (i.e. W (a), M (a)) and ii) a has the same kind and geographical location as v. Formally,

∀v ∈ V P a∈V A W (a)α av ≤ W (v) a∈V A M (a)α av ≤ M (v) (IV.2) (K(v) -K(a))α av = 0, ∀v ∈ V P , ∀a ∈ V A (IV.3) (G(v) -G(a))α av = 0, ∀v ∈ V P , ∀a ∈ V A (IV.4)
We assume that a logical link e ∈ E A between a service a s (e) and a service a d (e) is embedded in a physical path n ∈ N between v and x. Formally,

n∈N β en = 1, ∀e ∈ E A (IV.5)
A logical link e ∈ E A must be embedded in a single path n ∈ N vx . Such as a s (e) ∈ V A is hosted in physical node v ∈ V P and a d (e) ∈ V A is hosted in physical node x ∈ V P . Formally,

∀e ∈ E A , n ∈ N vx β en ≤ α as(e)v β en ≤ α a d (e)x (IV.6)
Each physical link l ∈ E P is characterized by the used bandwidth B used (l) by the IoT application A. Formally,

B used (l) = e∈E A B(e) n∈N ∆ ln β en , ∀l ∈ E P (IV.7)
Moreover, each physical link l ∈ E P cannot host more than its capacity. Formally,

B used (l) ≤ B(l), ∀l ∈ E P (IV.8)
Each physical path n ∈ N is characterized by an end-toend delay, L(n). The latter corresponds to the sum of delays of its forming l ∈ E P . Formally,

L(n) = l∈E P ∆ ln L(l), ∀n ∈ N (IV.9)
Finally, a logical link e ∈ E A must be be hosted in a path n, ensuring an end-to-end delay lower than that required by itself.

n∈N L(n)β en ≤ L(e), ∀e ∈ E A (IV.10)

Our objective is to generate, for each application A, the best possible provisioning solution while minimizing the placement cost in terms of allocated resources within P. For this reason, we define our objective function as follows,

min ∀v∈V P ,∀l∈E P (C tot W + C tot M + C tot B ) (IV.11)
The C tot W represents the processing cost of the application' components in the infrastructure. C tot M is related to the cost of the memory required by the components. Finally, C tot B corresponds the total communication cost for data transfer between applications components. Also, we define the costs associated to the physical infrastructure as i) a cost for processing C W (v), ii) a cost for memory C M (v), and iii) a cost for data transfer C B (l). Formally,

C tot W = v∈V P a∈V A C W (v)W (a)α av (IV.12) C tot M = v∈V P a∈V A C M (v)M (a)α av (IV.13) C tot B = l∈E P C B (l)B used (l) (IV.14) V. PROPOSAL: O-FSP
In this section, we will detail our proposal named Optimized Fog Service Provisioning (O-FSP) to resolve the formulated problem in the previous section. Our strategy is a greedy approach which aims to incrementally construct an optimized Fog service provisioning solution. To achieve its objective, O-FSP proceeds as follows. First, the problem is split into a set of solution components that are sorted: solving a solution component corresponds to building a small part of the final solution. Then, each solution component is greedily placed while considering its requirements. Finally, the process is repeated until all solution components are provisioned. It is worth noting that O-FSP rejects a Fog service A as soon as it fails to find a placement to one of its component. O-FSP is summarized in pseudo-code form in algorithm 1. In the following, we will detail each stage.

A. Fog service decomposition stage

The Fog-enabled IoT application (i.e., Fog service) A is subdivided into a set of k components according to |V A | and |E A |. The aforementioned subsets are called solution components and are denoted by {C i } 1≤i≤k . In order to do this, O-FSP selects first the subset of sensor/actuator nodes and their corresponding incoming/outgoing links. The latter are, then retrieved from the graph. The remaining A's topology, devoid of the aforementioned solution components, is called

Algorithm 1: O-FSP pseudo-algorithm 1 Input: G A , G P , N max 2 Output: S best 3 S best ← ∅ 4 {S i } 1≤i≤Nmax ← ∅ 5 {C i } 1≤i≤k ← FogServiceDecomposition (G A ) 6 Ã ← A 7 /* Find N max placements of end devices */ 8 for (a ∈ V A and K(a) = 0) do 9 {C i a } 1≤i≤Nmax ← FindProvisioning (C a ) 10 for i = 1 to N max do 11 S i ← S i ∪ {C i a } 12 Ã ← Ã / C a
{C i a } 1≤i≤Nmax ← FindProvisioning (C a ) 18 if ({C i a } ! = ∅) then 19 for i = 1 to N max do 20 S i ← S i ∪ {C i a } 21 Ã ← Ã / C a 22 else 23 S best ← ∅ 24 Stop ← true 25 S best ← SelectBestSolution ({S i } 1≤i≤Nmax )
Ã. It is straightforward to see that à may hold several nodes lacking their incoming links. We refer to these links as orphan links. C i encompasses i) a central node v i , and ii) its orphan incoming/outgoing links. {C i } 1≤i≤k is iteratively built on the basis of the number of their orphan links. Indeed, the nodes with the highest number of orphans links are selected first. The process is repeated until à becomes empty (i.e., à = ∅).

B. Solution component's provisioning stage

During the first iteration, O-FSP finds the N max best placements of end device solution components {C i } 1≤i≤k1 | k 1 ≤ k . Then, O-FSP incrementally constructs the Fog service provisioning solution. Hence, during each iteration, the N max best (partial) placements, {S i } 1≤i≤Nmax , maximizing the objective function defined by equation (IV.11) are generated (FindProvisioning in algorithm 1). To do so, N max physical nodes are selected for hosting the considered C i . The latter has sufficient resources (i.e. CPU, memory), and it is connected to one {C j } 1≤j≤i-1 's placement solution through a shortest path ensuring the required bandwidth and latency. We recall that N max solutions {C i j } 1≤i≤Nmax have already been generated for the placement of C j during the previous iterations. In doing so, we generate the best possible solution while avoiding the exploration of all possible combinations that would make the resolution impractical. Finally, the best solution S best , which corresponds to the placement that maximizes the objective function, is selected (SelectBestSolution in algorithm 1).

VI. PERFORMANCE EVALUATION

In this section, we will assess the feasibility of the FITOR framework and evaluate the performance of the proposed optimized Fog Service Provisioning strategy O-FSP. To achieve this, we first describe the technical details of the FITOR prototype. We then define the performance metrics to evaluate our proposal, and finally, we analyze the results and discuss the effectiveness of O-FSP compared with three main heuristics: i) Uniform which uniformly distributes service components a ∈ V A in available node v ∈ V P in the infrastructure, while respecting the requirements of the application, ii) Best-fit which favors the physical nodes and physical links with the smallest residual resources, and iii) Min-latency which minimizes the sum of delays between nodes hosting the applications components.

As depicted in Fig. 1, a prototype of FITOR is implemented based on a customized version of Calvin [START_REF] Persson | Calvin merging cloud and iot[END_REF]. Calvin is a project led by Ericsson which proposes a framework for the development of IoT applications. First, we have extended Calvin's application descriptor to support dynamic metrics, such as available CPU and RAM, network latency and bandwidth. In doing so, we are able to consider the stringent requirements of IoT applications. Then, a custom implementation of "Service Deployer" was developed to optimize the placement of Fog service components while considering the specified requirements. To ensure a holistic monitoring, we make use of Prometheus5 to collect metrics about our Fog platform behavior during tests. Prometheus relies on monitoring tools, such as netdata, cadvisor and blackbox exporter to generate the metrics.

To experiment our orchestration solution, we make use of both FIT/IoT-LAB [START_REF] Adjih | Fit iot-lab: A large scale open experimental iot testbed[END_REF] and Grid5000 [START_REF] Balouek | Adding virtualization capabilities to the Grid'5000 testbed[END_REF] infrastructures. FIT/IoT-LAB is a large scale open platform to perform IoT experiments. It provides more than 2000 heterogeneous sensor nodes spread in 6 different sites in France. In contrast, Grid5000 focus is on parallel and distributed computing, such as Cloud and Big Data. Grid5000 contains a large amount of powerful resources, grouped in homogeneous clusters. Similar to the FIT/IoT-LAB platform, nodes are also spread in different locations in France. Both platforms are highly configurable and accessible remotely, leveraging experiments in different areas.

Our main objective is to set up a realistic Fog environment, enabling the deployment of IoT applications and hence, their orchestration. To do so, we use M3 and A8 boards to set up the end device layer and the Mist sublayer, encompassing the sensors and Mist nodes. Each M3 board is composed of an ARM micro-controller, 64KB of RAM, various sensors (e.g., ambient sensor light, atmospheric pressure and temperature, etc.) and an IEEE 802.15.4 radio interface. On the other hand, A8 nodes are more potent. Thanks to its ARM A8 microprocessor and 256MB of RAM, it is capable of running user's applications and hence, can be considered as a Mist node. We then make use of some Grid5000 servers to emulate more powerful Fog nodes. To connect both infrastructures, we create L3 VPNs between the A8 nodes and Grid5000. Also, we use public IPv6 addresses to connect the M3 sensors in the network, as detailed in the tutorials available at FIT-IoT platform. Each node of our Fog infrastructure hosts:

• Docker engine to cope with hardware and software heterogeneity. Docker containers are used to create an image which encapsulates the software necessary in our setup, namely Calvin, Blackbox exporter and Netdata. • Cadvisor to ensure the monitoring of Docker containers performance. Some of the collected metrics are CPU and RAM utilization. • Blackbox exporter to measure the latency between the node and all other nodes of the infrastructure if needed. • Netdata and FireQoS to monitor the bandwidth utilization without the support of network equipment. In our setup, we use these tools to measure the bandwidth utilization of each Calvins flow. Note that the flow is characterized by a TCP connection between two nodes. Using FireQoS, we configure the Traffic Control module in the Linux kernel to identify each flow and to keep statistics about them. Then, Netdata collects the information and sends it to our infrastructure monitor.

A. Environment setup

Our Fog infrastructure P relies on elements from Grid5000 and FIT/IoT-LAB platforms. The Fog layer is composed of 20 servers from Grid5000 which are part of the genepi cluster. They are characterized by 2 CPUs Intel Xeon E5420, with 4 cores per CPU and 8 GB of RAM. Their CPU cost C W and memory cost C M are arbitrarily set to 0.1. It is worth noting that the runtimes are hosted by containers.

The Mist layer is composed of 50 A8 nodes. These nodes run FITOR's processes and may execute application components. Besides, C W and C M are set to 0.9. The cost of links C B is fixed to 0.1.

On the other hand, IoT applications are characterized by three types of components: i) trigger service which periodically sends tokens of a fixed size, T size , equals to 1024 byte at a given rate, T rate , taking values in [START_REF] Bonomi | Fog computing and its role in the internet of things[END_REF][START_REF] Minxian | A survey on load balancing algorithms for virtual machines placement in cloud computing[END_REF] tokens per second. These tokens transport the collected measurements related to the end devices' surrounding environment, ii) processing service which emulates the performed application treatment. It consumes a certain amount of million instructions (MI) per token, and iii) storage service which stores the received tokens in memory for further processing (if necessary).

The arrival rate of applications is fixed to 1 application every 2 minutes. For each application, we set the number of components according to a discrete uniform distribution. In this respect, we fix the number of trigger services to 1, while we vary the number of processing services and storage services in [START_REF] Bonomi | Fog computing and its role in the internet of things[END_REF][START_REF] De Brito | A service orchestration architecture for fogenabled infrastructures[END_REF] and [START_REF] Bonomi | Fog computing and its role in the internet of things[END_REF][START_REF] Iorga | Fog computing conceptual model[END_REF], respectively. The trigger service requires a memory M (a) equals to 100 bytes and an amount of CPU W (a) proportional to its T rate , in the range [300, 1000] MIPS. For the processing service, we consider that the processing of one token varies in [100, 1500] MI. Consequently, the CPU request is proportional to the processing effort per token, W token , i.e., W (a) = T rate ×W token . On the other hand, M (a) is fixed to 100Kb. Finally, we assume that the storage service requests a W (a) equals to 500 MIPS and a M (a) proportional to the token size and rate, such as M (a) = T rate × T size .

Evaluation results are always presented with confidence intervals corresponding to a confidence level of 95%. Tiny confidence intervals are not shown in the following figures.

B. Performance metrics

To evaluate the performance of O-FSP compared with the classical approaches, we consider the following metrics:

• A: is the acceptance rate of IoT applications.

• T: is the total number of processed tokens per second within the infrastructure. • W: is the average CPU utilization (expressed in percentage) of physical nodes in Grid5000 and FIT/IoT-LAB. • C tot : is the total provisioning cost related to the consumed resources, as measured by the monitoring tools.

C. Evaluation results

First, we evaluate the proposed strategy O-FSP regarding its acceptance rate and in comparison with the alternative approaches, Best-fit, Uniform and Min-latency. Table I compares the percentage of accepted IoT applications. We notice that O-FSP achieves 77.8% and hence, outperforms the classical strategies. This is due to the fact that the proposed approach aims to minimize the provisioning cost. In doing so, higher residual resources, specifically network bandwidth, are maintained. It is worth noting that Best-fit achieves good results since it favours the selection of less powerful nodes which will lead to a higher number of available powerful nodes. Fig. 2 (a) depicts the rate of processed tokens when increasing the number of provisioned applications. It is straightforward to see that our scheme O-FSP outperforms the classical strategies thanks to its capability to accept IoT applications while meeting their requirements. It is worth noting that the gap between the different approaches is insignificant for low number of provisioned applications. This is due to the fact that initially, all provisioning strategies are capable of placing the applications. However, the gap gets wider as soon as the number of applications increases. Such a result proves that O-FSP efficiently places the application components which corroborates the results related to the acceptance rate.

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • 0
• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • 10000
O-FSP Best-fit Uniform • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • 25
• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •
Fig. 2 (b) illustrates the provisioning cost of accepted IoT applications. It notably shows that O-FSP achieves a lower cost compared with the classical strategies and does so throughout the experiment. In fact, at the end of the experiment, the provisioning cost of O-FSP is ≈ 13% lower than the one of the second strategy, Min-latency (33, 033 ± 1, 289 vs 37, 998±2, 078). Such results are predictable since the proposed approach favours high fog physical nodes as long as the application requirements are satisfied. It worth noting that end devices and mist nodes have limited capacity. Consequently, they incur a high cost compared with fog nodes which are characterized by higher capacities.

In order to gauge the efficiency of O-FSP in terms of resource consumption, we evaluate the CPU usage of both end device/mist and fog nodes. Fig. 2 (c) and Fig. 2 (d) prove that our proposed strategy favours the fog nodes whenever they meet the application requirements. In fact, it achieves 90% of CPU usage which is 10% higher than the second method Min-latency. In doing so, end devices and mist nodes are kept available and used only when it is necessary. We recall that the latter are less powerful and more expensive than Commercial-Off-The-Shelf (COTS) servers. It is worth noting that all strategies reach, at the end of the experiment, a high level of CPU usage on both end device/mist and fog layers. This is due to the system saturation.

VII. CONCLUSION

In this paper, we tackled the problem of Fog-Enabled IoT application orchestration. To do so, we proposed FITOR, a new orchestration solution for IoT applications in the Fog environment. To deal with the service provisioning issue, we put forward a novel strategy, O-FSP, which optimizes the placement of IoT application components while meeting their non-functional requirements. In order to gauge the effectiveness of our solution, we implemented FITOR and O-FSP which make use of an extended version of Calvin, Grid5000 and FIT/IoT-LAB platforms. Extensive experiments show that the O-FSP strategy makes the provisioning more effective and outperforms classical strategies in terms of: i) acceptance rate, ii) provisioning cost, and iii) resource usage.

Fig. 1 :

 1 Fig. 1: Fog-IoT Orchestrator Architecture

  denotes the set of all admissible paths. Formally, N = {v,x}∈V 2 P N vx . • β en is a binary variable indicating whether a logical link e ∈ E A is hosted in the physical path n ∈ N . • (a s (e), a d (e)) ∈ V 2 A denotes the starting (source) and terminating (destination) component of the logical link e ∈ E A . • ∆ ln is a binary coefficient determining whether the physical link l ∈ E P belongs to the path n ∈ N or not. • B(e) = T rate (a s (e)) × T size (a d (e)) corresponds to the exchanged data rate in link e, from a s (e) to a d (e).

Fig. 2 :

 2 Fig. 2: Performance results

TABLE I :

 I A -Acceptance rate

	Provisioning Approach	Acceptance Rate (%)
	O-FSP	77.8 ± 5.5
	Min-latency	65.6 ± 1.9
	Best-fit	69.4 ± 3.4
	Uniform	65.2 ± 2.9

Kubernetes. Available at: https://kubernetes.io/.

Docker Swarm. Available at: https://docs.docker.com/engine/swarm/.

It is worth noting that kind K(v) specifies the hardware properties of the physical resource.

Prometheus. Available at: https://prometheus.io/.

https://www.statista.com/statistics/471264/ iot-number-of-connected-devices-


Ahmad Mazyad

Fabien Teytaud

Cyril Fonlupt

Information Gain Based Term Weighting Method for Multi-label Text Classification Task

In text classification, terms are given weights using Term Weighting Scheme (TWS) in order to improve classification performance. Multi-label classification task are generaly simplified into several single-label binary task. Thus, the term distribution are considered only in terms of positive and negative categories. In this paper, we propose a new TWS based on the information gain measure for multi-label classification task. This TWS try to overcome this shortness without affecting the complexity of the problem. In this paper, we examine our proposed TWS with eight well-known TWS on two popular problems using 5 learning algorithms. From our experimental results, our new proposed method outperforms other methods specialy regarding the macro-averaging measure.

Introduction

Text Categorization (TC) goal is to classify a text document into one or more categories. Generally, this approach is to learn an inductive classifier from a set of predefined categories. This approach requires that documents are represented in a suitable format such as the Vector Space Model (VSM) representation [START_REF] Salton | Term-weighting approaches in automatic text retrieval[END_REF]. In a VSM, a document d j is defined by a term vector d j = (w 1,j , w 2,j , ..., w t,j ) in which each term is associated with a weight w k,j .

The weight represents the quantity of information a term contributes to the semantics of a document. The method which assigns a weight to a term is called TWS.

TC belongs to the family of supervised learning. Thus, TWS could be either unsupervised or supervised depending on whether it makes use of class information. The unsupervised methods include the famous tf.idf proposed in [START_REF] Jones | A statistical interpretation of term specificity and its application in retrieval[END_REF] by Jones. tf.idf stands for Term Frequency-Inverse Document Frequency, and it is borrowed from the information retrieval field.

The Supervised Term Weighting (STW) methods incorporate documents membership information when computing each term weight. These methods include the feature selection metrics such as χ 2 , information gain ig, gain ratio gr, odds ratio or in [START_REF] Debole | Supervised term weighting for automated text categorization[END_REF], [START_REF] Deng | A comparative study on feature weight in text categorization[END_REF]. Recently, some authors proposed multiple intuition based methods. Wang et al. in [START_REF] Wang | Inverse category frequency based supervised term weighting scheme for text categorization[END_REF] proposed the inverse category frequency icf proposed. In [START_REF] Lan | Supervised and traditional term weighting methods for automatic text categorization[END_REF], Lan et al. presented relevance frequency rf . A general formula for the different TWSs experimented in this paper could be defined as:

w t,d = tf t,d × CF t .
Where w t,d is the weight of a term t in a document d, tf t,d stands for the term frequency of t in d and CF t is the collection frequency factor of t.

Different works performed on term weighting methods have shown different results and contradictory conclusions [START_REF] Lan | Supervised and traditional term weighting methods for automatic text categorization[END_REF]. For instance, by comparing tf.idf to three STW, Debole et al. in [START_REF] Debole | Supervised term weighting for automated text categorization[END_REF] showed the superiority of tf.gr over tf.ig and tf.χ 2 while finding no consistent superiority over tf.idf . Another study done by Lan et al. in [START_REF] Lan | Supervised and traditional term weighting methods for automatic text categorization[END_REF] confirmed the superiority of tf.idf over tf.chi. A recent and fair comparaison beween state of the art TWS [START_REF] Mazyad | A comparative study on term weighting schemes for text classification[END_REF] have shown similar results as shown in [START_REF] Debole | Supervised term weighting for automated text categorization[END_REF]. However, In [START_REF] Deng | A comparative study on feature weight in text categorization[END_REF], Deng et al. concluded unlike Debole the superiority tf.chi over tf.idf .

For this work, we seek to find an efficient TWS for multi-labeled classification task.

The paper is organized as follows: Section 2 presents the standard TWSs alongside with our proposed approach. In Sect. 3 we present 5 learning algorithms used in order assess the performance of TWSs. In Sect. 4, we compare the TWSs applied to two well-known data sets. Lastly, we consider future works in Sect. 5.

Term Weighting Methods

In this section, first, we present well-known TWS and second, our method.

Preliminary

Traditional classification algorithms are well suited for single label data sets. Thus, it can not learn from multi-labeled data sets. Several approaches exist to handle the multilabel classification task [START_REF] Tsoumakas | Multi-label classification: An overview[END_REF] such as problem transformation methods, and algorithm adaptation methods. Binary relevance transformation strategy is the most widely used strategy that simplifies the multi-labeled data set into several distinct single-label binary data set. That is, given the list of labels L = {l 1 , l 2 , ..., l m }, the original data set is transformed into m different data sets D = {D 1 , D 2 , ..., D m }. For each data set D i , documents having the label l i will be tagged as the positive category c i , and the rest as the negative category c i . Weights are then computed independently for each binary data set. Based on the binary transformation, given a term t k and a category c i , STW could be expressed using statistical information a, b, c and d obtained from the training data: a, b, c, d represents the number of documents that contain/do not contain t k and belong/do not belong to the positive category c i These statistical information are used in all TWS included in our work, except for tf.icf . In this paper, we logarithmically normalized the Term Frequency (tf) formula :

tf t,d = log(f t∈d ) + 1,
with f t∈d the number of occurrences of the term t in the document d.

Collection Frequency Factors

A Collection Frequency (CF) factor is a combination of statistical information. It is intended to measure the discriminative power of a term, i.e. it tells how much a term is related to a certain category. χ 2 corresponds to a test of independence between two variables (a term and a category). χ 2 is a popular feature selection method. χ 2 and other supervised feature selection schemes have been tested in several papers, as a term weighting methods for text categorization. For example, Deng et al. in [START_REF] Deng | A comparative study on feature weight in text categorization[END_REF], replaced the idf component with χ 2 component, claiming that tf.χ 2 is more efficient than tf.idf . In contrast, in a similar test, Debole et al. in [START_REF] Debole | Supervised term weighting for automated text categorization[END_REF], compare tf.idf with three supervised term weightings, namely, χ 2 , information gain and gain ratio. The authors have found no consistent superiority of these new term weighting methods over tf.idf.

Information Gain (ig) [START_REF] Cover | Elements of information theory[END_REF] is a measure of dependence between two random variables. In the context of text classification, it can be expressed as a measure of dependency between one random term and one random class. Mutual information is widely used in feature selection for text classification [START_REF] Debole | Supervised term weighting for automated text categorization[END_REF], [START_REF] Deng | A comparative study on feature weight in text categorization[END_REF].

Debole et al. used Gain Ratio (gr) applied to a feature selection method [START_REF] Debole | Supervised term weighting for automated text categorization[END_REF]. The authors claim that tf.gr is a better term evaluation functions than the tf.ig. In their text categorization test, they confirmed the superiority of tf.gr over tf.ig and tf.χ 2 .

Odds Ratio (or) is a measure that describes the strength of association between two random variables. It was first used as a feature selection methods by Mladeni'c et al. [START_REF] Mladeni'c | Feature selection for classification based on text hierarchy[END_REF] who found that odds ratio outperforms 5 other scoring methods studied in text classification experiments. Another comparative study on feature weight in text categorization is done by Deng et al. in [START_REF] Deng | A comparative study on feature weight in text categorization[END_REF]. The study shows a good performance of tf.or but still outperformed by tf.χ 2 .

Relevance frequency (rf ) is a supervised weight scheme proposed in [START_REF] Lan | Supervised and traditional term weighting methods for automatic text categorization[END_REF]. rf measures the distribution of term t k between positive and negative category and favors those terms that are more concentrated in the positive category than in negative category.

Inverse Category Frequency (icf ) is another supervised term weighting method proposed by Wang et al. in [START_REF] Wang | Inverse category frequency based supervised term weighting scheme for text categorization[END_REF]. icf stands for inverse category frequency and aims to favor terms that appear in fewer categories.

Main known CF factors are presented in tab. 1. We present some state of the art TWS in the next section.

χ 2 N × (a×d-b×c) 2 (a+c)(b+d)(a+b)(c+d) ig ( a N × log a×N (a+b)(a+c) ) + ( c N × log c×N (c+d)(a+c) ) +( b N × log b×N (a+b)(b+d) ) + ( d N × log d×N (c+d)(b+d) ) gr ig/(-a+c N × log a+c N -b+d N log b+d N ) or log(2 + a×d b×c ) rf log 2 + a max(1,c) icf log 2 |C| |C t k |
The TWS presented has proved to be efficient in text classification through a huge number of experimental studies. However, all these methods, except for tf.icf has a common shortness: they consider the distribution only in terms of positive and negative categories.

Our Information Gain Based Method

The basic idea of our proposed ig based method comes in form of a question: how much information gain a term t k have about a category after subtracting the information gain of the same term t k of the other categories. It is to say that the higher the difference between a term information gain of one category and the average of the other categories, the more the term helps in separating positive and negative categories. As explained in sect. 2.1, a multi-label classification task is transformed into multiple binary single-label classification task, therefore, a term has multiple collection frequency weights, one for each binary task. Each weight only considers the distribution of a feature/term in terms of the positive category and the negative category (all documents that do not belong to the positive category). We think that using these weights could be helpful for more effective TWS. Considering this idea, we propose a new TWS based on information gain. Its formula is defined by: To evaluate the differences between the information gain measure and our proposed method, let us consider the weights for the three terms in tab. 2.

w t,c = w t,c -(µ c ∈C w t,c + σ c ∈C w t,c ) .
First, let us clarify some points:

• When µ + σ > ig, the term contributes more to the negative categories than to the positive category.

• When µ + σ < ig, the term contributes more information to the positive category.

• When µ + σ = ig, the term has about the same amount of information about both positive and negative categories.

First, considering the term t 1 in tab. 2, µ + σ (0.5) is higher than ig value (0.3), which means that the negative categories have higher weights than the positive category, however the ig value of t 1 is a positive value, in contrary to our new method. That said, the difference doesn't have a big impact on scores especially when the number of categories in the corpus is big, as µ + σ will have about the same value. Now, if we consider terms t 1 and t 3 , they both have the same ig value (0.3), which means that they both contribute the same amount of information to the positive category, however by looking at the values of µ + σ, t 1 has a value of 0.5 > 0.3 and t 3 has a value of 0.1 < 0.3. In this case, we think that t 3 should have a higher value than t 1 as it has the same information gain in the positive category but smaller information gain in the negative categories. Finally, t 2 has same information gain value both in the positive category and the negative categories ig = µ + σ = 0.2, thus, the ig-based value is equal to 0.

Classifiers

Generally, the performance of a TWS is assessed on known benchmarks by evaluating a classification model on VSM representation of this TWS. In order to build the classification models, we experiment 5 different algorithms, namely : Passive-Aggressive, C4.5, Support Vector Machine, Stochastic Gradient Descent and Nearest Centroid.

Support Vector Machine (SVM)s are a set of supervised machine learning methods introduced by Boser et al.. Developed from statistical learning theory, SVMs have shown good performance in many fields. In text classification, Joachims in [START_REF] Joachims | Text categorization with support vector machines: Learning with many relevant features[END_REF] used SVM in which he demonstrates the better efficiency of SVM over other learning algorithms. Passive-Aggressive (PA) proposed by Crammer et al. in [START_REF] Crammer | Online passiveaggressive algorithms[END_REF] is a learning algorithm focused on online learning and large scale data set. The method treats a flow of documents, and outputs a prediction once a document is received. Later at any time a document true label is discovered, the method redefines its prediction function . Stochastic Gradient Descent (SGD) classifier [START_REF] Zhang | Solving large scale linear prediction problems using stochastic gradient descent algorithms[END_REF] is a linear classifier such as linear SVM, PA that uses SGD for training. This classifier is also used for large scale categorization problem. Nearest Centroid (NC) [START_REF] Tibshirani | Diagnosis of multiple cancer types by shrunken centroids of gene expression[END_REF] is a neighborhood-based classification algorithm, and C4.5 (C4.5) [START_REF] Quinlan | C4.5: Programs for Machine Learning[END_REF] is a state of the art supervised learning algorithm based on decision tree.

Results and Discussion

In this study, we compare eight term weighting methods alongside with our approach on two popular data sets, i.e. Reuters-215781 and Oshumed 1 using 5 classification algorithms in terms of micro-and macro-averaged F 1 measure.

Data Corpora

Two widely-used datasets are used to compare the performance of our proposed method with the performance of eight well-known TWS: Reuters-21578 and Oshumed. Binary relevance transformation strategy is applied on the two multi-label classification task as explained in sect. 2.1. A default list of stop words, numbers and punctuation are removed. Lower case transformation is applied, and the Porter's stemming is performed.

Reuters-21578 Benchmark Corpus

This data set is a well-known benchmark for TC research. We use the "Apte-Mod" split [START_REF] Joachims | Text categorization with support vector machines: Learning with many relevant features[END_REF]. The Apte split includes 10788 documents from the financial service, divided into a training set (7769 documents) and a test set (3019 documents). The data set is highly skewed, the smallest catgeory contains only 2 documents and the biggest contains 3964 documents.

Evaluation

Numerous evaluation metrics exist to evaluate the classification models such as F 1 measure. The F 1 measure can be considered as a weighted average of the precision (the fraction of positive predicictions that is correct) and recall (the fraction of actual positives that have been correctly classified) and can be formally defined as:

F 1 = 2 * recall * precision recall + precision .
Generally, the F 1 measure is computed in two ways, micro-averaged and macro-averaged. In micro-averaged, big categories are emphasized while in macro-averaged, all categories have the same importance.

In the two tables, underlined results represent the highest score over a column, and the bolded results is the best pair of micro-/macro-averaged F 1 scores when all the classifiers and all the TWSs are considered. The pair having the highest mean is chosen as the best.

Results

Table 4 and Table 5 show the micro-/macro-averaged F 1 performances of different TWSs. using linear SVM for the two data sets Reuters and Oshumed, respectively. Considering the Reuters data set, the best micro-averaged F 1 score 88.68% is achieved by using our method using SVM classifier. In terms of macro-averaged F 1 score, using our method gives the best score 57.70%. The best micro-/macroaveraged F 1 pair 87.29%/57.70% is also achieved by our information gain based method. Compared to the second best pair (87.27%/48.59%) achieved by tf.or, the proposed method records a boost of over 9% in terms of macro-averaged F 1 . In terms of learning algorithms, in this experiment, PA, SVM and SGD show comparable performances. NC records the lowest results. Considering the Oshumed data set, The highest micro-averaged F 1 (67.45%) is achieved using our proposed method. The highest macro-averaged F 1 (62.37%) achieved by using tf.or. As a pair of micro-and macro-averaged F 1 , the proposed method has a slightly higher average. In terms of learning algorithms, SGD and SVM perform the best followed closely by PA and finally, NC and C4.5 show the lowest results. Overall, in our study, we find that the proposed method give good results, better than the standard TWSs. tf.or, tf.rf , tf.idf and tf.ig have also shown good results. tf.χ 2 and tf.icf give the worst results.

Conclusion

For this work, we study a new term weighting scheme applied to multi-label text classification based on the information gain measure. The basic idea is that the information gain weight of a feature in negative categories should affect the importance of this term in the postive category.

We studied the effectiness of our method in comparaison to eight well-known TWSs applied to text classification tasks.

Experimental results show that our method outperformed all other methods tested in this study, specially in regard to the macro-averaged measure.

Table 1 :

 1 Seven traditional CF factors. N is the total number of docs, a the number of docs in the positive category cat that contain the term t k , b defines the number of docs in cat with no occurrences of t k , c is the number of docs not in cat in which t k occurs at least once, d the number of docs that don't belong to cat and have no occurrences of t k . |C| reprensents the number of categories and |C t k | is the number of categories that contain t k .

	CF	Formula
	idf	log( N a+c )

Table 2 :

 2 Comparison of the weighting values of ig and the proposed method. µ + σ is the average plus the standard deviation of scores of categories which are not the positive category. The values were hand-chosen.Where w t,c is the new weight of a term t and a category c, w t,c is the information gain score of a term t and a category c, µ c ∈C w t,c is the mean of weights on all other categories, and σ c ∈C w t,c is the standard deviation of weights on all other categories.

	Feature ig µ + σ New
	t 1	0.3	0.5	-0.2
	t 2	0.2	0.2	0
	t 3	0.3	0.1	0.2

Table 3 :

 3 Statistics on the selected data sets used for our experiments (training/test).The second dataset is another well-known benchmark from the Oshumed 1 collection created by W. Hersh. the corpus is includes a total number of 13,929 medical abstracts splitted into a training subset of 6,286 abstracts and a test subset of 7,643 abstracts from the MeSH categories of the year 1991. Each document in this data set belongs to one or more categories from 23 cardiovascular diseases categories.

		Reuters	Oshumed
	number of documents 7769/3019 6286/7643
	number of terms	26000	30198
	number of categories	90	23
	the smallest category	1/1	65/70
	the largest category	2877/1087 1799/2153
	4.1.2 Oshumed Benchmark Corpus

Table 3

 3 presents statistics about the two datasets.

Table 4 :

 4 micro-/macro-averaged F 1 results (%) on Reuters-21578 corpus using eight standard TWSs and the proposed method.

		PA	SVM	SGD	NC	C4.5
	tf	86.6/48.5	85.9/39.7 86.4/41.1 54.6/34.7 81.9/53.6
	tf.χ 2	86.3/48.5	84.8/43.9 86.4/40.8 54.6/34.7 81.8/53.2
	tf.idf	87.2/48.2	85.7/40.3 86.6/42.7 73.5/47.0 81.3/53.4
	tf.gr	86.5/47.1	86.5/42.4 86.4/41.1 54.6/34.7 82.0/51.8
	tf.or	86.6/48.5	87.3/48.6 86.3/40.8 54.6/34.7 81.9/52.8
	tf.ig	86.9/47.7	86.5/42.4 86.3/41.0 54.6/34.7 82.1/54.2
	tf.icf	85.9/46.4	84.0/37.8 85.0/40.3 62.5/46.4 80.9/52.0
	tf.rf	86.5/46.7	87.8/45.3 86.4/40.8 54.6/34.7 82.0/52.8
	New	87.3/57.7 88.7/51.7 88.4/49.0 66.5/54.7 82.2/51.3

Table 5 :

 5 micro-/macro-averaged F 1 results (%) on Oshumed using eight standard TWSs and the proposed method.

		PA	SVM	SGD	NC	C4.5
	tf	60.7/54.0 58.2/47.0	59.4/48.8	49.8/44.5 56.6/52.4
	tf.χ 2	60.3/55.5 62.5/55.3	59.4/52.0	54.7/51.8 57.4/53.9
	tf.idf 62.7/56.4 59.3/49.1	61.8/53.4	60.3/57.4 56.9/52.9
	tf.gr	63.8/58.1 60.8/51.7	63.3/56.0	62.4/60.2 56.8/52.6
	tf.or	65.2/62.4 64.9/58.8	66.0/60.6	59.2/57.4 56.6/52.8
	tf.ig	63.7/58.1 60.8/51.7	63.2/56.0	62.4/60.2 57.1/53.5
	tf.icf 56.5/51.3 49.3/41.9	54.6/48.3	59.1/55.2 56.5/52.7
	tf.rf	64.0/60.1 63.4/55.5	64.4/57.2	58.4/56.0 56.6/53.0
	New	64.4/60.8 67.0/60.8 67.4/61.2 59.4/57.0 56.7/52.5

http://disi.unitn.it/moschitti/corpora.htm