半监督模糊局部Fisher判别分析

半监督模糊半监督模糊 Fisher 降维分析降维分析 杨昔阳 1 邓朝阳2 李志伟1 1 泉州师范学院大数据重点实验室 泉州 福建 2 泉州医学高等专科学校 泉州 福建 摘要 摘要 针对少量具有模糊隶属度类别的数据和大量未知类别的数据组成的数据集 提出了一种 结合 PCA 和局部 Fisher 判别分析的半监督降维方法 这种半监督方法结合了 PCA 和局部 Fisher 判别的优点 一方面可保持所有数据的全局分布结构 另一方面又体现了已知类别属性的样本 分类信息 所提出的模型可以通过求解特征值问题求解 实验表明 在获取较为准确的模糊隶 属度的情况下 这种算法可以有效地对多维数据进行降维 关键词 模糊隶属度 PCA 局部 Fisher 判别分析 广义特征值问题 A Semi supervised Fuzzy Dimension Reduction Method Yang Xiyang1 Deng Chaoyang2 Li Zhiwei1 1 Key laboratory of Intelligent Computing and Information Processing of Fujian Province Quanzhou Normal University Quanzhou China 2 Quanzhou Medical College Quanzhou China Abstract This paper proposed a semi supervised fuzzy dimension reduction method by combining PCA and local Fisher Discriminant Analysis for a data set with a small number of data with fuzzy membership labels and a great amount of unlabeled data This method takes advantages of PCA and local FDA by preserving the global structure of unlabeled samples and separating labeled samples in different classes from each other Our tests show the usefulness of this method in dimension reduction provided that the fuzzy membership labels are correctly given Keywords Fuzzy Membership PCA Local Fisher Discriminant Analysis Generalized Eigenvalue Problem 将高维数据转化为低维数据 可以降低模式识别算法的计算量 避免算法陷入 维数 灾难 降维算法通过线性或非线性变换 建立从高维空间到低维空间的映射 并尽量保持 数据的邻域分布信息 降维算法可以分为监督降维和无监督降维两种 无监督降维方法包 括主成分分析 Principle Component Analysis PCA Error Reference source not found 局部 保持投影 Locality Preserving Projection Error Reference source not found 多维尺度分析 Multidimensional Scaling Error Reference source not found 等 这类算法由于缺乏足够的类 别指标的指引 对于某些数据集 在降维过程可能会存在一定的盲目性 Error Reference source not found 监督降维方法 包括 Fisher 判别分析 Fisher Discriminant Analysis FDA Error Reference source not found 局部 Fisher 判别分析 Local Fisher Discriminant Analysis L FDA 等 Error Reference source not found Error Reference source not found 利 用样本的类别属性信息进行降维 在有类别属性的样本 标号样本 足够多的情况下 这类 算法往往可以取得较好的降维效果 但是在实际应用场合 获取足够多的标号样本往往是 收稿日期 基金项目 福建省教育厅资助项目 JA12273 JK JA13395 泉州市科技局项目 2012Z103 通信作者 李志伟 1965 男 教授 从事应用数学研究 Wei 不切实际的 如果仅仅依靠少量标号样本进行降维 当选取的样本没有足够的代表性时 其效果反而不如无监督降维 此时 综合利用大量无标号样本和少量标号样本的半监督降 维方法是一种可行的降维手段 Error Reference source not found Error Reference source not found 上述降维方法处理的数据集都是具有分明类别属性的 也就是说一个数据要么属于某 一类 要么不属于某一类 没有中间的过渡情况 处理具有模糊隶属度的数据的方法有很 多 其中关于降维的算法包括 模糊 FDA Fuzzy Fisher Discriminant Analysis F FDA Error Reference source not found Error Reference source not found 概率型 FDA Probabilistic discriminant analysis Error Reference source not found 和基于核函数的模糊 FDAError Reference source not found 等 此外模糊化方法也经常用于模式识别的场合 比如基于模 糊图 Fuzzy Graph 特征提取算法 Error Reference source not found 模糊支持向量机 Error Reference source not found 等 由此可见 模糊化 是改造经典模式识别算法是一种手段 本文综合 模糊化 和半监督学习两种思想 提出了一种基于半监督模糊局部 Fisher 判 别的降维方法 Semi supervised Fuzzy Local Fisher Discriminant Analysis SFL FDA SFL FDA 首 先计算模糊化的局部组内散度矩阵和组间散度矩阵 借鉴半监督学习的思想 与 PCA 的总 散度矩阵进行综合 构造一个广义特征值问题 并通过求解这个问题得到最佳降维方向 这种方法综合了半监督学习和模糊化方法的优点 在本文的实验中 这样的综合有助于提 高降维的效果 本文的后续部分安排如下 第一节首先介绍与 SFL FDA 相关的算法 第二节首先介绍 了模糊 FDA 并给出了它的逐对表达形式 Pairwise Form 通过对它的修改提出了模糊局部 FDA 算法 最后和 PCA 进行综合 提出了 SFL FDA 降维模型 最后一节给出三个实验 验 证 SFL FDA 算法的有效性 1 1 降维方法回顾降维方法回顾 本节主要介绍和数据降维相关的一些数学模型 记是个维的数据样本 其中是空间的 列 向量 所有的 1 2 d i xRin nd i x d R 将组成一个的数据集 本文所研究的降维指的是 在空间中寻 i xdn 12 n Xx xx d R 找最佳的投影 列 向量 使得维的转变为一维的 即在上的投影 如果希 1d z d i x i z x i xz 望将转化为 维数据 则需要寻找 个列向量 记 i xr 1 rd r 12 r z zz 12 r Zz zz 则降维之后的 维数据表示在上的 个投影 i xr i Z x i xZr 1 1 主成分分析主成分分析 PCA 主成分分析 PCA 是一种使用最为广泛的无监督降维方法 Error Reference source not found 在 PCA 中 总散度矩阵 Total Scatter Matrix 定义为 1 n t ii i xxxxS 其中表示样本均值 还可以写成逐对形式 Pairwise Form Error Reference 1 1 n i i xx n t S source not found 11 1 2 nn tt i jijij ij Swxxxx 其中逐对系数矩阵 MERGEFORMAT 1 1 t i j w n PCA 通过下式 MERGEFORMAT 2 1 Optimal argmax d t z R d zz I z z S z 求解最佳投影向量 其中表示单位矩阵 Optimal z d I 1 2 Fisher 判别分析判别分析 FDA 线性判别分析 FDA 是一种应用广泛的 有监督的降维方法 对于一个带有分明类别属 性的数据集 表示标号样本的数量 表示样本点的类 2 1 ii x yin n 1 2 i cy i x 别属性 表示类别的总数 分明 是指 只能属于且仅能属于某一类别 FDA 的组间散c i x 度矩阵 Between class Scatter Matrix 定义为 1 mm c b m m Snxxxx 组内散度矩阵 Within class Scatter Matrix 定义为 1 1 i c w n iimm i m m y Sxxxx 且 其中 1 1 m i i i y m m n xx n 且 表示第个类别的样本均值 为第个类别的样本数 表示的类别属性 求和符m mnm i y i x 号的下标 表示对所有属于第个类别的样本求和 可以证明 和 1 i nimy m b S 的逐对形式为 Error Reference source not found w S 和 11 nn bb i jijij ij wxxxSx 11 nn ww i jijij ij wxxSxx 其中组间逐对系数 MERGEFORMAT 3 1 1 1 i yij b i j ij nnyy w nyy 组内逐对系数 MERGEFORMAT 4 1 0 i yij w i j ij nyy w yy FDA 通过求解 MERGEFORMAT 5 1 Optimal argmax d w b z R zz z zz S S 得到投影向量 Optimal z 1 3 局部局部 Fisher 判别分析判别分析 local FDA L FDA 在 MERGEFORMAT 3 式中 组间系数矩阵的元素仅仅依赖于的类别信息 b i j w ij x x 而与的距离远近无关 为了区分不同的数据对对降维的作用 强化样本 ij y y ij x x ij x x 局部的分布信息 Sugiyama 在文献 Error Reference source not found 中提出了局部 Fisher 判别分析法 L FDA L FDA 通过修改 MERGEFORMAT 3 式和 MERGEFORMAT 4 式逐对 系数和的定义 b i j w w i j w MERGEFORMAT 1 1 0 1 i i i jyij i jyij lblw i ji j ij ij AnyyAnnyy ww yy nyy 6 使得距离比较远的 具有相同类别属性的数据对 通过 对降维方向的选取产生较小的影 i j A 响 调节参数的定义方式有多种 Sugiyama 建议采用 i j A 2 exp ij i j ij xx A 其中 表示的第个近邻 实验表明是一个较好地选择 Error k iii xx k i x i xk7k Reference source not found 相应的局部组间散度矩阵 Local Between class Scatter Matrix 和局部组内散度矩阵 Local Within class Scatter Matrix 可以写成 lb S lw S 和 11 nn lblb i jijij ij xxxxwS 11 nn lwlw i jijij ij wxxxSx 和 FDA 一样 LFDA 通过最大化组间散度平方和 同时最小化组内散度平方和来寻找最 佳投影向量 即 MERGEFORMAT 7 1 Optimal argmax d lb lw z R zzS z zzS 2 2 半监督模糊局部半监督模糊局部 FisherFisher 判别分析判别分析 由于模糊集合比普通的集合具有更强的类别属性表达能力 很多基于分明集的方法都 有基于模糊集的拓展 例如基于模糊集的 FCM 算法是基于分明集的 K means 的拓展 基于 模糊集的模糊推理理论是基于一般集合论的数理逻辑的扩展 本节将给出 LFDA 的模糊化 方法 并将其与主成分分析结合 构造一种新的半监督模糊局部 Fisher 判别方法 2 1 模糊模糊 Fisher 判别分析判别分析 Fuzzy FDA F FDA 线性判别分析是一种常用的监督型降维方法 主要应用于具有分明的类别属性的场合 对于一个带有模糊类别属性的数据集 表示样本点 2 1 ii x uin 1 2 iiii c uuuu 属于各个类别的隶属度 仍然表示类别的总数 规定 i xc 1 1 10 c i mi m m uu 定义标号样本的总体均值和类均值为 MERGEFORMAT 8 11 11 nn m ii mi ii m xxux n x n 其中表示标号样本的容量 表示第类的样本容量 模仿 FDA 中组间散度 n 1 n mi m i nu m 矩阵和组内散度矩阵的形式 定义模糊组间散度矩阵 Fuzzy Between class Scatter b S w S Matrix 为 1 mm c fb m m Snxxxx 将 MERGEFORMAT 8 式代入 则可以写成如下的逐对形式 fb S 11111 111 11 1 1 1 2 cnnnn fb mm i miii mii miiii m nnc mm i mj mij ijm m nn fb i jijij ij nn Suxxuxx nnn nn uux x nnn wxxxx 其中 11 1 1 cc i mj mfb mm i ji mj m mm mm uu nn wuu nnnnn MERGEFORMAT 9 当与具有相同的分明的类别属性时 i x j x 1 1 i c i mj m m my uu nn 其中仍表示的分明类别属性 当与具有不同的分明类别属性时 i y i x i x j x 1 0 c i mj m m m uu n 由此可知 当数据具有分明的类别属性时 MERGEFORMAT 9 式与 MERGEFORMAT 3 式一致 因此 F FDA 模型的组间逐对系数 MERGEFORMAT 9 式可以看成是 FDA 模型的组 间逐对系数 MERGEFORMAT 3 式的推广 定义模糊组内散度矩阵 Fuzzy Within class Scatter Matrix 为 11 cn fw i miimm mi Suxxxx 将 MERGEFORMAT 8 式代入 则可以写成如下的逐对形式 fw S 11 11 11111 111 1 1 cn fw i miiimmimm mi cn i miimmm mi cnnnn i mj miii mii mi mijii m cnn mij m Sux xx xxxxx ux xnxx uux xuxux n n 11 11 1 2 nn i mj miii mj mij ij nn fw i jijij ij uux xuux x wxxxx 其中 MERGEFORMAT 10 1 c i mj mfw i j m m uu w n 同样地 F FDA 模型的组内逐对系数 MERGEFORMAT 10 式可以看成是 FDA 模型的组 内逐对系数 MERGEFORMAT 4 式的推广 2 2 模糊局部模糊局部 Fisher 判别分析判别分析 Fuzzy Local FDA FL FDA 1 3 节的局部化思想可以突出数据集的局部分布 使得距离比较近的标号数据对发挥更 大的作用 从而获得更好的判别性能 我们模仿 FDA 局部化为 L FDA 的做法 将 F FDA 局 部化为 FL FDA 这种改造方式同样也可以通过修改系数矩阵完成 在 L FDA 中 局部组间系数是依据是否属于同一类别这两种情况分段定义的 lb i j w ij x x 如果属于相同的类别 其组间系数矩阵需要通过加以调节 反之则不需要 而在 ij x x i j A 本文提出的 FL FDA 中 局部组间系数被定义为上述两种情况的加权平均 之所以这样 flb i j w 定义的原因是 模糊隶属度使得以一定程度属于相同的类别 同时也以一定的程度不 ij x x 属于相同的类别 权重 1 c i ji mj m m uu 表示隶属于同一类别的程度 显然 这样结合 MERGEFORMAT 9 式 FL ij x x 01 i j FDA 的组间逐对系数便可写成 11 11 1 1 fbfbflb i ji ji ji ji ji j cc i mj mi mj m i ji ji j mm mm ww uuuu nn w A nn A 由于不出现在 F FDA 的组内逐对系数中 所以同 MERGEFORMAT 10 式 仍然定义 FL i j A FDA 的模糊组内逐对系数为 1 c i mj m flwfw i ji j m m uu n ww 这样 FL FDA 的组内散度矩阵和组间散度矩阵为 和 11 nn flbflb i jijij ij Sxwxxx 11 nn flwflw i jijij ij Swxxxx FL FDA 同样通过最大化组间散度平方和 同时最小化组内散度平方和来寻找最佳投影 向量 MERGEFORMAT 11 1 Optimal argmax d flb flw z R Szz z z Sz 2 3 半监督模糊局部半监督模糊局部 Fisher 判别分析判别分析 semi supervised fuzzy local FDA SFL FDA 在现实生活中有可能出现一类这样的数据集 大部分数据的类别属性是未知的 1 n ii x 只有少量的数据经过专家的分析 得到了 模糊 类别属性 例如在一个蔬 1 n ii x 1 nn 菜叶片数据集中 专家给出了少量几张图片患病程度的类别属性 其中某些叶片被判定介 于健康与患病之间 文献 Error Reference source not found 综合有监督和无监督降维 提出了一种半监督 局部 Fisher 降维方法 SL FDA 降维方法 由此启发 本节我们定义一种新的 综合 PCA 和 FL FDA 的半监督模糊局部 Fisher 降维方法 SFL FDA 定义 SFL FDA 的降维模型为 MERGEFORMAT 12 1 Optimal argmax d sflb sflw z R z z zS zS z 其中 MERGEFORMAT 13 1 1 sflbflbtsflwflw SSSSSI 称为半监督模糊局部组间散度矩阵和组内散度矩阵 可以调节 PCA 和 FL FDA 在半 0 1 监督降维的作用 如果 那么 SFL FDA 就等价于 FL FDA 如果 那么 SFL FDA 就0 1 等价于 PCA 模型 MERGEFORMAT 12 的解法同上 可以证明是的最大特征 Optimal z inv sflwsflb SS 根所对应的特征向量 如果需要将数据降成二维数据 便可再求第二大特征根所对应的特 征向量 以此类推 Error Reference source not found 在下文的实验中 我们将所有的特 征向量进行归一化处理 Error Reference source not found 与文献 Error Reference source not found 提及的 SL FDA 比较 SFL FDA 可以看作是 SL FDA 的模糊化 下文我们将对这两种方法的降维效果进行比较 3 3 实验实验 3 1 人造数据集人造数据集 图 1 的圆圈和菱形数据点来自于两个不同的类别 实心的数据点表示标号数据 50 个 未标号的圆圈数据取样于一个中心位于 协方差矩阵的二维正态母体 3 0 4 0 0 4 50 个未标号的菱形数据来自均值为 具有相同协方差矩阵的正态母体 标号数据各有 3 0 5 个 圆圈数据取样于均值为的正态母体 菱形数据的母体均值为 协方差均为单位 1 v 2 v 阵 为了检验标号数据的位置对降维效果的影响 在以下的 3 个实验中 被赋予不同 1 v 2 v 的值 采用归一化的密度函数来定义标号数据的模糊隶属度 即取 12 12 1 normpdf normpdf normpdf normpdf iii ii x vx v x vx v MERGEFORMAT 14 其中表示参数为的二维正态分布的密度函数 取 normpdf x v v 0 5 在第一个实验中 如图 1 a 所示 设置与母体均值一致的 由于样 12 3 0 3 0 vv 本量比较大 PCA 可以比较好地识别出最佳的降维方向 由于标号样本具有较好的代表性 FL FDA 的降维效果也比较好 但由于样本量比较小而导致的随机性 其降维方向略有偏差 SFL FDA 的降维方向介于两者之间 在第二个实验中 如图 1 b 所示 设置 由于圆圈数据的标号样本 向上 偏离数据集 导致 FL FDA 得到的降维 12 3 5 3 0 vv 方向偏差比较大 在 PCA 的干预下 SFL FDA 可以得到较好的降维方向 在第三个实验中 如图 1 c 所示 设置以保证 FL FDA 结果的准确性 然后对整个数据集 12 3 0 3 0 vv 的纵坐标扩大 2 倍 受此影响 PCA 得到的降维方向偏差非常大 在 FL FDA 的干预下 SFL FDA 也得到较好的降维方向 在大多数实验中 SFL FDA 的降维方向是 PCA 和 FL FDA 的综合 a b 12 3 0 3 0 vv 12 3 5 3 0 vv c 纵坐标扩大 2 倍 图 1 SFL FDA演示图 为了比较 SFL FDA 和原有算法 SL FDA 的差异 我们构造两个来自于二维正态分布的数 据集 每个数据集含有 100 个样本 第一个数据集的母体均值为 第二个的母体均 1 0 值为 协方差矩阵为单位阵 显然理论上的最佳降维方向是轴方向 从每个数据集 1 0 x 随机选取 20 个样本作为标号数据 对于 SFL FDA 其模糊隶属度函数的计算方法同 MERGEFORMAT 14 式 通过 SL FDA 和 SFL FDA 计算最佳投影方向和 并 SL FDA z SFL FDA z 计算他们与轴所成的角度 图 2 给出了一次实验 SL FDA SFL FDA 及其他方法 的降维方向 x 图中的点的标记含义同上 由图 2 的实验可以发现 SFL FDA 略好于 SL FDA 重复该实验 1000 次 与轴所成的角度平均值为 0 0838 度 方差为 5 8412 而与轴 SL FDA z x SFL FDA z x 所成的角度平均值为 0 0637 度 方差为 5 5121 可见在这种情形下 SFL FDA 可以得到更 加精确的投影方向 1000 次实验的结果的盒子统计图如图 3 所示 图 2 数据集与降维方向图 3 一致率的盒子统计 3 2 半监督数据集半监督数据集 Chapelle 在其编著的 Semi supervised Learning 中提供了一个半监督数据库 Error Reference source not found 这个数据库包含 9 个半监督学习数据集 记为 i SSL 每个数据集包含 12 组实验 在每组实验中 10 个样本的类别属性是已知的 91 i 我们测试了其中 6 个数据集 另外 3 个数据集没有测试是因为 第 6 个数据集包含 6 个类别 使得寻找合适的隶属度非常困难 第 8 个数据集的样本个数超过 100 万 第 9 个数据集的 维数超过 1 万 计算量过于庞大 设定 利用 SFL FDA 和 SL FDA 方法 把这些数0 5 据集降成二维数据 然后采用经典的 FCM 算法进行聚类分析 所得到的类别与原有的类别 进行比较 采用一致率评判 SFL FDA 和 SL FDA 的优劣 由于数据集本身没有提供模糊隶属 度 我们通过遗传算法 GA 寻优最佳的类别隶属度 使得 SFL FDA 的一致率尽量高 这六个 数据集的计算结果如表 1 所示 由这些实验可以发现 SFL FDA 的降维效果无论在均值和 方差上看都要显著优于 SL FDA 但一个需要注意的问题是 SFL FDA 的这种优势是建立在 获得合适的模糊隶属度的基础上的 在实验中我们发现 如果模糊隶属度选取不当 SFL FDA 的效果反而会更差 表 1 SFL FDA 与 SL FDA 的一致率比较 数据集维数 标号样 本个数 未标号 个数 实验重 复次数 SL FDA 一致率 均值 SL FDA 一致率 标准差 SFL FDA 一致率 均值 SFL FDA 一致率 标准差 SSL1241101400120 78920 0492 0 93330 0115 SSL2241101400120 66790 0614 0 72570 0358 SSL3241101400120 54480 0248 0 59710 0263 SSL411710300120 5252 0 0118 0 55250 0098 SSL5241101400120 6091 0 0340 0 87630 0047 SSL7241101400120 5870 0 0407 0 58800 0404 3 3 乳腺癌数据集乳腺癌数据集 选取 UCI 乳腺癌数据库中的两个乳腺癌数据集 wdbc 和 wpbc 进行测试 数据来源 http archive ics uci edu ml datasets Breast Cancer Wisconsin Original 部分样本由于属 性信息缺失 未参与计算 样本的各个维度表示病人各项检验指标的均值 所有数据经过 标准化处理 即每个数据的属性都减去其对应的均值再除以对应的标准差 随机选择 10 个 样本作为标号样本 利用 SL FDA 和 SFL FDA 将数据集降维到二维空间 然后采用 FCM 进行 聚类分析 聚类的结果与原有数据的类别标识进行比较 得到一致率的平均值和标准差 由于样本的模糊隶属度未知 采用 k 近邻分类法 Knn classifier 估计样本的隶属度 即通过 计算某样本个近邻中各个类别的样本的比例代替该样本的隶属度 在的k20k 0 5 水平下 两种降维方法的一致率的结果如表 2 所示 其盒子统计图如图 4 所示 由此可知 在未能获取精确隶属度的前提下 SFL FDA 比 SL FDA 稍有优势 效果也更加稳定 表 2 乳腺癌数据库的一致率比较 数据集 样本个 数 标号样 本个数 样本维 数 实验重 复次数 SL FDA 一致率 标准差 SL FDA 一致率 方差 SFL FDA 一致率 均值 SFL FDA 一致率 标准差 wdbc56910105000 9042 0 0179 0 90850 0121 wpbc19810105000 5661 0 0279 0 57370 0161 a wdbc 一致率比较 b wpbc 一致率比较 图 4 乳腺癌数据的一致率比较 总结总结 数据降维是很多模式识别算法的前期准备 合理的降维可以有效降低后期算法的计算 量 同时保持模式识别的效果 因此降维分析是一个值得关注的问题 本文针对具有模糊 隶属度的数据集 综合 PCA 和模糊局部 FDA 算法 提出了一种称为 SFL FDA 的半监督降维 算法 在本文的实验中 我们对数据进行降维之后 再采用 FCM 算法与原有的类别进行比 较得到数据集的一致率 经过比较发现 SFL FDA 优于基于分明集的半监督方法 特别是在 准确的模糊隶属度已知的情况下 但我们也发现 如果不能准确得到数据的模糊隶属度 SFL FDA 的结果未必更好 如何得到较为可靠的模糊隶属度是我们后续将要研究的问题之一 参考文献参考文献 1 高惠璇 应用多元统计分析 M 北京大学出版社 2005 265 273 2 Fadi Dornaika Ammar Assoum Enhanced and parameterless Locality Preserving Projections for face recognition J Neurocomputing 99 2013 448 457 3 I Borg P Groenen Modern Multidimensional Scaling Theory and Applications M Springer Verlag NewYork 2005 4 苏祖强 汤宝平 刘自然 秦毅 基于正交半监督局部 Fisher 判别分析的故障诊断 J 机械工程学报 50 18 2014 7 13 5 Masashi Sugiyama Dimensionality reduction of multimodal labeled data by local Fisher discriminant analysis J Journal of Machin