为了正常的体验网站,请在浏览器设置里面开启Javascript功能!

一种搜索模糊聚类全局最优解的Tabu算法

2017-11-28 11页 doc 139KB 23阅读

用户头像

is_841159

暂无简介

举报
一种搜索模糊聚类全局最优解的Tabu算法一种搜索模糊聚类全局最优解的Tabu算法 一种搜索模糊聚类全局最优解的 Tabu 算法A Tabu SearcAhl gorithm for FuzzyCl ustering 1 1 2 孙银慧 白振兴 董天明 SunYi nhui Bai Zhenxing DongTi anming ,1.空军工程大学工程学院, 陕西 西安 710038; 2.94333部 队, 山东 潍坊 261000, (1.Air ForceE ngineering University, Shanxi x’ian 710038; 2. 9...
一种搜索模糊聚类全局最优解的Tabu算法
一种搜索模糊聚类全局最优解的Tabu算法 一种搜索模糊聚类全局最优解的 Tabu 算法A Tabu SearcAhl gorithm for FuzzyCl ustering 1 1 2 孙银慧 白振兴 董天明 SunYi nhui Bai Zhenxing DongTi anming ,1.空军工程大学工程学院, 陕西 西安 710038; 2.94333部 队, 山东 潍坊 261000, (1.Air ForceE ngineering University, Shanxi x’ian 710038; 2. 94333 U,nSithandongW eifang 261000) 摘 要:模糊聚类问题由于其非凸性而成为一个难以解决的数学问。题在解决模糊聚类问题时,会出现很多局部极小值和鞍点因此,启发式的模糊 C- 均值算法是应用最为广泛的算法,其缺点是很容易陷入局部极小值本文提出了一种搜索模糊聚 。。 类全局最优解的 Tabu 搜索算法,并比较这种新算法和模糊C - 均值算法的性能。经过多次数据试验,证明 Tabu 搜索算法在搜 索全局最优解时是很有效的。 关键词:模糊聚类;模糊C - 均值算法;Tabu 搜索技术;全局最优值 中图分类号:TP301.6 文献标识码:A 文章编号:1671-4792(-2008)10-0006-04 Abstrac,t The Fuzzy Custerng Problem (FCP)s a mathematca program whichs difficult to solves nce it s nonconvex,which liiiliiiimplies possession of many local minima.The fuzzy C-means heuristic is a widely known approachto this problem, butit is guaranteed only to yield local minima. In this paper,a new approach was proposed about this probislem ba swedhoni ch t abu search techniquein order to find a global solution of FCE. Thepe rformance of the algorithm was comparedwit h the fuzzy C-meansa lgorithm’s.it was provede ffect. , KeywordsFuzzy Clustering; Fuzzy C-meansAlg orithm; Tabu Search Technique;Globa l Optimization 0 引言 集被划分成 c 个子集且有 2?c?n,m 是平滑参数,又称加权 简要说来,模糊聚类问题就是,给定一些样本,要求根据 指数,m,1,尽管从数学角度看 m 的 出现 不 太 自然 , 但 如 果 样本的某些特征把这些样本进行聚类,并且可以根据某个样 不对隶属度加权,从硬聚类目标函数推广到模糊聚类目标函 本对于某个类或者多个类的隶属程度而 在聚 类 过 程中 把 这 ss 数将是无效的,xR,ln,R是数据点的 特征 空 间 ,z是 ??i?ij 个样本归入某一个类或多个类。 在硬聚类中每一个样本只能 s未 知 的 聚类 中 心 , 且 , 示 和 聚 类 中 心 ?z?R,l?j?cxz‖‖ji j 属于某一个确定的类。 的 Euclid 距离,Z=[z,z,…z]是一个 s×c 的矩阵,W{w]是一 12cij为方便对模糊聚类问题进行数学描述,在一个 s 维的空 个 n×c 的矩阵。 间中描述这些样本 ,s 表示这些样本所据以聚类的特征的数 如果矩阵 W 已知,问题就演化成寻找聚类中心 Z。 寻找 目。 所以,可以把模糊聚类描述成一个非线性的问题。 聚类中心是比较简单的,并且它的全局最小值总是可以求得 取 J,W,Z,的极小值, 的。 如果已知聚类中心 Z,那么,在求得 W 之后,就很容易解 决全局解的问题。 在求解模糊聚类问题时, 模糊 C- 均值算法是应用最为 1, , 广泛的一种算法。 模糊 C- 均值算法是先选择一个初始值,然 后算法不断迭代 ,计算当前聚类中心和 Z 之间的距离, 以 及 约束条件,当前 W 和给定 W 之间的距离。 当连续两次计算出的 W 或 Z ,2, 之间的距离小于预先给定的阈值时,算法停止。 前人已经证 4[]明算法是收敛的。 然而,算法也可能陷入模糊聚类问题的某 ,3, 此处,n 表示被聚类的样本,数据点,的数目,c 表示样本 个局部极小值或者鞍点而停止迭代。 这是因为当 J,W,,和 J 。 J、J、J分别表示相应的目标函数值。 对当前中心 z心矩阵 tub u 不断进行操作,通过后面将要叙述的位移产生可能的聚类中 ,,Z,都是凸函数时,函数 J,W,Z,是非凸的。 算法停止在某 心。 在算法进行过程中,需要保存最优聚类中心 z,并相应地 个局部极小值意味着所得到的解还可以进一步改进。 本文提 b 对目标函数值 J、J、J进行操作。 出的 Tabu 搜索算法就是搜索 模 糊 C- 均值 算 法 可能 找 不 到 tub 的全局最优解。 因为是进行 Tabu搜索 , 因此必须分离这些位移并存储Tabu 搜索是一种搜索局部最优解之外的解空间的一种引 在 Tabu列表中 。 位移定义如下, [1]导式的局部启发式搜索过程。 Glover引进这种算法主要是 ,7, [2]为了解决组合数学方面的问题。 Hansen用别的名字描述它 jj的基本思想,“急剧上升,平缓下降”。 自此,Tabu 搜索算法被 其中,z是第 j 个可能的中心,z是第 j 个当前中心,d? t u [3]成功地应用在商店的货物流通、建筑设计等方面。 s R是 d方向的随机向量,d=,d,,d=0,-1,+1。 经观察得知,当 j ii1 Tabu 搜索算法 越来越接近问题的解时, 需要以非常小的步幅来进行迭代。 给定一组 z,j=1,2,…c,可以利用下述公式计算全局最优 j可以用如下算法求方向乘子 α。 解, 算法描述如下, Step1,初始化,令 z为可能的 中心 ,J为 相 应的 目 标 函数 u u 值,z=z,且有 J=J,分别为 Tabu 列表长度,NTLM,、概率 阈 bubu 值 (P)、 可能解的数目 (NH)、 每个中心的最大迭代次数,I- MAX, 赋 值 。 方 向 乘 子 α=1, 迭 代 计 数 器 β=0.75, 令 k=1, ,4, NTL=0,l=1, Step2,利用可能的中心 z,固定所有中心,并通过产生 NH u 12NH l ,个邻近的点 z,z,… z来移动中心 z, 并 求 相 应的 目 标 函数 u 12NH 上述公式是求解令 J,W,Z,的偏导为 0 的 W 而得到的, J,J,…J的值。 Step3, 并且考虑到 W 可能为零阵。 模糊 C- 均值算法利用,4,式求 i 得所给定聚类中心值的权值。 给定权值 w和聚类中心 z,即 ?对 J,i=1,2,… NH 进行非降序排序 , 排 好 序后 , 将 它 们 t ij j [1] [NH] [1] [2] [NH] [1] 可求解目标函数 J,W,Z,, 标 记 为 ,J , … J , 显 然 J J ? … J , 若 J J , 则??? t t t t t t b k=k+l, , 5, [1]?如果用来产生 z的方向不是 Tabu 的,或者即使是 Tabu [1] l [1][1] 由此 可 知 , 对于 任 意 给定 的 一 组聚 类 中 心 z, 都 对 应 着,但是 J?J ,则令 z=z且 J =J,跳转到 Step4。 否则,产的 t b u u t j 目标函数的一个特定的值。 所以,可以利用这种新的搜索算 生 u :U (0,1) , 此 处 ,U (0,1) 是 一 个 (0,1) 之 间 的 函 数 ,, 如 果 法来形成聚类中心 z,并会产生一个目标函数的值 J,W,Z,。 j[1] [1] l [1]且 ,则令 ,跳转到 ,否则,跳J?J?J u,PJ =Jz=zStep4 bt u u t u 可以比较三种类型的聚类中心和它们所 对 应 的目 标 函 数的 转到 Step3的 ?, 值。 [2][NH]?重复进行 Step3的 ?,计算 zt,… z, 直 到 选中 一 个 t给定权值 w,就可以用下述的公式计算最优聚类中心, ij邻近的点,跳转到 Step4, ?若 k,IMAX,跳到 Step5,否则跳转到 Step2选择 新的 邻近点集。 ,6, l Step4, 如果 Tabu列表 中不存在产生 z的方向向量,则 u 上述公式是求解令 J ,W,Z, 的偏导为 0 而得到 Z。 当 , 令 NTL=NTL+1。 若 将 此 方 向 向 量 添 加 到 列 表 末 尾 m=1,硬聚类,时,,6,式为聚类中心。 FCM 算法利用,6,式在 NTL=NTLM+1,则删除列表头,并令 NTL=NTL-1。 若 J,J, bu已知隶属度矩阵的前提下求得聚类 中 心 。 所 以 , 可 以利 用 令 J=J,Z=Z,跳转到 Step2。 bubu Tabu 搜索技术结合,6,式和 w的值计算聚类中心 z。 实践证 ij jStep5, 若 l,c ,c 为 聚 类 数 ,, 则 l=l+1, 跳 转 到 Step2, 否 明,利用 z求 w比利用 w求 z效率要高。 j ij ij j 则,IMAX=β。 若 IMAX,1,则令 l=1,跳转到 Step2,否则,算 分别用 z、z、z表示可能解矩阵、当前模式矩阵、最优中 tub 法停止,Z是最优中心,J是相应的最优解,。 b b 时的 Tabu搜 索结果 中心上的时间会减少,因此,最好采用变化的参数 IMAX。 所以,可以从某个值 IMAX 开始,直至中心不再更优时, 利用因子 减小 IMAX 的值直至小于 1, 这和算法停止的 β 判定是一致的。 每个中心的非优化位移的最大数目的减小因子,β,,如 聚 类 类 别 数表二 FCM算 法 结 果, 10 个 二 维 样 本, 有 为 4 时的 Tabu搜 索结果 说明,Pb:样本序号,Iter:Tabu 搜索的迭代次数,C-means:FCM 的 目标函 数值 ,Tabu:Tabu搜 索 的目标 函数 值 ,Dev: Tabu搜 索 的 目 标 函数值和 FCM 的目标函数值的相对误差,AV:平均迭代次数和平均 相对误差。 2 算法的参数 Tabu 搜索算法的各个参数都会对算法的过程产生不同 程度的影响。 Tabu搜 索算法的参数描述如下, Tabu 列表大小 ,NTLM,,Tabu 列表中有搜索的历史记 Tabu搜索 的目标函数值 和 FCM的 目标 函 数 值的 表三 录,这是 Tabu 搜索算法最明显的特征。 算法假定没有存储最 平均相对误差 后的 NTL 位移,因此,没有修正倒数第二个解。 NTLM 是可 以存储在列表中的最大位移的数,因此,NTLM 的值越大,搜 索的存储能力越强。 概率阈值,P,,可以利用概率阈值来检测 Tabu 位移和优 于 当 前 解 的 位 移 , 从 而 更 接 近 于 最 优 解 。 可 能 解 的 数 目 ,NH,, 在 Tabu 搜 索中 , 研 究 NH 个可 能 的 解 来 决 定 下 一 步 将要进行的位移。 因此,NH 的值越大,就需要检测更多的邻 近点,反之,则需要检测较少的邻近点。 每个中心的非优化位移的 数目 ,IMAX,, 这 个 参数 决 定 在对下一个可能的中心进行操作前允 许进 行 多 少次 非 优 化 说明 ,C: 聚 类类 别数 ,N: 待聚类 样本 数目 ,Set: 数据 集编号 **. 模糊加权指数, 为 时为硬聚类, 。 m: m1 上所述,如果进行了 IMAX 个非优化位移 ,就可以确定 下 一 个中心。 当所有的中心都确定后,利用因子减小 IMAX 的值 ,0,β,1,。 显而易见,β 的值越小,IMAX 的值下降到 1 以 下的速度越快,算法就可以通过越少的可能的中心点求得最 优解,但是,所求得的最优解与实际最优解的误差会越大。 m=1.2,N=10,C=时3 ,S 与平均相对误差的关系 图三 方向乘子,α,,α 是一个标量,表示在特定方向上找到可 能解的步长。 α 必须为正数,且值越大,邻近点与当前解的距 离越大。 当越来越接近最优解时,α 的值是可以变小的。 经实验验证,可得到参数的经验性取值, nNTLM,1/15* 可 能 性 方 向 的 总 数 , 或 是(3-1)/15 ,n 是 待 聚 类样本数目,, 图四 m=1.2,N=10,S=时2,,C 与平均相对误差的关系 P,0.97, 4 结束语 NH,0.1* 可能性方向的总数, 在本文中提出了一种求 解 模 糊聚 类 问 题全 局 最 优解 的 α, 对 每 个 中 心 进 行 操 作 时 , 对 α 初 始 化 为 1, 并 使 用 Tabu 搜索算法。 经过多次数据试验,证明 Tabu 搜索算法在 搜索全局最优解时是很有效的。 减小因子 0.8, IMAX, 初始化为 40, 在处理完所有中心后使用减小因子 0.75, 参考文献β,0.75。 [1]J.C.Dunn.A fuzzy relative of the ISODATA processa nd 3 数据实验 its usei n detecting compactw ell-separated clusters [J].J.Cyber- 采用如下数据集,有[-5,5]之间的随机数 x,=1,2…n。 分 ii 别 在 m=1.2,1.5,2.0,3.0,5.0,n=10,50,100,c=3,4,s=2,3,5 的 情 net,1974. 况下对算法进行实验验证。 表一、二是实验的结果,表三是总 [2]J.C.Bezdek. Fuzzy mathematics in pattern lcassification, 结性的结果。从表中的结果可以看出,Tabu 搜索算法比 FCM Ph.D.Dissertation, Departm-Entof Applied Mathematics. Cornel 算法的性能要好。 在图一:图四中可以看出 , 当 m 的值更 [J]l University, Ithaca, New York,1973. 小,待聚类样本数、样本维数更少,以及聚类类 别数 更 多 时 , [3]M.A.Ismail and S.Z.Selim. Fuzzy C-meanOs:p timality 算法的优势更加明显。 只有极少数情况下,FCM 算法得到的 of solutions ande ffective termination of the algorithm[J]. Pattern 聚类中心要更接近实际的中心。 但是,当 Tabu 搜索进行的时 间长一些后,依然会得到和 FCM 同样的解,这是因为这两种 Recognition,1986. 算法都得到了全局最优解, 即是说 FCM 算法没有陷入局部 [4]高新波.模糊聚类分析及其应用[M].西安:西安电子科 极值点或鞍点。 技大学出版社,2004. [5]李 安 贵 等. 模 糊 数 学 及 其 应 用[M]. 北 京 , 冶 金 工 业 出 版社,2006. 作者简介 孙银 慧 ,1984— ,, 女, 汉 族 , 湖 北荆 门 人 , 空军 工 程 大学 工程学院在读硕士研究生,主要研究方向,智能信息处理, 白振 兴 ,1953— ,, 男, 汉 族 , 山 西太 原 人 , 空军 工 程 大学 工程学院计算机应用技术教授 ,主要研究 方 向, 智 能 信 息处 N=10,S=2,C=3时 ,m 与平均相对误差的关系 图一 理, 董天 明 ,1982 ,, 男, 汉 族 , 山 西 太 原 人 ,94333部 队 94 — 分队。 图二 m=1.2,S=2,C=3时 ,N 与平均相对误差关系
/
本文档为【一种搜索模糊聚类全局最优解的Tabu算法】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。 本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。 网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。

历史搜索

    清空历史搜索