Rahul Singh

Prashant Shenoy
email: shenoy@cs.umass.edu

Maitreya Natu
email: maitreya.natu@tcs.com

Vaishali Sadaphal
email: vaishali.sadaphal@tcs.com

Harrick Vin
email: harrick.vin@tcs.com

Predico: A System for What-if Analysis in Complex Data Center Applications

Modern data center applications are complex distributed systems with tens or hundreds of interacting software components. An important management task in data centers is to predict the impact of a certain workload or reconfiguration change on the performance of the application. Such predictions require the design of "what-if" models of the application that take as input hypothetical changes in the application's workload or environment and estimate its impact on performance. We present Predico, a workload-based what-if analysis system that uses commonly available monitoring information in large scale systems to enable the administrators to ask a variety of workload-based "what-if" queries about the system. Predico uses a network of queues to analytically model the behavior of large distributed applications. It automatically generates node-level queueing models and then uses model composition to build system-wide models. Predico employs a simple what-if query language and an intelligent query execution algorithm that employs on-the-fly model construction and a change propagation algorithm to efficiently answer queries on large scale systems. We have built a prototype of Predico and have used traces from two large production applications from a financial institution as well as real-world synthetic applications to evaluate its what-if modeling framework. Our experimental evaluation validates the accuracy of Predico's node-level resource usage, latency and workload-models and then shows how Predico enables what-if analysis in two different applications.

Introduction

Today online server applications have become popular in domains ranging from banking, finance, e-commerce, and social networking. Such server applications run on data centers and tend to be complex distributed systems with tens or hundreds of interacting software components running on large server clusters. As an example, consider an online stock trade processing application of a major financial firm. This application consists of 471 separate software components that process incoming stock trades at low latencies. Figure 1 shows another application which disseminates stock prices and market news to the terminals of stock traders; this application consists of 8970 components.

The components are depicted as nodes of the graph and process stock data and news from a multitude of sources, filter, aggregate, and then disseminate updates for each company to desktops that subscribe to such streams. Such data center applications differ significantly in scale and complexity when compared to traditional multi-tier web applications.

Typical data center applications evolve over time as new functionality is added, its workload volume grows, or its hardware or software is updated. To deal with such changes, an important management task for administrators is to predict the impact of any planned (or hypothetical) change on the performance of individual components or the entire system. This task, which is referred to as what-if analysis, requires the design of what-if models that take as input a potential change in the application workload or its settings and predict the impact of that change on application behavior. However, given the complexity of today's data center application, manual design of such what-if models is no longer feasible since data center administrators may not be able to comprehend the behavior of a complex system of tens of interacting components. Consequently, a what-if analysis system must be able to automatically derive such models from prior observations of application's behavior. Further, the system must be able to scale to large complex applications with hundreds of interacting components, while allowing rich what-if analysis efficiently. While a number of modeling techniques have been proposed for distributed or multi-tier web applications [START_REF] Stewart | Exploiting nonstationarity for performance prediction[END_REF][START_REF] Thereska | Ironmodel: robust performance models in the wild[END_REF][START_REF] Zhang | A regression-based analytic model for dynamic resource provisioning of multi-tier applications[END_REF][START_REF] Thereska | Informed data distribution selection in a self-predicting storage system[END_REF][START_REF] Jiang | Discovering Likely Invariants of Distributed Transaction Systems for Autonomic System Management[END_REF][START_REF] Tariq | Answering what-if deployment and configuration questions with wise[END_REF], such models are not directly targeted for what-if analysis or are not designed to scale to larger data center applications such as the ones illustrated in Figure 1. In this paper, we present Predico, a what-if analysis system to predict the impact of workload changes on the behavior of data center applications. Predico makes the following contributions:

-Modeling of complex data center applications: Predico employs a queuing-theoretic framework to model large distributed data-center applications. Our modeling framework is based on a network of queues and captures the dependence between the workload of each component of the application and the corresponding resource utilization, request latency and the outgoing workloads to other components. Predico uses monitoring data and request logs to estimate the parameters of such a model and employs model composition to create larger system-level models for groups of interacting application components.

Background and Problem Formulation

Our work assumes a large distributed application with N interacting components. We assume that the application is structured as a directed acyclic graph (DAG), where each vertex represents a software component and edges capture the interactions (i.e., flow of requests) between neighboring nodes. For simplicity, we assume that each component runs on a separate physical (or virtual) machine. 3 We assume that the DAG has one or more source nodes, that serve as entry points for application requests and one or more sinks, that serve as exits. The flow and processing of requests through such applications is captured by the DAG structure and is best explained with examples.

As examples of such distributed applications we consider two production financial applications. The first application is a stock trade processing application at a major financial firm; the application consists of 471 nodes and 2073 edges. New stock trade requests arrive at one of the source nodes and flow through the system and exit from the sink nodes as "results". Each intermediate node performs some intermediate processing on the trade request and triggers additional requests at downstream nodes. Nodes may aggregate incoming stock trades or break down a large stock order into smaller requests at downstream nodes. Figure 1 shows the structure of a market data dissemination application that disseminates stock prices and news updates for a company to trading terminals ("desktops") of stock traders. In this case, news items arrive from a number of sources and stock prices are obtained from a variety of exchanges, and this information is processed, transformed, filtered and/or aggregated and disseminated to any desktop node that has subscribed to information for a particular company. This application has 8970 nodes and 22719 edges and must provide updates at low latency in order for stock traders to make trades based on the latest market news.

Thus, we assume that requests flow through the DAG, with intermediate processing at each node; a request may trigger multiple requests at one or more downstream child nodes, and each node may aggregate requests from upstream parents. As can be seen, such applications are significantly larger and more complex than traditional multi-tier web applications.

We assume that the DAG structure for each application is known a priori (there are automated techniques to derive the DAG structure by observing incoming and outgoing traffic at each node [START_REF] Kind | A light-weight and scalable network profiling system[END_REF]). We assume that each node in the DAG is a black box-i.e., we can observe the incoming and outgoing request streams along its edges and the total node-level utilization but that we have no knowledge of the internals of the software component and how it processes each request. This is a reasonable assumption in practice since IT administrators typically do not have direct knowledge of the application logic inside a software component, requiring us to treat it as a black box. However, administrators have access to request logs that the application components may generate and can also track OS-level resource utilizations on each node.

We assume that there are R different types of requests in the entire distributed application. Each node can receive different types of requests belonging to the R types and can in turn trigger one or more requests of one of the R types at downstream child nodes. Given our black box assumption, the precise dependence of what type of outputs are generated by what set of inputs is unknown (and must be learned automatically by correlating request logs at a parent and a child). Similarly, the precise processing demands imposed by a set of requests are unknown and must also be learned.

Assuming such a data center application, our first problem is to model each application component (i.e., node of the DAG) by capturing the dependence between the incoming workload mix and the request latency, resource utilization, and the outgoing workload. Second, we need to use these node-level models to create system-level models that capture the behavior of a group of interacting nodes. Third, given such system-level models, we wish to enable rich workload-based what-if analysis of the distributed application. Such an analysis should allow administrators to pose what-if queries to determine the impact of a workload change at a particular node(s) on some other node(s) of the system. A typical what-if query is assumed to contain two parts: (i) the "if" part, which specifies the hypothetical workload change, and (ii) the "what" part, which specifies the nodes where the impact of this change should be computed. For instance, a volume-based what-if query could ask "what is the impact of doubling the volume of requests seen by source node i on the incoming workload and CPU utilization seen at some downstream node j?" Queries could also be concerned with the impact on latency: "what is the impact of doubling the volume of type B requests at node j on the latency of requests at node i?" Thus, to design our what-if analysis system, we must address the following three problems: (i) how should we model the dependence between the incoming workload at a node and the request latency, node utilization and the outgoing workload to down- stream nodes? (ii) how should we combine node-level models to create system-level models that capture the aggregate behavior of a group of interacting nodes in the DAG?

(iii) what algorithms should be used to efficiently execute a what-if query using these models? From an implementation standpoint, we are interested in a fourth question as well: (iv) How should our system scale to complex data center applications with tens or hundreds of components?

3 Modeling a Data Center Application

In this section, we first present a queuing model for a data center application that allows us to model the utilization and response time of these nodes. We then describe the construction of models to capture the input/output workload dependencies of these nodes. Finally, we explain how these node-level models are composed to construct systemwide models.

Queuing theoretic node-level models

