一种基于随机游走模型的多标签分类算法

《一种基于随机游走模型的多标签分类算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第３３卷第８期计算机学报Ｖｏｌ．３３Ｎｏ．８２０１０年８月ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳＡｕｇ．２０１０一种基于随机游走模型的多标签分类算法郑伟王朝坤刘璋王建民（清华大学软件学院北京１０００８４）（清华信息科学与技术国家实验室北京１０００８４）（信息系统安全教育部重点实验室北京１０００８４）摘要在数据挖掘领域，传统的单分类和多分类问题已经得到了广泛的研究．但是多标签数据的普遍存在性和重要性直到近些年来才逐渐得到人们的关注．在多标签分类问题中，由于标签相关性的存在，传统的单分类和多分类问题的解决方法，无法简单地应用于多标签分类问题．文中提出了一种基于随机游走模型的多标签分类算

2、法，称为多标签随机游走算法．首先，将多标签数据映射成为多标签随机游走图．当输入一个未分类数据时，建立一个多标签随机游走图系列．而后，对图系列中的每个图应用随机游走模型，得到遍历每个顶点的概率分布，并将这个点概率分布转化成每个标签的概率分布．最后，基于多标签随机游走算法，文中给出了一种新的阈值学习算法．真实数据集上的实验表明，多标签随机游走算法可以有效地解决多标签分类问题．关键词多标签；分类算法；随机游走；阈值学习中图法分类号ＴＰ１８１犇犗犐号：１０．３７２４／ＳＰ．Ｊ．１０１６．２０１０．０１４１８犃犕狌犾狋犻犔犪犫犲犾犆犾犪狊狊犻犳犻犮犪狋犻狅狀犃犾犵狅狉犻狋犺犿犅犪狊犲犱狅狀犚犪狀犱狅犿

3、犠犪犾犽犕狅犱犲犾ＺＨＥＮＧＷｅｉＷＡＮＧＣｈａｏＫｕｎＬＩＵＺｈａｎｇＷＡＮＧＪｉａｎＭｉｎ（犛犮犺狅狅犾狅犳犛狅犳狋狑犪狉犲，犜狊犻狀犵犺狌犪犝狀犻狏犲狉狊犻狋狔，犅犲犻犼犻狀犵１０００８４）（犜狊犻狀犵犺狌犪犖犪狋犻狅狀犪犾犔犪犫狅狉犪狋狅狉狔犳狅狉犐狀犳狅狉犿犪狋犻狅狀犛犮犻犲狀犮犲犪狀犱犜犲犮犺狀狅犾狅犵狔，犅犲犻犼犻狀犵１０００８４）（犓犲狔犔犪犫狅狉犪狋狅狉狔犳狅狉犐狀犳狅狉犿犪狋犻狅狀犛狔狊狋犲犿犛犲犮狌狉犻狋狔，犕犻狀犻狊狋狉狔狅犳犈犱狌犮犪狋犻狅狀，犅犲犻犼犻狀犵１０００８４）犃犫狊狋狉犪犮狋Ｔｈｅｒｅａｒｅｅｘｔｅｎｓｉｖｅｌｉｔｅｒａｔｕｒｅｓｒｅｌａｔｅｄｔｏｔｒ

4、ａｄｉｔｉｏｎａｌｓｉｎｇｌｅｃｌａｓｓａｎｄｍｕｌｔｉｃｌａｓｓｃｌａｓｓｉｆｉｃａｔｉｏｎｐｒｏｂｌｅｍｓ，ｉｎｗｈｉｃｈｅａｃｈｄａｔａｐｏｉｎｔｉｓａｓｓｉｇｎｅｄｔｏｏｎｅｃａｔｅｇｏｒｙ．Ｂｕｔｉｎｍａｎｙａｐｐｌｉｃａｔｉｏｎｓ，ａｄａｔａｐｏｉｎｔｍａｙｂｅｌｏｎｇｔｏｍｏｒｅｔｈａｎｏｎｅｃａｔｅｇｏｒｙ．ＴｈｉｓｋｉｎｄｏｆｐｒｏｂｌｅｍｉｓｃａｌｌｅｄｔｈｅＭｕｌｔｉＬａｂｅｌＣｌａｓｓｉｆｉｃａｔｉｏｎ（ＭＬＣ）ｐｒｏｂｌｅｍ．Ｄｕｅｔｏｔｈｅｅｘｉｓｔｉｎｇｏｆｌａｂｅｌｒｅｌｅｖａｎｃｅ，ｔｈｅｔｒａｄｉｔｉｏｎａｌｄａｔａｍｉｎｉｎｇｍｅｔｈｏｄｓｃａｎ

