非线性混合动力系统的分区聚类方法分析

Ankit K. Shah1, Dipak M. adhyar2

助理教授，仪器与控制系，SardarVallabhbhai Patel理工学院(SVIT)， Vasad, Gujarat, India
印度古吉拉特邦艾哈迈达巴德Nirma大学仪表与控制系科长2

摘要

非线性混合动力系统(NHDS)是连续域和离散域相互作用的动力学特征。据报道，该系统在化工系统、制造系统、机械系统、电气系统、电信系统、汽车控制和计算机磁盘驱动器控制等方面均有应用。由于一些未知离散事件的发生，非线性连续动力学将发生变化。因此，对于NHDS的识别，需要根据离散事件对开环数据进行分类。聚类是将对象组织成成员在某些方面相似的组的过程。近年来出现了多种满足这些要求的算法，并成功地应用于现实生活中的数据挖掘问题。模糊cmeans (FCM)和k-means是目前常用的基于无监督学习方法的划分算法。本文重点分析了FCM和k-means分区聚类方法在单罐NHDS数据分类中的应用。

关键字

非线性混合动力系统;聚类;模糊c均值;k - means。

介绍

经典控制理论利用动态系统模型，其状态演化由光滑的线性或非线性微分方程描述。然而，我们周围的许多动力系统也依赖于离散事件的发生，以及连续动力状态的演化。以连续时间非线性动力学和离散事件动力学相互作用为特征的系统称为非线性混合动力系统(NHDS)。当连续元素和离散元素在一个过程中一起工作，并且这些元素之间有相当大的关系时，有必要对动态元素进行建模。这就是为什么近年来许多研究人员将注意力集中在混合动力系统的建模和控制上[2,3]。

这种混合动力系统已在化工系统、制造系统、机械系统、电信系统、汽车控制和计算机磁盘驱动器控制等领域得到了广泛的应用。因此，混合动力系统出现在大量的应用领域，但这种混合动力系统的控制往往基于植物运行产生的启发式。文献[1-3]中提出了几种通过对连续变量和离散变量进行形式化积分来对混合系统建模的策略。对于这种组合动力系统的模型辨识，需要将数据按离散事件进行分类。在[5-10]中，混合动力系统使用了不同的基于聚类的数据分类算法。聚类是将数据组织成成员在某些方面相似的组的过程。聚类数据可以是图像、购物项目、模式、观察结果、特征向量、单词、文档、购物项目等形式。目标是以这样一种方式划分数据集:属于同一集群的对象尽可能相似，而属于不同集群的对象尽可能不相似。聚类是数据挖掘的一个重要组成部分，数据挖掘是一个探索和分析大量数据以获得有用信息的过程。聚类是将模式按组[12]进行无监督分类。在无监督分类问题中，没有预先定义的类别，但数据对象或个体应该形成若干组，以便组内一对对象之间的距离相对较小，而不同组之间的距离相对较大。 Only some mathematical criteria can decide on the composition of clusters when classifying data-sets automatically. Therefore clustering methods are endowed with distance functions that measure the dissimilarity of presented example cases, which is equivalent to measuring their similarity. As a result one yields a partition of the data-set into clusters regarding the chosen dissimilarity relation. Clustering approach can used for the data mining, text mining, information retrieval, web analysis, marketing, medical diagnostics, computational biology and many other applications. A variety of algorithms have recently emerged that meet these requirements and were successfully applied to real-life data mining problem [13]. In general clustering algorithms can be classified in to two categories: Hierarchical algorithms and Partitional algorithms.Hierarchical clustering algorithms produce a nested series of partitions based on a criterion for merging or splitting clusters based on similarity. Partitional clustering algorithms identify the partition that optimizes (usually locally) a clustering criterion [11]. Partitional methods have advantages in applications involving large data sets for which the construction of a dendrogram is computationally prohibitive. A problem accompanying the use of a partitional algorithm is the choice of the number of desired output clusters must be specified. The partitional techniques usually produce clusters by optimizing a criterion function defined either locally or globally. Partitional clustering algorithm mainly classified in to two kinds: k-means and fuzzy c-means algorithms.

