动态K-均值聚类算法

动态K-均值聚类算法（共7篇）

动态K-均值聚类算法 篇1

引言

径向基函数神经网络 (RBFNN) 以其简单的网络结构、快速的学习方法、较好的推广能力, 已经广泛地应用于许多领域, 特别是模式识别和函数逼近等领域。然而, 如何有效地确定RBF神经网络的网络结构和参数, 至今没有系统的规律可循。在RBF神经网络中需要确定的参数包括隐含层节点数、隐含层基函数的中心值和宽度、隐含层到输出层的连接权值。目前, 隐含层节点数主要依靠经验来选取。而根据moody准则, 神经网络的设计应该在满足精度要求的情况下有最小的结构, 以保证网络的泛化能力[1]。

由于隐含层基函数中心值的选取对网络的函数逼近能力有很大的影响, 目前最常用的确定隐含层中心值的方法是K-均值聚类法。由于K-均值聚类法的聚类过程一般能够根据输入向量比较准确地确定聚类数和相应的聚类中心, 因此, 如果在已知全部输入向量时使用该方法能够比较精确地确定网络结构。但是, 它要求实现确定全部输入向量和指定聚类中心的数目, 这在实际应用中很难办到。而动态K-均值聚类方法能够根据输入来实时地确定网络的中心。因此, 本文提出动态均值聚类方法, 对一般的K-均值方法进行改进。

一、BRF神经网络的结构原理

RBF神经网络最基本的结构形式是一种三层前向网络。网络的基本构成包括输入层、隐含层和输出层, 各层的节点数目分别为P, M, L, 每一层都有着完全不同的作用。其结构如图1所示。

第一层是输入层, 由一些信号源节点 (感知单元) 组成, 它们将网络与外界环境连接起来。第二层是隐含层, 由若干个隐节点构成。隐含层只有一个隐含层单元, 采用径向基函数作为其输出特性。第三层是输出层, 由若干个线性求和单元的输出节点组成, 它对输入模式的作用产生响应。输入层节点传递输入信号到隐含层。从输入空间到隐含层空间的变换是非线性的, 而从隐含层空间到输出层空间的变换是线性的。网络输出节点计算隐节点给出基函数的线性组合。输入层到隐含层之间的权值固定为1, 只有隐含层到输出层之间的权值Wkj (k=1, 2, …, L;j=1, 2, …, M) 可调。

在图1中, 输入层由P个信号源节点组成。设N为当前训练的样本总数, 对于训练集的每个样本即为输入矢量:X= (xl, x2, …, xp) , 其中xi (i=1, …, P) 为网络的第i个输入。隐含层由M个隐节点组成。每个隐含层节点的激活函数是一个径向基函数, 它是一种局部分布的中心点径向对称衰减的非负非线性函数。由于高斯基函数具备表示形式简单、径向对称、光滑性好、易于进行理论分析等优点, 所以文中隐含层变换函数采用高斯基函数, 其表达形式如下所示:

其中, X= (x1, x2, …, xp) T为网络输入矢量。Cj为隐含层第j个高斯单元的中心矢量, 与X具有相同维数的向量, Cj= (cj1, cj2, …, cjp) , (j=l, 2, …, M) 。ðj是第j个感知的变量 (可以自由选择的参数) , 它决定了该基函数围绕中心点的宽度。M是隐节点的个数。‖X-Cj‖是向量X-Cj的Euclid范数, 表示X和Cj之间的距离。Φj (X) 为隐含层第j个节点的输出, 即为第j个隐节点的活跃值。当前活跃值矢量为。由高斯公式可知, 从输入层到隐含层之间是一种函数变换, 隐含层节点的输出范围在0~1之间, 且输入样本愈靠近节点的中心, 输出值愈大, Φj (X) 在Cj处有一个唯一的最大值。随着‖X-Cj‖的增大, Φj (X) 迅速衰减到零。输出层由L个节点组成。设N为当前训练的样本总数, 对于每个样本即为网络的实际输出矢量为:yk= (y1, y2, …, yL) , k=l, …, L, 为网络的第k个输出。RBF神经网络的输出为隐含层节点输出的线性组合, 输出形式可表示为:

其中L是输出节点个数, Φj (X) 为高斯函数。wkj为第k (k=1, 2, …, L) 个输出节点与第j (j=l, 2, …, M) 个隐节点的连接权值。

二、BRF中心调整的动态K-均值聚类算法

2.1 动态K-均值的引入

RBF网络中心学习过程分两步:一是根据输入样本确定隐含层各节点的变换函数的中心Cj和半径ρj;二是采用误差校正学习算法, 调节输出层的权W。其目的就是把输入数据分配到一定数目的有意义的类别中去, 即根据欧氏空间中的距离来对输入向量进行聚类。本文采用自适应调整聚类中心的方法——动态均值聚类法。

该方法的基本思想是:首先已知据聚类中心的数目, 然后随着向量的输入, 计算输入向量与特定聚类中心的欧氏距离。如果距离小于门限值, 则将该聚类中心所对应的输入向量的平均值作为新的聚类中心;如果距离大于门限值, 则将刚输入的向量作为新的聚类中心。再接着输入向量, 直到确定所有的聚类中心。

2.2 动态K-均值聚类算法在RBF中的应用

动态K-均值聚类算法在RBF网络中心选取中的作用是调整聚类中心, 使网络中心的选取更精确。它的计算过程可以简要的描述如下:

首先, 令类别数为0 (第一个输入会强迫创建出一个类别模式以支持该输入) 。以后, 每遇到每一个新的输入向量, 则计算它与任何一个已分配的类别模式之间的距离。如果指定第P个输入向量为X (p) 以及第j个聚类中心为Cj, 则欧氏距离d可以表示为:

其中M是输入向量的维数。

设输入向量X (p) 和所有已分配的模式类别之间的距离已知, 且和该输入矢量最近的中心为Ck, 应有d0=‖X (p) -Ck‖<‖X (p) -Cj‖, j=1, …, T, j≠k其中T是已分配类别的数目。

在确定了与输入矢量最近的中心后, k就已经确定了, 从而d0也就确定了。先把它和距离门限值ρ进行比较, 会有如下两种情况:

(1) 当d0<ρ时, 输入矢量X (p) 在允许的误差范围内, 该输入矢量属于第k个类别。也就是说, 如果用Sk表示第K个中心所对应的全部输入矢量的集合, 则X (p) ∈Sk。这时可以引入k-均值聚类方法的思想, 通过求得所有成员矢量的平均值来进行中心更新。即:

其中NSk表示第K个聚类中心所对的输入矢量的个数。

(2) 当d0>ρ时, 输入矢量X (p) 不在允许的误差范围内, 从而不能分配到该类别中去。此时, 应该以X (p) 为中心, 分配一个新的聚类中心, 算法流程图如图2所示。

上面的过程用动态聚类的方法实时的找到了网络的中心, 在确定网络中心Cj之后, 可以令相应的半径ρj等于其与属于该类的训练样本之间的平均距离, 即:

最后可以根据误差梯度下降法调节权值W以完成RBF网络学习过程。

三、仿真试验及结果分析

本实验通过RBF神经网络函数逼近的方法来比较K-均值聚类和动态K-均值聚类方法的优劣。实验环境为PC机一台, 所用工具为MATLAB。

考虑非线性函数y=2sin (πx) +2cos (0.5πx) , x∈[0, 10], 用RBF神经网络进行函数逼近。

x以0.1为间隔在[0, 10]上均匀取值, 可得到100个样本作为训练样本。RBF神经网络的中心点个数取m=20, 基函数用高斯函数。对分别采用K-均值算法和动态K-均值算法确定RBF神经网络中心进行比较:采用K-均值聚类算法, 训练时样本的最小平均相对误差为0.1014327, 图3为K-均值聚类法RBF拟合曲线。采用动态K-均值聚类算法, 训练时样本的平均相对误差为0.0731432, 图4为动态K-均值聚类法RBF拟合曲线。可见采用动态K-均值聚类算法可以获得更好的效果。

四、结论

本文在k-均值聚类算法的基础上, 将动态均值聚类方法应用到RBF神经网络。该方法有效地解决了k-均值聚类的局限性, 提高了RBF的网络学习能力。通过仿真实验验证了该方法的实用性和精确度, 可供进一步的研究和实际应用。

参考文献

[1]阎平凡, 张长水.人工神经网络与模拟进化计算[M].北京:清华大学出版社, 2003.

[2]张海朝, 黄淼.基于RBF神经网络的B样条曲面重构[J], 微电子学与计算机, 2008, 7.

[3]兰天鸽, 方勇华.构造RBF神经网络及其参数优化[J], 计算机工程, 2008, 33 (5) .

[4]Roy A, Govil S, Miranda R.A Neural Network Learning Theory and aPolynomial Time RBF Algorithm[J].IEEE Trans.on Neural Network, 1997, 8 (6) :1301-1313.

[5]潘登, 郑应平.基于RBF神经网络的网格数据聚类方法[J].计算机应用, 2007, 26 (2) .

[6]任江涛, 孙婧昊.一种用于文本聚类的改进的K均值算法[J].计算机应用, 2006, 26 (6) .

[7]Mashor M Y.Hybrid training algorithm for RBF network[J].Interna-tional Journal of the Computer, the Internet and Management, 2000, 8 (2) :48-65.

[8]Bianchini M, Frascono P, Cori M.Learning without minima radialbasis function network[J].IEEE Trans on Neural Networks, 1995, 6 (3) :749-756.

[9]Pedrycz W.Conditional fuzzy clustering in the design of radial ba-sis function neural network[J].IEEE Trans on Neural Networks, 1998, 9 (4) :601-612.

[10]Gonzalez J, Pojas I, Pomares H.A new clustering technique for function approximation[J].IEEE Trans on Neural Networks, 2002, 13 (1) :132-142.

动态K-均值聚类算法 篇2

关键词：车牌识别,车牌定位,K-均值,聚类,字符识别

机动车号牌识别系统主要功能是通过图像采集和图像识别的手段识别机动车的身份。对车牌识别领域的研究最初起源于二十世纪九十年代的发达国家, 而国内的研究起源于二十世纪末。号牌识别的最主要的步骤是:车牌定位、字符分割和字符识别。而后两者现在基本已经达成共识, 字符分割采用对二值化图片进行垂直投影和水平投影, 字符识别使用模板匹配方法或者SVM方式。最重要而且方案最多样化的步骤还是在车牌定位上。

车牌定位基本可以分为三种大的研究方向:对灰度图像进行边缘检测、对灰度图像进行角点检测和对彩色图像进行颜色模型处理。边缘特征是人类视觉感知的重要来源, 文献将边缘检测理论、形态学填充、腐蚀开运算后得到车牌待选区域, 最后分析获取车牌位置, 边缘检测作为研究范围最广和目前大多数产品使用的技术, 的确具有速度快、准确率较高的特点, 尽管现有的边缘检测算子十分成熟, 但是没有一种适应于任何图像质量、任何图形环境的边缘提取方法, 而且为了得到高识别率, 对于每幅图像要选用合适的边缘检测算子。文献将彩色图像转换到HSV颜色空间中对色彩进行分层处理是车牌定位彩色图像处理方向较新颖的方法, 但是这类方法的缺点也是很明显的, 当车身颜色与牌照颜色相近时, 辨识就变的几乎不可能了。文献提出了角点检测法, 因为角点代表的特征像素点占图像像素总数的百分之一, 却构成物体大部分的外形要素, 由于牌照的字符部分角点数较多, 所以作者使用Harris算法获取整幅图像的所有角点, 然后使用一个固定大小的滑窗去遍历图中的角点以得到牌照待选区域。通过角点获取牌照区域受干扰小, 识别的效率也比较高, 是应该深入研究的方向。