5、ｎｏｔｂｅｄｉｒｅｃｔｌｙａｐｐｌｉｅｄｔｏｔｈｅＭＬＣｐｒｏｂｌｅｍｓ．ＴｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｓａｎｏｖｅｌＭＬＣａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｔｈｅｒａｎｄｏｍｗａｌｋｍｏｄｅｌ，ｃａｌｌｅｄＭｕｌｔｉＬａｂｅｌＲａｎｄｏｍＷａｌｋ（ＭＬＲＷ）ａｌｇｏｒｉｔｈｍ．Ｆｉｒｓｔｌｙ，ａｍｕｌｔｉｌａｂｅｌｒａｎｄｏｍｗａｌｋｇｒａｐｈｉｓｂｕｉｌｔｏｎｔｈｅｔｒａｉｎｉｎｇｓｅｔ．Ａｓａｎｕｎｌａｂｅｌｅｄｄａｔａａｒｒｉｖｅｓ，ａｍｕｌｔｉｌａｂｅｌｒａｎｄｏｍｗａｌｋｇｒａｐｈｓｙｓｔｅｍｗｉｌｌｂｅｂｕｉｌｔ，ｏｎｗｈｉｃｈｔｈｅｒａｎｄｏｍｗａｌｋｐｒｏｃｅｓｓ

6、ｉｎｇｉｓｃａｒｒｉｅｄｏｕｔ．Ａｆｔｅｒｔｈａｔ，ａｐｒｏｂａｂｉｌｉｔｙｄｉｓｔｒｉｂｕｔｉｏｎａｍｏｎｇａｌｌｌａｂｅｌｓｉｓｏｂｔａｉｎｅｄ．Ａｔｌａｓｔ，ａｔｈｒｅｓｈｏｌｄｌｅａｒｎｉｎｇａｌｇｏｒｉｔｈｍｉｓｐｒｏｐｏｓｅｄｂａｓｅｄｏｎｔｈｅＭＬＲＷａｌｇｏｒｉｔｈｍｓｏｔｈａｔｔｈｅｆｉｎａｌｐｒｅｄｉｃｔｉｏｎｏｎｅａｃｈｌａｂｅｌｉｓｐｒｅｓｅｎｔｅｄ．ＥｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｏｎａｃｔｕａｌｄａｔａｓｅｔｓｈｏｗｔｈａｔｔｈｅＭＬＲＷａｌｇｏｒｉｔｈｍｐｒｏｖｉｄｅｓａｎｅｆｆｅｃｔｉｖｅｓｏｌｕｔｉｏｎｔｏｔｈｅＭＬＣｐｒｏｂｌｅｍｓ．犓犲狔狑狅狉犱

7、狊ｍｕｌｔｉｌａｂｅｌ；ｃｌａｓｓｉｆｉｃａｔｉｏｎ；ｒａｎｄｏｍｗａｌｋ；ｔｈｒｅｓｈｏｌｄｌｅａｒｎｉｎｇ收稿日期：２０１００６１１．本课题得到国家自然科学基金（６０８０３０１６）、国家“九七三”重点基础研究发展规划项目基金（２００７ＣＢ３１０８０２，２００９ＣＢ３２０７０６）和国家“八六三”高技术研究发展计划项目基金（２００８ＡＡ０４２３０１，２００７ＡＡ０４０６０２）资助．郑伟，男，