Elsevier

Automatica

Volume 41, Issue 5, May 2005, Pages 905-913
Automatica

Brief paper
Identification of piecewise affine systems based on statistical clustering technique

https://doi.org/10.1016/j.automatica.2004.12.005Get rights and content

Abstract

This paper is concerned with the identification of a class of piecewise affine systems called a piecewise affine autoregressive exogenous (PWARX) model. The PWARX model is composed of ARX sub-models each of which corresponds to a polyhedral region of the regression space. Under the temporary assumption that the number of sub-models is known a priori, the input–output data are collected into several clusters by using a statistical clustering algorithm. We utilize support vector classifiers to estimate the boundary hyperplane between two adjacent regions in the regression space. In each cluster, the parameter vector of the sub-model is obtained by the least squares method. It turns out that the present statistical clustering approach enables us to estimate the number of sub-models based on the information criteria such as CAIC and MDL. The estimate of the number of sub-models is performed by applying the identification procedure several times to the same data set, after having fixed the number of sub-models to different values. Finally, we verify the applicability of the present identification method through a numerical example of a Hammerstein model.

Introduction

Hybrid systems are composed of both continuous dynamics governed by physical laws and discrete-event dynamics driven by logic and rules. Recently, much attention has been paid to hybrid systems from various viewpoints (van der Schaft & Schumacher, 2000).

This paper deals with a system representation of hybrid systems called a piecewise affine (PWA) system. A number of research works on PWA systems (Imura & van der Schaft, 2000, Johansson, 2003, Johansson & Rantzer, 1998, Nakada & Takaba, 2003) have been reported. Recently, it has been proved by Bemporad, Ferrari-Trecate, and Morari (2000) and by Heemels, De Schutter, and Bemporad (2001) that the PWA system is equivalent to the other hybrid system models such as mixed logical dynamical systems, linear complementarity systems, extended linear complementarity systems and max–min-plus-scaling systems.

The identification of PWA systems is quite important, because there are many linear systems with PWA nonlinearities such as saturation or relay elements, and a general nonlinear system can be treated as a PWA system by approximating a nonlinear function by a PWA one with arbitrary accuracy. There are some applications to the identification of real systems, e.g. a nonlinear electrical circuit (Ferrari-Trecate, Muselli, Liberati, & Morari, 2003), a fermentation process (Fantuzzi, Simani, Beghelli, & Rovatti, 2002) and a pick-and-place machine (Juloski, Heemels, & Ferrari-Trecate, 2004).

In the identification of PWA systems, a piecewise affine autoregressive exogenous (PWARX) model (Amaldi and Mattavelli, 2002, Bemporad et al., 2003, Ferrari-Trecate et al., 2003, Ragot et al., 2003, Roll et al., 2004, Vidal et al., 2003) is used as a typical model of PWA systems. The identification based on the PWARX model includes the estimation of both polyhedral partition on the regression space and the parameter of the ARX sub-model corresponding to each polyhedral region. In the case where the partition of the regression space is known a priori, the parameters of ARX sub-models can be estimated almost straightforwardly by the least squares method. However, the necessity of estimating the partition of the regression space as well as system parameters in the identification of PWA systems makes the development of identification methods extremely difficult. Jordan and Jacobs (1994) proposed an EM algorithm for hierarchical models that could be exploited for identifying PWARX models. Amaldi and Mattavelli (2002) considered a combinatorial optimization problem called the MIN PFS problem to estimate a piecewise linear model, which was approximately solved by a greedy method. Their result was applied by Bemporad et al. (2003) to the identification of the PWARX models with estimation of the number of sub-models. Ferrari-Trecate et al. (2003) developed an identification method by clustering parameter vectors, each of which is locally estimated from several data neighboring to each data. The optimality of the data classification utilized in this method was shown by Ferrari-Trecate and Schinkel (2003). Recently, Ragot et al. (2003) have proposed a method for identifying the parameter of sub-models when choosing an adapted weighting function, which allows one to select the data for which each sub-model is active. Vidal et al. (2003) have taken an algebraic geometric approach, in which the problem of estimating both the parameters and the number of sub-models is casted as a polynomial factorization problem. Moreover, Roll et al. (2004) have reduced the identification problem of a special class of PWARX models to a mixed-integer programming problem.