Consider the DAG of a data center application with k nodes denoted by n 1 , . . . , n k and R different type of requests. We model the data center application using an open network of k queues, one for each node with R classes of requests. We model each node as a M/G/1/P S queue i.e. the service times are assumed to have an arbitrary distribution and the service discipline at each node is assumed to be processor sharing (PS). Requests can arrive at a queue from other queues which are its parents in the DAG or in the case of source nodes of the DAG from external sources. For analytical tractability we assume that the distribution of inter-arrival times of requests coming from outside have a poisson distribution. We denote the arrival rates of requests of class r at the queue n i from outside by λ r 0,i . We assume that different classes of requests arriving at a queue have different mean service rates. We denote the mean service rate of requests of class r at node i by µ r i . Thus the DAG of a data center application is modeled as an open network of queues as shown in Figure 2. We use the well known queueing theory result called the BCMP theorem [START_REF] Forest Baskett | Open, closed, and mixed networks of queues with different classes of customers[END_REF] to analyze this network of queues. The BCMP theorem states that for such queueing networks the utilization, denoted by ρ i , of a node n i , is given by : where ρ r i denotes the resource utilization at node n i due to class r requests, λ r i denotes the arrival rate of requests of type r at node n i and µ r i denotes the service rate of requests of type r at node n i . This equation models the resource utilization of the node as a function of the per-class arrival rate and per-class service rates. Similarly, the average number of requests of type r at node n i under steady-state, denoted by K r i , is given by:

ρ i = R r=1 ρ r i = R r=1 λ r i µ r i (1)
K r i = ρ r i 1 -ρ i (2)
We can now use Little's Law [START_REF] Peter | The operational analysis of queueing network models[END_REF] to find out the T r i , the average response time of requests of type r at node n i using Equations 1 and 2:

T r i = K r i λ r i = 1 µ r i (1 -ρ i ) (3)
This equation models the response time at a node as a function of the total node resource utilization ρ i and the per-class service rate µ r i . Given a value for the per-class workload, λ r i , at a node we can use Equation 1 to find out the utilization ρ i and then use the computed value ρ i to find out the response time using Equation 3. The per-class service times µ i r is the only unknown in the equations. Since we assume that each node of the data center application is a black-box we need to estimate these unknowns from the available information gathered from monitoring of the node. We assume that request logs at a node contain an entry for each incoming request containing the timestamp and the request string or type of request and that the resource utilization of the node is being periodically monitored using a tool like iostat. Given such logs, multiple values of ρ i and λ r i can be collected over time. Since Equation 1 captures the relationship between these R + 1 variables, the values of the unknown per-class service rates µ r i can be numerically estimated using a regression method such as least squares.

Workload models

While queueing theory allows us to model the performance metrics of a node, we also need to capture the relationship between the incoming workload and the outgoing workload of a node.

To understand the node-level workload models that Predico needs to build, consider the node shown in Figure 3. This node n 1 has two parent nodes n 2 and n 3 and three child nodes n 4 , n 5 and n 6 . Let λ r 2,1 and λ r 3,1 denote the arrival rate of requests of type r from node n 2 and n 3 respectively to node n 1 . Similarly, let λ r 1,4 , λ r 1,5 and λ r 1,6 denote the arrival rate of requests of type r at node n 4 , n 5 and n 6 respectively from node n 1 . Predico needs to build models that capture the workload of each outgoing edge as functions of workload of the incoming edges. Thus, we seek a function for each of λ r 1,4 , λ r 1,5 and λ r 1,6 that expresses them as a function of

--→ λ 2,1 and --→ λ 3,1
where -→ λ i,j is short-hand for observed rates of various request types on the edge going from node n i to n j i.e. (λ

1 i,j , λ 2 i,j , • • • λ R i,j
) . Similarly, we seek functions for each of the other request types :

λ w 1,4 = f w 1,4 ( --→ λ 2,1 , --→ λ 3,1 ) , 1 ≤ w ≤ R (4)
We model workload-to-workload dependencies as piecewise linear functions. Although these dependencies are linear in steady state by the principle of job flow balance [START_REF] Peter | The operational analysis of queueing network models[END_REF], [START_REF] Menascé | Capacity planning for Web performance: metrics, models, and methods[END_REF], we choose piecewise linear modeling to capture the behavior of caches in servers. For instance, a node with a cache can initially be sending a large number of requests to downstream nodes when the cache is empty, but when the cache becomes full, it might serve requests from its cache instead of sending requests to its downstream nodes. This changing dependence of outgoing workload on incoming workload can be captured by two linear functions, one each for when a cache is cold and and when it is hot. To incorporate piecewise linear modeling, we replace the linear model shown in Equation 4with a piecewise-linear model by dividing the 2R-dimensional space spanned by ( --→ λ 2,1 , --→ λ 3,1 ) into n hypercube regions. A linear model is then used to capture the relationship in each of these regions independently. Thus, we can rewrite Equation 4 as a set of linear functions one for each region :

λ w 1,4 =            r=R r=1 A w,r 1 λ r 2,1 + B w,r 1 λ r 3,1 if ( --→ λ 2,1 , --→ λ 3,1 ) ∈ Z 1 r=R r=1 A w,r 2 λ r 2,1 + B w,r 2 λ r 3,1 if ( --→ λ 2,1 , --→ λ 3,1 ) ∈ Z 2 . . . . . . . . . . . . . . . r=R r=1 A w,r n λ r 2,1 + B w,r n λ r 3,1 if ( --→ λ 2,1 , --→ λ 3,1 ) ∈ Z n (5)
where Z i is the i th hypercube region. Equation 5 relates the outgoing workload to incoming workload, but to use it for computing the outgoing workload λ w 1,4 for a given value of incoming workload --→ λ 2,1 and --→ λ 3,1 we need to first find the number of regions, n, and the regions themselves, Z i . We then need to find individual linear functions for each region by computing the weights of the corresponding linear function, A w,r 1 and B w,r 1 . We use a regression analysis technique called multivariate adaptive regression splines (MARS) [START_REF] Friedman | Multivariate adaptive regression splines[END_REF] that automatically fits piecewise linear functions on data. Predico uses the monitoring data that contains multiple measurements of the variables --→ λ 2,1 , --→ λ 3,1 and λ w 1,4 to give as training data to MARS which finds out the different regions and the linear function in each region.

Model Composition: From Node-level to System-level Models

Predico uses node-level models to construct system-wide models using model composition. Model composition essentially "chains" together multiple node-level models to compute the workload, resource utilization and response time of a node as a function of one or more ancestor nodes. We illustrate the composition algorithm used by Predico using an example. Consider the sub-graph in Figure 4 that shows a parent node n 2 , extending our earlier example in Figure 3. At the node-level, Predico can compute the outgoing workload going from node n 2 to node n 1 , --→ λ 2,1 , as a set of R piecewise linear functions, one for each request type :

λ w 2,1 = f w 2,1 ( --→ λ 8,2 , --→ λ 7,2 ) , 1 ≤ w ≤ R (6)
Equation 4 gives the outgoing workload going from node n 1 to n 4 :

λ w 1,4 = f w 1,4 ( --→ λ 2,1 , --→ λ 3,1 ) , 1 ≤ w ≤ R (7)
Substituting the value of --→ λ 2,1 from Equation 6into Equation 7we obtain a "composed model" :

λ w 1,4 = f w 1,4 ( --→ f 2,1 ( --→ λ 8,2 , --→ λ 7,2 ), --→ λ 3,1 ) , 1 ≤ w ≤ R (8)
where

--→ f 2,1 ( --→ λ 8,2 , --→ λ 7,2 ) is shorthand for (f 1 2,1 ( --→ λ 8,2 , --→ λ 7,2 ), f 2 2,1 ( --→ λ 8,2 , --→ λ 7,2 ) , . . . , f R 2,1 ( --→ λ 8,2 , --→ λ 7,2 )
). Doing so enables the outgoing workload sent from node n 1 to n 4 to be expressed as a function of incoming workload of parent node n 2 . This process can be repeated for the outgoing workload going to nodes n 5 and n 6 from node n 1 and can also be recursively extended to nodes that are further upstream from n 2 .

Creation of the composed model shown in Equation 8requires composing the piecewise linear function f w 1,4 with each of the R piecewise linear functions f w 2,1 , 1 ≤ w ≤ R. Two piecewise linear functions can be easily composed by composing the individual linear functions in each corresponding region which leads to another piecewise linear function. Thus the composed model shown in Equation 8 is again a piecewise linear function which captures the relation between the outgoing workload of node n 1 and the incoming workload of a parent node n 2 .