1 车牌标准分析

现行的《中华人民共和国公共安全行业标准——中华人民共和国机动车号牌》 (GA36-2007) , 于2007年9月28日发布, 同年11月1日实施, 用来代替原来的国标GA36-1992。按照GA36-2007的标准, 为了我们计算机识别的方便, 我重新整理从号牌行数和号牌特征着手归纳, 见表1。

经过归类并简化后, 很大程度上避免了排列方式对识别算法的干扰, 在字符分割阶段对车牌进行横向投影分析号牌分类是单行牌照还是双行牌照, 并根据上表优化算法, 可以达到快速准确的目的, 见图1。

下面从典型的单行牌照, 分析其字符规律。牌照中的字符分为三段:第一个字符是省、自治区或者直辖市的简称, 确定为汉字字符;第二个字符是发牌机关代号, 是大写的英文字母;第三至第七个字符为序号, 通常为大写英文字符和阿拉伯数字字符的排列, 对于特别号段的车辆会在末位字符出现“警”“领”“学”“临”“试”“港”“澳”等汉字字符。

典型的双行牌照, 见图2。双行牌照第一行就是单行牌照分割点前的两个字符, 第二行是单行牌照的第三位到第七位。双行牌照和单行牌照相比, 长宽比更小。

从颜色方面看, 无论是单行的牌照还是双行的牌照, 都有多种颜色的排列组合。但是归纳来说, 牌照背景颜色和牌照字体颜色的组合一共是四种, 分别是:黄底黑字、蓝底白字、黑底白字、白底黑字。特殊分类的字符颜色为红色, 而且特殊字符不会出现在蓝底背景的牌照上面。

2 原始K-均值算法

用Harris角点检测算法运算后的图像, 通过观察可以发现“牌照区域肯定是角点聚集的区域, 但是角点聚集的区域不一定是牌照所在区域”, 需要使用一个聚类分析方法来找到若干个角点聚集区域, 然后通过对区域特征的筛选, 最终决定牌照位置。K-均值算法是一种得到了广泛使用的基于划分的聚类算法, 算法把n个数据点按照目标函数分为k个簇, 以使簇内数据点具有较高的相似度, 而这个目标函数可以是欧氏距离。K-均值算法满足了希望把n个角点以欧氏距离分为k个号牌待选区域的思想, 而且它的时间复杂度是O (tkn) , t是迭代次数, 所以对图3 (a) 上由Harris算法得到的角点执行K-均值算法, 经t次迭代得到k个簇, 见图3。

3 改进K-均值算法

使用原始K-均值算法并不能在每次收敛后都得到牌照正确的区域 (见图4) , 因为其算法本身是用于数据挖掘的, 算法中初始点是随机决定的, 目标函数使用的是欧氏距离, 为适应号牌识别的效率和识别率双重的要求, 需要对其修改。在这个过程中, 参考了文献, 但是考虑到文中AP算法的时间复杂度高, 所以还是用K-均值算法。

首先从算法的随机取初始点着手, 通过实验发现初始随机点选择的结果不同, 收敛后的簇是可能不一致的, 所以尽量要选择一种既能接近最终收敛簇的形心, 又能是一种快速稳定的初始点提取算法。研究后决定用分冶思想把图像分成若干个矩形区域, 算法1的步骤如下:

步骤2, 遍历Ci, 2这张存放了角点的二维表, , 1/ij=C×M W, k Ci, 2N/H=×, Aj, kAj, k1=+。

步骤3, 设值max, 遍历Aj, k, 当Aj-1, k, Aj+1, k, Aj, k-1, Aj, k+1均未被访问过时, max=Aj, k, 并标记Aj, k为已访问过。

步骤4, 循环到步骤3, 所有的初始点都选出为止。

第二点的改进是传统的K-均值聚类时使用的欧氏距离, 而牌照的规格不是圆, 需要使用标准化的欧氏距离公式。两个n维向量a (x11, x12, ..., x1n) 与

b (x21, x22, ..., x2n) 间的标准化欧氏距离公式为:

其中ks是分量的标准差, 对于最常见的440mm×140mm的机动车牌照上二维的角点数据, 公式可以推导为

于是整个号牌定位的算法可以这样描述:

步骤1, 使用FAST角点算法获取图中角点。

步骤2, 使用算法1提取K-均值的初始点。

步骤3, 以计算出的中心点执行K-均值算法。

步骤4, 修改K-均值算法使用公式1。

步骤5, 在聚类后获取的簇所组成的矩形中, 根据车牌标准, 删除以下情况:高要比宽大;宽大于高的3.5倍;宽小于高的2倍;号牌颜色面积小于总面积50%。

执行上述算法后得到图5, 其中左边一张是通过上述算法得到的初始点, 右图是通过初始点再调用K-均值算法得到最终的角点分类后各个区域的中心, 从中可以发现初始点已经很接近最终的收敛结果, 所以这种算法可以大大的加快K-均值算法迭代的速度, 而且使得K-均值算法的执行速度是快速的, 结果是稳定的。

4 算法效率实验

测试数据集的描述:本文采用从网上随机选取的二十七张车辆正面图片作为样本来验证改进后的算法的效率。通过FAST角点检测, 其中每张图产生一千个以下的角点。

算法对比:分别用传统K-均值算法、滑窗定位法和改进过的K-均值算法分别对样本图片的角点进行聚类, 分别从平均识别速度和平均识别率两个方面进行对比, 见表2。

表2是对三种不同聚类算法的实验结果的汇总, 给出了具体量化的数据, 通过表2可看出传统K-均值算法由于迭代次数多而收敛速度慢, 并且识别率低。而改进后的K-均值算法虽然算法复杂但是由于迭代过程的改进使得识别速度和平均识别率都得到了很好的平衡。

5 车牌字符分割算法研究

本章节将讨论车牌字符分割问题。车牌字符的分割是车辆号牌识别流程中承上启下的环节, 主要是继续前章车牌定位的工作结果, 主要任务是从一张车牌图像中准确可靠的分割得到各个字符并完成归一化的工作, 提供给下面字符识别环节来进行分析。

由于机动车牌照存在单行车牌和双行车牌, 所以进行列分割之前要首先进行判断。通过分析车牌区域的水平投影图的形态就可以知道, 见图7。

因为车牌尺寸不同, 必须对它进行归一操作:将牌照灰度图缩放到100×50像素, 计算各行中段约25%~75%的区域, 在这个区域中搜索灰度值最小点, 若该点在接近1/3处, 该号牌就是双行车牌, 否则是单行车牌。下面介绍用列分割方法把单行车牌进行字符分割。首先对车牌定位后的图像进行二值化操作 (临界灰度值是160) , 这样得到的二值化图像减少了光照不均的影响。然后对单行车牌区域的二值化图像做垂直投影, 见图8。

然后通过下列的步骤实现字符分割, 其中投影图为P。

步骤1:令max P=MAX (P) , 得到投影图中的最值。

步骤2:寻找N中的0值点, 以0值点将N分为若干块:recti, i=1, 2, 3, ...。

步骤4:各块宽度为width=imax (recti) -min (recti) 。宽度中值为media Width。将widthi<media Width×1.2的块就近合并。

步骤5:若recti的宽度大于两倍中值宽度, 按中点将其分拆成两块。

步骤6:重复步骤4和5, 直到无合并或拆分操作为止。

步骤7:如果块宽度小于各块平均宽度, 以该块中心左右往外media Width2作为分割点;否则以该块左右边界为分割点。

步骤8:按照分割点分割图像, 按照各分割块的左右次序对其编号。

步骤9:分析各块底色 (二值化图像为0的点) 的平均色度值, 将其和车牌区域底色比较, 删除误差超过50%的块。

这样就把字符从定位好的牌照图像中分离出来了, 见图9。

6 车牌字符分割识别研究

支持向量机来识别号牌字符, 利用其良好的分类能力, 可以用来对字符进行分类, 有很高的字符识别率。

1992年开始在统计学习理论领域发展了一种称为支持向量机 (Support Vector Machine, SVM) 的新的模式识别方法, 在解决小样本、非线性及高维模式识别的问题中表现出很好的性能。由于同时神经网络遇到了网络结构固定、过学习和欠学习问题, 所以支持向量机方法成了机器学习领域内新的热点。

SVM方法从线性可分的最优分类面 (Optimal Hyper-plane) 提出了二类分类技术。它通过构造最优超平面使得不同样本类的距离最大化。

yi[ (wixi) +b]-1≥0, i=1, 2, ..., n就得到了最优的分类面。表述成约束优化问题就是在 (l) d的条件下, 求方程

对w和b偏微分并使之等于0, 得到对偶问题

在线性不可分情况下, 增加了松弛项ξi≥0, 分类条件方程变成:

所谓SVM的训练, 就是通过已有的样本, 求得支撑最优分类面的样本向量。由于SVM自身的特点, 相对于识别的样本, 只需要少量样本进行训练。这一点就满足车牌字符识别系统的要求。同时, 如果把整个字符作为输入数据, 输入样本就具有高维度的特征, 这要求分类器能够进行高效的高维度数据分类能力, 这也是SVM的优势所在。鉴于以上这些原因, 构造了用于车牌字符识别的支持向量机, 并使用大量实际数据效验所设计方法的有效性。训练中从100多张尺寸为800×600的各类机动车照片中分割出700多张字符照片, 其中某种字符的照片数是大于1的, 按照字符分类, 每种字符抽取一张, 一共71张字符照片, 手动选定字符系统自动对其进行缩放操作, 统一成32×16像素的图片, 然后再进行灰度化操作和二值化操作 (通过实验二值化的阀值定为灰度值160) , 这样每个字符照片所包含的信息量是相同的。实验中使用的支持向量机是由台湾林智仁教授开发的libsvm, 由于Objective-C是向下支持C语言的, 所以libsvm (C语言版) 是可以直接用于Objective-C开发的, 见图10。使用svm_train来进行训练。

识别的步骤和训练的步骤是相似的。对于从字符分割后的字母/数字图片, 首先进行灰度化和二值化处理 (二值化的阀值定为灰度值160) , 这样把产生的二进制数值作为一个svm节点, 加载SVM自识别系统在磁盘上的识别模型, 返回识别的结果。

7 号牌识别应用

最后在一台联想Think Pad T430上, 安装了Mac OS Mountain Lion (10.8.5) X64位操作系统和Xcode编程开发软件, 并把APP运行在一台i Phone 4 (操作系统IOS7.1.2) 上实现了号牌识别的全部功能, 见图11。

经过号牌定位、字符分割和字符识别三大步骤后, 实验在真机上的运行效果如图10所示。

8 结语

针对车牌定位这个难点问题, 本文将K-均值算法用于号牌识别的算法并进行了优化, 首先提出用分冶思想用于K-均值算法的初始点选取;然后对K-均值算法得到的结果, 也就是号牌候选区域进行筛选, 结合形状和颜色等因素来最后精确定位车牌, 这样既提高了算法的收敛速度, 又增加了算法的准确性。经IOS平台上实现的整个号牌识别程序实验结果, 证明改进后的号牌定位算法提高了识别率, 成效显著。

