论文研究-一种基于p-Laplacian的谱聚类维数约简算法.pdf

所需积分/C币:10 2019-07-22 20:53:43 1.43MB .PDF
收藏 收藏
举报

近年来, 谱聚类因其深厚的理论基础而在机器学习和数据挖掘领域中引起了广泛的关注。针对谱聚类算法中采用Laplacian矩阵时无法获得较好的图切判据, 通过引入p-Laplacian算子, 提出了一种基于p-Laplacian的谱聚类维数约简算法。仿真实验表明, 提出的方法可以获得一种优化图切的近似解, 使得在降维后能够更为精确地求得原始数据在低维空间中的嵌入投影。
2128 计算机应用研究 第29卷 进后的谱聚类来构建维数约简算法时样本间的亲和度矩阵选 用下面的方法,即在由样本集构建的图G(V,E)中,设 y=max16;(),(l)}x;和x柜连 (18) x,和x,不相连 其中:62(j)=exp 4‖x-x, ;为X到它的近邻点之 间的距离。 根据以上分析,基于 p-Laplacian的谱聚类维数约简算法 流程如下所示 图2CM人脸数据集示例 输人:数据集X={x1,x2,…,xy,聚类数h,参数p=1.2 通过門sC算法计算得到∫低维嵌入数据点,然后用部分 输出:样本在低维空间的投影Y={y1,y2,…,yN,完成降维。 具有代表性的原人脸图像代替嵌人空间的点,则可得到如图3 a)根据式(18)构造样本亲和度矩阵W∈R b)初始化聚类A1=V,聚类数s=1; 所示的直观的低维嵌入结果。该图中同类图像分布得比较紧 c)重复步骤c)~g) 凑,不同类相互间则很分散,直观地说明」在降维过程中使用 d)对每一个聚类A2(i=1,2,…,s),最小化目标函数F(f); PLSC方法可以得到很好的低维嵌入结果。 e)利用式(7)或(8)对非规范矩阵或规范矩阵求解最优的边值,从3.3UC|数据集 而得到齐格切判据的近似解; 为进一步验证本文方达的有效性,选择了具有高维特征的 f)利用切割判据的最小目标函数对A1(i=1,…,s)进行分割 g)s∈=s+1 UCI数据集进行实验分析,表1给出了数据集的属性。对比方 法包括LDA、LLE、 SOMAP以及PLSC。LDA是种经典的线 1)利用过程中求解的特征值所对应的特征向量来张成低维空间,性降维方法;LLE是一种无监督学习算法,可以最大限度地保 得到样木在低维空间的投影 持线性组合系数的线性子空间嵌入;OMAP可以获得最大限 3实验仿真与结果分析 度地保持测地线距离的线性子空间嵌入,这些算法在维数约简 领域都引起了广泛的关注,具有较高的代表性,所以本文选用 为了分析本文提出的谱聚类维数约简算法的降维性能,分这三种算法作为对比算法。实验首先用四种算法对UCI数据 別选取了人脸数据集和UCI数据集进行了以下实验。实验的集进行降维,然后用半监督学习算法识别,最后对识别正确率 计算机环境为:处理器为 Pentium3.00CH,内存2GB,硬盘进行比较。识别时采取10倍交又验证的方法,选取数据集中 500GB,操作系统为 Windows x,编程语言为 MATLAB20b。的10%作为训练样本,剩余作为测试样本,得出训练集对测试 3.1算法的有效性分析 集的识別正确率,进行多次实验,将平均结果作为最终的识别 影响谱聚类算法的一个重要因索是选择合适的相似度知结果。 表1UI数据集属性 阵,一个理想的相似度矩阵应该是块对角矩阵,即对于一个聚 类別数 特征维数 样本数 类|A1,…,Ak},当数据点x、x属于不同类时s=0,则称矩阵 ionosphere S为对应于聚类{A1,…,Ak的块对角矩阵。实验选择 circles (三个圆环)数据集,对矩阵按照聚类属性重新排序。图1显 表2和图4为实验结果。 2UCI数据集平均正确识别率比铰 示了在原始空间计算的相似性矩阵和经 p-Laplacian谱映射后 算 LDA ISOMAP 得到的相似性矩阵。结果显示,原始空间的相似性矩阵无法体 识别率/% 81.37 86.79 87.34 90.18 现各类数据间的区分度,而经过p- Laplacian谱映射后得到的 相似性矩阵显示了明显的块对角模式,从而说明了该方法可增 PLSC 画u西 大类内相似度,同时缩小类间相似度。 80时 SOMAR 500 400 1020304050607080 300 特征维数 图3人脸数据集上的 图4UCI数据集上的 低维嵌入结果 维性能比较 yoor 100 IDA算法为线性方法,为了使其能够处理非线性高维数 010020030040500600U100200300400500600 据,首先把数据非线性地映射到某个特征空间,然后在这个特 (a)原始空间的相似性矩阵 b)谱块射后的相似性矩阵 征空间中进行 Fisher线性判別,这样就隐含地实现了对原输人 图1三个圆环数据集上的相似性矩阵 空间的非线性判别,从而可以使之和其他三种非线性方法具有 3.2人脸数据集 可比性。从该实验结果中可以看出,LDA算法的降维效果较 实验选用 image data中的 CMU face image数据集,图2显差, ISOMAP稍优于LLE,但差别不大,而PLSC与其他算法相 示了人脸数据集中的部分人脸数据。对每张人脸图片,取其灰比效果较优。这是因为经过对拉普拉斯矩阵的非线性一般化, 度值作为输人特征。对p1 laplacian参数p的考虑,分别采用p算法能够得到一个优化图切的近似解,并在嵌入空间中使得类 1.1,12,15,,7四个参数值进行了多次实验,根据实验结内更集中,类间更分散,获得较好的降维性能,从而提高了识别 果最终调整参数p=1.2,然后把改进后的拉普拉斯矩阵的第的正确率 二特征向量和第三特征向量分别作为嵌入空间的x轴和y轴。 (下转第2131页) 第6期 袁正午,等:一砷改进的射线跟踪定位算法 2131 用的电波频率为1.8GHz),如图2所示。先针对图2所示的量盲目的匹配,从而很好地提高了匹配速度,并且随着匹配数 地形建立定位数据库。其屮深色区域为建筑物,其高度为量的增多,匹配的效果会变得更好。这进一步证明了本文算法 15-30m,线色区域为树从,高度为3m,这是一个典犁的微小改进后更适用于匹配数量比较大的情况。 区结构。发射机高度为8.5m,接收机高度为1.5m;发射张角 为0.1,发射机和发射大线均为全方向天线,垂直极化方向。5结東语 仿真平台是MMD260+,1.6GHz,1GB内存,VC++6.0, 本文在基于射线跟踪的定位在线阶段对各个属性进行加 MATLAB7.1。根据发射机和接收札的位置用射线跟踪程序计 算出对应的数据库,完成离线阶段的工作。分别用文献[6]中 权,然后进行匹配预处理。仿真结果表明,该改进方法对在线 阶段匹配工作的精度和速度上都有了很好的提高,因此是一种 的算法、熵加权法、均方差加权法综合加权算法来计算定位后 的结果。图3所示即为实验后各种算法的对比图。从图中可具有较高安用价值的改进方法。 以看岀,熵加权和玓方差加权法能在一定程度上提高定位准确 参考文献: 率,但是组合加权法更加精确,并且在定位精度为6~8皿的准[1]袁正午.移动通信系统终端射线跟踪定位理论与方法[M].北京 确率上有了很大的提升。这是由于射线跟踪定位技术的实际 电子工业出版社,2007 情况决定的,即在定位精度要求低于6m时,是定位准确率能2 CHEN S H, JENG S K. An SBR/image approach for radio wave 达到的较好水平。 propagation in indoor environments with metallic furniture J]. IEEE Trans on Antennas and Propagation, 1997, 45(1): 98-106 十2 [3 TAN SY, TAN H S. A microcellucar communications propagation 湮70 noel based on the uniform theory of diffraclion and multiple image theory[ J. IEEE Trans on Antennas and Propagation, 1996, 44 (10):1317-1326 46 10121416 精度距离 [4』刘海涛,黎滨洪,谢勇,等.并行射线跟踪算法及其在城市电波预 图2仿真所用地形平面示意图 图3各种算法对比图 澳的应用[冂].电波科学学报,2004,19(5):581-585 表1是经过组合加权和预处理匹配之后的定位结果与原[5]袁正午,黎意超,李林,等,基动态分区的射线跟踪加速方法 始算法结果的响应时间对比表。 [J].计算机工程与应用,2010,46(27):77-79 表1改进前后对比表 L6」袁正午,江晓帆,基于三维射线跟踪方泫的城市微∴区定位模型 文献[6]算法改进前算法 改进后算法 「J.计算机应月研究,2009,26(8):2965-2967 比较项 匹配实例个数 2000 2000 600 [7]蒋占四,陈立平,罗年猛.最近邻实例检索相似度分祈[J].计算机 模型层次数 集成制造桑统,207,13(6):165-116 属性个数 [8〗樊冶平,濬德惠.多属性决策的一神主客观综合法[J].系统工程 匹配成功率/% 83.4 1995,13(5):28-31 最大匹配时可/e 4.8 4 3 [9」陈华友,多属性决策中的一种最优组合赋权方法研究[J].运筹与 管理,2003,12(2):6-10 从表I屮可以看出,改进的算法将模型层次数分为三层 「10罗佳,杨世平,基于熵权系数法的信息安全模糊风险评估「J1.计 在匹配实例个数及属性个数等各种条件完全相同时,经过改进 算杌技术与发展,2009,19(10):177-180 后的算法在匹配速度上有了改善。原因是经过预处理后,匹配 l1陈建海,冯杰.熵炆和灰关瑗在舰艇战损装备抢修排序中的应 时进行对比的数据有了很好的针对性,免了匹配时进行大 用「J1.船舰科学技术,2011,33(3):131-134. (上接第2128页) [2] Von LUXBLRG U. A tutorial on spectral clustering[ J]. Statistics and Computing,2007,17(4):395-416. 4结束语 31 AMCHIBECH S. Bounds for the largest p-Laplacian eignvalue for graphs[ J]. Discrete Mathematics, 2006, 306(21): 2762-2771 利用谱聚类来构造非线性维数约简算去,可以得到数据点14」ⅢENM, AUDIBERT J Y, Von LUXBURG U. Graph Laplacian and 在低维空间的嵌入,从而能很好地实现维数约简。本文提出基 their convergence on random neighborhood graphs[J1. Journal of 于p- Laplacian的谱聚类维数约简算法,获得了一种齐格图切的 Machine Learning Research, 2007, 8(12): 1325-1368 近似解,并通过对实验结果的分析表明,该算法使得投影到变15」 FLE CKINGER I, IIARRELL I E M, De thelin F. On the fun 換后的子空间中,类间的数据点具有更好的区分度。与其他降 damental eigenvalue ratio of the p-Laplacian[ J. Bulletin des Sci 维算法相比,在UCI数据集上的识别率也有着较好的效果。由 ences Mathematiques, 2007, 131(7): 613-619 于在该方法中需要调整参数p的大小,给P5C算法帮来了一16 g Alang,). ctive spectral clustering[ C//Proc o 定的影响,将会在下一步的工作中对参数p的调整进行深入 IEEE International Conference on Data Mining. Washington Dc 研究 IEEE Computer Society, 2010: 561-568 [7 BINDING P A, RYNNE B P. Variational and non-variational ei 参考文献 genvalues of the p-Laplacian[ J I. Differential Equations, 2008 [I]谭璐.高维薮据的降雏理论及应用[D].杭州:浙江大学,2005. 244(1):24-39

...展开详情
试读 4P 论文研究-一种基于p-Laplacian的谱聚类维数约简算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    • 至尊王者

      成功上传501个资源即可获取
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    论文研究-一种基于p-Laplacian的谱聚类维数约简算法.pdf 10积分/C币 立即下载
    1/4
    论文研究-一种基于p-Laplacian的谱聚类维数约简算法.pdf第1页
    论文研究-一种基于p-Laplacian的谱聚类维数约简算法.pdf第2页

    试读已结束,剩余2页未读...

    10积分/C币 立即下载 >