第5期 程肠，等：基于局部保留投影的多可选聚类发掘算法 ·603· 表示元素值全为1的列向量。r(·)表示矩阵的 此，P(X)LP(X)T+p(X)HL,Hp(X)'是实对称矩 迹。 阵。作为一个特征分解问题，A的最优解由前k个 为了表示简单，使用HSICox,)代替HSIC(2.F,, 最小非零特征值对应的特征向量构成，即A= 表示随机变量X和(x)=A'x,也就是X和Y之间 [a,a2…&]。下一步，可以使用k-means算法 的依赖性。 对子空间A进行聚类，得到可供选择的聚类结 假设有8个数据{x1,x2,…,xg,{,其中x,和x2, 果C2)。 x3和x4,x3和x6,x,和xg分别为一类。则向量y1= 可以看到，(X)HL,He(X)I直接影响了LPP y2=(1000),y3=y4=(0100),y5=y6= 算法中(X)Lp(X)T项，也就是说，可以把两个聚 (0010)T,y,=yg=(0001)'。矩阵Y的每一行对 类结果之间的独立性看作添加的约束项。同时，通 应一个y。L,是一个8×8的矩阵，由：和y的点 过添加更多的HSIC项，将算法推广可以找到更多 积构成。K是一个8×8的矩阵，表示(x:)和(x) 可供选择的聚类结果。 之间的相似度。同时注意，根据定义，H是一个n×n 举例来说，在寻找第3个可供选择的聚类结果 (在本例中是8×8)的常数矩阵，每行每列的和都等 C3)时，只要提供之前找到的两个聚类结果C)和 于0。因此，在上述示例中，每一行（列）都包含7个 C2),并把式(6)中的HSIC(ax.c)一项替换为 (安)和1个 HSIC(ATx.c)+HSIC(ax.c2,即可。因此只要在式 (8)中使用A'XHL,HXA+A'XHL2HXA,即直接 5基于局部保留投影的多可选聚类发 使用AXH(L,:+L,2）HXA代替AXHL,HXA。 掘算法 也就是说，使用(L,+L,2)代替了L,其他矩阵保持 不变即可。 由于通过HSIC,)可以自然地评估结构很复 RLPP算法描述如下： 杂的样本X和Y之间的相关性，因此结合HSICo.” 1)输入数据集X;一个X上的参考聚类结果 对LPP的目标函数进行修改。要求是转换矩阵A C。 必须能够发掘嵌入在高维数据中的低维流形结构， 2)输出一个数据集X上可供选择的参考聚类 并且与已知的聚类结果C)完全独立。换句话说， 结果C2。 在所有与已经存在的聚类结果C)不同的子空间 3)算法流程： 中，要选出能够最好地保持高维数据流形结构的子 ①计算L,L,=(y:y〉，其中y:是一个二元向 空间。因此，改进LPP的目标函数如下： 量，表示C)中x,的类标签的编码。 A=argmin A'XLX'A HSIC(ATX.c(D)= ②计算H=1-e.c。 argmin A XLX'A tr(HKHL,) (6) 式中：A表示A的最佳解，且由迹的性质可知 ③计算权值矩阵W,如果x是x:的k近邻点， r(HKHL,)=r(KHL,H)。不同的核函数在计算变 那么W,=exp- x-12 (t∈R),否则W,=0。 量之间的独立性时结果不同，这里采用线性核函数， t 映射函数定义为：(x)=ATx,因此，K= ④计算矩阵D,Da=∑W,计算拉普拉斯矩阵 (p(X),P(X)〉=YAAX。即 L,L=D-W。 ATXLXA tr(HKHL,)= ⑤使用高斯核计算核矩阵K,K=9(x)'· AXLXA+AXHL HX'A= p()。 AT (XLX+XHL HX)A (7) ⑥分解核矩阵K,K=PP,根据P(X)=AP 将数据集合X映射到高维特征空间中后，就可 得到(X)。 以最终得到(X)=[p(x)(x2)…(xn)]。其 ⑦计算(X)LP(X)'+(X)HL,H(X)的特 中，核矩阵K的元素为K=p(x:)I·(x)。即： 征值和特征向量。 A.m=A((X)L(X)+(X)HL H (X))A ⑧按特征值从小到大的顺序对特征向量排序。 (8) ⑨选择前k个最小的特征值对应的特征向量， 因为H和L,都是对称矩阵，所以 即A=[a0a1…ak-1Jo (X)HL,H(X)'也是对称矩阵，同样，因为L是 ①c2)-k-means(A'e(X))。 对称矩阵，所以P(X)L(X)T也是对称矩阵。因 RLPP算法的时间复杂度完全由计算最近邻矩表示元素值全为 １ 的列向量。 ｔｒ（·） 表示矩阵的 迹。 为了表示简单，使用 ＨＳＩＣ（Ｘ，Ｙ） 代替 ＨＳＩＣ（Ｚ，Ｆ，Ｇ） ， 表示随机变量 Ｘ 和 φ（ｘ）＝ Ａ Ｔ ｘ，也就是 Ｘ 和 Ｙ 之间 的依赖性。 假设有 ８ 个数据｛ｘ１ ，ｘ２ ，…，ｘ８ ，｝，其中 ｘ１ 和 ｘ２ ， ｘ３ 和 ｘ４ ，ｘ５ 和 ｘ６ ，ｘ７ 和 ｘ８ 分别为一类。 则向量 ｙ１ ＝ ｙ２ ＝ （１ ０ ０ ０） Ｔ ， ｙ３ ＝ ｙ４ ＝ （０ １ ０ ０） Ｔ ， ｙ５ ＝ ｙ６ ＝ （０ ０ １ ０） Ｔ ，ｙ７ ＝ ｙ８ ＝ （０ ０ ０ １） Ｔ 。 矩阵 Ｙ 的每一行对 应一个 ｙｉ。 Ｌｙ 是一个 ８×８ 的矩阵，由 ｙｉ 和 ｙｊ 的点 积构成。 Ｋ 是一个 ８×８ 的矩阵，表示 φ（ｘｉ）和φ（ｘｊ） 之间的相似度。 同时注意，根据定义，Ｈ 是一个 ｎ×ｎ （在本例中是 ８×８）的常数矩阵，每行每列的和都等 于 ０。 因此，在上述示例中，每一行（列）都包含 ７ 个 （－ １ ８ ）和 １ 个 ７ ８ 。 ５ 基于局部保留投影的多可选聚类发 掘算法 由于通过 ＨＳＩＣ（Ｘ，Ｙ） 可以自然地评估结构很复 杂的样本 Ｘ 和 Ｙ 之间的相关性，因此结合 ＨＳＩＣ（Ｘ，Ｙ） 对 ＬＰＰ 的目标函数进行修改。 要求是转换矩阵 Ａ 必须能够发掘嵌入在高维数据中的低维流形结构， 并且与已知的聚类结果 Ｃ （１） 完全独立。 换句话说， 在所有与已经存在的聚类结果 Ｃ （１） 不同的子空间 中，要选出能够最好地保持高维数据流形结构的子 空间。 因此，改进 ＬＰＰ 的目标函数如下： Ａｏｐｔ ＝ ａｒｇｍｉｎ Ａ ＴＸＬＸ ＴＡ ＋ ＨＳＩＣ（ＡＴＸ，Ｃ（１）） ＝ ａｒｇｍｉｎ Ａ ＴＸＬＸ ＴＡ ＋ ｔｒ ＨＫＨＬｙ ( ) （６） 式中：Ａｏｐｔ 表示 Ａ 的最佳解， 且由迹的性质可知 ｔｒ ＨＫＨＬｙ ( ) ＝ ｔｒ(ＫＨＬｙＨ) 。 不同的核函数在计算变 量之间的独立性时结果不同，这里采用线性核函数， 映射 函 数 定 义 为： φ（ｘ） ＝ Ａ Ｔ ｘ ， 因 此， Ｋ ＝ 〈φ（Ｘ），φ（Ｘ）〉 ＝ Ｘ ＴＡＡ ＴＸ 。 即 Ａ ＴＸＬＸ ＴＡ ＋ ｔｒ ＨＫＨＬｙ ( ) ＝ Ａ ＴＸＬＸ ＴＡ ＋ Ａ ＴＸＨＬｙＨＸ ＴＡ ＝ Ａ Ｔ ＸＬＸ Ｔ ＋ ＸＨＬｙＨＸ Ｔ ( ) Ａ （７） 将数据集合 Ｘ 映射到高维特征空间中后，就可 以最终得到 φ（Ｘ）＝ ［φ（ｘ１ ） φ（ｘ２ ） … φ（ｘｎ ）］。 其 中，核矩阵 Ｋ 的元素为 Ｋｉｊ ＝φ （ｘｉ） Ｔ·φ（ｘｊ）。 即： Ａｏｐｔ ＝ Ａ Ｔ （φ（Ｘ）Ｌφ （Ｘ） Ｔ ＋ φ（Ｘ）ＨＬｙＨφ （Ｘ） Ｔ ）Ａ （８） 因 为 Ｈ 和 Ｌｙ 都 是 对 称 矩 阵， 所 以 φ（Ｘ）ＨＬｙＨφ （Ｘ） Ｔ也是对称矩阵，同样，因为 Ｌ 是 对称矩阵，所以 φ(Ｘ) Ｌφ （Ｘ） Ｔ 也是对称矩阵。 因 此，φ（Ｘ）Ｌφ （Ｘ） Ｔ ＋φ（Ｘ）ＨＬｙＨφ （Ｘ） Ｔ 是实对称矩 阵。 作为一个特征分解问题，Ａｏｐｔ的最优解由前 ｋ 个 最小 非 零 特 征 值 对 应 的 特 征 向 量 构 成， 即 Ａ ＝ ［α１ α２… αｋ ］。 下一步，可以使用 ｋ⁃ｍｅａｎｓ ［１９］ 算法 对子空间 Ａ 进行聚类， 得到可供选择的聚类结 果 Ｃ （２） 。 可以看到，φ（Ｘ）ＨＬｙＨφ （Ｘ） Ｔ 直接影响了 ＬＰＰ 算法中 φ（Ｘ）Ｌφ （Ｘ） Ｔ 项，也就是说，可以把两个聚 类结果之间的独立性看作添加的约束项。 同时，通 过添加更多的 ＨＳＩＣ 项，将算法推广可以找到更多 可供选择的聚类结果。 举例来说，在寻找第 ３ 个可供选择的聚类结果 Ｃ （３）时，只要提供之前找到的两个聚类结果 Ｃ （１） 和 Ｃ （２） ，并 把 式 （ ６ ） 中 的 ＨＳＩＣ（ＡＴＸ，Ｃ（１）） 一 项 替 换 为 ＨＳＩＣ（ＡＴＸ，Ｃ（１） ） ＋ ＨＳＩＣ（ＡＴＸ，Ｃ（２）） 即可。 因此只要在 式 （８）中使用 Ａ ＴＸＨＬｙ１ＨＸ ＴＡ＋Ａ ＴＸＨＬｙ２ＨＸ ＴＡ，即直接 使用 Ａ ＴＸＨ （ Ｌｙ１ ＋ Ｌｙ２ ） ＨＸ ＴＡ 代替 Ａ ＴＸＨＬｙＨＸ ＴＡ。 也就是说，使用（Ｌｙ１ ＋Ｌｙ２ ）代替了 Ｌｙ，其他矩阵保持 不变即可。 ＲＬＰＰ 算法描述如下： １）输入 数据集 Ｘ；一个 Ｘ 上的参考聚类结果 Ｃ （１） 。 ２）输出 一个数据集 Ｘ 上可供选择的参考聚类 结果 Ｃ （２） 。 ３）算法流程： ①计算 Ｌｙ，Ｌｙ ＝ 〈 ｙｉ，ｙｊ〉，其中 ｙｉ 是一个二元向 量，表示 Ｃ （１）中 ｘｉ 的类标签的编码。 ②计算 Ｈ＝ Ｉ－ １ ｎ ｅｎ ｅ Ｔ ｎ 。 ③计算权值矩阵 Ｗ，如果 ｘｊ 是 ｘｉ 的 ｋ 近邻点， 那么 Ｗｉｊ ＝ ｅｘｐ－ ‖ｘｉ －ｘｊ‖２ ｔ （ｔ∈Ｒ），否则 Ｗｉｊ ＝ ０。 ④计算矩阵 Ｄ， Ｄｉｉ ＝ ∑ ｊ Ｗｉｊ，计算拉普拉斯矩阵 Ｌ，Ｌ ＝ Ｄ － Ｗ 。 ⑤使用高斯核计算核矩阵 Ｋ，Ｋｉｊ ＝ φ （ｘｉ） Ｔ · φ（ｘｊ）。 ⑥分解核矩阵 Ｋ，Ｋ ＝ Ｐ ＴΛＰ，根据 φ（Ｘ） ＝ Λ １ ２ Ｐ 得到 φ（Ｘ）。 ⑦计算 φ（Ｘ）Ｌφ （Ｘ） Ｔ ＋φ（Ｘ）ＨＬｙＨφ（Ｘ） Ｔ 的特 征值和特征向量。 ⑧按特征值从小到大的顺序对特征向量排序。 ⑨选择前 ｋ 个最小的特征值对应的特征向量， 即 Ａ＝ ［ａ０ ａ１… ａｋ－１ ］。 ⑩Ｃ （２）＝ ｋ⁃ｍｅａｎｓ（Ａ Ｔφ（Ｘ））。 ＲＬＰＰ 算法的时间复杂度完全由计算最近邻矩 第 ５ 期 程旸，等：基于局部保留投影的多可选聚类发掘算法 ·６０３·