In this paper, we present a new method for the identification of a PWARX model based on a statistical clustering of measured data via a Gaussian mixture model and support vector classifiers (SVCs). A major advantage of the statistical clustering technique is that the statistical information such as the log-likelihood function enables us to estimate the number of sub-models of a PWARX model. We show how to estimate the number of sub-models based on the statistical information criteria such as the consistent Akaike's information criterion (CAIC) (Bozdogan, 1987), and the minimum description length (MDL) criterion (Rissanen, 1978), after discussing the case where the number of sub-models is available in the identification procedure. We also verify the applicability of the present identification method to a Hammerstein model, which is a popular model of nonlinear systems and composed of a linear system with a static nonlinearity. If the nonlinearity is a PWA function, the present method can be easily applied to Hammerstein models.

The organization of this paper is as follows. In Section 2, we formulate the identification problem of a PWARX model. The measured data are classified into clusters based on a Gaussian mixture model in Section 3. Sections 4 and 5 are, respectively, devoted to estimating boundary hyperplanes between two adjacent polyhedral regions on the regression space and the parameters of local sub-models. In Section 6, the two criteria CAIC and MDL are introduced to estimate the number of sub-models. We apply the present identification method to a Hammerstein model in Section 7. Finally, we conclude this paper in Section 8.

Section snippets

Piecewise affine autoregressive exogenous (PWARX) model

In this paper, we consider the identification problem of a PWA system. We introduce a useful model called a PWARX model (Bemporad et al., 2003, Ferrari-Trecate et al., 2003, Roll et al., 2004) for the identification of a PWA system.

A PWARX model is given byyk=θ1Txk1+ek,ifxkX1,θsTxk1+ek,ifxkXs,k=1,2,,N.The vectors ukRm, ykRp and ekRp are the input, the output and the noise at time k, respectively. The regression vector xkRn is denoted by xk=[yk-1Tyk-2Tyk-nyTuk-1Tuk-2Tuk-nuT]T,where n=pn

Clustering of the measured data

We wish to classify the data zk,k=1,2,,N in Rn+p into s clusters. For this purpose, we classify the set of the time indices {1,2,,N} into s non-empty disjoint clusters Ci,i=1,2,,s. In this section, we employ a statistical clustering method based on a Gaussian mixture model (Alpaydın, 1998, Dempster et al., 1977, Jordan and Jacobs, 1994, Mitra et al., 2003, Miyamoto, 1999, Redner and Walker, 1984).

We assume that the probability density of the data zk is given by a Gaussian mixture model p(z;Φ)

Estimation of the boundary hyperplanes on the regression space

We describe a method for classifying two adjacent clusters in the regression space Rn with a hyperplane based on SVCs (Vapnik, 1998, Boyd and Vandenberghe, 2003). The simplest version of SVC is used by Bemporad et al. (2003), while the similar technique is also utilized by Ferrari-Trecate et al. (2003).

Before estimating the partition of the regression space, we need to check the adjacency of the clusters. We employ the so-called Delaunay graph (Edelsbrunner, 1987) for this purpose. This graph

Parameter estimation of each sub-model

Based on the data classified in the previous section, we estimate the parameter θi,i=1,2,,s by the LS method (Söderström and Stoica, 1989, Ljung, 1999). For each i=1,2,,s, the parameter can be estimated by the formulaθ^i=(XiTXi)-1XiTYi,Xi=[x¯ki1x¯ki2x¯kiNi]T,x¯kil=xkil1,l=1,2,,Ni,Yi=[yki1yki2ykiNi]T,Ci={ki1,ki2,,kiNi}.Here, the quantity Ni denotes the cardinality of Ci which is assumed to satisfy Nin+1 so that we can estimate θi. Obviously, i=1sNi=N holds.

We compute the parameter

Estimation of the number of sub-models

In this section, we discuss how to estimate the number of sub-models. Since the number of clusters is equal to that of sub-models, we show how to estimate the number of clusters based on the information criteria associated with the maximum-likelihood estimation in Section 3 (Hu and Xu, 2003, Jain et al., 2000).

