Towards Effective Prioritizing Water Pipe Replacement and Rehabilitation

1 Introduction

Clean water, distributed through a complex and growing network of water pipes, is essential for people's daily life. In fact, the large-scale urban water pipe networks are in fast growth to meet the increasing demand arising from the fast developing urban areas. However, the structural deterioration has presented great challenges to worldwide water utilities, posing a critical threat to not only the daily life but also a sustainable society since water is an essential and precious resource of human beings. For example, it is estimated that more than $32 billion cubic meters of treated water physically leak annually through distributed network worldwide [Kingdom et al., 2006]. And the corresponding total annual cost is around $ 14 billion [Kingdom et al., 2006]. As reported in [Carter and Rush, 2012], the New York City has spent $54.6 million to manage its break pipes from 1997 to 2011. As few municipalities can afford to systematically inspect all of their pipes in their water network due to scale of the water network and the difficulty of inspections - most pipes are laid underground, the task of proactively pinpointing those 'most-likely-to-fail' pipes, which enables cost-effective replacement and rehabilitant, becomes an important problem for a sustainable society.

∗The work is partially supported by NSF IIS-1116886, NSF IIS1049694, NSFC 61129001/F010403 and the 111 Project (B07022).

Formally, given 1) a prediction time point or window, 2) the pipe-specific failure sequence and 3) the associated attributes, one aims to predict the failure likelihood on a single pipe-wise level. It leads to a binary supervised learning problem if the failed pipes are regarded as positive samples and non-failure ones negative; and if one further considers the fact that negative samples are censored, survival analysis models are assumed to better capture this subtle difference of the censored data from other type data during learning. This paper further formulates the problem into a stochastic process.

The pipe failure problem has been an issue of concerning for municipal engineers since the early studies [Arnold, 1960; Clark, 1960; Niemeyer, 1960; Remus, 1960]. Traditionally, subject matter experts (SME) devise certain business rules to decide which pipes are risky and should receive top fixing priority. While such an intensive domain knowledge driven methodology usually involves ad-hoc rule definition and is not conveniently scalable when new attributes arrive. Existing pipe integrity management methodologies mostly focus on oil and gas, and many risk factor framework have been proposed in these areas such as the report from the Pipeline Research Council International and the manual by [Muhlbauer, 2004], where 9 categories are classified in the former and 4 in the latter. Compared with oil/gas transmission pipelines, urban water distribution network usually has less data available in fine-granularity. A practical way is to categorize the factors into physical indicators, load, corrosion, weather and historical failure record.

Another research line adopts the methodologies from statistic field to analyze the failure problem. One can refer to [Kleiner and Rajani, 2001] for an early review. Many early work focus on descriptive analysis towards pipe failures. [Shamir and Howard, 1979] calculate the average number of failures on a unit year and unit pipe length. And the spatial and temporal patterns of water distribution pipe failure in the City of Winnipeg are examined in [Goulter and Kazem, 1998]. On the other hand, predictive modeling is also investigated. [Kleiner and Rajani, 1999] addresses the problem of forecasting the aggregated number of pipe failures for the network, which is key to beforehand planing. [Pelletier et al., 2003] performs survival analysis to predict the evolution of the annual number of pipe breaks and to estimate the impact of different replacement scenarios in real case studies. [Tian et al., 2011] uses Cox survival analysis as a pilot study for pipe failure prediction. In a recent work, a rank boosting algorithm is adopted by [Wang et al., 2013] to rank the pipe break risks. However, to our best knowledge, no previous work has presented an already-deployed system and being continuously generating the environmental and business benefits to the concerned metropolitan. Moreover, from the machine learning perspective, we originally propose to formulate the pipe failure events into a self-exciting stochastic process model.

The main contributions of this paper are in five folds:

1) We implement a web based 'environmental computing' system addressing the real-world large scale urban pipe network maintenance supporting system, and it has been deployed in a real commercial environment, generating continuous impacts and benefits for a better sustainable society;

2) We evaluate the system's prediction performances quantitatively against the traditional subject matter expert driven risk matrix method on the real-world large scale dataset. And our study further discovers some specific limitations of the risk matrix method, and verify the viability of data-driven approach towards pipe analysis;

3) Attributes closely relevant to failure are identified by computational modeling, leading the agencies to better understand the root cause of pipe failure, which in turn improves and streamlines the pipe construction and maintenance;

4) Perhaps more interestingly, the temporal clustering patterns of failure time stamps are unveiled and mathematically modeled by a self-exciting stochastic model, which outperforms a linear aging baseline. And it can work flexibly in the absence of enough attribute information; while this is often the case in practice. We are not aware of any prior work formulating the self-exciting point process for pipe failure prediction problem, nor even for asset management literatures;