参考文献

[1]王晓雪, 苏杏丽.数字图像处理在车牌识别中的应用[J].自动化仪表, 2010, 31 (7) :22.

[2]迟晓君.一种基于支持向量机的车牌字符识别方法[J].信息技术与信息化, 2007, (6) :

一种改进的k-均值聚类算法 篇3

k-均值算法属于聚类技术中一种基本的划分方法,具有简单、快速的优点。其基本思想[1]是选取k个数据对象作为初始聚类中心,通过迭代把数据对象划分到不同的簇中,使簇内部对象之间的相似度很大,而簇之间对象的相似度很小。算法中参数k的值是事先给定的,并在数据对象集中随机选取k个数据对象作为初始聚类中心。一些研究[2,3,4,5]指出,如果初始聚类中心选取不当,k-均值算法的聚类结果可能会陷入局部最优解,从而得不到较好的聚类效果,本文的实验也证实了这一点。怎样从这些局部最优中找到一个较好的聚类结果是一个值得研究的问题。

本文对k-均值算法的初始聚类中心选择方法进行了改进,提出了一种从数据对象分布出发动态寻找并确定初始聚类中心的思路以及基于这种思路的改进算法。实验表明,与传统随机选取初始聚类中心的方法相比,改进后的方法有效改善了它的分类性能,并取得了较高的分类准确率。

1 k-均值算法

算法1 k-均值算法

输入:聚类个数k,以及包含n个数据对象的数据样本集;

输出:满足方差最小标准的k个聚类;

步骤:

(1) 从n个数据对象中任意选择k个对象作为初始聚类中心;

(2) 循环执行(3)到(4),直到每个聚类不再发生变化为止;

(3) 根据每个聚类中所有对象的均值(中心对象),计算样本集中每个对象与这些中心对象的距离,并根据最小距离重新对相应对象进行划分;

(4) 重新计算每个(有变化)聚类的均值(中心对象)。

由以上算法可知,k-均值算法的初始聚类中心是随机选定的,其聚类结果受初始聚类中心的选择影响较大。

2 k-均值改进算法的思想

在k-均值算法中,选择不同的初始聚类中心会产生不同的聚类结果且有不同的准确率,本文研究的目的就是如何找到与数据在空间分布上尽可能相一致的初始聚类中心。对数据进行划分,最根本的目的是使得一个聚类中的对象是相似的,而不同聚类中的对象是不相似的。如果用距离表示对象之间的相似性程度,相似对象之间的距离比不相似对象之间的距离要小。如果能够寻找到k个初始中心,它们分别代表了相似程度较大的数据集合,那么就找到了与数据在空间分布上相一致的初始聚类中心。

为了找到与数据在空间分布上相一致且相似程度较大的数据集合,采取下列步骤:

(1) 计算数据对象两两之间的距离;

(2) 找出距离最近的两个数据对象,形成一个数据对象集合A1,并将它们从总的数据集合U中删除;

(3) 计算A1中每一个数据对象与数据对象集合U中每一个样本的距离,找出在U中与A1中最近的数据对象,将它并入集合A1并从U中删除,直到A1中的数据对象个数到达一定阈值;

(4) 再从U中找到样本两两间距离最近的两个数据对象构成A2,重复上面的过程,直到形成k个对象集合;

(5) 最后对k个对象集合分别进行算术平均,形成k个初始聚类中心。

假设有一个2维数据集,包含有12个对象,其分布如图1所示。

假设要把它们划分为2类,按照上面的思想寻找初始聚类中心。a、b之间的距离最近,那么选择a、b构成一个数据对象集合A1,并将它们从总的集合U中删除。U中与A1相邻最近的对象是c,这样便将c加入A1集合并将它从U中删除。如果规定每个数据集合中所包含对象最大个数为4,则A1中将会再添加对象d。然后在U中再找出相互之间距离最近的两个对象g、h构成A2并将它们从U中删除。U中与A2相邻最近的对象是i,这样便将i加入A2并将它从U中删除,同样j也会并入A2。最后,将这两个对象集合分别进行算术平均,形成两个初始聚类中心。这样得到的初始聚类中心与实际样本的分布更加相符,从而可以得到更好的聚类效果。

3 基本概念

为便于说明问题,给出如下定义:

定义1 数据对象x=(x1,x2,…,xp)和y=(y1,y2,…,yp)之间的距离为:

$d(x,y)=\sqrt{(x{}_1-y{}_2){}^2+(x{}_2-y{}_2){}^2+\Lambda +(x{}_p-y{}_p){}^2}$

定义2 一个数据对象x与一个数据对象集合V之间的距离,定义为这个数据对象与这个数据对象集合中所有数据对象当中最近的距离:

d(x,V)=min(d(x,y),y∈V)

定义3 两个对象集合S和V之间的距离,定义为两个集合S和V中最近的两个数据对象x和y之间的距离:

d(S,V)=min(d(x,y),x∈S,y∈V)

4 改进的初始聚类中心选择算法算法2 初始聚类中心选择算法

假设数据对象集合U有n个数据对象,要将其聚为k类,m的初值为1。算法描述如下:

输入:聚类个数k,包含n个数据对象的数据样本集;

输出:满足方差最小标准的k个聚类;

步骤:

(1) 计算任意两个数据对象间的距离d(x,y),找到集合U中距离最近的两个数据对象,形成集合Am(1≤m≤k),并从集合U中删除这两个对象;

(2) 在U中找到距离集合Am最近的数据对象,将其加入集合Am,并从集合U中删除该对象;

(3) 重复(2)直到集合中的数据对象个数大于等于 a*n/k ( 0<a≤1);

(4) 如果m<k,则m←m+1,再从集合U中找到距离最近的两个数据对象,形成新的集合Am,(1≤m≤k),并从集合U中删除这两个数据对象,返回(2)执行;

(5) 将最终形成的k个集合中的数据对象分别进行算术平均,从而形成k个初始聚类中心。

从这k个初始聚类中心出发,应用k-均值聚类算法形成最终聚类。

5 实验分析

实验环境:P4 CPU,512MB内存,80GB硬盘,Windows 2000操作系统,VC++6.0编程语言。

实验数据:选自UCI数据库中的Iris数据集、Wine数据集和我们自己收集的Web用户数据集HWU1和HWU2。

实验方法:首先采用算法2寻找并确定初始聚类中心;在此基础上再应用算法1形成最终聚类结果。

实验结果:改进算法与随机选取初始聚类中心方法的比较如表1所示。

从表1可以看出:

(1) 随机选取初始聚类中心的方法从不同的初始中心出发会得到不同的聚类结果,聚类准确率有很大的差别,很不稳定,难以确定其是否可用。例如,对Iris数据集,多次随机选择聚类中心,最高准确率可以达到89.33%,最低仅为52.00%;对于HWU2数据集,多次随机选择聚类中心,最高准确率可以达到60.78%,最低仅为50.98%。产生这样结果的原因就是随机选择聚类中心的方法没有考虑到数据的分布情况,而只是给出了一个算法可以运行的必要条件(有初始聚类中心)。

(2) 改进后的算法能够得到较高且稳定的准确率。针对数据集Wine、HWU1可以得到最高准确率的聚类结果,针对数据集Iris、HWU2可以得到接近最高准确率的聚类结果。产生这样结果的原因就是改进后的算法首先根据启发式算法来寻找数据,因而产生的初始聚类中心比较符合数据实际分布,也就更适用于对实际数据的聚类。

6 结束语

本文首先给出了k-均值算法的一般过程,并分析了该算法随机选取初始聚类中心对聚类结果的影响,然后提出了一种从数据对象分布出发寻找初始聚类中心的思想以及基于这种思想的算法过程,并通过实验分析得出改进后的算法能够得到较高且稳定的准确率,更适用于对实际数据的聚类。

参考文献

[1]朱明.数据挖掘[M].合肥:中国科学技术大学出版社,2002.

[2]Kurniawan A,Benech N,Tao Yufei.Towards High-dimensional Cluste-ring[J].COMP,November 1999:1-2.

[3]MacQueen J.Some Methods for Classification and Analysis of Multivari-ate Observations[J].In:Proceedings of 5th Berkeley Symp.Math.Statist,Prob.,1967,1:281-297.

[4]Jolla L.Alternatives to the k-means algorithm that find better clustering[J].In:Proceeding of ACMSIGMOD,1992:192-195.

动态K-均值聚类算法 篇4

关键词：聚类分析,差分进化,K-均值聚类算法,Laplace分布,Logistic混沌搜索

K-均值算法是由Mac Queen[1]提出的一种经典的聚类分析算法,它具有算法简单且收敛速度快的优点,但是算法的聚类结果易受初始聚类中心影响,且容易陷入局部最优。近年来许多学者利用各种常用智能优化算法(如遗传算法[2,3]、微粒群优化[4]等)对K-均值算法进行改进,并取得了不错的效果。

由Storn和Price提出的差分进化(Differential Evolution,DE)算法[5]是一种基于群体进化的启发式算法。该算法从原始种群开始,通过变异(Mutation)、交叉(Crossover)和选择(Selection)操作来生成新种群,通过计算每个个体的适应度值,来确定个体的保留或淘汰,然后通过不断迭代运算,引导搜索过程向最优解逼近。文献[6-7]利用差分进化对K-均值算法进行改进,结果表明,与基于传统遗传、微粒群优化等常用进化算法的K-均值改进算法比较,基于差分进化的K-均值改进算法能获得更好性能。但是,传统差分进化算法也存在算法收敛速度与全局寻优能力之间的矛盾,进化后期易出现早熟、停滞现象,通过改变控制参数虽然可以提高算法收敛速度,但是也会造成其全局寻优能力的下降,从而使得基于传统差分进化的K-均值改进算法的性能受到一定影响。

针对上述问题,该文提出一种基于改进差分进化的K-均值聚类算法,基本思想是:在差分进化算法中通过引入Laplace变异算子来提高算法收敛速度和全局寻优能力,同时通过引入Logistic变尺度混沌搜索,以克服传统差分进化算法进化后期可能出现的早熟、进化停滞现象;然后将其用来改进K-均值算法。实验结果证明,该算法具有较好的全局寻优能力,且收敛速度较快。

1 聚类的基本数学模型

设样本集合为X={X1,X2,⋯,Xn},其中Xi={xi1,xi2,⋯,xid}为d维特征向量,聚类问题的目的就是要找到一个划分C={C1,C2,⋯,CK},使得最终的聚类结果满足:

且使得聚类准则函数JC取得极小值,JC为各样本到对应聚类中心距离的总和:

其中Zj为第j个聚类中心,d(Xi,Zj)为样本到对应聚类中心点的欧式空间距离。

2 改进差分进化算法

2.1 传统差分进化算法

传统差分进化算法通过种群内个体间的合作与竞争,保存优良个体,淘汰劣质个体,以实现对全局最优解的搜索,其演化过程包括变异、交叉和选择三种基本操作。

假设初始种群为PG={Xi,G|i=1⋯NP},其中Xi,G={xji,G|j=1⋯D}为第G代种群中的第i个个体,D为优化问题的维数,NP为种群规模。

1)变异操作

随机从种群中选择一个个体作为父代基向量,选择另外不同的个体作为父代差分向量,生成变异个体Vi,G,即

其中a≠b≠c≠i∈[1,NP],NP为种群规模,G为当前种群的代数,F为缩放因子。