We can now do a similar composition to find the dependence of the resource utilization of node n 1 , denoted by ρ 1 , and the response time of requests of type r at node n 1 , denoted by T r 1 on the incoming workload of parent node n 2 denoted by

--→ λ 8,2 ,
--→ λ 7,2 . Substituting Equation 6 into the resource utilization equation given by Equation 1 we get :

ρ 1 = R r=1 ρ r 1 = R r=1 λ r 1 µ r 1 = R r=1 λ r 3,1 + λ r 2,1 µ r 1 (9) = R r=1 λ r 3,1 + f r 2,1 ( --→ λ 8,2 , --→ λ 7,2 ) µ r 1 (10)
which expresses the resource utilization of node n 1 as a function of the incoming workload of node n 2 . Similarly, we can substitute from Equation 10 into the response time Equation 3 to express the response time of request type r at node n 1 as a function of the incoming workload of parent node n 2 :

T r 1 = 1 µ r 1 (1 -ρ 1 ) (11)
4 Answering What-if Queries

In this section we describe the three step process used by Predico to answer a given what-if query. The execution of a what-if query is a three step process comprising of: 1) finding the influence graph of the given query, 2) creating the node-level models of the nodes in the influence graph using the modeling technique described above and 3) using the change propagation algorithm to execute the query. We describe the three steps in greater detail below.

On-the-Fly Model Construction using the Influence Graph

Since the number of nodes and edges in the DAG may be large in complex applications, it is not economical to precompute all possible node-level models and periodically recompute models that have become invalid due to an actual workload or hardware change. Instead Predico employs a "just-in-time" policy to compute models on-the-fly when a query arrives; only those models that are necessary to answer the query are computed. Models from prior queries are cached and reused if they are still valid. Predico uses the notion of an influence graph to determine which models should be constructed to answer a query. Given a what-if query, the influence graph is the set of all possible paths from the nodes in the "if" part of the query to the nodes in the "what" part. Basically the influence of a workload change will propagate along all paths from the "if" nodes/edges to the "what" nodes; so the influence graph captures all of the nodes that must be considered to answer the query and other nodes in the DAG can be ignored.

Upon the arrival of a what-if query, Predico first computes the influence graph by generating the set of nodes that lie along all paths from the "if" nodes/edges to the "what" nodes. It then triggers on-demand construction of node-level workload models for all the nodes in the influence graph and node-level resource utilization and response time models for the "what" nodes alone. The use of the influence graph to prune the DAG and the reuse of previously computed models from the model cache enhances the scalability of the system and reduces computational overheads. The influence graph is also crucial for efficient query execution, as we will see in the next section.

Query Execution Using Change Propagation

After creating the node-level models for the nodes of the influence graph, Predico now needs to "execute" the query. Query execution involves propagating the specified workload change through the influence graph, one node at a time, to compute its final impact on the nodes/edges specified in the "what" part of the query. Once the workload change has been propagated to the nodes in the "what" part, the node-level models can be used to answer the query. Change propagation is equivalent to model composition-instead of directly computing a composed model for the "what" nodes/edges as a function of the Algorithm 1: Change Propagation via the Influence Graph "if" nodes/edges, the propagation algorithm propagates the specified change through the influence graph all the way down to the nodes/edges in the "what" part to achieve the same result. Predico's change propagation algorithm is described in Algorithm 1. It takes the node-level models and the influence graph, and traverses the influence graph in a breadth first manner. It starts with the nodes/edges in the "if" part and computes the values for the changed workload and then uses the model to compute its impact on the outgoing workload. This process is referred to as propagating the change from the incoming edges of a node to its outgoing edges. To illustrate, consider a query that is interested in estimating the impact of a doubling of the workload for a particular edge. If the original request rate was 10 req/s, then the new workload will be 20 req/s for that edge. This new value is used, along with the unchanged request rates for all other edges not impacted by the change, to compute the outgoing request rates for that node.

The algorithm proceeds in a breadth first fashion through the influence graph, starting with the "if" nodes/edges and computing the outgoing workload for each of the "if" nodes. The outgoing workload of a node becomes the incoming workload for downstream node(s), and the change propagation process repeats, one node at a time, in a breadth-first fashion, until the change has propagated to all of the "what" nodes/edges. At this point, the algorithm computes the value of interest at the node by using the node-level models and terminates.

Predico Implementation

This section describes WIFQL, a query language that can be used to pose what-if queries to Predico and the implementation details of Predico prototype.

Posing What-if Queries in Predico

Since the goal of Predico is to enable users to understand the impact of potential workload changes on the system behavior, our system supports a simple query language to enable a rich set of queries to be posed by IT administrators. Any query in our What-If Query Language (WIFQL) has two parts: a what part and an if part. The if part of the query describes the hypothetical change, while the what part asks the system to compute the impact of that change on different performance metrics at one or more nodes in the system. As an example of an WIFQL query, consider compute workload on edges (n1, n4), (n1, n5), (n1, n6) cpu utilization at nodes n1, n2 latency at nodes n1, n2 if workload on (n2, n1) *= 2 workload on (n3, n1) *= 0.5

This example query asks the system to compute the impact of a doubling of the workload along the edge going from node n 2 to n 1 and a halving of the workload along the edge going from node n 3 to n 1 on the CPU utilization and latency at nodes n 1 and n 2 and the workload on the edges going from node n 1 to nodes n 4 , n 5 and n 6 .

Figure 5 describes our query language grammar. As shown, the if part allows users to specify hypothetical changes to the workload or changes to the hardware (e.g., a faster CPU). The workload changes, which is the focus of this work, can be specified by identifying one or more edges or nodes in the DAG and indicating a change in volume or a change in the mix of requests; set operators such as multiply and divide can be used to specify relative changes to the current workload, rather than absolute values. The what part specifies the performance metrics of interest at particular nodes or edges; several metrics are supported including resource utilizations, workloads, latencies or spare capacities. As indicated earlier, we assume that the DAG representing the application is known a priori and is used by queries to refer to particular nodes and edges of interest and specify workload changes on these nodes or edges.

Prototype Implementation

We have implemented a prototype of Predico using Python and the R statistical language to perform what-if analysis in large data center applications. Figure 6 depicts the high-level architecture of Predico.

The Predico frontend is implemented using a python implementation of the lex and yacc parsing tools. It accepts user-posed queries and parses them by using the grammar rules of WIFQL. User-posed queries are then executed by the Predico execution engine, which comprises of two key components; the on-the-fly modeling engine and the what-if analysis engine. The on-the-fly modeling engine first computes the influence graph using a graph API in python and then creates node-level models by using on-the-fly model construction. The modeling engine retrieves data about the workload on the incoming and outgoing edges of the node and the total resource utilization of the node and then invokes an R module for building the node-level models. The R module uses the MARS function present in the MDA package to build piecewise linear nodelevel workload models and the linear regression function to find the per-class service rates using least squares regression. Next, the what-if analysis engine uses these models to answer ("execute") the query via the change propagation algorithm to propagate the hypothetical workload change through the model and compute its impact on the nodes of interest to the user. The change propagation algorithm is again implemented by using the graph API written in python. The what-if analysis engine stores the node-level models computed by the modeling engine in a model cache that is implemented as three tables in the MySQL relational database engine; one each for storing the weight vectors used in node-level workload models, the regions of the piecewise-linear model and the per-class service rates of a node required in the node-level resource utilization and response-time models.

Experimental Evaluation

In this section, we evaluate the performance of Predico by performing experiments on two applications. We first evaluate the accuracy of the analytical node-level resource utilization and response-time models and then the piecewise-linear workload models. We then perform experiments to ascertain the accuracy of system-level models formed by composition. We then employ Predico to perform case studies where we pose whatif queries to Predico and compare the predictions with ground truth values observed in actual experimental data.

Experimental Setup

We evaluate Predico on two different applications. The first set of applications are from the financial domain and are being used by the data center of a financial institution. The second application is a benchmark e-commerce application.