5) Our novel formulation for the pipe failure prediction identifies the new problems for the machine learning community beyond conventional classifiers, leaving a broad room to boost the performance based on the this seminal work.

2 System overview

In this section, we first describe the system's main use cases, and then the studied dataset as well as the modules that comprise the J2EE web system are briefed. There are mainly three scenarios for the system, as summarized: 1) Help operator find the 'likely-to-fail' pipes; 2) Help decision maker allocate the maintenance budget; 3) Help agency reveal important factors leading to failure.

2.1 Dataset description

The used dataset is a real-world urban network from one costal metropolis, which consists of over 600,000 pipes in fresh water system and nearly 100,000 for salt. Most of the pipes are laid after 1950 and the average age is over ten years. For most samples, there is a number of profile attributes associated with each pipe. Basically, the attributes can be categorized into pipe physical indicators, load, corrosion and weather etc. In addition, as time goes by, the pipe failure event will be processed and recorded by the agency on a routinely basis. As a result, each pipe is assumed to be associated with profiling attributes and the failure records.

However, still a portion of pipes whose attributes are recorded incompletely, or not well documented, resulting in only knowing their failure records and the year when they are laid. This fact calls for new formulation beyond the off-theshelf supervised learning methods.

2.2 Functional modules

The presented system is mainly comprised of four modules: a) data cleansing; b) pattern display; c) model training; d) risk prediction. It is also equipped with a GIS component to highlight the high-risky pipes on the map, and allows the user to directly manipulate the pipes from this interface instead of using a table-style list. An overview is shown in Fig.1.

Data preprocessing: The raw data are from two datasets: a) 'profile' dataset: pipe-specific profile attribute information, such as material type, length, completion year, location etc; and b) 'working order' dataset: historical pipe failure records, location and the completion year. In order to repopulate the failure information, the correspondence matching between the two datasets is performed. Specifically, the 'pipe id' serves as the foreign key for joining, and in the cases when the 'pipe id' is missing in one dataset, location is used to find the most likely pipe in the other.

Pattern display: To give a visual perception, the cleansed data is plot regarding with various aspects including water type (fresh or salt), district, material, diameter range, and length range etc. Different visualization chart is adopted such as histogram, bar, and bubble to plot certain distributions.

Model training: Learning based classifier and stochastic process model, together with risk matrix approach are evaluated and integrated in the system for pipe failure prediction.

Risk prediction: Prediction results are displayed and can be exported in different formats including shapefile, office xlsx, and csv file for further processing and supports the decision making. Meanwhile, pipes scored with different risk levels can be highlighted as the hot spots in the map.

3 Methodology

3.1 Attribute selection

Examination of the attributes associated with the pipes will help to identify those factors that appear most susceptible to failure. Once these attributes have been identified, hopefully it will lead to a means of reducing the failure rate in the future by improving the key conditions if feasible. Through a model variable correlation analysis and feature importance qualifying, we summarize the final selected attributes feeding to the computational model in Table 1. One should note that the importance ranking is based on the available pipe profile information under a supervised learning fashion, which may not be perfectly precise because some of the raw data are difficult to collect or estimate especially for the external factors like rainfall, highway impact etc. Some other relevant factors are excluded for certain reasons: e.g. 'bury depth' is excluded due to its strong correlation with 'zoneImp' and 'joint number' is strongly correlated to 'length'. 'Pressure' is also excluded due to unacceptable amount of missing values.

3.2 Binary classifiers using attribute information

The system is equipped with several predictive models and also allows easy extension for integrating more new models. Cox Model [Cox, 1972] (together with a new survival analysis algorithm: Multi-Task Logistic Regression (MTLR) [Yu and Baracos, 2011]), Artificial Neural Network (ANN), Logistic Regression (LGR) and Chaid Tree are available in the system which explore the massive labeled training data. However, there are still some limitations: From the practical perspective, one problem is for some pipes, especially for those constructed before 1970, of which the associated attribute information is largely incomplete, inconsistent, or unreliable. And collecting the relevant attributes information is often costive and difficult, such as estimating the water turbidity, the rainfall, and the soil type etc.; the other subtle but worth-noting issue is one cannot guarantee the current system has identified exhaustively all factors with respect to pipe failure, and sometimes training based on incomplete covariants may be misleading. From the theoretical perspective, conventional binary classifiers like ANN, Logistic Regression or Chaid tree cannot naturally explore and model the particular property for 'censored' samples compared with the Cox model and the MTLR models [Yu and Baracos, 2011] etc.