2)交叉操作

利用式(4)对种群中第i个个体Xi,G和其对应的变异个体Vi,G实施交叉操作,生成新个体Xi,G。

其中Xi,G为均匀分布概率,CR为交叉概率,Xi,G为随机选取的整数。

3)选择操作

将原种群的个体Xi,G和新个体Ui,G代入式(5)进行选择,适应度更优的个体进入下一代。

其中Xi,G+1为下一代的第i个个体,f为适应度函数。

2.2 Laplace变异算子

由文献[8]可知,基于柯西分布的变异算子能使算法的寻优能力得到很好地提高,而基于高斯分布的变异算子又能够较好地加快算法的收敛速度。

三种分布的密度函数曲线如图1所示,其中Laplace分布的密度函数同高斯分布相似,区别在于高斯分布概率密度用相对于均值的平方差表示,而Laplace分布概率密度用相对于均值的差的绝对值表示,其密度函数如下:

图中Laplace分布的尾部平滑度介于高斯和柯西变异算子之间,故可知Laplace变异算子既可以较好地保持种群的多样性,又可以使算法的收敛速度得到提高。

2.3 Logistic变尺度混沌搜索

为了克服DE算法在进化后期可能出现的早熟、进化停滞问题,使算法更好地收敛到全局最优解,该文在进化过程中引入了Logistic变尺度混沌搜索。

首先采用Logistic方程产生混沌序列,并按以下方式进行[0,1]中混沌序列和解空间中点列变换:

1)在[0,1]空间上随机产生一个N维变量z1=(z11,z12,⋯,z1N),其中

z1i≠0.25,0.5,0.75;i=1,2,⋯N,然后根据Logistic映射产生M个混沌序列zk,k=1,2,⋯,M

2)使用如下公式,将zk映射到解空间上M个点列xk=(xk1,xk2,⋯,xk N):

3)同理,根据下式将解空间的某个解xk映射到[0,1]区间进行混沌变换:

为使算法初期可以尽可能扩大搜索范围,而后期又可以尽量进行局部细搜索,改进算法采用了变尺度的混沌搜索。则式(7)变换为:

其中σ为尺度系数,G为当前迭代次数,Gmax为最大迭代次数。

3 基于改进差分进化的K-均值聚类算法

3.1 个体编码

改进算法个体采用基于聚类中心的实数编码方式,假设要求把数据分成k类,数据维数为d,每个个体是有k个聚类中心组成的向量,且每个聚类中心是d维的向量,所以每个个体是k×d维向量

Xi(c11,c12,⋯,c1d,c21,c22,⋯,c2d,⋯,ck1,ck2,⋯,ckd)

其中i=1,2,…,N,N为个体的数量;cj表示第j个聚类中心,cjl是代表第j个聚类中心的第l维的值。

3.2 早熟判断

在差分进化算法中,适应度函数用于判断种群进化过程中个体所在位置的好坏。衡量聚类效果的好坏,取决于Jc的结果,Jc越小聚类效果越好。所以,该文定义适应度函数如下:f(Xi)=Jc,同时引入早熟判断规则如公式(11)所示。

其中fi为当前个体适应度,fworst为当前最差个体适应度,fbest为当前最好个体适应度,pi随着迭代的进行将逐渐减小。该文设定一阈值,如果低于该阈值且不满足终止条件时,则认为该个体处于停滞状态。

3.3 算法步骤

步骤1:设定个体数N,最大迭代次数Gmax。

步骤2:种群的初始化:随机选取样本作为聚类中心,并计算当前位置适应度值。

步骤3:对于个体Xi,G按3.2描述产生变异算子F。

步骤4:分别根据式(3)执行变异操作,根据式(4)执行交叉操作,生成试验向量Uki,G,根据式(5)执行选择操作。

步骤5:根据个体的聚类中心编码,按照最近邻法则重新划分样本的归属类别。

步骤6:重新计算新的聚类中心,以替代原值。

步骤7:由式(11)判断是否陷入局部最优,若是,则对该个体变尺度混沌搜索,以利于跳出局部最优,转到步骤3。

步骤8:如不满足所设的终止条件,则转到步骤3,同时G的值自增1;否则输出最好个体值Xbest及最好适应度值f(Xbest),算法结束。

4 实验及效果评价

实验分别采用Iris、Wine和Zoo这3个知名数据集作为测试样本集,参数设置如下:种群规模为数据集维数的10倍,最大迭代次数Gmax为50次。其中DE-kmeans算法[6,7]中缩放因子F为0.5,交叉概率CR为0.1;本文算法中缩放因子F为Laplace随机数,交叉概率CR为0.1,阈值σ为0.8。对三种算法单独运行50次,根据适应度函数分别计算出最小值、最大值、平均值以及收敛到最优值所需要的时间。运行结果如表1所示。

从表1可以看出,K-均值算法虽然收敛速度最快,但因初始聚类中心的不同产生的最小适应度值和最大适应度值的差距较大且寻优精度最差;DE-kmeans的适应度相对稳定,但其收敛所消耗的时间较长;而本文所提算法的结果更加稳定,寻优精度更好,且收敛速度也较快。

5 结束语

本文首先在传统差分进化算法中引入Laplace变异算子和Logistic变尺度混沌搜索以提高其性能,然后将改进的差分进化算法应用于K-均值算法。实验结果表明:该文算法较好地克服了传统K-均值算法的缺点,具有较强的全局搜索能力,且收敛速度较快。

参考文献

[1]MacQueen J.Some methods for classification and analysis of multi-variate observations[C]//Proc.of the 5th Berkeley Symposium onMathematics Statistic Problem,1967,1:281-297.

[2]王家耀,张雪萍,周海燕.一个用于空间聚类分析的遗传K-均值算法[J].计算机工程,2006,32(3):188-190.

[3]Michael Laszlo,Sumitra Mukherjee.A genetic algorithm that exchanges neighboring centers for k-means clustering[J].Pattern Recogni tion Letters,2007,28(16):2359-2366.

[4]Omran M G H,Engelbrecht A P,Salman A.Dynamic clustering using particle swarm optimization with application in unsupervisedimage classification[J].Proceedings of World Academy of Science,Engineering and Technology,2005,9(11):199-204.

[5]Storn R,Price K.Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces[J].Journal ofGlobal Optimization,1997,11(4):341-359.

[6]Paterlini S,Krink T.High performance clustering with differential evolution[C]//Proc.of Congress on Evolutionary Computation,2004,2:2004-2011.

[7]Sudhakar G.Effective image clustering with differential evolution technique[J].International Journal of Computer and CommunicationTechnology,2010,2(1):11-19.

[8]Kuo-Tong Lan,Chun-Hsiung Lan.Notes on the distinction of Gaussian and Cauchy mutations[C]//Proc.of Eighth International Con ference on Intelligent Systems Design and Applications,2008:272-277.

[9]刘兴阳,毛力.基于Laplace分布变异的改进差分进化算法[J].计算机应用,2011,29(10):2719-2722.

[10]沈明明,毛力.融合K-调和均值的混沌粒子群聚类算法[J].计算机工程与应用,2011,47(27):144-146.

[11]张济强,高玉良.遗传模拟退火算法在k-means聚类中的应用[J].电脑知识与技术,2012,8(7):1611-1613.

动态K-均值聚类算法 篇5

关键词：朴素贝叶斯分类器,k-均值聚类,数据挖掘

1 引言

数据挖掘[1]是从大型数据集中将隐含在其中的、人们事先不知道的、对决策有用的知识获取的完整过程。分类是数据挖掘和机器学习中一个重要的研究课题, 它旨在生成一个分类函数或分类模型, 由该模型把数据库中的数据项映射到某一给定类别中, 从而实现对数据的分类。朴素贝叶斯分类器[2] (naive Bayesian classifiers) 是以概率密度函数为基础, 描述分类系统中条件属性和分类属性之间的映射关系。贝叶斯分类器的优点是出错率较小, 但实际上在使用过程中主要存在两个方面的限制:一是先验概率定义困难;二是类别条件独立问题:即独立性假设经常是不满足的。并且独立性假设在一定程度上限制了朴素贝叶斯分类器的适用性, 当处理的数据维数较多, 且数据量较大时, 朴素贝叶斯分类器的效率是偏低的, 且其准确率也有待提高。

针对上述限制, 提出结合k-均值聚类与贝叶斯方法进行分类知识挖掘的解决方案和实现方法。该方法先在数据预处理过程中采用k-均值算法, 得到相互独立的核心属性, 后进行贝叶斯方法的分类知识挖掘。由于k-均值聚类理论的引入, 改善了贝叶斯方法中属性独立性的限制, 提高了分类的准确率。并且由于k-均值算法的引入, 扩大了朴素贝叶斯分类器的应用领域。

2 k-均值聚类算法

2.1 聚类分析

聚类是一个将数据集划分为若干组或类的过程, 并使得同一个组内的数据对象具有较高的相似度;而不同组中的数据对象是不相似的。相似或不相似的描述是基于数据描述属性的取值来确定的。为了实现属性聚类, 通常将一块数据区域A描述成一张表, 在表中有n个对象, 主要是用来存放所有n个对象彼此之间所形成的差异。有矩阵

其中d (i, j) 表示对象i和j对象之间的差异 (或不相似程度) 。通常d (i, j) 为一个非负数;当对象i和j对象非常相似或彼此“接近”时, 该数值接近0;该数值越大, 就表示对象i和对象j越不相似。由于d (i, j) =d (j, i) 且d (i, i) =0, 因此就有上式所示矩阵。

2.2 k-均值算法

k-均值算法以要生成的簇的数目k为输入参数, 把n个对象划分成k个组 (k≤n) , 每个组表示一个簇。首先, 随机地选择k个对象作为初始聚类中心, 而对于所剩下其它对象, 则根据它们与这些聚类中心的相似度 (距离) , 分别将它们分配给与其最相似的 (聚类中心所代表的) 聚类;然后再计算每个所获新聚类的聚类中心 (该聚类中所有对象的均值) ;不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数, 具体定义如下:

其中E为数据库中所有对象的均方差之和;p为代表对象的空间中的一个点;mi为聚类Ci的均值。

k-均值算法试图找到使平方误差准则函数最小的簇。当潜在的簇形状是凸面的, 簇与簇之间区别较明显, 且簇大小相近时, 其聚类结果较理想。该算法复杂度为O (nkt) , 其中n为所有对象的数目, k为簇数, t是迭代的次数, 通常k<<n, t<<n。因此, 对处理大数据集合, 该算法非常高效, 伸缩性好。

3 朴素贝叶斯分类器

每个数据样本均是由为一个n维特征向量, X={x1, x2, …, xn}来描述其n个属性 (A1, A2, …, An) 的具体取值;假设共有m个不同类别, C1, C2, …, Cm。给定一个未知类别的数据样本X, 分类器在已知X情况下, 预测X属于事后概率最大的那个类别。也就是说, 朴素贝叶斯分类器将未知类别的样本X归属到类别Ci, 当且仅当:P (Ci|X) >P (Cj|X) , 对于1≤j≤m, j≠i。根据贝叶斯定理:

由于P (X) 对于所有类为常数, 最大化后验概率P (Ci|X) 可转化为最大化先验概率P (X|Ci) P (Ci) 。若数据集有许多属性和元组, 直接计算P (Ci|X) 的运算量是非常大的。为此, 通常都假设各属性的取值是相互独立的。对于特定的类别且其各属性相互独立, 就会有:, 可以根据数据样本估算P (x1|Ci) , P (x2|Ci) , …, P (xn|Ci) 的值。

