第5期 林大华，等：稀疏样本自表达子空间聚类算法 ·699. 数。但值得注意的是，D,和D依赖于Z,因此也是未 是式(3)的一个全局最优解，因此，算法2可将问题 知的。根据文献[11-13]，本文提出了一种迭代算法 (3)收敛到全局最优解。另外，在每一次迭代时都 去求解这个问题。 有封闭形式的解，因此我们的算法收敛非常快。 算法2目标函数优化算法 4实验分析与讨论 输入数据集X; 输出Z()E Rkn; 4.1实验数据集及评价指标 初始化Z)∈R",t=1: 本文算法通过MATLAB语言编程，且所有实验 do 都是在win7系统下的MATLAB2014软件上运行测 试。实验用到的数据集介绍如下。 1)计算对角矩阵D.o(1≤i≤n)和Do其中 Hopkins155[1]数据集被广泛用来测试各种子 D,的第k个对角元素为1 Do的第k个对 空间聚类算法。该数据集由156个视频序列组成， 2|Z0 一个序列对应一个数据集，所以其共有156个数据 角元素为 1 2I(Zo)*I, 集，并且每个序列中包含2或3个运动物体目标。 Jaffe[16]数据集由日本ATR表情识别研究协会 2)For每个i(1≤i≤n),计算 提供，该数据集包含10个人的213张表情图像，每 Z(D)=(XX+A D(+A2 D()-XX 张表情图像经过预处理被裁剪为32像素×32像素 3)t=t+1: 大小的尺度。 }until收敛。 USPs1刊数据集是由美国国家邮政局提供， 由上述算法2的描述知，优化目标函数的关键 数据集含有9298个0~10的手写数字数据集，每个 是目标值Z)要在迭代中收敛。下面证明目标函 手写数字数据经预处理都被裁剪为16像素×16像 数(2)的目标值在每一次迭代中都会减小。根据算 素大小的尺度。用每个数字的前100个图像进行 法2的第2步，可得 实验。 Z(D)minTr (X -XZ)"(-XZ) ORLi)数据集是由剑桥Olivetti实验室提供， AD Z+ATr Z Dz 数据集包含40人的共400张面部图像，每张人脸数 (5) 据经预处理被裁剪为16像素×16像素大小的尺度。 由式(5)，可得 为了验证算法的性能，将目前较好的子空间聚 Tr (X-XZ(D))T(X-XZ(D))+ 类算法LSR、LRR和SSC与本文算法进行对比实 A宫(2)rnzw+ 验。为了保证算法的公平性，所有算法都没有对数 据进行后期处理。 A2Tr(Z+)TDZ+1)≤ 子空间聚类的重要挑战是处理存在于数据中的 Tr (X-XZ()(X-XZ())+ 错误。因此，本文将子空间聚类错误率作为衡量各 A()D()D 个算法性能的评价标准。其中，错误率越小，子空间 聚类效果越好：反之，则越差。其定义为 于是，可推导出 Tr (X-XZ(+D)T(X-XZ(D)+ 子空间聚类错误率=错误分类的样本数 样本总数 A豆三z1+A三 I(Z+)I2≤ 4.2实验结果与分析 4.2.1 Hopkins155数据集上的实验 Tr(X-XZ)T(X-XZo)》 由于Hopkins155数据集包含156个不同的数 A三含1四 ,‖(Zo)I2 据集，根据文献[19]，本文将156个数据集中的子 空间聚类错误率的最大值(Max)、均值(Mean)和中 根据文献[14]，对于任意向量Z和Z。,有 值(Median)以及标准差(Std)作为评价指标。对 z且≤1z21ZT 1Z,1212Z12 IZoll 。由以上分 LSR,LRR,SSC以及本文算法SSR_SC在该数据集 进行了对比，实验结果如表1所示。 析可知，算法2中的目标值在每一次迭代中都会减 通过分析表1可知，在Hopkins155数据集上， 小。ZD(1≤i≤n)和D在收敛处满足等式 本文提出的SSR_SC比LSR、LRR和SSC获得了更 (5),且目标函数(2)是凸函数，于是此时得到的Z 好的子空间聚类效果。具体地，SSR_SC与LSR算数。 但值得注意的是，Ｄｉ 和Ｄ ～ 依赖于 Ｚ，因此也是未 知的。 根据文献［１１⁃１３］，本文提出了一种迭代算法 去求解这个问题。 算法 ２ 目标函数优化算法 输入 数据集 Ｘ； 输出 Ｚ （ｔ）∈Ｒ ｎ×ｎ ； 初始化Ｚ （１）∈Ｒ ｎ×ｎ ，ｔ ＝ １； ｄｏ｛ １）计算对角矩阵Ｄｉ （ｔ） （ １≤ｉ≤ｎ） 和Ｄ ～ （ｔ） 其中 Ｄｉ （ｔ）的第 ｋ 个对角元素为 １ ２ Ｚ （ｔ） ｋｉ ，Ｄ ～ （ｔ） 的第 ｋ 个对 角元素为 １ ２ ‖（Ｚ （ｔ） ） ｋ‖２ ； ２）Ｆｏｒ 每个 ｉ（１≤ｉ≤ｎ），计算 Ｚ （ｔ＋１） ｉ ＝ （Ｘ ＴＸ ＋ λ１ Ｄ （ｔ） ｉ ＋ λ２ Ｄ ～ （ｔ） ） －１ Ｘ ＴＸ ３）ｔ ＝ ｔ＋１； ｝ｕｎｔｉｌ 收敛。 由上述算法 ２ 的描述知，优化目标函数的关键 是目标值Ｚ （ｔ＋１） ｉ 要在迭代中收敛。 下面证明目标函 数（２）的目标值在每一次迭代中都会减小。 根据算 法 ２ 的第 ２ 步，可得 Ｚ （ｔ＋１） ＝ ｍｉｎ Ｚ Ｔｒ （Ｘ － ＸＺ） Ｔ （Ｘ － ＸＺ） ＋ λ１∑ ｎ ｉ ＝ １ Ｚ Ｔ ｉ Ｄ （ｔ） ｉ Ｚｉ ＋ λ２Ｔｒ Ｚ Ｔ Ｄ ～ （ｔ）Ｚ （５） 由式（５），可得 Ｔｒ （Ｘ － ＸＺ （ｔ＋１） ） Ｔ （Ｘ － ＸＺ （ｔ＋１） ） ＋ λ１∑ ｎ ｉ ＝ １ （Ｚ （ｔ＋１） ｉ ） Ｔ Ｄ （ｔ） ｉ Ｚ （ｔ＋１） ｉ ＋ λ２Ｔｒ （Ｚ （ｔ＋１） ） Ｔ Ｄ ～ （ｔ） Ｚ （ｔ＋１） ≤ Ｔｒ （Ｘ － ＸＺ （ｔ） ） Ｔ （Ｘ － ＸＺ （ｔ） ） ＋ λ１∑ ｎ ｉ ＝ １ （Ｚ （ｔ） ｉ ） Ｔ Ｄ （ｔ） ｉ Ｚ （ｔ） ｉ ＋ λ２Ｔｒ （Ｚ （ｔ） ） Ｔ Ｄ ～ （ｔ） Ｚ （ｔ） 于是，可推导出 Ｔｒ （Ｘ － ＸＺ （ｔ＋１） ） Ｔ （Ｘ － ＸＺ （ｔ＋１） ） ＋ λ１∑ ｄ ｉ ＝ １ ∑ ｎ ｊ ＝ １ ‖Ｚ （ｔ＋１） ｉｊ ‖ ＋ λ２∑ ｄ ｋ ＝ １ ‖ （Ｚ （ｔ＋１） ） ｋ‖２ ≤ Ｔｒ （Ｘ － ＸＺ （ｔ） ） Ｔ （Ｘ － ＸＺ （ｔ） ） λ１∑ ｄ ｉ ＝ １ ∑ ｎ ｊ ＝ １ （‖Ｚ （ｔ） ｉｊ ‖） ＋ λ２∑ ｄ ｋ ＝ １ ‖ （Ｚ （ｔ） ） ｋ‖２ 根据文献 ［ １４］， 对于任意向量 Ｚ 和 Ｚ０ ， 有 ‖Ｚ２‖－ ‖Ｚ‖２ ２ ２ ‖Ｚ０‖２ ≤‖Ｚ０‖２ － ‖Ｚ０‖２ ２ ２ ‖Ｚ０‖２ 。 由以上分 析可知，算法 ２ 中的目标值在每一次迭代中都会减 小。 Ｚ （ｔ） 、Ｄ （ｔ） ｉ （１≤ｉ≤ｎ） 和Ｄ ～ （ｔ） 在收敛处满足等式 （５），且目标函数（２）是凸函数，于是此时得到的 Ｚ 是式（３）的一个全局最优解，因此，算法 ２ 可将问题 （３）收敛到全局最优解。 另外，在每一次迭代时都 有封闭形式的解，因此我们的算法收敛非常快。 ４ 实验分析与讨论 ４．１ 实验数据集及评价指标 本文算法通过 ＭＡＴＬＡＢ 语言编程，且所有实验 都是在 ｗｉｎ７ 系统下的 ＭＡＴＬＡＢ ２０１４ 软件上运行测 试。 实验用到的数据集介绍如下。 Ｈｏｐｋｉｎｓ１５５ ［１５］数据集被广泛用来测试各种子 空间聚类算法。 该数据集由 １５６ 个视频序列组成， 一个序列对应一个数据集，所以其共有 １５６ 个数据 集，并且每个序列中包含 ２ 或 ３ 个运动物体目标。 Ｊａｆｆｅ ［１６］数据集由日本 ＡＴＲ 表情识别研究协会 提供，该数据集包含 １０ 个人的 ２１３ 张表情图像，每 张表情图像经过预处理被裁剪为 ３２ 像素×３２ 像素 大小的尺度。 ＵＳＰＳ ［１７］数据集是由 美 国 国 家 邮 政 局 提 供， 数据集含有 ９ ２９８ 个 ０～１０ 的手写数字数据集，每个 手写数字数据经预处理都被裁剪为 １６ 像素×１６ 像 素大小的尺度。 用每个数字的前 １００ 个图像进行 实验。 ＯＲＬ ［１８］数据集是由剑桥 Ｏｌｉｖｅｔｔｉ 实验室提供， 数据集包含 ４０ 人的共 ４００ 张面部图像，每张人脸数 据经预处理被裁剪为 １６ 像素×１６ 像素大小的尺度。 为了验证算法的性能，将目前较好的子空间聚 类算法 ＬＳＲ、ＬＲＲ 和 ＳＳＣ 与本文算法进行对比实 验。 为了保证算法的公平性，所有算法都没有对数 据进行后期处理。 子空间聚类的重要挑战是处理存在于数据中的 错误。 因此，本文将子空间聚类错误率作为衡量各 个算法性能的评价标准。 其中，错误率越小，子空间 聚类效果越好；反之，则越差。 其定义为 子空间聚类错误率＝ 错误分类的样本数 样本总数 ４．２ 实验结果与分析 ４．２．１ Ｈｏｐｋｉｎｓ１５５ 数据集上的实验 由于 Ｈｏｐｋｉｎｓ１５５ 数据集包含 １５６ 个不同的数 据集，根据文献［１９］，本文将 １５６ 个数据集中的子 空间聚类错误率的最大值（Ｍａｘ）、均值（Ｍｅａｎ）和中 值（Ｍｅｄｉａｎ） 以及标准差（ Ｓｔｄ） 作为评价指标。 对 ＬＳＲ，ＬＲＲ，ＳＳＣ 以及本文算法 ＳＳＲ＿ＳＣ 在该数据集 进行了对比，实验结果如表 １ 所示。 通过分析表 １ 可知，在 Ｈｏｐｋｉｎｓ１５５ 数据集上， 本文提出的 ＳＳＲ＿ＳＣ 比 ＬＳＲ、ＬＲＲ 和 ＳＳＣ 获得了更 好的子空间聚类效果。 具体地，ＳＳＲ＿ＳＣ 与 ＬＳＲ 算 第 ５ 期 林大华，等：稀疏样本自表达子空间聚类算法 ·６９９·