1. We evaluate our system on traces collected from the two production financial applications described in Section 2. The traces collected from the stock trade processing application contain the total number of requests sent out by every component within every 30 second interval. The traces collected from the market data dissemination application contain data for the number of bytes sent out from every component on each of its outgoing edge, within every 30 second interval. 2. The second application is the TPC-W benchmark [START_REF]TPC. the tpcw benchmark[END_REF] which models an online bookstore application. We implement the TPC-W application as a 2-node Java servlet based application consisting of the front-end server (Tomcat) and a backend database (MySQL). Notice that this application does not follow our DAG assumption since replies are sent back from the back-end database to the front-end server. Predico is also able to handle such applications that contain cycles between neighboring nodes by considering the two edges of the cycle separately. To implement this application we use a testbed comprising of two virtual machines for performing this experiment. Each virtual machine has a single 2.8 GHz Pentium 4 processor with 1GB memory. We use Tomcat version 5.5.26 and MySQL version 5.1.26 for setting up our TPC-W application. The TPC-W experimental setup allows us to monitor the end-to-end latency and resource utilization values apart from workload values.

Accuracy of Node-level Resource Usage and Latency Models

We model the data center application as an open network of queues that lead to Equation 1 which captures the node-level resource utilization and Equation 3 which captures the node-level latency. We validate the accuracy of this queueing model using the TPCW application running on a two server testbed. We use the httperf load generation tool to simulate requests arriving from customers with exponentially distributed inter-arrival times. The TPC-W web application exposes 14 different servlets which a customer visiting the website can invoke. We create a workload comprising of requests to two of these servlets, the "new products " and "execute search". We independently vary the arrival rate of requests to both these servlets from 10 to 100 requests per second with increase of 10 requests per second, thus generating a total of 100 arrival rate combinations. For each arrival rate combination, we let the system run for 15 minutes and measure the CPU utilizations at the Tomcat and MySQL server and the end-to-end latency. We use half of the 100 values for estimating the components of the two applications using CDF curves that show the percentage of components that have errors below a certain value. Figure 9 shows the errors for the market data dissemination application while Figure 10 shows the errors for the stock trade processing application. The curve labeled "Level-1" errors shows the CDF for the errors. We describe the concept of levels and the description about the "Level-2" and "Level-3" curves later in this section. The CDF curves indicate that the workload-toworkload models of 70% of the components have errors less than 10% in the case of the market data dissemination application while models for 80% of the components have errors less than 15% in the case of the stock trade processing application.

Our experimental results show that piecewise linear modeling provides accurate models of node-level workload for production data center applications.

Accuracy of System-level models with increasing composition depth

We evaluate the accuracy of system-level models created by composing multiple nodelevel models. Composition of multiple node-level models leads to an accumulation of the error terms. We conduct experiments to measure the increase in error with composing increasing number of node-level models. We again use the traces from the two financial applications to evaluate the accuracy of system-level models. We reuse the node-level models of each component built for validating the accuracy of node-level workload models in the previous section for this experiment.

We select each component and compose its node-level workload model with that of its ancestor components to express the outgoing workload of this component as a function of the incoming workload of its ancestors. By using composition repeatedly we successively construct models expressing workload of a component as a function of its ancestors at different levels. Level 1 model is built between the outgoing workload of a component and its incoming workload. Level 2 model is built between the outgoing workload of a component and the incoming workload of its immediate parents. Similarly level i model is built between the component and its ancestors that are reachable in (i -1) edges. We compute the average normalized RMS error of each component by computing the average normalized RMS error for the models of all the outgoing edges e4 e3 e1 e2 e5 show the CDF of normalized RMS errors for each level for the two applications. The CDF curve drops with increasing levels implying that the errors increase as we predict the workload of a component using ancestors higher up the component in the graph. Inspite of the increasing errors with increasing levels, the errors remain tolerable; for the Market Data Dissemination application even at level 4 the prediction errors for 80% of the components are less than 20%, while for the Stock Trade Processing at the level of 3 for 75% of the components the errors are less than 20%.

Our results on using composition to create system-level models on the traces collected from the two production applications reveal that even with increasing composition depth, the system-level models are effective in predicting workload.

Accuracy of System-level models with varying topology

The node-level models can be composed in a number of ways to create a system-level model depending on the topology of the DAG. We perform experiments to ascertain the prediction accuracy of composed models under different topologies. For this experiment we select some subgraphs in the DAGs for the two applications. We select subgraphs that correspond to three topologies-chain, split and join. These topologies correspond to different ways in which the components can interact with one another in an application: (i) in the chain topology, each component receives requests from a single upstream component, (ii) in the split topology, a component can send requests to multiple downstream components and (iii) in the join topology, a component can receive requests from multiple upstream components. For each subgraph, we create node-level models for each component and then use composition to create models to predict the workload on each outgoing edge of the subgraph. We measure prediction er- 11(c) and 11(d) show how the errors of the composed models vary as we predict the workload on various edges/nodes of the graphs. For the subgraphs selected from the market data dissemination application the prediction errors on all edges are within 5% while for the subgraph selected from the stock trade processing application the prediction errors are within 13%.

The errors reveal that Predico's composition based modeling technique performs well even in case of complex application topologies.

Workload-only What-if Analysis Case Study

We create use-case scenarios to illustrate how Predico can be used in practice and evaluate its performance in answering what-if questions which commonly arise in large-scale applications. In this section, we pose workload-related what-if questions; we choose subgraphs from the market data dissemination application and the stock trade processing application and use Predico to predict the impact of workload changes on source nodes at the workload on the other edges of the subgraphs.

We choose one subgraph each from the market data dissemination application and the stock trade processing application. The first subgraph has 1 source node while the other subgraph has 3 source nodes.

The topology of the first subgraph is shown in Figure 12(a). On this subgraph we pose the query: "what happens to the workload on downstream edges of subgraph 1 if the outgoing workload of the single source node increases by 2 and 2.5 times the current value". We examine the application traces and find periods of 1 hour duration each, h 1 , h 2 and h 3 , such that the outgoing workload from the source node increases by 2 and 2.5 times the workload in h 1 in the hours h 2 and h 3 respectively. Predico uses the trace The topology of the second subgraph is shown in Figure 13(a). On this subgraph we pose the query: "what happens to the workload on downstream nodes a) if the workload on the source nodes 143, 19 and 92 becomes 1.12, 1.5 and 1.5 times respectively the current value b) if the workload on the source nodes 143, 19 and 92 becomes 1.8, 1.65 and 1.65 times respectively the current value times". We compare Predico's prediction with ground truth values observed in the traces to compute the errors. Figure 13(c) plots the errors for the two queries for the downstream nodes in terms of normalized RMS error.

The trace collected from the stock trade processing application only contain the requests going out of each node and we assume that these requests are equally distributed among all its outgoing edges. Similarly, in the case of the market data dissemination application, the traces contain the bytes sent out on each edge and we assume that the number of bytes are an approximation of the number of requests. We note that even under these simplifying assumptions, Predico is able to make predictions with errors between 8% and 18%.

Related Work

A number of recent efforts have focused on building systems for performing whatif analysis on various distributed systems. The design and implementation of a selfpredicting cluster-based storage system is presented in [START_REF] Thereska | Informed data distribution selection in a self-predicting storage system[END_REF]. The approach, however, involves intrusive instrumentation of the system that is not feasible in production environments. WISE [START_REF] Tariq | Answering what-if deployment and configuration questions with wise[END_REF] is a system for answering what-if deployment and configuration questions for content distribution networks (CDN). WISE, however, only answers questions related to network latency and does not consider the server processing within data centers.

Apart from systems that are directly aimed at performing what-if analysis, a number of modeling techniques have been proposed that predict the performance of the system and can be employed for answering what-if questions about the system. Most of these techniques are aimed at multi-tiered systems. A number of these techniques use queuing models to predict the response time and resource utilization of such applications [START_REF] Urgaonkar | An Analytical Model for Multi-tier Internet Services and Its Applications[END_REF], [START_REF] Bennani | Resource allocation for autonomic data centers using analytic performance models[END_REF], [START_REF] Diao | Modeling differentiated services of multi-tier web applications[END_REF]. Similar to our approach, least squares is used to parameterize the queuing models in [START_REF] Zhang | A regression-based analytic model for dynamic resource provisioning of multi-tier applications[END_REF]. Similar to our automatic model derivation, the authors of [START_REF] Jiang | Discovering Likely Invariants of Distributed Transaction Systems for Autonomic System Management[END_REF] also automatically derive node-level models to capture relationships between workload; their technique is based on linear models while we have used a queuing-network modeling based approach. In [START_REF] Stewart | Exploiting nonstationarity for performance prediction[END_REF], nonstationarity in workloads is utilized to derive models for predicting the resource utilization and response time of an application as a function of workload volume and workload mix. The modeling approach proposed in [START_REF] Stewart | Performance Modeling and System Management for Multi-component Online Services[END_REF] creates "profiles" for the different components of a distributed application to model the resource demands placed by the components under different workloads on the underlying hardware. IRONModel [START_REF] Thereska | Ironmodel: robust performance models in the wild[END_REF] proposes a modeling architecture for creating robust models. The models are used for answering what-if questions about the impact of reconfigurations on the response time and throughput of a large storage system. In contrast to these systems, Predico is aimed at large-scale systems and enables easily modeling arbitrary distributed applications by joining together individual node-level models. Modellus [START_REF] Desnoyers | Modellus: Automated Modeling of Complex Internet Data Center Applications[END_REF] also uses composition of models to model data center applications. Modellus, however, models workload-to-workload interactions only while Predico looks at response time models as well. Also, Modellus is only a modeling framework, while Predico combines modeling with a full-scale what-if analysis system.