Firstly, we fix two positive integers smin and smax so that the true number of sub-models s is assumed to be in the interval [smin,smax]. Next, for all s=smin,,smax, we compute the

Application to Hammerstein model

A Hammerstein model in Fig. 7 is a popular model used in the nonlinear system identification, which is composed of a linear time-invariant (LTI) system and a static nonlinearity. If the static nonlinearity is a static PWA function, we can easily apply the present identification method to the Hammerstein model as shown below.

Example 2

We consider an SISO Hammerstein model. The plant P is an LTI system given by yk=-a1yk-1-a2yk-2+b1vk-1+ek,where a1, a2 and b1 are scalar constants, and σ is a saturation

Conclusion

In this paper, we have developed a new identification method of PWARX models. More specifically, our method consists of the following three techniques: the statistical clustering based on a Gaussian mixture model with the EM algorithm, the estimation of the regression space partition via soft margin support vector classifiers, and the least squares estimation of the parameter of the ARX sub-models. The advantage of the present identification method is that the information criteria such as CAIC

Acknowledgements

The authors would like to thank Dr. Hideyuki Tanaka, Kyoto University, and the anonymous referees for their helpful advice on this work.

Hayato Nakada received B.Eng. degree in informatics and mathematical science and M.Inf. (Master of Informatics) degree in applied mathematics and physics from Kyoto University, Japan in 2000 and 2002, respectively. He is currently a doctoral student at the Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University. His current research interests include analysis, control and identification of hybrid systems and saturating systems.

References (33)

  • S. Boyd et al.

    Convex optimization

    (2003)
  • H. Bozdogan

    Model selection and akaike's information criterion (AIC)the general theory and its analytical extensions

    Psychometrika

    (1987)
  • E.J. Bredensteiner et al.

    Multicategory classification by support vector machines

    Computational Optimization and Applications

    (1999)
  • A.P. Dempster et al.

    Maximum likelihood from incomplete data via the EM algorithm

    Journal of the Royal Statistical Society B

    (1977)
  • H. Edelsbrunner

    Algorithms in combinatorial geometry

    (1987)
  • C. Fantuzzi et al.

    Identification of piecewise affine models in noisy environment

    International Journal of Control

    (2002)
  • Cited by (0)

    Hayato Nakada received B.Eng. degree in informatics and mathematical science and M.Inf. (Master of Informatics) degree in applied mathematics and physics from Kyoto University, Japan in 2000 and 2002, respectively. He is currently a doctoral student at the Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University. His current research interests include analysis, control and identification of hybrid systems and saturating systems.

    Kiyotsugu Takaba received B.Eng. degree in applied mathematics and physics, M.Eng. degree in applied systems science and Dr.Eng. degree in applied mathematics and physics all from Kyoto University in 1989, 1991 and 1996, respectively. Since 1991, he has been with the Department of Applied Mathematics and Physics in Kyoto University, where he is presently an Associate Professor. His research interest includes robust and optimal control for multi-variable dynamical systems. He is a member of IEEE, ISCIE and SICE.

    Tohru Katayama received B.E., M.E. and Ph.D. degrees all in applied mathematics and physics from Kyoto University, Kyoto, in 1964, 1966 and 1969, respectively. Since 1986, he has been in the Department of Applied Mathematics and Physics, Kyoto University. He had visiting positions at UCLA from 1974 to 1975, and at University of Padova in 1997. He was an Associate Editor of IEEE Transactions on Automatic Control from 1996 to 1998, and is now a Subject Editor of International Journal of Robust and Nonlinear Control, and the Chair of IFAC Technical Committee of Stochastic Systems for 1999–2002, and the Chair of IFAC Coordinating Committee of Signals and Systems for 2002–2005. His research interests include estimation theory, stochastic realization, subspace method of identification, blind identification, and control of industrial processes.

    This paper was presented at IFAC Workshop on Adaptation and Learning in Control and Signal Processing (ALCOSP 04) and IFAC Workshop on Periodic Control Systems (PSYCO 04), Yokohama, Japan, August, 2004. This paper was recommended for publication in revised form by Associate Editor Antonio Vicino under the direction of Editor T. Söderström.

    View full text