第5期 程肠，等：基于局部保留投影的多可选聚类发掘算法 ·601· 够确保求出的新的子空间一定存在，并且解是全局 列空间中，可以用P×b计算，其中P被称为投影矩 最优的。 阵，P=A(ATA)AT。而(I-P)同样也是一个投 总的来说，本文所做的工作为：1)提出了一种新的 影矩阵，表示把投影到了AT的零空间中。文献[14] 算法RLPP,用于发掘多种可供选择的聚类结果：2) 中提出的2种算法把每个数据实例看作向量，利用 LPP根据同时满足质量和相异性要求的目标函数，生 了上述投影等式。文献[15]中的研究也与此相关， 成一个新的特征子空间，该特征子空间能够确保存在， 投影矩阵被应用于从所提供的聚类结果导出的距离 并且是全局最优的：3)通过实验，验证了RLPP的效 矩阵上。相比于文献[14]中的2种算法，这种方法 果，并与其他现有的算法进行了性能比较。 的优势在于能够解决数据维数比类别数小的情况。 1当前典型的可选聚类发掘方法 文献[16]提出的算法采用了不同的方法，通过对数 据的投影，使得在参考聚类结果中属于相同类别的 当前，有关发掘可选聚类结果的算法大体上可 数据点经过映射后在新的空间中拉开距离。这一方 以分为两类：一类直接利用原始数据空间寻找，另一 法与其他方法之间的不同之处在于它并不寻找一个 类则是基于投影（变形）子空间寻找。 全新的可选聚类，而是通过设定2个聚类结果之间 1.1基于全部原始数据空间 的相异度阈值，允许已知的聚类结果中的部分在可 这类研究利用的是整个原始特征空间，大多数 选聚类结果中保留下来。文献[17]和文献[18]中 研究的不同之处在于优化聚类质量和相异性的目标 所提出的算法基于谱聚类实现，前者表明可选聚类 函数不同。文献[4-9]中的研究可以归类为此类。 结果可以通过拉普拉斯矩阵不同的特征向量找到， 文献[4]提出了一种分层聚类(hierarchical cluste- 后者所提出的多重谱聚类(multiple spectral cluste- ring)算法COALA,该算法把从提供的聚类结果中生 ring,MSC)把子空间学习技术融入了谱聚类的过程 成的cannot--link约束项合并入它的每一个凝聚步骤 中，也就是说，MSC的目标函数是一个对偶函数 中，即尽可能多地满足这些cannot--ink约束项。在 (dual-function),通过最优化一项来修正另一项。另 文献[7]中，提出了CAMI算法，用于同时寻找两个 外，文献[I]提出了正则化PCA(regularized PCA, 可供选择的聚类结果。CAMI算法在混合模型下构 RPCA)和正则化的图方法(regularized graph-based 造聚类问题，优化了一个双重目标函数(dual-objec- method,RegGB)算法，其中RPCA与MSC一样，都 tive function),使得当两个混合模型之间的互信息 采用了HSIC,用于评估相关性，而RegGB算法则是 (反映了两种聚类结果之间的不同)最小时，对数似 基于图论构造。总的来说，RPCA和RegGB算法在 然（反映了聚类质量）最大。文献[6]提出的两种算 寻找可选聚类的能力上要优于之前所提到的算法， 法Dec-kmeans和Conv-EM也属于此类，这两种算法 但是RPCA算法只适用于线性结构的数据集，并且 分别改进了k-means和EM的目标函数，结合了一 其寻找可选聚类结果的能力有限，往往只能找到 个修正项，用于表示两种聚类结果之间的去相关信 个可选聚类，这些都极大地影响了它在使用上的灵 息。文献[8]中的工作采用了不同的方式，其原理 活性。因此，本文在文献[1]所提出的思路上，探索 来源于信息论，它的目标函数最大化全部数据实例 了一种新的算法，通过引入流形学习大大提高了其 和可选聚类结果类标之间的互信息(M),同时最小 发掘低维流形结构的能力和子空间学习能力，并通 化可选聚类和所提供的聚类结果之间的互信息。文 过核化扩大了其适用范围，使得其既适用于线性，同 献[8]中并没有基于传统的香农嫡，而是采用了 时又适用于非线性的数据集。 Renyi熵，以及相对应的二次互信息[2]，这种方法 在结合了非参数Parzen窗[]后使得MI基本近似。 2问题描述 这种双重优化聚类目标同样被用于文献[9]中，区 别在于文献「91使用的是迭代法，而不是文献「81中 假设数据集X={x1x2…xn},x:eR,即X是 所使用的分层技术。 dxn的矩阵，并提供一个使用任意聚类算法得到的 1.2基于投影子空间 参考聚类结果C)。则本文研究的目标为：发掘数 如果原数据空间的子空间与原数据空间是相互 据集X上的可供选择的聚类结果C2),并且C2)中 独立的（比如是正交的），那么根据该子空间得到的 的所有类别C2必须满足两个条件，U,C2=X和 聚类结果也与原聚类结果不同。文献[14-18]就是 C2nC2=0(i≠j)。除了与C)不同外，还要求 根据这样的理论基础提出了各自的算法。文献 C(2)的聚类质量较高。同理，若提供一组参考聚类 「14]由正交投影方法提出了两种寻找可供选择的 结果{C),C,…{,必须生成高质量的可供选择 聚类结果的算法。已知一个向量b,投影到矩阵的 的聚类结果C),且与之前所有的聚类结果{C)够确保求出的新的子空间一定存在，并且解是全局 最优的。 总的来说，本文所做的工作为：１）提出了一种新的 算法 ＲＬＰＰ，用于发掘多种可供选择的聚类结果；２） ＲＬＰＰ 根据同时满足质量和相异性要求的目标函数，生 成一个新的特征子空间，该特征子空间能够确保存在， 并且是全局最优的；３）通过实验，验证了 ＲＬＰＰ 的效 果，并与其他现有的算法进行了性能比较。 １ 当前典型的可选聚类发掘方法 当前，有关发掘可选聚类结果的算法大体上可 以分为两类：一类直接利用原始数据空间寻找，另一 类则是基于投影（变形）子空间寻找。 １．１ 基于全部原始数据空间 这类研究利用的是整个原始特征空间，大多数 研究的不同之处在于优化聚类质量和相异性的目标 函数不同。 文献［４⁃９］ 中的研究可以归类为此类。 文献［４］ 提出了一种分层聚类（ ｈｉｅｒａｒｃｈｉｃａｌ ｃｌｕｓｔｅ⁃ ｒｉｎｇ）算法 ＣＯＡＬＡ，该算法把从提供的聚类结果中生 成的 ｃａｎｎｏｔ⁃ｌｉｎｋ 约束项合并入它的每一个凝聚步骤 中，即尽可能多地满足这些 ｃａｎｎｏｔ⁃ｌｉｎｋ 约束项。 在 文献［７］中，提出了 ＣＡＭＩ 算法，用于同时寻找两个 可供选择的聚类结果。 ＣＡＭＩ 算法在混合模型下构 造聚类问题，优化了一个双重目标函数（ ｄｕａｌ⁃ｏｂｊｅｃ⁃ ｔｉｖｅ ｆｕｎｃｔｉｏｎ），使得当两个混合模型之间的互信息 （反映了两种聚类结果之间的不同）最小时，对数似 然（反映了聚类质量）最大。 文献［６］提出的两种算 法 Ｄｅｃ⁃ｋｍｅａｎｓ 和 Ｃｏｎｖ⁃ＥＭ 也属于此类，这两种算法 分别改进了 ｋ⁃ｍｅａｎｓ 和 ＥＭ 的目标函数，结合了一 个修正项，用于表示两种聚类结果之间的去相关信 息。 文献［８］中的工作采用了不同的方式，其原理 来源于信息论，它的目标函数最大化全部数据实例 和可选聚类结果类标之间的互信息（ＭＩ），同时最小 化可选聚类和所提供的聚类结果之间的互信息。 文 献［８］中并没有基于传统的香农熵［１０］ ，而是采用了 Ｒｅｎｙｉ 熵，以及相对应的二次互信息［１１⁃１２］ ，这种方法 在结合了非参数 Ｐａｒｚｅｎ 窗［１３］ 后使得 ＭＩ 基本近似。 这种双重优化聚类目标同样被用于文献［９］ 中，区 别在于文献［９］使用的是迭代法，而不是文献［８］中 所使用的分层技术。 １．２ 基于投影子空间 如果原数据空间的子空间与原数据空间是相互 独立的（比如是正交的），那么根据该子空间得到的 聚类结果也与原聚类结果不同。 文献［１４⁃１８］就是 根据这样的理论基础提出了各自的算法。 文献 ［１４］由正交投影方法提出了两种寻找可供选择的 聚类结果的算法。 已知一个向量 ｂ，投影到矩阵的 列空间中，可以用 Ｐ×ｂ 计算，其中 Ｐ 被称为投影矩 阵，Ｐ ＝ Ａ（Ａ ＴＡ ） －１Ａ Ｔ 。 而（Ⅰ－Ｐ） 同样也是一个投 影矩阵，表示把投影到了Ａ Ｔ 的零空间中。 文献［１４］ 中提出的 ２ 种算法把每个数据实例看作向量，利用 了上述投影等式。 文献［１５］中的研究也与此相关， 投影矩阵被应用于从所提供的聚类结果导出的距离 矩阵上。 相比于文献［１４］中的 ２ 种算法，这种方法 的优势在于能够解决数据维数比类别数小的情况。 文献［１６］提出的算法采用了不同的方法，通过对数 据的投影，使得在参考聚类结果中属于相同类别的 数据点经过映射后在新的空间中拉开距离。 这一方 法与其他方法之间的不同之处在于它并不寻找一个 全新的可选聚类，而是通过设定 ２ 个聚类结果之间 的相异度阈值，允许已知的聚类结果中的部分在可 选聚类结果中保留下来。 文献［１７］和文献［１８］中 所提出的算法基于谱聚类实现，前者表明可选聚类 结果可以通过拉普拉斯矩阵不同的特征向量找到， 后者所提出的多重谱聚类（ ｍｕｌｔｉｐｌｅ ｓｐｅｃｔｒａｌ ｃｌｕｓｔｅ⁃ ｒｉｎｇ， ＭＳＣ）把子空间学习技术融入了谱聚类的过程 中，也就是说， ＭＳＣ 的目标函数是一个对偶函数 （ｄｕａｌ⁃ｆｕｎｃｔｉｏｎ），通过最优化一项来修正另一项。 另 外，文献［ １］ 提出了正则化 ＰＣＡ（ ｒｅｇｕｌａｒｉｚｅｄ ＰＣＡ， ＲＰＣＡ）和正则化的图方法（ ｒｅｇｕｌａｒｉｚｅｄ ｇｒａｐｈ⁃ｂａｓｅｄ ｍｅｔｈｏｄ， ＲｅｇＧＢ）算法，其中 ＲＰＣＡ 与 ＭＳＣ 一样，都 采用了 ＨＳＩＣ，用于评估相关性，而 ＲｅｇＧＢ 算法则是 基于图论构造。 总的来说，ＲＰＣＡ 和 ＲｅｇＧＢ 算法在 寻找可选聚类的能力上要优于之前所提到的算法， 但是 ＲＰＣＡ 算法只适用于线性结构的数据集，并且 其寻找可选聚类结果的能力有限，往往只能找到一 个可选聚类，这些都极大地影响了它在使用上的灵 活性。 因此，本文在文献［１］所提出的思路上，探索 了一种新的算法，通过引入流形学习大大提高了其 发掘低维流形结构的能力和子空间学习能力，并通 过核化扩大了其适用范围，使得其既适用于线性，同 时又适用于非线性的数据集。 ２ 问题描述 假设数据集 Ｘ ＝ ｛ ｘ１ ｘ２… ｘｎ ｝，ｘｉ∈Ｒ ｄ ，即 Ｘ 是 ｄ×ｎ的矩阵，并提供一个使用任意聚类算法得到的 参考聚类结果 Ｃ （１） 。 则本文研究的目标为：发掘数 据集 Ｘ 上的可供选择的聚类结果 Ｃ （２） ，并且 Ｃ （２） 中 的所有类别 Ｃ （２） ｉ 必须满足两个条件，ＵｉＣ （２） ｉ ＝ Ｘ 和 Ｃ （２） ｉ ∩Ｃ （２） ｊ ＝Ø（∀ｉ≠ｊ）。 除了与 Ｃ （１）不同外，还要求 Ｃ （２）的聚类质量较高。 同理，若提供一组参考聚类 结果｛Ｃ （１） ，Ｃ （２） ，…｝，必须生成高质量的可供选择 的聚类结果 Ｃ （ｋ） ，且与之前所有的聚类结果｛Ｃ （１） ， 第 ５ 期 程旸，等：基于局部保留投影的多可选聚类发掘算法 ·６０１·