.452 智能系统学报 第12卷 对于阈值B,使用梯度下降的方法进行求解，通 过求偏导，得到B的梯度如下： n={y4∈D:y(∑w,d(,)-B>0)} V-GZn ③计算梯度： (8) k=1 7J=C∑a ken 为了满足约束条件：（∑，4(c)-B)> ④更新阈值：B=B-yVgJ: 0,参考w:的表示方式，则符合约束条件的y4的集合： ⑤更新集合p和p,使用算法1： m={beD(∑0,4()->0，重新 ⑥更新w。 定义了B的梯度公式： 至此，通过对训练集的距离学习，得到的权值 1n1 ω：，从而得到新的距离函数。通过数据集本身构成 J=c21 (9) 的辅助信息学习得到的混合距离，对数据集自身的 适应性更高，更有利于聚类效果的改善。 式中：n|表示集合n,的大小。使用梯度下降的 1.2时间复杂度分析 方法，求解B=B-yVJ,其中，y表示为梯度下降的 这个部分主要讨论所提算法的时间复杂度， 学习速率，设置y=。 HR-FCM算法的时间复杂度主要讨论的是混合距离 学习的时间复杂度。总的来说，混合距离学习的最 由于集合n不断改变，则等式进一步修改为 大时间复杂度为O(N2d),其中N表示训练数据集 如下形式： 中样本的个数，d表示样本的维度，p表示候选距离 0,iEp 的个数。算法的主要时间消耗在求解距离矩阵D (10) +CE,i∈p 中，时间复杂度为O(Ndp)。在迭代循环中，每一步 都有一个线性的时间复杂度，为O(max(V,n,))。 式中： 2 基于混合距离学习的鲁棒的FCM (11) 算法 具体的算法描述如下： 模糊C均值聚类算法(FCM),它是一种基于目 求解集合p*和p的算法，算法1如下： 标函数的聚类算法，是迄今为止应用最广泛、理论 1)初始化p=,Po={1,2,…,P},h=0; 最为完善的聚类算法。传统的FCM聚类算法使用 2)h=h+1,P=Pt+{i},P=Pi-,-{,其中i= 欧式距离作为距离度量函数导致其聚类性能和鲁 arg max 棒性较差。 icP-1 3)通过式(10)计算w,并判断其是否大于0。 针对传统FCM算法的缺点，近年来研究者们提 其中g=arg max{E}。如果ω，>0，则返回2)，否则 出了一些改进的FCM算法，例如：基于改进的模糊 划分的模糊C均值聚类算法(IFP-FCM)[1s)]和基于 设置p=p1Pi=P-,并终止。 改进的模糊划分的泛化的模糊C均值聚类算法 求解ω具体算法，算法2步骤如下： (GFP-FCM)[I6)。IFP-FCM算法是由Hoppner和 输入数据矩阵X∈R,惩罚因子C,成对约 Klawonn提出的一种改进的FCM聚类算法。FP 束(x。,xy),其中y={+1,-1) FCM算法通过对每个数据增加一个隶属约束函数， 输出距离权值ω，阈值B。 以降低算法对噪声的敏感性，增加了算法的鲁棒 步骤： 性。但是此算法仍然沿用的是传统的欧式距离作 1)初始化：o=w0=二，B=B(在初始权值下 为距离度量，受到IFP-FCM算法的启发，朱林等提 出了GIFP-FCM算法。 取距离的最大值作为B的初值)。 在此启发下，本文提出了一种基于混合距离学 2)计算距离矩阵：D(i,k), 习的鲁棒的FCM聚类算法，算法描述如下： 3)设置迭代步数：t=1, 假设给定一个样本集合X={x1,x2,…,x},其 4)循环，直至收敛： 中n是样本的个数，每一个样本是d维，预设聚类中 ①更新学习率：y=1/1,t=t+1 心的集合为V={y:,1≤i≤c},其中c表示类别数。 ②更新训练子集： 令u:表示第j个样本隶属于第i类的程度。则隶属对于阈值 β，使用梯度下降的方法进行求解，通 过求偏导，得到 β 的梯度如下： Ñβ Ｊ ＝ Ｃ ∑ ｎｐ ｋ ＝ １ ｙｋ （８） 为了满足约束条件： ｙｋ ∑ ｐ ｉ ＝ １ ωｉｄｉ ｘ ｋ ａ，ｘ ｋ ｂ ( ( ) － β) ＞ ０，参考 ωｉ 的表示方式，则符合约束条件的 ｙｋ 的集合： ｎ ＋ ｐ ＝ ｙｋ ∈ Ｄ：ｙｋ ∑ ｐ ｉ ＝ １ ωｉｄｉ ｘ ｋ ａ，ｘ ｋ ｂ { ( ( ) － β) ＞ ０} ，重新 定义了 β 的梯度公式： Ñβ Ｊ ＝ Ｃ∑ ｜ ｎｐ ＋｜ ｋ ＝ １ ｙｋ （９） 式中： ｎ ＋ ｐ 表示集合 ｎｐ ＋ 的大小。 使用梯度下降的 方法，求解 β′＝ β－γ Ñβ Ｊ，其中，γ 表示为梯度下降的 学习速率，设置 γ ＝ １ ｔ 。 由于集合 ｎｐ ＋ 不断改变，则等式进一步修改为 如下形式： ωｉ ＝ ０， ｉ ∈ ｐ － １ ｐ ＋ ＋ ＣＥｉ， ｉ ∈ ｐ ＋ ì î í ï ï ïï （１０） 式中： Ｅｉ ＝ ∑ ｎｐ ｋ ＝ １ ｙｋｄ ｋ ｉ － １ ｐ ＋ ∑ ｊ ＝ ｐ ＋∑ ｎｐ ｋ ＝ ｎ ＋ ｐ ｙｋｄ ｋ ｊ （１１） 具体的算法描述如下： 求解集合 ｐ ＋和 ｐ －的算法，算法 １ 如下： １）初始化 ｐ ＋ ＝∅，ｐ － ０ ＝{１，２，…，ｐ} ，ｈ ＝ ０； ２）ｈ ＝ ｈ＋１，ｐ ＋ ｈ ＝ ｐ ＋ ｈ－１ ＋{ｉ} ，ｐ － ｈ ＝ ｐ － ｈ－１ －{ｉ} ，其中 ｉ ＝ ａｒｇ ｍａｘ ｉ∈ｐ － ｈ－１ Ｅｉ { } ； ３）通过式（１０） 计算 ωｇ 并判断其是否大于 ０。 其中 ｇ ＝ ａｒｇ ｍａｘ ｉ∈ｐ ＋ ｈ Ｅｉ { } 。 如果 ωｇ ＞０，则返回 ２），否则 设置 ｐ ＋ ｈ ＝ ｐ ＋ ｈ－１ ，ｐ － ｈ ＝ ｐ － ｈ－１并终止。 求解 ω 具体算法，算法 ２ 步骤如下： 输入 数据矩阵 Ｘ∈Ｒ ｄ×Ｎ ，惩罚因子 Ｃ，成对约 束（ｘ ｋ ａ ，ｘ ｋ ｂ，ｙｋ），其中 ｙｋ ＝{＋１，－１} ； 输出 距离权值 ω，阈值 β。 步骤： １）初始化：ω＝ ω （０） ＝ １ ｐ ，β ＝ β （０） （在初始权值下 取距离的最大值作为 β 的初值）。 ２）计算距离矩阵：Ｄ（ｉ，ｋ）， ３）设置迭代步数：ｔ ＝ １， ４）循环，直至收敛： ①更新学习率：γ ＝ １ ／ ｔ，ｔ ＝ ｔ＋１ ②更新训练子集： ｎ ＋ ｐ ＝ ｙｋ ∈ Ｄ：ｙｋ ∑ ｐ ｉ ＝ １ ωｉｄｉ（ｘ ｋ ａ ，ｘ ｋ { ( ｂ） － β ＞ ０) } ③计算梯度： ∇ β Ｊ ＝ Ｃ∑ｋ∈ｎ ＋ ｐ ｙｋ ④更新阈值：β′＝ β－γ Ñβ Ｊ； ⑤更新集合 ｐ ＋和 ｐ － ，使用算法 １； ⑥更新 ω。 至此，通过对训练集的距离学习，得到的权值 ωｉ，从而得到新的距离函数。 通过数据集本身构成 的辅助信息学习得到的混合距离，对数据集自身的 适应性更高，更有利于聚类效果的改善。 １．２ 时间复杂度分析 这个部分主要讨论所提算法的时间复杂度， ＨＲ⁃ＦＣＭ 算法的时间复杂度主要讨论的是混合距离 学习的时间复杂度。 总的来说，混合距离学习的最 大时间复杂度为 Ｏ（Ｎ ２ ｄｐ），其中 Ｎ 表示训练数据集 中样本的个数，ｄ 表示样本的维度，ｐ 表示候选距离 的个数。 算法的主要时间消耗在求解距离矩阵 Ｄ 中，时间复杂度为 Ｏ（Ｎｄｐ）。 在迭代循环中，每一步 都有一个线性的时间复杂度，为 Ｏ（ｍａｘ（Ｎ，ｎｐ））。 ２ 基于混合距离学习的鲁棒的 ＦＣＭ 算法 模糊 Ｃ 均值聚类算法（ＦＣＭ），它是一种基于目 标函数的聚类算法，是迄今为止应用最广泛、理论 最为完善的聚类算法。 传统的 ＦＣＭ 聚类算法使用 欧式距离作为距离度量函数导致其聚类性能和鲁 棒性较差。 针对传统 ＦＣＭ 算法的缺点，近年来研究者们提 出了一些改进的 ＦＣＭ 算法，例如：基于改进的模糊 划分的模糊 Ｃ 均值聚类算法（ ＩＦＰ⁃ＦＣＭ） ［１５］ 和基于 改进的模糊划分的泛化的模糊 Ｃ 均值聚类算法 （ＧＩＦＰ⁃ＦＣＭ） ［１６］ 。 ＩＦＰ⁃ＦＣＭ 算法是由 Ｈöｐｐｎｅｒ 和 Ｋｌａｗｏｎｎ 提出的一种改进的 ＦＣＭ 聚类算法。 ＩＦＰ⁃ ＦＣＭ 算法通过对每个数据增加一个隶属约束函数， 以降低算法对噪声的敏感性，增加了算法的鲁棒 性。 但是此算法仍然沿用的是传统的欧式距离作 为距离度量，受到 ＩＦＰ⁃ＦＣＭ 算法的启发，朱林等提 出了 ＧＩＦＰ⁃ＦＣＭ 算法。 在此启发下，本文提出了一种基于混合距离学 习的鲁棒的 ＦＣＭ 聚类算法，算法描述如下： 假设给定一个样本集合 Ｘ ＝ ｘ１ ，ｘ２ ，…，ｘｎ { } ，其 中 ｎ 是样本的个数，每一个样本是 ｄ 维，预设聚类中 心的集合为 Ｖ ＝ ｖ{ ｉ，１≤ｉ≤ｃ} ，其中 ｃ 表示类别数。 令 ｕｉｊ表示第 ｊ 个样本隶属于第 ｉ 类的程度。 则隶属 ·４５２· 智 能 系 统 学 报 第 １２ 卷