As the prediction score obtained from classifiers such as ANN, Chaid Tree is not a posterior likelihood, it makes the risk measurements from fresh and salt systems are incomparable since in many cases the system user customizes and uses different models for different systems. To address this issue, the parametric Sigmoid model [Platt, 1999; Lin et al., 2007] is used in the system to calibrate the failure likelihood on an equal footing for cross-system risk ranking. Another advantage is knowing the likelihood naturally leads to the obtain of the failure number expectation for the next year. And it is informative for the decision maker to better determine and allocate the budget in advance.

3.3 Modeling temporally clustered failures using one-dimensional self-exciting process

Apart from the attribute-complete samples, there are still a few, whose attributes are missing in both fresh and salt systems. For these pipes, the above classifiers cannot be trained as no attribute data is available. On the other hand, it is appealing to suppose pipes are prone to leak repeatedly shortly after a recent failure event (even the previous failure has been fixed up) either inherently due to the damage brought by the previous failures, or externally lasting external impacts, such as road excavation. In another word, we conjecture the behind mechanism is not only due to events triggering the next in the causal sense, but also the clustering reflects the correlation of event occurrence due to unobserved variables such as geological factors and urban activities. Our inspection to the failure records verifies this idea and some examples are shown in Fig.2. In addition, such temporal clustering patterns are also observed and discussed in the previous literature [Goulter and Kazem, 1998], in the context of civil engineering study. And their empirical study further shows the temporal decay rate obeys an exponential distribution since the occurrence time instance. As a result, we are motivated to quantitatively model the failure behavior from the temporal perspective, by leveraging the historical event samples.

A series of investigations to pipe failure in New York and Philadelphia [O'Day, 1982; Ciottoni, 1983] conclude that age is not an influential factor, and our empirical study also suggests a simple assumption: the background rate of failure rate is relatively time-stationary as shown in Fig.5 for failure age distribution. Based on these assumptions, we formulate the time-stationary and temporal-clustered failures into a computationally efficient (with some mathematical approximation) self-exciting stochastic process.

Formally, given a sequence of failure events with time stamp t1, t2, ..., tn, we investigate a specific class of point processes termed as Hawkes Process [Hawkes, 1971], commonly used in earthquake analysis [Ogata, 1988; 1998], and recently used in the criminological literature [Johnson, 2008], which is modeled by a conditional intensity function:

In line with the observation made by [Goulter and Kazem, 1998], an exponential kernel is used:

where μ is the background rate controlling the intrinsic failure event influence time window, and α is the amplitude of the influence, while w-1 bears the physical implication for the average waiting time until a new failure comes. And according to [Rubin, 1972], the likelihood is given by:

To solve this problem, maximum likelihood estimation is performed in an Expectation-Maximization fashion to infer the model's parameters. While [Lewis et al., 2011] address the kernel form self-exciting terms specifically, here we begin the derivation in the context of general Hawkes process where g(x) is not specified. Let t0 = 0 and tn+1 = T , first one can obtain the log likelihood function in the form:

Observing log function is concave and G(0)=0, one can further derive the lower bound for the objective function:

where in the E-step:

Note that the above choices of pij and pii make the above lower bound tight when μ = μk and α = αk , which ensures that log-likelihood increases monotonically during the iterations. And in the M-step, the partial derivatives in terms of the objective function are given as:

Thus the updating μ and α in the kth iteration are:

Particularly, given an exponential kernel as g(t - tj) = we-w(t-tj) , we use the approximation e-w(T-ti) ≈ 0 when wT ≫ 1 as suggested in [Lewis et al., 2011] which shows the scale parameter w and α can be obtained by:

4 Experimental results

4.1 Results on attribute-complete data

The area under the Receiver Operating Characteristic (ROC) curve [Fawcett, 2006], aka. the Area Under Curve (AUC), is used to assess the predictive models in this paper. ROC has become a standard metric in the area[Provost et al., 1997]. We evaluate the performance of all testing methods regardng with overall performance as the prediction year varies from 2001 to 2011. Table 2 gives a rough statistics about the well recorded failure counts along the years. Also, the risk matrix method is quantitatively compared. Risk matrix method is popular for pipe integrity management. The main idea is to assign score to each pipe by considering the impact of the risk factors: 1) material; 2) age; 3) failure record; and 4) surrounding condition. For the samples with comeplete attributes, we evaluate three classifiers and two survival analysis models because we are interested in verifying whether the survial analysis models that are able to inherently handle censored data would outperform the other type data based approaches. For all tests, cross-validation is performed and the final AUC is obtained by averaging the hold-out testing results. In particular, for samples of fresh system, the cross-fold is set to ten; while for salt, cross-fold is five due to its smaller size.

4.2 Results on attributes-missing dataset using Hawkes Process model

We are interested in estimating the self-exciting term in the Hawkes process model thus those with zero failure record are excluded due to they can only influence the unconditional background failure rate μ. Thus basically we will select the pipes that has failed for at least once. As a case study, we collect 676 pipes whose attributes are missing/incomplete or in