Conclusions

Data center operators often need to ascertain the impact of unseen workload changes on large distributed applications. Predicting how a certain change in workload will influence complex data center applications is a challenging problem that needs automation. In this paper we presented Predico, a system which enables the user to perform "what-if" analysis on large distributed applications. Predico is non-intrusive and only uses commonly available monitoring data to construct models and uses a new change propagation technique to estimate the impact of specified workload changes.

We modeled a large-scale data center application as an open network of queues to derive resource utilization, latency and workload models. We used traces from two large production applications from data centers of a major financial institution and data from synthetic enterprise applications to evaluate the efficacy of Predico's what-if modeling framework. Our experimental evaluation validated the accuracy of the node-level resource utilization, response time and workload models and then showed how Predico enables what-if analysis in two different applications.

Acknowledgements: This reseach was supported in part by NSF grants CNS-0855128, CNS-0916972, CNS-0720616 and OCI-1032765.

Fig. 1 .

 1 Fig. 1. Stock Price and Market Data Dissemination Application; only a subset of the application is shown for brevity.

Fig. 2 .

 2 Fig. 2. Modeling a data center application using an open network of queues

Fig. 4 .

 4 Fig. 3. Node-level model

Fig. 5 .

 5 Fig. 5. The grammar for Predico's What-If Query Language (WIFQL)

Fig. 6 .

 6 Fig. 6. Predico Architecture

Fig. 9 .

 9 Fig. 9. Composed modeling for Market Data Dissemination App

Fig. 10 .

 10 Fig. 10. Composed Modeling for Stock Trade Processing App

Fig. 11 .

 11 Fig. 11. Prediction Errors of composed modeling on different topologies

Fig. 12 .

 12 Fig. 12. What-If case study on Market Data Dissemination Application

-

  Intelligent query execution: Predico uses a novel change propagation algorithm that uses these models to execute a what-if query and determine the impact of a workload change on other components. This algorithm first computes an influence graph to determine which application components are impacted by the specified whatif query and then uses a change propagation technique to propagate the specified workload change through each component in the influence graph. -Prototype Implementation: We have implemented a prototype of our Predico whatif modeling framework. Our prototype incorporates a What-If Query Language (WIFQL) that can be used by administrators to pose queries. Since our prototype needs to handle large data center applications with hundreds of interacting components, we implement several optimizations to scale the modeling framework to such large applications. Specifically Predico uses on-the-fly model construction and employs a cache of previously constructed models to reduce model computation overhead.

-Evaluation based on real traces and real-world synthetic applications: We conduct an experimental evaluation of Predico using traces of two large production applications from a financial institution as well as realistic synthetic applications. Our experimental results validate the accuracy of Predico's modeling framework in building node-level resource usage, latency and workload models and illustrate Predico's ability to enable accurate what-if analysis.

  Input : node-level models and influence graph for a what-if query Output: value of workload/resource usage at "what" nodes/edges for s In "if" nodes/edges do

	nodeQueue ← s
	while nodeQueue = ∅ do
	currentNode ← Pop(nodeQueue)
	for e In GetIncomingEdges(currentNode) do
	if ValueChanged(e) then
	GetChangedValue(e)
	else
	GetUnchangedValue(e)
	for o In GetOutgoingEdges(currentNode) do
	if o is in the influence graph then
	use node-level model of currentNode to find workload value on o
	SetValue(o)
	ValueChanged(o) = TRUE
	for c In GetChildNodes(currentNode) do
	if c is in the influence graph then
	Push(nodeQueue,c)

Table 1

 1

	lists the charac-

Table 1 .

 1 Characteristics of Production Traces

  What-If case study on Stock Trade Processing Applicationfrom hour h 1 and then predicts the workload values in hours h 2 and h 3 . We compare the ground truth value of the workload seen in the two hours and compare Predico's predictions to compute the errors. Figure12(c) plots the errors on all the downstream edges in terms of the normalized RMS error for each of the two changes mentioned in the what-if question.

	34	143 235 206 (a) Subgraph 2 19	92 (b) Subgraph 2 Average Workload Prediction Node Hour 143 19,92 h1 A B h2 1.12 A 1.5 B h3 1.8 A 1.65 B	8 10 18 16 14 12 % Error 6 4 2 0	h2 Prediction error on nodes h3 Node 34 Node 235 Node 206 Prediction Hour (c) Prediction Errors
		Fig. 13.

This assumption is easily relaxed and we employ it for simplicity of exposition.

the values of the per-class service rates on each of the 2 nodes and then use these values to predict the per-node resource utilizations and per-node per-class response time for the other half. The per-node response times are summed up to get the end-to-end latency. We compute the prediction errors by comparing the predictions of the node-level models with the values observed during the experiments. Figure 7 and Figure 8 shows the distribution of prediction errors in terms of percentage relative error in predicting the resource utilization and latency respectively.

By using an open network of queue modeling, we are able to predict node-level CPU utilization to within 2% of the actual value. The median prediction error for response time using our modeling approach is less than 10%.

Accuracy of Node-level Workload Models

We evaluate the accuracy of using piecewise-linear functions created by using MARS to model the relationship of the outgoing workload of a node with the incoming workload of the node. We use the traces collected from the two applications to create these models and then ascertain the accuracy of these models.

For each of the two applications, we selected each component in turn and extracted the data for the workload on its incoming edges and outgoing edges. We then use MARS to estimate a function which expresses the workload on each outgoing edge of a component as a piecewise linear function of the workload on all the incoming edges on the component. We evaluate the accuracy of the piecewise linear model in predicting the workload on each outgoing edge of this component. Cross-validation was used to measure the prediction accuracy; we divide the trace data for the selected component into training windows of 1 hour each and compute a model using MARS for each window for each outgoing edge. We then use each model to predict the data points outside of the window it was trained on; the deviations between the predicted and actual values were measured. We use the root mean square (RMS) error as a metric of error; we divide the RMS error by the range of actual values to report the results in normalized RMS error (%). The average normalized RMS error for the models of all the outgoing edges of a component is taken as the error for that component. We depict the errors for all


Abdelkader Ouali
email: abdelkader.ouali@unicaen.fr

Samir Loudni

Yahia Lebbah

Patrice Boizumault

Albrecht Zimmermann

Lakhdar Loukil

Efficiently Finding Conceptual Clustering Models with Integer Linear Programming

Conceptual clustering combines two long-standing machine learning tasks: the unsupervised grouping of similar instances and their description by symbolic concepts. In this paper, we decouple the problems of finding descriptions and forming clusters by first mining formal concepts (i.e. closed itemsets), and searching for the best k clusters that can be described with those itemsets. Most existing approaches performing the two steps separately are of a heuristic nature and produce results of varying quality. Instead, we address the problem of finding an optimal constrained conceptual clustering by using integer linear programming techniques. Most other generic approaches for this problem tend to have problems scaling. Our approach takes advantageous of both techniques, the general framework of integer linear programming, and high-speed specialized approaches of data mining. Experiments performed on UCI datasets show that our approach efficiently finds clusterings of consistently high quality.

Introduction

Data clustering is one of the foundational data mining tasks. Whether it is for the purpose of "unsupervised classification", data reduction, or anomaly detection, identifying groups of similar data points is an important task. Conceptual clustering [START_REF] Michalski | [END_REF]Fisher, 1987;[START_REF] Perkowitz | [END_REF][START_REF] Pensa | [END_REF] provides an additional aspect: the description of clusters by symbolic concepts, typically the domain of concept learning. Traditional approaches [START_REF] Michalski | [END_REF]Fisher, 1987] combine the formation of the clusters and of the descriptions, having to trade off the demands of one versus the other. Newer techniques [START_REF] Perkowitz | [END_REF][START_REF] Pensa | [END_REF] have instead chosen to decouple finding the descriptions -either before or after the clustering process -and the clustering step.