根据此方法, 对一个未知类别的样本X, 可以先分别计算出X属于每一个类别Ci的概率P (X|Ci) P (Ci) , 然后选择其中概率最大的类别作为其类别。即朴素贝叶斯分类模型为

4 基于均值的朴素贝叶斯分类算法

基于k-均值算法的朴素贝叶斯分类技术就是利用k-均值算法来研究各列属性之间存在的隐含的依赖关系, 将列属性值进行融合, 达到数据预处理目的, 最后再基于朴素贝叶斯方法进行分类。其处理步骤如下:

1.数据预处理:

(1) 随机地选择k个对象作为初始聚类中心, 而对于所剩下其它对象, 则根据它们与这些聚类中心的相似度 (距离) , 分别将它们分配给与其最相似的 (聚类中心所代表的) 聚类

(2) 再计算每个所获新聚类的聚类中心 (该聚类中所有对象的均值) ;

(3) 不断重复 (1) 、 (2) 直到标准测度函数

通过满足方差最小标准的k个聚类, 将其中相关系数较大的属性合并成一个综合属性。这样随后进行的贝叶斯分类中的各个属性间就能尽可能达到属性独立。

2.基于朴素贝叶斯分类算法进行分类挖掘

通过k-均值算法, 改善了条件属性独立性的限制, 符合朴素贝叶斯分类器的要求。由此可得到改进后的基于k-均值的朴素贝叶斯分类算法:先根据互不相关的核心属性集, 求取类的先验概率P (Ci) ;再由类条件独立的假定, 计算;最后通过上述分类器计算式, 得出分类结果。

5 实验结果及分析

本文中使用NBC表示朴素贝叶斯分类器, KMBC表示基于k-均值算法的朴素贝叶斯分类器。为了测试算法KMBC的效果, 选用了UCI机器学习数据库中的7个典型数据库实例, 数据集的基本信息见表1。实验在WINDOWS XP, J2SDK的平台下完成, 首先补齐决策表, 离散化处理, 在测试过程中同样采用交叉验证法;最后将得到的两种结果进行比较, 结果见表1.

由实验过程及实验结果分析发现, 实验所用的数据实例中, KMBC的分类准确率优于NBC。在算法运行时间上, KMBC略高于NBC, 两者之间运行时间的差别并不明显。

6 结束语

针对朴素贝叶斯分类器的条件独立性假设的限制, 本文提出了一种基于k-均值的朴素贝叶斯算法, 先利用k-均值算法对数据进行预处理, 通过属性合并改善条件属性间的依赖性, 找到一组最近似独立的属性结果, 以符合朴素分类器的算法要求。实验结果表明, 改进后的算法可以达到更精确的分类效果。并且当数据量很大, 而各维属性之间又存在隐含关系是, 改进后的算法是处理这些问题行之有效的方法。

参考文献

[1]han j w.数据挖掘概念与技术[M].北京:机械工业出版社, 2001

动态K-均值聚类算法 篇6

聚类分析是数据挖掘以及无监督机器学习领域的基础问题。目前已经有许多经典的聚类算法, 如K-均值、层次聚类以及谱聚类[1,2]等。然而, 传统的聚类算法通常针对具有单一表示或者单一视图的聚类对象。在多视图数据的情形下, 聚类对象有多种不同的表示并且从每一种表示出发都能对该数据对象进行聚类。多视图对象实现聚类的一个基本方法就是将该对象的相应于不同表示的样本向量合并成一个向量, 如此则将多视图的聚类问题转化成单一视图的聚类问题, 其后即可应用任何已知的单一视图聚类方法。可是, 简单地将数据对象的不同表示合并成一个统一的形式却并未考虑到各个不同表示之间的关系, 因而如何基于多视图数据的特点, 充分利用各个视图的信息对数据对象进行有效聚类即已成为多视图聚类算法的主要目标[3,4,5,6,7,8]。

多视图数据广泛出现在许多应用领域。在自然语言处理领域, 一篇文档或者整个语料库可能具有多语言版本, 每一种语言的版本实际上都是该文档的一个表示, 一个典型实例就是机器翻译领域中的平行语料库。公开发表的学术文章可以有摘要、关键词以及文章正文等多种表示, 这些表示均能概括文章的主旨内容。而且, 互联网也是多视图数据的另一个重要来源。网页可以表示成自然语言文本, 同时也可以由网页中的链接和锚文本来表示。其他的则如计算机图形学中的图像也都具有大量的不同表示, 如像素值、直方图等, 甚至还包括图像对应的标注文本。此外, 在自动语音识别领域, 语音数据一方面可以由声音表示, 同时也可以由一系列表示嘴唇移动的图片来表示。综上所述, 对于这些日渐丰富的多视图数据的聚类问题, 已经引起了人们的广泛关注和高度重视。

许多现存的多视图聚类算法都是基于Co-training[9]的思想[10,11,12,13,14]。Co-training最早是为了解决半监督机器学习领域的问题而由Michal Blum等人引入的。其核心思想是同时训练两个模型, 而后用其中一个模型去预测未标注的训练数据, 再将这些数据加入到原始的标注数据中, 利用新得到的训练数据集训练另一个模型, 如此反复直至达到某一目标。受Co-training的启发, 多视图的聚类算法旨在利用聚类对象在一个视图上的聚类结果去影响在其他视图上的聚类结果, 即在聚类过程中考虑到了不同视图之间的交互作用。这一类型中的一个典型例子就是多视图的K-均值聚类算法。在该算法中, 一个视图上的聚类结果将会用于初始化另一个视图的聚类中心, 反之亦然。但是, 当聚类对象的不同视图的个数有所增加时, 此一方法则变得复杂且难以分析。例如, 当出现三个视图时, 任何两个视图都可以对最后一个视图的初始聚类中心进行初始化, 但应当选择哪一个视图却难以确定, 而当视图个数更大时, 这些问题的复杂度也随之提升。另一个严重的问题则是该算法并不能保证收敛, 这也进一步限制了该算法的应用。

为了克服基于Co-training的K-均值聚类算法的这些缺点, 并结合其他学者的已有研究成果, 本文提出了一个改进的多视图K-均值聚类方法, 该方法具有以下几个特点:

(1) 定义了一个合适的目标函数同时将聚类问题重新表述成为一个凸优化问题。为了最小化该目标函数, 必然得出了一个迭代的优化算法。而且由于这是一个凸优化问题, 算法的收敛性可以得到保证。

(2) 该算法考虑到了不同视图之间的交互作用, 而为了简化这些交互作用, 文中只考虑每两个视图之间的交互, 通过这一考虑, 即可将Co-training的思想扩展到具有大量不同视图的情形, 同时还能保持模型的一致性。

1 多视图K-均值的形式化

K-均值聚类算法已广泛应用于实际的聚类问题中, 研究通过对已有的一个多视图K-均值算法加以改进, 可以更好地利用多视图数据的特点进行聚类。下面, 首先将K-均值聚类算法的求解形式变换成为一个优化问题。

1.1 基于聚簇指示矩阵的形式化

从正交非负矩阵因子模型[15,16]的角度, 传统的K-均值聚类方法可以看作是如下的一个优化问题:

其中, X是输入样本矩阵, 矩阵的每一行是一个聚类对象的向量表示, 每一列则表示这个样本向量的一维。而G称之为聚簇指示矩阵, 且满足 (1) 中的约束条件, 即该矩阵的每一个元素为0或者1, 并且每一行有且仅有一个位置为1, 如果第i行的第k个元素为1, 则表明第i个样本在第k个聚簇中, 该矩阵实际上刻画了这些聚类对象的聚簇结构, 图1即给出了对应的一个样例。矩阵F是聚簇中心矩阵, 其中的每一行表示一个聚簇中心的向量表示。如果n表示样本个数, K表示聚簇个数, 而d为样本的维度, 那么这三个矩阵的大小即可分别表示为n×d、n×K以及K×d。

1.2 多视图聚类的目图标函数

如果将上节中定义的目标函数写成标量的形式, 就会发现这个目标函数实际上给出的是每个样本到其所在聚簇中心距离的平方和, 而该平方和就是K-均值聚类算法的原始目标函数。为了适应多视图的情形, Cai Xiao等[17]提出了一个新的目标函数:

式 (2) 与式 (1) 的区别可作如下表述:

首先, 在多视图情形下, 每一个聚类对象有多个表示, 因此也会有多个样本输入矩阵, 对应于视图v的样本矩阵为X (v) , 类似地也有多个聚簇中心矩阵F (v) , 同时这个新的目标函数对各个视图亦赋予了不同的权值α (v) 。和式 (1) 相同, 该目标函数中也有一个聚簇指示矩阵, 该指示矩阵将不同的视图实现了联结。但是这个目标函数却存在一个问题, 也就是函数假定了在每个视图上的聚簇结构完全相同, 基于该假定, 这个目标函数中只有一个聚簇指示矩阵。在实际的聚类问题中, 不同视图上的聚类结果可能偏差很大, 强制要求所有视图的聚簇结构一样实际上是在不同的聚类结果中选取了一个折中, 但如此一来就有可能损害最优的聚类结果, 因为在其中加入了较差的聚类结果。为了解决这一问题, 文中对这个目标函数进行了修改, 得到了如下的目标:

其中, M为不同视图的个数。

在式 (3) 中, 对每个视图赋予了一个聚簇指示矩阵G (v) , 同时为了保证各个聚簇指示矩阵之间的交互关系又加入了一个约束项, 而λ则表示了该约束项的强度。如果没有该约束项, 将会很容易看到, 最小化该目标函数即是在每一个视图上分别最小化 (1) 式, 因为各个视图之间没有任何关系。约束项的设置就是控制各个视图的聚类结果之间的差异, 防止结果之间出现较大的偏差。为了达到这个目的, 即需要求约束函数L满足如下的两个条件:

(1) 非负性, 即对于任意的参数值, L≥0;

(2) 当且仅当各个视图的聚簇矩阵相同时, L=0。

然而, 在本文的模型中对于每个视图都有一个聚簇指示矩阵, 而聚类的最终结果只能是一个, 因此就必须从这些指示矩阵中选择一个最优的结果。目前, 研究主要是根据数据的特点, 定义一个主视图。一个视图称为主视图, 当且仅当该视图是聚类对象的相比于其他视图的一个更好的表示。如何选取主视图则依赖于研究者对数据的理解。

下节将给出一个具体的约束函数。

1.3 基于视图成对交互的约束项

这一节将会给出一个具体的约束函数的定义, 这个约束函数将多个视图之间的交互关系分解为若干个视图之间的成对交互, 如此变换后一方面能够简化视图之间的交互作用, 另一方面则可以在有更多视图的情形下依然保持模型的一致性。L的定义如下:

式 (4) 中的I称为交互集, 定义如下:

该集合定义了有哪些视图之间存在交互作用。而l (j, k) 的定义即如下:

其中, gi (j) 表示视图j的聚簇指示矩阵的第i行, 由聚簇指示矩阵的定义可知

因而本研究中定义的L符合上一节提出的约束函数需要满足的两个条件。上面已经定义了交互集, 集合的每个元素表示两个彼此有影响的视图, 而对于M个视图, 交互集可能的元素个数即为M (M-1) /2, 当M很大时, 该集合元素就会很多, 模型也随之趋于复杂。并且, 在实际聚类中, 并不是任意两个视图之间都会存在交互关系, 为此即可根据数据集定义一个合适的交互集。

