·44 智能系统学报 第3卷 2)中心向量w迭代公式为 1方向相似性聚类算法(DSCM) 方向相似性聚类算法](directional similarity xfue wi= (4) based clustering algorithm,DSCM)定义一个新的 I∑xue,I 方向相似度量函数S(x,w)来度量方向数据向量 x和聚类中心向量w,的相似性：S(X,w)=e, 对于式(2)的极值，可以通过利用拉格朗日优化 理论推导出模糊方向相似性聚类算法(FDSC)关于 i=1,2,c代表类别下标，j=1,2,…n代表样本 隶属度的迭代公式(3)和中心向量w的迭代公 下标，k为尺度参数.S(x,w)值越大说明数据向量 式4)求解.与传统的FCM聚类算法有所不同，按 x与中心向量w,的相似度越高.DSCM算法定义 照FDSC算法定义，数据向量xy与中心向量w,的 聚类目标函数为 相似度越高其隶属度应越大，故式3)中·1/(m- 王sw=,P (1) 1)>0,即权重指数m<1,同时为了保证算法有较好 DSCM算法通过拉格朗日优化理论构造拉格 的收敛性，权重指数0<m<1.FDSC聚类思想可以 朗日优化目标函数，推导出中心向量w的迭代公 理解成通过中心向量和隶属度的迭代公式求解最优 式，对所有样本经过有限次迭代过程自组织的找到 聚类中心w,使得目标代价函数Jsc最大，即样本 所有不动点，进一步采用凝聚层次聚类算法(ag 间相似度总和最大 glomerative hierarchical clustering,AHC)分析不动 2.2基于竞争学习理论的隶属度目标函数的构造 点的层次数，并通过层次聚类图进一步确定最佳聚 竞争学习的学习规则分为WTA(winner-take- 类数以及类与类之间的关系 all)与WTM(winner-take-more)2种，分别称为 DSCM算法可以避免初始化敏感的问题，能够 “硬”竞争学习(hard competitive learning)与“软”竞 对方向性数据进行自组织，并利用AHC算法侦测 争学习(soft competitive learning)s),WTA规则 出最优的聚类数.但对于高维大量数据特别是文本 存在一个重要问题：对于不同初始值的节点，学习 数据，由于样本数很大，对所有样本无法通过 过程中可能存在死节点(dead nodes)或利用不充分 DSCM算法中的有限次迭代过程，自组织的找到所 (under-utilization)的现象.为此，研究人员提出了 有不动点.因此DSCM算法的应用受到了很大的局 WTM规则，通过引入模糊隶属度等方法，削弱了学 限性。 习对节点初始值的依赖，但同时也造成数据的获胜 节点不确定，使得部分节点可能偏离其实际的类数 2鲁棒的模糊方向相似性聚类算法 据.文献[6]提出了惩罚对手的竞争学习(RPCL), 2.1 模糊方向相似性聚类算法(FDSC) 对于数据集中的每个样本，不仅其获胜节点以一定 在方向相似性聚类算法的基础上，引入模糊隶 的学习速率向该数据集“靠近”，而且其竞争对手以 属度关系，建立如下模糊化的目标函数： 更小的学习速率（惩罚速率）被“推离”该数据集，从 JDc=∑∑Ge 而减小了对学习过程的干扰 (2 基于惩罚对手的竞争学习(RPCL)的思想，在 目标函数满足条件： 24=10< 模糊方向相似性聚类算法DSC的基础之上，文中 <n, 进一步提出鲁棒性的模糊方向相似性聚类算法 ∈0,1]，式中：m为权重指数，i=1,2,c代表 RFDSC.对于一个单独的样本点x,通过引入隶属 类别下标，j=1,2,,n代表样本下标，k为尺度 参数 度约束函数：f(n,b,)= 定理1在∑=1,0< <n,∈ 构造新的目标函数： 0,11,ww=1条件下，使FDSC算法的目标函数 ,王，Ge)取极值时： (5) 1)隶属度迭代公式为 下文将对式(5)中参数a(1≤≤的选择做说明. =(e)v”/∑e)vm.”. 3) 权重指数m∈0，)，目标函数满足∑4=1,0< 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net1 方向相似性聚类算法(DSCM) 方向相似性聚类算法[3 ] ( directional similarity2 based clustering algorit hm ,DSCM) 定义一个新的 方向相似度量函数 S ( xj , wi) 来度量方向数据向量 xj 和聚类中心向量 wi 的相似性 : S ( xj , wi) = e kx T j wi , i = 1 ,2 , …, c 代表类别下标 , j = 1 ,2 , …, n 代表样本 下标 , k 为尺度参数. S ( xj , wi) 值越大说明数据向量 xj 与中心向量 wi 的相似度越高. DSCM 算法定义 聚类目标函数为 J S = ∑ c i = 1 ∑ n j = 1 S ( xj ,wi) = ∑ c i = 1 ∑ n j =1 e kx T j wi . (1) DSCM 算法通过拉格朗日优化理论构造拉格 朗日优化目标函数 ,推导出中心向量 wi 的迭代公 式 ,对所有样本经过有限次迭代过程自组织的找到 所有不动点 , 进一步采用凝聚层次聚类算法 ( ag2 glomerative hierarchical clustering ,A HC) 分析不动 点的层次数 ,并通过层次聚类图进一步确定最佳聚 类数以及类与类之间的关系. DSCM 算法可以避免初始化敏感的问题 ,能够 对方向性数据进行自组织 ,并利用 A HC 算法侦测 出最优的聚类数. 但对于高维大量数据特别是文本 数据 , 由 于 样 本 数 很 大 , 对 所 有 样 本 无 法 通 过 DSCM 算法中的有限次迭代过程 ,自组织的找到所 有不动点. 因此 DSCM 算法的应用受到了很大的局 限性. 2 鲁棒的模糊方向相似性聚类算法 211 模糊方向相似性聚类算法(FDSC) 在方向相似性聚类算法的基础上 ,引入模糊隶 属度关系 ,建立如下模糊化的目标函数 : J FDSC = ∑ c i = 1 ∑ n j = 1 u m ij e kx T j wi . (2) 目标函数满足条件 : ∑ c i =1 uij = 1 ,0 < ∑ n j =1 uij < n , uij ∈[0 ,1 ] ,式中 : m为权重指数 , i = 1 ,2 , …, c代表 类别下标 , j = 1 ,2 , …, n 代表样本下标 , k 为尺度 参数. 定理 1 在 ∑ c i = 1 uij = 1 ,0 < ∑ n j =1 uij < n , uij ∈ [0 ,1 ] ,w T i wi = 1 条件下 ,使 FDSC 算法的目标函数 J FDSC = ∑ c i =1 ∑ n j = 1 u m ij (e kx T j wi ) 取极值时 : 1) 隶属度 uij迭代公式为 uij = (e kx T j wi ) - 1/ ( m - 1) / ∑ c i = 1 (e kx T j wi ) - 1/ ( m - 1) . (3) 2) 中心向量 wi 迭代公式为 wi = ∑ n j = 1 x T j u m ij e kx T j wi ‖∑ n j = 1 x T j u m ij e kx T j wi ‖ . (4) 对于式(2) 的极值 ,可以通过利用拉格朗日优化 理论推导出模糊方向相似性聚类算法 (FDSC) 关于 隶属度 uij 的迭代公式 (3) 和中心向量 wi 的迭代公 式(4) 求解. 与传统的 FCM 聚类算法有所不同 ,按 照 FDSC 算法定义 ,数据向量 xj 与中心向量 wi 的 相似度越高其隶属度应越大 ,故式 (3) 中 - 1/ ( m - 1) > 0 ,即权重指数 m < 1 ,同时为了保证算法有较好 的收敛性 ,权重指数 0 < m < 1. FDSC 聚类思想可以 理解成通过中心向量和隶属度的迭代公式求解最优 聚类中心 wi ,使得目标代价函数 J FDBC最大 ,即样本 间相似度总和最大. 212 基于竞争学习理论的隶属度目标函数的构造 竞争学习的学习规则分为 WTA (winner2take2 all) 与 WTM ( winner2take2more) 2 种 ,分别称为 “硬”竞争学习(hard competitive learning) 与“软”竞 争学习 (soft competitive learning) [425 ] . WTA 规则 存在一个重要问题 :对于不同初始值的节点 , 学习 过程中可能存在死节点 (dead nodes) 或利用不充分 (under2utilization) 的现象. 为此 ,研究人员提出了 WTM 规则 ,通过引入模糊隶属度等方法 ,削弱了学 习对节点初始值的依赖 ,但同时也造成数据的获胜 节点不确定 ,使得部分节点可能偏离其实际的类数 据. 文献[ 6 ]提出了惩罚对手的竞争学习 (RPCL) , 对于数据集中的每个样本 ,不仅其获胜节点以一定 的学习速率向该数据集“靠近”,而且其竞争对手以 更小的学习速率(惩罚速率) 被“推离”该数据集 ,从 而减小了对学习过程的干扰. 基于惩罚对手的竞争学习 ( RPCL) 的思想 ,在 模糊方向相似性聚类算法 FDSC 的基础之上 ,文中 进一步提出鲁棒性的模糊方向相似性聚类算法 RFDSC. 对于一个单独的样本点 xj ,通过引入隶属 度约束函数 : f ( u1 , u2 , …, uc ) = ∑ c i =1 ui ( u m- 1 i - 1) , 构造新的目标函数 : J RFDSC = ∑ c i = 1 ∑ n j = 1 u m ij (e kx T j wi ) - ∑ n j = 1 aj ∑ c i =1 uij ( u m- 1 ij - 1) . (5) 下文将对式(5) 中参数 aj (1 ≤j ≤n) 的选择做说明. 权重指数 m ∈(0 ,1) ,目标函数满足 ∑ c i = 1 uij = 1 ,0 < ·44 · 智 能 系 统 学 报 第 3 卷