Given the large search space to traverse, all those techniques are heuristic, meaning that results are heavily influenced by the initialisation conditions, typically requiring numerous restarts, increasing computational costs. Once those have been performed, an additional question is how to identify the relevant result, as we will illustrate in the experimental section (Section 6).

To address this problem, we combine two exact techniques: we use closed itemset mining [START_REF] Uno | [END_REF] (or formal concept analysis) to discover candidates for descriptions, and integer linear programming (ILP) to select the best clusters (according to an objective function) that can be described by those descriptions. This results in a single optimal solution to the problem setting.

In ILP, this problem has been introduced as set partitioning and set covering problems [START_REF] Nemhauser | [END_REF], applied to clustering tasks in [Hansen et al., 1994], and adapted for constrained clustering in [Mueller and Kramer, 2010]. Exact techniques, such as the ones described in this latter work and in [Guns et al., 2013] tend to have problems scaling, and as a side-effect fix the number of clusters to make the problem tractable. In contrast to this, our adoption of closed itemsets cuts down on redundancy compared to other ways of selecting candidate clusters and our use of advanced ILP techniques give our approach additional flexibility.

Our contribution is therefore twofold: we propose an efficient technique for conceptual clustering, based on closed itemsets, that 1. is more flexible in terms of the constraints that can be enforced than existing approaches, and 2. gives more control and stronger guarantees to the user than existing heuristic approaches. The next section introduces the concepts used in this paper. Section 3 describes how different clustering tasks can be expressed as ILP problems, and Section 4 how to solve them. We discuss related work in Section 5 before demonstrating our technique's performance in Section 6. Section 7 concludes and points towards future research directions.

Definitions

In this section we introduce the definitions and concepts that we will use throughout this paper.

Formal concepts

Let I be a set of n distinct literals called items, an itemset (or pattern) is a non-null subset of I. The language of itemsets corresponds to L I = 2 I \∅. A transactional dataset is a multi-set of m itemsets of L I . Each itemset, usually called a transaction or object, is a database entry. For instance, Table 1a gives a transactional dataset T with m=11 transactions t 1 , . . . , t 11 described by n=8 items A, B, C, D, E, F, G, H.

Let R be a binary relation between the set T of transactions and the set I of items s.t. (t, i) ∈ R if the transaction t contains the item i : i ∈ t. We denote by R = (T , I, R) the tuple formed by these sets of transactions, items and the binary relation. R is called formal context [Ganter and Wille, 1997]. Two operators are defined:

• Let I ⊆ I, ext(I) = {t ∈ T | ∀i ∈ I, (t, i) ∈ R} • Let T ⊆ T , int(T ) = {i ∈ I| ∀t ∈ T, (t, i) ∈ R} ext(I)
is the set of transactions containing all items in I. int(T ) is the set of items contained by all transactions in T . These two operators induce a Galois connection between 2 T and 2 I , i.e. T ⊆ ext(I) ⇔ I ⊆ int(T ).

A pair such that (I = int(T ), T = ext(I)) is called formal concept. This definition defines a closure property on dataset T , closed(I) ⇔ I = int(ext(I)). An itemset I for which closed(I) = true is called closed pattern.

Using ext(I), we can define the frequency of a concept: freq(I) = |ext(I)|, and its diversity:

divers(I) = t∈ext(I) |{i ∈ I | (i / ∈ I) ∧ (i ∈ t)}|.
Additionally, we can refer to its size:

size(I) = |{i | i ∈ I}|.

Conceptual clustering

Clustering is the task of assigning the transactions in the data to relatively homogeneous groups. Conceptual clustering aims to also provide a distinct description for each clusterthe concept characterizing the transactions contained in it.

This problem can be formalized as: "find a set of k clusters, each described by a closed pattern P 1 , P 2 , ..., P k , covering all transactions without any overlap between clusters". For instance, Table 1b reports the various clusterings for k=3.

An evaluation function f is needed to express the goodness of the clustering. So, conceptual clustering looks for a disjoint set of clusters of T that optimizes a given criterion of clustering quality. For instance, for dataset T and k=3, minimizing f (P1, ..., P k ) = 1≤i≤k divers(Pi) provides one clustering s 1 , with optimal value 18 (see Table 1b).

Other clustering settings

Other clustering settings [Berkhin, 2006], e.g. soft clustering, co-clustering, and soft co-clustering, can also be expressed by the relationship between transactions and closed patterns. a. Co-clustering consists of finding k clusters covering both the set of transactions and the set of items, without any overlap on transactions or on items. For instance, s 1 provides a co-clustering on the transactional dataset T (see Table 1b). b. Soft clustering consists of relaxing:

• either the coverage relation: not all transactions are covered, but at least δ t transactions must be covered, where threshold δ t ≤ |T |(= m)

• or the non-overlap relation: small overlaps are allowed, but a transaction t cannot occur in more than δ o clusters, where threshold δ o ≥ 1 c. Soft co-clustering consists of relaxing the coverage or the non-overlap relations for transactions (as for soft clustering), but also the coverage or the non-overlap relations for items:

• not all items are covered, but at least γ i items must be covered, where threshold γ i ≤ |I|(= n) • small overlaps are allowed, but an item i cannot occur in more than γ o co-clusters, where threshold

γ o ≥ 1 Example 1 For δ t =6, δ o =1, γ i =7, γ o =2, s r = [{A, E}, {B, E, G}, {C, F, G,
H}] is a soft co-clustering since D is the only missing item, items E and G occur twice and {t 1 , t 7 , t 8 , t 9 , t 10 } are the uncovered transactions.

Integer Linear Programming

Integer Linear Programming (ILP) [START_REF] Nemhauser | [END_REF] is one of the most widely used methods for handling optimization problems, due to its rigorousness, flexibility and extensive modeling capability. An ILP program is a linear program with the added restriction that all the variables must be integer. Typically, an ILP model involves: (i) a set of decision variables, (ii) a set of linear constraints, where each constraint requires that a linear function of the decision variables is either equal to, less than, or greater than, a scalar value, and (iii) an objective function that assesses the quality of the solution. Solving an ILP problem consists of finding the best solution w.r.t. the objective function in the set of solutions that satisfy the constraints. Formally, an ILP problem takes the form:

Maximize or Minimize c T x Subject to Ax (≤, =, or ≥) b xi ∈ Z, i = 1..n (1)
where x represents the vector of decision variables, n is the total number of integer variables, c j (1≤j≤ n) are referred to as objective coefficients, A is an m × n matrix of coefficients, and b is an m × 1 vector of the right-hand-side values of the constraints.

ILP models

This section describes ILP models for the different clustering problems introduced in the previous section.

Conceptual clustering

Let T be a dataset with m transactions defined on a set of n items I. Let C be the set of p closed patterns (w.r.t. the frequency measure). Let a t,c be an m×p binary matrix where (a t,c = 1) iff c ⊆ t, i.e., the transaction t belongs to the cluster represented by the closed pattern c. Hence, the conceptual clustering problem can be modeled as an ILP (see Fig. 1a) using p boolean variables x c , (c ∈ C), where (x c = 1) iff the cluster represented by the closed pattern c belongs to the clustering. Constraints (1) state that each transaction t must be covered by exactly one cluster c. Constraint (2) restricts the number of clusters to k=k 0 clusters. The objective function is defined by associating to each cluster c a value v c reflecting the interest (maximize) or cost (minimize) of the cluster c, e.g. minimizing each concept's diversity or maximizing their size.

Trans.

Items t1 A B D t2 A E F t3 A E G t4 A E G t5 B E G t6 B E G t7 C E G t8 C E G t9 C E H t10 C E H t11 C F G H (a) Transactional dataset T . Sol. P1 P2 P3 s1 {A, B, D} {C, F, G, H} {E} s2 {B} {C} {A, E} s3 {A} {C} {B, E, G}
(b) Three conceptual clusterings for k=3.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