2 模型求解与优化算法

前述分析中已经给出了一个改进的多视图聚类目标函数, 下面即将给出一个迭代优化算法。

2.1 迭代优化算法

算法的模型中有三个参数需要求解:F (v) , G (v) 以及α (v) , 为了求得最优解, 每次迭代都需要固定两个参数, 其后求出另一个参数的最优值, 最终达到收敛。首先固定G (v) 以及α (v) , 更新F (v) 。此时目标函数的优化实际上相当于K-均值算法中聚簇中心的更新过程, 即对每个聚簇, 取该聚簇中所有样本的平均值作为该聚簇新的中心。接下来, 则要固定F (v) 以及α (v) , 更新G (v) , 不失一般性, 假设要更新G (1) , 可将目标函数写成如下形式:

从式 (7) 可以看到, 为了最小化J, 只需要对每一个样本, 求解如下的优化问题:

因为向量gi (1) 的元素均为0或者1, 加之有且仅有一个元素为1, 则gi (1) 可能的取值有K个, 此时枚举所有可能的取值后, 求出最优的解, 对每个样本依次求出对应的gi (1) , 即可推得最优的聚簇指示矩阵G (1) 。

接下来, 就需要更新权值α (v) , 即求解如下的最优化问题:

利用Lagrange函数消除约束, 由其可以得到:

式 (10) 中, H (v) =‖X (v) -G (v) F (v) ‖F2中, 对式 (10) 关于α (v) 求导, 并令导数为0即可以得到:

将代入上式, 进一步得到了α (v) 的更新公式:

至此, 则完整给出了所有参数的更新过程。

2.2 算法超参设定

以上算法中有两个超参需要手工设定, 特别地参数γ控制着不同视图的权值分布, 而γ也控制着一致性约束的强度。如果γ值很大, 则算法赋予每个视图的权值接近于1/M;反之, 如果γ值很小, 那么具有更小H (v) 值的视图对应的取值更大。通过在区间[2, 50]内按照一定的步长进行一维搜索得到最优参数, 而在区间[1e-8, 0.1]直接进行搜索, 可得到最优参数γ。当然, 也许还存在更好的启发式方法可用于选择参数的最优值。

3 实验及结果分析

3.1 数据集

本文在三个标准数据集上进行了聚类实验, 这三个数据集分别是:

(1) Rertus21 578数据集。该语料库包含许多不同的类别。在实验过程中, 选取了包含新闻最多的前10个类别, 从每个类别中随机选取了最多100篇文档。文档的标题和正文可看做是两个不同的视图, 而正文则是主视图。

(2) Rcv1。该语料库包含同一篇文档的多语言版本, 对于一篇英文文档, 包含有通过机器翻译生成的其他语言的相应文档。总共有六种类别, 可分别从每一类别中随机选取200篇英文文档以及对应的法文、德文版本。英文、法文以及德文被认为是三个不同的视图, 其中英文是主视图。由于使用词包模型得到的特征向量非常稀疏, 又使用PLIS[18]进行了降维。

(3) UCI digits dataset是阿拉伯数字的手写字识别数据集, 总共有0~9 10个类别, 各个类别均有200个实例, 每个实例有四种视图, 分别是傅里叶系数FOU, 相关系数FAU以及像素值PIX和KAR系数, 其中PIX是主视图。

表1即给出了这三个数据集的一个整体汇总。

3.2 实验设置

实验中, 使用了一些经典的聚类算法以及最新的多视图聚类算法, 并将这些方法的结果同本文提出的方法进行了比较。具体的对比分析可做如下阐述:

(1) K-均值。在每个视图上分别使用K-均值进行聚类, 并将最好的视图上的结果作为最终的聚类结果。

(2) 谱聚类。在每个视图上分别进行谱聚类, 也将最好视图上的结果作为最终的聚类结果。

(3) RMKMC是在文献[1]中提出的一个新的多视图聚类算法。

文中使用了三个标准的聚类评价指标:纯度 (Purity) , 正规化的互信息 (NMI) 以及F-值 (F-score) [14]。因为本文提出的方法以及前面提到的比较方法都依赖于初始化, 因此对于每一种方法都进行了随机初始化并且运行50次, 基于此来计算平均聚类结果以及标准差。三个数据集上的结果分别如表2、表3和表4所示 (括号内为标准差) 。

3.3 实验结果分析

表2给出了在Reuters21 578数据集上的实验结果。结果表明, 同单视图的K-均值和谱聚类相比, 多视图的K-均值聚类算法在Purity、NMI上提高了9%~10%左右, 而在F-score上则提高了4%~6%左右。关于其他两个数据集上的结果也与这一结论相符。而本文提出的方法同RMKMC相比则有了显著提升, 这也表明了该算法的有效性。

4 结束语

本文通过引入一个一致性约束函数, 得到一个新的多视图聚类目标函数, 为了最小化这个新的目标函数, 则提供了一个迭代更新的优化算法, 该算法能够有效地给出一个局部最优解。一致性约束函数能够有效地结合多种视图提供的信息, 从而提高聚类的效果。在三个数据集上的结果表明了本文提出的改进方法的有效性。

摘要：近几年来, 随着互联网的发展以及大数据时代的来临, 具有多种表示即多视图数据越来越多, 如何将传统的单一表示的数据聚类方法应用在多视图数据被广泛研究。其中传统的K-均值聚类算法因为有效性以及对于大数据的高效性而被扩展到了多视图数据领域, 本文针对最近提出的一个新的多视图K-均值聚类方法, 结合co-training的思想, 提出了一个改进的多视图K-均值聚类算法, 并在三个标准数据集上进行了实验, 同时和已有的一些方法进行了比较, 结果表明了算法的有效性。

动态K-均值聚类算法 篇7

置信规则推理 (RIMER) 是在证据推理、决策理论和产生式规则推理的基础上提出来的不确定信息下的一种专家系统[1,2]。置信规则能够有效地对不确定性和非线性进行建模, 并保证合理的准确度及允许语言的解释性。相对于现存的推理方法, 例如模糊逻辑推理和人工神经网络等, 置信规则推理的特点是能够在系统结构或输入数据含有未知或不完全信息的情况下进行明确地建模和推理。导致未知信息的原因有数据或信息的不完全或丢失[3]、专家或决策者无法提供完全且准备的判断[4,5]等。由于现实中很多决策问题的复杂性和不确定性, 往往无法利用传统方法建立准确的解析式机理模型, 而只能根据已知数据和专家经验进行分析和决策[6]。证据推理和置信规则推理方法为解决未知或不完全信息下的复杂决策和非线性系统问题提供了有利的工具。作为一种新的产生式专家系统, 置信规则推理已成功应用于预测 (如工程系统安全评估[7]、石墨成分检测[1]、管线检漏[8]、涡轮增压器可靠性预测[9]、非线性复杂系统故障预测[10]和惯性平台健康状态估计[11]) 、诊断 (如临床诊疗指导[12]) 、设计 (如新产品设计中的顾客认知风险分析[13]) 和监视 (如核安全保障评估[14]) 等。为了更好地辨识系统的潜在模式, 为决策者提供更可靠的决策策略, 利用专家知识和历史数据对置信规则库的结构和参数进行调节和训练是必要和有助的。

传统方法中, 置信规则库的结构和参数都是由专家或决策者根据经验知识或其它原始模型事前决定[1]。但是, 在大规模的置信规则库以及急剧变化模式的情况下, 仅仅利用专家知识来确定置信规则库的结构和参数是非常困难和不可靠的。置信规则的规则权重和属性权重的微小差异会给置信规则推理的表现带来很大的变化。为此, Yang等提出几种训练置信规则库的单目标和多目标非线性优化模型 (OMTBRBS) , 并将其应用到石墨成分检测[2]。这些模型的显著特点是输入输出信息可以只给出部分, 例如不完全或模糊、数字式或判断式、或者是混合的。 它们可以用来调节通过专家的领域知识或一般常识判断给出的置信规则库。置信规则库被扩展到更加广阔的信息表示框架下的应用, 使得构造各种不同类型的置信规则库系统更加便利。文中建议首先用专家知识初始化置信规则库, 然后利用局部优化算法训练置信规则库的参数, 例如MATLAB中的FMINCON或FMINIMAX等函数。实例仿真验证了专家知识的事先介入能够提高训练过程和训练结果的性能, 并且能够避免不合逻辑的推理结果。常瑞等提出基于梯度法和二分法的联合算法对置信规则库的参数进行训练, 并取得了比利用FMINCON或FMINIMAX等函数更好的训练结果[15]。Liu等在RIMER的基础上提出基于模糊规则的证据推理方法 (FURBER) , 给出训练置信规则库参数的学习算法[7], 并将其应用到工程系统安全评估。Liu等定义了置信规则库的一致性测度, 并提出了产生一致性置信规则库的优化方法[16]。Tang等将置信规则推理利用到新产品设计中的顾客认知风险分析, 并利用贝叶斯网络来产生置信规则库[13]。Zhou等在期望最大化 (EM) 算法的基础上提出在线更新置信规则库参数的递归算法, 并将置信规则推理应用到管线检漏和系统功效预测[8]。以上工作都是首先由专家知识或其它现存模型确定置信规则库的结构, 然后利用相关模型和算法来产生和训练置信规则库的参数。但是在很多复杂的决策和工程问题中, 置信规则库的结构同参数一样, 也不能从有限的专家知识或已有模型中准确产生。过多和过少的规则会相应造成过拟合和欠拟合。Yang等提出了一般形式的置信规则库结构, 考虑了规则前项之间的“与”“或”逻辑关系及层次化的置信规则库推理框架, 并给出了规则前项存在“或”逻辑的规则分解为只含“与”逻辑的基本规则形式的方法[1]。Zhou等在给出置信规则随机效用定义的基础上, 提出调节置信规则库结构的增加规则和删除规则的序贯方法[17]。但是该方法只适用于将置信规则库作为系统逼近器的情况, 也就是未知系统能够给出输入-输出形式的采样数据对;而不适用于作为控制器的情况, 例如在本文实例中集约生产计划中的应用。

当置信规则推理应用于仅有输入变量历史数据的问题中, 因规则前项变量的波动性和非平稳性, 提出相应的算法从输入变量历史数据中挖掘信息对置信规则库的结构进行识别是必须的。本文在K均值[18]和模糊C均值[19]的基础上提出置信K均值聚类算法对应用于系统控制的置信规则库的结构进行动态地识别。K均值中每个数据仅隶属于一个聚类, 模糊C均值中每个数据以隶属度函数的形式隶属于每个聚类。在证据推理框架下, 置信K均值中每个历史数据以置信度的形式隶属于相邻的两个聚类 (评价等级) 。置信K均值通过从历史数据中提取出每个规则前项变量的评价等级, 得到合理的置信规则库结构。该算法的最优聚类与任何两个相邻的评价等级间的距离成正比, 同时保证历史数据与最近的评价等级的距离最短。 这两个特点说明该算法能够提高最优结构的辨识度以及识别和推理的精确度。 本文提供置信规则推理在集约生产计划中应用的案例分析, 验证该算法的合理性和有效性。

1 置信规则推理

1.1 置信规则库的表达形式

产生式规则推理模型可以用下面的四元组表示:

$R=<X,A,D,F>(1)$

