最小代价路径标签传播算法.PDFVIP

第 卷 第 期 计 算 机 学 报 ３９ ７ 　 　　 　　 　　 　　 Ｖｏｌ．３９ Ｎｏ．７ 年 月 ２０１６ ７ Ｊｕｌ２０１６ ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳ ｙ 　 最小代价路径标签传播算法 汪西莉 蔺洪帅 　　 （陕西师范大学计算机科学学院 西安 ７１０１１９） 　 　 摘 要 现有的半监督分类方法由于时间复杂度较高等原因无法用于稍大规模的图像分类 该文根据聚类假设， ． 　 　 通过寻找标签在图中进行传播的最主要路径，即最小代价路径，提出了最小代价路径标签传播算法（ＭｉｎｉｍｕｍＣｏｓｔ ， ）该算法通过变形的最小生成树得到无标记样本到标记样本间的最小代价路径， ＰａｔｈＬａｂｅｌＰｒｏａａｔｉｏｎＭＣＰＬＰ． ｐｇ 使标记沿着节点间代价最小的路径传播来实现分类，每个节点仅需被传播一次就能得到它们的标记 同时发现本 ． 文算法以及其他这类基于图的标签传播半监督分类方法由于构建的稀疏图存在图的连通性问题，导致可能出现标 签不能被传播到所有节点，即存在数据不能被分类的情况 我们研究了图的双向不连通问题和图的单向不连通问 ． 题（非对称图），提出构建稀疏对称矩阵增强图的连通性以及对未分类数据进行再次分类的方法，解决由连通性带 来的数据不能被全部分类的问题 分析及实验结果表明提出的 算法不仅具有较低的时间复杂度，而且有 ． ＭＣＰＬＰ 较高的分类正确率 通过对大规模图像的分类实验，验证了 算法同样适合于大规模的图像数据分类 ． ＭＣＰＬＰ ． 关键词 基于图的半监督分类；最小代价路径；图的连通性；最小生成树；图像分类 　 中图法分类号 号 ／ ＴＰ１８ 犇犗犐 １０．１１８９７ＳＰ．Ｊ．１０１６．２０１６．０１４０７ 　　　 犔犪犫犲犾犘狉狅犪犪狋犻狅狀犜犺狉狅狌犺犕犻狀犻犿狌犿犆狅狊狋犘犪狋犺 狆犵 犵 ＷＡＮＧＸｉＬｉ ＬＩＮＨｏｎＳｈｕａｉ 　 ｇ （ ， ， ’ ） 犛犮犺狅狅犾狅 犆狅犿 狌狋犲狉犛犮犻犲狀犮犲 犛犺犪犪狀狓犻犖狅狉犿犪