t1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 t2 1 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 t3 1 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 t4 1 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 t5 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 1 t6 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 1 t7 0 0 0 0 0 0 0 1 1 1 0 0 1 0 1 1 0 1 t8 0 0 0 0 0 0 0 1 1 1 0 0 1 0 1 1 0 1 t9 0 0 0 0 0 0 0 1 1 0 1 0 0 1 1 0 0 0 t10 0 0 0 0 0 0 0 1 1 0 1 0 0 1 1 0 0 0 t11 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 1 1 (c) (at,c) matrix associated with dataset T .
Table 1: Running example. The quality measures we have introduced are related individually to the given patterns. The number of clusters k can also be defined as a variable whose value will be determined by the ILP solver. Constraint (2') illustrates how to control k by specifying a lower bound k min and/or an upper bound k max . Relaxing k removes constraints on the clustering and hence enables finding results from a larger solution space, giving our approach more flexibility (see Section 6.b).

Optimize c∈C vc . xc Subject to (1) c∈C at,c . xc = 1, ∀t ∈ T (2) c∈C xc = k0 xc ∈ {0, 1}, c ∈ C (a) ILP model for conceptual clustering (M1). Optimize c∈C vc . xc Subject to (4) yt ≤ c∈C at,c . xc ≤ δo . yt, ∀t ∈ T (5) t∈T yt ≥ δt (6) zi ≤ c∈C wi,c . xc ≤ γo . zi, ∀i ∈ I (7) i∈I zi ≥ γi k = c∈C xc kmin ≤ k ≤ kmax k ∈ N, xc ∈ {0, 1}, c ∈ C yt ∈ {0, 1}, t ∈ T zi ∈ {0, 1}, i ∈ I (c) ILP model for soft co-clustering (M3). Optimize c∈C vc . xc Subject to (1) c∈C at,c . xc = 1, ∀t ∈ T (2) k = c∈C xc (2 ) kmin ≤ k ≤ kmax (3) c∈C wi,c . xc = 1, ∀i ∈ I k ∈ N, xc ∈ {0, 1}, c ∈ C (b) ILP model for co-clustering (M2).
Example 2 Consider the dataset T of Table 1a. The (a t,c ) matrix associated with T is outlined in Table 1c. If we consider v c =size(c), then the solution that maximizes the objective function is x 2 =x 12 =x 15 =1, and all other variables x c are equal to 0 (so, k=3). This solution corresponds to the clustering s 1 (see Table 1b).

Co-clustering

Co-clustering consists of finding k clusters covering both the set of transactions and the set of items, without any overlap on transactions and on items. Let w i,c be an n × p binary matrix where (w i,c = 1) iff the item i belongs to the closed pattern c. Fig. 1b depicts the ILP model. Constraints (3) state that each item i must be covered by exactly one cluster c.

Example 3 The optimal solution x 2 =x 12 =x 15 =1 and all other variables x c equal to 0, corresponding to s 1 (see Table 1b) is a co-clustering since the associated clusters cover both sets I and T without overlap.

Soft clustering and soft co-clustering

For soft conceptual clustering (see Section 2.3b), we introduce m boolean variables y t , (t ∈ T ) such that (y t = 1) iff transaction t belongs to at least one cluster. Fig. 1c depicts the ILP model. First, as t∈T y t indicates the number of covered transactions, Constraint (5) states that at least δ t transactions must be covered. Second, as a transaction t belongs to c∈C a t,c x c clusters, Constraint (4) states that each transaction t must belong to at most δ o clusters. Note that if y t =0, then transaction t is not covered and Constraint (4) is satisfied.

We proceed in the same way for soft co-clustering (see Section 2.3c), by introducing n boolean variables z i , (i ∈ I) such that (z i = 1) iff item i belongs to at least one cluster. First, as i∈I z i indicates the number of covered items, Constraint (7) states that at least γ i items must be covered. Second, as an item i belongs to c∈C w i,c x c clusters, Constraint (6) states that each item i must belong to at most γ o clusters. Note that if z i =0, then item i is not covered and Constraint (6) is satisfied. Example 1 provides an example of soft co-clustering.

Additional constraints can be added in order to avoid undesired clusterings. For instance, one can specify extra constraints on the frequency of closed patterns (e.g. freq(c) > 1) which leads to a more balanced clustering for the dataset T , and may avoid outliers receiving their own clusters. In this case, the optimal solution to our running example is x 4 =x 7 =x 8 =1, and all other variables x c are equal to 0. It corresponds to the conceptual clustering s 3 (see

Preprocessing and solving

We have defined an ILP framework to express various kinds of clusterings. The strength of this framework lies in its flexibility in terms of the constraints that can be enforced. In Section 3, we defined constraints that enforce global restrictions on the clusters such as: clusters cover all of the transactions (or a minimum number of them), clusters should be disjoint (or have restricted overlaps), etc. But, in practice, there might be local constraints that should be defined on each individual closed pattern such as :

minimum and maximum frequency constraints, -MustLink(ti, tj) requires that transaction t i should be in the same cluster as t j , -CannotLink(ti, tj) requires that transaction t i should not be in the same cluster as t j .

The more selective local constraints are, the fewer the number of closed patterns for the solving step. Finally, the whole clustering process consists of the following two main steps: -Preprocessing step: compute closed patterns using efficient state-of-the-art extractors, e.g. LCM, and filter those violating local constraints. Constraints like minimum frequency and size are directly handled by the extractor. For CannotLink(ti, tj), any cluster c s.t. t i and t j belongs to ext(c) is removed. MustLink constraints are handled similarly.

-Solving step: solve one of the ILP clustering models detailed in Section 3 using efficient ILP solvers.

Related work

Conceptual clustering has been introduced in [Michalski, 1980], and extended in [START_REF] Michalski | [END_REF]Fisher, 1987]. Numerous approaches have been devised for tackling this problem, e.g. of statistical, syntactic or hierarchical nature [Schalkoff, 2008], with hierarchical conceptual clustering arguably the most prominent one among them [Fisher, 1987;[START_REF] Thompson | [END_REF]. Heuristic approaches Several methods have explored the idea of decoupling cluster-formation from finding the conceptual descriptions. Notably, Pensa et al. [START_REF] Pensa | [END_REF] also begin by mining closed (or δ-closed) patterns (itemsets) and their extensions and then perform k-Means clustering on them. Perkowitz and Etzioni [START_REF] Perkowitz | [END_REF], reverse the two phases: their cluster-mining first uses a clustering technique to form clusters. From the resulting clustering, descriptions are learned by a rule-learning technique. Instances are matched to descriptions, potentially leading to overlapping clusters. Finally, [START_REF] Geerts | [END_REF] introduced tiling. A tile is a formal concept, and in that work two settings are considered: i) finding k tiles that cover as many transactions as possible, and ii) finding the minimum number of tiles that cover all transactions. Both are clearly conceptual clustering settings but since tiles can overlap, so can clusters. CP/SAT for pattern set mining. The CP-paradigm is at the core of generic approaches to deal with k-pattern sets [START_REF] Khiari | [END_REF]Guns et al., 2013]. These methods allow to model sets of patterns, satisfying properties on the whole set, in a declarative and flexible way, such as conceptual clustering, k-tiling, to name a few, but they look for sets containing a fixed number of patterns and tend to have problems scaling. In [START_REF] Métivier | [END_REF], the authors formulate the conceptual clustering task as queries in given language. These queries are then translated into SAT clauses and resolved by a SAT solver. However, the proposed framework does not allow to express optimization criteria and has problems scaling. ILP/CP for distance-based clustering. Distance-based clustering relies upon dissimilarities (or similarities) between numerical attributes. In this line, several declarative approaches have been proposed. In [START_REF] Dao | [END_REF], a CP approach has been used. The proposed approach supports various kinds of user constraints. In [Babaki et al., 2014], an exact approach, which uses column generation in an ILP setting, is presented. This approach extends the one proposed in [Aloise et al., 2012]. In [Mueller and Kramer, 2010], a constrained clustering approach using ILP is proposed. This approach takes as input a set of possible base clusters and builds a clustering by selecting a suitable subset. The number of clusters k must be given upfront. In contrast, our proposal allows relaxing k by specifying lower/upper bounds. In their experiments, the set of base clusters is generated from frequent patterns. This makes the approach less applicable, because the number of base clusters is huge and selecting a suitable subset is challenging. Our adoption of closed patterns cuts down on redundancy compared to other ways of selecting candidate clusters and makes the solving step more efficient by reducing dramatically the number of candidate clusters.

Experiments and Results

The experimental evaluation is designed to address the following questions:

1. How (in terms of CPU-times) does our approach (CCLP) compare to the CP approach of Guns et al.

(KPatternSet) and the approach of Mueller et al.?

2. How do the resulting clusters compare w.r.t. different objective functions?