其中, X={Xi;i=1, …, T}是规则前项变量的集合, 每个前项变量在评价等级参考集A={A1, A2, …, AT}中取值。Ai={Ai, j;j=1, …, Ji}是前项变量Xi的分布式评价等级;Ai, j是一个评价等级参考值, 可以取值为语言型或数字型等;Ji=|Ai|是前项变量Xi的评价等级的个数。{X1→A1, X2→A2, …, XT→AT}是一组表示问题域的有限基本状态, 可以由AND (∧) 和OR (∨) 连接符连接起来。D={Dn;n=1, …, N}是规则后项变量的分布式评价等级, N是评价等级的个数。F是反映条件 (规则前项) 和结论 (规则后项) 之间关系的逻辑函数。

在此基础上, 置信规则推理中规则的基本形式表示如下:

$\begin{array}{l}R{}_k:\text{Ι}\text{F}A{}_1^k\wedge A{}_2^k\wedge \cdots \wedge A{}_{{\rm T}{}_k}^k\\ \text{Τ}\text{Η}\text{E}\text{Ν}\{(D{}_1,\overline{\beta }{}_{1,k}),(D{}_2,\overline{\beta }{}_{2,k}),\cdots ,(D{}_{{\rm N}},\overline{\beta }{}_{{\rm N},k})\},\\ \left({\displaystyle \sum _{n=1}^{{\rm N}}\overline{\beta }}{}_{n,k}\le 1\right)‚\text{规}\text{则}\text{权}\text{重}\text{为}\theta {}_k‚\text{前}\text{项}\text{变}\text{量}\text{权}\\ \text{重}\text{为}\delta {}_{1,k},\delta {}_{2,k},\cdots ,\delta {}_{{\rm T}{}_k,k}‚k\in \{1,\cdots ,L\}\end{array}(2)$

其中, Rk (k=1, …, L) 表示第k条规则, Aki (∈Ai;i=1, …, Tk) 是第i个前项变量在第k条规则中对应的评价等级, Tk是第k条规则中前项变量的数目, $\overline{\beta }{}_{n,k}$是第k条规则中规则后项相对于评价等级Dn的置信度, δi, k (i=1, …, Tk) 是第i个前项变量在第k条规则中的权重。如果${\displaystyle \sum _{n=1}^{{\rm N}}\overline{\beta }}{}_{n,k}=1$, 说明第k条规则是完备的;如果$0\le {\displaystyle \sum _{n=1}^{{\rm N}}\overline{\beta }}{}_{n,k}<1$, 说明第k条规则是不完备的。置信规则推理理论假设置信规则库中的L条规则相互独立, 也就是L个评价等级集合Ak (={Ak1, …, AkTk};k=1, …, L) 相互独立。

1.2 基于证据推理的置信规则推理算法

因置信规则之间的独立性满足递归证据推理 (RER, Recursive Evidential Reasoning) 的前提要求, Yang等提出了基于递归证据推理的置信规则推理算法[1]。在进行置信规则推理之前, 必须确定当前输入与每个规则前项变量的评价等级参考值之间的关系, 以产生每条置信规则的激发权重。其主要思想是检查每个规则前项变量的评价等级, 以确定当前输入相应于每个评价等级匹配度。其等价于将每个输入变量转换为评价等级与相应置信度的分布式形式。为了进行多维度的信息处理, Yang等给出了置信规则推理模型中各种形式的输入信息的转换框架及相关技术[1]。利用分布式评估方法, 输入中的第i个变量X*i可以转换为如下的分布式形式:

$S(X{}_i^{*})=\{(A{}_{i,j},\alpha {}_{i,j});j=1,\cdots ,J{}_i\}(3)$

其中αi, j是X*i相对于其评价等级Ai, j的置信度, 满足αi, j≥0及${\displaystyle \sum _{j=1}^{J{}_i}\alpha }{}_{i,j}\le 1‚i=1,\cdots ,{\rm T}.$

输入对第k条规则的匹配度为:

$(A{}_1^k,\alpha {}_1^k)\wedge (A{}_2^k,\alpha {}_2^k)\wedge \cdots \wedge (A{}_{{\rm T}{}_k}^k,\alpha {}_{{\rm T}{}_k}^k)(4)$

其中Aki∈{Ai, j;j=1, …, Ji}, αki∈{αi, j;j=1, …, Ji}。

置信规则推理的输入与输出的函数映射及推理输出的分布式形式可表示如下:

$S(X{}^{*})=\{(D{}_n,\beta {}_n);j=1,\cdots ,{\rm N}\}(5)$

其中βn由式 (6) 和式 (7) 得出。βn和βD满足${\displaystyle \sum _{n=1}^{{\rm N}}\beta }{}_n+\beta {}_D=1$。 ωk是每条置信规则相应的激发权重, βn, k是考虑输入的不完备性对$\overline{\beta }{}_{n,k}$进行更新后的置信度。

$\beta {}_n=\frac{\eta \left[{\displaystyle \prod _{k=1}^L\left(\omega {}_k\beta {}_{n,k}+1-\omega {}_k{\displaystyle \sum _{n=1}^{{\rm N}}\beta }{}_{n,k}\right)}-{\displaystyle \prod _{k=1}^L\left(1-\omega {}_k{\displaystyle \sum _{n=1}^{{\rm N}}\beta }{}_{n,k}\right)}\right]}{1-\eta \left[{\displaystyle \prod _{k=1}^L(}1-\omega {}_k)\right]}(6)$

η=

$\frac{1}{{\displaystyle \sum _{n=1}^{{\rm N}}{\displaystyle \prod _k^L(}}\omega {}_k\beta {}_{n,k}+1-\omega {}_k{\displaystyle \sum _{n=1}^{{\rm N}}\beta }{}_{n,k})-({\rm N}-1){\displaystyle \prod _{k=1}^L(}1-\omega {}_k{\displaystyle \sum _{n=1}^{{\rm N}}\beta }{}_{n,k})}$

(7)

2 置信规则推理的应用模式与结构识别

2.1 置信规则推理的应用模式

置信规则推理的应用可以划分为系统逼近器和系统控制器。作为系统逼近器和系统控制器的置信规则推理的应用模式可以用图1和图2表示。作为系统逼近器, 置信规则库的训练和调节由观察输出和推理输出的误差驱动, 置信规则推理输出是对实际系统输出的预测。作为系统控制器, 置信规则库的训练和调节由系统表现驱动, 置信规则推理输出是实际系统运作过程中的控制或决策变量。在系统逼近器和系统控制器应用模式下, 训练置信规则库的目标函数分别为式 (8) 和式 (9) 所示。

$\begin{array}{l}\min \xi (x,y,\widehat{y})=\xi ((\beta ,\theta ,\alpha )|(x,y))\\ =\xi (\widehat{y}(x)-y(x))=\xi (\widehat{y}(x;\beta ,\theta ,\alpha )-y(x))(8)\\ \min \Psi (x,q)=\Psi ((\beta ,\theta ,\alpha )|x)=\Psi (x,q(x;\beta ,\theta ,\alpha ))(9)\end{array}$

对于图1所示的置信规则库作为系统逼近器的应用, 历史数据以输入-输出数据对的形式给出, Zhou等在给出置信规则随机效用定义的基础上, 提出调节置信规则库结构的增加规则和删除规则的序贯算法[17]。本文针对置信规则库作为系统控制器的应用 (如图2所示) , 在历史数据只有输入数据的情况下, 提出调节置信规则库结构的置信K均值聚类算法, 但其也适用于置信规则库作为系统逼近器时的应用。

2.2 置信规则库的结构识别

本文中的结构识别是指在确定了规则库前项变量间的“与”“或”逻辑关系和置信规则库的级联层次化框架[1]情况下, 从输入变量历史数据中挖掘信息确定每个规则前项变量的评价等级及其效用。为了构建规则库, 必须确定每个前项变量的评价等级以及评价等级的数目[1]。置信规则库的结构及其规则数目取决于评价等级在输入变量定义域上的位置及其数目。寻找最优的置信规则库结构也就是寻找最合适数目和位置的评价等级集合, 该评价等级集合能够保证置信规则库对采样数据和系统模式形成最好的拟合。每个置信规则的前项都由所有前项变量及其每个评价等级交叉连接而成。式 (2) 中的规则前项可以写为式 (10) 和式 (11) 两个等价式, 其中μ (AkTk) 为前项变量XTk的评价等级AkTk的效用。一方面, μ (AkTk) 的不同取值直接决定了置信规则库前项变量评价等级的效用位置。另一方面, 对含有T个前项变量 (X={Xi;i=1, …, T}) 的置信规则库, Ji=|Ai|是前项变量Xi的评价等级的个数, 那么完整的置信规则库就含有$L={\displaystyle \prod _{j=1}^{{\rm T}}J}{}_j$条规则。考虑在决策者给出每个前项变量评价等级的数目的情况下, 从历史数据中挖掘出合理的评价等级效用的位置。图3给出了更直观的说明。其中*表示某前项变量的历史采样数据, {H1, H2, H3}表示该前项变量的评价等级, μ (Hi) (i=1, 2, 3) 是Hi的效用。 (a) 和 (b) 代表两种评价等级效用的定义。

结合图3和式 (11) , 规则前项评价等级效用的位酌直接决定了对应置信规则在输入变量定义域中的位置。置信规则库由置信规则组成, 在输入变量历史数据密集的地方设置前项变量评价等级及其效用, 可以使相应置信规则能够更好表达输入变量的信息模式, 提高置信规则库对输入变量的建模能力, 使得置信规则库的推理输出更加准确。图3 (a) 中评价等级效用的定义显然比 (b) 更有效。本文提出置信K均值聚类算法, 通过对输入变量历史数据的挖掘, 调节前项变量评价等级效用的位置, 得到更加合理的置信规则库结构。

$\begin{array}{l}R{}_k:(X{}_1\text{i}\text{s}A{}_1^k)\wedge (X{}_2\text{i}\text{s}A{}_2^k)\wedge \cdots \wedge (X{}_{{\rm T}{}_k}\text{i}\text{s}A{}_{{\rm T}{}_k}^k)(10)\\ R{}_k:(X{}_1\text{i}\text{s}\mu (A{}_1^k))\wedge (X{}_2\text{i}\text{s}\mu (A{}_2^k))\wedge \cdots \wedge (X{}_{{\rm T}{}_k}\text{i}\text{s}\mu (A{}_{{\rm T}{}_k}^k))(11)\end{array}$

3 置信K均值聚类算法

置信规则前项变量Xi含有Mi个采样数据{xi, j|j=1, …, Mi};CkXi为Xi的第k个聚类中心, 也就是评价等级效用的位置。在K均值[18]和模糊C均值[19]的基础上, 提出置信K均值聚类算法。K均值中每个数据仅隶属于一个聚类, 模糊C均值中每个数据以隶属度函数的形式隶属于每个聚类。在证据推理框架下, 置信K均值中每个历史数据以置信度的形式隶属于相邻的两个聚类 (评价等级) 。置信K均值聚类算法的目标函数及约束如下:

$\begin{array}{l}\min \Xi (C{}_{X{}_i}^k|k=1,\cdots ,{\rm K})={\displaystyle \sum _{j=1}^{{\rm M}{}_i}(}\gamma {}_{j,p}^i\parallel x{}_{i,j}-C{}_{X{}_i}^p\parallel \\ +\gamma {}_{j,p}^i\parallel x{}_{i,j}-C{}_{X{}_i}^q\parallel )(12)\end{array}$

