二分类图上的非冗余协同图模式挖掘算法-计算机学报.PDF

第 卷 第 期 计 算 机 学 报 ３８ ７ 　 　　 　　 　　 　　 Ｖｏｌ．３８ Ｎｏ．７ 年 月 ２０１５ ７ Ｊｕｌ２０１５ ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳ ｙ 　 二分类图上的非冗余协同图模式挖掘算法 王章辉 赵宇海 王国仁 李 源 　 　 　 （东北大学信息科学与工程学院 沈阳 １１０８１９） 　 　 摘 要 图模式广泛应用于构建高效图分类模型的特征空间识别 协同图模式是一种内部节点高度相关的图结 ． 　 　 构，与普通图模式相比，协同图模式具有更高的区分能力，从而更加适用于分类模型的特征选择 文中研究了从二 ． 分类图中挖掘非冗余协同图模式的问题，通过限制协同图模式的区分能力远远高于其所有子图模式的非冗余性 质，大幅度减少了挖掘结果的数量，同时保留了具有强区分能力的协同图模式 由于协同图模式理论上必须检测其 ． 所有子图是否满足约束条件，挖掘它们非常具有计算挑战性 基于非冗余协同图模式的多种特性，提出相对应的削 ． 减规则；通过对区分能力的边界估计，提出两个快速检测非冗余协同图模式方法，在此基础上给出了一种高效的深 度优先挖掘算法 大量真实与合成数据集上的实验结果表明， 算法明显优于其他两个代表性算法，作为 ＧＩＮＳ． ＧＩＮＳ 图分类模型的分类特征时，非冗余协同图模式获得了较高的分类精度． 关键词 二分类图；非冗余；协同图模式；图分类；图挖掘；子图模式；分类器 　 中图法分类号 号 ／ ＴＰ３１１ 犇犗犐 １０．１１８９７ＳＰ．Ｊ．１０１６．２０１５．０１４３４ 　　　 犕犻狀犻狀 犖狅狀犚犲犱狌狀犱犪狀狋犛狀犲狉 犌狉犪犺犘犪狋狋犲狉狀狊犳狉狅犿犜狑狅犆犾犪狊狊犲狊狅犳犌狉犪犺狊 犵 狔 犵狔 狆 狆 ＷＡＮＧＺｈａｎＨｕｉ ＺＨＡＯＹｕＨａｉ ＷＡＮＧＧｕｏＲｅｎ ＬＩＹｕａｎ ｇ 　 　 　 （ ， ， ） 犆狅犾犾犲犲狅 犐狀狅狉犿犪狋犻狅狀犛犮犻犲狀犮犲犪狀犱犈狀犻狀犲犲狉犻狀 犖狅狉狋犺犲犪狊狋犲狉狀犝狀犻狏犲狉狊犻狋 犛犺犲狀犪狀 １１０８１９ 犵 犳 犳 犵 犵 狔 狔 犵　 犃犫狊狋狉犪犮狋 Ｇｒａｈ ａｔｔ