第6期 郭瑛洁，等：基于最大间隔理论的组合距离学习算法 .847. 方法： 多类数据集。各个数据集的信息如表1所示。 1)初始化：w=w; 表1实验中使用的数据集信息 2)计算距离矩阵：D(i,k); Table 1 List of data sets 3)计算二次规划参数H和f: 数据集 样本数 特征数 类别数 H= breast 683 10 2 点（店三4dow小-日（含三4）+ sonar 208 60 2 wdbe 569 30 2 1A宫d heart 270 2 2 wine 178 13 3 4)利用二次规划优化算法求解得到最优解：α·= 1473 9 3 [aiag…ar]T; cme thyroid 215 3 5)计算集合p和p:算法1： 6)利用式(15)计算ω。 segment 2310 19 7 在数据集的选择上基于以下考虑：首先，这些数 3实验 据集的特征数和类别数都各不相同。另外，这些数 为了与传统CM算法之间有可比性，本文将简 据集是机器学习研究中被广泛使用的基准数据集， 单的以学习得到的距离函数替换传统FCM算法中 因而具有代表性。最后，由于数据集均为真实数据 的欧式距离。根据传统FCM算法的实现方法，本文 集，因此可以检验算法在真实应用中是否可行。 将通过以下步骤实现聚类： 文中所有实验均在MATLAB平台下进行，所有 训练数据集和测试数据集均先归一化至[0,1]内。 1)初始化隶属度矩阵U,使得 ∑4g=1,j= 带有边信息的训练集将通过如下方法产生：首先，随 1,2,…,n,u∈[0,1]。 机选取数据集的10%组成一个子集。然后，根据子 集中样本点带有的类标是否相同来生成约束对 2)计算聚类中心：c:= (x。,xy)集合。其中，类标相同的成对约束为正 约束对，反之为负约束对。将取个数相同的正负约 =1 束对组成训练集。 3)计算价值函数： 在组合距离分量的选择上，本文依据第2节的 94 J=) 理论，在实验中选取如下10个距离度量进行组合： d(x,y)=(x-y)1(x-y) 当其相对于上次价值函数值的改变量小于某个 阈值时，算法停止。 4）=(x-)rx-y) 4)更新隶属度矩阵： 1 d0x=21s- uj= =1 2/(m-1) d(x,y)=】 其中对于样本点x:,它与聚类中心c:之间的距 -31x 离使用如下公式计算： d6(x,y）=1-e2 d,=u,d(x,c） d(x,)=1-e 将上述聚类算法记为基于组合距离(hybrid dis- d(x,）=1-e tance)的FCM聚类算法(HDFCM)。 d,(x,)=1-eg 本节将上述HDCM算法与已有的经典距离学 dio(x,y)=1-e-lx12 习算法进行对比与分析。 在使用组合距离进行聚类的算法中，本文将依 3.1实验设置 据数据集的类别数给定聚类数目，初始隶属度矩阵 本文使用了8个来自UCI机器学习数据库的 随机生成。为了保证可比性，实验中所有的对比算 真实数据集。其中4个为二类数据集，其余4个为 法将使用相同的初始隶属度矩阵，训练集和其他参方法： １）初始化： ω ＝ ω （０） ； ２）计算距离矩阵： Ｄ（ｉ，ｋ） ； ３）计算二次规划参数 Ｈ 和 ｆ ： Ｈ ＝ ∑ ｐ ｉ ＝ １ ∑ ｎ ｑ ＝ １∑ ｎ ｒ ＝ １ ｄｉ，ｑｄｉ，ｒ ｙｑ ｙ ( ｒ) － １ ｄ ∑ ｐ ｉ ＝ １ ∑ ｎ ｋ ＝ １ ｙ ( ｋｄｉ，ｋ ) ２ ＋ ｙ ２ ｋ ｆ ＝ １ ｐ ∑ ｐ ｉ ＝ １ ∑ ｎ ｋ ＝ １ ｙｋｄｉ，ｋ ４）利用二次规划优化算法求解得到最优解： α ∗ ＝ ［α ∗ １ α ∗ ２ … α ∗ ｎ ］ Ｔ ； ５）计算集合 ｐ ＋ 和 ｐ － ：算法 １； ６）利用式（１５）计算 ω 。 ３ 实验 为了与传统 ＦＣＭ 算法之间有可比性，本文将简 单的以学习得到的距离函数替换传统 ＦＣＭ 算法中 的欧式距离。 根据传统 ＦＣＭ 算法的实现方法，本文 将通过以下步骤实现聚类： １）初始化隶属度矩阵 Ｕ ，使得 ∑ ｃ ｉ ＝ １ ｕｉｊ ＝ １，∀ｊ ＝ １，２，…，ｎ，ｕｉｊ ∈ [０，１] 。 ２）计算聚类中心： ｃｉ ＝ ∑ Ｎ ｊ ＝ １ ｕ ｍ ｉｊ ｘｊ ∑ Ｎ ｊ ＝ １ ｕ ｍ ｉｊ 。 ３）计算价值函数： Ｊ ＝ ∑ ｃ ｉ ＝ １ ∑ Ｎ ｊ ＝ １ ｕ ｍ ｉｊ ｄ ２ ｉｊ 当其相对于上次价值函数值的改变量小于某个 阈值时，算法停止。 ４）更新隶属度矩阵： ｕｉｊ ＝ １ ∑ ｃ ｋ ＝ １ ｄｉｊ ｄｋｊ æ è ç ö ø ÷ ２／ (ｍ－１ ) 其中对于样本点 ｘｊ ，它与聚类中心 ｃｉ 之间的距 离使用如下公式计算： ｄｉｊ ＝ ∑ ｐ ｒ ＝ １ ωｒｄｒ（ｘｊ，ｃｉ） 将上述聚类算法记为基于组合距离（ｈｙｂｒｉｄ ｄｉｓ⁃ ｔａｎｃｅ）的 ＦＣＭ 聚类算法（ＨＤＦＣＭ）。 本节将上述 ＨＤＦＣＭ 算法与已有的经典距离学 习算法进行对比与分析。 ３．１ 实验设置 本文使用了 ８ 个来自 ＵＣＩ 机器学习数据库的 真实数据集。 其中 ４ 个为二类数据集，其余 ４ 个为 多类数据集。 各个数据集的信息如表 １ 所示。 表 １ 实验中使用的数据集信息 Ｔａｂｌｅ １ Ｌｉｓｔ ｏｆ ｄａｔａ ｓｅｔｓ 数据集 样本数 特征数 类别数 ｂｒｅａｓｔ ６８３ １０ ２ ｓｏｎａｒ ２０８ ６０ ２ ｗｄｂｃ ５６９ ３０ ２ ｈｅａｒｔ ２７０ １２ ２ ｗｉｎｅ １７８ １３ ３ ｃｍｃ １ ４７３ ９ ３ ｔｈｙｒｏｉｄ ２１５ ５ ３ ｓｅｇｍｅｎｔ ２ ３１０ １９ ７ 在数据集的选择上基于以下考虑：首先，这些数 据集的特征数和类别数都各不相同。 另外，这些数 据集是机器学习研究中被广泛使用的基准数据集， 因而具有代表性。 最后，由于数据集均为真实数据 集，因此可以检验算法在真实应用中是否可行。 文中所有实验均在 ＭＡＴＬＡＢ 平台下进行，所有 训练数据集和测试数据集均先归一化至 [０，１] 内。 带有边信息的训练集将通过如下方法产生：首先，随 机选取数据集的 １０％组成一个子集。 然后，根据子 集中样本点带有的类标是否相同来生成约束对 ｘ ｋ ａ ，ｘ ｋ ｂ，ｙｋ ( ) 集合。 其中，类标相同的成对约束为正 约束对，反之为负约束对。 将取个数相同的正负约 束对组成训练集。 在组合距离分量的选择上，本文依据第 ２ 节的 理论，在实验中选取如下 １０ 个距离度量进行组合： ｄ１（ｘ，ｙ） ＝ （ｘ － ｙ） Ｔ Ｉ（ｘ － ｙ） ｄ３（ｘ，ｙ） ＝ （ｘ － ｙ） Ｔ ３Ｉ σ ２ （ｘ － ｙ） ｄ４（ｘ，ｙ） ＝ ∑ ｄ ｉ ＝ １ ｘｉ － ｙｉ ｄ５（ｘ，ｙ） ＝ ∑ ｄ ｉ ＝ １ ｘｉ － ｙｉ σ ２ ｄ６（ｘ，ｙ） ＝ １ － ｅ －３‖ｘ－ｙ‖２ σ ２ ｄ７（ｘ，ｙ） ＝ １ － ｅ －‖ｘ－ｙ‖２ σ ２ ｄ８（ｘ，ｙ） ＝ １ － ｅ －‖ｘ－ｙ‖２ ３σ ２ ｄ９（ｘ，ｙ） ＝ １ － ｅ －‖ｘ－ｙ‖２ ５σ ２ ｄ１０（ｘ，ｙ） ＝ １ － ｅ －‖ｘ－ｙ‖２ 在使用组合距离进行聚类的算法中，本文将依 据数据集的类别数给定聚类数目，初始隶属度矩阵 随机生成。 为了保证可比性，实验中所有的对比算 法将使用相同的初始隶属度矩阵，训练集和其他参 第 ６ 期 郭瑛洁，等：基于最大间隔理论的组合距离学习算法 ·８４７·