$\begin{array}{l}\text{s}.\text{t}.C{}_{X{}_i}^p=\underset{k=1}{\overset{{\rm K}}{{\displaystyle \max }}}\{C{}_{X{}_i}^k|C{}_{X{}_i}^k\le x{}_{i,j}\}(13)\\ C{}_{X{}_i}^q=\underset{k=1}{\overset{{\rm K}}{{\displaystyle \min }}}\{C{}_{X{}_i}^k|C{}_{X{}_i}^k\ge x{}_{i,j}\}(14)\\ \gamma {}_{j,p}^i=\frac{\parallel x{}_{i,j}-C{}_{X{}_i}^q\parallel }{\parallel C{}_{X{}_i}^q-C{}_{X{}_i}^p\parallel }(15)\\ \gamma {}_{j,q}^i=\frac{\parallel x{}_{i,j}-C{}_{X{}_i}^p\parallel }{\parallel C{}_{X{}_i}^q-C{}_{X{}_i}^p\parallel }(16)\\ C{}_{X{}_i}^m\ne C{}_{X{}_i}^n,m,n=1,\cdots ,{\rm K};m\ne n(17)\end{array}$

$\begin{array}{l}\overline{x{}_i}\le C{}_{X{}_i}^m\le \overline{x{}_i},m=1,\cdots ,{\rm K}(18)\\ L{}_{{\rm X}{}_i}^S\le \parallel C{}_{X{}_i}^m-C{}_{X{}_i}^{m+1}\parallel \le L{}_{{\rm X}{}_i}^G,m=1,\cdots ,{\rm K}-1(19)\end{array}$

其中CpXi和CqXi是距离xi, j最近的两个相邻评价等级, γij, p和γij, q是xi, j分别分配到CpXi和CqXi上的置信度, $\underset{¯}{x{}_i}$和$\overline{x{}_i}$分别是Xi的下限和上限, LSΧi和LGΧi分别是两个相邻评价等级间的最小和最大识别距离, K是聚类数目, ‖*‖是欧几里得距离。在目标函数Ξ中, γij, p和γij, q分别代表xi, j相对于CpXi和CqXi的置信度特征函数, ‖xi, j-CpXi‖和‖xi, j-CqXi‖分别代表xi, j相对于CpXi和CqXi的欧几里得距离。xi, j分配到其它非相邻聚类中心上的置信度γij, k=0 (k≠p, q) 。

从式 (12) 、式 (15) 和式 (16) 得$\Xi (C{}_{X{}_i}^k|k=1,\cdots ,{\rm K})=2{\displaystyle \sum _{j=1}^{{\rm M}{}_i}\frac{\parallel x{}_{i,j}-C{}_{X{}_i}^p\parallel \cdot \parallel x{}_{i,j}-C{}_{X{}_i}^q\parallel }{\parallel C{}_{X{}_i}^q-C{}_{X{}_i}^p\parallel }}$。该公式表示:①最优置信K聚类与相邻评价等级之间的距离成正比, 与人的认知能力相一致;②最优置信K聚类保证采样点以最小的距离靠近评价等级, 也就是保证输入变量尽可能趋近置信规则前项, 提高了置信规则库识别与推理的精确度。置信规则库的结构确定以后, 可以利用OMTBRBS来训练得到置信规则库的参数。

4 实例分析

本文以置信规则推理在集约生产计划中的应用为例来验证置信K均值算法的有效性及相对于传统依靠专家知识确定置信规则库结构方法的优越性。集约生产规划的任务是决定一段有限的时期内 (通常是6个月至两年) 的劳动力、生产力和库存水平以应对需求的不确定性和波动性。库存水平可以通过库存方程由生产力水平得出。案例及数据来源于HMMS (Holt, Modigliani, Muth and Simon) 匹兹堡油漆厂1949～1954年的实际运营数据[20], 其中需求数据如图4所示, 成本函数包括:正常雇佣成本 (Cr (t) =340.0Wt) 、聘用与解雇成本 (Cc (t) =64.3 (Wt-Wt-1) 2) 、加班与减班成本 (Co (t) =0.20 (Pt-5.57Wt) 2+51.2Pt-281.0Wt) 和库存相关成本 (Ci (t) =0.0825 (It- (320.0+0.0Dt) ) 2) 。 其中Wt、Pt、It和Dt分别表示第t个周期的劳动力水平、生产力水平、库存水平和销售量。

库存方程为

${\rm I}{}_t={\rm I}{}_{t-1}+{\rm P}{}_t-D{}_t(20)$

T个周期的总成本目标函数为

${\rm T}C{}_t={\displaystyle \sum _{n=t-{\rm T}+1}^t(}C{}^r(t)+C{}^c(t)+C{}^o(t)+C{}^i(t))(21)$

决策变量的边界与容量约束如下:

$\begin{array}{l}{\rm P}{}_t\le \overline{{\rm P}}{}_t(22)\\ W{}_t\le \overline{W}{}_t(23)\\ -\overline{V{\rm P}}{}_t\le {\rm P}{}_t-{\rm P}{}_{t-1}\le \overline{V{\rm P}}{}_t(24)\\ -\overline{VW}{}_t\le W{}_t-W{}_{t-1}\le \overline{VW}{}_t(25)\\ {\rm P}{}_t,W{}_t,\overline{{\rm P}}{}_t,\overline{W}{}_t,\overline{V{\rm P}}{}_t,\overline{V{\rm P}}{}_t,\overline{VW}{}_t,\overline{VW}{}_t\ge 0(26)\end{array}$

其中置信$\overline{{\rm P}}{}_t$和$\overline{W}{}_t$和为生产力和劳动力水平的能力约束, $\overline{V{\rm P}}{}_t$和$\underset{¯}{V{\rm P}}{}_t$为生产力允许的增加和减少变化量, $\overline{VW}{}_t$和$\underset{¯}{VW}{}_t$为劳动力允许的增加和减少变化量, 所有变量不小于零。

置信规则库由生产力水平子规则库和劳动力水平子规则库组成, 其层次化框架如图5所示。前者的规则前项为需求预测D${}_t^f$、库存水平It-1、劳动力水平Wt-1和生产力水平Pt-1, 规则后项为生产力水平Pt.后者的规则前项为生产力水平Pt和劳动力水平Wt-1, 规则后项为Wt.两个子规则库的置信规则分别表示如下:

$\begin{array}{l}\text{Ι}\text{f}D{}_t^f\text{i}\text{s}{\rm H}{}_{1,j{}_1},{\rm I}{}_{t-1}\text{i}\text{s}{\rm H}{}_{2,j{}_2},W{}_{t-1}\text{i}\text{s}{\rm H}{}_{3,j{}_3},\\ \text{a}\text{n}\text{d}{\rm P}{}_{t-1}\text{i}\text{s}{\rm H}{}_{4,j{}_4},\\ \text{t}\text{h}\text{e}\text{n}{\rm P}{}_t\text{i}\text{s}\{({\rm H}{}_{4,1},\beta {}_{r{}_1,1}^1),({\rm H}{}_{4,2},\beta {}_{r{}_1,2}^1),\cdots ,({\rm H}{}_{4,J{}_4},\beta {}_{r{}_1,J{}_4}^1)\}\end{array}(27)$

其中jk=1, …, Jk (k=1, …, 4) , r1=1, …, R1, θr1是第rth1个置信规则的规则权重。

$\begin{array}{l}\text{Ι}\text{f}{\rm P}{}_{t}is{\rm H}{}_{4,j{}_4}\text{a}\text{n}\text{d}W{}_{t-1}\text{i}\text{s}{\rm H}{}_{3,j{}_3},\\ \text{t}\text{h}\text{e}\text{n}W{}_t\text{i}\text{s}\{({\rm H}{}_{3,1},\beta {}_{r{}_2,1}^2),({\rm H}{}_{3,2},\beta {}_{r{}_2,2}^2),\cdots ,({\rm H}{}_{3,J{}_3},\beta {}_{r{}_2,J{}_3}^2)\}\end{array}(28)$

其中jk=1, …, Jk (k=4, 3) , r2=1, …, R2, θr2是第rth2个置信规则的规则权重。

基于置信规则推理的集约生产计划方法提供了一种动态的决策方法, 也就是在每个月初对下个决策周期 (本文中T=12个月) 进行规划, 在下个月初根据新的态势重新规划。由于1955年的需求数据没有被记录, 其影响到1954年的动态规划, 1949年的数据作为历史数据来初始化和训练1950年初的置信规则库, 所以给出1950～1953年四年的仿真结果。设定每个决策变量有3个评价等级, 由此两个子规则库的置信规则数目分别为34=81条和32=9条。3个评价等级的两端两个分别由边界条件决定, 所以问题转化为识别出中间的评价等级。需求、库存水平、劳动力水平和生产力水平的两端的评价等级的效用分别为:μ (H1, 1) =100, μ (H1, 3) =900; μ (H2, 1) =100, μ (H2, 3) =600; μ (H3, 1) =60, μ (H3, 3) =120; μ (H4, 1) =300, μ (H4, 3) =800。为了进行图示比较, 由专家知识和置信K均值得到的需求、劳动力、生产力和库存水平的中间评价等级的效用在图6中绘出。

图6中虚线和实线分别表示由专家经验知识和置信K均值得到的需求、劳动力、生产力和库存水平的中间评价等级的效用。因为没有考虑到历史数据所蕴含的潜在模式, 由专家知识直接确定的中间评价等级的效用不能根据实际情况做出相应变化。而由置信K均值从每个变量的历史数据中挖掘得到相应的中间评价等级的效用, 能敏感地反映数据中所蕴含的潜在信息和模式。表1列出了利用两种方法下所得到的成本要素。因为置信K均值从历史数据中挖掘出更适合的置信规则结构, 使得输入数据与置信规则的匹配更加合理, 得到更加准确的推理输出, 所以利用置信K均值的结构识别方法比利用专家经验知识的方法得到更小的总成本。

5 结语

针对置信规则库作为系统控制器时的应用, 本文在K均值和模糊C均值的基础上提出置信规则库结构识别的置信K均值聚类算法。该算法的特点是:①最优置信K聚类与相邻评价等级之间的距离成正比, 与人的认知能力相一致;②最优置信K聚类保证采样点以最小的距离靠近评价等级, 也就是保证输入变量尽可能趋近置信规则前项, 提高了置信规则库识别与推理的精确度。该算法同样适用于置信规则库作为系统逼近器时的应用。本文中置信规则库中评价等级的数目仍然由决策者实现给出, 下一步的工作是提出相应的数据挖掘算法, 不但动态地确定和调节评价等级效用的位置, 而且对其数目也要进行识别。

摘要：针对置信规则推理作为系统控制器时的应用, 提出一种置信K均值聚类算法用于置信规则库的结构识别。在构建好置信规则库的推理框架后, 该算法通过对规则前项输入变量的历史数据进行挖掘, 得到合理的置信规则库结构, 提高推理与决策的精度。相对于传统专家知识确定置信规则库结构的方法, 该算法的特点是:最优聚类与相邻评价等级之间的距离成正比, 与人的认知能力相一致;最优聚类保证采样点以最小的距离靠近评价等级, 也就是保证输入变量尽可能趋近置信规则前项。通过置信规则推理在集约生产计划中应用的案例分析验证了该算法的合理性和有效性。