(c) Fresh: exclude GI &GIL (d) Salt: exclude GI &GIL

Figure 4: Evaluation between data-driven and knowledgebased risk matrix methods using attribute-complete samples; prediction year = 2011. The diagonal in red is baseline.

low quality for fresh system, and 200 for salt. The completion date of these pipes are known 1 .

We use a concrete example to illustrate the experiment design: given a pipe with failures at: t1, t2, ..., tn, the first n-1 events are used as the training samples, and we have many samples for training the same model; while the last event at tn is used to build the reference ground truth for model testing. Specifically, the pipe is regarded as a positive testing sample if its last failure so far falls within a certain period after the failure at tn-1, i.e. tn ∈ (tn-1, tn-1 + T]. A practical T is set to a half year in our test. The prediction score for each pipe is calculated by the failure rate integral within the period: ∫ tn-1+T tn-1 λ(t)dt where the parameters are learned using the training samples. Based on this protocol, we train and test the Hawkes models for fresh and salt systems respectively. The ROC are presented in Table 4. And the iterative model parameter convergence and the fitting examples are plot in Fig.5. Note the linear aging model is compared as a baseline where the failure rate is modeled as λ = Constant × age.

1 In fact, as shown in the EM training algorithm derivation for the time-stationary Hawkes Process model, the model does not sensitively rely on the observation window T . Thus a rough estimation of T is enough. And for those pipes of which the completion date is unknown, the model is also workable as long as the failure records are complete and accurate, while this is often the case because the pipe failure will receive immediate processing and recording.

4.3 Discussion

Some observations are made as listed in the following:

Risk matrix method is prone to focuses on the most predominant aspects and deteriorate largely on a subtle classification boundary: As observed from Fig.3, all data-driven methods are consistently superior than the empiric-driven risk matrix approach for any given prediction year. And Fig.4 gives a more subtle example: by excluding the samples with material type 'GI' or 'GIL' 2 , the performances deteriorates severely with respect to both salt and fresh systems. This is reasonable considering these two types are relatively vulnerable than other types. Once such samples are excluded, the risk matrix method become weaker because the classifying boundary is probably a nonlinear combination of attributes.

2 GI: Galvanized Iron; GIL: Lined Galvanized Iron

Our results are in line with [Cox, 2008] discussing about limitations of the risk matrix approach.

Binary classifiers, which do not consider the labels in the training set are from censored observation, achieve comparable performance on the censored data: [Yu and Baracos, 2011] point out that the binary classifier cannot fully capture the characters of the censored data. While in our testing, we found both the classical Cox model and the state-of-theart MTLR show no significant superiority against the binary classifiers. In our analysis, this may be due to on one hand, the implicit nonlinear feature transformation as performed by ANN, Chaid can boost the performance; on the other hand, the labeling noise or unobserved labels brought by the censored observation can be addressed by the classifiers to some extent. Considering [Yu and Baracos, 2011]'s heavier training overload, in our application, the Chaid tree and Logistic Regression are recommended for their interpretability and efficiency especially when the training data grows fast and more attributes arrive incurring the high-dimensionality issue.

Formulating the failure event sequence into a self-exciting stochastic process model is beneficial against a simple linearly aging baseline or random guess: We also observe that the self-exciting Hawkes Process model achieves an acceptable result, and the temporal cluster grouping is visually demonstrated in our plot. Perhaps more importantly, our method gives a rigorous description about the particular temporal patterns of pipe failures, and we believe this methodology will also apply to many other asset management scenarios.

5 Conclusion and future work

An already-deployed pipe failure prediction system was detailed. We show that binary classifiers are comparable to the 'censored' survival analysis models and the imbalanced dataset is not a big issue from our empirical study. Moreover, we propose another way of looking at the pipe failures by formulating it as a self-exciting stochastic process, where the attributes are not a must as in other models.

This work opens up a new space for the machine learning community to address the pipe failure prediction problem and asset management applications, which is different from conventional learning paradigms and worth future studies: 1) Spatial-temporal modeling is appealing since the pipe failures exhibit somewhat spatial grouping as pointed by [Goulter and Kazem, 1998]; 2) this paper tackles the different types of failure indiscriminately since the failure type information is currently unavailable, while taking the type into account will lead to a multivariate point Hawkes process worth further investigation; 3) the possible underlying failure correlation among the nearby pipes can also be modeled by a multidimensional Hawkes process; 4) it is challenging but interesting to explore if one can repopulate the missing-attributes from the temporal patterns of failures, one relevant work is [Stomakhin et al., 2011]. It is also appealing to study if the graph matching method [Tian et al., 2012] can be applied to model the topological pattern of pipe networks, which is assumed to have the connection with pipe failures.