3. In light of the exact nature of our approach, how do the resulting clusters and their descriptions compare qualitatively with those resulting from existing heuristic approaches that operate in a similar framework? The two approaches with which we compare ourselves are those of Pensa et al. (CDKMeans) and Perkowitz et al. (CM). Experimental protocol. Experiments were carried out on the same datasets which were used in [Guns et al., 2013] and available from the UCI repository. Table 2 shows the characteristics of these datasets. All experiments were conducted on AMD Opteron 6282SE with 2.60 GHz of CPU and 512 GB of RAM. We used LCM to extract the set of all closed patterns and CPLEX v.12.4 to solve the different ILP models. For all methods, a time limit of 24 hours has been used.

Experiments have been performed without any local constraints on individual closed patterns. To evaluate the quality of a clustering, we test the coherence of a clustering, measured by the intra-cluster similarity (ICS) and the interclusters dissimilarity (ICD), both of which should be as large as possible. Given a similarity measure s between two transactions t and t , where s :

T × T → [0, 1], s(t, t ) = |t∩t | |t∪t | ICS(P1, ..., P k ) = 1 2 1≤i≤k ( t,t ∈P i s(t, t )) ICD(P1, ..., P k ) = 1≤i<j≤k ( t∈P i ,t ∈P j (1 -s(t, t )))
(a) Comparing CCLP with KPatternSet. Figs. 2a and2c compare the performance of the two methods on model M1 for various values of k on different datasets w.r.t. the first optimization setting (i.e. description size). The CPU-times of CCLP-M1 include those for the preprocessing step. For (k = 3), KPatternSet dominates CCLP-M1 except on Soybean, Zoo-1 and Mushroom. But, for (k ≥ 4), CCLP-M1 outperforms KPatternSet by several orders of magnitude on all datasets. Finally, KPatternSet fails to find a solution within the time limit for (k > 5). On Audiology dataset, both approaches were not able to find a solution. This is in part explained by the number of closed patterns (10 6 ) in comparison to the other datasets (from 10 3 to 10 5 ). For the second optimization setting (see Fig. 2b), the same observations can be made. Note that on Tic-Tac-Toe no conceptual clustering exists for (k = 4). Both settings obtain the same best value for k. Indeed, there is a bias towards a k near k max when using the description size. When comparing the CPU-times, CCLP-M1-relaxed is often faster, particularly on the two most difficult datasets Anneal and Hepatitis (speed-up of up to 3.84). Contrary to Mueller et al., our approach allows to relax k. To compare the two, we implemented the mean of inner cluster similarities (i.e., s(x, y)), the objective function used by that work, for fixed k (denoted CCLP-M1-Dist). Fig. 2d compares CCLP-M1-relaxed with CCLP-M1-Dist in terms of the best k found, and CPU-times. Both approaches almost always agree on the best value for k and obtain comparable CPU-times on the first 7 datasets, while on the two difficult datasets CCLP-M1-relaxed is clearly better. Fig. 3d shows that clusterings found by relaxing k are close to those found with fixed k Finally, in Fig. 2d, one can see that the preprocessing step is negligible as compared to the solving step, except on the two last datasets due to the high number of closed patterns. (c) Qualitative analysis of clusterings. To assess the quality of clusterings, we have plotted their values according to measures ICS and ICD. Points (see Fig. 3) represent the optimal clusterings obtained for different values of k on the selected datasets. A specific color is assigned to each dataset. A label, representing the value of k, is associated to some points with the same color. Moreover, we omitted to plot points that are on the Pareto front in Figs. 3b and 3c since they are incomparable. Fig. 3a shows the two optimization criteria of CCLP-M1. Except for the Vote and Tic-Tac-Toe datasets, the diversity measure sacrifices ICS to achieve higher ICD values. This is indicative of more balanced clusters: the ICS is necessarily limited by the number of instances per cluster but the ICD increases if there are more instances in other clusters to compare against. The size measure shows the opposite behavior, which is indicative of one (or a few) large clusters, and numerous smaller ones.

To compare with CDKMeans and CM,1 we first have to identify a good comparison clustering. To that end, (i) we ran each technique 100 times to smooth out the random initialization effects typical for k-Means, (ii) then we grouped the resulting into equivalence classes, in which clusterings agree on the composition of all clusters, (iii) finally, we chose the largest equivalence class and used its representative (i.e. one of the clusterings in it, since all have the same composition). If there were several equally large equivalence classes, we used a representative from each class.

The results show how difficult it can be to control the results of heuristic techniques: the representative clusterings of the CM approach never cover all transactions in the data, and often have overlapping clusters. Fig. 3b shows that the clusterings computed by CM have a qualitative disadvantage compared to the clusterings found by CCLP-M1 (points of CM are always dominated by those of CCLP-M1). For the sake of fair comparison, we run CCLP-M3 with settings that allowed similar amounts of non-coverage. In case that several equally large equivalence classes existed, we chose the clustering that maximized ICS and ICD and used its coverage as constraint for CCLP-M3. Figure 3c shows that our framework can approximate the results of the heuristic technique.

CDKMeans is even more difficult to control by the user: when using all closed patterns, the algorithm usually assigns all instances to one or two clusters, no matter k. Enforcing frequency constraints improves this situation somewhat even though |C| ≤ k for k ≥ 4. Additionally, the clusterings occasionally fail to stabilize, resulting in 100 different clusterings. Finally, the particular representation of clusters in CDKMeans can result in clusters that have descriptions yet no transactions assigned to them.

Conclusions

We have proposed an efficient approach for conceptual clustering that uses closed itemset mining to discover candidates for descriptions, and ILP to select the best clusters. Closed itemsets cut down on redundancy compared to other ways of selecting candidate clusters and ILP gives our approach more flexibility than exact ones, and stronger guarantees to the user than heuristic ones. We plan to exploit local search techniques to enhance the solving step. 3 4 5 6 7 8 9 10 3 4 5 6 7 8 9 10 3 4 5 6 7 8 9 10 3 4 5 6 7 8 9 10 3 4 5 6 7 8 9 10 3 4 5 6 7 8 9 10 3 4 5 6 7 8 9 3 4 5 6 7 8 9 10 3 4 5 6 7 8 9 10 3 4 5 6 7 8 9 10 3 4 5 6 7 8 9 10 3 4 5 6 7 8 9 10 3 4 5 6 7 8 9 10 3 4 5 6 7 8 9

Figure 1 :

 1 Figure 1: ILP models for conceptual clustering.

  (b) Impact of relaxing k. To assess the interest of relaxing k, Fig. 2d compares the performance of CCLP-M1 with k relaxed (CCLP-M1-relaxed) against CCLP-M1 in terms of the best value found for k (Col. 2 vs. Col. 5) and CPU-times (Col. 4 vs. Col. 7). Reported in Col. 5 are the best values found for k (3≤k≤10) that maximize the description size.

  Maximizing the description size.

Figure 2 :

 2 Figure 2: Comparing CPU-times.

  CCLP-M3 with Diversity vs. Cluster Mining (CM).

  using CCLP-M1-Relaxed-Size primary-tumor using CCLP-M1-Dist lymph using CCLP-M1-Relaxed-Size lymph using CCLP-M1-Dist vote using CCLP-M1-Relaxed-Size vote using CCLP-M1-Dist zoo-1 using CCLP-M1-Relaxed-Size zoo-1 using CCLP-M1-Dist mushroom using CCLP-M1-Relaxed-Size mushroom using CCLP-M1-Dist tic-tac-toe using CCLP-M1-Relaxed-Size tic-tac-toe using CCLP-M1-Dist (d) CCLP-M1-relaxed with Size vs. CCLP-M1-Dist.

Figure 3 :

 3 Figure 3: Comparing the quality of the resulting clusterings.

  Table 1b).

	dataset	#transactions #items density(%) Number of closed itemsets
	Soybean	630	50	32	31,759
	Primary-tumor	336	31	48	87,230
	Lymph	148	68	40	154,220
	Vote	435	48	33	227,031
	tic-tac-toe	958	27	33	42,711
	Mushroom	8124	119	18	221,524
	Zoo-1	101	36	44	4,567
	Hepatitis	137	68	50	3,788,341
	Anneal	812	93	45	1,805,193

Table 2 :

 2 Dataset characteristics.

For CM we used SimpleKMeans and JRip in Weka. We reimplemented CDKMeans : http://www.scientific-datamining.org/software/cdkmeans.zip.

Acknowledgements.

This work was partially supported by the Eiffel Excellence program -French Ministry of Foreign Affairs and International Development, REFERENCE: UR / EIFFEL-DOCTORAT 2015 / 840868H. This work was partly supported by the ANR (French Research National Agency) funded project Hybride ANR-11-BS002-002.