k-means聚类方法是一种清晰的划分方法，将每个给定的对象严格划分为某一组[14,15]。k-均值聚类方法是处理大型数据集的有效方法。为对象定义的边界非常清晰，因此被分类在一个且仅一个集群中。在[16,17]中也提出了各种改进的基于k-means聚类的算法。模糊逻辑是模糊集的逻辑;一个模糊集在1到0之间有一个无限范围的真值。模糊逻辑中的命题具有一定程度的真值，模糊集中的隶属度可以是完全包容、完全排他或介于两者之间。模糊集不同于清晰集，它允许元素的隶属度为[18]。模糊集的核心是隶属度函数。它是一个函数，它定义了集域中的值与其在模糊集中的隶属度之间的关系。 Fuzzy C-Means (FCM) algorithm of clustering allows one piece of data to belong to two or more clusters. This method developed by [19] and further improved by [20, 21], is frequently used in pattern recognition [20, 22].

由于NHDS数据集既包含数值值又包含类别值，且具有连续动态特性，因此我们对混合系统数据集的有效划分算法很感兴趣。本文的目的是分析k-means和FCM分区聚类算法对离散事件混合动力系统数据分类的效率。本文的结构如下。第2节介绍了用于无监督数据分类的k均值硬聚类算法。第3节介绍了用于无监督数据分类的模糊c均值聚类算法。在第4节中，使用k-means和模糊c-means算法对随机数据集进行数据分类的示例。第五节介绍了k-means和模糊cmeans算法在单罐NHDS分类中的应用。最后，第6节总结了用于混合系统数据分类的分区聚类方法的分析，并给出了这种分析的未来范围。

k -均值聚类算法

k-means聚类算法称为硬分区算法，它近似于最大似然解，用于确定成分密度混合密度的均值位置。要聚类的对象用k表示，k是聚类的数量。缩写符号C = (c1，…，ck)用于表示簇中心的完整集合。给定p维欧几里得空间中的n个观测值，k-均值聚类的目的是将n个观测值划分为k个集合(k < n)，以最小化聚类内平方和(WCSS)。k-means聚类的目标函数可以定义为[16,17]:

(1）

式中，ci为第i个聚类中点的均值。第一步选取k个点作为聚类中心(均值)的初始值为(，…，) 1 1 c c和终止条件。然后将所有数据点分配到它们最近的聚类中心ci，基于每个点到每个聚类中心的欧氏距离，表示为:

（2）

对于所有的i, k。现在，每个聚类中心均值被重新计算为该聚类中点的平均值:

（3）

重复(2)和(3)，直到聚类中心的平均值不变

该算法的主要优点是它的简单性和速度，这使得它可以在大型数据集上运行。它的缺点是每次运行都不会产生相同的结果，因为生成的聚类依赖于初始随机分配，因此表示局部最小值。它最小化了簇内方差，但不能确保结果具有全局最小方差。另一个缺点是它们的性能可能会受到异常值的影响。每个聚类的离散性使得k-means在分析和算法上难以处理。硬分区的最大缺点是，它要么在分区中包含一个数据点，要么严格地将它排除在外;数据元素不可能同时属于多个分区。然而，在自然聚类中，总是有一些数据元素部分属于一个集合，部分属于一个或多个其他集合。为了克服这一局限性，引入了模糊分区的概念，并将在下一节讨论。

模糊c均值(fcm)聚类算法

模糊逻辑是模糊集的逻辑;一个模糊集在1到0之间有一个无限范围的真值。模糊逻辑中的命题具有一定程度的真值，模糊集中的隶属度可以是完全包容、完全排他或介于[18]之间。模糊集不同于清晰集，因为它允许元素具有一定程度的隶属度。模糊集的核心是隶属度函数。它是一个函数，它定义了集域中的值与其在模糊集中的隶属度之间的关系。模糊c均值(FCM)聚类算法允许一条数据属于两个或多个聚类。要聚类的对象用k表示，其中k是聚类的数量。缩写符号C = c1，…，ck表示簇中心的完整集合。在一维欧几里得空间中给定一组n个观测值，FCM聚类的目的是将观测值划分为k个集合(k

（4）

式中，n为数据项数，k为2 k < n的聚类数，xj为p维第j个测度数据，;ij为xj在第i个聚类中的隶属度，m&为权重指数，决定了得到的聚类的模糊程度，。表示任何测量数据与中心之间相似度的范数。对于m = 2，这等价于线性归一化隶属度使它们的和为1。当m的值接近1时，离该点最近的聚类中心的权重要比其他聚类中心大得多，算法类似于k-means。隶属度矩阵U = [ij]及其元素必须满足以下约束条件:

FCM算法的第一步是选择k、m的值和终止准则。下一步选择k个点作为聚类中心(均值)的初始值，如()。现在，通过最小化式(4)给出的目标函数求隶属度矩阵U，得到解为

现在通过最小化(4)求聚类中心C的向量，得到的解为:

｀

重复(5)和(6)，直到满足终止条件。位于聚类中心的数据点的隶属度值最大，当数据点远离聚类中心时，隶属度逐渐降低。与k-means一样，该算法也最小化了簇内方差，但也存在与k-means相同的问题，最小值是局部最小值，结果取决于簇中心的初始选择。与k-means算法相比，该算法具有更好的收敛性能。FCM需要存储U和所有ci，而U和ci的交替估计对大规模数据集[23]造成了计算和存储负担。

随机数据集的分类

对于上述分区聚类算法的第一个分析，请考虑[24]中给出的示例。每200个样本分别生成4个正态分布随机数据集，中心分别为(0.125,0.25)、(0.625,0.25)、(0.375,0.75)和(0.875,0.75)。现在，将上述数据集混合在一起，生成800个样本的完整数据集xj = [XjYj]，如图1所示。采用k-means和FCM聚类算法，假设有四个聚类中心，对数据集xj进行聚类。

图2(a)和图2(b)分别为使用k-means和FCM算法得到的结果。聚类中心显示为、、*和O符号。采用模糊参数m = 2，终止准则= 0.00001的FCM算法。利用Matlab软件将上述两种聚类算法应用于随机数据，并推导出每个聚类中心的位置。最后的聚类中心位置为每个聚类使用的聚类算法如表1所示。

单罐NHDS的分类

为了识别NHDS，需要根据开环数据点的离散事件对其进行分类。在确定NHDS之前，使用聚类进行数据分类需要对给定的聚类数据选择合适的方法。文中[9,25]将这两种分区聚类算法应用于单罐NHDS，并对所得结果进行了分析。单槽NHDS的示意图如图3所示。给定系统由于涉及到罐内水位变化高度超过0.3 cm的离散事件，具有混合特性。

式(7)和式(8)给出的单油箱非线性混合系统的质量平衡和伯努利定律:

式中，A=0.0154 m2为罐体截面，K = 2 10-4 m2为出口孔截面，u为输入流量，g = 9.81 m/sec2为重力常数，h为罐体液位。给定的混合单罐系统由于液位高于0.3时罐体截面发生变化，被划分为两个区域。对于采样时间为1秒的1000个样本，使用值在0到0.001之间的随机输入uj生成一组数据集xj = [hj uj-1]。随机有界3%的误差已添加到测量水平hj。开环模拟输入输出混合单油箱响应如图4所示。在假设系统有两个聚类中心的情况下，将FCM和k-means算法应用于数据集xj。聚类中心显示为和O符号。采用模糊参数m = 2，终止准则=0.00001的模糊聚类算法。采用kmeans算法，终止准则为0.00001。图5(a)和图5(b)是使用混合单罐系统开环数据集的k-means和FCM聚类算法的划分结果。在表2中，给出了h 0.3和h > 0.3的分类结果，并给出了实际数据点数以及FCM和k-means算法划分的数据点数。

结论

在本节中，基于上述两个例子对k-means和FCM划分算法进行了分析。表1显示，与k-means相比，使用FCM定位聚类中心的平均估计误差较小。表2给出了给定混合系统数据点对类型1和类型2区域的分类和误分类误差的信息。k-均值聚类方法易于实现。k-means聚类的最大缺点是它要么在分区中包含一个数据点，要么严格地将它排除在外;数据不可能同时属于多个分区。然而，在自然聚类中，总是有一些数据元素部分属于一个集合，部分属于一个或多个其他集合。FCM使用隶属度函数允许数据点指向多个集合的一部分。除了将数据点分配给共享中的集群外，成员度还可以表示数据点属于集群的模糊程度或明确程度。与k-means方法相比，该方法对聚类中心初始化不敏感，在实际应用中不容易陷入目标函数的局部最小值。 Given analysis useful forthe classification of open loop data for the NHDS, which is useful for identification and control of hybrid systems.

表格一览


表1	表2

数字一览


图1	图2	图3	图4	图5

参考文献

A. van der Schaft, H. Schumacher，“混合动力系统导论”，Springer-Verlag，伦敦，2000。

V.S. Branicky, S.K.M. Borkar，“混合控制的统一框架:模型和最优控制理论”，IEEE翻译。自动控制，Vol.43, pp. 461-474, 1998。

A. Bemporad, M.Morari，“集成逻辑的系统控制。动力学与约束”，《自动化》，Vol. 35, pp. 407-427, 1999。

M. Hirata, Y. Hashimoto, S. Noguchi, S. Adachi，“机械系统的混合建模方法。《机电一体化》，Vol. 20, pp. 59-66, 2010。

G. Ferrari-Trecate, M. Muselli, D. Liberati, M. Morari，“分段仿射系统识别的聚类技术”，自动化，Vol. 39, pp. 205-217, 2003

A. Bemporad, A. Garulli, S. Paoletti, A. Vicino，“分段仿射系统辨识的有界误差方法”，IEEE自动控制学报，第50卷，第1567-1580页，2005。

中田恒，高木坤，田文雄。Katayama，“基于统计聚类技术的分段仿射系统辨识”，自动化，Vol. 41, pp. 905-913, 2005。

M. Tabatabaei-Pour, M. Gholami, K. Salahshoor, H. R. Shaker，“分段仿射混合系统的递归辨识”，第九届控制、自动化、机器人与视觉国际会议论文集，第1-6页，2006。

M.E. Gegundes, J. Aroba和J. m . Bravo，“分段仿射系统的模糊聚类和竞争学习的方法”，英。应用。人工易达利。，Vol. 21, pp. 1321-1329, 2008.

S. Ghosh, S. Maka，“一类非线性系统分段仿射逼近的模糊聚类技术”，公共非线性科学数值模拟，第15卷，第2235-2244页，2010。

A.K. Jain, M.N. Murty, P.J. Flynn，“数据聚类:综述”，ACM计算。调查，Vol. 31, pp. 264-323, 1999。

徐瑞和D. Wunsch，“聚类算法综述”，IEEE学报。神经网络，Vol. 16 (3)， pp. 645-678, 2005。

Berkhin，“聚类数据挖掘技术综述”，技术报告，Accrue软件，CA, 2002。

S.Z. Selim, M.A. Ismail，“K-means类型算法:一个广义收敛定理和局部最优性的表征”，IEEE Trans。模式肛门。马赫。《情报》第6卷，第81-87页，1984年。

T. Kanungo, D. M. Mount, N. S. Netanyahu, C. D. Piatko, R. Silverman和A. Y. Wu，“一种有效的K-means聚类算法:分析与实现”，IEEE Trans。模式分析与机器智能，Vol. 24(7)， pp. 881-892, 2000

G. Patane和M. Russo，“全自动集群系统”，IEEE Trans。神经网络，第13卷(6)，页。1285 - 1298年,2002年。

M. C. Su和C. H. Chou，“基于簇对称的K-means距离算法的改进版本”，IEEE Trans。模式分析与机器智能，Vol. 23(6)， pp. 674- 680,2001

张善荣，c - t。Sun和E. Mizutani，“神经模糊和软计算:学习和机器智能的计算方法”，Prentice Hall, 1996。
J. C. Bezdek，“模糊集的聚类有效性”，控制学报，Vol. 3(3)， pp. 58-73, 1973。

J. C. Dunn，“一种新的模糊划分算法及其在模式分类问题中的应用”，控制论杂志，第4卷(2)，第1-15页，1974。

J. C. Bezdek, N. R. Pal，“集群有效性的一些新研究，IEEE对系统人与控制论的转换”，Vol. 28(3)， pp. 301-315,1998。

葛华，“无监督最优模糊聚类”，IEEE学报。型。分析的马赫。Int。，Vol. 2, pp. 773-781, 1989.

K.-L。杜，“聚类:一种神经网络方法”，神经网络，Vol. 23, pp. 89-107, 2010。

熊凯，“一种基于模糊聚类的无监督图像数据库组织算法”，计算机工程学报。《社会》第3卷，第3909-3912页，2000年。

A. K. Shah, D. M. Adhyaru，“非线性混合动力系统PWARX模型的模糊选择”，第3届国际会议论文集，第1-6页，2013。